microsoft/qdk
Publicmirrored fromhttps://github.com/microsoft/qdkAvailable
allocator/mimalloc-sys/mimalloc/src/bitmap.c
432lines · modecode
| 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 | 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 | |
| 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 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 | // 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 | } |
| 433 | |