linux/Documentation/filesystems/directory-locking のテキトー訳

# はじめに

誰得？という気もしますがLinux kernelに含まれるドキュメント https://www.kernel.org/doc/Documentation/filesystems/directory-locking をテキトーに訳してみました。

* マルチプロセス、マルチスレッド、マルチコアの環境であちこちからファイルシステムのツリーに対する操作があってもツリーが壊れない
* ロックできるかぎり局所的なものにして並列動作時の性能を向上させる

という目標のためにどんな手法を使ってるかがわかると思います。この部分に限らずLinuxのファイルシステムの排他制御はスケーラビリティと性能のための工夫が大量に実装されているので、非常に興味深いです。

Readers-Writer lockのshared / read lockの方を「共有モード」のロック、exclusive write lockを「排他モード」のロックって書いてます。

変だなと思ったら原文の方を参照してください(5個とあるのに6まで番号があるのは原文もです)。

# directory-locking

ディレクトリ操作時のロックは二つのロックを用いて行われます - inode単位のもの(->i_rwsem)とファイルシステム単位のもの(->s_vfs_rename_mutex)です。

複数の非ディレクトリのi_rwsemをロックする時は、常にアドレスの昇順で行います。以後、これをinodeポインタの順序と呼びます。

この説明において、全ての操作は5つの種類に分類します。

1. 読み込み。ロックのルール：呼び出し元がロックを取得します。このロックは共有モードで取得されます。

2. オブジェクトの作成。ロックのルール：上に同じですが、ロックは排他モードで取得されます。

3. オブジェクトの削除。ロックのルール：呼び出し元は親オブジェクトをロックし、消されるオブジェクトを見つけてそれをロックしてからメソッドを呼び出します。この時のロックは排他モードです。

4. rename()のディレクトリをまたがないもの。ロックのルール：呼び出し元は親オブジェクトをロックし、リネーム元と先を探します。交換の場合(RENAME_EXCHANGEがflag引数で指定された場合)はリネーム元と先の両方をロックします。どのような場合ではリネーム先が存在すればロックします。もしリネーム元がディレクトリでない場合にもロックします。もし、両方をロックする必要があれば、ポインタの順序でロックします。
ロックができたらメソッドを呼びます。全てのロックは排他モードです。
注意：リネーム元(交換の場合はリネーム先も)のロックを共有モードに弱めるかもしれません

5. リンクの作成。ロックのルール：
 * 親オブジェクトをロック
 * ソースがディレクトリでないことをチェック
 * ソースをロック
 * メソッドを呼び出す
全てのロックは排他モードです。

6. ディレクトリをまたぐリネーム。これが最もトリッキーな部分です。ロックのルール：
 * ファイルシステムをロック
 * それぞれの親を”先祖が先”の順序でロック
 * リネーム元とリネーム先を探す
 * リネーム元の親がリネーム先と同じもしくは子孫の場合は-ENOTEMPTYで失敗
 * リネーム先の親がリネーム元と同じもしくは子孫の場合は-ELOOPで失敗
 * 交換の場合はリネーム元とリネーム先の両方をロック
 * リネーム先が存在すればそれをロック。リネーム元が非ディレクトリならそれをロック。もし、両方をロックする必要があればポインタの昇順でロック
 * メソッドを呼び出す
全ての ->i_rwsemは排他モードでロックされます。ここでも、リネーム元(交換の場合はリネーム先も)のロックを共有モードに弱めるかもしれません

上記のルールは全ての読み出し、変更、削除の対象となるディレクトリがロックされることを明らかに保証します。

もし、自身が自身の先祖となるディレクトリが存在しないなら、上記の手法はデッドロックを引き起こしません。
証明：

まず、いかなる瞬間でも半順序 A < B (AはBの先祖である)が存在するとします。

順序は変わり得ますが、次のことが真になります。

(1) もし、オブジェクトの削除かディレクトリをまたがないリネームがAのロックを持ってBのロックを取得しようとした場合、AはBのロックが取得できるまでBの親であり続けます。(証明：ディレクトリをまたがるリネームのみが親オブジェクトを変更するが、それは親オブジェクトのロックを取得する)

