目次 HFS Plus の基礎 コアとなる概念 ボリュームヘッダー B ツリー カタログファイル エクステントオーバーフローファイル アロケーションファイル アトリビュートファイル スタートアップファイル ハードリンク シンボリックリンク ジャーナル HFSX メタデータゾーン ホットファイル Unicode に関する微妙な問題 HFS ラッパー ボリュームの一貫性のチェック 要約 ダウンロード

このテクニカルノートでは、HFS Plus ボリュームのオンディスクフォーマットについて説明します。 ただし、HFS Plus ボリュームに関するプログラミングインタフェースについては説明しません。 このテクニカルノートは、File Manager プログラミングインタフェースによって提供される抽象層の下位にある非常にローレベルな層で HFS Plus を使った作業を必要とするデベロッパ向けに書かれています。 この中には、ディスク修復ユーティリティのデベロッパや、HFS Plus のサポートを他のプラットフォームにインプリメントしようとしているプログラマなどが含まれます。 このテクニカルノートでは、読者が「Inside Macintosh: Files」に記載されている HFS ボリュームに関する基本概念を十分に理解していることを前提にします。 [2004 年 5 月 5 日]

HFS Plus の基礎

HFS Plus は、MacOS のボリュームフォーマットです。 HFS Plus は、Mac OS 8.1 から導入されました。 HFS Plus のアーキテクチャは HFS にきわめて似ていますが、いくつかの変更が加えられています。 次に、重要な相違点をまとめた一覧表を示します。

表 1 HFS と HFS Plus の比較

これらの HFS Plus の機能をどの程度までプログラミングインタフェースを介して使用できるかは OS によります。 バージョン 9.0 以前の Mac OS では HFS Plus 固有の機能に対応するプログラミングインタフェースを提供していません。

まとめると、HFS Plus ボリュームフォーマットの設計を導いた主な目標は、次のとおりでした。

• ディスク領域の効率的な使用
• 世界各国の言語に対応したファイル名
• 将来計画されている名前付きフォークのサポート
• 非 Mac OS オペレーティングシステムにおけるブートの簡易化

次のセクションでは、これらの目標と、これらの目標を実現するための HFS と HFS Plus に対する要求の相違について説明します。

ディスク領域の効率的な使用

HFS では、ボリューム上の領域全体をアロケーションブロックと呼ばれる等しいサイズの小区画に分割します。 HFS は 16 ビットのフィールドを使って特定のアロケーションブロックを識別するため、HFS ボリューム上のアロケーションブロックの数は 2¹⁶ (65,536) 未満でなければなりません。 通常、1 つのアロケーションブロックのサイズは、ボリューム上のアロケーションブロックの数が 65,536 未満となるような 512 の最小倍数です（つまり、ボリュームサイズを 65,535 で割り、それを 512 の倍数に丸めた値）。 空でないフォークは、整数個のアロケーションブロックを占有する必要があります。 これは、1 つのフォークによって占有される領域の容量がアロケーションブロックサイズの倍数に切り上げられるという意味です。 ボリューム (およびアロケーションブロック) のサイズが大きくなるにつれ、割り当てられても未使用のまま残される領域の容量がだんだん多くなります。

一方、HFS Plus では 32 ビット値を使ってアロケーションブロックを識別します。 これにより、1 つのボリューム上に最大 2 ³²（4,294,967,296）までのアロケーションブロックを作成できるようになります。 特に 1GB またはそれ以上のサイズのボリュームで、アロケーションブロック数が多くなればなるほど、アロケーションブロックのサイズは小さくなると同時に、浪費される領域（フォークの末尾にある半端なアロケーションブロック。このようなアロケーションブロック全体は実際には使用されません）も少なくなります。 また、このことは、使用可能な領域を多数のファイルの間でより細かく分配できるようになるため、より多くのファイルをボリュームに格納できるということを意味します。 この変更は、ボリュームにサイズの小さなファイルが多数含まれる場合には特に役立ちます。

世界各国の言語に対応したファイル名

HFS では 31 バイトの文字列を使ってファイル名を格納します。 ファイル名とともに、ファイル名を解釈する方法を指定する何らかのスクリプト情報が格納されることはありません。 ファイル名は Roman スクリプトを前提とするルーチンを使って比較されてソートされます。 このため、Roman スクリプト以外のスクリプト（日本語など）を使用している名前の扱いが台なしになってしまいます。 しかも悪いことに、このアルゴリズムはバグだらけで、Roman スクリプトで使用する場合でさえ問題が起こります。 たとえば、Finder やその他のアプリケーションは、実行時に使用されているスクリプトに基づいてファイル名を解釈してしまいます。

HFS Plus では、最大 255 までの Unicode 文字を使ってファイル名を格納します。 ファイル名に 255 文字まで使用できるようになることで、内容を説明したわかりやすいファイル名を付けることが容易になります。 名前がコンピュータによって自動的に生成されるとき（Java のクラス名など）、長い名前は特に便利です。

HFS のカタログ B ツリーは 512 バイトのノードを使用します。 HFS Plus のファイル名は最大で 512 バイトまでを占有できます（長さフィールドを含めて）。 B ツリーのインデックスノードは少なくとも 2 つのキー（およびポインタとノードディスクリプタ）を格納する必要があるため、HFS Plus のカタログはより大きなノードサイズを使用する必要があります。 HFS Plus カタログ B ツリーの典型的なノードサイズは 4KB です。

HFS のカタログ B ツリーの場合、インデックスノードに格納されるキーは最大のキーサイズに対応する固定長の容量を常に占有します。 HFS Plus の場合、インデックスノードのキーは実際のキーのサイズによって決まる可変長の容量を占有します。 これにより、インデックスノード内の無駄な領域がなくなり、通常のディスクでは、ツリー内に効率のよい枝分かれ構造が作成されます（その結果、指定されたレコードを検出するために必要なノードアクセスの回数が少なくなります）。

将来計画されている名前付きフォークのサポート

HFS ボリューム上のファイルは、データフォークとリソースフォークという 2 つのフォークを持ち、これらのいずれかが空（長さがゼロ）であることもあります。 また、ファイルとディレクトリには、修正日や Finder 情報などの、ごくわずかな追加情報（カタログ情報またはメタデータと呼ばれます）が含まれます。

Apple のソフトウェアチームやサードパーティのデベロッパは、これまでしばしば、特定のファイルやディレクトリに関連する情報を格納しなければならないことがありました。 いくつかの場合では（たとえば、ファイルのカスタムアイコン）、データまたはリソースフォークが最適な格納場所になります。 しかし場合によっては（たとえば、ディレクトリのカスタムアイコン、あるいはファイル共有アクセスの特権）、データまたはリソースフォークを使用することが適切でなかったり、そもそも不可能なこともあります。

いくつかの製品には、ファイルおよびディレクトリ関連データを格納するための特殊用途のソリューションがインプリメントされています。 しかし、これらのソリューションはファイルシステムによって管理されていないため、ファイルおよびディレクトリ構造との間に不一致が発生する場合があります。

HFS Plus には、アトリビュートファイル、つまり、ファイルやディレクトリの追加情報を格納するために使用できる第 2 の B ツリーがあります。 このファイルはボリュームフォーマットの一部であるため、その情報は移動や名前の変更を行ってもファイルやディレクトリとともに保持され、ファイルやディレクトリを削除すると自動的に削除されます。 アトリビュートファイルのレコードの内容はまだ完全には定義されていませんが、最終的にはそれぞれのファイルやディレクトリに対応する任意の数のフォーク（Unicode 名によって識別される）を提供することになるはずです。

代替オペレーティングシステムの容易なスタートアップ

HFS Plus では特殊なスタートアップファイルが定義されています。これは、システムのスタートアップ時に容易に検出することのできる構造化されていないフォークです。 スタートアップファイルの保存場所とサイズはボリュームヘッダーに記述されています。 スタートアップファイルは、HFS または HFS Plus が ROM でサポートされていないシステムで特に役立ちます。 多くの点で、スタートアップファイルは HFS のブートブロックを一般化したもの、つまり、より大きな可変サイズの記憶容量を提供するブートブロックといえます。

先頭に戻る

コアとなる概念

HFS Plus は相互に関連するいくつかの構造を使って、ボリューム上のデータの構成を管理します。 これらの構造には次のものが含まれます。

• ボリュームヘッダー
• カタログファイル
• エクステントオーバーフローファイル
• アトリビュートファイル
• アロケーションファイル（ビットマップ）
• スタートアップファイル

これらの複雑な構造については、それぞれ独立したセクションで説明します。 このセクションでは、個別の構造の説明を始める前に、ボリュームフォーマットの概要を示し、それぞれの構造相互の関係を説明した上、HFS Plus によって使用されるプリミティブなデータ型を定義します。

用語の定義

HFS Plus は、ボリューム（ユーザデータおよびそのデータを取り出すための構造を含んだファイル）がディスク（ユーザデータが格納されるメディア）上にどのように存在するかを規定した仕様です。 ディスク上の記憶領域は、セクタと呼ばれる単位に分割されています。 セクタは、ディスクのドライバソフトウェアが 1 回の操作で（要求されたデータの前後に追加のデータの読み書きを行う必要なしに）読み取ったり書き込んだりするディスク領域の最小単位です。 通常、セクタのサイズは、データがディスク上に物理的に配置されている方法に基づいています。 ハードディスクでは、セクタは一般に 512 バイトです。 光メディアでは、セクタは一般に 2048 バイトです。

