Step 1 of 22

wc asks for its first 512 bytes

wc was started with no arguments, so main calls wc(0, ""): count the lines, words and bytes of standard input. Line 16 calls read(0, buf, 512).

Descriptor 0 is the read end of the pipe the shell built (user/sh.c:114). Through the usual system-call path (Tour 5: Life of a system call) this arrives in sys_read, then fileread, which sees FD_PIPE and calls piperead.

Right now the pipe is empty. cat on hart 1 has not written anything yet: it is still waiting for the disk to deliver the first block of README. So wc is about to discover that it has nothing to do, and that it must wait for an event that will happen on a different CPU.

The question for this whole tour: how can wc go to sleep in a way that can never miss cat’s wakeup, no matter how the instructions on the two harts interleave?

Step 2 of 22

piperead takes the pipe lock and finds it empty

piperead acquires pi->lock, so interrupts go off on hart 2 (Tour 15: Spinlocks from the hardware up). Then it tests the condition it needs: is there data? nread == nwrite means every byte ever written has been read: the pipe is empty. writeopen is still 1, because cat holds the write end open, so more data may still come and waiting makes sense. (If every writer had closed it, piperead would skip the loop and return 0: end of file.)

The condition (nread == nwrite && writeopen) is protected by the condition lock pi->lock. That pairing is the heart of every sleep in xv6: a condition, a lock that protects it, and a channel, an address both sides agree to use as the name of the event. Here the channel is &pi->nread, “the reader is waiting for nwrite to move past nread”.

Line 120 checks killed: a killed process must not start a long wait. killed takes wc’s own p->lock while pi->lock is held, which fixes a lock order you will see again and again on this path: pi->lock first, then p->lock.

Step 3 of 22

Register on the channel while still holding the condition lock

piperead calls sleep_prepare(&pi->nread) on line 124, before it releases pi->lock. sleep_prepare takes wc’s p->lock (the field chan is protected by it, kernel/proc.h:87) and records the channel: p->chan = &pi->nread.

That is all. wc does not go to sleep here. Its state is still RUNNING. It has only announced: “from now on, a wakeup on &pi->nread concerns me”.

The timing is everything. At this moment wc holds pi->lock, so cat cannot have changed the pipe since wc looked at it. Any cat that adds data must first acquire pi->lock, which it can only do after wc releases it on the next line, which is after p->chan is set. So any wakeup caused by new data is guaranteed to find wc registered. The check and the registration are atomic with respect to the waker, because the same lock covers both (Locks and interrupt state).

A zero channel is forbidden (line 552): p->chan == 0 is how wakeup says “you have been woken”, so 0 cannot also mean a real channel.

Step 4 of 22

How older xv6 did it, by handing the lock to sleep

If you have read the xv6 book or an older xv6-riscv, you met a different sleep. It took the channel and the condition lock. This is that older code, not the code at this commit:

// older xv6 (not this version)
void sleep(void *chan, struct spinlock *lk) {
  struct proc *p = myproc();
  acquire(&p->lock);
  release(lk);
  p->chan = chan;
  p->state = SLEEPING;
  sched();
  p->chan = 0;
  release(&p->lock);
  acquire(lk);
}

and piperead called sleep(&pi->nread, &pi->lock). The trick was a lock hand-over: take p->lock before dropping lk, so there is no instant when the sleeper holds neither. Since wakeup needed p->lock too, and the waker held lk, the waker ran either entirely before the check or after the sleeper was fully asleep.

This version splits the job in two. sleep_prepare registers under lk; the caller releases lk itself; sleep sleeps only if nobody has cleared the registration in between. Same guarantee, but sleep no longer needs to know about any condition lock, which, as you will see at the end, lets the UART driver sleep without having one.

Step 5 of 22

The gap between release and sleep

Line 125 releases pi->lock. wc now holds no lock at all, and interrupts are back on on hart 2. Line 126 is about to call sleep.

