Step 1 of 19

The shell asks for a pipe

pid 3 parsed ls | wc into a PIPE node and is running runcmd. Before it creates either program it calls pipe(p). On return, p[0] is a descriptor for the read end and p[1] for the write end. This is the first command since boot, so pid 3 has descriptors 0, 1 and 2 (the console) and nothing else: the pipe will get 3 and 4.

Everything after this line is plumbing: making ls’s descriptor 1 and wc’s descriptor 0 refer to the two ends. The programs themselves only ever use write(1, …) and read(0, …), exactly as they would with the console. That is the point of a pipe: it is a file that connects two programs, and neither program needs to know.

Step 2 of 19

sys_pipe builds both ends at once

sys_pipe reads one argument, the user address of the int[2] array, and asks pipealloc for two open files: rf (read end) and wf (write end). Then it installs them as descriptors and copies the two numbers out.

A pipe is one kernel object with two faces. Reading and writing are different permissions on different struct files, so a process can hold only one end, and the kernel can tell when all holders of one end are gone. That is how end of file will work.

From the ecall on, hart 0 runs on pid 3’s kernel stack (The stacks of xv6), empty until uservec loaded its top (kernel/trampoline.S:76). The array p that will receive the two numbers is not here: it is a local of runcmd, on pid 3’s user stack, which is why sys_pipe must copyout to it.

Step 3 of 19

Two struct files from the global table

pipealloc calls filealloc twice. Each call scans the global file table ftable (100 entries, NFILE) for one with ref == 0, sets ref = 1, and returns it.

ftable.lock is held for the scan and the claim, so hart 0 has interrupts off for these lines. The check ref == 0 and the store ref = 1 must be one atomic step.

Step 4 of 19

One page for the pipe itself

The pipe’s state lives in a whole 4096-byte page from kalloc. A struct pipe is exactly 552 bytes (a 24-byte spinlock, 512 bytes of data, four 4-byte integers; the offsets in kernel.asm’s pipeclose, such as sw zero,548(s1) for readopen = 0, confirm it), so 3,544 bytes of the page, about 3.5 KiB, are unused. xv6 has no allocator for small kernel objects, and that waste is the price of the simplicity.

Both ends start open, both counters at 0, and the two files are typed FD_PIPE, pointing at the same pi: rf readable only, wf writable only.

If anything fails, the bad: path gives back whatever was claimed: fileclose on the struct files (the kfree of the page is only a safeguard; nothing after kalloc can fail). Nothing leaks.

Step 5 of 19

A ring of 512 bytes and two counters that never wrap back

data is a circular buffer. nwrite counts every byte ever written and nread every byte ever read. They only increase; % PIPESIZE turns a count into a position:

With separate “read” and “write” indices that wrap at 512, full and empty would both look like “indices equal”. Free-running counters keep them apart, with no wasted slot and no extra flag.

They are 32-bit uints, so after 4 GiB through one pipe they overflow to 0. That is harmless: unsigned arithmetic is modulo 2³², and 512 divides 2³², so nwrite - nread and % 512 give the same answers across the overflow.

readopen and writeopen record whether any file for each end is still open.

Step 6 of 19

The descriptors, and the two numbers handed back

fdalloc picks the lowest free slot in pid 3’s ofile[] table: 3 for the read end, 4 for the write end. Then two copyouts store 3 and 4 into the user’s p[0] and p[1] (Tour 28: Crossing the user/kernel boundary in memory).

No lock protects ofile[]. Only pid 3 itself changes its own descriptor table, and an xv6 process has a single thread, so while pid 3 is in this system call nothing else can touch the table.

If the copyout fails (a bad p pointer), the descriptors are removed and both files closed, which also frees the pipe. A failed pipe leaves no trace.

Step 7 of 19

Fork twice, then rewire descriptors 0 and 1

pid 3 forks twice (Tour 20: fork). Each kfork calls filedup on every open descriptor, so the children start with the pipe’s two ends too.

