Step 1 of 20 · commit 1: Reserve a swap area at the end of the disk

A swap area the file system never sees

The story of this tour comes from gdb runs of the reference branch on three harts (QEMU 10.2.1), mostly while swaptest runs: its big test (pid 4) writes and checks 36,000 pages, the main swaptest process (pid 3) waits for it, and later tests fork, use a pipe, and run three big processes at once. Where a state below was not recorded, the note says so.

Commit 1 changes no kernel code. mkfs used to write exactly FSSIZE = 2,000 blocks; now it also writes the very last block of a swap area of NSWAP = 8,192 slots of 4,096 bytes. The file grows to 34,768 blocks (35,602,432 bytes); the blocks in between are never written by mkfs and read back as zeros. param.h gains NSWAP and SWAPSTART (= FSSIZE), shared by mkfs and the kernel.

The superblock’s size stays 2,000. That one decision is the whole protection: the kernel’s balloc only hands out blocks below sb.size (kernel/fs.c:74), so no file can ever be given a block of the swap area, and no code path except the swapping code will ever name one.

QEMU’s virtio disk takes its size from the image file, so the bigger file is all the device needs. (A smaller image would make the device fail the request; the driver then panics with virtio_disk_intr status; reasoned from the driver, not run.)

Step 2 of 20 · commit 2: Let the disk driver transfer a whole page

One request for a whole page

virtio_disk_rw used to take its sector, data address and length from the buffer: b->blockno, b->data, BSIZE. Its body is now disk_rw (line 218), which takes them as arguments; virtio_disk_rw passes the old values, so the file system sees no change.

virtio_disk_rwpage asks for PGSIZE = 4,096 bytes starting at blockno, four consecutive blocks, in one request. The data descriptor points at the physical page itself (line 255 of disk_rw): the device reads or writes guest physical memory, and in the kernel’s direct map a page’s address is its physical address. No copy through a buffer.

The struct buf argument survives for one reason: the completion protocol. disk_rw sets b->disk = 1, sleeps on b, and virtio_disk_intr clears b->disk and wakes b (lines 287–292 and kernel/virtio_disk.c:326). The swap code passes a struct buf of its own, used only as that sleep channel and flag; its 1,024-byte data array is never touched.

Getting PGSIZE wrong here (clinic 6) loses three quarters of every page, silently.

Step 3 of 20 · commit 3: Add swap slots

Slots, with a count of their users

The new file starts with the slot allocator. SLOTBLOCK(s) is the first block of slot s: 2,000 + 4s.

A slot is not just used or free: ref[s] counts the PTEs that refer to it, because fork will let a parent and a child share one swapped-out page (commit 5). swapalloc takes the first slot with count 0 and sets it to 1; swapdup adds one; swapfree drops one, and the slot is free again at 0. A uchar is enough: one slot can be shared by at most NPROC = 64 processes, and swapdup panics before the count could wrap.

The lock is a spinlock, slots.lock, and that is a requirement, not a convenience: swapfree will be called from uvmunmap, and when kwait frees a zombie it runs uvmunmap holding wait_lock and the child’s p->lock. A sleep-lock there would panic in sched. Nothing inside the critical sections sleeps or takes another lock.

swapalloc scans from slot 0 every time: at most 8,192 bytes, under a lock that is held only by eviction. Simple beats clever here.

Step 4 of 20 · commit 4: Keep a frame table: which process maps each user page

The frame table, a map from pages back to PTEs

A page table maps a virtual address to a physical page. Eviction needs the opposite: given a physical page, which PTE maps it? In this kernel a user page is mapped by exactly one PTE (fork copies pages), so the answer is one (process, virtual address) pair per page. ft.f has one entry for every page from KERNBASE to PHYSTOP: 32,768 entries of 16 bytes, 512 KiB of .bss. In this build ft is 0x80020 bytes, and the kernel’s end moves from 0x80020bb0 to 0x800a40b8 with all the branch’s additions: 131 fewer free pages, 128 of them this table.

