Zones, buddy allocation, compaction, and CMA

Before you start#

Read page faults and COW, address spaces and page tables, and locks and sleeping. This chapter describes upstream v6.12. Its allocator exercise uses a supplied sixteen-page model and read-only host counters. Do not create host memory pressure, drop caches, change CMA reservations or modify sysctls.

Learning goals#

Trace a conditional page allocation through zone selection, fast and slow paths and accounting failure. Explain buddy order, splitting and coalescing, watermarks and allocation context. Distinguish fragmentation from total free memory and identify why compaction or CMA cannot guarantee every high-order request succeeds.

A mental model#

Follow an allocation in five questions: what constraints did the caller request; which zones and free blocks are eligible; can the fast path satisfy the request; if not, what recovery does this context permit; and did later accounting accept the pages? The caller only owns a usable result after the allocator returns success. Each step can reject an allocation for a different reason, so “free memory” is not one universal pool. See the v6.12 page allocator and memory allocation guide.

From early memory to zones#

At boot, memblock tracks early physical memory and reservations before the ordinary page allocator is fully available. Later, the buddy allocator manages eligible physical pages. Memory is organized into NUMA nodes and zones; a zonelist supplies an ordered set of candidate zones under policy and allocation constraints. A page frame number, PFN, identifies a base-page frame in the physical-address model. struct page records kernel metadata associated with physical pages, while folios provide a higher-level representation for groups of pages in applicable MM paths. A page frame is not a process virtual address and is not automatically a device DMA address.

Zone names reflect addressability or usage constraints, not universal fixed physical regions. Depending on architecture and configuration, Linux can have ZONE_DMA, ZONE_DMA32, ZONE_NORMAL, ZONE_HIGHMEM, ZONE_MOVABLE and others. x86-64 and arm64 do not necessarily have identical zones, and a particular machine may have an empty or absent zone. Highmem is especially architecture/configuration dependent. The physical memory documentation describes the framework; inspect the running kernel and platform before interpreting a zone name.

Each zone maintains free-area structures for orders and migration types, together with watermarks and accounting. Per-CPU page lists, often called PCP lists, cache certain free pages to reduce contention on shared zone locks. A page in a PCP list is free for allocator purposes under its accounting rules but might not appear in the same buddy-list count a reader expects at a particular instant. Watermarks, reserves, allowed nodes, cpusets and allocation flags mean that a number of nominally free pages does not automatically make them available to every caller.

Source walkthrough#

The allocator's visible interface and profiling wrappers resolve to implementation paths including __alloc_pages_noprof in v6.12 mm/page_alloc.c. This excerpt is from that function (SPDX GPL-2.0-only; preparation and slow-path statements omitted):

page = get_page_from_freelist(alloc_gfp, order, alloc_flags, &ac);
if (likely(page))
	goto out;

The allocation context ac contains choices such as candidate zones and migration type under the setup path. get_page_from_freelist attempts an allocation subject to those constraints and allocator checks. A non-null result goes to shared post-allocation handling. If the first attempt fails, this function restores relevant allocation context and invokes __alloc_pages_slowpath; failure of the fast path is not automatically final failure or immediate OOM killing. Order bounds and preparation can fail earlier. The exact available reclaim, retry, compaction and reserve behavior depends on the GFP mask and state.

The same function has a post-allocation accounting branch (same file and SPDX notice; condition and surrounding instrumentation omitted):

__free_pages(page, order);
page = NULL;

This branch follows an unsuccessful memory-cgroup kernel-memory charge for a successful allocation when the relevant accounting condition applies. It frees the acquired pages and returns failure rather than leaking or exposing an uncharged allocation. The result demonstrates why “the buddy allocator found a page” and “the caller received a usable page” are distinct states. Callers must check the returned pointer and undo their own prior resources on failure. The memory allocation guide describes common allocation choices.

Orders, splitting and coalescing#

A buddy allocation of order n requests 2^n physically contiguous base pages, aligned to the corresponding block size under the buddy rules. Order 0 is one base page; order 4 is sixteen. This is physical contiguity of the block, not merely sixteen consecutive virtual addresses. Higher order is not a byte count and a successful small allocation does not establish that an adjacent physical page is available. Architectures, page size and configured maximum order affect absolute sizes and limits.

The buddy algorithm can split a larger free block to satisfy a smaller request. When a block is freed, it can merge with its matching free buddy of the same order if zone boundaries, migration type and allocator conditions permit. For an appropriately aligned PFN, the buddy candidate at a given order is derived by toggling the bit for that order, conceptually pfn XOR (1 << order). Merely finding some other free block of the same size is not enough; it must be the matching buddy and eligible for merging. Zone boundaries and metadata rules prevent indiscriminate coalescing.

In mm/internal.h, v6.12, SPDX GPL-2.0-or-later (surrounding code omitted), the helper that computes the candidate buddy is:

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

