Buddy Allocator

Free-list allocators search for a block and merge neighbours by looking at addresses and sizes. The binary buddy allocator removes both problems by restricting what a block can be. After this lesson your allocator will carve a power-of-two heap into power-of-two blocks, find any block's merge partner with a single XOR, and put the heap back together when everything is freed.

It was described by Harry Markowitz in 1963 and refined by Knuth, it is O(log n) for both operations, and it is the algorithm underneath the Linux kernel's page allocator (__alloc_pages), the FreeBSD VM system and many real-time allocators.

Blocks are aligned powers of two

The heap is exactly 2^MAX bytes. Every block has a size 2^k and its address is a multiple of 2^k. The allocator keeps one free list per order k, so a request is rounded UP to the next power of two, and order(n) is the smallest k with 2^k >= n.

Rounding costs memory: a 33-byte request occupies 64 bytes, nearly 50% wasted, which is the price of the structure.

The buddy

Cut a block of order k+1 in half and you get two blocks of order k that sit next to each other. They are each other's buddies. Because the parent was aligned to 2^(k+1), its two halves differ in exactly one address bit, bit k:

parent  order 5 at address 32 (binary 100000)
  low half   order 4 at 32   (100000)
  high half  order 4 at 48   (110000)     48 = 32 XOR 16, and 32 = 48 XOR 16

So the buddy of the order-k block at address A is A XOR 2^k. No search, no neighbour lookup: the partner's address is a calculation. Two blocks that are merely ADJACENT are not buddies: the order-2 blocks at 4 and 8 touch, but 4's buddy is 0 and 8's buddy is 12, and merging 4 with 8 would create a block of size 8 at address 4, which is not a multiple of 8.

What alloc and free do

To allocate, round the request up to an order k. Take a free block of that order if the list has one. If not, take a block from the smallest larger order that has one, and split it in halves again and again, putting the upper half of each split on its list, until a block of order k is left over. Always take the lowest address from a list so results are deterministic.

To free, look at the block's buddy. If the buddy is free AND of the same order, remove it from its list and treat the pair as one block of the next order up, then repeat the question there. Stop when the buddy is missing, in use, or split into smaller pieces, and put the result on its list. A completely free heap always reassembles into one block of order MAX.

A trace on a 64-byte heap (INIT 6), different from the tests:

ALLOC 10   order 4. Free: {order 6: [0]}. Split 64 -> 32 + 32 (32 listed), 32 -> 16 + 16 (16 listed).
           returns 0. Free: {order 4: [16], order 5: [32]}
ALLOC 20   order 5. List 5 has 32. returns 32. Free: {order 4: [16]}
FREE 0     buddy of 0 at order 4 is 0 XOR 16 = 16, free: merge into order 5 at 0.
           buddy of 0 at order 5 is 0 XOR 32 = 32, in use: stop.   Free: {order 5: [0]}

Common mistakes

• Merging a block with the neighbour at address + size instead of with address XOR size. Adjacent blocks are not always buddies.
• Stopping after one merge. Freeing the last block of a heap can cascade through every order up to the root.
• Forgetting the size of an allocated block: FREE receives only the address, so the allocator must remember each live block's order.
• Splitting but listing the LOWER half. The caller keeps the lower half and the upper half goes on the free list.

Your exercise

The starter reads commands and prints; you write order_for, the alloc with splits and the free with merges. FREELIST k prints the addresses on order k's list in ascending order, joined by commas, or - when the list is empty. Check non-buddy neighbours and a free that cascades more than one level.