1 // SPDX-License-Identifier: LGPL-2.1 OR BSD-2-Clause 2 /* 3 * Copyright (c) 2025-2026 Meta Platforms, Inc. and affiliates. 4 * Copyright (c) 2025-2026 Emil Tsalapatis <emil@etsalapatis.com> 5 */ 6 7 #include <libarena/common.h> 8 9 #include <libarena/asan.h> 10 #include <libarena/bitmap.h> 11 12 __weak 13 struct arena_bitmap __arena *bmp_alloc(size_t bits) 14 { 15 struct arena_bitmap __arena *bmp; 16 size_t size = BITS_TO_LONG_LONGS(bits) * sizeof(bmp->bits[0]); 17 18 /* Assume long-aligned masks. */ 19 if (bits % BITS_PER_LONG_LONG) 20 return NULL; 21 22 bmp = (struct arena_bitmap __arena *)arena_malloc(size); 23 if (!bmp) 24 return NULL; 25 26 bmp_clear(bits, bmp); 27 28 return bmp; 29 } 30 31 __weak 32 void bmp_free(struct arena_bitmap __arena *bmp) 33 { 34 arena_free(bmp); 35 } 36 37 __weak 38 void __bmp_set_bit(u32 bit, struct arena_bitmap __arena *bmp) 39 { 40 bmp->bits[BIT_WORD(bit)] |= BIT_MASK(bit); 41 } 42 43 __weak 44 void __bmp_clear_bit(u32 bit, struct arena_bitmap __arena *bmp) 45 { 46 bmp->bits[BIT_WORD(bit)] &= ~BIT_MASK(bit); 47 } 48 49 __weak 50 bool bmp_test_bit(u32 bit, struct arena_bitmap __arena *bmp) 51 { 52 return bmp->bits[BIT_WORD(bit)] & BIT_MASK(bit); 53 } 54 55 __weak 56 bool bmp_test_and_clear_bit(u32 bit, struct arena_bitmap __arena *bmp) 57 { 58 u64 val = BIT_MASK(bit); 59 u32 idx = BIT_WORD(bit); 60 u64 old, new, actual; 61 62 do { 63 old = bmp->bits[idx]; 64 65 if (!(old & val)) 66 return false; 67 68 new = old & ~val; 69 actual = cmpxchg(&bmp->bits[idx], old, new); 70 71 if (actual == old) 72 return true; 73 74 } while (can_loop); 75 76 return false; 77 } 78 79 __weak 80 bool bmp_test_and_set_bit(u32 bit, struct arena_bitmap __arena *bmp) 81 { 82 u64 val = BIT_MASK(bit); 83 u32 idx = BIT_WORD(bit); 84 u64 old, new, actual; 85 86 do { 87 old = bmp->bits[idx]; 88 89 if ((old & val)) 90 return true; 91 92 new = old | val; 93 actual = cmpxchg(&bmp->bits[idx], old, new); 94 95 if (actual == old) 96 return false; 97 98 } while (can_loop); 99 100 return false; 101 } 102 103 __weak 104 void bmp_clear_bit(u32 bit, struct arena_bitmap __arena *bmp) 105 { 106 u64 val = BIT_MASK(bit); 107 u32 idx = BIT_WORD(bit); 108 u64 old, new, actual; 109 110 do { 111 old = bmp->bits[idx]; 112 new = old & ~val; 113 actual = cmpxchg(&bmp->bits[idx], old, new); 114 115 } while (actual != old && can_loop); 116 } 117 118 __weak 119 void bmp_set_bit(u32 bit, struct arena_bitmap __arena *bmp) 120 { 121 u64 val = BIT_MASK(bit); 122 u32 idx = BIT_WORD(bit); 123 u64 old, new, actual; 124 125 do { 126 old = bmp->bits[idx]; 127 new = old | val; 128 actual = cmpxchg(&bmp->bits[idx], old, new); 129 130 } while (actual != old && can_loop); 131 } 132 133 __weak 134 void bmp_clear(size_t bits, struct arena_bitmap __arena *bmp) 135 { 136 size_t nwords = BITS_TO_LONG_LONGS(bits); 137 volatile u32 i; 138 139 for (i = zero; i < nwords && can_loop; i++) 140 bmp->bits[i] = 0; 141 } 142 143 static __always_inline u64 bmp_last_word_mask(size_t bits) 144 { 145 u32 rem = bits % BITS_PER_LONG_LONG; 146 147 return rem ? (1ULL << rem) - 1 : ~0ULL; 148 } 149 150 __weak 151 void bmp_and(size_t bits, struct arena_bitmap __arena *dst, struct arena_bitmap __arena *src1, struct arena_bitmap __arena *src2) 152 { 153 size_t nwords = BITS_TO_LONG_LONGS(bits); 154 volatile u32 i; 155 156 for (i = zero; i < nwords && can_loop; i++) 157 dst->bits[i] = src1->bits[i] & src2->bits[i]; 158 159 if (nwords && bits % BITS_PER_LONG_LONG) 160 dst->bits[nwords - 1] &= bmp_last_word_mask(bits); 161 } 162 163 __weak 164 void bmp_or(size_t bits, struct arena_bitmap __arena *dst, struct arena_bitmap __arena *src1, struct arena_bitmap __arena *src2) 165 { 166 size_t nwords = BITS_TO_LONG_LONGS(bits); 167 volatile u32 i; 168 169 for (i = zero; i < nwords && can_loop; i++) 170 dst->bits[i] = src1->bits[i] | src2->bits[i]; 171 172 if (nwords && bits % BITS_PER_LONG_LONG) 173 dst->bits[nwords - 1] &= bmp_last_word_mask(bits); 174 } 175 176 __weak 177 bool bmp_empty(size_t bits, struct arena_bitmap __arena *bmp) 178 { 179 size_t nwords = BITS_TO_LONG_LONGS(bits); 180 volatile u32 i; 181 182 for (i = zero; i < nwords && can_loop; i++) { 183 u64 mask = (i == nwords - 1) ? bmp_last_word_mask(bits) : ~0ULL; 184 185 if (bmp->bits[i] & mask) 186 return false; 187 } 188 189 return true; 190 } 191 192 __weak 193 void bmp_copy(size_t bits, struct arena_bitmap __arena *dst, struct arena_bitmap __arena *src) 194 { 195 size_t nwords = BITS_TO_LONG_LONGS(bits); 196 volatile u32 i; 197 198 for (i = zero; i < nwords && can_loop; i++) 199 dst->bits[i] = src->bits[i]; 200 201 if (nwords && bits % BITS_PER_LONG_LONG) 202 dst->bits[nwords - 1] &= bmp_last_word_mask(bits); 203 } 204 205 __weak 206 bool bmp_subset(size_t bits, struct arena_bitmap __arena *big, struct arena_bitmap __arena *small) 207 { 208 size_t nwords = BITS_TO_LONG_LONGS(bits); 209 volatile u32 i; 210 211 for (i = zero; i < nwords && can_loop; i++) { 212 u64 mask = (i == nwords - 1) ? bmp_last_word_mask(bits) : ~0ULL; 213 214 if (~big->bits[i] & small->bits[i] & mask) 215 return false; 216 } 217 218 return true; 219 } 220 221 __weak 222 bool bmp_intersects(size_t bits, struct arena_bitmap __arena *arg1, struct arena_bitmap __arena *arg2) 223 { 224 size_t nwords = BITS_TO_LONG_LONGS(bits); 225 volatile u32 i; 226 227 for (i = zero; i < nwords && can_loop; i++) { 228 u64 mask = (i == nwords - 1) ? bmp_last_word_mask(bits) : ~0ULL; 229 230 if (arg1->bits[i] & arg2->bits[i] & mask) 231 return true; 232 } 233 234 return false; 235 } 236 237 __weak 238 void bmp_print(size_t bits, struct arena_bitmap __arena *bmp) 239 { 240 size_t nwords = BITS_TO_LONG_LONGS(bits); 241 volatile u32 i; 242 243 for (i = zero; i < nwords && can_loop; i++) 244 arena_stderr("%016llx ", bmp->bits[i]); 245 } 246