Extension labs · lab 11 · Memory · ★★★★☆

Copy-on-write fork

In this tree kfork copies every page of the parent with uvmcopy: one kalloc and one 4096-byte memmove per page. Most of that work is wasted. The shell forks a child that calls exec a few microseconds later and throws the copy away. In this lab you make fork share the parent’s pages instead: both page tables point at the same physical pages, mapped read-only, and the first store by either process takes a page fault that copies just that one page.

The idea fits in one sentence; the details are where an operating system shows its insides. A page can now belong to several page tables: when may it be freed, and what happens on three harts when its owners let go at the same moment? Does anything in this tree already handle store faults, and what would it make of yours? The kernel also writes into user memory on a process’s behalf: does that write fault too? And some pages are read-only for good, like program text: how will your fault handler know them from shared ones? The think section asks these questions in the order a designer meets them.

The reference solution is six small commits. With it, a fork of the shell allocates 6 pages instead of 11, and a process using 60% of RAM can fork, which the original kernel refuses.

Read first: Tour 10: Exceptions and faults, Tour 20: fork, Tour 25: A user address space, Tour 26: sbrk, eager and lazy, and page faults, Tour 27: The physical page allocator, Tour 28: Crossing the user/kernel boundary in memory · The stacks of xv6, Locks and interrupt state

What this lab teaches

How the hardware enforces a read-only page: a store from user mode through a PTE without PTE_W raises a store page fault (scause 15) with the address in stval, and how the kernel can turn that fault into a private copy and retry the instruction.
How a new kind of page fault has to coexist with the fault handling this tree already has, and how to make sure two handlers never fight over one fault.
How the kernel’s own writes into user memory interact with a read-only user PTE, and what that means for code that runs with spinlocks held.
How to keep a reference count per physical page correctly on three harts: which lock protects it, what exactly must happen inside the critical section, and what a lost update does on a real run.
Which PTE bits the hardware ignores, and why a kernel may need one of them.
Why exec and exit need no change at all, why the parent’s TLB needs no flush, and why a page with one remaining sharer can be made writable instead of copied.

The reference branch

ext/11-cow in ShowMeTheStack/xv6-riscv-labs, branched from the frozen commit 06aad25; 6 commits.

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

1. The spec

Behaviour. After fork, parent and child share every user page that the parent had mapped. No user page is copied by fork. A page that was writable in the parent becomes read-only in both page tables and is marked copy-on-write. The first store to it, by either process, copies that one page into a fresh page owned by the storing process, and the store is retried. Afterwards each process sees only its own writes, exactly as with a copying fork.

The same must hold when the kernel writes into a shared page on a process’s behalf: read into a buffer, wait(&status), pipe(fds), fstat into a page shared since fork must all work.

What must not change.

Pages that were read-only before fork (program text, mapped R|X|U by kexec) stay read-only forever. A store to text must still kill the process, as usertests nowrite checks, and read into text must still fail, as usertests copyout checks.
The stack guard page (mapped without PTE_U, kernel/exec.c:95) stays inaccessible.
Lazy allocation keeps working: a page reserved by sbrklazy and never touched is not mapped when fork runs, and a first touch in either process still allocates a fresh zeroed page through vmfault.
If no memory is left for a copy, the faulting process is killed; the kernel must not panic. (A system call that needs a copy and finds no memory fails instead; one consequence is worked out in the think section.)
No page leaks: usertests compares the number of free pages before and after.
usertests -q must print ALL TESTS PASSED on 3 harts.

The test program, cowtest, prints one line per check:

$ cowtest
cowtest: big: OK
cowtest: lazy: OK
cowtest: copyout: OK
cowtest: independence: OK
usertrap(): unexpected scause 0xf pid=8
            sepc=0x55c stval=0x508
cowtest: text: OK
cowtest: forks: OK
cowtest: free pages 32436 before, 32436 after
cowtest: no leaks: OK
cowtest: ALL OK

big: allocate 60% of RAM with sbrk (more than half of the free memory), write every page, fork; the child checks and rewrites 101 pages, the parent rewrites 51 (both include the first page). Without copy-on-write, fork fails for lack of memory.
lazy: sbrklazy 8 pages, touch only the first, fork; the child writes the shared page (a copy-on-write fault), writes and reads untouched pages (lazy faults), and the parent’s values must be unchanged.
copyout: the child reads from a pipe into 6 bytes straddling two pages it has not touched since fork: only the kernel writes them.
independence: parent and child each write a global after fork, in a fixed order enforced by pipes; neither may see the other’s value.
text: a child stores to its own code; it must be killed (the usertrap() message above is that kill, expected).
forks: 5 rounds of 20 children, each forking a grandchild, all running on 3 harts.
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.

1Where is a write to a shared page caught?

Parent and child must be able to share a page until one of them writes it. Something has to notice that write before it lands in the shared page. What notices it, and what does the kernel learn when it does? Commit to an answer before the hints: is it a check in software, or something the hardware does on every store?

Check yourself

1warm-upChoose one

A child shares its parent’s stack page, mapped without PTE_W. The child executes sd ra, 8(sp) (a store) to that page. What value does usertrap read from scause?

8, an environment call from U-mode13, a load page fault15, a store/AMO page fault12, an instruction page fault

2solidTrue or false, and why

True or false: after a copy-on-write fault is handled, usertrap must add 4 to p->trapframe->epc so that the process does not execute the faulting store twice.

TrueFalse

Why?

The hardware advances sepc by itself on a page fault.The store never completed; returning to the same instruction makes it run once, on the new page.Stores are idempotent, so running one twice is harmless.

2How does the kernel tell a shared page from a page that is read-only for good?

After the change, a store fault on a mapped, valid, user page without PTE_W happens in two different situations: the page is shared copy-on-write, or the page really is read-only (program text). The first must be copied; the second must kill the process. The PTE in both cases has V, R and U set and W clear. How does the fault handler tell them apart? And which other mapped, valid page will uvmcopy see that is neither?

Check yourself

1solidDecode the bits

On the reference branch, gdb stopped in the copy-on-write handler and printed the faulting process’s PTE: 0x21fcf1d3. Decode the flag bits (bits 0 to 9). What kind of page is it?

Value: 0x21fcf1d3

V (bit 0)W (bit 2)U (bit 4)D (bit 7)RSW bit 8What happens on a user store?

2solidChoose one

With copy-on-write in place, a child overflows its one-page user stack and stores to the guard page just below it. The guard PTE has V and W set and U clear; at fork, uvmcopy turned W into PTE_COW as for any writable page. What must happen?

