Extension labs · lab 9 · Scheduling · ★★★★★

User threads: clone, join and futex

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.

Read first: Tour 5: Life of a system call, Tour 7: The trampoline and the trapframe, Tour 16: sleep and wakeup, and the lost-wakeup problem, Tour 20: fork, Tour 21: exit, wait and zombies, Tour 23: kill, Tour 26: sbrk, eager and lazy, and page faults, Tour 28: Crossing the user/kernel boundary in memory, Tour 43: A system call, CSR by CSR · The stacks of xv6, Locks and interrupt state

What this lab teaches

What a thread is to a kernel: which state must be private (registers, trapframe, kernel stack, user stack) and which is shared (the page table, the size of user memory), and why the shared part needs a reference count and a lock of its own.
How the trap entry code can find per-thread state at a moment when every general-purpose register still belongs to the user.
What happens to a page table that several harts use at once: which changes race, what each race does on a real run, and what it takes for code that only reads the page table to stay safe.
How the lifetime rules of processes (exit, wait, kill, orphans and init) extend to threads, and what goes wrong when a shared resource is freed by the first user instead of the last.
How a user-level sleep primitive is built on this tree’s sleep_prepare/sleep/wakeup protocol, what decides whether a wakeup can get lost, and how a mutex can avoid system calls when nobody contends.

The reference branch

ext/09-threads in ShowMeTheStack/xv6-riscv-labs, branched from the frozen commit 06aad25; 10 commits.

git clone https://github.com/ShowMeTheStack/xv6-riscv-labs
cd xv6-riscv-labs
git checkout -b my-threads 06aad25   # start your own
git diff 06aad25 origin/ext/09-threads   # only when you want the answer

1. The spec

System calls.

int clone(void (*fn)(void *), void *arg, void *stack) creates a thread in the caller’s address space and returns its id (a pid), or -1. The thread starts at fn with a0 = arg and sp = stack; stack is the top of memory the caller allocated. The thread has its own pid, kernel stack and trapframe, and copies of the caller’s open files and current directory (as with fork). fn must not return; it ends with exit(status).
int join(int *status) waits for a thread that the calling thread created, stores its exit status and returns its id; -1 if there is none.
int futex_wait(int *addr, int val): if *addr == val, sleep until a futex_wake on addr; otherwise return at once. Spurious returns are allowed: callers re-check.
int futex_wake(int *addr, int n) wakes up to n threads waiting on addr and returns how many it woke.

The library (user/uthread.c): thread_create(fn, arg) (fn returns the exit status), thread_join(&status), and struct mutex with mutex_lock/mutex_unlock. An uncontended lock and unlock make no system call.

Semantics to decide and keep. wait must never return a thread and join never a child process. The process ends when its first thread exits (the one its parent waits for), and a kill or a fatal fault in any thread ends every thread. Every thread may call sbrk and touch lazily allocated memory at the same time as the others. A process may have up to 8 threads alive (including zombies not yet joined).

What must not change. Single-threaded programs behave exactly as before: user memory may still reach up to TRAPFRAME (usertests lazy_sbrk checks the very last page), and usertests -q must print ALL TESTS PASSED on 3 harts.

The test program, threadtest, prints one line per check (output from the reference, 3 harts):

$ 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

create and join: 7 threads return 100…106; each status comes back exactly once through join, an eighth thread cannot be created, and a further join returns -1.
registers: 7 threads each make 2000 getpid calls; every call must return the thread’s own id, and the thread’s id and loop state (kept in callee-saved registers) and its counters (kept on its own stack) must survive the traps.
mutex: 7 threads each add 1 to a shared counter 20,000 times, slowly (read, a 200-iteration delay, write), under the mutex. The same without the mutex is printed for comparison and is not checked: how many updates get lost depends on how much the threads overlap.
ping-pong: two threads pass a turn back and forth 5000 times, each sleeping in futex_wait until the other wakes it.
sbrk: 7 threads each call sbrk(4096) 50 times at once; every page must be its caller’s alone, and the break must have moved by exactly 350 pages.
lazy: 7 threads write one byte each into the same 512 lazily allocated pages at once.
shared memory only grows: with a second thread alive, an eager sbrk of 128 MiB (more than the machine has) fails and leaves the break where it was, and sbrk(-4096) and exec fail; alone again, shrinking works.
wait and join: with one child process and one thread, each call returns only its own kind.
stress: 20 rounds of 7 threads doing mutex increments, lazy sbrk and a fork+wait each.
exit / kill ends all threads: a child whose first thread exits (or is killed) while other threads spin or sleep; the parent’s wait returns, and the free page count comes back to its starting value once init has reaped the rest.
no leaks: free pages counted with sbrk before and after are equal.

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 a thread share, and what must it own?

Two threads of one process run on two harts at the same time, in the same address space. Go through struct proc (kernel/proc.h:82) field by field: which fields can stay per thread, and which describe something the threads must share, so that a change by one is seen by all? Commit to a list before the hints, and think about what happens to the shared part when one thread exits.

Check yourself

1warm-upChoose all that apply

Which of these must exist once per thread, not once per address space, when two threads of a process run on two harts at once?

2Where does each thread's trapframe live, and how does uservec find it?

The trapframe page is mapped at TRAPFRAME in every user page table (kernel/proc.c:197), and uservec finds it with li a0, TRAPFRAME (kernel/trampoline.S:37). Two threads share one page table now. Where does the second thread’s trapframe go, and how does the trap entry code, which may not touch a single register before saving it, learn which one to use?

Check yourself

1solidType a number

On the reference branch, TRAPFRAME is 0x3fffffe000 and TFSIZE is 512. gdb stopped uservec right after its first instruction, in the thread that lives in slot 1. What value does a0 hold? (Hex is fine.)

decimal, 0x hex or 0b binary

2deepFill in the machine state

A thread in slot 1 executes ecall. Fill in the machine state at the instruction right after csrrw a0, sscratch, a0, the first instruction of uservec.

Privilege modeActive stackPage table (satp)Interrupts (sstatus.SIE)

3When can a shared page table be freed?

In this tree freeproc frees a process’s page table and all its user memory when its parent reaps it (kernel/proc.c:161). Now four threads share one page table. Thread A exits and its creator joins it. What must freeproc do with the page table, the trapframe page and the user memory? Decide who frees them, when, and what has to be read under which lock.

Check yourself

1solidTrue or false, and why

True or false: in the reference, a thread that has called exit but has not yet been joined still holds its reference to the address space.

TrueFalse

Why?

The scheduler drops it when it switches away from the zombie.kexit cannot drop the reference because it still runs on the user stack.dropvm runs from freeproc, which the joiner (or init) calls when it reaps the zombie.

4Who reaps a thread, and what ends a process?

A shell runs a threaded program and calls wait. The program’s first thread created three threads. Which of these four struct procs may wait return? What should join return if the caller also forked a child process? And what should happen to the three threads when the first thread calls exit(0), or when the shell’s user types Ctrl-C (kill)?

Check yourself

1solidChoose one

The first thread of a process forks a child process and creates a thread. The child process exits at once; the thread is still running. The first thread calls join(&st). What happens in the reference?

join reaps both, the zombie first.join returns the child process’s pid at once, because it is a zombie.join sleeps until the thread exits, then returns its id; the child process stays a zombie until wait is called.join returns -1, because the caller has a child process.

5Two threads change the address space at once

With threads, several harts can run system calls and page faults on the same page table at the same moment. List every place that changes a page table or sz. For each, what happens if two threads run it at the same time with no lock? Then the hard part: copyin, copyout and the hardware’s own page walker read the page table without any lock. What rule makes that safe, and what does it forbid?

The reference design

The races. We produced the first two on 3 harts (clinics 4 and 5); the fork row is reasoned from the code:

code	race	result
`sbrk`	two threads read the same `sz`	both get the same address; with eager `sbrk` both map the same page: `panic: mappages: remap`
lazy fault	two threads touch an unmapped page	both map it (`remap` panic), or the second sees it mapped, `vmfault` returns 0, and the thread is killed
`fork`	another thread grows memory during `uvmcopy`	a copy of a half-changed page table

The reference adds vm->lock (a spinlock) and takes it around each of them. growproc now does both kinds of sbrk and returns the old size, so reading the break and moving it is one critical section. vmfault does its check-and-map under the lock, and when the page is already mapped it returns success if the PTE allows the access (PTE_U and PTE_R or PTE_W): that is the winner’s page. A store to text or a touch of the guard page still fails, as before. kfork holds the parent’s vm->lock for the copy.

Readers take no lock. copyout may be halfway through a memmove into a user page; the hardware walker may be fetching through any PTE, and another hart’s TLB may still hold a translation (there is no cross-hart TLB flush in this tree). That is safe only because, while an address space is shared, pages are only ever added: nothing unmaps or frees a user page under them. Three things would break that rule, so the reference changes them when vm->ref > 1: sbrk(-n) (shrinking frees pages) and exec (replaces the whole page table) are refused, and an eager sbrk no longer uses uvmalloc, whose failure path unmaps and frees the pages it had already mapped in the same call (kernel/vm.c:230). Instead uvmgrow first creates the page-table pages, then takes every physical page it needs, and maps them only when all are in hand; if memory runs out, it gives the pages back before any was mapped. A sz read without the lock can then only be too small, never too large. (Simplified: on hardware with a weaker memory order than QEMU’s on this host, walk would also need a fence between zeroing a new page-table page and linking it, so that a lock-free reader never sees the link before the zeros.)

Lock order: p->lock before vm->lock (allocproc, freeproc, kwait’s copyout), and vm->lock before kmem.lock. Nothing takes a p->lock while holding vm->lock.

Check yourself

1deepChoose one

Remove only the lock from growproc (everything else as in the reference). Seven threads each call sbrk(4096) (eager) 50 times at once on 3 harts. What is the worst outcome the race can produce?

A deadlock, because both threads spin on kmem.lock.Two threads get the same memory, and the test finds the overlap.panic: mappages: remap, when two threads both map the page at the same old breakNothing: sbrk is a system call, and system calls on one process are serialized.

6Sleeping on a word of user memory without losing the wakeup

A mutex holder releases the lock and wants to wake one sleeping waiter. The waiter decided to sleep because it saw the word still locked. In this tree, sleeping is sleep_prepare then sleep, and waking is wakeup (kernel/proc.c:546 to kernel/proc.c:595). In what order must futex_wait register itself and look at the user word, and does it need a lock of its own around the two? What sleep channel do all threads agree on?

The reference design

Register, then look. With the order reversed (look, then register), a wakeup that falls between the two finds nobody registered, and the waiter then sleeps on a word that will never be woken again: clinic 3, both ping-pong threads asleep for ever. With the reference order, every futex_wake either comes before the waiter’s look (then the look sees the new value, since the waker stored it first) or after the registration (then wakeup-style code finds p->chan set, clears it, and the sleep that follows returns at once). The lost wakeup cannot happen.

No extra lock. The ordering comes from p->lock, which sleep_prepare takes to set p->chan and the waker’s scan takes to read it. If the scan takes this thread’s p->lock after sleep_prepare released it, it sees the registration. If it took it before, then sleep_prepare’s acquire comes after the scan’s release, and the waker’s store to the user word (which came before its system call, before that release) is visible to the look that follows. Either way one side sees the other.

The channel is the word’s physical address: the same for every thread of the process (they share one page table), and different from every kernel channel, which point into kernel memory.

Two more details. A thread that decides not to sleep must clear p->chan (kernel/uart.c:86 leaves it set, harmlessly, because nothing counts uart wakeups), otherwise futex_wake(addr, 1) could spend its one wakeup on a thread that is not waiting.

And a kill has the same gap as a wakeup. futex_wait checks killed(p) after registering, but a kill that lands between that check and sleep only sets killed: kkill makes a thread RUNNABLE only if it is already SLEEPING. The thread then sleeps on a word nobody may ever change, never exits, and its address space is never freed. The reference closes the gap the same way as for wakeups: kkill and killthreads also clear p->chan, so that sleep returns at once. Every sleeper in this tree re-checks its condition (and killed) in a loop, so the extra return is harmless. We did not catch the original gap in a normal run (it is a few instructions wide), but with a scratch delay of 5 ticks between the check and sleep it lost the kill every time:

$ lostkill
lostkill: child 4 exited with 5
lostkill: free pages 32470 before, 32458 after: FAIL
$
1 sleep  init
2 sleep  sh
5 sleep  lostkill

(lostkill, a scratch program, forks a child whose thread blocks in futex_wait while the child’s first thread exits; the last three lines are Ctrl-P’s process list: pid 5, the thread, asleep for ever, its 12 pages lost.) The same delay on the reference kernel printed 32470 before, 32470 after: OK, with no lostkill left in the list, in both runs.

