Recovering 2.11BSD, fighting the patches

Recovering 2.11BSD, fighting the patches

2.11BSD was released March 14, 1991 to celebrate the 30th anniversary of the PDP-11. It was released 15 months after 2.10.1BSD was released in January 1989.

2.11BSD was quite the ambitious release. The high points include:
  1. The kernel logger (/dev/klog)
  2. The  namei cache and argument encapsulation calling sequence
  3. readv(2)/writev(2) as system calls rather than emulation/compatibility routines
  4. Shadow password file implementation (the May 1989 4.3BSD update)
  5. A TMSCP (TK50/TU81) driver with standalone support (bootblock and standalone driver)
  6. Pronet and LH/DH IMP networking support
  7. The portable ascii archive file format (ar, ranlib)
  8. The Unibus Mapping Register (UMR) handling of the network was rewritten to avoid allocating excessive UMRs.
  9. The necessary mods to the IP portion of the networking were made to allow traceroute (which is present in 2.11BSD) to run.
  10. Long filenames in the file system
In addition to a completely new syscall setup. Item 10 required a full new install with restoring from a back up tape. Item #7 would be a thorn in my side.

However, following on the heels of 2.10.1BSD as quickly as it did, there's a number of changes that followed quickly after the release. So, by November of 1994 195 patches had been released for the tree. Well, there were more patches than that (patches 2 and 3 had several parts, and my work has uncovered a number of hidden patches along the way, but more about those later).

The Problem(s)

Well, if we have patch 195, and all 195 patches, what's the problem? Why can't you do a simple for loop and patch -R to get back to original? And for that matter, why were no copies of the original saved?

Turns out the root of both of these problems can be summarized as 'resource shortage'. Back in the day when this was released, 100MB disks were large. The release came on 2 mag tapes that held 40MB each. Saving a copy of these required a substantial amount of space. And it was more important to have the latest release, not the original release, for running the system. It was more efficient and better anyway.

In addition to small disk space, these small systems were connected via USENET or UUCP. These connections tended to be slow. Coupled with the small size of the storage on the PDP-11s running 2.11BSD, the patches weren't what we think of as modern patches. The patches started before the newer unified diff format was created. That format is much more efficient that the traditional context diffs. In addition, compress(1) was the only thing that could compress things, giving poor compression ratios. The UUCP transport of usenet messages also mean that the messages had to be relatively short. So, this mean that the 'patches' were really an upgrade process, that often included patches. But just as often, it included instructions like this from patch 4:
        Apply the patch "/tmp/dif" (multiple files updated by it) and
        install the new scripts ":splfix.mfps" and "splfix.movb+mfps".
