sync.cpp raw
1 // Copyright (c) 2011-2021 The Limenka 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
34 struct 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
59 private:
60 bool fTry;
61 std::string mutexName;
62 std::string sourceFile;
63 const std::string m_thread_name;
64 int sourceLine;
65 };
66
67 using LockStackItem = std::pair<void*, CLockLocation>;
68 using LockStack = std::vector<LockStackItem>;
69 using LockStacks = std::unordered_map<std::thread::id, LockStack>;
70
71 using LockPair = std::pair<void*, void*>;
72 using LockOrders = std::map<LockPair, LockStack>;
73 using InvLockOrders = std::set<LockPair>;
74
75 struct LockData {
76 LockStacks m_lock_stacks;
77 LockOrders lockorders;
78 InvLockOrders invlockorders;
79 std::mutex dd_mutex;
80 };
81
82 LockData& 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
91 static void potential_deadlock_detected(const LockPair& mismatch, const LockStack& s1, const LockStack& s2)
92 {
93 LogError("POTENTIAL DEADLOCK DETECTED");
94 LogError("Previous lock order was:");
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 LogError("%s %s", prefix, i.second.ToString());
104 }
105
106 std::string mutex_a, mutex_b;
107 LogError("Current lock order is:");
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 LogError("%s %s", 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
127 static void double_lock_detected(const void* mutex, const LockStack& lock_stack)
128 {
129 LogError("DOUBLE LOCK DETECTED");
130 LogError("Lock order:");
131 for (const LockStackItem& i : lock_stack) {
132 std::string prefix{};
133 if (i.first == mutex) {
134 prefix = " (*)";
135 }
136 LogError("%s %s", 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
147 template <typename MutexType>
148 static void push_lock(MutexType* c, const CLockLocation& locklocation)
149 {
150 constexpr bool is_recursive_mutex =
151 std::is_base_of<RecursiveMutex, MutexType>::value ||
152 std::is_base_of<std::recursive_mutex, MutexType>::value;
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
192 static 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
204 template <typename MutexType>
205 void 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 }
209 template void EnterCritical(const char*, const char*, int, Mutex*, bool);
210 template void EnterCritical(const char*, const char*, int, RecursiveMutex*, bool);
211 template void EnterCritical(const char*, const char*, int, std::mutex*, bool);
212 template void EnterCritical(const char*, const char*, int, std::recursive_mutex*, bool);
213
214 void CheckLastCritical(void* cs, std::string& lockname, const char* guardname, const char* file, int line)
215 {
216 LockData& lockdata = GetLockData();
217 std::lock_guard<std::mutex> lock(lockdata.dd_mutex);
218
219 const LockStack& lock_stack = lockdata.m_lock_stacks[std::this_thread::get_id()];
220 if (!lock_stack.empty()) {
221 const auto& lastlock = lock_stack.back();
222 if (lastlock.first == cs) {
223 lockname = lastlock.second.Name();
224 return;
225 }
226 }
227
228 LogError("INCONSISTENT LOCK ORDER DETECTED");
229 LogError("Current lock order (least recent first) is:");
230 for (const LockStackItem& i : lock_stack) {
231 LogError(" %s", i.second.ToString());
232 }
233 if (g_debug_lockorder_abort) {
234 tfm::format(std::cerr, "%s:%s %s was not most recent critical section locked, details in debug log.\n", file, line, guardname);
235 abort();
236 }
237 throw std::logic_error(strprintf("%s was not most recent critical section locked", guardname));
238 }
239
240 void LeaveCritical()
241 {
242 pop_lock();
243 }
244
245 static std::string LocksHeld()
246 {
247 LockData& lockdata = GetLockData();
248 std::lock_guard<std::mutex> lock(lockdata.dd_mutex);
249
250 const LockStack& lock_stack = lockdata.m_lock_stacks[std::this_thread::get_id()];
251 std::string result;
252 for (const LockStackItem& i : lock_stack)
253 result += i.second.ToString() + std::string("\n");
254 return result;
255 }
256
257 static bool LockHeld(void* mutex)
258 {
259 LockData& lockdata = GetLockData();
260 std::lock_guard<std::mutex> lock(lockdata.dd_mutex);
261
262 const LockStack& lock_stack = lockdata.m_lock_stacks[std::this_thread::get_id()];
263 for (const LockStackItem& i : lock_stack) {
264 if (i.first == mutex) return true;
265 }
266
267 return false;
268 }
269
270 template <typename MutexType>
271 void AssertLockHeldInternal(const char* pszName, const char* pszFile, int nLine, MutexType* cs)
272 {
273 if (LockHeld(cs)) return;
274 tfm::format(std::cerr, "Assertion failed: lock %s not held in %s:%i; locks held:\n%s", pszName, pszFile, nLine, LocksHeld());
275 abort();
276 }
277 template void AssertLockHeldInternal(const char*, const char*, int, Mutex*);
278 template void AssertLockHeldInternal(const char*, const char*, int, RecursiveMutex*);
279
280 template <typename MutexType>
281 void AssertLockNotHeldInternal(const char* pszName, const char* pszFile, int nLine, MutexType* cs)
282 {
283 if (!LockHeld(cs)) return;
284 tfm::format(std::cerr, "Assertion failed: lock %s held in %s:%i; locks held:\n%s", pszName, pszFile, nLine, LocksHeld());
285 abort();
286 }
287 template void AssertLockNotHeldInternal(const char*, const char*, int, Mutex*);
288 template void AssertLockNotHeldInternal(const char*, const char*, int, RecursiveMutex*);
289
290 void DeleteLock(void* cs)
291 {
292 LockData& lockdata = GetLockData();
293 std::lock_guard<std::mutex> lock(lockdata.dd_mutex);
294 const LockPair item = std::make_pair(cs, nullptr);
295 LockOrders::iterator it = lockdata.lockorders.lower_bound(item);
296 while (it != lockdata.lockorders.end() && it->first.first == cs) {
297 const LockPair invitem = std::make_pair(it->first.second, it->first.first);
298 lockdata.invlockorders.erase(invitem);
299 lockdata.lockorders.erase(it++);
300 }
301 InvLockOrders::iterator invit = lockdata.invlockorders.lower_bound(item);
302 while (invit != lockdata.invlockorders.end() && invit->first == cs) {
303 const LockPair invinvitem = std::make_pair(invit->second, invit->first);
304 lockdata.lockorders.erase(invinvitem);
305 lockdata.invlockorders.erase(invit++);
306 }
307 }
308
309 bool LockStackEmpty()
310 {
311 LockData& lockdata = GetLockData();
312 std::lock_guard<std::mutex> lock(lockdata.dd_mutex);
313 const auto it = lockdata.m_lock_stacks.find(std::this_thread::get_id());
314 if (it == lockdata.m_lock_stacks.end()) {
315 return true;
316 }
317 return it->second.empty();
318 }
319
320 bool g_debug_lockorder_abort = true;
321
322 #endif /* DEBUG_LOCKORDER */
323