folly/detail/Futex.cpp

   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 #include <folly/detail/Futex.h>
  18 #include <boost/intrusive/list.hpp>
  19 #include <folly/Hash.h>
  20 #include <folly/ScopeGuard.h>
  21 #include <folly/portability/SysSyscall.h>
  22 #include <stdint.h>
  23 #include <string.h>
  24 #include <cerrno>
  25 #include <condition_variable>
  26 #include <mutex>
  27
  28 #ifdef __linux__
  29 #include <linux/futex.h>
  30 #endif
  31
  32 using namespace std::chrono;
  33
  34 namespace folly {
  35 namespace detail {
  36
  37 namespace {
  38
  39 ////////////////////////////////////////////////////
  40 // native implementation using the futex() syscall
  41
  42 #ifdef __linux__
  43
  44 /// Certain toolchains (like Android's) don't include the full futex API in
  45 /// their headers even though they support it. Make sure we have our constants
  46 /// even if the headers don't have them.
  47 #ifndef FUTEX_WAIT_BITSET
  48 # define FUTEX_WAIT_BITSET 9
  49 #endif
  50 #ifndef FUTEX_WAKE_BITSET
  51 # define FUTEX_WAKE_BITSET 10
  52 #endif
  53 #ifndef FUTEX_PRIVATE_FLAG
  54 # define FUTEX_PRIVATE_FLAG 128
  55 #endif
  56 #ifndef FUTEX_CLOCK_REALTIME
  57 # define FUTEX_CLOCK_REALTIME 256
  58 #endif
  59
  60 int nativeFutexWake(void* addr, int count, uint32_t wakeMask) {
  61   int rv = syscall(__NR_futex,
  62                    addr, /* addr1 */
  63                    FUTEX_WAKE_BITSET | FUTEX_PRIVATE_FLAG, /* op */
  64                    count, /* val */
  65                    nullptr, /* timeout */
  66                    nullptr, /* addr2 */
  67                    wakeMask); /* val3 */
  68
  69   /* NOTE: we ignore errors on wake for the case of a futex
  70      guarding its own destruction, similar to this
  71      glibc bug with sem_post/sem_wait:
  72      https://sourceware.org/bugzilla/show_bug.cgi?id=12674 */
  73   if (rv < 0) {
  74     return 0;
  75   }
  76   return rv;
  77 }
  78
  79 template <class Clock>
  80 struct timespec
  81 timeSpecFromTimePoint(time_point<Clock> absTime)
  82 {
  83   auto epoch = absTime.time_since_epoch();
  84   if (epoch.count() < 0) {
  85     // kernel timespec_valid requires non-negative seconds and nanos in [0,1G)
  86     epoch = Clock::duration::zero();
  87   }
  88
  89   // timespec-safe seconds and nanoseconds;
  90   // chrono::{nano,}seconds are `long long int`
  91   // whereas timespec uses smaller types
  92   using time_t_seconds = duration<std::time_t, seconds::period>;
  93   using long_nanos = duration<long int, nanoseconds::period>;
  94
  95   auto secs = duration_cast<time_t_seconds>(epoch);
  96   auto nanos = duration_cast<long_nanos>(epoch - secs);
  97   struct timespec result = { secs.count(), nanos.count() };
  98   return result;
  99 }
 100
 101 FutexResult nativeFutexWaitImpl(void* addr,
 102                                 uint32_t expected,
 103                                 time_point<system_clock>* absSystemTime,
 104                                 time_point<steady_clock>* 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 // Our emulated futex uses 4096 lists of wait nodes.  There are two levels
 163 // of locking: a per-list mutex that controls access to the list and a
 164 // per-node mutex, condvar, and bool that are used for the actual wakeups.
 165 // The per-node mutex allows us to do precise wakeups without thundering
 166 // herds.
 167
 168 struct EmulatedFutexWaitNode : public boost::intrusive::list_base_hook<> {
 169   void* const addr_;
 170   const uint32_t waitMask_;
 171
 172   // tricky: hold both bucket and node mutex to write, either to read
 173   bool signaled_;
 174   std::mutex mutex_;
 175   std::condition_variable cond_;
 176
 177   EmulatedFutexWaitNode(void* addr, uint32_t waitMask)
 178     : addr_(addr)
 179     , waitMask_(waitMask)
 180     , signaled_(false)
 181   {
 182   }
 183 };
 184
 185 struct EmulatedFutexBucket {
 186   std::mutex mutex_;
 187   boost::intrusive::list<EmulatedFutexWaitNode> waiters_;
 188
 189   static const size_t kNumBuckets = 4096;
 190
 191   static EmulatedFutexBucket& bucketFor(void* addr) {
 192     static auto gBuckets = new EmulatedFutexBucket[kNumBuckets];
 193     uint64_t mixedBits = folly::hash::twang_mix64(
 194         reinterpret_cast<uintptr_t>(addr));
 195     return gBuckets[mixedBits % kNumBuckets];
 196   }
 197 };
 198
 199 int emulatedFutexWake(void* addr, int count, uint32_t waitMask) {
 200   auto& bucket = EmulatedFutexBucket::bucketFor(addr);
 201   std::unique_lock<std::mutex> bucketLock(bucket.mutex_);
 202
 203   int numAwoken = 0;
 204   for (auto iter = bucket.waiters_.begin();
 205        numAwoken < count && iter != bucket.waiters_.end(); ) {
 206     auto current = iter;
 207     auto& node = *iter++;
 208     if (node.addr_ == addr && (node.waitMask_ & waitMask) != 0) {
 209       ++numAwoken;
 210
 211       // we unlink, but waiter destroys the node
 212       bucket.waiters_.erase(current);
 213
 214       std::unique_lock<std::mutex> nodeLock(node.mutex_);
 215       node.signaled_ = true;
 216       node.cond_.notify_one();
 217     }
 218   }
 219   return numAwoken;
 220 }
 221
 222 template <typename F>
 223 FutexResult emulatedFutexWaitImpl(
 224     F* futex,
 225     uint32_t expected,
 226     time_point<system_clock>* absSystemTime,
 227     time_point<steady_clock>* absSteadyTime,
 228     uint32_t waitMask) {
 229   static_assert(
 230       std::is_same<F, Futex<std::atomic>>::value ||
 231           std::is_same<F, Futex<EmulatedFutexAtomic>>::value,
 232       "Type F must be either Futex<std::atomic> or Futex<EmulatedFutexAtomic>");
 233   void* addr = static_cast<void*>(futex);
 234   auto& bucket = EmulatedFutexBucket::bucketFor(addr);
 235   EmulatedFutexWaitNode node(addr, waitMask);
 236
 237   {
 238     std::unique_lock<std::mutex> bucketLock(bucket.mutex_);
 239
 240     if (futex->load(std::memory_order_relaxed) != expected) {
 241       return FutexResult::VALUE_CHANGED;
 242     }
 243
 244     bucket.waiters_.push_back(node);
 245   } // bucketLock scope
 246
 247   std::cv_status status = std::cv_status::no_timeout;
 248   {
 249     std::unique_lock<std::mutex> nodeLock(node.mutex_);
 250     while (!node.signaled_ && status != std::cv_status::timeout) {
 251       if (absSystemTime != nullptr) {
 252         status = node.cond_.wait_until(nodeLock, *absSystemTime);
 253       } else if (absSteadyTime != nullptr) {
 254         status = node.cond_.wait_until(nodeLock, *absSteadyTime);
 255       } else {
 256         node.cond_.wait(nodeLock);
 257       }
 258     }
 259   } // nodeLock scope
 260
 261   if (status == std::cv_status::timeout) {
 262     // it's not really a timeout until we unlink the unsignaled node
 263     std::unique_lock<std::mutex> bucketLock(bucket.mutex_);
 264     if (!node.signaled_) {
 265       bucket.waiters_.erase(bucket.waiters_.iterator_to(node));
 266       return FutexResult::TIMEDOUT;
 267     }
 268   }
 269   return FutexResult::AWOKEN;
 270 }
 271
 272 } // namespace
 273
 274 /////////////////////////////////
 275 // Futex<> specializations
 276
 277 template <>
 278 int
 279 Futex<std::atomic>::futexWake(int count, uint32_t wakeMask) {
 280 #ifdef __linux__
 281   return nativeFutexWake(this, count, wakeMask);
 282 #else
 283   return emulatedFutexWake(this, count, wakeMask);
 284 #endif
 285 }
 286
 287 template <>
 288 int
 289 Futex<EmulatedFutexAtomic>::futexWake(int count, uint32_t wakeMask) {
 290   return emulatedFutexWake(this, count, wakeMask);
 291 }
 292
 293 template <>
 294 FutexResult
 295 Futex<std::atomic>::futexWaitImpl(uint32_t expected,
 296                                   time_point<system_clock>* absSystemTime,
 297                                   time_point<steady_clock>* absSteadyTime,
 298                                   uint32_t waitMask) {
 299 #ifdef __linux__
 300   return nativeFutexWaitImpl(
 301       this, expected, absSystemTime, absSteadyTime, waitMask);
 302 #else
 303   return emulatedFutexWaitImpl(
 304       this, expected, absSystemTime, absSteadyTime, waitMask);
 305 #endif
 306 }
 307
 308 template <>
 309 FutexResult
 310 Futex<EmulatedFutexAtomic>::futexWaitImpl(
 311         uint32_t expected,
 312         time_point<system_clock>* absSystemTime,
 313         time_point<steady_clock>* absSteadyTime,
 314         uint32_t waitMask) {
 315   return emulatedFutexWaitImpl(
 316       this, expected, absSystemTime, absSteadyTime, waitMask);
 317 }
 318
 319 } // namespace detail
 320 } // namespace folly