Step 1 of 18 · commit 1: Reserve two user pages below the trapframe

Two new pages at the top of the address space

The story of this tour: the machine boots on three harts, you type vdsotest, the shell (pid 2) forks pid 3, which execs vdsotest; vdsotest forks children that read their pid, store to the pages and are killed, and are reaped. The states come from gdb runs on the finished branch (ext/10-vdso, 8 commits), started halted with breakpoints set first.

Commit 1 is a contract. User code must find the pages without asking, so their addresses are compile-time constants that both the kernel and user/ulib.c include. Counting down from MAXVA (0x4000000000):

MAXHEAP names the heap’s new ceiling. The structs are what the pages contain; the #ifndef __ASSEMBLER__ guard matters because kernel/trampoline.S:14 includes this header and the assembler does not understand C structs (GCC defines __ASSEMBLER__ for .S files).

Step 2 of 18 · commit 1: Reserve two user pages below the trapframe

The heap stops below the new pages

Two places enforce the heap’s ceiling: the lazy branch here, and growproc for eager growth and shrinking (kernel/proc.c:243, changed the same way). Before this commit the heap could grow to TRAPFRAME; now it stops at MAXHEAP = USHARED.

If p->sz could cover the new pages, three things would break (clinic 6): uvmalloc would try to map over them (panic: mappages: remap), sbrk(-n) would unmap and free them, the shared page included, and the kernel’s own reads, which commit 5 limits to the process’s memory below p->sz, would accept them. User stores are not among the three: vmfault's ismapped test refuses those even without the ceiling.

