1 | /* ---------------------------------------------------------------------------- |
2 | Copyright (c) 2019-2020 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. |
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 fullfilled |
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 | // Set `count` bits at `bitmap_idx` to 1 atomically |
84 | // Returns `true` if all `count` bits were 0 previously. `any_zero` is `true` if there was at least one zero bit. |
85 | bool _mi_bitmap_claim(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx, bool* any_zero); |
86 | |
87 | bool _mi_bitmap_is_claimed(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx); |
88 | bool _mi_bitmap_is_any_claimed(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx); |
89 | |
90 | |
91 | //-------------------------------------------------------------------------- |
92 | // the `_across` functions work on bitmaps where sequences can cross over |
93 | // between the fields. This is used in arena allocation |
94 | //-------------------------------------------------------------------------- |
95 | |
96 | // Find `count` bits of zeros and set them to 1 atomically; returns `true` on success. |
97 | // Starts at idx, and wraps around to search in all `bitmap_fields` fields. |
98 | 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); |
99 | |
100 | // Set `count` bits at `bitmap_idx` to 0 atomically |
101 | // Returns `true` if all `count` bits were 1 previously. |
102 | bool _mi_bitmap_unclaim_across(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx); |
103 | |
104 | // Set `count` bits at `bitmap_idx` to 1 atomically |
105 | // Returns `true` if all `count` bits were 0 previously. `any_zero` is `true` if there was at least one zero bit. |
106 | 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); |
107 | |
108 | bool _mi_bitmap_is_claimed_across(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx); |
109 | bool _mi_bitmap_is_any_claimed_across(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx); |
110 | |
111 | #endif |
112 | |