A Race Detector Unfurled

Race detectors are seriously cool tools that make writing race-free concurrent code easy — they detect the ever so elusive race conditions in a program. The Go race detector is one such tool that ships with Go, thereby making the magic of race detection trivially accessible to you and me.

This talk will present the subtleties of race detection and explore how the Go race detector does it. We will delve into the race detector's use of vector clocks (from distributed systems!) to detect data races, including the implementation. Finally, we will touch upon the clever optimizations that make the tool practical for use in the real world.

Transcript

1. A Race Detector Unfurled kavya @kavya719
2. // Shared variable var count = 0 func incrementCount() { if count == 0 { count ++ } } func main() { // Spawn two “threads” go incrementCount() go incrementCount() } “g2” “g1” R <— 0 R <— 0 W —> 1 W —> 1 count = 2 R <— 0 W —> 1 R <— 1 !W count = 1 data races “when two+ threads concurrently access a shared memory location, at least one access is a write.” }
3. elusive
 have undefined consequences —> the language memory model says: within a goroutine —
 reads + writes are ordered with multiple goroutines —
 shared data must be synchronized by you.
 relevant
 easy to introduce in languages 
 like Go
4. read by goroutine 7 at incrementCount() created at main() race detectors …but how?
5. “…goroutines concurrently access a shared memory location, at least one access is a write.” ? determine “concurrent” memory accesses? can they be ordered by happens-before?
6. vector clocks means to establish happens-before ordering
7. var count = 0 func incrementCount() { mu.Lock() if count == 0 { count ++ } mu.Unlock() } func main() { go incrementCount() go incrementCount() } g2 g1
8. vector clocks means to establish happens-before ordering 0 1 lock(mu) 4 1 t1 = max(4, 0) t2 = max(0,1) g1 g2 0 0 g1 g2 0 0 g1 g2 1 0 read(count) 2 0 3 0 4 0 unlock(mu) lock(mu) write(count) 4 2 read(count) X Y
9. g1 3 0 4 0 write 4 1 g2 4 2 read X Y X ≺ Y ? (3, 0) < (4, 2) ? so yes.
10. X ≺ Y ? (2, 0) < (0, 1) ? no. Y ≺ X ? no. so, concurrent g1 0 0 1 0 2 0 read(count) write(count) X g2 0 0 1 0 2 0 Y
11. pure happens-before detection uses vector clocks to determine concurrent memory accesses.
12. go run -race to implement happens-before detection, need to: create vector clocks for goroutines
 …at goroutine creation
 update vector clocks based on memory access,
 synchronization events
 …when these events occur
 compare vector clocks to detect happens-before 
 relations.
 …when a memory access occurs
13. program spawn lock read race race detector state race detector state machine
14. program goroutine creation synchronizations memory accesses } go stdlib source
 (if race.Enabled blocks) } compiler instrumentation
 (the gc compiler only)
15. Is a C++ race-detection library. TSan implements the 
 happens-before race detection:
 creates, updates vector clocks keeps track of memory and 
 synchronization events compares vector clocks to 
 detect data races. threadsanitizer race detector
16. go incrementCount() struct ThreadState { ThreadClock clock; } func newproc1() { if race.Enabled { newg.racectx = racegostart(…) } ... } proc.go count == 0 raceread(…) by compiler instrumentation 1. data race with a previous access? 2. store information about this access 
 for future detections 0 0
17. stores information about memory accesses. 8-byte shadow word for an access: TID clock pos wr TID: accessor goroutine ID
 clock: scalar clock of accessor , optimized vector clock pos: offset, size in 8-byte word wr: IsWrite bit shadow state gx 3 pos wr gx gy 3 2 3 scalar clock, not full vector clock. Optimization
