Step 1 of 19

The shell prints its prompt and asks for a line

getcmd writes the prompt to file descriptor 2 (standard error, which is the console, like 0 and 1). That write is the journey of Tour 5: Life of a system call. Then it clears the 100-byte buf and calls gets to fill it with one line.

The shell has no idea a keyboard exists. Its descriptor 0 is the console device that user/init.c opened at boot, and every process inherited it. For the shell, a line of typing is whatever read(0, …) returns.

If gets comes back with an empty buffer, getcmd returns -1 and the shell exits. You will see how the kernel produces that “empty” answer when we reach control-D.

Step 2 of 19

gets reads one byte at a time

gets calls read(0, &c, 1): one byte per system call. For "ls\n" that is three read calls, each a full trip into the kernel and back.

Why not ask for 100 bytes at once? Because gets must stop exactly at the newline, and it cannot know where that is in advance. For the console this costs little, because the kernel hands back at most one line per read anyway (you will see why). For a file or a pipe it would matter: reading one byte at a time is the simplest way to never consume bytes that belong to the next line.

The read stub puts SYS_read (5) in a7 and executes ecall (user/usys.S:24). From here to sys_read the path is the one in Tour 5: Life of a system call. If read returns less than 1 (0 at end of file, -1 on error), gets stops.

Step 3 of 19

The file layer hands the read to the console driver

sys_read fetched its arguments and found ofile[0], the shell’s console open file (struct file). fileread sees FD_DEVICE with major number 1 (CONSOLE) and calls devsw[1].read, a function pointer that consoleinit set to consoleread at boot (kernel/console.c:201).

The first argument, 1, says “the destination is a user address”. The same driver function can be called with 0 and a kernel address; here it is the address of the shell’s local variable c in gets.

No lock is held, and interrupts are on, as they are for most of every system call.

Hart 0’s sp now points into the shell’s kernel stack (The stacks of xv6), the page that belongs to its process slot (slot 1, at 0x3fffffb000 in this build; its top is 0x3fffffc000). It was empty when the shell executed ecall; uservec loaded its top (kernel/trampoline.S:76), and it now holds usertrap, syscall, sys_read and fileread. The shell’s user stack, with gets’s c on it, waits unchanged.

Step 4 of 19

The console's input buffer and its three indices

consoleread's first act is acquire(&cons.lock) (kernel/console.c:95), so look at what that lock protects. cons is one global structure: a 128-byte circular buffer and three ever-increasing indices.

Always r ≤ w ≤ e. Bytes between r and w belong to readers; bytes between w and e are a line still being edited, which backspace may take back. The indices are uints that only grow; % INPUT_BUF_SIZE turns them into array positions, the same trick the pipe uses (Tour 39: Pipes).

Right now r = w = e = 0: nothing typed. And cons.lock is a spinlock, so hart 0 now has interrupts off. The irq strip shows how: acquire’s push_off found SIE on (the system call turned it on in usertrap), so it recorded intena = 1 and set noff to 1; the release will turn interrupts back on (Locks and interrupt state). Remember that 1: in step 9 an interrupt handler takes the same lock and records a 0.

Step 5 of 19

Nothing to read. Register, then let go

cons.r == cons.w: no committed line. The shell must wait, and it does so with the two-step sleep of this version of xv6 (sleep and wakeup):

1. If the shell has been killed, give up with -1 instead of waiting for a key that might never come. kkill both sets killed and makes a sleeping victim RUNNABLE, so a killed shell gets here again promptly.
2. sleep_prepare(&cons.r) records “I am waiting on channel &cons.r” in p->chan, while cons.lock is still held.
3. Only then release cons.lock (line 105) and call sleep (line 106).

The channel is the address of cons.r. Any unique address would do; this one says what is being waited for: r to become different from w.

killed (line 100) and sleep_prepare each take the shell’s p->lock for a moment inside the cons.lock critical section. That nesting, cons.lock then p->lock, is the same order consoleintr uses when it calls wakeup, so the two can never deadlock (Tour 18: Lock ordering: how xv6 avoids deadlock).

Step 6 of 19

The shell goes to sleep and hart 0 goes idle

sleep takes the shell’s p->lock. p->chan is still &cons.r (no key yet), so it marks the shell SLEEPING and calls sched, which switches to hart 0’s scheduler thread. sched insists that p->lock is the only lock held (noff == 1, kernel/proc.c:487). That is why cons.lock had to be released first: a hart that slept holding cons.lock would leave every keystroke handler spinning forever.

The shell is now frozen inside consoleread, its kernel stack preserved. It occupies no hart. Hart 0’s scheduler releases the shell’s p->lock, finds nothing RUNNABLE, and executes wfi, like the others.

All three harts are idle. The machine is waiting for you.

