folly/test/FutexTest.cpp

   1 /*
   2  * Copyright 2014 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 <gflags/gflags.h>
  26 #include <glog/logging.h>
  27 #include <gtest/gtest.h>
  28 #include <time.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         auto deadline = time_point_cast<Duration>(
  68             Clock::now() + microseconds(1 << (stress % 20)));
  69         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   auto start = Clock::now();
  85   EXPECT_EQ(f.futexWaitUntil(0, start + milliseconds(100)),
  86             FutexResult::TIMEDOUT);
  87   LOG(INFO) << "Futex wait timed out after waiting for "
  88             << duration_cast<milliseconds>(Clock::now() - start).count()
  89             << "ms, should be ~100ms";
  90 }
  91
  92 template <typename Clock>
  93 void deterministicAtomicWaitUntilTests() {
  94   Futex<DeterministicAtomic> f(0);
  95
  96   // Futex wait must eventually fail with either FutexResult::TIMEDOUT or
  97   // FutexResult::INTERRUPTED
  98   auto res = f.futexWaitUntil(0, Clock::now() + milliseconds(100));
  99   EXPECT_TRUE(res == FutexResult::TIMEDOUT || res == FutexResult::INTERRUPTED);
 100 }
 101
 102 template<template<typename> class Atom>
 103 void run_wait_until_tests() {
 104   liveClockWaitUntilTests<Atom, system_clock, system_clock::duration>();
 105   liveClockWaitUntilTests<Atom, steady_clock, steady_clock::duration>();
 106
 107   typedef duration<int64_t, pico> picoseconds;
 108   liveClockWaitUntilTests<Atom, system_clock, picoseconds>();
 109 }
 110
 111 template <>
 112 void run_wait_until_tests<DeterministicAtomic>() {
 113   deterministicAtomicWaitUntilTests<system_clock>();
 114   deterministicAtomicWaitUntilTests<steady_clock>();
 115 }
 116
 117 uint64_t diff(uint64_t a, uint64_t b) {
 118   return a > b ? a - b : b - a;
 119 }
 120
 121 void run_system_clock_test() {
 122   /* Test to verify that system_clock uses clock_gettime(CLOCK_REALTIME, ...)
 123    * for the time_points */
 124   struct timespec ts;
 125   const int maxIters = 1000;
 126   int iter = 0;
 127   uint64_t delta = 10000000 /* 10 ms */;
 128
 129   /** The following loop is only to make the test more robust in the presence of
 130    * clock adjustments that can occur. We just run the loop maxIter times and
 131    * expect with very high probability that there will be atleast one iteration
 132    * of the test during which clock adjustments > delta have not occurred. */
 133   while (iter < maxIters) {
 134     uint64_t a = duration_cast<nanoseconds>(system_clock::now()
 135                                             .time_since_epoch()).count();
 136
 137     clock_gettime(CLOCK_REALTIME, &ts);
 138     uint64_t b = ts.tv_sec * 1000000000ULL + ts.tv_nsec;
 139
 140     uint64_t c = duration_cast<nanoseconds>(system_clock::now()
 141                                             .time_since_epoch()).count();
 142
 143     if (diff(a, b) <= delta &&
 144         diff(b, c) <= delta &&
 145         diff(a, c) <= 2 * delta) {
 146       /* Success! system_clock uses CLOCK_REALTIME for time_points */
 147       break;
 148     }
 149     iter++;
 150   }
 151   EXPECT_TRUE(iter < maxIters);
 152 }
 153
 154 void run_steady_clock_test() {
 155   /* Test to verify that steady_clock uses clock_gettime(CLOCK_MONOTONIC, ...)
 156    * for the time_points */
 157   EXPECT_TRUE(steady_clock::is_steady);
 158
 159   uint64_t A = duration_cast<nanoseconds>(steady_clock::now()
 160                                           .time_since_epoch()).count();
 161
 162   struct timespec ts;
 163   clock_gettime(CLOCK_MONOTONIC, &ts);
 164   uint64_t B = ts.tv_sec * 1000000000ULL + ts.tv_nsec;
 165
 166   uint64_t C = duration_cast<nanoseconds>(steady_clock::now()
 167                                           .time_since_epoch()).count();
 168   EXPECT_TRUE(A <= B && B <= C);
 169 }
 170
 171 TEST(Futex, clock_source) {
 172   run_system_clock_test();
 173
 174   /* On some systems steady_clock is just an alias for system_clock. So,
 175    * we must skip run_steady_clock_test if the two clocks are the same. */
 176   if (!std::is_same<system_clock,steady_clock>::value) {
 177     run_steady_clock_test();
 178   }
 179 }
 180
 181 TEST(Futex, basic_live) {
 182   run_basic_tests<std::atomic>();
 183   run_wait_until_tests<std::atomic>();
 184 }
 185
 186 TEST(Futex, basic_emulated) {
 187   run_basic_tests<EmulatedFutexAtomic>();
 188   run_wait_until_tests<EmulatedFutexAtomic>();
 189 }
 190
 191 TEST(Futex, basic_deterministic) {
 192   DSched sched(DSched::uniform(0));
 193   run_basic_tests<DeterministicAtomic>();
 194   run_wait_until_tests<DeterministicAtomic>();
 195 }
 196
 197 int main(int argc, char ** argv) {
 198   testing::InitGoogleTest(&argc, argv);
 199   gflags::ParseCommandLineFlags(&argc, &argv, true);
 200   return RUN_ALL_TESTS();
 201 }