Stack Unwinding: Rebuilding the Call Stack from Frame Rules

A backtrace looks like a stack of records, one per call, each with a saved return address. The stack itself contains no such records. It contains whatever each function decided to push: saved registers, spilled locals, outgoing arguments, and sometimes a return address. Recovering the call chain means knowing, for each function on it, which bytes of the current frame belong to that function and where the caller’s frame begins. That knowledge is not in the stack. It is in a table indexed by instruction address, and the unwinder’s job is to read the table, apply it, and repeat with the registers it has reconstructed.

The one invariant unwinding depends on

Every unwinding scheme rests on a single convention: at any instruction inside a function, there is an address called the canonical frame address (CFA) which equals the value the stack pointer had at the call site in the caller, immediately before the call instruction pushed the return address. The return address is then at a fixed offset from the CFA, eight bytes below it on x86-64, and the caller’s stack pointer after the return is the CFA itself.

On x86-64 the CFA is defined as the value of rsp in the caller before the call, so inside the callee, after the call pushed the return address, the CFA is rsp + 8. A function that pushes rbp and then subtracts 64 for locals has a CFA of rbp + 16 for the body of the function, because rbp was set to the rsp value after the push. The CFA definition changes as the prologue executes, which is why unwinding needs a rule per address range rather than a rule per function.

The frame pointer chain is the degenerate case. If every function stores the previous rbp at [rbp] and keeps rbp fixed for its whole body, the chain can be walked with one load per frame: read [rbp] for the caller’s frame pointer and [rbp+8] for the return address.

/* Walk the rbp chain. Correct only while rbp is a frame pointer. */
void *bp;
__asm__ volatile ("mov %%rbp, %0" : "=r"(bp));
while (bp) {
    void **frame = (void **)bp;
    void *ret = frame[1];
    bp = frame[0];
    if (!ret) break;
    /* report ret; stop if bp stops increasing or leaves the stack mapping */
}

Compilers stopped guaranteeing this decades ago for optimised code, because reserving a register for a value that is only read during debugging costs a register in every function. -fomit-frame-pointer is the default at most optimisation levels on x86-64. A chain walk on such a binary follows whatever integer happens to sit where a saved frame pointer would be, which typically produces a short garbage trace and occasionally a loop.

Two encodings of the same rules

The replacement is a table of unwind rules, emitted by the compiler for every function, keyed by address range. Two sections carry it. .debug_frame is the debugging form, not loaded at run time. .eh_frame is the run-time form, placed in a loadable segment, because the same information is needed by the exception machinery: to unwind to a handler, the personality routine must reconstruct the caller’s registers exactly as a debugger does.

Both are built from two kinds of record. A CIE (common information entry) holds the values shared by a group of functions: the code alignment factor used to scale address advances, the data alignment factor for stack offsets, the register number that holds the return address, and an initial instruction sequence that establishes the rules in force before any prologue has run. An FDE (frame description entry) names a start address and a length, points back to its CIE, and holds instructions that modify the CIE’s rules across the function’s address range.

The instructions are a compact bytecode with the same shape as the line table’s: DW_CFA_advance_loc moves the current location forward without changing rules, DW_CFA_offset says a register was saved at a given offset from the CFA, DW_CFA_def_cfa sets the CFA to a register plus an offset, DW_CFA_def_cfa_offset changes only the offset, DW_CFA_register says a value lives in a different register, and DW_CFA_remember_state with DW_CFA_restore_state handles the branching that a prologue with several paths produces. A typical prologue compiles to a handful of these: advance to the push, record that rbp is saved at CFA-16, advance past the mov, redefine the CFA as rbp+16.

Running the program at a PC

Unwinding one frame takes four steps.

First, find the FDE whose address range contains the current program counter. Scanning every FDE would be linear in the size of the program, so linkers build .eh_frame_hdr, a segment containing a sorted array of (initial location, FDE address) pairs with a header describing the encoding of each field. A binary search over that array finds the candidate in logarithmic time, and the FDE’s range check confirms it. The encodings are relative to the header itself, so the table needs no relocation at load time, which matters because it is consulted from signal handlers and from the dynamic loader.

Second, execute the CIE’s initial instructions, then the FDE’s instructions up to the current PC. The result is a rule for every register: saved at CFA minus some offset, preserved in another register, undefined, or unchanged from the caller. Registers with no rule are assumed unchanged.

Third, compute the CFA value from the current registers using the rule just derived, then read the return address from its recorded location. If the rule says the return address is at CFA-8, that is one memory read.

Fourth, set the program counter to the return address and the stack pointer to the CFA, and repeat. The new PC identifies the caller’s FDE, and the process continues until a frame has no FDE, the return address is zero, or a termination routine such as _start is reached.

The cost per frame is the bytecode interpretation plus one or two memory reads. That is more expensive than a frame-pointer walk, and it touches memory that may not be resident, which is why kernel and profiler unwinders often replace the bytecode with a precomputed form: the Linux kernel’s ORC unwinder generates a compact table at build time so the unwinder only looks up and applies a fixed-size record, trading image size for speed and for the ability to run in contexts where interpreting a bytecode is awkward.

Where unwinding stops

The first hard limit is a signal frame. When a signal is delivered, the kernel builds a frame on the user stack containing the interrupted context and points the program at the handler. The handler’s own FDE describes the handler, not the transition; without a marker, the unwinder sees a return address that is not a call return and stops. GCC emits such a marker, an FDE whose augmentation announces a signal frame, and unwinders that honour it read the saved context out of the kernel’s frame layout. Unwinders that do not honour it produce a trace that ends at the handler, which is a common reason a crash inside a signal handler shows only one frame.

The second is a corrupted or switched stack. If a function has overwritten its own return address, the reconstructed PC is arbitrary; the next FDE lookup either finds nothing or finds a range that happens to contain the value, and the resulting trace is fiction. Every memory read during unwinding can also fault, because the CFA may point outside the mapped stack. A debugger handles this by reading tracee memory through ptrace, which returns an error instead of delivering a signal, and by refusing to continue when the reconstructed stack pointer does not move in the expected direction.

The third is code with no unwind information at all: hand-written assembly without .cfi directives, JIT output, and functions from a library built without unwind tables. For these the unwinder has no rules and must stop, or fall back to a heuristic scan of the stack for values that look like return addresses. Heuristic scanning produces plausible traces that are wrong in ways that are hard to detect, since any integer in the stack that falls inside a function’s range is accepted.

A fourth case is more subtle. Unwinding is not always done from a stopped process. A sampling profiler interrupts a running thread and unwinds from the interrupted context, where the PC may be in the middle of a prologue that has already adjusted the stack pointer but not yet recorded the change in a rule the unwinder has passed. The CFI is written so that each instruction boundary has a consistent state, but the boundary between two instructions is not an instruction boundary, and a profiler that samples the PC asynchronously has to tolerate a frame that does not reconstruct cleanly. This is the same reason a breakpoint in a prologue is unreliable, discussed in where a breakpoint on a line lands.

The rules also interact with inlining. An inlined call has no stack frame, so unwinding by frame produces the physical callers only; the logical frames the source describes come from the debugging information attached to the address range, not from the unwind tables. Reconstructing those requires the location machinery covered in debugging optimised code, which is a separate table indexed by the same address.