以下は、Linux カーネル文書、Documentation/filesystems/path-lookup.txt の kanda.motohiro@gmail.com による訳です。原文と同じ、GPL v2 で公開します。
パスウオークと名前検索のロッキング
====================================
パス解決とは、パス名文字列に対応する dentry を、パスウオークをしながら探すことです。典型的には、すべての open(), stat() etc. のたびに、パス名が解決されます。パスは、既知の dentry を持つ、パス名の最初のコンポーネント（つまり、ルートあるいはカレントワーキングディレクトリ）から始まって、パス文字列の次のコンポーネントの名を持つその dentry の子を探すというように、名前空間のツリーをウオークすることで解決されます。その子の dentry から、次の要素を持つ子を探す、というように、検索を繰り返します。
これは、マルチユーザー環境やウェブサーバーのようなワークロードでは頻繁に行われる操作なので、このコードを最適化するのは重要です。
パスウオーク同期の歴史：
2.5.10 以前は、d_lookup (dcache ハッシュ検索) で dcache_lock が取られました。ということは、パス検索のすべてのコンポーネントで、ということです。2.5.10 からは、 fast-walk アルゴリズムが、最初に dcache_lock を取って、可能な限り多くのキャッシュされた dentry コンポーネントをウオークするように変わりました。しかし、それはロック保持時間をとても長くし、大規模 SMP マシンでの性能に影響を与えました。2.5.62 カーネルから、dcache は、 RCU を使って、ロック無しの dcache 検索を可能とする新しいロックモデルが使われるようになりました。
前記すべてのアルゴリズムは、検索する dentry のロックを取って、参照カウントを上げる必要があります。これは、その dentry が次のパス要素をウオークするためのベースとなるために必要です。これは、非効率的で、スケールしません。非効率というのは、すべての dentry 要素に必要なロックとアトミック操作がすべてを遅くするためです。スケールしないというのは、パスウオークを頻繁に行う多くの並列アプリケーションは、通常、共通の dentry
(普通は、ルート、 "/" あるいはカレントワーキングディレクトリ)からパス検索を始めるからです。このため、これらの共通パス要素に対する競合が、ロックとキャッシュラインのキューイングをもたらします。
2.6.38 から、 RCU を使って、パスウオーク全体の大部分（dcache 検索も含む）を完全に「ストアなし」にすることができるようになりました。（つまり、ロックも、アトミック操作も、共通の dentry のキャッシュラインへのストアもなし。）これが、「rcu-walk」パスウオークです。
パスウオークの概要
=====================
名前文字列は、開始点（ルートディレクトリ、カレントワーキングディレクトリ、ファイルディスクリプタ相対）と、要素（ディレクトリエントリー名）のシーケンスを指定し、その両方で、ネームスペース内のあるパスを参照します。パスは、(dentry, vfsmount) タプルで表現されます。名前の要素は、 '/' で区切られた、サブ文字列です。
名前検索は、名前文字列が参照する特定のパス（普通は、最後の要素あるいは、その親）を見つけようとします。これは、まず、名前文字列の開始点で示されるパス（それは、あらかじめ、わかっています。つまり、current->fs->cwd あるいは current->fs->root）を得て、検索のための最初の親とします。次に、続く名前要素に対して、繰り返し、現在の親の子の中から、求める名前のものを探し、それが最後でなければ、それを次の検索のための親とします。
親は、当然、ディレクトリでなくてはいけませんし、親の inode に、それをたどるための適当なパーミッションを持っていなければいけません。
子を、次の検索のための親とするためには、さらにチェックと手続きが必要です。シンボリックリンクは、名前文字列の中のシンボリックリンク名を、ターゲットと入れ替え、再帰的なパスウオークを必要とします。マウントポイントは、たどられなくてはならず、（以降のパス要素が参照する vfsmount を変更します。）マウントポイントのパスから、マウントされた vfsmount のルートにスイッチします。これらのふるまいは、パスウオークの実際にフラグによって、いろいろ、変化します。
パスウオークは、一般的に言って、以下のことが必要です。
- ウオークの開始点を探す。
- inode のパーミッションと有効性のチェックをする。
- （親、名前要素）タプルを、 dcache ハッシュ名前検索する。
- マウントポイントを超える。
- パスの部分を検索し、必要に応じて、存在しない部分を作成する。
安全な、ストアをしない、 dcache ハッシュテーブルの検索
============================================
Dcache 名前検索
------------------
dcache（親、名前）タプルを検索するには、タプルのハッシュを計算して、それを dcache ハッシュテーブルのバケツを選択するのに使います。次に、バケツのエントリーのリストがウオークされ、それぞれのエントリーに対して、（親、名前）タプルの完全な比較をします。
ハッシュリストは RCU で守られているので、リストウオークは同時の更新（ハッシュへの挿入、削除）とはシリアライズされていません。これは、 RCU リストの一般的な例です。ただ、後述するリネームだけは特別です。
dentry にある親と名前メンバー、そして dcache ハッシュへの所属、そして inode は、dentry ごとにある d_lock スピンロックで守られます。dentry の参照カウントが取られ、（d_lock のもとでフィールドが調べられた後）これによって、 d_inode ポインターと実際の inode が安定します。このように、次のパスウオークのステップをするための安定したポイントが得られます。
前記メンバーは、 d_seq seqlock でも守られています。ただ、これはリードオンリーの保護で、結果に永続性はありません。このため、 d_seq で同期をするときには、注意が必要です。（以下の seqcount ベースの検索を参照。）
リネーム
-------
リネームの場合に戻りましょう。通常の RCU 保護されたリストでは、オブジェクトに対する操作は、挿入と、いずれ最後になされる削除です。オブジェクトは、 RCU グレースピリオドが終わるまで、再使用されません。これによって、 RCU リストをたどる操作は問題なしにオブジェクトを渡り歩くことができます。（詳しくは、 RCU の文書を参照。）
しかし、 dentry がリネームされるときは、そのハッシュ値が変わり、新しいハッシュリストに移動する必要があることがあります。新しい別名をアロケートして、挿入するのは、高価で、ディレクトリ dentry には問題があります。 dentry を削除した後、新しいハッシュバケツに挿入する前に、グレースピリオドだけ待つというのは、遅延が大きくなりすぎます。なので、実際には、 dentry は、直ちに、新しいリストに挿入されます。
しかし、 dentry のリストポインターが、グレースピリオドを待つことなく、新しいリストのオブジェクトを指すように更新されるとすると、同時に行われる、古いリストに対する RCU 検索が、新しい（誤った）リストに突っ込んでくることになり、古いリスト上の残りのエントリーを見ないで終わることになります。
誤ったリストをウオークすることは、根本的な問題ではありません。dentry 比較は、決してマッチしませんから。しかし、マッチすべきエントリーを見逃すことがあるのは、とてもまずいことです。このために、 seqlock を使って、リネームが起きたかを検出し、検索をリトライできるようにします。
1 2 3
+---+ +---+ +---+
hlist-->| N-+->| N-+->| N-+->
head <--+-P |<-+-P |<-+-P |
+---+ +---+ +---+
dentry 2 をリネームすると、それを前記リストから削除し、新しいリストに挿入することになります。以下のようになります。
1 3
+---+ +---+ (ご心配なく。ポインターが長くても、
hlist-->| N-+-------->| N-+-> 現代の CPU では、測定できるほどの
head <--+-P |<--------+-P | 性能の変化はありません。)訳注。ジョークなのかな。
+---+ +---+
^ 2 ^
| +---+ |
| | N-+----+
+----+-P |
+---+
これが、通常の RCU リスト削除です。削除されたオブジェクトのポインターはそのままなので、現在オブジェクト２をたどっている同時実行するリストウオーカーは、次のオブジェクトへ行く時には、正しく、オブジェクト３をたどります。
しかし、オブジェクト２を新しいリストに挿入すると、こうなります。
1 3
+---+ +---+
hlist-->| N-+-------->| N-+->
head <--+-P |<--------+-P |
+---+ +---+
2
+---+
| N-+---->
<----+-P |
+---+
グレースピリオドまで待たなかったので、２への同時実行する検索があるかもしれません。それが、２の「次の」ポインターをたどった場合、オブジェクト３をチェックすることなく、別のリスト上にウオークしていってしまいます。
関連する、しかし、明らかにまた別の問題は、検索操作に対する、リネームのアトミシティです。ファイルが、「A」から「B」にリネームされたら、検索は、「A」あるいは「B」のどちらか１つを見つけるべきです。なので、「A」の検索が NULL を返したなら、次に行う「B」の検索は成功しなくてはいけません。（逆は真ではないのに注意。）
dentry を古いハッシュリストから削除して、新しいハッシュリストに挿入する間に、検索は、マッチする dentry として、「A」も「B」も見つけることができないことがあります。この競合をカバーするために、同じリネーム seqlock が、同じように使われます。つまり、リネームが実行中であるとわかったら、ネガティブの検索結果をリトライします。
Seqcount ベースの検索
----------------------
参照カウントベースの dcache 検索では、d_lock が、 dentry へのアクセスをシリアライズするために使われます。それは、dentry の名前と親を比較し、参照カウントを取るまでの間、dentry を安定化させます。（次に、参照カウントが、そこからパスウオークの次の部分を始めるための安定した場所を提供します。）
以前に説明したように、私たちの目的は、パスの中間にある dentry のロックや参照カウントを取らないでパスウオークをすることです。このために、dentry ごとの seqlock (d_seq) を使って、 dentry の名前、親、そして inode の「一貫したスナップショット」をとります。そのスナップショットが、パスウオークの次の部分を始めるのに使われます。 d_seq のもとで、一貫したスナップショットを作成するとき、まず最初にメンバーを読み込んで、後からはそのポインターを使い、 dentry からの再ロードは行わないことが重要です。（そうでないと、名前がアンリンクされたときに、足元の d_inode がNULL になるなど、興味深いことが起きます。）
また、いかなる破壊的操作もしないことが重要です。（ほぼ、共用データへのアトミックでないストアのこと）そして、操作が「終わった」ら、 seqcount をもう一度チェックします。 seqcount が違っていたら、リトライ、あるいは中止します。破壊的あるいは変更する操作を避けるのは、失敗したときに、簡単にやりなおせるからです。
この結果、コール元は、 dentry が消えないように RCU ロックを持っていれば、 seqcount ベースの検索ができ、 dentry の参照カウントを上げたり、いかなる意味でも書き込んだりしないで済むということです。こうして返された dentry は、以降の操作で、操作の完了後に d_seq を再チェックすれば使えます。
inode も rcu を使って解放されますから、 seqcount 検索された dentry の inode を参照してアクセス権のチェックをすることができます。
パズルのこの２つの部分を使って、 dentry 要素へのロックも参照カウントもないパス検索ができるのです。
RCU-walk パスウオークの設計
============================
パスウオークのコードは、今では、２つの異なるモードを持ちます。ref-walk と rcu-walk です。ref-walk は、 dcache 検索をする伝統的な[*] 方法で、 dentry への同時の変更をシリアライズするために、 d_lock を使い、dentry の参照カウントを取ります。ref-walk はシンプルで明示的で、それぞれの dentry をパスウオークする間、スリープしても、ロックを取ってもかまいません。rcu-walk は、 seqcount ベースの dentry 検索を行い、中間の要素の検索を、dentry や inode にある共有データへのストアを全くせずに行えます。rcu-walk はすべての場合に使えるわけではありません。例えば、ファイルシステムがスリープしたり、複雑な操作をしなくてはいけないときは、rcu-walk は ref-walk モードにスイッチされなくてはいけません。
[*] RCU は、ref-walk の dentry ハッシュ検索で使われますが、完全なパスウオークでは使われません。
ref-walk が、安定した、参照カウントされた「親」を使って、残りのパス文字列をウオークするのに対して、rcu-walk は d_seq で保護されたスナップショットを使います。この親のスナップショットの子を検索するとき、親の d_seq クリティカルセクションを閉じる前に、子の d_seq クリティカルセクションを開きます。これは、ウオークダウンできる、ロックのはしごを提供します。
proc 101
/----------------\
/ comm: "vi" \
/ fs.root: dentry0 \
\ fs.cwd: dentry2 /
\ /
\----------------/
なので、例えば、 vi が open("/home/npiggin/test.c", O_RDWR), する場合、まず、current->fs->root から始めます。それは、メモリ常駐 dentry です。あるいは、"./test.c" として開けば、 cwd から始めます。名前はどちらも、 proc101 のコンテキストでは同じパスを参照します。
dentry 0
+---------------------+ rcu-walk はここから始まります。d_seq を覚えて、
| name: "/" | inode のパーミッションをチェックし、次のパス要素である
| inode: 10 | "home" を検索します...
| children:"home", ...|
+---------------------+
|
dentry 1 V
+---------------------+ ... するとこうなります。dentry1 が、ハッシュ検索で
| name: "home" | 見つかります。ここで、 d_seq を覚えて、名前文字列と
| inode: 678 | 親ポインターを比較します。同じなら、dentry0 の d_seq
| children:"npiggin" | を再度チェックします。次に、 inode をチェックして、
+---------------------+ 次の要素を検索します。
|
dentry2 V
+---------------------+ 注意：ここで、 dentry0 が更新されても、検索は無効に
| name: "npiggin" | なる必要はありません。なので、d_seq のチェックのためには、
| inode: 543 | 親だけを覚えていれば良く、親の親は忘れることができます。
| children:"a.c", ... |
+---------------------+
|
dentry3 V
+---------------------+ ここまで来ると、目的の dentry があります。
| name: "a.c" | その d_lock を取り、この dentry の d_seq を
| inode: 14221 | チェックします。OK なら、参照カウントを上げることができます。
| children:NULL | d_lock を持っているので、それは可能です。
+---------------------+
rcu-walk モードから、 dentry の参照カウントを取る、つまり、 d_lock を取って、 d_seq を再チェックして、参照カウントを上げる、のを、「dropping rcu」あるいは、rcu-walk から ref-walk モードに落ちる、と呼びます。
これは、ある意味では、トランプの家です。親のスナップショットでの seqcount チェックが失敗すれば、家はくずれてしまいます。親の親の d_seq セクションはクローズしてしまったので、立つべき場所は残っていません。その場合、パスウオークは完全にやり直さなくてはいけません。（ref-walk モードでも、ライブロックを防ぐためにそうすることがあります。）完全な再開始は高価ですが、幸運なことにそれはとてもまれです。
スリープが必要だったり、ファイルシステムのコールバックが ref-walk を必要とするところに達したら、ウオークを再開始する代わりに、手元にある最後の正しいとわかっている dentry において、 rcu ドロップを試みます。こういう場合、 ref-walk において、完全な再開始を避けるのは、性能とスケーラビリティにとって基本的に重要です。creat や unlink など、ブロックする操作はまれではありませんから。
rcu-walk の詳細な設計は以下のとおりです。
* nd->flags に LOOKUP_RCU を立てます。これが、rcu-walk と ref-walk を区別します。
* パスウオーク全体の RCU ロックを取ります。パスの開始点 (eg. root/cwd/fd-path) から取ります。
ここで、 dentry 参照カウントは、dentry の永続性のためには必要なくなります。
* ファイルシステムが登録解除するときには、 synchronize_rcu を呼びますから、rcu-walk の間、d_ops と i_ops をアクセスしても安全です。
* 同様に、パスウオーク全体の vfsmount ロックを取ります。ここで、 mnt 参照カウントは、永続性のためには必要なくなります。また、mount 検索をすることもできますし、マウントポイントの dentry とマウントルートが、パス全体で安定化していることを前提とできます。
* dentry ごとの seqlock を取って、 dentry の名前、親、そして inode を守ります。これによって、これらのタプルをアトミックにロードでき、そのメンバーのどれかが変更されたかチェックすることもできます。
* Dentry 検索（親、目的の文字列のタプルによる）のときに、子が見つかった後で、親のシーケンス番号を再チェックして、パスウオークの間に、親において何か変更がなかったか確認します。
* inode も RCU で守られているので、 d_inode をロードして、その inode を限られた範囲で使うことができます。
* i_mode, i_uid, i_gid を見て、パスウオークの間、実行パーミッションのチェックができます。
* i_op をロードできます。
* 目的の dentry に着いたら、そこで rcu を落とします。(ie.d_lock を取って、 d_seq をチェックし、参照カウントを上げます。)
* パスのどこかで seqlock チェックが失敗したら、 ref-walk でパス検索の完全な再開始をします。 rcu-walk の失敗を示すのには、 -ECHILD が使われることが多いです。（もっとよい errno があるとよいのですが。）
rcu-walk が続けられないケースは：
* NULL dentry （つまり、パス要素がキャッシュされてない時）
* リンクをたどる時
.
リンクをたどるのは、いずれ、 rcu-walk でできるようになるかもしれません。
パス要素がキャッシュされてない時は、必ず、 ref-walk モードに落ちる必要があります。少なくとも、 i_mutex を取ったり、オブジェクトを確保したりする必要がありますから。
最後に：
「ストアなし」パスウオークと言っても、厳密にはストアがあります。 vfsmount ロックと参照カウントを取ります。（どちらも、CPU ごとにできます。）それに、スタックへのストアもします。（当然、CPU ローカルです。）最後の dentry に対しては、ロックと参照カウントを取る必要があります。
重要なのは、共用データ、現実的に可能な限り、には、ロックもストアもないことです。この結果、パス解決において素晴らしい性能向上とスケーラビリティが得られました。
面白い統計
======================
以下の表は、いくつかの簡単なワークロード(2s12c24t Westmere, debian グラフィカルシステムでない)に対しての、 rcu 検索の統計です。Ungraceful （訳注。restart）は、 d_seq 失敗の結果、rcu drop して、完全なパス検索をやり直さなくてはいけなかった回数です。他の場合は、最後の要素の前に rcu drop が必要だった（訳注。けど、途中からドロップするだけで済んだ良いケース。）回数です。nodentry は、 dentry がない場合、 revalidate は、ファイルシステムの revalidate ルーチンが rcu drop を必要とした場合、permission は、パーミッションチェックのためにドロップした場合、そして link はシンボリックリンクをたどるためにドロップした場合です。
rcu-lookups restart nodentry link revalidate permission
bootup 47121 0 4624 1010 10283 7852
dbench 25386793 0 6778659(26.7%) 55 549 1156
kbuild 2696672 10 64442(2.3%) 108764(4.0%) 1 1590
git diff 39605 0 28 2 0 106
vfstest 24185492 4945 708725(2.9%) 1076136(4.4%) 0 2651
これでわかるのは、 rcu-walk 検索の失敗、つまり、 ref-walk ではじめからやり直したもの、はとてもまれだということです。"vfstest" の場合、特に同時実行する renames/mkdir/rmdir/ creat/unlink/etc がそのような競合を引き起こすはずですが、restart はそれほどではありません。
rcu-walk から ref-walk にドロップするということは、何らかの理由で参照カウントを取らないといけない dentry にあたったということです。パスウオークの目的に着いたのかもしれません。 rcu-walk モードでは対処できない状況になったのかもしれません。理想的には目的の dentry に着いた時だけ、ドロップするべきなので、それ以外の統計項目は、それがかなわなかった回数です。
rcu-walk モードからの失敗ではないドロップ、例えば、dentry がなかったため、（これはよくあることです。）というのは、rcu-walk スキーマの失敗とは必ずしも言えません。なぜならば、パスのいくらかの要素は、rcu-walk モードでたどれたかもしれないからです。共通パス要素（cwd あるいは root）から離れれば離れるだけ、 dentry の競合は少なくなるでしょう。逆に、共通パス要素に近づけは、それだけ、 dentry キャッシュにのっている可能性も高まります。
dcache ロックについての論文と他の文書
================================================
1. Scaling dcache with RCU (http://linuxjournal.com/article.php?sid=7124).
2. http://lse.sourceforge.net/locking/dcache/dcache.html
以上