A shared read-only page: system calls without a trap
getpid() asks the kernel for one integer it already knows. To get it, the process executes
ecall, the hart traps, uservec saves 31 registers, the kernel switches page tables,
usertrap and syscall run, and the whole trip is undone on the way back. In this tree
that is 1,103 instructions after the ecall, two writes to satp and four sfence.vma
(counted with gdb). In this lab you map one extra page into every process, at a fixed
address just below the trapframe, with the process’s pid in it, readable but not
writable from user mode. ugetpid() then becomes one load: 12 instructions, no trap.
A second page, the same physical page in every process, carries a copy of the kernel’s
ticks, written by clockintr and read with no lock by uuptime(). That raises the
question every shared-memory design must answer: can a reader see a half-written value?
The code is small (about 70 lines of kernel, a third of them comments), but placing a page
at the top of the user address space touches more than you might expect. What else in the
kernel already decides what lives near the top of a user address space? Who creates a page
table, who throws one away, and how often does that happen in the life of one process? Does
the kernel itself obey a read-only PTE when a system call touches user memory? Answering
those is the lab. On QEMU the result is about 500 times faster per call.
The top of a user address space: TRAMPOLINE (no PTE_U, used only in S-mode), the trapframe page below it, and now two pages that user code may read; how a fixed virtual address becomes a contract between the kernel and the user library.
What the PTE permission bits do to each kind of access, and what happens in this tree, where store faults already mean lazy allocation, when a user program stores to a page it may only read.
How long a page lives compared with the page tables that map it, and what exec, which builds a whole new page table, does to a page that must outlive it.
Whether the kernel’s own copies to and from user memory obey the same PTE bits as the hardware does, and what that means for a page user code may read but should not hand to a system call.
When a value shared between harts can be read with no lock (one writer, one naturally aligned 32-bit word, a volatile read) and when it cannot (two values that must agree).
What a trap costs, measured two ways: instructions counted with gdb, and calls per tick timed from user mode, and why user code here cannot read the time CSR.
git clone https://github.com/ShowMeTheStack/xv6-riscv-labs
cd xv6-riscv-labs
git checkout -b my-vdso 06aad25 # start your own
git diff 06aad25 origin/ext/10-vdso # only when you want the answer
1. The spec
Behaviour. Every process has two extra pages mapped at fixed addresses just below the
trapframe, both readable and not writable from user mode:
address
name
contents
physical page
0x3fffffd000
USYSCALL
struct usyscall { int pid; }
one per process
0x3fffffc000
USHARED
struct ushared { uint ticks; }
one for the whole system
The user library gains two functions that read them without a system call:
int ugetpid(void); // == getpid()
int uuptime(void); // == uptime(), give or take a tick in flight
A forked child reads its own pid; an exec’d image reads the same pid as before exec.
The copy of ticks changes by itself, once per tick, in every process.
A user store to either page kills the process, like a store to program text. Nothing may
turn that store into a lazily allocated page.
The heap may not grow into the pages: sbrk and sbrklazy stop at USHARED.
What must not change. System calls behave as before for every address below p->sz.
A system call handed a pointer into the new pages fails, as it did when nothing was mapped
there (usertests lazy_copy checks read and write on exactly these addresses). No page
leaks; the shared page is never freed. usertests -q must print ALL TESTS PASSED on 3
harts. (One test, lazy_sbrk, checks the old heap ceiling by its exact value; the
reference branch updates that one expected value, see the reveal.)
The test program, vdsotest, prints one line per check:
$ vdsotest
vdsotest: pid: OK
vdsotest: uptime agrees: OK
vdsotest: uptime advances: OK
usertrap(): unexpected scause 0xf pid=4
sepc=0x14 stval=0x3fffffd000
vdsotest: usyscall read-only: OK
usertrap(): unexpected scause 0xf pid=5
sepc=0x2e stval=0x3fffffc000
vdsotest: ushared read-only: OK
vdsotest: read() into usyscall fails: OK
vdsotest: write() from ushared fails: OK
vdsotest: pid unchanged: OK
usertrap(): unexpected scause 0xf pid=6
sepc=0xd2 stval=0x3fffffd000
vdsotest: heap ceiling: OK
vdsotest: fork: OK
vdsotest: exec: OK
vdsotest: 20 children: OK
vdsotest: ALL OK
pid: ugetpid() == getpid().
uptime agrees: uptime(), then uuptime(), then uptime() again; the middle value
lies between the other two. uptime advances: after pause(2), uuptime() is at least 2
larger.
usyscall / ushared read-only: a child stores to the page; it must be killed (exit
status -1), not survive (status 0). The usertrap() lines are those kills, expected; the
test checks each child’s status itself.
read() into usyscall fails, write() from ushared fails, pid unchanged: system calls
refuse the pages in both directions.
heap ceiling: a child grows its heap lazily to the limit; sbrklazy(1) more must fail,
and a store to USYSCALL with p->sz at its maximum must still kill it.
fork, exec: a child, and a child that execs vdsotest exec, read their own pid.
20 children: 20 children on 3 harts each read their own pid 100,000 times.
vdsotest time measures: it reports whether user mode may execute rdtime, then how many
getpid, ugetpid, uptime and uuptime calls fit into 20 ticks.
2. Think first
Answer each question in your head (or on paper) before opening a hint. Hints get more specific; the reference answer comes last.
1What does getpid cost, and which part of it is necessary?
Trace getpid() from the user stub to the return. List what the hardware and the kernel do
on the way in and on the way out. Then ask: which of those steps is needed to produce the
answer, and what would user code need in order to find the pid by itself, with no trap?
Commit to an answer before reading the hints: could the kernel give the process its pid
once, and keep it correct afterwards?
The only work that produces the answer is one load of p->pid in sys_getpid. Everything else exists to cross the boundary between user mode and the kernel safely. A user load can reach any page its page table maps with PTE_U.
Hint 3.
Put the pid in a page of its own, filled in by the kernel when the process is created, and map that page into the process’s own page table where user code can read it. A pid never changes for the life of a process, so the kernel never has to update it.
The reference design
On the way in: ecall switches the hart to S-mode and jumps to uservec on the
trampoline page page; uservec saves all 31 user registers in the trapframe, loads the
kernel stack, satp and tp, and jumps to usertrap, which saves sepc, checks
killed (taking p->lock), turns interrupts on and calls syscall. sys_getpid
finally loads p->pid. On the way out, usertrap checks killed again,
prepare_return sets stvec, sstatus and sepc, and userret switches satp back
and restores the 31 registers before sret.
Counted with gdb on the reference branch (see Measure): 1,103 instructions from the first
instruction of uservec to sret, with 2 csrw satp, 4 sfence.vma and one
fence.i. 392 of them are in mycpu, 144 in push_off and 118 in pop_off: the
bookkeeping behind myproc (called 4 times) and the two acquisitions of p->lock in
killed. Ten are in sys_getpid.
The answer itself needs none of that. The pid is fixed from allocproc to
freeproc, so the kernel can write it once into a page and map the page into the
process’s own page table with PTE_U. A user load then reads it: ugetpid() compiles
to lui, addi, slli and one lw: 12 instructions from its entry to its ret.
Values that change, like the tick count, need the kernel to keep the page up to date
(a later question).
Check yourself
1warm-upType a number
In one getpid() round trip on this kernel, from ecall to the instruction after it,
how many times is satp written?
gdb counted 1,103 instructions from the first instruction of uservec to sret for
one getpid. Which part of that work does ugetpid() keep?
2Where in the address space?
User code must find the page without asking the kernel, so its address must be fixed and
known when the user library is compiled. Look at the user address space (Tour 25: A user address space):
which addresses are already taken, and by what? Pick an address for the per-process page,
and check it against everything else that can place memory in a user address space. What
else in the kernel has to learn about your choice?
Text, data and the stack sit at the bottom and are placed by kexec; the heap grows up from there, and today it may grow all the way to TRAPFRAME. A fixed page anywhere in that range collides with a large enough heap.
Hint 3.
Take the pages directly below TRAPFRAME (TRAPFRAME - PGSIZE, then one more for the shared page) and lower the heap’s ceiling to the lowest of them, in both places that enforce it.
The reference design
The reference uses USYSCALL = TRAPFRAME - PGSIZE = 0x3fffffd000 and, one page lower,
USHARED = 0x3fffffc000. The top of the address space is already reserved for
kernel-managed pages (TRAMPOLINE, TRAPFRAME), and the bottom belongs to the
program. Between them only the heap can grow, and it used to be allowed to grow up to
TRAPFRAME. So the new pages lower the ceiling: MAXHEAP = USHARED, checked in
growproc and in sys_sbrk's lazy branch.
Forgetting the ceiling is clinic 6. Lazily, the heap’s p->sz could cover the new pages;
eagerly, uvmalloc would try to map a page where one is already mapped. usertests lazy_sbrk does exactly that: it grows the heap to the ceiling and then asks for one more
byte, and the kernel panics with mappages: remap. Worse, sbrk(-n) would then call
uvmdealloc over the pages and free them, the shared page included.
The ceiling is not what keeps user stores out: vmfault refuses a fault on these pages
twice over, because the address is at or above p->sz (kernel/vm.c:463) and because
the page is already mapped (kernel/vm.c:466); the second test refuses even if p->sz
covered the pages (clinic 6 shows it). What the ceiling does is keep p->sz from covering
them at all. Otherwise the kernel’s own reads would treat them as process memory (a later
question), eager sbrk would panic in mappages, and sbrk(-n) would free the shared
page while every process maps it.
One existing test encodes the old ceiling: lazy_sbrk expects the last heap page at
TRAPFRAME - PGSIZE (user/usertests.c:2793). The reference changes that expected value
to MAXHEAP - PGSIZE; it is the only change to usertests.
Check yourself
1warm-upType a number
MAXVA is 1L << 38, TRAMPOLINE is MAXVA - PGSIZE and TRAPFRAME is
TRAMPOLINE - PGSIZE. What is USYSCALL = TRAPFRAME - PGSIZE, in hex?
kernel/memlayout.h
46// map the trampoline page to the highest address,
You map the two pages but leave the heap ceiling at TRAPFRAME in growproc and
sys_sbrk. usertests lazy_sbrk grows the heap lazily to 0x3fffffb000, adds one
page eagerly with sbrk(4096) so that p->sz is 0x3fffffc000, then calls
sbrk(1). What happens?
Choose the permission bits for the two new PTEs. Then predict, step by step, what happens
when a user program executes *(int *)USYSCALL = 1234;. Which scause? Which kernel
function is asked to deal with it first, and what must it decide? Could it end up giving
the process a fresh writable page at that address?
On every user access the hardware checks the PTE: V and U always, then R for a load, W for a store, X for a fetch. A failed store is a store page fault, scause 15, whatever the reason. In this tree usertrap gives every load or store page fault to vmfault before giving up.
The PTEs get PTE_R | PTE_U (plus PTE_V, which mappages adds). U makes the page
reachable from user mode, R lets loads succeed, and the missing W and X forbid
stores and execution. Recorded on the branch, pid 3’s page-table entry for
USYSCALL is 0x21fd4413: physical page 0x87f51, flags 0x13 = V|R|U.
The store: the hart finds W clear and raises a store/AMO page fault, scause = 15, with
stval = 0x3fffffd000 and sepc at the store. uservec and usertrap run as for
any trap; the fault branch calls vmfault (kernel/trap.c:71). Its first test is
va >= psz, and here va is 0x3fffffd000 while p->sz was 0x5000 in the recorded
run, so it returns 0 at once. usertrap prints unexpected scause 0xf and kills the
process.
Could vmfault ever allocate a page there? Only if both of its tests passed: the
address below p->sz (impossible once the heap’s ceiling is USHARED), and the page not
mapped (never true: the page is always mapped). Either test alone is enough. The ceiling test in vdsotest checks the worst case: with p->sz at its
maximum, 0x3fffffc000, gdb recorded vmfault declining va 0x3fffffd000 against
psz 0x3fffffc000, and the child was killed.
With PTE_W left on (clinic 2) the store simply succeeds: any process can rewrite the pid
that its own library reports, and, worse, the shared page, which every other process
reads.
Check yourself
1solidDecode the bits
gdb read this PTE for USYSCALL in vdsotest’s page table, after the program had
called ugetpid(). Decode the flag bits.
Value: 0x21fd4453
2solidChoose one
vdsotest’s child executes *(volatile int *)USYSCALL = 1234; with p->sz =
0x5000. Which statement describes what the kernel does?
The per-process page needs a physical page and a mapping. Decide when the physical page is
allocated, when the pid is written into it, when it is mapped, unmapped and freed. Walk
the life of a process that the shell forks and that then execs a program: does your
design give the exec’d program the page? What happens to the page table exec throws
away?
Hint 1.
The trapframe is the model: another per-process page at a fixed address near the top of the user address space. Find every line that touches p->trapframe or TRAPFRAME in proc.c and exec.c, and note which function each one is in.
Hint 2.
Two lifetimes: the physical page must live as long as the process slot is in use (fork to wait), but exec builds a whole new page table and discards the old one (kernel/exec.c:138), and freewalk panics if a page table still holds a leaf when it is freed (kernel/vm.c:276).
Hint 3.
Allocate the page (and write the pid) next to the trapframe’s allocation, free it next to the trapframe’s free. Map it in the one function that creates every user page table, so fork and exec both get it; unmap it, without freeing, in that function’s mirror.
The reference design
Like the trapframe, the page has two separate lifetimes:
physical page
mapping
created
allocproc, right after the trapframe, which also writes p->pid into it
proc_pagetable is called in two places: by allocproc for a new process, and by
kexec for the new image (kernel/exec.c:56). Mapping the page there gives both the
page automatically. During exec two page tables map the same physical page for a
moment; when kexec commits, proc_freepagetable removes the mapping from the old one
(kernel/exec.c:138). That unmap must not free the page, which the new image is using.
Recorded on the branch: sh (pid 3) built the new table on hart 2 and dropped the old
one on hart 0, both mapping physical page 0x87f51000.
What goes wrong otherwise:
Map it somewhere only allocproc reaches (clinic 5): the first program exec’d by
the shell has no page, and its first ugetpid() is a load fault.
Forget to unmap it (clinic 3): uvmfree only removes the pages below sz, and
freewalk finds a leaf PTE at index 509 and panics with freewalk: leaf, at the
very first exec, during boot.
Unmap it with do_free = 1 (clinic 4): exec frees a page the process still maps, and
freeproc frees it a second time. The free list is corrupted.
Check yourself
1solidPut in order
The shell forks pid 3, which execs vdsotest, which exits and is reaped by the
shell. Put these events for pid 3’s usyscall page in order.
proc_freepagetable unmaps it from the old page table, without freeing it
allocproc allocates the page and writes 3 into it
proc_pagetable maps it into the child’s first page table
freeproc, in the shell’s wait, frees the page and removes the last mapping
kexec’s call to proc_pagetable maps the same page into the new image’s page table
2deepChoose one
You add uvmunmap(pagetable, USYSCALL, 1, 0) to proc_pagetable's error paths but
forget it in proc_freepagetable. When does the kernel first notice?
After your answer to the previous question, check two cases by reading code, not by
assumption. A forked child must see its pid, not its parent’s: is there any way the
parent’s page, or its contents, could end up in the child? And after exec, could the new
image see a stale value?
uvmcopy copies the pages in [0, sz) only. Everything above sz in the child’s page table was put there by proc_pagetable when allocproc built it.
Hint 3.
The child’s page is new and was filled in by allocproc with the child’s pid. exec keeps the same struct proc and therefore the same page and the same pid.
The reference design
kfork calls allocproc first, which allocates a fresh page and writes the child’s
pid into it (gdb recorded pid 3’s page at 0x87f51000 while the shell, pid 2, had
0x87f52000), then maps it in the child’s new page table. uvmcopy copies only
[0, p->sz) (kernel/proc.c:271), far below USYSCALL, so the parent’s page is never
copied or shared. That is also why the mapping must not be made by copying the parent’s
PTE: the child would then read the parent’s pid.
exec does not create a process; kexec reuses p, so p->usyscall and the pid in it
are unchanged, and the new page table maps the same page. vdsotest’s fork and exec
checks confirm both: the child, and a child that execs vdsotest exec, compare
ugetpid() with getpid() and exit 0.
The shared page is the opposite case on purpose: every page table maps the same
physical page, so a forked child and its parent read the same ticks.
Check yourself
1solidTrue or false, and why
True or false: in the reference design, uvmcopy copies the parent’s usyscall page
into the child, and kfork then overwrites the pid in the copy.
Why?
6The kernel reads and writes user memory too
Your pages are mapped and read-only. Now a program passes their address to a system call:
read(fd, (char *)USYSCALL, 8) asks the kernel to write the page, and
write(fd, (char *)USHARED, 8) asks it to read it. The kernel does not use the user’s PTE
the way the hardware does. What happens to each call? Is either result a problem? Run
usertests -q at this point if you have built that far.
Hint 1.
The kernel copies with copyout and copyin. Both translate the user address with walkaddr (kernel/vm.c:122) and then use memmove on a physical address, through the kernel’s direct map of RAM.
Find the rule xv6 already applies to user pointers in other places (how does the kernel decide whether an address is part of the process’s memory?), and make the copy routines that read user memory apply it too.
The reference design
read into USYSCALL fails: copyout finds the page through walkaddr, then sees
that PTE_W is clear and returns -1. Good.
write from USHARED succeeds: copyin finds a valid PTE_U page and copies from it.
Reading a read-only page is not dangerous in itself, but it changes behaviour that a test
relies on. usertests lazy_copy lists 0x3fffffc000 and 0x3fffffd000 among
addresses that read and write must reject, because nothing used to be mapped there.
With the pages mapped, the test fails, from commit 3 on (recorded at commit 4):
$ usertests lazy_copy
usertests starting
test lazy_copy: write succeeded
FAILED
SOME TESTS FAILED
The fix states a rule the kernel already half-follows: a system call may only touch the
process’s memory, below p->sz. fetchaddr enforces it byte by byte and vmfault
for faults; the reference adds if (va0 >= psz) return -1; to copyin and
copyinstr. That test is page-granular: it refuses pages that start at or above
p->sz (below PGROUNDUP(p->sz) everything is as before, including the bytes between
sz and the end of its page). copyout needs no
change because its PTE_W test already refuses both pages. Every caller of copyin
passes the calling process’s own sz (even pipewrite, which names it pr,
kernel/pipe.c:96), so nothing below sz is affected.
(Linux makes the opposite choice: its vDSO pages may be passed to write. Either is
consistent; this tree’s tests encode the stricter one.)
Check yourself
1solidMatch the pairs
Before the copyin fix, match each access to the new pages with what happens.
7One page for everyone, read with no lock
uptime() returns ticks, which clockintr increments on hart 0 under tickslock, and
sys_uptime reads under the same lock. For uuptime() the kernel copies ticks into
one page shared by all processes, and user code reads it with no lock at all (it could
not take a kernel spinlock anyway). Where does the page come from, and who may free it?
Then the hard part: on three harts, can a reader see a value that was never written? Can
the compiler or the hardware make the read return something stale forever?
A RISC-V load or store of a naturally aligned 32-bit word is single-copy atomic: another hart sees the whole old value or the whole new one. But a compiler may keep a value it has already loaded in a register, unless the access is volatile (or atomic). And two separate words can be seen in any mix of old and new.
Hint 3.
Allocate one page at boot (after the allocator exists, before the first process), never free it, map it in every user page table, and in clockintr store the new ticks into it inside the existing critical section. Read it in user code through a volatile pointer.
The reference design
The page.trapinit runs on hart 0 during boot, after kinit and before
userinit; the reference allocates the page there with kalloc and zeroes it
(recorded: 0x87f59000). Every user page table maps that same physical page at USHARED.
Nobody owns it, so nobody frees it: proc_freepagetable unmaps it with do_free = 0.
Freeing it when one process exits would put a page on the free list that every other
process still maps and that clockintr still writes, ten times a second.
The write.clockintr adds ushared->ticks = ticks; right after ticks++, inside
tickslock. The lock is not needed against readers (they take none), but clockintr
already holds it and there is only one writer, hart 0. In this build the store is one
sw a5,0(a4) at 0x8000267c.
The read.uuptime() compiles to one lw. RVWMO makes an aligned 32-bit load or
store single-copy atomic, so a reader on hart 1 sees either the old count or the new
one, never two halves. Staleness is bounded too: the store becomes visible to other harts
in finite time, and each call of uuptime() loads again because the pointer is
volatile. Without volatile, a loop like while (uuptime() == t0) may be compiled
into one load followed by an endless loop (here uuptime is a separate function in
ulib.c, which hides the problem; inline it and it may appear). The strictly portable C
would use __atomic_store_n and __atomic_load_n with __ATOMIC_RELAXED.
When this is not enough. A single value is consistent by itself. Two values that must
agree (ticks and a timestamp of the last tick, or a 64-bit counter written as two 32-bit
halves) can be read half-updated. That needs a sequence counter: the writer increments it
before and after the update, and the reader retries if it saw an odd value or a change.
That is how the Linux vDSO publishes the time.
Ordering against uptime().vdsotest checks uptime() <= uuptime() <= uptime().
clockintr stores the copy before release, whose fence rw,w publishes it with
ticks; a later sys_uptime acquires tickslock after that release, so the first
uptime() is never ahead of the copy. Conversely, a value the reader saw was stored inside
a critical section, and the following sys_uptime acquires the lock after that
section’s release, so the second uptime() is never behind it. The check passed in every
recorded run.
Check yourself
1solidChoose all that apply
uuptime() reads the shared page with no lock while clockintr on hart 0 writes it.
Which statements are true for this tree on RISC-V?
2warm-upChoose one
proc_freepagetable unmaps the shared page. Which do_free argument is right, and
why?
8How do you measure the difference?
You want numbers: how long one getpid() takes versus one ugetpid(). The best clock is
the time CSR, which clockintr reads with rdtime. Can a user program execute
rdtime in this tree? If not, what clock can you use from user mode, and how many calls
must you make for the answer to be meaningful?
Each privilege mode needs its own permission: mcounteren lets S-mode read the counters, scounteren lets U-mode. A disallowed rdtime is an illegal instruction, scause 2.
Hint 3.
Use ticks. A tick is about 0.1 s (1000000 counts of the time CSR, which runs at 10 MHz on QEMU’s virt machine), so count how many calls fit into, say, 20 ticks, and read the clock with uuptime() so that the timing loop itself makes no system call.
The reference design
No. timerinit sets bit 1 (TM) of mcounteren so that S-mode may read time
(kernel/start.c:62), but nothing writes scounteren, so U-mode may not. vdsotest time checks it: its child executes rdtime and is killed with scause 0x2 (illegal
instruction) and stval=0xc01027f3, the instruction’s own encoding (rdtime a5).
So the measurement counts calls per tick: 1,000 calls at a time until uuptime() has
advanced 20 ticks (about 2 seconds). Results from a recorded run on 3 harts:
getpid() 175,000 calls (about 11,400 ns each), ugetpid() 88,831,000 calls (about
22 ns each). The resolution is one tick in 20, 5%, plenty for a 500-fold difference.
These are QEMU numbers. Counting instructions per iteration of the timing loop (the
loop’s own jalr, addiw, bnez included): 1,109 for getpid against 15 for
ugetpid, a factor of about 74. The remaining factor of about 7 is time per
instruction: QEMU spends far longer per instruction on the kernel path. Translation-cache
flushes are a large share of that: an experiment that removed the four
sfence.vma from the trampoline (an experiment only; real hardware needs them) cut
getpid by about a third, from about 11,700-12,300 ns to about 7,900-8,200 ns, with
ugetpid unchanged. We did not measure the rest. Real hardware has different ratios,
but a trap with two page-table switches is expensive everywhere.
Check yourself
1solidChoose one
A user program on this kernel executes rdtime a5 (as vdsotest time’s probe does). What happens?
Write the test first: copy the spec’s checks into user/vdsotest.c and add
$U/_vdsotest\ to UPROGS in the Makefile. Until the library functions exist it will not
link; that is fine, it tells you what to build.
Milestones, in an order that keeps the system bootable after each one.
The layout.USYSCALL, USHARED, the two structs and the heap’s new ceiling in
kernel/memlayout.h; use the ceiling in growproc and sys_sbrk; update the one
expected value in usertests lazy_sbrk. Guard the structs with #ifndef __ASSEMBLER__:
trampoline.S includes memlayout.h. Test: usertests -q.
The physical page. A struct usyscall *usyscall field in struct proc; allocate,
zero and fill it in allocproc, free it in freeproc. Test: usertests -q (the page
exists but nothing maps it; a leak would show in the free-page checks).
The mapping. Map it read-only in the function that builds user page tables, unmap it
in the one that frees them, and undo it in the error path. Test: boot. If the kernel
panics before the shell prompt, read clinic 3. From here until milestone 5, usertests -q fails at lazy_copy (write succeeded); that is expected.
The shared page. Allocate it in trapinit, update it in clockintr, map and
unmap it like the per-process page (but never free it).
The kernel’s copies. Run usertests -q: lazy_copy fails with write succeeded.
Make copyin and copyinstr refuse addresses at or above psz. Test: usertests -q.
The library and the test.ugetpid and uuptime in user/ulib.c, prototypes in
user/user.h. Test: vdsotest, then usertests -q, then vdsotest again.
Debugging advice. To catch anything during boot (clinic 3 panics before the shell
starts), start QEMU halted with make qemu-gdb (it adds -S and a gdb port of its own,
which it writes into .gdbinit), run ${TOOLPREFIX}gdb kernel/kernel in another
terminal, and set breakpoints before the first continue. TOOLPREFIX is your RISC-V
toolchain’s prefix, the same one xv6’s Makefile detects (riscv64-unknown-elf-,
riscv64-linux-gnu- or riscv64-elf-); set it with export TOOLPREFIX=riscv64-unknown-elf- or whichever you have. On Debian/Ubuntu/WSL,
gdb-multiarch also works as the debugger.
usertrap(): unexpected scause 0xd ... stval=0x3fffffd000 at the first ugetpid(): the
load faulted. Print the PTE. From a kernel breakpoint (for example on setkilled), walk
myproc()->pagetable for 0x3fffffd000 by hand: indices 255, 511 and 509 at levels 2, 1
and 0, each PTE’s physical page number shifted left by 12 to reach the next table (the
kernel’s direct map lets gdb read those physical addresses directly). No PTE means the page was not mapped in this page table (was it
exec’d?); a PTE without 0x10 means PTE_U is missing.
panic: freewalk: leaf while booting: some page above sz is still mapped when a page
table is freed. bt shows which free (kexec or freeproc); p i in the innermost
freewalk frame gives the index, 509 for USYSCALL, 508 for USHARED.
panic: mappages: remap from growproc: the heap reached the new pages.
Strange pids or a crash in kalloc: a page was freed while still mapped, or twice.
Break on kfree with the condition pa == <the page's address> and look at each bt.
To see user code from gdb, set breakpoints on user addresses from user/vdsotest.asm
and condition them (the same address exists in every program); x/i $pc shows the
instruction.
4. Debugging clinic
Each of these bugs was put into the reference solution on purpose and run on three harts. The symptom is exactly what happened. Try to explain it before revealing why.
1The PTE has no PTE_U
The usyscall mapping copies the trapframe’s mapping and drops PTE_W, leaving PTE_R
only:
vdsotest’s first check calls ugetpid(), whose lw at 0x980 loads from
0x3fffffd000. The PTE exists and the pid is correct in the page (gdb read 3), but its
flags are 0x03 = V|R: without U, a user-mode access faults whatever the other bits
say. A load fault is scause 13 (0xd). usertrap hands it to vmfault, which
declines because the address is above p->sz, and kills the process before it prints a
single line.
usertests passes: nothing in it reads the new page. The trapframe and trampoline are
mapped without PTE_U on purpose, because only S-mode code uses them; this page exists
only for user mode.
2PTE_W is left on
Both pages are mapped like the trapframe, with PTE_W, plus PTE_U:
To see the effect we added a small program, forge (not part of the branch), that stores
1 at USYSCALL and 1000000 at USHARED.
What happened when we ran it
$ forge
forge: getpid() 3, ugetpid() 3
forge: after the store, ugetpid() 1
forge: uptime() 1, uuptime() 1000000
$ vdsotest
vdsotest: pid: OK
vdsotest: uptime agrees: OK
vdsotest: uptime advances: OK
vdsotest: usyscall read-only: FAIL
vdsotest: ushared read-only: FAIL
vdsotest: read() into usyscall fails: FAIL
vdsotest: write() from ushared fails: OK
vdsotest: pid unchanged: FAIL
vdsotest: heap ceiling: FAIL
vdsotest: fork: FAIL
vdsotest: exec: OK
vdsotest: 20 children: OK
vdsotest: SOME TESTS FAILED
$ usertests -q
usertests starting
[...]
test lazy_copy: read succeeded
FAILED
SOME TESTS FAILED
With W set, user stores just succeed. forge makes its own ugetpid() report pid 1,
and its store to the shared page makes uuptime() report 1,000,000 ticks, in every
process, until hart 0’s next clockintr overwrites it. A per-process page that the
process can write is merely useless; a writable shared page lets any process lie to all
the others.
The kernel is fooled as well. copyout's only defence is its PTE_W test
(kernel/vm.c:364), so read(fd, USYSCALL, 8) now succeeds and writes 8 bytes of
README over the pid: read() into usyscall fails: FAIL, and from then on
pid unchanged and fork (which compares the parent’s ugetpid() with getpid())
fail too. heap ceiling fails because the child’s final store survives. usertests lazy_copy catches the same read.
3The page is not unmapped in proc_freepagetable
The page is mapped in proc_pagetable, but its mirror forgets it:
xv6 kernel is booting
hart 2 starting
hart 1 starting
panic: freewalk: leaf
# gdb, breakpoint on panic (rerun):
#0 panic (s=s@entry=0x80007138 "freewalk: leaf") at kernel/printk.c:139
#1 0x000000008000137c in freewalk (pagetable=0x87f51000) at kernel/vm.c:276
#2 0x000000008000139a in freewalk (pagetable=0x87f52000) at kernel/vm.c:273
#3 0x000000008000139a in freewalk (pagetable=pagetable@entry=0x87f53000) at kernel/vm.c:273
#4 0x00000000800013c8 in uvmfree (pagetable=pagetable@entry=0x87f53000, sz=sz@entry=0) at kernel/vm.c:289
#5 0x0000000080001b98 in proc_freepagetable (pagetable=0x87f53000, sz=sz@entry=0) at kernel/proc.c:248
#6 0x0000000080004c1a in kexec (path=path@entry=0x80007180 "/init", argv=argv@entry=0x3fffffdfd0) at kernel/exec.c:138
#7 0x0000000080001990 in forkret () at kernel/proc.c:566
[...]
frame freewalk {'i': '0x1fd', 'pagetable': '0x87f51000', '$s0': '0x3fffffdd10', '$s1': '0x87f51fe8', '$s2': '0x87f52000', '$s3': '0x87f51000', '$a0': '0x80007138'}
frame freewalk {'i': '0x1ff', 'pagetable': '0x87f52000', '$s0': '0x3fffffdd40', '$s1': '0x87f52ff8', '$s2': '0x87f53000', '$s3': '0x87f52000', '$a0': '0x80007138'}
frame freewalk {'i': '0xff', 'pagetable': '0x87f53000', '$s0': '0x3fffffdd70', '$s1': '0x87f537f8', '$s2': '0x87f54000', '$s3': '0x87f53000', '$a0': '0x80007138'}
The kernel never reaches the shell. The very first process is created by userinit
with an empty user image (sz 0) and, in forkret, execs /init. kexec builds
the new page table and frees the old one with proc_freepagetable (frame #6). The old
table still maps USYSCALL. uvmfree removes only the pages in [0, sz), none here,
and then freewalk descends the three levels (frames #3, #2, #1, following index 255,
then 511, then 509) and at index 0x1fd = 509 of the level-0 table finds a valid leaf:
USYSCALL is 0x3fffffd000, whose level-0 index is (0x3fffffd000 >> 12) & 0x1ff =
509. It panics rather than free a table through which a page is still reachable.
The panic is a feature: without it the page-table pages would be freed with a live
mapping inside, and the physical page would be unreachable for the rest of the
process’s life. Every page outside [0, sz) has to be unmapped by name, as
TRAMPOLINE and TRAPFRAME already are.
$ vdsotest
vdsotest: pid: FAIL
vdsotest: uptime agrees: OK
vdsotest: uptime advances: OK
usertrap(): unexpected scause 0xf pid=4
sepc=0x14 stval=0x3fffffd000
vdsotest: usyscall read-only: OK
usertrap(): unexpected scause 0xf pid=5
sepc=0x2e stval=0x3fffffc000
vdsotest: ushared read-only: OK
vdsotest: read() into usyscall fails: OK
vdsotest: write() from ushared fails: OK
vdsotest: pid unchanged: FAIL
scause=0xd sepc=0x80000b2e stval=0x800e022e4061141
panic: kerneltrap
# gdb (rerun, same console output), breakpoints on the unmap in proc_freepagetable,
# on freeproc's kfree, on sys_getpid and on panic:
[...]
allocproc: {'hart': 0, 'noff': 1, 'intena': 0, 'sie': 0} pid 1 p->usyscall 0x87f54000
unmap-free USYSCALL: {'hart': 0, 'noff': 0, 'intena': 0, 'sie': 0, 'pid': 1, 'name': 'init'} pagetable 0x87f53000 PTE 0x21fd5013 frames ['proc_freepagetable', 'kexec', 'forkret', 'myproc']
allocproc: {'hart': 0, 'noff': 1, 'intena': 1, 'sie': 0, 'pid': 1, 'name': 'init'} pid 2 p->usyscall 0x87f52000
unmap-free USYSCALL: {'hart': 0, 'noff': 0, 'intena': 1, 'sie': 1, 'pid': 2, 'name': 'sh'} pagetable 0x87f51000 PTE 0x21fd4813 frames ['proc_freepagetable', 'kexec', 'sys_exec', 'syscall', 'usertrap', '0x3ffffff09c']
allocproc: {'hart': 1, 'noff': 1, 'intena': 1, 'sie': 0, 'pid': 2, 'name': 'sh'} pid 3 p->usyscall 0x87f51000
unmap-free USYSCALL: {'hart': 1, 'noff': 0, 'intena': 1, 'sie': 1, 'pid': 3, 'name': 'vdsotest'} pagetable 0x87f54000 PTE 0x21fd4413 frames ['proc_freepagetable', 'kexec', 'sys_exec', 'syscall', 'usertrap', '0x3ffffff09c']
sys_getpid: {'hart': 1, 'noff': 0, 'intena': 1, 'sie': 1, 'pid': 3, 'name': 'vdsotest'} p->usyscall 0x87f51000 first 8 bytes 0x87f19000 next 8 0x101010101010101
allocproc: {'hart': 0, 'noff': 1, 'intena': 1, 'sie': 0, 'pid': 3, 'name': 'vdsotest'} pid 4 p->usyscall 0x87f54000
freeproc kfree: {'hart': 0, 'noff': 2, 'intena': 1, 'sie': 0, 'pid': 3, 'name': 'vdsotest'} p->pid 4 p->usyscall 0x87f54000 frames ['freeproc', 'kwait', 'sys_wait', 'syscall', 'usertrap', '0x3ffffff09c']
unmap-free USYSCALL: {'hart': 0, 'noff': 2, 'intena': 1, 'sie': 0, 'pid': 3, 'name': 'vdsotest'} pagetable 0x87f47000 PTE 0x21fd5013 frames ['proc_freepagetable', 'freeproc', 'kwait', 'sys_wait', 'syscall', 'usertrap', '0x3ffffff09c']
[...]
panic: {'hart': 1, 'noff': 2, 'intena': 1, 'sie': 0, 'pid': 3, 'name': 'vdsotest'} frames ['panic', 'kerneltrap', 'kernelvec']
#0 panic (s=s@entry=0x80007390 "kerneltrap") at kernel/printk.c:139
#1 0x000000008000289c in kerneltrap () at kernel/trap.c:159
#2 0x0000000080005728 in kernelvec () at kernel/kernelvec.S:38
Backtrace stopped: frame did not save the PC
interrupted: sepc 0x80000b2e kalloc + 32 in section .text s1 0x800e022e4061141 fp 0x3fffff9e90
saved ra 0x80000b24 kalloc + 22 in section .text
ra 0x80000fb8 walk + 122 in section .text
ra 0x8000105a mappages + 72 in section .text
ra 0x8000144a uvmcopy + 100 in section .text
ra 0x80001da6 kfork + 44 in section .text
ra 0x80002a9e sys_fork + 12 in section .text
ra 0x80002a2e syscall + 58 in section .text
ra 0x800027b4 usertrap + 166 in section .text
ra 0x3ffffff09c No symbol matches 274877903004.
kmem.freelist 0x800e022e4061141
Two different mistakes come out of one line.
At exec, from boot on. Every exec frees the running process’s own page, while the
process keeps mapping and owning it. It starts before the shell prompt: init’s exec of
/init freed 0x87f54000 (PTE 0x21fd5013), and the shell’s exec freed 0x87f52000.
When the shell then execs vdsotest (pid 3), kexec frees pid 3’s page,
p->usyscall = 0x87f51000, which the new page table maps too. kfree fills a
freed page with 0x01 bytes and stores the free-list link in its first 8 bytes: gdb read
exactly that in pid 3’s page (0x87f19000, then 0x0101...). ugetpid() returns the low
32 bits of a kernel pointer: pid: FAIL. Freed pages get reused while still mapped: after
serving as pid 3’s first page table, init’s page 0x87f54000 was handed to pid 4 by
allocproc as its usyscall page, while init still maps it as its own USYSCALL. Two
processes now share one pid page, and the kernel has no idea.
At wait. For each child vdsotest reaps, freeproc calls kfree(p->usyscall) and
then proc_freepagetable frees the same page again (both records show pid 4’s page,
PTE 0x21fd5013 = physical 0x87f54000). A page freed twice makes the free list
point at itself: X.next = X. kalloc hands X out (most likely to a fork, whose
uvmcopy copies a code page into it), then, because the head still says X, hands out
X again and sets the head to X’s first 8 bytes, now program code:
0x0800e022e4061141 is the little-endian form of 41 11 06 e4 22 e0 00 08, the
instructions addi sp,sp,-16; sd ra,8(sp); sd s0,0(sp); addi s0,sp,16. The next
kalloc, from walk inside a later uvmcopy (noff 2: the child’s p->lock
and kmem.lock), loads r->next through that “pointer”: a load page fault in the
kernel (scause 0xd at kalloc+32), and kerneltrap panics.
The general rule: every physical page has exactly one owner that frees it. For the usyscall
page that is freeproc; page tables only borrow it.
5The mapping is made outside the page-table builder, so exec loses it
p->pagetable = proc_pagetable(p);
if (p->pagetable == 0) {
freeproc(p);
release(&p->lock);
return 0;
}
+
+ // map the usyscall page, read-only for user code.
+ if (mappages(p->pagetable, USYSCALL, PGSIZE, (uint64)(p->usyscall),
+ PTE_R | PTE_U) < 0) {
+ freeproc(p);
+ release(&p->lock);
+ return 0;
+ }
What happened when we ran it
$ vdsotest
usertrap(): unexpected scause 0xd pid=3
sepc=0x980 stval=0x3fffffd000
$ usertests -q
usertests starting
[...]
ALL TESTS PASSED
# gdb, breakpoint on setkilled (rerun):
setkilled: {'hart': 2, 'noff': 0, 'intena': 0, 'sie': 0, 'pid': 3, 'name': 'vdsotest'} scause 0xd stval 0x3fffffd000 sepc 0x980
frames ['setkilled', 'usertrap', '0x3ffffff09c']
p->usyscall 0x87f51000 pid in page 3
pagetable 0x87f21000
PTE for 0x3ffffff000: 0x2000184b
PTE for 0x3fffffe000: 0x21fcfcc7
PTE for 0x3fffffd000: no PTE (level-0 entry 509 is 0x0)
PTE for 0x3fffffc000: 0x21fd6413
The console shows exactly what clinic 1 showed: the first ugetpid() load faults. Only
the page table tells them apart. Here the physical page exists and holds the right pid,
but the page table of the exec’d vdsotest has no entry at all for it: kexec built
that table with proc_pagetable (kernel/exec.c:56), and the mapping now lives in
allocproc, which exec never calls. A forked child that does notexec would read
its pid fine, but in practice every program a user runs is started by exec, so the page
is missing in all of them.
The fix is to map fixed pages in the one function every user page table comes from. The
trapframe has always been mapped there for the same reason.
6The heap’s ceiling stays at TRAPFRAME
Everything else as in the reference, but the old limit is kept in both places:
- if (sz + n > MAXHEAP) {
+ if (sz + n > TRAPFRAME) {
[...]
- if (addr + n > MAXHEAP)
+ if (addr + n > TRAPFRAME)
What happened when we ran it
# one boot:
$ vdsotest
[...]
vdsotest: pid unchanged: OK
vdsotest: heap ceiling: FAIL
vdsotest: fork: OK
vdsotest: exec: OK
vdsotest: 20 children: OK
vdsotest: SOME TESTS FAILED
$ usertests lazy_sbrk
usertests starting
test lazy_sbrk: panic: mappages: remap
# a second boot, gdb attached, breakpoint on panic, `usertests lazy_sbrk`:
#0 panic (s=s@entry=0x80007108 "mappages: remap") at kernel/printk.c:139
#1 0x00000000800010ac in mappages (pagetable=pagetable@entry=0x80023000, va=va@entry=274877890560, size=size@entry=4096, pa=<optimized out>, pa@entry=2147725312, perm=perm@entry=22) at kernel/vm.c:167
#2 0x0000000080001302 in uvmalloc (pagetable=0x80023000, oldsz=274877890560, newsz=274877890561, xperm=xperm@entry=4) at kernel/vm.c:234
#3 0x0000000080001d4a in growproc (n=1) at kernel/proc.c:281
#4 0x0000000080002b28 in sys_sbrk () at kernel/sysproc.c:51
#5 0x0000000080002a2e in syscall () at kernel/syscall.c:146
#6 0x00000000800027b4 in usertrap () at kernel/trap.c:74
[...]
# two more boots with a probe program (ceilprobe, not on the branch) whose children
# grow p->sz lazily to 0x3fffffe000, over both new pages:
$ ceilprobe store
ceilprobe: sz 0x0000003FFFFFE000, storing to USYSCALL
usertrap(): unexpected scause 0xf pid=4
sepc=0x9e stval=0x3fffffd000
ceilprobe: store child status -1
ceilprobe: sz 0x0000003FFFFFE000, write(USHARED) returns 8
$
[...]
$ ceilprobe shrink
ceilprobe: sz 0x0000003FFFFFE000, sbrk(-8192)
usertrap(): unexpected scause 0xd pid=4
sepc=0x490 stval=0x3fffffc000
ceilprobe: shrink child status -1, uuptime 3
$ ceilprobe store
usertrap(): unexpected scause 0xf pid=5
sepc=0xa70 stval=0x0
$ vdsotest
usertrap(): unexpected scause 0xf pid=6
sepc=0xa70 stval=0x0
vdsotest heap ceiling notices first, without any damage: its child’s sbrklazy(1) beyond
0x3fffffc000 succeeds, so by the code the child exits with status 3 instead of being
killed, and p->sz now covers the shared page.
usertests lazy_sbrk turns the same hole into a panic. It grows the heap lazily up to
MAXHEAP - PGSIZE, maps the last page eagerly with sbrk(4096), and then asks for one
byte more, expecting -1. growproc compares with the old ceiling, so it calls
uvmalloc from oldsz = 274877890560 = 0x3fffffc000: the address of USHARED.
mappages finds the shared page’s PTE there and panics (kernel/vm.c:167).
The probe runs show what the ceiling really protects. A store to USYSCALL with p->sz
covering it is still killed: vmfault declines because ismapped finds the page.
But copyin's new test is bypassed, so write from USHARED returns 8. And
sbrk(-8192) from 0x3fffffe000 makes uvmdealloc unmap both pages with do_free =
1: the child’s next uuptime() faults on the now-unmapped 0x3fffffc000, and the shared
page, which every other process still maps and clockintr still writes, is on the
free list. From then on every new program died at once (scause 0xf, stval=0x0), even
vdsotest. We did not trace that last failure further; a shared page freed while in use
is enough to explain a broken system.
5. The reference solution
Take the guided tour through the reference solution, one commit at a time, with the machine state at every step:
On the branch (ext/10-vdso, 8 commits, every commit builds), built with the project
toolchain and run on 3 harts (-smp 3 -m 128M):
$ vdsotest
vdsotest: pid: OK
vdsotest: uptime agrees: OK
vdsotest: uptime advances: OK
usertrap(): unexpected scause 0xf pid=4
sepc=0x14 stval=0x3fffffd000
vdsotest: usyscall read-only: OK
usertrap(): unexpected scause 0xf pid=5
sepc=0x2e stval=0x3fffffc000
vdsotest: ushared read-only: OK
vdsotest: read() into usyscall fails: OK
vdsotest: write() from ushared fails: OK
vdsotest: pid unchanged: OK
usertrap(): unexpected scause 0xf pid=6
sepc=0xd2 stval=0x3fffffd000
vdsotest: heap ceiling: OK
vdsotest: fork: OK
vdsotest: exec: OK
vdsotest: 20 children: OK
vdsotest: ALL OK
$ usertests -q
usertests starting
test copyin: OK
test copyout: OK
[...]
test nowrite: usertrap(): unexpected scause 0xf pid=6590
[...]
test lazy_copy: OK
test lazy_copyinstr: OK
test lazy_sbrk: OK
test partial_write: OK
test unlinkcwd: OK
ALL TESTS PASSED
$ vdsotest
[...]
vdsotest: ALL OK
The three usertrap() lines in vdsotest are the expected kills of the read-only and
ceiling checks; the test verifies each from the child’s exit status. usertests -q passing
shows that the rest of the system is unchanged: lazy_copy (system calls refuse the
addresses of the new pages), lazy_sbrk (the heap reaches its new ceiling and no further),
nowrite (stores to TRAPFRAME and above still kill), and the free-page counts that
usertests compares. vdsotest passes again after usertests.
For comparison, at commit 4 (both pages mapped, copyin not yet changed) usertests -q
stops at test lazy_copy: write succeeded, FAILED.
Time per call, from vdsotest time on 3 harts (QEMU 10.2.1; a tick is about 0.1 s,
20 ticks per measurement; times on QEMU depend on the computer and on what else it is
doing, so yours will differ):
calls in 20 ticks
about
ratio
getpid()
175,000
11,428 ns
ugetpid()
88,831,000
22 ns
508×
uptime()
169,000
11,834 ns
uuptime()
89,029,000
22 ns
527×
Two earlier runs gave 174,000 / 168,000 getpid() and 89,731,000 / 87,894,000 ugetpid()
calls: the numbers are stable to a few percent.
Instructions per call, single-stepped with gdb (QEMU’s single-step with interrupts
masked, one hart locked):
Where the 1,103 go: 83 in the trampoline (uservec 44, userret 39), 392 in
mycpu, 144 in push_off, 118 in pop_off, 84 in myproc, 86 in acquire and
holding, 34 in release, 38 in killed, 43 in usertrap, 42 in
prepare_return, 29 in syscall and 10 in sys_getpid. Most of the cost is
bookkeeping around the trap: finding the current process four times and checking killed
twice, each under p->lock. The answer itself is one load in both cases.
Instructions against time. The timing loop adds 3 instructions per call (jalr s2,
addiw, bnez at 0x53c-0x540 in user/vdsotest.asm), so one iteration is 1,109
instructions with getpid (3 + 3 + 1,103) and 15 with ugetpid (3 + 12): a factor of about
74. The measured factor is about 508, so each instruction on the getpid path costs about 7
times as much time. A run with the four sfence.vma removed from trampoline.S
(not valid on hardware; on QEMU the satp writes still flush): getpid went from 11,695 and
12,269 ns to 8,230 and 7,874 ns, ugetpid stayed at 21-24 ns. Translation-cache flushes are
therefore a large share of the extra time per instruction; the rest was not measured.
Memory. One page per process (the usyscall page, allocated next to the trapframe) and one
page in total for USHARED. Two pages of user virtual address space are taken from the top
of the heap’s range.
7. Go further
A real vDSO clock. Set scounteren.TM in the kernel so that user code may execute
rdtime, and publish in the shared page what is needed to convert time to seconds. Then
uuptime can report fractions of a tick. You will need two values that must agree, and so
a sequence counter; it teaches the reader-retry protocol that Linux uses.
More per-process facts. Publish the parent’s pid, or a per-process count of system
calls that the kernel updates on every trap. Which of them need volatile, which need
ordering, and which can only be written by the process’s own hart?
Map code, not just data. Put a small function in a page shared by all processes,
mapped R|X|U, and let user programs call it at a fixed address. This is what a real vDSO
is: an ELF image the kernel maps into every process. It teaches position-independent code
and why the kernel must never let that page be writable.
Measure on real hardware. Run the branch on a RISC-V board and compare the
getpid / ugetpid ratio with QEMU’s. The instruction counts stay the same; the cost of a
trap and of sfence.vma will not.