Stack Unwinding Without Frame Pointers: Call Frame Information

The oldest backtrace technique is a linked list. Each function stores the caller’s frame pointer in a slot at a fixed offset from its own, so a debugger follows the chain from the innermost frame outward. It costs one register and two instructions per function, and it works only while every function in the chain obeys the convention. On x86-64, rbp is that register, and the chain is a sequence of [rbp] slots holding the previous rbp, with the return address at [rbp+8].

Optimising compilers broke the chain deliberately. With -fomit-frame-pointer, the default at ordinary optimisation levels on the common compilers for x86-64, rbp becomes a general-purpose register, and the chain no longer exists. The information needed to walk the stack is instead emitted as data: a table of rules, one per address range, describing where each function keeps the return address and how to restore the caller’s registers. That table is call frame information, and interpreting it is what every unwinder on a modern system does.

What the rules say

Call frame information describes, for any instruction address inside a function, the canonical frame address and the location of the saved registers relative to it. The CFA is not a stored value; it is computed, usually as the stack pointer at function entry plus a constant, or as the frame pointer plus a constant. The return address is then at a defined offset from the CFA.

The rules are encoded as DWARF expressions of the form “register n is at CFA + offset”, “register n is in register m”, or “register n is at the value stored at the address in register m”. A row of the table applies to an address range; when execution moves from one range to another, a set of opcodes updates the rule set. Because the rules are relative to a computed base rather than to absolute addresses, the same table works regardless of where the stack actually sits.

The table is stored in .eh_frame, or in .debug_frame for information used only by debuggers. .eh_frame is allocated and present in the loaded image because the same tables drive C++ exception unwinding at runtime; .debug_frame may be stripped and need not be loaded. The distinction matters when a stripped binary still produces usable backtraces through the runtime unwinder but a debugger cannot find .debug_frame: the information is there, just in the section the runtime uses.

Entries come in pairs. A Common Information Entry holds the code alignment factor, the data alignment factor, the return-address register number, and the initial rule set, typically “CFA = rsp + 8, return address at CFA - 8” for x86-64. A Frame Description Entry holds the address range it covers, a pointer to its CIE, and the instruction sequence that transforms the initial rules across that range. A function with no stack adjustment and no saved registers may need no instructions at all beyond its prologue, and the FDE is correspondingly tiny.

The x86-64 ABI makes one simplification that is worth knowing: the CFA at the call site is defined as the value of rsp before the call instruction, which is rsp + 8 inside the callee after the return address has been pushed. That convention is what lets an unwinder compute the caller’s stack pointer without knowing anything about the callee’s frame layout beyond the rules.

Walking one frame

Given a program counter and a stack pointer, the unwinder performs the same steps at every level.

It locates the FDE covering the program counter. In .eh_frame, the FDEs are not sorted in a way that permits binary search directly, so linkers emit .eh_frame_hdr, a table of contents holding a sorted array of (initial location, FDE address) pairs, plus an encoding byte describing how to decode them. The runtime unwinder binary-searches that array; a reader without it must scan. This is the reason readelf --debug-dump=frames on a large binary produces so much output: it decodes every FDE, not just the relevant one.

It runs the FDE’s instruction sequence up to the target address, maintaining the rule set. The opcodes include DW_CFA_advance_loc (move the location without changing rules), DW_CFA_def_cfa and DW_CFA_def_cfa_offset (change the CFA definition), DW_CFA_offset (a register is saved at a CFA-relative slot), DW_CFA_remember_state and DW_CFA_restore_state (save and restore rule sets, needed when a function has multiple epilogues), and DW_CFA_expression (a register’s location is computed by a small DWARF expression rather than a fixed offset).

It computes the CFA from the current register values, then reads the return address from its slot, and reconstructs the caller’s register set by applying the rules for the callee-saved registers. The restored stack pointer is the CFA itself, minus any adjustment the caller made before the call, which the caller’s own rules will supply at the next step.

It repeats with the recovered program counter and stack pointer. Termination conditions are equally important: the unwinder stops when it reaches a frame with no FDE, when the recovered program counter is zero, when the stack pointer fails to increase monotonically, or when a configured depth limit is hit. That last check exists because a corrupted stack can produce a cycle, and an unwinder that follows it forever will either hang or read off the end of the mapped stack and fault inside the debugger.

#include <stddef.h>
#include <string.h>

/* One rule row, reduced to what a frame with a constant CFA needs. */
struct rule {
    unsigned long pc_start, pc_end;
    long cfa_offset;   /* CFA = rsp + cfa_offset */
    long ra_slot;      /* return address lives at CFA + ra_slot */
};

