1276789Sdim//===-- sanitizer_deadlock_detector.h ---------------------------*- C++ -*-===// 2276789Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6276789Sdim// 7276789Sdim//===----------------------------------------------------------------------===// 8276789Sdim// 9276789Sdim// This file is a part of Sanitizer runtime. 10276789Sdim// The deadlock detector maintains a directed graph of lock acquisitions. 11276789Sdim// When a lock event happens, the detector checks if the locks already held by 12276789Sdim// the current thread are reachable from the newly acquired lock. 13276789Sdim// 14276789Sdim// The detector can handle only a fixed amount of simultaneously live locks 15276789Sdim// (a lock is alive if it has been locked at least once and has not been 16276789Sdim// destroyed). When the maximal number of locks is reached the entire graph 17276789Sdim// is flushed and the new lock epoch is started. The node ids from the old 18276789Sdim// epochs can not be used with any of the detector methods except for 19276789Sdim// nodeBelongsToCurrentEpoch(). 20276789Sdim// 21276789Sdim// FIXME: this is work in progress, nothing really works yet. 22276789Sdim// 23276789Sdim//===----------------------------------------------------------------------===// 24276789Sdim 25276789Sdim#ifndef SANITIZER_DEADLOCK_DETECTOR_H 26276789Sdim#define SANITIZER_DEADLOCK_DETECTOR_H 27276789Sdim 28353358Sdim#include "sanitizer_bvgraph.h" 29276789Sdim#include "sanitizer_common.h" 30276789Sdim 31276789Sdimnamespace __sanitizer { 32276789Sdim 33276789Sdim// Thread-local state for DeadlockDetector. 34276789Sdim// It contains the locks currently held by the owning thread. 35276789Sdimtemplate <class BV> 36276789Sdimclass DeadlockDetectorTLS { 37276789Sdim public: 38276789Sdim // No CTOR. 39276789Sdim void clear() { 40276789Sdim bv_.clear(); 41276789Sdim epoch_ = 0; 42276789Sdim n_recursive_locks = 0; 43276789Sdim n_all_locks_ = 0; 44276789Sdim } 45276789Sdim 46276789Sdim bool empty() const { return bv_.empty(); } 47276789Sdim 48276789Sdim void ensureCurrentEpoch(uptr current_epoch) { 49276789Sdim if (epoch_ == current_epoch) return; 50276789Sdim bv_.clear(); 51276789Sdim epoch_ = current_epoch; 52280031Sdim n_recursive_locks = 0; 53280031Sdim n_all_locks_ = 0; 54276789Sdim } 55276789Sdim 56276789Sdim uptr getEpoch() const { return epoch_; } 57276789Sdim 58276789Sdim // Returns true if this is the first (non-recursive) acquisition of this lock. 59276789Sdim bool addLock(uptr lock_id, uptr current_epoch, u32 stk) { 60276789Sdim CHECK_EQ(epoch_, current_epoch); 61276789Sdim if (!bv_.setBit(lock_id)) { 62276789Sdim // The lock is already held by this thread, it must be recursive. 63276789Sdim CHECK_LT(n_recursive_locks, ARRAY_SIZE(recursive_locks)); 64276789Sdim recursive_locks[n_recursive_locks++] = lock_id; 65276789Sdim return false; 66276789Sdim } 67276789Sdim CHECK_LT(n_all_locks_, ARRAY_SIZE(all_locks_with_contexts_)); 68276789Sdim // lock_id < BV::kSize, can cast to a smaller int. 69276789Sdim u32 lock_id_short = static_cast<u32>(lock_id); 70276789Sdim LockWithContext l = {lock_id_short, stk}; 71276789Sdim all_locks_with_contexts_[n_all_locks_++] = l; 72276789Sdim return true; 73276789Sdim } 74276789Sdim 75276789Sdim void removeLock(uptr lock_id) { 76276789Sdim if (n_recursive_locks) { 77276789Sdim for (sptr i = n_recursive_locks - 1; i >= 0; i--) { 78276789Sdim if (recursive_locks[i] == lock_id) { 79276789Sdim n_recursive_locks--; 80276789Sdim Swap(recursive_locks[i], recursive_locks[n_recursive_locks]); 81276789Sdim return; 82276789Sdim } 83276789Sdim } 84276789Sdim } 85280031Sdim if (!bv_.clearBit(lock_id)) 86280031Sdim return; // probably addLock happened before flush 87276789Sdim if (n_all_locks_) { 88276789Sdim for (sptr i = n_all_locks_ - 1; i >= 0; i--) { 89276789Sdim if (all_locks_with_contexts_[i].lock == static_cast<u32>(lock_id)) { 90276789Sdim Swap(all_locks_with_contexts_[i], 91276789Sdim all_locks_with_contexts_[n_all_locks_ - 1]); 92276789Sdim n_all_locks_--; 93276789Sdim break; 94276789Sdim } 95276789Sdim } 96276789Sdim } 97276789Sdim } 98276789Sdim 99276789Sdim u32 findLockContext(uptr lock_id) { 100276789Sdim for (uptr i = 0; i < n_all_locks_; i++) 101276789Sdim if (all_locks_with_contexts_[i].lock == static_cast<u32>(lock_id)) 102276789Sdim return all_locks_with_contexts_[i].stk; 103276789Sdim return 0; 104276789Sdim } 105276789Sdim 106276789Sdim const BV &getLocks(uptr current_epoch) const { 107276789Sdim CHECK_EQ(epoch_, current_epoch); 108276789Sdim return bv_; 109276789Sdim } 110276789Sdim 111276789Sdim uptr getNumLocks() const { return n_all_locks_; } 112276789Sdim uptr getLock(uptr idx) const { return all_locks_with_contexts_[idx].lock; } 113276789Sdim 114276789Sdim private: 115276789Sdim BV bv_; 116276789Sdim uptr epoch_; 117276789Sdim uptr recursive_locks[64]; 118276789Sdim uptr n_recursive_locks; 119276789Sdim struct LockWithContext { 120276789Sdim u32 lock; 121276789Sdim u32 stk; 122276789Sdim }; 123276789Sdim LockWithContext all_locks_with_contexts_[64]; 124276789Sdim uptr n_all_locks_; 125276789Sdim}; 126276789Sdim 127276789Sdim// DeadlockDetector. 128276789Sdim// For deadlock detection to work we need one global DeadlockDetector object 129276789Sdim// and one DeadlockDetectorTLS object per evey thread. 130276789Sdim// This class is not thread safe, all concurrent accesses should be guarded 131276789Sdim// by an external lock. 132276789Sdim// Most of the methods of this class are not thread-safe (i.e. should 133276789Sdim// be protected by an external lock) unless explicitly told otherwise. 134276789Sdimtemplate <class BV> 135276789Sdimclass DeadlockDetector { 136276789Sdim public: 137276789Sdim typedef BV BitVector; 138276789Sdim 139276789Sdim uptr size() const { return g_.size(); } 140276789Sdim 141276789Sdim // No CTOR. 142276789Sdim void clear() { 143276789Sdim current_epoch_ = 0; 144276789Sdim available_nodes_.clear(); 145276789Sdim recycled_nodes_.clear(); 146276789Sdim g_.clear(); 147276789Sdim n_edges_ = 0; 148276789Sdim } 149276789Sdim 150276789Sdim // Allocate new deadlock detector node. 151276789Sdim // If we are out of available nodes first try to recycle some. 152276789Sdim // If there is nothing to recycle, flush the graph and increment the epoch. 153276789Sdim // Associate 'data' (opaque user's object) with the new node. 154276789Sdim uptr newNode(uptr data) { 155276789Sdim if (!available_nodes_.empty()) 156276789Sdim return getAvailableNode(data); 157276789Sdim if (!recycled_nodes_.empty()) { 158276789Sdim for (sptr i = n_edges_ - 1; i >= 0; i--) { 159276789Sdim if (recycled_nodes_.getBit(edges_[i].from) || 160276789Sdim recycled_nodes_.getBit(edges_[i].to)) { 161276789Sdim Swap(edges_[i], edges_[n_edges_ - 1]); 162276789Sdim n_edges_--; 163276789Sdim } 164276789Sdim } 165276789Sdim CHECK(available_nodes_.empty()); 166276789Sdim // removeEdgesFrom was called in removeNode. 167276789Sdim g_.removeEdgesTo(recycled_nodes_); 168276789Sdim available_nodes_.setUnion(recycled_nodes_); 169276789Sdim recycled_nodes_.clear(); 170276789Sdim return getAvailableNode(data); 171276789Sdim } 172276789Sdim // We are out of vacant nodes. Flush and increment the current_epoch_. 173276789Sdim current_epoch_ += size(); 174276789Sdim recycled_nodes_.clear(); 175276789Sdim available_nodes_.setAll(); 176276789Sdim g_.clear(); 177280031Sdim n_edges_ = 0; 178276789Sdim return getAvailableNode(data); 179276789Sdim } 180276789Sdim 181276789Sdim // Get data associated with the node created by newNode(). 182276789Sdim uptr getData(uptr node) const { return data_[nodeToIndex(node)]; } 183276789Sdim 184276789Sdim bool nodeBelongsToCurrentEpoch(uptr node) { 185276789Sdim return node && (node / size() * size()) == current_epoch_; 186276789Sdim } 187276789Sdim 188276789Sdim void removeNode(uptr node) { 189276789Sdim uptr idx = nodeToIndex(node); 190276789Sdim CHECK(!available_nodes_.getBit(idx)); 191276789Sdim CHECK(recycled_nodes_.setBit(idx)); 192276789Sdim g_.removeEdgesFrom(idx); 193276789Sdim } 194276789Sdim 195276789Sdim void ensureCurrentEpoch(DeadlockDetectorTLS<BV> *dtls) { 196276789Sdim dtls->ensureCurrentEpoch(current_epoch_); 197276789Sdim } 198276789Sdim 199276789Sdim // Returns true if there is a cycle in the graph after this lock event. 200276789Sdim // Ideally should be called before the lock is acquired so that we can 201276789Sdim // report a deadlock before a real deadlock happens. 202276789Sdim bool onLockBefore(DeadlockDetectorTLS<BV> *dtls, uptr cur_node) { 203276789Sdim ensureCurrentEpoch(dtls); 204276789Sdim uptr cur_idx = nodeToIndex(cur_node); 205276789Sdim return g_.isReachable(cur_idx, dtls->getLocks(current_epoch_)); 206276789Sdim } 207276789Sdim 208276789Sdim u32 findLockContext(DeadlockDetectorTLS<BV> *dtls, uptr node) { 209276789Sdim return dtls->findLockContext(nodeToIndex(node)); 210276789Sdim } 211276789Sdim 212276789Sdim // Add cur_node to the set of locks held currently by dtls. 213276789Sdim void onLockAfter(DeadlockDetectorTLS<BV> *dtls, uptr cur_node, u32 stk = 0) { 214276789Sdim ensureCurrentEpoch(dtls); 215276789Sdim uptr cur_idx = nodeToIndex(cur_node); 216276789Sdim dtls->addLock(cur_idx, current_epoch_, stk); 217276789Sdim } 218276789Sdim 219276789Sdim // Experimental *racy* fast path function. 220276789Sdim // Returns true if all edges from the currently held locks to cur_node exist. 221276789Sdim bool hasAllEdges(DeadlockDetectorTLS<BV> *dtls, uptr cur_node) { 222276789Sdim uptr local_epoch = dtls->getEpoch(); 223276789Sdim // Read from current_epoch_ is racy. 224276789Sdim if (cur_node && local_epoch == current_epoch_ && 225276789Sdim local_epoch == nodeToEpoch(cur_node)) { 226276789Sdim uptr cur_idx = nodeToIndexUnchecked(cur_node); 227276789Sdim for (uptr i = 0, n = dtls->getNumLocks(); i < n; i++) { 228276789Sdim if (!g_.hasEdge(dtls->getLock(i), cur_idx)) 229276789Sdim return false; 230276789Sdim } 231276789Sdim return true; 232276789Sdim } 233276789Sdim return false; 234276789Sdim } 235276789Sdim 236276789Sdim // Adds edges from currently held locks to cur_node, 237276789Sdim // returns the number of added edges, and puts the sources of added edges 238276789Sdim // into added_edges[]. 239276789Sdim // Should be called before onLockAfter. 240276789Sdim uptr addEdges(DeadlockDetectorTLS<BV> *dtls, uptr cur_node, u32 stk, 241276789Sdim int unique_tid) { 242276789Sdim ensureCurrentEpoch(dtls); 243276789Sdim uptr cur_idx = nodeToIndex(cur_node); 244276789Sdim uptr added_edges[40]; 245276789Sdim uptr n_added_edges = g_.addEdges(dtls->getLocks(current_epoch_), cur_idx, 246276789Sdim added_edges, ARRAY_SIZE(added_edges)); 247276789Sdim for (uptr i = 0; i < n_added_edges; i++) { 248276789Sdim if (n_edges_ < ARRAY_SIZE(edges_)) { 249276789Sdim Edge e = {(u16)added_edges[i], (u16)cur_idx, 250276789Sdim dtls->findLockContext(added_edges[i]), stk, 251276789Sdim unique_tid}; 252276789Sdim edges_[n_edges_++] = e; 253276789Sdim } 254276789Sdim } 255276789Sdim return n_added_edges; 256276789Sdim } 257276789Sdim 258276789Sdim bool findEdge(uptr from_node, uptr to_node, u32 *stk_from, u32 *stk_to, 259276789Sdim int *unique_tid) { 260276789Sdim uptr from_idx = nodeToIndex(from_node); 261276789Sdim uptr to_idx = nodeToIndex(to_node); 262276789Sdim for (uptr i = 0; i < n_edges_; i++) { 263276789Sdim if (edges_[i].from == from_idx && edges_[i].to == to_idx) { 264276789Sdim *stk_from = edges_[i].stk_from; 265276789Sdim *stk_to = edges_[i].stk_to; 266276789Sdim *unique_tid = edges_[i].unique_tid; 267276789Sdim return true; 268276789Sdim } 269276789Sdim } 270276789Sdim return false; 271276789Sdim } 272276789Sdim 273276789Sdim // Test-only function. Handles the before/after lock events, 274276789Sdim // returns true if there is a cycle. 275276789Sdim bool onLock(DeadlockDetectorTLS<BV> *dtls, uptr cur_node, u32 stk = 0) { 276276789Sdim ensureCurrentEpoch(dtls); 277276789Sdim bool is_reachable = !isHeld(dtls, cur_node) && onLockBefore(dtls, cur_node); 278276789Sdim addEdges(dtls, cur_node, stk, 0); 279276789Sdim onLockAfter(dtls, cur_node, stk); 280276789Sdim return is_reachable; 281276789Sdim } 282276789Sdim 283276789Sdim // Handles the try_lock event, returns false. 284276789Sdim // When a try_lock event happens (i.e. a try_lock call succeeds) we need 285276789Sdim // to add this lock to the currently held locks, but we should not try to 286276789Sdim // change the lock graph or to detect a cycle. We may want to investigate 287276789Sdim // whether a more aggressive strategy is possible for try_lock. 288276789Sdim bool onTryLock(DeadlockDetectorTLS<BV> *dtls, uptr cur_node, u32 stk = 0) { 289276789Sdim ensureCurrentEpoch(dtls); 290276789Sdim uptr cur_idx = nodeToIndex(cur_node); 291276789Sdim dtls->addLock(cur_idx, current_epoch_, stk); 292276789Sdim return false; 293276789Sdim } 294276789Sdim 295276789Sdim // Returns true iff dtls is empty (no locks are currently held) and we can 296276789Sdim // add the node to the currently held locks w/o chanding the global state. 297276789Sdim // This operation is thread-safe as it only touches the dtls. 298276789Sdim bool onFirstLock(DeadlockDetectorTLS<BV> *dtls, uptr node, u32 stk = 0) { 299276789Sdim if (!dtls->empty()) return false; 300276789Sdim if (dtls->getEpoch() && dtls->getEpoch() == nodeToEpoch(node)) { 301276789Sdim dtls->addLock(nodeToIndexUnchecked(node), nodeToEpoch(node), stk); 302276789Sdim return true; 303276789Sdim } 304276789Sdim return false; 305276789Sdim } 306276789Sdim 307276789Sdim // Finds a path between the lock 'cur_node' (currently not held in dtls) 308276789Sdim // and some currently held lock, returns the length of the path 309276789Sdim // or 0 on failure. 310276789Sdim uptr findPathToLock(DeadlockDetectorTLS<BV> *dtls, uptr cur_node, uptr *path, 311276789Sdim uptr path_size) { 312276789Sdim tmp_bv_.copyFrom(dtls->getLocks(current_epoch_)); 313276789Sdim uptr idx = nodeToIndex(cur_node); 314276789Sdim CHECK(!tmp_bv_.getBit(idx)); 315276789Sdim uptr res = g_.findShortestPath(idx, tmp_bv_, path, path_size); 316276789Sdim for (uptr i = 0; i < res; i++) 317276789Sdim path[i] = indexToNode(path[i]); 318276789Sdim if (res) 319276789Sdim CHECK_EQ(path[0], cur_node); 320276789Sdim return res; 321276789Sdim } 322276789Sdim 323276789Sdim // Handle the unlock event. 324276789Sdim // This operation is thread-safe as it only touches the dtls. 325276789Sdim void onUnlock(DeadlockDetectorTLS<BV> *dtls, uptr node) { 326276789Sdim if (dtls->getEpoch() == nodeToEpoch(node)) 327276789Sdim dtls->removeLock(nodeToIndexUnchecked(node)); 328276789Sdim } 329276789Sdim 330276789Sdim // Tries to handle the lock event w/o writing to global state. 331276789Sdim // Returns true on success. 332276789Sdim // This operation is thread-safe as it only touches the dtls 333276789Sdim // (modulo racy nature of hasAllEdges). 334276789Sdim bool onLockFast(DeadlockDetectorTLS<BV> *dtls, uptr node, u32 stk = 0) { 335276789Sdim if (hasAllEdges(dtls, node)) { 336276789Sdim dtls->addLock(nodeToIndexUnchecked(node), nodeToEpoch(node), stk); 337276789Sdim return true; 338276789Sdim } 339276789Sdim return false; 340276789Sdim } 341276789Sdim 342276789Sdim bool isHeld(DeadlockDetectorTLS<BV> *dtls, uptr node) const { 343276789Sdim return dtls->getLocks(current_epoch_).getBit(nodeToIndex(node)); 344276789Sdim } 345276789Sdim 346276789Sdim uptr testOnlyGetEpoch() const { return current_epoch_; } 347276789Sdim bool testOnlyHasEdge(uptr l1, uptr l2) { 348276789Sdim return g_.hasEdge(nodeToIndex(l1), nodeToIndex(l2)); 349276789Sdim } 350276789Sdim // idx1 and idx2 are raw indices to g_, not lock IDs. 351276789Sdim bool testOnlyHasEdgeRaw(uptr idx1, uptr idx2) { 352276789Sdim return g_.hasEdge(idx1, idx2); 353276789Sdim } 354276789Sdim 355276789Sdim void Print() { 356276789Sdim for (uptr from = 0; from < size(); from++) 357276789Sdim for (uptr to = 0; to < size(); to++) 358276789Sdim if (g_.hasEdge(from, to)) 359276789Sdim Printf(" %zx => %zx\n", from, to); 360276789Sdim } 361276789Sdim 362276789Sdim private: 363276789Sdim void check_idx(uptr idx) const { CHECK_LT(idx, size()); } 364276789Sdim 365276789Sdim void check_node(uptr node) const { 366276789Sdim CHECK_GE(node, size()); 367276789Sdim CHECK_EQ(current_epoch_, nodeToEpoch(node)); 368276789Sdim } 369276789Sdim 370276789Sdim uptr indexToNode(uptr idx) const { 371276789Sdim check_idx(idx); 372276789Sdim return idx + current_epoch_; 373276789Sdim } 374276789Sdim 375276789Sdim uptr nodeToIndexUnchecked(uptr node) const { return node % size(); } 376276789Sdim 377276789Sdim uptr nodeToIndex(uptr node) const { 378276789Sdim check_node(node); 379276789Sdim return nodeToIndexUnchecked(node); 380276789Sdim } 381276789Sdim 382276789Sdim uptr nodeToEpoch(uptr node) const { return node / size() * size(); } 383276789Sdim 384276789Sdim uptr getAvailableNode(uptr data) { 385276789Sdim uptr idx = available_nodes_.getAndClearFirstOne(); 386276789Sdim data_[idx] = data; 387276789Sdim return indexToNode(idx); 388276789Sdim } 389276789Sdim 390276789Sdim struct Edge { 391276789Sdim u16 from; 392276789Sdim u16 to; 393276789Sdim u32 stk_from; 394276789Sdim u32 stk_to; 395276789Sdim int unique_tid; 396276789Sdim }; 397276789Sdim 398276789Sdim uptr current_epoch_; 399276789Sdim BV available_nodes_; 400276789Sdim BV recycled_nodes_; 401276789Sdim BV tmp_bv_; 402276789Sdim BVGraph<BV> g_; 403276789Sdim uptr data_[BV::kSize]; 404276789Sdim Edge edges_[BV::kSize * 32]; 405276789Sdim uptr n_edges_; 406276789Sdim}; 407276789Sdim 408276789Sdim} // namespace __sanitizer 409276789Sdim 410276789Sdim#endif // SANITIZER_DEADLOCK_DETECTOR_H 411