Pages, faults and allocation

2.6 Sharing memory: pages, faults and the TLB

The third promise is memory: every process gets an address space of its own, as large as it likes, and the operating system finds the physical frames to back it. This section is how the kernel keeps that promise with less physical memory than has been promised, why that makes the first touch of every page a trip into the kernel, and what else follows from the frames being shared.

The address space and the TLB

Each process has its own virtual address space, mapped onto physical 4 KB frames by page tables the kernel writes and the core walks, with recent translations cached in the per-core TLB. A load that misses the TLB walks the table: four dependent loads, one per level (five on the largest machines). The upper levels are almost always in cache and the core keeps a small cache of them, so a walk costs 20–40 cycles when the leaf entry is in L1 or L2 and a few hundred when it is in L3 or DRAM. The TLB is small. On a typical current server core the first-level data TLB holds 64 translations for 4 KB pages, and the second level, shared with instruction translations, holds 1,536–2,048.

Six to eight megabytes of reach with 4 KB pages, against an L3 of 60 MB and an order table of hundreds of megabytes. A random access into a 40 MB table misses the TLB on about five accesses in six, and each miss adds a page walk before the cache miss can even begin. The page table can also map a whole 2 MB or 1 GB block with a single entry, provided the block is physically contiguous and aligned; with 2 MB pages the same table is 20 translations and never misses. Where such blocks come from is below.

Backing on first touch

The kernel’s central design choice about memory is laziness. mmap, and therefore Vec::with_capacity, gives you addresses, not frames. Processes ask for far more than they touch (a 2 MB stack per thread, a 1 GB arena that may fill by evening), and physical memory is shared by everyone, so the kernel attaches a frame to a page only when the page is first written. The first write traps, because the page table says the page is not present; the handler finds a free frame, zeroes it so that the last owner’s data does not leak, writes the page-table entry and returns, and the store retries. That is a minor page fault, the third of the three ways into the kernel, and it costs 0.5–1 µs with the zeroing. A 1 GB table is 262,144 of them, 150–250 ms the first time through. On a two-socket box the same event also decides which socket’s DRAM the page lives in: the frame comes from the node of the core that touched it.

Faults also serve file mappings, copy-on-write after fork, and swapped-out pages. A major fault requires I/O; a copy-on-write fault or a file-backed fault satisfied from the page cache is normally minor. Disk-backed faults can cost 100 µs on NVMe or milliseconds on a disk. The fault counters distinguish them by whether I/O was needed.

Taking frames back

Because frames are shared, the kernel can take them back. When memory runs low, kswapd reclaims: it drops clean page-cache pages, pages of your own executable included, since they can be read again from disk, and writes anonymous pages out to swap. A reclaimed page may need a major fault if its contents must be read back; if the data remains cached, the fault can be minor. Turning swap off removes the second case and not the first. The kernel offers an opt-out, mlock, which pins a range’s frames so that reclaim passes them by; the price is that locked memory is resident whether or not it is used, and the limit on it (RLIMIT_MEMLOCK) is small by default.

Huge pages and compaction

A 2 MB page needs 2 MB of physically contiguous free memory, and fragmentation can make such blocks scarce even when total free memory is ample. The kernel has two answers. Transparent huge pages (THP) are the automatic one: when a process touches a 2 MB-aligned range the kernel backs it with a huge page if it can find one, and a thread, khugepaged, collapses runs of 4 KB pages into huge ones in the background. When no contiguous block exists the kernel can make one by compaction, moving in-use frames together to open a hole, which kcompactd does in the background and which a page fault that wants a huge page may do itself, synchronously, for milliseconds. Explicit huge pages, hugetlbfs, are the reserved answer: a pool set aside at boot or soon after, while contiguous memory is still plentiful, mapped with MAP_HUGETLB, which reclaim and compaction leave alone and which no other process can use.

Placement on two sockets

On a two-socket box the kernel also tries to keep pages near the cores that use them, and it cannot see which core uses a page without asking. Automatic NUMA balancing asks by periodically unmapping a sample of a process’s pages, so that the next touch faults and reports which node touched it, and migrating pages toward their users. Each sample is a page fault the kernel scheduled on your thread, 0.5–1 µs, for a placement decision that a thread which touched its own memory from its own core already made.

Shootdowns

Because every core caches translations privately, changing a mapping is not a local act. When a page is unmapped or its permissions change, every core that might hold the old translation must drop it, and the only way to make a core do that is to interrupt it: the kernel sends a TLB-shootdown interrupt to each core currently running a thread of that process, each one flushes and acknowledges, and the unmapping core waits for all of them. A munmap on one thread therefore stalls every other thread of the process, a few microseconds each, whether or not they ever touched the pages. A program rarely calls it directly; its allocator calls munmap.

