Step 1 of 18 · commit 1: Limit user memory to below the PLIC

A cap on user memory

The story in this tour, recorded with gdb attached on three harts: you type sumtest, the shell forks pid 3, pid 3 calls exec, and sumtest (still pid 3) runs its checks: copies through pipes and files, a read into a lazy page, bad pointers, fork.

A note on the state boxes: the tour schema knows only three page tables, so on this branch satp: kernel means the running process’s own kernel page table (p->kpagetable), except in the scheduler, where the details say which.

Commit 1 makes room. A process’s kernel page table (commit 2) will map the process’s pages at their user addresses, next to everything the kernel maps. The kernel’s lowest mapping is the PLIC, at 0x0c000000 (192 MB); the UART and virtio come next, at 0x10000000. So user memory now ends at USERTOP = PLIC instead of TRAPFRAME. growproc (eager sbrk) and sys_sbrk (lazy) test against it, and kexec refuses a program whose segments or stack would end above it.

The TRAPFRAME and TRAMPOLINE pages stay where they were, above USERTOP: they have no PTE_U and will never be mirrored.

Step 2 of 18 · commit 1: Limit user memory to below the PLIC

Two usertests that asked for a gigabyte

lazy_alloc and lazy_unmap reserve REGION_SZ bytes with sbrklazy and touch one page in every 64 (lazy_unmap one in every 4096, each in a new child). With a 192 MB ceiling, a 1 GB reservation fails and both tests would print sbrklazy() failed. 176 MB fits below the ceiling and is still more than all of RAM, so only a lazy reservation can succeed. The tests do less than before, though: lazy_alloc touches 704 pages instead of 4,096, and lazy_unmap runs 11 rounds instead of 64.

lazy_sbrk changed too (in the same commit): it grew memory in 1 GB steps towards MAXVA and checked the top page below TRAPFRAME. Its loop never notices that sbrklazy failed, so with the new cap it would spin forever. It now grows to one page below USERTOP in a single call; the step loop and its comment are gone. These are the only changes to usertests, and every check is kept.

Step 3 of 18 · commit 2: Give each process its own kernel page table

A kernel page table that shares almost everything

kvmcreate builds one process’s kernel page table in two pages:

• a root that starts as a copy of kernel_pagetable's 512 entries, so entries 2 (RAM) and 255 (trampoline, kernel stacks) point at the kernel’s own level-1 pages, shared;
• a private level-1 page for gigabyte 0, a copy of the kernel’s, whose entries 96 to 128 still point at the kernel’s level-0 pages for the PLIC, UART and virtio. Entries 0 to 95, below USERTOP, are empty: the user pages go there (commit 3).

gdb read the shell’s (pid 2’s) kernel page table on the finished branch:

               kernel_pagetable   sh's kpagetable
root[0]        0x21fff801         0x21fcc001    private level-1 page
root[2]        0x21ff7001         0x21ff7001    shared (RAM)
root[255]      0x21fe6c01         0x21fe6c01    shared (trampoline, kstacks)
level-1[96]    0x21fff001         0x21fff001    shared (PLIC)
level-1[128]   0x21fff401         0x21fff401    shared (UART, virtio)

