ファイル情報はどのように記録されているのか？

今時のハードディスクは、テラバイト(TB)単位が当たり前の状況になってしまった...。

1TB＝1,000GB＝1,000,000MB＝1,000,000,000KB＝1,000,000,000,000B（1兆バイト）

単純に1バイト1文字と考えれば、1兆文字が記録できるのだ！天文学的な情報量である。この広大な保存領域にデータはどのように保存されているのだろうか？普段はOSのファイルシステムとして完全に隠蔽された状態である。今回はその隠蔽された構造を調べてみようと思う。

HFS+のフォーマット

ハードディスクを、1兆文字書ける無地のノートのようなものと考えれば、フォーマットとはそこに罫線を引き、どのように記録するかを定めたルールと言えるかもしれない。

セクタ

ほとんどのハードディスクは、512バイト*1のセクタというマス目に区切られている。
ハードディスクのコントーローラーは、読み書きをこのセクタ単位で取り扱うのだ。

アロケーションブロック

一方、OSXがHFS+フォーマットで管理する時は、8つのセクタをまとめて4Kバイトのアロケーションプロックという単位で管理している。
それぞれのアロケーションブロックには、順にアロケーションブロック番号が割り振られている。

エクステント

ファイルを保存する時には、データを書き込む先頭のアロケーションブロック番号と連続するブロック数を記録しておく。
HFS+では、上記の先頭のアロケーションブロック番号と連続するブロック数の記録をエクステントと呼んでいる。

カタログノード

上記エクステントをファイル名やその他の属性と共に、目次情報として保存することで、ファイルは保存される。
HFS+では、この目次情報のことをカタログノードと呼んでいる。
1つのファイルは、内容そのものと、その内容の在処を記録したカタログノードに分けて記録されているのだ。

カタログノードには、カタログノードID（CNID）が設定される。（完全にユニークなIDである）
一度設定されたカタログノードIDは、たとえファイルが削除されたとしても再利用されることはない。

エクステントオーバーフローノード

何度も修正・削除が繰り返される環境においては、必ずしも連続した領域1つだけで保存できるとは限らない。
保存したいデータ容量以上の空き領域が確保できない時は、複数のエクステントに分けて保存する必要もある。

そのため、カタログノードは8つのエクステントを保持できるようになっている。
しかし、ファイルによっては8つ以上のエクステントが必要になる可能性もある。
その場合は、エクステントオーバーフローノードを生成して、さらに8つのエクステントを追加できるようになっている。
さらなるエクステントが必要な時は、エクステントオーバーフローノードをもう一度生成して...この繰り返しで対応する。

但し、エスクテントオーバーフローノードが増えると、ファイルアクセスは遅くなる。
1ファイル＝1カタログノード（8つのエクステント内）で管理できた方が、効率がいい。

カタログファイル

上記カタログノード（目次情報）は、カタログファイルに記録される。
カタログファイルは、CNID＝4のファイルである。
カタログファイルには複数のカタログノードが記録されており、ファイルの内容はそこから辿れるのだ。

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

同様に、エクステントオーバーフローノードは、エクステントオーバーフローファイルに記録される。
エクステントオーバーフローファイルは、CNID＝3のファイルである。

予約済みのカタログノードID

カタログノードIDの1-15までは予約されており、以下のような役割が定義されている。

/* Catalog file data structures */

enum {
	kHFSRootParentID		= 1,	/* Parent ID of the root folder （ルートディレクトリの親ID）*/
	kHFSRootFolderID		= 2,	/* Folder ID of the root folder （ルートディレクトリのディレクトリID）*/
	kHFSExtentsFileID		= 3,	/* File ID of the extents file （エクステントオーバーフローファイルのファイルID）*/
	kHFSCatalogFileID		= 4,	/* File ID of the catalog file （カタログファイルのファイルID）*/
	kHFSBadBlockFileID		= 5,	/* File ID of the bad allocation block file （不良ブロックファイルのファイルID）*/
	kHFSAllocationFileID		= 6,	/* File ID of the allocation file (HFS Plus only) （アロケーションファイルのファイルID）*/
	kHFSStartupFileID		= 7,	/* File ID of the startup file (HFS Plus only) （スタートアップファイルのファイルID）*/
	kHFSAttributesFileID		= 8,	/* File ID of the attribute file (HFS Plus only) （アトリビュートファイルのファイルID）*/
	kHFSAttributeDataFileID         = 13,	/* Used in Mac OS X runtime for extent based attributes （Mac OS X環境でエクステントを活用した属性で使用される）*/
	                                        /* kHFSAttributeDataFileID is never stored on disk. （kHFSAttributeDataFileIDはディスク上に保存されることはない）*/
	kHFSRepairCatalogFileID		= 14,	/* Used when rebuilding Catalog B-tree （カタログB-Treeを再構築する時に使用される）*/
	kHFSBogusExtentFileID		= 15,	/* Used for exchanging extents in extents file （ExchangeFilesオペレーションの間に一時的に使用される）*/
	kHFSFirstUserCatalogNodeID	= 16	/*（ユーザーファイルおよびユーザーディレクトリが使用できる最初のCNID）*/
};

