Leak Detection by Reachability Rather Than Allocation Count

A leak is not a block that was allocated and never freed. A program may allocate a block at startup, keep it in a global table for the whole run, and never free it, and that is not a leak by any useful definition. A leak is a block that is no longer reachable from anything the program can still use, and that will therefore never be freed. The distinction matters because it determines what a detector must compute. Counting allocations against frees measures the size of the heap, not the size of the problem. Deciding reachability requires knowing which words in memory are pointers, and that is where every practical detector has to make a compromise.

Roots and the set that must be scanned

Reachability is defined relative to a root set: the places a program can begin a traversal. For a process on a conventional operating system the roots are the stacks of every thread, the register state saved for each thread, the writable data segments holding globals and statics, and any thread-local storage. To these a detector adds the structures it knows about from intercepting allocation and deallocation, so that a block already marked free is not traversed.

The traversal itself is a mark phase. Start from the roots, treat each aligned word as a potential pointer, and if it points into a live heap block, mark that block and scan its contents as well. When the frontier is empty, every unmarked block is unreachable. This is the same algorithm a tracing collector runs, with the difference that the detector does not then free anything; it reports.

The hard part is the phrase “treat each aligned word as a potential pointer”. In a language with a precise object map, the runtime knows which words are pointers and which are integers. In C and C++, it does not. A stack frame holds return addresses, saved registers, spilled temporaries, and padding, and any of those bytes might coincidentally form a value that falls inside a heap block.

Conservative scanning and its false positives

A conservative detector accepts that ambiguity and assumes the worst: any word that looks like a pointer into a heap block is treated as one. The consequence is that a block is reported as reachable when the only reference to it is a stale copy in a dead stack slot or an integer that happens to have the same value.

The classic example is a value left in a register or on the stack after the last use. A compiler is free to keep a pointer in a callee-saved register across a call, and it is free to reuse that register afterwards without clearing it. A detector that scans the register file therefore sees a pointer that the program has already abandoned. Valgrind’s Memcheck separates blocks into definitely lost, indirectly lost, possibly lost, and still reachable, and the possibly lost category exists for exactly this kind of ambiguity: the block is reachable, but only through a pointer that does not point at its start, so the reference may be an artefact rather than a live link.

The false negative direction is equally real. A block referenced only through an XOR-linked list, or through a pointer stored as an offset, or through a tagged pointer with the low bits used for a flag, will not be found by a scanner that looks for exact addresses. Interior pointers are handled by rounding the candidate down to the containing block, which requires an interval lookup over the block table; a detector that only accepts pointers to block starts will miss a reference to the middle of an array.

The allocation record and what it must retain

To report anything useful, the detector needs a record per block: the size, the allocation site, and the state. AddressSanitizer’s LeakSanitizer keeps a hash table of live allocations and records a stack trace at allocation time, which it stores in a separate region so that the trace does not appear as a root reference to itself. Valgrind maintains its block records in its own allocator, separate from the client’s heap, which is one reason its instrumentation is more thorough and slower.

The size of the record determines the overhead. A detector that stores a fixed-size backtrace of a few frames per live block can cost tens of bytes per allocation, which is acceptable for a diagnostic run and unacceptable as a permanent mode. This is the reason leak detection is normally a separate build or a separate runtime flag rather than a default.

The tracking also has to handle reallocation. realloc may extend a block in place or move it; a detector that treats it as a free followed by an allocation loses the identity of the block and will report the old address as freed and the new one as newly allocated. Detectors intercept the call and update the record, preserving the original allocation site so that the report names the place the buffer was first created rather than the place it was grown.

Reachability at process exit is not the whole story

Most detectors run their analysis at exit, after the program has stopped. That timing has a consequence worth being explicit about: any block still reachable from a global at exit is reported as still reachable and not as a leak, even if the program would have leaked it had it run for another hour. The distinction is between a leak and a deliberately retained allocation, and only the program’s own intent separates them.

The opposite error is more damaging. A block that is reachable at exit only because the program’s shutdown path has not yet run will be reported as not leaked, while the same program running indefinitely would grow without bound. A detector that runs at exit cannot see growth over time. Catching that requires sampling the heap while the program runs and comparing the set of reachable blocks across snapshots, which is what a heap profiler with a delta view does: it records the allocation stacks and diffs two snapshots, so a block that is still reachable but was allocated between the snapshots shows as growth rather than as a leak.

Growth is the metric that matters for long-running services. A process that allocates a buffer per request and retains the last one thousand of them in a ring has no leak in the reachability sense, and unbounded memory growth in the practical sense. Only the snapshot comparison exposes it.

Detecting the use-after-free that leaks

Some of the most confusing leak reports are produced by the opposite defect. A block is freed, a new block is allocated at the same address, and the program still holds a pointer to the old address. The pointer now refers to the new block, which is reachable, and the new block’s own owner may also free it, producing a double free. The detector sees a block that is reachable and does not report a leak, while the real defect is an aliasing error.

AddressSanitizer addresses this by quarantining freed blocks: memory returned by free is not immediately available for reuse, so a stale pointer that is dereferenced lands in a region marked as poisoned and produces a report naming the free site. The quarantine has a size limit, and once it is exceeded the oldest freed blocks are released for reuse, so a defect that manifests after a large number of frees can escape. The same trade appears in any scheme that detects use-after-free by delaying reuse: the detection window is a function of the quarantine size, and the quarantine size is a function of the memory budget.

Reading a report without over-trusting it

A leak report is a hypothesis with a call stack attached. The stack names the allocation site, which is usually a wrapper such as a container’s growth function, and the useful frame is the caller several levels up. The size field distinguishes a small bookkeeping leak from a large buffer leak. The count field, when the detector aggregates by stack, distinguishes a single missed free from a per-iteration leak that will dominate the process’s growth.

The classification fields should be read before the stack. Definitely lost means no reference was found at all. Indirectly lost means the block is reachable only from another block that is itself lost, which usually means one root cause produced a whole subtree. Still reachable means a reference exists from a global or a live stack, which may be intentional.

What the report cannot establish is whether the allocation should have been freed. That is a question about the ownership design, and the answers are the ones the rest of this cluster covers. A block that is unreachable because the only owner was moved and the source was not cleared is a defect in move semantics. A block retained because a cycle of shared owners never reached zero is the case reference counting cannot collect. A descriptor that stays open for the same reason shows up not in the heap at all but in the table covered by descriptor lifetime.