When an allocator frees a block, how do boundary tags let it merge with both neighbouring free blocks in constant time?

A general-purpose allocator carves blocks out of one contiguous region. When the program releases a block, the allocator's real work is not recording that the block is free — that is one bit — but deciding whether the block has just become part of a larger free region. Two adjacent free blocks that stay separate can never satisfy a request bigger than either of them, so merging on release is what keeps a long-lived heap able to answer large requests at all. ## Neighbour means address neighbour The neighbours that matter are **physical**: the block that ends exactly where this one begins, and the block that begins exactly where this one ends. That is a different relation from the free list. The free list links free blocks in insertion order, or size order, or whatever order the design chose; two blocks adjacent on the list may sit at opposite ends of the region, and two blocks adjacent in memory may be nowhere near each other on the list. Walking the list therefore cannot tell you who your neighbours are, and walking it anyway would make release cost time proportional to the number of free blocks. Going **forward** is easy, because every block already needs a header. One word holds the block's size and a couple of flag bits (allocated or free; often also whether the block below is free). Add that size to the block's own address and you land precisely on the next block's header. Going **backward** is the hard direction. Standing on a header there is nothing in it that says how far down the previous header lies — the previous block may be any size at all. ## The boundary tag Knuth's answer is to repeat the size at the **end** of the block as well as at the start: - the **header** sits immediately before the payload and holds `size` plus flags; - the **footer** — the boundary tag — occupies the block's last word and repeats the same `size` and free bit; - therefore the word immediately *below* any header is, by construction, the previous block's footer. Read that word, subtract the size it reports from the current block's address, and you are standing on the previous block's header. The step is two memory reads and a subtraction, regardless of heap size or block count. ## The release path, step by step 1. Mark the block free in its own header. 2. Read the word below the header. If the previous block is free, unlink it from the free list and extend the region being formed downwards to its header. 3. Compute the following block's address by adding the (possibly already extended) size. If that block is free, unlink it too and extend the region upwards. 4. Write the surviving header at the region's lowest address and the surviving footer at its highest, both carrying the summed size, and push the single resulting block onto the free list. The swallowed blocks' interior tags are not erased. They are simply never read again, because after step 4 no header points at them. | previous neighbour | next neighbour | result of the release | |---|---|---| | in use | in use | the block stays alone and joins the free list | | free | in use | one block; the previous block's header survives | | in use | free | one block; this block's header survives | | free | free | one block spanning all three; the previous header survives | ## What it costs and how the cost is trimmed - **Space.** A footer doubles the per-block tag. Many designs keep the footer only in free blocks and carry a *previous-block-is-free* bit in each header instead, so an allocated block pays one word and a free block — whose space is idle anyway — pays two. - **Unlinking must also be constant time.** Extending a region downwards means removing a block from the middle of the free list, so the list is doubly linked; a singly linked list would force a scan and undo the whole benefit. - **Immediate versus deferred merging.** Merging on every release keeps the heap tidy but costs work on a block that may be re-requested immediately. Some designs defer merging until a request fails, trading a tidier steady state for less work on hot release paths. ## Where it goes wrong A write one byte past the end of a payload lands on a footer, and a write just before a payload lands on a header. Either corrupts a size, and the next walk steps into the middle of a block and treats arbitrary bytes as a tag. The crash then appears far away from the code that caused it, which is why allocators with tag checking are worth their cost during development. The first and last blocks of the region also need sentinel tags marked permanently in use, or the walk steps outside the region entirely.