Here is what “frozen” means. swtch stores the shell’s sp and ra in its p->context and loads hart 0’s scheduler sp (kernel/swtch.S:26). The shell’s frames stay exactly where they were:

sh's kernel stack (slot 1)            hart 0's scheduler stack (stack0, slice 0)
  top ─► usertrap                       top ─► start, main (from boot)
         syscall                               scheduler   ◄─ sp, after swtch
         sys_read
         fileread
         consoleread
         sleep
         sched    ◄─ saved in sh's p->context.sp

Nothing runs on the shell’s kernel stack until some scheduler swtches back to it.

Step 7 of 19

You press l. Hart 2 takes the interrupt

Your terminal sends the byte 0x6c (l). QEMU’s emulated UART puts it in its receive FIFO, sets bit 0 of LSR (“data ready”), and, because uartinit enabled receive interrupts, raises its interrupt line, IRQ 10 (UART0_IRQ). The PLIC has that IRQ enabled for every hart (plicinithart), so it signals a supervisor external interrupt to all three.

All three are in wfi with interrupts off. wfi still wakes up, because the RISC-V spec says it resumes when a locally enabled interrupt is pending, whatever the global SIE bit says. Each woken hart goes round its loop to intr_on() (kernel/proc.c:441). The first to get there takes the trap; a hart that arrives after that hart’s claim has lowered the signal takes no trap at all and just rescans (often only one hart traps, Tour 9: Device interrupts and the PLIC). Here hart 2 gets there first: kernelvec, kerneltrap (Tour 8: Traps taken inside the kernel), and devintr.

scause is 0x8000000000000009, supervisor external interrupt. plic_claim asks the PLIC which device: 10, the UART. So uartintr runs, on a hart that has no process at all. Interrupt handlers serve the machine, not whoever happens to be running.

Which stack does the handler run on? xv6 has no separate interrupt stack (The stacks of xv6): kernelvec pushes a 256-byte frame of saved registers onto whatever stack sp points into (kernel/kernelvec.S:14). So a keystroke lands on whichever stack the claiming hart happened to be using:

Here all three harts are idle, so it is the first case:

hart 2's scheduler stack (its 4 KiB slice of stack0, top 0x8000a890)
  top ─► start, main      (from boot)
         scheduler        interrupted in its intr_on()/intr_off() window
         kernelvec frame  256 bytes: the interrupted code's registers
         kerneltrap
         devintr          ◄─ sp

In a gdb run of this build that typed ls | wc at an idle machine, all eight keystrokes were handled this way, on harts 0, 1 and 2, and sp on entry to consoleintr was always 496 bytes below the top of that hart’s slice (0x8000a6a0 on hart 2), 528 once consoleintr had pushed its own 32-byte frame.

Step 8 of 19

uartintr pulls the byte out of the chip

The UART has one interrupt line for both directions, so uartintr does both jobs every time:

• Reading ISR is the “acknowledge” the comment means, but on a 16550 that read only clears a transmitter-empty request; a received-data request goes away only when the receive FIFO is emptied, below.
• If the transmitter is idle, wakeup(&tx_chan) wakes any writer waiting in uartwrite (Tour 38: Output to the console from three harts). Nobody is writing now, so this visits all 64 process slots and finds no one asleep on it. It is harmless, and the simplest correct thing: the handler cannot cheaply tell why it was called.
• Then a loop: uartgetc checks LSR bit 0 and, while a byte is waiting, reads RHR, which removes it from the chip’s FIFO. Each byte goes to consoleintr.

The loop drains the FIFO, so if you typed two keys faster than the interrupt was handled, one interrupt delivers both. Here it delivers one: 0x6c.

After uartintr returns, devintr calls plic_complete(10). Until then the PLIC will not signal IRQ 10 again, which is why a second keystroke can never start a second uartintr on another hart while this one runs.

One comes almost at once anyway: the echo in consoleintr wrote THR, and since uartinit enabled transmit interrupts, the UART raises a “transmitter empty” request when that byte has gone. The PLIC holds it until plic_complete(10) and then signals again. That second uartintr, on whichever hart claims it, finds no input: its ISR read clears the transmit request, it runs the wakeup(&tx_chan) scan, and returns. In a gdb run of this build, every keystroke caused exactly two uartintr calls.

Step 9 of 19

consoleintr echoes l and stores it

consoleintr takes cons.lock. l is not a control character, so it reaches the default case:

• c != 0 and e - r < 128: there is room. A full buffer drops the key silently.
• \r would become \n (Enter, in a moment).
• consputc echoes it: the l you see on screen comes from here, not from any program. That is line editing (cooked input): the kernel shows you what you are typing even though nobody has read it yet.
• cons.buf[0] = 'l', and e becomes 1.

w does not move. The l is typed but not committed, so no wakeup: the shell sleeps on. Apart from control-D and a full buffer (next step), a reader never sees half a line, which is what lets backspace work.

