Bitcoin Core 29.99.0
P2P Digital Currency
sync.cpp
Go to the documentation of this file.
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
34struct 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
59private:
60 bool fTry;
61 std::string mutexName;
62 std::string sourceFile;
63 const std::string m_thread_name;
64 int sourceLine;
65};
66
67using LockStackItem = std::pair<void*, CLockLocation>;
68using LockStack = std::vector<LockStackItem>;
69using LockStacks = std::unordered_map<std::thread::id, LockStack>;
70
71using LockPair = std::pair<void*, void*>;
72using LockOrders = std::map<LockPair, LockStack>;
73using InvLockOrders = std::set<LockPair>;
74
75struct LockData {
76 LockStacks m_lock_stacks;
77 LockOrders lockorders;
78 InvLockOrders invlockorders;
79 std::mutex dd_mutex;
80};
81
82LockData& 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
91static 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
127static 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
147template <typename MutexType>
148static 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.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
192static 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
204template <typename MutexType>
205void 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}
209template void EnterCritical(const char*, const char*, int, std::mutex*, bool);
210template void EnterCritical(const char*, const char*, int, std::recursive_mutex*, bool);
211
212void 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 LogPrintf("INCONSISTENT LOCK ORDER DETECTED\n");
227 LogPrintf("Current lock order (least recent first) is:\n");
228 for (const LockStackItem& i : lock_stack) {
229 LogPrintf(" %s\n", 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
238void LeaveCritical()
239{
240 pop_lock();
241}
242
243static 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
255static 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
268template <typename MutexType>
269void 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}
275template void AssertLockHeldInternal(const char*, const char*, int, Mutex*);
276template void AssertLockHeldInternal(const char*, const char*, int, RecursiveMutex*);
277
278template <typename MutexType>
279void 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}
285template void AssertLockNotHeldInternal(const char*, const char*, int, Mutex*);
286template void AssertLockNotHeldInternal(const char*, const char*, int, RecursiveMutex*);
287
288void 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
307bool 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
318bool g_debug_lockorder_abort = true;
319
320#endif /* DEBUG_LOCKORDER */
static void pool cs
#define LogPrintf(...)
Definition: logging.h:361
void format(std::ostream &out, FormatStringCheck< sizeof...(Args)> fmt, const Args &... args)
Format list of arguments to the stream according to given format string.
Definition: tinyformat.h:1079
std::string ThreadGetInternalName()
Get the thread's internal (in-memory) name; used e.g.
Definition: threadnames.cpp:45
std::string ToString(const T &t)
Locale-independent version of std::to_string.
Definition: string.h:245
const char * prefix
Definition: rest.cpp:1117
void AssertLockHeldInternal(const char *pszName, const char *pszFile, int nLine, MutexType *cs) EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: sync.h:74
void EnterCritical(const char *pszName, const char *pszFile, int nLine, MutexType *cs, bool fTry=false)
Definition: sync.h:70
void DeleteLock(void *cs)
Definition: sync.h:77
void CheckLastCritical(void *cs, std::string &lockname, const char *guardname, const char *file, int line)
Definition: sync.h:72
void LeaveCritical()
Definition: sync.h:71
bool LockStackEmpty()
Definition: sync.h:78
void AssertLockNotHeldInternal(const char *pszName, const char *pszFile, int nLine, MutexType *cs) LOCKS_EXCLUDED(cs)
Definition: sync.h:76
#define strprintf
Format arguments and return the string or write to given std::ostream (see tinyformat::format doc for...
Definition: tinyformat.h:1172