When Unix learned to reboot(2).

History of Reboot(2)

Recently, a friend asked me the history of halt, and when did we have to stop with the sync / sync / sync dance before running halt or reboot. The two are related, it turns out.

That sync; sync; sync Thing...

If you go looking around the net, you'll find some people giving advice like "when shutting down, type 'sync; sync; sync; halt' to be safe." There's good reasons behind this advice which aren't immediately clear and are interesting to explore. Before exploring, I'd been told that the reasons for the sync dance were a driver bug in v6 that's been fixed 45 years ago... But it turns out whoever told me that must have been mistaken because the code tells a different story...

The sync program called the sync system call and exited (and still does). The sync system call in research editions of unix was implemented as approximately:

foreach mountpoint

    write superblock with bwrite

for each dirty inode

    write the inode with iupdat

bflush

 

It would step through the fixed list of buffers in the system, writing the dirty ones out. It used bwrite() to do this, which was synchronous.  Each write had to complete before the next one started. iupdat will read the inode off the disk, update that inode, and write out, again synchronously. bflush writes everything with bwrite, but marks the buffers as B_ASYNC which means in that case it won't wait. And nothing else waits either. So, recommendation for typing sync 3 times, one line at a time, was to give time for the buffers to drain (the subsequent syncs would schedule no new I/O on a quiet system). Typing all three on one line with semicolons, didn't give this time...

If you look at the recommendation, it's actually quite smart. Typed one line at a time, waiting for the prompt each time, would schedule a lot of I/O the first time, then give the operator a harmless task to do for a few seconds that would allow the I/O to complete before they did anything. The kernel avoided all kinds of nasty deadlocks that later systems would face when they implemented waiting for the I/O to complete.

Edit: One bit of lore that was passed on to me was the first sync returned right away, but the second one blocked.... I've found no evidence of that in BSD or System V based systems... although there is an increasing amount of protection against multiple threads being in the sync code as concurrency in Unix increased.

Why not do this in reboot(2)?

None of the versions of Research Unix had a system call to reboot. To restart things, one killed init with SIGHUP, which would in turn kill everything else and fork a new shell in single user. There was no other way to restart the system, and bad things happened if init actually died. But there was no clean reboot option, nor any way to stop the kernel cleanly (apart from the power switch).

Looking at the sources, there was one small hint that something was planned, but never executed. All the system calls were defined in /usr/include/sys.s. A close examination shows the following:

lock    = 53.

ioctl   = 54.

reboot  = 55.

mpx     = 56.

setinf  = 59.

which proves me wrong, right? Well, maybe not. Looking at sysent.c, we see the following:

1, 0, syslock,          /* 53 = lock user in core */

3, 0, ioctl,            /* 54 = ioctl */

0, 0, nosys,            /* 55 = readwrite (in abeyance) */

4, 0, mpxchan,          /* 56 = creat mpx comm channel */

0, 0, nosys,            /* 57 = reserved for USG */

0, 0, nosys,            /* 58 = reserved for USG */

3, 0, exece,            /* 59 = exece */

which lists 'nosys' as the handler, so there's no implementation. There's no reboot system call. I'll also note that there's another disconnect: system call 59 is listed as setinf (whatever that is), but is implemented as exece.

Enter 4BSD

The first reference to reboot(2) I can find is in 4.0BSD in sysent.c, we see the following;

3, 0, ioctl,            /* 54 = ioctl */

1, 0, reboot,           /* 55 = reboot */

4, 0, mpxchan,          /* 56 = creat mpx comm channel */

where reboot landed in the slot allocated for it. There's a new command in /etc/ that calls it (by the syscall number, not the normal wrapper). It wasn't in 2.8BSD, but is also present in a similar form in 2.9BSD and later. 3BSD still has the placeholder pointing at nosys. Since the 2BSD evolution tracked 4BSD, I'll not call it out further.

