| 1 | |
| 2 | |
| 3 | * Copyright (c) 2025-2026 Meta Platforms, Inc. and affiliates.
|
| 4 | * Copyright (c) 2025-2026 Emil Tsalapatis <[email protected]>
|
| 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 |
|
| 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 | }
|