A tour of a living system

The last chapter left a question: a hundred programs run on one processor, so who decides which of them gets to run, and who protects them from one another? In that chapter we also caught this someone in the act. The sandbox saw many cores but was allowed to use only one, and time after time someone stopped our processes when they had used up their share. That someone is the operating system. You could get to know it from books, but we have a better way: we have been inside one all along. Every cell of the course runs on a server under Linux, and this chapter is a guidebook to it.

Here is the route. At the entrance we look around and read the plaque with the history. In the first hall we meet the kernel and listen in on what a program asks it for. In the second we see processes, and how one process gives birth to another. The third hall is about why everything in Unix is a file, the fourth about the pipes that connect programs, and the fifth about the shell, the language in which those pipes are laid. In the sixth we find out who we are here and what we are allowed to do. And on the way out, as in any museum, there is a gift shop: the rules by which everything we saw was built. Touching the exhibits is allowed and encouraged: every cell is live.

The entrance: where are we?

First we ask the system who we are and where we are.

The system is Linux. The kernel version could be anything. On the course server it is 4.19.0-gvisor (older versions of gVisor said 4.4.0): that is how gVisor introduces itself, and we’ll get to gVisor below. We are process number 1, the first and, as we’ll soon find out, almost the only process in our world. User number 65,534 is nobody, the user with the fewest rights in the system. And the root holds directories familiar to anyone who has looked inside Linux or macOS: bin for programs, etc for settings, tmp for temporary files, and proc, a window into the kernel that we’ll come back to. There is one of our own as well: data, the course’s data, with the earthquakes and War and Peace from earlier chapters.

Hall one: the kernel

Your program can’t draw a letter on the screen by itself, read a byte from a disk or send a packet over the network. Politeness has nothing to do with it: the program is physically prevented. A processor has two modes. Ordinary programs run in user mode: they can reach only their own memory, and the instructions that control devices and memory are forbidden: a program that tries to execute one is stopped on the spot. In kernel mode everything is allowed. Kernel mode is where the kernel runs: the heart of the operating system and the only program that touches the hardware directly.

When a program needs something from the outside world, it asks the kernel. It puts the number of the request and its arguments into registers and executes a special processor instruction, which on x86-64 is called, fittingly, syscall. The processor switches to kernel mode and jumps to a place the kernel chose in advance; the program can’t choose where to jump. The kernel checks whether the program has the right to make this request, carries it out, puts the answer in a register and hands control back. Such a request is called a system call. This wall between the two modes is where Meltdown from the last chapter leaked through.

How many system calls does the shortest program make? Take the line print("hi"), run in a Python process of its own.

You can listen in on a program’s system calls with the strace utility. The sandbox doesn’t have it, so we recorded the trace in advance on a similar system and put it in /data/os. Walk through it.

A trace is an ordinary text file with one line per call: the name, the arguments in parentheses and, after the equals sign, the kernel’s answer. We can count it the way we counted words in Chapter 8.

The most frequent call is rt_sigaction: Python asks how each of sixty-odd signals is set up and installs its own handler for Ctrl+C, so that it can turn it into a KeyboardInterrupt. Next come newfstatat and openat, “does this file exist?” and “open this file.” In 43 cases the kernel refused, but there is nothing alarming about that. Most refusals are ENOENT, “no such file”: Python looks in every place where the standard library and its modules might be, and it doesn’t find them on the first try. ENOTTY answers the question “is this a terminal?”: Python finds out where its output goes, to decide whether to collect text in a buffer.

The trace has an oddity too: there are five write calls, not one. Four of them write to files with the extension .pyc. This is the bytecode of Chapter 33: Python compiled the modules encodings and linecache and saved the result to disk so that it wouldn’t have to compile them next time. The next time is the strace -c summary in the same folder, taken on a second run: the cache was already on disk, 292 calls were enough, and there was only one write. The cache idea of Chapter 34 works here too, at the level of files.

You can make a system call yourself, without going through print. The os module is a thin wrapper around the kernel’s calls: os.write(1, some_bytes) makes the same write we saw in the trace.

The kernel answered with the number of bytes written: 56, although the line has 52 characters. The letters é and à take two bytes each in UTF-8 and the em dash three, as we saw in Chapter 28. The second experiment shows the price of the wall: even the simplest system call costs several times as much as an ordinary function call (on the course server, as you’re about to find out, even more), because the processor switches modes and the kernel checks rights. That’s why programs try to call the kernel as rarely as they can: print collects text in a buffer and hands it over in a single write.

