Source Distribution

Developing a program as large as AutoCAD on personal computers, with most programmers working off-site, presents some interesting logistical problems—mainly, how do you distribute the source code which presently occupies over twenty megabytes. The source has outgrown every medium we have chosen, and at times we've even handed out paper bags with twenty or more floppy discs.

We finally settled on Iomega Bernoulli Boxes, with twenty megabytes per cartridge. Naturally, the source grew to fill them. This is a modest proposal to buy some time before the inevitable happened. It wasn't implemented.

Combining the files in a source distribution into a composite archive file can enormously speed up the process of copying source distribution media. Benchmarks, recommendations, and a moral are presented.

by Kelvin R. Throop
September 29th, 1987

On the morning of July 18th, Liberty, New Hampshire became the first town to vanish. Many residents of New Providence, over a wooded ridge from Liberty, were awakened at about 3:30 A.M. by a clap of thunder. Those who looked outside saw clear sky and a glow in the direction of Liberty. Volunteer firemen called friends in Liberty to ask what had happened, but none of the calls were answered. Most people went back to sleep.

By midday, all the world knew what had happened, but nobody knew how or why. The town of Liberty was gone. Gone to a meter below the ground. Gone right to the town limits, where some branches had fallen on undisturbed grass after their trees had vanished.

* * *

There has never been a truly satisfactory way of distributing full source releases of AutoCAD. The product has grown so rapidly that it rapidly outgrew each medium selected for distribution and became a large burden to copy and maintain.

Largely at my urging, Autodesk spent a large sum of money to equip all AutoCAD developers with Iomega Bernoulli 20 megabyte drives and has purchased an seemingly endless supply of cartridges for these drives. On the face of it, the Bernoulli is an ideal source distribution medium.

• It is fast. Average access time is comparable to a high performance Winchester hard disc drive.
• It supports a true DOS file system. Files can be extracted with normal DOS commands. No special archiving tools are required.
• It is a high-density medium. Each cartridge stores over 20 megabytes formatted. This is enough for an entire AutoCAD source and object distribution.

In practice, several disadvantages have become apparent.

• They don't work very well. Cartridges which verify one day may prove unreadable the next.
• Software support is shaky. Several bugs which can cause loss of all data on a cartridge have only recently been fixed.
• Image copy is untrustworthy. Binary image copy from one cartridge to another seems to frequently result in undetected data errors. There is no confidence that image copy correctly intercalates the bad track maps of the cartridges involved.
• The alternative, MS-DOS copy of entire directory trees, is painfully slow.

But hey, what do you want, it's from Utah, right?

Right.

* * *

The president appointed an investigating panel chaired by the secretary of defense and made up of the secretary of the interior, the chairman of the National Academy of Sciences, and the president of M.I.T. On the 20th, the group held a press conference in Manchester and announced that no probable cause had yet been found. The defense secretary said that hostile action had been ruled out “for the time being”, since no aircraft were in the area at the time, nor were any satellites tracked by NORAD overhead. “In any case”, the secretary concluded, “we possess no technology which could do this, and we don't believe our adversaries do either”.

* * *

Well, I got us into this, so I decided to spend some time seeing if I could get us out. The first thing I did is make some measurements of the AutoCAD X.0.60 (8/2/87) full distribution Bernoulli. I copied the directory tree from this cartridge to a Unix file system over NFS. I then made a tar file of the entire directory tree copied from the Bernoulli. The total size of the data on the Bernoulli was 19,786,240 bytes.

All of the measurements presented herein were made on an IBM PC/AT, 6 Mhz version, with an Iomega 2010 or 2020 removable cartridge disc system. In all of the following timings, I assume that the Bernoulli cartridges being written have been previously formatted. Formatting takes approximately 4 minutes per cartridge. Since all operations require a formatted cartridge, this is invariant under the options we're exploring and can be added to all the numbers presented below.

* * *

Over the next week ten more towns vanished: two in Massachusetts, another in New Hampshire, three in California (including one suburb of San Francisco), one in New Mexico, two in England, and one in the Netherlands. Data began to accumulate about the phenomenon. One of the California towns vanished during a Landsat pass; the multispectral camera recorded only the glow of ionized air molecules recombining. The nuclear test detectors on the remaining Vela satellite and the monitors on the Navstar constellation observed four light flashes coincident with disappearances. Nothing like the double flash of a nuclear detonation was seen, just slow airglow decay. No prompt radiation was detected at the time of the disappearances, nor was residual radiation found at the sites. Electromagnetic transients similar to a very large lightning strike were detected, and underground solar neutrino experiments reported six neutrino events near the time of the flashes, but gave only a 60% chance that this was correlated. Aviation Week reported that some at Los Alamos believed the flash spectrum similar to a free electron laser, but they had no idea how this could occur spontaneously.

