EuroSys 2019 LockDoc

EuroSys - 2019 - LockDoc: Trace-Based Analysis of Locking in the Linux Kernel

摘要

对内核开发者来说，锁的使用是一件非常烦琐而且复杂的工作，需要针对代码的上下文、特定的成员对象综合考虑锁的使用，更糟糕的一件事情是，开发文档上关于锁的使用的介绍是不全面的，甚至是出错的。在这样的条件下，开发者很难不写出错误代码，错误的使用锁可能造成死锁、条件竞争，或者是并行的性能下降等危害。

相较之前的工作倾向于帮助开发者找到 内核中的 bug，本文采用了另一种思路来降低开发者写出含有 bug 代码的概率：即通过更完善的文档、更详细的介绍来帮助开发者编写正确的代码。那么如何得到正确的加锁规则和完善的文档？作者在这里基于以下出发点：一般而言，Linux 等操作系统绝大多数情况下处于正常运行状态，因此可以通过分析正常情况 下Linux 内核的 trace 来推断什么是合理的加锁规则。

为此，本文提出了一种基于 trace 的自动加锁规则推断工具，通过在一个插桩的 Linux 内核上记录对内核的数据结构和对锁的获取释放的记录，可以分析并推断锁的合理加锁规则，通过这些规则可以验证现有文档的缺陷以及定位可能的bug。

最终，作者在实验中找到了 52,452 个违反推导出的加锁规则的例子，并由开发者确认了其中一个是真实存在的 bug。

背景

锁的使用

从上图可以看到，在 Linux kenerl 的版本号从 3.0 到 4.18 的 7 年时间里，Linux kernel 的总代码行数增长了约 73%，Spinlock 锁的使用增长了 45%，而 mutexes 锁的使用增长了约 81%，增长关系随着代码行数的增加保持着一定的线性关系。

复杂的使用场景

Linux 中提供了多种加锁机制，根据当前或者潜在的上下文环境，比如用于一个 IRQ 的 handler，或者是 bottom half，开发者需要选择符合需求的锁，比如说 spin_lock[_(bh|irq)]，read_seqbegin，write_seqlock[_(bh|irq)]， mutex_lock，down，local_(bh|irq)_disable 还是preempt_disable 。此外，在符合需求的锁中，可能需要继续选择性能最好的一个，比如在不会条件竞争的情况下，序列锁 read_seqbegin 、write_seqlock 比 spinlocks 的效率更好；而如果已知并发的控制流只会在一个 CPU 上运行的话 ，轻量级的加锁机制 preempt_disable， local_bh_disable，local_irq_disable 更被推荐使用。

潜在的 Bug

对于并行来说，是否加锁一直是一个需要取舍的问题，如果采取谨慎小心的态度，那么所有相关的数据结构都需要加上锁，那么很容易就有性能上的问题；相反，如果采用一种非常宽松的策略，那么很有可能就会出现条件竞争相关的漏洞，并最终导致相关的 bug。

除此之外，锁的顺序也相当重要，否则很有可能导致活锁或者死锁的问题；另外，及时释放一个已获得的锁也是避免潜在 bug 的重要手段。由于 Linux 代码中经常出现的函数提早返回的情况，跟加锁相关的代码相比，锁的释放的相关代码更多。

关于锁的文档

那么 Linux 对相关的文档是否详尽呢？答案也是否定的。以 struct inode 为例，在头文件 include/linux/fs.h 中有仅有一处有价值的注释：

spinlock_t i_lock ; /∗ i_blocks , i_bytes , maybe i_size ∗/

那么换一个思路，从具体的实现文件 fs/inode.c 来看，里面有如下注释：

Inode locking rules:

inode−>i_lock protects :
  inode−>i_state , inode−>i_hash , __iget ()
Inode LRU list locks protect :
	inode−>i_sb−>s_inode_lru , inode−>i_lru
[...]
inode_hash_lock protects :
	inode_hashtable , inode−>i_hash
[...]

但这里同样存在着极大的问题，比如 inode−>i_hash，inode−>i_lock 和 inode_hash_lock 这两种规则都被建议来保护该数据结构，这很难不让阅读该注释的开发人员迷惑。

更有趣的是，开发人员甚至可能写出如下注释：

We don’t actually know what locking is used at the lower level; but if it’s a filesystem that supports quotas, it will be using i_lock as in inode_add_bytes().

总而言之，对于一个对源代码陌生的新 Linux 开发人员来说，处理 Linux kernel 中成百上千种锁是一种非常困难的任务而且极大容易出错。

已有的研究

目前，对 linux kernel 已有的研究可以简单分为以下三种，即预先的静态分析，过程中的动态分析，以及对过程中产生的结果所做的事后分析，三者各自拥有不同的优缺点。

• Ahead-of-Time Analysis

  • 静态分析的缺点非常明显，比如别名指针的问题，或者是针对程序的控制流的状态判断问题。现有的静态分析工作一般针对的代码模式较为有限，解决的问题也较为不全面。

• Runtime Analysis

  • 运行时的动态分析不会遇到诸如别名指针等问题，但相应的，存在代码覆盖率之类的问题。

• Ex-Post Analysis

  • 由于 Ex-Post Analysis 依赖于 Runtime Analysis 生成的结果，因此在大多数情况下二者的优缺点是相似的，但相比 Runtime Analysis，研究人员能以任意方式来存储并分析应用的执行结果。

但令人遗憾的是，现有的工作绝大部分仍在关注如何在源代码中发现 bug 或者是解决性能的瓶颈，而没有任何的工作来辅助开发者写出正确的代码，本工作即旨在弥补这一缺陷，利用基于 trace 的分析，架成一道连接文档和 Linux kernel 真实开发环境的一道桥梁。

