025 まず勉強しましょう（１日目）
●025 まず勉強しましょう（１日目）
ときは平成Ｙ＋１年、チャレンジの１日目、自室でググっていた。
外付けＨＤＤは「HFS Plus」（...M0cOS拡張フォーマットともいう）でフォーマットされている。
「HFS Plus」とか「M0cファイルシステム」とかでググると、HFS Plus の仕様を解説するドキュメントである「TN1150」が見つかる。これが一番詳しい。
HFS Plus の HFS の部分は Hierarchical File System の頭文字らしい。階層的なファイルシステムという意味かな（...いや階層的ではないファイルシステムってあるのだろうか？、余分なことが気になる）。元々は HFS というファイルシステムがあって、それを拡張したので Plus が付いたらしいです。
HFS Plus でフォーマットされた領域（...領域はボリュームとかパーティションともいう）の先頭には「ボリュームヘッダ」があり、領域の諸元情報が格納されている。その中に 5 個の特殊ファイルに関する情報がある。このうち「アロケーションファイル」と「カタログファイル」、「エクステントオーバーフローファイル」の 3 つにはファイルの格納場所など、ファイル復活のために重要な情報が格納されているようだ。
HFS Plus では、ファイルは 1 つまたは複数個の「エクステント」に格納される。エクステントとは、連続する「アロケーションブロック」のこと。アロケーションブロックとは、領域を適度なサイズで分割したものだ。
HFS Plus はアロケーションブロックを最小単位としてＨＤＤにアクセスするのである。なお、アロケーションブロックは M0c 用語らしく、他のＯＳではアロケーションユニットとかクラスタと言う。
アロケーションブロックのサイズは通常 4096 バイト（4KB）で、その先頭を 0 番とする。そして、ファイルの格納場所は、エクステントの最初のブロックの番号とブロックの個数のペアの情報として表現される。例えば、アロケーションブロック番号 100 から 104 までの 5 個のブロックからなるエクステントは、(#100, 5) と示す。完璧に理解できた！
さて。
アロケーションファイルは、領域の使用状況を表す情報を記録する「ビットマップ」形式のファイルである。...このビットマップはＢＭＰファイルとかの画像形式とは違って、1 ビットで何か 1 つの状況を表すデータ構造だよ。
アロケーションファイルの最初のバイトの最上位のビット（7 ビット目）がアロケーションブロックの 0 番、6 ビット目がアロケーションブロックの 1 番、...、0 ビット目がアロケーションブロックの 7 番、そして、次のバイトの 7 ビット目がアロケーションブロックの 8 番、...と言うようにアロケーションファイルのビットと、アロケーションブロックが対応して、ビットが 0 なら未使用、1 なら使用中を意味する。
アロケーションファイルで 0 となっているブロックを調べて、そこに 00h 以外のデータが含まれていたら、それは削除してしまったデータかも知れない。これを確認せねば。
カタログファイルは、ファイルやフォルダの情報が格納されている「Ｂツリー」形式のファイルである。ファイル名（またはフォルダ名）、更新時刻、ファイルのアクセス権、そしてエクステントの情報などが格納されている。エクステントの情報が重要で、これを特定できればファイルの復活につながる。だがエクステント情報を探すにはＢツリーを理解する必要があるようだ。
Ｂツリーは少し複雑だけれども、この詳細は TN1150 が明らかにしてくれる。基礎的な用語や概念から実装の細部までを丁寧に漏れなく解説している。TN1150 をよく読むと次のことが分かる。
＊＊＊
カタログファイルは固定長サイズの「ノード」の連続からなり、先頭のノードの番号が 0 番、ノードのサイズは典型的には 4096 バイトらしい。そしてノードには他のノードへの「ポインタ（ノード番号）」が含まれていて、ノードがリンクして木構造を作る。木構造なのでＢツリーというようだ。なぜ「Ｂ」が付くのかは不明だけど、ＡツリーやＣツリーもあるのかな（...それはないよ）。
ノード内には「レコード」が一つまたは複数個、含まれていて、ノードの先頭と末尾にはレコードの個数やレコードのオフセット情報がある。この情報を参照してレコードにアクセスできる。
先頭部分（...TN1150 ではノード記述子と言うのですが、先頭部分で十分ですね）は 14 バイト固定で、ノードの種別やレコードの個数、Ｂ木でのノードの高さ等の情報を含む。
レコード数を N として、ノードの末尾の (N+1)*2 バイトはオフセット情報で、各 2 バイトでレコードの開始または末尾を示す。先頭部分は 14 バイト固定なので、オフセット情報の最初は必ず +14 となり、最初のレコードの先頭を示す。オフセット情報の最後は、最後のレコードの末尾を示す。
ノードは４種類あって、「ヘッダーノード」「インデックスノード」「リーフノード」と「マップノード」である。そして、ノードの種類によってレコードに格納される情報が異なる。
ヘッダーノードは、カタログファイルの先頭にある（つまりノード番号が 0 番）。ヘッダーノードの最初のレコードである「ヘッダーレコード」にはカタログファイルの諸元情報が格納されていて、この中にインデックスノードを参照するためのポインタがある。ヘッダーレコードは最初のレコードなので 15 バイト目から始まり、レコードのサイズも固定なので直ぐに分かるだろう。なお、ヘッダーノードのレコード数は 3 固定で、他に「ユーザデータレコード」と「マップレコード」がありますが略です。
インデックスノードは、Ｂツリーの木を構成するノードである。そのレコードには「キー情報」と「ポインタ」が格納されている。キー情報は親フォルダのＩＤとファイル名（またはフォルダ名）である。ポインタは他のインデックスノード（またはリーフノード）にリンクするノード番号である。インデックスノードのレコード数は可変で、レコード数の分だけ他のノードにリンクする。
リーフノードは、木の末端（葉）となるノードである。レコードにはキー情報とデータが格納されている。キー情報はインデックスノードと同じ。データはファイルに関する諸情報である。エクステント情報はここにある。
マップノードには、「マップレコード」が含まれている。その中身はビットマップ（アロケーションファイルと同様）で、カタログファイル内のノードの使用状況を示す情報が記録されている。
ヘッダーノードにはＢ木の根本となるノードへのポインタ（ノード番号）が格納されていて、このルートとなるノードから（他のインデックスノードを経て）リーフノードに向かって木を探索することで、目的とするエクステント情報にアクセスするのだ。
＊＊＊
と、...そういうことだ。イメージは完璧に理解できましたね。カタカナ用語が溢れていて閉口しそうだが、難しいことは書かれていない。英語も易しくて分りやすい。Ｂツリーの探索が少し不安ですが、少なくとも、領域の先頭にあるボリュームヘッダから、カタログファイルのヘッダーレコードまではたどり着けるはずだ。あとは実物を見て考えよう！
調査対象はリーフノードだ。リーフノードのレコードに削除したファイルの格納場所を示すエクステント情報が残っていればファイルを復活できるだろう。
前世紀のパソコンで利用されていた D0s の FAT フォーマットでは、ファイルを削除した場合にファイル名の最初の 1 バイトを削除マークに変更するのみで、他の情報は残っているので、ファイルの復活は簡単だったらしい。エコロジーですね。上書きされていないという条件付きだけど。
HFS Plus もファイル削除をリーフノードをＢツリーから外すことだけで処理していたら、エクステント情報はそっくり残っているかもしれない。これが希望の星だ。
最後のエクステントオーバーフローファイルは、カタログファイルと同じくＢツリー形式のファイルで、カタログファイルのリーフノードのレコード内に格納できるエスクステント情報の個数は 8 個と固定されているため、ファイルの断片化により 9 個目以降のエスクステントができた場合に、その情報を格納するためのファイルだ。エスクステント情報が残存していないかチェックしよう。
明日は研究室でＨＤＤを調査だ。
つづく（...続きます）
＊＊＊
