Step 1 of 17 · commit 1: Count references to each physical page in kalloc

One counter for every page of RAM

The story of this tour, recorded on three harts with gdb attached and with a counting copy of the kernel: the machine boots, you type echo hi, the shell (pid 2) forks pid 3, pid 3 writes its stack and data pages, then calls exec. Later steps follow cowtest’s read into a shared buffer and wait reaping a child.

Commit 1 prepares the allocator for pages with several owners. kref.count has one int per physical page from KERNBASE to PHYSTOP: 32,768 entries, 128 KiB in .bss. In this build kref sits at 0x8000f9c0, right after kmem, and the array begins 24 bytes later, after the spinlock. PA2REF turns a page’s physical address into its index.

The count means “how many page tables map this page”, with one convention: a page that kalloc has handed out counts 1 even before it is mapped (page-table pages, trapframes and pipe buffers are never shared, so they stay at 1).

kref.lock is a new spinlock, separate from kmem.lock. kinit runs on hart 0 before the other harts are released from their wait in main, with interrupts off and paging off; initializing both locks here is the same pattern as before.

Step 2 of 17 · commit 1: Count references to each physical page in kalloc

Every page starts life counted once

freerange hands every page to kfree once, to build the free list. But kfree now drops a reference, and refuses (panics) when the count is already 0. So each page’s count is set to 1 first, and the kfree call brings it to 0, which frees it.

The assignment needs no lock: only hart 0 runs, with interrupts off. Inside kfree, kref.lock and then kmem.lock are taken and released, one after the other, 32,703 times each (the free pages in this build, whose end is 0x80040be8) (noff goes 0 → 1 → 0, intena 0, since interrupts were already off).

Why not let kfree treat count 0 as “fine, free it”? Because then a double free would look exactly like a normal one. With this convention, dropping a page that nobody holds is always a bug, and commit 1 makes it a panic: clinic 4 shows it catching one.

Step 3 of 17 · commit 1: Count references to each physical page in kalloc

kfree drops one reference

Jump ahead to a moment that only makes sense once sharing is on: pid 3 has finished exec("echo") and kexec frees the old image (kernel/exec.c:138). Its first text page is still shared with the shell, so its count is 2. This kfree brings it to 1 and returns at line 76: the page stays where it is, mapped by pid 2.

The decrement and the test for zero are one critical section: the new value goes into the local n while the lock is held, and the decision on line 75 uses n, not a second read of the array. If two harts drop the last two references at once, one gets n = 1 and the other n = 0, and exactly one frees.

The memset junk fill and the free-list push happen only for a page whose count reached 0, after kref.lock is released and before kmem.lock is taken. That is safe: with the count at 0, no page table maps the page any more, so nobody else can reach it. And because the two locks are never held together, there is no ordering to get wrong between them.

State: this is a system call, so usertrap turned interrupts on; the acquire recorded intena 1 and turned SIE off. (No breakpoint was set on this particular kfree; the hart is the one where gdb saw pid 3’s last allocations in kexec, and the lock state follows from the code.) When release pops back to noff 0, interrupts come back on.

Step 4 of 17 · commit 1: Count references to each physical page in kalloc

kalloc sets the count, and two small helpers

kalloc pops a page under kmem.lock exactly as before. A page just popped belongs to nobody else, so its count is set to 1 afterwards, under kref.lock. (The store would be safe even without the lock, since no other hart can know this page yet; taking the lock keeps the rule simple: every access to kref.count holds kref.lock.)

krefinc is what fork will call for every shared page; it panics if the page is not allocated, which catches a whole class of bugs. krefcount reads one count; the fault handler will use it to decide whether a copy is needed at all.

The state shown is from a later commit’s point of view: in the recorded run, pid 3 (the shell’s child, before exec) took a copy-on-write fault and the handler called kalloc. At the focus lines kref.lock is held: noff 1, intena 0, because a page fault leaves interrupts off for the whole handler, so the first acquire saw SIE off. gdb recorded the same state a few lines earlier, at the kmem.freelist read under kmem.lock: noff 1, intena 0, SIE 0, on hart 0.

