folly/detail/Futex.h

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