# Race Detector
## go race detector

基于[ThreadSanitizer runtime library](https://github.com/google/sanitizers)sh实现.

### 怎么应用?

```
$ 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                 |


## 算法

算法伪代码:

```python
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
```


```python
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         |