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