英语

• 意大利语

运行时锁正确性验证器

由 Ingo Molnar <mingo@redhat.com> 启动

由 Arjan van de Ven <arjan@linux.intel.com> 添加

锁类 (Lock-class)

验证器操作的基本对象是锁的“类”。

锁类是锁的一个组，它们在逻辑上是相同的，符合锁定规则，即使锁可能有多个（可能数万个）实例。 例如，inode 结构中的锁是一个类，而每个 inode 都有该锁类的自己的实例化。

验证器跟踪锁类的“使用状态”，并跟踪不同锁类之间的依赖关系。 锁使用情况表明锁是如何用于其 IRQ 上下文的，而锁依赖性可以理解为锁顺序，其中 L1 -> L2 表示任务尝试在持有 L1 时获取 L2。 从 lockdep 的角度来看，这两个锁（L1 和 L2）不一定相关； 这种依赖关系只是意味着该顺序曾经发生过。 验证器不断努力证明锁的使用和依赖关系是正确的，否则验证器会发出错误信息。

锁类的行为由其所有实例共同构建：当启动后使用锁类的第一个实例时，该类会被注册，然后所有（后续）实例将被映射到该类，因此它们的用法和依赖关系将有助于该类的用法和依赖关系。 锁类不会在锁实例消失时消失，但如果锁类（静态或动态）的内存空间被回收，则可以将其删除，例如，当模块被卸载或工作队列被销毁时。

状态 (State)

验证器跟踪锁类使用历史记录，并将使用情况分为 (4 种用法 * n 个状态 + 1) 个类别

其中 4 种用法可以是

• “在状态上下文中曾经被持有”

• “在状态上下文中曾经作为读锁被持有”

• “在启用状态的情况下曾经被持有”

• “在启用状态的情况下曾经作为读锁被持有”

其中 n 个状态在 kernel/locking/lockdep_states.h 中编码，截至目前包括

• 硬中断 (hardirq)

• 软中断 (softirq)

其中最后一个类别是

• “曾经被使用” [ == !unused ]

当锁定规则被违反时，这些使用位会显示在锁定错误消息中，位于花括号内，总共有 2 * n 个状态位。 一个虚构的例子

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 个状态的锁和读锁（如果存在）的使用情况，并且每个位位置上显示的字符指示

“.”	在禁用中断且不在中断上下文的情况下获取
“-”	在中断上下文中获取
“+”	在启用中断的情况下获取
“？”	在启用中断的情况下在中断上下文中获取。

这些位用一个例子来说明

(&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

对于给定的状态，无论锁是否曾经在该状态上下文中获取，以及该状态是否启用，都会产生如下表所示的四种可能情况。 位字符能够指示报告时锁的确切情况。

	启用中断	禁用中断
曾经在中断中	“？”	“-”
从未在中断中	“+”	“.”

字符“-”表示禁用了中断，因为否则会显示字符“？”。 类似的推论也适用于“+”。

未使用的锁（例如，互斥锁）不能成为错误的原因。

单锁状态规则：

一个锁是中断安全的，意味着它曾经在中断上下文中被使用过，而一个锁是中断不安全的，意味着它曾经在启用中断的情况下被获取过。

软中断不安全的锁类也自动是硬中断不安全的。 以下状态必须是互斥的：基于其用法，任何锁类只允许设置其中一个

<hardirq-safe> or <hardirq-unsafe>
<softirq-safe> or <softirq-unsafe>

这是因为如果一个锁可以在中断上下文中使用（中断安全），那么它不能在启用中断的情况下获取（中断不安全）。 否则，可能会发生死锁。 例如，在这种锁被获取但尚未释放的情况下，如果上下文被中断，则会尝试两次获取此锁，从而导致死锁，称为锁递归死锁。

验证器检测并报告违反这些单锁状态规则的锁使用情况。

多锁依赖规则：

同一个锁类不得被获取两次，因为这可能导致锁递归死锁。

此外，不能以相反的顺序获取两个锁

<L1> -> <L2>
<L2> -> <L1>

因为这可能导致死锁 - 称为锁反转死锁 - 因为尝试获取两个锁形成一个循环，这可能导致两个上下文永久地相互等待。 验证器将找到这种任意复杂度的依赖关系圈，即，在 acquire-lock 操作之间可以有任何其他的锁定序列； 验证器仍然会找到这些锁是否可以以循环的方式获取。

此外，以下基于用法的锁依赖关系在任何两个锁类之间都是不允许的

<hardirq-safe>   ->  <hardirq-unsafe>
<softirq-safe>   ->  <softirq-unsafe>

第一条规则来自以下事实：硬中断安全的锁可能被硬中断上下文获取，从而中断硬中断不安全的锁 - 因此可能导致锁反转死锁。 同样，软中断安全的锁可能被软中断上下文获取，从而中断软中断不安全的锁。

以上规则适用于内核中发生的任何锁定序列：当获取新锁时，验证器会检查新锁和任何持有的锁之间是否存在任何规则冲突。

当锁类改变其状态时，将执行以上依赖规则的以下方面

• 如果发现新的硬中断安全锁，我们会检查它是否在过去获取过任何硬中断不安全的锁。

• 如果发现新的软中断安全锁，我们会检查它是否在过去获取过任何软中断不安全的锁。

• 如果发现新的硬中断不安全锁，我们会检查是否任何硬中断安全的锁在过去获取过它。

• 如果发现新的软中断不安全锁，我们会检查是否任何软中断安全的锁在过去获取过它。

（同样，我们进行这些检查的原因是，中断上下文可能会中断_任何_中断不安全或硬中断不安全的锁，这可能会导致锁反转死锁 - 即使该锁场景尚未在实践中触发。）

例外情况：导致嵌套锁定的嵌套数据依赖关系

在某些情况下，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 ATM。 尽管它们的采用有限，但如果感兴趣的锁被“意外”解锁，这些注解会生成 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]