Between those two lines lies the dangerous gap. Anything can happen in it: cat on hart 1 can grab the pipe lock, fill the pipe and call wakeup; a timer interrupt can even make wc yield hart 2 and run again much later. In a naive design that is exactly where the wakeup gets lost.

Here, it cannot be lost, because wc is already registered: whatever wakeup happens in the gap clears wc’s p->chan. When wc finally enters sleep(), the first thing sleep does is look at p->chan. Zero means “your event already happened”, and sleep returns without sleeping.

Why release the lock before sleeping at all? Because cat needs pi->lock to add the data wc is waiting for. A sleeper that kept the condition lock would wait forever for a waker that cannot get in.

Step 6 of 22

What the gap would do without registration

To see what sleep_prepare buys, imagine a broken piperead that checks the condition, releases the lock, and then registers and sleeps in one step, as a careless designer might write:

// BROKEN, for illustration only
while (pi->nread == pi->nwrite && pi->writeopen) {
  release(&pi->lock);
  register_and_sleep(&pi->nread);   // hypothetical
  acquire(&pi->lock);
}

The window between the release and the registration is the classic race condition. It is tiny, a few dozen instructions, so the bug might appear once in a million runs, and it would appear as a stall or a hang, not a crash: wc stays asleep next to data until some later wakeup(&pi->nread) happens to rescue it. With cat, one will come (its next write calls wakeup on line 89 or 105, and its exit calls pipeclose), but a writer that sends one message and then waits for an answer, on a second pipe, say, never calls wakeup again, and both processes hang forever.

The real code moves the registration inside the critical section, which turns the window into a harmless “already woken” state that sleep detects.

Step 7 of 22

sleep, for real this time

In our story cat is still waiting for the disk, so nothing has happened in the gap. sleep takes wc’s p->lock (interrupts off again; they were on, so push_off records intena = 1) and checks p->chan. It is still &pi->nread: no wakeup yet. So sleep marks wc SLEEPING and calls sched.

Notice that the check of p->chan and the change to SLEEPING happen under the same p->lock that wakeup must take to clear p->chan. So wakeup either runs entirely before line 567 (and sleep returns at once) or entirely after wc has been switched off the CPU. The window from step 5 is closed at both ends: at the start by registering under pi->lock, at the end by deciding under p->lock.

wc’s state is now SLEEPING and p->chan names what it waits for. No scheduler on any hart will pick it, because schedulers only run RUNNABLE processes.

Step 8 of 22

sched insists on exactly one lock

sched runs four sanity checks before switching away. Line 487 is the one that matters for sleeping: mycpu()->noff must be exactly 1. One spinlock held, and it must be p->lock (line 485).

This is why piperead had to release pi->lock itself before calling sleep(), and why this version’s sleep takes no lock argument. Suppose wc went to sleep still holding pi->lock:

• cat on hart 1 would call acquire(&pi->lock) and spin, with interrupts off, for as long as wc sleeps.
• wc sleeps until someone writes to the pipe.
• The only someone is cat, spinning.

A deadlock, and hart 1 would be lost too: with interrupts off it cannot even take a timer interrupt to run something else. The noff != 1 check turns that silent hang into an immediate panic("sched locks").

p->lock is the single exception, because swtch hands it to the scheduler, which releases it (Tour 13: swtch and the lock handed across a context switch). Before switching, sched also saves wc’s intena (1) in a callee-saved register, so that whichever hart resumes wc gets it back (Locks and interrupt state).

Step 9 of 22

Hart 2's scheduler lets go of wc

swtch saved wc’s registers into wc’s p->context and loaded hart 2’s scheduler context. Execution continues right after the swtch on line 453, where hart 2’s scheduler last switched to wc.

The ld sp in swtch is where hart 2 changed stacks: from wc’s kernel stack to its own scheduler stack, the 4 KiB slice of stack0 it has used since boot (The stacks of xv6). wc’s kernel stack stays behind, frozen:

wc's kernel stack, while wc sleeps
  top ─► usertrap
         syscall
         sys_read
         fileread
         piperead
         sleep
         sched     ◄─ wc->context.sp

