Step 1 of 25

sh (pid 2): the prompt, and a read that will wait

The shell has printed $ with write(2, "$ ", 2), a trip through the system-call path of Tour 5: Life of a system call: ecall, the trampoline page, usertrap, consolewrite, uartwrite, and back. Now it clears its 100-byte buf and calls gets, which calls read(0, &c, 1): one byte per system call.

Descriptor 0 is the console, opened by init at boot and inherited. One struct file is shared by init’s descriptors 0, 1, 2 and the shell’s 0, 1, 2: reference count 6. Keep counting it; by the end of the tour it will have been as high as 15.

Step 2 of 25

sh (pid 2): nothing typed yet, so sleep on &cons.r

fileread routed the read through devsw[CONSOLE] to consoleread, which took cons.lock (interrupts off) and found the input buffer empty: r == w.

So the shell registers on the channel &cons.r with sleep_prepare, while still holding cons.lock, then releases the lock and calls sleep. Registering before releasing is the rule that prevents lost wakeups everywhere in this version of xv6; you will see it at every sleep in this tour.

The shell is now SLEEPING. Hart 0’s scheduler finds nothing else to run and joins the others in wfi. All three harts are idle, and the whole machine waits for your fingers. Tour 37: A keystroke's journey follows this wait, and your keystrokes, in detail.

Keep an eye on the “running on” strip: this tour visits every kind of stack (The stacks of xv6). Here hart 0 is on the shell’s kernel stack, the page of its process slot (slot 1, at 0x3fffffb000 in this build), which uservec pointed sp at (kernel/trampoline.S:76). When the shell sleeps, its frames (usertrap … consoleread, sleep, sched) stay on that page and swtch moves hart 0 to its scheduler stack (kernel/swtch.S:26). From then on, all three harts’ sps point into their scheduler stacks, the three 4 KiB slices of stack0.

Step 3 of 25

No process: you press Enter, and hart 2 commits the line

You type l, s, space, |, space, w, c. Each key is its own UART interrupt, claimed through the PLIC by whichever hart gets there first (in our trace, a mix of all three). Each time, consoleintr echoes the character with uartputc_sync and appends it to cons.buf, but does not commit it: the shell sleeps on.

Then Enter. Your terminal sends \r; hart 2 claims the interrupt. \r becomes \n, it is echoed and stored, and line 182 commits the whole line: w = e = 8. Then wakeup(&cons.r) walks the process table, taking each p->lock, finds the shell, and makes it RUNNABLE.

This step belongs to no process. Hart 2 was idle; the interrupt arrived in its scheduler loop. The kernel did all of this, echoing and line editing, before any program saw a single byte.

