Virtual memory and the TLB

Deep dive

How it works

In: a virtual address from a load, store or fetch · Out: the physical address, or a page fault · State: page tables in memory and TLB entries per core · Cost: TLB hit about 1 cycle; a page walk order of 20-40 cycles with cached PTEs, hundreds from DRAM.

48-bit VA:  [PML4 9][PDPT 9][PD 9][PT 9][offset 12]
CR3 → PML4 → PDPT ─(1 GiB page)→  PD ─(2 MiB page)→  PT → 4 KiB page

1. TLB lookup: L1 DTLB (order of 64-96 entries, about 1 cycle), then L2 STLB (order of 1.5-3k entries, several cycles extra).
2. Page walk on a miss: up to 4 dependent loads (5 with 57-bit LA57 paging). Page-walk caches keep upper levels. The leaf PTEs are ordinary cached data. Cost is order of 20-40 cycles when the PTEs hit in cache, hundreds when they come from DRAM.
3. Virtualization: nested (two-dimensional) walks need up to 24 memory references for 4-level guest and host tables. Huge pages in both the guest and the host help most there.
4. Page fault on first touch: the kernel allocates and zeroes a page and installs the PTE. Order of 1 µs for 4 KiB, order of 100 µs for zeroing a 2 MiB page.
5. Shootdowns: munmap, mprotect, madvise(MADV_DONTNEED) in a multithreaded process send IPIs so other cores flush stale entries. Order of µs, and it grows with the number of cores.

TLB sizes (data side):

AArch64 granules: 4 KiB (2 MiB and 1 GiB blocks), 16 KiB (32 MiB blocks), 64 KiB (512 MiB blocks). The contiguous bit lets 16 adjacent 4 KiB PTEs share one TLB entry (64 KiB).

Decision table

Code

THP and hugetlbfs allocation on Linux, and a measurement of random reads over 1 GiB with 4 KiB pages vs THP. Type-checked for x86_64-linux.

// Linux only. Cargo.toml: libc = "0.2"
use std::{io, ptr, time::Instant};

const HUGE: usize = 2 << 20; // 2 MiB

/// Anonymous memory backed by 2 MiB pages if possible.
/// explicit = true: hugetlbfs pool (needs `sysctl vm.nr_hugepages=N`), fails if the pool is empty.
/// explicit = false: transparent huge pages via madvise, silently falls back to 4 KiB pages.
fn alloc_huge(len: usize, explicit: bool) -> io::Result<*mut u8> {
    let len = len.next_multiple_of(HUGE);
    let prot = libc::PROT_READ | libc::PROT_WRITE;
    let flags = libc::MAP_PRIVATE | libc::MAP_ANONYMOUS;
    unsafe {
        if explicit {
            let p = libc::mmap(ptr::null_mut(), len, prot, flags | libc::MAP_HUGETLB | libc::MAP_HUGE_2MB, -1, 0);
            return if p == libc::MAP_FAILED { Err(io::Error::last_os_error()) } else { Ok(p.cast()) };
        }
        // THP needs 2 MiB-aligned virtual ranges: over-allocate, then trim both ends.
        let raw = libc::mmap(ptr::null_mut(), len + HUGE, prot, flags, -1, 0);
        if raw == libc::MAP_FAILED { return Err(io::Error::last_os_error()); }
        let start = (raw as usize).next_multiple_of(HUGE);
        let head = start - raw as usize;
        if head > 0 { libc::munmap(raw, head); }
        let tail = HUGE - head;
        if tail > 0 { libc::munmap((start + len) as *mut _, tail); }
        if libc::madvise(start as *mut _, len, libc::MADV_HUGEPAGE) != 0 {
            return Err(io::Error::last_os_error()); // e.g. THP compiled out
        }
        Ok(start as *mut u8)
    }
}

/// 4 KiB pages only: tell the kernel never to use THP here.
fn alloc_small(len: usize) -> io::Result<*mut u8> {
    unsafe {
        let p = libc::mmap(ptr::null_mut(), len, libc::PROT_READ | libc::PROT_WRITE,
                           libc::MAP_PRIVATE | libc::MAP_ANONYMOUS, -1, 0);
        if p == libc::MAP_FAILED { return Err(io::Error::last_os_error()); }
        libc::madvise(p, len, libc::MADV_NOHUGEPAGE);
        Ok(p.cast())
    }
}

/// Bytes of this process backed by THP, from the kernel's own accounting.
fn anon_huge_kib() -> u64 {
    std::fs::read_to_string("/proc/self/smaps_rollup").unwrap_or_default().lines()
        .find(|l| l.starts_with("AnonHugePages:"))
        .and_then(|l| l.split_whitespace().nth(1)?.parse().ok()).unwrap_or(0)
}

/// Independent random 8-byte reads: each one is a likely cache miss and, with 4 KiB
/// pages over 1 GiB, a likely TLB miss too.
fn random_reads_ns(p: *mut u8, len: usize, n: usize) -> f64 {
    let words = unsafe { std::slice::from_raw_parts_mut(p as *mut u64, len / 8) };
    for (i, w) in words.iter_mut().enumerate().step_by(512) { *w = i as u64; } // fault every 4 KiB
    let (mut s, mut acc) = (0x9E37_79B9_7F4A_7C15u64, 0u64);
    let t = Instant::now();
    for _ in 0..n {
        s ^= s << 13; s ^= s >> 7; s ^= s << 17;
        acc = acc.wrapping_add(words[(s % words.len() as u64) as usize]);
    }
    std::hint::black_box(acc);
    t.elapsed().as_nanos() as f64 / n as f64
}

