sanitizer_common: add Semaphore

[dvyukov]

Summary

Semaphore is a portable way to park/unpark threads.
The plan is to use it to implement a portable blocking
mutex in subsequent changes. Semaphore can also be used
to efficiently wait for other things (e.g. we currently
spin to synchronize thread creation and start).

[dvyukov]

I've separated this from actual mutex implementation because this contains lots of OS-dependent code, which has higher risks of breaking things and being reverted. So I want to land and secure this first.

Looking into adding tests.

[dvyukov]

added test

[dvyukov]

FTR the mutex change that uses this semaphore is implemented here:
https://github.com/dvyukov/llvm-project/pull/3/files
(but it's a huge uncleaned change that I am slowly merging)

[vitalybuka]

compiler-rt/lib/sanitizer_common/sanitizer_mac.cpp

512

So we just spin here?
maybe TODO?

compiler-rt/lib/sanitizer_common/sanitizer_mutex.cpp

22–34

isn't this the same?

void Semaphore::Wait() {
  
  for(;;) {
    u32 count = atomic_load(&state_, memory_order_relaxed);
    if (count == 0) {
      FutexWait(&state_, 0);
      continue;
    }
    if (atomic_compare_exchange_weak(&state_, &count, count - 1,
                                     memory_order_acquire))
      break;
  };
}

[melver]

compiler-rt/lib/sanitizer_common/sanitizer_mutex.cpp

38

Do we care if count==0? My guess is we probably don't, but just checking.

compiler-rt/lib/sanitizer_common/sanitizer_mutex.h

77

Depending on how early they should be initialized, it might be worth it to make this a constexpr constructor. Probably would mean inline initializing state_ below.

compiler-rt/lib/tsan/go/buildgo.sh

31

s/ /\t/
if this should be consistent with rest of file.

[dvyukov]

addressed comments

compiler-rt/lib/sanitizer_common/sanitizer_mutex.cpp

22–34

It's subtly different.
atomic_compare_exchange returns the current value of the variable on failure (in count).
In the current version of the code, we use that value and don't re-load the variable after atomic_compare_exchange failure. In your version we re-load after failure.
On stress benchmarks for lock-free containers in makes 2x difference in overall performance. Here it does not matter much because we block/unblock threads anyway (slow). But I prefer to write it in the canonical way w/o unnecessary pessimization.

38

Added CHECK_NE(count, 0). Callers should not increment by 0.

[dvyukov]

Addressed all comments and uploaded a new version.

[hans]

compiler-rt/lib/sanitizer_common/sanitizer_win.cpp

817

This adds a dependency on API-MS-Win-Core-Synch-l1-2-0.dll, which according to https://docs.microsoft.com/en-us/windows/win32/api/synchapi/nf-synchapi-waitonaddress is only available on Windows 8 and later.

This is a problem for Chrome, which still supports Windows 7.

Is there some way this could be done without depending on a new API?

See https://bugs.chromium.org/p/chromium/issues/detail?id=1236586

[hans]

compiler-rt/lib/sanitizer_common/sanitizer_win.cpp

817

Actually, Reid pointed out to me that I'm wrong about shipping Chrome/ASan builds anywhere outside our own testing infrastructure, in which case this is not a problem.

[dvyukov]

compiler-rt/lib/sanitizer_common/sanitizer_win.cpp

817

Does Chrome need to support Windows 7 _with_ TSAN? I assume TSAN build is only used by few developers and on bots.

[hans]

compiler-rt/lib/sanitizer_common/sanitizer_win.cpp

817

I thought we shipped our ASan builds to some small subset of users, but it turns out I was mistaken. Sorry for the noise.

[efriedma]

There's a bug report https://github.com/llvm/llvm-project/issues/63786 mentioning Windows 7; I guess it's the same WaitOnAddress thing discussed previously? Maybe someone can reply on the bug report.

compiler-rt/lib/sanitizer_common/CMakeLists.txt

set(SANITIZER_SOURCES_NOTERMINATION
   sanitizer_flags.cpp
   sanitizer_flag_parser.cpp
   sanitizer_fuchsia.cpp
   sanitizer_libc.cpp
   sanitizer_libignore.cpp
   sanitizer_linux.cpp
   sanitizer_linux_s390.cpp
   sanitizer_mac.cpp
+  sanitizer_mutex.cpp
   sanitizer_netbsd.cpp
   sanitizer_persistent_allocator.cpp
   sanitizer_platform_limits_freebsd.cpp
   sanitizer_platform_limits_linux.cpp
   sanitizer_platform_limits_netbsd.cpp
   sanitizer_platform_limits_posix.cpp
   sanitizer_platform_limits_solaris.cpp
   sanitizer_posix.cpp

compiler-rt/lib/sanitizer_common/sanitizer_fuchsia.cpp

 void SetAlternateSignalStack() {}
 void UnsetAlternateSignalStack() {}
 void InitTlsSize() {}
 
 bool SignalContext::IsStackOverflow() const { return false; }
 void SignalContext::DumpAllRegisters(void *context) { UNIMPLEMENTED(); }
 const char *SignalContext::Describe() const { UNIMPLEMENTED(); }
 
+void FutexWait(atomic_uint32_t *p, u32 cmp) {
+  zx_status_t status = _zx_futex_wait(reinterpret_cast<zx_futex_t *>(p), cmp,
+                                      ZX_HANDLE_INVALID, ZX_TIME_INFINITE);
+  if (status != ZX_ERR_BAD_STATE)  // Normal race.
+    CHECK_EQ(status, ZX_OK);
+}
+
+void FutexWake(atomic_uint32_t *p, u32 count) {
+  zx_status_t status = _zx_futex_wake(reinterpret_cast<zx_futex_t *>(p), count);
+  CHECK_EQ(status, ZX_OK);
+}
+
 enum MutexState : int { MtxUnlocked = 0, MtxLocked = 1, MtxSleeping = 2 };
 
 BlockingMutex::BlockingMutex() {
   // NOTE!  It's important that this use internal_memset, because plain
   // memset might be intercepted (e.g., actually be __asan_memset).
   // Defining this so the compiler initializes each field, e.g.:
   //   BlockingMutex::BlockingMutex() : BlockingMutex(LINKER_INITIALIZED) {}
   // might result in the compiler generating a call to memset, which would

compiler-rt/lib/sanitizer_common/sanitizer_linux.cpp

 
 char **GetEnviron() {
   char **argv, **envp;
   GetArgsAndEnv(&argv, &envp);
   return envp;
 }
 
 #if !SANITIZER_SOLARIS
+void FutexWait(atomic_uint32_t *p, u32 cmp) {
+#    if SANITIZER_FREEBSD
+  _umtx_op(p, UMTX_OP_WAIT_UINT, cmp, 0, 0);
+#    elif SANITIZER_NETBSD
+  sched_yield();   /* No userspace futex-like synchronization */
+#    else
+  internal_syscall(SYSCALL(futex), (uptr)p, FUTEX_WAIT_PRIVATE, cmp, 0, 0, 0);
+#    endif
+}
+
+void FutexWake(atomic_uint32_t *p, u32 count) {
+#    if SANITIZER_FREEBSD
+  _umtx_op(p_, UMTX_OP_WAKE, count, 0, 0);
+#    elif SANITIZER_NETBSD
+                   /* No userspace futex-like synchronization */
+#    else
+  internal_syscall(SYSCALL(futex), (uptr)p, FUTEX_WAKE_PRIVATE, count, 0, 0, 0);
+#    endif
+}
+
 enum { MtxUnlocked = 0, MtxLocked = 1, MtxSleeping = 2 };
 
 BlockingMutex::BlockingMutex() {
   internal_memset(this, 0, sizeof(*this));
 }
 
 void BlockingMutex::Lock() {
   CHECK_EQ(owner_, 0);

compiler-rt/lib/sanitizer_common/sanitizer_mac.cpp

if (malloc_num_zones > 1 && malloc_zones[0] != &sanitizer_zone) {
           malloc_zones[0] = &sanitizer_zone;
           break;
         }
       }
     }
   }
 }
 