也就是说，复杂的 multi-CPU 和 multi-task 锁定场景不必在实践中发生才能证明死锁：只有简单的“组件”锁定链必须至少发生一次（任何时间，在任何任务/上下文中），验证器才能证明正确性。 （例如，通常需要 3 个以上的 CPU 和任务、中断上下文和时间安排的非常不可能的星座才能发生的复杂死锁也可以在普通的、负载较轻的单 CPU 系统上检测到！）

这从根本上降低了内核锁定相关 QA 的复杂性：QA 期间必须做的是在内核中尽可能多地触发“简单”的单任务锁定依赖关系，至少一次，以证明锁定正确性 - 而不是必须触发 CPU 之间锁定交互的每种可能组合，以及每种可能的硬中断和软中断嵌套场景（这在实践中是不可能做到的）。

[1]

假设验证器本身是 100% 正确的，并且系统的其他部分不会以任何方式破坏验证器的状态。 我们还假设所有 NMI/SMM 路径[即使是禁用硬中断的代码路径也可能被中断]都是正确的，并且不会干扰验证器。 我们还假设 64 位“链哈希”值对于系统中的每个锁链都是唯一的。 此外，锁递归不得高于 20。

性能：

以上规则需要大量的运行时检查。 如果我们对每次获取锁和每次启用中断事件都这样做，这将使系统实际上慢得无法使用。 检查的复杂性是 O(N^2)，因此即使只有几百个锁类，我们也不得不对每个事件进行数万次检查。

通过仅检查任何给定的“锁定场景”（彼此获取的锁的唯一序列）一次来解决此问题。 维护一个简单的持有锁堆栈，并计算一个轻量级的 64 位哈希值，该哈希值对于每个锁链都是唯一的。 首次验证链时，哈希值随后被放入哈希表中，可以在无锁方式下检查该哈希表。 如果锁定链稍后再次发生，哈希表会告诉我们不必再次验证该链。

问题排查：

验证器最多跟踪 MAX_LOCKDEP_KEYS 个锁类。 超过此数量将触发以下 lockdep 警告

(DEBUG_LOCKS_WARN_ON(id >= MAX_LOCKDEP_KEYS))

默认情况下，MAX_LOCKDEP_KEYS 当前设置为 8191，并且典型的桌面系统具有少于 1,000 个锁类，因此此警告通常由锁类泄漏或无法正确初始化锁导致。 以下说明了这两个问题

1. 运行验证器时重复加载和卸载模块将导致锁类泄漏。 这里的问题是，每次加载模块都会为该模块的锁创建一组新的锁类，但卸载模块不会删除旧类（请参阅下面关于重用锁类的讨论，了解原因）。 因此，如果重复加载和卸载该模块，锁类的数量最终将达到最大值。

2. 使用诸如数组之类的结构，这些结构具有大量未显式初始化的锁。 例如，具有 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 阻塞，并导致自身死锁。

同一锁实例的读者/写者的阻塞条件：

只有四个阻塞条件

1. 写者阻塞其他写者。

2. 读者阻塞写者。

3. 写者阻塞递归读者和非递归读者。

4. 并且读者（无论是否递归）不阻塞其他递归读者，但可能会阻塞非递归读者（由于可能共存的写者等待者）

阻塞条件矩阵，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 的 read_unlock() Y，而任务 B 正在等待任务 A 的 read_unlock() X。

依赖类型和强依赖路径：

锁依赖关系记录了一对锁的获取顺序，并且因为锁有 3 种类型，理论上锁依赖关系有 9 种类型，但我们可以证明 4 种类型的锁依赖关系足以进行死锁检测。

对于每个锁依赖关系

L1 -> L2

，这意味着 lockdep 在运行时看到在同一个上下文中 L1 被持有，之后 L2 被持有。 在死锁检测中，我们关心是否会在持有 L1 的情况下阻塞 L2，IOW，是否存在一个锁 L3，L1 阻塞 L3 并且 L2 被 L3 阻塞。 因此，我们只关心 1) L1 阻塞什么，2) 什么阻塞 L2。 因此，我们可以合并 L1 的递归读者和非递归读者（因为它们阻塞相同的类型），并且我们可以合并 L2 的写者和非递归读者（因为它们被相同的类型阻塞）。

通过以上组合进行简化，lockdep 图中有 4 种类型的依赖关系边

1. -(ER)->

   独占写者到递归读者的依赖关系，“X -(ER)-> Y”表示 X -> Y，并且 X 是写者，Y 是递归读者。

2. -(EN)->

   独占写者到非递归锁的依赖关系，“X -(EN)-> Y”表示 X -> Y，并且 X 是写者，Y 要么是写者，要么是非递归读者。

3. -(SR)->

   共享读者到递归读者的依赖关系，“X -(SR)-> Y”表示 X -> Y，并且 X 是读者（无论递归与否），Y 是递归读者。

4. -(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，然后让另一个 CPU/任务在 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 等同于：如果存在死锁场景，则依赖关系图中必须存在强循环。

根据 Wikipedia[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，所以 Lx 在 Px+1 上不可能是读锁，而 Lx 在 Px 上是递归读锁，这是不可能的。因为读锁（无论是否递归）不会阻塞递归读锁，因此 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