Implement Buddy Allocator for Physical Memory Management

Topic Overview

Power-of-Two Physical Pages

The buddy allocator splits and merges power-of-two blocks of physical memory. Linux's page_alloc.c uses it for page-sized (and larger) allocations because coalescing is O(log n) with simple bitwise buddy math.

Split and Coalesce

Allocation of 200 KB from a 1024 KB arena:

• Round up to 256 KB (next power of two)
• Split 1024 into two 512 blocks, then split one 512 into two 256
• On free, merge buddies if both are free: buddy = addr XOR size

cCopy
Loading…

Why This Matters in Production

Linux's physical page allocator in mm/page_alloc.c is a buddy system just like this one, tracking per-order free lists and coalescing blocks via the same base-address XOR trick to fight external fragmentation. Get the splitting or coalescing logic wrong and you reproduce the exact class of bug kernel developers chase when large contiguous allocations mysteriously fail under memory pressure.

Debugging Checklist

Before you call the implementation done, walk failure modes on purpose. Test empty structures, single-element edge cases, maximum concurrency, and errno paths that must not crash the program. OS code usually fails in production when happy-path tests pass but invariants break under contention or memory pressure.

Implementation Notes

Keep structures small and name fields after kernel counterparts when possible. That lets you read man pages and kernel source side by side while you work. Print observable events during development; remove noisy logs once tests pass reliably.

For This Exercise

You will implement free lists per order, split on alloc, and merge on free. This exercise asks you to print the tree after each operation so fragmentation behavior is visible.

Your Task

The Linux kernel hands out physical memory with a buddy allocator. Build one over a 1024 KB pool.

• Every block is a power of two in size, from 1 KB to 1024 KB, and starts at an offset that is a multiple of its size. The pool starts as one free 1024 KB block at offset 0.
• Allocate N KB: round N up to a power of two. Take the smallest free block that is big enough; among blocks of that size, the one with the lowest offset. While the block is larger than needed, split it in half: keep the lower half and put the upper half on the free list. A request above 1024 KB, or one that no free block fits, fails.
• Free: mark the block free. Then, while its buddy (the block at offset XOR size, the same size) is also free, merge them into one block twice as large at the lower offset, and try again one size up.

Input

Commands until the end of input. Allocations are named, so they can be freed by name; at most 32 are live.

• alloc NAME KB
• free NAME
• status

Output

First buddy pool_kb=1024. Then:

• alloc: a line per split, split 1024@0 -> 512@0 + 512@512 (size@offset, in KB), then alloc A 100KB -> 128KB block at 0, or alloc X 2000KB -> FAIL (out of memory).
• free: free A: 128KB at 0, then a line per merge, merge 128@0 + 128@128 -> 256@0. An unknown name prints free X: not allocated.
• status: free: 128@128 256@256 512@512, the free blocks in offset order (just free: when there are none), then used_kb=128 free_kb=896.