folly/detail/Futex.h

   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 #pragma once
  18
  19 #include <atomic>
  20 #include <cassert>
  21 #include <chrono>
  22 #include <limits>
  23 #include <type_traits>
  24
  25 #include <boost/noncopyable.hpp>
  26
  27 #include <folly/portability/Unistd.h>
  28
  29 namespace folly { namespace detail {
  30
  31 enum class FutexResult {
  32   VALUE_CHANGED, /* Futex value didn't match expected */
  33   AWOKEN,        /* futex wait matched with a futex wake */
  34   INTERRUPTED,   /* Spurious wake-up or signal caused futex wait failure */
  35   TIMEDOUT,
  36 };
  37
  38 /**
  39  * Futex is an atomic 32 bit unsigned integer that provides access to the
  40  * futex() syscall on that value.  It is templated in such a way that it
  41  * can interact properly with DeterministicSchedule testing.
  42  *
  43  * If you don't know how to use futex(), you probably shouldn't be using
  44  * this class.  Even if you do know how, you should have a good reason
  45  * (and benchmarks to back you up).
  46  */
  47 template <template <typename> class Atom = std::atomic>
  48 struct Futex : Atom<uint32_t>, boost::noncopyable {
  49
  50   explicit constexpr Futex(uint32_t init = 0) : Atom<uint32_t>(init) {}
  51
  52   /** Puts the thread to sleep if this->load() == expected.  Returns true when
  53    *  it is returning because it has consumed a wake() event, false for any
  54    *  other return (signal, this->load() != expected, or spurious wakeup). */
  55   bool futexWait(uint32_t expected, uint32_t waitMask = -1) {
  56     auto rv = futexWaitImpl(expected, nullptr, nullptr, waitMask);
  57     assert(rv != FutexResult::TIMEDOUT);
  58     return rv == FutexResult::AWOKEN;
  59   }
  60
  61   /** Similar to futexWait but also accepts a deadline until when the wait call
  62    *  may block.
  63    *
  64    *  Optimal clock types: std::chrono::system_clock, std::chrono::steady_clock.
  65    *  NOTE: On some systems steady_clock is just an alias for system_clock,
  66    *  and is not actually steady.
  67    *
  68    *  For any other clock type, now() will be invoked twice. */
  69   template <class Clock, class Duration = typename Clock::duration>
  70   FutexResult futexWaitUntil(
  71       uint32_t expected,
  72       std::chrono::time_point<Clock, Duration> const& deadline,
  73       uint32_t waitMask = -1) {
  74     using Target = typename std::conditional<
  75         Clock::is_steady,
  76         std::chrono::steady_clock,
  77         std::chrono::system_clock>::type;
  78     auto const converted = time_point_conv<Target>(deadline);
  79     return futexWaitImpl(expected, converted, waitMask);
  80   }
  81
  82   /** Wakens up to count waiters where (waitMask & wakeMask) !=
  83    *  0, returning the number of awoken threads, or -1 if an error
  84    *  occurred.  Note that when constructing a concurrency primitive
  85    *  that can guard its own destruction, it is likely that you will
  86    *  want to ignore EINVAL here (as well as making sure that you
  87    *  never touch the object after performing the memory store that
  88    *  is the linearization point for unlock or control handoff).
  89    *  See https://sourceware.org/bugzilla/show_bug.cgi?id=13690 */
  90   int futexWake(int count = std::numeric_limits<int>::max(),
  91                 uint32_t wakeMask = -1);
  92
  93  private:
  94   /** Optimal when TargetClock is the same type as Clock.
  95    *
  96    *  Otherwise, both Clock::now() and TargetClock::now() must be invoked. */
  97   template <typename TargetClock, typename Clock, typename Duration>
  98   static typename TargetClock::time_point time_point_conv(
  99       std::chrono::time_point<Clock, Duration> const& time) {
 100     using std::chrono::duration_cast;
 101     using TargetDuration = typename TargetClock::duration;
 102     using TargetTimePoint = typename TargetClock::time_point;
 103     if (std::is_same<Clock, TargetClock>::value) {
 104       // in place of time_point_cast, which cannot compile without if-constexpr
 105       auto const delta = time.time_since_epoch();
 106       return TargetTimePoint(duration_cast<TargetDuration>(delta));
 107     } else {
 108       // different clocks with different epochs, so non-optimal case
 109       auto const delta = time - Clock::now();
 110       return TargetClock::now() + duration_cast<TargetDuration>(delta);
 111     }
 112   }
 113
 114   template <typename Deadline>
 115   typename std::enable_if<Deadline::clock::is_steady, FutexResult>::type
 116   futexWaitImpl(
 117       uint32_t expected,
 118       Deadline const& deadline,
 119       uint32_t waitMask) {
 120     return futexWaitImpl(expected, nullptr, &deadline, waitMask);
 121   }
 122
 123   template <typename Deadline>
 124   typename std::enable_if<!Deadline::clock::is_steady, FutexResult>::type
 125   futexWaitImpl(
 126       uint32_t expected,
 127       Deadline const& deadline,
 128       uint32_t waitMask) {
 129     return futexWaitImpl(expected, &deadline, nullptr, waitMask);
 130   }
 131
 132   /** Underlying implementation of futexWait and futexWaitUntil.
 133    *  At most one of absSystemTime and absSteadyTime should be non-null.
 134    *  Timeouts are separated into separate parameters to allow the
 135    *  implementations to be elsewhere without templating on the clock
 136    *  type, which is otherwise complicated by the fact that steady_clock
 137    *  is the same as system_clock on some platforms. */
 138   FutexResult futexWaitImpl(
 139       uint32_t expected,
 140       std::chrono::system_clock::time_point const* absSystemTime,
 141       std::chrono::steady_clock::time_point const* absSteadyTime,
 142       uint32_t waitMask);
 143 };
 144
 145 /** A std::atomic subclass that can be used to force Futex to emulate
 146  *  the underlying futex() syscall.  This is primarily useful to test or
 147  *  benchmark the emulated implementation on systems that don't need it. */
 148 template <typename T>
 149 struct EmulatedFutexAtomic : public std::atomic<T> {
 150   EmulatedFutexAtomic() noexcept = default;
 151   constexpr /* implicit */ EmulatedFutexAtomic(T init) noexcept
 152       : std::atomic<T>(init) {}
 153   // It doesn't copy or move
 154   EmulatedFutexAtomic(EmulatedFutexAtomic&& rhs) = delete;
 155 };
 156
 157 /* Available specializations, with definitions elsewhere */
 158
 159 template <>
 160 int Futex<std::atomic>::futexWake(int count, uint32_t wakeMask);
 161
 162 template <>
 163 FutexResult Futex<std::atomic>::futexWaitImpl(
 164     uint32_t expected,
 165     std::chrono::system_clock::time_point const* absSystemTime,
 166     std::chrono::steady_clock::time_point const* absSteadyTime,
 167     uint32_t waitMask);
 168
 169 template <>
 170 int Futex<EmulatedFutexAtomic>::futexWake(int count, uint32_t wakeMask);
 171
 172 template <>
 173 FutexResult Futex<EmulatedFutexAtomic>::futexWaitImpl(
 174     uint32_t expected,
 175     std::chrono::system_clock::time_point const* absSystemTime,
 176     std::chrono::steady_clock::time_point const* absSteadyTime,
 177     uint32_t waitMask);
 178
 179 } // namespace detail
 180 } // namespace folly