On the course server the wall is thicker still. Between your program and the server’s kernel stands gVisor, a program Google released as open source in 2018. It intercepts the sandbox’s system calls and carries them out itself, passing only a small, carefully checked share of them on to the server’s kernel. The result is a kernel inside a kernel: even if a reader’s program finds a bug in the implementation of some call, the bug will be in gVisor, and the server’s Linux will stay intact. gVisor also has a mode of its own that resembles strace: it records every system call of the sandbox, but only the server’s owner can turn it on.

Hall two: processes

A program is a file on disk, such as /usr/local/bin/python3. A process is a program while it runs: its code, its own memory, the state of its registers, its open files, its current directory and the number by which the kernel knows it, the PID. One program can run as ten processes at once, like ten open browser windows.

In Unix everything is a file, processes included. There is no /proc directory on the disk: it is a window through which the kernel shows its tables as files. Every process has a directory there named after its number. Tom Killian of Bell Labs came up with it for the eighth edition of Unix and in 1984 described it in a paper called “Processes as Files”; Linux got its own /proc in 1992.

We are alone in our world: only process number 1 is visible. On a laptop this directory would hold hundreds of numbers, but the sandbox lives in a separate process namespace and isn’t shown anyone else’s processes. Process 1 is the program python3, started with the file /opt/cs/harness.py: the course’s service program, which receives your code and runs it inside itself. That’s why your code “is” process number 1. The Threads line says that the process has several threads: service threads forward your output to the page. State: R means “running”: the process reads its own status at a moment when it is, of course, running. VmRSS is how much memory it occupies right now.

How a process is born

New processes in Unix are born by division. The fork call makes an exact copy of a process: the same program, the same memory, the same open files, the same place in the code. Two processes return from fork, and the only difference between them is the answer they get: the parent gets the child’s number, the child gets zero. From this answer each knows who it is and goes its own way. For the child to take up a different job there is a second call, exec: it replaces the process’s program with another one, keeping the number and the open files. Meanwhile the parent waits for the child with the wait call and learns how the child finished.

The number a process finishes with is its exit code. By convention 0 means all is well, and any other number means something went wrong; what exactly is up to the program. The shell, which we’ll come to, runs every command this way: fork, then exec in the child and wait in the parent. Splitting the job into two calls looks odd. Why not a single call, “run this program”? But in the gap between the two the child gets ready: it changes its directory, reconnects its files, lowers its own privileges, all with ordinary code and no special parameters.

Since every process except the first was born from another, processes form a tree. In the diagram below the sandbox runs a command and, while it is running, reads /proc: who is whose parent, what state each process is in, and where its standard inputs and outputs lead.

Choose the pipeline sleep 2 | sort | uniq -c. Process 1, our program, gave birth to the shell sh, and the shell to one process per command. All three run at the same time and spend almost all of it asleep, in state S: sort waits for sleep to write something, and uniq waits for sort. A sleeping process uses no processor time: the kernel will wake it up when data arrives. That is part of the answer to the question at the start of the chapter. Of the hundred processes on a computer, only a few want to run at any given moment; the rest are waiting for something.

Hall three: everything is a file

A process works with files through the kernel too. It asks for a file to be opened by name, and the kernel returns a small number, an index in this process’s table of open files. From then on the program says not “read from /data/os/README.md” but “read from number 7.” This number is called a file descriptor. The process’s descriptor table can be seen in /proc too.

The first three numbers are special, by an agreement that goes back to the first versions of Unix. Zero is standard input, where a program reads from; one is standard output, where print writes; two is standard error, where Python writes a traceback. The program doesn’t know, and shouldn’t need to know, what they are connected to: a terminal, a file, another program. Here all three lead to pipe:[…], that is, to pipes. Whatever goes into descriptor 1 (from os.write, say, or from a command we started) travels down a pipe, and at the other end a service thread of the sandbox packs the text into messages and sends them to this page. Numbers 3 to 6 are service copies and pipes of the same sandbox, and the file we opened got the first free number.

Connecting standard output to a file, or standard input to some other file, means changing what numbers 0, 1 and 2 point to before the program starts. The shell can do this: command > file sends the output to a file, command < file takes the input from a file, and 2>&1 sends errors wherever the output goes. It does this in that gap between fork and exec: the child reconnects its descriptors and then turns into the program it was meant to be, which suspects nothing.

“Everything is a file” is not a figure of speech. Devices in Unix look like files too: /dev/null is a black hole that swallows everything written to it, and /dev/urandom an endless source of random bytes. The kernel’s tables in /proc look like files, and so do the pipes between programs. They are all read with the same read and written with the same write, and that is why the same programs work with all of them.

Hall four: pipes

A pipe is a buffer in the kernel with two ends, each with a descriptor of its own. Whatever one process writes into one end, another reads from the other end, in the same order: first in, first out. It is the queue of Chapter 15, built as a ring buffer from the same chapter. How big is the ring? To find out, we’ll write into a pipe that nobody reads from, until the kernel says there is no more room.

