Extension labs · lab 12 · Memory · ★★★★☆

Demand-paged exec

In this tree kexec reads a whole program into memory before the program runs its first instruction. For each loadable segment of the ELF file it allocates every page and fills it with readi (loadseg). usertests is 16 pages; echo is 2, and the second, its bss, is never touched when you type echo hi. In this lab exec only records where each segment lives in the file, keeps the file, and lets the program start with no text and no data at all. Each page is read from the file the first time something touches it.

The idea is old (it is how Unix has run programs since the late 1970s), and it touches more of the kernel than you might expect. Who notices the first touch of a page, and what does that have to do with the lazy heap this tree already has? Reading a file means locking an inode and waiting for the disk, from inside a fault handler: where can such a fault happen, and what does the kernel hold at that moment? What happens when a program reads its own file into a page of itself that is not there yet? What keeps the file alive while it runs, and what does a running program see when someone deletes, truncates or rewrites it? The think section asks these questions in the order a designer meets them.

The reference solution is eleven small commits. With it, dexectest lazy loads 8 of the 25 pages of its image, and each page it touches later costs exactly one page of memory.

Read first: Tour 10: Exceptions and faults, Tour 17: Sleep-locks, Tour 22: exec, Tour 26: sbrk, eager and lazy, and page faults, Tour 28: Crossing the user/kernel boundary in memory, Tour 33: The life of an inode, Tour 36: Reading and writing a file · The stacks of xv6, Locks and interrupt state

What this lab teaches

How an instruction fetch from a page that is not mapped reaches the kernel, and how a new kind of page fault has to share usertrap and vmfault with the lazy heap this tree already has.
What a freshly loaded page must contain, byte by byte, and which PTE bits it gets, so that the program cannot tell it was loaded late.
What a fault handler may do when it has to wait for the disk: which locks are held and what the interrupt state is on each path that can reach it, and what the rule “never sleep holding a spinlock” means for the kernel’s own copies into user memory.
What can go wrong when a system call that already holds locks touches a page that is not there yet, and how to rule it out by construction instead of detecting it.
Why a running program needs a counted reference to its file, why dropping that reference needs a transaction, and what a running program sees when its file is removed, truncated or rewritten.
What a trap handler can lose when it sleeps, and why a test that counts free pages has to change its idea of what is free.

The reference branch

ext/12-demand-exec 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-demand-exec 06aad25   # start your own
git diff 06aad25 origin/ext/12-demand-exec   # only when you want the answer

1. The spec

Behaviour. exec reads the ELF header and the program headers, checks them at least as strictly as before (a segment that could not have been loaded must still make exec fail), and records each loadable segment: where it starts in memory, its size in memory, where its bytes are in the file, how many bytes the file supplies, and its permissions. It maps no page of text or data. The stack and the argument strings are still built by exec, as before. When the program, or the kernel on its behalf, first touches a page of a segment, that one page is allocated, filled from the file (bytes the file does not supply are zero), and mapped with the segment’s permissions. A page outside every segment and outside the heap is still a fatal fault.

Every way of touching memory must work: instruction fetches, loads, stores, and the kernel’s own copies for system calls (read into a buffer, write from one, wait(&status), exec’s argument strings, path names).

The file. A running program keeps its file alive. If the file is unlinked while the program runs, the program keeps running, and the file’s inode and blocks are freed when the last process running it exits or calls exec. If the file is truncated, a page that is not loaded yet cannot be read, and the process is killed when it needs that page. If the file is rewritten, pages loaded after the change come from the new contents. (The think section discusses why this lab allows that.)

What must not change.

Text stays read-only and executable, data writable and not executable: a store to text must still kill the process (usertests nowrite), and read into text must still fail (usertests copyout).
The lazy heap (sbrklazy) keeps working, and memory obtained after sbrk(-n) is zero.
No kernel panic or hang, whatever the program does with its own file, and whatever program headers a crafted ELF file contains.
usertests -q must print ALL TESTS PASSED on 3 harts. A small change to usertests turns out to be needed; the think section finds which, and why.

The test program, dexectest, prints one line per check (dexectest NAME runs one):

$ dexectest
dexectest: lazy: touching 2 data pages took 2 free pages
dexectest: lazy: OK
dexectest: fork: OK
dexectest: locked: OK
dexectest: selfread: OK
dexectest: unlink: OK
usertrap(): unexpected scause 0xd pid=7
            sepc=0xd52 stval=0xd000
dexectest: truncate: OK
dexectest: modify: OK
dexectest: shrink: OK
dexectest: content: OK
dexectest: ALL OK

The program carries a 16-page initialized array, big[], so it has data pages that come from the file; each check touches its own pages of it first.

lazy: count free pages, touch two untouched pages of big[], count again: exactly 2 pages must be gone, and both pages must hold the file’s values.
fork: a child forked before page 3 was touched reads it; so does the parent.
locked: write to a pipe from an untouched page, read from the pipe into another, and wait(&status) with status in a third: each must work.
selfread: read the program’s own file into an untouched data page (must succeed and show \x7fELF), and into a page of read-only data (must fail).
unlink, truncate, modify: a copy of the program, started as a helper, has its file unlinked (it must finish normally), truncated to nothing (it must be killed: the usertrap() lines above are that kill, expected), or overwritten in one place (it must see the new value).
shrink: a child gives back memory below the end of its image with sbrk and takes the addresses back with sbrklazy: they must read as zero.
content: every byte of the text equals the file, the rest of its last page is zero, and a bss array is all zeros.

2. Think first

Answer each question in your head (or on paper) before opening a hint. Hints get more specific; the reference answer comes last.

1What must exec remember, and for how long?

Today kexec loads every segment with loadseg and then lets go of the file (kernel/exec.c:79). If a page is to be read only when it is first touched, possibly minutes later, what must the kernel keep, and where? What guarantees that the file is still there, and still the same file, when that moment comes? Which other events in a process’s life have to know about what you keep?

2Which fault, and whose fault is it?

With nothing mapped, the very first instruction of a new program cannot be fetched. What does the hart report, and does usertrap handle it today? This tree already fills some missing pages on demand: vmfault gives the lazy heap fresh zero pages (kernel/trap.c:71). Now a missing page below p->sz can be a page of the program, a lazy heap page, or something that should never be touched. How does the kernel tell them apart?

The reference design

The first fetch raises an instruction page fault, scause 12. usertrap today sends only 13 (load) and 15 (store) to vmfault; 12 falls into the else branch, which kills the process. Since the first program is init, the kernel then panics with init exiting (clinic 1). Add 12 to the condition and treat it as a read.

The three kinds of missing page are separated by address alone, because kexec lays out every address space the same way:

address	what it is	who maps it
below the end of the last segment, inside a segment	program text or data	fault: read from the file
below the end, between two segments	a hole	nobody: fatal
guard page and stack	the stack	`kexec`, eagerly
above the stack, below `p->sz`	the lazy heap	fault: zero page (`vmfault`)

So vmfault keeps its checks (below p->sz, not mapped) and asks one more question before allocating a zero page: is the page below the end of the image? The reference computes that end from the last recorded segment (imgend) and sends such pages to a new function, loadpage. Nothing changes for the heap.

One more caller is easy to miss: the kernel’s own copies. copyin, copyout and copyinstr call vmfault for a missing page (kernel/vm.c:357), and they run with the process’s page table in hand, so a system call can be the first to touch a page of the program. In the recorded boot, the data page of init’s image was first touched by the kernel: init’s child (pid 2, about to become the shell) called exec("sh", argv), and sys_exec fetched the global argv array with copyin.

Check yourself

1warm-upMatch the pairs

Match each scause value that can reach usertrap from user mode with what happened.

1213158

2solidChoose one

You have made kexec map nothing and taught vmfault to load program pages, but left usertrap's condition as scause == 15 || scause == 13. You boot. What do you see?

kernel/trap.c

} else if ((which_dev = devintr()) != 0) {
  // ok
} else if ((r_scause() == 15 || r_scause() == 13) &&
           vmfault(p->pagetable, p->sz, r_stval(),
                   (r_scause() == 13) ? 1 : 0) != 0) {
  // page fault on lazily-allocated page
} else {
  printk("usertrap(): unexpected scause 0x%lx pid=%d\n", r_scause(), p->pid);
  printk("            sepc=0x%lx stval=0x%lx\n", r_sepc(), r_stval());
  setkilled(p);
}

A hang: the fault is retried forever.init: starting sh, and then the shell dies at its first instructionusertrap(): unexpected scause 0xc pid=1, then panic: init exitingusertrap(): unexpected scause 0xd pid=1, because the fetch is a load

3What goes into the page?

A page of a segment is about to be loaded. Which of its 4096 bytes come from the file, and from where in the file? Which must be zero? Take two real cases: sh’s data segment starts at 0x2000 with filesz 0x10 and memsz 0x98; in the original tree, usertests’ text ends at 0x8739, in the middle of page 0x8000. And which PTE bits does each page get?

Check yourself

1solidType a number

usertests’ data segment: vaddr 0x9000, off 0xa000, filesz 0x4d0, memsz 0x6d08. When page 0x9000 is loaded, how many bytes are read from the file?

decimal, 0x hex or 0b binary

2solidDecode the bits

gdb read this PTE right after the reference mapped init’s page 0x0. Decode it.

Value: 0x21fd541b

V (bit 0)W (bit 2)X (bit 3)U (bit 4)A (bit 6)

4Where does a load run, and what may it do there?

Loading a page now locks the executable’s inode (ilock, a sleep lock) and calls readi, which calls bread, which may wait for the disk. Find every path that can reach the load. On each, are interrupts on or off, and which locks does the thread hold at that moment? Which paths break a rule of this kernel, what would happen, and what will you do about it?

The reference design

The paths, with the state observed by gdb on the reference branch:

