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.

To state the boundaries explicitly, because this note sits in a dense neighbourhood: this note owns the buddy mechanism — the free_area data structure, the order range and MAX_PAGE_ORDER, the buddy-finding XOR, expand(), __free_one_page(), the __rmqueue* family including fallback stealing, and how to read /proc/buddyinfo. It does not own the surrounding policy. The layering, top to bottom, is: SLUB is the buddy allocator’s biggest customer (it buys whole pages and retails objects out of them — everything about slab geometry, per-CPU freelists and /proc/slabinfo lives there, not here); GFP flags encode what a caller is allowed to do to get memory; watermarks own the fast-path/slow-path split and the decision to wake reclaim; zones and nodes own which free_area array gets consulted and in what order; per-CPU page lists own the lock-free cache in front of the free lists; Page Order and Fragmentation owns the fragmentation taxonomy and the rationale for mobility grouping; and Memory Compaction owns the repair mechanism. Where this note touches those subjects it does so only far enough to make the buddy mechanism intelligible, and links out.

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.

Because everything in this allocator is a power of two, the whole order axis fits in one table. Memorize this table and most of /proc/buddyinfo, most dmesg allocation-failure splats, and most of the huge-page story stop needing arithmetic:

Order	Pages (2ⁿ)	Size @ 4 KiB base page	What typically lives here
0	1	4 KiB	Anonymous/file page faults, page-table pages, the overwhelming majority of all allocations
1	2	8 KiB	`kmalloc-8k` slabs, x86-64 kernel thread stacks when `vmalloc`-backed stacks are off
2	4	16 KiB	Larger SLUB slabs, some network ring descriptors
3	8	32 KiB	`PAGE_ALLOC_COSTLY_ORDER` — the last “cheap” order (see below)
4	16	64 KiB	Jumbo-frame skb buffers, some driver DMA rings — the first order that routinely fails under fragmentation
5	32	128 KiB	Large per-CPU chunk allocations
6	64	256 KiB	Rare; large contiguous driver buffers
7	128	512 KiB	Rare
8	256	1 MiB	Rare
9	512	2 MiB	`pageblock_order` on x86-64 with THP; one PMD-mapped huge page (Transparent Huge Pages, hugetlbfs and Reserved Huge Pages)
10	1024	4 MiB	`MAX_PAGE_ORDER` — the largest block the allocator will ever hand out or coalesce into

Two of those rows are load-bearing constants rather than mere sizes. Order 3 is PAGE_ALLOC_COSTLY_ORDER, defined as #define PAGE_ALLOC_COSTLY_ORDER 3 in mmzone.h — above this order the kernel treats an allocation as expensive and stops retrying indefinitely in the slow path, which is why an order-4 failure is a realistic event and an order-0 failure essentially means the machine is dying. Order 9 is pageblock_order on x86-64: with CONFIG_TRANSPARENT_HUGEPAGE=y, pageblock-flags.h defines pageblock_order as MIN_T(unsigned int, HPAGE_PMD_ORDER, MAX_PAGE_ORDER), i.e. min(9, 10) = 9. That is the granularity at which migratetypes are tracked — a fact that matters enormously in the fallback section below.

MAX_PAGE_ORDER is not universally 10. It is CONFIG_ARCH_FORCE_MAX_ORDER where an architecture defines that symbol, and the values differ sharply because they are tied to each architecture’s huge-page size:

Architecture / config	`MAX_PAGE_ORDER`	Max block	Source
x86-64 (all configs)	10 (the generic default — `arch/x86/Kconfig` does not define `ARCH_FORCE_MAX_ORDER` at all)	4 MiB	v6.12 `arch/x86/Kconfig` — verified absent by grep
arm64, 4 KiB pages	10	4 MiB	v6.12 `arch/arm64/Kconfig` L1612
arm64, 16 KiB pages	11	32 MiB	same
arm64, 64 KiB pages	13	512 MiB	same
powerpc64, 4 KiB pages	12	16 MiB	v6.12 `arch/powerpc/Kconfig` L893
powerpc64, 64 KiB pages	8	16 MiB	same
arm (32-bit), default	10	4 MiB	v6.12 `arch/arm/Kconfig` L1294

The pattern is that each architecture sets the bound so the largest buddy block is at least its natural huge-page size: arm64 with 64 KiB base pages has a 512 MiB PMD-level huge page, so its buddy allocator must be able to track order-13 blocks. This is also why 1 GiB pages on x86-64 are “gigantic” — order 18, eight orders above MAX_PAGE_ORDER, so the buddy allocator structurally cannot produce one (see hugetlbfs and Reserved Huge Pages).

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).

Rather than trust release notes, this was dated by existence-checking: fetching the identical path include/linux/mmzone.h at successive release tags from raw.githubusercontent.com and recording what each one actually contains. The result is unambiguous:

