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