path	interrupts	locks held when the load starts	may it sleep?
`usertrap` → `vmfault` (a fault from user code)	off	none	yes
system call → `copyinstr` in `argstr` (e.g. `sys_open`)	on	none	yes
`sys_mkdir`, `sys_mknod`, `sys_chdir`: `argstr` after `begin_op`	on	none (a transaction is not a lock)	yes
`piperead` / `pipewrite` → `copyout`/`copyin`	off	`pi->lock`	no
`consoleread` → `copyout`	off	`cons.lock`	no
`kwait` → `copyout` of the status	off	`wait_lock`, the child’s `p->lock`	no
`fileread`/`filewrite` → `readi`/`writei` → copy	on	the file’s inode lock and a buffer’s lock (sleep-locks)	see the next question

A sleep from a page fault is legal even though interrupts are off: sleep takes p->lock, sched checks that noff is exactly 1 and that interrupts are off, and the scheduler on this hart turns them back on. gdb saw the first load of the system do it: init’s text page needed three disk reads, and init slept three times inside virtio_disk_rw with noff 1, intena 0 (gdb stopped three times in the disk driver’s wait loop), and came back on another hart in between.

The three spinlock paths are bugs waiting for a cache miss. piperead and pipewrite hold pi->lock (noff 1) while they copy; if the copy loads a page and bread has to wait for the disk, sched sees noff 2 and panics. Clinic 6 shows exactly that, with dexectest locked (there, the pipe write). If the blocks happen to be cached, nothing sleeps and nothing happens, which is why such a bug can survive testing.

The fix used here: load first, then lock. sys_read, sys_write and sys_wait call a new function, uvmprefault, before they take any lock. It walks the pages of the user buffer that lie below the end of the image and loads the missing ones. A loaded page stays loaded for the rest of the system call: only this process could unmap it (with sbrk, exec or exit), and it is busy in this system call; xv6 processes have one thread. So the copy, later, under the lock, finds every program page present. Lazy heap pages need nothing: allocating one takes only kalloc's spinlock and never sleeps, as before.

Alternatives, and why not: loading in a kernel thread (xv6 has none), making the copies fail under a lock (a read from a pipe into a global buffer would fail at random), or copying through a bounce buffer outside the lock in every driver (many changes; the prefault is one rule in three places).

Check yourself

1solidFill in the machine state

sh takes an instruction page fault on its first text page. The load reads a block that is not in the buffer cache, so virtio_disk_rw has queued the request and is about to sleep, inside its own critical section (kernel/virtio_disk.c:288). Fill in the hart’s state at that line.

kernel/virtio_disk.c

disk.avail->idx += 1; // not % NUM ...
281
io_fence();
283
*R(VIRTIO_MMIO_QUEUE_NOTIFY) = 0; // value is queue number
285
// Wait for virtio_disk_intr() to say request has finished.
while (b->disk == 1) {
  sleep_prepare(b);
  release(&disk.vdisk_lock);
  sleep();
  acquire(&disk.vdisk_lock);
}
293
disk.info[idx[0]].b = 0;
free_chain(idx[0]);

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

2solidChoose one

The prefault is missing from sys_read. dexectest locked reads from a pipe into a data page that is not loaded yet. Its blocks are not in the buffer cache. What happens?

panic: sched lockspanic: acquire, because ilock takes a lock already heldThe read works, a little slower.The read returns -1.

5A program reads its own file

A program opens its own executable and calls read(fd, buf, 4096), where buf is in a data page it has not touched yet. Follow the call through fileread and readi in a kernel that loads pages inside copyout and has no prefault. Which locks does the process hold when the copy needs the page, and what does the load then try to take? What about two programs, each reading the other’s file?

The reference design

fileread holds the inode lock of the file being read, which here is the program’s own file, and readi holds the lock of the buffer it is copying from. The copy reaches vmfault, the load calls ilock on p->exe, the very same inode, and acquiresleep waits for the lock to be released, by itself. The process sleeps forever. Nothing panics, kill cannot help (it makes the process runnable, and acquiresleep goes back to sleep), and anyone else who needs that file waits behind it. If the inode lock were somehow skipped, the buffer lock would deadlock only when the block being copied from is the block the load needs (a read into the page that holds that very part of the file). In selfread they differ: the copy holds the block at file offset 0, and the load of 0xc000 needs file offset 0x6000 + 0x7000 = 0xd000. Clinic 6 shows the hang and the sleeping process’s stack.

Two programs that read each other’s files deadlock the same way, in a cycle: process A reads B’s program file, so it holds that inode’s lock, and its copy needs a page of A’s own program, so it waits for A’s file’s lock; process B does the mirror image. Each holds what the other needs, an ABBA deadlock between two sleep-locks. A run on a kernel without the prefault, with two copies of one program (abA, abB), each reading the other’s file into its own untouched data, hung in the first round; gdb showed abA (pid 4) sleeping on inode 28’s lock, held by pid 5, and abB (pid 5) sleeping on inode 29’s lock, held by pid 4. On the reference branch the same program ran 10 rounds without trouble.

The prefault from the previous question removes every case at once: sys_read loads the buffer’s program pages before fileread takes any lock, so the copy never loads. That is why the reference calls it from the system-call layer and not inside the pipe or console code: it is the last point before any lock, spinlock or sleep-lock. Detecting the self-deadlock instead (a check in acquiresleep for lk->pid == myproc()->pid) would only turn a hang into a panic; the read is legitimate and must work.

(Linux meets the same problem when write() copies from a buffer that is memory-mapped from the file being written, and solves it the same way: fault the user pages in before taking the locks, then copy.)

Check yourself

1solidChoose one

Without the prefault, dexectest selfread reads its own file into a data page it has not touched. What does the console show?

panic: acquirepanic: sched locksdexectest: selfread: FAIL, because read returns -1Nothing more: dexectest never finishes, and the prompt never comes back.

2deepTrue or false, and why

True or false: after sys_read has loaded the buffer’s program pages, one of them could be unmapped again before fileread copies into it, so the copy still needs the load path as a fallback.

TrueFalse

Why?

The page is locked in memory by the prefault.Only the process itself can unmap its pages (sbrk, exec, exit), and it is busy in this system call.Interrupts are off during the copy, so nothing can run.

6The file changes under a running program

The program’s file is unlinked while it runs. Or truncated. Or rewritten. What happens in each case, with the design so far, and what should happen? And look again at kexit dropping p->exe: what is special about that particular iput?

The reference design

Unlinked: the process holds a reference, so iput does not free anything until that reference goes. Pages keep loading from the unlinked file. When the last process running it exits, its iput in kexit is the last one, the inode has nlink 0, and iput truncates and frees it: itrunc → bfree → log_write. That is the special case: the only time the iput of p->exe writes to the disk, and the reason it must be inside the transaction. Outside one, log_write panics with log_write outside of trans (clinic 5). A bug that only shows when a running program’s file was deleted is invisible to usertests.

Truncated (open with O_TRUNC): the next load of a page that is not loaded yet asks readi for bytes the file no longer has and gets fewer. The page cannot be built, so loadpage frees it and fails, vmfault returns 0, and usertrap kills the process. (A system call that needed that page fails instead.) Truncation never makes a process read another file’s data: the blocks were freed through the inode, so the inode no longer points at them. dexectest truncate checks the kill.

Rewritten: pages already loaded keep their old contents, pages loaded later come from the new contents. A program can end up running a mix of two versions. The reference accepts this and documents it; dexectest modify checks that a running helper sees a value written into its file after it started. Real systems close the hole by refusing to open a running program’s file for writing (ETXTBSY), or by giving each executable mapping a private copy of a page when the file changes; both are stretch goals.

Two checks move into kexec, because uvmalloc and loadseg used to make them without saying so. The original kernel noticed a truncated or corrupt program when loadseg's readi came up short, and exec failed; the reference checks, while the inode is locked, that the file is long enough to hold every segment’s bytes (ph.off + ph.filesz <= ip->size). And the original kernel could never accept a segment that ends absurdly high: uvmalloc ran out of memory long before, and exec returned -1. Without that implicit limit a crafted ELF whose data segment ends past MAXVA makes the stack setup panic in walk, and one whose segment ends just below the trampoline makes it panic with mappages: remap. The reference refuses any segment that ends above TRAPFRAME - (USERSTACK + 1) * PGSIZE, which leaves room for the guard page and the stack. One difference remains, by design: a segment with a huge bss that does fit (4 GiB, say) now execs, since nothing is allocated until it is touched; the original kernel refused it for lack of memory.

Check yourself

1solidChoose one

A kernel has every other part of this lab right, but kexit drops p->exe after end_op instead of before it. When does it go wrong?

Only when the exiting process holds the last reference to a program file that was unlinked while it ran: panic: log_write outside of trans.At the next boot: the file system is corrupt because the free was not logged.Never: iput takes care of its own transaction.At every exit, with panic: log_write outside of trans.

2solidMatch the pairs

A helper program is running from file dxcopy and has not yet touched page 7 of its data. Match what happens to the file with what the helper sees when it then touches page 7, on the reference branch.

dxcopy is unlinkeddxcopy is truncated to 0 bytesa new value is written into page 7’s bytes in dxcopythe same three, on the original kernel

7What else has to learn about the new state?

Three more places see the new state of a process. kfork: a child of a demand-paged process. growproc with a negative size: sbrk(-n) below the end of the image, then sbrklazy(n) to take the addresses back. And usertrap itself, which reads scause, sepc and stval several times: is that still safe now that the fault handler can sleep?

Check yourself

1deepChoose one

init (pid 1) takes its first instruction page fault on hart 1, with scause 12 and stval 0xbc. The load reads three blocks from the disk, and init waits for each. Right after the read, back on hart 1, what did gdb read from the scause CSR?

0, because the hart was idle0x8000000000000009, a supervisor external interrupt12, because the CSR belongs to the process12, because interrupts are off in the fault handler

2solidTrue or false, and why

True or false: a child forked before its parent touched page 3 of big[] gets page 3 from its parent when it touches it.

TrueFalse

Why?

The child loads it from the file through its own reference to the executable.The child gets a zero page from the lazy heap code.The parent is asked to load it and share it.

8How do you know it works, and what does usertests think?

usertests counts the free pages before its tests and after, and fails if pages were lost (user/usertests.c:3476, user/usertests.c:3500). What will it report on the demand-paged kernel, and is it right? And how can a test program show, from user space, that a page is loaded only when touched?

Check yourself

1warm-upType a number