/* Recover the caller's pc and sp. stack is the base of mapped stack
   memory and stack_len its size, so reads can be bounds-checked. */
int step(const struct rule *rs, size_t n, unsigned long pc, unsigned long sp,
         const unsigned char *stack, unsigned long stack_len,
         unsigned long *caller_pc, unsigned long *caller_sp)
{
    for (size_t i = 0; i < n; i++) {
        if (pc < rs[i].pc_start || pc >= rs[i].pc_end) continue;
        unsigned long cfa = sp + (unsigned long)rs[i].cfa_offset;
        unsigned long slot = cfa + (unsigned long)rs[i].ra_slot;
        if (slot < (unsigned long)stack || slot + sizeof(long) > stack_len)
            return -1;             /* would read outside the stack */
        unsigned long ra;
        memcpy(&ra, stack + slot, sizeof ra);
        *caller_pc = ra;
        *caller_sp = cfa;          /* sp before the call pushed the ra */
        return ra ? 0 : 1;         /* 1 means the outermost frame */
    }
    return -1;                     /* no FDE: unknown frame */
}

The real table has a rule per register, not just for the return address, and the CFA may be defined in terms of rbp rather than rsp in frames that use a frame pointer. The reduced version is enough to see the essential property: unwinding is a table lookup plus a stack read, with no assumption about how the function was compiled.

Why the compiler must emit the rules at every point

The rules are not per function but per address range, and the ranges must cover every instruction where an unwind could be requested. That includes the prologue, where rsp is being adjusted and saved registers are being pushed one at a time, and it includes the epilogue, where they are popped. A signal can arrive between any two instructions, and an asynchronous profiler samples at arbitrary points, so an FDE whose rules are only correct after the prologue produces wrong backtraces for interrupts in the prologue.

Compilers handle this by emitting DW_CFA_advance_loc between pushes and adjusting the CFA offset each time. The effect is a table with several tiny rows at function entry and exit, and one large row for the body. A function that saves six registers in its prologue has six rows describing the intermediate states, each a few bytes.

Two producer behaviours break unwinders in practice. Hand-written assembly without CFI directives produces a function with no FDE at all, and the unwinder must stop there, truncating the backtrace at the boundary. And a function that adjusts rsp dynamically, through a variable-length array, an alloca, or an alignment adjustment before a call, must describe the adjustment, typically with a CFA expression rather than a constant offset. If the producer gets that wrong, the return address is read from the wrong slot and the backtrace silently diverges into garbage rather than failing visibly.

Unwinding a core file versus a live process

A live unwind reads registers from the running thread and memory from the process. A post-mortem unwind reads both from the core file, and the difference in reliability comes from what was dumped. The register set at the faulting frame is present in the thread’s note. The stack pages are present only if the dump filter included them; if the faulting thread’s stack was in a mapping the filter excluded, the first frame may be readable while the second is not.

The distinction shows up as a backtrace that is correct at the top and full of ?? below. Some debuggers report the failure explicitly; others print a plausible-looking frame from whatever bytes happened to be at the computed address. The only defence is to check the recovered frame pointers against the mapping list, since a return address outside every executable mapping is not a return address. That mapping information is described in what an ELF core file preserves.

A related limitation is that the unwinder needs the right CFI. If the process loaded a shared library that was rebuilt after the core file was written, the FDEs in the loaded copy no longer match the code that ran. Build identifiers exist to catch this, and their role is described in matching binaries to debug information.

The cost of not keeping frame pointers

Keeping rbp as a frame pointer costs one register out of sixteen general-purpose registers, plus a push, a pop, and a move per function call. On register-poor architectures that register pressure is a real cost, and it is the reason the optimisation is default. The price is paid by every tool that walks the stack: unwinding becomes a table interpretation, and the table must be present and correct.

The table’s own cost is modest, a few bytes per function for simple frames and more for functions with complex prologues, but it is not free, and it is allocated and relocated at load time because it lives in .eh_frame. The .eh_frame_hdr table of contents adds an index so lookups are logarithmic rather than linear, and the linker builds it because the alternative — scanning every FDE on every exception — would make throwing an exception proportional to the number of functions in the binary.

The trade is therefore not “frame pointers versus nothing”. It is a register and two instructions per call against a few bytes of read-only data per function and a lookup at unwind time. Both designs are in use; the difference is which resource the system values less, and the practical consequence is that a backtrace tool must handle the table case, because on optimised binaries it is the only case there is. The addresses it produces are then turned into source locations by the machinery described in DWARF line tables, and the corruption that most often defeats it, a buffer overrun rewriting a saved return address, is what the checks described in AddressSanitizer shadow memory are built to catch.