folly/test/FutexTest.cpp

   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 <functional>
  22 #include <ratio>
  23 #include <thread>
  24
  25 #include <glog/logging.h>
  26
  27 #include <folly/Chrono.h>
  28 #include <folly/portability/GTest.h>
  29 #include <folly/portability/Time.h>
  30
  31 using namespace folly::detail;
  32 using namespace folly::test;
  33 using namespace std;
  34 using namespace std::chrono;
  35 using folly::chrono::coarse_steady_clock;
  36
  37 typedef DeterministicSchedule DSched;
  38
  39 template <template <typename> class Atom>
  40 void run_basic_thread(
  41     Futex<Atom>& f) {
  42   EXPECT_TRUE(f.futexWait(0));
  43 }
  44
  45 template <template <typename> class Atom>
  46 void run_basic_tests() {
  47   Futex<Atom> f(0);
  48
  49   EXPECT_FALSE(f.futexWait(1));
  50   EXPECT_EQ(f.futexWake(), 0);
  51
  52   auto thr = DSched::thread(std::bind(run_basic_thread<Atom>, std::ref(f)));
  53
  54   while (f.futexWake() != 1) {
  55     std::this_thread::yield();
  56   }
  57
  58   DSched::join(thr);
  59 }
  60
  61 template <template <typename> class Atom, typename Clock, typename Duration>
  62 void 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 = fp->futexWaitUntil(0, deadline);
  72         EXPECT_TRUE(res == FutexResult::TIMEDOUT || res == FutexResult::AWOKEN);
  73         if (res == FutexResult::AWOKEN) {
  74           break;
  75         }
  76       }
  77     });
  78
  79     while (f.futexWake() != 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(f.futexWaitUntil(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 = time_point_cast<Duration>(
  99         start - 2 * start.time_since_epoch());
 100     EXPECT_EQ(f.futexWaitUntil(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
 108 template <typename Clock>
 109 void 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 = f.futexWaitUntil(0, Clock::now() + milliseconds(100));
 115   EXPECT_TRUE(res == FutexResult::TIMEDOUT || res == FutexResult::INTERRUPTED);
 116 }
 117
 118 template <template <typename> class Atom>
 119 void 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
 128 template <>
 129 void run_wait_until_tests<DeterministicAtomic>() {
 130   deterministicAtomicWaitUntilTests<system_clock>();
 131   deterministicAtomicWaitUntilTests<steady_clock>();
 132   deterministicAtomicWaitUntilTests<coarse_steady_clock>();
 133 }
 134
 135 uint64_t diff(uint64_t a, uint64_t b) {
 136   return a > b ? a - b : b - a;
 137 }
 138
 139 void 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 = duration_cast<nanoseconds>(system_clock::now()
 153                                             .time_since_epoch()).count();
 154
 155     clock_gettime(CLOCK_REALTIME, &ts);
 156     uint64_t b = ts.tv_sec * 1000000000ULL + ts.tv_nsec;
 157
 158     uint64_t c = duration_cast<nanoseconds>(system_clock::now()
 159                                             .time_since_epoch()).count();
 160
 161     if (diff(a, b) <= delta &&
 162         diff(b, c) <= delta &&
 163         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
 172 void 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 = duration_cast<nanoseconds>(steady_clock::now()
 178                                                 .time_since_epoch()).count();
 179
 180   struct timespec ts;
 181   clock_gettime(CLOCK_MONOTONIC, &ts);
 182   const uint64_t B = ts.tv_sec * 1000000000ULL + ts.tv_nsec;
 183
 184   const uint64_t C = duration_cast<nanoseconds>(steady_clock::now()
 185                                                 .time_since_epoch()).count();
 186   EXPECT_TRUE(A <= B && B <= C);
 187 }
 188
 189 template <template <typename> class Atom>
 190 void run_wake_blocked_test() {
 191   for (auto delay = std::chrono::milliseconds(1);; delay *= 2) {
 192     bool success = false;
 193     Futex<Atom> f(0);
 194     auto thr = DSched::thread([&] { success = f.futexWait(0); });
 195     /* sleep override */ std::this_thread::sleep_for(delay);
 196     f.store(1);
 197     f.futexWake(1);
 198     DSched::join(thr);
 199     LOG(INFO) << "delay=" << delay.count() << "_ms, success=" << success;
 200     if (success) {
 201       break;
 202     }
 203   }
 204 }
 205
 206 TEST(Futex, clock_source) {
 207   run_system_clock_test();
 208
 209   /* On some systems steady_clock is just an alias for system_clock. So,
 210    * we must skip run_steady_clock_test if the two clocks are the same. */
 211   if (!std::is_same<system_clock,steady_clock>::value) {
 212     run_steady_clock_test();
 213   }
 214 }
 215
 216 TEST(Futex, basic_live) {
 217   run_basic_tests<std::atomic>();
 218   run_wait_until_tests<std::atomic>();
 219 }
 220
 221 TEST(Futex, basic_emulated) {
 222   run_basic_tests<EmulatedFutexAtomic>();
 223   run_wait_until_tests<EmulatedFutexAtomic>();
 224 }
 225
 226 TEST(Futex, basic_deterministic) {
 227   DSched sched(DSched::uniform(0));
 228   run_basic_tests<DeterministicAtomic>();
 229   run_wait_until_tests<DeterministicAtomic>();
 230 }
 231
 232 TEST(Futex, wake_blocked_live) {
 233   run_wake_blocked_test<std::atomic>();
 234 }
 235
 236 TEST(Futex, wake_blocked_emulated) {
 237   run_wake_blocked_test<EmulatedFutexAtomic>();
 238 }