Conservative Stack Scanning Without Type Maps

A C program’s stack holds no metadata. A slot contains a machine word, and nothing distinguishes a pointer from a counter, a length, a hash, or four characters of a string. The compiler that produced the frame is gone, and even if it were present it might not have recorded which slots are live at which program counter. A collector for such a language has three options: require the programmer to register every root explicitly, restrict the language so that type information survives to run time, or guess.

Guessing is the conservative approach, and it works better than it sounds. The rule is: any word whose value lies within the heap’s address range, and which is aligned to the heap’s object granularity, is treated as a possible pointer. Marking follows it. A word that is not a pointer causes an object to be retained that did not need to be; a word that is a pointer is followed correctly. The scheme never frees a reachable object, which is the only correctness property that matters, and it can retain objects that are actually dead.

The address test and why it must be conservative

The test is a range comparison against the set of heap regions. With one contiguous heap the test is two comparisons; with several regions it is a search, and implementations use a page map or a coarse address table to make it a few instructions.

Alignment narrows the false-positive rate. If every object begins on an 8-byte boundary, a word whose low three bits are non-zero cannot be a valid object address, so the collector can reject it without a range test. If the heap is laid out so that all object addresses fall in a sparse subset of the address space, the false-positive rate falls further. Some collectors go beyond alignment and require the candidate to point at an object’s header, checking a magic value or a plausible size; that is a validity test rather than a range test, and it trades a memory read for a lower false-positive rate.

static int may_be_pointer(uintptr_t w, struct heap *h) {
    if (w & (ALIGN - 1)) return 0;                 /* misaligned: not an object */
    for (int i = 0; i < h->nregions; i++)
        if (w >= h->base[i] && w < h->base[i] + h->len[i])
            return 1;
    return 0;
}

The false-positive probability for a random word is roughly the fraction of the address space that the heap occupies, multiplied by the probability that the word is aligned. For a 64-bit address space and a heap of a few hundred megabytes, the range fraction is roughly one part in tens of billions, which is small enough that arbitrary integers almost never pass. The problem is that the words on a stack are not random: they include lengths, offsets, and pointers into buffers that happen to sit near the heap, and those are much more likely to fall inside a heap region.

Why the ambiguity forbids moving

A conservative collector cannot distinguish a genuine pointer from a coincidental integer, so it cannot rewrite the word. If it moved the object the word referred to, it would have to update the word, and updating a word that is not a pointer corrupts the program’s data. There is no way to tell which case applies, so no object may move.

That single consequence determines the collector’s architecture. A conservative collector must be non-moving, which means it cannot compact, which means it inherits all the fragmentation problems described in mark-sweep and free lists. It can still use a copying policy for the heap it fully controls, meaning objects allocated by the collector itself with known layout, but anything reachable from an ambiguous root must stay put.

Some implementations narrow the problem by separating the two: a moving collector for objects the runtime allocates with precise layout, and a non-moving region for objects reachable from foreign code. The boundary between them is a handle or a pin, and the accounting for which objects are pinned is the collector’s main bookkeeping burden.

Bartlett’s work on compacting with ambiguous roots took the other route: compact anyway, and during the update phase use a break table to rewrite pointers, treating any ambiguous word that maps to a moved object as a pointer and leaving the rest alone. The table records only the points where the old-to-new displacement changes, so it stays small, and the ambiguity is resolved at collection time rather than on every access.

What conservative scanning retains

Retention is the practical cost. Three sources are worth separating.

The first is stale stack slots. A function that uses a large buffer in a local variable and then returns leaves the frame’s slot pointing into the heap until something overwrites it. If the collector scans a deeper frame’s unused slots, it marks objects the program cannot reach. The remedy is to scan only the live portion of each frame, which requires knowing the frame’s extent; the collector can derive that from the stack pointer and the frame pointer chain, but not the set of live slots within a frame.

