Step 1 of 20

The shell decides to fork

getcmd has filled buf with "ls\n". It is not cd, so the shell calls fork1, a wrapper that calls fork() and panics if it fails, then wait(0).

Why fork at all? The shell wants to run ls and then keep being the shell. exec replaces the memory of the process that calls it, so if the shell called exec("ls") itself, the shell would be gone. Instead it makes a copy; the copy parses the command and turns itself into ls, while the original waits. This pairing is the fork and exec pattern, and it is how every Unix shell runs every command.

Notice what is not done here: the shell does not parse the command. Parsing allocates memory with malloc (see Tour 26: sbrk, eager and lazy, and page faults), and line 173 does it in the child, so the shell’s own memory never grows. That is why the shell stays at five pages for its whole life, a number that will matter in a moment.

fork() is a system call stub: li a7,1 (SYS_fork) and ecall at address 0xc80 in user/sh.asm. From the ecall to sys_fork, the path is exactly Tour 5: Life of a system call's.

Step 2 of 20

sys_fork hands over to kfork

sys_fork takes no arguments, so it does not fetch any. It calls kfork and returns whatever it returns: the child’s pid, or -1. syscall will store that value in the shell’s saved a0 (kernel/syscall.c:146).

Remember the state of things on hart 0 at this moment. usertrap has already saved the user program counter and added 4 to it, so p->trapframe->epc holds 0xc84, the ret right after the ecall. It has turned interrupts back on. The shell’s trapframe holds every user register exactly as they were at the ecall.

That trapframe is about to be photocopied. Everything in it, including that already advanced epc, will become the child’s starting point.

Two stacks belong to the shell, and this step uses the second. Its user stack, the page at 0x4000, was abandoned at the ecall: uservec saved the user sp (0x4f80 in our run) in the trapframe and loaded sp from kernel_sp. Hart 0 now runs on the shell’s kernel stack, the page at KSTACK(1), empty at the moment of the trap and now holding usertrap → syscall → sys_fork (The stacks of xv6).

Step 3 of 20

kfork asks for an empty process

kfork has the whole job in outline: get a blank process (allocproc), copy the parent’s memory (uvmcopy), copy its registers, share its files, and finally make the child runnable.

p is the shell, found with myproc. np (“new process”) will be the child. If allocproc returns 0, the table is full or memory ran out, and fork() returns -1 to the shell, and fork1 calls the shell’s own panic, which prints fork on the console and exits.

Read the rest of the function with one fact in mind: from line 266 to line 294, hart 0 holds the child’s p->lock. allocproc returns with it held. That means interrupts are off on hart 0 for the whole copy, and any other hart that wants this slot’s lock (a scheduler scan, wakeup, kill(3)) must wait. What keeps schedulers from running the half-built child is its USED state; the fields being filled in (memory, trapframe, files) are private to the process (kernel/proc.h:95), and no other hart reads them.

Step 4 of 20

Scanning the table, one lock at a time

allocproc walks proc[] from the start. For each slot it takes that slot’s lock, looks at state, and lets go if the slot is in use:

It needs the lock even to read state, because another hart could be changing it. And it must keep the lock between seeing UNUSED and writing USED on line 126: otherwise two harts forking at once could both see slot 2 free and both claim it.

With the lock held, line 126 sets state = USED. From now on no other allocproc will pick this slot, and no scheduler will run it, since schedulers only run RUNNABLE processes.

Holding the first spinlock turned interrupts off on hart 0 (push_off); they stay off while any spinlock is held, and from line 124 on, the one held is slot 2’s.

Step 5 of 20

A pid from its own lock

allocpid hands out process IDs from the global counter nextpid. init got 1, the shell 2, and this child gets 3. (In our gdb run: child pid=3 slot=2.)

