Linux Kernel 2.6 Documentation:
/usr/src/linux/Documentation/filesystems/dentry-locking.txt
filesystems/dentry-locking.txt
Linux 2.6 の dcache ロックの解説
[プレインテキスト版]
- 原著作者: unknown
- 翻訳者: Seiji Kaneko < skaneko at mbn dot or dot jp >
- バージョン: 2.6.29
- 翻訳日時: 2009/07/09
=========================================================
これは、
Linux-2.6.29/Documentation/filesystems/dentry-locking.txt の和訳
です。
翻訳団体： JF プロジェクト < http://www.linux.or.jp/JF/ >
更新日 ： 2009/07/09
翻訳者 ： Seiji Kaneko < skaneko at mbn dot or dot jp >
=========================================================
#RCU-based dcache locking model
RCU ベースの dcache ロックモデル
==============================
#On many workloads, the most common operation on dcache is to look up a
#dentry, given a parent dentry and the name of the child. Typically,
#for every open(), stat() etc., the dentry corresponding to the
#pathname will be looked up by walking the tree starting with the first
#component of the pathname and using that dentry along with the next
#component to look up the next level and so on. Since it is a frequent
#operation for workloads like multiuser environments and web servers,
#it is important to optimize this path.
多くの負荷では、dcache に対する最もよく使われる操作とは、親 dentry と子の名
前を与えて dentry を探索する処理です。典型的には全ての open()、stat() など
で、パス名に一致する dentry をツリーを辿って探す、つまりパス名の最初の要素
を使ってツリー探索を開始し、得られた dentry を使ってパス名の二番目の要素で
次のレベルを探索し、などの繰り返しが続きます。これはマルチユーザ環境や、ウ
ェブサーバなどの負荷で頻繁に発生する操作ですから、このパスを最適化すること
が重要になります。
#Prior to 2.5.10, dcache_lock was acquired in d_lookup and thus in
#every component during path look-up. Since 2.5.10 onwards, fast-walk
#algorithm changed this by holding the dcache_lock at the beginning and
#walking as many cached path component dentries as possible. This
#significantly decreases the number of acquisition of
#dcache_lock. However it also increases the lock hold time
#significantly and affects performance in large SMP machines. Since
#2.5.62 kernel, dcache has been using a new locking model that uses RCU
#to make dcache look-up lock-free.
2.5.10 以前では、dcache_lock が d_lookup で取得されており、その結果パス探
索の間は全てのコンポーネントで取得されていました。2.5.10 以降では、高速探
索アルゴリズムによりこの状況が変わって、探索の最初に dcache_lock を取得し、
キャッシュされたパスコンポーネント dentry を可能な限り辿ろうとするよう変わ
りました。これにより、dcache_lock の取得回数は大きく下がりましたが、ロック
保持時間が大幅に伸び、大規模 SMP マシンの性能に影響がでました。2.5.62 カー
ネルからは、dcache 探索をロックなしで行なうため、dcache には RCU を用いた
新ロックモデルが使われています。
#The current dcache locking model is not very different from the
#existing dcache locking model. Prior to 2.5.62 kernel, dcache_lock
#protected the hash chain, d_child, d_alias, d_lru lists as well as
#d_inode and several other things like mount look-up. RCU-based changes
#affect only the way the hash chain is protected. For everything else
#the dcache_lock must be taken for both traversing as well as
#updating. The hash chain updates too take the dcache_lock. The
#significant change is the way d_lookup traverses the hash chain, it
#doesn't acquire the dcache_lock for this and rely on RCU to ensure
#that the dentry has not been *freed*.
現在の dcache ロックモデルは、従来の dcache ロックモデルと大きく異なるもので
はありません。2.5.62 以前のカーネルでは、dcache_lock が hash_chain, d_child,
d_alias, d_lru リストと d_inode およびマウント時の探索などを守っていました。
RCU ベースでの変更は、hash_chain が保護されているやり方のみに影響します。それ
以外のすべてで、dcache_lock を探索時と更新時の両方で取得する必要があります。
hash chain の更新にも dcache_lock の取得が必要です。大きな変更は、d_lookup
が hash chain を探索する方法に加えられています。変更後では、探索操作に
dcache_lock が取得されず、dentry が＊解放＊されていないことは RCU 側の保証
に委ねられます。
#Dcache locking details
Dcache ロック処理の詳細
======================
#For many multi-user workloads, open() and stat() on files are very
#frequently occurring operations. Both involve walking of path names to
#find the dentry corresponding to the concerned file. In 2.4 kernel,
#dcache_lock was held during look-up of each path component. Contention
#and cache-line bouncing of this global lock caused significant
#scalability problems. With the introduction of RCU in Linux kernel,
#this was worked around by making the look-up of path components during
#path walking lock-free.
多くのマルチユーザ負荷環境では、ファイルに対する open() と stat() は非常によ
く発生する操作です。いずれの処理も、パス名をたどって対象とするファイルに対応し
た dentry を探す処理を含みます。2.4 カーネルでは、dcache_lock がパスコンポー
ネントを検索している間、ずっと保持されていました。このグローバルロックでの、キ
ャッシュロック競合とキャッシュラインバウンス (訳注: ロック領域のキャッシュラ
インのプロセッサ間での転送の多発。特にスピン系) は、高多重システムでの性能の
伸びに重大な問題となっていました。Linux カーネルへの RCU 機構の導入により、パ
ス名をたどる際のパスコンポーネントの探索がロック不要となり、この問題は回避でき
るようになりました。
#Safe lock-free look-up of dcache hash table
安全でロック不要の dcache ハッシュテーブル探索
===========================================
#Dcache is a complex data structure with the hash table entries also
#linked together in other lists. In 2.4 kernel, dcache_lock protected
#all the lists. We applied RCU only on hash chain walking. The rest of
#the lists are still protected by dcache_lock. Some of the important
#changes are :
Dcache は、ハッシュテーブルエントリを持ち、他のリストからも共用リンクされる
複雑なデータ構造体です。2.4 カーネルでは、dcache_lock がリスト群全体を保護
していました。(現在のカーネルでは) 私たちはハッシュチェインを辿る操作にのみ
RCU を使うようにしました。リストの他の部分は依然として dcache_lock で保護
されています。ここで重要となる変更を幾つか以下で説明します。
#1. The deletion from hash chain is done using hlist_del_rcu() macro
# which doesn't initialize next pointer of the deleted dentry and
# this allows us to walk safely lock-free while a deletion is
# happening.
1. ハッシュチェインからの削除は hlist_del_rcu() マクロを使って行われ、このマ
クロは削除された dentry の次のエントリを指すポインタを初期化しません。この
ことにより、削除が行われた場合でもロックなしで安全にチェインを辿ることがで
きます。
#2. Insertion of a dentry into the hash table is done using
# hlist_add_head_rcu() which take care of ordering the writes - the
# writes to the dentry must be visible before the dentry is
# inserted. This works in conjunction with hlist_for_each_rcu() while
# walking the hash chain. The only requirement is that all
# initialization to the dentry must be done before
# hlist_add_head_rcu() since we don't have dcache_lock protection
# while traversing the hash chain. This isn't different from the
# existing code.
2. dentry をハッシュテーブルに挿入するには、hlist_add_head_rcu() を使ってく
ださい。これを使えば書き込み順序などの面倒をすべてみてもらえます。dentry
への書き込みは、dentry 挿入前に可視になっていなければいけません。これを守
れば、hlist_add_head_rcu() と組み合わせることで、ハッシュチェインを辿る
処理中も処理可能となります。要求事項は、hlist_add_head_rcu() の実行前に
dentry の全ての初期化を済ませておかなければならないことだけです。これは
ハッシュチェインを辿る処理の際に dcache_lock を持っていないためです。こ
の点は既存のコードの処理と異なっているわけではありません。
#3. The dentry looked up without holding dcache_lock by cannot be
# returned for walking if it is unhashed. It then may have a NULL
# d_inode or other bogosity since RCU doesn't protect the other
# fields in the dentry. We therefore use a flag DCACHE_UNHASHED to
# indicate unhashed dentries and use this in conjunction with a
# per-dentry lock (d_lock). Once looked up without the dcache_lock,
# we acquire the per-dentry lock (d_lock) and check if the dentry is
# unhashed. If so, the look-up is failed. If not, the reference count
# of the dentry is increased and the dentry is returned.
3. dcache_lock なしに探索した dentry は、ハッシュされていない場合には、辿る
ための dentry として戻り値に返すことは不可能です。戻した場合、NULL d_inode
や、そのほかの無効な状態に遭遇するかもしれません。これは RCU では dentry
の他のフィールドは保護していないためです。このため、DCACHE_UNHASHED フラグ
を使ってハッシュされていない dentry を示し、これを dentry 毎のロック
(d_lock) と組み合わせて使用します。まず dcache_lock なしに探索をおこなっ
た場合、dentry 毎にあるロック (d_lock) を取得して、dentry がハッシュされ
ているかどうかを確認します。ハッシュされていない場合、探索は失敗です。ハッ
シュされていた場合には、dentry の参照カウントに 1 を加え、dentry を戻り値
とします。
#4. Once a dentry is looked up, it must be ensured during the path walk
# for that component it doesn't go away. In pre-2.5.10 code, this was
# done holding a reference to the dentry. dcache_rcu does the same.
# In some sense, dcache_rcu path walking looks like the pre-2.5.10
# version.
4. 一旦 dentry の探索を行ったあとは、その各要素のパスを辿る間、内容が変化しな
いことを保証しなければいけません。2.5.10 以前のコードでは、これは dentry
への参照を維持することで保証されていました。dcache_rcu はそれと同じ処理を
行います。ある意味、dcache_rcu を用いたパスを辿る処理は、2.5.10 以前のも
のと同じように見えます。
#5. All dentry hash chain updates must take the dcache_lock as well as
# the per-dentry lock in that order. dput() does this to ensure that
# a dentry that has just been looked up in another CPU doesn't get
# deleted before dget() can be done on it.
5. dentry ハッシュチェインの更新処理では、dcache_lock と、dentry 毎のロック
をこの順で取得しなければいけません。dput() はこれを行い、他の CPU による探
索で発見された dentry が、dget() で処理ができるまで削除されないように保証
します。
#6. There are several ways to do reference counting of RCU protected
# objects. One such example is in ipv4 route cache where deferred
# freeing (using call_rcu()) is done as soon as the reference count
# goes to zero. This cannot be done in the case of dentries because
# tearing down of dentries require blocking (dentry_iput()) which
# isn't supported from RCU callbacks. Instead, tearing down of
# dentries happen synchronously in dput(), but actual freeing happens
# later when RCU grace period is over. This allows safe lock-free
# walking of the hash chains, but a matched dentry may have been
# partially torn down. The checking of DCACHE_UNHASHED flag with
# d_lock held detects such dentries and prevents them from being
# returned from look-up.
6. RCU で保護されたオブジェクトに対する参照カウントには、幾つかの実現手段があ
ります。その一つの例として、ipv4 ラウトキャッシュでは、参照カウントが 0
になるとすぐに遅延解放 (call_rcu() を使って) が実行されます。dentry の場
合、このような処理ができません。これは、dentry を外すには、RCU コールバッ
クではサポートされていないブロッキング処理 (dentry_iput()) が必要となる
ためです。それに代わって dentry では、dentry を外す処理は dput() で同期
的に実施し、実際の領域の解放は RCU の猶予期間が終わってから行うようになっ
ています。これにより、ハッシュチェインを安全にロックなしで辿ることが可能に
なっていますが、探索で見つけた dentry は部分的に外された状態になっている
かもしれません。d_lock を持った状態で DCACHE_UNHASHED フラグの検査を行う
ことでそのような dentry を検知でき、検索結果として返してしまうのを防ぐこ
とができます。
#Maintaining POSIX rename semantics
POSIX リネームセマンティックの維持
================================
#Since look-up of dentries is lock-free, it can race against a
#concurrent rename operation. For example, during rename of file A to
#B, look-up of either A or B must succeed. So, if look-up of B happens
#after A has been removed from the hash chain but not added to the new
#hash chain, it may fail. Also, a comparison while the name is being
#written concurrently by a rename may result in false positive matches
#violating rename semantics. Issues related to race with rename are
#handled as described below :
dentry の探索はロックを持たないで行うため、並行して実行されるリネーム処理と
競合を起こす可能性があります。例えば、ファイル A を B への名称変更中は、A
という名称の探索と B という名称の探索のどちらかは成功する必要があります。従
って、A がハッシュチェインから削除されてはいるが、新ハッシュチェインに追加
されてはいないタイミングで B への探索が起こった場合、うまくいかないるかもしれ
ません。また、リネームによる名称変更の処理の実行中に並行して比較が行われた
場合、名称変更のセマンティックに反した誤った探索成功が発生するかもしれませ
ん。競合に関する問題は、以下のようにして処理されます。
#1. Look-up can be done in two ways - d_lookup() which is safe from
# simultaneous renames and __d_lookup() which is not. If
# __d_lookup() fails, it must be followed up by a d_lookup() to
# correctly determine whether a dentry is in the hash table or
# not. d_lookup() protects look-ups using a sequence lock
# (rename_lock).
1. 探索は二通りの方法で行うことができます - d_lookup() は同時のリネーム処理に
対して安全で、__d_lookup() は安全ではありません。__d_lookup() が失敗した
場合、引き続いて d_lookup() を実行してハッシュテーブル内に求める dentry が
存在するかどうかを正しく判定しなければいけません。d_lookup() はシーケンス
ロック (rename_lock) を使って探索を保護します。
#2. The name associated with a dentry (d_name) may be changed if a
# rename is allowed to happen simultaneously. To avoid memcmp() in
# __d_lookup() go out of bounds due to a rename and false positive
# comparison, the name comparison is done while holding the
# per-dentry lock. This prevents concurrent renames during this
# operation.
2. dentry に関連付けられた名前 (d_name) は、リネーム処理が並行して動作するこ
とを許されていた場合、変更されるかもしれません。__d_lookup() での memcmp()
処理が名称変更に伴って配列範囲外になるのを避けるため、そして誤った比較結果
とならないようにするために、名前の比較は dentry 毎のロックを持った状態で行
われます。これにより、比較処理中のリネーム処理の並行動作を防ぎます。
#3. Hash table walking during look-up may move to a different bucket as
# the current dentry is moved to a different bucket due to rename.
# But we use hlists in dcache hash table and they are
# null-terminated. So, even if a dentry moves to a different bucket,
# hash chain walk will terminate. [with a list_head list, it may not
# since termination is when the list_head in the original bucket is
# reached]. Since we redo the d_parent check and compare name while
# holding d_lock, lock-free look-up will not race against d_move().
3. 検索時のハッシュテーブルを辿る処理は、リネーム処理により現在の dentry が
異なったバケットに移動するのに伴い、異なったバケットに移動する可能性があ
ります。ただし、この場合は dcache ハッシュテーブルの hlist を用いており、
それは NULL 終端されています。従って、dentry が異なったバケットに移動し
た場合でも、ハッシュチェインを辿る処理が止まらなくなることはありません
(一方 list_head 型のリストでは、元のバケットのリストヘッドに到達した場
合に完了となるため、移動の結果完了しなくなるかもしれません)。ここでは
d_lock を持って d_parent チェックと名前比較を再実行しているため、ロック
を持たない検索処理と d_move() との競合は起こらないはずです。
#4. There can be a theoretical race when a dentry keeps coming back to
# original bucket due to double moves. Due to this look-up may
# consider that it has never moved and can end up in a infinite loop.
# But this is not any worse that theoretical livelocks we already
# have in the kernel.
4. 二回の移動に伴い、dentry が元のバケットに戻された場合、理論上は競合が発生
する可能性があります。このため、探索処理で全く移動していないと判断される可
能性や、無限ループになる可能性の考慮などが必要になってきます。ただし、この
状態は現状のカーネルに存在する、やはり理論上のライブロックの可能性より悪い
ものとは言えません。
#Important guidelines for filesystem developers related to dcache_rcu
dcache_rcu に関するファイルシステム開発者向けの重要なガイドライン
=============================================================
#1. Existing dcache interfaces (pre-2.5.62) exported to filesystem
# don't change. Only dcache internal implementation changes. However
# filesystems *must not* delete from the dentry hash chains directly
# using the list macros like allowed earlier. They must use dcache
# APIs like d_drop() or __d_drop() depending on the situation.
1. ファイルシステムに公開された、既存の dcache インターフェース (2.5.62 以
前) は変更されていません。dcache の内部実装のみが変更されています。ただし、
ファイルシステムは以前許されていたような、リストマクロを使った dentry ハ
ッシュチェインからのエントリの削除を絶対に行ってはいけません。この場合は
状況に応じて d_drop() や __d_drop() などの dcache API を使わなければい
けません。
#2. d_flags is now protected by a per-dentry lock (d_lock). All access
# to d_flags must be protected by it.
2. d_flags は dentry 毎にあるロック (d_lock) で保護されるようになりました。
d_flags へのアクセスはこのロックを取得し、保護した状態で行わなければいけ
ません。
#3. For a hashed dentry, checking of d_count needs to be protected by
# d_lock.
3. ハッシュされた dentry では、d_count のチェックは、d_lock を取得し、保護
した状態で行わなければいけません。
#Papers and other documentation on dcache locking
dcache ロック方法に関する論文と関連文書
=====================================
1. Scaling dcache with RCU (http://linuxjournal.com/article.php?sid=7124).
2. http://lse.sourceforge.net/locking/dcache/dcache.html
Linux カーネル 2.6 付属文書一覧へ戻る