FRAME(pa) is the index, FRAMEPA(i) the way back. An entry with proc = 0 is not a user page: page-table pages, trapframes, kernel stacks, pipe buffers and free pages are never recorded, and so can never be chosen for eviction.

ft.lock protects the entries (and, from commit 9, the clock hand). Its place in the lock order is fixed by its users: uvmunmap clears entries while freeproc holds the zombie’s p->lock, so p->lock comes before ft.lock. Commit 9 has to respect that.

Step 5 of 20 · commit 4: Keep a frame table: which process maps each user page

Every fresh user page is recorded

uvmalloc records each page right after mappages has mapped it: ftset(mem, myproc(), a) (line 241). The same call appears in vmfault's lazy path and in uvmcopy, which now receives the child (np) as a fourth argument, because the pages it maps belong to the child, not to myproc(). Swap-in will be the fourth place. uvmunmap clears the entry just before it frees the page (line 209).

myproc() in uvmalloc is right for both of its callers: sbrk grows the calling process, and kexec allocates the new image for the calling process. The new image is mapped in a page table that is not yet p->pagetable: the entry says “pid 4, va a” while p->pagetable maps something else at a. Commit 9’s clock checks for exactly that.

(State: a lazy sbrk never reaches uvmalloc; this is the eager path, as in usertests’ sbrkmuch. Reasoned from the code, not recorded.)

Step 6 of 20 · commit 5: Mark swapped-out PTEs, free their slots, share them on fork

What a page in swap looks like

When V is clear, the RISC-V page-table walk stops and faults without looking at any other bit of the PTE: the rest is the kernel’s. The reference uses it as follows:

PTE_SWAP is bit 8, one of the two RSW bits reserved for supervisor software. Any bit would do when V is clear, but a dedicated, named bit is what lets the code tell a swapped page from a zero PTE, which in this tree already means “lazily allocated, not touched yet”.

A real one, recorded by gdb in swapin: 0x10b516 = slot 0x10b516 >> 10 = 1,069, flags 0x116 = R W U PTE_SWAP. Slot 1,069 is blocks 6,276 to 6,279 of fs.img.

Step 7 of 20 · commit 5: Mark swapped-out PTEs, free their slots, share them on fork

uvmunmap gives slots back

Every path that gives back user memory ends here: exit (through the parent’s kwait → freeproc), kexec dropping the old image, sbrk(-n) through uvmdealloc. A swapped PTE now has its own case, before the V test that used to skip it: drop the PTE’s reference to the slot (if the caller frees memory at all) and clear the PTE.

The state shown is the worst case, reasoned from the code: a parent reaping a zombie holds wait_lock and the zombie’s p->lock (noff 2), and swapfree adds slots.lock for a moment (noff 3). That is why slot counts are protected by a spinlock and swapfree never sleeps.

Without these six lines, nothing crashes at first. Clinic 4 removes them: after two tests the swap area is full, and the third test’s process is killed for lack of memory, with 8,184 of the 8,192 slots owned by processes that no longer exist.

Step 8 of 20 · commit 5: Mark swapped-out PTEs, free their slots, share them on fork

fork shares the slot

uvmcopy runs under the child’s np->lock (from allocproc until kernel/proc.c:294), so it may not sleep, and reading a page from the disk sleeps. It does not need to: it gives the child the same PTE, slot number and permissions included, and counts one more reference. Each process will read its own copy when it touches the page; the second reader finds the slot still there because the count kept it alive.

Recorded: swaptest’s main process (pid 3) forks a test child, and its data page 0x2000 is in swap: *pte = 0x116, slot 0, flags R W U PTE_SWAP. gdb printed slots.ref[0] = 1 just before swapdup (line 323), and noff 1, intena 1, SIE 0, on hart 1. Page 0x2000 holds the program’s globals, npages among them: this exact sharing is what keeps the child’s npages at 36,000. Clinic 3 removes the case, the child gets a zero page there, and the syscalls test copies 0 pages.

