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

451 lines, 278 significant
1#include "mycpp/mark_sweep_heap.h"
2
3#include <inttypes.h> // PRId64
4#include <stdlib.h> // getenv()
5#include <string.h> // strlen()
6#include <sys/time.h> // gettimeofday()
7#include <time.h> // clock_gettime(), CLOCK_PROCESS_CPUTIME_ID
8#include <unistd.h> // STDERR_FILENO
9
10#include "_build/detected-cpp-config.h" // for GC_TIMING
11#include "mycpp/gc_builtins.h" // StringToInt()
12#include "mycpp/gc_slab.h"
13
14// TODO: Remove this guard when we have separate binaries
15#if MARK_SWEEP
16
17void MarkSweepHeap::Init() {
18 Init(1000); // collect at 1000 objects in tests
19}
20
21void MarkSweepHeap::Init(int gc_threshold) {
22 gc_threshold_ = gc_threshold;
23
24 char* e;
25 e = getenv("OILS_GC_THRESHOLD");
26 if (e) {
27 int result;
28 if (StringToInt(e, strlen(e), 10, &result)) {
29 // Override collection threshold
30 gc_threshold_ = result;
31 }
32 }
33
34 // only for developers
35 e = getenv("_OILS_GC_VERBOSE");
36 if (e && strcmp(e, "1") == 0) {
37 gc_verbose_ = true;
38 }
39
40 live_objs_.reserve(KiB(10));
41 roots_.reserve(KiB(1)); // prevent resizing in common case
42}
43
44int MarkSweepHeap::MaybeCollect() {
45 // Maybe collect BEFORE allocation, because the new object won't be rooted
46 #if GC_ALWAYS
47 int result = Collect();
48 #else
49 int result = -1;
50 if (num_live() > gc_threshold_) {
51 result = Collect();
52 }
53 #endif
54
55 num_gc_points_++; // this is a manual collection point
56 return result;
57}
58
59 #if defined(BUMP_SMALL)
60 #include "mycpp/bump_leak_heap.h"
61
62BumpLeakHeap gBumpLeak;
63 #endif
64
65// Allocate and update stats
66// TODO: Make this interface nicer.
67void* MarkSweepHeap::Allocate(size_t num_bytes, int* obj_id, int* pool_id) {
68 // log("Allocate %d", num_bytes);
69 #ifndef NO_POOL_ALLOC
70 if (num_bytes <= pool1_.kMaxObjSize) {
71 *pool_id = 1;
72 return pool1_.Allocate(obj_id);
73 }
74 if (num_bytes <= pool2_.kMaxObjSize) {
75 *pool_id = 2;
76 return pool2_.Allocate(obj_id);
77 }
78 if (num_bytes <= pool3_.kMaxObjSize) {
79 *pool_id = 3;
80 return pool3_.Allocate(obj_id);
81 }
82 *pool_id = 0; // malloc(), not a pool
83 #endif
84
85 // Does the pool allocator approximate a bump allocator? Use pool2_
86 // threshold of 48 bytes.
87 // These only work with GC off -- OILS_GC_THRESHOLD=[big]
88 #ifdef BUMP_SMALL
89 if (num_bytes <= 48) {
90 return gBumpLeak.Allocate(num_bytes);
91 }
92 #endif
93
94 if (to_free_.empty()) {
95 // Use higher object IDs
96 *obj_id = greatest_obj_id_;
97 greatest_obj_id_++;
98
99 // This check is ON in release mode
100 CHECK(greatest_obj_id_ <= kMaxObjId);
101 } else {
102 ObjHeader* dead = to_free_.back();
103 to_free_.pop_back();
104
105 *obj_id = dead->obj_id; // reuse the dead object's ID
106
107 free(dead);
108 }
109
110 void* result = malloc(num_bytes);
111 DCHECK(result != nullptr);
112
113 live_objs_.push_back(static_cast<ObjHeader*>(result));
114
115 num_live_++;
116 num_allocated_++;
117 bytes_allocated_ += num_bytes;
118
119 return result;
120}
121
122 #if 0
123void* MarkSweepHeap::Reallocate(void* p, size_t num_bytes) {
124 FAIL(kNotImplemented);
125 // This causes a double-free in the GC!
126 // return realloc(p, num_bytes);
127}
128 #endif
129
130// "Leaf" for marking / TraceChildren
131//
132// - Abort if nullptr
133// - Find the header (get rid of this when remove ObjHeader member)
134// - Tag::{Opaque,FixedSized,Scanned} have their mark bits set
135// - Tag::{FixedSize,Scanned} are also pushed on the gray stack
136
137void MarkSweepHeap::MaybeMarkAndPush(RawObject* obj) {
138 ObjHeader* header = ObjHeader::FromObject(obj);
139 if (header->heap_tag == HeapTag::Global) { // don't mark or push
140 return;
141 }
142
143 int obj_id = header->obj_id;
144 #ifndef NO_POOL_ALLOC
145 if (header->pool_id == 1) {
146 if (pool1_.IsMarked(obj_id)) {
147 return;
148 }
149 pool1_.Mark(obj_id);
150 } else if (header->pool_id == 2) {
151 if (pool2_.IsMarked(obj_id)) {
152 return;
153 }
154 pool2_.Mark(obj_id);
155 } else if (header->pool_id == 3) {
156 if (pool3_.IsMarked(obj_id)) {
157 return;
158 }
159 pool3_.Mark(obj_id);
160 } else
161 #endif
162 {
163 if (mark_set_.IsMarked(obj_id)) {
164 return;
165 }
166 mark_set_.Mark(obj_id);
167 }
168
169 switch (header->heap_tag) {
170 case HeapTag::Opaque: // e.g. strings have no children
171 break;
172
173 case HeapTag::Scanned: // these 2 types have children
174 case HeapTag::FixedSize:
175 gray_stack_.push_back(header); // Push the header, not the object!
176 break;
177
178 default:
179 FAIL(kShouldNotGetHere);
180 }
181}
182
183void MarkSweepHeap::TraceChildren() {
184 while (!gray_stack_.empty()) {
185 ObjHeader* header = gray_stack_.back();
186 gray_stack_.pop_back();
187
188 switch (header->heap_tag) {
189 case HeapTag::FixedSize: {
190 auto fixed = reinterpret_cast<LayoutFixed*>(header->ObjectAddress());
191 int mask = FIELD_MASK(*header);
192
193 for (int i = 0; i < kFieldMaskBits; ++i) {
194 if (mask & (1 << i)) {
195 RawObject* child = fixed->children_[i];
196 if (child) {
197 MaybeMarkAndPush(child);
198 }
199 }
200 }
201 break;
202 }
203
204 case HeapTag::Scanned: {
205 auto slab = reinterpret_cast<Slab<RawObject*>*>(header->ObjectAddress());
206
207 int n = NUM_POINTERS(*header);
208 for (int i = 0; i < n; ++i) {
209 RawObject* child = slab->items_[i];
210 if (child) {
211 MaybeMarkAndPush(child);
212 }
213 }
214 break;
215 }
216 default:
217 // Only FixedSize and Scanned are pushed
218 FAIL(kShouldNotGetHere);
219 }
220 }
221}
222
223void MarkSweepHeap::Sweep() {
224 #ifndef NO_POOL_ALLOC
225 pool1_.Sweep();
226 pool2_.Sweep();
227 pool3_.Sweep();
228 #endif
229
230 int last_live_index = 0;
231 int num_objs = live_objs_.size();
232 for (int i = 0; i < num_objs; ++i) {
233 ObjHeader* obj = live_objs_[i];
234 DCHECK(obj); // malloc() shouldn't have returned nullptr
235
236 bool is_live = mark_set_.IsMarked(obj->obj_id);
237
238 // Compact live_objs_ and populate to_free_. Note: doing the reverse could
239 // be more efficient when many objects are dead.
240 if (is_live) {
241 live_objs_[last_live_index++] = obj;
242 } else {
243 to_free_.push_back(obj);
244 // free(obj);
245 num_live_--;
246 }
247 }
248 live_objs_.resize(last_live_index); // remove dangling objects
249
250 num_collections_++;
251 max_survived_ = std::max(max_survived_, num_live());
252}
253
254int MarkSweepHeap::Collect() {
255 #ifdef GC_TIMING
256 struct timespec start, end;
257 if (clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start) < 0) {
258 FAIL("clock_gettime failed");
259 }
260 #endif
261
262 int num_roots = roots_.size();
263 int num_globals = global_roots_.size();
264
265 if (gc_verbose_) {
266 log("");
267 log("%2d. GC with %d roots (%d global) and %d live objects",
268 num_collections_, num_roots + num_globals, num_globals, num_live());
269 }
270
271 // Resize it
272 mark_set_.ReInit(greatest_obj_id_);
273 #ifndef NO_POOL_ALLOC
274 pool1_.PrepareForGc();
275 pool2_.PrepareForGc();
276 pool3_.PrepareForGc();
277 #endif
278
279 // Mark roots.
280 // Note: It might be nice to get rid of double pointers
281 for (int i = 0; i < num_roots; ++i) {
282 RawObject* root = *(roots_[i]);
283 if (root) {
284 MaybeMarkAndPush(root);
285 }
286 }
287
288 for (int i = 0; i < num_globals; ++i) {
289 RawObject* root = global_roots_[i];
290 if (root) {
291 MaybeMarkAndPush(root);
292 }
293 }
294
295 // Traverse object graph.
296 TraceChildren();
297
298 Sweep();
299
300 if (gc_verbose_) {
301 log(" %d live after sweep", num_live());
302 }
303
304 // We know how many are live. If the number of objects is close to the
305 // threshold (above 75%), then set the threshold to 2 times the number of
306 // live objects. This is an ad hoc policy that removes observed "thrashing"
307 // -- being at 99% of the threshold and doing FUTILE mark and sweep.
308
309 int water_mark = (gc_threshold_ * 3) / 4;
310 if (num_live() > water_mark) {
311 gc_threshold_ = num_live() * 2;
312 num_growths_++;
313 if (gc_verbose_) {
314 log(" exceeded %d live objects; gc_threshold set to %d", water_mark,
315 gc_threshold_);
316 }
317 }
318
319 #ifdef GC_TIMING
320 if (clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end) < 0) {
321 FAIL("clock_gettime failed");
322 }
323
324 double start_secs = start.tv_sec + start.tv_nsec / 1e9;
325 double end_secs = end.tv_sec + end.tv_nsec / 1e9;
326 double gc_millis = (end_secs - start_secs) * 1000.0;
327
328 if (gc_verbose_) {
329 log(" %.1f ms GC", gc_millis);
330 }
331
332 total_gc_millis_ += gc_millis;
333 if (gc_millis > max_gc_millis_) {
334 max_gc_millis_ = gc_millis;
335 }
336 #endif
337
338 return num_live(); // for unit tests only
339}
340
341void MarkSweepHeap::PrintStats(int fd) {
342 dprintf(fd, " num live = %10d\n", num_live());
343 // max survived_ can be less than num_live(), because leave off the last GC
344 dprintf(fd, " max survived = %10d\n", max_survived_);
345 dprintf(fd, "\n");
346
347 #ifndef NO_POOL_ALLOC
348 dprintf(fd, " num allocated = %10d\n",
349 num_allocated_ + pool1_.num_allocated() + pool2_.num_allocated() + pool3_.num_allocated());
350 dprintf(fd, " num in heap = %10d\n", num_allocated_);
351 #else
352 dprintf(fd, " num allocated = %10d\n", num_allocated_);
353 #endif
354
355 #ifndef NO_POOL_ALLOC
356 dprintf(fd, " num in pool 1 = %10d\n", pool1_.num_allocated());
357 dprintf(fd, " num in pool 2 = %10d\n", pool2_.num_allocated());
358 dprintf(fd, " num in pool 3 = %10d\n", pool3_.num_allocated());
359 dprintf(
360 fd, "bytes allocated = %10" PRId64 "\n",
361 bytes_allocated_ + pool1_.bytes_allocated() + pool2_.bytes_allocated() + pool3_.bytes_allocated());
362 #else
363 dprintf(fd, "bytes allocated = %10" PRId64 "\n", bytes_allocated_);
364 #endif
365
366 dprintf(fd, "\n");
367 dprintf(fd, " num gc points = %10d\n", num_gc_points_);
368 dprintf(fd, " num collections = %10d\n", num_collections_);
369 dprintf(fd, "\n");
370 dprintf(fd, " gc threshold = %10d\n", gc_threshold_);
371 dprintf(fd, " num growths = %10d\n", num_growths_);
372 dprintf(fd, "\n");
373 dprintf(fd, " max gc millis = %10.1f\n", max_gc_millis_);
374 dprintf(fd, "total gc millis = %10.1f\n", total_gc_millis_);
375 dprintf(fd, "\n");
376 dprintf(fd, "roots capacity = %10d\n",
377 static_cast<int>(roots_.capacity()));
378 dprintf(fd, " objs capacity = %10d\n",
379 static_cast<int>(live_objs_.capacity()));
380}
381
382// Cleanup at the end of main() to remain ASAN-safe
383void MarkSweepHeap::MaybePrintStats() {
384 int stats_fd = -1;
385 char* e = getenv("OILS_GC_STATS");
386 if (e && strlen(e)) { // env var set and non-empty
387 stats_fd = STDERR_FILENO;
388 } else {
389 // A raw file descriptor lets benchmarks extract stats even if the script
390 // writes to stdout and stderr. Shells can't use open() without potential
391 // conflicts.
392
393 e = getenv("OILS_GC_STATS_FD");
394 if (e && strlen(e)) {
395 // Try setting 'stats_fd'. If there's an error, it will be unchanged, and
396 // we don't PrintStats();
397 StringToInt(e, strlen(e), 10, &stats_fd);
398 }
399 }
400
401 if (stats_fd != -1) {
402 PrintStats(stats_fd);
403 }
404}
405
406void MarkSweepHeap::FreeEverything() {
407 roots_.clear();
408 global_roots_.clear();
409
410 Collect();
411
412 // Collect() told us what to free()
413 for (auto obj : to_free_) {
414 free(obj);
415 }
416 #ifndef NO_POOL_ALLOC
417 pool1_.Free();
418 pool2_.Free();
419 pool3_.Free();
420 #endif
421}
422
423void MarkSweepHeap::CleanProcessExit() {
424 char* e = getenv("OILS_GC_ON_EXIT");
425 // collect by default; OILS_GC_ON_EXIT=0 overrides
426 if (e && strcmp(e, "0") == 0) {
427 ;
428 } else {
429 FreeEverything();
430 }
431 MaybePrintStats();
432}
433
434// for the main binary
435void MarkSweepHeap::ProcessExit() {
436 #ifdef CLEAN_PROCESS_EXIT
437 FreeEverything();
438 #else
439 char* e = getenv("OILS_GC_ON_EXIT");
440 // don't collect by default; OILS_GC_ON_EXIT=1 overrides
441 if (e && strcmp(e, "1") == 0) {
442 FreeEverything();
443 }
444 #endif
445
446 MaybePrintStats();
447}
448
449MarkSweepHeap gHeap;
450
451#endif // MARK_SWEEP