The scheduler sets intena = 0 (line 456, so that this release leaves interrupts off: Locks and interrupt state), clears c->proc and, on line 463, releases wc’s p->lock: the lock that wc took in sleep(), carried across the switch, and released by a different thread (Locks and interrupt state). From this instant wc is a sleeping process that any hart’s wakeup can inspect.

Then hart 2 goes looking for other work. wc uses no CPU at all while it waits. That is the whole point of sleeping instead of spinning: three harts, and none of them is burning cycles polling an empty pipe.

Step 10 of 22

cat arrives with data and takes the pipe lock

The disk finishes, cat is woken and gets the first 512 bytes of README into its buf. It calls write(1, buf, 512), which reaches pipewrite on hart 1.

pipewrite acquires pi->lock, the same condition lock wc used. For each byte it checks two things:

• Is the read end still open, and is cat not killed? Otherwise writing is pointless. (killed takes cat’s p->lock under pi->lock: the same order as before.)
• Is the pipe full? nwrite == nread + PIPESIZE means 512 unread bytes are already waiting. The counters are never reduced modulo 512; only the index into data is (% PIPESIZE). So nwrite - nread is always the number of bytes in the pipe.

The pipe is empty, so cat takes the else branch for every one of its 512 bytes.

Step 11 of 22

512 bytes, one copyin each

Each byte travels from cat’s user memory into the ring with its own copyin of length 1, which walks cat’s page table by software. 512 page-table walks with a spinlock held and interrupts off: simple rather than fast. After the loop, nwrite is 512 and nread is 0. The condition wc was waiting for is now false: the pipe is not empty.

If copyin meets a page that was reserved lazily (with sbrklazy) and not yet touched, it calls vmfault, which calls kalloc, which takes kmem.lock. So the full nesting possible here is pi->lock → kmem.lock. cat’s buf is a global, allocated eagerly when exec loaded the program, so in our run that does not happen.

Holding a spinlock while copying from user memory is fine because copyin never sleeps: a bad address makes it return -1 (line 96), it does not wait for anything.

Step 12 of 22

wakeup, with the condition lock still held

Having made the condition false (“pipe empty”), cat announces it: wakeup(&pi->nread). Then it releases pi->lock and returns 512.

pipewrite calls wakeup before release. As step 4 explained, this version would also be correct with the two lines swapped, because wc registered under the lock. Calling it with the lock held is still the conventional, easy-to-check pattern: the condition change and the announcement form one critical section.

Note that cat does not know whether anyone is waiting, and does not care. It calls wakeup on every write. If nobody is registered on &pi->nread, wakeup changes nothing. That is cheap insurance: xv6 does not keep a “number of waiters” counter that could itself be got wrong.

Step 13 of 22

wakeup visits every process, under each one's lock

wakeup walks all 64 slots of the process table. For each, it takes that process’s p->lock and compares p->chan with &pi->nread. Under that lock a registered process is always in one of three clean states:

1. Not registered on this channel: skipped.
2. Registered but not asleep: in the gap of step 5 (RUNNING, or RUNNABLE if a timer made it yield there). wakeup clears p->chan only; its next sleep() returns at once.
3. Fully asleep: SLEEPING, registers saved by swtch, p->lock released by its hart’s scheduler. wakeup clears p->chan and sets RUNNABLE.

wc is in state 3. It becomes RUNNABLE: eligible to run, not running. (The source comment on line 588 says “RUNNING”; the code correctly sets RUNNABLE.)

wakeup wakes every process registered on the channel, not just one. Whoever runs first wins; the rest must cope (step 18).

Step 14 of 22

cat's next write finds the pipe full

cat returns to user space, reads the next 512 bytes of README (block 48 already held all of the first 1024 bytes, so this one is a cache hit), and writes again. Suppose wc has not run yet. Now nwrite == nread + 512: the pipe is full, and this time cat must wait, on the other channel, &pi->nwrite.

