Hierarchical File System
From Wikipedia, the free encyclopedia
| HFS | |
|---|---|
| Developer | Apple Computer |
| Full name | Hierarchical File System |
| Introduced | September 17, 1985 (System 2.1) |
| Partition identifier | Apple_HFS (Apple Partition Map) 0xAF (MBR) |
| Structures | |
| Directory contents | B*-tree |
| File allocation | B*-tree |
| Bad blocks | B*-tree |
| Limits | |
| Max file size | 2 GiB |
| Max number of files | 65535 |
| Max filename size | 31 characters |
| Max volume size | 2 TiB |
| Allowed characters in filenames | All 8-bit values except colon ":". Discouraged null and nonprints. |
| Features | |
| Dates recorded | Creation, modification, backup |
| Date range | January 1, 1904 - February 6, 2040 |
| Forks | Only 2 (data and resource) |
| Attributes | Color (3 bits, all other flags 1 bit), locked, custom icon, bundle, invisible, alias, system, stationery, inited, no INIT resources, shared, desktop |
| File system permissions | AppleShare |
| Transparent compression | Yes (third-party), Stacker |
| Transparent encryption | No |
| Supported operating systems | Mac OS, Mac OS X |
Hierarchical File System (HFS), is a file system developed by Apple Computer for use on computers running Mac OS. Originally designed for use on floppy and hard disks, it can also be found on read-only media such as CD-ROMs. HFS is also referred to as HFS Standard and Mac OS Standard, where its successor HFS Plus is also called HFS Extended or Mac OS Extended.
Contents |
[edit] History
HFS was introduced by Apple in September 1985 to replace Macintosh File System (MFS), the original file system which had been introduced the year before with the Macintosh computer. Developed by Patrick Dirks and Bill Bruffey, HFS 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 disks, 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 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.
[edit] 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 Blocks, which contain system startup information. For example, the names of the System and Shell (usually the Finder) 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*-tree 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*-tree 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 code, type code, 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.
[edit] 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 multitasking, 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.[1] It is also a serious reliability concern, as damage to this file can destroy the entire file system. This contrasts with other filesystems that store file and directory records in separate structures (such as Microsoft'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.
[edit] References
- ^ Giampaolo, Dominic (1999). Practical File System Design with the Be File System (PDF), Morgan Kaufmann, 37. ISBN 1-55860-497-9.
[edit] See also
[edit] External links
- HFS specification from developer.apple.com
- The HFS Primer (PDF) 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 Windows
- hfsutils - open-source software to manipulate HFS on Unix, DOS, Windows, OS/2
| Applications |
|---|
|
Apple File Security · Calculator · Chooser · Drive Setup · DVD Player · Finder · Graphing Calculator · Keychain Access · PictureViewer · PowerTalk - QuickTime Player · Network Browser · Scrapbook · Sherlock · Software Update · Stickies · Apple System Profiler · SimpleText |
| Developer |
| Technology |
|
Command (⌘) · Option (⌥) · JavaScript · Code Fragment Manager · WorldScript Control Strip · Creator code · Hierarchical File System · HFS Plus · Keychain · Apple Data Detectors - V-Twin / Apple Information Access Technology - Macintosh File System · PICT · QuickDraw · QuickTime · Resource fork · Type code · WorldScript |
| Related articles |
|
Manager · Toolbox · Memory Management · Old World ROM · New World ROM |
