folly/detail/Futex.cpp

   1 /*
   2  * Copyright 2016 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 <stdint.h>
  19 #include <string.h>
  20 #include <condition_variable>
  21 #include <mutex>
  22 #include <boost/intrusive/list.hpp>
  23 #include <folly/Hash.h>
  24 #include <folly/ScopeGuard.h>
  25
  26 #ifdef __linux__
  27 # include <errno.h>
  28 # include <linux/futex.h>
  29 # include <sys/syscall.h>
  30 #endif
  31
  32 using namespace std::chrono;
  33
  34 namespace folly { 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(void* addr,
 101                                 uint32_t expected,
 102                                 time_point<system_clock>* absSystemTime,
 103                                 time_point<steady_clock>* absSteadyTime,
 104                                 uint32_t waitMask) {
 105   assert(absSystemTime == nullptr || absSteadyTime == nullptr);
 106
 107   int op = FUTEX_WAIT_BITSET | FUTEX_PRIVATE_FLAG;
 108   struct timespec ts;
 109   struct timespec* timeout = nullptr;
 110
 111   if (absSystemTime != nullptr) {
 112     op |= FUTEX_CLOCK_REALTIME;
 113     ts = timeSpecFromTimePoint(*absSystemTime);
 114     timeout = &ts;
 115   } else if (absSteadyTime != nullptr) {
 116     ts = timeSpecFromTimePoint(*absSteadyTime);
 117     timeout = &ts;
 118   }
 119
 120   // Unlike FUTEX_WAIT, FUTEX_WAIT_BITSET requires an absolute timeout
 121   // value - http://locklessinc.com/articles/futex_cheat_sheet/
 122   int rv = syscall(__NR_futex,
 123                    addr, /* addr1 */
 124                    op, /* op */
 125                    expected, /* val */
 126                    timeout, /* timeout */
 127                    nullptr, /* addr2 */
 128                    waitMask); /* val3 */
 129
 130   if (rv == 0) {
 131     return FutexResult::AWOKEN;
 132   } else {
 133     switch(errno) {
 134       case ETIMEDOUT:
 135         assert(timeout != nullptr);
 136         return FutexResult::TIMEDOUT;
 137       case EINTR:
 138         return FutexResult::INTERRUPTED;
 139       case EWOULDBLOCK:
 140         return FutexResult::VALUE_CHANGED;
 141       default:
 142         assert(false);
 143         // EINVAL, EACCESS, or EFAULT.  EINVAL means there was an invalid
 144         // op (should be impossible) or an invalid timeout (should have
 145         // been sanitized by timeSpecFromTimePoint).  EACCESS or EFAULT
 146         // means *addr points to invalid memory, which is unlikely because
 147         // the caller should have segfaulted already.  We can either
 148         // crash, or return a value that lets the process continue for
 149         // a bit. We choose the latter. VALUE_CHANGED probably turns the
 150         // caller into a spin lock.
 151         return FutexResult::VALUE_CHANGED;
 152     }
 153   }
 154 }
 155
 156 #endif // __linux__
 157
 158 ///////////////////////////////////////////////////////
 159 // compatibility implementation using standard C++ API
 160
 161 // Our emulated futex uses 4096 lists of wait nodes.  There are two levels
 162 // of locking: a per-list mutex that controls access to the list and a
 163 // per-node mutex, condvar, and bool that are used for the actual wakeups.
 164 // The per-node mutex allows us to do precise wakeups without thundering
 165 // herds.
 166
 167 struct EmulatedFutexWaitNode : public boost::intrusive::list_base_hook<> {
 168   void* const addr_;
 169   const uint32_t waitMask_;
 170
 171   // tricky: hold both bucket and node mutex to write, either to read
 172   bool signaled_;
 173   std::mutex mutex_;
 174   std::condition_variable cond_;
 175
 176   EmulatedFutexWaitNode(void* addr, uint32_t waitMask)
 177     : addr_(addr)
 178     , waitMask_(waitMask)
 179     , signaled_(false)
 180   {
 181   }
 182 };
 183
 184 struct EmulatedFutexBucket {
 185   std::mutex mutex_;
 186   boost::intrusive::list<EmulatedFutexWaitNode> waiters_;
 187
 188   static const size_t kNumBuckets = 4096;
 189   static EmulatedFutexBucket* gBuckets;
 190   static std::once_flag gBucketInit;
 191
 192   static EmulatedFutexBucket& bucketFor(void* addr) {
 193     std::call_once(gBucketInit, [](){
 194       gBuckets = new EmulatedFutexBucket[kNumBuckets];
 195     });
 196     uint64_t mixedBits = folly::hash::twang_mix64(
 197         reinterpret_cast<uintptr_t>(addr));
 198     return gBuckets[mixedBits % kNumBuckets];
 199   }
 200 };
 201
 202 EmulatedFutexBucket* EmulatedFutexBucket::gBuckets;
 203 std::once_flag EmulatedFutexBucket::gBucketInit;
 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 FutexResult emulatedFutexWaitImpl(
 229         void* addr,
 230         uint32_t expected,
 231         time_point<system_clock>* absSystemTime,
 232         time_point<steady_clock>* absSteadyTime,
 233         uint32_t waitMask) {
 234   auto& bucket = EmulatedFutexBucket::bucketFor(addr);
 235   EmulatedFutexWaitNode node(addr, waitMask);
 236
 237   {
 238     std::unique_lock<std::mutex> bucketLock(bucket.mutex_);
 239
 240     uint32_t actual;
 241     memcpy(&actual, addr, sizeof(uint32_t));
 242     if (actual != expected) {
 243       return FutexResult::VALUE_CHANGED;
 244     }
 245
 246     bucket.waiters_.push_back(node);
 247   } // bucketLock scope
 248
 249   std::cv_status status = std::cv_status::no_timeout;
 250   {
 251     std::unique_lock<std::mutex> nodeLock(node.mutex_);
 252     while (!node.signaled_ && status != std::cv_status::timeout) {
 253       if (absSystemTime != nullptr) {
 254         status = node.cond_.wait_until(nodeLock, *absSystemTime);
 255       } else if (absSteadyTime != nullptr) {
 256         status = node.cond_.wait_until(nodeLock, *absSteadyTime);
 257       } else {
 258         node.cond_.wait(nodeLock);
 259       }
 260     }
 261   } // nodeLock scope
 262
 263   if (status == std::cv_status::timeout) {
 264     // it's not really a timeout until we unlink the unsignaled node
 265     std::unique_lock<std::mutex> bucketLock(bucket.mutex_);
 266     if (!node.signaled_) {
 267       bucket.waiters_.erase(bucket.waiters_.iterator_to(node));
 268       return FutexResult::TIMEDOUT;
 269     }
 270   }
 271   return FutexResult::AWOKEN;
 272 }
 273
 274 } // anon namespace
 275
 276
 277 /////////////////////////////////
 278 // Futex<> specializations
 279
 280 template <>
 281 int
 282 Futex<std::atomic>::futexWake(int count, uint32_t wakeMask) {
 283 #ifdef __linux__
 284   return nativeFutexWake(this, count, wakeMask);
 285 #else
 286   return emulatedFutexWake(this, count, wakeMask);
 287 #endif
 288 }
 289
 290 template <>
 291 int
 292 Futex<EmulatedFutexAtomic>::futexWake(int count, uint32_t wakeMask) {
 293   return emulatedFutexWake(this, count, wakeMask);
 294 }
 295
 296 template <>
 297 FutexResult
 298 Futex<std::atomic>::futexWaitImpl(uint32_t expected,
 299                                   time_point<system_clock>* absSystemTime,
 300                                   time_point<steady_clock>* absSteadyTime,
 301                                   uint32_t waitMask) {
 302 #ifdef __linux__
 303   return nativeFutexWaitImpl(
 304       this, expected, absSystemTime, absSteadyTime, waitMask);
 305 #else
 306   return emulatedFutexWaitImpl(
 307       this, expected, absSystemTime, absSteadyTime, waitMask);
 308 #endif
 309 }
 310
 311 template <>
 312 FutexResult
 313 Futex<EmulatedFutexAtomic>::futexWaitImpl(
 314         uint32_t expected,
 315         time_point<system_clock>* absSystemTime,
 316         time_point<steady_clock>* absSteadyTime,
 317         uint32_t waitMask) {
 318   return emulatedFutexWaitImpl(
 319       this, expected, absSystemTime, absSteadyTime, waitMask);
 320 }
 321
 322 }} // namespace folly::detail