Extension labs · lab 16 · Memory · ★★★★★

Swapping to disk

In this tree a process can use only as much memory as there are free pages. When kalloc finds its free list empty, sbrk fails and a lazy page fault kills the process. In this lab you make the kernel take a page that some process has not used for a while, write it to a reserved area at the end of the disk, and give its physical page to whoever needs it. When the owner touches that page again, it takes a page fault, and the kernel reads the page back in. The test program writes and checks 36,000 pages on a machine with 32,768 pages of RAM.

Swapping touches more of the kernel than any lab before it, because it moves pages out from under processes that are not expecting it. Where on the disk do the pages go, and through which layer? How does a PTE say “this page is on disk, in slot 2128”? Which page do you pick, and how do you get from a physical page to the PTE that maps it? The page you pick may belong to a process that is running on another hart at that very moment: what does that hart’s TLB (translation lookaside buffer) still believe? Eviction needs the disk, and the disk sleeps: from which of kalloc's many callers is that allowed? The kernel copies into user memory while holding spinlocks: what if the page it copies to is on disk? The think section asks these questions in the order a designer meets them.

The reference solution is twelve commits. It passes usertests -q on three harts, and during that run it writes about 49,000 pages to swap without anyone noticing.

Read first: Tour 10: Exceptions and faults, Tour 16: sleep and wakeup, and the lost-wakeup problem, Tour 17: Sleep-locks, 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, Tour 29: A disk read, end to end · The stacks of xv6, Locks and interrupt state

What this lab teaches

Where evicted pages can live on a disk that already holds a file system, which of the file system’s layers they should go through, and how a whole physical page can reach the disk.
How a PTE with V clear becomes the kernel’s own storage, and which existing code walks user page tables and has to learn what such an entry means.
What the hardware records about the use of a page, how a kernel can turn that into a choice of victim, and how to get from a physical page back to the PTE that maps it.
What a TLB is allowed to remember after a PTE changes, and what that means for which pages may be taken at all.
Which allocation sites may wait for a disk and which may not, and how the ones that may not still find memory when RAM is full.
What a physical address obtained from a PTE is worth once pages can move, and how the kernel’s own copies to and from user memory have to protect themselves.
What fork, exit and exec must do with pages that are not in memory, and how two processes can share one copy on disk.

The reference branch

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

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

1. The spec

Behaviour. When memory runs low, the kernel picks a user page, writes it to a free slot of a swap area on the disk, marks the PTE that mapped it as “in swap, slot s”, and frees the physical page. When the process touches the page again (a load, a store or an instruction fetch), or the kernel copies to or from it for a system call, the page is read back into a free page and mapped again with the same permissions. A program cannot tell, except by the time it takes.

The swap area holds 8,192 slots of one page each (32 MiB), on fs.img. Files must never be given its blocks, and swapping must never disturb files (where it lives, and how it is read and written, is question 1).
fork of a process with pages in swap gives the child the same contents: both processes must see their pages, and neither may see the other’s later writes.
exit, exec and sbrk(-n) give back the slots of the pages they discard. Nothing leaks: free pages plus free slots are the same after a test as before it.
When both memory and swap are full, a process that needs a page is killed (a fault) or gets an error (sbrk, read), as before: the kernel must not panic.
A new system call swapstat(struct swapstat *) reports free pages, slots in use, and the pages written out and read in since boot.

What must not change. Every program behaves as before. usertests -q must print ALL TESTS PASSED on 3 harts, with swapping active: several of its tests use up all of memory on purpose.

The test program, swaptest, prints one line per check (counts vary from run to run; this is the reference branch):

$ swaptest
swaptest: big: wrote 36000 pages: 3710 out, 0 in
swaptest: big: checked 36000 pages, 0 wrong: 32299 out, 32299 in
swaptest: big: OK
swaptest: syscalls: copied 32 pages, 0 wrong; 5 sources and 4 destinations were in swap
swaptest: syscalls: OK
swaptest: fork: 21 slots in use at fork
swaptest: fork: child ok, parent 0 wrong, 26 pages read in
swaptest: fork: OK
swaptest: procs: 15838 out, 13651 in
swaptest: procs: OK
swaptest: free pages + free slots: 40594 before, 40594 after
swaptest: leak: OK
swaptest: 62267 pages written out, 45992 read in
swaptest: ALL OK

big: write 36,000 pages (more than the 32,768 pages of RAM) with a pattern that depends on the page and the word, then check every word of every page, the last page first.
syscalls: the kernel reads from and writes to pages that are in swap: pages go through a pipe, 512 bytes at a time, until write has had to read 4 source pages from swap and read 4 destination pages.
fork: fill 2,000 pages, use enough memory to push some of them out, give that memory back, fork. The child checks every page and overwrites half of them; then the parent checks every page.
procs: three processes of 12,500 pages each, started together, so that they evict each other’s pages. It fails if nothing was written out.
leak: free pages plus free slots, before and after.

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 do evicted pages go, and through which layer?

An evicted page’s 4,096 bytes must be stored off RAM and found again later by a number. The only storage is the disk, which already holds a file system with a log (Tour 31: The log: begin_op, commit and group commit) and a buffer cache (Tour 30: The buffer cache) in front of the driver. Where on the disk do you put swapped pages, and how do you read and write them: as a file, through the log, through the buffer cache, or some other way? Commit to an answer, then check it against what each layer is for.

Check yourself

1warm-upType a number

FSSIZE is 2,000 blocks of 1,024 bytes, and the swap area holds NSWAP = 8,192 slots of one page each, starting at block SWAPSTART = FSSIZE. How many blocks long is fs.img on the reference branch?

decimal, 0x hex or 0b binary

2solidChoose one

A classmate suggests writing evicted pages with bwrite through the buffer cache, “so the driver code stays untouched”. Which is the strongest reason the reference does not?

bwrite would put the page in the log.bwrite cannot write blocks beyond sb.size.To change a block through the cache you must bread it first, which reads from the disk the 4 blocks you are about to overwrite, and the 4 buffers then push useful file-system blocks out of a 30-block cache.The buffer cache cannot be used while memory is short, because bget allocates a page.

2How does a PTE say "this page is in slot 1069"?

After eviction the process must fault on its next access, and the fault handler must find the slot. Where do you keep the slot number? Then list the code that already walks user page tables. What does each one do today with the entry you just designed, and which ones will misbehave?

The reference design

The PTE itself is the natural place: it is exactly what the fault handler looks up. A swapped-out PTE in the reference has:

bits	value
0 (V)	0: the hardware faults on any access and ignores everything else
1–4 (R W X U)	the permissions the page will get back
8 (`PTE_SWAP`, an RSW bit)	1: “this is a page in swap”, as opposed to a zero, lazy PTE
10 and up (the PPN field)	the slot number

Three existing functions read user PTEs and would get it wrong:

uvmunmap skips PTEs without V. Every page in swap at exit, exec or sbrk(-n) would keep its slot forever: swap fills up (clinic 4).
uvmcopy skips them too. The child would have no PTE for the page; its first access would look like a lazy page to vmfault, which hands it a zero-filled page. The child silently reads zeros (clinic 3).
vmfault sees “not mapped, below p->sz” and would also allocate a zero page, losing the data and the slot.

walkaddr needs no change: it returns 0 for a page without V, which already makes copyin and copyout call vmfault. mappages is never asked to map over a swapped PTE: swap-in writes the PTE directly. freewalk runs after uvmunmap has cleared all leaves.

Sharing in fork: the child cannot read the page in to copy it, because kfork holds the child’s np->lock across uvmcopy (no sleeping). So the reference copies the PTE and counts one more reference to the slot. The slot allocator keeps a reference count per slot (uchar ref[NSWAP], under the spinlock slots.lock), and a slot is free when no PTE refers to it. Each process reads its own copy in later.

Check yourself

1solidDecode the bits

On the reference branch, gdb stopped in swapin and printed the PTE of the page being read back: 0x10b516. Decode it.

Value: 0x10b516

V (bit 0)W (bit 2)U (bit 4)bit 8 (PTE_SWAP)the slot number (PTE >> 10)

2solidChoose all that apply

Before any other change, the kernel starts producing swapped-out PTEs (V clear, PTE_SWAP set, slot in the PPN field). Which unchanged functions of this tree then lose data or slots?

3Which page do you take, and how do you find its PTE?

Memory is full and you need one page. You would like one that has not been used for a while. What does the hardware tell you about use? And once you have chosen a physical page, how do you find the PTE that maps it, so that you can change it?

Check yourself

1solidTrue or false, and why

True or false: with the clock algorithm, a page whose PTE has A set when the hand reaches it can never be evicted.

TrueFalse

Why?

A is ignored; only D (dirty) matters for eviction.The hardware clears A after a while, so the page becomes evictable on its own.The hand clears A and moves on; if the page is not used again before the hand comes back, A is still clear then and the page is taken.

2deepChoose one

A classmate’s clock holds ft.lock while it takes the owner’s p->lock: acquire(&ft.lock); p = ft.f[i].proc; acquire(&p->lock); .... Meanwhile, on another hart, the shell runs kwait and frees a zombie, the same p, holding its p->lock. What can happen?

acquire panics because p->lock is held by another hart.A deadlock: the clock holds ft.lock and waits for p->lock, while freeproc → uvmunmap holds p->lock and waits for ft.lock to clear the frame-table entry.The zombie’s page is evicted after it was freed.Nothing: spinlocks cannot deadlock, they only spin.

4Whose pages may you take?

The hand reaches a page of hog, which is running in user mode on hart 2 at this very moment. You clear V in its PTE, write the page to slot s, and put the physical page on the free list, where someone else gets it. What does hart 2 do on hog’s next store to that page? Which processes’ pages is it safe to take, and why?

The reference design

Hart 2 may not even look at the PTE. Its TLB can still hold the old translation va → old page, writable, and RISC-V lets it keep using that entry until hart 2 itself executes sfence.vma. hog’s store lands in a page that is now free, or already someone else’s: the other process’s data is corrupted, and hog’s write is lost, because the copy on disk was taken before it. Nothing faults, nothing panics.

Hart 0 cannot fix this by flushing: sfence.vma only affects the TLB of the hart that executes it. Real kernels send an interprocessor interrupt (a “TLB shootdown”) and wait for every hart that may cache the translation to flush. This kernel has no such mechanism, so the reference designs around it:

A process that is SLEEPING or RUNNABLE entered the kernel through uservec, which switched to the kernel page table and executed sfence.vma (kernel/trampoline.S:89–kernel/trampoline.S:95). No hart holds its user translations. It cannot run again while the evicting hart holds its p->lock, because scheduler needs that lock to switch to it; and when it does run, its next return to user mode goes through userret, which flushes again.
The evicting process itself is in the kernel, on the kernel page table; its return to user mode flushes in userret.
A process that is RUNNING on another hart is never touched, whether it is in user mode (the TLB problem) or in the kernel (it may be in the middle of using a physical address it got from its page table: a later question).

The same rule covers clearing A: the clock only clears A in PTEs of processes that hold no translation in any TLB, so the next access really walks the table and sets A again.

Observed. In clinic 1 the state check is replaced by “any live process”. A gdb breakpoint caught that kernel evicting pages of a process that was running on another hart (that hart’s pc was 0x11e, user code; 22 such evictions in two runs). swaptest still passed every time: the damage needs the victim to use the page again through its stale entry before its next trap flushes it (at most one timer tick, 0.1 s), and the test’s processes do not revisit a page that soon. A race no test caught is exactly why this rule must come from reasoning, not from testing.

Check yourself

1solidChoose one

Hart 0 evicts a page of process P, which is RUNNING in user mode on hart 2, and executes sfence.vma right after changing P’s PTE. Is P now safe?

