1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2019-2020 Broadcom
8 #define BITALLOC_MAX_LEVELS 6
11 /* Finds the last bit set plus 1, equivalent to gcc __builtin_fls */
13 ba_fls(bitalloc_word_t v)
20 if (!(v & 0xFFFF0000u)) {
24 if (!(v & 0xFF000000u)) {
28 if (!(v & 0xF0000000u)) {
32 if (!(v & 0xC0000000u)) {
36 if (!(v & 0x80000000u)) {
44 /* Finds the first bit set plus 1, equivalent to gcc __builtin_ffs */
46 ba_ffs(bitalloc_word_t v)
48 int c; /* c will be the number of zero bits on the right plus 1 */
68 ba_init(struct bitalloc *pool, int size)
70 bitalloc_word_t *mem = (bitalloc_word_t *)pool;
76 if (size < 1 || size > BITALLOC_MAX_SIZE)
81 i < (int)(BITALLOC_SIZEOF(size) / sizeof(bitalloc_word_t));
88 /* Embed number of words of next level, after each level */
89 int words[BITALLOC_MAX_LEVELS];
93 words[0] = (size + 31) / 32;
94 while (words[lev] > 1) {
96 words[lev] = (words[lev - 1] + 31) / 32;
100 offset += words[lev];
101 pool->storage[offset++] = words[--lev];
104 /* Free the entire pool */
105 for (i = 0; i < size; i++)
112 ba_alloc_helper(struct bitalloc *pool,
119 bitalloc_word_t *storage = &pool->storage[offset];
120 int loc = ba_ffs(storage[index]);
128 if (pool->size > size) {
129 r = ba_alloc_helper(pool,
136 r = index * 32 + loc;
142 storage[index] &= ~(1 << loc);
143 *clear = (storage[index] == 0);
150 ba_alloc(struct bitalloc *pool)
154 return ba_alloc_helper(pool, 0, 1, 32, 0, &clear);
158 * Help function to alloc entry from highest available index
160 * Searching the pool from highest index for the empty entry.
163 * Pointer to the resource pool
166 * Offset of the storage in the pool
169 * Number of words in this level
172 * Number of entries in this level
175 * Index of words that has the entry
178 * Indicate if a bit needs to be clear due to the entry is allocated
185 ba_alloc_reverse_helper(struct bitalloc *pool,
192 bitalloc_word_t *storage = &pool->storage[offset];
193 int loc = ba_fls(storage[index]);
201 if (pool->size > size) {
202 r = ba_alloc_reverse_helper(pool,
209 r = index * 32 + loc;
215 storage[index] &= ~(1 << loc);
216 *clear = (storage[index] == 0);
223 ba_alloc_reverse(struct bitalloc *pool)
227 return ba_alloc_reverse_helper(pool, 0, 1, 32, 0, &clear);
231 ba_alloc_index_helper(struct bitalloc *pool,
238 bitalloc_word_t *storage = &pool->storage[offset];
242 if (pool->size > size)
243 r = ba_alloc_index_helper(pool,
250 r = 1; /* Check if already allocated */
253 *index = *index / 32;
256 r = (storage[*index] & (1 << loc)) ? 0 : -1;
264 storage[*index] &= ~(1 << loc);
265 *clear = (storage[*index] == 0);
272 ba_alloc_index(struct bitalloc *pool, int index)
275 int index_copy = index;
277 if (index < 0 || index >= (int)pool->size)
280 if (ba_alloc_index_helper(pool, 0, 1, 32, &index_copy, &clear) >= 0)
287 ba_inuse_helper(struct bitalloc *pool,
293 bitalloc_word_t *storage = &pool->storage[offset];
297 if (pool->size > size)
298 r = ba_inuse_helper(pool,
304 r = 1; /* Check if in use */
307 *index = *index / 32;
310 r = (storage[*index] & (1 << loc)) ? -1 : 0;
316 ba_inuse(struct bitalloc *pool, int index)
318 if (index < 0 || index >= (int)pool->size)
321 return ba_inuse_helper(pool, 0, 1, 32, &index) == 0;
325 ba_free_helper(struct bitalloc *pool,
331 bitalloc_word_t *storage = &pool->storage[offset];
335 if (pool->size > size)
336 r = ba_free_helper(pool,
342 r = 1; /* Check if already free */
345 *index = *index / 32;
348 r = (storage[*index] & (1 << loc)) ? -1 : 0;
354 storage[*index] |= (1 << loc);
360 ba_free(struct bitalloc *pool, int index)
362 if (index < 0 || index >= (int)pool->size)
365 return ba_free_helper(pool, 0, 1, 32, &index);
369 ba_inuse_free(struct bitalloc *pool, int index)
371 if (index < 0 || index >= (int)pool->size)
374 return ba_free_helper(pool, 0, 1, 32, &index) + 1;
378 ba_free_count(struct bitalloc *pool)
380 return (int)pool->free_count;
383 int ba_inuse_count(struct bitalloc *pool)
385 return (int)(pool->size) - (int)(pool->free_count);
389 ba_find_next_helper(struct bitalloc *pool,
396 bitalloc_word_t *storage = &pool->storage[offset];
397 int loc, r, bottom = 0;
399 if (pool->size > size)
400 r = ba_find_next_helper(pool,
407 bottom = 1; /* Bottom of tree */
410 *index = *index / 32;
413 int bit_index = *index * 32;
415 loc = ba_ffs(~storage[*index] & ((bitalloc_word_t)-1 << loc));
418 r = (bit_index + loc);
419 if (r >= (int)pool->size)
422 /* Loop over array at bottom of tree */
426 while ((int)pool->size > bit_index) {
427 loc = ba_ffs(~storage[*index]);
431 r = (bit_index + loc);
432 if (r >= (int)pool->size)
442 if (r >= 0 && (free)) {
445 storage[*index] |= (1 << loc);
452 ba_find_next_inuse(struct bitalloc *pool, int index)
455 index >= (int)pool->size ||
456 pool->free_count == pool->size)
459 return ba_find_next_helper(pool, 0, 1, 32, &index, 0);
463 ba_find_next_inuse_free(struct bitalloc *pool, int index)
466 index >= (int)pool->size ||
467 pool->free_count == pool->size)
470 return ba_find_next_helper(pool, 0, 1, 32, &index, 1);