Heap fragmentation: Worked examples — Coding deep dive

This is the "roll up your sleeves" child of Heap fragmentation. The parent gave you the ideas — external vs internal fragmentation, coalescing, the block-size formula. Here we drive every one of those ideas through concrete numbers, and we deliberately hit every corner case the topic can throw at you: each sign of the block formula, zero-size and degenerate inputs, the limiting behaviour when requests get huge, a real-world word problem, and an exam-style trick.

Before any example, let us re-earn the two tools we lean on, in plain words.

The scenario matrix

Every worked example below is tagged with the matrix cell it covers, so you can see the whole space is filled.

Cell	What varies	Extreme it probes	Example
A External-fail	free total ≥ request, holes non-adjacent	the classic NULL-despite-free	Ex 1
B Coalesce-save	free in adjacent order	holes merge back to one	Ex 2
C LIFO vs random	same allocs, two free orders	order decides fate	Ex 3
D Internal $W > 0$	$r + h$ overshoots a boundary	worst-case waste	Ex 4
E Internal $W = 0$	$r + h$ lands exactly on a boundary	zero-waste degenerate	Ex 5
F Zero / tiny input	$r = 0$	header-only block	Ex 6
G Limiting behaviour	$r \to$ large	waste fraction $\to 0$	Ex 7
H Word problem	game-server churn	real-world external frag	Ex 8
I Exam twist	"total free = request ⇒ success?"	disprove with a counter-layout	Ex 9

We touch every sign of $W$ (positive in D, zero in E), zero input (F), the large limit (G), both free orders (C), and the two flavours of fragmentation (external: A,B,C,H,I; internal: D,E,F,G).

Ex 1 — Cell A: external fragmentation forces NULL

Worked example The classic failure

Heap of 100 bytes, one hole $[0, 100)$ . Do (first-fit, no headers for clarity): A=malloc(30); B=malloc(30); C=malloc(30); free(B); Then malloc(40). Does it succeed?

Forecast: total free after free(B) is $30 + 10 = 40$ . Guess yes or no before reading.

A=malloc(30) takes $[0, 30)$ . Free hole shrinks to $[30, 100)$ . Why this step? First-fit takes bytes from the front of the first hole large enough.
B=malloc(30) takes $[30, 60)$ . Free hole $[60, 100)$ .
C=malloc(30) takes $[60, 90)$ . Free hole $[90, 100)$ — that's 10 bytes.
free(B) returns $[30, 60)$ . Its left neighbour $A$ (live) and right neighbour $C$ (live) are not free, so nothing coalesces. Free list = $[30, 60)$ and $[90, 100)$ . Why this step? Coalescing needs a free physical neighbour; both of B's neighbours are in use.
malloc(40): scan holes. $[30, 60) = 30$ bytes ✗; $[90, 100) = 10$ bytes ✗. No single hole ≥ 40 ⇒ NULL. Why this step? malloc returns one contiguous range; it cannot span the live block $C$ at $[60, 90)$ .

Verify: largest single hole $= max (30, 10) = 30 < 40$ , yet total free $= 30 + 10 = 40 \geq 40$ . The inequality on the max is what decides success — and it fails. This is external fragmentation.

Ex 2 — Cell B: coalescing rescues the same request

Worked example Free the middle-right neighbour instead

Same start as Ex 1 through step 3 (holes: only $[90, 100)$ , blocks $A [0, 30), B [30, 60), C [60, 90)$ ). Now do free(C); free(B); then malloc(40).

Forecast: will the 40-byte request succeed now?

free(C) returns $[60, 90)$ . Its right neighbour is the free hole $[90, 100)$ — adjacent! Coalesce: $[60, 90) \cup [90, 100) = [60, 100)$ , a 40-byte hole. Why this step? $C$ 's right edge (90) equals the hole's left edge (90) ⇒ physically touching ⇒ merge.
free(B) returns $[30, 60)$ . Its right neighbour is now the free hole $[60, 100)$ — adjacent again. Coalesce: $[30, 100)$ , a 70-byte hole.
malloc(40): hole $[30, 100)$ has 70 ≥ 40 ⇒ success, returns $[30, 70)$ .

Verify: largest hole $= 70 \geq 40$ ⇒ succeeds — the exact opposite of Ex 1, with the same total free bytes before the request. Only the free order changed.

Ex 3 — Cell C: same allocations, two destinies

Worked example Order decides everything

Allocate $A, B, C$ each 30 bytes into 100. Compare random order (free(A); free(C);) vs LIFO/stack order (free(C); free(B); free(A);). Report the largest free hole after each.

Forecast: which order leaves one big clean hole?

Random: free(A) → hole $[0, 30)$ (neighbour $B$ live, no merge). free(C) → hole $[60, 90)$ merges with the tail $[90, 100)$ → $[60, 100)$ . Live block $B [30, 60)$ sits between. Holes: $[0, 30)$ and $[60, 100)$ . Largest $= 40$ . Why this step? $A$ and $C$ are not adjacent — the live $B$ is the fence between them.
LIFO: free(C) → $[60, 100)$ . free(B) → $[30, 60)$ merges right → $[30, 100)$ . free(A) → $[0, 30)$ merges right → $[0, 100)$ . One hole, largest $= 100$ . Why this step? Each freed block always touches the growing right-hand hole, so every free coalesces. This is exactly why the stack never fragments — it is strict LIFO.

