UNIX file system

The UNIX file system was one of the first file systems to internally completely separate directories (the catalogues of files) from the meta-data about a file (such as the information about where the data of the file was stored).

UNIX did this through the mechanism of the inode, a separate structure, in which most of the information about a file was kept. Directories were implemented as an abstraction on top of the previous layer), using 'file' objects provided by the inode layer; directory files only held mappings from file-names (visible to users) to inode numbers (used internally by the operating system, and generally not visible to users).

The inodes themselves were held in an inode table, the ilist, kept in a separate area of the disk, outside the area used to hold the blocks of the files themselves. A special block, the root block (also called the super-block) - initially held in block 0, later block 1, on the disk partition - held information about which blocks in the partition held the inodes, which blocks were available to hold data, and other general information about the file system on that partition.

Details

For the sake of efficiency (there are many more small files than large ones), the location of the first few blocks of a file was kept in the inode itself. If a file needed to grow past that, indirect blocks were used; these were blocks (stored in the area of the disk used for file data) which held an array of the block numbers of the actual blocks of the file; the block numbers of the indirect blocks were held in the inode.

The file system allowed 'holey' files; in the tables of block numbers (either in the inode, or in indirect blocks), a block number of 0 indicated that block had never been written to, and thus never allocated. The UNIX file I/O system allowed users to write data wherever they wanted within a file, leaving gaps if they so desired. Such 'missing' blocks contained all zeros when read.

Inodes also held information such as the length of the file, whether the file was actually a directory (treated specially by the system, in that only the system could write to it, to prevent users from damaging the file system), the owner of the file, the file's protection, and last modification and access times, etc.

Finally, the inode held a count of the number of hard links to the file; a given file could appear in more than one directory, and the count was needed to garbage collect the file's blocks when the last directory entry for it was deleted. All directory entries for a file were equal; none had special status.

Evolution

Within the above general scheme, the UNIX file system evolved in minor ways over time. After UNIX Fourth Edition‎, the inode itself indicated whether it was a 'special file', for a device, rather than an ordinary file; before V4, inodes 1-40. were reserved for special files.

Also starting with V4, information about which blocks were 'free', and available to be allocated to files, was kept in a 'free list' of blocks, the head of which was kept in the root block. (Prior to V4, this information was kept in a separate bit array.) When a partition was initialized as a file system, the free list was constructed to hold all the blocks available for files. Similarly, starting in V4, the root block also held a cache of free inodes; when this was exhausted, a sweep of the ilist on the disk refilled it. (Hopefully!)

V4, V5 and V6 file systems are almost identical (to the point that most tools for the early versions of the file system will work on most instances of the latest); but V6 includes support for extra-large (huge) files. In these, the last indirect block listed in the inode did not contain the block numbers of data blocks, but rather the block numbers of 'double-indirect blocks', which then held the block numbers of 'ordinary' indirect blocks. PWB/UNIX, although mostly V6, does not support extra-large files.

Without extra-large files, the largest file supported is 512*256*8=1,048,576 bytes; with extra-large files, in theory it could be somewhat larger than 256*256*512=33,554,432 bytes - but the length of a file is stored in a 24-bit field in the inode, so in practice a file in a V6 file system can be at most 16,777,216 bytes long. If a V6 file system does not have any files longer than 512*256*7=917,504 bytes, this distinction can be ignored; all the early tools will work on it.

By the time of Unix Seventh Edition, disks had grown in size to the point that use of 16-bit block numbers were a serious handicap. Prior to V7, larger disks had been handled by splitting them into partitions, with none being larger than 2^16=65,536 blocks. In V7, block numbers were increased in size from 16 bits to 32; the inode format was changed to accommodate this, and had a number of other minor changes.

Further evolution

The UNIX file system, as described above, lasted quite a long time; minor detail changes were made over time, but in general the above description of the details applied to most versions of UNIX before BSD 4.1b. As UNIX became used for larger and larger machines, however, two aspects of the file system became problematic: performance, and robustness.

The former was basically caused by the tendency of the UNIX file system to scatter the blocks of a file (especially large data files, where performance was more of an issue) across the entire disk, once the file system had been in use for a while. The latter was caused by the fact that there was only a single copy of much critical information, e.g. the root block.

A major modification to the UNIX file system was therefore done, the BSD Fast File System. It kept the basic concept of the two-level system, with inodes and directories, but made extensive detail changes (e.g. having multiple copies of the root block, scattered across the disk) to address the efficiency and robustness issues.

See also

• Repairing early UNIX file systems

External links

• UNIX Implementation - a Thompson paper which gives an overview of the implementation of the file system
• fs(V) - short but clear detailed specification of the V5 file system
• directory(V)
• fs(V) - the V6 file system description
• filsys(V) - the V7 file system description