Tag	`MAX_ORDER`	`MAX_PAGE_ORDER`	`NR_PAGE_ORDERS`	`free_area[]` declared as	Max usable order
v6.2	`11` (exclusive)	—	—	`free_area[MAX_ORDER]`	10
v6.3	`11` (exclusive)	—	—	`free_area[MAX_ORDER]`	10
v6.4	`10` (inclusive)	—	—	`free_area[MAX_ORDER + 1]`	10
v6.5	`10` (inclusive)	—	—	`free_area[MAX_ORDER + 1]`	10
v6.7	`10` (inclusive)	—	—	`free_area[MAX_ORDER + 1]`	10
v6.8	gone	`10`	`MAX_PAGE_ORDER + 1`	`free_area[NR_PAGE_ORDERS]`	10
v6.12 (this note’s pin)	gone	`10`	`MAX_PAGE_ORDER + 1`	`free_area[NR_PAGE_ORDERS]`	10
v6.18	gone	`10`	`MAX_PAGE_ORDER + 1`	`free_area[NR_PAGE_ORDERS]`	10

Read the table across and the trap becomes obvious: the largest usable order has been 10 the entire time. Nothing about the allocator’s capability changed in either release. What changed was what the name means, and then what the name is — and code that said for (o = 0; o < MAX_ORDER; o++) silently became an off-by-one in 6.4, which is precisely why the 6.8 rename happened. Note also that v6.18 — which is itself a longterm release, alongside the v6.12 this note pins (kernel.org releases, checked 2026-09-11) — is byte-for-byte identical to v6.12 on all four of these constants, so everything in this note about the order range applies unchanged to both.

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[] at page_alloc.c L259–L270: "Unmovable", "Movable", "Reclaimable", "HighAtomic", "CMA", "Isolate" — and those are exactly the type labels you see in /proc/pagetypeinfo.

The complete set, with what each one is for and where it falls back to when it runs dry:

Migratetype	Value	Config gate	What goes here	Falls back to (in order)	Who is allowed to take from it
`MIGRATE_UNMOVABLE`	0	always	Kernel objects the kernel cannot relocate: SLUB slabs, page tables, DMA buffers, anything with an unknown number of raw pointers into it	`RECLAIMABLE` → `MOVABLE`	anyone, via fallback
`MIGRATE_MOVABLE`	1	always	User anonymous and page-cache pages — relocatable, because the kernel owns every reference through the page tables and the rmap (Memory Compaction migrates exactly these)	`RECLAIMABLE` → `UNMOVABLE`	anyone, via fallback
`MIGRATE_RECLAIMABLE`	2	always	Not movable, but droppable under pressure: dentry and inode caches, and other `SLAB_RECLAIM_ACCOUNT` slabs	`UNMOVABLE` → `MOVABLE`	anyone, via fallback
`MIGRATE_HIGHATOMIC`	3 (aliased to `MIGRATE_PCPTYPES`)	always	A reserve, not a workload class: high-order blocks set aside so `GFP_ATOMIC` order-N allocations from interrupt context have somewhere to draw from when everything else is fragmented	none — it is a destination, not a source	only allocations carrying `ALLOC_RESERVES`; ordinary allocations have `nr_free_highatomic` subtracted from their usable free count in `__zone_watermark_unusable_free()`
`MIGRATE_CMA`	4	`CONFIG_CMA`	Contiguous Memory Allocator pageblocks: accept only movable pages, so the whole range can be evacuated on demand for a large DMA buffer	n/a — has its own `__rmqueue_cma_fallback()`	movable allocations carrying `ALLOC_CMA`
`MIGRATE_ISOLATE`	5	`CONFIG_MEMORY_ISOLATION`	A temporary state, not a home: “can’t allocate from here”. Set while a range is being hot-unplugged, CMA-allocated, or compacted	n/a	nobody — that is the point

Two things in that table are easy to get wrong. First, MIGRATE_PCPTYPES is not a migratetype; it is the literal count 3 marking where the “real” workload classes stop, and MIGRATE_HIGHATOMIC is defined as equal to it (MIGRATE_HIGHATOMIC = MIGRATE_PCPTYPES), so the first three types — and only those three — are the ones cached on the per-CPU page lists. Second, CMA and ISOLATE are conditionally compiled, so MIGRATE_TYPES is 4, 5, or 6 depending on .config; on the Fedora kernel used for the live output later in this note, /boot/config-* shows both CONFIG_CMA=y and CONFIG_MEMORY_ISOLATION=y, so all six exist.

The HIGHATOMIC reserve is sized dynamically rather than tuned. reserve_highatomic_pageblock() caps it at roughly 1% of the zone’s managed pages, rounded up to a whole number of pageblocks, with a minimum of one pageblock — and if 1% of the zone is smaller than a single pageblock, no reserve is created at all (page_alloc.c L2032–L2048):

	if ((zone_managed_pages(zone) / 100) < pageblock_nr_pages)
		return;
	max_managed = ALIGN((zone_managed_pages(zone) / 100), pageblock_nr_pages);
	if (zone->nr_reserved_highatomic >= max_managed)
		return;

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 (mm/internal.h L610–L643):

