Visual walkthrough — Heap fragmentation

---

Step 1 — Draw the heap as a row of boxes

WHAT. Before any symbol, a picture. The heap is just a long strip of memory. We will draw it as 100 little boxes, numbered 0 to 99. Box number = the address = "how far along the strip this byte sits". A filled box ■ means in use; a dot · means free.

WHY a straight line? Because memory addresses are one after another, like house numbers on a single street. This straightness is the whole story: a chunk of memory is a run of neighbouring boxes, and "neighbouring" will turn out to be everything.

PICTURE. Look at the strip — 100 empty boxes, one address label under a few of them. Nothing is used yet. This single empty run is one hole: a maximal stretch of free boxes.

The notation [0, 100) reads "start at box 0, up to but not including box 100" — so it covers boxes 0…99, a run of 100.

---

Step 2 — malloc(n) bites off the front of a hole

WHAT. Call malloc(30). The allocator walks its list of holes, finds the first one big enough (this rule is called first-fit), and carves 30 boxes off its front. Those boxes become block A.

WHY first-fit? Because scanning stops at the first hole that fits — it is the simplest, fastest rule. Any fitting rule would show the same fragmentation later; first-fit just makes the story concrete.

PICTURE. Boxes 0…29 are now filled (that is A). The single hole shrank to [30, 100), a run of 70.

$$\underset{\text{ask for 30 boxes}}{\underbrace{\text{malloc}(30)}}⟶\underset{\text{30 used boxes}}{\underbrace{A=[0,30)}},\underset{[30,100)}{\underbrace{\text{hole}=[70\text{ left}]}}$$

• $[0,30)$ — the boxes A now owns; nobody else can touch them until A is freed.
• $[30,100)$ — what is left, still one clean hole of size $70$.

---

Step 3 — Fill up with three same-size blocks

WHAT. Two more malloc(30) calls: block B takes [30,60), block C takes [60,90). After A, B, C we have three live blocks packed together and one small tail hole [90,100) of size 10.

WHY pack them? So the picture is dense and honest — this is what a busy program looks like: many blocks live at once, holes squeezed to the edges.

PICTURE. Three coloured runs A, B, C fill boxes 0…89; only [90,100) remains free.

$$A=[0,30),B=[30,60),C=[60,90),\text{hole}=[90,100)$$

Notice B sits wedged between A and C. Remember that word wedged — it is about to matter.

---

Step 4 — free(B) opens a hole in the MIDDLE

WHAT. We free(B). Boxes [30,60) go back to free. Now there are two holes: [30,60) (size 30) and [90,100) (size 10).

WHY does this hurt? The freed hole is surrounded — A on its left, C on its right. It is trapped. It cannot join hands with the other hole because C stands between them.

PICTURE. A live, a 30-box gap, C live, then a 10-box gap. The two dotted regions are not touching.

Total free right now:

$$\underset{[30,60)}{\underbrace{30}}+\underset{[90,100)}{\underbrace{10}}=\underset{\text{free bytes}}{\underbrace{40}}$$

Forty boxes are free. Hold that number.

---

Step 5 — The failure: malloc(40) returns NULL

WHAT. Ask for malloc(40). The allocator needs 40 boxes in one unbroken run. It checks each hole:

• Hole [30,60) → size 30. $30<40$. ✗
• Hole [90,100) → size 10. $10<40$. ✗

No single hole fits. malloc returns ==NULL== — even though 40 free boxes exist.

WHY can't it use both holes? Because malloc promises a contiguous run: the pointer it returns must let you walk 40 steps forward without ever leaving your block. The 40 free boxes are split 30 + 10 on opposite sides of C. You cannot store a 40-box object half here and half there.

PICTURE. The requested 40-box bar (shown floating above) is longer than either gap. It simply does not fit in either slot.

This is the parent's central result, now derived from box one: free memory can exist and still be unusable, because it is broken into non-adjacent pieces.

---

Step 6 — The cure that doesn't work vs. the one that does: coalescing

WHAT. Coalescing = when you free a block, the allocator peeks at the box immediately left and immediately right; if either is already a hole, it fuses them into one bigger hole.

WHY it can save us — sometimes. Coalescing only merges neighbours. So the order you free in decides everything.

PICTURE — two timelines side by side:

• Bad order (top): we freed B first (trapped, no neighbour is free) → stuck at 30 + 10.
• Good order (bottom): free in reverse of allocation — free C, then B, then A. Each free touches the growing right-hand hole and fuses. The heap heals back to one clean [0,100).

Watch the good order box-by-box:

$$\begin{array}{l}\text{free }C:[60,100)\text{(C’s 30 + tail 10 fuse)}\\ \text{free }B:[30,100)\text{(B joins the run on its right)}\\ \text{free }A:[0,100)\text{(A joins — one whole hole again)}\end{array}$$

Reading each line: the freed block's right neighbour was already free, so the two share an edge and merge. That freeing-newest-first pattern is LIFO / stack order — the same discipline the stack uses automatically, which is why the stack never fragments.

---

Step 7 — The other flavour: internal fragmentation (waste hidden inside)

WHAT. Even a single malloc wastes memory. Real allocators refuse odd sizes: they round every request up to a fixed step (for alignment and to stash a bookkeeping header). So you ask for r boxes, they set aside a bigger block, and the extra tail inside your block is dead space.

WHY round up? Hardware reads memory fastest at aligned addresses (multiples of a), and the allocator needs h header boxes to remember the block's size. Both force sizes to a grid.

PICTURE. Request r = 20. Add header h = 8 → need 28. The grid step is a = 16. Twenty-eight does not fit in one 16-box unit, so we must take two units = 32. Your 20 sit inside; 32 − 20 = 12 boxes are wasted and locked inside a live block — no coalescing can ever reach them.

---

The one-picture summary

One board, the whole story: a full strip, a mid-strip free, the fatal malloc(40), the LIFO cure, and the internal-waste inset — external fragmentation (gaps between blocks) and internal fragmentation (waste inside a block) side by side.

Recall Feynman retelling — say it to a 12-year-old

Picture a shelf with 100 slots. You put in three toy boxes A, B, C, one after another, packed tight. Now you take out the middle box B. There is a hole where B was, and a tiny hole at the very end — 40 empty slots in total. But your new toy needs 40 slots all in a row, and box C is standing right in the middle of your empty slots. So even though 40 slots are empty, the toy won't go in. That's external fragmentation. Now here's the trick: if instead you take toys out newest-first (C, then B, then A), each empty slot touches the last one and they merge into one big empty space again — no fragmentation. Separately, the shelf only accepts toys in pairs of slots plus a name-tag slot, so a toy needing 20 slots actually grabs 32 and wastes 12 forever inside its own spot — that's internal fragmentation, and no amount of tidying frees those 12 until you remove the whole toy.

Recall

Total free = 40, holes are 30 and 10 around block C. Does malloc(40) succeed? ::: No — no single contiguous hole is ≥ 40, so it returns NULL. Which free order heals the heap to one hole? ::: LIFO / stack order (free C, then B, then A). For r=20, h=8, a=16, what block size and waste? ::: B = 32, W = 12 boxes.

---

Connections

• malloc and free — the allocator carving and fusing the holes we drew
• Stack vs Heap — why the stack (strict LIFO) never hits Step 5
• Memory alignment — the grid step a behind Step 7's internal waste
• Memory leaks — leaked = never freed; fragmented = freed but scattered
• Pool allocator / Arena allocator — same-size or bulk strategies that dodge Step 5
• Garbage collection — compacting collectors physically move blocks to erase the gaps