Reachability, Retention, and What Counts as a Leak

The word leak is used for two different failures, and the difference decides which tool can find it. In a language with manual reclamation, a leak is memory that the program will never free because it has lost the pointer: the bytes remain allocated and no code path can reach them again. In a language with automatic reclamation, no such memory exists, since anything unreachable is collectable, and the failure that gets called a leak is memory that is still reachable through a structure that grows without bound. The second kind is invisible to a reachability analysis and visible to a growth analysis. The first kind is the reverse.

Two definitions that disagree

Take a cache that stores entries in a hash table keyed by pointer identity and never removes them. Under manual reclamation the table’s buckets remain reachable from a global, so nothing is leaked in the strict sense: every byte is reachable from a root. The program’s footprint grows until it exhausts memory. Under a collector, the entries are equally reachable and equally uncollectable. Both systems exhibit the same symptom and neither has any unreachable object.

Now take a linked list whose head pointer is overwritten without freeing the nodes. Under manual reclamation every node is unreachable and the bytes are lost. Under a collector, the nodes become collectable at the next cycle and the footprint returns to its baseline. The same bug produces a leak in one system and nothing in the other.

A definition that covers both cases has to be about intent rather than reachability: memory is leaked when it is retained beyond the point where the program can use it, and retention is a property of the live data structure, not of the pointer graph. That definition is not mechanically checkable, which is why every practical tool approximates it from one side or the other.

How a tracing analysis decides liveness

A reachability-based leak detector works by marking. Starting from a set of roots (the stacks of all threads, the registers, the global data segment, thread-local storage, and any runtime structures the collector knows about) and follows pointers transitively and marks everything reachable. Anything in the heap that is not marked is unreachable and, if the analysis is correct, will never be used again.

For a managed runtime the collector already performs this work, so a leak report is a byproduct: mark, then report the unmarked set with the allocation site recorded when each object was created. The report is precise because the runtime knows exactly which words are pointers and where every object begins.

For a native program the same analysis requires answering two questions the hardware does not answer: which words in a block of memory are pointers, and where objects begin. Neither is available from the machine state. Approximations follow:

• Conservative scanning. Treat every aligned word in a root region as a potential pointer. If its value falls inside a heap block, mark that block. This never misses a real pointer, at the cost of marking some non-pointers, which keeps genuinely dead objects alive.
• Interior pointers. A pointer may target the middle of an object rather than its base. Accepting interior pointers requires either a block lookup structure that maps any address to its containing block, or a scan of candidate blocks. Accepting them increases false retention.
• Object headers. Without compiler support, a detector must place a header before each allocation to record its size and mark bit, which changes the layout the program sees and breaks code that frees foreign pointers or assumes alignment.

A mark phase over such a heap is short enough to state completely. The worklist holds block addresses rather than objects, and marking is a flag in the block header:

#include <stdint.h>
#include <stddef.h>

struct block { size_t size; int marked; struct block *next; };

/* Conservative mark: every aligned word of a marked block is a candidate pointer. */
static void mark_all(struct block *heap, size_t heap_bytes, uintptr_t *roots, size_t nroots)
{
    struct block *work[1024];              /* fixed worklist; overflow is a reporting concern */
    size_t top = 0;

    for (size_t i = 0; i < nroots; i++) {
        for (struct block *b = heap; (char *)b < (char *)heap + heap_bytes; b = b->next) {
            if (roots[i] >= (uintptr_t)b && roots[i] < (uintptr_t)b + b->size) {
                if (!b->marked) { b->marked = 1; work[top++] = b; }   /* interior pointers count */
                break;
            }
        }
    }
    while (top) {                          /* transitively scan each newly marked block */
        struct block *b = work[--top];
        uintptr_t *w = (uintptr_t *)(b + 1);
        size_t words = (b->size - sizeof *b) / sizeof *w;
        for (size_t i = 0; i < words; i++) {
            for (struct block *c = heap; (char *)c < (char *)heap + heap_bytes; c = c->next) {
                if (w[i] >= (uintptr_t)c && w[i] < (uintptr_t)c + c->size) {
                    if (!c->marked) { c->marked = 1; work[top++] = c; }
                    break;
                }
            }
        }
    }
}

The inner scan is linear in the number of blocks, which is why production detectors replace it with a sorted block index or a page-level map. The marking rule is what matters: an address that falls anywhere inside a block keeps the whole block alive, including its interior, and a value that merely looks like an address does the same.

The result is a detector that reports a superset of the true garbage. Its reports are trustworthy in one direction, in that a block it calls unreachable is unreachable unless a pointer was hidden from it, and untrustworthy in the other.

