Virtual Memory: Understanding Page Tables, Page Faults, and TLB from a Single Memory Access Instruction

A program successfully maps a large chunk of memory, yet RSS does not grow synchronously; a page fault occurs on the first write. Following a single value = *p memory access instruction allows us to separate valid address, page table translation, and actual content into three distinct layers.

Below, we manually calculate addresses using x86-64 with 4 KiB base pages, then follow a single page of data through first use, fork, and unmapping. Page sizes and permission encodings for other architectures may differ.

1. Why a load instruction sometimes doesn't enter the kernel, and sometimes causes a page fault

Assume the program executes value = *p. The CPU receives the virtual address and the read operation; the MMU needs to verify the mapping and access permissions. Typically, it first utilizes the translation cached in the TLB; if hit and permissions are satisfied, there is no need to read the entire page table from scratch for this access. If the TLB does not have a suitable entry, the hardware attempts a page walk; the page table cache and the regular CPU cache may further accelerate this process.

If the walk yields a valid mapping, a TLB miss can be resolved entirely by hardware. If the mapping is missing or permissions do not match, the CPU generates an exception, and the kernel examines the address range and access semantics on the software side: this could be a legitimate first allocation, swap-in, copy-on-write, or the program accessing an address it does not own. After successful handling, the original instruction is usually retried; user accesses that cannot be satisfied result in SIGSEGV, SIGBUS, etc., depending on the situation.

Placing "page fault" back into a specific scenario: File content has already been read into the page cache by another process. The current process may still page fault on first access because the corresponding PTE has not yet been installed. This time, it can reuse existing content without reading from disk again.

Thus, having a VMA, having a PTE, and data being resident cannot substitute for each other.

2. Why page tables are multi-level: Calculate the space cost first

A 48-bit address with 4 KiB pages means 2^48 / 2^12 = 2^36 virtual pages. If each page reserves a fixed 8-byte entry, a single linear page table would require 2^39 bytes, which is 512 GiB. Most processes use only a tiny fraction of this space; pre-allocating page tables for all holes is very wasteful.

Multi-level page tables allow an empty upper-level entry to represent an entire unmapped range, allocating lower-level table pages only for branches that are actually needed. For x86-64's 4 KiB table pages, 512 entries of 8 bytes exactly fill one page, so each level uses 9 bits for indexing. Four levels of indexing total 36 bits, plus 12 bits for page offset equals 48 bits.

"Folded" means Linux generic code can still be written against the 5-level interface; the layer not needed for the target configuration does not correspond to an independent hardware table. The PGD in 4-level mode corresponds to hardware PML4; in 5-level mode, PGD corresponds to PML5. Names cannot be mechanically bound forever to the same hardware layer. See Page Table Levels.

Manually calculating how an address locates a physical page

Construct an address such that the four-level indices are sequentially 1, 2, 3, 4, and the page offset is 0x567. CR3 provides the physical base address of the top-level table and related control information. The hardware reads the 1st entry of the top level to get the base address of the next table; then takes the 2nd, 3rd, and 4th entries. The address of each step's entry is "base address of that level + index × 8", not adding the four indices and multiplying by the page size.

Assume the final leaf entry points to physical page base address 0x12345000; the target physical address is 0x12345567. The page offset comes from the lower 12 bits of the virtual address; the lower bits of the PTE are flags and do not store this offset.

indices = [1, 2, 3, 4]
shifts = [39, 30, 21, 12]
va = sum(index << shift for index, shift in zip(indices, shifts)) | 0x567
assert [(va >> shift) & 0x1ff for shift in shifts] == indices
physical_base = 0x12345000  # Hypothetical result from traversal, not reading actual page table
physical = physical_base | (va & 0xfff)
assert physical == 0x12345567
assert (1 << 48) // 4096 * 8 == 512 * (1 << 30)
print(f"virtual={va:#x}, physical={physical:#x}")

Below, we split the address into indices and offset, directly change the leaf size, and observe where the traversal terminates. The diagram selects 0x40000000 as the aligned data base address; the calculation rules are the same as the manual calculation above.

$$\mathrm{PA}=leaf\_base+(\mathrm{VA}\mathrm{mod}{2}^b)$$

b is the offset bit width covered by the leaf: in this diagram, we take 12, 21, and 30 respectively.

Address Width: Separate Capability, Enabled State, and Actual Allocation

