Prep: Sv39 Page Tables — 33k

Session: Fri Oct 9, 1h30 · Exercises: 33k_paging · Prep time: ~50 min · Lecture: Virtual Memory I: Sv39 Page Tables

What you will build

The page-table tree the hardware will eventually read: a root, interior tables, and leaf entries mapping virtual pages to physical ones. You will pack an address and flags into one 64-bit entry, unpack it, and descend three nine-bit levels to the level-0 slot, taking a zeroed page from Thursday's allocator whenever a level is missing. The MMU stays off; a software translator stands in for it. The self-test checks that an entry round-trips, the UART page identity-maps, a high virtual address forces new interior tables, and an unmapped address does not translate.

Concepts you need

• The untranslated offset — Virtual Memory I §2 · Sv39 Paging § Splitting a virtual address
• Three nine-bit indices — Virtual Memory I §3.1, §3.2
• PTE layout: PPN at bit 10 — Virtual Memory I §4.1, §4.4 · Sv39 Paging § The page-table entry
• Leaf versus branch — Virtual Memory I §4.2 · Sv39 Paging § Leaf or branch
• The three-level descent; tables allocated on demand — Virtual Memory I §5.1, §5.5 · Sv39 Paging § Descending the tree
• Building a table vs. the hardware using one — Virtual Memory I §6.1

Read before class

What	Time
Virtual Memory I §2–§4 (formats, PTE bits, leaf vs. branch)	20 min
Virtual Memory I §5.1, §5.4–§5.5 (two worked translations)	10 min
Sv39 Paging: The page-table entry, Leaf or branch, descending the tree	10 min
Paper worksheet (below)	10 min

Worksheet: draw a 64-bit PTE as boxes labeled 53..10 (PPN), 9..8 (RSW), 7..0 (D A G U X W R V). Encode physical 0x8040_0000 as valid, readable, writable; decode 0x0000_0000_2010_040F into an address and a leaf-or-branch verdict. Bring it to class.

Mental model

By hand, with the root at 0x8700_0000:

va 0x4020_1ABC -> VPN[2]=1  VPN[1]=1  VPN[0]=1  offset=0xABC

root[1]   = 0x21C0_0401   V only  -> table at 0x8700_1000
level1[1] = 0x21C0_0801   V only  -> table at 0x8700_2000
level0[1] = 0x2010_0007   V R W   -> page  at 0x8040_0000

phys = 0x8040_0000 | 0xABC = 0x8040_0ABC

The answer keeps the question's low three hex digits. Building that mapping into a table with only a root: entry 1 is invalid, so the kernel takes a page from the allocator, zeroes it, writes a V-only entry pointing at it, and repeats one level down. Two table pages for one data page — the tree charges for spread, not volume. Zeroing matters: a page fresh off the free list still holds the list's next pointer, and a stale word with bit 0 set looks like a valid entry.

Check yourself

1. PTE 0x0000_0000_2010_0401: leaf or branch, and what address?
   Answer

   Low ten bits 0x001: V only, so a branch. Shift right by 10 (not 12) gives PPN 0x80401; left by 12 gives 0x8040_1000, the next table.
2. Why zero a freshly allocated interior table before linking it in?
   Answer

   It still holds the free list's next pointer; a stale word with bit 0 set reads as a valid entry, and a later descent follows it into nonsense.
3. A table has only a root. You map one page whose subtree does not exist. How many table pages are allocated, with what low ten bits?
   Answer

   Two, level 1 and level 0, linked by entries with low bits 0x001, V alone. Adding R still passes a software check of V, but the hardware would treat that entry as a superpage leaf.

What "done" looks like

oslings run is green, then oslings submit before you leave. Not green? Submit anyway (substantial credit), then finish by Monday 11:59 pm and submit again. Midterm 1 is next Thursday, Oct 15, and covers everything through this exercise.

If you finish early

Work the lecture's Practice Problems on paper and reread Sv39 Paging § Mistakes that cost points (Midterm 1 material). Then read xv6 book chapter 3, "Page tables," or start the next prep page, Prep: Processes.