In 4.0BSD (1980), reboot() just call a machine dependent boot() routine. It called update(), which scheduled the writes as described above. It printed that it was waiting for the IO to finish. However, the 'wait for it' code was basically 'sleep(5)' and so if all the data didn't get out in 5 seconds, bad things would happen. So the "sync sync sync halt" dance was still useful advice. It would get thee ball rolling and easily double the amount of time that the data had to make it to the disk, depending on the typist... 4.1c (1982) bumped this to 10s and had ifdef'd out code to try to wait for all the dirty buffers to clear.

In 4.2BSD (1983), the wait for the writes code is engaged. It tries up to 20 times to walk the list of bufs in the system to let the buffers drain. So progress is made here. 4.3 adds a delay that's 40ms * iter (total of 8.4s)... which remains through at least 4.4BSD (1993)...  So while things got better, so did systems, and more and more I/O could be piled up. Successor BSD systems improved on this as well, including various ways to solve it (mostly when systems got big enough so update(8) couldn't flush all the I/O in 30s before the next sync call started).

AT&T Unix

Meanwhile, on the AT&T side of things...  System III (1980) didn't have anything. System Vr1 doesn't have anything. None of the Programmer Work Bench releases (PWB) have a reboot(2).

System Vr2 (1984) defined a new uadmin(2) system call. It acted like an indirect system call (you passed it what you wanted it to do as the first arg). One of these, A_REBOOT, is called from fsck, but the kernel doesn't implement it.

Fast forward to System Vr3 (1987) and we find an implementation. It's basically a call to umount for the / filesystem followed by a call to reset the CPU. The other filesystems are unmounted as part of shutdown process before uadmin(A_REBOOT, ..) gets called, so only / remained mounted by the time it's called. This call to umount flushes the dirty buffers, and cleanly unwinds everything else so nothing is pending when the call to the CPU reset happens. So finally the 'sync sync sync halt' problem had been solved... Well, maybe... There's no timeout, nor any way to avoid deadlock. Still, a fairly clean solution to the issue, especially relative to what BSD was doing at the time.

Commercial Unix

The availability of even leaked source from the early days. By the time SunOS gets to 4.1, however, there was a vfs_syncall() which the MD boot() function called to synchronize everything (it only returned when all the scheduled I/O was done). I've not checked to see if there was a halting problem here or not, but empirical evidence of rebooting a lot of suns suggests that it was rarely a problem in practice if any of the I/Os somehow got wedged...  Or that I was lucky enough not to have a large enough fleet of machines where flaky disk problems start to show up... I can't find any earlier versions of the Sun sources, so it's hard to know when this solution entered into the tree (the code I have looked at dates from 1994, 11 years after the initial release).  I suspect Sun solved this problem early, but have no proof of this beyond a hunch.

Other Unixes, that aren't just System V ports, are hard to find in source form, so I can't say from original sources whether or not they solved the issue or not prior to System Vr3. There were also a lot of 4.2BSD and 4.3BSD ports that didn't survive either to be examined.

