12d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines//===-- sanitizer_deadlock_detector.h ---------------------------*- C++ -*-===// 22d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 32d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// The LLVM Compiler Infrastructure 42d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 52d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// This file is distributed under the University of Illinois Open Source 62d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// License. See LICENSE.TXT for details. 72d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 82d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines//===----------------------------------------------------------------------===// 92d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 102d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// This file is a part of Sanitizer runtime. 112d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// The deadlock detector maintains a directed graph of lock acquisitions. 122d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// When a lock event happens, the detector checks if the locks already held by 132d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// the current thread are reachable from the newly acquired lock. 142d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 152d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// The detector can handle only a fixed amount of simultaneously live locks 162d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// (a lock is alive if it has been locked at least once and has not been 172d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// destroyed). When the maximal number of locks is reached the entire graph 182d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// is flushed and the new lock epoch is started. The node ids from the old 192d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// epochs can not be used with any of the detector methods except for 202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// nodeBelongsToCurrentEpoch(). 212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// FIXME: this is work in progress, nothing really works yet. 232d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines//===----------------------------------------------------------------------===// 252d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#ifndef SANITIZER_DEADLOCK_DETECTOR_H 272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#define SANITIZER_DEADLOCK_DETECTOR_H 282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#include "sanitizer_common.h" 302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#include "sanitizer_bvgraph.h" 312d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesnamespace __sanitizer { 332d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 342d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// Thread-local state for DeadlockDetector. 352d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// It contains the locks currently held by the owning thread. 362d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestemplate <class BV> 372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesclass DeadlockDetectorTLS { 382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines public: 392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // No CTOR. 402d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void clear() { 412d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bv_.clear(); 422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines epoch_ = 0; 432d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines n_recursive_locks = 0; 442d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines n_all_locks_ = 0; 452d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 462d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 472d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool empty() const { return bv_.empty(); } 482d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 492d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void ensureCurrentEpoch(uptr current_epoch) { 502d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (epoch_ == current_epoch) return; 512d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bv_.clear(); 522d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines epoch_ = current_epoch; 532d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 542d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 552d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr getEpoch() const { return epoch_; } 562d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 572d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Returns true if this is the first (non-recursive) acquisition of this lock. 582d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool addLock(uptr lock_id, uptr current_epoch, u32 stk) { 592d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Printf("addLock: %zx %zx stk %u\n", lock_id, current_epoch, stk); 602d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK_EQ(epoch_, current_epoch); 612d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (!bv_.setBit(lock_id)) { 622d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // The lock is already held by this thread, it must be recursive. 632d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK_LT(n_recursive_locks, ARRAY_SIZE(recursive_locks)); 642d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines recursive_locks[n_recursive_locks++] = lock_id; 652d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return false; 662d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 672d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK_LT(n_all_locks_, ARRAY_SIZE(all_locks_with_contexts_)); 682d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // lock_id < BV::kSize, can cast to a smaller int. 692d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines u32 lock_id_short = static_cast<u32>(lock_id); 702d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines LockWithContext l = {lock_id_short, stk}; 712d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines all_locks_with_contexts_[n_all_locks_++] = l; 722d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return true; 732d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 742d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 752d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void removeLock(uptr lock_id) { 762d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (n_recursive_locks) { 772d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (sptr i = n_recursive_locks - 1; i >= 0; i--) { 782d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (recursive_locks[i] == lock_id) { 792d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines n_recursive_locks--; 802d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Swap(recursive_locks[i], recursive_locks[n_recursive_locks]); 812d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return; 822d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 832d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 842d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 852d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Printf("remLock: %zx %zx\n", lock_id, epoch_); 862d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK(bv_.clearBit(lock_id)); 872d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (n_all_locks_) { 882d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (sptr i = n_all_locks_ - 1; i >= 0; i--) { 892d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (all_locks_with_contexts_[i].lock == static_cast<u32>(lock_id)) { 902d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Swap(all_locks_with_contexts_[i], 912d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines all_locks_with_contexts_[n_all_locks_ - 1]); 922d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines n_all_locks_--; 932d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines break; 942d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 952d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 962d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 972d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 982d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 992d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines u32 findLockContext(uptr lock_id) { 1002d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 0; i < n_all_locks_; i++) 1012d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (all_locks_with_contexts_[i].lock == static_cast<u32>(lock_id)) 1022d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return all_locks_with_contexts_[i].stk; 1032d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return 0; 1042d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1052d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1062d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines const BV &getLocks(uptr current_epoch) const { 1072d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK_EQ(epoch_, current_epoch); 1082d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return bv_; 1092d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1102d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1112d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr getNumLocks() const { return n_all_locks_; } 1122d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr getLock(uptr idx) const { return all_locks_with_contexts_[idx].lock; } 1132d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1142d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines private: 1152d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines BV bv_; 1162d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr epoch_; 1172d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr recursive_locks[64]; 1182d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr n_recursive_locks; 1192d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines struct LockWithContext { 1202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines u32 lock; 1212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines u32 stk; 1222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines }; 1232d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines LockWithContext all_locks_with_contexts_[64]; 1242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr n_all_locks_; 1252d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines}; 1262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// DeadlockDetector. 1282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// For deadlock detection to work we need one global DeadlockDetector object 1292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// and one DeadlockDetectorTLS object per evey thread. 1302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// This class is not thread safe, all concurrent accesses should be guarded 1312d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// by an external lock. 1322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// Most of the methods of this class are not thread-safe (i.e. should 1332d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// be protected by an external lock) unless explicitly told otherwise. 1342d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestemplate <class BV> 1352d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesclass DeadlockDetector { 1362d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines public: 1372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines typedef BV BitVector; 1382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr size() const { return g_.size(); } 1402d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1412d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // No CTOR. 1422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void clear() { 1432d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines current_epoch_ = 0; 1442d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines available_nodes_.clear(); 1452d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines recycled_nodes_.clear(); 1462d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines g_.clear(); 1472d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines n_edges_ = 0; 1482d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1492d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1502d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Allocate new deadlock detector node. 1512d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // If we are out of available nodes first try to recycle some. 1522d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // If there is nothing to recycle, flush the graph and increment the epoch. 1532d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Associate 'data' (opaque user's object) with the new node. 1542d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr newNode(uptr data) { 1552d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (!available_nodes_.empty()) 1562d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return getAvailableNode(data); 1572d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (!recycled_nodes_.empty()) { 1582d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Printf("recycling: n_edges_ %zd\n", n_edges_); 1592d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (sptr i = n_edges_ - 1; i >= 0; i--) { 1602d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (recycled_nodes_.getBit(edges_[i].from) || 1612d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines recycled_nodes_.getBit(edges_[i].to)) { 1622d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Swap(edges_[i], edges_[n_edges_ - 1]); 1632d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines n_edges_--; 1642d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1652d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1662d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK(available_nodes_.empty()); 1672d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // removeEdgesFrom was called in removeNode. 1682d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines g_.removeEdgesTo(recycled_nodes_); 1692d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines available_nodes_.setUnion(recycled_nodes_); 1702d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines recycled_nodes_.clear(); 1712d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return getAvailableNode(data); 1722d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1732d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // We are out of vacant nodes. Flush and increment the current_epoch_. 1742d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines current_epoch_ += size(); 1752d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines recycled_nodes_.clear(); 1762d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines available_nodes_.setAll(); 1772d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines g_.clear(); 1782d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return getAvailableNode(data); 1792d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1802d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1812d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Get data associated with the node created by newNode(). 1822d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr getData(uptr node) const { return data_[nodeToIndex(node)]; } 1832d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1842d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool nodeBelongsToCurrentEpoch(uptr node) { 1852d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return node && (node / size() * size()) == current_epoch_; 1862d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1872d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1882d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void removeNode(uptr node) { 1892d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr idx = nodeToIndex(node); 1902d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK(!available_nodes_.getBit(idx)); 1912d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK(recycled_nodes_.setBit(idx)); 1922d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines g_.removeEdgesFrom(idx); 1932d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1942d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1952d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void ensureCurrentEpoch(DeadlockDetectorTLS<BV> *dtls) { 1962d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dtls->ensureCurrentEpoch(current_epoch_); 1972d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1982d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1992d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Returns true if there is a cycle in the graph after this lock event. 2002d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Ideally should be called before the lock is acquired so that we can 2012d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // report a deadlock before a real deadlock happens. 2022d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool onLockBefore(DeadlockDetectorTLS<BV> *dtls, uptr cur_node) { 2032d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ensureCurrentEpoch(dtls); 2042d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr cur_idx = nodeToIndex(cur_node); 2052d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return g_.isReachable(cur_idx, dtls->getLocks(current_epoch_)); 2062d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2072d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2082d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines u32 findLockContext(DeadlockDetectorTLS<BV> *dtls, uptr node) { 2092d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return dtls->findLockContext(nodeToIndex(node)); 2102d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2112d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2122d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Add cur_node to the set of locks held currently by dtls. 2132d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void onLockAfter(DeadlockDetectorTLS<BV> *dtls, uptr cur_node, u32 stk = 0) { 2142d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ensureCurrentEpoch(dtls); 2152d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr cur_idx = nodeToIndex(cur_node); 2162d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dtls->addLock(cur_idx, current_epoch_, stk); 2172d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2182d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2192d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Experimental *racy* fast path function. 2202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Returns true if all edges from the currently held locks to cur_node exist. 2212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool hasAllEdges(DeadlockDetectorTLS<BV> *dtls, uptr cur_node) { 2222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr local_epoch = dtls->getEpoch(); 2232d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Read from current_epoch_ is racy. 2242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (cur_node && local_epoch == current_epoch_ && 2252d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines local_epoch == nodeToEpoch(cur_node)) { 2262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr cur_idx = nodeToIndexUnchecked(cur_node); 2272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 0, n = dtls->getNumLocks(); i < n; i++) { 2282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (!g_.hasEdge(dtls->getLock(i), cur_idx)) 2292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return false; 2302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2312d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return true; 2322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2332d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return false; 2342d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2352d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2362d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Adds edges from currently held locks to cur_node, 2372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // returns the number of added edges, and puts the sources of added edges 2382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // into added_edges[]. 2392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Should be called before onLockAfter. 2402d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr addEdges(DeadlockDetectorTLS<BV> *dtls, uptr cur_node, u32 stk, 2412d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines int unique_tid) { 2422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ensureCurrentEpoch(dtls); 2432d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr cur_idx = nodeToIndex(cur_node); 2442d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr added_edges[40]; 2452d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr n_added_edges = g_.addEdges(dtls->getLocks(current_epoch_), cur_idx, 2462d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines added_edges, ARRAY_SIZE(added_edges)); 2472d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 0; i < n_added_edges; i++) { 2482d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (n_edges_ < ARRAY_SIZE(edges_)) { 2492d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Edge e = {(u16)added_edges[i], (u16)cur_idx, 2502d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dtls->findLockContext(added_edges[i]), stk, 2512d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines unique_tid}; 2522d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines edges_[n_edges_++] = e; 2532d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2542d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Printf("Edge%zd: %u %zd=>%zd in T%d\n", 2552d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // n_edges_, stk, added_edges[i], cur_idx, unique_tid); 2562d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2572d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return n_added_edges; 2582d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2592d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2602d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool findEdge(uptr from_node, uptr to_node, u32 *stk_from, u32 *stk_to, 2612d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines int *unique_tid) { 2622d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr from_idx = nodeToIndex(from_node); 2632d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr to_idx = nodeToIndex(to_node); 2642d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 0; i < n_edges_; i++) { 2652d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (edges_[i].from == from_idx && edges_[i].to == to_idx) { 2662d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines *stk_from = edges_[i].stk_from; 2672d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines *stk_to = edges_[i].stk_to; 2682d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines *unique_tid = edges_[i].unique_tid; 2692d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return true; 2702d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2712d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2722d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return false; 2732d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2742d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2752d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Test-only function. Handles the before/after lock events, 2762d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // returns true if there is a cycle. 2772d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool onLock(DeadlockDetectorTLS<BV> *dtls, uptr cur_node, u32 stk = 0) { 2782d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ensureCurrentEpoch(dtls); 2792d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool is_reachable = !isHeld(dtls, cur_node) && onLockBefore(dtls, cur_node); 2802d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines addEdges(dtls, cur_node, stk, 0); 2812d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines onLockAfter(dtls, cur_node, stk); 2822d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return is_reachable; 2832d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2842d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2852d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Handles the try_lock event, returns false. 2862d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // When a try_lock event happens (i.e. a try_lock call succeeds) we need 2872d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // to add this lock to the currently held locks, but we should not try to 2882d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // change the lock graph or to detect a cycle. We may want to investigate 2892d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // whether a more aggressive strategy is possible for try_lock. 2902d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool onTryLock(DeadlockDetectorTLS<BV> *dtls, uptr cur_node, u32 stk = 0) { 2912d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ensureCurrentEpoch(dtls); 2922d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr cur_idx = nodeToIndex(cur_node); 2932d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dtls->addLock(cur_idx, current_epoch_, stk); 2942d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return false; 2952d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2962d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2972d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Returns true iff dtls is empty (no locks are currently held) and we can 2982d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // add the node to the currently held locks w/o chanding the global state. 2992d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // This operation is thread-safe as it only touches the dtls. 3002d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool onFirstLock(DeadlockDetectorTLS<BV> *dtls, uptr node, u32 stk = 0) { 3012d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (!dtls->empty()) return false; 3022d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (dtls->getEpoch() && dtls->getEpoch() == nodeToEpoch(node)) { 3032d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dtls->addLock(nodeToIndexUnchecked(node), nodeToEpoch(node), stk); 3042d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return true; 3052d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 3062d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return false; 3072d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 3082d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3092d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Finds a path between the lock 'cur_node' (currently not held in dtls) 3102d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // and some currently held lock, returns the length of the path 3112d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // or 0 on failure. 3122d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr findPathToLock(DeadlockDetectorTLS<BV> *dtls, uptr cur_node, uptr *path, 3132d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr path_size) { 3142d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines tmp_bv_.copyFrom(dtls->getLocks(current_epoch_)); 3152d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr idx = nodeToIndex(cur_node); 3162d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK(!tmp_bv_.getBit(idx)); 3172d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr res = g_.findShortestPath(idx, tmp_bv_, path, path_size); 3182d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 0; i < res; i++) 3192d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines path[i] = indexToNode(path[i]); 3202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (res) 3212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK_EQ(path[0], cur_node); 3222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return res; 3232d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 3242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3252d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Handle the unlock event. 3262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // This operation is thread-safe as it only touches the dtls. 3272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void onUnlock(DeadlockDetectorTLS<BV> *dtls, uptr node) { 3282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (dtls->getEpoch() == nodeToEpoch(node)) 3292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dtls->removeLock(nodeToIndexUnchecked(node)); 3302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 3312d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Tries to handle the lock event w/o writing to global state. 3332d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Returns true on success. 3342d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // This operation is thread-safe as it only touches the dtls 3352d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // (modulo racy nature of hasAllEdges). 3362d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool onLockFast(DeadlockDetectorTLS<BV> *dtls, uptr node, u32 stk = 0) { 3372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (hasAllEdges(dtls, node)) { 3382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dtls->addLock(nodeToIndexUnchecked(node), nodeToEpoch(node), stk); 3392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return true; 3402d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 3412d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return false; 3422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 3432d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3442d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool isHeld(DeadlockDetectorTLS<BV> *dtls, uptr node) const { 3452d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return dtls->getLocks(current_epoch_).getBit(nodeToIndex(node)); 3462d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 3472d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3482d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr testOnlyGetEpoch() const { return current_epoch_; } 3492d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool testOnlyHasEdge(uptr l1, uptr l2) { 3502d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return g_.hasEdge(nodeToIndex(l1), nodeToIndex(l2)); 3512d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 3522d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // idx1 and idx2 are raw indices to g_, not lock IDs. 3532d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool testOnlyHasEdgeRaw(uptr idx1, uptr idx2) { 3542d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return g_.hasEdge(idx1, idx2); 3552d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 3562d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3572d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void Print() { 3582d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr from = 0; from < size(); from++) 3592d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr to = 0; to < size(); to++) 3602d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (g_.hasEdge(from, to)) 3612d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Printf(" %zx => %zx\n", from, to); 3622d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 3632d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3642d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines private: 3652d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void check_idx(uptr idx) const { CHECK_LT(idx, size()); } 3662d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3672d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void check_node(uptr node) const { 3682d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK_GE(node, size()); 3692d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK_EQ(current_epoch_, nodeToEpoch(node)); 3702d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 3712d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3722d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr indexToNode(uptr idx) const { 3732d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines check_idx(idx); 3742d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return idx + current_epoch_; 3752d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 3762d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3772d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr nodeToIndexUnchecked(uptr node) const { return node % size(); } 3782d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3792d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr nodeToIndex(uptr node) const { 3802d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines check_node(node); 3812d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return nodeToIndexUnchecked(node); 3822d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 3832d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3842d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr nodeToEpoch(uptr node) const { return node / size() * size(); } 3852d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3862d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr getAvailableNode(uptr data) { 3872d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr idx = available_nodes_.getAndClearFirstOne(); 3882d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines data_[idx] = data; 3892d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return indexToNode(idx); 3902d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 3912d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3922d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines struct Edge { 3932d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines u16 from; 3942d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines u16 to; 3952d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines u32 stk_from; 3962d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines u32 stk_to; 3972d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines int unique_tid; 3982d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines }; 3992d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 4002d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr current_epoch_; 4012d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines BV available_nodes_; 4022d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines BV recycled_nodes_; 4032d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines BV tmp_bv_; 4042d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines BVGraph<BV> g_; 4052d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr data_[BV::kSize]; 4062d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Edge edges_[BV::kSize * 32]; 4072d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr n_edges_; 4082d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines}; 4092d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 4102d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} // namespace __sanitizer 4112d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 4122d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#endif // SANITIZER_DEADLOCK_DETECTOR_H 413