THE FOLD / RESPAWN / ROLLBACK / THE BUDDY ALLOCATOR
THE BUDDY ALLOCATOR
merging is cheap because most merges are forbidden
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Split memory in half, and half again, until a block is just big enough. Each block then has exactly one partner — its buddy — and merging is possible only with that one. Finding it is not a search: it is a single XOR.
LIT verified live. A 1,048,576-byte arena, 64-byte minimum block, 200 allocations of random sizes. Every buddy address satisfies
LIT verified live. A 1,048,576-byte arena, 64-byte minimum block, 200 allocations of random sizes. Every buddy address satisfies
buddy = addr XOR size — checked on all 209 splits, 0 exceptions. 51,644 bytes were requested and 68,800 handed out: 17,156 bytes of internal waste, 24.94%, which is the price of rounding to powers of two. Freeing all 200 coalesces the arena back to a single whole block with 0 stray fragments.2 HOW IT WAS WEAVED · AI + HUMAN
The buddy system is Harry Markowitz’s (1963), described by Knuth in TAOCP vol. 1; Linux still allocates physical pages this way.
AVAN (AI) checked the two claims that are usually asserted side by side and are quite different in kind.
AVAN (AI) checked the two claims that are usually asserted side by side and are quite different in kind.
addr XOR size is an identity — it either holds always or the allocator is broken, and it held 209 times out of 209. Full coalescence is a property of a run, and it is the one that actually fails in practice when a single long-lived block sits in the middle. Here every block was freed, so the arena came back whole; that is a real result about this run and not a general guarantee.3 ONE DIMENSION
The arena, split down to blocks. Each level halves.
4 TWO DIMENSIONS · INTERACTIVE
Allocate and free. Watch the buddies merge.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a tree of halvings.
AVAN’s addition (the inverse-companion): the forward reading is that the buddy system makes merging cheap. The inverse is that it makes merging cheap by making most merges illegal. Two adjacent free blocks of the same size usually cannot combine — only the one partner fixed at allocation time will do. The XOR is fast because the answer was decided before the question, and the 24.94% waste is the same decision seen from the other side. Read backwards, this is not an allocator that found a clever merge rule; it is one that shrank the space of possible merges until the rule became arithmetic.
LIT a 1,048,576-byte arena with 64-byte minimum blocks and 200 random allocations: every buddy address satisfies buddy = addr XOR size, checked on all 209 splits with 0 exceptions; 51,644 bytes were requested and 68,800 handed out, 17,156 bytes of internal waste at 24.94%, and freeing all 200 coalesces the arena back to a single whole block with 0 stray fragments
FIG The buddy system is Harry Markowitz's (1963), described by Knuth in TAOCP vol. 1; Linux still allocates physical pages this way. AVAN checked two claims that are usually asserted together but differ in kind. buddy = addr XOR size is an identity - it holds always or the allocator is broken, and it held 209 of 209. Full coalescence is a property of a run, and it is the one that fails in practice when a long-lived block sits in the middle; here every block was freed, so the arena came back whole, which is a real result about this run and not a general guarantee.
FIG The buddy system is Harry Markowitz's (1963), described by Knuth in TAOCP vol. 1; Linux still allocates physical pages this way. AVAN checked two claims that are usually asserted together but differ in kind. buddy = addr XOR size is an identity - it holds always or the allocator is broken, and it held 209 of 209. Full coalescence is a property of a run, and it is the one that fails in practice when a long-lived block sits in the middle; here every block was freed, so the arena came back whole, which is a real result about this run and not a general guarantee.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of ROLLBACK · David Lee Wise (ROOT0), with AVAN