ファイルシステム

ファイルシステムは /home/user/notes.txt のようなパスをデータへ結び付ける。本課の inode モデルは内容をデータブロック、メタデータを inode、名前を親ディレクトリーのデータへ分ける。名前は対象自身の inode にはない。

預かり所の台帳に notes.txt→7 と書き、品物を 7 番へ置くイメージだ。品物の記録はサイズ、参照数、内容位置を持ち、名前は台帳にある。同じ品物へ複数の札を発行するように、複数名が同じ inode を指せる。

仕組み

OSTEP の教育用ファイルシステム vsfs を縮小し、4 KB ブロックが 13 個ある。0 は配置を記すスーパーブロック、1 と 2 は inode とデータのビットマップ、3 と 4 は各 4 inode を持つ表で計 8 inode。5–12 は D0–D7 のデータ領域だ。

inode は型、バイトサイズ、リンク数、内容ブロック番号を持つ。実 inode には権限、所有者、時刻などもあり、形式で異なる。ディレクトリーも inode とデータブロックを使うが、型と操作規則は特別で、内容は name→inode number の項目だ。

根は i0、データ D0 に home→i3 と readme.txt→i2 がある。根から各パス成分について、ディレクトリー inode でデータ位置を得て、そのデータで次 inode を探す。最後に対象 inode を読む。

本課は各ディレクトリー一ブロック、キャッシュなしなので、深さ d の open を 2d+1 モデルブロック読み取りと数える。ブロック内の名前比較には CPU 作業があるが、追加ディスク読込は課金しない。内容サイズは式に入らず、open は内容をまだ読んでいない。全実ファイルシステムの物理 I/O 法則ではない。

ステップ実行

既定は open("/home/user/notes.txt")、read、unlink。根データ D0、home は D1、user は D3、内容は D4 と D5 に散らばる。連続したパスは連続ブロックを要求しない。

1. 読み取り 1、2：i0 から D0 を得て、D0 で home→i3 を探す。対象内容は未読。
2. 読み取り 3、4：i3 と D1 を読み、user→i5 を得る。
3. 読み取り 5、6：i5 と D3 から notes.txt→i7。
4. 読み取り 7：i7 は 8192 バイトのファイル、リンク数 1、D4 と D5 を指す。名前フィールドはない。open は inode を指す fd 3 を返し、まだ your data: 0 B。
5. 読み取り 8、9：read(fd 3) は既知 inode を使い、パスを再走査せず D4、D5 の 8192 バイトを取得する。
6. unlink が変更するのは親ディレクトリーなので、モデルはパス全体を再びたどり、読み取り 10–15 を数えて、ファイルではなく user の表 D3 で止まる。続いて更新する。

削除の順序は次のとおり。

1. D3 を書き、notes.txt→i7 を除く。名前は一覧から消えるが inode と内容はまだ変わらない。
2. i7 を読む。これが読み取り 16。
3. i7 を書き、リンク数を 1 から 0 にする。
4. データビットマップの D4、D5 を消し、inode ビットマップの i7 を消す。二つのマップ書き込みになる。ビットマップはマウント時からメモリーに常駐するので、先に読む必要はない。

計 16 読み取り、4 書き込み。20 モデル I/O のうち対象内容は二読み取りだ。このモデルは開いている参照を数えないためリンクゼロで回収する。実システムなら先の fd がまだ開いている場合に通常保存が必要で、このアニメーションから即解放を一般化できない。

D4、D5 は空き印でも本文が残る。ビットを消す操作はデータを上書きせず、後の割当が再利用し得る。実媒体、TRIM、暗号化、上書き方針で復元性は変わり、名前の削除は確実な消去と同じではない。

rm が除くもの

Two names の link("/home/user/notes.txt", "backup.txt") は、モデル内では同じ D3 へ新名を置く。i7 への七読み取り後、D3 に backup.txt→i7、inode のリンク数 1→2 を二回書く。内容は読まず、コピーも書込もしない。実際の相対パスはプロセスの作業ディレクトリーに従う。

その後 notes.txt を unlink すると、その項目を除いて 2→1 とし、ビットマップや内容は解放しない。backup.txt から開くと同じ i7、D4、D5、8192 バイトを得る。色は inode に属するので二つの名も同色だ。

