linux死锁检测工具lockdep

在Linux系统里,假设有两处代码(比如不同线程的两个函数F1和F2)都要获取两个锁(分别为L1和L2),如果F1持有L1后再去获取L2,而此时恰好由F2持有L2且它也正在尝试获取L1,那么此时就是处于死锁的状态,这是一个最简单的死锁例子,也即所谓的AB-BA死锁。

死锁导致的最终结果无需多说,关于如何避免死锁在教科书上也有提到,最简单直观的做法就是按顺序上锁,以破坏死锁的环形等待条件。但对于拥有成千上万个锁的整个系统来说,完全定义它们之间的顺序是非常困难的,所以一种更可行的办法就是尽量提前发现这其中潜在的死锁风险,而不是等到最后真正出现死锁时给用户带来切实的困惑。

已有很多工具用于发现可能的死锁风险,而本文介绍的调试/检测模块lockdep,即是属于这一类工具的一种。调试模块lockdep由Ingo Molnar自2006年引入内核,经过实践验证,其对提前发现死锁起到了巨大的效果。

lockdep是linux内核调试的一个选项,在编译内核时(make menuconfig)时可以自由选择。

Lockdep锁类

1. lockdep操作的基本单元并非单个的锁实例,而是锁类(lock-class)

比如,struct inode结构体中的自旋锁i_lock字段就代表了这一类锁,而具体每个inode节点的锁只是该类锁中的一个实例。对所有这些实例,lockdep会把它们当作一个整体做处理,即把判断粒度放大,否则对可能有成千上万个的实例进行逐一判断,那处理难度可想而知,而且也没有必要。当然,在具体的处理中,可能会记录某些特性情况下的实例的部分相关信息,以便提供事后问题排查。

2. lockdep跟踪每个锁类的自身状态,也跟踪各个锁类之间的依赖关系

通过一系列的验证规则,以确保锁类状态和锁类之间的依赖总是正确的。另外,锁类一旦在初次使用时被注册,那么后续就会一直存在,所有它的具体实例都会关联到它。

3.锁类有4n + 1种不同的历史状态

其中的4是指:
– ‘ever held in STATE context’ –> 该锁曾在STATE上下文被持有过
– ‘ever head as readlock in STATE context’ –> 该锁曾在STATE上下文被以读锁形式持有过
– ‘ever head with STATE enabled’ –> 该锁曾在启用STATE的情况下被持有过
– ‘ever head as readlock with STATE enabled’ –> 该锁曾在启用STATE的情况下被以读锁形式持有过
其中的n也就是STATE状态的个数,目前有三个,可以根据需要添加:
– hardirq –> 硬中断
– softirq –> 软中断
– reclaim_fs –> fs回收(回收fs的相关资源,比如内存时,情况比较特殊,所以被单独出来作为一个STATE)
其中的1是:
– ‘ever used’ [ == !unused ] –> 不属于上面提到的任何特殊情况,仅仅只是表示该锁曾经被使用过

没有一个“曾经没有使用过”的状态,因为如果没有使用,那么就不会注册到lockdep里来。

4. 一旦违反了相关的验证规则,那么在调试模块lockdep给出的错误里就会显示出对应的状态位信息

看一个具体示例:

注意大括号内的符号,一共有6个字符,分别对应STATE和STATE-read这六种(因为目前每个STATE有3种不同含义)情况,各个字符代表的含义分别如下:

5. 单锁状态规则(Single-lock state rules)

1)一个软中断不安全(softirq-unsafe)的锁类同样也是硬中断不安全(hardirq-unsafe)的。
2)对于任何一个锁类,它不可能同时是hardirq-safe和hardirq-unsafe,也不可能同时是softirq-safe和softirq-unsafe,即这两对对应状态是互斥的。
上面这两条就是lockdep判断单锁是否会发生死锁的检测规则。

备注:
关于四个名称的概念如下(参考4)

(1) ever held in hard interrupt context (hardirq-safe);
(2) ever held in soft interrupt context (softirg-safe);
(3) ever held in hard interrupt with interrupts enabled (hardirq-unsafe);
(4) ever held with soft interrupts and hard interrupts enabled (softirq-unsafe);
(5) ever used (!unused).

