ユニオン・ファイル・システム。 実装、パート I


This article brought to you by LWN subscribers

Subscribers to LWN.net は、この記事とそれにまつわるすべてのことを可能にしてくれました。 もし、私たちのコンテンツを評価してくださるなら、ぜひ購読を申し込んで、次の記事を実現してください。

March 25, 2009

この記事は Valerie Aurora (formerly Henson) によって投稿されました

先週の記事では、ファイル システムの結合に関する使用例、基本概念、および共通の設計問題点について概説しました。 今週は、ユニオニング ファイル システムのいくつかの実装について、技術的な詳細を説明します。 この記事で取り上げるユニオニング・ファイルシステムは、Plan 9ユニオンディレクトリ、BSDユニオンマウント、Linuxユニオンマウントです。 次回は、unionfs、aufs、そしておそらく他の1つか2つのユニオニングファイルシステムを取り上げ、このシリーズを締めくくります。

各ファイルシステムについて、その基本アーキテクチャ、機能、および実装を説明します。 実装については、特にホワイトアウトとディレクトリの読み込みに焦点を当てます。 この記事を読む前に、昨年 11 月に開催された union mount ワークショップの AndreasGruenbacher の記事をチェックするとよいでしょう。 これは、ディストリビューション開発者にとって最も緊急の課題である、ファイル システムのユニオンの特徴についてよくまとめられています。 その序文から。 「それは、読み取り専用で使用されるイメージまたはファイルシステム (書き込み可能でないか、イメージへの書き込みが不要なため) を持ち、このイメージまたはファイルシステムが書き込み可能であるように装い、変更を別の場所に保存することです」

Plan 9 統合ディレクトリ

The Plan 9 operatingsystem(browseable source code here) は独自の特別な Plan 9 方法で統合を実装しています。 Plan 9 の組合わせディレクトリでは、トップレベルのディレクトリ名空間のみがマージされ、サブディレクトリはマージされません。 UNIX 規格の制約を受けない Plan 9 組合ディレクトリは、ホワイトアウトを実装せず、重複するエントリーを選別することもありません。

Plan 9 のユニオン・ディレクトリは次のように作成されます。

 bind -a /home/val/bin/ /bin

この場合、ディレクトリ/home/val/binは、(-aオプションの)/binより後にユニオンマウントされることになります。 (私は、個人的なbin/のコマンドがシステム全体のコマンドよりも優先されることを好むので、これは奇妙な順序付けに思えますが、これは Plan 9 の文書にある例です)。 Brian Kernigh は、組合ディレクトリの用途の 1 つを説明しています。 「このユニオンディレクトリのメカニズムは、従来の UNIX シェルの検索パスを置き換えるものです。 あなたに関する限り、すべての実行可能なプログラムは /bin にあります。 ユニオンディレクトリは、理論的には、シンボリックリンクと検索パスという基本的なUNIXビルディングブロックの多くの用途を置き換えることができる。

ホワイトアウトや重複排除を行わない場合、readdir()ユニオンディレクトリを実装することは些細なことである。 基礎となるファイルシステムからのディレクトリエントリオフセットは、ディレクトリの先頭からのディレクトリエントリのバイト単位のオフセットに直接対応します。 dirread() は stat()man ページで説明されている Dir 型の構造体を返します。 Dirの中で重要なのはQidメンバである。 Qid は、

…path と vers フィールドを含む構造体です。path は現在ファイルサーバにあるすべてのパス名の中で一意であることが保証され、vers はファイルが変更されるたびに変化します。 path は long long (64 ビット、vlong)、vers は unsigned long (32 ビット、ulong) です。

では、なぜこれが面白いのでしょうか。 readdir() の実装が面倒な理由の 1 つは、struct direntd_off メンバー、つまり単一の off_t (アプリケーションがラージ ファイル サポートでコンパイルされていない限り 32 ビット) を返し、次の readdir() 呼び出しでアプリケーションが読み取りを続行すべきディレクトリ エントリをマークすることです。 これは、d_offが232バイト以下のフラットファイルへの単純なバイトオフセットであり、既存のディレクトリエントリが移動されない限り、問題なく動作します-最近の多くのファイルシステム(XFS、btrfs、htreeインデックスを持つext3)ではそうではありません。 96 ビットの Qid は、32 ビットや 64 ビットの off_t よりもはるかに有用なプレースマーカーです。 readdir() の実装に関わる問題の良いまとめとしては、TheodoreY. Ts’o の btrfs メーリングリストへのこのトピックに関する素晴らしい投稿をお読みください。

ソフトウェアエンジニアリングの観点から、Plan 9 ユニオンディレクトリは天国のようです。 ホワイトアウト、重複エントリーの除去、複雑なディレクトリのオフセット、トップレベルのディレクトリを超えるネームスペースのマージなどがなく、実装はシンプルでメンテナンスが容易です。しかし、Linux (または他の UNIX) 用のユニオンファイルシステムの実用的な実装は、これらの問題を解決しなければならないでしょう。