The state is reasoned from the code, not recorded: vdsotest’s ceiling check runs in a child that calls sbrklazy in 1 GiB steps until p->sz is exactly 0x3fffffc000, then sbrklazy(1), which line 60 refuses. A system call runs with interrupts on (after usertrap's intr_on) and no lock held: p->sz is private to the running process.

Step 3 of 18 · commit 1: Reserve two user pages below the trapframe

The one test that knew the old ceiling

lazy_sbrk walks the heap to the very top in 1 GiB lazy steps, maps the last page eagerly and checks that one more byte is refused. It names the ceiling by value: the last heap page was TRAPFRAME - PGSIZE, which is now USYSCALL. The commit changes the expected value to MAXHEAP - PGSIZE (0x3fffffb000) and nothing else; the test still checks the same three things: that the heap reaches the ceiling, that the last page is zero-filled, and that sbrk(1) and sbrklazy(1) fail there.

Changing a test is a decision to make consciously. Here the behaviour “the heap may grow up to TRAPFRAME” is exactly what the lab has to give up, one page per fixed mapping. Every other test is unchanged, including lazy_copy, which will force commit 5.

Step 4 of 18 · commit 2: Give each process a usyscall page

allocproc gives every process its own page

You typed vdsotest; the shell (pid 2) forks on hart 1. allocproc has found an UNUSED slot, holds its p->lock (line 115), has taken pid 3 from allocpid and the trapframe from kalloc. Now the new page: one more kalloc (gdb: 0x87f51000), zeroed, and the pid written at offset 0.

Why zero it? kalloc fills pages with 0x05 junk (kernel/kalloc.c:80); the user will see the whole page, and zeroes are a better promise for the bytes after pid. No kernel data can leak through it either way, since nothing else is ever stored there.

The pid can be written once and forgotten: it never changes while the slot is in use. If kalloc fails, freeproc undoes whatever was allocated so far (it tests each pointer before freeing it).

gdb recorded noff 1, intena 1, SIE 0: the one lock is the new process’s p->lock, and the intr_on in usertrap had turned interrupts on before acquire saved that in intena.

Step 5 of 18 · commit 2: Give each process a usyscall page

freeproc frees it, and only freeproc

Jump ahead: pid 4, vdsotest’s first child, stored to USYSCALL, was killed and is a zombie. vdsotest (pid 3) reaps it in kwait on hart 0, holding wait_lock and the zombie’s p->lock (gdb: noff 2, intena 1), and freeproc releases its resources.

The usyscall page is freed right next to the trapframe, with the same pattern: free if allocated, then clear the pointer. Recorded: pid 4’s page was 0x87f47000.

This is the only place the per-process page is freed. Page tables will map it (commit 3) but never free it. Its life is the slot’s life, from allocproc to freeproc, and the order here does not matter: the zombie is not running, and nothing else uses its page table, which proc_freepagetable on line 174 tears down next.

Step 6 of 18 · commit 3: Map the usyscall page read-only into user space

proc_pagetable maps it read-only

Back in the fork of pid 3: allocproc calls proc_pagetable for the child’s page table (0x87f47000 in the recorded run). Three fixed pages now, top down: the trampoline (R|X, no U), the trapframe (R|W, no U), and the usyscall page (R|U).

The flags are the whole design. U: a user-mode access is allowed at all (the other two pages deliberately lack it; only S-mode code on the trampoline uses them). R: loads succeed. No W: a user store faults (scause 15), vmfault declines because the address is above p->sz, and the process is killed. No X: the page cannot be executed.

The error path unmaps what was mapped before, in reverse order, then frees the page-table pages with uvmfree(pagetable, 0). It does not free the usyscall page: when proc_pagetable returns 0, allocproc calls freeproc (line 147), which frees it with everything else.

Step 7 of 18 · commit 3: Map the usyscall page read-only into user space

exec gets the page for free

Same lines, second caller. pid 3 now runs on hart 2 and calls exec("vdsotest"). kexec builds the new image’s page table with this very function (kernel/exec.c:56), so the new table (0x87f21000) maps USYSCALL to the same physical page, p->usyscall = 0x87f51000, holding pid 3. Mapping fixed pages here, rather than in allocproc, is what makes exec work; clinic 5 maps the page in allocproc instead, and the first exec’d program dies at its first ugetpid().

State: no spinlock (gdb: noff 0, SIE 1), but kexec holds the executable’s inode sleep-lock from ilock (kernel/exec.c:46) until iunlockput at line 79, and it is inside a file-system transaction (begin_op). Sleep-locks do not turn interrupts off, so a timer interrupt may preempt pid 3 here.

For a moment, two page tables map 0x87f51000: the old one (0x87f47000, still in p->pagetable) and this new one.

Step 8 of 18 · commit 3: Map the usyscall page read-only into user space

proc_freepagetable unmaps it, without freeing

kexec has committed: p->pagetable is the new table and the name is vdsotest. Now it frees the old table (kernel/exec.c:138). gdb recorded this on hart 0, while the previous step ran on hart 2: pid 3 gave up its hart in between (most likely sleeping on a disk read of the ELF file) and was resumed by another hart’s scheduler.

The old table’s top entries, read by gdb at this line (on the finished branch, so USHARED is there too):

All three fixed pages are unmapped with do_free = 0: the trampoline is kernel code, the trapframe and the usyscall page belong to the slot and are still mapped by the new table. Then uvmfree frees [0, sz) and the page-table pages. Without line 236, freewalk finds the usyscall leaf at index 509 and panics (clinic 3); with do_free = 1, the page the new image is reading goes back on the free list (clinic 4).

Step 9 of 18 · commit 4: Share one ticks page with every process

One page for the whole system, allocated at boot

The second page holds something that changes: the tick count. It is the same for every process, so one physical page serves all of them. trapinit runs once, on hart 0, in main after kinit (so kalloc works) and before userinit (so the first page table can map it). gdb: ushared = 0x87f59000, paging on (the kernel page table), interrupts off, still on the boot stack.

Nobody owns this page. It is never freed, and that is the one rule to keep in mind when writing its unmap in commit 4’s change to proc_freepagetable (do_free = 0).

Why kalloc and not a static variable? A variable smaller than a page would share its page with other kernel data, and mapping that page with PTE_U would show that data to every process. A page from kalloc contains nothing else.

Step 10 of 18 · commit 4: Share one ticks page with every process

clockintr publishes ticks

Only hart 0 counts ticks. One line is added inside the existing critical section: the new value goes to the shared page right after ticks++. gdb stopped here with ticks 1, 2, 3 during boot, each time taken in hart 0’s scheduler loop (no process: the interrupt landed in scheduler's intr_on window), noff 1, intena 0.

In this build the line is one sw a5,0(a4) at 0x8000267c: a single naturally aligned 32-bit store. That is what makes a lock-free reader safe: under RVWMO an aligned word access is single-copy atomic, so a reader sees the old value or the new one, never a mix. tickslock protects ticks against sys_uptime and sys_pause; it does not protect the copy from user readers, who take no lock, and it does not need to.

The copy lives at the moment release runs its fence rw,w: everything before it, including this store, is visible to any hart that later acquires tickslock. That gives the first half of vdsotest’s uptime() <= uuptime() <= uptime(). The second half holds too: a reader that saw the value stored inside some critical section of clockintr makes its next sys_uptime call afterwards, and that call’s acquire of tickslock comes after the release ending that section, so it reads ticks at least as large.

Step 11 of 18 · commit 4: Share one ticks page with every process

The shared page in every page table

The same pattern as USYSCALL, one page lower, but with a global physical address: every page table ever built maps ushared. gdb read the USHARED PTE in every page table it looked at (pids 1, 2, 3 and vdsotest’s children): always physical page 0x87f59000, and 0x21fd6413 (flags V R U) as the kernel wrote it. (The state shown is the fork of pid 3 a few lines after the previous fork step; it is reasoned, not a separate stop.)

The error path now unwinds four mappings. And proc_freepagetable (line 248) unmaps the shared page with do_free = 0 and a comment, because this is the one place where a slip of one character frees a page that the whole system is using.

One more detail gdb showed: after vdsotest first called uuptime(), its USHARED PTE read 0x21fd6453: the hardware had set A (0x40). This tree enables hardware A/D updates in kernel/start.c:41 (Svadu extension (A and D bits)), so the accessed bit is set per page table, even for a page that is shared.

Step 12 of 18 · commit 5: Keep system calls out of the read-only pages

copyin keeps system calls below p->sz

From commit 3 on (one PTE_U page at 0x3fffffd000 is enough), usertests -q failed with test lazy_copy: write succeeded. The kernel reads user memory through walkaddr, which asks only for V and U; copyout adds a software PTE_W test, but copyin adds nothing. So write(fd, USHARED, n) copied the shared page into a file, and lazy_copy lists exactly 0x3fffffc000 and 0x3fffffd000 as addresses that must fail.

The new lines apply, page by page, the rule that fetchaddr (kernel/syscall.c:15) and vmfault already follow: a system call may touch only the process’s memory, below p->sz (precisely: no page that starts at or above it). gdb recorded the refusal in vdsotest’s write() from ushared check: va0 0x3fffffc000, psz 0x5000, len 8, called from writei through either_copyin. copyinstr gets the same test, so open((char *)USYSCALL, ...) fails too.

State: filewrite holds the inode’s sleep-lock and writei the buffer’s (kernel/fs.c:560 copies into bp->data); neither is a spinlock, so interrupts stay on (gdb: noff 0, SIE 1). The test returns before anything is copied, and write returns -1.

Step 13 of 18 · commit 6: Add ugetpid and uuptime to the user library

ugetpid: a system call that is a load

The whole feature, seen from user mode. ulib.c includes kernel/memlayout.h for the address and the struct, and the function compiles to (from user/vdsotest.asm):

970: addi sp,sp,-16      978: lui  a5,0x4000
972: sd   ra,8(sp)       97c: addi a5,a5,-3      # 0x3fffffd
974: sd   s0,0(sp)       97e: slli a5,a5,0xc     # 0x3fffffd000
976: addi s0,sp,16       980: lw   a0,0(a5)      # the pid
                         982..988: restore, ret

gdb single-stepped it: 12 instructions from entry to ret, all in U-mode, with satp on the user page table throughout. The lw at 0x980 is the instruction that faulted with scause 0xd in clinics 1 and 5. Compare getpid(): li a7,11; ecall; ret in user mode, and 1,103 instructions between ecall and sret.

No volatile here: the pid never changes, so a compiler that keeps it in a register is right.

Step 14 of 18 · commit 6: Add ugetpid and uuptime to the user library

uuptime: volatile, because the kernel writes behind your back

Same shape, different promise. The value at USHARED changes ten times a second without this program doing anything, and C has no way to know that unless the access is volatile. Without it, a caller that inlines uuptime into while (uuptime() == t0) ; could load once and spin forever. With it, every call performs a fresh lw, one load, like ugetpid.

The load is a plain 32-bit lw of an aligned word, matched by the kernel’s single sw: single-copy atomic, no lock. A user program could not take a kernel spinlock anyway; the only synchronization available across the user/kernel boundary here is the atomicity of one memory access.

Step 15 of 18 · commit 7: Add vdsotest

A store to the page, from the test's point of view

vdsotest runs each dangerous check in a child (inchild) and decides from the exit status alone: -1 means the kernel killed it (kexit(-1) after setkilled), 0 means the store survived and the function returned. So the final ALL OK does not depend on reading the console; the usertrap() lines are printed by the kernel for each expected kill.

pid 4 executes sw at 0x14 (inside store_usyscall), with the address 0x3fffffd000. The hart finds the PTE: V, R, U set, W clear. The store does not happen; a store page fault is raised instead.

Step 16 of 18 · commit 7: Add vdsotest

usertrap: vmfault refuses, the process dies

gdb, at the kill: scause 0xf, stval 0x3fffffd000, sepc 0x14, hart 0, noff 0, SIE 0 (a fault leaves interrupts off; only the system-call branch calls intr_on).

The fault branch (lines 77-79, unchanged by this lab) calls vmfault with p->sz = 0x5000. gdb stopped inside it at the first test: va 0x3fffffd000 >= psz 0x5000, return 0. So the else branch prints the two lines and setkilled marks the process; line 87 calls kexit.

The same run shows the worst case. In the ceiling check (pid 6), p->sz was raised to the maximum, 0x3fffffc000, before the store; gdb recorded vmfault declining va 0x3fffffd000 against psz 0x3fffffc000. Because the ceiling is USHARED, no process can make p->sz cover these pages, but the refusal does not depend on that: vmfault's second test, ismapped, refuses any mapped page. A probe on a kernel without the ceiling (clinic 6) grew p->sz over both pages and its store was still killed.

Step 17 of 18 · commit 7: Add vdsotest

Fork, exec, and twenty children at once

forktest: the child compares ugetpid() with getpid() and with the parent’s pid; the parent checks its own page afterwards. exectest: a child execs vdsotest exec, whose main checks ugetpid() == getpid() in the new image and exits with the answer. Together they cover both callers of proc_pagetable: allocproc and kexec.

manytest forks 20 children that run on all three harts at once, each loading its own USYSCALL 100,000 times. Every child has the same virtual address and a different physical page; nothing is shared, so nothing can interfere. (In the recorded runs, gdb saw vdsotest’s earlier children, pids 4 to 7 from the read-only, ceiling and fork checks, get pages 0x87f47000, 0x87f44000, 0x87f23000 and 0x87f27000: pages are recycled as children are reaped. The manytest children’s pages were not recorded.)

Run order in the test matters for debugging: pid first, so a missing mapping (clinics 1 and 5) kills vdsotest before it prints anything at all.

Step 18 of 18 · commit 8: Measure in vdsotest what the trap costs

Measuring the trap

userrdtime first: U-mode may not read time here (only mcounteren.TM is set, in kernel/start.c:62), and the child is killed with scause 0x2. So timeit counts calls per tick, using uuptime() as its clock so that the loop adds no system calls of its own.

Recorded on 3 harts (vdsotest time, after usertests -q):

About 500 times faster. The instruction counts explain a factor of about 74 (1,109 versus 15 per loop iteration, see Measure); the remaining factor of about 7 is time per instruction. Removing the four sfence.vma (an experiment only) made getpid about a third faster, so QEMU’s translation-cache flushes are a large share of it; the rest was not measured. On real hardware the ratio is different, but the cost has the same parts: the trap, the register save, the page-table switch and the work around it. That is the price this lab stops paying for two values the process may simply know.