| 1 |
/* ---------------------------------------------------------------------------- |
| 2 |
Copyright (c) 2019-2023 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 |
represented 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 |
|
| 15 |
The `_across` postfixed functions do allow sequences that can cross over |
| 16 |
between 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. |
| 28 |
static 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. |
| 43 |
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) |
| 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_INTPTR_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. |
| 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 fulfilled |
| 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 |
// Set `count` bits at `bitmap_idx` to 0 atomically |
| 131 |
// Returns `true` if all `count` bits were 1 previously. |
| 132 |
bool _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. |
| 145 |
bool _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. |
| 157 |
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) { |
| 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. |
| 169 |
bool _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 |
|
| 184 |
bool _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 |
|
| 188 |
bool _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`) |
| 203 |
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) |
| 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 |
|
| 266 |
rollback: |
| 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 |
// retry? (we make a recursive call instead of goto to be able to use const declarations) |
| 283 |
if (retries <= 2) { |
| 284 |
return mi_bitmap_try_find_claim_field_across(bitmap, bitmap_fields, idx, count, retries+1, bitmap_idx); |
| 285 |
} |
| 286 |
else { |
| 287 |
return false; |
| 288 |
} |
| 289 |
} |
| 290 |
|
| 291 |
|
| 292 |
// Find `count` bits of zeros and set them to 1 atomically; returns `true` on success. |
| 293 |
// Starts at idx, and wraps around to search in all `bitmap_fields` fields. |
| 294 |
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) { |
| 295 |
mi_assert_internal(count > 0); |
| 296 |
if (count <= 2) { |
| 297 |
// we don't bother with crossover fields for small counts |
| 298 |
return _mi_bitmap_try_find_from_claim(bitmap, bitmap_fields, start_field_idx, count, bitmap_idx); |
| 299 |
} |
| 300 |
|
| 301 |
// visit the fields |
| 302 |
size_t idx = start_field_idx; |
| 303 |
for (size_t visited = 0; visited < bitmap_fields; visited++, idx++) { |
| 304 |
if (idx >= bitmap_fields) { idx = 0; } // wrap |
| 305 |
// first try to claim inside a field |
| 306 |
if (count <= MI_BITMAP_FIELD_BITS) { |
| 307 |
if (_mi_bitmap_try_find_claim_field(bitmap, idx, count, bitmap_idx)) { |
| 308 |
return true; |
| 309 |
} |
| 310 |
} |
| 311 |
// if that fails, then try to claim across fields |
| 312 |
if (mi_bitmap_try_find_claim_field_across(bitmap, bitmap_fields, idx, count, 0, bitmap_idx)) { |
| 313 |
return true; |
| 314 |
} |
| 315 |
} |
| 316 |
return false; |
| 317 |
} |
| 318 |
|
| 319 |
// Helper for masks across fields; returns the mid count, post_mask may be 0 |
| 320 |
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) { |
| 321 |
MI_UNUSED(bitmap_fields); |
| 322 |
const size_t bitidx = mi_bitmap_index_bit_in_field(bitmap_idx); |
| 323 |
if mi_likely(bitidx + count <= MI_BITMAP_FIELD_BITS) { |
| 324 |
*pre_mask = mi_bitmap_mask_(count, bitidx); |
| 325 |
*mid_mask = 0; |
| 326 |
*post_mask = 0; |
| 327 |
mi_assert_internal(mi_bitmap_index_field(bitmap_idx) < bitmap_fields); |
| 328 |
return 0; |
| 329 |
} |
| 330 |
else { |
| 331 |
const size_t pre_bits = MI_BITMAP_FIELD_BITS - bitidx; |
| 332 |
mi_assert_internal(pre_bits < count); |
| 333 |
*pre_mask = mi_bitmap_mask_(pre_bits, bitidx); |
| 334 |
count -= pre_bits; |
| 335 |
const size_t mid_count = (count / MI_BITMAP_FIELD_BITS); |
| 336 |
*mid_mask = MI_BITMAP_FIELD_FULL; |
| 337 |
count %= MI_BITMAP_FIELD_BITS; |
| 338 |
*post_mask = (count==0 ? 0 : mi_bitmap_mask_(count, 0)); |
| 339 |
mi_assert_internal(mi_bitmap_index_field(bitmap_idx) + mid_count + (count==0 ? 0 : 1) < bitmap_fields); |
| 340 |
return mid_count; |
| 341 |
} |
| 342 |
} |
| 343 |
|
| 344 |
// Set `count` bits at `bitmap_idx` to 0 atomically |
| 345 |
// Returns `true` if all `count` bits were 1 previously. |
| 346 |
bool _mi_bitmap_unclaim_across(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx) { |
| 347 |
size_t idx = mi_bitmap_index_field(bitmap_idx); |
| 348 |
size_t pre_mask; |
| 349 |
size_t mid_mask; |
| 350 |
size_t post_mask; |
| 351 |
size_t mid_count = mi_bitmap_mask_across(bitmap_idx, bitmap_fields, count, &pre_mask, &mid_mask, &post_mask); |
| 352 |
bool all_one = true; |
| 353 |
mi_bitmap_field_t* field = &bitmap[idx]; |
| 354 |
size_t prev = mi_atomic_and_acq_rel(field++, ~pre_mask); // clear first part |
| 355 |
if ((prev & pre_mask) != pre_mask) all_one = false; |
| 356 |
while(mid_count-- > 0) { |
| 357 |
prev = mi_atomic_and_acq_rel(field++, ~mid_mask); // clear mid part |
| 358 |
if ((prev & mid_mask) != mid_mask) all_one = false; |
| 359 |
} |
| 360 |
if (post_mask!=0) { |
| 361 |
prev = mi_atomic_and_acq_rel(field, ~post_mask); // clear end part |
| 362 |
if ((prev & post_mask) != post_mask) all_one = false; |
| 363 |
} |
| 364 |
return all_one; |
| 365 |
} |
| 366 |
|
| 367 |
// Set `count` bits at `bitmap_idx` to 1 atomically |
| 368 |
// Returns `true` if all `count` bits were 0 previously. `any_zero` is `true` if there was at least one zero bit. |
| 369 |
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) { |
| 370 |
size_t idx = mi_bitmap_index_field(bitmap_idx); |
| 371 |
size_t pre_mask; |
| 372 |
size_t mid_mask; |
| 373 |
size_t post_mask; |
| 374 |
size_t mid_count = mi_bitmap_mask_across(bitmap_idx, bitmap_fields, count, &pre_mask, &mid_mask, &post_mask); |
| 375 |
bool all_zero = true; |
| 376 |
bool any_zero = false; |
| 377 |
_Atomic(size_t)*field = &bitmap[idx]; |
| 378 |
size_t prev = mi_atomic_or_acq_rel(field++, pre_mask); |
| 379 |
if ((prev & pre_mask) != 0) all_zero = false; |
| 380 |
if ((prev & pre_mask) != pre_mask) any_zero = true; |
| 381 |
while (mid_count-- > 0) { |
| 382 |
prev = mi_atomic_or_acq_rel(field++, mid_mask); |
| 383 |
if ((prev & mid_mask) != 0) all_zero = false; |
| 384 |
if ((prev & mid_mask) != mid_mask) any_zero = true; |
| 385 |
} |
| 386 |
if (post_mask!=0) { |
| 387 |
prev = mi_atomic_or_acq_rel(field, post_mask); |
| 388 |
if ((prev & post_mask) != 0) all_zero = false; |
| 389 |
if ((prev & post_mask) != post_mask) any_zero = true; |
| 390 |
} |
| 391 |
if (pany_zero != NULL) { *pany_zero = any_zero; } |
| 392 |
return all_zero; |
| 393 |
} |
| 394 |
|
| 395 |
|
| 396 |
// Returns `true` if all `count` bits were 1. |
| 397 |
// `any_ones` is `true` if there was at least one bit set to one. |
| 398 |
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) { |
| 399 |
size_t idx = mi_bitmap_index_field(bitmap_idx); |
| 400 |
size_t pre_mask; |
| 401 |
size_t mid_mask; |
| 402 |
size_t post_mask; |
| 403 |
size_t mid_count = mi_bitmap_mask_across(bitmap_idx, bitmap_fields, count, &pre_mask, &mid_mask, &post_mask); |
| 404 |
bool all_ones = true; |
| 405 |
bool any_ones = false; |
| 406 |
mi_bitmap_field_t* field = &bitmap[idx]; |
| 407 |
size_t prev = mi_atomic_load_relaxed(field++); |
| 408 |
if ((prev & pre_mask) != pre_mask) all_ones = false; |
| 409 |
if ((prev & pre_mask) != 0) any_ones = true; |
| 410 |
while (mid_count-- > 0) { |
| 411 |
prev = mi_atomic_load_relaxed(field++); |
| 412 |
if ((prev & mid_mask) != mid_mask) all_ones = false; |
| 413 |
if ((prev & mid_mask) != 0) any_ones = true; |
| 414 |
} |
| 415 |
if (post_mask!=0) { |
| 416 |
prev = mi_atomic_load_relaxed(field); |
| 417 |
if ((prev & post_mask) != post_mask) all_ones = false; |
| 418 |
if ((prev & post_mask) != 0) any_ones = true; |
| 419 |
} |
| 420 |
if (pany_ones != NULL) { *pany_ones = any_ones; } |
| 421 |
return all_ones; |
| 422 |
} |
| 423 |
|
| 424 |
bool _mi_bitmap_is_claimed_across(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx) { |
| 425 |
return mi_bitmap_is_claimedx_across(bitmap, bitmap_fields, count, bitmap_idx, NULL); |
| 426 |
} |
| 427 |
|
| 428 |
bool _mi_bitmap_is_any_claimed_across(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx) { |
| 429 |
bool any_ones; |
| 430 |
mi_bitmap_is_claimedx_across(bitmap, bitmap_fields, count, bitmap_idx, &any_ones); |
| 431 |
return any_ones; |
| 432 |
} |