BSD union mounts

BSD は 2 種類のユニオニングを実装しています。mountコマンドの"-o union"オプションは Plan 9 と同様の union ディレクトリを生成し、mount_unionfsコマンドはホワイトアウトと全名前空間のマージを含むよりフル機能のユニオニングファイルシステムを実装しています。 この記事では、具体的な実装の詳細について、1995 年の USENIX paperUnionmounts in 4.4BSD-Lite に記載されたオリジナルの BSD ユニオンマウント実装と FreeBSD7.1 のmount_unionfsman ページおよびソースコードの 2 つのソースを使用します。

書き込み可能なユニオンのトップブランチが書き込み可能である限り、 ディレクトリは既存のディレクトリやユニオンマウントの「下」でも「上」でも ユニオンマウントすることが可能です。 ホワイトアウトの 2 つのモードがサポートされています。ディレクトリが削除されるとホワイトアウトが常に作成されるか、またはその名前を持つ別のディレクトリ・エントリが書き込み可能なブランチの下のブランチに現在存在する場合にのみ作成されます。 コピーアップされたファイルの所有権とモードを設定するための3つのモードがサポートされています。 最も単純なのはtransparentで、新しいファイルは元のファイルと同じオーナーとモードを保持する。 masquerade モードはコピーされたファイルを特定のユーザが所有するようにし、新しいファイルのモードを決定するマウントオプションのセットをサポートする。 traditional モードは所有者をユニオンマウントコマンドを実行したユーザに設定し、ユニオンマウント時の umask に従ってモードを設定する。

ディレクトリが開かれるといつでも、まだ存在していなければ同じ名前のディレクトリが最上層の書き込み可能に作成される。 論文より:

ルックアップ時に積極的にシャドウ ディレクトリを作成することにより、ユニオン ファイルシステムは、マウントのルートからコピーアップのポイントまでのディレクトリのチェーンをチェックし、場合によっては作成する必要性を回避します。ディレクトリによって消費されるディスク容量はごくわずかなので、最初に通過するときにディレクトリを作成することがより良い選択肢のように思えました。

結果として、"find /union" はすべてのディレクトリ (ただし、非ディレクトリを指すディレクトリエントリは除く) を書き込み可能な層にコピーすることになります。

ファイルは、書き込み権限でオープンされるか、 ファイルの属性が変更されると、最上位層にコピーされる。 (ディレクトリはオープン時にコピーされるため、含まれるディレクトリは書き込み可能な層に既に存在することが保証されます)。 コピーアップされるファイルに複数のハードリンクがある場合,他のリンクは無視され,新しいファイルのリンク数は1です。 これは、ハードリンクを使用し、1つのリンク名による変更が別のハードリンクを介して参照されたときに表示されることを期待するアプリケーションを破壊する可能性があります。 そのようなアプリケーションは比較的まれですが、この状況でどのアプリケーションが失敗するかについて、誰も体系的な研究を行っていません。

ホワイトアウトは、特別なディレクトリ・エントリタイプ、DH_WHT で実装されています。 ホワイトアウトのディレクトリエントリは実際の inode を参照しませんが、fsck のような既存のファイルシステムの機能との互換性を保つために、各ホワイトアウトのディレクトリエントリには偽の inode 番号、WINO 予約ホワイトアウトノード番号が含まれています。 ホワイトアウトディレクトリエントリをサポートするために、基礎となるファイルシステムを変更する必要があります。 ホワイトアウトのエントリを置き換える新しいディレクトリは、新しい “opaque” inode 属性を介して不透明としてマークされ、ルックアップがそれを通過しないようにします (これも、基礎となるファイルシステムの最小限のサポートが必要です)。 opendir() 時に、C ライブラリはディレクトリを一度に読み、重複を削除し、ホワイトアウトを適用し、結果をキャッシュします。

BSD のユニオンマウントは書き込み可能なトップブランチ以下のブランチの変更を扱おうとしません (許可はされていますが)。 mount_unionfs man ページからの例です。

 The commands mount -t cd9660 -o ro /dev/cd0 /usr/src mount -t unionfs -o noatime /var/obj /usr/src mount the CD-ROM drive /dev/cd0 on /usr/src and then attaches /var/obj on top. For most purposes the effect of this is to make the source tree appear writable even though it is stored on a CD-ROM. The -o noatime option is useful to avoid unnecessary copying from the lower to the upper layer.

Another example (私は、ソース管理はファイルシステムの外で実装するのがベストであると考えています。):

 The command mount -t unionfs -o noatime -o below /sys $HOME/sys attaches the system source tree below the sys directory in the user's home directory. This allows individual users to make private changes to the source, and build new kernels, without those changes becoming visible to other users.