Step 5 of 17 · commit 2: Add cowfault to copy a shared page on first write

A PTE bit that the hardware ignores

A copy-on-write page and a text page look the same to the hardware: V, R, U set, W clear. The kernel needs to remember which is which, and the place to remember it is the PTE itself. Bits 0-7 are interpreted by the Sv39 walk (V R W X U G A D). Bits 8 and 9, the RSW field, are “reserved for supervisor software”: the hardware ignores them. PTE_COW is bit 8.

Two consequences worth seeing:

• PTE_FLAGS keeps the low 10 bits (0x3FF), so it already carries bit 8 along when a PTE’s flags are copied, and freewalk's leaf test, which looks at R|W|X only, is unaffected.
• A COW PTE observed with gdb on this branch: 0x21fcf1d3, physical page 0x87f3c, flags 0x1d3 = V|R|U|A|D|COW (QEMU sets the A and D bits as pages are used). A text page of sh has X set and never bit 8.

Step 6 of 17 · commit 2: Add cowfault to copy a shared page on first write

cowfault: is this really a copy-on-write page?

The new function. It will be called with whatever address faulted, so it first decides whether the fault is its business, and says no in every doubtful case by returning 0:

• va >= MAXVA: walk would panic on such an address. User programs can produce one: usertests nowrite stores to 0xffffffffffffffff.
• no PTE, or the PTE lacks any of V, U, PTE_COW: an unmapped page (maybe lazy, for vmfault to handle), a text page (no COW bit), or the guard page (no U).

Only then is it a shared page that this process is allowed to write. Line 502 computes the flags of the private version: the old flags with W added and COW removed (so text’s X, if it were ever here, and U, R and the A/D bits carry over).

In the recorded run this is pid 3, the shell’s child, on hart 0, a few instructions after fork returned 0 in it: its first store, to its stack page 0x4000, faulted. gdb showed sp = 0x3fffff9fa0 in the kernel stack whose base is p->kstack = 0x3fffff9000, and noff 0, SIE 0: no lock, interrupts off, as in every page fault (Tour 26: sbrk, eager and lazy, and page faults).

Step 7 of 17 · commit 2: Add cowfault to copy a shared page on first write

The last sharer takes the page over

If this page table holds the only reference, there is nobody to protect: make the PTE writable, clear PTE_COW, keep the page. No allocation, no copy.

In the measured run this happened right after echo hi finished. pid 3 had copied the stack page 0x4000 and the data page 0x2000 (dropping its references to the shell’s originals), and its exec dropped the rest. When the shell (pid 2) next wrote those two pages, both faulted (they were still marked COW in its page table) and both were taken over: the counting kernel printed cow takeover sh 2 va 0x4000 and va 0x2000.

The count is read under kref.lock inside krefcount, and the lock is released before the PTE changes. Safe, because a count of 1 can only rise through a fork of a process that maps the page, and the only such process is this one, which is busy here: xv6 processes have one thread.

Step 8 of 17 · commit 2: Add cowfault to copy a shared page on first write

Copy, remap, drop

The general case, pid 3’s stack page with count 2: allocate a page, copy all 4096 bytes, point this PTE at the copy with W set and COW cleared, then drop this page table’s reference to the original with kfree: 2 → 1, so the shell keeps it.

The order matters. The PTE is rewritten only after the copy is complete, and the old page is released only after the PTE no longer points at it. If kalloc fails, nothing has changed and the function returns 0; the caller then kills the process (a fault) or fails the system call (copyout).

No sfence.vma here. This hart runs on the kernel page table, and the user page table’s new PTE is used only after userret switches satp back, with an sfence.vma before and after (kernel/trampoline.S:110-kernel/trampoline.S:112).

Every call here is short and never sleeps: kalloc and kfree take spinlocks only. That is what makes cowfault callable from places that already hold spinlocks, which is commit 4’s problem.

Step 9 of 17 · commit 3: Handle store faults on copy-on-write pages in usertrap

usertrap: a store fault now has two meanings

