Walking a Multi-Level Page Table

The page number in a virtual address is 36 bits wide on a conventional 48-bit x86-64 configuration. Storing those bits in a flat table alongside a frame number would cost more memory than most machines have. The hierarchy that replaces the flat table is a radix tree with a fan-out chosen so that one node fits in one page, and the walk down that tree is the operation the processor performs on every instruction fetch and every data access that misses the translation cache.

Fan-Out Determined by the Page Size

Each table node is one page. At 4096 bytes and eight bytes per entry, a node holds 512 entries, which is exactly 2^9. Nine bits of the page number index a node, so the 36-bit page number divides into four chunks of nine, and the tree has four levels. A 45-bit page number, as with a 57-bit virtual address space, needs five levels. This is why the number of levels is not a design preference but an arithmetic consequence of the page size and the entry size.

#include <stdint.h>

#define ENTRIES_PER_TABLE 512
#define PRESENT           (1ull << 0)
#define ENTRY_ADDR_MASK   0x000ffffffffff000ull

static inline unsigned index_of(uintptr_t page_number, int level)
{
    /* level 0 is the top-most table, closest to the root */
    return (unsigned)((page_number >> (9 * (3 - level))) & 511);
}

static inline uintptr_t table_entry(uintptr_t table, unsigned index)
{
    return ((const uint64_t *)table)[index];
}

The shift count is computed from the level rather than hard-coded per level so the same indexing code serves machines with different virtual widths, which is what portable kernels do.

The Four Steps

A walk begins at the root, whose physical address the processor reads from a register the kernel loads on context switch. On x86-64 that register is CR3; on ARMv8 it is TTBR0_EL1 for the low half of the address space and TTBR1_EL1 for the high half. The first nine bits of the page number select an entry in the root table. That entry, if present, contains the physical address of the next-level table, masked so that the low bits can carry flags. The next nine bits select an entry in that table, and so on through the third level, whose entry points at a fourth-level table. The fourth-level entry contains the frame number, which is concatenated with the twelve offset bits to form the physical address.

Four dependent loads. Each load cannot begin until the previous one has produced its address, so the walk is a chain of memory latencies rather than a set of parallel accesses. In a machine whose L1 cache answers in a few cycles and whose DRAM answers in hundreds, a walk that hits cache at every level costs tens of cycles and one that misses at every level costs on the order of a thousand. The translation cache described in the TLB and what happens on a miss exists because paying that chain on every access would leave the processor stalled on translation far more often than on data.

The tables themselves compete for cache with the data the program actually wants. A process with a large working set populates many tables, and those tables occupy cache lines that would otherwise hold user data. This is a second-order effect that becomes first-order in workloads with sparse access patterns across a wide address range, where each new page touched drags in a fresh set of table entries.

Sparse Allocation and the Cost of a Cold Mapping

The hierarchy exists to make sparse address spaces cheap, and it does. A process that has touched only a few megabytes across a 128 TiB address space has allocated only the tables along the paths to those megabytes. Each new region of 2 MiB requires a new fourth-level table, one 4096-byte allocation; each new region of 1 GiB requires a new third-level table. The root and the second level are typically allocated once and shared across the whole address space.

The cost appears at first touch. Mapping a page in a previously untouched 2 MiB region requires allocating a table page and initializing 512 entries to not-present, then filling one entry. That is a page-sized zeroing operation for a single 4 KiB mapping. Mapping 512 pages in the same region amortizes the table allocation across all of them, which is why allocators and loaders place adjacent objects together rather than scattering them.

Tearing down is symmetric and can be more expensive. Unmapping a range requires walking the tree to find the leaves, and when a table becomes entirely empty the kernel may free it and clear the parent entry. The decision to free eagerly or lazily is a trade: eager freeing returns memory promptly but costs a scan of 512 entries at each level, while lazy freeing leaves empty tables resident. Kernels generally free a table when the last entry is cleared, because an empty table still occupies a cache line and still has to be skipped on every walk that reaches that subtree.

Flags Along the Path

Every entry in the walk carries flags, and the effective permission of a translation is the conjunction of the flags at each level. An entry that is not present terminates the walk and raises a fault; the faulting level determines what the handler can infer. The present bit at the top level with a not-present bit at the leaf means the region exists but the page is not mapped, which is the ordinary case for demand paging. A not-present bit higher up means the entire subtree is absent, which lets the kernel distinguish a genuine hole in the address space from an unmapped page inside a mapped region.

Access and dirty bits are usually maintained at the leaf, but the architecture permits them at intermediate levels as an optimization: a higher-level bit can be set instead of walking to the leaf to update it, and clearing the higher-level bit forces subsequent walks to descend and set the lower bits. This reduces the number of page-table writes for a workload that repeatedly dirties pages in the same 2 MiB region. The cost is that the kernel must understand the aggregation rule when it wants to know whether a specific page was accessed, and must walk down rather than trust a single bit.

The user/supervisor bit and the no-execute bit are also inherited. A leaf marked executable under a non-executable parent cannot be executed, which is how the kernel enforces a non-executable stack region with a single high-level entry rather than touching every leaf. The mechanism is not free of subtlety: changing a high-level flag requires flushing translations that were cached under the old value, and the invalidation rules are architecture-specific.

Where the Root Comes From

The walk begins at a physical address the kernel places in a register. On x86-64 the register is loaded with the physical address of the top-level table, and on processors that implement address-space tagging the low bits of the loaded value also carry an identifier for the address space. ARMv8 splits the job between two base registers, one for each half of the address space, which is how a kernel keeps itself mapped in the high half while a process owns the low half without duplicating the whole tree.

Changing the register is how a context switch changes address spaces, and the change is not free. Loading a new root discards the entries cached for the old one unless tagging lets translations from several address spaces coexist, in which case the processor simply stops matching them. Without tagging, every switch empties the translation cache and the incoming context pays a walk for each page it touches until the cache refills.

The root also constrains the allocator. A top-level table must be physically contiguous and aligned so that its address fits the format the register accepts, and it must stay alive as long as any processor might be walking it. Freeing a table page on one processor while another is midway through a walk over the same page produces a use-after-free below the level the kernel can observe, which is why table pages are released through a deferral mechanism rather than returned to the allocator immediately.

When the Walk Is Short-Circuited

Large pages collapse levels. A 2 MiB page is described by an entry at the third level, which points directly at a frame and sets a flag indicating that the entry is a leaf rather than a table pointer. The walk terminates one level early, the fourth-level table for that region is never allocated, and one entry covers 512 ordinary pages. A 1 GiB page terminates at the second level and covers 512 of the 2 MiB pages.

This is the same trade as the address split itself: fewer levels means fewer dependent loads and fewer table pages, but the mapped unit must be physically contiguous and the waste inside a partially used large page grows with its size. A 2 MiB page that holds one live 4 KiB object wastes almost the whole 2 MiB of physical memory, which is why kernels do not use large pages for arbitrary allocations and why transparent huge page schemes have policies about when to collapse. The details of when collapse is worthwhile belong to large pages and TLB coverage.

The walk is also short-circuited before it starts, by the translation cache. A hit means no table access at all, and the cache’s reach is measured in the number of distinct pages touched, not the number of accesses. That distinction is why a program that loops over a small array forever performs almost no walks while a program that streams through a large one performs one per page, and it is the reason page-table walks are studied as a property of the working set rather than of the instruction count.