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 | |
12 | typedef 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 | |
17 | static inline void |
18 | fb_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 | |
23 | static inline bool |
24 | fb_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 | |
34 | static inline bool |
35 | fb_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 | |
50 | static inline bool |
51 | fb_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 | |
58 | static inline void |
59 | fb_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 | |
66 | static inline void |
67 | fb_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 | */ |
80 | typedef void (*fb_group_visitor_t)(void *ctx, fb_group_t *fb, fb_group_t mask); |
81 | JEMALLOC_ALWAYS_INLINE void |
82 | fb_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 | |
123 | JEMALLOC_ALWAYS_INLINE void |
124 | fb_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. */ |
134 | static inline void |
135 | fb_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. */ |
141 | static inline void |
142 | fb_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 | |
147 | JEMALLOC_ALWAYS_INLINE void |
148 | fb_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. */ |
154 | JEMALLOC_ALWAYS_INLINE size_t |
155 | fb_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. */ |
162 | JEMALLOC_ALWAYS_INLINE size_t |
163 | fb_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 | */ |
174 | JEMALLOC_ALWAYS_INLINE ssize_t |
175 | fb_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 | */ |
224 | static inline size_t |
225 | fb_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. */ |
231 | static inline size_t |
232 | fb_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 | */ |
241 | static inline ssize_t |
242 | fb_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 | |
247 | static inline ssize_t |
248 | fb_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. */ |
254 | JEMALLOC_ALWAYS_INLINE bool |
255 | fb_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 | */ |
284 | static inline bool |
285 | fb_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 | */ |
295 | static inline bool |
296 | fb_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. */ |
303 | static inline bool |
304 | fb_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. */ |
311 | static inline bool |
312 | fb_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 | |
318 | JEMALLOC_ALWAYS_INLINE size_t |
319 | fb_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 | |
333 | static inline size_t |
334 | fb_srange_longest(fb_group_t *fb, size_t nbits) { |
335 | return fb_range_longest_impl(fb, nbits, /* val */ true); |
336 | } |
337 | |
338 | static inline size_t |
339 | fb_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 | */ |
347 | static inline void |
348 | fb_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. */ |
356 | static inline void |
357 | fb_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. */ |
365 | static inline void |
366 | fb_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 | |