Which stack does a keystroke run on? Whatever the claiming hart was using: kernelvec pushes its 256-byte frame onto the current stack (kernel/kernelvec.S:14), and xv6 has no separate interrupt stack. Here every hart is idle, so it is a scheduler stack. When we replayed this command under gdb, all eight keystrokes (on harts 2, 0, 2, 0, 1, 1, 2, 0) entered consoleintr on the claiming hart’s scheduler stack with sp 496 bytes below the top of its slice. Had a hart been running a process, the same handler would have run on that process’s kernel stack (Tour 37: A keystroke's journey).

Step 4 of 25

sh (pid 2): awake on hart 1, eight reads later

No hart is told that the shell is runnable; each scheduler notices on its next scan. Hart 1 woke from wfi and found it first. The shell resumes inside sleep, on a different hart from the one it fell asleep on. Nothing in its kernel stack cares.

consoleread retakes cons.lock, takes l, copies it to the user with copyout, and returns 1. gets loops. The line costs eight one-byte reads in all: the first is the one that slept in step 2 and now returns l; the other seven find committed bytes and return at once.

buf now holds "ls | wc\n". Hart 0 is idle; hart 2 is back in its scheduler.

Two stack switches brought the shell here. Hart 1’s scheduler swtched onto the shell’s kernel stack, at the sched frame saved in step 2 (kernel/swtch.S:26), so the frames hart 0 left behind were resumed by hart 1. Then the read returned and userret loaded the shell’s user sp from the trapframe (kernel/trampoline.S:118), leaving the kernel stack empty.

Step 5 of 25

sh (pid 2): fork a child to do the work, then wait

The line is not cd, so the shell calls fork1 and the child runs runcmd(parsecmd(cmd)). The parent goes straight to wait(0).

Notice who parses: the child. Parsing allocates a tree with malloc and writes \0s into buf. Done in the child, all of that vanishes when the child exits; the shell itself never parses, never allocates and never frees, so it can run forever without leaking. cd is the exception (line 166) because changing directory in a child would change only the child’s directory.

fork returns twice. We follow the kernel side first.

Step 6 of 25

sh (pid 2): kfork copies memory and shares open files

kfork (Tour 20: fork) has already built pid 3: a slot from allocproc, a trapframe page, a new page table with a full copy of the shell’s memory (uvmcopy), and a copy of the shell’s registers with a0 = 0 so the child sees fork() return 0.

Lines 285-288 are where the pipeline’s plumbing will later come from. The child gets the parent’s descriptor table copied, but the open files themselves are shared: filedup increments each struct file’s reference count. The console’s count goes from 6 to 9. The child also shares the shell’s current directory, the root inode, through idup.

Then pid 3 is made RUNNABLE and fork returns 3 to the shell. The shell calls wait, and kwait finds no exited child, registers on its own struct proc as a channel, and sleeps. Hart 1’s scheduler takes the next RUNNABLE process in table order: pid 3.

The stacks of pid 3 are made in two different ways. Its user stack is part of the memory uvmcopy copies: same virtual addresses (the page at 0x4000 in this build), a different physical page, with the shell’s frames in it, so the child returns from fork into the same main. Its kernel stack is not copied at all. pid 3 gets slot 2, whose stack page (0x3fffff9000) was mapped at boot, and allocproc set context.sp to its top and context.ra to forkret (kernel/proc.c:147): an empty stack, waiting for a first swtch.

Step 7 of 25

sh (pid 3): parsecmd builds a PIPE tree

pid 3 starts life returning from fork with 0 and calls parsecmd, a small recursive-descent parser (recursive-descent parser). parsepipe parses one command with parseexec (ls), sees |, and recurses for the right side (wc). The result:

pipecmd
├── left:  execcmd  argv = {"ls", 0}
└── right: execcmd  argv = {"wc", 0}

The argv strings are not copied. They point into buf itself, and nulterminate writes a \0 after each word, turning "ls | wc\n" into "ls\0| wc\0". This is pid 3’s private copy of buf; the shell’s is untouched.

The first malloc asks the kernel for memory with sbrk: 64 KiB, allocated eagerly, a few hundred bytes of which hold this tree.

On the stacks, pid 3’s first run went: hart 1’s scheduler swtched to it and landed on the empty top of its kernel stack (0x3fffffa000 when we checked under gdb), in forkret; forkret went straight to userret, whose ld sp switched to pid 3’s copy of the user stack, usable from the sret on. pid 3 never ran a line of usertrap before its first instruction in user mode.

Step 8 of 25

sh (pid 3): pipe() creates the channel

runcmd sees PIPE. pipe(p) enters the kernel, where pipealloc claims two struct files from the global table (under ftable.lock) and one 4096-byte page from kalloc (under kmem.lock) to hold a struct pipe: a spinlock, a 512-byte ring buffer, two counters (nread, nwrite) and two open flags (readopen, writeopen). sys_pipe installs the read end as descriptor 3 and the write end as descriptor 4, the lowest free slots, and copies {3, 4} into p.

Tour Tour 39: Pipes takes this apart byte by byte. Here, remember three facts: the pipe holds 512 bytes; a reader of an empty pipe sleeps until a write or until every write end is closed; and “every write end” is counted in struct file references, which fork is about to multiply.

Step 9 of 25

sh (pid 3): two forks, and descriptors rewired

pid 3 forks pid 4 (left side, ls) at line 105 and pid 5 (right side, wc) at line 112. Lines 106–110 and 113–117 then run in the children, not in pid 3. Each fork dups all five open files: the console’s count rises to 12, then 15 (in our trace both forks happened before either child ran, so nothing had been closed yet).

The children rearrange their descriptors with the “close, then dup into the lowest free slot” idiom:

After this, ls’s standard output is the pipe and wc’s standard input is the pipe. When the children exec, the descriptor table survives (Tour 22: exec), so ls and wc inherit the wiring without knowing it exists. This is the whole trick of Unix pipelines: the shell connects programs by arranging descriptors 0 and 1 before exec.

In our trace all three forks ran on hart 1. pid 4 and pid 5 are now RUNNABLE, but harts 0 and 2 are in wfi and will not notice until their next interrupt.

Step 10 of 25

sh (pid 3): close both ends, then wait

pid 3 closes p[0] and p[1] (user/sh.c:119). It must: if it kept the write end open, wc could never see end of file, and pid 3 would wait for wc forever while wc waited for pid 3. Tour 39: Pipes shows this classic bug in full.

Then wait(0). kwait takes wait_lock (a spinlock: interrupts off), scans the table for children of pid 3, finds pids 4 and 5 alive, and registers on the channel p (its own struct proc) with sleep_prepare, still holding wait_lock. Then it releases the lock and sleeps.

Three processes now sleep, each on a different channel: init and the shell on their own struct procs, pid 3 on its own. Hart 1 is free, and its scheduler picks the next RUNNABLE process in table order: pid 4.

Step 11 of 25

ls (pid 4): exec loads the program from disk

pid 4 calls exec("ls", argv) (user/sh.c:79). kexec (Tour 22: exec) looks up ls in the current directory (the root) and finds inode 10, locks it, and reads its ELF header with readi.

This is the first time anything touches the disk. ls’s header is in block 301 of the disk image, and it is not in the buffer cache. bread calls virtio_disk_rw, which queues the request for the virtio disk and sleeps until the disk’s completion interrupt (Tour 29: A disk read, end to end). Then the code segment, at file offset 0x1000 and 0xb89 bytes long, comes from blocks 305, 306 and 307.

In our trace, those four blocks were the only disk reads ls caused in the whole command. The directory, the inode blocks and everything else were already in the buffer cache. (ls is 40,256 bytes on disk, but exec loads only 2,953 bytes of it; most of the rest is debugging information, symbol tables and page-alignment padding, which exec never reads.)

When kexec returns, pid 4 is no longer a shell. Its name is ls, its memory is ls’s, and its descriptors are untouched: 0 console, 1 pipe, 2 console.

kexec runs entirely on pid 4’s kernel stack, and it is what gives ls a new user stack. It builds it in a brand-new page table (one page at 0x3000 in this build, with a guard page below it), copies the argument string "ls" and the argv array onto it, and sets trapframe->sp to point at them (kernel/exec.c:137). Only then does it free the old image, including the shell’s user stack that pid 4 had been running on (kernel/exec.c:138).

Step 12 of 25

wc (pid 5): reads an empty pipe, and sleeps

Now we follow wc, on hart 2. Its exec finished, and with no arguments it calls wc(0, ""), reading descriptor 0: read(0, buf, 512) (user/wc.c:16). fileread sees FD_PIPE and calls piperead.

Take the simplest case: wc gets here before ls has written a byte. (In other traced runs ls was usually 72–299 bytes ahead by the time wc first found the pipe empty; sooner or later wc always does.) The pipe is empty (nread == nwrite == 0) and the write end is open (ls holds it), so wc must wait: sleep_prepare(&pi->nread) while holding pi->lock, release, sleep.

wc has no idea it is reading from ls. Had you typed wc alone, the same read(0, …) would have gone to consoleread and waited for your keystrokes.

When wc sleeps, its frames (usertrap, syscall, sys_read, fileread, piperead, sleep, sched) stay on its kernel stack and hart 2 returns to its scheduler stack. Tour 39: Pipes draws that stack.

Step 13 of 25

ls (pid 4): open the current directory

Back to ls, in user mode on hart 1. With no arguments, main calls ls("."). A directory is a file, so ls opens it like any other file and asks fstat what it is: T_DIR.

open(".") returns descriptor 3, the lowest free slot (0, 1 and 2 are taken). Do not confuse it with pid 3’s old descriptor 3: ls closed that one before exec. Descriptor numbers are per process; the same number can mean different files in different processes.

The kernel side of this open is the next stop.

Step 14 of 25

ls (pid 4): namex resolves "." to inode 1

sys_open starts a log transaction with begin_op (a lookup may drop the last reference to an inode, which can write the disk) and calls namei. "." does not start with /, so namex begins at the process’s current directory, the root inode, inherited through every fork since init.

skipelem extracts the element ".". ilock locks the root inode, a sleep lock (no need to read it from disk: it is cached and valid). dirlookup reads the directory’s entries and finds "." in the very first one, pointing at inode 1, the root itself. "." is an ordinary directory entry that mkfs wrote; the kernel has no special case for it. Tour 34: Path lookup covers path lookup in depth.

Back in sys_open: a struct file of type FD_INODE with offset 0, readable only.

Step 15 of 25

ls (pid 4): reading a directory entry through the buffer cache

ls reads the directory 16 bytes at a time, one struct dirent per read(fd, &de, sizeof(de)) (user/ls.c:60). Each goes fileread → ilock → readi.

The root directory is 1024 bytes: 64 slots, all in one disk block. bmap maps offset 0 to block 47. bread returns that block locked; readi copies 16 bytes straight from the cached block into ls’s de with either_copyout, releases the block with brelse, and fileread advances the file offset by 16.

So ls makes 65 read calls on this directory: 64 slots, then a 65th that returns 0 at offset 1024. 40 of the slots are empty (inum == 0) and are skipped; 24 are real entries, from . to console.

Step 16 of 25

ls (pid 4): a cache hit in bget

bget takes bcache.lock (a spinlock: interrupts off) and walks the list of 30 buffers (NBUF) looking for device 1, block 47. Block 47 was read at boot (when init looked up /init) and used for every lookup since, including exec’s lookups of sh, ls and wc. It is there: refcnt++, release bcache.lock, then take the buffer’s own sleep-lock.

In our trace there was no disk read for block 47 or for the inode blocks during the whole command. Had the block been evicted, b->valid would be 0 and bread would read it from the disk, sleeping in virtio_disk_rw, as exec did for ls’s code (Tour 29: A disk read, end to end, Tour 30: The buffer cache).

Step 17 of 25

ls (pid 4): stat every entry, and print it a byte at a time

For each of the 24 entries, ls builds the path ./README, ./cat, … and calls stat, which is three system calls: open, fstat, close. Each open is another path lookup through block 47; each close runs fileclose → iput inside a log transaction. That is 72 system calls just to learn the types, inode numbers and sizes.

Then printf prints a line like

README         2 2 2441

and user printf makes one write(1, &c, 1) per character (Tour 38: Output to the console from three harts). The 24 lines total 608 bytes, so ls makes 608 write calls. Every one goes to descriptor 1, which is the pipe.

Step 18 of 25

ls (pid 4): pipewrite stores a byte and wakes wc

filewrite sees FD_PIPE and calls pipewrite. Under pi->lock: the read end is open, the pipe is not full, so copyin fetches the byte . from ls’s memory and stores it at data[0]; nwrite becomes 1.

Then wakeup(&pi->nread). wc is registered on that channel, asleep, so it becomes RUNNABLE. This happens at the end of every pipewrite call, whether or not anyone is waiting: 608 walks of the process table for 608 bytes.

Could ls fill the pipe? It writes 608 bytes into 512 slots, so if wc read nothing until byte 513, ls would sleep on &pi->nwrite until wc made room. In our runs wc kept up and ls never slept here.

Stack census. At this moment five processes exist, and every one of them owns two stacks; each hart owns one more. Values from our gdb run of this build:

                user stack                     kernel stack (slot page)
pid 1 init      page 0x3000: main, in wait     0x3fffffd000: usertrap … kwait, sleep, sched
pid 2 sh        page 0x4000: main, in wait     0x3fffffb000: usertrap … kwait, sleep, sched
pid 3 sh        page 0x4000: main, runcmd,     0x3fffff9000: usertrap … kwait, sleep, sched
                in wait
pid 4 ls        page 0x3000: main, ls (with    0x3fffff7000: usertrap … filewrite, pipewrite
                buf[512]), printf … putc                     ◄─ hart 1's sp
pid 5 wc        page 0x3000: main, wc          0x3fffff5000: usertrap … piperead, sleep, sched

hart 0  scheduler stack, stack0 slice 0 (top 0x80008890): start, main, scheduler, in wfi  ◄─ sp
hart 1  scheduler stack, stack0 slice 1 (top 0x80009890): start, main, scheduler;
        its sp is parked in cpus[1].context while ls runs
hart 2  scheduler stack, stack0 slice 2 (top 0x8000a890): start, main, scheduler, in wfi  ◄─ sp

Thirteen stacks, and only three sp registers: at any instant at most three of them are being used. Everything else is a stack waiting, either a user stack whose sp is saved in the trapframe, or a kernel stack whose sp is saved in p->context, or, for hart 1’s scheduler stack, in cpus[1].context. Notice that the user stacks share virtual addresses (three at 0x3000, two at 0x4000) yet are five different physical pages, one per page table, while the kernel stacks all live in the one kernel page table and so must have different addresses. The other 59 slots’ kernel stacks exist too, mapped at boot and empty.

Step 19 of 25

wc (pid 5): wakes on hart 2 and drains what is there

Hart 2’s scheduler picks wc up. It retakes pi->lock, sees bytes, and copies as many as are there (up to 512) into its buf with copyout, advancing nread. Then wakeup(&pi->nwrite) for any writer waiting for room, and it returns.

ls keeps writing while wc works, so each read gets whatever has piled up. In eight traced runs wc needed between 5 and 17 data reads, for example 244, 238, 2, 80, 22, 22, then 0; another run had a stretch of 1-byte reads, wc and ls alternating byte by byte. The split is timing; the total, 608, is not.

Step 20 of 25

wc (pid 5): counting, in user mode

Back in user mode, wc counts: every byte (c), every \n (l), and every transition from whitespace to non-whitespace (w). This is the only computation in the whole command that the user asked for, and it is a few tens of thousands of instructions. Everything else in this tour is the operating system moving data and coordinating processes.

Each line of ls’s output has four words (name, type, inode number, size), so 24 lines give 96 words. After its last data read, wc has seen all 608 bytes, but it does not know that. It calls read again. Had ls still been running, the pipe would be empty with the write end open, and wc would sleep once more; only the write end being closed can tell it the data is over.

Step 21 of 25

ls (pid 4): exit closes the write end

ls has printed everything and calls exit(0). kexit (Tour 21: exit, wait and zombies) first closes every descriptor. Descriptor 1 holds the pipe’s write end with reference count 1: ls is the last writer. fileclose drops it to 0 and calls pipeclose, which, under pi->lock, sets writeopen = 0 and calls wakeup(&pi->nread). If wc is asleep on the pipe, it becomes RUNNABLE.

Then the current directory is released (iput in a transaction), and under wait_lock ls hands any children to init (it has none), wakes its parent pid 3 (asleep in kwait), and here, holding both wait_lock and its own p->lock, records its exit status and becomes a zombie. Line 360 then lets go of wait_lock (noff 2 → 1), because sched refuses to switch with any spinlock but p->lock held (Locks and interrupt state). sched switches away for the last time. Its memory and slot remain until pid 3 collects them.

ls is standing on its own kernel stack through all of this, up to the last swtch (kernel/swtch.S:26), which moves hart 1 to its scheduler stack for good. Nothing frees that stack, and nothing needs to: it belongs to slot 3, not to ls. What ls leaves for its parent to free is the trapframe and the user page table, with its user stack in it.

Step 22 of 25

wc (pid 5): end of file, and the answer

Suppose ls has already exited when wc makes its final read: piperead took pi->lock, found nread == nwrite with writeopen == 0, skipped the sleep loop and returned 0 at once. (Had ls still been running, wc would have slept, and ls’s pipeclose would have woken it.) To wc that is end of file, exactly as from a disk file or a control-D at the console. The loop ends.

Line 33 prints "24 96 608 \n": 24 lines, 96 words, 608 bytes, and an empty name (hence the trailing space). That is 11 bytes, and with user printf it is 11 write system calls on descriptor 1, which for wc is the console.

If ls exits before wc has taken everything, the leftover bytes still come out first, from a pipe whose writer is already gone. Data written to a pipe survives the writer.

Step 23 of 25

wc (pid 5): eleven bytes to the screen

Each of the 11 writes takes Tour 5: Life of a system call's road: filewrite sees FD_DEVICE, consolewrite copies the byte in, and uartwrite takes tx_lock, a sleep lock, checks that the UART’s transmitter is idle, and writes the byte to the THR register. QEMU passes it to your terminal.

tx_lock is what keeps output from different processes from mixing finer than one batch. Here nobody competes: no other process is writing to the console. But had cat been printing on another hart, its 32-byte batches and wc’s single bytes would have interleaved; Tour 38: Output to the console from three harts shows exactly that, from a real run.