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