ジャーナルを除く HFS Plus ボリューム上の大半のデータ構造は、セクタのサイズに依存しません。 ジャーナルは、個々のセクタへのアクセスに依存するため、セクタのサイズはジャーナルヘッダーの jhdr_size フィールドに格納されます（ボリュームにジャーナルが存在する場合）。

HFS Plus は領域の割り当てを、アロケーションブロックと呼ばれる単位で行います。アロケーションブロックとは、連続するバイトを単純に 1 つのグループとしてまとめたものです。 1 つのアロケーションブロックのサイズ（バイト単位）は 512 以上の 2 のべき乗の値であり、ボリュームの初期化時に設定されます。 ボリュームを再初期化しないかぎり、この値を容易に変更することはできません。 アロケーションブロックは、32 ビットのアロケーションブロック番号によって識別されるため、ボリューム上には最大で 2³² 個のアロケーションブロックが存在できることになります。 ファイルシステムの現在のインプリメンテーションは、サイズが 4K のアロケーションブロックに最適化されています。

ボリュームヘッダーを含めて、これらのボリュームの構造はすべて 1 つまたは複数のアロケーションブロックの一部です（ただし、代替ボリュームヘッダーは該当しない場合があります。詳細は後述のとおりです）。 この点が HFS とは異なります。HFS には、どのアロケーションブロックにも属さないいくつかの構造（ブートブロック、マスターディレクトリブロック、ビットマップなど）が存在します。

ファイルの連続性を高めてフラグメンテーションを避けるため、通常、ディスク領域は複数のアロケーションブロックのグループであるファイル、つまりクランプに割り当てられます。 クランプのサイズは、必ずアロケーションブロックサイズの倍数です。 デフォルトのクランプサイズは、ボリュームヘッダーに指定されてます。

どの HFS Plus ボリュームもボリュームヘッダーを持っていなければなりません。 ボリュームヘッダーには、ボリュームの作成日時、ボリューム上にあるファイルの数、それにその他の重要な構造のボリューム上の位置など、ボリュームに関する雑多な情報が含まれています。 ボリュームヘッダーは、必ずボリュームの先頭から 1024 バイトの位置にあります。

代替ボリュームヘッダーと呼ばれるボリュームヘッダーのコピーは、ボリュームの末尾から 1024 バイトさかのぼった位置から始まる場所に格納されています。 ボリュームの先頭から 1024 バイト（ボリュームヘッダーの前）とボリュームの最後の 512 バイト（代替ボリュームヘッダーの後）は予約されています。 ボリュームヘッダー、代替ボリュームヘッダー、およびボリュームヘッダーと代替ボリュームヘッダーの前また後にある予約領域を含むアロケーションブロックはすべて、アロケーションファイルにおいて使用済みとしてマークされます。 このようにマークされたアロケーションブロックの実際の数は、アロケーションブロックサイズによって異なります。

1 つの HFS Plus ボリュームには 5 つの特殊ファイルが含まれており、これらの中にはフォルダ、ユーザファイル、属性といったファイルシステムの情報にアクセスするために必要なファイルシステム構造体が含まれています。 特殊ファイルとは、カタログファイル、エクステントオーバーフローファイル、アロケーションファイル、アトリビュートファイル、およびスタートアップファイルの 5 つです。 これらのファイルは単一のフォーク（データフォーク）のみを持ち、フォークのエクステントはボリュームヘッダー内に記述されています。

カタログファイルは、ボリューム上のフォルダとファイルの階層を記述する特殊ファイルです。 カタログファイルには、ボリューム上のすべてのファイルとフォルダに関する重要な情報と、カタログファイルに格納されているファイルとフォルダに対するカタログ情報が含まれています。 カタログファイルは、巨大なフォルダ階層の中をすばやくかつ効率的に検索できるように B ツリー（「バランスツリー」）として構成されています。

カタログファイルは、後述するように、ファイルとフォルダの名前を格納し、それらの名前は最大 255 文字までの Unicode 文字から構成されています。

アトリビュートファイルは、ファイルやフォルダの追加データを含むもう 1 つの特殊ファイルです。 カタログファイルと同様に、アトリビュートファイルも B ツリーとして構成されています。 将来、このファイルは追加フォークに関する情報の格納に使用される予定です （カタログファイルがファイルのデータフォークおよびリソースフォークに関する情報を格納する方法に似ています）。

HFS Plus では、フォークのエクステントのリストを保持することで、どのアロケーションブロックがそのフォークに属するかを追跡します。 エクステントとは、何らかのフォークに割り当てられたアロケーションブロックの連続する範囲のことで、先頭のアロケーションブロックの番号とアロケーションブロックの数という数値のペアによって表されます。 ユーザファイルの場合、それぞれのフォークの先頭から 8 つのエクステントはボリュームのカタログファイルに格納されます。 また、それ以上のエクステントはエクステントオーバーフローファイルに格納されます。なお、このファイルも B ツリーとして構成されています。

エクステントオーバーフローファイルは、自分自身を除く他の特殊ファイルの追加エクステントも格納します。 ただし、スタートアップファイルがボリュームヘッダーに 8 つを超えるエクステントを格納しなければならなくなると（その結果、エクステントオーバーフローファイルに追加エクステントを格納する必要があります）、アクセスが非常にむずかしくなり、スタートアップファイルの目的を果たさなくなってしまいます。 このため実際には、スタートアップファイルはエクステントオーバーフローファイルに追加エクステントを格納する必要がないように割り当てを行わなければなりません。

アロケーションファイルは、アロケーションブロックが使用済みであるかどうかを示す特殊ファイルです。 このファイルは、HFS ボリュームのビットマップと同じ役割を果たしますが、ファイルであることでボリュームフォーマットに柔軟性を与えられます。

スタートアップファイルは、非 Mac OS コンピュータを HFS Plus ボリュームからブートすることを可能にする別の特殊ファイルです。

最後に、不良ブロックファイルは、特定のアロケーションブロックを格納するメディアの一部に欠陥があるとき、ボリュームがそのアロケーションブロックを使用できないようにします。 不良ブロックファイルは特殊ファイルでもなければ、ユーザファイルでもありません。これは、エクステントオーバーフローファイルの中で使用される慣例にすぎません。 詳細については、「不良ブロックファイル」を参照してください。

幅広い構造

HFS Plus ボリュームの大半は 7 つのタイプの情報または領域から構成されています。

1. ユーザファイルフォーク
2. アロケーションファイル（ビットマップ）
3. カタログファイル
4. エクステントオーバーフローファイル
5. アトリビュートファイル
6. スタートアップファイル
7. 未使用領域

図 1 に、HFS Plus ボリュームの一般的な構造を示します。

図 1. HFS Plus ボリュームの構成

ボリュームヘッダーは、必ず固定の位置にあります（ボリュームの先頭から 1024 バイト）。 しかし、その他の特殊ファイルは、ボリュームヘッダーブロックと代替ボリュームヘッダーブロックに挟まれた任意の位置に現れます。 これらのファイルは任意の順序で現れ、必ずしも連続していません。

HFS Plus ボリューム上の情報はアロケーションブロックのみによって構成されます（ただし、代替ボリュームヘッダーは例外となる場合があります。詳細は後述します）。 アロケーションブロックはメディア上の領域を、より使いやすい区画にグループ化する手段にすぎません。 1 つのアロケーションブロックのサイズは 512 以上の 2 のべき乗値になります。 アロケーションブロックのサイズは、ボリュームヘッダーのパラメータの 1 つであり、その値はボリュームを初期化するときに設定されます。ボリュームの再初期化を行わないかぎり、この値は変更することはほとんど不可能です。

プリミティブなデータ型

このセクションでは、HFS Plus ボリュームで使用されるプリミティブなデータ型について説明します。 このボリュームで使用されるすべてのデータ型は C 言語で定義されています。 この仕様では、コンパイラがパディングフィールドを挿入しないことが前提になっています。 必要なパディングフィールドがあれば明示的に宣言されます。

予約されているフィールドとパディングフィールド

この仕様では、多くの場所でフィールドまたはフィールド内のビットを予約済みと記述しています。 この記述は、次のように明確に限定された意味を持ちます。

• 予約されたフィールドを含む構造体を作成するとき、インプリメンテーションではそのフィールドをゼロに設定する必要があります。
• 既存の構造体を読み込むとき、インプリメンテーションではそのフィールドに含まれる値を無視する必要があります。
• 予約されたフィールドを含む構造体を変更するとき、インプリメンテーションでは予約されているフィールドの値を維持する必要があります。

この定義により、ボリュームフォーマットに対する下位互換性が強化されます。

パディングフィールドも予約されているフィールドとまったく同じ意味を持ちます。 名前の違いは、インプリメンテーションの動作の違いを示すものではなく、設計者がフィールドを含めたときの意図を反映したものにすぎません。

整数型

すべての整数値は次のプリミティブなデータ型のいずれかによって定義されます。 UInt8、SInt8、UInt16、SInt16、UInt32、SInt32、UInt64、および SInt64 これらのデータ型は符号なし、および符号付き（2 の補数）の 8 ビット、16 ビット、32 ビット、および 64 ビットの数値を表します。

