Stack Unwinding in the Kernel Without Frame Pointers

Walking a stack sounds like a solved problem: follow the saved frame pointer from one frame to the next until it stops. It is solved only if the frame pointer exists. On x86-64 there are sixteen general-purpose registers, and reserving one of them permanently for the frame chain costs a register in every function in the kernel, plus two instructions per call and two per return. Compilers therefore omit it by default when optimising, which leaves the kernel with stacks it cannot read by that method. What it can read is a table the compiler emits alongside the code.

What a frame chain actually contains

The classic layout pushes the previous frame pointer onto the stack, sets the frame pointer to the current stack position, and allocates local storage below it. A walker reads the saved value at the current frame pointer, which is the address of the previous frame, and repeats. Two invariants make this work: every frame is in the chain, and the saved value is at a fixed offset from the frame pointer.

Neither holds when the compiler optimises. A leaf function that uses no stack does not build a frame at all, so it is invisible to the chain. A function that builds one and then inlines another into it has one frame for two source-level calls. Tail calls overwrite the caller’s frame instead of adding one. A function that adjusts the stack pointer dynamically (for a variable-length array, or an aligned temporary) moves the frame base during its body, so a sample taken in the middle may not match the layout at entry.

The frame chain also fails in the presence of an interrupt. When an interrupt arrives, the processor pushes a frame containing the interrupted instruction pointer, the flags, and on some entries an error code, then the kernel’s entry code pushes the remaining registers. The result is a region of the stack that is not a function frame and does not follow the chain’s rules, so a walker that reaches it and continues will read garbage as a return address.

Unwind tables as a data structure

The alternative is to describe, for every address range in the code, how to recover the caller’s frame. This is what DWARF call frame information does. The table is not a program; it is a state machine whose state changes at stated instruction addresses, and whose state says where each callee-saved register was saved and how the stack pointer moved.

For each function, a Common Information Entry establishes the initial state, and on x86-64 that state is the one the ABI fixes for the instruction after a call: the canonical frame address is the stack pointer at entry plus eight, which puts the return address at the canonical frame address minus eight, that is, at the top of the caller-active region the callee has not yet disturbed. Then a sequence of Frame Description Entries, each beginning at an address, modifies that state. A typical body prologue produces one entry: at offset four, an instruction has pushed the previous frame pointer and subtracted space for locals, so the canonical frame address is now the stack pointer plus a larger constant and the saved frame pointer is recoverable at a stated offset from it. The rest of the function needs no further entries, because nothing else about the frame changes.

Unwinding one step means: find the table row covering the current instruction pointer, apply its rules to the current register values, and compute the caller’s return address and stack pointer. Repeat until the return address is zero or the walker recognises a sentinel. The cost is a binary search over the table plus the application of a handful of rules, tens of cycles rather than thousands, which is cheap enough to run during a fault.

The tables are large. On x86-64 the compiler can emit them in a compact form and the linker can merge identical sequences, and the kernel’s own variant is smaller still: a byte-oriented encoding that sorts entries by instruction address and stores, per entry, a pair of small offsets (how far the canonical frame address sits from the stack pointer, and where the saved frame pointer was stowed) plus a tag saying whether the entry describes a real frame, a mid-prologue state, or an interrupt frame. Recovery is then a sorted lookup followed by two additions, with no interpretation of a rule language at all, which is what makes the walk cheap enough to run from a fault handler. The kernel generates these tables at build time from the object files rather than relying on the toolchain’s output format, which keeps them usable before the debugger or any userspace tool exists.

struct unwind_entry {
	unsigned long ip;       /* first instruction address this row covers */
	signed short sp_offset; /* canonical frame address minus stack pointer */
	signed short bp_offset; /* offset of the saved frame pointer, if any */
	unsigned char type;     /* real frame, mid-prologue, or interrupt */
};

