Buddy Allocator

What is the Buddy Allocator?

The buddy allocator is a memory management scheme used by Linux (the buddy allocator in the kernel). Memory is always divided into blocks whose sizes are powers of two. When a request comes in, the allocator finds the smallest power-of-two block that fits, splitting larger blocks as needed.

Why powers of two?

Powers of two make splitting and merging fast and simple: a block of size 2^k can be split into two buddies of size 2^k-1, and two adjacent buddies of equal size can be merged back into one larger block.

Why internal fragmentation?

Because requests are rounded up to the nearest power of two, some memory is wasted inside a block. For example, a 100 KB request gets a 128 KB block, wasting 28 KB. This wasted space is called internal fragmentation.

How splitting works

If no block of the required size is free, the allocator recursively splits the smallest free block large enough to fit the request until it reaches the target size.

How merging works

When a block is freed, the allocator checks its buddy. If the buddy is also free, they are merged into their parent block. This continues recursively up the tree.

Buddy vs. Heap vs. Paging vs. Stack

• Heap allocator: allocates variable-size blocks from a contiguous region (e.g. malloc).
• Buddy allocator: a power-of-two allocator optimized for fast split/merge (used by the OS kernel for physical pages).
• Paging: divides memory into fixed-size pages/frames and maps virtual addresses via a page table.
• Stack: a LIFO region where frames are pushed/popped in a fixed growth direction.