Race Detector

go race detector

基于ThreadSanitizer runtime librarysh实现.

怎么应用?

$ go test -race mypkg    // test the package
$ go run -race mysrc.go  // compile and run the program
$ go build -race mycmd   // build the command
$ go install -race mypkg // install the package

会在运行时打印争用日志.

开销?

• 编译时加入了特殊指令.

  • 每次访存都会多一个指令开销.

• 运行时

  • Every aligned 8-byte word of application memory is mapped into N Shadow Words using direct address mapping (no memory accesses required to compute the shadow address).

thread sanitizer

• https://github.com/google/sanitizers/wiki/ThreadSanitizerAlgorithm

• 核心数据结构

  • Shadow Word

• 核心算法

  • State Machine

    • 每一次访存都会更新状态机.

shadow word

Shadow Word is a 64-bit object that contains the following fields:

TID (Thread Id)	16 bits (configurable)
Scalar Clock	42 bits (configurable)
IsWrite	1 bit
Access Size (1, 2, 4 or 8)	2 bits
Address Offset (0..7)	3 bits

算法

算法伪代码:

def HandleMemoryAccess(addr, tid, is_write, size, pc):
  shadow_address = MapApplicationToShadow(addr)
  IncrementThreadClock(tid)
  LogEvent(tid, pc);
  new_shadow_word = {tid, CurrentClock(tid), is_write, size, addr & 7}
  store_word = new_shadow_word
  for i in 1..N:
    UpdateOneShadowState(shadow_address, i, new_shadow_word, store_word)
  if store_word:
    # Evict a random Shadow Word
    shadow_address[Random(N)] = store_word  # Atomic

def UpdateOneShadowState(shadow_address, i, new_shadow_word, store_word):
  idx = (i + new_shadow_word.offset) % N
  old_shadow_word = shadow_address[idx]  # Atomic
  if old_shadow_word == 0: # The old state is empty
    if store_word:
      StoreIfNotYetStored(shadow_address[idx], store_word)
    return
  if AccessedSameRegion(old_shadow_word, new_shadow_word):
    if SameThreads(old_shadow_word, new_shadow_word):
      TODO
    else:  # Different threads
      if not HappensBefore(old_shadow_word, new_shadow_word):
        ReportRace(old_shadow_word, new_shadow_word)
  elif AccessedIntersectingRegions(old_shadow_word, new_shadow_word):
    if not SameThreads(old_shadow_word, new_shadow_word)
      if not HappensBefore(old_shadow_word, new_shadow_word)
        ReportRace(old_shadow_word, new_shadow_word)
  else: # regions did not intersect
    pass # do nothing

def StoreIfNotYetStored(shadow_address, store_word):
  *shadow_address = store_word  # Atomic
  store_word = 0

源代码

参考 [[rdmisc/thread_sanitizer]]

历史

http://gcc.gnu.org/wiki/cauldron2012?action=AttachFile&do=get&target=kcc.pdf

v1

ThreadSanitizer v1

Based on Valgrind
Used since 2009
Slow (20x-300x slowdown)

• Still, found thousands races

• Also, faster than others Other race detectors for C/C++:

• Helgrind (Valgrind)

• Intel Parallel Inspector (PIN)

v2

ThreadSanitizer v2 overview

• Simple compile-time instrumentation

• Redesigned run-time library

  • Fully parallel

  • No expensive atomics/locks on fast path ○ Scales to huge apps

  • Predictable memory footprint

  • Informative reports

slowdown

Application	Tsan1	Tsan2	Tsan1/Tsan2
RPC benchmark	283x	8.5x	33x
Server app test	28x	2x	14x
String util test	30x	2.4x	13x