folly/detail/Futex.cpp

   1 /*
   2  * Copyright 2015 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   assert(rv >= 0);
  69
  70   return rv;
  71 }
  72
  73 template <class Clock>
  74 struct timespec
  75 timeSpecFromTimePoint(time_point<Clock> absTime)
  76 {
  77   auto epoch = absTime.time_since_epoch();
  78   if (epoch.count() < 0) {
  79     // kernel timespec_valid requires non-negative seconds and nanos in [0,1G)
  80     epoch = Clock::duration::zero();
  81   }
  82
  83   // timespec-safe seconds and nanoseconds;
  84   // chrono::{nano,}seconds are `long long int`
  85   // whereas timespec uses smaller types
  86   using time_t_seconds = duration<std::time_t, seconds::period>;
  87   using long_nanos = duration<long int, nanoseconds::period>;
  88
  89   auto secs = duration_cast<time_t_seconds>(epoch);
  90   auto nanos = duration_cast<long_nanos>(epoch - secs);
  91   struct timespec result = { secs.count(), nanos.count() };
  92   return result;
  93 }
  94
  95 FutexResult nativeFutexWaitImpl(void* addr,
  96                                 uint32_t expected,
  97                                 time_point<system_clock>* absSystemTime,
  98                                 time_point<steady_clock>* absSteadyTime,
  99                                 uint32_t waitMask) {
 100   assert(absSystemTime == nullptr || absSteadyTime == nullptr);
 101
 102   int op = FUTEX_WAIT_BITSET | FUTEX_PRIVATE_FLAG;
 103   struct timespec ts;
 104   struct timespec* timeout = nullptr;
 105
 106   if (absSystemTime != nullptr) {
 107     op |= FUTEX_CLOCK_REALTIME;
 108     ts = timeSpecFromTimePoint(*absSystemTime);
 109     timeout = &ts;
 110   } else if (absSteadyTime != nullptr) {
 111     ts = timeSpecFromTimePoint(*absSteadyTime);
 112     timeout = &ts;
 113   }
 114
 115   // Unlike FUTEX_WAIT, FUTEX_WAIT_BITSET requires an absolute timeout
 116   // value - http://locklessinc.com/articles/futex_cheat_sheet/
 117   int rv = syscall(__NR_futex,
 118                    addr, /* addr1 */
 119                    op, /* op */
 120                    expected, /* val */
 121                    timeout, /* timeout */
 122                    nullptr, /* addr2 */
 123                    waitMask); /* val3 */
 124
 125   if (rv == 0) {
 126     return FutexResult::AWOKEN;
 127   } else {
 128     switch(errno) {
 129       case ETIMEDOUT:
 130         assert(timeout != nullptr);
 131         return FutexResult::TIMEDOUT;
 132       case EINTR:
 133         return FutexResult::INTERRUPTED;
 134       case EWOULDBLOCK:
 135         return FutexResult::VALUE_CHANGED;
 136       default:
 137         assert(false);
 138         // EINVAL, EACCESS, or EFAULT.  EINVAL means there was an invalid
 139         // op (should be impossible) or an invalid timeout (should have
 140         // been sanitized by timeSpecFromTimePoint).  EACCESS or EFAULT
 141         // means *addr points to invalid memory, which is unlikely because
 142         // the caller should have segfaulted already.  We can either
 143         // crash, or return a value that lets the process continue for
 144         // a bit. We choose the latter. VALUE_CHANGED probably turns the
 145         // caller into a spin lock.
 146         return FutexResult::VALUE_CHANGED;
 147     }
 148   }
 149 }
 150
 151 #endif // __linux__
 152
 153 ///////////////////////////////////////////////////////
 154 // compatibility implementation using standard C++ API
 155
 156 // Our emulated futex uses 4096 lists of wait nodes.  There are two levels
 157 // of locking: a per-list mutex that controls access to the list and a
 158 // per-node mutex, condvar, and bool that are used for the actual wakeups.
 159 // The per-node mutex allows us to do precise wakeups without thundering
 160 // herds.
 161
 162 struct EmulatedFutexWaitNode : public boost::intrusive::list_base_hook<> {
 163   void* const addr_;
 164   const uint32_t waitMask_;
 165
 166   // tricky: hold both bucket and node mutex to write, either to read
 167   bool signaled_;
 168   std::mutex mutex_;
 169   std::condition_variable cond_;
 170
 171   EmulatedFutexWaitNode(void* addr, uint32_t waitMask)
 172     : addr_(addr)
 173     , waitMask_(waitMask)
 174     , signaled_(false)
 175   {
 176   }
 177 };
 178
 179 struct EmulatedFutexBucket {
 180   std::mutex mutex_;
 181   boost::intrusive::list<EmulatedFutexWaitNode> waiters_;
 182
 183   static const size_t kNumBuckets = 4096;
 184   static EmulatedFutexBucket* gBuckets;
 185   static std::once_flag gBucketInit;
 186
 187   static EmulatedFutexBucket& bucketFor(void* addr) {
 188     std::call_once(gBucketInit, [](){
 189       gBuckets = new EmulatedFutexBucket[kNumBuckets];
 190     });
 191     uint64_t mixedBits = folly::hash::twang_mix64(
 192         reinterpret_cast<uintptr_t>(addr));
 193     return gBuckets[mixedBits % kNumBuckets];
 194   }
 195 };
 196
 197 EmulatedFutexBucket* EmulatedFutexBucket::gBuckets;
 198 std::once_flag EmulatedFutexBucket::gBucketInit;
 199
 200 int emulatedFutexWake(void* addr, int count, uint32_t waitMask) {
 201   auto& bucket = EmulatedFutexBucket::bucketFor(addr);
 202   std::unique_lock<std::mutex> bucketLock(bucket.mutex_);
 203
 204   int numAwoken = 0;
 205   for (auto iter = bucket.waiters_.begin();
 206        numAwoken < count && iter != bucket.waiters_.end(); ) {
 207     auto current = iter;
 208     auto& node = *iter++;
 209     if (node.addr_ == addr && (node.waitMask_ & waitMask) != 0) {
 210       ++numAwoken;
 211
 212       // we unlink, but waiter destroys the node
 213       bucket.waiters_.erase(current);
 214
 215       std::unique_lock<std::mutex> nodeLock(node.mutex_);
 216       node.signaled_ = true;
 217       node.cond_.notify_one();
 218     }
 219   }
 220   return numAwoken;
 221 }
 222
 223 FutexResult emulatedFutexWaitImpl(
 224         void* addr,
 225         uint32_t expected,
 226         time_point<system_clock>* absSystemTime,
 227         time_point<steady_clock>* absSteadyTime,
 228         uint32_t waitMask) {
 229   auto& bucket = EmulatedFutexBucket::bucketFor(addr);
 230   EmulatedFutexWaitNode node(addr, waitMask);
 231
 232   {
 233     std::unique_lock<std::mutex> bucketLock(bucket.mutex_);
 234
 235     uint32_t actual;
 236     memcpy(&actual, addr, sizeof(uint32_t));
 237     if (actual != expected) {
 238       return FutexResult::VALUE_CHANGED;
 239     }
 240
 241     bucket.waiters_.push_back(node);
 242   } // bucketLock scope
 243
 244   std::cv_status status = std::cv_status::no_timeout;
 245   {
 246     std::unique_lock<std::mutex> nodeLock(node.mutex_);
 247     while (!node.signaled_ && status != std::cv_status::timeout) {
 248       if (absSystemTime != nullptr) {
 249         status = node.cond_.wait_until(nodeLock, *absSystemTime);
 250       } else if (absSteadyTime != nullptr) {
 251         status = node.cond_.wait_until(nodeLock, *absSteadyTime);
 252       } else {
 253         node.cond_.wait(nodeLock);
 254       }
 255     }
 256   } // nodeLock scope
 257
 258   if (status == std::cv_status::timeout) {
 259     // it's not really a timeout until we unlink the unsignaled node
 260     std::unique_lock<std::mutex> bucketLock(bucket.mutex_);
 261     if (!node.signaled_) {
 262       bucket.waiters_.erase(bucket.waiters_.iterator_to(node));
 263       return FutexResult::TIMEDOUT;
 264     }
 265   }
 266   return FutexResult::AWOKEN;
 267 }
 268
 269 } // anon namespace
 270
 271
 272 /////////////////////////////////
 273 // Futex<> specializations
 274
 275 template <>
 276 int
 277 Futex<std::atomic>::futexWake(int count, uint32_t wakeMask) {
 278 #ifdef __linux__
 279   return nativeFutexWake(this, count, wakeMask);
 280 #else
 281   return emulatedFutexWake(this, count, wakeMask);
 282 #endif
 283 }
 284
 285 template <>
 286 int
 287 Futex<EmulatedFutexAtomic>::futexWake(int count, uint32_t wakeMask) {
 288   return emulatedFutexWake(this, count, wakeMask);
 289 }
 290
 291 template <>
 292 FutexResult
 293 Futex<std::atomic>::futexWaitImpl(uint32_t expected,
 294                                   time_point<system_clock>* absSystemTime,
 295                                   time_point<steady_clock>* absSteadyTime,
 296                                   uint32_t waitMask) {
 297 #ifdef __linux__
 298   return nativeFutexWaitImpl(
 299       this, expected, absSystemTime, absSteadyTime, waitMask);
 300 #else
 301   return emulatedFutexWaitImpl(
 302       this, expected, absSystemTime, absSteadyTime, waitMask);
 303 #endif
 304 }
 305
 306 template <>
 307 FutexResult
 308 Futex<EmulatedFutexAtomic>::futexWaitImpl(
 309         uint32_t expected,
 310         time_point<system_clock>* absSystemTime,
 311         time_point<steady_clock>* absSteadyTime,
 312         uint32_t waitMask) {
 313   return emulatedFutexWaitImpl(
 314       this, expected, absSystemTime, absSteadyTime, waitMask);
 315 }
 316
 317 }} // namespace folly::detail