(2) もし、ディレクトリをまたぐリネームがファイルシステムのロックを持っていれば、この順序はすべてのロックが取得されるまで変化しません。（証明：他のディレクトリをまたぐリネームはファイルシステムのロックでブロックされ、全てのロックが取得されるまでは順序は変更されません）

(3) 非ディレクトリなオブジェクトのロックはディレクトリオブジェクトのロックの後にポインタの昇順で取得される。（証明：リネーム以外のすべての操作は高々一つの非ディレクトリオブジェクトのロックしか取得しない。リネームの場合はリネーム元とリネーム元がディレクトリでない時にポインタの昇順で取得される。）

ここで最低限なデッドロックの条件を考えます。各プロセスはなんらかのロックを取得しようとしていて、すでに少なくとも一つのロックを取得しているとします。
競合するロックの組み合わせを考えましょう。
まずファイルシステムのロックは競合しません、ファイルシステムのロックでブロックされているプロセスは他のロックを持っていないからです。
なので、すべてのプロセスは->i_rwsemでブロックされていることになります。

(3) により、非ディレクトリのロックを持っている任意のプロセスは他の非ディレクトリで大きなアドレスのオブジェクトを待っていることにになります。すると、最大のアドレスを非ディレクトリオブジェクトを持ったプロセスは実行を進めることができ、非ディレクトリのオブジェクトは競合の組み合わせの中に入りません。

そして、リンクの作成もデッドロックの一部にはなりえません。リンク元のオブジェクトではブロックされず、それはロックを持ってないことを意味します。

競合するオブジェクトはディレクトリをまたぐリネームもしくは競合するオブジェクトを子に持ったもののどちらかになります。確かに、ディレクトリをまたぐリネーム以外の操作で取得されたロックを考えると、その操作をブロックしているロックは(1)により子オブジェクトに属するものになります。

つまり、操作の一つはディレクトリをまたぐリネームということになります。
そうでないなら競合するオブジェクトが無限にあり、すべてが競合している子を持っているということになりますが、どのオブジェクトも自身の子孫でないという前提があります。さらに、ディレクトリをまたぐリネームは同時に一つしかありません（上記を参照）。

ブロックしている操作がディレクトリをまたぐリネームだとします。子孫の一つがディレクトリをまたぐリネームによってロックされています（そうでないなら、また無限の競合しているオブジェクトを想定しないといけません）。しかし、それはディレクトリをまたぐリネームが順序に違反したロックを取得しているということになります。(2)によりファイルシステムのロックを取得しているならロックの順序が変わることはありえません。
しかし、ディレクトリをまたぐリネームにおけるロックのルールは先祖をロックする前に子孫をロックすることを保証しています。
矛盾、つまりデッドロックは不可能です。Q.E.D.

これらの操作はループを作らないことを保証します。確かに、ループを作りうる唯一の操作はディレクトリをまたぐリネームです。
rename()によって追加される(親、子)のペアは(新しい親、リネーム元)のみなので、ループはそれらのオブジェクトを含み、他のオブジェクトはrename()の前から存在しないといけません。つまり、ループを作ってしまうrename()がファイルシステムのロックを取得して呼ばれる時点で新しい親がリネーム元と同じかその子孫でないといけません。しかし、新しい親がリネーム元と同じがその子孫であった場合、ファイルシステムのロックを取得した時に-ELOOPで失敗します。

このロックのルールは任意のDAGに対して動作しますが、ディレクトリがあるディレクトリの子孫であるかチェックする機能の存在に依存しています。今の実装はディレクトリのグラフがツリーであることを前提にしています。
この前提は全ての操作において保持されます（ディレクトリをまたぐリネームはサイクルを作らずツリーを保ち、ディレクトリに対するlink()は失敗します）。

ここでの”ディレクトリ” == “子を持つ任意のオブジェクト”です、なので、もしハイブリッドなオブジェクトを導入しようとする場合、link(2)がそれらに対して使えないようにするか、is_subdir()がそんな野獣の存在するところでも動くように修正する必要があります。