OILS / mycpp / gc_heap_test.cc View on Github | oilshell.org

494 lines, 292 significant
1// mycpp/gc_heap_test.cc
2
3#include "mycpp/runtime.h"
4#include "vendor/greatest.h"
5
6#define ASSERT_NUM_LIVE_OBJS(x) \
7 ASSERT_EQ_FMT((x), static_cast<int>(gHeap.num_live()), "%d");
8
9// Hm we're getting a warning because these aren't plain old data?
10// https://stackoverflow.com/questions/1129894/why-cant-you-use-offsetof-on-non-pod-structures-in-c
11// https://stackoverflow.com/questions/53850100/warning-offset-of-on-non-standard-layout-type-derivedclass
12
13// The structures must be layout compatible! Protect against typos.
14
15#define ASSERT_GLOBAL_STR(field) \
16 static_assert(offsetof(BigStr, field) == offsetof(GlobalStr<1>, field), \
17 "BigStr and GlobalStr should be consistent");
18ASSERT_GLOBAL_STR(len_);
19// NOTE: offsetof doesn't work with bitfields...
20// ASSERT_GLOBAL_STR(hash_);
21// ASSERT_GLOBAL_STR(is_hashed_);
22ASSERT_GLOBAL_STR(data_);
23
24static_assert(offsetof(Slab<int>, items_) ==
25 offsetof(GlobalSlab<int COMMA 1>, items_),
26 "Slab and GlobalSlab should be consistent");
27
28#define ASSERT_GLOBAL_LIST(field) \
29 static_assert( \
30 offsetof(List<int>, field) == offsetof(GlobalList<int COMMA 1>, field), \
31 "List and GlobalList should be consistent");
32
33ASSERT_GLOBAL_LIST(len_);
34ASSERT_GLOBAL_LIST(capacity_);
35ASSERT_GLOBAL_LIST(slab_);
36
37#define ASSERT_GLOBAL_DICT(field) \
38 static_assert(offsetof(Dict<int COMMA int>, field) == \
39 offsetof(GlobalDict<int COMMA int COMMA 1>, field), \
40 "Dict and GlobalDict should be consistent");
41
42ASSERT_GLOBAL_DICT(len_);
43ASSERT_GLOBAL_DICT(capacity_);
44ASSERT_GLOBAL_DICT(index_);
45ASSERT_GLOBAL_DICT(keys_);
46ASSERT_GLOBAL_DICT(values_);
47
48void ShowSlab(void* obj) {
49 auto slab = reinterpret_cast<Slab<void*>*>(obj);
50 auto* header = ObjHeader::FromObject(obj);
51 assert(header->heap_tag == HeapTag::Scanned);
52
53 int n = NUM_POINTERS(*header);
54 for (int i = 0; i < n; ++i) {
55 void* p = slab->items_[i];
56 if (p == nullptr) {
57 log("p = nullptr");
58 } else {
59 log("p = %p", p);
60 }
61 }
62}
63
64// Prints field masks for Dict and List
65TEST field_masks_test() {
66 auto L = NewList<int>();
67 StackRoots _roots({&L});
68
69 L->append(1);
70 log("List mask = %d", FIELD_MASK(*ObjHeader::FromObject(L)));
71
72 auto d = Alloc<Dict<BigStr*, int>>();
73 StackRoots _roots2({&d});
74
75 auto key = StrFromC("foo");
76 StackRoots _roots9({&key});
77 d->set(key, 3);
78
79 // oops this is bad? Because StrFromC() might move d in the middle of the
80 // expression! Gah!
81 // d->set(StrFromC("foo"), 3);
82
83 log("Dict mask = %d", FIELD_MASK(*ObjHeader::FromObject(d)));
84
85#if 0
86 ShowFixedChildren(L);
87 ShowFixedChildren(d);
88#endif
89
90 auto L2 = NewList<BigStr*>();
91 StackRoots _roots3({&L2});
92
93 auto s = StrFromC("foo");
94 StackRoots _roots4({&s});
95
96 L2->append(s);
97 L2->append(s);
98 ShowSlab(L2->slab_);
99
100 PASS();
101}
102
103TEST offsets_test() {
104 // Note: These will be different for 32 bit
105
106 ASSERT_EQ(offsetof(List<int>, slab_),
107 offsetof(GlobalList<int COMMA 1>, slab_));
108
109 if (sizeof(void*) == 8) {
110 // 0b 0000 0010
111 unsigned list_mask = List<int>::field_mask();
112 ASSERT_EQ_FMT(0x0002, list_mask, "0x%x");
113
114 // in binary: 0b 0000 0000 0001 1100
115 unsigned dict_mask = Dict<int COMMA int>::field_mask();
116 ASSERT_EQ_FMT(0x0001c, dict_mask, "0x%x");
117 }
118
119 PASS();
120}
121
122// TODO: the last one overflows
123int sizes[] = {0, 1, 2, 3, 4, 5, 8,
124 9, 12, 16, 256, 257, 1 << 30, (1 << 30) + 1};
125int nsizes = sizeof(sizes) / sizeof(sizes[0]);
126
127TEST roundup_test() {
128 for (int i = 0; i < nsizes; ++i) {
129 int n = sizes[i];
130 log("%d -> %d", n, RoundUp(n));
131 }
132
133 PASS();
134}
135
136TEST list_resize_policy_test() {
137 log("");
138 log("\tList<int>");
139 log("\tkNumItems2 %d", List<int>::kNumItems2);
140
141 auto small = NewList<int>();
142
143 for (int i = 0; i < 20; ++i) {
144 small->append(i);
145 int c = small->capacity_;
146 int slab_bytes = sizeof(ObjHeader) + c * sizeof(int);
147 log("desired %3d how many %3d slab bytes %3d", i, c, slab_bytes);
148 }
149
150 log("");
151 log("\tList<BigStr*>");
152 log("\tNumItems2 %d", List<BigStr*>::kNumItems2);
153
154 // Note: on 32-bit systems, this should be the same
155
156 auto big = NewList<BigStr*>();
157 for (int i = 0; i < 20; ++i) {
158 big->append(kEmptyString);
159 int c = big->capacity_;
160 int slab_bytes = sizeof(ObjHeader) + c * sizeof(BigStr*);
161 log("desired %3d how many %3d slab bytes %3d", i, c, slab_bytes);
162 }
163
164 PASS();
165}
166
167TEST dict_resize_policy_test() {
168 log("\tDict<int, int>");
169
170 log("\tkNumItems2 %d", Dict<int, int>::kNumItems2);
171 log("\tkHeaderFudge %d", Dict<int, int>::kHeaderFudge);
172
173 auto small = Alloc<Dict<int, int>>();
174
175 for (int i = 0; i < 20; ++i) {
176 small->set(i, i);
177 int c = small->capacity_;
178 int slab_k = sizeof(ObjHeader) + c * sizeof(int);
179 int slab_v = slab_k;
180
181 int x = small->index_len_;
182 int index_bytes = sizeof(ObjHeader) + x * sizeof(int);
183
184 log("desired %3d how many %3d k %3d v %3d index %3d %3d", i, c, slab_k,
185 slab_v, x, index_bytes);
186 }
187
188 log("");
189 log("\tDict<BigStr*, int>");
190
191 log("\tkNumItems2 %d", Dict<BigStr*, int>::kNumItems2);
192 log("\tkHeaderFudge %d", Dict<BigStr*, int>::kHeaderFudge);
193
194 auto big = Alloc<Dict<BigStr*, int>>();
195
196 for (int i = 0; i < 20; ++i) {
197 BigStr* key = str_repeat(StrFromC("x"), i);
198 big->set(key, i);
199 int c = big->capacity_;
200 int slab_k = sizeof(ObjHeader) + c * sizeof(BigStr*);
201 int slab_v = sizeof(ObjHeader) + c * sizeof(int);
202
203 int x = big->index_len_;
204 int index_bytes = sizeof(ObjHeader) + x * sizeof(int);
205
206 log("desired %3d how many %3d k %3d v %3d index %3d %3d", i, c, slab_k,
207 slab_v, x, index_bytes);
208 }
209
210 PASS();
211}
212
213class Point {
214 public:
215 Point(int x, int y) : x_(x), y_(y) {
216 }
217 int size() {
218 return x_ + y_;
219 }
220
221 static constexpr ObjHeader obj_header() {
222 return ObjHeader::ClassFixed(kZeroMask, sizeof(Point));
223 }
224
225 int x_;
226 int y_;
227};
228
229const int kLineMask = 0x3; // 0b0011
230
231class Line {
232 public:
233 Line() : begin_(nullptr), end_(nullptr) {
234 }
235
236 static constexpr ObjHeader obj_header() {
237 return ObjHeader::ClassFixed(kLineMask, sizeof(Line));
238 }
239
240 Point* begin_;
241 Point* end_;
242};
243
244TEST fixed_trace_test() {
245 gHeap.Collect();
246
247 ASSERT_NUM_LIVE_OBJS(0);
248
249 Point* p = nullptr;
250 Point* p2 = nullptr;
251 Line* line = nullptr;
252
253 StackRoots _roots({&p, &p2, &line});
254
255 p = Alloc<Point>(3, 4);
256 log("point size = %d", p->size());
257
258 ASSERT_NUM_LIVE_OBJS(1);
259
260 line = Alloc<Line>();
261
262 p2 = Alloc<Point>(5, 6);
263 line->begin_ = p;
264
265 // ROOTING ISSUE: This isn't valid? Uncomment and we'll see a crash in
266 // testgc mode.
267
268 // line->end_ = Alloc<Point>(5, 6);
269
270 // I think the problem is that the allocation causes the LHS to be invalid?
271
272 line->end_ = p2;
273
274 ASSERT_NUM_LIVE_OBJS(3);
275
276 gHeap.Collect();
277 ASSERT_NUM_LIVE_OBJS(3);
278
279 // remove last reference
280 line->end_ = nullptr;
281 p2 = nullptr;
282
283 gHeap.Collect();
284 ASSERT_NUM_LIVE_OBJS(2);
285
286 PASS();
287}
288
289GLOBAL_STR(str4, "egg");
290
291TEST slab_trace_test() {
292 gHeap.Collect();
293
294 ASSERT_NUM_LIVE_OBJS(0);
295
296 {
297 List<int>* ints = nullptr;
298 StackRoots _roots({&ints});
299 ints = Alloc<List<int>>();
300 ASSERT_NUM_LIVE_OBJS(1);
301
302 ints->append(3);
303 ASSERT_NUM_LIVE_OBJS(2);
304 } // ints goes out of scope
305
306 gHeap.Collect();
307 ASSERT_NUM_LIVE_OBJS(0);
308
309 List<BigStr*>* strings = nullptr;
310 BigStr* tmp = nullptr;
311 StackRoots _roots({&strings, &tmp});
312
313 // List of strings
314 strings = Alloc<List<BigStr*>>();
315 ASSERT_NUM_LIVE_OBJS(1);
316
317 // +2: slab and string
318 tmp = StrFromC("yo");
319 strings->append(tmp);
320 ASSERT_NUM_LIVE_OBJS(3);
321
322 // +1 string
323 tmp = StrFromC("bar");
324 strings->append(tmp);
325 ASSERT_NUM_LIVE_OBJS(4);
326
327 // -1: remove reference to "bar"
328 strings->set(1, nullptr);
329 tmp = nullptr;
330 gHeap.Collect();
331 ASSERT_NUM_LIVE_OBJS(3);
332
333 // -1: set to GLOBAL instance. Remove reference to "yo".
334 strings->set(0, str4);
335 gHeap.Collect();
336 ASSERT_NUM_LIVE_OBJS(2);
337
338 PASS();
339}
340
341TEST global_trace_test() {
342 gHeap.Collect();
343
344 BigStr* l4 = nullptr;
345 List<BigStr*>* strings = nullptr;
346
347 int num_roots;
348 num_roots = gHeap.roots_.size();
349 ASSERT_EQ_FMT(0, num_roots, "%d");
350
351 StackRoots _roots({&l4, &strings});
352
353 num_roots = gHeap.roots_.size();
354 ASSERT_EQ_FMT(2, num_roots, "%d");
355
356 // 2 roots, but no live objects
357 l4 = str4;
358 ASSERT_NUM_LIVE_OBJS(0);
359
360 gHeap.Collect();
361 ASSERT_NUM_LIVE_OBJS(0);
362
363 // Heap reference to global
364
365 strings = Alloc<List<BigStr*>>();
366 ASSERT_NUM_LIVE_OBJS(1);
367
368 // We now have the Slab too
369 strings->append(nullptr);
370 ASSERT_NUM_LIVE_OBJS(2);
371
372 // Global pointer doesn't increase the count
373 strings->set(1, str4);
374 ASSERT_NUM_LIVE_OBJS(2);
375
376 // Not after GC either
377 gHeap.Collect();
378 ASSERT_NUM_LIVE_OBJS(2);
379
380 PASS();
381}
382
383// 8 byte vtable, 8 byte ObjHeader, then member_
384class BaseObj {
385 public:
386 explicit BaseObj(uint32_t obj_len) {
387 }
388 BaseObj() : BaseObj(sizeof(BaseObj)) {
389 }
390
391 virtual int Method() {
392 return 3;
393 }
394
395 static constexpr ObjHeader obj_header() {
396 return ObjHeader::ClassFixed(kZeroMask, sizeof(BaseObj));
397 }
398
399 int member_ = 254;
400};
401
402// 8 byte vtable, 8 byte ObjHeader, then member_, then derived_member_
403class DerivedObj : public BaseObj {
404 public:
405 DerivedObj() : BaseObj(sizeof(DerivedObj)) {
406 }
407 virtual int Method() {
408 return 4;
409 }
410
411 static constexpr ObjHeader obj_header() {
412 return ObjHeader::ClassFixed(kZeroMask, sizeof(DerivedObj));
413 }
414
415 int derived_member_ = 253;
416 int derived_member2_ = 252;
417};
418
419void ShowObj(ObjHeader* obj) {
420 log("obj->heap_tag %d", obj->heap_tag);
421#if 0
422 log("obj->obj_len %d", obj->obj_len);
423#endif
424}
425
426TEST inheritance_test() {
427 gHeap.Collect();
428
429 ASSERT_NUM_LIVE_OBJS(0);
430
431 DerivedObj* obj = nullptr;
432 StackRoots _roots({&obj});
433
434 ASSERT_NUM_LIVE_OBJS(0);
435 gHeap.Collect();
436 ASSERT_NUM_LIVE_OBJS(0);
437
438 obj = Alloc<DerivedObj>();
439 ASSERT_EQ_FMT(253, obj->derived_member_, "%d");
440 ASSERT_NUM_LIVE_OBJS(1);
441
442 gHeap.Collect();
443 ASSERT_NUM_LIVE_OBJS(1);
444 ASSERT_EQ_FMT(253, obj->derived_member_, "%d");
445
446 PASS();
447}
448
449TEST stack_roots_test() {
450 BigStr* s = nullptr;
451 List<int>* L = nullptr;
452
453 gHeap.Collect();
454
455 ASSERT_EQ(0, gHeap.roots_.size());
456
457 StackRoots _roots({&s, &L});
458
459 s = StrFromC("foo");
460 L = NewList<int>();
461
462 int num_roots = gHeap.roots_.size();
463 ASSERT_EQ_FMT(2, num_roots, "%u");
464
465 PASS();
466}
467
468GREATEST_MAIN_DEFS();
469
470int main(int argc, char** argv) {
471 gHeap.Init();
472
473 GREATEST_MAIN_BEGIN();
474
475 RUN_TEST(field_masks_test);
476 RUN_TEST(offsets_test);
477
478 RUN_TEST(roundup_test);
479 RUN_TEST(list_resize_policy_test);
480 RUN_TEST(dict_resize_policy_test);
481
482 RUN_TEST(fixed_trace_test);
483 RUN_TEST(slab_trace_test);
484 RUN_TEST(global_trace_test);
485
486 RUN_TEST(inheritance_test);
487
488 RUN_TEST(stack_roots_test);
489
490 gHeap.CleanProcessExit();
491
492 GREATEST_MAIN_END();
493 return 0;
494}