UNIX file system

The UNIX file system was one of the first file systems to internally 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).

It 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, which only held mappings from file-names (visible to users) to inode numbers.

The inodes themselves were held 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 (initially, block 0 on the disk partition) held information about where in the partition the inodes were stored, which blocks were available to hold data, and other general information about the file system on that partition.

Details

Information about which blocks were 'free', and available to be allocated to files, was kept in a 'free list', the head of which was kept in the root block. The root block also held a cache of free inodes; when this was exhausted, a sweep of the inode table refilled it. (Hopefully!)

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 next blocks of the file; the block numbers of the indirect blocks were held in the inode. For even larger files, the last indirect block noted in the inode did not hold the block numbers of data blocks, but the block numbers of 'double-indirect blocks', which held the block numbers of ordinary indirect blocks.

The file system allowed 'holey' files; in the tables of block numbers, a block number of 0 indicated that block had never been written to, and thus never allocated. The UNIX 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.

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

BSD Fast File System