TSAN Internal Semaphore Fairness
- 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
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