Merge tag 'arm-soc/for-5.5/maintainers-part2' of https://github.com/Broadcom/stblinux...
[linux-2.6-microblaze.git] / drivers / gpu / drm / omapdrm / tcm-sita.c
1 /*
2  * SImple Tiler Allocator (SiTA): 2D and 1D allocation(reservation) algorithm
3  *
4  * Authors: Ravi Ramachandra <r.ramachandra@ti.com>,
5  *          Lajos Molnar <molnar@ti.com>
6  *          Andy Gross <andy.gross@ti.com>
7  *
8  * Copyright (C) 2012 Texas Instruments Incorporated - http://www.ti.com/
9  *
10  * This package is free software; you can redistribute it and/or modify
11  * it under the terms of the GNU General Public License version 2 as
12  * published by the Free Software Foundation.
13  *
14  * THIS PACKAGE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
15  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
16  * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
17  *
18  */
19 #include <linux/init.h>
20 #include <linux/module.h>
21 #include <linux/errno.h>
22 #include <linux/sched.h>
23 #include <linux/wait.h>
24 #include <linux/bitmap.h>
25 #include <linux/slab.h>
26 #include "tcm.h"
27
28 static unsigned long mask[8];
29 /*
30  * pos          position in bitmap
31  * w            width in slots
32  * h            height in slots
33  * map          ptr to bitmap
34  * stride               slots in a row
35  */
36 static void free_slots(unsigned long pos, u16 w, u16 h,
37                 unsigned long *map, u16 stride)
38 {
39         int i;
40
41         for (i = 0; i < h; i++, pos += stride)
42                 bitmap_clear(map, pos, w);
43 }
44
45 /*
46  * w            width in slots
47  * pos          ptr to position
48  * map          ptr to bitmap
49  * num_bits     number of bits in bitmap
50  */
51 static int r2l_b2t_1d(u16 w, unsigned long *pos, unsigned long *map,
52                 size_t num_bits)
53 {
54         unsigned long search_count = 0;
55         unsigned long bit;
56         bool area_found = false;
57
58         *pos = num_bits - w;
59
60         while (search_count < num_bits) {
61                 bit = find_next_bit(map, num_bits, *pos);
62
63                 if (bit - *pos >= w) {
64                         /* found a long enough free area */
65                         bitmap_set(map, *pos, w);
66                         area_found = true;
67                         break;
68                 }
69
70                 search_count = num_bits - bit + w;
71                 *pos = bit - w;
72         }
73
74         return (area_found) ? 0 : -ENOMEM;
75 }
76
77 /*
78  * w = width in slots
79  * h = height in slots
80  * a = align in slots   (mask, 2^n-1, 0 is unaligned)
81  * offset = offset in bytes from 4KiB
82  * pos = position in bitmap for buffer
83  * map = bitmap ptr
84  * num_bits = size of bitmap
85  * stride = bits in one row of container
86  */
87 static int l2r_t2b(u16 w, u16 h, u16 a, s16 offset,
88                 unsigned long *pos, unsigned long slot_bytes,
89                 unsigned long *map, size_t num_bits, size_t slot_stride)
90 {
91         int i;
92         unsigned long index;
93         bool area_free = false;
94         unsigned long slots_per_band = PAGE_SIZE / slot_bytes;
95         unsigned long bit_offset = (offset > 0) ? offset / slot_bytes : 0;
96         unsigned long curr_bit = bit_offset;
97
98         /* reset alignment to 1 if we are matching a specific offset */
99         /* adjust alignment - 1 to get to the format expected in bitmaps */
100         a = (offset > 0) ? 0 : a - 1;
101
102         /* FIXME Return error if slots_per_band > stride */
103
104         while (curr_bit < num_bits) {
105                 *pos = bitmap_find_next_zero_area(map, num_bits, curr_bit, w,
106                                 a);
107
108                 /* skip forward if we are not at right offset */
109                 if (bit_offset > 0 && (*pos % slots_per_band != bit_offset)) {
110                         curr_bit = ALIGN(*pos, slots_per_band) + bit_offset;
111                         continue;
112                 }
113
114                 /* skip forward to next row if we overlap end of row */
115                 if ((*pos % slot_stride) + w > slot_stride) {
116                         curr_bit = ALIGN(*pos, slot_stride) + bit_offset;
117                         continue;
118                 }
119
120                 /* TODO: Handle overlapping 4K boundaries */
121
122                 /* break out of look if we will go past end of container */
123                 if ((*pos + slot_stride * h) > num_bits)
124                         break;
125
126                 /* generate mask that represents out matching pattern */
127                 bitmap_clear(mask, 0, slot_stride);
128                 bitmap_set(mask, (*pos % BITS_PER_LONG), w);
129
130                 /* assume the area is free until we find an overlap */
131                 area_free = true;
132
133                 /* check subsequent rows to see if complete area is free */
134                 for (i = 1; i < h; i++) {
135                         index = *pos / BITS_PER_LONG + i * 8;
136                         if (bitmap_intersects(&map[index], mask,
137                                 (*pos % BITS_PER_LONG) + w)) {
138                                 area_free = false;
139                                 break;
140                         }
141                 }
142
143                 if (area_free)
144                         break;
145
146                 /* go forward past this match */
147                 if (bit_offset > 0)
148                         curr_bit = ALIGN(*pos, slots_per_band) + bit_offset;
149                 else
150                         curr_bit = *pos + a + 1;
151         }
152
153         if (area_free) {
154                 /* set area as in-use. iterate over rows */
155                 for (i = 0, index = *pos; i < h; i++, index += slot_stride)
156                         bitmap_set(map, index, w);
157         }
158
159         return (area_free) ? 0 : -ENOMEM;
160 }
161
162 static s32 sita_reserve_1d(struct tcm *tcm, u32 num_slots,
163                            struct tcm_area *area)
164 {
165         unsigned long pos;
166         int ret;
167
168         spin_lock(&(tcm->lock));
169         ret = r2l_b2t_1d(num_slots, &pos, tcm->bitmap, tcm->map_size);
170         if (!ret) {
171                 area->p0.x = pos % tcm->width;
172                 area->p0.y = pos / tcm->width;
173                 area->p1.x = (pos + num_slots - 1) % tcm->width;
174                 area->p1.y = (pos + num_slots - 1) / tcm->width;
175         }
176         spin_unlock(&(tcm->lock));
177
178         return ret;
179 }
180
181 static s32 sita_reserve_2d(struct tcm *tcm, u16 h, u16 w, u16 align,
182                                 s16 offset, u16 slot_bytes,
183                                 struct tcm_area *area)
184 {
185         unsigned long pos;
186         int ret;
187
188         spin_lock(&(tcm->lock));
189         ret = l2r_t2b(w, h, align, offset, &pos, slot_bytes, tcm->bitmap,
190                         tcm->map_size, tcm->width);
191
192         if (!ret) {
193                 area->p0.x = pos % tcm->width;
194                 area->p0.y = pos / tcm->width;
195                 area->p1.x = area->p0.x + w - 1;
196                 area->p1.y = area->p0.y + h - 1;
197         }
198         spin_unlock(&(tcm->lock));
199
200         return ret;
201 }
202
203 static void sita_deinit(struct tcm *tcm)
204 {
205         kfree(tcm);
206 }
207
208 static s32 sita_free(struct tcm *tcm, struct tcm_area *area)
209 {
210         unsigned long pos;
211         u16 w, h;
212
213         pos = area->p0.x + area->p0.y * tcm->width;
214         if (area->is2d) {
215                 w = area->p1.x - area->p0.x + 1;
216                 h = area->p1.y - area->p0.y + 1;
217         } else {
218                 w = area->p1.x + area->p1.y * tcm->width - pos + 1;
219                 h = 1;
220         }
221
222         spin_lock(&(tcm->lock));
223         free_slots(pos, w, h, tcm->bitmap, tcm->width);
224         spin_unlock(&(tcm->lock));
225         return 0;
226 }
227
228 struct tcm *sita_init(u16 width, u16 height)
229 {
230         struct tcm *tcm;
231         size_t map_size = BITS_TO_LONGS(width*height) * sizeof(unsigned long);
232
233         if (width == 0 || height == 0)
234                 return NULL;
235
236         tcm = kzalloc(sizeof(*tcm) + map_size, GFP_KERNEL);
237         if (!tcm)
238                 goto error;
239
240         /* Updating the pointers to SiTA implementation APIs */
241         tcm->height = height;
242         tcm->width = width;
243         tcm->reserve_2d = sita_reserve_2d;
244         tcm->reserve_1d = sita_reserve_1d;
245         tcm->free = sita_free;
246         tcm->deinit = sita_deinit;
247
248         spin_lock_init(&tcm->lock);
249         tcm->bitmap = (unsigned long *)(tcm + 1);
250         bitmap_clear(tcm->bitmap, 0, width*height);
251
252         tcm->map_size = width*height;
253
254         return tcm;
255
256 error:
257         kfree(tcm);
258         return NULL;
259 }