ファイルシステムソムリエになる話

利きファイルシステムができるのかという話を見かけたので、できそうだなと思って書いたやつです。

「ここに何かのファイルシステムがあります。ファイル操作を行って、どのファイルシステムか当ててください。なおディスクイメージを見ることはできません。」という問題を解く方法について考えます。

ぱっと思いつく方法はこれでしょうからやっていきます

以下のスクリプトを走らせます。512GBで各FSのイメージ作って、ディレクトリをいくつか掘ってinode番号を表示させるだけです。

#!/bin/sh

FS="btrfs ext4 xfs"
DIR=/mnt/test

for f in $FS; do
    echo ${f}
    truncate -s 512G ${f}.img &&
        mkfs.${f} ${f}.img >/dev/null &&
        mount ${f}.img ${DIR} &&
        mkdir -p ${DIR}/{0,1}/{0,1,2,3} &&
        ls -ldi ${DIR}/{0,1}/{,0,1,2,3} &&
        umount /mnt/test &&
        rm ${f}.img
done

結果はこんな感じ:

btrfs
257 drwxr-xr-x 1 root root 8 Jun 16 23:36 /mnt/test/0/
258 drwxr-xr-x 1 root root 0 Jun 16 23:36 /mnt/test/0/0
259 drwxr-xr-x 1 root root 0 Jun 16 23:36 /mnt/test/0/1
260 drwxr-xr-x 1 root root 0 Jun 16 23:36 /mnt/test/0/2
261 drwxr-xr-x 1 root root 0 Jun 16 23:36 /mnt/test/0/3
262 drwxr-xr-x 1 root root 8 Jun 16 23:36 /mnt/test/1/
263 drwxr-xr-x 1 root root 0 Jun 16 23:36 /mnt/test/1/0
264 drwxr-xr-x 1 root root 0 Jun 16 23:36 /mnt/test/1/1
265 drwxr-xr-x 1 root root 0 Jun 16 23:36 /mnt/test/1/2
266 drwxr-xr-x 1 root root 0 Jun 16 23:36 /mnt/test/1/3
ext4
mke2fs 1.42.13 (17-May-2015)
2097153 drwxr-xr-x 6 root root 4096 Jun 16 23:56 /mnt/test/0/
2097154 drwxr-xr-x 2 root root 4096 Jun 16 23:56 /mnt/test/0/0
2097155 drwxr-xr-x 2 root root 4096 Jun 16 23:56 /mnt/test/0/1
2097156 drwxr-xr-x 2 root root 4096 Jun 16 23:56 /mnt/test/0/2
2097157 drwxr-xr-x 2 root root 4096 Jun 16 23:56 /mnt/test/0/3
7077889 drwxr-xr-x 6 root root 4096 Jun 16 23:56 /mnt/test/1/
7077890 drwxr-xr-x 2 root root 4096 Jun 16 23:56 /mnt/test/1/0
7077891 drwxr-xr-x 2 root root 4096 Jun 16 23:56 /mnt/test/1/1
7077892 drwxr-xr-x 2 root root 4096 Jun 16 23:56 /mnt/test/1/2
7077893 drwxr-xr-x 2 root root 4096 Jun 16 23:56 /mnt/test/1/3
xfs
       99 drwxr-xr-x 6 root root 42 Jun 16 23:36 /mnt/test/0/
268435552 drwxr-xr-x 2 root root  6 Jun 16 23:36 /mnt/test/0/0
537395296 drwxr-xr-x 2 root root  6 Jun 16 23:36 /mnt/test/0/1
805306464 drwxr-xr-x 2 root root  6 Jun 16 23:36 /mnt/test/0/2
      100 drwxr-xr-x 2 root root  6 Jun 16 23:36 /mnt/test/0/3
268435553 drwxr-xr-x 6 root root 42 Jun 16 23:36 /mnt/test/1/
537395297 drwxr-xr-x 2 root root  6 Jun 16 23:36 /mnt/test/1/0
805306465 drwxr-xr-x 2 root root  6 Jun 16 23:36 /mnt/test/1/1
      101 drwxr-xr-x 2 root root  6 Jun 16 23:36 /mnt/test/1/2
268435554 drwxr-xr-x 2 root root  6 Jun 16 23:36 /mnt/test/1/3

わかりやすいですね。 btrfsはinode番号がシーケンシャルに増えていきます。ext4とXFSではinode番号が飛んでいます。ext4とXFSで比べるとext4では同じディレクトリ内のファイル(0/{,0,1,2,3}の組および1/{,0,1,2,3})はinode番号が固まっています。一方、XFSでは同一ディレクトリ内のファイルでもinode番号が飛んでいます。

こうしたinode番号のallocのされ方の違いは各FSのレイアウト・allocation policyに起因しています。詳しく見ていきましょう。

