Golang种族检测

竞赛条件是非常讨厌的错误。 难以追踪,复制和隔离; 通常在异常情况下发生,并经常导致难以调试的问题。 因此,最好尽早预防和发现它们。 值得庆幸的是,有一个可用于生产的准备就绪的算法可以应对这一挑战-ThreadSanitizer v2,这是一种经过实践检验的库,可为Go,Rust,C和C ++中的编译器提供支持。

首先,让我们显示一个典型的比赛条件。 我们有一个简单的全局计数变量:

而且我们会计算发生的事件数,无论我们是在计算HTTP请求,还是点赞或火种匹配都无关紧要。 相关的是我们如何做到的。 我们将函数称为Run

 fun Run(amount int) { for i := 0; i < amount; i++ { Cnt++ } } 

但这还不是全部。 我们从多个goroutine中调用它:

 func main() { wg := &sync.WaitGroup{} for i := 0; i < 10; i++ { wg.Add(1) go func() { defer wg.Done() Run(1000) }() } wg.Wait(); fmt.Println(Cnt) } 

而且我们希望结果是10000 。 然而,这不可能在多核多线程系统上发生。 您最有可能获得5234运行, 1243次运行甚至1521次运行的结果,而没有任何确定性或可重复性。 这是典型的数据竞赛!

让我们不要停止这个玩具示例。 相反,让我们评估一些在现实世界中产生严重后果的比赛条件。

著名的例子

这是Linux内核中的竞争条件。 它涉及棘手的内存页面相互作用, mmapmadvise系统调用,这些漏洞允许特权升级利用。 也就是说,您可以mmap根拥有的文件,即写时复制,这是一项有效的操作(每次写入此mmap -ed区域均不得写入基础文件),但是在某些情况下,写入会传播到基础文件,尽管我们不是特权用户。

进一步的信息

Therac-25

另一个著名的例子是Therac-25放射治疗仪。 它在机器设置和显示设置之间存在争用条件。 如果用户键入指令的速度过快并迅速更改,则机器可能会以最大辐射剂量结束,同时向操作员显示虚假信息。 这导致了多起事故和死亡案例。
进一步的信息

定义

在继续之前,让我们简要地迭代所需的定义:

竞态条件 —竞态条件是一种不希望的情况,当设备或系统尝试同时执行两个或多个操作时会发生这种情况,但是由于设备或系统的性质,必须按照正确的顺序进行操作正确完成

由于一般的竞争条件范围,并且要求领域知识了解什么是正确的行为,因此在本文的其余部分中,我们将重点放在数据竞争上,这是更为狭窄和客观的定义。

数据争用并发访问内存位置,其中之一是写操作

并发访问 -事件顺序未知的一种。 关系happens before没有happens before

关系发生之前需要进一步解释。 每个goroutine都有自己的逻辑时钟。 它在每次操作时都会递增。 每个goroutine中都有严格的顺序,事件是顺序发生的(或者至少我们观察到它们好像顺序发生的那样,各种编译器优化/乱序执行可能会干扰)。 在goroutine之间,除非它们之间存在同步,否则没有顺序。

在下图中,您可以直观地看到它。 happens before使用箭头突出显示关系happens before 。 我想提醒一下, happens before关系是happens before关系传递happens before

常见错误

让我们观察一下go程序中的一些常见错误。 这些示例在其他主要语言中具有类似的等效项,因为我非常喜欢它,所以它在Go中。

