Coalescing Free Blocks

Splitting creates small blocks; programs free them at unpredictable times; and after enough churn a heap can hold plenty of free memory that is USELESS:

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

200 bytes are free, but the largest single free block is 100. ALLOC 150 fails while twice that much sits idle. This is external fragmentation — memory lost not inside blocks but BETWEEN them — and 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 200][used 200][free 100]        ALLOC 150 now succeeds

When and how

Production allocators coalesce EAGERLY — at free time — because the neighbor checks are cheap if you can find the neighbors:

• The NEXT physical block is easy: it starts at addr + size. Stepping forward by size is exactly how implicit-list allocators traverse the heap.
• The PREVIOUS block is the hard direction — a size field only tells you how far FORWARD to step, not backward. The O(1) answer is Knuth's boundary tag: duplicate the size at the END of each block (a footer), so the predecessor's metadata sits at a fixed negative offset. That trick gets its own lesson (Boundary Tags).

Our simulator keeps blocks in an address-ordered list, so we can use a simpler tactic: after every FREE, one linear pass merges each run of consecutive free blocks. Merged sizes simply add — this model charges no per-block header on split, so there is none to reclaim on merge:

[108:100 free][208:100 free][308:716 free]   ->   [108:916 free]

The pass must collapse the WHOLE run — 100 + 100 + 716 — not just the first pair it meets. Freeing a block whose neighbors are BOTH free is precisely the case that turns three fragments into one.

Double-free is an error, not a merge

FREE is only legal on a currently-USED block. Test 4 frees address 8 twice: the first prints OK (and the block coalesces with the tail into 8:1016:free), the second must print BAD — there is a free block AT address 8 now, but it is not an allocated one. In C this exact 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.

Your exercise

Test 2 is the three-way merge: allocate 100 three times (addresses 8, 108, 208, leaving tail 308:716), then FREE 108 and FREE 208. The grader expects BLOCKS to print exactly two lines: 8:100:used and 108:916:free. Three free lines (108:100:free, 208:100:free, 308:716:free) mean you never coalesced; 108:200:free followed by 308:716:free means your pass merges only one pair and missed the tail. Hidden test 7 frees in the order 8, then 208, then 108 — the middle-block-last order that only passes if freeing 108 merges BOTH directions at once, collapsing the whole heap back to a single 8:1016:free.