Good day, hackfolk. Today's article is about semi-space collectors.Many of you know what these are, but perhaps not so many haveseen an annotated implementation, so let's do that.

Just to recap, the big picture here is that a semi-space collectordivides a chunk of memory into two equal halves or spaces, called thefromspace and the tospace. Allocation proceeds linearly acrosstospace, from one end to the other. When the tospace is full, we flipthe spaces: the tospace becomes the fromspace, and the fromspace becomesthe tospace. The collector copies out all live data from thefromspace to the tospace (hence the names), starting from some set ofroot objects. Once the copy is done, allocation then proceeds in thenew tospace.

In practice when you build a GC, it's parameterized in a few ways, oneof them being how the user of the GC will represent objects. Let's takeas an example a simple tag-in-the-first-word scheme:

struct gc\_obj { union { uintptr\_t tag; struct gc\_obj *forwarded; // for GC }; uintptr\_t payload[0];};

We'll divide all the code in the system into GC code and user code.Users of the GC define how objects are represented. When user codewants to know what the type of an object is, it looks at the first wordto check the tag. But, you see that GC has a say in what therepresentation of user objects needs to be: there's a forwarded membertoo.

static const uintptr\_t NOT\_FORWARDED\_BIT = 1;int is\_forwarded(struct gc\_obj *obj) { return (obj->tag & NOT\_FORWARDED\_BIT) == 1;}void* forwarded\_addr(struct gc\_obj *obj) { return obj->forwarded;}void forward(struct gc\_obj *from, struct gc\_obj *to) { from->forwarded = to;}

forwarded is a forwarding pointer. When GC copies an object fromfromspace to tospace, it clobbers the first word of the old copy infromspace, writing the new address there. It's like when you move to anew flat and have your mail forwarded from your old to your new address.

There is a contract between the GC and the user in which the user agreesto always set the NOT\_FORWARDED\_BIT in the first word of its objects.That bit is a way for the GC to check if an object is forwarded or not:a forwarded pointer will never have its low bit set, becauseallocations are aligned on some power-of-two boundary, for example 8bytes.

struct gc\_heap;// To implement by the user:size\_t heap\_object\_size(struct gc\_obj *obj);size\_t trace\_heap\_object(struct gc\_obj *obj, struct gc\_heap *heap, void (*visit)(struct gc\_obj **field, struct gc\_heap *heap));size\_t trace\_roots(struct gc\_heap *heap, void (*visit)(struct gc\_obj **field, struct gc\_heap *heap));

The contract between GC and user is in practice one of the mostimportant details of a memory management system. As a GC author, youwant to expose the absolute minimum interface, to preserve your freedomto change implementations. The GC-user interface does need to have someminimum surface area, though, for example to enable inlining of the hotpath for object allocation. Also, as we see here, there are someoperations needed by the GC which are usually implemented by the user:computing the size of an object, tracing its references, and tracing theroot references. If this aspect of GC design interests you, I wouldstrongly recommend having a look at MMTk, which hasbeen fruitfully exploring this space over the last two decades.

struct gc\_heap { uintptr\_t hp; uintptr\_t limit; uintptr\_t from\_space; uintptr\_t to\_space; size\_t size;};

Now we get to the implementation of the GC. With the exception of howto inline the allocation hot-path, none of this needs to be exposed tothe user. We start with a basic definition of what a semi-space heapis, above, and below we will implement collection and allocation.

static uintptr\_t align(uintptr\_t val, uintptr\_t alignment) { return (val + alignment - 1) & ~(alignment - 1);}static uintptr\_t align\_size(uintptr\_t size) { return align(size, sizeof(uintptr\_t));}

All allocators have some minimum alignment, which is usually a power oftwo at least as large as the target language's ABI alignment. Usuallyit's a word or two; here we just use one word (4 or 8 bytes).

struct gc\_heap* make\_heap(size\_t size) { size = align(size, getpagesize()); struct gc\_heap *heap = malloc(sizeof(struct gc\_heap)); void *mem = mmap(NULL, size, PROT\_READ|PROT\_WRITE, MAP\_PRIVATE|MAP\_ANONYMOUS, -1, 0); heap->to\_space = heap->hp = (uintptr\_t) mem; heap->from\_space = heap->limit = space->hp + size / 2; heap->size = size; return heap;}

Making a heap is just requesting a bunch of memory and dividing it intwo. How you get that space differs depending on your platform; here weuse mmap and also the platform malloc for the struct gc\_heapmetadata. Of course you will want to check that both the mmap and themalloc succeed :)

struct gc\_obj* copy(struct gc\_heap *heap, struct gc\_obj *obj) { size\_t size = heap\_object\_size(obj); struct gc\_obj *new\_obj = (struct gc\_obj*)heap->hp; memcpy(new\_obj, obj, size); forward(obj, new\_obj); heap->hp += align\_size(size); return new\_obj;}void flip(struct gc\_heap *heap) { heap->hp = heap->from\_space; heap->from\_space = heap->to\_space; heap->to\_space = heap->hp; heap->limit = heap->hp + heap->size / 2;} void visit\_field(struct gc\_obj **field, struct gc\_heap *heap) { struct gc\_obj *from = *field; struct gc\_obj *to = is\_forwarded(from) ? forwarded(from) : copy(heap, from); *field = to;}void collect(struct gc\_heap *heap) { flip(heap); uintptr\_t scan = heap->hp; trace\_roots(heap, visit\_field); while(scan < heap->hp) { struct gc\_obj *obj = scan; scan += align\_size(trace\_heap\_object(obj, heap, visit\_field)); }}

Here we have the actual semi-space collection algorithm! It's a tinybit of code about which people have written reams of prose, and to befair there are many things to say—too many for here.

Personally I think the most interesting aspect of a semi-space collectoris the so-called "Cheney scanning algorithm": when we see an objectthat's not yet traced, in visit\_field, we copy() it to tospace, butdon't actually look at its fields. Instead collect keeps track ofthe partition of tospace that contains copied objects which have notyet been traced, which are those in [scan, heap->hp). The Cheneyscan sweeps through this space, advancing scan, possibly copying moreobjects and extending heap->hp, until such a time as the needs-tracingpartition is empty. It's quite a neat solution that requires noadditional memory.

inline struct gc\_obj* allocate(struct gc\_heap *heap, size\_t size) {retry: uintptr\_t addr = heap->hp; uintptr\_t new\_hp = align\_size(addr + size); if (heap->limit < new\_hp) { collect(heap); if (heap->limit - heap->hp < size) { fprintf(stderr, "out of memory\n"); abort(); } goto retry; } heap->hp = new\_hp; return (struct gc\_obj*)addr;}

Finally, we have the allocator: the reason we have the GC in the firstplace. The fast path just returns heap->hp, and arranges for the nextallocation to return heap->hp + size. The slow path calls collect()and then retries.

Welp, that's a semi-space collector. Until next time for some notes onephemerons again. Until then, have a garbage holiday season!