File Systems used to be Flat

Today we take hierarchical file systems for granted.  Path names follow lines of directories to the final file that is being specified.  Hierarchical path names are the basis for URLs.  Both fellows in the Apple "Hi, I'm a Mac", "And I'm a PC" ads have Hierarchical file names.  Even the OSes in hand held PDA's have them.  But file systems used to be flat.  In this post I describe one such file system, the file system on the OS on which I learned to program, Control Data Corporation's ITOS for the Cyber 18/20.

My first programs were written in FORTRAN (I'm not shouting--the language is spelled in all upper case) and compiled and ran on a Control Data Corporation Cyber 18/20.  The Little Cyber, as it was lovingly called, was a small 16-bit, word addressable minicomputer sold by the same folks that brought you the CDC 6600 super computer.  Each user on the Little Cyber had a single level directory.  All  a user's files were in one big directory.  And you could have as many characters in a file name as you wanted--as long as you didn't want more than eight.  And, like my college professor's policy on term papers, there were no extensions.

The time sharing operating system on the Little Cyber was call ITOS.  One day a very nice Customer Engineer arrived from La Jolla carrying a 50 MB disk containing the entire source code to ITOS.  Asked if we would like to join him for lunch, one of our number, a person who shall remain nameless, declined with some excuse about having to do some backups.  The backup that was made after the CE left was that of the ITOS source code disk.  (I wish we still had that backup.  As far as I can tell ITOS has now completely disappeared, as is the case with too much of the software from yesteryear.)  On those spinning, rusty colored disks were all the secrets of the operating system we were running, including the source code to the file system.  We had many enjoyable hours reading the stuff on that disk.

First thing that surprised us was that ITOS was written partly in FORTRAN and partly in assembly code.  We all assumed all operating systems were written in assembly language.  It wasn't until later that we learned about C and Unix.  Some of the ITOS source dated back into the mid 1960's when the system was called MSOS and ran on the Control Data 1700.  The 1700 was made from the same cord wood style logic modules that the larger CDC mainframes were constructed from.  A module is shown below.  The support for the file system dated back to this earlier machine.  

Common to all file systems, even from the very first days of disk systems, is the need to keep metadata.  Metadata is the data needed by the system to keep track of the user's data.  It's the data about the data.  For each file the system has to keep track of where on the disk the contents of the file is located, the name of the file, and other data, like the creation date, permissions, owner of the file, and so on.  Today we sometimes call the metadata for a single file an inode, named such by Ken Thompson when he invented the Unix file system in the late 1960's.  IBM called metadata for a file a "Dataset Control Block" or DCB.  Another old name for this collection of information was "File Control Block" or FCB.

On an ITOS volume, there were a fixed number of FCBs, 4096 of them, if I remember correctly.  They included everything you needed to find the data, except the file's name.  The FCB was located by its index into the FCB table.  This was very similar to what Ken did with Unix.  The original Unix file systems has a fixed number of inodes located at the beginning of the volume.  Directory entries in Unix contain the index into the inode associated with that file.  But that was not how the folks who worked at the La Jolla Control Data facility did it.

Files were located using what was called a complete file name, made of up an eight character user-id and the eight character file name the user saw.  Since the machine was only word addressable, that is, a sixteen bit word was the smallest addressable unit in memory, each complete name was eight words long.  Areas on the ITOS volume were divided into buckets of name index entries.  Each name index entry was nine words long, consisting of the complete name plus a word containing the FCB number.  To open a file, the complete name was hashed into an bucket number and that bucket was searched for the entry for that matched the file name.  When there was a match, you had your FCB number and could access the file.  So in reality the file system was really, really flat.  All the files for all the users were in one big directory!  Only the trick with using the user id as part of the complete name gave the illusion of a user directory.  To list the files in your directory, the system read every name in the directory and only showed you the ones that had your user-id name.

All this was so close to being really nice yet missed the mark.  The designers had already divided the names from the metadata.  All that was needed to make the file system hierarchical was to define a file type of "directory" that could have contained file names and FCB numbers, the same entries that were in the buckets.  Each directory in a path could have just been walked linearly until you found the name you were looking for.  In fact, this would have been less code, no need for hashing the names into a bunch of buckets.  That's basically the design Ken Thompson came up with for Unix.  His genius lies in seeing ways to build more functionality while using less code.

But as any designer or artist knows--simple is hard.