Boundary Tags

The coalescing lesson could find the NEXT block easily and still needed a list to find the PREVIOUS one. After this lesson you will have a heap with no block list at all: the blocks are laid out in memory with a tag at each end, and a free can merge with both neighbours in constant time by reading the bytes next to it.

The problem Knuth solved

A header sits at the START of a block, so a block can step forward: the next header is at address + size + overhead. Stepping backward is impossible, because nothing at the freed block says how big the previous one was or where it starts. Without a trick, free has to walk the heap from the beginning to find its predecessor, which is O(n), so many naive allocators only merge forward.

Knuth's answer (The Art of Computer Programming, vol 1, section 2.5) is the boundary tag: write the same {size, state} word at the END of every block as well. Then the word just before any block's header is the previous block's footer, and it says everything:

byte:   0     8            8+a     16+a    24+a         24+a+b
        [ HDR ][ payload a ][ FTR ][ HDR ][ payload b ][ FTR ]
        |<----- block A ----------->|<------ block B ------>|
                              ^                ^
                A's footer = d - 16        d = B's data address

From B's data address d: A's footer is at d - 16. If it says A has payload pa, A's data starts at d - 16 - pa.

The model

Every block is HDR = 8 bytes of header, a payload, and FTR = 8 bytes of footer, so each block costs 16 bytes of overhead. A tag is one integer word: payload * 2 + used, where used is 1 for an allocated block and 0 for a free one. (Real allocators round sizes to multiples of 8, so the low bits are free to carry flags; our sizes are arbitrary, so we shift instead.) The header and footer of a block always hold the same tag.

The heap is a table of tag words indexed by byte address; only tag positions hold anything. INIT n writes one free block: header at 0, data at 8, payload n - 16, footer at n - 8. A worked layout for INIT 200 then ALLOC 40:

INIT 200      tag at 0 = 368 (184*2, free)           tag at 192 = 368
ALLOC 40      the block splits; remainder = 184 - 40 - 16 = 128
   used block, data 8:   tag at 0 = 81  (40*2+1)     tag at 48  = 81
   free remainder, data 64 (= 8 + 40 + 16):
                         tag at 56 = 256 (128*2)     tag at 192 = 256

Splitting must WRITE all four tags. The old footer position (192) is now the remainder's footer and the old header is now the used block's; the used block needs a brand-new footer at 48 and the remainder a brand-new header at 56. A split follows the same threshold as before: only if the remainder payload p - m - 16 is at least MINP = 16.

Merging in both directions

When block B at data address d is freed:

1. Next: B's own header gives its payload pb; the next block's header is at d + pb + 8. If that block exists (the address is inside the heap) and its tag says free, absorb it.
2. Previous: if d > 8, read the word at d - 16. If it says free, absorb B into that block.

Merging blocks of payload x and y gives one block of payload x + 16 + y (the two tags in the middle become payload again), and BOTH end tags of the result must be rewritten: the header at the front and the footer at the back. After one merge the block you are holding has a new size, so the second merge must use it.

Cost

Two words per block, 16 bytes in a 64-bit allocator, is steep for small allocations. glibc keeps the footer only in FREE chunks and stores a "previous in use" flag in the next header; dlmalloc is the classic boundary-tag allocator.

The commands

PREV <d> reads the footer before d's header and prints the previous block as <data>:<payload>:<state>, or NONE for the first block. NEXT <d> steps forward the same way (NONE for the last block). TAG <d> prints the raw header and footer words, hdr=<w> ftr=<w>. All three print BAD if <d> is not the data address of a block.

Common mistakes

• Treating the overhead as 8 instead of 16 when stepping: the previous block's data is d - 16 - pa, not d - 8 - pa.
• Rewriting only the header on FREE. The footer is what the NEXT block reads later, so a stale footer makes PREV report a freed block as used.
• Forgetting the footer of a block that was just split: the used block must get a new footer where its payload ends.
• After merging with the previous block, writing the result's tags at the freed block's address instead of the previous block's.

Your exercise

The starter holds the tag table, set_block to write both tags of a block, and a heap walk. You write the split in alloc, the two merges in free, and prev. The tests read raw tags after frees and splits, so a footer you forgot to update will show up in TAG or PREV.