llvm / llvm/llvm-project

TSAN Internal Semaphore Fairness

Open
#177,529 0 comments 0 reactions 0 assignees View on GitHub
compiler-rt:tsan
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

The following contrived spin lock program stalls for extended periods (minutes, or possibly never finishes) when compiled and run with -fsanitize=thread. I believe this is due to [`__sanitizer::Semaphore`](https://github.com/llvm/llvm-project/blob/main/compiler-rt/lib/sanitizer_common/sanitizer_mutex.cpp#L31-L49) not being fair.

```c++
#include
#include
#include

class SpinLock {
std::atomic flag_{false};

public:
void lock() {
bool expected = false;
while (!flag_.compare_exchange_weak(expected, true,
std::memory_order_acquire,
std::memory_order_relaxed)) {
expected = false;
}
}

void unlock() {
flag_.store(false, std::memory_order_release);
}
};

static SpinLock spinlock;

void worker(int iterations) {
for (int i = 0; i < iterations; ++i) {
spinlock.lock();
spinlock.unlock();
}
}

int main(int argc, char* argv[]) {
const int ITERATIONS_PER_THREAD = (argc > 1) ? atoi(argv[1]) : 1000;
const int NUM_THREADS = (argc > 2) ? atoi(argv[2]) : 4;

std::vector threads;
for (int i = 0; i < NUM_THREADS; ++i) {
threads.emplace_back(worker, ITERATIONS_PER_THREAD);
}

return 0;
}
```

Running with sufficient iterations and threads (for example, 10000 iterations and 32 threads seems to his this quite often on both a Linux and Mac machine), the program appears to spin on the CPU, with the thread that owns the application Spinlock indefinitely waiting on TSAN's internal Mutex (Semaphore) as part of tsan_interface_atomic.cpp's implementation.

## Starved thread

```
Thread 10 (Thread 0x7fffef8f7700 (LWP 509989) "spinlock_test_c"):
#0 0x0000555555625e2a in __sanitizer::FutexWait (p=p@entry=0x7ffff7f77a10, cmp=cmp@entry=0) at /tmp/compiler-rt-20.1-20.1.0-0/lib/sanitizer_common/sanitizer_linux.cpp:806
#1 0x0000555555627462 in __sanitizer::Semaphore::Wait (this=this@entry=0x7ffff7f77a10) at /tmp/compiler-rt-20.1-20.1.0-0/lib/sanitizer_common/sanitizer_mutex.cpp:35
#2 0x00005555555e0cc4 in __sanitizer::Mutex::Lock (this=0x7ffff7f77a08) at /tmp/compiler-rt-20.1-20.1.0-0/lib/tsan/rtl/../../sanitizer_common/sanitizer_mutex.h:196
#3 __sanitizer::GenericScopedLock<__sanitizer::Mutex>::GenericScopedLock (mu=0x7ffff7f77a08, this=) at /tmp/compiler-rt-20.1-20.1.0-0/lib/tsan/rtl/../../sanitizer_common/sanitizer_mutex.h:383
#4 (anonymous namespace)::OpStore::Atomic (v=, a=0x555556a00960 "\001", mo=, pc=, thr=0x7fffef8f6f80) at /tmp/compiler-rt-20.1-20.1.0-0/lib/tsan/rtl/tsan_interface_atomic.cpp:319
#5 AtomicImpl<(anonymous namespace)::OpStore, unsigned char volatile*, unsigned char> (mo=) at /tmp/compiler-rt-20.1-20.1.0-0/lib/tsan/rtl/tsan_interface_atomic.cpp:529
#6 __tsan_atomic8_store (a=0x555556a00960 "\001", v=, mo=) at /tmp/compiler-rt-20.1-20.1.0-0/lib/tsan/rtl/tsan_interface_atomic.cpp:562
#7 0x000055555564ecee in std::__atomic_base::store (this=0x555556a00960 , __i=false, __m=std::memory_order::release) at /opt/rh/gcc-toolset-13/root/usr/lib/gcc/x86_64-redhat-linux/13/../../../../include/c++/13/bits/atomic_base.h:481
#8 std::atomic::store (this=0x555556a00960 , __i=false, __m=std::memory_order::release) at /opt/rh/gcc-toolset-13/root/usr/lib/gcc/x86_64-redhat-linux/13/../../../../include/c++/13/atomic:104
#9 0x000055555564dfbd in SpinLock::unlock (this=0x555556a00960 ) at spinlock_test.cpp:20
```

I noticed this while writing some benchmarks for TSAN, but not in any actual "real world" code. Although it's unfortunate, I'm not sure how realistic this severe starvation is in the "real world." I'm reporting this here to get initial feedback.

`__sanitizer::Semaphore` is in the critical path for all __tsan_* atomic ops, so changing it to be fair could possibly be too expensive, if this is not a realistically important scenario.

Contributor guide

Open the contributing guide

Research direction

Run the supplied spinlock_test.cpp reproducer with -fsanitize=thread, using high iteration and thread counts such as 10000 and 32. Read sanitizer_mutex.cpp around __sanitizer::Semaphore::Wait and tsan_interface_atomic.cpp around the OpStore path shown in the trace. Done means the starvation behavior is characterized and the selected solution is validated against this reproducer without unacceptable TSAN overhead.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
compilers, testing-qa
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
42/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.