| 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 |
(this is used in region allocation) |
| 15 |
|
| 16 |
The `_across` postfixed functions do allow sequences that can cross over |
| 17 |
between the fields. (This is used in arena allocation) |
| 18 |
---------------------------------------------------------------------------- */ |
| 19 |
#pragma once |
| 20 |
#ifndef MI_BITMAP_H |
| 21 |
#define MI_BITMAP_H |
| 22 |
|
| 23 |
/* ----------------------------------------------------------- |
| 24 |
Bitmap definition |
| 25 |
----------------------------------------------------------- */ |
| 26 |
|
| 27 |
#define MI_BITMAP_FIELD_BITS (8*MI_SIZE_SIZE) |
| 28 |
#define MI_BITMAP_FIELD_FULL (~((size_t)0)) // all bits set |
| 29 |
|
| 30 |
// An atomic bitmap of `size_t` fields |
| 31 |
typedef _Atomic(size_t) mi_bitmap_field_t; |
| 32 |
typedef mi_bitmap_field_t* mi_bitmap_t; |
| 33 |
|
| 34 |
// A bitmap index is the index of the bit in a bitmap. |
| 35 |
typedef size_t mi_bitmap_index_t; |
| 36 |
|
| 37 |
// Create a bit index. |
| 38 |
static inline mi_bitmap_index_t mi_bitmap_index_create(size_t idx, size_t bitidx) { |
| 39 |
mi_assert_internal(bitidx < MI_BITMAP_FIELD_BITS); |
| 40 |
return (idx*MI_BITMAP_FIELD_BITS) + bitidx; |
| 41 |
} |
| 42 |
|
| 43 |
// Create a bit index. |
| 44 |
static inline mi_bitmap_index_t mi_bitmap_index_create_from_bit(size_t full_bitidx) { |
| 45 |
return mi_bitmap_index_create(full_bitidx / MI_BITMAP_FIELD_BITS, full_bitidx % MI_BITMAP_FIELD_BITS); |
| 46 |
} |
| 47 |
|
| 48 |
// Get the field index from a bit index. |
| 49 |
static inline size_t mi_bitmap_index_field(mi_bitmap_index_t bitmap_idx) { |
| 50 |
return (bitmap_idx / MI_BITMAP_FIELD_BITS); |
| 51 |
} |
| 52 |
|
| 53 |
// Get the bit index in a bitmap field |
| 54 |
static inline size_t mi_bitmap_index_bit_in_field(mi_bitmap_index_t bitmap_idx) { |
| 55 |
return (bitmap_idx % MI_BITMAP_FIELD_BITS); |
| 56 |
} |
| 57 |
|
| 58 |
// Get the full bit index |
| 59 |
static inline size_t mi_bitmap_index_bit(mi_bitmap_index_t bitmap_idx) { |
| 60 |
return bitmap_idx; |
| 61 |
} |
| 62 |
|
| 63 |
/* ----------------------------------------------------------- |
| 64 |
Claim a bit sequence atomically |
| 65 |
----------------------------------------------------------- */ |
| 66 |
|
| 67 |
// Try to atomically claim a sequence of `count` bits in a single |
| 68 |
// field at `idx` in `bitmap`. Returns `true` on success. |
| 69 |
bool _mi_bitmap_try_find_claim_field(mi_bitmap_t bitmap, size_t idx, const size_t count, mi_bitmap_index_t* bitmap_idx); |
| 70 |
|
| 71 |
// Starts at idx, and wraps around to search in all `bitmap_fields` fields. |
| 72 |
// For now, `count` can be at most MI_BITMAP_FIELD_BITS and will never cross fields. |
| 73 |
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); |
| 74 |
|
| 75 |
// Like _mi_bitmap_try_find_from_claim but with an extra predicate that must be fulfilled |
| 76 |
typedef bool (mi_cdecl *mi_bitmap_pred_fun_t)(mi_bitmap_index_t bitmap_idx, void* pred_arg); |
| 77 |
bool _mi_bitmap_try_find_from_claim_pred(mi_bitmap_t bitmap, const size_t bitmap_fields, const size_t start_field_idx, const size_t count, mi_bitmap_pred_fun_t pred_fun, void* pred_arg, mi_bitmap_index_t* bitmap_idx); |
| 78 |
|
| 79 |
// Set `count` bits at `bitmap_idx` to 0 atomically |
| 80 |
// Returns `true` if all `count` bits were 1 previously. |
| 81 |
bool _mi_bitmap_unclaim(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx); |
| 82 |
|
| 83 |
// Try to set `count` bits at `bitmap_idx` from 0 to 1 atomically. |
| 84 |
// Returns `true` if successful when all previous `count` bits were 0. |
| 85 |
bool _mi_bitmap_try_claim(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx); |
| 86 |
|
| 87 |
// Set `count` bits at `bitmap_idx` to 1 atomically |
| 88 |
// Returns `true` if all `count` bits were 0 previously. `any_zero` is `true` if there was at least one zero bit. |
| 89 |
bool _mi_bitmap_claim(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx, bool* any_zero); |
| 90 |
|
| 91 |
bool _mi_bitmap_is_claimed(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx); |
| 92 |
bool _mi_bitmap_is_any_claimed(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx); |
| 93 |
|
| 94 |
|
| 95 |
//-------------------------------------------------------------------------- |
| 96 |
// the `_across` functions work on bitmaps where sequences can cross over |
| 97 |
// between the fields. This is used in arena allocation |
| 98 |
//-------------------------------------------------------------------------- |
| 99 |
|
| 100 |
// Find `count` bits of zeros and set them to 1 atomically; returns `true` on success. |
| 101 |
// Starts at idx, and wraps around to search in all `bitmap_fields` fields. |
| 102 |
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); |
| 103 |
|
| 104 |
// Set `count` bits at `bitmap_idx` to 0 atomically |
| 105 |
// Returns `true` if all `count` bits were 1 previously. |
| 106 |
bool _mi_bitmap_unclaim_across(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx); |
| 107 |
|
| 108 |
// Set `count` bits at `bitmap_idx` to 1 atomically |
| 109 |
// Returns `true` if all `count` bits were 0 previously. `any_zero` is `true` if there was at least one zero bit. |
| 110 |
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); |
| 111 |
|
| 112 |
bool _mi_bitmap_is_claimed_across(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx); |
| 113 |
bool _mi_bitmap_is_any_claimed_across(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx); |
| 114 |
|
| 115 |
#endif |