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 #endif
20
21 #include <algorithm>
22 #include <atomic>
23 #include <cstdlib>
24 #include <functional>
25 #include <memory>
26 #include <random>
27 #include <string>
28 #include <thread> // NOLINT(build/c++11)
29 #include <vector>
30
31 #include "gtest/gtest.h"
32 #include "absl/base/attributes.h"
33 #include "absl/base/config.h"
34 #include "absl/base/internal/raw_logging.h"
35 #include "absl/base/internal/sysinfo.h"
36 #include "absl/memory/memory.h"
37 #include "absl/synchronization/internal/thread_pool.h"
38 #include "absl/time/clock.h"
39 #include "absl/time/time.h"
40
41 namespace {
42
43 // TODO(dmauro): Replace with a commandline flag.
44 static constexpr bool kExtendedTest = false;
45
CreatePool(int threads)46 std::unique_ptr<absl::synchronization_internal::ThreadPool> CreatePool(
47 int threads) {
48 return absl::make_unique<absl::synchronization_internal::ThreadPool>(threads);
49 }
50
51 std::unique_ptr<absl::synchronization_internal::ThreadPool>
CreateDefaultPool()52 CreateDefaultPool() {
53 return CreatePool(kExtendedTest ? 32 : 10);
54 }
55
56 // Hack to schedule a function to run on a thread pool thread after a
57 // duration has elapsed.
ScheduleAfter(absl::synchronization_internal::ThreadPool * tp,absl::Duration after,const std::function<void ()> & func)58 static void ScheduleAfter(absl::synchronization_internal::ThreadPool *tp,
59 absl::Duration after,
60 const std::function<void()> &func) {
61 tp->Schedule([func, after] {
62 absl::SleepFor(after);
63 func();
64 });
65 }
66
67 struct TestContext {
68 int iterations;
69 int threads;
70 int g0; // global 0
71 int g1; // global 1
72 absl::Mutex mu;
73 absl::CondVar cv;
74 };
75
76 // To test whether the invariant check call occurs
77 static std::atomic<bool> invariant_checked;
78
GetInvariantChecked()79 static bool GetInvariantChecked() {
80 return invariant_checked.load(std::memory_order_relaxed);
81 }
82
SetInvariantChecked(bool new_value)83 static void SetInvariantChecked(bool new_value) {
84 invariant_checked.store(new_value, std::memory_order_relaxed);
85 }
86
CheckSumG0G1(void * v)87 static void CheckSumG0G1(void *v) {
88 TestContext *cxt = static_cast<TestContext *>(v);
89 ABSL_RAW_CHECK(cxt->g0 == -cxt->g1, "Error in CheckSumG0G1");
90 SetInvariantChecked(true);
91 }
92
TestMu(TestContext * cxt,int c)93 static void TestMu(TestContext *cxt, int c) {
94 for (int i = 0; i != cxt->iterations; i++) {
95 absl::MutexLock l(&cxt->mu);
96 int a = cxt->g0 + 1;
97 cxt->g0 = a;
98 cxt->g1--;
99 }
100 }
101
TestTry(TestContext * cxt,int c)102 static void TestTry(TestContext *cxt, int c) {
103 for (int i = 0; i != cxt->iterations; i++) {
104 do {
105 std::this_thread::yield();
106 } while (!cxt->mu.TryLock());
107 int a = cxt->g0 + 1;
108 cxt->g0 = a;
109 cxt->g1--;
110 cxt->mu.Unlock();
111 }
112 }
113
TestR20ms(TestContext * cxt,int c)114 static void TestR20ms(TestContext *cxt, int c) {
115 for (int i = 0; i != cxt->iterations; i++) {
116 absl::ReaderMutexLock l(&cxt->mu);
117 absl::SleepFor(absl::Milliseconds(20));
118 cxt->mu.AssertReaderHeld();
119 }
120 }
121
TestRW(TestContext * cxt,int c)122 static void TestRW(TestContext *cxt, int c) {
123 if ((c & 1) == 0) {
124 for (int i = 0; i != cxt->iterations; i++) {
125 absl::WriterMutexLock l(&cxt->mu);
126 cxt->g0++;
127 cxt->g1--;
128 cxt->mu.AssertHeld();
129 cxt->mu.AssertReaderHeld();
130 }
131 } else {
132 for (int i = 0; i != cxt->iterations; i++) {
133 absl::ReaderMutexLock l(&cxt->mu);
134 ABSL_RAW_CHECK(cxt->g0 == -cxt->g1, "Error in TestRW");
135 cxt->mu.AssertReaderHeld();
136 }
137 }
138 }
139
140 struct MyContext {
141 int target;
142 TestContext *cxt;
143 bool MyTurn();
144 };
145
MyTurn()146 bool MyContext::MyTurn() {
147 TestContext *cxt = this->cxt;
148 return cxt->g0 == this->target || cxt->g0 == cxt->iterations;
149 }
150
TestAwait(TestContext * cxt,int c)151 static void TestAwait(TestContext *cxt, int c) {
152 MyContext mc;
153 mc.target = c;
154 mc.cxt = cxt;
155 absl::MutexLock l(&cxt->mu);
156 cxt->mu.AssertHeld();
157 while (cxt->g0 < cxt->iterations) {
158 cxt->mu.Await(absl::Condition(&mc, &MyContext::MyTurn));
159 ABSL_RAW_CHECK(mc.MyTurn(), "Error in TestAwait");
160 cxt->mu.AssertHeld();
161 if (cxt->g0 < cxt->iterations) {
162 int a = cxt->g0 + 1;
163 cxt->g0 = a;
164 mc.target += cxt->threads;
165 }
166 }
167 }
168
TestSignalAll(TestContext * cxt,int c)169 static void TestSignalAll(TestContext *cxt, int c) {
170 int target = c;
171 absl::MutexLock l(&cxt->mu);
172 cxt->mu.AssertHeld();
173 while (cxt->g0 < cxt->iterations) {
174 while (cxt->g0 != target && cxt->g0 != cxt->iterations) {
175 cxt->cv.Wait(&cxt->mu);
176 }
177 if (cxt->g0 < cxt->iterations) {
178 int a = cxt->g0 + 1;
179 cxt->g0 = a;
180 cxt->cv.SignalAll();
181 target += cxt->threads;
182 }
183 }
184 }
185
TestSignal(TestContext * cxt,int c)186 static void TestSignal(TestContext *cxt, int c) {
187 ABSL_RAW_CHECK(cxt->threads == 2, "TestSignal should use 2 threads");
188 int target = c;
189 absl::MutexLock l(&cxt->mu);
190 cxt->mu.AssertHeld();
191 while (cxt->g0 < cxt->iterations) {
192 while (cxt->g0 != target && cxt->g0 != cxt->iterations) {
193 cxt->cv.Wait(&cxt->mu);
194 }
195 if (cxt->g0 < cxt->iterations) {
196 int a = cxt->g0 + 1;
197 cxt->g0 = a;
198 cxt->cv.Signal();
199 target += cxt->threads;
200 }
201 }
202 }
203
TestCVTimeout(TestContext * cxt,int c)204 static void TestCVTimeout(TestContext *cxt, int c) {
205 int target = c;
206 absl::MutexLock l(&cxt->mu);
207 cxt->mu.AssertHeld();
208 while (cxt->g0 < cxt->iterations) {
209 while (cxt->g0 != target && cxt->g0 != cxt->iterations) {
210 cxt->cv.WaitWithTimeout(&cxt->mu, absl::Seconds(100));
211 }
212 if (cxt->g0 < cxt->iterations) {
213 int a = cxt->g0 + 1;
214 cxt->g0 = a;
215 cxt->cv.SignalAll();
216 target += cxt->threads;
217 }
218 }
219 }
220
G0GE2(TestContext * cxt)221 static bool G0GE2(TestContext *cxt) { return cxt->g0 >= 2; }
222
TestTime(TestContext * cxt,int c,bool use_cv)223 static void TestTime(TestContext *cxt, int c, bool use_cv) {
224 ABSL_RAW_CHECK(cxt->iterations == 1, "TestTime should only use 1 iteration");
225 ABSL_RAW_CHECK(cxt->threads > 2, "TestTime should use more than 2 threads");
226 const bool kFalse = false;
227 absl::Condition false_cond(&kFalse);
228 absl::Condition g0ge2(G0GE2, cxt);
229 if (c == 0) {
230 absl::MutexLock l(&cxt->mu);
231
232 absl::Time start = absl::Now();
233 if (use_cv) {
234 cxt->cv.WaitWithTimeout(&cxt->mu, absl::Seconds(1));
235 } else {
236 ABSL_RAW_CHECK(!cxt->mu.AwaitWithTimeout(false_cond, absl::Seconds(1)),
237 "TestTime failed");
238 }
239 absl::Duration elapsed = absl::Now() - start;
240 ABSL_RAW_CHECK(
241 absl::Seconds(0.9) <= elapsed && elapsed <= absl::Seconds(2.0),
242 "TestTime failed");
243 ABSL_RAW_CHECK(cxt->g0 == 1, "TestTime failed");
244
245 start = absl::Now();
246 if (use_cv) {
247 cxt->cv.WaitWithTimeout(&cxt->mu, absl::Seconds(1));
248 } else {
249 ABSL_RAW_CHECK(!cxt->mu.AwaitWithTimeout(false_cond, absl::Seconds(1)),
250 "TestTime failed");
251 }
252 elapsed = absl::Now() - start;
253 ABSL_RAW_CHECK(
254 absl::Seconds(0.9) <= elapsed && elapsed <= absl::Seconds(2.0),
255 "TestTime failed");
256 cxt->g0++;
257 if (use_cv) {
258 cxt->cv.Signal();
259 }
260
261 start = absl::Now();
262 if (use_cv) {
263 cxt->cv.WaitWithTimeout(&cxt->mu, absl::Seconds(4));
264 } else {
265 ABSL_RAW_CHECK(!cxt->mu.AwaitWithTimeout(false_cond, absl::Seconds(4)),
266 "TestTime failed");
267 }
268 elapsed = absl::Now() - start;
269 ABSL_RAW_CHECK(
270 absl::Seconds(3.9) <= elapsed && elapsed <= absl::Seconds(6.0),
271 "TestTime failed");
272 ABSL_RAW_CHECK(cxt->g0 >= 3, "TestTime failed");
273
274 start = absl::Now();
275 if (use_cv) {
276 cxt->cv.WaitWithTimeout(&cxt->mu, absl::Seconds(1));
277 } else {
278 ABSL_RAW_CHECK(!cxt->mu.AwaitWithTimeout(false_cond, absl::Seconds(1)),
279 "TestTime failed");
280 }
281 elapsed = absl::Now() - start;
282 ABSL_RAW_CHECK(
283 absl::Seconds(0.9) <= elapsed && elapsed <= absl::Seconds(2.0),
284 "TestTime failed");
285 if (use_cv) {
286 cxt->cv.SignalAll();
287 }
288
289 start = absl::Now();
290 if (use_cv) {
291 cxt->cv.WaitWithTimeout(&cxt->mu, absl::Seconds(1));
292 } else {
293 ABSL_RAW_CHECK(!cxt->mu.AwaitWithTimeout(false_cond, absl::Seconds(1)),
294 "TestTime failed");
295 }
296 elapsed = absl::Now() - start;
297 ABSL_RAW_CHECK(absl::Seconds(0.9) <= elapsed &&
298 elapsed <= absl::Seconds(2.0), "TestTime failed");
299 ABSL_RAW_CHECK(cxt->g0 == cxt->threads, "TestTime failed");
300
301 } else if (c == 1) {
302 absl::MutexLock l(&cxt->mu);
303 const absl::Time start = absl::Now();
304 if (use_cv) {
305 cxt->cv.WaitWithTimeout(&cxt->mu, absl::Milliseconds(500));
306 } else {
307 ABSL_RAW_CHECK(
308 !cxt->mu.AwaitWithTimeout(false_cond, absl::Milliseconds(500)),
309 "TestTime failed");
310 }
311 const absl::Duration elapsed = absl::Now() - start;
312 ABSL_RAW_CHECK(
313 absl::Seconds(0.4) <= elapsed && elapsed <= absl::Seconds(0.9),
314 "TestTime failed");
315 cxt->g0++;
316 } else if (c == 2) {
317 absl::MutexLock l(&cxt->mu);
318 if (use_cv) {
319 while (cxt->g0 < 2) {
320 cxt->cv.WaitWithTimeout(&cxt->mu, absl::Seconds(100));
321 }
322 } else {
323 ABSL_RAW_CHECK(cxt->mu.AwaitWithTimeout(g0ge2, absl::Seconds(100)),
324 "TestTime failed");
325 }
326 cxt->g0++;
327 } else {
328 absl::MutexLock l(&cxt->mu);
329 if (use_cv) {
330 while (cxt->g0 < 2) {
331 cxt->cv.Wait(&cxt->mu);
332 }
333 } else {
334 cxt->mu.Await(g0ge2);
335 }
336 cxt->g0++;
337 }
338 }
339
TestMuTime(TestContext * cxt,int c)340 static void TestMuTime(TestContext *cxt, int c) { TestTime(cxt, c, false); }
341
TestCVTime(TestContext * cxt,int c)342 static void TestCVTime(TestContext *cxt, int c) { TestTime(cxt, c, true); }
343
EndTest(int * c0,int * c1,absl::Mutex * mu,absl::CondVar * cv,const std::function<void (int)> & cb)344 static void EndTest(int *c0, int *c1, absl::Mutex *mu, absl::CondVar *cv,
345 const std::function<void(int)>& cb) {
346 mu->Lock();
347 int c = (*c0)++;
348 mu->Unlock();
349 cb(c);
350 absl::MutexLock l(mu);
351 (*c1)++;
352 cv->Signal();
353 }
354
355 // Code common to RunTest() and RunTestWithInvariantDebugging().
RunTestCommon(TestContext * cxt,void (* test)(TestContext * cxt,int),int threads,int iterations,int operations)356 static int RunTestCommon(TestContext *cxt, void (*test)(TestContext *cxt, int),
357 int threads, int iterations, int operations) {
358 absl::Mutex mu2;
359 absl::CondVar cv2;
360 int c0 = 0;
361 int c1 = 0;
362 cxt->g0 = 0;
363 cxt->g1 = 0;
364 cxt->iterations = iterations;
365 cxt->threads = threads;
366 absl::synchronization_internal::ThreadPool tp(threads);
367 for (int i = 0; i != threads; i++) {
368 tp.Schedule(std::bind(&EndTest, &c0, &c1, &mu2, &cv2,
369 std::function<void(int)>(
370 std::bind(test, cxt, std::placeholders::_1))));
371 }
372 mu2.Lock();
373 while (c1 != threads) {
374 cv2.Wait(&mu2);
375 }
376 mu2.Unlock();
377 return cxt->g0;
378 }
379
380 // Basis for the parameterized tests configured below.
RunTest(void (* test)(TestContext * cxt,int),int threads,int iterations,int operations)381 static int RunTest(void (*test)(TestContext *cxt, int), int threads,
382 int iterations, int operations) {
383 TestContext cxt;
384 return RunTestCommon(&cxt, test, threads, iterations, operations);
385 }
386
387 // Like RunTest(), but sets an invariant on the tested Mutex and
388 // verifies that the invariant check happened. The invariant function
389 // will be passed the TestContext* as its arg and must call
390 // SetInvariantChecked(true);
391 #if !defined(ABSL_MUTEX_ENABLE_INVARIANT_DEBUGGING_NOT_IMPLEMENTED)
RunTestWithInvariantDebugging(void (* test)(TestContext * cxt,int),int threads,int iterations,int operations,void (* invariant)(void *))392 static int RunTestWithInvariantDebugging(void (*test)(TestContext *cxt, int),
393 int threads, int iterations,
394 int operations,
395 void (*invariant)(void *)) {
396 absl::EnableMutexInvariantDebugging(true);
397 SetInvariantChecked(false);
398 TestContext cxt;
399 cxt.mu.EnableInvariantDebugging(invariant, &cxt);
400 int ret = RunTestCommon(&cxt, test, threads, iterations, operations);
401 ABSL_RAW_CHECK(GetInvariantChecked(), "Invariant not checked");
402 absl::EnableMutexInvariantDebugging(false); // Restore.
403 return ret;
404 }
405 #endif
406
407 // --------------------------------------------------------
408 // Test for fix of bug in TryRemove()
409 struct TimeoutBugStruct {
410 absl::Mutex mu;
411 bool a;
412 int a_waiter_count;
413 };
414
WaitForA(TimeoutBugStruct * x)415 static void WaitForA(TimeoutBugStruct *x) {
416 x->mu.LockWhen(absl::Condition(&x->a));
417 x->a_waiter_count--;
418 x->mu.Unlock();
419 }
420
NoAWaiters(TimeoutBugStruct * x)421 static bool NoAWaiters(TimeoutBugStruct *x) { return x->a_waiter_count == 0; }
422
423 // Test that a CondVar.Wait(&mutex) can un-block a call to mutex.Await() in
424 // another thread.
TEST(Mutex,CondVarWaitSignalsAwait)425 TEST(Mutex, CondVarWaitSignalsAwait) {
426 // Use a struct so the lock annotations apply.
427 struct {
428 absl::Mutex barrier_mu;
429 bool barrier ABSL_GUARDED_BY(barrier_mu) = false;
430
431 absl::Mutex release_mu;
432 bool release ABSL_GUARDED_BY(release_mu) = false;
433 absl::CondVar released_cv;
434 } state;
435
436 auto pool = CreateDefaultPool();
437
438 // Thread A. Sets barrier, waits for release using Mutex::Await, then
439 // signals released_cv.
440 pool->Schedule([&state] {
441 state.release_mu.Lock();
442
443 state.barrier_mu.Lock();
444 state.barrier = true;
445 state.barrier_mu.Unlock();
446
447 state.release_mu.Await(absl::Condition(&state.release));
448 state.released_cv.Signal();
449 state.release_mu.Unlock();
450 });
451
452 state.barrier_mu.LockWhen(absl::Condition(&state.barrier));
453 state.barrier_mu.Unlock();
454 state.release_mu.Lock();
455 // Thread A is now blocked on release by way of Mutex::Await().
456
457 // Set release. Calling released_cv.Wait() should un-block thread A,
458 // which will signal released_cv. If not, the test will hang.
459 state.release = true;
460 state.released_cv.Wait(&state.release_mu);
461 state.release_mu.Unlock();
462 }
463
464 // Test that a CondVar.WaitWithTimeout(&mutex) can un-block a call to
465 // mutex.Await() in another thread.
TEST(Mutex,CondVarWaitWithTimeoutSignalsAwait)466 TEST(Mutex, CondVarWaitWithTimeoutSignalsAwait) {
467 // Use a struct so the lock annotations apply.
468 struct {
469 absl::Mutex barrier_mu;
470 bool barrier ABSL_GUARDED_BY(barrier_mu) = false;
471
472 absl::Mutex release_mu;
473 bool release ABSL_GUARDED_BY(release_mu) = false;
474 absl::CondVar released_cv;
475 } state;
476
477 auto pool = CreateDefaultPool();
478
479 // Thread A. Sets barrier, waits for release using Mutex::Await, then
480 // signals released_cv.
481 pool->Schedule([&state] {
482 state.release_mu.Lock();
483
484 state.barrier_mu.Lock();
485 state.barrier = true;
486 state.barrier_mu.Unlock();
487
488 state.release_mu.Await(absl::Condition(&state.release));
489 state.released_cv.Signal();
490 state.release_mu.Unlock();
491 });
492
493 state.barrier_mu.LockWhen(absl::Condition(&state.barrier));
494 state.barrier_mu.Unlock();
495 state.release_mu.Lock();
496 // Thread A is now blocked on release by way of Mutex::Await().
497
498 // Set release. Calling released_cv.Wait() should un-block thread A,
499 // which will signal released_cv. If not, the test will hang.
500 state.release = true;
501 EXPECT_TRUE(
502 !state.released_cv.WaitWithTimeout(&state.release_mu, absl::Seconds(10)))
503 << "; Unrecoverable test failure: CondVar::WaitWithTimeout did not "
504 "unblock the absl::Mutex::Await call in another thread.";
505
506 state.release_mu.Unlock();
507 }
508
509 // Test for regression of a bug in loop of TryRemove()
TEST(Mutex,MutexTimeoutBug)510 TEST(Mutex, MutexTimeoutBug) {
511 auto tp = CreateDefaultPool();
512
513 TimeoutBugStruct x;
514 x.a = false;
515 x.a_waiter_count = 2;
516 tp->Schedule(std::bind(&WaitForA, &x));
517 tp->Schedule(std::bind(&WaitForA, &x));
518 absl::SleepFor(absl::Seconds(1)); // Allow first two threads to hang.
519 // The skip field of the second will point to the first because there are
520 // only two.
521
522 // Now cause a thread waiting on an always-false to time out
523 // This would deadlock when the bug was present.
524 bool always_false = false;
525 x.mu.LockWhenWithTimeout(absl::Condition(&always_false),
526 absl::Milliseconds(500));
527
528 // if we get here, the bug is not present. Cleanup the state.
529
530 x.a = true; // wakeup the two waiters on A
531 x.mu.Await(absl::Condition(&NoAWaiters, &x)); // wait for them to exit
532 x.mu.Unlock();
533 }
534
535 struct CondVarWaitDeadlock : testing::TestWithParam<int> {
536 absl::Mutex mu;
537 absl::CondVar cv;
538 bool cond1 = false;
539 bool cond2 = false;
540 bool read_lock1;
541 bool read_lock2;
542 bool signal_unlocked;
543
CondVarWaitDeadlock__anon0e5fde650111::CondVarWaitDeadlock544 CondVarWaitDeadlock() {
545 read_lock1 = GetParam() & (1 << 0);
546 read_lock2 = GetParam() & (1 << 1);
547 signal_unlocked = GetParam() & (1 << 2);
548 }
549
Waiter1__anon0e5fde650111::CondVarWaitDeadlock550 void Waiter1() {
551 if (read_lock1) {
552 mu.ReaderLock();
553 while (!cond1) {
554 cv.Wait(&mu);
555 }
556 mu.ReaderUnlock();
557 } else {
558 mu.Lock();
559 while (!cond1) {
560 cv.Wait(&mu);
561 }
562 mu.Unlock();
563 }
564 }
565
Waiter2__anon0e5fde650111::CondVarWaitDeadlock566 void Waiter2() {
567 if (read_lock2) {
568 mu.ReaderLockWhen(absl::Condition(&cond2));
569 mu.ReaderUnlock();
570 } else {
571 mu.LockWhen(absl::Condition(&cond2));
572 mu.Unlock();
573 }
574 }
575 };
576
577 // Test for a deadlock bug in Mutex::Fer().
578 // The sequence of events that lead to the deadlock is:
579 // 1. waiter1 blocks on cv in read mode (mu bits = 0).
580 // 2. waiter2 blocks on mu in either mode (mu bits = kMuWait).
581 // 3. main thread locks mu, sets cond1, unlocks mu (mu bits = kMuWait).
582 // 4. main thread signals on cv and this eventually calls Mutex::Fer().
583 // Currently Fer wakes waiter1 since mu bits = kMuWait (mutex is unlocked).
584 // Before the bug fix Fer neither woke waiter1 nor queued it on mutex,
585 // which resulted in deadlock.
TEST_P(CondVarWaitDeadlock,Test)586 TEST_P(CondVarWaitDeadlock, Test) {
587 auto waiter1 = CreatePool(1);
588 auto waiter2 = CreatePool(1);
589 waiter1->Schedule([this] { this->Waiter1(); });
590 waiter2->Schedule([this] { this->Waiter2(); });
591
592 // Wait while threads block (best-effort is fine).
593 absl::SleepFor(absl::Milliseconds(100));
594
595 // Wake condwaiter.
596 mu.Lock();
597 cond1 = true;
598 if (signal_unlocked) {
599 mu.Unlock();
600 cv.Signal();
601 } else {
602 cv.Signal();
603 mu.Unlock();
604 }
605 waiter1.reset(); // "join" waiter1
606
607 // Wake waiter.
608 mu.Lock();
609 cond2 = true;
610 mu.Unlock();
611 waiter2.reset(); // "join" waiter2
612 }
613
614 INSTANTIATE_TEST_SUITE_P(CondVarWaitDeadlockTest, CondVarWaitDeadlock,
615 ::testing::Range(0, 8),
616 ::testing::PrintToStringParamName());
617
618 // --------------------------------------------------------
619 // Test for fix of bug in DequeueAllWakeable()
620 // Bug was that if there was more than one waiting reader
621 // and all should be woken, the most recently blocked one
622 // would not be.
623
624 struct DequeueAllWakeableBugStruct {
625 absl::Mutex mu;
626 absl::Mutex mu2; // protects all fields below
627 int unfinished_count; // count of unfinished readers; under mu2
628 bool done1; // unfinished_count == 0; under mu2
629 int finished_count; // count of finished readers, under mu2
630 bool done2; // finished_count == 0; under mu2
631 };
632
633 // Test for regression of a bug in loop of DequeueAllWakeable()
AcquireAsReader(DequeueAllWakeableBugStruct * x)634 static void AcquireAsReader(DequeueAllWakeableBugStruct *x) {
635 x->mu.ReaderLock();
636 x->mu2.Lock();
637 x->unfinished_count--;
638 x->done1 = (x->unfinished_count == 0);
639 x->mu2.Unlock();
640 // make sure that both readers acquired mu before we release it.
641 absl::SleepFor(absl::Seconds(2));
642 x->mu.ReaderUnlock();
643
644 x->mu2.Lock();
645 x->finished_count--;
646 x->done2 = (x->finished_count == 0);
647 x->mu2.Unlock();
648 }
649
650 // Test for regression of a bug in loop of DequeueAllWakeable()
TEST(Mutex,MutexReaderWakeupBug)651 TEST(Mutex, MutexReaderWakeupBug) {
652 auto tp = CreateDefaultPool();
653
654 DequeueAllWakeableBugStruct x;
655 x.unfinished_count = 2;
656 x.done1 = false;
657 x.finished_count = 2;
658 x.done2 = false;
659 x.mu.Lock(); // acquire mu exclusively
660 // queue two thread that will block on reader locks on x.mu
661 tp->Schedule(std::bind(&AcquireAsReader, &x));
662 tp->Schedule(std::bind(&AcquireAsReader, &x));
663 absl::SleepFor(absl::Seconds(1)); // give time for reader threads to block
664 x.mu.Unlock(); // wake them up
665
666 // both readers should finish promptly
667 EXPECT_TRUE(
668 x.mu2.LockWhenWithTimeout(absl::Condition(&x.done1), absl::Seconds(10)));
669 x.mu2.Unlock();
670
671 EXPECT_TRUE(
672 x.mu2.LockWhenWithTimeout(absl::Condition(&x.done2), absl::Seconds(10)));
673 x.mu2.Unlock();
674 }
675
676 struct LockWhenTestStruct {
677 absl::Mutex mu1;
678 bool cond = false;
679
680 absl::Mutex mu2;
681 bool waiting = false;
682 };
683
LockWhenTestIsCond(LockWhenTestStruct * s)684 static bool LockWhenTestIsCond(LockWhenTestStruct* s) {
685 s->mu2.Lock();
686 s->waiting = true;
687 s->mu2.Unlock();
688 return s->cond;
689 }
690
LockWhenTestWaitForIsCond(LockWhenTestStruct * s)691 static void LockWhenTestWaitForIsCond(LockWhenTestStruct* s) {
692 s->mu1.LockWhen(absl::Condition(&LockWhenTestIsCond, s));
693 s->mu1.Unlock();
694 }
695
TEST(Mutex,LockWhen)696 TEST(Mutex, LockWhen) {
697 LockWhenTestStruct s;
698
699 std::thread t(LockWhenTestWaitForIsCond, &s);
700 s.mu2.LockWhen(absl::Condition(&s.waiting));
701 s.mu2.Unlock();
702
703 s.mu1.Lock();
704 s.cond = true;
705 s.mu1.Unlock();
706
707 t.join();
708 }
709
710 // --------------------------------------------------------
711 // The following test requires Mutex::ReaderLock to be a real shared
712 // lock, which is not the case in all builds.
713 #if !defined(ABSL_MUTEX_READER_LOCK_IS_EXCLUSIVE)
714
715 // Test for fix of bug in UnlockSlow() that incorrectly decremented the reader
716 // count when putting a thread to sleep waiting for a false condition when the
717 // lock was not held.
718
719 // For this bug to strike, we make a thread wait on a free mutex with no
720 // waiters by causing its wakeup condition to be false. Then the
721 // next two acquirers must be readers. The bug causes the lock
722 // to be released when one reader unlocks, rather than both.
723
724 struct ReaderDecrementBugStruct {
725 bool cond; // to delay first thread (under mu)
726 int done; // reference count (under mu)
727 absl::Mutex mu;
728
729 bool waiting_on_cond; // under mu2
730 bool have_reader_lock; // under mu2
731 bool complete; // under mu2
732 absl::Mutex mu2; // > mu
733 };
734
735 // L >= mu, L < mu_waiting_on_cond
IsCond(void * v)736 static bool IsCond(void *v) {
737 ReaderDecrementBugStruct *x = reinterpret_cast<ReaderDecrementBugStruct *>(v);
738 x->mu2.Lock();
739 x->waiting_on_cond = true;
740 x->mu2.Unlock();
741 return x->cond;
742 }
743
744 // L >= mu
AllDone(void * v)745 static bool AllDone(void *v) {
746 ReaderDecrementBugStruct *x = reinterpret_cast<ReaderDecrementBugStruct *>(v);
747 return x->done == 0;
748 }
749
750 // L={}
WaitForCond(ReaderDecrementBugStruct * x)751 static void WaitForCond(ReaderDecrementBugStruct *x) {
752 absl::Mutex dummy;
753 absl::MutexLock l(&dummy);
754 x->mu.LockWhen(absl::Condition(&IsCond, x));
755 x->done--;
756 x->mu.Unlock();
757 }
758
759 // L={}
GetReadLock(ReaderDecrementBugStruct * x)760 static void GetReadLock(ReaderDecrementBugStruct *x) {
761 x->mu.ReaderLock();
762 x->mu2.Lock();
763 x->have_reader_lock = true;
764 x->mu2.Await(absl::Condition(&x->complete));
765 x->mu2.Unlock();
766 x->mu.ReaderUnlock();
767 x->mu.Lock();
768 x->done--;
769 x->mu.Unlock();
770 }
771
772 // Test for reader counter being decremented incorrectly by waiter
773 // with false condition.
TEST(Mutex,MutexReaderDecrementBug)774 TEST(Mutex, MutexReaderDecrementBug) ABSL_NO_THREAD_SAFETY_ANALYSIS {
775 ReaderDecrementBugStruct x;
776 x.cond = false;
777 x.waiting_on_cond = false;
778 x.have_reader_lock = false;
779 x.complete = false;
780 x.done = 2; // initial ref count
781
782 // Run WaitForCond() and wait for it to sleep
783 std::thread thread1(WaitForCond, &x);
784 x.mu2.LockWhen(absl::Condition(&x.waiting_on_cond));
785 x.mu2.Unlock();
786
787 // Run GetReadLock(), and wait for it to get the read lock
788 std::thread thread2(GetReadLock, &x);
789 x.mu2.LockWhen(absl::Condition(&x.have_reader_lock));
790 x.mu2.Unlock();
791
792 // Get the reader lock ourselves, and release it.
793 x.mu.ReaderLock();
794 x.mu.ReaderUnlock();
795
796 // The lock should be held in read mode by GetReadLock().
797 // If we have the bug, the lock will be free.
798 x.mu.AssertReaderHeld();
799
800 // Wake up all the threads.
801 x.mu2.Lock();
802 x.complete = true;
803 x.mu2.Unlock();
804
805 // TODO(delesley): turn on analysis once lock upgrading is supported.
806 // (This call upgrades the lock from shared to exclusive.)
807 x.mu.Lock();
808 x.cond = true;
809 x.mu.Await(absl::Condition(&AllDone, &x));
810 x.mu.Unlock();
811
812 thread1.join();
813 thread2.join();
814 }
815 #endif // !ABSL_MUTEX_READER_LOCK_IS_EXCLUSIVE
816
817 // Test that we correctly handle the situation when a lock is
818 // held and then destroyed (w/o unlocking).
819 #ifdef ABSL_HAVE_THREAD_SANITIZER
820 // TSAN reports errors when locked Mutexes are destroyed.
TEST(Mutex,DISABLED_LockedMutexDestructionBug)821 TEST(Mutex, DISABLED_LockedMutexDestructionBug) NO_THREAD_SAFETY_ANALYSIS {
822 #else
823 TEST(Mutex, LockedMutexDestructionBug) ABSL_NO_THREAD_SAFETY_ANALYSIS {
824 #endif
825 for (int i = 0; i != 10; i++) {
826 // Create, lock and destroy 10 locks.
827 const int kNumLocks = 10;
828 auto mu = absl::make_unique<absl::Mutex[]>(kNumLocks);
829 for (int j = 0; j != kNumLocks; j++) {
830 if ((j % 2) == 0) {
831 mu[j].WriterLock();
832 } else {
833 mu[j].ReaderLock();
834 }
835 }
836 }
837 }
838
839 // --------------------------------------------------------
840 // Test for bug with pattern of readers using a condvar. The bug was that if a
841 // reader went to sleep on a condition variable while one or more other readers
842 // held the lock, but there were no waiters, the reader count (held in the
843 // mutex word) would be lost. (This is because Enqueue() had at one time
844 // always placed the thread on the Mutex queue. Later (CL 4075610), to
845 // tolerate re-entry into Mutex from a Condition predicate, Enqueue() was
846 // changed so that it could also place a thread on a condition-variable. This
847 // introduced the case where Enqueue() returned with an empty queue, and this
848 // case was handled incorrectly in one place.)
849
850 static void ReaderForReaderOnCondVar(absl::Mutex *mu, absl::CondVar *cv,
851 int *running) {
852 std::random_device dev;
853 std::mt19937 gen(dev());
854 std::uniform_int_distribution<int> random_millis(0, 15);
855 mu->ReaderLock();
856 while (*running == 3) {
857 absl::SleepFor(absl::Milliseconds(random_millis(gen)));
858 cv->WaitWithTimeout(mu, absl::Milliseconds(random_millis(gen)));
859 }
860 mu->ReaderUnlock();
861 mu->Lock();
862 (*running)--;
863 mu->Unlock();
864 }
865
866 struct True {
867 template <class... Args>
868 bool operator()(Args...) const {
869 return true;
870 }
871 };
872
873 struct DerivedTrue : True {};
874
875 TEST(Mutex, FunctorCondition) {
876 { // Variadic
877 True f;
878 EXPECT_TRUE(absl::Condition(&f).Eval());
879 }
880
881 { // Inherited
882 DerivedTrue g;
883 EXPECT_TRUE(absl::Condition(&g).Eval());
884 }
885
886 { // lambda
887 int value = 3;
888 auto is_zero = [&value] { return value == 0; };
889 absl::Condition c(&is_zero);
890 EXPECT_FALSE(c.Eval());
891 value = 0;
892 EXPECT_TRUE(c.Eval());
893 }
894
895 { // bind
896 int value = 0;
897 auto is_positive = std::bind(std::less<int>(), 0, std::cref(value));
898 absl::Condition c(&is_positive);
899 EXPECT_FALSE(c.Eval());
900 value = 1;
901 EXPECT_TRUE(c.Eval());
902 }
903
904 { // std::function
905 int value = 3;
906 std::function<bool()> is_zero = [&value] { return value == 0; };
907 absl::Condition c(&is_zero);
908 EXPECT_FALSE(c.Eval());
909 value = 0;
910 EXPECT_TRUE(c.Eval());
911 }
912 }
913
914 static bool IntIsZero(int *x) { return *x == 0; }
915
916 // Test for reader waiting condition variable when there are other readers
917 // but no waiters.
918 TEST(Mutex, TestReaderOnCondVar) {
919 auto tp = CreateDefaultPool();
920 absl::Mutex mu;
921 absl::CondVar cv;
922 int running = 3;
923 tp->Schedule(std::bind(&ReaderForReaderOnCondVar, &mu, &cv, &running));
924 tp->Schedule(std::bind(&ReaderForReaderOnCondVar, &mu, &cv, &running));
925 absl::SleepFor(absl::Seconds(2));
926 mu.Lock();
927 running--;
928 mu.Await(absl::Condition(&IntIsZero, &running));
929 mu.Unlock();
930 }
931
932 // --------------------------------------------------------
933 struct AcquireFromConditionStruct {
934 absl::Mutex mu0; // protects value, done
935 int value; // times condition function is called; under mu0,
936 bool done; // done with test? under mu0
937 absl::Mutex mu1; // used to attempt to mess up state of mu0
938 absl::CondVar cv; // so the condition function can be invoked from
939 // CondVar::Wait().
940 };
941
942 static bool ConditionWithAcquire(AcquireFromConditionStruct *x) {
943 x->value++; // count times this function is called
944
945 if (x->value == 2 || x->value == 3) {
946 // On the second and third invocation of this function, sleep for 100ms,
947 // but with the side-effect of altering the state of a Mutex other than
948 // than one for which this is a condition. The spec now explicitly allows
949 // this side effect; previously it did not. it was illegal.
950 bool always_false = false;
951 x->mu1.LockWhenWithTimeout(absl::Condition(&always_false),
952 absl::Milliseconds(100));
953 x->mu1.Unlock();
954 }
955 ABSL_RAW_CHECK(x->value < 4, "should not be invoked a fourth time");
956
957 // We arrange for the condition to return true on only the 2nd and 3rd calls.
958 return x->value == 2 || x->value == 3;
959 }
960
961 static void WaitForCond2(AcquireFromConditionStruct *x) {
962 // wait for cond0 to become true
963 x->mu0.LockWhen(absl::Condition(&ConditionWithAcquire, x));
964 x->done = true;
965 x->mu0.Unlock();
966 }
967
968 // Test for Condition whose function acquires other Mutexes
969 TEST(Mutex, AcquireFromCondition) {
970 auto tp = CreateDefaultPool();
971
972 AcquireFromConditionStruct x;
973 x.value = 0;
974 x.done = false;
975 tp->Schedule(
976 std::bind(&WaitForCond2, &x)); // run WaitForCond2() in a thread T
977 // T will hang because the first invocation of ConditionWithAcquire() will
978 // return false.
979 absl::SleepFor(absl::Milliseconds(500)); // allow T time to hang
980
981 x.mu0.Lock();
982 x.cv.WaitWithTimeout(&x.mu0, absl::Milliseconds(500)); // wake T
983 // T will be woken because the Wait() will call ConditionWithAcquire()
984 // for the second time, and it will return true.
985
986 x.mu0.Unlock();
987
988 // T will then acquire the lock and recheck its own condition.
989 // It will find the condition true, as this is the third invocation,
990 // but the use of another Mutex by the calling function will
991 // cause the old mutex implementation to think that the outer
992 // LockWhen() has timed out because the inner LockWhenWithTimeout() did.
993 // T will then check the condition a fourth time because it finds a
994 // timeout occurred. This should not happen in the new
995 // implementation that allows the Condition function to use Mutexes.
996
997 // It should also succeed, even though the Condition function
998 // is being invoked from CondVar::Wait, and thus this thread
999 // is conceptually waiting both on the condition variable, and on mu2.
1000
1001 x.mu0.LockWhen(absl::Condition(&x.done));
1002 x.mu0.Unlock();
1003 }
1004
1005 // The deadlock detector is not part of non-prod builds, so do not test it.
1006 #if !defined(ABSL_INTERNAL_USE_NONPROD_MUTEX)
1007
1008 TEST(Mutex, DeadlockDetector) {
1009 absl::SetMutexDeadlockDetectionMode(absl::OnDeadlockCycle::kAbort);
1010
1011 // check that we can call ForgetDeadlockInfo() on a lock with the lock held
1012 absl::Mutex m1;
1013 absl::Mutex m2;
1014 absl::Mutex m3;
1015 absl::Mutex m4;
1016
1017 m1.Lock(); // m1 gets ID1
1018 m2.Lock(); // m2 gets ID2
1019 m3.Lock(); // m3 gets ID3
1020 m3.Unlock();
1021 m2.Unlock();
1022 // m1 still held
1023 m1.ForgetDeadlockInfo(); // m1 loses ID
1024 m2.Lock(); // m2 gets ID2
1025 m3.Lock(); // m3 gets ID3
1026 m4.Lock(); // m4 gets ID4
1027 m3.Unlock();
1028 m2.Unlock();
1029 m4.Unlock();
1030 m1.Unlock();
1031 }
1032
1033 // Bazel has a test "warning" file that programs can write to if the
1034 // test should pass with a warning. This class disables the warning
1035 // file until it goes out of scope.
1036 class ScopedDisableBazelTestWarnings {
1037 public:
1038 ScopedDisableBazelTestWarnings() {
1039 #ifdef _WIN32
1040 char file[MAX_PATH];
1041 if (GetEnvironmentVariableA(kVarName, file, sizeof(file)) < sizeof(file)) {
1042 warnings_output_file_ = file;
1043 SetEnvironmentVariableA(kVarName, nullptr);
1044 }
1045 #else
1046 const char *file = getenv(kVarName);
1047 if (file != nullptr) {
1048 warnings_output_file_ = file;
1049 unsetenv(kVarName);
1050 }
1051 #endif
1052 }
1053
1054 ~ScopedDisableBazelTestWarnings() {
1055 if (!warnings_output_file_.empty()) {
1056 #ifdef _WIN32
1057 SetEnvironmentVariableA(kVarName, warnings_output_file_.c_str());
1058 #else
1059 setenv(kVarName, warnings_output_file_.c_str(), 0);
1060 #endif
1061 }
1062 }
1063
1064 private:
1065 static const char kVarName[];
1066 std::string warnings_output_file_;
1067 };
1068 const char ScopedDisableBazelTestWarnings::kVarName[] =
1069 "TEST_WARNINGS_OUTPUT_FILE";
1070
1071 #ifdef ABSL_HAVE_THREAD_SANITIZER
1072 // This test intentionally creates deadlocks to test the deadlock detector.
1073 TEST(Mutex, DISABLED_DeadlockDetectorBazelWarning) {
1074 #else
1075 TEST(Mutex, DeadlockDetectorBazelWarning) {
1076 #endif
1077 absl::SetMutexDeadlockDetectionMode(absl::OnDeadlockCycle::kReport);
1078
1079 // Cause deadlock detection to detect something, if it's
1080 // compiled in and enabled. But turn off the bazel warning.
1081 ScopedDisableBazelTestWarnings disable_bazel_test_warnings;
1082
1083 absl::Mutex mu0;
1084 absl::Mutex mu1;
1085 bool got_mu0 = mu0.TryLock();
1086 mu1.Lock(); // acquire mu1 while holding mu0
1087 if (got_mu0) {
1088 mu0.Unlock();
1089 }
1090 if (mu0.TryLock()) { // try lock shouldn't cause deadlock detector to fire
1091 mu0.Unlock();
1092 }
1093 mu0.Lock(); // acquire mu0 while holding mu1; should get one deadlock
1094 // report here
1095 mu0.Unlock();
1096 mu1.Unlock();
1097
1098 absl::SetMutexDeadlockDetectionMode(absl::OnDeadlockCycle::kAbort);
1099 }
1100
1101 // This test is tagged with NO_THREAD_SAFETY_ANALYSIS because the
1102 // annotation-based static thread-safety analysis is not currently
1103 // predicate-aware and cannot tell if the two for-loops that acquire and
1104 // release the locks have the same predicates.
1105 TEST(Mutex, DeadlockDetectorStessTest) ABSL_NO_THREAD_SAFETY_ANALYSIS {
1106 // Stress test: Here we create a large number of locks and use all of them.
1107 // If a deadlock detector keeps a full graph of lock acquisition order,
1108 // it will likely be too slow for this test to pass.
1109 const int n_locks = 1 << 17;
1110 auto array_of_locks = absl::make_unique<absl::Mutex[]>(n_locks);
1111 for (int i = 0; i < n_locks; i++) {
1112 int end = std::min(n_locks, i + 5);
1113 // acquire and then release locks i, i+1, ..., i+4
1114 for (int j = i; j < end; j++) {
1115 array_of_locks[j].Lock();
1116 }
1117 for (int j = i; j < end; j++) {
1118 array_of_locks[j].Unlock();
1119 }
1120 }
1121 }
1122
1123 #ifdef ABSL_HAVE_THREAD_SANITIZER
1124 // TSAN reports errors when locked Mutexes are destroyed.
1125 TEST(Mutex, DISABLED_DeadlockIdBug) NO_THREAD_SAFETY_ANALYSIS {
1126 #else
1127 TEST(Mutex, DeadlockIdBug) ABSL_NO_THREAD_SAFETY_ANALYSIS {
1128 #endif
1129 // Test a scenario where a cached deadlock graph node id in the
1130 // list of held locks is not invalidated when the corresponding
1131 // mutex is deleted.
1132 absl::SetMutexDeadlockDetectionMode(absl::OnDeadlockCycle::kAbort);
1133 // Mutex that will be destroyed while being held
1134 absl::Mutex *a = new absl::Mutex;
1135 // Other mutexes needed by test
1136 absl::Mutex b, c;
1137
1138 // Hold mutex.
1139 a->Lock();
1140
1141 // Force deadlock id assignment by acquiring another lock.
1142 b.Lock();
1143 b.Unlock();
1144
1145 // Delete the mutex. The Mutex destructor tries to remove held locks,
1146 // but the attempt isn't foolproof. It can fail if:
1147 // (a) Deadlock detection is currently disabled.
1148 // (b) The destruction is from another thread.
1149 // We exploit (a) by temporarily disabling deadlock detection.
1150 absl::SetMutexDeadlockDetectionMode(absl::OnDeadlockCycle::kIgnore);
1151 delete a;
1152 absl::SetMutexDeadlockDetectionMode(absl::OnDeadlockCycle::kAbort);
1153
1154 // Now acquire another lock which will force a deadlock id assignment.
1155 // We should end up getting assigned the same deadlock id that was
1156 // freed up when "a" was deleted, which will cause a spurious deadlock
1157 // report if the held lock entry for "a" was not invalidated.
1158 c.Lock();
1159 c.Unlock();
1160 }
1161 #endif // !defined(ABSL_INTERNAL_USE_NONPROD_MUTEX)
1162
1163 // --------------------------------------------------------
1164 // Test for timeouts/deadlines on condition waits that are specified using
1165 // absl::Duration and absl::Time. For each waiting function we test with
1166 // a timeout/deadline that has already expired/passed, one that is infinite
1167 // and so never expires/passes, and one that will expire/pass in the near
1168 // future.
1169
1170 static absl::Duration TimeoutTestAllowedSchedulingDelay() {
1171 // Note: we use a function here because Microsoft Visual Studio fails to
1172 // properly initialize constexpr static absl::Duration variables.
1173 return absl::Milliseconds(150);
1174 }
1175
1176 // Returns true if `actual_delay` is close enough to `expected_delay` to pass
1177 // the timeouts/deadlines test. Otherwise, logs warnings and returns false.
1178 ABSL_MUST_USE_RESULT
1179 static bool DelayIsWithinBounds(absl::Duration expected_delay,
1180 absl::Duration actual_delay) {
1181 bool pass = true;
1182 // Do not allow the observed delay to be less than expected. This may occur
1183 // in practice due to clock skew or when the synchronization primitives use a
1184 // different clock than absl::Now(), but these cases should be handled by the
1185 // the retry mechanism in each TimeoutTest.
1186 if (actual_delay < expected_delay) {
1187 ABSL_RAW_LOG(WARNING,
1188 "Actual delay %s was too short, expected %s (difference %s)",
1189 absl::FormatDuration(actual_delay).c_str(),
1190 absl::FormatDuration(expected_delay).c_str(),
1191 absl::FormatDuration(actual_delay - expected_delay).c_str());
1192 pass = false;
1193 }
1194 // If the expected delay is <= zero then allow a small error tolerance, since
1195 // we do not expect context switches to occur during test execution.
1196 // Otherwise, thread scheduling delays may be substantial in rare cases, so
1197 // tolerate up to kTimeoutTestAllowedSchedulingDelay of error.
1198 absl::Duration tolerance = expected_delay <= absl::ZeroDuration()
1199 ? absl::Milliseconds(10)
1200 : TimeoutTestAllowedSchedulingDelay();
1201 if (actual_delay > expected_delay + tolerance) {
1202 ABSL_RAW_LOG(WARNING,
1203 "Actual delay %s was too long, expected %s (difference %s)",
1204 absl::FormatDuration(actual_delay).c_str(),
1205 absl::FormatDuration(expected_delay).c_str(),
1206 absl::FormatDuration(actual_delay - expected_delay).c_str());
1207 pass = false;
1208 }
1209 return pass;
1210 }
1211
1212 // Parameters for TimeoutTest, below.
1213 struct TimeoutTestParam {
1214 // The file and line number (used for logging purposes only).
1215 const char *from_file;
1216 int from_line;
1217
1218 // Should the absolute deadline API based on absl::Time be tested? If false,
1219 // the relative deadline API based on absl::Duration is tested.
1220 bool use_absolute_deadline;
1221
1222 // The deadline/timeout used when calling the API being tested
1223 // (e.g. Mutex::LockWhenWithDeadline).
1224 absl::Duration wait_timeout;
1225
1226 // The delay before the condition will be set true by the test code. If zero
1227 // or negative, the condition is set true immediately (before calling the API
1228 // being tested). Otherwise, if infinite, the condition is never set true.
1229 // Otherwise a closure is scheduled for the future that sets the condition
1230 // true.
1231 absl::Duration satisfy_condition_delay;
1232
1233 // The expected result of the condition after the call to the API being
1234 // tested. Generally `true` means the condition was true when the API returns,
1235 // `false` indicates an expected timeout.
1236 bool expected_result;
1237
1238 // The expected delay before the API under test returns. This is inherently
1239 // flaky, so some slop is allowed (see `DelayIsWithinBounds` above), and the
1240 // test keeps trying indefinitely until this constraint passes.
1241 absl::Duration expected_delay;
1242 };
1243
1244 // Print a `TimeoutTestParam` to a debug log.
1245 std::ostream &operator<<(std::ostream &os, const TimeoutTestParam ¶m) {
1246 return os << "from: " << param.from_file << ":" << param.from_line
1247 << " use_absolute_deadline: "
1248 << (param.use_absolute_deadline ? "true" : "false")
1249 << " wait_timeout: " << param.wait_timeout
1250 << " satisfy_condition_delay: " << param.satisfy_condition_delay
1251 << " expected_result: "
1252 << (param.expected_result ? "true" : "false")
1253 << " expected_delay: " << param.expected_delay;
1254 }
1255
1256 std::string FormatString(const TimeoutTestParam ¶m) {
1257 std::ostringstream os;
1258 os << param;
1259 return os.str();
1260 }
1261
1262 // Like `thread::Executor::ScheduleAt` except:
1263 // a) Delays zero or negative are executed immediately in the current thread.
1264 // b) Infinite delays are never scheduled.
1265 // c) Calls this test's `ScheduleAt` helper instead of using `pool` directly.
1266 static void RunAfterDelay(absl::Duration delay,
1267 absl::synchronization_internal::ThreadPool *pool,
1268 const std::function<void()> &callback) {
1269 if (delay <= absl::ZeroDuration()) {
1270 callback(); // immediate
1271 } else if (delay != absl::InfiniteDuration()) {
1272 ScheduleAfter(pool, delay, callback);
1273 }
1274 }
1275
1276 class TimeoutTest : public ::testing::Test,
1277 public ::testing::WithParamInterface<TimeoutTestParam> {};
1278
1279 std::vector<TimeoutTestParam> MakeTimeoutTestParamValues() {
1280 // The `finite` delay is a finite, relatively short, delay. We make it larger
1281 // than our allowed scheduling delay (slop factor) to avoid confusion when
1282 // diagnosing test failures. The other constants here have clear meanings.
1283 const absl::Duration finite = 3 * TimeoutTestAllowedSchedulingDelay();
1284 const absl::Duration never = absl::InfiniteDuration();
1285 const absl::Duration negative = -absl::InfiniteDuration();
1286 const absl::Duration immediate = absl::ZeroDuration();
1287
1288 // Every test case is run twice; once using the absolute deadline API and once
1289 // using the relative timeout API.
1290 std::vector<TimeoutTestParam> values;
1291 for (bool use_absolute_deadline : {false, true}) {
1292 // Tests with a negative timeout (deadline in the past), which should
1293 // immediately return current state of the condition.
1294
1295 // The condition is already true:
1296 values.push_back(TimeoutTestParam{
1297 __FILE__, __LINE__, use_absolute_deadline,
1298 negative, // wait_timeout
1299 immediate, // satisfy_condition_delay
1300 true, // expected_result
1301 immediate, // expected_delay
1302 });
1303
1304 // The condition becomes true, but the timeout has already expired:
1305 values.push_back(TimeoutTestParam{
1306 __FILE__, __LINE__, use_absolute_deadline,
1307 negative, // wait_timeout
1308 finite, // satisfy_condition_delay
1309 false, // expected_result
1310 immediate // expected_delay
1311 });
1312
1313 // The condition never becomes true:
1314 values.push_back(TimeoutTestParam{
1315 __FILE__, __LINE__, use_absolute_deadline,
1316 negative, // wait_timeout
1317 never, // satisfy_condition_delay
1318 false, // expected_result
1319 immediate // expected_delay
1320 });
1321
1322 // Tests with an infinite timeout (deadline in the infinite future), which
1323 // should only return when the condition becomes true.
1324
1325 // The condition is already true:
1326 values.push_back(TimeoutTestParam{
1327 __FILE__, __LINE__, use_absolute_deadline,
1328 never, // wait_timeout
1329 immediate, // satisfy_condition_delay
1330 true, // expected_result
1331 immediate // expected_delay
1332 });
1333
1334 // The condition becomes true before the (infinite) expiry:
1335 values.push_back(TimeoutTestParam{
1336 __FILE__, __LINE__, use_absolute_deadline,
1337 never, // wait_timeout
1338 finite, // satisfy_condition_delay
1339 true, // expected_result
1340 finite, // expected_delay
1341 });
1342
1343 // Tests with a (small) finite timeout (deadline soon), with the condition
1344 // becoming true both before and after its expiry.
1345
1346 // The condition is already true:
1347 values.push_back(TimeoutTestParam{
1348 __FILE__, __LINE__, use_absolute_deadline,
1349 never, // wait_timeout
1350 immediate, // satisfy_condition_delay
1351 true, // expected_result
1352 immediate // expected_delay
1353 });
1354
1355 // The condition becomes true before the expiry:
1356 values.push_back(TimeoutTestParam{
1357 __FILE__, __LINE__, use_absolute_deadline,
1358 finite * 2, // wait_timeout
1359 finite, // satisfy_condition_delay
1360 true, // expected_result
1361 finite // expected_delay
1362 });
1363
1364 // The condition becomes true, but the timeout has already expired:
1365 values.push_back(TimeoutTestParam{
1366 __FILE__, __LINE__, use_absolute_deadline,
1367 finite, // wait_timeout
1368 finite * 2, // satisfy_condition_delay
1369 false, // expected_result
1370 finite // expected_delay
1371 });
1372
1373 // The condition never becomes true:
1374 values.push_back(TimeoutTestParam{
1375 __FILE__, __LINE__, use_absolute_deadline,
1376 finite, // wait_timeout
1377 never, // satisfy_condition_delay
1378 false, // expected_result
1379 finite // expected_delay
1380 });
1381 }
1382 return values;
1383 }
1384
1385 // Instantiate `TimeoutTest` with `MakeTimeoutTestParamValues()`.
1386 INSTANTIATE_TEST_SUITE_P(All, TimeoutTest,
1387 testing::ValuesIn(MakeTimeoutTestParamValues()));
1388
1389 TEST_P(TimeoutTest, Await) {
1390 const TimeoutTestParam params = GetParam();
1391 ABSL_RAW_LOG(INFO, "Params: %s", FormatString(params).c_str());
1392
1393 // Because this test asserts bounds on scheduling delays it is flaky. To
1394 // compensate it loops forever until it passes. Failures express as test
1395 // timeouts, in which case the test log can be used to diagnose the issue.
1396 for (int attempt = 1;; ++attempt) {
1397 ABSL_RAW_LOG(INFO, "Attempt %d", attempt);
1398
1399 absl::Mutex mu;
1400 bool value = false; // condition value (under mu)
1401
1402 std::unique_ptr<absl::synchronization_internal::ThreadPool> pool =
1403 CreateDefaultPool();
1404 RunAfterDelay(params.satisfy_condition_delay, pool.get(), [&] {
1405 absl::MutexLock l(&mu);
1406 value = true;
1407 });
1408
1409 absl::MutexLock lock(&mu);
1410 absl::Time start_time = absl::Now();
1411 absl::Condition cond(&value);
1412 bool result =
1413 params.use_absolute_deadline
1414 ? mu.AwaitWithDeadline(cond, start_time + params.wait_timeout)
1415 : mu.AwaitWithTimeout(cond, params.wait_timeout);
1416 if (DelayIsWithinBounds(params.expected_delay, absl::Now() - start_time)) {
1417 EXPECT_EQ(params.expected_result, result);
1418 break;
1419 }
1420 }
1421 }
1422
1423 TEST_P(TimeoutTest, LockWhen) {
1424 const TimeoutTestParam params = GetParam();
1425 ABSL_RAW_LOG(INFO, "Params: %s", FormatString(params).c_str());
1426
1427 // Because this test asserts bounds on scheduling delays it is flaky. To
1428 // compensate it loops forever until it passes. Failures express as test
1429 // timeouts, in which case the test log can be used to diagnose the issue.
1430 for (int attempt = 1;; ++attempt) {
1431 ABSL_RAW_LOG(INFO, "Attempt %d", attempt);
1432
1433 absl::Mutex mu;
1434 bool value = false; // condition value (under mu)
1435
1436 std::unique_ptr<absl::synchronization_internal::ThreadPool> pool =
1437 CreateDefaultPool();
1438 RunAfterDelay(params.satisfy_condition_delay, pool.get(), [&] {
1439 absl::MutexLock l(&mu);
1440 value = true;
1441 });
1442
1443 absl::Time start_time = absl::Now();
1444 absl::Condition cond(&value);
1445 bool result =
1446 params.use_absolute_deadline
1447 ? mu.LockWhenWithDeadline(cond, start_time + params.wait_timeout)
1448 : mu.LockWhenWithTimeout(cond, params.wait_timeout);
1449 mu.Unlock();
1450
1451 if (DelayIsWithinBounds(params.expected_delay, absl::Now() - start_time)) {
1452 EXPECT_EQ(params.expected_result, result);
1453 break;
1454 }
1455 }
1456 }
1457
1458 TEST_P(TimeoutTest, ReaderLockWhen) {
1459 const TimeoutTestParam params = GetParam();
1460 ABSL_RAW_LOG(INFO, "Params: %s", FormatString(params).c_str());
1461
1462 // Because this test asserts bounds on scheduling delays it is flaky. To
1463 // compensate it loops forever until it passes. Failures express as test
1464 // timeouts, in which case the test log can be used to diagnose the issue.
1465 for (int attempt = 0;; ++attempt) {
1466 ABSL_RAW_LOG(INFO, "Attempt %d", attempt);
1467
1468 absl::Mutex mu;
1469 bool value = false; // condition value (under mu)
1470
1471 std::unique_ptr<absl::synchronization_internal::ThreadPool> pool =
1472 CreateDefaultPool();
1473 RunAfterDelay(params.satisfy_condition_delay, pool.get(), [&] {
1474 absl::MutexLock l(&mu);
1475 value = true;
1476 });
1477
1478 absl::Time start_time = absl::Now();
1479 bool result =
1480 params.use_absolute_deadline
1481 ? mu.ReaderLockWhenWithDeadline(absl::Condition(&value),
1482 start_time + params.wait_timeout)
1483 : mu.ReaderLockWhenWithTimeout(absl::Condition(&value),
1484 params.wait_timeout);
1485 mu.ReaderUnlock();
1486
1487 if (DelayIsWithinBounds(params.expected_delay, absl::Now() - start_time)) {
1488 EXPECT_EQ(params.expected_result, result);
1489 break;
1490 }
1491 }
1492 }
1493
1494 TEST_P(TimeoutTest, Wait) {
1495 const TimeoutTestParam params = GetParam();
1496 ABSL_RAW_LOG(INFO, "Params: %s", FormatString(params).c_str());
1497
1498 // Because this test asserts bounds on scheduling delays it is flaky. To
1499 // compensate it loops forever until it passes. Failures express as test
1500 // timeouts, in which case the test log can be used to diagnose the issue.
1501 for (int attempt = 0;; ++attempt) {
1502 ABSL_RAW_LOG(INFO, "Attempt %d", attempt);
1503
1504 absl::Mutex mu;
1505 bool value = false; // condition value (under mu)
1506 absl::CondVar cv; // signals a change of `value`
1507
1508 std::unique_ptr<absl::synchronization_internal::ThreadPool> pool =
1509 CreateDefaultPool();
1510 RunAfterDelay(params.satisfy_condition_delay, pool.get(), [&] {
1511 absl::MutexLock l(&mu);
1512 value = true;
1513 cv.Signal();
1514 });
1515
1516 absl::MutexLock lock(&mu);
1517 absl::Time start_time = absl::Now();
1518 absl::Duration timeout = params.wait_timeout;
1519 absl::Time deadline = start_time + timeout;
1520 while (!value) {
1521 if (params.use_absolute_deadline ? cv.WaitWithDeadline(&mu, deadline)
1522 : cv.WaitWithTimeout(&mu, timeout)) {
1523 break; // deadline/timeout exceeded
1524 }
1525 timeout = deadline - absl::Now(); // recompute
1526 }
1527 bool result = value; // note: `mu` is still held
1528
1529 if (DelayIsWithinBounds(params.expected_delay, absl::Now() - start_time)) {
1530 EXPECT_EQ(params.expected_result, result);
1531 break;
1532 }
1533 }
1534 }
1535
1536 TEST(Mutex, Logging) {
1537 // Allow user to look at logging output
1538 absl::Mutex logged_mutex;
1539 logged_mutex.EnableDebugLog("fido_mutex");
1540 absl::CondVar logged_cv;
1541 logged_cv.EnableDebugLog("rover_cv");
1542 logged_mutex.Lock();
1543 logged_cv.WaitWithTimeout(&logged_mutex, absl::Milliseconds(20));
1544 logged_mutex.Unlock();
1545 logged_mutex.ReaderLock();
1546 logged_mutex.ReaderUnlock();
1547 logged_mutex.Lock();
1548 logged_mutex.Unlock();
1549 logged_cv.Signal();
1550 logged_cv.SignalAll();
1551 }
1552
1553 // --------------------------------------------------------
1554
1555 // Generate the vector of thread counts for tests parameterized on thread count.
1556 static std::vector<int> AllThreadCountValues() {
1557 if (kExtendedTest) {
1558 return {2, 4, 8, 10, 16, 20, 24, 30, 32};
1559 }
1560 return {2, 4, 10};
1561 }
1562
1563 // A test fixture parameterized by thread count.
1564 class MutexVariableThreadCountTest : public ::testing::TestWithParam<int> {};
1565
1566 // Instantiate the above with AllThreadCountOptions().
1567 INSTANTIATE_TEST_SUITE_P(ThreadCounts, MutexVariableThreadCountTest,
1568 ::testing::ValuesIn(AllThreadCountValues()),
1569 ::testing::PrintToStringParamName());
1570
1571 // Reduces iterations by some factor for slow platforms
1572 // (determined empirically).
1573 static int ScaleIterations(int x) {
1574 // ABSL_MUTEX_READER_LOCK_IS_EXCLUSIVE is set in the implementation
1575 // of Mutex that uses either std::mutex or pthread_mutex_t. Use
1576 // these as keys to determine the slow implementation.
1577 #if defined(ABSL_MUTEX_READER_LOCK_IS_EXCLUSIVE)
1578 return x / 10;
1579 #else
1580 return x;
1581 #endif
1582 }
1583
1584 TEST_P(MutexVariableThreadCountTest, Mutex) {
1585 int threads = GetParam();
1586 int iterations = ScaleIterations(10000000) / threads;
1587 int operations = threads * iterations;
1588 EXPECT_EQ(RunTest(&TestMu, threads, iterations, operations), operations);
1589 #if !defined(ABSL_MUTEX_ENABLE_INVARIANT_DEBUGGING_NOT_IMPLEMENTED)
1590 iterations = std::min(iterations, 10);
1591 operations = threads * iterations;
1592 EXPECT_EQ(RunTestWithInvariantDebugging(&TestMu, threads, iterations,
1593 operations, CheckSumG0G1),
1594 operations);
1595 #endif
1596 }
1597
1598 TEST_P(MutexVariableThreadCountTest, Try) {
1599 int threads = GetParam();
1600 int iterations = 1000000 / threads;
1601 int operations = iterations * threads;
1602 EXPECT_EQ(RunTest(&TestTry, threads, iterations, operations), operations);
1603 #if !defined(ABSL_MUTEX_ENABLE_INVARIANT_DEBUGGING_NOT_IMPLEMENTED)
1604 iterations = std::min(iterations, 10);
1605 operations = threads * iterations;
1606 EXPECT_EQ(RunTestWithInvariantDebugging(&TestTry, threads, iterations,
1607 operations, CheckSumG0G1),
1608 operations);
1609 #endif
1610 }
1611
1612 TEST_P(MutexVariableThreadCountTest, R20ms) {
1613 int threads = GetParam();
1614 int iterations = 100;
1615 int operations = iterations * threads;
1616 EXPECT_EQ(RunTest(&TestR20ms, threads, iterations, operations), 0);
1617 }
1618
1619 TEST_P(MutexVariableThreadCountTest, RW) {
1620 int threads = GetParam();
1621 int iterations = ScaleIterations(20000000) / threads;
1622 int operations = iterations * threads;
1623 EXPECT_EQ(RunTest(&TestRW, threads, iterations, operations), operations / 2);
1624 #if !defined(ABSL_MUTEX_ENABLE_INVARIANT_DEBUGGING_NOT_IMPLEMENTED)
1625 iterations = std::min(iterations, 10);
1626 operations = threads * iterations;
1627 EXPECT_EQ(RunTestWithInvariantDebugging(&TestRW, threads, iterations,
1628 operations, CheckSumG0G1),
1629 operations / 2);
1630 #endif
1631 }
1632
1633 TEST_P(MutexVariableThreadCountTest, Await) {
1634 int threads = GetParam();
1635 int iterations = ScaleIterations(500000);
1636 int operations = iterations;
1637 EXPECT_EQ(RunTest(&TestAwait, threads, iterations, operations), operations);
1638 }
1639
1640 TEST_P(MutexVariableThreadCountTest, SignalAll) {
1641 int threads = GetParam();
1642 int iterations = 200000 / threads;
1643 int operations = iterations;
1644 EXPECT_EQ(RunTest(&TestSignalAll, threads, iterations, operations),
1645 operations);
1646 }
1647
1648 TEST(Mutex, Signal) {
1649 int threads = 2; // TestSignal must use two threads
1650 int iterations = 200000;
1651 int operations = iterations;
1652 EXPECT_EQ(RunTest(&TestSignal, threads, iterations, operations), operations);
1653 }
1654
1655 TEST(Mutex, Timed) {
1656 int threads = 10; // Use a fixed thread count of 10
1657 int iterations = 1000;
1658 int operations = iterations;
1659 EXPECT_EQ(RunTest(&TestCVTimeout, threads, iterations, operations),
1660 operations);
1661 }
1662
1663 TEST(Mutex, CVTime) {
1664 int threads = 10; // Use a fixed thread count of 10
1665 int iterations = 1;
1666 EXPECT_EQ(RunTest(&TestCVTime, threads, iterations, 1),
1667 threads * iterations);
1668 }
1669
1670 TEST(Mutex, MuTime) {
1671 int threads = 10; // Use a fixed thread count of 10
1672 int iterations = 1;
1673 EXPECT_EQ(RunTest(&TestMuTime, threads, iterations, 1), threads * iterations);
1674 }
1675
1676 } // namespace
1677