Step 1 of 18

The child asks to become ls

runcmd has an EXEC command whose argv is {"ls", 0}. The string "ls" is inside the child’s copy of buf (at 0x2020), cut off by a null byte where the newline was; the argv array itself is in the execcmd structure that malloc placed in the heap.

exec(ecmd->argv[0], ecmd->argv) passes two user addresses: the path and the array. If exec returns at all, it failed, and line 80 prints exec ls failed. On success it never returns: the code that would have returned to is gone.

exec is the stub li a7,7 (SYS_exec) and ecall; the trip to sys_exec is Tour 5: Life of a system call's.

Step 2 of 18

sys_exec copies everything into the kernel first

sys_exec copies the path into path[128] on the kernel stack with argstr, and then each argument string into a page of its own from kalloc: it reads each pointer of the user argv array with fetchaddr until it finds the null, and copies the string it points to with fetchstr. For ls that is one page, holding "ls".

Why copy before doing anything? Because kexec is about to destroy the memory these strings live in. The new stack will be built from the kernel copies, and only after that is the old image freed. The copies also protect the kernel from a pointer that is bad or that points at nothing: fetchaddr and fetchstr check every access (Tour 6: System-call arguments and user pointers).

Both arrays are locals of sys_exec, on pid 3’s kernel stack: path[128] and argv[32], the 32 pointers to those kernel pages. That is why sys_exec’s frame is 480 bytes (kernel/kernel.asm). With kexec’s 544-byte frame on top of it, these two functions alone take 1 KiB, a quarter of the one-page kernel stack; the argument strings, up to a page each, could never fit there, so they get pages of their own.

At most MAXARG (32) slots, so at most 31 arguments, each at most a page. A bad path returns -1 at once. Any later failure (too many arguments, a bad pointer, kalloc out of memory) jumps to bad, which frees the pages already taken and returns -1.

Step 3 of 18

A transaction, a path lookup and an inode lock

kexec starts with begin_op, opening a file-system transaction. exec only reads the file, so why? Because at the end it drops its inode reference with iunlockput, and if someone deleted ls in the meantime, that drop would be the last reference and would free the file’s blocks: a disk write, which must be inside a transaction (Tour 31: The log: begin_op, commit and group commit). begin_op may sleep if the log is busy; no spinlock is held, so that is allowed.

namei("ls") resolves the relative path from the current directory, /, and returns the in-memory inode for /ls (inode 10, 40256 bytes), referenced but unlocked (Tour 34: Path lookup). On the way, namei briefly locks the / directory inode to search it, then unlocks it. If there is no such file, kexec ends the transaction and returns -1: this is the one failure that does not go through bad.

ilock then takes the inode’s sleep lock, reading the on-disk inode if needed. The process holds it while it reads the file. Interrupts stay on: a sleep-lock is not a spinlock. Its inner spinlock was held only inside acquiresleep, so once ilock returns, this hart’s noff is back to 0 (Locks and interrupt state).

Step 4 of 18

Is this an ELF file?

readi copies the first 64 bytes of the file into elf, a local struct elfhdr on the kernel stack. The 0 argument says the destination is a kernel address. Underneath, readi asks the buffer cache for the file’s first block, taking bcache.lock and that buffer’s sleep-lock briefly (Tour 30: The buffer cache).

Two checks: the file must hold at least 64 bytes (line 49), and its first four bytes must be 7f 45 4c 46 (“\x7fELF”), which as a little-endian uint is ELF_MAGIC, 0x464C457F. For user/_ls, readelf -h shows what else the header says:

A file that is not ELF (say, README) fails here and goes to bad.

Step 5 of 18

A second page table, beside the first

proc_pagetable builds a fresh page table with no user memory, only the trampoline page and the trapframe mapped at the top (Tour 25: A user address space). It is held in the local variable pagetable. The process is still running on its old page table, p->pagetable, and nothing points to the new one except this local.

