tsan: weaken concurrency guarantees in deadlock detector mutex hashmap

read locking on every access is too expensive



git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@203112 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 35 insertions, 33 deletions

diff --git a/lib/sanitizer_common/sanitizer_addrhashmap.h b/lib/sanitizer_common/sanitizer_addrhashmap.h
index b623fcc06..9bb44e41c 100644
--- a/lib/sanitizer_common/sanitizer_addrhashmap.h
+++ b/lib/sanitizer_common/sanitizer_addrhashmap.h
@@ -44,7 +44,7 @@ template<typename T, uptr kSize>
 class AddrHashMap {
  private:
   struct Cell {
-    RWMutex          mtx;
+    StaticSpinMutex  mtx;
     atomic_uintptr_t addr;
     T                val;
   };
@@ -66,17 +66,17 @@ class AddrHashMap {
     uptr                   addr_;
     bool                   created_;
     bool                   remove_;
-    bool                   write_;
   };
 
  private:
   friend class Handle;
   Cell *table_;
 
-  static const uptr kRemoved = 1;
+  static const uptr kLocked = 1;
+  static const uptr kRemoved = 2;
 
-  Cell *acquire(uptr addr, bool remove, bool *created, bool *write);
-  void  release(uptr addr, bool remove, bool write, Cell *c);
+  Cell *acquire(uptr addr, bool remove, bool *created);
+  void  release(uptr addr, bool remove, bool created, Cell *c);
   uptr hash(uptr addr);
 };
 
@@ -86,12 +86,12 @@ AddrHashMap<T, kSize>::Handle::Handle(AddrHashMap<T, kSize> *map, uptr addr,
   map_ = map;
   addr_ = addr;
   remove_ = remove;
-  cell_ = map_->acquire(addr_, remove_, &created_, &write_);
+  cell_ = map_->acquire(addr_, remove_, &created_);
 }
 
 template<typename T, uptr kSize>
 AddrHashMap<T, kSize>::Handle::~Handle() {
-  map_->release(addr_, remove_, write_, cell_);
+  map_->release(addr_, remove_, created_, cell_);
 }
 
 template<typename T, uptr kSize>
@@ -116,7 +116,7 @@ AddrHashMap<T, kSize>::AddrHashMap() {
 
 template<typename T, uptr kSize>
 typename AddrHashMap<T, kSize>::Cell *AddrHashMap<T, kSize>::acquire(uptr addr,
-    bool remove, bool *created, bool *write) {
+    bool remove, bool *created) {
   // When we access the element associated with addr,
   // we lock its home cell (the cell associated with hash(addr).
   // If the element was just created or is going to be removed,
@@ -126,19 +126,21 @@ typename AddrHashMap<T, kSize>::Cell *AddrHashMap<T, kSize>::acquire(uptr addr,
   // inserts.
   // Note that the home cell is not necessary the cell where the element is
   // stored.
-  *write = false;
   *created = false;
   uptr h0 = hash(addr);
   Cell *c0 = &table_[h0];
-  // First try to find an existing element under read lock.
-  if (!remove) {
-    c0->mtx.ReadLock();
+  // First try to find an existing element w/o read mutex.
+  {
     uptr h = h0;
     for (;;) {
       Cell *c = &table_[h];
       uptr addr1 = atomic_load(&c->addr, memory_order_acquire);
       if (addr1 == 0)  // empty cell denotes end of the cell chain for the elem
         break;
+      // Locked cell means that another thread can be concurrently inserting
+      // the same element, fallback to mutex.
+      if (addr1 == kLocked)
+        break;
       if (addr1 == addr)  // ok, found it
         return c;
       h++;
@@ -146,10 +148,10 @@ typename AddrHashMap<T, kSize>::Cell *AddrHashMap<T, kSize>::acquire(uptr addr,
         h = 0;
       CHECK_NE(h, h0);  // made the full cycle
     }
-    c0->mtx.ReadUnlock();
   }
-  // Now try to create it under write lock.
-  *write = true;
+  if (remove)
+    return 0;
+  // Now try to create it under the mutex.
   c0->mtx.Lock();
   uptr h = h0;
   for (;;) {
@@ -157,12 +159,9 @@ typename AddrHashMap<T, kSize>::Cell *AddrHashMap<T, kSize>::acquire(uptr addr,
     uptr addr1 = atomic_load(&c->addr, memory_order_acquire);
     if (addr1 == addr)  // another thread has inserted it ahead of us
       return c;
-    if (remove && addr1 == 0) {  // the element has not existed before
-      c0->mtx.Unlock();
-      return 0;
-    }
-    if (!remove && (addr1 == 0 ||addr1 == kRemoved) &&
-        atomic_compare_exchange_strong(&c->addr, &addr1, addr,
+    // Skip kLocked, since we hold the home cell mutex, it can't be our elem.
+    if ((addr1 == 0 || addr1 == kRemoved) &&
+        atomic_compare_exchange_strong(&c->addr, &addr1, kLocked,
           memory_order_acq_rel)) {
       // we've created the element
       *created = true;
@@ -176,23 +175,26 @@ typename AddrHashMap<T, kSize>::Cell *AddrHashMap<T, kSize>::acquire(uptr addr,
 }
 
 template<typename T, uptr kSize>
-void AddrHashMap<T, kSize>::release(uptr addr, bool remove, bool write,
+void AddrHashMap<T, kSize>::release(uptr addr, bool remove, bool created,
     Cell *c) {
   if (c == 0)
     return;
   // if we are going to remove, we must hold write lock
-  CHECK_EQ(!remove || write, true);
-  CHECK_EQ(atomic_load(&c->addr, memory_order_relaxed), addr);
-  // denote that the cell is empty now
-  if (remove)
-    atomic_store(&c->addr, kRemoved, memory_order_release);
-  // unlock the home cell
-  uptr h0 = hash(addr);
-  Cell *c0 = &table_[h0];
-  if (write)
+  uptr addr1 = atomic_load(&c->addr, memory_order_relaxed);
+  if (created) {
+    // denote completion of insertion
+    atomic_store(&c->addr, addr, memory_order_release);
+    // unlock the home cell
+    uptr h0 = hash(addr);
+    Cell *c0 = &table_[h0];
     c0->mtx.Unlock();
-  else
-    c0->mtx.ReadUnlock();
+  } else {
+    CHECK_EQ(addr, addr1);
+    if (remove) {
+      // denote that the cell is empty now
+      atomic_store(&c->addr, kRemoved, memory_order_release);
+    }
+  }
 }
 
 template<typename T, uptr kSize>