Page Order and Fragmentation

An allocation order is the exponent in the buddy allocator’s power-of-two block size: an order-n request asks for 2ⁿ physically contiguous page frames. The order concept is what makes the buddy system efficient, but it also exposes its central weakness — fragmentation. Over time, as blocks of mixed sizes and lifetimes are allocated and freed, free memory shatters into small scattered pieces; eventually there is plenty of total free memory but no contiguous run large enough to satisfy a high-order request, and the allocation fails despite free memory existing. Linux fights this not by changing the buddy algorithm but by grouping pages by mobility — sorting allocations into migratetypes (unmovable, movable, reclaimable) and confining each class to its own pageblocks, so that the movable pages (which dominate, and which can be relocated) cluster together and can later be evacuated by compaction to rebuild large contiguous blocks. This anti-fragmentation grouping was Mel Gorman’s 2007 work (LWN) and remains the design in the v6.12 long-term-support kernel (released 2024-11-17).

This note is the why companion to The Buddy Allocator, which covers the how (free lists, split/merge, entry points). Here the subject is the problem: what order means for fragmentation, the difference between internal and external fragmentation, why high-order allocations fail, and the design rationale behind migratetype grouping, pageblocks, fallback stealing, and compaction. The mechanism of fallback stealing (steal_suitable_fallback) and the free-list data structures live in the buddy note; this note explains why they are shaped the way they are.

Order, in Two Sentences

Order n means 2ⁿ pages. Order 0 is one page (4 KiB on x86-64), order 1 is two pages (8 KiB), order 3 is eight pages (32 KiB), order 9 is 512 pages (2 MiB — one transparent huge page worth), and the default maximum order 10 is 1024 pages (4 MiB), bounded by MAX_PAGE_ORDER = 10 in include/linux/mmzone.h. A request’s order is the smallest power of two that holds the requested size, rounded up — which is the seed of internal fragmentation.

Two Kinds of Fragmentation

The word “fragmentation” hides two distinct problems, and the buddy allocator trades one against the other.

Internal fragmentation is wasted space inside an allocated block. Because the buddy allocator only hands out power-of-two-page blocks, a request for 5 pages must round up to an order-3 block (8 pages), wasting 3 pages. A 4100-byte request rounds up to order-1 (8 KiB), wasting almost half. This waste is internal to the granted allocation — the caller holds the whole block but uses only part of it. The buddy allocator’s coarse power-of-two granularity makes internal fragmentation its inherent cost; this is precisely why SLUB layer exists, to sub-divide a buddy page into tightly-packed small objects and avoid wasting most of a page on a 64-byte structure.

External fragmentation is the opposite: free memory exists, but it is broken into pieces too small and too scattered to satisfy a large contiguous request. Imagine memory as a row of pages, half of them free — but the free pages are interleaved one-on-one-off with allocated pages. There is 50% free memory and yet not a single free pair of adjacent pages, so an order-1 allocation fails. External fragmentation is the buddy allocator’s Achilles’ heel and the problem the whole anti-fragmentation machinery is built to attack. The buddy coalescing step (merging freed buddies upward) is the first line of defense — it opportunistically rebuilds large blocks the instant both halves are free — but coalescing can only merge a block with its specific aligned buddy, so a single stuck allocated page anywhere in a region blocks the entire region from coalescing up.

flowchart TB
  subgraph INT["Internal fragmentation"]
    direction LR
    REQ["request: 5 pages"] --> BLK["granted: order-3 block<br/>(8 pages)"]
    BLK --> WASTE["3 pages wasted<br/>inside the block"]
  end
  subgraph EXT["External fragmentation"]
    direction LR
    MEM["memory: A . A . A . A .<br/>(A=used, .=free)"] --> FREE["50% free, but<br/>no two adjacent free pages"]
    FREE --> FAIL["order-1 (2-page) alloc FAILS<br/>despite free memory"]
  end

The two faces of fragmentation. What it shows: internal fragmentation (top) is space wasted inside a granted block because the buddy allocator rounds up to a power of two; external fragmentation (bottom) is free memory that exists but is too scattered to form a contiguous block of the needed size. The insight to take: these pull in opposite directions — fine granularity (small blocks) reduces internal waste but invites external scattering; coarse granularity reduces external scattering but wastes more inside each block. The buddy allocator accepts internal fragmentation (mitigated by slab) to keep its merging cheap, and attacks external fragmentation with migratetype grouping and compaction.