The same pattern, mirrored:

1. wakeup(&pi->nread): make sure a reader knows there is data. (Here wc is already RUNNABLE with chan == 0, so this changes nothing.)
2. sleep_prepare(&pi->nwrite) under pi->lock (the highlighted line; inside it, cat briefly holds its p->lock too, nested inside pi->lock, as in step 3).
3. Release pi->lock, sleep(), re-acquire, loop.

The first wakeup matters when the writer sleeps in the middle of a large write. Without it, a writer could fill the pipe and sleep without ever telling a reader, and the two would wait for each other.

Step 15 of 22

Hart 0 picks up wc

Hart 0 was idle in wfi. wakeup does not signal idle harts; hart 0 notices only when its next interrupt (usually its own timer tick, up to a tenth of a second later in QEMU) ends the wfi. In this telling that tick happens to come now: it loops, and its scheduler scans the table. At slot 5 it takes wc’s p->lock, sees RUNNABLE, marks it RUNNING, sets c->proc and calls swtch into wc’s saved context.

Until that swtch’s ld sp, hart 0 is on its own scheduler stack; after it, on wc’s kernel stack. wc went to sleep on hart 2 and wakes up on hart 0. Nothing in its kernel stack cares: the call chain usertrap → … → piperead → sleep → sched is intact, saved on wc’s own kernel stack (Tour 12: One scheduler per hart).

Which hart picks wc is a matter of timing. In practice hart 1 is a strong candidate: the moment cat sleeps, hart 1’s scheduler continues its scan at wc’s slot. But nothing in sleep remembers “my hart”.

Step 16 of 22

sleep returns on a different hart

sched returns into sleep, on hart 0, holding the p->lock that hart 0’s scheduler acquired. Line 571 releases it, and interrupts come back on as noff drops to 0 (sched restored the intena that wc had when it slept, kernel/proc.c:496, Locks and interrupt state).

sleep does not clear p->chan: wakeup already did that, and in the kill case (step 19) leaving it set is harmless because the next sleep() will be preceded by a fresh sleep_prepare.

And sleep returns no information. It does not say why wc woke up, or whether the pipe now has data. wc must find out for itself, under pi->lock.

Step 17 of 22

Re-check the condition, then take the bytes

wc re-acquires pi->lock and goes back to the top of the while: is the pipe still empty? No: nwrite - nread == 512. The loop exits and the copy loop moves up to 512 bytes to wc’s buf with copyout, one byte at a time, advancing nread. (Like copyin, copyout could call kalloc under pi->lock for a lazily reserved page.)

Then wakeup(&pi->nwrite): the pipe has room again, and cat, asleep on that channel since step 14, becomes RUNNABLE. Both directions of the pipe use the same handshake, with the roles swapped.

read returns 512. wc counts those bytes in user space and calls read again. The dance repeats until README’s 2441 bytes are through. When cat exits, closing the last write end, pipeclose sets writeopen = 0 and calls wakeup(&pi->nread), so a wc waiting on an empty pipe wakes, sees writeopen == 0, and returns 0: end of file.

Step 18 of 22

Why every sleep sits in a while loop

Line 119 is a while, not an if. A wakeup means “something happened on this channel”, never “your condition is now true”. There are several ways wc can come out of sleep() with the pipe still empty:

• Several readers. If two processes read the same pipe, wakeup(&pi->nread) wakes both. The first to get pi->lock takes all the data; the second finds the pipe empty again and must go back to sleep.
• Kill. kkill makes a sleeping victim RUNNABLE without any event at all (next step).
• Shared channels. One channel can stand for several conditions. begin_op waits on &log both for a commit to finish and for log space to free up.
• Wakeups without data. pipewrite calls wakeup(&pi->nread) on line 105 even when it copied nothing: for write(fd, buf, 0), or when the very first copyin fails.

So the rule throughout xv6: re-acquire the condition lock, re-test the condition, and sleep again if it does not hold. A wakeup that turns out to be useless costs one loop; trusting it could cost correctness.

