4. 锁依赖图

锁依赖图（Lock Dependency Graph, LDG）是死锁检测与预防的核心工具。通过将锁的获取关系建模为有向图，可以直观地发现循环等待链，从而在代码审查或运行时分析中提前暴露死锁风险。本节将系统讲解锁依赖图的构建方法、循环依赖识别技术，以及如何在 Android 内核驱动开发中应用这一工具。

4.1 锁依赖图的基本概念与构建规则

锁依赖图是一个有向图 G = (V, E)，其中：

• V（顶点）：表示系统中的每一把锁（如 spinlock、mutex、rwlock）。
• E（有向边）：表示锁的获取顺序。若线程 T 在持有锁 A 的情况下请求锁 B，则添加一条从 A 指向 B 的有向边 A → B。

构建锁依赖图的核心规则如下：

4.2 锁依赖图的绘制方法

绘制锁依赖图通常分为三个步骤：锁操作日志采集 → 依赖关系提取 → 图形化渲染。以下分别介绍手动绘制与自动化工具两种方式。

4.2.1 手动绘制：基于代码审查

对于小型驱动模块，可以通过审查所有加锁/解锁路径来手动构建依赖图。以下是一个典型的驱动代码片段：

/* 驱动函数 A */
void func_a(void) {
    spin_lock(&lock1);
    spin_lock(&lock2);
    /* 临界区 */
    spin_unlock(&lock2);
    spin_unlock(&lock1);
}

/* 驱动函数 B */
void func_b(void) {
    spin_lock(&lock2);
    spin_lock(&lock3);
    /* 临界区 */
    spin_unlock(&lock3);
    spin_unlock(&lock2);
}

/* 驱动函数 C */
void func_c(void) {
    spin_lock(&lock3);
    spin_lock(&lock1);  /* 潜在死锁点 */
    /* 临界区 */
    spin_unlock(&lock1);
    spin_unlock(&lock3);
}

根据上述代码，可以提取出以下依赖边：

• func_a: lock1 → lock2
• func_b: lock2 → lock3
• func_c: lock3 → lock1

这三条边构成了一个完整的循环依赖链：lock1 → lock2 → lock3 → lock1。

4.2.2 自动化绘制：使用 lockdep 与图形工具

Linux 内核的 lockdep 子系统可以在运行时自动记录锁依赖关系，并通过 /proc/lockdep 和 /proc/lockdep_chains 导出。结合 dot 工具（Graphviz）可以生成可视化依赖图：

# 从内核导出锁依赖数据
cat /proc/lockdep_chains > lock_chains.txt

# 使用脚本转换为 dot 格式（示例脚本片段）
awk '{print $1 " -> " $3}' lock_chains.txt | sort -u > edges.dot

# 使用 Graphviz 生成 SVG 图
dot -Tsvg edges.dot -o lock_dep_graph.svg

4.3 循环依赖识别与死锁路径分析

锁依赖图中的有向环直接对应死锁的循环等待条件。识别循环依赖是死锁排查的核心任务。以下 SVG 图展示了一个典型的循环依赖场景：

识别循环依赖的常用方法包括：

• 深度优先搜索（DFS）：对每个节点进行 DFS，若在递归栈中发现已访问节点，则存在环。
• 拓扑排序：若无法生成完整的拓扑排序，则图中存在环。
• 锁链长度检测：lockdep 默认记录最大锁链深度（MAX_LOCKDEP_CHAINS），超过阈值时触发告警。

4.4 Android 驱动中的锁依赖图实战

在 Android BSP 开发中，锁依赖图常用于以下场景：

4.4.1 实战案例：I2C 设备驱动死锁排查

某 Android 设备在压力测试下出现 I2C 总线死锁。通过 lockdep 日志提取依赖图如下：

[  123.456] INFO: possible circular locking dependency detected
[  123.456] 3 locks held by kworker/0:1/42:
[  123.456]  #0:  (&adap->bus_lock){+.+.}-{3:3}, at: i2c_transfer+0x58/0x100
[  123.456]  #1:  (&client->lock){+.+.}-{3:3}, at: i2c_device_probe+0x24/0x80
[  123.456]  #2:  (&dev->mutex){+.+.}-{3:3}, at: driver_probe_device+0x40/0x120

[  123.456] other info that might help us debug this:
[  123.456]  Possible unsafe locking scenario:
[  123.456]        CPU0                    CPU1
[  123.456]        ----                    ----
[  123.456]   lock(&dev->mutex);
[  123.456]                                lock(&adap->bus_lock);
[  123.456]                                lock(&client->lock);
[  123.456]   lock(&dev->mutex);
[  123.456]  *** DEADLOCK ***

根据日志绘制依赖图：

• CPU0 路径：dev->mutex → adap->bus_lock → client->lock
• CPU1 路径：adap->bus_lock → client->lock → dev->mutex

两条路径形成环：dev->mutex → adap->bus_lock → client->lock → dev->mutex。解决方案是统一锁获取顺序，确保所有路径都按 dev->mutex → adap->bus_lock → client->lock 的顺序获取。

4.5 锁依赖图的进阶分析技术

对于复杂系统，锁依赖图可能包含数百个节点和数千条边。以下技术可提升分析效率：

4.5.1 依赖图简化：锁分组与层次化

将功能相关的锁合并为锁组，在图中以超节点表示。例如，所有与 DMA 缓冲区相关的锁可以归为 DMA_LOCK_GROUP。简化后的图更易于识别跨子系统的循环依赖。

4.5.2 锁依赖矩阵

对于锁数量较少（< 20）的场景，可以使用依赖矩阵进行快速分析。矩阵元素 M[i][j] 表示是否存在从锁 i 到锁 j 的依赖边：

矩阵中 M[1][2]=1、M[2][3]=1、M[3][1]=1 构成环。通过矩阵的幂运算可以检测长度为 k 的环。

4.5.3 运行时依赖图动态更新

在 Android 内核中，lockdep 支持运行时动态更新依赖图。当检测到新依赖边时，会立即执行环检测。若发现环，则输出告警并记录调用栈。驱动开发者可以通过 echo 1 > /sys/kernel/debug/locking/lockdep_enable 动态启用/禁用检测。

4.6 锁依赖图工具链与最佳实践

以下工具和流程可帮助团队系统化地使用锁依赖图：

最佳实践总结：

1. 编码阶段：使用 lockdep_assert_held() 和 lockdep_assert_not_held() 在代码中显式声明锁状态。
2. 代码审查：为每个驱动模块绘制锁依赖图，确保无环且锁顺序一致。
3. 测试阶段：开启 lockdep 运行压力测试，收集所有告警并修复。
4. 发布前：关闭 lockdep 以消除性能开销，但保留 LOCK_STAT 用于线上监控。