Stack Unwinding With and Without Frame Pointers

A sample that records only the instruction pointer answers “which code is hot”. A sample that records the whole call chain answers “which path made it hot”, and that is the question worth paying for. Recovering the chain means walking the stack backwards, one frame at a time, using only the machine state that survives at an arbitrary instruction boundary. The difficulty is that there is no standard in-memory layout for a frame; the layout is decided by each function’s prologue, and in optimised builds it is designed to be invisible.

The frame pointer chain and its price

The cheap method relies on a calling convention: the callee pushes the caller’s frame pointer, then sets the frame pointer to point at the saved value. Reading the word at %rbp yields the previous %rbp, and the word just above it is the return address. The walk is a two-step loop per frame, each step a dependent load, so unwinding k frames costs k dependent cache accesses and terminates cleanly when a frame pointer of zero or a chain that leaves the stack region is found.

The price is a register. If the compiler reserves a general-purpose register for this, it has one fewer for temporaries, and on x86-64 the architecture offers only sixteen general-purpose registers, three of which are already committed to the stack pointer, the frame pointer, and instruction pointer. Compilers therefore omit the frame pointer by default in optimised builds, which leaves every callee free to use %rbp for anything. Frame-pointer chain walking then produces garbage: the walk either terminates after one or two frames or wanders into unrelated memory.

The omission also destroys a debugging aid that costs almost nothing to reason about. What the flag buys is roughly a register’s worth of register pressure on a register-starved architecture, and the measurable benefit varies by workload, which is why the trade-off has been argued repeatedly rather than settled.

Reconstructing the rules with DWARF call-frame information

The alternative is to consult a table describing, for every address in the program, how to compute the caller’s frame. This is the .eh_frame and .debug_frame data defined by DWARF. Each entry covers an address range and a set of rules: where the canonical frame address (CFA) is relative to the current stack pointer or frame pointer, and where each saved register lives relative to the CFA. Rules can be constants, register names, or small expressions evaluated by an interpreter.

The unwind algorithm is a fixed point over that table. Start with the current register set. Look up the rule set for the current program counter. Compute the CFA, which gives the caller’s stack pointer. Apply the register rules to recover the caller’s callee-saved registers, including the return address. That return address becomes the new program counter, and the loop repeats. Each step requires a table lookup that is essentially a binary search over the frame description entries followed by evaluation of a handful of rules.

Two things make this expensive enough to matter. The tables are auxiliary data, not hot code, so each lookup is likely to miss in the last-level cache. The interpreter is a small virtual machine, and its per-frame work runs in the hundreds of instructions. Combined with a sample rate of a few hundred hertz, DWARF unwinding is affordable; combined with a rate of thousands of hertz and deep stacks, the profiler becomes a significant part of the workload it is measuring. Profilers that want both high rates and deep stacks generally choose frame pointers, which is why distributions sometimes ship a build option that restores them.

The kernel has a third variant. Ordinary kernel code could not use frame pointers, and interpreting DWARF tables inside an interrupt handler was unacceptable, so the kernel carries a generated unwind table with a compact encoding: a per-frame description plus a sorted list of program counters, arranged so that the lookup is a binary search and the unwind itself is a few integer operations. It supports both the “the frame pointer is valid, just follow it” case and the “read the return address at this offset from the stack pointer” case in the same table, which is why the generated table is small.

Hardware branch records as an unwinder

Modern x86 processors can record a ring of taken branches in a buffer, including call and return pairs. A profiler that enables this gets, for each sample, the last n control transfers leading to the instruction that was interrupted, with no stack walk at all. The cost is a fixed number of hardware entries, typically a few tens, so the recovered chain is truncated at a shallow depth, and a switch that loses the buffer resets the history.

Branch records are exact where a stack walk is heuristic: they report branches that happened, independent of whether the compiler left any trace of the frame. Their limitation is depth combined with the fact that they capture only control flow the hardware chose to record. Mixing them with a software walk is possible but the boundary is delicate, since the two sources can disagree about the call path.

Where unwinds fail

Every unwinder has inputs it cannot handle, and the failure is silent. The most common cases:

Signal frames. When a signal arrives, the kernel places a synthetic frame on the user stack and jumps to the handler. The handler’s own frames unwind normally, but reaching the interrupted function requires knowing the kernel’s frame layout, which differs between architectures and versions. A profiler that does not recognise the signal trampoline terminates the walk at the handler, which is why signal-based profilers can show a stack of depth two.

Hand-written assembly. Code without a prologue and epilogue that a table describes will not unwind. Assembly that adjusts the stack pointer manually and calls into C leaves the unwinder with an inconsistent state, and the recovered return address may be arbitrary data interpreted as a code address.

Generated code. Just-in-time compilers emit code at addresses that no static table describes. Without a registration mechanism, both frame-pointer walking and DWARF lookup fall back to guesswork at every transition between generated and compiled code.

Tail calls. A tail call replaces the caller’s frame with the callee’s, so the caller genuinely is not on the stack. A correct unwind reports this, and the resulting call path differs from the source-level call graph. Tools that reconstruct callers from the stack therefore cannot see the elided frames.

Stack switching. Coroutines, user-level thread schedulers, and code that allocates an alternate stack all move the stack pointer to an unrelated region. An unwinder that assumes a contiguous stack will follow a frame pointer into an unrelated mapping, or stop, depending on values it finds there.

Frames whose saved values were optimised away. DWARF describes how to recover a register only where the compiler saved it. In leaf functions and in code that overwrites callee-saved registers after their last use, the rule may be “undefined”, and the recovered value is not the caller’s. The unwinder must detect this and stop; a walker that continues regardless produces a plausible-looking chain of wrong frames, which is worse than a short one.

Heuristic walking and its false frames

Some stack walkers scan the stack for words that look like code addresses, checking each against the executable mappings. This recovers something on binaries with no unwind information at all, and it produces phantom frames whenever a saved integer, a length, or a pointer happens to fall inside executable memory. On a 64-bit address space, executable mappings are a small fraction of the range, so false positives are uncommon per word but not negligible over thousands of scanned words.

The characteristic symptom of a bad unwind is a chain whose frames do not make sense: a frame that cannot call the next one, a repeated frame, or a frame from an unrelated subsystem. Flame graphs built from such chains show invented call paths, and the width of a phantom frame is real time attributed to a call that never occurred. Comparing the profile with a known-good call graph for a small test case is the cheapest way to detect this, and it is worth doing once whenever the unwinding mode changes.

Because the cost of unwinding is per sample and the rate is per second, the chosen method sets the profiler’s overhead floor. Keeping that floor bounded is a question about which instrument to use for a given event rate, treated in instrumentation and call counting. The consequences for reading a profile are more subtle: call chains produced by different unwinders are not interchangeable, so two profiles only compare meaningfully if they were collected the same way, a constraint that differential profiles depend on.