The Buddy Allocator: How Linux Hands Out Page Frames

The idea: blocks of 2^order pages that split and merge

The kernel manages physical memory in page frames of 4 KiB, numbered by their PFN (page frame number; physical address = PFN × 4096). Most requests need one page, but some need several physically contiguous pages: a DMA buffer for a device that does not go through an IOMMU, a 2 MiB huge page, a kernel stack (16 KiB on x86-64). The allocator must hand out contiguous runs quickly and keep free memory from breaking into useless pieces.

The buddy allocator (mm/page_alloc.c) only deals in blocks of 2^order contiguous pages, and every block of order k starts at a PFN that is a multiple of 2^k. So each block has exactly one buddy, the other half of the block one order up, at PFN XOR 2k. The animation uses a zone of 32 pages and orders 0–5; Linux uses orders 0–10 (up to 4 MiB).

Reading the canvas

• Zone (top): one row per order, each block drawn as wide as its pages. Green = free block, a colour = allocated (a red border means unmovable), white outline = split into smaller blocks, yellow = the block being worked on. The bottom row is the 32 page frames; the lighter pages of an allocation are the ones wasted by rounding up.
• free_area[order] (left): the free list of each order, newest first, with nr_free, and the same counts as /proc/buddyinfo prints them.
• This step (middle): the calculations of the current allocation, free or compaction.
• Allocations (right): who owns which pages, how many they asked for and how many are wasted.

Allocation: find the smallest block, split it

1. Round the request up to a power of two: order = ⌈log2 pages⌉.
2. __rmqueue_smallest looks at free_area[order]; if it is empty, at free_area[order + 1], and so on.
3. It takes the first block of the first non-empty list. If that block is bigger than needed, expand halves it again and again: the lower half is kept, the upper half goes on the free list one order down.

From an empty zone, one page needs five splits: 32 → 16 + 16 free → 8 + 8 free → … → 1 + 1 free. The next 4-page request then finds a block on free_area[2] at once (Demo: split on allocation). Each step is O(1) list work, and there are at most MAX_ORDER steps.

Freeing: merge with the buddy, repeat

__free_one_page computes the buddy of the freed block, buddy = pfn XOR 2k. If the buddy is a free block of the same order (the kernel marks such pages PageBuddy and stores the order in them), it is taken off its list and the two merge into a block of order k + 1 at the lower PFN; then the check repeats. Otherwise the block goes on free_area[k]. Because merging always happens as soon as possible, two free buddies of the same order never exist side by side.

In Demo: free and coalesce, freeing A (PFN 0) cannot merge because its buddy B (PFN 0 XOR 1 = 1) is in use. Freeing B merges it with A into an order-1 block, whose buddy (0 XOR 2 = 2) is C. Freeing C then merges 0–3, 0–7, 0–15 and 0–31: the zone is one block again.

Internal and external fragmentation

	Internal fragmentation	External fragmentation
What is wasted	pages inside an allocation that were not asked for	free pages that are not contiguous
Cause	rounding up to 2order: 5 pages → 8	long-lived allocations scattered over memory
Demo	internal fragmentation: 5, 9 and 3 pages use 8, 16 and 4: 11 of 32 pages wasted	external fragmentation: 16 pages free, largest block 4 pages, an 8-page request fails
Remedy	allocate exact sizes from a smaller allocator on top (slab), or free the tail (alloc_pages_exact)	compaction; grouping pages by mobility

Compaction, and why unmovable pages matter

A page mapped into a process only through its page tables can be moved: allocate a new frame, copy the contents, point the page table entries at the new frame. Compaction (mm/compaction.c) runs two scanners: the migrate scanner walks up from the start of the zone looking for movable pages, the free scanner walks down from the end looking for free pages, and pages are moved from the first to the second until the scanners meet. The free pages collect at the start of the zone and merge into big blocks (Demo: compaction: A and C move up, and a 16-page request succeeds).

Kernel memory that is used through its physical or direct-mapped address (page tables, slab objects, most kernel buffers) is unmovable. One such page pins its whole region: in Demo: an unmovable page blocks compaction, C stays at PFN 8–11 and no 16-page block can form, although 16 pages are free. That is why Linux groups allocations by migratetype (movable, unmovable, reclaimable) into separate 2 MiB pageblocks, so unmovable pages do not end up scattered across memory. You can see the free counts per migratetype in /proc/pagetypeinfo.

How to see it on a real system

$ cat /proc/buddyinfo
Node 0, zone      DMA      0      0      0      0      0      0      0      0      1      1      3
Node 0, zone    DMA32   1850   1433    997    603    318    168     79     33     14      4    356
Node 0, zone   Normal  21468  12870   5329   1807    726    278    103     35     20     11   2413

Each column is nr_free of one order, from order 0 (4 KiB) to order 10 (4 MiB). Many small blocks and few large ones mean fragmented memory; echo 1 > /proc/sys/vm/compact_memory compacts all zones, and /proc/vmstat counts compaction attempts and failures (compact_stall, compact_fail).

What sits on top of the buddy allocator

• Per-CPU page lists: single pages are freed to and allocated from a small per-CPU cache first, so most order-0 allocations take no lock.
• The slab allocator (SLUB): kmalloc and object caches cut buddy pages into small objects (a 192-byte inode, a 64-byte buffer), which avoids the rounding waste for small sizes.
• vmalloc: virtually contiguous memory made of scattered single pages, for large buffers that do not need physical contiguity.
• Page faults: a process's pages come from here one at a time, see Virtual Memory.
• malloc: user space never sees the buddy allocator directly; glibc gets pages with brk/mmap and cuts them into chunks, see Stack vs Heap in C.

What the page leaves out

Zones (DMA, DMA32, Normal) and NUMA nodes, each with its own free areas; the watermarks (min, low, high) that wake kswapd or make an allocation reclaim memory itself; the separate free lists per migratetype and the fallback between them; per-CPU lists; the GFP flags that say whether an allocation may sleep, do I/O or retry; and the OOM killer. Compaction here is simplified: it moves whole allocated blocks to the top end of the highest free block above them, instead of scanning single pages in pageblock steps.

References

Mel Gorman, Understanding the Linux Virtual Memory Manager: Physical Page Allocation

Linux kernel documentation: Physical Memory

LWN: Memory compaction

mm/page_alloc.c (__rmqueue_smallest, expand, __free_one_page)