• The left child, pid 4, will become ls: close(1) frees descriptor 1, so dup(p[1]) lands in the lowest free slot, 1. Then it closes both originals.
• The right child, pid 5, will become wc: close(0), dup(p[0]) lands in 0, and it closes both originals.
• pid 3 closes both ends and waits for both children.

When the dust settles, regardless of which hart ran which line first:

Each end’s struct file ends with ref == 1: the write end is held only by ls, the read end only by wc. Every close on these lines matters, and step 18 shows what one missing close does.

Step 8 of 19

wc reads first, and the pipe is empty

wc has exec’d (Tour 22: exec) and called read(0, buf, 512) (user/wc.c:16). fileread sees FD_PIPE and calls piperead. Sooner or later wc drains everything ls has written so far and finds the pipe empty. In our traced runs that first happened after ls had written 72–299 bytes, but take the simplest case: wc gets here before ls has written anything.

piperead takes pi->lock (interrupts off on hart 2) and finds nread == nwrite: empty. The write end is still open, so data may yet come; wc must wait:

1. Killed? Then return -1 rather than wait.
2. sleep_prepare(&pi->nread), still holding pi->lock.
3. Release pi->lock (line 125), then sleep (line 126).

The reader sleeps on &pi->nread, the writer will sleep on &pi->nwrite. Two channels, so a wakeup meant for readers never disturbs a writer and vice versa.

Follow noff on the irq strip: 1 under pi->lock (with intena 1, since SIE was on in the system call); 2 for a moment inside killed and sleep_prepare, which take wc’s p->lock; 0 after the release on line 125, which turns interrupts back on. Then sleep takes p->lock again, so sched sees exactly what it demands: noff 1, and that one lock is p->lock (Locks and interrupt state).

When wc sleeps, its whole call chain stays on its kernel stack, and swtch moves hart 2 to its scheduler stack (kernel/swtch.S:26):

wc's kernel stack                     hart 2
  top ─► usertrap                       sp ─► its scheduler stack (stack0, slice 2):
         syscall                              start, main, scheduler, then wfi
         sys_read
         fileread
         piperead    holds nothing now: pi->lock released at line 125
         sleep
         sched       ◄─ saved in wc's p->context.sp

A sleeping process costs one kernel stack page (its slot’s, allocated at boot) and no hart.

Step 9 of 19

ls writes one byte

ls prints its first line, . 1 1 1024, with printf, and user printf calls write(1, &c, 1) once per character (Tour 38: Output to the console from three harts). So ls will make 608 one-byte write calls into this pipe, one per byte of its output.

Descriptor 1 is the pipe’s write end. filewrite checks writable (the read end would fail here) and sees FD_PIPE, so it calls pipewrite with the user address and n = 1.

ls has no idea this is not the console. The same filewrite call reached consolewrite for echo in Tour 5: Life of a system call; the type field is all that differs.

Step 10 of 19

pipewrite stores the byte under pi->lock

pipewrite takes pi->lock and loops over the bytes (one, here):

• If the read end is closed (readopen == 0) or ls was killed, return -1: writing to a pipe nobody can read is an error, not a wait.
• If the pipe is full, sleep (step 13).
• Otherwise copyin one byte from ls’s memory and store it at data[nwrite % 512], then nwrite++.

The copy from user memory happens with a spinlock held, interrupts off. That is allowed because copyin never sleeps: it walks the page table in software, and at worst allocates a page with kalloc (Tour 28: Crossing the user/kernel boundary in memory). A bad address simply ends the write early.

Copying one byte per iteration costs a page-table walk per byte. It keeps the loop simple, and lets it stop exactly where the pipe fills.

Each byte makes a one-byte stop on ls’s kernel stack on the way: copyin copies it into pipewrite’s local ch (kernel/pipe.c:95), and only then into data. piperead does the mirror image on wc’s kernel stack, data → its own ch → user memory.

Step 11 of 19

Every write wakes the reader