The one exception to this general rule was a copy of the Unisoft 1.0 kernel I found on bitsavers. It dates from 1986 (so relatively late). It has a reboot system call (number 64, not 55). That system call calls update(), like 4BSD's, but then does a big for() loop (1 to 1,000,000) before calling a routine that resets the CPU. This kernel is a V7 port, and most likely got the idea (and maybe the code) from one of the 4BSD releases. This kernel appears to be the basis Sony's SUNIX (which appears to be a 7th Edition-based Unix that predated SONY's NEWS-OS based on 4.2BSD). NEWS-OS likely behaved like 4.2BSD, but I can't confirm that due to lack of sources. If you know more info about SUNIX or NEWS-OS, please leave a comment.

Linux

Linux's sync call is synchronous. You get the same guarantees as you do from fsync. This behavior was introduced in 1.3.20, released in 1995. Prior to that the same sync dance advice was useful since early versions of Linux were more aggressively asynchronous in their handling of disk writes than other contemporary systems. While this helped it compete in benchmarks, it caused data integrity problems when Linux machines started to be put into production (which was one of the reasons motivating the change). Modern Linux systems flush out all the dirty buffers as part of the shutdown sequence and wait for the flush to complete before proceeding to reboot, turning the system off or halting.

Conclusion

For years, I'd been told the reasons for the 3 sync dance was due to a driver bug, long since fixed, in a DEC disk driver in v6. However, digging into it shows that there were decent reasons for doing this dance, even after Unix learned to reboot() itself.

Traditional Unix Toolchains

Older Unix systems tend to be fairly uniform in how they handle the so-called 'toolchain' for creating binaries. This blog will give a quick overview of the toolchain pipeline for Unix systems that follow the V7 tradition (which evolved along with Unix, a topic for a separate blog maybe).

Unix is a pipeline based system, either physically or logically. One program takes input, process the data and produces output. The input and output have some interface they obey, usually text-based. The Unix toolchain is no different.

Overview

Here's a simplified view of what's going on. We'll add more detail later.

In this view, the C compiler takes .c code and turns it into assembler. How it does that, and how it optimizes, etc is for another blog post. Once the assembler is created, it's passed to as(1) which translates the assembler into .o files. The .o files contain the binary representation fo the assembler, plus a lot of metadata about it: what addresses correspond to what symbols, how to relocate the raw assembler when connected together, various debugging information (sometimes) and what section each bit of data resides in. You cannot directly execute a .o file. ld takes all the .o files and produces an executable (the default name of which is a.out). a.out files are executable. They happen to be in the same format as the .o files, except they have a different magic number which tells the kernel how to load them into memory and initialize the CPU's registers for that program.

Program Layout

In traditional unix, there were only three sections to a program. There were no shared libraries or other fancy things done by the linker (such as linker sets). The world view was much simpler. There were three sections, each one had a size. There was the 'text' section. This was the executable code. There was the 'data' section, which contained initialized data. And there was the 'bss' section which also contained data that was initialized to 0. 

The heap resides above the bss and is managed by the unix sbrk(2) system call. The so-called "break" is set to the end of the bss segment (often referred to by the symbol ebss). Malloc(3) is built on top of sbrk(2) and will manage returning bits to the OS when it can.

For the PDP-11 and other segmented architectures, there can be complications. There can be separate I&D space (instruction and data) so that each one resides in it's own address space. This helps PDP-11 programs break the 64k limit. In addition, there can be overlays. Overlays are 8k segments that are mapped into the address space as needed to increase the text size of the program. The linker handles much of this, but the programmer must specify the overlap groups. Each group can be no more than 8k in size, and the main program can be no more than 56k in size (and the overlay manager uses 8k of the data segment as well). Programs in unix tend to not use overlays, but the kernel makes heavy use of them.

Compiler (cc, f77, etc)

Compilers create assembler output. Compilers, like the C compiler, may invoke other programs to do this. The C compiler runs the source through cpp to create an intermediate file (.i files) that it runs through the first pass of the C compiler. There are a number of other passes of the compiler that take the initial output and optimize it in various ways (usually by parsing and rewriting assembler). The final output of the compilers, at least in this era, is always textual assembler.

Assembler (as)

The assembler is the only thing in the system that creates .o files. Well, not strictly true since ld can also take .o files and produce a .o file from it, but true enough. The assemble takes the textual assembler and creates a .o file from that. The .o file includes information about how to relocate it (ld uses this info), what symbols go where, what bits are in the text section, what is in the data, etc.

Archive Files (ar)

It's fairly expensive to open a lot of files on Unix, especially if they are small. It's also inconvenient to carry around a number of different files to implement something. So unix ld also supports reading files in from an archive. An archive adds some headers to describe the file and then places a copy of the file into the archive. Unix has had a number of different archive formats (I could do a mini-blog entry on all of the ones through 4BSD), but conceptually they are all the same. The ar(1) program is used to create and manage .a files for this purpose.

One motivation for the library is to save space. If it's efficient to create a lot of tiny .o files, then the loader can only bring in what's needed saving space. When the address space is only 64k (or 64k+64k for separate I&D machines), every little bit helps. The archiver removes the overhead of having to do directory lookups on hundreds of files by creating a container for those objects that ld doesn't have to process by name.

When processing through a library, ld looks at each .o that's in the archive for symbols and includes it if it finds any that are needed for the current image so far. It just does one pass through an archive, though. This means if you have foo.o and bar.o in the archive and foo.o depends on bar.o somehow, foo.o needs to come first so that ld can find bar.o later. If they are in the other order, then ld may pass over bar.o entirely and then when it is processing foo.o, it will not go back and look for it.

lorder(1) and tsort(1) are used to try to optimize the order of the .o's in the library to make it possible to just do one pass through the library (though when you have circular dependencies, you're back to this same issue). lorder uses nm(1) to read all the .o's on the command line and produce dependencies. tsort takes these dependencies and sorts them into a list in the proper dependency order where possible. When cycles exist, it produces an order that minimizes passes required to resolve them all.

