How the Linux kernel slices and recombines physical memory into power-of-two blocks — fast, fragmentation-resistant, and elegantly recursive. Watch the algorithm split, allocate, and merge in real time.
The kernel manages physical RAM in fixed-size pages — usually
4 KiB each. The buddy allocator groups them into blocks whose size is always
2ⁿ × pages. We call n the order.
An order-0 block is one page. Order-1 is two contiguous pages. Order-2 is
four. Linux typically goes up to order 10 — a 4 MiB chunk of 1024 pages.
Every block at order n has a buddy: the adjacent block
it would merge with to form a single order-n+1 block.
For each order, the allocator keeps a doubly-linked list of currently free blocks.
The whole structure lives in struct zone.free_area[MAX_ORDER] —
one entry per order. Allocating a block is a head-pop; freeing is a head-push.
Initially, all of memory might sit as a single huge block at the top order. As demand arrives, blocks get split downward; as memory is released, they get merged upward.
Suppose you ask for an order-1 block (2 pages). The allocator looks at
free_area[1]. If it's empty, it walks upward until it
finds a non-empty list — say, order 4. It pops that block, then splits
it in half: one half goes back onto free_area[3], the other
gets split again, and again, until we have a block of the requested order.
Press step below to watch a request for an order-1 block cascade down through three splits.
Two blocks of order n are buddies if their starting addresses
differ in exactly one bit — the bit at position n
(counting in pages, from zero). To find the buddy of a block at index
i, you simply XOR with 2ⁿ:
Freeing is the mirror image of allocation. When a block is released, the allocator looks at its buddy. If the buddy is also free at the same order, they coalesce into a block one order larger. Then it checks that block's buddy — and the merge can ripple all the way to the top.
This is what keeps fragmentation in check: every freed block is greedily reabsorbed into the largest contiguous chunk it can join.
A live 16-page region with a complete buddy allocator running in your browser. Click any button below to allocate; click an allocated block to free it. Watch the free lists and the trace log update in real time.