kernel/pipe.c

Headers

kernel/file.h defines struct file, whose pipe field points at the structure below. It needs struct sleeplock (for the inode it also declares), hence kernel/sleeplock.h and kernel/fs.h before it.

The pipe structure

data is a circular buffer of PIPESIZE (512) bytes. Instead of a “head” and a “tail” index, the pipe keeps two ever-increasing counters: nwrite, the total number of bytes ever written, and nread, the total ever read. Then:

• the number of bytes waiting in the buffer is nwrite - nread, always between 0 and 512;
• the buffer is empty when nread == nwrite, and full when nwrite == nread + PIPESIZE;
• byte number k of the stream lives at data[k % PIPESIZE].

With head and tail indices that wrap at 512, “empty” and “full” would both look like “head equals tail”; the counters make the two cases different.

The counters are uint and do wrap around after 2^32 bytes. That is harmless: unsigned arithmetic in C is done modulo 2^32, so nwrite - nread and the full test stay correct across the wrap, and since 512 divides 2^32 evenly, k % PIPESIZE picks the same slot before and after.

readopen and writeopen record whether each end still has an open file. They decide when a reader sees end-of-file, when a writer gets an error, and when the pipe can be freed. lock protects every field.

pipealloc(): make a pipe and its two ends

Called by sys_pipe. It produces two open files, *f0 for reading and *f1 for writing, sharing one new pipe.

*f0 and *f1 are set to 0 first so that the failure path can tell which allocations happened. filealloc takes entries from the system-wide file table; it can fail if all NFILE (100) are in use.

Allocate and initialize the pipe

The pipe structure gets a whole page from kalloc. It needs only a little over 512 bytes, so most of the 4096 are wasted, but kalloc is the only memory allocator the kernel has: it hands out whole pages and nothing smaller.

Both ends start open and the buffer empty. Then the two open files are filled in: the first readable only, the second writable only, both pointing at the pipe. Because fileread and filewrite check readable and writable, reading from the write end (or writing to the read end) fails with -1 before any pipe code runs.

Each open file starts with a reference count of 1 (set by filealloc), owned by the caller.

Failure path

Undo whatever was allocated. At this point the open files still have type FD_NONE (they were never filled in), so fileclose only returns them to the file table and does not try to close a pipe.

pipeclose(): one end is closed

Called by fileclose when the last reference to one end’s open file goes away (writable says which end). The pipe records that the end is closed and wakes anyone waiting on the other side, because their situation has changed:

• Write end closed. A reader sleeping on an empty pipe must wake up and see end-of-file (read returns 0) instead of sleeping forever. Readers sleep on the channel &pi->nread.
• Read end closed. A writer sleeping on a full pipe must wake up and fail, since nobody will ever drain the buffer. Writers sleep on &pi->nwrite.

When both ends are closed nobody can reach the pipe any more, and its page is freed. The lock must be released before kfree: the lock lives inside the page, and kfree fills the page with junk bytes, so releasing afterwards would write into freed memory.

pipewrite(): copy n bytes from user memory into the pipe

Called by filewrite for a pipe’s write end. addr is a user virtual address. The loop runs until all n bytes are in the pipe, sleeping whenever the buffer is full; so a large write may be delivered in several pieces, with reads interleaved.

The pipe’s lock is held throughout, except while sleeping. Each time around, the writer first checks whether it should give up:

• the read end is closed: no one will ever read, so the write fails with -1;
• the process has been killed (killed): return -1 so that it can exit instead of waiting.

Either way the return value is -1 even if some bytes were already written.

Buffer full, so wake the reader and sleep

When the buffer holds 512 unread bytes, the writer cannot continue. It first wakes any reader (&pi->nread), since there is plenty to read, then sleeps on its own channel, &pi->nwrite, until a reader makes room.

The order of the three calls is what prevents a lost wakeup. sleep_prepare records “this process waits on &pi->nwrite” while the pipe lock is still held. Only then is the lock released. If a reader now drains the buffer and calls wakeup(&pi->nwrite) before this process has actually gone to sleep, wakeup still finds the registration and clears it, and sleep then returns at once instead of sleeping. Had the lock been released before registering, that wakeup could arrive in the gap and be missed. The writer would then sleep on a buffer that is in fact empty, and the reader, finding nothing more to read, would go to sleep too: both asleep forever.

After waking the writer re-takes the lock and goes round the loop again, rechecking everything: a wakeup only means “something changed”, not “there is room”.

Copy one byte

With room in the buffer, one byte is copied from user memory with copyin and stored at slot nwrite % PIPESIZE; then nwrite advances. Copying a byte at a time is slow but simple: it never has to split a copy at the buffer’s wrap-around point or at a full buffer.

copyin fails if addr + i is not valid memory of this process. Then the write stops: if nothing was written yet, it reports -1; otherwise it reports the bytes that did go in.

copyin is called while the pipe’s spinlock is held. That is allowed only because copyin never sleeps: at worst it allocates and maps a page for a lazily grown heap (vmfault), which does not sleep.

Wake readers and return

Any bytes written may be what a sleeping reader is waiting for, so readers are woken on the way out. The return value is the number of bytes written, normally n.

piperead(): wait until there is something to read

Called by fileread for a pipe’s read end. The loop sleeps while the pipe is empty and the write end is still open. It stops in two cases:

• there is data: go and copy it;
• the buffer is empty and the write end is closed: no data will ever come. The copy loop below then copies nothing and read returns 0, which programs understand as end-of-file.

A killed process returns -1 instead of waiting. Sleeping uses the same sleep_prepare / release / sleep sequence as pipewrite, on the readers’ channel &pi->nread, so a wakeup arriving between the release and the sleep is not lost.

Unlike the writer, the reader does not wait for all n bytes: as soon as any data is present it returns what is there. That is the Unix rule for pipes, and the reason programs must call read in a loop.

Copy out what is available, then wake writers

Up to n bytes are moved, one at a time, from slot nread % PIPESIZE to the user’s buffer with copyout, stopping early when the buffer runs empty. nread is advanced only after the byte was successfully copied, so a failed copy does not lose data from the pipe.

Taking data out makes room, so writers sleeping on a full pipe are woken (&pi->nwrite). The result is the number of bytes read, or -1 if the very first copy failed.

The //DOC: comments in this file are labels, not explanations: the xv6 book locates these lines by searching for the label text and cites their line numbers. They have no effect on the code.