diff options
author | Dmitry Vyukov <dvyukov@google.com> | 2014-03-06 12:04:26 +0000 |
---|---|---|
committer | Dmitry Vyukov <dvyukov@google.com> | 2014-03-06 12:04:26 +0000 |
commit | c847a57ef2a49346bba535d54252b08277cfdae6 (patch) | |
tree | d239f7a36ba315bff37baae66bea701385d2e744 /lib/sanitizer_common/sanitizer_addrhashmap.h | |
parent | 7bb80e4dd4f40476135da3e443333649ec9b9699 (diff) | |
download | compiler-rt-c847a57ef2a49346bba535d54252b08277cfdae6.tar.gz |
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
Diffstat (limited to 'lib/sanitizer_common/sanitizer_addrhashmap.h')
-rw-r--r-- | lib/sanitizer_common/sanitizer_addrhashmap.h | 68 |
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> |