こんにちは、scottです。
みなさん、NTFS読んでますか? Windowsを使っている方ならもちろん読んだことがあると思います。
今日の3分リーディングでは、NTFSのrun listを読んでみたいと思います。

これです。

(オレンジ色の吹き出しと点線囲みは筆者による。)

もう目にタコができるくらいrun listについて見られている方は、復習がてらお付き合いください。

ちなみに、今回は Active@ Disk Editor (http://www.disk-editor.org/)というツールを使っています。
わかりやすくFILEレコードを色付けしてくれて便利です。

run listって何?

run list^[1]とは、ボリューム上に配置されたデータのありかを、連続して配置した部分("run")ごとに保持しているリストです。

上記の図のように、データが分割もとい断片化していれば、複数の"run"が記録されることになります。

run listはnon-residentなattributeに含まれます。
（non-residentって何? attributeって何?? という方は、近くのNTFSに詳しい人に聞いてみよう！）

runはoffset（ボリュームのどこからか）とlength（どれくらい連続して記録されているか）のペアで表現され、run listはこのrunが任意個並んだもの、というわけです。

こういうことですね。

実際のrun list

ただし、先ほど説明した内容がそのまま記録媒体に保存されるわけではありません。
実際にはoffsetの部分は前のrunのoffsetとの差分で表現されるのです^[2]。また、ここで終わり、という情報が最後に付きます。

ちょっと文だとわかりにくいので前の図を借りると、実際には以下のような表現になっているわけです。

そしてこの表現をrunごとに以下のようなバイト列にして順に並べたものが記録媒体に記録されます。

[XY] [LL ...] [OO ...]

ここで

• X: OO... のバイト数
• Y: LL... のバイト数
• LL...: length (little endian)
• OO...: offset (little endian)、負の値は2の補数

です。

run listの最後には、XYのそれぞれが0となった00が、終わりの合図として記録されます。

例えば次のような感じです。

このrunを読むと、length=0x01、offset=0x0F5F73、となります。

並び順は、lengthがうち。offsetはそと。

上記の図では、さらに次のことがわかります。

• 続いて（00ではなく）21が記録されているので、このrun listには続きがある
• 21から、lengthが1バイト、offsetが2バイトさらに続く

sparse(疎な)ファイル

さて、普通のデータがどうrun listとして記録されるかはわかりました。
一方で世の中には、内容の一部がボリューム上に記録されていない、スッカスカなファイルがあります。これはsparse(スパース。疎な、まばらな)ファイルと呼ばれています。

これはrun listとしてどう表現されるのでしょうか?

というわけで実際に以下のようなファイルを用意してみました。

それでは、このファイルのrun listを見てみましょう。
（なおこのボリュームのクラスタサイズは4KiBです。）

ちょっと長いですが、以下のような内容になっていることがわかります。

• 01 10: length=0x10, offset=(0バイト)
• 31 10 6D 2D 04: length=0x10, offset=0x042D6D
• 01 40: length=0x40, offset=(0バイト)
• 31 10 1D 51 2A: length=0x10, offset=0x2A511D
  （なおoffsetを差分として見ると、実際には0x042D6D+0x2A511D=クラスタ#0x2E7E8Aから続くrunですね）
• 01 30: length=0x30, offset=(0バイト)
• 00: おわり

これを図にすると以下のような感じになるでしょうか。

先ほど示したrun listのように、sparseファイルのうちボリューム上に記録されていない部分のrunは、offsetが0バイトになるのです。

ちょっとクイズ

いきなりですが、ルートディレクトリ直下には$Bootという8KiBのファイルがあります。
これはNTFSボリュームの先頭(クラスタ#0)から連続して書かれているブートローダを指しているのですが、
このファイルのrun listはどう表現されるでしょうか?
なおクラスタサイズは4KiBだとします。

2クラスタの長さで、offsetが0の1つだけのrunだから01 02 00?
でもこれだと先頭がsparseなファイルと見分けが付かない!?

では実際の$BootファイルのFILEレコードを見てみましょう。

正解は11 02 00 00でした。

offsetは、先頭がsparseのrun listとは違う、長さ1バイトの00と表現されていました。
このような区別ができるのもrun listの構造のおもしろポイントですね。

というわけで、run listの読み方は以上です。
それでは。

参考

NTFS Documentation: https://flatcap.org/linux-ntfs/ntfs/
英語だけどとっても詳しい!

NTFSの読み方: https://qiita.com/kusano_k/items/45b0a86649aabb8040ff
日本語で図つきでNTFSを紹介している数少ない記事のひとつ。

---

1. 表記について: "run list"という表現が正しいかどうかは不明ですが、runを複数含むlistなので、この記事ではrun listと呼びます。NTFSを解説している複数のWebページでもそう書いてあるので、そんなに間違った言葉ではないと思いたい。一方Microsoftは「マッピング情報(Mapping pair)」と呼んでいるようです。 ↩︎

2. 前のrunのoffsetとの差分で表現される: 前のrunのoffset+length（言い換えれば前のrunのおしり）からの差分ではないところがポイントですね。私はちょっと混乱しました。 ↩︎