Fragmentation

An allocator can be fast and still starve its program. Fragmentation is HOW allocators waste memory, and it comes in two flavours. After this lesson your allocator will report both, with numbers the grader checks to four decimal places.

Internal fragmentation

Internal fragmentation is waste INSIDE allocated blocks. This allocator rounds every request up to a size class (16, 32, 64, 128, 256, 512 or 1024 bytes), and the slack is invisible to the program but real in RAM:

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

ALLOC 10 lands in class 16 and adds 6. When the block is freed its contribution disappears: the slack is no longer trapped inside an allocation, the whole block is simply free again.

External fragmentation

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. This lesson scores it as

external_frag = (free - largest_free) / free        (0 when nothing is free)

where free is the total of all free blocks and largest_free is the biggest one. One perfect free block scores 0.0000; dust approaches 1.

Rounding without floating point

REPORT prints the ratio with exactly four decimals, and the output is compared character by character, in six languages. Floating-point formatting is where languages disagree: for a ratio that lands exactly on a tie, such as 1/32 = 0.03125, one language rounds to 0.0312 and another to 0.0313. So do the arithmetic in integers and round half up:

q = (2 * (free - largest_free) * 10000 + free) / (2 * free)      (integer division)
print  q / 10000  "."  q % 10000 padded to 4 digits

For free = 336 and largest_free = 304 that gives q = 952, printed 0.0952. Use this rule exactly; it is also how you should print any exact decimal that must be byte-identical across languages.

A worked REPORT

INIT 400
ALLOC 30    -> 0     class 32, slack 2
ALLOC 30    -> 32    class 32
ALLOC 30    -> 64    class 32
FREE 32              [0:32 used][32:32 free][64:32 used][96:304 free]
REPORT
used=64 free=336 free_blocks=2 largest_free=304 internal_frag=4 external_frag=0.0952

used counts class sizes of live blocks (2 x 32). Internal fragmentation is 4: three blocks wasted 2 each, and the freed one took its 2 back. The two free blocks cannot merge because a used block sits between them, so 32 of the 336 free bytes are stranded behind the largest block: 32/336 = 0.0952.

The allocator underneath

Addresses start at 0 and there are no headers in this model; the point here is measurement. ALLOC rounds up to the class, takes the first free block that is large enough, and splits off any remainder as a new free block. FREE marks the block free and merges adjacent free blocks. A request over 1024 bytes, or one no free block can hold, prints OOM.

Fighting each flavour

• Internal: tighter size classes (jemalloc's 16, 32, 48, 64, 80 spacing), or slab caches that round nothing for a known type.
• External: coalescing, which you built; buddy systems, which 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 placement policy fixes. Valgrind and AddressSanitizer/LeakSanitizer catch them; heaptrack shows which call sites the bytes came from.

Common mistakes

• Adding slack on ALLOC and not subtracting it on FREE: a freed heap must report internal_frag=0.
• Using floating-point formatting and landing on the wrong side of a tie.
• Printing 0.0 or 0 instead of 0.0000 when nothing is fragmented.
• Counting free memory only from the tail instead of summing every free block.

Your exercise

The starter implements the allocator; you write the class lookup and the REPORT line. Hidden tests include a heap with five stranded blocks and a ratio of exactly 1/32.