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 (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.
mi_bitmap_index_create(size_t idx,size_t bitidx)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.
mi_bitmap_index_create_from_bit(size_t full_bitidx)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.
mi_bitmap_index_field(mi_bitmap_index_t bitmap_idx)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
mi_bitmap_index_bit_in_field(mi_bitmap_index_t bitmap_idx)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
mi_bitmap_index_bit(mi_bitmap_index_t bitmap_idx)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
116