wire / wire-format / page-allocator

Linux page allocator (buddy system)

The Linux page allocator uses the buddy system for physical page allocation. Memory is divided into blocks of power-of-2 pages (order 0 = 1 page, order 1 = 2 pages, ..., order 10 = 1024 pages = 4MB). Free blocks are kept in per-order free lists. Allocation: find smallest free block >= requested size, split if larger (buddy). Deallocation: coalesce with buddy if free. Per-zone (DMA, DMA32, Normal, Movable, Device) and per-node (NUMA).

wire-format kind wire-format status standard verification verified tier B wire-format@1

aka: Linux page allocator (buddy system)

wire format

spec: Linux kernel (buddy allocator)

The Linux page allocator uses the buddy system for physical page allocation. Memory is divided into blocks of power-of-2 pages (order 0 = 1 page, order 1 = 2 pages, ..., order 10 = 1024 pages = 4MB). Free blocks are kept in per-order free lists. Allocation: find smallest free block >= requested size, split if larger (buddy). Deallocation: coalesce with buddy if free. Per-zone (DMA, DMA32, Normal, Movable, Device) and per-node (NUMA).

fieldsizemeaning
Order0-10 (or higher)Order n = 2^n pages. Order 0 = 1 page (4KB), order 10 = 1024 pages (4MB).
Free listper order, per zoneDoubly-linked list of free blocks of each order.
AllocationO(log n)Find smallest free block >= requested. If larger, split (buddy). May allocate from higher order.
DeallocationO(log n)Free block. Check if buddy is free; if so, coalesce. Repeat.
Zonesper nodeDMA (0-16MB), DMA32 (0-4GB), Normal (4GB+), Movable, Device. Each zone has its own free lists.
NUMAper nodeEach NUMA node has its own zones. Allocation prefers local node.
FragmentationmetricExternal fragmentation: free memory split into small blocks. Compaction (memory compaction) defragments.
Watermarksper zonemin, low, high watermarks. When free memory drops below 'low', kswapd (reclaim) starts. Below 'min', direct reclaim (blocking).

example:

00 00 00 00

Buddy allocator (placeholder)


provenance

agent: curl -H 'accept: application/json' wire.phall.io/wire-format/page-allocator or /wire-format/page-allocator.json