static inline struct page *find_buddy_page_pfn(struct page *page,
			unsigned long pfn, unsigned int order, unsigned long *buddy_pfn)
{
	unsigned long __buddy_pfn = __find_buddy_pfn(pfn, order);
	struct page *buddy;
 
	buddy = page + (__buddy_pfn - pfn);          /* pointer arithmetic on the mem_map */
	if (buddy_pfn)
		*buddy_pfn = __buddy_pfn;
 
	if (page_is_buddy(page, buddy, order))       /* free? same order? same zone? */
		return buddy;
	return NULL;
}

The line buddy = page + (__buddy_pfn - pfn) is worth pausing on: it converts a PFN difference into a struct page * by adding it to the current page pointer, which works only because the mem_map array of struct page is contiguous over at least MAX_PAGE_ORDER pages — stated as an explicit assumption in the comment above __find_buddy_pfn(). That assumption is what the #error Allocator MAX_PAGE_ORDER exceeds SECTION_SIZE check in mmzone.h protects.

The key property the XOR gives you is that one page frame has a different buddy at every order, and which one you mean depends entirely on the order you are currently holding:

flowchart LR
  PFN["PFN 8<br/>0b0000_1000"]
  PFN --> O0["order 0: 8 XOR 1 = 9"]
  PFN --> O1["order 1: 8 XOR 2 = 10"]
  PFN --> O2["order 2: 8 XOR 4 = 12"]
  PFN --> O3["order 3: 8 XOR 8 = 0"]
  PFN --> O4["order 4: 8 XOR 16 = 24"]

The buddy of PFN 8 at each order, computed by __find_buddy_pfn(). What it shows: “the buddy” is not a property of a page — it is a property of a (page, order) pair. PFN 8 pairs with 9 when it is a single page, with 10 when it heads a 2-page block, with 12 when it heads a 4-page block, and with 0 when it heads an 8-page block — note that at order 3 the buddy is below it, because bit 3 of 0b1000 is set and flipping it clears it. The insight to take: the XOR both finds the neighbour and tells you which of the pair is the lower one, which is why the merge step can compute the combined block’s start as a simple buddy_pfn & pfn — AND-ing two PFNs that differ in exactly one bit yields the smaller of them.

Working the alignment requirement from the other side makes the invariant concrete. An order-2 block may start at PFN 8, 12, 16, 20, … but never at PFN 9, 10, 11, 13 — those are not multiples of 4. If a misaligned order-2 “block” at PFN 9 were somehow allowed, 9 ^ 4 = 13 would name a range (13–16) that overlaps the wrong neighbours and merging would corrupt memory. This is why __free_one_page() opens with a hard assertion rather than a graceful error:

	VM_BUG_ON_PAGE(pfn & ((1 << order) - 1), page);

(1 << order) - 1 is a mask of the low order bits; if any of them are set in the PFN, the block is not order-aligned and the kernel panics on the spot.

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.

Drawn as a tree, with concrete page-frame numbers, the split is easier to hold in mind than the loop is:

flowchart TB
  A["order-3 block<br/>PFN 8..15 (8 pages, 32 KiB)"]
  A -->|"keep low half"| B["order-2<br/>PFN 8..11"]
  A -->|"push high half to free_area[2]"| B2(["FREE order-2<br/>PFN 12..15"])
  B -->|"keep low half"| C["order-1<br/>PFN 8..9"]
  B -->|"push high half to free_area[1]"| C2(["FREE order-1<br/>PFN 10..11"])
  C -->|"keep low half"| D["order-0<br/>PFN 8 — RETURNED TO CALLER"]
  C -->|"push high half to free_area[0]"| D2(["FREE order-0<br/>PFN 9"])
  style D fill:#2d6a4f,color:#fff

expand(zone, page, low=0, high=3, mt) splitting one 8-page block down to a single page. What it shows: each loop iteration decrements high, halves size, and hands the upper half (&page[size]) to the free list one order down, while the caller keeps walking down the lower half. Three iterations produce three newly-freed blocks — one order-2, one order-1, one order-0 — plus the single page the caller asked for. The insight to take: the returned page is always the lowest-PFN page of the original block, and the leftovers are always the upper halves. This is not incidental: it is why a long run of small allocations out of one big block yields physically ascending addresses, which the comment above expand() credits as “a critical factor in sglist merging’s success” — scatter-gather lists can coalesce adjacent segments because the allocator hands out ascending, adjacent pages rather than scattering them.