kvmcreate is called from allocproc with the new process’s p->lock held: when sumtest forks, that is pid 4’s lock, noff 1, and intena 1, because the system call turned interrupts on before the acquire. (allocproc's lock state is reasoned from the code; gdb recorded noff 1, intena 1 a few lines later in kfork, under the same lock.)

Step 4 of 18 · commit 2: Give each process its own kernel page table

Freeing exactly what is private

kvmfree frees the private level-1 page, the level-0 pages under its entries 0 to 95 (PX(1, USERTOP) = 96), and the root. It does not touch the leaf PTEs: the user pages belong to the user page table, which proc_freepagetable frees, and the shared kernel pages belong to the kernel.

That loop bound is a promise: nothing is ever mapped in entries 96 and above of the private level-1 page. Commit 1’s cap keeps it. Clinic 3 breaks the cap, and this loop then leaks exactly the level-0 pages it does not know about (383 of them in that run).

freeproc calls it from kwait with wait_lock and the zombie’s p->lock held (state reasoned from the code). kfree only takes kmem.lock, briefly.

Step 5 of 18 · commit 2: Give each process its own kernel page table

The scheduler installs the process's page table

The scheduler has chosen sumtest and holds its p->lock. Before swtch it now calls kvmswitch(p->kpagetable): sfence.vma, csrw satp, sfence.vma. gdb on hart 0:

before kvmswitch   satp = 0x8000000000087fff   (kernel_pagetable 0x87fff000)
after kvmswitch    satp = 0x8000000000087f10   (sumtest's kpagetable 0x87f10000)
noff 1, intena 0, sstatus 0x200000020, sp 0x80008860

The hart keeps running the scheduler, on the scheduler stack, after satp changed: the code, the stack (stack0 in the kernel’s data) and proc[] are mapped identically in both page tables. From swtch on, sumtest runs with its own kernel page table, and prepare_return will store it as kernel_satp (kernel/trap.c:116), so every later trap from user mode lands on it too.

intena is 0: the scheduler’s intr_on(); intr_off(); window left interrupts off before this acquire.

Step 6 of 18 · commit 2: Give each process its own kernel page table

And switches back before letting go

When sumtest gives up the hart (it yields, sleeps or exits), swtch returns here with its p->lock still held. The first thing the scheduler does is kvminithart: back to kernel_pagetable.

The order matters. After release(&p->lock):

• if sumtest is a zombie, its parent’s kwait can take the lock and freeproc frees its kernel page table;
• if it is runnable, another hart can run it, and its exec frees the old kernel page table.

Either way, a hart that were still using that page table would walk a freed page at its next TLB miss. Clinic 6 leaves this line out: gdb found two harts whose root page table had become a trapframe.

(The state shown is reasoned: the line runs right after swtch returns, under the lock the process handed back.)

Step 7 of 18 · commit 3: Map user pages in the process's kernel page table too

Mirroring the user's pages

kvmsync makes one range of a process’s kernel page table agree with its user page table. For each page: if the user PTE is a valid leaf with PTE_U, copy it (allocating level-0 pages in the private level-1 page as needed); otherwise clear the kernel copy, if there is one.

The PTE_U test keeps the stack guard page out. gdb, the shell’s PTEs for 0x0-0x4000 on the finished branch:

va       user page table   kernel page table
0x0000   0x21fce05b        0x21fce01b    text (R|X|U)
0x1000   0x21fcd41b        0x21fcd45b    text
0x2000   0x21fcd0d7        0x21fcd017    data (R|W|U)
0x3000   0x21fccc07        0x0           guard page: no U, not mirrored
0x4000   0x21fcc8d7        0x21fcc817    stack

Same physical pages, same permissions, but different A (0x40) and D (0x80) bits: the hardware sets them in whichever copy it used. The user ran its text and wrote its data and stack; the kernel only read 0x1000. Nothing in xv6 reads A or D, but a kernel that did (to choose pages to swap out, for example) would have to combine both copies.

The function only writes the private part of the kernel page table, and only for addresses below USERTOP: its callers guarantee that.

Step 8 of 18 · commit 3: Map user pages in the process's kernel page table too

sbrk in both directions

Growing: uvmalloc maps the new pages in the user page table, kvmsync mirrors them. If the mirror runs out of memory for a level-0 page, both are undone and sbrk fails. No TLB flush: the hart has never seen these addresses mapped, and before user code can touch them, the return to user mode flushes (kernel/trampoline.S:110).

Shrinking: uvmdealloc unmaps and frees the pages, kvmsync clears their kernel copies, and then sfence.vma, because this hart is running on this very page table and may hold the freed pages in its TLB (translation lookaside buffer). Without the flush, a copy later in the same system call could still reach a page that kfree has handed to someone else.

gdb caught sumtest here three times (the copy check giving its 2 pages back, and the lazy check twice): hart 0, satp 0x8000000000087f10 (its own kernel page table), noff 0. usertrap turned interrupts on for the system call, and no lock is held.

Step 9 of 18 · commit 3: Map user pages in the process's kernel page table too

fork mirrors the child's whole image

After uvmcopy fills the child’s user page table, kvmsync copies all of [0, sz) into the child’s kernel page table. gdb, in sumtest’s fork check: hart 0, child pid 4, sz 32768, noff 1 (pid 4’s lock, held since allocproc), intena 1, the parent’s satp 0x8000000000087f10, the child’s new kernel page table at 0x87f42000.

The mirror is placed after line 294 (np->sz = p->sz, unchanged base code) on purpose. If the mirror fails, freeproc frees the child’s user page table with uvmfree(pagetable, np->sz). With np->sz still 0 it would unmap nothing and freewalk would find leaf PTEs and panic freewalk: leaf. In the original code the order did not matter, because uvmcopy cleans up after itself on failure.

No flush: no hart is using the child’s page table yet. The scheduler flushes when it installs it.

Step 10 of 18 · commit 3: Map user pages in the process's kernel page table too

exec swaps both page tables at once

The shell’s child (pid 3) has loaded sumtest into a new user page table. Before the point of no return, kexec also builds a new kernel page table for the new image (kvmcreate + kvmsync); if either fails, exec fails cleanly and the old image is untouched.

At the commit it swaps both, then kvmswitch puts the new kernel page table in satp and only then frees the old ones. gdb at line 151, on hart 0:

satp before    0x8000000000087f51   (the kernel page table pid 3 got from fork)
kpagetable     0x87f10000           (new)
oldkpagetable  0x87f51000
noff 0, intena 1, sstatus 0x200000022 (SIE on)

Switching satp with interrupts on, in the middle of a system call, is safe: the code, this kernel stack and all kernel data are mapped the same way in both tables. If a timer interrupt preempts the process between line 147 and line 151, it resumes (perhaps on another hart) with the scheduler installing p->kpagetable, already the new one.

The argument copies just above (kernel/exec.c:106, kernel/exec.c:117) go into the new user page table while the old one is current: those copies cannot use the new addresses directly, which is why commit 6 keeps the software walk in copyout for any page table that is not the current process’s.

Step 11 of 18 · commit 3: Map user pages in the process's kernel page table too

A lazy fault fills both tables

usertrap's lazy-allocation branch now calls uvmfault(p, va, read) instead of vmfault (kernel/trap.c:72 on this commit): vmfault maps the zeroed page in the user page table, kvmsync adds it to the kernel page table. If that second step runs out of memory, the first is undone, so the invariant “a PTE_U page is mapped in both or in neither” survives even out of memory.

No flush here: the fault came from user mode, and the faulting instruction runs again only after userret, whose sfence.vma comes with the switch to the user page table.

Between this commit and commit 6, copyin and copyout still walk the user page table and may allocate lazy pages through vmfault without mirroring them. Nothing reads the kernel page table’s user part yet, so this does no harm; commit 6 removes that path for the current process. (The state is reasoned: a page fault from user mode leaves interrupts off, and no lock is held.)

Step 12 of 18 · commit 4: Add copy loops that use user addresses with SUM set

The copy loop, with SUM set for exactly its duration

ucopy(dst, src, n) is seven instructions per byte, between csrs sstatus, t0, which sets bit 18 (SUM), and csrc sstatus, t0, which clears it. The constant comes from an .equ, since riscv.h’s SSTATUS_SUM sits inside #ifndef __ASSEMBLER__; commit 4 adds SSTATUS_SUM and SSTATUS_MXR there for the C code.

gdb, an early copy in sumtest (pipe() storing a file descriptor at 0x6e48):

at ucopy:          sstatus 0x200000022   satp 0x8000000000087f10   noff 0
after csrs:        sstatus 0x200040022

The only difference is 0x40000. dst is a plain user address, 0x6e48; with sumtest’s kernel page table in satp and SUM set, sb t1, 0(a0) stores straight into its page.

The loop is a leaf: no stack frame, no use of ra, nothing saved. That is what will let commit 5 abandon it halfway through and return from it anyway.

Step 13 of 18 · commit 4: Add copy loops that use user addresses with SUM set

Strings, and where a failed copy resumes

ucopystr copies up to and including a '\0', at most max bytes, and returns 0 if it copied the '\0', -1 if it ran out. It has two exits, and both clear SUM. Forget one and SUM stays on for whatever the hart does next: clinic 5.

ucopyend marks the end of the code whose faults the kernel may forgive. ucopyfail, after it, is where such a fault resumes: clear SUM, return -1. Since neither loop touched sp or ra, its ret returns to whoever called ucopy or ucopystr, with -1, as if the loop had returned it.

Step 14 of 18 · commit 5: Recover from page faults in user copies

kerneltrap learns to forgive one kind of fault

sumtest lazy reads 6 bytes from a pipe into p + PGSIZE + 10, an sbrklazy page nobody has touched. piperead copies one byte at a time with pi->lock held; the first sb faults. gdb at line 160:

scause 0xf   sepc 0x8000593c (the sb in ucopy)   stval 0x800a
saved sstatus 0x200040100 (SUM set)   live sstatus 0x200000100 (SUM cleared)
noff 1, intena 1, p->sz 40960

Line 154 cleared SUM first: from here on, nothing on this hart may use user memory until the copy resumes. Then the new branch: a load or store page fault whose sepc lies between ucopy and ucopyend. uvmfault maps a zeroed page at 0x8000 in both page tables, sfence.vma makes sure the retry cannot see a stale “invalid”, and the function returns. w_sstatus(sstatus) at line 178 restores SUM, sret returns to the same sb, and the copy continues.

This fault was taken with pi->lock held and interrupts off. uvmfault only takes kmem.lock inside kalloc, never sleeps, and so is safe here: the same reasoning that allowed copyout to call vmfault before.

Step 15 of 18 · commit 5: Recover from page faults in user copies

A fault nobody can fix

sumtest bad pointers reads README into its stack guard page, 0x5000. The address is below p->sz, so the range check lets it through; the guard page has no PTE_U and was never mirrored, so the sb faults. gdb: scause 0xf, sepc 0x8000593c, stval 0x5000, noff 0.

uvmfault → vmfault refuses, because the page is mapped in the user page table (ismapped). So line 163 sets sepc to ucopyfail. gdb’s next stop is there, with the stack the hardware left behind:

#0  ucopyfail () at kernel/uaccess.S:65
#1  copyout (..., dstva=20480, ..., len=16) at kernel/vm.c:440
#2  either_copyout (...)
#3  readi (..., dst=20480, off=0, n=16) at kernel/fs.c:526

readi sees -1 and returns -1; read fails. A store into text (stval 0x116, the code of fail() in sumtest) ends the same way.

Everything else that is not a device interrupt still reaches the panic at line 168: a fault outside the copy loops is a kernel bug, and the kernel says so.

Here readi holds the inode’s and the buffer’s sleep-locks, which do not count in noff: noff is 0, and interrupts are off only because this is a trap.

Step 16 of 18 · commit 6: Copy user memory directly in copyin, copyout, copyinstr

copyout uses the user's address

ulen returns how many of the len bytes at va lie below sz. It compares len > sz - va (after checking va < sz), so a huge len cannot overflow into a small sum. copyout for the current process: copy those bytes with ucopy, and fail if they were not all of them. No walk, no memmove, no physical address.

Whether pagetable is the current process’s decides the path. kexec is the only caller with another page table; it keeps the old loop below line 445, which is now reached only for a page table that is not in satp.

The state shown is copyin's, the twin a few lines below, which gdb recorded from pipewrite in sumtest copy: one byte per call from 0x2000, 0x2001, …, with pi->lock held (noff 1, intena 1) and satp 0x8000000000087f10. pipewrite calls copyin once per byte: 100 calls for a 100-byte write, each now paying for the myproc at line 436 and two CSR writes. The measure section shows what that costs.

Step 17 of 18 · commit 6: Copy user memory directly in copyin, copyout, copyinstr

copyin and copyinstr have only one path

Every caller of copyin and copyinstr (fetchaddr, fetchstr, pipewrite, either_copyin) passes the current process’s page table, so the software walk is gone from both; a call with any other page table now panics instead of quietly doing the wrong thing.

copyinstr passes ulen(srcva, max, psz) as the limit: a string may not run past p->sz. If the '\0' is not found before that limit, ucopystr returns -1, as the old loop did. And sumtest lazy opens a name inside an untouched lazy page: the first lbu in ucopystr faults, commit 5 maps the page, and the name turns out to be "", the current directory.

Commit 6’s message names the one behavioural difference: the old copies were page-granular, so the bytes between p->sz and the end of its page were readable; now the limit is p->sz itself. Copying the valid prefix before failing keeps usertests partial_write, which writes 2 bytes of which only the first is valid, passing.