The Buddy Allocator

The buddy allocator is the Linux kernel’s bottom-level physical page allocator: the code that hands out and reclaims physically contiguous runs of page frames. It keeps free memory organized as a set of free lists, one per allocation order — order n holds blocks of exactly 2ⁿ contiguous pages. To satisfy a request it splits a larger block in half repeatedly until it has a block of the right size (each half is the other’s buddy); when a block is freed it checks whether its buddy is also free and, if so, coalesces the two back into a block of the next order up. This split-and-merge discipline keeps physically contiguous free memory available with O(log N) work per operation and almost no bookkeeping beyond the free lists themselves. In the v6.12 long-term-support kernel (released 2024-11-17) the public entry points are alloc_pages()/__alloc_pages() to allocate and __free_pages()/free_pages() to free, the per-zone state lives in struct zone’s free_area[NR_PAGE_ORDERS] array, and the live state is observable through /proc/buddyinfo (per mm/page_alloc.c and include/linux/mmzone.h).

This note covers the mechanism: the free-list data structures, the order range, the split (expand) and coalesce (__free_one_page) algorithms, the allocation/free entry points, and /proc/buddyinfo. The problem the buddy system is fighting — internal vs external fragmentation, why high-order requests fail, and the anti-fragmentation strategy — lives in its sibling Page Order and Fragmentation. The cousin mechanisms that sit just above the buddy allocator on the fast path — the watermark fast path, the per-CPU page lists that serve hot order-0 allocations without taking the zone lock, the node hierarchy the allocator iterates, and the GFP flags that constrain a request — each have their own note; this one cross-links them rather than re-teaching them. Above the buddy allocator entirely sits SLUB layer, which carves buddy-supplied pages into small same-sized kernel objects.

Mental Model

Think of the buddy allocator as a stack of bins, one per power-of-two block size. The order-0 bin holds single pages, order-1 holds aligned pairs, order-2 holds aligned runs of four, and so on up to the largest block the allocator will track. Every block in a bin is naturally aligned to its own size — an order-n block always starts at a page-frame number (PFN) that is a multiple of 2ⁿ. This alignment is the whole trick: because a block is aligned to its size, its buddy (the adjacent block it can merge with) is found by flipping exactly one bit of its PFN, the bit at position n. Allocation walks up the bins looking for the smallest available block and splits it down to size; freeing walks up the bins merging with buddies as far as it can.

flowchart TB
  subgraph ZONE["struct zone"]
    FA["free_area[NR_PAGE_ORDERS]<br/>(orders 0..MAX_PAGE_ORDER = 0..10)"]
  end
  FA --> O0["free_area[0]<br/>blocks of 1 page (4 KiB)"]
  FA --> O1["free_area[1]<br/>blocks of 2 pages (8 KiB)"]
  FA --> O2["free_area[2]<br/>blocks of 4 pages (16 KiB)"]
  FA --> ODOT["..."]
  FA --> O10["free_area[10]<br/>blocks of 1024 pages (4 MiB)"]
  O2 --> FL["struct free_area:<br/>free_list[MIGRATE_TYPES]<br/>(one list per migratetype)<br/>nr_free (count)"]
  FL --> U["free_list[UNMOVABLE]"]
  FL --> M["free_list[MOVABLE]"]
  FL --> R["free_list[RECLAIMABLE]"]
  FL --> H["free_list[HIGHATOMIC]"]

The per-zone buddy free-list structure in Linux v6.12. What it shows: each memory zone owns an array free_area[NR_PAGE_ORDERS] indexed by allocation order 0 through MAX_PAGE_ORDER (= 10 on most configs, so 11 orders total). Each struct free_area is not a single list — it is an array of free_list[MIGRATE_TYPES], one doubly-linked list per migratetype (UNMOVABLE / MOVABLE / RECLAIMABLE / HIGHATOMIC / …), plus an nr_free counter. The insight to take: the buddy allocator is two-dimensional — indexed first by size (order) and within each order by mobility (migratetype). The order axis is the buddy mechanism proper; the migratetype axis is the anti-fragmentation layer bolted on top (covered in Page Order and Fragmentation).