The cost of a split is the reason the buddy allocator is described as O(log N): the loop runs at most high - low times, and high is bounded by MAX_PAGE_ORDER = 10, so no allocation ever performs more than ten split steps, regardless of how much memory the machine has.

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 branch that decides whether the buddy free lists are touched at all is in rmqueue() (page_alloc.c L3066–L3093), and it is the single most important performance fact about this allocator: zone->lock is a per-zone spinlock, so on a large machine every CPU allocating order-0 pages would serialize on one cache line. The per-CPU lists exist to make that not happen.

flowchart TB
  START["rmqueue(zone, order, migratetype)"] --> PCP{"pcp_allowed_order(order)?<br/>order &lt;= 3, or order == 9 with THP"}
  PCP -->|yes| PL["rmqueue_pcplist()<br/>local_lock, NO zone-&gt;lock"]
  PL --> HIT{"pcp list<br/>non-empty?"}
  HIT -->|yes| DONE["return page<br/>FAST PATH — no zone lock taken"]
  HIT -->|"no (refill)"| BULK["rmqueue_bulk()<br/>takes zone-&gt;lock ONCE,<br/>pulls pcp-&gt;batch pages"]
  BULK --> DONE
  PCP -->|no| RB["rmqueue_buddy()<br/>spin_lock_irqsave(&amp;zone-&gt;lock)"]
  RB --> RQ["__rmqueue()"]
  RQ --> DONE2["return page<br/>SLOW PATH — zone lock held"]
  style DONE fill:#2d6a4f,color:#fff
  style DONE2 fill:#7f5539,color:#fff

The rmqueue() branch point that determines whether zone->lock is taken. What it shows: pcp_allowed_order() (page_alloc.c L542–L551) returns true for order <= PAGE_ALLOC_COSTLY_ORDER (that is, orders 0–3) and, when CONFIG_TRANSPARENT_HUGEPAGE is set, also for order == HPAGE_PMD_ORDER (order 9 on x86-64). Those orders go to the per-CPU lists; everything else goes straight to the buddy free lists under the zone lock. The insight to take: the buddy allocator’s split/coalesce machinery is not on the hot path for ordinary allocation. The common case — an order-0 anonymous page fault — normally hits a per-CPU list and never touches a free_area at all; the zone lock is taken once per pcp->batch pages on refill, amortizing it. The buddy proper is what you fall through to for anything larger than 32 KiB, and for the refills. The list layout itself (order_to_pindex() packs MIGRATE_PCPTYPES × (PAGE_ALLOC_COSTLY_ORDER + 1) = 12 low-order lists plus two THP-order lists) is Per-CPU Page Lists’s subject, not this note’s. 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.

Traced concretely with the arithmetic spelled out — free PFN 9 as a single page, into a zone where PFNs 8, 10 and 11 are already free but 12–15 are in use:

flowchart LR
  subgraph S0["Step 1 — free PFN 9, order 0"]
    A1["block pfn=9 order=0"] --> A2["buddy_pfn = 9 XOR 1 = 8<br/>0b1001 XOR 0b0001 = 0b1000"]
    A2 --> A3{"is PFN 8 free<br/>and order 0?"}
    A3 -->|yes| A4["merge<br/>combined = 8 AND 9 = 8<br/>now pfn=8 order=1"]
  end
  subgraph S1["Step 2 — pfn 8, order 1"]
    B2["buddy_pfn = 8 XOR 2 = 10<br/>0b1000 XOR 0b0010 = 0b1010"] --> B3{"is PFN 10 free<br/>and order 1?"}
    B3 -->|yes| B4["merge<br/>combined = 8 AND 10 = 8<br/>now pfn=8 order=2"]
  end
  subgraph S2["Step 3 — pfn 8, order 2"]
    C2["buddy_pfn = 8 XOR 4 = 12<br/>0b1000 XOR 0b0100 = 0b1100"] --> C3{"is PFN 12 free<br/>and order 2?"}
    C3 -->|no| C4["STOP<br/>insert pfn=8 on free_area[2]"]
  end
  A4 --> B2
  B4 --> C2

One call to __free_one_page() cascading two orders up and then stopping. What it shows: each iteration computes buddy_pfn = pfn ^ (1 << order), validates the candidate with page_is_buddy(), and on success pulls the buddy off its free list, sets pfn = buddy_pfn & pfn (which is always the lower of the two, since they differ in exactly one bit), and increments order. The insight to take: freeing is not O(1) and it is not unbounded either — a single free_pages() can do up to ten merges, each removing a block from one free list, and it stops the instant one buddy check fails. Step 2 is the subtle one: at order 1 the buddy of PFN 8 is PFN 10, and “is PFN 10 free at order 1” is asking whether the two-page block 10–11 is free, not whether page 10 alone is. page_is_buddy() checks PageBuddy(buddy) && buddy_order(buddy) == order precisely to answer that question.

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.)

