Measuring Fragmentation: Free Space That Cannot Be Used

A heap that is 70 percent free can fail an allocation of a quarter of its size. The free bytes are not contiguous, or they are locked into size classes that cannot serve the request, or they belong to a span that will not be released until it empties. This is fragmentation, and the reason it is hard to measure is that it is not a property of any single block: it is a property of the arrangement of free and live blocks relative to the sequence of requests the program will make next.

Two kinds of waste, one name

The standard split distinguishes waste that is inside an allocated block from waste that is between them.

Internal fragmentation is the difference between the size requested and the size the allocator actually committed to the request. It includes class rounding, alignment padding, and per-object headers. It is measurable exactly, because it is a deterministic function of the requested size and the allocator’s class table. A program with a known size histogram can compute its internal fragmentation without running at all.

External fragmentation is free memory that exists but cannot satisfy a request. It arises when the free regions are smaller than the request, or are of the wrong type, or are held by a structure that will not subdivide them. It is not measurable from the free list alone, because whether a free region can serve a request depends on the request.

A third kind deserves separate treatment because it dominates real footprints:

Retention fragmentation is memory the allocator holds but the program cannot use: free objects in per-thread caches, empty spans that have not been returned to the page allocator, and pages released to the allocator but not to the kernel. It is not fragmentation in the classical sense: the memory is perfectly usable, just by a future allocation rather than a current one. It produces the same symptom, a footprint above the live set.

The ratios that predict failure

Three numbers are worth computing, and they answer different questions.

The live fraction is live bytes over heap bytes. It says how much of the heap is doing work. A sustained live fraction below roughly a half in a heap that is not shrinking usually means the allocator is holding space for a peak that has passed.

The free-space contiguity is the largest free region over the total free bytes. It answers the question that predicts whether a large request will succeed: a heap with 10 MiB free whose largest contiguous run is 64 KiB cannot serve a 1 MiB request even though it has the room. On a free-list allocator this ratio is computed by walking the free list and tracking the maximum; on a segregated allocator it is computed per size class, because free objects of one class are not interchangeable with another.

The span occupancy is the mean fraction of each span’s objects that are live. For a span-based allocator this is the number that determines how much memory the class is holding relative to its live set: a class with 20 percent occupancy across 100 spans holds five times the pages its objects need.

/* Fragmentation statistics for a heap of contiguous blocks, each with a size header. */
#include <stdio.h>

struct block { size_t size; int free; };

void frag_stats(struct block *heap, size_t heap_bytes)
{
    size_t free_bytes = 0, largest = 0, live_bytes = 0;
    for (struct block *b = heap; (char *)b < (char *)heap + heap_bytes;
         b = (struct block *)((char *)b + b->size)) {
        if (b->free) {
            free_bytes += b->size;
            if (b->size > largest) largest = b->size;   /* contiguity of the free space */
        } else {
            live_bytes += b->size;
        }
    }
    printf("live=%zu free=%zu largest_free=%zu contiguity=%.3f\n",
           live_bytes, free_bytes, largest,
           free_bytes ? (double)largest / free_bytes : 0.0);
}

The walk requires blocks to be laid out contiguously at ascending addresses, which a boundary-tag arena with a header between blocks has and a segregated allocator does not; the free list itself is not consulted. For the latter, the equivalent measurement is per class plus a separate accounting of spans, since the addresses of a class’s objects are interleaved with other classes by design.

Why a heap fragments at all

Fragmentation is a consequence of allocation patterns interacting with a placement policy, and the patterns that produce it are ordinary.

Long-lived objects interleaved with short-lived ones. A program that allocates a persistent object between two temporary ones leaves a hole when the temporaries are freed. Repeat and the heap becomes a sieve of small holes between pinned blocks. No coalescing can merge the holes, because the live block between them is immovable.

Size churn. A workload whose allocation sizes drift upward over time cannot reuse the small holes it created earlier. The holes remain free and useless while the heap grows at the top. A first-fit policy makes this worse by leaving small remainders at the front of the list, which is the mechanism behind the classical result that first-fit tends to leave a trail of small unusable fragments while best-fit tends to leave a trail of larger ones.