On the reference branch, dexectest lazy counts free pages, reads one int from each of two untouched pages of big[], and counts again. How many free pages did the two reads cost?

decimal, 0x hex or 0b binary

3. Build it

Start.

git checkout -b my-12 06aad25

Add the test program first: copy the spec’s list of checks into user/dexectest.c and add $U/_dexectest\ to UPROGS in the Makefile. On the unmodified kernel lazy, truncate and modify print FAIL (it loads everything at exec, so nothing that happens later can matter) and the rest print OK: that is the test working.

Milestones, in an order that keeps the system bootable after each one. Until the switch in milestone 7, exec still loads everything, so every new piece can be tested by the existing suite before it carries any weight.

Keep the file. p->exe in struct proc; kexec keeps namei's reference and drops the old program’s inside its transaction; kfork duplicates it; kexit drops it inside the transaction it already has. Test: usertests -q.
Record the segments. A small table in struct proc, filled by kexec, copied by kfork. Test: it boots.
The loader. A function that, given a process and a page address, finds the segment, allocates and zeroes a page, reads the file’s part of it with readi under ilock, and maps it. Nothing calls it yet. Test: it compiles.
Route faults to it. In vmfault, before the zero-page code: below the end of the image, call the loader. Then make usertrap read scause and stval once, into locals, and accept scause 12 as well. Test: usertests -q (no program page is ever missing yet, so nothing changes).
Load before locking. A function that loads the program pages of a user range, called from sys_read, sys_write and sys_wait before they take any lock. Test: usertests -q.
Fix usertests’ leak check so that it loads its own image before the first count.
Flip the switch. kexec stops calling uvmalloc and loadseg for segments and checks that the file holds each segment’s bytes instead. Test: dexectest, then usertests -q, then dexectest again.
sbrk below the image. Cut the segment table in growproc when the process shrinks. Test: dexectest shrink.

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

A panic at boot right after hart 2 starting means init died: look at the usertrap() line. scause 0xc is a fetch nobody handled; 0x2 at sepc = the entry point means the page was mapped but its bytes are wrong.
Print every load while you build it: printk("load %s %d va %p\n", p->name, p->pid, va). The first lines of a boot should be init loading 0x0, then init’s child loading 0x1000 inside exec.
A hang with idle harts: attach gdb, list proc[] with their state and chan, and compare a SLEEPING process’s chan with the addresses of inode and buffer locks. To see a sleeping process’s kernel stack, set $sp, $s0 and $pc from its p->context (sp, s0, ra) on a halted hart, run bt, and put the registers back.
panic: sched locks: break on panic and run bt; look for a lock-holding function (piperead, consoleread, kwait) above copyout/copyin and a disk wait below.

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.

1usertrap does not handle instruction page faults

Everything else is in place, but the fault branch in usertrap still accepts only loads and stores:

