How the Shell Runs ls | grep foo

The idea: a pipe is a kernel buffer with two file descriptors

When you type ls | grep foo, the shell starts two programs and connects the output of the first to the input of the second. Neither program knows about the other. ls writes to its fd 1 (standard output) and grep reads its fd 0 (standard input), as they always do. The shell has arranged that both fds point at the two ends of one pipe: a buffer inside the kernel.

The page follows the shell (bash, pid 100) through every system call it makes, then lets the two children run on one CPU. You see each process's fd table, the pipe's two open files with their reference counts, the ring of 16 slots that holds the data, and the terminal.

pipe(): two fds, the lowest free numbers

pipe(fds) creates the pipe and returns two new file descriptors: fds[0] is the read end and fds[1] the write end. The kernel always hands out the lowest unused numbers. The shell already has 0, 1 and 2 open on the terminal, so the pipe gets fd 3 (read) and fd 4 (write). Data written to fd 4 waits in the kernel until someone reads it from fd 3, in the same order, as a plain stream of bytes.

fork, dup2, close, execve: the order matters

A pipe only makes sense between two processes, so the shell forks twice. fork() copies the fd table: the child's fd 3 and fd 4 point at the same open files as the parent's. Each open file (struct file) counts how many fds refer to it in f_count. After two forks, each end has three fds: bash's and both children's.

Each child then wires its own end and drops the rest:

Who	Calls	Effect
writer child	dup2(4, 1)	fd 1 now points at the write end instead of the terminal
writer child	close(3); close(4)	drops the read end and the spare copy of the write end
writer child	execve("/bin/ls", …)	a new program, the same fd table
reader child	dup2(3, 0), close(3); close(4), execve("/bin/grep", …)	fd 0 is the read end, nothing else touches the pipe
the shell	close(3); close(4), then wait4()	the shell keeps no pipe end and waits for both children

execve() keeps every fd that isn't marked close-on-exec (O_CLOEXEC). That is the whole trick: the fd table is set up by the shell's code in the child, and then the program is swapped underneath it. ls doesn't know its fd 1 is a pipe. Programs can still check with isatty(): that is why ls prints one name per line, and why stdio sends output to a pipe in 4 KiB blocks instead of line by line. (Demo: ls | grep foo, the normal pipeline.) The fork itself is on A Linux Process from fork; what it copies in memory is on copy-on-write fork.

The 64 KiB buffer: blocking both ways

Since Linux 2.6.11 a pipe holds 64 KiB: a ring of 16 pipe_buffer slots, each one 4 KiB page. head is the next slot to write and tail the next slot to read. Two wait queues let the ends wait for each other:

• a read() on an empty pipe sleeps on rd_wait until a writer adds data;
• a write() to a full pipe sleeps on wr_wait until a reader makes room;
• each side wakes the other: pipe_write wakes rd_wait, pipe_read wakes wr_wait.

So a fast writer can't run away from a slow reader: it can be at most 64 KiB ahead, and then it simply stops. This is back-pressure, the same idea as a bounded buffer with a mutex and condition variables, done by the kernel. read() returns whatever is there, up to the size asked for, so grep's read(0, buf, 32768) can take 8 slots at once (Demo: full buffer: cat blocks until grep drains it). A program can change the size with fcntl(fd, F_SETPIPE_SZ, n) up to /proc/sys/fs/pipe-max-size (1 MiB by default). Writes of at most PIPE_BUF = 4096 bytes are atomic: two writers' small writes never interleave.

EOF needs every write end closed

The reader can't know from the data that the writer is finished. It learns it from the kernel: when the write end's f_count drops to 0 (pipe->writers = 0), a read() on an empty pipe returns 0, end of file. A process closes its fds when it calls close() or exits.

"Every" means every fd in every process. In Demo: shell forgets close(4): grep never sees EOF, the shell skips its own close(3); close(4). ls finishes and exits, but the write end still has one fd: the shell's fd 4. grep reads all the data and then sleeps in read() forever, waiting for an EOF that can't come. Meanwhile the shell sleeps in wait4() waiting for grep. Neither will move: a deadlock that only Ctrl-C ends. The same bug appears when a child forgets to close the end it doesn't use, which is why the reader closes fd 4 before execve. Libraries open fds with O_CLOEXEC for the same reason: a stray copy of a write end in some other program keeps a pipe open.

SIGPIPE and EPIPE

The other direction: when the read end's f_count drops to 0, nobody can ever read what is written. A write() then makes the kernel send SIGPIPE to the writer, and the call fails with EPIPE. SIGPIPE's default action ends the process; a shell reports exit status 141 = 128 + 13 (see How Linux Delivers a Signal). A program that ignores SIGPIPE, like most servers, gets -1 with errno = EPIPE instead and must handle it.

This is how yes | head -1 ends even though yes never stops on its own (Demo: yes | head -1: yes gets SIGPIPE). yes fills the 64 KiB and sleeps. head reads 8 KiB, prints one y and exits. Its exit closes the last read end, which wakes yes, whose next write gets SIGPIPE. When both ends are gone, the kernel frees the pipe and the 56 KiB nobody read.

$?, PIPESTATUS and pipefail

The shell reaps both children with wait4() and sets $? to the status of the last command. After yes | head -1, $? is 0 even though yes was killed: bash keeps each status in ${PIPESTATUS[@]} (here 141 0), and with set -o pipefail the pipeline fails if any command does. Scripts that use pipefail often have to allow 141 for exactly this case.

What the page leaves out

The page has one CPU and a task keeps it until it blocks; a real kernel preempts and runs both programs at once on two CPUs, so the buffer is rarely full. The shell is simplified: real bash puts the pipeline in its own process group and makes it the terminal's foreground job (setpgid, tcsetpgrp), and the children may run before the parent's next fork. The page skips pipe2(O_CLOEXEC | O_NONBLOCK) and EAGAIN, poll/epoll on a pipe, named pipes (FIFOs, mkfifo), splice/tee/vmsplice, the merging of small writes into one page, packet mode (O_DIRECT), pipe accounting limits per user, and here-strings and process substitution, which also use pipes. Sizes are rounded to whole slots: ls's 38 bytes take one slot.

References

pipe(7): capacity, PIPE_BUF, EOF and SIGPIPE rules

dup(2): dup, dup2, dup3

Bash Reference Manual: Pipelines, PIPESTATUS and pipefail

Linux source: fs/pipe.c (pipe_read, pipe_write)