The pipe took 65,536 bytes, or 64 KiB, the default size in Linux. Normally a writer isn’t turned away as ours was: it falls asleep until the reader frees some room, and in the same way the reader falls asleep when the pipe is empty. Every pipeline rests on two more rules. When all the writers have closed their end, the reader, once it has read everything, gets an empty answer, end of file, and knows it is time to finish. And when the reading end is closed, a writer that tries to write is stopped by the kernel with the signal SIGPIPE: there is nobody to read anyway. Python ignores this signal (remember SIG_IGN in the trace?) and turns it into a BrokenPipeError exception. Play with the pipe yourself.

Neither program here controls the other. The writer doesn’t know who is reading, the reader doesn’t know who is writing, their speeds even out on their own through sleep, and the end of the work passes down the chain by itself. That is why pipes are so easy to connect: each program knows only its own input and output.

Hall five: the shell

To connect programs with pipes you need a language in which that is easy to say. It is the language of the shell, the command interpreter, the program that answers you in a terminal window. On Linux it is usually bash, on macOS zsh, and in our sandbox sh, which is dash, small and fast. The shell is an ordinary program: it reads a line, takes it apart, does fork and exec for each command, connects the commands with pipes and waits. The sandbox has no terminal, so the course has a module called cs.shell: its function sh passes a line to the shell and prints it after a $ sign, followed by everything the commands printed.

The trace has 352 lines: 351 calls and a last line about the exit. The last two commands are our first pipelines. cut -d'(' -f1 cuts each line at the parenthesis and keeps the first piece, the name of the call. uniq -c merges identical lines and writes how many there were, but only adjacent ones: in the next-to-last command the calls come in no particular order, and in the first lines each one is counted once. That is why uniq is always preceded by sort, which brings identical lines together. sort -rn sorts by the number at the start of each line, from largest to smallest, and head -5 keeps the first five lines. We got the same answer as Counter gave us in the first hall, from five small programs, none of which knows anything about system calls.

A chain like this is called a shell pipeline, and programs that read standard input, do something with the data and write the result to standard output are called filters. The word appeared right after pipes did: it turned out that almost every utility was worth teaching to read standard input when it isn’t given a file. And here is the rule about the end of the work in action.

yes prints the letter y forever, and head -3 takes three lines and finishes. Now nobody is left to read what yes writes, the kernel sends it SIGPIPE, and the endless program ends by itself. Bash keeps the exit codes of every link: head has 0, and yes has 141, which is 128 plus 13, the number of the signal SIGPIPE. This is how an exit code tells you that a process was killed by a signal, and by which one.

Six lines against ten pages

In 1986 Jon Bentley, who wrote the column “Programming Pearls” in Communications of the ACM, asked Donald Knuth for a worked example of literate programming, his way of writing a program as if it were a book. The problem was to find the $k$ most frequent words in a text. Knuth wrote more than ten pages of carefully explained Pascal with an ingenious data structure. Bentley asked McIlroy to review it. McIlroy praised the exposition and then showed a solution in six commands:

Here it is on War and Peace, in Louise and Aylmer Maude’s English translation. For an English novel McIlroy’s A-Za-z ought to be enough, and tr A-Z a-z takes care of the capitals. But the novel also has Hélène, Pierre’s wife.

The first command does its job, and the five most frequent words are as dull as you’d expect. The second shows what the same command does to Hélène. tr dates from the 1970s and works with bytes, and in UTF-8 the letters é and è take two bytes each, as we found out in Chapter 28. Neither byte is a Latin letter, so tr cuts the name into three words, H, l and ne, and Hélène never makes it into the word count. The third command does the same counting with tools that understand the encoding: grep -oE '[[:alpha:]]+' prints each run of letters on a line of its own, and sed 's/.*/\L&/' converts the line to lower case; the result goes into a file, redirected as in the third hall. Six programs, about a second, and we have the novel’s word frequencies, which in Chapter 8 we counted with a Python dictionary. Hélène is in it now: 165 times, 390th place.

McIlroy ended his review sharply. Knuth, he wrote, had shown “how to program intelligibly, but not wisely,” and had made “a sort of industrial-strength Fabergé egg,” refined and wonderfully worked, “a museum piece from the start.” A wise engineering solution, in his view, would be built from reusable parts, and the simple pipeline would “get answers right now, not next week or next month.”

Python has a relative of pipes too: the generators of Chapter 10. A chain of generators passes data along one item at a time, like a pipe, and no link holds the whole stream in memory. sort, on the other hand, is a link that has to read everything before it can give out its first line: you can’t sort what you haven’t seen. Repeating sort | uniq -c in Python is the chapter’s first task. Meanwhile, here is a terminal. It runs every command in a fresh sandbox, so files created in /tmp don’t survive until the next command; chain commands with ; or &&.

