Step 1 of 19

The shell went to sleep in wait

Rewind a little. Right after forking ls (Tour 20: fork), the shell called wait(0) on hart 0. The argument is where to store the child’s exit status; the shell passes a null pointer because it does not care. (wait is a stub; SYS_wait is 3.)

sys_wait fetches the address with argaddr and calls kwait. The next two steps show what kwait did then, on hart 0, while ls was still being built. Everything after that is ls’s exit on hart 2.

A parent that never calls wait leaves its zombies around until it exits itself; then they pass to init, which always waits (step 18).

Step 2 of 19

kwait's first scan finds a live child

kwait takes wait_lock first, and keeps it for the whole scan and right up to the decision to sleep. The parent fields it reads are protected by that lock (kernel/proc.h:92).

The scan walks all 64 slots looking for pp->parent == p. Only slot 2, the child, matches. For it, kwait also takes the child’s p->lock, because state (and later xstate and pid) are protected by p->lock. The lock order is wait_lock then p->lock, the order used everywhere.

The child is not a ZOMBIE yet (it is RUNNABLE, RUNNING, or briefly SLEEPING on a disk read while exec loads ls), so line 403 releases its lock and the scan continues. havekids is 1.

Step 3 of 19

Registering, then sleeping

The shell has a child, has not been killed, and no child is dead yet, so it must wait.

sleep_prepare(p) registers the shell as waiting on the channel p, its own struct proc address (&proc[1]). The channel is just a number both sides agree on; a dying child will call wakeup on its parent pointer, which is the same address.

Then, in this order: release wait_lock (line 415), then sleep (line 416). The shell is registered before it lets go of wait_lock. Step 16 shows the race this ordering defeats.

What does the sleeping shell leave behind? Only its kernel stack, frozen, and the sp and ra that swtch saved in p->context before moving hart 0 to its scheduler stack (kernel/swtch.S:26):

sh's kernel stack (KSTACK(1), top 0x3fffffc000)
  top ─► usertrap   32 bytes
         syscall    32
         sys_wait   32
         kwait      80
         sleep      32
         sched      48
         ◄─ p->context.sp (256 bytes below the top)

Its user stack, the page at 0x4000 in its own page table, is untouched since the ecall; the user sp waits in the trapframe (The stacks of xv6).

The shell is now SLEEPING, and (in our staging, where hart 2 has taken ls) hart 0’s scheduler finds nothing else to run and waits in wfi. When it wakes, sleep returns and line 417 takes wait_lock again before rescanning: the for (;;) loop means every wakeup leads to a fresh scan, never to an assumption.

Step 4 of 19

ls finishes

Back to the present, on hart 2. ls was started with no arguments, so it listed . and now calls exit(0). The stub puts SYS_exit (2) in a7 and executes ecall; Tour 5: Life of a system call has the trip into the kernel.

exit never returns, in user space or in the kernel. Even a main that just returns ends here, because start calls exit(main(...)) (user/ulib.c:17).

The status, 0, means success. It will travel through the child’s struct proc, the xstate field, to whoever waits for it.

Step 5 of 19

sys_exit calls kexit

sys_exit fetches the status with argint and calls kexit. The return 0 is never reached; it exists only to keep the C compiler happy about a function that returns uint64.

Hart 2 is on ls’s kernel stack, the page at KSTACK(2) that uservec switched to at the ecall. Keep an eye on it: kexit will run on this stack to the very end, and the stack will outlive ls.

kexit is also called by usertrap when a process has been killed (kernel/trap.c:58 before a system call, kernel/trap.c:82 after any trap), with status -1 (Tour 23: kill). That is the same function, so everything below applies to a killed process too.

Step 6 of 19

Closing every open file

kexit first checks that it is not init (if init exited, orphans would have no one to reap them, so the kernel panics instead).

