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/Indestructible.h>
  20 #include <folly/ScopeGuard.h>
  21 #include <folly/hash/Hash.h>
  22 #include <folly/portability/SysSyscall.h>
  23 #include <stdint.h>
  24 #include <string.h>
  25 #include <array>
  26 #include <cerrno>
  27 #include <condition_variable>
  28 #include <mutex>
  29
  30 #ifdef __linux__
  31 #include <linux/futex.h>
  32 #endif
  33
  34 using namespace std::chrono;
  35
  36 namespace folly {
  37 namespace detail {
  38
  39 namespace {
  40
  41 ////////////////////////////////////////////////////
  42 // native implementation using the futex() syscall
  43
  44 #ifdef __linux__
  45
  46 /// Certain toolchains (like Android's) don't include the full futex API in
  47 /// their headers even though they support it. Make sure we have our constants
  48 /// even if the headers don't have them.
  49 #ifndef FUTEX_WAIT_BITSET
  50 # define FUTEX_WAIT_BITSET 9
  51 #endif
  52 #ifndef FUTEX_WAKE_BITSET
  53 # define FUTEX_WAKE_BITSET 10
  54 #endif
  55 #ifndef FUTEX_PRIVATE_FLAG
  56 # define FUTEX_PRIVATE_FLAG 128
  57 #endif
  58 #ifndef FUTEX_CLOCK_REALTIME
  59 # define FUTEX_CLOCK_REALTIME 256
  60 #endif
  61
  62 int nativeFutexWake(void* addr, int count, uint32_t wakeMask) {
  63   int rv = syscall(__NR_futex,
  64                    addr, /* addr1 */
  65                    FUTEX_WAKE_BITSET | FUTEX_PRIVATE_FLAG, /* op */
  66                    count, /* val */
  67                    nullptr, /* timeout */
  68                    nullptr, /* addr2 */
  69                    wakeMask); /* val3 */
  70
  71   /* NOTE: we ignore errors on wake for the case of a futex
  72      guarding its own destruction, similar to this
  73      glibc bug with sem_post/sem_wait:
  74      https://sourceware.org/bugzilla/show_bug.cgi?id=12674 */
  75   if (rv < 0) {
  76     return 0;
  77   }
  78   return rv;
  79 }
  80
  81 template <class Clock>
  82 struct timespec
  83 timeSpecFromTimePoint(time_point<Clock> absTime)
  84 {
  85   auto epoch = absTime.time_since_epoch();
  86   if (epoch.count() < 0) {
  87     // kernel timespec_valid requires non-negative seconds and nanos in [0,1G)
  88     epoch = Clock::duration::zero();
  89   }
  90
  91   // timespec-safe seconds and nanoseconds;
  92   // chrono::{nano,}seconds are `long long int`
  93   // whereas timespec uses smaller types
  94   using time_t_seconds = duration<std::time_t, seconds::period>;
  95   using long_nanos = duration<long int, nanoseconds::period>;
  96
  97   auto secs = duration_cast<time_t_seconds>(epoch);
  98   auto nanos = duration_cast<long_nanos>(epoch - secs);
  99   struct timespec result = { secs.count(), nanos.count() };
 100   return result;
 101 }
 102
 103 FutexResult nativeFutexWaitImpl(void* addr,
 104                                 uint32_t expected,
 105                                 time_point<system_clock>* absSystemTime,
 106                                 time_point<steady_clock>* absSteadyTime,
 107                                 uint32_t waitMask) {
 108   assert(absSystemTime == nullptr || absSteadyTime == nullptr);
 109
 110   int op = FUTEX_WAIT_BITSET | FUTEX_PRIVATE_FLAG;
 111   struct timespec ts;
 112   struct timespec* timeout = nullptr;
 113
 114   if (absSystemTime != nullptr) {
 115     op |= FUTEX_CLOCK_REALTIME;
 116     ts = timeSpecFromTimePoint(*absSystemTime);
 117     timeout = &ts;
 118   } else if (absSteadyTime != nullptr) {
 119     ts = timeSpecFromTimePoint(*absSteadyTime);
 120     timeout = &ts;
 121   }
 122
 123   // Unlike FUTEX_WAIT, FUTEX_WAIT_BITSET requires an absolute timeout
 124   // value - http://locklessinc.com/articles/futex_cheat_sheet/
 125   int rv = syscall(__NR_futex,
 126                    addr, /* addr1 */
 127                    op, /* op */
 128                    expected, /* val */
 129                    timeout, /* timeout */
 130                    nullptr, /* addr2 */
 131                    waitMask); /* val3 */
 132
 133   if (rv == 0) {
 134     return FutexResult::AWOKEN;
 135   } else {
 136     switch(errno) {
 137       case ETIMEDOUT:
 138         assert(timeout != nullptr);
 139         return FutexResult::TIMEDOUT;
 140       case EINTR:
 141         return FutexResult::INTERRUPTED;
 142       case EWOULDBLOCK:
 143         return FutexResult::VALUE_CHANGED;
 144       default:
 145         assert(false);
 146         // EINVAL, EACCESS, or EFAULT.  EINVAL means there was an invalid
 147         // op (should be impossible) or an invalid timeout (should have
 148         // been sanitized by timeSpecFromTimePoint).  EACCESS or EFAULT
 149         // means *addr points to invalid memory, which is unlikely because
 150         // the caller should have segfaulted already.  We can either
 151         // crash, or return a value that lets the process continue for
 152         // a bit. We choose the latter. VALUE_CHANGED probably turns the
 153         // caller into a spin lock.
 154         return FutexResult::VALUE_CHANGED;
 155     }
 156   }
 157 }
 158
 159 #endif // __linux__
 160
 161 ///////////////////////////////////////////////////////
 162 // compatibility implementation using standard C++ API
 163
 164 // Our emulated futex uses 4096 lists of wait nodes.  There are two levels
 165 // of locking: a per-list mutex that controls access to the list and a
 166 // per-node mutex, condvar, and bool that are used for the actual wakeups.
 167 // The per-node mutex allows us to do precise wakeups without thundering
 168 // herds.
 169
 170 struct EmulatedFutexWaitNode : public boost::intrusive::list_base_hook<> {
 171   void* const addr_;
 172   const uint32_t waitMask_;
 173
 174   // tricky: hold both bucket and node mutex to write, either to read
 175   bool signaled_;
 176   std::mutex mutex_;
 177   std::condition_variable cond_;
 178
 179   EmulatedFutexWaitNode(void* addr, uint32_t waitMask)
 180     : addr_(addr)
 181     , waitMask_(waitMask)
 182     , signaled_(false)
 183   {
 184   }
 185 };
 186
 187 struct EmulatedFutexBucket {
 188   std::mutex mutex_;
 189   boost::intrusive::list<EmulatedFutexWaitNode> waiters_;
 190
 191   static constexpr size_t const kNumBuckets = kIsMobile ? 256 : 4096;
 192
 193   static EmulatedFutexBucket& bucketFor(void* addr) {
 194     // Statically allocating this lets us use this in allocation-sensitive
 195     // contexts. This relies on the assumption that std::mutex won't dynamically
 196     // allocate memory, which we assume to be the case on Linux and iOS.
 197     static Indestructible<std::array<EmulatedFutexBucket, kNumBuckets>>
 198         gBuckets;
 199     uint64_t mixedBits =
 200         folly::hash::twang_mix64(reinterpret_cast<uintptr_t>(addr));
 201     return (*gBuckets)[mixedBits % kNumBuckets];
 202   }
 203 };
 204
 205 int emulatedFutexWake(void* addr, int count, uint32_t waitMask) {
 206   auto& bucket = EmulatedFutexBucket::bucketFor(addr);
 207   std::unique_lock<std::mutex> bucketLock(bucket.mutex_);
 208
 209   int numAwoken = 0;
 210   for (auto iter = bucket.waiters_.begin();
 211        numAwoken < count && iter != bucket.waiters_.end(); ) {
 212     auto current = iter;
 213     auto& node = *iter++;
 214     if (node.addr_ == addr && (node.waitMask_ & waitMask) != 0) {
 215       ++numAwoken;
 216
 217       // we unlink, but waiter destroys the node
 218       bucket.waiters_.erase(current);
 219
 220       std::unique_lock<std::mutex> nodeLock(node.mutex_);
 221       node.signaled_ = true;
 222       node.cond_.notify_one();
 223     }
 224   }
 225   return numAwoken;
 226 }
 227
 228 template <typename F>
 229 FutexResult emulatedFutexWaitImpl(
 230     F* futex,
 231     uint32_t expected,
 232     time_point<system_clock>* absSystemTime,
 233     time_point<steady_clock>* absSteadyTime,
 234     uint32_t waitMask) {
 235   static_assert(
 236       std::is_same<F, Futex<std::atomic>>::value ||
 237           std::is_same<F, Futex<EmulatedFutexAtomic>>::value,
 238       "Type F must be either Futex<std::atomic> or Futex<EmulatedFutexAtomic>");
 239   void* addr = static_cast<void*>(futex);
 240   auto& bucket = EmulatedFutexBucket::bucketFor(addr);
 241   EmulatedFutexWaitNode node(addr, waitMask);
 242
 243   {
 244     std::unique_lock<std::mutex> bucketLock(bucket.mutex_);
 245
 246     if (futex->load(std::memory_order_relaxed) != expected) {
 247       return FutexResult::VALUE_CHANGED;
 248     }
 249
 250     bucket.waiters_.push_back(node);
 251   } // bucketLock scope
 252
 253   std::cv_status status = std::cv_status::no_timeout;
 254   {
 255     std::unique_lock<std::mutex> nodeLock(node.mutex_);
 256     while (!node.signaled_ && status != std::cv_status::timeout) {
 257       if (absSystemTime != nullptr) {
 258         status = node.cond_.wait_until(nodeLock, *absSystemTime);
 259       } else if (absSteadyTime != nullptr) {
 260         status = node.cond_.wait_until(nodeLock, *absSteadyTime);
 261       } else {
 262         node.cond_.wait(nodeLock);
 263       }
 264     }
 265   } // nodeLock scope
 266
 267   if (status == std::cv_status::timeout) {
 268     // it's not really a timeout until we unlink the unsignaled node
 269     std::unique_lock<std::mutex> bucketLock(bucket.mutex_);
 270     if (!node.signaled_) {
 271       bucket.waiters_.erase(bucket.waiters_.iterator_to(node));
 272       return FutexResult::TIMEDOUT;
 273     }
 274   }
 275   return FutexResult::AWOKEN;
 276 }
 277
 278 } // namespace
 279
 280 /////////////////////////////////
 281 // Futex<> specializations
 282
 283 template <>
 284 int
 285 Futex<std::atomic>::futexWake(int count, uint32_t wakeMask) {
 286 #ifdef __linux__
 287   return nativeFutexWake(this, count, wakeMask);
 288 #else
 289   return emulatedFutexWake(this, count, wakeMask);
 290 #endif
 291 }
 292
 293 template <>
 294 int
 295 Futex<EmulatedFutexAtomic>::futexWake(int count, uint32_t wakeMask) {
 296   return emulatedFutexWake(this, count, wakeMask);
 297 }
 298
 299 template <>
 300 FutexResult
 301 Futex<std::atomic>::futexWaitImpl(uint32_t expected,
 302                                   time_point<system_clock>* absSystemTime,
 303                                   time_point<steady_clock>* absSteadyTime,
 304                                   uint32_t waitMask) {
 305 #ifdef __linux__
 306   return nativeFutexWaitImpl(
 307       this, expected, absSystemTime, absSteadyTime, waitMask);
 308 #else
 309   return emulatedFutexWaitImpl(
 310       this, expected, absSystemTime, absSteadyTime, waitMask);
 311 #endif
 312 }
 313
 314 template <>
 315 FutexResult
 316 Futex<EmulatedFutexAtomic>::futexWaitImpl(
 317         uint32_t expected,
 318         time_point<system_clock>* absSystemTime,
 319         time_point<steady_clock>* absSteadyTime,
 320         uint32_t waitMask) {
 321   return emulatedFutexWaitImpl(
 322       this, expected, absSystemTime, absSteadyTime, waitMask);
 323 }
 324
 325 } // namespace detail
 326 } // namespace folly