1/* ----------------------------------------------------------------------------
2Copyright (c) 2019-2021 Microsoft Research, Daan Leijen
3This is free software; you can redistribute it and/or modify it under the
4terms 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/* ----------------------------------------------------------------------------
9Concurrent bitmap that can set/reset sequences of bits atomically,
10represeted as an array of fields where each field is a machine word (`size_t`)
11
12There are two api's; the standard one cannot have sequences that cross
13between the bitmap fields (and a sequence must be <= MI_BITMAP_FIELD_BITS).
14(this is used in region allocation)
15
16The `_across` postfixed functions do allow sequences that can cross over
17between 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.
29static 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.
44inline 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.
100bool _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
112bool _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.
133bool _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.
140bool _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.
153bool _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.
165static 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
175bool _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
179bool _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.
193static 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
254rollback:
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.
281bool _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
302static 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.
328bool _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.
351bool _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.
380static 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
406bool _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
410bool _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