vault

Page Allocator

14 min read

Page Allocator

Beneath the size-class machinery sits a layer that does not care about objects at all — it allocates and frees pages, the 8 KiB units (pageSize = 1 << 13) that spans are built from. The page allocator (runtime.pageAlloc, embedded in the mheap) tracks every page in the process’s address space with a single giant bitmap — one bit per page, 1 = in use, 0 = free — and answers the question “where is a run of N contiguous free pages?” To make that search fast over a heap that may span hundreds of gigabytes, it overlays the bitmap with an implicit radix tree of summaries: each tree node records, for the region it covers, the run of free pages at its start, at its end, and the longest run anywhere inside. Allocation walks the tree top-down, using these summaries plus hardware bit-scan instructions to skip vast fully-allocated regions, and performs an address-ordered first-fit. This design replaced the older treap-based allocator in Go 1.14 — the Go 1.14 release notes record that “the page allocator is more efficient and incurs significantly less lock contention at high values of GOMAXPROCS” (go1.14 release notes) — and it remains the allocator as of Go 1.26 (the current stable release; 1.26.3 shipped 2026-05-07), verified directly against the Go master source (mpagealloc.go top comment; proposal 35112).

This note explains the bitmap, the radix-tree summary structure, the top-down search, and the scavenger hook that returns pages to the OS. The size-class/span layer above it is Size Classes and Span Management; the three-tier cache that calls it is mcache mcentral and mheap; the OS reservation/commit machinery below it is Memory Mapping and OS Interaction.

Mental Model

Picture the entire 48-bit virtual address space as one enormous bit array — one bit per 8 KiB page. Searching that array linearly for a free run would be hopeless. So the page allocator builds, on top of the bitmap, a tree of “summaries.” Think of it like a building directory: instead of walking every floor to find an empty room, you read the lobby board (“Floor 3 has the most contiguous space”), go to floor 3, read its board, and so on, descending only into regions that can possibly satisfy you.

Two structural choices make this scale:

  • The bitmap is sharded into chunks of pallocChunkPages pages — 1 << 9 = 512 pages = 4 MiB per chunk on most platforms (logPallocChunkPages = 9; smaller, 1 << 6, on Wasm) (mpagealloc.go, lines 57–65). Chunks are held in a two-level sparse array so the bitmap need not be one contiguous mapping.
  • The radix tree is implicit: each level is one flat array, not pointer-linked nodes. A node’s children are simply the next-level array entries at the corresponding index range. This costs virtual address space (the arrays are reserved for the whole address space) but no per-node pointer overhead and no pointer chasing.
flowchart TD
    L0["L0: each summary covers 16 GiB<br/>(root level)"] --> L1["L1: each covers 2 GiB<br/>(8 children per L0 entry)"]
    L1 --> L2["L2: each covers 256 MiB"]
    L2 --> L3["L3: each covers 32 MiB"]
    L3 --> CH["chunk: 4 MiB = 512 pages<br/>pallocBits bitmap"]
    CH --> PG["page: 8 KiB"]
    SUM["each summary = (start, max, end):<br/>free pages at start / longest run / free pages at end"] -.describes.-> L0

Diagram: the radix tree over the page bitmap. The insight is that each summary is a tiny (start, max, end) triple — three numbers — yet it lets the search prune entire 16 GiB subtrees with one comparison (summary.max() >= npages?). The leaf level is the per-chunk bitmap; everything above is derived metadata.

The Bitmap — pallocBits and Chunks

The leaf data structure is pallocData, holding a chunk’s bitmap. Two bitsets per chunk (mpallocbits.go):

  • pallocBits — the allocation bitmap: pallocChunkPages bits, 1 = page in use, 0 = free.
  • scavenged — a parallel bitmap: 1 = this free page has already been scavenged (returned to the OS), so re-using it will cost a page fault.

Chunks are addressed by chunkIdx. The translation functions are pure arithmetic (mpagealloc.go, lines 112–125):

