The first part of the post is an exploration of the Go -race flag, and it’s connection with Thread Sanitizer. Later chapter shows how the race detector was added to a selected Go project.

This post was originally created as a project for a university course. It does not explain the basics of the algorithm, which was already presented and focuses on the real-world implementation.

Concurrency in Go

The Go programming language has concurrency embedded deep in the language specification itself and tries to treat concurrent code as first-class citizen. It is inherently visible in the following snippet.

package main

import "fmt"
import "time"

func main() {
    go compute(10)
    go compute(20)
    
    compute(40)
}

func compute(iterations int) {
    for i := 0; i < iterations; i++ {
        fmt.Printf("Computing %d/%d\n", i, iterations)
        time.Sleep(time.Second)
    }
}

The go keyword is dispatching the function concurrently almost as ergonomicaly as running the function synchronously. While this may look like just a fancy syntactic sugar to avoid working with OS threads, the reality is a bit more complex. Go works with a concept of goroutines which are abstraction above system threads with a custom scheduler. In reality, the Go program spawns a fix number of system threads (primarily based on available CPU cores) and assigns goroutines to them dynamically. This allows the runtime to have better control over the running code.

Another construct linked with concurrency in Go is channel. It is also a key part of the language specification with a special syntax and keyword chan.

Channels and goroutines are two concepts that differentiate Go from other languages in terms of concurrency. They make writing concurrent code fairly easy in Go. However, at the same time, they also make it quite easy to create a data race condition. Luckily, the official Go toolchain contains an option to build the executable with race detector embedded in the runtime.

The Go Race Detector

Let’s start with a simple snippet to show it in action before diving into the technicalities:

// main.go
package main

import (
	"fmt"
)

func main() {
	var result = 0

	go func() {
		result += 1
	}()

	result += 2
	fmt.Println(result)
}

Will the printed number be two or three? Nobody knows, we have a data race.

# usual compilation and run
$ go run main.go 
2

# compilation with embedded race detector
$ go run -race main.go
==================
WARNING: DATA RACE
Read at 0x00c000010118 by goroutine 7:
  main.main.func1()
      /build/main.go:11 +0x2c

Previous write at 0x00c000010118 by main goroutine:
  main.main()
      /build/main.go:14 +0xb0

Goroutine 7 (running) created at:
  main.main()
      /build/main.go:10 +0x98
==================
2
Found 1 data race(s)
exit status 66

Great, the embedded race detector caught the issue and even provided relatively helpful comments. The program was directly run by go run -race, but it could be similarly compiled and executed with go build -race main.go -o race && ./race.

How does it work?

Quick peak into relevant Go sources reveals that Go is in fact using ThreadSanitizer from LLVM project.

ThreadSanitizer

ThreadSanitizer is now part of the LLVM toolset, but historically it resided in github.com/google/sanitizers, which is still linked by a lot of materials using the sanitizers. Glimpsing over the relevant documentation for the tool, it is described as “ThreadSanitizer (aka TSan) is a data race detector for C/C++.” Next section will explore the TSan as is and later dive into how Go actually uses it.

ThreadSanitizer Algorithm

This section is mostly based on ThreadSanitizerAlgorithm project wiki with references to the actual source code as of 8b25820.

ThreadSanitizer uses happens-before algorithm to detect races as they occur.

Before elaborating on the implementation, it is necessary to point out that ThreadSanitizer can detect many data race bugs, but it is also designed to be reasonably fast (yet still with non-negligible performance penalty). However, there is one compromise, it may detect the issues in runtime, but there is no guarantee that it will. This can be mostly attributed to memory limitations and also the fact that sometimes the algorithm itself may miss a data race due to asynchronous manipulation of internal structures by design, because synchronization would impose significant performance penalty.

Intuitively, the algorithm works by storing last read/write clock time for each 64-bit word for up to N threads in memory and centrally storing the mutexes and their clocks. Based on the locks/unlocks, it updates the clock for each thread, which is stored in thread-local variable. On each memory access, the clock times of the 64-bit word is checked with the thread’s own clock time. Depending on the result, it detects unordered manipulation and reports races. It also stores a ring buffer of memory manipulation events to back-reference in case of a detected race to do best-effort in reporting the offending functions and lines.

As usual, the reality is a bit muddier. The next sections will try to describe selected parts of the TSan in a bit more detail.

Shadow State

The central and most memory costly part of the algorithm is “Shadow State”, which directly maps each 8-byte word in memory to N 8-byte 4-byte “Shadow Words”. This direct mapping is one of the key aspects of TSan. It allows O(1) access to the shadow state, which is checked on hot-path for each memory manipulation. Another property of the direct mapping is that there is no need for synchronization, as the Shadow Words are swapped atomically in-place.

History sidetrack

