TECHNOLOGY LINUX KERNEL

【第12回】元東大教員から学ぶLinuxカーネル「仮想ファイルシステム」

2022年10月10日

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOS(Linuxカーネル)の授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校(UNC)コンピュータサイエンス学部で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発.
  • プログラミング歴15年以上,習得している言語: C/C++PythonSolidity/Vyper,Java,Ruby,Go,Rust,D,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開
  • 2020年1月~現在はアメリカのノースカロライナ州チャペルヒルにあるGuarantee Happiness LLCのCTOとしてECサイト開発やWeb/SNSマーケティングの業務.2022年6月~現在はアメリカのノースカロライナ州チャペルヒルにあるJapanese Tar Heel, Inc.のCEO兼CTO.
  • 最近は自然言語処理AIイーサリアムに関する有益な情報発信に従事.
    • (AI全般を含む)自然言語処理AIの論文の日本語訳や,AIチャットボット(ChatGPT,Auto-GPT,Gemini(旧Bard)など)の記事を50本以上執筆.アメリカのサンフランシスコ(広義のシリコンバレー)の会社でプロンプトエンジニア・マネージャー・Quality Assurance(QA)の業務委託の経験あり.
    • (スマートコントラクトのプログラミングを含む)イーサリアムや仮想通貨全般の記事を200本以上執筆.イギリスのロンドンの会社で仮想通貨の英語の記事を日本語に翻訳する業務委託の経験あり.

こういった私から学べます.

前回を読んでいない方はこちらからどうぞ.

Linuxカーネルの記事一覧はこちらからどうぞ.

LinuxカーネルはC言語で書かれています.

私にC言語の無料相談をしたいあなたは,公式LINE「ChishiroのC言語」の友だち追加をお願い致します.

私のキャパシティもあり,一定数に達したら終了しますので,今すぐ追加しましょう!

友だち追加

独学が難しいあなたは,元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう.後悔はさせません!

今回のテーマは仮想ファイルシステム(VFS:Virtual File System)です.

仮想ファイルシステムを理解すると,OSがファイル操作を簡単にしていることがわかります.

仮想ファイルシステム

仮想ファイルシステムは,Linuxがサポートするすべてのファイルシステムモデルを抽象化します.

C++の抽象ベースクラスと同様の概念になります.

ファイルシステムを抽象化すると以下ができます.

  • 異なるファイルシステムの共存:例えばFAT32でフォーマットされたUSBドライブとext4でフォーマットされたHDD/SSDのrootfsを同時にマウント
  • 協調:例えば,FAT32とext4ファイルシステム間でファイルをシームレスにコピー

file system

上図に仮想ファイルシステムの概要を示します.

仮想ファイルシステムは,ユーザ空間のアプリケーション(例:cp)からシステムコールを呼び出して,カーネル空間のファイルシステムを操作する場合にアクセスします.

仮想ファイルシステムは,ファイルシステム(例:ext4)を操作するために,ハードウェアのストレージ(例:HDD/SSD)にアクセスします.

共通の(Top/Bottom)仮想ファイルシステムのインタフェース

共通の(Top/Bottom)仮想ファイルシステムのインタフェースを紹介します.

仮想ファイルシステムは,ユーザ空間が共通のインタフェースで,保存されている具体的なファイルシステムに依存せずにファイルにアクセスすることを可能にします.

標準的なシステムコールとして,open,read,write,lseek等があります.

また,ユーザ空間とのTop仮想ファイルシステムのインタフェースにより,ファイルシステム間で透過的に動作します(下図).

common file system interface

ファイルシステム抽象化レイヤを紹介します.

仮想ファイルシステムはユーザ空間の要求を対応する物理ファイルシステム(例:ext4,FAT32,JFFS2)にリダイレクトします.

つまり,ファイルシステム抽象化レイヤは,ファイルシステムを利用したBottom仮想ファイルシステムのインタフェースです.

Linuxカーネルで新しいファイルシステムを開発することは,Bottom仮想ファイルシステムのインタフェースに準拠することを意味します.

※Top仮想ファイルシステムのインタフェースは共通になります.

例えば,HDD/SDDでext4に書き込む場合は以下の手順になります.

  • システムコール:writeシステムコール
  • Top仮想ファイルシステムのインタフェース:sys_write関数
  • Bottom仮想ファイルシステムのインタフェース:ext4_write_begin関数とext4_write_end関数
  • HDD/SSDに書き込み:ext4_write_begin関数とext4_write_end関数の間の処理

Unixファイルシステム

Unixファイルシステムの「ファイルシステム」という用語は,ファイルシステムの種類やパーティションを指すことがあります.

下図のように,ディレクトリに整理されたファイルの階層的なツリーのことです.

