Fragmentation Without Leaks: Diagnosing a Growing Heap

A leak detector answers a narrow question: which allocations were never freed. A process can pass every leak check and still grow until it is killed. Its live set is flat, its free calls balance its malloc calls, and its resident size climbs. The bytes are not lost; they are held in a form that the allocator cannot hand to the requests that arrive next. Distinguishing that condition from a leak requires looking at the heap’s internal accounting rather than at the program’s allocation pairs.

Two different failures wearing one name

Internal fragmentation is bytes the allocator consumed but the program did not ask for. It is deterministic given the request sizes and the allocator’s rounding rules: a request of 33 bytes served from a 48-byte class wastes 15 bytes, every time. It is computable from a histogram of request sizes and does not depend on order.

External fragmentation is free bytes that exist but cannot satisfy a request because they are not contiguous, or not in the right place. It depends entirely on order. A sequence that allocates A, B, C and frees B leaves a hole the size of B; if no later request fits in it, those bytes are unavailable in practice while remaining free in accounting.

The two have opposite cures. Internal fragmentation is fixed by better class spacing or by allocating exact sizes, a change to the allocator. External fragmentation is fixed by keeping similarly sized objects together, by coalescing, and by not mixing long-lived and short-lived objects in the same region, a change to the allocation pattern or to the segregation policy.

A third category is often folded in and should not be: retained free space. Memory that is free at the allocator level but not returned to the operating system. It is neither fragmentation nor a leak; it is policy. The distinction matters because retained free space is the one form that can be released without changing the program at all, if the allocator offers a way to ask.

Reading the allocator’s own numbers

The counters that separate these conditions are usually available from the allocator rather than from the program. For a size-class heap they include, per class: the number of live objects, the bytes they occupy, the number of free objects, and the number of spans with at least one free object. Three derived quantities are diagnostic.

Occupancy of partially used spans. If many spans are one-quarter full, the allocator is holding a large amount of space in a form where most of each span is free but not reusable by other classes. This is the signature of a class whose population shrank after a peak, a phase that allocated many objects of one size and then stopped.

Free bytes versus the largest free extent. If total free bytes are large but the largest extent is small, external fragmentation is the binding constraint. If the largest extent is comparable to the total, the free space is consolidated and the problem is elsewhere.

Live bytes versus resident bytes. The gap is the sum of internal waste, retained free space, and metadata. Its size distinguishes rounding (a small, stable gap) from retention (a gap that grows and never shrinks) and from fragmentation (a gap that grows and shrinks with workload phases).

A heap profiler that records allocations can supply the request histogram, which combined with the class table gives internal waste exactly. The same histogram over time shows whether the request mix is shifting, which distinguishes “the program is allocating bigger objects now” from “the same objects are being placed worse”.

The allocation-order effect

The dominant cause of external fragmentation in a non-moving heap is the interleaving of lifetimes. Consider a loop that allocates a persistent node and a scratch buffer on each iteration, frees the scratch, and keeps the node. After n iterations the heap holds n nodes and n holes, one hole between each pair of nodes. Total free space is n scratch-buffer sizes, but the largest contiguous free extent is one scratch-buffer size, because each hole is bounded by live nodes.

Nothing is leaked. Every scratch buffer was freed. The heap has grown to hold both populations and cannot reuse the holes for anything larger than a scratch buffer.

The fix is placement, not deallocation. If scratch buffers come from a separate region, whether through an arena reset per iteration or through a separate size class in a segregated heap, the holes never form. This is the practical argument for segregating by lifetime as well as by size, and it is why request-scoped pools exist in servers even when a good general allocator is available.

The same effect appears within one size class when objects are of different sizes. A span that holds mixed sizes develops gaps that no single object fits, which is why class-based allocators use exact sizes for small objects and never split within a small class.

Coalescing cannot repair a bad layout