The handler copies the guard page and the store succeeds.The process is killed, because the handler requires PTE_U as well as PTE_COW.The kernel panics in walk.vmfault allocates a fresh zeroed page there, as for a lazy page.

3A store fault already means something in this tree

This tree has lazy allocation: sbrklazy(n) only raises p->sz (kernel/sysproc.c:62), and the first touch of each page faults into vmfault, called from usertrap for scause 13 and 15 (kernel/trap.c:71). Suppose you add copy-on-write fork but do not touch usertrap. A child writes its stack after fork. What happens, step by step? Then: how should the two handlers be combined, and in which order? Could one fault ever need both?

The reference design

Without a change to usertrap, the child’s store faults with scause 15, the existing branch calls vmfault, and vmfault returns 0 because ismapped says the page is mapped (kernel/vm.c:466). usertrap prints unexpected scause 0xf and kills the child. And not only the child: fork marked the parent’s PTEs COW as well, so the parent dies at its own first store to a formerly writable page, and so does init, whose pages became COW when it forked the shell at boot. We built exactly that (commit 2 plus the new uvmcopy) and typed echo hi: pid 3, then pid 2, then pid 1 were killed, and the kernel stopped with panic: init exiting. That is the interaction to discover: in this tree “store page fault” does not mean “lazy page”, it means “lazy page or COW page”, and the existing code only knows the first.

The two cases are disjoint because they are about different PTE states:

the PTE for the faulting page	lazy (`vmfault`)	COW handler
no PTE, or `V` clear, address below `p->sz`	allocates	declines
`V`, `U`, `PTE_COW` set	declines (mapped)	copies
`V` set, no `PTE_COW` (text, guard)	declines	declines: kill
address at or above `p->sz` and unmapped	declines	declines: kill

The reference adds one branch before the lazy one: scause == 15 && cowfault(...). Load faults (13) never need COW, since reading a shared page is allowed. A fault never needs both handlers: a lazy page that is not mapped at fork is simply not shared, and after the fault that allocates it, it is a private writable page. fork does not copy lazy pages at all; each process gets its own zeroed page if it touches one later.

The same two-way split appears again in copyout, which already calls vmfault for unmapped pages and now also has to handle COW pages (next question).

4Who counts the sharers, and under which lock?

A physical page may now be mapped by several page tables. kfree is called by uvmunmap whenever any one of them lets go (exit, exec, sbrk(-n)). When may the page really go back on the free list, and where do you keep the information? Then, on 3 harts: the parent and the child exit at the same moment on two harts, and both call kfree on the same text page. What must be true of your code so that the page is freed exactly once?

The reference design

Keep one counter per physical page: int count[(PHYSTOP - KERNBASE) / PGSIZE], 32,768 entries, 128 KiB of kernel .bss (32 pages, which shows up as 32 fewer free pages: cowtest counts 32,468 free pages on the original kernel and 32,436 with this branch). The index is (pa - KERNBASE) / PGSIZE. kalloc sets it to 1, fork adds one for every page it shares, and kfree becomes “drop one reference”: it frees the page only when its count reaches 0. freerange sets each page’s count to 1 before its first kfree so that the boot-time frees bring it to 0.

The race. --count[i] is a load, a subtract and a store (lw, addiw, sw in this build). Without a lock:

time	hart 0 (parent exits)	hart 1 (child exits)
1	loads 2
2		loads 2
3	stores 1, “still shared”
4		stores 1, “still shared”

Nobody frees the page: a leak. The mirror image (a lost increment during a fork racing with an exit) is worse: the count reaches 0 while a page table still maps the page, the page is freed and handed to someone else. Clinic 1 shows both happening on a real run.

With a spinlock around the read-modify-write and the test, the two decrements serialize: one hart sees 1, the other sees 0 and frees. The lock must cover the decrement and the decision; reading the count again after releasing it would reopen the race.

Which lock? kmem.lock would work, but the reference uses a separate kref.lock. The counts and the free list share no invariant that needs one critical section: once a count reaches 0 nobody else holds the page, so pushing it on the free list a moment later, under kmem.lock, is safe; and in kalloc the page just popped is known to nobody until its count is set. Separate locks keep fork, which now does one count update per page and no page copies (it still allocates page-table pages), off the free list’s lock. The two locks are never held together (each function releases one before taking the other), so they add no lock-order edge between them.

Check yourself

1warm-upType a number

The counts array has one int for every 4096-byte page between KERNBASE and PHYSTOP. How many entries does it have?

kernel/memlayout.h

40// the kernel expects there to be RAM
41// for use by the kernel and user pages
42// from physical address 0x80000000 to PHYSTOP.
43#define KERNBASE 0x80000000L
44#define PHYSTOP  (KERNBASE + 128 * 1024 * 1024)

decimal, 0x hex or 0b binary

2deepChoose one

Suppose kfree does this, with a lock only around the decrement:

acquire(&kref.lock);
kref.count[i]--;
release(&kref.lock);
if (kref.count[i] == 0)
  /* put the page on the free list */

Two harts drop the last two references to one page at the same time. What can go wrong?

A deadlock, because kfree takes kref.lock twice.The page leaks, because both harts read 1.Nothing: the decrement is protected, so the count is always right.Both harts can read 0 after their releases and both free the page: a double free that corrupts the free list.

5The kernel writes too

read(fd, buf, n) in a forked child, where buf is in a page the child has not written since fork. The kernel puts the data in buf with copyout. Does that store take a page fault? What does copyout do today with the shared page, and what must it do? Look at piperead: which locks are held when copyout runs, and what does that forbid your fix to do? Finally, read is not the only system call that writes into user memory. Which call does every shell make after every fork, and what would its failure leave behind in the process table?

The reference design

The kernel’s store does not fault. copyout finds the physical address with walkaddr and writes through the kernel page table’s direct map of RAM, which is writable. The user PTE is looked at only in software. Today, copyout sees that PTE_W is clear and returns -1 (kernel/vm.c:364): the read fails. (If that test were missing, the kernel would write straight into the page every sharer sees, the worst possible outcome.)

So copyout must break the sharing itself: if the PTE has PTE_COW, call the COW handler (the reference’s cowfault), which copies and remaps the page, then write into the physical page it returns. Read-only pages without PTE_COW still fail with -1, which is what usertests copyout checks with a buffer at address 0.

The locking constraint: copyout is called with spinlocks held. In piperead it runs under pi->lock (noff 1), in kwait under wait_lock and the child’s p->lock (noff 2). Holding a spinlock means interrupts are off and the code must not sleep. The handler calls kalloc and kfree, which only take spinlocks and never sleep, so it is legal, and it adds new lock-order edges: pi->lock → kmem.lock, pi->lock → kref.lock, and in kwait a third level, noff 3, measured with gdb in the reveal. If memory is exhausted, cowfault returns 0, copyout returns -1, and the system call fails cleanly; no sleeping wait for memory is possible here.

