1 /* SPDX-License-Identifier: BSD-3-Clause 2 * Copyright(c) 2019-2020 Broadcom 3 * All rights reserved. 4 */ 5 6 #ifndef _BITALLOC_H_ 7 #define _BITALLOC_H_ 8 9 #include <stdint.h> 10 11 /* Bitalloc works on uint32_t as its word size */ 12 typedef uint32_t bitalloc_word_t; 13 14 struct bitalloc { 15 bitalloc_word_t size; 16 bitalloc_word_t free_count; 17 bitalloc_word_t storage[1]; 18 }; 19 20 #define BA_L0(s) (((s) + 31) / 32) 21 #define BA_L1(s) ((BA_L0(s) + 31) / 32) 22 #define BA_L2(s) ((BA_L1(s) + 31) / 32) 23 #define BA_L3(s) ((BA_L2(s) + 31) / 32) 24 #define BA_L4(s) ((BA_L3(s) + 31) / 32) 25 26 #define BITALLOC_SIZEOF(size) \ 27 (sizeof(struct bitalloc) * \ 28 (((sizeof(struct bitalloc) + \ 29 sizeof(struct bitalloc) - 1 + \ 30 (sizeof(bitalloc_word_t) * \ 31 ((BA_L0(size) - 1) + \ 32 ((BA_L0(size) == 1) ? 0 : (BA_L1(size) + 1)) + \ 33 ((BA_L1(size) == 1) ? 0 : (BA_L2(size) + 1)) + \ 34 ((BA_L2(size) == 1) ? 0 : (BA_L3(size) + 1)) + \ 35 ((BA_L3(size) == 1) ? 0 : (BA_L4(size) + 1)))))) / \ 36 sizeof(struct bitalloc))) 37 38 #define BITALLOC_MAX_SIZE (32 * 32 * 32 * 32 * 32 * 32) 39 40 /* The instantiation of a bitalloc looks a bit odd. Since a 41 * bit allocator has variable storage, we need a way to get a 42 * a pointer to a bitalloc structure that points to the correct 43 * amount of storage. We do this by creating an array of 44 * bitalloc where the first element in the array is the 45 * actual bitalloc base structure, and the remaining elements 46 * in the array provide the storage for it. This approach allows 47 * instances to be individual variables or members of larger 48 * structures. 49 */ 50 #define BITALLOC_INST(name, size) \ 51 struct bitalloc name[(BITALLOC_SIZEOF(size) / \ 52 sizeof(struct bitalloc))] 53 54 /* Symbolic return codes */ 55 #define BA_SUCCESS 0 56 #define BA_FAIL -1 57 #define BA_ENTRY_FREE 0 58 #define BA_ENTRY_IN_USE 1 59 #define BA_NO_ENTRY_FOUND -1 60 61 /** 62 * Initializates the bitallocator 63 * 64 * Returns 0 on success, -1 on failure. Size is arbitrary up to 65 * BITALLOC_MAX_SIZE 66 */ 67 int ba_init(struct bitalloc *pool, int size); 68 69 /** 70 * Returns -1 on failure, or index of allocated entry 71 */ 72 int ba_alloc(struct bitalloc *pool); 73 int ba_alloc_index(struct bitalloc *pool, int index); 74 75 /** 76 * Query a particular index in a pool to check if its in use. 77 * 78 * Returns -1 on invalid index, 1 if the index is allocated, 0 if it 79 * is free 80 */ 81 int ba_inuse(struct bitalloc *pool, int index); 82 83 /** 84 * Variant of ba_inuse that frees the index if it is allocated, same 85 * return codes as ba_inuse 86 */ 87 int ba_inuse_free(struct bitalloc *pool, int index); 88 89 /** 90 * Find next index that is in use, start checking at index 'idx' 91 * 92 * Returns next index that is in use on success, or 93 * -1 if no in use index is found 94 */ 95 int ba_find_next_inuse(struct bitalloc *pool, int idx); 96 97 /** 98 * Variant of ba_find_next_inuse that also frees the next in use index, 99 * same return codes as ba_find_next_inuse 100 */ 101 int ba_find_next_inuse_free(struct bitalloc *pool, int idx); 102 103 /** 104 * Multiple freeing of the same index has no negative side effects, 105 * but will return -1. returns -1 on failure, 0 on success. 106 */ 107 int ba_free(struct bitalloc *pool, int index); 108 109 /** 110 * Returns the pool's free count 111 */ 112 int ba_free_count(struct bitalloc *pool); 113 114 /** 115 * Returns the pool's in use count 116 */ 117 int ba_inuse_count(struct bitalloc *pool); 118 119 #endif /* _BITALLOC_H_ */ 120