Look closely at which trapframe gets mapped: p->trapframe, the process’s existing trapframe page. Both page tables now map the same physical page at TRAPFRAME. That is what makes the switch at the commit point painless: the registers exec writes for the new program (epc, sp, a1) go into a page that both the old and the new image share.

This is the whole strategy of exec: build the new world entirely on the side, then swap it in with a few stores.

Step 6 of 18

Reading the program headers

The loop reads the four program headers one at a time, at file offsets 64, 120, 176 and 232:

For each LOAD segment, three checks guard against a malicious file:

• memsz < filesz: the segment would claim more file bytes than memory to hold them;
• vaddr + memsz < vaddr: the sum wraps around 2^64, which could make a huge segment look small to the next check;
• vaddr % PGSIZE != 0: loadseg assumes the segment starts on a page boundary (it walks the new table one page at a time from vaddr).

None of these needs a lock beyond the inode’s: the header bytes come from this file, read under its sleep-lock.

Step 7 of 18

Allocating pages for each segment

kexec calls uvmalloc(pagetable, sz, vaddr + memsz, flags2perm(flags)) for each segment (kernel/exec.c:72). uvmalloc maps fresh, zeroed pages from the old size up to the new end, adding PTE_R and PTE_U to the permissions:

• Segment 1, code: uvmalloc(pt, 0, 0xb89, PTE_X). One page at 0x0, flags R X U.
• Segment 2, data: uvmalloc(pt, 0xb89, 0x1030, PTE_W). The old size rounds up to 0x1000, so one page at 0x1000, flags R W U.

sz is now 0x1030.

Zero-filling is not optional. The data segment has filesz = 0: all 48 bytes are .bss section, variables C promises start at zero, and they get that only because memset cleared the page. It also keeps the previous owner’s data in a recycled page from leaking into ls.

If kalloc or mappages fails, uvmalloc frees the pages it added and returns 0, and kexec goes to bad.

Step 8 of 18

loadseg copies the file into physical pages

loadseg fills the pages just mapped. It cannot write to virtual address 0x0: this hart runs on the kernel page table, and the new page table is not installed anywhere. So, for each page, it asks walkaddr for the physical address that 0x0 maps to in the new table, and has readi copy file bytes straight there. The kernel can write any physical address directly (direct map).

For segment 1: one iteration, n = 0xb89 (2953) bytes from file offset 0x1000. At 1024 bytes per block, that is three blocks read through the buffer cache. For segment 2, filesz is 0, so the loop does not run at all.

The panic on line 166 cannot fire unless uvmalloc is broken: every page was just mapped. A short read (a truncated file) returns -1, and kexec goes to bad.

Step 9 of 18

Done with the file

iunlockput releases the inode’s sleep-lock and drops the reference that namei took; end_op closes the transaction. Setting ip = 0 tells the bad: code that there is no inode left to release.

This happens before building the stack, deliberately. The rest of exec touches only memory, so there is no reason to keep other processes waiting on the inode lock or to keep the log from committing. Hold file-system locks for as short a time as possible.

From here to the end, kexec holds no locks at all, apart from the brief kmem.lock inside kalloc (two stack pages) and kfree (the 26 pages of the old image).

Step 10 of 18

A guard page and a one-page stack

Two different things are called “stack” and “sp” from here on, and they must not be confused. The hart is running kexec on pid 3’s kernel stack: its real sp register is 0x3fffff9bc0, 1088 bytes below the top of KSTACK(2) (gdb at line 137 showed exactly that depth for every exec system call in our run). The user stack being built here lives in the new page table, which no hart is using; kexec’s C variable sp is just a number, the address that the new program’s sp will have. No instruction pushes onto it; every byte goes there by copyout.

The stack goes just above the program. sz rounds up from 0x1030 to 0x2000, and uvmalloc maps USERSTACK + 1 = 2 more pages, writable: 0x2000 and 0x3000. sz becomes 0x4000.