which included a shar file that needed to be run through /bin/sh (or unshar, if you were lucky). You then needed to follow the instructions, which included patching. Patch 14 illustrates the problem, it includes the instructions that say to run /tmp/c created by the shar. It looks like this:
#! /bin/sh -v
cd /usr/src/usr.bin
rm lint/*
zcat PORT/lint.tar.Z | tar xf -
cd lint
rm :yyfix llib-*
cp -p /tmp/libs libs
So this is a very efficient way to remove files. Often the diffs were larger than the original files, so it was more efficient to remove and replace. But this presents two problems: what files were there before? And even in this case, what files were removed? These operations were not uncommon, and destroyed information. It's a bit like running the sausage mill backwards to rebuild the pig.

Another problem for this project is phantom patches in the first 80 patches. A number of changes appear only in the patches that come with the catch-up kit. These aren't a surprise, as a number of patches going backwards had unexpected slight line number anomalies in them. After patch 80, patch generation appears to be better managed, but at the time of this writing, the author hasn't tried to reapply all the patches to get back to the p195 tape from the reconstructed release tape. The author also has not audited the comp.bugs.2bsd mailing list between the March 1991 release and the November 1994 p195 tape. Given the surprises so far (tftp and tftpd were updated in May 1991, patches were posted in comp.bugs.2bsd, but no formal patch was released and this change does appear in the catch-up patches), additional discoveries like this cannot be ruled out.

The Path Forward

Taken at face value it's hopeless. There's no way to definitively reconstruct the lost information. But there's some glimmers of home. First, there weren't a lot of files deleted like this. lint, pcc, ld, ranlib and a few others were removed. However, what's missing can be rather critical. Next, we have both the prior release (2.10.1BSD). A good first approximation of what is there in the release will be what's in the last release. Many files aren't changed often in the 2BSD. So we have some data present there, even if some was destroyed.

There were also a number of patches. These can provide data about the missing files. There's all the patches in the 2.11BSD series, as well as a number of patches posted to comp.bugs.2bsd after 2.10.1BSD was released. We know from the release notes that these were included in the 2.11BSD release.

Next, we have 4.2BSD, 4.3BSD and even 4.4BSD and the SCCS files that go along with them. This means that we can see changes that were going on in the 4BSD series, and we know much code came from there in 2.11BSD, both before and after the release.

Next, we have dates. We are fortunate that all the files are dated in the tree. This means we have a way of testing if we've missed anything in our reconstruction. If we reconstruct something that's dated after the release of 2.11BSD, we have a very good reason to believe that we've missed something.

There was a catch-up kit that was produced around patch 80. It contained a number of commands to re-removed what should have been removed, as well patch everything up. This gives us a second way of checking: can we apply this kit to get to patch 80? Does it work? And if we replay the individual patches we should get the same thing. And it should be the same as we got unapplying the patches back from 195. A word of caution: as with all other things around this project, we must always be open to the possibility of a mistake in the catch-up kit. There are at least a few files that it tries to remove that aren't necessarily there.

Finally, we know that the system was released as binaries. Which means that the system built. So we can test the reconstruction by compiling it. We should be able to build the final system. But we need to do that with the final system, so some way must be found to bootstrap it for this test. I'll talk more about that in another blog.

The Slog Backward

The slog backwards proceeded with fits and starts. For the first 20 or so patches (that is patch 177-195), it was fairly straight forward. I was able to use them to develop the framework to proceed. It wasn't until I hit the a.out binary format changes that I had problems (the first, looking back, of these is 176).

The Framework

I settled on a fairly simple framework going backwards. There are three types of patches in the archive. First, there are the pure patches. These have a simple patch set to apply, and maybe some verbal description of commands to run. Often, these commands were just the minimal amount to rebuild so you didn't have to suffer through a day's long compile. Sometimes, they included sneaky instructions. The patches 89-99 all contain the following text:
The /GENALLSYS script is obsolete and has been removed
so in addition to applying the patches, the script needed to be removed. To complicate things, some patches were generated from the root directory, while others were generated in the leaf node. To this end when the script detects a simple patch it tries to locate a hints/patch#.setup script. If one is found, then that script is sourced. Setup scripts are expected to be idempotent so we can reuse them for the forward trip. They all do a cd to where the patch was generated from. After the setup, if any, the mk211bsd script will apply the patch.

However, when there's other things to do, that won't work. So, there's a second way to assist. If there's a hints/patch#.unpatch, then that will be run and it is responsible for moving the patch backwards. About 20 patches need this assistance. For example, patch 118 replaces ucb/Mail with a port from 4.3. So, I need to reconstruct what was there. In this case, I copy the ucb/Mail files from 2.10.1 and then check for patches in comp.bugs.2bsd (there aren't any) and in the patch stream (patch 10 tweaks it). So, I have to reapply all those patches in the unpatch script.

The second type of file is the shar file. Here, one has to run the shar file through /bin/sh (or unshar) and use the extracted files to do something. Often times there's a short script to run and a patch to apply, but other times it's more complicated. In these cases, you must provide an hints/patch#.unshar file. This file takes care of unsharing things, and running whatever you need to do to unapply it. This varies a lot. In some cases, you extract a patch (or set of patches) and reverse apply them. In other cases, you need to remove files. In still others you need to snag them from 2.10.1 and touch them up (like we did for ucb/Mail).

The final type is a tar ball. These files are treated like patches, with the usual unpatch protocol. However, the unpatch program script has to know how the tar file encoded its patches.

Interesting Patches

There's 195 patches (and a few sub-patches). Describing all of them would be quite tedious. Only about 80 hints are needed (and a few additional files for reconstructed fixups). I'll describe some of the more interesting ones briefly here. Most of the interesting ones are in the last 50 or so. And by interesting, I mean ones that destroyed information such that it had to be reconstructed or that otherwise affected the reconstruction.

Patch 185 replaces m4, so we have to snag the one from 2.10.1BSD to replace it, as well as unapply a patch in the shar file. Patch 115 did a fixup on the Makefile, so we have to reapply it so that patch 115 will unapply correctly.

Patch 184 fixes the makefiles to use pipelines instead of temporary files now that the assembler can cope with pipelines. At the same time, it removed a few obsolete compatibility system calls that need to be added back from 2.10.1BSD. Adding them back messes up the directory times, which make depends on, so workarounds have to be deployed in build2.sh, the bootstrap script (make in 2.11BSD assumes times in the future mean the directory is up to date and doesn't need to be rebuilt, while newer makes will ignore that time and descend into the directory always).

Patch 180 updates symcompact.c and strcompact.c by replacing them entirely. These files weren't in 2.10.1BSD, but came in with patch 172, so needed to be recovered from there. It also adds symdump.c which needs to be removed. There's no data loss here, but it illustrates the need to look at all the patches to see what might need to be recovered (and what doesn't).

Patch 178 removes an unused header, and fixes up another one. The headers were resynchronized in patch 175, so a small fixup is needed here. Need to investigate this, and other 'fixup' patches. One unknown is whether 2.11BSD shipped with the unsynchronized /usr/include and /usr/src/include or not. The reconstruction tries to get the right ones in each place, but uses the /usr/include ones as the ones in /usr/src/include when we can't otherwise reconstruct.

Patches 158-176 remove the 8 character limit to symbol names in programs. These are quite disruptive, but for the most part just large patches. ranlib(1) was grabbed from 2.10.1 and patched to cope with the new archive format to undo these patches. ld(1) needed similar work (and once I started rebuilding things, I had to fix so it would compile). It also needed some fixes from comp.bugs.2bsd. Initially, I'd kept them separate, but I eventually needed to merge them together. ranlib(1) and ld(1) represent the largest effort in retro-programming to reconstruct (code was cut and pasted from other programs that survived and minimally changed to be functionally correct).

Patches 151 and 152 rework the assembler. A number of patches to as were posted to comp.bugs.2bsd that needed to be applied to 2.10.1's assembler to make things work out. A couple of minor tweaks were needed after all these changes were applied, though, to make the patches work out.

Patch 142 unapplied the patch, but then needs to unapply changes to all the kernel config files. This a recurring issue for the generated files, so some fancy scripting is needed to apply them to all the kernel config directories. Patches 124, 121, 93 (which has to remove some directories), 84, 83, 72, 42, 36, 4, and 2. There's a number of issues with patching the kernel, not least was that overlay structures were often hacked on the fly and preserving them is hard. The restoration has only tried to get GENERIC and possibly KAZOO kernel configs correct, and the others it has largely ignored. I'll do a full blog on all the issues to detail what is or isn't recovered.

Patch 132 brings in named, so it needed to be recovered from 2.10.1, plus patches from patch 106.

Patch 123 is actually missing a part. It updates the documentation for how to install the system. This means we need to apply some kind if fixup. But all we know for sure is the SCCS id changed, so that's all we fix up. If I find more data to support other changes, I'll update to include that, but so far nothing has surfaced.

Patch 118 replaces ucb/Mail with the one from 4.3BSD. Revert to 2.10.1BSD's version and apply a patch from patch 10. There's no publicly posted patches to 2.10.1BSD for ucb/Mail.

Patch 80 is the catch-up kit patch. A lot of files were added from USENET. Undoing it is straight forward, making it go forward will tough, but we have the files at least. This is both a blessing and a curse to the project. On the one hand, we have a second way of cross checking things. On the other, the cross checks reveal many problems, including updated kermit being missing entirely (though, to be fair, /usr/src/new and /usr/src/local weren't considered part of the system until patch 195, so prior to that patches to this part of the tree were irregular).

Patch 40 is an announcement of corrupt files in the original release in /usr/games. I've chosen to restore them to what was intended for the original tape.

Patch 17 massively reworked pcc. It's not quite right in the reconstruction yet, however, since the 'redo catch-up kit' test fails to delete some expected files, what shipped in 2.11BSD isn't quite right. It may never be right, and that may not matter since it didn't work anyway.

Patch 14 fixes lint. It was totally broken in 2.11 (but worked in 2.10.1). Undoing it may also be incorrect for a similar reason as patch 17. Since neither one of these worked, it may be quite hard to know what 2.11 shipped with. A case could be made, though, that it doesn't matter...

Patch 2 removed tmscpboot.s. The rest of the patch undoes easily, but tmscpboot.s was new in 2.11BSD. We know it is derived from tkboot.s which comes from Ultrix-11, but I've not yet been able to tweak it to work yet...

Current Status

At this point, I've reconstructed a possible release tape. A series of them, actually. All of them fail the tests set forth above (though in fewer and fewer ways each iteration). I'm able to use the different tests to suggest fixes. I've recovered 5 lost patches (which I write about elsewhere). There's at least 5 more I believe based on the attempts to apply the catch-up kit. I discovered the first 5 based entirely on bad dates. The current reconstruction is decent (maybe 30-40 files still aren't quiet right, and a similar number are reconstructions that work, but it's impossible to know if they are missing bug fixes). The tmscpboot stuff is still missing, and there's a number of minor fixups that need to be reconciled with the known missing patches. All very careful, detailed work, so it may be some time to work through them.


Bootstrapping 2.11BSD (no patches) from 2.11BSD pl 195

Bootstrapping 2.11BSD (original)

I've had the sources for what I think is the original 2.11BSD for some time now. However, how do I know these sources are good? That's a very good question. I have a series of tests that I'm doing to verify that the sources are consistent with what we know, or have some kind of known deviation / reconstruction when not. They had passed only the first of my many tests (they were consistent with the patches themselves, but nothing else). It was time to see if I could build what I'd made.
Click to close image, click and drag to move. Use arrow keys for next and previous.

One thing we know for sure: The 2.11BSD release happened. This means that sources for the release must be buildable, in some way. The 2.11 BSD release notes don't mention any reproducibility issues. Presumably the documented way will work. However patches 106-111 fix dozens of build issues that affected reproducibility of the build. In addition, one should be able to build twice in a row and get identical results, modulo a few binaries that encode dates and such. Experience has shown that many programs in /usr/local or /usr/new are the worst offenders. I've made the decision that if make install doesn't install it from the top level, then it won't be in the release I recreate. Though I also made the decision that building some man pages by hand was also OK to make that happen...

Part of building it twice is building it at all. In patches 158-178, the binary format of the .o files changes to accommodate longer symbol names. As a result, the binaries in the 195 image don't produce binaries that work on the unpatched release (well, the binaries themselves do, but the .o's are wrong, as are all programs that read symbols). In addition, there's issues just building everything on the 195 image: as, nm, and ld don't even build, and without those, you won't get far. In fact, the 195 assembler won't even assemble the assembler I've recreated. Since the straight forward way won't work, I thought I'd document what does.

For a background on the toolchains, please see an earlier blog post. It goes over all the basics of toolchains, which I assume people are familiar with.

Bootstrapping as

So, we have to bootstrap the assembler. The 2.11pl195 assembler won't assemble it properly. The v7 assembler will. However, building it on a v7 system isn't the solution: the resulting binaries won't run on the 2.11BSD system. The system call format changed with 2.11BSD, so even the 2.10BSD binaries won't run. One advantage, though, of either the 2.11BSD or the V7 assembler is that it will run under apout.

Apout is a tool that the unix-1972 crowd over at tuhs created to run PDP-11 binaries on modern hardware. It doesn't implement all the system calls. The C compiler which forks other things won't run, for example. However, the assembler will. And the loader. And cpp. Why's the last one important? Well, if we have cpp, then we can assemble the 2.11BSD system call glue in libc.

The assembler is written in fairly low-level code. It calls half a dozen system calls, so this is easy, right? For the system calls, one needed only cpp and the assembler to create them. However, there's one other function it calls: signal. Signal used to be a system call when as was written. In 2BSD, Berkeley reworked how signals worked, so they created a compatibility shim written in C for the old way. That presents a problem... Getting the C compiler going was a lot of effort because it was so many passes and I'd have to string them all together by hand. My solution was to look at the sources and notice that it was just called to register an atexit function to cleanup tmp files when SIGINT was received. This is important for real, old-school PDP-11 hardware that measured the speed in hundreds of thousands of operations a second (or worse!). It would mean that ^C would clean up the temp files. But for bootstrapping? It's not really needed. So I created a .s file that was just '_signal: rts pc', which does nothing but satisfy linkage...

To make things simple, I used ld's partial link functionality to link all the .o's together to create a bootstrap.o. This took the place of libc. So I was able to bootstrap the assembler using the V7 as and ld binaries as well as the 2.11BSD cpp binary to pre-process the 2.11 sources. I did this twice, once for each pass of the assembler. I added the code to the script that I use to create the 2.11BSD (original) tree. This script took care of copying the results into the 2.11BSD tree. It was able to assemble itself, so on to the next step.

Now that I had the assembler bootstrapped, I could move on to the next things. Here we shift from the FreeBSD host that was creating the 2.11BSD (original) tree to a 2.11BSD pl 195 simh image that had a copy of this tree (which I'll call ur2.11 below to distinguish it from 2.11BSD pl 195 which I'll just call '195 below) mounted on /scratch. FYI: the 'ur' prefix means 'original' and it's often used in linguistics to describe the original version of something, now lost but reconstructed.

Bootstrapping ranlib (and to get there ld and nm)

So, one of the things you need is something called ranlib. It reads through a library and collects a table of all the symbols in that library and puts it in the first member of that archive. ld then uses that to pull in what it needs from the library. This eliminates the need to worry about cycles and other strange things. Normally, without a table of contents, ld will just make a single pass through the .a file, pulling in everything that's needed. When there's no cycles in the dependencies, this works great when you create the library with 'lorder *.o | tsort' so that it can be pulled in with one pass. If there are cycles, the library has to be pulled in multiple times to resolve them all.

libc, of course, has cycles. So, how do we fix that? Well, we need to build ranlib (since the newer ranlib uses a different table of contents format, because why would it be easy). To make matters worse, 2.11BSD changed the archive format to the portable archive format from the old PDP-11 format.

So, to build ranlib, we need libc and ld. For libc, we need nm because the lorder shell script uses it and I didn't want to hack the build process. Let's focus on the first two of those. In an ideal world, we could just build them on the '195 image. For once in this project, that's entirely possible, but with a caveat. The include files have changed, so I needed to build this on the 195 system, but using the ur2.11 includes (not the '195 ones, they had been rototilled in the 158-178 patch sequence for the new binary format). I needed to do this in the '195 system because it could create new binaries (but chrooted to the ur2.11 system could not). I was able to do this simply enough:
cd /scratch/usr/src/bin
cc -o ld -O -i ld.c -I/scratch/usr/include
cc -o nm -O -i nm.c -I/scratch/usr/include
 Now I had everything I needed to bootstrap ranlib... almost....

Drop into the chroot

As readers of my blog know, I recently did some search into chroot. The reason was this effort. I'd recalled reading that it was added into 4.2BSD, etc. So I went looking and found an interesting story (that I've already told).

Now you know why I was looking: the next step is to chroot into /scratch. Once we're there, we need to do a few things. First, let's copy things over:
chroot /scratch
cd usr/src/bin/as
cp as /bin
cp as2 /lib
rm as as2
cd ..
cp nm ld /bin
rm nm ld
cp /bin/true /usr/bin/ranlib
OK. That gives us a working assembler, loader and nm. What about cc? Don't we need to rebuild it? Turns out, no. It's already working, creating perfectly fine assembler. Since we just swapped out the assembler, we're good: it produces the new format. And the loader, it can combine them into binaries that will run (we're quite fortunate that the '195 loader can create binaries that work on ur2.11). What about ar(1)? Well, we don't have to bootstrap that either (at least not yet) since the format is the same, even if the program was imported from 4.3BSD in the 158-178 patch series. Finally, we avoid an extra step later by copying /bin/true to ranlib. This means the ranlib in the ur2.11 tree right now (which came from '195) won't create an entry in libc.a we have to delete later.

Building libc.a and crt0.o

So, next up, we need to rebuild libc and crt0.o. cc uses these to create working binaries, and we need cc to rebuild ranlib. Thankfully, it's relatively straight forward to rebuild libc and install it:
cd /usr/src/lib/libc
make clean
# Hack around make sometimes failing to descend on some runs
(cd pdp/compat-4.1; make)
(cd pdp; make)
make install
make clean
so now we've replaced the '195 libc.a with it's newer format binaries with ur2.11 libc.a with the proper for this version format. When building, you may have noticed tsort reported a cycle in the dependency graph. It's safe to ignore that for now, we'll work around it in a minute. Depending on dates of directories, you may need to build deep directories by hand because directories in the future aren't considered out of date so aren't rebuilt...

Building ranlib (for real)

Now we can build ranlib, and use it to add a table of contents to libc.a. We'll need to specify libc.a twice in order for it to resolve the circular dependency. When linking libraries w/o the ranlib table of contents, ld only makes one pass through the library. So, if we list it twice, it will get the rest of the dependencies when it makes a second pass through the library. Since all the other symbols are resolved, we don't wind up with two copies of anything.
cd /usr/src/usr.bin
cc -o ranlib -O -i ranlib.c -lc
cp ranlib /usr/bin
ranlib /lib/libc.a
So, now we have a sane libc.a and ranlib.

Finishing up the Bootstrapping

OK. We could go on from here and make a lot of progress. Along the way, though, we'll discover that there's some programs whose Makefile assumes certain things about ar, or want to exec the strip program, etc. So we'll build those now and install them to make for smoother sailing later. All the other dependencies are properly handled.
cd /usr/src/bin
make ar strip
cp ar strip /bin
And we're not quite done. install groks the binary format, so it has to be bootstrapped now before we use install -s as part of many make install targets:
cd /usr/src/usr.bin
make xinstall
cp xinstall /usr/bin/install 

Doing the Build

At this point, the simple way to build is to do the following
cd /usr/src
make clean
make all
make install
make clean
make all
make install
which builds everything twice. This is far from optimal, but will work. The things that fail the first time around, due to missing libraries and such, will succeed the second time through.

One could look in the sources and find there's another process, 'make build' which installs the includes (well, that's commented out, and that caused version skew between /usr/src/include and /usr/include), builds and installs libc, builds and installs the C compiler, rebuilds libc, rebuilds and reinstalls the C compiler, then builds and installs usr.lib before building and installing 'bin usr.bin etc ucb new games' directories. This works mostly OK. However, in our situation, this leaves a big hole: there's programs in /usr/src/usr.lib that need other libraries in /usr/src/usr.lib, so they fail to build in the make build scenario. Plus, I've had it fail in the second build of libc for reasons unknown (it just fails to descend into the pdp directory, which it had no trouble doing the first time).

So if you go and look at the bootstrap program, you'll see the following crazy dance that it does. Of course, it knows it's already built libc once (and it lacks the above workaround for libc, but the actual automation has it):
cd /usr/src
make clean
cd lib
for i in ccom cpp c2 libc ccom cpp c2; do
    (cd $i; make all install)
cd ../usr.lib
for i in lib[0-9A-Za-z]*; do
    (cd $i; make all install; make clean)
ln /usr/lib/libom.a /usr/lib/libm.a
cd ..
make all
make install
make clean
which is similar enough to 'make build' but avoids the holes in it and avoids having to build absolutely everything twice (though it does build libc and the C compiler 3 times total, which likely is overkill). The funky pattern for building libraries is because there's a lib.b that's installed (it's just a text file with what appears to be B code in it). The link for libm afterwards is to mimic what the make install target does in usr.lib since we're not using it and libom.a is used for libm.a on 2.11BSD. Since we remove all .a's in creating the root, we have to recreate this here.

In the end, we're left with a complete user land that we can then move to the next phase with. Once we have a kernel, we can rebuild the release tapes which I'll leave as a topic for another day. With the boot block rework, the disk label changes and the changing needs of the 2.11BSD community, rebuilding them for ur2.11 is somewhat different than 2.11BSD patch 469.

As a workaround for some build issues, I also needed to build a number of man pages so the program associated with them would be properly installed... Suffice to say I rebuilt all the man pages in the end as part of the bootstrap script, but they aren't strictly required to run the system.

Building the Kernel

Normally, one would re config the kernel and build it. However, in 2.11BSD as released, there were a number of hacks made to the kernel Makefile to get it to fit into memory. Normally, one would hack these things in /sys/conf/Make.sunix so configuring GENERIC wouldn't destroy any carefully worked out overlay, but that wasn't done initially. So, we have to be careful how we build.

Also, in the initial version, the root partition was hard coded into the kernel. There was a script call /GENALLSYS that would create all versions of the: rpunix, raunix, xpunix, hkunix, etc.When installing, one needs to know the proper one to use. So, putting that all together, we can just do this:

cd /usr/src/sys/GENERIC
make && make install && (cd / ; cp unix genunix; sh -x /GENALLSYS)

which builds all possible bootable kernels... 

Building all the Standalone Programs

When we built everything, a few things still weren't build: the boot loader, the autoconfig and boot program (which is different than the boot loader). One just needs to build in /sys/mdec, /sys/autoconfig and /sys/pdpstand:
cd /sys/mdec
make && make install && make clean
cd /sys/autoconfig
make && make install && make clean
cd /sys/pdpstand
make && make install && make clean
Once one has mdec installed, one needs to dd the blocks onto the disk to make it bootable. When I was bootstrapping this disk, I did it with the intention of making a bootable system. I had to add /usr to /etc/fstab too, but all the things I did might fill another blog entry...


Building entire systems is messy, and has always been messy. Unless you skipped to the conclusion, I suspect that you've already formed this opinion about the 2.11BSD build process.  I've managed to enshrine everything above into build.sh and build2.sh to make things automated. Using this technique I've managed to build a ur2.11BSD boot disk, created boot tapes and installed from those tapes. Automation was key, though, to recording all the right steps in the right order.


Missing 2.11BSD patches

2.11BSD Missing Patches

While looking into some date anomalies in the final image (since I'd like to get the dates right) I discovered a number of source directories had dates slightly newer than the date in the announcement. This lead me to discover some missing patches in a couple of different places.

The Anomaly

I've automated the system generation, tape generation and installing from tapes to allow me to make small tweaks and get end to end testing. As part of this, after the system is installed, I'll do a test boot, similar to the following, as if I'd installed the system on April 10th, 1991 and booted it on April 15th. The boot looks something like this:
sim> boot rq

boot: 73Boot
: ra(0,0)unix

2.11 BSD UNIX #1: Fri Mar 15 15:48:55 PST 1991

phys mem  = 4186112
avail mem = 4008640
user mem  = 307200

Apr 10 13:50:01 init: configure system
ra 0 csr 172150 vector 154 attached
rl 0 csr 174400 vector 160 attached
tms 0 csr 174500 vector 260 attached
ts 0 csr 172520 vector 224 attached
xp 0 csr 176700 vector 254 attached
erase, kill ^U, intr ^C
# date 9104151234
date: can't write wtmp file.
Mon Apr 15 12:34:00 PDT 1991
# Fast boot ... skipping disk checks
/dev/ra0c on /usr: Device busy
checking quotas: done.
Assuming non-networking system ...
preserving editor files
clearing /tmp
standard daemons: update cron accounting.
starting lpd
starting local daemons:.
Mon Apr 15 12:34:01 PDT 1991

2.10 BSD UNIX (my.domain.name) (console)

I set the date in single user then bring it up to multiuser. In one of my tests, I found the following:
-rw-r--r--  1 imp  imp   9777 Aug 31  1991 alloc.c
-rw-r--r--  1 imp  imp   4817 Aug 31  1991 alloc11.c
-rw-r--r--  1 imp  imp  12474 Aug 31  1991 doprnt.c
-rw-r--r--  1 imp  imp   3299 Feb 23  1987 doprnt11.s
-rw-r--r--  1 imp  imp    831 Aug 31  1991 printf.c
-rw-r--r--  1 imp  imp  20446 Aug 31  1991 sh.c
-rw-r--r--  1 imp  imp   1771 Aug 31  1991 sh.char.c
which I thought was quite strange. There shouldn't be any files dated newer than the release in the tree. I know all files patched don't get the time set right, so I exclude those from my search (I plan on fixing that bug later). The above files (and others, it's just a short list) shouldn't be there. So I started looking...

The Diffs

Running diffs against 2.10.1 I discovered that the csh files were almost all the same. However, a typical diff looked like:

diff -ur root-2.10.1/usr/src/bin/csh/alloc.c root-2.11/usr/src/bin/csh/alloc.c
--- root-2.10.1/usr/src/bin/csh/alloc.c 1987-02-08 15:27:23.000000000 -0700
+++ root-2.11/usr/src/bin/csh/alloc.c   1991-08-31 01:03:00.000000000 -0600
@@ -4,10 +4,10 @@
  * specifies the terms and conditions for redistribution.

-#ifndef lint
+#if    !defined(lint) && defined(DOSCCS)
 /* From "@(#)malloc.c  5.5 (Berkeley) 2/25/86"; */
 static char *sccsid = "@(#)alloc.c     5.3 (Berkeley) 3/29/86";
