XFSを解析した話 (3) - Directory 編

目次

想定読者

XFS Filesystem の生データを解析したいと思っている方に向けた記事です。 

今回の記事では、XFSの ディレクトリの inode について解説していきます。

おさらい

XFSの inode は inode core と data fork と attribute fork の3つのデータからなります。

inode core 内の format と mode を元に data fork をパースすることで、その inode に紐づかれた情報を読み取ることが可能です。ディレクトリの場合は、ディレクトリの配下に存在する inode の情報で ファイルの場合は実際のデータが取得できます。

data fork の解析

ディレクトリの format は以下の3種類存在し、それぞれの format に応じて data fork をパースします。

  • local
  • extents
  • btree

この3つの format の違いは data fork で表現できるデータ量が異なります。 local < extents < btree の順番に表現できるデータ量が増加し、 local format では管理しきれなくなると、 extents format に変換されるという形です。また、 data fork のサイズは attribute fork のサイズによって決定されます。(仕様書: 16.3 Data Fork を参照)

attribute fork について

attribute fork は attr1attr2 の2種類のバージョンが存在します。違いとしては、inode 内での attribute fork のサイズが固定長か可変長の違いです。 XFSのスーパーブロック内にある features2 パラメータに XFS_SB_VERSION2_ATTR2BIT(0x80)が立っていれば attr2 ということになります。(仕様書: 16.4 Attribute Fork を参照)

実際に確認しましょう。

$ xfs_db xfs.img
xfs_db> sb 
xfs_db> p 

色々割愛...
features2 = 0x18a

0x18a とでました。 ATTR2BIT は 0x80 なので xfs.img の attribute fork は attr2 のバージョンを利用していることがわかります。attribute fork のサイズは inode core 内にある forkoff によって決定されます。

次に各 format 毎に data fork をパースしていきます。

format local を解析

XFSを解析した話(SuperBlock 編)デバッグ用のイメージを作成 こちらで作成したイメージを利用します。

ルートディレクトリが format local の ディレクトリであるため、初めは root inode の data fork を解析していきます。 rootino のオフセットは root inode の offset を計算 で計算した値を利用します。

改めて root inode のデータを見ましょう。

$ xxd -s 65536 -l 512 xfs.img

00010000: 494e 41ed 0301 0000 0000 0000 0000 0000  INA.............
00010010: 0000 0004 0000 0000 0000 0000 0000 0000  ................
00010020: 6350 1d2e 04e4 de45 6350 1a4b 0ddb 729e  cP.....EcP.K..r.
00010030: 6350 1a4b 0ddb 729e 0000 0000 0000 001c  cP.K..r.........
00010040: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00010050: 0000 0002 0000 0000 0000 0000 0000 0000  ................
00010060: ffff ffff 6af2 441d 0000 0000 0000 0006  ....j.D.........
00010070: 0000 0001 0000 0030 0000 0000 0000 0000  .......0........
00010080: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00010090: 6350 1834 2a46 72e0 0000 0000 0000 0080  cP.4*Fr.........
000100a0: 1b1b cec8 c7eb 4ff3 bfd5 1fad cd95 ee46  ......O........F
000100b0: 0200 0000 0080 0300 6065 7463 0200 0000  ........`etc....
000100c0: 8303 0070 7661 7202 0001 2b40 0000 0000  ...pvar...+@....
000100d0: 0000 0000 0000 0000 0000 0000 0000 0000  ................

以下 0x00 のため省略

inode core のサイズは inode バージョンが 3 の場合 176 で固定のため、 0xb0 からのデータが data fork になります。

これが data fork のデータになります。

000100b0: 0200 0000 0080 0300 6065 7463 0200 0000  ........`etc....
000100c0: 8303 0070 7661 7202 0001 2b40 0000 0000  ...pvar...+@....

format local の data fork は Short Form Directories と呼ばれ、inode 内に配下ディレクトリの情報が入っています。(仕様書: 18.1 Short Form Directories を参照)

これが実際の構造体になります。

typedef struct xfs_dir2_sf_hdr {
    uint8_t         count;
    uint8_t         i8count;
    xfs_dir2_inou_t parent; // 4 bytes
} __packed xfs_dir2_sf_hdr_t;

typedef struct xfs_dir2_sf_entry {
     __uint8_t          namelen;
     xfs_dir2_sf_off_t  offset; // 2 bytes
     __uint8_t          name[1];
     __uint8_t          ftype;
     xfs_dir2_inou_t    inumber;
} xfs_dir2_sf_entry_t;