Compare the irq strip with step 4. Same lock, but this acquire ran inside a trap handler, where SIE was already off, so it recorded intena = 0, and the release on line 189 will leave interrupts off, as kerneltrap needs. And because SIE is always off while noff > 0, this interrupt could never have landed on hart 0 while the shell held cons.lock there: a handler never spins on a lock held by the code it interrupted (Locks and interrupt state, Locks and interrupt state).

Step 10 of 19

The echo spins on the UART, interrupts off

consputc sends the byte with uartputc_sync: spin until LSR says the transmitter can take a byte, then write THR.

Why spin rather than sleep like uartwrite? Because there is nothing to put to sleep. This code runs in an interrupt handler, on whatever stack the hart was using (here the scheduler’s; often an unrelated process’s kernel stack), with cons.lock held. sleep would need a process of its own and would have to drop every spinlock first. A byte takes about a quarter of a millisecond at 38,400 baud on real hardware, and much less on QEMU, so spinning is the cheap option.

push_off here nests: acquire(&cons.lock) already did one (noff 1), this makes 2, and pop_off brings it back to 1. Interrupts stay off throughout (Locks and interrupt state).

Note what the echo does not take: tx_lock, the sleep-lock that orders write output. So your echoed letters can land between the bytes of another process’s output. Tour 38: Output to the console from three harts shows that happening.

Step 11 of 19

s, and what backspace and control-U would do

You press s. This time hart 1 claims the interrupt, and the same path stores buf[1] = 's', e = 2, and echoes s. Which hart handles a key does not matter: they all share cons, and cons.lock serializes them.

Had you mistyped, this is where it would be fixed, before any program sees it:

• Backspace (^H, or the Delete key, 0x7f, which most terminals send): if e != w, step e back one and erase the character on screen with \b, space, \b. The test e != w stops it at the start of the uncommitted text: a line already handed to a reader cannot be taken back.
• Control-U (kill line): erase backwards until e reaches w or the character before e is a newline.

Neither touches r or w, so neither needs to wake anyone. Erasing is cheap because the line is still entirely the kernel’s.

Step 12 of 19

Enter commits the line and wakes the reader

You press Enter. The terminal sends \r (13), carriage return; our trace of a real run shows exactly 108, 115, 13 arriving. Hart 2 claims it.

Line 171 turns \r into \n, so programs see Unix newlines. The echo moves the cursor to the next line, buf[2] = '\n', e = 3. Then line 179: a newline completes the line, so w = e = 3. The three bytes l, s, \n are now committed, and wakeup(&cons.r) tells anyone waiting on that channel.

Two other conditions also commit: control-D (end of file, below) and a full buffer (e - r == 128). The full-buffer rule makes sure a reader can always drain the buffer, so a 200-character line cannot jam the console forever.

Step 13 of 19

wakeup finds the shell

wakeup visits all 64 slots of the process table. For each it takes p->lock (so hart 2 now holds two spinlocks, cons.lock then a p->lock) and compares p->chan with &cons.r.

The shell matches. Its chan is cleared and, since it is fully SLEEPING, it becomes RUNNABLE. A waiter can be in one of three states when the wakeup comes, and each is handled:

Then consoleintr releases cons.lock, uartintr finds no more bytes, and hart 2 returns from the trap into its scheduler loop.

Step 14 of 19

Some hart picks the shell up

The shell is RUNNABLE, but no hart is told. Schedulers are not notified; each one notices on its next scan of the table. Hart 2 will scan as soon as it returns from the trap. Hart 0 scans whenever its wfi ends, on its next timer tick (about every 0.1 s) or on an external-interrupt signal like the one that just went to all harts. And one such signal is due: Enter’s echo went out before the wakeup, so its “transmitter empty” interrupt re-signals all harts right after plic_complete, just after the shell became RUNNABLE. That is a likely reason an idle hart picks the shell up within microseconds rather than at the next tick.

In this telling hart 0 gets there first: it takes the shell’s p->lock, sees RUNNABLE, marks it RUNNING, and switches to it (Tour 12: One scheduler per hart). The shell resumes inside sleep on hart 0, and since sleep releases p->lock on the way out, it returns into consoleread with no locks. In our traced runs the shell resumed on hart 1 in one run and hart 2 in another: which hart wins is a race, and it does not matter.

On the stacks, the switch at line 453 is the mirror of step 6. swtch saves hart 0’s scheduler sp in cpus[0].context and loads the shell’s saved sp (kernel/swtch.S:26), which points into the shell’s kernel stack at sched’s frame, exactly where step 6 left it. Had hart 1 won the race instead, the same kernel stack would simply have been resumed from hart 1: the stack belongs to the shell’s process slot, not to a hart.

Step 15 of 19

consoleread takes one byte and returns