That sounds quite inconvenient, and it is. libc.a, especially in newer versions, has a number of circular dependencies that a single pass fails to resolve. One can work around this issue by specifying libc multiple times (which is unsatisfying, even if it doesn't produce a binary with two copies of everything), or do something else. The something else involves adding a table of contents to the library. A program called ranlib will read through an archive creating an index of defined symbols that points to the offset in the file that he .o with that symbol is present at. It does this by creating a first member of the archive named __.SYMDEF and placing its table in there. The format of the table is something that ranlib and ld agree on. ld uses this table to include files that are needed and to be able to seek backwards easily. In effect, this is the same as ld doing two passes over an archive (one to build this index, and one to process it), but in effect precomputes the first pass to keep ld simpler.

Loader (ld)

The linker can operate in two different modes. The first mode most people are not familiar with. In this mode, it will take .o files and partially link them together to produce a new .o file. libc uses this mode of operation to create all the assembler glue to call system calls and optimize out some of the local labels that the assembler produces and expects ld to optimize away. Since these files are consulted so often, the build process of libc does it at build time so that every invocation of ld later can be faster.

The second mode is the mode people are more familiar with. In this mode, ld combines a number of .o and .a files to create an executable (a.out by default, so that's what people call executables in general). a.out binaries lacked shared libraries, so ld produced the final output. This was both good and bad. It wasted space with all those copies of libc, but it also produced self-contained binaries that didn't need any external libraries to work. The PDP-11 didn't really have good demand paging hardware, like the later VAX machines, so was a poor fit to shared libraries. Shared libraries generally rely on mmap(2) working and larger address spaces to map the libraries in at. mmap(2) requires a page-grained MMU, which didn't usefully exist on the PDP-11 (it had 8k segments, which was far to large a percent of the whole address space to be useful). One good thing about binaries being self contained means that if the kernel can run the system calls that are in it, the binary will work. This has allowed PWB systems to be able to execute both v6 and v7 binaries, despite the two having different system call interfaces.

The Kernel

Speaking of the kernel, the kernel is the last step in the toolchain, or can be thought of as such. The kernel reads in the headers from the a.out files, and sets up the address space for the process when a new a.out binary is exec'd. It uses the layout I showed above, or some variant of it, to set things up, to populate memory and makes whatever arrangements with the MMU to protect the pages from other processes (if possible, some systems like an 8086 don't have MMUs but do have segments so can fake all this except the memory protection benefits). For separate I&D space binaries, it also sets up the segment registers for that to work.

The stack is also initialized. The detail of exactly where it goes varies somewhat. It's usually located with the data segment since it holds data almost exclusively. Stacks in this era were usually quite small. This tended to drive programs that had shallow call graphs and that made use of more global variables than a more modern style would suggest. All these things conserved stack space, though it's generally agreed today that it required more effort to read and understand because the context is spread out over more parts of the program than more modern coding practices tend to produce.

Conclusion

Without the complications of shared libraries, or link time optimizations, the tools of this area tended to be rather simple. They had simple interfaces between them. There were good boundaries between the different components. This limited the number of programs with knowledge of the formats for the different layers. Due to this limited spread of knowledge, switching out different parts for other parts often could be done without changing components that didn't directly know about the object format. This also produced simpler programs that used different engineering tricks to get the most performance out of the limited hardware of the day. The PDP-11s were approximately 0.1-0.5MIPS machines in this time frame with super slow I/O paths. This is about 100,000 times slower than most computers people interact with today. One advantage of the thoughtful engineering trade offs is that all the pieces are relatively easy to understand.

The modern ecosystems that we have today are more complex. ELF came along in the 90s and obsoleted the text, data, bss world view. shared libraries made huge programs, like X11, feasible. Today, clang bypasses the separate assembler stage and generates .o files directly. The llvm linker, lld, can optimize binaries between modules to produce better code. All these new features added complication to a simple model. While I morn for the loss of simplicity, I've become too used to the rich features they provide to want to go back. Understanding the roots of this complexity, though, helps to understand some of the weird quirks that persist, even to this day.

And speaking of weird quirks, I'd like to end with 'bss'. It's a 1950s IBM assembler mnemonic for 'block started by symbol' and was used to create storage that was associated with a symbol, but had no initial value. Today, 'bss' is no longer that, exactly. Its origin has been lost, for most people, in the sands of time and now it just means 'zeroed storage area'. So this very Unix centric term actually predates Unix by 10 or 15 years for a machine that Unix wouldn't run on until it was 10 or 15 years old... Here's a snapshot from the IBM assembler manual, available from the UA-SAP wikipedia page

showing the original source...

[[ This blog edited to include snapshot of the BSS manual entry ]]

v7 compilation for simple .c's in /usr/src/cmd.

After about 4 and a half hours of build time, I have results to share. There's 110 .c files in /usr/src/cmd. 85 of these compile and link (it's unclear if they run). 25 have a compile or link error:

