24cd175625758281d893dae811202c4872c0ab22
[folly.git] / folly / test / FutexTest.cpp
1 /*
2  * Copyright 2017 Facebook, Inc.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *   http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16
17 #include <folly/detail/Futex.h>
18 #include <folly/test/DeterministicSchedule.h>
19
20 #include <chrono>
21 #include <functional>
22 #include <ratio>
23 #include <thread>
24
25 #include <glog/logging.h>
26
27 #include <folly/portability/Time.h>
28 #include <folly/portability/GTest.h>
29
30 using namespace folly::detail;
31 using namespace folly::test;
32 using namespace std;
33 using namespace std::chrono;
34
35 typedef DeterministicSchedule DSched;
36
37 template <template<typename> class Atom>
38 void run_basic_thread(
39     Futex<Atom>& f) {
40   EXPECT_TRUE(f.futexWait(0));
41 }
42
43 template <template<typename> class Atom>
44 void run_basic_tests() {
45   Futex<Atom> f(0);
46
47   EXPECT_FALSE(f.futexWait(1));
48   EXPECT_EQ(f.futexWake(), 0);
49
50   auto thr = DSched::thread(std::bind(run_basic_thread<Atom>, std::ref(f)));
51
52   while (f.futexWake() != 1) {
53     std::this_thread::yield();
54   }
55
56   DSched::join(thr);
57 }
58
59 template <template<typename> class Atom, typename Clock, typename Duration>
60 void liveClockWaitUntilTests() {
61   Futex<Atom> f(0);
62
63   for (int stress = 0; stress < 1000; ++stress) {
64     auto fp = &f; // workaround for t5336595
65     auto thrA = DSched::thread([fp,stress]{
66       while (true) {
67         const auto deadline = time_point_cast<Duration>(
68             Clock::now() + microseconds(1 << (stress % 20)));
69         const auto res = fp->futexWaitUntil(0, deadline);
70         EXPECT_TRUE(res == FutexResult::TIMEDOUT || res == FutexResult::AWOKEN);
71         if (res == FutexResult::AWOKEN) {
72           break;
73         }
74       }
75     });
76
77     while (f.futexWake() != 1) {
78       std::this_thread::yield();
79     }
80
81     DSched::join(thrA);
82   }
83
84   {
85     const auto start = Clock::now();
86     const auto deadline = time_point_cast<Duration>(start + milliseconds(100));
87     EXPECT_EQ(f.futexWaitUntil(0, deadline), FutexResult::TIMEDOUT);
88     LOG(INFO) << "Futex wait timed out after waiting for "
89               << duration_cast<milliseconds>(Clock::now() - start).count()
90               << "ms using clock with " << Duration::period::den
91               << " precision, should be ~100ms";
92   }
93
94   {
95     const auto start = Clock::now();
96     const auto deadline = time_point_cast<Duration>(
97         start - 2 * start.time_since_epoch());
98     EXPECT_EQ(f.futexWaitUntil(0, deadline), FutexResult::TIMEDOUT);
99     LOG(INFO) << "Futex wait with invalid deadline timed out after waiting for "
100               << duration_cast<milliseconds>(Clock::now() - start).count()
101               << "ms using clock with " << Duration::period::den
102               << " precision, should be ~0ms";
103   }
104 }
105
106 template <typename Clock>
107 void deterministicAtomicWaitUntilTests() {
108   Futex<DeterministicAtomic> f(0);
109
110   // Futex wait must eventually fail with either FutexResult::TIMEDOUT or
111   // FutexResult::INTERRUPTED
112   const auto res = f.futexWaitUntil(0, Clock::now() + milliseconds(100));
113   EXPECT_TRUE(res == FutexResult::TIMEDOUT || res == FutexResult::INTERRUPTED);
114 }
115
116 template<template<typename> class Atom>
117 void run_wait_until_tests() {
118   liveClockWaitUntilTests<Atom, system_clock, system_clock::duration>();
119   liveClockWaitUntilTests<Atom, steady_clock, steady_clock::duration>();
120
121   typedef duration<int64_t, std::ratio<1, 10000000>> decimicroseconds;
122   liveClockWaitUntilTests<Atom, system_clock, decimicroseconds>();
123 }
124
125 template <>
126 void run_wait_until_tests<DeterministicAtomic>() {
127   deterministicAtomicWaitUntilTests<system_clock>();
128   deterministicAtomicWaitUntilTests<steady_clock>();
129 }
130
131 uint64_t diff(uint64_t a, uint64_t b) {
132   return a > b ? a - b : b - a;
133 }
134
135 void run_system_clock_test() {
136   /* Test to verify that system_clock uses clock_gettime(CLOCK_REALTIME, ...)
137    * for the time_points */
138   struct timespec ts;
139   const int maxIters = 1000;
140   int iter = 0;
141   const uint64_t delta = 10000000 /* 10 ms */;
142
143   /** The following loop is only to make the test more robust in the presence of
144    * clock adjustments that can occur. We just run the loop maxIter times and
145    * expect with very high probability that there will be atleast one iteration
146    * of the test during which clock adjustments > delta have not occurred. */
147   while (iter < maxIters) {
148     uint64_t a = duration_cast<nanoseconds>(system_clock::now()
149                                             .time_since_epoch()).count();
150
151     clock_gettime(CLOCK_REALTIME, &ts);
152     uint64_t b = ts.tv_sec * 1000000000ULL + ts.tv_nsec;
153
154     uint64_t c = duration_cast<nanoseconds>(system_clock::now()
155                                             .time_since_epoch()).count();
156
157     if (diff(a, b) <= delta &&
158         diff(b, c) <= delta &&
159         diff(a, c) <= 2 * delta) {
160       /* Success! system_clock uses CLOCK_REALTIME for time_points */
161       break;
162     }
163     iter++;
164   }
165   EXPECT_TRUE(iter < maxIters);
166 }
167
168 void run_steady_clock_test() {
169   /* Test to verify that steady_clock uses clock_gettime(CLOCK_MONOTONIC, ...)
170    * for the time_points */
171   EXPECT_TRUE(steady_clock::is_steady);
172
173   const uint64_t A = duration_cast<nanoseconds>(steady_clock::now()
174                                                 .time_since_epoch()).count();
175
176   struct timespec ts;
177   clock_gettime(CLOCK_MONOTONIC, &ts);
178   const uint64_t B = ts.tv_sec * 1000000000ULL + ts.tv_nsec;
179
180   const uint64_t C = duration_cast<nanoseconds>(steady_clock::now()
181                                                 .time_since_epoch()).count();
182   EXPECT_TRUE(A <= B && B <= C);
183 }
184
185 template <template <typename> class Atom>
186 void run_wake_blocked_test() {
187   Futex<Atom> f(0);
188
189   auto thr = DSched::thread([&] { EXPECT_TRUE(f.futexWait(0)); });
190
191   // A sleep here guarantees to a large extent that 'thr' will execute
192   // futexWait before we wake it up, thus testing late futexWake.
193   std::this_thread::sleep_for(std::chrono::milliseconds(2));
194
195   f.store(1);
196   f.futexWake(1);
197   DSched::join(thr);
198 }
199
200 TEST(Futex, clock_source) {
201   run_system_clock_test();
202
203   /* On some systems steady_clock is just an alias for system_clock. So,
204    * we must skip run_steady_clock_test if the two clocks are the same. */
205   if (!std::is_same<system_clock,steady_clock>::value) {
206     run_steady_clock_test();
207   }
208 }
209
210 TEST(Futex, basic_live) {
211   run_basic_tests<std::atomic>();
212   run_wait_until_tests<std::atomic>();
213 }
214
215 TEST(Futex, basic_emulated) {
216   run_basic_tests<EmulatedFutexAtomic>();
217   run_wait_until_tests<EmulatedFutexAtomic>();
218 }
219
220 TEST(Futex, basic_deterministic) {
221   DSched sched(DSched::uniform(0));
222   run_basic_tests<DeterministicAtomic>();
223   run_wait_until_tests<DeterministicAtomic>();
224 }
225
226 TEST(Futex, wake_blocked_live) {
227   run_wake_blocked_test<std::atomic>();
228 }
229
230 TEST(Futex, wake_blocked_emulated) {
231   run_wake_blocked_test<EmulatedFutexAtomic>();
232 }