【お知らせ】プログラミング記事の投稿はQiitaに移行しました。

巨大ファイルのマッピング

id:n7shi:20101204でUNIX V6のファイルシステムを分析しましたが、リバースエンジニアリングをソースで裏付ける手法だったため漏れがありました。以下の記事で二重間接参照の存在を知りました。

SIMH上のUNIX V6で実験して確認しました。

実験 1(直接参照→間接参照)

SIMH上でダミーファイルを作成します。/dev/zeroが存在しないためディスクの生データを利用しています。

# dd if=/dev/rk0 of=test count=8

1ブロックが512バイトのため、上の例では 8 * 512 = 4KB です。inodeからは8つのブロック(addr)が参照されますが、一番単純なもの(直接参照)ではセクタを直接参照しているため 8 * 512 となります。id:n7shi:20101204で作成した自作ツール(要Silverlight)で読み込んでaddrを確認します。

size: 4096
addr: 1758,1736,1739,1742,1745,1748,1751,1752

SIMH上で1バイト増やします。

# echo "" >> test

これを自作ツールで確認します。

size: 4097
addr: 1755,0,0,0,0,0,0,0

間接参照ブロックにまとめられたことが確認できます。ディスクイメージをバイナリエディタで確認します。1755というのはセクタ番号を示すため 1755 * 512 = 0xdb600 となります。

000DB600 DE 06 C8 06 CB 06 CE 06-D1 06 D4 06 D7 06 D8 06
000DB610 E1 06 00 00 00 00 00 00-00 00 00 00 00 00 00 00

2バイトずつリトルエンディアンで取り出したものを10進数で示します。

  • 1758, 1736, 1739, 1742, 1745, 1748, 1751, 1752, 1761, 0, 0, 0, 0, 0, 0, 0

4096バイト時点での直接参照のブロックの後に、1761が追加されています。該当ブロックをバイナリエディタで確認します。(1761 * 512 = 0xdc200)

000DC200 0A 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00

echo "" で追加した'\n'(0x0a)が書き込まれています。

実験 2(間接参照→二重間接参照)

間接参照ではブロックポインタが特定のブロックに格納されています。1ブロックが512バイトで、ポインタが16bitのため、1ブロックには256個のポインタが格納されています。間接参照は7個まで持てるため 7 * 256 * 512 = 896KB が上限です。それ以上のサイズでは、8個目のブロックがブロックマップへのポインタとなる二重間接参照となります。

SIMH上で896KBのファイルを作成します。(7 * 256 = 1792)

# dd if=/dev/rk0 of=test count=1792

inodeを自作ツールで確認します。

size: 917504
addr: 1739,2051,909,2017,2859,1262,207,0

SIMH上で1バイト増やします。

# echo "" >> test

これを自作ツールで確認します。

size: 917505
addr: 1739,2051,909,2017,2859,1262,207,752

二重間接参照ブロックの752が追加されています。該当ブロック(二重間接参照)をバイナリエディタで確認します。(752 * 512 = 0x5e000)

0005E000 29 03 00 00 00 00 00 00-00 00 00 00 00 00 00 00

0x329=809 ブロックが追加されています。該当ブロック(間接参照)をバイナリエディタで確認します。(809 * 512 = 0x65200)

00065200 2C 03 00 00 00 00 00 00-00 00 00 00 00 00 00 00

ようやくデータが格納されているのが 0x32c=812 ブロックだと分かります。該当ブロック(データ)をバイナリエディタで確認します。(812 * 512 = 0x65800)

00065800 0A 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00

echo "" で追加した'\n'(0x0a)が書き込まれています。

以上で、間接参照の最後に二重間接参照が追加されていることが確認できました。