1 | /* ---------------------------------------------------------------------------- |
2 | Copyright (c) 2019-2021 Microsoft Research, Daan Leijen |
3 | This is free software; you can redistribute it and/or modify it under the |
4 | terms of the MIT license. A copy of the license can be found in the file |
5 | "LICENSE" at the root of this distribution. |
6 | -----------------------------------------------------------------------------*/ |
7 | |
8 | /* ---------------------------------------------------------------------------- |
9 | Concurrent bitmap that can set/reset sequences of bits atomically, |
10 | represeted as an array of fields where each field is a machine word (`size_t`) |
11 | |
12 | There are two api's; the standard one cannot have sequences that cross |
13 | between the bitmap fields (and a sequence must be <= MI_BITMAP_FIELD_BITS). |
14 | (this is used in region allocation) |
15 | |
16 | The `_across` postfixed functions do allow sequences that can cross over |
17 | between the fields. (This is used in arena allocation) |
18 | ---------------------------------------------------------------------------- */ |
19 | |
20 | #include "mimalloc.h" |
21 | #include "mimalloc-internal.h" |
22 | #include "bitmap.h" |
23 | |
24 | /* ----------------------------------------------------------- |
25 | Bitmap definition |
26 | ----------------------------------------------------------- */ |
27 | |
28 | // The bit mask for a given number of blocks at a specified bit index. |
29 | static inline size_t mi_bitmap_mask_(size_t count, size_t bitidx) { |
30 | mi_assert_internal(count + bitidx <= MI_BITMAP_FIELD_BITS); |
31 | mi_assert_internal(count > 0); |
32 | if (count >= MI_BITMAP_FIELD_BITS) return MI_BITMAP_FIELD_FULL; |
33 | if (count == 0) return 0; |
34 | return ((((size_t)1 << count) - 1) << bitidx); |
35 | } |
36 | |
37 | |
38 | /* ----------------------------------------------------------- |
39 | Claim a bit sequence atomically |
40 | ----------------------------------------------------------- */ |
41 | |
42 | // Try to atomically claim a sequence of `count` bits in a single |
43 | // field at `idx` in `bitmap`. Returns `true` on success. |
44 | inline bool _mi_bitmap_try_find_claim_field(mi_bitmap_t bitmap, size_t idx, const size_t count, mi_bitmap_index_t* bitmap_idx) |
45 | { |
46 | mi_assert_internal(bitmap_idx != NULL); |
47 | mi_assert_internal(count <= MI_BITMAP_FIELD_BITS); |
48 | mi_assert_internal(count > 0); |
49 | mi_bitmap_field_t* field = &bitmap[idx]; |
50 | size_t map = mi_atomic_load_relaxed(field); |
51 | if (map==MI_BITMAP_FIELD_FULL) return false; // short cut |
52 | |
53 | // search for 0-bit sequence of length count |
54 | const size_t mask = mi_bitmap_mask_(count, 0); |
55 | const size_t bitidx_max = MI_BITMAP_FIELD_BITS - count; |
56 | |
57 | #ifdef MI_HAVE_FAST_BITSCAN |
58 | size_t bitidx = mi_ctz(~map); // quickly find the first zero bit if possible |
59 | #else |
60 | size_t bitidx = 0; // otherwise start at 0 |
61 | #endif |
62 | size_t m = (mask << bitidx); // invariant: m == mask shifted by bitidx |
63 | |
64 | // scan linearly for a free range of zero bits |
65 | while (bitidx <= bitidx_max) { |
66 | const size_t mapm = map & m; |
67 | if (mapm == 0) { // are the mask bits free at bitidx? |
68 | mi_assert_internal((m >> bitidx) == mask); // no overflow? |
69 | const size_t newmap = map | m; |
70 | mi_assert_internal((newmap^map) >> bitidx == mask); |
71 | if (!mi_atomic_cas_weak_acq_rel(field, &map, newmap)) { // TODO: use strong cas here? |
72 | // no success, another thread claimed concurrently.. keep going (with updated `map`) |
73 | continue; |
74 | } |
75 | else { |
76 | // success, we claimed the bits! |
77 | *bitmap_idx = mi_bitmap_index_create(idx, bitidx); |
78 | return true; |
79 | } |
80 | } |
81 | else { |
82 | // on to the next bit range |
83 | #ifdef MI_HAVE_FAST_BITSCAN |
84 | const size_t shift = (count == 1 ? 1 : mi_bsr(mapm) - bitidx + 1); |
85 | mi_assert_internal(shift > 0 && shift <= count); |
86 | #else |
87 | const size_t shift = 1; |
88 | #endif |
89 | bitidx += shift; |
90 | m <<= shift; |
91 | } |
92 | } |
93 | // no bits found |
94 | return false; |
95 | } |
96 | |
97 | // Find `count` bits of 0 and set them to 1 atomically; returns `true` on success. |
98 | // Starts at idx, and wraps around to search in all `bitmap_fields` fields. |
99 | // `count` can be at most MI_BITMAP_FIELD_BITS and will never cross fields. |
100 | bool _mi_bitmap_try_find_from_claim(mi_bitmap_t bitmap, const size_t bitmap_fields, const size_t start_field_idx, const size_t count, mi_bitmap_index_t* bitmap_idx) { |
101 | size_t idx = start_field_idx; |
102 | for (size_t visited = 0; visited < bitmap_fields; visited++, idx++) { |
103 | if (idx >= bitmap_fields) idx = 0; // wrap |
104 | if (_mi_bitmap_try_find_claim_field(bitmap, idx, count, bitmap_idx)) { |
105 | return true; |
106 | } |
107 | } |
108 | return false; |
109 | } |
110 | |
111 | // Like _mi_bitmap_try_find_from_claim but with an extra predicate that must be fullfilled |
112 | bool _mi_bitmap_try_find_from_claim_pred(mi_bitmap_t bitmap, const size_t bitmap_fields, |
113 | const size_t start_field_idx, const size_t count, |
114 | mi_bitmap_pred_fun_t pred_fun, void* pred_arg, |
115 | mi_bitmap_index_t* bitmap_idx) { |
116 | size_t idx = start_field_idx; |
117 | for (size_t visited = 0; visited < bitmap_fields; visited++, idx++) { |
118 | if (idx >= bitmap_fields) idx = 0; // wrap |
119 | if (_mi_bitmap_try_find_claim_field(bitmap, idx, count, bitmap_idx)) { |
120 | if (pred_fun == NULL || pred_fun(*bitmap_idx, pred_arg)) { |
121 | return true; |
122 | } |
123 | // predicate returned false, unclaim and look further |
124 | _mi_bitmap_unclaim(bitmap, bitmap_fields, count, *bitmap_idx); |
125 | } |
126 | } |
127 | return false; |
128 | } |
129 | |
130 | /* |
131 | // Find `count` bits of 0 and set them to 1 atomically; returns `true` on success. |
132 | // For now, `count` can be at most MI_BITMAP_FIELD_BITS and will never span fields. |
133 | bool _mi_bitmap_try_find_claim(mi_bitmap_t bitmap, const size_t bitmap_fields, const size_t count, mi_bitmap_index_t* bitmap_idx) { |
134 | return _mi_bitmap_try_find_from_claim(bitmap, bitmap_fields, 0, count, bitmap_idx); |
135 | } |
136 | */ |
137 | |
138 | // Set `count` bits at `bitmap_idx` to 0 atomically |
139 | // Returns `true` if all `count` bits were 1 previously. |
140 | bool _mi_bitmap_unclaim(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx) { |
141 | const size_t idx = mi_bitmap_index_field(bitmap_idx); |
142 | const size_t bitidx = mi_bitmap_index_bit_in_field(bitmap_idx); |
143 | const size_t mask = mi_bitmap_mask_(count, bitidx); |
144 | mi_assert_internal(bitmap_fields > idx); MI_UNUSED(bitmap_fields); |
145 | // mi_assert_internal((bitmap[idx] & mask) == mask); |
146 | size_t prev = mi_atomic_and_acq_rel(&bitmap[idx], ~mask); |
147 | return ((prev & mask) == mask); |
148 | } |
149 | |
150 | |
151 | // Set `count` bits at `bitmap_idx` to 1 atomically |
152 | // Returns `true` if all `count` bits were 0 previously. `any_zero` is `true` if there was at least one zero bit. |
153 | bool _mi_bitmap_claim(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx, bool* any_zero) { |
154 | const size_t idx = mi_bitmap_index_field(bitmap_idx); |
155 | const size_t bitidx = mi_bitmap_index_bit_in_field(bitmap_idx); |
156 | const size_t mask = mi_bitmap_mask_(count, bitidx); |
157 | mi_assert_internal(bitmap_fields > idx); MI_UNUSED(bitmap_fields); |
158 | //mi_assert_internal(any_zero != NULL || (bitmap[idx] & mask) == 0); |
159 | size_t prev = mi_atomic_or_acq_rel(&bitmap[idx], mask); |
160 | if (any_zero != NULL) *any_zero = ((prev & mask) != mask); |
161 | return ((prev & mask) == 0); |
162 | } |
163 | |
164 | // Returns `true` if all `count` bits were 1. `any_ones` is `true` if there was at least one bit set to one. |
165 | static bool mi_bitmap_is_claimedx(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx, bool* any_ones) { |
166 | const size_t idx = mi_bitmap_index_field(bitmap_idx); |
167 | const size_t bitidx = mi_bitmap_index_bit_in_field(bitmap_idx); |
168 | const size_t mask = mi_bitmap_mask_(count, bitidx); |
169 | mi_assert_internal(bitmap_fields > idx); MI_UNUSED(bitmap_fields); |
170 | size_t field = mi_atomic_load_relaxed(&bitmap[idx]); |
171 | if (any_ones != NULL) *any_ones = ((field & mask) != 0); |
172 | return ((field & mask) == mask); |
173 | } |
174 | |
175 | bool _mi_bitmap_is_claimed(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx) { |
176 | return mi_bitmap_is_claimedx(bitmap, bitmap_fields, count, bitmap_idx, NULL); |
177 | } |
178 | |
179 | bool _mi_bitmap_is_any_claimed(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx) { |
180 | bool any_ones; |
181 | mi_bitmap_is_claimedx(bitmap, bitmap_fields, count, bitmap_idx, &any_ones); |
182 | return any_ones; |
183 | } |
184 | |
185 | |
186 | //-------------------------------------------------------------------------- |
187 | // the `_across` functions work on bitmaps where sequences can cross over |
188 | // between the fields. This is used in arena allocation |
189 | //-------------------------------------------------------------------------- |
190 | |
191 | // Try to atomically claim a sequence of `count` bits starting from the field |
192 | // at `idx` in `bitmap` and crossing into subsequent fields. Returns `true` on success. |
193 | static bool mi_bitmap_try_find_claim_field_across(mi_bitmap_t bitmap, size_t bitmap_fields, size_t idx, const size_t count, const size_t retries, mi_bitmap_index_t* bitmap_idx) |
194 | { |
195 | mi_assert_internal(bitmap_idx != NULL); |
196 | |
197 | // check initial trailing zeros |
198 | mi_bitmap_field_t* field = &bitmap[idx]; |
199 | size_t map = mi_atomic_load_relaxed(field); |
200 | const size_t initial = mi_clz(map); // count of initial zeros starting at idx |
201 | mi_assert_internal(initial <= MI_BITMAP_FIELD_BITS); |
202 | if (initial == 0) return false; |
203 | if (initial >= count) return _mi_bitmap_try_find_claim_field(bitmap, idx, count, bitmap_idx); // no need to cross fields |
204 | if (_mi_divide_up(count - initial, MI_BITMAP_FIELD_BITS) >= (bitmap_fields - idx)) return false; // not enough entries |
205 | |
206 | // scan ahead |
207 | size_t found = initial; |
208 | size_t mask = 0; // mask bits for the final field |
209 | while(found < count) { |
210 | field++; |
211 | map = mi_atomic_load_relaxed(field); |
212 | const size_t mask_bits = (found + MI_BITMAP_FIELD_BITS <= count ? MI_BITMAP_FIELD_BITS : (count - found)); |
213 | mask = mi_bitmap_mask_(mask_bits, 0); |
214 | if ((map & mask) != 0) return false; |
215 | found += mask_bits; |
216 | } |
217 | mi_assert_internal(field < &bitmap[bitmap_fields]); |
218 | |
219 | // found range of zeros up to the final field; mask contains mask in the final field |
220 | // now claim it atomically |
221 | mi_bitmap_field_t* const final_field = field; |
222 | const size_t final_mask = mask; |
223 | mi_bitmap_field_t* const initial_field = &bitmap[idx]; |
224 | const size_t initial_mask = mi_bitmap_mask_(initial, MI_BITMAP_FIELD_BITS - initial); |
225 | |
226 | // initial field |
227 | size_t newmap; |
228 | field = initial_field; |
229 | map = mi_atomic_load_relaxed(field); |
230 | do { |
231 | newmap = map | initial_mask; |
232 | if ((map & initial_mask) != 0) { goto rollback; }; |
233 | } while (!mi_atomic_cas_strong_acq_rel(field, &map, newmap)); |
234 | |
235 | // intermediate fields |
236 | while (++field < final_field) { |
237 | newmap = MI_BITMAP_FIELD_FULL; |
238 | map = 0; |
239 | if (!mi_atomic_cas_strong_acq_rel(field, &map, newmap)) { goto rollback; } |
240 | } |
241 | |
242 | // final field |
243 | mi_assert_internal(field == final_field); |
244 | map = mi_atomic_load_relaxed(field); |
245 | do { |
246 | newmap = map | final_mask; |
247 | if ((map & final_mask) != 0) { goto rollback; } |
248 | } while (!mi_atomic_cas_strong_acq_rel(field, &map, newmap)); |
249 | |
250 | // claimed! |
251 | *bitmap_idx = mi_bitmap_index_create(idx, MI_BITMAP_FIELD_BITS - initial); |
252 | return true; |
253 | |
254 | rollback: |
255 | // roll back intermediate fields |
256 | while (--field > initial_field) { |
257 | newmap = 0; |
258 | map = MI_BITMAP_FIELD_FULL; |
259 | mi_assert_internal(mi_atomic_load_relaxed(field) == map); |
260 | mi_atomic_store_release(field, newmap); |
261 | } |
262 | if (field == initial_field) { |
263 | map = mi_atomic_load_relaxed(field); |
264 | do { |
265 | mi_assert_internal((map & initial_mask) == initial_mask); |
266 | newmap = map & ~initial_mask; |
267 | } while (!mi_atomic_cas_strong_acq_rel(field, &map, newmap)); |
268 | } |
269 | // retry? (we make a recursive call instead of goto to be able to use const declarations) |
270 | if (retries < 4) { |
271 | return mi_bitmap_try_find_claim_field_across(bitmap, bitmap_fields, idx, count, retries+1, bitmap_idx); |
272 | } |
273 | else { |
274 | return false; |
275 | } |
276 | } |
277 | |
278 | |
279 | // Find `count` bits of zeros and set them to 1 atomically; returns `true` on success. |
280 | // Starts at idx, and wraps around to search in all `bitmap_fields` fields. |
281 | bool _mi_bitmap_try_find_from_claim_across(mi_bitmap_t bitmap, const size_t bitmap_fields, const size_t start_field_idx, const size_t count, mi_bitmap_index_t* bitmap_idx) { |
282 | mi_assert_internal(count > 0); |
283 | if (count==1) return _mi_bitmap_try_find_from_claim(bitmap, bitmap_fields, start_field_idx, count, bitmap_idx); |
284 | size_t idx = start_field_idx; |
285 | for (size_t visited = 0; visited < bitmap_fields; visited++, idx++) { |
286 | if (idx >= bitmap_fields) idx = 0; // wrap |
287 | // try to claim inside the field |
288 | if (count <= MI_BITMAP_FIELD_BITS) { |
289 | if (_mi_bitmap_try_find_claim_field(bitmap, idx, count, bitmap_idx)) { |
290 | return true; |
291 | } |
292 | } |
293 | // try to claim across fields |
294 | if (mi_bitmap_try_find_claim_field_across(bitmap, bitmap_fields, idx, count, 0, bitmap_idx)) { |
295 | return true; |
296 | } |
297 | } |
298 | return false; |
299 | } |
300 | |
301 | // Helper for masks across fields; returns the mid count, post_mask may be 0 |
302 | static size_t mi_bitmap_mask_across(mi_bitmap_index_t bitmap_idx, size_t bitmap_fields, size_t count, size_t* pre_mask, size_t* mid_mask, size_t* post_mask) { |
303 | MI_UNUSED_RELEASE(bitmap_fields); |
304 | const size_t bitidx = mi_bitmap_index_bit_in_field(bitmap_idx); |
305 | if mi_likely(bitidx + count <= MI_BITMAP_FIELD_BITS) { |
306 | *pre_mask = mi_bitmap_mask_(count, bitidx); |
307 | *mid_mask = 0; |
308 | *post_mask = 0; |
309 | mi_assert_internal(mi_bitmap_index_field(bitmap_idx) < bitmap_fields); |
310 | return 0; |
311 | } |
312 | else { |
313 | const size_t pre_bits = MI_BITMAP_FIELD_BITS - bitidx; |
314 | mi_assert_internal(pre_bits < count); |
315 | *pre_mask = mi_bitmap_mask_(pre_bits, bitidx); |
316 | count -= pre_bits; |
317 | const size_t mid_count = (count / MI_BITMAP_FIELD_BITS); |
318 | *mid_mask = MI_BITMAP_FIELD_FULL; |
319 | count %= MI_BITMAP_FIELD_BITS; |
320 | *post_mask = (count==0 ? 0 : mi_bitmap_mask_(count, 0)); |
321 | mi_assert_internal(mi_bitmap_index_field(bitmap_idx) + mid_count + (count==0 ? 0 : 1) < bitmap_fields); |
322 | return mid_count; |
323 | } |
324 | } |
325 | |
326 | // Set `count` bits at `bitmap_idx` to 0 atomically |
327 | // Returns `true` if all `count` bits were 1 previously. |
328 | bool _mi_bitmap_unclaim_across(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx) { |
329 | size_t idx = mi_bitmap_index_field(bitmap_idx); |
330 | size_t pre_mask; |
331 | size_t mid_mask; |
332 | size_t post_mask; |
333 | size_t mid_count = mi_bitmap_mask_across(bitmap_idx, bitmap_fields, count, &pre_mask, &mid_mask, &post_mask); |
334 | bool all_one = true; |
335 | mi_bitmap_field_t* field = &bitmap[idx]; |
336 | size_t prev = mi_atomic_and_acq_rel(field++, ~pre_mask); |
337 | if ((prev & pre_mask) != pre_mask) all_one = false; |
338 | while(mid_count-- > 0) { |
339 | prev = mi_atomic_and_acq_rel(field++, ~mid_mask); |
340 | if ((prev & mid_mask) != mid_mask) all_one = false; |
341 | } |
342 | if (post_mask!=0) { |
343 | prev = mi_atomic_and_acq_rel(field, ~post_mask); |
344 | if ((prev & post_mask) != post_mask) all_one = false; |
345 | } |
346 | return all_one; |
347 | } |
348 | |
349 | // Set `count` bits at `bitmap_idx` to 1 atomically |
350 | // Returns `true` if all `count` bits were 0 previously. `any_zero` is `true` if there was at least one zero bit. |
351 | bool _mi_bitmap_claim_across(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx, bool* pany_zero) { |
352 | size_t idx = mi_bitmap_index_field(bitmap_idx); |
353 | size_t pre_mask; |
354 | size_t mid_mask; |
355 | size_t post_mask; |
356 | size_t mid_count = mi_bitmap_mask_across(bitmap_idx, bitmap_fields, count, &pre_mask, &mid_mask, &post_mask); |
357 | bool all_zero = true; |
358 | bool any_zero = false; |
359 | _Atomic(size_t)*field = &bitmap[idx]; |
360 | size_t prev = mi_atomic_or_acq_rel(field++, pre_mask); |
361 | if ((prev & pre_mask) != 0) all_zero = false; |
362 | if ((prev & pre_mask) != pre_mask) any_zero = true; |
363 | while (mid_count-- > 0) { |
364 | prev = mi_atomic_or_acq_rel(field++, mid_mask); |
365 | if ((prev & mid_mask) != 0) all_zero = false; |
366 | if ((prev & mid_mask) != mid_mask) any_zero = true; |
367 | } |
368 | if (post_mask!=0) { |
369 | prev = mi_atomic_or_acq_rel(field, post_mask); |
370 | if ((prev & post_mask) != 0) all_zero = false; |
371 | if ((prev & post_mask) != post_mask) any_zero = true; |
372 | } |
373 | if (pany_zero != NULL) *pany_zero = any_zero; |
374 | return all_zero; |
375 | } |
376 | |
377 | |
378 | // Returns `true` if all `count` bits were 1. |
379 | // `any_ones` is `true` if there was at least one bit set to one. |
380 | static bool mi_bitmap_is_claimedx_across(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx, bool* pany_ones) { |
381 | size_t idx = mi_bitmap_index_field(bitmap_idx); |
382 | size_t pre_mask; |
383 | size_t mid_mask; |
384 | size_t post_mask; |
385 | size_t mid_count = mi_bitmap_mask_across(bitmap_idx, bitmap_fields, count, &pre_mask, &mid_mask, &post_mask); |
386 | bool all_ones = true; |
387 | bool any_ones = false; |
388 | mi_bitmap_field_t* field = &bitmap[idx]; |
389 | size_t prev = mi_atomic_load_relaxed(field++); |
390 | if ((prev & pre_mask) != pre_mask) all_ones = false; |
391 | if ((prev & pre_mask) != 0) any_ones = true; |
392 | while (mid_count-- > 0) { |
393 | prev = mi_atomic_load_relaxed(field++); |
394 | if ((prev & mid_mask) != mid_mask) all_ones = false; |
395 | if ((prev & mid_mask) != 0) any_ones = true; |
396 | } |
397 | if (post_mask!=0) { |
398 | prev = mi_atomic_load_relaxed(field); |
399 | if ((prev & post_mask) != post_mask) all_ones = false; |
400 | if ((prev & post_mask) != 0) any_ones = true; |
401 | } |
402 | if (pany_ones != NULL) *pany_ones = any_ones; |
403 | return all_ones; |
404 | } |
405 | |
406 | bool _mi_bitmap_is_claimed_across(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx) { |
407 | return mi_bitmap_is_claimedx_across(bitmap, bitmap_fields, count, bitmap_idx, NULL); |
408 | } |
409 | |
410 | bool _mi_bitmap_is_any_claimed_across(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx) { |
411 | bool any_ones; |
412 | mi_bitmap_is_claimedx_across(bitmap, bitmap_fields, count, bitmap_idx, &any_ones); |
413 | return any_ones; |
414 | } |
415 | |