+void FutexWait(atomic_uint32_t *p, u32 cmp) {
+  // FIXME: implement actual blocking.
+  sched_yield();
+}
+
+void FutexWake(atomic_uint32_t *p, u32 count) {}
+
 BlockingMutex::BlockingMutex() {
   internal_memset(this, 0, sizeof(*this));
 }
 
 void BlockingMutex::Lock() {
   CHECK(sizeof(OSSpinLock) <= sizeof(opaque_storage_));
   CHECK_EQ(OS_SPINLOCK_INIT, 0);
   CHECK_EQ(owner_, 0);

compiler-rt/lib/sanitizer_common/sanitizer_mutex.h

SpinMutex() {
     Init();
   }
 
  private:
   SpinMutex(const SpinMutex &) = delete;
   void operator=(const SpinMutex &) = delete;
 };
 
+// Semaphore provides an OS-dependent way to park/unpark threads.
+// The last thread returned from Wait can destroy the object
+// (destruction-safety).
+class Semaphore {
+ public:
+  constexpr Semaphore() {}
+  Semaphore(const Semaphore &) = delete;
+  void operator=(const Semaphore &) = delete;
+
+  void Wait();
+  void Post(u32 count = 1);
+
+ private:
+  atomic_uint32_t state_ = {0};
+};
+
+void FutexWait(atomic_uint32_t *p, u32 cmp);
+void FutexWake(atomic_uint32_t *p, u32 count);
+
 class MUTEX BlockingMutex {
  public:
   explicit constexpr BlockingMutex(LinkerInitialized)
       : opaque_storage_ {0, }, owner_ {0} {}
   BlockingMutex();
   void Lock() ACQUIRE();
   void Unlock() RELEASE();
 

compiler-rt/lib/sanitizer_common/sanitizer_mutex.cpp

+//===-- sanitizer_mutex.cpp -----------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is shared between AddressSanitizer and ThreadSanitizer
+// run-time libraries.
+//===----------------------------------------------------------------------===//
+
+#include "sanitizer_mutex.h"
+
+#include "sanitizer_common.h"
+
+namespace __sanitizer {
+
+void Semaphore::Wait() {
+  u32 count = atomic_load(&state_, memory_order_relaxed);
+  for (;;) {
+    if (count == 0) {
+      FutexWait(&state_, 0);
+      count = atomic_load(&state_, memory_order_relaxed);
+      continue;
+    }
+    if (atomic_compare_exchange_weak(&state_, &count, count - 1,
+                                     memory_order_acquire))
+      break;
+  }
+}
+
+void Semaphore::Post(u32 count) {
+  CHECK_NE(count, 0);
+  atomic_fetch_add(&state_, count, memory_order_release);
+  FutexWake(&state_, count);
+}
+
+}  // namespace __sanitizer

compiler-rt/lib/sanitizer_common/sanitizer_solaris.cpp

 }
 
 uptr internal_clock_gettime(__sanitizer_clockid_t clk_id, void *tp) {
   // FIXME: No internal variant.
   return clock_gettime(clk_id, (timespec *)tp);
 }
 
 // ----------------- sanitizer_common.h