After the loop, pipewrite calls wakeup(&pi->nread) (kernel/pipe.c:105), still holding pi->lock. wakeup walks all 64 process slots, taking each p->lock in turn, and finds wc asleep on &pi->nread: it clears wc’s chan and makes it RUNNABLE.

pipewrite does this at the end of every call, whether or not anyone is waiting. ls makes 608 calls, so that is 608 walks of the process table, about 39,000 p->lock acquisitions, to move 608 bytes. Simplicity over speed, again.

Then pi->lock is released and write returns 1 to ls, which goes on to its next character.

Step 12 of 19

wc wakes on hart 2 and takes what is there

Hart 2’s scheduler picks wc up. It returns from sleep, retakes pi->lock, re-checks (not empty now), and copies: up to n = 512 bytes, stopping as soon as nread == nwrite. Each byte goes out with copyout into wc’s buf, and nread++ follows only a successful copy.

A pipe read returns whatever is there, not necessarily 512 bytes. By the time wc ran, ls had written more. In our traced runs wc needed between 5 and 17 reads, for example 244, 238, 2, 80, 22, 22, then 0; another run included a stretch of 1-byte reads, wc and ls alternating byte by byte. The split depends on timing; the total is always 608.

Then wakeup(&pi->nwrite): space was freed, so a writer waiting for room may go on.

The wakeup itself moved nothing: it only set wc RUNNABLE. Hart 2’s scheduler then swtched onto wc’s kernel stack (kernel/swtch.S:26), at the sched frame saved in step 8, and the chain unwound from there: sched returned to sleep, sleep to piperead, which retakes pi->lock (line 127) and then re-checks its loop condition.

Step 13 of 19

When ls outruns wc, the pipe fills

In our runs wc kept up, but nothing guarantees it. Suppose hart 2 were busy and wc had not read yet: ls’s output is 608 bytes and the pipe holds 512, so on byte 513 nwrite == nread + 512. The pipe is full.

pipewrite then:

1. wakeup(&pi->nread): make sure the reader knows there is data.
2. sleep_prepare(&pi->nwrite), holding pi->lock.
3. Release pi->lock, sleep, and retake the lock when woken.

It is the mirror image of the reader. The writer sleeps on &pi->nwrite, and piperead's wakeup(&pi->nwrite) releases it once there is room. The loop then re-checks readopen and killed, so a writer whose reader died is not stuck forever.

This is flow control: a fast producer is slowed to the speed of its consumer, and memory use stays at one page per pipe no matter how much data flows.

The writer’s sleep looks just like the reader’s in step 8, one level over: ls’s frames wait on ls’s kernel stack while hart 1 goes to its scheduler stack.

ls's kernel stack (asleep on &pi->nwrite)
  top ─► usertrap
         syscall
         sys_write
         filewrite
         pipewrite   i = 0: byte 513 not yet stored
         sleep
         sched       ◄─ saved in ls's p->context.sp

Where pipewrite was in its loop (i and the user address, kept in callee-saved registers) survives the sleep: sleep and sched save those registers in their frames, and swtch saves the rest in p->context, which is how it continues with the right byte when it wakes.

Step 14 of 19

ls exits and closes its descriptors

ls has printed all 24 lines and calls exit(0). kexit first closes every open descriptor. ls never called close(1) itself, and did not need to: exit closes everything, and that is how most pipes get closed in practice.

Descriptor 0 is the console (its reference count drops by one). Descriptor 1 is the pipe’s write end, with ref == 1: ls was its last holder. fileclose is about to discover that.

Step 15 of 19

fileclose drops the last reference

fileclose takes ftable.lock and decrements ref. If others still hold the file, that is all. Here ref becomes 0, so it copies the structure into the local ff, marks the slot free (ref = 0, FD_NONE), and releases ftable.lock. Only then does it call pipeclose with ff.writable = 1.