-  } else if ((scause == 15 || scause == 13 || scause == 12) &&
+  } else if ((scause == 15 || scause == 13) &&
              vmfault(p->pagetable, p->sz, stval, (scause == 15) ? 0 : 1) != 0) {

What happened when we ran it

xv6 kernel is booting

hart 2 starting
hart 1 starting
usertrap(): unexpected scause 0xc pid=1
            sepc=0xbc stval=0xbc
panic: init exiting

2The page is zeroed after the file data is read

The memset moves below the read, as if zeroing were a final cleanup:

   if ((mem = kalloc()) == 0)
     return 0;
-  memset(mem, 0, PGSIZE);
   off = va - s->va;
   if (off < s->filesz) {
     [...]
     iunlock(p->exe);
   }
+  memset(mem, 0, PGSIZE);
   if (mappages(p->pagetable, va, PGSIZE, (uint64)mem,

What happened when we ran it

xv6 kernel is booting

hart 2 starting
hart 1 starting
usertrap(): unexpected scause 0x2 pid=1
            sepc=0xbc stval=0x0
panic: init exiting

3The page is not zeroed at all

The memset is gone: readi fills the part of the page the file supplies, and the rest keeps whatever kalloc left there.

   if ((mem = kalloc()) == 0)
     return 0;
-  // zero first: what the file does not supply (the bss, the end
-  // of the last page) must read as 0, not as kalloc's junk.
-  memset(mem, 0, PGSIZE);
   off = va - s->va;

What happened when we ran it

xv6 kernel is booting

hart 1 starting
hart 2 starting
init: starting sh
$ echo hi
usertrap(): unexpected scause 0xd pid=3
            sepc=0x11b4 stval=0x505050505050505
$ dexectest
usertrap(): unexpected scause 0xd pid=4
            sepc=0x11b4 stval=0x505050505050505
$ usertests -q
usertrap(): unexpected scause 0xd pid=5
            sepc=0x11b4 stval=0x505050505050505
$

4fork shares the executable without taking a reference

kfork copies the pointer, as if the child could borrow the parent’s reference:

   np->cwd = idup(p->cwd);
-  np->exe = idup(p->exe); // the child runs the same program
+  np->exe = p->exe;

What happened when we ran it

xv6 kernel is booting

hart 1 starting
hart 2 starting
init: starting sh
$ echo hi
hi
$ ls
.              1 1 1024
[...]
dexectest      2 23 147072
console        3 24 0
$ dexectest
dexectest: lazy: touching 2 data pages took 2 free pages
dexectest: lazy: OK
panic: ilock

# another boot of the same kernel, `dexectest fork` alone, gdb breakpoint on panic:
#0  panic (s=s@entry=0x80007468 "ilock") at kernel/printk.c:139
#1  0x000000008000336a in ilock (ip=<optimized out>) at kernel/fs.c:301
#2  0x0000000080004d42 in loadpage (p=p@entry=0x800101e0 <proc+1072>, va=va@entry=36864) at kernel/exec.c:232
#3  0x0000000080001554 in vmfault (pagetable=0x87f25000, psz=<optimized out>, va=va@entry=36864, read=read@entry=1) at kernel/vm.c:473
#4  0x000000008000279e in usertrap () at kernel/trap.c:77
#5  0x0000003ffffff09c in ?? ()
$1 = 3
$2 = "dexectest\000\000\000\000\000\000"
$3 = {dev = 1, inum = 23, ref = 0, lock = {locked = 0, lk = {locked = 0, name = 0x80007568 "sleep lock", cpu = 0x0}, name = 0x80007448 "inode", pid = 0}, valid = 1, type = 2, major = 0, minor = 0, nlink = 1, size = 147072, addrs = {1007, 1008, 1009, 1010, 1011, 1012, 1013, 1014, 1015, 1016, 1017, 1018, 1019}}

# a third boot: usertests -q
[...]
ALL TESTS PASSED

5exit drops the executable outside the transaction

kexit closes the transaction first and drops p->exe afterwards:

   begin_op();
   iput(p->cwd);
-  iput(p->exe); // may free an unlinked program: needs the transaction
   end_op();
+  iput(p->exe);
   p->cwd = 0;

What happened when we ran it

xv6 kernel is booting

hart 1 starting
hart 2 starting
init: starting sh
$ usertests -q
usertests starting
test copyin: OK
[...]
test unlinkcwd: OK
ALL TESTS PASSED
$ dexectest unlink
panic: log_write outside of trans

# another boot, `dexectest unlink`, gdb breakpoint on panic:
#0  panic (s=s@entry=0x80007548 "log_write outside of trans") at kernel/printk.c:139
#1  0x0000000080003fe4 in log_write (b=b@entry=0x8001c960 <bcache+17816>) at kernel/log.c:232
#2  0x0000000080002ee2 in bfree (dev=<optimized out>, b=<optimized out>) at kernel/fs.c:105
#3  0x0000000080003452 in itrunc (ip=ip@entry=0x80020d68 <itable+704>) at kernel/fs.c:472
#4  0x000000008000352a in iput (ip=0x80020d68 <itable+704>) at kernel/fs.c:365
#5  0x0000000080002182 in kexit (status=0) at kernel/proc.c:349
#6  0x0000000080002a20 in sys_exit () at kernel/sysproc.c:15
#7  0x00000000800029dc in syscall () at kernel/syscall.c:146
#8  0x0000000080002762 in usertrap () at kernel/trap.c:73
#9  0x0000003ffffff09c in ?? ()
$1 = 1
$2 = 1
$3 = 4
$4 = "dxcopy\000\000t\000\000\000\000\000\000"

6read() copies into an unloaded page while holding locks

There is no prefault: sys_read, sys_write and sys_wait go straight to the code that copies, and the copy loads a missing page wherever it happens to be:

   if (argfd(0, 0, &f) < 0)
     return -1;
-  // load the buffer's program pages now: fileread holds locks
-  // while it copies, and loading a page needs to sleep.
-  if (n > 0 && uvmprefault(myproc(), p, n) < 0)
-    return -1;
   return fileread(f, p, n);

(and the same three lines in sys_write, one in sys_wait.)

What happened when we ran it

xv6 kernel is booting

hart 2 starting
hart 1 starting
init: starting sh
$ dexectest locked
panic: sched locks

# gdb breakpoint on panic, same boot:
#0  panic (s=s@entry=0x800071a8 "sched locks") at kernel/printk.c:139
#1  0x0000000080001fb2 in sched () at kernel/proc.c:494
#2  0x0000000080002052 in sleep () at kernel/proc.c:575
#3  0x0000000080005d24 in virtio_disk_rw (b=b@entry=0x8001e7c8 <bcache+25600>, write=write@entry=0) at kernel/virtio_disk.c:290
#4  0x0000000080002d54 in bread (dev=1, blockno=1068) at kernel/bio.c:98
#5  0x0000000080003788 in readi (ip=0x80020ce0 <itable+568>, user_dst=user_dst@entry=0, dst=dst@entry=2280865792, off=61440, n=n@entry=4096) at kernel/fs.c:524
#6  0x0000000080004d56 in loadpage (p=p@entry=0x800101e0 <proc+1072>, va=va@entry=57344) at kernel/exec.c:235
#7  0x0000000080001554 in vmfault (pagetable=pagetable@entry=0x87f25000, psz=psz@entry=110592, va=va@entry=57344, read=read@entry=1) at kernel/vm.c:473
#8  0x00000000800016a8 in copyin (pagetable=0x87f25000, psz=110592, dst=dst@entry=0x3fffff9ebf "", srcva=srcva@entry=57344, len=len@entry=1) at kernel/vm.c:391
#9  0x0000000080004758 in pipewrite (pi=0x87f44000, addr=57344, n=8) at kernel/pipe.c:96
#10 0x0000000080004498 in filewrite (f=0x80022700 <ftable+104>, addr=57344, n=8) at kernel/file.c:143
#11 0x000000008000508a in sys_write () at kernel/sysfile.c:97
#12 0x00000000800029dc in syscall () at kernel/syscall.c:146
#13 0x0000000080002762 in usertrap () at kernel/trap.c:73
#14 0x0000003ffffff09c in ?? ()
$1 = 2
$2 = 1
$3 = 3
$4 = "dexectest\000\000\000\000\000\000"
  Id   Target Id                    Frame
  1    Thread 1.1 (CPU#0 [running]) acquire (lk=lk@entry=0x800101e0 <proc+1072>) at kernel/spinlock.c:37
  2    Thread 1.2 (CPU#1 [running]) acquire (lk=lk@entry=0x800101e0 <proc+1072>) at kernel/spinlock.c:37
* 3    Thread 1.3 (CPU#2 [running]) panic (s=s@entry=0x800071a8 "sched locks") at kernel/printk.c:139

# another boot: `dexectest selfread`, which never returns
$ dexectest selfread
# (nothing more; after a while gdb was attached to the hung kernel)
  Id   Target Id                    Frame
* 1    Thread 1.1 (CPU#0 [halted ]) s_sstatus (x=2) at kernel/riscv.h:67
  2    Thread 1.2 (CPU#1 [halted ]) s_sstatus (x=2) at kernel/riscv.h:67
  3    Thread 1.3 (CPU#2 [halted ]) s_sstatus (x=2) at kernel/riscv.h:67
[...]
proc[0] pid 1 SLEEPING init chan 0x8000fdb0 <proc>
proc[1] pid 2 SLEEPING sh chan 0x8000ffc8 <proc+536>
proc[2] pid 3 SLEEPING dexectest chan 0x80020cf0 <itable+584>
  exe inum 23 ref 2 lock.locked 1 lock.pid 3 &exe->lock 0x80020cf0 <itable+584>
[...]
  kernel stack of pid 3 (from p->context):
#0  r_tp () at kernel/riscv.h:344
#1  cpuid () at kernel/proc.c:67
#2  mycpu () at kernel/proc.c:76
#3  sched () at kernel/proc.c:502
#4  0x0000000080002052 in sleep () at kernel/proc.c:575
#5  0x00000000800040ce in acquiresleep (lk=lk@entry=0x80020cf0 <itable+584>) at kernel/sleeplock.c:28
#6  0x0000000080003336 in ilock (ip=0x80020ce0 <itable+568>) at kernel/fs.c:303
#7  0x0000000080004d42 in loadpage (p=p@entry=0x800101e0 <proc+1072>, va=va@entry=49152) at kernel/exec.c:234
#8  0x0000000080001554 in vmfault (pagetable=0x87f25000, pagetable@entry=0x1, psz=psz@entry=0, va=va@entry=49152, read=read@entry=0) at kernel/vm.c:473
#9  0x00000000800015e2 in copyout (pagetable=0x1, psz=0, dstva=dstva@entry=49152, src=src@entry=0x800199f0 <bcache+5672> "\177ELF\002\001\001", len=len@entry=1024) at kernel/vm.c:357
#10 0x00000000800023c0 in either_copyout (user_dst=user_dst@entry=1, dst=dst@entry=49152, src=src@entry=0x800199f0 <bcache+5672>, len=len@entry=1024) at kernel/proc.c:657
#11 0x000000008000375a in readi (ip=0x80020ce0 <itable+568>, user_dst=user_dst@entry=1, dst=dst@entry=49152, off=0, n=n@entry=4096) at kernel/fs.c:526
#12 0x00000000800043b0 in fileread (f=0x800226d8 <ftable+64>, addr=49152, n=4096) at kernel/file.c:122
#13 0x0000000080005042 in sys_read () at kernel/sysfile.c:81
#14 0x00000000800029dc in syscall () at kernel/syscall.c:146
#15 0x0000000080002762 in usertrap () at kernel/trap.c:73
#16 0x0000003ffffff09c in ?? ()

Two different failures from one missing rule, “load before you lock”.

dexectest locked: a sleep under a spinlock. The parent’s first copy is a write into a pipe from page 8 of big[] (va 57344 = 0xe000), which it has never touched. pipewrite holds pi->lock and copies byte by byte with copyin (kernel/pipe.c:96). The first byte finds the page missing, vmfault calls loadpage, readi needs block 1068 (file offset 0xf000), which is not in the buffer cache, and virtio_disk_rw goes to sleep. sleep takes p->lock; sched counts noff 2 (pi->lock and p->lock) and panics. The other two harts are stuck in acquire on proc+1072, this process’s p->lock, which the panicking hart will never release. Had the block been in the cache, nothing would have slept and the write would have worked: a bug that depends on the cache. The read from the pipe and the wait that follow in the same check would fail the same way (piperead holds pi->lock, kwait holds two spinlocks); a kernel with only sys_write's prefault removed also printed panic: sched locks for this check.

dexectest selfread: a process waiting for itself. dexectest reads its own file into page 6 of big[] (va 49152 = 0xc000). fileread locks inode 23, the program’s own file, and readi copies the first block with either_copyout, holding that block’s buffer (its first bytes, \177ELF, are visible in src). The copy needs the page; loadpage calls ilock on p->exe, the same inode 23, and acquiresleep sleeps until the holder lets go. The holder is pid 3 itself: lock.pid 3, and the process’s chan is the address of that lock. It will sleep forever. No panic, no message; the harts sit idle in the scheduler and the shell never prints another prompt.

(In both backtraces some argument values of vmfault and copyout are stale registers in this optimized build, for example pagetable=0x1; the addresses and line numbers are what matter. The selfread stack was reconstructed by setting a halted hart’s sp, s0 and pc from the sleeping process’s saved context, which is why its top frames are sched and mycpu.)

Both are fixed by the same three call sites: sys_read, sys_write and sys_wait load the program pages of the user buffer before any lock is taken.

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

5b32942 Keep a reference to the executable in each process
kernel/exec.c
@@ -30,9 +30,9 @@ kexec(char *path, char **argv)
3030 char *s, *last;
3131 int i, off;
3232 uint64 argc, sz = 0, sp, ustack[MAXARG], stackbase;
3333 struct elfhdr elf;
34 struct inode *ip;
34 struct inode *ip, *oldexe;
3535 struct proghdr ph;
3636 pagetable_t pagetable = 0, oldpagetable;
3737 struct proc *p = myproc();
3838
@@ -75,11 +75,10 @@ kexec(char *path, char **argv)
7575 sz = sz1;
7676 if (loadseg(pagetable, ph.vaddr, ip, ph.off, ph.filesz) < 0)
7777 goto bad;
7878 }
79 iunlockput(ip);
80 end_op();
81 ip = 0;
79 // ip stays locked, and the transaction open, until the new
80 // image is committed below.
8281
8382 p = myproc();
8483 uint64 oldsz = p->sz;
8584
@@ -130,12 +129,19 @@ kexec(char *path, char **argv)
130129 safestrcpy(p->name, last, sizeof(p->name));
131130
132131 // Commit to the user image.
133132 oldpagetable = p->pagetable;
133 oldexe = p->exe;
134134 p->pagetable = pagetable;
135135 p->sz = sz;
136 // keep namei's reference: the image's pages come from ip.
137 p->exe = ip;
136138 p->trapframe->epc = elf.entry; // initial program counter = ulib.c:start()
137139 p->trapframe->sp = sp; // initial stack pointer
140 iunlock(ip);
141 if (oldexe)
142 iput(oldexe); // inside the transaction: it may free the file
143 end_op();
138144 proc_freepagetable(oldpagetable, oldsz);
139145
140146 return argc; // this ends up in a0, the first argument to main(argc, argv)
141147
kernel/proc.c
@@ -285,8 +285,9 @@ kfork(void)
285285 for (i = 0; i < NOFILE; i++)
286286 if (p->ofile[i])
287287 np->ofile[i] = filedup(p->ofile[i]);
288288 np->cwd = idup(p->cwd);
289 np->exe = idup(p->exe); // the child runs the same program
289290
290291 safestrcpy(np->name, p->name, sizeof(p->name));
291292
292293 pid = np->pid;
@@ -340,10 +341,12 @@ kexit(int status)
340341 }
341342
342343 begin_op();
343344 iput(p->cwd);
345 iput(p->exe); // may free an unlinked program: needs the transaction
344346 end_op();
345347 p->cwd = 0;
348 p->exe = 0;
346349
347350 acquire(&wait_lock);
348351
349352 // Give any children to init.
kernel/proc.h
@@ -99,6 +99,7 @@ struct proc {
9999 struct trapframe *trapframe; // data page for trampoline.S
100100 struct context context; // swtch() here to run process
101101 struct file *ofile[NOFILE]; // Open files
102102 struct inode *cwd; // Current directory
103 struct inode *exe; // Executable file the image comes from
103104 char name[16]; // Process name (debugging)
104105};
5432ffa Record the program's segments in exec
kernel/exec.c
@@ -32,8 +32,10 @@ kexec(char *path, char **argv)
3232 uint64 argc, sz = 0, sp, ustack[MAXARG], stackbase;
3333 struct elfhdr elf;
3434 struct inode *ip, *oldexe;
3535 struct proghdr ph;
36 struct seg seg[NSEG];
37 int nseg = 0;
3638 pagetable_t pagetable = 0, oldpagetable;
3739 struct proc *p = myproc();
3840
3941 begin_op();
@@ -67,15 +69,24 @@ kexec(char *path, char **argv)
6769 if (ph.vaddr + ph.memsz < ph.vaddr)
6870 goto bad;
6971 if (ph.vaddr % PGSIZE != 0)
7072 goto bad;
73 if (ph.vaddr < sz || nseg == NSEG) // overlapping, or too many
74 goto bad;
7175 uint64 sz1;
7276 if ((sz1 = uvmalloc(pagetable, sz, ph.vaddr + ph.memsz,
7377 flags2perm(ph.flags))) == 0)
7478 goto bad;
7579 sz = sz1;
7680 if (loadseg(pagetable, ph.vaddr, ip, ph.off, ph.filesz) < 0)
7781 goto bad;
82 // remember where the segment's bytes are in the file.
83 seg[nseg].va = ph.vaddr;
84 seg[nseg].memsz = ph.memsz;
85 seg[nseg].off = ph.off;
86 seg[nseg].filesz = ph.filesz;
87 seg[nseg].perm = flags2perm(ph.flags);
88 nseg++;
7889 }
7990 // ip stays locked, and the transaction open, until the new
8091 // image is committed below.
8192
@@ -134,8 +145,10 @@ kexec(char *path, char **argv)
134145 p->pagetable = pagetable;
135146 p->sz = sz;
136147 // keep namei's reference: the image's pages come from ip.
137148 p->exe = ip;
149 memmove(p->seg, seg, sizeof(seg));
150 p->nseg = nseg;
138151 p->trapframe->epc = elf.entry; // initial program counter = ulib.c:start()
139152 p->trapframe->sp = sp; // initial stack pointer
140153 iunlock(ip);
141154 if (oldexe)
kernel/param.h
@@ -5,8 +5,9 @@
55#define NINODE 50 // maximum number of active i-nodes
66#define NDEV 10 // maximum major device number
77#define ROOTDEV 1 // device number of file system root disk
88#define MAXARG 32 // max exec arguments
9#define NSEG 4 // max loadable segments per program
910#define MAXOPBLOCKS 10 // max # of blocks any FS op writes
1011#define LOGBLOCKS (MAXOPBLOCKS * 3) // max data blocks in on-disk log
1112#define NBUF (MAXOPBLOCKS * 3) // size of disk block cache
1213#define FSSIZE 2000 // size of file system in blocks
kernel/proc.c
@@ -286,8 +286,10 @@ kfork(void)
286286 if (p->ofile[i])
287287 np->ofile[i] = filedup(p->ofile[i]);
288288 np->cwd = idup(p->cwd);
289289 np->exe = idup(p->exe); // the child runs the same program
290 memmove(np->seg, p->seg, sizeof(p->seg));
291 np->nseg = p->nseg;
290292
291293 safestrcpy(np->name, p->name, sizeof(p->name));
292294
293295 pid = np->pid;
kernel/proc.h
@@ -77,8 +77,17 @@ struct trapframe {
7777};
7878
7979enum procstate { UNUSED, USED, SLEEPING, RUNNABLE, RUNNING, ZOMBIE };
8080
81// A loadable segment of the running program, recorded by exec.
82struct seg {
83 uint64 va; // first virtual address, page-aligned
84 uint64 memsz; // bytes in memory
85 uint64 off; // offset of the segment in the file
86 uint64 filesz; // bytes that come from the file; the rest is zero
87 int perm; // PTE_X and/or PTE_W
88};
89
8190// Per-process state
8291struct proc {
8392 struct spinlock lock;
8493
@@ -100,6 +109,8 @@ struct proc {
100109 struct context context; // swtch() here to run process
101110 struct file *ofile[NOFILE]; // Open files
102111 struct inode *cwd; // Current directory
103112 struct inode *exe; // Executable file the image comes from
113 struct seg seg[NSEG]; // Its loadable segments, by address
114 int nseg; // Number of segments in seg[]
104115 char name[16]; // Process name (debugging)
105116};
2b8f12d Add loadpage to read one page of the program on demand
kernel/defs.h
@@ -24,8 +24,10 @@ void consoleintr(int);
2424void consputc(int);
2525
2626// exec.c
2727int kexec(char*, char**);
28uint64 imgend(struct proc*);
29uint64 loadpage(struct proc*, uint64);
2830
2931// file.c
3032struct file* filealloc(void);
3133void fileclose(struct file*);
kernel/exec.c
@@ -192,4 +192,63 @@ loadseg(pagetable_t pagetable, uint64 va, struct inode *ip, uint offset,
192192 }
193193
194194 return 0;
195195}
196
197// The end of p's program image. Addresses below it belong to the
198// program's segments; the stack and the heap lie above it.
199uint64
200imgend(struct proc *p)
201{
202 struct seg *s;
203
204 if (p->nseg == 0)
205 return 0;
206 s = &p->seg[p->nseg - 1];
207 return s->va + s->memsz;
208}
209
210// Read the page at va of p's program image from the executable
211// and map it with its segment's permissions. va must be
212// page-aligned, below imgend(p), and not mapped. Called by
213// vmfault. May sleep, so the caller must hold no spinlock (and
214// not the executable's inode lock). Returns the page's physical
215// address, or 0 if va is in no segment or the page can't be loaded.
216uint64
217loadpage(struct proc *p, uint64 va)
218{
219 struct seg *s;
220 uint64 off;
221 uint n;
222 char *mem;
223
224 for (s = p->seg; s < &p->seg[p->nseg]; s++)
225 if (va >= s->va && va < s->va + s->memsz)
226 break;
227 if (s == &p->seg[p->nseg])
228 return 0; // a hole between segments
229
230 if ((mem = kalloc()) == 0)
231 return 0;
232 // zero first: what the file does not supply (the bss, the end
233 // of the last page) must read as 0, not as kalloc's junk.
234 memset(mem, 0, PGSIZE);
235 off = va - s->va;
236 if (off < s->filesz) {
237 n = PGSIZE;
238 if (s->filesz - off < PGSIZE)
239 n = s->filesz - off;
240 ilock(p->exe);
241 if (readi(p->exe, 0, (uint64)mem, s->off + off, n) != n) {
242 iunlock(p->exe); // the file is shorter than the program
243 kfree(mem);
244 return 0;
245 }
246 iunlock(p->exe);
247 }
248 if (mappages(p->pagetable, va, PGSIZE, (uint64)mem,
249 PTE_R | PTE_U | s->perm) != 0) {
250 kfree(mem);
251 return 0;
252 }
253 return (uint64)mem;
254}
d1ec1e5 Let vmfault load missing pages of the program
kernel/vm.c
@@ -451,22 +451,27 @@ copyinstr(pagetable_t pagetable, uint64 psz, char *dst, uint64 srcva,
451451 }
452452}
453453
454454// allocate and map user memory if process is referencing a page
455// that was lazily allocated in sys_sbrk().
455// that was lazily allocated in sys_sbrk(), or a page of the
456// program that exec has not loaded yet.
456457// returns 0 if va is invalid or already mapped, or if
457458// out of physical memory, and physical address if successful.
458459uint64
459460vmfault(pagetable_t pagetable, uint64 psz, uint64 va, int read)
460461{
461462 uint64 mem;
463 struct proc *p = myproc();
462464
463465 if (va >= psz)
464466 return 0;
465467 va = PGROUNDDOWN(va);
466468 if (ismapped(pagetable, va)) {
467469 return 0;
468470 }
471 // text or data of the program: read it from the file.
472 if (pagetable == p->pagetable && va < imgend(p))
473 return loadpage(p, va);
469474 mem = (uint64)kalloc();
470475 if (mem == 0)
471476 return 0;
472477 memset((void *)mem, 0, PGSIZE);
b980265 Read scause and stval before a page fault can sleep
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 (loading a page of the program), and while
55 // this process sleeps other traps 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,14 @@ 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) {
76 } else if ((scause == 15 || scause == 13) &&
77 vmfault(p->pagetable, p->sz, stval, (scause == 13) ? 1 : 0) != 0) {
7478 // page fault on lazily-allocated page
7579 } 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());
80 printk("usertrap(): unexpected scause 0x%lx pid=%d\n", scause, p->pid);
81 printk(" sepc=0x%lx stval=0x%lx\n", p->trapframe->epc, stval);
7882 setkilled(p);
7983 }
8084
8185 if (killed(p))
f85c3e4 Handle instruction page faults in usertrap
kernel/trap.c
@@ -72,11 +72,12 @@ usertrap(void)
7272
7373 syscall();
7474 } else if ((which_dev = devintr()) != 0) {
7575 // ok
76 } else if ((scause == 15 || scause == 13) &&
77 vmfault(p->pagetable, p->sz, stval, (scause == 13) ? 1 : 0) != 0) {
78 // 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 of the
79 // program not loaded yet (12: instruction fetch).
7980 } else {
8081 printk("usertrap(): unexpected scause 0x%lx pid=%d\n", scause, p->pid);
8182 printk(" sepc=0x%lx stval=0x%lx\n", p->trapframe->epc, stval);
8283 setkilled(p);
82d7f5b Load a system call's program pages before taking locks
kernel/defs.h
@@ -171,8 +171,9 @@ int copyout(pagetable_t, uint64, uint64, char *, uint64);
171171int copyin(pagetable_t, uint64, char *, uint64, uint64);
172172int copyinstr(pagetable_t, uint64, char *, uint64, uint64);
173173int ismapped(pagetable_t, uint64);
174174uint64 vmfault(pagetable_t, uint64, uint64, int);
175int uvmprefault(struct proc*, uint64, uint64);
175176
176177// plic.c
177178void plicinit(void);
178179void plicinithart(void);
kernel/sysfile.c
@@ -75,8 +75,12 @@ sys_read(void)
7575 argaddr(1, &p);
7676 argint(2, &n);
7777 if (argfd(0, 0, &f) < 0)
7878 return -1;
79 // load the buffer's program pages now: fileread holds locks
80 // while it copies, and loading a page needs to sleep.
81 if (n > 0 && uvmprefault(myproc(), p, n) < 0)
82 return -1;
7983 return fileread(f, p, n);
8084}
8185
8286uint64
@@ -89,8 +93,11 @@ sys_write(void)
8993 argaddr(1, &p);
9094 argint(2, &n);
9195 if (argfd(0, 0, &f) < 0)
9296 return -1;
97 // as in sys_read: filewrite copies in while holding locks.
98 if (n > 0 && uvmprefault(myproc(), p, n) < 0)
99 return -1;
93100
94101 return filewrite(f, p, n);
95102}
96103
kernel/sysproc.c
@@ -32,8 +32,11 @@ uint64
3232sys_wait(void)
3333{
3434 uint64 p;
3535 argaddr(0, &p);
36 // kwait copies the status out holding spinlocks.
37 if (p != 0 && uvmprefault(myproc(), p, sizeof(int)) < 0)
38 return -1;
3639 return kwait(p);
3740}
3841
3942uint64
kernel/vm.c
@@ -481,8 +481,32 @@ vmfault(pagetable_t pagetable, uint64 psz, uint64 va, int read)
481481 }
482482 return mem;
483483}
484484
485// Load the pages of p's program in [va, va+n) that are not mapped
486// yet. A system call that copies to or from user memory while it
487// holds locks calls this first, with no locks held: loading a page
488// of the program sleeps and locks the executable's inode.
489// Returns -1 if a page of the program in the range can't be loaded.
490int
491uvmprefault(struct proc *p, uint64 va, uint64 n)
492{
493 uint64 a, end;
494
495 end = imgend(p);
496 if (n == 0 || va >= end)
497 return 0;
498 if (n > end - va)
499 n = end - va;
500 for (a = PGROUNDDOWN(va); a < va + n; a += PGSIZE) {
501 if (ismapped(p->pagetable, a))
502 continue;
503 if (vmfault(p->pagetable, p->sz, a, 1) == 0)
504 return -1;
505 }
506 return 0;
507}
508
485509int
486510ismapped(pagetable_t pagetable, uint64 va)
487511{
488512 pte_t *pte = walk(pagetable, va, 0);
1d1a268 Make usertests load its own image before counting free pages
user/usertests.c
@@ -3467,13 +3467,29 @@ countfree()
34673467 sbrk(-((uint64)sbrk(0) - sz0));
34683468 return n;
34693469}
34703470
3471// read one byte of every page of this program's image (text, data
3472// and bss), so that a kernel that loads the image on demand has
3473// loaded all of it.
3474void
3475touchimage(void)
3476{
3477 extern char end[];
3478
3479 for (uint64 a = 0; a < (uint64)end; a += PGSIZE)
3480 (void)*(volatile char *)a;
3481}
3482
34713483int
34723484drivetests(int quick, int continuous, char *justone)
34733485{
34743486 do {
34753487 printf("usertests starting\n");
3488 // the tests touch parts of this program that nothing touched
3489 // before; with demand-paged exec that loads pages, which are
3490 // not lost.
3491 touchimage();
34763492 int free0 = countfree();
34773493 int free1 = 0;
34783494 int ntests = 0;
34793495 int n;
1b5d1ed Stop loading the program in exec
kernel/exec.c
@@ -5,10 +5,11 @@
55#include "spinlock.h"
66#include "proc.h"
77#include "defs.h"
88#include "elf.h"
9
10static int loadseg(pde_t *, uint64, struct inode *, uint, uint);
9#include "sleeplock.h"
10#include "fs.h"
11#include "file.h"
1112
1213// map ELF permissions to PTE permission bits.
1314int
1415flags2perm(int flags)
@@ -57,9 +58,10 @@ kexec(char *path, char **argv)
5758
5859 if ((pagetable = proc_pagetable(p)) == 0)
5960 goto bad;
6061
61 // Load program into memory.
62 // Record the program's segments. Their pages are read from ip
63 // when the program first touches them (loadpage).
6264 for (i = 0, off = elf.phoff; i < elf.phnum; i++, off += sizeof(ph)) {
6365 if (readi(ip, 0, (uint64)&ph, off, sizeof(ph)) != sizeof(ph))
6466 goto bad;
6567 if (ph.type != ELF_PROG_LOAD)
@@ -71,15 +73,13 @@ kexec(char *path, char **argv)
7173 if (ph.vaddr % PGSIZE != 0)
7274 goto bad;
7375 if (ph.vaddr < sz || nseg == NSEG) // overlapping, or too many
7476 goto bad;
75 uint64 sz1;
76 if ((sz1 = uvmalloc(pagetable, sz, ph.vaddr + ph.memsz,
77 flags2perm(ph.flags))) == 0)
78 goto bad;
79 sz = sz1;
80 if (loadseg(pagetable, ph.vaddr, ip, ph.off, ph.filesz) < 0)
81 goto bad;
77 if (ph.vaddr + ph.memsz > TRAPFRAME - (USERSTACK + 1) * PGSIZE)
78 goto bad; // no room for the guard page and the stack
79 if (ph.off + ph.filesz < ph.off || ph.off + ph.filesz > ip->size)
80 goto bad; // the file must hold the segment's bytes
81 sz = ph.vaddr + ph.memsz;
8282 // remember where the segment's bytes are in the file.
8383 seg[nseg].va = ph.vaddr;
8484 seg[nseg].memsz = ph.memsz;
8585 seg[nseg].off = ph.off;
@@ -167,34 +167,8 @@ bad:
167167 }
168168 return -1;
169169}
170170
171// Load an ELF program segment into pagetable at virtual address va.
172// va must be page-aligned
173// and the pages from va to va+sz must already be mapped.
174// Returns 0 on success, -1 on failure.
175static int
176loadseg(pagetable_t pagetable, uint64 va, struct inode *ip, uint offset,
177 uint sz)
178{
179 uint i, n;
180 uint64 pa;
181
182 for (i = 0; i < sz; i += PGSIZE) {
183 pa = walkaddr(pagetable, va + i);
184 if (pa == 0)
185 panic("loadseg: address should exist");
186 if (sz - i < PGSIZE)
187 n = sz - i;
188 else
189 n = PGSIZE;
190 if (readi(ip, 0, (uint64)pa, offset + i, n) != n)
191 return -1;
192 }
193
194 return 0;
195}
196
197171// The end of p's program image. Addresses below it belong to the
198172// program's segments; the stack and the heap lie above it.
199173uint64
200174imgend(struct proc *p)
a571e87 Trim the segment table when sbrk shrinks the process
kernel/defs.h
@@ -26,8 +26,9 @@ void consputc(int);
2626// exec.c
2727int kexec(char*, char**);
2828uint64 imgend(struct proc*);
2929uint64 loadpage(struct proc*, uint64);
30void segtrim(struct proc*, uint64);
3031
3132// file.c
3233struct file* filealloc(void);
3334void fileclose(struct file*);
kernel/exec.c
@@ -180,8 +180,28 @@ imgend(struct proc *p)
180180 s = &p->seg[p->nseg - 1];
181181 return s->va + s->memsz;
182182}
183183
184// p has shrunk to sz (sbrk with a negative size). Forget the parts
185// of its segments above sz, page by page, so that memory the
186// process grows into later is zeroed, as before, and is not read
187// from the file.
188void
189segtrim(struct proc *p, uint64 sz)
190{
191 uint64 top = PGROUNDUP(sz);
192 int i;
193
194 for (i = 0; i < p->nseg && p->seg[i].va < top; i++) {
195 struct seg *s = &p->seg[i];
196 if (s->va + s->memsz > top)
197 s->memsz = top - s->va;
198 if (s->filesz > s->memsz)
199 s->filesz = s->memsz;
200 }
201 p->nseg = i; // drop the segments entirely above sz
202}
203
184204// Read the page at va of p's program image from the executable
185205// and map it with its segment's permissions. va must be
186206// page-aligned, below imgend(p), and not mapped. Called by
187207// vmfault. May sleep, so the caller must hold no spinlock (and
kernel/proc.c
@@ -247,8 +247,9 @@ growproc(int n)
247247 return -1;
248248 }
249249 } else if (n < 0) {
250250 sz = uvmdealloc(p->pagetable, sz, sz + n);
251 segtrim(p, sz);
251252 }
252253 p->sz = sz;
253254 return 0;
254255}
c4171a1 Add dexectest, a test program for demand-paged exec
Makefile
@@ -149,8 +149,9 @@ UPROGS=\
149149 $U/_logstress\
150150 $U/_forphan\
151151 $U/_dorphan\
152152 $U/_sync\
153 $U/_dexectest\
153154
154155fs.img: mkfs/mkfs README $(UPROGS)
155156 mkfs/mkfs fs.img README $(UPROGS)
156157
user/dexectest.c
@@ -0,0 +1,481 @@
1//
2// tests for demand-paged exec.
3// each test prints "dexectest: <name>: OK" or "... FAIL".
4// run all: dexectest; run one: dexectest <name>.
5//
6
7#include "kernel/types.h"
8#include "kernel/riscv.h"
9#include "kernel/fcntl.h"
10#include "kernel/elf.h"
11#include "kernel/vm.h"
12#include "user/user.h"
13
14#define NBIG 16 // pages in big[]
15#define PERPAGE (PGSIZE / sizeof(int))
16#define PAGE(k) (k * PERPAGE)
17
18// 16 pages of initialized data. They are part of the file, so after
19// exec each of them is loaded from the file when first touched.
20// Every int is 0x5a5a5a5a except the first of each page, which is
21// 1000 + the page number. Each test touches its own pages first.
22int big[NBIG * PERPAGE] __attribute__((aligned(PGSIZE))) = {
23 [0 ... NBIG * PERPAGE - 1] = 0x5a5a5a5a,
24 [PAGE(0)] = 1000, [PAGE(1)] = 1001, [PAGE(2)] = 1002,
25 [PAGE(3)] = 1003, [PAGE(4)] = 1004, [PAGE(5)] = 1005,
26 [PAGE(6)] = 1006, [PAGE(7)] = 1007, [PAGE(8)] = 1008,
27 [PAGE(9)] = 1009, [PAGE(10)] = 1010, [PAGE(11)] = 1011,
28 [PAGE(12)] = 1012, [PAGE(13)] = 1013, [PAGE(14)] = 1014,
29 [PAGE(15)] = 1015,
30};
31
32// a page of read-only data, in the text segment.
33const char ro[PGSIZE] __attribute__((aligned(PGSIZE))) = "read-only";
34
35// bss: never written, must read as zeros.
36char zeros[2 * PGSIZE];
37
38char *self; // this program's file name, argv[0]
39int failed;
40
41void
42result(char *name, int ok)
43{
44 printf("dexectest: %s: %s\n", name, ok ? "OK" : "FAIL");
45 if (!ok)
46 failed = 1;
47}
48
49// does page k of big[] hold what the file says?
50int
51pageok(int k)
52{
53 int *q = &big[PAGE(k)];
54
55 if (q[0] != 1000 + k)
56 return 0;
57 for (int i = 1; i < PERPAGE; i++)
58 if (q[i] != 0x5a5a5a5a)
59 return 0;
60 return 1;
61}
62
63// count free pages by allocating them all with sbrk.
64int
65countfree(void)
66{
67 char *sz0 = sbrk(0);
68 int n = 0;
69
70 while (sbrk(PGSIZE) != SBRK_ERROR)
71 n++;
72 sbrk(-(sbrk(0) - sz0));
73 return n;
74}
75
76// read this program's ELF header and program headers.
77int
78readphdrs(char *file, struct proghdr *ph, int max)
79{
80 struct elfhdr elf;
81 int fd, n = 0;
82
83 if ((fd = open(file, O_RDONLY)) < 0)
84 return -1;
85 if (read(fd, &elf, sizeof(elf)) != sizeof(elf) || elf.magic != ELF_MAGIC) {
86 close(fd);
87 return -1;
88 }
89 for (int i = 0; i < elf.phnum && n < max; i++) {
90 // read() can't seek: reopen and skip to the i-th header.
91 close(fd);
92 fd = open(file, O_RDONLY);
93 char skip[64];
94 uint64 off = elf.phoff + i * sizeof(struct proghdr);
95 while (off > 0) {
96 int m = off > sizeof(skip) ? sizeof(skip) : off;
97 if (read(fd, skip, m) != m)
98 break;
99 off -= m;
100 }
101 if (read(fd, &ph[n], sizeof(ph[n])) != sizeof(ph[n]))
102 break;
103 if (ph[n].type == ELF_PROG_LOAD)
104 n++;
105 }
106 close(fd);
107 return n;
108}
109
110// file offset of virtual address va, or -1.
111int
112fileoff(char *file, uint64 va)
113{
114 struct proghdr ph[4];
115 int n = readphdrs(file, ph, 4);
116
117 for (int i = 0; i < n; i++)
118 if (va >= ph[i].vaddr && va < ph[i].vaddr + ph[i].filesz)
119 return ph[i].off + (va - ph[i].vaddr);
120 return -1;
121}
122
123// after exec, touching a page of the program costs one page,
124// and only then.
125void
126lazytest(void)
127{
128 volatile int x;
129
130 countfree(); // first call allocates page-table pages; ignore it
131 int before = countfree();
132 x = big[PAGE(1)];
133 x = big[PAGE(2)];
134 int after = countfree();
135 (void)x;
136 printf("dexectest: lazy: touching 2 data pages took %d free pages\n",
137 before - after);
138 result("lazy", before - after == 2 && pageok(1) && pageok(2));
139}
140
141// a child forked before a page is touched loads it from the same
142// file.
143void
144forktest(void)
145{
146 int pid = fork();
147 if (pid < 0) {
148 printf("dexectest: fork failed\n");
149 result("fork", 0);
150 return;
151 }
152 if (pid == 0)
153 exit(pageok(3) ? 0 : 1);
154 int xstatus;
155 wait(&xstatus);
156 result("fork", xstatus == 0 && pageok(3));
157}
158
159// the kernel copies to and from untouched program pages while it
160// holds spinlocks: pipewrite and piperead hold pi->lock, kwait holds
161// wait_lock and the child's p->lock.
162void
163lockedtest(void)
164{
165 int fds[2];
166 int *dst = &big[PAGE(4)];
167 int *status = &big[PAGE(5)];
168 int *src = &big[PAGE(8)];
169
170 if (pipe(fds) < 0) {
171 result("locked", 0);
172 return;
173 }
174 int pid = fork();
175 if (pid < 0) {
176 result("locked", 0);
177 return;
178 }
179 if (pid == 0) {
180 int v[2] = {4004, 4005};
181 write(fds[1], v, sizeof(v));
182 exit(7);
183 }
184 int m = write(fds[1], src, 2 * sizeof(int)); // from page 8
185 close(fds[1]);
186 int n = 0, k;
187 while (n < 4 * sizeof(int) &&
188 (k = read(fds[0], (char *)dst + n, 4 * sizeof(int) - n)) > 0)
189 n += k; // into page 4
190 close(fds[0]);
191 int w = wait(status); // into page 5
192 // the pipe holds the child's two ints and page 8's first two, in
193 // either order.
194 int ok = (dst[0] == 4004 && dst[1] == 4005 && dst[2] == 1008 &&
195 dst[3] == 0x5a5a5a5a) ||
196 (dst[0] == 1008 && dst[1] == 0x5a5a5a5a && dst[2] == 4004 &&
197 dst[3] == 4005);
198 result("locked", m == 2 * sizeof(int) && n == 4 * sizeof(int) && ok &&
199 w == pid && *status == 7);
200}
201
202// read() from this program's own file into its own unloaded pages:
203// fileread holds the file's inode lock while it copies.
204void
205selfreadtest(void)
206{
207 char *dst = (char *)&big[PAGE(6)];
208 int fd = open(self, O_RDONLY);
209
210 if (fd < 0) {
211 printf("dexectest: cannot open %s\n", self);
212 result("selfread", 0);
213 return;
214 }
215 int n = read(fd, dst, PGSIZE); // page 6: data, writable
216 close(fd);
217 int ok = n == PGSIZE && *(uint *)dst == ELF_MAGIC;
218
219 fd = open(self, O_RDONLY);
220 int m = read(fd, (char *)ro, 16); // text: must fail
221 close(fd);
222 result("selfread", ok && m < 0 && strcmp(ro, "read-only") == 0);
223}
224
225// copy file src to dst.
226int
227copyfile(char *src, char *dst)
228{
229 char buf[512];
230 int n, in, out;
231
232 if ((in = open(src, O_RDONLY)) < 0)
233 return -1;
234 if ((out = open(dst, O_CREATE | O_WRONLY | O_TRUNC)) < 0) {
235 close(in);
236 return -1;
237 }
238 while ((n = read(in, buf, sizeof(buf))) > 0)
239 if (write(out, buf, n) != n)
240 break;
241 close(in);
242 close(out);
243 return n == 0 ? 0 : -1;
244}
245
246// start a copy of this program as a helper that waits for a byte
247// on its stdin, then checks the pages of big[] (see main).
248// returns its pid; *go is the pipe to write the byte to.
249int
250starthelper(char *file, int *go)
251{
252 int down[2], up[2];
253 char c;
254
255 if (pipe(down) < 0 || pipe(up) < 0)
256 return -1;
257 int pid = fork();
258 if (pid < 0)
259 return -1;
260 if (pid == 0) {
261 close(0);
262 dup(down[0]);
263 close(1);
264 dup(up[1]);
265 close(down[0]);
266 close(down[1]);
267 close(up[0]);
268 close(up[1]);
269 exec(file, (char *[]){file, "helper", 0});
270 exit(2);
271 }
272 close(down[0]);
273 close(up[1]);
274 // the helper writes one byte once it runs; until then we must
275 // not change its file.
276 if (read(up[0], &c, 1) != 1) {
277 close(up[0]);
278 close(down[1]);
279 wait(0);
280 return -1;
281 }
282 close(up[0]);
283 *go = down[1];
284 return pid;
285}
286
287// what the helper reports by its exit status, or -1 if killed.
288int
289finishhelper(int go)
290{
291 int xstatus;
292
293 write(go, "g", 1);
294 close(go);
295 wait(&xstatus);
296 return xstatus;
297}
298
299// the file of a running program is unlinked: the process keeps
300// it alive, and its pages still load.
301void
302unlinktest(void)
303{
304 int go;
305
306 if (copyfile(self, "dxcopy") < 0) {
307 result("unlink", 0);
308 return;
309 }
310 int pid = starthelper("dxcopy", &go);
311 if (pid < 0) {
312 result("unlink", 0);
313 return;
314 }
315 int r = unlink("dxcopy");
316 int st = finishhelper(go);
317 result("unlink", r == 0 && st == 0 && open("dxcopy", O_RDONLY) < 0);
318}
319
320// the file of a running program is truncated: a page that is not
321// loaded yet can't be read, so the process is killed.
322void
323truncatetest(void)
324{
325 int go;
326
327 if (copyfile(self, "dxcopy") < 0) {
328 result("truncate", 0);
329 return;
330 }
331 int pid = starthelper("dxcopy", &go);
332 if (pid < 0) {
333 result("truncate", 0);
334 return;
335 }
336 close(open("dxcopy", O_WRONLY | O_TRUNC));
337 int st = finishhelper(go);
338 unlink("dxcopy");
339 result("truncate", st == -1);
340}
341
342// the file of a running program is overwritten: a page that is
343// not loaded yet comes from the new contents.
344void
345modifytest(void)
346{
347 int go, fd;
348 int v = 2007;
349
350 if (copyfile(self, "dxcopy") < 0) {
351 result("modify", 0);
352 return;
353 }
354 int off = fileoff("dxcopy", (uint64)&big[PAGE(7)]);
355 int pid = starthelper("dxcopy", &go);
356 if (off < 0 || pid < 0) {
357 result("modify", 0);
358 return;
359 }
360 // overwrite the first int of page 7 in the file.
361 fd = open("dxcopy", O_RDWR);
362 char skip[512];
363 for (int left = off; left > 0;) {
364 int m = left > sizeof(skip) ? sizeof(skip) : left;
365 read(fd, skip, m);
366 left -= m;
367 }
368 write(fd, &v, sizeof(v));
369 close(fd);
370 int st = finishhelper(go);
371 unlink("dxcopy");
372 // the helper exits with 3 if it saw 2007 in page 7.
373 result("modify", st == 3);
374}
375
376// sbrk(-n) below the end of the image and back again: the pages
377// that come back must be zeros, not the file's bytes. The child
378// gives back its own stack doing this, so from then on it calls
379// only the system-call stubs, which use no stack, until it exits.
380void
381shrinktest(void)
382{
383 int pid = fork();
384 if (pid < 0) {
385 result("shrink", 0);
386 return;
387 }
388 if (pid == 0) {
389 int n = sbrk(0) - (char *)&big[PAGE(8)];
390 sys_sbrk(-n, SBRK_EAGER); // give back pages 8-15, bss, stack
391 sys_sbrk(n, SBRK_LAZY); // take the addresses back, lazily
392 exit(big[PAGE(9)]); // 0 if page 9 came back zeroed
393 }
394 int xstatus;
395 wait(&xstatus);
396 result("shrink", xstatus == 0);
397}
398
399// the whole image, touched at last: the text is the file's bytes,
400// with zeros after them, and the bss is zero.
401void
402contenttest(void)
403{
404 struct proghdr ph[4];
405 char buf[512];
406 int ok = 1;
407 int n = readphdrs(self, ph, 4);
408
409 if (n < 1)
410 ok = 0;
411 for (int i = 0; i < n; i++) {
412 if (ph[i].flags & ELF_PROG_FLAG_WRITE)
413 continue; // data: the program has written some of it
414 // compare the segment with the file.
415 int fd = open(self, O_RDONLY);
416 uint64 left = ph[i].off;
417 while (left > 0) {
418 int m = left > sizeof(buf) ? sizeof(buf) : left;
419 read(fd, buf, m);
420 left -= m;
421 }
422 char *m = (char *)ph[i].vaddr;
423 for (uint64 done = 0; done < ph[i].filesz;) {
424 int k = ph[i].filesz - done > sizeof(buf) ? sizeof(buf)
425 : ph[i].filesz - done;
426 if (read(fd, buf, k) != k || memcmp(m + done, buf, k) != 0)
427 ok = 0;
428 done += k;
429 }
430 close(fd);
431 // the rest of the last page is zero.
432 for (uint64 a = ph[i].vaddr + ph[i].filesz;
433 a < PGROUNDUP(ph[i].vaddr + ph[i].memsz); a++)
434 if (*(char *)a != 0)
435 ok = 0;
436 }
437 for (int k = 0; k < NBIG; k++)
438 if (!pageok(k) && k != 4 && k != 5 && k != 6) // 4-6 were written
439 ok = 0;
440 for (int i = 0; i < sizeof(zeros); i++)
441 if (zeros[i] != 0)
442 ok = 0;
443 result("content", ok);
444}
445
446struct test {
447 char *name;
448 void (*f)(void);
449} tests[] = {
450 {"lazy", lazytest}, {"fork", forktest},
451 {"locked", lockedtest}, {"selfread", selfreadtest},
452 {"unlink", unlinktest}, {"truncate", truncatetest},
453 {"modify", modifytest}, {"shrink", shrinktest},
454 {"content", contenttest},
455};
456
457int
458main(int argc, char *argv[])
459{
460 self = argv[0];
461 if (argc == 2 && strcmp(argv[1], "helper") == 0) {
462 // started by starthelper: say we run, wait for the go byte,
463 // then touch pages 7 to 15.
464 char c;
465 write(1, "r", 1);
466 if (read(0, &c, 1) != 1)
467 exit(1);
468 if (big[PAGE(7)] == 2007)
469 exit(3); // modifytest changed the file
470 for (int k = 7; k < NBIG; k++)
471 if (!pageok(k))
472 exit(1);
473 exit(0);
474 }
475
476 for (int i = 0; i < sizeof(tests) / sizeof(tests[0]); i++)
477 if (argc < 2 || strcmp(argv[1], tests[i].name) == 0)
478 tests[i].f();
479 printf("dexectest: %s\n", failed ? "SOME TESTS FAILED" : "ALL OK");
480 exit(failed);
481}

