Inside Macintosh: Files /

Chapter 2 - File Manager

Data Organization on Volumes

This section describes how data is organized on HFS volumes. In general, an application that simply manipulates data stored in files does not need to know how that data is organized on a volume or on the physical storage medium containing that volume. The organization described in this section is maintained by the File Manager for its own uses. Some specialized applications and file-system utilities, however, do need to know exactly how file data is stored on a disk.

WARNING

This section is provided primarily for informational purposes. The organization of data on volumes is subject to change. Before you use this information to read or modify the data stored on a volume, be sure to check that the drSigWord field in the master directory block (described in "Master Directory Blocks" beginning on page 2-59) identifies that volume as an HFS volume.

Much of the information describing the files and directories on an HFS volume is read into memory when the volume is mounted. (For example, most of the volume's master directory block is read into memory as a volume control block.) For a description of how that data is organized in memory, see "Data Organization in Memory" beginning on page 2-76.

The File Manager uses a number of interrelated structures to manage the organization of data on disk and in memory. For this reason, it is easy to lose sight of the simple and elegant scheme that underlies these structures. As you read through this section and the next, you should keep these points in mind:

• The File Manager keeps track of which blocks on a disk are allocated to files and which are not by storing a volume bitmap on disk and in memory. If a bit in the map is set, the corresponding block is allocated to some file; otherwise, the corresponding block is free for allocation.
• The File Manager always allocates logical disk blocks to a file in groups called allocation blocks; an allocation block is simply a group of consecutive logical blocks. The size of a volume's allocation blocks depends on the capacity of the volume; there can be at most 65,535 allocation blocks on a volume.
• The File Manager keeps track of the directory hierarchy on a volume by maintaining a file called the catalog file; the catalog file lists all the files and directories on a volume, as well as some of the attributes of those files and directories. A catalog file is organized as a B*-tree (or "balanced tree") to allow quick and efficient searches through a directory hierarchy that is typically quite large.
• The File Manager keeps track of which allocation blocks belong to a file by maintaining a list of the file's extents; an extent is a contiguous range of allocation blocks allocated to some file, which can be represented by a pair of numbers: the start of the range and the length of the range. The first three extents of most files are stored in the volume's catalog file. All remaining file extents are stored in the extents overflow file, which is also organized as a B*-tree.
• The first three extents of the catalog file and the extents overflow file are stored in the master directory block (on disk) and the volume control buffer (in memory); a master directory block is always located at a fixed offset from the beginning of a volume, and a volume control block is stored in the VCB queue.

---

Subtopics

Disk and Volume Organization

Boot Blocks

Master Directory Blocks

Volume Bitmaps

B*-Trees

Catalog Files

Extents Overflow Files