Ext4

Ext4ファイルシステム内部がBlock Group(BG)という領域に分割されています。各BGは空きブロックの数・空きinodeの数・どのinodeが空いているのかを示すbitmapを持ちます。inodeのallocateはどこかのBGから行われます。

たとえば今回の結果だと、"0/*"がBG#256から、"1/*"がBG#864からallocされていることがわかります。"Group 256"の"Free inodes"が"2097158-"と"0/3"の次のinode番号になり、同様に"Group 864"でも"Free inodes"が"1/3"の次である"7077894-"となっています。

# dumpe2fs ext4.img
…
Group 256: (Blocks 8388608-8421375) [ITABLE_ZEROED]
  Checksum 0xb0b5, unused inodes 8187
  Block bitmap at 8388608 (+0), Inode bitmap at 8388624 (+16)
  Inode table at 8388640-8389151 (+32)
  24539 free blocks, 8187 free inodes, 5 directories, 8187 unused inodes
  Free blocks: 8396837-8421375
  Free inodes: 2097158-2105344
…
Group 864: (Blocks 28311552-28344319) [ITABLE_ZEROED]
  Checksum 0xf815, unused inodes 8187
  Block bitmap at 28311552 (+0), Inode bitmap at 28311568 (+16)
  Inode table at 28311584-28312095 (+32)
  24539 free blocks, 8187 free inodes, 5 directories, 8187 unused inodes
  Free blocks: 28319781-28344319
  Free inodes: 7077894-7086080

Ext4は新しいinodeを(ルート直下の場合を除いて)親ディレクトリと同じBG内にallocしようとします。、一般にディレクトリのinodeへのアクセスの後にはその中のファイルにアクセスすることが予想されます。ext4では同一BG内のinodeは固まって配置されているため、同一BGにallocすることでディレクトリinodeの読みこみがついでにその中のファイルのinodeの読みこみもやってくれる可能性が高まります。おそらくこの効果による速度向上を狙ったinode allocation policyなのでしょう。まとめるとext4は"locality"を重視したallocationを行っているわけです。

XFS

XFSでもExt4のBGと同様にファイルシステムの内部をAllocation Groupという領域に分割しています。ただし、Ext4では上記のように800以上にも分割されていましたが、XFSでは多くの場合(FSが128MBから4TBの間なら)、4つのAGに分割されるだけです。

そう思ってよくよくXFSのinode番号の結果を見てみると、4つごとにinode番号のだいたいの大きさがそろっていますね。それぞれAG#0-AG#3にallocationされているというわけです。

せっかくなので、こっちもallocationされている様子を見ておきましょう。まず、AG#0の情報をdumpします。

# xfs_db xfs.img
xfs_db> agi 0
xfs_db> p
magicnum = 0x58414749
versionnum = 1
seqno = 0
length = 33554432
count = 64
root = 3
level = 1
freecount = 58
newino = 96
dirino = null
unlinked[0-63] =
uuid = 3dd1af10-10f6-45dc-b466-c10a727d9842
lsn = 0x100000002
crc = 0x7df3830f (correct)
free_root = 4
free_level = 1

ここの"root"がこのAGでinodeを管理しているB+treeのrootがあるブロックです。該当部分をinodeのB+treeとしてdumpします。

xfs_db> fsblock 3
xfs_db> type inobt
xfs_db> p
magic = 0x49414233
level = 0
numrecs = 1
leftsib = null
rightsib = null
bno = 24
lsn = 0x100000002
uuid = 3dd1af10-10f6-45dc-b466-c10a727d9842
owner = 0
crc = 0x1b9f870b (correct)
recs[1] = [startino,freecount,free] 1:[96,58,0xffffffffffffffc0]

"[startino,freecount,free] 1:[96,58,0xffffffffffffffc0]" がinode管理情報です。XFSではinodeは64個の塊で動的にallocされていきます。このエントリはinode番号96から64個分のinodeについて管理しています。"freecount"が58なので64-58=6個のinodeが使用されており、どこが空いているのかは"free" bitmapを見ることでわかります。実際96-101に相当する下位6bitが0で残りが1になっていることが見てとれます。

同様にAG#1のinode B+treeも見てみると…。(agi 1+addrでAG#1のoffsetを確認し、そこに3足したところがAG#1のinode B+tree root)

xfs_db> agi 1
xfs_db> addr
current
        byte offset 137438954496, length 512
        buffer block 268435458 (fsbno 33554432), 1 bb
        inode -1, dir inode -1, type agi
