Step 1 of 15

wc prints its answer

wc has counted README: 48 lines, 336 words, 2441 bytes. Line 33 prints "48 336 2441 README\n", 19 bytes, to file descriptor 1, the console.

wc inherited descriptor 1 from the shell, so it shares one open file (struct file) with cat, the shell and init: the same struct file, the same console. Nothing in wc knows that cat is printing at the same moment on hart 0, and nothing needs to. Arbitrating the screen is the kernel’s job.

Step 2 of 15

printf makes one system call per byte

xv6’s user printf has no buffer. vprintf walks the format string and sends every character through putc, which is write(fd, &c, 1) (user/printf.c:12). Numbers go through printint, which also calls putc once per digit.

So wc’s 19-byte line costs 19 write system calls, each carrying one byte all the way through Tour 5: Life of a system call's path. That is slow, but the important consequence here is different: to the kernel, wc’s line is not one request. It is 19 unrelated one-byte requests, and the kernel is free to put other output between any two of them.

A real C library buffers printf output and hands the kernel a whole line at once, which is one reason lines from different programs rarely break apart on Unix.

Step 3 of 15

cat writes 512 bytes at once

cat does the opposite: one read of up to 512 bytes from README, then one write(1, buf, n) of all of them. README is 2441 bytes, so cat makes five writes: 512, 512, 512, 512 and 393 bytes.

One write is one request to the kernel. Does that mean a 512-byte write reaches the screen in one piece? No. The next step shows the kernel cutting it into smaller pieces before it reaches the UART, and every cut is a place where someone else’s bytes can get in.

Step 4 of 15

consolewrite cuts every write into 32-byte batches

consolewrite has a 32-byte buffer on the kernel stack. For each batch it copies up to 32 bytes from the user with either_copyin and hands them to uartwrite. cat’s 512-byte write becomes 16 calls of uartwrite(buf, 32); the final 393-byte write becomes 12 calls of 32 bytes and one of 9.

Why batches? The bytes must be copied out of user memory before the device can see them, and a small fixed buffer on the kernel stack avoids allocating memory per write. The cost is the granularity you will meet next: uartwrite holds its lock for one batch, not for the whole write.

wc’s one-byte writes go through the same loop: one batch of 1 byte each.

“On the kernel stack” means cat’s own: the page of its process slot that uservec pointed sp at when cat executed ecall (kernel/trampoline.S:76; The stacks of xv6). It now holds usertrap, syscall, sys_write, filewrite, and consolewrite’s frame with buf in it. A kernel stack is one 4 KiB page with an unmapped guard page below it.

Step 5 of 15

uartwrite holds tx_lock for one batch

uartwrite took tx_lock on line 82 and now feeds the batch to the UART one byte at a time: register on tx_chan, check LSR, write THR if the transmitter is idle, otherwise sleep until the UART’s transmit interrupt (Tour 5: Life of a system call has the details). On QEMU the transmitter is nearly always ready, so in practice the 32 bytes go out in a quick burst. (A kernel instrumented to record every lock saw uartwrite take tx_lock 1,426 times across boot, usertests and several pipelines, and never sleep holding it: the idle test on line 87 always succeeded, Locks and interrupt state.)

Look at the irq strip: noff is 0. uartwrite calls sleep_prepare on line 86 holding a sleep-lock and no spinlock, unlike the console and the pipe, which register while holding the lock that guards their condition. Here the condition is a device register, LSR, which no lock can guard; if the UART goes idle between the check and sleep, the interrupt’s wakeup(&tx_chan) clears p->chan and sleep returns at once (Locks and interrupt state).

tx_lock is a sleep lock (Tour 17: Sleep-locks). Its holder may sleep in the middle of a batch, so it cannot be a spinlock. And interrupts stay on while it is held: holding a sleep-lock does not disable them.

This lock is the reason a batch is never mixed with another batch: while cat holds it, no other uartwrite can send a byte. It is released on line 95, after 32 bytes, and taken again for the next batch.

Step 6 of 15

wc waits for the lock, asleep

Inside, a sleep-lock is a locked flag guarded by a small spinlock, lk->lk. acquiresleep takes tx_lock.lk (so interrupts are off on hart 1 for these few lines), finds locked == 1 because cat holds the sleep-lock, registers on the channel lk with sleep_prepare, releases the spinlock, and calls sleep (line 28).

