projects/linux·blob master · refs

245 lines · 5.0 KiB

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 <[email protected]>
5 */
6
7#include <libarena/common.h>
8
9#include <libarena/asan.h>
10#include <libarena/bitmap.h>
11
12__weak
13struct 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
32void bmp_free(struct arena_bitmap __arena *bmp)
33{
34 arena_free(bmp);
35}
36
37__weak
38void __bmp_set_bit(u32 bit, struct arena_bitmap __arena *bmp)
39{
40 bmp->bits[BIT_WORD(bit)] |= BIT_MASK(bit);
41}
42
43__weak
44void __bmp_clear_bit(u32 bit, struct arena_bitmap __arena *bmp)
45{
46 bmp->bits[BIT_WORD(bit)] &= ~BIT_MASK(bit);
47}
48
49__weak
50bool 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
56bool 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
80bool 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
104void 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
119void 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
134void 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
143static __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
151void 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
164void 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
177bool 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
193void 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
206bool 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
222bool 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
238void 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}