Introduction

The xo-alloc library provides a in incremental, generational collector for c++ code.

Features:

  • incremental - can reasonably expect short pause times.

  • generational - focuses effort on collecting young objects, on the basis that they’re more likely to be garbage.

  • compacting - each garbage collection cycle evacuates survivors to contiguous memory, so effect is to defragment.

  • collects cycles - collection algorithm naturally collects cyclic references

Tradeoffs:

  • Application is responsible for spilling register values and protecting hardware stack, since garbage collector cannot indepndently distinguish collectable object pointers from non-pointer values.

  • GC will not spontaneously run without permission. Instead will set a pending bit, with GC occurring only when application releases it (e.g. when stack+registers are known to be empty of values subject to GC).

  • GC implementation is single-threaded. It cannot run in parallel with the mutator (i.e. application code) In return this allows GC to be only lightly coupled with application.

  • GC divides each generation into separate from- and to- spaces. A collection cycle copies surviving objects out of from-space. Once complete, the entire from-space is treated as empty, and available to become to-space on a future cycle. This means that at any time only half of allocated memory is available to the application; the rest is waiting to receive survivors from the next GC cycle.

Design

Garbage Collector

The garbage collector supports two generations, labelled nursery and tenured. Nursery objects that survive two collection cycles are promoted to tenured space. Nursery and tenured objects are kept in separate memory areas, instead of being interspersed.

Collection cycles come in two flavors:

  1. incremental collections - these collect only the nursery space.

  2. full collections - these collect both nursery and tenured spaces. Full collection may incur noticeable GC pauses.

Application Interaction

Application code that interacts with GC has several responsibilities.

  1. application must explicitly invoke GC, when convenient. Since in general any GC-eligible object may get moved by the collector: once a collection cycle completes, it’s up to the application to re-load pointers from memory addresses (GC roots) that have been shared with the collector.

  2. application must identify a set of GC roots. GC preserves everything reachable from any GC root

  3. The collector needs to know how to traverse GC-managed objects. We teach it this by requiring that such objects inherit the xo::Object interface, and implement auxiliary function detailed below.

  4. GC also needs to know when a mutation alters a pointer from one GC-managed object to another. In particular, GC needs to track pointers from tenured space into nursery space, and update them when an incremental collection moves nursery objects. We do this by requiring application code use a GC-provided assignment primitive on GC-eligible pointers.

Example GC Use

 1 #include "xo/object/List.hpp"     // polymorphic List with GC support
 2 #include "xo/object/String.hpp"   // string type with GC support
 3 #include "xo/alloc/GC.hpp"
 4
 5 int main() {
 6     using xo::gc::Config;
 7     using xo::obj::String;
 8     using xo::obj::List;
 9     using xo::gp;
10
11     Config config = { .initial_nursery_z_ = 50*1000,
12                       .initial_tenured_z_ = 10*1000*1000,
13                       .debug_flag_ = false };
14
15     up<GC> gc = GC::make(config);
16
17     Object::mm = gc; // use GC for allocation of Object (+ derived classes)
18
19     gc->disable_gc(); // gc forbidden
20
21     // tiny example data structure
22     gp<String> s1 = String::copy("hello");
23     gp<String> s2 = String::copy(", ");
24     gp<String> s3 = String::copy("world!");
25     gp<List> list = List::cons(s1, List::cons(s2, List::cons(s3, List::nil)));
26
27     // tell GC what to preserve
28     gc->add_gc_root(reinterpret_cast<Object **>(list.ptr_address());
29
30     gc->enable_gc();  // triggers immediate gc
31
32     // s1, s2, s3 invalid.
33     // list at new address
34
35     std::cout << "list.size=" << list->size << std::endl;
36 }

GC-Eligible Types

Or, how to inherit xo::Object and provide GC support

A type Foo that inherits xo::Object needs to provide overrides for Object methods _shallow_size(), _shallow_copy() and _forward_children():

Typical Pattern

GC support methods look something like this:

  • class definition

 1 #include "xo/alloc/Object.hpp"
 2
 3 namespace xo {
 4     class Foo : public xo::Object {
 5     public:
 6         ...
 7         virtual std::size_t _shallow_size() const override;
 8         virtual Object * _shallow_copy() const override;
 9         virtual std::size_t _forward_children() override;
10     };
11 }

  • use overloaded operator new

A GC-eligible class will allocate instances using the MMPtr overload. This allocates memory in GC-owned space

  • _shallow_size() returns the amount of memory used by the subject:

1 std::size_t Foo::_shallow_size() const { return sizeof(Foo); }

  • _shallow_copy() is invoked during GC to create a copy of the subject

    It should use the xo::Cpof argument to operator new.

1 Object *
2 Foo::_shallow_copy() const;

  • _forward_children() is invoked during GC to vist child xo::Object pointers to make sure they survive

1 std::size_t
2 Foo::_forward_children();

Atomic Types Without Object Pointers

Plain-old-data classes without embedded pointers

1 Object *
2 Foo::_shallow_copy() const {
3     return new (Cpof(this)) Foo(*this);
4 }

1 std::size_t
2 Foo::_forward_children() { return Foo::_shallow_size(); }

For example see xo::obj::String in xo-object

Non-GC Objects

A class Foo that inherits xo::Object can opt-out of garbage collection by omitting the MMptr(mm) overload.

In that case Foo::_shallow_size(), Foo::_shallow_copy() and Foo::_forward_children() will not be called:

1 std::size_t Foo::_shallow_size() const { return sizeof(Foo); }
2 Object *    Foo::_shallow_copy() const { assert(false); return nullptr; }
3 std::size_t Foo::_forward_children()   { assert(false); return 0; }

For example see xo::obj::Boolean in xo-object

Structs Containing Object Pointers

A class with object pointers needs to tell GC how to traverse them

 1 #include "xo/alloc/Object.hpp"
 2
 3 namespace xo {
 4     class Foo : public xo::Object {
 5     public:
 6         ...
 7         virtual std::size_t _shallow_size() const override;
 8         virtual Object * _shallow_copy() const override;
 9         virtual std::size_t _forward_children() override;
10
11     private:
12         gp<Object> bar_;
13         gp<Object> quux_;
14     };
15 }

  • _forward_children() is invoked during GC to fixup child pointers that refer to forwarding objects:

1 std::size_t
2 Foo::_forward_children()
3 {
4     Object::_forward_inplace(bar_);
5     Object::_forward_inplace(quux_);
6
7     return Foo::_shallow_size();
8 }

For example see xo::obj::List in xo-object