x86-64 addresses must also satisfy the canonical rules of the current mode: unused high bits are extended according to the effective highest address bit. 5-level paging brings a larger virtual space, but does not require processes to immediately allocate more physical memory. The CPU exposing LA57 only indicates capability; it also requires kernel configuration and runtime mode. Linux, also considering application compatibility, usually does not default to placing ordinary mmap outside the 47-bit window. See 5-Level Paging Description.

3. Permissions exist in the mapping path, not just as a switch in the last entry

First, distinguish several types of information using common x86 leaf entries:

Huge page leaves and regular PTEs interpret some bits differently, and physical address bit widths must also be handled according to CPU capabilities.

For example, if the upper level denies user access, reading cannot succeed even if the leaf entry's U/S allows it. Similarly, if a PTE's Dirty=0, it is not sufficient to prove that anonymous content has a valid backing copy: hardware access clues and data recovery sources are different issues.

The VMA permissions maintained by the kernel describe "how the program is allowed to use this range"; the hardware page table permissions describe "whether this current access can be completed directly." The two are intentionally not always identical; this is precisely the foundation for COW to work in the next section. To locate specific bit definitions, target the kernel's arch/x86/include/asm/pgtable_types.h; do not treat simplified teaching diagrams as directly portable bitmasks.

4. Following a page of data through demand paging and COW

When a program maps a private anonymous read-write space, the kernel first registers the address range and semantics. It is usually not necessary to immediately allocate data pages for every address. The first read might use optimizations like sharing the zero page; the first actual write requires a page capable of saving this process's data and ensures that newly allocated user data content does not leak information from previous users.

Then fork is called. Parent and child need to see the same private memory content as at fork time, but if the child process quickly execs, copying all data pages immediately would waste a lot of work. The typical COW approach is to let both sides temporarily share the physical page, set the relevant hardware mappings to write-protected, while retaining the writable semantics of both VMA. True writes force the kernel to determine if separation is necessary.

Reading the diagram: VMA allows write, why still write-protect exception?

When the child process writes, the kernel finds "VMA allows write, current shared mapping prohibits direct write," so it establishes a writable page satisfying private semantics. If copying is indeed needed, the child's new page receives the original content, then executes the original modification; the parent continues mapping the old page. If the old page already satisfies exclusive conditions, it might only restore write permissions. Specific paths are also affected by huge pages, pinned references, etc.; you cannot deduce how many memcpys occurred just from seeing COW semantics from the user perspective.

File MAP_PRIVATE mappings can also produce private COW pages: the modified parts are not written back to the original file. MAP_SHARED expresses shared modification semantics; file pages may enter the writeback path. Both can have page faults; the number of page faults itself does not tell you who the data ultimately belongs to.

Below, we keep two mappings for the same page, attempting writes in "the other party is still present" and "the other party has unmapped" scenarios. Compare complete content and copy counts, not just whether the arrow color changed.

Experiment: Observing isolation results, not guessing copy counts

Below, we simultaneously observe first-write and post-fork visibility, using only 64 base pages:

#define _GNU_SOURCE
#include <assert.h>
#include <stdio.h>
#include <sys/mman.h>
#include <sys/resource.h>
#include <sys/wait.h>
#include <unistd.h>