uvmclear then clears PTE_U on the lower page, 0x2000. It stays mapped, but user code may not touch it: it is the guard page. If ls recursed too deep and its stack pointer went below 0x3000, the next store would fault there instead of silently overwriting ls’s data at 0x1000 (Tour 26: sbrk, eager and lazy, and page faults shows the refusal).

sp = 0x4000, the top of the stack, and stackbase = 0x3000, the lowest address the arguments may reach.

Here is the new image so far, in the new page table:

Step 11 of 18

Pushing the argument strings

The strings come first, at the very top of the stack. For each argument, sp moves down by the string’s length plus its null byte, then down again to a multiple of 16 (the RISC-V calling convention requires a 16-byte-aligned sp).

For our one argument, "ls": 0x4000 - 3 = 0x3ffd, aligned down to 0x3ff0. The check against stackbase stops a huge argument list from running into the guard page.

copyout writes the 3 bytes into the new page table, at 0x3ff0, by walking that table to the physical page (Tour 28: Crossing the user/kernel boundary in memory). It also refuses pages without PTE_W, which is why it could never be tricked into writing over code.

ustack[0] = 0x3ff0 remembers where the string landed, as an address that will be valid in ls’s address space. Then ustack[1] = 0, the null that ends argv.

Step 12 of 18

Pushing argv, and what main will see

Next the array of pointers: (argc + 1) * 8 = 16 bytes, so sp goes from 0x3ff0 to 0x3fe0 (already aligned). copyout writes ustack[0..1] there. That array is ls’s argv.

The top page of ls’s stack, as main will find it:

0x4000  +---------------------------+  top of stack (sz)
        | (13 bytes of padding)     |
0x3ff3  +---------------------------+
        | 'l' 's' '\0'              |  argv[0] points here
0x3ff0  +---------------------------+
        | 0x0000000000000000        |  argv[1] = null
0x3fe8  +---------------------------+
        | 0x0000000000003ff0        |  argv[0]
0x3fe0  +---------------------------+  <- sp, and a1 = argv
        |                           |
        | free stack, grows down    |
0x3000  +---------------------------+  stackbase
        | guard page (no PTE_U)     |
0x2000  +---------------------------+

Notice where ustack[] lived while it was being filled: it is a local array of kexec, so it sat on the kernel stack, and line 117 copied its first 16 bytes out to the user stack in the new page table. The kernel stack is the workbench, the user stack the finished product.

Line 124 stores sp, 0x3fe0, into the saved a1. By the calling convention, a1 is the second argument of a function, and the program’s first function will be start(argc, argv). gdb confirmed: sp=0x3fe0 a1=0x3fe0 for ls.

Step 13 of 18

Naming the process

The loop finds the last path component (for /usr/bin/ls it would be ls; here the path is already ls), and safestrcpy copies it into p->name. The name is only for debugging: Ctrl-P’s procdump prints it, and so does syscall's “unknown sys call” message.

Strictly, this is a change to the process that happens before the commit point. It does no harm: nothing after it can fail.

Step 14 of 18

The commit point

Everything is ready. Four stores turn the shell’s child into ls:

• p->pagetable = pagetable: the new address space;
• p->sz = 0x4000: its size;
• p->trapframe->epc = 0x258: user execution will resume at start, not after the ecall;
• p->trapframe->sp = 0x3fe0: the new stack.

There is no lock here, and none is needed. p->pagetable and p->sz are private to the process (kernel/proc.h:95); the trapframe is used only by this process’s own traps. And the hart is running on the kernel page table, so swapping p->pagetable does not pull the memory out from under the code running now. The new table takes effect when usertrap returns and the trampoline loads satp from MAKE_SATP(p->pagetable).

