OILS / mycpp / mark_sweep_heap.cc View on Github | oils.pub

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