Repository navigation
Expand file tree
/
Copy pathbitmap.h
More file actions
343 lines (256 loc) · 16.4 KB
/
Copy pathbitmap.h
File metadata and controls
343 lines (256 loc) · 16.4 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
/* ----------------------------------------------------------------------------
Copyright (c) 2019-2024 Microsoft Research, Daan Leijen
This is free software; you can redistribute it and/or modify it under the
terms of the MIT license. A copy of the license can be found in the file
"LICENSE" at the root of this distribution.
-----------------------------------------------------------------------------*/
/* ----------------------------------------------------------------------------
Concurrent bitmap that can set/reset sequences of bits atomically
---------------------------------------------------------------------------- */
#pragma once
#ifndef MI_BITMAP_H
#define MI_BITMAP_H
/* --------------------------------------------------------------------------------
Atomic bitmaps with release/acquire guarantees:
`mi_bfield_t`: is a single machine word that can efficiently be bit counted (usually `size_t`)
each bit usually represents a single MI_ARENA_SLICE_SIZE in an arena (64 KiB).
We need 16K bits to represent a 1GiB arena.
`mi_bchunk_t`: a chunk of bfield's of a total of MI_BCHUNK_BITS (= 512 on 64-bit, 256 on 32-bit)
allocations never span across chunks -- so MI_ARENA_MAX_OBJ_SIZE is the number
of bits in a chunk times the MI_ARENA_SLICE_SIZE (512 * 64KiB = 32 MiB).
These chunks are cache-aligned and we can use AVX2/AVX512/NEON/SVE/SVE2/etc. instructions
to scan for bits (perhaps) more efficiently.
We allocate byte-sized ranges aligned to bytes in the bfield, and bfield-sized
ranges aligned to a bfield.
Searching linearly through the chunks would be too slow (16K bits per GiB).
Instead we add a "chunkmap" to do a two-level search (more or less a btree of depth 2).
`mi_bchunkmap_t` (== `mi_bchunk_t`): for each chunk we track if it has (potentially) any bit set.
The chunkmap has 1 bit per chunk that is set if the chunk potentially has a bit set.
This is used to avoid scanning every chunk. (and thus strictly an optimization)
It is conservative: it is fine to set a bit in the chunk map even if the chunk turns out
to have no bits set. It is also allowed to briefly have a clear bit even if the
chunk has bits set -- as long as we guarantee that the bit will be set later on;
(this allows us to set the chunkmap bit right after we set a bit in the corresponding chunk).
However, when we clear a bit in a chunk, and the chunk is indeed all clear, we
cannot safely clear the bit corresponding to the chunk in the chunkmap since it
may race with another thread setting a bit in the same chunk. Therefore, when
clearing, we first test if a chunk is clear, then clear the chunkmap bit, and
then test again to catch any set bits that we may have missed.
Since the chunkmap may thus be briefly out-of-sync, this means that we may sometimes
not find a free page even though it's there (but we accept this as we avo
8000
id taking
full locks). (Another way to do this is to use an epoch but we like to avoid that complexity
for now).
`mi_bitmap_t`: a bitmap with N chunks. A bitmap has a chunkmap of MI_BCHUNK_BITS (512)
and thus has at most 512 chunks (=2^18 bits x 64 KiB slices = 16 GiB max arena size).
The minimum is 1 chunk which is a 32 MiB arena.
For now, the implementation assumes MI_HAS_FAST_BITSCAN and uses trailing-zero-count
and pop-count (but we think it can be adapted work reasonably well on older hardware too)
--------------------------------------------------------------------------------------------- */
// A word-size bit field.
typedef size_t mi_bfield_t;
#define MI_BFIELD_BITS_SHIFT (MI_SIZE_SHIFT+3)
#define MI_BFIELD_BITS (1 << MI_BFIELD_BITS_SHIFT)
#define MI_BFIELD_SIZE (MI_BFIELD_BITS/8)
#define MI_BFIELD_LO_BIT8 (((~(mi_bfield_t)0))/0xFF) // 0x01010101 ..
#define MI_BFIELD_HI_BIT8 (MI_BFIELD_LO_BIT8 << 7) // 0x80808080 ..
#define MI_BCHUNK_SIZE (MI_BCHUNK_BITS / 8)
#define MI_BCHUNK_FIELDS (MI_BCHUNK_BITS / MI_BFIELD_BITS) // 8 on both 64- and 32-bit
// some compiler (msvc in C mode) cannot have expressions in the alignment attribute
#if MI_BCHUNK_SIZE==64
#define mi_decl_bchunk_align mi_decl_align(64)
#elif MI_BCHUNK_SIZE==32
#define mi_decl_bchunk_align mi_decl_align(32)
#else
#define mi_decl_bchunk_align mi_decl_align(MI_BCHUNK_SIZE)
#endif
// A bitmap chunk contains 512 bits on 64-bit (256 on 32-bit)
typedef mi_decl_bchunk_align struct mi_bchunk_s {
_Atomic(mi_bfield_t) bfields[MI_BCHUNK_FIELDS];
} mi_bchunk_t;
// The chunkmap has one bit per corresponding chunk that is set if the chunk potentially has bits set.
// The chunkmap is itself a chunk.
typedef mi_bchunk_t mi_bchunkmap_t;
#define MI_BCHUNKMAP_BITS MI_BCHUNK_BITS
#define MI_BITMAP_MAX_CHUNK_COUNT (MI_BCHUNKMAP_BITS)
#define MI_BITMAP_MIN_CHUNK_COUNT (1)
#if MI_SIZE_BITS > 32
#define MI_BITMAP_DEFAULT_CHUNK_COUNT (64) // 2 GiB on 64-bit -- this is for the page map
#else
#define MI_BITMAP_DEFAULT_CHUNK_COUNT (1)
#endif
#define MI_BITMAP_MAX_BIT_COUNT (MI_BITMAP_MAX_CHUNK_COUNT * MI_BCHUNK_BITS) // 16 GiB arena
#define MI_BITMAP_MIN_BIT_COUNT (MI_BITMAP_MIN_CHUNK_COUNT * MI_BCHUNK_BITS) // 32 MiB arena
#define MI_BITMAP_DEFAULT_BIT_COUNT (MI_BITMAP_DEFAULT_CHUNK_COUNT * MI_BCHUNK_BITS) // 2 GiB arena
// An atomic bitmap
struct mi_decl_bchunk_align mi_bitmap_s {
_Atomic(size_t) chunk_count; // total count of chunks (0 < N <= MI_BCHUNKMAP_BITS)
size_t _padding[MI_BCHUNK_SIZE/MI_SIZE_SIZE - 1]; // suppress warning on msvc
mi_bchunkmap_t chunkmap;
mi_bchunk_t chunks[MI_BITMAP_DEFAULT_CHUNK_COUNT]; // usually dynamic MI_BITMAP_MAX_CHUNK_COUNT
};
static inline size_t mi_bitmap_chunk_count(const mi_bitmap_t* bitmap) {
return mi_atomic_load_relaxed(&((mi_bitmap_t*)bitmap)->chunk_count);
}
static inline size_t mi_bitmap_max_bits(const mi_bitmap_t* bitmap) {
return (mi_bitmap_chunk_count(bitmap) * MI_BCHUNK_BITS);
}
/* --------------------------------------------------------------------------------
Atomic bitmap operations
-------------------------------------------------------------------------------- */
// Many operations are generic over setting or clearing the bit sequence: we use `mi_xset_t` for this (true if setting, false if clearing)
typedef bool mi_xset_t;
#define MI_BIT_SET (true)
#define MI_BIT_CLEAR (false)
// Required size of a bitmap to represent `bit_count` bits.
size_t mi_bitmap_size(size_t bit_count, size_t* chunk_count);
// Initialize a bitmap to all clear; avoid a mem_zero if `already_zero` is true
// returns the size of the bitmap.
size_t mi_bitmap_init(mi_bitmap_t* bitmap, size_t bit_count, bool already_zero);
// Set/clear a sequence of `n` bits in the bitmap (and can cross chunks).
// Not atomic so only use if still local to a thread.
void mi_bitmap_unsafe_setN(mi_bitmap_t* bitmap, size_t idx, size_t n);
// Set a bit in the bitmap; returns `true` if it atomically transitioned from 0 to 1
bool mi_bitmap_set(mi_bitmap_t* bitmap, size_t idx);
// Clear a bit in the bitmap; returns `true` if it atomically transitioned from 1 to 0
bool mi_bitmap_clear(mi_bitmap_t* bitmap, size_t idx);
// Set a sequence of `n` bits in the bitmap; returns `true` if atomically transitioned from all 0's to 1's
// If `already_set` is not NULL, it is set to count of bits were already all set.
// (this is used for correct statistics if commiting over a partially committed area)
bool mi_bitmap_setN(mi_bitmap_t* bitmap, size_t idx, size_t n, size_t* already_set);
// Clear a sequence of `n` bits in the bitmap; returns `true` if atomically transitioned from all 1's to 0's
bool mi_bitmap_clearN(mi_bitmap_t* bitmap, size_t idx, size_t n);
// Is a sequence of n bits already all set/cleared?
bool mi_bitmap_is_xsetN(mi_xset_t set, mi_bitmap_t* bitmap, size_t idx, size_t n);
// Is the bitmap completely clear?
bool mi_bitmap_is_all_clear(mi_bitmap_t* bitmap);
// Is a sequence of n bits already set?
// (Used to check if a memory range is already committed)
static inline bool mi_bitmap_is_setN(mi_bitmap_t* bitmap, size_t idx, size_t n) {
return mi_bitmap_is_xsetN(MI_BIT_SET, bitmap, idx, n);
}
// Is a sequence of n bits already clear?
static inline bool mi_bitmap_is_clearN(mi_bitmap_t* bitmap, size_t idx, size_t n) {
return mi_bitmap_is_xsetN(MI_BIT_CLEAR, bitmap, idx, n);
}
static inline bool mi_bitmap_is_set(mi_bitmap_t* bitmap, size_t idx) {
return mi_bitmap_is_setN(bitmap, idx, 1);
}
static inline bool mi_bitmap_is_clear(mi_bitmap_t* bitmap, size_t idx) {
return mi_bitmap_is_clearN(bitmap, idx, 1);
}
// Called once a bit is cleared to see if the memory slice can be claimed.
typedef bool (mi_claim_fun_t)(size_t slice_index, mi_arena_t* arena, bool* keep_set);
// Find a set bits in the bitmap, atomically clear it, and check if `claim` returns true.
// If not claimed, continue on (potentially setting the bit again depending on `keep_set`).
// Returns true on success, and in that case sets the index: `0 <= *pidx <= MI_BITMAP_MAX_BITS-n`.
mi_decl_nodiscard bool mi_bitmap_try_find_and_claim(mi_bitmap_t* bitmap, size_t tseq, size_t* pidx,
mi_claim_fun_t* claim, mi_arena_t* arena );
// Atomically clear a bit but only if it is set. Will block otherwise until the bit is set.
// This is used to delay free-ing a page that it at the same time being considered to be
// allocated from `mi_arena_try_abandoned` (and is in the `claim` function of `mi_bitmap_try_find_and_claim`).
void mi_bitmap_clear_once_set(mi_bitmap_t* bitmap, size_t idx);
// If a bit is set in the bitmap, return `true` and set `idx` to the index of the highest bit.
// Otherwise return `false` (and `*idx` is undefined).
// Used for unloading arena's
bool mi_bitmap_bsr(mi_bitmap_t* bitmap, size_t* idx);
// Return count of all set bits in a bitmap.
size_t mi_bitmap_popcount(mi_bitmap_t* bitmap);
typedef bool (mi_forall_set_fun_t)(size_t slice_index, size_t slice_count, mi_arena_t* arena, void* arg2);
// Visit all set bits in a bitmap (`slice_count == 1`)
bool _mi_bitmap_forall_set(mi_bitmap_t* bitmap, mi_forall_set_fun_t* visit, mi_arena_t* arena, void* arg);
// Visit all set bits in a bitmap with larger ranges if possible (`slice_count >= 1`)
// Ranges will never cross chunk boundaries though (and `slice_count <= MI_BCHUNK_BITS`)
bool _mi_bitmap_forall_setc_ranges(mi_bitmap_t* bitmap, mi_forall_set_fun_t* visit, mi_arena_t* arena, void* arg);
// Visit all set bits in a bitmap with at least `rngslices` at a time (and aligned to `rngslices`).
// This is used by purging to not break up transparent huge pages for example.
// Ranges will never cross chunk boundaries (and `slice_count <= MI_BCHUNK_BITS`).
bool _mi_bitmap_forall_setc_rangesn(mi_bitmap_t* bitmap, size_t rngslices, mi_forall_set_fun_t* visit, mi_arena_t* arena, void* arg);
// Count all set bits in given range in the bitmap.
size_t mi_bitmap_popcountN( mi_bitmap_t* bitmap, size_t idx, size_t n);
/* ----------------------------------------------------------------------------
Binned concurrent bitmap
Assigns a size class to each chunk such that small blocks don't cause too
much fragmentation since we keep chunks for larger blocks separate.
---------------------------------------------------------------------------- */
// mi_chunkbin_t is defined in mimalloc-stats.h
static inline mi_chunkbin_t mi_chunkbin_inc(mi_chunkbin_t bbin) {
mi_assert_internal(bbin < MI_CBIN_COUNT);
return (mi_chunkbin_t)((int)bbin + 1);
}
static inline mi_chunkbin_t mi_chunkbin_dec(mi_chunkbin_t bbin) {
mi_assert_internal(bbin > MI_CBIN_NONE);
return (mi_chunkbin_t)((int)bbin - 1);
}
static inline mi_chunkbin_t mi_chunkbin_of(size_t slice_count) {
if (slice_count==1) return MI_CBIN_SMALL;
if (slice_count==8) return MI_CBIN_MEDIUM;
#if MI_ENABLE_LARGE_PAGES
if (slice_count==MI_BFIELD_BITS) return MI_CBIN_LARGE;
#endif
if (slice_count > MI_BCHUNK_BITS) return MI_CBIN_HUGE;
return MI_CBIN_OTHER;
}
// An atomic "binned" bitmap for the free slices where we keep chunks reserved for particular size classes
struct mi_decl_bchunk_align mi_bbitmap_s {
_Atomic(size_t) chunk_count; // total count of chunks (0 < N <= MI_BCHUNKMAP_BITS)
_Atomic(size_t) chunk_max_accessed; // max chunk index that was once cleared or set
#if (MI_BCHUNK_SIZE / MI_SIZE_SIZE) > 2
size_t _padding[MI_BCHUNK_SIZE/MI_SIZE_SIZE - 2]; // suppress warning on msvc by aligning manually
#endif
mi_bchunkmap_t chunkmap;
mi_bchunkmap_t chunkmap_bins[MI_CBIN_COUNT - 1]; // chunkmaps with bit set if the chunk is in that size class (excluding MI_CBIN_NONE)
mi_bchunk_t chunks[MI_BITMAP_DEFAULT_CHUNK_COUNT]; // usually dynamic MI_BITMAP_MAX_CHUNK_COUNT
};
static inline size_t mi_bbitmap_chunk_count(const mi_bbitmap_t* bbitmap) {
return mi_atomic_load_relaxed(&((mi_bbitmap_t*)bbitmap)->chunk_count);
}
static inline size_t mi_bbitmap_max_bits(const mi_bbitmap_t* bbitmap) {
return (mi_bbitmap_chunk_count(bbitmap) * MI_BCHUNK_BITS);
}
mi_chunkbin_t mi_bbitmap_debug_get_bin(const mi_bchunk_t* chunkmap_bins, size_t chunk_idx);
size_t mi_bbitmap_size(size_t bit_count, size_t* chunk_count);
// If a bit is clear in the bitmap, return `true` and set `idx` to the index of the highest bit that was clear.
// Otherwise return `false` (and `*idx` is undefined).
// Used for debug output.
bool mi_bbitmap_bsr_inv(mi_bbitmap_t* bbitmap, size_t* idx);
// Initialize a bitmap to all clear; avoid a mem_zero if `already_zero` is true
// returns the size of the bitmap.
size_t mi_bbitmap_init(mi_bbitmap_t* bbitmap, size_t bit_count, bool already_zero);
// Set/clear a sequence of `n` bits in the bitmap (and can cross chunks).
// Not atomic so only use if still local
6338
to a thread.
void mi_bbitmap_unsafe_setN(mi_bbitmap_t* bbitmap, size_t idx, size_t n);
// Set a sequence of `n` bits in the bbitmap; returns `true` if atomically transitioned from all 0's to 1's
bool mi_bbitmap_setN(mi_bbitmap_t* bbitmap, size_t idx, size_t n);
// Is a sequence of n bits already all set/cleared?
bool mi_bbitmap_is_xsetN(mi_xset_t set, mi_bbitmap_t* bbitmap, size_t idx, size_t n);
// Is a sequence of n bits already set?
// (Used to check if a memory range is already committed)
static inline bool mi_bbitmap_is_setN(mi_bbitmap_t* bbitmap, size_t idx, size_t n) {
return mi_bbitmap_is_xsetN(MI_BIT_SET, bbitmap, idx, n);
}
// Is a sequence of n bits already clear?
static inline bool mi_bbitmap_is_clearN(mi_bbitmap_t* bbitmap, size_t idx, size_t n) {
return mi_bbitmap_is_xsetN(MI_BIT_CLEAR, bbitmap, idx, n);
}
// Try to atomically transition `n` bits from all set to all clear. Returns `true` on succes.
// `n` cannot cross chunk boundaries, where `n <= MI_CHUNK_BITS`.
bool mi_bbitmap_try_clearNC(mi_bbitmap_t* bbitmap, size_t idx, size_t n);
// Specialized versions for common bit sequence sizes
bool mi_bbitmap_try_find_and_clear(mi_bbitmap_t* bbitmap, size_t tseq, size_t* pidx); // 1-bit
bool mi_bbitmap_try_find_and_clear8(mi_bbitmap_t* bbitmap, size_t tseq, size_t* pidx); // 8-bits
// bool mi_bbitmap_try_find_and_clearX(mi_bbitmap_t* bbitmap, size_t tseq, size_t* pidx); // MI_BFIELD_BITS
bool mi_bbitmap_try_find_and_clearNX(mi_bbitmap_t* bbitmap, size_t n, size_t tseq, size_t* pidx); // < MI_BFIELD_BITS
bool mi_bbitmap_try_find_and_clearNC(mi_bbitmap_t* bbitmap, size_t n, size_t tseq, size_t* pidx); // > MI_BFIELD_BITS <= MI_BCHUNK_BITS
bool mi_bbitmap_try_find_and_clearN_(mi_bbitmap_t* bbitmap, size_t n, size_t tseq, size_t* pidx); // > MI_BCHUNK_BITS
// Find a sequence of `n` bits in the bbitmap with all bits set, and try to atomically clear all.
// Returns true on success, and in that case sets the index: `0 <= *pidx <= MI_BITMAP_MAX_BITS-n`.
mi_decl_nodiscard static inline bool mi_bbitmap_try_find_and_clearN(mi_bbitmap_t* bbitmap, size_t n, size_t tseq, size_t* pidx) {
if (n==1) return mi_bbitmap_try_find_and_clear(bbitmap, tseq, pidx); // small pages
if (n==8) return mi_bbitmap_try_find_and_clear8(bbitmap, tseq, pidx); // medium pages
// if (n==MI_BFIELD_BITS) return mi_bbitmap_try_find_and_clearX(bbitmap, tseq, pidx); // large pages
if (n==0) return false;
if (n<=MI_BFIELD_BITS) return mi_bbitmap_try_find_and_clearNX(bbitmap, tseq, n, pidx);
if (n<=MI_BCHUNK_BITS) return mi_bbitmap_try_find_and_clearNC(bbitmap, tseq, n, pidx);
return mi_bbitmap_try_find_and_clearN_(bbitmap, tseq, n, pidx);
}
#endif // MI_BITMAP_H