18. g1: count == 0 raceread(…) by compiler instrumentation g1: count++ racewrite(…) g2: count == 0 raceread(…) and check for race g1 1 0:8 0 1 0 g1 2 0:8 1 2 0 g2 1 0:8 0 0 1
19. race detection compare: <accessor’s vector clock, new shadow word> g2 1 0:8 0 0 1 “…when two+ threads concurrently access a shared memory location, at least one access is a write.” g1 2 0:8 1 with: each existing shadow word
20. race detection compare: <accessor’s vector clock, new shadow word> do the access locations overlap? are any of the accesses a write? are the TIDS different? are they concurrent (no happens-before)? existing shadow word’s clock: (2, ?) g2’s vector clock: (0, 1) g1 2 0:8 1 g2 1 0:8 0 0 1 ✓ ✓ ✓ ✓ with: each existing shadow word
21. do the access locations overlap? are any of the accesses a write? are the TIDS different? are they concurrent (no happens-before)? race detection g1 1 0:8 1 g2 0 0:8 0 compare (accessor’s threadState, new shadow word) with each existing shadow word: 0 0 RACE! ✓ ✓ ✓ ✓
22. g1 g2 0 0 g1 g2 0 0 g1 g2 1 0 2 0 3 0 unlock(mu) 3 1 lock(mu) g1 = max(3, 0) g2 = max(0,1) TSan must track synchronization events …to facilitate the “transfer” of the releaser’s vector clock to the acquirer. synchronization events
23. sync vars mu := sync.Mutex{} struct SyncVar { SyncClock clock; } contains a vector clock SyncClock mu.Unlock() 3 0 g1 g2 mu.Lock() max( SyncClock) 0 1
24. TSan can track your custom sync primitives too, via dynamic annotations!
 
 TSan tracks file descriptors, memory allocations etc. too a note (or two)…
25. @kavya719 speakerdeck.com/kavya719/a-race-detector-unfurled ThreadSanitizer 
 Original paper: research.google.com/pubs/archive/35604.pdf
 
 Optimizations similar to in FastTrack: https://users.soe.ucsc.edu/~cormac/papers/pldi09.pdf
 The source (lives in the LLVM repo):
 http://llvm.org/releases/download.html The Go compiler/ source https://github.com/golang/go
26. 8-byte shadow word for an access: TID clock pos wr TID: accessor goroutine ID
 clock: scalar clock of accessor , optimized vector clock pos: offset, size in 8-byte word wr: IsWrite bit directly-mapped: 0x7fffffffffff 0x7f0000000000 0x1fffffffffff 0x180000000000 application shadow Another Shadow State Optimization
27. N shadow cells per application word (8-bytes) gx read When shadow words are filled, evict one at random. Optimization clock_1 0:2 0 gx gy write clock_2 4:8 1 gy
28. evaluation “is it reliable?” “is it scalable?” program slowdown = 5x-15x memory usage = 5x-10x no false positives (only reports “real races”, but can be benign) can miss races! depends on execution trace 
 As of August 2015, 1200+ races in Google’s codebase, ~100 in the Go stdlib,
 100+ in Chromium,
 + LLVM, GCC, OpenSSL, WebRTC, Firefox
29. alternatives I. Static detectors analyze the program’s source code.
 • typically have to augment the source with race annotations (-) • single detection pass sufficient to determine all possible 
 races (+) • too many false positives to be practical (-)
 II. Lockset-based dynamic detectors uses an algorithm based on locks held
 • more performant than pure happens-before (+) • may not recognize synchronization via non-locks,
 like channels (would report as races) (-)
30. III. Hybrid dynamic detectors combines happens-before + locksets.
 (TSan v1, but it was hella unscalable)
 • “best of both worlds” (+) • false positives (-) • complicated to implement (-)
 
 

31. requirements I. Go specifics v1.1+ gc compiler gccgo does not support as per: https://gcc.gnu.org/ml/gcc-patches/2014-12/msg01828.html x86_64 required Linux, OSX, Windows II. TSan specifics LLVM Clang 3.2, gcc 4.8 x86_64 requires ASLR, so compile/ ld with -fPIE, -pie maps (using mmap but does not reserve) virtual address space; tools like top/ ulimit may not work as expected.
32. fun facts TSan maps (by mmap but does not reserve) tons of virtual address space; tools like top/ ulimit may not work as expected. need: gdb -ex 'set disable-randomization off' --args ./a.out
 due to ASLR requirement.
 
 Deadlock detection? Kernel TSan?
33. goroutine 1 obj.UpdateMe() mu.Lock() flag = true mu.Unlock() goroutine 2 mu.Lock() var f bool = flag mu.Unlock () if (f) { obj.UpdateMe() } { { a fun concurrency example