Buddy System — Memory Allocation

Overview

What this concept solves

The buddy system is a structured allocator that trades a little wasted space for very fast allocation and, especially, very fast coalescing. All blocks are powers of two in size. Memory starts as one giant block; to satisfy a request, the allocator rounds the request up to the nearest power of two and, if the smallest available block is too big, splits it in half — and halves again — until it has a block of exactly the right size.

When a block is split, the two halves are buddies. The defining trick is that a block's buddy is found by a single XOR: buddyAddress = blockAddress XOR blockSize. That makes the reverse operation — merging — almost free. When a block is freed, the allocator checks whether its buddy is also free; if so, the two coalesce back into the larger block, and that block checks its buddy, cascading upward until no further merge is possible.

This is why Linux uses a buddy system for its page allocator: physical memory is handed out in power-of-two runs of pages, and when memory is freed, large contiguous regions reassemble quickly so the next big request can be served. The cost is internal fragmentation — rounding a 100K request up to 128K wastes 28K inside the block — which the slab allocator (layered on top) exists partly to mitigate.

Mechanics

How it works

Allocation: round up, then split down

Round the request up to the next power of two (bounded below by a minimum block size). A 100K request becomes a 128K block.
Find the smallest free block that is at least that size. Free blocks are kept in lists segregated by size (one list per power of two), so this lookup is fast.
Split down to size. If the block is bigger than needed, split it into two equal buddies, keep one, and put the other on the free list for its size. Repeat until the block is exactly the rounded-up size.
Hand it out. The requester gets a power-of-two block; the difference between the rounded size and the actual request is internal fragmentation.

Free: merge with the buddy

Compute the buddy address with addr XOR size. Because blocks are power-of-two aligned, this flips exactly the bit that distinguishes the two halves.
Check the buddy's state. If the buddy is free and whole (not itself split), the two can merge.
Merge and ascend. Combine the two halves into the larger block, then repeat the buddy check at the next size up — coalescing cascades as far as it can.
Stop when the buddy is busy, is split into smaller pieces still in use, or the whole heap has reassembled.

Why the XOR works

Two buddies of size S occupy addresses that differ only in the bit with value S (because they were created by splitting an aligned 2S block). XOR-ing an address with S flips that one bit, turning a block's address into its buddy's and vice versa. So finding a buddy is one instruction, and the allocator never has to search — coalescing is O(1) per level, O(log n) total.

Internal fragmentation is the price

Because every allocation is rounded up to a power of two, a request just over a boundary wastes nearly half the block. A 257K request takes a 512K block — 255K wasted inside. This is internal fragmentation, and it's the buddy system's characteristic cost, accepted in exchange for fast splitting and merging.

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

simulation › Buddy System

About this simulation

The buddy system manages memory as power-of-two blocks. A request is rounded up to the next power of two; a large free block is split in half repeatedly until it's the right size; the unused half of each split is the block's buddy. On free, a block merges with its buddy whenever the buddy is also free — found with a single XOR of the address. Scenario 1 · Split & merge runs allocs and frees; scenario 2 · Full merge cascade shows blocks coalescing all the way back to the whole heap.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Watch a request split down to size

On scenario 1 · Split & merge, step through the first allocation: P1 requests 100K, which rounds up to 128K. The allocator finds the 1024K block and splits it 1024 → 512 → 256 → 128, keeping the left half each time. Watch the gray 'internal fragmentation' segment appear inside P1's block — 28K wasted because 100K had to round up to 128K.

try 02

See a buddy merge — and a blocked one

Keep stepping into the free P3 and free P1 operations. Freeing P3 lets its 64K block merge with its free buddy back into 128K, but that block's buddy (P1) is busy, so it stops. After freeing P1, two 256K free blocks remain — but they sit on opposite sides of P2 and P4, so they can't merge (not buddies). Watch the free-list summary and the 'can't merge' narration.

try 03

Trigger a full coalescing cascade

Switch to scenario 2 · Full merge cascade. Allocate two 200K blocks (each rounds to 256K), then free them in order. Freeing the second block sets off a cascade: 256+256 merges to 512, then 512+512 merges back to the full 1024K heap. Step slowly to watch each XOR-driven merge, then hit Auto to see the whole cascade run.

In practice

When to use it — and what you give up

When the buddy system shines

Page-level allocation in a kernel — Linux's physical page allocator is a buddy system; power-of-two page runs and fast coalescing are exactly what it needs.
Fast coalescing is a priority — if you free and re-allocate large blocks frequently and need them to reassemble quickly, the XOR-and-merge is hard to beat.
Allocation sizes cluster near powers of two — when requests are already close to powers of two, the internal-fragmentation cost is small.
Avoid it for many odd-sized small objects — the rounding waste becomes severe; layer a slab allocator on top instead (which is exactly what real kernels do).

Real-world example

The Linux kernel allocates physical memory with a buddy allocator operating on orders (order-0 is one page, order-1 is two pages, and so on up the powers of two). Freed page runs coalesce upward so high-order allocations can succeed. On top of the buddy allocator sits the slab/SLUB allocator, which carves those pages into right-sized object caches — the buddy system handles pages, slab handles objects.

Pros

O(1) buddy lookup, O(log n) coalescing — merging is a single XOR plus a list operation per level.
Fast splitting — find the smallest block and halve down a known number of steps.
Limited, predictable external fragmentation — free space reassembles into large blocks readily.
Simple free lists — one list per power-of-two size class.

Cons

Internal fragmentation — rounding every request up to a power of two can waste up to nearly half a block.
Coarse size classes — only power-of-two sizes exist; there's no 192K block, only 128K or 256K.
Merges can be blocked — two free blocks that aren't buddies (busy blocks between them) can't coalesce.
Not ideal for many small odd-sized objects — needs a slab layer on top to be space-efficient there.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

buddy.ts

const MIN = 64;

function nextPow2(n: number): number {
  let p = MIN;
  while (p < n) p *= 2;
  return p;
}

interface Block { start: number; size: number; free: boolean; }

/** The buddy of a block: flip the single bit equal to its size. */
function buddyAddress(start: number, size: number): number {
  return start ^ size;          // XOR — O(1), no search
}

/** On free, coalesce upward while the buddy is also free. */
function freeAndMerge(blocks: Map<number, Block>, start: number, size: number, total: number) {
  let s = start, sz = size;
  while (sz < total) {
    const b = buddyAddress(s, sz);
    const buddy = blocks.get(b);
    if (!buddy || !buddy.free || buddy.size !== sz) break; // buddy busy/split → stop
    blocks.delete(b);
    blocks.delete(s);
    s = Math.min(s, b);          // merged block starts at the lower address
    sz *= 2;                     // ascend one size class and check again
  }
  blocks.set(s, { start: s, size: sz, free: true });
}

References & further reading

5 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. No scoring saved.

question 01 / 03

How does the buddy system find a freed block's buddy?

question 02 / 03

What is the buddy system's characteristic source of waste?

question 03 / 03

After freeing two blocks, why might two adjacent free blocks still fail to merge?

0/3 answered