func chunkIndex(p uintptr) chunkIdx {
	return chunkIdx((p - arenaBaseOffset) / pallocChunkBytes)
}
func chunkPageIndex(p uintptr) uint {
	return uint(p % pallocChunkBytes / pageSize)
}

arenaBaseOffset linearizes the address space — on amd64, “negative” (top-bit-set) addresses are offset by 1<<47 so the index space is contiguous and monotone. chunkIndex gives which chunk an address falls in; chunkPageIndex gives the page’s offset within that chunk.

Chunks themselves live in a two-level sparse array, chunks [1<<pallocChunksL1Bits]*[1<<pallocChunksL2Bits]pallocData. On a 48-bit-address platform pallocChunksL1Bits = 13 (mpagealloc_64bit.go), and L2 is heapAddrBits − logPallocChunkBytes − pallocChunksL1Bits = 48 − 22 − 13 = 13 bits as well, so each L2 leaf block holds 1<<13 pallocData entries — at 128 bytes each (two 512-bit bitmaps), that is a 1 MiB leaf block (mpagealloc.go, lines 80–87, 220–246). The sparse two-level form means the runtime maps L2 blocks lazily as the heap grows into new regions, instead of reserving one monstrous flat array.

The bitmap operations themselves lean on hardware intrinsics: finding a free run within a chunk is a sequence of ctz/clz (count-trailing/leading-zeros) over 64-bit words, and popcnt counts how many pages in a range are scavenged. pallocBits.find(npages, searchIdx) returns the page index of the first run of npages free pages at or after searchIdx (mpallocbits.go).

The Summary Radix Tree — pallocSum

Above the chunk bitmaps sits the summary tree. Each summary is a single uint64, pallocSum, packing three values (mpagealloc.go, lines 1031–1043):

type pallocSum uint64
// packs: start (free pages at the start of the region),
//        max   (longest run of free pages anywhere in the region),
//        end   (free pages at the end of the region)
func packPallocSum(start, max, end uint) pallocSum {
	if max == maxPackedValue {
		return pallocSum(uint64(1 << 63))
	}
	return pallocSum((uint64(start) & (maxPackedValue - 1)) | ...)
}
  • start — how many contiguous free pages there are from the beginning of this region. Needed because a run can straddle the boundary between two sibling regions.
  • end — how many contiguous free pages there are up to the end of this region. Pair the end of one region with the start of the next and you detect a boundary-crossing run.
  • max — the longest run of free pages found anywhere inside the region. If max >= npages, the allocation fits somewhere in this subtree; if not, prune it.

The tree has a fixed number of levels (summaryLevels, architecture-dependent — 5 on 48-bit platforms). Each non-leaf level uses summaryLevelBits = 3 bits, so each node has 8 children: “The value of 3 is chosen such that the block of summaries we need to scan at each level fits in 64 bytes (2^3 summaries * 8 bytes per summary), which is close to the L1 cache line width on many systems. Also, a value of 3 fits 4 tree levels perfectly into the 21-bit pallocBits summary field at the root level” (mpagealloc.go, lines 67–79). On 64-bit platforms summaryLevels = 5 (mpagealloc_64bit.go). The root level (summary[0]) has each entry covering 16 GiB; each descent narrows by a factor of 8 — 2 GiB, 256 MiB, 32 MiB — down to a 4 MiB chunk.

Each level is one flat array: summary [summaryLevels][]pallocSum. The tree is implicit — node i at level l has children [i<<3, i<<3 + 8) at level l+1. No pointers, no dynamic node allocation. The arrays’ backing store is reserved for the whole address space in pageAlloc.init and committed lazily in grow.

Mechanical Walk-through — Allocating a Page Run

pageAlloc.alloc(npages) is the entry point, called by mheap.alloc under mheap_.lock (mpagealloc.go, lines 879–931):

1. The searchAddr fast path

