GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

mirrored from https://github.com/microsoft/qdkAvailable

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
92f542e70a6ca4eadffcee9e2e42c59c8f02df49

Branches

Tags

  • No tags available.
0Branches0Tags
Go to file
Add file
Code

Clone

HTTPS

Download ZIP

qdk/source/allocator/mimalloc-sys/mimalloc/src

source/allocator/mimalloc-sys/mimalloc/src/bitmap.h

119lines · modeblame

RawDownload
Latest commit unavailable.
91589c3aIan Davis2 years ago1/* ----------------------------------------------------------------------------
2Copyright (c) 2019-2023 Microsoft Research, Daan Leijen
3This is free software; you can redistribute it and/or modify it under the
4terms 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/* ----------------------------------------------------------------------------
9Concurrent bitmap that can set/reset sequences of bits atomically,
ce21e681Ian Davis11 months ago10represented as an array of fields where each field is a machine word (`size_t`)
91589c3aIan Davis2 years ago11
12There are two api's; the standard one cannot have sequences that cross
13between the bitmap fields (and a sequence must be <= MI_BITMAP_FIELD_BITS).
14(this is used in region allocation)
15
16The `_across` postfixed functions do allow sequences that can cross over
17between the fields. (This is used in arena allocation)
18---------------------------------------------------------------------------- */
19#pragma once
20#ifndef MI_BITMAP_H
21#define MI_BITMAP_H
22
23/* -----------------------------------------------------------
24Bitmap 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
31typedef _Atomic(size_t) mi_bitmap_field_t;
32typedef mi_bitmap_field_t* mi_bitmap_t;
33
34// A bitmap index is the index of the bit in a bitmap.
35typedef size_t mi_bitmap_index_t;
36
37// Create a bit index.
ce21e681Ian Davis11 months ago38static inline mi_bitmap_index_t mi_bitmap_index_create_ex(size_t idx, size_t bitidx) {
39mi_assert_internal(bitidx <= MI_BITMAP_FIELD_BITS);
40return (idx*MI_BITMAP_FIELD_BITS) + bitidx;
41}
91589c3aIan Davis2 years ago42static inline mi_bitmap_index_t mi_bitmap_index_create(size_t idx, size_t bitidx) {
43mi_assert_internal(bitidx < MI_BITMAP_FIELD_BITS);
ce21e681Ian Davis11 months ago44return mi_bitmap_index_create_ex(idx,bitidx);
91589c3aIan Davis2 years ago45}
46
47// Create a bit index.
48static inline mi_bitmap_index_t mi_bitmap_index_create_from_bit(size_t full_bitidx) {
49return mi_bitmap_index_create(full_bitidx / MI_BITMAP_FIELD_BITS, full_bitidx % MI_BITMAP_FIELD_BITS);
50}
51
52// Get the field index from a bit index.
53static inline size_t mi_bitmap_index_field(mi_bitmap_index_t bitmap_idx) {
54return (bitmap_idx / MI_BITMAP_FIELD_BITS);
55}
56
57// Get the bit index in a bitmap field
58static inline size_t mi_bitmap_index_bit_in_field(mi_bitmap_index_t bitmap_idx) {
59return (bitmap_idx % MI_BITMAP_FIELD_BITS);
60}
61
62// Get the full bit index
63static inline size_t mi_bitmap_index_bit(mi_bitmap_index_t bitmap_idx) {
64return bitmap_idx;
65}
66
67/* -----------------------------------------------------------
68Claim a bit sequence atomically
69----------------------------------------------------------- */
70
71// Try to atomically claim a sequence of `count` bits in a single
72// field at `idx` in `bitmap`. Returns `true` on success.
73bool _mi_bitmap_try_find_claim_field(mi_bitmap_t bitmap, size_t idx, const size_t count, mi_bitmap_index_t* bitmap_idx);
74
75// Starts at idx, and wraps around to search in all `bitmap_fields` fields.
76// For now, `count` can be at most MI_BITMAP_FIELD_BITS and will never cross fields.
77bool _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);
78
79// Like _mi_bitmap_try_find_from_claim but with an extra predicate that must be fullfilled
80typedef bool (mi_cdecl *mi_bitmap_pred_fun_t)(mi_bitmap_index_t bitmap_idx, void* pred_arg);
81bool _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);
82
83// Set `count` bits at `bitmap_idx` to 0 atomically
84// Returns `true` if all `count` bits were 1 previously.
85bool _mi_bitmap_unclaim(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx);
86
87// Try to set `count` bits at `bitmap_idx` from 0 to 1 atomically.
88// Returns `true` if successful when all previous `count` bits were 0.
89bool _mi_bitmap_try_claim(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx);
90
91// Set `count` bits at `bitmap_idx` to 1 atomically
92// Returns `true` if all `count` bits were 0 previously. `any_zero` is `true` if there was at least one zero bit.
93bool _mi_bitmap_claim(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx, bool* any_zero);
94
95bool _mi_bitmap_is_claimed(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx);
96bool _mi_bitmap_is_any_claimed(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx);
97
98
99//--------------------------------------------------------------------------
100// the `_across` functions work on bitmaps where sequences can cross over
101// between the fields. This is used in arena allocation
102//--------------------------------------------------------------------------
103
104// Find `count` bits of zeros and set them to 1 atomically; returns `true` on success.
105// Starts at idx, and wraps around to search in all `bitmap_fields` fields.
106bool _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);
107
108// Set `count` bits at `bitmap_idx` to 0 atomically
109// Returns `true` if all `count` bits were 1 previously.
110bool _mi_bitmap_unclaim_across(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx);
111
112// Set `count` bits at `bitmap_idx` to 1 atomically
113// Returns `true` if all `count` bits were 0 previously. `any_zero` is `true` if there was at least one zero bit.
ce21e681Ian Davis11 months ago114bool _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 ago115
ce21e681Ian Davis11 months ago116bool _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);
91589c3aIan Davis2 years ago117bool _mi_bitmap_is_any_claimed_across(mi_bitmap_t bitmap, size_t bitmap_fields, size_t count, mi_bitmap_index_t bitmap_idx);
118
119#endif