首页 > *nix技术, 内核技术, 跟踪调试 > 死锁检测模块lockdep简介

死锁检测模块lockdep简介

2013年4月10日 发表评论 阅读评论 10,045 次浏览

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

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

已有很多工具用于发现可能的死锁风险,而本文介绍的调试/检测模块lockdep,即是属于这一类工具的一种。调试模块lockdep从2006年(https://lwn.net/Articles/185666/)引入内核,经过实践验证,其对提前发现死锁起到了巨大的效果(http://lwn.net/Articles/321670/)。

官方文档(完全参考2)有介绍调试模块lockdep的设计原理,这里按照我自己的理解描述一下。
一,lockdep操作的基本单元并非单个的锁实例,而是锁类(lock-class)。比如,struct inode结构体中的自旋锁i_lock字段就代表了这一类锁,而具体每个inode节点的锁只是该类锁中的一个实例。对所有这些实例,lockdep会把它们当作一个整体做处理,即把判断粒度放大,否则对可能有成千上万个的实例进行逐一判断,那处理难度可想而知,而且也没有必要。当然,在具体的处理中,可能会记录某些特性情况下的实例的部分相关信息,以便提供事后问题排查(没看具体源码,属个人猜测,:))。

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

三,锁类有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回收(没看lockdep的源代码,应该是在回收fs的相关资源,比如内存时,情况比较特殊,所以被单独出来作为一个STATE)
其中的1是:
– ‘ever used’ [ == !unused ] –> 不属于上面提到的任何特殊情况,仅仅只是表示该锁曾经被使用过

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

四,一旦违反了相关的验证规则,那么在调试模块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个字符,分别对应STATE和STATE-read这六种(因为目前每个STATE有3种不同含义)情况,各个字符代表的含义分别如下:

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

五,单锁状态规则(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的理解(不一定正确)是:在加锁、持锁,再到解锁的整个过程中,硬中断都处于禁止状态,即该锁不会被硬中断打断,比如:

	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-safe和softirq-unsafe与此类似,即:softirq-safe锁类的实例不会被软中断和硬中断打断。

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

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

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

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

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

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

这意味着,如果同一个锁实例,在某些地方是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.

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

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

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

九,应用层lockdep
2013年2月6号,lwn上发表了一篇文章(参考3),用于描述应用层lockdep补丁(https://lwn.net/Articles/536366/),它的最大好处是与内核lockdep共用一套代码,这意味着应用层lockdep功能代码的维护和升级都由Linux内核人员一起做了。虽然,目前该补丁尚未合入mainline主线,不过仍然值得大力期待。

完全参考:
1,The kernel lock validator
https://lwn.net/Articles/185666/

2,lockdep-design.txt
https://git.kernel.org/cgit/linux/kernel/git/stable/linux-stable.git/tree/Documentation/lockdep-design.txt?id=v2.6.30.8

参考:
1,如何避免死锁
http://www.cnblogs.com/cxd4321/archive/2012/05/28/2521542.html

2,Interrupts, threads, and lockdep
http://lwn.net/Articles/321663/

3,应用层的lockdep
https://lwn.net/Articles/536363/

4,United States Patent 8145903:Method and system for a kernel lock validator
http://www.freepatentsonline.com/8145903.html

转载请保留地址:http://www.lenky.info/archives/2013/04/2253http://lenky.info/?p=2253


备注:如无特殊说明,文章内容均出自Lenky个人的真实理解而并非存心妄自揣测来故意愚人耳目。由于个人水平有限,虽力求内容正确无误,但仍然难免出错,请勿见怪,如果可以则请留言告之,并欢迎来讨论。另外值得说明的是,Lenky的部分文章以及部分内容参考借鉴了网络上各位网友的热心分享,特别是一些带有完全参考的文章,其后附带的链接内容也许更直接、更丰富,而我只是做了一下归纳&转述,在此也一并表示感谢。关于本站的所有技术文章,欢迎转载,但请遵从CC创作共享协议,而一些私人性质较强的心情随笔,建议不要转载。

法律:根据最新颁布的《信息网络传播权保护条例》,如果您认为本文章的任何内容侵犯了您的权利,请以Email或书面等方式告知,本站将及时删除相关内容或链接。

  1. 本文目前尚无任何评论.
  1. 本文目前尚无任何 trackbacks 和 pingbacks.