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 ]]

Old-school Disk Partitioning

Old-School Disk Partitions

Unix started out life in 1970. Many of the things it did, it had to invent on the fly. Disk handling was one of those items. Something we take utterly for granted today was, once upon a time, an area of active innovation. This blog will explore the early days of Unix: when we had static partitioning compiled into the driver.

Typical drive of the era: large, and difficult to manage (an RL01 or RL02 by the looks of it good for maybe 5MB or 10MB of storage).

Evolution of Partitions

Unix from the earliest days had at least two types of data that was stored on disks. The first type was a file system, which offered a hierarchical name space. The second type was swap. Unix was a swapping system from the earliest days, and to multiplex jobs into and out of memory. The kernel would keep track of what blocks were assigned to which process.

Since the disk played two different roles, with different allocation policies and persistent storage. To keep things simple, in the first edition, the disk was partitioned in a static way. The file system used its part of the disk, and swap used the rest.

DEC never did produce a partitioning standard (though later it used Unix's on its Unix-related products). This mean that the Unix guys had nothing to draw from, and so failed to produce a standard before Unix left the research group.

1st through 3rd Edition

There was almost nothing resembling partitioning in the 1st-3rd edition kernels. Unix booted off the 'drum' device using the top 64 blocks to store itself. The rest of that disk was reserved for swapping processes into/out of core memory. The sources refer to this as 'the drum' and there were 1024 256-byte blocks in the drum.

The disks were presented as a device node, which was the entire disk. This is from the 3rd edition manual page:

rk? refers to an entire RK03 disk as a single sequentially-addressed file. Its 256-word blocks are numbered 0 to 4871. Like the RF disk and the tape files, its addressing is block-oriented.

which describes a single file that has its entire block store available. The 3rd edition has the enigmatic /crp filesystem documented for one of the drives (I wonder what it's an abbreviation for):

/dev/rk0	/ filesystem
/dev/rk1	/usr
/dev/rk2	/sys
/dev/rk3	/crp

which also shows that you had one filesystem per disk. At 1.2MB, these drives are little bigger than a floppy disk, so having just one filesystem per drive was not much of a limitation. Also note that the sector size was 256 words, or 512 bytes.

Since we have limited sources for this time period, it's hard to say for sure. The bulk of the surviving data, though, says at most the last 64 blocks are reserved for Unix...

4th Edition

With the 4th Edition, we start to see multiple files that refer to different sections of the disk. This was done because the new rp03 drives supported 81200 blocks, which exceeded the limits of the time of 65536 blocks per device. It also allows the drive to be broken up into more manageable chunks. In this release, there were 8 different files in the /dev directory named rp0 to rp7. For a second drive connected, rp8..rp15 would reference that drive. The manual has this table in it, which mirrors the surviving code:

disk	start	length
0	0	40600
1	40600	40600
2	0	3200
3	3200	39000
4	42200	39000
5-7	Unassigned

which allows basically two configurations for the drive: split in half, or split into a small root partition and two others. But where's the partition for swap?

There isn't one... Swap space in the 4th Edition was configured in param.h #defines. You defined the device, start and length on that device to use. The system would then configure that during early boot. The down side, though, of #defines was one couldn't easily do a binary patch. Swap was put in between the used parts of other of the disk. This was tricky to get right, since you had to map out the system.

You'd think that all the drives were like this, but that's not the case. The rf(4) driver specified the size of the drive itself with different minors. The rk(4) driver allowed one to experiment with different interleaf factors with different minor numbers. It really was up to the drive itself to decide how to interpret the minor number. This isn't unusual.... the various magtape drivers used minor numbers to specify density and whether or not to rewind on close.

5th and 6th Editions

The 5th edition continued the evolution. It changed the table above and there's a number of overlapping regions that need special care to be used. This also meant that you'd have to re-install the system, or hack the tables in the driver when you upgraded, if you used xp3 or xp4. There was only about 7 months between the 4th and 5th editions, so I suspect this problem wasn't too common. When 4th edition came out, there were 20 sites running it, by the 5th edition it was up to 50, so the numbers weren't huge. Since the kernel was patchable with adb or front panel switches, this issue likely could be mitigated enough to rebuild. Folks running 4th edition were trailblazers, by definition, so could be expected to cope with any upgrades they were doing to the 5th edition. By the time the 6th edition came out, it was in the hundreds or thousands, which may explain why it remained constant between 5th and 6th edition releases. The rp(4)'s predefined table became this:

disk	start	length
0	0	40600
1	40600	40600
2	0	9200
3	72000	9200
4	0	65535
5	15600	65535
6-7	Unassigned

Swapping was still handled by using the space between the partitions or after the end of the filesystem. The 4th edition way of configuring swap was improved by moving the defines to variables that can be more easily patched with adb(1). So through the 6th edition, swap still didn't need its own partition.

What is interesting is that 5th edition introduced raw character devices as well as block devices used for filesystem.

The 6th edition uses the same tables as 5th edition. It also introduces other disk interfaces with similar hard-coded partitions using a similar scheme.

7th Edition

The 7th Edition changes the layout again. It wasn't to be mean, but was because DEC introduced newer, larger drives. 7th Edition also allows larger partitions, as disk addresses are now 3 bytes instead of two. Some drivers now support multiple drives, so the partitions are fixed, but setup so that different layouts of the devices are supported, as well as different models.  For example, the hp(4) driver supports both the rp04/rp05 and the rp06 drives (which are twice as large as the rp04/rp05 drives) so has a number of different layouts that align to this size difference so they can be used on as many different drives as possible. The hs(4) driver was also added as well, but it was more of a swap / drum device.

The problem in the PDP-11 world is that new controllers have been appearing, some from third parties, and the number of disks you can connect to the PDP-11 has started to proliferate. This problem was only going to get worse.

2BSD through 2.11BSD

Skipping ahead a bit, the 7th Edition begat 2BSD which begat a series of releases for the PDP-11 (starting amusingly enough with the 'last' PDP-11 release: 2.8BSD!). By the time we get to 2.11BSD, we have a system that has about 50 different types of disks and partitioning schemes that are increasingly difficult to manage. Each one is a special little snowflake depending on what kind of drive is attached. The table in xp the driver runs 75 lines, which the authors know is bad because they prefix this table with:

/* THIS SHOULD BE READ OFF THE PACK, PER DRIVE */

 We'll return to 2.11BSD in a part 2.

4BSD

4BSD had a similar problem. They made it more palatable by creating a program, diskpart, which displayed the default disk partitions for a specific drive type, or allowed one to create partitions tables to cut and paste into a driver and/or config files. This helped, but was still compiled into the kernel rather than on the disk pack. 4.1BSD introduced, in 1981, a new wrinkle:

 * The bad sector information and replacement sectors
 * are conventionally only accessible through the
 * 'h' file system partition of the disk.  If that
 * partition is used for a file system, the user is
 * responsible for making sure that it does not overlap
 * the bad sector information or any replacement sectors.

Progress, but it was slow. Through at least 4.3BSD this was the case: every driver had their own table that was hand-tweaked for the drives that driver supported. This was OK, as far as it went, but as the industry shifted away from controller + disk combos where there were only a few choices to standard interfaces between the drive and host and most of the functionality in the drive, this became an untenable situation.

We'll explore how it got worse, before it got better in my second part. We'll see how different vendors innovated in this area ahead of a solution that appeared in 4.3BSD Tahoe and in AT&T System Vr3.0 around the same time.

[[ edited to correct typos ]]