Worked example: the first burst of the day

A 2 GB order table is created with Vec::with_capacity at startup, on a thread that then does nothing with it, and is first written during the opening burst, from the hot thread on core 3. The burst pays 524,288 minor faults at 0.5–1 µs, 0.25–0.5 s in total, spread as a 0.5–1 µs stall on every message that touches a page nobody touched before, which during an opening burst is most of them. If the table was zeroed by the startup thread on the other socket instead, there are no faults, and every one of those accesses is a remote DRAM access for the rest of the day. If the box is short of memory the table’s cold pages are swapped out by lunch and come back as 100 µs major faults. And if the table’s pages are 4 KB, a random access into it misses the TLB nearly every time, which is a page walk before the DRAM access the ladder already charged for.

Each of those is the memory manager keeping its promise in the way that suits a thousand ordinary processes: frames on demand, from wherever the toucher happens to be, taken back when someone else needs them, in the page size that costs the least to manage. None of it is visible in the program’s code, and all of it is visible in the first burst’s histogram.

Seeing it

perf stat -e page-faults,minor-faults,major-faults,dTLB-load-misses,dTLB-store-misses ./binary counts the faults and the TLB misses, and after warm-up a correctly prefaulted, resident working set should add no new page faults. TLB misses can continue whenever its translations do not fit. grep -E 'AnonHugePages|HugePages_' /proc/meminfo and /proc/<pid>/smaps_rollup (AnonHugePages, Locked) show whether huge pages and locking took effect, which they silently do not when the kernel’s THP mode or the lock limit forbids them. compact_stall and numa_hint_faults in /proc/vmstat count compaction inside faults and balancing faults, and both count events the loop never asked for.

2.7 The allocator in between

The kernel hands out memory in pages, through a system call, and a program wants it in 24-byte pieces, a million times a second. Nothing in the kernel bridges that gap; a library in user space does. The allocator is the first example in this book of the pattern the whole chapter points at, a user-space cache in front of a kernel service, and it is worth seeing how it works, where it stops working, and what it does to other cores when it hands memory back.

A cache in front of the kernel

Vec::with_capacity, Vec::push on a full vector, Box::new, String::from, format! and collect all call the global allocator (Vec::new itself does not; it allocates on the first push), and Rust’s default on Linux is glibc’s malloc. The allocator takes large ranges from the kernel, with brk to grow the heap or mmap for a fresh range, and hands out small pieces of them from per-thread arenas, regions it already owns. The fast path is fast: a small request is served from an arena in 20–50 ns without the kernel, a freed piece goes back to the arena’s free lists, and a well-behaved allocator in a steady state rarely leaves user mode. In that steady state the allocator has turned a microsecond-scale kernel service into a 50 ns one, which is the point of a cache.

Where the cache misses

The kernel enters at the edges. An arena that runs out asks for more, and new pages may fault on first use. glibc can serve a large request with its own mmap, and freeing it can then call munmap; a request may instead reuse an arena. The initial mmap threshold is commonly 128 KiB and adapts with allocation history, subject to configuration. Collection growth can also copy its old contents. Rust does not guarantee a Vec growth factor. The glibc allocator controls explain why size alone cannot predict every syscall; trace the actual run.

What returning memory costs

Memory the allocator returns to the kernel costs twice. It comes back unfaulted, so the next use pays the first-touch faults again. And munmap, brk shrinking and madvise(MADV_DONTNEED) remove mappings, which is the TLB shootdown of the previous section: every other core running a thread of this process is interrupted, flushes its translations and resumes. A thread that frees a large buffer on core 1 interrupts the thread on core 3, which allocated nothing. That is the TLB row in /proc/interrupts, and it is the reason an allocator’s behaviour matters to threads that never call it. Other allocators (jemalloc, mimalloc) make different choices about when to return memory, and all of them return it eventually.

A thread that calls the allocator inside its loop therefore pays the allocator’s edges at the allocator’s choice of moment, and a process that frees large buffers on any thread pays shootdowns on every thread. Neither cost appears in the code that pays it, which is what makes the allocator worth counting.

Seeing it

A counting allocator wraps System through GlobalAlloc, increments a counter in alloc, alloc_zeroed and realloc, and forwards each call without logging or allocating inside the wrapper. Count deallocations separately if frees matter too.

Read ALLOCS after warm-up, run a million iterations, read it again, and assert the two are equal. strace -e trace=mmap,munmap,brk,mremap shows every time the allocator crossed the line after startup, and the TLB row for the hot core shows what that cost the others. Lab 2.2 uses the counter; the real system’s test suite should too, because it turns “we think the hot path is allocation-free” into a number.