ECE344 Fall 2026 (Sec 1) Lec 10 - Page Tables

Overview

Jon Eyolfson explains how RISC-V SV39 multi-level page tables reduce the memory cost of sparse per-process address spaces: instead of a 1 GB flat table for a 39-bit virtual address, a translation typically needs only three 4 KB tables. He traces the address-indexing and page-walk process, then connects it to page alignment, xv6 allocation, page faults, lazy allocation, and copy-on-write.

Key takeaways

A flat SV39 page table needs 2^27 entries; at 8 bytes each, that is 1 GB per process even when most virtual pages are unused.
Three levels of 512-entry tables reduce the storage needed for a single mapped page to 12 KB, because unmapped regions can be excluded by invalid upper-level entries.
SV39 uses a 12-bit page offset and three 9-bit VPN indices; the page walk replaces the VPN with the final PPN while preserving the offset.
Multi-level page tables save memory for sparse mappings but add page-table memory accesses, making translation caching important.
Page faults enable both lazy allocation and copy-on-write: the kernel can create a page on first access or copy a shared page only when a process writes.
Page validity applies to a full 4,096-byte page, so an invalid pointer access can escape detection when it lands within an already mapped page.

Chapters

0:00 Test One Scope, Study Materials, and Lab Expectations

Test One covers material through the first half of the next lecture on virtual memory; Jon Eyolfson recommends archived ECE344 and 2025 ECE353 midterms for practice.
The test emphasizes operating-systems concepts and interpreting or fixing supplied code rather than writing large programs from scratch.
Students should also understand Labs 1 and 2; the lecture notes that the course has not yet introduced threads or concurrency.

4:48 Why a Flat SV39 Page Table Can Cost 1 GB

A 39-bit virtual address with 4,096-byte pages has a 12-bit offset and a 27-bit virtual page number, requiring 2^27 entries in a flat table.
At 8 bytes per page-table entry, a flat table occupies 2^30 bytes, or 1 GB, for each process.
Programs such as `cat` use only a small fraction of their address spaces, so most flat-table entries would merely mark unmapped addresses as invalid.

7:27 Fitting 512 Page-Table Entries on One Page

A 4,096-byte page holds 512 entries when each page-table entry is 8 bytes: 4,096 ÷ 8 = 512 = 2^9.
Using those 9 bits as an index makes a single page-sized table cover only a 21-bit address space, or 2 MB, which is too small for typical processes.
The RISC-V SATP register identifies the root page table by its physical page number; on x86, the corresponding register is CR3.

11:21 Page Alignment, PPNs, and Virtual-to-Physical Translation

With 4,096-byte pages, page-aligned addresses have their low 12 bits set to zero, so the page number and offset can be handled separately.
A physical page number (PPN) identifies a physical page without its offset; a virtual page number (VPN) identifies the process's virtual page to translate.
An 8-byte-aligned page-table entry begins at an address divisible by 8, which can be checked by confirming its lowest three binary bits are zero.

15:38 SV39 Splits the VPN into Three 9-Bit Indices

SV39 divides the 27-bit VPN into L2, L1, and L0 indices of 9 bits each, with every level containing up to 512 entries.
SATP points to the root L2 table; a valid L2 entry points to an L1 table, an L1 entry points to an L0 table, and the L0 entry supplies the final PPN.
Each index selects an entry in its level's page-table array, allowing the page-table structure to grow only where virtual addresses are mapped.

22:21 Sparse Address Spaces Save Memory at the Cost of More Lookups

A single virtual-page translation in a three-level table needs only three page-sized tables, or 12 KB, instead of a 1 GB flat table.
An invalid entry stops the page walk early: an invalid L2 entry can exclude a 1 GB region, while an invalid L1 entry can exclude a 2 MB region.
The tradeoff is more memory accesses during translation—three page-table reads rather than one for a flat table—so a cache such as a translation lookaside buffer is needed to address the latency.

27:57 Page-Table Entries, Huge Pages, and xv6 Helpers

A page table is an array of 512 64-bit entries, totaling exactly 4,096 bytes; L2 and L1 entries point to lower-level tables, while L0 entries provide final mappings.
In the described RISC-V PTE scheme, a valid entry with no read, write, or execute permissions indicates a next-level table; permission bits identify a leaf mapping.
A leaf at L1 can map a 2 MB huge page, and a leaf at L2 can map a 1 GB page, avoiding lower-level tables for large contiguous regions.
The xv6 helpers `pte2pa` and `PX` extract a physical address from a PTE and an index for a page-table level, respectively.

33:50 How xv6 Allocates and Frees Physical Pages

The kernel's physical-memory allocator organizes free frames as a linked list, using a page itself to store its next pointer while that page is free.
Allocation removes a page from the free-list head; deallocation returns it to the list.
A newly allocated page table is zeroed so that all of its entries initially represent invalid mappings.

35:54 Walking a Two-Level Table for a 30-Bit Address

For a 30-bit virtual address and 4,096-byte pages, the VPN has 18 bits; a flat table of 8-byte entries would require 2 MB per process.
A two-level design uses 9-bit L1 and L0 indices; mapping just one virtual page requires one page for each table, or 8 KB.
For virtual address `0x3FFFF008`, both indices are 511 and the offset is `0x008`; with the demonstrated L0 PPN `0xCAFE`, the translated physical address is `0xCAFE008`.

42:20 Aliased Page Tables, Page Faults, and Segmentation Faults

A page-table entry can point to the same lower-level table as another entry, making distinct virtual addresses map to the same physical pages—an alias that can cause unintended shared writes.
If a page-table walk reaches an invalid entry, the MMU raises a page fault; the kernel can reject an illegal access, resulting in a segmentation-fault signal.
The kernel can also handle a fault by allocating and mapping a page on first access, then restarting the instruction so the process need not observe the fault.

47:00 Copy-on-Write and the MMU Simulator Walkthrough

Copy-on-write lets processes created by `fork` initially share a physical page; when one writes, the kernel handles the fault by copying the page and giving that process an independent mapping.
The lecture's MMU simulator models 16 physical frames and provides allocation, `map`, and `translate` operations that show each level of an SV39 page-table walk.
A valid PTE maps an entire 4,096-byte page, not an individual byte: changing the offset does not change the page-table lookup, and an out-of-bounds access can go unnoticed if it remains on a mapped page.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Jon Eyolfson.