splitting and coalescing blocks

An allocator is constantly reshaping its pool of free memory to match the requests it gets. Two operations do most of that reshaping. Splitting is cutting a large free block into a smaller piece for you plus a leftover free piece. Coalescing (also spelled coalescing, sometimes called merging) is the reverse: gluing two adjacent free blocks back into one larger free block. Together they keep the free pool flexible without constantly going back to the kernel.

Splitting, concretely: suppose the smallest free block on hand is 100 bytes and you ask for 24. Rather than waste 76 bytes by giving you the whole block, the allocator carves off a 24-byte piece (plus its header) for you and turns the remaining bytes into a smaller free block, which it puts back on the free list for a future request. Coalescing happens at free time and fights the damage splitting can cause. When you free a block, the allocator checks whether the blocks physically adjacent to it in memory are also free; if a neighbor is free, it merges them into a single larger free block. Without coalescing, a long run of allocate-then-free would leave the heap chopped into a confetti of tiny free fragments — external fragmentation — and a later large request would fail even though there was plenty of total free space. Merging adjacent holes back together restores big contiguous regions.

The catch is that coalescing only works on blocks that are physically adjacent, so the allocator needs to know each block's size and its neighbors. That is why blocks carry headers (and sometimes footers) recording their size and free/used status — so that from one block the allocator can compute where the next one begins and whether it can be merged. Splitting and coalescing are the everyday machinery by which a real allocator balances satisfying requests against keeping memory from fragmenting.