The second is interior pointers. A pointer to the middle of an array is a valid address that falls inside a heap region, and it must keep the whole array alive. That is correct behaviour, since the program may still access the array through that pointer, but it means a pointer to one byte of a 1 MiB buffer retains the whole buffer. Conservative collectors handle interior pointers by mapping the address back to the containing object through an object map, which is a search unless the heap is divided into fixed-size blocks.

The third is genuine false positives. A computed value that happens to equal a heap address retains an object. Zorn’s 1993 measurement is the standard reference on the magnitude: the retained fraction depends on the program, and for some allocation patterns the collector retains a noticeable fraction of the heap that a precise collector would free. The figure is workload-dependent and should not be quoted as a constant.

Retention is bounded by the amount of stack and register state, not by the heap, so a program with deep recursion and many live words retains more. That is the reason conservative collectors are often paired with a policy of clearing dead slots: the compiler inserts stores of zero into slots that go out of scope, which removes the ambiguity at a small cost in instructions.

Registers, signal handlers, and the setjmp problem

Scanning registers requires the collector to know their values. On a system where the collector runs as a library call from the program’s own thread, it can spill the registers to a buffer with setjmp or an equivalent, then scan that buffer as part of the root set.

The awkward part is that setjmp is required by the C standard to save only the registers it needs to restore control flow, and a compiler may keep a live pointer in a register that setjmp does not save. The usual workaround is a small assembly routine that pushes all callee-saved and caller-saved registers onto the stack, making them visible as ordinary stack words. That routine is architecture-specific, and it is the one part of a conservative collector that cannot be written portably.

Signal-handler-based collection faces a harder version of the same problem: the handler runs on an alternate stack with a register set that the kernel saved in a ucontext_t, whose layout is platform-specific. A collector that stops threads with a signal must therefore know each platform’s context layout, and it must ensure that the pointer values in the saved context are not stale.

A further hazard is that the collector must not treat a pointer into a different thread’s stack as a heap pointer, and must not mistake a pointer into a mapped file or a shared library for a heap object. The region test handles this if the heap regions are enumerated exactly, which is why conservative collectors maintain an explicit list of regions and refuse to scan anything outside it.

Interaction with the C compiler

A compiler that does not know a collector exists can break it in ways that are hard to diagnose. The most notorious is the optimized-away root: a variable that holds the only pointer to an object is not used again in the function, so the compiler keeps it in a register that is later reused, or eliminates it entirely. If a collection happens after that point, the object appears unreachable.

The standard mitigation is that the program must make the pointer appear live across the collection point, which the collector’s own API does by taking the pointer as an argument or by a compiler barrier. In C, an empty inline assembly block with a memory clobber is the portable way to force the compiler to treat the value as live. This is a language-level obligation that a precise collector does not impose, and it is the main reason conservative collection is described as requiring discipline rather than being transparent.

A related hazard is that the compiler may reorder a store of a pointer into a heap object past a collection point, so the collector sees the object as unreachable while the program has already published the pointer. The fix is a compiler barrier at the allocation call, which is again an obligation on the runtime’s interface.

When the approach is the right one

Conservative collection is the standard choice for a runtime that must interoperate with unmanaged code, for a language whose implementation does not carry type maps, and for a system where adding precise metadata would require changes to every compiler in the toolchain. Its costs are retention, no compaction, and platform-specific root capture; its benefit is that it works with an ordinary C compiler and an ordinary C ABI.

The alternative is precise scanning, which requires the compiler to emit stack maps and the runtime to understand them. That is the design of every managed runtime with a JIT, and it is what makes compaction available. The trade between the two is essentially the trade between a collector that must be told where the pointers are and one that guesses: the first needs cooperation up front and pays nothing at run time, the second needs nothing up front and pays in retained memory.

Both designs need to handle the objects that the program has asked the runtime to treat specially: weak references, finalizers, and the ephemeron case where a value is retained only if its key is retained. That machinery is the subject of weak references, finalization, and ephemerons.