点击上方蓝色“Linux News搬运工”关注我们~

Finding race conditions with KCSAN

By Jonathan Corbet

October 14, 2019

Race conditions （多方竞争）是最难调查的一类bug了。这种问题的影响有可能很细微，重现也很难，甚至完全不可能。有时候只是加两行调试代码就可能导致这个问题再也不出现了。因此kernel社区都很希望能有一个工具来自动找到race condition。在9月下旬，Marco Elver宣布了一个KCSAN工具（the Kernel Concurrency Sanitizer）就是针对这个需求的，并且已经真的发现了好几个真实问题。

race condition问题都有一个共性，就是对一个公用数据的多方访问的不同顺序会导致不同的结果。这类问题很难通过审查代码来检测出，因为这牵涉到代码里不同地方的多处代码，而且要能想象出会产生问题的那种特殊访问顺序。不过用工具来监测的话，哪怕系统行为表现正常，工具也有可能报出潜在问题。KCSAN会持续监控对内存区域的访问，来查找如下访问特征：

• 多个线程访问同一处内存

• 这些访问的顺序不可知，例如并没有锁来保证访问顺序，并且

• 至少其中一个访问是个写操作。

不用说，监控每一处内存空间的工作量就太大了，所以KCSAN采用了统计学方法来期望最终能碰到这种情形。

How it works

第一步是在编译kernel的时候加上-fsanitize=thread选项，GCC和Clang都支持这个选项。编译好的代码就能允许监控内存访问了。具体来说，每个内存访问都会通过某个嵌入的函数调用来实现。假如代码里会在addr这个位置读取4个字节，那么编译生成的代码就会调用__tsan_read4(addr)。监控代码支持__tsan_readN()和__tsan_writeN()这些函数，这样就有可能根据它监测到的访问行为模式来做进一步的工作了。

KCSAN中，每2000次调用这些函数时，其中1999次都会被忽略掉，否则的话会导致kernel太慢了，以至于无法使用。在第2000次访问时，KCSAN就会留意一下这个访问的地址，在附近这段时间内看看是否有其他的访问。在当前访问这个内存的线程上下文内，KCSAN会设置一个watchpoint，这是通过在一个很小的表格里记录下访问地址、长度、以及是否写入操作等信息来实现的。然后这个线程就直接delay 10us（可以调整）。

上面描述的流程是一个简化版本，这里其实还有一些例外。首先，在决定是否忽略一次访问的时候，KCSAN会先看看是否有watchpoint在关注这个地址，如果有的话，只要这次访问是write，或者创建watchpoint的那次操作是write，都会被判定为检测到一个race condition，然后在system log里记录一笔。

假如没有watchpoint关注它，那么代码会判断当前的访问是否是在atomic context（原子操作上下文，这是KCSAN自己的一个定义，跟kernel里常用的定义不太一样），然后再决定是否忽略这次访问。如果是atomic access的话，那就不会创建watchpoint，不过如果本来就已经有了一个watch point，然后代码里访问这块内存既有atomic访问也有非atomic访问，那么通常也会出问题。

与此同时，起初的线程在设置watchpoint之后进入额外delay阶段，那么在delay结束之后，watchpoint就会被删除掉，也就不再监控这个地址了。不过在继续执行之前，会检查一下这个地址的内容，如果在watchpoint被设置之后这个内容发生了变化，那么还是会报出一次race condition事件。

当然上面的介绍仍是一个简化描述，不过核心算法差不多就是这样了。很明显它肯定会错过很多race codition，因为它只检查kernel内存访问中的一小部分。不过，如果运行足够长的时间，KCSAN就能查到代码审查中漏网的很多race condition了。

KCSAN in action

syzbot系统已经开始把KCSAN加到它的模糊测试中了，因此很快就有bug报了出来。第一个被报出来的是kernel的taskstats子系统出的问题，然后Christian Brauner给出了fix，不过尚未合入mainline。不过fix已经迭代了5个版本，应该快要完成了。

在内核中，最仔细审查是否有并发问题的代码就是RCU子（read-copy-update）系统了。RCU本身就是设计出来作为并发管理机制的。在10月7日，KCSAN就发现了RCU内的一个data race condtion，后来就有好几个patch试图fix这个问题，暂时还未合入mainline。

其实KCSAN也会产生假警报。可以通过在代码里改一下写法来让这些访问不再被KCSAN检测为race condition，比如对这些访问用READ_ONCE()和WRITE_ONCE()来标记。有些开发者很担心KCSAN报告会导致开发者还没有完全搞懂逻辑就急于解决问题。其实这些假警报也是有价值的，Eric Dumazet在分析TCP代码里报出的疑似race condition的时候，就查出并修复了一处真的race condition，是由2012年的TCP fast open机制引入的。

KCSAN是个全新的工具，还有不少很多细节需要打磨，需要不少时间，也需要开发社区共同努力来把KCSAN报告更好的利用起来。可以肯定的是，它会非常有价值，因为能找到那些很难查的bug。今后在KCSAN的帮助下，kernel一定会更加稳定可靠。