Note what the table’s shape already tells you: it is fallbacks[MIGRATE_PCPTYPES][MIGRATE_PCPTYPES - 1], i.e. only the first three migratetypes have fallbacks at all, and each has exactly two. The comment immediately above it in the source says so flatly: “The other migratetypes do not have fallbacks.” HIGHATOMIC, CMA and ISOLATE are never fallback sources through this table — HIGHATOMIC because it is a reserve that must stay intact, CMA because it has its own gated path, ISOLATE because the whole point of the type is that nothing may be allocated from it.

The full decision, including the two paths most descriptions omit, is __rmqueue() → __rmqueue_fallback() (page_alloc.c L2181–L2255 and L2263–L2293):

flowchart TB
  RQ["__rmqueue(zone, order, mt, alloc_flags)"] --> CMA{"CONFIG_CMA and ALLOC_CMA<br/>and free CMA &gt; half of zone free?"}
  CMA -->|yes| CF["__rmqueue_cma_fallback()<br/>drain CMA first to keep it balanced"]
  CF --> OK(["page"])
  CMA -->|no| SM["__rmqueue_smallest(zone, order, mt)<br/>scan free_area[order..MAX_PAGE_ORDER]<br/>for a block of THIS migratetype"]
  SM --> F1{"found?"}
  F1 -->|yes| EXP["page_del_and_expand()<br/>split down to requested order"]
  EXP --> OK
  F1 -->|no| CMA2{"ALLOC_CMA set?"}
  CMA2 -->|yes| CF
  CMA2 -->|no| FB["__rmqueue_fallback()"]
  FB --> BIG["scan DOWN from MAX_PAGE_ORDER:<br/>find the LARGEST donor block<br/>on a fallback migratetype"]
  BIG --> STEAL{"can_steal_fallback()?<br/>i.e. can we claim the<br/>whole pageblock?"}
  STEAL -->|yes| DO["steal_suitable_fallback()<br/>convert whole pageblock to mt,<br/>then expand remainder"]
  STEAL -->|"no, and request is MOVABLE"| SMALL["find_smallest:<br/>scan UP from requested order,<br/>steal the SMALLEST donor instead"]
  SMALL --> DO
  DO --> OK
  BIG -->|"no donor at any order"| NUL(["NULL — caller enters the slow path"])
  style OK fill:#2d6a4f,color:#fff
  style NUL fill:#9d0208,color:#fff

The complete __rmqueue() decision, from same-migratetype allocation through fallback stealing. What it shows: three things that the usual one-line summary (“it falls back to another migratetype”) hides. (1) The search directions are opposite. __rmqueue_smallest() scans upward from the requested order to waste as little as possible; __rmqueue_fallback() scans downward from MAX_PAGE_ORDER to find the largest donor, because — per the source comment — that “roughly approximates finding the pageblock with the most free pages, which would be too costly to do exactly.” (2) There is an exception for MOVABLE. If the allocator cannot claim the entire donor pageblock and the request is MIGRATE_MOVABLE, it jumps to the find_smallest label and steals the smallest suitable block instead — the source’s reasoning being that a movable page landing in a foreign pageblock “won’t cause permanent fragmentation” because compaction can move it back out later, so there is no reason to break up a big block. (3) CMA is drained preferentially when more than half the zone’s free memory is CMA, which stops CMA reserves from sitting idle while normal memory is consumed. The insight to take: fallback is not a failure mode, it is a carefully-biased heuristic whose whole design goal is to make each act of migratetype pollution as large and as reversible as possible.

One more constraint shapes the search. __rmqueue_fallback() begins by raising its floor:

	if (order < pageblock_order && alloc_flags & ALLOC_NOFRAGMENT)
		min_order = pageblock_order;

With ALLOC_NOFRAGMENT set — which the allocator uses when it would rather try a different zone than fragment this one — sub-pageblock donors are refused outright, so the only fallback considered is one that takes a whole pageblock (order 9 or 10 on x86-64) and converts it wholesale. The why of that policy, and the fragmentation index that drives it, belong to Page Order and Fragmentation and Memory Compaction.

Reading /proc/buddyinfo on a Live System

The buddy allocator’s live state is exposed in two procfs files, both created in vmstat.c’s init_mm_internals() (mm/vmstat.c L2197–L2198):

	proc_create_seq("buddyinfo",    0444, NULL, &fragmentation_op);
	proc_create_seq("pagetypeinfo", 0400, NULL, &pagetypeinfo_op);

The modes matter and are a common source of confusion: /proc/buddyinfo is world-readable (0444), but /proc/pagetypeinfo is root-only (0400) by construction. That is not a distribution hardening choice — it is in the upstream source.

Live output in this section

