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

87

This also needs to reset thread_destroyed because contexts are reused.

97

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

87

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

97

I will give it a try!

190

OK!

[krytarowski]

lib/sanitizer_common/sanitizer_thread_registry.cc

87

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/lsan/lsan_interceptors.cc

INTERCEPTOR(int, pthread_create, void *th, void *attr,
   }
   if (attr == &myattr)
     pthread_attr_destroy(&myattr);
   return res;
 }
 
 INTERCEPTOR(int, pthread_join, void *th, void **ret) {
   ENSURE_LSAN_INITED;
-  int tid = ThreadTid((uptr)th);
+  ThreadContextBase *tctx = ThreadTctx((uptr)th);
   int res = REAL(pthread_join)(th, ret);
   if (res == 0)
-    ThreadJoin(tid);
+    ThreadJoin(tctx->tid);
   return res;
 }
 
 INTERCEPTOR(void, _exit, int status) {
   if (status == 0 && HasReportedLeaks()) status = common_flags()->exitcode;
   REAL(_exit)(status);
 }
 

lib/lsan/lsan_thread.h

 };
 
 void InitializeThreadRegistry();
 
 void ThreadStart(u32 tid, tid_t os_id, bool workerthread = false);
 void ThreadFinish();
 u32 ThreadCreate(u32 tid, uptr uid, bool detached);
 void ThreadJoin(u32 tid);
-u32 ThreadTid(uptr uid);
+ThreadContextBase *ThreadTctx(uptr uid);
 
 u32 GetCurrentThread();
 void SetCurrentThread(u32 tid);
 ThreadContext *CurrentThreadContext();
 void EnsureMainThreadIDIsCorrect();
 }  // namespace __lsan
 
 #endif  // LSAN_THREAD_H

lib/lsan/lsan_thread.cc

 static bool FindThreadByUid(ThreadContextBase *tctx, void *arg) {
   uptr uid = (uptr)arg;
   if (tctx->user_id == uid && tctx->status != ThreadStatusInvalid) {
     return true;
   }
   return false;
 }
 
-u32 ThreadTid(uptr uid) {
+ThreadContextBase *ThreadTctx(uptr uid) {
   return thread_registry->FindThread(FindThreadByUid, (void*)uid);
 }
 
 void ThreadJoin(u32 tid) {
   CHECK_NE(tid, kInvalidTid);
   thread_registry->JoinThread(tid, /* arg */nullptr);
 }
 

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) {}
public:
   u32 CreateThread(uptr user_id, bool detached, u32 parent_tid, void *arg);
 
   typedef void (*ThreadCallback)(ThreadContextBase *tctx, void *arg);
   // Invokes callback with a specified arg for each thread context.
   // Should be guarded by ThreadRegistryLock.
   void RunCallbackForEachThreadLocked(ThreadCallback cb, void *arg);
 
   typedef bool (*FindThreadCallback)(ThreadContextBase *tctx, void *arg);
-  // Finds a thread using the provided callback. Returns kUnknownTid if no
+  // Finds a thread using the provided callback. Returns NULL if no
   // thread is found.
-  u32 FindThread(FindThreadCallback cb, void *arg);
+  ThreadContextBase *FindThread(FindThreadCallback cb, void *arg);
   // Should be guarded by ThreadRegistryLock. Return 0 if no thread
   // is found.
   ThreadContextBase *FindThreadContextLocked(FindThreadCallback cb,
                                              void *arg);
   ThreadContextBase *FindThreadContextByOsIDLocked(tid_t os_id);
 
   void SetThreadName(u32 tid, const char *name);
   void SetThreadNameByUserId(uptr user_id, const char *name);

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_relaxed(&thread_destroyed, 0);
 }
 
 ThreadContextBase::~ThreadContextBase() {
   // ThreadContextBase should never be deleted.
   CHECK(0);
 }
 
 void ThreadContextBase::SetName(const char *new_name) {
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);
   OnReset();
 }
 
+void ThreadContextBase::SetDestroyed() {
+  atomic_store(&thread_destroyed, 1, memory_order_release);
+}
+
+bool ThreadContextBase::GetDestroyed() {
+  return !!atomic_load(&thread_destroyed, memory_order_acquire);
+}
+
 // 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),
void ThreadRegistry::RunCallbackForEachThreadLocked(ThreadCallback cb,
   for (u32 tid = 0; tid < n_contexts_; tid++) {
     ThreadContextBase *tctx = threads_[tid];
     if (tctx == 0)
       continue;
     cb(tctx, arg);
   }
 }
 
-u32 ThreadRegistry::FindThread(FindThreadCallback cb, void *arg) {
+ThreadContextBase *
+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 tctx;
   }
-  return kUnknownTid;
+  return 0;
 }
 
 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))

lib/tsan/rtl/tsan_interceptors.cc

