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