Bitcoin Core  22.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 #if defined(HAVE_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  sourceLine(nLine) {}
50 
51  std::string ToString() const
52  {
53  return strprintf(
54  "'%s' in %s:%s%s (in thread '%s')",
55  mutexName, sourceFile, sourceLine, (fTry ? " (TRY)" : ""), m_thread_name);
56  }
57 
58  std::string Name() const
59  {
60  return mutexName;
61  }
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 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  static LockData& lock_data = *new LockData();
92  return lock_data;
93 }
94 
95 static void potential_deadlock_detected(const LockPair& mismatch, const LockStack& s1, const LockStack& s2)
96 {
97  LogPrintf("POTENTIAL DEADLOCK DETECTED\n");
98  LogPrintf("Previous lock order was:\n");
99  for (const LockStackItem& i : s1) {
100  std::string prefix{};
101  if (i.first == mismatch.first) {
102  prefix = " (1)";
103  }
104  if (i.first == mismatch.second) {
105  prefix = " (2)";
106  }
107  LogPrintf("%s %s\n", prefix, i.second.ToString());
108  }
109 
110  std::string mutex_a, mutex_b;
111  LogPrintf("Current lock order is:\n");
112  for (const LockStackItem& i : s2) {
113  std::string prefix{};
114  if (i.first == mismatch.first) {
115  prefix = " (1)";
116  mutex_a = i.second.Name();
117  }
118  if (i.first == mismatch.second) {
119  prefix = " (2)";
120  mutex_b = i.second.Name();
121  }
122  LogPrintf("%s %s\n", prefix, i.second.ToString());
123  }
124  if (g_debug_lockorder_abort) {
125  tfm::format(std::cerr, "Assertion failed: detected inconsistent lock order for %s, details in debug log.\n", s2.back().second.ToString());
126  abort();
127  }
128  throw std::logic_error(strprintf("potential deadlock detected: %s -> %s -> %s", mutex_b, mutex_a, mutex_b));
129 }
130 
131 static void double_lock_detected(const void* mutex, const LockStack& lock_stack)
132 {
133  LogPrintf("DOUBLE LOCK DETECTED\n");
134  LogPrintf("Lock order:\n");
135  for (const LockStackItem& i : lock_stack) {
136  std::string prefix{};
137  if (i.first == mutex) {
138  prefix = " (*)";
139  }
140  LogPrintf("%s %s\n", prefix, i.second.ToString());
141  }
142  if (g_debug_lockorder_abort) {
143  tfm::format(std::cerr,
144  "Assertion failed: detected double lock for %s, details in debug log.\n",
145  lock_stack.back().second.ToString());
146  abort();
147  }
148  throw std::logic_error("double lock detected");
149 }
150 
151 template <typename MutexType>
152 static void push_lock(MutexType* c, const CLockLocation& locklocation)
153 {
154  constexpr bool is_recursive_mutex =
155  std::is_base_of<RecursiveMutex, MutexType>::value ||
156  std::is_base_of<std::recursive_mutex, MutexType>::value;
157 
158  LockData& lockdata = GetLockData();
159  std::lock_guard<std::mutex> lock(lockdata.dd_mutex);
160 
161  LockStack& lock_stack = lockdata.m_lock_stacks[std::this_thread::get_id()];
162  lock_stack.emplace_back(c, locklocation);
163  for (size_t j = 0; j < lock_stack.size() - 1; ++j) {
164  const LockStackItem& i = lock_stack[j];
165  if (i.first == c) {
166  if (is_recursive_mutex) {
167  break;
168  }
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  auto lock_stack_copy = lock_stack;
174  lock_stack.pop_back();
175  double_lock_detected(c, lock_stack_copy);
176  // double_lock_detected() does not return.
177  }
178 
179  const LockPair p1 = std::make_pair(i.first, c);
180  if (lockdata.lockorders.count(p1))
181  continue;
182 
183  const LockPair p2 = std::make_pair(c, i.first);
184  if (lockdata.lockorders.count(p2)) {
185  auto lock_stack_copy = lock_stack;
186  lock_stack.pop_back();
187  potential_deadlock_detected(p1, lockdata.lockorders[p2], lock_stack_copy);
188  // potential_deadlock_detected() does not return.
189  }
190 
191  lockdata.lockorders.emplace(p1, lock_stack);
192  lockdata.invlockorders.insert(p2);
193  }
194 }
195 
196 static void pop_lock()
197 {
198  LockData& lockdata = GetLockData();
199  std::lock_guard<std::mutex> lock(lockdata.dd_mutex);
200 
201  LockStack& lock_stack = lockdata.m_lock_stacks[std::this_thread::get_id()];
202  lock_stack.pop_back();
203  if (lock_stack.empty()) {
204  lockdata.m_lock_stacks.erase(std::this_thread::get_id());
205  }
206 }
207 
208 template <typename MutexType>
209 void EnterCritical(const char* pszName, const char* pszFile, int nLine, MutexType* cs, bool fTry)
210 {
211  push_lock(cs, CLockLocation(pszName, pszFile, nLine, fTry, util::ThreadGetInternalName()));
212 }
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 {
220  LockData& lockdata = GetLockData();
221  std::lock_guard<std::mutex> lock(lockdata.dd_mutex);
222 
223  const LockStack& lock_stack = lockdata.m_lock_stacks[std::this_thread::get_id()];
224  if (!lock_stack.empty()) {
225  const auto& lastlock = lock_stack.back();
226  if (lastlock.first == cs) {
227  lockname = lastlock.second.Name();
228  return;
229  }
230  }
231 
232  LogPrintf("INCONSISTENT LOCK ORDER DETECTED\n");
233  LogPrintf("Current lock order (least recent first) is:\n");
234  for (const LockStackItem& i : lock_stack) {
235  LogPrintf(" %s\n", i.second.ToString());
236  }
237  if (g_debug_lockorder_abort) {
238  tfm::format(std::cerr, "%s:%s %s was not most recent critical section locked, details in debug log.\n", file, line, guardname);
239  abort();
240  }
241  throw std::logic_error(strprintf("%s was not most recent critical section locked", guardname));
242 }
243 
244 void LeaveCritical()
245 {
246  pop_lock();
247 }
248 
249 std::string LocksHeld()
250 {
251  LockData& lockdata = GetLockData();
252  std::lock_guard<std::mutex> lock(lockdata.dd_mutex);
253 
254  const LockStack& lock_stack = lockdata.m_lock_stacks[std::this_thread::get_id()];
255  std::string result;
256  for (const LockStackItem& i : lock_stack)
257  result += i.second.ToString() + std::string("\n");
258  return result;
259 }
260 
261 static bool LockHeld(void* mutex)
262 {
263  LockData& lockdata = GetLockData();
264  std::lock_guard<std::mutex> lock(lockdata.dd_mutex);
265 
266  const LockStack& lock_stack = lockdata.m_lock_stacks[std::this_thread::get_id()];
267  for (const LockStackItem& i : lock_stack) {
268  if (i.first == mutex) return true;
269  }
270 
271  return false;
272 }
273 
274 template <typename MutexType>
275 void AssertLockHeldInternal(const char* pszName, const char* pszFile, int nLine, MutexType* cs)
276 {
277  if (LockHeld(cs)) return;
278  tfm::format(std::cerr, "Assertion failed: lock %s not held in %s:%i; locks held:\n%s", pszName, pszFile, nLine, LocksHeld());
279  abort();
280 }
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 {
287  if (!LockHeld(cs)) return;
288  tfm::format(std::cerr, "Assertion failed: lock %s held in %s:%i; locks held:\n%s", pszName, pszFile, nLine, LocksHeld());
289  abort();
290 }
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 {
296  LockData& lockdata = GetLockData();
297  std::lock_guard<std::mutex> lock(lockdata.dd_mutex);
298  const LockPair item = std::make_pair(cs, nullptr);
299  LockOrders::iterator it = lockdata.lockorders.lower_bound(item);
300  while (it != lockdata.lockorders.end() && it->first.first == cs) {
301  const LockPair invitem = std::make_pair(it->first.second, it->first.first);
302  lockdata.invlockorders.erase(invitem);
303  lockdata.lockorders.erase(it++);
304  }
305  InvLockOrders::iterator invit = lockdata.invlockorders.lower_bound(item);
306  while (invit != lockdata.invlockorders.end() && invit->first == cs) {
307  const LockPair invinvitem = std::make_pair(invit->second, invit->first);
308  lockdata.lockorders.erase(invinvitem);
309  lockdata.invlockorders.erase(invit++);
310  }
311 }
312 
313 bool LockStackEmpty()
314 {
315  LockData& lockdata = GetLockData();
316  std::lock_guard<std::mutex> lock(lockdata.dd_mutex);
317  const auto it = lockdata.m_lock_stacks.find(std::this_thread::get_id());
318  if (it == lockdata.m_lock_stacks.end()) {
319  return true;
320  }
321  return it->second.empty();
322 }
323 
324 bool g_debug_lockorder_abort = true;
325 
326 #endif /* DEBUG_LOCKORDER */
ToString
std::string ToString(const T &t)
Locale-independent version of std::to_string.
Definition: string.h:87
tinyformat::format
void format(std::ostream &out, const char *fmt, const Args &... args)
Format list of arguments to the stream according to given format string.
Definition: tinyformat.h:1062
sync.h
AnnotatedMixin< std::mutex >
CheckLastCritical
void CheckLastCritical(void *cs, std::string &lockname, const char *guardname, const char *file, int line)
Definition: sync.h:75
DeleteLock
void DeleteLock(void *cs)
Definition: sync.h:80
bitcoin-config.h
LeaveCritical
void LeaveCritical()
Definition: sync.h:74
cs
static void pool cs
Definition: mempool_eviction.cpp:12
tinyformat.h
prefix
const char * prefix
Definition: rest.cpp:926
strencodings.h
AssertLockHeldInternal
void AssertLockHeldInternal(const char *pszName, const char *pszFile, int nLine, MutexType *cs) EXCLUSIVE_LOCKS_REQUIRED(cs)
Definition: sync.h:77
util::ThreadGetInternalName
const std::string & ThreadGetInternalName()
Get the thread's internal (in-memory) name; used e.g.
Definition: threadnames.cpp:53
LogPrintf
#define LogPrintf(...)
Definition: logging.h:187
LockStackEmpty
bool LockStackEmpty()
Definition: sync.h:81
strprintf
#define strprintf
Format arguments and return the string or write to given std::ostream (see tinyformat::format doc for...
Definition: tinyformat.h:1164
EnterCritical
void EnterCritical(const char *pszName, const char *pszFile, int nLine, MutexType *cs, bool fTry=false)
Definition: sync.h:73
logging.h
threadnames.h
AssertLockNotHeldInternal
void AssertLockNotHeldInternal(const char *pszName, const char *pszFile, int nLine, MutexType *cs) LOCKS_EXCLUDED(cs)
Definition: sync.h:79