cpp

Coverage Report

Created: 2022-11-10 11:34

/home/andy/git/oilshell/oil/mycpp/marksweep_heap.cc
Line
Count
Source (jump to first uncovered line)
1
#include "mycpp/runtime.h"
2
3
// Start of garbage collection.  We have a circular dependency here because I
4
// don't want some kind of STL iterator.
5
0
void RootSet::MarkRoots(MarkSweepHeap* heap) {
6
0
  for (int i = 0; i < num_frames_; ++i) {
7
0
    const std::vector<Obj*>& frame = stack_[i];
8
0
    int n = frame.size();
9
0
    for (int j = 0; j < n; ++j) {
10
      // TODO: would be nice to do non-recursive marking
11
0
      heap->MarkObjects(frame[j]);
12
0
    }
13
0
  }
14
0
}
15
16
39
void MarkSweepHeap::Init() {
17
39
  Init(1000);  // collect at 1000 objects in tests
18
39
}
19
20
39
void MarkSweepHeap::Init(int gc_threshold) {
21
39
  gc_threshold_ = gc_threshold;
22
23
39
  char* e = getenv("OIL_GC_THRESHOLD");
24
39
  if (e) {
25
0
    int result;
26
0
    if (StringToInteger(e, strlen(e), 10, &result)) {
27
      // Override collection threshold
28
0
      gc_threshold_ = result;
29
0
    }
30
0
  }
31
32
39
  live_objs_.reserve(KiB(10));
33
39
  roots_.reserve(KiB(1));  // prevent resizing in common case
34
39
}
35
36
3
void MarkSweepHeap::Report() {
37
3
  log("  num allocated   = %10d", num_allocated_);
38
3
  log("bytes allocated   = %10d", bytes_allocated_);
39
3
  log("  max live        = %10d", max_live_);
40
3
  log("  num live        = %10d", num_live_);
41
3
  log("  num collections = %10d", num_collections_);
42
3
  log("");
43
3
  log("roots capacity    = %10d", roots_.capacity());
44
3
  log(" objs capacity    = %10d", live_objs_.capacity());
45
3
}
46
47
#if defined(MALLOC_LEAK)
48
49
// for testing performance
50
void* MarkSweepHeap::Allocate(size_t num_bytes) {
51
  return calloc(num_bytes, 1);
52
}
53
54
void* MarkSweepHeap::Reallocate(void* p, size_t num_bytes) {
55
  return realloc(p, num_bytes);
56
}
57
58
#elif defined(BUMP_LEAK)
59
60
#else
61
62
4.53k
void* MarkSweepHeap::Allocate(size_t num_bytes) {
63
  // log("Allocate %d", num_bytes);
64
65
  // Maybe collect BEFORE allocation, because the new object won't be rooted
66
  #if GC_EVERY_ALLOC
67
  Collect();
68
  #else
69
4.53k
  if (num_live_ > gc_threshold_) {
70
2
    Collect();
71
2
  }
72
4.53k
  #endif
73
74
  // num_live_ UPDATED after possible collection
75
4.53k
  if (num_live_ > gc_threshold_) {
76
0
    gc_threshold_ = num_live_ * 2;
77
0
  }
78
79
  //
80
  // Allocate and update stats
81
  //
82
83
4.53k
  void* result = calloc(num_bytes, 1);
84
4.53k
  assert(result);
85
86
0
  live_objs_.push_back(result);
87
88
4.53k
  num_live_++;
89
4.53k
  num_allocated_++;
90
4.53k
  bytes_allocated_ += num_bytes;
91
92
  // Allocate() is special: we use RootInCurrentFrame because it's a LEAF, and
93
  // this function doesn't have RootingScope to do PushScope/PopScope
94
  #if RET_VAL_ROOTING
95
  gHeap.RootInCurrentFrame(static_cast<Obj*>(result));
96
  static_cast<Obj*>(result)->heap_tag_ = Tag::Opaque;  // it is opaque to start!
97
  #endif
98
99
4.53k
  return result;
100
4.53k
}
101
102
// Right now, this doesn't affect the GC policy
103
0
void* MarkSweepHeap::Reallocate(void* p, size_t num_bytes) {
104
0
  return realloc(p, num_bytes);
105
0
}
106
107
#endif  // MALLOC_LEAK
108
109
249
void MarkSweepHeap::MarkObjects(Obj* obj) {
110
249
  bool is_marked = marked_.find(obj) != marked_.end();
111
249
  if (is_marked) {
112
62
    return;
113
62
  }
114
115
187
  marked_.insert(static_cast<void*>(obj));
116
117
187
  auto header = ObjHeader(obj);
118
187
  switch (header->heap_tag_) {
119
92
  case Tag::FixedSize: {
120
92
    auto fixed = reinterpret_cast<LayoutFixed*>(header);
121
92
    int mask = fixed->field_mask_;
122
123
    // TODO(Jesse): Put the 16 in a #define
124
1.56k
    for (int i = 0; i < 16; ++i) {
125
1.47k
      if (mask & (1 << i)) {
126
140
        Obj* child = fixed->children_[i];
127
140
        if (child) {
128
129
          MarkObjects(child);
129
129
        }
130
140
      }
131
1.47k
    }
132
133
92
    break;
134
0
  }
135
136
12
  case Tag::Scanned: {
137
12
    assert(header == obj);
138
139
0
    auto slab = reinterpret_cast<Slab<void*>*>(header);
140
141
    // TODO(Jesse): Give this a name
142
12
    int n = (slab->obj_len_ - kSlabHeaderSize) / sizeof(void*);
143
144
104
    for (int i = 0; i < n; ++i) {
145
92
      Obj* child = reinterpret_cast<Obj*>(slab->items_[i]);
146
92
      if (child) {
147
31
        MarkObjects(child);
148
31
      }
149
92
    }
150
151
12
    break;
152
0
  }
153
154
83
  default: {
155
83
    assert(header->heap_tag_ == Tag::Forwarded ||
156
83
           header->heap_tag_ == Tag::Global ||
157
83
           header->heap_tag_ == Tag::Opaque);
158
83
  }
159
160
    // other tags like Tag::Opaque have no children
161
187
  }
162
187
}
163
164
62
void MarkSweepHeap::Sweep() {
165
62
  int last_live_index = 0;
166
62
  int num_objs = live_objs_.size();
167
4.76k
  for (int i = 0; i < num_objs; ++i) {
168
4.69k
    void* obj = live_objs_[i];
169
4.69k
    assert(obj);  // malloc() shouldn't have returned nullptr
170
171
0
    bool is_live = marked_.find(obj) != marked_.end();
172
4.69k
    if (is_live) {
173
167
      live_objs_[last_live_index++] = obj;
174
4.53k
    } else {
175
4.53k
      free(obj);
176
4.53k
      num_live_--;
177
4.53k
    }
178
4.69k
  }
179
62
  live_objs_.resize(last_live_index);  // remove dangling objects
180
62
  marked_.clear();
181
182
62
  num_collections_++;
183
62
  max_live_ = std::max(max_live_, num_live_);
184
62
}
185
186
62
int MarkSweepHeap::Collect() {
187
#if RET_VAL_ROOTING
188
189
  #ifdef GC_VERBOSE
190
  log("  Collect with %d roots and %d frames", NumRoots(), NumFrames());
191
  #endif
192
193
  root_set_.MarkRoots(this);
194
#else
195
62
  int num_roots = roots_.size();
196
197
  #ifdef GC_VERBOSE
198
  log("  Collect with %d roots, %d live", num_roots, num_live_);
199
  #endif
200
201
185
  for (int i = 0; i < num_roots; ++i) {
202
    // Note: When we abandon the Cheney collector, we no longer need double
203
    // pointers
204
123
    Obj* root = *(roots_[i]);
205
206
123
    if (root) {
207
89
      MarkObjects(root);
208
89
    }
209
123
  }
210
62
#endif
211
212
62
  Sweep();
213
#ifdef GC_VERBOSE
214
  log("  %d live after sweep", num_live_);
215
#endif
216
217
62
  return num_live_;  // for unit tests only
218
62
}
219
220
// Cleanup at the end of main() to remain ASAN-safe
221
31
void MarkSweepHeap::DoProcessExit(bool fast_exit) {
222
31
  char* e = getenv("OIL_GC_ON_EXIT");
223
224
31
  if (fast_exit) {
225
    // don't collect by default; OIL_GC_ON_EXIT=1 overrides
226
0
    if (e && strcmp(e, "1") == 0) {
227
0
      root_set_.PopScope();
228
0
      Collect();
229
0
    }
230
31
  } else {
231
    // collect by default; OIL_GC_ON_EXIT=0 overrides
232
31
    if (e && strcmp(e, "0") == 0) {
233
0
      ;
234
31
    } else {
235
31
      root_set_.PopScope();
236
31
      Collect();
237
31
    }
238
31
  }
239
240
31
  e = getenv("OIL_GC_STATS");
241
31
  if (e && strlen(e)) {  // env var set and non-empty
242
0
    Report();
243
0
  }
244
31
}
245
246
31
void MarkSweepHeap::CleanProcessExit() {
247
31
  DoProcessExit(false);  // not fast_exit
248
31
}
249
250
// for the main binary
251
0
void MarkSweepHeap::FastProcessExit() {
252
0
  DoProcessExit(true);
253
0
}
254
255
#if defined(MARK_SWEEP) && !defined(BUMP_LEAK)
256
MarkSweepHeap gHeap;
257
#endif