wc is now asleep, holding nothing. Hart 1 is free and goes back to its scheduler, which finds nothing to run and waits in wfi.

The same register-then-release pattern as everywhere in this version of xv6 (sleep and wakeup) protects against a lost wakeup: if cat releases the lock on hart 0 between line 27 and line 28, its wakeup clears wc’s p->chan, and sleep returns immediately.

On the stacks: sleep → sched → swtch saves wc’s sp in its p->context and puts hart 1 on its scheduler stack (kernel/swtch.S:26). wc’s frames stay on its kernel stack, waiting:

wc's kernel stack
  top ─► usertrap
         syscall
         sys_write
         filewrite
         consolewrite   buf[32] holds the byte "4"
         uartwrite
         acquiresleep
         sleep
         sched          ◄─ saved in wc's p->context.sp

The byte wc wants to print is already copied into the kernel, in consolewrite’s buf on that stack. It waits there, with the rest of the frames, until wc runs again.

Step 7 of 15

Two queues, two channels

There are now two different kinds of waiting around the UART, on two different channels:

At most one process can ever be waiting on tx_chan: only the holder of tx_lock sends bytes. Everybody else waits one level up, on the lock.

If cat did have to wait for the transmitter (rare on QEMU, common on a real 38,400 baud line), the “transmitter empty” interrupt would arrive at any hart, here hart 2, and uartintr would call wakeup(&tx_chan). That wakeup walks the whole process table but can only ever wake cat. (It may also clear a leftover p->chan == &tx_chan from an earlier holder, because uartwrite does not unregister after its last byte; that is harmless, since every sleep follows a fresh sleep_prepare.) wc, asleep on &tx_lock, is untouched: waking it would be pointless, since cat still holds the lock.

Step 8 of 15

Release wakes every waiter, and the race is open

cat’s batch is out. releasesleep clears locked and calls wakeup(lk), which makes wc RUNNABLE. It does not hand the lock to wc. There is no queue: every waiter is woken, and whoever reaches acquiresleep first wins.

cat is already running. It returns to consolewrite, copies the next 32 bytes, and calls uartwrite again, all within microseconds. wc must first be picked up by a scheduler. So cat often wins again, and wc goes back to sleep.

In our run, wc’s whole line and then the shell’s $ appeared at exactly byte 512 of README, after cat’s first write ended and before its second began. The race above may explain why wc got nothing in during that first write. But no cat byte appears inside wc’s 19 writes or the prompt, so cat was probably not writing at all during that time: perhaps wc only reached its printf then, or cat was held up in its next read. This is an inference; we did not trace it. The break fell in the middle of the word “contributions” because a byte count, not a word or a line, decides where writes start and end.

Note also that releasesleep’s wakeup sends no signal to idle harts waiting in wfi: a woken wc runs only when some scheduler next scans the table.

Step 9 of 15

You type, and the echo ignores tx_lock

