Step 1 of 19 · commit 1: Keep a reference to the executable in each process

exec keeps the file it read

The story of this tour, recorded with gdb on the branch, three harts (the recording predates one bound check in kexec and one pipe write in dexectest, so kernel addresses in exec.c differ from the branch’s by a few bytes): the machine boots, init and the shell load their pages as they run, you type echo hi, and the shell’s child (pid 3) calls exec("echo"). Later steps follow dexectest reading its own file, and a helper whose file is deleted while it runs.

Commit 1 changes what kexec does with the inode namei gave it. The original kernel dropped it as soon as the segments were read (iunlockput, then end_op). Now the image will be read later, so the process keeps that reference in p->exe (a new field in struct proc). Keeping the one namei already counted costs nothing: no idup, no extra lock.

Two things moved to make this possible. The inode stays locked, and the transaction open, until the image is committed (the comment at line 79): the commit is where the new reference replaces the old one, and the old one must be dropped inside a transaction. The error path is unchanged: every goto bad still happens with ip locked and the transaction open, exactly what bad: (line 148) undoes.

At the focus lines gdb saw pid 3 on hart 2 holding the inode lock of echo (inode 4, lock.pid 3), and log.outstanding = 1: this exec’s transaction. The old image’s file, the shell’s (inode 13), had ref 2: the shell’s reference and this child’s.

Step 2 of 19 · commit 1: Keep a reference to the executable in each process

Dropping the old program, inside the transaction

iunlock first, then iput of the old program’s file, then end_op. The order inside is deliberate:

• iput can free the inode and its blocks, when this was the last reference to a file that has been unlinked meanwhile. Freeing writes the free bitmap and the inode through the log, so it must happen before end_op.
• The new inode is unlocked before the old one is dropped. If they are the same file (a shell that execs sh), iput would only lower ref from 2 to 1; but holding one inode’s sleep-lock while iput might take another’s is an ordering this code never needs.

Here the old file is sh, ref 2 → 1: nothing is written. Only an unlinked program makes this iput write; the last step of the tour shows one doing it. oldexe is 0 only once: for init’s exec from forkret, the first process has no program yet.

Step 3 of 19 · commit 1: Keep a reference to the executable in each process

The child inherits the file, exit lets it go

kfork treats the program file like the current directory: the child gets its own counted reference with idup. The child needs it because it shares nothing with its parent’s address space but copies: pages the parent loaded are copied by uvmcopy, pages it never touched are missing in the child too, and the child will load them itself, from the file, through p->exe.

kfork still holds the child’s np->lock here (since allocproc, until line 295): noff 1, intena 1 (a system call, so interrupts were on before the first acquire). Inside idup, itable.lock makes it noff 2 for a few instructions: the edge p->lock → itable.lock that p->cwd already created (Locks and interrupt state). (This state is reasoned from the code; no breakpoint was set here.)

In kexit (below in the same file, lines 343-348) the reference is dropped next to p->cwd, inside the begin_op/end_op that was already there. Clinic 4 removes the idup and gets panic: ilock; clinic 5 moves the iput out of the transaction and gets panic: log_write outside of trans.

Step 4 of 19 · commit 1: Keep a reference to the executable in each process

exit drops the reference inside its transaction

echo has printed hi and exits. gdb stopped at line 345 on hart 2: p->exe is inode 4 with ref 1 and nlink 1, and log.outstanding is 1, the transaction begun at line 343. This iput makes ref 0 and writes nothing, since the file still has its name. The in-memory inode stays in the table, valid, until iget needs the slot for another file.

Setting p->exe = 0 matters for the same reason as p->cwd = 0: the zombie keeps its struct proc until the parent’s wait, and no stale pointer should survive in it.

Nothing else in exit changes. The process’s pages, loaded or not, are freed by freeproc in the parent’s kwait, as before: uvmunmap skips pages that were never mapped (kernel/vm.c:205), so an image with holes in it frees cleanly.

Step 5 of 19 · commit 2: Record the program's segments in exec

A record per segment

