以下は、Linux カーネル文書、Documentation/locking/lockdep-design.txt の kanda.motohiro@gmail.com による訳です。原文と同じ、GPL v2 で公開します。
実行時にロックが正しいことを検証する
=====================================
started by Ingo Molnar <mingo@redhat.com>
additions by Arjan van de Ven <arjan@linux.intel.com>
ロッククラス
----------
検証機が操作する基本オブジェクトは、ロックの「クラス」です。
ロックのクラスとは、ロック規則に関して論理的に同じロックのグループです。ロックが複数の（もしかすると１万以上の）インスタンスを持っていてもかまいません。例えば、inode 構造体にあるロックは一つのクラスです。inode のそれぞれは、そのロッククラスのインスタンスを持ちます。
検証機は、ロッククラスの「状態」を追跡します。さらに、異なるロッククラスの間の依存関係も追跡します。検証機は状態と依存関係が正しいことの証明を常に維持します。
ロックインスタンスとは違って、ロッククラス自身は決して消えません。ブート後にロッククラスが最初に使われた時にそれは登録され、以降そのロッククラスに、使用がアタッチされます。
状態
-----
検証機は、ロッククラスの使用履歴を、4n + 1 の個々のビットで追跡します。
- 'ever held in STATE context'
- 'ever held as readlock in STATE context'
- 'ever held with STATE enabled'
- 'ever held as readlock with STATE enabled'
STATE は、以下のいずれかです。(kernel/locking/lockdep_states.h)
- hardirq
- softirq
- reclaim_fs
- 'ever used' [ == !unused ]
ロック規則が破られた時は、ロックエラーメッセージ中に、これら状態ビットがカーリーブラケット中に表示されます。故意にエラーをおこした時の例です。
modprobe/2287 is trying to acquire lock:
(&sio_locks[i].lock){-.-...}, at: [<c02867fd>] mutex_lock+0x21/0x24
but task is already holding lock:
(&sio_locks[i].lock){-.-...}, at: [<c02867fd>] mutex_lock+0x21/0x24
ビット位置は、前記の状態一覧の、STATE, STATE-read を示します。表示される文字は、
'.' acquired while irqs disabled and not in irq context
'-' acquired in irq context
'+' acquired with irqs enabled
'?' acquired in irq context with irqs enabled.
使われていない mutex は、エラーの原因となることはありません。
単一のロックの状態規則
------------------------
softirq-unsafe なロッククラスは、自動的に hardirq-unsafe でもあります。以下の状態は排他的で、どのロッククラスに対しても、その一つだけが有効です。
<hardirq-safe> and <hardirq-unsafe>
<softirq-safe> and <softirq-unsafe>
検証機はこれらの単一のロックの状態規則を破るロックの使用を検出し、報告します。
複数ロックの依存規則
----------------------------
同じロッククラスを２回取ることはできません。再帰的自己デッドロックになるからです。
さらに、２つのロックを異なる順序で取ってはいけません。
<L1> -> <L2>
<L2> -> <L1>
これは、ロック逆転デッドロックになるからです。（検証機は、任意の複雑さの中からそのような依存関係を見つけることができます。つまり、ロック確保操作の間に、どのようなロックシーケンスがあってもかまいません。検証機はその場合でもロック間の全ての依存関係を追跡できます。）
さらに、２つのロッククラスの間で、以下のロック依存性の使用は許されません。
<hardirq-safe> -> <hardirq-unsafe>
<softirq-safe> -> <softirq-unsafe>
最初の規則は、hardirq-safe ロックは、hardirq-unsafe ロックに割り込んで、hardirq コンテキストで取ることができるため、ロック逆転のデッドロックになる可能性があるという事実に基づきます。同様に、softirq-safe ロックは、softirq-unsafe ロックに割り込んで、softirq コンテキストで取ることができます。
上記の規則は、カーネルで起きる全てのロックシーケンスに強制されます。新しいロックを取る時は、検証機は新しいロックと保持されているロックのいずれかに規則を破るものがないかをチェックします。
ロッククラスがその状態を変えるとき、前記依存関係の以下の側面が強制されます。
- if a new hardirq-safe lock is discovered, we check whether it
took any hardirq-unsafe lock in the past.
- if a new softirq-safe lock is discovered, we check whether it took
any softirq-unsafe lock in the past.
- if a new hardirq-unsafe lock is discovered, we check whether any
hardirq-safe lock took it in the past.
- if a new softirq-unsafe lock is discovered, we check whether any
softirq-safe lock took it in the past.
（繰り返しますが、このチェックも、割り込みコンテキストは「任意の」irq-unsafe あるいは hardirq-unsafe ロックを割り込むことができることを基準に行われます。それは、ロック逆転のデッドロックになることがあります。そのロックシナリオが実際にはまだ、起きていなくてもそれは可能です。）
例外：ネストしたデータ依存がネストしたロックになる時
-------------------------------------------------------------
Linux カーネルが、同じロッククラスの一つ以上のインスタンスを取る、まれな場合があります。そういう場合は、典型的には、同じタイプのオブジェクト間にある種の階層がある時に起きます。こういう時は、２つのオブジェクト間には固有の「自然な」順序があります（階層の性質で決まります）。カーネルは、それぞれのオブジェクトに決められたこの固定の順序でロックを確保します。
「ロックのネスト」が生じるそのようなオブジェクト階層の例は、「ディスク全体」フロックデバイスオブジェクトと、「パーティション」オブジェクトです。パーティションは、デバイス全体の「部分」であり、パーティションロックよりもディスク全体のロックをより高いロックとして必ず先に取れば、ロック順序は完全に正しいです。検証機はこの自然な順序を自動的には検出しません。順序のもととなるロック規則は静的ではないからです。
検証機にこの正しい使用モデルを教えるために、新しいバージョンのいくつかのロックプリミティブが追加されました。あなたはそれを使って「ネストレベル」を指定できます。ブロックデバイスの mutex についての呼び出し例はこのようになります。
enum bdev_bd_mutex_lock_class
{
BD_MUTEX_NORMAL,
BD_MUTEX_WHOLE,
BD_MUTEX_PARTITION
};
mutex_lock_nested(&bdev->bd_contains->bd_mutex, BD_MUTEX_PARTITION);
この場合、ロックは、パーティションであることがわかっている bdev オブジェクトに対して行われます。
検証機は、このように、ネストしたやり方で取られたロックを、検証の目的のためには、個別の（サブ）クラスとして扱います。
注意：コードを、_nested() プリミティブを使うように変える時は、注意して、階層が正しくマップされているか、本当に完全にチェックして下さい。そうでないと、擬陽性や擬陰性が起きます。
１００％正しいことの証明
--------------------------
検証機は、完璧な、数学的な「閉包」（ロックが正しいことの証明）を達成します。それはカーネルの存在期間のうちで少なくても一度起きた、全ての単純なスタンドアロンの単一タスクのロックシーケンスに対して、検証機が、これらのロックシーケンスの組み合わせとタイミングをどのように変えても、ロック関連のデッドロックのクラスが一切起きないことを１００％の確度で証明できるという意味です。 [*]
つまり、複雑なマルチCPUとマルチタスクのロックシナリオは、実際に、デッドロック検知をするために起きる必要がないということです。単純な、「コンポーネント」ロックチェーンだけが、少なくても一度起きる必要があるだけです（それはいつでもよく、どのタスク／コンテキストでもよいです）。それだけで、検証機は正しさを証明できます。（例えば、通常なら、３つ以上のCPUと、普通ならありえないタスク、割り込みコンテキスト、そしてタイミングの組み合わせがないと起きないような複雑なデッドロックであっても、単純な、ほとんど負荷のない単一CPUシステムにおいても検出が可能です！）
これは、カーネルのロックに関わる QA の複雑さを根本的に減らします。QA で行う必要のあることは、できるだけ多くの、カーネル内の「単純な」シングルタスクのロック依存関係を作り出すことです。少なくても一度それをすれば、ロックの正しさを証明できます。かつてはそれは、CPU 間の全てのロック相互作用の組み合わせに加えて、全ての hardirq と softirq のネストの組み合わせのシナリオを発生させる必要がありました（そんなことは実際にはできないのです）。
[*] 検証機そのものは１００％正しくて、検証機の状態をシステムの他の部分がこわすことはけっしてないことを前提とします。また、全ての NMI/SMM パス（それは、hardirq を禁止したコードパスでも割り込みます）は正しくて、検証機に干渉しないことも前提とします。また、システムの全てのロックチェーンで６４ビットの「チェーンハッシュ」値は一意であることを前提とします。また、ロック再帰は２０以下でなくてはいけません。
性能
------------
前記の規則は、「かなりな」量のランタイムチェックを必要とします。それを、すべてのロック確保と割り込み有効化イベントで行っていたら、システムは実用的には使えないほど遅くなるでしょう。チェックの複雑さは、O(N^2) です。なので、たった数百のロッククラスでも、イベントごとに数万回のチェックが必要です。
この問題は、全ての与えられた「ロックシナリオ」（ロックが取られる一意のシーケンス）を、一度だけ、チェックすることで解決されます。保持されているロックの簡単なスタックが維持され、軽量の６４ビットハッシュ値が計算されます。ハッシュはすべてのロックチェーンで一意です。チェーンが最初に検証される時に、ハッシュ値がハッシュテーブルに置かれます。そのハッシュテーブルは、ロックフリーな方法でチェックできます。ロックチェーンがその後また現れたら、ハッシュテーブルを見れば、このチェーンはもう検証しないでもいいことがわかります。
トラブルシュート
----------------
検証機は、最大で MAX_LOCKDEP_KEYS 個のロッククラスを追跡します。この数を超えると以下の lockdep 警告が出ます。
(DEBUG_LOCKS_WARN_ON(id >= MAX_LOCKDEP_KEYS))
デフォルトで、MAX_LOCKDEP_KEYS は現在 8191 です。典型的なデスクトップシステムは、1,000 以下のロッククラスしか持ちません。なので、この警告は通常は、ロッククラスのリークか、あるいはロックを正しく初期化してないことから起きます。以下にこの２つの問題を述べます。
1. Repeated module loading and unloading while running the validator
will result in lock-class leakage. The issue here is that each
load of the module will create a new set of lock classes for
that module's locks, but module unloading does not remove old
classes (see below discussion of reuse of lock classes for why).
Therefore, if that module is loaded and unloaded repeatedly,
the number of lock classes will eventually reach the maximum.
2. Using structures such as arrays that have large numbers of
locks that are not explicitly initialized. For example,
a hash table with 8192 buckets where each bucket has its own
spinlock_t will consume 8192 lock classes -unless- each spinlock
is explicitly initialized at runtime, for example, using the
run-time spin_lock_init() as opposed to compile-time initializers
such as __SPIN_LOCK_UNLOCKED(). Failure to properly initialize
the per-bucket spinlocks would guarantee lock-class overflow.
In contrast, a loop that called spin_lock_init() on each lock
would place all 8192 locks into a single lock class.
The moral of this story is that you should always explicitly
initialize your locks.
One might argue that the validator should be modified to allow
lock classes to be reused. However, if you are tempted to make this
argument, first review the code and think through the changes that would
be required, keeping in mind that the lock classes to be removed are
likely to be linked into the lock-dependency graph. This turns out to
be harder to do than to say.
Of course, if you do run out of lock classes, the next thing to do is
to find the offending lock classes. First, the following command gives
you the number of lock classes currently in use along with the maximum:
grep "lock-classes" /proc/lockdep_stats
This command produces the following output on a modest system:
lock-classes: 748 [max: 8191]
If the number allocated (748 above) increases continually over time,
then there is likely a leak. The following command can be used to
identify the leaking lock classes:
grep "BD" /proc/lockdep
Run the command and save the output, then compare against the output from
a later run of this command to identify the leakers. This same output
can also help you find situations where runtime lock initialization has
been omitted.
以上