/src/abseil-cpp/absl/synchronization/mutex.cc
Line | Count | Source (jump to first uncovered line) |
1 | | // Copyright 2017 The Abseil Authors. |
2 | | // |
3 | | // Licensed under the Apache License, Version 2.0 (the "License"); |
4 | | // you may not use this file except in compliance with the License. |
5 | | // You may obtain a copy of the License at |
6 | | // |
7 | | // https://www.apache.org/licenses/LICENSE-2.0 |
8 | | // |
9 | | // Unless required by applicable law or agreed to in writing, software |
10 | | // distributed under the License is distributed on an "AS IS" BASIS, |
11 | | // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
12 | | // See the License for the specific language governing permissions and |
13 | | // limitations under the License. |
14 | | |
15 | | #include "absl/synchronization/mutex.h" |
16 | | |
17 | | #ifdef _WIN32 |
18 | | #include <windows.h> |
19 | | #ifdef ERROR |
20 | | #undef ERROR |
21 | | #endif |
22 | | #else |
23 | | #include <fcntl.h> |
24 | | #include <pthread.h> |
25 | | #include <sched.h> |
26 | | #include <sys/time.h> |
27 | | #endif |
28 | | |
29 | | #include <assert.h> |
30 | | #include <errno.h> |
31 | | #include <stdio.h> |
32 | | #include <stdlib.h> |
33 | | #include <string.h> |
34 | | #include <time.h> |
35 | | |
36 | | #include <algorithm> |
37 | | #include <atomic> |
38 | | #include <cstddef> |
39 | | #include <cstdlib> |
40 | | #include <cstring> |
41 | | #include <thread> // NOLINT(build/c++11) |
42 | | |
43 | | #include "absl/base/attributes.h" |
44 | | #include "absl/base/call_once.h" |
45 | | #include "absl/base/config.h" |
46 | | #include "absl/base/dynamic_annotations.h" |
47 | | #include "absl/base/internal/atomic_hook.h" |
48 | | #include "absl/base/internal/cycleclock.h" |
49 | | #include "absl/base/internal/hide_ptr.h" |
50 | | #include "absl/base/internal/low_level_alloc.h" |
51 | | #include "absl/base/internal/raw_logging.h" |
52 | | #include "absl/base/internal/spinlock.h" |
53 | | #include "absl/base/internal/sysinfo.h" |
54 | | #include "absl/base/internal/thread_identity.h" |
55 | | #include "absl/base/internal/tsan_mutex_interface.h" |
56 | | #include "absl/base/optimization.h" |
57 | | #include "absl/debugging/stacktrace.h" |
58 | | #include "absl/debugging/symbolize.h" |
59 | | #include "absl/synchronization/internal/graphcycles.h" |
60 | | #include "absl/synchronization/internal/per_thread_sem.h" |
61 | | #include "absl/time/time.h" |
62 | | |
63 | | using absl::base_internal::CurrentThreadIdentityIfPresent; |
64 | | using absl::base_internal::CycleClock; |
65 | | using absl::base_internal::PerThreadSynch; |
66 | | using absl::base_internal::SchedulingGuard; |
67 | | using absl::base_internal::ThreadIdentity; |
68 | | using absl::synchronization_internal::GetOrCreateCurrentThreadIdentity; |
69 | | using absl::synchronization_internal::GraphCycles; |
70 | | using absl::synchronization_internal::GraphId; |
71 | | using absl::synchronization_internal::InvalidGraphId; |
72 | | using absl::synchronization_internal::KernelTimeout; |
73 | | using absl::synchronization_internal::PerThreadSem; |
74 | | |
75 | | extern "C" { |
76 | 0 | ABSL_ATTRIBUTE_WEAK void ABSL_INTERNAL_C_SYMBOL(AbslInternalMutexYield)() { |
77 | 0 | std::this_thread::yield(); |
78 | 0 | } |
79 | | } // extern "C" |
80 | | |
81 | | namespace absl { |
82 | | ABSL_NAMESPACE_BEGIN |
83 | | |
84 | | namespace { |
85 | | |
86 | | #if defined(ABSL_HAVE_THREAD_SANITIZER) |
87 | | constexpr OnDeadlockCycle kDeadlockDetectionDefault = OnDeadlockCycle::kIgnore; |
88 | | #else |
89 | | constexpr OnDeadlockCycle kDeadlockDetectionDefault = OnDeadlockCycle::kAbort; |
90 | | #endif |
91 | | |
92 | | ABSL_CONST_INIT std::atomic<OnDeadlockCycle> synch_deadlock_detection( |
93 | | kDeadlockDetectionDefault); |
94 | | ABSL_CONST_INIT std::atomic<bool> synch_check_invariants(false); |
95 | | |
96 | | ABSL_INTERNAL_ATOMIC_HOOK_ATTRIBUTES |
97 | | absl::base_internal::AtomicHook<void (*)(int64_t wait_cycles)> |
98 | | submit_profile_data; |
99 | | ABSL_INTERNAL_ATOMIC_HOOK_ATTRIBUTES absl::base_internal::AtomicHook<void (*)( |
100 | | const char* msg, const void* obj, int64_t wait_cycles)> |
101 | | mutex_tracer; |
102 | | ABSL_INTERNAL_ATOMIC_HOOK_ATTRIBUTES |
103 | | absl::base_internal::AtomicHook<void (*)(const char* msg, const void* cv)> |
104 | | cond_var_tracer; |
105 | | |
106 | | } // namespace |
107 | | |
108 | | static inline bool EvalConditionAnnotated(const Condition* cond, Mutex* mu, |
109 | | bool locking, bool trylock, |
110 | | bool read_lock); |
111 | | |
112 | 0 | void RegisterMutexProfiler(void (*fn)(int64_t wait_cycles)) { |
113 | 0 | submit_profile_data.Store(fn); |
114 | 0 | } |
115 | | |
116 | | void RegisterMutexTracer(void (*fn)(const char* msg, const void* obj, |
117 | 0 | int64_t wait_cycles)) { |
118 | 0 | mutex_tracer.Store(fn); |
119 | 0 | } |
120 | | |
121 | 0 | void RegisterCondVarTracer(void (*fn)(const char* msg, const void* cv)) { |
122 | 0 | cond_var_tracer.Store(fn); |
123 | 0 | } |
124 | | |
125 | | namespace { |
126 | | // Represents the strategy for spin and yield. |
127 | | // See the comment in GetMutexGlobals() for more information. |
128 | | enum DelayMode { AGGRESSIVE, GENTLE }; |
129 | | |
130 | | struct ABSL_CACHELINE_ALIGNED MutexGlobals { |
131 | | absl::once_flag once; |
132 | | // Note: this variable is initialized separately in Mutex::LockSlow, |
133 | | // so that Mutex::Lock does not have a stack frame in optimized build. |
134 | | std::atomic<int> spinloop_iterations{0}; |
135 | | int32_t mutex_sleep_spins[2] = {}; |
136 | | absl::Duration mutex_sleep_time; |
137 | | }; |
138 | | |
139 | | ABSL_CONST_INIT static MutexGlobals globals; |
140 | | |
141 | 0 | absl::Duration MeasureTimeToYield() { |
142 | 0 | absl::Time before = absl::Now(); |
143 | 0 | ABSL_INTERNAL_C_SYMBOL(AbslInternalMutexYield)(); |
144 | 0 | return absl::Now() - before; |
145 | 0 | } |
146 | | |
147 | 0 | const MutexGlobals& GetMutexGlobals() { |
148 | 0 | absl::base_internal::LowLevelCallOnce(&globals.once, [&]() { |
149 | 0 | if (absl::base_internal::NumCPUs() > 1) { |
150 | | // If the mode is aggressive then spin many times before yielding. |
151 | | // If the mode is gentle then spin only a few times before yielding. |
152 | | // Aggressive spinning is used to ensure that an Unlock() call, |
153 | | // which must get the spin lock for any thread to make progress gets it |
154 | | // without undue delay. |
155 | 0 | globals.mutex_sleep_spins[AGGRESSIVE] = 5000; |
156 | 0 | globals.mutex_sleep_spins[GENTLE] = 250; |
157 | 0 | globals.mutex_sleep_time = absl::Microseconds(10); |
158 | 0 | } else { |
159 | | // If this a uniprocessor, only yield/sleep. Real-time threads are often |
160 | | // unable to yield, so the sleep time needs to be long enough to keep |
161 | | // the calling thread asleep until scheduling happens. |
162 | 0 | globals.mutex_sleep_spins[AGGRESSIVE] = 0; |
163 | 0 | globals.mutex_sleep_spins[GENTLE] = 0; |
164 | 0 | globals.mutex_sleep_time = MeasureTimeToYield() * 5; |
165 | 0 | globals.mutex_sleep_time = |
166 | 0 | std::min(globals.mutex_sleep_time, absl::Milliseconds(1)); |
167 | 0 | globals.mutex_sleep_time = |
168 | 0 | std::max(globals.mutex_sleep_time, absl::Microseconds(10)); |
169 | 0 | } |
170 | 0 | }); |
171 | 0 | return globals; |
172 | 0 | } |
173 | | } // namespace |
174 | | |
175 | | namespace synchronization_internal { |
176 | | // Returns the Mutex delay on iteration `c` depending on the given `mode`. |
177 | | // The returned value should be used as `c` for the next call to `MutexDelay`. |
178 | 0 | int MutexDelay(int32_t c, int mode) { |
179 | 0 | const int32_t limit = GetMutexGlobals().mutex_sleep_spins[mode]; |
180 | 0 | const absl::Duration sleep_time = GetMutexGlobals().mutex_sleep_time; |
181 | 0 | if (c < limit) { |
182 | | // Spin. |
183 | 0 | c++; |
184 | 0 | } else { |
185 | 0 | SchedulingGuard::ScopedEnable enable_rescheduling; |
186 | 0 | ABSL_TSAN_MUTEX_PRE_DIVERT(nullptr, 0); |
187 | 0 | if (c == limit) { |
188 | | // Yield once. |
189 | 0 | ABSL_INTERNAL_C_SYMBOL(AbslInternalMutexYield)(); |
190 | 0 | c++; |
191 | 0 | } else { |
192 | | // Then wait. |
193 | 0 | absl::SleepFor(sleep_time); |
194 | 0 | c = 0; |
195 | 0 | } |
196 | 0 | ABSL_TSAN_MUTEX_POST_DIVERT(nullptr, 0); |
197 | 0 | } |
198 | 0 | return c; |
199 | 0 | } |
200 | | } // namespace synchronization_internal |
201 | | |
202 | | // --------------------------Generic atomic ops |
203 | | // Ensure that "(*pv & bits) == bits" by doing an atomic update of "*pv" to |
204 | | // "*pv | bits" if necessary. Wait until (*pv & wait_until_clear)==0 |
205 | | // before making any change. |
206 | | // Returns true if bits were previously unset and set by the call. |
207 | | // This is used to set flags in mutex and condition variable words. |
208 | | static bool AtomicSetBits(std::atomic<intptr_t>* pv, intptr_t bits, |
209 | 0 | intptr_t wait_until_clear) { |
210 | 0 | for (;;) { |
211 | 0 | intptr_t v = pv->load(std::memory_order_relaxed); |
212 | 0 | if ((v & bits) == bits) { |
213 | 0 | return false; |
214 | 0 | } |
215 | 0 | if ((v & wait_until_clear) != 0) { |
216 | 0 | continue; |
217 | 0 | } |
218 | 0 | if (pv->compare_exchange_weak(v, v | bits, std::memory_order_release, |
219 | 0 | std::memory_order_relaxed)) { |
220 | 0 | return true; |
221 | 0 | } |
222 | 0 | } |
223 | 0 | } |
224 | | |
225 | | //------------------------------------------------------------------ |
226 | | |
227 | | // Data for doing deadlock detection. |
228 | | ABSL_CONST_INIT static absl::base_internal::SpinLock deadlock_graph_mu( |
229 | | absl::kConstInit, base_internal::SCHEDULE_KERNEL_ONLY); |
230 | | |
231 | | // Graph used to detect deadlocks. |
232 | | ABSL_CONST_INIT static GraphCycles* deadlock_graph |
233 | | ABSL_GUARDED_BY(deadlock_graph_mu) ABSL_PT_GUARDED_BY(deadlock_graph_mu); |
234 | | |
235 | | //------------------------------------------------------------------ |
236 | | // An event mechanism for debugging mutex use. |
237 | | // It also allows mutexes to be given names for those who can't handle |
238 | | // addresses, and instead like to give their data structures names like |
239 | | // "Henry", "Fido", or "Rupert IV, King of Yondavia". |
240 | | |
241 | | namespace { // to prevent name pollution |
242 | | enum { // Mutex and CondVar events passed as "ev" to PostSynchEvent |
243 | | // Mutex events |
244 | | SYNCH_EV_TRYLOCK_SUCCESS, |
245 | | SYNCH_EV_TRYLOCK_FAILED, |
246 | | SYNCH_EV_READERTRYLOCK_SUCCESS, |
247 | | SYNCH_EV_READERTRYLOCK_FAILED, |
248 | | SYNCH_EV_LOCK, |
249 | | SYNCH_EV_LOCK_RETURNING, |
250 | | SYNCH_EV_READERLOCK, |
251 | | SYNCH_EV_READERLOCK_RETURNING, |
252 | | SYNCH_EV_UNLOCK, |
253 | | SYNCH_EV_READERUNLOCK, |
254 | | |
255 | | // CondVar events |
256 | | SYNCH_EV_WAIT, |
257 | | SYNCH_EV_WAIT_RETURNING, |
258 | | SYNCH_EV_SIGNAL, |
259 | | SYNCH_EV_SIGNALALL, |
260 | | }; |
261 | | |
262 | | enum { // Event flags |
263 | | SYNCH_F_R = 0x01, // reader event |
264 | | SYNCH_F_LCK = 0x02, // PostSynchEvent called with mutex held |
265 | | SYNCH_F_TRY = 0x04, // TryLock or ReaderTryLock |
266 | | SYNCH_F_UNLOCK = 0x08, // Unlock or ReaderUnlock |
267 | | |
268 | | SYNCH_F_LCK_W = SYNCH_F_LCK, |
269 | | SYNCH_F_LCK_R = SYNCH_F_LCK | SYNCH_F_R, |
270 | | }; |
271 | | } // anonymous namespace |
272 | | |
273 | | // Properties of the events. |
274 | | static const struct { |
275 | | int flags; |
276 | | const char* msg; |
277 | | } event_properties[] = { |
278 | | {SYNCH_F_LCK_W | SYNCH_F_TRY, "TryLock succeeded "}, |
279 | | {0, "TryLock failed "}, |
280 | | {SYNCH_F_LCK_R | SYNCH_F_TRY, "ReaderTryLock succeeded "}, |
281 | | {0, "ReaderTryLock failed "}, |
282 | | {0, "Lock blocking "}, |
283 | | {SYNCH_F_LCK_W, "Lock returning "}, |
284 | | {0, "ReaderLock blocking "}, |
285 | | {SYNCH_F_LCK_R, "ReaderLock returning "}, |
286 | | {SYNCH_F_LCK_W | SYNCH_F_UNLOCK, "Unlock "}, |
287 | | {SYNCH_F_LCK_R | SYNCH_F_UNLOCK, "ReaderUnlock "}, |
288 | | {0, "Wait on "}, |
289 | | {0, "Wait unblocked "}, |
290 | | {0, "Signal on "}, |
291 | | {0, "SignalAll on "}, |
292 | | }; |
293 | | |
294 | | ABSL_CONST_INIT static absl::base_internal::SpinLock synch_event_mu( |
295 | | absl::kConstInit, base_internal::SCHEDULE_KERNEL_ONLY); |
296 | | |
297 | | // Hash table size; should be prime > 2. |
298 | | // Can't be too small, as it's used for deadlock detection information. |
299 | | static constexpr uint32_t kNSynchEvent = 1031; |
300 | | |
301 | | static struct SynchEvent { // this is a trivial hash table for the events |
302 | | // struct is freed when refcount reaches 0 |
303 | | int refcount ABSL_GUARDED_BY(synch_event_mu); |
304 | | |
305 | | // buckets have linear, 0-terminated chains |
306 | | SynchEvent* next ABSL_GUARDED_BY(synch_event_mu); |
307 | | |
308 | | // Constant after initialization |
309 | | uintptr_t masked_addr; // object at this address is called "name" |
310 | | |
311 | | // No explicit synchronization used. Instead we assume that the |
312 | | // client who enables/disables invariants/logging on a Mutex does so |
313 | | // while the Mutex is not being concurrently accessed by others. |
314 | | void (*invariant)(void* arg); // called on each event |
315 | | void* arg; // first arg to (*invariant)() |
316 | | bool log; // logging turned on |
317 | | |
318 | | // Constant after initialization |
319 | | char name[1]; // actually longer---NUL-terminated string |
320 | | }* synch_event[kNSynchEvent] ABSL_GUARDED_BY(synch_event_mu); |
321 | | |
322 | | // Ensure that the object at "addr" has a SynchEvent struct associated with it, |
323 | | // set "bits" in the word there (waiting until lockbit is clear before doing |
324 | | // so), and return a refcounted reference that will remain valid until |
325 | | // UnrefSynchEvent() is called. If a new SynchEvent is allocated, |
326 | | // the string name is copied into it. |
327 | | // When used with a mutex, the caller should also ensure that kMuEvent |
328 | | // is set in the mutex word, and similarly for condition variables and kCVEvent. |
329 | | static SynchEvent* EnsureSynchEvent(std::atomic<intptr_t>* addr, |
330 | | const char* name, intptr_t bits, |
331 | 0 | intptr_t lockbit) { |
332 | 0 | uint32_t h = reinterpret_cast<uintptr_t>(addr) % kNSynchEvent; |
333 | 0 | synch_event_mu.Lock(); |
334 | | // When a Mutex/CondVar is destroyed, we don't remove the associated |
335 | | // SynchEvent to keep destructors empty in release builds for performance |
336 | | // reasons. If the current call is the first to set bits (kMuEvent/kCVEvent), |
337 | | // we don't look up the existing even because (if it exists, it must be for |
338 | | // the previous Mutex/CondVar that existed at the same address). |
339 | | // The leaking events must not be a problem for tests, which should create |
340 | | // bounded amount of events. And debug logging is not supposed to be enabled |
341 | | // in production. However, if it's accidentally enabled, or briefly enabled |
342 | | // for some debugging, we don't want to crash the program. Instead we drop |
343 | | // all events, if we accumulated too many of them. Size of a single event |
344 | | // is ~48 bytes, so 100K events is ~5 MB. |
345 | | // Additionally we could delete the old event for the same address, |
346 | | // but it would require a better hashmap (if we accumulate too many events, |
347 | | // linked lists will grow and traversing them will be very slow). |
348 | 0 | constexpr size_t kMaxSynchEventCount = 100 << 10; |
349 | | // Total number of live synch events. |
350 | 0 | static size_t synch_event_count ABSL_GUARDED_BY(synch_event_mu); |
351 | 0 | if (++synch_event_count > kMaxSynchEventCount) { |
352 | 0 | synch_event_count = 0; |
353 | 0 | ABSL_RAW_LOG(ERROR, |
354 | 0 | "Accumulated %zu Mutex debug objects. If you see this" |
355 | 0 | " in production, it may mean that the production code" |
356 | 0 | " accidentally calls " |
357 | 0 | "Mutex/CondVar::EnableDebugLog/EnableInvariantDebugging.", |
358 | 0 | kMaxSynchEventCount); |
359 | 0 | for (auto*& head : synch_event) { |
360 | 0 | for (auto* e = head; e != nullptr;) { |
361 | 0 | SynchEvent* next = e->next; |
362 | 0 | if (--(e->refcount) == 0) { |
363 | 0 | base_internal::LowLevelAlloc::Free(e); |
364 | 0 | } |
365 | 0 | e = next; |
366 | 0 | } |
367 | 0 | head = nullptr; |
368 | 0 | } |
369 | 0 | } |
370 | 0 | SynchEvent* e = nullptr; |
371 | 0 | if (!AtomicSetBits(addr, bits, lockbit)) { |
372 | 0 | for (e = synch_event[h]; |
373 | 0 | e != nullptr && e->masked_addr != base_internal::HidePtr(addr); |
374 | 0 | e = e->next) { |
375 | 0 | } |
376 | 0 | } |
377 | 0 | if (e == nullptr) { // no SynchEvent struct found; make one. |
378 | 0 | if (name == nullptr) { |
379 | 0 | name = ""; |
380 | 0 | } |
381 | 0 | size_t l = strlen(name); |
382 | 0 | e = reinterpret_cast<SynchEvent*>( |
383 | 0 | base_internal::LowLevelAlloc::Alloc(sizeof(*e) + l)); |
384 | 0 | e->refcount = 2; // one for return value, one for linked list |
385 | 0 | e->masked_addr = base_internal::HidePtr(addr); |
386 | 0 | e->invariant = nullptr; |
387 | 0 | e->arg = nullptr; |
388 | 0 | e->log = false; |
389 | 0 | strcpy(e->name, name); // NOLINT(runtime/printf) |
390 | 0 | e->next = synch_event[h]; |
391 | 0 | synch_event[h] = e; |
392 | 0 | } else { |
393 | 0 | e->refcount++; // for return value |
394 | 0 | } |
395 | 0 | synch_event_mu.Unlock(); |
396 | 0 | return e; |
397 | 0 | } |
398 | | |
399 | | // Decrement the reference count of *e, or do nothing if e==null. |
400 | 0 | static void UnrefSynchEvent(SynchEvent* e) { |
401 | 0 | if (e != nullptr) { |
402 | 0 | synch_event_mu.Lock(); |
403 | 0 | bool del = (--(e->refcount) == 0); |
404 | 0 | synch_event_mu.Unlock(); |
405 | 0 | if (del) { |
406 | 0 | base_internal::LowLevelAlloc::Free(e); |
407 | 0 | } |
408 | 0 | } |
409 | 0 | } |
410 | | |
411 | | // Return a refcounted reference to the SynchEvent of the object at address |
412 | | // "addr", if any. The pointer returned is valid until the UnrefSynchEvent() is |
413 | | // called. |
414 | 0 | static SynchEvent* GetSynchEvent(const void* addr) { |
415 | 0 | uint32_t h = reinterpret_cast<uintptr_t>(addr) % kNSynchEvent; |
416 | 0 | SynchEvent* e; |
417 | 0 | synch_event_mu.Lock(); |
418 | 0 | for (e = synch_event[h]; |
419 | 0 | e != nullptr && e->masked_addr != base_internal::HidePtr(addr); |
420 | 0 | e = e->next) { |
421 | 0 | } |
422 | 0 | if (e != nullptr) { |
423 | 0 | e->refcount++; |
424 | 0 | } |
425 | 0 | synch_event_mu.Unlock(); |
426 | 0 | return e; |
427 | 0 | } |
428 | | |
429 | | // Called when an event "ev" occurs on a Mutex of CondVar "obj" |
430 | | // if event recording is on |
431 | 0 | static void PostSynchEvent(void* obj, int ev) { |
432 | 0 | SynchEvent* e = GetSynchEvent(obj); |
433 | | // logging is on if event recording is on and either there's no event struct, |
434 | | // or it explicitly says to log |
435 | 0 | if (e == nullptr || e->log) { |
436 | 0 | void* pcs[40]; |
437 | 0 | int n = absl::GetStackTrace(pcs, ABSL_ARRAYSIZE(pcs), 1); |
438 | | // A buffer with enough space for the ASCII for all the PCs, even on a |
439 | | // 64-bit machine. |
440 | 0 | char buffer[ABSL_ARRAYSIZE(pcs) * 24]; |
441 | 0 | int pos = snprintf(buffer, sizeof(buffer), " @"); |
442 | 0 | for (int i = 0; i != n; i++) { |
443 | 0 | int b = snprintf(&buffer[pos], sizeof(buffer) - static_cast<size_t>(pos), |
444 | 0 | " %p", pcs[i]); |
445 | 0 | if (b < 0 || |
446 | 0 | static_cast<size_t>(b) >= sizeof(buffer) - static_cast<size_t>(pos)) { |
447 | 0 | break; |
448 | 0 | } |
449 | 0 | pos += b; |
450 | 0 | } |
451 | 0 | ABSL_RAW_LOG(INFO, "%s%p %s %s", event_properties[ev].msg, obj, |
452 | 0 | (e == nullptr ? "" : e->name), buffer); |
453 | 0 | } |
454 | 0 | const int flags = event_properties[ev].flags; |
455 | 0 | if ((flags & SYNCH_F_LCK) != 0 && e != nullptr && e->invariant != nullptr) { |
456 | | // Calling the invariant as is causes problems under ThreadSanitizer. |
457 | | // We are currently inside of Mutex Lock/Unlock and are ignoring all |
458 | | // memory accesses and synchronization. If the invariant transitively |
459 | | // synchronizes something else and we ignore the synchronization, we will |
460 | | // get false positive race reports later. |
461 | | // Reuse EvalConditionAnnotated to properly call into user code. |
462 | 0 | struct local { |
463 | 0 | static bool pred(SynchEvent* ev) { |
464 | 0 | (*ev->invariant)(ev->arg); |
465 | 0 | return false; |
466 | 0 | } |
467 | 0 | }; |
468 | 0 | Condition cond(&local::pred, e); |
469 | 0 | Mutex* mu = static_cast<Mutex*>(obj); |
470 | 0 | const bool locking = (flags & SYNCH_F_UNLOCK) == 0; |
471 | 0 | const bool trylock = (flags & SYNCH_F_TRY) != 0; |
472 | 0 | const bool read_lock = (flags & SYNCH_F_R) != 0; |
473 | 0 | EvalConditionAnnotated(&cond, mu, locking, trylock, read_lock); |
474 | 0 | } |
475 | 0 | UnrefSynchEvent(e); |
476 | 0 | } |
477 | | |
478 | | //------------------------------------------------------------------ |
479 | | |
480 | | // The SynchWaitParams struct encapsulates the way in which a thread is waiting: |
481 | | // whether it has a timeout, the condition, exclusive/shared, and whether a |
482 | | // condition variable wait has an associated Mutex (as opposed to another |
483 | | // type of lock). It also points to the PerThreadSynch struct of its thread. |
484 | | // cv_word tells Enqueue() to enqueue on a CondVar using CondVarEnqueue(). |
485 | | // |
486 | | // This structure is held on the stack rather than directly in |
487 | | // PerThreadSynch because a thread can be waiting on multiple Mutexes if, |
488 | | // while waiting on one Mutex, the implementation calls a client callback |
489 | | // (such as a Condition function) that acquires another Mutex. We don't |
490 | | // strictly need to allow this, but programmers become confused if we do not |
491 | | // allow them to use functions such a LOG() within Condition functions. The |
492 | | // PerThreadSynch struct points at the most recent SynchWaitParams struct when |
493 | | // the thread is on a Mutex's waiter queue. |
494 | | struct SynchWaitParams { |
495 | | SynchWaitParams(Mutex::MuHow how_arg, const Condition* cond_arg, |
496 | | KernelTimeout timeout_arg, Mutex* cvmu_arg, |
497 | | PerThreadSynch* thread_arg, |
498 | | std::atomic<intptr_t>* cv_word_arg) |
499 | 0 | : how(how_arg), |
500 | 0 | cond(cond_arg), |
501 | 0 | timeout(timeout_arg), |
502 | 0 | cvmu(cvmu_arg), |
503 | 0 | thread(thread_arg), |
504 | 0 | cv_word(cv_word_arg), |
505 | 0 | contention_start_cycles(CycleClock::Now()), |
506 | 0 | should_submit_contention_data(false) {} |
507 | | |
508 | | const Mutex::MuHow how; // How this thread needs to wait. |
509 | | const Condition* cond; // The condition that this thread is waiting for. |
510 | | // In Mutex, this field is set to zero if a timeout |
511 | | // expires. |
512 | | KernelTimeout timeout; // timeout expiry---absolute time |
513 | | // In Mutex, this field is set to zero if a timeout |
514 | | // expires. |
515 | | Mutex* const cvmu; // used for transfer from cond var to mutex |
516 | | PerThreadSynch* const thread; // thread that is waiting |
517 | | |
518 | | // If not null, thread should be enqueued on the CondVar whose state |
519 | | // word is cv_word instead of queueing normally on the Mutex. |
520 | | std::atomic<intptr_t>* cv_word; |
521 | | |
522 | | int64_t contention_start_cycles; // Time (in cycles) when this thread started |
523 | | // to contend for the mutex. |
524 | | bool should_submit_contention_data; |
525 | | }; |
526 | | |
527 | | struct SynchLocksHeld { |
528 | | int n; // number of valid entries in locks[] |
529 | | bool overflow; // true iff we overflowed the array at some point |
530 | | struct { |
531 | | Mutex* mu; // lock acquired |
532 | | int32_t count; // times acquired |
533 | | GraphId id; // deadlock_graph id of acquired lock |
534 | | } locks[40]; |
535 | | // If a thread overfills the array during deadlock detection, we |
536 | | // continue, discarding information as needed. If no overflow has |
537 | | // taken place, we can provide more error checking, such as |
538 | | // detecting when a thread releases a lock it does not hold. |
539 | | }; |
540 | | |
541 | | // A sentinel value in lists that is not 0. |
542 | | // A 0 value is used to mean "not on a list". |
543 | | static PerThreadSynch* const kPerThreadSynchNull = |
544 | | reinterpret_cast<PerThreadSynch*>(1); |
545 | | |
546 | 1 | static SynchLocksHeld* LocksHeldAlloc() { |
547 | 1 | SynchLocksHeld* ret = reinterpret_cast<SynchLocksHeld*>( |
548 | 1 | base_internal::LowLevelAlloc::Alloc(sizeof(SynchLocksHeld))); |
549 | 1 | ret->n = 0; |
550 | 1 | ret->overflow = false; |
551 | 1 | return ret; |
552 | 1 | } |
553 | | |
554 | | // Return the PerThreadSynch-struct for this thread. |
555 | 1.10M | static PerThreadSynch* Synch_GetPerThread() { |
556 | 1.10M | ThreadIdentity* identity = GetOrCreateCurrentThreadIdentity(); |
557 | 1.10M | return &identity->per_thread_synch; |
558 | 1.10M | } |
559 | | |
560 | 0 | static PerThreadSynch* Synch_GetPerThreadAnnotated(Mutex* mu) { |
561 | 0 | if (mu) { |
562 | 0 | ABSL_TSAN_MUTEX_PRE_DIVERT(mu, 0); |
563 | 0 | } |
564 | 0 | PerThreadSynch* w = Synch_GetPerThread(); |
565 | 0 | if (mu) { |
566 | 0 | ABSL_TSAN_MUTEX_POST_DIVERT(mu, 0); |
567 | 0 | } |
568 | 0 | return w; |
569 | 0 | } |
570 | | |
571 | 1.10M | static SynchLocksHeld* Synch_GetAllLocks() { |
572 | 1.10M | PerThreadSynch* s = Synch_GetPerThread(); |
573 | 1.10M | if (s->all_locks == nullptr) { |
574 | 1 | s->all_locks = LocksHeldAlloc(); // Freed by ReclaimThreadIdentity. |
575 | 1 | } |
576 | 1.10M | return s->all_locks; |
577 | 1.10M | } |
578 | | |
579 | | // Post on "w"'s associated PerThreadSem. |
580 | 0 | void Mutex::IncrementSynchSem(Mutex* mu, PerThreadSynch* w) { |
581 | 0 | static_cast<void>(mu); // Prevent unused param warning in non-TSAN builds. |
582 | 0 | ABSL_TSAN_MUTEX_PRE_DIVERT(mu, 0); |
583 | | // We miss synchronization around passing PerThreadSynch between threads |
584 | | // since it happens inside of the Mutex code, so we need to ignore all |
585 | | // accesses to the object. |
586 | 0 | ABSL_ANNOTATE_IGNORE_READS_AND_WRITES_BEGIN(); |
587 | 0 | PerThreadSem::Post(w->thread_identity()); |
588 | 0 | ABSL_ANNOTATE_IGNORE_READS_AND_WRITES_END(); |
589 | 0 | ABSL_TSAN_MUTEX_POST_DIVERT(mu, 0); |
590 | 0 | } |
591 | | |
592 | | // Wait on "w"'s associated PerThreadSem; returns false if timeout expired. |
593 | 0 | bool Mutex::DecrementSynchSem(Mutex* mu, PerThreadSynch* w, KernelTimeout t) { |
594 | 0 | static_cast<void>(mu); // Prevent unused param warning in non-TSAN builds. |
595 | 0 | ABSL_TSAN_MUTEX_PRE_DIVERT(mu, 0); |
596 | 0 | assert(w == Synch_GetPerThread()); |
597 | 0 | static_cast<void>(w); |
598 | 0 | bool res = PerThreadSem::Wait(t); |
599 | 0 | ABSL_TSAN_MUTEX_POST_DIVERT(mu, 0); |
600 | 0 | return res; |
601 | 0 | } |
602 | | |
603 | | // We're in a fatal signal handler that hopes to use Mutex and to get |
604 | | // lucky by not deadlocking. We try to improve its chances of success |
605 | | // by effectively disabling some of the consistency checks. This will |
606 | | // prevent certain ABSL_RAW_CHECK() statements from being triggered when |
607 | | // re-rentry is detected. The ABSL_RAW_CHECK() statements are those in the |
608 | | // Mutex code checking that the "waitp" field has not been reused. |
609 | 0 | void Mutex::InternalAttemptToUseMutexInFatalSignalHandler() { |
610 | | // Fix the per-thread state only if it exists. |
611 | 0 | ThreadIdentity* identity = CurrentThreadIdentityIfPresent(); |
612 | 0 | if (identity != nullptr) { |
613 | 0 | identity->per_thread_synch.suppress_fatal_errors = true; |
614 | 0 | } |
615 | | // Don't do deadlock detection when we are already failing. |
616 | 0 | synch_deadlock_detection.store(OnDeadlockCycle::kIgnore, |
617 | 0 | std::memory_order_release); |
618 | 0 | } |
619 | | |
620 | | // --------------------------Mutexes |
621 | | |
622 | | // In the layout below, the msb of the bottom byte is currently unused. Also, |
623 | | // the following constraints were considered in choosing the layout: |
624 | | // o Both the debug allocator's "uninitialized" and "freed" patterns (0xab and |
625 | | // 0xcd) are illegal: reader and writer lock both held. |
626 | | // o kMuWriter and kMuEvent should exceed kMuDesig and kMuWait, to enable the |
627 | | // bit-twiddling trick in Mutex::Unlock(). |
628 | | // o kMuWriter / kMuReader == kMuWrWait / kMuWait, |
629 | | // to enable the bit-twiddling trick in CheckForMutexCorruption(). |
630 | | static const intptr_t kMuReader = 0x0001L; // a reader holds the lock |
631 | | // There's a designated waker. |
632 | | // INVARIANT1: there's a thread that was blocked on the mutex, is |
633 | | // no longer, yet has not yet acquired the mutex. If there's a |
634 | | // designated waker, all threads can avoid taking the slow path in |
635 | | // unlock because the designated waker will subsequently acquire |
636 | | // the lock and wake someone. To maintain INVARIANT1 the bit is |
637 | | // set when a thread is unblocked(INV1a), and threads that were |
638 | | // unblocked reset the bit when they either acquire or re-block (INV1b). |
639 | | static const intptr_t kMuDesig = 0x0002L; |
640 | | static const intptr_t kMuWait = 0x0004L; // threads are waiting |
641 | | static const intptr_t kMuWriter = 0x0008L; // a writer holds the lock |
642 | | static const intptr_t kMuEvent = 0x0010L; // record this mutex's events |
643 | | // Runnable writer is waiting for a reader. |
644 | | // If set, new readers will not lock the mutex to avoid writer starvation. |
645 | | // Note: if a reader has higher priority than the writer, it will still lock |
646 | | // the mutex ahead of the waiting writer, but in a very inefficient manner: |
647 | | // the reader will first queue itself and block, but then the last unlocking |
648 | | // reader will wake it. |
649 | | static const intptr_t kMuWrWait = 0x0020L; |
650 | | static const intptr_t kMuSpin = 0x0040L; // spinlock protects wait list |
651 | | static const intptr_t kMuLow = 0x00ffL; // mask all mutex bits |
652 | | static const intptr_t kMuHigh = ~kMuLow; // mask pointer/reader count |
653 | | |
654 | | static_assert((0xab & (kMuWriter | kMuReader)) == (kMuWriter | kMuReader), |
655 | | "The debug allocator's uninitialized pattern (0xab) must be an " |
656 | | "invalid mutex state"); |
657 | | static_assert((0xcd & (kMuWriter | kMuReader)) == (kMuWriter | kMuReader), |
658 | | "The debug allocator's freed pattern (0xcd) must be an invalid " |
659 | | "mutex state"); |
660 | | |
661 | | // Hack to make constant values available to gdb pretty printer |
662 | | enum { |
663 | | kGdbMuSpin = kMuSpin, |
664 | | kGdbMuEvent = kMuEvent, |
665 | | kGdbMuWait = kMuWait, |
666 | | kGdbMuWriter = kMuWriter, |
667 | | kGdbMuDesig = kMuDesig, |
668 | | kGdbMuWrWait = kMuWrWait, |
669 | | kGdbMuReader = kMuReader, |
670 | | kGdbMuLow = kMuLow, |
671 | | }; |
672 | | |
673 | | // kMuWrWait implies kMuWait. |
674 | | // kMuReader and kMuWriter are mutually exclusive. |
675 | | // If kMuReader is zero, there are no readers. |
676 | | // Otherwise, if kMuWait is zero, the high order bits contain a count of the |
677 | | // number of readers. Otherwise, the reader count is held in |
678 | | // PerThreadSynch::readers of the most recently queued waiter, again in the |
679 | | // bits above kMuLow. |
680 | | static const intptr_t kMuOne = 0x0100; // a count of one reader |
681 | | |
682 | | // flags passed to Enqueue and LockSlow{,WithTimeout,Loop} |
683 | | static const int kMuHasBlocked = 0x01; // already blocked (MUST == 1) |
684 | | static const int kMuIsCond = 0x02; // conditional waiter (CV or Condition) |
685 | | static const int kMuIsFer = 0x04; // wait morphing from a CondVar |
686 | | |
687 | | static_assert(PerThreadSynch::kAlignment > kMuLow, |
688 | | "PerThreadSynch::kAlignment must be greater than kMuLow"); |
689 | | |
690 | | // This struct contains various bitmasks to be used in |
691 | | // acquiring and releasing a mutex in a particular mode. |
692 | | struct MuHowS { |
693 | | // if all the bits in fast_need_zero are zero, the lock can be acquired by |
694 | | // adding fast_add and oring fast_or. The bit kMuDesig should be reset iff |
695 | | // this is the designated waker. |
696 | | intptr_t fast_need_zero; |
697 | | intptr_t fast_or; |
698 | | intptr_t fast_add; |
699 | | |
700 | | intptr_t slow_need_zero; // fast_need_zero with events (e.g. logging) |
701 | | |
702 | | intptr_t slow_inc_need_zero; // if all the bits in slow_inc_need_zero are |
703 | | // zero a reader can acquire a read share by |
704 | | // setting the reader bit and incrementing |
705 | | // the reader count (in last waiter since |
706 | | // we're now slow-path). kMuWrWait be may |
707 | | // be ignored if we already waited once. |
708 | | }; |
709 | | |
710 | | static const MuHowS kSharedS = { |
711 | | // shared or read lock |
712 | | kMuWriter | kMuWait | kMuEvent, // fast_need_zero |
713 | | kMuReader, // fast_or |
714 | | kMuOne, // fast_add |
715 | | kMuWriter | kMuWait, // slow_need_zero |
716 | | kMuSpin | kMuWriter | kMuWrWait, // slow_inc_need_zero |
717 | | }; |
718 | | static const MuHowS kExclusiveS = { |
719 | | // exclusive or write lock |
720 | | kMuWriter | kMuReader | kMuEvent, // fast_need_zero |
721 | | kMuWriter, // fast_or |
722 | | 0, // fast_add |
723 | | kMuWriter | kMuReader, // slow_need_zero |
724 | | ~static_cast<intptr_t>(0), // slow_inc_need_zero |
725 | | }; |
726 | | static const Mutex::MuHow kShared = &kSharedS; // shared lock |
727 | | static const Mutex::MuHow kExclusive = &kExclusiveS; // exclusive lock |
728 | | |
729 | | #ifdef NDEBUG |
730 | | static constexpr bool kDebugMode = false; |
731 | | #else |
732 | | static constexpr bool kDebugMode = true; |
733 | | #endif |
734 | | |
735 | | #ifdef ABSL_INTERNAL_HAVE_TSAN_INTERFACE |
736 | | static unsigned TsanFlags(Mutex::MuHow how) { |
737 | | return how == kShared ? __tsan_mutex_read_lock : 0; |
738 | | } |
739 | | #endif |
740 | | |
741 | | #if defined(__APPLE__) || defined(ABSL_BUILD_DLL) |
742 | | // When building a dll symbol export lists may reference the destructor |
743 | | // and want it to be an exported symbol rather than an inline function. |
744 | | // Some apple builds also do dynamic library build but don't say it explicitly. |
745 | | Mutex::~Mutex() { Dtor(); } |
746 | | #endif |
747 | | |
748 | | #if !defined(NDEBUG) || defined(ABSL_HAVE_THREAD_SANITIZER) |
749 | 0 | void Mutex::Dtor() { |
750 | 0 | if (kDebugMode) { |
751 | 0 | this->ForgetDeadlockInfo(); |
752 | 0 | } |
753 | 0 | ABSL_TSAN_MUTEX_DESTROY(this, __tsan_mutex_not_static); |
754 | 0 | } |
755 | | #endif |
756 | | |
757 | 0 | void Mutex::EnableDebugLog(const char* name) { |
758 | | // Need to disable writes here and in EnableInvariantDebugging to prevent |
759 | | // false race reports on SynchEvent objects. TSan ignores synchronization |
760 | | // on synch_event_mu in Lock/Unlock/etc methods due to mutex annotations, |
761 | | // but it sees few accesses to SynchEvent in EvalConditionAnnotated. |
762 | | // If we don't ignore accesses here, it can result in false races |
763 | | // between EvalConditionAnnotated and SynchEvent reuse in EnsureSynchEvent. |
764 | 0 | ABSL_ANNOTATE_IGNORE_WRITES_BEGIN(); |
765 | 0 | SynchEvent* e = EnsureSynchEvent(&this->mu_, name, kMuEvent, kMuSpin); |
766 | 0 | e->log = true; |
767 | 0 | UnrefSynchEvent(e); |
768 | | // This prevents "error: undefined symbol: absl::Mutex::~Mutex()" |
769 | | // in a release build (NDEBUG defined) when a test does "#undef NDEBUG" |
770 | | // to use assert macro. In such case, the test does not get the dtor |
771 | | // definition because it's supposed to be outline when NDEBUG is not defined, |
772 | | // and this source file does not define one either because NDEBUG is defined. |
773 | | // Since it's not possible to take address of a destructor, we move the |
774 | | // actual destructor code into the separate Dtor function and force the |
775 | | // compiler to emit this function even if it's inline by taking its address. |
776 | 0 | ABSL_ATTRIBUTE_UNUSED volatile auto dtor = &Mutex::Dtor; |
777 | 0 | ABSL_ANNOTATE_IGNORE_WRITES_END(); |
778 | 0 | } |
779 | | |
780 | 0 | void EnableMutexInvariantDebugging(bool enabled) { |
781 | 0 | synch_check_invariants.store(enabled, std::memory_order_release); |
782 | 0 | } |
783 | | |
784 | 0 | void Mutex::EnableInvariantDebugging(void (*invariant)(void*), void* arg) { |
785 | 0 | ABSL_ANNOTATE_IGNORE_WRITES_BEGIN(); |
786 | 0 | if (synch_check_invariants.load(std::memory_order_acquire) && |
787 | 0 | invariant != nullptr) { |
788 | 0 | SynchEvent* e = EnsureSynchEvent(&this->mu_, nullptr, kMuEvent, kMuSpin); |
789 | 0 | e->invariant = invariant; |
790 | 0 | e->arg = arg; |
791 | 0 | UnrefSynchEvent(e); |
792 | 0 | } |
793 | 0 | ABSL_ANNOTATE_IGNORE_WRITES_END(); |
794 | 0 | } |
795 | | |
796 | 0 | void SetMutexDeadlockDetectionMode(OnDeadlockCycle mode) { |
797 | 0 | synch_deadlock_detection.store(mode, std::memory_order_release); |
798 | 0 | } |
799 | | |
800 | | // Return true iff threads x and y are part of the same equivalence |
801 | | // class of waiters. An equivalence class is defined as the set of |
802 | | // waiters with the same condition, type of lock, and thread priority. |
803 | | // |
804 | | // Requires that x and y be waiting on the same Mutex queue. |
805 | 0 | static bool MuEquivalentWaiter(PerThreadSynch* x, PerThreadSynch* y) { |
806 | 0 | return x->waitp->how == y->waitp->how && x->priority == y->priority && |
807 | 0 | Condition::GuaranteedEqual(x->waitp->cond, y->waitp->cond); |
808 | 0 | } |
809 | | |
810 | | // Given the contents of a mutex word containing a PerThreadSynch pointer, |
811 | | // return the pointer. |
812 | 0 | static inline PerThreadSynch* GetPerThreadSynch(intptr_t v) { |
813 | 0 | return reinterpret_cast<PerThreadSynch*>(v & kMuHigh); |
814 | 0 | } |
815 | | |
816 | | // The next several routines maintain the per-thread next and skip fields |
817 | | // used in the Mutex waiter queue. |
818 | | // The queue is a circular singly-linked list, of which the "head" is the |
819 | | // last element, and head->next if the first element. |
820 | | // The skip field has the invariant: |
821 | | // For thread x, x->skip is one of: |
822 | | // - invalid (iff x is not in a Mutex wait queue), |
823 | | // - null, or |
824 | | // - a pointer to a distinct thread waiting later in the same Mutex queue |
825 | | // such that all threads in [x, x->skip] have the same condition, priority |
826 | | // and lock type (MuEquivalentWaiter() is true for all pairs in [x, |
827 | | // x->skip]). |
828 | | // In addition, if x->skip is valid, (x->may_skip || x->skip == null) |
829 | | // |
830 | | // By the spec of MuEquivalentWaiter(), it is not necessary when removing the |
831 | | // first runnable thread y from the front a Mutex queue to adjust the skip |
832 | | // field of another thread x because if x->skip==y, x->skip must (have) become |
833 | | // invalid before y is removed. The function TryRemove can remove a specified |
834 | | // thread from an arbitrary position in the queue whether runnable or not, so |
835 | | // it fixes up skip fields that would otherwise be left dangling. |
836 | | // The statement |
837 | | // if (x->may_skip && MuEquivalentWaiter(x, x->next)) { x->skip = x->next; } |
838 | | // maintains the invariant provided x is not the last waiter in a Mutex queue |
839 | | // The statement |
840 | | // if (x->skip != null) { x->skip = x->skip->skip; } |
841 | | // maintains the invariant. |
842 | | |
843 | | // Returns the last thread y in a mutex waiter queue such that all threads in |
844 | | // [x, y] inclusive share the same condition. Sets skip fields of some threads |
845 | | // in that range to optimize future evaluation of Skip() on x values in |
846 | | // the range. Requires thread x is in a mutex waiter queue. |
847 | | // The locking is unusual. Skip() is called under these conditions: |
848 | | // - spinlock is held in call from Enqueue(), with maybe_unlocking == false |
849 | | // - Mutex is held in call from UnlockSlow() by last unlocker, with |
850 | | // maybe_unlocking == true |
851 | | // - both Mutex and spinlock are held in call from DequeueAllWakeable() (from |
852 | | // UnlockSlow()) and TryRemove() |
853 | | // These cases are mutually exclusive, so Skip() never runs concurrently |
854 | | // with itself on the same Mutex. The skip chain is used in these other places |
855 | | // that cannot occur concurrently: |
856 | | // - FixSkip() (from TryRemove()) - spinlock and Mutex are held) |
857 | | // - Dequeue() (with spinlock and Mutex held) |
858 | | // - UnlockSlow() (with spinlock and Mutex held) |
859 | | // A more complex case is Enqueue() |
860 | | // - Enqueue() (with spinlock held and maybe_unlocking == false) |
861 | | // This is the first case in which Skip is called, above. |
862 | | // - Enqueue() (without spinlock held; but queue is empty and being freshly |
863 | | // formed) |
864 | | // - Enqueue() (with spinlock held and maybe_unlocking == true) |
865 | | // The first case has mutual exclusion, and the second isolation through |
866 | | // working on an otherwise unreachable data structure. |
867 | | // In the last case, Enqueue() is required to change no skip/next pointers |
868 | | // except those in the added node and the former "head" node. This implies |
869 | | // that the new node is added after head, and so must be the new head or the |
870 | | // new front of the queue. |
871 | 0 | static PerThreadSynch* Skip(PerThreadSynch* x) { |
872 | 0 | PerThreadSynch* x0 = nullptr; |
873 | 0 | PerThreadSynch* x1 = x; |
874 | 0 | PerThreadSynch* x2 = x->skip; |
875 | 0 | if (x2 != nullptr) { |
876 | | // Each iteration attempts to advance sequence (x0,x1,x2) to next sequence |
877 | | // such that x1 == x0->skip && x2 == x1->skip |
878 | 0 | while ((x0 = x1, x1 = x2, x2 = x2->skip) != nullptr) { |
879 | 0 | x0->skip = x2; // short-circuit skip from x0 to x2 |
880 | 0 | } |
881 | 0 | x->skip = x1; // short-circuit skip from x to result |
882 | 0 | } |
883 | 0 | return x1; |
884 | 0 | } |
885 | | |
886 | | // "ancestor" appears before "to_be_removed" in the same Mutex waiter queue. |
887 | | // The latter is going to be removed out of order, because of a timeout. |
888 | | // Check whether "ancestor" has a skip field pointing to "to_be_removed", |
889 | | // and fix it if it does. |
890 | 0 | static void FixSkip(PerThreadSynch* ancestor, PerThreadSynch* to_be_removed) { |
891 | 0 | if (ancestor->skip == to_be_removed) { // ancestor->skip left dangling |
892 | 0 | if (to_be_removed->skip != nullptr) { |
893 | 0 | ancestor->skip = to_be_removed->skip; // can skip past to_be_removed |
894 | 0 | } else if (ancestor->next != to_be_removed) { // they are not adjacent |
895 | 0 | ancestor->skip = ancestor->next; // can skip one past ancestor |
896 | 0 | } else { |
897 | 0 | ancestor->skip = nullptr; // can't skip at all |
898 | 0 | } |
899 | 0 | } |
900 | 0 | } |
901 | | |
902 | | static void CondVarEnqueue(SynchWaitParams* waitp); |
903 | | |
904 | | // Enqueue thread "waitp->thread" on a waiter queue. |
905 | | // Called with mutex spinlock held if head != nullptr |
906 | | // If head==nullptr and waitp->cv_word==nullptr, then Enqueue() is |
907 | | // idempotent; it alters no state associated with the existing (empty) |
908 | | // queue. |
909 | | // |
910 | | // If waitp->cv_word == nullptr, queue the thread at either the front or |
911 | | // the end (according to its priority) of the circular mutex waiter queue whose |
912 | | // head is "head", and return the new head. mu is the previous mutex state, |
913 | | // which contains the reader count (perhaps adjusted for the operation in |
914 | | // progress) if the list was empty and a read lock held, and the holder hint if |
915 | | // the list was empty and a write lock held. (flags & kMuIsCond) indicates |
916 | | // whether this thread was transferred from a CondVar or is waiting for a |
917 | | // non-trivial condition. In this case, Enqueue() never returns nullptr |
918 | | // |
919 | | // If waitp->cv_word != nullptr, CondVarEnqueue() is called, and "head" is |
920 | | // returned. This mechanism is used by CondVar to queue a thread on the |
921 | | // condition variable queue instead of the mutex queue in implementing Wait(). |
922 | | // In this case, Enqueue() can return nullptr (if head==nullptr). |
923 | | static PerThreadSynch* Enqueue(PerThreadSynch* head, SynchWaitParams* waitp, |
924 | 0 | intptr_t mu, int flags) { |
925 | | // If we have been given a cv_word, call CondVarEnqueue() and return |
926 | | // the previous head of the Mutex waiter queue. |
927 | 0 | if (waitp->cv_word != nullptr) { |
928 | 0 | CondVarEnqueue(waitp); |
929 | 0 | return head; |
930 | 0 | } |
931 | | |
932 | 0 | PerThreadSynch* s = waitp->thread; |
933 | 0 | ABSL_RAW_CHECK( |
934 | 0 | s->waitp == nullptr || // normal case |
935 | 0 | s->waitp == waitp || // Fer()---transfer from condition variable |
936 | 0 | s->suppress_fatal_errors, |
937 | 0 | "detected illegal recursion into Mutex code"); |
938 | 0 | s->waitp = waitp; |
939 | 0 | s->skip = nullptr; // maintain skip invariant (see above) |
940 | 0 | s->may_skip = true; // always true on entering queue |
941 | 0 | s->wake = false; // not being woken |
942 | 0 | s->cond_waiter = ((flags & kMuIsCond) != 0); |
943 | 0 | #ifdef ABSL_HAVE_PTHREAD_GETSCHEDPARAM |
944 | 0 | if ((flags & kMuIsFer) == 0) { |
945 | 0 | assert(s == Synch_GetPerThread()); |
946 | 0 | int64_t now_cycles = CycleClock::Now(); |
947 | 0 | if (s->next_priority_read_cycles < now_cycles) { |
948 | | // Every so often, update our idea of the thread's priority. |
949 | | // pthread_getschedparam() is 5% of the block/wakeup time; |
950 | | // CycleClock::Now() is 0.5%. |
951 | 0 | int policy; |
952 | 0 | struct sched_param param; |
953 | 0 | const int err = pthread_getschedparam(pthread_self(), &policy, ¶m); |
954 | 0 | if (err != 0) { |
955 | 0 | ABSL_RAW_LOG(ERROR, "pthread_getschedparam failed: %d", err); |
956 | 0 | } else { |
957 | 0 | s->priority = param.sched_priority; |
958 | 0 | s->next_priority_read_cycles = |
959 | 0 | now_cycles + static_cast<int64_t>(CycleClock::Frequency()); |
960 | 0 | } |
961 | 0 | } |
962 | 0 | } |
963 | 0 | #endif |
964 | 0 | if (head == nullptr) { // s is the only waiter |
965 | 0 | s->next = s; // it's the only entry in the cycle |
966 | 0 | s->readers = mu; // reader count is from mu word |
967 | 0 | s->maybe_unlocking = false; // no one is searching an empty list |
968 | 0 | head = s; // s is new head |
969 | 0 | } else { |
970 | 0 | PerThreadSynch* enqueue_after = nullptr; // we'll put s after this element |
971 | 0 | #ifdef ABSL_HAVE_PTHREAD_GETSCHEDPARAM |
972 | 0 | if (s->priority > head->priority) { // s's priority is above head's |
973 | | // try to put s in priority-fifo order, or failing that at the front. |
974 | 0 | if (!head->maybe_unlocking) { |
975 | | // No unlocker can be scanning the queue, so we can insert into the |
976 | | // middle of the queue. |
977 | | // |
978 | | // Within a skip chain, all waiters have the same priority, so we can |
979 | | // skip forward through the chains until we find one with a lower |
980 | | // priority than the waiter to be enqueued. |
981 | 0 | PerThreadSynch* advance_to = head; // next value of enqueue_after |
982 | 0 | do { |
983 | 0 | enqueue_after = advance_to; |
984 | | // (side-effect: optimizes skip chain) |
985 | 0 | advance_to = Skip(enqueue_after->next); |
986 | 0 | } while (s->priority <= advance_to->priority); |
987 | | // termination guaranteed because s->priority > head->priority |
988 | | // and head is the end of a skip chain |
989 | 0 | } else if (waitp->how == kExclusive && waitp->cond == nullptr) { |
990 | | // An unlocker could be scanning the queue, but we know it will recheck |
991 | | // the queue front for writers that have no condition, which is what s |
992 | | // is, so an insert at front is safe. |
993 | 0 | enqueue_after = head; // add after head, at front |
994 | 0 | } |
995 | 0 | } |
996 | 0 | #endif |
997 | 0 | if (enqueue_after != nullptr) { |
998 | 0 | s->next = enqueue_after->next; |
999 | 0 | enqueue_after->next = s; |
1000 | | |
1001 | | // enqueue_after can be: head, Skip(...), or cur. |
1002 | | // The first two imply enqueue_after->skip == nullptr, and |
1003 | | // the last is used only if MuEquivalentWaiter(s, cur). |
1004 | | // We require this because clearing enqueue_after->skip |
1005 | | // is impossible; enqueue_after's predecessors might also |
1006 | | // incorrectly skip over s if we were to allow other |
1007 | | // insertion points. |
1008 | 0 | ABSL_RAW_CHECK(enqueue_after->skip == nullptr || |
1009 | 0 | MuEquivalentWaiter(enqueue_after, s), |
1010 | 0 | "Mutex Enqueue failure"); |
1011 | | |
1012 | 0 | if (enqueue_after != head && enqueue_after->may_skip && |
1013 | 0 | MuEquivalentWaiter(enqueue_after, enqueue_after->next)) { |
1014 | | // enqueue_after can skip to its new successor, s |
1015 | 0 | enqueue_after->skip = enqueue_after->next; |
1016 | 0 | } |
1017 | 0 | if (MuEquivalentWaiter(s, s->next)) { // s->may_skip is known to be true |
1018 | 0 | s->skip = s->next; // s may skip to its successor |
1019 | 0 | } |
1020 | 0 | } else if ((flags & kMuHasBlocked) && |
1021 | 0 | (s->priority >= head->next->priority) && |
1022 | 0 | (!head->maybe_unlocking || |
1023 | 0 | (waitp->how == kExclusive && |
1024 | 0 | Condition::GuaranteedEqual(waitp->cond, nullptr)))) { |
1025 | | // This thread has already waited, then was woken, then failed to acquire |
1026 | | // the mutex and now tries to requeue. Try to requeue it at head, |
1027 | | // otherwise it can suffer bad latency (wait whole queue several times). |
1028 | | // However, we need to be conservative. First, we need to ensure that we |
1029 | | // respect priorities. Then, we need to be careful to not break wait |
1030 | | // queue invariants: we require either that unlocker is not scanning |
1031 | | // the queue or that the current thread is a writer with no condition |
1032 | | // (unlocker will recheck the queue for such waiters). |
1033 | 0 | s->next = head->next; |
1034 | 0 | head->next = s; |
1035 | 0 | if (MuEquivalentWaiter(s, s->next)) { // s->may_skip is known to be true |
1036 | 0 | s->skip = s->next; // s may skip to its successor |
1037 | 0 | } |
1038 | 0 | } else { // enqueue not done any other way, so |
1039 | | // we're inserting s at the back |
1040 | | // s will become new head; copy data from head into it |
1041 | 0 | s->next = head->next; // add s after head |
1042 | 0 | head->next = s; |
1043 | 0 | s->readers = head->readers; // reader count is from previous head |
1044 | 0 | s->maybe_unlocking = head->maybe_unlocking; // same for unlock hint |
1045 | 0 | if (head->may_skip && MuEquivalentWaiter(head, s)) { |
1046 | | // head now has successor; may skip |
1047 | 0 | head->skip = s; |
1048 | 0 | } |
1049 | 0 | head = s; // s is new head |
1050 | 0 | } |
1051 | 0 | } |
1052 | 0 | s->state.store(PerThreadSynch::kQueued, std::memory_order_relaxed); |
1053 | 0 | return head; |
1054 | 0 | } |
1055 | | |
1056 | | // Dequeue the successor pw->next of thread pw from the Mutex waiter queue |
1057 | | // whose last element is head. The new head element is returned, or null |
1058 | | // if the list is made empty. |
1059 | | // Dequeue is called with both spinlock and Mutex held. |
1060 | 0 | static PerThreadSynch* Dequeue(PerThreadSynch* head, PerThreadSynch* pw) { |
1061 | 0 | PerThreadSynch* w = pw->next; |
1062 | 0 | pw->next = w->next; // snip w out of list |
1063 | 0 | if (head == w) { // we removed the head |
1064 | 0 | head = (pw == w) ? nullptr : pw; // either emptied list, or pw is new head |
1065 | 0 | } else if (pw != head && MuEquivalentWaiter(pw, pw->next)) { |
1066 | | // pw can skip to its new successor |
1067 | 0 | if (pw->next->skip != |
1068 | 0 | nullptr) { // either skip to its successors skip target |
1069 | 0 | pw->skip = pw->next->skip; |
1070 | 0 | } else { // or to pw's successor |
1071 | 0 | pw->skip = pw->next; |
1072 | 0 | } |
1073 | 0 | } |
1074 | 0 | return head; |
1075 | 0 | } |
1076 | | |
1077 | | // Traverse the elements [ pw->next, h] of the circular list whose last element |
1078 | | // is head. |
1079 | | // Remove all elements with wake==true and place them in the |
1080 | | // singly-linked list wake_list in the order found. Assumes that |
1081 | | // there is only one such element if the element has how == kExclusive. |
1082 | | // Return the new head. |
1083 | | static PerThreadSynch* DequeueAllWakeable(PerThreadSynch* head, |
1084 | | PerThreadSynch* pw, |
1085 | 0 | PerThreadSynch** wake_tail) { |
1086 | 0 | PerThreadSynch* orig_h = head; |
1087 | 0 | PerThreadSynch* w = pw->next; |
1088 | 0 | bool skipped = false; |
1089 | 0 | do { |
1090 | 0 | if (w->wake) { // remove this element |
1091 | 0 | ABSL_RAW_CHECK(pw->skip == nullptr, "bad skip in DequeueAllWakeable"); |
1092 | | // we're removing pw's successor so either pw->skip is zero or we should |
1093 | | // already have removed pw since if pw->skip!=null, pw has the same |
1094 | | // condition as w. |
1095 | 0 | head = Dequeue(head, pw); |
1096 | 0 | w->next = *wake_tail; // keep list terminated |
1097 | 0 | *wake_tail = w; // add w to wake_list; |
1098 | 0 | wake_tail = &w->next; // next addition to end |
1099 | 0 | if (w->waitp->how == kExclusive) { // wake at most 1 writer |
1100 | 0 | break; |
1101 | 0 | } |
1102 | 0 | } else { // not waking this one; skip |
1103 | 0 | pw = Skip(w); // skip as much as possible |
1104 | 0 | skipped = true; |
1105 | 0 | } |
1106 | 0 | w = pw->next; |
1107 | | // We want to stop processing after we've considered the original head, |
1108 | | // orig_h. We can't test for w==orig_h in the loop because w may skip over |
1109 | | // it; we are guaranteed only that w's predecessor will not skip over |
1110 | | // orig_h. When we've considered orig_h, either we've processed it and |
1111 | | // removed it (so orig_h != head), or we considered it and skipped it (so |
1112 | | // skipped==true && pw == head because skipping from head always skips by |
1113 | | // just one, leaving pw pointing at head). So we want to |
1114 | | // continue the loop with the negation of that expression. |
1115 | 0 | } while (orig_h == head && (pw != head || !skipped)); |
1116 | 0 | return head; |
1117 | 0 | } |
1118 | | |
1119 | | // Try to remove thread s from the list of waiters on this mutex. |
1120 | | // Does nothing if s is not on the waiter list. |
1121 | 0 | void Mutex::TryRemove(PerThreadSynch* s) { |
1122 | 0 | SchedulingGuard::ScopedDisable disable_rescheduling; |
1123 | 0 | intptr_t v = mu_.load(std::memory_order_relaxed); |
1124 | | // acquire spinlock & lock |
1125 | 0 | if ((v & (kMuWait | kMuSpin | kMuWriter | kMuReader)) == kMuWait && |
1126 | 0 | mu_.compare_exchange_strong(v, v | kMuSpin | kMuWriter, |
1127 | 0 | std::memory_order_acquire, |
1128 | 0 | std::memory_order_relaxed)) { |
1129 | 0 | PerThreadSynch* h = GetPerThreadSynch(v); |
1130 | 0 | if (h != nullptr) { |
1131 | 0 | PerThreadSynch* pw = h; // pw is w's predecessor |
1132 | 0 | PerThreadSynch* w; |
1133 | 0 | if ((w = pw->next) != s) { // search for thread, |
1134 | 0 | do { // processing at least one element |
1135 | | // If the current element isn't equivalent to the waiter to be |
1136 | | // removed, we can skip the entire chain. |
1137 | 0 | if (!MuEquivalentWaiter(s, w)) { |
1138 | 0 | pw = Skip(w); // so skip all that won't match |
1139 | | // we don't have to worry about dangling skip fields |
1140 | | // in the threads we skipped; none can point to s |
1141 | | // because they are in a different equivalence class. |
1142 | 0 | } else { // seeking same condition |
1143 | 0 | FixSkip(w, s); // fix up any skip pointer from w to s |
1144 | 0 | pw = w; |
1145 | 0 | } |
1146 | | // don't search further if we found the thread, or we're about to |
1147 | | // process the first thread again. |
1148 | 0 | } while ((w = pw->next) != s && pw != h); |
1149 | 0 | } |
1150 | 0 | if (w == s) { // found thread; remove it |
1151 | | // pw->skip may be non-zero here; the loop above ensured that |
1152 | | // no ancestor of s can skip to s, so removal is safe anyway. |
1153 | 0 | h = Dequeue(h, pw); |
1154 | 0 | s->next = nullptr; |
1155 | 0 | s->state.store(PerThreadSynch::kAvailable, std::memory_order_release); |
1156 | 0 | } |
1157 | 0 | } |
1158 | 0 | intptr_t nv; |
1159 | 0 | do { // release spinlock and lock |
1160 | 0 | v = mu_.load(std::memory_order_relaxed); |
1161 | 0 | nv = v & (kMuDesig | kMuEvent); |
1162 | 0 | if (h != nullptr) { |
1163 | 0 | nv |= kMuWait | reinterpret_cast<intptr_t>(h); |
1164 | 0 | h->readers = 0; // we hold writer lock |
1165 | 0 | h->maybe_unlocking = false; // finished unlocking |
1166 | 0 | } |
1167 | 0 | } while (!mu_.compare_exchange_weak(v, nv, std::memory_order_release, |
1168 | 0 | std::memory_order_relaxed)); |
1169 | 0 | } |
1170 | 0 | } |
1171 | | |
1172 | | // Wait until thread "s", which must be the current thread, is removed from the |
1173 | | // this mutex's waiter queue. If "s->waitp->timeout" has a timeout, wake up |
1174 | | // if the wait extends past the absolute time specified, even if "s" is still |
1175 | | // on the mutex queue. In this case, remove "s" from the queue and return |
1176 | | // true, otherwise return false. |
1177 | 0 | void Mutex::Block(PerThreadSynch* s) { |
1178 | 0 | while (s->state.load(std::memory_order_acquire) == PerThreadSynch::kQueued) { |
1179 | 0 | if (!DecrementSynchSem(this, s, s->waitp->timeout)) { |
1180 | | // After a timeout, we go into a spin loop until we remove ourselves |
1181 | | // from the queue, or someone else removes us. We can't be sure to be |
1182 | | // able to remove ourselves in a single lock acquisition because this |
1183 | | // mutex may be held, and the holder has the right to read the centre |
1184 | | // of the waiter queue without holding the spinlock. |
1185 | 0 | this->TryRemove(s); |
1186 | 0 | int c = 0; |
1187 | 0 | while (s->next != nullptr) { |
1188 | 0 | c = synchronization_internal::MutexDelay(c, GENTLE); |
1189 | 0 | this->TryRemove(s); |
1190 | 0 | } |
1191 | 0 | if (kDebugMode) { |
1192 | | // This ensures that we test the case that TryRemove() is called when s |
1193 | | // is not on the queue. |
1194 | 0 | this->TryRemove(s); |
1195 | 0 | } |
1196 | 0 | s->waitp->timeout = KernelTimeout::Never(); // timeout is satisfied |
1197 | 0 | s->waitp->cond = nullptr; // condition no longer relevant for wakeups |
1198 | 0 | } |
1199 | 0 | } |
1200 | 0 | ABSL_RAW_CHECK(s->waitp != nullptr || s->suppress_fatal_errors, |
1201 | 0 | "detected illegal recursion in Mutex code"); |
1202 | 0 | s->waitp = nullptr; |
1203 | 0 | } |
1204 | | |
1205 | | // Wake thread w, and return the next thread in the list. |
1206 | 0 | PerThreadSynch* Mutex::Wakeup(PerThreadSynch* w) { |
1207 | 0 | PerThreadSynch* next = w->next; |
1208 | 0 | w->next = nullptr; |
1209 | 0 | w->state.store(PerThreadSynch::kAvailable, std::memory_order_release); |
1210 | 0 | IncrementSynchSem(this, w); |
1211 | |
|
1212 | 0 | return next; |
1213 | 0 | } |
1214 | | |
1215 | | static GraphId GetGraphIdLocked(Mutex* mu) |
1216 | 737k | ABSL_EXCLUSIVE_LOCKS_REQUIRED(deadlock_graph_mu) { |
1217 | 737k | if (!deadlock_graph) { // (re)create the deadlock graph. |
1218 | 1 | deadlock_graph = |
1219 | 1 | new (base_internal::LowLevelAlloc::Alloc(sizeof(*deadlock_graph))) |
1220 | 1 | GraphCycles; |
1221 | 1 | } |
1222 | 737k | return deadlock_graph->GetId(mu); |
1223 | 737k | } |
1224 | | |
1225 | 368k | static GraphId GetGraphId(Mutex* mu) ABSL_LOCKS_EXCLUDED(deadlock_graph_mu) { |
1226 | 368k | deadlock_graph_mu.Lock(); |
1227 | 368k | GraphId id = GetGraphIdLocked(mu); |
1228 | 368k | deadlock_graph_mu.Unlock(); |
1229 | 368k | return id; |
1230 | 368k | } |
1231 | | |
1232 | | // Record a lock acquisition. This is used in debug mode for deadlock |
1233 | | // detection. The held_locks pointer points to the relevant data |
1234 | | // structure for each case. |
1235 | 368k | static void LockEnter(Mutex* mu, GraphId id, SynchLocksHeld* held_locks) { |
1236 | 368k | int n = held_locks->n; |
1237 | 368k | int i = 0; |
1238 | 646k | while (i != n && held_locks->locks[i].id != id) { |
1239 | 277k | i++; |
1240 | 277k | } |
1241 | 368k | if (i == n) { |
1242 | 368k | if (n == ABSL_ARRAYSIZE(held_locks->locks)) { |
1243 | 0 | held_locks->overflow = true; // lost some data |
1244 | 368k | } else { // we have room for lock |
1245 | 368k | held_locks->locks[i].mu = mu; |
1246 | 368k | held_locks->locks[i].count = 1; |
1247 | 368k | held_locks->locks[i].id = id; |
1248 | 368k | held_locks->n = n + 1; |
1249 | 368k | } |
1250 | 368k | } else { |
1251 | 0 | held_locks->locks[i].count++; |
1252 | 0 | } |
1253 | 368k | } |
1254 | | |
1255 | | // Record a lock release. Each call to LockEnter(mu, id, x) should be |
1256 | | // eventually followed by a call to LockLeave(mu, id, x) by the same thread. |
1257 | | // It does not process the event if is not needed when deadlock detection is |
1258 | | // disabled. |
1259 | 368k | static void LockLeave(Mutex* mu, GraphId id, SynchLocksHeld* held_locks) { |
1260 | 368k | int n = held_locks->n; |
1261 | 368k | int i = 0; |
1262 | 646k | while (i != n && held_locks->locks[i].id != id) { |
1263 | 277k | i++; |
1264 | 277k | } |
1265 | 368k | if (i == n) { |
1266 | 0 | if (!held_locks->overflow) { |
1267 | | // The deadlock id may have been reassigned after ForgetDeadlockInfo, |
1268 | | // but in that case mu should still be present. |
1269 | 0 | i = 0; |
1270 | 0 | while (i != n && held_locks->locks[i].mu != mu) { |
1271 | 0 | i++; |
1272 | 0 | } |
1273 | 0 | if (i == n) { // mu missing means releasing unheld lock |
1274 | 0 | SynchEvent* mu_events = GetSynchEvent(mu); |
1275 | 0 | ABSL_RAW_LOG(FATAL, |
1276 | 0 | "thread releasing lock it does not hold: %p %s; " |
1277 | 0 | , |
1278 | 0 | static_cast<void*>(mu), |
1279 | 0 | mu_events == nullptr ? "" : mu_events->name); |
1280 | 0 | } |
1281 | 0 | } |
1282 | 368k | } else if (held_locks->locks[i].count == 1) { |
1283 | 368k | held_locks->n = n - 1; |
1284 | 368k | held_locks->locks[i] = held_locks->locks[n - 1]; |
1285 | 368k | held_locks->locks[n - 1].id = InvalidGraphId(); |
1286 | 368k | held_locks->locks[n - 1].mu = |
1287 | 368k | nullptr; // clear mu to please the leak detector. |
1288 | 368k | } else { |
1289 | 0 | assert(held_locks->locks[i].count > 0); |
1290 | 0 | held_locks->locks[i].count--; |
1291 | 0 | } |
1292 | 368k | } |
1293 | | |
1294 | | // Call LockEnter() if in debug mode and deadlock detection is enabled. |
1295 | 0 | static inline void DebugOnlyLockEnter(Mutex* mu) { |
1296 | 0 | if (kDebugMode) { |
1297 | 0 | if (synch_deadlock_detection.load(std::memory_order_acquire) != |
1298 | 0 | OnDeadlockCycle::kIgnore) { |
1299 | 0 | LockEnter(mu, GetGraphId(mu), Synch_GetAllLocks()); |
1300 | 0 | } |
1301 | 0 | } |
1302 | 0 | } |
1303 | | |
1304 | | // Call LockEnter() if in debug mode and deadlock detection is enabled. |
1305 | 368k | static inline void DebugOnlyLockEnter(Mutex* mu, GraphId id) { |
1306 | 368k | if (kDebugMode) { |
1307 | 368k | if (synch_deadlock_detection.load(std::memory_order_acquire) != |
1308 | 368k | OnDeadlockCycle::kIgnore) { |
1309 | 368k | LockEnter(mu, id, Synch_GetAllLocks()); |
1310 | 368k | } |
1311 | 368k | } |
1312 | 368k | } |
1313 | | |
1314 | | // Call LockLeave() if in debug mode and deadlock detection is enabled. |
1315 | 368k | static inline void DebugOnlyLockLeave(Mutex* mu) { |
1316 | 368k | if (kDebugMode) { |
1317 | 368k | if (synch_deadlock_detection.load(std::memory_order_acquire) != |
1318 | 368k | OnDeadlockCycle::kIgnore) { |
1319 | 368k | LockLeave(mu, GetGraphId(mu), Synch_GetAllLocks()); |
1320 | 368k | } |
1321 | 368k | } |
1322 | 368k | } |
1323 | | |
1324 | | static char* StackString(void** pcs, int n, char* buf, int maxlen, |
1325 | 0 | bool symbolize) { |
1326 | 0 | static constexpr int kSymLen = 200; |
1327 | 0 | char sym[kSymLen]; |
1328 | 0 | int len = 0; |
1329 | 0 | for (int i = 0; i != n; i++) { |
1330 | 0 | if (len >= maxlen) |
1331 | 0 | return buf; |
1332 | 0 | size_t count = static_cast<size_t>(maxlen - len); |
1333 | 0 | if (symbolize) { |
1334 | 0 | if (!absl::Symbolize(pcs[i], sym, kSymLen)) { |
1335 | 0 | sym[0] = '\0'; |
1336 | 0 | } |
1337 | 0 | snprintf(buf + len, count, "%s\t@ %p %s\n", (i == 0 ? "\n" : ""), pcs[i], |
1338 | 0 | sym); |
1339 | 0 | } else { |
1340 | 0 | snprintf(buf + len, count, " %p", pcs[i]); |
1341 | 0 | } |
1342 | 0 | len += static_cast<int>(strlen(&buf[len])); |
1343 | 0 | } |
1344 | 0 | return buf; |
1345 | 0 | } |
1346 | | |
1347 | 0 | static char* CurrentStackString(char* buf, int maxlen, bool symbolize) { |
1348 | 0 | void* pcs[40]; |
1349 | 0 | return StackString(pcs, absl::GetStackTrace(pcs, ABSL_ARRAYSIZE(pcs), 2), buf, |
1350 | 0 | maxlen, symbolize); |
1351 | 0 | } |
1352 | | |
1353 | | namespace { |
1354 | | enum { |
1355 | | kMaxDeadlockPathLen = 10 |
1356 | | }; // maximum length of a deadlock cycle; |
1357 | | // a path this long would be remarkable |
1358 | | // Buffers required to report a deadlock. |
1359 | | // We do not allocate them on stack to avoid large stack frame. |
1360 | | struct DeadlockReportBuffers { |
1361 | | char buf[6100]; |
1362 | | GraphId path[kMaxDeadlockPathLen]; |
1363 | | }; |
1364 | | |
1365 | | struct ScopedDeadlockReportBuffers { |
1366 | 0 | ScopedDeadlockReportBuffers() { |
1367 | 0 | b = reinterpret_cast<DeadlockReportBuffers*>( |
1368 | 0 | base_internal::LowLevelAlloc::Alloc(sizeof(*b))); |
1369 | 0 | } |
1370 | 0 | ~ScopedDeadlockReportBuffers() { base_internal::LowLevelAlloc::Free(b); } |
1371 | | DeadlockReportBuffers* b; |
1372 | | }; |
1373 | | |
1374 | | // Helper to pass to GraphCycles::UpdateStackTrace. |
1375 | 1.14k | int GetStack(void** stack, int max_depth) { |
1376 | 1.14k | return absl::GetStackTrace(stack, max_depth, 3); |
1377 | 1.14k | } |
1378 | | } // anonymous namespace |
1379 | | |
1380 | | // Called in debug mode when a thread is about to acquire a lock in a way that |
1381 | | // may block. |
1382 | 368k | static GraphId DeadlockCheck(Mutex* mu) { |
1383 | 368k | if (synch_deadlock_detection.load(std::memory_order_acquire) == |
1384 | 368k | OnDeadlockCycle::kIgnore) { |
1385 | 0 | return InvalidGraphId(); |
1386 | 0 | } |
1387 | | |
1388 | 368k | SynchLocksHeld* all_locks = Synch_GetAllLocks(); |
1389 | | |
1390 | 368k | absl::base_internal::SpinLockHolder lock(&deadlock_graph_mu); |
1391 | 368k | const GraphId mu_id = GetGraphIdLocked(mu); |
1392 | | |
1393 | 368k | if (all_locks->n == 0) { |
1394 | | // There are no other locks held. Return now so that we don't need to |
1395 | | // call GetSynchEvent(). This way we do not record the stack trace |
1396 | | // for this Mutex. It's ok, since if this Mutex is involved in a deadlock, |
1397 | | // it can't always be the first lock acquired by a thread. |
1398 | 91.3k | return mu_id; |
1399 | 91.3k | } |
1400 | | |
1401 | | // We prefer to keep stack traces that show a thread holding and acquiring |
1402 | | // as many locks as possible. This increases the chances that a given edge |
1403 | | // in the acquires-before graph will be represented in the stack traces |
1404 | | // recorded for the locks. |
1405 | 277k | deadlock_graph->UpdateStackTrace(mu_id, all_locks->n + 1, GetStack); |
1406 | | |
1407 | | // For each other mutex already held by this thread: |
1408 | 554k | for (int i = 0; i != all_locks->n; i++) { |
1409 | 277k | const GraphId other_node_id = all_locks->locks[i].id; |
1410 | 277k | const Mutex* other = |
1411 | 277k | static_cast<const Mutex*>(deadlock_graph->Ptr(other_node_id)); |
1412 | 277k | if (other == nullptr) { |
1413 | | // Ignore stale lock |
1414 | 0 | continue; |
1415 | 0 | } |
1416 | | |
1417 | | // Add the acquired-before edge to the graph. |
1418 | 277k | if (!deadlock_graph->InsertEdge(other_node_id, mu_id)) { |
1419 | 0 | ScopedDeadlockReportBuffers scoped_buffers; |
1420 | 0 | DeadlockReportBuffers* b = scoped_buffers.b; |
1421 | 0 | static int number_of_reported_deadlocks = 0; |
1422 | 0 | number_of_reported_deadlocks++; |
1423 | | // Symbolize only 2 first deadlock report to avoid huge slowdowns. |
1424 | 0 | bool symbolize = number_of_reported_deadlocks <= 2; |
1425 | 0 | ABSL_RAW_LOG(ERROR, "Potential Mutex deadlock: %s", |
1426 | 0 | CurrentStackString(b->buf, sizeof (b->buf), symbolize)); |
1427 | 0 | size_t len = 0; |
1428 | 0 | for (int j = 0; j != all_locks->n; j++) { |
1429 | 0 | void* pr = deadlock_graph->Ptr(all_locks->locks[j].id); |
1430 | 0 | if (pr != nullptr) { |
1431 | 0 | snprintf(b->buf + len, sizeof(b->buf) - len, " %p", pr); |
1432 | 0 | len += strlen(&b->buf[len]); |
1433 | 0 | } |
1434 | 0 | } |
1435 | 0 | ABSL_RAW_LOG(ERROR, |
1436 | 0 | "Acquiring absl::Mutex %p while holding %s; a cycle in the " |
1437 | 0 | "historical lock ordering graph has been observed", |
1438 | 0 | static_cast<void*>(mu), b->buf); |
1439 | 0 | ABSL_RAW_LOG(ERROR, "Cycle: "); |
1440 | 0 | int path_len = deadlock_graph->FindPath(mu_id, other_node_id, |
1441 | 0 | ABSL_ARRAYSIZE(b->path), b->path); |
1442 | 0 | for (int j = 0; j != path_len && j != ABSL_ARRAYSIZE(b->path); j++) { |
1443 | 0 | GraphId id = b->path[j]; |
1444 | 0 | Mutex* path_mu = static_cast<Mutex*>(deadlock_graph->Ptr(id)); |
1445 | 0 | if (path_mu == nullptr) continue; |
1446 | 0 | void** stack; |
1447 | 0 | int depth = deadlock_graph->GetStackTrace(id, &stack); |
1448 | 0 | snprintf(b->buf, sizeof(b->buf), |
1449 | 0 | "mutex@%p stack: ", static_cast<void*>(path_mu)); |
1450 | 0 | StackString(stack, depth, b->buf + strlen(b->buf), |
1451 | 0 | static_cast<int>(sizeof(b->buf) - strlen(b->buf)), |
1452 | 0 | symbolize); |
1453 | 0 | ABSL_RAW_LOG(ERROR, "%s", b->buf); |
1454 | 0 | } |
1455 | 0 | if (path_len > static_cast<int>(ABSL_ARRAYSIZE(b->path))) { |
1456 | 0 | ABSL_RAW_LOG(ERROR, "(long cycle; list truncated)"); |
1457 | 0 | } |
1458 | 0 | if (synch_deadlock_detection.load(std::memory_order_acquire) == |
1459 | 0 | OnDeadlockCycle::kAbort) { |
1460 | 0 | deadlock_graph_mu.Unlock(); // avoid deadlock in fatal sighandler |
1461 | 0 | ABSL_RAW_LOG(FATAL, "dying due to potential deadlock"); |
1462 | 0 | return mu_id; |
1463 | 0 | } |
1464 | 0 | break; // report at most one potential deadlock per acquisition |
1465 | 0 | } |
1466 | 277k | } |
1467 | | |
1468 | 277k | return mu_id; |
1469 | 277k | } |
1470 | | |
1471 | | // Invoke DeadlockCheck() iff we're in debug mode and |
1472 | | // deadlock checking has been enabled. |
1473 | 368k | static inline GraphId DebugOnlyDeadlockCheck(Mutex* mu) { |
1474 | 368k | if (kDebugMode && synch_deadlock_detection.load(std::memory_order_acquire) != |
1475 | 368k | OnDeadlockCycle::kIgnore) { |
1476 | 368k | return DeadlockCheck(mu); |
1477 | 368k | } else { |
1478 | 0 | return InvalidGraphId(); |
1479 | 0 | } |
1480 | 368k | } |
1481 | | |
1482 | 0 | void Mutex::ForgetDeadlockInfo() { |
1483 | 0 | if (kDebugMode && synch_deadlock_detection.load(std::memory_order_acquire) != |
1484 | 0 | OnDeadlockCycle::kIgnore) { |
1485 | 0 | deadlock_graph_mu.Lock(); |
1486 | 0 | if (deadlock_graph != nullptr) { |
1487 | 0 | deadlock_graph->RemoveNode(this); |
1488 | 0 | } |
1489 | 0 | deadlock_graph_mu.Unlock(); |
1490 | 0 | } |
1491 | 0 | } |
1492 | | |
1493 | 0 | void Mutex::AssertNotHeld() const { |
1494 | | // We have the data to allow this check only if in debug mode and deadlock |
1495 | | // detection is enabled. |
1496 | 0 | if (kDebugMode && |
1497 | 0 | (mu_.load(std::memory_order_relaxed) & (kMuWriter | kMuReader)) != 0 && |
1498 | 0 | synch_deadlock_detection.load(std::memory_order_acquire) != |
1499 | 0 | OnDeadlockCycle::kIgnore) { |
1500 | 0 | GraphId id = GetGraphId(const_cast<Mutex*>(this)); |
1501 | 0 | SynchLocksHeld* locks = Synch_GetAllLocks(); |
1502 | 0 | for (int i = 0; i != locks->n; i++) { |
1503 | 0 | if (locks->locks[i].id == id) { |
1504 | 0 | SynchEvent* mu_events = GetSynchEvent(this); |
1505 | 0 | ABSL_RAW_LOG(FATAL, "thread should not hold mutex %p %s", |
1506 | 0 | static_cast<const void*>(this), |
1507 | 0 | (mu_events == nullptr ? "" : mu_events->name)); |
1508 | 0 | } |
1509 | 0 | } |
1510 | 0 | } |
1511 | 0 | } |
1512 | | |
1513 | | // Attempt to acquire *mu, and return whether successful. The implementation |
1514 | | // may spin for a short while if the lock cannot be acquired immediately. |
1515 | 0 | static bool TryAcquireWithSpinning(std::atomic<intptr_t>* mu) { |
1516 | 0 | int c = globals.spinloop_iterations.load(std::memory_order_relaxed); |
1517 | 0 | do { // do/while somewhat faster on AMD |
1518 | 0 | intptr_t v = mu->load(std::memory_order_relaxed); |
1519 | 0 | if ((v & (kMuReader | kMuEvent)) != 0) { |
1520 | 0 | return false; // a reader or tracing -> give up |
1521 | 0 | } else if (((v & kMuWriter) == 0) && // no holder -> try to acquire |
1522 | 0 | mu->compare_exchange_strong(v, kMuWriter | v, |
1523 | 0 | std::memory_order_acquire, |
1524 | 0 | std::memory_order_relaxed)) { |
1525 | 0 | return true; |
1526 | 0 | } |
1527 | 0 | } while (--c > 0); |
1528 | 0 | return false; |
1529 | 0 | } |
1530 | | |
1531 | 277k | void Mutex::Lock() { |
1532 | 277k | ABSL_TSAN_MUTEX_PRE_LOCK(this, 0); |
1533 | 277k | GraphId id = DebugOnlyDeadlockCheck(this); |
1534 | 277k | intptr_t v = mu_.load(std::memory_order_relaxed); |
1535 | | // try fast acquire, then spin loop |
1536 | 277k | if (ABSL_PREDICT_FALSE((v & (kMuWriter | kMuReader | kMuEvent)) != 0) || |
1537 | 277k | ABSL_PREDICT_FALSE(!mu_.compare_exchange_strong( |
1538 | 277k | v, kMuWriter | v, std::memory_order_acquire, |
1539 | 277k | std::memory_order_relaxed))) { |
1540 | | // try spin acquire, then slow loop |
1541 | 0 | if (ABSL_PREDICT_FALSE(!TryAcquireWithSpinning(&this->mu_))) { |
1542 | 0 | this->LockSlow(kExclusive, nullptr, 0); |
1543 | 0 | } |
1544 | 0 | } |
1545 | 277k | DebugOnlyLockEnter(this, id); |
1546 | 277k | ABSL_TSAN_MUTEX_POST_LOCK(this, 0, 0); |
1547 | 277k | } |
1548 | | |
1549 | 91.3k | void Mutex::ReaderLock() { |
1550 | 91.3k | ABSL_TSAN_MUTEX_PRE_LOCK(this, __tsan_mutex_read_lock); |
1551 | 91.3k | GraphId id = DebugOnlyDeadlockCheck(this); |
1552 | 91.3k | intptr_t v = mu_.load(std::memory_order_relaxed); |
1553 | 91.3k | for (;;) { |
1554 | | // If there are non-readers holding the lock, use the slow loop. |
1555 | 91.3k | if (ABSL_PREDICT_FALSE(v & (kMuWriter | kMuWait | kMuEvent)) != 0) { |
1556 | 0 | this->LockSlow(kShared, nullptr, 0); |
1557 | 0 | break; |
1558 | 0 | } |
1559 | | // We can avoid the loop and only use the CAS when the lock is free or |
1560 | | // only held by readers. |
1561 | 91.3k | if (ABSL_PREDICT_TRUE(mu_.compare_exchange_weak( |
1562 | 91.3k | v, (kMuReader | v) + kMuOne, std::memory_order_acquire, |
1563 | 91.3k | std::memory_order_relaxed))) { |
1564 | 91.3k | break; |
1565 | 91.3k | } |
1566 | 91.3k | } |
1567 | 91.3k | DebugOnlyLockEnter(this, id); |
1568 | 91.3k | ABSL_TSAN_MUTEX_POST_LOCK(this, __tsan_mutex_read_lock, 0); |
1569 | 91.3k | } |
1570 | | |
1571 | | bool Mutex::LockWhenCommon(const Condition& cond, |
1572 | | synchronization_internal::KernelTimeout t, |
1573 | 0 | bool write) { |
1574 | 0 | MuHow how = write ? kExclusive : kShared; |
1575 | 0 | ABSL_TSAN_MUTEX_PRE_LOCK(this, TsanFlags(how)); |
1576 | 0 | GraphId id = DebugOnlyDeadlockCheck(this); |
1577 | 0 | bool res = LockSlowWithDeadline(how, &cond, t, 0); |
1578 | 0 | DebugOnlyLockEnter(this, id); |
1579 | 0 | ABSL_TSAN_MUTEX_POST_LOCK(this, TsanFlags(how), 0); |
1580 | 0 | return res; |
1581 | 0 | } |
1582 | | |
1583 | 0 | bool Mutex::AwaitCommon(const Condition& cond, KernelTimeout t) { |
1584 | 0 | if (kDebugMode) { |
1585 | 0 | this->AssertReaderHeld(); |
1586 | 0 | } |
1587 | 0 | if (cond.Eval()) { // condition already true; nothing to do |
1588 | 0 | return true; |
1589 | 0 | } |
1590 | 0 | MuHow how = |
1591 | 0 | (mu_.load(std::memory_order_relaxed) & kMuWriter) ? kExclusive : kShared; |
1592 | 0 | ABSL_TSAN_MUTEX_PRE_UNLOCK(this, TsanFlags(how)); |
1593 | 0 | SynchWaitParams waitp(how, &cond, t, nullptr /*no cvmu*/, |
1594 | 0 | Synch_GetPerThreadAnnotated(this), |
1595 | 0 | nullptr /*no cv_word*/); |
1596 | 0 | this->UnlockSlow(&waitp); |
1597 | 0 | this->Block(waitp.thread); |
1598 | 0 | ABSL_TSAN_MUTEX_POST_UNLOCK(this, TsanFlags(how)); |
1599 | 0 | ABSL_TSAN_MUTEX_PRE_LOCK(this, TsanFlags(how)); |
1600 | 0 | this->LockSlowLoop(&waitp, kMuHasBlocked | kMuIsCond); |
1601 | 0 | bool res = waitp.cond != nullptr || // => cond known true from LockSlowLoop |
1602 | 0 | EvalConditionAnnotated(&cond, this, true, false, how == kShared); |
1603 | 0 | ABSL_TSAN_MUTEX_POST_LOCK(this, TsanFlags(how), 0); |
1604 | 0 | ABSL_RAW_CHECK(res || t.has_timeout(), |
1605 | 0 | "condition untrue on return from Await"); |
1606 | 0 | return res; |
1607 | 0 | } |
1608 | | |
1609 | 0 | bool Mutex::TryLock() { |
1610 | 0 | ABSL_TSAN_MUTEX_PRE_LOCK(this, __tsan_mutex_try_lock); |
1611 | 0 | intptr_t v = mu_.load(std::memory_order_relaxed); |
1612 | | // Try fast acquire. |
1613 | 0 | if (ABSL_PREDICT_TRUE((v & (kMuWriter | kMuReader | kMuEvent)) == 0)) { |
1614 | 0 | if (ABSL_PREDICT_TRUE(mu_.compare_exchange_strong( |
1615 | 0 | v, kMuWriter | v, std::memory_order_acquire, |
1616 | 0 | std::memory_order_relaxed))) { |
1617 | 0 | DebugOnlyLockEnter(this); |
1618 | 0 | ABSL_TSAN_MUTEX_POST_LOCK(this, __tsan_mutex_try_lock, 0); |
1619 | 0 | return true; |
1620 | 0 | } |
1621 | 0 | } else if (ABSL_PREDICT_FALSE((v & kMuEvent) != 0)) { |
1622 | | // We're recording events. |
1623 | 0 | return TryLockSlow(); |
1624 | 0 | } |
1625 | 0 | ABSL_TSAN_MUTEX_POST_LOCK( |
1626 | 0 | this, __tsan_mutex_try_lock | __tsan_mutex_try_lock_failed, 0); |
1627 | 0 | return false; |
1628 | 0 | } |
1629 | | |
1630 | 0 | ABSL_ATTRIBUTE_NOINLINE bool Mutex::TryLockSlow() { |
1631 | 0 | intptr_t v = mu_.load(std::memory_order_relaxed); |
1632 | 0 | if ((v & kExclusive->slow_need_zero) == 0 && // try fast acquire |
1633 | 0 | mu_.compare_exchange_strong( |
1634 | 0 | v, (kExclusive->fast_or | v) + kExclusive->fast_add, |
1635 | 0 | std::memory_order_acquire, std::memory_order_relaxed)) { |
1636 | 0 | DebugOnlyLockEnter(this); |
1637 | 0 | PostSynchEvent(this, SYNCH_EV_TRYLOCK_SUCCESS); |
1638 | 0 | ABSL_TSAN_MUTEX_POST_LOCK(this, __tsan_mutex_try_lock, 0); |
1639 | 0 | return true; |
1640 | 0 | } |
1641 | 0 | PostSynchEvent(this, SYNCH_EV_TRYLOCK_FAILED); |
1642 | 0 | ABSL_TSAN_MUTEX_POST_LOCK( |
1643 | 0 | this, __tsan_mutex_try_lock | __tsan_mutex_try_lock_failed, 0); |
1644 | 0 | return false; |
1645 | 0 | } |
1646 | | |
1647 | 0 | bool Mutex::ReaderTryLock() { |
1648 | 0 | ABSL_TSAN_MUTEX_PRE_LOCK(this, |
1649 | 0 | __tsan_mutex_read_lock | __tsan_mutex_try_lock); |
1650 | 0 | intptr_t v = mu_.load(std::memory_order_relaxed); |
1651 | | // Clang tends to unroll the loop when compiling with optimization. |
1652 | | // But in this case it just unnecessary increases code size. |
1653 | | // If CAS is failing due to contention, the jump cost is negligible. |
1654 | 0 | #if defined(__clang__) |
1655 | 0 | #pragma nounroll |
1656 | 0 | #endif |
1657 | | // The while-loops (here and below) iterate only if the mutex word keeps |
1658 | | // changing (typically because the reader count changes) under the CAS. |
1659 | | // We limit the number of attempts to avoid having to think about livelock. |
1660 | 0 | for (int loop_limit = 5; loop_limit != 0; loop_limit--) { |
1661 | 0 | if (ABSL_PREDICT_FALSE((v & (kMuWriter | kMuWait | kMuEvent)) != 0)) { |
1662 | 0 | break; |
1663 | 0 | } |
1664 | 0 | if (ABSL_PREDICT_TRUE(mu_.compare_exchange_strong( |
1665 | 0 | v, (kMuReader | v) + kMuOne, std::memory_order_acquire, |
1666 | 0 | std::memory_order_relaxed))) { |
1667 | 0 | DebugOnlyLockEnter(this); |
1668 | 0 | ABSL_TSAN_MUTEX_POST_LOCK( |
1669 | 0 | this, __tsan_mutex_read_lock | __tsan_mutex_try_lock, 0); |
1670 | 0 | return true; |
1671 | 0 | } |
1672 | 0 | } |
1673 | 0 | if (ABSL_PREDICT_TRUE((v & kMuEvent) == 0)) { |
1674 | 0 | ABSL_TSAN_MUTEX_POST_LOCK(this, |
1675 | 0 | __tsan_mutex_read_lock | __tsan_mutex_try_lock | |
1676 | 0 | __tsan_mutex_try_lock_failed, |
1677 | 0 | 0); |
1678 | 0 | return false; |
1679 | 0 | } |
1680 | | // we're recording events |
1681 | 0 | return ReaderTryLockSlow(); |
1682 | 0 | } |
1683 | | |
1684 | 0 | ABSL_ATTRIBUTE_NOINLINE bool Mutex::ReaderTryLockSlow() { |
1685 | 0 | intptr_t v = mu_.load(std::memory_order_relaxed); |
1686 | 0 | #if defined(__clang__) |
1687 | 0 | #pragma nounroll |
1688 | 0 | #endif |
1689 | 0 | for (int loop_limit = 5; loop_limit != 0; loop_limit--) { |
1690 | 0 | if ((v & kShared->slow_need_zero) == 0 && |
1691 | 0 | mu_.compare_exchange_strong(v, (kMuReader | v) + kMuOne, |
1692 | 0 | std::memory_order_acquire, |
1693 | 0 | std::memory_order_relaxed)) { |
1694 | 0 | DebugOnlyLockEnter(this); |
1695 | 0 | PostSynchEvent(this, SYNCH_EV_READERTRYLOCK_SUCCESS); |
1696 | 0 | ABSL_TSAN_MUTEX_POST_LOCK( |
1697 | 0 | this, __tsan_mutex_read_lock | __tsan_mutex_try_lock, 0); |
1698 | 0 | return true; |
1699 | 0 | } |
1700 | 0 | } |
1701 | 0 | PostSynchEvent(this, SYNCH_EV_READERTRYLOCK_FAILED); |
1702 | 0 | ABSL_TSAN_MUTEX_POST_LOCK(this, |
1703 | 0 | __tsan_mutex_read_lock | __tsan_mutex_try_lock | |
1704 | 0 | __tsan_mutex_try_lock_failed, |
1705 | 0 | 0); |
1706 | 0 | return false; |
1707 | 0 | } |
1708 | | |
1709 | 277k | void Mutex::Unlock() { |
1710 | 277k | ABSL_TSAN_MUTEX_PRE_UNLOCK(this, 0); |
1711 | 277k | DebugOnlyLockLeave(this); |
1712 | 277k | intptr_t v = mu_.load(std::memory_order_relaxed); |
1713 | | |
1714 | 277k | if (kDebugMode && ((v & (kMuWriter | kMuReader)) != kMuWriter)) { |
1715 | 0 | ABSL_RAW_LOG(FATAL, "Mutex unlocked when destroyed or not locked: v=0x%x", |
1716 | 0 | static_cast<unsigned>(v)); |
1717 | 0 | } |
1718 | | |
1719 | | // should_try_cas is whether we'll try a compare-and-swap immediately. |
1720 | | // NOTE: optimized out when kDebugMode is false. |
1721 | 277k | bool should_try_cas = ((v & (kMuEvent | kMuWriter)) == kMuWriter && |
1722 | 277k | (v & (kMuWait | kMuDesig)) != kMuWait); |
1723 | | |
1724 | | // But, we can use an alternate computation of it, that compilers |
1725 | | // currently don't find on their own. When that changes, this function |
1726 | | // can be simplified. |
1727 | | // |
1728 | | // should_try_cas is true iff the bits satisfy the following conditions: |
1729 | | // |
1730 | | // Ev Wr Wa De |
1731 | | // equal to 0 1 |
1732 | | // and not equal to 1 0 |
1733 | | // |
1734 | | // after xoring by 0 1 0 1, this is equivalent to: |
1735 | | // |
1736 | | // equal to 0 0 |
1737 | | // and not equal to 1 1, which is the same as: |
1738 | | // |
1739 | | // smaller than 0 0 1 1 |
1740 | 277k | static_assert(kMuEvent > kMuWait, "Needed for should_try_cas_fast"); |
1741 | 277k | static_assert(kMuEvent > kMuDesig, "Needed for should_try_cas_fast"); |
1742 | 277k | static_assert(kMuWriter > kMuWait, "Needed for should_try_cas_fast"); |
1743 | 277k | static_assert(kMuWriter > kMuDesig, "Needed for should_try_cas_fast"); |
1744 | | |
1745 | 277k | bool should_try_cas_fast = |
1746 | 277k | ((v ^ (kMuWriter | kMuDesig)) & |
1747 | 277k | (kMuEvent | kMuWriter | kMuWait | kMuDesig)) < (kMuWait | kMuDesig); |
1748 | | |
1749 | 277k | if (kDebugMode && should_try_cas != should_try_cas_fast) { |
1750 | | // We would usually use PRIdPTR here, but is not correctly implemented |
1751 | | // within the android toolchain. |
1752 | 0 | ABSL_RAW_LOG(FATAL, "internal logic error %llx %llx %llx\n", |
1753 | 0 | static_cast<long long>(v), |
1754 | 0 | static_cast<long long>(should_try_cas), |
1755 | 0 | static_cast<long long>(should_try_cas_fast)); |
1756 | 0 | } |
1757 | 277k | if (should_try_cas_fast && |
1758 | 277k | mu_.compare_exchange_strong(v, v & ~(kMuWrWait | kMuWriter), |
1759 | 277k | std::memory_order_release, |
1760 | 277k | std::memory_order_relaxed)) { |
1761 | | // fast writer release (writer with no waiters or with designated waker) |
1762 | 277k | } else { |
1763 | 0 | this->UnlockSlow(nullptr /*no waitp*/); // take slow path |
1764 | 0 | } |
1765 | 277k | ABSL_TSAN_MUTEX_POST_UNLOCK(this, 0); |
1766 | 277k | } |
1767 | | |
1768 | | // Requires v to represent a reader-locked state. |
1769 | 91.3k | static bool ExactlyOneReader(intptr_t v) { |
1770 | 91.3k | assert((v & (kMuWriter | kMuReader)) == kMuReader); |
1771 | 91.3k | assert((v & kMuHigh) != 0); |
1772 | | // The more straightforward "(v & kMuHigh) == kMuOne" also works, but |
1773 | | // on some architectures the following generates slightly smaller code. |
1774 | | // It may be faster too. |
1775 | 91.3k | constexpr intptr_t kMuMultipleWaitersMask = kMuHigh ^ kMuOne; |
1776 | 91.3k | return (v & kMuMultipleWaitersMask) == 0; |
1777 | 91.3k | } |
1778 | | |
1779 | 91.3k | void Mutex::ReaderUnlock() { |
1780 | 91.3k | ABSL_TSAN_MUTEX_PRE_UNLOCK(this, __tsan_mutex_read_lock); |
1781 | 91.3k | DebugOnlyLockLeave(this); |
1782 | 91.3k | intptr_t v = mu_.load(std::memory_order_relaxed); |
1783 | 91.3k | assert((v & (kMuWriter | kMuReader)) == kMuReader); |
1784 | 91.3k | for (;;) { |
1785 | 91.3k | if (ABSL_PREDICT_FALSE((v & (kMuReader | kMuWait | kMuEvent)) != |
1786 | 91.3k | kMuReader)) { |
1787 | 0 | this->UnlockSlow(nullptr /*no waitp*/); // take slow path |
1788 | 0 | break; |
1789 | 0 | } |
1790 | | // fast reader release (reader with no waiters) |
1791 | 91.3k | intptr_t clear = ExactlyOneReader(v) ? kMuReader | kMuOne : kMuOne; |
1792 | 91.3k | if (ABSL_PREDICT_TRUE( |
1793 | 91.3k | mu_.compare_exchange_strong(v, v - clear, std::memory_order_release, |
1794 | 91.3k | std::memory_order_relaxed))) { |
1795 | 91.3k | break; |
1796 | 91.3k | } |
1797 | 91.3k | } |
1798 | 91.3k | ABSL_TSAN_MUTEX_POST_UNLOCK(this, __tsan_mutex_read_lock); |
1799 | 91.3k | } |
1800 | | |
1801 | | // Clears the designated waker flag in the mutex if this thread has blocked, and |
1802 | | // therefore may be the designated waker. |
1803 | 0 | static intptr_t ClearDesignatedWakerMask(int flag) { |
1804 | 0 | assert(flag >= 0); |
1805 | 0 | assert(flag <= 1); |
1806 | 0 | switch (flag) { |
1807 | 0 | case 0: // not blocked |
1808 | 0 | return ~static_cast<intptr_t>(0); |
1809 | 0 | case 1: // blocked; turn off the designated waker bit |
1810 | 0 | return ~static_cast<intptr_t>(kMuDesig); |
1811 | 0 | } |
1812 | 0 | ABSL_UNREACHABLE(); |
1813 | 0 | } |
1814 | | |
1815 | | // Conditionally ignores the existence of waiting writers if a reader that has |
1816 | | // already blocked once wakes up. |
1817 | 0 | static intptr_t IgnoreWaitingWritersMask(int flag) { |
1818 | 0 | assert(flag >= 0); |
1819 | 0 | assert(flag <= 1); |
1820 | 0 | switch (flag) { |
1821 | 0 | case 0: // not blocked |
1822 | 0 | return ~static_cast<intptr_t>(0); |
1823 | 0 | case 1: // blocked; pretend there are no waiting writers |
1824 | 0 | return ~static_cast<intptr_t>(kMuWrWait); |
1825 | 0 | } |
1826 | 0 | ABSL_UNREACHABLE(); |
1827 | 0 | } |
1828 | | |
1829 | | // Internal version of LockWhen(). See LockSlowWithDeadline() |
1830 | | ABSL_ATTRIBUTE_NOINLINE void Mutex::LockSlow(MuHow how, const Condition* cond, |
1831 | 0 | int flags) { |
1832 | | // Note: we specifically initialize spinloop_iterations after the first use |
1833 | | // in TryAcquireWithSpinning so that Lock function does not have any non-tail |
1834 | | // calls and consequently a stack frame. It's fine to have spinloop_iterations |
1835 | | // uninitialized (meaning no spinning) in all initial uncontended Lock calls |
1836 | | // and in the first contended call. After that we will have |
1837 | | // spinloop_iterations properly initialized. |
1838 | 0 | if (ABSL_PREDICT_FALSE( |
1839 | 0 | globals.spinloop_iterations.load(std::memory_order_relaxed) == 0)) { |
1840 | 0 | if (absl::base_internal::NumCPUs() > 1) { |
1841 | | // If this is multiprocessor, allow spinning. |
1842 | 0 | globals.spinloop_iterations.store(1500, std::memory_order_relaxed); |
1843 | 0 | } else { |
1844 | | // If this a uniprocessor, only yield/sleep. |
1845 | 0 | globals.spinloop_iterations.store(-1, std::memory_order_relaxed); |
1846 | 0 | } |
1847 | 0 | } |
1848 | 0 | ABSL_RAW_CHECK( |
1849 | 0 | this->LockSlowWithDeadline(how, cond, KernelTimeout::Never(), flags), |
1850 | 0 | "condition untrue on return from LockSlow"); |
1851 | 0 | } |
1852 | | |
1853 | | // Compute cond->Eval() and tell race detectors that we do it under mutex mu. |
1854 | | static inline bool EvalConditionAnnotated(const Condition* cond, Mutex* mu, |
1855 | | bool locking, bool trylock, |
1856 | 0 | bool read_lock) { |
1857 | | // Delicate annotation dance. |
1858 | | // We are currently inside of read/write lock/unlock operation. |
1859 | | // All memory accesses are ignored inside of mutex operations + for unlock |
1860 | | // operation tsan considers that we've already released the mutex. |
1861 | 0 | bool res = false; |
1862 | | #ifdef ABSL_INTERNAL_HAVE_TSAN_INTERFACE |
1863 | | const uint32_t flags = read_lock ? __tsan_mutex_read_lock : 0; |
1864 | | const uint32_t tryflags = flags | (trylock ? __tsan_mutex_try_lock : 0); |
1865 | | #endif |
1866 | 0 | if (locking) { |
1867 | | // For lock we pretend that we have finished the operation, |
1868 | | // evaluate the predicate, then unlock the mutex and start locking it again |
1869 | | // to match the annotation at the end of outer lock operation. |
1870 | | // Note: we can't simply do POST_LOCK, Eval, PRE_LOCK, because then tsan |
1871 | | // will think the lock acquisition is recursive which will trigger |
1872 | | // deadlock detector. |
1873 | 0 | ABSL_TSAN_MUTEX_POST_LOCK(mu, tryflags, 0); |
1874 | 0 | res = cond->Eval(); |
1875 | | // There is no "try" version of Unlock, so use flags instead of tryflags. |
1876 | 0 | ABSL_TSAN_MUTEX_PRE_UNLOCK(mu, flags); |
1877 | 0 | ABSL_TSAN_MUTEX_POST_UNLOCK(mu, flags); |
1878 | 0 | ABSL_TSAN_MUTEX_PRE_LOCK(mu, tryflags); |
1879 | 0 | } else { |
1880 | | // Similarly, for unlock we pretend that we have unlocked the mutex, |
1881 | | // lock the mutex, evaluate the predicate, and start unlocking it again |
1882 | | // to match the annotation at the end of outer unlock operation. |
1883 | 0 | ABSL_TSAN_MUTEX_POST_UNLOCK(mu, flags); |
1884 | 0 | ABSL_TSAN_MUTEX_PRE_LOCK(mu, flags); |
1885 | 0 | ABSL_TSAN_MUTEX_POST_LOCK(mu, flags, 0); |
1886 | 0 | res = cond->Eval(); |
1887 | 0 | ABSL_TSAN_MUTEX_PRE_UNLOCK(mu, flags); |
1888 | 0 | } |
1889 | | // Prevent unused param warnings in non-TSAN builds. |
1890 | 0 | static_cast<void>(mu); |
1891 | 0 | static_cast<void>(trylock); |
1892 | 0 | static_cast<void>(read_lock); |
1893 | 0 | return res; |
1894 | 0 | } |
1895 | | |
1896 | | // Compute cond->Eval() hiding it from race detectors. |
1897 | | // We are hiding it because inside of UnlockSlow we can evaluate a predicate |
1898 | | // that was just added by a concurrent Lock operation; Lock adds the predicate |
1899 | | // to the internal Mutex list without actually acquiring the Mutex |
1900 | | // (it only acquires the internal spinlock, which is rightfully invisible for |
1901 | | // tsan). As the result there is no tsan-visible synchronization between the |
1902 | | // addition and this thread. So if we would enable race detection here, |
1903 | | // it would race with the predicate initialization. |
1904 | 0 | static inline bool EvalConditionIgnored(Mutex* mu, const Condition* cond) { |
1905 | | // Memory accesses are already ignored inside of lock/unlock operations, |
1906 | | // but synchronization operations are also ignored. When we evaluate the |
1907 | | // predicate we must ignore only memory accesses but not synchronization, |
1908 | | // because missed synchronization can lead to false reports later. |
1909 | | // So we "divert" (which un-ignores both memory accesses and synchronization) |
1910 | | // and then separately turn on ignores of memory accesses. |
1911 | 0 | ABSL_TSAN_MUTEX_PRE_DIVERT(mu, 0); |
1912 | 0 | ABSL_ANNOTATE_IGNORE_READS_AND_WRITES_BEGIN(); |
1913 | 0 | bool res = cond->Eval(); |
1914 | 0 | ABSL_ANNOTATE_IGNORE_READS_AND_WRITES_END(); |
1915 | 0 | ABSL_TSAN_MUTEX_POST_DIVERT(mu, 0); |
1916 | 0 | static_cast<void>(mu); // Prevent unused param warning in non-TSAN builds. |
1917 | 0 | return res; |
1918 | 0 | } |
1919 | | |
1920 | | // Internal equivalent of *LockWhenWithDeadline(), where |
1921 | | // "t" represents the absolute timeout; !t.has_timeout() means "forever". |
1922 | | // "how" is "kShared" (for ReaderLockWhen) or "kExclusive" (for LockWhen) |
1923 | | // In flags, bits are ored together: |
1924 | | // - kMuHasBlocked indicates that the client has already blocked on the call so |
1925 | | // the designated waker bit must be cleared and waiting writers should not |
1926 | | // obstruct this call |
1927 | | // - kMuIsCond indicates that this is a conditional acquire (condition variable, |
1928 | | // Await, LockWhen) so contention profiling should be suppressed. |
1929 | | bool Mutex::LockSlowWithDeadline(MuHow how, const Condition* cond, |
1930 | 0 | KernelTimeout t, int flags) { |
1931 | 0 | intptr_t v = mu_.load(std::memory_order_relaxed); |
1932 | 0 | bool unlock = false; |
1933 | 0 | if ((v & how->fast_need_zero) == 0 && // try fast acquire |
1934 | 0 | mu_.compare_exchange_strong( |
1935 | 0 | v, |
1936 | 0 | (how->fast_or | |
1937 | 0 | (v & ClearDesignatedWakerMask(flags & kMuHasBlocked))) + |
1938 | 0 | how->fast_add, |
1939 | 0 | std::memory_order_acquire, std::memory_order_relaxed)) { |
1940 | 0 | if (cond == nullptr || |
1941 | 0 | EvalConditionAnnotated(cond, this, true, false, how == kShared)) { |
1942 | 0 | return true; |
1943 | 0 | } |
1944 | 0 | unlock = true; |
1945 | 0 | } |
1946 | 0 | SynchWaitParams waitp(how, cond, t, nullptr /*no cvmu*/, |
1947 | 0 | Synch_GetPerThreadAnnotated(this), |
1948 | 0 | nullptr /*no cv_word*/); |
1949 | 0 | if (cond != nullptr) { |
1950 | 0 | flags |= kMuIsCond; |
1951 | 0 | } |
1952 | 0 | if (unlock) { |
1953 | 0 | this->UnlockSlow(&waitp); |
1954 | 0 | this->Block(waitp.thread); |
1955 | 0 | flags |= kMuHasBlocked; |
1956 | 0 | } |
1957 | 0 | this->LockSlowLoop(&waitp, flags); |
1958 | 0 | return waitp.cond != nullptr || // => cond known true from LockSlowLoop |
1959 | 0 | cond == nullptr || |
1960 | 0 | EvalConditionAnnotated(cond, this, true, false, how == kShared); |
1961 | 0 | } |
1962 | | |
1963 | | // RAW_CHECK_FMT() takes a condition, a printf-style format string, and |
1964 | | // the printf-style argument list. The format string must be a literal. |
1965 | | // Arguments after the first are not evaluated unless the condition is true. |
1966 | | #define RAW_CHECK_FMT(cond, ...) \ |
1967 | 0 | do { \ |
1968 | 0 | if (ABSL_PREDICT_FALSE(!(cond))) { \ |
1969 | 0 | ABSL_RAW_LOG(FATAL, "Check " #cond " failed: " __VA_ARGS__); \ |
1970 | 0 | } \ |
1971 | 0 | } while (0) |
1972 | | |
1973 | 0 | static void CheckForMutexCorruption(intptr_t v, const char* label) { |
1974 | | // Test for either of two situations that should not occur in v: |
1975 | | // kMuWriter and kMuReader |
1976 | | // kMuWrWait and !kMuWait |
1977 | 0 | const uintptr_t w = static_cast<uintptr_t>(v ^ kMuWait); |
1978 | | // By flipping that bit, we can now test for: |
1979 | | // kMuWriter and kMuReader in w |
1980 | | // kMuWrWait and kMuWait in w |
1981 | | // We've chosen these two pairs of values to be so that they will overlap, |
1982 | | // respectively, when the word is left shifted by three. This allows us to |
1983 | | // save a branch in the common (correct) case of them not being coincident. |
1984 | 0 | static_assert(kMuReader << 3 == kMuWriter, "must match"); |
1985 | 0 | static_assert(kMuWait << 3 == kMuWrWait, "must match"); |
1986 | 0 | if (ABSL_PREDICT_TRUE((w & (w << 3) & (kMuWriter | kMuWrWait)) == 0)) return; |
1987 | 0 | RAW_CHECK_FMT((v & (kMuWriter | kMuReader)) != (kMuWriter | kMuReader), |
1988 | 0 | "%s: Mutex corrupt: both reader and writer lock held: %p", |
1989 | 0 | label, reinterpret_cast<void*>(v)); |
1990 | 0 | RAW_CHECK_FMT((v & (kMuWait | kMuWrWait)) != kMuWrWait, |
1991 | 0 | "%s: Mutex corrupt: waiting writer with no waiters: %p", label, |
1992 | 0 | reinterpret_cast<void*>(v)); |
1993 | 0 | assert(false); |
1994 | 0 | } |
1995 | | |
1996 | 0 | void Mutex::LockSlowLoop(SynchWaitParams* waitp, int flags) { |
1997 | 0 | SchedulingGuard::ScopedDisable disable_rescheduling; |
1998 | 0 | int c = 0; |
1999 | 0 | intptr_t v = mu_.load(std::memory_order_relaxed); |
2000 | 0 | if ((v & kMuEvent) != 0) { |
2001 | 0 | PostSynchEvent( |
2002 | 0 | this, waitp->how == kExclusive ? SYNCH_EV_LOCK : SYNCH_EV_READERLOCK); |
2003 | 0 | } |
2004 | 0 | ABSL_RAW_CHECK( |
2005 | 0 | waitp->thread->waitp == nullptr || waitp->thread->suppress_fatal_errors, |
2006 | 0 | "detected illegal recursion into Mutex code"); |
2007 | 0 | for (;;) { |
2008 | 0 | v = mu_.load(std::memory_order_relaxed); |
2009 | 0 | CheckForMutexCorruption(v, "Lock"); |
2010 | 0 | if ((v & waitp->how->slow_need_zero) == 0) { |
2011 | 0 | if (mu_.compare_exchange_strong( |
2012 | 0 | v, |
2013 | 0 | (waitp->how->fast_or | |
2014 | 0 | (v & ClearDesignatedWakerMask(flags & kMuHasBlocked))) + |
2015 | 0 | waitp->how->fast_add, |
2016 | 0 | std::memory_order_acquire, std::memory_order_relaxed)) { |
2017 | 0 | if (waitp->cond == nullptr || |
2018 | 0 | EvalConditionAnnotated(waitp->cond, this, true, false, |
2019 | 0 | waitp->how == kShared)) { |
2020 | 0 | break; // we timed out, or condition true, so return |
2021 | 0 | } |
2022 | 0 | this->UnlockSlow(waitp); // got lock but condition false |
2023 | 0 | this->Block(waitp->thread); |
2024 | 0 | flags |= kMuHasBlocked; |
2025 | 0 | c = 0; |
2026 | 0 | } |
2027 | 0 | } else { // need to access waiter list |
2028 | 0 | bool dowait = false; |
2029 | 0 | if ((v & (kMuSpin | kMuWait)) == 0) { // no waiters |
2030 | | // This thread tries to become the one and only waiter. |
2031 | 0 | PerThreadSynch* new_h = Enqueue(nullptr, waitp, v, flags); |
2032 | 0 | intptr_t nv = |
2033 | 0 | (v & ClearDesignatedWakerMask(flags & kMuHasBlocked) & kMuLow) | |
2034 | 0 | kMuWait; |
2035 | 0 | ABSL_RAW_CHECK(new_h != nullptr, "Enqueue to empty list failed"); |
2036 | 0 | if (waitp->how == kExclusive && (v & kMuReader) != 0) { |
2037 | 0 | nv |= kMuWrWait; |
2038 | 0 | } |
2039 | 0 | if (mu_.compare_exchange_strong( |
2040 | 0 | v, reinterpret_cast<intptr_t>(new_h) | nv, |
2041 | 0 | std::memory_order_release, std::memory_order_relaxed)) { |
2042 | 0 | dowait = true; |
2043 | 0 | } else { // attempted Enqueue() failed |
2044 | | // zero out the waitp field set by Enqueue() |
2045 | 0 | waitp->thread->waitp = nullptr; |
2046 | 0 | } |
2047 | 0 | } else if ((v & waitp->how->slow_inc_need_zero & |
2048 | 0 | IgnoreWaitingWritersMask(flags & kMuHasBlocked)) == 0) { |
2049 | | // This is a reader that needs to increment the reader count, |
2050 | | // but the count is currently held in the last waiter. |
2051 | 0 | if (mu_.compare_exchange_strong( |
2052 | 0 | v, |
2053 | 0 | (v & ClearDesignatedWakerMask(flags & kMuHasBlocked)) | |
2054 | 0 | kMuSpin | kMuReader, |
2055 | 0 | std::memory_order_acquire, std::memory_order_relaxed)) { |
2056 | 0 | PerThreadSynch* h = GetPerThreadSynch(v); |
2057 | 0 | h->readers += kMuOne; // inc reader count in waiter |
2058 | 0 | do { // release spinlock |
2059 | 0 | v = mu_.load(std::memory_order_relaxed); |
2060 | 0 | } while (!mu_.compare_exchange_weak(v, (v & ~kMuSpin) | kMuReader, |
2061 | 0 | std::memory_order_release, |
2062 | 0 | std::memory_order_relaxed)); |
2063 | 0 | if (waitp->cond == nullptr || |
2064 | 0 | EvalConditionAnnotated(waitp->cond, this, true, false, |
2065 | 0 | waitp->how == kShared)) { |
2066 | 0 | break; // we timed out, or condition true, so return |
2067 | 0 | } |
2068 | 0 | this->UnlockSlow(waitp); // got lock but condition false |
2069 | 0 | this->Block(waitp->thread); |
2070 | 0 | flags |= kMuHasBlocked; |
2071 | 0 | c = 0; |
2072 | 0 | } |
2073 | 0 | } else if ((v & kMuSpin) == 0 && // attempt to queue ourselves |
2074 | 0 | mu_.compare_exchange_strong( |
2075 | 0 | v, |
2076 | 0 | (v & ClearDesignatedWakerMask(flags & kMuHasBlocked)) | |
2077 | 0 | kMuSpin | kMuWait, |
2078 | 0 | std::memory_order_acquire, std::memory_order_relaxed)) { |
2079 | 0 | PerThreadSynch* h = GetPerThreadSynch(v); |
2080 | 0 | PerThreadSynch* new_h = Enqueue(h, waitp, v, flags); |
2081 | 0 | intptr_t wr_wait = 0; |
2082 | 0 | ABSL_RAW_CHECK(new_h != nullptr, "Enqueue to list failed"); |
2083 | 0 | if (waitp->how == kExclusive && (v & kMuReader) != 0) { |
2084 | 0 | wr_wait = kMuWrWait; // give priority to a waiting writer |
2085 | 0 | } |
2086 | 0 | do { // release spinlock |
2087 | 0 | v = mu_.load(std::memory_order_relaxed); |
2088 | 0 | } while (!mu_.compare_exchange_weak( |
2089 | 0 | v, |
2090 | 0 | (v & (kMuLow & ~kMuSpin)) | kMuWait | wr_wait | |
2091 | 0 | reinterpret_cast<intptr_t>(new_h), |
2092 | 0 | std::memory_order_release, std::memory_order_relaxed)); |
2093 | 0 | dowait = true; |
2094 | 0 | } |
2095 | 0 | if (dowait) { |
2096 | 0 | this->Block(waitp->thread); // wait until removed from list or timeout |
2097 | 0 | flags |= kMuHasBlocked; |
2098 | 0 | c = 0; |
2099 | 0 | } |
2100 | 0 | } |
2101 | 0 | ABSL_RAW_CHECK( |
2102 | 0 | waitp->thread->waitp == nullptr || waitp->thread->suppress_fatal_errors, |
2103 | 0 | "detected illegal recursion into Mutex code"); |
2104 | | // delay, then try again |
2105 | 0 | c = synchronization_internal::MutexDelay(c, GENTLE); |
2106 | 0 | } |
2107 | 0 | ABSL_RAW_CHECK( |
2108 | 0 | waitp->thread->waitp == nullptr || waitp->thread->suppress_fatal_errors, |
2109 | 0 | "detected illegal recursion into Mutex code"); |
2110 | 0 | if ((v & kMuEvent) != 0) { |
2111 | 0 | PostSynchEvent(this, waitp->how == kExclusive |
2112 | 0 | ? SYNCH_EV_LOCK_RETURNING |
2113 | 0 | : SYNCH_EV_READERLOCK_RETURNING); |
2114 | 0 | } |
2115 | 0 | } |
2116 | | |
2117 | | // Unlock this mutex, which is held by the current thread. |
2118 | | // If waitp is non-zero, it must be the wait parameters for the current thread |
2119 | | // which holds the lock but is not runnable because its condition is false |
2120 | | // or it is in the process of blocking on a condition variable; it must requeue |
2121 | | // itself on the mutex/condvar to wait for its condition to become true. |
2122 | 0 | ABSL_ATTRIBUTE_NOINLINE void Mutex::UnlockSlow(SynchWaitParams* waitp) { |
2123 | 0 | SchedulingGuard::ScopedDisable disable_rescheduling; |
2124 | 0 | intptr_t v = mu_.load(std::memory_order_relaxed); |
2125 | 0 | this->AssertReaderHeld(); |
2126 | 0 | CheckForMutexCorruption(v, "Unlock"); |
2127 | 0 | if ((v & kMuEvent) != 0) { |
2128 | 0 | PostSynchEvent( |
2129 | 0 | this, (v & kMuWriter) != 0 ? SYNCH_EV_UNLOCK : SYNCH_EV_READERUNLOCK); |
2130 | 0 | } |
2131 | 0 | int c = 0; |
2132 | | // the waiter under consideration to wake, or zero |
2133 | 0 | PerThreadSynch* w = nullptr; |
2134 | | // the predecessor to w or zero |
2135 | 0 | PerThreadSynch* pw = nullptr; |
2136 | | // head of the list searched previously, or zero |
2137 | 0 | PerThreadSynch* old_h = nullptr; |
2138 | | // a condition that's known to be false. |
2139 | 0 | PerThreadSynch* wake_list = kPerThreadSynchNull; // list of threads to wake |
2140 | 0 | intptr_t wr_wait = 0; // set to kMuWrWait if we wake a reader and a |
2141 | | // later writer could have acquired the lock |
2142 | | // (starvation avoidance) |
2143 | 0 | ABSL_RAW_CHECK(waitp == nullptr || waitp->thread->waitp == nullptr || |
2144 | 0 | waitp->thread->suppress_fatal_errors, |
2145 | 0 | "detected illegal recursion into Mutex code"); |
2146 | | // This loop finds threads wake_list to wakeup if any, and removes them from |
2147 | | // the list of waiters. In addition, it places waitp.thread on the queue of |
2148 | | // waiters if waitp is non-zero. |
2149 | 0 | for (;;) { |
2150 | 0 | v = mu_.load(std::memory_order_relaxed); |
2151 | 0 | if ((v & kMuWriter) != 0 && (v & (kMuWait | kMuDesig)) != kMuWait && |
2152 | 0 | waitp == nullptr) { |
2153 | | // fast writer release (writer with no waiters or with designated waker) |
2154 | 0 | if (mu_.compare_exchange_strong(v, v & ~(kMuWrWait | kMuWriter), |
2155 | 0 | std::memory_order_release, |
2156 | 0 | std::memory_order_relaxed)) { |
2157 | 0 | return; |
2158 | 0 | } |
2159 | 0 | } else if ((v & (kMuReader | kMuWait)) == kMuReader && waitp == nullptr) { |
2160 | | // fast reader release (reader with no waiters) |
2161 | 0 | intptr_t clear = ExactlyOneReader(v) ? kMuReader | kMuOne : kMuOne; |
2162 | 0 | if (mu_.compare_exchange_strong(v, v - clear, std::memory_order_release, |
2163 | 0 | std::memory_order_relaxed)) { |
2164 | 0 | return; |
2165 | 0 | } |
2166 | 0 | } else if ((v & kMuSpin) == 0 && // attempt to get spinlock |
2167 | 0 | mu_.compare_exchange_strong(v, v | kMuSpin, |
2168 | 0 | std::memory_order_acquire, |
2169 | 0 | std::memory_order_relaxed)) { |
2170 | 0 | if ((v & kMuWait) == 0) { // no one to wake |
2171 | 0 | intptr_t nv; |
2172 | 0 | bool do_enqueue = true; // always Enqueue() the first time |
2173 | 0 | ABSL_RAW_CHECK(waitp != nullptr, |
2174 | 0 | "UnlockSlow is confused"); // about to sleep |
2175 | 0 | do { // must loop to release spinlock as reader count may change |
2176 | 0 | v = mu_.load(std::memory_order_relaxed); |
2177 | | // decrement reader count if there are readers |
2178 | 0 | intptr_t new_readers = (v >= kMuOne) ? v - kMuOne : v; |
2179 | 0 | PerThreadSynch* new_h = nullptr; |
2180 | 0 | if (do_enqueue) { |
2181 | | // If we are enqueuing on a CondVar (waitp->cv_word != nullptr) then |
2182 | | // we must not retry here. The initial attempt will always have |
2183 | | // succeeded, further attempts would enqueue us against *this due to |
2184 | | // Fer() handling. |
2185 | 0 | do_enqueue = (waitp->cv_word == nullptr); |
2186 | 0 | new_h = Enqueue(nullptr, waitp, new_readers, kMuIsCond); |
2187 | 0 | } |
2188 | 0 | intptr_t clear = kMuWrWait | kMuWriter; // by default clear write bit |
2189 | 0 | if ((v & kMuWriter) == 0 && ExactlyOneReader(v)) { // last reader |
2190 | 0 | clear = kMuWrWait | kMuReader; // clear read bit |
2191 | 0 | } |
2192 | 0 | nv = (v & kMuLow & ~clear & ~kMuSpin); |
2193 | 0 | if (new_h != nullptr) { |
2194 | 0 | nv |= kMuWait | reinterpret_cast<intptr_t>(new_h); |
2195 | 0 | } else { // new_h could be nullptr if we queued ourselves on a |
2196 | | // CondVar |
2197 | | // In that case, we must place the reader count back in the mutex |
2198 | | // word, as Enqueue() did not store it in the new waiter. |
2199 | 0 | nv |= new_readers & kMuHigh; |
2200 | 0 | } |
2201 | | // release spinlock & our lock; retry if reader-count changed |
2202 | | // (writer count cannot change since we hold lock) |
2203 | 0 | } while (!mu_.compare_exchange_weak(v, nv, std::memory_order_release, |
2204 | 0 | std::memory_order_relaxed)); |
2205 | 0 | break; |
2206 | 0 | } |
2207 | | |
2208 | | // There are waiters. |
2209 | | // Set h to the head of the circular waiter list. |
2210 | 0 | PerThreadSynch* h = GetPerThreadSynch(v); |
2211 | 0 | if ((v & kMuReader) != 0 && (h->readers & kMuHigh) > kMuOne) { |
2212 | | // a reader but not the last |
2213 | 0 | h->readers -= kMuOne; // release our lock |
2214 | 0 | intptr_t nv = v; // normally just release spinlock |
2215 | 0 | if (waitp != nullptr) { // but waitp!=nullptr => must queue ourselves |
2216 | 0 | PerThreadSynch* new_h = Enqueue(h, waitp, v, kMuIsCond); |
2217 | 0 | ABSL_RAW_CHECK(new_h != nullptr, |
2218 | 0 | "waiters disappeared during Enqueue()!"); |
2219 | 0 | nv &= kMuLow; |
2220 | 0 | nv |= kMuWait | reinterpret_cast<intptr_t>(new_h); |
2221 | 0 | } |
2222 | 0 | mu_.store(nv, std::memory_order_release); // release spinlock |
2223 | | // can release with a store because there were waiters |
2224 | 0 | break; |
2225 | 0 | } |
2226 | | |
2227 | | // Either we didn't search before, or we marked the queue |
2228 | | // as "maybe_unlocking" and no one else should have changed it. |
2229 | 0 | ABSL_RAW_CHECK(old_h == nullptr || h->maybe_unlocking, |
2230 | 0 | "Mutex queue changed beneath us"); |
2231 | | |
2232 | | // The lock is becoming free, and there's a waiter |
2233 | 0 | if (old_h != nullptr && |
2234 | 0 | !old_h->may_skip) { // we used old_h as a terminator |
2235 | 0 | old_h->may_skip = true; // allow old_h to skip once more |
2236 | 0 | ABSL_RAW_CHECK(old_h->skip == nullptr, "illegal skip from head"); |
2237 | 0 | if (h != old_h && MuEquivalentWaiter(old_h, old_h->next)) { |
2238 | 0 | old_h->skip = old_h->next; // old_h not head & can skip to successor |
2239 | 0 | } |
2240 | 0 | } |
2241 | 0 | if (h->next->waitp->how == kExclusive && |
2242 | 0 | h->next->waitp->cond == nullptr) { |
2243 | | // easy case: writer with no condition; no need to search |
2244 | 0 | pw = h; // wake w, the successor of h (=pw) |
2245 | 0 | w = h->next; |
2246 | 0 | w->wake = true; |
2247 | | // We are waking up a writer. This writer may be racing against |
2248 | | // an already awake reader for the lock. We want the |
2249 | | // writer to usually win this race, |
2250 | | // because if it doesn't, we can potentially keep taking a reader |
2251 | | // perpetually and writers will starve. Worse than |
2252 | | // that, this can also starve other readers if kMuWrWait gets set |
2253 | | // later. |
2254 | 0 | wr_wait = kMuWrWait; |
2255 | 0 | } else if (w != nullptr && (w->waitp->how == kExclusive || h == old_h)) { |
2256 | | // we found a waiter w to wake on a previous iteration and either it's |
2257 | | // a writer, or we've searched the entire list so we have all the |
2258 | | // readers. |
2259 | 0 | if (pw == nullptr) { // if w's predecessor is unknown, it must be h |
2260 | 0 | pw = h; |
2261 | 0 | } |
2262 | 0 | } else { |
2263 | | // At this point we don't know all the waiters to wake, and the first |
2264 | | // waiter has a condition or is a reader. We avoid searching over |
2265 | | // waiters we've searched on previous iterations by starting at |
2266 | | // old_h if it's set. If old_h==h, there's no one to wakeup at all. |
2267 | 0 | if (old_h == h) { // we've searched before, and nothing's new |
2268 | | // so there's no one to wake. |
2269 | 0 | intptr_t nv = (v & ~(kMuReader | kMuWriter | kMuWrWait)); |
2270 | 0 | h->readers = 0; |
2271 | 0 | h->maybe_unlocking = false; // finished unlocking |
2272 | 0 | if (waitp != nullptr) { // we must queue ourselves and sleep |
2273 | 0 | PerThreadSynch* new_h = Enqueue(h, waitp, v, kMuIsCond); |
2274 | 0 | nv &= kMuLow; |
2275 | 0 | if (new_h != nullptr) { |
2276 | 0 | nv |= kMuWait | reinterpret_cast<intptr_t>(new_h); |
2277 | 0 | } // else new_h could be nullptr if we queued ourselves on a |
2278 | | // CondVar |
2279 | 0 | } |
2280 | | // release spinlock & lock |
2281 | | // can release with a store because there were waiters |
2282 | 0 | mu_.store(nv, std::memory_order_release); |
2283 | 0 | break; |
2284 | 0 | } |
2285 | | |
2286 | | // set up to walk the list |
2287 | 0 | PerThreadSynch* w_walk; // current waiter during list walk |
2288 | 0 | PerThreadSynch* pw_walk; // previous waiter during list walk |
2289 | 0 | if (old_h != nullptr) { // we've searched up to old_h before |
2290 | 0 | pw_walk = old_h; |
2291 | 0 | w_walk = old_h->next; |
2292 | 0 | } else { // no prior search, start at beginning |
2293 | 0 | pw_walk = |
2294 | 0 | nullptr; // h->next's predecessor may change; don't record it |
2295 | 0 | w_walk = h->next; |
2296 | 0 | } |
2297 | |
|
2298 | 0 | h->may_skip = false; // ensure we never skip past h in future searches |
2299 | | // even if other waiters are queued after it. |
2300 | 0 | ABSL_RAW_CHECK(h->skip == nullptr, "illegal skip from head"); |
2301 | | |
2302 | 0 | h->maybe_unlocking = true; // we're about to scan the waiter list |
2303 | | // without the spinlock held. |
2304 | | // Enqueue must be conservative about |
2305 | | // priority queuing. |
2306 | | |
2307 | | // We must release the spinlock to evaluate the conditions. |
2308 | 0 | mu_.store(v, std::memory_order_release); // release just spinlock |
2309 | | // can release with a store because there were waiters |
2310 | | |
2311 | | // h is the last waiter queued, and w_walk the first unsearched waiter. |
2312 | | // Without the spinlock, the locations mu_ and h->next may now change |
2313 | | // underneath us, but since we hold the lock itself, the only legal |
2314 | | // change is to add waiters between h and w_walk. Therefore, it's safe |
2315 | | // to walk the path from w_walk to h inclusive. (TryRemove() can remove |
2316 | | // a waiter anywhere, but it acquires both the spinlock and the Mutex) |
2317 | |
|
2318 | 0 | old_h = h; // remember we searched to here |
2319 | | |
2320 | | // Walk the path upto and including h looking for waiters we can wake. |
2321 | 0 | while (pw_walk != h) { |
2322 | 0 | w_walk->wake = false; |
2323 | 0 | if (w_walk->waitp->cond == |
2324 | 0 | nullptr || // no condition => vacuously true OR |
2325 | | // this thread's condition is true |
2326 | 0 | EvalConditionIgnored(this, w_walk->waitp->cond)) { |
2327 | 0 | if (w == nullptr) { |
2328 | 0 | w_walk->wake = true; // can wake this waiter |
2329 | 0 | w = w_walk; |
2330 | 0 | pw = pw_walk; |
2331 | 0 | if (w_walk->waitp->how == kExclusive) { |
2332 | 0 | wr_wait = kMuWrWait; |
2333 | 0 | break; // bail if waking this writer |
2334 | 0 | } |
2335 | 0 | } else if (w_walk->waitp->how == kShared) { // wake if a reader |
2336 | 0 | w_walk->wake = true; |
2337 | 0 | } else { // writer with true condition |
2338 | 0 | wr_wait = kMuWrWait; |
2339 | 0 | } |
2340 | 0 | } |
2341 | 0 | if (w_walk->wake) { // we're waking reader w_walk |
2342 | 0 | pw_walk = w_walk; // don't skip similar waiters |
2343 | 0 | } else { // not waking; skip as much as possible |
2344 | 0 | pw_walk = Skip(w_walk); |
2345 | 0 | } |
2346 | | // If pw_walk == h, then load of pw_walk->next can race with |
2347 | | // concurrent write in Enqueue(). However, at the same time |
2348 | | // we do not need to do the load, because we will bail out |
2349 | | // from the loop anyway. |
2350 | 0 | if (pw_walk != h) { |
2351 | 0 | w_walk = pw_walk->next; |
2352 | 0 | } |
2353 | 0 | } |
2354 | |
|
2355 | 0 | continue; // restart for(;;)-loop to wakeup w or to find more waiters |
2356 | 0 | } |
2357 | 0 | ABSL_RAW_CHECK(pw->next == w, "pw not w's predecessor"); |
2358 | | // The first (and perhaps only) waiter we've chosen to wake is w, whose |
2359 | | // predecessor is pw. If w is a reader, we must wake all the other |
2360 | | // waiters with wake==true as well. We may also need to queue |
2361 | | // ourselves if waitp != null. The spinlock and the lock are still |
2362 | | // held. |
2363 | | |
2364 | | // This traverses the list in [ pw->next, h ], where h is the head, |
2365 | | // removing all elements with wake==true and placing them in the |
2366 | | // singly-linked list wake_list. Returns the new head. |
2367 | 0 | h = DequeueAllWakeable(h, pw, &wake_list); |
2368 | |
|
2369 | 0 | intptr_t nv = (v & kMuEvent) | kMuDesig; |
2370 | | // assume no waiters left, |
2371 | | // set kMuDesig for INV1a |
2372 | |
|
2373 | 0 | if (waitp != nullptr) { // we must queue ourselves and sleep |
2374 | 0 | h = Enqueue(h, waitp, v, kMuIsCond); |
2375 | | // h is new last waiter; could be null if we queued ourselves on a |
2376 | | // CondVar |
2377 | 0 | } |
2378 | |
|
2379 | 0 | ABSL_RAW_CHECK(wake_list != kPerThreadSynchNull, |
2380 | 0 | "unexpected empty wake list"); |
2381 | | |
2382 | 0 | if (h != nullptr) { // there are waiters left |
2383 | 0 | h->readers = 0; |
2384 | 0 | h->maybe_unlocking = false; // finished unlocking |
2385 | 0 | nv |= wr_wait | kMuWait | reinterpret_cast<intptr_t>(h); |
2386 | 0 | } |
2387 | | |
2388 | | // release both spinlock & lock |
2389 | | // can release with a store because there were waiters |
2390 | 0 | mu_.store(nv, std::memory_order_release); |
2391 | 0 | break; // out of for(;;)-loop |
2392 | 0 | } |
2393 | | // aggressive here; no one can proceed till we do |
2394 | 0 | c = synchronization_internal::MutexDelay(c, AGGRESSIVE); |
2395 | 0 | } // end of for(;;)-loop |
2396 | | |
2397 | 0 | if (wake_list != kPerThreadSynchNull) { |
2398 | 0 | int64_t total_wait_cycles = 0; |
2399 | 0 | int64_t max_wait_cycles = 0; |
2400 | 0 | int64_t now = CycleClock::Now(); |
2401 | 0 | do { |
2402 | | // Profile lock contention events only if the waiter was trying to acquire |
2403 | | // the lock, not waiting on a condition variable or Condition. |
2404 | 0 | if (!wake_list->cond_waiter) { |
2405 | 0 | int64_t cycles_waited = |
2406 | 0 | (now - wake_list->waitp->contention_start_cycles); |
2407 | 0 | total_wait_cycles += cycles_waited; |
2408 | 0 | if (max_wait_cycles == 0) max_wait_cycles = cycles_waited; |
2409 | 0 | wake_list->waitp->contention_start_cycles = now; |
2410 | 0 | wake_list->waitp->should_submit_contention_data = true; |
2411 | 0 | } |
2412 | 0 | wake_list = Wakeup(wake_list); // wake waiters |
2413 | 0 | } while (wake_list != kPerThreadSynchNull); |
2414 | 0 | if (total_wait_cycles > 0) { |
2415 | 0 | mutex_tracer("slow release", this, total_wait_cycles); |
2416 | 0 | ABSL_TSAN_MUTEX_PRE_DIVERT(this, 0); |
2417 | 0 | submit_profile_data(total_wait_cycles); |
2418 | 0 | ABSL_TSAN_MUTEX_POST_DIVERT(this, 0); |
2419 | 0 | } |
2420 | 0 | } |
2421 | 0 | } |
2422 | | |
2423 | | // Used by CondVar implementation to reacquire mutex after waking from |
2424 | | // condition variable. This routine is used instead of Lock() because the |
2425 | | // waiting thread may have been moved from the condition variable queue to the |
2426 | | // mutex queue without a wakeup, by Trans(). In that case, when the thread is |
2427 | | // finally woken, the woken thread will believe it has been woken from the |
2428 | | // condition variable (i.e. its PC will be in when in the CondVar code), when |
2429 | | // in fact it has just been woken from the mutex. Thus, it must enter the slow |
2430 | | // path of the mutex in the same state as if it had just woken from the mutex. |
2431 | | // That is, it must ensure to clear kMuDesig (INV1b). |
2432 | 0 | void Mutex::Trans(MuHow how) { |
2433 | 0 | this->LockSlow(how, nullptr, kMuHasBlocked | kMuIsCond); |
2434 | 0 | } |
2435 | | |
2436 | | // Used by CondVar implementation to effectively wake thread w from the |
2437 | | // condition variable. If this mutex is free, we simply wake the thread. |
2438 | | // It will later acquire the mutex with high probability. Otherwise, we |
2439 | | // enqueue thread w on this mutex. |
2440 | 0 | void Mutex::Fer(PerThreadSynch* w) { |
2441 | 0 | SchedulingGuard::ScopedDisable disable_rescheduling; |
2442 | 0 | int c = 0; |
2443 | 0 | ABSL_RAW_CHECK(w->waitp->cond == nullptr, |
2444 | 0 | "Mutex::Fer while waiting on Condition"); |
2445 | 0 | ABSL_RAW_CHECK(w->waitp->cv_word == nullptr, |
2446 | 0 | "Mutex::Fer with pending CondVar queueing"); |
2447 | | // The CondVar timeout is not relevant for the Mutex wait. |
2448 | 0 | w->waitp->timeout = {}; |
2449 | 0 | for (;;) { |
2450 | 0 | intptr_t v = mu_.load(std::memory_order_relaxed); |
2451 | | // Note: must not queue if the mutex is unlocked (nobody will wake it). |
2452 | | // For example, we can have only kMuWait (conditional) or maybe |
2453 | | // kMuWait|kMuWrWait. |
2454 | | // conflicting != 0 implies that the waking thread cannot currently take |
2455 | | // the mutex, which in turn implies that someone else has it and can wake |
2456 | | // us if we queue. |
2457 | 0 | const intptr_t conflicting = |
2458 | 0 | kMuWriter | (w->waitp->how == kShared ? 0 : kMuReader); |
2459 | 0 | if ((v & conflicting) == 0) { |
2460 | 0 | w->next = nullptr; |
2461 | 0 | w->state.store(PerThreadSynch::kAvailable, std::memory_order_release); |
2462 | 0 | IncrementSynchSem(this, w); |
2463 | 0 | return; |
2464 | 0 | } else { |
2465 | 0 | if ((v & (kMuSpin | kMuWait)) == 0) { // no waiters |
2466 | | // This thread tries to become the one and only waiter. |
2467 | 0 | PerThreadSynch* new_h = |
2468 | 0 | Enqueue(nullptr, w->waitp, v, kMuIsCond | kMuIsFer); |
2469 | 0 | ABSL_RAW_CHECK(new_h != nullptr, |
2470 | 0 | "Enqueue failed"); // we must queue ourselves |
2471 | 0 | if (mu_.compare_exchange_strong( |
2472 | 0 | v, reinterpret_cast<intptr_t>(new_h) | (v & kMuLow) | kMuWait, |
2473 | 0 | std::memory_order_release, std::memory_order_relaxed)) { |
2474 | 0 | return; |
2475 | 0 | } |
2476 | 0 | } else if ((v & kMuSpin) == 0 && |
2477 | 0 | mu_.compare_exchange_strong(v, v | kMuSpin | kMuWait)) { |
2478 | 0 | PerThreadSynch* h = GetPerThreadSynch(v); |
2479 | 0 | PerThreadSynch* new_h = Enqueue(h, w->waitp, v, kMuIsCond | kMuIsFer); |
2480 | 0 | ABSL_RAW_CHECK(new_h != nullptr, |
2481 | 0 | "Enqueue failed"); // we must queue ourselves |
2482 | 0 | do { |
2483 | 0 | v = mu_.load(std::memory_order_relaxed); |
2484 | 0 | } while (!mu_.compare_exchange_weak( |
2485 | 0 | v, |
2486 | 0 | (v & kMuLow & ~kMuSpin) | kMuWait | |
2487 | 0 | reinterpret_cast<intptr_t>(new_h), |
2488 | 0 | std::memory_order_release, std::memory_order_relaxed)); |
2489 | 0 | return; |
2490 | 0 | } |
2491 | 0 | } |
2492 | 0 | c = synchronization_internal::MutexDelay(c, GENTLE); |
2493 | 0 | } |
2494 | 0 | } |
2495 | | |
2496 | 0 | void Mutex::AssertHeld() const { |
2497 | 0 | if ((mu_.load(std::memory_order_relaxed) & kMuWriter) == 0) { |
2498 | 0 | SynchEvent* e = GetSynchEvent(this); |
2499 | 0 | ABSL_RAW_LOG(FATAL, "thread should hold write lock on Mutex %p %s", |
2500 | 0 | static_cast<const void*>(this), (e == nullptr ? "" : e->name)); |
2501 | 0 | } |
2502 | 0 | } |
2503 | | |
2504 | 0 | void Mutex::AssertReaderHeld() const { |
2505 | 0 | if ((mu_.load(std::memory_order_relaxed) & (kMuReader | kMuWriter)) == 0) { |
2506 | 0 | SynchEvent* e = GetSynchEvent(this); |
2507 | 0 | ABSL_RAW_LOG(FATAL, |
2508 | 0 | "thread should hold at least a read lock on Mutex %p %s", |
2509 | 0 | static_cast<const void*>(this), (e == nullptr ? "" : e->name)); |
2510 | 0 | } |
2511 | 0 | } |
2512 | | |
2513 | | // -------------------------------- condition variables |
2514 | | static const intptr_t kCvSpin = 0x0001L; // spinlock protects waiter list |
2515 | | static const intptr_t kCvEvent = 0x0002L; // record events |
2516 | | |
2517 | | static const intptr_t kCvLow = 0x0003L; // low order bits of CV |
2518 | | |
2519 | | // Hack to make constant values available to gdb pretty printer |
2520 | | enum { |
2521 | | kGdbCvSpin = kCvSpin, |
2522 | | kGdbCvEvent = kCvEvent, |
2523 | | kGdbCvLow = kCvLow, |
2524 | | }; |
2525 | | |
2526 | | static_assert(PerThreadSynch::kAlignment > kCvLow, |
2527 | | "PerThreadSynch::kAlignment must be greater than kCvLow"); |
2528 | | |
2529 | 0 | void CondVar::EnableDebugLog(const char* name) { |
2530 | 0 | SynchEvent* e = EnsureSynchEvent(&this->cv_, name, kCvEvent, kCvSpin); |
2531 | 0 | e->log = true; |
2532 | 0 | UnrefSynchEvent(e); |
2533 | 0 | } |
2534 | | |
2535 | | // Remove thread s from the list of waiters on this condition variable. |
2536 | 0 | void CondVar::Remove(PerThreadSynch* s) { |
2537 | 0 | SchedulingGuard::ScopedDisable disable_rescheduling; |
2538 | 0 | intptr_t v; |
2539 | 0 | int c = 0; |
2540 | 0 | for (v = cv_.load(std::memory_order_relaxed);; |
2541 | 0 | v = cv_.load(std::memory_order_relaxed)) { |
2542 | 0 | if ((v & kCvSpin) == 0 && // attempt to acquire spinlock |
2543 | 0 | cv_.compare_exchange_strong(v, v | kCvSpin, std::memory_order_acquire, |
2544 | 0 | std::memory_order_relaxed)) { |
2545 | 0 | PerThreadSynch* h = reinterpret_cast<PerThreadSynch*>(v & ~kCvLow); |
2546 | 0 | if (h != nullptr) { |
2547 | 0 | PerThreadSynch* w = h; |
2548 | 0 | while (w->next != s && w->next != h) { // search for thread |
2549 | 0 | w = w->next; |
2550 | 0 | } |
2551 | 0 | if (w->next == s) { // found thread; remove it |
2552 | 0 | w->next = s->next; |
2553 | 0 | if (h == s) { |
2554 | 0 | h = (w == s) ? nullptr : w; |
2555 | 0 | } |
2556 | 0 | s->next = nullptr; |
2557 | 0 | s->state.store(PerThreadSynch::kAvailable, std::memory_order_release); |
2558 | 0 | } |
2559 | 0 | } |
2560 | | // release spinlock |
2561 | 0 | cv_.store((v & kCvEvent) | reinterpret_cast<intptr_t>(h), |
2562 | 0 | std::memory_order_release); |
2563 | 0 | return; |
2564 | 0 | } else { |
2565 | | // try again after a delay |
2566 | 0 | c = synchronization_internal::MutexDelay(c, GENTLE); |
2567 | 0 | } |
2568 | 0 | } |
2569 | 0 | } |
2570 | | |
2571 | | // Queue thread waitp->thread on condition variable word cv_word using |
2572 | | // wait parameters waitp. |
2573 | | // We split this into a separate routine, rather than simply doing it as part |
2574 | | // of WaitCommon(). If we were to queue ourselves on the condition variable |
2575 | | // before calling Mutex::UnlockSlow(), the Mutex code might be re-entered (via |
2576 | | // the logging code, or via a Condition function) and might potentially attempt |
2577 | | // to block this thread. That would be a problem if the thread were already on |
2578 | | // a condition variable waiter queue. Thus, we use the waitp->cv_word to tell |
2579 | | // the unlock code to call CondVarEnqueue() to queue the thread on the condition |
2580 | | // variable queue just before the mutex is to be unlocked, and (most |
2581 | | // importantly) after any call to an external routine that might re-enter the |
2582 | | // mutex code. |
2583 | 0 | static void CondVarEnqueue(SynchWaitParams* waitp) { |
2584 | | // This thread might be transferred to the Mutex queue by Fer() when |
2585 | | // we are woken. To make sure that is what happens, Enqueue() doesn't |
2586 | | // call CondVarEnqueue() again but instead uses its normal code. We |
2587 | | // must do this before we queue ourselves so that cv_word will be null |
2588 | | // when seen by the dequeuer, who may wish immediately to requeue |
2589 | | // this thread on another queue. |
2590 | 0 | std::atomic<intptr_t>* cv_word = waitp->cv_word; |
2591 | 0 | waitp->cv_word = nullptr; |
2592 | |
|
2593 | 0 | intptr_t v = cv_word->load(std::memory_order_relaxed); |
2594 | 0 | int c = 0; |
2595 | 0 | while ((v & kCvSpin) != 0 || // acquire spinlock |
2596 | 0 | !cv_word->compare_exchange_weak(v, v | kCvSpin, |
2597 | 0 | std::memory_order_acquire, |
2598 | 0 | std::memory_order_relaxed)) { |
2599 | 0 | c = synchronization_internal::MutexDelay(c, GENTLE); |
2600 | 0 | v = cv_word->load(std::memory_order_relaxed); |
2601 | 0 | } |
2602 | 0 | ABSL_RAW_CHECK(waitp->thread->waitp == nullptr, "waiting when shouldn't be"); |
2603 | 0 | waitp->thread->waitp = waitp; // prepare ourselves for waiting |
2604 | 0 | PerThreadSynch* h = reinterpret_cast<PerThreadSynch*>(v & ~kCvLow); |
2605 | 0 | if (h == nullptr) { // add this thread to waiter list |
2606 | 0 | waitp->thread->next = waitp->thread; |
2607 | 0 | } else { |
2608 | 0 | waitp->thread->next = h->next; |
2609 | 0 | h->next = waitp->thread; |
2610 | 0 | } |
2611 | 0 | waitp->thread->state.store(PerThreadSynch::kQueued, |
2612 | 0 | std::memory_order_relaxed); |
2613 | 0 | cv_word->store((v & kCvEvent) | reinterpret_cast<intptr_t>(waitp->thread), |
2614 | 0 | std::memory_order_release); |
2615 | 0 | } |
2616 | | |
2617 | 0 | bool CondVar::WaitCommon(Mutex* mutex, KernelTimeout t) { |
2618 | 0 | bool rc = false; // return value; true iff we timed-out |
2619 | |
|
2620 | 0 | intptr_t mutex_v = mutex->mu_.load(std::memory_order_relaxed); |
2621 | 0 | Mutex::MuHow mutex_how = ((mutex_v & kMuWriter) != 0) ? kExclusive : kShared; |
2622 | 0 | ABSL_TSAN_MUTEX_PRE_UNLOCK(mutex, TsanFlags(mutex_how)); |
2623 | | |
2624 | | // maybe trace this call |
2625 | 0 | intptr_t v = cv_.load(std::memory_order_relaxed); |
2626 | 0 | cond_var_tracer("Wait", this); |
2627 | 0 | if ((v & kCvEvent) != 0) { |
2628 | 0 | PostSynchEvent(this, SYNCH_EV_WAIT); |
2629 | 0 | } |
2630 | | |
2631 | | // Release mu and wait on condition variable. |
2632 | 0 | SynchWaitParams waitp(mutex_how, nullptr, t, mutex, |
2633 | 0 | Synch_GetPerThreadAnnotated(mutex), &cv_); |
2634 | | // UnlockSlow() will call CondVarEnqueue() just before releasing the |
2635 | | // Mutex, thus queuing this thread on the condition variable. See |
2636 | | // CondVarEnqueue() for the reasons. |
2637 | 0 | mutex->UnlockSlow(&waitp); |
2638 | | |
2639 | | // wait for signal |
2640 | 0 | while (waitp.thread->state.load(std::memory_order_acquire) == |
2641 | 0 | PerThreadSynch::kQueued) { |
2642 | 0 | if (!Mutex::DecrementSynchSem(mutex, waitp.thread, t)) { |
2643 | | // DecrementSynchSem returned due to timeout. |
2644 | | // Now we will either (1) remove ourselves from the wait list in Remove |
2645 | | // below, in which case Remove will set thread.state = kAvailable and |
2646 | | // we will not call DecrementSynchSem again; or (2) Signal/SignalAll |
2647 | | // has removed us concurrently and is calling Wakeup, which will set |
2648 | | // thread.state = kAvailable and post to the semaphore. |
2649 | | // It's important to reset the timeout for the case (2) because otherwise |
2650 | | // we can live-lock in this loop since DecrementSynchSem will always |
2651 | | // return immediately due to timeout, but Signal/SignalAll is not |
2652 | | // necessary set thread.state = kAvailable yet (and is not scheduled |
2653 | | // due to thread priorities or other scheduler artifacts). |
2654 | | // Note this could also be resolved if Signal/SignalAll would set |
2655 | | // thread.state = kAvailable while holding the wait list spin lock. |
2656 | | // But this can't be easily done for SignalAll since it grabs the whole |
2657 | | // wait list with a single compare-exchange and does not really grab |
2658 | | // the spin lock. |
2659 | 0 | t = KernelTimeout::Never(); |
2660 | 0 | this->Remove(waitp.thread); |
2661 | 0 | rc = true; |
2662 | 0 | } |
2663 | 0 | } |
2664 | |
|
2665 | 0 | ABSL_RAW_CHECK(waitp.thread->waitp != nullptr, "not waiting when should be"); |
2666 | 0 | waitp.thread->waitp = nullptr; // cleanup |
2667 | | |
2668 | | // maybe trace this call |
2669 | 0 | cond_var_tracer("Unwait", this); |
2670 | 0 | if ((v & kCvEvent) != 0) { |
2671 | 0 | PostSynchEvent(this, SYNCH_EV_WAIT_RETURNING); |
2672 | 0 | } |
2673 | | |
2674 | | // From synchronization point of view Wait is unlock of the mutex followed |
2675 | | // by lock of the mutex. We've annotated start of unlock in the beginning |
2676 | | // of the function. Now, finish unlock and annotate lock of the mutex. |
2677 | | // (Trans is effectively lock). |
2678 | 0 | ABSL_TSAN_MUTEX_POST_UNLOCK(mutex, TsanFlags(mutex_how)); |
2679 | 0 | ABSL_TSAN_MUTEX_PRE_LOCK(mutex, TsanFlags(mutex_how)); |
2680 | 0 | mutex->Trans(mutex_how); // Reacquire mutex |
2681 | 0 | ABSL_TSAN_MUTEX_POST_LOCK(mutex, TsanFlags(mutex_how), 0); |
2682 | 0 | return rc; |
2683 | 0 | } |
2684 | | |
2685 | 0 | void CondVar::Signal() { |
2686 | 0 | SchedulingGuard::ScopedDisable disable_rescheduling; |
2687 | 0 | ABSL_TSAN_MUTEX_PRE_SIGNAL(nullptr, 0); |
2688 | 0 | intptr_t v; |
2689 | 0 | int c = 0; |
2690 | 0 | for (v = cv_.load(std::memory_order_relaxed); v != 0; |
2691 | 0 | v = cv_.load(std::memory_order_relaxed)) { |
2692 | 0 | if ((v & kCvSpin) == 0 && // attempt to acquire spinlock |
2693 | 0 | cv_.compare_exchange_strong(v, v | kCvSpin, std::memory_order_acquire, |
2694 | 0 | std::memory_order_relaxed)) { |
2695 | 0 | PerThreadSynch* h = reinterpret_cast<PerThreadSynch*>(v & ~kCvLow); |
2696 | 0 | PerThreadSynch* w = nullptr; |
2697 | 0 | if (h != nullptr) { // remove first waiter |
2698 | 0 | w = h->next; |
2699 | 0 | if (w == h) { |
2700 | 0 | h = nullptr; |
2701 | 0 | } else { |
2702 | 0 | h->next = w->next; |
2703 | 0 | } |
2704 | 0 | } |
2705 | | // release spinlock |
2706 | 0 | cv_.store((v & kCvEvent) | reinterpret_cast<intptr_t>(h), |
2707 | 0 | std::memory_order_release); |
2708 | 0 | if (w != nullptr) { |
2709 | 0 | w->waitp->cvmu->Fer(w); // wake waiter, if there was one |
2710 | 0 | cond_var_tracer("Signal wakeup", this); |
2711 | 0 | } |
2712 | 0 | if ((v & kCvEvent) != 0) { |
2713 | 0 | PostSynchEvent(this, SYNCH_EV_SIGNAL); |
2714 | 0 | } |
2715 | 0 | ABSL_TSAN_MUTEX_POST_SIGNAL(nullptr, 0); |
2716 | 0 | return; |
2717 | 0 | } else { |
2718 | 0 | c = synchronization_internal::MutexDelay(c, GENTLE); |
2719 | 0 | } |
2720 | 0 | } |
2721 | 0 | ABSL_TSAN_MUTEX_POST_SIGNAL(nullptr, 0); |
2722 | 0 | } |
2723 | | |
2724 | 0 | void CondVar::SignalAll() { |
2725 | 0 | ABSL_TSAN_MUTEX_PRE_SIGNAL(nullptr, 0); |
2726 | 0 | intptr_t v; |
2727 | 0 | int c = 0; |
2728 | 0 | for (v = cv_.load(std::memory_order_relaxed); v != 0; |
2729 | 0 | v = cv_.load(std::memory_order_relaxed)) { |
2730 | | // empty the list if spinlock free |
2731 | | // We do this by simply setting the list to empty using |
2732 | | // compare and swap. We then have the entire list in our hands, |
2733 | | // which cannot be changing since we grabbed it while no one |
2734 | | // held the lock. |
2735 | 0 | if ((v & kCvSpin) == 0 && |
2736 | 0 | cv_.compare_exchange_strong(v, v & kCvEvent, std::memory_order_acquire, |
2737 | 0 | std::memory_order_relaxed)) { |
2738 | 0 | PerThreadSynch* h = reinterpret_cast<PerThreadSynch*>(v & ~kCvLow); |
2739 | 0 | if (h != nullptr) { |
2740 | 0 | PerThreadSynch* w; |
2741 | 0 | PerThreadSynch* n = h->next; |
2742 | 0 | do { // for every thread, wake it up |
2743 | 0 | w = n; |
2744 | 0 | n = n->next; |
2745 | 0 | w->waitp->cvmu->Fer(w); |
2746 | 0 | } while (w != h); |
2747 | 0 | cond_var_tracer("SignalAll wakeup", this); |
2748 | 0 | } |
2749 | 0 | if ((v & kCvEvent) != 0) { |
2750 | 0 | PostSynchEvent(this, SYNCH_EV_SIGNALALL); |
2751 | 0 | } |
2752 | 0 | ABSL_TSAN_MUTEX_POST_SIGNAL(nullptr, 0); |
2753 | 0 | return; |
2754 | 0 | } else { |
2755 | | // try again after a delay |
2756 | 0 | c = synchronization_internal::MutexDelay(c, GENTLE); |
2757 | 0 | } |
2758 | 0 | } |
2759 | 0 | ABSL_TSAN_MUTEX_POST_SIGNAL(nullptr, 0); |
2760 | 0 | } |
2761 | | |
2762 | 0 | void ReleasableMutexLock::Release() { |
2763 | 0 | ABSL_RAW_CHECK(this->mu_ != nullptr, |
2764 | 0 | "ReleasableMutexLock::Release may only be called once"); |
2765 | 0 | this->mu_->Unlock(); |
2766 | 0 | this->mu_ = nullptr; |
2767 | 0 | } |
2768 | | |
2769 | | #ifdef ABSL_HAVE_THREAD_SANITIZER |
2770 | | extern "C" void __tsan_read1(void* addr); |
2771 | | #else |
2772 | | #define __tsan_read1(addr) // do nothing if TSan not enabled |
2773 | | #endif |
2774 | | |
2775 | | // A function that just returns its argument, dereferenced |
2776 | 0 | static bool Dereference(void* arg) { |
2777 | | // ThreadSanitizer does not instrument this file for memory accesses. |
2778 | | // This function dereferences a user variable that can participate |
2779 | | // in a data race, so we need to manually tell TSan about this memory access. |
2780 | 0 | __tsan_read1(arg); |
2781 | 0 | return *(static_cast<bool*>(arg)); |
2782 | 0 | } |
2783 | | |
2784 | | ABSL_CONST_INIT const Condition Condition::kTrue; |
2785 | | |
2786 | | Condition::Condition(bool (*func)(void*), void* arg) |
2787 | 0 | : eval_(&CallVoidPtrFunction), arg_(arg) { |
2788 | 0 | static_assert(sizeof(&func) <= sizeof(callback_), |
2789 | 0 | "An overlarge function pointer passed to Condition."); |
2790 | 0 | StoreCallback(func); |
2791 | 0 | } |
2792 | | |
2793 | 0 | bool Condition::CallVoidPtrFunction(const Condition* c) { |
2794 | 0 | using FunctionPointer = bool (*)(void*); |
2795 | 0 | FunctionPointer function_pointer; |
2796 | 0 | std::memcpy(&function_pointer, c->callback_, sizeof(function_pointer)); |
2797 | 0 | return (*function_pointer)(c->arg_); |
2798 | 0 | } |
2799 | | |
2800 | | Condition::Condition(const bool* cond) |
2801 | 0 | : eval_(CallVoidPtrFunction), |
2802 | | // const_cast is safe since Dereference does not modify arg |
2803 | 0 | arg_(const_cast<bool*>(cond)) { |
2804 | 0 | using FunctionPointer = bool (*)(void*); |
2805 | 0 | const FunctionPointer dereference = Dereference; |
2806 | 0 | StoreCallback(dereference); |
2807 | 0 | } |
2808 | | |
2809 | 0 | bool Condition::Eval() const { return (*this->eval_)(this); } |
2810 | | |
2811 | 0 | bool Condition::GuaranteedEqual(const Condition* a, const Condition* b) { |
2812 | 0 | if (a == nullptr || b == nullptr) { |
2813 | 0 | return a == b; |
2814 | 0 | } |
2815 | | // Check equality of the representative fields. |
2816 | 0 | return a->eval_ == b->eval_ && a->arg_ == b->arg_ && |
2817 | 0 | !memcmp(a->callback_, b->callback_, sizeof(a->callback_)); |
2818 | 0 | } |
2819 | | |
2820 | | ABSL_NAMESPACE_END |
2821 | | } // namespace absl |