Prevent Thread Exited/Joined events race

[krytarowski]

Summary

Add atomic verification to ensure that Thread is Joined after marking it
Finished.

It is required for NetBSD in order to prevent Thread Exited/Joined race,
that may occur when native system libpthread(3) cannot be reliably traced
in a way to guarantee that the mentioned events happen one after another.

This change fixes at least TSan and LSan on NetBSD.

Sponsored by <The NetBSD Foundation>

[krytarowski]

This change proposal is in the same time request for improvement.

check-tsan can give nice looking results like:

Testing Time: 48.84s
********************
Failing Tests (13):
    ThreadSanitizer-x86_64 :: deadlock_detector_stress_test.cc
    ThreadSanitizer-x86_64 :: dtls.c
    ThreadSanitizer-x86_64 :: exceptions.cc
    ThreadSanitizer-x86_64 :: ignore_lib5.cc
    ThreadSanitizer-x86_64 :: ignored-interceptors-mmap.cc
    ThreadSanitizer-x86_64 :: longjmp3.cc
    ThreadSanitizer-x86_64 :: longjmp4.cc
    ThreadSanitizer-x86_64 :: mutex_lock_destroyed.cc
    ThreadSanitizer-x86_64 :: signal_errno.cc
    ThreadSanitizer-x86_64 :: signal_malloc.cc
    ThreadSanitizer-x86_64 :: signal_sync2.cc
    ThreadSanitizer-x86_64 :: signal_thread.cc
    ThreadSanitizer-x86_64 :: vfork.cc

  Expected Passes    : 245
  Expected Failures  : 1
  Unsupported Tests  : 83
  Unexpected Failures: 13

On the other hand there still can happen this race... so something is suboptimal. Improper usage of atomic functions?

Failing Tests (43):
    ThreadSanitizer-Unit :: rtl/./TsanRtlTest-x86_64-Test/Posix.ThreadLocalAccesses
    ThreadSanitizer-Unit :: rtl/./TsanRtlTest-x86_64-Test/ThreadSanitizer.BasicMutex
    ThreadSanitizer-Unit :: rtl/./TsanRtlTest-x86_64-Test/ThreadSanitizer.BasicSpinMutex
    ThreadSanitizer-Unit :: rtl/./TsanRtlTest-x86_64-Test/ThreadSanitizer.BenignRaceOnVptr
    ThreadSanitizer-Unit :: rtl/./TsanRtlTest-x86_64-Test/ThreadSanitizer.FuncCall
    ThreadSanitizer-Unit :: rtl/./TsanRtlTest-x86_64-Test/ThreadSanitizer.HarmfulRaceOnVptr
    ThreadSanitizer-Unit :: rtl/./TsanRtlTest-x86_64-Test/ThreadSanitizer.LockedWriteThenRead
    ThreadSanitizer-Unit :: rtl/./TsanRtlTest-x86_64-Test/ThreadSanitizer.Memcpy
    ThreadSanitizer-Unit :: rtl/./TsanRtlTest-x86_64-Test/ThreadSanitizer.MemcpyRace2
    ThreadSanitizer-Unit :: rtl/./TsanRtlTest-x86_64-Test/ThreadSanitizer.MemcpyRace3
    ThreadSanitizer-Unit :: rtl/./TsanRtlTest-x86_64-Test/ThreadSanitizer.MemcpyStack
    ThreadSanitizer-Unit :: rtl/./TsanRtlTest-x86_64-Test/ThreadSanitizer.MemsetRace1
    ThreadSanitizer-Unit :: rtl/./TsanRtlTest-x86_64-Test/ThreadSanitizer.Mutex
    ThreadSanitizer-Unit :: rtl/./TsanRtlTest-x86_64-Test/ThreadSanitizer.RaceWithOffset
    ThreadSanitizer-Unit :: rtl/./TsanRtlTest-x86_64-Test/ThreadSanitizer.RaceWithOffset2
    ThreadSanitizer-Unit :: rtl/./TsanRtlTest-x86_64-Test/ThreadSanitizer.ReadReadNoRace
    ThreadSanitizer-Unit :: rtl/./TsanRtlTest-x86_64-Test/ThreadSanitizer.ReadWriteRace
    ThreadSanitizer-Unit :: rtl/./TsanRtlTest-x86_64-Test/ThreadSanitizer.ReportDeadThread
    ThreadSanitizer-Unit :: rtl/./TsanRtlTest-x86_64-Test/ThreadSanitizer.ReportRace
    ThreadSanitizer-Unit :: rtl/./TsanRtlTest-x86_64-Test/ThreadSanitizer.RwMutex
    ThreadSanitizer-Unit :: rtl/./TsanRtlTest-x86_64-Test/ThreadSanitizer.SimpleWrite
    ThreadSanitizer-Unit :: rtl/./TsanRtlTest-x86_64-Test/ThreadSanitizer.SimpleWriteWrite
    ThreadSanitizer-Unit :: rtl/./TsanRtlTest-x86_64-Test/ThreadSanitizer.StaticMutex
    ThreadSanitizer-Unit :: rtl/./TsanRtlTest-x86_64-Test/ThreadSanitizer.ThreadDetach1
    ThreadSanitizer-Unit :: rtl/./TsanRtlTest-x86_64-Test/ThreadSanitizer.ThreadSync
    ThreadSanitizer-Unit :: rtl/./TsanRtlTest-x86_64-Test/ThreadSanitizer.WriteReadRace
    ThreadSanitizer-Unit :: rtl/./TsanRtlTest-x86_64-Test/ThreadSanitizer.WriteThenLockedRead
    ThreadSanitizer-Unit :: unit/./TsanUnitTest-x86_64-Test/Mutex.Write
    ThreadSanitizer-x86_64 :: deadlock_detector_stress_test.cc
    ThreadSanitizer-x86_64 :: dtls.c
    ThreadSanitizer-x86_64 :: exceptions.cc
    ThreadSanitizer-x86_64 :: fd_tid_recycled.cc
    ThreadSanitizer-x86_64 :: ignore_lib5.cc
    ThreadSanitizer-x86_64 :: ignored-interceptors-mmap.cc
    ThreadSanitizer-x86_64 :: longjmp3.cc
    ThreadSanitizer-x86_64 :: longjmp4.cc
    ThreadSanitizer-x86_64 :: mutex_lock_destroyed.cc
    ThreadSanitizer-x86_64 :: signal_errno.cc
    ThreadSanitizer-x86_64 :: signal_malloc.cc
    ThreadSanitizer-x86_64 :: signal_sync2.cc
    ThreadSanitizer-x86_64 :: signal_thread.cc
    ThreadSanitizer-x86_64 :: vfork.cc

  Expected Passes    : 252
  Expected Failures  : 1
  Unsupported Tests  : 83
  Unexpected Failures: 43