The other call is wait(&status): kwait copies the exit status out with copyout before it frees the zombie, and gives up with -1 if that fails (kernel/proc.c:390-kernel/proc.c:395). The status variable usually lives in the parent’s stack page, which is shared with the child it just forked. If the COW copy fails, the zombie stays in the process table. That happens in two situations:

copyout does not handle COW at all (clinic 2): every such wait fails, zombies pile up, and fork eventually runs out of process slots.
Memory is exhausted, perhaps by the dying child itself: wait returns -1. In an out-of-memory test run on this branch, the parent’s next store to that still-shared stack page then found no memory either and the parent was killed. Nothing panicked and no page leaked.

Check yourself

1solidFill in the machine state

A forked child (cowtest, pid 6) calls read on a pipe into a buffer it shares copy-on-write with its parent. piperead holds pi->lock and calls copyout, which calls the COW handler, which calls kalloc. Fill in the hart’s state just after kalloc has acquired kmem.lock.

kernel/pipe.c

112piperead(struct pipe *pi, uint64 addr, int n)
113{
int i;
struct proc *pr = myproc();
char ch;
117
acquire(&pi->lock);
while (pi->nread == pi->nwrite && pi->writeopen) { //DOC: pipe-empty
  if (killed(pr)) {
    release(&pi->lock);
    return -1;
  }
  sleep_prepare(&pi->nread); //DOC: piperead-sleep
  release(&pi->lock);
  sleep();
  acquire(&pi->lock);
}
for (i = 0; i < n; i++) { //DOC: piperead-copy
  if (pi->nread == pi->nwrite)
    break;
  ch = pi->data[pi->nread % PIPESIZE];
  if (copyout(pr->pagetable, pr->sz, addr + i, &ch, 1) == -1) {
    if (i == 0)
      i = -1;
    break;
  }
  pi->nread++;
}
wakeup(&pi->nwrite); //DOC: piperead-wakeup
release(&pi->lock);
return i;
143}

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

2warm-upTrue or false, and why

True or false: when copyout writes into a user page, the hardware checks that page’s user PTE, so a copy-on-write page makes copyout fault like a user store.

TrueFalse

Why?

copyout writes to the physical address through the kernel page table’s direct map; the user PTE is only read in software.Supervisor mode ignores PTE permissions entirely.copyout uses sstatus.SUM to write user pages directly, and SUM bypasses W.

6When can you skip the copy?

Parent and child share a page. The child writes it first and gets its own copy; the shared page now has count 1, and only the parent maps it, still read-only with PTE_COW. Later the parent writes it. Does the parent need to copy? What check lets you skip the copy, and is that check safe on three harts without holding kref.lock until the PTE is updated? What if parent and child fault on the same page at the same moment on two harts?

Check yourself

1deepChoose one

The COW handler reads the count with krefcount(pa) (which takes and releases kref.lock) and, if it is 1, sets PTE_W in the faulting process’s PTE. Why is it safe to set PTE_W after the lock has been released?

Only a fork of a process that maps the page can raise the count, and the only such process is the one in the handler; xv6 processes are single-threaded.Because interrupts are off in usertrap, so no other hart can run.It is not safe; the reference has a race here.Because the PTE update is a single atomic store.

7What else frees, flushes, or fails?

Go through every place that unmaps or frees user memory, and every place that changes a PTE. Which need changes for copy-on-write: kexec freeing the old image, kexit and freeproc, sbrk(-n), the error path of uvmcopy itself? After uvmcopy clears PTE_W in the parent’s page table, the parent’s hart may still hold a writable translation in its TLB (translation lookaside buffer). Does it need an sfence.vma?

3. Build it

Start.

git checkout -b my-cow 06aad25

Add your test program first (copy the spec’s list of checks into user/cowtest.c, add $U/_cowtest\ to UPROGS in the Makefile). On the unmodified kernel cowtest big must print fork failed and FAIL: that is the test working.

Milestones, in an order that keeps the system bootable after each one.

Reference counts in kalloc.c. The array, its lock, kalloc setting 1, kfree dropping one, a krefinc, a krefcount, and freerange setting 1 before each boot-time free. Nothing shares pages yet, so every count is 0 or 1. Test: boot, usertests -q. A panic in kfree now means a real double free somewhere (the original kernel would have silently corrupted its free list).
The COW bit and the handler. PTE_COW in riscv.h; a function in vm.c that takes a page table and a virtual address and either makes the page writable (copy, or take over) or returns 0. Nothing calls it yet. Test: it compiles.
The fault path. One new branch in usertrap, before the lazy one, for scause 15. Test: usertests -q (still no shared pages, so behaviour is unchanged).
The kernel’s writes. In copyout, call the handler for PTE_COW pages before the PTE_W test. Test: usertests -q.
Flip the switch: share in uvmcopy. Now everything above is exercised. Test: cowtest, then usertests -q, then cowtest again (a leak in usertests would show as fewer free pages in the second cowtest).

Debugging advice. For breakpoints at boot, start QEMU halted with make qemu-gdb (it adds -S and a gdb port of its own, which it writes into .gdbinit), run ${TOOLPREFIX}gdb kernel/kernel in another terminal, and set them before the first continue; for later events, continue and interrupt with Ctrl-C when you need to. TOOLPREFIX is your RISC-V toolchain’s prefix, the same one xv6’s Makefile detects (riscv64-unknown-elf-, riscv64-linux-gnu- or riscv64-elf-); set it with export TOOLPREFIX=riscv64-unknown-elf- or whichever you have. On Debian/Ubuntu/WSL, gdb-multiarch also works as the debugger.

Print, don’t guess: a temporary printk("cow %s %d va %p ref %d\n", ...) in the handler shows each copy. On the reference, echo hi prints two copies in the shell’s child (stack 0x4000, then data 0x2000) and two takeovers in the shell afterwards.
Count pages: a counter in kalloc attributed to myproc() gives “pages per fork” and “pages per exec” (the measurements below were made that way).
panic: kfree: refcount means some page was dropped more times than it was counted: break on that panic and look at bt (which path), then think about who else dropped it.
usertrap(): unexpected scause 0xf for a process that should live means neither handler accepted the fault: print the PTE (p/x *walk(p->pagetable, va, 0) in gdb) and check V, U, W and bit 8.
A test that hangs: attach gdb, thread apply all bt, and list proc[] states. Usually one process is SLEEPING in piperead and the partner is a ZOMBIE that exited early.