No, but only because hart 0 should have used sfence.vma with P’s address instead of zero, zero.Yes: sfence.vma flushes the TLBs of all harts.No: sfence.vma only flushes hart 0’s TLB; hart 2 may still use its cached translation.Yes: hart 2 rereads the PTE on every access.

2deepChoose all that apply

The clock reaches a page of process P while holding P’s p->lock. For which states of P may it evict the page?

5Where may eviction run?

The obvious place to evict is kalloc: when the free list is empty, write some page out and return its frame. List kalloc's callers and what each one holds when it calls. What does an eviction have to do that some of them cannot allow? And if kalloc does not evict, how do those callers still find memory when user pages fill RAM?

Check yourself

1solidFill in the machine state

swaptest (pid 3) forks while one of its pages is in swap. Fill in the state of the hart at the moment uvmcopy copies the swapped-out PTE into the child’s page table.

kernel/proc.c

258int
259kfork(void)
260{
int i, pid;
struct proc *np;
struct proc *p = myproc();
264
// Allocate process.
if ((np = allocproc()) == 0) {
  return -1;
}
269
// Copy user memory from parent to child.
if (uvmcopy(p->pagetable, np->pagetable, p->sz) < 0) {
  freeproc(np);
  release(&np->lock);
  return -1;
}
np->sz = p->sz;

Privilege modeActive stackInterrupts (sstatus.SIE)noffintena

2solidChoose all that apply

Which callers may use ualloc (which can evict, and so sleep) instead of kalloc?

6The kernel's own copies

copyout already calls vmfault when walkaddr returns 0, so a read into a buffer that is in swap will bring it back from inside copyout. On which paths does copyout (or copyin) run with a spinlock held, and what happens if the page is in swap there? Then a quieter problem: copyout gets a physical address from the PTE, then copies to it. What can happen between those two steps now that pages move, even when no lock is held?

The reference design

Copies under a spinlock. Four paths copy while holding a spinlock: piperead and pipewrite (pi->lock), consoleread (cons.lock) and kwait (wait_lock and the child’s p->lock). If the page is in swap there, vmfault reads it back and sleeps for the disk with the spinlock held: panic: sched locks. Clinic 2 shows exactly that, from swaptest syscalls.

They are reached through three system calls: read and write on a pipe or the console, and wait. Before the copy starts, the reference goes through the user buffer once (uvmpin): a page that is in swap is read back in, and every page that is in memory gets PTE_PIN (bit 9, the other RSW bit), which the clock respects; uvmunpin clears the bits when the call returns. A pipe reader may sleep for minutes between the two; the pin is what keeps its buffer in memory all that time.

What the pin leaves alone matters as much:

Files. readi and writei copy holding only sleep-locks, so a page that is missing there may be read back in during the copy. read and write on a file pin nothing.
Pages that do not exist yet. A lazy page of the buffer is left to the copy, which allocates it as the original kernel did, under the spinlock, with whatever memory is free (ualloc does not evict when its caller holds a spinlock). The pin brings back only pages the process has used before, which in the original kernel would all have been in memory anyway.
Pages beyond p->sz, and pages without PTE_U: the copy fails there, as before.

So every program sees what it saw before. A probe program, pinread, reads the 2,441-byte README into a lazy buffer of 1, 1,000, 34,000 and 100,000 pages: the original kernel and the reference both return 2441 every time (pinread in the measure section).

Two simpler designs fail. Pinning the whole process during these calls leaves a process that is the only big one with nothing it may evict to make room for its own buffer: with that design swaptest syscalls hung, QEMU idle (reasoned from the code, not traced: a write failed for lack of memory and the test then waited on a read forever). Pinning and faulting in the whole buffer, lazy pages included, for every read and write changes what programs see: reading README into a 34,000-page lazy buffer returned -1 instead of 2441, because 34,000 pinned pages are more than memory and swap can hold. A pin is a promise of memory; promise only what the copy will need.

Between translation and copy. copyout does pa0 = walkaddr(...), then memmove(pa0 + ...). With interrupts on, a timer interrupt can arrive in between and yield: the process is RUNNABLE, the clock on another hart may evict that very page, and someone else may get the physical page before memmove writes into it. The reference keeps interrupts off (push_off) from walkaddr to the end of memmove in copyin, copyout and copyinstr: the process stays RUNNING on this hart, and RUNNING pages are not taken. vmfault may sleep, so it is called with interrupts on, and the loop then translates again. uvmpin uses the same trick between “this page is in memory” and setting PTE_PIN.

The general rule this lab teaches: a physical address read from a user PTE is only good while nothing can evict that page, either because the process cannot stop running (interrupts off), or because the page is pinned.

Check yourself

1solidChoose one

The reference without the pin in sys_write (clinic 2). swaptest syscalls writes 512 bytes from a page that is in swap to a pipe. What happens?

It works, only more slowly, because sleep releases pi->lockpanic: sched locks, from pipewrite → copyin → vmfault → swapin → … → sleep with pi->lock heldA deadlock: the process waits for pi->lock, which it holdswrite returns -1, because copyin refuses pages that are in swap

2deepFill in the machine state

On the reference branch, swaptest writes to a pipe from a buffer that sys_write has pinned. Fill in the hart’s state while copyin runs its memmove inside pipewrite.

kernel/pipe.c

76int
77pipewrite(struct pipe *pi, uint64 addr, int n)
78{
int i = 0;
struct proc *pr = myproc();
81
acquire(&pi->lock);
while (i < n) {
  if (pi->readopen == 0 || killed(pr)) {
    release(&pi->lock);
    return -1;
  }
  if (pi->nwrite == pi->nread + PIPESIZE) { //DOC: pipewrite-full
    wakeup(&pi->nread);
    sleep_prepare(&pi->nwrite);
    release(&pi->lock);
    sleep();
    acquire(&pi->lock);
  } else {
    char ch;
    if (copyin(pr->pagetable, pr->sz, &ch, addr + i, 1) == -1) {
      if (i == 0)
        i = -1;
      break;
    }
    pi->data[pi->nwrite++ % PIPESIZE] = ch;
    i++;
  }
}
wakeup(&pi->nread);
release(&pi->lock);
107
return i;

Privilege modePage table (satp)Interrupts (sstatus.SIE)noffintena

7fork, exit, exec, and a page still on its way out

Go through the rest of a process’s life with pages in swap. What must fork give the child for a swapped-out page, and who frees the slot in the end? What must exit, exec and sbrk(-n) do? kexec builds the new image in a new page table while the old one is still p->pagetable, and loadseg sleeps in readi with a physical page of the new image in hand: could the clock take that page? Last: the clock has just marked a page “in slot s” and started writing it out, and its owner wakes up and touches it. What does the owner read?

Check yourself

1solidType a number

A process has one page in slot 7. It forks twice; then the first child exits; then the parent touches the page (reading it back in). What is slots.ref[7] now?

decimal, 0x hex or 0b binary

2deepPut in order

Put the steps of one eviction by evict in the order the reference performs them.

write the page to the slot
kfree the physical page
releasesleep(&swapio.lock)
allocate a free slot
the clock picks a victim and rewrites its PTE to “in swap, slot s”
acquiresleep(&swapio.lock)

3. Build it

Start.

git checkout -b my-swap 06aad25

Write the test first: copy the spec’s checks into user/swaptest.c and add $U/_swaptest\ to UPROGS. You will need a way to see what the kernel does: add the swapstat system call early (milestone 1), even though its counters stay at zero until the end. Until eviction exists, swaptest big must be killed (usertrap(): unexpected scause 0xf) once its pages outnumber the free ones: that is the test working.

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

The swap area and the disk. NSWAP and SWAPSTART in param.h; mkfs writes the last block of the swap area so that fs.img grows by 32 MiB (check with ls -l fs.img: 35,602,432 bytes). Split virtio_disk_rw so that a page-sized request can be made. Test: boot, usertests -q. A quick self-test helps: at boot, write a page with a pattern to slot 0, read it into another page, compare, print one line, then remove it.
Slots and the frame table. A slot allocator with reference counts; one frame-table entry per physical page, set wherever a fresh user page is mapped and cleared where uvmunmap frees it. Nothing uses them yet. Test: usertests -q.
The swapped-out PTE. The bits in riscv.h; uvmunmap frees the slot; uvmcopy shares it. Still nothing creates such a PTE. Test: it compiles, usertests -q.
Swap-in. vmfault recognises the PTE and reads the page back; usertrap also sends instruction faults (scause 12) there, and saves scause and stval before anything can sleep. Test: usertests -q.
Protect the kernel’s copies. Interrupts off between translation and copy in copyin, copyout and copyinstr; pin the buffer in read, write and wait. Test: usertests -q.
Eviction. The clock, evict, and an allocator for user pages that evicts when memory is low, used by uvmalloc, vmfault and swap-in. This switches swapping on. Test: swaptest, then usertests -q, then swaptest again.

Debugging advice. make qemu-gdb starts QEMU halted and waiting for gdb (its port is written to .gdbinit); in another terminal, run ${TOOLPREFIX}gdb kernel/kernel and continue. 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.

Do not call myproc() or mycpu() from gdb while the kernel is stopped: myproc() does a push_off/pop_off, and the pop_off can turn interrupts on in the stopped context. Read cpus[$tp].proc, cpus[$tp].noff and cpus[$tp].intena instead (tp holds the hart number in the kernel).
A breakpoint on the line of the clock that rewrites the PTE, with p/x *pte and p p->state, shows every victim; a condition such as if p != me picks out evictions of other processes’ pages. Conditions are evaluated with QEMU stopped, so expect the run to slow down until the breakpoint is disabled.
panic: sched locks means something slept with a spinlock held: break panic, then bt. The frames between the lock holder and sleep tell you which path needs a pin or must not evict.
A process killed with unexpected scause 0xf or 0xd at an address it owns, while swap is not full, means eviction found no victim: print the free-page count and slots.nused, and check that the clock clears A.
Wrong data with no crash: make the test print the first wrong word and its page. A wrong word at a fixed offset in every bad page (word 128, for instance) points at the size of the disk transfer; zeros point at a PTE the kernel lost (fork, or a lazy page mapped over a swapped one).
swaptest takes about a minute, usertests -q about one and a half: slower than on the original kernel, because several of its tests fill memory, and now fill swap too. (Timings on QEMU depend on your computer and on what else it is doing.)

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.

1Taking pages from a process that is running on another hart

The clock’s test on the owner’s state is “any live process” instead of “not running, or myself”:

-  struct proc *me = myproc();
...
-    if (p->state == SLEEPING || p->state == RUNNABLE || p == me) {
+    if (p->state != USED && p->state != ZOMBIE) {

What happened when we ran it

$ swaptest
[...]
swaptest: procs: 17135 out, 14004 in
swaptest: procs: OK
swaptest: free pages + free slots: 40594 before, 40594 after
swaptest: leak: OK
swaptest: 63564 pages written out, 46345 read in
swaptest: ALL OK
[...]

# another boot, gdb: break swap.c:175 if p->state == RUNNING && p != cpus[$tp].proc
[...]
=== EVICT RUNNING
$91 = (void *) 0x0
$92 = 11
$93 = 10
$94 = "swaptest\000\000\000\000\000\000\000"
$95 = <optimized out>
$96 = 0x2132a497
  Id   Target Id                    Frame 
* 1    Thread 1.1 (CPU#0 [running]) clock (s=<optimized out>) at kernel/swap.c:175
  2    Thread 1.2 (CPU#1 [halted ]) s_sstatus (x=2) at kernel/riscv.h:67
  3    Thread 1.3 (CPU#2 [running]) 0x000000000000011e in ?? ()
[...]

Honest summary first: we never saw this bug break anything. Three runs of swaptest in one boot printed ALL OK (the end of the first is shown; the other two are elided at [...]), and so did two more runs in another boot with gdb attached, which caught 22 such evictions. What gdb did show is the bug happening: in the record above (the 16th of the 22), hart 0 ($91), running for pid 11 ($92), is about to evict a page of pid 10 ($93). Pid 10 is RUNNING, and the only other hart that is running is hart 2, at pc 0x11e, a user address (inside swaptest’s check loop): pid 10 is executing user code at that moment. $96 is the PTE just before the rewrite: physical page 0x84ca9000, flags 0x97 (V, R, W, U and D; A is clear, which is why the clock chose it). All 22 evictions were in the procs test (pids 9 to 11 in the first run, 18 to 20 in the second), where three processes run on three harts and evict each other’s pages.

Why it did no visible harm here: for damage, pid 10 has to touch the page again through the stale translation in hart 2’s TLB, before hart 2 flushes it. Hart 2 flushes on every trap from user mode (uservec), and the timer alone causes one every 0.1 s. swaptest’s processes walk their pages in order and do not come back to a page that soon. A program that keeps a small working set hot (a hash table, a stack) would: its stores would land in a page already freed and perhaps handed to another process, and its copy on disk would miss them. No fault, no panic, two processes’ memory silently wrong.

This bug has a second, quieter side: a RUNNING process may be inside the kernel with a physical address of its own page in hand, between walkaddr and memmove in copyout, or in the middle of uvmcopy reading the parent’s pages. The push_off there keeps its own hart from switching away, but does nothing against another hart that ignores the RUNNING state.

The lesson is the one the think section argues: TLB rules have to come from reasoning about which hart may hold which translation. A test passing three times proves only that the window was not hit.

2write does not pin its buffer

The pin is left out of sys_write (read and wait keep theirs):

-  // as in sys_read: pipewrite copies in holding a spinlock.
-  pin = n > 0 && f->type != FD_INODE;
-  if (pin && uvmpin(p, n) < 0)
-    return -1;
   r = filewrite(f, p, n);
-  if (pin)
-    uvmunpin(p, n);
   return r;

What happened when we ran it

$ swaptest
swaptest: big: wrote 36000 pages: 3710 out, 0 in
swaptest: big: checked 36000 pages, 0 wrong: 32299 out, 32299 in
swaptest: big: OK
panic: sched locks

# gdb, another boot, break panic:
[...]
$1 = (void *) 0x0
$2 = 2
$3 = 1
$4 = 5
$5 = "swaptest\000\000\000\000\000\000\000"
#0  panic (s=s@entry=0x800081a8 "sched locks") at kernel/printk.c:139
#1  0x0000000080002118 in sched () at kernel/proc.c:488
#2  0x00000000800021b8 in sleep () at kernel/proc.c:569
#3  0x0000000080005be2 in disk_rw (b=b@entry=0x80021c18 <swapio+48>, sector=sector@entry=7536, data=data@entry=0x800c2000 [...]
#4  0x0000000080005e60 in virtio_disk_rwpage (b=b@entry=0x80021c18 <swapio+48>, blockno=blockno@entry=3768, pa=pa@entry=0x800c2000, write=write@entry=0) at kernel/virtio_disk.c:312
#5  0x0000000080005f4e in swaprw (s=s@entry=442, pa=pa@entry=0x800c2000, write=write@entry=0) at kernel/swap.c:132
#6  0x00000000800063f4 in swapin (pagetable=pagetable@entry=0x87f43000, va=va@entry=45056) at kernel/swap.c:252
#7  0x000000008000163e in vmfault (pagetable=pagetable@entry=0x87f43000, psz=psz@entry=147476480, va=va@entry=45056, read=read@entry=1) at kernel/vm.c:551
#8  0x00000000800017e8 in copyin (pagetable=0x87f43000, psz=147476480, dst=dst@entry=0x3fffff7ebf "", srcva=srcva@entry=45056, len=len@entry=1) at kernel/vm.c:419
#9  0x0000000080004926 in pipewrite (pi=0x81d1a000, addr=45056, n=512) at kernel/pipe.c:96
#10 0x0000000080004666 in filewrite (f=0x80020b58 <ftable+104>, addr=45056, n=512) at kernel/file.c:143
#11 0x0000000080005120 in sys_write () at kernel/sysfile.c:102
#12 0x0000000080002b36 in syscall () at kernel/syscall.c:148
#13 0x00000000800028bc in usertrap () at kernel/trap.c:73
#14 0x0000003ffffff09c in ?? ()

3fork forgets pages that are in swap

uvmcopy has no case for a swapped-out PTE, so it does what the original code does with any PTE without V: skips it.

-  pte_t *pte, *npte;
+  pte_t *pte;
...
-    if (*pte & PTE_SWAP) {
-      // the child shares the slot; each process will read
-      // its own copy in when it uses the page.
-      if ((npte = walk(new, i, 1)) == 0)
-        goto err;
-      *npte = *pte;
-      swapdup(PTE2SLOT(*pte));
-      continue;
-    }
     if ((*pte & PTE_V) == 0)
       continue; // physical page hasn't been allocated

What happened when we ran it

$ swaptest
swaptest: big: wrote 36000 pages: 3710 out, 0 in
swaptest: big: checked 36000 pages, 0 wrong: 32299 out, 32299 in
swaptest: big: OK
swaptest: syscalls: copied 0 pages, 0 wrong; 0 sources and 0 destinations were in swap
swaptest: syscalls: FAIL
swaptest: fork: 1958 slots in use at fork
swaptest: page 7 word 0 is 0
swaptest: page 8 word 0 is 0
swaptest: page 9 word 0 is 0
swaptest: fork: child FAILED, parent 0 wrong, 1950 pages read in
swaptest: fork: FAIL
swaptest: procs: 17503 out, 17502 in
swaptest: procs: OK
swaptest: free pages + free slots: 40594 before, 40594 after
swaptest: leak: OK
swaptest: 60220 pages written out, 51754 read in
swaptest: SOME TESTS FAILED

4Slots are not freed when a process lets go of its pages

uvmunmap keeps skipping PTEs without V, as in the original tree, so a page in swap keeps its slot forever when a process exits, execs, or shrinks:

-    if (*pte & PTE_SWAP) { // the page is in swap, not in memory
-      if (do_free)
-        swapfree(PTE2SLOT(*pte));
-      *pte = 0;
-      continue;
-    }
     if ((*pte & PTE_V) == 0) // has physical page been allocated?
       continue;

What happened when we ran it

$ swaptest
swaptest: big: wrote 36000 pages: 3710 out, 0 in
swaptest: big: checked 36000 pages, 0 wrong: 32299 out, 32299 in
swaptest: big: OK
swaptest: syscalls: copied 32 pages, 0 wrong; 5 sources and 4 destinations were in swap
swaptest: syscalls: OK
usertrap(): unexpected scause 0xf pid=6
            sepc=0x476 stval=0x8162000
swaptest: fork: FAIL
usertrap(): unexpected scause 0xf pid=9
            sepc=0x7c stval=0x2833000
usertrap(): unexpected scause 0xf pid=10
            sepc=0x7c stval=0x2535000
swaptest: procs: 0 out, 0 in
swaptest: procs: FAIL
swaptest: free pages + free slots: 40594 before, 32410 after
swaptest: leak: FAIL
swaptest: 40503 pages written out, 32312 read in
swaptest: SOME TESTS FAILED
$ swaptest
usertrap(): unexpected scause 0xf pid=12
            sepc=0x7c stval=0x7e54000
swaptest: big: FAIL
[...]
swaptest: free pages + free slots: 32409 before, 32408 after
swaptest: leak: FAIL
swaptest: 5 pages written out, 2 read in
swaptest: SOME TESTS FAILED

5The second chance does not clear A

The clock tests A but forgets to clear it:

         if (*pte & PTE_A) {
-          *pte &= ~PTE_A; // second chance
+          ; // second chance
         } else {

What happened when we ran it

$ swaptest
usertrap(): unexpected scause 0xf pid=4
            sepc=0x7c stval=0x7e52000
swaptest: big: FAIL
usertrap(): unexpected scause 0xf pid=5
            sepc=0x7c stval=0x7e50000
swaptest: syscalls: FAIL
usertrap(): unexpected scause 0xf pid=6
            sepc=0x476 stval=0x7e51000
swaptest: fork: FAIL
usertrap(): unexpected scause 0xf pid=10
            sepc=0x7c stval=0x1c8a000
swaptest: procs: 0 out, 0 in
swaptest: procs: FAIL
swaptest: free pages + free slots: 40594 before, 40594 after
swaptest: leak: OK
swaptest: 5 pages written out, 2 read in
swaptest: SOME TESTS FAILED

6The page request moves one block instead of a page

The length of the page-sized request in the driver is left at BSIZE, copied from virtio_disk_rw:

 virtio_disk_rwpage(struct buf *b, uint blockno, void *pa, int write)
 {
-  disk_rw(b, (uint64)blockno * (BSIZE / 512), (char *)pa, PGSIZE, write);
+  disk_rw(b, (uint64)blockno * (BSIZE / 512), (char *)pa, BSIZE, write);
 }

What happened when we ran it

$ swaptest
swaptest: big: wrote ^E^E^E^E^E pages: ^E^E^E^E out, ^E in
swaptest: page ^E^E^E^E^E word ^E^E^E is ^E^E^E^E^E^E^E^E^E^E^E^E^E^E^E
swaptest: page ^E^E^E^E^E word ^E^E^E is ^E^E^E^E^E^E^E^E^E^E^E^E^E^E^E
swaptest: page ^E^E^E^E^E word ^E^E^E is ^E^E^E^E^E^E^E^E^E^E^E^E^E^E^E
usertrap(): unexpected scause 0xc pid=4
            sepc=0x505050505050504 stval=0x505050505050504
usertrap(): unexpected scause 0xf pid=3
            sepc=0x1010 stval=0x1

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

3fe676b Reserve a swap area at the end of the disk
kernel/param.h
@@ -9,6 +9,8 @@
99#define MAXOPBLOCKS 10 // max # of blocks any FS op writes
1010#define LOGBLOCKS (MAXOPBLOCKS * 3) // max data blocks in on-disk log
1111#define NBUF (MAXOPBLOCKS * 3) // size of disk block cache
1212#define FSSIZE 2000 // size of file system in blocks
13#define NSWAP 8192 // swap slots (pages) after the file system
14#define SWAPSTART FSSIZE // first block of the swap area
1315#define MAXPATH 128 // maximum file path name
1416#define USERSTACK 1 // user stack pages
mkfs/mkfs.c
@@ -23,8 +23,9 @@
2323#define NINODES 200
2424
2525// Disk layout:
2626// [ boot block | sb block | log | inode blocks | free bit map | data blocks ]
27// followed by the swap area, NSWAP pages that the file system never uses.
2728
2829int nbitmap = FSSIZE / BPB + 1;
2930int ninodeblocks = NINODES / IPB + 1;
3031int nlog = LOGBLOCKS + 1; // Header followed by LOGBLOCKS data blocks.
@@ -113,8 +114,13 @@ main(int argc, char *argv[])
113114
114115 for (i = 0; i < FSSIZE; i++)
115116 wsect(i, zeroes);
116117
118 // make room for the swap area after the file system: NSWAP
119 // slots of one page (4096 bytes) each. sb.size stays FSSIZE,
120 // so the file system never allocates these blocks.
121 wsect(SWAPSTART + NSWAP * (4096 / BSIZE) - 1, zeroes);
122
117123 memset(buf, 0, sizeof(buf));
118124 memmove(buf, &sb, sizeof(sb));
119125 wsect(1, buf);
120126
dfebd4d Let the disk driver transfer a whole page
kernel/defs.h
@@ -179,8 +179,9 @@ void plic_complete(int);
179179
180180// virtio_disk.c
181181void virtio_disk_init(void);
182182void virtio_disk_rw(struct buf *, int);
183void virtio_disk_rwpage(struct buf *, uint, void *, int);
183184void virtio_disk_intr(void);
184185
185186// number of elements in fixed-size array
186187#define NELEM(x) (sizeof(x) / sizeof((x)[0]))
kernel/virtio_disk.c
@@ -211,13 +211,13 @@ alloc3_desc(int *idx)
211211 }
212212 return 0;
213213}
214214
215void
216virtio_disk_rw(struct buf *b, int write)
215// transfer len bytes between data and the disk, starting at
216// sector. the caller sleeps on b until the transfer is done.
217static void
218disk_rw(struct buf *b, uint64 sector, char *data, uint len, int write)
217219{
218 uint64 sector = b->blockno * (BSIZE / 512);
219
220220 acquire(&disk.vdisk_lock);
221221
222222 // the spec's Section 5.2 says that legacy block operations use
223223 // three descriptors: one for type/reserved/sector, one for the
@@ -251,10 +251,10 @@ virtio_disk_rw(struct buf *b, int write)
251251 disk.desc[idx[0]].len = sizeof(struct virtio_blk_req);
252252 disk.desc[idx[0]].flags = VRING_DESC_F_NEXT;
253253 disk.desc[idx[0]].next = idx[1];
254254
255 disk.desc[idx[1]].addr = (uint64)b->data;
256 disk.desc[idx[1]].len = BSIZE;
255 disk.desc[idx[1]].addr = (uint64)data;
256 disk.desc[idx[1]].len = len;
257257 if (write)
258258 disk.desc[idx[1]].flags = 0; // device reads b->data
259259 else
260260 disk.desc[idx[1]].flags = VRING_DESC_F_WRITE; // device writes b->data
@@ -296,8 +296,23 @@ virtio_disk_rw(struct buf *b, int write)
296296
297297 release(&disk.vdisk_lock);
298298}
299299
300void
301virtio_disk_rw(struct buf *b, int write)
302{
303 disk_rw(b, b->blockno * (BSIZE / 512), (char *)b->data, BSIZE, write);
304}
305
306// read or write the page at physical address pa, as PGSIZE / BSIZE
307// blocks starting at blockno, in one request. used for swapping;
308// b only serves to wait for the request (b->data is not used).
309void
310virtio_disk_rwpage(struct buf *b, uint blockno, void *pa, int write)
311{
312 disk_rw(b, (uint64)blockno * (BSIZE / 512), (char *)pa, PGSIZE, write);
313}
314
300315void
301316virtio_disk_intr()
302317{
303318 acquire(&disk.vdisk_lock);
4e715cb Add swap slots
Makefile
@@ -27,9 +27,10 @@ OBJS = \
2727 $K/exec.o \
2828 $K/sysfile.o \
2929 $K/kernelvec.o \
3030 $K/plic.o \
31 $K/virtio_disk.o
31 $K/virtio_disk.o \
32 $K/swap.o
3233
3334# riscv64-unknown-elf- or riscv64-linux-gnu-
3435# perhaps in /opt/riscv/bin
3536#TOOLPREFIX =
kernel/defs.h
@@ -106,8 +106,14 @@ void procdump(void);
106106
107107// swtch.S
108108void swtch(struct context*, struct context*);
109109
110// swap.c
111void swapinit(void);
112int swapalloc(void);
113void swapdup(int);
114void swapfree(int);
115
110116// spinlock.c
111117void acquire(struct spinlock*);
112118int holding(struct spinlock*);
113119void initlock(struct spinlock*, char*);
kernel/main.c
@@ -27,8 +27,9 @@ main()
2727 binit(); // buffer cache
2828 iinit(); // inode table
2929 fileinit(); // file table
3030 virtio_disk_init(); // emulated hard disk
31 swapinit(); // swap slots
3132 userinit(); // first user process
3233
3334 __atomic_store_n(&started, 1, __ATOMIC_RELEASE);
3435 } else {
kernel/swap.c
@@ -0,0 +1,70 @@
1// Swapping: user pages written out to the swap area at the end
2// of the disk, and read back in when they are used again.
3
4#include "types.h"
5#include "param.h"
6#include "memlayout.h"
7#include "riscv.h"
8#include "spinlock.h"
9#include "sleeplock.h"
10#include "fs.h"
11#include "buf.h"
12#include "proc.h"
13#include "defs.h"
14
15// a slot holds one page: PGSIZE / BSIZE blocks of the swap area.
16#define SLOTBLOCK(s) (SWAPSTART + (s) * (PGSIZE / BSIZE))
17
18// the swap slots. a slot is free when no PTE refers to it;
19// after fork, a parent and a child can both refer to one.
20struct {
21 struct spinlock lock;
22 uchar ref[NSWAP]; // number of PTEs that hold each slot
23 int nused; // slots with ref > 0
24} slots;
25
26void
27swapinit(void)
28{
29 initlock(&slots.lock, "slots");
30}
31
32// allocate a free slot. returns -1 if the swap area is full.
33int
34swapalloc(void)
35{
36 acquire(&slots.lock);
37 for (int s = 0; s < NSWAP; s++) {
38 if (slots.ref[s] == 0) {
39 slots.ref[s] = 1;
40 slots.nused++;
41 release(&slots.lock);
42 return s;
43 }
44 }
45 release(&slots.lock);
46 return -1;
47}
48
49// one more PTE refers to slot s (fork copied a swapped-out PTE).
50void
51swapdup(int s)
52{
53 acquire(&slots.lock);
54 if (slots.ref[s] < 1 || slots.ref[s] == 255)
55 panic("swapdup");
56 slots.ref[s]++;
57 release(&slots.lock);
58}
59
60// a PTE no longer refers to slot s.
61void
62swapfree(int s)
63{
64 acquire(&slots.lock);
65 if (slots.ref[s] < 1)
66 panic("swapfree");
67 if (--slots.ref[s] == 0)
68 slots.nused--;
69 release(&slots.lock);
70}
de89af9 Keep a frame table: which process maps each user page
kernel/defs.h
@@ -111,8 +111,10 @@ void swtch(struct context*, struct context*);
111111void swapinit(void);
112112int swapalloc(void);
113113void swapdup(int);
114114void swapfree(int);
115void ftset(void *, struct proc *, uint64);
116void ftclear(void *);
115117
116118// spinlock.c
117119void acquire(struct spinlock*);
118120int holding(struct spinlock*);
@@ -164,9 +166,9 @@ void kvmmap(pagetable_t, uint64, uint64, uint64, int);
164166int mappages(pagetable_t, uint64, uint64, uint64, int);
165167pagetable_t uvmcreate(void);
166168uint64 uvmalloc(pagetable_t, uint64, uint64, int);
167169uint64 uvmdealloc(pagetable_t, uint64, uint64);
168int uvmcopy(pagetable_t, pagetable_t, uint64);
170int uvmcopy(pagetable_t, pagetable_t, uint64, struct proc *);
169171void uvmfree(pagetable_t, uint64);
170172void uvmunmap(pagetable_t, uint64, uint64, int);
171173void uvmclear(pagetable_t, uint64);
172174pte_t * walk(pagetable_t, uint64, int);
kernel/proc.c
@@ -267,9 +267,9 @@ kfork(void)
267267 return -1;
268268 }
269269
270270 // Copy user memory from parent to child.
271 if (uvmcopy(p->pagetable, np->pagetable, p->sz) < 0) {
271 if (uvmcopy(p->pagetable, np->pagetable, p->sz, np) < 0) {
272272 freeproc(np);
273273 release(&np->lock);
274274 return -1;
275275 }
kernel/swap.c
@@ -22,12 +22,47 @@ struct {
2222 uchar ref[NSWAP]; // number of PTEs that hold each slot
2323 int nused; // slots with ref > 0
2424} slots;
2525
26// the frame table: for every physical page that is mapped as a
27// user page, the process and the virtual address that map it.
28// eviction needs this reverse map to find the PTE of a page.
29#define NFRAME ((PHYSTOP - KERNBASE) / PGSIZE)
30#define FRAME(pa) (((uint64)(pa) - KERNBASE) / PGSIZE)
31#define FRAMEPA(i) (KERNBASE + (uint64)(i) * PGSIZE)
32
33struct {
34 struct spinlock lock;
35 struct frame {
36 struct proc *proc; // 0 if not a user page
37 uint64 va;
38 } f[NFRAME];
39} ft;
40
2641void
2742swapinit(void)
2843{
2944 initlock(&slots.lock, "slots");
45 initlock(&ft.lock, "ftable");
46}
47
48// record that p maps the user page pa at va.
49void
50ftset(void *pa, struct proc *p, uint64 va)
51{
52 acquire(&ft.lock);
53 ft.f[FRAME(pa)].proc = p;
54 ft.f[FRAME(pa)].va = va;
55 release(&ft.lock);
56}
57
58// pa is no longer mapped as a user page.
59void
60ftclear(void *pa)
61{
62 acquire(&ft.lock);
63 ft.f[FRAME(pa)].proc = 0;
64 release(&ft.lock);
3065}
3166
3267// allocate a free slot. returns -1 if the swap area is full.
3368int
kernel/vm.c
@@ -205,8 +205,9 @@ uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free)
205205 if ((*pte & PTE_V) == 0) // has physical page been allocated?
206206 continue;
207207 if (do_free) {
208208 uint64 pa = PTE2PA(*pte);
209 ftclear((void *)pa);
209210 kfree((void *)pa);
210211 }
211212 *pte = 0;
212213 }
@@ -236,8 +237,9 @@ uvmalloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz, int xperm)
236237 kfree(mem);
237238 uvmdealloc(pagetable, a, oldsz);
238239 return 0;
239240 }
241 ftset(mem, myproc(), a);
240242 }
241243 return newsz;
242244}
243245
@@ -291,13 +293,13 @@ uvmfree(pagetable_t pagetable, uint64 sz)
291293
292294// Given a parent process's page table, copy
293295// its memory into a child's page table.
294296// Copies both the page table and the
295// physical memory.
297// physical memory. np is the child, for the frame table.
296298// returns 0 on success, -1 on failure.
297299// frees any allocated pages on failure.
298300int
299uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
301uvmcopy(pagetable_t old, pagetable_t new, uint64 sz, struct proc *np)
300302{
301303 pte_t *pte;
302304 uint64 pa, i;
303305 uint flags;
@@ -316,8 +318,9 @@ uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
316318 if (mappages(new, i, PGSIZE, (uint64)mem, flags) != 0) {
317319 kfree(mem);
318320 goto err;
319321 }
322 ftset(mem, np, i);
320323 }
321324 return 0;
322325
323326err:
@@ -473,8 +476,9 @@ vmfault(pagetable_t pagetable, uint64 psz, uint64 va, int read)
473476 if (mappages(pagetable, va, PGSIZE, mem, PTE_W | PTE_U | PTE_R) != 0) {
474477 kfree((void *)mem);
475478 return 0;
476479 }
480 ftset((void *)mem, myproc(), va);
477481 return mem;
478482}
479483
480484int
3534991 Mark swapped-out PTEs, free their slots, share them on fork
kernel/riscv.h
@@ -397,8 +397,16 @@ typedef uint64 *pagetable_t; // 512 PTEs
397397#define PTE_W (1L << 2)
398398#define PTE_X (1L << 3)
399399#define PTE_U (1L << 4) // user can access
400400
401// a PTE with V clear is ignored by the hardware, so its other bits
402// are free for the kernel. PTE_SWAP (bit 8, an RSW bit) marks a page
403// that is out in swap; the slot number sits where the PPN would be,
404// and R, W, X and U keep the permissions it will get back.
405#define PTE_SWAP (1L << 8)
406#define SLOT2PTE(s) (((uint64)(s)) << 10)
407#define PTE2SLOT(pte) ((int)((pte) >> 10))
408
401409// shift a physical address to the right place for a PTE.
402410#define PA2PTE(pa) ((((uint64)pa) >> 12) << 10)
403411
404412#define PTE2PA(pte) (((pte) >> 10) << 12)
kernel/vm.c
@@ -201,8 +201,14 @@ uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free)
201201
202202 for (a = va; a < va + npages * PGSIZE; a += PGSIZE) {
203203 if ((pte = walk(pagetable, a, 0)) == 0) // leaf page table entry allocated?
204204 continue;
205 if (*pte & PTE_SWAP) { // the page is in swap, not in memory
206 if (do_free)
207 swapfree(PTE2SLOT(*pte));
208 *pte = 0;
209 continue;
210 }
205211 if ((*pte & PTE_V) == 0) // has physical page been allocated?
206212 continue;
207213 if (do_free) {
208214 uint64 pa = PTE2PA(*pte);
@@ -299,16 +305,25 @@ uvmfree(pagetable_t pagetable, uint64 sz)
299305// frees any allocated pages on failure.
300306int
301307uvmcopy(pagetable_t old, pagetable_t new, uint64 sz, struct proc *np)
302308{
303 pte_t *pte;
309 pte_t *pte, *npte;
304310 uint64 pa, i;
305311 uint flags;
306312 char *mem;
307313
308314 for (i = 0; i < sz; i += PGSIZE) {
309315 if ((pte = walk(old, i, 0)) == 0)
310316 continue; // page table entry hasn't been allocated
317 if (*pte & PTE_SWAP) {
318 // the child shares the slot; each process will read
319 // its own copy in when it uses the page.
320 if ((npte = walk(new, i, 1)) == 0)
321 goto err;
322 *npte = *pte;
323 swapdup(PTE2SLOT(*pte));
324 continue;
325 }
311326 if ((*pte & PTE_V) == 0)
312327 continue; // physical page hasn't been allocated
313328 pa = PTE2PA(*pte);
314329 flags = PTE_FLAGS(*pte);
4bf2377 Read a swapped-out page back in on a page fault
kernel/defs.h
@@ -113,8 +113,9 @@ int swapalloc(void);
113113void swapdup(int);
114114void swapfree(int);
115115void ftset(void *, struct proc *, uint64);
116116void ftclear(void *);
117uint64 swapin(pagetable_t, uint64);
117118
118119// spinlock.c
119120void acquire(struct spinlock*);
120121int holding(struct spinlock*);
kernel/swap.c
@@ -22,8 +22,16 @@ struct {
2222 uchar ref[NSWAP]; // number of PTEs that hold each slot
2323 int nused; // slots with ref > 0
2424} slots;
2525
26// swap I/O moves one page at a time. holding swapio.lock also
27// keeps a page from being read back in while it is still being
28// written out.
29struct {
30 struct sleeplock lock;
31 struct buf b; // only used to wait for the disk; b.data is unused
32} swapio;
33
2634// the frame table: for every physical page that is mapped as a
2735// user page, the process and the virtual address that map it.
2836// eviction needs this reverse map to find the PTE of a page.
2937#define NFRAME ((PHYSTOP - KERNBASE) / PGSIZE)
@@ -42,8 +50,9 @@ void
4250swapinit(void)
4351{
4452 initlock(&slots.lock, "slots");
4553 initlock(&ft.lock, "ftable");
54 initsleeplock(&swapio.lock, "swapio");
4655}
4756
4857// record that p maps the user page pa at va.
4958void
@@ -102,4 +111,40 @@ swapfree(int s)
102111 if (--slots.ref[s] == 0)
103112 slots.nused--;
104113 release(&slots.lock);
105114}
115
116// copy the page at physical address pa to slot s (write = 1),
117// or slot s to pa (write = 0). sleeps until the disk is done.
118// the caller holds swapio.lock.
119static void
120swaprw(int s, void *pa, int write)
121{
122 if (!holdingsleep(&swapio.lock))
123 panic("swaprw");
124 virtio_disk_rwpage(&swapio.b, SLOTBLOCK(s), pa, write);
125}
126
127// the page at va is in swap: read it into a fresh page and map
128// it again. returns the physical address, or 0 if out of memory.
129// sleeps, so the caller must not hold a spinlock.
130uint64
131swapin(pagetable_t pagetable, uint64 va)
132{
133 pte_t *pte;
134 char *mem;
135 int s;
136
137 if ((mem = kalloc()) == 0)
138 return 0;
139 pte = walk(pagetable, va, 0);
140 s = PTE2SLOT(*pte);
141
142 acquiresleep(&swapio.lock);
143 swaprw(s, mem, 0);
144 releasesleep(&swapio.lock);
145
146 *pte = PA2PTE(mem) | (*pte & (PTE_R | PTE_W | PTE_X | PTE_U)) | PTE_V;
147 ftset(mem, myproc(), va);
148 swapfree(s);
149 return (uint64)mem;
150}
kernel/trap.c
@@ -50,9 +50,14 @@ usertrap(void)
5050
5151 // save user program counter.
5252 p->trapframe->epc = r_sepc();
5353
54 if (r_scause() == 8) {
54 // vmfault may sleep (reading a page from swap), and while this
55 // process sleeps other traps on this hart reuse these registers.
56 uint64 scause = r_scause();
57 uint64 stval = r_stval();
58
59 if (scause == 8) {
5560 // system call
5661
5762 if (killed(p))
5863 kexit(-1);
@@ -67,15 +72,15 @@ usertrap(void)
6772
6873 syscall();
6974 } else if ((which_dev = devintr()) != 0) {
7075 // ok
71 } else if ((r_scause() == 15 || r_scause() == 13) &&
72 vmfault(p->pagetable, p->sz, r_stval(),
73 (r_scause() == 13) ? 1 : 0) != 0) {
74 // page fault on lazily-allocated page
76 } else if ((scause == 15 || scause == 13 || scause == 12) &&
77 vmfault(p->pagetable, p->sz, stval, (scause == 15) ? 0 : 1) != 0) {
78 // page fault on lazily-allocated page, or on a page in swap
79 // (12: an instruction fetch from a swapped-out text page).
7580 } else {
76 printk("usertrap(): unexpected scause 0x%lx pid=%d\n", r_scause(), p->pid);
77 printk(" sepc=0x%lx stval=0x%lx\n", r_sepc(), r_stval());
81 printk("usertrap(): unexpected scause 0x%lx pid=%d\n", scause, p->pid);
82 printk(" sepc=0x%lx stval=0x%lx\n", p->trapframe->epc, stval);
7883 setkilled(p);
7984 }
8085
8186 if (killed(p))
kernel/vm.c
@@ -469,19 +469,24 @@ copyinstr(pagetable_t pagetable, uint64 psz, char *dst, uint64 srcva,
469469 }
470470}
471471
472472// allocate and map user memory if process is referencing a page
473// that was lazily allocated in sys_sbrk().
473// that was lazily allocated in sys_sbrk(), or bring the page
474// back from swap.
474475// returns 0 if va is invalid or already mapped, or if
475476// out of physical memory, and physical address if successful.
477// may sleep.
476478uint64
477479vmfault(pagetable_t pagetable, uint64 psz, uint64 va, int read)
478480{
479481 uint64 mem;
482 pte_t *pte;
480483
481484 if (va >= psz)
482485 return 0;
483486 va = PGROUNDDOWN(va);
487 if ((pte = walk(pagetable, va, 0)) != 0 && (*pte & PTE_SWAP))
488 return swapin(pagetable, va);
484489 if (ismapped(pagetable, va)) {
485490 return 0;
486491 }
487492 mem = (uint64)kalloc();
6d912b6 Keep copyin and copyout from losing their page
kernel/vm.c
@@ -369,24 +369,32 @@ copyout(pagetable_t pagetable, uint64 psz, uint64 dstva, char *src, uint64 len)
369369 va0 = PGROUNDDOWN(dstva);
370370 if (va0 >= MAXVA)
371371 return -1;
372372
373 // with interrupts off this process keeps running on this
374 // hart, so no other hart can evict the page while we use pa0.
375 push_off();
373376 pa0 = walkaddr(pagetable, va0);
374377 if (pa0 == 0) {
375 if ((pa0 = vmfault(pagetable, psz, va0, 0)) == 0) {
378 pop_off();
379 // lazy or swapped out: vmfault may sleep.
380 if (vmfault(pagetable, psz, va0, 0) == 0)
376381 return -1;
377 }
382 continue; // translate again, with interrupts off
378383 }
379384
380385 pte = walk(pagetable, va0, 0);
381386 // forbid copyout over read-only user text pages.
382 if ((*pte & PTE_W) == 0)
387 if ((*pte & PTE_W) == 0) {
388 pop_off();
383389 return -1;
390 }
384391
385392 n = PGSIZE - (dstva - va0);
386393 if (n > len)
387394 n = len;
388395 memmove((void *)(pa0 + (dstva - va0)), src, n);
396 pop_off();
389397
390398 len -= n;
391399 src += n;
392400 dstva = va0 + PGSIZE;
@@ -403,18 +411,21 @@ copyin(pagetable_t pagetable, uint64 psz, char *dst, uint64 srcva, uint64 len)
403411 uint64 n, va0, pa0;
404412
405413 while (len > 0) {
406414 va0 = PGROUNDDOWN(srcva);
415 push_off(); // as in copyout
407416 pa0 = walkaddr(pagetable, va0);
408417 if (pa0 == 0) {
409 if ((pa0 = vmfault(pagetable, psz, va0, 1)) == 0) {
418 pop_off();
419 if (vmfault(pagetable, psz, va0, 1) == 0)
410420 return -1;
411 }
421 continue;
412422 }
413423 n = PGSIZE - (srcva - va0);
414424 if (n > len)
415425 n = len;
416426 memmove(dst, (void *)(pa0 + (srcva - va0)), n);
427 pop_off();
417428
418429 len -= n;
419430 dst += n;
420431 srcva = va0 + PGSIZE;
@@ -434,13 +445,15 @@ copyinstr(pagetable_t pagetable, uint64 psz, char *dst, uint64 srcva,
434445 int got_null = 0;
435446
436447 while (got_null == 0 && max > 0) {
437448 va0 = PGROUNDDOWN(srcva);
449 push_off(); // as in copyout
438450 pa0 = walkaddr(pagetable, va0);
439451 if (pa0 == 0) {
440 if ((pa0 = vmfault(pagetable, psz, va0, 1)) == 0) {
452 pop_off();
453 if (vmfault(pagetable, psz, va0, 1) == 0)
441454 return -1;
442 }
455 continue;
443456 }
444457 n = PGSIZE - (srcva - va0);
445458 if (n > max)
446459 n = max;
@@ -458,8 +471,9 @@ copyinstr(pagetable_t pagetable, uint64 psz, char *dst, uint64 srcva,
458471 --max;
459472 p++;
460473 dst++;
461474 }
475 pop_off();
462476
463477 srcva = va0 + PGSIZE;
464478 }
465479 if (got_null) {
e718e23 Pin the buffer while read, write or wait copy under a spinlock
kernel/defs.h
@@ -178,8 +178,10 @@ int copyout(pagetable_t, uint64, uint64, char *, uint64);
178178int copyin(pagetable_t, uint64, char *, uint64, uint64);
179179int copyinstr(pagetable_t, uint64, char *, uint64, uint64);
180180int ismapped(pagetable_t, uint64);
181181uint64 vmfault(pagetable_t, uint64, uint64, int);
182int uvmpin(uint64, uint64);
183void uvmunpin(uint64, uint64);
182184
183185// plic.c
184186void plicinit(void);
185187void plicinithart(void);
kernel/riscv.h
@@ -405,8 +405,12 @@ typedef uint64 *pagetable_t; // 512 PTEs
405405#define PTE_SWAP (1L << 8)
406406#define SLOT2PTE(s) (((uint64)(s)) << 10)
407407#define PTE2SLOT(pte) ((int)((pte) >> 10))
408408
409// on a valid PTE: the kernel is about to copy to or from this page
410// holding a spinlock, so it must stay in memory. bit 9, an RSW bit.
411#define PTE_PIN (1L << 9)
412
409413// shift a physical address to the right place for a PTE.
410414#define PA2PTE(pa) ((((uint64)pa) >> 12) << 10)
411415
412416#define PTE2PA(pte) (((pte) >> 10) << 12)
kernel/sysfile.c
@@ -68,31 +68,46 @@ sys_dup(void)
6868uint64
6969sys_read(void)
7070{
7171 struct file *f;
72 int n;
72 int n, r, pin;
7373 uint64 p;
7474
7575 argaddr(1, &p);
7676 argint(2, &n);
7777 if (argfd(0, 0, &f) < 0)
7878 return -1;
79 return fileread(f, p, n);
79 // pipes and the console copy out holding a spinlock. a file
80 // holds only sleep-locks, and may bring pages in as it copies.
81 pin = n > 0 && f->type != FD_INODE;
82 if (pin && uvmpin(p, n) < 0)
83 return -1;
84 r = fileread(f, p, n);
85 if (pin)
86 uvmunpin(p, n);
87 return r;
8088}
8189
8290uint64
8391sys_write(void)
8492{
8593 struct file *f;
86 int n;
94 int n, r, pin;
8795 uint64 p;
8896
8997 argaddr(1, &p);
9098 argint(2, &n);
9199 if (argfd(0, 0, &f) < 0)
92100 return -1;
93101
94 return filewrite(f, p, n);
102 // as in sys_read: pipewrite copies in holding a spinlock.
103 pin = n > 0 && f->type != FD_INODE;
104 if (pin && uvmpin(p, n) < 0)
105 return -1;
106 r = filewrite(f, p, n);
107 if (pin)
108 uvmunpin(p, n);
109 return r;
95110}
96111
97112uint64
98113sys_close(void)
kernel/sysproc.c
@@ -31,10 +31,18 @@ sys_fork(void)
3131uint64
3232sys_wait(void)
3333{
3434 uint64 p;
35 int r;
36
3537 argaddr(0, &p);
36 return kwait(p);
38 // kwait copies the status out holding spinlocks.
39 if (p != 0 && uvmpin(p, sizeof(int)) < 0)
40 return -1;
41 r = kwait(p);
42 if (p != 0)
43 uvmunpin(p, sizeof(int));
44 return r;
3745}
3846
3947uint64
4048sys_sbrk(void)
kernel/vm.c
@@ -482,8 +482,57 @@ copyinstr(pagetable_t pagetable, uint64 psz, char *dst, uint64 srcva,
482482 return -1;
483483 }
484484}
485485
486// piperead, pipewrite, consoleread and kwait copy to or from user
487// memory while holding a spinlock, and so cannot wait for a page to
488// come back from swap. bring every page of [va, va+n) that is in
489// swap back in, and pin every page that is in memory: eviction
490// leaves a page with PTE_PIN alone. pages that do not exist yet
491// (lazy), or that the user may not access, are left alone: the copy
492// treats them exactly as before. returns -1 if a page cannot be
493// brought back (out of memory).
494int
495uvmpin(uint64 va, uint64 n)
496{
497 struct proc *p = myproc();
498 uint64 a = PGROUNDDOWN(va);
499 pte_t *pte;
500
501 while (a < va + n && a < p->sz) {
502 push_off(); // as in copyout: no eviction between check and pin
503 pte = walk(p->pagetable, a, 0);
504 if (pte && (*pte & PTE_SWAP)) {
505 pop_off();
506 // may sleep, and may evict our own pages, but not pinned ones.
507 if (vmfault(p->pagetable, p->sz, a, 1) == 0) {
508 uvmunpin(va, n);
509 return -1;
510 }
511 continue; // check the page again
512 }
513 if (pte && (*pte & PTE_V) && (*pte & PTE_U))
514 *pte |= PTE_PIN;
515 pop_off();
516 a += PGSIZE;
517 }
518 return 0;
519}
520
521// undo uvmpin(va, n).
522void
523uvmunpin(uint64 va, uint64 n)
524{
525 struct proc *p = myproc();
526 uint64 a;
527 pte_t *pte;
528
529 for (a = PGROUNDDOWN(va); a < va + n && a < p->sz; a += PGSIZE) {
530 if ((pte = walk(p->pagetable, a, 0)) != 0 && (*pte & PTE_V))
531 *pte &= ~PTE_PIN;
532 }
533}
534
486535// allocate and map user memory if process is referencing a page
487536// that was lazily allocated in sys_sbrk(), or bring the page
488537// back from swap.
489538// returns 0 if va is invalid or already mapped, or if
8a1fa73 Evict a page with the clock algorithm
kernel/defs.h
@@ -114,8 +114,9 @@ void swapdup(int);
114114void swapfree(int);
115115void ftset(void *, struct proc *, uint64);
116116void ftclear(void *);
117117uint64 swapin(pagetable_t, uint64);
118int evict(void);
118119
119120// spinlock.c
120121void acquire(struct spinlock*);
121122int holding(struct spinlock*);
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_A (1L << 6) // accessed: set by the hardware (menvcfg.ADUE)
400401
401402// a PTE with V clear is ignored by the hardware, so its other bits
402403// are free for the kernel. PTE_SWAP (bit 8, an RSW bit) marks a page
403404// that is out in swap; the slot number sits where the PPN would be,
kernel/swap.c
@@ -43,8 +43,9 @@ struct {
4343 struct frame {
4444 struct proc *proc; // 0 if not a user page
4545 uint64 va;
4646 } f[NFRAME];
47 int hand; // the clock hand: next frame to look at
4748} ft;
4849
4950void
5051swapinit(void)
@@ -123,8 +124,89 @@ swaprw(int s, void *pa, int write)
123124 panic("swaprw");
124125 virtio_disk_rwpage(&swapio.b, SLOTBLOCK(s), pa, write);
125126}
126127
128// go round the frame table, clock-wise, for a user page to evict.
129// a page whose PTE has A set was used since the hand last passed:
130// clear A and give it a second chance. only pages of a process
131// that is not running on any hart (it flushed its TLB when it
132// entered the kernel) or of the caller itself are taken, and
133// never a pinned page. on success the PTE says "in slot s" and
134// the page is the caller's to write out and free.
135static void *
136clock(int s)
137{
138 struct proc *me = myproc();
139 struct proc *p;
140 pte_t *pte;
141 uint64 va;
142 int i;
143
144 for (int n = 0; n < 2 * NFRAME; n++) {
145 acquire(&ft.lock);
146 i = ft.hand;
147 ft.hand = (ft.hand + 1) % NFRAME;
148 p = ft.f[i].proc;
149 va = ft.f[i].va;
150 release(&ft.lock);
151 if (p == 0)
152 continue;
153
154 // p->lock before ft.lock: freeproc frees pages holding p->lock.
155 acquire(&p->lock);
156 if (p->state == SLEEPING || p->state == RUNNABLE || p == me) {
157 acquire(&ft.lock);
158 pte = 0;
159 if (ft.f[i].proc == p && ft.f[i].va == va)
160 pte = walk(p->pagetable, va, 0);
161 // during exec the frame may be in the new page table, not
162 // in p->pagetable yet: then the PTE maps another page. the
163 // stack guard page (no PTE_U) is never used: not worth a write.
164 if (pte && (*pte & PTE_V) && (*pte & PTE_U) &&
165 PTE2PA(*pte) == FRAMEPA(i) && !(*pte & PTE_PIN)) {
166 if (*pte & PTE_A) {
167 *pte &= ~PTE_A; // second chance
168 } else {
169 *pte = SLOT2PTE(s) | (*pte & (PTE_R | PTE_W | PTE_X | PTE_U)) |
170 PTE_SWAP;
171 ft.f[i].proc = 0;
172 release(&ft.lock);
173 release(&p->lock);
174 return (void *)FRAMEPA(i);
175 }
176 }
177 release(&ft.lock);
178 }
179 release(&p->lock);
180 }
181 return 0;
182}
183
184// write one user page out to swap and free it. returns 0 if the
185// swap area is full or no page can be evicted. sleeps, so the
186// caller must not hold a spinlock.
187int
188evict(void)
189{
190 void *pa;
191 int s;
192
193 acquiresleep(&swapio.lock);
194 if ((s = swapalloc()) < 0) {
195 releasesleep(&swapio.lock);
196 return 0;
197 }
198 if ((pa = clock(s)) == 0) {
199 swapfree(s);
200 releasesleep(&swapio.lock);
201 return 0;
202 }
203 swaprw(s, pa, 1);
204 releasesleep(&swapio.lock);
205 kfree(pa);
206 return 1;
207}
208
127209// the page at va is in swap: read it into a fresh page and map
128210// it again. returns the physical address, or 0 if out of memory.
129211// sleeps, so the caller must not hold a spinlock.
130212uint64
db21ba0 Evict when free memory runs low
kernel/defs.h
@@ -58,8 +58,9 @@ void ireclaim(int);
5858
5959// kalloc.c
6060void* kalloc(void);
6161void kfree(void *);
62int kfreecount(void);
6263void kinit(void);
6364
6465// log.c
6566void initlog(int, struct superblock*);
@@ -115,8 +116,9 @@ void swapfree(int);
115116void ftset(void *, struct proc *, uint64);
116117void ftclear(void *);
117118uint64 swapin(pagetable_t, uint64);
118119int evict(void);
120void * ualloc(void);
119121
120122// spinlock.c
121123void acquire(struct spinlock*);
122124int holding(struct spinlock*);
kernel/kalloc.c
@@ -20,8 +20,9 @@ struct run {
2020
2121struct {
2222 struct spinlock lock;
2323 struct run *freelist;
24 int nfree; // pages on freelist
2425} kmem;
2526
2627void
2728kinit()
@@ -58,8 +59,9 @@ kfree(void *pa)
5859
5960 acquire(&kmem.lock);
6061 r->next = kmem.freelist;
6162 kmem.freelist = r;
63 kmem.nfree++;
6264 release(&kmem.lock);
6365}
6466
6567// Allocate one 4096-byte page of physical memory.
@@ -71,12 +73,26 @@ kalloc(void)
7173 struct run *r;
7274
7375 acquire(&kmem.lock);
7476 r = kmem.freelist;
75 if (r)
77 if (r) {
7678 kmem.freelist = r->next;
79 kmem.nfree--;
80 }
7781 release(&kmem.lock);
7882
7983 if (r)
8084 memset((char *)r, 5, PGSIZE); // fill with junk
8185 return (void *)r;
8286}
87
88// the number of free pages.
89int
90kfreecount(void)
91{
92 int n;
93
94 acquire(&kmem.lock);
95 n = kmem.nfree;
96 release(&kmem.lock);
97 return n;
98}
kernel/swap.c
@@ -11,8 +11,12 @@
1111#include "buf.h"
1212#include "proc.h"
1313#include "defs.h"
1414
15// keep at least this many pages free for allocations that cannot
16// evict.
17#define FREELOW 32
18
1519// a slot holds one page: PGSIZE / BSIZE blocks of the swap area.
1620#define SLOTBLOCK(s) (SWAPSTART + (s) * (PGSIZE / BSIZE))
1721
1822// the swap slots. a slot is free when no PTE refers to it;
@@ -205,8 +209,27 @@ evict(void)
205209 kfree(pa);
206210 return 1;
207211}
208212
213// allocate a page for user memory. when few pages are free, first
214// evict pages to swap until FREELOW are free again, so that
215// allocations that cannot wait for the disk (page-table pages,
216// fork, pipes: all under spinlocks) still find memory. evicting
217// sleeps, so a caller that holds a spinlock (a copy under pi->lock
218// that touches a lazy page) only gets what is free, as before.
219void *
220ualloc(void)
221{
222 int locked;
223
224 push_off();
225 locked = mycpu()->noff > 1; // a spinlock is held besides our push_off
226 pop_off();
227 while (!locked && kfreecount() < FREELOW && evict())
228 ;
229 return kalloc();
230}
231
209232// the page at va is in swap: read it into a fresh page and map
210233// it again. returns the physical address, or 0 if out of memory.
211234// sleeps, so the caller must not hold a spinlock.
212235uint64
@@ -215,9 +238,9 @@ swapin(pagetable_t pagetable, uint64 va)
215238 pte_t *pte;
216239 char *mem;
217240 int s;
218241
219 if ((mem = kalloc()) == 0)
242 if ((mem = ualloc()) == 0)
220243 return 0;
221244 pte = walk(pagetable, va, 0);
222245 s = PTE2SLOT(*pte);
223246
kernel/vm.c
@@ -231,9 +231,9 @@ uvmalloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz, int xperm)
231231 return oldsz;
232232
233233 oldsz = PGROUNDUP(oldsz);
234234 for (a = oldsz; a < newsz; a += PGSIZE) {
235 mem = kalloc();
235 mem = ualloc();
236236 if (mem == 0) {
237237 uvmdealloc(pagetable, a, oldsz);
238238 return 0;
239239 }
@@ -551,9 +551,9 @@ vmfault(pagetable_t pagetable, uint64 psz, uint64 va, int read)
551551 return swapin(pagetable, va);
552552 if (ismapped(pagetable, va)) {
553553 return 0;
554554 }
555 mem = (uint64)kalloc();
555 mem = (uint64)ualloc();
556556 if (mem == 0)
557557 return 0;
558558 memset((void *)mem, 0, PGSIZE);
559559 if (mappages(pagetable, va, PGSIZE, mem, PTE_W | PTE_U | PTE_R) != 0) {
8ad407b Add swapstat and swaptest, a test program for swapping
Makefile
@@ -146,8 +146,9 @@ UPROGS=\
146146 $U/_usertests\
147147 $U/_grind\
148148 $U/_wc\
149149 $U/_zombie\
150 $U/_swaptest\
150151 $U/_logstress\
151152 $U/_forphan\
152153 $U/_dorphan\
153154 $U/_sync\
kernel/defs.h
@@ -7,8 +7,9 @@ struct pipe;
77struct proc;
88struct spinlock;
99struct sleeplock;
1010struct stat;
11struct swapstat;
1112struct superblock;
1213
1314// bio.c
1415void binit(void);
@@ -117,8 +118,9 @@ void ftset(void *, struct proc *, uint64);
117118void ftclear(void *);
118119uint64 swapin(pagetable_t, uint64);
119120int evict(void);
120121void * ualloc(void);
122void swapstat(struct swapstat *);
121123
122124// spinlock.c
123125void acquire(struct spinlock*);
124126int holding(struct spinlock*);
kernel/swap.c
@@ -9,8 +9,9 @@
99#include "sleeplock.h"
1010#include "fs.h"
1111#include "buf.h"
1212#include "proc.h"
13#include "swapstat.h"
1314#include "defs.h"
1415
1516// keep at least this many pages free for allocations that cannot
1617// evict.
@@ -32,8 +33,10 @@ struct {
3233// written out.
3334struct {
3435 struct sleeplock lock;
3536 struct buf b; // only used to wait for the disk; b.data is unused
37 int pageouts; // pages written out since boot
38 int pageins; // pages read in since boot
3639} swapio;
3740
3841// the frame table: for every physical page that is mapped as a
3942// user page, the process and the virtual address that map it.
@@ -204,8 +207,9 @@ evict(void)
204207 releasesleep(&swapio.lock);
205208 return 0;
206209 }
207210 swaprw(s, pa, 1);
211 swapio.pageouts++;
208212 releasesleep(&swapio.lock);
209213 kfree(pa);
210214 return 1;
211215}
@@ -245,11 +249,27 @@ swapin(pagetable_t pagetable, uint64 va)
245249 s = PTE2SLOT(*pte);
246250
247251 acquiresleep(&swapio.lock);
248252 swaprw(s, mem, 0);
253 swapio.pageins++;
249254 releasesleep(&swapio.lock);
250255
251256 *pte = PA2PTE(mem) | (*pte & (PTE_R | PTE_W | PTE_X | PTE_U)) | PTE_V;
252257 ftset(mem, myproc(), va);
253258 swapfree(s);
254259 return (uint64)mem;
255260}
261
262// for the swapstat system call.
263void
264swapstat(struct swapstat *st)
265{
266 st->freepages = kfreecount();
267 acquire(&slots.lock);
268 st->slotsused = slots.nused;
269 release(&slots.lock);
270 st->nslots = NSWAP;
271 acquiresleep(&swapio.lock);
272 st->pageouts = swapio.pageouts;
273 st->pageins = swapio.pageins;
274 releasesleep(&swapio.lock);
275}
kernel/swapstat.h
@@ -0,0 +1,8 @@
1// filled in by the swapstat system call.
2struct swapstat {
3 int freepages; // pages on the free list
4 int slotsused; // swap slots in use
5 int nslots; // swap slots in all (NSWAP)
6 int pageouts; // pages written to swap since boot
7 int pageins; // pages read from swap since boot
8};
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_swapstat(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_swapstat] = sys_swapstat,
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_swapstat 23
kernel/sysproc.c
@@ -5,8 +5,9 @@
55#include "memlayout.h"
66#include "spinlock.h"
77#include "proc.h"
88#include "vm.h"
9#include "swapstat.h"
910
1011uint64
1112sys_exit(void)
1213{
@@ -117,4 +118,19 @@ sys_uptime(void)
117118 xticks = ticks;
118119 release(&tickslock);
119120 return xticks;
120121}
122
123// report free memory and swap use.
124uint64
125sys_swapstat(void)
126{
127 struct swapstat st;
128 uint64 addr;
129
130 argaddr(0, &addr);
131 swapstat(&st);
132 if (copyout(myproc()->pagetable, myproc()->sz, addr, (char *)&st,
133 sizeof(st)) < 0)
134 return -1;
135 return 0;
136}
user/swaptest.c
@@ -0,0 +1,257 @@
1// Test swapping: use more memory than the machine has, check
2// that every page comes back with its contents, use pages in
3// swap as system call buffers, fork a process that is partly in
4// swap, and run several big processes at once.
5
6#include "kernel/types.h"
7#include "kernel/swapstat.h"
8#include "user/user.h"
9
10#define PG 4096
11
12int npages = 36000; // more than the 32,768 pages of RAM
13
14// the value of word w of page i in round r.
15uint64
16val(uint64 i, uint64 w, uint64 r)
17{
18 return (i << 32) ^ (w << 20) ^ (r * 0x9e3779b97f4a7c15ULL);
19}
20
21void
22fill(char *base, int n, int r)
23{
24 for (int i = 0; i < n; i++) {
25 uint64 *p = (uint64 *)(base + (uint64)i * PG);
26 for (int w = 0; w < PG / 8; w++)
27 p[w] = val(i, w, r);
28 }
29}
30
31// check pages [0, n), the last one first if backward.
32// returns the number of pages with a wrong word.
33int
34check(char *base, int n, int r, int backward)
35{
36 int bad = 0;
37 for (int k = 0; k < n; k++) {
38 int i = backward ? n - 1 - k : k;
39 uint64 *p = (uint64 *)(base + (uint64)i * PG);
40 for (int w = 0; w < PG / 8; w++) {
41 if (p[w] != val(i, w, r)) {
42 if (bad < 3)
43 printf("swaptest: page %d word %d is %lx\n", i, w, p[w]);
44 bad++;
45 break;
46 }
47 }
48 }
49 return bad;
50}
51
52struct swapstat
53sst(void)
54{
55 struct swapstat st;
56 swapstat(&st);
57 return st;
58}
59
60// wait for one child; 1 if it exited with status 0.
61int
62childok(void)
63{
64 int xs = 1;
65 if (wait(&xs) < 0)
66 return 0;
67 return xs == 0;
68}
69
70char *
71grow(int n)
72{
73 char *p = sbrklazy(n * PG);
74 if (p == SBRK_ERROR) {
75 printf("swaptest: sbrklazy(%d pages) failed\n", n);
76 exit(1);
77 }
78 return p;
79}
80
81// write npages pages, then check them, newest first.
82void
83bigtest(void)
84{
85 struct swapstat a = sst(), b, c;
86 char *base = grow(npages);
87 fill(base, npages, 1);
88 b = sst();
89 printf("swaptest: big: wrote %d pages: %d out, %d in\n", npages,
90 b.pageouts - a.pageouts, b.pageins - a.pageins);
91 int bad = check(base, npages, 1, 1);
92 c = sst();
93 printf("swaptest: big: checked %d pages, %d wrong: %d out, %d in\n",
94 npages, bad, c.pageouts - b.pageouts, c.pageins - b.pageins);
95 exit(bad != 0);
96}
97
98// the kernel reads and writes pages that are in swap: copy page 2i
99// to page 2i+1 through a pipe, 512 bytes (the pipe's size) at a
100// time, until 4 source pages and 4 destination pages were found
101// in swap (the first write() or read() of the page read it in).
102void
103syscalltest(void)
104{
105 int fds[2], bad = 0, nsrc = 0, ndst = 0, i;
106 char *base = grow(npages);
107 fill(base, npages, 2);
108 if (pipe(fds) < 0)
109 exit(1);
110 for (i = 0; i < npages / 2 && (nsrc < 4 || ndst < 4); i++) {
111 char *src = base + (uint64)(2 * i) * PG;
112 char *dst = src + PG;
113 for (int off = 0; off < PG; off += 512) {
114 struct swapstat a = sst();
115 if (write(fds[1], src + off, 512) != 512) {
116 printf("swaptest: write failed\n");
117 exit(1);
118 }
119 struct swapstat b = sst();
120 if (read(fds[0], dst + off, 512) != 512) {
121 printf("swaptest: read failed\n");
122 exit(1);
123 }
124 struct swapstat c = sst();
125 if (off == 0) {
126 nsrc += b.pageins > a.pageins;
127 ndst += c.pageins > b.pageins;
128 }
129 }
130 if (memcmp(src, dst, PG) != 0)
131 bad++;
132 }
133 printf("swaptest: syscalls: copied %d pages, %d wrong; %d sources and %d "
134 "destinations were in swap\n",
135 i, bad, nsrc, ndst);
136 exit(bad != 0 || nsrc < 4 || ndst < 4);
137}
138
139// fill 2000 pages, push them out by using a lot of memory, give
140// that memory back, then fork. both processes check all pages,
141// and the child's writes must not reach the parent.
142void
143forktest(void)
144{
145 int m = 2000, h = 37000;
146 char *base = grow(m);
147 fill(base, m, 3);
148 char *hog = grow(h);
149 for (int i = 0; i < h; i++)
150 hog[(uint64)i * PG] = 1;
151 sbrk(-h * PG);
152 struct swapstat a = sst();
153 printf("swaptest: fork: %d slots in use at fork\n", a.slotsused);
154 int pid = fork();
155 if (pid < 0) {
156 printf("swaptest: fork failed\n");
157 exit(1);
158 }
159 if (pid == 0) {
160 int bad = check(base, m, 3, 0);
161 fill(base, m / 2, 4); // must not show in the parent
162 exit(bad != 0);
163 }
164 int cok = childok();
165 int bad = check(base, m, 3, 0);
166 struct swapstat b = sst();
167 printf("swaptest: fork: child %s, parent %d wrong, %d pages read in\n",
168 cok ? "ok" : "FAILED", bad, b.pageins - a.pageins);
169 exit(!cok || bad != 0 || a.slotsused == 0);
170}
171
172// three processes of 12,500 pages each: all three fill their
173// pages before any of them checks, so together they need more
174// memory than there is and evict each other's pages.
175void
176procstest(void)
177{
178 int n = 12500, ready[2], go[2], ok = 1;
179 char c;
180 struct swapstat a = sst();
181 if (pipe(ready) < 0 || pipe(go) < 0)
182 exit(1);
183 for (int k = 0; k < 3; k++) {
184 int pid = fork();
185 if (pid < 0) {
186 printf("swaptest: fork failed\n");
187 exit(1);
188 }
189 if (pid == 0) {
190 close(ready[0]);
191 close(go[1]);
192 char *base = grow(n);
193 fill(base, n, 10 + k);
194 write(ready[1], "r", 1);
195 close(ready[1]);
196 read(go[0], &c, 1); // wait until all three have filled
197 exit(check(base, n, 10 + k, 1) != 0);
198 }
199 }
200 // a child that was killed never writes; its exit closes its end,
201 // so read returns 0 instead of waiting forever.
202 close(ready[1]);
203 for (int k = 0; k < 3; k++)
204 if (read(ready[0], &c, 1) != 1)
205 break;
206 write(go[1], "ggg", 3);
207 for (int k = 0; k < 3; k++)
208 ok &= childok();
209 struct swapstat b = sst();
210 printf("swaptest: procs: %d out, %d in\n", b.pageouts - a.pageouts,
211 b.pageins - a.pageins);
212 exit(!ok || b.pageouts == a.pageouts);
213}
214
215// run f in a child and print OK or FAIL.
216int
217run(void (*f)(void), char *name)
218{
219 int pid = fork();
220 if (pid < 0) {
221 printf("swaptest: fork failed\n");
222 exit(1);
223 }
224 if (pid == 0)
225 f();
226 int ok = childok();
227 printf("swaptest: %s: %s\n", name, ok ? "OK" : "FAIL");
228 return ok;
229}
230
231int
232main(int argc, char *argv[])
233{
234 int ok = 1;
235 if (argc > 1)
236 npages = atoi(argv[1]);
237 struct swapstat a = sst();
238 ok &= run(bigtest, "big");
239 ok &= run(syscalltest, "syscalls");
240 ok &= run(forktest, "fork");
241 ok &= run(procstest, "procs");
242 struct swapstat b = sst();
243 // a page moving between memory and swap changes both counts.
244 printf("swaptest: free pages + free slots: %d before, %d after\n",
245 a.freepages + a.nslots - a.slotsused,
246 b.freepages + b.nslots - b.slotsused);
247 if (a.freepages - a.slotsused != b.freepages - b.slotsused) {
248 printf("swaptest: leak: FAIL\n");
249 ok = 0;
250 } else {
251 printf("swaptest: leak: OK\n");
252 }
253 printf("swaptest: %d pages written out, %d read in\n",
254 b.pageouts - a.pageouts, b.pageins - a.pageins);
255 printf("swaptest: %s\n", ok ? "ALL OK" : "SOME TESTS FAILED");
256 exit(!ok);
257}
user/user.h
@@ -1,7 +1,8 @@
11#define SBRK_ERROR ((char *)-1)
22
33struct stat;
4struct swapstat;
45
56// system calls
67int fork(void);
78int exit(int) __attribute__((noreturn));
@@ -24,8 +25,9 @@ int getpid(void);
2425char *sys_sbrk(int, int);
2526int pause(int);
2627int uptime(void);
2728int sync(void);
29int swapstat(struct swapstat *);
2830
2931// ulib.c
3032int stat(const char *, struct stat *);
3133char *strcpy(char *, const char *);
user/usys.pl
@@ -42,4 +42,5 @@ entry("getpid");
4242entry("sbrk");
4343entry("pause");
4444entry("uptime");
4545entry("sync");
46entry("swapstat");

6. Verify and measure

On the branch (ext/16-swap, 12 commits), built with the project toolchain and run on 3 harts (-smp 3 -m 128M), one boot:

$ swaptest
swaptest: big: wrote 36000 pages: 3710 out, 0 in
swaptest: big: checked 36000 pages, 0 wrong: 32299 out, 32299 in
swaptest: big: OK
swaptest: syscalls: copied 32 pages, 0 wrong; 5 sources and 4 destinations were in swap
swaptest: syscalls: OK
swaptest: fork: 21 slots in use at fork
swaptest: fork: child ok, parent 0 wrong, 26 pages read in
swaptest: fork: OK
swaptest: procs: 15838 out, 13651 in
swaptest: procs: OK
swaptest: free pages + free slots: 40594 before, 40594 after
swaptest: leak: OK
swaptest: 62267 pages written out, 45992 read in
swaptest: ALL OK
$ usertests -q
usertests starting
test copyin: OK
test copyout: OK
...
test kernmem: usertrap(): unexpected scause 0xd pid=6485
...
test sbrkfail: OK
...
test lazy_sbrk: OK
...
ALL TESTS PASSED
$ swaptest
swaptest: big: wrote 36000 pages: 3708 out, 0 in
swaptest: big: checked 36000 pages, 0 wrong: 16073 out, 16073 in
swaptest: big: OK
swaptest: syscalls: copied 31 pages, 0 wrong; 4 sources and 4 destinations were in swap
swaptest: syscalls: OK
swaptest: fork: 22 slots in use at fork
swaptest: fork: child ok, parent 0 wrong, 24 pages read in
swaptest: fork: OK
swaptest: procs: 14608 out, 14603 in
swaptest: procs: OK
swaptest: free pages + free slots: 40594 before, 40594 after
swaptest: leak: OK
swaptest: 44807 pages written out, 30716 read in
swaptest: ALL OK

What this shows, check by check:

big: 36,000 pages of 4,096 bytes, every 8-byte word checked, in a machine with 32,768 pages of RAM and 32,403 free at boot. Writing them needed 3,710 evictions. Checking them newest first moved 32,299 pages in and out in the first run and 16,073 in the second: which pages are out depends on where the clock hand happens to be (next section).
syscalls: write read 5 source pages back from swap, read 4 destination pages, all before the copy itself, which runs under pi->lock; no panic, no wrong byte.
fork: 21 slots were in use when the process forked (most of them its own pages); the child read every page correctly through the shared slots, its writes did not reach the parent, and the parent then read its own pages back (26 swap-ins).
procs: three processes, 37,500 pages in all, evicted each other’s pages (15,838 pages written out) and all read back correct.
leak: free pages plus free slots, 40,594 before and after. The checks run in child processes, so their page-table pages, which sbrk(-n) does not free, are gone too.
usertests -q passes with swapping active. The usertrap() lines are the expected kills of tests such as kernmem, MAXVAplus, stacktest and nowrite. Several tests (sbrkfail, execout, the countfree at the start and end) use up all of memory on purpose; with swap they also fill the swap area first, and their final count of free pages before and after still matches.

usertests -q also passes at commits 8, 9 and 10 alone, and other boots of the head ran swaptest three more times: ALL OK each time.

The numbers below come from a copy of the branch with two extra programs, not part of the branch: pinread and sstat.

Reading into a lazy buffer, as before. pinread reads the 2,441-byte README into a buffer reserved with sbrklazy and never touched, of 1, 1,000, 34,000 and 100,000 pages. On the original kernel and on the reference branch the output is the same:

pinread: read(README, 1-page lazy buffer) = 2441
pinread: read(README, 1000-page lazy buffer) = 2441
pinread: read(README, 34000-page lazy buffer) = 2441
pinread: read(README, 100000-page lazy buffer) = 2441

read on a file pins nothing, and the copy allocates only the one page it fills. (With a pin of the whole buffer, the last two lines read = -1.)

How much usertests -q swaps. sstat prints swapstat’s numbers. In one boot the copy ran pinread, sstat, usertests -q, sstat, swaptest, sstat:

sstat: free 32403 slots 0/8192 out 0 in 0 uptime 6
[...]
ALL TESTS PASSED
sstat: free 32404 slots 1/8192 out 49160 in 34 uptime 873
[...]
swaptest: ALL OK
sstat: free 32406 slots 3/8192 out 98391 in 33303 uptime 1378

	pages written out	pages read in	time
`usertests -q`	49,160	34	867 ticks (about 87 s); 89.9 s by the wall clock
`swaptest` (that run)	49,231	33,269	505 ticks (about 50 s)
`usertests -q` on the original kernel	0	0	54.1 s by the wall clock

usertests writes out about 49,000 pages and reads back 34: the tests that fill memory (sbrkfail, execout with its 15 rounds, countfree) push their own pages out and then exit, and freeing a page that is in swap costs no I/O, only swapfree. That is probably most of the extra half minute. (These timings were measured while the computer was busy with other work; your times will differ, but the page counts will not change much.)

What a page costs. In the swaptest run above, 82,500 page transfers took about 50 s of wall time, including everything else the test did: at most about 0.6 ms per transfer, one 4,096-byte virtio request each, on QEMU’s emulated disk.

The clock and a sequential scan. big writes pages 0 to 35,999 and then checks them from 35,999 down. A scan larger than memory is the classic bad case for LRU-like policies. On a freshly booted kernel the check moved 32,299 pages each way in every recorded run; run again in the same boot, it moved about 16,000 (16,073 and 16,095), because the clock hand starts from wherever the last test left it. The hand goes round physical pages, not virtual addresses, so the pages in swap are not simply “the oldest” ones. A real kernel adds read-ahead and smarter aging; see further.

What it costs in memory. The frame table is 512 KiB (128 pages), the slot counts 8 KiB, and swapio’s unused buffer 1 KiB: the kernel image ends at 0x800a40b8 instead of 0x80020bb0, 131 pages more. 32 pages are kept free by ualloc as a reserve.

7. Go further

Skip clean pages. Keep the slot of a page that was read in, and clear D when you do; if D is still clear when the page is evicted again, the copy on disk is still good and no write is needed. This is the swap cache, and it is where the D bit, which the hardware already maintains, pays off.
A swapper thread. Move eviction into a kernel thread that wakes when free memory drops below a low-water mark and evicts up to a high-water mark. ualloc then only waits, and fork could wait for it too instead of failing when memory is full.
Let fork make room. fork cannot evict under np->lock. Count the parent’s resident pages first and evict until that many are free, before allocproc; or combine with copy-on-write (lab 11), which makes fork need almost no pages at all.
TLB shootdowns. Add an interprocessor interrupt (the SBI or the CLINT’s software interrupts) that makes another hart execute sfence.vma and acknowledge it, and then allow evicting pages of processes that are running. Measure what the round trip costs, and see why real kernels batch shootdowns.
Several requests in flight. swapio.lock allows one page transfer at a time. The virtio queue has room for more; give each eviction its own buffer and a per-slot “being written” flag, and measure swaptest again.