BSD Fast File System

Until the creation of the Berkeley BSD Fast File System for BSD 4.1, all prior Unixes had used basically the file system designed for the early PDP-11 versions of Unix. While very simple (in on-disk structure, and thus implementation), it had some performance, functionality and robustness issues. The FFS fixed these, so successfully that the FFS and its descendants are still the file system of most Unix descendants today.

Issues

The performance issue were the most critical, but there were lesser functionality and robustness issue as well. The FFS fixed most of these issues (although without duplication of most meta-data, and all data, it was still susceptible to hardware failures such as head crashes).

Performance

The original Unix file system was too simple to be able to get good performance out of the disks of the era. One factor was the small block size (which was to some extent ameliorated in systems prior to the FFS by using larger block sizes); the other was the extreme non-locality of data placement, which was an endemic (albeit un-intended) feature of the earlier system.

Once the system had been running for a while, free blocks were scattered fairly randomly across the disk, and the blocks comprising a new file were thus widely scattered; reading the file resulted in a great deal of head motion (seeks). There was no cure for this state of affairs, other than dumping and re-building the disk.

Functionality

Although the original file system did include so-called hard links, those were non-optimal in a lot of ways; among other issue, they were restricted to a single logical volume.

Another problematic limitation was the length of file names; although all ASCII characters could be use, the maximum length of any element (level) of a file name was only 14 characters.

Robustness

The old file system had only one copy of all the meta-data of a volume, including the super block. While some of the meta-data (such as the free list could be re-constructed from other meta-data (by scanning all the inodes), most could not.

Performance changes

The most fundamental changes to the file system were needed to increase the performance; in particular, to prevent the fragmentation which rendered high performance impossible.

The 'block size' was increased substantially, although to prevent excessive wastage of space when storing small files, all blocks were divisible into fragments - which are actually the true 'block size' of the new file system; FFS 'blocks' are better thought of as a method to aggregate contiguous groups of fragments into a unit.

Instead of the old layout, with all the inodes at the start of the disk, the disk was divided into cylinder groups, each of which contains a tranche of inodes (along with associated meta-data, such as free inode and fragment bit maps), and a number of cylinders worth of data blocks.

Generally, an attempt is made to allocate all the storage for a file in the same cylinder group as its inode, so that seeks to retrieve the data are minimized. The blocks of a file are also placed on the disk in rotationally-optimized locations.

Inodes contained the block numbers of the first N blocks, so that all the data of files up to a fairly good size could be reached directly; all except the last one were fully blocks, but the last one might contain only one or more fragments. For large files, an inode also held the block numbers of a single indirect block, a double-indirect block (i.e. that block contained the block numbers of a set of indirect blocks), and a triple-indirect block.

To allow tuning of the file system to various applications, many of the 'constants' of the file system (such as the number of fragments in a block) were actually configuration parameters which could be set at the time the file-system was created; these values were stored in the 'super block'. Since the file system would be incomprehensible if these values were lost, a copy of the super-block was stored at the start of each cylinder group.

The full scheme is far too complex to be fully explained here; consult the paper on the FFS for the details.

Functionality changes

A number of changes were made to the FFS to increase the functionality - unlike the performance improvements, which were generally invisible to the users, these were.

Long directory entries

In the original Unix file system, directories contained arrays of fixed-format directory entries, each of which contained an inode number, and (shortish) fixed-length name.

The FFS changed this so that directory entries also contained an 'entry length' field and a 'name length' field; the name was made variable length. From an entry, the start of the next entry could be found using the entry length field. The separate name length field allowed deletion to be an easy process; the unused space of the now-empty entry was added to the previous entry.

Symbolics links, etc

When the inode format was changed, the number of inode types was increased. The old file system allowed for only 4 types (file, directory, and block and character devices). By getting rid of the separate 'allocated' bit (an unallocated inode is now indicated by a 0 type field), the number of types was increased to 7, and two new types were added: symbolic links, and 'sockets' (used by the networking code).

Further reading

Marshall K. McKusick, William N. Joy, Samuel J. Leffler, Robert S. Fabry, A Fast File System for UNIX