unix file systems

file content

ファイルとは,ファイルアドレス0からアドレス(ファイルサイズ-1)までのバイト列を並べたものです(上図).

ファイルのメタデータとして名前,アクセス権,修正日等を持ちます.

また,以下の情報を管理します.

  • inode:ファイルの属性情報をまとめたデータ
  • dentry:ファイル名,ディレクトリ階層構造,キャッシュ情報をまとめたデータ

ディレクトリは,ファイルや他のディレクトリ(サブディレクトリ)を含むフォルダのことです.

サブディレクトリを入れ子にして,パスを作成することができます.

例えば,「/home/chishiro/Desktop/file」となります(下図).

unix file systems2

仮想ファイルシステムのデータ構造

仮想ファイルシステムのデータ構造は以下になります.

  • dentry:ファイル/ディレクトリ名と,ファイルシステムのディレクトリツリーを定義する階層的なリンク
  • inode:ファイル/ディレクトリのメタデータ
  • file:プロセスによって開かれたファイルに関する情報
  • superblock:ファイルシステムの論理パーティションに関する情報
  • file_system_type:ファイルシステムタイプ(例:ext4)に関する情報
  • 関連する操作(bottom仮想ファイルシステムのインタフェース):super_operations,inode_operations,dentry_operations,file_operations

superblock

superblock

superblockは,ファイルシステム(パーティション)に関するグローバルな情報を含みます(上図).

ファイルシステムで作成され,マウント時に仮想ファイルシステムに渡されます.

ディスクベースのファイルシステムはsuperblockを特別な場所に保存します.

他のファイルシステムにはマウント時に生成する方法があります.

linux/include/linux/fs.hでsuperblockを管理するsuper_block構造体があります.

super_operations構造体でsuperblockを操作します.

各メンバ変数は,super_block構造体を操作する関数ポインタで,主な操作関数は以下になります.

  • alloc_inode関数ポインタ:alloc_inode関数から呼び出され,inode構造体のメモリを確保し,初期化します.
  • destroy_inode関数ポインタ:destroy_inode関数から呼び出され,inode構造体に割り当てられているリソースを解放します.
  • dirty_inode関数ポインタ:inodeがdirtyとマークされたときに仮想ファイルシステムによって呼び出されます.
  • write_inode関数ポインタ:仮想ファイルシステムがディスクにinodeを書き込む必要があるときに呼び出されます.
  • drop_inode関数ポインタ:inode->i_lockスピンロックを保持したまま,そのinodeへの最後のアクセスが遮断されたときに呼び出されます.
  • evict_inode関数ポインタ:inodeに関するあらゆる情報をディスクとメモリから削除します(ディスク上のinodeと関連するデータブロックの両方).
  • put_super関数ポインタ:仮想ファイルシステムがsuperblockを解放(アンマウント)する際に呼び出されます(superblockのロックを保持した状態).
  • sync_fs関数ポインタ:仮想ファイルシステムがsuperblockに関連するすべてのdirtyデータを書き出すときに呼び出されます.
  • freeze_fs関数ポインタ:仮想ファイルシステムがファイルシステムをロックし,強制的に整合性のある状態にするときに呼び出されます.この方法は現在,LVM(Logical Volume Manager)で使用されています.
  • unfreeze_fs関数ポインタ:仮想ファイルシステムがファイルシステムのロックを解除し,再び書き込み可能にするときに呼び出されます.
  • statfs関数ポインタ:仮想ファイルシステムがファイルシステムの統計情報を取得する必要があるときに呼び出されます.
  • remount_fs関数ポインタ:ファイルシステムが再マウントされたときに呼び出されます(カーネルロックがかかった状態).
  • umount_begin関数ポインタ:仮想ファイルシステムがファイルシステムをアンマウントする際に呼び出されます.

また,ファイルシステムをマウントする関数は,linux/fs/super.cのmount_bdev関数です.

inode

inode

inodeは,ファイルやディレクトリに関するもので,メタデータとファイル/ディレクトリの操作方法に関する情報が含まれています(上図).

メタデータとして,ファイルサイズ,所有者ID/グループ等があります.

ファイル/ディレクトリがアクセスされたときに,ファイルシステムによってオンデマンドで生成されなければなりません.

Unix系ファイルシステムではディスクから読み込みます.

他のファイルシステムでは,ディスク上の情報から再構築されます.

linux/include/linux/fs.hのinode構造体でinodeを管理します.

inode_operations構造体でinodeを操作します.