Linux union mounts

BSD union mounts と同様に、Linux union mounts は VFS レイヤーでファイルシステム結束を実装し、ホワイトアウトと不透明なディレクトリタグのために基礎となるファイルシステムからいくつかのマイナーサポートを提供します。 このパッチのいくつかのバージョンが存在し、Jan Blunck、Bharata B. Rao、および Miklos Szeredi などによって書かれ、修正されました。

このコードのひとつのバージョンは、最上位ディレクトリのみをマージし、プラン 9 ユニオンディレクトリと BSD -o unionmount オプションに似ています。 このバージョンのユニオンマウント (私はユニオンディレクトリと呼んでいます) は、Goldwyn Rodrigues による最近の LWN 記事と Miklos Szeredi による最近の更新パッチセットで詳しく説明されています。 この記事の残りの部分では、フルネームスペースをマージするユニオンマウントのバージョンに焦点を当てます。

Linux ユニオンマウントは現在活発に開発中です。 この記事では、Jan Blunck が Linux2.6.25-mm1, util-linux 2.13, e2fsprogs 1.40.2 に対してリリースしたバージョンについて記述しています。 パッチセットは、quilt シリーズとして、Jan の ftp サイトからダウンロードできます:

Kernel patches: ftp://ftp.suse.com/pub/people/jblunck/patches/

Utilities: ftp://ftp.suse.com/pub/people/jblunck/union-mount/

私は、上記のパッチの git バージョンへのリンクと、いくつかの HOWTO スタイルのドキュメントを http://valerieaurora.org/union で作成しました。

連合は、ファイルシステムを MS_UNION フラグセットでマウントすると作られます (MS_BEFOREMS_AFTER および MS_REPLACEmount コードベース で定義されていますが、現在は使用されていません。)。 MS_UNION フラグが指定された場合、マウントされたファイルシステムは読み込み専用かホワイトアウトをサポートする必要がある。 このバージョンのユニオンマウントでは、ユニオンマウントフラグは mount の “-o union” オプションで指定されます。 たとえば、2 つのループバックデバイスファイルシステム /img/ro と /img/rw のユニオンを作成するには、次のように実行します:

 # mount -o loop,ro,union /img/ro /mnt/union/ # mount -o loop,union /img/rw /mnt/union/

Each union mount creates astruct union_mount:

 struct union_mount {atomic_t u_count;/* reference count */struct mutex u_mutex;struct list_head u_unions;/* list head for d_unions */struct hlist_node u_hash;/* list head for searching */struct hlist_node u_rhash;/* list head for reverse searching */struct path u_this;/* this is me */struct path u_next;/* this is what I overlay */ };

Documentation/filesystems/union-mounts.txtで説明したように、「すべての union_mount 構造は、ユニオンスタックの次の下位層を参照するための 1 つのハッシュとユニオンスタックの次の上位層を逆引きするための 1 つのハッシュテーブルでキャッシュされる」のです。”

ホワイトアウトと不透明なディレクトリは、BSD とほぼ同じ方法で実装されています。 ext2 と ext3 の実装では、ホワイトアウトのディレクトリエントリタイプである DT_WHT が使用されます。 予約された whiteout inodenumber, EXT3_WHT_INO が定義されましたが、まだ使用されていません; whiteout エントリーは現在通常の inode を割り当てています。 新しい inode フラグ S_OPAQUE は、ディレクトリを不透明にするために定義されています。BSD と同様に、ディレクトリはホワイトアウトエントリを置き換えるときのみ不透明になります。 必要であれば、ファイルへのパスの各ディレクトリがトップブランチにコピーされます (ディレクトリのコピーオンデマンド)。

readdir() は、現在の実装の最も弱い点の一つである。 これは BSD の union mountreaddir() と同じ方法で実装されていますが、カーネル内にあります。 d_off フィールドは、現在のディレクトリのオフセットから前のディレクトリのサイズを引いた値に設定される。 最上層のディレクトリの下にあるディレクトリのエントリは、 重複やホワイトアウトがないか、以前のエントリと照合する必要があります。 現在の実装では、各 readdir() (技術的には getdents()) システムコールは以前のすべてのディレクトリ・エントリーをカーネル内のキャッシュに読み込み、返す各エントリーをユーザー・バッファにコピーする前にキャッシュ内のそれらと比較します。 その結果、readdir() は複雑で遅く、潜在的に大量のカーネル メモリを割り当ててしまいます。