Boundary-tag coalescing merges adjacent free blocks, and it is necessary, but it only merges what is already adjacent. In the interleaved-lifetime case above, the holes are never adjacent because live nodes separate them. Coalescing reduces the number of fragments but cannot move live objects, so a heap that has become a checkerboard stays one.

This is the fundamental limit of all non-moving allocators: they can choose where to place a new allocation, and they can merge free neighbours, but they cannot relocate a live object. A moving collector can, at the cost of updating every pointer, which requires knowing where all the pointers are, which is why moving collectors are tied to a language runtime that can enumerate roots.

The practical consequence is that fragmentation must be prevented at placement time, and prevention requires knowing something about lifetimes. An allocator that sees only sizes cannot know that the scratch buffer will die before the node. It can only observe the pattern after the fact, through the occupancy counters, and adapt, which is what the policy knobs on general-purpose allocators are for.

Policy knobs that change the outcome

Several allocator-level settings shift the balance, and their names vary but their meanings do not.

Retaining fewer empty spans reduces footprint at the cost of more page-allocator traffic. An allocator that keeps every empty span for reuse has a footprint equal to the high-water mark of each class; one that releases empty spans promptly has a footprint closer to the live set, with the risk of reacquiring pages it just gave up.

Arena or region count controls how finely the heap is partitioned. More arenas reduce contention and can improve locality, but each arena has its own free space, so the amount of memory that is free-but-unavailable grows with the number of partitions. This is the same stranding problem that per-thread caches introduce, and it is bounded by the same technique: a global limit on total free space with rebalancing.

Dirty page decay determines how long freed pages keep their contents. A page that has been written and then freed still occupies physical memory; if the allocator returns it to the operating system, the next use faults and the kernel zeroes it. Retaining dirty pages trades memory for avoiding those faults. The knob is a direct memory-versus-latency trade and has nothing to do with fragmentation, though it appears in the same accounting.

Huge-page backing changes the granularity of the mapping. A 2 MiB huge page holding many small objects cannot be partially returned, so an allocator using huge pages for small-object spans retains more per span. The trade is fewer TLB misses against coarser release.

None of these knobs fixes fragmentation caused by lifetime interleaving. They change how much slack the heap retains, not whether holes form.

A measurement discipline that distinguishes the cases

The useful sequence when a process grows with a flat live set:

1. Record the live bytes from the program’s own accounting, or from a sampling profiler, over time. Flat live bytes with rising resident bytes is the condition in question.
2. Record the allocator’s free bytes and largest free extent. A small largest extent with large free bytes indicates external fragmentation; a large extent indicates retention.
3. Record per-class occupancy and span counts. A class with many partially used spans points at a phase change in the workload.
4. Compare requested bytes to consumed bytes for the dominant classes. A stable ratio near the class rounding means internal waste is not the cause.
5. Only then look for a leak, using a detector that reports allocations with no matching free, which will report nothing if the condition is fragmentation.

The order matters because leak detection is the expensive step and the least likely to be informative in this scenario. The cheap counters come first.

One further case resembles fragmentation and is not: a growing number of distinct allocation sites each holding a small live object. That is growth in the live set, correctly tracked, and the cure is in the program’s data structures. The tell is that live bytes rise with resident bytes rather than diverging from them.

When the cure is structural

Since placement is the only lever a non-moving allocator has, the durable fixes are structural. Separating long-lived from short-lived allocations by region is the strongest: it removes the interleaving that creates holes, and it makes the short-lived region releasable as a unit. Sizing objects to class boundaries removes internal waste where the layout permits it. Pooling objects whose count is bounded removes both, because a pool that never grows past its bound has no fragmentation to speak of.

The remaining cases, where a general heap serves a workload whose lifetimes are genuinely unpredictable, are where the allocator’s own policy is the only control, and where the honest statement is that some waste is inherent: any non-moving allocator can be forced into a checkerboard by an adversarial sequence of allocate-and-free operations, and no policy prevents it. The counters exist so that the waste can be measured rather than assumed, and so that a rising footprint is attributed to the mechanism that actually causes it.