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
|
#include "../util.h"
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
/**
* These cache-size details are from
* https://www.copetti.org/writings/consoles/nintendo-3ds/. We call the second
* level of cache (only available on N3DS) L3, since this GC design only cares
* about L1D and L3.
*/
static const size_t L1D_SIZE = 16 * 1024, L3_SIZE = 2 * 1024 * 1024;
/**
* Constants that should probably be learned.
*/
static const size_t NURSERY_L1D_SIZE_FACTOR = 1;
static const size_t YOUNG_HEAP_L3_SIZE_FACTOR = 2;
/**
* Objects each have a header, with a slightly different layout depending on
* which heap the object is in. Each header tracks the layout of the object
* itself, as well as some other properties, in a uniform way. via the
* `enum object_kind` and `struct object_size` types.
*/
/**
* Gives special properties the object might have, as well as the interpretation
* of its size.
*/
enum object_kind {
/**
* A normal object. Has up to 2¹⁶ slots for values, and up to 2¹³ slots for
* untraced `uintptr_t`s (which may simply be used as bytes).
*/
OBJECT_NORMAL,
/**
* An untraced object. Has up to 2²⁹ slots for untraced `uintptr_t`s (which
* may simply be used as bytes).
*/
OBJECT_UNTRACED,
/**
* A hashtable keyed by the addresses. This behaves like a normal object, but
* the first untraced slot gets set to the `uintptr_t` 1 whenever a collection
* traces the hashtable.
*
* The hashtable uses this information to rehash after each collection.
*/
OBJECT_EQ_HASHTABLE,
/**
* A wrapper for a pointer to a code address. When this object gets collected,
* calls `free_code` on its first untraced slot.
*/
OBJECT_COMPILED_FUNCTION,
};
/**
* A `size_t`-sized encoding of the object size. Also stores an extra bit used
* to indicate that the object has been moved in nursery collection, and that
* the object has been marked in old-heap collection.
*/
struct object_size {
enum object_kind kind : 2;
bool mark : 1;
size_t bits : (8 * sizeof(size_t)) - 3;
};
/**
* Returns the number of slots for values the object has.
*/
static size_t object_value_slots(struct object_size size) {
switch (size.kind) {
case OBJECT_NORMAL:
case OBJECT_EQ_HASHTABLE:
case OBJECT_COMPILED_FUNCTION:
return size.bits >> ((4 * sizeof(size_t)) - 3);
case OBJECT_UNTRACED:
return 0;
}
}
/**
* Returns the number of untraced slots the object has.
*/
static size_t object_untraced_slots(struct object_size size) {
switch (size.kind) {
case OBJECT_NORMAL:
case OBJECT_EQ_HASHTABLE:
case OBJECT_COMPILED_FUNCTION:
return size.bits & ((1 << ((4 * sizeof(size_t)) - 3)) - 1);
case OBJECT_UNTRACED:
return size.bits;
}
}
/**
* This struct is used as an opaque type for the fields of an object.
*/
struct object {
uintptr_t hd;
uintptr_t tl[];
};
/**
* This is the layout of an object in the nursery.
*/
struct nursery_object {
struct object_size size;
uintptr_t slots[];
};
/**
* This is the layout of an object in the young-heap. Because the young-heap is
* collected with mark-compact, it needs a dedicated forwarding pointer (or in
* our case, a forwarding offset) and can't simply overwrite the object slots
* with one.
*/
struct young_heap_object {
struct object_size size;
size_t fwd;
uintptr_t slots[];
};
/**
* This is the layout of an object in the old-heap. It matches the nursery
* layout at the moment.
*/
struct old_heap_object {
struct object_size size;
uintptr_t slots[];
};
/**
* The nursery and young-heap each have a layout like:
*
* ┌──────────────┐ ←── Top
* │remembered set│
* ├──────────────┤ ←── Limit
* │ free │
* │ space │
* ├──────────────┤ ←── Next
* │ │
* │ │
* │ objects │
* │ │
* │ │
* └──────────────┘ ←── Bottom
*
* The layout of both regions are defined by the four labelled pointers, so we
* define them.
*/
uintptr_t nursery_bottom, nursery_next, nursery_limit, nursery_top;
uintptr_t young_heap_bottom, young_heap_next, young_heap_limit, young_heap_top;
/**
* The old-heap is composed of blocks, each of which are stored in an
* intrusive doubly linked list per size class. Size classes start at 8 bytes
* and go up to 64KiB, with a "large object" size class past that. For size
* classes up to and including 4KiB, blocks are 64KiB in size. Past that, blocks
* are sized to fit one object of the size class.
*
* Each block has a local free-list of objects of the size class.
*/
enum old_heap_size_class {
SIZE_8 = 0,
SIZE_16,
SIZE_32,
SIZE_64,
SIZE_128,
SIZE_256,
SIZE_512,
SIZE_1024,
SIZE_2048,
SIZE_4096,
SIZE_8192,
SIZE_16384,
SIZE_32768,
SIZE_65536,
SIZE_HUGE,
SIZE_CLASS_COUNT,
};
struct old_heap_block {
struct old_heap_block *prev, *next;
struct old_heap_free_object *free_list;
};
struct old_heap_free_object {
struct old_heap_free_object *next;
};
static struct old_heap_block old_heap_sentinels[SIZE_CLASS_COUNT];
void gc_init(void) {
// Allocate the nursery and young-heap.
nursery_bottom = nursery_next =
(uintptr_t)malloc(L1D_SIZE * NURSERY_L1D_SIZE_FACTOR);
assume(nursery_bottom);
young_heap_bottom = young_heap_next =
(uintptr_t)malloc(L3_SIZE * YOUNG_HEAP_L3_SIZE_FACTOR);
assume(young_heap_bottom);
// Self-link the old-heap.
for (size_t i = 0; i < SIZE_CLASS_COUNT; i++) {
old_heap_sentinels[i].prev = old_heap_sentinels[i].next =
&old_heap_sentinels[i];
}
}
|
