How are Unix pipes implemented?

If I remember correctly, this work was an end of semester advanced OS/Networking class presentation. I picked Pipes, others picked the filesystem, device drivers, CUDA, process scheduling etc. For the master’s thesis, my work was on active indoor localization and tracking (early work before indoor Google maps was launched).

Re: your second question, I guess you’re referring to identifying a FIFO on the filesystem - that’s a simple ls -la - FIFOs show up as regular files with the p attribute. For procfs or sysfs - just ls /proc or ls /sys

Man page: http://nersp.nerdc.ufl.edu/~dicke3/nerspcs/ls.html

You should see the p attribute for FIFOs on the filesystem. Sysfs and procfs map onto internal (in-memory) kernel data structures, so those might just show up as regular files in the “virtual” filesystem. So cat, grep etc. on these files will be just reads/writes from/to the appropriate memory space in the kernel or for read only files, they may be “code generated output” that allows for inspection of some internal state in the kernel.

> Can you elaborate on how to identify the filename for a pipe in procfs or sysfs in a simple "echo hello | wc -c" example?

You can see it under /proc/$pid/fd. For example, if you run "sleep 600|wc -c" (just to give yourself some time to poke around), you can see:

    $ ls -l /proc/2760791/fd 
    total 0
    lrwx------ 1 ams ams 64 Mar 28 13:35 0 -> /dev/pts/10
    l-wx------ 1 ams ams 64 Mar 28 13:35 1 -> pipe:[54074122]
    lrwx------ 1 ams ams 64 Mar 28 13:35 2 -> /dev/pts/10
    
    $ ls -l /proc/2760792/fd
    total 0
    lr-x------ 1 ams ams 64 Mar 28 13:35 0 -> pipe:[54074122]
    lrwx------ 1 ams ams 64 Mar 28 13:35 1 -> /dev/pts/10
    lrwx------ 1 ams ams 64 Mar 28 13:35 2 -> /dev/pts/10

Here 2760791 is the pid of the "sleep 600", and 2760792 is the pid of "wc". You can see they're both connected to "pipe:[54074122]".

54074122 is the (virtual, i.e., not disk-based) inode of the pipe. You can get substantially the same information from lsof:

    $ lsof -E -u ams|egrep 'sleep|wc'|grep pipe
    sleep     2760791  ams    1w     FIFO               0,13        0t0   54074122 pipe 2760792,wc,0r
    wc        2760792  ams    0r     FIFO               0,13        0t0   54074122 pipe 2760791,sleep,1w

But the name "pipe:[54074122]" is actually the "filename" of the pipe, and it comes from here in fs/pipe.c:

    static char *pipefs_dname(struct dentry *dentry, char *buffer, int buflen)
    {
            return dynamic_dname(dentry, buffer, buflen, "pipe:[%lu]",
                                    d_inode(dentry)->i_ino);
    }

(There's an interesting note in Documentation/filesystems/vfs.txt about how pseudo-filesystems like pipefs can generate these names only when someone asks for them, since they're not used for anything otherwise. The only way I know of to ask for the name in this case is to call readlink() on the pipe fd under /proc/$pid/fd, as ls does.)

The slides are from 2011, not the code. Linux had pipes even in the v0.01 release from 1991, as the original article here mentions.

Pipes are bytes Streams. Communication between actors as well as CSP channels are object streams.

Pipes exercise backpressure on the writer - if the pipe is full the writer is blocked. Actor systems mostly use seemingly unbounded queues. The sender will not get blocked.

Here's a short 2014 paper from McIlroy himself discussing his early thinking back then: https://www.cs.dartmouth.edu/~doug/sieve/sieve.pdf

TL;DR: McIlroy was applying the concept of coroutines, which was described by Melvin Conway in 1963. Two processes communicating over a pipe are basically coroutines, except instead of passing structured data they're just passing bytes.

A Unix pipeline is a set of multiple coroutines. In fact, Tony Hoare's 1978 Communicating Sequential Processes paper cites the UNIX shell[1] for the concept of coroutines, and discussion of coroutines figures prominently in that paper. See https://www.cs.cmu.edu/~crary/819-f09/Hoare78.pdf CSP basically models the behavior of a large set of coroutines.

AFAIU, Erlang was partly inspired by CSP. You can draw a straight line from coroutines, through Unix pipelines and CSP, to Erlang's processes.

[1] Specifically, Ken Thompson's 1976 paper, "The UNIX command language." See https://archive.org/details/theunixcommandlanguage

Thank you very much for digging this up, and to all the other commenters here for the useful references.

Now I'm confused and curious as to what the ‘library filing scheme’ means. Does it mean shared libraries? IIRC Unix stuff was statically-linked at first. And then again, what are ‘indexing’ and ‘data path switching’?

http://usingcsp.com/cspbook.pdf is the classic.

It has some unusual notation you might need to get used to, but it's a real goldmine of ideas.

There's "the CSP book", by Tony Hoare himself: http://usingcsp.com/cspbook.pdf

Sorry, I was wrong about the BSDs. FreeBSD's pipe.2 manpage clearly says that pipes are still bidirectional. https://www.freebsd.org/cgi/man.cgi?query=pipe&sektion=2

That said, it is not based on socketpair any more. sys/kern/sys_pipe.c says:

    /*
     * This file contains a high-performance replacement for the socket-based
     * pipes scheme originally used in FreeBSD/4.4Lite.  It does not support
     * all features of sockets, but does do everything that pipes normally
     * do.
     */

my_df %>% plot(col1,col2,col3)

see 18.2.1 and 18.2.4 in https://r4ds.had.co.nz/pipes.html

much sugar