Here we provide a high-level description ofThreadSanitizer (version 2) algorithm.The tool is work-in-progress, so some details may change in future.This is the second version ofThreadSanitizer,the first (slow and deprecated) version can be foundhere.

ThreadSanitizer consists of two parts:instrumentation module and a run-time library.

We instrument every memory access in the program unless it can be provento be race-free or redundant.Memory accesses are simply prepended with a function call like__tsan_read4(addr).

Examples of race-free access:

• Reads from constant globals (including vtables).
• Accesses to memory that does not escape the current function (and therefore the current thread).

Examples of redundant accesses:

• Read that happens before a write to the same location.

Atomic memory accesses are instrumented using specialized__tsan_atomic_ callbacks.Reads from vtable pointer are instrumented using__tsan_vptr_update todeal withbenign vptr races.Function entry and exit are instrumented with__tsan_func_entry(caller_pc)and__tsan_func_exit.A call to__tsan_init is inserted before all initializers.

Shadow State isN Shadow Words (described below);N is one of 2, 4, 8 (configurable).Every aligned 8-byte word of application memory is mapped intoN Shadow Wordsusing direct address mapping (no memory accesses required to compute the shadow address).

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

One Shadow Word represents a single memory access to a subset of bytes withinthe 8-byte word of application memory.Therefore the Shadow State describesN different accessesto the corresponding application memory region.

The core of the algorithm is theState Machine,a function that updates the Shadow State on every memory access.

First,the thread's clock is incremented anda new Shadow Word that corresponds to the current memory access is created.Then the State Machine iterates over all Shadow Words stored in the Shadow State.If one of the old Shadow Words constitutes a race with the new Shadow Word, a warningmessage is printed.The new Shadow Word is inserted in place of an empty Shadow Word or in place of a Shadow Wordthat happened-before the new one.If no place for insertion is found, a random Shadow Word is evicted.

All accesses to Shadow Words are 64-bit atomic loads/stores,but otherwise no locking is involved.Even if two threads are modifying the same Shadow State at the same time,the Shadow State will remain consistent.There is tiny probability to miss a data race though.

Approximate pseudo code follows(for an exact algorithm see the code intsan_rtl.cc;we will update the pseudo code oncethe actual code is frozen).

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 nothingdef StoreIfNotYetStored(shadow_address, store_word):  *shadow_address = store_word  # Atomic  store_word = 0

ThreadSanitizer needs to report stack traces and other information forprevious accessesinvolved in a data race.LogEvent(tid, pc) (see above) stores the access event in a large thread-localcircular buffer for later recovery.TODO: add more detail.

Finding races and memory errors with compiler instrumentation