Physical Memory Management: Constraints on Allocation from Continuous Blocks

Eight pages are free, yet you cannot allocate two contiguous pages; one node has ample resources, but another constrained allocation still fails. Physical allocation must simultaneously satisfy quantity, shape, location, and wait conditions.

We start by splitting and merging in a 16-page buddy model, then gradually reintroduce NUMA, zones, watermarks, and GFP constraints layer by layer.

1. Understanding Allocation Shape via order

alloc_pages(gfp, order) requests 2^order physically contiguous base pages, returning the corresponding struct page. The base page size is determined by architecture and configuration; if P=4096 bytes, orders 0, 1, and 4 correspond to 4, 8, and 64 KiB respectively. order is not a byte count, nor is it the page count itself.

Assume a managed range spans only PFN 0 to 15, initially a single order 4 free block. Now, request an order 2 allocation, which is 4 pages. The allocator does not need to hand over all 16 pages: it first splits into [0,8) and [8,16), then splits the former into [0,4) and [4,8), retaining two unused buddies for subsequent allocations.

Continuing with two more releases along the diagram clarifies the merge conditions:

If [8,16) is also still free, it can continue merging back to the initial order 4.

Adjacency is not enough: must be same-order, aligned buddies

For block start PFNs aligned to 2^order, the same-order buddy start can be calculated as PFN XOR (1 << order). However, obtaining a number only finds a candidate: you must also verify it belongs to a manageable range, is indeed a same-order free block, and satisfies migration type rules. Two blocks adjacent in address are not necessarily buddies of this order; for example, order 2 blocks [4,8) and [8,12) cannot directly combine into an order 3 block aligned to 8 pages.

Why eight free pages might still not yield two pages

Still using 16 pages, assume all even PFNs are occupied and all odd PFNs are free. Half the memory is free, yet no two pages are contiguous. The total amount is sufficient, but the shape is not. This is external fragmentation, not the applicant requesting more bytes than the total free memory.

If occupied pages are migratable, the kernel might move them to one side, freeing up larger contiguous ranges; if critical positions are occupied by non-migratable objects or long-term pinned pages, compaction may not succeed. If the workload does not fundamentally require physical continuity, the interface design should avoid high orders rather than demanding the allocator create contiguous regions out of any fragmented state. The upper limit for high orders is also determined by the target kernel configuration and should not be hardcoded as MAX_ORDER=11.

If even PFNs are occupied and odd PFNs free, eight pages remain but no free adjacent pair exists. Migration may improve the shape; pinned or unmovable contents can prevent it. Avoid demanding high-order physical continuity when the consumer only needs virtual continuity. Maximum order depends on the target configuration.

2. An Executable Buddy Model

Below, we manage only 16 pages represented by Python integers, without allocating or moving real physical memory. It demonstrates how splitting, same-order merging, and allocation records constrain each other, omitting NUMA, watermarks, PCP, and concurrent synchronization.

free = [set() for _ in range(5)]
free[4].add(0)
allocated = {}

def alloc(order):
    if not 0 <= order < len(free):
        raise ValueError("invalid order")
    source = next((n for n in range(order, len(free)) if free[n]), None)
    if source is None:
        return None
    start = min(free[source])
    free[source].remove(start)
    while source > order:
        source -= 1
        free[source].add(start + (1 << source))
    allocated[start] = order
    return start

def release(start):
    order = allocated.pop(start)  # Reject unallocated/double-free starts
    while order + 1 < len(free):
        buddy = start ^ (1 << order)
        if buddy not in free[order]:
            break
        free[order].remove(buddy)
        start = min(start, buddy)
        order += 1
    free[order].add(start)

a, b = alloc(2), alloc(2)
assert (a, b) == (0, 4)
assert free[3] == {8}
release(a)
assert free[2] == {0}
release(b)
assert free[4] == {0} and not allocated
assert all(not blocks for blocks in free[:4])
print("Split, buddy blocking, and level-by-level merge: Passed")

The real allocator must maintain these invariants under locks and accounting protocols; you cannot directly replace the set operations in the model with lock-free lists. When releasing original high-order allocations, you must also adhere to the order and reference contracts of the corresponding API, and cannot arbitrarily release any individual page within it as an independent allocation result.

3. Nodes and Zones Add Location Conditions to "Available"

NUMA nodes express memory access location and cost, while zones express different usage constraints within the same node. A node does not necessarily equal a CPU socket: the system can have nodes containing only memory, nodes spanning multiple physical address ranges, and single-socket machines may also expose NUMA topology. Remote access cost depends on hardware, access patterns, and congestion, and cannot be fixed as 30% slower.

Local allocation preference on normal nodes can reduce remote access, but user memory policies, cpusets, and allocation flags affect the allowed set and fallback. If an application binds threads only to node 0, but its existing pages are still on node 1, it will not automatically migrate all content just because the thread moves. "First touch" should also be understood as the placement behavior when actually establishing a backing page, not treating the malloc return moment as the moment of physical ownership for all pages.