One branch, placed before the lazy-allocation branch, for scause 15 only (a load from a shared page is always fine). The two branches can never both claim a fault: cowfault succeeds only for a mapped PTE with V|U|COW, and vmfault succeeds only for an unmapped page below p->sz (kernel/vm.c:463, kernel/vm.c:466). So the order is not about priority; it is just which question is asked first.

Before this commit, the store fault in the child would have gone to vmfault, which returns 0 for any mapped page, and the child would have been killed with unexpected scause 0xf. That is the interaction between the two features: in this tree, a store fault means “lazy page” or “COW page”.

The fault arrives exactly like the lazy faults of Tour 26: sbrk, eager and lazy, and page faults: uservec saved the user registers in the trapframe and moved to pid 3’s empty kernel stack; usertrap left interrupts off (only the system-call branch calls intr_on), so the whole copy runs with SIE 0 and noff 0. epc is not advanced, so the return retries the store.

pid 3's kernel stack, during the fault
  top ─► usertrap
         cowfault
         kalloc / kfree (briefly)

Step 10 of 17 · commit 3: Handle store faults on copy-on-write pages in usertrap

When nobody can fix the fault

cowtest text makes a child (pid 8 in the recorded run) store to its own code at 0x508. Text is R|X|U without bit 8, so cowfault declines; the page is mapped, so vmfault declines; the else branch prints the message and kills it:

usertrap(): unexpected scause 0xf pid=8
            sepc=0x55c stval=0x508

The same branch catches the other refusals: the guard page (no U), an address beyond p->sz, and a copy-on-write fault that found no free memory (cowfault returns 0 when kalloc fails). Out of memory on a COW fault therefore kills the process instead of panicking the kernel, the same policy as for lazy pages. The process cannot be given an error code: it was executing an ordinary store, not a system call.

Step 11 of 17 · commit 4: Break copy-on-write sharing in copyout

copyout: the kernel's writes do not fault

Scene 2: cowtest copyout. pid 6, a child that has not touched buf since fork, reads 6 bytes from a pipe into buf, straddling the pages 0x3000 and 0x4000. Both are shared with the parent, count 2. piperead copies byte by byte, calling copyout for each, with pi->lock held (kernel/pipe.c:133).

copyout writes with memmove to pa0, a physical address, through the kernel page table’s direct map, which maps all RAM writable (kernel/vm.c:42). The hardware never looks at the user PTE, so there is no fault to rely on. The new lines check PTE_COW themselves and call the same cowfault, which returns the physical address of the private copy; the memmove then goes there. The old PTE_W test right below stays: a read into text still fails, as usertests copyout demands.

Note the order relative to vmfault above: an unmapped lazy page is first allocated (fresh, writable, never COW), so it passes straight through.

gdb recorded this exact moment twice in one read, at va 0x3000 and then 0x4000 (the first byte that lands on each page triggers the copy; the rest find PTE_W set): noff 1, intena 1, SIE 0, hart 0.

Step 12 of 17 · commit 4: Break copy-on-write sharing in copyout

A copy under two spinlocks