実 OS にはメモリ中の開いた参照もある。巨大なログを rm し、リンクゼロで元の名が消えても、プロセスが開き続ければ容量を保持し得る。最後の関連参照を閉じるかプロセスが終わって回収可能になる。この参照はディスクのリンク数とは別で、他のカーネル参照も寿命に関係する。

境界ケース

• ENOENT：open("/home/guest/diary.txt") は home の後 D1 に guest がなく、四読み取りで止まり、使った読み取りは戻らない。open が返すのは ENOENT だけで、どの成分が欠けたかは示さない。キャンバスの赤い印はモデルが止まった位置を示すものだ。実システムは不在名のキャッシュもあり、失敗パス数をそのまま物理 I/O 倍数にできない。
• /home/user は i5 のディスクリプターを返し、内容はディレクトリー項目。続く read は EISDIR になる。Linux は open と fstat でメタデータを調べ、項目は readdir で解析済みの形で得る。read で生ブロックとして読むのではない。
• /readme.txt/x は i2 を読んでディレクトリーでなくファイルだと分かり、ENOTDIR で失敗する。三読み取りは支払い済みだ。
• Append one block は 4 KB を追加し、データマップを割当済みにし、新ブロックへ内容を書き、inode のポインターとサイズを更新する三書込。クラッシュ整合性には順序とプロトコルが必要で、本モデルはジャーナル保証を持たない。
• パスを使う操作は再走査し、read(fd) は既知 inode を使う。実 dentry、inode、ページキャッシュは熱い open のディスクアクセスをなくし得る。
• Shallow path の /readme.txt は深さ 1 で三読み取り、既定深さ 3 は七。差は階層で内容サイズではない。実費用にはキャッシュとディレクトリー索引も効く。

よくある間違い

• 名前を inode のフィールドとする。名前はディレクトリーにあり、一 inode は複数名または一時的に無名でも参照され得る。同一ファイルシステムの rename は通常名前空間のメタデータを変え、大きい内容をコピーしない。正確な書込数は実装と置換先による。
• rm が全バイトを消すと思う。項目と参照を減らす操作で、媒体の消去は別だ。SSD のマッピングとウェアレベリングは単純上書きモデルで保証できない。
• ハードリンクをコピーやシンボリックリンクと混同する。前者は inode、内容、サイズ、権限を共有し、原名の区別がなく、通常ファイルシステムを越えない。後者はパスを持つ別オブジェクトで、境界を越えたりリンク切れになったりする。
• 一つの ls で全占有が分かると思う。別名や開いた参照がファイルを保持する場合がある。
• 空きバイトだけを見る。このモデルや一部形式は inode が独立に尽きる。他は動的に記録を割り当て、別のメタデータ制約もある。該当する環境では df -i と通常 df を分けて見る。
• パス階層が無料だと思う。本課は各成分二読み取り。実キャッシュで隠れても、冷たい階層、ネットワーク FS、多数の探索は測る価値がある。

モデルの範囲

13 ブロック、8 inode、各 inode の直接ポインター 4 個なので最大四ブロック。実システムは間接ブロックや extent を使い、ext2/ext3 の間接参照、ext4/XFS/APFS の extent 系構造などがある。根はここで 0、ext 系は 2。

ディレクトリーを線形走査するが、大きいものには ext4 の dir_index ハッシュ木などがあり、全実装へ線形式を当てはめない。二つのビットマップがメモリーに常駐する以外、dentry、inode、データキャッシュはなく、権限、時刻、所有者、ジャーナル、メモリの開いたファイル表はない。unlink の途中で電源が失われれば不整合になり得て、この順序だけで耐久性を保証するものではない。

試験用ファイルでメタデータとリンクを観察するコマンド：

stat notes.txt          # inode number, size, link count, block count
ls -i                   # the name → inode mapping, straight from the directory
ln notes.txt backup.txt # watch the link count go to 2, with no data copied
df -i                   # inodes used and free, separately from bytes

Linux の strace -e trace=openat,read ./your-program はシステムコールを示し、内部の全名前探索や物理ディスク読込を展開しない。filefrag -v は対応形式の extent を見せる。macOS の stat -f '%i %l %z' は inode、リンク数、サイズ、fs_usage -f filesys は FS 操作を示す。ハードリンクで 1→2 になっても内容はコピーせず、du のハードリンク計数規則やメタデータ割当が表示量へ影響する。