Page table

A page table is the data structure describing an address space's mappings from virtual page numbers to page frames, together with access and status information. A page table entry can describe a resident memory page and its permissions. Nonresident or unmapped memory pages require a representation that lets the operating system distinguish them; a hardware not-present flag alone need not make that distinction. On x86, additional operating system information determines whether a not-present mapping is legitimate. ^[ref]

The four rows drawn under paging are an illustrative model, combining page table and operating system information: virtual page 0x12 is resident in physical frame 0x07 with read-only permission; 0x13 is resident in 0x02 with read/write permission; 0x14 is mapped read/write but nonresident; 0x15 is unmapped. The labels deliberately separate mapping policy, residency and permission. They are not a literal x86 entry layout. A translation lookaside buffer valid flag is a fourth, independent notion: it says that a cached translation can be considered, not that every resident memory page has a cached translation.

A flat array with one page table entry per virtual page would have $2^{16}/256=256$ entries in this example. At an assumed four bytes per entry, it occupies $256\cdot 4=1024$ bytes, whether one memory page or all 256 memory pages are mapped. A multi-level page table saves space in sparse address spaces by allocating lower-level tables only for the regions that need them. The tradeoff is extra dependent lookups during a page table walk; a translation lookaside buffer avoids repeating those lookups on a hit. ^[ref]

One record in a page table, holding a page frame number or a next-level table reference together with architecture-dependent flags. Effective permissions in a multi-level page table can depend on several entries, not just the final one.

A hierarchy of page tables indexed by successive groups of virtual page number bits. Unused regions can omit lower-level tables.

The useful omission is an entire lower-level array, not merely an invalid page table entry. One absent upper-level entry can represent a large unmapped interval of the address space. The Linux kernel's documented hierarchy uses this idea to avoid allocating tables for unused regions; its software levels can also be folded to match the hardware. ^[ref]

Choose an original teaching model with 16-bit virtual addresses, 16-bit physical addresses, and 256-byte memory pages and page frames. The eight high bits identify a virtual memory page; divide these into two four-bit indices. The eight low bits are the offset within the memory page. Thus each page table has 16 entries: the root selects a lower-level page table, and that table selects a data page frame. Every page table entry is four bytes, including its reference and flags. These are chosen model parameters, not a hardware entry encoding.

For a virtual address $v$, extract the root index $i$, lower-level index $j$, and offset $d$ by Euclidean division:Here $\lfloor \cdot \rfloor$ is the floor function and $\mathrm{mod}$ denotes the remainder in Euclidean division. Each index ranges from 0 to 15, and $d$ ranges from 0 to 255. In hexadecimal, virtual address 0x1234 splits into $i=1$, $j=2$, and $d=0x34=52$; its binary numeral system representation is 0001 | 0010 | 00110100.

Fix the requested operation to be a one-byte user read. Assume both table nodes and the data page frame are resident, table reads are allowed, and no mapping changes during the page table walk. The model requires presence at both levels and takes the set intersection of the two entries' read, write, execute, and user-access permissions. This is an explicit memory protection rule for this model; Sv39 page tables use different rules. The root's physical address is 0x8000; the relevant entries are:

The first lookup obtains a table reference, not the final data physical address. The second lookup obtains page frame number 7. Both entries permit a user read, so the original offset is added to the data page frame base:The page table walk therefore reads records at 0x8004 and 0x9008, then the requested read accesses data at 0x0734. All three are distinct physical addresses. These are two dependent table lookups followed by one data access, not a claim of three accesses to main computer memory: a memory cache can satisfy table lookups, and cached intermediate translations can skip them.

Under the same memory protection rule, a user write at 0x1234 fails because lower-level entry 2 denies writes, even though root entry 1 allows them. Clearing either entry's presence flag also prevents the access. An absent root entry stops the page table walk before any lower-level lookup. A page fault then requires the operating system to determine whether a permitted mapping needs storage or the access is invalid; absence alone does not establish demand paging eligibility.

With an empty translation lookaside buffer, the permitted read causes a TLB miss and this successful page table walk, with no page fault. If the resulting mapping and permissions are cached for the current address space, a later read at 0x1235 can use a TLB hit to reach 0x0735. A later write can cause a protection page fault on a TLB hit because the cached mapping remains read-only. Assume cached permissions are current; changing them requires the architecture's prescribed invalidation. A TLB miss describes a missing cached translation, while a page fault describes an access that cannot proceed under the translation or protection rules. ^[ref]

