Heap fragmentation: Foundations — Coding deep dive

Before you can follow the parent note Heap fragmentation, you must own every word and symbol it uses. We build each one from nothing, in an order where each rests on the one before.

1. A byte, and memory as a ruler of numbered boxes

Look at the figure: the boxes are drawn in a single row because that is the truth of it — memory is one-dimensional. Box 0, then box 1, then box 2, with no gaps in the numbering. When the parent note writes a heap "of 100 bytes", it means boxes 0 through 99.

Why the topic needs this: the entire idea of fragmentation is about positions along this ruler. "Adjacent", "contiguous", "a gap" — all of these are statements about box numbers being next to each other. Without the ruler picture, none of the later words mean anything.

2. Contiguous — the word that makes fragmentation possible

Why the topic needs this: the parent note's key sentence — "malloc must return a single contiguous range" — is the reason fragmentation exists at all. If memory could be handed out in scattered pieces, there would be no fragmentation problem.

3. The heap — the box-region you rent from

The freedom to free in any order is precisely what lets holes appear in awkward places. See malloc and free for the mechanics of these two functions.

Why the topic needs this: fragmentation is a heap phenomenon. The stack, freeing in strict order, never fragments — a fact the parent note states and we make sense of in section 7.

4. A "block", a "hole", and the free-list

The pair notation $(start, size)$ means: "a hole begins at box start and is size boxes long." So $(30, 30)$ means boxes 30, 31, ..., 59 are free — that is start = 30 and size = 30, giving the last free box as $30 + 30 - 1 = 59$ .

The half-open bracket $[a, b)$ the parent uses means the same run: boxes from a up to but not including b. So $[30, 60)$ = boxes 30 to 59. The square bracket [ includes a; the round bracket ) excludes b. We use it because then the length is simply $b - a$ with no "+1" to remember.

Recall Check: what boxes does

$[90, 100)$ cover, and how many? Boxes 90, 91, ..., 99 — that is $100 - 90 = 10$ boxes.

Why the topic needs this: the parent's simulation table tracks the free-list after every operation. You must read $(30, 30) + [90, 10)$ as "two separate holes: one of 30 boxes at position 30, one of 10 boxes at position 90."

5. Adjacent — the condition for merging

Why the topic needs this: "adjacent" is the exact word that decides whether two holes can become one. This single distinction separates a heap that heals itself from one that stays broken.

6. Coalescing — merging neighbour holes

Follow the figure top to bottom. In the top strip, freeing the middle block leaves a hole touching the existing right-hand hole; because they are adjacent, the allocator erases the boundary and writes one longer hole (bottom strip). This is why the ordering of your free calls matters so much: only neighbours merge.

Why the topic needs this: coalescing is the heap's only built-in defence against fragmentation. Understanding that it works only on neighbours explains every result in the parent note.

7. Allocation orders — why LIFO stays clean

When you free in LIFO order, each freed block is always the one touching the growing free region on its right, so every free coalesces immediately — the heap collapses back to one big hole. Free in a mixed order and you strand holes between still-live blocks. This is the difference the parent note demonstrates between "free B in the middle" (fragmenting) and "free C, B, A" (clean).

Why the topic needs this: the fix the parent recommends — "free in reverse order" — only makes sense once you see that reverse order guarantees adjacency at every step.

8. The math symbols: ceiling $⌈ \cdot ⌉$ , $r$ , $h$ , $a$

The internal-fragmentation formula uses four symbols. Take them one at a time.

Trace the figure for $r = 20, h = 8, a = 16$ : you need $20 + 8 = 28$ boxes. That is more than one 16-box quantum but less than two, so $⌈ 28/16 ⌉ = 2$ , giving $B = 2 \times 16 = 32$ . The bar shows 20 usable (green) + 8 header (yellow) + 4 dead (red) $= 32$ ; the wasted-to-you portion is $W = 32 - 20 = 12$ (the 8 header plus the 4 dead tail).

Recall Check the ceiling:

$r = 40, h = 8, a = 16$ — what is $B$ ? $r + h = 48$ ; $48/16 = 3$ exactly; $⌈ 3 ⌉ = 3$ ; $B = 3 \times 16 = 48$ . Waste $W = 48 - 40 = 8$ .

Why the topic needs this: internal fragmentation is defined by this formula. Every symbol in it must be crisp or the "12 bytes wasted" result is just magic.

9. NULL — the "no room" answer

Why the topic needs this: the punchline of external fragmentation — "malloc(40) returns NULL even though 40 bytes are free" — hinges on knowing NULL means failure, not an address.

Prerequisite map

Equipment checklist

I can say what a byte and an address are

A byte is one numbered box holding a number; its address is its position, counting from 0 along a single straight ruler of memory.

I can define contiguous

Boxes whose addresses are consecutive with no interruption — one unbroken run.

I know why malloc needs contiguous memory

An object of N bytes must sit in N boxes in a row; it cannot straddle a used region, so scattered free boxes can't serve one request.

I can read the pair notation (start, size) and the bracket [a, b)

(start, size) is a hole beginning at box start, size boxes long; [a, b) covers boxes a up to but not including b, of length b - a.

I can tell adjacent holes from non-adjacent ones

Adjacent = one ends exactly where the other begins, no box between; non-adjacent = a live block sits in between.

I know what coalescing does and its one condition

It fuses two holes into one bigger hole; it only works when the holes are physically adjacent.

I know why LIFO free order avoids fragmentation

Each freed block always touches the growing free region, so every free coalesces immediately and the heap returns to one big hole.

I can compute the ceiling of a number

Round it up to the next whole number; a number already whole stays put.

I can evaluate B = ceil((r+h)/a)*a and W = B - r

For r=20,h=8,a=16: r+h=28, ceil(28/16)=2, B=32, W=12.

I know what NULL signals

malloc returning NULL means it found no big-enough contiguous hole — request denied.

Connections

Heap fragmentation — the parent topic these foundations unlock
malloc and free — the rent/return functions that build and coalesce holes
Stack vs Heap — why the strict-order stack never fragments
Memory alignment — the source of the $a$ quantum in the waste formula
Memory leaks — a different bug: never returned, vs. returned but scattered