Safepoints and Stack Maps: Letting a Collector Find Roots

A tracing collector starts from the roots: the globals, the thread stacks, and the registers. Globals are easy to enumerate because the runtime allocated them. Stacks and registers are not, because a compiled function keeps values in registers and stack slots chosen by the register allocator, and nothing in the machine state says which of those words is a pointer. A collector that guesses will either miss live objects and free them, or retain dead ones. The two mechanisms that solve this are safepoints, which control when collection may observe a thread, and stack maps, which describe what the thread’s frame contains at those points.

Why the machine state is not self-describing

Consider a function that computes a[i] + b[i] where a and b are arrays. The compiled code loads two pointers into registers, computes an address, loads two values, adds them. At the moment the addition executes, the two pointer registers are dead, because their last use has passed. A register allocator is free to reuse them for something else immediately afterward, and it usually does.

Now suppose the addition traps: a null check fails, or an overflow check fires, or a load hits an unmapped page. The trap handler needs to run, and running it may allocate, which may trigger a collection. At that instant the register file contains whatever the allocator decided, and the collector cannot tell whether a particular register holds a pointer into the heap or an integer that happens to look like one.

A conservative collector solves this by treating any word that falls within the heap’s address range as a potential pointer. That is sound, since a real pointer is never missed, but it retains objects that are actually dead whenever a stale value remains in a register or slot. It also fails on a moving collector: an interior pointer cannot be updated if the collector does not know that the word is a pointer, and treating a non-pointer as one and “updating” it corrupts data.

A precise collector needs an exact answer: for this program counter, which registers and which stack slots hold pointers. That is what a stack map is.

Stack maps as a table keyed by return address

A stack map is an entry in a side table, indexed by a code offset, listing the locations that hold object references. For each such offset, the map records a bit vector over stack slots and a set of register numbers. The table is emitted by the compiler, which knows the liveness of every value at every instruction.

offset 0x0142: stack slots 3, 4, 7 ; registers rbx, r12
offset 0x0168: stack slots 3, 4     ; registers r12
offset 0x01a0: (none)               ; no calls, no collection possible

The map is needed only at points where a collection can happen, which in a language with allocation is any point that calls into the runtime or allocates. The compiler emits a map at each such point and none elsewhere, so the table’s size is proportional to the number of call sites, not to the number of instructions. For a large method the table is still substantial: one bit vector per call site, of length equal to the frame’s spill area.

The map has to describe the frame precisely enough for the collector to walk it. For each frame the collector needs the return address (to find the map), the frame size, and the location of the saved frame pointer if the frame chain uses one. Implementations differ: some use a frame pointer chain so that unwinding is a linked-list walk, and some omit the frame pointer and rely on unwind tables that encode the frame size as a function of the program counter. Omitting the frame pointer frees a register and is why compiled code on x86-64 typically does not keep one, but it makes stack walking depend entirely on accurate unwind metadata.

Getting control at a safepoint

A stack map describes a point; a safepoint is the mechanism that ensures the thread is at such a point when the collector wants to look. Without it, a collector that stops a thread arbitrarily may stop it in the middle of an operation whose intermediate state is not described by any map.

There are two broad designs.

Polling. The compiler inserts a check at function entries, at loop back edges, and after calls. The check reads a per-thread flag and branches to a slow path if it is set. The flag is set by the collector when it wants threads to stop. Because the check is at a known instruction, the map for that instruction describes the state exactly.

Preemption with patch points. The runtime does not rely on polls in the code; it stops threads with a signal or an OS-level suspension, then inspects the program counter. If the counter is not at a safepoint, the runtime either waits for the thread to reach one or rewinds the counter to the nearest preceding safepoint and reconstructs the state there. Reconstruction is possible when the compiler recorded, for each instruction, how to map the state back to the preceding safepoint, which requires the register allocator to keep that information.

Polling is simpler and more portable; preemption avoids the cost of the poll in the hot path but requires the runtime to be able to reconstruct state at arbitrary points. Many production runtimes use a hybrid: polls at loop back edges and method entries, plus the ability to patch a poll in when a collection is requested, so that code that is already running will hit a check soon.

