在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.lock){-.-…}, at: [] mutex_lock+0×21/0×24
but task is already holding lock:
(&sio_locks.lock){-.-…}, at: [] mutex_lock+0×21/0×24
注意大括号内的符号，一共有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的理解（不一定正确）是：在加锁、持锁，再到解锁的整个过程中，硬中断都处于禁止状态，即该锁不会被硬中断打断，比如：
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-safe和softirq-unsafe与此类似，即：softirq-safe锁类的实例不会被软中断和硬中断打断。
六，多锁依赖规则（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，并且锁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知晓这些加锁规则，因此有了新的加锁原语。对于上面的例子，对应的会有：
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就知道，这是在对分区进行加锁，因此会将它作为一个单独的（子）类对待，而不是报错提示重复加锁。
八，性能
通过前面的介绍，可以看到规则检测的时间复杂度为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
|
