1/*
2 * Copyright 2013-present 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 <condition_variable>
22#include <functional>
23#include <ratio>
24#include <thread>
25
26#include <glog/logging.h>
27
28#include <folly/Chrono.h>
29#include <folly/portability/GTest.h>
30#include <folly/portability/Time.h>
31
32using namespace folly::detail;
33using namespace folly::test;
34using namespace std;
35using namespace std::chrono;
36using folly::chrono::coarse_steady_clock;
37
38typedef DeterministicSchedule DSched;
39
40template <template <typename> class Atom>
41void run_basic_thread(Futex<Atom>& f) {
42 EXPECT_EQ(FutexResult::AWOKEN, futexWait(&f, 0));
43}
44
45template <template <typename> class Atom>
46void run_basic_tests() {
47 Futex<Atom> f(0);
48
49 EXPECT_EQ(FutexResult::VALUE_CHANGED, futexWait(&f, 1));
50 EXPECT_EQ(futexWake(&f), 0);
51
52 auto thr = DSched::thread(std::bind(run_basic_thread<Atom>, std::ref(f)));
53
54 while (futexWake(&f) != 1) {
55 std::this_thread::yield();
56 }
57
58 DSched::join(thr);
59}
60
61template <template <typename> class Atom, typename Clock, typename Duration>
62void liveClockWaitUntilTests() {
63 Futex<Atom> f(0);
64
65 for (int stress = 0; stress < 1000; ++stress) {
66 auto fp = &f; // workaround for t5336595
67 auto thrA = DSched::thread([fp, stress] {
68 while (true) {
69 const auto deadline = time_point_cast<Duration>(
70 Clock::now() + microseconds(1 << (stress % 20)));
71 const auto res = futexWaitUntil(fp, 0, deadline);
72 EXPECT_TRUE(res == FutexResult::TIMEDOUT || res == FutexResult::AWOKEN);
73 if (res == FutexResult::AWOKEN) {
74 break;
75 }
76 }
77 });
78
79 while (futexWake(&f) != 1) {
80 std::this_thread::yield();
81 }
82
83 DSched::join(thrA);
84 }
85
86 {
87 const auto start = Clock::now();
88 const auto deadline = time_point_cast<Duration>(start + milliseconds(100));
89 EXPECT_EQ(futexWaitUntil(&f, 0, deadline), FutexResult::TIMEDOUT);
90 LOG(INFO) << "Futex wait timed out after waiting for "
91 << duration_cast<milliseconds>(Clock::now() - start).count()
92 << "ms using clock with " << Duration::period::den
93 << " precision, should be ~100ms";
94 }
95
96 {
97 const auto start = Clock::now();
98 const auto deadline =
99 time_point_cast<Duration>(start - 2 * start.time_since_epoch());
100 EXPECT_EQ(futexWaitUntil(&f, 0, deadline), FutexResult::TIMEDOUT);
101 LOG(INFO) << "Futex wait with invalid deadline timed out after waiting for "
102 << duration_cast<milliseconds>(Clock::now() - start).count()
103 << "ms using clock with " << Duration::period::den
104 << " precision, should be ~0ms";
105 }
106}
107
108template <typename Clock>
109void deterministicAtomicWaitUntilTests() {
110 Futex<DeterministicAtomic> f(0);
111
112 // Futex wait must eventually fail with either FutexResult::TIMEDOUT or
113 // FutexResult::INTERRUPTED
114 const auto res = futexWaitUntil(&f, 0, Clock::now() + milliseconds(100));
115 EXPECT_TRUE(res == FutexResult::TIMEDOUT || res == FutexResult::INTERRUPTED);
116}
117
118template <template <typename> class Atom>
119void run_wait_until_tests() {
120 liveClockWaitUntilTests<Atom, system_clock, system_clock::duration>();
121 liveClockWaitUntilTests<Atom, steady_clock, steady_clock::duration>();
122 liveClockWaitUntilTests<Atom, steady_clock, coarse_steady_clock::duration>();
123
124 typedef duration<int64_t, std::ratio<1, 10000000>> decimicroseconds;
125 liveClockWaitUntilTests<Atom, system_clock, decimicroseconds>();
126}
127
128template <>
129void run_wait_until_tests<DeterministicAtomic>() {
130 deterministicAtomicWaitUntilTests<system_clock>();
131 deterministicAtomicWaitUntilTests<steady_clock>();
132 deterministicAtomicWaitUntilTests<coarse_steady_clock>();
133}
134
135uint64_t diff(uint64_t a, uint64_t b) {
136 return a > b ? a - b : b - a;
137}
138
139void run_system_clock_test() {
140 /* Test to verify that system_clock uses clock_gettime(CLOCK_REALTIME, ...)
141 * for the time_points */
142 struct timespec ts;
143 const int maxIters = 1000;
144 int iter = 0;
145 const uint64_t delta = 10000000 /* 10 ms */;
146
147 /** The following loop is only to make the test more robust in the presence of
148 * clock adjustments that can occur. We just run the loop maxIter times and
149 * expect with very high probability that there will be atleast one iteration
150 * of the test during which clock adjustments > delta have not occurred. */
151 while (iter < maxIters) {
152 uint64_t a =
153 duration_cast<nanoseconds>(system_clock::now().time_since_epoch())
154 .count();
155
156 clock_gettime(CLOCK_REALTIME, &ts);
157 uint64_t b = ts.tv_sec * 1000000000ULL + ts.tv_nsec;
158
159 uint64_t c =
160 duration_cast<nanoseconds>(system_clock::now().time_since_epoch())
161 .count();
162
163 if (diff(a, b) <= delta && diff(b, c) <= delta && diff(a, c) <= 2 * delta) {
164 /* Success! system_clock uses CLOCK_REALTIME for time_points */
165 break;
166 }
167 iter++;
168 }
169 EXPECT_TRUE(iter < maxIters);
170}
171
172void run_steady_clock_test() {
173 /* Test to verify that steady_clock uses clock_gettime(CLOCK_MONOTONIC, ...)
174 * for the time_points */
175 EXPECT_TRUE(steady_clock::is_steady);
176
177 const uint64_t A =
178 duration_cast<nanoseconds>(steady_clock::now().time_since_epoch())
179 .count();
180
181 struct timespec ts;
182 clock_gettime(CLOCK_MONOTONIC, &ts);
183 const uint64_t B = ts.tv_sec * 1000000000ULL + ts.tv_nsec;
184
185 const uint64_t C =
186 duration_cast<nanoseconds>(steady_clock::now().time_since_epoch())
187 .count();
188 EXPECT_TRUE(A <= B && B <= C);
189}
190
191template <template <typename> class Atom>
192void run_wake_blocked_test() {
193 for (auto delay = std::chrono::milliseconds(1);; delay *= 2) {
194 bool success = false;
195 Futex<Atom> f(0);
196 auto thr = DSched::thread(
197 [&] { success = FutexResult::AWOKEN == futexWait(&f, 0); });
198 /* sleep override */ std::this_thread::sleep_for(delay);
199 f.store(1);
200 futexWake(&f, 1);
201 DSched::join(thr);
202 LOG(INFO) << "delay=" << delay.count() << "_ms, success=" << success;
203 if (success) {
204 break;
205 }
206 }
207}
208
209TEST(Futex, clock_source) {
210 run_system_clock_test();
211
212 /* On some systems steady_clock is just an alias for system_clock. So,
213 * we must skip run_steady_clock_test if the two clocks are the same. */
214 if (!std::is_same<system_clock, steady_clock>::value) {
215 run_steady_clock_test();
216 }
217}
218
219TEST(Futex, basic_live) {
220 run_basic_tests<std::atomic>();
221 run_wait_until_tests<std::atomic>();
222}
223
224TEST(Futex, basic_emulated) {
225 run_basic_tests<EmulatedFutexAtomic>();
226 run_wait_until_tests<EmulatedFutexAtomic>();
227}
228
229TEST(Futex, basic_deterministic) {
230 DSched sched(DSched::uniform(0));
231 run_basic_tests<DeterministicAtomic>();
232 run_wait_until_tests<DeterministicAtomic>();
233}
234
235TEST(Futex, wake_blocked_live) {
236 run_wake_blocked_test<std::atomic>();
237}
238
239TEST(Futex, wake_blocked_emulated) {
240 run_wake_blocked_test<EmulatedFutexAtomic>();
241}
242