6. Verify and measure

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

$ dexectest
dexectest: lazy: touching 2 data pages took 2 free pages
dexectest: lazy: OK
dexectest: fork: OK
dexectest: locked: OK
dexectest: selfread: OK
dexectest: unlink: OK
usertrap(): unexpected scause 0xd pid=7
            sepc=0xd52 stval=0xd000
dexectest: truncate: OK
dexectest: modify: OK
dexectest: shrink: OK
dexectest: content: OK
dexectest: ALL OK
$ usertests -q
usertests starting
test copyin: OK
test copyout: OK
[...]
test nowrite: usertrap(): unexpected scause 0xf pid=6571
[...]
test unlinkcwd: OK
ALL TESTS PASSED
$ dexectest
dexectest: lazy: touching 2 data pages took 2 free pages
dexectest: lazy: OK
dexectest: fork: OK
dexectest: locked: OK
dexectest: selfread: OK
dexectest: unlink: OK
usertrap(): unexpected scause 0xd pid=6660
            sepc=0xd52 stval=0xd000
dexectest: truncate: OK
dexectest: modify: OK
dexectest: shrink: OK
dexectest: content: OK
dexectest: ALL OK

The usertrap() lines are the expected kills. In dexectest truncate the helper touches page 7 of big[] (stval=0xd000) after its file was truncated, and the test checks that its exit status is -1; in usertests nowrite a child stores to text. usertests -q passing shows that what the original kernel did still works: copyout into text still fails (the page is mapped without PTE_W and copyout refuses it), stores to text still kill, the stack guard still faults, the lazy heap still works, and no page is lost.