構造体の定義から見る

http://www.opensource.apple.com/source/xnu/xnu-2050.18.24/bsd/hfs/hfs_format.h

カタログノード

カタログノードが、属性情報＋ HFSPlusForkDataが指し示すフォークを保持することで、ファイルを保存している。
カタログノードは、２つのフォーク（保存領域）を保持している。
- データフォーク（ファイルの内容）
- リソースフォーク（OSXでは未使用、OS9まで利用していた）

/* HFS Plus catalog file record - 248 bytes */
struct HFSPlusCatalogFile {
	int16_t 		recordType;		/* == kHFSPlusFileRecord */
	u_int16_t 		flags;			/* file flags */
	u_int32_t 		reserved1;		/* reserved - initialized as zero */
	u_int32_t 		fileID;			/* file ID */
	u_int32_t 		createDate;		/* date and time of creation */
	u_int32_t 		contentModDate;		/* date and time of last content modification */
	u_int32_t 		attributeModDate;	/* date and time of last attribute modification */
	u_int32_t 		accessDate;		/* date and time of last access (MacOS X only) */
	u_int32_t 		backupDate;		/* date and time of last backup */
	HFSPlusBSDInfo 		bsdInfo;		/* permissions (for MacOS X) */
	FndrFileInfo 		userInfo;		/* Finder information */
	FndrOpaqueInfo	 	finderInfo;		/* additional Finder information */
	u_int32_t 		textEncoding;		/* hint for name conversions */
	u_int32_t 		reserved2;		/* reserved - initialized as zero */

	/* Note: these start on double long (64 bit) boundary */
	HFSPlusForkData 	dataFork;		/* size and block data for data fork */
	HFSPlusForkData 	resourceFork;		/* size and block data for resource fork */
} __attribute__((aligned(2), packed));
typedef struct HFSPlusCatalogFile HFSPlusCatalogFile;

フォーク

HFSPlusForkDataは、8つのエクステントを保持することで、ファイルの内容を追跡する。

/* HFS Plus Fork data info - 80 bytes */
struct HFSPlusForkData {
	u_int64_t 		logicalSize;	/* fork's logical size in bytes */
	u_int32_t 		clumpSize;	/* fork's clump size in bytes */
	u_int32_t 		totalBlocks;	/* total blocks used by this fork */
	HFSPlusExtentRecord 	extents;	/* initial set of extents */
} __attribute__((aligned(2), packed));
typedef struct HFSPlusForkData HFSPlusForkData;

/* HFS Plus extent record */
typedef HFSPlusExtentDescriptor HFSPlusExtentRecord[8];

エクステント

エクステントは、データが保存されている先頭ブロックと、連続するブロック数を記録している。

/* HFS Plus extent descriptor */
struct HFSPlusExtentDescriptor {
	u_int32_t 	startBlock;		/* first allocation block */
	u_int32_t 	blockCount;		/* number of allocation blocks */
} __attribute__((aligned(2), packed));
typedef struct HFSPlusExtentDescriptor HFSPlusExtentDescriptor;

カタログキー

カタログノードはカタログファイルの中で、以下のキーを使ったB-Tree構造で保存されている。

/* HFS Plus catalog key */
struct HFSPlusCatalogKey {
	u_int16_t 		keyLength;	/* key length (in bytes) */
	u_int32_t 		parentID;	/* parent folder ID */
	HFSUniStr255 		nodeName;	/* catalog node name */
} __attribute__((aligned(2), packed));
typedef struct HFSPlusCatalogKey HFSPlusCatalogKey;

上記のカタログキーに、HFSPlusCatalogFile構造体が続く構造なのかもしれない。

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

ファイル内容の追跡に、カタログノードが保持する8つのエクステントで不足した場合、
エクステントオーバーフローノードを生成して、さらに8つのエクステントを追加する。