The last store matters most for the stack story: p->trapframe->sp used to hold the user sp saved when this process trapped in for exec (inside the shell’s stack page at 0x4000). It now holds 0x3fe0, in the new stack page. The hart, meanwhile, is still on the kernel stack and stays there until userret.

Then proc_freepagetable frees the old image: 21 user pages (0x15000 bytes: the shell’s five pages plus the 16-page heap) and its 5 page-table pages. One of those 21 is the old user stack, the one the process was running on when it called exec. Freeing it is safe only because nothing points into it any more: the hart is on the kernel stack, and the saved user sp was just overwritten. Only the trapframe and trampoline mappings are removed without freeing: the trapframe page lives on in the new table.

Step 15 of 18

Every way to fail

All the failures before the commit point land here (except a failed namei, which returns directly). The bad: code undoes exactly what was done, using the two variables that were initialized for this purpose:

In every case p->pagetable, p->sz and the user registers are untouched (only p->name might be, after line 130, but nothing after it fails). The shell’s child gets -1 from exec, prints exec ls failed, and exits.

sz grows only as pages are actually mapped, so proc_freepagetable(pagetable, sz) frees exactly what exists. That is why the code is careful to assign sz = sz1 only after each uvmalloc succeeds.

Step 16 of 18

The return value becomes argc

kexec returns argc, 1. sys_exec frees the kernel pages that held the argument strings (they have been copied onto the new stack) and returns 1. syscall stores it in the saved a0.

So, when ls starts, its registers are:

Every other register still holds whatever the shell had in it at the ecall. xv6 does not clear them. ls cannot depend on them, and does not, since compiled C code initializes registers before reading them.

exec “returns” a value even though the code that called it is gone. The trick is that the system-call return path does not care whose code it returns to: it loads the trapframe and executes sret.

Step 17 of 18

ls starts at start()

usertrap returns into the trampoline with MAKE_SATP(p->pagetable), now the new page table. userret executes fence.i (as it does on every return to user mode), installs that table between two sfence.vmas, reloads the registers and srets. The register reload includes ld sp, 48(a0) (kernel/trampoline.S:118): that is the instant sp leaves pid 3’s kernel stack (empty again: every kernel frame has returned) for the user stack exec built, at 0x3fe0; the hart can use that stack only after sret returns it to user mode. Until that load, from csrw satp on, sp still held a kernel-stack address that ls’s page table does not map (The stacks of xv6).

The first instruction fetched in user mode is at 0x258: start, whose arguments arrive in a0 and a1, exactly where exec put argc and argv. It calls main(1, argv), and ls lists the current directory. When main returns, start calls exit with its result, so even a program that forgets to call exit ends cleanly (Tour 21: exit, wait and zombies).

No stale translation from the shell’s page table can survive into ls: they were discarded when the exec system call entered the kernel (uservec runs sfence.vma right after switching to the kernel table), and the new table is installed between two more.

Step 18 of 18

What exec cost, and why it is shaped this way

The bill for turning the shell’s child into ls: one kernel page for the argument string (given back at the end), 4 user pages and 5 page-table pages taken (the trapframe page is reused), 26 pages given back, and three blocks of program code read from the file after the block holding the headers. All 26 had been allocated moments earlier: 10 by fork (5 user pages copied by uvmcopy, 5 page-table pages) and 16 by malloc’s eager sbrk. Copy-on-write fork avoids copying the 5 pages, and a combined spawn call avoids building the child’s address space at all.

The design rests on two ideas:

• Build beside, then commit. The new image is complete before the old one is touched, so failure is always recoverable, and the commit is four stores. The same holds for the stack: the new user stack is built in the new page table while the hart runs on the kernel stack, which exec never replaces, and the old user stack is freed only after the commit.
• Private things need no locks. A process’s page table, size and trapframe belong to it alone, and xv6 processes have a single thread, so even replacing the whole address space is done without a lock. The locks in exec are all on the shared things: the log, the inode, the buffer cache and the page allocator, and each is held only as long as it must be.