sync.cpp
1 // Copyright (c) 2011-2021 The Bitcoin Core developers 2 // Distributed under the MIT software license, see the accompanying 3 // file COPYING or http://www.opensource.org/licenses/mit-license.php. 4 5 #include <sync.h> 6 7 #include <logging.h> 8 #include <tinyformat.h> 9 #include <util/strencodings.h> 10 #include <util/threadnames.h> 11 12 #include <map> 13 #include <mutex> 14 #include <set> 15 #include <system_error> 16 #include <thread> 17 #include <type_traits> 18 #include <unordered_map> 19 #include <utility> 20 #include <vector> 21 22 #ifdef DEBUG_LOCKORDER 23 // 24 // Early deadlock detection. 25 // Problem being solved: 26 // Thread 1 locks A, then B, then C 27 // Thread 2 locks D, then C, then A 28 // --> may result in deadlock between the two threads, depending on when they run. 29 // Solution implemented here: 30 // Keep track of pairs of locks: (A before B), (A before C), etc. 31 // Complain if any thread tries to lock in a different order. 32 // 33 34 struct CLockLocation { 35 CLockLocation( 36 const char* pszName, 37 const char* pszFile, 38 int nLine, 39 bool fTryIn, 40 const std::string& thread_name) 41 : fTry(fTryIn), 42 mutexName(pszName), 43 sourceFile(pszFile), 44 m_thread_name(thread_name), 45 sourceLine(nLine) {} 46 47 std::string ToString() const 48 { 49 return strprintf( 50 "'%s' in %s:%s%s (in thread '%s')", 51 mutexName, sourceFile, sourceLine, (fTry ? " (TRY)" : ""), m_thread_name); 52 } 53 54 std::string Name() const 55 { 56 return mutexName; 57 } 58 59 private: 60 bool fTry; 61 std::string mutexName; 62 std::string sourceFile; 63 const std::string& m_thread_name; 64 int sourceLine; 65 }; 66 67 using LockStackItem = std::pair<void*, CLockLocation>; 68 using LockStack = std::vector<LockStackItem>; 69 using LockStacks = std::unordered_map<std::thread::id, LockStack>; 70 71 using LockPair = std::pair<void*, void*>; 72 using LockOrders = std::map<LockPair, LockStack>; 73 using InvLockOrders = std::set<LockPair>; 74 75 struct LockData { 76 LockStacks m_lock_stacks; 77 LockOrders lockorders; 78 InvLockOrders invlockorders; 79 std::mutex dd_mutex; 80 }; 81 82 LockData& GetLockData() { 83 // This approach guarantees that the object is not destroyed until after its last use. 84 // The operating system automatically reclaims all the memory in a program's heap when that program exits. 85 // Since the ~LockData() destructor is never called, the LockData class and all 86 // its subclasses must have implicitly-defined destructors. 87 static LockData& lock_data = *new LockData(); 88 return lock_data; 89 } 90 91 static void potential_deadlock_detected(const LockPair& mismatch, const LockStack& s1, const LockStack& s2) 92 { 93 LogPrintf("POTENTIAL DEADLOCK DETECTED\n"); 94 LogPrintf("Previous lock order was:\n"); 95 for (const LockStackItem& i : s1) { 96 std::string prefix{}; 97 if (i.first == mismatch.first) { 98 prefix = " (1)"; 99 } 100 if (i.first == mismatch.second) { 101 prefix = " (2)"; 102 } 103 LogPrintf("%s %s\n", prefix, i.second.ToString()); 104 } 105 106 std::string mutex_a, mutex_b; 107 LogPrintf("Current lock order is:\n"); 108 for (const LockStackItem& i : s2) { 109 std::string prefix{}; 110 if (i.first == mismatch.first) { 111 prefix = " (1)"; 112 mutex_a = i.second.Name(); 113 } 114 if (i.first == mismatch.second) { 115 prefix = " (2)"; 116 mutex_b = i.second.Name(); 117 } 118 LogPrintf("%s %s\n", prefix, i.second.ToString()); 119 } 120 if (g_debug_lockorder_abort) { 121 tfm::format(std::cerr, "Assertion failed: detected inconsistent lock order for %s, details in debug log.\n", s2.back().second.ToString()); 122 abort(); 123 } 124 throw std::logic_error(strprintf("potential deadlock detected: %s -> %s -> %s", mutex_b, mutex_a, mutex_b)); 125 } 126 127 static void double_lock_detected(const void* mutex, const LockStack& lock_stack) 128 { 129 LogPrintf("DOUBLE LOCK DETECTED\n"); 130 LogPrintf("Lock order:\n"); 131 for (const LockStackItem& i : lock_stack) { 132 std::string prefix{}; 133 if (i.first == mutex) { 134 prefix = " (*)"; 135 } 136 LogPrintf("%s %s\n", prefix, i.second.ToString()); 137 } 138 if (g_debug_lockorder_abort) { 139 tfm::format(std::cerr, 140 "Assertion failed: detected double lock for %s, details in debug log.\n", 141 lock_stack.back().second.ToString()); 142 abort(); 143 } 144 throw std::logic_error("double lock detected"); 145 } 146 147 template <typename MutexType> 148 static void push_lock(MutexType* c, const CLockLocation& locklocation) 149 { 150 constexpr bool is_recursive_mutex = 151 std::is_base_of<RecursiveMutex, MutexType>::value || 152 std::is_base_of<std::recursive_mutex, MutexType>::value; 153 154 LockData& lockdata = GetLockData(); 155 std::lock_guard<std::mutex> lock(lockdata.dd_mutex); 156 157 LockStack& lock_stack = lockdata.m_lock_stacks[std::this_thread::get_id()]; 158 lock_stack.emplace_back(c, locklocation); 159 for (size_t j = 0; j < lock_stack.size() - 1; ++j) { 160 const LockStackItem& i = lock_stack[j]; 161 if (i.first == c) { 162 if (is_recursive_mutex) { 163 break; 164 } 165 // It is not a recursive mutex and it appears in the stack two times: 166 // at position `j` and at the end (which we added just before this loop). 167 // Can't allow locking the same (non-recursive) mutex two times from the 168 // same thread as that results in an undefined behavior. 169 auto lock_stack_copy = lock_stack; 170 lock_stack.pop_back(); 171 double_lock_detected(c, lock_stack_copy); 172 // double_lock_detected() does not return. 173 } 174 175 const LockPair p1 = std::make_pair(i.first, c); 176 if (lockdata.lockorders.count(p1)) 177 continue; 178 179 const LockPair p2 = std::make_pair(c, i.first); 180 if (lockdata.lockorders.count(p2)) { 181 auto lock_stack_copy = lock_stack; 182 lock_stack.pop_back(); 183 potential_deadlock_detected(p1, lockdata.lockorders[p2], lock_stack_copy); 184 // potential_deadlock_detected() does not return. 185 } 186 187 lockdata.lockorders.emplace(p1, lock_stack); 188 lockdata.invlockorders.insert(p2); 189 } 190 } 191 192 static void pop_lock() 193 { 194 LockData& lockdata = GetLockData(); 195 std::lock_guard<std::mutex> lock(lockdata.dd_mutex); 196 197 LockStack& lock_stack = lockdata.m_lock_stacks[std::this_thread::get_id()]; 198 lock_stack.pop_back(); 199 if (lock_stack.empty()) { 200 lockdata.m_lock_stacks.erase(std::this_thread::get_id()); 201 } 202 } 203 204 template <typename MutexType> 205 void EnterCritical(const char* pszName, const char* pszFile, int nLine, MutexType* cs, bool fTry) 206 { 207 push_lock(cs, CLockLocation(pszName, pszFile, nLine, fTry, util::ThreadGetInternalName())); 208 } 209 template void EnterCritical(const char*, const char*, int, Mutex*, bool); 210 template void EnterCritical(const char*, const char*, int, RecursiveMutex*, bool); 211 template void EnterCritical(const char*, const char*, int, std::mutex*, bool); 212 template void EnterCritical(const char*, const char*, int, std::recursive_mutex*, bool); 213 214 void CheckLastCritical(void* cs, std::string& lockname, const char* guardname, const char* file, int line) 215 { 216 LockData& lockdata = GetLockData(); 217 std::lock_guard<std::mutex> lock(lockdata.dd_mutex); 218 219 const LockStack& lock_stack = lockdata.m_lock_stacks[std::this_thread::get_id()]; 220 if (!lock_stack.empty()) { 221 const auto& lastlock = lock_stack.back(); 222 if (lastlock.first == cs) { 223 lockname = lastlock.second.Name(); 224 return; 225 } 226 } 227 228 LogPrintf("INCONSISTENT LOCK ORDER DETECTED\n"); 229 LogPrintf("Current lock order (least recent first) is:\n"); 230 for (const LockStackItem& i : lock_stack) { 231 LogPrintf(" %s\n", i.second.ToString()); 232 } 233 if (g_debug_lockorder_abort) { 234 tfm::format(std::cerr, "%s:%s %s was not most recent critical section locked, details in debug log.\n", file, line, guardname); 235 abort(); 236 } 237 throw std::logic_error(strprintf("%s was not most recent critical section locked", guardname)); 238 } 239 240 void LeaveCritical() 241 { 242 pop_lock(); 243 } 244 245 static std::string LocksHeld() 246 { 247 LockData& lockdata = GetLockData(); 248 std::lock_guard<std::mutex> lock(lockdata.dd_mutex); 249 250 const LockStack& lock_stack = lockdata.m_lock_stacks[std::this_thread::get_id()]; 251 std::string result; 252 for (const LockStackItem& i : lock_stack) 253 result += i.second.ToString() + std::string("\n"); 254 return result; 255 } 256 257 static bool LockHeld(void* mutex) 258 { 259 LockData& lockdata = GetLockData(); 260 std::lock_guard<std::mutex> lock(lockdata.dd_mutex); 261 262 const LockStack& lock_stack = lockdata.m_lock_stacks[std::this_thread::get_id()]; 263 for (const LockStackItem& i : lock_stack) { 264 if (i.first == mutex) return true; 265 } 266 267 return false; 268 } 269 270 template <typename MutexType> 271 void AssertLockHeldInternal(const char* pszName, const char* pszFile, int nLine, MutexType* cs) 272 { 273 if (LockHeld(cs)) return; 274 tfm::format(std::cerr, "Assertion failed: lock %s not held in %s:%i; locks held:\n%s", pszName, pszFile, nLine, LocksHeld()); 275 abort(); 276 } 277 template void AssertLockHeldInternal(const char*, const char*, int, Mutex*); 278 template void AssertLockHeldInternal(const char*, const char*, int, RecursiveMutex*); 279 280 template <typename MutexType> 281 void AssertLockNotHeldInternal(const char* pszName, const char* pszFile, int nLine, MutexType* cs) 282 { 283 if (!LockHeld(cs)) return; 284 tfm::format(std::cerr, "Assertion failed: lock %s held in %s:%i; locks held:\n%s", pszName, pszFile, nLine, LocksHeld()); 285 abort(); 286 } 287 template void AssertLockNotHeldInternal(const char*, const char*, int, Mutex*); 288 template void AssertLockNotHeldInternal(const char*, const char*, int, RecursiveMutex*); 289 290 void DeleteLock(void* cs) 291 { 292 LockData& lockdata = GetLockData(); 293 std::lock_guard<std::mutex> lock(lockdata.dd_mutex); 294 const LockPair item = std::make_pair(cs, nullptr); 295 LockOrders::iterator it = lockdata.lockorders.lower_bound(item); 296 while (it != lockdata.lockorders.end() && it->first.first == cs) { 297 const LockPair invitem = std::make_pair(it->first.second, it->first.first); 298 lockdata.invlockorders.erase(invitem); 299 lockdata.lockorders.erase(it++); 300 } 301 InvLockOrders::iterator invit = lockdata.invlockorders.lower_bound(item); 302 while (invit != lockdata.invlockorders.end() && invit->first == cs) { 303 const LockPair invinvitem = std::make_pair(invit->second, invit->first); 304 lockdata.lockorders.erase(invinvitem); 305 lockdata.invlockorders.erase(invit++); 306 } 307 } 308 309 bool LockStackEmpty() 310 { 311 LockData& lockdata = GetLockData(); 312 std::lock_guard<std::mutex> lock(lockdata.dd_mutex); 313 const auto it = lockdata.m_lock_stacks.find(std::this_thread::get_id()); 314 if (it == lockdata.m_lock_stacks.end()) { 315 return true; 316 } 317 return it->second.empty(); 318 } 319 320 bool g_debug_lockorder_abort = true; 321 322 #endif /* DEBUG_LOCKORDER */