* * *

First I measured the time to perform a file-by-file copy of all files on the distribution using Metaware's FIND. The file by file copy from one Bernoulli cartridge to another took a mind-numbing 63 minutes: one hour and 3 minutes!

The discrepancy between this and the time required to simply transfer the data from one cartridge to the next was elucidated by performing an image copy from one cartridge to another. The Iomega RCD utility copied the entire cartridge in a tad less than 5 minutes: more than twelve times faster.

* * *

As in time of war or natural disaster, the population surprised the politicians with its equanimity. Certainly there was uneasiness, and frustration grew as days passed without any explanation or plans to deal with the crisis, but no real signs of panic emerged. If scientists had no theories (as one physicist put it, “nothing even deserving of the term wild guess”), explanations nonetheless abounded. Television evangelists seized on the crisis as demonstrating God's wrath on sinful man (though none understood why Las Vegas was still around). The National Star interviewed 75 prophets and psychics who had predicted the disappearances, but was silent on which cities the “UFO Aliens” would kidnap next. Sinister rumors of Soviet secret weapons circulated, supported by the fact that no Eastern Bloc city had vanished.

* * *

Clearly, something odd is going on here. While one expects a hard-coded device-specific image copy utility to run faster than the operating system's copy facility, a factor of two is more than one typically gains. But twelve times faster? Hmmm….

Next I decided to try copying the 19.7 megabyte tar file I made from the distribution onto a Bernoulli across NFS. The entire copy operation took 6.4 minutes. Note that this was a DOS copy across an Ethernet link from a Unix file system, yet it was only 28% slower than Iomega's much-vaunted image copy facility. As all of those who have studied at the feet of the legendary masters of gonzo programming (especially those who did their studying in Cleveland) know, factors of ten percent may stem from sloppiness, but factors of ten invariably indicate idiocy. It was clear that somewhere deep within the sanctum sanctorum, the very nucleus of the operating system, there was some really major league evil.

* * *

By September 1st, over one hundred villages, towns, and cities in the United States, Western Europe, Latin America, Japan, and Australia had evaporated into the dead of night and the world was beginning to go truly crazy. Not one Soviet or Eastern European town had been affected; NATO moved to alert status “as a precautionary measure”. Still, no pattern emerged. Mostly small and medium sized towns and suburbs were vanishing. In the U.S. most were on the East and West coasts. Most of the mid-continent disappearances were university towns. No large cities nor unincorporated areas had yet gone, and people began to flow to the cities. Squatter camps appeared in state and national parks.

* * *

So, back into the Honda and down the hill to Duff's machine (which, unlike my humble configuration, has a gen-u-wine two-holer Bernoulli). I took the Bernoulli onto which I had copied the 19.7 megabyte tar file and tried copying it to an empty cartridge with a simple DOS COPY command. The entire copy completed in 5 minutes and 43 seconds.

At this point it's worth recapping the timings in these experiments. All timings in this table are in seconds.

What can we conclude? Clearly the enormous difference between the time required to copy the tar file and the time to reproduce the entire file structure on the target Bernoulli is simply the time that the operating system required to create all of the directories and files in the source distribution. Since the inefficiency is in the nucleus of the operating system itself, there is only one way to get around it.

* * *

For perhaps the very first time, a librarian came to the rescue of civilization. Todd Murphy was a researcher for the Library of Congress project to build a computer database on the vanishing towns in the hope of finding some common thread or pattern. But the brain is still the best computer when it comes to finding patterns. The answer came not from the database, but to Murphy's mind as he was entering data in the middle of the night.

* * *

Clearly, since the problem is in the operating system, the only way to overcome it is to bypass the operating system. Hence, we should prepare our source distributions as tar archives which can be copied more than ten times faster than fully elaborated MS-DOS directory structures. Fortunately, the Metaware FIND utility (licensed to all AutoCAD developers as part of the High C distribution) can write Unix-compatible tar files. Using Unix tar format allows Unix systems to process the distribution without format conversion. If the current directory contains a complete AutoCAD source distribution, you can prepare a Unix tar format Bernoulli on drive L with file name DIST.TAR with the command:

find *.* -utarc L:DIST.TAR -t

Having prepared a Bernoulli containing a tar distribution, you can extract the entire directory tree into the current directory with the command:

find -utarx L:DIST.TAR -cp .

If you have access to a Unix system, you can copy the tar file from the Bernoulli to Unix as a single binary file and extract the component files under Unix with the command:

tar xfv tarfile

where tarfile is the name of the file you've copied the entire distribution tar file into. Note that files are archived as they were originally stored; no end of line convention conversion is performed. Hence, even if you de-tar the archive on Unix, you will end up with source files in MS-DOS format.

* * *

That Murphy is forceful and persuasive as well as wise was evident when, after hurriedly checking his hypothesis against the list of cities and finding complete confirmation, he convinced the White House switchboard to awaken the vice president and the national security adviser and ended up at 4 A.M. declaiming to a small, bleary-eyed group in the Situation Room, “Congress has to act on federal overriding legislation today, and you must get the President back in town to sign it before we lose any more people. Get State to work contacting the Europeans right now—it's going to be night soon over there. And call the prime minister of New Zealand! Every town that vanished had declared itself a nuclear-free zone. And the nuclei are moving out.”

* * *

So, Horatio, the problem lies not in the stars nor in Roy, Utah, but rather in the nucleus of MS-DOS. Consequently, only one solution is possible. We must move to a completely nuclear-free software distribution format—one which can be replicated without a single call to the inefficient heart of MS-DOS. The tar file mechanism suggested herein provides such a solution and allows creation of AutoCAD full distribution media more than ten times faster than previous techniques without compromising data integrity.

I also investigated compression techniques. Our distribution almost fills a cartridge at present, and already excludes some items which should probably included in a full distribution (e.g., the Kelvinator). My experiments indicated that compression can help us fit far more data on a cartridge (and commensurately decrease the effective time to copy the original, uncompressed, data), but the convenience costs of compression are fairly high. I started with the original 19.7 megabyte composite tar file and used the Unix compress program. This reduced the file size to 8,751,305 bytes, saving over 55%, but compressing this file required almost 9 minutes of elapsed time on a Sun 3/260. Since the Unix compress program runs only on Unix, and Unix cannot directly read a Bernoulli, compressing the entire distribution in this manner means one must copy the entire 8.7 megabyte compressed tar file to Unix, then decompress it, then extract files from the archive. At the instant that the compression or decompression is complete, the entire mess occupies over 28.5 megabytes on the Unix system—a very severe free space constraint on any system. Decompressing the file takes about four minutes of elapsed time.

Since a large part of the problems with the Unix compress program stem from its inability to run on MS-DOS, I tried Kern's fsq program, which runs on both Unix and DOS. I was about to glibly say, “and it's still running”, but it just finished. I don't think we'll use fsq: it took 39 minutes of elapsed time to compress the composite tar file on the Sun 3/260 (27 minutes of CPU time), and it only reduced the file to 17,640,789 bytes, saving less than 11%.

Compression seems impractical when applied wholesale to the entire distribution, but can be useful for compressing smaller parts of the release. Duff has suggested that we tar the files directory-by-directory and compress at that level. This would drastically reduce the disc space required to decompress each part and only marginally increase the time needed to copy the cartridge.

Finally, I have been thinking about how to guard against undetected errors in these distributions, however copied. Neither Unix tar nor Metaware FIND in its native archive mode provide any form of file checksum. I am willing to write an external checksum utility to guarantee accurate distributions. If the following description seems a tool we will actually use, I will invest the day or so to write it.

To make a distribution, compress the directories of the distribution into one or more tar archives. After creating the archives on a trusted system and compressing them if you like, run the checksum program on each archive:

feathers -m tarfile

This program reads the named tarfile and checksums each block in the file with a highly reliably checksum. It creates a checksum file named tarfile.cks, and reversibly encrypts the first 128 bytes of the tarfile so that tar cannot unpack the file. All of the tar files and their corresponding .cks files are placed on a master Bernoulli and then copied for all recipients.

When a developer receives a Bernoulli, he verifies all of the files on it with the call:

feathers tarfile

This validates the file against the corresponding .cks file and, only if it is correct, decrypts the tar file so it may be de-archived. This absolutely guarantees that no developer can end up with corrupted data (unless an error sneaks past the checksum algorithm).