English

• 意大利语

运行时锁正确性验证器

由 Ingo Molnar 发起 <mingo@redhat.com>

Arjan van de Ven 进行了补充 <arjan@linux.intel.com>

锁类

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

锁类是指在加锁规则上逻辑相同的锁组，即使这些锁可能有多个（可能是数万个）实例化对象。例如，inode struct is 中的锁属于一个类，而每个 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

其中最后 1 个类别是

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

当违反加锁规则时，这些使用位会出现在加锁错误消息中，位于大括号内，总共有 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 中锁和读锁（如果存在）的使用情况，每个位位置显示的字符表示

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

通过一个例子来说明这些位

(&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-safe（中断安全）的意味着它曾被用于中断上下文，而一个锁是 irq-unsafe（中断不安全）的意味着它曾在启用中断的情况下被获取。

一个 softirq-unsafe（软中断不安全）的锁类自动也是 hardirq-unsafe（硬中断不安全）的。以下状态必须是互斥的：根据其用法，任何锁类只允许设置其中一个状态

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

这是因为如果一个锁可以在中断上下文中使用（irq-safe），那么它就绝不能在启用中断的情况下被获取（irq-unsafe）。否则，可能会发生死锁。例如，在这样一种场景下：在该锁被获取之后但在释放之前，如果上下文被中断，则该锁将被尝试再次获取，从而产生死锁，称为锁递归死锁（lock recursion deadlock）。

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

多锁依赖规则：

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

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

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

因为这可能导致死锁——称为锁反转死锁（lock inversion deadlock）——因为获取这两个锁的尝试形成了一个环，这可能导致两个上下文永久互相等待。验证器将发现具有任意复杂度的此类依赖环，也就是说，在加锁操作之间可以存在任何其他加锁序列；验证器仍然能够找出这些锁是否可以以循环的方式获取。

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

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

第一条规则源于这样一个事实：硬中断安全锁可能被硬中断上下文获取，从而中断硬中断不安全锁——并因此导致锁反转死锁。同样，软中断安全锁可能被软中断上下文获取，从而中断软中断不安全锁。

上述规则适用于内核中发生的任何加锁序列：在获取新锁时，验证器会检查新锁与任何已持有的锁之间是否存在规则违例。

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

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

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

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

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

（同样，我们进行这些检查的基础是：中断上下文可以中断_任何_ irq-unsafe 或 hardirq-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 的时钟需要持有 rq->lock。

另一系列宏是 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 系统上检测到！）

这从根本上降低了内核加锁相关 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 对 Y 执行 read_unlock()，而任务 B 正在等待任务 A 对 X 执行 read_unlock()。

依赖类型与强依赖路径：

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

对于每个锁依赖

L1 -> L2

，这意味着 lockdep 在运行时同一环境中看到 L1 在 L2 之前被持有。在死锁检测中，我们关心的是在持有 L1 的情况下是否会在 L2 上被阻塞，换句话说，是否存在一个加锁者 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 等价于：如果存在死锁场景，则依赖图中必然存在一个强环。

根据维基百科[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