ヘッダーに entry 数などが記載され、続く entry のリストにディレクトリの情報が記載されます。 ということで data fork のバイナリを分解しましょう。

000100b0: 0200 0000 0080 0300 6065 7463 0200 0000  ........`etc....
000100c0: 8303 0070 7661 7202 0001 2b40 0000 0000  ...pvar...+@....
これを分解していく

xfs_dir2_sf_hdr 
02          - count この後続く entryの数
00          - i8count entry内にいくつ 8 bytes inode が存在するか(よくわかってない)
0000 0080   - parent この inode の親の番号 

xfs_dir2_sf_entry[0]
03          - namelen ディレクトリ名の長さ 
00 60       - offset わからない... 
65 74 63    - name 0x65, 0x74, 0x63 は etc ですね
02          - ftype わからない... 
00 00 00 83 - inode の番号(131)

xfs_dir2_sf_entry[1]
03          - namelen ディレクトリ名の長さ 
00 70       - offset わからない... 
76 61 72    - name 0x76, 0x61, 0x72 は var ですね
02          - ftype わからない... 
00 01 2b 40 - inode の番号 (76608)

xfs_db で確認してみましょう。

xfs_db> inode 128
xfs_db> p 
長いので省略

u3.sfdir3.hdr.count = 2
u3.sfdir3.hdr.i8count = 0
u3.sfdir3.hdr.parent.i4 = 128
u3.sfdir3.list[0].namelen = 3
u3.sfdir3.list[0].offset = 0x60
u3.sfdir3.list[0].name = "etc"
u3.sfdir3.list[0].inumber.i4 = 131
u3.sfdir3.list[0].filetype = 2
u3.sfdir3.list[1].namelen = 3
u3.sfdir3.list[1].offset = 0x70
u3.sfdir3.list[1].name = "var"
u3.sfdir3.list[1].inumber.i4 = 76608
u3.sfdir3.list[1].filetype = 2

しっかりと計算したものと一致していることがわかります。 これで format local は終わりです。次に format extents について解析します。

format extents を解析

format extents は format local とは異なり、extents という形でデータを管理します。 イメージとしては以下の画像のようなもので、実際のデータに対する pointer を inode 内で保持するような仕組みです。(17.1 Extent List を参照)

format extents を解析するためには、まず format extents の inode を作る必要があるので、作っていきます。作り方は簡単で format local は inode のサイズ 512 bytes から inode core の 172 bytes を引いた 340 bytes のデータしか表現できません。(attribute fork が 0 の場合)そのため 340 bytes 以上のデータを持つような ディレクトリを作成すれば format local は format extents に昇格することがわかります。

最初に作った Linux.img をマウントしてデータを書き込んでいきます。

$ losetup -f 

# loop5 が空いている場合
$ losetup /dev/loop5 Linux.img
$ mount /dev/loop5p2 /mnt/xfs

# 適当に長い名前のファイルを3つ作る(128文字を3つにした)
$ touch /mnt/xfs/AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
$ touch /mnt/xfs/AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB
$ touch /mnt/xfs/AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAC


# xfs.img を取り出す
$ xxd  /dev/loop5p2  | xxd -r  >> xfs.img

xfs.img を xfs_db で確認します。

xfs_db> inode 128 
xfs_db> p
長いのでいろいろ割愛

core.nblocks = 1
core.nextents = 1
core.forkoff = 0
core.format = 2 (extents)
u3.bmx[0] = [startoff,startblock,blockcount,extentflag]
0:[0,15,1,0]

format extents ですね。xxd を用いて生のデータを見ましょう。

$ xxd -s 65536 -l 512 xfs.img
00010000: 494e 41ed 0302 0000 0000 0000 0000 0000  INA.............
00010010: 0000 0004 0000 0000 0000 0000 0000 0000  ................
00010020: 63a4 9e1f 07da 00ee 63a4 9e00 2a10 9dd1  c.......c...*...
00010030: 63a4 9e00 2a10 9dd1 0000 0000 0000 1000  c...*...........
00010040: 0000 0000 0000 0001 0000 0000 0000 0001  ................
00010050: 0000 0002 0000 0000 0000 0000 0000 0000  ................
00010060: ffff ffff 21fa fe60 0000 0000 0000 000a  ....!..`........
00010070: 0000 0001 0000 0054 0000 0000 0000 0000  .......T........
00010080: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00010090: 6350 1834 2a46 72e0 0000 0000 0000 0080  cP.4*Fr.........
000100a0: 1b1b cec8 c7eb 4ff3 bfd5 1fad cd95 ee46  ......O........F
000100b0: 0000 0000 0000 0000 0000 0000 01e0 0001  ................
000100c0: 8303 0070 7661 7202 0001 2b40 8000 8041  ...pvar...+@...A
000100d0: 4141 4141 4141 4141 4141 4141 4141 4141  AAAAAAAAAAAAAAAA
000100e0: 4141 4141 4141 4141 4141 4141 4141 4141  AAAAAAAAAAAAAAAA
000100f0: 4141 4141 4141 4141 4141 4141 4141 4141  AAAAAAAAAAAAAAAA
00010100: 4141 4141 4141 4141 4141 4141 4141 4141  AAAAAAAAAAAAAAAA
00010110: 4141 4141 4141 4141 4141 4141 4141 4141  AAAAAAAAAAAAAAAA
00010120: 4141 4141 4141 4141 4141 4141 4141 4141  AAAAAAAAAAAAAAAA
00010130: 4141 4141 4141 4141 4141 4141 4141 4141  AAAAAAAAAAAAAAAA
00010140: 4141 4141 4141 4141 4141 4141 4141 4101  AAAAAAAAAAAAAAA.
00010150: 0000 0085 8001 1041 4141 4141 4141 4141  .......AAAAAAAAA
00010160: 4141 4141 4141 4141 4141 4141 4141 4141  AAAAAAAAAAAAAAAA
00010170: 4141 4141 4141 4141 4141 4141 4141 4141  AAAAAAAAAAAAAAAA
00010180: 4141 4141 4141 4141 4141 4141 4141 4141  AAAAAAAAAAAAAAAA
00010190: 4141 4141 4141 4141 4141 4141 4141 4141  AAAAAAAAAAAAAAAA
000101a0: 4141 4141 4141 4141 4141 4141 4141 4141  AAAAAAAAAAAAAAAA
000101b0: 4141 4141 4141 4141 4141 4141 4141 4141  AAAAAAAAAAAAAAAA
000101c0: 4141 4141 4141 4141 4141 4141 4141 4141  AAAAAAAAAAAAAAAA
000101d0: 4141 4141 4141 4201 0000 0087 0000 0000  AAAAAAB.........
000101e0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000101f0: 0000 0000 0000 0000 0000 0000 0000 0000  ................