Then it closes all 16 descriptor slots. ls has three: 0, 1 and 2, all pointing to the single console open file (struct file) that init opened at boot. Its reference count is 9 (3 from init, 3 from the shell, 3 from ls), so these three fileclose calls take it to 8, 7, 6. None reaches zero, so the file stays open for the shell and init. (ls opened . while listing, but closed it itself.)

Why close files here, in exit, rather than leave it to the parent’s wait? Because closing can have effects other processes are waiting for: closing the last write end of a pipe is what tells the reader “end of file” (Tour 39: Pipes). That should happen when the process dies, not whenever its parent gets around to waiting.

Step 7 of 19

Letting go of the current directory

p->cwd is a counted reference to the root directory’s in-memory inode. iput drops it.

Why wrap a mere reference drop in a transaction (begin_op … end_op)? Because iput might write to the disk: if this were the last reference to an inode with no links left (a directory deleted while the process sat in it), iput would free its blocks and its on-disk inode. Every file-system write goes through log_write, which must be inside a transaction (Tour 31: The log: begin_op, commit and group commit). For the root directory nothing is written, but kexit cannot know that in advance.

begin_op may sleep (if the log is being committed or is too full). That is one more reason this happens early, before kexit takes any spinlock: a process holding a spinlock must never sleep.

Step 8 of 19

Taking wait_lock and giving children away

kexit now takes wait_lock (kernel/proc.c:347) and calls reparent. From here on, interrupts are off on hart 2.

reparent looks for processes whose parent is ls. If it finds one, it makes initproc the new parent and wakes init, in case that child is already a zombie waiting to be collected. ls has no children, so the loop finds nothing.

Without this, a dead process’s children would still point at the freed slot. If nobody reused it, no one would ever reap them; if a new process took the slot, it would wrongly find them as its own children.

Note that reparent reads every pp->parent without taking pp->lock. That is correct: parent is protected by wait_lock, which hart 2 holds, so no other hart can be changing any parent field right now.

Step 9 of 19

Waking the parent, before dying

p->parent is the shell’s struct proc, &proc[1]: the channel the shell registered on. wakeup walks the whole table taking each p->lock in turn. At slot 1 it finds the shell with chan == &proc[1], clears chan, and since the shell is SLEEPING, makes it RUNNABLE.

It looks premature: ls is not a zombie yet. But the shell cannot see ls in any in-between state, because the first thing the shell does after waking is acquire(&wait_lock) (line 417), and hart 2 holds wait_lock until ls is fully a zombie. Waking early just lets the shell start moving sooner.

Notice also what hart 2 does not hold yet: its own p->lock. wakeup visits every slot, including slot 2, and takes its lock. If kexit already held its own p->lock here, acquire would find it already held by this hart and panic (kernel/spinlock.c:25). So the order inside kexit is forced: wake first, then lock itself.

Step 10 of 19

Becoming a zombie

Now ls takes its own p->lock (order: wait_lock, then p->lock, as always) and writes two fields that are protected by it:

• xstate = 0, the exit status, kept for the parent;
• state = ZOMBIE.

A zombie has no open files and no current directory, but it still has its user memory, its page table, its trapframe, its kernel stack and its slot in the table. It does not free those itself: the slot must survive until the parent has read xstate, and the slot, which comes with its kernel stack (kernel stacks are never freed in this version, step 15), must not be handed back while this hart is still running on that stack. xv6 puts all the freeing in one place, freeproc, run by the parent.

Look at where hart 2 is standing while it writes ZOMBIE:

ls's kernel stack (KSTACK(2), top 0x3fffffa000)
  top ─► usertrap
         syscall
         sys_exit
         kexit  ◄─ sp

A function cannot free the stack it is running on: kfree would fill the page with junk while the function’s own frames and return addresses are still in it, and another hart could kalloc the page at once. xv6 never needs to. A kernel stack belongs to the slot, not the process, so nobody frees it at all; it just must not be reused until ls has left it.

Then line 360 releases wait_lock, but not p->lock. The shell, spinning on hart 0, gets wait_lock now and starts its scan. When it reaches slot 2 it will need ls’s p->lock, which hart 2 is still holding. Hold that thought.

