030 ＨＤＤを調査しよう（２日目）
●030 ＨＤＤを調査しよう（２日目）
ときは平成Ｙ＋１年、チャレンジの２日目。今日も研究室には誰もいない。お正月だし。静かだから良いよね。
調査したい対象は明確だ。まずボリュームヘッダをみて、それからアロケーションファイルとカタログファイル、それからエクステントオーバーフローファイルだ。
外付けＨＤＤをパソコンに接続する。ＯＳがＨＤＤを認識してＨＤＤ内の領域をマウントすると「/dev/sdb1」とか「/dev/sdb2」とかのデバイスファイルが出来る。
なお、パソコンのＯＳは L1n だ。M0cに接続したら何が起こるか恐ろしいから接続してはならぬ。
ＨＤＤの領域の最初のブロック（ブロック番号 0）をリードしてボリュームヘッダを確認しよう。/dev/sdb2 をオープンして先頭から 4096 バイトを読み出せばよい。ｄｄコマンドで出来ることだけれど、後々のことを考慮して簡単で良いからスクリプトを書いておこう。
def read_allocation(num,siz=1):
f = open('/dev/sdb2','rb')
f.seek(4096*num)
b = f.read(4096*siz)
f.close()
return b
ファイル /dev/sdb2 を指定してオープン、シーク（num で指定したブロックまでジャンプ）、リード（siz で指定したブロック分を読み出す、指定がない場合は１）、ファイルをクローズ、読み出したデータをリターンする。そのままですね。
さて、b = read_allocation(0x0,1) で読み出した 4096 バイトを 16 進表示でダンプする。400h からの 512 バイトがボリュームヘッダだ（...以下、数値に h を付けて 16 進数表記を示す。「400h」なら 10 進数で 1024）。
まず最初に、400h からのシグネチャ「48h,2Bh」と、402h からのバージョン「00h,04h」が確認できる。
482Bh と 0004h は、ファイルシステムが定義する「H+」や「4」と一致する（...48h はアスキーコードで「H」で、2Bh は「+」ですね）。順調に調査がスタートし始めた。
次に、470h からと 510h からの各 80 バイトはアロケーションファイルとカタログファイルの格納情報だ。
この 80 バイトは TN1150 に記述されている「フォークデータ構造体」だ。そのの内訳はファイルサイズで 8 バイト、クランプサイズで 4 バイト、使用ブロック数で 4 バイト、エクステント情報の 8 個分で 64 バイトである（8+4+4+8*8 = 80）。
ファイルサイズは 8 バイト（＝ 64 ビット）あるので 2^64 = 10^44 バイトまで表現できる。まぁ、相当に大きなファイルでも大丈夫。
使用ブロック数はアロケーションブロックの数のことで、アロケーションブロックが 4096 バイトの場合、4096 * (2^32) = 10^30 バイトとなる。つまり、ファイルサイズより使用ブロック数の方が先に限界になる。Wiki などでは HFS Plus の最大ファイルサイズを 8EiB（＝2^60）と説明しているがどうやって実現するのだろう？ アロケーションブロックのサイズを大きくすればよいのかな。えとー、１ブロックを (2^60)/(2^32) = 2^28 = 268,435,456 バイトにすればよい。最小単位が２６８ＭＢ？ あははは
なお、使用ブロック数はエスクテント情報のブロック数の合計と一致しているはず。一致しない場合はエスクテントオーバーフローファイルに記録されているのだろう。クランプサイズは、...後述しよう。
このＨＤＤの場合、アロケーションファイルとカタログファイルのフォークデータは、
{ 'allocationFile':
{ 'logicalSize': 61034496,
'clumpSize': 61034496,
'totalBlocks': 14901,
'extents': {0: (1, 14901), 1: (0, 0), 2: (0, 0), 3: (0, 0),
4: (0, 0), 5: (0, 0), 6: (0, 0), 7: (0, 0) } } }
{ 'catalogFile':
{ 'logicalSize': 308281344,
'clumpSize': 308281344,
'totalBlocks': 75264,
'extents': {0: (885303, 75264), 1: (0, 0), 2: (0, 0), 3: (0, 0),
4: (0, 0), 5: (0, 0), 6: (0, 0), 7: (0, 0) } } }
であった。
どちらも 1 個のエクステントで格納されていて、アロケーションファイルは (#1, 3A35h)、カロログファイルは (#D8237h, 12600h) と分かる。念の為だけど、(#D8237h, 12600h) とはアロケーションブロック番号 D8237h から 12600h 個のブロックからなるエクステントだ。
まず、カタログファイルにアクセス。先頭ブロック #D8237h の 4096 バイトを読み出す。
b = read_allocation(0xd8237,1) ですね。
ここまでは読み出したデータを 16 進表示してテキストファイルにした後、エディタでフィールド毎に改行して解釈できたが、この先は難しくなるだろう。読み出したデータのフィールド名と値を表示するスクリプトを組んでおこう。
＊＊＊
TN1150 で解説されている構造体の情報を変換して、これをスクリプトに取り込んで再帰的にデータを表示させる。
ボリュームヘッダーの構造体の情報は次の様になる。長いので中間は省略した。正確には TN1150 を参照して欲しい。
s_VolumeHeader = [ [ "VolumeHeader", [
[ "[skip1024]", bUInt8*1024 ],
[ "signature", p_str16 ],
[ "version", bUInt16 ],
[ "attributes", bUInt32 ],
[ "lastMountedVersion", bUInt32 ],
[ "journalInfoBlock", bUInt32 ],
[ "createDate", p_date32 ],
# ...,
[ "allocationFile", s_ForkData ],
[ "extentsFile", s_ForkData ],
[ "catalogFile", s_ForkData ],
[ "attributesFile", s_ForkData ],
[ "startupFile", s_ForkData ] ] ] ]
bUInt8 など b で始まる変数はバイト数を示す。bUInt16 なら 2 バイトです。
p_ で始まる p_str16 や p_date32 などは関数です（...関数なのに p とは）。p_date32 は次の関数です。日付情報は大きな整数ではなくて、年月日時分秒として表示したいですよね。
def p_date32(x):
t1 = get_num(x,0,4)
t2 = datetime(1904,1,1) + timedelta(seconds=t1)
t3 = t2.strftime('%Y/%m/%d %H:%M:%S')
return t3, 4
同じ感じで、"signature" も文字列にしました。"journalInfoBlock" はアロケーションブロック番号なので 16 進表示の方が良いですかね。表示の際に変換しても良いですけど。スクリプトでデータを処理する際は数値の方が便利ですから。まあ後で考えよう。
s_VolumeHeader や s_ForkData の様に s_ で始まる変数は TN1150 に記載されている構造体を変換したもので、s_ForkData だと
s_ForkData = [
[ "logicalSize", bUInt64 ], [ "clumpSize", bUInt32 ],
[ "totalBlocks", bUInt32 ], [ "extents", p_ExtentRecord ] ]
と定義してます。p_ExtentRecord は、s_ExtentRecord でも記述できなくはないのですが...、
s_ExtentRecord = [
[0, s_extent], [1, s_extent], [2, s_extent], [3, s_extent],
[4, s_extent], [5, s_extent], [6, s_extent], [7, s_extent] ]
s_extent = [
["startBlock", bUInt32], ["blockCount", bUInt32] ]
これだと、データを表示したときに煩雑だと感じたので関数を用意しました。
def p_ExtentRecord(x):
r = {}
for i in range(8):
a = i*2*bUInt32
r[i] = [get_num(x,a,bUInt32), get_num(x,a+bUInt32,bUInt32)]
return r, bUInt32 * 16
これを適当にデコーダを作って（...、
def s_decode(x,s,p=0): # dict decode version
r = {}
for m,n in s:
if type(n)==list: t,q = s_decode(x[p:],n)
elif "__call__" in dir(n): t,q = n(x[p:])
elif type(n)==int: t,q = get_num(x,p,n),n
r[m] = t; p += q
return r,p
とかですね、はい、作りました）、
x = read_allocation(0,1)
r = s_decode(x, s_VolumeHeader)[0]
print r
とすればボリュームヘッダを表示できる。
カタログファイルのノードも同じように構造体の情報を取り込んで表示できるようにする。デコーダはその日の気分で違うので（...、辞書だと順番が保持されないので、リストにする等。データ処理するときには辞書の方が便利だけど）、
def catalogFile_leafNode(x):
# r = s_decode_yesterday(x, s_catalogFile_Node)[0]
r = s_decode_today(x, s_catalogFile_Node)[0]
return r
の様に関数で包んで利用する場合が多いです（...何の話か？）。
アトリビュートファイルの場合の s_attributeFile_Node を [048] で具体的に解説しているので参照してね！
＊＊＊
はい。カタログファイルの話に戻ります。
カタログファイルの先頭（ノード番号 0）はヘッダーノードで、この内にレコードが 3 個含まれていて、その 1 つ目がヘッダーレコードだ。ヘッダーレコードによると、ノード数は 9300h で、空きノード数は 8C80h、そしてノードサイズは 4096 バイトではなく、8192 バイト（8KB）だった。事前調査と少し違う。オフセット情報も合わない。
カタログファイルは 12600h 個のブロックがあり、1 ノード 8KB とするとノードの数は 9300h 個となるから、ヘッダーレコードのノード数の情報と一致する。
1 ノード 8KB として、カタログファイル内の全ノードを探索して、オールゼロのノードをカウントすると、
c = [read_allocation(0xd8237+n*2,2).count('\0') == 8192
for n in range(0x9300)]
print sum(c)
...と、8C80h 個あり、これも空きノード数と一致する。
私「ふーむ、ＨＤＤが大容量なのでノードサイズが調整されて大きくなったのかもね」
TN1150 を読み直すと、カタログファイルのノードサイズは M0cOSX では 8KB との記述を発見、疑問は解消された。
空きノード数とオールゼロのノード数が一致ということは、削除ファイルに対応するノードは全てがゼロクリアされているのか。これはいきなりショックだ。
＊＊＊
ノードのサイズは 2 ブロックと分かったので、b2 = read_allocation(0xd8237,2) で読み直す。するとノードの末尾のオフセット情報も正しく確認できた。
n 番目のノードは read_allocation(0xd8237+n*2,2) で読み出せ、n を for n in range(0x9300) で回せば、全ノードをノード番号の順で読み出せる。これで確定かな。
私「あれ、Ｂツリーの探索は不要だったのね。まあいいけど」
使用中のノードは、(1647+16+1) 個ある。ノード先頭部分の情報でノードの種別をカウントすると、1647 個はリーフノード、16 個はインデックスノード、1 個はヘッダーノードとなった。
なお、マップノードは見つからなかった。TN1150 を読み直すとちゃんと説明されていた。ヘッダーノードの 3 個目のレコードであるマップレコードに収まらない場合にマップノードが作成されるとのこと。ヘッダーノード内のマップレコードは「ノードサイズ - 256 バイト」つまり 8192 - 256 = 7936 バイトある。7936*8 = 63488 ビットで、ノード数は 9300h (=37632) なのでヘッダーノードだけで間に合う。
ヘッダーノードのマップレコードを見ると、先頭は FFh が連なっていて、その後 00h が続く中に飛び飛びに 10h や 02h などが記録されている。00h が続く中にある 10h は、昔はこの辺も使用中で FFh だったのが、ファイル削除により大部分が未使用となった中で、少しだけ残ったノードを示すものだ。加えてマップレコードで０となっているノードは、ゼロクリアされていることを既に確認してしまっている。ここにノードがあったのか、今はもうないのか、とファイル削除の痕跡を見るのはつらい。暗雲。不運。
＊＊＊
マップレコードの様子を図にして見ました。Fig.G1 です。先頭の 8192 ビット分を横 128 縦 64 にします。128 * 64 = 8192 です。横軸の値を X、縦軸の値を Y とすると、(X,Y) のポイントがマップレコードの X+Y ビット目に対応します。
青色が使用中のノードです。ぽつんと散在している青色が寂しい感じですね。
＊＊＊
リーフノードのレコードの 1 つ 1 つに、1 つのファイル（またはフォルダ）の情報が格納されている。「スレッド」というものがあるらしいが関係なさそうなので省略する。
そこで、リーフノードのレコードを順次、表示していく。ファイルは 34773 個、フォルダは 28 個あった。これらは皆現存するファイルやフォルダの情報だ。使用中のノードのうち 183 個にゴミ情報が残っていたが、レコードのオフセット情報の残骸と思われて、エスクステントの情報では無さそうだった。
現存ファイルのエクステント数は多くて 6 個で、エクステントオーバーフローファイルには情報は記録されていなかった。システム（ＯＳ）がデフラグをしてるのではなくて、このＨＤＤはファイルの追加がほとんどで、削除することは少く、つまりあまり使い込んでいないためだろうか。
削除されたファイルの情報、特にエクステントの情報を探したが見つからなかった。綺麗にゼロクリアされている。希望の星だったのに。
＊＊＊
カタログファイルの現状から推測すると、ファイルの削除により、削除ファイルに対応するリーフノードのレコードが 1 つ削除される。リーフノードの先頭部分にあるレコード数を 1 減算し、削除するレコード以降の分を前方に移動して、残った空き部分はゼロクリア。レコードを移動したらノード末尾のオフセット情報も修正する、と推察される。ただオフセット情報も 1 個減るのだがそれはゼロクリアしていない可能性あり。
そして、リーフノードからレコードが削除されてレコード数が 0 個になると、リーフノードも削除される。インデックスノードの対応するレコードを削除する等してリーフノードをＢツリーから外す。外したリーフノードはゼロクリアして未使用ノードとするようだ。
ノードを開放する前にゼロクリアすることはセキュリティ的に良い習慣だ。
レコードは可変長なこともあり、削除したレコードを残すと検索の邪魔になり、ファイルシステムの性能に影響するのだろう。階層的に構成されたファイルシステムを効率的に検索できるようにＢツリー構造を導入したのだから性能を追求すべきだろう。そう理解できる。
でも空になったリーフノードはＢツリーから外すだけでよくてゼロクリアしなくてもよいのにと恨めしい。たとえゼロクリアしなくても最後の 1 レコードの情報しかないとしても。
＊＊＊
カタログファイルを調べていて、ちょっと驚いたことがある。
ファイルとフォルダにはユニークな番号（CNID）が付与されている。特にフォルダにユニークな番号を付与することは、ルートフォルダからの全フォルダ名を列挙（いわゆるフルパス名）しなくても同名フォルダを区別できるので、インデックスノードの探索効率が向上して有用だ。Ｂツリーを探索する際に使うキー情報に入っている親フォルダＩＤが CNID だ。
でもファイルにまで番号を振らなくてもと思う。CNID を使うと、ファイル名を変更して別のフォルダに移動しても、なんならファイルの中身を書き換えても、システムからファイルを追跡できることを意味する。パソコンに基本的人権があるとしても、流石にファイルには人権は無いだろう。けれども、パソコンのＨＤＤの中の情報はパソコンやその所有者のものであり、パソコンメーカーやＯＳメーカーがバックドアーを設けてＨＤＤの中の情報を検閲するようなことは許してはならない！
私「...あれ、何をしていたんだったかな」
なんだか荒ぶっていたのに気がついた。八つ当たりでしょうか。コーヒーブレークしよう。
＊＊＊
次は、アロケーションファイル。アロケーションファイルは先頭ブロックが #1 で、ここからの 3A35h ブロックである。
アロケーションファイルの 3A35h*4096*8 = 1D1A8000h ビットで全アロケーションブロックと対応する。アロケーションブロックの全部にアクセスするということは、ＨＤＤのほぼ全体をアクセスすることになるので、とても時間がかかると予想される。少なくとも数時間か。１０時間はかからないはず？
私「疲れたしスクリプトを作ったら帰ろう」
とりあえずアロケーションファイルを読んで、ビットが 0 となっているものを探して、対応するアロケーションブロックを調べて何かデータが残っているブロック、つまり削除ファイルのデータの残骸を含むブロックの番号を出力しよう。
私「標準出力に出して、リダイレクトしてファイル保存でいいよね？」（...ひとり言が増えてる）
for blk in range(0x3a35): # 0〜3A34hまでループ
x = read_allocation(1+blk,1) # アロケーションファイルからリード
for byt in range(4096): # 0〜4095までループ
d = "{:08b}".format(ord(x[byt])) # 二進数に変換
for bit in range(8): # 0〜7までループ
if d[bit]=='0': # ビットが0かをチェック
iy = blk*4096*8+byt*8+bit # ブロック番号を計算
y = read_allocation(iy,1) # アロケーションブロックをリード
check_block(y,iy) # ブロックの内容をチェック
私「アロケーションファイルから 1 バイトを取り出して、ＭＳＢから順に、0 だったらアロケーションブロックをアクセス、バイトを二進数にしたら 0 番目がＭＳＢだから（カチャカチャ）」（...ＭＳＢは最上位ビットです）
だいたいデバックできた。スクリプトをＲＵＮ。
つづきは明日。今日は帰ろう（...なお、お気付きの方も多いと思いますが、これでは全然処理が進まないので駄目です。しばらく様子を見ていたら現実的ではないと分かり、スクリプトを組み直すことになります。全く帰れませんでした）。
＊＊＊