Check yourself

1solidPut in order

Put the steps of the reference futex_wait(addr, val) in order.

sleep_prepare(chan)
Find the channel: copyin the word (faulting in a lazy page) and take its physical address
If equal and not killed: sleep()
copyin the word again and compare it with val

2solidChoose one

On the reference, gdb stopped in futex_wake with n = 1 and found the waiting thread (pid 21) on the channel but in state RUNNING, not SLEEPING. What does the reference do with it?

Skips it, because only SLEEPING threads can be woken, and looks for another.Clears its p->chan and counts it as woken; its sleep() will return at once.Waits for it to reach sleep() and then makes it RUNNABLE.

7A mutex that usually needs no system call

With futex_wait and futex_wake, write mutex_lock and mutex_unlock. The common case (nobody else wants the lock) must use no system call at all, and an unlock must never miss a sleeping waiter. How many values does the lock word need?

Check yourself

1warm-upType a number

A single thread locks and unlocks a reference struct mutex 1000 times, with no other thread alive. How many system calls do mutex_lock and mutex_unlock make in total?

decimal, 0x hex or 0b binary

3. Build it

Start.

git checkout -b my-threads 06aad25

Add threadtest early, even before the system calls exist (declare them in user/user.h, add them to user/usys.pl, and let the kernel return -1). It will fail everywhere; each milestone makes more of it pass.

Milestones, in an order that keeps usertests -q passing after each one.

struct vm. Move sz into it, with ref and a spinlock; every p->sz in the kernel becomes p->vm->sz; allocproc takes a vm from a static table; freeproc drops the reference and the last one frees the page table. Every vm has one user. Test: usertests -q.
The trampoline. Put the trapframe address in sscratch in prepare_return and make uservec and userret use it (still TRAPFRAME). If you get this wrong, the very first return to user space fails: the machine hangs at boot or init dies. Test: boot and usertests -q.
Trapframe slots. The trapframe page moves into the vm; a thread’s trapframe is a slot in it. Test: usertests -q.
clone. allocproc either makes a new vm or joins an existing one in a free slot. A thread is reaped by wait for now. Test: a small program whose threads each print their pid (only from the main thread, or the characters interleave), then usertests -q.
join, and wait without threads. Test: threadtest create and join.
Locks for the shared address space, then the exit/kill rules, then the futexes, then the library. Run all of threadtest and usertests -q, several times.

Debugging advice. Run with make qemu-gdb CPUS=3 and attach gdb from a second terminal when you need to look inside. A race that threadtest hits once in twenty runs is real: run it in a loop and keep the logs.

A silent hang (no panic, no prompt): attach gdb and run info threads and thread apply all bt. A hart stuck at 0x3ffffff000 (the first instruction of uservec) with scause = 12 is fetching the trampoline through a broken page table (clinic 2). All harts idle in scheduler means every thread is asleep: print each proc’s pid, state and chan, and the user word at chan (it is a physical address, which the kernel’s direct map lets gdb read): a futex sleeper whose word already has the value it waited for has lost its wakeup (clinic 3).
usertrap(): unexpected scause 0xc with a sepc that is not a code address means a thread returned to user space with someone else’s registers (clinic 1). Check which slot each thread’s p->trapframe points to and what sscratch holds at userret (hbreak *0x3ffffff0a8 stops just after it is read).
panic: mappages: remap in a threaded program: two harts mapped the same page; find which path took no vm->lock (clinics 4 and 5).
Threads made RUNNABLE do not start at once on an idle hart: an idle hart sits in wfi until its next timer interrupt (this tree sends no interrupt to other harts), up to a tenth of a second. Short tests may therefore run their threads one after another. Make stress tests long enough to overlap.

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.

1Every thread uses the same trapframe

The trampoline and the slots are in place, but every thread is given slot 0:

-  p->trapframe = (struct trapframe *)(p->vm->tfpage + p->slot * TFSIZE);
+  p->trapframe = (struct trapframe *)p->vm->tfpage;

and prepare_return writes TRAPFRAME into sscratch for everyone. This is what you get if you share the page table and leave the trapframe mapping alone.

What happened when we ran it

$ threadtest
usertrap(): unexpected scause 0xc pid=4
usertrap(): unexpected scause 0xc pid=5
            sepc=0x67179a0010800e0 stval=0x67179a0010800e0
            sepc=0x67179a0010800e0 stval=0x67179a0010800e0
threadtest: the process running the tests was killed
usertrap(): unexpected scause 0xc pid=6
            sepc=0x22f4067179a00108 stval=0x22f4067179a00108
usertrap(): unexpected scause 0xc pid=7
            sepc=0x22f4067179a00108 stval=0x22f4067179a00108
threadtest: exit ends all threads: FAIL
usertrap(): unexpected scause 0xc pid=8
            sepc=0x26f022f4067179a0 stval=0x26f022f4067179a0
usertrap(): unexpected scause 0xc pid=9
            sepc=0x26f022f4067179a0 stval=0x26f022f4067179a0
threadtest: kill ends all threads: OK
threadtest: free pages 32469 before, 32469 after
threadtest: no leaks: OK
threadtest: SOME TESTS FAILED
$

2The first thread to be reaped frees the page table

freeproc frees the page table and user memory whenever it reaps any thread, as the original code did for a process; only the trapframe page waits for the last reference:

-  if (ref == 0) {
-    if (p->pagetable)
-      proc_freepagetable(p->pagetable, sz);
-    kfree(tf);
-  }
+  if (p->pagetable)
+    proc_freepagetable(p->pagetable, sz);
+  if (ref == 0)
+    kfree(tf);

What happened when we ran it

$ threadtest

(nothing more: no output, no panic, no prompt. gdb attached after 120 s:)

  Id   Target Id                    Frame