-#endif not lint

  * malloc.c (Caltech) 2/21/82

which removed the SCCS IDs from the binary to save size. Other changes included introducing overlays for the first time. This indicated size issue. Let's take a look at what else was going on around the 31 Aug 91 in the patch stream. Looking, we find that this is just after patch 18 (which fixed a long vs int bug in test) as well as patch 17, which updated pcc. This sounds like a size hack by someone that had just updated the compiler, or was testing with pcc (the normal system compiler wasn't pcc, but the earlier Thompson compiler). Another of the changes also fixes an issue with character handling, which other patches have done to reduce the size of binaries that got too big.

So, in context, this change makes perfect sense. The only trouble is that it wasn't posted to comp.bugs.2bsd, nor did it make it into Steven Schultz's patch repo. And csh isn't the only troublesome one. There's issues in rn, and games/warp.

The Catch Up Patch

There was a catchup kit that was issued officially as Patch 80 (though it omitted patch 79).  Looking in that patch kit we find this change! So it's in one that was intended. So what to do?  And it turns out there's 5 such patches (but only 4 of them made it into the patch kit... I'll talk about #5 in a minute).

I've decided to look at the dates of each of these patches and pretend they happened just after the patch whose date is closest). I've updated my mk211bsd script to extract these from the catch up patch.

Oh, and there were a number of new programs added in the catchup patch as well. These must be deleted too, but I'd already noticed that and deleted them.

tftp changes

So, on May 4th, 1991 a patch to dd.c was posted to comp.bugs.2bsd. It's also included in the official archive as patch 1. The release announcement was dated March 14th, 1991. But there's tftp files dated May 15th, 1991. What's up with those? Turns out, this is another missed patch (but one that's assumed to be in place in the catch-up patch because it's not in there. Well, it's partially in the patches, partially in the scripts. It's an update of tftp and tftpd to a new version. It was posted to comp.bugs.2bsd on May 15th, 1991, but isn't in the official list of patches. So not only do we have to dig it out of the catch-up patches (from two different files), we also have to restore the old man pages from 2.10.1BSD, but in a different place, so this patch will be a patch + rm (which going backwards is patch + cp)

csh changes

As discussed above, these are various hacks to get the size of csh down.

warp changes

The changes here are around the config script used to generate files for the build. The changes use full path names, and cope with the new shadow password format changes.

pcc changes

[[ edit -- these were poorly documented: they are in patch 17, but not called out specifically to apply ]]

rn changes

As part of the catchup, there's a number of minor patches to rn that were included in the catch up, but weren't formally published or occupy a number of their own.

My Work

So, how does this affect me? Well, it means that I need to understand the catch up patch a lot better. I had hoped to use it later as a cross-check against my work. I didn't anticipate that I'd be using it "sooner" as to get missing bits I'd found using other techniques. I've had to update mk211bsd to extract the bits, as well as creating a couple of hints files to help me undo the changes.

And when the time comes to reply all the patches, I'll need to take these anomalies into account as well. But that's a problem for future me.

I also have to complete the audit of the weird file dates. There's 63 of them right now, 29 in /usr/src still. Some of clearly old man pages that I can remove. Some are the result of running 'configure' or similar script (rn has 7 of these). Some are config files that change over time (like for the root name server). Some may be just left-over detritus of a running system. I need to see which ones fall into which categories and update accordingly. This may dovetail back into needing to bring them back to make sure I can march back to pl195 and get the same system. Since I started with ~1500 such anomalies, I think being down to 63 is quite good. And there's others elsewhere in the system... 

Current status

As you might guess, if I'm finding things like this, that means I'm getting closer. I've shared a lot of this on my @bsdimp twitter account, but now is a good time for a wrap up. Here's what's done currently:
  1. Script to undo all the patches, including helper 'hints' scripts, where possible from existing artifacts.
  2. Miss patches reconstructed and integrated into the build
  3. Automated installing 2.11BSDpl195 image
  4. Automated bootstrapping back from 195 -> 0. There's a number of interesting problems here that I'll blog about soon
  5. Building the 2.11BSD pl 0 tapes automatically
  6. Test installing the pl  0 system from the pl 0 tapes.
The missing bits include
  1. Getting the dates right (or failing that plausible) for the patched files
  2. Finishing the date audit and tracking all anomalies to ground.
  3. Cleaning up my helper scripts off the image
  4. Creating a github repo with all the patches in it
  5. Reproducing the build on a second system
  6. Getting the ownership right for some files (eg using the mtree hack to get the ownership and permissions right, generating it from the pl195 tape/image, etc)
  7. Getting dates right on /, right now restor(8) doesn't restore the date in one at a time mode, so these are all wrong.
  8. Fixing tmscp boot. It's broken. The tmscpboot.s, ported from tkboot.s, only existed for a short period of time and has been lost. My reconstruction has issues (it won't boot), and I've not delved into why.
  9. Creating automation to ensure that the 'catch up' kit will apply cleanly.
And of course, I need to figure out the best way to publish the artifacts when I think I'm done.


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
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'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.


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.


First screen shot of 2.11BSD as released

My automation produced this today...

which is the first time something close to a 2.11BSD, unmodified, has booted in 30 years... Alas, it's only in SIMH, but still, I've reached 'as released' or as close as I can reconstruct.

I've uploaded all the tools to github if you'd like to check it out. I've not yet uploaded images, since I want to cleanup a blog I've been keeping about this and post them with that (also gives me a chance to tweak a few things (like give a real domain-name) if I wanted to do so...

A great note to end the week on...