Lab 9 · reveal · 20 steps · 10 commits
Every xv6 process has exactly one thread: one page table, one trapframe, one kernel stack,
one stream of instructions. In this lab you add threads. clone(fn, arg, stack) starts a
new thread that runs in the caller’s address space, on a stack the caller allocated;
join() waits for one to finish; futex_wait and futex_wake let threads sleep and wake
each other on a word of shared memory; and a small user library builds thread_create,
thread_join and a mutex on top of them.
Sharing one page table between several harts at once breaks assumptions that
hold so quietly in this tree that nobody wrote them down. The trampoline finds the
trapframe at a fixed address: where does the second thread’s trapframe go, and how
does uservec, with every register full of user data, find it? Who frees a page table
that four threads use, and when? What happens when two threads call sbrk, or touch the
same lazily allocated page, on two harts at the same moment? What does exit mean now,
and wait, and kill? And how do you put a thread to sleep until some user memory
changes without losing the wakeup that arrives a moment too early?
The reference solution is ten small commits. With it, creating and joining a thread costs
no page allocations at all (a fork of a 1 MiB process costs 266), and 2000
create-and-join pairs take 3 timer ticks where 2000 fork-and-wait pairs take 69.
Each step shows one change on the branch ext/09-threads, the code around it, and the state of the machine when that code runs.
vm->lockkernel/proc.hStep 1 of 20 · commit 1: Move the user memory size into a shared struct vm
The story of this tour, recorded on 3 harts with gdb attached to the finished branch:
threadtest’s test process (pid 4) creates its first thread (pid 5), the thread runs,
traps and exits, pid 4 joins it, and later the futex and fault paths of other threads.
The state boxes come from those runs; where a step’s state is reasoned instead, the
note says so.
Commit 1 changes no behaviour. It only moves what describes memory out of struct proc: sz goes into a new struct vm with a reference count and a lock, and each
struct proc gets a pointer to it. With threads, every thread of a process will point
to the same struct vm; for now each process has its own, with ref = 1.
The state above is a moment from much later (commit 6’s growproc), chosen because
it shows the structure in use: pid 4 holds vm->lock while it moves the break from
0x7000 to 0x9000 for a second thread’s stack, and gdb printed the vm as ref = 2,
slots = 3. The page-table pointer stays in struct proc as a copy (comment: “the
vm’s”): it never changes while threads share it, a rule commit 6 enforces.
Every p->sz in the kernel becomes p->vm->sz: about twenty uses in exec.c, file.c,
pipe.c, proc.c, syscall.c, sysfile.c, sysproc.c and trap.c, all mechanical.
wait_lockpid 335's p->lockkernel/proc.cStep 2 of 20 · commit 1: Move the user memory size into a shared struct vm
allocvm mirrors allocproc: scan the static table vms[NPROC], taking each
entry’s lock, and claim the first with ref 0. dropvm, called from freeproc,
gives one reference back.
The order inside dropvm is the point. Decrement and read sz in one critical
section; decide “was I last?” from the local ref, not from a second look at the
structure. Once the lock is released with ref = 0, a fork on another hart may
claim this very struct vm in allocvm and set sz to 0, so reading vm->sz after
the release could free the wrong amount.
The state is from the finished branch, where dropvm has a few more lines (the slot
bit and the trapframe page) but the same order of steps: init (pid 1) on hart 2 reaping pid 335, the last thread of a process from
threadtest’s exit test (its first thread had exited, which killed the others; init
inherited them). gdb stopped on the line that frees: ref had reached 0, sz was
0xb000. kwait holds wait_lock and the zombie’s p->lock, so noff is 2; inside
dropvm, vm->lock made it 3 for a few instructions and was already released.
kernel/trampoline.SStep 3 of 20 · commit 2: Find the trapframe through sscratch, not a constant
At the first instruction of uservec every general-purpose register holds a user
value that must be saved, so the code may not touch one. The original borrowed
sscratch to park a0 (csrw sscratch, a0) and then loaded the constant
TRAPFRAME into a0. A per-thread address cannot be a constant; but it can be
in sscratch, if the kernel put it there before returning to user space (next
steps). Then one csrrw exchanges the two: a0 gets the trapframe address,
sscratch gets the user’s a0, and lines 69-70 store that into the frame as before.
Recorded with gdb (a hardware breakpoint at 0x3ffffff004, right after the csrrw),
for pid 5, the thread in slot 1, entering the kernel for exit(100): a0 = 0x3fffffe200 (slot 1), sscratch = 0x64 (100, the exit status the user had in a0),
scause = 8 (ecall), sepc = 0xfde (the ecall in the exit stub), sp = 0x6fe0,
on the thread’s own user stack. satp still holds the user page table
(0x8000000000080024, root 0x80024000, the one pid 4 uses too).
This commit alone changes nothing visible: sscratch still holds TRAPFRAME.
Step 4 of 20 · commit 2: Find the trapframe through sscratch, not a constant
On the way out, userret switches to the user page table (line 108) and then needs
the trapframe to restore registers from. csrr a0, sscratch reads it without
changing sscratch: the value must still be there at the thread’s next trap, when
uservec swaps it out again.
Recorded at pid 5’s very first entry into user space, coming from forkret
(a hardware breakpoint just after line 113): a0 = sscratch = 0x3fffffe200, satp = 0x8000000000080024, sepc = 0x15f4 (the library’s start function, where the thread
begins). sp is 0x3fffff5fd0, pid 5’s kernel stack, which the user page table does
not map; line 117 replaces it with the user’s.
Why is it safe to keep a kernel-chosen value in sscratch across user mode? User
code cannot read or write sscratch (it is an S-mode CSR), and nothing in the kernel
touches it between prepare_return and sret, where interrupts are off. Traps taken
in the kernel go to kernelvec, which does not use it.
kernel/trap.cStep 5 of 20 · commit 3: Give each thread a trapframe slot in one shared page
prepare_return already fills the per-thread fields that uservec will need next
time (kernel_sp, kernel_hartid…, lines 116-119). Those writes go to
p->trapframe, which is now this thread’s slot, so each thread’s slot carries its own
kernel stack pointer: two threads trapping at once on two harts land on two different
kernel stacks. Line 123 adds the one value that cannot live in the frame itself: the
frame’s own user address, TRAPFRAME + slot * 512, written into sscratch.
Recorded: pid 5 on hart 2, called from forkret for its first return, p->slot = 1, p->trapframe = 0x80023200 (the kernel address of slot 1 in the trapframe page at
0x80023000), epc = 0x15f4. Interrupts are off since line 108 (gdb: sstatus SIE
clear, noff 0, intena 0): a timer interrupt here would go through stvec, which line
112 already pointed at uservec. (Commit 2 wrote the constant TRAPFRAME here; commit
3 changed it to the slot.)
pid 5's p->lockvm->lockkernel/memlayout.hStep 6 of 20 · commit 3: Give each thread a trapframe slot in one shared page
A trapframe is 288 bytes (struct trapframe, 36 fields of 8 bytes: 4 for the kernel,
the user pc and 31 user registers). Commit 3 gives
each thread a 512-byte slot in the one page at TRAPFRAME, so 8 threads per process
(NTHREAD), and a _Static_assert in proc.c stops the build if the struct ever
outgrows its slot. The page itself moves into struct vm (tfpage, plus a bitmask
slots), and struct proc gets its slot number.
Why not a page per thread below TRAPFRAME? Because user memory may already extend
up to TRAPFRAME: usertests lazy_sbrk grows a process to exactly that limit and
writes the last page. Slots in the existing page need no new mapping, no unmapping
when a thread dies, and no TLB thinking: the page is mapped once, in proc_pagetable,
for the life of the address space.
The state is the moment the slots get used (commit 4’s sharevm), recorded: pid 4
on hart 2 creating pid 5, holding pid 5’s p->lock (from allocproc) and
vm->lock, noff 2. gdb printed slots = 3 (bits 0 and 1: pid 4 and the new thread),
ref = 1 just before the increment, tfpage = 0x80023000.
child's p->lockkernel/proc.cStep 7 of 20 · commit 3: Give each thread a trapframe slot in one shared page
allocvm now also allocates the trapframe page, before the scan, so that no
kalloc happens while a vm->lock is held (it would be legal, kmem.lock comes after
vm->lock in the order, but there is no reason to). If no table entry is free, the page
goes back. A new address space starts with slots = 1: slot 0 is its first thread’s.
dropvm clears the thread’s slot bit together with the decrement, and the last
reference frees the trapframe page after the page table. The page table must go
first: proc_freepagetable unmaps TRAPFRAME (without freeing what it points to),
and only then may the page itself be reused.
State reasoned, not recorded: the shell forking for a command, with the child’s
p->lock held since allocproc found its slot, so noff 1 and interrupts off; the
system call turned them on before (usertrap line 66), so intena 1.
pid 5's p->lockvm->lockkernel/proc.cStep 8 of 20 · commit 4: Add clone: a new thread in the caller's address space
Recorded at line 151, the first clone of the test: gdb stopped on hart 2 with i = 1, slots = 3 (the bit was just set), ref = 1 (about to become 2), and vm->lock
held by cpus+256 (hart 2). Taking a slot and raising ref happen in one critical
section: two threads cloning at the same moment on two harts cannot pick the same
slot, and dropvm’s “last one out” test can never see a count that misses a thread
being born.
If all 8 slots are taken (counting zombies not yet joined), sharevm returns -1 and
clone fails; threadtest create and join checks that an eighth thread is refused.
pid 5's p->lockkernel/proc.cStep 9 of 20 · commit 4: Add clone: a new thread in the caller's address space
allocproc takes the vm to join, or 0 for a new process. A thread gets everything
a process gets that is about running (a pid, the slot’s kernel stack, a fresh
context that starts at forkret) but no page table: line 227 calls
proc_pagetable only for a new vm, and kclone copies the caller’s pointer.
Line 226 is where the slot becomes a trapframe: tfpage + slot * TFSIZE is the
kernel’s (direct-mapped, physical) address of the slot, 0x80023200 for pid 5. The
same 512 bytes appear in the user page table at 0x3fffffe200.
State: one frame above the previous step (reasoned from it): pid 5’s p->lock held,
vm->lock not yet taken.
pid 5's p->lockkernel/proc.cStep 10 of 20 · commit 4: Add clone: a new thread in the caller's address space
Recorded at line 415 (the first clone): np->pid = 5, np->slot = 1,
np->trapframe = 0x80023200, fn = 0x15f4 (the library’s start), arg = stack = 0x6ff0 (the top 16 bytes of the new stack hold fn and arg for start), and both
np->pagetable and p->pagetable are 0x80024000. No user memory is copied.
The new frame starts as a copy of the caller’s (line 414: gp, tp and the rest
come along), then gets its own pc, argument and stack. ra = 0: if fn ever
returned, the thread would jump to address 0 and fault, and the fault would kill the
process; the library’s start calls exit instead.
With a shared trapframe (clinic 1), lines 414-418 would write into the caller’s
saved registers: the caller would “return” from clone into start, on the new
stack.
The rest is kfork's tail: duplicate file descriptors and the current directory,
set parent under wait_lock, then RUNNABLE under the child’s lock. Until commit 5,
wait reaps threads too.
wait_lockpid 5's p->lockkernel/proc.cStep 11 of 20 · commit 5: Add join, and keep wait() away from threads
One scan, one new test: a child shares the caller’s address space exactly when it is
a thread of the caller. wait passes threads = 0 and skips threads; join passes 1
and skips processes.
Recorded: pid 4 in join, line 530, having found pid 5 a zombie with xstate = 100
(exitfn returned 100 + 0). pp->vm is read under pp->lock: allocproc sets it
and freeproc clears it under that lock, so the comparison cannot catch a slot in
the middle of being reused. freeproc then calls dropvm, which lowers ref by
one (from 8, reasoned: all 7 threads of this test were still counted); pid 4 still uses
the address space, so nothing is freed.
copyout of the status into pid 4’s memory (line 534) runs with wait_lock and
pid 5’s p->lock held; if the target page were still lazy, vmfault would take
vm->lock (from commit 6) as a third lock: noff 3, the same depth as the
kfree path below it.
vm->lockkernel/proc.cStep 12 of 20 · commit 6: Lock the shared address space where it changes
Both kinds of sbrk now go through growproc, which returns the old size:
reading the break and moving it happen under vm->lock, so no two threads can be
handed the same addresses. The original lazy path read sz in sys_sbrk and added
to it separately (kernel/sysproc.c:48, kernel/sysproc.c:62).
Recorded at the line that stores the new size (vm->sz = newsz): pid 4, n = 8192,
eager, sz = 0x7000, newsz = 0x9000, ref = 2: the library taking a second thread
stack while the first thread runs.
With ref > 1 an eager sbrk goes through uvmgrow instead of uvmalloc
(lines 338-346). uvmalloc maps page by page and, if memory runs out halfway,
unmaps and frees the pages it already mapped (kernel/vm.c:230); another hart’s
TLB (translation lookaside buffer) could still hold one of them. uvmgrow creates the page-table pages first,
then takes every physical page it needs, and maps them only when all are in hand; on
failure it gives back pages that were never mapped. threadtest checks it with a
128 MiB sbrk while a second thread is alive.
The lock is held across uvmalloc, which may allocate and zero many pages with
interrupts off on this hart. A big eager sbrk therefore delays this hart’s timer
interrupt for as long as the allocation takes. kfork in the original tree already
did the same for its whole copy (under the child’s p->lock), so this adds no new
kind of latency.
Shrinking is refused while ref > 1 (line 350): another thread may be inside
copyout into the very page, and nothing else protects it.
vm->lockkernel/vm.cStep 13 of 20 · commit 6: Lock the shared address space where it changes
Seven threads touch the same 512 lazy pages (threadtest lazy). Two faults on one
page can now only be handled one at a time, and the second must succeed: the page
it wanted exists.
Recorded on the reference, in both runs where we put a breakpoint on line 519: here
pid 43 on hart 1 faulted on a store (read = 0) to 0x1c8000, took the lock, and
found the PTE 0x2007c817 already there: flags 0x017 = V, R, W, U, with A and D
still clear because no access has gone through it yet. Another thread had mapped it
a moment earlier. The vm at that moment: ref = 8, slots = 255, all 8 slots in use.
Line 520 accepts the page because it is a user page that allows a write; a store to
text (no W) or to the guard page (no U) still fails and kills, as usertests
checks.
Page faults leave interrupts off (usertrap turns them on only for system calls),
so acquire recorded intena 0.
vm->lockkernel/exec.cStep 14 of 20 · commit 6: Lock the shared address space where it changes
kexec builds a new page table and frees the old one (kernel/exec.c:138).
With another thread still running in the old one, that thread’s next instruction
would fetch through freed memory. The reference refuses: exec fails with -1 while
ref > 1. (Linux instead kills the other threads first; see “further”.) The read of
ref takes the lock for clarity; a count of 1 cannot change underneath, since only a
thread of this address space could raise it, and this is the only one.
This, with the refused shrink and uvmgrow in growproc, is what makes the
lock-free readers safe: while an address space is shared, nothing removes a user page. copyin,
copyout and the hardware walker may look at the page table at any moment and
never find a page freed under them.
kfork (same commit) holds the parent’s vm->lock around uvmcopy, so a fork
from one thread copies a consistent snapshot even while another thread grows memory.
Only the calling thread exists in the child.
State reasoned: threadtest’s shared memory only grows check calling exec("echo") with a
second thread alive, at line 43 (noff 1 for vm->lock, so interrupts are off; intena
1, since the system call had turned them on).
pid 334's p->lockkernel/proc.cStep 15 of 20 · commit 7: End the whole process when its first thread exits or is killed
exit keeps its meaning for the program as a whole: when the first thread exits (the
one its parent waits for), or when any thread has been killed, kexit first marks
every other thread of the address space killed and wakes the sleeping ones. Each
exits the next time it passes through usertrap: at once if it is in a system call
or asleep, at its next timer interrupt if it is computing in user mode.
Recorded: pid 333, the exit test’s child, calling exit(5) on hart 0. At line 493
it holds pid 334’s p->lock; pid 334 was RUNNABLE (a spinning thread, just
preempted), and gdb saw hart 1 at the same moment at user address 0x8, inside
spinfn: another of pid 333’s threads, still spinning, about to be stopped by its next
timer tick.
pp->vm == p->vm is read under pp->lock, and our own vm cannot be recycled while
we use it, so an equal pointer really is a sibling. Who reaps the killed threads? Their
parent is pid 333, a zombie soon; reparent gives them to init, init’s wait reaps
them (their vm is not init’s), and the last one frees the memory (step 2 is that
moment, recorded in another run). threadtest checks that the free page count
returns to its starting value.
kernel/futex.cStep 16 of 20 · commit 8: Add futex_wait and futex_wake
The channel is the physical address of the user word (futexchan, lines 20-31): the
same for every thread, since they share one page table, and never equal to a kernel
channel. The copyin there also faults in a lazily allocated word.
Then the order that matters: sleep_prepare (line 48) before the look at the word
(line 49). Recorded at line 56, the ping-pong test: pid 34 (thread 0) about to sleep,
val = 1, x = 1, p->chan = 0x8002b010, and the word at that physical address
still 1. If the other thread stores 0 and calls futex_wake now, it finds p->chan
set, clears it, and sleep returns at once.
No lock is held here (noff 0, interrupts on: a system call), and none is needed
around the two steps: p->lock, taken inside sleep_prepare and inside the waker’s
scan, orders them (think question 6). A thread that does not sleep clears its
registration (lines 62-64).
A kill has the same gap between line 53 and line 56. The same commit makes kkill
and killthreads clear p->chan along with setting killed, so a kill that lands
there turns the sleep on line 56 into an immediate return, exactly as a wakeup
would; the thread then exits on its way back through usertrap.
pid 21's p->lockStep 17 of 20 · commit 8: Add futex_wait and futex_wake
Like wakeup, but it stops after n threads and returns the count. Recorded at line
88 during the mutex test: pid 20 unlocking with n = 1, chan 0x8002b018 (the mutex
word m, user address 0x2018), finding pid 21 registered but in state RUNNING: pid
21 was somewhere between its sleep_prepare and its sleep, on another hart.
Clearing p->chan is what makes that sleep return at once. Counting it as woken
is right: it will retry the mutex.
In the measured runs this was the common case: of 36 threads woken in one contended mutex run, only 1 had actually gone to sleep (in another, 215 woken and none asleep).
user/uthread.cStep 18 of 20 · commit 9: Add a user thread library with a futex mutex
Three values: 0 free, 1 held, 2 held and maybe waited for. The fast path is one
compare-and-swap (compiled to an lr.w.aq/sc.w loop: RV64GC has no single
compare-and-swap instruction), and the unlock one amoswap.w.rl that returns 1: no
system call. A waiter
exchanges 2 into the word before it sleeps, so the holder’s unlock sees 2 and calls
futex_wake. futex_wait(&m->v, 2) returns at once if the word is no longer 2, which
closes the gap between the exchange and the system call.
__ATOMIC_ACQUIRE on the lock and __ATOMIC_RELEASE on the unlock order the data
the mutex protects, as acquire and release do in the kernel (Tour 19: Memory ordering across harts).
State reasoned: a thread of the mutex test in user mode, on its own stack.
Step 19 of 20 · commit 9: Add a user thread library with a futex mutex
clone passes one argument, so the library writes fn and arg into the top 16
bytes of the new stack and passes their address both as the argument and as the
stack pointer: the thread starts in start(s) with sp = s, and its frames grow
downwards from just below them (recorded in step 10: arg = stack = 0x6ff0). start
calls fn(arg) and exits with its result, which join returns.
Stacks come from sbrk (thread-safe since commit 6) and are reused after
thread_join. The table is protected by the library’s own futex mutex: any thread
may create threads. There are no guard pages: a thread that overflows its 8 KiB
writes into the next one’s stack, silently (see “further”).
user/threadtest.cStep 20 of 20 · commit 10: Add threadtest
Seven threads walk the same 512 lazily allocated pages in the same order, each
writing its own byte. The first thread through a page takes the fault and maps it;
the others fault on it at the same moment or find it mapped. sb a3,0(a4) at 0x320
is the store that faults: clinic 5’s two kills both have sepc=0x320.
Each check in threadtest follows one think question: registers (the slot and
sscratch), join and wait (the vm test), sbrk and lazy (the address-space
lock), shrink and exec (the “only grow while shared” rule), the exit and kill checks
(killing a thread group), ping-pong (futex ordering). The gate, gatewait, holds all
threads in futex_wait until the last is created, so they start together; even so,
an idle hart waits in wfi for its next timer interrupt before it picks up a woken
thread, which is why the tests do enough work to overlap.
Lab 9 · wrap-up
The branch head (ext/09-threads, 10 commits), built with the project toolchain, run on 3
harts (-smp 3 -m 128M):
$ threadtest
threadtest: create and join: OK
threadtest: registers: OK
threadtest: mutex: 140000 of 140000
threadtest: mutex: OK
threadtest: without the mutex: 120203 of 140000 (not checked)
threadtest: ping-pong: OK
threadtest: sbrk: OK
threadtest: lazy: OK
threadtest: shared memory only grows: OK
threadtest: wait and join: OK
threadtest: stress: OK
threadtest: exit ends all threads: OK
threadtest: kill ends all threads: OK
threadtest: free pages 32469 before, 32469 after
threadtest: no leaks: OK
threadtest: ALL OK
$ usertests -q
usertests starting
test copyin: OK
test copyout: OK
[...]
test kernmem: usertrap(): unexpected scause 0xd pid=6814
sepc=0x1b54 stval=0x80000000
[...]
test lazy_sbrk: OK
test partial_write: OK
test unlinkcwd: OK
ALL TESTS PASSED
$ threadtest
threadtest: create and join: OK
[...]
threadtest: without the mutex: 60000 of 140000 (not checked)
[...]
threadtest: free pages 32469 before, 32469 after
threadtest: no leaks: OK
threadtest: ALL OK
The usertrap() lines inside usertests are its expected kills (kernmem reads kernel
memory and must die). usertests -q passing shows the single-threaded world unchanged:
lazy_sbrk still grows memory up to TRAPFRAME - PGSIZE, nowrite and stacktest
still die (the new vmfault accepts an already-mapped page only if it allows the
access), sbrkfail and the other out-of-memory tests behave as before (a single-threaded
process still grows with uvmalloc), and the free-page count after all tests equals
the one before. threadtest
after usertests reports the same 32,469 free pages. The same three commands passed on
a second boot, and usertests -q passed at every intermediate commit; every commit
builds on its own.
The “without the mutex” number is printed, not checked: 120,203 and 60,000 here, 59,439 and 80,393 on the second boot, 140,000 (no update lost) in some earlier runs. How much the threads overlap depends on when idle harts next take a timer interrupt.
Keys: ← → step · Home start