Go语言是如何实现race dectect的

2016-11-20

Go语言是如何实现race dectect的

在写如果检测race之前，首先明白第一个问题，什么是race?

当多个goroutine同时在对同一个变量执行读和写冲突的操作时，结果是不能确定的，这就是race。比如goroutine1在读a，goroutine2在写a，如果不能确定goroutine1读到的结果是goroutine2写之前还是写之后的值，就是race了。

var x int
go func() {
    v := x
}()
x = 5

上面的代码v的值到底是0，还是5呢？不知道，这段代码存在race。这是比较口头的描述，严谨的形式化的描述，就需要讲Go的内存模型。

Go的内存模型描述的是"在一个groutine中对变量进行读操作能够侦测到在其他goroutine中对该变量的写操作"的条件。

这里不展开，可以读我以前写的一些东西(TL;DR...因为年代久远又没更新，里面的示例在现在还是错的了...不过这篇文章对于理解happens before概念还是很好的)。

假设A和B表示一个多线程的程序执行的两个操作。如果A happens-before B，那么A操作对内存的影响 将对执行B的线程(且执行B之前)可见。

有了happens before这么形式化的描述之后，是否有race，等价于对于同一块内存访问，是否有存在无法判断happens before的冲突操作。即是说：

对于前面那段代码，v := x和x = 5两个操作访问了同一块内存x，并且没有任何保证v := x是happens before x = 5的，所以这段代码有race。

那么"实现race dectect"这个问题，就转化成了"happens before事件的检测问题"。

如何检测到happens before事件呢？

我们可以把"哪个线程id，在什么时间，访问哪块内存，是读还是写"，只要把所有内存访问的事件都记录下来，然后遍历，验证这些操作之间的先后顺序。一旦发现，比如，读和写两条操作记录，无法满足读happens before写，就是检测到race了。

但是要记录所有的内存访问操作，看起来代价似乎有点吓人。其实只是记录可能会被并发访问的变量，并不是所有变量，下里的g是局部变量，就不需要记录了。

func f() {
    g := 3
}

但是代价似乎还是很大？确实。好吧，会慢10倍还是100倍我不确定，反正线上代码是不会开race跑的。既然Go都已经做了，肯定是能做的。

需要有两部分，在Go里面-race编译选项会做相应的处理。编译部分需要在涉及到内存访问的地方插入指令来记录事件；运行时则是检测事件之间的happens before。

整个思路就是这样，再具体就是细节了。

一条内存访问事件可以用8个字节来记录：16位线程id，42位时间戳，5位记内存位置，1位标记是读还是写。

线程id不用解释，读写标记也不用解释。时间戳是逻辑时钟，不是每次取真实时间。

只用5位如何记录内存位置呢？这里就有点技巧了，Go的内存管理也用到了同样的技巧。对于实际使用的一块内存区域，映射另一块"影子"内存区域，映射出来的是真实的"影子"。

比如有一个数组A[1000]，它的"影子"是B[1000]。A[i]里面发生了什么事件，只在记录在B[i]里面就行了。注意两者大小不需要是一样的，比如

int  A[1000];   // 真实使用的数组
char B[1000];   // 用于记录发生在A数组里面操作，如果只记读/写1位足已，记其它也不一定用到8位

同理，对于实际使用的内存区域是[0x7fffffffffff 0x7f0000000000]，它的"影子"区域可以是[0x1fffffffffff 0x180000000000]，5位可以表示64个单元，如果实际使用的内存使用按8字节对齐之后，是足够表示一组的。

好像有点说不明白，这么解释吧：3位可以表示8个单元的状态，对吧？2的3次方等于8

A[8个8字节的单元] => B[3位]

A里面是否发生了读或者写的操作，在B里面用位的0或1记录来下。说明只用少量内存就可以记录大量事件！

回到事件的记录格式，一条记录占8个字节，其中有5位记录内存位置。5位是可以记录64个8字节的，也就是race dectect的空间开销是使用的内存的1/8(其实不是，因为对同一内存的事件，要记录一组)。

看个例子，我们记录下了第一条事件，线程T1，在E1时间戳，访问内存区域[0 2]，执行写操作：

(T1,E1,0:2,W)

第二条事件，线程T2，在E2时间戳，读内存区域[4 8]：

(T2,E2,4:8,R)

因为位置没有交集，所以没有冲突。

第三条事件，线程T3，在E3时间戳，读内存区域[0 4]：

(T3,E3,0:4,R)

这个区域是跟第一个事件的区域有交集的，那么假设E1无法满足happens before E3，那么就检测到冲突了。

参考资料：https://github.com/google/sanitizers/wiki/ThreadSanitizerAlgorithm

思考是个很有趣味的事情。起点是好奇心，终点是智慧。

思考需要一步一步将具体问题抽象成可以代码描述出来的实现。

忍不住看了答案，所以写的顺序就一步步反推了。实际上在不知道一个东西如何解决时，自己想，是很能锻炼抽象问题的能力，也是非常有意思的。读完这篇文章的读者就错过一次机会了。

所以呢，留一道思考题，死锁检测又该如何做呢？可以留言，或者来份简历大家交流一下（开个玩笑而已，不打广告了）。