在循环柜台上比赛

 func main() { var wg sync.WaitGroup wg.Add(5) for i := 0; i < 5; i++ { go func() { fmt.Println(i) // Not the 'i' you are looking for. wg.Done() }() } wg.Wait() } 

试试看。 根据事件的顺序,您可能会得到0 4 4 4 4作为输出。 当然不是您期望的输出。 解决方法非常简单:

 func main() { var wg sync.WaitGroup wg.Add(5) for i := 0; i < 5; i++ { go func(j int) { fmt.Println(j) wg.Done() }(i) } wg.Wait() } 

未受保护的全球

这与介绍性示例相似:

 var Cnt int func Inc(amount int) { Cnt += amount } func main() { go Inc(10) go Int(100) } 

解决方案是同步访问全局Cnt变量,因为增量操作不是原子操作(除非使用sync/atomic包)。

因此,我们使用互斥锁:

 var Cnt int var m = &sync.Mutex{} func Inc(amount int) { m.Lock() defer m.Unlock() Cnt += amount } 

或原子变量:

 var Cnt int64 func Inc(amount int64) { atomic.AddInt64(&Cnt, amount) } 

违反记忆模型

Go内存模型指定编译器提供的保证。 如果您违反该合同,那您将陷入困境。 编译器可以自由地优化代码或使用它做不可预测的事情。

 var a string var done bool func setup() { a = "hello, world" done = true } func main() { go setup() for !done { } fmt.Print(a) } 

在此示例中,go的内存模型不能保证对一个goroutine的写入对其他goroutine可见,因为它们之间没有同步。 编译器也可以自由地进行优化:

到一个更简单的结构中,而不是每次迭代都加载完成的变量。 此外,不能保证在CPU内核之间的内存缓冲区和L1高速缓存之间应在并发读取的done变量之间刷新。 这都是由于无序执行的复杂性以及跨体系结构的各种内存保证所致。 例如,x86在汇编代码方面比ARM体系结构具有更强的内存保证。

同步原语

在Go中,我们具有以下同步原语:

  • 通道,即发送和接收是一个同步点
  • 同步包

有关更多详细信息,请查阅这些内容,它们并不是行之有效的概念,也不是种族检测。 重要的一点是,它们会在订购程序代码之前发生。

检测比赛条件

在Go中,只需使用-race编译器标志即可完成。 我们甚至可以使用它进行测试,并在任何竞争条件下失败:

 go install -race go build -race go test -race 

如开始时所说,它在后台使用ThreadSanitizer库。 您应该期望运行时间减慢2–20倍,内存消耗增加5–10倍。 其他要求是启用CGO和64位操作系统。 它可以可靠地检测比赛条件,而不会产生误报。 在使用过程中,发现了chrome中的1000多个bug,go的标准库中的100多个bug,其他项目中的更多。

-race标志的作用是通过附加指令来检测代码。 例如,这个简单的函数:

 func Inc(x *int) { *x++ } 

Get编译成:

 movq "".x+8(SP), AX incq (AX) 

但是,在打开-race会得到一堆汇编代码,有趣的是:

 ... call runtime.raceread(SB) ... call runtime.racewrite(SB) ... 

也就是说,编译器为每个可同时到达的内存位置添加了读取和写入障碍。 编译器足够聪明,不会检测局部变量,因为这会导致相当大的性能损失。

算法

首先是坏消息:

 Determining if an arbitrary program contains potential data races is NP-hard. 

Netzer&Miller 1990年

因此,我们的算法应进行权衡。 ˍ

首先,我们如何以及何时收集数据。 我们的选择是动态分析或静态分析。 静态分析的主要缺点是正确注释源代码所需的时间。 之所以使用这种动态方法,是因为除了打开它之外,不需要其他程序员干预。 可以实时收集数据或将其丢弃到某个地方进行事后分析。 出于性能方面的考虑,ThreadSanitizer使用动态方法。 否则,我们可能会堆积大量不必要的数据。

动态种族检测有多种方法,包括基于先验,基于锁集和混合模型的纯发生。 ThreadSanitizer使用过的以前发生过。 现在,我们将介绍3种算法,每种纯算法都发生在动态竞速检测之前,每种算法都在最后一种算法上有所改进。 我们将了解ThreadSanitizer的演变方式,并从卑鄙的起源中了解其工作原理:

矢量时钟

首先,让我们解释一下矢量时钟的概念。 我们不会记住每个goroutine仅记住其逻辑时钟,而是记住上一次从另一个goroutine听到的逻辑时钟。

如果两个事件之间的关系严格greaterless它们之间的关系,则矢量时钟将部分排序。 否则,它们是并发的。

DJIT +

DJIT +是矢量时钟的一种应用程序,用于纯净发生在数据竞争检测器之前。

我们记得以下向量时钟:

  • 每个锁$ m $释放$$ L_m =(t_0,\ ldots,t_n)$$
  • 在位置x $$ R_x =(t_0,\ ldots,t_n)$$上读取的最后一个内存
  • 在位置x $$ W_x =(t_0,\ ldots,t_n)$$上的最后一次内存写入
  • Goroutine向量时钟,$$ C_x =(t_0,\ ldots,t_n)$$

让我们看一个没有种族的例子:

竞赛检测器看到的每一行都代表一个事件。 首先,我们从goroutine 0写入位置$ x $,并在$ W_x $中将其记住。 之后,我们释放锁$ m $,并在$ L_m $中更新goroutine 0字段,这就是我们的锁释放向量时钟。 通过获取锁,我们可以按元素最大化$ L_m $和$ C_1 $的向量时钟,因为我们知道锁的锁定发生在锁释放之后。 我们执行写入goroutine 1,并检查我们自己的向量时钟是否同时与$ W_x $和$ R_x $并发。 严格要求,因此一切都很好。

与现在相同的示例,但是没有goroutine同步。 没有锁的锁和释放。 比较goroutine 1向量时钟时,$(0,8)$与最后一次写入$ W_x =(4,0)$并发。 因此,我们已经检测到数据竞争。 这是要理解的最重要概念,其余就是优化。

快速通道

快速通道引入了第一个优化。 有关完整的细节,我建议阅读原始论文,写得很好!

我们观察到以下属性。 如果写入时没有数据争用,则每个写入都是顺序的。 也就是说,记住最后写入的goroutine和该goroutine的逻辑时钟就足够了。 因此,我们创建了影子字,表示最后的存储器写入,逻辑时钟和goroutine ID。 格式@

对于阅读来说,这是个不同的故事。 只要读取和写入并严格排序,就可以同时进行多个读取,这是完全有效的。 因此,只要单个goroutine读取数据,我们就利用影子字读取表示形式,并且在并发读取场景中回退昂贵的全矢量时钟:

ThreadSanitizer v2

在FastTrack上进一步改进了线程清理程序。 而不是使用单独的$ R_x $和$ W_x $,我们为每个8字节的四字保持固定大小的影子字池。 也就是说,我们用部分影子词来估计整个矢量时钟。 在完整的影子词池中,我们随机逐出一个条目。

通过引入这种折衷,我们跟踪了速度和性能的假阴性。 我们固定的影子字池是内存映射的,因此与较昂贵的哈希图或可变大小的数组访问相比,允许廉价的访问以及附加和字节移位。

让我们来看一个例子。 每个影子字是8字节宽,由goroutine逻辑时钟,goroutine id,write / read标志和我们正在读/写的8byte字中的位置组成。

到目前为止一切都很好。 让我们进行另一项操作。

现在让我们介绍一下数据竞赛。 例程1的例程3向量时钟为5,小于写在池中的10@1影子字。 因此,我们可以确定发生了数据竞赛。 (我们假设每个goroutine的事件均按顺序到达,否则,我们无法确定goroutine 3的10@1条目大于还是小于goroutine 3的当前矢量时钟条目。这是由算法设计和实现所强制执行的)

摘要

作为本文的总结,我们介绍了逻辑时钟和矢量时钟的基础知识,以及如何在数据竞争检测器之前使用它们,并将其构建为go’s -race使用的ThreadSanitizer v2。

我们在算法设计中观察到了权衡取舍,它以较高的误报率换取了速度,但是禁止误报。 这个属性建立了信任,并且有了这种信任,我们当然知道,如果它向我们尖叫,我们就会有一场竞赛,而不是算法中一些奇怪的情况。 没有举足轻重的种族测试,只有真实的阳性报道。

虽然,保留在我这只是数据竞争检测器; 绕开它很容易。 例如,尽管在并发设置中存在严重错误,但以下代码仍将通过数据争用检测器:

 var Cnt int64 func Run(amount int) { for i := 0; i < amount; i++ { val := atomic.LoadInt64(&Cnt) val ++ // incrementing Cnt isn't atomic, we just load and store the value atomically. atomic.StoreInt64(&Cnt, val) } } 

参考文献

  • 滑梯
  • https://golang.org/doc/articles/race_detector.html
  • 种族探测器选项
  • https://github.com/google/sanitizers/wiki/ThreadSanitizerAlgorithm
  • Go记忆模型
  • Kavya Joshi谈“引擎盖下的种族”
  • https://blog.golang.org/race-detector
  • https://danluu.com/concurrency-bugs/
  • ThreadSanitizer —实践中的数据竞争检测Google论文
  • FastTrack:高效,精确的动态比赛检测
  • 适用于Linux内核和用户空间的AddressSanitizer / ThreadSanitizer。
  • DJIT +算法MultiRace:在多线程C ++程序中进行高效的实时数据竞争检测
  • 关于共享内存并行程序执行的事件排序的复杂性(Netzer,Miller,1990年)