Every commit builds with make kernel/kernel fs.img, and usertests -q printed ALL TESTS PASSED on 3 harts at each of the 11 commits.

Crafted ELF files (copies of echo with patched program headers) on the same branch: a data segment ending past MAXVA, one ending where the stack would cover the trampoline, and a text segment longer than the file all make exec return -1, as on the original kernel, with no panic. A 4 GiB bss segment execs (exec-succeeded), where the original kernel refused it for lack of memory: nothing is allocated until it is touched.

The same dexectest on the original kernel: lazy: touching 2 data pages took 0 free pages, lazy: FAIL, truncate: FAIL, modify: FAIL, all other checks OK.

(These counts were made with a dexectest whose locked check had no pipe write yet; the kernel’s loading code is the same.)

Pages loaded against the size of the image. A scratch copy of the branch counted, per program file, the execs, the pages of the image, and the pages loaded (and which ones); a scratch copy of the original kernel counted the pages its exec allocated for segments. Both printed the counters on Ctrl-P (instrumentation not on the branch). Same commands, one boot each, except the dexectest lazy row, which comes from a separate boot of the counting branch:

program (image pages)	event	original kernel: pages loaded	demand paging: pages loaded
`init` (2)	boot	2	2
`sh` (3)	boot and three command lines	3	3
`echo` (2)	`echo hi`	2	1 (its bss page is never touched)
`ls`, `cat`, `grep`, `wc` (2 each)	`ls`, `cat README \| grep the \| wc`	8	8
`dexectest` (25)	`dexectest lazy` alone	25	8 (text pages 0, 1, 2 and 4, data page `0x5000`, `big[]` pages 1 and 2, one bss page)
`dexectest` (25)	full `dexectest`	25	26 (all 25, one of them twice: page 3 of `big[]`, which the `fork` check makes both the child and the parent load)
`dxcopy` helpers (25)	3 runs inside `dexectest`	75	22 (13 different pages)
`echo` (2)	in `usertests -q`	4 (2 execs; one of them, `bigargtest`’s, then fails)	1 (1 exec succeeds)
`usertests` (16)	`usertests -q`	16	16 (the `touchimage` warm-up)