Monotonic growth with a bounded live set. A program that allocates and frees steadily but always allocates from the top, either because it is a bump allocator or because its free lists are exhausted by holes of the wrong size, grows without bound. The heap’s live fraction falls toward zero while the footprint climbs, which is the signature to look for.

Class mismatch after a phase change. A program that allocates many 32-byte objects during startup and many 512-byte objects later holds the startup spans forever, because a span of 32-byte objects cannot serve a 512-byte request. The pages are not free, since they contain free objects, but they are unusable for the current phase.

The 50 percent rule and what it actually says

A well-known result for first-fit allocation, reported in the standard survey of dynamic storage allocation, states that under effectively random request order, in the steady state, with block sizes rarely equal, the free list tends toward about half the number of blocks in use. The wasted space is therefore of the same order as the live space, and it is scattered rather than concentrated. The result is a statement about a specific model (independent random sizes, random frees, no systematicity in placement), and it is often quoted as a general law about allocators. It is not: the same survey observes that these assumptions fail for most real programs, and that measured fragmentation in real workloads varies enormously with the allocation pattern.

What the result establishes is narrower than its reputation: inside those randomness assumptions, first-fit’s steady state wastes space proportional to the live set, so fragmentation in that model is a property of the demand pattern rather than of implementation quality. An allocator can beat the bound for a particular workload by exploiting its structure (segregating by size, using per-thread caches, using a copying collector that compacts), but each of those is a change to the model, not a fix to the policy.

The practical reading is about trend rather than level. A heap whose live bytes stay flat while its live fraction falls is accumulating unusable space, which is the signature of a pattern that has outgrown the allocator’s ability to reuse what it freed. The absolute value of the fraction says little on its own, because it depends on the size mix and on how many spans the allocator is holding for later.

Compaction as the alternative

The only general remedy for external fragmentation is to move live objects so that free space becomes contiguous. That is what a copying or compacting collector does, and its cost is the reason most native allocators do not.

Compaction requires knowing every pointer to every object, because moving an object invalidates all references to it. In a managed runtime with a precise object map that is available. In a native program it is not: pointers live in registers, on stacks, inside other objects, and in memory the allocator cannot identify. Moving an object in such a program is impossible without cooperation from every code path that might hold a reference.

The alternatives short of compaction are all heuristics:

• Release empty spans promptly. Returning a span to the page allocator as soon as its last object is freed keeps the heap close to the live set, at the cost of repeated mmap and munmap calls and the page faults that follow reallocation.
• Defragment by class. Some allocators compact within a class for objects they own themselves, such as free-list nodes and cache entries, where every pointer to the object is one the allocator wrote. For objects handed to the program the same argument fails: the allocator knows the class’s free objects and their holes, but not where the program’s pointers to a live object are, so moving it would leave them dangling. Managed runtimes with an exact object map can compact; a malloc heap cannot.
• Huge-page-backed heaps. Backing the heap with 2 MiB pages reduces the number of mappings and the page-table overhead, and makes holes of a few kilobytes irrelevant to the kernel’s view. It does not make the holes usable, but it changes the failure mode from an allocation failure to a footprint increase.

What to measure and when

The measurement that predicts trouble is the one taken at the moment of a failure. When an allocation returns null or the process is killed for exceeding a limit, the useful facts are the size that failed, the total free bytes at that moment, the largest free region, and the occupancy of the class that would have served it. An allocator with a statistics interface can report all four; without one, the information has to be reconstructed from a heap dump, which is a much slower path and often unavailable in the failing process.

The second useful measurement is the trend. A heap whose live fraction is falling while its live bytes stay flat is accumulating retention, and the accumulation is either a leak in the reachability sense or a policy that never releases. A heap whose live bytes rise while the live fraction stays flat is growing legitimately, and the only question is whether the growth is expected. Distinguishing these two from a footprint graph alone is not possible; it requires the free-space statistics alongside the resident size, which is why fragmentation measurement belongs with the mapping-level attribution rather than as a separate exercise.