あれ... 思ってたのと違う。となった皆様は多いんじゃないでしょうか。 format extents は データ に対する pointer を持つから inode 内にディレクトリの情報などは持たないんじゃないか?というか3つファイルを作成したのに 2つしかなさそうDA☆ となります。
これはファイルシステムあるあるですが、古いデータが残っているだけで実際には使われないゴミデータが残っているという状況です。0x100b0の行を見てもらえればわかりやすいですが、format local の時とは異なるデータが入っています。

format extents の場合、 inode core に続く data fork には extent list というデータが入ります。inode core 内の nextents がいくつの extent を持っているかを表現しています。今回の場合は nextents が 1 のため一つの extents を持つ inode であることがわかります。

では、extents をパースしていきます。このデータは xfs_bmbt_rec と呼ばれるデータで Linux上のコードだと以下のように表現されています。

typedef struct xfs_bmbt_rec {
    __be64          l0, l1;
} xfs_bmbt_rec_t;

https://github.com/torvalds/linux/blob/d2b6f8a179194de0ffc4886ffc2c4358d86047b8/fs/xfs/libxfs/xfs_format.h#L1787-L1789

L0 と L1 という 8 bytes のデータを持つ計 16 bytes の構造体です。
この bmbt_rec を以下の処理で変換してやることで extent のデータが取得できます。

pythonの書き方わかんなくなったので go で変換します。

# 元となるデータ(16 bytes)
# 000100b0: 0000 0000 0000 0000 0000 0000 01e0 0001  

func main() {
    BmbtRec{L0: 0x00, L1: 0x01e00001}.Unpack()
}

type BmbtRec struct {
    L0, L1 uint64
}