TSan is still a developing tool, but the documentation for it is mainly not. On the internet there are plenty of sources describing TSan as 8-byte to 8-byte mapping which is no longer (as of 2021) true. It evolved to TSan v3 and now uses 4-byte “Shadow Words”. I have discovered this after looking through source codes, seeing the following type declaration and wondering what I am missing with that u32 union. However, short exploration of git blame for the exact line of code provided answers in form of commit b332134. I have confirmed it later in Go sources that they are in fact compiling against TSan v3.

// ... (definition of parts word)
union {
    Parts part_;
    u32 raw_;
};

In the lowest setting the TSan would “allocate” two 32-bit “Shadow Words” per each 8-bytes of memory (effectively 1:1 mapping). The Shadow Word count is configurable. Naturally, increasing the count bloats the memory usage of TSan significantly, but may be more effective in catching race bugs. When the single memory is accessed by more threads concurrently than available Shadow Words, some accesses are missed.

Each 4-byte shadow word is divided in the following way:

struct Parts {
    u8 access_; // access type (which bits were accessed) (8-bits)
    Sid sid_; // slot id (8-bits)
    u16 epoch_ : kEpochBits; // epoch at the time of access (14-bits)
    u16 is_read_ : 1; // read only flag (1-bit)
    u16 is_atomic_ : 1; // atomicity flag (1-bit)
};

The first part, access_ specifies which part of the 8-byte memory were accessed by encoding it in an 8-bit bitmap. There is also a special value kFreeAccess set as 0x81 (in binary 10000001), which flags freed memory. sid_ and epoch_ identifies which thread (via slot id) and at which thread time (epoch) the memory was accessed. Last two bits, is_read_ and is_atomic_ are bit flags. Together they form 32-bit long Shadow Word.

Threads

TSan has multiple places in which data about threads are kept. Firstly, there is a global storage of Threads, which is shared with other sanitizers in LLVM. However, as you seen in Parts struct, there is some reference called sid_. This is slot ID, which is an index in an array of slots, kept as a global variable. Each started thread is assigned a slot with a given ID, which is then used to reference it during race-detection. There is a limited number of slots – 256 (8-bit sid), when there are more threads, the slots are reused in cooperation with a global thread queue. Lastly, each thread has a ThreadState struct, which is referenced in a slot and can be accessed by thread-local storage.

Key attribute stored in ThreadState is clock of type VectorClock, effectively array of 256 clocks, indexed by slot ID. The number stored for each slot ID is called epoch and it is u16 limited to 14-bits (14-bit epoch_ in Parts).

Epoch

As said before, the epoch is 14-bit integer. Threads and “Sync variables” (mainly mutexes) store their own array of epochs indexed by slot ID. Each Shadow Word then stores a combination of slot ID and epoch. When a thread manipulates with memory, it will extract the epoch based on slot ID from its vector clock and compare it to the epoch stored in the Shadow Word. If we oversimplify a bit, when the thread epoch is lower than epoch in Shadow Word, we have a potential race bug. Naturally, there are many other checks on the way (R/W, access from the same thread, etc.).

The epoch changes always root from the thread vector clock. All the other epochs are synchronized from them. When a mutex is unlocked, apart from synchronizing the thread clock with the mutex, the thread epoch is incremented. Incrementing thread epoch means that the epoch in the thread’s vector clock on its own slot id is incremented.

There are a few synchronizing functions Acquire, Release, ReleaseStore and their combinations. Acquire will synchronize the thread clock with another VectorClock as follows:

for (uptr i = 0; i < kThreadSlotCount; i++)
    clk_[i] = max(clk_[i], src->clk_[i]);

The Release function is a reverse to Acquire, meaning it synchronizes the mutex clock with a thread clock. Lastly, ReleaseStore just copies the whole clock from the thread clock to the mutex clock.

Epoch is a 14-bit integer, which will eventually (i.e., after 16 384 unlocks) overflow. The overflow situation is quite nasty because it makes all the checks and assumptions incorrect. To overcome this, the epoch counter will never overflow, but in certain cases it is checked if any clock is about to overflow. If that is the case, TSan will basically reset all clocks, increment global epoch counter and start from zero.

Check for races

Previous chapters describe some parts of the TSan, now let’s look into the CheckRaces implementation. I have slightly modified it (mainly added comments) to make it as much readable as possible. The goal of this function is to identify data races and on the way store the new Shadow Word representing the current access.

