运行时锁正确性验证器¶
由 Ingo Molnar <mingo@redhat.com> 发起
由 Arjan van de Ven <arjan@linux.intel.com> 补充
锁类¶
验证器操作的基本对象是锁的“类”。
锁类是逻辑上关于锁定规则相同的锁的集合，即使锁可能具有多个（可能数万个）实例。 例如，inode 结构中的锁是一个类，而每个 inode 都有该锁类的自己的实例。
验证器跟踪锁类的“使用状态”，并跟踪不同锁类之间的依赖关系。锁的使用指示锁在其 IRQ 上下文中的使用方式，而锁依赖可以理解为锁顺序，其中 L1 -> L2 表示任务正在尝试在持有 L1 的同时获取 L2。从 lockdep 的角度来看，这两个锁（L1 和 L2）不一定相关；该依赖关系只是意味着该顺序曾经发生过。 验证器会不断努力证明锁的使用和依赖是正确的，否则验证器会在不正确时发出 splat。
锁类的行为由其所有实例共同构建：在启动后首次使用锁类的实例时，该类会被注册，然后所有（后续）实例将被映射到该类，因此它们的使用和依赖将有助于该类的使用和依赖。当锁实例消失时，锁类不会消失，但是如果锁类（静态或动态）的内存空间被回收，则可以删除锁类，例如当模块被卸载或工作队列被销毁时会发生这种情况。
状态¶
验证器跟踪锁类的使用历史，并将使用情况分为 (4 种使用情况 * n 个状态 + 1) 类
其中 4 种使用情况可以是
“在 STATE 上下文中曾经持有”
“在 STATE 上下文中曾经作为读锁持有”
“在启用 STATE 的情况下曾经持有”
“在启用 STATE 的情况下曾经作为读锁持有”
其中 n 个 STATE 在 kernel/locking/lockdep_states.h 中编码，截至目前，它们包括
hardirq
softirq
其中最后一个类别是
“曾经使用” [ == !未使用 ]
当锁定规则被违反时，这些使用位会以大括号的形式显示在锁定错误消息中，总共有 2 * n 个 STATE 位。一个人为的例子
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
对于给定的锁，从左到右的位位置分别指示该锁和读锁（如果存在）的使用情况，对于上面列出的每个 n 个 STATE，每个位位置显示的字符指示
“.”
在禁用 irq 且不在 irq 上下文中时获取
“-”
在 irq 上下文中获取
“+”
在启用 irq 的情况下获取
“？”
在启用 irq 的情况下在 irq 上下文中获取。
这些位用一个例子来说明
(&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24
||||
||| \-> softirq disabled and not in softirq context
|| \--> acquired in softirq context
| \---> hardirq disabled and not in hardirq context
\----> acquired in hardirq context
对于给定的 STATE，无论锁是否在该 STATE 上下文中被获取过以及该 STATE 是否被启用，都会产生以下表格中所示的四种可能情况。位字符能够指示截至报告时间锁的准确情况。
启用 irq
禁用 irq
曾经在 irq 中
“？”
“-”
从未在 irq 中
“+”
“.”
字符“-”表示 irq 已禁用，因为否则将显示字符“?”。对于“+”也可以应用类似的推导。
未使用的锁（例如，互斥锁）不能成为错误的原因。
单锁状态规则：¶
一个锁是 irq 安全的，意味着它曾经在 irq 上下文中使用过，而一个锁是 irq 不安全的，意味着它曾经在启用 irq 的情况下获取过。
一个软中断不安全的锁类也会自动是硬中断不安全的。以下状态必须是互斥的：基于其使用情况，对于任何锁类，只允许设置其中一个状态。
<hardirq-safe> or <hardirq-unsafe>
<softirq-safe> or <softirq-unsafe>
这是因为如果一个锁可以在 irq 上下文中使用（irq 安全），那么它不能在启用 irq 的情况下获取（irq 不安全）。否则，可能会发生死锁。例如，在获取此锁后但在释放之前，如果上下文被中断，则此锁将被尝试获取两次，从而导致死锁，称为锁递归死锁。
验证器会检测并报告违反这些单锁状态规则的锁使用情况。
多锁依赖规则：¶
同一个锁类不能被获取两次，因为这可能会导致锁递归死锁。
此外，不能以相反的顺序获取两个锁
<L1> -> <L2>
<L2> -> <L1>
因为这可能会导致死锁（称为锁反转死锁），因为获取这两个锁的尝试形成一个循环，这可能导致两个上下文永久地相互等待。验证器将发现这种任意复杂度的依赖循环，即在获取锁操作之间可以有任何其他的锁定序列；验证器仍然会发现这些锁是否可以以循环方式获取。
此外，任何两个锁类之间都不允许出现以下基于使用情况的锁依赖关系
<hardirq-safe> -> <hardirq-unsafe>
<softirq-safe> -> <softirq-unsafe>
第一个规则来自这样一个事实，即一个硬中断安全的锁可能被硬中断上下文获取，从而中断一个硬中断不安全的锁，因此可能导致锁反转死锁。同样，软中断安全的锁可能被软中断上下文获取，从而中断一个软中断不安全的锁。
上述规则适用于内核中发生的任何锁定序列：在获取新锁时，验证器会检查新锁和任何已持有锁之间是否存在任何规则冲突。
当锁类更改其状态时，会强制执行上述依赖规则的以下方面
如果发现新的硬中断安全锁，我们会检查它过去是否获取过任何硬中断不安全的锁。
如果发现新的软中断安全锁，我们会检查它过去是否获取过任何软中断不安全的锁。
如果发现新的硬中断不安全锁，我们会检查过去是否有任何硬中断安全锁获取过它。
如果发现新的软中断不安全锁，我们会检查过去是否有任何软中断安全锁获取过它。
（同样，我们也会基于中断上下文可能中断_任何_ irq 不安全或硬中断不安全锁的前提进行这些检查，这可能会导致锁反转死锁，即使该锁场景尚未在实践中触发。）
例外：导致嵌套锁定的嵌套数据依赖¶
在某些情况下，Linux 内核会获取同一锁类的多个实例。这种情况通常发生在同一类型的对象中存在某种层次结构时。在这些情况下，两个对象之间存在固有的“自然”顺序（由层次结构的属性定义），内核在每个对象上以这种固定的顺序获取锁。
导致“嵌套锁定”的对象层次结构的示例是“整个磁盘”块设备对象和“分区”块设备对象；分区是“整个设备的一部分”，只要始终将整个磁盘锁作为比分区锁更高的锁，则锁顺序完全正确。验证器不会自动检测到这种自然顺序，因为顺序背后的锁定规则不是静态的。
为了教验证器关于这种正确的使用模型，添加了各种锁定原语的新版本，允许您指定“嵌套级别”。块设备互斥锁的一个示例调用如下所示
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() 原语时，请务必小心并彻底检查层次结构是否正确映射；否则可能会得到误报或漏报。
注解¶
可以使用两种构造来注释和检查必须在何处以及是否持有某些锁：lockdep_assert_held*(&lock) 和 lockdep_*pin_lock(&lock)。
顾名思义，lockdep_assert_held* 系列宏断言在特定时间持有特定锁（否则会生成 WARN()）。此注解在内核中广泛使用，例如 kernel/sched/core.c
void update_rq_clock(struct rq *rq)
{
s64 delta;
lockdep_assert_held(&rq->lock);
[...]
}
其中需要持有 rq->lock 才能安全地更新 rq 的时钟。
另一类宏是 lockdep_*pin_lock()，它目前仅用于 rq->lock。尽管它们的应用有限，但如果感兴趣的锁被“意外”解锁，这些注解会生成 WARN()。这对于调试带有回调的代码特别有用，在这些代码中，上层假设锁仍然被持有，而下层认为可以放弃并重新获取锁（“无意中”引入了竞争）。lockdep_pin_lock() 返回一个“struct pin_cookie”，然后由 lockdep_unpin_lock() 使用，以检查是否有人篡改了锁，例如 kernel/sched/sched.h
static inline void rq_pin_lock(struct rq *rq, struct rq_flags *rf)
{
rf->cookie = lockdep_pin_lock(&rq->lock);
[...]
}
static inline void rq_unpin_lock(struct rq *rq, struct rq_flags *rf)
{
[...]
lockdep_unpin_lock(&rq->lock, rf->cookie);
}
尽管关于锁定要求的注释可能提供有用的信息，但注解执行的运行时检查在调试锁定问题时非常宝贵，并且在检查代码时具有相同的详细程度。如有疑问，请始终首选注解！
100% 正确性的证明：¶
验证器实现了完美的、数学上的“闭包”（锁定正确性的证明），即对于内核生命周期中至少发生过一次的每个简单的、独立的单任务锁定序列，验证器以 100% 的确定性证明，这些锁定序列的任何组合和时序都不会导致任何类型的锁相关的死锁。[1]
也就是说，复杂的、多 CPU 和多任务锁定场景不必在实践中发生就可以证明死锁：只有简单的“组件”锁定链必须至少发生一次（在任何时间、任何任务/上下文中），验证器才能证明其正确性。（例如，通常需要 3 个以上的 CPU 以及不太可能的任务、中断上下文和时序组合才能发生的复杂死锁，也可以在普通的、轻负载的单 CPU 系统上检测到！）
这从根本上降低了内核与锁定相关的质量保证的复杂性：在质量保证期间需要做的是尽可能多地触发内核中的“简单”单任务锁定依赖关系，至少一次，以证明锁定的正确性 - 而不必触发 CPU 之间锁交互的每种可能的组合，以及每种可能的硬中断和软中断嵌套场景（这在实践中是不可能做到的）。
性能：¶
上述规则需要大量的运行时检查。如果我们对每个获取的锁和每个启用中断事件都这样做，系统实际上会变得慢得无法使用。检查的复杂性是 O(N^2)，所以即使只有几百个锁类，我们每次事件也需要进行数万次检查。
这个问题通过只检查任何给定的“锁定场景”（彼此获取的锁的唯一序列）一次来解决。维护一个简单的持有锁的堆栈，并计算出一个轻量级的 64 位哈希值，该哈希值对于每个锁链都是唯一的。哈希值在首次验证链时，会被放入一个哈希表中，该哈希表可以以无锁的方式进行检查。如果锁定链稍后再次出现，哈希表会告诉我们不必再次验证该链。
故障排除：¶
验证器跟踪最大 MAX_LOCKDEP_KEYS 个锁类。超出此数量将触发以下锁依赖警告
(DEBUG_LOCKS_WARN_ON(id >= MAX_LOCKDEP_KEYS))
默认情况下，MAX_LOCKDEP_KEYS 当前设置为 8191，典型的桌面系统具有少于 1,000 个锁类，因此此警告通常是由锁类泄漏或未能正确初始化锁引起的。以下说明了这两个问题
在运行验证器时重复加载和卸载模块会导致锁类泄漏。这里的问题是，每次加载模块都会为该模块的锁创建一组新的锁类，但模块卸载不会删除旧的锁类（请参阅下面关于重用锁类的讨论）。因此，如果反复加载和卸载该模块，锁类的数量最终将达到最大值。
使用诸如数组之类的结构，这些结构具有大量未显式初始化的锁。例如，一个具有 8192 个桶的哈希表，其中每个桶都有自己的自旋锁 spinlock_t，将消耗 8192 个锁类 - 除非 - 每个自旋锁都在运行时显式初始化，例如，使用运行时 spin_lock_init() 而不是编译时初始化器，例如 __SPIN_LOCK_UNLOCKED()。未能正确初始化每个桶的自旋锁将保证锁类溢出。相比之下，对每个锁调用 spin_lock_init() 的循环会将所有 8192 个锁放入单个锁类中。
这个故事的寓意是，您应该始终显式地初始化您的锁。
有人可能会争辩说应该修改验证器以允许重用锁类。但是，如果您想提出这个论点，请首先查看代码并仔细考虑所需的更改，同时考虑到要删除的锁类很可能已链接到锁依赖关系图中。事实证明，这比说起来要难得多。
当然，如果您确实用完了锁类，那么接下来要做的是找到有问题的锁类。首先，以下命令会给出当前正在使用的锁类数量以及最大数量
grep "lock-classes" /proc/lockdep_stats
此命令在适度的系统上会产生以下输出
lock-classes: 748 [max: 8191]
如果分配的数量（上面的 748）随着时间的推移不断增加，那么很可能存在泄漏。以下命令可用于识别泄漏的锁类
grep "BD" /proc/lockdep
运行该命令并保存输出，然后将其与稍后运行此命令的输出进行比较，以识别泄漏者。相同的输出还可以帮助您找到运行时省略锁初始化的情况。
递归读锁：¶
本文档的其余部分试图证明某种类型的循环等同于死锁的可能性。
有三种类型的锁：写锁（即排他锁，如 spin_lock() 或 write_lock()）、非递归读锁（即共享锁，如 down_read()）和递归读锁（递归共享锁，如 rcu_read_lock()）。在本文档的其余部分中，我们使用以下这些锁的符号
W 或 E：表示写锁（排他锁）。r：表示非递归读锁。R：表示递归读锁。S：表示所有读锁（非递归 + 递归），因为它们都是共享锁。N：表示写锁和非递归读锁，因为它们都不是递归的。
显然，N 是 “r 或 W”，而 S 是 “r 或 R”。
递归读锁，顾名思义，是允许在同一锁实例的另一个读锁的临界区内获取的锁，换句话说，允许一个锁实例的嵌套读端临界区。
而非递归读锁如果试图在同一锁实例的另一个读锁的临界区内获取，则会导致自身死锁。
递归读锁和非递归读锁的区别在于：递归读锁仅会被写锁持有者阻塞，而非递归读锁可能会被写锁等待者阻塞。考虑以下示例
TASK A: TASK B:
read_lock(X);
write_lock(X);
read_lock_2(X);
任务 A 首先通过 read_lock() 在 X 上获取读锁（无论是递归的还是非递归的）。当任务 B 尝试在 X 上获取写锁时，它将被阻塞并成为 X 上写锁的等待者。现在，如果 read_lock_2() 是递归读锁，则任务 A 将取得进展，因为写锁等待者不会阻塞递归读锁，并且不会发生死锁。但是，如果 read_lock_2() 是非递归读锁，它将被写锁等待者 B 阻塞，并导致自身死锁。
同一锁实例的读/写锁上的阻塞条件：¶
简单来说有四种阻塞条件
写锁阻塞其他写锁。
读锁阻塞写锁。
写锁阻塞递归读锁和非递归读锁。
并且读锁（递归或非递归）不会阻塞其他递归读锁，但可能会阻塞非递归读锁（因为可能存在共存的写锁等待者）
阻塞条件矩阵，Y 表示行阻塞列，N 表示否则。
W
r
R
W
Y
Y
Y
r
Y
Y
N
R
Y
Y
N
（W：写锁，r：非递归读锁，R：递归读锁）
递归获取。与非递归读锁不同，递归读锁仅被当前写锁持有者阻塞，而不是写锁等待者，例如
TASK A: TASK B:
read_lock(X);
write_lock(X);
read_lock(X);
对于递归读锁来说，这不是死锁，因为当任务 B 等待锁 X 时，第二个 read_lock() 不需要等待，因为它是一个递归读锁。但是，如果 read_lock() 是非递归读锁，则上述情况是死锁，因为即使 TASK B 中的 write_lock() 无法获取锁，它也可以阻塞 TASK A 中的第二个 read_lock()。
请注意，锁可以是写锁（排他锁）、非递归读锁（非递归共享锁）或递归读锁（递归共享锁），具体取决于用于获取锁的锁操作（更具体地说，是 lock_acquire() 的“read”参数的值）。换句话说，单个锁实例根据获取函数具有三种类型的获取：排他获取、非递归读获取和递归读获取。
简而言之，我们将写锁和非递归读锁称为“非递归”锁，并将递归读锁称为“递归”锁。
递归锁不会互相阻塞，而非递归锁会互相阻塞（即使是两个非递归读锁也是如此）。非递归锁可以阻塞相应的递归锁，反之亦然。
涉及递归锁的死锁情况如下
TASK A: TASK B:
read_lock(X);
read_lock(Y);
write_lock(Y);
write_lock(X);
任务 A 正在等待任务 B 解锁 Y，而任务 B 正在等待任务 A 解锁 X。
依赖类型和强依赖路径：¶
锁依赖关系记录了一对锁的获取顺序，并且由于锁有 3 种类型，因此理论上有 9 种类型的锁依赖关系，但我们可以证明 4 种类型的锁依赖关系足以进行死锁检测。
对于每个锁依赖关系
L1 -> L2
, 这意味着 lockdep 在运行时在同一上下文中看到 L1 在 L2 之前被持有。在死锁检测中，我们关心的是是否可以在持有 L1 的情况下被 L2 阻塞，即是否有一个锁 L3，L1 阻塞 L3，并且 L2 被 L3 阻塞。因此，我们只关心 1）L1 阻塞什么和 2）什么阻塞 L2。因此，我们可以将 L1 的递归读锁和非递归读锁合并（因为它们阻塞相同的类型），并且可以将 L2 的写锁和非递归读锁合并（因为它们被相同的类型阻塞）。
通过上述简化组合，锁依赖关系图中存在 4 种类型的依赖边
- -(ER)->
互斥写者到递归读者依赖，“X -(ER)-> Y” 表示 X -> Y，且 X 是写者，Y 是递归读者。
- -(EN)->
互斥写者到非递归锁依赖，“X -(EN)-> Y” 表示 X -> Y，且 X 是写者，Y 是写者或非递归读者。
- -(SR)->
共享读者到递归读者依赖，“X -(SR)-> Y” 表示 X -> Y，且 X 是读者（递归或非递归），Y 是递归读者。
- -(SN)->
共享读者到非递归锁依赖，“X -(SN)-> Y” 表示 X -> Y，且 X 是读者（递归或非递归），Y 是写者或非递归读者。
请注意，给定两个锁，它们之间可能存在多个依赖关系，例如
TASK A:
read_lock(X);
write_lock(Y);
...
TASK B:
write_lock(X);
write_lock(Y);
，我们在依赖图中同时有 X -(SN)-> Y 和 X -(EN)-> Y。
我们使用 -(xN)-> 来表示 -(EN)-> 或 -(SN)-> 的边，类似的，使用 -(Ex)->，-(xR)-> 和 -(Sx)->。
“路径” 是图中一系列连续的依赖边。我们定义“强”路径，表示路径中每个依赖关系的强依赖性，为不包含两个连续边（依赖关系）为 -(xR)-> 和 -(Sx)-> 的路径。换句话说，“强”路径是从一个锁通过锁依赖关系走到另一个锁的路径，如果 X -> Y -> Z 在路径中（其中 X、Y、Z 是锁），且从 X 到 Y 的路径是通过 -(SR)-> 或 -(ER)-> 依赖关系，那么从 Y 到 Z 的路径必须不是通过 -(SN)-> 或 -(SR)-> 依赖关系。
我们将在下一节中看到为什么该路径被称为“强”。
递归读死锁检测：¶
现在我们证明两件事
引理 1
如果存在一个闭合的强路径（即一个强环），那么就存在导致死锁的锁定序列组合。也就是说，一个强环足以进行死锁检测。
引理 2
如果没有闭合的强路径（即强环），那么就不存在可能导致死锁的锁定序列组合。也就是说，强环是死锁检测所必需的。
有了这两个引理，我们可以很容易地说，闭合的强路径对于死锁来说既是充分的又是必要的，因此闭合的强路径等价于死锁的可能性。由于闭合的强路径代表可能导致死锁的依赖链，因此我们称其为“强”，考虑到存在不会导致死锁的依赖环。
充分性证明（引理 1）
假设我们有一个强环
L1 -> L2 ... -> Ln -> L1
，这意味着我们有依赖关系
L1 -> L2
L2 -> L3
...
Ln-1 -> Ln
Ln -> L1
现在我们可以构造一个导致死锁的锁定序列组合
首先，让一个 CPU/任务在 L1 -> L2 中获取 L1，然后让另一个在 L2 -> L3 中获取 L2，以此类推。 之后，Lx -> Lx+1 中的所有 Lx 都由不同的 CPU/任务持有。
然后，因为我们有 L1 -> L2，所以 L1 的持有者将在 L1 -> L2 中获取 L2，但是由于 L2 已经被另一个 CPU/任务持有，加上 L1 -> L2 和 L2 -> L3 不是 -(xR)-> 和 -(Sx)-> （强的定义），这意味着 L1 -> L2 中的 L2 是一个非递归锁（被任何人阻塞）或者 L2 -> L3 中的 L2 是写者（阻塞任何人），因此 L1 的持有者无法获取 L2，它必须等待 L2 的持有者释放。
此外，对于 L2 的持有者，我们可以得出类似的结论：它必须等待 L3 的持有者释放，依此类推。现在我们可以证明 Lx 的持有者必须等待 Lx+1 的持有者释放，并注意 Ln+1 是 L1，因此我们有一个循环等待场景，没有人可以取得进展，因此发生死锁。
必要性证明（引理 2）
引理 2 等价于：如果存在死锁场景，那么依赖图中一定存在一个强环。
根据维基百科[1]，如果存在死锁，那么一定存在一个循环等待场景，这意味着有 N 个 CPU/任务，其中 CPU/任务 P1 正在等待 P2 持有的锁，P2 正在等待 P3 持有的锁，...，Pn 正在等待 P1 持有的锁。我们将 Px 正在等待的锁命名为 Lx，因此由于 P1 正在等待 L1 并持有 Ln，因此我们将在依赖图中看到 Ln -> L1。类似地，我们在依赖图中看到 L1 -> L2，L2 -> L3，...，Ln-1 -> Ln，这意味着我们有一个环
Ln -> L1 -> L2 -> ... -> Ln
，现在让我们证明这个环是强的
对于锁 Lx，Px 提供依赖关系 Lx-1 -> Lx，Px+1 提供依赖关系 Lx -> Lx+1，并且由于 Px 正在等待 Px+1 释放 Lx，因此 Px+1 上的 Lx 不可能是读者，并且 Px 上的 Lx 是递归读者，因为读者（无论是否递归）都不会阻止递归读者，因此 Lx-1 -> Lx 和 Lx -> Lx+1 不可能是 -(xR)-> -(Sx)-> 对，这对环中的任何锁都成立，因此该环是强的。
参考文献：¶
[1]: https://en.wikipedia.org/wiki/Deadlock [2]: Shibu, K. (2009). Intro To Embedded Systems (1st ed.). Tata McGraw-Hill