func (b BmbtRec) Unpack() {
    const BMBT_EXNTFLAG_BITLEN = 1
    fmt.Println("StartOff:", (b.L0&Mask64Lo(64-BMBT_EXNTFLAG_BITLEN))>>9)
    fmt.Println("StartBlock:", ((b.L0&Mask64Lo(9))<<43)|(b.L1>>21))
    fmt.Println("BlockCount:", b.L1&Mask64Lo(21))
}

func Mask64Lo(n int64) uint64 {
    return (1 << n) - 1
}

https://github.com/torvalds/linux/blob/d2b6f8a179194de0ffc4886ffc2c4358d86047b8/fs/xfs/libxfs/xfs_bmap_btree.c#L60 を参考

実行結果は以下になります。

StartOff: 0
StartBlock: 15
BlockCount: 1

StartOff は複数の extent を取得した際(今回は 1件だけだが)にどの extent が何番目かを管理する。要は extent list のソート用のデータです。
StartBlock はその extent がファイルシステム上のどの位置に存在するかを示しています。
BlockCount は StartBlock から何ブロック続いているかを示します。

これらの情報を元に format extents な root inode を読み込んでいきます。

今回に関しては、StartOffとBlockCountはともにそこまで意識することはないです。問題は StartBlock です。脳死で BlockSize(4096) * StartBlock なんて計算をすると痛い目に遭います。

解説を書くのが辛くなってきたので、ソースコード貼ります。 go-xfs-filesystem/xfs/sb.go at main · masahiro331/go-xfs-filesystem · GitHub

問題は AG0 ではない AG に extent は存在する場合、単純な計算ではずれるという問題があります。 今回は AG0 のはずなので 15 になると思いますが、一応計算のコードを貼っておきます。

func mask64Lo(n int) int {
    return (1 << n) - 1
}

func main() {
    const (
        Agblocks   = 4862
        Agblklog   = 13
        StartBlock = 15
    )

    AgBlockNumber := StartBlock & mask64Lo(Agblklog)
    AgNumber := StartBlock >> Agblklog
    fmt.Println(AgNumber*Agblocks + AgBlockNumber)
}

ということで xxd を用いて 4096 * 15 に飛んで 1ブロック分だけデータを取得します。

$ xxd -s 61440 -l 4096 xfs.img