bool CheckRaces(ThreadState* thr, RawShadow* shadow_mem, Shadow cur,
                int unused0, int unused1, AccessType typ) {
  bool stored = false;
  
  // iterate over all the N shadow words
  for (uptr idx = 0; idx < kShadowCnt; idx++) {
    // load the shadow word
    RawShadow* sp = &shadow_mem[idx];
    Shadow old(LoadShadow(sp));
    
    // check for empty shadow word
    if (LIKELY(old.raw() == Shadow::kEmpty)) {
      // we encountered empty shadow word.
      // next ones cannot be initialized yet,
      // -> no races detected
      
      // check if we want to store and if we stored already
      if (!(typ & kAccessCheckOnly) && !stored)
        StoreShadow(sp, cur.raw());
      return false;
    }
    
    // check if the access bit-map overlaps with the shadow word one
    if (LIKELY(!(cur.access() & old.access())))
      continue;
      
    // check if we have not encountered our own previous access
    if (LIKELY(cur.sid() == old.sid())) {
      if (!(typ & kAccessCheckOnly) &&
          LIKELY(cur.access() == old.access() && old.IsRWWeakerOrEqual(typ))) {
        StoreShadow(sp, cur.raw());
        stored = true;
      }
      continue;
    }
    
    // check if the access is relevant 
    if (LIKELY(old.IsBothReadsOrAtomic(typ)))
      continue;
      
    // check our clock for given sid with epoch in the shadow word
    if (LIKELY(thr->clock.Get(old.sid()) >= old.epoch()))
      continue;
     
    
    DoReportRace(thr, shadow_mem, cur, old, typ);
    return true;
  }
  
  // We did not find any races and had already stored
  // the current access info, so we are done.
  if (LIKELY(stored))
    return false;
  
  // Choose a random candidate slot and replace it.
  uptr index =
      atomic_load_relaxed(&thr->trace_pos) / sizeof(Event) % kShadowCnt;
  StoreShadow(&shadow_mem[index], cur.raw());
  return false;
}

The function is not short, but it gives a great overview of how the races are detected and what checks need to be done on the way.

There is much more…

There is much more to the nuances of TSan. Not to go into detail, I will just mention some of them:

  • A significant part of TSan is determining and keeping track of what memory was accessed by whom to provide relevant reporting. The history reconstruction is not trivial.
  • TSan has also an ability to detect deadlocks.
  • The source code is very performance optimized. There are a lot of bitwise operations, special macros to advise the compiler which path is more likely to happen, optimizations to have relevant data on single cache-line and more.
  • Process forks are also a thing that can occur and the TSan needs to handle.
  • On epoch overflow, the reset is not synchronized with the memory access (it would be slow to synchronize on each memory access). This means that TSan needs to handle a situation when this memory access leaves bogus value in Shadow State.
  • TSan can take advantage of vectorization on modern CPUs. There is a vectorized alternative for many functions. This post uses the non-vectorized variants, as they are easier to understand without knowledge of the CPU instructions.

Go-TSan instrumentation

The Go language uses pre-build binaries for TSan, which can be found in src/runtime/race as .syso files. Importantly, they contain extern C bindings from tsan_go.cpp. The extern C clause ensures that the function labels in the pre-compiled files will be the same as in source code and Go can link to them. This is done through fair number of assembly files, similarly to this:

TEXT	runtime·raceread<ABIInternal>(SB), NOSPLIT, $0-8
	MOVQ	AX, RARG1
	MOVQ	(SP), RARG2
	// void __tsan_read(ThreadState *thr, void *addr, void *pc);
	MOVQ	$__tsan_read(SB), AX
	JMP	racecalladdr<>(SB)
	
// func runtime·RaceRead(addr uintptr)
TEXT	runtime·RaceRead(SB), NOSPLIT, $0-8
	// This needs to be a tail call, because raceread reads caller pc.
	JMP	runtime·raceread(SB)

Later this is brought to Go in runtime with just a function declaration:

func RaceRead(addr unsafe.Pointer)

Many of the functions are later linked to src/internal/race to be used by standard library, for example in mutex handling:

func (m *Mutex) Lock() {
    // Fast path: grab unlocked mutex.
    if atomic.CompareAndSwapInt32(&m.state, 0, mutexLocked) {
        // [compile-time constant]
        if race.Enabled {
            // [transitive call to Acquire() in TSan through __tsan_acquire()]
            race.Acquire(unsafe.Pointer(m))
        }
        return
    }
    // Slow path (outlined so that the fast path can be inlined)
    m.lockSlow()
}

