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
bmp_alloc(size_t bits)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
bmp_free(struct arena_bitmap __arena * bmp)32 void bmp_free(struct arena_bitmap __arena *bmp)
33 {
34 arena_free(bmp);
35 }
36
37 __weak
__bmp_set_bit(u32 bit,struct arena_bitmap __arena * bmp)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
__bmp_clear_bit(u32 bit,struct arena_bitmap __arena * bmp)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
bmp_test_bit(u32 bit,struct arena_bitmap __arena * bmp)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
bmp_test_and_clear_bit(u32 bit,struct arena_bitmap __arena * bmp)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
bmp_test_and_set_bit(u32 bit,struct arena_bitmap __arena * bmp)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
bmp_clear_bit(u32 bit,struct arena_bitmap __arena * bmp)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
bmp_set_bit(u32 bit,struct arena_bitmap __arena * bmp)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
bmp_clear(size_t bits,struct arena_bitmap __arena * bmp)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
bmp_last_word_mask(size_t bits)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
bmp_and(size_t bits,struct arena_bitmap __arena * dst,struct arena_bitmap __arena * src1,struct arena_bitmap __arena * src2)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
bmp_or(size_t bits,struct arena_bitmap __arena * dst,struct arena_bitmap __arena * src1,struct arena_bitmap __arena * src2)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
bmp_empty(size_t bits,struct arena_bitmap __arena * bmp)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
bmp_copy(size_t bits,struct arena_bitmap __arena * dst,struct arena_bitmap __arena * src)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
bmp_subset(size_t bits,struct arena_bitmap __arena * big,struct arena_bitmap __arena * small)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
bmp_intersects(size_t bits,struct arena_bitmap __arena * arg1,struct arena_bitmap __arena * arg2)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
bmp_print(size_t bits,struct arena_bitmap __arena * bmp)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