the buddy system

Imagine a chocolate bar made of 16 squares that you can only break by snapping it cleanly in half. To give someone a single square, you snap the bar into two 8s, snap one 8 into two 4s, a 4 into two 2s, a 2 into two 1s, and hand over one. When pieces come back, you can glue two halves into the whole they came from — but only the two specific halves that were once together, their buddies. The buddy system manages memory exactly this way: every block is a power-of-two size, splitting always halves a block, and merging only ever rejoins a block with its one original partner.

Precisely: the allocator keeps free lists for each power-of-two block size (16 KiB, 32 KiB, 64 KiB, ...). To satisfy a request, it rounds up to the next power of two, then finds the smallest free block of at least that size; if that block is bigger than needed, it splits it in half, putting one half (the buddy) on the free list for the smaller size, and repeats until it has a block of the right size. Freeing is the reverse: when a block is freed, the allocator checks whether its buddy — the other half it was split from, found by simply flipping one bit in the block's address — is also free; if so, the two coalesce back into the next size up, and that check repeats up the chain. Because a block's buddy is computed by a single bit-flip of its address (buddy of a block at address A with size S is A XOR S), both splitting and the merge check are extremely fast.

The buddy system is the page-level allocator inside the Linux kernel and many others: it manages physical memory in power-of-two runs of pages and is what the slab allocator asks for its slabs. Its strength is fast, simple coalescing that fights external fragmentation well. Its honest weakness is internal fragmentation from the power-of-two rounding: a request for a 17 KiB region must be served by a 32 KiB block, wasting nearly half. That is the deliberate trade — coarse, rounded sizes in exchange for cheap, predictable splitting and merging.