* 1    Thread 1.1 (CPU#0 [halted ]) s_sstatus (x=2) at kernel/riscv.h:67
  2    Thread 1.2 (CPU#1 [halted ]) s_sstatus (x=2) at kernel/riscv.h:67
  3    Thread 1.3 (CPU#2 [running]) 0x0000003ffffff000 in ?? ()
[...]
Thread 3 (Thread 1.3 (CPU#2 [running])):
$1 = 0xc
[...]
Thread 3 (Thread 1.3 (CPU#2 [running])):
$4 = 0x3ffffff000
[...]
Thread 3 (Thread 1.3 (CPU#2 [running])):
$7 = 0x3ffffff000
[...]
Thread 3 (Thread 1.3 (CPU#2 [running])):
$10 = 0x8000000000080024

(the four values are scause, sepc, stvec and satp of the stuck hart, hart 2. The
process table, read through a halted hart:)

slot 0 pid 1 state 2 chan 0x80011c00 killed 0 thread 0 tslot 0 name init vm 0x80010e00
slot 1 pid 2 state 2 chan 0x80011d70 killed 0 thread 0 tslot 0 name sh vm 0x80010e38
slot 2 pid 3 state 2 chan 0x80011ee0 killed 0 thread 0 tslot 0 name threadtest vm 0x80010e70
slot 3 pid 4 state 4 chan (nil) killed 0 thread 0 tslot 0 name threadtest vm 0x80010ea8
slot 5 pid 6 state 5 chan (nil) killed 0 thread 1 tslot 2 name threadtest vm 0x80010ea8
[...]
slot 10 pid 11 state 5 chan (nil) killed 0 thread 1 tslot 7 name threadtest vm 0x80010ea8

3futex_wait looks at the word before registering

-  sleep_prepare(chan);
   if (copyin(p->pagetable, p->vm->sz, (char *)&x, addr, sizeof(x)) < 0)
     r = -1;
   else if (x != val)
     r = 0;
   else if (killed(p))
     r = -1;
   else {
+    sleep_prepare(chan);
     sleep();
     return 0;
   }

It looks harmless: register only when you are really going to sleep.

What happened when we ran it

$ threadtest
threadtest: create and join: OK
threadtest: registers: OK
threadtest: mutex: 140000 of 140000
threadtest: mutex: OK
threadtest: without the mutex: 140000 of 140000 (not checked)

(nothing more for 240 s. gdb: all three harts idle in scheduler; the process table:)

[...]
slot 2 pid 3 state 2 chan 0x80011ee0 killed 0 thread 0 tslot 0 name threadtest vm 0x80010e70
   word at chan: 0
slot 3 pid 4 state 2 chan 0x80012050 killed 0 thread 0 tslot 0 name threadtest vm 0x80010ea8
   word at chan: 0
slot 4 pid 34 state 2 chan 0x8002b010 killed 0 thread 1 tslot 1 name threadtest vm 0x80010ea8
   word at chan: 1
slot 5 pid 35 state 2 chan 0x8002b010 killed 0 thread 1 tslot 2 name threadtest vm 0x80010ea8
   word at chan: 1

Rare: this bug hung threadtest in 1 of 24 runs (the others printed ALL OK); in other runs of it we also saw it hang in the mutex test. gdb found nothing running: pids 34 and 35, the two ping-pong threads, are both SLEEPING (state 2) on channel 0x8002b010, the physical address of turn (user address 0x2010, in the page at 0x8002b000). The word holds 1: it is thread 1’s turn. Yet thread 1 (pid 35) sleeps in futex_wait(&turn, 0), waiting for a value the word no longer has. (pid 4 sleeps in join, pid 3 in wait; their channels are kernel addresses, and the “word” gdb printed there means nothing.)

The interleaving that produced it:

time	hart A: thread 1 (pid 35)	hart B: thread 0 (pid 34)
1	`futex_wait(&turn, 0)`: copyin reads `turn` = 0
2		stores `turn = 1`, calls `futex_wake(&turn, 1)`
3		scan finds no thread with `chan` = `0x8002b010`: wakes nobody
4	`sleep_prepare(chan)`, `sleep()`: SLEEPING
5		waits for `turn == 0`: `futex_wait(&turn, 1)` reads 1, sleeps

Each thread now waits for the other. In the mutex test the same lost wakeup is often repaired by luck: another contender writes 2 into the mutex word and a later unlock wakes the forgotten sleeper. That is why the hang is rare and why the test that hands a turn between exactly two threads is the one that catches it. With the reference order, step 4’s registration comes before step 1’s look, and step 3 would have found and cleared it (Tour 16: sleep and wakeup, and the lost-wakeup problem is the same story inside the kernel).

4sbrk without the address-space lock

growproc without acquire(&vm->lock) and its two releases; everything else as in the reference (so vmfault still locks).

What happened when we ran it

$ threadtest
threadtest: create and join: OK
threadtest: registers: OK
threadtest: mutex: 140000 of 140000
threadtest: mutex: OK
threadtest: without the mutex: 140000 of 140000 (not checked)
threadtest: ping-pong: OK
ppanic: amappages: remapnic: mappages: remap

5vmfault as in the original tree

vmfault left unchanged from the original kernel: no vm->lock, and an already-mapped page means failure:

-  acquire(&vm->lock);
   if (ismapped(pagetable, va)) {
-    // another thread may have mapped it a moment ago: ...
-    pte = walk(pagetable, va, 0);
-    mem = 0;
-    if ((*pte & PTE_U) && (*pte & (read ? PTE_R : PTE_W)))
-      mem = PTE2PA(*pte);
-    release(&vm->lock);
-    return mem;
+    return 0;
   }

What happened when we ran it

$ threadtest
threadtest: create and join: OK
threadtest: registers: OK
threadtest: mutex: 140000 of 140000
threadtest: mutex: OK
threadtest: without the mutex: 108025 of 140000 (not checked)
threadtest: ping-pong: OK
threadtest: sbrk: OK
usertrap(): unexpected scause 0xf pid=44
            sepc=0x320 stval=0x25c001
usertrap(): unexpected scause 0xf pid=47
            sepc=0x320 stval=0x268004
threadtest: the process running the tests was killed
threadtest: exit ends all threads: OK
threadtest: kill ends all threads: OK
threadtest: free pages 32469 before, 32469 after
threadtest: no leaks: OK
threadtest: SOME TESTS FAILED
$

6join takes any child

The vm test is applied in one direction only: wait skips threads, but join accepts any child:

-        if ((pp->vm == p->vm) != threads) {
+        if (!threads && pp->vm == p->vm) {

What happened when we ran it

$ threadtest
threadtest: create and join: OK
threadtest: registers: OK
threadtest: mutex: 140000 of 140000
threadtest: mutex: OK
threadtest: without the mutex: 122186 of 140000 (not checked)
threadtest: ping-pong: OK
threadtest: sbrk: OK
threadtest: lazy: OK
threadtest: shared memory only grows: OK
threadtest: wait and join: FAIL
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: SOME TESTS FAILED
$

5. The reference solution

Take the guided tour through the reference solution, one commit at a time, with the machine state at every step:

Open the reveal tour →

Or read the commits

12c53d6 Move the user memory size into a shared struct vm
kernel/exec.c
@@ -80,9 +80,9 @@ kexec(char *path, char **argv)
8080 end_op();
8181 ip = 0;
8282
8383 p = myproc();
84 uint64 oldsz = p->sz;
84 uint64 oldsz = p->vm->sz;
8585
8686 // Allocate some pages at the next page boundary.
8787 // Make the first inaccessible as a stack guard.
8888 // Use the rest as the user stack.
@@ -131,9 +131,9 @@ kexec(char *path, char **argv)
131131
132132 // Commit to the user image.
133133 oldpagetable = p->pagetable;
134134 p->pagetable = pagetable;
135 p->sz = sz;
135 p->vm->sz = sz;
136136 p->trapframe->epc = elf.entry; // initial program counter = ulib.c:start()
137137 p->trapframe->sp = sp; // initial stack pointer
138138 proc_freepagetable(oldpagetable, oldsz);
139139
kernel/file.c
@@ -93,9 +93,9 @@ filestat(struct file *f, uint64 addr)
9393 if (f->type == FD_INODE || f->type == FD_DEVICE) {
9494 ilock(f->ip);
9595 stati(f->ip, &st);
9696 iunlock(f->ip);
97 if (copyout(p->pagetable, p->sz, addr, (char *)&st, sizeof(st)) < 0)
97 if (copyout(p->pagetable, p->vm->sz, addr, (char *)&st, sizeof(st)) < 0)
9898 return -1;
9999 return 0;
100100 }
101101 return -1;
kernel/pipe.c
@@ -92,9 +92,9 @@ pipewrite(struct pipe *pi, uint64 addr, int n)
9292 sleep();
9393 acquire(&pi->lock);
9494 } else {
9595 char ch;
96 if (copyin(pr->pagetable, pr->sz, &ch, addr + i, 1) == -1) {
96 if (copyin(pr->pagetable, pr->vm->sz, &ch, addr + i, 1) == -1) {
9797 if (i == 0)
9898 i = -1;
9999 break;
100100 }
@@ -129,9 +129,9 @@ piperead(struct pipe *pi, uint64 addr, int n)
129129 for (i = 0; i < n; i++) { //DOC: piperead-copy
130130 if (pi->nread == pi->nwrite)
131131 break;
132132 ch = pi->data[pi->nread % PIPESIZE];
133 if (copyout(pr->pagetable, pr->sz, addr + i, &ch, 1) == -1) {
133 if (copyout(pr->pagetable, pr->vm->sz, addr + i, &ch, 1) == -1) {
134134 if (i == 0)
135135 i = -1;
136136 break;
137137 }
kernel/proc.c
@@ -9,8 +9,12 @@
99struct cpu cpus[NCPU];
1010
1111struct proc proc[NPROC];
1212
13// one address space per process; a process has at least one
14// thread, so NPROC is always enough.
15struct vm vms[NPROC];
16
1317struct proc *initproc;
1418
1519int nextpid = 1;
1620struct spinlock pid_lock;
@@ -47,16 +51,19 @@ proc_mapstacks(pagetable_t kpgtbl)
4751void
4852procinit(void)
4953{
5054 struct proc *p;
55 struct vm *vm;
5156
5257 initlock(&pid_lock, "nextpid");
5358 initlock(&wait_lock, "wait_lock");
5459 for (p = proc; p < &proc[NPROC]; p++) {
5560 initlock(&p->lock, "proc");
5661 p->state = UNUSED;
5762 p->kstack = KSTACK((int)(p - proc));
5863 }
64 for (vm = vms; vm < &vms[NPROC]; vm++)
65 initlock(&vm->lock, "vm");
5966}
6067
6168// Must be called with interrupts disabled,
6269// to prevent race with process being moved
@@ -101,8 +108,44 @@ allocpid()
101108
102109 return pid;
103110}
104111
112// Find an unused address space and give it one user.
113static struct vm *
114allocvm(void)
115{
116 struct vm *vm;
117
118 for (vm = vms; vm < &vms[NPROC]; vm++) {
119 acquire(&vm->lock);
120 if (vm->ref == 0) {
121 vm->ref = 1;
122 vm->sz = 0;
123 release(&vm->lock);
124 return vm;
125 }
126 release(&vm->lock);
127 }
128 return 0;
129}
130
131// Drop p's reference to its address space. The last
132// thread out frees the page table and the user memory.
133static void
134dropvm(struct proc *p)
135{
136 struct vm *vm = p->vm;
137 uint64 sz;
138 int ref;
139
140 acquire(&vm->lock);
141 ref = --vm->ref;
142 sz = vm->sz; // read before another allocvm() can reuse vm
143 release(&vm->lock);
144 if (ref == 0 && p->pagetable)
145 proc_freepagetable(p->pagetable, sz);
146}
147
105148// Look in the process table for an UNUSED proc.
106149// If found, initialize state required to run in the kernel,
107150// and return with p->lock held.
108151// If there are no free procs, or a memory allocation fails, return 0.
@@ -131,9 +174,14 @@ found:
131174 release(&p->lock);
132175 return 0;
133176 }
134177
135 // An empty user page table.
178 // A new address space with an empty user page table.
179 if ((p->vm = allocvm()) == 0) {
180 freeproc(p);
181 release(&p->lock);
182 return 0;
183 }
136184 p->pagetable = proc_pagetable(p);
137185 if (p->pagetable == 0) {
138186 freeproc(p);
139187 release(&p->lock);
@@ -157,12 +205,12 @@ freeproc(struct proc *p)
157205{
158206 if (p->trapframe)
159207 kfree((void *)p->trapframe);
160208 p->trapframe = 0;
161 if (p->pagetable)
162 proc_freepagetable(p->pagetable, p->sz);
209 if (p->vm)
210 dropvm(p);
211 p->vm = 0;
163212 p->pagetable = 0;
164 p->sz = 0;
165213 p->pid = 0;
166214 p->name[0] = 0;
167215 p->chan = 0;
168216 p->killed = 0;
@@ -237,9 +285,9 @@ growproc(int n)
237285{
238286 uint64 sz;
239287 struct proc *p = myproc();
240288
241 sz = p->sz;
289 sz = p->vm->sz;
242290 if (n > 0) {
243291 if (sz + n > TRAPFRAME) {
244292 return -1;
245293 }
@@ -248,9 +296,9 @@ growproc(int n)
248296 }
249297 } else if (n < 0) {
250298 sz = uvmdealloc(p->pagetable, sz, sz + n);
251299 }
252 p->sz = sz;
300 p->vm->sz = sz;
253301 return 0;
254302}
255303
256304// Create a new process, copying the parent.
@@ -267,14 +315,14 @@ kfork(void)
267315 return -1;
268316 }
269317
270318 // Copy user memory from parent to child.
271 if (uvmcopy(p->pagetable, np->pagetable, p->sz) < 0) {
319 if (uvmcopy(p->pagetable, np->pagetable, p->vm->sz) < 0) {
272320 freeproc(np);
273321 release(&np->lock);
274322 return -1;
275323 }
276 np->sz = p->sz;
324 np->vm->sz = p->vm->sz;
277325
278326 // copy saved user registers.
279327 *(np->trapframe) = *(p->trapframe);
280328
@@ -387,9 +435,9 @@ kwait(uint64 addr)
387435 if (pp->state == ZOMBIE) {
388436 // Found one.
389437 pid = pp->pid;
390438 if (addr != 0 &&
391 copyout(p->pagetable, p->sz, addr, (char *)&pp->xstate,
439 copyout(p->pagetable, p->vm->sz, addr, (char *)&pp->xstate,
392440 sizeof(pp->xstate)) < 0) {
393441 release(&pp->lock);
394442 release(&wait_lock);
395443 return -1;
@@ -647,9 +695,9 @@ int
647695either_copyout(int user_dst, uint64 dst, void *src, uint64 len)
648696{
649697 struct proc *p = myproc();
650698 if (user_dst) {
651 return copyout(p->pagetable, p->sz, dst, src, len);
699 return copyout(p->pagetable, p->vm->sz, dst, src, len);
652700 } else {
653701 memmove((char *)dst, src, len);
654702 return 0;
655703 }
@@ -662,9 +710,9 @@ int
662710either_copyin(void *dst, int user_src, uint64 src, uint64 len)
663711{
664712 struct proc *p = myproc();
665713 if (user_src) {
666 return copyin(p->pagetable, p->sz, dst, src, len);
714 return copyin(p->pagetable, p->vm->sz, dst, src, len);
667715 } else {
668716 memmove(dst, (char *)src, len);
669717 return 0;
670718 }
kernel/proc.h
@@ -77,8 +77,16 @@ struct trapframe {
7777};
7878
7979enum procstate { UNUSED, USED, SLEEPING, RUNNABLE, RUNNING, ZOMBIE };
8080
81// A user address space. Every thread of a process points to
82// the same one; the last thread to go frees the page table.
83struct vm {
84 struct spinlock lock;
85 int ref; // threads using this address space
86 uint64 sz; // size of user memory (bytes)
87};
88
8189// Per-process state
8290struct proc {
8391 struct spinlock lock;
8492
@@ -93,10 +101,10 @@ struct proc {
93101 struct proc *parent; // Parent process
94102
95103 // these are private to the process, so p->lock need not be held.
96104 uint64 kstack; // Virtual address of kernel stack
97 uint64 sz; // Size of process memory (bytes)
98 pagetable_t pagetable; // User page table
105 struct vm *vm; // Address space, shared by threads
106 pagetable_t pagetable; // User page table (the vm's)
99107 struct trapframe *trapframe; // data page for trampoline.S
100108 struct context context; // swtch() here to run process
101109 struct file *ofile[NOFILE]; // Open files
102110 struct inode *cwd; // Current directory
kernel/syscall.c
@@ -11,12 +11,12 @@
1111int
1212fetchaddr(uint64 addr, uint64 *ip)
1313{
1414 struct proc *p = myproc();
15 if (addr >= p->sz ||
16 addr + sizeof(uint64) > p->sz) // both tests needed, in case of overflow
15 // both tests needed, in case of overflow
16 if (addr >= p->vm->sz || addr + sizeof(uint64) > p->vm->sz)
1717 return -1;
18 if (copyin(p->pagetable, p->sz, (char *)ip, addr, sizeof(*ip)) != 0)
18 if (copyin(p->pagetable, p->vm->sz, (char *)ip, addr, sizeof(*ip)) != 0)
1919 return -1;
2020 return 0;
2121}
2222
@@ -25,9 +25,9 @@ fetchaddr(uint64 addr, uint64 *ip)
2525int
2626fetchstr(uint64 addr, char *buf, int max)
2727{
2828 struct proc *p = myproc();
29 if (copyinstr(p->pagetable, p->sz, buf, addr, max) < 0)
29 if (copyinstr(p->pagetable, p->vm->sz, buf, addr, max) < 0)
3030 return -1;
3131 return strlen(buf);
3232}
3333
kernel/sysfile.c
@@ -516,10 +516,11 @@ sys_pipe(void)
516516 fileclose(rf);
517517 fileclose(wf);
518518 return -1;
519519 }
520 if (copyout(p->pagetable, p->sz, fdarray, (char *)&fd0, sizeof(fd0)) < 0 ||
521 copyout(p->pagetable, p->sz, fdarray + sizeof(fd0), (char *)&fd1,
520 if (copyout(p->pagetable, p->vm->sz, fdarray, (char *)&fd0, sizeof(fd0)) <
521 0 ||
522 copyout(p->pagetable, p->vm->sz, fdarray + sizeof(fd0), (char *)&fd1,
522523 sizeof(fd1)) < 0) {
523524 p->ofile[fd0] = 0;
524525 p->ofile[fd1] = 0;
525526 fileclose(rf);
kernel/sysproc.c
@@ -44,9 +44,9 @@ sys_sbrk(void)
4444 int n;
4545
4646 argint(0, &n);
4747 argint(1, &t);
48 addr = myproc()->sz;
48 addr = myproc()->vm->sz;
4949
5050 if (t == SBRK_EAGER || n < 0) {
5151 if (growproc(n) < 0) {
5252 return -1;
@@ -58,9 +58,9 @@ sys_sbrk(void)
5858 if (addr + n < addr)
5959 return -1;
6060 if (addr + n > TRAPFRAME)
6161 return -1;
62 myproc()->sz += n;
62 myproc()->vm->sz += n;
6363 }
6464 return addr;
6565}
6666
kernel/trap.c
@@ -68,9 +68,9 @@ usertrap(void)
6868 syscall();
6969 } else if ((which_dev = devintr()) != 0) {
7070 // ok
7171 } else if ((r_scause() == 15 || r_scause() == 13) &&
72 vmfault(p->pagetable, p->sz, r_stval(),
72 vmfault(p->pagetable, p->vm->sz, r_stval(),
7373 (r_scause() == 13) ? 1 : 0) != 0) {
7474 // page fault on lazily-allocated page
7575 } else {
7676 printk("usertrap(): unexpected scause 0x%lx pid=%d\n", r_scause(), p->pid);
5b063f6 Find the trapframe through sscratch, not a constant
kernel/riscv.h
@@ -190,8 +190,15 @@ r_stvec()
190190 asm volatile("csrr %0, stvec" : "=r"(x));
191191 return x;
192192}
193193
194// Supervisor Scratch: user traps find their trapframe here
195static inline void
196w_sscratch(uint64 x)
197{
198 asm volatile("csrw sscratch, %0" : : "r"(x));
199}
200
194201// Supervisor Timer Comparison Register
195202static inline uint64
196203r_stimecmp()
197204{
kernel/trampoline.S
@@ -26,18 +26,15 @@ uservec:
2626 # in supervisor mode, but with a
2727 # user page table.
2828 #
2929
30 # save user a0 in sscratch so
31 # a0 can be used to get at TRAPFRAME.
32 csrw sscratch, a0
33
34 # each process has a separate p->trapframe memory area,
35 # but it's mapped to the same virtual address
36 # (TRAPFRAME) in every process's user page table.
37 li a0, TRAPFRAME
38
39 # save the user registers in TRAPFRAME
30 # swap a0 and sscratch: a0 now holds the user virtual
31 # address of this thread's trapframe, which
32 # prepare_return() put in sscratch, and sscratch
33 # holds the user's a0.
34 csrrw a0, sscratch, a0
35
36 # save the user registers in the trapframe
4037 sd ra, 40(a0)
4138 sd sp, 48(a0)
4239 sd gp, 56(a0)
4340 sd tp, 64(a0)
@@ -110,11 +107,13 @@ userret:
110107 sfence.vma zero, zero
111108 csrw satp, a0
112109 sfence.vma zero, zero
113110
114 li a0, TRAPFRAME
111 # the trapframe's address, left in sscratch by
112 # prepare_return() for the next trap too.
113 csrr a0, sscratch
115114
116 # restore all but a0 from TRAPFRAME
115 # restore all but a0 from the trapframe
117116 ld ra, 40(a0)
118117 ld sp, 48(a0)
119118 ld gp, 56(a0)
120119 ld tp, 64(a0)
kernel/trap.c
@@ -117,8 +117,12 @@ prepare_return(void)
117117 p->trapframe->kernel_sp = p->kstack + PGSIZE; // process's kernel stack
118118 p->trapframe->kernel_trap = (uint64)usertrap;
119119 p->trapframe->kernel_hartid = r_tp(); // hartid for cpuid()
120120
121 // where uservec and userret find the trapframe, as a
122 // user virtual address.
123 w_sscratch(TRAPFRAME);
124
121125 // set up the registers that trampoline.S's sret will use
122126 // to get to user space.
123127
124128 // set S Previous Privilege mode to User.
34ee0f3 Give each thread a trapframe slot in one shared page
kernel/memlayout.h
@@ -60,4 +60,9 @@
6060// ...
6161// TRAPFRAME (p->trapframe, used by the trampoline)
6262// TRAMPOLINE (the same page as in the kernel)
6363#define TRAPFRAME (TRAMPOLINE - PGSIZE)
64
65// the trapframe page holds one trapframe per thread:
66// thread slot i's is at TRAPFRAME + i*TFSIZE.
67#define TFSIZE 512
68#define NTHREAD (PGSIZE / TFSIZE)
kernel/proc.c
@@ -13,8 +13,10 @@ struct proc proc[NPROC];
1313// one address space per process; a process has at least one
1414// thread, so NPROC is always enough.
1515struct vm vms[NPROC];
1616
17_Static_assert(sizeof(struct trapframe) <= TFSIZE, "TFSIZE too small");
18
1719struct proc *initproc;
1820
1921int nextpid = 1;
2022struct spinlock pid_lock;
@@ -108,24 +110,31 @@ allocpid()
108110
109111 return pid;
110112}
111113
112// Find an unused address space and give it one user.
114// Find an unused address space and give it one user, with
115// a new trapframe page whose slot 0 that user takes.
113116static struct vm *
114117allocvm(void)
115118{
116119 struct vm *vm;
120 char *tf;
117121
122 if ((tf = kalloc()) == 0)
123 return 0;
118124 for (vm = vms; vm < &vms[NPROC]; vm++) {
119125 acquire(&vm->lock);
120126 if (vm->ref == 0) {
121127 vm->ref = 1;
122128 vm->sz = 0;
129 vm->tfpage = tf;
130 vm->slots = 1;
123131 release(&vm->lock);
124132 return vm;
125133 }
126134 release(&vm->lock);
127135 }
136 kfree(tf);
128137 return 0;
129138}
130139
131140// Drop p's reference to its address space. The last
@@ -134,16 +143,22 @@ static void
134143dropvm(struct proc *p)
135144{
136145 struct vm *vm = p->vm;
137146 uint64 sz;
147 char *tf;
138148 int ref;
139149
140150 acquire(&vm->lock);
151 vm->slots &= ~(1 << p->slot);
141152 ref = --vm->ref;
142153 sz = vm->sz; // read before another allocvm() can reuse vm
154 tf = vm->tfpage;
143155 release(&vm->lock);
144 if (ref == 0 && p->pagetable)
145 proc_freepagetable(p->pagetable, sz);
156 if (ref == 0) {
157 if (p->pagetable)
158 proc_freepagetable(p->pagetable, sz);
159 kfree(tf);
160 }
146161}
147162
148163// Look in the process table for an UNUSED proc.
149164// If found, initialize state required to run in the kernel,
@@ -167,21 +182,17 @@ allocproc(void)
167182found:
168183 p->pid = allocpid();
169184 p->state = USED;
170185
171 // Allocate a trapframe page.
172 if ((p->trapframe = (struct trapframe *)kalloc()) == 0) {
173 freeproc(p);
174 release(&p->lock);
175 return 0;
176 }
177
178 // A new address space with an empty user page table.
186 // A new address space with a trapframe page, of which this
187 // first thread uses slot 0, and an empty user page table.
179188 if ((p->vm = allocvm()) == 0) {
180189 freeproc(p);
181190 release(&p->lock);
182191 return 0;
183192 }
193 p->slot = 0;
194 p->trapframe = (struct trapframe *)p->vm->tfpage;
184195 p->pagetable = proc_pagetable(p);
185196 if (p->pagetable == 0) {
186197 freeproc(p);
187198 release(&p->lock);
@@ -202,11 +213,9 @@ found:
202213// p->lock must be held.
203214static void
204215freeproc(struct proc *p)
205216{
206 if (p->trapframe)
207 kfree((void *)p->trapframe);
208 p->trapframe = 0;
217 p->trapframe = 0; // the vm frees the trapframe page
209218 if (p->vm)
210219 dropvm(p);
211220 p->vm = 0;
212221 p->pagetable = 0;
@@ -241,9 +250,9 @@ proc_pagetable(struct proc *p)
241250 }
242251
243252 // map the trapframe page just below the trampoline page, for
244253 // trampoline.S.
245 if (mappages(pagetable, TRAPFRAME, PGSIZE, (uint64)(p->trapframe),
254 if (mappages(pagetable, TRAPFRAME, PGSIZE, (uint64)(p->vm->tfpage),
246255 PTE_R | PTE_W) < 0) {
247256 uvmunmap(pagetable, TRAMPOLINE, 1, 0);
248257 uvmfree(pagetable, 0);
249258 return 0;
kernel/proc.h
@@ -27,11 +27,12 @@ struct cpu {
2727};
2828
2929extern struct cpu cpus[NCPU];
3030
31// per-process data for the trap handling code in trampoline.S.
32// sits in a page by itself just under the trampoline page in the
33// user page table. not specially mapped in the kernel page table.
31// per-thread data for the trap handling code in trampoline.S.
32// one slot of TFSIZE bytes in the trapframe page, which sits just
33// under the trampoline page in the user page table. not specially
34// mapped in the kernel page table.
3435// uservec in trampoline.S saves user registers in the trapframe,
3536// then initializes registers from the trapframe's
3637// kernel_sp, kernel_hartid, kernel_satp, and jumps to kernel_trap.
3738// prepare_return() and userret in trampoline.S set up
@@ -81,10 +82,12 @@ enum procstate { UNUSED, USED, SLEEPING, RUNNABLE, RUNNING, ZOMBIE };
8182// A user address space. Every thread of a process points to
8283// the same one; the last thread to go frees the page table.
8384struct vm {
8485 struct spinlock lock;
85 int ref; // threads using this address space
86 uint64 sz; // size of user memory (bytes)
86 int ref; // threads using this address space
87 uint64 sz; // size of user memory (bytes)
88 char *tfpage; // trapframe page, mapped at TRAPFRAME
89 int slots; // bit i set: trapframe slot i is in use
8790};
8891
8992// Per-process state
9093struct proc {
@@ -103,9 +106,10 @@ struct proc {
103106 // these are private to the process, so p->lock need not be held.
104107 uint64 kstack; // Virtual address of kernel stack
105108 struct vm *vm; // Address space, shared by threads
106109 pagetable_t pagetable; // User page table (the vm's)
107 struct trapframe *trapframe; // data page for trampoline.S
110 int slot; // Trapframe slot in vm->tfpage
111 struct trapframe *trapframe; // data for trampoline.S, in that slot
108112 struct context context; // swtch() here to run process
109113 struct file *ofile[NOFILE]; // Open files
110114 struct inode *cwd; // Current directory
111115 char name[16]; // Process name (debugging)
kernel/trap.c
@@ -119,9 +119,9 @@ prepare_return(void)
119119 p->trapframe->kernel_hartid = r_tp(); // hartid for cpuid()
120120
121121 // where uservec and userret find the trapframe, as a
122122 // user virtual address.
123 w_sscratch(TRAPFRAME);
123 w_sscratch(TRAPFRAME + p->slot * TFSIZE);
124124
125125 // set up the registers that trampoline.S's sret will use
126126 // to get to user space.
127127
f532c40 Add clone: a new thread in the caller's address space
kernel/defs.h
@@ -81,8 +81,9 @@ void printkinit(void);
8181// proc.c
8282int cpuid(void);
8383void kexit(int);
8484int kfork(void);
85int kclone(uint64, uint64, uint64);
8586int growproc(int);
8687void proc_mapstacks(pagetable_t);
8788pagetable_t proc_pagetable(struct proc *);
8889void proc_freepagetable(pagetable_t, uint64);
kernel/proc.c
@@ -136,8 +136,28 @@ allocvm(void)
136136 kfree(tf);
137137 return 0;
138138}
139139
140// Add one more thread to vm: return a free trapframe slot
141// for it, or -1 if all NTHREAD slots are taken.
142static int
143sharevm(struct vm *vm)
144{
145 int i;
146
147 acquire(&vm->lock);
148 for (i = 0; i < NTHREAD; i++) {
149 if ((vm->slots & (1 << i)) == 0) {
150 vm->slots |= 1 << i;
151 vm->ref++;
152 release(&vm->lock);
153 return i;
154 }
155 }
156 release(&vm->lock);
157 return -1;
158}
159
140160// Drop p's reference to its address space. The last
141161// thread out frees the page table and the user memory.
142162static void
143163dropvm(struct proc *p)
@@ -161,12 +181,14 @@ dropvm(struct proc *p)
161181}
162182
163183// Look in the process table for an UNUSED proc.
164184// If found, initialize state required to run in the kernel,
165// and return with p->lock held.
185// and return with p->lock held. If vm is 0 it gets a new
186// address space; otherwise it is a new thread in vm, and the
187// caller sets p->pagetable.
166188// If there are no free procs, or a memory allocation fails, return 0.
167189static struct proc *
168allocproc(void)
190allocproc(struct vm *vm)
169191{
170192 struct proc *p;
171193
172194 for (p = proc; p < &proc[NPROC]; p++) {
@@ -182,19 +204,28 @@ allocproc(void)
182204found:
183205 p->pid = allocpid();
184206 p->state = USED;
185207
186 // A new address space with a trapframe page, of which this
187 // first thread uses slot 0, and an empty user page table.
188 if ((p->vm = allocvm()) == 0) {
189 freeproc(p);
190 release(&p->lock);
191 return 0;
208 if (vm == 0) {
209 // A new address space with a trapframe page, of which this
210 // first thread uses slot 0, and an empty user page table.
211 if ((p->vm = allocvm()) == 0) {
212 freeproc(p);
213 release(&p->lock);
214 return 0;
215 }
216 p->slot = 0;
217 } else {
218 // One more thread in vm, in a slot of its own.
219 if ((p->slot = sharevm(vm)) < 0) {
220 freeproc(p);
221 release(&p->lock);
222 return 0;
223 }
224 p->vm = vm;
192225 }
193 p->slot = 0;
194 p->trapframe = (struct trapframe *)p->vm->tfpage;
195 p->pagetable = proc_pagetable(p);
196 if (p->pagetable == 0) {
226 p->trapframe = (struct trapframe *)(p->vm->tfpage + p->slot * TFSIZE);
227 if (vm == 0 && (p->pagetable = proc_pagetable(p)) == 0) {
197228 freeproc(p);
198229 release(&p->lock);
199230 return 0;
200231 }
@@ -276,9 +307,9 @@ void
276307userinit(void)
277308{
278309 struct proc *p;
279310
280 p = allocproc();
311 p = allocproc(0);
281312 initproc = p;
282313
283314 p->cwd = namei("/");
284315
@@ -319,9 +350,9 @@ kfork(void)
319350 struct proc *np;
320351 struct proc *p = myproc();
321352
322353 // Allocate process.
323 if ((np = allocproc()) == 0) {
354 if ((np = allocproc(0)) == 0) {
324355 return -1;
325356 }
326357
327358 // Copy user memory from parent to child.
@@ -360,8 +391,55 @@ kfork(void)
360391
361392 return pid;
362393}
363394
395// Create a new thread in the caller's address space. It starts
396// at fn(arg) on the given user stack, with its own trapframe
397// slot and kernel stack, and copies of the caller's open files
398// and current directory.
399int
400kclone(uint64 fn, uint64 arg, uint64 stack)
401{
402 int i, pid;
403 struct proc *np;
404 struct proc *p = myproc();
405
406 if ((np = allocproc(p->vm)) == 0)
407 return -1;
408
409 // the same page table: nothing is copied.
410 np->pagetable = p->pagetable;
411
412 // start at fn(arg) on the new stack. fn must not return:
413 // ra = 0 makes a return fault.
414 *(np->trapframe) = *(p->trapframe);
415 np->trapframe->epc = fn;
416 np->trapframe->a0 = arg;
417 np->trapframe->sp = stack;
418 np->trapframe->ra = 0;
419
420 for (i = 0; i < NOFILE; i++)
421 if (p->ofile[i])
422 np->ofile[i] = filedup(p->ofile[i]);
423 np->cwd = idup(p->cwd);
424
425 safestrcpy(np->name, p->name, sizeof(p->name));
426
427 pid = np->pid;
428
429 release(&np->lock);
430
431 acquire(&wait_lock);
432 np->parent = p;
433 release(&wait_lock);
434
435 acquire(&np->lock);
436 np->state = RUNNABLE;
437 release(&np->lock);
438
439 return pid;
440}
441
364442// Pass p's abandoned children to init.
365443// Caller must hold wait_lock.
366444void
367445reparent(struct proc *p)
kernel/syscall.c
@@ -102,8 +102,9 @@ extern uint64 sys_unlink(void);
102102extern uint64 sys_link(void);
103103extern uint64 sys_mkdir(void);
104104extern uint64 sys_close(void);
105105extern uint64 sys_sync(void);
106extern uint64 sys_clone(void);
106107
107108// An array mapping syscall numbers from syscall.h
108109// to the function that handles the system call.
109110static uint64 (*syscalls[])(void) = {
@@ -129,8 +130,9 @@ static uint64 (*syscalls[])(void) = {
129130 [SYS_link] = sys_link,
130131 [SYS_mkdir] = sys_mkdir,
131132 [SYS_close] = sys_close,
132133 [SYS_sync] = sys_sync,
134 [SYS_clone] = sys_clone,
133135 // clang-format on
134136};
135137
136138void
kernel/syscall.h
@@ -20,4 +20,5 @@
2020#define SYS_link 19
2121#define SYS_mkdir 20
2222#define SYS_close 21
2323#define SYS_sync 22
24#define SYS_clone 23
kernel/sysproc.c
@@ -27,8 +27,20 @@ sys_fork(void)
2727{
2828 return kfork();
2929}
3030
31// clone(fn, arg, stack): a new thread that shares this
32// address space and starts at fn(arg) with sp = stack.
33uint64
34sys_clone(void)
35{
36 uint64 fn, arg, stack;
37 argaddr(0, &fn);
38 argaddr(1, &arg);
39 argaddr(2, &stack);
40 return kclone(fn, arg, stack);
41}
42
3143uint64
3244sys_wait(void)
3345{
3446 uint64 p;
user/user.h
@@ -24,8 +24,9 @@ int getpid(void);
2424char *sys_sbrk(int, int);
2525int pause(int);
2626int uptime(void);
2727int sync(void);
28int clone(void (*)(void *), void *, void *);
2829
2930// ulib.c
3031int stat(const char *, struct stat *);
3132char *strcpy(char *, const char *);
user/usys.pl
@@ -42,4 +42,5 @@ entry("getpid");
4242entry("sbrk");
4343entry("pause");
4444entry("uptime");
4545entry("sync");
46entry("clone");
016bdaa Add join, and keep wait() away from threads
kernel/defs.h
@@ -97,9 +97,9 @@ void scheduler(void) __attribute__((noreturn));
9797void sched(void);
9898void sleep_prepare(void*);
9999void sleep(void);
100100void userinit(void);
101int kwait(uint64);
101int kwait(uint64, int);
102102void wakeup(void*);
103103void yield(void);
104104int either_copyout(int user_dst, uint64 dst, void *src, uint64 len);
105105int either_copyin(void *dst, int user_src, uint64 src, uint64 len);
kernel/proc.c
@@ -500,10 +500,11 @@ kexit(int status)
500500}
501501
502502// Wait for a child process to exit and return its pid.
503503// Return -1 if this process has no children.
504// With threads set, wait for a child thread instead (join).
504505int
505kwait(uint64 addr)
506kwait(uint64 addr, int threads)
506507{
507508 struct proc *pp;
508509 int havekids, pid;
509510 struct proc *p = myproc();
@@ -517,8 +518,15 @@ kwait(uint64 addr)
517518 if (pp->parent == p) {
518519 // make sure the child isn't still in exit() or swtch().
519520 acquire(&pp->lock);
520521
522 // a child thread shares our address space; a child
523 // process has its own. each kind has its own call.
524 if ((pp->vm == p->vm) != threads) {
525 release(&pp->lock);
526 continue;
527 }
528
521529 havekids = 1;
522530 if (pp->state == ZOMBIE) {
523531 // Found one.
524532 pid = pp->pid;
kernel/syscall.c
@@ -103,8 +103,9 @@ extern uint64 sys_link(void);
103103extern uint64 sys_mkdir(void);
104104extern uint64 sys_close(void);
105105extern uint64 sys_sync(void);
106106extern uint64 sys_clone(void);
107extern uint64 sys_join(void);
107108
108109// An array mapping syscall numbers from syscall.h
109110// to the function that handles the system call.
110111static uint64 (*syscalls[])(void) = {
@@ -131,8 +132,9 @@ static uint64 (*syscalls[])(void) = {
131132 [SYS_mkdir] = sys_mkdir,
132133 [SYS_close] = sys_close,
133134 [SYS_sync] = sys_sync,
134135 [SYS_clone] = sys_clone,
136 [SYS_join] = sys_join,
135137 // clang-format on
136138};
137139
138140void
kernel/syscall.h
@@ -21,4 +21,5 @@
2121#define SYS_mkdir 20
2222#define SYS_close 21
2323#define SYS_sync 22
2424#define SYS_clone 23
25#define SYS_join 24
kernel/sysproc.c
@@ -44,9 +44,18 @@ uint64
4444sys_wait(void)
4545{
4646 uint64 p;
4747 argaddr(0, &p);
48 return kwait(p);
48 return kwait(p, 0);
49}
50
51// join(&status): wait for a thread this thread created.
52uint64
53sys_join(void)
54{
55 uint64 p;
56 argaddr(0, &p);
57 return kwait(p, 1);
4958}
5059
5160uint64
5261sys_sbrk(void)
user/user.h
@@ -25,8 +25,9 @@ char *sys_sbrk(int, int);
2525int pause(int);
2626int uptime(void);
2727int sync(void);
2828int clone(void (*)(void *), void *, void *);
29int join(int *);
2930
3031// ulib.c
3132int stat(const char *, struct stat *);
3233char *strcpy(char *, const char *);
user/usys.pl
@@ -43,4 +43,5 @@ entry("sbrk");
4343entry("pause");
4444entry("uptime");
4545entry("sync");
4646entry("clone");
47entry("join");
4aed831 Lock the shared address space where it changes
kernel/defs.h
@@ -82,9 +82,9 @@ void printkinit(void);
8282int cpuid(void);
8383void kexit(int);
8484int kfork(void);
8585int kclone(uint64, uint64, uint64);
86int growproc(int);
86uint64 growproc(int, int);
8787void proc_mapstacks(pagetable_t);
8888pagetable_t proc_pagetable(struct proc *);
8989void proc_freepagetable(pagetable_t, uint64);
9090int kkill(int);
@@ -158,8 +158,9 @@ void kvminithart(void);
158158void kvmmap(pagetable_t, uint64, uint64, uint64, int);
159159int mappages(pagetable_t, uint64, uint64, uint64, int);
160160pagetable_t uvmcreate(void);
161161uint64 uvmalloc(pagetable_t, uint64, uint64, int);
162uint64 uvmgrow(pagetable_t, uint64, uint64, int);
162163uint64 uvmdealloc(pagetable_t, uint64, uint64);
163164int uvmcopy(pagetable_t, pagetable_t, uint64);
164165void uvmfree(pagetable_t, uint64);
165166void uvmunmap(pagetable_t, uint64, uint64, int);
kernel/exec.c
@@ -34,8 +34,17 @@ kexec(char *path, char **argv)
3434 struct inode *ip;
3535 struct proghdr ph;
3636 pagetable_t pagetable = 0, oldpagetable;
3737 struct proc *p = myproc();
38 int shared;
39
40 // other threads run in this address space, and exec would
41 // free it under them. refuse.
42 acquire(&p->vm->lock);
43 shared = p->vm->ref > 1;
44 release(&p->vm->lock);
45 if (shared)
46 return -1;
3847
3948 begin_op();
4049
4150 // Open the executable file.
kernel/proc.c
@@ -317,29 +317,48 @@ userinit(void)
317317
318318 release(&p->lock);
319319}
320320
321// Grow or shrink user memory by n bytes.
322// Return 0 on success, -1 on failure.
323int
324growproc(int n)
325{
326 uint64 sz;
321// Grow or shrink user memory by n bytes. If n > 0 and not
322// eager, only reserve the addresses: vmfault() allocates each
323// page on first touch. Return the old size, or -1 on failure.
324// Threads of a process may call this at the same time.
325uint64
326growproc(int n, int eager)
327{
328 uint64 sz, newsz;
327329 struct proc *p = myproc();
330 struct vm *vm = p->vm;
328331
329 sz = p->vm->sz;
332 acquire(&vm->lock);
333 sz = newsz = vm->sz;
330334 if (n > 0) {
331 if (sz + n > TRAPFRAME) {
332 return -1;
333 }
334 if ((sz = uvmalloc(p->pagetable, sz, sz + n, PTE_W)) == 0) {
335 return -1;
335 if (sz + n > TRAPFRAME)
336 goto bad;
337 newsz = sz + n;
338 if (eager) {
339 // shared: uvmgrow() never unmaps a page on failure.
340 if (vm->ref > 1)
341 newsz = uvmgrow(p->pagetable, sz, newsz, PTE_W);
342 else
343 newsz = uvmalloc(p->pagetable, sz, newsz, PTE_W);
344 if (newsz == 0)
345 goto bad;
336346 }
337347 } else if (n < 0) {
338 sz = uvmdealloc(p->pagetable, sz, sz + n);
348 // another thread may be using the memory, even in the
349 // middle of a copyout(): don't free it under it.
350 if (vm->ref > 1)
351 goto bad;
352 newsz = uvmdealloc(p->pagetable, sz, sz + n);
339353 }
340 p->vm->sz = sz;
341 return 0;
354 vm->sz = newsz;
355 release(&vm->lock);
356 return sz;
357
358bad:
359 release(&vm->lock);
360 return -1;
342361}
343362
344363// Create a new process, copying the parent.
345364// Sets up child kernel stack to return as if from fork() system call.
@@ -354,15 +373,19 @@ kfork(void)
354373 if ((np = allocproc(0)) == 0) {
355374 return -1;
356375 }
357376
358 // Copy user memory from parent to child.
377 // Copy user memory from parent to child, while no other
378 // thread of the parent changes it.
379 acquire(&p->vm->lock);
359380 if (uvmcopy(p->pagetable, np->pagetable, p->vm->sz) < 0) {
381 release(&p->vm->lock);
360382 freeproc(np);
361383 release(&np->lock);
362384 return -1;
363385 }
364386 np->vm->sz = p->vm->sz;
387 release(&p->vm->lock);
365388
366389 // copy saved user registers.
367390 *(np->trapframe) = *(p->trapframe);
368391
kernel/sysproc.c
@@ -59,31 +59,17 @@ sys_join(void)
5959
6060uint64
6161sys_sbrk(void)
6262{
63 uint64 addr;
6463 int t;
6564 int n;
6665
6766 argint(0, &n);
6867 argint(1, &t);
69 addr = myproc()->vm->sz;
7068
71 if (t == SBRK_EAGER || n < 0) {
72 if (growproc(n) < 0) {
73 return -1;
74 }
75 } else {
76 // Lazily allocate memory for this process: increase its memory
77 // size but don't allocate memory. If the processes uses the
78 // memory, vmfault() will allocate it.
79 if (addr + n < addr)
80 return -1;
81 if (addr + n > TRAPFRAME)
82 return -1;
83 myproc()->vm->sz += n;
84 }
85 return addr;
69 // reading the old size and setting the new one must be one
70 // step, or two threads could both get the same memory.
71 return growproc(n, t == SBRK_EAGER || n < 0);
8672}
8773
8874uint64
8975sys_pause(void)
kernel/vm.c
@@ -240,8 +240,51 @@ uvmalloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz, int xperm)
240240 }
241241 return newsz;
242242}
243243
244// Like uvmalloc(), for a page table that other threads use:
245// on failure it must not unmap anything, since another hart
246// may still hold a removed page in its TLB. So first make the
247// page-table pages, then take every physical page, and map
248// only when all are in hand. Returns newsz, or 0 on failure.
249uint64
250uvmgrow(pagetable_t pagetable, uint64 oldsz, uint64 newsz, int xperm)
251{
252 char *mem, *list = 0;
253 uint64 a;
254
255 if (newsz < oldsz)
256 return oldsz;
257
258 oldsz = PGROUNDUP(oldsz);
259 // page-table pages made here stay if a later step fails;
260 // they map nothing and are freed with the page table.
261 for (a = oldsz; a < newsz; a += PGSIZE)
262 if (walk(pagetable, a, 1) == 0)
263 return 0;
264 // the pages, chained through their first word.
265 for (a = oldsz; a < newsz; a += PGSIZE) {
266 if ((mem = kalloc()) == 0) {
267 while ((mem = list) != 0) {
268 list = *(char **)mem;
269 kfree(mem);
270 }
271 return 0;
272 }
273 *(char **)mem = list;
274 list = mem;
275 }
276 // cannot fail now: every PTE has a page-table page.
277 for (a = oldsz; a < newsz; a += PGSIZE) {
278 mem = list;
279 list = *(char **)mem;
280 memset(mem, 0, PGSIZE);
281 if (mappages(pagetable, a, PGSIZE, (uint64)mem, PTE_R | PTE_U | xperm) != 0)
282 panic("uvmgrow");
283 }
284 return newsz;
285}
286
244287// Deallocate user pages to bring the process size from oldsz to
245288// newsz. oldsz and newsz need not be page-aligned, nor does newsz
246289// need to be less than oldsz. oldsz can be larger than the actual
247290// process size. Returns the new process size.
@@ -452,29 +495,43 @@ copyinstr(pagetable_t pagetable, uint64 psz, char *dst, uint64 srcva,
452495}
453496
454497// allocate and map user memory if process is referencing a page
455498// that was lazily allocated in sys_sbrk().
456// returns 0 if va is invalid or already mapped, or if
499// returns 0 if va is invalid, already mapped without this access, or if
457500// out of physical memory, and physical address if successful.
458501uint64
459502vmfault(pagetable_t pagetable, uint64 psz, uint64 va, int read)
460503{
504 struct vm *vm = myproc()->vm;
461505 uint64 mem;
506 pte_t *pte;
462507
463508 if (va >= psz)
464509 return 0;
465510 va = PGROUNDDOWN(va);
511
512 // other threads may fault on the same page, or change the
513 // page table, at the same time.
514 acquire(&vm->lock);
466515 if (ismapped(pagetable, va)) {
467 return 0;
516 // another thread may have mapped it a moment ago: then the
517 // access is allowed. otherwise (text, guard page) it isn't.
518 pte = walk(pagetable, va, 0);
519 mem = 0;
520 if ((*pte & PTE_U) && (*pte & (read ? PTE_R : PTE_W)))
521 mem = PTE2PA(*pte);
522 release(&vm->lock);
523 return mem;
468524 }
469525 mem = (uint64)kalloc();
470 if (mem == 0)
471 return 0;
472 memset((void *)mem, 0, PGSIZE);
473 if (mappages(pagetable, va, PGSIZE, mem, PTE_W | PTE_U | PTE_R) != 0) {
474 kfree((void *)mem);
475 return 0;
526 if (mem != 0) {
527 memset((void *)mem, 0, PGSIZE);
528 if (mappages(pagetable, va, PGSIZE, mem, PTE_W | PTE_U | PTE_R) != 0) {
529 kfree((void *)mem);
530 mem = 0;
531 }
476532 }
533 release(&vm->lock);
477534 return mem;
478535}
479536
480537int
5104cb5 End the whole process when its first thread exits or is killed
kernel/exec.c
@@ -141,8 +141,9 @@ kexec(char *path, char **argv)
141141 // Commit to the user image.
142142 oldpagetable = p->pagetable;
143143 p->pagetable = pagetable;
144144 p->vm->sz = sz;
145 p->thread = 0; // the first thread of a new program
145146 p->trapframe->epc = elf.entry; // initial program counter = ulib.c:start()
146147 p->trapframe->sp = sp; // initial stack pointer
147148 proc_freepagetable(oldpagetable, oldsz);
148149
kernel/proc.c
@@ -213,16 +213,18 @@ found:
213213 release(&p->lock);
214214 return 0;
215215 }
216216 p->slot = 0;
217 p->thread = 0;
217218 } else {
218219 // One more thread in vm, in a slot of its own.
219220 if ((p->slot = sharevm(vm)) < 0) {
220221 freeproc(p);
221222 release(&p->lock);
222223 return 0;
223224 }
224225 p->vm = vm;
226 p->thread = 1;
225227 }
226228 p->trapframe = (struct trapframe *)(p->vm->tfpage + p->slot * TFSIZE);
227229 if (vm == 0 && (p->pagetable = proc_pagetable(p)) == 0) {
228230 freeproc(p);
@@ -476,19 +478,43 @@ reparent(struct proc *p)
476478 }
477479 }
478480}
479481
480// Exit the current process. Does not return.
481// An exited process remains in the zombie state
482// until its parent calls wait().
482// Kill every other thread in p's address space.
483static void
484killthreads(struct proc *p)
485{
486 struct proc *pp;
487
488 for (pp = proc; pp < &proc[NPROC]; pp++) {
489 if (pp == p)
490 continue;
491 acquire(&pp->lock);
492 if (pp->vm == p->vm) {
493 pp->killed = 1;
494 if (pp->state == SLEEPING)
495 pp->state = RUNNABLE;
496 }
497 release(&pp->lock);
498 }
499}
500
501// Exit the current thread. Does not return.
502// An exited thread remains in the zombie state
503// until its parent calls wait() (or join()).
483504void
484505kexit(int status)
485506{
486507 struct proc *p = myproc();
487508
488509 if (p == initproc)
489510 panic("init exiting");
490511
512 // the process ends when its first thread exits, or when any
513 // thread is killed (by kill() or a fault): end them all.
514 if (!p->thread || killed(p))
515 killthreads(p);
516
491517 // Close all open files.
492518 for (int fd = 0; fd < NOFILE; fd++) {
493519 if (p->ofile[fd]) {
494520 struct file *f = p->ofile[fd];
@@ -762,8 +788,10 @@ wakeup(void *chan)
762788
763789// Kill the process with the given pid.
764790// The victim won't exit until it tries to return
765791// to user space (see usertrap() in trap.c).
792// If pid is one thread of a process, its kexit()
793// kills the other threads.
766794int
767795kkill(int pid)
768796{
769797 struct proc *p;
kernel/proc.h
@@ -107,8 +107,9 @@ struct proc {
107107 uint64 kstack; // Virtual address of kernel stack
108108 struct vm *vm; // Address space, shared by threads
109109 pagetable_t pagetable; // User page table (the vm's)
110110 int slot; // Trapframe slot in vm->tfpage
111 int thread; // Made by clone(): exit ends only it
111112 struct trapframe *trapframe; // data for trampoline.S, in that slot
112113 struct context context; // swtch() here to run process
113114 struct file *ofile[NOFILE]; // Open files
114115 struct inode *cwd; // Current directory
3d41c5c Add futex_wait and futex_wake
Makefile
@@ -12,8 +12,9 @@ OBJS = \
1212 $K/string.o \
1313 $K/main.o \
1414 $K/vm.o \
1515 $K/proc.o \
16 $K/futex.o \
1617 $K/swtch.o \
1718 $K/trampoline.o \
1819 $K/trap.o \
1920 $K/syscall.o \
kernel/defs.h
@@ -77,8 +77,12 @@ int pipewrite(struct pipe*, uint64, int);
7777int printk(char*, ...) __attribute__ ((format (printf, 1, 2)));
7878void panic(char*) __attribute__((noreturn));
7979void printkinit(void);
8080
81// futex.c
82int kfutex_wait(uint64, int);
83int kfutex_wake(uint64, int);
84
8185// proc.c
8286int cpuid(void);
8387void kexit(int);
8488int kfork(void);
kernel/futex.c
@@ -0,0 +1,93 @@
1//
2// futexes: sleep and wake on a word of user memory, the
3// kernel half of a user-level mutex. the word itself is
4// only ever changed by user code, with atomic instructions.
5//
6
7#include "types.h"
8#include "param.h"
9#include "memlayout.h"
10#include "riscv.h"
11#include "spinlock.h"
12#include "proc.h"
13#include "defs.h"
14
15extern struct proc proc[NPROC];
16
17// The sleep channel for the futex word at user address addr:
18// its physical address, which every thread of the process
19// sees the same. 0 if addr is not a good, aligned address.
20static void *
21futexchan(uint64 addr)
22{
23 struct proc *p = myproc();
24 int x;
25
26 // copyin() also faults in a lazily allocated page.
27 if (addr % sizeof(int) != 0 ||
28 copyin(p->pagetable, p->vm->sz, (char *)&x, addr, sizeof(x)) < 0)
29 return 0;
30 return (void *)(walkaddr(p->pagetable, addr) + addr % PGSIZE);
31}
32
33// Sleep until futex_wake(addr), if *addr == val.
34// Return 0 when woken, or at once if *addr != val.
35int
36kfutex_wait(uint64 addr, int val)
37{
38 struct proc *p = myproc();
39 void *chan;
40 int x, r;
41
42 if ((chan = futexchan(addr)) == 0)
43 return -1;
44
45 // register first, then look at the word. a futex_wake()
46 // that comes after the look clears p->chan, and sleep()
47 // then returns at once: the wakeup cannot be lost.
48 sleep_prepare(chan);
49 if (copyin(p->pagetable, p->vm->sz, (char *)&x, addr, sizeof(x)) < 0)
50 r = -1;
51 else if (x != val)
52 r = 0;
53 else if (killed(p))
54 r = -1;
55 else {
56 sleep();
57 return 0;
58 }
59
60 // not sleeping after all: unregister, so that a
61 // futex_wake() does not count this thread as woken.
62 acquire(&p->lock);
63 p->chan = 0;
64 release(&p->lock);
65 return r;
66}
67
68// Wake up to n threads sleeping in futex_wait(addr).
69// Return how many were woken.
70int
71kfutex_wake(uint64 addr, int n)
72{
73 struct proc *p;
74 void *chan;
75 int woken = 0;
76
77 if ((chan = futexchan(addr)) == 0)
78 return -1;
79
80 for (p = proc; p < &proc[NPROC] && woken < n; p++) {
81 acquire(&p->lock);
82 if (p->chan == chan) {
83 // as in wakeup(): a thread still on its way to sleep()
84 // sees p->chan == 0 and does not sleep.
85 p->chan = 0;
86 if (p->state == SLEEPING)
87 p->state = RUNNABLE;
88 woken++;
89 }
90 release(&p->lock);
91 }
92 return woken;
93}
kernel/proc.c
@@ -490,8 +490,9 @@ killthreads(struct proc *p)
490490 continue;
491491 acquire(&pp->lock);
492492 if (pp->vm == p->vm) {
493493 pp->killed = 1;
494 pp->chan = 0; // see kkill()
494495 if (pp->state == SLEEPING)
495496 pp->state = RUNNABLE;
496497 }
497498 release(&pp->lock);
@@ -802,8 +803,11 @@ kkill(int pid)
802803 for (p = proc; p < &proc[NPROC]; p++) {
803804 acquire(&p->lock);
804805 if (p->pid == pid) {
805806 p->killed = 1;
807 // a victim between its killed() check and sleep()
808 // (futex_wait, for one) must not go to sleep after all.
809 p->chan = 0;
806810 if (p->state == SLEEPING) {
807811 // Wake process from sleep().
808812 p->state = RUNNABLE;
809813 }
kernel/syscall.c
@@ -104,8 +104,10 @@ extern uint64 sys_mkdir(void);
104104extern uint64 sys_close(void);
105105extern uint64 sys_sync(void);
106106extern uint64 sys_clone(void);
107107extern uint64 sys_join(void);
108extern uint64 sys_futex_wait(void);
109extern uint64 sys_futex_wake(void);
108110
109111// An array mapping syscall numbers from syscall.h
110112// to the function that handles the system call.
111113static uint64 (*syscalls[])(void) = {
@@ -133,8 +135,10 @@ static uint64 (*syscalls[])(void) = {
133135 [SYS_close] = sys_close,
134136 [SYS_sync] = sys_sync,
135137 [SYS_clone] = sys_clone,
136138 [SYS_join] = sys_join,
139 [SYS_futex_wait] = sys_futex_wait,
140 [SYS_futex_wake] = sys_futex_wake,
137141 // clang-format on
138142};
139143
140144void
kernel/syscall.h
@@ -22,4 +22,6 @@
2222#define SYS_close 21
2323#define SYS_sync 22
2424#define SYS_clone 23
2525#define SYS_join 24
26#define SYS_futex_wait 25
27#define SYS_futex_wake 26
kernel/sysproc.c
@@ -56,8 +56,30 @@ sys_join(void)
5656 argaddr(0, &p);
5757 return kwait(p, 1);
5858}
5959
60// futex_wait(addr, val): sleep if *addr == val.
61uint64
62sys_futex_wait(void)
63{
64 uint64 addr;
65 int val;
66 argaddr(0, &addr);
67 argint(1, &val);
68 return kfutex_wait(addr, val);
69}
70
71// futex_wake(addr, n): wake up to n futex_wait(addr)ers.
72uint64
73sys_futex_wake(void)
74{
75 uint64 addr;
76 int n;
77 argaddr(0, &addr);
78 argint(1, &n);
79 return kfutex_wake(addr, n);
80}
81
6082uint64
6183sys_sbrk(void)
6284{
6385 int t;
user/user.h
@@ -26,8 +26,10 @@ int pause(int);
2626int uptime(void);
2727int sync(void);
2828int clone(void (*)(void *), void *, void *);
2929int join(int *);
30int futex_wait(int *, int);
31int futex_wake(int *, int);
3032
3133// ulib.c
3234int stat(const char *, struct stat *);
3335char *strcpy(char *, const char *);
user/usys.pl
@@ -44,4 +44,6 @@ entry("pause");
4444entry("uptime");
4545entry("sync");
4646entry("clone");
4747entry("join");
48entry("futex_wait");
49entry("futex_wake");
e12eb7d Add a user thread library with a futex mutex
Makefile
@@ -101,9 +101,9 @@ $K/%.o: $K/%.S
101101
102102tags: $(OBJS)
103103 etags kernel/*.S kernel/*.c
104104
105ULIB = $U/ulib.o $U/usys.o $U/printf.o $U/umalloc.o
105ULIB = $U/ulib.o $U/usys.o $U/printf.o $U/umalloc.o $U/uthread.o
106106
107107_%: %.o $(ULIB) $U/user.ld
108108 $(LD) $(LDFLAGS) -T $U/user.ld -o $@ $< $(ULIB)
109109 $(OBJDUMP) -S $@ > $*.asm
user/user.h
@@ -51,4 +51,13 @@ void printf(const char *, ...) __attribute__((format(printf, 1, 2)));
5151
5252// umalloc.c
5353void *malloc(uint);
5454void free(void *);
55
56// uthread.c
57struct mutex {
58 int v; // 0: free, 1: held, 2: held, maybe with sleepers
59};
60int thread_create(int (*)(void *), void *);
61int thread_join(int *);
62void mutex_lock(struct mutex *);
63void mutex_unlock(struct mutex *);
user/uthread.c
@@ -0,0 +1,108 @@
1// User threads on clone() and join(), and a mutex on
2// futex_wait() and futex_wake().
3
4#include "kernel/types.h"
5#include "user/user.h"
6
7#define TSTACK 8192 // bytes of stack for each thread
8#define MAXT 8 // the kernel's NTHREAD
9
10// what a new thread finds at the top of its stack.
11struct tstart {
12 int (*fn)(void *);
13 void *arg;
14};
15
16// thread stacks, reused after join. no guard pages.
17static struct {
18 int tid; // the thread using it, or 0 if free
19 char *stack;
20} stacks[MAXT];
21static struct mutex stacklock;
22
23// every thread starts here, on its new stack: call the
24// thread's function and exit with what it returns.
25static void
26start(void *a)
27{
28 struct tstart *s = a;
29 exit(s->fn(s->arg));
30}
31
32// Start fn(arg) in a new thread. Return its id, or -1.
33int
34thread_create(int (*fn)(void *), void *arg)
35{
36 struct tstart *s;
37 int i, tid = -1;
38
39 mutex_lock(&stacklock);
40 for (i = 0; i < MAXT; i++)
41 if (stacks[i].tid == 0)
42 break;
43 if (i < MAXT && stacks[i].stack == 0) {
44 stacks[i].stack = sbrk(TSTACK); // sbrk is thread-safe
45 if (stacks[i].stack == SBRK_ERROR)
46 stacks[i].stack = 0;
47 }
48 if (i < MAXT && stacks[i].stack != 0) {
49 // the top 16 bytes hold fn and arg; sp starts below them.
50 s = (struct tstart *)(stacks[i].stack + TSTACK) - 1;
51 s->fn = fn;
52 s->arg = arg;
53 tid = clone(start, s, s);
54 if (tid > 0)
55 stacks[i].tid = tid;
56 }
57 mutex_unlock(&stacklock);
58 return tid;
59}
60
61// Wait for a thread this thread created to exit. Return its
62// id, and its exit status in *status, or -1 if there is none.
63int
64thread_join(int *status)
65{
66 int i, tid;
67
68 tid = join(status);
69 if (tid > 0) {
70 mutex_lock(&stacklock);
71 for (i = 0; i < MAXT; i++)
72 if (stacks[i].tid == tid)
73 stacks[i].tid = 0;
74 mutex_unlock(&stacklock);
75 }
76 return tid;
77}
78
79// m->v is 0 when the mutex is free, 1 when it is held,
80// and 2 when it is held and threads may be asleep on it.
81void
82mutex_lock(struct mutex *m)
83{
84 int c = 0;
85
86 // free: take it with one atomic instruction, no system call.
87 if (__atomic_compare_exchange_n(&m->v, &c, 1, 0, __ATOMIC_ACQUIRE,
88 __ATOMIC_RELAXED))
89 return;
90
91 // held: mark it 2 ("someone waits") and sleep until it is
92 // free. the exchange both takes the mutex, if it got free,
93 // and makes sure the holder's unlock will wake us.
94 if (c != 2)
95 c = __atomic_exchange_n(&m->v, 2, __ATOMIC_ACQUIRE);
96 while (c != 0) {
97 futex_wait(&m->v, 2);
98 c = __atomic_exchange_n(&m->v, 2, __ATOMIC_ACQUIRE);
99 }
100}
101
102void
103mutex_unlock(struct mutex *m)
104{
105 // nobody waits (1): done. maybe somebody (2): wake one.
106 if (__atomic_exchange_n(&m->v, 0, __ATOMIC_RELEASE) == 2)
107 futex_wake(&m->v, 1);
108}
0194dc5 Add threadtest
Makefile
@@ -150,8 +150,9 @@ UPROGS=\
150150 $U/_logstress\
151151 $U/_forphan\
152152 $U/_dorphan\
153153 $U/_sync\
154 $U/_threadtest\
154155
155156fs.img: mkfs/mkfs README $(UPROGS)
156157 mkfs/mkfs fs.img README $(UPROGS)
157158
user/threadtest.c
@@ -0,0 +1,514 @@
1//
2// tests for clone, join, futexes and the thread library.
3// each test prints "threadtest: <name>: OK" or "... FAIL".
4// only the first thread prints; other threads report through
5// their exit status or shared memory.
6//
7
8#include "kernel/types.h"
9#include "kernel/riscv.h"
10#include "user/user.h"
11
12#define NT 7 // threads besides the first: the kernel allows 8 in all
13
14int failed;
15
16void
17result(char *name, int ok)
18{
19 printf("threadtest: %s: %s\n", name, ok ? "OK" : "FAIL");
20 if (!ok)
21 failed = 1;
22}
23
24// count free pages by allocating them all with sbrk.
25// only in a single-threaded process: sbrk(-n) needs that.
26int
27countfree(void)
28{
29 char *sz0 = sbrk(0);
30 int n = 0;
31
32 while (sbrk(PGSIZE) != SBRK_ERROR)
33 n++;
34 sbrk(-(sbrk(0) - sz0));
35 return n;
36}
37
38// a starting gate: threads sleep until gateopen() lets them
39// all go at once, so that they run at the same time.
40int gate;
41
42void
43gatewait(void)
44{
45 while (__atomic_load_n(&gate, __ATOMIC_ACQUIRE) == 0)
46 futex_wait(&gate, 0);
47}
48
49void
50gateopen(void)
51{
52 __atomic_store_n(&gate, 1, __ATOMIC_RELEASE);
53 futex_wake(&gate, NT);
54}
55
56// start n threads running fn(i), i = 0..n-1; tids[i] gets
57// each id. return 1 if all started.
58int
59startall(int (*fn)(void *), int n, int *tids)
60{
61 int ok = 1;
62
63 gate = 0;
64 for (int i = 0; i < n; i++) {
65 tids[i] = thread_create(fn, (void *)(uint64)i);
66 if (tids[i] < 0)
67 ok = 0;
68 }
69 gateopen();
70 return ok;
71}
72
73// join every thread; return 1 if all exited with status 0.
74int
75joinall(void)
76{
77 int st, ok = 1;
78
79 while (thread_join(&st) > 0)
80 if (st != 0)
81 ok = 0;
82 return ok;
83}
84
85// create and join: exit statuses come back to the creator.
86int
87exitfn(void *arg)
88{
89 gatewait();
90 return 100 + (int)(uint64)arg;
91}
92
93void
94jointest(void)
95{
96 int tids[NT], seen[NT] = {0}, st, tid, ok;
97
98 ok = startall(exitfn, NT, tids);
99 // all 8 trapframe slots are taken now (or soon by zombies).
100 if (thread_create(exitfn, 0) >= 0)
101 ok = 0;
102 for (int n = 0; n < NT; n++) {
103 if ((tid = thread_join(&st)) < 0) {
104 ok = 0;
105 break;
106 }
107 for (int i = 0; i < NT; i++)
108 if (tid == tids[i] && st == 100 + i)
109 seen[i]++;
110 }
111 for (int i = 0; i < NT; i++)
112 if (seen[i] != 1)
113 ok = 0;
114 if (thread_join(&st) != -1) // no threads left
115 ok = 0;
116 result("create and join", ok);
117}
118
119// every thread traps into the kernel thousands of times; its
120// registers and system-call results must stay its own.
121int
122regsfn(void *arg)
123{
124 int me = getpid();
125 volatile uint64 a = (uint64)arg, b = 3 * a, c = 7 * a;
126
127 gatewait();
128 for (int i = 0; i < 2000; i++) {
129 if (getpid() != me)
130 return 1;
131 a += 1;
132 b += 3;
133 c += 7;
134 }
135 if (a != (uint64)arg + 2000 || b != 3 * (uint64)arg + 6000 ||
136 c != 7 * (uint64)arg + 14000)
137 return 2;
138 return 0;
139}
140
141void
142regstest(void)
143{
144 int tids[NT];
145 int ok = startall(regsfn, NT, tids);
146 result("registers", joinall() && ok);
147}
148
149// a shared counter, incremented slowly (read, wait, write) by
150// all threads: under the futex mutex, and without it.
151#define NINC 20000
152struct mutex m;
153volatile int counter;
154
155void
156slowinc(void)
157{
158 int c = counter;
159 for (volatile int j = 0; j < 200; j++)
160 ;
161 counter = c + 1;
162}
163
164int
165countfn(void *arg)
166{
167 gatewait();
168 for (int i = 0; i < NINC; i++) {
169 mutex_lock(&m);
170 slowinc();
171 mutex_unlock(&m);
172 }
173 return 0;
174}
175
176int
177racefn(void *arg)
178{
179 gatewait();
180 for (int i = 0; i < NINC; i++)
181 slowinc();
182 return 0;
183}
184
185void
186mutextest(void)
187{
188 int tids[NT], ok;
189
190 counter = 0;
191 ok = startall(countfn, NT, tids);
192 ok = joinall() && ok;
193 printf("threadtest: mutex: %d of %d\n", counter, NT * NINC);
194 result("mutex", ok && counter == NT * NINC);
195
196 // the same without the mutex: updates get lost whenever
197 // threads really run at once. printed, not checked.
198 counter = 0;
199 startall(racefn, NT, tids);
200 joinall();
201 printf("threadtest: without the mutex: %d of %d (not checked)\n", counter,
202 NT * NINC);
203}
204
205// two threads hand a turn back and forth through a futex,
206// each sleeping until the other wakes it: a single lost
207// wakeup leaves both asleep for ever.
208#define NPING 5000
209int turn;
210
211int
212pingfn(void *arg)
213{
214 int me = (int)(uint64)arg;
215
216 for (int i = 0; i < NPING; i++) {
217 while (__atomic_load_n(&turn, __ATOMIC_ACQUIRE) != me)
218 futex_wait(&turn, 1 - me);
219 __atomic_store_n(&turn, 1 - me, __ATOMIC_RELEASE);
220 futex_wake(&turn, 1);
221 }
222 return 0;
223}
224
225void
226pingtest(void)
227{
228 int ok = 1;
229
230 turn = 0;
231 if (thread_create(pingfn, (void *)0) < 0 ||
232 thread_create(pingfn, (void *)1) < 0)
233 ok = 0;
234 result("ping-pong", joinall() && ok);
235}
236
237// sbrk from many threads at once: every call must get its
238// own memory.
239#define NSBRK 50
240char *got[NT][NSBRK];
241
242int
243sbrkfn(void *arg)
244{
245 int me = (int)(uint64)arg;
246
247 gatewait();
248 for (int k = 0; k < NSBRK; k++) {
249 char *p = sbrk(PGSIZE);
250 if (p == SBRK_ERROR)
251 return 1;
252 memset(p, 'a' + me, PGSIZE);
253 got[me][k] = p;
254 }
255 return 0;
256}
257
258void
259sbrktest(void)
260{
261 int tids[NT], ok;
262 char *before = sbrk(0);
263
264 ok = startall(sbrkfn, NT, tids);
265 ok = joinall() && ok;
266 if (sbrk(0) != before + NT * NSBRK * PGSIZE)
267 ok = 0;
268 for (int i = 0; ok && i < NT; i++)
269 for (int k = 0; k < NSBRK; k++)
270 for (int j = 0; j < PGSIZE; j++)
271 if (got[i][k][j] != 'a' + i) {
272 ok = 0;
273 break;
274 }
275 result("sbrk", ok);
276}
277
278// all threads touch the same lazily allocated pages at once:
279// each page faults on several harts at the same moment.
280#define NLAZY 512
281char *lazy;
282
283int
284lazyfn(void *arg)
285{
286 int me = (int)(uint64)arg;
287
288 gatewait();
289 for (int j = 0; j < NLAZY; j++)
290 lazy[j * PGSIZE + me] = 'a' + me;
291 return 0;
292}
293
294void
295lazytest(void)
296{
297 int tids[NT], ok;
298
299 lazy = sbrklazy(NLAZY * PGSIZE);
300 ok = startall(lazyfn, NT, tids);
301 ok = joinall() && ok;
302 for (int j = 0; j < NLAZY; j++)
303 for (int i = 0; i < NT; i++)
304 if (lazy[j * PGSIZE + i] != 'a' + i)
305 ok = 0;
306 result("lazy", ok);
307}
308
309// while another thread exists, the address space may not
310// shrink or be replaced, and an eager sbrk that runs out of
311// memory must give up without mapping anything.
312int waitword;
313
314int
315sleepfn(void *arg)
316{
317 while (__atomic_load_n(&waitword, __ATOMIC_ACQUIRE) == 0)
318 futex_wait(&waitword, 0);
319 return 0;
320}
321
322void
323sharedtest(void)
324{
325 char *argv[] = {"echo", "exec", "succeeded", 0};
326 int ok = 1;
327
328 waitword = 0;
329 if (thread_create(sleepfn, 0) < 0)
330 ok = 0;
331 char *brk = sbrk(0);
332 if (sbrk(1 << 27) != SBRK_ERROR || sbrk(0) != brk) // 128 MiB: too much
333 ok = 0;
334 if (sbrk(-PGSIZE) != SBRK_ERROR)
335 ok = 0;
336 if (exec("echo", argv) != -1)
337 ok = 0;
338 __atomic_store_n(&waitword, 1, __ATOMIC_RELEASE);
339 futex_wake(&waitword, 1);
340 ok = joinall() && ok;
341 // alone again: shrinking works.
342 if (sbrk(PGSIZE) == SBRK_ERROR || sbrk(-PGSIZE) == SBRK_ERROR)
343 ok = 0;
344 result("shared memory only grows", ok);
345}
346
347// join() reaps threads, wait() reaps child processes.
348int
349slowfn(void *arg)
350{
351 pause(3);
352 return 7;
353}
354
355void
356waitjointest(void)
357{
358 int pid, tid, st, ok = 1;
359
360 pid = fork();
361 if (pid == 0)
362 exit(42);
363 tid = thread_create(slowfn, 0);
364 if (pid < 0 || tid < 0)
365 ok = 0;
366 if (thread_join(&st) != tid || st != 7)
367 ok = 0;
368 if (wait(&st) != pid || st != 42)
369 ok = 0;
370 if (thread_join(&st) != -1 || wait(&st) != -1)
371 ok = 0;
372 result("wait and join", ok);
373}
374
375// the first thread's exit, or a kill, ends every thread.
376int
377spinfn(void *arg)
378{
379 for (;;)
380 ;
381}
382
383int
384blockfn(void *arg)
385{
386 int never = 0;
387 for (;;)
388 futex_wait(&never, 0);
389}
390
391int
392freeagain(int free0)
393{
394 // the killed threads are reaped by init, a moment later.
395 for (int i = 0; i < 50; i++) {
396 if (countfree() == free0)
397 return 1;
398 pause(1);
399 }
400 return 0;
401}
402
403void
404exittest(void)
405{
406 int free0 = countfree(), pid, st, ok = 1;
407
408 pid = fork();
409 if (pid == 0) {
410 thread_create(spinfn, 0);
411 thread_create(spinfn, 0);
412 thread_create(blockfn, 0);
413 pause(2);
414 exit(5);
415 }
416 if (wait(&st) != pid || st != 5)
417 ok = 0;
418 result("exit ends all threads", ok && freeagain(free0));
419
420 ok = 1;
421 pid = fork();
422 if (pid == 0) {
423 thread_create(spinfn, 0);
424 thread_create(blockfn, 0);
425 thread_create(blockfn, 0);
426 joinall(); // never returns
427 exit(0);
428 }
429 pause(2);
430 kill(pid);
431 if (wait(&st) != pid || st != -1)
432 ok = 0;
433 result("kill ends all threads", ok && freeagain(free0));
434}
435
436// many rounds of everything at once, on all harts: mutex,
437// sbrk, lazy faults, and fork + wait from inside threads.
438#define ROUNDS 20
439
440int
441stressfn(void *arg)
442{
443 int me = (int)(uint64)arg, pid, st;
444
445 gatewait();
446 for (int i = 0; i < 300; i++) {
447 mutex_lock(&m);
448 counter++;
449 mutex_unlock(&m);
450 }
451 char *p = sbrklazy(2 * PGSIZE);
452 if (p == SBRK_ERROR)
453 return 1;
454 p[0] = p[PGSIZE] = me;
455 pid = fork();
456 if (pid == 0)
457 exit(me);
458 if (pid < 0 || wait(&st) != pid || st != me)
459 return 2;
460 return 0;
461}
462
463void
464stresstest(void)
465{
466 int tids[NT], ok = 1;
467
468 counter = 0;
469 for (int r = 0; r < ROUNDS; r++) {
470 if (!startall(stressfn, NT, tids))
471 ok = 0;
472 if (!joinall())
473 ok = 0;
474 }
475 result("stress", ok && counter == ROUNDS * NT * 300);
476}
477
478int
479main(int argc, char *argv[])
480{
481 int free0, free1, pid, st;
482
483 free0 = countfree();
484
485 // run the in-process tests in a child, so that the memory
486 // they leave allocated is freed before the second count.
487 pid = fork();
488 if (pid == 0) {
489 jointest();
490 regstest();
491 mutextest();
492 pingtest();
493 sbrktest();
494 lazytest();
495 sharedtest();
496 waitjointest();
497 stresstest();
498 exit(failed);
499 }
500 if (wait(&st) != pid || st != 0)
501 failed = 1;
502 if (st == -1)
503 printf("threadtest: the process running the tests was killed\n");
504
505 exittest();
506
507 if (!freeagain(free0))
508 failed = 1;
509 free1 = countfree();
510 printf("threadtest: free pages %d before, %d after\n", free0, free1);
511 result("no leaks", free1 == free0);
512 printf("threadtest: %s\n", failed ? "SOME TESTS FAILED" : "ALL OK");
513 exit(failed);
514}

6. Verify and measure

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.

What a thread costs. A scratch copy of the reference kernel counted kalloc calls inside kfork and inside kclone, and timed loops with uptime (one tick is about a tenth of a second). The program had a 1 MiB heap, written:

	`fork`	`clone`
pages allocated by the call	266 (260 for the image, 1 trapframe page, 5 page-table pages)	0
2000 × create + reap	69 ticks (`fork` + `wait`; the same in a second run)	3 ticks (`thread_create` + `thread_join`, both runs)

(Tick counts on QEMU depend on what else the computer is doing; yours will differ, but the gap between the two columns will not close.)

A thread needs a struct proc (which has its kernel stack since boot) and a slot in a page that already exists; its user stack (8 KiB from sbrk) is the library’s and is reused.

How often the kernel is involved. The same scratch copy counted futex calls (instrumentation not on the branch):

workload	`futex_wait` calls	went to sleep	`futex_wake` calls	threads woken
1 thread, 140,000 lock/unlock pairs	0	0	0	0
7 threads × 20,000 pairs (run 1)	2,289	0	3,812	215
7 threads × 20,000 pairs (run 2)	2,375	1	4,072	36
ping-pong, 2 threads × 5000 turns (run 1)	5,204	4,835	10,000	4,837
ping-pong (run 2)	2,856	2,756	10,000	2,757

The mutex stays in user space unless there is contention, and even under contention the holder’s critical section (a 200-iteration loop) is usually over before a waiter gets into the kernel, so few waiters actually sleep. “Woken” exceeds “went to sleep” because futex_wake counts threads that were registered but still on their way to sleep: exactly the window the register-then-look order protects. In ping-pong, where a thread can only wait for the other, most futex_wait calls do go to sleep; the rest find the turn already handed over.

7. Go further

Share the descriptor table. clone copies the open-file table as fork does, so a file one thread opens is invisible to the others. Move ofile[] and cwd into a refcounted structure like struct vm; you will meet the same “last one out” and locking questions for open and close.
exec kills the other threads. Instead of refusing, make exec from any thread kill its siblings, wait until they are gone (ref back to 1), and then replace the image. This is what Linux does; it needs a way to wait for threads that are not your children.
Guard pages for thread stacks. Allocate each stack with one extra page and clear its PTE_U (a new system call, or an mprotect-like one), so that an overflow faults instead of corrupting a neighbour.
Wake an idle hart. A RUNNABLE thread waits up to a timer tick for an idle hart in wfi. Send it a supervisor software interrupt from wakeup and measure how ping-pong and the mutex test change. The CLINT’s msip will not do on its own: it raises a machine-level interrupt, which this tree neither delegates nor handles (start never sets mtvec or mie.MSIE). Either run QEMU with -machine virt,aclint=on and use the ACLINT’s SSWI device, which sets sip.SSIP on the target hart, or add a small M-mode handler that turns MSIP into SSIP.
Copy-on-write meets threads. After lab 11, a page with reference count 1 may be “taken over” without copying. With threads, two threads of one process can fault on the same COW page at once. Work out which lock cowfault needs now.