/* Rows are sorted by ip; the applicable row is the last one <= ip. */
static const struct unwind_entry *
lookup(const struct unwind_entry *table, unsigned int count, unsigned long ip)
{
	unsigned int lo = 0, hi = count;

	while (lo < hi) {
		unsigned int mid = lo + (hi - lo) / 2;
		if (table[mid].ip <= ip)
			lo = mid + 1;
		else
			hi = mid;
	}
	if (!lo)
		return 0;   /* before the first row: not covered */
	return &table[lo - 1];
}

Two entry points, two kinds of stack

A walk that starts inside ordinary code follows one path. A walk that starts in an interrupt handler follows another, because the handler’s own frame sits on top of a frame the processor created, and the interrupted context may be either kernel or user mode. The kernel therefore keeps separate unwinders for the two cases and dispatches on the frame it is given.

The task-context unwinder begins with the current instruction pointer and stack pointer, and steps through frames that all belong to kernel code. The interrupt unwinder begins with a register snapshot that the entry code saved, reconstructs the interrupted instruction pointer from it, and decides whether the interrupted code was in the kernel or in userspace. If it was in userspace, the walk stops: the kernel has no unwind tables for arbitrary user code, and the user stack belongs to a different address space that may not even be the current one.

That last point is the subtle failure. A walker reading the user stack while the kernel runs on behalf of a different task reads another process’s memory. On architectures with tagged or protected pointers, or with a stack that lives in a separate mapping, the read may fault. Kernel unwinders therefore check that each candidate address lies within the kernel’s text range before trusting it, and abandon the walk when it does not.

Reliability is checked rather than assumed. Every kernel stack has a known extent, and every frame must be within it and must move in the correct direction: the stack grows down on the common architectures, so each successive frame pointer must be greater than the last. A walker that sees a non-increasing pointer, or a pointer outside the stack, stops and reports the trace as unreliable rather than printing a chain of invented addresses. A trace marked unreliable is not worthless; it means the entries up to that point were plausible, and the fault is likely to have damaged the stack itself.

Choosing between the two

Unwind tables cost space in the image, in proportion to the number of functions and the size of their prologues, which is why the compact encoding matters and why a build that keeps tables for every driver pays for it in image size. They must also be generated and merged at build time; the benefit is the recovered register and a walk that works for optimised code.

Both are supported, and the choice is a build option. A kernel built with frame pointers reports traces by the chain; one built with the table-based unwinder consults the tables. Distribution kernels have moved between the two over time, driven by profiling tools that prefer chains for their simplicity and by performance work that prefers the free register. The practical consequence is that a stack trace pasted into a bug report may have been produced by either mechanism, and a trace with obviously wrong symbol names usually indicates that the tables and the running image disagree, because the kernel was rebuilt after the trace was taken or the module’s tables were not registered.

Modules complicate the second case. A module’s text is not part of the kernel image, so its unwind tables must be registered when it loads and removed when it unloads, and the unwinder must consult all registered tables rather than one. A module that fails to register its tables produces a trace that ends at the module boundary, with the caller unknown. Since module text is freed on unload, a stale registration would point into reused memory, which is why removal is mandatory rather than best-effort.

Where unwinding appears in practice

The consumer is not only the debugger. A warning prints a stack trace to show which call path triggered it, and that trace is produced by the same machinery, in the same context, possibly while the kernel is in a state where a lock is held and allocation is forbidden. A tracepoint that records a call stack for later analysis uses it too, and so does the fault handler that formats the report described in decoding an oops report. Each of those is a place where a stack walk that allocates, takes a lock, or faults turns a diagnostic into a second failure.

The limit of the technique is that it recovers control flow, not data. It says which function called which, not what the arguments were, unless the compiler emitted location information for those arguments and the walker chooses to interpret it. Recovering a variable’s value from a register that has since been reused is impossible without that information, and the information is exactly what a kernel built for general use omits to save space. A trace therefore identifies the path and the instruction, and the rest of the diagnosis comes from reading the code at that instruction.