In common x86 configurations, DMA/DMA32 relates to low address ranges, but "requesting DMA32 memory" cannot replace device DMA masks, IOMMU mappings, and consistency handling. Some memory provided by CXL may also be used as normal System RAM; seeing CXL does not necessarily mean it belongs to ZONE_DEVICE. Topology and structure definitions can be found in Physical Memory.

4. Watermarks Are Not Three Fixed Failure Switches

Free pages reserve a portion of margin to ensure that burst allocations and the reclaim paths themselves can still obtain resources. If normal allocations exhaust all pages, the I/O or metadata requests required for reclaim may also fail to progress, forming a harder-to-break cycle.

Actual checks also include order, low zone protection, unusable free pages, and watermark boost. They are not three fixed switches; you cannot directly deduce "below low means immediate reclaim, below min means OOM."

For example, NORMAL has 1200 free pages, with min/low/high assumed to be 1000/1500/2000. This state suggests background balance should proceed, but you cannot decide based solely on 1200 that an order 4 request will definitely succeed: it might not find 16 contiguous pages, or the request might be constrained by another node or zone. Conversely, some non-waiting allocations fail directly without performing synchronous reclaim on behalf of the caller.

GFP: How Much Work the Caller Allows the Allocator to Do

GFP is a behavioral constraint, not a success rate promise.

__GFP_RECLAIM includes direct reclaim and kswapd-related permissions; it is not simply a new name for __GFP_DIRECT_RECLAIM. __GFP_NORETRY does not completely prohibit any lightweight reclaim attempts. If reclaim inside filesystem or block I/O might re-enter resources held by itself, appropriate NOFS/NOIO scope control is needed; casually changing everything to GFP_ATOMIC only shrinks the resource selection and does not solve dependency design issues. See Memory Allocation Guide.

5. How PCP Caches Reduce Lock Contention and Why They Affect Observation

Assume a CPU continuously allocates and releases many small-order pages. If every operation modifies the zone's global free structure, local operations become shared lock contention. PCP pagesets keep a batch of pages on the CPU side; common allocations take from the local batch cache, replenishing when exhausted; releases enter the local cache first, and are returned in batches only after reaching a threshold.

It spreads out global operations, which also means recently freed pages may not immediately appear in the buddy's high-order free lists. Only after PCP is drained can they merge with other buddies. When observing, distinguish between "system free pages" and "blocks listed by order in the current buddy." Which orders PCP supports and what local synchronization it uses vary by version and configuration; it cannot always be described as "only order 0, completely lock-free."

Migration Types: Grouping Similar Purposes Together

Unlike PCP, migration types primarily try to group allocations with similar migratability, preventing non-migratable objects from being scattered across every large range. RECLAIMABLE means the owning subsystem has the opportunity to reclaim objects; MOVABLE means the physical location can be changed while maintaining semantics. These two are not the same. Fallback and runtime pinned references can still weaken the initial classification effect.

6. Page Descriptors, References, and Memory Offlining

struct page is management metadata, not the page content itself. Field meanings vary by page purpose; normal RAM, compound pages, slab, and device pages should not be forced into a fabricated structure layout. Reference counting and mapping counts answer different questions: a page without user PTE mapping may still be held by the page cache or kernel; obtaining a page pointer does not automatically imply holding an infinitely extendable reference.

If the base page is 4 KiB, and assuming a page descriptor occupies 64 bytes in a certain configuration, this single item accounts for a ratio of 64/4096 = 1.5625%; this calculation is for understanding metadata scale and should not be written as a fixed size for all kernels. Large memory systems must also consider vmemmap organization, reserved areas, and other management structures.

Hotplug: Adding Range and Handing Over to Allocator Are Two Steps

MOVABLE increases offlining opportunities, but long-term pins, non-migratable content, or insufficient migration targets can still prevent offline. See Memory Hotplug.

7. Reading buddyinfo for Evidence, Not Success Guarantees

from pathlib import Path
import os
import re

page_size = os.sysconf("SC_PAGE_SIZE")
for line in Path("/proc/buddyinfo").read_text().splitlines():
    match = re.match(r"Node\s+(\d+),\s+zone\s+(\S+)\s+(.*)", line)
    if not match:
        continue
    node, zone, rest = match.groups()
    blocks = [int(value) for value in rest.split()]
    pages = sum(count * (1 << order) for order, count in enumerate(blocks))
    highest = max((i for i, count in enumerate(blocks) if count), default=None)
    print(f"node={node} zone={zone} buddy_bytes={pages * page_size} "
          f"highest_nonempty_order={highest}")

Each column is the number of blocks for that order, not the number of pages; you must multiply by 2^order and then by the base page size. The highest non-empty order only indicates that blocks of that order existed at the time of reading; concurrent allocations, watermarks, migration types, and node policies can still cause your request to fail. Only by combining zoneinfo watermarks/protections, process NUMA policies, and allocation context can you explain the cause of failure.

The next article, Slab and kmalloc, cuts a batch of physical pages into objects; Page Reclaim and Swap explains how the slow path turns used memory back into available resources.