1 つの解決策は、BSD のアプローチを採用して、ユーザー空間でキャッシュ、ホワイトアウト、および重複処理を実行することです。 Bharata B. Rao は glibc におけるユニオンマウント readdir() のサポートを設計しています (POSIX 標準では、素のカーネルシステムコールがすべての要件を満たさない場合、 readdir() を libc レベルで実装することが許可されています)。 これにより、メモリ使用量がアプリケーションに移動し、キャッシュが永続化されます。 836>

私の提案は、BSD のユニオンマウントから技術を取り入れ、それを拡張することです:積極的にディレクトリのディレクトリエントリだけでなく、下位ファイルシステムからのすべてのディレクトリエントリをコピーし、重複とホワイトアウトを処理し、ディレクトリを不透明にして、それをディスクに書き出すことです。 事実上、ディレクトリの最初のオープン時にディレクトリ・エントリのホワイトアウトと重複を処理し、その後、ディレクトリ・エントリの結果の「キャッシュ」をディスクに書き出しています。 基礎となるファイル・システム上のファイルを指すディレクトリ・エントリは、それが「フォールスルー」エントリであることを何らかの形で示す必要があります(ホワイトアウトの反対で、下位ファイル・システムでオブジェクトを検索することを明示的に要求するものです)。 このアプローチの副作用は、ホワイトアウトがまったく不要になることです。

このアプローチで解決しなければならない問題の 1 つは、下位ファイル システムを指すディレクトリ エントリをどのように表現するかということです。 エントリーは予約されたノード番号を指すことができる、 ファイルシステムは各エントリーに inode を割り当てることができるが、 新しい S_LOOKOVERTHERE inode 属性でそれをマークする、 予約されたターゲットにシンボリックリンクを作成するなど、 多くのソリューションがある。 このアプローチでは、基礎となるファイル システムでより多くのスペースを使用しますが、すべての他のアプローチでは、メモリに同じスペースを割り当てる必要があり、一般にメモリはディスクよりも大切です。

現在の実装でそれほど緊急ではない問題は、inodenum が起動時に安定していないことです (なぜこれが問題なのかについては、以前のファイル システムの結合に関する記事を参照してください)。 もうひとつのオプションは、トップレベルディレクトリのファイルや外部ファイルシステムなど、どこかに永続的な inode マップを保存することです。

ハードリンクは BSD ユニオンマウントと同じ方法で処理されます (正確に言うと、処理されません)。 繰り返しになりますが、あるハードリンクされたパスを介してファイルを変更し、別のハードリンクされたパス (シンボリックリンクとは対照的) を介して変更を確認することに依存するアプリケーションがどれほどあるのかは、明らかではありません。 これを正しく処理するために私が思いつく唯一の方法は、複数のハード リンクで遭遇した inode の永続的なキャッシュをディスク上のどこかに保存しておくことです。 例えば、inode 42 のコピーを開始し、リンク カウントが 3 であることがわかったとします。 ファイル システム ID、ノード番号、リンク数、およびトップ レベル ファイル システム上の新しいコピーのノード番号を含む、ハード リンク データベースのエントリを作成することになります。 これは、CSV形式のファイルに格納するか、ルートディレクトリの予約ディレクトリにシンボリックリンクとして格納するか(例えば、「/.hardlink_hack/<fs_id>/42」は「<new_inode_num> 3」にリンクする)、実際のデータベースに格納することができる。 もしエントリーが存在すれば、リンク数を減らし、新しいファイルシステム上の正しいinodeへのハードリンクを作成します。 すべてのパスが見つかると,リンクカウントは1になり,そのエントリーはデータベースから削除できる. この方法の良いところは、オーバーヘッドに限りがあり、関連するinodeへのパスがすべて検索された時点で完全に消滅することである。 BSD の実装では、多くのアプリケーションが、POSIXLY ではない正しいハードリンクの動作で喜んで実行されることが示されています。 ユーザ空間は通常これを透過的に処理し(異なるファイルシステムからのディレクトリに対してすでにこのケースを処理しなければならないので)、ディレクトリの内容を一つずつコピーすることにフォールバックする。 カーネル内のブランチをまたがるディレクトリの再帰的な rename() を実装することは、通常のファイルシステムをまたがる rename と同じ理由で、良いアイデアとは言えません。 VFS の変更のほとんどは、約 1000 行のファイルである fs/union.c に分離されています。 このファイルの約 1/3 はカーネル内の readdir() の実装であり、これはマージされる前にほぼ確実に他のものに置き換えられるでしょう。 このコードをマージする際の主な障害は readdir() の実装です。

ユニオンマウントの素晴らしい要約は、Bharata B. Rao の FOSS.IN 用ユニオンマウントのスライドで見ることができます。 ご期待ください。

Index entries for this article
Kernel Filesystems/Union
Kernel Union mounts
GuestArticles Aurora (Henson).But Butterfly (Author)。 ヴァレリー

について

コメントを残す

メールアドレスが公開されることはありません。