The small programs touch almost everything they have, and demand paging saves little there: a 2-page program cannot save more than a page. The gain grows with the part of a program a run does not need: the helpers in dexectest used 22 of 75 pages. Notice also the failed exec: the original kernel read echo twice for bigargtest, whose exec is built to fail when it copies the arguments; the demand-paged kernel read nothing for it.

How much of usertests is ever touched? All of it. With the touchimage warm-up removed (and its leak check failing, as expected: lost some free pages 32466 (out of 32469)), the 16 pages of usertests (9 text, 7 data and bss) were loaded 136 times across all its processes, and every one of the 16 at least once. A test suite runs every test; that is what it is for. The 136 loads are the price of forking before touching: a child inherits only the pages its parent had loaded, and loads the rest again from the file (through the buffer cache), each child for itself.

One page per touch. dexectest lazy: touching 2 data pages took 2 free pages on this branch, 0 on the original kernel.

Where loads happen. In the gdb runs of the finished branch (boot, echo hi, dexectest selfread, locked, unlink, truncate), loads came from page faults with interrupts off and from three system-call paths with interrupts on: sys_exec's copyin of argv, sys_open's copyinstr of a path (the shell opening console: the string is in sh’s second text page), and the prefaults of sys_read and sys_wait. Every load that read a block not in the cache slept, and processes regularly finished a load on a different hart from the one that started it.