4. Debugging clinic

Each of these bugs was put into the reference solution on purpose and run on three harts. The symptom is exactly what happened. Try to explain it before revealing why.

1The reference counts are not locked

Every acquire(&kref.lock) / release(&kref.lock) pair in kalloc.c removed (in kfree, kalloc, krefinc and krefcount); everything else as in the reference:

-  acquire(&kref.lock);
   if (kref.count[PA2REF(pa)] < 1)
     panic("kfree: refcount");
   n = --kref.count[PA2REF(pa)];
-  release(&kref.lock);
   if (n > 0)
     return; // another page table still maps it

In this build the decrement is lw at 0x80000a6a, then seven instructions, then sw at 0x80000a80: nine instructions from load to store.

What happened when we ran it

$ refrace 500
refrace: free pages 32440 before, 32440 after: OK
$ refrace 500
refrace: free pages 32440 before, 32439 after: FAIL
$ refrace 500
refrace: free pages 32439 before, 32439 after: OK
$ refrace 500
refrace: free pages 32439 before, 32439 after: OK
$ refrace 500
refrace: free pages 32439 before, 32439 after: OK
$

(another boot)
$ refrace 500
refrace: free pages 32440 before, 32440 after: OK
$ refrace 500
refrace: free pages 32440 before, 32441 after: FAIL
panic: kfree: refcount

Honest summary first: usertests -q and cowtest never caught this bug. On 3 boots of this kernel (3 harts), each running usertests -q twice and cowtest five times, all 21 runs passed, cowtest always reporting 32,436 free pages before and after.

It took a stress program written for it, refrace (not part of the branch): three workers, each doing fork + exit + wait 500 times, with free pages counted before and after. The workers and all their short-lived children share the program’s text pages, so every fork (krefinc) and every exit (kfree via uvmunmap) on any hart does a read-modify-write of the same few counters. It ran 5 times on each of 6 fresh boots: boots 1 and 3 printed five OK lines; boot 2 is the first block above (one leaked page); boots 4, 5 and 6 ended in panic: kfree: refcount (boot 6 is the second block; boot 5 first leaked a page between runs, then panicked on its fifth run). 4 boots of 6 went wrong. On the reference branch the same program printed OK every time.

Two kinds of lost update show up, exactly as predicted in the think section:

A lost decrement (two harts load the same count, both store count − 1): the count never reaches 0, the page is never freed. 32440 before, 32439 after is one leaked page. Nothing crashes; the memory is simply gone until reboot (boot 2, and between the second and third run of boot 5).
A lost increment (a fork on one hart and an exit on another, overlapping): the count is one too low, so it reaches 0 while a page table still maps the page. kfree puts a page that is still in use on the free list: one page more than before (32441). The next drop of that page by the page table that still maps it finds count 0, and the check added in commit 1 panics with kfree: refcount. Without that check, the page would have been handed to someone else while still mapped: silent corruption of two processes.

Why did gdb hide it? With gdb attached and a breakpoint inserted, QEMU’s timing changes; 8 logged runs under gdb showed nothing. This is typical of races: the observation changes the odds. We also ran a copy with the window artificially widened (a 1000-iteration delay loop between the load and the store): refrace failed on its first run with 32441 and the same panic, yet usertests -q and cowtest still passed on that copy, because they rarely change the same counter from two harts at once.

The lesson: a passing test suite says little about a missing lock. Reason it out from the interleaving table, then write a test that makes the interleaving likely.

2copyout does not handle copy-on-write pages

The new block in copyout is missing, so a COW destination falls into the existing PTE_W test:

     pte = walk(pagetable, va0, 0);
-    // the kernel's own writes do not fault: copy a
-    // copy-on-write page here, as a user store would.
-    if ((*pte & PTE_COW) != 0) {
-      if ((pa0 = cowfault(pagetable, va0)) == 0)
-        return -1;
-    }
     // forbid copyout over read-only user text pages.
     if ((*pte & PTE_W) == 0)
       return -1;

What happened when we ran it

$ cowtest
cowtest: big: OK
cowtest: lazy: OK
cowtest: copyout: FAIL
cowtest: independence: OK
cowtest: text: FAIL
cowtest: forks: FAIL
cowtest: free pages 32436 before, 32428 after
cowtest: no leaks: FAIL
cowtest: SOME TESTS FAILED
$ usertests -q
usertests starting
test copyin: OK
...
test twochildren: OKpreempt: preempt read errorx
...
test sbrkfail: OK
test sbrkarg: runtest: fork error
 pipe1 oops 3 total 0
pipe1: pipe1 oops 1
forkfocreateforkteMAXVAplus: fork failed
sbrkfail: no allocation failed; allocate more?
sbrkfail: fork failed
kernmem: fork failed
...
openiput: fork failed
$

copyout: FAIL is the direct effect: the child’s read into a buffer it shares with its parent returns -1, because copyout sees a PTE without PTE_W.

The other failures come from a less obvious user of copyout: wait. kwait copies the child’s exit status into *addr with copyout (kernel/proc.c:390) before it frees the zombie, and if that fails it returns -1 and leaves the zombie in the process table (kernel/proc.c:391-kernel/proc.c:395). A parent that forks and then calls wait(&status) without storing to its stack in between still has its stack page shared copy-on-write, so every such wait fails:

text: FAIL: the child was killed as it should be, but wait(&xstatus) failed and xstatus was never written.
forks: FAIL: texttest’s killed child (exit status -1) is still an unreaped zombie, and the first childok() in forkstest reaps that zombie instead of one of its own children. (The children’s waits for their grandchildren succeed: int xs = 1; stores to the child’s stack first, which gives it a private stack page, and childok’s prologue stores ra before calling wait. An instrumented copy confirmed it: the failed copyout is texttest’s, the late reap happens inside forkstest.)
no leaks: FAIL: 8 pages still held by the one forks child left unreaped when countfree runs.

In usertests, run does exactly that pattern, fork() then wait(&xstatus) (user/usertests.c:3427), and does not check wait’s return value. wait returns -1 at once (it finds the previous test’s unreaped zombie and fails to copy out its status), xstatus is never written (its stack slot happens to hold 0), and run prints OK while the test is still running. Tests start overlapping, their output interleaves (test twochildren: OKpreempt: preempt read error), unreaped zombies fill the process table, and finally fork itself fails: runtest: fork error. The leftover test processes keep printing fork failed after the shell prompt is back.

One missing if in copyout breaks read, wait and through them half of usertests, with not a single panic.

3Every page becomes copy-on-write, including text

In uvmcopy, the PTE_W test is dropped, so read-only pages are marked COW too:

