microsoft/qdk
Publicmirrored from https://github.com/microsoft/qdkAvailable
source/allocator/mimalloc-sys/mimalloc/src/bitmap.c
441lines · modeblame
91589c3aIan Davis2 years ago | 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, | |
ce21e681Ian Davis11 months ago | 10 | represented as an array of fields where each field is a machine word (`size_t`) |
91589c3aIan Davis2 years ago | 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); | |
ce21e681Ian Davis11 months ago | 84 | const size_t shift = (count == 1 ? 1 : (MI_SIZE_BITS - mi_clz(mapm) - bitidx)); |
91589c3aIan Davis2 years ago | 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 | | |
ce21e681Ian Davis11 months ago | 167 | // Try to set `count` bits at `bitmap_idx` from 0 to 1 atomically. |
91589c3aIan Davis2 years ago | 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]); | |
ce21e681Ian Davis11 months ago | 175 | do { |
91589c3aIan Davis2 years ago | 176 | if ((expected & mask) != 0) return false; |
ce21e681Ian Davis11 months ago | 177 | } |
91589c3aIan Davis2 years ago | 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 | |
ce21e681Ian Davis11 months ago | 215 | |
91589c3aIan Davis2 years ago | 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 | } | |
ce21e681Ian Davis11 months ago | 282 | mi_stat_counter_increase(_mi_stats_main.arena_rollback_count,1); |
91589c3aIan Davis2 years ago | 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. | |
| 295 | 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) { | |
| 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 | |
ce21e681Ian Davis11 months ago | 307 | /* |
91589c3aIan Davis2 years ago | 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 | } | |
ce21e681Ian Davis11 months ago | 313 | */ |
91589c3aIan Davis2 years ago | 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 | |
| 323 | 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) { | |
| 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. | |
| 349 | bool _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. | |
ce21e681Ian Davis11 months ago | 372 | 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, size_t* already_set) { |
91589c3aIan Davis2 years ago | 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; | |
ce21e681Ian Davis11 months ago | 380 | size_t one_count = 0; |
91589c3aIan Davis2 years ago | 381 | _Atomic(size_t)*field = &bitmap[idx]; |
| 382 | size_t prev = mi_atomic_or_acq_rel(field++, pre_mask); | |
ce21e681Ian Davis11 months ago | 383 | if ((prev & pre_mask) != 0) { all_zero = false; one_count += mi_popcount(prev & pre_mask); } |
91589c3aIan Davis2 years ago | 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); | |
ce21e681Ian Davis11 months ago | 387 | if ((prev & mid_mask) != 0) { all_zero = false; one_count += mi_popcount(prev & mid_mask); } |
91589c3aIan Davis2 years ago | 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); | |
ce21e681Ian Davis11 months ago | 392 | if ((prev & post_mask) != 0) { all_zero = false; one_count += mi_popcount(prev & post_mask); } |
91589c3aIan Davis2 years ago | 393 | if ((prev & post_mask) != post_mask) any_zero = true; |
| 394 | } | |
| 395 | if (pany_zero != NULL) { *pany_zero = any_zero; } | |
ce21e681Ian Davis11 months ago | 396 | if (already_set != NULL) { *already_set = one_count; }; |
| 397 | mi_assert_internal(all_zero ? one_count == 0 : one_count <= count); | |
91589c3aIan Davis2 years ago | 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. | |
ce21e681Ian Davis11 months ago | 404 | 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, size_t* already_set) { |
91589c3aIan Davis2 years ago | 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; | |
ce21e681Ian Davis11 months ago | 412 | size_t one_count = 0; |
91589c3aIan Davis2 years ago | 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; | |
ce21e681Ian Davis11 months ago | 416 | if ((prev & pre_mask) != 0) { any_ones = true; one_count += mi_popcount(prev & pre_mask); } |
91589c3aIan Davis2 years ago | 417 | while (mid_count-- > 0) { |
| 418 | prev = mi_atomic_load_relaxed(field++); | |
| 419 | if ((prev & mid_mask) != mid_mask) all_ones = false; | |
ce21e681Ian Davis11 months ago | 420 | if ((prev & mid_mask) != 0) { any_ones = true; one_count += mi_popcount(prev & mid_mask); } |
91589c3aIan Davis2 years ago | 421 | } |
| 422 | if (post_mask!=0) { | |
| 423 | prev = mi_atomic_load_relaxed(field); | |
| 424 | if ((prev & post_mask) != post_mask) all_ones = false; | |
ce21e681Ian Davis11 months ago | 425 | if ((prev & post_mask) != 0) { any_ones = true; one_count += mi_popcount(prev & post_mask); } |
91589c3aIan Davis2 years ago | 426 | } |
| 427 | if (pany_ones != NULL) { *pany_ones = any_ones; } | |
ce21e681Ian Davis11 months ago | 428 | if (already_set != NULL) { *already_set = one_count; } |
| 429 | mi_assert_internal(all_ones ? one_count == count : one_count < count); | |
91589c3aIan Davis2 years ago | 430 | return all_ones; |
| 431 | } | |
| 432 | | |
ce21e681Ian Davis11 months ago | 433 | bool _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); | |
91589c3aIan Davis2 years ago | 435 | } |
| 436 | | |
| 437 | bool _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; | |
ce21e681Ian Davis11 months ago | 439 | mi_bitmap_is_claimedx_across(bitmap, bitmap_fields, count, bitmap_idx, &any_ones, NULL); |
91589c3aIan Davis2 years ago | 440 | return any_ones; |
| 441 | } |