Fragmentation

An allocator can be fast and still starve its program. Fragmentation is HOW allocators waste memory, and it comes in exactly two flavors. This lesson makes you measure both, with formulas the grader checks to four decimal places.

Internal fragmentation is waste INSIDE allocated blocks. Our allocator rounds every request up to a size class (16, 32, 64, ..., 1024); the slack is invisible to the program but real in RAM:

internal_frag = sum over LIVE blocks of (class - requested)

ALLOC 10 in class 16 adds 6. When a block is freed, its contribution is SUBTRACTED — the slack is no longer trapped inside an allocation; the whole block is simply free again.

External fragmentation is free memory shattered into pieces too small to use. Total free space can be huge while the largest single block is tiny. We quantify the shatter as:

external_frag = 1 - largest_free / total_free      (0 if nothing is free)

One perfect free block scores 0.0000; dust approaches 1.

Walk the numbers (this is test 4)

INIT 1024
ALLOC 10 x3     [0:16 used][16:16 used][32:16 used][48:976 free]
                 each adds 6 internal frag -> 18
FREE 16         [0:16 used][16:16 FREE][32:16 used][48:976 free]
                 internal: 18 - 6 = 12
REPORT
used=32 free=992 free_blocks=2 largest_free=976 internal_frag=12 external_frag=0.0161

used counts the class sizes of live blocks (2 x 16 = 32). The two free blocks — 16 bytes mid-heap, 976 at the tail — cannot merge because a used block sits between them, so external frag is 1 - 976/992 = 0.016129..., printed as 0.0161. The mechanics around the metrics are the ones you already built: an address-ordered heap starting at 0 (no headers in this model), first-fit on the class-rounded size, split off the remainder, coalesce adjacent free blocks on FREE, and OOM when no class fits the request or no free block fits the class.

Fighting each flavor

• Internal: tighter size classes (jemalloc's 16/32/48/64/80 spacing), or slab caches with zero rounding for one known type.
• External: coalescing (you built it), buddy systems that merge by construction, or compaction — physically moving live blocks together. Garbage-collected languages compact routinely; C and C++ cannot, because every raw pointer into a moved block would dangle.
• Leaks are a third problem — blocks never freed at all, which no fragmentation strategy fixes. Valgrind and AddressSanitizer/LeakSanitizer catch them; heaptrack and jemalloc's profiler show which call sites the bytes came from.

Your exercise

REPORT is compared as one exact string: used=<u> free=<f> free_blocks=<b> largest_free=<l> internal_frag=<i> external_frag=<x.xxxx> — always four decimals, so format with something like Python's f"{x:.4f}" (0.0000, never 0.0 or 0). The dedicated trap is test 3: ALLOC 10, FREE 0, REPORT must print exactly used=0 free=1024 free_blocks=1 largest_free=1024 internal_frag=0 external_frag=0.0000. If your line says internal_frag=6, you accumulated slack on ALLOC but forgot to subtract it on FREE — the single most common failure on this exercise. Hidden test 5 checks the accounting mid-flight: INIT 100, ALLOC 50 (class 64) must report used=64 free=36 ... internal_frag=14.