Why a separate lock, pid_lock, and not the slot’s p->lock? Because nextpid is not part of any one slot. Two harts forking at once hold different slot locks (slot 2 and slot 3, say), so neither slot lock would stop them both reading nextpid == 3 and handing out the same pid twice. The read and the increment must be one indivisible step for everyone, and that needs one lock for everyone.

Note the nesting: proc[2].lock is held while pid_lock is taken. That is safe because no code anywhere holds pid_lock and then asks for a p->lock, so no cycle can form (Tour 18: Lock ordering: how xv6 avoids deadlock). pid_lock is one of only four locks a measured run ever saw taken under a p->lock, and fork takes all four (Tour 51: The lock-order graph, measured). The strip shows noff 2: two spinlocks held on this hart (Locks and interrupt state).

Pids are never reused within a boot: the counter only grows. Slots are reused all the time; slot 2 will hold pid 4 for the next command.

Step 6 of 20

A trapframe page and an empty page table

The child needs two things before it can ever run in user mode:

• a trapframe page, from kalloc, where its user registers will live;
• a user page table, from proc_pagetable (kernel/proc.c:175). It is empty of user memory, but it already maps two pages at the top: the shared trampoline page at TRAMPOLINE (0x3ffffff000) and this child’s own trapframe just below it at TRAPFRAME. Tour 25: A user address space walks these mappings bit by bit.

Each kalloc briefly takes kmem.lock, the lock on the shared free-page list (Tour 27: The physical page allocator). The page table needs three of them: one for the top-level page and two for the levels below that walk creates when the first mapping is added.

Either allocation can fail. Then freeproc undoes whatever was done (it checks each pointer before freeing), sets the slot back to UNUSED, and the lock is released. The table is left exactly as it was.

Step 7 of 20

Rigging the first context switch

A process starts running when some scheduler calls swtch into its saved context: swtch loads ra, sp and the callee-saved registers and executes ret, which jumps to ra (Tour 13: swtch and the lock handed across a context switch). A brand-new process has never run, so there is no real saved context. These lines forge one:

• ra = forkret: the ret at the end of swtch will “return” into forkret (address 0x8000193a in this build).
• sp = p->kstack + PGSIZE: the top of the child’s kernel stack. Each slot’s stack was mapped at boot by proc_mapstacks at KSTACK(slot). For slot 2 that is 0x3fffff9000, so sp = 0x3fffffa000, exactly what gdb printed.

Everything else is zeroed by memset. forkret does not care about the other callee-saved registers, because it is the first function on an empty stack.

Note what is not copied: the shell’s kernel stack. Right now two kernel stacks are involved, and they look nothing alike:

sh's kernel stack (KSTACK(1))      child's kernel stack (KSTACK(2))
  top 0x3fffffc000 ─► usertrap       top 0x3fffffa000 ─► (empty)
                      syscall                             ▲ context.sp
                      sys_fork                            context.ra = forkret
                      kfork
                      allocproc ◄─ sp

The child never made the fork call, so it has no frames to inherit; the shell’s frames would be meaningless to it. Its stack page was not allocated by fork either: it was mapped at boot and has belonged to slot 2 ever since (Tour 24: The kernel page table and turning paging on). Whatever an earlier occupant of slot 2 left in it is simply below the new sp and will be overwritten.

allocproc now returns np, still locked.

Step 8 of 20

Copying the shell's memory

Back in kfork, uvmcopy gives the child a private copy of every user page the shell has. The shell’s size p->sz is 0x5000 (five pages; Tour 25: A user address space draws them):

If the copy fails (out of memory), uvmcopy has already freed the pages it copied; freeproc then frees the page-table pages and the trapframe, and fork returns -1. Line 276 records the size only after success. Until then np->sz is 0, which is why uvmcopy must clean up after itself.

This is the expensive part of fork, and it is mostly wasted: in a moment the child will call exec, which throws all five copies away (Tour 22: exec). Real kernels avoid the waste with copy-on-write; xv6 keeps the simple version.

Step 9 of 20

uvmcopy, page by page