The Order Range and the MAX_ORDER → MAX_PAGE_ORDER Rename

An allocation order is the base-2 logarithm of the block size in pages: order 0 is one page, order 1 is two pages, order n is 2ⁿ pages. On a 4-KiB-page machine, order 0 is 4 KiB and the maximum order’s block is 2^MAX_PAGE_ORDER × 4 KiB. The constant that bounds the range is defined in include/linux/mmzone.h:

#ifndef CONFIG_ARCH_FORCE_MAX_ORDER
#define MAX_PAGE_ORDER 10
#else
#define MAX_PAGE_ORDER CONFIG_ARCH_FORCE_MAX_ORDER
#endif
#define MAX_ORDER_NR_PAGES (1 << MAX_PAGE_ORDER)   /* 1024 pages */
#define NR_PAGE_ORDERS (MAX_PAGE_ORDER + 1)         /* 11 orders: 0..10 */

With the default MAX_PAGE_ORDER = 10, the largest block the buddy allocator tracks is 2^10 = 1024 pages = 4 MiB on a 4-KiB-page system. NR_PAGE_ORDERS = 11 is the number of free lists per migratetype (orders 0 through 10, inclusive). Architectures can override the maximum with CONFIG_ARCH_FORCE_MAX_ORDER.

The naming here has a history that routinely trips people up, so it is worth pinning precisely against the source tree:

