Repository navigation
Expand file tree
/
Copy pathverse_heap.h
More file actions
325 lines (251 loc) · 13.5 KB
/
Copy pathverse_heap.h
File metadata and controls
325 lines (251 loc) · 13.5 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
/*
* Copyright (c) 2023-2025 Epic Games, Inc. All Rights Reserved.
* Copyright (c) 2026 Filip Pizlo. All Rights Reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY FILIP PIZLO ``AS IS'' AND ANY
* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL FILIP PIZLO OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#ifndef VERSE_HEAP_H
#define VERSE_HEAP_H
#include "pas_allocation_result.h"
#include "pas_bitvector.h"
#include "pas_immutable_vector.h"
#include "pas_simple_large_free_heap.h"
#include "pas_thread_local_cache_layout_node.h"
#include "pas_utils.h"
#include "verse_heap_chunk_map.h"
#include "verse_heap_config.h"
#include "verse_heap_iteration_state.h"
#include "verse_heap_object_set.h"
#include "verse_heap_object_set_set.h"
#include "verse_heap_page_header.h"
#if PAS_ENABLE_VERSE
PAS_BEGIN_EXTERN_C;
typedef struct pas_heap pas_heap;
typedef struct verse_heap_object_set verse_heap_object_set;
typedef struct verse_heap_page_header verse_heap_page_header;
PAS_API extern bool verse_heap_is_ready_for_allocation;
PAS_API extern verse_heap_object_set verse_heap_all_objects;
PAS_API extern verse_heap_object_set_set verse_heap_all_sets;
/* This is meant to be queried directly by the Verse VM. */
PAS_API extern size_t verse_heap_live_bytes;
PAS_API extern size_t verse_heap_swept_bytes; /* Num bytes swept by the last sweep. */
/* This is meant to be set directly by the Verse VM. Anytime live bytes is found to be greater than or equal
the threshold, the trigger callback is called. It's expected that the callback will do its own locking
and it will use that lock to protect its changes to the threshold. */
PAS_API extern size_t verse_heap_live_bytes_trigger_threshold;
PAS_API extern void (*verse_heap_live_bytes_trigger_callback)(void);
/* We never free into this and we make sure that it only ever gets totally zeroed pages. As in, totally
clean pages from time of birth.
FIXME: We need to support these being reserved-but-not-committed pages for systems that don't do demand
paging. */
PAS_API extern pas_simple_large_free_heap verse_heap_page_cache;
PAS_API extern uint64_t verse_heap_latest_version;
PAS_API extern verse_heap_page_header verse_heap_large_objects_header;
PAS_API extern uint64_t verse_heap_allocating_black_version;
PAS_API extern bool verse_heap_is_sweeping;
PAS_API extern verse_heap_iteration_state verse_heap_current_iteration_state;
PAS_API extern size_t verse_heap_num_large_entries_for_iteration;
PAS_API extern pas_allocator_counts verse_heap_allocator_counts;
PAS_DECLARE_IMMUTABLE_VECTOR(verse_heap_thread_local_cache_layout_node_vector,
pas_thread_local_cache_layout_node);
PAS_API extern verse_heap_thread_local_cache_layout_node_vector verse_heap_thread_local_cache_layout_node_vector_instance;
/* Creates a heap with the requested minalign and optionally size and alignment.
Heaps cannot be destroyed.
If the min_align argument is smaller than VERSE_HEAP_MIN_ALIGN then the behavior is as if it was
VERSE_HEAP_MIN_ALIGN, but it must be at least 1.
If the size is 0, then:
- Alignment is ignored.
- This heap has no special virtual memory reservation; it just uses the global page cache.
If the size is not zero, then:
- Size must be at least VERSE_HEAP_CHUNK_SIZE.
- Alignment must be a power of 2 and at least 1.
- Size must be aligned to alignment.
- The heap uses a virtual memory reservation of that size and alignment. */
PAS_API pas_heap* verse_heap_create(size_t min_align, size_t size, size_t alignment);
PAS_API void verse_heap_did_become_ready_for_allocation(void);
PAS_API void* verse_heap_get_base(pas_heap* heap);
PAS_API void verse_heap_add_to_set(pas_heap* heap, verse_heap_object_set* set);
/* Call this from one thread to start sweep and then do a handshake and then call the second function. */
PAS_API void verse_heap_start_allocating_black_before_handshake(void);
PAS_API void verse_heap_start_sweep_before_handshake(void);
PAS_API size_t verse_heap_start_sweep_after_handshake(void);
/* Use this to sweep in parallel (each thread calls this with a different range). */
PAS_API void verse_heap_sweep_range(size_t begin, size_t end);
/* Call this from one thread to end the sweep. */
PAS_API void verse_heap_end_sweep(void);
PAS_API pas_thread_local_cache_node* verse_heap_get_thread_local_cache_node(void);
PAS_API void verse_heap_thread_local_cache_node_stop_local_allocators(pas_thread_local_cache_node* node,
uint64_t expected_version);
PAS_API uintptr_t verse_heap_find_allocated_object_start(uintptr_t inner_ptr);
PAS_API size_t verse_heap_get_allocation_size(uintptr_t inner_ptr);
PAS_API bool verse_heap_owns_address(uintptr_t ptr);
PAS_API verse_heap_page_header* verse_heap_get_page_header(uintptr_t inner_ptr);
PAS_API pas_heap* verse_heap_get_heap(uintptr_t inner_ptr);
static PAS_ALWAYS_INLINE unsigned* verse_heap_mark_bits_word_for_address(uintptr_t address)
{
return (unsigned*)pas_round_down_to_power_of_2(address, VERSE_HEAP_CHUNK_SIZE)
+ PAS_BITVECTOR_WORD_INDEX(
pas_modulo_power_of_2(address, VERSE_HEAP_CHUNK_SIZE) >> VERSE_HEAP_MIN_ALIGN_SHIFT);
}
/* This is the fastest path to querying a mark bit if you get an object "out of the blue". If you're querying
mark bits for a bunch of objects in the same page, then it's more efficient to use bitvector ops directly
after getting the appropriate slice of bits from verse_heap_mark_bits_base_for_boundary. */
static PAS_ALWAYS_INLINE bool verse_heap_is_marked(void* object)
{
return pas_bitvector_get_from_word(
*verse_heap_mark_bits_word_for_address((uintptr_t)object),
(uintptr_t)object >> VERSE_HEAP_MIN_ALIGN_SHIFT);
}
/* This is the fastest path to setting or clearing a mark bit if you get an object "out of the blue". If you're
modifying mark bits for a bunch of objects in the same page, then it's more efficient to use bitvector ops
directly after getting the appropriate slice of bits from verse_heap_mark_bits_base_for_boundary.
Also, this is an atomic operation with full fencing. In some parts of the GC algorithm, you can (and should)
try to:
- Not use atomics. You can get away with that under certain conditions. For example: if you know that you are
setting or clearing all of the mark bits in a word and nobody else is looking to do the opposite of you.
- Use relaxed atomics. For example, parallel marking can (and should) use unfenced CAS to set mark bits on
those CPUs that have such a thing, since based on the Riptide experience, that's worth significant overall
throughput. But you cannot do that for conservative marking (see verse_heap_inlines.h, comment above
verse_heap_find_allocated_object_start()). You also cannot use relaxed atomics in the libpas black
allocation, since that must be fenced against modifying alloc metadata (ibid).
Returns true if we marked the object, or false if it was already marked. */
static PAS_ALWAYS_INLINE bool verse_heap_set_is_marked(void* object, bool value)
{
return pas_bitvector_set_atomic_in_word(
verse_heap_mark_bits_word_for_address((uintptr_t)object),
(uintptr_t)object >> VERSE_HEAP_MIN_ALIGN_SHIFT,
value);
}
static PAS_ALWAYS_INLINE bool verse_heap_set_is_marked_relaxed(void* object, bool value)
{
return pas_bitvector_set_atomic_in_word_relaxed(
verse_heap_mark_bits_word_for_address((uintptr_t)object),
(uintptr_t)object >> VERSE_HEAP_MIN_ALIGN_SHIFT,
value);
}
static PAS_ALWAYS_INLINE unsigned* verse_heap_mark_bits_base_for_boundary(void* page_boundary)
{
PAS_TESTING_ASSERT(pas_is_aligned((uintptr_t)page_boundary, VERSE_HEAP_MIN_ALIGN));
PAS_TESTING_ASSERT(!PAS_BITVECTOR_BIT_SHIFT((uintptr_t)page_boundary >> VERSE_HEAP_MIN_ALIGN_SHIFT));
return verse_heap_mark_bits_word_for_address((uintptr_t)page_boundary);
}
/* This is an internal-ish function. */
PAS_API void verse_heap_initialize_page_cache_config(pas_large_free_heap_config* config);
PAS_API size_t verse_heap_get_size(pas_heap* heap);
PAS_API size_t verse_heap_get_alignment(pas_heap* heap);
PAS_API size_t verse_heap_get_min_align(pas_heap* heap);
/* WARNING: Deallocation is not supported in the verse heap, except in the case of TLC stoppage, and internally
as part of the sweep. */
static PAS_ALWAYS_INLINE verse_heap_iteration_state verse_heap_get_iteration_state(void)
{
uint64_t version;
verse_heap_iteration_state* state;
verse_heap_iteration_state result;
uint64_t new_version;
version = verse_heap_current_iteration_state.version;
if (!version) {
pas_zero_memory(&result, sizeof(result));
return result;
}
state = &verse_heap_current_iteration_state + pas_depend(version);
result.version = version;
result.set_being_iterated = state->set_being_iterated;
state = &verse_heap_current_iteration_state
+ pas_depend((uintptr_t)result.set_being_iterated);
new_version = state->version;
if (new_version != version) {
/* We only admit two possibilities here:
- We went from iterating to not iterating, so the new_version is zero. In that case, we know that
there's no iteration going on for the purpose of this function.
- We went from iterating to not iterating to iterating again, but we haven't had a handshake yet.
In that case, we can act as if we're not iterating. */
PAS_ASSERT(!new_version || new_version > version);
pas_zero_memory(&result, sizeof(result));
}
return result;
}
static PAS_ALWAYS_INLINE void verse_heap_notify_allocation(uintptr_t bytes_allocated)
{
uintptr_t new_live_bytes;
PAS_ASSERT((intptr_t)bytes_allocated >= 0);
if (!bytes_allocated)
return;
for (;;) {
uintptr_t old_live_bytes;
old_live_bytes = verse_heap_live_bytes;
new_live_bytes = old_live_bytes + bytes_allocated;
PAS_ASSERT(new_live_bytes > old_live_bytes);
if (pas_compare_and_swap_uintptr_weak(&verse_heap_live_bytes, old_live_bytes, new_live_bytes))
break;
}
if (new_live_bytes >= verse_heap_live_bytes_trigger_threshold)
verse_heap_live_bytes_trigger_callback();
}
static PAS_ALWAYS_INLINE void verse_heap_notify_deallocation(uintptr_t bytes_deallocated)
{
PAS_ASSERT((intptr_t)bytes_deallocated >= 0);
if (!bytes_deallocated)
return;
for (;;) {
uintptr_t old_live_bytes;
uintptr_t new_live_bytes;
old_live_bytes = verse_heap_live_bytes;
new_live_bytes = old_live_bytes - bytes_deallocated;
PAS_ASSERT(new_live_bytes < old_live_bytes);
if (pas_compare_and_swap_uintptr_weak(&verse_heap_live_bytes, old_live_bytes, new_live_bytes))
break;
}
}
static PAS_ALWAYS_INLINE void verse_heap_notify_sweep(uintptr_t bytes_swept)
{
PAS_ASSERT((intptr_t)bytes_swept >= 0);
if (!bytes_swept)
return;
verse_heap_notify_deallocation(bytes_swept);
for (;;) {
uintptr_t old_swept_bytes;
uintptr_t new_swept_bytes;
old_swept_bytes = verse_heap_swept_bytes;
new_swept_bytes = verse_heap_swept_bytes + bytes_swept;
PAS_ASSERT(new_swept_bytes > old_swept_bytes);
if (pas_compare_and_swap_uintptr_weak(&verse_heap_swept_bytes, old_swept_bytes, new_swept_bytes))
break;
}
}
/* Shorthand for verse_heap_find_allocated_object_start((uintptr_t)ptr) == (uintptr_t)ptr.
For now, this is only intended for testing. A byproduct of calling this in a test is that it causes us to look at the
page header of any page that the chunk map says is allocated. Tests rely on that.
If we wanted to use this outside testing, we'd have to combine it with a GC state check and a mark bit check, plus some
other logic. */
PAS_API bool verse_heap_object_is_allocated(void* ptr);
/* This is meant to be called as the casual case of the Verse VM allocator. It can handle any size. Note that
this is a different algorithm from pas_try_allocate_common.
For fast case allocation, the Verse VM should maintain its own table of local allocators for the sizes and
heaps it wants to use. */
PAS_API pas_allocation_result verse_heap_try_allocate(pas_heap* heap, size_t size);
PAS_API pas_allocation_result verse_heap_allocate(pas_heap* heap, size_t size);
/* This is mean to be called as the fast case of aligned allocation. */
PAS_API pas_allocation_result verse_heap_try_allocate_with_alignment(pas_heap* heap, size_t size, size_t alignment);
PAS_API pas_allocation_result verse_heap_allocate_with_alignment(pas_heap* heap, size_t size, size_t alignment);
PAS_END_EXTERN_C;
#endif /* PAS_ENABLE_VERSE */
#endif /* VERSE_HEAP_H */