Attributing Allocations to Call Sites by Unwinding the Stack

A heap profile that reports “eight megabytes in 512 KiB blocks” is nearly useless; the same profile annotated with the function that requested each block is an answer. The annotation comes from capturing a stack trace at every allocation and folding the traces into a tree. The tree is cheap to store and cheap to aggregate. Producing it is where the difficulty lies, because recovering a call stack from inside a function requires information the compiler is free to discard.

Why the frame pointer chain is not enough

The oldest unwinding method follows a linked list. On the common x86-64 calling convention, a function that keeps a frame pointer stores the caller’s frame pointer at a known offset from its own, and the return address sits immediately above it. Walking the list is three instructions per frame: load the saved pointer, load the return address, repeat. It costs a few cycles per frame and needs nothing but the stack.

The convention does not require the frame pointer. Compilers at any meaningful optimisation level use the register that would hold it as a general-purpose register, because on x86-64 there are only sixteen and the pressure is real. A function compiled without a frame pointer has no saved chain entry, so a naive walk either stops at that frame or, worse, follows whatever integer happens to be in the slot that used to hold the pointer, producing a trace through unrelated addresses. The result is a profile with plausible-looking call paths that are fabricated.

Two workarounds exist and both have costs. Compiling everything with the frame pointer forced on removes the ambiguity, at the price of a register and of the code that register would have made faster; for a profiled build that is often acceptable, and for a production build it usually is not. Unwinding by heuristic, checking that each candidate frame lies within a stack mapping and that the return address lies inside an executable mapping, filters nonsense but cannot distinguish a real frame from a coincidental pair of values, and it silently truncates traces at frames it cannot follow.

Table-driven unwinding

The general solution is to describe, for every instruction in the program, how to recover the caller’s state. That description is generated by the compiler and stored as unwind tables alongside the code. On the Itanium C++ ABI, which the major Unix-like systems follow for exception handling, the table is split into two levels: a compact table indexed by the program counter gives a coarse location, and a per-function bytecode program describes the exact stack state at that location: where the return address was spilled, which registers were saved where, and how much the stack pointer moved.

Unwinding with these tables proceeds by lookup and interpretation rather than by following pointers:

1. Take the current program counter and find the function’s unwind entry, a binary search in a sorted table keyed by address range.
2. Run the function’s bytecode until the current instruction offset is covered, accumulating a rule for each register: unchanged, saved at a stack offset, or saved in another register.
3. Apply the rules to the saved register context, producing the caller’s stack pointer, its frame base, and the return address.
4. Repeat with the caller’s program counter until a frame is marked as the outermost, or a depth limit is reached.

Each step is a search plus a small interpretation loop. The cost is tens of instructions per frame, which is one to two orders of magnitude more than the frame-pointer walk, and it is paid at every allocation. For a program allocating a few million small objects per second, unwinding every allocation is not affordable; unwinding a sampled subset is, and that is why sampling profilers exist as a separate design rather than a variant of full tracing.

The tables are usually consulted through a library that hides the bytecode: the platform’s unwinder, which is also what exception propagation uses. Using it has a consequence worth knowing: the unwinder assumes it is being called at a point where the stack is in a consistent state, and it may allocate or take locks while resolving the first lookup for a module. A tracing allocator that calls the unwinder from inside its own malloc re-enters itself. The standard mitigation is to prime the unwinder’s per-module state at load time by walking one frame for each loaded module, and to hold a re-entrancy flag that makes the allocator skip recording while an unwind is in progress.

Compressing the trace into a tree

Storing a full trace per allocation would cost more memory than the allocations being traced. A trace of depth ten is ten return addresses, 80 bytes on a 64-bit machine, against a median allocation of a few dozen bytes. The fix is to build a prefix tree in which each distinct stack is a path from the root, and each allocation stores only a pointer to its leaf plus a size. Two allocations from the same call site share the whole path.