This approach is used through the standard libraries to instrument calls relevant to thread sanitizer mostly from sync/* libraries. All the calls exist in runtime bindings and also in the runtime/race library.

Lastly, all the memory accesses need to be instrumented. The compiler calls internally instrument2() method for each memory access, which injects relevant instrumentation similar to the following:

func (s *state) load(t *types.Type, src *ssa.Value) *ssa.Value {
	s.instrumentFields(t, src, instrumentRead)
	return s.rawLoad(t, src)
}

To show how the compiled instrumentation works, I have compiled following function incr with -race flag.

//go:nosplit
func incr(n *int) {
    *n += 1
}

Why the //go:nosplit?

Because incr() with instrumentation is calling other functions, the compiler would also inject checks for stack size (and potentionally grow it). The //go:nosplit disables this behavior. Basically telling the compiler “trust me; I will not exceed the allocated stack in this function”. Naturally, this could be a problem when running with the race detector, but the decompiled function is cleaner for demonstration purposes.

Later I decompiled it in Ghidra, which produced the following C code (after minor cleanup).

void main::main.main.func1(int *n)
{
    runtime::runtime.racefuncenter(...);
    runtime::runtime.raceread();
    runtime::runtime.racewrite();
    *n += 1
    runtime::runtime.racefuncexit();
}

Practical use of Go Race detector

I have shown some basic examples previously, but one of the big advantages of Go integrations is that it is very simple to run tests with race detector enabled, go test -race ./.... It is advised to run the tests multiple times with -race for example as go test -race -count 100 ./.... Provided that the codebase has some tests to exercise the potential race bugs, it is a straightforward way to catch issues.

For some practical example, I have chosen to use one of my projects codeberg.org/oidq/s-ingress. It is a simple Kubernetes Ingress controller implementation in pure Go. The concurrency model is not a rocket science here, but still, in one of the first versions, I had an issue with it crashing due to race-condition bugs.

Conceptually, the concurrency model is fairly simple, as shown in the diagram below:

Controller
Controller
Proxy
Proxy
Request Handler
Request Handler
Request Handler
Request Handler
Request Handler
Request Handler
Reconciler
Reconciler
Atomic Config Pointer
Atomic Config Pointer
Read
Read
Write
Write
Requests Reconcile
Requests R...
Sends Configuration
Sends Conf...
Controller State
Controller State
RW
RW
RW
RW
Object State
Object State
Object State
Object State
Object State
Object State
Links
Links
Atomic value
Atomic value
Mutex
Mutex
Goroutine
Goroutine
Legend
LegendText is not SVG - cannot display
Simplified diagram of memory access

My main point of concern is a race between Controller and Reconciler goroutines. They access multiple objects guarded by multiple mutexes. Proxy and Request Handlers use an atomic pointer to otherwise static configuration data, so it should not be problematic.

The codebase has a small number of unit tests and E2E tests. Running existing unit tests with -race -count 100 was simple and yielded no issues. However, E2E requires a bit more setup, because the whole container must be compiled with -race.

E2E Tests

One downside of race detection in Go (apart from performance) is that the program needs to be compiled with CGO_ENABLED, which is not possible to then easily use in scratch containers. The solution was to create a separate build process for this testing which would be built with race detection enabled.

Apart from running other E2E tests against the ingress controller instance with race detector compiled in, I have decided to add a test, which will try to provoke the race condition by modifying multiple objects concurrently. The changes still need to go through K8s API, so the control here is minimal, but should be enough. After running all the E2E tests, there also needs to be a check to verify that no race has occurred in the ingress. Because the Ingress controller is running in a completely separate environment than the test suits, the easiest way was to just check the logs. The setup was a bit tedious and required some tweaks to the testing setup, but it is working in commit bbfc46e7b4.

The initial run of the test targeted and parallel reconciliation of ConfigMap, Ingress and IngressClasses reported an issue:

WARNING: DATA RACE
Read at 0x00c0001eeb08 by goroutine 178:
  codeberg.org/oidq/s-ingress/pkg/controller.(*IngressController).Reconcile()
      /app/pkg/controller/reconcile.go:52 +0x6c
  ...

Previous write at 0x00c0001eeb08 by goroutine 164:
  codeberg.org/oidq/s-ingress/pkg/controller.(*IngressController).updateConfig()
      /app/pkg/controller/converter.go:130 +0x70
  ...

Goroutine 178 (running) created at:
  .../controller.(*Controller[go.shape.struct { k8s.io/apimachinery/pkg/types.NamespacedName }]).Start.func1()
      .../controller-runtime@v0.23.0/pkg/internal/controller/controller.go:309 +0x2d4

Goroutine 164 (running) created at:
  sync.(*WaitGroup).Go()
      /usr/local/go/src/sync/waitgroup.go:238 +0x6c
  main.main()
     /app/cmd/main.go:88 +0xd14

I was able to identify and fix the issue in commit 9964adbd15. Looking at the commit, it is fairly obvious what was the issue. There was unguarded access to a shared attribute hiding in plain sight.

Eventually, I would like to add some more tests to the suite, but even this test makes me a bit more confident, that the handling in controller/ is okay. I am quite happy to see that it had not found any other significant data race issue in the controller implementation.

Conclusion

I found it interesting to see how this kind of runtime check is implemented real-world battle-tested analyzer. While I may not use the hours spent staring into the source code of TSan anytime soon, it was surely an interesting journey.

If you have read this to the end, I sure hope you have also learned something new or at least enjoyed it.