-    if (*pte & PTE_W) {
-      // the parent must stop writing it too.
-      *pte = (*pte & ~PTE_W) | PTE_COW;
-    }
+    *pte = (*pte & ~PTE_W) | PTE_COW;

What happened when we ran it

$ cowtest
cowtest: big: OK
cowtest: lazy: OK
cowtest: copyout: OK
cowtest: independence: OK
cowtest: text: FAIL
cowtest: forks: OK
cowtest: free pages 32436 before, 32436 after
cowtest: no leaks: OK
cowtest: SOME TESTS FAILED
$ usertests -q
usertests starting
test copyout: usertrap(): unexpected scause 0x2 pid=211
            sepc=0x676 stval=0x2c61646b
FAILED
SOME TESTS FAILED

4The fork error path frees the parent’s page

In uvmcopy, the error path keeps the shape of the original code, which freed the page it had just allocated (kfree(mem)), but now there is no new page, so it frees the shared one:

-    if (mappages(new, i, PGSIZE, pa, flags) != 0)
-      goto err;
+    if (mappages(new, i, PGSIZE, pa, flags) != 0) {
+      kfree((void *)pa);
+      goto err;
+    }
     krefinc(pa); // the child's page table maps it too

The error path only runs when mappages cannot allocate a page-table page, so we used a trigger program (forkoom, not part of the branch): allocate every free page with sbrk, give back k pages, fork, for k = 2, 4, 6, … 40.

What happened when we ran it

$ forkoom
forkoom: 2 pages free: fork failed
usertrap(): unexpected scause 0xc pid=3
            sepc=0x1000 stval=0x1000
panic: kfree: refcount

# gdb, breakpoint on the new kfree in uvmcopy:
uvmcopy (old=0x87f28000, new=0x80041000, sz=132874240) at kernel/vm.c:317
#1 kfork () at kernel/proc.c:271  #2 sys_fork  #3 syscall  #4 usertrap
i = 0x0, pa = 0x87f25000, kref.count[pa] = 1
# after the kfree:
kref.count[pa] = 0
0x87f25000:  0x00000000  0x00000000  0x01010101  0x01010101
# breakpoint on the panic:
#0 kfree (pa=0x87f25000) at kernel/kalloc.c:72
#1 uvmunmap (pagetable=0x87f28000, va=0, npages=32440, do_free=1)
#2 uvmfree  #3 proc_freepagetable  #4 freeproc (p=<proc+720>)
#5 kwait (addr=0)  #6 sys_wait  #7 syscall  #8 usertrap
myproc()->name = "sh", pid 2, mycpu()->noff = 3

# the reference branch, same program: "fork failed" for every k,
# then cowtest: ALL OK.

5Only the child’s PTE is made copy-on-write

uvmcopy computes read-only COW flags for the child but leaves the parent’s PTE writable:

-    if (*pte & PTE_W) {
-      // the parent must stop writing it too.
-      *pte = (*pte & ~PTE_W) | PTE_COW;
-    }
     flags = PTE_FLAGS(*pte);
+    if (flags & PTE_W)
+      flags = (flags & ~PTE_W) | PTE_COW;

What happened when we ran it

$ cowtest
cowtest: big: OK
cowtest: lazy: OK
cowtest: copyout: OK
cowtest: independence: FAIL
usertrap(): unexpected scause 0xf pid=8
            sepc=0x55c stval=0x508
cowtest: text: OK
cowtest: forks: OK
cowtest: free pages 32436 before, 32436 after
cowtest: no leaks: OK
cowtest: SOME TESTS FAILED
$ usertests -q
usertests starting
...
ALL TESTS PASSED

6Off by one in the reference-count index

The index macro adds one, a typical slip when thinking of “page numbers” as counting from 1:

-#define PA2REF(pa) (((uint64)(pa) - KERNBASE) / PGSIZE)
+#define PA2REF(pa) (((uint64)(pa) - KERNBASE) / PGSIZE + 1)

What happened when we ran it

$ cowtest
...
cowtest: free pages 32436 before, 32436 after
cowtest: ALL OK
$ usertests -q
...
ALL TESTS PASSED

# gdb, before kvminit (after kinit):
p &kref.count[32768]      = (int *) 0x8002f9d8 <pid_lock>
p &pid_lock               = (struct spinlock *) 0x8002f9d8 <pid_lock>
p pid_lock.locked         = 0
# after kvminit, before procinit:
p/x kernel_pagetable      = 0x87fff000
p pid_lock.locked         = 1
# after procinit:
p pid_lock.locked         = 0

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