Why High-Order Allocations Fail Under Fragmentation

The buddy allocator can only build an order-n block by coalescing two aligned order-(n−1) buddies, recursively down to single pages. An order-10 (4 MiB) block therefore requires 1024 specific, contiguous, aligned pages to all be simultaneously free. A single allocated page anywhere in that 4 MiB span — even one tiny unmovable kernel object — poisons the entire block: the coalescing chain cannot complete, and no order-10 block can form there no matter how much free memory surrounds it. This is why order-0 allocations essentially never fail for lack of contiguity (any free page will do), order-3 and below usually succeed (small runs reassemble readily under reclaim pressure — hence PAGE_ALLOC_COSTLY_ORDER = 3 in mmzone.h, the threshold above which the allocator treats a request as “costly” and is more willing to give up), and order-4-and-up grow progressively more failure-prone as a system’s uptime and workload churn fragment memory.

The kernel even quantifies this with a fragmentation index. Per Documentation/admin-guide/sysctl/vm.rst, the debugfs file extfrag/extfrag_index shows, for each order in each zone, an index where “values tending towards 0 imply allocations would fail due to lack of memory, values towards 1000 imply failures are due to fragmentation and -1 implies that the allocation will succeed as long as watermarks are met.” The extfrag_threshold sysctl (default 500) is the cutoff the kernel uses to decide whether a failing high-order allocation should trigger compaction (fragmentation is the cause, defragmenting will help) or reclaim (there genuinely isn’t enough memory). This index is the formal definition of “is this failure caused by fragmentation or by scarcity?” — symbol by symbol: index → 0 means free pages are scarce relative to the request (reclaim, not compaction, is the cure); index → 1000 means there is enough free memory but it’s too fragmented (compaction is the cure); index = −1 means the allocation would succeed if the zone’s watermarks are met (no fragmentation problem at all).

Anti-Fragmentation: Grouping Pages by Mobility

The key insight behind Linux’s defense, due to Mel Gorman (LWN 2007, “Group pages of related mobility together”), is that not all pages are equally hard to move, and if you keep the easy-to-move pages away from the hard-to-move ones, you can always rebuild large contiguous regions out of the movable areas. Pages are sorted into migratetypes (the enum in mmzone.h, also the second index of the buddy free lists — see The Buddy Allocator):

• MIGRATE_MOVABLE — pages whose contents can be relocated transparently: user anonymous pages and page-cache pages, which the kernel can copy elsewhere and fix up the mappings (this is Page Migration, the primitive compaction relies on). These dominate a typical system’s memory.
• MIGRATE_UNMOVABLE — pages the kernel cannot relocate: kernel data structures, slab objects, page tables, DMA targets. A pointer somewhere holds their physical address, so moving them would require finding and rewriting every reference — generally impossible.
• MIGRATE_RECLAIMABLE — pages that cannot be moved but can be freed under pressure (e.g. some slab caches like the dentry/inode caches, reclaimed via shrinkers). They are a middle ground: you can’t relocate them, but you can throw them away and regenerate them later.

The rationale is decisive: if unmovable pages were scattered uniformly across RAM, every large region would contain at least one immovable page and no high-order block could ever be reliably built. By confining unmovable allocations to their own pageblocks, the kernel guarantees that the movable pageblocks contain only relocatable pages — and any movable pageblock can therefore be evacuated wholesale to assemble a free order-9 or order-10 block on demand. Anti-fragmentation does not eliminate fragmentation; it contains the unmovable kind so that compaction can fix the rest.

Pageblocks: the Granularity of Mobility

Mobility is tracked not per page but per pageblock — a fixed-size, naturally-aligned span of pages that is the unit at which the kernel assigns a migratetype. On x86-64 the pageblock order equals HPAGE_PMD_ORDER (9), so a pageblock is 512 pages = 2 MiB — exactly one transparent-huge-page span, which is no coincidence: the whole point is to be able to free up a contiguous, suitably-aligned region big enough to back a huge page. The definition in include/linux/pageblock-flags.h:

