Boundary Tags

Donald Knuth introduced boundary tags in The Art of Computer Programming (vol 1, §2.5) to make coalescing on free O(1) in both directions.

The problem

Without boundary tags, when you free(p), you can:

• Find the NEXT block in O(1) — it sits at addr + size.
• Find the PREVIOUS block in O(n) — you have to walk from the heap start.

This makes coalescing the previous block slow, so many naïve allocators only coalesce the next neighbor.

The trick

Place BOTH a HEADER at the start AND a FOOTER at the end of every block. Both contain the same metadata: {size, is_free}.

+-----+--------+-----+-----+--------+-----+-----+--------+-----+
| HDR | payload| FTR | HDR | payload| FTR | HDR | payload| FTR |
+-----+--------+-----+-----+--------+-----+-----+--------+-----+
                    ^
              this is byte (block2.addr - HDR - FTR)
              which equals byte (block1.addr + block1.payload)

Now on free(B):

• Read B.addr - HDR - FTR to find the previous block's footer.
• If it says is_free=1, merge with the previous block — O(1).
• Then check the next block's header at B.addr + B.payload + FTR for forward coalescing.

Used by

• Doug Lea's dlmalloc (the basis of glibc's ptmalloc).
• Most textbook allocators (CS:APP §9.9.10 implements one).

The cost

Two extra words per block (header + footer) — 16 bytes overhead in a 64-bit allocator. For typical allocations (≥ 64 bytes) this is acceptable. Modern designs reduce it: jemalloc encodes the "free" flag in the page metadata, not per-block.

This lesson

You'll build an allocator with boundary tags and expose a PREV command that uses the tag trick to identify the previous block in O(1) — proving the technique works.