Reading Papers - Data Race Detection
# Happens-Before Tracking
# Lockset
# SOSP'97 - Eraser
Eraser 通过检测程序的所有内存访问是否遵循某个事先约定的 locking discipline 来判断是否存在潜在的 data race 。
SOSP'97 - Eraser - A Dynamic Data Race Detector for Multi-Threaded Programs
Taxonomy : lockset / dynamic race detection
Tag : lockset
# Lockset 算法
对于每个共享变量 ,Lockset 算法维护 的 candidate lock set ,即曾经保护过对 的访问的所有锁的集合,记为 。
设 表示线程 当前持有的所有锁,则使用 naive locking discipline 的 Lockset 算法如下:
每当一个新的共享变量 被初始化时,令 为程序中所有锁的全集。
每当线程 访问 时,令 。该过程称为 lockset refinement 。
如果出现 的情况,则发出警告。
naive discipline 的约束条件过于严格,例如以下三种实践中常见的情况均不满足该约束:
在程序的初始化阶段,可能还未产生并发执行,此时共享变量的访问通常是无锁的。
一些共享变量在初始化之后就是 read-only 的,可以安全地被无锁访问。
对于 n reader / 1 writer 的情况,通常会使用 read-write lock 来保护共享内存访问。
对于第一种情况,Eraser 尝试将 lockset refinement 推迟至初始化阶段完成之后:当某个共享变量被第二个线程访问时,Eraser 判定该变量已完成初始化。如果一直是同一个线程在读写该变量,则对应的 lockset 不会被更新。
对于第二种情况,Eraser 仅对那些会被复数个线程改写的共享变量发出警告。
对于第三种情况,Eraser 使用 extended locking discipline 。设 表示线程 当前持有的所有锁, 表示线程 当前持有的所有 write lock ,则算法的 lockset refinement 变为:
对于线程 对 的每次读操作,令 。
对于线程 对 的每次写操作,令 。
# Eraser 实现
Eraser 将所有全局变量以及堆区中的所有变量视为共享内存。
为了维护 ,Eraser 需要插桩锁的获取和释放、以及线程的创建和终结。
为了维护 ,Eraser 需要插桩所有的内存读写操作。对于动态分配的内存,Eraser 还需插桩所有对 allocator 的调用。
# Lockset 讨论
有时程序会用多把锁来保护某个共享变量,此时写操作必须持有所有锁,而读操作仅需持有其中一把(可能每次不同的)锁。对于这种情况,Lockset 算法会产生误报。
可以将 Lockset 放宽到仅对写操作更新 candidate lock set ,但这又会导致更多漏报。
可以使用更复杂的数据结构(sets of sets of locks),但这会引入过高的复杂性。
# Combination of Happens-before and Lockset
# PPoPP'03 - MultiRace
MultiRace 改进并综合利用 Djit 算法和 Lockset 算法,实现变量与对象粒度的 data race 检测。
PPoPP'03 - Efficient On-the-Fly Data Race Detection in Multithreaded C++ Programs
Taxonomy : happens-before / lockset / dynamic race detection
Tag : happens-before / lockset
MultiRace 只记录一部分共享变量访问操作,因而其负载比过去的工具要小几个数量级。
论文中仅讨论互斥锁和内存屏障,并认为其它的同步原语都可以用类似的方法处理。
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01