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 bool bmp_test_and_clear_bit(u32 bit, struct arena_bitmap __arena *bmp) 39 { 40 u64 val = BIT_MASK(bit); 41 u32 idx = BIT_WORD(bit); 42 u64 old, new, actual; 43 44 do { 45 old = bmp->bits[idx]; 46 47 if (!(old & val)) 48 return false; 49 50 new = old & ~val; 51 actual = cmpxchg(&bmp->bits[idx], old, new); 52 53 if (actual == old) 54 return true; 55 56 } while (can_loop); 57 58 return false; 59 } 60 61 __weak 62 bool bmp_test_and_set_bit(u32 bit, struct arena_bitmap __arena *bmp) 63 { 64 u64 val = BIT_MASK(bit); 65 u32 idx = BIT_WORD(bit); 66 u64 old, new, actual; 67 68 do { 69 old = bmp->bits[idx]; 70 71 if ((old & val)) 72 return true; 73 74 new = old | val; 75 actual = cmpxchg(&bmp->bits[idx], old, new); 76 77 if (actual == old) 78 return false; 79 80 } while (can_loop); 81 82 return false; 83 } 84 85 __weak 86 void bmp_clear_bit(u32 bit, struct arena_bitmap __arena *bmp) 87 { 88 u64 val = BIT_MASK(bit); 89 u32 idx = BIT_WORD(bit); 90 u64 old, new, actual; 91 92 do { 93 old = bmp->bits[idx]; 94 new = old & ~val; 95 actual = cmpxchg(&bmp->bits[idx], old, new); 96 97 } while (actual != old && can_loop); 98 } 99 100 __weak 101 void bmp_set_bit(u32 bit, struct arena_bitmap __arena *bmp) 102 { 103 u64 val = BIT_MASK(bit); 104 u32 idx = BIT_WORD(bit); 105 u64 old, new, actual; 106 107 do { 108 old = bmp->bits[idx]; 109 new = old | val; 110 actual = cmpxchg(&bmp->bits[idx], old, new); 111 112 } while (actual != old && can_loop); 113 } 114 115 __weak 116 void bmp_clear(size_t bits, struct arena_bitmap __arena *bmp) 117 { 118 size_t nwords = BITS_TO_LONG_LONGS(bits); 119 volatile u32 i; 120 121 for (i = zero; i < nwords && can_loop; i++) 122 bmp->bits[i] = 0; 123 } 124 125 static __always_inline u64 bmp_last_word_mask(size_t bits) 126 { 127 u32 rem = bits % BITS_PER_LONG_LONG; 128 129 return rem ? (1ULL << rem) - 1 : ~0ULL; 130 } 131 132 __weak 133 void bmp_and(size_t bits, struct arena_bitmap __arena *dst, struct arena_bitmap __arena *src1, struct arena_bitmap __arena *src2) 134 { 135 size_t nwords = BITS_TO_LONG_LONGS(bits); 136 volatile u32 i; 137 138 for (i = zero; i < nwords && can_loop; i++) 139 dst->bits[i] = src1->bits[i] & src2->bits[i]; 140 141 if (nwords && bits % BITS_PER_LONG_LONG) 142 dst->bits[nwords - 1] &= bmp_last_word_mask(bits); 143 } 144 145 __weak 146 void bmp_or(size_t bits, struct arena_bitmap __arena *dst, struct arena_bitmap __arena *src1, struct arena_bitmap __arena *src2) 147 { 148 size_t nwords = BITS_TO_LONG_LONGS(bits); 149 volatile u32 i; 150 151 for (i = zero; i < nwords && can_loop; i++) 152 dst->bits[i] = src1->bits[i] | src2->bits[i]; 153 154 if (nwords && bits % BITS_PER_LONG_LONG) 155 dst->bits[nwords - 1] &= bmp_last_word_mask(bits); 156 } 157 158 __weak 159 bool bmp_empty(size_t bits, struct arena_bitmap __arena *bmp) 160 { 161 size_t nwords = BITS_TO_LONG_LONGS(bits); 162 volatile u32 i; 163 164 for (i = zero; i < nwords && can_loop; i++) { 165 u64 mask = (i == nwords - 1) ? bmp_last_word_mask(bits) : ~0ULL; 166 167 if (bmp->bits[i] & mask) 168 return false; 169 } 170 171 return true; 172 } 173 174 __weak 175 void bmp_copy(size_t bits, struct arena_bitmap __arena *dst, struct arena_bitmap __arena *src) 176 { 177 size_t nwords = BITS_TO_LONG_LONGS(bits); 178 volatile u32 i; 179 180 for (i = zero; i < nwords && can_loop; i++) 181 dst->bits[i] = src->bits[i]; 182 183 if (nwords && bits % BITS_PER_LONG_LONG) 184 dst->bits[nwords - 1] &= bmp_last_word_mask(bits); 185 } 186 187 __weak 188 bool bmp_subset(size_t bits, struct arena_bitmap __arena *big, struct arena_bitmap __arena *small) 189 { 190 size_t nwords = BITS_TO_LONG_LONGS(bits); 191 volatile u32 i; 192 193 for (i = zero; i < nwords && can_loop; i++) { 194 u64 mask = (i == nwords - 1) ? bmp_last_word_mask(bits) : ~0ULL; 195 196 if (~big->bits[i] & small->bits[i] & mask) 197 return false; 198 } 199 200 return true; 201 } 202 203 __weak 204 bool bmp_intersects(size_t bits, struct arena_bitmap __arena *arg1, struct arena_bitmap __arena *arg2) 205 { 206 size_t nwords = BITS_TO_LONG_LONGS(bits); 207 volatile u32 i; 208 209 for (i = zero; i < nwords && can_loop; i++) { 210 u64 mask = (i == nwords - 1) ? bmp_last_word_mask(bits) : ~0ULL; 211 212 if (arg1->bits[i] & arg2->bits[i] & mask) 213 return true; 214 } 215 216 return false; 217 } 218 219 __weak 220 void bmp_print(size_t bits, struct arena_bitmap __arena *bmp) 221 { 222 size_t nwords = BITS_TO_LONG_LONGS(bits); 223 volatile u32 i; 224 225 for (i = zero; i < nwords && can_loop; i++) 226 arena_stderr("%016llx ", bmp->bits[i]); 227 } 228