Step 11 of 19

Into the scheduler, never to return

kexit calls sched, which checks the rules for giving up the CPU: hold exactly one lock (p->lock), interrupts off, state no longer RUNNING. All true. swtch saves ls’s registers into p->context and resumes hart 2’s scheduler thread.

Inside that swtch, line 26 (ld sp, 8(a1), kernel/swtch.S:26) is the last instruction hart 2 executes with ls’s stack in mind: line 11 (sd sp, 8(a0), kernel/swtch.S:11) already saved sp into p->context (pointing at sched’s frame), and line 26 moves sp to hart 2’s scheduler stack. ls’s kernel stack is left exactly as it is, usertrap → syscall → sys_exit → kexit → sched, and no hart will ever look at those frames again.

For any other process, that saved context would be resumed some day. Not this one: no scheduler will ever pick a ZOMBIE, so sched never returns into kexit, and line 496 and the panic("zombie exit") on kernel/proc.c:364 never run for it.

Step 12 of 19

Hart 2's scheduler lets go of the zombie

swtch “returns” into scheduler on hart 2, just after the swtch call on line 453 that started ls running some time ago. Hart 2 is now on its own scheduler stack, its slice of stack0, which belongs to the hart, not to any process.

The code after the swtch sets c->proc = 0 and releases ls’s p->lock (line 463). The lock was taken by ls in kexit and is released here, on the far side of the switch, by the scheduler (Tour 13: swtch and the lock handed across a context switch). Only now, with hart 2 running on its own stack and no longer touching ls’s kernel stack, is the zombie completely still.

That is why the release has to wait until this point. If ls released its own lock before calling sched, the parent could free the slot while hart 2 was still pushing and popping on the slot’s kernel stack in sched and swtch. A later fork could then hand that stack to a new process, and two harts would be using one stack.

One line before the release, line 456 sets mycpu()->intena = 0. Hart 2’s struct cpu still held ls’s intena (1, from its system call), and without that line the release on line 463 would turn interrupts on in the middle of the scheduler loop (Locks and interrupt state).

Step 13 of 19

The parent's scan finds the zombie

The shell, back from sleep (on hart 0 in our staging; it could be any hart) and holding wait_lock, rescans. Slot 2’s parent is the shell, so it takes slot 2’s p->lock. The source comment on line 383 says why: make sure the child isn’t still in exit() or swtch().

Suppose the shell did not take that lock and freed the zombie the moment it saw ZOMBIE. Hart 0’s freeproc would free the trapframe and page table and set state = UNUSED and pid = 0, while hart 2 is still running as ls: still in sched and swtch, myproc() still returns slot 2, and it still writes ls’s context. The fields state, xstate and pid would be written by two harts with no common lock (the rule in kernel/proc.h:85).

In this version a new fork still could not grab the slot too early, but only because allocproc must acquire proc[2].lock (kernel/proc.c:115), which hart 2 holds until its scheduler releases it (kernel/proc.c:463). Taking pp->lock in kwait makes the guarantee direct: once the parent holds it, the child’s hart has finished with the slot and its kernel stack, so the parent can dismantle it.

Here the scan finds state == ZOMBIE, and pid = 3.

Step 14 of 19

Delivering the exit status

If the caller passed an address, copyout writes the 4-byte xstate into the caller’s memory, using the caller’s page table (p is the shell here). The shell passed 0, so this is skipped; our gdb run printed addr=0x0.

A caller that cares looks like usertests’s run() (user/usertests.c:3427): wait(&xstatus) with xstatus on its user stack. Then copyout walks the parent’s page table to find the physical page and writes 0 there (Tour 28: Crossing the user/kernel boundary in memory).

If the copy fails (a bad pointer), wait returns -1 and leaves the zombie in place, so the status is not lost and a later wait can still collect it.

