CompilersGarbage CollectionMedium

Implement Copying Garbage Collection

Master the fundamental concepts of garbage collection through this focused micro-challenge.

~45 minutes Garbage Collection Ready to learn

Topic Overview

Semispace Copying Collectors

Copying GC divides heap into from-space and to-space. Cheney's algorithm copies reachable objects to to-space, updates pointers, swaps spaces. Lisp machines and nursery collections in generational GC use copying for fast bump allocation. The tradeoff is memory: you need twice the heap capacity because only one semispace is active at a time.

Cheney Scan

Forward pointer scan iterates to-space. For each object, copy unforwarded children, leave forwarding pointer in from-space slot. Scan and free pointer chase each other through to-space until all reachable objects are copied.

c
Loading…

Bump pointer allocation in to-space is O(1)
Only live data copied; dead objects vanish
Requires 2x heap reservation
Forwarding pointers fix interior references

Connecting to real compilers

Production compilers embed this step inside a longer pipeline. GCC flows through cpp, cc1, assembly, and ld; Clang uses the driver, Sema, LLVM IR passes, and a target backend. LLVM bitcode, JVM bytecode, and WASM are other familiar IRs at the same layer. The exercise isolates one pass so you can test it alone before chaining it to the next stage.

Why for this exercise

You will implement copying garbage collection with semispaces. This exercise asks you to copy live objects, maintain forwarding pointers, and swap spaces after collection.

Implementation Task

Your Task

Implement a copying garbage collector with Cheney's algorithm: the heap is split into two semispaces; objects are allocated with a bump pointer, and a collection copies every live object into the other semispace, compacting it, and simply abandons everything left behind.

Input

Command	Meaning
`semispace BYTES`	size of each semispace (first line)
`new NAME SIZE`	allocate (sizes are multiples of 8)
`link A B` / `unlink A B`	add / remove a pointer (ordered, like mark-and-sweep)
`root NAME` / `unroot NAME`	roots, kept in the order added
`gc`	collect now

The heap

The two semispaces start at 0x1000 and 0x2000. Allocation starts in the one at 0x1000.
new bumps the allocation pointer. If the object doesn't fit in the rest of the current semispace, run a collection first (printed like any other); if it still doesn't fit, print out of memory: NAME and ignore that command.

Cheney's algorithm

free = start of to-space. Copy each root, in root order, to free (skipping one already copied), advancing free by its size and leaving a forwarding address behind.
scan = start of to-space. While scan < free: for the object at scan, copy each pointer target in link order (unless already forwarded), then advance scan past it.
Swap the semispaces: allocation continues at free in what was to-space.

Output

For each collection, numbered from 1:

c
Loading…

At the end: heap: NAME@0xADDR ... in address order (or heap: empty).

Example

Input:

c
Loading…

Output:

c
Loading…

Requirements

Objects have an address, size, pointer list and forwarding address; the scan loop needs nothing but the to-space itself as its queue.
After a collection, all pointers must refer to the copies.

Hidden tests cover shared objects copied once, cycles, a second collection back into the first semispace, and allocation that triggers a collection (and one that still fails).