すべてのマルチバイト整数値はビッグエンディアン（Big-endian）フォーマットで格納されます。 つまり、各バイトは、ブロックの先頭からのオフセットが大きくなるのに応じて、最上位バイトから最下位バイトまでの順に格納されます。 ビットの番号は 0 から n-1となり（型が UIntn および SIntn として）、ビット 0 が最下位ビットとなります。

HFS Plus の名前

HFS Plus のファイルおよびフォルダ名は、HFSUniStr255 型によって定義される、長さを示す 16 ビットの値が先頭に付いた、最大 255 文字までの Unicode 文字から構成されます。

struct HFSUniStr255 {
    UInt16  length;
    UniChar unicode[255];
};
typedef struct HFSUniStr255 HFSUniStr255;
typedef const  HFSUniStr255 *ConstHFSUniStr255Param;

UniChar は、『The Unicode Standard, Version 2.0 [Unicode, Inc. ISBN 0-201-48345-9]』で定義されている Unicode 文字セットで定義された文字を表す UInt16 型の値です。

HFS Plus は完全に分解された文字列を標準的な順序で格納します。 HFS Plus は大小文字を区別せずに文字列を比較します。 文字列には Unicode 文字が含まれている場合があり、比較の際には無視する必要があります。 これらの問題の詳細については、「Unicode に関する微妙な問題」を参照してください。

HFS Plus のバリエーションである HFSX では、名前の大文字小文字が区別されるボリュームを持つことが可能です。 名前は完全に分解され、標準的な順序となっていますが、比較の際に Unicode 文字列は無視されません。

テキストエンコーディング

従来の Mac OS プログラミングインタフェースはファイル名を Pascal 文字列として渡します（StringPtr または FSSpec に埋め込まれた Str63 として）。 このような文字列に含まれる文字は Unicode ではありません。エンコーディングは、システムソフトウェアがローカライズされた方法とインストールされているランゲージキットによって異なります。 このため、同一のバイトのシーケンスがまったく異なる Unicode 文字のシーケンスを表すことがあります。 同様に、多くの Unicode 文字が複数の Mac OS テキストエンコーディングに属しています。

HFS Plus には、特に Mac OS エンコーディングの Pascal 文字列と Unicode との間の Mac OS での変換を支援するために設計された 2 つの機能が用意されています。 第 1 の機能は、ファイルおよびフォルダのカタログレコードに含まれる textEncoding フィールドです。 このフィールドは、レコードの Unicode 名を Mac OS エンコーディングの Pascal 文字列に変換するときに使用するヒントとして定義されています。

表 2 に、textEncoding フィールドに設定できる有効な値の定義を示します。

表 2 テキストエンコーディング

HFS Plus のテキストエンコーディングを支援する第 2 の機能はボリュームヘッダーの encodingsBitmap フィールドです。 ボリューム上のカタログノードで使用される各エンコーディングに対して、encodingsBitmap フィールドの対応するビットがセットされていなければなりません。

逆に、ボリューム上のどの名前にも特定のエンコーディングが使用されていないときに、そのエンコーディングに対応するビットがビットマップの中でセットされていても構いません。 これは、インプリメンテーションがオブジェクトの削除または名前変更を行うとき、それが特定のエンコーディングを使用する最後の名前であった場合にも、そのエンコーディングビットをクリアする必要がないということを意味します。

HFS Plus の日付

HFS Plus は日付をボリュームヘッダーやカタログレコードなどのいくつかのデータ構造に格納します。 これらの日付は、1904 年 1 月 1 日（GMT）の午前 0 時から経過した秒数を含んだ符号なし 32 ビット整数（UInt32）として格納されます。 この点は、値が地方時を表す HFS と若干異なります。

表現可能な最大の日付は 2040 年 2 月 6 日の 6 時 28 分 15 秒（GMT）です。

この日付値はうるう秒が計算に入っていません。 その代わりに、毎年、4 等分したうるう日が日付に組み込まれます。 表現可能な日付の範囲に、うるう日を持たない 1900 年または 2100 年が含まれていないので、これでも十分役割を果たします。

クライアントソフトウェアが想定しているフォーマットへの日付と時刻の変換は、それぞれのインプリメンテーションに任されています。 たとえば、Mac OS の File Manager は日付を地方時で渡します。そして、Mac OS HFS Plus のインプリメンテーションはその地方時と GMT との間で日付の変換を適切に行います。

HFS Plus のアクセス権

それぞれのファイルやフォルダについて、HFS Plus は HFSPlusBSDInfo 構造体によって定義されたアクセス権を含むレコードを保持します。

struct HFSPlusBSDInfo {
    UInt32  ownerID;
    UInt32  groupID;
    UInt8   adminFlags;
    UInt8   ownerFlags;
    UInt16  fileMode;
    union {
        UInt32  iNodeNum;
        UInt32  linkCount;
        UInt32  rawDevice;
    } special;
};
typedef struct HFSPlusBSDInfo HFSPlusBSDInfo;

それぞれのフィールドは次のような意味を持ちます。

ownerID

ファイルまたはフォルダの所有者の Mac OS X ユーザ ID。 バージョン 10.3 以前の Mac OS X では、ユーザ ID 99 は、現在コンソールにログインしているユーザの ID として扱われます。 コンソールにログインしているユーザがいなければ、ユーザ ID 99 はユーザ ID 0（root）として扱われます。 Mac OS X バージョン 10.3 では、ユーザ ID 99 は、呼び出しを行っているユーザの ID として扱われます（その結果、同時に全員が所有者となります）。 これらの置き換えは実行時に行われます。 ディスク上の実際のユーザ ID は変わりません。

groupID

ファイルまたはフォルダに関連付けられているグループの Mac OS X グループ ID。 通常、Mac OS X では、グループ ID 99 は「unknown」という名前のグループに割り当てられます。 Mac OS X では、実行時のグループ ID の置き換えはありません。

adminFlags

スーパーユーザのみが設定可能な BSD フラグ群。 このフィールドは、Mac OS X の struct stat の st_flags フィールドの 16 ビット目から 23 ビット目までに対応します。 詳細については、chflags(2) のマニュアルページを参照してください。 次の表は、adminFlags フィールド内のビット位置と、st_flags フィールドで使用される対応するマスクの名前を示します。

ビット	st_flags のマスク	意味
0	SF_ARCHIVED	ファイルはアーカイブ済み
1	SF_IMMUTABLE	ファイルは変更不可
2	SF_APPEND	ファイルへの書き込みは追加のみ可

ownerFlags

ファイルまたはディレクトリの所有者またはスーパーユーザが設定可能な BSD フラグ群。 このフィールドは、Mac OS X の struct stat の st_flags フィールドの 0 ビット目から 7 ビット目までに対応します。 詳細については、chflags(2) のマニュアルページを参照してください。 次の表は、ownerFlags フィールド内のビット位置と、st_flags フィールドで使用される対応するマスクの名前を示します。

ビット	st_flags のマスク	意味
0	UF_NODUMP	このファイルをダンプ（バックアップまたはアーカイブ）しない
1	UF_IMMUTABLE	ファイルは変更不可
2	UF_APPEND	ファイルへの書き込みは追加のみ可
3	UF_OPAQUE	ディレクトリは不透過（後述を参照）

fileMode

BSD のファイルタイプとモードビット群。 以下に示すヘッダーから抜粋した定数は、16 進数ではなく 8 進数である点に注意してください。

#define S_ISUID 0004000 /* 実行時にユーザ ID をセット */ #define S_ISGID 0002000 /* 実行時にグループ ID をセット */ #define S_ISTXT 0001000 /* スティッキービット */ #define S_IRWXU 0000700 /* 所有者の RWX マスク */ #define S_IRUSR 0000400 /* 所有者の R マスク */ #define S_IWUSR 0000200 /* 所有者の W マスク */ #define S_IXUSR 0000100 /* 所有者の X マスク */ #define S_IRWXG 0000070 /* グループの RWX マスク */ #define S_IRGRP 0000040 /* グループの R マスク */ #define S_IWGRP 0000020 /* グループの W マスク */ #define S_IXGRP 0000010 /* グループの X マスク */ #define S_IRWXO 0000007 /* その他のユーザの RWX マスク */ #define S_IROTH 0000004 /* その他のユーザの R マスク */ #define S_IWOTH 0000002 /* その他のユーザの W マスク */ #define S_IXOTH 0000001 /* その他のユーザの X マスク */ #define S_IFMT 0170000 /* ファイルマスクのタイプ */ #define S_IFIFO 0010000 /* 名前付きパイプ（fifo） */ #define S_IFCHR 0020000 /* キャラクタ特殊 */ #define S_IFDIR 0040000 /* ディレクトリ */ #define S_IFBLK 0060000 /* ブロック特殊 */ #define S_IFREG 0100000 /* 通常 */ #define S_IFLNK 0120000 /* シンボリックリンク */ #define S_IFSOCK 0140000 /* ソケット */ #define S_IFWHT 0160000 /* ホワイトアウト */