While README scrolls by, you start typing your next command. Each key is an interrupt, here on hart 2, and consoleintr echoes it through consputc and uartputc_sync (Tour 37: A keystroke's journey).

uartputc_sync never touches tx_lock. It cannot: it runs in an interrupt handler, with cons.lock held, where sleeping is forbidden, and a sleep-lock’s waiter sleeps. So it spins until LSR says the transmitter is ready and writes THR, whoever is in the middle of a batch.

In a second run we typed a new command while cat was printing, and the screen showed our keystrokes cat README & ; w in the middle of README’s text. Echoes interleave at single-byte granularity with everything except procdump’s listing (both need cons.lock).

Step 10 of 15

printk takes pr.lock for the whole call

One of your keys is control-P. consoleintr calls procdump, which prints with printk, the kernel’s own printf (Tour 37: A keystroke's journey).

printk takes pr.lock, a spinlock, for the whole call, and prints every character with consputc. So two printk calls on different harts never mix: the second waits, spinning, until the first has printed its last byte (until a panic sets panicking). Kernel messages are short and rare, so spinning is acceptable.

Count hart 2’s levels on the irq strip: cons.lock (from consoleintr), pr.lock, and, inside every consputc, the push_off in uartputc_sync: noff 3, tying the deepest nesting anywhere in xv6, reached in this way only when someone types control-P (Locks and interrupt state). intena is 0 at every level, because the first push_off happened inside the trap handler.

Why not use uartwrite and tx_lock like everyone else? Because printk must work where sleeping is impossible: inside interrupt handlers (like this one), with spinlocks held (here cons.lock), and early in boot before any process exists. Only a spinning path works in all three.

Step 11 of 15

consputc goes straight to the UART

consputc is the bottom of both the echo and printk: one byte, straight to uartputc_sync, no buffer, no tx_lock. Its only special case is BACKSPACE, which becomes \b, space, \b to erase a character on the screen.

There is a subtlety in “whole call”. procdump prints each process with two printk calls (kernel/proc.c:700 and kernel/proc.c:701): the fields, then "\n". pr.lock is released in between, so another hart’s printk could slip in before the newline. printk protects calls, not lines. (Here hart 2 also holds cons.lock throughout procdump, so echoes, at least, cannot get in.)

Step 12 of 15

The shell's prompt, and what wc's 19 writes really were

Back to the real run. wc won tx_lock once per byte and printed its line, then exited. The shell (pid 2) woke in kwait, looped, and called getcmd, which writes "$ " with one write of 2 bytes: one batch, so no other process’s write can come between the $ and the space (an echo or a printk still could).

On screen: contribution (end of cat’s first write), 48 336 2441 README and a newline (19 separate writes by wc), $ (one write by the shell), then s: Russ Cox (start of cat’s second write).

The three processes ran on different harts and none of them knew about the others. The only lock that ordered these writes was tx_lock, taken once per batch; when they happened was decided by scheduling.

Step 13 of 15

panic: one hart stops the world's printing

Now suppose something goes badly wrong: a kernel bug makes hart 1 take an unexpected trap while wc is in the kernel, copying a byte of its output in copyin. kerneltrap prints scause, sepc and stval, then calls panic (kernel/trap.c:153). (A hypothetical: in our run nothing panicked.)

panic sets panicking = 1 before printing. That one global flag changes every hart’s behavior:

• printk skips pr.lock. The lock might be held forever by the code that broke, and the panic message matters more than tidy output.
• uartputc_sync skips push_off/pop_off: pop_off can itself call panic (kernel/spinlock.c:110, kernel/spinlock.c:112), and the panic may have come from exactly that bookkeeping, so the panic path stays clear of it.

Then it prints panic: and the message, sets panicked = 1, and spins forever.

On the stack, the unexpected trap is not a switch. kernelvec pushed its 256-byte frame onto wc’s kernel stack, right on top of the frames of the copy (kernel/kernelvec.S:14), and kerneltrap and panic run above it. Nothing below them will ever run again on hart 1.

Step 14 of 15

After the panic, printing freezes the printer

Once panicked is set, any thread that reaches uartputc_sync spins forever at line 109, so the panic message stays the last kernel text on the screen. Say you press a key after the panic: hart 2 takes the interrupt, consoleintr takes cons.lock and tries to echo, and hart 2 freezes here, holding cons.lock, with interrupts off. From then on any hart that wants cons.lock spins forever too.

Notice what is not frozen: uartwrite never looks at panicked. In this version a process on another hart that is still being scheduled, like cat on hart 0, can keep sending batches through uartwrite after the panic message. (It can only keep going while the transmitter is always ready: hart 2 froze inside uartintr before calling plic_complete (kernel/trap.c:210), so the PLIC delivers no more UART interrupts, and a uartwrite that ever has to sleep on tx_chan never wakes. We read this from the code; we did not trigger a panic.) Whether it gets that far depends on which locks the panicking hart left held.

Step 15 of 15

Three granularities, three locks

Back to a healthy machine, and cat copying its next batch. Here is the whole rule for how output can mix in xv6:

Two paths reach the same 16550: a polite one that sleeps and takes turns (for processes), and a blunt one that spins and ignores the queue (for the kernel and interrupt handlers). Each exists because the other cannot work everywhere.

What did a crowded console cost? wc’s 19 bytes took 19 system calls, and each byte could cost zero, one or several rounds of sleeping for tx_lock, depending on how often it lost the race; cat’s 2441 bytes took 5 write calls and 77 batches. And not one byte was lost: every lock here decides order, never whether a byte gets out.