DenseSet version of D113997

[vitalybuka]

Summary

Depends on D113997, D114048.

[melver]

I assume this one will be squashed into "tsan: remove quadratic behavior in pthread_join"?

[vitalybuka]

In D114050#3137155, @melver wrote:

I assume this one will be squashed into "tsan: remove quadratic behavior in pthread_join"?

yes

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_hashmap.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.
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_;
-  HashMap<uptr, Tid> live_;
+  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

#endif
   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_.Insert(user_id, tid));
+    CHECK(live_.insert({user_id, tid}).second);
   }
   tctx->SetCreated(user_id, total_threads_++, detached,
                    parent_tid, arg);
   return tid;
 }
 
 void ThreadRegistry::RunCallbackForEachThreadLocked(ThreadCallback cb,
                                                     void *arg) {
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);
-  u32 tid;
-  if (live_.Find(user_id, &tid))
-    threads_[tid]->SetName(name);
+  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_.Remove(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_.Remove(tctx->user_id);
+          live_.erase(tctx->user_id);
         tctx->SetJoined(arg);
         QuarantinePush(tctx);
       }
     }
     if (!destroyed)
       internal_sched_yield();
   } while (!destroyed);
 }
ThreadStatus ThreadRegistry::FinishThread(u32 tid) {
   } else {
     // The thread never really existed.
     CHECK_EQ(tctx->status, ThreadStatusCreated);
     dead = true;
   }
   tctx->SetFinished();
   if (dead) {
     if (tctx->user_id)
-      live_.Remove(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() {
   ThreadContextBase *tctx = invalid_threads_.front();
   invalid_threads_.pop_front();
   return tctx;
 }
 
 u32 ThreadRegistry::ConsumeThreadUserId(uptr user_id) {
   ThreadRegistryLock l(this);
   u32 tid;
-  CHECK(live_.Remove(user_id, &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_.Insert(user_id, tctx->tid));
+  CHECK(live_.insert({user_id, tctx->tid}).second);
 }
 
 }  // namespace __sanitizer