f3e6e37 Count references to each physical page in kalloc
kernel/defs.h
@@ -59,8 +59,10 @@ void ireclaim(int);
5959// kalloc.c
6060void* kalloc(void);
6161void kfree(void *);
6262void kinit(void);
63void krefinc(uint64);
64int krefcount(uint64);
6365
6466// log.c
6567void initlog(int, struct superblock*);
6668void log_write(struct buf*);
kernel/kalloc.c
@@ -22,36 +22,60 @@ struct {
2222 struct spinlock lock;
2323 struct run *freelist;
2424} kmem;
2525
26// Reference counts, one per physical page from KERNBASE to
27// PHYSTOP: how many page tables map the page (a page that
28// kalloc returned and nobody has shared yet has count 1).
29// kfree drops one reference and frees the page at zero.
30#define PA2REF(pa) (((uint64)(pa) - KERNBASE) / PGSIZE)
31
32struct {
33 struct spinlock lock;
34 int count[(PHYSTOP - KERNBASE) / PGSIZE];
35} kref;
36
2637void
2738kinit()
2839{
2940 initlock(&kmem.lock, "kmem");
41 initlock(&kref.lock, "kref");
3042 freerange(end, (void *)PHYSTOP);
3143}
3244
3345void
3446freerange(void *pa_start, void *pa_end)
3547{
3648 char *p;
3749 p = (char *)PGROUNDUP((uint64)pa_start);
38 for (; p + PGSIZE <= (char *)pa_end; p += PGSIZE)
50 for (; p + PGSIZE <= (char *)pa_end; p += PGSIZE) {
51 kref.count[PA2REF(p)] = 1; // kfree drops this to 0
3952 kfree(p);
53 }
4054}
4155
42// Free the page of physical memory pointed at by pa,
43// which normally should have been returned by a
56// Drop one reference to the page of physical memory pointed
57// at by pa, which normally should have been returned by a
4458// call to kalloc(). (The exception is when
4559// initializing the allocator; see kinit above.)
60// The page is freed when its last reference is dropped.
4661void
4762kfree(void *pa)
4863{
4964 struct run *r;
65 int n;
5066
5167 if (((uint64)pa % PGSIZE) != 0 || (char *)pa < end || (uint64)pa >= PHYSTOP)
5268 panic("kfree");
5369
70 acquire(&kref.lock);
71 if (kref.count[PA2REF(pa)] < 1)
72 panic("kfree: refcount");
73 n = --kref.count[PA2REF(pa)];
74 release(&kref.lock);
75 if (n > 0)
76 return; // another page table still maps it
77
5478 // Fill with junk to catch dangling refs.
5579 memset(pa, 1, PGSIZE);
5680
5781 r = (struct run *)pa;
@@ -75,8 +99,35 @@ kalloc(void)
7599 if (r)
76100 kmem.freelist = r->next;
77101 release(&kmem.lock);
78102
79 if (r)
103 if (r) {
80104 memset((char *)r, 5, PGSIZE); // fill with junk
105 acquire(&kref.lock);
106 kref.count[PA2REF(r)] = 1;
107 release(&kref.lock);
108 }
81109 return (void *)r;
82110}
111
112// Add a reference to page pa: one more page table maps it.
113void
114krefinc(uint64 pa)
115{
116 acquire(&kref.lock);
117 if (kref.count[PA2REF(pa)] < 1)
118 panic("krefinc");
119 kref.count[PA2REF(pa)]++;
120 release(&kref.lock);
121}
122
123// How many page tables map page pa.
124int
125krefcount(uint64 pa)
126{
127 int n;
128
129 acquire(&kref.lock);
130 n = kref.count[PA2REF(pa)];
131 release(&kref.lock);
132 return n;
133}
922cf8d Add cowfault to copy a shared page on first write
kernel/defs.h
@@ -171,8 +171,9 @@ int copyout(pagetable_t, uint64, uint64, char *, uint64);
171171int copyin(pagetable_t, uint64, char *, uint64, uint64);
172172int copyinstr(pagetable_t, uint64, char *, uint64, uint64);
173173int ismapped(pagetable_t, uint64);
174174uint64 vmfault(pagetable_t, uint64, uint64, int);
175uint64 cowfault(pagetable_t, uint64);
175176
176177// plic.c
177178void plicinit(void);
178179void plicinithart(void);
kernel/riscv.h
@@ -396,8 +396,9 @@ typedef uint64 *pagetable_t; // 512 PTEs
396396#define PTE_R (1L << 1)
397397#define PTE_W (1L << 2)
398398#define PTE_X (1L << 3)
399399#define PTE_U (1L << 4) // user can access
400#define PTE_COW (1L << 8) // RSW bit: copy-on-write page
400401
401402// shift a physical address to the right place for a PTE.
402403#define PA2PTE(pa) ((((uint64)pa) >> 12) << 10)
403404
kernel/vm.c
@@ -476,8 +476,46 @@ vmfault(pagetable_t pagetable, uint64 psz, uint64 va, int read)
476476 }
477477 return mem;
478478}
479479
480// give the process its own writable copy of the copy-on-write
481// page at va, after a write to it. if this page table holds the
482// only reference, make the page writable again instead of copying.
483// returns the physical address of the writable page, or 0 if va
484// is not a copy-on-write user page or out of physical memory.
485uint64
486cowfault(pagetable_t pagetable, uint64 va)
487{
488 pte_t *pte;
489 uint64 pa;
490 uint flags;
491 char *mem;
492
493 if (va >= MAXVA)
494 return 0;
495 va = PGROUNDDOWN(va);
496 pte = walk(pagetable, va, 0);
497 if (pte == 0)
498 return 0;
499 if ((*pte & (PTE_V | PTE_U | PTE_COW)) != (PTE_V | PTE_U | PTE_COW))
500 return 0;
501 pa = PTE2PA(*pte);
502 flags = (PTE_FLAGS(*pte) | PTE_W) & ~PTE_COW;
503
504 if (krefcount(pa) == 1) {
505 // nobody else shares it any more: take it over.
506 *pte = PA2PTE(pa) | flags;
507 return pa;
508 }
509
510 if ((mem = kalloc()) == 0)
511 return 0;
512 memmove(mem, (char *)pa, PGSIZE);
513 *pte = PA2PTE(mem) | flags;
514 kfree((void *)pa); // drop this page table's reference
515 return (uint64)mem;
516}
517
480518int
481519ismapped(pagetable_t pagetable, uint64 va)
482520{
483521 pte_t *pte = walk(pagetable, va, 0);
b013bd4 Handle store faults on copy-on-write pages in usertrap
kernel/trap.c
@@ -67,8 +67,10 @@ usertrap(void)
6767
6868 syscall();
6969 } else if ((which_dev = devintr()) != 0) {
7070 // ok
71 } else if (r_scause() == 15 && cowfault(p->pagetable, r_stval()) != 0) {
72 // store to a copy-on-write page
7173 } else if ((r_scause() == 15 || r_scause() == 13) &&
7274 vmfault(p->pagetable, p->sz, r_stval(),
7375 (r_scause() == 13) ? 1 : 0) != 0) {
7476 // page fault on lazily-allocated page
261e3f3 Break copy-on-write sharing in copyout
kernel/vm.c
@@ -359,8 +359,14 @@ copyout(pagetable_t pagetable, uint64 psz, uint64 dstva, char *src, uint64 len)
359359 }
360360 }
361361
362362 pte = walk(pagetable, va0, 0);
363 // the kernel's own writes do not fault: copy a
364 // copy-on-write page here, as a user store would.
365 if ((*pte & PTE_COW) != 0) {
366 if ((pa0 = cowfault(pagetable, va0)) == 0)
367 return -1;
368 }
363369 // forbid copyout over read-only user text pages.
364370 if ((*pte & PTE_W) == 0)
365371 return -1;
366372
e669202 Share user pages in fork instead of copying them
kernel/vm.c
@@ -288,36 +288,35 @@ uvmfree(pagetable_t pagetable, uint64 sz)
288288 uvmunmap(pagetable, 0, PGROUNDUP(sz) / PGSIZE, 1);
289289 freewalk(pagetable);
290290}
291291
292// Given a parent process's page table, copy
293// its memory into a child's page table.
294// Copies both the page table and the
295// physical memory.
292// Given a parent process's page table, share
293// its memory with a child's page table.
294// Writable pages become copy-on-write in both:
295// read-only, with PTE_COW set. No memory is copied.
296296// returns 0 on success, -1 on failure.
297// frees any allocated pages on failure.
297// drops the child's references on failure.
298298int
299299uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
300300{
301301 pte_t *pte;
302302 uint64 pa, i;
303303 uint flags;
304 char *mem;
305304
306305 for (i = 0; i < sz; i += PGSIZE) {
307306 if ((pte = walk(old, i, 0)) == 0)
308307 continue; // page table entry hasn't been allocated
309308 if ((*pte & PTE_V) == 0)
310309 continue; // physical page hasn't been allocated
311310 pa = PTE2PA(*pte);
311 if (*pte & PTE_W) {
312 // the parent must stop writing it too.
313 *pte = (*pte & ~PTE_W) | PTE_COW;
314 }
312315 flags = PTE_FLAGS(*pte);
313 if ((mem = kalloc()) == 0)
316 if (mappages(new, i, PGSIZE, pa, flags) != 0)
314317 goto err;
315 memmove(mem, (char *)pa, PGSIZE);
316 if (mappages(new, i, PGSIZE, (uint64)mem, flags) != 0) {
317 kfree(mem);
318 goto err;
319 }
318 krefinc(pa); // the child's page table maps it too
320319 }
321320 return 0;
322321
323322err:
055c288 Add cowtest, a test program for copy-on-write fork
Makefile
@@ -149,8 +149,9 @@ UPROGS=\
149149 $U/_logstress\
150150 $U/_forphan\
151151 $U/_dorphan\
152152 $U/_sync\
153 $U/_cowtest\
153154
154155fs.img: mkfs/mkfs README $(UPROGS)
155156 mkfs/mkfs fs.img README $(UPROGS)
156157
user/cowtest.c
@@ -0,0 +1,271 @@
1//
2// tests for copy-on-write fork.
3// each test prints "cowtest: <name>: OK" or "... FAIL".
4//
5
6#include "kernel/types.h"
7#include "kernel/riscv.h"
8#include "kernel/memlayout.h"
9#include "user/user.h"
10
11int failed;
12
13void
14result(char *name, int ok)
15{
16 printf("cowtest: %s: %s\n", name, ok ? "OK" : "FAIL");
17 if (!ok)
18 failed = 1;
19}
20
21// wait for one child; return 1 if it exited with status 0.
22int
23childok(void)
24{
25 int xstatus;
26
27 if (wait(&xstatus) < 0)
28 return 0;
29 return xstatus == 0;
30}
31
32// count free pages by allocating them all with sbrk.
33int
34countfree(void)
35{
36 char *sz0 = sbrk(0);
37 int n = 0;
38
39 while (sbrk(PGSIZE) != SBRK_ERROR)
40 n++;
41 sbrk(-(sbrk(0) - sz0));
42 return n;
43}
44
45// allocate 60% of RAM (more than half of the free memory), fork,
46// and let both processes write. without copy-on-write the fork
47// fails for lack of memory.
48void
49bigtest(void)
50{
51 uint64 sz = (PHYSTOP - KERNBASE) / 10 * 6;
52 char *p = sbrk(sz);
53 int ok = 1;
54
55 if (p == SBRK_ERROR) {
56 printf("cowtest: sbrk(%ld) failed\n", sz);
57 result("big", 0);
58 return;
59 }
60 for (char *q = p; q < p + sz; q += PGSIZE)
61 *(int *)q = getpid();
62
63 int pid = fork();
64 if (pid < 0) {
65 printf("cowtest: fork failed\n");
66 result("big", 0);
67 sbrk(-sz);
68 return;
69 }
70 if (pid == 0) {
71 int ppid = *(int *)p;
72 // write 100 pages spread over the region.
73 for (char *q = p; q < p + sz; q += sz / 100 / PGSIZE * PGSIZE) {
74 if (*(int *)q != ppid)
75 exit(1);
76 *(int *)q = getpid();
77 }
78 exit(0);
79 }
80 for (char *q = p; q < p + sz; q += sz / 50 / PGSIZE * PGSIZE)
81 *(int *)(q + 8) = 1;
82 ok = childok();
83 for (char *q = p; q < p + sz; q += PGSIZE)
84 if (*(int *)q != getpid())
85 ok = 0;
86 sbrk(-sz);
87 result("big", ok);
88}
89
90// pages that were allocated lazily (sbrklazy) and never touched
91// are not mapped when fork runs. a store to one must still be a
92// lazy allocation, in parent and child, next to shared pages.
93void
94lazytest(void)
95{
96 char *p = sbrklazy(8 * PGSIZE);
97 int ok = 1;
98
99 p[0] = 'p'; // page 0 mapped before fork, pages 1-7 not
100 int pid = fork();
101 if (pid < 0) {
102 result("lazy", 0);
103 return;
104 }
105 if (pid == 0) {
106 if (p[0] != 'p')
107 exit(1);
108 p[0] = 'c'; // copy-on-write fault
109 p[3 * PGSIZE] = 'c'; // lazy-allocation fault
110 if (p[PGSIZE * 5] != 0) // a read fault on a lazy page
111 exit(1);
112 exit(p[0] == 'c' && p[3 * PGSIZE] == 'c' ? 0 : 1);
113 }
114 p[3 * PGSIZE] = 'p';
115 ok = childok() && p[0] == 'p' && p[3 * PGSIZE] == 'p';
116 sbrk(-8 * PGSIZE);
117 result("lazy", ok);
118}
119
120char buf[3 * PGSIZE];
121
122// the kernel writes into a shared page: read() from a pipe into a
123// buffer the child has not touched since fork (copyout's path).
124void
125copyouttest(void)
126{
127 int fds[2];
128 int ok = 1;
129 // six bytes straddling a page boundary inside buf.
130 char *dst = (char *)PGROUNDUP((uint64)buf) + PGSIZE - 3;
131
132 memset(buf, 'x', sizeof(buf));
133 if (pipe(fds) < 0) {
134 result("copyout", 0);
135 return;
136 }
137 int pid = fork();
138 if (pid < 0) {
139 result("copyout", 0);
140 return;
141 }
142 if (pid == 0) {
143 close(fds[1]);
144 int n = read(fds[0], dst, 6);
145 if (n != 6 || memcmp(dst, "hello!", 6) != 0)
146 exit(1);
147 exit(0);
148 }
149 close(fds[0]);
150 write(fds[1], "hello!", 6);
151 close(fds[1]);
152 ok = childok();
153 for (int i = 0; i < sizeof(buf); i++)
154 if (buf[i] != 'x')
155 ok = 0;
156 result("copyout", ok);
157}
158
159int shared = 1;
160
161// after fork, each process's writes are invisible to the other,
162// in both directions.
163void
164independencetest(void)
165{
166 int topar[2], tochild[2];
167 char c;
168
169 shared = 1;
170 if (pipe(topar) < 0 || pipe(tochild) < 0) {
171 result("independence", 0);
172 return;
173 }
174 int pid = fork();
175 if (pid < 0) {
176 result("independence", 0);
177 return;
178 }
179 if (pid == 0) {
180 close(topar[0]);
181 close(tochild[1]);
182 read(tochild[0], &c, 1); // parent has written 2
183 if (shared != 1)
184 exit(1);
185 shared = 3;
186 write(topar[1], "x", 1);
187 read(tochild[0], &c, 1);
188 exit(shared == 3 ? 0 : 1);
189 }
190 close(topar[1]);
191 close(tochild[0]);
192 shared = 2;
193 write(tochild[1], "x", 1);
194 // child has written 3 (read returns 0 if the child exited early)
195 int ok = read(topar[0], &c, 1) == 1 && shared == 2;
196 write(tochild[1], "x", 1);
197 close(topar[0]);
198 close(tochild[1]);
199 ok = childok() && ok;
200 result("independence", ok);
201}
202
203// text is read-only, not copy-on-write: a store must still kill.
204void
205texttest(void)
206{
207 int xstatus;
208 int pid = fork();
209
210 if (pid < 0) {
211 result("text", 0);
212 return;
213 }
214 if (pid == 0) {
215 *(volatile int *)texttest = 0;
216 exit(0);
217 }
218 wait(&xstatus);
219 result("text", xstatus == -1);
220}
221
222// many processes sharing and copying pages at once on all harts.
223void
224forkstest(void)
225{
226 int ok = 1;
227
228 for (int round = 0; round < 5; round++) {
229 for (int i = 0; i < 20; i++) {
230 int pid = fork();
231 if (pid < 0) {
232 ok = 0;
233 break;
234 }
235 if (pid == 0) {
236 shared = i;
237 int pid2 = fork(); // a grandchild shares the copy
238 if (pid2 == 0) {
239 exit(shared == i ? 0 : 1);
240 }
241 int xs = 1;
242 wait(&xs);
243 exit(xs == 0 && shared == i ? 0 : 1);
244 }
245 }
246 for (int i = 0; i < 20; i++)
247 if (!childok())
248 ok = 0;
249 }
250 result("forks", ok);
251}
252
253int
254main(int argc, char *argv[])
255{
256 int free0 = countfree();
257
258 bigtest();
259 lazytest();
260 copyouttest();
261 independencetest();
262 texttest();
263 forkstest();
264
265 int free1 = countfree();
266 printf("cowtest: free pages %d before, %d after\n", free0, free1);
267 result("no leaks", free1 == free0);
268
269 printf(failed ? "cowtest: SOME TESTS FAILED\n" : "cowtest: ALL OK\n");
270 exit(failed);
271}

6. Verify and measure

On the branch (ext/11-cow, 6 commits), built with the project toolchain and run on 3 harts (-smp 3 -m 128M):

$ cowtest
cowtest: big: OK
cowtest: lazy: OK
cowtest: copyout: OK
cowtest: independence: OK
usertrap(): unexpected scause 0xf pid=8
            sepc=0x55c stval=0x508
cowtest: text: OK
cowtest: forks: OK
cowtest: free pages 32436 before, 32436 after
cowtest: no leaks: OK
cowtest: ALL OK
$ usertests -q
usertests starting
test copyin: OK
test copyout: OK
...
test nowrite: usertrap(): unexpected scause 0xf pid=6770
...
OK
...
ALL TESTS PASSED

The usertrap() lines are the expected kills: cowtest text and usertests nowrite store to text and must die. usertests -q passing shows that everything the original kernel did still works: copyout into text still fails, the guard page still faults (stacktest), lazy allocation still works through fork (lazy_*), and the free-page count at the end equals the one at the start. cowtest run again after usertests and again after ls | wc (all in one boot) reports the same 32,436 free pages; since cowtest now requires the counts to be equal, a page freed while still mapped would fail it as surely as a leak.

The same cowtest on the original kernel: cowtest: fork failed, big: FAIL, all other checks OK, 32,468 free pages. The 32-page difference is the reference-count array.

Pages per fork. A scratch copy of each kernel counted every kalloc against the process that made it, and printed the count for each fork and exec (instrumentation not on the branch):

event	original	copy-on-write
`fork` of `sh` (pid 2 → 3)	11 pages: 4 `allocproc` + 5 copied + 2 page-table	6 pages: 4 `allocproc` + 2 page-table
the child’s copies before `exec("echo")`	0	2 (stack `0x4000`, data `0x2000`)
`exec("echo")`	9	9
the shell’s next stores to `0x2000` and `0x4000`	0	0 (two takeovers, no copy)

ls | wc. The shell forks a child (pid 4) that parses the line (allocating a 16-page heap with malloc), creates the pipe, and forks the two sides:

	original	copy-on-write
fork 2 → 4	11	6
fork 4 → 5 (`ls`)	27 (its 16 heap pages copied too)	6
fork 4 → 6 (`wc`)	27	6
copy-on-write copies	0	4 (3 in pid 4, 1 in pid 6) + 1 takeover in pid 5
`exec` of `ls` and `wc`	9 + 9	9 + 9
fork + exec total	83 pages	40 pages

The pages that pid 4’s heap occupies (16), the pipe (1) and exec’s argument pages are the same in both. Copy-on-write halves the cost of a pipeline of tiny programs; the bigger the forking process, the bigger the saving, up to the cowtest big case where the original kernel cannot fork at all.

What it costs. 32 pages (128 KiB) of .bss for the counts, one spinlock round trip per page per fork, and one trap per first write to a shared page (a full uservec / userret round trip plus a 4096-byte copy, the same copy the original fork made eagerly).

7. Go further

Share page-table pages too. fork still allocates the child’s page-table pages (2 for sh, about 40 for cowtest big). Sharing level-0 page-table pages read-only and copying them on demand is how real kernels make fork of a huge process cheap; it teaches how the walk itself can be copy-on-write.
Per-page metadata instead of an array of ints. Replace kref.count with a struct page per physical page (count, flags, a list link). This is how Linux organizes memory, and it prepares for swapping (lab 16) and mmap (lab 15).
Atomic counts without a lock. Use __atomic_fetch_add / __atomic_sub_fetch on the counters (RISC-V amoadd.w) and remove kref.lock. Work out why the decrement-and-test becomes one instruction’s result, and measure lock contention before and after with the refrace program.
vfork. A vfork that lends the parent’s page table to the child until it calls exec costs even less than copy-on-write. Find out what it forbids the child to do, and why.
Threads break the takeover argument. After lab 9 (clone), two threads share a page table, so a count of 1 can rise while the handler is deciding. Fix cowfault for that world.