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 : : #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 : : 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 : 0 :
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 */
|
