Go语言是如何实现race dectect的

2016-11-20

Go语言是如何实现race dectect的

1.

在写如果检测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 := xx = 5两个操作访问了同一块内存x,并且没有任何保证v := x是happens before x = 5的,所以这段代码有race。

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

2.

如何检测到happens before事件呢?

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

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

func f() {
    g := 3
}

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

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

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

3.

一条内存访问事件可以用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

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

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

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

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

racedectectgolang