walk(new, i, 1) may allocate page-table pages for the child with kalloc: that is the reserve of free pages at work (commit 10), since no eviction is possible under np->lock. If it fails, the error path’s uvmunmap drops the references the child already holds, slots included.

Step 9 of 20 · commit 6: Read a swapped-out page back in on a page fault

vmfault: a third kind of missing page

vmfault already handles every user page fault and every copyin or copyout that finds no mapping. It now asks one more question before the old ones: is there a PTE marked PTE_SWAP? If so the page exists, on disk, and swapin brings it back. Only then come the old cases: mapped (decline) or lazy (allocate a zero page). Without the new test, the lazy branch would map a zero page over the swapped PTE and the data would be lost.

Recorded: pid 4 (swaptest big, checking its pages) loads from 0x5da1000, whose PTE is 0xe6d16: slot 923, R W U. Hart 2, noff 0, sstatus = 0x200000020 (SIE clear, SPIE set): as in every page fault (Tour 26: sbrk, eager and lazy, and page faults), usertrap left interrupts off, and vmfault will sleep with them off. That is allowed: sleep only requires that no spinlock but p->lock be held, and the scheduler turns interrupts on for itself.

Step 10 of 20 · commit 6: Read a swapped-out page back in on a page fault

swapin

The order of the steps is the point:

1. Get a page (line 137). From commit 10 this is ualloc, which may evict another page first, so swapin must not hold swapio.lock yet: the eviction takes it too.
2. Read the slot into it, holding the sleep-lock swapio.lock (lines 142–144). Swap I/O is one page at a time; and, more important, a page that is still being written out holds that lock until its write completes (commit 9), so this read can never see a half-written slot.
3. Only then rebuild the PTE: the new page, the saved permissions, V (line 146). Until this line, an access from anywhere would still fault and land here again.
4. Record the page in the frame table and drop this PTE’s reference to the slot.

Recorded right after the read, at the PTE line (line 256 in the branch head): pid 4, va 0x5d0f000, slot 1,069, *pte = 0x10b516, the new page at 0x83074000. gdb showed swapio.lock free again (locked = 0), noff 0, interrupts off, hart 0.

Between step 1 and step 3, could anyone change this PTE? Only pid 4 itself: it is RUNNING, so other harts’ evictions leave its pages alone (commit 9), and a sleep in step 2 does not matter because a swapped PTE has nothing to evict.

Step 11 of 20 · commit 6: Read a swapped-out page back in on a page fault

usertrap keeps its fault registers

Two small changes, both because a page fault can now sleep.

scause and stval are read once, into locals, before anything else. While pid 4 sleeps in swapin, its hart runs other processes, which trap and overwrite those registers; pid 4 may even resume on another hart. The old code read them again after vmfault returned, to print the kill message. The message now prints the saved values and p->trapframe->epc.

The fault test (lines 76–77) now also accepts scause 12, an instruction page fault: a text page can be evicted like any other, and fetching an instruction from it must bring it back. In the recorded run the clock took one of pid 3’s text pages (0x21fc881b: V R X U) while pid 3 slept in wait; its next fetch from that page will be a cause-12 fault. Before this lab such a fault was always fatal. A fetch from a lazy heap page still ends in a kill, one fault later: vmfault maps it without X, the fetch faults again, and the page is now mapped.

Step 12 of 20 · commit 7: Keep copyin and copyout from losing their page

copyout keeps its page by staying on its hart

copyout turns a user address into a physical one with walkaddr, then writes there through the kernel’s direct map. That physical address is only good while the page stays where it is. A system call runs with interrupts on; a timer interrupt between walkaddr and memmove would yield, making the process RUNNABLE, and another hart’s clock could then evict the page and give it to someone else. The memmove would write into a stranger’s memory.

push_off at line 375 closes that window: with interrupts off no timer can preempt this hart, the process stays RUNNING, and RUNNING processes’ pages are not taken. The translation, the PTE_W check and the copy all happen inside it. vmfault can sleep, so the loop pops out (line 378), lets it bring the page in, and then translates again from the top (line 382): it does not trust the physical address vmfault returned, because the page may have moved again before the push_off.

