搜公众号
推荐 原创 视频 Java开发 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库
Lambda在线 > Linux程序猿 > linux死锁检测工具lockdep

linux死锁检测工具lockdep

Linux程序猿 2019-01-18
举报

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


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


已有很多工具用于发现可能的死锁风险,而本文介绍的调试/检测模块lockdep,即是属于这一类工具的一种。调试模块lockdepIngo 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给出的错误里就会显示出对应的状态位信息。
看一个具体示例:


modprobe/2287 is trying to acquire lock:
(&sio_locks[i].lock){-.-…}, at: [] mutex_lock+0x21/0x24

but task is already holding lock:
(&sio_locks[i].lock){-.-…}, at: [] mutex_lock+0x21/0x24

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

‘.’ acquired while irqs disabled and not in irq context
‘-‘ acquired in irq context
‘+’ acquired with irqs enabled
‘?’ acquired in irq context with irqs enabled.

5. 单锁状态规则(Single-lock state rules
1一个软中断不安全(softirq-unsafe)的锁类同样也是硬中断不安全(hardirq-unsafe)的。
2对于任何一个锁类,它不可能同时是hardirq-safehardirq-unsafe,也不可能同时是softirq-safesoftirq-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-safehardirq-unsafe,单看它们中一个的英文描述,这还不太好理解,我们需要对比着看。可以看到,hardirq-unsafe“with interrupts enabled”,那么与此相对,hardirq-safe应该就是“with interrupts disabled”,因此,个人目前对hardirq-safe的理解(不一定正确)是:在加锁、持锁,再到解锁的整个过程中,硬中断都处于禁止状态,即该锁不会被硬中断打断,比如:

1

2

3

4

5

spin_lock_irqsave(&priv->tx_ba_stream_tbl_lock, flags);

list_for_each_entry_safe(del_tbl_ptr, tmp_node,

           &priv->tx_ba_stream_tbl_ptr, list)

  mwifiex_11n_delete_tx_ba_stream_tbl_entry(priv, del_tbl_ptr);

spin_unlock_irqrestore(&priv->tx_ba_stream_tbl_lock, flags);

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

6. 多锁依赖规则(Multi-lock dependency rules
1同一个锁类不能被获取两次,因为这会导致递归死锁。
2不能以不同的顺序获取两个锁类,即如此这样:

1

2

<L1> -> <L2>

<L2> -> <L1>

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

1

2

<L1> -> <L3> -> <L4> -> <L2>

<L2> -> <L3> -> <L4> -> <L1>

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

1

2

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

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

这意味着,如果同一个锁实例,在某些地方是hardirq-safe(即采用spin_lock_irqsave(…)),而在某些地方又是hardirq-unsafe(即采用spin_lock(…)),那么就存在死锁的风险。这应该容易理解,比如在进程上下文中持有锁A,并且锁Ahardirq-unsafe,如果此时触发硬中断,而硬中断处理函数又要去获取锁A,那么就导致了死锁。
在锁类状态发生变化时,进行如下几个规则检测,判断是否存在潜在死锁。比较简单,就是判断hardirq-safehardirq-unsafe以及softirq-safesoftirq-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知晓这些加锁规则,因此有了新的加锁原语。对于上面的例子,对应的会有:

1

2

3

4

5

6

7

8

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);

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

8. 性能

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



版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《linux死锁检测工具lockdep》的版权归原作者「Linux程序猿」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注Linux程序猿微信公众号

Linux程序猿微信公众号:doifelse

Linux程序猿

手机扫描上方二维码即可关注Linux程序猿微信公众号

Linux程序猿最新文章

精品公众号随机推荐

举报