Everything below was captured on the machine this note was written on: Fedora Linux 44, kernel 7.1.13-200.fc44.x86_64, x86-64, 125 GiB RAM, on 2026-09-11. That is Fedora’s build of upstream stable 7.1.13 (released 2026-09-02, per kernel.org/releases.json fetched 2026-09-11, which at that moment listed mainline 7.3-rc2, latest stable 7.2.5, and longterm 6.18.51 / 6.12.109 / 6.6.156 / 6.1.187 / 5.15.220 / 5.10.269). The source citations in this note are pinned to v6.12 — the vault’s pin, chosen because it is a longterm release, though note it is not the only one: 6.18 is longterm too; the observations come from a 7.1 kernel, which is a fair pairing only because the four constants that govern this output — MAX_PAGE_ORDER = 10, NR_PAGE_ORDERS = 11, PAGE_ALLOC_COSTLY_ORDER = 3, pageblock_order = 9 — were verified identical at v6.12 and v6.18 above, and the buddyinfo format has 11 order columns in all of them. The session ran unprivileged, which is why /proc/pagetypeinfo could not be read (see below).

The columns, and what an actual line says

$ uname -r
7.1.13-200.fc44.x86_64

$ cat /proc/buddyinfo
Node 0, zone      DMA      1      0      0      0      0      0      0      0      1      1      2 
Node 0, zone    DMA32    589    315    317    136     99     63     53     36     36     28    398 
Node 0, zone   Normal  97610 115140 115732  41167  16622   8534   4173   1270    759    708   1860

Field	Meaning
`Node 0`	The NUMA node. This is a single-socket machine, so there is exactly one; a two-socket box prints `Node 0` and `Node 1` blocks.
`zone DMA` / `DMA32` / `Normal`	The zone. Each zone owns its own `free_area[NR_PAGE_ORDERS]`, so these rows are independent allocators that happen to share a node. On x86-64: `DMA` is the first 16 MiB, `DMA32` the first 4 GiB, `Normal` everything above.
Columns 1–11	`zone->free_area[order].nr_free` for order 0, 1, 2, … 10 — the number of free blocks, left to right. There are always exactly `NR_PAGE_ORDERS = 11` columns on a default x86-64 build.

Walking the Normal row by hand: there are 97,610 free single pages, 115,140 free aligned 2-page blocks, … and 1,860 free aligned 1024-page (4 MiB) blocks. Note what is not shown — the migratetype breakdown is collapsed away, and the numbers are blocks, never pages.

The single most common misreading: blocks are not pages

nr_free counts blocks. To get pages you must weight each column by 2^order, and the difference is not a rounding error — it is a factor of eleven on this machine:

Order	Pages/block	Block size	Free blocks	Free pages	Free MiB	Share of zone’s free memory
0	1	4 KiB	97,610	97,610	381.3	2.15%
1	2	8 KiB	115,140	230,280	899.5	5.06%
2	4	16 KiB	115,732	462,928	1,808.3	10.17%
3	8	32 KiB	41,167	329,336	1,286.5	7.24%
4	16	64 KiB	16,622	265,952	1,038.9	5.84%
5	32	128 KiB	8,534	273,088	1,066.8	6.00%
6	64	256 KiB	4,173	267,072	1,043.2	5.87%
7	128	512 KiB	1,270	162,560	635.0	3.57%
8	256	1 MiB	759	194,304	759.0	4.27%
9	512	2 MiB	708	362,496	1,416.0	7.97%
10	1024	4 MiB	1,860	1,904,640	7,440.0	41.86%
total			403,575 blocks	4,550,266 pages	17,774.5 MiB	100%

The order-10 column holds 0.46% of the blocks but 41.86% of the free memory. Anyone eyeballing buddyinfo and concluding “most of my free memory is in single pages” because the left-hand columns are numerically largest has it exactly backwards. Summing all three zones the same way gives 4,550,266 + 446,279 + 1,537 = 4,998,082 pages ≈ 19,524 MiB, which agrees with the MemFree: 19998708 kB (≈19,530 MiB) sampled at the same moment to within 0.03% — the residual is simply that the two files are read at slightly different instants and are not a consistent snapshot.

A one-liner that does the weighting:

awk 'NR>1 { p=0; for (i=5; i<=NF; i++) p += $i * 2^(i-5);
            printf "%s %-7s %10d pages  %8.1f MiB\n", $2, $4, p, p*4/1024 }' /proc/buddyinfo

Watching a split-and-coalesce cycle live

The mechanism in the expand() and __free_one_page() sections is directly observable. The experiment: record buddyinfo, mmap 12 GiB of anonymous memory and touch one byte of every 4 KiB page (12 GiB ÷ 4 KiB = 3,145,728 order-0 faults, each of which must ultimately be carved out of some larger block), record again, munmap it, record a third time.

    char *p = mmap(NULL, 12UL<<30, PROT_READ|PROT_WRITE,
                   MAP_PRIVATE|MAP_ANONYMOUS|MAP_NORESERVE, -1, 0);
    for (size_t off = 0; off < 12UL<<30; off += 4096)
        p[off] = 1;          /* one minor fault -> one order-0 page, 3.1M times */

