sync.cpp
1 // Copyright (c) 2011-present 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 <tinyformat.h> 8 #include <util/log.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 std::string&& thread_name) 41 : fTry(fTryIn), 42 mutexName(pszName), 43 sourceFile(pszFile), 44 m_thread_name(std::move(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 LogError("POTENTIAL DEADLOCK DETECTED"); 94 LogError("Previous lock order was:"); 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 LogError("%s %s", prefix, i.second.ToString()); 104 } 105 106 std::string mutex_a, mutex_b; 107 LogError("Current lock order is:"); 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 LogError("%s %s", 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 LogError("DOUBLE LOCK DETECTED"); 130 LogError("Lock order:"); 131 for (const LockStackItem& i : lock_stack) { 132 std::string prefix{}; 133 if (i.first == mutex) { 134 prefix = " (*)"; 135 } 136 LogError("%s %s", 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_v<RecursiveMutex, MutexType> || 152 std::is_base_of_v<std::recursive_mutex, MutexType>; 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.contains(p1)) 177 continue; 178 179 const LockPair p2 = std::make_pair(c, i.first); 180 if (lockdata.lockorders.contains(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, std::mutex*, bool); 210 template void EnterCritical(const char*, const char*, int, std::recursive_mutex*, bool); 211 212 void CheckLastCritical(void* cs, std::string& lockname, const char* guardname, const char* file, int line) 213 { 214 LockData& lockdata = GetLockData(); 215 std::lock_guard<std::mutex> lock(lockdata.dd_mutex); 216 217 const LockStack& lock_stack = lockdata.m_lock_stacks[std::this_thread::get_id()]; 218 if (!lock_stack.empty()) { 219 const auto& lastlock = lock_stack.back(); 220 if (lastlock.first == cs) { 221 lockname = lastlock.second.Name(); 222 return; 223 } 224 } 225 226 LogError("INCONSISTENT LOCK ORDER DETECTED"); 227 LogError("Current lock order (least recent first) is:"); 228 for (const LockStackItem& i : lock_stack) { 229 LogError(" %s", i.second.ToString()); 230 } 231 if (g_debug_lockorder_abort) { 232 tfm::format(std::cerr, "%s:%s %s was not most recent critical section locked, details in debug log.\n", file, line, guardname); 233 abort(); 234 } 235 throw std::logic_error(strprintf("%s was not most recent critical section locked", guardname)); 236 } 237 238 void LeaveCritical() 239 { 240 pop_lock(); 241 } 242 243 static std::string LocksHeld() 244 { 245 LockData& lockdata = GetLockData(); 246 std::lock_guard<std::mutex> lock(lockdata.dd_mutex); 247 248 const LockStack& lock_stack = lockdata.m_lock_stacks[std::this_thread::get_id()]; 249 std::string result; 250 for (const LockStackItem& i : lock_stack) 251 result += i.second.ToString() + std::string("\n"); 252 return result; 253 } 254 255 static bool LockHeld(void* mutex) 256 { 257 LockData& lockdata = GetLockData(); 258 std::lock_guard<std::mutex> lock(lockdata.dd_mutex); 259 260 const LockStack& lock_stack = lockdata.m_lock_stacks[std::this_thread::get_id()]; 261 for (const LockStackItem& i : lock_stack) { 262 if (i.first == mutex) return true; 263 } 264 265 return false; 266 } 267 268 template <typename MutexType> 269 void AssertLockHeldInternal(const char* pszName, const char* pszFile, int nLine, MutexType* cs) 270 { 271 if (LockHeld(cs)) return; 272 tfm::format(std::cerr, "Assertion failed: lock %s not held in %s:%i; locks held:\n%s", pszName, pszFile, nLine, LocksHeld()); 273 abort(); 274 } 275 template void AssertLockHeldInternal(const char*, const char*, int, Mutex*); 276 template void AssertLockHeldInternal(const char*, const char*, int, RecursiveMutex*); 277 278 template <typename MutexType> 279 void AssertLockNotHeldInternal(const char* pszName, const char* pszFile, int nLine, MutexType* cs) 280 { 281 if (!LockHeld(cs)) return; 282 tfm::format(std::cerr, "Assertion failed: lock %s held in %s:%i; locks held:\n%s", pszName, pszFile, nLine, LocksHeld()); 283 abort(); 284 } 285 template void AssertLockNotHeldInternal(const char*, const char*, int, Mutex*); 286 template void AssertLockNotHeldInternal(const char*, const char*, int, RecursiveMutex*); 287 288 void DeleteLock(void* cs) 289 { 290 LockData& lockdata = GetLockData(); 291 std::lock_guard<std::mutex> lock(lockdata.dd_mutex); 292 const LockPair item = std::make_pair(cs, nullptr); 293 LockOrders::iterator it = lockdata.lockorders.lower_bound(item); 294 while (it != lockdata.lockorders.end() && it->first.first == cs) { 295 const LockPair invitem = std::make_pair(it->first.second, it->first.first); 296 lockdata.invlockorders.erase(invitem); 297 lockdata.lockorders.erase(it++); 298 } 299 InvLockOrders::iterator invit = lockdata.invlockorders.lower_bound(item); 300 while (invit != lockdata.invlockorders.end() && invit->first == cs) { 301 const LockPair invinvitem = std::make_pair(invit->second, invit->first); 302 lockdata.lockorders.erase(invinvitem); 303 lockdata.invlockorders.erase(invit++); 304 } 305 } 306 307 bool LockStackEmpty() 308 { 309 LockData& lockdata = GetLockData(); 310 std::lock_guard<std::mutex> lock(lockdata.dd_mutex); 311 const auto it = lockdata.m_lock_stacks.find(std::this_thread::get_id()); 312 if (it == lockdata.m_lock_stacks.end()) { 313 return true; 314 } 315 return it->second.empty(); 316 } 317 318 bool g_debug_lockorder_abort = true; 319 320 #endif /* DEBUG_LOCKORDER */