Commit | Line | Data |
---|---|---|
71e8831f AG |
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> | |
0d6fa53f | 8 | * Andy Gross <andy.gross@ti.com> |
71e8831f | 9 | * |
0d6fa53f | 10 | * Copyright (C) 2012 Texas Instruments, Inc. |
71e8831f AG |
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 | */ | |
0d6fa53f AG |
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> | |
71e8831f | 27 | #include <linux/slab.h> |
0d6fa53f | 28 | #include "tcm.h" |
71e8831f | 29 | |
0d6fa53f AG |
30 | static 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 | |
71e8831f | 37 | */ |
0d6fa53f AG |
38 | static void free_slots(unsigned long pos, uint16_t w, uint16_t h, |
39 | unsigned long *map, uint16_t stride) | |
71e8831f | 40 | { |
0d6fa53f | 41 | int i; |
71e8831f | 42 | |
0d6fa53f AG |
43 | for (i = 0; i < h; i++, pos += stride) |
44 | bitmap_clear(map, pos, w); | |
71e8831f AG |
45 | } |
46 | ||
0d6fa53f AG |
47 | /* |
48 | * w width in slots | |
49 | * pos ptr to position | |
50 | * map ptr to bitmap | |
51 | * num_bits number of bits in bitmap | |
71e8831f | 52 | */ |
0d6fa53f AG |
53 | static int r2l_b2t_1d(uint16_t w, unsigned long *pos, unsigned long *map, |
54 | size_t num_bits) | |
71e8831f | 55 | { |
0d6fa53f AG |
56 | unsigned long search_count = 0; |
57 | unsigned long bit; | |
58 | bool area_found = false; | |
71e8831f | 59 | |
0d6fa53f | 60 | *pos = num_bits - w; |
71e8831f | 61 | |
0d6fa53f AG |
62 | while (search_count < num_bits) { |
63 | bit = find_next_bit(map, num_bits, *pos); | |
71e8831f | 64 | |
0d6fa53f AG |
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 | } | |
71e8831f | 71 | |
0d6fa53f AG |
72 | search_count = num_bits - bit + w; |
73 | *pos = bit - w; | |
74 | } | |
75 | ||
76 | return (area_found) ? 0 : -ENOMEM; | |
71e8831f AG |
77 | } |
78 | ||
0d6fa53f AG |
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 | |
71e8831f | 88 | */ |
0d6fa53f AG |
89 | static 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) | |
71e8831f | 92 | { |
0d6fa53f AG |
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 | } | |
71e8831f | 115 | |
0d6fa53f AG |
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 | } | |
71e8831f | 121 | |
0d6fa53f | 122 | /* TODO: Handle overlapping 4K boundaries */ |
71e8831f | 123 | |
0d6fa53f AG |
124 | /* break out of look if we will go past end of container */ |
125 | if ((*pos + slot_stride * h) > num_bits) | |
126 | break; | |
71e8831f | 127 | |
0d6fa53f AG |
128 | /* generate mask that represents out matching pattern */ |
129 | bitmap_clear(mask, 0, slot_stride); | |
130 | bitmap_set(mask, (*pos % BITS_PER_LONG), w); | |
71e8831f | 131 | |
0d6fa53f AG |
132 | /* assume the area is free until we find an overlap */ |
133 | area_free = true; | |
71e8831f | 134 | |
0d6fa53f AG |
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; | |
71e8831f | 141 | break; |
71e8831f AG |
142 | } |
143 | } | |
144 | ||
0d6fa53f | 145 | if (area_free) |
71e8831f | 146 | break; |
71e8831f | 147 | |
0d6fa53f AG |
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 | } | |
71e8831f | 154 | |
0d6fa53f AG |
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); | |
71e8831f AG |
159 | } |
160 | ||
0d6fa53f | 161 | return (area_free) ? 0 : -ENOMEM; |
71e8831f AG |
162 | } |
163 | ||
0d6fa53f AG |
164 | static s32 sita_reserve_1d(struct tcm *tcm, u32 num_slots, |
165 | struct tcm_area *area) | |
71e8831f | 166 | { |
0d6fa53f AG |
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; | |
71e8831f | 177 | } |
0d6fa53f | 178 | spin_unlock(&(tcm->lock)); |
71e8831f | 179 | |
0d6fa53f | 180 | return ret; |
71e8831f AG |
181 | } |
182 | ||
0d6fa53f AG |
183 | static 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) | |
71e8831f | 186 | { |
0d6fa53f AG |
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; | |
71e8831f | 199 | } |
0d6fa53f | 200 | spin_unlock(&(tcm->lock)); |
71e8831f AG |
201 | |
202 | return ret; | |
203 | } | |
204 | ||
0d6fa53f | 205 | static void sita_deinit(struct tcm *tcm) |
71e8831f | 206 | { |
0d6fa53f | 207 | kfree(tcm); |
71e8831f AG |
208 | } |
209 | ||
0d6fa53f | 210 | static s32 sita_free(struct tcm *tcm, struct tcm_area *area) |
71e8831f | 211 | { |
0d6fa53f AG |
212 | unsigned long pos; |
213 | uint16_t w, h; | |
71e8831f | 214 | |
0d6fa53f AG |
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; | |
71e8831f | 222 | } |
0d6fa53f AG |
223 | |
224 | spin_lock(&(tcm->lock)); | |
225 | free_slots(pos, w, h, tcm->bitmap, tcm->width); | |
226 | spin_unlock(&(tcm->lock)); | |
227 | return 0; | |
71e8831f AG |
228 | } |
229 | ||
0d6fa53f | 230 | struct tcm *sita_init(u16 width, u16 height) |
71e8831f | 231 | { |
0d6fa53f AG |
232 | struct tcm *tcm; |
233 | size_t map_size = BITS_TO_LONGS(width*height) * sizeof(unsigned long); | |
71e8831f | 234 | |
0d6fa53f AG |
235 | if (width == 0 || height == 0) |
236 | return NULL; | |
71e8831f | 237 | |
0d6fa53f AG |
238 | tcm = kzalloc(sizeof(*tcm) + map_size, GFP_KERNEL); |
239 | if (!tcm) | |
240 | goto error; | |
71e8831f | 241 | |
0d6fa53f AG |
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; | |
71e8831f | 249 | |
0d6fa53f AG |
250 | spin_lock_init(&tcm->lock); |
251 | tcm->bitmap = (unsigned long *)(tcm + 1); | |
252 | bitmap_clear(tcm->bitmap, 0, width*height); | |
71e8831f | 253 | |
0d6fa53f | 254 | tcm->map_size = width*height; |
71e8831f | 255 | |
0d6fa53f | 256 | return tcm; |
71e8831f | 257 | |
0d6fa53f AG |
258 | error: |
259 | kfree(tcm); | |
260 | return NULL; | |
71e8831f | 261 | } |