Why copy and release first? The slot may be reused by another hart’s filealloc the moment the lock is released, so the fields must be saved. And the cleanup must run outside ftable.lock: for inode files it calls begin_op and iput, which can sleep, and no one may sleep holding a spinlock. Pipes use the same path.

Step 16 of 19

pipeclose marks the write end closed and wakes the reader

pipeclose takes pi->lock, sets writeopen = 0, and calls wakeup(&pi->nread): a reader asleep on an empty pipe must re-check, because “empty” now means “finished”, not “wait”.

readopen is still 1 (wc holds the read end), so the pipe survives, with any unread bytes still in data. pi->lock is released and ls continues its exit: it closes descriptor 2, wakes its parent pid 3, and becomes a zombie (Tour 21: exit, wait and zombies).

Note that writeopen is a single flag, not a count. It goes to 0 only when the write end’s single struct file is finally closed, because fileclose only calls pipeclose when that file’s ref reaches 0. Counting the descriptors happens one level up, in ftable.

Step 17 of 19

wc sees end of file

wc reads again. If bytes remain, it gets them first: the loop condition on line 119 only waits while the pipe is empty and the write end is open. If ls exits before wc has taken everything, the leftover bytes still come out first.

On the next read, nread == nwrite and writeopen == 0: the while is skipped, the copy loop breaks at once with i = 0, and piperead returns 0. To wc, that is end of file, the same answer a disk file gives at its end, and its loop while ((n = read(fd, buf, sizeof(buf))) > 0) ends (user/wc.c:16).

wc prints 24 96 608 (with a trailing space: its name argument is "") and exits. Its exit closes the read end, the last reference to the pipe.

Step 18 of 19

The classic bug: one forgotten close

Delete line 116, close(p[1]), in the right child. What happens?

wc (pid 5) now holds the pipe’s write end itself, at descriptor 4, through exec. When ls exits, the write end’s ref drops from 2 to 1, not to 0. pipeclose is never called, writeopen stays 1, and when wc has read all 608 bytes, piperead sees “empty, but the write end is open” and sleeps, waiting for a writer that is itself. Nothing will ever wake it. pid 3 waits forever for wc, and the shell (pid 2) waits forever for pid 3. Your terminal shows no prompt.

The same hang follows if pid 3 forgets line 120, close(p[1]): then pid 3 holds a write end while it waits for wc, and wc waits for pid 3 to close it. A deadlock spread across two processes, with no lock involved.

Forgetting to close a read end does no harm in ls | wc, because wc reads to the end. It bites only when the reader quits early: if ls kept its copy (line 108) and wc exited early, ls’s writes would not fail with -1 (readopen would still be 1), and ls could sleep forever on a full pipe that only it can read.

Step 19 of 19

The last close frees the page

wc exits. fileclose drops the read end’s ref to 0 and calls pipeclose with writable = 0: readopen = 0, wakeup(&pi->nwrite) (no writer left to hear it). Now both flags are 0, so after releasing pi->lock it frees the page with kfree. The lock lived inside the page, so it must be released before the page is freed; no other hart can be waiting for it, because no struct file points to this pipe any more.

What did ls | wc cost in pipe machinery? One page, two struct files, 608 write calls each taking pi->lock and walking the process table to wake the reader, a few to a couple of dozen read calls (6 to 18 in our runs), and at least one sleep. The ideas that carried it:

• Counters, not indices: nwrite - nread says everything, even across overflow.
• One lock, two channels: pi->lock for every check-and-act, &pi->nread and &pi->nwrite so readers and writers wake only each other.
• Register before releasing: sleep_prepare inside pi->lock, so no lost wakeups between harts.
• End of file is a reference count reaching zero, which is why every close matters.

kexit runs to the end on wc’s own kernel stack and leaves it for good in its final sched. It does not free that stack, and could not: it is standing on it. It never needs to, because kernel stacks belong to process slots, allocated once at boot. What freeproc frees later, in pid 3’s kwait, is the trapframe and the user page table, and with it wc’s user stack.