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

    root@wlonex.imsd.contel.com:/usr/src/sys/GENERIC

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)

login:

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

+#endif

 /*

  * 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

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.

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