#elif defined(CONFIG_TRANSPARENT_HUGEPAGE)
#define pageblock_order   MIN_T(unsigned int, HPAGE_PMD_ORDER, MAX_PAGE_ORDER)
#else
/* If huge pages are not used, group by MAX_ORDER_NR_PAGES */
#define pageblock_order   MAX_PAGE_ORDER
#endif
#define pageblock_nr_pages   (1UL << pageblock_order)

So with transparent huge pages enabled (the common case), pageblock_order = min(9, 10) = 9 and pageblock_nr_pages = 512. /proc/pagetypeinfo prints this directly — Page block order: 9, Pages per block: 512 (proc.rst). Each pageblock carries a stored migratetype (a few bits in a per-pageblock bitmap), set when the block is first carved out and changed only deliberately. Confining a migratetype to whole pageblocks (rather than per-page) is what makes the scheme cheap: the kernel tracks one migratetype per 2 MiB, not per 4 KiB, and the free-list free_list[migratetype] lookup in the buddy allocator is just an array index.

Fallback Stealing — and Why It Is Careful

Strict separation would be wasteful: if all UNMOVABLE pageblocks are full but MOVABLE ones have free space, refusing to satisfy an unmovable allocation would be absurd. So the allocator falls back — it steals a block from another migratetype following the fallbacks[] table (detailed in The Buddy Allocator). But naive fallback is corrosive to anti-fragmentation: every time an unmovable allocation lands a single page inside a movable pageblock, that pageblock can no longer be fully evacuated, and its value for building huge pages is destroyed.

The kernel’s mitigation, and the reason the fallback code is more subtle than a simple “grab any block,” is twofold. First, it steals the largest available fallback block rather than the smallest — pulling from a big block minimizes the number of separate pageblocks polluted (find_suitable_fallback() / can_steal_fallback() in page_alloc.c). Second, when it can, it converts the entire pageblock to the requesting migratetype and moves all the block’s free pages onto the new migratetype’s free list (steal_suitable_fallback() claims the whole block when free_pages + alike_pages >= (1 << (pageblock_order - 1)), i.e. at least half the block is free or already-compatible). Converting the whole block means future frees in that pageblock land on the correct list and the pollution is concentrated in one already-mixed block rather than smeared across many clean ones. The allocator also boosts watermarks (boost_watermark()) on a fallback event, raising reclaim pressure so kswapd proactively frees memory and reduces the chance of future fallbacks. This is anti-fragmentation as damage control: fallback is allowed, but every fallback is structured to do the least harm to future high-order availability.

The Role of Compaction

Anti-fragmentation grouping is a preventive measure — it keeps movable pages clustered so that large contiguous regions remain recoverable. The recovery itself is memory compaction: a defragmentation pass that scans a zone with two cursors moving toward each other — a migrate scanner walking up from the bottom collecting in-use movable pages, and a free scanner walking down from the top collecting free pages — and relocates the movable pages into the free slots (Page Migration), sweeping used pages to one end and free pages to the other until a contiguous free block of the requested order emerges. Compaction only works because of the grouping: it can only relocate MIGRATE_MOVABLE pages, so the more strictly movable pages have been confined to movable pageblocks, the more effective compaction is. Together they form the loop: grouping keeps the mess contained, compaction periodically cleans it up. Compaction fires on demand when a high-order allocation’s fragmentation index exceeds extfrag_threshold, in the background via kcompactd, and proactively per the compaction_proactiveness sysctl (per vm.rst).

Failure Modes and Common Misunderstandings

“I have 8 GB free, why did my order-4 allocation fail?” Because free total says nothing about free contiguous. Read /proc/buddyinfo: a row dense on the left (high order-0/order-1 counts) and empty on the right means external fragmentation. The fix is compaction or restructuring the allocation, not adding RAM. The classic dmesg splat is page allocation failure: order:4, mode:... followed by a buddyinfo dump showing the exhausted high orders.

Confusing internal and external fragmentation. They are opposites. Internal = waste inside a too-big block (cured by finer granularity / slab). External = free memory too scattered (cured by coarser grouping / compaction). A fix for one can worsen the other; the buddy+slab+compaction stack is a deliberate balance.

