Mark-and-Sweep — The Simplest GC

Our language allocates objects on the heap (strings, functions, closures, classes, instances). Without garbage collection, these objects would accumulate forever, leaking memory. A garbage collector (GC) automatically reclaims memory that is no longer reachable.

The Mark-and-Sweep Algorithm

Invented by John McCarthy in 1960 for Lisp, mark-and-sweep is the oldest and simplest GC algorithm:

Phase 1 — Mark: Starting from the "roots" (values the program can directly access), traverse all reachable objects and mark them.

Phase 2 — Sweep: Walk the entire list of allocated objects. Free any object that is NOT marked. Clear the mark on objects that ARE marked (for the next collection).

When to Collect

We trigger collection when the number of allocated bytes exceeds a threshold:

allocate(size):
    bytesAllocated += size
    if bytesAllocated > gcThreshold:
        collectGarbage()
        gcThreshold = bytesAllocated * GC_GROW_FACTOR
    return malloc(size)

The threshold grows after each collection (typically 2x). This amortizes the cost of collection: more allocations between collections means each collection does more work but happens less often.

The Object List

All heap objects are linked in an intrusive linked list via their next pointer:

Object {
    type: ObjType
    isMarked: bool
    next: Object*      // next object in the GC list
}

The sweep phase walks this list linearly.

Mark Phase

markRoots():
    // Mark values on the VM stack
    for value in vm.stack:
        markValue(value)
    // Mark global variables
    for value in vm.globals:
        markValue(value)
    // Mark open upvalues
    for upvalue in vm.openUpvalues:
        markObject(upvalue)

markObject(obj):
    if obj is null or obj.isMarked: return
    obj.isMarked = true
    // Recursively mark objects this object references
    traceReferences(obj)

Sweep Phase

sweep():
    previous = null
    object = vm.objects
    while object is not null:
        if object.isMarked:
            object.isMarked = false   // reset for next cycle
            previous = object
            object = object.next
        else:
            unreached = object
            object = object.next
            if previous: previous.next = object
            else: vm.objects = object
            free(unreached)

Your Task

Implement mark-and-sweep GC. Track allocated objects in a linked list, trigger collection at a threshold, mark from roots, and sweep unmarked objects.