0000f000: 5844 4233 a065 f0a0 0000 0000 0000 0078  XDB3.e.........x
0000f010: 0000 0001 0000 004d 1b1b cec8 c7eb 4ff3  .......M......O.
0000f020: bfd5 1fad cd95 ee46 0000 0000 0000 0080  .......F........
0000f030: 0230 0d90 0000 0000 0000 0000 0000 0000  .0..............
0000f040: 0000 0000 0000 0080 012e 0200 0000 0040  ...............@
0000f050: 0000 0000 0000 0080 022e 2e02 0000 0050  ...............P
0000f060: 0000 0000 0000 0083 0365 7463 0200 0060  .........etc...`
0000f070: 0000 0000 0001 2b40 0376 6172 0200 0070  ......+@.var...p
0000f080: 0000 0000 0000 0085 8041 4141 4141 4141  .........AAAAAAA
0000f090: 4141 4141 4141 4141 4141 4141 4141 4141  AAAAAAAAAAAAAAAA
0000f0a0: 4141 4141 4141 4141 4141 4141 4141 4141  AAAAAAAAAAAAAAAA
0000f0b0: 4141 4141 4141 4141 4141 4141 4141 4141  AAAAAAAAAAAAAAAA
0000f0c0: 4141 4141 4141 4141 4141 4141 4141 4141  AAAAAAAAAAAAAAAA
0000f0d0: 4141 4141 4141 4141 4141 4141 4141 4141  AAAAAAAAAAAAAAAA
0000f0e0: 4141 4141 4141 4141 4141 4141 4141 4141  AAAAAAAAAAAAAAAA
0000f0f0: 4141 4141 4141 4141 4141 4141 4141 4141  AAAAAAAAAAAAAAAA
0000f100: 4141 4141 4141 4141 4101 0000 0000 0080  AAAAAAAAA.......
0000f110: 0000 0000 0000 0087 8041 4141 4141 4141  .........AAAAAAA
0000f120: 4141 4141 4141 4141 4141 4141 4141 4141  AAAAAAAAAAAAAAAA
0000f130: 4141 4141 4141 4141 4141 4141 4141 4141  AAAAAAAAAAAAAAAA
0000f140: 4141 4141 4141 4141 4141 4141 4141 4141  AAAAAAAAAAAAAAAA
0000f150: 4141 4141 4141 4141 4141 4141 4141 4141  AAAAAAAAAAAAAAAA
0000f160: 4141 4141 4141 4141 4141 4141 4141 4141  AAAAAAAAAAAAAAAA
0000f170: 4141 4141 4141 4141 4141 4141 4141 4141  AAAAAAAAAAAAAAAA
0000f180: 4141 4141 4141 4141 4141 4141 4141 4141  AAAAAAAAAAAAAAAA
0000f190: 4141 4141 4141 4141 4201 0000 0000 0110  AAAAAAAAB.......
0000f1a0: 0000 0000 0000 0088 8041 4141 4141 4141  .........AAAAAAA
0000f1b0: 4141 4141 4141 4141 4141 4141 4141 4141  AAAAAAAAAAAAAAAA
0000f1c0: 4141 4141 4141 4141 4141 4141 4141 4141  AAAAAAAAAAAAAAAA
0000f1d0: 4141 4141 4141 4141 4141 4141 4141 4141  AAAAAAAAAAAAAAAA
0000f1e0: 4141 4141 4141 4141 4141 4141 4141 4141  AAAAAAAAAAAAAAAA
0000f1f0: 4141 4141 4141 4141 4141 4141 4141 4141  AAAAAAAAAAAAAAAA
0000f200: 4141 4141 4141 4141 4141 4141 4141 4141  AAAAAAAAAAAAAAAA
0000f210: 4141 4141 4141 4141 4141 4141 4141 4141  AAAAAAAAAAAAAAAA
0000f220: 4141 4141 4141 4141 4301 0000 0000 01a0  AAAAAAAAC.......
0000f230: ffff 0d90 0000 0000 0000 0000 0000 0000  ................

長いので割愛

しっかり取れていますね。 先頭のマジックバイトに注目すると、XDB3と表示されていることがわかります。

これは format extents の中でも Block Directories と呼ばれる形式になります。Block Directories は extent の先に format local のような形でディレクトリの情報が入っているタイプになります。

このようなイメージです。

ということで、データをパースしていきます。

struct xfs_dir3_blk_hdr {
    __be32          magic;  /* magic number */
    __be32          crc;    /* CRC of block */
    __be64          blkno;  /* first block of the buffer */
    __be64          lsn;    /* sequence number of last write */
    uuid_t          uuid;   /* filesystem we belong to */
    __be64          owner;  /* inode that owns the block */
};

struct xfs_dir3_data_hdr {
    struct xfs_dir3_blk_hdr hdr;
    xfs_dir2_data_free_t    best_free[XFS_DIR2_DATA_FD_COUNT];
    __be32          pad;    /* 64 bit alignment */
};

はじめにヘッダー部分を実装を参考にパースしていきます。

linux/fs/xfs/libxfs/xfs_da_format.h at 5bfc75d92efd494db37f5c4c173d3639d4772966 · torvalds/linux · GitHub

# 元となるデータ
0000f000: 5844 4233 a065 f0a0 0000 0000 0000 0078  XDB3.e.........x
0000f010: 0000 0001 0000 004d 1b1b cec8 c7eb 4ff3  .......M......O.
0000f020: bfd5 1fad cd95 ee46 0000 0000 0000 0080  .......F........
0000f030: 0230 0d90 0000 0000 0000 0000 0000 0000  .0..............

xfs_dir3_blk_hdr
5844 4233                                magic マジックバイト
a065 f0a0                                crc 誤りの検出用
0000 0000 0000 0078                      blkno 実データが入ってるブロック
0000 0001 0000 004d                      lsn ログ用のやつらしい
1b1b cec8 c7eb 4ff3 bfd5 1fad cd95 ee46  uuid UUID
0000 0000 0000 0080                      このextentを持つinodeの番号


xfs_dir2_data_free_t // XFS_DIR2_DATA_FD_COUNT = 3
0230 0d90    best_free[0] 使ってないのでわかりません() 
0000 0000    best_free[1]
0000 0000    best_free[2]

padding
0000 0000 アライメント用です

あとは local extent と同様に block を追いかけることでパース可能です。

今日の記事では割愛しますが、 format extents にはこの他にも Node Directories, Leaf Directories などさらに階層化が可能な仕組みが存在します。またそれらでも表現できなければ、 format btree が登場します。