Buddy Allocator

The binary buddy allocator, invented by Harry Markowitz (1963) and refined by Knuth, is famous for two properties:

• O(log n) allocate and free.
• Predictable coalescing: every block has a unique "buddy" determined entirely by its address.

It is the algorithm behind the Linux kernel page allocator (__alloc_pages), the FreeBSD VM system, and many real-time allocators.

The setup

The heap is exactly 2^MAX_ORDER bytes. Every block has a power-of-two size, 2^k. The set of free blocks is organized as one free list per order:

free_list[k] = blocks of size 2^k

The buddy

For a block at address A of order k, its buddy is:

buddy(A, k) = A XOR (1 << k)

Why XOR? The address bit at position k is the only difference between the two halves of a 2^(k+1)-sized parent block. Flipping that bit gives you the sibling.

Allocate

alloc(s):
    k = smallest order with 2^k >= s
    if free_list[k] is empty:
        find smallest j > k with a free block
        repeatedly split: take a 2^j block, put its second half on free_list[j-1], j -= 1
        until j == k
    pop free_list[k]

Free

free(A, k):
    while k < MAX_ORDER:
        b = buddy(A, k)
        if b is on free_list[k]:    # buddy is also free
            remove b from free_list[k]
            A = min(A, b)
            k += 1                  # merged, recurse
        else:
            break
    push A onto free_list[k]

Every merge restores a higher-order block. After enough frees the heap returns to one giant 2^MAX_ORDER free block.

Trade-offs

• Internal fragmentation: a 33-byte allocation occupies a 64-byte block — 48% waste.
• External fragmentation: bounded — merging is automatic when buddies are free.
• Speed: O(log heap_size) per operation; cache-friendly.

Variants

• Binary buddy (this lesson): powers of 2 only.
• Fibonacci buddy: sizes follow the Fibonacci sequence, reducing internal frag.
• Weighted buddy, double buddy: hybrid schemes used in some kernels.

Why study it

Buddy is the simplest allocator that gives O(log n) operations AND automatic coalescing. It's the foundation of virtually every kernel memory manager.