xfs_db> fsblock 33554435
xfs_db> type inobt
xfs_db> p
magic = 0x49414233
level = 0
numrecs = 1
leftsib = null
rightsib = null
bno = 268435480
lsn = 0x100000002
uuid = 3dd1af10-10f6-45dc-b466-c10a727d9842
owner = 1
crc = 0x687eec0e (correct)
recs[1] = [startino,freecount,free] 1:[96,61,0xfffffffffffffff8]

こちらもinode番号96から、となっていますね。ここに記録される96というのはAG内localのinode番号でFSでのinode番号にするには上位bit領域にAGの番号を入れる必要があります。そう思って"0/0"のinode番号を見ると"268435552"というのは"0x10000060"というわけで"0x60=96"と"0x1"=AGの番号が見てとれます。

さてXFSのinode allocation policyの話に行きましょう。XFSではディレクトリの場合、FS全体でラウンドロビンにAGを(優先して)選択していきます。そのため最初の実験結果のようにディレクトリごとにAGが変わっていっているわけですね。一方でファイルであればディレクトリと同じAGを優先するので、さきほどのスクリプトディレクトリ0,1以下はファイルを作るようにするとこうなります。

xfs
       96 drwxr-xr-x 4 root root 24 Jun 17 01:18 /mnt/test
       99 drwxr-xr-x 2 root root 42 Jun 17 01:18 /mnt/test/0/
      100 -rw-r--r-- 1 root root  0 Jun 17 01:18 /mnt/test/0/0
      101 -rw-r--r-- 1 root root  0 Jun 17 01:18 /mnt/test/0/1
      102 -rw-r--r-- 1 root root  0 Jun 17 01:18 /mnt/test/0/2
      103 -rw-r--r-- 1 root root  0 Jun 17 01:18 /mnt/test/0/3
268435552 drwxr-xr-x 2 root root 42 Jun 17 01:18 /mnt/test/1/
268435553 -rw-r--r-- 1 root root  0 Jun 17 01:18 /mnt/test/1/0
268435554 -rw-r--r-- 1 root root  0 Jun 17 01:18 /mnt/test/1/1
268435555 -rw-r--r-- 1 root root  0 Jun 17 01:18 /mnt/test/1/2
268435556 -rw-r--r-- 1 root root  0 Jun 17 01:18 /mnt/test/1/3

ディレクトリをFS全体でラウンドロビンに配置していくことで、個々のディレクトリ内の操作はAGが異なれば独立して進めることができ、scalabiltyが向上しています。このようにXFSでは"scalability"を意識したallocation policyが使われています。

Btrfs

Btrfsでは、ディレクトリとファイルとの親子関係・inodeデータ・ファイルのデータ位置情報が全て「ファイルシステムツリー」(FS tree)と呼ばれるB-treeで管理されます。また、Btrfsにおいては「どこのinodeが空いているか」を管理するまとまった情報(ext4やXFSのbitmapみたいな)は(デフォルトでは)存在しません。treeの中でファイル削除などで空いてしまったinode番号を発見する最速の方法はFS treeを全部scanすることです。前述の通り、FS treeには様々な情報が載っているのでこれをなめていくのはかなりの時間がかかります。ということで、Btrfsではこれまでにallocした最大のinode番号を覚えておいて、これまでに割り当てたことのないinode番号を割り当てるというallocation policyをとっています。そのため、最初の結果のようにシーケンシャルになっています。なんですかね、"simple"なallocation policyとでも言っておくといいんでしょうか。

(Btrfsはext4, XFSみたいにFS領域分割しないのかというのがありますが、一応chunkという単位に分かれています。ただ、localityやscalabilityのためでは(多分)なく管理しやすさぐらい…。localityなんてやろうとしてもどうせCoW FSだからそのうち崩壊するだろうし、デフォルトでinode番号管理構造ないからallocするinode番号を開けていくようにするのはうまくいかないし…。inode_cacheを仮定してallocするinode番号を変えるなどするのはおもしろいのかもしれないが…もう2時なのでもうこんな感じで)

まとめ

それぞれのFSがBtrfsはsimple, Ext4はlocality, XFSはscalabilityと違ったinode allocation policyを取っています。そのおかげであなたも明日からファイルシステムソムリエです。おめでとうございます。

補則

今回は作りたてのFSだったけれど、じゃあ、ある程度使われたFSだとどうなるってことなんですが、inode_cacheなしのbtrfsだとやはりシーケンシャルに当たるのでわかりやすい。ext4とXFSではinodeの空き方によって複雑になる気がします。まあXFSの方が性質上inode番号が大きくなりがちなんでそこ見ていけばいいかなとか、inode領域が動的確保なことを利用してあるAG内のファイルにデータを書きまくる->その後にそのAG内でallocされたinode番号を見るといったことをすればいいんじゃないでしょうか。

