/* You Are Not Expected to Understand This */

The title of this post, you are not expected to understand this, is one of the most famous comments ever. It is in the v6 version of Unix, the mother operating system of Linux, Android,and iOS. Unix was developed by Dennis Ritchie and Ken Thompson at Bell Labs in the early 1970s. When I say "comment" I am using the word in the technical sense of an annotation to the source code for human readers that is ignored by the compiler.

John Lions

The v6 version of Unix was especially famous because John Lions of University of New South Wales in Australia wrote an annotated version of the source code which was used by many computer science departments to teach operating system design. That is the orange book below.

But AT&T decided to make money on Unix and insisted that Lyons book could only be used in schools that were paid-up Unix licensees (since it contained a copy of the source code). That had approximately zero effect, and everyone simply photocopied it like samizdat publications in the Soviet Union. Eventually, the book was published through normal channels and you can still buy it on Amazon. Interestingly, the cover, above on the right, shows students illicitly photocopying the original version. My copy from postgrad days was a photocopy. I only discovered the cover used to be orange when writing this post.

One part of the code is concerned with what is called a context switch. The same thing is going on in your laptop, and even your phone, but since you are the only person using it then it is less obvious. Back in the 1970s, computers were too big and expensive to give everyone their own, and so they were shared, an approach known as time-sharing. Each user would have a keyboard and screen and be connected to the computer over a wire (there were ways to do dialup too). The trick was that it seemed to each user that they had the whole machine. The operating system would switch from one user to another as they hit keys, or the clock interrupted, and so on.

Processes

I still remember my first operating system course when Roger Needham, who was the lecturer, explained the notion of a process. It was a wonderfully simple and elegant idea once you understood it. I'll try and explain it. A computer, like the PDP11 that the early Unix ran on, had a number of general-purpose hardware registers (used for calculation, word processing, and so on), and a few other more specialized ones. Each user (actually each process, but let's just assume each user is only doing one thing at a time) had a little bit of memory allocated that was large enough to hold a copy of these registers. When one process was done running (for example, it was waiting for its user to type a key, which takes place approximately every century in computer time) then the operating system would perform the context switch. All the general and special registers would be saved in the special bit of memory for that process.

Then a new process would be selected to run next. There always is one, since if there is no real work to be done, there is a sort of last-ditch process called the idle process, which is always ready to run (and does nothing when it does, just wasting time until something more useful needs to be run). To run the new process, the general and special purpose registers were loaded from the saved values in the special piece of memory for that process, which were saved the last time it ran. When the code starts to execute, it looks to the user sitting at the terminal as if nothing has happened in between keystrokes, but actually, the system got on with all the other things that other users wanted to achieve.

You are not expected to understand this

The famous comment occurs at the end of the little bit of code in the operating system that gives control to the new process after it has loaded some of the registers. Having written my share of code like this, I'll point out that it is pretty tricky. After all, having loaded the registers, the operating system is in a sort of halfway-house, with some registers containing operating system values, and some containing the new process values. So everything has to be done very carefully in the right order. Here's the code from the 1975 Unix v6 source:

        /*
	 * Switch to stack of the new process and set up
	 * his segmentation registers.
	 */
	retu(rp->p_addr);
	sureg();
	/*
	 * If the new process paused because it was
	 * swapped out, set the stack level to the last call
	 * to savu(u_ssav).  This means that the return
	 * which is executed immediately after the call to aretu
	 * actually returns from the last routine which did
	 * the savu.
	 *
	 * You are not expected to understand this.
	 */
	if(rp->p_flag&SSWAP) {
		rp->p_flag =& ~SSWAP;
		aretu(u.u_ssav);
	}
	/*
	 * The value returned here has many subtle implications.
	 * See the newproc comments.
	 */
	return(1);

As Lion's commentary says:

This code is operating system code, unlike something that would happen in a normal program. The "retu" statement overwrites the return address (and some other registers) on the stack with the value from the little saved block for that process. The return statement at the end will pull that return address off the stack and go there. In a normal program, the return always goes back to where a procedure was called from, since a normal user doesn't get to play around adjusting the return address. But there is a complication, that if the process was swapped out (had all its memory written to the disk) then it needs to return to a different place because it shouldn't return back to the swap code that was running when the old process finally gave up control. Instead, it needs to return to a special value the swap code saved before it did its work. The return statemnt at the end will return to the equivalent place, whether the process was swapped out or not, reload the rest of the registers, and the user program will carry on as if nothing had happened.

Ken Thompson Didn't Understand It

Interestingly, years later, Ken Thompson admitted that the reason that it was so hard to wrap your head around what is going on is that it is wrong. As Thompson said:

The real problem is that we didn't understand what was going on either. The savu/retu mechanism for doing process exchange was fundamentally broken because it depended on switching to a previous stack frame and executing function return code in a different procedure from the one that saved the earlier state. This worked on the PDP-11 because its compiler always used the same context-save mechanism; with the Interdata compiler, the procedure return code differed depending on which registers were saved.

What this snippet of code above got wrong was the assumption that you could just put return at the end of the snippet, and it would execute exactly the same code as the procedure that had actually been called. On the PDP that was true, but on other systems it was not. So they fixed it to work and removed the famous comment.

Teaching Computer Science

But a modern operating system is simply too big to use for a university course. Linux is 15+M lines of code. As Ken Thompson is quoted on the cover of Lions' book:

After 20 years this is still the best exposition of the workings of a real operating system

But at only 9,000 lines, Unix v6 was tractable, people continued to study it (and maybe still do), and the famous comment lived on. The fact that every smartphone operating system owes its heritage to this system makes it remain historically important today. And every supercomputer, and most cloud servers. It has to be the most influential 9,000 lines of code of all time.

Reading real programs is a part of learning computer science that should be emphasized more. As an undergraduate, we mostly programmed in BCPL, a local Cambridge language that is the fore-runner of C and C++. We had access to the full source code of the compiler and reading it was as valuable as the more theoretical aspects we learned in our compiler-writing course. Today, with open source, it is easy to read the source code for many systems actually in use (Linux, the Apache web server, Hadoop, TensorFlow, and thousands more) but these are hundreds of thousands, if not millions, of lines of code. As I said above, Linux is somewhere between 15M and 20M lines of code, depending on just what you include.

Just as no English teacher is going to teach only writing, without also expecting students to read good writing (although who knows what goes on in English departments today), no programming teacher should expect to teach only writing, without expecting students to read good programming. I suppose you could say that due to Lions, Unix v6 became the To Kill a Mockingbird of computer science.

If you didn't understand this post...well, I did warn you. It's the title of the post.

 

Sign up for Sunday Brunch, the weekly Breakfast Bytes email.