if chunkIndex(p.searchAddr.addr()) >= p.end {
	return 0, 0   // heap exhausted
}
if pallocChunkPages-chunkPageIndex(p.searchAddr.addr()) >= uint(npages) {
	i := chunkIndex(p.searchAddr.addr())
	if max := p.summary[len(p.summary)-1][i].max(); max >= uint(npages) {
		j, searchIdx := p.chunkOf(i).find(npages, chunkPageIndex(p.searchAddr.addr()))
		addr = chunkBase(i) + uintptr(j)*pageSize
		goto Found
	}
}

searchAddr is a hint: “every valid heap address below this is allocated and not worth searching.” If the request might fit in the same chunk searchAddr points into, the allocator checks that chunk’s leaf summary directly and, if max >= npages, scans just that one chunk’s bitmap — skipping the whole tree walk. This is the common case for a heap that is allocating linearly.

2. The radix-tree search — find

If the fast path misses, p.find(npages) walks the tree top-down (mpagealloc.go, lines 654+):

for l := 0; l < len(p.summary); l++ {
	entries := p.summary[l][i : i+entriesPerBlock]   // the 8-ish children
	for j := j0; j < len(entries); j++ {
		sum := entries[j]
		if sum == 0 { size = 0; continue }   // fully-allocated region: skip
		s := sum.start()
		if size+s >= uint(npages) {
			// A boundary-crossing run: end of previous entry + start of this one.
			// ... compute exact base, descend or return ...
		}
		if sum.max() >= uint(npages) {
			// The run fits entirely inside this entry: descend into it.
		}
		size = sum.end()   // carry the trailing free run into the next sibling
	}
}

At each level the allocator iterates over the (up to 8) child summaries looking for one of two things, exactly as the top comment states:

  1. A subtree whose max is large enough — the run fits within one child; descend into it.
  2. Enough boundary-crossing free pages — the end of one child plus the start of the next (plus possibly fully-free children in between) sum to npages; the run straddles siblings, and the exact start address is now known.

A summary of 0 means the region is entirely allocated — skipped instantly. This pruning is what makes the search sub-linear: a single comparison discards a 16 GiB subtree. The walk also maintains firstFree, narrowing the window where the first free page lives, so it can update searchAddr for next time.

3. Mark the bits and update

Found:
	scav = p.allocRange(addr, npages)   // set the npages bits in the bitmap
	if p.searchAddr.lessThan(searchAddr) {
		p.searchAddr = searchAddr        // advance the hint
	}
	return addr, scav

allocRange sets the npages bits in the affected chunk bitmaps, and propagates the change up the summary tree — every ancestor summary whose region changed is recomputed (update). It also counts, via the scavenged bitmap, how many of the allocated pages were previously scavenged — scav — so the caller (mheap) knows how much memory it must re-commit / fault back in.

4. Freeing — pageAlloc.free

free(base, npages) is the inverse (mpagealloc.go, lines 940+): it clears the bits (a single-bit free1 fast path for npages == 1, a ranged clear otherwise), propagates the summaries upward, lowers searchAddr if the freed region is below it, and notifies the scavenge index that this chunk now has free pages available to scavenge.

The Scavenger Hook — Returning Pages to the OS

The page allocator is also where the scavenger plugs in. Free pages still count against the process’s resident set (RSS) until the runtime tells the OS it no longer needs them — that is scavenging (a sysUnused call, see Memory Mapping and OS Interaction). The pageAlloc.scav substructure holds a scavengeIndex — “an efficient index of chunks that have pages available to scavenge” — and counters for background vs. eager release (mpagealloc.go, lines 275–290).

There are two scavenging fronts (mgcscavenge.go):

  • Background scavenger — a goroutine, soft-capped at a small fraction of mutator time, that drives estimated heap RSS down toward a goal derived from GOGC/GOMEMLIMIT.
  • Eager / synchronous scavenger — runs at allocation time when the heap grows or an allocation would breach GOMEMLIMIT. The reasoning: if the heap had to grow, existing fragments were too small, so those fragments are scavenged eagerly to offset the RSS growth.

Critically, “the background scavenger and heap-growth scavenger only release memory in chunks that have not been densely-allocated for at least 1 full GC cycle” — the scavenged bitmap and per-chunk density tracking prevent the runtime from churning pages it is about to re-use. The scav triple in allocRange’s return value closes the loop: re-allocating a scavenged page costs a page fault, and the runtime accounts for that.

