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