[dvyukov]

lib/sanitizer_common/sanitizer_thread_registry.cc

95

This also needs to reset thread_destroyed because contexts are reused.

106

Now looking at the code more closely, I think we can contain this all inside of ThreadRegistry without changing public API and exposing more guts.

We could set thread_destroyed in ThreadRegistry::FinishThread (right after tctx->SetFinished()), and wait for the flag in ThreadRegistry::JoinThread (need to release the mutex around yield).
This looks like a cleaner solution and will fix all sanitizers at once.
Will this work for netbsd?

Sorry for not noticing it earlier.

190

we now generally use nullptr for pointers

[krytarowski]

lib/sanitizer_common/sanitizer_thread_registry.cc

95

I see, this might be the reason why I observed the races!

106

I will give it a try!

190

OK!

[krytarowski]

lib/sanitizer_common/sanitizer_thread_registry.cc

95

I've confirmed that after resetting thread_destroyed in Reset() there are no longer races.

I'm going to revamp the patch now.

[krytarowski]

This approach appears to be stable for TSan/NetBSD, no single race or misbehavior has been observed so far.

lib/sanitizer_common/sanitizer_thread_registry.h

public:
 
   ThreadStatus status;
   bool detached;
   bool workerthread;
 
   u32 parent_tid;
   ThreadContextBase *next;  // For storing thread contexts in a list.
 
+  atomic_uint32_t thread_destroyed; // To address race of Joined vs Finished
+
   void SetName(const char *new_name);
 
   void SetDead();
   void SetJoined(void *arg);
   void SetFinished();
   void SetStarted(tid_t _os_id, bool _workerthread, void *arg);
   void SetCreated(uptr _user_id, u64 _unique_id, bool _detached,
                   u32 _parent_tid, void *arg);
   void Reset();
 
+  void SetDestroyed();
+  bool GetDestroyed();
+
   // The following methods may be overriden by subclasses.
   // Some of them take opaque arg that may be optionally be used
   // by subclasses.
   virtual void OnDead() {}
   virtual void OnJoined(void *arg) {}
   virtual void OnFinished() {}
   virtual void OnStarted(void *arg) {}
   virtual void OnCreated(void *arg) {}