The state shown is reasoned, not recorded: swapstat’s copyout runs with no lock, so after line 375 noff is 1 and intena 1 (interrupts were on). copyin and copyinstr get the same treatment.

Step 13 of 20 · commit 7: Keep copyin and copyout from losing their page

copyin under pi->lock

Recorded in the branch head, during swaptest syscalls: pid 5 writes from 0x5000 to a pipe; pipewrite holds pi->lock and calls copyin for one byte at a time (kernel/pipe.c:96). At the memmove (line 426) gdb showed noff 2 (pi->lock and this push_off), intena 1, SIE 0, pa0 = 0x804f3000, on hart 1. The page is in memory because sys_write pinned it first (commit 8).

Here the push_off adds nothing: the spinlock already keeps interrupts off. What matters is the other branch (line 417): if this page were not in memory, vmfault would read it from the disk with pi->lock held, and sched would panic. Nothing in commit 7 prevents that. Commit 8 makes sure that, on this path, the page is always there.

Step 14 of 20 · commit 8: Pin the buffer while read, write or wait copy under a spinlock

Pinning a buffer

uvmpin walks the pages of the user buffer. For each one:

• In swap (line 504): let vmfault bring it back (it may sleep, and may evict other pages, even this process’s, but never a pinned one), then look at the same page again.
• In memory and user-accessible (line 513): set PTE_PIN, bit 9. The test and the set are done with interrupts off (line 502), the copyout trick again, so the page cannot be evicted between “it is here” and “it is pinned”.
• Anything else: leave it. A page that does not exist yet (lazy) is allocated by the copy itself, under the lock, from free memory, exactly as in the original kernel; a page without PTE_U, or beyond p->sz, makes the copy fail as it always did.

Only the first case costs anything, and it brings back pages the process had before, which in the original kernel would all have been in memory. So uvmpin never asks for more memory than the program already used. If it cannot bring a page back (memory and swap both exhausted), the pins already set are removed and the call returns -1.

Recorded: pid 4 calls write (a printf from swaptest big) with its buffer on the stack page 0x4000, PTE 0x203d00d7 (V R W U A D) just before the pin. Hart 0, noff 1 (this push_off), intena 1: the system call had interrupts on.

Why pin instead of “bring in and hope”: a pipe reader brings its buffer in, then sleeps in piperead until data arrives, possibly for minutes. Memory pressure meanwhile would evict an unpinned buffer, and the copy that follows, under pi->lock, would need the disk.

Step 15 of 20 · commit 8: Pin the buffer while read, write or wait copy under a spinlock

read, write and wait pin, then unpin

sys_read and sys_write pin [p, p+n) before they call fileread / filewrite, and unpin afterwards, but only when the file is not an inode (FD_INODE): a pipe or a device. readi and writei copy holding sleep-locks only, so their copies may bring a page back from swap themselves, and pinning a whole buffer for them would only waste memory. sys_wait pins the 4-byte status, because kwait copies it out holding wait_lock and the child’s p->lock. Together these cover every copy this kernel makes under a spinlock: piperead, pipewrite, consoleread and kwait.

The design’s test is the probe pinread (measure section): read of the 2,441-byte README into a lazy buffer of 1, 1,000, 34,000 or 100,000 pages returns 2441 every time, as on the original kernel. Pinning the whole buffer, lazy pages included, would have returned -1 for the two big ones.

The state shown is the other end of the story, recorded inside kwait just after its copyout (pp->parent = 0, kernel/proc.c:397 in the branch): pid 3 has waited for pid 4; hart 0, noff 2, intena 1. The status address 0x4f1c is on pid 3’s stack page, whose PTE was 0x21fc72d7: flags 0x2d7, V R W U A D and PTE_PIN. The page had been pinned for the whole time pid 3 slept in wait, while big evicted thousands of pages; in another run gdb caught one of pid 3’s text pages being taken at such a moment (next step).