“Anti-fragmentation prevents fragmentation.” No — it contains it. Unmovable pages still fragment their own pageblocks; the guarantee is only that movable pageblocks stay evacuable. A workload that allocates and pins enormous numbers of unmovable kernel objects (leaky drivers, excessive slab) can still fragment memory in ways compaction cannot fix, because compaction cannot move unmovable pages.

THP allocations are the canonical victim. A transparent huge page needs a 2-MiB contiguous, aligned, fully-movable region (one order-9 block). Under fragmentation these become unavailable, THP allocation falls back to 4-KiB pages, and the TLB-reach benefit evaporates — which is the single most common real-world consequence of external fragmentation. Watching thp_fault_fallback in /proc/vmstat climb is the symptom.

Order is not size in bytes. A common off-by-a-factor error is treating “order 4” as “4 pages” or “4 KiB.” Order 4 is 2⁴ = 16 pages = 64 KiB on x86-64. Always read order as an exponent.

Alternatives and When to Choose Them

The real question is usually “how do I avoid needing a high-order contiguous allocation at all?”:

• Use vmalloc() instead of high-order alloc_pages() when you need a large buffer that must be virtually contiguous but not physically contiguous. vmalloc stitches order-0 pages (which never suffer external-fragmentation failure) into a contiguous virtual mapping, sidestepping the problem entirely — at the cost of extra page-table setup and TLB pressure. See The Buddy Allocator’s alternatives section.
• Use scatter-gather / chained buffers in drivers so the hardware can DMA from many small physically-discontiguous chunks, eliminating the need for one big contiguous region.
• Reserve memory up front with CMA for the rare case (large camera/video DMA buffers) where a big physically contiguous region is genuinely required and cannot be assembled reliably at runtime.
• Raise vm.min_free_kbytes to keep a larger reserve of contiguous free memory, reducing fragmentation-induced failures at the cost of usable RAM.

Production Notes

The grouping-by-mobility design has been load-bearing in Linux since the late 2.6 series (the patch series was posted to LWN in 2007) and is unchanged in principle in v6.12.

Uncertain

Verify: the exact mainline release that first merged grouping-by-mobility (commonly cited as 2.6.24, ~2007). Reason: the LWN article is the v28 patch series, dated 2007, not a merge-commit confirmation; the specific stable release is from memory. To resolve: check the git history of mm/page_alloc.c for the commit introducing MIGRATE_*/fallbacks[] and read off its first-appearing tag. uncertain The operational toolkit is small and direct: /proc/buddyinfo (free blocks per order — left-heavy = fragmented), /proc/pagetypeinfo (the same broken down by migratetype — shows whether unmovable pages have leaked into movable blocks), /proc/vmstat counters (compact_*, thp_fault_fallback, pgmigrate_*), and the extfrag/extfrag_index debugfs file for the formal fragmentation index. The recurring production story is a long-uptime server (databases, container hosts) whose THP allocation rate quietly degrades as memory fragments, recovered by enabling/encouraging compaction (vm.compaction_proactiveness) or, in the limit, by echo 1 > /proc/sys/vm/compact_memory to force a full compaction pass. Gorman’s foundational write-ups (LWN 2007 on grouping, LWN 2010 on compaction) remain the authoritative narrative of why the design looks the way it does.

See Also

• The Buddy Allocator — the how: free lists, split/merge, __rmqueue_smallest, __free_one_page, fallback-stealing mechanism, /proc/buddyinfo.
• Memory Compaction — the active defragmentation pass that migrates movable pages to rebuild high-order blocks; the cure this note’s grouping enables.
• Page Migration — the primitive compaction uses to relocate a movable page and fix up every mapping.
• Transparent Huge Pages — the canonical high-order (order-9) allocation whose success depends on low fragmentation.
• The Slab Allocator and SLUB — sub-divides buddy pages into small objects, the answer to internal fragmentation.
• Watermarks and the Allocation Fast Path — the watermark gate; fallback events boost watermarks to drive reclaim.
• Memory Zones and Nodes — fragmentation and compaction are per-zone; each zone has its own free-area and migratetype state.
• Linux Memory Management MOC — section 4, The Page Allocator (Buddy System).