uvmcopy steps through the parent’s addresses a page at a time, i = 0x0, 0x1000, …, 0x4000. For each:

1. walk finds the parent’s PTE (page-table entry) (without allocating). Unmapped pages are skipped; that is how lazily allocated holes survive a fork (Tour 26: sbrk, eager and lazy, and page faults).
2. pa is the parent’s physical page, flags its permission bits.
3. kalloc a fresh page and memmove all 4096 bytes. This works because the kernel can reach any physical page at its own address (direct map).
4. mappages maps the copy at the same virtual address with the same flags in the child’s table.

Same address and same flags, so the child’s memory looks exactly like the shell’s. Even the guard page at 0x3000 keeps its missing U bit: the child gets a guard too.

The page at 0x4000 is the shell’s user stack, and it is copied like any other page: uvmcopy neither knows nor cares that it is a stack. So the child gets the shell’s stack frames byte for byte (start’s and main’s frames, which hold saved registers and return addresses, and fork1's frame with its return address into main), and since its saved sp will also be the shell’s (next step), it will resume on its own copy as if it had made the call itself.

Five pages, five kallocs, 20 KiB copied, plus the page-table pages mappages needs below the top level. The failure path (err:) unmaps and frees the i/PGSIZE pages already copied, so a half-copied child leaks nothing.

Step 10 of 20

Registers, and the one that differs

Line 279 is a C struct assignment: it copies the shell’s whole trapframe, 288 bytes, into the child’s. The child gets the shell’s sp, ra, s0…, and above all its epc, 0xc84, already past the ecall. When the child first reaches user mode it will continue at the ret of the fork stub, just like the parent.

Line 282 is the only difference: the child’s saved a0 becomes 0. Since a0 carries a system call’s return value, fork() returns 0 in the child, while the parent’s a0 will get the pid 3. That one register is how the two identical programs tell themselves apart (if (fork1() == 0)).

The copied sp, 0x4f80 in our run, is right for the child: the same address in its own copy of the stack page. The copy also brings across fields that are wrong for the child: kernel_sp is the top of the shell’s kernel stack (0x3fffffc000), kernel_hartid is hart 0. Harmless: prepare_return rewrites all the kernel fields on the child’s way out to user mode (step 18), before the child can ever trap.

Step 11 of 20

Sharing open files and the current directory

The child gets the same file descriptors, pointing at the same open files. Copying a struct file * pointer creates a second user, so filedup bumps the file’s reference count, and idup does the same for the current directory’s inode.

The shell has descriptors 0, 1 and 2, all pointing at one struct file for the console: init opened it once and duped it twice (3 references), and forking the shell added 3 more. So this loop takes that count from 6 to 9. Its other 13 descriptors are empty.

This sharing is what makes redirection work: ls’s output goes wherever the shell’s descriptor 1 goes, and a parent and child sharing a file also share its offset.

The counts live in shared tables, so filedup takes ftable.lock and idup takes itable.lock, each for a few instructions, nested inside proc[2].lock. That nesting is safe because filedup and idup take no other lock, and no code holds ftable.lock or itable.lock while waiting for a p->lock.

Step 12 of 20

Name, pid, and a lock let go

safestrcpy copies the name, so the child is also called sh until exec renames it. (That is why our gdb log shows pid=3 name=sh calling sbrk before it becomes ls.) The pid is saved in a local because np->pid may only be read under np->lock, and the lock is about to go.

Line 294 then releases the child’s lock. The child is complete but still USED, so no scheduler will run it. Releasing pops the last push_off, so interrupts come back on after that line.

Why let go now, only to take the same lock again at line 300? Because the next step needs wait_lock, and xv6’s rule is that wait_lock must be acquired before any p->lock, never after (kernel/proc.c:26). Taking wait_lock while still holding np->lock would break that order, and the next step shows the deadlock that would follow.

Step 13 of 20

Recording the parent under wait_lock

np->parent = p records that the shell is the child’s parent. The parent field is not protected by p->lock but by the global wait_lock (kernel/proc.h:92), because the code that reads it looks at other processes’ parent fields: kwait scans the table for pp->parent == p, and reparent in a dying process rewrites its children’s parents. One global lock gives all of them a consistent view of the family tree.

The parent is set before the child becomes runnable (next step). So by the time the child can run, and therefore by the time it could possibly call exit, its parent is the shell, and kexit's wakeup(p->parent) will reach the right process.

Step 14 of 20

Publishing the child

The last write, under np->lock again: state = RUNNABLE. This single store is the moment of publication. Before it, the child is invisible to every scheduler; after it, any hart may pick it up.

The order of the whole function is built around this line:

1. build everything (memory, registers, files, name) while the slot is USED;
2. set the parent;
3. only then, RUNNABLE.

Publishing last means no scheduler can ever see a half-built process. And the lock around the store does more than serialize it: release contains a memory fence (memory barrier (fence)), so every earlier write (the trapframe copy, the page table, the file pointers) is visible to the other harts before RUNNABLE is. A scheduler that takes proc[2].lock and sees RUNNABLE is guaranteed to see the finished child, not stale memory (Tour 19: Memory ordering across harts).

Step 15 of 20

The parent goes back to wait

kfork returns 3. syscall stores it into the shell’s saved a0, and the shell returns to user mode the way every system call does (Tour 5: Life of a system call). fork1() returns 3, which is not 0, so the shell skips runcmd and calls wait(0). On the way out, the shell’s kernel stack emptied frame by frame as the functions returned, and userret reloaded the user sp from the trapframe: hart 0 is back on the user stack it left at the ecall.

The shell now goes to sleep in kwait until its child exits. Tour 21: exit, wait and zombies follows that half of the story: the zombie, the reaping, and why wait_lock is held while the shell decides to sleep.

From here on the parent and the child run independently. Which one runs first, and on which hart, is up to the schedulers. In our gdb run both happened to land on the same hart; we follow the case where the child starts on a different one, because that is what the code must be prepared for.

The same-hart case is the common one. Nothing tells an idle hart that a process became RUNNABLE; hart 2 only notices at its next timer tick, up to about 0.1 s later. Meanwhile the shell goes to sleep in kwait almost at once, and hart 0’s own scheduler, resuming its scan just after the shell’s slot, finds slot 2 immediately.

Step 16 of 20

Hart 2's scheduler finds the child

The next timer interrupt pulls hart 2 out of wfi. Its scheduler sweeps the table, taking each lock in turn. At slot 2 it finds RUNNABLE.

Holding proc[2].lock, it sets the state to RUNNING, records the process in c->proc (this hart’s struct cpu), and calls swtch, saving the scheduler’s own registers in c->context and loading the child’s forged context.

Until that swtch, hart 2 runs on its scheduler stack: the same 4 KiB slice of stack0 it booted on, which became the scheduler stack when main called scheduler and never returned. It belongs to the hart, not to any process, and it has no guard page.

The lock is not released before the switch. It travels across swtch with the thread of control: the scheduler took it, and the child, on the far side, will release it (Tour 13: swtch and the lock handed across a context switch tells that story in full). Until then, no other hart can see slot 2 in the inconsistent state “marked RUNNING but not actually running yet”.

Step 17 of 20

swtch "returns" into forkret

swtch loaded sp = 0x3fffffa000 (line 26, kernel/swtch.S:26) and ra = forkret, and its final ret jumped there. That ld sp is the moment hart 2 leaves its scheduler stack (where swtch just saved the scheduler’s sp into c->context) for the child’s kernel stack. gdb at forkret’s first instruction: sp=0x3fffffa000, the very top. The child is running for the first time, on hart 2, on its own empty kernel stack. The call stack shows only forkret: there is nothing beneath it, no usertrap, no syscall, because the child never made the fork call. It only inherited its result.

myproc now says pid 3, because the scheduler set c->proc. The first thing to do is release p->lock, the lock hart 2’s scheduler acquired. (A process returning to the scheduler via sched would release it in its own code after sched returns; a new process has no such code, so forkret does it.)

That release does not turn interrupts on. The noff and intena it consults are the ones the scheduler left: it acquired p->lock with interrupts already off, so intena is 0, and line 520 takes noff from 1 to 0 with interrupts still off (Locks and interrupt state, Locks and interrupt state). They come on only when sret enters user mode.

The first block runs only once per boot, for init, to set up the file system and exec /init. For our child it is skipped.

Step 18 of 20

forkret leaves for user space

forkret now does what the end of usertrap does, by hand:

• prepare_return turns interrupts off and refills the kernel fields of the trapframe: kernel_sp = the top of the child’s kernel stack (0x3fffffa000), kernel_hartid = 2, the kernel page table and the address of usertrap. The stale values copied from the shell in step 10 are gone. It also sets sepc to the saved epc, 0xc84.
• MAKE_SATP builds the satp value for the child’s page table.
• It calls userret at its trampoline address, TRAMPOLINE + (userret - trampoline) = 0x3ffffff09c, passing satp in a0.

From userret on it is the return path of Tour 5: Life of a system call: fence.i, switch satp to the child’s table, reload the 31 registers from the trapframe (with a0 = 0), and sret.

Inside userret the page table changes first and sp second. After csrw satp (kernel/trampoline.S:111) sp still holds a kernel-stack address that the child’s page table does not map, so there is no usable stack from here until sret; ld sp, 48(a0) (kernel/trampoline.S:118) loads the child’s user sp, which becomes usable only when sret returns to user mode. forkret’s frame is never popped: it is simply abandoned, and the next trap starts again at kernel_sp, the top.

Step 19 of 20

The child sees fork() return 0

sret lands at 0xc84, the ret in the fork stub, with a0 = 0. The stub returns, fork1 returns 0, and line 172’s test succeeds. This process takes the other branch: runcmd(parsecmd(cmd)).

Everything the child sees is the shell’s world: buf still contains "ls\n" (it is at 0x2020 in the child’s copy of the data page), sp resumes at the shell’s 0x4f80 (0x4f90 once fork1 returns) and the user stack holds the same frames, descriptors 0–2 are the console. The only differences are the return value and everything the program cannot see: a different pid, different physical pages, a different kernel stack (empty again, since nothing of the child’s runs in the kernel while it is in user mode).

parsecmd will grow the child’s heap by 64 KiB (Tour 26: sbrk, eager and lazy, and page faults), and runcmd will call exec("ls", argv) (Tour 22: exec), which discards everything fork just copied.

Step 20 of 20

What one fork cost

Count it up. To run ls, fork took 11 pages from the allocator: 1 trapframe, 5 copies of user pages, and 5 page-table pages (the top level, plus a level-1 and a level-0 page for the trampoline and trapframe at the top, and another pair for user memory at the bottom). That is 44 KiB for a process that will throw its memory away a moment later, when it calls exec.

It took six kinds of lock: each p->lock in turn during the scan (including the shell’s own slot 1), pid_lock, kmem.lock once per page (11 times), ftable.lock (3 times), itable.lock, and wait_lock. And it followed three rules that recur across xv6:

• Claim under a lock: see UNUSED and write USED without letting go.
• Publish last: make the object runnable only when it is complete, under its lock, so the release fence publishes everything before it.
• Respect the lock order: wait_lock before p->lock, even if it means releasing a lock and taking it again.

Stacks cost nothing extra: the user stack was one of the five copied pages, and the child’s kernel stack was already waiting in slot 2, mapped at boot. The only “stack work” fork did was two stores: context.sp and context.ra.

Two copies of the shell now exist, distinguishable only by one register (in our staging, one on hart 0 and one on hart 2). Next, the child turns into ls (Tour 22: exec).