struct seg holds the five values the think section listed: where the segment starts in memory, how big it is there, where its bytes are in the file, how many bytes the file has, and the PTE permissions (flags2perm's result, so PTE_X and/or PTE_W). struct proc gets seg[NSEG], kept in address order, and nseg. NSEG is 4 (param.h); every program in this tree has 2 loadable segments (forktest, linked differently, has 1).

The comment block in struct proc says the fields below it are “private to the process, so p->lock need not be held”. The new ones belong there: only the process itself reads them (in its faults and system calls), and they change only in its own exec or sbrk, or in kfork before the child can run. That is also why the fault path can read them without any lock.

Step 6 of 19 · commit 2: Record the program's segments in exec

exec records each segment

Each segment is still loaded as before, and now also recorded in a local seg[], copied into the process at the commit with the other parts of the new image. A failed exec leaves the old table untouched, like the old page table.

One new check: a segment must start at or above the end of the previous one, and there may be at most NSEG of them. The original kernel accepted overlapping segments without noticing (uvmalloc mapped only the pages above the previous end, and loadseg wrote into whatever was mapped); with demand paging a page must belong to exactly one segment, or the fault would not know which bytes to read. No program in this tree has overlapping segments: ${TOOLPREFIX}readelf -l shows text at 0x0 and data at the next page boundary (the linker script aligns .data to 0x1000).

kfork copies the table along with the reference (in proc.c). Nothing reads it yet.

Step 7 of 19 · commit 3: Add loadpage to read one page of the program on demand

loadpage: find the segment, zero the page

The loader, loadpage(p, va), for one page-aligned address below the end of the image (imgend, defined above it, computes that end from the last segment). First the segment that contains the page; if there is none, va is in a hole between segments and the fault is not this function’s to fix. Then a page from kalloc, zeroed before anything else. kalloc fills pages with 0x05 (kernel/kalloc.c:80), and whatever the file does not supply (the bss, the tail of a segment’s last page) must read as 0. Clinics 2 and 3 get this order wrong in both directions.

The state is from the finished branch: the very first page load of the boot. init (pid 1) returned to user mode at its entry point 0xbc with nothing mapped, the fetch faulted (scause 12), and here, on hart 1, loadpage handles va 0. As in every page fault, interrupts are off: usertrap calls intr_on only for system calls (kernel/trap.c:66). No lock is held yet.

init's kernel stack, during the load
  top ─► usertrap
         vmfault
         loadpage
         readi → bread → virtio_disk_rw → sleep (next step)

Step 8 of 19 · commit 3: Add loadpage to read one page of the program on demand

loadpage: read the file's part, under the inode lock

If the page holds any of the file’s bytes (off < filesz), readi copies min(4096, filesz - off) of them into the front of the page, from file offset s->off + off, with the inode locked: ilock is a sleep-lock, and readi may wait for the disk in bread. A short read means the file is now shorter than the program (someone truncated it): the page cannot be built, it is freed, and the function returns 0. Then mappages with PTE_R | PTE_U plus the segment’s bits. A page entirely past filesz skips the read and never touches the inode.

init’s page 0: filesz is 0xa01, so 2561 bytes, three 1024-byte blocks. gdb stopped at line 241 with the lock held by pid 1, then three times in virtio_disk_rw's wait loop: on hart 1, on hart 1, on hart 0, each time with noff 1 (disk.vdisk_lock) and intena 0. Back at line 246 the process was on hart 1. Sleeping here is legal although interrupts are off: sleep takes p->lock, sched finds noff 1 and interrupts off, as it requires, and the scheduler on this hart turns them on while init waits.

The PTE this produced, read by gdb before init went back to user mode: 0x21fd541b, flags 0x1b = V|R|X|U.

Step 9 of 19 · commit 4: Let vmfault load missing pages of the program

vmfault: below the image, the page comes from the file

One comparison, placed after the two checks that were already there (below p->sz, not mapped) and before the zero-page code: a missing page below the end of the image belongs to the program, and loadpage builds it. Above it, the lazy heap, unchanged. The test pagetable == p->pagetable keeps kexec's copies into a new page table (the stack, which is mapped anyway) away from the current process’s segments.

Because copyin, copyout and copyinstr call vmfault for missing pages, a system call can be the first to touch a page of the program. gdb caught exactly that during boot: init forked, and its child (pid 2, still named init) called exec("sh", argv). sys_exec fetched argv, a global array in init’s data page 0x1000, with copyin, and that page was loaded through here with interrupts on (a system call) and no locks. The load started on hart 1, waited once for the disk, and finished on hart 0. It is a page the child then threw away when exec replaced the image.

Step 10 of 19 · commit 5: Read scause and stval before a page fault can sleep

Read the trap registers before anything can sleep

usertrap read scause, sepc and stval from the CSRs again and again: to pick a branch, as vmfault's argument, and in the error message. That was safe while nothing in between could sleep. Now vmfault can sleep in loadpage, and the CSRs belong to the hart: while the process sleeps, the hart runs the scheduler and takes other traps, and the process may wake up on another hart altogether.

gdb saw it: at the top of this fault scause was 12 and stval 0xbc; after init’s read had finished, the same hart’s scause read 0x8000000000000009, a supervisor external interrupt (the disk), and stval 0. Had the load failed after sleeping, the old code would have printed that interrupt’s cause and address instead of the fault’s.

So usertrap copies scause and stval into locals at once, and the error message prints p->trapframe->epc, the sepc saved at line 52. Returning to user mode was never affected: prepare_return writes sepc from the trapframe, not from the CSR.

This step’s state: the start of init’s first fault, hart 1, on the kernel stack that uservec switched to, which held nothing until usertrap's frame. Interrupts are off and stay off on this path.

Step 11 of 19 · commit 6: Handle instruction page faults in usertrap

The instruction page fault joins the branch

scause 12 now goes to vmfault with 13 and 15, as a read. Until this lab no fetch could hit a missing page of the program, because exec had mapped all the text; from the switch on, the first instruction of every program faults here. gdb recorded vmfault entered from here with va 0xbc, psz 0x4000 and read 1: init’s entry point, its two image pages plus guard and stack.

devintr is still asked first: a timer or device interrupt has a scause with the top bit set, never 12, 13 or 15, so the order does not matter for correctness.

Retrying needs nothing special: epc was not advanced (only the system-call branch adds 4), so userret returns to the same instruction, which now finds its page. The bytes were written through the kernel’s direct map, and userret executes fence.i (kernel/trampoline.S:107) before every return to user mode, so the hart fetches the new instructions and not anything stale.

Step 12 of 19 · commit 7: Load a system call's program pages before taking locks

uvmprefault: load before you lock

Scene 2: dexectest selfread. The program opens its own file and calls read(fd, dst, 4096) with dst at 0xc000, page 6 of big[], which it has never touched.

uvmprefault(p, va, n) walks the pages of [va, va+n) that lie below the end of the image and loads every one that is not mapped, through vmfault. Pages above the image are left alone: a lazy heap page costs only kalloc, which takes a spinlock and never sleeps, so a copy under a lock may allocate it as before. If a program page cannot be loaded, the system call fails with -1, before it has touched anything.

gdb stopped here on hart 2 with a = 0xc000, interrupts on, nothing held: the load that follows may sleep on the disk and on the inode lock, and it did (loadpage began on hart 2 and finished on hart 0). It was the same inode the read is about to lock, and that is fine now, because the read has not locked it yet.

Step 13 of 19 · commit 7: Load a system call's program pages before taking locks

read and write call it first

sys_read and sys_write call uvmprefault after decoding their arguments and before fileread/filewrite, the last moment at which the system call holds no lock. What each kind of file holds while it copies:

After the prefault, dexectest selfread goes on into fileread, which locks inode 23, the program’s own file, and readi copies four blocks into page 6, which is now mapped: no load, no second ilock. The test then reads 16 bytes into ro, a page of read-only data in the text segment. The prefault loads that page (text is legal to load), and copyout refuses it because its PTE has no PTE_W (kernel/vm.c:364): read returns -1, as usertests copyout demands for text.

The page stays mapped between the prefault and the copy because nothing but this process could unmap it, and this process is busy here.

Step 14 of 19 · commit 7: Load a system call's program pages before taking locks

wait copies under two spinlocks

kwait copies the child’s exit status into *addr while it holds wait_lock and the child’s p->lock (kernel/proc.c:376, kernel/proc.c:384-kernel/proc.c:391): noff 2. A load there would be a sleep with noff 3 at sched. So sys_wait loads the status’s page first, if it is a program page.

dexectest locked (pid 5) does exactly that: wait(&big[PAGE(5)]), a status variable in an untouched data page. gdb stopped in uvmprefault from sys_wait with a = 0xb000 on hart 2, interrupts on, no locks; the page was loaded and the load finished on the same hart. A moment earlier the same process had read from a pipe into page 4 (0xa000) the same way, through sys_read's prefault, and its child (pid 6) had exited.

Step 15 of 19 · commit 8: Make usertests load its own image before counting free pages

usertests loads itself before it counts

drivetests counts free pages with countfree before the tests and after, and reports lost pages if the second count is lower. On a demand-paged kernel the usertests process itself loads pages of its own image during the tests (code of later tests, the test table, strings), and those pages are no longer free. A run of the branch without this commit printed FAILED -- lost some free pages 32467 (out of 32470): three pages of usertests were “lost” into usertests.

touchimage reads one byte of every page from address 0 up to the linker’s end (text, data and bss), through a volatile pointer so the compiler cannot drop the reads. After it, the whole image is loaded, both counts see the same program, and the leak check means what it meant before. On the original kernel every page is already there and it changes nothing. In this build the loop is three instructions (lbu, add, bltu) starting at address 0.

Step 16 of 19 · commit 9: Stop loading the program in exec

The switch

uvmalloc and loadseg are gone from the loop; loadseg is deleted. The loop now only checks and records, and sz becomes the end of the last segment, so the guard page and the stack land at the next page boundary exactly as before. Everything else in kexec, the stack, the argument strings, the commit, is unchanged.

Two checks are new, because uvmalloc and loadseg used to make them implicitly. Line 77: the segment must end low enough to leave room for the guard page and the stack below TRAPFRAME. The original kernel could not get past uvmalloc with a segment that ends near MAXVA (it ran out of memory and exec returned -1); without this line, a crafted ELF made the stack setup panic (panic: walk for a segment ending past MAXVA, panic: mappages: remap for one ending at the trampoline). Line 79: the file must be long enough to hold every segment’s bytes, as loadseg's readi used to check; without it such a program would start and die at its first fault in the missing part. ip->size is valid because the inode is locked, which is why exec.c now includes fs.h and file.h.

gdb saw dexectest’s exec commit on hart 0 with its inode (23, ref 1) locked by pid 4 and the transaction open. After it, the process ran with nothing mapped but the stack and the trampoline. Its first fault was an instruction fetch at 0xd34, its entry point.

Step 17 of 19 · commit 10: Trim the segment table when sbrk shrinks the process

sbrk below the image

growproc calls segtrim(p, sz) after uvmdealloc when the process shrinks. Each segment is cut at the new size, rounded up to a page as uvmdealloc rounds it, and segments entirely above it are dropped. The end of the image moves down with the process, so if it grows again (sbrklazy) and touches those addresses, vmfault gives it zero pages, as the original kernel does, instead of the program’s bytes.

Only a process that gives back its own stack can get here, since the stack lies above the image. dexectest shrink does it in a child: sys_sbrk(-n, SBRK_EAGER) down to page 8 of big[], sys_sbrk(n, SBRK_LAZY) back up, then exit(big[PAGE(9)]). Between the two calls it uses only registers (we checked the compiled code: the raw system-call stubs need no stack). It exits with 0 on this branch. A copy of the branch with the segtrim call removed printed dexectest: shrink: FAIL: the child’s exit status was not 0. (Reasoned: page 9 came back from the file, whose first int there is 1009, instead of as zeros; the status itself was not printed.)

(The state is reasoned, not recorded: segtrim runs in the shrinking child’s sys_sbrk with interrupts on and no locks.)