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