int main(void) {
    long page = sysconf(_SC_PAGESIZE);
    assert(page > 0);
    size_t length = 64 * (size_t)page;
    unsigned char *memory = mmap(NULL, length, PROT_READ | PROT_WRITE,
                                MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    assert(memory != MAP_FAILED);
    assert(madvise(memory, length, MADV_NOHUGEPAGE) == 0);
    struct rusage before, after;
    assert(getrusage(RUSAGE_SELF, &before) == 0);
    volatile unsigned char *data = memory;
    for (size_t i = 0; i < length; i += (size_t)page)
        data[i] = 7;
    assert(getrusage(RUSAGE_SELF, &after) == 0);
    printf("First sequential page write minor faults diff: %ld\n",
           after.ru_minflt - before.ru_minflt);
    fflush(stdout);
    pid_t child = fork();
    assert(child >= 0);
    if (child == 0) {
        assert(data[0] == 7);
        data[0] = 9;
        assert(data[0] == 9);
        _exit(0);
    }
    int status;
    assert(waitpid(child, &status, 0) == child);
    assert(WIFEXITED(status) && WEXITSTATUS(status) == 0);
    assert(data[0] == 7);
    assert(munmap(memory, length) == 0);
    puts("Child process private modification did not change parent process content: Passed");
}

Compile with cc -std=c11 -Wall -Wextra -Werror vm-demo.c -o vm-demo, without -DNDEBUG. The minor fault difference is for observation only; do not assert it must equal 64; measurements may also include other intra-process activities. Minor faults usually do not require backend reads for this handling, but this does not mean the overhead is negligible. The experiment does not read PFNs, so it verifies user-visible isolation, not direct evidence of physical page sharing.

5. Why TLB consistency is part of memory safety

Assume CPU 0 executes munmap, clearing the PTE for address A; CPU 1 is running another thread in the same address space, and its TLB still caches the translation from A to physical page P. Ordinary data cache coherence can propagate modifications to page table memory, but it will not automatically cause each TLB entry to re-query the page table. If P is allocated to another object at this time, CPU 1's old translation might continue to read/write the new object's data.

Therefore, before an old physical page is handed to someone else again, dangerous old translations must be invalidated. Revoking mappings, tightening permissions, and page migration all require coordinating translation maintenance with page lifespan.

The traditional x86 path often uses IPI to coordinate relevant CPUs, but indiscriminate broadcasting is not required. Address space usage records, batch invalidation, deferred processing, and hardware capabilities can reduce workload; the specific function chain varies by implementation, but security boundaries remain unchanged. See TLB Invalidation Interface.

PCID/ASID attaches address space tags to cached translations, allowing results from different address spaces to potentially remain in the TLB simultaneously. It reduces unnecessary clearing, but cannot make already-expired mappings permanently valid; tag reuse and page table updates still require handling invalidation. The overhead of frequent mprotect/munmap also varies with the number of active CPUs for the address space and batch size; it should not be estimated solely by how many PTEs were modified.

6. Where do the benefits of huge pages come from, and who pays the cost?

First, calculate the number of leaf entries required to fully map 1 GiB of data:

One huge page translation also covers a larger virtual range, potentially reducing TLB pressure for certain working sets. Benefits come from changes in translation coverage and page table workload; the actual magnitude still depends on the CPU and access patterns.

However, TLB capacity and organization for different page sizes may not be identical; you cannot simply multiply by a fixed number of entries to assume a CPU's actual performance. Huge pages also require corresponding contiguous physical ranges; allocation, zeroing, migration, and compaction may concentrate costs into a single page fault. Ranges using only a small number of bytes may cause internal waste; partial unmapping or permission changes may also require splitting.

THP is not simply "changing a flag on 512 originally contiguous pages": background merging can allocate new huge pages and move content; the page fault path can also directly attempt huge pages. Whether PTE mapping for mTHP gains extra hardware translation benefits depends on the architecture.

Actual sizes and enablement policies should be checked via interfaces like hugepages-*kB/enabled; do not judge all paths solely by the top-level switch; explicit MADV_COLLAPSE has its own independent contract. See THP Management Documentation and HugeTLB.

7. Why PTI switches page tables

Traditional shared layouts allow user and kernel mappings to reside in the same address translation structure, with normal permission checks preventing user access to kernel pages. However, Meltdown-class issues show that accesses denied by architecture permissions on specific CPUs may still leave observable side-channel traces in transient execution. The idea of PTI is to shrink the set of kernel mappings visible in the user-space page table, so that most sensitive addresses are not in that mapping at all.

Switch to the full view when entering the kernel, switch back to the reduced view when returning to user space; the minimal region required for entry must still be accessible. The two views can share the lower-level page tables for the user part; this does not mean every process's entire user data and every level of page table are completely copied twice. Overhead includes page table switching and related translation maintenance; PCID can mitigate some costs; it cannot be fixed as "exactly two TLB misses per syscall." See x86 PTI Design.

8. Separating four quantities when reading observation results

When reading monitoring data, keep four quantities separate:

Large VmSize with small RSS can come from untouched mappings. Whether huge pages are actually used should be combined with fields like smaps; do not look only at configuration switches.

/proc/<pid>/pagemap is a binary interface; PFNs may be hidden due to permission restrictions, and bit interpretations should be read according to documentation versions; do not directly cat into text. The next article VMA and Maple Tree continues to answer: how the kernel knows a page fault address is valid, and why modifying a range of permissions might split out more VMAs.