X-Git-Url: http://plrg.eecs.uci.edu/git/?p=folly.git;a=blobdiff_plain;f=folly%2Fdetail%2FFutex.cpp;h=b4dd3d1953532273d76f8befd38868662f766654;hp=118eb466f72dbaf6a252b6765f7b375b385b5ef2;hb=ee1a988dbb1648c25d1cf1c40eafbf2e7bff81b4;hpb=ed8c80a0e0988e4ce687f51ca832a00e4a6b7930

diff --git a/folly/detail/Futex.cpp b/folly/detail/Futex.cpp
index 118eb466..b4dd3d19 100644
--- a/folly/detail/Futex.cpp
+++ b/folly/detail/Futex.cpp
@@ -1,5 +1,5 @@
 /*
- * Copyright 2017 Facebook, Inc.
+ * Copyright 2017-present Facebook, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -13,26 +13,25 @@
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
-
 #include <folly/detail/Futex.h>
+#include <folly/ScopeGuard.h>
+#include <folly/hash/Hash.h>
+#include <folly/portability/SysSyscall.h>
 #include <stdint.h>
 #include <string.h>
-#include <condition_variable>
-#include <mutex>
-#include <boost/intrusive/list.hpp>
-#include <folly/CallOnce.h>
-#include <folly/Hash.h>
-#include <folly/ScopeGuard.h>
+#include <array>
+#include <cerrno>
+
+#include <folly/synchronization/ParkingLot.h>
 
 #ifdef __linux__
-# include <errno.h>
-# include <linux/futex.h>
-# include <sys/syscall.h>
+#include <linux/futex.h>
 #endif
 
 using namespace std::chrono;
 
-namespace folly { namespace detail {
+namespace folly {
+namespace detail {
 
 namespace {
 
@@ -159,121 +158,67 @@ FutexResult nativeFutexWaitImpl(void* addr,
 ///////////////////////////////////////////////////////
 // compatibility implementation using standard C++ API
 
-// Our emulated futex uses 4096 lists of wait nodes.  There are two levels
-// of locking: a per-list mutex that controls access to the list and a
-// per-node mutex, condvar, and bool that are used for the actual wakeups.
-// The per-node mutex allows us to do precise wakeups without thundering
-// herds.
-
-struct EmulatedFutexWaitNode : public boost::intrusive::list_base_hook<> {
-  void* const addr_;
-  const uint32_t waitMask_;
-
-  // tricky: hold both bucket and node mutex to write, either to read
-  bool signaled_;
-  std::mutex mutex_;
-  std::condition_variable cond_;
-
-  EmulatedFutexWaitNode(void* addr, uint32_t waitMask)
-    : addr_(addr)
-    , waitMask_(waitMask)
-    , signaled_(false)
-  {
-  }
-};
-
-struct EmulatedFutexBucket {
-  std::mutex mutex_;
-  boost::intrusive::list<EmulatedFutexWaitNode> waiters_;
-
-  static const size_t kNumBuckets = 4096;
-  static EmulatedFutexBucket* gBuckets;
-  static folly::once_flag gBucketInit;
-
-  static EmulatedFutexBucket& bucketFor(void* addr) {
-    folly::call_once(gBucketInit, [](){
-      gBuckets = new EmulatedFutexBucket[kNumBuckets];
-    });
-    uint64_t mixedBits = folly::hash::twang_mix64(
-        reinterpret_cast<uintptr_t>(addr));
-    return gBuckets[mixedBits % kNumBuckets];
-  }
-};
-
-EmulatedFutexBucket* EmulatedFutexBucket::gBuckets;
-folly::once_flag EmulatedFutexBucket::gBucketInit;
+using Lot = ParkingLot<uint32_t>;
+Lot parkingLot;
 
 int emulatedFutexWake(void* addr, int count, uint32_t waitMask) {
-  auto& bucket = EmulatedFutexBucket::bucketFor(addr);
-  std::unique_lock<std::mutex> bucketLock(bucket.mutex_);
-
-  int numAwoken = 0;
-  for (auto iter = bucket.waiters_.begin();
-       numAwoken < count && iter != bucket.waiters_.end(); ) {
-    auto current = iter;
-    auto& node = *iter++;
-    if (node.addr_ == addr && (node.waitMask_ & waitMask) != 0) {
-      ++numAwoken;
-
-      // we unlink, but waiter destroys the node
-      bucket.waiters_.erase(current);
-
-      std::unique_lock<std::mutex> nodeLock(node.mutex_);
-      node.signaled_ = true;
-      node.cond_.notify_one();
+  int woken = 0;
+  parkingLot.unpark(addr, [&](const uint32_t& mask) {
+    if ((mask & waitMask) == 0) {
+      return UnparkControl::RetainContinue;
     }
-  }
-  return numAwoken;
+    assert(count > 0);
+    count--;
+    woken++;
+    return count > 0 ? UnparkControl::RemoveContinue
+                     : UnparkControl::RemoveBreak;
+  });
+  return woken;
 }
 
+template <typename F>
 FutexResult emulatedFutexWaitImpl(
-        void* addr,
-        uint32_t expected,
-        time_point<system_clock>* absSystemTime,
-        time_point<steady_clock>* absSteadyTime,
-        uint32_t waitMask) {
-  auto& bucket = EmulatedFutexBucket::bucketFor(addr);
-  EmulatedFutexWaitNode node(addr, waitMask);
-
-  {
-    std::unique_lock<std::mutex> bucketLock(bucket.mutex_);
-
-    uint32_t actual;
-    memcpy(&actual, addr, sizeof(uint32_t));
-    if (actual != expected) {
+    F* futex,
+    uint32_t expected,
+    time_point<system_clock>* absSystemTime,
+    time_point<steady_clock>* absSteadyTime,
+    uint32_t waitMask) {
+  static_assert(
+      std::is_same<F, Futex<std::atomic>>::value ||
+          std::is_same<F, Futex<EmulatedFutexAtomic>>::value,
+      "Type F must be either Futex<std::atomic> or Futex<EmulatedFutexAtomic>");
+  ParkResult res;
+  if (absSystemTime) {
+    res = parkingLot.park_until(
+        futex,
+        waitMask,
+        [&] { return *futex == expected; },
+        [] {},
+        *absSystemTime);
+  } else if (absSteadyTime) {
+    res = parkingLot.park_until(
+        futex,
+        waitMask,
+        [&] { return *futex == expected; },
+        [] {},
+        *absSteadyTime);
+  } else {
+    res = parkingLot.park(
+        futex, waitMask, [&] { return *futex == expected; }, [] {});
+  }
+  switch (res) {
+    case ParkResult::Skip:
       return FutexResult::VALUE_CHANGED;
-    }
-
-    bucket.waiters_.push_back(node);
-  } // bucketLock scope
-
-  std::cv_status status = std::cv_status::no_timeout;
-  {
-    std::unique_lock<std::mutex> nodeLock(node.mutex_);
-    while (!node.signaled_ && status != std::cv_status::timeout) {
-      if (absSystemTime != nullptr) {
-        status = node.cond_.wait_until(nodeLock, *absSystemTime);
-      } else if (absSteadyTime != nullptr) {
-        status = node.cond_.wait_until(nodeLock, *absSteadyTime);
-      } else {
-        node.cond_.wait(nodeLock);
-      }
-    }
-  } // nodeLock scope
-
-  if (status == std::cv_status::timeout) {
-    // it's not really a timeout until we unlink the unsignaled node
-    std::unique_lock<std::mutex> bucketLock(bucket.mutex_);
-    if (!node.signaled_) {
-      bucket.waiters_.erase(bucket.waiters_.iterator_to(node));
+    case ParkResult::Unpark:
+      return FutexResult::AWOKEN;
+    case ParkResult::Timeout:
       return FutexResult::TIMEDOUT;
-    }
   }
-  return FutexResult::AWOKEN;
-}
 
-} // anon namespace
+  return FutexResult::INTERRUPTED;
+}
 
+} // namespace
 
 /////////////////////////////////
 // Futex<> specializations
@@ -320,4 +265,5 @@ Futex<EmulatedFutexAtomic>::futexWaitImpl(
       this, expected, absSystemTime, absSteadyTime, waitMask);
 }
 
-}} // namespace folly::detail
+} // namespace detail
+} // namespace folly