splitting and coalescing blocks

Picture a long shelf where you store boxes side by side. Two everyday moves keep it usable. If someone needs a small box and the only free gap is large, you split the gap: hand out the small piece they need and leave the leftover as a smaller free gap. And if two free gaps end up sitting right next to each other, you coalesce them: knock down the wall between and treat them as one bigger gap, so a future big box can fit. Splitting and coalescing are exactly these two moves for memory blocks, and together they keep the heap from rotting into useless little fragments.

Splitting happens on allocation. Suppose the smallest suitable free block is 128 bytes but the request is for 32. Rather than hand out the whole 128 (wasting 96 bytes inside the block — internal fragmentation), the allocator splits it: it carves off a 32-byte block to return, writes a new header for the remaining 96-byte block, and puts that remainder back on the free list. Coalescing happens on free. When you free a block, the allocator checks its immediate neighbours (using boundary tags to look left, and stepping forward by size to look right): for each neighbour that is also free, it merges them into one larger free block by combining their sizes and rewriting one header. So freeing three adjacent 64-byte blocks ends up as a single 192-byte free block, ready for a larger request.

Why this matters: without coalescing, a program that allocates many small blocks and frees them would leave the heap full of small free holes — plenty of total free memory, but no single piece big enough for a large request (that is external fragmentation). Coalescing is the main defence against it. The honest tension: coalescing on every free costs time, and aggressive splitting creates more tiny blocks. Many allocators therefore defer coalescing (batch it) or skip it in their fast small-object path and only coalesce larger regions, trading a little fragmentation for speed.