tsan: remove quadratic behavior in pthread_join

[dvyukov]

Summary

pthread_join needs to map pthread_t of the joined thread to our Tid.
Currently we do this with linear search over all threads.
This has quadratic complexity and becomes much worse with the new
tsan runtime, which memorizes all threads that ever existed.

To resolve this add a hash map of live threads only (that are still
associated with pthread_t) and use it for the mapping.

With the new tsan runtime some programs spent 1/3 of time in this mapping.
After this change the mapping disappears from profiles.

Depends on D113996.

[melver]

compiler-rt/lib/sanitizer_common/sanitizer_thread_registry.cpp

171

Insert seems to have its own CHECK.

Although I find the API could be improved.. I'll comment on the other patch.

[dvyukov]

rebase

[dvyukov]

PTAL

[vitalybuka]

rebase

compiler-rt/lib/sanitizer_common/sanitizer_thread_registry.h

 //
 // General thread bookkeeping functionality.
 //===----------------------------------------------------------------------===//
 
 #ifndef SANITIZER_THREAD_REGISTRY_H
 #define SANITIZER_THREAD_REGISTRY_H
 
 #include "sanitizer_common.h"
+#include "sanitizer_dense_map.h"
 #include "sanitizer_list.h"
 #include "sanitizer_mutex.h"
 
 namespace __sanitizer {
 
 enum ThreadStatus {
   ThreadStatusInvalid,   // Non-existent thread, data is invalid.
   ThreadStatusCreated,   // Created but not yet running.
public:
 
   void SetThreadName(u32 tid, const char *name);
   void SetThreadNameByUserId(uptr user_id, const char *name);
   void DetachThread(u32 tid, void *arg);
   void JoinThread(u32 tid, void *arg);
   // Finishes thread and returns previous status.
   ThreadStatus FinishThread(u32 tid);
   void StartThread(u32 tid, tid_t os_id, ThreadType thread_type, void *arg);
+  u32 ConsumeThreadUserId(uptr user_id);
   void SetThreadUserId(u32 tid, uptr user_id);
 
  private:
   const ThreadContextFactory context_factory_;
   const u32 max_threads_;
   const u32 thread_quarantine_size_;
   const u32 max_reuse_;
 
   Mutex mtx_;
 
   u64 total_threads_;   // Total number of created threads. May be greater than
                         // max_threads_ if contexts were reused.
   uptr alive_threads_;  // Created or running.
   uptr max_alive_threads_;
   uptr running_threads_;
 
   InternalMmapVector<ThreadContextBase *> threads_;
   IntrusiveList<ThreadContextBase> dead_threads_;
   IntrusiveList<ThreadContextBase> invalid_threads_;
+  DenseMap<uptr, Tid> live_;
 
   void QuarantinePush(ThreadContextBase *tctx);
   ThreadContextBase *QuarantinePop();
 };
 
 typedef GenericScopedLock<ThreadRegistry> ThreadRegistryLock;
 
 } // namespace __sanitizer
 
 #endif // SANITIZER_THREAD_REGISTRY_H

compiler-rt/lib/sanitizer_common/sanitizer_thread_registry.cpp

 //===-- sanitizer_thread_registry.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 sanitizer tools.
 //
 // General thread bookkeeping functionality.
 //===----------------------------------------------------------------------===//
 
 #include "sanitizer_thread_registry.h"
 
+#include "sanitizer_placement_new.h"
+
 namespace __sanitizer {
 
 ThreadContextBase::ThreadContextBase(u32 tid)
     : tid(tid), unique_id(0), reuse_count(), os_id(0), user_id(0),
       status(ThreadStatusInvalid), detached(false),
       thread_type(ThreadType::Regular), parent_tid(0), next(0) {
   name[0] = '\0';
   atomic_store(&thread_destroyed, 0, memory_order_release);
#endif
   CHECK_NE(tid, kInvalidTid);
   CHECK_LT(tid, max_threads_);
   CHECK_EQ(tctx->status, ThreadStatusInvalid);
   alive_threads_++;
   if (max_alive_threads_ < alive_threads_) {
     max_alive_threads_++;
     CHECK_EQ(alive_threads_, max_alive_threads_);
   }
+  if (user_id) {
+    // Ensure that user_id is unique. If it's not the case we are screwed.
+    // Ignoring this situation may lead to very hard to debug false
+    // positives later (e.g. if we join a wrong thread).
+    CHECK(live_.try_emplace(user_id, tid).second);
+  }
   tctx->SetCreated(user_id, total_threads_++, detached,
                    parent_tid, arg);
   return tid;
 }
 
 void ThreadRegistry::RunCallbackForEachThreadLocked(ThreadCallback cb,
                                                     void *arg) {
   CheckLocked();
void ThreadRegistry::SetThreadName(u32 tid, const char *name) {
   CHECK_NE(tctx, 0);
   CHECK_EQ(SANITIZER_FUCHSIA ? ThreadStatusCreated : ThreadStatusRunning,
            tctx->status);
   tctx->SetName(name);
 }
 
 void ThreadRegistry::SetThreadNameByUserId(uptr user_id, const char *name) {
   ThreadRegistryLock l(this);
-  for (u32 tid = 0; tid < threads_.size(); tid++) {
-    ThreadContextBase *tctx = threads_[tid];
-    if (tctx != 0 && tctx->user_id == user_id &&
-        tctx->status != ThreadStatusInvalid) {
-      tctx->SetName(name);
-      return;
-    }
-  }
+  if (const auto *tid = live_.find(user_id))
+    threads_[tid->second]->SetName(name);
 }
 
 void ThreadRegistry::DetachThread(u32 tid, void *arg) {
   ThreadRegistryLock l(this);
   ThreadContextBase *tctx = threads_[tid];
   CHECK_NE(tctx, 0);
   if (tctx->status == ThreadStatusInvalid) {
     Report("%s: Detach of non-existent thread\n", SanitizerToolName);
     return;
   }
   tctx->OnDetached(arg);
   if (tctx->status == ThreadStatusFinished) {
+    if (tctx->user_id)
+      live_.erase(tctx->user_id);
     tctx->SetDead();
     QuarantinePush(tctx);
   } else {
     tctx->detached = true;
   }
 }
 
 void ThreadRegistry::JoinThread(u32 tid, void *arg) {
   bool destroyed = false;
   do {
     {
       ThreadRegistryLock l(this);
       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())) {
+        if (tctx->user_id)
+          live_.erase(tctx->user_id);
         tctx->SetJoined(arg);
         QuarantinePush(tctx);
       }
     }
     if (!destroyed)
       internal_sched_yield();
   } while (!destroyed);
 }
