Why Contiguous Memory Gets Scarce

The Linux kernel's virtual memory model normally hides physical discontinuities: page tables make scattered physical pages appear contiguous to user-space applications. Problems arise, however, when the kernel itself needs a run of physically contiguous pages from its linear mapping area. Block-allocator objects and DMA buffers that cannot use scatter-gather are two common cases. When such requests fail, the kernel may fall back to direct reclaim or compaction, causing unpredictable latency spikes or outright allocation failures.

Eliminating dependence on high-order allocations in the linear mapping is theoretically clean but impractical for a code base the size of Linux. Instead, kernel developers have spent years adding mechanisms that reduce how badly memory fragments in the first place. These efforts date back to the Linux 2.x series and continue today, with mixed reception. At LSFMM 2014, for instance, developers complained that the memory compaction mechanism was inefficient and its bugs hard to reproduce, yet the feature survived and has been refined in later kernels.

Mel Gorman has been the most persistent contributor here. His first major patch set took 28 iterations before landing in Linux 2.6.24. A second set, merged in Linux 5.0, cut memory fragmentation events by 94% on single- and dual-socket machines. The mechanisms below are the foundation those patches build on.

Buddy Allocator Extensions

Linux uses the buddy algorithm for page allocation, extended beyond the textbook version with three features:

  • Partitioned buddy allocator
  • Per-CPU pagesets
  • Grouping by migration type

The kernel organizes physical memory by node, zone, and page, and the partitioned allocator handles one zone within one node. Per-CPU pagesets are an optimization for single-page allocations and have nothing to do with fragmentation. Grouping by migration type is the mechanism aimed at defragmentation.

One historical note: before Linux 4.8, page reclaim was managed per zone, a design left over from 32-bit systems with large high-memory areas. Because different zones aged at different rates, the kernel accumulated awkward patches. Gorman later moved reclaim to be per-node, which resolved these issues. Observability tools based on BPF need to account for that distinction.

Grouping Pages by Mobility

Memory regions differ in how freely their pages can be relocated. For page-table-mapped virtual memory, removing a physical page is a three-step operation:

  1. Allocate a new page.
  2. Copy contents from the old page to the new one.
  3. Update the page-table entry to point at the new page frame number.

The virtual address never changes, so such pages are easy to migrate. The linear mapping area is different: virtual address is physical address plus a constant, so moving a page changes its address. Allocating memory with __GFP_MOVABLE (used for user-space memory) or __GFP_RECLAIMABLE (used for file pages) tells the kernel which pages are safe to move.

When movable and unmovable pages share the same regions, free blocks become interleaved and large contiguous chunks never form. To avoid this, the kernel defines migration types and separates pages accordingly. The three primary ones are MIGRATE_UNMOVABLE, MIGRATE_MOVABLE, and MIGRATE_RECLAIMABLE. The current mix per memory region is visible in /proc/pagetypeinfo.

When an allocation needs a page from a depleted migration type, the kernel steals a whole block from another type, choosing the largest available block to limit damage. Block size is governed by pageblock_order. Stealing priority follows a fixed order:

  • MIGRATE_UNMOVABLE: steal from MIGRATE_RECLAIMABLE, then MIGRATE_MOVABLE
  • MIGRATE_RECLAIMABLE: steal from MIGRATE_UNMOVABLE, then MIGRATE_MOVABLE
  • MIGRATE_MOVABLE: steal from MIGRATE_RECLAIMABLE, then MIGRATE_UNMOVABLE

Frequent stealing is itself a warning sign: it means fragmentation events are occurring, and later allocations may suffer.

Measuring Fragmentation with ftrace

The kernel exposes external fragmentation events through ftrace, which can be enabled and captured as follows. Enable the events with:

echo 1> /sys/kernel/debug/tracing/events/kmem/mm_page_alloc_extfrag/enable

Then start collecting:

cat /sys/kernel/debug/tracing/trace_pipe> ~/extfrag.log

Press Ctrl-C to stop. Each event contains multiple fields:

Linux ftrace events' fields

To gauge real fragmentation pressure, filter for events where fallback_order < pageblock order; on x86_64, pageblock order is 9. When finished, clean up with:

echo 0> /sys/kernel/debug/tracing/events/kmem/mm_page_alloc_extfrag/enable

Grouping by migration type is a delaying tactic, not a cure. It keeps fragmentation from getting out of hand early, but high-order allocations can still fail under sustained load. The follow-up mechanisms the kernel uses to actively regulate fragmentation will be covered in the next part.