Reachability from Roots and the Transitive Closure

McCarthy’s original description of Lisp’s storage reclamation already had the shape: mark what the machine can still name, then reuse the rest. A tracing collector never asks whether an object is still useful. It asks a narrower question that can actually be answered by inspecting memory: is there a chain of pointers from something the program can still name to this object? If no such chain exists, no future instruction of the program can load the object’s address, and its storage can be reused without changing observable behaviour. That is the whole justification for the technique. Everything else about a tracer, from the mark bits to the worklist to the sweep, is machinery for computing this one property efficiently.

The property is deliberately weaker than usefulness. An object reachable from a global but never touched again stays alive until the global is reassigned. A collector cannot distinguish a pointer that will be dereferenced from one that will not, because that distinction depends on the program’s future, and the collector only sees the present. Every design decision below follows from taking the conservative definition seriously.

The root set is wider than the stack

A root is a pointer the collector cannot discover by following another object. The obvious roots are the thread stacks, but a real runtime has more of them, and forgetting one produces the worst possible bug: an object that the program can still reach gets reused underneath it.

Live registers are roots, which is why collection happens at a safepoint rather than at an arbitrary instruction. At a safepoint the compiler has described, for each frame and each program counter, exactly which registers and which stack slots hold references. The collector reads the registers, spills them to a known location if necessary, and treats the spill slots as roots. Without that description a collector must guess, which is the subject of conservative stack scanning.

Beyond registers and stacks, the root set typically includes:

• Static and global variables in the data segment, including the static fields of loaded classes.
• Thread-local storage, which is per-thread mutable state that no stack frame owns.
• Handles registered by native code, such as local and global references created through a foreign-function interface.
• Interned strings and other runtime tables that hold strong references by construction.
• The finalization or weak-reference queues, whose entries keep objects alive until they are processed.

The last category is where implementations tend to leak. A queue that holds an object strongly while waiting to run a destructor keeps that object, and everything it points to, alive for at least one extra cycle. Weak processing exists precisely to break that chain, and it is fiddly enough to deserve its own treatment in weak references and finalization.

Marking as graph search with a visited set

The mark phase is a graph traversal over the heap. The graph’s nodes are objects, its edges are pointers stored inside objects, and the roots are the entry points. Because the graph is cyclic and can share subgraphs heavily, the traversal needs a visited set; without one, a cycle of two objects would loop forever.

The visited set is normally a mark bit per object, or one bit per addressable word. Marking proceeds as follows: every root is marked and pushed onto a worklist; while the worklist is non-empty, an object is popped, its pointer fields are read using the object’s layout description, and each target that is not yet marked is marked and pushed.

/* Every heap object begins with this header. The class pointer names a
   layout descriptor: an array of byte offsets of the object's pointer fields. */
struct header { struct layout *klass; unsigned marked : 1; };

static void mark_object(struct header *h, struct stack *wl) {
    if (h->marked) return;
    h->marked = 1;
    stack_push(wl, h);                 /* push once, on the white-to-grey edge */
}

void mark_from_roots(struct stack *wl) {
    struct header *h;
    while ((h = stack_pop(wl)) != NULL) {
        struct layout *l = h->klass;
        for (unsigned i = 0; i < l->npointers; i++) {
            /* The descriptor, not the raw bytes, decides what is a pointer. */
            struct header **f = (struct header **)((char *)h + l->offset[i]);
            if (*f) mark_object(*f, wl);
        }
    }
}

The cost of this phase is proportional to the number of live objects and the number of pointer slots inside them, not to the size of the heap. A heap of 4 GiB containing 200 MiB of live data costs roughly the same to mark as a heap of 200 MiB that is entirely live. That insensitivity to garbage volume is the defining advantage of tracing over the per-assignment accounting used by reference counting, which pays a fixed cost every time a pointer is stored.

Reading pointer fields requires knowing where they are. A precise collector uses a layout map per type: a bitmap of pointer offsets, or a descriptor with the offsets of the first few fields plus a run-length encoded tail. This map is the reason a tracing collector needs cooperation from the compiler and the object model, and the reason a language without such metadata cannot easily be collected precisely.

Where the mark bit lives, and what it costs

Two placements are common, and the trade is measurable.

A side bitmap allocates one bit per granule of heap, typically one bit per 8 or 16 bytes. At one bit per 8 bytes the bitmap is 1/64 of the heap, about 1.6 percent overhead, and it can be scanned linearly without dereferencing any object. Sweeping then becomes a sequential pass over the bitmap and the heap in address order, which is friendly to hardware prefetching and lets the collector free whole runs of objects with one free-list insertion.

An in-object bit costs no extra memory, but setting it dirties the first cache line of the object. On a 64-byte cache line, marking a small object brings in a line that may otherwise have stayed in the mutator’s cache, and the write forces the line to be written back later. For a heap with millions of small objects the extra cache traffic is real, though it is usually accepted in exchange for simpler object lookup: given a pointer, the mark bit is at a fixed offset.

There is a third option, used by collectors that must mark objects they do not own, such as a collector layered over memory allocated by foreign code: a bitmap indexed by address range, one bit per machine word. It wastes space for large objects but never needs a header, so it works on memory whose layout the collector did not choose.

Depth, recursion, and the shape of the worklist

The traversal order matters less for correctness than for memory. A depth-first walk over a long linked list pushes one entry per link, so a chain of ten million nodes needs ten million worklist entries. A fixed-size mark stack therefore overflows on exactly the inputs that are easiest to construct, and the collector must either grow the stack, fall back to marking in place, or abort.

The classical answer is pointer reversal, published independently as the Deutsch-Schorr-Waite algorithm: the traversal state is stored in the object’s own pointer fields, so the walk needs constant auxiliary space. When the collector descends into a field it overwrites that field with a back-pointer to the parent, and restores it on the way up. The heap is left unchanged at the end, but the object is transiently inconsistent, which rules the technique out for concurrent collection unless every read of a reversed field is mediated by a barrier.

Breadth-first marking with a bounded queue has a different failure mode: the queue fills, and the collector must either process objects out of order or mark a subtree lazily. Several production collectors combine approaches, using a small explicit stack and switching to a mark-bit sweep of the whole heap when it overflows, accepting the extra pass rather than failing.

What the closure does not establish

Three gaps between the theory and the behaviour are worth stating plainly.

Reachability is not liveness at the granularity of a stack slot. When a local variable goes out of scope, its slot usually keeps the old pointer until something else overwrites it. A precise collector marks from the slot because the stack map says the slot holds a reference; it cannot tell that the reference is dead. The result is retention: a large object graph stays alive until the frame returns or the compiler emits an explicit store of a null value. Compilers that care emit those stores; compilers that do not leave the retention to the next collection cycle.

Floating garbage survives marking. An object that became unreachable during the mark phase was still reachable when its parent was scanned, so it is marked and survives to the next cycle. This is not a bug but a consequence of computing a snapshot without stopping the world for the entire traversal; the amount of floating garbage is bounded by the allocation rate multiplied by the cycle length.

Finally, the mark phase proves only that no path exists at the instant the roots were read. Any mutation after that point can invalidate that result, which is why concurrent and incremental collectors need write barriers, and why a collector that marks while the program runs must either re-scan modified objects or maintain the invariant that no black object points to a white one. That invariant is the entire subject of concurrent marking and tri-colour barriers.

The sweep that follows marking is where fragmentation enters the picture, since the freed cells must be made allocatable again. How that bookkeeping is arranged is the next problem, taken up in mark-sweep and free-list fragmentation.