Notice that the XOR only produces a candidate PFN. The merge decision belongs to the caller and to page_is_buddy, which checks that the buddy is a free buddy page of the same order in the same zone. The excerpt does not show the merge loop, the freeing paths that call it, or the case where the candidate is not in the zone.

Consider a toy zone of sixteen contiguous base pages, PFNs 0–15, initially one aligned free order-4 block. A request for order 2 needs four pages. One possible sequence splits order 4 into two order-3 blocks (0–7 and 8–15), then splits the first into order-2 blocks (0–3 and 4–7), and allocates 0–3. Free blocks 4–7 and 8–15 remain. When 0–3 is returned and no constraints prevent merging, its order-2 buddy is 4–7: they combine to 0–7, which can combine with order-3 buddy 8–15 into the original order-4 block. This is an idealized state, not a dump from the host allocator.

For the counterexample, suppose PFNs 0, 4, 8 and 12 are each occupied by unmovable pages while the other twelve pages are free. There is plenty of free memory by count, but no four-page aligned order-2 block entirely free in this sixteen-page region. Coalescing cannot cross an allocated page. A real allocator has more zones, PCP state and migration types, but the example demonstrates why total free RAM cannot guarantee a physically contiguous high-order allocation.

GFP flags and execution context#

A GFP mask describes allocation constraints and permitted actions. GFP_KERNEL is a common sleepable-context choice and can permit direct reclaim and I/O-related work according to its flags. It must not be used blindly while holding a raw spinlock or in a context where sleeping or recursion into a held subsystem would deadlock. GFP_ATOMIC is intended for contexts that cannot sleep and can use limited reserves under its rules, but it can still fail; reserves are not an unlimited emergency pool. Read v6.12 GFP definitions for the exact release.

In include/linux/gfp_types.h, v6.12, SPDX GPL-2.0 (other definitions and comments omitted):

#define GFP_ATOMIC	(__GFP_HIGH|__GFP_KSWAPD_RECLAIM)
#define GFP_KERNEL	(__GFP_RECLAIM | __GFP_IO | __GFP_FS)
#define GFP_KERNEL_ACCOUNT (GFP_KERNEL | __GFP_ACCOUNT)
#define GFP_NOWAIT	(__GFP_KSWAPD_RECLAIM | __GFP_NOWARN)

The masks are compositions of lower-level flags, so the difference between a sleepable and an atomic caller is which actions are present, not a single "priority" number. GFP_ATOMIC has no direct-reclaim bit, which fits contexts that cannot sleep. The excerpt does not show how each flag is consumed in the slow path, and it does not say how often either mask fails in practice.

Filesystem or block-I/O code may need to restrict reclaim recursion while it holds resources that reclaim would try to acquire. Scoped memalloc_nofs_save/restore and memalloc_noio_save/restore influence the current allocation context under their documented use; simply selecting a flag without understanding the surrounding call chain does not prove deadlock freedom. __GFP_ACCOUNT requests applicable memory-cgroup accounting, which explains the post-allocation charge branch above. Retry modifiers and no-fail requests have strict semantics and are not interchangeable performance preferences. A caller must establish what failure means, release already acquired resources and avoid relying on an allocation that its context forbids.

The fast path applies watermarks and eligible zones before returning a page. The slow path may wake or invoke reclaim, attempt compaction, retry under permitted conditions, or reach an OOM decision. The exact path depends on order, allocation flags, node constraints, watermarks and configuration. A high-order request can fail even while order-0 requests succeed. A nonblocking caller can fail without entering the same reclaim path as a sleepable caller. Do not infer a complete sequence from one NULL result or a single free-memory counter.

Fragmentation, compaction and CMA#

External fragmentation means free pages exist but are not arranged into the contiguous blocks needed by an order request. Compaction attempts to isolate and migrate movable pages so free blocks can form. It can fail or be skipped because suitable pages, migration targets, permissions or time are unavailable. Long-term pinned pages, unmovable kernel allocations, device constraints and zone boundaries can prevent successful consolidation. The v6.12 compaction implementation has multiple outcome and retry paths; the existence of compaction does not promise success or bounded latency for every allocation.

Migration types group pages according to expected mobility and reserve purposes, improving the allocator's ability to form contiguous blocks. They are not perfect physical walls: fallback and special rules exist. The Contiguous Memory Allocator, CMA, reserves suitable regions for allocations requiring contiguity while allowing appropriate movable use under its policy. CMA still needs pages to be migratable and available at allocation time; pinned or otherwise unmovable pages can obstruct it. A CMA allocation is not automatically a CPU virtual mapping or a device DMA mapping. Drivers must use the appropriate subsystem and DMA API rather than treating a PFN as a bus address.

vmalloc can create a virtually contiguous kernel range backed by noncontiguous physical pages; it answers a different requirement from a high-order buddy allocation. Its page tables, context and access restrictions matter, and it does not make a scatter-gather-incapable device able to DMA arbitrary backing. The later kernel-allocation chapter covers that interface. Choose the physical, virtual, DMA and context guarantees required by the actual consumer before choosing an allocator.