Verify: LIFO largest hole $= 100$ (fully defragmented) vs random $= 40$ . Same three allocations, different free order, opposite fragmentation. See Pool allocator / Arena allocator for structures that enforce clean freeing.

Ex 4 — Cell D: internal fragmentation, worst-ish case

Worked example Overshooting a boundary

$r = 20$ , header $h = 8$ , alignment $a = 16$ . Find block size $B$ and waste $W$ .

Forecast: you asked for 20 — how many bytes actually get consumed?

Add the header: $r + h = 20 + 8 = 28$ . Why this step? The allocator must store its own 8-byte bookkeeping inside the block.
Round up to a multiple of 16: $⌈ 28/16 ⌉ = ⌈ 1.75 ⌉ = 2$ . So $B = 2 \cdot 16 = 32$ . Why ceiling and not round? 28 does not fit in one 16-unit; you must take two, even though the second is barely used. Regular rounding of 1.75 also gives 2 here, but $⌈ \cdot ⌉$ is the correct rule in general (e.g. 1.1 → 2, not 1).
Waste $W = B - r = 32 - 20 = 12$ bytes lost inside every such allocation.

Verify: $B = 32$ is a multiple of $a = 16$ ✓, and $B \geq r + h = 28$ ✓ with no smaller multiple ( $16 < 28$ ) working ✓. Waste fraction $= 12/32 = 37.5%$ . See Memory alignment — the root cause.

Ex 5 — Cell E: the zero-waste boundary case

Ex 6 — Cell F: zero-size request `malloc(0)`

Ex 7 — Cell G: the limiting behaviour, huge request

Worked example Waste fraction as

$r$ grows With $h = 8$ , $a = 16$ , compute the waste fraction $W / B$ for $r = 1024$ , and argue the limit as $r \to \infty$ .

Forecast: does big-object allocation waste a lot or a little, proportionally?

$r + h = 1024 + 8 = 1032$ . $⌈ 1032/16 ⌉ = ⌈ 64.5 ⌉ = 65$ , so $B = 65 \cdot 16 = 1040$ .
$W = 1040 - 1024 = 16$ ; fraction $W / B = 16/1040 \approx 0.01538 = 1.538%$ . Why this step? The overhead ( $h$ + rounding) is a fixed handful of bytes, but $r$ is huge — so proportionally it shrinks.
Limit: overhead $\leq h + a$ (header plus at most one extra alignment unit), a constant. So $W / B \leq (h + a) / (r) \to 0$ as $r \to \infty$ . Why this tool (a limit)? We want the trend, not one value — a limit answers "what does the fraction approach as requests get arbitrarily large?"

Verify: $1.538% ≪ 37.5%$ from Ex 4. Internal fragmentation hurts small objects, becomes negligible for large ones — motivating pools for many small same-size objects rather than raw malloc.

Ex 8 — Cell H: real-world word problem

Worked example Game-server projectile churn

A server pool of 240 bytes holds bullet objects. Bullets are allocated first-fit. Sequence: spawn bullets $b_{1}, b_{2}, b_{3}, b_{4}$ each 60 bytes (fills the pool), then bullets $b_{2}, b_{4}$ despawn (free). A new big effect object needs 120 contiguous bytes. Fits?

Forecast: two freed 60-byte bullets = 120 free — surely the effect fits?

Layout after 4 spawns: $b_{1} [0, 60), b_{2} [60, 120), b_{3} [120, 180), b_{4} [180, 240)$ . Pool full.
free(b_2) → hole $[60, 120)$ ; neighbours $b_{1}, b_{3}$ live ⇒ no merge. free(b_4) → hole $[180, 240)$ ; left neighbour $b_{3}$ live, right is the pool end ⇒ no merge. Why this step? The alternating live/free pattern is the classic fragmentation generator.
Holes: $[60, 120) = 60$ and $[180, 240) = 60$ , separated by live $b_{3}$ . Largest $= 60 < 120$ ⇒ NULL, effect cannot spawn.

Verify: total free $= 60 + 60 = 120 =$ request, yet largest hole $= 60 < 120$ ⇒ fails. A same-size Pool allocator would store all 60-byte bullets and refuse to mix a 120-byte object into that pool — sidestepping the problem entirely. Compacting Garbage collection would instead move $b_{3}$ to fuse the holes.

Ex 9 — Cell I: the exam twist (disprove a plausible claim)

Recall Quick self-test

Success of malloc(n) depends on which quantity? ::: The size of the largest single contiguous hole, not total free bytes. For r=20, h=8, a=16, the wasted bytes are? ::: 12 For r=24, h=8, a=16, the rounding waste is? ::: 0 (only the 8-byte header is overhead) malloc(0) with h=8, a=16 carves a block of size? ::: 16 bytes (all overhead) As r grows large, W/B tends to? ::: 0

Connections

Heap fragmentation — the parent topic these examples drill
malloc and free — the first-fit allocator every example simulates
Stack vs Heap — why LIFO (Ex 3) never fragments
Memory alignment — the $a$ in the block formula (Ex 4–7)
Pool allocator / Arena allocator — the fixes for Ex 8
Garbage collection — compaction that would rescue Ex 8
Memory leaks — contrast: leaked ≠ fragmented