042 余談になります（続２）
●042 余談になります（続２）
友「引き続き、提供は私になります。今回はエクステントオーバーフローファイルです。」
＊＊＊
エクステントオーバーフローファイルについて説明したい。
今まで、エクステントオーバーフローファイルについては、ほとんど注目していなかった。ファイル削除後の現状ではエクステントオーバーフローファイルは空っぽだったからだ。
それが、ジャーナルファイルを分析するとこで、エクステントオーバーフローファイルのノードの情報が幾つも得られることが分かった。これは分析せざるを得ないですね。
＊＊＊
エクステントオーバーフローファイル（...長いですね、エクステントＯＶファイル？、エクステントファイルと呼びましょう。良いですね）はカタログファイルと同様なＢツリー構造です。
固定長のノードの連続で構成されていて、ノードの先頭部分は固定の 14 バイトで、その内容はカタログファイルと同じです。ノードの末尾にはオフセットの情報があり、先頭部分に含まれるレコード数とこのオフセットを使って、レコードにアクセスできます。
最初のノード（...0 番のノード）はヘッダーノードで、この中にＢツリーのルートとなるノードの番号が格納されています。
ルートノードの配下にはインデックスノードやリーフノードができます。これがＢツリーです。ルートノードがそのままリーフノードであることも、ルートノードの直下にリーフノードがあることもあるのでしょう、多分。
インデックスノードのレコードは、キー情報 12 バイトとポインタ（ノード番号） 4 バイトです。固定長ですね
リーフノードのレコードは、キー情報 12 バイトとデータ（エクステント情報）の 64 バイトです。あ、カタログファイルではデータの先頭にレコードタイプの情報が付いていたのですけれども、リーフノードのレコードには無いですね。そのままエクステント情報が入っています。1 種類しかないから大丈夫です。
カタログファイルとの違いは、あまり無いのですが、ノードのサイズが 4096 バイトであること（カタログファイルは 8192 バイトでした）、リーフノードのレコードには、データとして 9 個目以降のエクステント情報があり、その所有者のファイルＩＤ等が含まれていること（ファイル名などの情報はない）程度です。
あ、ということは、キー情報の中身は違いますね。カタログファイルではキー情報は親フォルダＩＤとファイル名でしたが、エクステントファイルのキー情報は、ファイルＩＤとフォークタイプと開始ブロック番号です。
ファイルＩＤは、このエクステント情報の所有者を示し、開始ブロック番号は、このエクステント情報のファイル内での相対的な開始位置を示すブロック番号です。フォークタイプはフォークのタイプです（？）。
あとは、...Ｂツリーの検索方法などもカタログファイルと同じですね。キー情報は、ファイルＩＤ＞フォークタイプ＞ブロック番号の順で比較されるそうです。はい。
＊＊＊
早速、ジャーナルファイルから、エクステントファイルのデータを取り出して行きましょう。
ジャーナルファイルは、アロケーションブロックの #3A37h 〜 #D236h にあって、#3A37h に start/4096 (=010DBh) を加えたところが最古のデータでした。#(3A37h+010DBh) からジャーナルファイルの末尾 #D236h までと、先頭の #(3A37h+1) から #(3A37h+010DBh-1) までを調べれば、ジャーナルファイルを一周したことになります。
ブロックリストヘッダーから次のブロックリストヘッダーまでのブロックが目的とするデータ保管場所で、このブロックを出力します。その際、ブロックリストヘッダーのブロック情報をみて、保管データのアロケーションブロック番号が #D237h 〜 #E036h の範囲にあるものを選びます。この範囲がエクステントファイルなのです（...[052] も読んでね）。
アロケーションブロック番号が #D237h なら、エクステントファイルのヘッダーノードです。
最初に見つかったヘッダーノードは次のものでした。
0 = {'desc': { 'fLink': 0,
'bLink': 0,
'kind': 1,
'height': 0,
'numRecords': 3,
'reserved': 0 },
'record': {
0: { 'treeDepth': 2,
'rootNode': 3,
'leafRecords': 547,
'firstLeafNode': 5,
'lastLeafNode': 1,
'nodeSize': 4096,
'maxkeyLength': 10,
'totalNodes': 3584,
'freeNodes': 3570,
'reserved1': 0,
'clumpSize': 14680064,
'btreeType': 0,
'keyCompareType': 0,
'attributes': 2,
'reserved3': 0, },
1: { 'data': '00000000...0000' },
2: { 'data': 'fffc0000...0000' } },
'offset': [ 14, 120, 248, 4088 ] }
ヘッダーノードのレコードは 3 個と決まっていて、その１つ目にルートとなるノードの番号等を含むエクステントファイルの諸情報があります。２つ目は、利用者情報らしいのですがオールゼロです。３つ目はマップレコードです。ノードの使用中・未使用を示すビットマップです。
'totalNodes' の 3584 と 'freeNodes' 3570 の差 3584-3570=14 が使用中のノード数でしょう。マップレコードの fffc0000... で、最初の 14 個が使用中と分かります。1 個はヘッダーノードとして、残り 13 個はインデックスノードとリーフノードなのでしょう。
あとは、ルートノードは 3 番で、Ｂツリーの高さは 2 です。なので、ルートノードの下に 12 個のリーフノードがあるようです。リーフノードの最初は 5、最後は 1 ですね。それとリーフノードのレコードの合計は 547 個みたいです。うむむ。
これらの情報が、どのように変わっていくのかを図にして見ましょう。次の Fig.J4 です。上段は、ルードノード番号、リーフノードの最初と最後、Ｂツリーの深さで、下段がリーフノードのレコード数です。
縦軸は各々の値で、横軸は見つかったヘッダーノードの通し番号です。0 〜 83 がジャーナルファイルの１つ目の区間で、84 〜 139 が２つ目です。140 〜 144 が３つ目です（...２つ目の区間は 80〜 かも）。
１つ目の区間では、ルートは３番、リーフノード先頭は 5 番、最後は 1 番で、レコード数のみが単調に増えています。それが２つ目に入り次第、イベンド 85 で０個になっています。何をしたんでしょうか？、デフラグした覚えはないそうですが...。
２つ目の区間では、ルートノード = リーフノード先頭 = リーフノード末尾 = １番のノードという状態で、リーフレコードが増えています。なるほどですね。
そして、イベンド 105 で、リーフノード先頭とリーフノード末尾が分かれて（...図では分からないですが、先頭が 2 で末尾が 1 です）、ルートノードは 3 番になりました。
３つ目の区間では、これらは削除されました。
＊＊＊
エクステントファイルのレコードは、２つ目の区間の最初で全部削除されて、その後のデータは全部ジャーナルファイルに保管されている、ってことでしょうか。だとしたら、意外に良い感じ。
エクステントファイルが単独で更新されていたら話は別ですが。無いといいなー
＊＊＊
ヘッダーノード以外のノードも見てみましょう。
ヘッダーノードを全部みたら、使用されているノードは 0 〜 14 の 15 個だと判明したので、イベンド毎にこれらノードのレコード数を図にしました。次の Fig.J5 です。
縦軸はノード番号で 0 〜 14 です。横軸はイベンドで、Fig.J4 と同じです。レコード数 0〜52 を輝度表示していて、-10 はレコード数が不明な部分です。
0 番はヘッダーノードなのでレコード数は 3 です。
１つ目の区間では、更新があった 5 個のノード以外は情報がなくて紫色（=-10）になっています。
主に 1 番のノードでレコードが増えていて、52 個を超えたところで、13 番のノードにレコードが移動している様子が見て取れます。52 > 40、52 > 46、52 > 50、52 > 51 など移動するレコード数はバラバラです。何故でしょう。
13 番のノードもレコード数が 52 個で一杯になったためか、イベント 35 ではインデックスノードが 1 つ増えて、1 番のノードは 52 > 26 と変化しました。丁度半分。14 番のノードのレコードは 27 個です。以後は 1 番から 14 番のノードに移動しています。
リーフノードのレコードは 76 バイトで、先頭部分（14バイト）とオフセット情報（2+2*Nバイト）があるので、52 個だと 14 + 2 + (76+2)*52 = 4072 バイト。これで一杯です。
２つ目の区間に入り次第、1 〜 14 番のノードが順番にゼロクリアされています。その後は、1 番のノードで、レコード数が増加して、52 個を超えたところで、２つのノードに分割（1 番＝ 28 個、2 番＝ 27 個）して、3 番がルートノードになっています。
ゼロクリアが始まったのは、イベント 80 なので、２つ目の区間は 80〜 が正しいのかも、...。
その後も、1 番のノードのレコード数が 52 個を越える毎にレコードが移動されて、更には 4 番、5 番のノードが使用されるようになりました。
３つ目の区間では、これらは削除されました。
＊＊＊
友「Ｂツリーはこのように振る舞うのかと、興味深いですね。ノードが一杯になってレコードを移動する時は移動先のレコード数と足して２で割る感じかも。逆に、一杯にならないと移動しないのかな。レコード数が減る場合は、０個になってノード自体が消える場合の他は、調整しないのでしょうか、うーむ」
＊＊＊
レコードの内容を見てみましょう。ヘッダーノードは既に確認したのですが、インデックスノード（...実質ルードノードですね）とリーフノードのレコードが気になります（...わたし気になります、って）。
最初に見つかったインデックスノードです。１つ目の区間のイベント 10 あたりで見つかりました。
3 = {'desc': {'kind': 0, 'reserved': 0, 'fLink': 0, 'numRecords': 12, 'height': 2, 'bLink': 0}
'record': {
_0: {'node': _5, 'fileID': 20601, 'forkT': 0, 'pad': 0, 'sBlock': _5369, 'keyL': 10},
_1: {'node': _2, 'fileID': 20602, 'forkT': 0, 'pad': 0, 'sBlock': _6121, 'keyL': 10},
_2: {'node': _4, 'fileID': 20602, 'forkT': 0, 'pad': 0, 'sBlock': _8169, 'keyL': 10},
_3: {'node': _6, 'fileID': 20602, 'forkT': 0, 'pad': 0, 'sBlock': 12277, 'keyL': 10},
_4: {'node': _7, 'fileID': 20602, 'forkT': 0, 'pad': 0, 'sBlock': 16481, 'keyL': 10},
_5: {'node': _8, 'fileID': 20602, 'forkT': 0, 'pad': 0, 'sBlock': 19469, 'keyL': 10},
_6: {'node': _9, 'fileID': 20602, 'forkT': 0, 'pad': 0, 'sBlock': 22697, 'keyL': 10},
_7: {'node': 10, 'fileID': 20602, 'forkT': 0, 'pad': 0, 'sBlock': 27349, 'keyL': 10},
_8: {'node': 11, 'fileID': 20602, 'forkT': 0, 'pad': 0, 'sBlock': 31689, 'keyL': 10},
_9: {'node': 12, 'fileID': 20602, 'forkT': 0, 'pad': 0, 'sBlock': 36257, 'keyL': 10},
10: {'node': 13, 'fileID': 20602, 'forkT': 0, 'pad': 0, 'sBlock': 40369, 'keyL': 10},
11: {'node': _1, 'fileID': 20602, 'forkT': 0, 'pad': 0, 'sBlock': 42857, 'keyL': 10}},
'offset': [ 14, 30, 46, 62, 78, 94, 110, 126, 142, 158, 174, 190, 206 ] }
高さ 2 なのでルートですね。ヘッダーノードのルートノードの番号とも一致します。
12 個のレコードがあり、順番はバラバラですが（'node' をみると）1 と 2、4〜12 番のノードをポイントしています。これらはリーフノードなのでしょう。先頭ノードは 5 番、末尾ノードは 1 番と、ヘッダーノードの情報と一致します。ファイルＩＤは 20601 と 20602 の２つだけなのでしょうか。
インデックスノードのレコードは 16 バイトなのでオフセットの情報は 16 刻みで増えています。等差数列。
ジャーナルファイルでみつかったエクステントファイルのデータからは、インデックスノードはルートだけで、他は全部リーフノードでした。
＊＊＊
リーフノードも見てみたのですが、高さが 1 で、ノード番号の代わりにエクステント情報が入っているだけの違いなので省略します。
エクステントの分布を図にして見ましたが、見た目が良くないのでボツです。すごく断片化していることは把握できました。ほとんどのポイントが孤立しています。
アロケーションブロック番号の最小は (0EB0,3003,7) で、最大は (1602,1166,2) でした。この範囲で 54728 個のブロックが、エクステントファイルにエクステント情報として記録されています。
Fig.F1 と Fig.F2 で見た空きブロックの分布との違いは、何でしょうか。謎を感じます。
ジャーナルファイルで最初に発見したヘッダーノードで、リーフノードのレコード数は既に 547 個あり、１つ目の区間では 100 個も増えていないことを考えると、ジャーナルファイルに残っていない消えた記録が相当ありそうです。５倍くらいはあるのかも？
アロケーションファイルをもっと詳しく調べるべきでしょうか。検討しましょう。
＊＊＊
１つ目の区間でエクステントファイルにデータが格納された原因は何か、断片化しているファイルを追ってみましょう。Fig.J4 と Fig.J5 で見たように、１つ目の区間で増えたエクステントファイルのレコードが２つ目の区間の最初で消えているのも謎でした。調べたら何か分かるでしょうか。
１つ目の区間で、レコードのキー情報に含まれるファイルＩＤを全部集めてみたところ、20601 と 20602 の２つだけでした。
そして、ジャーナルファイル中のカタログファイルのデータにこのファイルＩＤを持つファイルが無いか探したところ、...見つかりました。容疑者は、
"store.db"
と
".store.db"
です。
容疑はこの 2 つファイルがアロケーションブロックを取り合った為、断片化してエクステントファイルにエクステント情報が格納された疑いです。ファイルＩＤは 1 つのＨＤＤ内ではユニークなＩＤですし、このＨＤＤはＩＤの再利用はされていないので、人違いの可能性はまず無いです。
"store.db" ファイルは、ジャーナルファイルの最初の記録は、10/28 16:36:50 で 181,522,432 バイトでした。これより前から書込みが始まっていたようですがジャーナルファイルには残っていません。最後は 11/26 23:34:50 で 203,362,304 バイトになりました。ブロック数は 49649 ですが、カタログファイル内には 2025 + 220 + 444 + 488 + 604 + 484 + 580 + 524 = 5369 ブロック分だけが記録されています。残りはエクステントファイルでしょう。
".store.db" ファイルは、最初は 10/28 16:55:16 で 182,079,488 バイトでした。最後は 11/26 23:34:50 で 203,362,304 バイトです。2 つのファイルのサイズが同じになったのは偶然でしょうか。ブロック数は 49649 で、カタログファイル内には 4273 + 4 + 8 + 16 + 12 + 8 + 8 + 8 = 4337 ですが、そのほとんどは１つ目のエクステントです。
"store.db" ファイルのカタログファイル内のエクステント情報
0: [119556085, 2025], 1: [120330936, 220], 2: [121106401, 444], 3: [121543717, 488],
4: [121746846, _604], 5: [121749378, 484], 6: [122660822, 580], 7: [124385872, 524]
".store.db" ファイルのカタログファイル内のエクステント情報
0: [123123683, 4273], 1: [123131800, __4], 2: [123177987, __8], 3: [123181802, _16],
4: [123211211, __12], 5: [123213784, __8], 6: [123223616, __8], 7: [123226185, __8]
ファイル名を見ただけで有罪を宣言したくなりますが、エクステント情報をみると、互いにアロケーションブロックを取り合っているようには見えません。うーむ。
＊＊＊
ジャーナルファイルの１つ目の区間はファイルを書き込んでいた時期でした。これらの書き込んだファイルの間で、"store.db" ファイルが断片化された可能性が考えられます。
ファイルＡの書込み、ファイルＢの書込み、...、"store.db" ファイルの更新（サイズ増加）、ファイルＣの書込み、"store.db" ファイルの更新（サイズ増加）、...という想定です。
ジャーナルファイルのデータから更新状況を分析してみましょう。
まず、アロケーションファイルです。ファイルが書き込まれるとカタログファイルの更新と共に、アロケーションファイルも更新されます。当然ですね。
ジャーナルファイルの１つ目の区間の最初の５回では、アロケーションファイルの 14EDh が更新されています。他にも更新されたデータはありますが、とりあえずは 14EDh に注目してみます。
最初の５回の更新で、14EDh に対応するアロケーションブロック 4096*8 個のうち、空きブロックの数は 20969 > 12568 > 5319 > 951 > 4 と減って行きます。ブロックをダンプして目視確認すると、前半には主に FFh が並び、後半は 00h となっていました。前から順番に使用されているようです。
そして、同時に更新されたカタログファイルとエクステントファイルのデータからエクステント情報を取り出して、使用しているアロケーションブロックを確認すると、14EDh のアロケーションブロックの先頭から順に並んでいました。
この５回分を次に示します。
(1) : 10/28 16:55:16 : Catalog node=841, Extent node=1
CT (14EA,2545,5)-(14ED,1125,5) OV (14ED,1125,6)-(14ED,1126,5)
GAP(14ED,1126,6)-(14ED,1127,1)
CT (14ED,1127,2)-(14ED,1473,5) OV (14ED,1473,6)-(14ED,1475,1)
(2) : 10/28 16:55:47 : Catalog node=841, Extent node=1
CT (14EA,2545,5)-(14ED,1125,5) OV (14ED,1125,6)-(14ED,1126,5)
GAP(14ED,1126,6)-(14ED,1127,1)
CT (14ED,1127,2)-(14ED,1473,5) OV (14ED,1473,6)-(14ED,1475,1)
CT (14ED,1475,2)-(14ED,2524,2) OV (14ED,2524,3)-(14ED,2525,2) <- New (+2 files)
(3) : 10/28 16:56:17 : Catalog node=841, Extent node=1
CT (14EA,2545,5)-(14ED,1125,5) OV (14ED,1125,6)-(14ED,1126,5)
GAP(14ED,1126,6)-(14ED,1127,1)
CT (14ED,1127,2)-(14ED,1473,5) OV (14ED,1473,6)-(14ED,1475,1)
CT (14ED,1475,2)-(14ED,2524,2) OV (14ED,2524,3)-(14ED,2525,2)
CT (14ED,2525,3)-(14ED,3430,3) OV (14ED,3430,4)-(14ED,3431,3) <- New (+2 files)
(4) : 10/28 16:56:47 : Catalog node=841, Extent node=1
CT (14EA,2545,5)-(14ED,1125,5) OV (14ED,1125,6)-(14ED,1126,5)
GAP(14ED,1126,6)-(14ED,1127,1)
CT (14ED,1127,2)-(14ED,1473,5) OV (14ED,1473,6)-(14ED,1475,1)
CT (14ED,1475,2)-(14ED,2524,2) OV (14ED,2524,3)-(14ED,2525,2)
CT (14ED,2525,3)-(14ED,3430,3) OV (14ED,3430,4)-(14ED,3431,3)
CT (14ED,3431,4)-(14ED,3975,7) OV (14ED,3976,0)-(14ED,3977,3) <- New (+3 files)
(5) : 10/28 16:57:17 : Catalog node=841, Extent node=1
CT (14EA,2545,5)-(14ED,1125,5) OV (14ED,1125,6)-(14ED,1126,5)
GAP(14ED,1126,6)-(14ED,1127,1)
CT (14ED,1127,2)-(14ED,1473,5) OV (14ED,1473,6)-(14ED,1475,1)
CT (14ED,1475,2)-(14ED,2524,2) OV (14ED,2524,3)-(14ED,2525,2)
CT (14ED,2525,3)-(14ED,3430,3) OV (14ED,3430,4)-(14ED,3431,3)
CT (14ED,3431,4)-(14ED,3975,7) OV (14ED,3976,0)-(14ED,3977,3)
CT (14ED,3977,4)-(14EE, 47,7) <- New (+2 files)
簡単に説明します。「CT (14EA,2545,5)-(14ED,1125,5)」の CT は、カタログファイルからのエクステント情報であることを意味します。OV だとエクステントファイルから、です。
「(14EA,2545,5)」はアロケーションブロック番号で 14EAh*4096*8 + 2545*8 + 5 のことです。２つのブロック番号によってエクステントの範囲を示しています。GAP はブロック番号が飛んでいる部分です。
(1) では、エクステント情報をまとめると、(14EDh,0,0)-(14EDh,1475,1) の範囲が（GAP の 4 ブロックを除いて）使用されています。
残りの (14EDh,1475,2)-(14EDh,4095,7) に GAP の４を加えると、アロケーションファイルから求めた空きブロック数 20969 と一致します。
...、念の為の検算です。(0x14ED*4096*8 + 4095*8 + 7) - (0x14ED*4096*8 + 1475*8 + 2) + 4 = 20969 です。OK です。
(2) では、(1) の使用範囲の後ろに、２ファイル分（カタログファイルのリーフノードで２レコード分）のデータが書き込まれて、その後ろに ".store.db" の増加した８ブロックが書き込まれています。
(3)〜(5) でも同様に 2〜3 のファイルが書き込まれた後に、".store.db" のデータが 8 ブロックあるいは 12 ブロック書き込まれています。
このような状況で ".store.db" ファイルは断片化したようです。想定した通りでした。
(1)〜(5) の更新時刻は約 30 秒間隔です。メモリ上で書込みの処理を行って、ある程度、溜まったら実際にＨＤＤに書き込むのですかね。遅延書込み？
＊＊＊
この時に書き込んでいたファイルは、比較的小さなファイルだったので、ファイル自体は断片化していなくて（GAPの部分を除き）、1 つのエクステントに書き込まれています。
でも、数ギガバイト程のファイルだと、ファイルの書込み中に ".store.db" ファイルが割り込んで邪魔になりそうです。
8 ブロックとか 12 ブロックのギャップが発生していたら ".store.db" ファイル等を疑いましょう。
＊＊＊
友「それで、".store.db" って何、消えた理由は？」
私「Zzzz」
＊＊＊
ジャーナルファイルによれば、このＨＤＤは 12/8 の７時５９分４３秒頃に M0c に接続された。
当初は ".store.db" は存続していたが、８時１分１３秒を最後に存在が確認できていない。そして、８時１分１６秒に同名のファイルが同じフォルダの中に作成されている。ファイルＩＤが異なるので別人だ。"store.db" も別人に作り変えられていた。
多分、始末されたのだろう。...、誰がヤッたのか、その理由や動機は？
＊＊＊
友「ジャーナルファイルは見ていた！というタイトルで、サスペンス小説書けないかなー」
私「Zzzz（...どんな？）」
友「えーと、...主人公はマトリの人で、現行犯で逮捕したのだけど、上司が証拠不十分だから不起訴と言ってて、困っていて、差し押さえたアイホンから通話履歴とか連絡先を確保したいのだけれどもロックされていて、指紋ロックは未設定でパスコードは黙秘されて、一緒にノートも差し押さえてあって、ログインはできないけど、ＨＤＤをぶっこ抜いてアクセスできたけれども、欲しかったアイホンとの同期ファイルは削除されていて、このままでは！と言う、その時、ジャーナルファイルは見ていた、...とか。
冤罪を晴らすパターンもできそうな。裁判で、権力者側が証拠となる写真のファイルを捏造していて、被告は有罪になりそうになっていて、弁護士さんは頑張っているけど捏造と見破れなくて、もう時間切れで、その時、ジャーナルファイルは見ていた」
＊＊＊