UNIX のいくつかのバージョンでは、スティッキービットの S_ISTXT を使用して、実行可能ファイルの終了後もファイルのコードをメモリ内に残すことを示します。これは、同じ実行可能ファイルがまたすぐに使用される場合にパフォーマンスの向上に寄与します。 Mac OS X はこの最適化機能を使用しません。 ディレクトリのスティッキービットがセットされている場合、Mac OS X では、当該ディレクトリ内のファイルの移動、削除、名前の変更を制限します。 ファイルは、削除を行うユーザがファイルが格納されているディレクトリに対する書き込み権限があり、ファイルまたはディレクトリの所有者である場合、またはスーパーユーザである場合に削除できます。

special

このフィールドは、特別な種類のファイルの場合にのみ使用されます。 ディレクトリおよび大半のファイルではこのフィールドは使用されず、予約済みです。 使用されている場合、このフィールドは次のいずれかとして使用されます。

iNodeNum

ハードリンクファイルの場合、このフィールドにはリンク参照番号が格納されます。 詳細については、「ハードリンク」のセクションを参照してください。

linkCount

間接ノードファイルの場合、このフィールドには当該ノードファイルを指すハードリンクの数が格納されます。 詳細については、「ハードリンク」のセクションを参照してください。

rawDevice

ブロック型特殊デバイスファイルおよびキャラクタ型特殊デバイスファイルの場合（S_IFMT フィールドに S_IFCHR または S_IFBLK が格納されている場合）、このフィールドにはデバイス番号が格納されます。

フォークデータ構造体

HFS Plus は HFSPlusForkData 構造体を使ってファイルの内容に関する情報を保持します。 このような構造体が 2 つ（1 つはリソースフォークに対応するもので、もう 1 つはデータフォークに対応するもの）が各ユーザファイルに対するカタログレコードに格納されています。 また、ボリュームヘッダーには、それぞれの特殊ファイルに対するフォークデータ構造体が含まれます。

エクステントレコードに含まれる未使用のエクステント記述子は、startBlock および blockCount の両方がゼロに設定されます。 たとえば、対象となるフォークが 3 つのエクステントを占有している場合、最後の 5 つのエクステント記述子はすべてゼロになります。

struct HFSPlusForkData {
    UInt64                  logicalSize;
    UInt32                  clumpSize;
    UInt32                  totalBlocks;
    HFSPlusExtentRecord     extents;
};
typedef struct HFSPlusForkData HFSPlusForkData;
 
typedef HFSPlusExtentDescriptor HFSPlusExtentRecord[8];

それぞれのフィールドは次のような意味を持ちます。

logicalSize

フォークに含まれる有効なデータのサイズ（バイト単位）。

clumpSize

ボリュームヘッダーに含まれる HFSPlusForkData 構造体においては、これはフォークのクランプサイズです。このサイズは、ボリュームヘッダー内のデフォルトのクランプサイズに優先して使用されます。

カタログレコードに含まれる HFSPlusForkData 構造体においては、このフィールドはボリュームヘッダー内のデフォルトのクランプサイズに優先するフォークごとのクランプサイズを格納することを目的としていました。 しかし、Mac OS X バージョン 10.3 以前のアップルのインプリメンテーションではこのフィールドを無視していました。 Mac OS X バージョン 10.3 からは、このフィールドはフォークから実際に読み取ったブロックの数を記録するために使用されています。 詳細については、「ホットファイル」のセクションを参照してください。

totalBlocks

対象となるフォークのすべてのエクステントで使用されるアロケーションブロックの総数。

extents

フォークのエクステント記述子の配列。 この配列には、先頭から 8 つのエクステント記述子が保持されます。 それを超えるエクステント記述子が必要な場合、それらはエクステントオーバーフローファイルに格納されます。

HFSPlusExtentDescriptor 構造体は個々のエクステントに関する情報を保持するために使用されます。

struct HFSPlusExtentDescriptor {
    UInt32                  startBlock;
    UInt32                  blockCount;
};
typedef struct HFSPlusExtentDescriptor HFSPlusExtentDescriptor;

それぞれのフィールドは次のような意味を持ちます。

startBlock

エクステント内の先頭のアロケーションブロック。

blockCount

アロケーションブロック単位で表したエクステントの長さ。

先頭に戻る

ボリュームヘッダー

各 HFS Plus ボリュームには、ボリュームの先頭から 1024 バイトの位置にボリュームヘッダーがあります。 HFS のマスターディレクトリブロック（MDB）に相当するボリュームヘッダーには、ボリューム内のその他の重要な構造の位置など、ボリューム全体に関する情報が含まれます。 インプリメンテーションでは、ボリュームがアンマウントされる前に必ずこの構造を更新する必要があります。

ボリュームヘッダーのコピーである代替ボリュームヘッダーは、ボリュームの末尾から 1024 バイトさかのぼった位置から始まる場所に格納されています。 インプリメンテーションでは、いずれかの特殊ファイルの長さまたは場所が変更されたときにだけこのコピーを更新する必要があります。 代替ボリュームヘッダーは、もっぱらディスク修復ユーティリティで使用することを前提にしています。

ボリュームの最初の 1024 バイトおよび最後の 512 バイトは予約されています。

最初の 1536 バイト（予約済みにボリュームヘッダーを加えた量）を含むアロケーションブロック（1 つまたは複数）は、アロケーションファイルの中で「使用済み」としてマークされています（詳細については、「アロケーションファイル」のセクションを参照してください）。 また、代替ボリュームヘッダーとそれに続く予約済みの領域に対応するために、最後のアロケーションブロック（または、ボリュームが 512 バイト単位のアロケーションブロックを使用してフォーマットされている場合には 2 つのアロケーションブロック）もアロケーションファイルにおいて使用中として印がつけられます。

ボリュームヘッダーは HFSPlusVolumeHeader 型によって記述されます。

struct HFSPlusVolumeHeader {
    UInt16              signature;
    UInt16              version;
    UInt32              attributes;
    UInt32              lastMountedVersion;
    UInt32              journalInfoBlock;
 
    UInt32              createDate;
    UInt32              modifyDate;
    UInt32              backupDate;
    UInt32              checkedDate;
 
    UInt32              fileCount;
    UInt32              folderCount;
 
    UInt32              blockSize;
    UInt32                  totalBlocks;
    UInt32              freeBlocks;
 
    UInt32              nextAllocation;
    UInt32              rsrcClumpSize;
    UInt32              dataClumpSize;
    HFSCatalogNodeID    nextCatalogID;
 
    UInt32              writeCount;
    UInt64              encodingsBitmap;
 
    UInt32              finderInfo[8];
 
    HFSPlusForkData     allocationFile;
    HFSPlusForkData     extentsFile;
    HFSPlusForkData     catalogFile;
    HFSPlusForkData     attributesFile;
    HFSPlusForkData     startupFile;
};
typedef struct HFSPlusVolumeHeader HFSPlusVolumeHeader;

それぞれのフィールドは次のような意味を持ちます。

signature

ボリュームシグネチャ。これは、HFS Plus ボリュームに対しては kHFSPlusSigWord（'H+'）、HFSX ボリュームに対しては kHFSXSigWord（'HX'）でなければなりません。

version

ボリュームフォーマットのバージョン。現在のバージョンは、HFS Plus ボリュームに対しては 4（kHFSPlusVersion）、HFSX ボリュームに対しては 5（kHFSXVersion）となっています。

attributes

後述するボリューム属性。

lastMountedVersion

書き込みを行うためにこのボリュームを最後にマウントしたインプリメンテーションを一意に識別する値。 この値は、将来のインプリメンテーションにおいて、古いインプリメンテーションによって最後にマウントされたボリュームを検出して、問題がないかどうかをチェックするために使用できます。 オンディスク構造に変更を加えるコードは、このフィールドにコードを識別する一意の値にセットする必要もあります。 サードパーティによる HFS Plus のインプリメンテーションでは、このフィールドに登録されているクリエータコードを格納してください。 Mac OS 8.1から 9.2.2 にかけて使用されている値は '8.10' です。 Mac OS X によって使用される値は '10.0' です。 Mac OS X において、ジャーナルボリューム（HFSX を含む）によって使用される値は 'HFSJ' です。 Mac OS X 上で fsck_hfs によって使用される値は 'fsck' です。

journalInfoBlock

ボリュームのジャーナルに対する JournalInfoBlock が格納されいているアロケーションブロックのアロケーションブロック番号。 このフィールドは、attribute フィールドの kHFSVolumeJournaledBit がセットされている場合にのみ有効です。それ以外の場合、このフィールドは予約済みとなります。

createDate

ボリュームが作成された日付と時刻。 フォーマットの詳細については、「HFS Plus の日付」を参照してください。

modifyDate

ボリュームが最後に修正された日付と時刻。 フォーマットの詳細については、「HFS Plus の日付」を参照してください。

backupDate

ボリュームが最後にバックアップされた日付と時刻。 ボリュームフォーマットにおいては、このフィールドに対して特に何もする必要はありません。このフィールドは、ユーザプログラムの便宜を図る目的でのみ定義されています。 フォーマットの詳細については、「HFS Plus の日付」を参照してください。

checkedDate

ボリュームの一貫性が最後にチェックされた日付と時刻。 Disk First Aid などのディスクチェックツールでは、ディスクチェックを実行したときにこのフィールドをセットする必要があります。 ディスクチェックツールは、この日付に基づいて、定期的なボリュームのチェックを実行することが可能です。

fileCount

ボリューム上にあるファイルの総数。 fileCount フィールドの値に特殊ファイルは含まれません。 この値は、カタログファイルに記録されているファイルレコードの数と同じはずです。

