X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=folly%2Fdetail%2FFutex.cpp;h=14fbe8ad151974a2d28a4593a1b22da658ed19bc;hb=b67b22f4e27773e2e2c155a3629ff8d468bb1286;hp=9baafd2a48a0008e8018feadbf27b4bd88ba6f40;hpb=22afce906d7e98d95f8c45c3301072d9fd891d41;p=folly.git

diff --git a/folly/detail/Futex.cpp b/folly/detail/Futex.cpp
index 9baafd2a..14fbe8ad 100644
--- a/folly/detail/Futex.cpp
+++ b/folly/detail/Futex.cpp
@@ -1,5 +1,5 @@
 /*
- * Copyright 2014 Facebook, Inc.
+ * Copyright 2013-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,28 +13,257 @@
  * 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 <array>
+#include <cerrno>
+
+#include <folly/synchronization/ParkingLot.h>
+
+#ifdef __linux__
+#include <linux/futex.h>
+#endif
+
+using namespace std::chrono;
+
+namespace folly {
+namespace detail {
+
+namespace {
+
+////////////////////////////////////////////////////
+// native implementation using the futex() syscall
+
+#ifdef __linux__
+
+/// Certain toolchains (like Android's) don't include the full futex API in
+/// their headers even though they support it. Make sure we have our constants
+/// even if the headers don't have them.
+#ifndef FUTEX_WAIT_BITSET
+# define FUTEX_WAIT_BITSET 9
+#endif
+#ifndef FUTEX_WAKE_BITSET
+# define FUTEX_WAKE_BITSET 10
+#endif
+#ifndef FUTEX_PRIVATE_FLAG
+# define FUTEX_PRIVATE_FLAG 128
+#endif
+#ifndef FUTEX_CLOCK_REALTIME
+# define FUTEX_CLOCK_REALTIME 256
+#endif
+
+int nativeFutexWake(void* addr, int count, uint32_t wakeMask) {
+  int rv = syscall(__NR_futex,
+                   addr, /* addr1 */
+                   FUTEX_WAKE_BITSET | FUTEX_PRIVATE_FLAG, /* op */
+                   count, /* val */
+                   nullptr, /* timeout */
+                   nullptr, /* addr2 */
+                   wakeMask); /* val3 */
+
+  /* NOTE: we ignore errors on wake for the case of a futex
+     guarding its own destruction, similar to this
+     glibc bug with sem_post/sem_wait:
+     https://sourceware.org/bugzilla/show_bug.cgi?id=12674 */
+  if (rv < 0) {
+    return 0;
+  }
+  return rv;
+}
+
+template <class Clock>
+struct timespec
+timeSpecFromTimePoint(time_point<Clock> absTime)
+{
+  auto epoch = absTime.time_since_epoch();
+  if (epoch.count() < 0) {
+    // kernel timespec_valid requires non-negative seconds and nanos in [0,1G)
+    epoch = Clock::duration::zero();
+  }
+
+  // timespec-safe seconds and nanoseconds;
+  // chrono::{nano,}seconds are `long long int`
+  // whereas timespec uses smaller types
+  using time_t_seconds = duration<std::time_t, seconds::period>;
+  using long_nanos = duration<long int, nanoseconds::period>;
+
+  auto secs = duration_cast<time_t_seconds>(epoch);
+  auto nanos = duration_cast<long_nanos>(epoch - secs);
+  struct timespec result = { secs.count(), nanos.count() };
+  return result;
+}
+
+FutexResult nativeFutexWaitImpl(void* addr,
+                                uint32_t expected,
+                                time_point<system_clock>* absSystemTime,
+                                time_point<steady_clock>* absSteadyTime,
+                                uint32_t waitMask) {
+  assert(absSystemTime == nullptr || absSteadyTime == nullptr);
+
+  int op = FUTEX_WAIT_BITSET | FUTEX_PRIVATE_FLAG;
+  struct timespec ts;
+  struct timespec* timeout = nullptr;
+
+  if (absSystemTime != nullptr) {
+    op |= FUTEX_CLOCK_REALTIME;
+    ts = timeSpecFromTimePoint(*absSystemTime);
+    timeout = &ts;
+  } else if (absSteadyTime != nullptr) {
+    ts = timeSpecFromTimePoint(*absSteadyTime);
+    timeout = &ts;
+  }
 
-namespace folly { namespace detail {
+  // Unlike FUTEX_WAIT, FUTEX_WAIT_BITSET requires an absolute timeout
+  // value - http://locklessinc.com/articles/futex_cheat_sheet/
+  int rv = syscall(__NR_futex,
+                   addr, /* addr1 */
+                   op, /* op */
+                   expected, /* val */
+                   timeout, /* timeout */
+                   nullptr, /* addr2 */
+                   waitMask); /* val3 */
 
-/* see Futex.h */
-FutexResult futexErrnoToFutexResult(int returnVal, int futexErrno) {
-  if (returnVal == 0) {
+  if (rv == 0) {
     return FutexResult::AWOKEN;
+  } else {
+    switch(errno) {
+      case ETIMEDOUT:
+        assert(timeout != nullptr);
+        return FutexResult::TIMEDOUT;
+      case EINTR:
+        return FutexResult::INTERRUPTED;
+      case EWOULDBLOCK:
+        return FutexResult::VALUE_CHANGED;
+      default:
+        assert(false);
+        // EINVAL, EACCESS, or EFAULT.  EINVAL means there was an invalid
+        // op (should be impossible) or an invalid timeout (should have
+        // been sanitized by timeSpecFromTimePoint).  EACCESS or EFAULT
+        // means *addr points to invalid memory, which is unlikely because
+        // the caller should have segfaulted already.  We can either
+        // crash, or return a value that lets the process continue for
+        // a bit. We choose the latter. VALUE_CHANGED probably turns the
+        // caller into a spin lock.
+        return FutexResult::VALUE_CHANGED;
+    }
   }
-  switch(futexErrno) {
-    case ETIMEDOUT:
-      return FutexResult::TIMEDOUT;
-    case EINTR:
-      return FutexResult::INTERRUPTED;
-    case EWOULDBLOCK:
-      return FutexResult::VALUE_CHANGED;
-    default:
-      assert(false);
-      /* Shouldn't reach here. Just return one of the FutexResults */
+}
+
+#endif // __linux__
+
+///////////////////////////////////////////////////////
+// compatibility implementation using standard C++ API
+
+using Lot = ParkingLot<uint32_t>;
+Lot parkingLot;
+
+int emulatedFutexWake(void* addr, int count, uint32_t waitMask) {
+  int woken = 0;
+  parkingLot.unpark(addr, [&](const uint32_t& mask) {
+    if ((mask & waitMask) == 0) {
+      return UnparkControl::RetainContinue;
+    }
+    assert(count > 0);
+    count--;
+    woken++;
+    return count > 0 ? UnparkControl::RemoveContinue
+                     : UnparkControl::RemoveBreak;
+  });
+  return woken;
+}
+
+template <typename F>
+FutexResult emulatedFutexWaitImpl(
+    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;
+    case ParkResult::Unpark:
+      return FutexResult::AWOKEN;
+    case ParkResult::Timeout:
+      return FutexResult::TIMEDOUT;
   }
+
+  return FutexResult::INTERRUPTED;
+}
+
+} // namespace
+
+/////////////////////////////////
+// Futex<> specializations
+
+template <>
+int
+Futex<std::atomic>::futexWake(int count, uint32_t wakeMask) {
+#ifdef __linux__
+  return nativeFutexWake(this, count, wakeMask);
+#else
+  return emulatedFutexWake(this, count, wakeMask);
+#endif
+}
+
+template <>
+int
+Futex<EmulatedFutexAtomic>::futexWake(int count, uint32_t wakeMask) {
+  return emulatedFutexWake(this, count, wakeMask);
+}
+
+template <>
+FutexResult
+Futex<std::atomic>::futexWaitImpl(uint32_t expected,
+                                  time_point<system_clock>* absSystemTime,
+                                  time_point<steady_clock>* absSteadyTime,
+                                  uint32_t waitMask) {
+#ifdef __linux__
+  return nativeFutexWaitImpl(
+      this, expected, absSystemTime, absSteadyTime, waitMask);
+#else
+  return emulatedFutexWaitImpl(
+      this, expected, absSystemTime, absSteadyTime, waitMask);
+#endif
+}
+
+template <>
+FutexResult
+Futex<EmulatedFutexAtomic>::futexWaitImpl(
+        uint32_t expected,
+        time_point<system_clock>* absSystemTime,
+        time_point<steady_clock>* absSteadyTime,
+        uint32_t waitMask) {
+  return emulatedFutexWaitImpl(
+      this, expected, absSystemTime, absSteadyTime, waitMask);
 }
 
-}}
+} // namespace detail
+} // namespace folly