Back in consoleread, the shell retakes cons.lock (line 107) and checks again. It always re-checks, because a wakeup only means “something may have changed”. Now r = 0, w = 3, so it takes buf[0], l, and r becomes 1.

either_copyout with user_dst = 1 calls copyout, which walks the shell’s page table in software and stores the byte into c on the shell’s user stack (Tour 28: Crossing the user/kernel boundary in memory). This happens with cons.lock held and interrupts off. That is allowed because copyout never sleeps: at worst it allocates a page with kalloc, which only takes another spinlock.

n drops to 0, so the loop ends after one byte (had gets asked for more, it would have stopped at the \n instead, line 129). consoleread releases the lock and returns 1. Tour 5: Life of a system call's return path carries the 1 back to user mode.

Step 16 of 19

The rest of the line arrives without sleeping

gets stores l and loops. The second read finds r = 1 < w = 3 at once, takes s, returns 1. The third takes \n, returns 1, and gets stops at the newline. buf is now "ls\n" followed by a 0 byte.

So typing one command cost: six UART interrupts (three bringing your bytes, and three more raised when the transmitter finished sending each echo), each with a fruitless 64-slot wakeup(&tx_chan) scan, three echoes, three read system calls, and exactly one sleep and one wakeup of the shell.

For a longer command the arithmetic is the same: ls | wc plus Enter is 8 bytes, so 8 one-byte read calls: the first sleeps until Enter commits the line, and the other seven return at once.

On the way out, userret loaded the shell’s user sp from the trapframe (kernel/trampoline.S:118). From that instruction until sret the hart is still in supervisor mode, which cannot use user pages, so it has no usable stack; sret makes the user stack usable. After it, the shell’s kernel stack holds nothing at all, and each of the next two reads starts it again from the top.

Step 17 of 19

Control-D: end of file from a keyboard

A keyboard has no end, so the console needs a way to say “end of file”. In xv6 it is control-D (byte 4). consoleintr stores it like a character and commits the line at once (kernel/console.c:179), even with no newline.

When consoleread meets it:

• If nothing has been copied yet in this call (n == target), the ^D is consumed and read returns 0, the end-of-file answer.
• If some bytes were already copied, r-- puts the ^D back, so this read returns just those bytes and the next one returns 0.

Type hi then control-D to cat: its read(0, buf, 512) returns 2, the next returns 0, and cat ends. To the shell, which reads one byte at a time, control-D at the start of a line gives gets an empty buffer; getcmd returns -1, the shell exits, and init prints init: starting sh and starts a new one (user/init.c).

Step 18 of 19

Control-P: a process listing from inside the interrupt

Control-P (byte 16) never reaches cons.buf. consoleintr calls procdump straight from the interrupt handler, still holding cons.lock. That is why it works even when every process is stuck: it needs no process and no scheduler. From one of our runs:

1 sleep  init
2 sleep  sh

procdump reads p->state and p->name without p->lock, on purpose (its comment says so): a debugging tool for a wedged machine must not wait for a lock a stuck process may hold. The price is that a line can be slightly stale.

Each printk takes pr.lock (Tour 38: Output to the console from three harts), so during each call hart 2 holds cons.lock then pr.lock. Between the two calls of each line (line 700, then 701), it holds only cons.lock. Inside each character, uartputc_sync's own push_off adds a third level: noff 3, tying the deepest nesting in the kernel, and the only place cons.lock → pr.lock appears in the lock order (Locks and interrupt state, Locks and interrupt state).

This is the deepest call chain in the tour, and it sits on hart 2’s scheduler stack: kernelvec’s frame, then kerneltrap, devintr, uartintr, consoleintr, procdump, printk and its helpers. Measured under gdb in this build, the deepest point is 960 bytes below the top, nearly a quarter of the slice’s 4096 bytes. The margin matters: a stack0 slice has no guard page, so an overflow would silently run into hart 1’s slice below it.

Step 19 of 19

The line reaches the shell, and the next story begins

getcmd returns 0. The shell skips leading blanks, sees that the line is not cd, forks a child to parse and run it, and waits. What follows (fork, exec, and for ls | wc a pipe) is Tour 40: Capstone: the shell running ls | wc.

Look back at what made this work across three harts:

• One lock for the shared buffer. cons.lock covers buf, r, w and e, for the interrupt handler and the reader alike, on whichever harts they run.
• A handler that never sleeps. consoleintr echoes by spinning, with interrupts off, because it has no process to put to sleep.
• Commit on newline. Only whole lines become readable, so editing is private to the kernel and cheap.
• Register before releasing. sleep_prepare inside cons.lock, wakeup inside cons.lock: no lost wakeup, and the reader always re-checks.

The shell slept on hart 0 and woke on whichever hart scanned first; your keys were handled on harts 2, 1 and 2. None of that changed what the shell read.