mycpp-examples

Coverage Report

Created: 2022-07-15 02:23

/home/uke/oil/mycpp/gc_heap.cc
Line
Count
Source (jump to first uncovered line)
1
// gc_heap.cc
2
3
#include "gc_heap.h"
4
5
#include <sys/mman.h>  // mprotect()
6
7
using gc_heap::Heap;
8
using gc_heap::Local;
9
using gc_heap::Obj;
10
11
namespace gc_heap {
12
13
GLOBAL_STR(kEmptyString, "");
14
15
Heap gHeap;
16
17
// LayoutForwarded and LayoutFixed aren't real types.  You can cast arbitrary
18
// objs to them to access a HOMOGENEOUS REPRESENTATION useful for garbage
19
// collection.
20
21
class LayoutForwarded : public Obj {
22
 public:
23
  Obj* new_location;  // valid if and only if heap_tag_ == Tag::Forwarded
24
};
25
26
// for Tag::FixedSize
27
class LayoutFixed : public Obj {
28
 public:
29
  Obj* children_[16];  // only the entries denoted in field_mask will be valid
30
};
31
32
44
void Space::Init(int space_size) {
33
#if GC_PROTECT
34
  void* p = mmap(nullptr, space_size, PROT_READ | PROT_WRITE,
35
                 MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
36
  begin_ = static_cast<char*>(p);
37
#else
38
44
  begin_ = static_cast<char*>(malloc(space_size));
39
44
#endif
40
44
  size_ = space_size;
41
42
44
  Clear();
43
44
}
44
45
0
void Space::Free() {
46
#if GC_PROTECT
47
  Protect();  // There is no way of deallocating I guess
48
#else
49
0
  free(begin_);
50
0
#endif
51
0
}
52
53
#if GC_PROTECT
54
void Space::Protect() {
55
  int m = mprotect(begin_, size_, PROT_NONE);
56
  assert(m == 0);
57
}
58
59
void Space::Unprotect() {
60
  int m = mprotect(begin_, size_, PROT_READ | PROT_WRITE);
61
  assert(m == 0);
62
}
63
#endif
64
65
0
Obj* Heap::Relocate(Obj* obj, Obj* header) {
66
  // Move an object from one space to another.
67
  // If there's no vtable, then obj == header.  Otherwise header points to the
68
  // Obj header, which is right after the vtable.
69
70
0
  switch (header->heap_tag_) {
71
0
  case Tag::Forwarded: {
72
0
    auto f = reinterpret_cast<LayoutForwarded*>(header);
73
0
    return f->new_location;
74
0
  }
75
76
0
  case Tag::Global: {  // e.g. GlobalStr isn't copied or forwarded
77
    // log("*** GLOBAL POINTER");
78
0
    return obj;
79
0
  }
80
81
0
  default: {
82
0
    assert(header->heap_tag_ == Tag::Opaque ||
83
0
           header->heap_tag_ == Tag::FixedSize ||
84
0
           header->heap_tag_ == Tag::Scanned);
85
86
0
    auto new_location = reinterpret_cast<Obj*>(free_);
87
    // Note: if we wanted to save space on ASDL records, we could calculate
88
    // their length from the field_mask here.  How much would it slow down GC?
89
0
    int n = header->obj_len_;
90
0
    assert(n > 0);  // detect common problem
91
0
    memcpy(new_location, obj, n);
92
    // log("memcpy %d bytes from %p -> %p", n, obj, new_location);
93
#if 0
94
    if (obj->heap_tag_ == Tag::Opaque) {
95
      Str* s = static_cast<Str*>(obj);
96
      log("from = %s", s->data_);
97
      Str* s2 = static_cast<Str*>(new_location);
98
      log("to = %s", s2->data_);
99
    }
100
#endif
101
    // aligned() like Heap::Allocate()
102
0
    free_ += aligned(n);
103
104
#if GC_DEBUG
105
    num_live_objs_++;
106
#endif
107
108
0
    auto f = reinterpret_cast<LayoutForwarded*>(header);
109
0
    f->heap_tag_ = Tag::Forwarded;
110
0
    f->new_location = new_location;
111
0
    return new_location;
112
0
  }
113
0
  }  // switch
114
0
}
115
116
0
inline Obj* ObjHeader(Obj* obj) {
117
  // If we see a vtable pointer, return the Obj* header immediately following.
118
  // Otherwise just return Obj itself.
119
0
  return (obj->heap_tag_ & 0x1) == 0
120
0
             ? reinterpret_cast<Obj*>(reinterpret_cast<char*>(obj) +
121
0
                                      sizeof(void*))
122
0
             : obj;
123
0
}
124
125
0
void Heap::Collect() {
126
#if GC_DEBUG
127
  log("--> COLLECT with %d roots", roots_top_);
128
  num_collections_++;
129
#endif
130
131
#if GC_PROTECT
132
  to_space_.Unprotect();
133
#endif
134
135
  // If we grew one space, the other one has to catch up.
136
0
  if (to_space_.size_ < from_space_.size_) {
137
0
    to_space_.Free();
138
0
    to_space_.Init(from_space_.size_);
139
0
  }
140
141
0
  char* scan = to_space_.begin_;  // boundary between black and gray
142
0
  free_ = scan;                   // where to copy new entries
143
0
  limit_ = scan + to_space_.size_;
144
145
#if GC_DEBUG
146
  num_live_objs_ = 0;
147
#endif
148
149
0
  for (int i = 0; i < roots_top_; ++i) {
150
0
    Obj** handle = roots_[i];
151
0
    auto root = *handle;
152
#if GC_VERBOSE
153
    log("%d. handle %p", i, handle);
154
    log("    root %p", root);
155
#endif
156
157
0
    if (root) {  // could be nullptr
158
0
      auto header = ObjHeader(root);
159
160
      // This updates the underlying Str/List/Dict with a forwarding pointer,
161
      // i.e. for other objects that are pointing to it
162
0
      Obj* new_location = Relocate(root, header);
163
#if TODO_BUG
164
      for (int j = 0; j < roots_top_; ++j) {
165
        Obj** handle2 = roots_[j];
166
        auto root2 = *handle2;
167
        if (root2) {
168
          switch (root2->heap_tag_) {
169
          case Tag::Forwarded:
170
          case Tag::Global:
171
          case Tag::Opaque:
172
          case Tag::FixedSize:
173
          case Tag::Scanned:
174
            break;
175
          default:
176
            assert(0);  // NOTE(Jesse): Pretty sure this is InvalidCodePath();
177
          }
178
        }
179
      }
180
181
#endif
182
183
      // log("    new location %p", new_location);
184
185
      // This update is for the "double indirection", so future accesses to a
186
      // local variable use the new location
187
0
      *handle = new_location;
188
0
    }
189
0
  }
190
191
0
  while (scan < free_) {
192
0
    auto obj = reinterpret_cast<Obj*>(scan);
193
0
    auto header = ObjHeader(obj);
194
195
0
    switch (header->heap_tag_) {
196
0
    case Tag::FixedSize: {
197
0
      auto fixed = reinterpret_cast<LayoutFixed*>(header);
198
0
      int mask = fixed->field_mask_;
199
0
      for (int i = 0; i < 16; ++i) {
200
0
        if (mask & (1 << i)) {
201
0
          Obj* child = fixed->children_[i];
202
          // log("i = %d, p = %p, heap_tag = %d", i, child, child->heap_tag_);
203
0
          if (child) {
204
0
            auto child_header = ObjHeader(child);
205
            // log("  fixed: child %d from %p", i, child);
206
0
            fixed->children_[i] = Relocate(child, child_header);
207
            // log("  to %p", fixed->children_[i]);
208
0
          }
209
0
        }
210
0
      }
211
0
      break;
212
0
    }
213
0
    case Tag::Scanned: {
214
0
      assert(header == obj);  // no inheritance
215
0
      auto slab = reinterpret_cast<Slab<void*>*>(header);
216
0
      int n = (slab->obj_len_ - kSlabHeaderSize) / sizeof(void*);
217
0
      for (int i = 0; i < n; ++i) {
218
0
        Obj* child = reinterpret_cast<Obj*>(slab->items_[i]);
219
0
        if (child) {  // note: List<> may have nullptr; Dict is sparse
220
0
          auto child_header = ObjHeader(child);
221
0
          slab->items_[i] = Relocate(child, child_header);
222
0
        }
223
0
      }
224
0
      break;
225
0
    }
226
0
    default: {
227
0
      assert(header->heap_tag_ == Tag::Forwarded ||
228
0
             header->heap_tag_ == Tag::Global ||
229
0
             header->heap_tag_ == Tag::Opaque);
230
0
    }
231
232
      // other tags like Tag::Opaque have no children
233
0
    }
234
    // aligned() like Heap::Allocate()
235
0
    scan += aligned(header->obj_len_);
236
0
  }
237
238
  // We just copied everything from_space_ -> to_space_.  Maintain
239
  // invariant of the space we will allocate from next time.
240
0
  from_space_.Clear();
241
#if GC_PROTECT
242
  from_space_.Protect();
243
  // log("begin = %x", *from_space_.begin_);
244
#endif
245
246
0
  Swap();
247
248
#if GC_VERBOSE
249
  Report();
250
#endif
251
0
}
252
253
241
bool str_equals(Str* left, Str* right) {
254
  // Fast path for identical strings.  String deduplication during GC could
255
  // make this more likely.  String interning could guarantee it, allowing us
256
  // to remove memcmp().
257
241
  if (left == right) {
258
0
    return true;
259
0
  }
260
  // obj_len_ equal implies string lengths are equal
261
241
  if (left->obj_len_ == right->obj_len_) {
262
238
    return memcmp(left->data_, right->data_, len(left)) == 0;
263
238
  }
264
3
  return false;
265
241
}
266
267
4
bool maybe_str_equals(Str* left, Str* right) {
268
4
  if (left && right) {
269
2
    return str_equals(left, right);
270
2
  }
271
272
2
  if (!left && !right) {
273
0
    return true;  // None == None
274
0
  }
275
276
2
  return false;  // one is None and one is a Str*
277
2
}
278
279
#if GC_DEBUG
280
void ShowFixedChildren(Obj* obj) {
281
  assert(obj->heap_tag_ == Tag::FixedSize);
282
  auto fixed = reinterpret_cast<LayoutFixed*>(obj);
283
  log("MASK:");
284
285
  // Note: can this be optimized with the equivalent x & (x-1) trick?
286
  // We need the index
287
  // There is a de Brjuin sequence solution?
288
  // https://stackoverflow.com/questions/757059/position-of-least-significant-bit-that-is-set
289
290
  int mask = fixed->field_mask_;
291
  for (int i = 0; i < 16; ++i) {
292
    if (mask & (1 << i)) {
293
      Obj* child = fixed->children_[i];
294
      if (child) {
295
        // make sure we get Tag::Opaque, Tag::Scanned, etc.
296
        log("i = %d, p = %p, heap_tag = %d", i, child, child->heap_tag_);
297
      }
298
    }
299
  }
300
}
301
#endif
302
303
}  // namespace gc_heap