Hall six: who are we here?

The kernel doesn’t only carry out requests; it also decides who may do what. In Unix every process has a user, and every file has an owner, a group and nine permission bits. Here they are.

A string like -rw-r--r-- is read in threes. The first character is the type: - for an ordinary file, d for a directory. Then come three triples of permissions: for the owner, for the owner’s group and for everyone else, and each triple has r (read), w (write) and x (execute, or, for a directory, enter it). /etc/passwd belongs to root; everyone can read it, and only the owner can write to it. Permissions are bits, and chmod 600 writes them as an octal number: 6 is 110, read and write for the owner, and 0 is nothing for the rest. After chmod 000 even the owner can’t read the file: the kernel looks at the permission bits and makes no exception for owners.

There were two refusals, and they were different. Appending to /etc/passwd was blocked by permissions, since the file belongs to someone else: “Permission denied.” Creating /hello was blocked by a different wall: the whole root of the sandbox is mounted read-only, “Read-only file system,” and no permissions would have helped. Even root (user number 0), whom the kernel allows almost everything, would have nowhere to write here. And we aren’t even root; we are nobody. The only place we can write is /tmp, and this directory has a special letter t at the end of its permissions: anyone can write into such a directory, but only a file’s owner can delete it. On top of that, our process has been stripped of all the kernel’s special privileges, and it has no network. A sandbox where readers run whatever code they like has to be like this: every wall here is a system call that the kernel will refuse.

The environment

A process gets one more thing from its parent at birth: environment variables, “name = value” pairs that configure programs without changing their code. The most useful one is PATH, a list of directories, separated by colons, where the shell looks for a program when you type ls without a path. HOME is the home directory. The environment is copied into the child on fork and kept on exec, but it is a copy: whatever the child changes in its own, the parent won’t see.

Writing NAME=value command puts the variable into the environment of that one command: the child sh sees it, but the parent doesn’t have it. This is how in Chapter 16 we switched off hash salting with the variable PYTHONHASHSEED: with it set, two separate runs of Python give the same hash. The last line takes us back to the .pyc files of the first hall. The sandbox sets the variable PYTHONDONTWRITEBYTECODE, which tells Python not to save its bytecode cache, since there is nowhere to write it anyway. Every Python started from the shell obeys it. With the -I option, though, Python ignores environment variables. Process 1 was started with this option (remember its command line in the hall of processes), and what keeps it from saving the cache is permissions and the read-only root. We used the same option to record the trace on an ordinary system, and there Python saved four .pyc files.

On the way out: the Unix philosophy

Everything we saw in the halls was built by a few rules, and it was McIlroy again who wrote them down. In 1978, in the foreword to a special issue of the Bell System Technical Journal devoted to Unix, he and his co-authors described the style that had grown up among the system’s creators. The first rule: “Make each program do one thing well. To do a new job, build afresh rather than complicate old programs by adding new ‘features.’” The second: “Expect the output of every program to become the input to another, as yet unknown, program.” In 1994 the Unix historian Peter Salus summed this up in three sentences that are quoted more often than the original: “Write programs that do one thing and do it well. Write programs to work together. Write programs to handle text streams, because that is a universal interface.”

These rules can be seen in the course’s sandbox itself. Your cell prints text. The service part of the sandbox does one thing: it turns the text into events, one JSON object per line, and writes them into a pipe. The server does another: it passes these lines on to the page as they appear. And the page does a third: it draws them under the cell. None of the parts knows how the others work, and any of them can be replaced. It is the same kind of pipeline, except that its pipes run across the network.

The philosophy has its price, and we’ve seen that too. A text stream is a universal interface but a loose one: tr cut Hélène into pieces because to it “text” means bytes, and a file name with a space in it breaks half of all one-liners. That is why Python programs and formats like JSON live alongside pipes. But the habit of breaking a problem into small parts with simple connections will serve you in any language.

Tasks

Three tasks: repeat the pipeline in Python, count a file as fussily as wc does, and write a few one-liners. The tests check your answers against the sandbox’s own utilities.

What next

The tour is over, but one question from the start of the chapter is still open. Sleeping processes don’t use the processor, but what about the ones that want to run? In the pipeline sort | uniq -c on a large file, both links are working. On a laptop right now a browser, a music player and a compiler all want to run, and there are, say, two cores. In the last chapter the kernel stopped our processes time after time and then let them go again. By what rule does it choose whom to stop and whom to let run? A hundred processes, two cores. Who’s next? That is the subject of the next chapter, and it begins on July 20, 1969, a few minutes before the landing on the Moon, when the onboard computer of Apollo 11 found itself overloaded.