lib/sanitizer_common/sanitizer_thread_registry.cc

 
 namespace __sanitizer {
 
 ThreadContextBase::ThreadContextBase(u32 tid)
     : tid(tid), unique_id(0), reuse_count(), os_id(0), user_id(0),
       status(ThreadStatusInvalid),
       detached(false), workerthread(false), parent_tid(0), next(0) {
   name[0] = '\0';
+  atomic_store(&thread_destroyed, 0, memory_order_release);
 }
 
 ThreadContextBase::~ThreadContextBase() {
   // ThreadContextBase should never be deleted.
   CHECK(0);
 }
 
 void ThreadContextBase::SetName(const char *new_name) {
   name[0] = '\0';
   if (new_name) {
     internal_strncpy(name, new_name, sizeof(name));
     name[sizeof(name) - 1] = '\0';
   }
 }
 
 void ThreadContextBase::SetDead() {
   CHECK(status == ThreadStatusRunning ||
         status == ThreadStatusFinished);
   status = ThreadStatusDead;
   user_id = 0;
   OnDead();
 }
 
+void ThreadContextBase::SetDestroyed() {
+  atomic_store(&thread_destroyed, 1, memory_order_release);
+}
+
+bool ThreadContextBase::GetDestroyed() {
+  return !!atomic_load(&thread_destroyed, memory_order_acquire);
+}
+
 void ThreadContextBase::SetJoined(void *arg) {
   // FIXME(dvyukov): print message and continue (it's user error).
   CHECK_EQ(false, detached);
   CHECK_EQ(ThreadStatusFinished, status);
   status = ThreadStatusDead;
   user_id = 0;
   OnJoined(arg);
 }
void ThreadContextBase::SetCreated(uptr _user_id, u64 _unique_id,
   detached = _detached;
   // Parent tid makes no sense for the main thread.
   if (tid != 0)
     parent_tid = _parent_tid;
   OnCreated(arg);
 }
 
 void ThreadContextBase::Reset() {
   status = ThreadStatusInvalid;
   SetName(0);
+  atomic_store(&thread_destroyed, 0, memory_order_release);
   OnReset();
 }
 
 // ThreadRegistry implementation.
 
 const u32 ThreadRegistry::kUnknownTid = ~0U;
 
 ThreadRegistry::ThreadRegistry(ThreadContextFactory factory, u32 max_threads,
                                u32 thread_quarantine_size, u32 max_reuse)
     : context_factory_(factory),
       max_threads_(max_threads),
       thread_quarantine_size_(thread_quarantine_size),
       max_reuse_(max_reuse),
       mtx_(),
       n_contexts_(0),
       total_threads_(0),
       alive_threads_(0),

 
 u32 ThreadRegistry::FindThread(FindThreadCallback cb, void *arg) {
   BlockingMutexLock l(&mtx_);
   for (u32 tid = 0; tid < n_contexts_; tid++) {
     ThreadContextBase *tctx = threads_[tid];
     if (tctx != 0 && cb(tctx, arg))
       return tctx->tid;
   }
   return kUnknownTid;
 }
 
 ThreadContextBase *
 ThreadRegistry::FindThreadContextLocked(FindThreadCallback cb, void *arg) {
   CheckLocked();
   for (u32 tid = 0; tid < n_contexts_; tid++) {
     ThreadContextBase *tctx = threads_[tid];
     if (tctx != 0 && cb(tctx, arg))
if (tctx->status == ThreadStatusFinished) {
     tctx->SetDead();
     QuarantinePush(tctx);
   } else {
     tctx->detached = true;
   }
 }
 
 void ThreadRegistry::JoinThread(u32 tid, void *arg) {
+  bool destroyed = false;
+  do {
+    {
       BlockingMutexLock l(&mtx_);
       CHECK_LT(tid, n_contexts_);
       ThreadContextBase *tctx = threads_[tid];
       CHECK_NE(tctx, 0);
       if (tctx->status == ThreadStatusInvalid) {
         Report("%s: Join of non-existent thread\n", SanitizerToolName);
         return;
       }
+      if ((destroyed = tctx->GetDestroyed())) {
         tctx->SetJoined(arg);
         QuarantinePush(tctx);
       }
+    }
+    if (!destroyed)
+      internal_sched_yield();
+  } while (!destroyed);
+}
 
 // Normally this is called when the thread is about to exit.  If
 // called in ThreadStatusCreated state, then this thread was never
 // really started.  We just did CreateThread for a prospective new
 // thread before trying to create it, and then failed to actually
 // create it, and so never called StartThread.
 void ThreadRegistry::FinishThread(u32 tid) {
   BlockingMutexLock l(&mtx_);
if (tctx->status == ThreadStatusRunning) {
     CHECK_EQ(tctx->status, ThreadStatusCreated);
     dead = true;
   }
   tctx->SetFinished();
   if (dead) {
     tctx->SetDead();
     QuarantinePush(tctx);
   }
+  tctx->SetDestroyed();
 }
 
 void ThreadRegistry::StartThread(u32 tid, tid_t os_id, bool workerthread,
                                  void *arg) {
   BlockingMutexLock l(&mtx_);
   running_threads_++;
   CHECK_LT(tid, n_contexts_);
   ThreadContextBase *tctx = threads_[tid];