假设与挑战

假设有如下代码， 其中 seconds 和 minutes 是两个共享变量，分别被锁 sec_lock 和 min lock 保护。

lock(&sec_lock); // transaction a − start
seconds = seconds + 1;
if (seconds == 60) {
    lock(&min_lock); // transaction b − start
    seconds = 0;
    minutes = minutes + 1;
    unlock(&min_lock); // transaction b − end
}
unlock(&sec_lock); // transaction a − end

在某次执行中，该代码执行了 1000 次，此外还有另外一条执行结果，一个错误地没有给 minutes 加上 min_lock 锁，那么统计对 minutes 变量的访问情况，以及可能的加锁规则，得到结果如下图所示：

其中正确的结果满足无加锁、sec_lock、sec_lock->min_lock、min_lock 这四种情况，所以会有 16 次符合要求的访问，而错误的加锁规则之满足无加锁以及 sec_lock 这两种情况，所以这两种加锁规则还需要额外加上一个错误路径带来的 1，具体的计算规则如下图所示：

无加锁：1000 // 60 + 1 = 17

sec_lock：1000 // 60 + 1 = 17

sec_lock -> min_lock：1000 // 60 = 16

min_lock：1000 // 60 = 16

min_lock -> sec_lock：0

那么，下一个问题，我们如何选择正确的可能？

为此，作者提出了“次优选择”的策略。首先选择一个合理的阈值 tac，在 sr 高于阈值 tac 的所有情况中，选择值 sr 最小的一个，如果有多种可能，选择其中加锁最多的一个。这种选择的理由在于，在假设高于阈值的选择都具有可能性的情况下，错误的加锁使用反而会给错误的选择贡献访问，所以错误的选择反而 sr 的值更高。同理，在可选情况较多时，全集更比子集具有合理性。

设计与实现

LockDoc 的整体工作流程如上图所示，具体来说可以分成三个阶段，下面简单介绍三个阶段的工作。

monitoring/tracing phase

通过在一个 VM 里运行插桩后的 Linux kernel，记录相关数据结构的分配以及锁的加锁以及释放，生成相应的 trace 并插入到数据库中。

locking-rule derivation phase

利用上一阶段得到的数据，在这一阶段可以推断出所有的加锁规则的假设上的可能性，然后推断出合理的规则。

analysis phase

这一阶段主要是利用前一阶段生成的结果，来主要完成以下三个工作：

1. 通过生成的加锁规则和官方文档提供的加锁规则进行对比，比较二者的合理性
2. 利用生成的加锁规则，生成用户可读的文档
3. 通过生成规则的和记录的内存访问，验证代码中是否存在违背加锁规则的现象

实验评估

前置条件

• vanilla Linux 4.10
• lock：spinlock_t， rw_lock_t， semaphore， rw_semaphore， mutex， rcu
• Fail*-based experiment environment

测试代码的覆盖率：

Locking Rule Checking

测试的 5 个数据结构主要来自 OCFS2 和 ext4 所使用的组件 JBD2，分别是 inode、 dentry、journal_t 、transaction_t、journal_head

根据在源代码中的注释，可以抽象出 142  项规则（71 个对象的读/写），总的结果如下表所示（其中 Table 5 是 Table 4 中 inode 项的详细结果）：

其中 #No 表示没有触发到的代码，#Ob 则是触发到的代码，后三者中√ 表示结果完全符合， 􏰊~ 表示执行结果和文档部分符合，× 表示完全不符合。

从这里能推出的结论是，或者是 Linux kernel 的源代码，或者是相关的文档，二者之中必然有一个出错了。但由于这里没有一个可供参考的 Ground Truth，因此无法得出确切的结论。但可以看出的是，transaction_t 的文档质量相对较好，因为他和实际执行结果的匹配程度最高。

Locking Rule Mining

本节主要讨论了 tac 和 sr 相关的合理性，比如不同的阈值 tac 会带来不同的结果，比如 tac 更低的时候，由于次优选择的策略，可能会选择不同的结果。

关于实际 sr 可能更低的情况，作者给了以下几个猜想：

1. 由于代码的覆盖率问题，无法触发代码可能会导致 sa = 0
2. 插桩的不完整或者是其他工作上的疏忽，导致了 sr 较低

然后作者给出了利用推断出的规则可以生成的文档的例子：

Locking Rule Violations

作者在实验中最终找到了 52,452 个违反规则的内存访问的例子，但这同样由于没有 Ground Truth 而无法进行验证，但其中有一个被开发人员证实为 bug。

关于 FP，作者总结了以下几点原因：

1. Linux kernel 的代码中，可能会因为性能的原因，主动选择不使用某些锁
2. 或者相似的情况，当开发者知道某些情况下不会出现并发访问的时候，会主动忽略锁的使用
3. 上述问题引起的噪音加上次优选择的策略，可能推断出错误的加锁规则，同样会引起 FP

总结与未来展望

开发 kernel 的艰巨性决定了一个详尽的文档的必要性，而文档往往是不详细的残酷现实又给了该问题致命一击。

那么如何得到一个详尽而且正确的文档呢？作者巧妙地基于一个假设：一般情况下 Linux 等操作系统是正常运行的，正常运行的系统很大概率正常地使用着锁。因此，我们能从一个系统的执行流程中推断出什么样的使用才是合理的。

当然，这种假设不仅仅适用于 Linux kernel，这种基于大数据的合理性推断完全可以推广到其他大型应用的开发过程中，辅助相应问题的解决。