OILS / mycpp / demo / gc_header.cc View on Github | oilshell.org

371 lines, 194 significant
1#include <inttypes.h>
2#include <limits.h> // HOST_NAME_MAX
3#include <string.h> // memcpy()
4#include <time.h> // strftime()
5#include <unistd.h> // gethostname()
6
7#include <new> // placement new
8
9#include "mycpp/common.h" // log()
10#include "mycpp/gc_obj.h" // ObjHeader
11#include "vendor/greatest.h"
12
13namespace demo {
14
15// Could put this in ./configure, although glibc seems to have it
16bool IsLittleEndian() {
17 int i = 42;
18 int* pointer_i = &i;
19 char c = *(reinterpret_cast<char*>(pointer_i));
20
21 // Should be 42 on little endian, 0 on big endian
22 return c == 42;
23}
24
25#define GC_NEW(T, ...) \
26 LayoutGc* untyped = gHeap.Allocate(); \
27 T* obj = new (untyped.place)(...) untyped.header = T::obj_header(); \
28 untyped.header.obj_id = gHeap.mark_set_.NextObjectId() return obj
29
30class Point {
31 public:
32 int x;
33 int y;
34
35 int vtag() {
36 char* p = reinterpret_cast<char*>(this);
37 ObjHeader* header = reinterpret_cast<ObjHeader*>(p - sizeof(ObjHeader));
38 return header->type_tag;
39 }
40
41 static constexpr ObjHeader obj_header() {
42 // type_tag is 42
43 return ObjHeader::Global(42);
44 }
45};
46
47// Alloc<T> allocates an instance of T and fills in the GC header BEFORE the
48// object, and BEFORE any vtable (for classes with virtual functions).
49//
50// Alloc<T> is nicer for static dispatch; GC_NEW(T, ...) would be awkward.
51
52// Steps to initialize a GC object:
53//
54// 1. Allocate untyped data
55// 2. Fill in constexpr header data
56// 3. Fill in DYNAMIC header data, like object ID
57// 4. Invoke constructor with placement new
58
59struct LayoutGc {
60 ObjHeader header;
61 uint8_t place[1]; // flexible array, for placement new
62};
63
64template <typename T>
65T* Alloc() {
66 // TODO: use gHeap.Allocate()
67
68 LayoutGc* untyped =
69 static_cast<LayoutGc*>(malloc(sizeof(ObjHeader) + sizeof(T)));
70 untyped->header = T::obj_header();
71
72 // TODO: assign proper object ID from MarkSweepHeap
73 untyped->header.obj_id = 124; // dynamic, but can be done by allocator
74 return new (untyped->place) T();
75}
76
77TEST gc_header_test() {
78 Point* p = Alloc<Point>();
79 log("p = %p", p);
80
81 log("p->vtag() = %d", p->vtag());
82 ASSERT_EQ_FMT(42, p->vtag(), "%d");
83
84 PASS();
85}
86
87class Node {
88 public:
89 Node() {
90 }
91
92 virtual int Method() {
93 return 42;
94 }
95
96 static constexpr ObjHeader obj_header() {
97 return ObjHeader::ClassFixed(field_mask(), sizeof(Node));
98 }
99
100 int x;
101 // max is either 24 or 30 bits, so use unsigned int
102 static constexpr unsigned int field_mask() {
103 return 0x0f;
104 }
105};
106
107class Derived : public Node {
108 public:
109 Derived() : Node() {
110 }
111
112 virtual int Method() {
113 return 43;
114 }
115
116 int x;
117
118 static constexpr unsigned field_mask() {
119 return Node::field_mask() | 0x30;
120 }
121
122 static constexpr ObjHeader obj_header() {
123 return ObjHeader::ClassFixed(field_mask(), sizeof(Derived));
124 }
125};
126
127class NoVirtual {
128 public:
129 NoVirtual() {
130 }
131
132 static constexpr ObjHeader obj_header() {
133 return ObjHeader::ClassFixed(field_mask(), sizeof(NoVirtual));
134 }
135
136 int i;
137
138 static constexpr unsigned field_mask() {
139 return 0xf0;
140 }
141};
142
143// TODO: Put this in mycpp/portability_test.cc and distribute to users
144
145TEST endian_test() {
146 log("little endian? %d", IsLittleEndian());
147
148 Derived* derived = Alloc<Derived>();
149 log("sizeof(Node) = %d", sizeof(Node));
150 log("sizeof(Derived) = %d", sizeof(Derived));
151
152 ObjHeader* header = ObjHeader::FromObject(derived);
153 log("Derived is GC object? %d", header->type_tag & 0x1);
154
155 NoVirtual* n2 = Alloc<NoVirtual>();
156 ObjHeader* header2 = ObjHeader::FromObject(n2);
157 log("NoVirtual is GC object? %d", header2->type_tag & 0x1);
158
159 Node* n = Alloc<Node>();
160 ObjHeader* h = ObjHeader::FromObject(n);
161 FIELD_MASK(*h) = 0b11;
162 log("field mask %d", FIELD_MASK(*h));
163 log("num pointers %d", NUM_POINTERS(*h));
164
165 PASS();
166}
167
168//
169// Union test
170//
171
172// This is 8 bytes! Unions and bitfields don't work together?
173struct UnionBitfield {
174 unsigned heap_tag : 2;
175
176 union Trace {
177 // Note: the string length is NOT used by the GC, so it doesn't really have
178 // to be here. But this makes the BigStr object smaller.
179
180 unsigned str_len : 30; // HeapTag::Opaque
181 unsigned num_pointers : 30; // HeapTag::Scanned
182 unsigned field_mask : 30; // HeapTag::Fixed
183 } trace;
184};
185
186//
187// header_.is_header // 1 bit
188// header_.type_tag // 7 bits
189//
190// #ifdef MARK_SWEEP
191// header_.obj_id
192// #else
193// header_.field_mask
194// #endif
195//
196// header_.heap_tag
197//
198// #ifdef MARK_SWEEP
199// union {
200// header_.field_mask.val
201// header_.str_len.val
202// header_.num_pointers.val
203// }
204// #else
205// header_.obj_len
206// #endif
207
208union ObjHeader2 {
209 // doesn't work: initializations for multiple members?
210 // ObjHeader2() : raw_bytes(0), is_header(1) {
211
212 // also doesn't work
213 // ObjHeader2() : is_header(1), type_tag(1) {
214
215 ObjHeader2() : raw_bytes(0) {
216 }
217
218 uint64_t raw_bytes;
219
220 class _is_header {
221 public:
222 _is_header(int val) : val(val) {
223 }
224 unsigned val : 1;
225 unsigned _1 : 31;
226 unsigned _2 : 32;
227 } is_header;
228
229 struct _type_tag {
230 _type_tag(int val) : val(val) {
231 }
232 unsigned _1 : 1;
233 unsigned val : 7;
234 unsigned _2 : 24;
235 unsigned _3 : 32;
236 } type_tag;
237
238 struct _obj_id {
239 unsigned _1 : 8;
240 unsigned val : 24;
241 unsigned _2 : 32;
242 } obj_id;
243
244 struct _heap_tag {
245 unsigned _1 : 32;
246 unsigned val : 2;
247 unsigned _2 : 30;
248 } heap_tag;
249
250 // These three share the same bigs
251 struct _field_mask {
252 unsigned _1 : 32;
253 unsigned _2 : 2;
254 unsigned val : 30;
255 } field_mask;
256
257 struct _str_len {
258 unsigned _1 : 32;
259 unsigned _2 : 2;
260 unsigned val : 30;
261 } str_len;
262
263 struct _num_pointers {
264 unsigned _1 : 32;
265 unsigned _2 : 2;
266 unsigned val : 30;
267 } num_pointers;
268
269 // Hand-written classes, including fixed size List and Dict headers
270 void InitFixedClass(int field_mask) {
271 this->is_header.val = 1;
272 this->heap_tag.val = HeapTag::FixedSize;
273 this->field_mask.val = field_mask;
274 }
275
276 // - Slab<List*>, Slab<BigStr> (might be HeapStr*)
277 // - Generated classes without inheritance
278 // - all ASDL types
279 void InitScanned(int num_pointers) {
280 this->is_header.val = 1;
281 this->heap_tag.val = HeapTag::Scanned;
282 this->num_pointers.val = num_pointers;
283 }
284
285 void InitStr(int str_len) {
286 this->is_header.val = 1;
287 this->heap_tag.val = HeapTag::Opaque;
288 this->str_len.val = str_len;
289 }
290
291 void InitAsdlVariant(int type_tag, int num_pointers) {
292 this->is_header.val = 1;
293
294 this->type_tag.val = type_tag;
295
296 this->heap_tag.val = HeapTag::Scanned;
297 this->num_pointers.val = num_pointers;
298 }
299
300 // Other:
301 // - HeapTag::Global is for GlobalBigStr*, GLOBAL_LIST, ...
302 //
303 // All the variants of value_e get their own type tag?
304 // - Boxed value.{Bool,Int,Float}
305 // - And "boxless" / "tagless" BigStr, List, Dict
306};
307
308class Token {
309 public:
310 Token() {
311 }
312
313 ObjHeader2 header_;
314};
315
316TEST union_test() {
317 log("sizeof(UnionBitfield) = %d", sizeof(UnionBitfield));
318
319 Token t;
320
321 t.header_.is_header.val = 1;
322
323 t.header_.type_tag.val = 127;
324 t.header_.obj_id.val = 12345678; // max 16 Mi
325
326 t.header_.heap_tag.val = HeapTag::Scanned;
327 t.header_.field_mask.val = 0xff;
328
329 log("is_header %d", t.header_.is_header.val);
330
331 log("type_tag %d", t.header_.type_tag.val);
332 log("obj_id %d", t.header_.obj_id.val);
333
334 log("heap_tag %d", t.header_.heap_tag.val);
335
336 log("field_mask %d", t.header_.field_mask.val);
337 log("str_len %d", t.header_.str_len.val);
338 log("num_pointers %d", t.header_.num_pointers.val);
339
340 // Garbage collector
341
342 // First check check SmallStr.is_present_ - it might not be a pointer at all
343 ObjHeader2* obj = reinterpret_cast<ObjHeader2*>(&t);
344
345 // Then check for vtable - it might not be a pointer to an ObjHeader2
346 if (!obj->is_header.val) {
347 // advance 8 bytes and assert header.is_header
348 log("Not a header");
349 }
350
351 PASS();
352}
353
354} // namespace demo
355
356GREATEST_MAIN_DEFS();
357
358int main(int argc, char** argv) {
359 // gHeap.Init();
360
361 GREATEST_MAIN_BEGIN();
362
363 RUN_TEST(demo::gc_header_test);
364 RUN_TEST(demo::endian_test);
365 RUN_TEST(demo::union_test);
366
367 // gHeap.CleanProcessExit();
368
369 GREATEST_MAIN_END();
370 return 0;
371}