Finding and Tracing GC Roots

Roots Are the Hardest Part to Get Right

Mark-and-sweep is conceptually simple, but almost every real-world GC bug lives in one place: an incomplete or incorrect root set. This lesson isolates that concern — instead of writing a whole collector, you build the root-tracing logic on its own and reason carefully about every place a live reference can hide.

The Four Root Buckets

In a tree-walking interpreter, "what's alive" is implicit in the call stack. In a bytecode VM, it has to be explicit, because the collector has no idea what a raw stack slot or hash-table entry means unless you tell it. The canonical root categories are:

1. The VM operand stack. Every value currently pushed — including intermediate results mid-expression, like the still-unpopped left operand of a binary op whose right operand triggered an allocation (and therefore possibly a collection) while being evaluated.
2. Global variables. The whole globals table, values and all — a global can be the only reference keeping a large object graph alive.
3. Open upvalues. A closure that hasn't returned yet may have upvalues still pointing directly at a live stack slot in an enclosing frame; if that frame's function is otherwise done executing, the only reason its slot must stay valid is the open upvalue.
4. Compiler temporaries. While the compiler itself is running (and it allocates: string constants, function objects for nested fun declarations), those in-progress values aren't yet reachable from the VM's stack or globals — the compiler has to root them manually or a GC triggered during compilation will eat its own work.

Tracing Through Object Kinds

Reachability isn't just "is this object a root" — it's transitive. Each kind of object needs its own logic for what it points to (often called "blackening" an object in collector terminology):

Missing an edge for even one object kind means the collector will under-mark and free something still reachable through that path — a silent, delayed-fuse bug, since the freed object may not be touched again until much later in the program, far from where it was wrongly collected.

Why This Deserves Its Own Lesson

A collector that "usually works" is far more dangerous than one that crashes immediately, because reachability bugs manifest as use-after-free corruption that only shows up when a collection happens to run at just the wrong moment — which is exactly why GC bugs are notoriously non-deterministic and hard to reproduce. Writing the root/trace logic carefully, and testing it directly (rather than only testing end-to-end programs), is the only reliable way to catch these before they hide inside a "rare" crash report.

What to build

Implement the four root buckets and a generic mark_obj that recursively (or via worklist) marks through .refs. Drive it from the given stdin commands (STACK PUSH, GLOBAL, UPVALUE, TEMP, REF, TRACE) and confirm marked:<n> matches exactly the transitive closure of your roots — not more (leaked temps), not less (a missing root category).