Hierarchical File System
HFS is an acronym for Hierarchical File System, a format specification of a file system for storing files on floppy and hard disks by Apple computers running Mac OS, but can also be found on read-only media such as CD-ROMs.
History
HFS was introduced in January 1986 as a new file system for Macintosh computers. It superseded the Macintosh File System (MFS) which was a flat file system, used only on the earliest Mac models. Because Macintosh computers use richer data than other commonly available file systems such as FAT used by DOS or the original Unix file system would allow, Apple developed a new more appropriate file system, rather than adopting an existing specification. For example, HFS permits filenames up to 31 characters in length, supports metadata and dual forked (separate data and resource forks per file) files.
While HFS like most other file systems may be seen as a proprietary format, because it was so well documented there are usually solutions available to access HFS formatted disks from most modern operating systems.
In 1998, Apple introduced HFS Plus to address inefficient allocation of disk space in HFS and to add other improvements. HFS is still supported by current versions of Mac OS, but starting with Mac OS X an HFS volume cannot be used for booting.
Design and implementation
These are the structures that make up HFS volumes:
- Blocks 0 and 1 of the volume are the Boot Blocks, these contain system startup information. For example the names of the System and Shell (usually the Finder) files which are loaded at startup.
- Block 2 contains the Master Directory Block (aka MDB). This defines a wide variety of data about the volume itself, for example date & time stamps for when the volume was created, the location of the other volume structures such as the Volume Bitmap or the size of logical structures such as allocation blocks. There is also a duplicate of the MDB called the Alternate Master Directory Block (aka Alternate MDB) located at the opposite end of the volume in the second to last block. This is intended mainly for use by disk utilities and is only updated when either the Catalog File or Extents Overflow File grow in size.
- Block 3 is the starting block of the Volume Bitmap, which keeps track of which allocation blocks are in use and which are free. Each allocation block on the volume is represented by a bit in the map, if the bit is set then the block is in use, if it is clear then the block is free to be used. Since the Volume Bitmap must have a bit to represent each allocation block, its size is determined by the size of the volume itself.
- The Catalog File is a B*-tree that contains information on all the files and directories stored in the volume. Each file or directory in the Catalog File can be located by its unique Catalog Node ID (or CNID).
- Each file is made up of a File Thread Record which stores just the name of the file and the CNID of its parent directory and a File Record which stores a variety of metadata about the file including its CNID, the size of the file, three timestamps (when the file was created, last modified, last backed up), the first file extents of the data and resource forks and pointers to the file's first data and resource extent records in the Extent Overflow File. The File Record also stores two 16 byte fields that are used by the Finder to store attributes about the file including things like its creator code, type code, the window the file should appear in and its location within the window.
- Similarly each directory is made up of a Directory Thread Record which stores just the name of the directory and the CNID of its parent directory and a Directory Record which stores data like the number of files stored within the directory, the CNID of the directory, three timestamps (when the file was created, last modified, last backed up). Like the File Record, the Directory Record also stores two 16 byte fields for use by the Finder. These store things like the width & height and x & y co-ordinates for the window used to display the contents of the directory, the display mode (icon view, list view, etc) of the window and the position of the window's scroll bar.
- The Extent Overflow File is another B*-tree that contains extents that record blocks allocated to files once the initial three allowed for each file in the Catalog File are used up. Later versions also added the ability for the Extent Overflow File to store extents that record bad blocks, to prevent a machine from trying to write to them.