Failure Modes and Common Misunderstandings

“The page allocator allocates objects.” No — it allocates pages, in runs. Objects are the size-class layer’s concern (Size Classes and Span Management). The page allocator has no notion of size class; it answers “give me N contiguous 8 KiB pages” and nothing more.

“Free memory means low RSS.” Not necessarily. A page can be free in the bitmap yet still resident (counted in RSS) until the scavenger calls sysUnused on it. The gap between heap-released and heap-idle is exactly this un-scavenged free memory. A program that frees a lot but shows high RSS is waiting on the scavenger — see Memory Mapping and OS Interaction.

“First-fit causes bad fragmentation.” The allocator does address-ordered first-fit, deliberately. Address-ordered first-fit has well-studied good fragmentation behavior — it tends to pack allocations toward low addresses, leaving large contiguous free regions high up, which is why searchAddr works as a monotone hint. It is not a naive first-fit.

“The radix tree wastes gigabytes of RAM.” It wastes virtual address space — the summary arrays are reserved for the whole address space — but only the portions covering the actual heap are committed (backed by physical memory). The top comment is explicit: “a large amount of virtual address space may be reserved by the runtime,” but reserved ≠ resident.

Boundary-crossing runs are easy to forget. A large allocation may span the boundary between two summary entries, two chunks, or even two arenas. The start/end fields of pallocSum exist precisely so the search can stitch a run across a sibling boundary; ignoring them would make the allocator unable to find runs that fit but are not wholly inside one node.

Alternatives and Comparison

  • The old treap allocator (pre-Go 1.14). Before the radix-tree allocator, mheap kept free spans in a treap (a balanced binary search tree keyed by size/address). Allocation was a tree lookup; the problem, per proposal 35112, was scalability — the treap was a single global structure under mheap_.lock, and every span split/coalesce was a tree mutation. The bitmap+radix design replaced it for better cache behavior and to enable finer-grained future locking.
  • Buddy allocators (Linux kernel). The buddy system allocates power-of-two page blocks and coalesces “buddies.” Simple and fast but suffers internal fragmentation (only power-of-two sizes) — Go’s allocator can hand out any page count, with the size-class layer handling sub-page granularity above it.
  • Free-list / boundary-tag allocators. A classic per-size or address-ordered free list of free runs. The radix tree is essentially a summary index over the free space that makes the “find a run of N” query fast without materializing per-run list nodes.

The 1.14 ship date is verified: the Go 1.14 release notes confirm the page-allocator rewrite landed in that cycle, describing it as “more efficient” with “significantly less lock contention at high values of GOMAXPROCS” (go1.14 release notes). The mechanism above is verified directly against the Go master (1.26-era) source.

Production Notes

The page allocator has essentially no user-facing knobs — it is pure runtime internals. Its behavior surfaces indirectly:

  • GODEBUG=gctrace=1 and runtime.MemStats report HeapIdle, HeapReleased, and HeapInuse. HeapIdle − HeapReleased is free-but-resident memory the page allocator holds and the scavenger has not yet released.
  • GOMEMLIMIT (Go 1.19+) makes the eager scavenger more aggressive: when the heap approaches the soft limit, the page allocator’s eager scavenge path returns memory synchronously to keep RSS under the cap — see GOMEMLIMIT and the Soft Memory Limit.
  • debug.FreeOSMemory() forces an immediate, full scavenge — it walks the page allocator’s free chunks and sysUnused-es everything. Useful after a known memory spike, costly because re-using that memory will fault.
  • Large contiguous allocations (huge slices, big maps) stress the page allocator’s ability to find long runs; sustained allocation/free of large objects can fragment the page space, visible as the heap growing despite stable live-set size. Rick Hudson’s ISMM 2018 keynote frames the allocator/collector co-design that the page layer underpins (ismmkeynote).

See Also

Graph View

Backlinks