• Linux 6.3 and earlier: the constant was MAX_ORDER and it was exclusive — its value was 11, the array was declared free_area[MAX_ORDER], the maximum usable order was 10, and MAX_ORDER_NR_PAGES was 1 << (MAX_ORDER - 1) (confirmed in v6.3 mmzone.h: #define MAX_ORDER 11).
• Linux 6.4 (released 2023): a semantic flip made MAX_ORDER inclusive — its value dropped to 10, the array became free_area[MAX_ORDER + 1], and MAX_ORDER_NR_PAGES became 1 << MAX_ORDER (confirmed in v6.4 mmzone.h). The numeric maximum order (10) and the count (11) did not change; what changed was whether the named constant is the max order or is one-past it.
• Linux 6.8 (released 2024): a pure spelling change renamed MAX_ORDER to MAX_PAGE_ORDER and introduced NR_PAGE_ORDERS = MAX_PAGE_ORDER + 1 for the array count (confirmed in v6.8 mmzone.h). No semantic change — both are 10, inclusive. The rename was driven by the old name’s ambiguity (it had meant “exclusive” for years, then “inclusive” since 6.4, confusing everyone).

So the often-repeated shorthand “MAX_ORDER was renamed to MAX_PAGE_ORDER” is true but conflates two distinct changes: the inclusive/exclusive flip in 6.4 and the rename in 6.8. The v6.12 LTS kernel this note targets carries the post-rename, inclusive form. The bound also matters elsewhere: MAX_PAGE_ORDER is checked against the SPARSEMEM section size (#if (MAX_PAGE_ORDER + PAGE_SHIFT) > SECTION_SIZE_BITS #error), so a buddy block can never straddle a memory section.

struct free_area and the Per-Migratetype Free Lists

The per-order state is a single small struct (mmzone.h):

struct free_area {
	struct list_head	free_list[MIGRATE_TYPES];
	unsigned long		nr_free;
};

free_list is an array of linked-list heads, one per migratetype; nr_free is the total count of blocks (not pages) at this order across all migratetypes. The migratetypes are an enum:

enum migratetype {
	MIGRATE_UNMOVABLE,
	MIGRATE_MOVABLE,
	MIGRATE_RECLAIMABLE,
	MIGRATE_PCPTYPES,    /* number of types on the per-CPU pcp lists */
	MIGRATE_HIGHATOMIC = MIGRATE_PCPTYPES,
#ifdef CONFIG_CMA
	MIGRATE_CMA,
#endif
#ifdef CONFIG_MEMORY_ISOLATION
	MIGRATE_ISOLATE,     /* can't allocate from here */
#endif
	MIGRATE_TYPES
};

The first three — UNMOVABLE, MOVABLE, RECLAIMABLE — are the workhorse classes used to group pages by how easily the kernel can relocate them, which is the heart of the anti-fragmentation story in Page Order and Fragmentation. MIGRATE_PCPTYPES is not a real type; it is a count marking “these first three live on the per-CPU pcp lists.” MIGRATE_HIGHATOMIC is a small reserve carved out of the free lists so that high-order atomic allocations (allocations from interrupt context that cannot sleep or reclaim — see GFP Flags and Allocation Contexts) have somewhere to draw from when the rest of memory is fragmented; ordinary allocations are kept out of it. MIGRATE_CMA (Contiguous Memory Allocator) pageblocks accept only movable pages so they can be evacuated on demand for large DMA buffers, and MIGRATE_ISOLATE is a temporary state marking a range that must not be allocated from (used during memory hot-unplug and compaction). The human-readable names are in migratetype_names[] in page_alloc.c: "Unmovable", "Movable", "Reclaimable", "HighAtomic", "CMA", "Isolate".

Each struct zone embeds one of these arrays:

struct zone {
	...
	struct free_area	free_area[NR_PAGE_ORDERS];
	...
};

A free block’s own pages double as the list nodes: the head struct page of a free block has its lru/buddy_list field threaded into the appropriate free_list, and its private order is recorded via set_buddy_order() (which stashes the order in the page’s private field and sets the PageBuddy flag). This is why the buddy allocator needs essentially no external bookkeeping — the free blocks are the data structure.

Finding the Buddy: the XOR Trick

The defining operation is computing a block’s buddy. Because every order-n block is aligned to 2ⁿ pages, two buddies differ in exactly one PFN bit — the bit at position n. So the buddy’s PFN is found by flipping that one bit, i.e. XOR-ing with 1 << order (mm/internal.h):

static inline unsigned long
__find_buddy_pfn(unsigned long page_pfn, unsigned int order)
{
	return page_pfn ^ (1 << order);
}

For example, an order-2 block (4 pages) starting at PFN 12 (0b1100) has its buddy at 12 ^ 4 = 8 (0b1000); the two together form an order-3 block (8 pages) starting at PFN 8. An order-2 block at PFN 8 has its buddy at 8 ^ 4 = 12 — the relationship is symmetric, as it must be. A candidate buddy is only a real buddy if it is itself free, of the same order, and in the same zone; find_buddy_page_pfn() computes the candidate and validates it with page_is_buddy(), returning NULL if the buddy is in use, a different order, or out of range.

Allocation: Walking Up and Splitting Down (expand)

The core allocation routine is __rmqueue_smallest() (page_alloc.c). To satisfy an order-n request it scans the free lists from order n upward, looking for the smallest available block of the requested migratetype:

struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
				int migratetype)
{
	unsigned int current_order;
	struct free_area *area;
	struct page *page;
 
	for (current_order = order; current_order < NR_PAGE_ORDERS; ++current_order) {
		area = &(zone->free_area[current_order]);
		page = get_page_from_free_area(area, migratetype);
		if (!page)
			continue;
		page_del_and_expand(zone, page, order, current_order, migratetype);
		...
		return page;
	}
	return NULL;
}

If the smallest block found is larger than requested (current_order > order), it must be split. page_del_and_expand() removes the block from its free list and calls expand(), which repeatedly halves the block, returning the upper half of each split to the free list one order down, until a block of the requested order remains:

static inline unsigned int expand(struct zone *zone, struct page *page,
				  int low, int high, int migratetype)
{
	unsigned int size = 1 << high;
	unsigned int nr_added = 0;
 
	while (high > low) {
		high--;
		size >>= 1;                       /* halve the block */
		if (set_page_guard(zone, &page[size], high))
			continue;                 /* DEBUG_PAGEALLOC poisons the half */
		__add_to_free_list(&page[size], zone, high, migratetype, false);
		set_buddy_order(&page[size], high);
		nr_added += size;
	}
	return nr_added;
}

Walking through it: suppose a process needs an order-0 page (one page) but the smallest free block is order-3 (8 pages). expand(low=0, high=3) splits the 8-page block: the top 4 pages go back to the order-2 list, leaving a 4-page block; that splits, the top 2 pages go to the order-1 list, leaving a 2-page block; that splits, the top 1 page goes to the order-0 list, leaving the single page the caller wanted. One order-3 allocation thus seeds the order-2, order-1, and order-0 lists with one block each — which is exactly why a freshly-booted, lightly-used system shows nonzero counts spread across many orders in /proc/buddyinfo. The set_page_guard() branch is a debug feature (CONFIG_DEBUG_PAGEALLOC): instead of returning the half to the free list, it marks it as a guard page that stays unmapped, catching out-of-bounds accesses.

The full allocation path layers several caches and policies above __rmqueue_smallest: the per-CPU pcp lists (__rmqueue_pcplist) serve order-0 and other small allocations without taking the zone lock (Per-CPU Page Lists); the watermark check in get_page_from_freelist() decides whether the zone has enough free memory to allocate without waking reclaim; and __rmqueue() consults the fallback machinery (below) when the requested migratetype’s lists are empty. The public entry is __alloc_pages(), whose underlying function in v6.12 is __alloc_pages_noprof():

struct page *__alloc_pages_noprof(gfp_t gfp, unsigned int order,
				  int preferred_nid, nodemask_t *nodemask)
{
	...
	if (WARN_ON_ONCE_GFP(order > MAX_PAGE_ORDER, gfp))
		return NULL;                 /* orders above the max are rejected */
	...
	/* First allocation attempt: the fast path */
	page = get_page_from_freelist(alloc_gfp, order, alloc_flags, &ac);
	if (likely(page))
		goto out;
	/* Fast path failed: enter the slow path (reclaim, compaction, retry) */
	page = __alloc_pages_slowpath(alloc_gfp, order, &ac);
	...
}

A note on the _noprof suffix, because it is easy to get wrong: __alloc_pages was not renamed to __alloc_pages_noprof. Rather, a memory-allocation-profiling macro layer (CONFIG_MEM_ALLOC_PROFILING, introduced in Linux 6.10 — the config is absent in v6.9 and present in v6.10, where gfp.h already defines alloc_pages_noprof) wraps the allocator entry points so that, when enabled, each call site is tagged with the code location that allocated. __alloc_pages still exists as the public macro; __alloc_pages_noprof() is the underlying (“no profiling”) function the macro expands to. The same *_noprof convention applies to alloc_pages_noprof(), __get_free_pages_noprof(), and the rest of the family.

Freeing: Coalescing with Buddies (__free_one_page)

Freeing is the mirror image. The public entry __free_pages() drops the page’s reference count and, if it hits zero, returns the block to the allocator via free_unref_page() (which may stage order-0 pages on the per-CPU lists first). The block ultimately reaches __free_one_page(), the coalescing core (page_alloc.c):

static inline void __free_one_page(struct page *page, unsigned long pfn,
		struct zone *zone, unsigned int order,
		int migratetype, fpi_t fpi_flags)
{
	unsigned long buddy_pfn = 0, combined_pfn;
	struct page *buddy;
 
	VM_BUG_ON_PAGE(pfn & ((1 << order) - 1), page);   /* must be order-aligned */
	account_freepages(zone, 1 << order, migratetype);
 
	while (order < MAX_PAGE_ORDER) {
		buddy = find_buddy_page_pfn(page, pfn, order, &buddy_pfn);
		if (!buddy)
			goto done_merging;        /* buddy not free → stop */
		...
		__del_page_from_free_list(buddy, zone, order, buddy_mt);  /* pull buddy off its list */
		combined_pfn = buddy_pfn & pfn;   /* lower of the two PFNs = merged block start */
		page = page + (combined_pfn - pfn);
		pfn = combined_pfn;
		order++;                          /* climb one order and try again */
	}
 
done_merging:
	set_buddy_order(page, order);
	/* add the (possibly merged) block to the free list at its final order */
	...
}

The loop is the heart of the buddy system: while the block can still grow (below MAX_PAGE_ORDER), find its buddy; if the buddy is free, remove the buddy from its list, compute the merged block’s start as buddy_pfn & pfn (the lower of the two aligned PFNs), bump the order, and repeat. The moment the buddy is not free, stop and insert the block at whatever order it reached. So freeing the last page that completes an aligned 4-MiB run can cascade all the way up to an order-10 block in a single call. The order < MAX_PAGE_ORDER bound stops the merge at the largest tracked block. There is one subtlety guarded in the real code: blocks at or above pageblock_order (9 on x86-64 with transparent huge pages, i.e. 512 pages = 2 MiB — see pageblock-flags.h) are only merged with a buddy of a mergeable migratetype, so that pageblock-isolation and CMA/HIGHATOMIC accounting stay correct.

Fallback Stealing When a Migratetype Runs Dry

When __rmqueue_smallest() finds no block of the requested migratetype at any order, the allocator does not give up — it steals a block from another migratetype rather than fail or wake reclaim prematurely. The fallback order is a static table in page_alloc.c:

static int fallbacks[MIGRATE_PCPTYPES][MIGRATE_PCPTYPES - 1] = {
	[MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE   },
	[MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE },
	[MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE   },
};

An UNMOVABLE request with empty UNMOVABLE lists tries RECLAIMABLE first, then MOVABLE, and so on. Crucially, the allocator prefers to steal the largest available fallback block and, where it can, claim the whole pageblock for the requesting migratetype (steal_suitable_fallback() / can_steal_fallback()), converting that pageblock so future frees land on the right list. This whole-block stealing is the mechanism that limits the damage fallback does to anti-fragmentation; the rationale for why grabbing the largest block and converting the whole pageblock matters — and how it interacts with Memory Compaction — is the subject of Page Order and Fragmentation. (CMA pages get their own special __rmqueue_cma_fallback() path so that movable allocations can borrow from CMA reserves.)

/proc/buddyinfo and /proc/pagetypeinfo

The buddy allocator’s live state is exposed in two procfs files (per Documentation/filesystems/proc.rst). /proc/buddyinfo shows, per node and zone, the number of free blocks at each order:

> cat /proc/buddyinfo
Node 0, zone      DMA      0      4      5      4      4      3 ...
Node 0, zone   Normal      1      0      0      1    101      8 ...

Reading the Normal row: 1 free block of 2⁰ pages, 0 of 2¹, 0 of 2², 1 of 2³, 101 of 2⁴, 8 of 2⁵, and so on across the 11 columns (orders 0..10). The docs note this is a fragmentation-diagnosis tool: it “will give you a clue as to how big an area you can safely allocate, or why a previous allocation failed.” A row that is dense on the left and empty on the right means memory is fragmented — plenty of single pages, no large contiguous runs. /proc/pagetypeinfo breaks the same counts down further, by migratetype, and prints the pageblock order:

> cat /proc/pagetypeinfo
Page block order: 9
Pages per block:  512

Free pages count per migrate type at order   0    1    2  ...
Node 0, zone   DMA32, type    Unmovable    103   54   77  ...
Node 0, zone   DMA32, type      Movable    169  152  113  ...

Page block order: 9 / Pages per block: 512 confirms the 2-MiB pageblock granularity on this x86-64 host. Watching the Movable row collapse toward the left while Unmovable counts persist on the right is the classic signature of the fragmentation that motivates compaction.

Failure Modes and Common Misunderstandings

“alloc_pages can always give me order 0.” Not under the watermark regime. An order-0 allocation can still fail or stall: if free memory is below the relevant watermark and the GFP flags forbid reclaim (e.g. GFP_ATOMIC in interrupt context), the fast path returns NULL. The buddy allocator never blocks on a forbidden context; it returns NULL and the caller must cope.

Confusing nr_free (blocks) with free pages. nr_free and the buddyinfo columns count blocks, not pages. One block at order 10 is 1024 pages. To get free pages you must weight each column by 2^order. This is the most common misreading of buddyinfo.

Expecting high-order allocations to succeed under load. Even with gigabytes free, an order-5+ allocation can fail if memory is fragmented into single pages — there may be no contiguous run that large. This is the failure that Memory Compaction exists to fix, and the reason kmalloc of large sizes can fail where vmalloc (virtually contiguous) succeeds. See Page Order and Fragmentation for the full mechanism.

Order-alignment is mandatory. You cannot free an arbitrary sub-range of a block, and you cannot free a block at the wrong order. __free_one_page() carries VM_BUG_ON_PAGE(pfn & ((1 << order) - 1), page) — freeing a misaligned PFN is a kernel bug, not a soft error. Pair every alloc_pages(gfp, order) with a __free_pages(page, order) at the same order.

The buddy allocator is not where small allocations come from. A kmalloc(64, GFP_KERNEL) does not call the buddy allocator directly for 64 bytes — it draws from a SLUB cache that itself obtained whole pages from the buddy allocator earlier. The buddy allocator’s currency is always whole pages.

Alternatives and When to Choose Them

Within the kernel, the buddy allocator is the source of physical pages — there is no alternative for contiguous physical memory below it. The choices are about which layer you call:

• alloc_pages() / __get_free_pages() — call the buddy allocator directly when you genuinely need page-granular, physically contiguous memory (DMA buffers, page tables, ring buffers). You specify the order.
• kmem_cache_alloc — for objects smaller than a page or many same-sized objects; SLUB amortizes one buddy allocation across many objects. This is the right call for the overwhelming majority of kernel allocations.
• vmalloc() — when you need a large virtually contiguous region but the underlying pages need not be physically contiguous; vmalloc stitches together order-0 pages from the buddy allocator and maps them contiguously in the kernel’s virtual address space, sidestepping the high-order fragmentation problem at the cost of TLB pressure and slower access.
• CMA (dma_alloc_contiguous and friends) — for very large contiguous DMA regions that the buddy allocator could never reliably satisfy under fragmentation; CMA reserves movable pageblocks at boot and evacuates them on demand.

The decision tree “kmalloc, vmalloc, alloc_pages, or a kmem_cache?” is owned by the Linux Memory Management MOC and the GFP Flags and Allocation Contexts note.

Production Notes

The buddy allocator was described in this form for Linux by Mel Gorman in his Understanding the Linux Virtual Memory Manager book (the “Physical Page Allocation” chapter), and the anti-fragmentation grouping that turned it from “splits and merges” into “splits, merges, and groups by mobility” was Gorman’s work, merged with the LWN-tracked “Group pages of related mobility together to reduce external fragmentation” series. In real systems, the buddy allocator’s health is watched through /proc/buddyinfo and the nr_free_pages / pgalloc/pgfree counters in /proc/vmstat; the canonical operational symptom of buddy trouble is an order-N allocation failure splat in dmesg (e.g. page allocation failure: order:4), which prints the buddyinfo-style free-area breakdown so you can see exactly which orders were exhausted. The standard remediations — raising vm.min_free_kbytes to keep more contiguous memory in reserve, enabling compaction, or restructuring a driver to use vmalloc/scatter-gather instead of high-order contiguous allocations — all follow from understanding that the failure is fragmentation, not a shortage of total memory.

See Also

• Page Order and Fragmentation — the problem this allocator fights: internal/external fragmentation, why high-order requests fail, migratetype anti-fragmentation grouping, and the compaction connection.
• Watermarks and the Allocation Fast Path — the min/low/high watermark gate that sits in front of the buddy free lists and decides allocate-now vs wake-reclaim.
• Per-CPU Page Lists — the lock-free per-CPU cache of order-0 (and small-order) pages layered above the buddy free lists.
• Memory Zones and Nodes — the DMA/DMA32/Normal/Movable zones and NUMA nodes the allocator iterates; each zone owns one free_area[].
• GFP Flags and Allocation Contexts — how callers encode “can I sleep / do I/O / trigger reclaim / need DMA-able memory” into every allocation.
• The Slab Allocator and SLUB — the layer above that carves buddy pages into small kernel objects.
• Memory Compaction — defragments physical memory by migrating pages to free contiguous runs for high-order buddy allocations.
• Linux Memory Management MOC — section 4, The Page Allocator (Buddy System).