Next Previous Contents

7. Macintosh Hierarchical Filesystem - HFS

All Macintosh storage devices except floppy disks are partitioned into one or more volumes. Volumes can contain four kinds of items: files, directories, directory threads and file threads. Each item is described by a catalog record which is analogous to a Unix inode. Catalog records are organized in the on-disk catalog B-Tree. Directory contents are derived from searching the catalog B-Tree. Only a file can occupy space outside of its catalog record.

A Macintosh "file" contains two components, or forks. The resource fork is an indexed file containing code segments, menu items, dialog boxes, etc. The data fork has the "stream of bytes" semantics of a Unix file contents. Each fork is comprised of one or more extents or contiguous runs of blocks. An extent descriptor encodes an extent's starting block and length into a 32bit quantity. The first extent record (three extent descriptors) of each fork is a part of the file's catalog record. Any further extent records are kept in the extents overflow B-Tree.

In addition to file and B-Tree extents a volume also contains two boot blocks, a volume information block, and a free space bitmap. There is a remarkable amount of redundancy in the on diskdata structures which improves crash recovery. While not strictly a part of the filesystem, it should be noted that several catalog record fields are reserved for the exclusive use of Finder, a program which handles user access to the filesystem and automatically maintains associations between applications and data files. Thus, HFS must also maintain this Finder info.

Every file and directory on an HFS volume has an identification number, similar to an inode number in the Unix filesystem. However, a file or directory is named by its parent's identification number and the file or directory's file name, which is a 32 character string that can contain nulls. This combination is the search key to the volume's catalog B-Tree. The catalog B-Tree differs from a traditional B-Tree structure in that all the nodes at each level of the B-Tree are linked together to form a doubly linked list and all of the records are in the leaf nodes. These variations permit accessing many items in the same directory by traversing the leaves using the linked list. Strictly speaking, the HFS B-Trees are a variant of B+-Trees although Apple's technical documentation calls them B*-Trees.

Each directory, including the root directory, contains its directory thread, which has the empty filename. The directory thread record contains the name of the directory and the id of the parent of the directory. Similarly, filethreads contain the name of a file and the id of the directory they are in. While every directory must contain a directory thread, file threads are very uncommon. In fact, both are examples of HFS redundancy - for undamaged trees, threads are not strictly necessary. Both file and directory records contain 32 bytes of information used by Finder. The first three extent descriptors for the catalog B-Tree are kept in the volume information block. If the catalog B-Tree file grows beyond three extents, the remaining extent descriptors are kept in the extents overfow.

HFS and HFS+ (also called Sequoia) filesystems are well documented. The best source of tech. information about HFS can be found in the Inside Macintosh series of books. Look at http://developer.apple.com/techpubs/mac/Files/Files-99.html. The HFS+ filesystem is described in Technote 1150, available online at http://developer.apple.com/technotes/tn/tn1150.html. A lot of information is available also in other technotes. This links are collected by Paul H. Hargrove:

7.1 Accessing HFS from Linux

7.2 Accessing HFS from OS/2 (HFS/2)

HFS/2 lets OS/2 users seamlessly read and write files on diskettes formatted with the Hierarchical File System, the file system used by Macintosh computers. With HFS/2, Macintosh diskettes can be used just as if they were regular diskettes.

This program is no longer being developed, because author doesn't use OS/2. If you are willing to maintain the program, let him know.

7.3 Accessing HFS from Windows 95/98/NT (HFV Explorer)

An HFS volume browser for Windows NT and Windows 9x based on hfsutils. Launch pad support for all major Macintosh emulators running on Windows.

7.4 Accessing HFS from DOS (MAC-ETTE)

Mac-ette is a PC utility which can read, write, format and duplicate Macintosh HFS format 1.4 Meg diskettes on a PC equipped with a 3.5 inch high density diskette drive.

7.5 HFS utils

The hfsutils package contains a set of command-line utilities such as hformat, hmount, hdir, hcopy, etc. They allow read-write access of files and directories on HFS volumes.

7.6 MacFS: A Portable Macintosh File System Library

This is a Macintosh file system library which is portable to a variety of operating systems and platforms. It presents a programming interface sufficient for creating a user level API as well as file system drivers for operating systems that support them. Authors implemented and tested such a user level API and utility programs based on it as well as an experimental Unix Virtual File System. They also describe the Macintosh Hierarchical File System and their implementation and note that the design is not well suited to reentrancy and that its complex data structures can lead to slow implementations in multiprogrammed environments. Performance measurements show that our implementation is faster than the native Macintosh implementation at creating, deleting, reading and writing files with small request sizes, but slower than the Berkeley Fast File System (FFS.) However, the native Macintosh implementation can perform large read and write operations faster that either our implementation or FFS.

Next Previous Contents

Hosting by: Hurra Communications Ltd.
Generated: 2007-01-26 17:58:09