エクステントオーバーフローノードは、エクステントオーバーフローファイルの中で、以下のキーを使った構造で保存されている。

/* HFS Plus Extent key */
struct HFSPlusExtentKey {
	u_int16_t 	keyLength;		/* length of key, excluding this field */
	u_int8_t 	forkType;		/* 0 = data fork, FF = resource fork */
	u_int8_t 	pad;			/* make the other fields align on 32-bit boundary */
	u_int32_t 	fileID;			/* file ID */
	u_int32_t 	startBlock;		/* first file allocation block number in this extent */
} __attribute__((aligned(2), packed));
typedef struct HFSPlusExtentKey HFSPlusExtentKey;

上記のエクステントオーバーフローキーに、HFSPlusExtentRecord構造体が続く構造なのかもしれない。

/* HFS Plus extent record */
typedef HFSPlusExtentDescriptor HFSPlusExtentRecord[8];

ボリュームヘッダー

ファイルの内容はカタログノードが管理し、カタログノードはカタログファイルに記録される。
そしてカタログファイル自体も、通常のファイルと同じように、エクステントを束ねたフォークによって管理されている。
よって、カタログファイルを管理するフォークも必要になる。
そのような特殊なフォークはHFS+のボリュームヘッダにある。

HFS+のボリュームの先頭第2セクタには、以下のような情報が記録されているのだ。

/* HFS Plus Volume Header - 512 bytes */
/* Stored at sector #2 (3rd sector) and second-to-last sector. */
struct HFSPlusVolumeHeader {
	u_int16_t 	signature;		/* == kHFSPlusSigWord */
	u_int16_t 	version;		/* == kHFSPlusVersion */
	u_int32_t 	attributes;		/* volume attributes */
	u_int32_t 	lastMountedVersion;	/* implementation version which last mounted volume */
	u_int32_t 	journalInfoBlock;	/* block addr of journal info (if volume is journaled, zero otherwise) */

	u_int32_t 	createDate;		/* date and time of volume creation */
	u_int32_t 	modifyDate;		/* date and time of last modification */
	u_int32_t 	backupDate;		/* date and time of last backup */
	u_int32_t 	checkedDate;		/* date and time of last disk check */

	u_int32_t 	fileCount;		/* number of files in volume */
	u_int32_t 	folderCount;		/* number of directories in volume */

	u_int32_t 	blockSize;		/* size (in bytes) of allocation blocks */
	u_int32_t 	totalBlocks;		/* number of allocation blocks in volume (includes this header and VBM*/
	u_int32_t 	freeBlocks;		/* number of unused allocation blocks */

	u_int32_t 	nextAllocation;		/* start of next allocation search */
	u_int32_t 	rsrcClumpSize;		/* default resource fork clump size */
	u_int32_t 	dataClumpSize;		/* default data fork clump size */
	u_int32_t 	nextCatalogID;		/* next unused catalog node ID */

	u_int32_t 	writeCount;		/* volume write count */
	u_int64_t 	encodingsBitmap;	/* which encodings have been use  on this volume */

	u_int8_t 	finderInfo[32];		/* information used by the Finder */

	HFSPlusForkData	 allocationFile;	/* allocation bitmap file */
	HFSPlusForkData  extentsFile;		/* extents B-tree file */
	HFSPlusForkData  catalogFile;		/* catalog B-tree file */
	HFSPlusForkData  attributesFile;	/* extended attributes B-tree file */
	HFSPlusForkData	 startupFile;		/* boot file (secondary loader) */
} __attribute__((aligned(2), packed));
typedef struct HFSPlusVolumeHeader HFSPlusVolumeHeader;

構造体の末尾のHFSPlusForkDataの領域で管理されている。

アロケーションファイル各アロケーションブロックの使用状況を管理するビットマップを管理する。

エクステントオーバーフローファイルファイルに8つ以上のエクステントが必要になった場合、こちらにエントリを追加して管理する。

カタログファイルファイルの内容や属性、ディレクトリに関する情報を管理する。

アトリビュートファイルデータフォーク、リソースフォーク以外のフォークに関する情報を管理する。

スタートアップファイル OSのブートローダーを格納するための領域。Mac OS 9、Mac OS Xでは使用されていない。

第7回 HFS、HFS Plusの基本的概念【前編】 (1/4) - ITmedia エンタープライズ