Insertion walks the existing children of each node comparing return addresses, allocating a node only when a new address appears. The number of nodes is bounded by the number of distinct call paths, not by the number of allocations, which is what makes the representation practical: a program with a few hundred call sites produces a few thousand nodes regardless of allocation rate.

struct node {
    uintptr_t pc;             /* return address for this frame */
    struct node *first_child; /* siblings linked through `next` */
    struct node *next;
    uint64_t bytes;           /* live bytes attributed to this path */
    uint64_t count;
};

/* Insert one trace; returns the leaf node for the caller to charge. */
static struct node *intern(struct node *root, const uintptr_t *pcs, int depth)
{
    struct node *cur = root;
    for (int i = 0; i < depth; i++) {
        struct node **link = &cur->first_child;
        while (*link && (*link)->pc != pcs[i])
            link = &(*link)->next;
        if (!*link) {                       /* new call path: one node per address */
            struct node *n = node_alloc();
            n->pc = pcs[i];
            *link = n;
        }
        cur = *link;
    }
    return cur;
}

Charging live bytes to a leaf and propagating totals up the tree at report time gives both a per-call- site figure and a per-subtree figure without any per-allocation aggregation. The same tree answers “which function is responsible” at two granularities: the leaf’s own bytes are the direct requests, and the leaf’s subtree total includes everything its callees requested. Confusing the two is the most common misreading of a heap profile, since a wrapper that allocates nothing itself still owns a large subtree.

Frames that the unwinder cannot see

Unwind tables describe compiled functions. Several common situations produce frames the tables do not cover, and each biases a profile in a specific direction.

Assembly and JIT-compiled code. Hand-written assembly routines frequently have no unwind information, so unwinding stops at them. A runtime that generates machine code at run time has no tables at all unless it registers them; the major just-in-time runtimes do register unwind information for generated code precisely so that profilers and exception handling can walk through it, but a custom JIT that omits this appears as a single opaque frame.

Tail calls. When a compiler turns a call in tail position into a jump, the callee reuses the caller’s frame. The return address for the caller is gone, so the trace shows the callee called from the caller’s caller. The allocation is attributed one level too high, and no unwinding method can recover the missing frame because the information was never stored.

Inlined functions. The unwind table describes the outer function’s frame only. An allocation inside an inlined callee unwinds to the outer function’s caller, losing the distinction between inlined bodies. Recovering it requires consulting debug information, specifically the DWARF line and inline tables, which is a separate lookup per frame against a much larger structure, and it is usually deferred to report time rather than done during capture.

Signal handlers and alternate stacks. An allocation from a signal handler runs on a different stack, often a small one installed for the purpose. The unwinder follows the alternate stack to its base and then has no valid caller, so the trace ends there. Allocations from handlers are rare but not nonexistent, and they appear in a profile as unattributed.

Coroutines and manually switched stacks. A runtime that switches stacks explicitly must tell the unwinder about the switch, otherwise each stack looks like an independent chain rooted at nothing. Some runtimes do; the ones that do not produce traces that stop at the switch point.

Depth, sampling, and the cost of precision

Trace depth is a tunable with a clear trade. Deeper traces distinguish call paths that shallower ones merge, and cost more per capture: unwinding dominates the per-allocation cost, so depth multiplies the overhead roughly linearly up to the point where the tree deduplicates. A depth of eight to sixteen frames is the usual compromise, chosen because allocation call chains are typically shallow, since a request goes through a wrapper or two before reaching the allocator, and because the tree’s node count grows quickly with depth when many paths share only the top few frames.

The other lever is which allocations to trace. Tracing every allocation gives exact counts and exact bytes at a cost that can change the program’s behaviour: the traced process spends its time in the unwinder, and any lock in the tracing path serialises threads that were previously independent. Tracing a fixed fraction, or every n-th allocation, reduces the overhead proportionally and yields estimates whose accuracy improves with the number of samples rather than with the size of the heap. The choice between exactness and representativeness is the same one that governs sampling designs in general, and it interacts with leak detection , where a rare allocation path can be the one that leaks and a sampling rate that misses it produces a confidently wrong answer.