Branch data Line data Source code
1 : : /* SPDX-License-Identifier: BSD-3-Clause
2 : : * Copyright(c) 2019-2023 Broadcom
3 : : * All rights reserved.
4 : : */
5 : :
6 : : #include "bitalloc.h"
7 : :
8 : : #define BITALLOC_MAX_LEVELS 6
9 : :
10 : : /* Finds the last bit set plus 1, equivalent to gcc __builtin_fls */
11 : : static int
12 : 0 : ba_fls(bitalloc_word_t v)
13 : : {
14 : : int c = 32;
15 : :
16 [ # # ]: 0 : if (!v)
17 : : return 0;
18 : :
19 [ # # ]: 0 : if (!(v & 0xFFFF0000u)) {
20 : 0 : v <<= 16;
21 : : c -= 16;
22 : : }
23 [ # # ]: 0 : if (!(v & 0xFF000000u)) {
24 : 0 : v <<= 8;
25 : 0 : c -= 8;
26 : : }
27 [ # # ]: 0 : if (!(v & 0xF0000000u)) {
28 : 0 : v <<= 4;
29 : 0 : c -= 4;
30 : : }
31 [ # # ]: 0 : if (!(v & 0xC0000000u)) {
32 : 0 : v <<= 2;
33 : 0 : c -= 2;
34 : : }
35 [ # # ]: 0 : if (!(v & 0x80000000u)) {
36 : : v <<= 1;
37 : 0 : c -= 1;
38 : : }
39 : :
40 : : return c;
41 : : }
42 : :
43 : : /* Finds the first bit set plus 1, equivalent to gcc __builtin_ffs */
44 : : static int
45 : 0 : ba_ffs(bitalloc_word_t v)
46 : : {
47 : : int c; /* c will be the number of zero bits on the right plus 1 */
48 : :
49 : 0 : v &= -v;
50 [ # # ]: 0 : c = v ? 32 : 0;
51 : :
52 [ # # ]: 0 : if (v & 0x0000FFFF)
53 : 0 : c -= 16;
54 [ # # ]: 0 : if (v & 0x00FF00FF)
55 : 0 : c -= 8;
56 [ # # ]: 0 : if (v & 0x0F0F0F0F)
57 : 0 : c -= 4;
58 [ # # ]: 0 : if (v & 0x33333333)
59 : 0 : c -= 2;
60 [ # # ]: 0 : if (v & 0x55555555)
61 : 0 : c -= 1;
62 : :
63 : 0 : return c;
64 : : }
65 : :
66 : : int
67 : 0 : ba_init(struct bitalloc *pool, int size, bool free)
68 : : {
69 : : bitalloc_word_t *mem = (bitalloc_word_t *)pool;
70 : : int i;
71 : :
72 : : /* Initialize */
73 : 0 : pool->size = 0;
74 : :
75 [ # # ]: 0 : if (size < 1 || size > BITALLOC_MAX_SIZE)
76 : : return -1;
77 : :
78 : : /* Zero structure */
79 : : for (i = 0;
80 [ # # # # : 0 : i < (int)(BITALLOC_SIZEOF(size) / sizeof(bitalloc_word_t));
# # # # #
# ]
81 : 0 : i++)
82 : 0 : mem[i] = 0;
83 : :
84 : : /* Initialize */
85 : 0 : pool->size = size;
86 : :
87 : : /* Embed number of words of next level, after each level */
88 : : int words[BITALLOC_MAX_LEVELS];
89 : : int lev = 0;
90 : : int offset = 0;
91 : :
92 : 0 : words[0] = (size + 31) / 32;
93 [ # # ]: 0 : while (words[lev] > 1) {
94 : 0 : lev++;
95 : 0 : words[lev] = (words[lev - 1] + 31) / 32;
96 : : }
97 : :
98 [ # # ]: 0 : while (lev) {
99 : 0 : offset += words[lev];
100 : 0 : pool->storage[offset++] = words[--lev];
101 : : }
102 : :
103 : : /* Free the entire pool if it is required*/
104 [ # # ]: 0 : if (free) {
105 [ # # ]: 0 : for (i = 0; i < size; i++)
106 : 0 : ba_free(pool, i);
107 : : }
108 : :
109 : : return 0;
110 : : }
111 : :
112 : : static int
113 : 0 : ba_alloc_helper(struct bitalloc *pool,
114 : : int offset,
115 : : int words,
116 : : unsigned int size,
117 : : int index,
118 : : int *clear)
119 : : {
120 : 0 : bitalloc_word_t *storage = &pool->storage[offset];
121 : 0 : int loc = ba_ffs(storage[index]);
122 : : int r;
123 : :
124 [ # # ]: 0 : if (loc == 0)
125 : : return -1;
126 : :
127 : 0 : loc--;
128 : :
129 [ # # ]: 0 : if (pool->size > size) {
130 : 0 : r = ba_alloc_helper(pool,
131 : 0 : offset + words + 1,
132 : 0 : storage[words],
133 : : size * 32,
134 : 0 : index * 32 + loc,
135 : : clear);
136 : : } else {
137 : 0 : r = index * 32 + loc;
138 : 0 : *clear = 1;
139 : 0 : pool->free_count--;
140 : : }
141 : :
142 [ # # ]: 0 : if (*clear) {
143 : 0 : storage[index] &= ~(1 << loc);
144 : 0 : *clear = (storage[index] == 0);
145 : : }
146 : :
147 : : return r;
148 : : }
149 : :
150 : : int
151 : 0 : ba_alloc(struct bitalloc *pool)
152 : : {
153 : 0 : int clear = 0;
154 : :
155 : 0 : return ba_alloc_helper(pool, 0, 1, 32, 0, &clear);
156 : : }
157 : :
158 : : /**
159 : : * Help function to alloc entry from highest available index
160 : : *
161 : : * Searching the pool from highest index for the empty entry.
162 : : *
163 : : * [in] pool
164 : : * Pointer to the resource pool
165 : : *
166 : : * [in] offset
167 : : * Offset of the storage in the pool
168 : : *
169 : : * [in] words
170 : : * Number of words in this level
171 : : *
172 : : * [in] size
173 : : * Number of entries in this level
174 : : *
175 : : * [in] index
176 : : * Index of words that has the entry
177 : : *
178 : : * [in] clear
179 : : * Indicate if a bit needs to be clear due to the entry is allocated
180 : : *
181 : : * Returns:
182 : : * 0 - Success
183 : : * -1 - Failure
184 : : */
185 : : static int
186 : 0 : ba_alloc_reverse_helper(struct bitalloc *pool,
187 : : int offset,
188 : : int words,
189 : : unsigned int size,
190 : : int index,
191 : : int *clear)
192 : : {
193 : 0 : bitalloc_word_t *storage = &pool->storage[offset];
194 : 0 : int loc = ba_fls(storage[index]);
195 : : int r;
196 : :
197 [ # # ]: 0 : if (loc == 0)
198 : : return -1;
199 : :
200 : 0 : loc--;
201 : :
202 [ # # ]: 0 : if (pool->size > size) {
203 : 0 : r = ba_alloc_reverse_helper(pool,
204 : 0 : offset + words + 1,
205 : 0 : storage[words],
206 : : size * 32,
207 : 0 : index * 32 + loc,
208 : : clear);
209 : : } else {
210 : 0 : r = index * 32 + loc;
211 : 0 : *clear = 1;
212 : 0 : pool->free_count--;
213 : : }
214 : :
215 [ # # ]: 0 : if (*clear) {
216 : 0 : storage[index] &= ~(1 << loc);
217 : 0 : *clear = (storage[index] == 0);
218 : : }
219 : :
220 : : return r;
221 : : }
222 : :
223 : : int
224 : 0 : ba_alloc_reverse(struct bitalloc *pool)
225 : : {
226 : 0 : int clear = 0;
227 : :
228 : 0 : return ba_alloc_reverse_helper(pool, 0, 1, 32, 0, &clear);
229 : : }
230 : :
231 : : static int
232 : 0 : ba_alloc_index_helper(struct bitalloc *pool,
233 : : int offset,
234 : : int words,
235 : : unsigned int size,
236 : : int *index,
237 : : int *clear)
238 : : {
239 : 0 : bitalloc_word_t *storage = &pool->storage[offset];
240 : : int loc;
241 : : int r;
242 : :
243 [ # # ]: 0 : if (pool->size > size)
244 : 0 : r = ba_alloc_index_helper(pool,
245 : 0 : offset + words + 1,
246 : 0 : storage[words],
247 : : size * 32,
248 : : index,
249 : : clear);
250 : : else
251 : : r = 1; /* Check if already allocated */
252 : :
253 : 0 : loc = (*index % 32);
254 : 0 : *index = *index / 32;
255 : :
256 [ # # ]: 0 : if (r == 1) {
257 [ # # ]: 0 : r = (storage[*index] & (1 << loc)) ? 0 : -1;
258 : : if (r == 0) {
259 : 0 : *clear = 1;
260 : 0 : pool->free_count--;
261 : : }
262 : : }
263 : :
264 [ # # ]: 0 : if (*clear) {
265 : 0 : storage[*index] &= ~(1 << loc);
266 : 0 : *clear = (storage[*index] == 0);
267 : : }
268 : :
269 : 0 : return r;
270 : : }
271 : :
272 : : int
273 : 0 : ba_alloc_index(struct bitalloc *pool, int index)
274 : : {
275 : 0 : int clear = 0;
276 : 0 : int index_copy = index;
277 : :
278 [ # # # # ]: 0 : if (index < 0 || index >= (int)pool->size)
279 : : return -1;
280 : :
281 [ # # ]: 0 : if (ba_alloc_index_helper(pool, 0, 1, 32, &index_copy, &clear) >= 0)
282 : : return index;
283 : : else
284 : 0 : return -1;
285 : : }
286 : :
287 : : static int
288 : 0 : ba_inuse_helper(struct bitalloc *pool,
289 : : int offset,
290 : : int words,
291 : : unsigned int size,
292 : : int *index)
293 : : {
294 : 0 : bitalloc_word_t *storage = &pool->storage[offset];
295 : : int loc;
296 : : int r;
297 : :
298 [ # # ]: 0 : if (pool->size > size)
299 : 0 : r = ba_inuse_helper(pool,
300 : 0 : offset + words + 1,
301 : 0 : storage[words],
302 : : size * 32,
303 : : index);
304 : : else
305 : : r = 1; /* Check if in use */
306 : :
307 : 0 : loc = (*index % 32);
308 : 0 : *index = *index / 32;
309 : :
310 [ # # ]: 0 : if (r == 1)
311 [ # # ]: 0 : r = (storage[*index] & (1 << loc)) ? -1 : 0;
312 : :
313 : 0 : return r;
314 : : }
315 : :
316 : : int
317 : 0 : ba_inuse(struct bitalloc *pool, int index)
318 : : {
319 [ # # # # ]: 0 : if (index < 0 || index >= (int)pool->size)
320 : : return -1;
321 : :
322 : 0 : return ba_inuse_helper(pool, 0, 1, 32, &index) == 0;
323 : : }
324 : :
325 : : static int
326 : 0 : ba_free_helper(struct bitalloc *pool,
327 : : int offset,
328 : : int words,
329 : : unsigned int size,
330 : : int *index)
331 : : {
332 : 0 : bitalloc_word_t *storage = &pool->storage[offset];
333 : : int loc;
334 : : int r;
335 : :
336 [ # # ]: 0 : if (pool->size > size)
337 : 0 : r = ba_free_helper(pool,
338 : 0 : offset + words + 1,
339 : 0 : storage[words],
340 : : size * 32,
341 : : index);
342 : : else
343 : : r = 1; /* Check if already free */
344 : :
345 : 0 : loc = (*index % 32);
346 : 0 : *index = *index / 32;
347 : :
348 [ # # ]: 0 : if (r == 1) {
349 [ # # ]: 0 : r = (storage[*index] & (1 << loc)) ? -1 : 0;
350 : : if (r == 0)
351 : 0 : pool->free_count++;
352 : : }
353 : :
354 [ # # ]: 0 : if (r == 0)
355 : 0 : storage[*index] |= (1 << loc);
356 : :
357 : 0 : return r;
358 : : }
359 : :
360 : : int
361 : 0 : ba_free(struct bitalloc *pool, int index)
362 : : {
363 [ # # # # ]: 0 : if (index < 0 || index >= (int)pool->size)
364 : : return -1;
365 : :
366 : 0 : return ba_free_helper(pool, 0, 1, 32, &index);
367 : : }
368 : :
369 : : int
370 : 0 : ba_inuse_free(struct bitalloc *pool, int index)
371 : : {
372 [ # # # # ]: 0 : if (index < 0 || index >= (int)pool->size)
373 : : return -1;
374 : :
375 : 0 : return ba_free_helper(pool, 0, 1, 32, &index) + 1;
376 : : }
377 : :
378 : : int
379 : 0 : ba_free_count(struct bitalloc *pool)
380 : : {
381 : 0 : return (int)pool->free_count;
382 : : }
383 : :
384 : 0 : int ba_inuse_count(struct bitalloc *pool)
385 : : {
386 : 0 : return (int)(pool->size) - (int)(pool->free_count);
387 : : }
388 : :
389 : : static int
390 : 0 : ba_find_next_helper(struct bitalloc *pool,
391 : : int offset,
392 : : int words,
393 : : unsigned int size,
394 : : int *index,
395 : : int free)
396 : : {
397 : 0 : bitalloc_word_t *storage = &pool->storage[offset];
398 : : int loc, r, bottom = 0;
399 : :
400 [ # # ]: 0 : if (pool->size > size)
401 : 0 : r = ba_find_next_helper(pool,
402 : 0 : offset + words + 1,
403 : 0 : storage[words],
404 : : size * 32,
405 : : index,
406 : : free);
407 : : else
408 : : bottom = 1; /* Bottom of tree */
409 : :
410 : 0 : loc = (*index % 32);
411 : 0 : *index = *index / 32;
412 : :
413 [ # # ]: 0 : if (bottom) {
414 : 0 : int bit_index = *index * 32;
415 : :
416 : 0 : loc = ba_ffs(~storage[*index] & ((bitalloc_word_t)-1 << loc));
417 [ # # ]: 0 : if (loc > 0) {
418 : 0 : loc--;
419 : 0 : r = (bit_index + loc);
420 [ # # ]: 0 : if (r >= (int)pool->size)
421 : : r = -1;
422 : : } else {
423 : : /* Loop over array at bottom of tree */
424 : : r = -1;
425 : 0 : bit_index += 32;
426 : 0 : *index = *index + 1;
427 [ # # ]: 0 : while ((int)pool->size > bit_index) {
428 : 0 : loc = ba_ffs(~storage[*index]);
429 : :
430 [ # # ]: 0 : if (loc > 0) {
431 : 0 : loc--;
432 : 0 : r = (bit_index + loc);
433 [ # # ]: 0 : if (r >= (int)pool->size)
434 : : r = -1;
435 : : break;
436 : : }
437 : 0 : bit_index += 32;
438 : 0 : *index = *index + 1;
439 : : }
440 : : }
441 : : }
442 : :
443 [ # # ]: 0 : if (r >= 0 && (free)) {
444 [ # # ]: 0 : if (bottom)
445 : 0 : pool->free_count++;
446 : 0 : storage[*index] |= (1 << loc);
447 : : }
448 : :
449 : 0 : return r;
450 : : }
451 : :
452 : : int
453 : 0 : ba_find_next_inuse(struct bitalloc *pool, int index)
454 : : {
455 [ # # ]: 0 : if (index < 0 ||
456 [ # # ]: 0 : index >= (int)pool->size ||
457 [ # # ]: 0 : pool->free_count == pool->size)
458 : : return -1;
459 : :
460 : 0 : return ba_find_next_helper(pool, 0, 1, 32, &index, 0);
461 : : }
462 : :
463 : : int
464 : 0 : ba_find_next_inuse_free(struct bitalloc *pool, int index)
465 : : {
466 [ # # ]: 0 : if (index < 0 ||
467 [ # # ]: 0 : index >= (int)pool->size ||
468 [ # # ]: 0 : pool->free_count == pool->size)
469 : : return -1;
470 : :
471 : 0 : return ba_find_next_helper(pool, 0, 1, 32, &index, 1);
472 : : }
|