= Memory block coalescing
<Memory block coalescing> merges adjacent free allocation blocks into a larger free block. It improves the allocator's representation and use of free space without moving intervening live objects. The mechanism is useful after deallocation, when a returned block may adjoin free neighbors. A <free list> records the resulting regions; it can be implemented using a list or another search structure.<Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and others>[Chapter17, §17.2, “Splitting and Coalescing”, printed pp.3–4]{ref}
Using half-open address intervals, two free blocks $[a,b)$ and $[b,c)$ can become $[a,c)$. Their usable bookkeeping lengths add: $(b-a)+(c-b)=c-a$. For an original example, suppose free intervals occupy offsets $[0,24)$ and $[40,80)$ while the intervening16-<byte> block is live. Releasing that middle block makes all of $[0,80)$ free, so merging its two neighbors produces an80-<byte> block. An occupied8-<byte> block after offset80 still separates this region from a later free interval.
An address-aware insertion can check the predecessor's end against the new block's start and the successor's start against its end. When both are adjacent, all three join. An implementation may delay merging, but a search that examines only unmerged entries can miss a sufficiently large contiguous region. Coalescing policy and allocation search therefore affect observed success as well as the physical occupancy pattern.
These examples omit block headers and other allocator metadata. A real merge must maintain those structures, preserve <memory alignment> guarantees and avoid treating an occupied or separately managed region as free. Coalescing does not cure a hole separated from its neighbor by a still-live allocation; that requires deallocation, a different placement strategy or a valid <memory compaction> mechanism.
Back to article page
