邊界標籤（boundary tag）

有個棘手的問題。當你 free() 一個區塊時，你會很想把它和相鄰的空閒區塊合併成一個更大的區塊（這樣之後才能滿足大型請求）。和你後面的區塊合併很容易——你可以越過自己的大小往前讀它的標頭。但和你前面的區塊合併卻很難：你只有一個指向自己起點的指標，沒有任何東西告訴你前一個區塊從哪裡開始、有多大。你得從堆積最前面一路走過來才能找到左鄰居。邊界標籤（boundary tag）正是讓這個左鄰居查找變成瞬間完成的巧妙技巧。

這個出自 Donald Knuth 的技巧，是把區塊的大小與空閒/使用中旗標存兩次：一次放在區塊最開頭的標頭（header）裡，另一次再放在區塊最末端的尾標（footer，也就是邊界標籤）裡。現在考慮釋放位址 p 處的區塊。前一個區塊的尾標就坐落在緊接於 p 的標頭之前的那幾個位元組。於是你讀那幾個位元組，得知前一個區塊的大小以及它是否空閒；若它是空閒的，你就能直接跳回它的標頭（前一個區塊起點 = p 的標頭減去那個大小）並合併——全在常數時間內完成，無須掃描。尾標是一份刻意放在邊界上的重複中介資料，正是為了讓下一個區塊能越過它往回看。

邊界標籤正是讓雙向常數時間合併成為可能的關鍵，它出現在教科書配置器以及 glibc 的 malloc 中。誠實的代價：每個區塊現在在標頭之外又多帶一個字組的開銷（尾標），對大量小型配置很傷。現代配置器常對使用中的區塊省掉尾標（你只需要在空閒區塊上放尾標，因為你只會併入空閒的鄰居），或乾脆改用分離式儲存來完全避開它——在分離式儲存中，同一類別的區塊從不合併。所以邊界標籤是一項漂亮的經典技術，而非通用必需品。