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