アロケーションファイル	各アロケーションブロックの使用状況を管理するビットマップを管理する。
エクステントオーバーフローファイル	ファイルに8つ以上のエクステントが必要になった場合、こちらにエントリを追加して管理する。
カタログファイル	ファイルの内容や属性、ディレクトリに関する情報を管理する。
アトリビュートファイル	データフォーク、リソースフォーク以外のフォークに関する情報を管理する。
スタートアップファイル	OSのブートローダーを格納するための領域。Mac OS 9、Mac OS Xでは使用されていない。

マルチフォークの構造

ここまで、ファイル本体（中身）と伝統的な属性情報（ファイル名・日時・権限など）は、カタログファイルとエクステントオーバーフローファイルによって管理される仕組みを見てきた。そこには、データフォークとリソースフォーク*2の２つのフォーク（保存領域）があることも分かった。

さらに、HFS+では、ユーザー定義の任意のフォークを自由に追加することもできる！
ユーザー定義の任意のフォークを管理しているのが、アトリビュートファイルである。

ACL（Access Control Lists＝アクセス制御リスト）が実現されているのもアトリビュートファイルのおかげである。
EA（Extended Attribute＝拡張属性）が実現されているのも、アトリビュートファイルのおかげである。
HFS compression（透過的圧縮）が実現されているのも、アトリビュートファイルのおかげである。

SpotlightはEA（com.apple.metadata:kMDItem ... で始まるフォーク）なども利用して、きめ細かな検索を実現している。
TimeMachineもEA（com.apple.backupd. ... で始まるフォーク）を利用して、バックアップを実現している。
OS9までの旧来のリソースフォーク（OSXでは未使用）は、com.apple.ResourceForkというEAのリソースフォークとして復活している。

つまり、最新の利便性を追求するための拡張的な属性情報は、アトリビュートファイルによって管理されているのだ。

属性キー＝独自のフォーク名称

/* Attribute key */
enum { kHFSMaxAttrNameLen = 127 };
struct HFSPlusAttrKey {
	u_int16_t     keyLength;       /* key length (in bytes) */
	u_int16_t     pad;	       /* set to zero */
	u_int32_t     fileID;          /* file associated with attribute */
	u_int32_t     startBlock;      /* first allocation block number for extents */
	u_int16_t     attrNameLen;     /* number of unicode characters */
	u_int16_t     attrName[kHFSMaxAttrNameLen];   /* attribute name (Unicode) */
} __attribute__((aligned(2), packed));
typedef struct HFSPlusAttrKey HFSPlusAttrKey;

属性レコード＝値のデータ構造

/*	A generic Attribute Record*/
union HFSPlusAttrRecord {
	u_int32_t 		recordType;
	HFSPlusAttrInlineData 	inlineData;   /* NOT USED */
	HFSPlusAttrData 	attrData;
	HFSPlusAttrForkData 	forkData;
	HFSPlusAttrExtents 	overflowExtents;
};
typedef union HFSPlusAttrRecord HFSPlusAttrRecord;

HFSPlusAttrData ＝属性情報をアトリビュートファイル内部に格納する。

/*
 * Atrributes B-tree Data Record
 *
 * For small attributes, whose entire value is stored
 * within a single B-tree record.
 */
struct HFSPlusAttrData {
	u_int32_t    recordType;   /* == kHFSPlusAttrInlineData */
	u_int32_t    reserved[2];
	u_int32_t    attrSize;     /* size of attribute data in bytes */
	u_int8_t     attrData[2];  /* variable length */
} __attribute__((aligned(2), packed));
typedef struct HFSPlusAttrData HFSPlusAttrData;

HFSPlusAttrForkData ＝属性情報をエクステントを利用してアトリビュートファイル外部に追加する。（旧来のリソークフォークと同じ仕組み）

/*
  	HFSPlusAttrForkData
  	For larger attributes, whose value is stored in allocation blocks.
  	If the attribute has more than 8 extents, there will be additional
  	records (of type HFSPlusAttrExtents) for this attribute.
*/
struct HFSPlusAttrForkData {
	u_int32_t 	recordType;		/* == kHFSPlusAttrForkData*/
	u_int32_t 	reserved;
	HFSPlusForkData theFork;		/* size and first extents of value*/
} __attribute__((aligned(2), packed));
typedef struct HFSPlusAttrForkData HFSPlusAttrForkData;

HFSPlusAttrExtents ＝上記HFSPlusAttrForkDataでエクステントが不足した時に追加される。

