folly/detail/Futex.cpp

   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 #include <folly/detail/Futex.h>
  17 #include <folly/ScopeGuard.h>
  18 #include <folly/hash/Hash.h>
  19 #include <folly/portability/SysSyscall.h>
  20 #include <stdint.h>
  21 #include <string.h>
  22 #include <array>
  23 #include <cerrno>
  24
  25 #include <folly/synchronization/ParkingLot.h>
  26
  27 #ifdef __linux__
  28 #include <linux/futex.h>
  29 #endif
  30
  31 using namespace std::chrono;
  32
  33 namespace folly {
  34 namespace detail {
  35
  36 namespace {
  37
  38 ////////////////////////////////////////////////////
  39 // native implementation using the futex() syscall
  40
  41 #ifdef __linux__
  42
  43 /// Certain toolchains (like Android's) don't include the full futex API in
  44 /// their headers even though they support it. Make sure we have our constants
  45 /// even if the headers don't have them.
  46 #ifndef FUTEX_WAIT_BITSET
  47 # define FUTEX_WAIT_BITSET 9
  48 #endif
  49 #ifndef FUTEX_WAKE_BITSET
  50 # define FUTEX_WAKE_BITSET 10
  51 #endif
  52 #ifndef FUTEX_PRIVATE_FLAG
  53 # define FUTEX_PRIVATE_FLAG 128
  54 #endif
  55 #ifndef FUTEX_CLOCK_REALTIME
  56 # define FUTEX_CLOCK_REALTIME 256
  57 #endif
  58
  59 int nativeFutexWake(void* addr, int count, uint32_t wakeMask) {
  60   int rv = syscall(__NR_futex,
  61                    addr, /* addr1 */
  62                    FUTEX_WAKE_BITSET | FUTEX_PRIVATE_FLAG, /* op */
  63                    count, /* val */
  64                    nullptr, /* timeout */
  65                    nullptr, /* addr2 */
  66                    wakeMask); /* val3 */
  67
  68   /* NOTE: we ignore errors on wake for the case of a futex
  69      guarding its own destruction, similar to this
  70      glibc bug with sem_post/sem_wait:
  71      https://sourceware.org/bugzilla/show_bug.cgi?id=12674 */
  72   if (rv < 0) {
  73     return 0;
  74   }
  75   return rv;
  76 }
  77
  78 template <class Clock>
  79 struct timespec
  80 timeSpecFromTimePoint(time_point<Clock> absTime)
  81 {
  82   auto epoch = absTime.time_since_epoch();
  83   if (epoch.count() < 0) {
  84     // kernel timespec_valid requires non-negative seconds and nanos in [0,1G)
  85     epoch = Clock::duration::zero();
  86   }
  87
  88   // timespec-safe seconds and nanoseconds;
  89   // chrono::{nano,}seconds are `long long int`
  90   // whereas timespec uses smaller types
  91   using time_t_seconds = duration<std::time_t, seconds::period>;
  92   using long_nanos = duration<long int, nanoseconds::period>;
  93
  94   auto secs = duration_cast<time_t_seconds>(epoch);
  95   auto nanos = duration_cast<long_nanos>(epoch - secs);
  96   struct timespec result = { secs.count(), nanos.count() };
  97   return result;
  98 }
  99
 100 FutexResult nativeFutexWaitImpl(
 101     void* addr,
 102     uint32_t expected,
 103     system_clock::time_point const* absSystemTime,
 104     steady_clock::time_point const* absSteadyTime,
 105     uint32_t waitMask) {
 106   assert(absSystemTime == nullptr || absSteadyTime == nullptr);
 107
 108   int op = FUTEX_WAIT_BITSET | FUTEX_PRIVATE_FLAG;
 109   struct timespec ts;
 110   struct timespec* timeout = nullptr;
 111
 112   if (absSystemTime != nullptr) {
 113     op |= FUTEX_CLOCK_REALTIME;
 114     ts = timeSpecFromTimePoint(*absSystemTime);
 115     timeout = &ts;
 116   } else if (absSteadyTime != nullptr) {
 117     ts = timeSpecFromTimePoint(*absSteadyTime);
 118     timeout = &ts;
 119   }
 120
 121   // Unlike FUTEX_WAIT, FUTEX_WAIT_BITSET requires an absolute timeout
 122   // value - http://locklessinc.com/articles/futex_cheat_sheet/
 123   int rv = syscall(__NR_futex,
 124                    addr, /* addr1 */
 125                    op, /* op */
 126                    expected, /* val */
 127                    timeout, /* timeout */
 128                    nullptr, /* addr2 */
 129                    waitMask); /* val3 */
 130
 131   if (rv == 0) {
 132     return FutexResult::AWOKEN;
 133   } else {
 134     switch(errno) {
 135       case ETIMEDOUT:
 136         assert(timeout != nullptr);
 137         return FutexResult::TIMEDOUT;
 138       case EINTR:
 139         return FutexResult::INTERRUPTED;
 140       case EWOULDBLOCK:
 141         return FutexResult::VALUE_CHANGED;
 142       default:
 143         assert(false);
 144         // EINVAL, EACCESS, or EFAULT.  EINVAL means there was an invalid
 145         // op (should be impossible) or an invalid timeout (should have
 146         // been sanitized by timeSpecFromTimePoint).  EACCESS or EFAULT
 147         // means *addr points to invalid memory, which is unlikely because
 148         // the caller should have segfaulted already.  We can either
 149         // crash, or return a value that lets the process continue for
 150         // a bit. We choose the latter. VALUE_CHANGED probably turns the
 151         // caller into a spin lock.
 152         return FutexResult::VALUE_CHANGED;
 153     }
 154   }
 155 }
 156
 157 #endif // __linux__
 158
 159 ///////////////////////////////////////////////////////
 160 // compatibility implementation using standard C++ API
 161
 162 using Lot = ParkingLot<uint32_t>;
 163 Lot parkingLot;
 164
 165 int emulatedFutexWake(void* addr, int count, uint32_t waitMask) {
 166   int woken = 0;
 167   parkingLot.unpark(addr, [&](const uint32_t& mask) {
 168     if ((mask & waitMask) == 0) {
 169       return UnparkControl::RetainContinue;
 170     }
 171     assert(count > 0);
 172     count--;
 173     woken++;
 174     return count > 0 ? UnparkControl::RemoveContinue
 175                      : UnparkControl::RemoveBreak;
 176   });
 177   return woken;
 178 }
 179
 180 template <typename F>
 181 FutexResult emulatedFutexWaitImpl(
 182     F* futex,
 183     uint32_t expected,
 184     system_clock::time_point const* absSystemTime,
 185     steady_clock::time_point const* absSteadyTime,
 186     uint32_t waitMask) {
 187   static_assert(
 188       std::is_same<F, Futex<std::atomic>>::value ||
 189           std::is_same<F, Futex<EmulatedFutexAtomic>>::value,
 190       "Type F must be either Futex<std::atomic> or Futex<EmulatedFutexAtomic>");
 191   ParkResult res;
 192   if (absSystemTime) {
 193     res = parkingLot.park_until(
 194         futex,
 195         waitMask,
 196         [&] { return *futex == expected; },
 197         [] {},
 198         *absSystemTime);
 199   } else if (absSteadyTime) {
 200     res = parkingLot.park_until(
 201         futex,
 202         waitMask,
 203         [&] { return *futex == expected; },
 204         [] {},
 205         *absSteadyTime);
 206   } else {
 207     res = parkingLot.park(
 208         futex, waitMask, [&] { return *futex == expected; }, [] {});
 209   }
 210   switch (res) {
 211     case ParkResult::Skip:
 212       return FutexResult::VALUE_CHANGED;
 213     case ParkResult::Unpark:
 214       return FutexResult::AWOKEN;
 215     case ParkResult::Timeout:
 216       return FutexResult::TIMEDOUT;
 217   }
 218
 219   return FutexResult::INTERRUPTED;
 220 }
 221
 222 } // namespace
 223
 224 /////////////////////////////////
 225 // Futex<> specializations
 226
 227 template <>
 228 int
 229 Futex<std::atomic>::futexWake(int count, uint32_t wakeMask) {
 230 #ifdef __linux__
 231   return nativeFutexWake(this, count, wakeMask);
 232 #else
 233   return emulatedFutexWake(this, count, wakeMask);
 234 #endif
 235 }
 236
 237 template <>
 238 int
 239 Futex<EmulatedFutexAtomic>::futexWake(int count, uint32_t wakeMask) {
 240   return emulatedFutexWake(this, count, wakeMask);
 241 }
 242
 243 template <>
 244 FutexResult Futex<std::atomic>::futexWaitImpl(
 245     uint32_t expected,
 246     system_clock::time_point const* absSystemTime,
 247     steady_clock::time_point const* absSteadyTime,
 248     uint32_t waitMask) {
 249 #ifdef __linux__
 250   return nativeFutexWaitImpl(
 251       this, expected, absSystemTime, absSteadyTime, waitMask);
 252 #else
 253   return emulatedFutexWaitImpl(
 254       this, expected, absSystemTime, absSteadyTime, waitMask);
 255 #endif
 256 }
 257
 258 template <>
 259 FutexResult Futex<EmulatedFutexAtomic>::futexWaitImpl(
 260     uint32_t expected,
 261     system_clock::time_point const* absSystemTime,
 262     steady_clock::time_point const* absSteadyTime,
 263     uint32_t waitMask) {
 264   return emulatedFutexWaitImpl(
 265       this, expected, absSystemTime, absSteadyTime, waitMask);
 266 }
 267
 268 } // namespace detail
 269 } // namespace folly