Tracing Roots & Reachability

The correctness of a garbage collector depends entirely on accurately identifying roots and tracing reachability. Missing a root means freeing a live object (a crash). Including a non-root means leaking memory (less critical but still wasteful).

What Are Roots?

Roots are values that the program can directly access without following a reference chain. In our VM, the roots are:

1. Values on the VM stack — local variables and temporaries
2. Global variable table — all global variable values
3. Open upvalues — upvalues still pointing to stack slots
4. Compiler temporaries — objects created during compilation (if GC can trigger during compile)
5. The call frame functions — the function objects in active call frames

Tracing Object References

Once we have marked the roots, we must trace through all object references to find indirectly reachable objects:

traceReferences(obj):
    switch obj.type:
        case STRING:
            // strings don't reference other objects
            break
        case FUNCTION:
            markObject(obj.name)       // function name string
            for constant in obj.chunk.constants:
                markValue(constant)    // constants may be objects
        case CLOSURE:
            markObject(obj.function)
            for upvalue in obj.upvalues:
                markObject(upvalue)
        case UPVALUE:
            markValue(obj.closed)      // the captured value
        case CLASS:
            markObject(obj.name)
            markTable(obj.methods)
        case INSTANCE:
            markObject(obj.klass)
            markTable(obj.fields)

The Worklist Approach

Naive recursive tracing can overflow the call stack for deep object graphs. The solution: use an explicit worklist (gray stack):

markObject(obj):
    if obj is null or obj.isMarked: return
    obj.isMarked = true
    grayStack.push(obj)

traceAll():
    while grayStack is not empty:
        obj = grayStack.pop()
        traceReferences(obj)

This converts recursion to iteration, eliminating stack overflow risk.

Reachability is Conservative

The GC treats any value that could be accessed as reachable. A variable that is technically dead (will never be read again) but is still on the stack is considered reachable. This is safe but may delay collection. Optimizing compilers can insert "null out" instructions to help the GC, but we keep things simple.

How V8 Handles Roots

V8 has a much larger root set: the global object, built-in objects (Array, Map, etc.), handles (pointers from C++ to JS objects), and the execution stack. V8's GC is highly optimized with generational collection, incremental marking, and concurrent sweeping.

Your Task

Implement root identification for all root types and recursive tracing through all object reference types using an explicit worklist.