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