Notice that copyout runs with two spinlocks held and interrupts off. That is allowed only because copyout never sleeps: even if the address lies in a lazily allocated page that is not mapped yet, vmfault allocates it with kalloc, which may spin briefly on kmem.lock but never sleeps.

Step 15 of 19

Freeing the husk

kwait clears pp->parent and calls freeproc, which frees what the zombie could not free itself:

• the trapframe page, with kfree;
• the user memory and the page table, with proc_freepagetable. For ls that is 4 user pages (code, data, guard, stack; sz = 0x4000) and 5 page-table pages. The trampoline is unmapped but not freed: it is the kernel’s own code, shared by every process.

Then it wipes the fields and sets state = UNUSED. The slot is free for the next fork (Tour 20: fork); the next command the shell runs will get slot 2 again, as pid 4.

Two stacks, two fates. ls’s user stack, the page at 0x3000, is one of those 4 user pages: it goes back to the free list here, with the user page table. Its kernel stack is not freed: each slot’s stack was mapped once at boot (proc_mapstacks) and is reused by whoever occupies the slot. The frames ls left there (usertrap … kexit → sched) are never popped; the next occupant’s first swtch simply starts at the top again (context.sp = kstack + PGSIZE, kernel/proc.c:147).

Finally the locks are released in reverse order, and kwait returns 3. syscall puts 3 in the shell’s a0, and the shell prints its next $ .

Step 16 of 19

The lost wakeup that wait_lock prevents

Go back to step 3. Why must kwait hold wait_lock from the start of its scan until after sleep_prepare? Imagine it released the lock right after the scan:

The shell would hang with a zombie child it never collects. With xv6’s order, ls cannot reach its wakeup until the shell releases wait_lock, and by then the shell is registered. If the wakeup then comes between line 415 and line 416, it clears the shell’s chan, and sleep sees chan == 0 and returns at once (Tour 16: sleep and wakeup, and the lost-wakeup problem).

This is the general recipe: the condition (“is there a zombie?”) and the registration must be covered by the same lock that the waker holds when it changes the condition. Here that lock is wait_lock.

Step 17 of 19

When the parent dies first

ls had no children. To see reparent earn its keep, run the test program zombie. It forks; the child exits at once; the parent pauses 5 ticks and then exits too, without ever calling wait.

1. The child exits: it becomes a ZOMBIE, and its wakeup(p->parent) finds nobody waiting on that channel. It stays a zombie.
2. Five ticks later the parent exits. Inside its kexit, reparent finds the zombie child, sets its parent to initproc, and calls wakeup(initproc).
3. init, asleep in kwait on channel initproc, wakes up, rescans, finds a zombie child, and frees it.

The order inside kexit matters here too: reparent runs under wait_lock, so the parent’s own exit and init’s scan cannot interleave. init sees either the old parent (and the zombie is not its child) or the new one, never a half-changed tree.

Step 18 of 19

init, the reaper

init’s inner loop is a dedicated reaper. It calls wait, and:

• if the result is the shell’s pid, the shell has exited (you typed Ctrl-D); break out and start a new shell;
• if it is any other pid, it was an orphan that init inherited; ignore it and wait again;
• if wait fails, something is very wrong.

init never cares about the status, so it passes 0, like the shell.

Most of the time init is asleep in kwait on its own channel. Three things wake it: its child the shell exiting, reparent handing it the children of a dying process, and an already-adopted orphan exiting later. All call wakeup(initproc), so one sleep covers every case, and the loop in kwait sorts out which happened by rescanning.

Step 19 of 19

What dying cost

Look at the whole of kexit once more. Its last part is a short critical section under wait_lock, and everything slow (closing files, the log transaction) happens before it, while no spinlock is held.

The protocol in one table:

Three ideas carry it. A process cannot hand back the slot it is still running in, and its parent still needs its exit status, so death has two halves. A lock held across a context switch tells another hart when the switch is complete. And a waiter must register under the same lock the waker takes, or the wakeup can be lost. ls is gone; slot 2 is UNUSED; the shell prints $ .