if (tctx->status == ThreadStatusRunning) {
     running_threads_--;
   } else {
     // The thread never really existed.
     CHECK_EQ(tctx->status, ThreadStatusCreated);
     dead = true;
   }
   tctx->SetFinished();
   if (dead) {
+    if (tctx->user_id)
+      live_.erase(tctx->user_id);
     tctx->SetDead();
     QuarantinePush(tctx);
   }
   tctx->SetDestroyed();
   return prev_status;
 }
 
 void ThreadRegistry::StartThread(u32 tid, tid_t os_id, ThreadType thread_type,

 ThreadContextBase *ThreadRegistry::QuarantinePop() {
   if (invalid_threads_.size() == 0)
     return 0;
   ThreadContextBase *tctx = invalid_threads_.front();
   invalid_threads_.pop_front();
   return tctx;
 }
 
+u32 ThreadRegistry::ConsumeThreadUserId(uptr user_id) {
+  ThreadRegistryLock l(this);
+  u32 tid;
+  auto *t = live_.find(user_id);
+  CHECK(t);
+  tid = t->second;
+  live_.erase(t);
+  auto *tctx = threads_[tid];
+  CHECK_EQ(tctx->user_id, user_id);
+  tctx->user_id = 0;
+  return tid;
+}
+
 void ThreadRegistry::SetThreadUserId(u32 tid, uptr user_id) {
   ThreadRegistryLock l(this);
   ThreadContextBase *tctx = threads_[tid];
   CHECK_NE(tctx, 0);
   CHECK_NE(tctx->status, ThreadStatusInvalid);
   CHECK_NE(tctx->status, ThreadStatusDead);
   CHECK_EQ(tctx->user_id, 0);
   tctx->user_id = user_id;
+  CHECK(live_.try_emplace(user_id, tctx->tid).second);
 }
 
 }  // namespace __sanitizer

compiler-rt/lib/tsan/rtl/tsan_rtl_thread.cpp

#endif
   thr = 0;
 }
 
 struct ConsumeThreadContext {
   uptr uid;
   ThreadContextBase *tctx;
 };
 
-static bool ConsumeThreadByUid(ThreadContextBase *tctx, void *arg) {
-  ConsumeThreadContext *findCtx = (ConsumeThreadContext *)arg;
-  if (tctx->user_id == findCtx->uid && tctx->status != ThreadStatusInvalid) {
-    if (findCtx->tctx) {
-      // Ensure that user_id is unique. If it's not the case we are screwed.
-      // Something went wrong before, but now there is no way to recover.
-      // Returning a wrong thread is not an option, it may lead to very hard
-      // to debug false positives (e.g. if we join a wrong thread).
-      Report("ThreadSanitizer: dup thread with used id 0x%zx\n", findCtx->uid);
-      Die();
-    }
-    findCtx->tctx = tctx;
-    tctx->user_id = 0;
-  }
-  return false;
-}
-
 Tid ThreadConsumeTid(ThreadState *thr, uptr pc, uptr uid) {
-  ConsumeThreadContext findCtx = {uid, nullptr};
-  ctx->thread_registry.FindThread(ConsumeThreadByUid, &findCtx);
-  Tid tid = findCtx.tctx ? findCtx.tctx->tid : kInvalidTid;
-  DPrintf("#%d: ThreadTid uid=%zu tid=%d\n", thr->tid, uid, tid);
-  return tid;
+  return ctx->thread_registry.ConsumeThreadUserId(uid);
 }
 
 void ThreadJoin(ThreadState *thr, uptr pc, Tid tid) {
   CHECK_GT(tid, 0);
   CHECK_LT(tid, kMaxTid);
   DPrintf("#%d: ThreadJoin tid=%d\n", thr->tid, tid);
   ctx->thread_registry.JoinThread(tid, thr);
 }