GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

mirrored fromhttps://github.com/microsoft/qdkAvailable

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
73ca361d760b28bb5a9c231f916024b08f884fae

Branches

Tags

  • No tags available.
0Branches0Tags
Go to file
Add file
Code

Clone

HTTPS

Download ZIP

qdk/source/allocator/mimalloc-sys/mimalloc/src

source/allocator/mimalloc-sys/mimalloc/src/bitmap.c

441lines · modecode

RawDownload
Latest commit unavailable.
1/* ----------------------------------------------------------------------------
2Copyright (c) 2019-2023 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,
10represented 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
15The `_across` postfixed functions do allow sequences that can cross over
16between the fields. (This is used in arena allocation)
17---------------------------------------------------------------------------- */
18
19#include "mimalloc.h"
20#include "mimalloc/internal.h"
21#include "bitmap.h"
22
23/* -----------------------------------------------------------
24 Bitmap definition
25----------------------------------------------------------- */
26
27// The bit mask for a given number of blocks at a specified bit index.
28static inline size_t mi_bitmap_mask_(size_t count, size_t bitidx) {
29 mi_assert_internal(count + bitidx <= MI_BITMAP_FIELD_BITS);
30 mi_assert_internal(count > 0);
31 if (count >= MI_BITMAP_FIELD_BITS) return MI_BITMAP_FIELD_FULL;
32 if (count == 0) return 0;
33 return ((((size_t)1 << count) - 1) << bitidx);
34}
35
36
37/* -----------------------------------------------------------
38 Claim a bit sequence atomically
39----------------------------------------------------------- */
40
41// Try to atomically claim a sequence of `count` bits in a single
42// field at `idx` in `bitmap`. Returns `true` on success.
43inline bool _mi_bitmap_try_find_claim_field(mi_bitmap_t bitmap, size_t idx, const size_t count, mi_bitmap_index_t* bitmap_idx)
44{
45 mi_assert_internal(bitmap_idx != NULL);
46 mi_assert_internal(count <= MI_BITMAP_FIELD_BITS);
47 mi_assert_internal(count > 0);
48 mi_bitmap_field_t* field = &bitmap[idx];
49 size_t map = mi_atomic_load_relaxed(field);
50 if (map==MI_BITMAP_FIELD_FULL) return false; // short cut
51
52 // search for 0-bit sequence of length count
53 const size_t mask = mi_bitmap_mask_(count, 0);
54 const size_t bitidx_max = MI_BITMAP_FIELD_BITS - count;
55
56#ifdef MI_HAVE_FAST_BITSCAN
57 size_t bitidx = mi_ctz(~map); // quickly find the first zero bit if possible
58#else
59 size_t bitidx = 0; // otherwise start at 0
60#endif
61 size_t m = (mask << bitidx); // invariant: m == mask shifted by bitidx
62
63 // scan linearly for a free range of zero bits
64 while (bitidx <= bitidx_max) {
65 const size_t mapm = (map & m);
66 if (mapm == 0) { // are the mask bits free at bitidx?
67 mi_assert_internal((m >> bitidx) == mask); // no overflow?
68 const size_t newmap = (map | m);
69 mi_assert_internal((newmap^map) >> bitidx == mask);
70 if (!mi_atomic_cas_strong_acq_rel(field, &map, newmap)) { // TODO: use weak cas here?
71 // no success, another thread claimed concurrently.. keep going (with updated `map`)
72 continue;
73 }
74 else {
75 // success, we claimed the bits!
76 *bitmap_idx = mi_bitmap_index_create(idx, bitidx);
77 return true;
78 }
79 }
80 else {
81 // on to the next bit range
82#ifdef MI_HAVE_FAST_BITSCAN
83 mi_assert_internal(mapm != 0);
84 const size_t shift = (count == 1 ? 1 : (MI_SIZE_BITS - mi_clz(mapm) - bitidx));
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// Set `count` bits at `bitmap_idx` to 0 atomically
131// Returns `true` if all `count` bits were 1 previously.
132bool _mi_bitmap_unclaim(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx) {
133 const size_t idx = mi_bitmap_index_field(bitmap_idx);
134 const size_t bitidx = mi_bitmap_index_bit_in_field(bitmap_idx);
135 const size_t mask = mi_bitmap_mask_(count, bitidx);
136 mi_assert_internal(bitmap_fields > idx); MI_UNUSED(bitmap_fields);
137 // mi_assert_internal((bitmap[idx] & mask) == mask);
138 const size_t prev = mi_atomic_and_acq_rel(&bitmap[idx], ~mask);
139 return ((prev & mask) == mask);
140}
141
142
143// Set `count` bits at `bitmap_idx` to 1 atomically
144// Returns `true` if all `count` bits were 0 previously. `any_zero` is `true` if there was at least one zero bit.
145bool _mi_bitmap_claim(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx, bool* any_zero) {
146 const size_t idx = mi_bitmap_index_field(bitmap_idx);
147 const size_t bitidx = mi_bitmap_index_bit_in_field(bitmap_idx);
148 const size_t mask = mi_bitmap_mask_(count, bitidx);
149 mi_assert_internal(bitmap_fields > idx); MI_UNUSED(bitmap_fields);
150 //mi_assert_internal(any_zero != NULL || (bitmap[idx] & mask) == 0);
151 size_t prev = mi_atomic_or_acq_rel(&bitmap[idx], mask);
152 if (any_zero != NULL) { *any_zero = ((prev & mask) != mask); }
153 return ((prev & mask) == 0);
154}
155
156// Returns `true` if all `count` bits were 1. `any_ones` is `true` if there was at least one bit set to one.
157static 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) {
158 const size_t idx = mi_bitmap_index_field(bitmap_idx);
159 const size_t bitidx = mi_bitmap_index_bit_in_field(bitmap_idx);
160 const size_t mask = mi_bitmap_mask_(count, bitidx);
161 mi_assert_internal(bitmap_fields > idx); MI_UNUSED(bitmap_fields);
162 const size_t field = mi_atomic_load_relaxed(&bitmap[idx]);
163 if (any_ones != NULL) { *any_ones = ((field & mask) != 0); }
164 return ((field & mask) == mask);
165}
166
167// Try to set `count` bits at `bitmap_idx` from 0 to 1 atomically.
168// Returns `true` if successful when all previous `count` bits were 0.
169bool _mi_bitmap_try_claim(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx) {
170 const size_t idx = mi_bitmap_index_field(bitmap_idx);
171 const size_t bitidx = mi_bitmap_index_bit_in_field(bitmap_idx);
172 const size_t mask = mi_bitmap_mask_(count, bitidx);
173 mi_assert_internal(bitmap_fields > idx); MI_UNUSED(bitmap_fields);
174 size_t expected = mi_atomic_load_relaxed(&bitmap[idx]);
175 do {
176 if ((expected & mask) != 0) return false;
177 }
178 while (!mi_atomic_cas_strong_acq_rel(&bitmap[idx], &expected, expected | mask));
179 mi_assert_internal((expected & mask) == 0);
180 return true;
181}
182
183
184bool _mi_bitmap_is_claimed(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx) {
185 return mi_bitmap_is_claimedx(bitmap, bitmap_fields, count, bitmap_idx, NULL);
186}
187
188bool _mi_bitmap_is_any_claimed(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx) {
189 bool any_ones;
190 mi_bitmap_is_claimedx(bitmap, bitmap_fields, count, bitmap_idx, &any_ones);
191 return any_ones;
192}
193
194
195//--------------------------------------------------------------------------
196// the `_across` functions work on bitmaps where sequences can cross over
197// between the fields. This is used in arena allocation
198//--------------------------------------------------------------------------
199
200// Try to atomically claim a sequence of `count` bits starting from the field
201// at `idx` in `bitmap` and crossing into subsequent fields. Returns `true` on success.
202// Only needs to consider crossing into the next fields (see `mi_bitmap_try_find_from_claim_across`)
203static 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)
204{
205 mi_assert_internal(bitmap_idx != NULL);
206
207 // check initial trailing zeros
208 mi_bitmap_field_t* field = &bitmap[idx];
209 size_t map = mi_atomic_load_relaxed(field);
210 const size_t initial = mi_clz(map); // count of initial zeros starting at idx
211 mi_assert_internal(initial <= MI_BITMAP_FIELD_BITS);
212 if (initial == 0) return false;
213 if (initial >= count) return _mi_bitmap_try_find_claim_field(bitmap, idx, count, bitmap_idx); // no need to cross fields (this case won't happen for us)
214 if (_mi_divide_up(count - initial, MI_BITMAP_FIELD_BITS) >= (bitmap_fields - idx)) return false; // not enough entries
215
216 // scan ahead
217 size_t found = initial;
218 size_t mask = 0; // mask bits for the final field
219 while(found < count) {
220 field++;
221 map = mi_atomic_load_relaxed(field);
222 const size_t mask_bits = (found + MI_BITMAP_FIELD_BITS <= count ? MI_BITMAP_FIELD_BITS : (count - found));
223 mi_assert_internal(mask_bits > 0 && mask_bits <= MI_BITMAP_FIELD_BITS);
224 mask = mi_bitmap_mask_(mask_bits, 0);
225 if ((map & mask) != 0) return false; // some part is already claimed
226 found += mask_bits;
227 }
228 mi_assert_internal(field < &bitmap[bitmap_fields]);
229
230 // we found a range of contiguous zeros up to the final field; mask contains mask in the final field
231 // now try to claim the range atomically
232 mi_bitmap_field_t* const final_field = field;
233 const size_t final_mask = mask;
234 mi_bitmap_field_t* const initial_field = &bitmap[idx];
235 const size_t initial_idx = MI_BITMAP_FIELD_BITS - initial;
236 const size_t initial_mask = mi_bitmap_mask_(initial, initial_idx);
237
238 // initial field
239 size_t newmap;
240 field = initial_field;
241 map = mi_atomic_load_relaxed(field);
242 do {
243 newmap = (map | initial_mask);
244 if ((map & initial_mask) != 0) { goto rollback; };
245 } while (!mi_atomic_cas_strong_acq_rel(field, &map, newmap));
246
247 // intermediate fields
248 while (++field < final_field) {
249 newmap = MI_BITMAP_FIELD_FULL;
250 map = 0;
251 if (!mi_atomic_cas_strong_acq_rel(field, &map, newmap)) { goto rollback; }
252 }
253
254 // final field
255 mi_assert_internal(field == final_field);
256 map = mi_atomic_load_relaxed(field);
257 do {
258 newmap = (map | final_mask);
259 if ((map & final_mask) != 0) { goto rollback; }
260 } while (!mi_atomic_cas_strong_acq_rel(field, &map, newmap));
261
262 // claimed!
263 *bitmap_idx = mi_bitmap_index_create(idx, initial_idx);
264 return true;
265
266rollback:
267 // roll back intermediate fields
268 // (we just failed to claim `field` so decrement first)
269 while (--field > initial_field) {
270 newmap = 0;
271 map = MI_BITMAP_FIELD_FULL;
272 mi_assert_internal(mi_atomic_load_relaxed(field) == map);
273 mi_atomic_store_release(field, newmap);
274 }
275 if (field == initial_field) { // (if we failed on the initial field, `field + 1 == initial_field`)
276 map = mi_atomic_load_relaxed(field);
277 do {
278 mi_assert_internal((map & initial_mask) == initial_mask);
279 newmap = (map & ~initial_mask);
280 } while (!mi_atomic_cas_strong_acq_rel(field, &map, newmap));
281 }
282 mi_stat_counter_increase(_mi_stats_main.arena_rollback_count,1);
283 // retry? (we make a recursive call instead of goto to be able to use const declarations)
284 if (retries <= 2) {
285 return mi_bitmap_try_find_claim_field_across(bitmap, bitmap_fields, idx, count, retries+1, bitmap_idx);
286 }
287 else {
288 return false;
289 }
290}
291
292
293// Find `count` bits of zeros and set them to 1 atomically; returns `true` on success.
294// Starts at idx, and wraps around to search in all `bitmap_fields` fields.
295bool _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) {
296 mi_assert_internal(count > 0);
297 if (count <= 2) {
298 // we don't bother with crossover fields for small counts
299 return _mi_bitmap_try_find_from_claim(bitmap, bitmap_fields, start_field_idx, count, bitmap_idx);
300 }
301
302 // visit the fields
303 size_t idx = start_field_idx;
304 for (size_t visited = 0; visited < bitmap_fields; visited++, idx++) {
305 if (idx >= bitmap_fields) { idx = 0; } // wrap
306 // first try to claim inside a field
307 /*
308 if (count <= MI_BITMAP_FIELD_BITS) {
309 if (_mi_bitmap_try_find_claim_field(bitmap, idx, count, bitmap_idx)) {
310 return true;
311 }
312 }
313 */
314 // if that fails, then try to claim across fields
315 if (mi_bitmap_try_find_claim_field_across(bitmap, bitmap_fields, idx, count, 0, bitmap_idx)) {
316 return true;
317 }
318 }
319 return false;
320}
321
322// Helper for masks across fields; returns the mid count, post_mask may be 0
323static 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) {
324 MI_UNUSED(bitmap_fields);
325 const size_t bitidx = mi_bitmap_index_bit_in_field(bitmap_idx);
326 if mi_likely(bitidx + count <= MI_BITMAP_FIELD_BITS) {
327 *pre_mask = mi_bitmap_mask_(count, bitidx);
328 *mid_mask = 0;
329 *post_mask = 0;
330 mi_assert_internal(mi_bitmap_index_field(bitmap_idx) < bitmap_fields);
331 return 0;
332 }
333 else {
334 const size_t pre_bits = MI_BITMAP_FIELD_BITS - bitidx;
335 mi_assert_internal(pre_bits < count);
336 *pre_mask = mi_bitmap_mask_(pre_bits, bitidx);
337 count -= pre_bits;
338 const size_t mid_count = (count / MI_BITMAP_FIELD_BITS);
339 *mid_mask = MI_BITMAP_FIELD_FULL;
340 count %= MI_BITMAP_FIELD_BITS;
341 *post_mask = (count==0 ? 0 : mi_bitmap_mask_(count, 0));
342 mi_assert_internal(mi_bitmap_index_field(bitmap_idx) + mid_count + (count==0 ? 0 : 1) < bitmap_fields);
343 return mid_count;
344 }
345}
346
347// Set `count` bits at `bitmap_idx` to 0 atomically
348// Returns `true` if all `count` bits were 1 previously.
349bool _mi_bitmap_unclaim_across(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx) {
350 size_t idx = mi_bitmap_index_field(bitmap_idx);
351 size_t pre_mask;
352 size_t mid_mask;
353 size_t post_mask;
354 size_t mid_count = mi_bitmap_mask_across(bitmap_idx, bitmap_fields, count, &pre_mask, &mid_mask, &post_mask);
355 bool all_one = true;
356 mi_bitmap_field_t* field = &bitmap[idx];
357 size_t prev = mi_atomic_and_acq_rel(field++, ~pre_mask); // clear first part
358 if ((prev & pre_mask) != pre_mask) all_one = false;
359 while(mid_count-- > 0) {
360 prev = mi_atomic_and_acq_rel(field++, ~mid_mask); // clear mid part
361 if ((prev & mid_mask) != mid_mask) all_one = false;
362 }
363 if (post_mask!=0) {
364 prev = mi_atomic_and_acq_rel(field, ~post_mask); // clear end part
365 if ((prev & post_mask) != post_mask) all_one = false;
366 }
367 return all_one;
368}
369
370// Set `count` bits at `bitmap_idx` to 1 atomically
371// Returns `true` if all `count` bits were 0 previously. `any_zero` is `true` if there was at least one zero bit.
372bool _mi_bitmap_claim_across(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx, bool* pany_zero, size_t* already_set) {
373 size_t idx = mi_bitmap_index_field(bitmap_idx);
374 size_t pre_mask;
375 size_t mid_mask;
376 size_t post_mask;
377 size_t mid_count = mi_bitmap_mask_across(bitmap_idx, bitmap_fields, count, &pre_mask, &mid_mask, &post_mask);
378 bool all_zero = true;
379 bool any_zero = false;
380 size_t one_count = 0;
381 _Atomic(size_t)*field = &bitmap[idx];
382 size_t prev = mi_atomic_or_acq_rel(field++, pre_mask);
383 if ((prev & pre_mask) != 0) { all_zero = false; one_count += mi_popcount(prev & pre_mask); }
384 if ((prev & pre_mask) != pre_mask) any_zero = true;
385 while (mid_count-- > 0) {
386 prev = mi_atomic_or_acq_rel(field++, mid_mask);
387 if ((prev & mid_mask) != 0) { all_zero = false; one_count += mi_popcount(prev & mid_mask); }
388 if ((prev & mid_mask) != mid_mask) any_zero = true;
389 }
390 if (post_mask!=0) {
391 prev = mi_atomic_or_acq_rel(field, post_mask);
392 if ((prev & post_mask) != 0) { all_zero = false; one_count += mi_popcount(prev & post_mask); }
393 if ((prev & post_mask) != post_mask) any_zero = true;
394 }
395 if (pany_zero != NULL) { *pany_zero = any_zero; }
396 if (already_set != NULL) { *already_set = one_count; };
397 mi_assert_internal(all_zero ? one_count == 0 : one_count <= count);
398 return all_zero;
399}
400
401
402// Returns `true` if all `count` bits were 1.
403// `any_ones` is `true` if there was at least one bit set to one.
404static 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, size_t* already_set) {
405 size_t idx = mi_bitmap_index_field(bitmap_idx);
406 size_t pre_mask;
407 size_t mid_mask;
408 size_t post_mask;
409 size_t mid_count = mi_bitmap_mask_across(bitmap_idx, bitmap_fields, count, &pre_mask, &mid_mask, &post_mask);
410 bool all_ones = true;
411 bool any_ones = false;
412 size_t one_count = 0;
413 mi_bitmap_field_t* field = &bitmap[idx];
414 size_t prev = mi_atomic_load_relaxed(field++);
415 if ((prev & pre_mask) != pre_mask) all_ones = false;
416 if ((prev & pre_mask) != 0) { any_ones = true; one_count += mi_popcount(prev & pre_mask); }
417 while (mid_count-- > 0) {
418 prev = mi_atomic_load_relaxed(field++);
419 if ((prev & mid_mask) != mid_mask) all_ones = false;
420 if ((prev & mid_mask) != 0) { any_ones = true; one_count += mi_popcount(prev & mid_mask); }
421 }
422 if (post_mask!=0) {
423 prev = mi_atomic_load_relaxed(field);
424 if ((prev & post_mask) != post_mask) all_ones = false;
425 if ((prev & post_mask) != 0) { any_ones = true; one_count += mi_popcount(prev & post_mask); }
426 }
427 if (pany_ones != NULL) { *pany_ones = any_ones; }
428 if (already_set != NULL) { *already_set = one_count; }
429 mi_assert_internal(all_ones ? one_count == count : one_count < count);
430 return all_ones;
431}
432
433bool _mi_bitmap_is_claimed_across(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx, size_t* already_set) {
434 return mi_bitmap_is_claimedx_across(bitmap, bitmap_fields, count, bitmap_idx, NULL, already_set);
435}
436
437bool _mi_bitmap_is_any_claimed_across(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx) {
438 bool any_ones;
439 mi_bitmap_is_claimedx_across(bitmap, bitmap_fields, count, bitmap_idx, &any_ones, NULL);
440 return any_ones;
441}
442