folderCount

ボリューム上にあるフォルダの総数。 folderCount フィールドの値にはルートフォルダは含まれません。 この値は、カタログファイルに記録されているフォルダレコードの数から 1 を引いた数と同じはずです（カタログファイルのフォルダレコードにはルートフォルダも含まれているため）。

blockSize

アロケーションブロックサイズ（バイト単位）。

totalBlocks

ディスク上にあるアロケーションブロックの総数。 サイズがアロケーションブロックサイズの偶数倍であるディスクの場合、ボリュームヘッダーと代替ボリュームヘッダーを含めて、ディスク上のすべての領域がアロケーションブロックに組み込まれます。 ディスクのサイズが、アロケーションブロックサイズの偶数倍でない場合、全体がディスクに収まるアロケーションブロックのみが数えられます。 ディスク末尾の残余領域はボリュームフォーマットでは使用されません（前述のように、代替ボリュームヘッダーの格納に使用する場合を除きます）。

freeBlocks

ディスク上にある未使用のアロケーションブロックの総数。

nextAllocation

次のアロケーション検索の開始点。 nextAllocation フィールドは、ファイルの領域を割り当てるときに空きアロケーションブロックの検索を開始する場所のヒントとして Mac OS によって使用されます。 このフィールドには、検索を開始することになるアロケーションブロック番号が含まれます。 この種のヒントを必要としないインプリメンテーションでは、このフィールドを予約済みとして扱うこともできます。 [インプリメンテーション詳細： 従来の Mac OS のインプリメンテーションでは、通常、このフィールドに最も最近割り当てられたエクステントの先頭のアロケーションブロックをセットしていました。 最も最近割り当てられたエクステントの直後にあるアロケーションブロックがこのフィールドにセットされることはありません。というのも、ファイルがクローズされるときにそのエクステントが短縮される可能性があるためです（クランプ全体が割り当てられていても、実際に使用されていないこともあるため）。］ 詳細については、「アロケーションファイル」のセクションを参照してください。

rsrcClumpSize

リソースフォークのデフォルトのクランプサイズ（バイト単位）。 これは、サイズが大きくなっているファイルをどこまで拡張するかをインプリメンテーションに対して示すヒントとなります。 現在までのアップルのインプリメンテーションは、データフォークとリソースフォークのどちらについても、rsrcClumpSize を無視し、dataClumpSize を使用します。

dataClumpSize

データフォークのデフォルトのクランプサイズ（バイト単位）。 これは、サイズが大きくなっているファイルをどこまで拡張するかをインプリメンテーションに対して示すヒントとなります。 現在までのアップルのインプリメンテーションは、データフォークとリソースフォークのどちらについても、rsrcClumpSize を無視し、dataClumpSize を使用します。

nextCatalogID

使用されていない次のカタログ ID。 カタログ ID の詳細については、「カタログファイル」を参照してください。

writeCount

このフィールドはボリュームがマウントされるたびに増加していきます。 このフィールドを使用することで、インプリメンテーションはメディアが取り出された（あるいは何らかの理由でアクセスできない）場合でも、ボリュームをマウントし続けることができます。 メディアが再度挿入されたとき、インプリメンテーションはこのフィールドをチェックして、取り出されていた間にメディアが変更されたかどうかを判断できます。 ボリュームの構造を直接的に変更した場合、インプリメンテーションまたはユーティリティは writeCount フィールドを変更する必要があります。 このことは、ボリューム上の項目を追加または削除した場合には特に重要になります。

encodingsBitmap

このフィールドは、ボリューム上のファイルおよびフォルダの名前に使用されているテキストエンコーディングを追跡します。 このビットマップにより、Unicode 名を直接的に使用しないインプリメンテーションのパフォーマンスを部分的に最適化することができます。 詳細については、「テキストエンコーディング」のセクションを参照してください。

finderInfo

32 ビットの項目で構成されるこの配列には、Mac OS の Finder およびシステムソフトウェアのブートプロセスによって使用される情報が格納されています。

finderInfo[0] には、ブート可能システムが格納されているディレクトリ（Mac OS 8 または 9 における「システムフォルダ」、あるいは、Mac OS X における /System/Library/CoreServices など）のディレクトリ ID が格納されています。 ボリューム上にブート可能なシステムがない場合にはゼロとなります。 この値は通常、finderInfo[3] または finderInfo[5] と同じです。

finderInfo[1] には、スタートアップアプリケーション（Finder など）の親ディレクトリの ID、または、ボリュームがブート可能でない場合はゼロが格納されています。

finderInfo[2] には、ボリュームがマウントされたときに Finder に表示するディレクトリのディレクトリ ID、または、ディレクトリウィンドウを開かない場合にはゼロが格納されています。 従来の Mac OS では、このウィンドウは、開く対象となるウィンドウのリンクリストの最初のウィンドウです。ディレクトリの Finder 情報の frOpenChain フィールドに、リスト内の次のディレクトリの ID が格納されています。 オープンウィンドウリストは使用が廃止されました。 Mac OS X の Finder はこのディレクトリのウィンドウを開きますが、オープンウィンドウリストの残りは無視します。 Mac OS X の Finder はこのフィールドを変更しません。

finderInfo[3] には、ブート可能な Mac OS 8 または 9 の「システムフォルダ」のディレクトリ ID、または、なければゼロが格納されています。

finderInfo[4] は予約済みです。

finderInfo[5] には、ブート可能な Mac OS X システム（/System/Library/CoreServices ディレクトリ）のディレクトリ ID、または、ボリューム上にブート可能な Mac OS X システムがなければゼロが格納されています。

finderInfo[6] および finderInfo[7] は、64 ビットの一意のボリューム識別子を格納するために Mac OS X によって使用されます。 この識別子の 1 つの使い方は、ボリュームの所有権（ユーザ ID）情報を尊重するかどうかを追跡することです。 これらの要素は、ボリュームに対して識別子が作成されていなければゼロとなります。

allocationFile

アロケーションファイルの位置とサイズに関する情報。 HFSPlusForkData 型の詳細については、「フォークデータ構造体」を参照してください。

extentsFile

エクステントファイルの位置とサイズに関する情報。 HFSPlusForkData 型の詳細については、「フォークデータ構造体」を参照してください。

catalogFile

カタログファイルの位置とサイズに関する情報。 HFSPlusForkData 型の詳細については、「フォークデータ構造体」を参照してください。

attributesFile

アトリビュートファイルの位置とサイズに関する情報。 HFSPlusForkData 型の詳細については、「フォークデータ構造体」を参照してください。

startupFile

スタートアップファイルの位置とサイズに関する情報。 HFSPlusForkData 型の詳細については、「フォークデータ構造体」を参照してください。

ボリューム属性

ボリュームヘッダーの attributes フィールドは 1 ビットフラグの集合として扱われます。 各ビットの定義は以下に示す定数によって与えられます。

enum {
    /* ビット 0〜6 は予約されている */
    kHFSVolumeHardwareLockBit       =  7,
    kHFSVolumeUnmountedBit          =  8,
    kHFSVolumeSparedBlocksBit       =  9,
    kHFSVolumeNoCacheRequiredBit    = 10,
    kHFSBootVolumeInconsistentBit   = 11,
    kHFSCatalogNodeIDsReusedBit     = 12,
    kHFSVolumeJournaledBit          = 13,
    /* ビット 14 は予約されている */
    kHFSVolumeSoftwareLockBit       = 15
    /* ビット 16〜31 は予約されている */
};

それぞれのビットは次のような意味を持ちます。

ビット 0-7

インプリメンテーションでは、これらのビットを予約済みとして扱う必要があります。

kHFSVolumeUnmountedBit（ビット 8）

このビットは、アンマウントまたは取り出しの前にボリュームが正しくフラッシュされた場合にセットします。 インプリメンテーションでは、書き込みを行うためにボリュームをマウントするとき、メディア上のこのビットをクリアする必要があります。 また、他のすべてのボリューム情報をフラッシュした後で、書き込み可能ボリュームをアンマウントする最後のステップとして、メディア上のこのビットをセットする必要があります。 このビットがクリアされているボリュームのマウントを要求された場合、インプリメンテーションはそのボリュームの一貫性に問題があるとみなし、そのボリュームを使用する前に適切な一貫性チェックを実行しなければなりません。

kHFSVolumeSparedBlocksBit（ビット 9）

このビットは、エクステントオーバーフローファイルの中に不良ブロック（ファイル ID IDkHFSBadBlockFileID に属する）に関する何らかのレコードが含まれている場合にセットします。 詳細については、「不良ブロックファイル」を参照してください。

kHFSVolumeNoCacheRequiredBit（ビット 10）

このビットは、このボリュームのブロックのキャッシュを行う必要がない場合にセットします。 たとえば、RAM または ROM ディスクは実際にはメモリ内に格納されているので、ボリュームの内容をキャッシュするために追加のメモリを使用するのは無駄です。

kHFSBootVolumeInconsistentBit（ビット 11）

このビットは kHFSVolumeUnmountedBit に似ていますが、意味が逆になります。 インプリメンテーションでは、書き込みを行うためにボリュームをマウントするとき、メディア上のこのビットをセットする必要があります。 また、他のすべてのボリューム情報をフラッシュした後で、書き込み可能ボリュームをアンマウントする最後のステップとして、メディア上のこのビットをクリアする必要があります。 このビットがセットされているボリュームのマウントを要求された場合、インプリメンテーションはそのボリュームの一貫性に問題があるとみなし、そのボリュームを使用する前に適切な一貫性チェックを実行しなければなりません。

kHFSCatalogNodeIDsReusedBit（ビット 12）

このビットは、nextCatalogID フィールドが 32 ビットを超え、より小さなカタログノード ID を再利用する必要がある場合にセットします。 このビットがセットされている場合、nextCatalogID と同じまたはそれよりも大きい ID を持つカタログレコードが存在するのが一般的です（エラーではありません）。 このビットがセットされている場合、新規作成されるカタログレコードに割り当てる ID が既存のレコードで使用されている ID と重複しないようにする必要があります。

kHFSVolumeJournaledBit（ビット 13）

このビットがセットされている場合、当該ボリュームにはジャーナルがあります。ジャーナルは、ボリュームヘッダーの journalInfoBlock フィールドを使用して場所を知ることができます。

第 14 ビット

インプリメンテーションでは、このビットを予約済みとして扱う必要があります。

kHFSVolumeSoftwareLockBit（ビット 15）

このビットは、ソフトウェアの設定によってボリュームが書き込み保護されている場合にセットされます。 このビットがセットされている場合、インプリメンテーションではボリュームへの書き込みを拒否する必要があります。 このフラグは、他の方法では書き込み禁止にできないメディア上のボリュームを保護したり、パーティションに分割されたデバイス上の個別のパーティションを保護するときに特に役立ちます。

第 16 〜 31 ビット

インプリメンテーションでは、これらのビットを予約済みとして扱う必要があります。

先頭に戻る

B ツリー

このセクションでは、カタログファイル、エクステントオーバーフローファイル、およびアトリビュートファイルに使用されている B ツリーの構造について説明します。 B ツリーはファイルのデータフォークに格納されています。 それぞれの B ツリーは、ボリュームヘッダーの中に、そのデータフォークのサイズとエクステントの初期値を記述する HFSPlusForkData 構造体を持ちます。

B ツリーファイルは複数の固定長ノードに分割されます。それぞれのノードには複数のレコードが含まれ、それらのレコードは 1 つのキーといくらかのデータで構成されます。 B ツリーの目的は、あるキーをそれに対応するデータに効率的にマップすることです。 これを実現するためは、キーに何らかの順列がなければなりません。つまり、あるキーを別のキーと比較して、小さいか、等しいか、大きいかを判定できる厳密に定義された方法が存在する必要があるということです。

ノードのサイズ（バイト単位で表される）は、512 から 32,768 までの範囲の 2 のべき乗値でなければなりません。 B ツリーのノードサイズは、B ツリーの作成時に決まります。 B ツリーファイルの論理長は、ノードの数とノードサイズを掛け合わせた値になります。

次のような 4 種類のノードがあります。

• それぞれの B ツリーには 1 つのヘッダーノードが含まれています。 ヘッダーノードは常に B ツリー内の先頭ノードです。 このノードには、ツリー内の他のノードを検索するときに必要な情報が含まれています。
• マップノードにはマップレコードが含まれます。マップレコードには、ヘッダーノードのマップレコードに収まりきらないアロケーションデータ（B ツリー内の空きノードを示すビットマップ）が格納されます。
• インデックスノードには B ツリーの構造を定義するポインタレコードが含まれます。
• リーフノードには、キーに関連付けられているデータを含むデータレコードが格納されます。 各データレコードに対応するキーは一意でなければなりません。

すべてのノードは、次のセクションで説明する共通の構造を持っています。

ノードの構造

ノードは番号によって指定されます。 ノードの番号は、そのノードのファイル内でのオフセット値をノードサイズで割って求めることができます。 それぞれのノードは同一の一般構造を持ちます。つまり、1 つのノードは、ノードの先頭にあるノード記述子、ノードの最後にあるレコードオフセットのリスト、およびレコードのリストという 3 つの主要部分から構成されます。 図 2 に、この構造を示します。

図 2. ノードの構造

ノード記述子には、ノードに関する基本的な情報と、他のノードとの相互リンクが含まれます。 BTNodeDescriptor データ型がこの構造を表します。

struct BTNodeDescriptor {
    UInt32    fLink;
    UInt32    bLink;
    SInt8     kind;
    UInt8     height;
    UInt16    numRecords;
    UInt16    reserved;
};
typedef struct BTNodeDescriptor BTNodeDescriptor;

それぞれのフィールドは次のような意味を持ちます。

fLink

同じタイプの次のノードのノード番号。 最後のノードの場合は 0。

bLink

同じタイプの前のノードのノード番号。 先頭のノードの場合は 0。

kind

ノードのタイプ。 4 種類のノード（ヘッダーノード、マップノード、インデックスノード、リーフノード）がありますが、詳細については後述します。

height

B ツリーの階層内での対象となるノードのレベルまたは深さ。 ヘッダーノードの場合、このフィールドはゼロでなければなりません。 リーフノードの場合、このフィールドは 1 でなければなりません。 インデックスノードの場合、このフィールドはそれがポイントする子ノードのレベルよりも 1 大きくなります。 マップノードのレベルはヘッダーノードと同様にゼロになります （マップノードはヘッダーノード内のマップレコードを拡張したものと考えてください）。

numRecords

対象となるノードに含まれるレコードの数。

reserved

インプリメンテーションでは、これを予約済みのフィールドとして扱う必要があります。

ノード記述子は常に 14 バイト（sizeof(BTNodeDescriptor)）の長さを持ちます。このため、ノードに含まれるレコードのリストは、常にノードの先頭から 14 バイト目から始まります。 各レコードのサイズはレコードのタイプとそれに含まれる情報の量によって変わります。

それぞれのレコードは、ノードの末尾にあるレコードのオフセットのリストを使ってアクセスされます。 このリストの各エントリは、ノードの先頭からレコードの先頭までのオフセット値（バイト単位）を含む UInt16 型の値です。 それぞれのオフセットは逆順に格納されています。つまり、先頭のレコードのオフセットはノードの最後の 2 バイトに格納され、2 番目のレコードのオフセットはその前の 2 バイトに格納されます。 先頭のレコードのオフセットは常に 14 であるため、ノードの最後の 2 バイトには 14 という値が含まれることになります。

ノード記述子の kind フィールドはノードのタイプを記述します。これにより、そのノードにどのような種類のレコードが含まれているかがわかり、B ツリーの階層内でのそのノードの目的も明らかになります。 ノードには、次の定数で指定される 4 つのタイプがあります。

enum {
    kBTLeafNode       = -1,
    kBTIndexNode      =  0,
    kBTHeaderNode     =  1,
    kBTMapNode        =  2
};

B ツリーのノードタイプによりそのノードに含まれるレコードのタイプが決まるということを十分に認識しておく必要があります。 リーフノードには常にデータレコードが含まれます。 インデックスノードには常にポインタレコードが含まれます。 マップノードには常にマップレコードが含まれます。 また、ヘッダーレコードには常にヘッダーレコード、予約されているレコード、およびマップレコードが含まれます。 以下のセクションでは、4 つのノードタイプと、それらに対応するレコードについて説明します。

ヘッダーノード

どの B ツリーファイルでも、その先頭ノード（ノード 0）はヘッダーノードです。ヘッダーノードには、B ツリーファイル全体に関する重要情報が含まれます。 ヘッダーレコードの中には 3 つのレコードが存在します。 先頭のレコードは B ツリーヘッダーレコードで、2 番目のレコードは常に 128 バイト長のユーザデータレコードです。 また、最後のレコードは B ツリーマップレコードで、ユーザデータレコードとレコードオフセットの間にある残りの領域すべてを占有します。 図 3 にヘッダーノードの構造を示します。

図 3 ヘッダーノードの構造

ヘッダーノードのノード記述子に含まれる fLink フィールドには、先頭のマップノードのノード番号が含まれます。また、マップノードがない場合は 0 が含まれます。 ヘッダーノードのノード記述子に含まれる bLink フィールドは常にゼロに設定されていなければなりません。

ヘッダーレコード

B ツリーヘッダーレコードには、B ツリーのサイズ、最大のキー長、先頭および最後のリーフノードの位置など、B ツリーに関する一般的な情報が含まれています。 BTHeaderRec データ型がヘッダーレコードの構造を表します。

struct BTHeaderRec {
    UInt16    treeDepth;
    UInt32    rootNode;
    UInt32    leafRecords;
    UInt32    firstLeafNode;
    UInt32    lastLeafNode;
    UInt16    nodeSize;
    UInt16    maxKeyLength;
    UInt32    totalNodes;
    UInt32    freeNodes;
    UInt16    reserved1;
    UInt32    clumpSize;      // misaligned
    UInt8     btreeType;
    UInt8     keyCompareType;
    UInt32    attributes;     // long aligned again
    UInt32    reserved3[16];
};
typedef struct BTHeaderRec BTHeaderRec;

それぞれのフィールドは次のような意味を持ちます。

treeDepth

B ツリーの現在のレベル。 常に、ルートノードの height フィールドと等しくなります。

rootNode

ルートノード、つまり、B ツリーのルートとして動作するインデックスノードのノード番号。 詳細については、「インデックスノード」を参照してください。 rootNode がリーフノードである可能性もあります。 詳細については、「Inside Macintosh: Files」の 2-69 ページを参照してください。

leafRecords

すべてのリーフノードに含まれるレコードの総数。

firstLeafNode

先頭にあるリーフノードのノード番号。 リーフノードが存在しない場合、このフィールドの値はゼロになります。

lastLeafNode

末尾にあるリーフノードのノード番号。 リーフノードが存在しない場合、このフィールドの値はゼロになります。

nodeSize

ノードのサイズ（バイト単位）。 この値は、512 から 32,768 の範囲にある 2 のべき乗値です。

maxKeyLength

インデックスまたはリーフノードに含まれるキーの最大長。 HFSVolumes.h では、HFS および HFS Plus の両方についてカタログファイルとエクステントファイルの maxKeyLength 値が定義されています（kHFSPlusExtentKeyMaximumLength、kHFSExtentKeyMaximumLength、kHFSPlusCatalogKeyMaximumLength、kHFSCatalogKeyMaximumLength）。 アトリビュート B ツリーの最大キー長はカタログファイルよりも若干大きくなるはずです。 一般に、maxKeyLength は、1 つのノードが最大サイズの 2 つのキーとノード記述子およびオフセットを格納できる程度に十分に小さくなければなりません（nodeSize 比較して）。

totalNodes

B ツリーに含まれるノードの総数（空きノードであるか、使用済みノードであるかに関係なく）。 B ツリーファイルの長さはこの値と nodeSize を掛け合わせて計算することができます。

freeNodes

B ツリーに含まれる未使用ノードの数。

reserved1

インプリメンテーションでは、これを予約済みのフィールドとして扱う必要があります。

clumpSize

HFS Plus B ツリーでは無視されます。 その代わりに、HFSPlusForkData レコードの clumpSize フィールドが使用されます。 最大限の互換性を維持するため、インプリメンテーションではノード記述子の clumpSize に、ボリュームを初期化したときの HFSPlusForkData の clumpSize と同じ値を設定してください。 そうでない場合は、ヘッダーレコードの clumpSize を予約済みとして扱ってください。

btreeType

このフィールドに格納される値の型は BTreeTypes です。

enum BTreeTypes{ kHFSBTreeType = 0, // 制御ファイル kUserBTreeType = 128, // ユーザ B　ツリータイプ、128 から開始 kReservedBTreeType = 255 };

このフィールドは、カタログ、エクステント、およびアトリュビュートの各 B ツリーにおいて kHFSBTreeType と同じである必要があります。 このフィールドは、ホットファイル B ツリーにおいて kUserBTreeType と同じである必要があります。 歴史的に、1 〜 127 および　kReservedBTreeType の値は、Mac OS 9 およびそれ以前のシステムソフトウェアが使用する B ツリーによって使用されていました。

keyCompareType

HFSX ボリュームでは、カタログ B ツリーヘッダー内のこのフィールドはキーの順列を定義します（ボリュームで大文字小文字が区別されるかどうかにかかわらず）。 それ以外の場合、インプリメンテーションでは、これを予約済みのフィールドとして扱う必要があります。

定数名	値	意味
kHFSCaseFolding	0xCF	大小文字統合（大文字小文字を区別しない）
kHFSBinaryCompare	0xBC	バイナリ比較（大文字小文字を区別）

attributes

B ツリーのさまざまな属性を記述するために使用するビットの集合。 これらのビットの意味を以下に示します。

reserved3

インプリメンテーションでは、これを予約済みのフィールドとして扱う必要があります。

次の定数は、ヘッダーレコードの attributes フィールドでセットされるさまざまなビットを定義します。

enum {
    kBTBadCloseMask           = 0x00000001,
    kBTBigKeysMask            = 0x00000002,
    kBTVariableIndexKeysMask  = 0x00000004
};

それぞれのビットは次のような意味を持ちます。

kBTBadCloseMask

このビットは B ツリーが適切にクローズされているかどうかを示し、必要な場合は一貫性のチェックを行います。 このビットは HFS Plus B ツリーでは使用されません。 インプリメンテーションでは、このビットを予約済みとして扱う必要があります。

kBTBigKeysMask

このビットがセットされていると、インデックスおよびリーフノードに含まれるキーの keyLength フィールドは UInt16 型になります。そうでない場合は UInt8 型になります。 このビットはすべての HFS Plus B ツリーでセットする必要があります。

kBTVariableIndexKeysMask

このビットがセットされていると、インデックスノードのキーはその keyLength フィールドで指定されたバイト数を占有します。そうでない場合、インデックスノードのキーは常に maxKeyLength のバイト数を占有します。 HFS Plus カタログ B ツリーではこのビットをセットし、HFS Plus エクステント B ツリーではこのビットをクリアする必要があります。

ここで説明しなかったビットはすべて予約済みとして扱う必要があります。

ユーザデータレコード

ヘッダーノードの 2 番目のレコードは必ず 128 バイトの長さがあります。この小さな領域に B ツリーにかかわる情報を格納することができます。

HFS Plus のカタログ、エクステント、およびアトリビュートの各 B ツリーでは、このレコードは使用されず予約済みとなります。 HFS Plus のホットファイル B ツリーでは、このレコードにホットファイルレコードプロセスの一般情報が格納されます。

マップレコード

ヘッダーノードの残された領域は 3 番目のレコードであるマップレコードによって占有されます。 マップレコードは、B ツリー内のどのノードが使用されていて、どのノードが使用されていないかを示すビットマップです。 これらのビットはアロケーションファイルのビットと同じ方法で解釈されます。

ノード記述子、ヘッダーレコード、予約されているレコード、およびレコードオフセットをまとめると、ヘッダーノードの中の 256 バイトが占有されます。 このため、マップレコードのサイズ（バイト単位）は nodeSize から 256 を差し引いた値になります。 B ツリー内に、ヘッダーノードのマップレコードで表すことのできるノードを超えるノードが存在する場合は、マップノードが追加のアロケーションデータを格納するために使用されます。

マップノード

ヘッダーノードのマップレコードに十分なサイズがなくて、B ツリー内のすべてのノードを表すことができない場合、残ったアロケーションデータを格納するためにマップノードが使用されます。 この場合、ヘッダーノードのノード記述子に含まれる fLink フィールドには先頭のマップノードのノード数が含まれます。

マップノードはノード記述子と 1 つのマップレコードから構成されます。 このマップレコードはヘッダーノードに含まれるマップノードの続きです。 このマップレコードのサイズは、ノード全体のサイズからノード記述子のサイズ（14 バイト）、2 つのオフセット（4 バイト）、および 2 バイトの空き領域を差し引いた値になります。 つまり、マップレコードのサイズはノード全体のサイズから 20 バイトを引いた値になり、常に 4 バイトの偶数倍になります。 なお、マップレコードの先頭は 4 バイト境界に揃えられていません。 マップレコードはノード記述子の直後（14 バイトのオフセット）から始まります。

B ツリーは必要な数のマップノードを使用し、B ツリー内にあるすべてのノードのアロケーションデータを提供します。 複数のマップノードはヘッダーノードから始まり、それらのノード記述子に含まれる fLink フィールドを介して連結されています。 最後のマップノードのノード記述子に含まれる fLink フィールドの値はゼロです。 bLink フィールドはマップノードでは使用されず、すべてのマップノードでゼロにセットされていなければなりません。

キーを含むレコード

インデックスおよびリーフノードのレコードは共通の構造を持っています。 これらのレコードには、keyLength、キーそのもの、レコードデータがこの順番に格納されています。

レコードの先頭部分である keyLength は、B ツリーのヘッダーレコードに含まれる attributes フィールドの値に応じて、UInt8 または UInt16 のいずれかになります。 attributes フィールドの kBTBigKeysMask ビットがセットされていると、keyLength は UInt16 になり、そうでなければ UInt8 になります。 このフィールドに格納されているキーの長さに keyLength フィールドそのもののサイズは含まれていません。

keyLength の直後にキーそのものが続きます。 キーの長さはノードのタイプと B ツリーの属性によって決まります。 リーフノードでは、キーの長さは常に keyLength によって決まります。 インデックスノードの場合、キーの長さは、ヘッダーレコードに含まれる B ツリー属性の kBTVariableIndexKeysMask ビットの値によって変わります。 このビットがクリアされていると、キーは B ツリーヘッダーレコードの maxKeyLength フィールドで指定されている一定のバイト数を占有します。 一方、このビットがセットされていると、キーの長さはキーレコードの keyLength フィールドによって決定されます。

キーの後にはレコードのデータが続きます。 このデータのフォーマットは、次の 2 つのセクションで説明するように、ノードのタイプによって異なります。 ただし、データは常に 2 バイト境界に揃えられ、偶数バイトを占有します。 第 1 のアライメント条件を満たすため、keyLength のサイズとキーのサイズの合計が奇数になる場合は、キーとデータの間にパッドバイトを挿入する必要があります。 また、第 2 のアライメント条件を満たすため、データサイズが奇数の場合はデータの後にパッドバイトを追加する必要があります。

インデックスノード

インデックスノードに含まれるレコードはポインタレコードと呼ばれます。 これらのレコードには、UInt32 で表される keyLength、キー、およびノード番号が含まれます。 ポインタレコードで指定された番号を持つノードは、インデックスノードの子ノードと呼ばれます。 1 つのインデックスノードは、ノードのサイズとノードに含まれるキーのサイズによって、2 つまたはそれ以上の子ノードを持ちます。

リーフノード

B ツリーの最も下位のレベルはリーフノードによって独占されます。 このノードには、ポインタレコードの代わりにデータレコードが含まれます。 データレコードには、keyLength、キー、およびキーに関連付けられたデータが含まれます。 このデータが可変長である場合もあります。

HFS Plus B ツリーでデータレコードに含まれるデータは、キーに関連づけられた HFS Plus ボリューム構造（CatalogRecord、ExtentRecord、AttributeRecord など）です。

キーを含むレコードの検索

B ツリーは、効率的な検索、挿入、および削除を可能にするため高度に構造化されています。 この構造は主としてキーを含むレコード (ポインタレコードとデータレコード) と、それらを格納しているノード (インデックスノードおよびリーフノード) に影響します。 次に、インデックスノードとリーフノードで使用される順序の要件を示します。

• キーを含むレコードはそれらのキーが昇順になるようにノード内に配置する必要があります。
• あるレベルにあるすべてのノード（同じ height フィールドの値を持つノード）は、それらの fLink および bLink フィールドを介して連結されている必要があります。 最小のキーを持つノードはチェーンの先頭に位置し、その bLink フィールドはゼロでなければなりません。 また、最大のキーを持つノードはチェーンの末尾に位置し、その fLink フィールドはゼロでなければなりません。
• どのノードの場合も、そのノードに含まれるすべてのキーは、チェーン内の次のノード（fLink によってポイントされる）に含まれるすべてのキーよりも小さくなければなりません。 同様に、そのノードに含まれるすべてのキーはチェック内の前のノード（bLink によってポイントされる）に含まれるすべてのキーよりも大きくなければなりません。

このような方法で配列されたキーを保持することで、B ツリーをすばやく検索して、特定のキーに対応するデータを見つけることが可能になります。 図 4 に、架空のキーを含む B ツリーのサンプルを示します（この例のキーは単純な整数であるとします）。

インプリメンテーションにおいて特定の検索キーに対応するデータを検索する場合、検索はルートノードから開始されます。 先頭のレコードを起点に、検索キーと同じかそれ未満のキーのうちの最大のキーを持つレコードを検索します。 この後、検索対象は子ノード（通常はインデックスノード）に移り、同じプロセスが繰り返されます。

このプロセスはリーフノードの達するまで続けられます。 リーフノードで検出したキーが検索キーに等しい場合、検出されたレコードには検索キーに対応する目的のデータが含まれます。 また、検出したキーが検索キーと等しくない場合、その検索キーは B ツリー内に存在しないということになります。

図 4. B ツリーのサンプル

HFS の B ツリーと HFS Plus の B ツリーの比較

HFS Plus 上の B ツリーの構造は、HFS ボリュームで使用される B ツリーの構造と密接な関係があります。 これらの構造の間には、ノードのサイズ、インデックスノード内のキーのサイズ、およびキー長のサイズ（UInt8 と UInt16）という 3 つの大きな違いがあります。

ノードのサイズ

HFS B ツリーでは、ノードは常に 512 バイトの固定長を持ちます。

HFS Plus B ツリーでは、ノードのサイズはヘッダーノードに含まれるフィールド（nodeSize）によって決まります。 ノードのサイズは 512 から 32,768 の範囲にある2のべき乗値でなければなりません。 インプリメンテーションでは、nodeSize フィールドを使って、実際のノードサイズを決定する必要があります。

HFS Plus では次のようなデフォルトのノードサイズが使用されます。

• カタログファイルの場合は 4KB（Mac OS X では 8KB）
• エクステントオーバーフローファイルの場合は 1KB（Mac OS X では 4KB）
• アトリビュートファイルの場合は 4KB

これらのサイズはボリュームを初期化するときに設定され、その後は容易には変更できません。 異なるノードサイズで HFS Plus ボリュームを初期化することは認められていますが、ノードサイズには、インデックスノードが 2 つの最大サイズのキー（およびノード記述子、レコードオフセット、子へのポインタなどのその他のオーバーヘッドを含めて）を含むことができるように十分なサイズを割り当てる必要があります。

インデックスノードのキーサイズ

HFS B ツリーの場合、インデックスノードに含まれるすべてのキーは固定長の領域、つまりその B ツリーの最大のキー長を占有します。 これにより、インデックスノード内部で新しいキーを格納するために十分な空き領域があるかどうかを心配しなくても、あるキーを別のキーで置き換えることができるため、レコードの挿入や削除のアルゴリズムが簡略化されます。 ただし、キーが可変長のときには（キー長がファイル名の長さによって変わるカタログファイルの中などで）、ある程度の領域の浪費が発生します。

HFS Plus B ツリーの場合、インデックスノードに含まれるキーはサイズを変えることができます。 これにより、レコードの挿入や削除のアルゴリズムは複雑になりますが、キーが可変長のときにも（カタログファイルなど）、領域の浪費を抑えることができます。 また、このことは、キーの実際のサイズによって、インデックスノードに含まれるキーの数が異なるということも意味します。

先頭に戻る

カタログファイル

HFS Plus では、カタログファイルを使って、ボリューム上にあるファイルとフォルダの階層に関する情報を保守します。 カタログファイルは B ツリーファイルとして編成されており、ヘッダーノード、インデックスノード、リーフノード、および（必要な場合は）マップノードから構成されます。 カタログファイルの先頭のエクステント（とファイルのヘッダーノード）はボリュームヘッダーの中に格納されています。 インプリメンテーションは、カタログファイルのヘッダーノードから B ツリーのルートノードのノード番号を取得することができます。 また、前のセクションで説明したように、ルートノードから B ツリーのキーを検索することができます。

「B ツリー」のセクションでは、HFS Plus B ツリーのノードサイズに関する標準的な規則を定義しました。 カタログファイルも B ツリーであるため、カタログファイルは当然のことながらこの規則の必要条件を継承します。 また、カタログファイルのノードサイズは少なくとも 4KB（kHFSPlusCatalogMinNodeSize）でなければなりません。

カタログファイルに含まれるそれぞれのファイルやフォルダには、重複のないカタログノード ID（CNID）が割り当てられています。 フォルダの場合、CNID はフォルダ ID であり、ディレクトリ ID または dirID と呼ばれることもあります。また、ファイルの場合は、それはファイル ID になります。 特定のファイルまたはフォルダについて、親 ID とは、そのファイルまたはフォルダを含むフォルダ、つまり親フォルダの CNID のことです。

カタログノード ID は CatalogNodeID データ型によって定義されます。

typedef UInt32 HFSCatalogNodeID;

先頭から 16 の CNID はアップルが使用するために予約されており、次のような標準的な割り当てを含んでいます。

enum {
    kHFSRootParentID            = 1,
    kHFSRootFolderID            = 2,
    kHFSExtentsFileID           = 3,
    kHFSCatalogFileID           = 4,
    kHFSBadBlockFileID          = 5,
    kHFSAllocationFileID        = 6,
    kHFSStartupFileID           = 7,
    kHFSAttributesFileID        = 8,
    kHFSRepairCatalogFileID     = 14,
    kHFSBogusExtentFileID       = 15,
    kHFSFirstUserCatalogNodeID  = 16
};

これらの定数は次のような意味を持ちます。

kHFSRootParentID

ルートフォルダの親 ID。

kHFSRootFolderID

ルートフォルダのフォルダ ID。

kHFSExtentsFileID

エクステントオーバーフローファイルのファイル ID。

kHFSCatalogFileID

カタログファイルのファイル ID。

kHFSBadBlockFileID

不良ブロックファイルのファイル ID。 不良ブロックファイルは特殊ファイルではなく、むしろユーザファイルの 1 つです。 詳細については、「不良ブロックファイル」を参照してください。

kHFSAllocationFileID

アロケーションファイル（HFS Plus で導入された）のファイル ID。

kHFSStartupFileID

スタートアップファイル（HFS Plus で導入された）のファイル ID。

kHFSAttributesFileID

アトリビュートファイル（HFS Plus で導入された）のファイル ID。

kHFSRepairCatalogFileID

カタログファイルの再構築時に fsck_hfs によって一時的に使用される。

kHFSBogusExtentFileID

ExchangeFiles オペレーションの間に一時的に使用される。

kHFSFirstUserCatalogNodeID

ユーザファイルおよびユーザフォルダが使用できる最初の CNID。

また、ゼロの CNID は使用されることがなく、nil 値として働きます。

通常、CNID は kHFSFirstUserCatalogNodeID から始まって、シーケンシャルに割り当てられます。 2000 年 1 月 18 日以前の仕様の HFS Plus では、ボリュームヘッダーの nextCatalogID フィールドが、ボリューム上の最大 CNID よりも大きい必要がありました（インプリメンテーションが nextCatalogID を使用して、新規作成されたファイルまたはディレクトリに割り当てる CNID を決められるように ）。 しかし、高い頻度でファイルやディレクトリを作成するボリューム（処理量の多いサーバなど）では、CNID 値が足りなくなる可能性があるため、これは問題になることがあります。

現在は、HFS Plus ボリュームでは、CNID 値が循環し再利用でき