/home/andy/git/oilshell/oil/mycpp/gc_heap.cc

Source (jump to first uncovered line)
// gc_heap.cc

#include <sys/mman.h>  // mprotect()

#include "mycpp/gc_types.h"

using gc_heap::Heap;
using gc_heap::Local;
using gc_heap::Obj;

namespace gc_heap {

GLOBAL_STR(kEmptyString, "");

Heap gHeap;

// LayoutForwarded and LayoutFixed aren't real types.  You can cast arbitrary
// objs to them to access a HOMOGENEOUS REPRESENTATION useful for garbage
// collection.

class LayoutForwarded : public Obj {
 public:
  Obj* new_location;  // valid if and only if heap_tag_ == Tag::Forwarded
};

// for Tag::FixedSize
class LayoutFixed : public Obj {
 public:
  Obj* children_[16];  // only the entries denoted in field_mask will be valid
};

void Space::Init(int space_size) {
#if GC_PROTECT
  void* p = mmap(nullptr, space_size, PROT_READ | PROT_WRITE,
                 MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
  begin_ = static_cast<char*>(p);
#else
  begin_ = static_cast<char*>(malloc(space_size));
#endif
  size_ = space_size;

  Clear();
}

void Space::Free() {
#if GC_PROTECT
  Protect();  // There is no way of deallocating I guess
#else
  free(begin_);
#endif
}

#if GC_PROTECT
void Space::Protect() {
  int m = mprotect(begin_, size_, PROT_NONE);
  assert(m == 0);
}

void Space::Unprotect() {
  int m = mprotect(begin_, size_, PROT_READ | PROT_WRITE);
  assert(m == 0);
}
#endif

Obj* Heap::Relocate(Obj* obj, Obj* header) {
  // Move an object from one space to another.
  // If there's no vtable, then obj == header.  Otherwise header points to the
  // Obj header, which is right after the vtable.

  switch (header->heap_tag_) {
  case Tag::Forwarded: {
    auto f = reinterpret_cast<LayoutForwarded*>(header);
    return f->new_location;
  }

  case Tag::Global: {  // e.g. GlobalStr isn't copied or forwarded
    // log("*** GLOBAL POINTER");
    return obj;
  }

  default: {
    assert(header->heap_tag_ == Tag::Opaque ||
           header->heap_tag_ == Tag::FixedSize ||
           header->heap_tag_ == Tag::Scanned);

    auto new_location = reinterpret_cast<Obj*>(free_);
    // Note: if we wanted to save space on ASDL records, we could calculate
    // their length from the field_mask here.  How much would it slow down GC?
    int n = header->obj_len_;
    assert(n > 0);  // detect common problem
    memcpy(new_location, obj, n);
    // log("memcpy %d bytes from %p -> %p", n, obj, new_location);
#if 0
    if (obj->heap_tag_ == Tag::Opaque) {
      Str* s = static_cast<Str*>(obj);
      log("from = %s", s->data_);
      Str* s2 = static_cast<Str*>(new_location);
      log("to = %s", s2->data_);
    }
#endif
    // aligned() like Heap::Allocate()
    free_ += aligned(n);

#if GC_STATS
    num_live_objs_++;
#endif

    auto f = reinterpret_cast<LayoutForwarded*>(header);
    f->heap_tag_ = Tag::Forwarded;
    f->new_location = new_location;
    return new_location;
  }
  }  // switch
}

inline Obj* ObjHeader(Obj* obj) {
  // If we see a vtable pointer, return the Obj* header immediately following.
  // Otherwise just return Obj itself.
  return (obj->heap_tag_ & 0x1) == 0
             ? reinterpret_cast<Obj*>(reinterpret_cast<char*>(obj) +
                                      sizeof(void*))
             : obj;
}

void Heap::Collect() {
#if GC_STATS
  log("--> COLLECT with %d roots", roots_top_);
  num_collections_++;
#endif

#if GC_PROTECT
  to_space_.Unprotect();
#endif

  // If we grew one space, the other one has to catch up.
  if (to_space_.size_ < from_space_.size_) {
    to_space_.Free();
    to_space_.Init(from_space_.size_);
  }

  char* scan = to_space_.begin_;  // boundary between black and gray
  free_ = scan;                   // where to copy new entries
  limit_ = scan + to_space_.size_;

#if GC_STATS
  num_live_objs_ = 0;
#endif

  for (int i = 0; i < roots_top_; ++i) {
    Obj** handle = roots_[i];
    auto root = *handle;
#if GC_VERBOSE
    log("%d. handle %p", i, handle);
    log("    root %p", root);
#endif

    if (root) {  // could be nullptr
      auto header = ObjHeader(root);

      // This updates the underlying Str/List/Dict with a forwarding pointer,
      // i.e. for other objects that are pointing to it
      Obj* new_location = Relocate(root, header);
#if TODO_BUG
      for (int j = 0; j < roots_top_; ++j) {
        Obj** handle2 = roots_[j];
        auto root2 = *handle2;
        if (root2) {
          switch (root2->heap_tag_) {
          case Tag::Forwarded:
          case Tag::Global:
          case Tag::Opaque:
          case Tag::FixedSize:
          case Tag::Scanned:
            break;
          default:
            assert(0);  // NOTE(Jesse): Pretty sure this is InvalidCodePath();
          }
        }
      }

#endif

      // log("    new location %p", new_location);

      // This update is for the "double indirection", so future accesses to a
      // local variable use the new location
      *handle = new_location;
    }
  }

  while (scan < free_) {
    auto obj = reinterpret_cast<Obj*>(scan);
    auto header = ObjHeader(obj);

    switch (header->heap_tag_) {
    case Tag::FixedSize: {
      auto fixed = reinterpret_cast<LayoutFixed*>(header);
      int mask = fixed->field_mask_;
      for (int i = 0; i < 16; ++i) {
        if (mask & (1 << i)) {
          Obj* child = fixed->children_[i];
          // log("i = %d, p = %p, heap_tag = %d", i, child, child->heap_tag_);
          if (child) {
            auto child_header = ObjHeader(child);
            // log("  fixed: child %d from %p", i, child);
            fixed->children_[i] = Relocate(child, child_header);
            // log("  to %p", fixed->children_[i]);
          }
        }
      }
      break;
    }
    case Tag::Scanned: {
      assert(header == obj);  // no inheritance
      auto slab = reinterpret_cast<Slab<void*>*>(header);
      int n = (slab->obj_len_ - kSlabHeaderSize) / sizeof(void*);
      for (int i = 0; i < n; ++i) {
        Obj* child = reinterpret_cast<Obj*>(slab->items_[i]);
        if (child) {  // note: List<> may have nullptr; Dict is sparse
          auto child_header = ObjHeader(child);
          slab->items_[i] = Relocate(child, child_header);
        }
      }
      break;
    }
    default: {
      assert(header->heap_tag_ == Tag::Forwarded ||
             header->heap_tag_ == Tag::Global ||
             header->heap_tag_ == Tag::Opaque);
    }

      // other tags like Tag::Opaque have no children
    }
    // aligned() like Heap::Allocate()
    scan += aligned(header->obj_len_);
  }

  // We just copied everything from_space_ -> to_space_.  Maintain
  // invariant of the space we will allocate from next time.
  from_space_.Clear();
#if GC_PROTECT
  from_space_.Protect();
  // log("begin = %x", *from_space_.begin_);
#endif

  Swap();

#if GC_VERBOSE
  Report();
#endif
}

bool str_equals(Str* left, Str* right) {
  // Fast path for identical strings.  String deduplication during GC could
  // make this more likely.  String interning could guarantee it, allowing us
  // to remove memcmp().
  if (left == right) {
    return true;
  }
  // obj_len_ equal implies string lengths are equal
  if (left->obj_len_ == right->obj_len_) {
    return memcmp(left->data_, right->data_, len(left)) == 0;
  }
  return false;
}

bool maybe_str_equals(Str* left, Str* right) {
  if (left && right) {
    return str_equals(left, right);
  }

  if (!left && !right) {
    return true;  // None == None
  }

  return false;  // one is None and one is a Str*
}

#if GC_STATS
void ShowFixedChildren(Obj* obj) {
  assert(obj->heap_tag_ == Tag::FixedSize);
  auto fixed = reinterpret_cast<LayoutFixed*>(obj);
  log("MASK:");

  // Note: can this be optimized with the equivalent x & (x-1) trick?
  // We need the index
  // There is a de Brjuin sequence solution?
  // https://stackoverflow.com/questions/757059/position-of-least-significant-bit-that-is-set

  int mask = fixed->field_mask_;
  for (int i = 0; i < 16; ++i) {
    if (mask & (1 << i)) {
      Obj* child = fixed->children_[i];
      if (child) {
        // make sure we get Tag::Opaque, Tag::Scanned, etc.
        log("i = %d, p = %p, heap_tag = %d", i, child, child->heap_tag_);
      }
    }
  }
}
#endif

}  // namespace gc_heap

cpp

Coverage Report

Created: 2022-08-03 12:23

Line	Count	Source (jump to first uncovered line)
1		// gc_heap.cc
2
3		#include <sys/mman.h> // mprotect()
4
5		#include "mycpp/gc_types.h"
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	101	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	101	begin_ = static_cast<char*>(malloc(space_size));
39	101	#endif
40	101	size_ = space_size;
41
42	101	Clear();
43	101	}
44
45	20	void Space::Free() {
46		#if GC_PROTECT
47		Protect(); // There is no way of deallocating I guess
48		#else
49	20	free(begin_);
50	20	#endif
51	20	}
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	1.46k	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	1.46k	switch (header->heap_tag_) {
71	367	case Tag::Forwarded: {
72	367	auto f = reinterpret_cast<LayoutForwarded*>(header);
73	367	return f->new_location;
74	0	}
75
76	430	case Tag::Global: { // e.g. GlobalStr isn't copied or forwarded
77		// log("*** GLOBAL POINTER");
78	430	return obj;
79	0	}
80
81	669	default: {
82	669	assert(header->heap_tag_ == Tag::Opaque \|\|
83	669	header->heap_tag_ == Tag::FixedSize \|\|
84	669	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	669	int n = header->obj_len_;
90	669	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	669	free_ += aligned(n);
103
104		#if GC_STATS
105		num_live_objs_++;
106		#endif
107
108	669	auto f = reinterpret_cast<LayoutForwarded*>(header);
109	669	f->heap_tag_ = Tag::Forwarded;
110	669	f->new_location = new_location;
111	669	return new_location;
112	0	}
113	1.46k	} // switch
114	1.46k	}
115
116	2.13k	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	2.13k	return (obj->heap_tag_ & 0x1) == 0
120	2.13k	? reinterpret_cast<Obj>(reinterpret_cast<char>(obj) +
121	2	sizeof(void*))
122	2.13k	: obj;
123	2.13k	}
124
125	364	void Heap::Collect() {
126		#if GC_STATS
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	364	if (to_space_.size_ < from_space_.size_) {
137	9	to_space_.Free();
138	9	to_space_.Init(from_space_.size_);
139	9	}
140
141	364	char* scan = to_space_.begin_; // boundary between black and gray
142	364	free_ = scan; // where to copy new entries
143	364	limit_ = scan + to_space_.size_;
144
145		#if GC_STATS
146		num_live_objs_ = 0;
147		#endif
148
149	1.86k	for (int i = 0; i < roots_top_; ++i) {
150	1.50k	Obj** handle = roots_[i];
151	1.50k	auto root = *handle;
152		#if GC_VERBOSE
153		log("%d. handle %p", i, handle);
154		log(" root %p", root);
155		#endif
156
157	1.50k	if (root) { // could be nullptr
158	1.16k	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	1.16k	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	1.16k	*handle = new_location;
188	1.16k	}
189	1.50k	}
190
191	1.03k	while (scan < free_) {
192	669	auto obj = reinterpret_cast<Obj*>(scan);
193	669	auto header = ObjHeader(obj);
194
195	669	switch (header->heap_tag_) {
196	125	case Tag::FixedSize: {
197	125	auto fixed = reinterpret_cast<LayoutFixed*>(header);
198	125	int mask = fixed->field_mask_;
199	2.12k	for (int i = 0; i < 16; ++i) {
200	2.00k	if (mask & (1 << i)) {
201	149	Obj* child = fixed->children_[i];
202		// log("i = %d, p = %p, heap_tag = %d", i, child, child->heap_tag_);
203	149	if (child) {
204	148	auto child_header = ObjHeader(child);
205		// log(" fixed: child %d from %p", i, child);
206	148	fixed->children_[i] = Relocate(child, child_header);
207		// log(" to %p", fixed->children_[i]);
208	148	}
209	149	}
210	2.00k	}
211	125	break;
212	0	}
213	14	case Tag::Scanned: {
214	14	assert(header == obj); // no inheritance
215	0	auto slab = reinterpret_cast<Slab<void>>(header);
216	14	int n = (slab->obj_len_ - kSlabHeaderSize) / sizeof(void*);
217	208	for (int i = 0; i < n; ++i) {
218	194	Obj* child = reinterpret_cast<Obj*>(slab->items_[i]);
219	194	if (child) { // note: List<> may have nullptr; Dict is sparse
220	151	auto child_header = ObjHeader(child);
221	151	slab->items_[i] = Relocate(child, child_header);
222	151	}
223	194	}
224	14	break;
225	0	}
226	530	default: {
227	530	assert(header->heap_tag_ == Tag::Forwarded \|\|
228	530	header->heap_tag_ == Tag::Global \|\|
229	530	header->heap_tag_ == Tag::Opaque);
230	530	}
231
232		// other tags like Tag::Opaque have no children
233	669	}
234		// aligned() like Heap::Allocate()
235	669	scan += aligned(header->obj_len_);
236	669	}
237
238		// We just copied everything from_space_ -> to_space_. Maintain
239		// invariant of the space we will allocate from next time.
240	364	from_space_.Clear();
241		#if GC_PROTECT
242		from_space_.Protect();
243		// log("begin = %x", *from_space_.begin_);
244		#endif
245
246	364	Swap();
247
248		#if GC_VERBOSE
249		Report();
250		#endif
251	364	}
252
253	1.08k	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	1.08k	if (left == right) {
258	21	return true;
259	21	}
260		// obj_len_ equal implies string lengths are equal
261	1.06k	if (left->obj_len_ == right->obj_len_) {
262	278	return memcmp(left->data_, right->data_, len(left)) == 0;
263	278	}
264	785	return false;
265	1.06k	}
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_STATS
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