TOCS|Concurrency|Eraser

Race Condition（竞争）指多线程同时访问一个资源时，由于访问顺序不同，导致的结果不同。这种并发性bug经常难以复现，又被称为海森bug（测不准）。Eraser，用于检测这种情况。翻译过程中附带重构。

总结一下，这个Eraser就是用一个迭代的方式，维护每次内存被访问时，使用锁的交集。如果交集为空，那么说明没有锁能保证每次访问时都被使用，因此就可能发生Data Race。一个亮点在于，Eraser可以直接通过机器码插入到源程序，而无需插入源代码中。

原作: ACM Transactions on Computer Systems, Vol. 15, No. 4, November 1997 引用: http://cseweb.ucsd.edu/~savage/papers/Tocs97.pdf 译者：朝闻君

Eraser: A Dynamic Data Race Detector for Multithreaded Programs

摘要

多线程编程复杂容易出错，很容易造成data race，却难以定位。

Eraser，可以在基于锁的程序中通过监控共享内存的引用，核查锁的行为一致性，动态检测出data race。并且Eraser可以对二进制机器码修改，直接插入原程序。

关键词：二进制机器码修改，多线程，竞争检测。

LOCKSET 算法

初始算法

如果不同线程在用不同的锁保护同一个共享变量，那么就有可能有两个线程同时访问一个共享变量。

强制共享变量必须被一组特定的锁保护。Eraser监控每次读写，来观测程序是否遵循这个规范。

由于Eraser没有办法知道锁的目的，因此必须根据历史来获取锁的保护关系。

对于每个共享变量v，Eraser维护一个候选锁集合C(v)，其中存放所有保护过v的锁。

Lockset Refinement

初始版本

变量初始化时，C（v）为所有可能的锁的集合。

变量被访问时，C（v）<- C(v)

[公式]

当前线程的锁的集合。

显然，这个集合只会变小或者维持稳定。

终态：

所有的线程用一致的锁保护同一个资源（不动点）=> Refined

C（v）为空 => Inconsistent

检测到v没有被正确保护

改进规则

上面的规则太过于严格，有三种情况不会发生Race Condition，同时又违背了上面的规则。

• 初始化时 - 无锁
• 只读数据 - 无需锁
• 读写锁- 单写多读

初始化/只读

如果没有其他线程能引用时，那么没有必要把其他线程锁住。对于新分配的数据既是如此。

为了避免错误的警告，Eraser将候选集的refinement延迟到初始化完成之后再进行。然而确认初始化是否完成很困难，因此这个时间又被延迟到共享变量被第二个线程初次访问时。

如果共享变量始终仅由一个线程读写，那么refinement就始终不执行。

此外，对于只读对象，同样没有必要保护。通过只警告那些被多个线程写的共享变量，可以提供这样的支持。

完成上面逻辑的状态机

• 分配时，Virgin。
• 初始化完成时，Exclusive。
• 被其他线程写，Shared-Modified。
• 被其他线程读，Shared。

憨憨们可能会在初始化完成前就让其他线程访问，那属于自己作死，与Eraser无关。

读写锁

如果因为写而更新，则只保留那些处于写mode的锁。

这样读锁就会被筛去，因为他们事实上无法保护data race。

实现

Eraser实现在Alpha处理器上的Digital Unix OS中，使用ATOM [Srivastava and Eustace 1994]二进制修改系统。

Eraser将没有修改的二进制代码作为输入，产生功能一致的新的二进制代码，但是其中插入了Eraser runtime。

监测每个全局/堆上的load/store来维护C(v)（通过地址和栈指针的关系）

监测每次锁的acquire/release的调用以及线程的创建/终结，来维护线程持有的锁。

监测每个内存分配，来初始化C(v)，每个word都有可能成为共享变量。（这么麻烦，主要是因为在对二进制，而不是源代码做修改）

维护通过寄存器而不是栈指针所能访问的栈地址的集合。

race发生时，Eraser log到文件中，并报告行号，栈帧的traceback，线程ID，内存地址，访问方式，PC/RSP的值等等，从而定位问题代码。如果还不能发现，那么让Eraser log每次访问。

边界条件

存在一些误报，因为Eraser以标准C/C++的内存分配/lock作为监控对象。因此使用一些特殊的注解，可以让Eraser忽略这些误报

Memory Reuse

私有的内存分配器无法被监控

EraserReuse(address, size)

Primary Lock

私有的锁无法被监控

EraserReadLock(lock)
EraserReadUnlock(lock)
EraserWriteLock(lock)
EraserWriteUnlock(lock)

Begin Races

程序前编译器插入的代码，出了Data Race但是不会导致程序受影响。

EraserIgnoreOn( )
EraserIgnoreOff( )

性能

作者发现一般的开销来自于ATOM中每次监控都需要进行一次函数调用，但是升级到1996版本就能内联了。因此他直接认为性能没有很大影响，并且也不是程序主要的目的所在。

检测OS的问题很困难。

Systems that integrate thread and interrupt processing [Kleiman and Eykholt 1995] may have less trouble with this problem.