folly/detail/Futex.h

   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 #pragma once
  18
  19 #include <atomic>
  20 #include <chrono>
  21 #include <limits>
  22 #include <assert.h>
  23 #include <errno.h>
  24 #include <linux/futex.h>
  25 #include <sys/syscall.h>
  26 #include <unistd.h>
  27 #include <boost/noncopyable.hpp>
  28
  29 using std::chrono::steady_clock;
  30 using std::chrono::system_clock;
  31 using std::chrono::time_point;
  32
  33 namespace folly { namespace detail {
  34
  35 enum class FutexResult {
  36   VALUE_CHANGED, /* Futex value didn't match expected */
  37   AWOKEN,        /* futex wait matched with a futex wake */
  38   INTERRUPTED,   /* Spurious wake-up or signal caused futex wait failure */
  39   TIMEDOUT
  40 };
  41
  42 /* Converts return value and errno from a futex syscall to a FutexResult */
  43 FutexResult futexErrnoToFutexResult(int returnVal, int futexErrno);
  44
  45 /**
  46  * Futex is an atomic 32 bit unsigned integer that provides access to the
  47  * futex() syscall on that value.  It is templated in such a way that it
  48  * can interact properly with DeterministicSchedule testing.
  49  *
  50  * If you don't know how to use futex(), you probably shouldn't be using
  51  * this class.  Even if you do know how, you should have a good reason
  52  * (and benchmarks to back you up).
  53  */
  54 template <template <typename> class Atom = std::atomic>
  55 struct Futex : Atom<uint32_t>, boost::noncopyable {
  56
  57   explicit Futex(uint32_t init = 0) : Atom<uint32_t>(init) {}
  58
  59   /** Puts the thread to sleep if this->load() == expected.  Returns true when
  60    *  it is returning because it has consumed a wake() event, false for any
  61    *  other return (signal, this->load() != expected, or spurious wakeup). */
  62   bool futexWait(uint32_t expected, uint32_t waitMask = -1);
  63
  64   /** Similar to futexWait but also accepts a timeout that gives the time until
  65    *  when the call can block (time is the absolute time i.e time since epoch).
  66    *  Allowed clock types: std::chrono::system_clock, std::chrono::steady_clock.
  67    *  Returns one of FutexResult values.
  68    *
  69    *  NOTE: On some systems steady_clock is just an alias for system_clock,
  70    *  and is not actually steady.*/
  71   template <class Clock, class Duration = typename Clock::duration>
  72   FutexResult futexWaitUntil(uint32_t expected,
  73                              const time_point<Clock, Duration>& absTime,
  74                              uint32_t waitMask = -1);
  75
  76   /** Wakens up to count waiters where (waitMask & wakeMask) != 0,
  77    *  returning the number of awoken threads. */
  78   int futexWake(int count = std::numeric_limits<int>::max(),
  79                 uint32_t wakeMask = -1);
  80
  81   private:
  82
  83   /** Futex wait implemented via syscall SYS_futex. absTimeout gives
  84    *  time till when the wait can block. If it is nullptr the call will
  85    *  block until a matching futex wake is received. extraOpFlags can be
  86    *  used to specify addtional flags to add to the futex operation (by
  87    *  default only FUTEX_WAIT_BITSET and FUTEX_PRIVATE_FLAG are included).
  88    *  Returns 0 on success or -1 on error, with errno set to one of the
  89    *  values listed in futex(2). */
  90   int futexWaitImpl(uint32_t expected,
  91                     const struct timespec* absTimeout,
  92                     int extraOpFlags,
  93                     uint32_t waitMask);
  94 };
  95
  96 template <>
  97 inline int
  98 Futex<std::atomic>::futexWaitImpl(uint32_t expected,
  99                                   const struct timespec* absTimeout,
 100                                   int extraOpFlags,
 101                                   uint32_t waitMask) {
 102   assert(sizeof(*this) == sizeof(int));
 103
 104   /* Unlike FUTEX_WAIT, FUTEX_WAIT_BITSET requires an absolute timeout
 105    * value - http://locklessinc.com/articles/futex_cheat_sheet/ */
 106   int rv = syscall(
 107       SYS_futex,
 108       this, /* addr1 */
 109       FUTEX_WAIT_BITSET | FUTEX_PRIVATE_FLAG | extraOpFlags, /* op */
 110       expected, /* val */
 111       absTimeout, /* timeout */
 112       nullptr, /* addr2 */
 113       waitMask); /* val3 */
 114
 115   assert(rv == 0 ||
 116          errno == EWOULDBLOCK ||
 117          errno == EINTR ||
 118          (absTimeout != nullptr && errno == ETIMEDOUT));
 119
 120   return rv;
 121 }
 122
 123 template <>
 124 inline bool Futex<std::atomic>::futexWait(uint32_t expected,
 125                                           uint32_t waitMask) {
 126   return futexWaitImpl(expected, nullptr, 0 /* extraOpFlags */, waitMask) == 0;
 127 }
 128
 129 template <>
 130 inline int Futex<std::atomic>::futexWake(int count, uint32_t wakeMask) {
 131   assert(sizeof(*this) == sizeof(int));
 132   int rv = syscall(SYS_futex,
 133                    this, /* addr1 */
 134                    FUTEX_WAKE_BITSET | FUTEX_PRIVATE_FLAG, /* op */
 135                    count, /* val */
 136                    nullptr, /* timeout */
 137                    nullptr, /* addr2 */
 138                    wakeMask); /* val3 */
 139   assert(rv >= 0);
 140   return rv;
 141 }
 142
 143 /* Convert std::chrono::time_point to struct timespec */
 144 template <class Clock, class Duration = typename Clock::Duration>
 145 struct timespec timePointToTimeSpec(const time_point<Clock, Duration>& tp) {
 146   using std::chrono::nanoseconds;
 147   using std::chrono::seconds;
 148   using std::chrono::duration_cast;
 149
 150   struct timespec ts;
 151   auto duration = tp.time_since_epoch();
 152   auto secs = duration_cast<seconds>(duration);
 153   auto nanos = duration_cast<nanoseconds>(duration - secs);
 154   ts.tv_sec = secs.count();
 155   ts.tv_nsec = nanos.count();
 156   return ts;
 157 }
 158
 159 template <template<typename> class Atom> template<class Clock, class Duration>
 160 inline FutexResult
 161 Futex<Atom>::futexWaitUntil(
 162                uint32_t expected,
 163                const time_point<Clock, Duration>& absTime,
 164                uint32_t waitMask) {
 165
 166   static_assert(std::is_same<Clock,system_clock>::value ||
 167                 std::is_same<Clock,steady_clock>::value,
 168                 "Only std::system_clock or std::steady_clock supported");
 169
 170   struct timespec absTimeSpec = timePointToTimeSpec(absTime);
 171   int extraOpFlags = 0;
 172
 173   /* We must use FUTEX_CLOCK_REALTIME flag if we are getting the time_point
 174    * from the system clock (CLOCK_REALTIME). This check also works correctly for
 175    * broken glibc in which steady_clock is a typedef to system_clock.*/
 176   if (std::is_same<Clock,system_clock>::value) {
 177     extraOpFlags = FUTEX_CLOCK_REALTIME;
 178   } else {
 179     assert(Clock::is_steady);
 180   }
 181
 182   const int rv = futexWaitImpl(expected, &absTimeSpec, extraOpFlags, waitMask);
 183   return futexErrnoToFutexResult(rv, errno);
 184 }
 185
 186 }}