Step 19 of 22

A kill is a wakeup with no event

Suppose some process calls kill(5) while wc sleeps on an empty pipe. kkill takes wc’s p->lock, sets killed = 1 and, because wc is SLEEPING, makes it RUNNABLE. It does not clear p->chan. No data arrived; the “wakeup” is fake.

wc returns from sleep() with p->chan still &pi->nread. That stale value is harmless: a later wakeup(&pi->nread) would clear it without changing wc’s state (state 2 of step 13), and the next sleep() is always preceded by a new sleep_prepare, which overwrites it.

Back in piperead, the while re-tests: the pipe is still empty, so it goes round again, and line 120’s killed check sees the flag and returns -1. wc then dies on its way back to user space (kernel/trap.c:81). This is why the killed test sits inside the loop, before each sleep, not once at the top.

Step 20 of 22

One channel, two conditions in begin_op

The same pattern appears all over xv6, and begin_op shows why the loop must re-test everything. A file-system call may not start while a commit is in progress (line 133), nor if its worst-case writes might overflow the log (line 138). Both waits use the single channel &log, under the condition lock log.lock.

end_op calls wakeup(&log) in two situations: after a commit finishes, and when a call ends without committing, freeing reserved space. Either one wakes every sleeper in begin_op, whatever it was waiting for. A process woken because a commit finished may find that the log is still too full; a process woken because space freed may find that a commit has started meanwhile. The while (1) re-runs both tests and sleeps again if needed. (sys_sync waits on &log too, for a commit to complete, so one channel actually serves three waits.)

Using one channel for two conditions is a deliberate simplification. It costs some useless wakeups and buys simpler code; the loop keeps it correct. (Tour 31: The log: begin_op, commit and group commit covers the log itself.)

Step 21 of 22

The UART sleeps with no condition lock

wc finishes counting and prints 48 336 2441 and a newline. User printf writes one character per write call (user/printf.c:12), so that is 13 trips into uartwrite, each with n = 1.

Here the “condition” is a bit in a device register, LSR_TX_IDLE. No kernel lock protects it: the UART changes it whenever it finishes sending, and the waker is uartintr, an interrupt handler that may run on any hart. There is no condition lock to hold across the check.

The split design handles it by ordering alone: sleep_prepare(&tx_chan) first, then read LSR. If the transmitter becomes idle after the read, its interrupt comes after the registration, so the wakeup clears p->chan and sleep() returns at once. The older sleep(chan, lk) needed a lock to hand over, so the older driver kept a software copy of the device state (a tx_busy flag) under a tx_lock spinlock that the interrupt handler also took. The split design lets uartwrite test the hardware bit directly, with no condition lock (Locks and interrupt state). Tour 5: Life of a system call walks through this exact loop.

When LSR says idle, uartwrite writes the byte and never sleeps, leaving p->chan set to &tx_chan. That stale registration is harmless, for the same reason as after a kill: every sleep() is preceded by a fresh sleep_prepare.

Step 22 of 22

What it took

wc has counted README: 48 lines, 336 words, 2441 bytes. At least five reads of the pipe returned data; each could have gone to sleep, been woken from another hart, and resumed on a third.

The key ideas:

• Register before you release. sleep_prepare records the channel while the condition lock is held, so a wakeup can never slip between the check and the registration.
• Decide under p->lock. sleep sleeps only if p->chan is still set, checked under the lock wakeup also takes. A wakeup in the gap becomes “return at once”.
• Only p->lock across the switch. sched panics if any other spinlock is held, because a sleeping spinlock holder would freeze every hart that wants it.
• Wakeups are hints. Every sleep sits in a loop that re-tests the condition and the killed flag.

Older xv6 got the first two by passing the condition lock into sleep. This version splits the work, which costs one extra p->lock round trip per sleep and buys a sleep that does not need a lock at all, as uartwrite shows. Tour 39: Pipes follows pipes further; Tour 17: Sleep-locks builds sleep-locks on top of this primitive.