The zone Normal rows, seconds apart:

### BEFORE                                    MemFree: 19998708 kB
Node 0, zone   Normal  97610 115140 115732  41167  16622   8534   4173   1270    759    708   1860

### AFTER touching 12 GiB                     MemFree:  7368048 kB
Node 0, zone   Normal  38081  46020  16107  10376   6463   3545   1382    434    293    389    469

### AFTER munmap                              MemFree: 19487160 kB
Node 0, zone   Normal  89475 115779 114726  41269  16670   8520   4197   1294    760    718   1735

(The DMA and DMA32 rows did not move by a single block in either direction — the allocator’s zone preference sent every one of those three million faults to Normal, which is Memory Zones and Nodes’s subject.)

Order	Before	After touch	After munmap	Before → touch	Recovered
0	97,610	38,081	89,475	−61%	92%
2	115,732	16,107	114,726	−86%	99%
4	16,622	6,463	16,670	−61%	100%
6	4,173	1,382	4,197	−67%	101%
8	759	293	760	−61%	100%
9	708	389	718	−45%	101%
10	1,860	469	1,735	−75%	93%

xychart-beta
  title "Free blocks per order, zone Normal (log10 of block count)"
  x-axis "allocation order" [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
  y-axis "log10(free blocks)" 0 --> 6
  line "before (idle)" [4.99, 5.06, 5.06, 4.61, 4.22, 3.93, 3.62, 3.10, 2.88, 2.85, 3.27]
  line "after touching 12 GiB" [4.58, 4.66, 4.21, 4.02, 3.81, 3.55, 3.14, 2.64, 2.47, 2.59, 2.67]
  line "after munmap" [4.95, 5.06, 5.06, 4.62, 4.22, 3.93, 3.62, 3.11, 2.88, 2.86, 3.24]

Real /proc/buddyinfo counts for zone Normal, plotted as log₁₀ of the block count because the raw counts span five orders of magnitude (97,610 blocks at order 0 versus 708 at order 9 — a linear axis would flatten the entire right-hand half of the chart into the x-axis). Log₁₀ of a count c is the power to which 10 must be raised to give c; so 4.99 means ≈10^4.99 ≈ 97,600 blocks, and a drop of 1.0 on this axis is a tenfold fall. What it shows: the “after” curve is depressed at every single order, not just the high ones — three million order-0 faults consumed blocks from all eleven free lists, because __rmqueue_smallest() takes the smallest available block and only climbs when the lower lists are empty. The insight to take: the third line is the point. After munmap, the curve lands essentially back on top of the original at every order — __free_one_page()’s coalescing loop reassembled 4 MiB blocks out of three million individually-freed pages, recovering 93% of the order-10 count with no compaction, no kswapd, and no administrator action. Merging is not a background job; it happens inline in the free() path.

Two things in that data are worth dwelling on.

Splitting drains every order, not just the big ones. Order 2 lost 86% of its blocks. That is expand() at work in reverse: each time the order-0, order-1 and order-2 lists ran dry, __rmqueue_smallest() climbed to a bigger block and split it, seeding the lower lists — and those seeds were immediately consumed by the next faults. The 1,391 order-10 blocks that disappeared (1,860 → 469) are 5.4 GiB of 4 MiB blocks shredded into single pages.

Coalescing recovers almost all of it, for free. After munmap, order 10 came back from 469 to 1,735 — 93% of the original. Every one of those restored 4 MiB blocks required ten successful buddy merges to rebuild, and all of them happened inside munmap’s page-freeing loop. The 7% shortfall is the honest part: a handful of pageblocks now have a long-lived allocation sitting in the middle of them, so their buddies never became free and the merge stopped early. That residue is external fragmentation, and it is exactly what Memory Compaction exists to clean up and what Page Order and Fragmentation explains. Run this experiment for days instead of seconds, with a mix of unmovable kernel allocations interleaved, and the right-hand columns stop coming back.

/proc/pagetypeinfo

/proc/pagetypeinfo breaks the same counts down by migratetype and prints the pageblock geometry. On this host it could not be read, and the failure is informative:

$ cat /proc/pagetypeinfo
cat: /proc/pagetypeinfo: Permission denied

$ ls -l /proc/pagetypeinfo
-r--------. 1 root root 0 Sep 11 23:07 /proc/pagetypeinfo

That 0400 is the mode passed to proc_create_seq() in the kernel source quoted above, so every Linux system behaves this way; fragmentation triage by migratetype requires root. The format, per Documentation/filesystems/proc.rst:

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

Free pages count per migrate type at order       0      1      2      3      4  ...
Node    0, zone      DMA, type    Unmovable      0      0      0      1      1  ...
Node    0, zone      DMA, type  Reclaimable      0      0      0      0      0  ...
Node    0, zone      DMA, type      Movable      1      1      2      1      2  ...

Page block order: 9 and Pages per block: 512 are pageblock_order and pageblock_nr_pages — the 2 MiB granularity derived earlier from MIN_T(unsigned int, HPAGE_PMD_ORDER, MAX_PAGE_ORDER). The per-type rows are free_area[order].free_list[type] lengths, i.e. the second dimension that buddyinfo sums away. The classic fragmentation signature is the Movable row collapsing toward the left while Unmovable counts persist on the right: plenty of relocatable memory, but the immovable allocations are spread thinly enough to pin every large block. /proc/pagetypeinfo also prints a second table counting whole pageblocks per migratetype, which is the number to watch when diagnosing migratetype pollution from fallback stealing.

Uncertain

Verify: the per-migratetype free counts and the pageblock-count table on this specific host. Reason: /proc/pagetypeinfo is mode 0400 and this session had no root and no passwordless sudo (sudo -n true → “a password is required”), so no live pagetypeinfo output could be captured; the sample shown above is the kernel documentation’s, not this machine’s. The file’s existence, its 0400 mode, and the format are verified against the running system and the v6.12 source. To resolve: re-run sudo cat /proc/pagetypeinfo on a host with privilege. uncertain

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.

Above order 3 the kernel stops trying as hard. PAGE_ALLOC_COSTLY_ORDER = 3 is not advisory; three separate places in the v6.12 slow path change behaviour at exactly that boundary (page_alloc.c):

should_compact_retry() opens with if (!order || order > PAGE_ALLOC_COSTLY_ORDER) return false; — a costly-order allocation gets no compaction retry loop through this path.
should_reclaim_retry() resets its no_progress_loops counter only when order <= PAGE_ALLOC_COSTLY_ORDER, so a costly allocation burns through MAX_RECLAIM_RETRIES even when reclaim is making progress — the comment says why: “Costly allocations might have made a progress but this doesn’t mean their order will become available due to high fragmentation.”
__alloc_pages_may_oom() carries the comment /* The OOM killer will not help higher order allocs */ immediately above if (order > PAGE_ALLOC_COSTLY_ORDER) goto out; — the kernel would rather return NULL than kill a process to satisfy a 64 KiB contiguous request.

This is why an order-4 failure in dmesg is a routine fragmentation event on a long-running box, while an order-0 failure means something far more serious.

Putting the common symptoms next to their real causes:

Symptom	Actual cause	What to look at	Remedy
`page allocation failure: order:4, mode:0x...` in `dmesg`, plenty of `MemFree`	External fragmentation — no contiguous run that large	The free-area dump the splat itself prints (same shape as `buddyinfo`); check whether the right-hand columns are zero	Raise `vm.min_free_kbytes`; enable/tune compaction; change the driver to use `vmalloc` or scatter-gather
`order:0` allocation failure	Genuine exhaustion, or an atomic allocation ([[GFP Flags and Allocation Contexts\|`GFP_ATOMIC`]]) that could not dip below the min watermark	The `mode:` field in the splat — does it include `__GFP_DIRECT_RECLAIM`?	Fix the caller’s context, or add memory
`alloc_pages()` returns `NULL` immediately with `order > 10`	Rejected outright: `WARN_ON_ONCE_GFP(order > MAX_PAGE_ORDER, gfp)`	The one-time `WARN` in `dmesg`	Use CMA or boot-time reservation — no order above `MAX_PAGE_ORDER` is ever satisfiable (hugetlbfs and Reserved Huge Pages)
`buddyinfo` right-hand columns stay near zero after freeing everything	Long-lived `UNMOVABLE` allocations pinning pageblocks	`/proc/pagetypeinfo` (root) — is `Unmovable` spread across many pageblocks?	Compaction; `vm.min_free_kbytes`; see Page Order and Fragmentation
High `pgalloc`/`pgfree` churn in `/proc/vmstat` with flat `MemFree`	Normal — the pcp lists absorbing an allocate/free-heavy workload	`/proc/vmstat` `pgalloc_normal`, `pgfree`	Nothing; this is the allocator working

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.

vault

Explorer

The Buddy Allocator

The Buddy Allocator

Mental Model

The Order Range and the MAX_ORDER → MAX_PAGE_ORDER Rename

struct free_area and the Per-Migratetype Free Lists

Finding the Buddy: the XOR Trick

Allocation: Walking Up and Splitting Down (expand)

Freeing: Coalescing with Buddies (__free_one_page)

Fallback Stealing When a Migratetype Runs Dry

Reading /proc/buddyinfo on a Live System

The columns, and what an actual line says

The single most common misreading: blocks are not pages

Watching a split-and-coalesce cycle live

/proc/pagetypeinfo

Failure Modes and Common Misunderstandings

Alternatives and When to Choose Them

Production Notes

See Also

Graph View

Table of Contents

Backlinks