A process removes write permission from a page, updates the page-table entry, and hands the physical frame to a read-only consumer. Another core writes through a translation cached before the update. The page table in memory is correct; the system is not.
Page tables are authoritative data structures, but processors cache their results. Correctness therefore has two layers:
- a page-table walk must derive the right frame and authority from the current entries; and
- every translation cache that could hold an older result must stop using it before the old authority is considered revoked.
Translation-cache invariant. Every usable TLB entry must be equivalent to a currently authorized page-table translation, or the kernel must prevent the entry from being used until invalidation completes.
Sv39 is a radix-tree lookup
The baseline RISC-V Sv39 scheme uses 4 KiB pages and three page-table levels. A page-table page contains 512 eight-byte entries, so each level consumes nine virtual-page-number bits. The 64-bit virtual address is interpreted as:
| Field | Bits | Meaning |
|---|---|---|
| sign extension | 63:39 | must equal bit 38 for a canonical Sv39 address |
VPN[2] | 38:30 | root-page index |
VPN[1] | 29:21 | middle-level index |
VPN[0] | 20:12 | final-level index |
| page offset | 11:0 | byte within a 4 KiB page |
The satp control register identifies the translation mode, root page-table physical page number, and—when implemented and used—an address-space identifier (ASID). An Sv39 page table is a sparse radix tree: a non-leaf PTE points to the next page-table page; a leaf PTE supplies the final physical page number (PPN) and permissions.
PTE meaning before arithmetic
For the baseline Sv39 PTE, the relevant low bits are:
| Bit | Name | Architectural role in this model |
|---|---|---|
| 0 | V | entry is valid |
| 1 | R | loads permitted at a leaf |
| 2 | W | stores permitted at a leaf |
| 3 | X | instruction fetch permitted at a leaf |
| 4 | U | user-mode access permitted |
| 5 | G | mapping is global across address spaces |
| 6 | A | page has been accessed, according to the implemented A/D scheme |
| 7 | D | page has been written, according to the implemented A/D scheme |
9:8 | RSW | reserved for supervisor software |
53:10 | PPN | next table or mapped physical page |
An entry with V=0 is invalid. The combination R=0, W=1 is also reserved as invalid. If any of R, W, or X is set in a valid entry, the entry is a leaf. If all three are clear, the entry is a pointer to the next level. User access additionally requires the appropriate operation permission and U=1.
Leaf entries may appear above level zero to create superpages. A level-1 leaf maps 2 MiB; a level-2 leaf maps 1 GiB. The unused low PPN fields must be zero so the physical superpage is aligned. A high-level leaf with misaligned physical bits faults rather than rounding the address.
Retrieval — reconstruct the discriminator. Why can the walker not decide “leaf versus next table” from V alone?
Reveal the diagnostic answerExpandCollapse
V establishes only that the entry has an architecturally valid form. A valid entry with R=W=X=0 points to a lower-level table; a valid entry with any of R, W, or X set is a leaf. Treating every valid PTE as a leaf would interpret a page-table page’s PPN as application data.
Sv39 page tables and TLB management
Evaluate each statement regarding RISC-V Sv39 radix page tables and TLB coherence:
Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.
Execute a complete page-table walk
For a memory access at virtual address a conceptual Sv39 walker performs this state transition:
require canonical(v)
table_pa := satp.PPN × 4096
for level i := 2 down to 0:
pte_pa := table_pa + VPN[i](v) × 8
pte := physical_memory[pte_pa]
reject invalid encodings
if pte is a leaf:
check superpage alignment, privilege, and access permission
combine leaf PPN, any inherited VPN bits, and offset
return physical address
if i = 0:
fault: no leaf exists
table_pa := pte.PPN × 4096
The pseudocode omits extension-dependent details but preserves the control dependencies: validity before dereference, leaf classification before permission checks, and permission checks before the data access completes.
Worked trace: a three-level 4 KiB mapping
Translate a user read from virtual address 0x0000000123456789. It is canonical because bit 38 and bits 63:39 are all zero.
Field extraction gives:
| Field | Decimal | Hex |
|---|---|---|
VPN[2] | 4 | 0x004 |
VPN[1] | 282 | 0x11A |
VPN[0] | 86 | 0x056 |
| offset | 1929 | 0x789 |
Assume satp.PPN selects root table physical address 0x81000000.
- Root PTE address:
0x81000000 + 0x004 × 8 = 0x81000020. Its valid non-leaf PTE points to table0x81200000. - Middle PTE address:
0x81200000 + 0x11A × 8 = 0x812008D0. Its valid non-leaf PTE points to table0x81300000. - Final PTE address:
0x81300000 + 0x056 × 8 = 0x813002B0. It is a leaf withV=1, R=1, W=0, X=0, U=1and PPN0x2A35F. - A user read is authorized. The physical address is
(0x2A35F << 12) | 0x789 = 0x2A35F789.
Changing the operation to a store produces a protection fault at step 3; the walker must not issue a store to 0x2A35F789. Changing U to zero also rejects the user access even though R=1.
Worked trace: a level-1 superpage
Take virtual address fields VPN[2]=7, VPN[1]=12, VPN[0]=301, offset 0x2A0. At level 1 the walker finds an R-X leaf. A 2 MiB mapping replaces only the high physical page-number fields; the low nine PPN bits represented by VPN[0] come from the virtual address. The physical construction is conceptually:
If PTE.PPN[0] is nonzero, the leaf is misaligned and the access faults. Copying the full PTE PPN into the physical address would map a 4 KiB page and discard the very property that made the entry a level-1 leaf.
Application — audit a walk. A trace reaches level 0 with V=1, R=0, W=0, X=0. The implementation returns PTE.PPN << 12 | offset. Identify the defect and the correct architectural outcome.
Reveal the auditExpandCollapse
At level 0, a valid non-leaf entry asks the walker to descend when no level remains. No leaf translation exists, so the access faults. Returning the PPN exposes the page-table page itself as user data and can turn metadata into writable authority if subsequent checks are also wrong.
A TLB caches a proof result, not only a number
A translation lookaside buffer (TLB) caches a key such as (ASID, VPN, page size) and a result containing the PPN plus permission and status state. A TLB hit bypasses page-table memory references, but it does not bypass the access check. A cached read-only translation must still reject a store.
A TLB miss means the translation is absent from the cache. A page fault means translation cannot complete under the current page-table and access rules. A TLB miss can end in a successful walk; a TLB hit can end in a protection fault.
Translation cost under an explicit serial model
Assume:
- a TLB lookup costs
- each memory access costs
- a miss performs an -level serial page-table walk and then the requested data access;
- the walk is not served by caches and does not overlap the data-cache lookup; and
- page faults are excluded.
With TLB hit rate
For ns, ns, and
The 2% miss rate adds 3.6 ns over the 61 ns hit path under this model. Real processors overlap lookups and cache page-table entries, so this equation is a derivation exercise, not a hardware benchmark.
Application — expose the hidden assumption. A report uses 1 ns + 3 × 60 ns + 60 ns = 241 ns as the cost of every load on the machine above. Which observation would falsify the report fastest?
Reveal the diagnosisExpandCollapse
A high TLB hit rate falsifies the assumption that every load performs a walk. The 241 ns path applies only to a miss under the serial, uncached model. A useful follow-up measurement separates TLB hits, TLB misses with cached walk data, and page faults; averaging all memory operations into the worst modeled path erases the mechanism.
Reach and page size
TLB reach is the mapped byte span represented by useful cached entries. Sixty-four 4 KiB entries cover at most 256 KiB; sixty-four 2 MiB entries cover 128 MiB. Larger pages increase reach but coarsen allocation, sharing, protection, and fault granularity. Reach is an upper bound: conflicting sets, mixed page sizes, duplicate aliases, and context changes can reduce useful coverage.
Experiment: translation, permission, and cache state
The investigation below uses a deliberately small machine: 12-bit virtual addresses, 256-byte pages, one page-table level, 4-bit physical frame numbers, and a fixed ASID-tagged TLB snapshot. It models address decomposition and permission decisions, not Sv39’s three memory references, replacement behavior, A/D updates, or invalidation races.
Prediction — record an answer before changing a control. Process A reads virtual 0x4A3. Which bits are preserved in the physical address, and can a TLB hit make a later write legal if the PTE is read-only?
Translate a virtual address—or trigger a fault
This bounded 12-bit machine uses 256-byte pages. Change the process, access type, and address to expose ASID-tagged TLB hits, page-table walks, non-present pages, shared frames, and permission failures.
Model scope: one-level page tables, 4-bit frame numbers, no huge pages, and a fixed TLB snapshot. Real 64-bit machines use multi-level tables and wider physical addresses; the VPN/offset and permission invariants are unchanged.
Static state: process A reads 0x4A3. VPN 4 is cached and maps to frame 2, preserving offset 0xA3, so the physical address is 0x2A3.
Transfer — force three distinct outcomes. Find one setting that produces a TLB hit, one that performs a successful page-table walk, and one that faults despite the page being present. For each, write (process, access, VA, VPN, offset, result) and identify the first decision that distinguishes it from the other two.
Reveal one admissible set and the verification criteriaExpandCollapse
Examples from the fixed model:
(A, read, 0x4A3)selects VPN0x4, offset0xA3; A’s TLB contains the mapping, so the result is frame0x2, physical0x2A3.(B, read, 0x8A3)selects VPN0x8, offset0xA3; the page is present but absent from B’s fixed TLB, so a walk maps it to frame0x6, physical0x6A3.(A, write, 0xCA3)selects present VPN0xC, but itsr--permission rejects the store.
Thus the prediction preserves the low eight bits 0xA3; a TLB hit cannot make a write legal when the cached translation is read-only because permission state is part of the cached result. Equivalent states are fully valid. The decisive evidence is not the widget label: the answer must show key lookup, presence, and operation-specific authority as separate checks.
Context switches, ASIDs, and invalidation
Without ASIDs, a context switch that installs a new address space may require discarding untagged user translations. With ASIDs, translations from multiple address spaces can coexist and be selected by (ASID, VPN). ASIDs optimize identity; they do not remove revocation. Reusing an ASID for a different page table requires invalidating translations associated with the old meaning.
RISC-V SFENCE.VMA orders the issuing hart’s explicit page-table updates with that hart’s later translations and invalidates translations selected by its operands. It is a local-hart operation. Revoking a mapping on a multicore system requires coordination with every hart that could use the address space.
The protocol’s safety point is the final arrow. Reusing the frame after changing the PTE but before remote acknowledgement can expose the new owner’s bytes through an old translation. Sending an interprocessor interrupt without waiting for completion is also insufficient: delivery is not invalidation.
Worked race: stale writable authority
- Hart 1 runs process A and caches
(ASID 9, VPN 4) → PFN 21, RW. - Hart 0 changes A’s PTE to read-only and maps PFN 21 into process B as private data.
- Hart 0 performs a local fence but sends no shootdown.
- Hart 1 resumes A and stores through its cached
RWentry.
The page-table snapshot appears secure, yet A modifies B’s data. The defect is not “the TLB contains old data” in an abstract sense; it retains old authority. The repair must cover every hart on which A could have run, or prove that a hart never cached A’s translations.
Transfer — optimize without weakening safety. A process has run only on harts 0 and 2 of a 64-hart machine. State a valid targeted shootdown and the evidence the kernel must maintain to avoid sending 62 unnecessary invalidations.
Reveal the argumentExpandCollapse
Track an address-space CPU mask that conservatively includes every hart that may hold its translations. Update the PTE, send range/ASID invalidations to harts 0 and 2, execute the corresponding local invalidation on the initiating hart when applicable, wait for acknowledgements, and only then complete revocation or frame reuse. The optimization is sound only if mask updates are synchronized with scheduling; a false negative is a security bug, while a false positive costs performance.
Counterexamples that separate the mechanisms
| Claim | Counterexample | Correct distinction |
|---|---|---|
| “TLB miss means the page is on storage.” | present PTE absent from TLB | cache miss versus not-present fault |
| “A valid PTE is a leaf.” | valid R=W=X=0 entry | next-table pointer versus leaf |
| “ASIDs eliminate flushes.” | ASID reuse or permission downgrade | identity tagging versus revocation |
| “A larger page always improves performance.” | sparse writes dirty an entire coarse mapping and waste memory | reach versus granularity |
| “Updating the PTE revokes access.” | remote hart retains writable TLB entry | authoritative table versus cached authority |
| “More TLB entries give exactly proportional reach.” | set conflicts and mixed mappings | capacity bound versus effective coverage |
Deep Practice
Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.
Exercise 4.2.1: Extracting Sv39 Three-Level Virtual Page Number Indices
Given a 64-bit canonical virtual address 0x0000000123456789 in RISC-V Sv39:
- Verify whether the address is canonical.
- Extract the 12-bit intra-page byte offset.
- Extract the 9-bit indices for VPN[2] (root level), VPN[1] (middle level), and VPN[0] (leaf level) in hexadecimal and decimal.
HintExpandCollapse
Sv39 requires bits 63:39 to equal bit 38, followed by three 9-bit VPN fields and a 12-bit offset.
Worked solutionExpandCollapse
- Canonical check:
Bit 38 is the most significant bit of VPN[2]. For
0x0000000123456789, bit 38 is 0. Bits 63:39 are all 0, matching bit 38. Hence, the address is canonical. - Page offset:
The lowest 12 bits (bits 11:0) are
0x789(decimal 1929). - VPN decomposition:
Shift right by 12 bits to discard the offset:
0x0000000123456.- (decimal 86).
- (decimal 282).
- (decimal 4).
Exercise 4.2.2: Distinguishing Leaf Translations from Intermediate Radix Pointers
An operating system kernel traverses an Sv39 page table. At level 1, the MMU encounters a PTE with bit pattern 0x0000000080000A0B.
- Decode the flag bits
- Determine whether this PTE is an invalid entry, a pointer to a level-0 page table, or a superpage leaf translation.
- If it is a leaf, state the page size mapped and verify if the physical alignment requirement is satisfied.
HintExpandCollapse
Inspect bits 0 (V), 1 (R), 2 (W), and 3 (X). For a leaf at level 1, PPN[0] must be zero.
Worked solutionExpandCollapse
- Flag decoding:
The lowest byte is
0x0B- Bit 0 = 1 (valid).
- Bit 1 = 1 (readable).
- Bit 2 = 0 (not writable).
- Bit 3 = 1 (executable).
- Bit 4 = 0 (supervisor only).
- Classification: Since and at least one of is set this PTE is a leaf translation, not a next-level pointer (which would require
- Superpage alignment: At level 1, a leaf maps a 2 MiB superpage The physical page number occupies bits 53:10. Shift right by 10 bits: The lowest 9 bits of PPN are Because the superpage is misaligned. Hardware will raise a page-fault exception on access rather than translating.
Exercise 4.2.3: Calculating Effective Memory Access Time with Multi-Level Walks
A system features a single-level TLB with hit access time and main memory access time Address translation requires a 4-level page table walk in hardware on a TLB miss.
- Formulate the equation for Effective Memory Access Time given TLB hit rate
- Calculate for
- Calculate the minimum TLB hit rate required to keep translation overhead within 10% of bare memory access time
HintExpandCollapse
On a TLB hit, time is t_TLB + t_mem. On a miss, time is t_TLB + 4 * t_mem + t_mem.
Worked solutionExpandCollapse
- EMAT formulation:
- TLB hit:
- TLB miss (4 memory accesses for the walk plus 1 for the data):
- Numeric evaluation for
- Threshold hit rate: We require A hit rate of at least 98.0% is required.
Exercise 4.2.4: TLB Reach Expansion via Megapages and Gigapages
A processor TLB contains 512 entries.
- Compute the TLB reach using standard 4 KiB base pages.
- If an application database allocates 256 entries for 2 MiB superpages and 256 entries for standard 4 KiB pages, compute the new total TLB reach.
- Explain why using 2 MiB superpages for an irregular 12 KiB data structure is counterproductive.
HintExpandCollapse
TLB reach is the number of entries multiplied by page size. Consider internal fragmentation for small structures.
Worked solutionExpandCollapse
- Base page reach:
- Mixed superpage reach: Using superpages expands the virtual address reach by more than 250 with identical hardware entry counts.
- Fragmentation drawback: Mapping a 12 KiB structure with a 2 MiB superpage wastes of contiguous physical RAM to internal fragmentation. Furthermore, page-out or dirty-tracking operations must move or mark the entire 2 MiB chunk, wasting memory bandwidth.
Exercise 4.2.5: Proving Correct Ordering in Multi-Core TLB Invalidation Protocols
Let Core 0 update a PTE to revoke write permissions on physical frame intending to reassign to an isolated process on Core 1. Prove that Core 0 must not allocate until all remote cores have completed and acknowledged their TLB shootdown.
HintExpandCollapse
Show that a window exists where Core 1 writes through stale TLB authority if reuse precedes shootdown completion.
Worked solutionExpandCollapse
Assume for contradiction that Core 0 reallocates frame to Process before Core 1 acknowledges completion of the TLB invalidation.
- Prior to revocation, Core 1 executes Process and caches a valid, writable TLB entry:
- Core 0 modifies the memory PTE for to set (or and issues an asynchronous Inter-Processor Interrupt (IPI) to Core 1.
- Without awaiting acknowledgment, Core 0 assigns frame to Process and begins initializing confidential data into
- Before Core 1 handles the IPI, Process on Core 1 executes a store instruction to
- The MMU on Core 1 queries its local TLB, finds the cached translation with and commits the store directly into physical frame without walking the memory page table.
- Process has thus corrupted or observed Process ‘s confidential memory, violating the fundamental memory isolation invariant.
Therefore, the happens-before edge:
is strictly necessary for safety.