False retention in conservative systems

Conservative collection has a specific and instructive failure mode: a value that is not a pointer but looks like one pins an object. An integer that happens to equal a heap address, a stale copy of a pointer left in a register or a stack slot by an earlier call, a byte string containing an address: each of these keeps its target alive for as long as the value remains in a scanned region.

The classic instance is the stale stack slot. A function computes a pointer, finishes, and returns; the slot it used is below the stack pointer and out of scope, but a later call reuses the same stack region and the old value may still be there when a collection runs. Conservative collectors deal with this by scanning only the live portion of the stack, from the current stack pointer to the stack base, and by clearing registers that are known dead. Neither is perfect, and the residual effect is that memory appears to be retained with no visible reference.

The practical consequence for leak hunting is that a conservative detector’s report has to be read with an eye on what could be pinning the object. A block reported as reachable with no apparent owner is often reachable through a stale word, and the fix is to clear the buffer or register that holds it rather than to change the data structure.

Building a usable leak report

A mark-and-sweep pass gives a set of unmarked blocks. That set alone is not actionable: it says nothing about when the blocks were allocated, which call path created them, or whether the count is growing. Three additions make it a report.

Allocation stacks. Recording a stack trace at allocation time, as described in stack-based attribution , lets the unmarked set be grouped by call path. The grouping is what turns thousands of blocks into a handful of suspects.

Age. A block allocated during the current epoch and still live is not evidence of anything; a block that has survived several collections is. Tracking the epoch in which each block was allocated and reporting only blocks older than a threshold removes the noise from short-lived allocation, which is the overwhelming majority of traffic in most programs.

Deltas between snapshots. Two reports taken at different points, with the same roots, can be diffed by allocation stack. The stacks whose live bytes grew between the snapshots are the ones that retain memory across the interval. This is the most reliable signal available, because it removes the static baseline of caches, tables, and pools that a program allocates once and keeps, which would otherwise dominate the report.

The diff has a subtlety worth stating: a stack that grew may be a cache that is supposed to grow, and a stack that stayed flat may be a leak whose growth is masked by an equal amount of legitimate freeing elsewhere. Only a series of snapshots over a long interval separates the two, which is why the useful leak tools are the ones that run for the duration of a process rather than once.

Why managed runtimes still leak

A collector removes the unreachable-memory leak and leaves two others, both common enough that managed services exhaust heaps regularly.

Retention through long-lived references. A listener list that adds a handler per request and never removes it; a static map keyed by an object whose hashCode and equals are identity-based; a thread-local holding a large buffer after the work that needed it. Every one is reachable, every one is a leak by intent, and no reachability analysis can flag it. The tools that find these are the ones that report retained size: for each object, the total bytes that would become collectable if it were removed. Retained size is a graph computation over the object graph, and the objects worth examining are the ones whose retained size is large relative to their own size.

Fragmentation and delayed return. A collector that frees objects but does not return their pages to the operating system keeps the process footprint high while the live set is small. This is not a leak in any definition, but it is indistinguishable from one in a footprint graph. The distinction requires knowing what the collector’s heap is holding versus what the program’s live objects occupy, and the gap is exactly the allocator’s own metadata and free space rather than anything the program did.

Finalisation and deferred cleanup. An object that is reachable from a finaliser queue is alive by the collector’s definition even though no program code can use it. A queue of pending finalisers that grows faster than it drains retains everything it references, and the retention is invisible to a reachability report that treats the queue as a root. The same applies to weak references that are cleared lazily, and to any deferred-work structure whose entries hold strong references.

The direction each tool can be trusted

The practical point is what each analysis can and cannot see, and the discipline of choosing the one that can see the suspected failure.

A mark-and-sweep pass sees unreachable blocks and nothing about intent. It is the right tool when the suspicion is a lost pointer, and it is blind to a growing cache that is reachable by construction.

A growth diff over allocation stacks sees retention across time and nothing about reachability. It is the right tool for a slow leak in a long-running service, including all the managed-runtime cases above, and it cannot distinguish a leak from a working set that legitimately grows with the input.

A retained-size computation over an object graph sees which single object is holding the memory and nothing about how it got there. It is the right tool for a heap dominated by one large structure.

No analysis sees intent. The closest approach is a comparison against an expectation: a program that has finished processing its input should return to a baseline footprint, and the difference between its footprint then and at the start is the retention that has no purpose. Establishing that baseline requires the same measurement discipline as any other footprint work: the counters described in reading a process footprint are where the comparison starts, and the long-interval growth analysis is how the comparison is made automatic.