Reading allocator evidence#

/proc/buddyinfo reports free blocks by node, zone and order at a moment in time. A count in column n represents blocks of 2^n base pages, but PCP caching, concurrent activity, zone eligibility and watermarks mean that multiplying and summing it is not a promise that a particular caller can allocate. /proc/zoneinfo gives richer zone data; /proc/pagetypeinfo may expose migration-type information depending on permissions and configuration. /proc/meminfo offers a broader summary with different accounting. These files can reveal host capacity and workload characteristics, and a container may expose host-wide values that do not represent its cgroup limit.

For a reasoned diagnosis, record allocation order, GFP context, node/zone constraints, memory-cgroup limit, relevant counters and the earliest error. A failure with many free pages may reflect fragmentation, policy, watermarks, a cgroup charge or an incompatible zone; a low free count alone does not establish which one. Measurements race with normal allocations and can be expensive on a large system. No host allocation stress is required to understand the model.

Watermarks are constraints, not a single free counter#

Imagine a zone has a free order-0 page, but taking it would violate the watermark and reserve rules for a particular allocation. The fast path can skip that zone even though a raw free-page count is nonzero. A different allocation context might be allowed to use a reserve, while another node or zone in the zonelist might satisfy the original request. These choices depend on allocation flags, node masks and kernel state; they are not a promise that a privileged caller can always bypass the allocator's safeguards. The slow path can change the state by reclaiming or compacting, but it can also return failure when those actions are disallowed or unsuccessful.

Now add accounting: a page is found in an eligible zone, but the relevant memory-cgroup charge fails. The quoted branch returns that page to the allocator and reports NULL. This is not external fragmentation, even though the caller sees an allocation failure. A useful investigation therefore separates zone selection, free-block availability, reclaim/compaction and final charging instead of treating all NULL returns as the same event. The caller must also avoid assuming that its own locks allow a slow-path allocation to enter reclaim recursively.

Practice#

Source-only route: draw the sixteen-page split and rejoin sequence. Calculate the buddy of PFN 0 at order 2 as 0 XOR 4 = 4, then the buddy of the combined order-3 block at PFN 0 as 0 XOR 8 = 8. Add the four occupied PFNs in the fragmentation counterexample and explain why twelve free pages do not form an order-2 block there. Annotate the actual fast-path success and accounting-failure branches separately; no allocator invocation is implied.

Read-only host route: run as an ordinary user:

getconf PAGESIZE
head -20 /proc/buddyinfo
head -35 /proc/zoneinfo
head -25 /proc/meminfo
if [ -r /proc/pagetypeinfo ]; then head -25 /proc/pagetypeinfo; else printf 'pagetypeinfo not readable\n'; fi

Output varies by architecture, memory size, kernel and namespace. /proc/pagetypeinfo can be expensive or restricted; omit it if unavailable or inappropriate for the host. These values are snapshots and can reveal hardware and workload information; review before sharing. Do not use sudo, allocate large buffers, force compaction, drop caches or adjust CMA. If a file is hidden, record that visibility limit rather than treating it as a zero count.

Deliver the toy-state table and one carefully labeled observation, such as which node/zone/order columns were visible. As a counterexample, a displayed nonzero high-order count is not a guarantee that a constrained cgroup or device allocation will succeed later. No files are created and no cleanup is needed.

Knowledge check#

1. Why can a high-order request fail despite substantial free memory?
2. What happens in the shown __alloc_pages_noprof accounting branch after a page was found but the charge fails?
3. Why is GFP_ATOMIC not an unlimited guarantee of allocation success?
4. What must be true before two order-2 blocks can merge in the buddy example?
5. Why does virtual contiguity from vmalloc not establish device DMA contiguity?

Answers#

1. Free pages may be fragmented, in an ineligible zone or node, below an applicable watermark, pinned against compaction, or rejected by accounting. The exact failure needs more evidence.
2. The code frees the allocated pages and sets the result to NULL; the caller must handle failure and its own earlier resources.
3. It avoids sleeping under its intended constraints and can use limited reserves, but those reserves and eligible pages can be exhausted.
4. The blocks must be matching aligned buddies of the same order, both free and mergeable under the zone and allocator rules; arbitrary neighboring free blocks are insufficient.
5. Virtual adjacency does not imply physical or device-visible adjacency. Device DMA requires the appropriate mapping and hardware contract.

Checkpoint#

Deliver the split/coalesce and fragmentation tables plus one labeled read-only observation. Pass when you explain the fast-path versus charge-failure distinction, choose GFP context based on sleep/reclaim constraints, and give a reason compaction can fail. If uncertain, retrace __alloc_pages_noprof and recalculate the buddy PFNs. This is not certification.

Sources#

• v6.12 page allocator.
• v6.12 GFP definitions.
• v6.12 compaction.
• Physical memory.
• Memory allocation guide.