• accton, sa (lack of acct in libc)
• ar, nm, prof, ranlib, size, strip (mismatch between NMAGIC/OMAGIC and ARMAGIC_X)
• arcv (obsolete conversion program written in old style)
• clri, dcheck, dump, dumpdir, icheck, mkfs, ncheck, quot, restor (inode differences)
• dmesg (message buffer issues?)
• getty (freaks out compiler)
• graph (missing symbols for curses and libm stuff)
• osh (old shell? Written in funky style)
• ps, pstat (proc definition differences)
• tc (silly compiler issue, trivial to fix, but I have not Tek4015 terminals)

So 10 classes of issues for the affected files. Not too terrible. But there's other issues that will need looking into. 'ld' compiles fine, but it works on pdp11 a.out files, for example. cc compiles, but doesn't have the venix specific switches. I've written a shell script to do this, not a Makefile, and the commands used aren't quite right. Venix appears to support different amounts of stack under the data segment (but without docs, it's hard to know what flags I need), but none of my binaries have those. There's NMAGIC and OMAGIC binaries that have different meanings, and so on. All this makes the 'file foo /bin/foo' differ. Plus I haven't done the more complicated commands, nor have I poked at the compiler apart from cc, nor the kernel really at all, nor the libraries, nor the .y files. And factor.s and prime.s are pdp-11 assembler, so I'd have to pull those in from somewhere.

But given that almost all the normal commands compiled just fine, and many appear to work gives me hope that I might be able to reconstruct the sources used to build at last parts of the system. For some reason, that's appealing to me, but I can't really articulate a reason why, or come up with why that might be useful. Though it seems like a fun background project to celebrate the 40th anniversary of Version 7 in a couple of  years. Though running it on a 35 year old computer at that point may limit its appeal...