void DestroyThreadState() {
   ProcDestroy(proc);
   ThreadSignalContext *sctx = thr->signal_ctx;
   if (sctx) {
     thr->signal_ctx = 0;
     UnmapOrDie(sctx, sizeof(*sctx));
   }
   DTLS_Destroy();
   cur_thread_finalize();
+  thr->tctx->SetDestroyed();
 }
 }  // namespace __tsan
 
 #if !SANITIZER_MAC && !SANITIZER_NETBSD
 static void thread_finalize(void *v) {
   uptr iter = (uptr)v;
   if (iter > 1) {
     if (pthread_setspecific(interceptor_ctx()->finalize_key,
TSAN_INTERCEPTOR(int, pthread_create,
   }
   if (attr == &myattr)
     pthread_attr_destroy(&myattr);
   return res;
 }
 
 TSAN_INTERCEPTOR(int, pthread_join, void *th, void **ret) {
   SCOPED_INTERCEPTOR_RAW(pthread_join, th, ret);
-  int tid = ThreadTid(thr, pc, (uptr)th);
+  ThreadContextBase *tctx = ThreadTctx(thr, pc, (uptr)th);
   ThreadIgnoreBegin(thr, pc);
   int res = BLOCK_REAL(pthread_join)(th, ret);
   ThreadIgnoreEnd(thr, pc);
   if (res == 0) {
-    ThreadJoin(thr, pc, tid);
+    while (!tctx->GetDestroyed())
+       internal_sched_yield();
+    ThreadJoin(thr, pc, tctx->tid);
   }
   return res;
 }
 
 DEFINE_REAL_PTHREAD_FUNCTIONS
 
 TSAN_INTERCEPTOR(int, pthread_detach, void *th) {
   SCOPED_TSAN_INTERCEPTOR(pthread_detach, th);
-  int tid = ThreadTid(thr, pc, (uptr)th);
+  ThreadContextBase *tctx = ThreadTctx(thr, pc, (uptr)th);
   int res = REAL(pthread_detach)(th);
   if (res == 0) {
-    ThreadDetach(thr, pc, tid);
+    ThreadDetach(thr, pc, tctx->tid);
   }
   return res;
 }
 
 // Problem:
 // NPTL implementation of pthread_cond has 2 versions (2.2.5 and 2.3.2).
 // pthread_cond_t has different size in the different versions.
 // If call new REAL functions for old pthread_cond_t, they will corrupt memory

lib/tsan/rtl/tsan_rtl.h

 void ThreadIgnoreSyncEnd(ThreadState *thr, uptr pc);
 
 void FuncEntry(ThreadState *thr, uptr pc);
 void FuncExit(ThreadState *thr);
 
 int ThreadCreate(ThreadState *thr, uptr pc, uptr uid, bool detached);
 void ThreadStart(ThreadState *thr, int tid, tid_t os_id, bool workerthread);
 void ThreadFinish(ThreadState *thr);
-int ThreadTid(ThreadState *thr, uptr pc, uptr uid);
+ThreadContextBase *ThreadTctx(ThreadState *thr, uptr pc, uptr uid);
 void ThreadJoin(ThreadState *thr, uptr pc, int tid);
 void ThreadDetach(ThreadState *thr, uptr pc, int tid);
 void ThreadFinalize(ThreadState *thr);
 void ThreadSetName(ThreadState *thr, const char *name);
 int ThreadCount(ThreadState *thr);
 void ProcessPendingSignals(ThreadState *thr);
 
 Processor *ProcCreate();

lib/tsan/rtl/tsan_rtl_thread.cc

static bool FindThreadByUid(ThreadContextBase *tctx, void *arg) {
   uptr uid = (uptr)arg;
   if (tctx->user_id == uid && tctx->status != ThreadStatusInvalid) {
     tctx->user_id = 0;
     return true;
   }
   return false;
 }
 
-int ThreadTid(ThreadState *thr, uptr pc, uptr uid) {
-  int res = ctx->thread_registry->FindThread(FindThreadByUid, (void*)uid);
-  DPrintf("#%d: ThreadTid uid=%zu tid=%d\n", thr->tid, uid, res);
+ThreadContextBase *ThreadTctx(ThreadState *thr, uptr pc, uptr uid) {
+  ThreadContextBase *res;
+  res = ctx->thread_registry->FindThread(FindThreadByUid, (void*)uid);
+  DPrintf("#%d: ThreadTid uid=%zu tid=%d\n", thr->tid, uid, res->tid);
   return res;
 }
 
 void ThreadJoin(ThreadState *thr, uptr pc, int tid) {
   CHECK_GT(tid, 0);
   CHECK_LT(tid, kMaxTid);
   DPrintf("#%d: ThreadJoin tid=%d\n", thr->tid, tid);
   ctx->thread_registry->JoinThread(tid, thr);