Use the two-level address translation model and map exactly four resident virtual memory pages, numbered 0x12, 0x13, 0xa0, and 0xa1. Assign their data page frames to 0x07, 0x02, 0x05, and 0x06, respectively. Only two root indices occur: 1 and 10. Allocate exactly three table nodes: the root at 0x8000, the lower-level table for root index 1 at 0x9000, and the lower-level table for root index 10 at 0xa000. Root entries 1 and 10 reference those tables; all other root entries are absent. Lower-level entries 2 and 3 in the first table and entries 0 and 1 in the second table hold the four mappings; every other lower-level entry is absent. Use the read-only permissions already specified for virtual memory page 0x12; let the other three mappings permit user reads and writes, with no execution, and let both populated root entries permit user reads and writes.

Each root index covers 16 virtual memory pages, hence $16\cdot 256=4096$ bytes of the address space. A compact table node occupies $16\cdot 4=64$ bytes. The three nodes therefore require $3\cdot 64=192$ bytes of table storage, including the root and all absent entry slots in the allocated nodes. A single-level array requires $256\cdot 4=1024$ bytes for the same address space, saving $1024-192=832$ bytes in the compact model. Four data page frames occupy another $4\cdot 256=1024$ bytes; those contents are separate from table storage.

If instead the allocator dedicates a whole 256-byte page frame to every table node, the three nodes consume 768 bytes, leaving $3(256-64)=576$ bytes unused within those allocations. The single-level table fills four such page frames and still consumes 1024 bytes. Thus this example saves 256 bytes of allocated table storage under that alternative policy. Neither accounting includes allocator metadata, operating-system process records, or translation lookaside buffer storage; data allocations are the same in both designs.

Placement matters as well as mapping count. Four virtual memory pages 0x12, 0x42, 0x72, and 0xa2 require the root plus four lower-level tables: five nodes, 320 compact bytes, or 1280 bytes with a dedicated page frame per node. Only four data page frames are still required. Let $g$ be the number of distinct root indices represented by the mappings. With no retained empty lower-level tables, table storage is $64(1+g)$ compact bytes or $256(1+g)$ allocated bytes under the dedicated-page frame policy. Even an empty address space retains the root in this accounting, so $g=0$ costs 64 or 256 bytes.

For a fully populated address space, $g=16$: 17 nodes cost 1088 compact bytes or 4352 allocated bytes. The single-level table remains 1024 bytes. Sparse allocation is therefore a conditional space benefit; scattered mappings, node allocation granularity, and the root's overhead can reverse it. Additional dependent lookups on a TLB miss also have a cost, but node counts alone establish no universal execution-time ordering.

The actual Sv39 page table geometry uses three nine-bit indices and a twelve-bit offset for base 4096-byte memory pages. Each table contains 512 eight-byte page table entries, exactly one 4096-byte memory page; the satp processor register identifies the root. A 64-bit virtual address must repeat bit 38 in bits 63 through 39. Higher-level terminal entries can also map aligned larger memory pages, shortening the page table walk. These rules differ from the 16-bit, four-byte-entry two-level address translation model. ^[ref]

For ordinary Sv39 page tables, valid nonterminal page table entries reference the next table with read, write, and execute flags clear; those clear flags do not prohibit reading the eventual data. The terminal entry supplies access permissions, with additional processor privilege level and status checks. An invalid entry, malformed encoding, or denied access can cause a page fault. Thus the model's set intersection of read/write permissions at both levels must not be applied mechanically to Sv39 page tables. ^[ref]

In xv6 RISC-V source code, root allocation is separate from lower-level allocation: uvmcreate() allocates and clears a root page table, while walk() with allocation enabled allocates and clears missing lower-level tables and installs valid references to them. With allocation disabled, a missing table makes walk() return failure. This software routine finds a page table entry for the operating system; it is not the hardware's complete permission-checking page table walk. ^[ref]

Looking up page table entries to obtain a page frame number and effective access attributes. On ordinary x86 hardware paging, a TLB miss can initiate this lookup without entering the operating system.

// Target: computer-science.bigb