Coalescing Free Blocks

Splitting makes blocks smaller, and programs free them at unpredictable times. After enough churn a heap can hold plenty of free memory that is useless. After this lesson your allocator will merge neighbouring free blocks every time something is freed, so the heap can come back together.

External fragmentation

Here is a heap after a burst of allocations and frees, with each box showing a block's payload:

[free 50][used 100][free 50][used 200][free 100]

200 bytes are free, but the largest single free block is 100, so ALLOC 150 fails while twice that much memory sits idle. This is external fragmentation: memory lost not inside blocks but between them. The antidote is coalescing, merging adjacent free blocks back into one:

free the [used 100] in the middle:
[free 50][free 100][free 50][used 200][free 100]
[        free 50 + hdr + 100 + hdr + 50        ][used 200][free 100]

Merging costs nothing and gives back a header

Two neighbouring blocks each carry a header. When they become one block, the second header is no longer needed; its HDR bytes turn back into payload. So merging block A (size a) with the block B right after it gives a single block of size a + HDR + b, at A's address. The invariant from the last lesson still holds: HDR + size summed over all blocks equals the heap size.

INIT 500 ; ALLOC 70 ; ALLOC 90 ; FREE 8
8:70:free     86:90:used     184:316:free        (free 70, used 90, tail)
FREE 86  ->  the freed block touches a free block on EACH side:
8:70 + 8 + 90 = 168, then 168 + 8 + 316 = 492      8:492:free

Freeing a block whose neighbours are BOTH free is the case that turns three fragments into one, so a merge pass must keep going until no two adjacent blocks are both free; stopping after the first pair leaves a fragment behind.

When and how

Production allocators coalesce EAGERLY, at free time, because the neighbour checks are cheap if you can find the neighbours:

• The NEXT physical block is easy: it starts at addr + size + HDR, the header right after this block's payload.
• The PREVIOUS block is the hard direction. A size field only tells you how far FORWARD to step. The O(1) answer is Knuth's boundary tag: a duplicate of the size at the END of each block. That trick gets its own lesson, Boundary Tags.

This lesson's simulator keeps blocks in an address-ordered list, so one linear pass after every FREE can merge each run of consecutive free blocks.

Double free is an error, not a merge

FREE is only legal on a currently USED block. After a merge, the absorbed block's address does not exist any more: freeing it again must print BAD, exactly like freeing something that was never allocated. In C this mistake is a double-free vulnerability; glibc aborts with free(): invalid pointer when its integrity checks catch it. Your simulator gets to be the detector.

Common mistakes

• Merging only the first pair in a run, so freeing a block between two free ones leaves a fragment.
• Forgetting the header: the merged size is a + b, which loses HDR bytes per merge and breaks the invariant. It must be a + HDR + b.
• Merging blocks that are neighbours in the FREE LIST but not in memory. Adjacent means adjacent in address order, with nothing between them.
• Letting FREE succeed on an address that a merge removed.

Your exercise

The starter already allocates with splitting and marks blocks free; it calls coalesce() after every successful FREE, and that function is yours. The tests free blocks in every order, including the middle one last, and probe the heap with LARGEST to prove memory really came back together.