Linux内核机制总结内核互斥技术之死锁检测工具lockdep(四十四)
文章目录
- 1 死锁检测工具lockdep
- 1.1 使用方法
- 1.2 技术原理
- 重要：本系列文章内容摘自
1 死锁检测工具lockdep
常见的死锁有以下4种情况：
（1）进程重复申请同一个锁，称为AA死锁。例如，重复申请同一个自旋锁；使用读写锁，第一次申请读锁，第二次申请写锁。
（2）进程申请自旋锁时没有禁止硬中断，进程获取自旋锁以后，硬中断抢占，申请同一个自旋锁。这种AA死锁很隐蔽，人工审查很难发现。
（3）两个进程都要获取锁L1和L2，进程1持有锁L1，再去获取锁L2，如果这个时候进程2持有锁L2并且正在尝试获取锁L1，那么进程1和进程2就会死锁，称为AB-BA死锁。
（4）在一个处理器上进程1持有锁L1，再去获取锁L2，在另一个处理器上进程2持有锁L2，硬中断抢占进程2以后获取锁L1。这种AB-BA死锁很隐蔽，人工审查很难发现。
避免AB-BA死锁最简单的方法就是定义锁的申请顺序，以破坏死锁的环形等待条件。但是如果一个系统拥有几百个甚至几千个锁，那么没法完全定义所有锁的申请顺序，更可行的办法是在开发阶段提前发现潜在的死锁风险，而不是等到在市场上出现死锁时给用户带来糟糕的体验。内核提供的死锁检测工具lockdep用来发现内核的死锁风险。
1.1 使用方法
死锁检测工具lockdep的配置宏如下：
（1）CONFIG_LOCKDEP：在配置菜单中看不到这个配置宏，打开配置宏CONFIG_PROVE_LOCKING或CONFIG_DEBUG_LOCK_ALLOC的时候会自动打开这个配置宏。
（2）CONFIG_PROVE_LOCKING：允许内核报告死锁问题。
（3）CONFIG_DEBUG_LOCK_ALLOC：检查内核是否错误地释放被持有的锁。
（4）CONFIG_DEBUG_LOCKING_API_SELFTESTS：内核在初始化的过程中运行一小段自我测试程序，自我测试程序检查调试机制是否可以发现常见的锁缺陷。
1.2 技术原理
死锁检测工具lockdep操作的基本对象是锁类，例如结构体里面的锁是一个锁类，结构体的每个实例里面的锁是锁类的一个实例。
lockdep跟踪每个锁类的自身状态，也跟踪各个锁类之间的依赖关系，通过一系列的验证规则，确保锁类状态和锁类之间的依赖总是正确的。另外，锁类一旦在初次使用时被注册，后续就会一直存在，它的所有具体实例都会关联到它。
1．锁类状态
lockdep为锁类定义了（4n+1）种使用历史状态，其中的4指代如下：
（1）该锁曾在STATE上下文中被持有过。
（2）该锁曾在STATE上下文中被以读锁形式持有过。
（3）该锁曾在开启STATE的情况下被持有过。
（4）该锁曾在开启STATE的情况下被以读锁形式持有过。
其中的n是STATE状态的个数，STATE状态包括硬中断（hardirq）、软中断（softirq）和reclaim_fs（__GFP_FS分配，表示允许向下调用到文件系统。如果文件系统持有锁以后使用标志位__GFP_FS申请内存，在内存严重不足的情况下，需要回收文件页，把修改过的文件页写回到存储设备，递归调用文件系统的函数，可能导致死锁）。
其中的1是指该锁曾经被使用过。
如果锁曾在硬中断上下文中被持有过，那么锁是硬中断安全的（hardirq-safe）；
如果锁曾在开启硬中断的情况下被持有过，那么锁是硬中断不安全的（hardirq-unsafe）。
2．检查规则
单锁状态规则如下：
（1）一个软中断不安全的锁类也是硬中断不安全的锁类。
（2）任何一个锁类，不可能同时是硬中断安全的和硬中断不安全的，也不可能同时是软中断安全的和软中断不安全的。也就是说：硬中断安全和硬中断不安全是互斥的，软中断安全和软中断不安全也是互斥的。
多锁依赖规则如下：
（1）同一个锁类不能被获取两次，否则可能导致递归死锁（AA死锁）。
（2）不能以不同顺序获取两个锁类，否则导致AB-BA死锁。
（3）不允许在获取硬中断安全的锁类之后获取硬中断不安全的锁类。
硬中断安全的锁类可能被硬中断获取。假设处理器0上的进程首先获取硬中断安全的锁类A，然后获取硬中断不安全的锁类B；处理器1上的进程获取锁类B，硬中断抢占进程，获取锁类A，可能导致AB-BA死锁。
（4）不允许在获取软中断安全的锁类之后获取软中断不安全的锁类。
软中断安全的锁类可能被软中断获取。假设处理器0上的进程首先获取软中断安全的锁类A，然后获取软中断不安全的锁类B；处理器1上的进程获取锁类B，软中断抢占进程，获取锁类A，可能导致AB-BA死锁。
当锁类的状态发生变化时，检查下面的依赖规则：
（1）如果锁类的状态变成硬中断安全，检查过去是否在获取它之后获取硬中断不安全的锁。
（2）如果锁类的状态变成软中断安全，检查过去是否在获取它之后获取软中断不安全的锁。
（3）如果锁类的状态变成硬中断不安全，检查过去是否在获取硬中断安全的锁之后获取它。
（4）如果锁类的状态变成软中断不安全，检查过去是否在获取软中断安全的锁之后获取它。
内核有时需要获取同一个锁类的多个实例，上面的检查规则会导致误报“重复上锁”，需要使用“spin_lock_nested(lock, subclass)”这类编程接口设置子类以区分同类锁，消除警报。例如：
kernel/sched/sched.h
static inline void double_lock(spinlock_t *l1, spinlock_t *l2)
{if (l1 > l2)swap(l1, l2);spin_lock(l1);spin_lock_nested(l2, SINGLE_DEPTH_NESTING); /* 宏SINGLE_DEPTH_NESTING的值是1 */
}
3．代码分析
以自旋锁为例说明，自旋锁的结构体嵌入了一个数据类型为lockdep_map的成员dep_map，用来把锁实例映射到锁类。
include/linux/spinlock_types.h
typedef struct spinlock {union {struct raw_spinlock rlock;#ifdef CONFIG_DEBUG_LOCK_ALLOC
# define LOCK_PADSIZE (offsetof(struct raw_spinlock, dep_map))struct {u8 __padding[LOCK_PADSIZE];struct lockdep_map dep_map;};
#endif};
} spinlock_t;typedef struct raw_spinlock {arch_spinlock_t raw_lock;…
#ifdef CONFIG_DEBUG_LOCK_ALLOCstruct lockdep_map dep_map;
#endif
} raw_spinlock_t;
数据类型lockdep_map的成员key是锁类的键值，同一个锁类的所有锁实例使用相同的键值；成员class_cache[0]指向锁类的主类（即子类号为0），class_cache[1]指向锁类的子类1：
include/linux/lockdep.h
struct lockdep_map {struct lock_class_key *key;struct lock_class *class_cache[NR_LOCKDEP_CACHING_CLASSES]; /*宏NR_LOCKDEP_CACHING_CLASSES的值是2 */…
};
使用函数spin_lock_init()初始化自旋锁的时候，定义一个数据类型为lock_class_key的静态局部变量，使用它的地址作为锁类的键值：
spin_lock_init() -> raw_spin_lock_init()include/linux/spinlock.h
# define raw_spin_lock_init(lock) \
do { \static struct lock_class_key __key; \\__raw_spin_lock_init((lock), #lock, &__key);\
} while (0)__raw_spin_lock_init() -> lockdep_init_map()kernel/locking/lockdep.c
void lockdep_init_map(struct lockdep_map *lock, const char *name,struct lock_class_key *key, int subclass)
{….lock->key = key;…
}
锁类的主要成员如下：
struct lock_class {struct hlist_node hash_entry;struct list_head lock_entry;struct lockdep_subclass_key *key;…unsigned long usage_mask;…struct list_head locks_after, locks_before;…
}
（1）成员hash_entry用来把锁类加入散列表，第一次申请锁的时候，需要把锁实例映射到锁类，根据锁实例的键值在散列表中查找锁类。
（2）成员lock_entry用来把锁类加入全局的锁类链表。
（3）成员key指向键值。
（4）成员usage_mask是锁类的使用历史状态。
（5）成员locks_after：曾经在获取本锁类之后获取的所有锁类。
（6）成员locks_before：曾经在获取本锁类之前获取的所有锁类。
在进程描述符中增加了以下成员：
include/linux/sched.h
struct task_struct {…
#ifdef CONFIG_LOCKDEP
# define MAX_LOCK_DEPTH 48ULu64 curr_chain_key;int lockdep_depth;unsigned int lockdep_recursion;struct held_lock held_locks[MAX_LOCK_DEPTH];gfp_t lockdep_reclaim_gfp;
#endif…
};
数组held_locks保存进程持有的锁，成员lockdep_depth是进程持有的锁的数量。
如下所示，调用spin_lock()申请自旋锁的时候检测死锁，函数__lock_acquire是lockdep检测死锁的核心函数，执行过程如下：
（1）如果是第一次申请锁实例，需要把锁实例映射到锁类。
（2）把锁添加到当前进程的数组held_locks中。
（3）调用函数mark_irqflags修改锁的状态，检查依赖规则。
（4）调用函数validate_chain检查死锁。
假设当前申请锁类L2，函数validate_chain的检查过程如下：
（1）调用函数check_deadlock检查重复上锁，即当前进程是否已经持有锁类L2，如果已经持有锁类L2，除非两次都申请读锁，否则存在死锁。
（2）调用函数check_prevs_add，根据以前学到的锁类依赖关系检查死锁。
假设当前申请锁类L2，函数check_prevs_add针对当前进程的数组held_locks中的每个锁类L1，调用函数check_prev_add检查，检查过程如下：
（1）调用函数check_noncircular以检查AB-BA死锁。
（2）调用函数check_prevs_add，根据以前学到的锁类依赖关系检查死锁。
假设当前申请锁类L2，函数check_prevs_add针对当前进程的数组held_locks中的每个锁类L1，调用函数check_prev_add检查，检查过程如下：
（1）调用函数check_noncircular以检查AB-BA死锁。
检查锁类L1是否出现在锁类L2的链表locks_after中，如果出现，说明以前的申请顺序是L2-L1，现在的申请顺序是L1-L2，存在死锁风险。
递归检查，针对锁类L2的链表locks_after中的每个锁类L3，检查锁类L1是否出现在锁类L3的链表locks_after中，如果出现，说明存在死锁风险。
（2）调用函数check_prev_add_irq，检查是否存在以下情况：“在获取硬中断安全的锁类之后获取硬中断不安全的锁类”或者“在获取软中断安全的锁类之后获取软中断不安全的锁类”。
如果锁类L1的链表locks_before中存在硬中断安全的锁类，并且锁类L2的链表locks_after中存在硬中断不安全的锁类，那么说明在获取硬中断安全的锁类之后获取硬中断不安全的锁类，存在死锁风险。
（3）学习锁类的依赖关系：把锁类L2添加到锁类L1的链表locks_after中，把锁类L1添加到锁类L2的链表locks_before中。
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！