1#ifndef JEMALLOC_INTERNAL_FB_H
2#define JEMALLOC_INTERNAL_FB_H
3
4/*
5 * The flat bitmap module. This has a larger API relative to the bitmap module
6 * (supporting things like backwards searches, and searching for both set and
7 * unset bits), at the cost of slower operations for very large bitmaps.
8 *
9 * Initialized flat bitmaps start at all-zeros (all bits unset).
10 */
11
12typedef unsigned long fb_group_t;
13#define FB_GROUP_BITS (ZU(1) << (LG_SIZEOF_LONG + 3))
14#define FB_NGROUPS(nbits) ((nbits) / FB_GROUP_BITS \
15 + ((nbits) % FB_GROUP_BITS == 0 ? 0 : 1))
16
17static inline void
18fb_init(fb_group_t *fb, size_t nbits) {
19 size_t ngroups = FB_NGROUPS(nbits);
20 memset(fb, 0, ngroups * sizeof(fb_group_t));
21}
22
23static inline bool
24fb_empty(fb_group_t *fb, size_t nbits) {
25 size_t ngroups = FB_NGROUPS(nbits);
26 for (size_t i = 0; i < ngroups; i++) {
27 if (fb[i] != 0) {
28 return false;
29 }
30 }
31 return true;
32}
33
34static inline bool
35fb_full(fb_group_t *fb, size_t nbits) {
36 size_t ngroups = FB_NGROUPS(nbits);
37 size_t trailing_bits = nbits % FB_GROUP_BITS;
38 size_t limit = (trailing_bits == 0 ? ngroups : ngroups - 1);
39 for (size_t i = 0; i < limit; i++) {
40 if (fb[i] != ~(fb_group_t)0) {
41 return false;
42 }
43 }
44 if (trailing_bits == 0) {
45 return true;
46 }
47 return fb[ngroups - 1] == ((fb_group_t)1 << trailing_bits) - 1;
48}
49
50static inline bool
51fb_get(fb_group_t *fb, size_t nbits, size_t bit) {
52 assert(bit < nbits);
53 size_t group_ind = bit / FB_GROUP_BITS;
54 size_t bit_ind = bit % FB_GROUP_BITS;
55 return (bool)(fb[group_ind] & ((fb_group_t)1 << bit_ind));
56}
57
58static inline void
59fb_set(fb_group_t *fb, size_t nbits, size_t bit) {
60 assert(bit < nbits);
61 size_t group_ind = bit / FB_GROUP_BITS;
62 size_t bit_ind = bit % FB_GROUP_BITS;
63 fb[group_ind] |= ((fb_group_t)1 << bit_ind);
64}
65
66static inline void
67fb_unset(fb_group_t *fb, size_t nbits, size_t bit) {
68 assert(bit < nbits);
69 size_t group_ind = bit / FB_GROUP_BITS;
70 size_t bit_ind = bit % FB_GROUP_BITS;
71 fb[group_ind] &= ~((fb_group_t)1 << bit_ind);
72}
73
74
75/*
76 * Some implementation details. This visitation function lets us apply a group
77 * visitor to each group in the bitmap (potentially modifying it). The mask
78 * indicates which bits are logically part of the visitation.
79 */
80typedef void (*fb_group_visitor_t)(void *ctx, fb_group_t *fb, fb_group_t mask);
81JEMALLOC_ALWAYS_INLINE void
82fb_visit_impl(fb_group_t *fb, size_t nbits, fb_group_visitor_t visit, void *ctx,
83 size_t start, size_t cnt) {
84 assert(cnt > 0);
85 assert(start + cnt <= nbits);
86 size_t group_ind = start / FB_GROUP_BITS;
87 size_t start_bit_ind = start % FB_GROUP_BITS;
88 /*
89 * The first group is special; it's the only one we don't start writing
90 * to from bit 0.
91 */
92 size_t first_group_cnt = (start_bit_ind + cnt > FB_GROUP_BITS
93 ? FB_GROUP_BITS - start_bit_ind : cnt);
94 /*
95 * We can basically split affected words into:
96 * - The first group, where we touch only the high bits
97 * - The last group, where we touch only the low bits
98 * - The middle, where we set all the bits to the same thing.
99 * We treat each case individually. The last two could be merged, but
100 * this can lead to bad codegen for those middle words.
101 */
102 /* First group */
103 fb_group_t mask = ((~(fb_group_t)0)
104 >> (FB_GROUP_BITS - first_group_cnt))
105 << start_bit_ind;
106 visit(ctx, &fb[group_ind], mask);
107
108 cnt -= first_group_cnt;
109 group_ind++;
110 /* Middle groups */
111 while (cnt > FB_GROUP_BITS) {
112 visit(ctx, &fb[group_ind], ~(fb_group_t)0);
113 cnt -= FB_GROUP_BITS;
114 group_ind++;
115 }
116 /* Last group */
117 if (cnt != 0) {
118 mask = (~(fb_group_t)0) >> (FB_GROUP_BITS - cnt);
119 visit(ctx, &fb[group_ind], mask);
120 }
121}
122
123JEMALLOC_ALWAYS_INLINE void
124fb_assign_visitor(void *ctx, fb_group_t *fb, fb_group_t mask) {
125 bool val = *(bool *)ctx;
126 if (val) {
127 *fb |= mask;
128 } else {
129 *fb &= ~mask;
130 }
131}
132
133/* Sets the cnt bits starting at position start. Must not have a 0 count. */
134static inline void
135fb_set_range(fb_group_t *fb, size_t nbits, size_t start, size_t cnt) {
136 bool val = true;
137 fb_visit_impl(fb, nbits, &fb_assign_visitor, &val, start, cnt);
138}
139
140/* Unsets the cnt bits starting at position start. Must not have a 0 count. */
141static inline void
142fb_unset_range(fb_group_t *fb, size_t nbits, size_t start, size_t cnt) {
143 bool val = false;
144 fb_visit_impl(fb, nbits, &fb_assign_visitor, &val, start, cnt);
145}
146
147JEMALLOC_ALWAYS_INLINE void
148fb_scount_visitor(void *ctx, fb_group_t *fb, fb_group_t mask) {
149 size_t *scount = (size_t *)ctx;
150 *scount += popcount_lu(*fb & mask);
151}
152
153/* Finds the number of set bit in the of length cnt starting at start. */
154JEMALLOC_ALWAYS_INLINE size_t
155fb_scount(fb_group_t *fb, size_t nbits, size_t start, size_t cnt) {
156 size_t scount = 0;
157 fb_visit_impl(fb, nbits, &fb_scount_visitor, &scount, start, cnt);
158 return scount;
159}
160
161/* Finds the number of unset bit in the of length cnt starting at start. */
162JEMALLOC_ALWAYS_INLINE size_t
163fb_ucount(fb_group_t *fb, size_t nbits, size_t start, size_t cnt) {
164 size_t scount = fb_scount(fb, nbits, start, cnt);
165 return cnt - scount;
166}
167
168/*
169 * An implementation detail; find the first bit at position >= min_bit with the
170 * value val.
171 *
172 * Returns the number of bits in the bitmap if no such bit exists.
173 */
174JEMALLOC_ALWAYS_INLINE ssize_t
175fb_find_impl(fb_group_t *fb, size_t nbits, size_t start, bool val,
176 bool forward) {
177 assert(start < nbits);
178 size_t ngroups = FB_NGROUPS(nbits);
179 ssize_t group_ind = start / FB_GROUP_BITS;
180 size_t bit_ind = start % FB_GROUP_BITS;
181
182 fb_group_t maybe_invert = (val ? 0 : (fb_group_t)-1);
183
184 fb_group_t group = fb[group_ind];
185 group ^= maybe_invert;
186 if (forward) {
187 /* Only keep ones in bits bit_ind and above. */
188 group &= ~((1LU << bit_ind) - 1);
189 } else {
190 /*
191 * Only keep ones in bits bit_ind and below. You might more
192 * naturally express this as (1 << (bit_ind + 1)) - 1, but
193 * that shifts by an invalid amount if bit_ind is one less than
194 * FB_GROUP_BITS.
195 */
196 group &= ((2LU << bit_ind) - 1);
197 }
198 ssize_t group_ind_bound = forward ? (ssize_t)ngroups : -1;
199 while (group == 0) {
200 group_ind += forward ? 1 : -1;
201 if (group_ind == group_ind_bound) {
202 return forward ? (ssize_t)nbits : (ssize_t)-1;
203 }
204 group = fb[group_ind];
205 group ^= maybe_invert;
206 }
207 assert(group != 0);
208 size_t bit = forward ? ffs_lu(group) : fls_lu(group);
209 size_t pos = group_ind * FB_GROUP_BITS + bit;
210 /*
211 * The high bits of a partially filled last group are zeros, so if we're
212 * looking for zeros we don't want to report an invalid result.
213 */
214 if (forward && !val && pos > nbits) {
215 return nbits;
216 }
217 return pos;
218}
219
220/*
221 * Find the first set bit in the bitmap with an index >= min_bit. Returns the
222 * number of bits in the bitmap if no such bit exists.
223 */
224static inline size_t
225fb_ffu(fb_group_t *fb, size_t nbits, size_t min_bit) {
226 return (size_t)fb_find_impl(fb, nbits, min_bit, /* val */ false,
227 /* forward */ true);
228}
229
230/* The same, but looks for an unset bit. */
231static inline size_t
232fb_ffs(fb_group_t *fb, size_t nbits, size_t min_bit) {
233 return (size_t)fb_find_impl(fb, nbits, min_bit, /* val */ true,
234 /* forward */ true);
235}
236
237/*
238 * Find the last set bit in the bitmap with an index <= max_bit. Returns -1 if
239 * no such bit exists.
240 */
241static inline ssize_t
242fb_flu(fb_group_t *fb, size_t nbits, size_t max_bit) {
243 return fb_find_impl(fb, nbits, max_bit, /* val */ false,
244 /* forward */ false);
245}
246
247static inline ssize_t
248fb_fls(fb_group_t *fb, size_t nbits, size_t max_bit) {
249 return fb_find_impl(fb, nbits, max_bit, /* val */ true,
250 /* forward */ false);
251}
252
253/* Returns whether or not we found a range. */
254JEMALLOC_ALWAYS_INLINE bool
255fb_iter_range_impl(fb_group_t *fb, size_t nbits, size_t start, size_t *r_begin,
256 size_t *r_len, bool val, bool forward) {
257 assert(start < nbits);
258 ssize_t next_range_begin = fb_find_impl(fb, nbits, start, val, forward);
259 if ((forward && next_range_begin == (ssize_t)nbits)
260 || (!forward && next_range_begin == (ssize_t)-1)) {
261 return false;
262 }
263 /* Half open range; the set bits are [begin, end). */
264 ssize_t next_range_end = fb_find_impl(fb, nbits, next_range_begin, !val,
265 forward);
266 if (forward) {
267 *r_begin = next_range_begin;
268 *r_len = next_range_end - next_range_begin;
269 } else {
270 *r_begin = next_range_end + 1;
271 *r_len = next_range_begin - next_range_end;
272 }
273 return true;
274}
275
276/*
277 * Used to iterate through ranges of set bits.
278 *
279 * Tries to find the next contiguous sequence of set bits with a first index >=
280 * start. If one exists, puts the earliest bit of the range in *r_begin, its
281 * length in *r_len, and returns true. Otherwise, returns false (without
282 * touching *r_begin or *r_end).
283 */
284static inline bool
285fb_srange_iter(fb_group_t *fb, size_t nbits, size_t start, size_t *r_begin,
286 size_t *r_len) {
287 return fb_iter_range_impl(fb, nbits, start, r_begin, r_len,
288 /* val */ true, /* forward */ true);
289}
290
291/*
292 * The same as fb_srange_iter, but searches backwards from start rather than
293 * forwards. (The position returned is still the earliest bit in the range).
294 */
295static inline bool
296fb_srange_riter(fb_group_t *fb, size_t nbits, size_t start, size_t *r_begin,
297 size_t *r_len) {
298 return fb_iter_range_impl(fb, nbits, start, r_begin, r_len,
299 /* val */ true, /* forward */ false);
300}
301
302/* Similar to fb_srange_iter, but searches for unset bits. */
303static inline bool
304fb_urange_iter(fb_group_t *fb, size_t nbits, size_t start, size_t *r_begin,
305 size_t *r_len) {
306 return fb_iter_range_impl(fb, nbits, start, r_begin, r_len,
307 /* val */ false, /* forward */ true);
308}
309
310/* Similar to fb_srange_riter, but searches for unset bits. */
311static inline bool
312fb_urange_riter(fb_group_t *fb, size_t nbits, size_t start, size_t *r_begin,
313 size_t *r_len) {
314 return fb_iter_range_impl(fb, nbits, start, r_begin, r_len,
315 /* val */ false, /* forward */ false);
316}
317
318JEMALLOC_ALWAYS_INLINE size_t
319fb_range_longest_impl(fb_group_t *fb, size_t nbits, bool val) {
320 size_t begin = 0;
321 size_t longest_len = 0;
322 size_t len = 0;
323 while (begin < nbits && fb_iter_range_impl(fb, nbits, begin, &begin,
324 &len, val, /* forward */ true)) {
325 if (len > longest_len) {
326 longest_len = len;
327 }
328 begin += len;
329 }
330 return longest_len;
331}
332
333static inline size_t
334fb_srange_longest(fb_group_t *fb, size_t nbits) {
335 return fb_range_longest_impl(fb, nbits, /* val */ true);
336}
337
338static inline size_t
339fb_urange_longest(fb_group_t *fb, size_t nbits) {
340 return fb_range_longest_impl(fb, nbits, /* val */ false);
341}
342
343/*
344 * Initializes each bit of dst with the bitwise-AND of the corresponding bits of
345 * src1 and src2. All bitmaps must be the same size.
346 */
347static inline void
348fb_bit_and(fb_group_t *dst, fb_group_t *src1, fb_group_t *src2, size_t nbits) {
349 size_t ngroups = FB_NGROUPS(nbits);
350 for (size_t i = 0; i < ngroups; i++) {
351 dst[i] = src1[i] & src2[i];
352 }
353}
354
355/* Like fb_bit_and, but with bitwise-OR. */
356static inline void
357fb_bit_or(fb_group_t *dst, fb_group_t *src1, fb_group_t *src2, size_t nbits) {
358 size_t ngroups = FB_NGROUPS(nbits);
359 for (size_t i = 0; i < ngroups; i++) {
360 dst[i] = src1[i] | src2[i];
361 }
362}
363
364/* Initializes dst bit i to the negation of source bit i. */
365static inline void
366fb_bit_not(fb_group_t *dst, fb_group_t *src, size_t nbits) {
367 size_t ngroups = FB_NGROUPS(nbits);
368 for (size_t i = 0; i < ngroups; i++) {
369 dst[i] = ~src[i];
370 }
371}
372
373#endif /* JEMALLOC_INTERNAL_FB_H */
374