fn main() -> io::Result<()> {
    let len = 1 << 30;
    let small = alloc_small(len)?;
    println!("4 KiB pages: {:.1} ns/read", random_reads_ns(small, len, 50_000_000));
    let huge = alloc_huge(len, false)?;
    println!("THP:         {:.1} ns/read", random_reads_ns(huge, len, 50_000_000));
    println!("AnonHugePages: {} MiB", anon_huge_kib() / 1024);
    Ok(())
}

Complexity and constants

• Reach = entries × page size. Translation is free inside the reach. Outside it, each access risks a walk.
• 1 GiB of 4 KiB pages = 262 144 PTEs = 2 MiB of leaf page tables. Those compete for cache too.
• Expected speedup for random access over GiB-sized data from 2 MiB pages: order of 10-30 %, more under virtualization. Measure: perf stat -e dTLB-load-misses,dTLB-loads (event names vary by CPU).

Efficiency

• Cost: a TLB hit costs about 1 cycle (L1) plus several cycles for the second level. A miss starts a walk of up to 4 dependent loads: order of 20-40 cycles when PTEs are cached, hundreds from DRAM. A 4 KiB first-touch fault costs order of 1 µs, zeroing a 2 MiB page order of 100 µs. Bound: latency of dependent walks, on top of the cache miss.
• Levers:
  • 2 MiB pages — Skylake reach 6 MiB → 3 GiB; random access over GiB-sized data order of 10-30 % faster, more under virtualization — large random-access tables
  • hugetlbfs or 1 GiB pages reserved at boot — guaranteed, no compaction stalls — fixed-size tables (DB, DPDK, JVM)
  • avoid munmap and mprotect in hot multithreaded code — no IPI shootdowns — latency-sensitive services
• Naive → standard → state of the art:
• naive: 4 KiB pages, random access over GiB · cache miss plus page walk per access
• standard: THP in madvise mode on the big region · order of 10-30 % faster
• state of the art: reserved 1 GiB pages, or a huge-page-aware allocator (TCMalloc) · reach of terabytes

Implementation notes

• THP modes: /sys/kernel/mm/transparent_hugepage/enabled = always | madvise | never, plus .../defrag. The defaults depend on the distro. khugepaged collapses 4 KiB pages into huge pages later, in the background.
• Check what you got: AnonHugePages in /proc/self/smaps_rollup or /proc/meminfo. For hugetlbfs, check HugePages_Total/Free in /proc/meminfo.
• THP only applies to 2 MiB-aligned, 2 MiB-sized portions of a VMA. An unaligned 3 MiB region may get none.
• File-backed THP is limited (tmpfs with huge=, filesystems with large-folio support on recent kernels). Anonymous memory is the reliable case.
• Page size at runtime: sysconf(_SC_PAGESIZE). Never hard-code 4096: Apple Silicon (16 KiB) and some ARM Linux kernels (16/64 KiB) differ.
• mlock/MAP_LOCKED keeps pages resident (no major faults) but does not make them huge.
• Allocators: jemalloc, mimalloc and TCMalloc (Temeraire) can back heaps with huge pages. Rust's default system allocator does what glibc malloc does.

Pitfalls

• Microbenchmarks that pre-touch memory once and then measure, hiding fault and zeroing cost that production pays on every fresh allocation.
• enabled=always causing RSS growth: a sparsely touched 2 MiB region costs the whole 2 MiB. Redis warns at startup when THP is enabled for this reason, plus fork copy-on-write amplification.
• Assuming MAP_HUGETLB works without reserving pages: it returns ENOMEM.
• Frequent mmap/munmap of buffers in a threaded server: each unmap is a TLB shootdown. Reuse buffers instead (buffer pools).
• Huge pages and NUMA: a 1 GiB page lives on one node. Interleave or bind on purpose.

Variants and alternatives

In production

PostgreSQL huge_pages = try, the JVM -XX:+UseLargePages / -XX:+UseTransparentHugePages, DPDK (hugetlbfs required), Oracle and SAP HANA, TCMalloc huge-page-aware allocation across Google's fleet. Stockfish allocates its transposition table with madvise(MADV_HUGEPAGE) on Linux.

Implementations

Sources

• Intel, Intel 64 and IA-32 Architectures Software Developer's Manual, Vol. 3A, ch. 4 (Paging).
• Linux kernel documentation, Transparent Hugepage Support (admin-guide/mm/transhuge) and HugeTLB Pages (admin-guide/mm/hugetlbpage). THP · HugeTLB
• Abhishek Bhattacharjee, Daniel Lustig, Architectural and Operating System Support for Virtual Memory, Synthesis Lectures on Computer Architecture, 2017.
• Arkaprava Basu et al., Efficient Virtual Memory for Big Memory Servers, ISCA, 2013. paper
• A. H. Hunter et al., Beyond malloc efficiency to fleet efficiency: a hugepage-aware memory allocator, OSDI, 2021. paper · code