/*
  	HFSPlusAttrExtents
  	This record contains information about overflow extents for large,
  	fragmented attributes.
*/
struct HFSPlusAttrExtents {
	u_int32_t 		recordType;	/* == kHFSPlusAttrExtents*/
	u_int32_t 		reserved;
	HFSPlusExtentRecord	extents;	/* additional extents*/
} __attribute__((aligned(2), packed));
typedef struct HFSPlusAttrExtents HFSPlusAttrExtents;

実例から追跡してみる

初期化したばかりのハードディスクにテキストエディットを使って「hello world!」という12文字のテキストを保存してみる。
そのときどんなことが起こるのか想像してみることで、ここまで調べてきたことの全体像がもう少し鮮明になるかもしれない。

書き込んだファイルは以下のような内容と属性を持っている。

 $ cat /hello.txt 
 hello world!

 $ ls -lOe@ /hello.txt 
 -rw-r--r--@ 1 bebe  staff  - 13  4  3 14:08 /hello.txt
 	com.apple.TextEncoding	15 

 $ xattr -lx /hello.txt
 com.apple.TextEncoding:
 00000000  75 74 66 2D 38 3B 31 33 34 32 31 37 39 38 34     |utf-8;134217984|
 0000000f

ボリュームヘッダの内容

ハードディスクの第2セクタのボリュームヘッダ領域のカタログファイルのフォークデータ領域が更新される。
- CNID（カタログノードID）=4のファイルは、アロケーションブロックの1番から1ブロック分の領域あるよ。

ハードディスクの第2セクタのボリュームヘッダ領域のアトリビュートファイルのフォークデータ領域が更新される。
- CNID（カタログノードID）=8のファイルは、アロケーションブロックの2番から1ブロック分の領域にあるよ。

カタログファイルの内容（アロケーションブロックの1番から1ブロック分の領域）

カタログキーが設定される
- keyLength ＝ 15（hello.txtの9バイトと、keyLengthの2バイト、parentIDの4バイト）
- parentID ＝ /
- nodeName ＝ hello.txt

カタログノード（248バイトの情報）が設定される。
- 日時情報や権限とデータフォーク位置が書き込まれる。
  - CNID（カタログノードID）=16のファイルは、アロケーションブロックの3番から1ブロック分の領域にあるよ。

hello.txtの内容（アロケーションブロックの3番から1ブロック分の領域）

アロケーションブロックの3番に「hello world!」が書き込まれる。

アトリビュートファイルの内容（アロケーションブロックの2番から1ブロック分の領域）

アトリビュートキーが設定される。
- u_int16_t keyLength ＝ 58（44 ＋ 14）
- u_int16_t pad ＝ 0
- u_int32_t fileID ＝ 16
- u_int32_t startBlock ＝ 4
- u_int16_t attrNameLen ＝ 44（ユニコードなので1文字2バイト？）
- u_int16_t attrName ＝ com.apple.TextEncoding

アトリビュートレコードが設定される。
- HFSPlusAttrDataが書き込まれる。
  - u_int32_t recordType = kHFSPlusAttrInlineData
  - u_int32_t reserved[2]
  - u_int32_t attrSize ＝ 15
  - u_int8_t attrData[2] ＝ utf-8;134217984

以上のような情報がハードディスクに書き込まれるのではないかと、想像している。

このような地道な作業の繰り返しで、100万ファイル以上が複雑なディレクトリ構造の中に保存されているのだ！
大小ざまざまなファイルが、更新を繰り返しながら、破綻なく確実に保存される世界を考えていると、感動を覚える。

参考ページ

「Undocumented Mac OS X」最新記事一覧 - ITmedia Keywords
白山貴之さんの深遠なOSXの仕組みの解説には、唸るものがある。
読み返すほどに少しずつ理解も深まり、新たな発見と感動がある。

ディープな世界だ！（素晴らしい情報に感謝です！）

*1:最近は4Kバイトのセクタもあるようだ。

*2:但し、最新のOSXでは、カタログノードのリソースフォークは未使用のはず。

HFS+のフォーマット

セクタ

アロケーションブロック

エクステント

カタログノード

エクステント オーバーフロー ノード

カタログファイル

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

予約済みのカタログノードID

構造体の定義から見る

カタログノード

フォーク

エクステント

カタログキー

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

ボリュームヘッダー

マルチフォークの構造

実例から追跡してみる

ボリュームヘッダの内容

カタログファイルの内容（アロケーションブロックの1番から1ブロック分の領域）

hello.txtの内容（アロケーションブロックの3番から1ブロック分の領域）

アトリビュートファイルの内容（アロケーションブロックの2番から1ブロック分の領域）

参考ページ

エクステントオーバーフローノード

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

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