folly/test/FutexTest.cpp

   1 /*
   2  * Copyright 2016 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         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 TEST(Futex, clock_source) {
 186   run_system_clock_test();
 187
 188   /* On some systems steady_clock is just an alias for system_clock. So,
 189    * we must skip run_steady_clock_test if the two clocks are the same. */
 190   if (!std::is_same<system_clock,steady_clock>::value) {
 191     run_steady_clock_test();
 192   }
 193 }
 194
 195 TEST(Futex, basic_live) {
 196   run_basic_tests<std::atomic>();
 197   run_wait_until_tests<std::atomic>();
 198 }
 199
 200 TEST(Futex, basic_emulated) {
 201   run_basic_tests<EmulatedFutexAtomic>();
 202   run_wait_until_tests<EmulatedFutexAtomic>();
 203 }
 204
 205 TEST(Futex, basic_deterministic) {
 206   DSched sched(DSched::uniform(0));
 207   run_basic_tests<DeterministicAtomic>();
 208   run_wait_until_tests<DeterministicAtomic>();
 209 }
 210
 211 int main(int argc, char ** argv) {
 212   testing::InitGoogleTest(&argc, argv);
 213   gflags::ParseCommandLineFlags(&argc, &argv, true);
 214   return RUN_ALL_TESTS();
 215 }