主な操作関数は以下になります.

  • create関数ポインタ:open/creatシステムコールで呼び出され,通常のファイルをサポートしたい場合にのみ必要です.
  • lookup関数ポインタ:仮想ファイルシステムが親ディレクトリのinodeを検索する必要があるときに呼び出されます.探すべき名前は,dentryで見つかります.
  • link関数ポインタ:linkシステムコールで呼び出されます.ハードリンクをサポートしたい場合のみ必要です.
  • unlink関数ポインタ:unlinkシステムコールによって呼び出されるます.inodeの削除をサポートしたい場合にのみ必要です.
  • symlink関数ポインタ:symlinkシステムコールによって呼び出されます.symlinkをサポートしたい場合のみ必要です.
  • mkdir関数ポインタ:mkdirシステムコールで呼び出されます.サブディレクトリの作成をサポートしたい場合にのみ必要です.
  • rmdir関数ポインタ:rmdirシステムコールによって呼び出されます.サブディレクトリの削除をサポートしたい場合にのみ必要です.
  • mknod関数ポインタ:デバイス(char,block)inode,名前付きパイプ(FIFO)またはソケットを作成するためにmknodシステムコールによって呼び出されます.これらのタイプのinodeの作成をサポートしたい場合にのみ必要です.
  • rename関数ポインタ:renameシステムコールによって呼び出され,最初(第2引数と第3引数)のinodeとdentryから2番目(第4引数と第5引数)のinodeとdentryによって与えられる親と名前を持つようにオブジェクトの名前を変更します.

dentry(directory entry)

dentry

dentry(directory entry)はファイルまたはディレクトリを以下に関連付けるものです.

  • ファイル名/ディレクトリ名を格納する
  • ディレクトリ内の位置を保存する
  • ディレクトリ固有の操作(例:パス名検索)を実行する

例えば,「/home/lkp/test.txt」の場合,1つのdentryは'/', 'home', 'chishiro', 'test.txt' のそれぞれに関連します.

また,ディスク表現のキャッシュは,ファイルやディレクトリのアクセスに応じてオンザフライで(処理中に)構築されます.

dentryには,used,unusedまたはnegativeの値があります.

  • used:有効なinode(d_inodeが指す)に対応し,1人以上のユーザー(d_count)が存在する.メモリを解放するために破棄することはできない.
  • unused:有効なinodeであるが,現在のユーザがいない.キャッシュのためにメモリに保存される.破棄可能.
  • negative:有効なinodeを指していない.例えば,存在しないファイルをopenする.キャッシュのために保持される.破棄可能.

dentryは必要に応じて構築され,将来の迅速なパス名検索のためのdentry cache(dcache)と呼ばれるメモリに保存されます.

dcache(dentry cache)は,使用したdentryのinodeのi_dentryメンバ変数でリンクされたリストです.

1つのinodeは複数のリンクを持つことができ,したがって複数のdentryを持つことができます.

dcacheは,LRU(Least Recently Used)でソートされたunusedかつnegativeのdentryのリンクリストで,LRUリストの末尾から素早く再利用します.

ハッシュテーブル+ハッシュ関数で,dcacheに存在する対応するdentryに素早くパスを解決します.

dcacheのハッシュテーブルは,dentry_hashtableの配列です.

各要素は,同じ値にハッシュされたdentryのリストへのポインタです.

ハッシングは,d_hash関数で行います.

ファイルシステムは独自のハッシュ関数を提供することができます.

dcache 内のdentryを検索するのはd_lookup関数で行います.

成功すればdentryを返し,失敗すればNULLを返します.

inodeも同様にメモリ内のinodeキャッシュにキャッシュされます.

dcacheのdentryはinodeキャッシュのinodeをピン留めしています.

linux/include/linux/dcache.hのdentry_operations構造体でdentryを操作します.

dentryの操作する関数ポインタは以下になります.

  • d_revalidate関数ポインタ:仮想ファイルシステムがdentryを再検証する必要があるときに呼び出されます.名前の検索でdcache内のdentryが見つかるたびに呼び出されます.
  • d_weak_revalidate関数ポインタ:仮想ファイルシステムがジャンプした(選択した)dentryを再検証する必要があるときに呼び出されます.親ディレクトリのルックアップによって取得されなかったdentryでパスウォークが終了したときに呼び出されます.
  • d_hash関数ポインタ:仮想ファイルシステムがハッシュテーブルにdentryを追加するときに呼び出されます.d_hash関数に渡される最初のdentryは,名前がハッシュ化される親ディレクトリです.
  • d_compare関数ポインタ:あるdentryと与えられた名前を比較するために呼び出されます.
  • d_delete関数ポインタ:dentryへの最後の参照が削除され,dcacheがそれをキャッシュするかどうか決定しているときに呼び出されます.
  • d_init関数ポインタ:dentry割り当て時に呼び出されます.
  • d_release関数ポインタ:dentryが本当に解放されたときに呼び出されます.
  • d_iput関数ポインタ:dentryがinodeを失ったとき(割り当てが解放される直前)に呼び出されます.
  • d_dname関数ポインタ:dentryのパス名を生成すべきときに呼び出されます.
  • d_automount関数ポインタ:オートマウントデントリがトラバースする(横断する/アクセスするという意味)ときに呼び出されます(オプション).
  • d_manage関数ポインタ:ファイルシステムがデントリからの移行を管理できるようにします(オプション).
  • d_real関数ポインタ:overlay/union型ファイルシステムはこのメソッドを実装し,overlayによって隠された基礎となるdentryの1つを返します.

