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