What is the Buddy System for Memory Allocation?
Learn how the buddy system allocates memory in power-of-two blocks, splits and coalesces buddies, and its fragmentation trade-off.
Expected Interview Answer
The buddy system is a kernel memory allocator that manages physical memory in power-of-two-sized blocks, splitting a large free block into two equal buddies to satisfy a smaller request and merging adjacent free buddies back together to fight fragmentation.
The allocator starts with memory organized as a small set of maximal free blocks, each a power of two in size, tracked in per-order free lists. When a request arrives, the allocator finds the smallest free block at least as large as the request; if the block is bigger than needed, it repeatedly splits in half, placing one half back on the lower-order free list and recursing on the other half, until the block size matches the requested order. Each split half is called a buddy of the other, and their addresses differ by exactly the block size, which is what allows a cheap XOR-based computation to find a block’s buddy during release. On free, the allocator checks whether the just-freed block’s buddy is also free; if so, it merges them into a single block of the next order up and repeats the check with the merged block’s buddy, coalescing as far up the size classes as possible. This gives O(log n) allocation and free with fast buddy address computation, at the cost of internal fragmentation because every request is rounded up to the next power of two.
- Fast O(log n) allocate and free via simple address-based buddy lookup
- Coalescing on free keeps large free blocks available, limiting external fragmentation
- Power-of-two sizing makes buddy address computation a cheap XOR
- Basis for the Linux kernel page allocator (zoned buddy allocator)
AI Mentor Explanation
The buddy system is like a groundstaff splitting one full-size practice ground into two identical halves whenever a smaller net session is needed, and splitting again if an even smaller session is booked, always halving evenly. When a session ends, the staff check whether the matching other half is also free right now, and if so they immediately rejoin the two halves back into the original full ground. This constant halving and rejoining keeps the ground inventory tidy, though a session needing slightly more than one half still gets a full half reserved for it, wasting the leftover space.
Step-by-Step Explanation
Step 1
Locate free block
Find the smallest free block at or above the requested order in the per-order free lists.
Step 2
Recursive split
If the block is larger than needed, split it into two equal buddies, keep one and repeat until the size matches.
Step 3
Allocate
Return the correctly sized block to the caller and mark it allocated.
Step 4
Free and coalesce
On release, check the buddy address; if it is also free, merge into the next order and repeat upward.
What Interviewer Expects
- Explanation of power-of-two block sizes and per-order free lists
- How splitting works recursively to satisfy a request
- How buddy address computation enables cheap coalescing on free
- Awareness that internal fragmentation is the trade-off (rounding up to power of two)
Common Mistakes
- Confusing the buddy system with the slab allocator
- Forgetting that buddies must be adjacent AND both free to merge
- Not mentioning internal fragmentation as the main cost
- Thinking buddy allocation avoids all fragmentation entirely
Best Answer (HR Friendly)
“The buddy system manages memory in chunks that are always a power of two in size — like 4KB, 8KB, 16KB — and splits a big chunk in half repeatedly to fit a smaller request, keeping the other half ready to reuse. When memory is freed, it checks if the neighboring half is also free and instantly merges them back together, which keeps memory tidy and allocation fast, though it can waste some space by rounding requests up.”
Code Example
#define MAX_ORDER 10 /* blocks range from 2^0 to 2^MAX_ORDER pages */
struct free_list { struct block *head; } free_lists[MAX_ORDER + 1];
/* buddy of a block differs from it by exactly one bit at its size’s position */
void *buddy_of(void *block, int order, void *base) {
unsigned long offset = (unsigned long)block - (unsigned long)base;
unsigned long buddy_offset = offset ^ (1UL << order);
return (char *)base + buddy_offset;
}
void *alloc_block(int order) {
int o = order;
while (o <= MAX_ORDER && free_lists[o].head == NULL) o++;
if (o > MAX_ORDER) return NULL; /* out of memory */
struct block *b = pop(&free_lists[o]);
while (o > order) {
o--;
struct block *half = split_upper_half(b, o);
push(&free_lists[o], half); /* keep one half free */
}
return b; /* correctly sized block */
}Follow-up Questions
- How does the buddy system decide two blocks can be coalesced?
- What causes internal fragmentation in a buddy allocator, and how much can be wasted in the worst case?
- How does the Linux kernel use the buddy system for physical page allocation?
- How does the slab allocator build on top of the buddy system?
MCQ Practice
1. What size classes does the buddy system use for blocks?
The buddy system always allocates blocks whose size is a power of two, enabling recursive splitting and cheap buddy address computation.
2. When can two buddy blocks be merged on free?
Coalescing only happens between a block and its specific buddy (computed via XOR of the address), and only when both are currently free.
3. What is the main downside of the buddy system?
Because block sizes are restricted to powers of two, a request just over a size boundary rounds up to the next size class, wasting space inside the block.
Flash Cards
What is the buddy system? — A memory allocator using power-of-two block sizes, splitting to allocate and merging adjacent free buddies on release.
How is a block’s buddy found? — By XORing the block’s offset with its size, giving the address of its matching half.
Main cost of the buddy system? — Internal fragmentation, since every request rounds up to the next power of two.
Where is the buddy system used in practice? — As the core physical page allocator in the Linux kernel.