Inside that copy, cowfault calls kalloc, which takes kmem.lock while pi->lock is still held: noff 2, intena 1 (the outer acquire happened after usertrap's intr_on). gdb confirmed noff 2, intena 1, SIE 0 at line 98.

This is why cowfault must never sleep. sched panics with sched locks if a process tries to give up the CPU with any spinlock other than its own p->lock held (Locks and interrupt state). kalloc and kfree never sleep, so the rule holds; and if memory has run out, copyout just fails and read returns what it copied so far.

The lock-order graph gains edges: pi->lock → kmem.lock and pi->lock → kref.lock. An edge into a lock that takes nothing else cannot close a cycle, since neither kmem.lock nor kref.lock is ever held while acquiring anything.

Step 13 of 17 · commit 5: Share user pages in fork instead of copying them

uvmcopy shares instead of copying

The switch. Back to the start of scene 1: you typed echo hi, and the shell (pid 2) is in kfork, holding its new child’s np->lock since allocproc (through kernel/proc.c:294). gdb recorded noff 1, intena 1 here.

For each mapped page: the same physical address goes into the child’s page table, with the same flags, and krefinc counts the new mapping. No kalloc, no memmove. For sh that is five pages: text 0x0 and 0x1000, data 0x2000, the guard page 0x3000, the stack 0x4000; gdb counted five krefinc calls for this fork. The guard page is writable without U, so it becomes COW without U and the fault handler will refuse it.

The cost of this fork, measured with a counting kernel: 6 pages (4 in allocproc for the trapframe, the root page table and the two page-table pages under the trampoline, plus 2 page-table pages for the child’s low addresses), against 11 in the original (the same 4, plus 5 copied pages and 2 page-table pages).

Unmapped pages (lazy sbrk pages never touched) are skipped as before: there is nothing to share, and each process will fault its own copy in.

Step 14 of 17 · commit 5: Share user pages in fork instead of copying them

The parent must stop writing too

The parent’s PTE is modified in place, before the child’s flags are read from it: PTE_W off, PTE_COW on. Both page tables now say the same thing about the page. Forget the parent’s side and the child is protected but the parent is not: its stores land in the page the child sees (clinic 5, which usertests does not notice).

Read-only pages (text, R|X|U) skip the if and are shared with their flags unchanged: read-only forever, never copied, freed when the last of the sharers lets go.

What about the parent’s TLB (translation lookaside buffer), which may still hold a writable translation for 0x4000? It cannot be used: pid 2 is in the kernel on the kernel page table, and the only way back to user mode is userret, which executes sfence.vma before and after loading satp (kernel/trampoline.S:110-kernel/trampoline.S:112). No other hart can be running pid 2.

Step 15 of 17 · commit 5: Share user pages in fork instead of copying them

Undoing a fork that ran out of memory

mappages can fail: it may need a new page-table page and kalloc can return 0. The order of the two lines in the loop makes the undo exact: the reference is added only after the mapping exists, so on failure pages 0 .. i-1 are mapped and counted, page i is neither, and uvmunmap(new, 0, i / PGSIZE, 1) drops exactly the child’s references.

The parent keeps whatever PTE_COW marks were already made; with count 1 its next store to such a page takes it over, no copy.

We tested this path with a program that leaves only 2 to 40 free pages before calling fork: on this branch every fork failed cleanly, and cowtest passed afterwards. With one extra kfree((void *)pa) here, copied from the old code’s kfree(mem), the parent’s own text page was freed under it: an instruction fault, then panic: kfree: refcount in the shell’s kwait (clinic 4).

Step 16 of 17 · commit 5: Share user pages in fork instead of copying them

exec and exit change nothing

uvmunmap is untouched by the branch, and that is the point. echo has exited, and the shell reaps it in kwait holding wait_lock and the zombie’s p->lock; the zombie’s pages go through this loop and each one through kfree. Here every page reaches 0 and is freed: echo’s image came from its own exec, and the sharing with the shell already ended there (step 3). A zombie that never called exec (a forkstest child in cowtest, say) would only drop references on the pages it still shares with its parent.

Inside each kfree, kref.lock makes it noff 3 for a few instructions: the same depth as the original kernel’s kwait → kfree → kmem.lock. exec dropping an old image (kexec → proc_freepagetable) and sbrk(-n) (uvmdealloc) take the same path. Because the allocator counts, nothing above it needed to learn about sharing.

Step 17 of 17 · commit 6: Add cowtest, a test program for copy-on-write fork

The test that the original kernel fails

cowtest big asks for 60% of the 128 MiB of RAM, 80530632 bytes (19,661 pages), and writes every page, so they are all really allocated. Then it forks. The original kernel would have to copy all of them, with about 12,800 pages left: uvmcopy fails and fork returns -1 (cowtest: fork failed, big: FAIL on the unmodified kernel). With sharing, fork costs page-table pages only.

The child checks that it sees the parent’s values and overwrites 101 pages spread over the region: about 100 copy-on-write faults, one page each. The parent overwrites 51 (at offset 8, so it does not disturb the child’s checks; both loops include the first page), then waits and checks that its values are untouched. Everything fits because only written pages are copied.

The other checks follow the think section one by one: lazy pages after fork, the kernel’s writes (copyout through read, which straddles two pages), independence in both directions, text staying read-only, 100 children and 100 grandchildren on three harts, and a page count before and after.