+void FutexWait(atomic_uint32_t *p, u32 cmp) {
+  // FIXME: implement actual blocking.
+  sched_yield();
+}
+
+void FutexWake(atomic_uint32_t *p, u32 count) {}
+
 BlockingMutex::BlockingMutex() {
   CHECK(sizeof(mutex_t) <= sizeof(opaque_storage_));
   internal_memset(this, 0, sizeof(*this));
   CHECK_EQ(mutex_init((mutex_t *)&opaque_storage_, USYNC_THREAD, NULL), 0);
 }
 
 void BlockingMutex::Lock() {
   CHECK(sizeof(mutex_t) <= sizeof(opaque_storage_));

compiler-rt/lib/sanitizer_common/sanitizer_win.cpp

uptr GetRSS() {
   if (!GetProcessMemoryInfo(GetCurrentProcess(), &counters, sizeof(counters)))
     return 0;
   return counters.WorkingSetSize;
 }
 
 void *internal_start_thread(void *(*func)(void *arg), void *arg) { return 0; }
 void internal_join_thread(void *th) { }
 
+void FutexWait(atomic_uint32_t *p, u32 cmp) {
+  WaitOnAddress(p, &cmp, sizeof(cmp), INFINITE);
+}
+
+void FutexWake(atomic_uint32_t *p, u32 count) {
+  if (count == 1)
+    WakeByAddressSingle(p);
+  else
+    WakeByAddressAll(p);
+}
+
 // ---------------------- BlockingMutex ---------------- {{{1
 
 BlockingMutex::BlockingMutex() {
   CHECK(sizeof(SRWLOCK) <= sizeof(opaque_storage_));
   internal_memset(this, 0, sizeof(*this));
 }
 
 void BlockingMutex::Lock() {

compiler-rt/lib/sanitizer_common/tests/sanitizer_mutex_test.cpp

TEST(SanitizerCommon, BlockingMutex) {
   pthread_t threads[kThreads];
   for (int i = 0; i < kThreads; i++)
     PTHREAD_CREATE(&threads[i], 0, lock_thread<BlockingMutex>, &data);
   for (int i = 0; i < kThreads; i++)
     PTHREAD_JOIN(threads[i], 0);
   check_locked(mtx);
 }
 
+struct SemaphoreData {
+  Semaphore *sem;
+  bool done;
+};
+
+void *SemaphoreThread(void *arg) {
+  auto data = static_cast<SemaphoreData *>(arg);
+  data->sem->Wait();
+  data->done = true;
+  return nullptr;
+}
+
+TEST(SanitizerCommon, Semaphore) {
+  Semaphore sem;
+  sem.Post(1);
+  sem.Wait();
+  sem.Post(3);
+  sem.Wait();
+  sem.Wait();
+  sem.Wait();
+
+  SemaphoreData data = {&sem, false};
+  pthread_t thread;
+  PTHREAD_CREATE(&thread, nullptr, SemaphoreThread, &data);
+  sleep(1);
+  CHECK(!data.done);
+  sem.Post(1);
+  PTHREAD_JOIN(thread, nullptr);
+}
+
 }  // namespace __sanitizer

compiler-rt/lib/tsan/go/build.bat

type ^
   ..\..\sanitizer_common\sanitizer_deadlock_detector1.cpp ^
   ..\..\sanitizer_common\sanitizer_stackdepot.cpp ^
   ..\..\sanitizer_common\sanitizer_persistent_allocator.cpp ^
   ..\..\sanitizer_common\sanitizer_flag_parser.cpp ^
   ..\..\sanitizer_common\sanitizer_symbolizer.cpp ^
   ..\..\sanitizer_common\sanitizer_termination.cpp ^
   ..\..\sanitizer_common\sanitizer_file.cpp ^
   ..\..\sanitizer_common\sanitizer_symbolizer_report.cpp ^
+  ..\..\sanitizer_common\sanitizer_mutex.cpp ^
   ..\rtl\tsan_external.cpp ^
   > gotsan.cpp
 
 gcc ^
   -c ^
   -o race_windows_amd64.syso ^
   gotsan.cpp ^
   -I..\rtl ^

compiler-rt/lib/tsan/go/buildgo.sh

SRCS="
   ../../sanitizer_common/sanitizer_allocator.cpp
   ../../sanitizer_common/sanitizer_common.cpp
   ../../sanitizer_common/sanitizer_common_libcdep.cpp
   ../../sanitizer_common/sanitizer_deadlock_detector2.cpp
   ../../sanitizer_common/sanitizer_file.cpp
   ../../sanitizer_common/sanitizer_flag_parser.cpp
   ../../sanitizer_common/sanitizer_flags.cpp
   ../../sanitizer_common/sanitizer_libc.cpp
+  ../../sanitizer_common/sanitizer_mutex.cpp
   ../../sanitizer_common/sanitizer_persistent_allocator.cpp
   ../../sanitizer_common/sanitizer_printf.cpp
   ../../sanitizer_common/sanitizer_suppressions.cpp
   ../../sanitizer_common/sanitizer_thread_registry.cpp
   ../../sanitizer_common/sanitizer_stackdepot.cpp
   ../../sanitizer_common/sanitizer_stacktrace.cpp
   ../../sanitizer_common/sanitizer_symbolizer.cpp
   ../../sanitizer_common/sanitizer_symbolizer_report.cpp