hardirq-safe或hardirq-unsafe,单看它们中一个的英文描述,这还不太好理解,我们需要对比着看。可以看到,hardirq-unsafe是“with interrupts enabled”,那么与此相对,hardirq-safe应该就是“with interrupts disabled”,因此,个人目前对hardirq-safe的理解(不一定正确)是:在加锁、持锁,再到解锁的整个过程中,硬中断都处于禁止状态,即该锁不会被硬中断打断,比如:

这个锁priv->tx_ba_stream_tbl_lock就属于hardirq-safe锁类的一个实例;
softirq-safe和softirq-unsafe与此类似,即:softirq-safe锁类的实例不会被软中断和硬中断打断。

6. 多锁依赖规则(Multi-lock dependency rules)

1)同一个锁类不能被获取两次,因为这会导致递归死锁。
2)不能以不同的顺序获取两个锁类,即如此这样:

是不行的。因为这会非常容易的导致本文最先提到的AB-BA死锁。当然,下面这样的情况也不行:

即在中间插入了其它正常顺序的锁也能被lockdep检测出来。
3,同一个锁实例在任何两个锁类之间不能出现这样的情况:

这意味着,如果同一个锁实例,在某些地方是hardirq-safe(即采用spin_lock_irqsave(…)),而在某些地方又是hardirq-unsafe(即采用spin_lock(…)),那么就存在死锁的风险。这应该容易理解,比如在进程上下文中持有锁A,并且锁A是hardirq-unsafe,如果此时触发硬中断,而硬中断处理函数又要去获取锁A,那么就导致了死锁。
在锁类状态发生变化时,进行如下几个规则检测,判断是否存在潜在死锁。比较简单,就是判断hardirq-safe和hardirq-unsafe以及softirq-safe和softirq-unsafe是否发生了碰撞,直接引用英文,如下:

– 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.

7. 例外情况:嵌套数据依赖导致嵌套加锁

在Linux内核里有一些极少数情况会获取同一个锁类的多个实例,这一般发生在多个具有层次结构的同一种类型对象之内。在这些情况里,根据层次结构,多个对象之间有一种自然的固定顺序,因此内核也将按照这个固定顺序对各个对象进行加锁操作。
导致嵌套加锁的最一般例子是磁盘(whole disk)和分区(partition),它们拥有相同的类型block-dev,但是分区属于磁盘的一部分,因此加锁顺序应该总是先加磁盘锁,再加分区锁,否则就是错误的。如何让lockdep知晓这些加锁规则,因此有了新的加锁原语。对于上面的例子,对应的会有:

如此lockdep就知道,这是在对分区进行加锁,因此会将它作为一个单独的(子)类对待,而不是报错提示重复加锁。

8. 性能

通过前面的介绍,可以看到规则检测的时间复杂度为O(N^2),因此即便只有几百个锁类,那在每一次加锁或启用中断事件时,进行的检测操作也会需要数万次,而这种检测还是运行时检测(runtime checking),性能损耗十分的大,这基本无法接受。
要解决这个问题,一般方法也就是以空间换时间,lockdep就是这么做的。即对于任意给定的“加锁场景”(locking scenario),都只会检测一次。具体怎么做呢?通过维护一个持锁栈并结合64bit的哈希值来进行,每一个锁链(lock chain,也就是不同深浅的持锁栈)对应唯一的哈希值。对锁链进行规则检测时,会先在哈希表内查找哈希值,即如果某个锁链第一次出现时,会因为查找不到哈希值而进行规则检测,如果违反规则,那么走出错路径,否则计算对应的哈希值并存放到哈希表内。如果这个锁链不是第一次出现,那么就会在哈希表内查找到对应的哈希值,也就是这个锁链曾经被检测过,没有违反规则,所以无需再做检测,从而提高运行时检测性能。

原文地址:Linux程序猿

发表评论

电子邮件地址不会被公开。 必填项已用*标注