The cost of a poll and where to put it

A poll is a load of a thread-local flag and a conditional branch. On a modern core the load hits L1 and the branch is never taken in the common case, so the cost is a few cycles. In a loop that runs a few instructions per iteration, a few cycles per iteration is a measurable fraction. The standard mitigation is to hoist the poll out of inner loops and place it at the loop’s back edge only when the loop is known to be long-running, or to check only every N iterations by counting down a register.

The countdown variant costs an extra decrement and branch per iteration but amortizes the flag load. The choice depends on how the loop’s body compares to the poll: for a loop doing a memory-bound computation, the poll is noise; for a loop incrementing a counter, the poll may double the cost.

Placement also matters for correctness. A poll must not be inside a region where the state is inconsistent, such as between a store and the subsequent bookkeeping that makes the store visible to the collector. The compiler must place polls only where the stack map is valid and the object graph is coherent, which in practice means before and after operations that can allocate, not in the middle of them.

Interaction with register allocation and inlining

Every value that is live across a safepoint must have a location the map can describe. A value in a callee-saved register is easy, since the register’s content is preserved across calls. A value that the allocator would like to keep in a caller-saved register across a call must be spilled, and the spill slot’s liveness must be recorded. This is why safepoints constrain register allocation: they create live ranges that must survive calls, and those ranges force spills.

Inlining compounds the problem. An inlined callee’s locals become part of the caller’s frame, and the stack map at a safepoint inside the inlined body must describe the inlined frame’s live values as well as the caller’s. Implementations handle this by emitting maps that describe the merged frame and recording the inlining structure separately for stack traces. The map is therefore larger at inlined safepoints, and a deeply inlined function can have a map covering many logical frames.

The alternative, used by some runtimes, is to keep inlined frames out of the map and instead record the inlining tree so that a stack trace can be reconstructed by walking the caller’s frame and applying the tree. That saves map space at the cost of a more complex trace walk.

Edge cases that produce real bugs

Derived pointers. A pointer computed as base + offset is not necessarily a valid root, but it must be updated if the base moves. A moving collector needs to know which slot holds the base, and a compiler that keeps only the derived pointer in a register has lost that information. Runtimes that move objects require the compiler to keep the base live across any safepoint where the derived pointer is live, or to record the derivation in the map. This is the reason interior pointers are restricted in languages with moving collectors.

The frame’s return address. The map is indexed by the return address of a call, and the return address is on the stack. If the collector walks frames while the thread is at a safepoint in the middle of a function, the “return address” is the address of the poll, not of a call. Implementations that index maps by return address must ensure every safepoint is at a call, or must use a separate encoding for non-call safepoints.

Signals and asynchronous collection. A collector that stops threads with a signal must ensure the signal handler runs on a stack the collector can walk, and that the handler does not itself allocate. The handler’s own frame is not described by any map, so the collector must either exclude it or describe it. This is why asynchronous collection requires the runtime to control signal delivery closely, and why some runtimes suspend threads with a mechanism other than signals. The same constraint applies to any runtime event that has to walk frames at an arbitrary program counter, including exception unwinding, which must decode a frame’s tables from a raise point that is not a call boundary.

Cooperative versus preemptive. A thread that never reaches a safepoint cannot be stopped cooperatively. Long-running native code called from the managed language, or a tight loop with no back edge that the compiler instrumented, can stall a collection indefinitely. Runtimes mitigate this by requiring native calls to be annotated as safepoint-transparent and by inserting polls at every loop back edge, but the general problem remains: the collector’s latency is bounded by the longest interval between safepoints in any running thread.

The design’s overall shape is a contract between compiler and collector: the compiler promises to describe the state at designated points, and the collector promises to observe only those points. The cost is the poll and the map’s space, and the benefit is that the collector can be precise, which is what a moving collector requires. The interaction with the code that a JIT produces at run time is covered in tiered compilation and deoptimization, where the maps must also be usable to reconstruct interpreter state.