ファイルシステムのデータ構造

ファイルシステムのデータ構造を紹介します.

file

fileオブジェクトは,プロセスによって開かれたファイルを表します(上図).

openで生成され,closeで破棄されます.

2つのプロセスが同じファイルをオープンする場合,2つのfileオブジェクトが同じ一意なdentryを指し,そのdentry自体が一意なinodeを指します.

ディスク上のデータ構造には対応しません.

linux/include/linux/fs.hのfile構造体でファイルを管理します.

file_operations構造体でファイルを操作します.

ファイルを操作する主な関数ポインタは以下になります.

  • llseek関数ポインタ:仮想ファイルシステムがファイル位置のインデックスを移動する必要があるときに呼び出されます.
  • read関数ポインタ:readおよび関連するシステムコールによって呼び出されます.
  • write関数ポインタ:writeおよび関連するシステムコールによって呼び出されます.
  • read_iter関数ポインタ:iov_iterを宛先とする非同期読み出しの可能性があります.
  • write_iter関数ポインタ:iov_iterをソースとする非同期書き込みの可能性があります.
  • poll関数ポインタ:プロセスがこのファイルにアクティビティがあるかどうかをチェックし,(オプションで)アクティビティがあるまでスリープ状態にしたいときに仮想ファイルシステムによって呼び出されます.select/pollシステムコールによって呼び出されます.
  • mmap関数ポインタ:mmapシステムコールで呼び出されます.
  • open関数ポインタ:仮想ファイルシステムがinodeをオープンする際に呼び出されます.仮想ファイルシステムはファイルをオープンするとき,新しいfile構造体を作成します.そして,新たに確保されたfile構造体に対して呼び出されます.
  • flush関数ポインタ:ファイルをフラッシュするためにcloseシステムコールによって呼び出されます.
  • release関数ポインタ:開いているファイルへの最後の参照が閉じられたときに呼び出されます.

linux/include/linux/fs.hのfile_system_type構造体で特定の具体的なファイルシステムタイプに関する情報を管理します.

マウントされているファイルシステムとは無関係に,サポートされているファイルシステムごとに1つです(コンパイル時に選択).

linux/include/linux/mount.hのvfsmount構造体は,ファイルシステムがマウントされると作成されます.

vfsmount構造体は,ファイルシステムの特定のインスタンス「マウントポイント」を表します.

プロセスのデータ構造

process

プロセスのデータ構造を紹介します(上図).

linux/include/linux/fdtable.hのfiles_struct構造体は,オープンしたファイルやファイルディスクリプタに関するプロセス単位の情報を管理します.

linux/include/linux/fs_struct.hのfs_struct構造体は,プロセスに関連するファイルシステム情報を管理します.

linux/fs/mount.hのmnt_namespace構造体は,マウントされたファイルシステムのユニークなビューをプロセスに提供します.

まとめ

今回は仮想ファイルシステムを紹介しました.

主要なデータ構造はまとめると以下になります.

  • file_system_type構造体:ファイルシステム(例:ext4)
  • super_block構造体:マウントされたファイルシステムのインスタンス(つまりパーティション)
  • dentry構造体:パス名
  • inode構造体:ファイルのメタデータ
  • file構造体:オープンファイル記述子
  • address_space構造体:ノード単位のページキャッシュ

3つの鍵となるキャッシュは以下になります.

  • dentryキャッシュ:dentry_hashtable,dentry->d_hash,dentry->d_hash
  • inodeキャッシュ:inode_hashtable,inode->i_hash
  • ページキャッシュ:inode->i_mapping

仮想ファイルシステムを深掘りしたいあなたは,以下を読みましょう!

LinuxカーネルはC言語で書かれています.

私にC言語の無料相談をしたいあなたは,公式LINE「ChishiroのC言語」の友だち追加をお願い致します.

私のキャパシティもあり,一定数に達したら終了しますので,今すぐ追加しましょう!

友だち追加

独学が難しいあなたは,元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう.後悔はさせません!

次回はこちらからどうぞ.

-TECHNOLOGY, LINUX KERNEL
-, , , , , , ,