あとbtrfs、inode割り当て一周したらどーすんのってのはちゃんとinode_cacheというmount optionでどこが空いているかのデータベース作ってそこ見てくれるようになるんで安心してください。でも64bit環境ならそうそうなくならんし普通はなくてもいいんじゃないかな。

おまけ: f2fsとnilfs2

f2fs
 4 drwxr-xr-x 6 root root 4096 Jun 17 02:20 /mnt/test/0/
 5 drwxr-xr-x 2 root root 4096 Jun 17 02:20 /mnt/test/0/0
 6 drwxr-xr-x 2 root root 4096 Jun 17 02:20 /mnt/test/0/1
 7 drwxr-xr-x 2 root root 4096 Jun 17 02:20 /mnt/test/0/2
 8 drwxr-xr-x 2 root root 4096 Jun 17 02:20 /mnt/test/0/3
 9 drwxr-xr-x 6 root root 4096 Jun 17 02:20 /mnt/test/1/
10 drwxr-xr-x 2 root root 4096 Jun 17 02:20 /mnt/test/1/0
11 drwxr-xr-x 2 root root 4096 Jun 17 02:20 /mnt/test/1/1
12 drwxr-xr-x 2 root root 4096 Jun 17 02:20 /mnt/test/1/2
13 drwxr-xr-x 2 root root 4096 Jun 17 02:20 /mnt/test/1/3
nilfs2
mkfs.nilfs2 (nilfs-utils 2.1.6)
Start writing file system initial data to the device
       Blocksize:4096  Device:nilfs2.img  Device Size:549755813888
File system initialization succeeded !! 
12 drwxr-xr-x 6 root root 4096 Jun 17 02:32 /mnt/test/0/
17 drwxr-xr-x 2 root root 4096 Jun 17 02:32 /mnt/test/0/0
18 drwxr-xr-x 2 root root 4096 Jun 17 02:32 /mnt/test/0/1
19 drwxr-xr-x 2 root root 4096 Jun 17 02:32 /mnt/test/0/2
20 drwxr-xr-x 2 root root 4096 Jun 17 02:32 /mnt/test/0/3
21 drwxr-xr-x 6 root root 4096 Jun 17 02:32 /mnt/test/1/
22 drwxr-xr-x 2 root root 4096 Jun 17 02:32 /mnt/test/1/0
23 drwxr-xr-x 2 root root 4096 Jun 17 02:32 /mnt/test/1/1
24 drwxr-xr-x 2 root root 4096 Jun 17 02:32 /mnt/test/1/2
25 drwxr-xr-x 2 root root 4096 Jun 17 02:32 /mnt/test/1/3

allocation policy 知らないけどどうもシーケンシャルな様子。log structuredだからそんなもんですな。Btrfsではroot inode番号256なことを使って判別すればいいかなという気がする。あとBtrfsはlink-countしないので全部"1"になってるとこでも判別できる。そうやって見ていくと、directoryのsizeのとこでもFS判別できるね。ソムリエ道は奥が深い。



というか、 root directoryのinode番号で結構わかるね(涙 (btrfs:256, ext4:2, xfs:96(設定によるが), f2fs:3, nilfs2: 2)

まだおまけ

こうなるとどうしても root inode番号見ずにf2fsとnilfs2を区別したい。ということで、0/{0,1,2,3}を作る->一度0/{0,1,2,3}を削除->sync->もう一度0/{0,1,2,3}を作るとしてみた結果

f2fs
 4 drwxr-xr-x 6 root root 4096 Jun 17 02:36 /mnt/test/0/
 9 drwxr-xr-x 2 root root 4096 Jun 17 02:36 /mnt/test/0/0
10 drwxr-xr-x 2 root root 4096 Jun 17 02:36 /mnt/test/0/1
11 drwxr-xr-x 2 root root 4096 Jun 17 02:36 /mnt/test/0/2
12 drwxr-xr-x 2 root root 4096 Jun 17 02:36 /mnt/test/0/3
nilfs2
mkfs.nilfs2 (nilfs-utils 2.1.6)
Start writing file system initial data to the device
       Blocksize:4096  Device:nilfs2.img  Device Size:549755813888
File system initialization succeeded !!
12 drwxr-xr-x 6 root root 4096 Jun 17 02:36 /mnt/test/0/
13 drwxr-xr-x 2 root root 4096 Jun 17 02:36 /mnt/test/0/0
14 drwxr-xr-x 2 root root 4096 Jun 17 02:36 /mnt/test/0/1
15 drwxr-xr-x 2 root root 4096 Jun 17 02:36 /mnt/test/0/2
16 drwxr-xr-x 2 root root 4096 Jun 17 02:36 /mnt/test/0/3

inode番号がf2fsでは不連続、nilfs2では連続しているのがわかる。syncしているのがポイントでsyncしないとnilfs2でもうまく連続にはならない。