folly/detail/Futex.cpp

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