7. Go further

Make the latent bug fail every time. A sleep under a spinlock only panics when the load misses the buffer cache. A check at the top of loadpage, panic if this hart’s noff is not 0 (read with interrupts off, so the hart cannot change under you), turns clinic 6’s pipe case into a panic on every run. Why does it not catch the self-deadlock, and what would you need to catch that (a per-process count of held sleep-locks)?
Text busy. Refuse to open a running program’s file for writing (and refuse to exec a file open for writing), as Unix does with ETXTBSY. You will need a count of executing processes per inode that kfork can update without sleeping, and you will meet the question of which lock protects it.
Share text pages between processes. Every process loads its own copy of a text page, even when ten processes run the same program. Keep loaded pages in a per-inode cache and map the same physical page read-only into each process: a first page cache, and the reason real kernels count references to pages (lab 11).
Fault-around. Load the neighbours of a faulting page too, if they are cheap (already in the buffer cache). Measure faults and disk reads per program before and after.
Drop clean pages under memory pressure. A text page that was never written can be unmapped and freed when memory runs out, and loaded again from the file on the next touch: no swap space needed. What must the kernel know about a page to decide it may do that? (Lab 16 builds on this.)
mmap. The segment table is a special case of a list of file-backed mappings. Generalize it into mmap and munmap of any file (lab 15).