Hierarchical File System
Encyclopedia
Hierarchical File System (HFS) is a file system
developed by Apple Inc. for use in computer systems running Mac OS
. Originally designed for use on floppy
and hard disk
s, it can also be found on read-only media such as CD-ROM
s. HFS is also referred to as Mac OS Standard (or, erroneously, "HFS Standard"), where its successor, HFS Plus
, is also called Mac OS Extended (or, erroneously, “HFS Extended”). With the introduction of OS X 10.6, Apple has dropped support to format or write HFS disks and images
, which are only supported as read-only volumes.
for the Macintosh, replacing the Macintosh File System
(MFS), the original file system which had been introduced over a year and a half earlier with the first Macintosh
computer. Drawing heavily upon Apple's first hierarchical SOS operating system for the failed Apple III
, which also served as the basis for hierarchical filing systems on the Apple IIe
and Lisa
, HFS was developed by Patrick Dirks and Bill Bruffey and it shared a number of design features with MFS that were not available in other file systems of the time (such as DOS
's FAT
). Files could have multiple forks (normally a data and a resource fork
), which allowed program code to be stored separately from resources such as icons that might need to be localised. Files were referenced with unique file IDs rather than file names, and file names could be 255 characters long (although the Finder only supported a maximum of 31 characters).
However MFS was optimised to be used on very small and slow media, namely floppy disk
s, so HFS was introduced to overcome some of the performance problems that arrived with the introduction of larger media, notably hard drives. The main concern was the time needed to display the contents of a folder. Under MFS all of the file and directory listing information was stored in a single file, which the system had to search to build a list of the files stored in a particular folder. This worked well with a system with a few hundred kilobytes of storage and perhaps a hundred files, but as the systems grew into megabytes and thousands of files, the performance degraded rapidly.
The solution was to replace MFS's directory structure with one more suitable to larger file systems. HFS replaced the flat table structure with the Catalog File which uses a B-tree
structure that could be searched very quickly regardless of size. HFS also re-designed various structures to be able to hold larger numbers, 16-bit integers being replaced by 32-bit almost universally. Oddly, one of the few places this "upsizing" did not take place was the file directory itself, which limits HFS to a total of 64k files.
While HFS is a proprietary file system format, it is well documented so there are usually solutions available to access HFS formatted disks from most modern operating system
s.
Although Apple introduced HFS out of necessity with its first 20MB hard disk
offering for the Macintosh in September of 1985, HFS wasn't widely introduced until System 3.0 which debuted with the Macintosh Plus
in January 1986 along with the larger 800K floppy disk drive for the Macintosh, which also required HFS support. More importantly, HFS was hard-coded into new Plus' 128K ROM
, freeing not only space from the system software disk, but also RAM
. However, RAM based HFS support was also implemented for use with the earlier Macintosh 512K
's 64K ROM through the addition of an INIT
file on the System Disk. The introduction of HFS was the first advancement by Apple to leave a Macintosh model behind: the original 128K Macintosh
, which lacked sufficient memory to load the HFS code and was promptly discontinued.
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
, and beginning with OS X 10.6 (Snow Leopard), HFS volumes are read-only and cannot be created or updated.
There are five structures that make up an HFS volume:
, as only one program can write to this structure at a time, meaning that many programs may be waiting in queue due to one program "hogging" the system. It is also a serious reliability concern, as damage to this file can destroy the entire file system. This contrasts with other file systems that store file and directory records in separate structures (such as DOS's FAT file system or the Unix File System
), where having structure distributed across the disk means that damaging a single directory is generally non-fatal and the data may possibly be re-constructed with data held in the non-damaged portions.
Additionally, the limit of 65,535 allocation blocks resulted in files having a "minimum" size equivalent 1/65,535th the size of the disk. Thus, any given volume, no matter its size, could only store a maximum of 65,535 files. Moreover, any file would be allocated more space than it actually needed, up to the allocation block size. When disks were small, this was of little consequence, because the individual allocation block size was trivial, but as disks started to approach the 1 GB mark, the smallest amount of space that any file could occupy (a single allocation block) became excessively large, wasting significant amounts of disk space. For example, on a 1 GB disk, the allocation block size under HFS is 16 KB, so even a 1 byte file would take up 16 KB of disk space. This situation was less of a problem for users having large files (such as pictures, databases or audio) because these larger files wasted less space as a percentage of their file size. Users with many small files, on the other hand, could lose a copious amount of space due to large allocation block size. This made partitioning disks into smaller logical volumes very appealing for Mac users, because small documents stored on a smaller volume would take up much less space than if they resided on a large partition. The same problem existed in the FAT16 file system.
File system
A file system is a means to organize data expected to be retained after a program terminates by providing procedures to store, retrieve and update data, as well as manage the available space on the device which contain it. A file system organizes data in an efficient manner and is tuned to the...
developed by Apple Inc. for use in computer systems running Mac OS
Mac OS
Mac OS is a series of graphical user interface-based operating systems developed by Apple Inc. for their Macintosh line of computer systems. The Macintosh user experience is credited with popularizing the graphical user interface...
. Originally designed for use on floppy
Floppy disk
A floppy disk is a disk storage medium composed of a disk of thin and flexible magnetic storage medium, sealed in a rectangular plastic carrier lined with fabric that removes dust particles...
and hard disk
Hard disk
A hard disk drive is a non-volatile, random access digital magnetic data storage device. It features rotating rigid platters on a motor-driven spindle within a protective enclosure. Data is magnetically read from and written to the platter by read/write heads that float on a film of air above the...
s, it can also be found on read-only media such as CD-ROM
CD-ROM
A CD-ROM is a pre-pressed compact disc that contains data accessible to, but not writable by, a computer for data storage and music playback. The 1985 “Yellow Book” standard developed by Sony and Philips adapted the format to hold any form of binary data....
s. HFS is also referred to as Mac OS Standard (or, erroneously, "HFS Standard"), where its successor, HFS Plus
HFS Plus
HFS Plus or HFS+ is a file system developed by Apple Inc. to replace their Hierarchical File System as the primary file system used in Macintosh computers . It is also one of the formats used by the iPod digital music player...
, is also called Mac OS Extended (or, erroneously, “HFS Extended”). With the introduction of OS X 10.6, Apple has dropped support to format or write HFS disks and images
Disk image
A disk image is a single file or storage device containing the complete contents and structure representing a data storage medium or device, such as a hard drive, tape drive, floppy disk, CD/DVD/BD, or USB flash drive, although an image of an optical disc may be referred to as an optical disc image...
, which are only supported as read-only volumes.
History
HFS was introduced by Apple in September 1985 specifically to support Apple's first hard disk driveHard Disk 20
The Macintosh Hard Disk 20 was the first hard drive developed by Apple Computer specifically for use with the Macintosh 512K. Introduced on September 17, 1985, it was part of Apple's long awaited solution toward completing the Macintosh Office announced in January 1985...
for the Macintosh, replacing the Macintosh File System
Macintosh File System
Macintosh File System is a volume format created by Apple Computer for storing files on 400K floppy disks. MFS was introduced with the Macintosh 128K in January 1984....
(MFS), the original file system which had been introduced over a year and a half earlier with the first Macintosh
Macintosh 128K
The Macintosh 128K machine, released as the "Apple Macintosh", was the original Apple Macintosh personal computer. Its beige case contained a monitor and came with a keyboard and mouse. An indentation in the top of the case made it easier for the computer to be lifted and carried. It had a selling...
computer. Drawing heavily upon Apple's first hierarchical SOS operating system for the failed Apple III
Apple III
The Apple III is a business-oriented personal computer produced and released by Apple Computer that was intended as the successor to the Apple II series, but largely considered a failure in the market. Development work on the Apple III started in late 1978 under the guidance of Dr. Wendell Sander...
, which also served as the basis for hierarchical filing systems on the Apple IIe
Apple IIe
The Apple IIe is the third model in the Apple II series of personal computers produced by Apple Computer. The e in the name stands for enhanced, referring to the fact that several popular features were now built-in that were only available as upgrades and add-ons in earlier models...
and Lisa
Apple Lisa
The Apple Lisa—also known as the Lisa—is a :personal computer designed by Apple Computer, Inc. during the early 1980s....
, HFS was developed by Patrick Dirks and Bill Bruffey and it shared a number of design features with MFS that were not available in other file systems of the time (such as DOS
DOS
DOS, short for "Disk Operating System", is an acronym for several closely related operating systems that dominated the IBM PC compatible market between 1981 and 1995, or until about 2000 if one includes the partially DOS-based Microsoft Windows versions 95, 98, and Millennium Edition.Related...
's FAT
File Allocation Table
File Allocation Table is a computer file system architecture now widely used on many computer systems and most memory cards, such as those used with digital cameras. FAT file systems are commonly found on floppy disks, flash memory cards, digital cameras, and many other portable devices because of...
). Files could have multiple forks (normally a data and a resource fork
Resource fork
The resource fork is a construct of the Mac OS operating system used to store structured data in a file, alongside unstructured data stored within the data fork. A resource fork stores information in a specific form, such as icons, the shapes of windows, definitions of menus and their contents, and...
), which allowed program code to be stored separately from resources such as icons that might need to be localised. Files were referenced with unique file IDs rather than file names, and file names could be 255 characters long (although the Finder only supported a maximum of 31 characters).
However MFS was optimised to be used on very small and slow media, namely floppy disk
Floppy disk
A floppy disk is a disk storage medium composed of a disk of thin and flexible magnetic storage medium, sealed in a rectangular plastic carrier lined with fabric that removes dust particles...
s, so HFS was introduced to overcome some of the performance problems that arrived with the introduction of larger media, notably hard drives. The main concern was the time needed to display the contents of a folder. Under MFS all of the file and directory listing information was stored in a single file, which the system had to search to build a list of the files stored in a particular folder. This worked well with a system with a few hundred kilobytes of storage and perhaps a hundred files, but as the systems grew into megabytes and thousands of files, the performance degraded rapidly.
The solution was to replace MFS's directory structure with one more suitable to larger file systems. HFS replaced the flat table structure with the Catalog File which uses a B-tree
B-tree
In computer science, a B-tree is a tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree is a generalization of a binary search tree in that a node can have more than two children...
structure that could be searched very quickly regardless of size. HFS also re-designed various structures to be able to hold larger numbers, 16-bit integers being replaced by 32-bit almost universally. Oddly, one of the few places this "upsizing" did not take place was the file directory itself, which limits HFS to a total of 64k files.
While HFS is a proprietary file system format, it is well documented so there are usually solutions available to access HFS formatted disks from most modern operating system
Operating system
An operating system is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer system...
s.
Although Apple introduced HFS out of necessity with its first 20MB hard disk
Hard Disk 20
The Macintosh Hard Disk 20 was the first hard drive developed by Apple Computer specifically for use with the Macintosh 512K. Introduced on September 17, 1985, it was part of Apple's long awaited solution toward completing the Macintosh Office announced in January 1985...
offering for the Macintosh in September of 1985, HFS wasn't widely introduced until System 3.0 which debuted with the Macintosh Plus
Macintosh Plus
The Macintosh Plus computer was the third model in the Macintosh line, introduced on January 16, 1986, two years after the original Macintosh and a little more than a year after the Macintosh 512K, with a price tag of US$2599...
in January 1986 along with the larger 800K floppy disk drive for the Macintosh, which also required HFS support. More importantly, HFS was hard-coded into new Plus' 128K ROM
Read-only memory
Read-only memory is a class of storage medium used in computers and other electronic devices. Data stored in ROM cannot be modified, or can be modified only slowly or with difficulty, so it is mainly used to distribute firmware .In its strictest sense, ROM refers only...
, freeing not only space from the system software disk, but also RAM
Ram
-Animals:*Ram, an uncastrated male sheep*Ram cichlid, a species of freshwater fish endemic to Colombia and Venezuela-Military:*Battering ram*Ramming, a military tactic in which one vehicle runs into another...
. However, RAM based HFS support was also implemented for use with the earlier Macintosh 512K
Macintosh 512K
The Macintosh 512K Personal Computer, also known as the "Fat Mac", is the second of a long line of Apple Macintosh computers, was the first update to the original Macintosh 128K. It was virtually identical to the previous Mac, differing primarily in the amount of built-in memory , which quadrupled...
's 64K ROM through the addition of an INIT
Init
init is a program for Unix-based computer operating systems that spawns all other processes. It runs as a daemon and typically has PID 1. The boot loader starts the kernel and the kernel starts init...
file on the System Disk. The introduction of HFS was the first advancement by Apple to leave a Macintosh model behind: the original 128K Macintosh
Macintosh 128K
The Macintosh 128K machine, released as the "Apple Macintosh", was the original Apple Macintosh personal computer. Its beige case contained a monitor and came with a keyboard and mouse. An indentation in the top of the case made it easier for the computer to be lifted and carried. It had a selling...
, which lacked sufficient memory to load the HFS code and was promptly discontinued.
In 1998, Apple introduced HFS Plus
HFS Plus
HFS Plus or HFS+ is a file system developed by Apple Inc. to replace their Hierarchical File System as the primary file system used in Macintosh computers . It is also one of the formats used by the iPod digital music player...
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
Mac OS X
Mac OS X is a series of Unix-based operating systems and graphical user interfaces developed, marketed, and sold by Apple Inc. Since 2002, has been included with all new Macintosh computer systems...
an HFS volume cannot be used for booting
Booting
In computing, booting is a process that begins when a user turns on a computer system and prepares the computer to perform its normal operations. On modern computers, this typically involves loading and starting an operating system. The boot sequence is the initial set of operations that the...
, and beginning with OS X 10.6 (Snow Leopard), HFS volumes are read-only and cannot be created or updated.
Design
The Hierarchical File System divides a volume into logical blocks of 512 bytes. These logical blocks are then grouped together into allocation blocks which can contain one or more logical blocks depending on the total size of the volume. HFS uses a 16 bit value to address allocation blocks, limiting the number of allocation blocks to 65,536.There are five structures that make up an HFS volume:
- Logical blocks 0 and 1 of the volume are the Boot BlocksBoot sectorA boot sector or boot block is a region of a hard disk, floppy disk, optical disc, or other data storage device that contains machine code to be loaded into random-access memory by a computer system's built-in firmware...
, which contain system startup information. For example, the names of the System and Shell (usually the FinderMacintosh FinderThe Finder is the default file manager used on Mac OS and Mac OS X operating systems; it is responsible for the overall user-management of files, disks, network volumes and the launching of other applications...
) files which are loaded at startup. - Logical 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 logical 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.
- Logical 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 Extent Overflow File is a B-treeB-treeIn computer science, a B-tree is a tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree is a generalization of a binary search tree in that a node can have more than two children...
that contains extra extents that record which allocation blocks are allocated to which files, once the initial three extents 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 the file system from trying to allocate a bad block to a file. - The Catalog File is another B-treeB-treeIn computer science, a B-tree is a tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree is a generalization of a binary search tree in that a node can have more than two children...
that contains records for all the files and directories stored in the volume. It stores four types of records. Each file consists of a File Thread Record and a File Record while each directory consists of a Directory Thread Record and a Directory Record. Files and directories in the Catalog File are located by their unique Catalog Node ID (or CNID).- A File Thread Record stores just the name of the file and the CNID of its parent directory.
- A File Record 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 codeCreator codeA creator code is a mechanism introduced in pre-Mac OS X versions of the Macintosh operating system to link a data file to the application program which created it, in a manner similar to file extensions in other operating systems. Codes are four-byte OSTypes. For example, the creator code of the...
, type codeType codeA type code is the only mechanism used in pre-Mac OS X versions of the Macintosh operating system to denote a file's format, in a manner similar to file extensions in other operating systems. Codes are four-byte OSTypes...
, the window the file should appear in and its location within the window. - A Directory Thread Record stores just the name of the directory and the CNID of its parent directory.
- A Directory Record which stores data like the number of files stored within the directory, the CNID of the directory, three timestamps (when the directory 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.
Problems
The Catalog File, which stores all the file and directory records in a single data structure, results in performance problems when the system allows multitaskingComputer multitasking
In computing, multitasking is a method where multiple tasks, also known as processes, share common processing resources such as a CPU. In the case of a computer with a single CPU, only one task is said to be running at any point in time, meaning that the CPU is actively executing instructions for...
, as only one program can write to this structure at a time, meaning that many programs may be waiting in queue due to one program "hogging" the system. It is also a serious reliability concern, as damage to this file can destroy the entire file system. This contrasts with other file systems that store file and directory records in separate structures (such as DOS's FAT file system or the Unix File System
Unix File System
The Unix file system is a file system used by many Unix and Unix-like operating systems. It is also called the Berkeley Fast File System, the BSD Fast File System or FFS...
), where having structure distributed across the disk means that damaging a single directory is generally non-fatal and the data may possibly be re-constructed with data held in the non-damaged portions.
Additionally, the limit of 65,535 allocation blocks resulted in files having a "minimum" size equivalent 1/65,535th the size of the disk. Thus, any given volume, no matter its size, could only store a maximum of 65,535 files. Moreover, any file would be allocated more space than it actually needed, up to the allocation block size. When disks were small, this was of little consequence, because the individual allocation block size was trivial, but as disks started to approach the 1 GB mark, the smallest amount of space that any file could occupy (a single allocation block) became excessively large, wasting significant amounts of disk space. For example, on a 1 GB disk, the allocation block size under HFS is 16 KB, so even a 1 byte file would take up 16 KB of disk space. This situation was less of a problem for users having large files (such as pictures, databases or audio) because these larger files wasted less space as a percentage of their file size. Users with many small files, on the other hand, could lose a copious amount of space due to large allocation block size. This made partitioning disks into smaller logical volumes very appealing for Mac users, because small documents stored on a smaller volume would take up much less space than if they resided on a large partition. The same problem existed in the FAT16 file system.
External links
- HFS specification from developer.apple.com
- The HFS Primer (PDFPortable Document FormatPortable Document Format is an open standard for document exchange. This file format, created by Adobe Systems in 1993, is used for representing documents in a manner independent of application software, hardware, and operating systems....
) from MWJ - Filesystems HOWTO: HFS - slightly out of date
- HFS File Structure Explained - early description of HFS
- DiskWarrior - Software to eliminate all damage to the HFS disk directory
- MacDrive - Software to read and write HFS/HFS Plus formatted disks on Microsoft WindowsMicrosoft WindowsMicrosoft Windows is a series of operating systems produced by Microsoft.Microsoft introduced an operating environment named Windows on November 20, 1985 as an add-on to MS-DOS in response to the growing interest in graphical user interfaces . Microsoft Windows came to dominate the world's personal...
- hfsutils - open-source software to manipulate HFS on Unix, DOS, Windows, OS/2