Move folly/LifoSem.h
authorYedidya Feldblum <yfeldblum@fb.com>
Mon, 6 Nov 2017 23:22:31 +0000 (15:22 -0800)
committerFacebook Github Bot <facebook-github-bot@users.noreply.github.com>
Mon, 6 Nov 2017 23:35:45 +0000 (15:35 -0800)
Summary: [Folly] Move `folly/LifoSem.h` to `folly/synchronization/`.

Reviewed By: meyering

Differential Revision: D6245444

fbshipit-source-id: 14ffa012fa92b8c6aaf5900c930156894a492003

12 files changed:
CMakeLists.txt
folly/LifoSem.cpp [deleted file]
folly/LifoSem.h [deleted file]
folly/Makefile.am
folly/executors/ManualExecutor.h
folly/executors/task_queue/LifoSemMPMCQueue.h
folly/executors/task_queue/PriorityLifoSemMPMCQueue.h
folly/executors/task_queue/UnboundedBlockingQueue.h
folly/synchronization/LifoSem.cpp [new file with mode: 0644]
folly/synchronization/LifoSem.h [new file with mode: 0644]
folly/synchronization/test/LifoSemTests.cpp [new file with mode: 0644]
folly/test/LifoSemTests.cpp [deleted file]

index a372161..3715297 100755 (executable)
@@ -505,6 +505,7 @@ if (BUILD_TESTS)
 
     DIRECTORY synchronization/test/
       TEST call_once_test SOURCES CallOnceTest.cpp
+      TEST lifo_sem_test SOURCES LifoSemTests.cpp
 
     DIRECTORY system/test/
       TEST memory_mapping_test SOURCES MemoryMappingTest.cpp
@@ -569,7 +570,6 @@ if (BUILD_TESTS)
         SOURCES
           JsonOtherTest.cpp
       TEST lazy_test SOURCES LazyTest.cpp
-      TEST lifosem_test SOURCES LifoSemTests.cpp
       TEST lock_traits_test SOURCES LockTraitsTest.cpp
       TEST locks_test SOURCES SmallLocksTest.cpp SpinLockTest.cpp
       TEST logging_test SOURCES LoggingTest.cpp
diff --git a/folly/LifoSem.cpp b/folly/LifoSem.cpp
deleted file mode 100644 (file)
index d3fa506..0000000
+++ /dev/null
@@ -1,40 +0,0 @@
-/*
- * Copyright 2017 Facebook, Inc.
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- *   http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-#include <folly/LifoSem.h>
-
-/// Raw node storage is preallocated in a contiguous memory segment,
-/// but we use an anonymous mmap so the physical memory used (RSS) will
-/// only reflect the maximum number of waiters that actually existed
-/// concurrently.  For blocked threads the max node count is limited by the
-/// number of threads, so we can conservatively estimate that this will be
-/// < 10k.  For LifoEventSem, however, we could potentially have many more.
-///
-/// On a 64-bit architecture each LifoSemRawNode takes 16 bytes.  We make
-/// the pool 1 million entries.
-
-LIFOSEM_DECLARE_POOL(std::atomic, 1000000)
-
-namespace folly {
-
-ShutdownSemError::ShutdownSemError(const std::string& msg)
-  : std::runtime_error(msg)
-{}
-
-ShutdownSemError::~ShutdownSemError() noexcept {
-}
-
-} // namespace folly
diff --git a/folly/LifoSem.h b/folly/LifoSem.h
deleted file mode 100644 (file)
index 9017609..0000000
+++ /dev/null
@@ -1,600 +0,0 @@
-/*
- * Copyright 2017 Facebook, Inc.
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- *   http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-#pragma once
-
-#include <algorithm>
-#include <atomic>
-#include <cstdint>
-#include <cstring>
-#include <memory>
-#include <system_error>
-
-#include <folly/AtomicStruct.h>
-#include <folly/Baton.h>
-#include <folly/CachelinePadded.h>
-#include <folly/IndexedMemPool.h>
-#include <folly/Likely.h>
-
-namespace folly {
-
-template <
-    template <typename> class Atom = std::atomic,
-    class BatonType = Baton<Atom>>
-struct LifoSemImpl;
-
-/// LifoSem is a semaphore that wakes its waiters in a manner intended to
-/// maximize performance rather than fairness.  It should be preferred
-/// to a mutex+condvar or POSIX sem_t solution when all of the waiters
-/// are equivalent.  It is faster than a condvar or sem_t, and it has a
-/// shutdown state that might save you a lot of complexity when it comes
-/// time to shut down your work pipelines.  LifoSem is larger than sem_t,
-/// but that is only because it uses padding and alignment to avoid
-/// false sharing.
-///
-/// LifoSem allows multi-post and multi-tryWait, and provides a shutdown
-/// state that awakens all waiters.  LifoSem is faster than sem_t because
-/// it performs exact wakeups, so it often requires fewer system calls.
-/// It provides all of the functionality of sem_t except for timed waiting.
-/// It is called LifoSem because its wakeup policy is approximately LIFO,
-/// rather than the usual FIFO.
-///
-/// The core semaphore operations provided are:
-///
-/// -- post() -- if there is a pending waiter, wake it up, otherwise
-/// increment the value of the semaphore.  If the value of the semaphore
-/// is already 2^32-1, does nothing.  Compare to sem_post().
-///
-/// -- post(n) -- equivalent to n calls to post(), but much more efficient.
-/// sem_t has no equivalent to this method.
-///
-/// -- bool tryWait() -- if the semaphore's value is positive, decrements it
-/// and returns true, otherwise returns false.  Compare to sem_trywait().
-///
-/// -- uint32_t tryWait(uint32_t n) -- attempts to decrement the semaphore's
-/// value by n, returning the amount by which it actually was decremented
-/// (a value from 0 to n inclusive).  Not atomic.  Equivalent to n calls
-/// to tryWait().  sem_t has no equivalent to this method.
-///
-/// -- wait() -- waits until tryWait() can succeed.  Compare to sem_wait().
-///
-/// LifoSem also has the notion of a shutdown state, in which any calls
-/// that would block (or are already blocked) throw ShutdownSemError.
-/// Note the difference between a call to wait() and a call to wait()
-/// that might block.  In the former case tryWait() would succeed, and no
-/// isShutdown() check is performed.  In the latter case an exception is
-/// thrown.  This behavior allows a LifoSem controlling work distribution
-/// to drain.  If you want to immediately stop all waiting on shutdown,
-/// you can just check isShutdown() yourself (preferrably wrapped in
-/// an UNLIKELY).  This fast-stop behavior is easy to add, but difficult
-/// to remove if you want the draining behavior, which is why we have
-/// chosen the former.  Since wait() is the only method that can block,
-/// it is the only one that is affected by the shutdown state.
-///
-/// All LifoSem operations operations except valueGuess() are guaranteed
-/// to be linearizable.
-typedef LifoSemImpl<> LifoSem;
-
-
-/// The exception thrown when wait()ing on an isShutdown() LifoSem
-struct ShutdownSemError : public std::runtime_error {
-  explicit ShutdownSemError(const std::string& msg);
-  ~ShutdownSemError() noexcept override;
-};
-
-namespace detail {
-
-// Internally, a LifoSem is either a value or a linked list of wait nodes.
-// This union is captured in the LifoSemHead type, which holds either a
-// value or an indexed pointer to the list.  LifoSemHead itself is a value
-// type, the head is a mutable atomic box containing a LifoSemHead value.
-// Each wait node corresponds to exactly one waiter.  Values can flow
-// through the semaphore either by going into and out of the head's value,
-// or by direct communication from a poster to a waiter.  The former path
-// is taken when there are no pending waiters, the latter otherwise.  The
-// general flow of a post is to try to increment the value or pop-and-post
-// a wait node.  Either of those have the effect of conveying one semaphore
-// unit.  Waiting is the opposite, either a decrement of the value or
-// push-and-wait of a wait node.  The generic LifoSemBase abstracts the
-// actual mechanism by which a wait node's post->wait communication is
-// performed, which is why we have LifoSemRawNode and LifoSemNode.
-
-/// LifoSemRawNode is the actual pooled storage that backs LifoSemNode
-/// for user-specified Handoff types.  This is done so that we can have
-/// a large static IndexedMemPool of nodes, instead of per-type pools
-template <template <typename> class Atom>
-struct LifoSemRawNode {
-  std::aligned_storage<sizeof(void*),alignof(void*)>::type raw;
-
-  /// The IndexedMemPool index of the next node in this chain, or 0
-  /// if none.  This will be set to uint32_t(-1) if the node is being
-  /// posted due to a shutdown-induced wakeup
-  uint32_t next;
-
-  bool isShutdownNotice() const { return next == uint32_t(-1); }
-  void clearShutdownNotice() { next = 0; }
-  void setShutdownNotice() { next = uint32_t(-1); }
-
-  typedef folly::IndexedMemPool<LifoSemRawNode<Atom>,32,200,Atom> Pool;
-
-  /// Storage for all of the waiter nodes for LifoSem-s that use Atom
-  static Pool& pool();
-};
-
-/// Use this macro to declare the static storage that backs the raw nodes
-/// for the specified atomic type
-#define LIFOSEM_DECLARE_POOL(Atom, capacity)                 \
-  namespace folly {                                          \
-  namespace detail {                                         \
-  template <>                                                \
-  LifoSemRawNode<Atom>::Pool& LifoSemRawNode<Atom>::pool() { \
-    static Pool* instance = new Pool((capacity));            \
-    return *instance;                                        \
-  }                                                          \
-  }                                                          \
-  }
-
-/// Handoff is a type not bigger than a void* that knows how to perform a
-/// single post() -> wait() communication.  It must have a post() method.
-/// If it has a wait() method then LifoSemBase's wait() implementation
-/// will work out of the box, otherwise you will need to specialize
-/// LifoSemBase::wait accordingly.
-template <typename Handoff, template <typename> class Atom>
-struct LifoSemNode : public LifoSemRawNode<Atom> {
-
-  static_assert(sizeof(Handoff) <= sizeof(LifoSemRawNode<Atom>::raw),
-      "Handoff too big for small-object optimization, use indirection");
-  static_assert(alignof(Handoff) <=
-                alignof(decltype(LifoSemRawNode<Atom>::raw)),
-      "Handoff alignment constraint not satisfied");
-
-  template <typename ...Args>
-  void init(Args&&... args) {
-    new (&this->raw) Handoff(std::forward<Args>(args)...);
-  }
-
-  void destroy() {
-    handoff().~Handoff();
-#ifndef NDEBUG
-    memset(&this->raw, 'F', sizeof(this->raw));
-#endif
-  }
-
-  Handoff& handoff() {
-    return *static_cast<Handoff*>(static_cast<void*>(&this->raw));
-  }
-
-  const Handoff& handoff() const {
-    return *static_cast<const Handoff*>(static_cast<const void*>(&this->raw));
-  }
-};
-
-template <typename Handoff, template <typename> class Atom>
-struct LifoSemNodeRecycler {
-  void operator()(LifoSemNode<Handoff,Atom>* elem) const {
-    elem->destroy();
-    auto idx = LifoSemRawNode<Atom>::pool().locateElem(elem);
-    LifoSemRawNode<Atom>::pool().recycleIndex(idx);
-  }
-};
-
-/// LifoSemHead is a 64-bit struct that holds a 32-bit value, some state
-/// bits, and a sequence number used to avoid ABA problems in the lock-free
-/// management of the LifoSem's wait lists.  The value can either hold
-/// an integral semaphore value (if there are no waiters) or a node index
-/// (see IndexedMemPool) for the head of a list of wait nodes
-class LifoSemHead {
-  // What we really want are bitfields:
-  //  uint64_t data : 32; uint64_t isNodeIdx : 1; uint64_t seq : 31;
-  // Unfortunately g++ generates pretty bad code for this sometimes (I saw
-  // -O3 code from gcc 4.7.1 copying the bitfields one at a time instead of
-  // in bulk, for example).  We can generate better code anyway by assuming
-  // that setters won't be given values that cause under/overflow, and
-  // putting the sequence at the end where its planned overflow doesn't
-  // need any masking.
-  //
-  // data == 0 (empty list) with isNodeIdx is conceptually the same
-  // as data == 0 (no unclaimed increments) with !isNodeIdx, we always
-  // convert the former into the latter to make the logic simpler.
-  enum {
-    IsNodeIdxShift = 32,
-    IsShutdownShift = 33,
-    SeqShift = 34,
-  };
-  enum : uint64_t {
-    IsNodeIdxMask = uint64_t(1) << IsNodeIdxShift,
-    IsShutdownMask = uint64_t(1) << IsShutdownShift,
-    SeqIncr = uint64_t(1) << SeqShift,
-    SeqMask = ~(SeqIncr - 1),
-  };
-
- public:
-
-  uint64_t bits;
-
-  //////// getters
-
-  inline uint32_t idx() const {
-    assert(isNodeIdx());
-    assert(uint32_t(bits) != 0);
-    return uint32_t(bits);
-  }
-  inline uint32_t value() const {
-    assert(!isNodeIdx());
-    return uint32_t(bits);
-  }
-  inline constexpr bool isNodeIdx() const {
-    return (bits & IsNodeIdxMask) != 0;
-  }
-  inline constexpr bool isShutdown() const {
-    return (bits & IsShutdownMask) != 0;
-  }
-  inline constexpr uint32_t seq() const {
-    return uint32_t(bits >> SeqShift);
-  }
-
-  //////// setter-like things return a new struct
-
-  /// This should only be used for initial construction, not for setting
-  /// the value, because it clears the sequence number
-  static inline constexpr LifoSemHead fresh(uint32_t value) {
-    return LifoSemHead{ value };
-  }
-
-  /// Returns the LifoSemHead that results from popping a waiter node,
-  /// given the current waiter node's next ptr
-  inline LifoSemHead withPop(uint32_t idxNext) const {
-    assert(isNodeIdx());
-    if (idxNext == 0) {
-      // no isNodeIdx bit or data bits.  Wraparound of seq bits is okay
-      return LifoSemHead{ (bits & (SeqMask | IsShutdownMask)) + SeqIncr };
-    } else {
-      // preserve sequence bits (incremented with wraparound okay) and
-      // isNodeIdx bit, replace all data bits
-      return LifoSemHead{
-          (bits & (SeqMask | IsShutdownMask | IsNodeIdxMask)) +
-          SeqIncr + idxNext };
-    }
-  }
-
-  /// Returns the LifoSemHead that results from pushing a new waiter node
-  inline LifoSemHead withPush(uint32_t _idx) const {
-    assert(isNodeIdx() || value() == 0);
-    assert(!isShutdown());
-    assert(_idx != 0);
-    return LifoSemHead{ (bits & SeqMask) | IsNodeIdxMask | _idx };
-  }
-
-  /// Returns the LifoSemHead with value increased by delta, with
-  /// saturation if the maximum value is reached
-  inline LifoSemHead withValueIncr(uint32_t delta) const {
-    assert(!isNodeIdx());
-    auto rv = LifoSemHead{ bits + SeqIncr + delta };
-    if (UNLIKELY(rv.isNodeIdx())) {
-      // value has overflowed into the isNodeIdx bit
-      rv = LifoSemHead{ (rv.bits & ~IsNodeIdxMask) | (IsNodeIdxMask - 1) };
-    }
-    return rv;
-  }
-
-  /// Returns the LifoSemHead that results from decrementing the value
-  inline LifoSemHead withValueDecr(uint32_t delta) const {
-    assert(delta > 0 && delta <= value());
-    return LifoSemHead{ bits + SeqIncr - delta };
-  }
-
-  /// Returns the LifoSemHead with the same state as the current node,
-  /// but with the shutdown bit set
-  inline LifoSemHead withShutdown() const {
-    return LifoSemHead{ bits | IsShutdownMask };
-  }
-
-  inline constexpr bool operator== (const LifoSemHead& rhs) const {
-    return bits == rhs.bits;
-  }
-  inline constexpr bool operator!= (const LifoSemHead& rhs) const {
-    return !(*this == rhs);
-  }
-};
-
-/// LifoSemBase is the engine for several different types of LIFO
-/// semaphore.  LifoSemBase handles storage of positive semaphore values
-/// and wait nodes, but the actual waiting and notification mechanism is
-/// up to the client.
-///
-/// The Handoff type is responsible for arranging one wakeup notification.
-/// See LifoSemNode for more information on how to make your own.
-template <typename Handoff, template <typename> class Atom = std::atomic>
-struct LifoSemBase {
-
-  /// Constructor
-  constexpr explicit LifoSemBase(uint32_t initialValue = 0)
-      : head_(LifoSemHead::fresh(initialValue)) {}
-
-  LifoSemBase(LifoSemBase const&) = delete;
-  LifoSemBase& operator=(LifoSemBase const&) = delete;
-
-  /// Silently saturates if value is already 2^32-1
-  void post() {
-    auto idx = incrOrPop(1);
-    if (idx != 0) {
-      idxToNode(idx).handoff().post();
-    }
-  }
-
-  /// Equivalent to n calls to post(), except may be much more efficient.
-  /// At any point in time at which the semaphore's value would exceed
-  /// 2^32-1 if tracked with infinite precision, it may be silently
-  /// truncated to 2^32-1.  This saturation is not guaranteed to be exact,
-  /// although it is guaranteed that overflow won't result in wrap-around.
-  /// There would be a substantial performance and complexity cost in
-  /// guaranteeing exact saturation (similar to the cost of maintaining
-  /// linearizability near the zero value, but without as much of
-  /// a benefit).
-  void post(uint32_t n) {
-    uint32_t idx;
-    while (n > 0 && (idx = incrOrPop(n)) != 0) {
-      // pop accounts for only 1
-      idxToNode(idx).handoff().post();
-      --n;
-    }
-  }
-
-  /// Returns true iff shutdown() has been called
-  bool isShutdown() const {
-    return UNLIKELY(head_->load(std::memory_order_acquire).isShutdown());
-  }
-
-  /// Prevents blocking on this semaphore, causing all blocking wait()
-  /// calls to throw ShutdownSemError.  Both currently blocked wait() and
-  /// future calls to wait() for which tryWait() would return false will
-  /// cause an exception.  Calls to wait() for which the matching post()
-  /// has already occurred will proceed normally.
-  void shutdown() {
-    // first set the shutdown bit
-    auto h = head_->load(std::memory_order_acquire);
-    while (!h.isShutdown()) {
-      if (head_->compare_exchange_strong(h, h.withShutdown())) {
-        // success
-        h = h.withShutdown();
-        break;
-      }
-      // compare_exchange_strong rereads h, retry
-    }
-
-    // now wake up any waiters
-    while (h.isNodeIdx()) {
-      auto& node = idxToNode(h.idx());
-      auto repl = h.withPop(node.next);
-      if (head_->compare_exchange_strong(h, repl)) {
-        // successful pop, wake up the waiter and move on.  The next
-        // field is used to convey that this wakeup didn't consume a value
-        node.setShutdownNotice();
-        node.handoff().post();
-        h = repl;
-      }
-    }
-  }
-
-  /// Returns true iff value was decremented
-  bool tryWait() {
-    uint32_t n = 1;
-    auto rv = decrOrPush(n, 0);
-    assert((rv == WaitResult::DECR && n == 0) ||
-           (rv != WaitResult::DECR && n == 1));
-    // SHUTDOWN is okay here, since we don't actually wait
-    return rv == WaitResult::DECR;
-  }
-
-  /// Equivalent to (but may be much more efficient than) n calls to
-  /// tryWait().  Returns the total amount by which the semaphore's value
-  /// was decreased
-  uint32_t tryWait(uint32_t n) {
-    auto const orig = n;
-    while (n > 0) {
-#ifndef NDEBUG
-      auto prev = n;
-#endif
-      auto rv = decrOrPush(n, 0);
-      assert((rv == WaitResult::DECR && n < prev) ||
-             (rv != WaitResult::DECR && n == prev));
-      if (rv != WaitResult::DECR) {
-        break;
-      }
-    }
-    return orig - n;
-  }
-
-  /// Blocks the current thread until there is a matching post or the
-  /// semaphore is shut down.  Throws ShutdownSemError if the semaphore
-  /// has been shut down and this method would otherwise be blocking.
-  /// Note that wait() doesn't throw during shutdown if tryWait() would
-  /// return true
-  void wait() {
-    // early check isn't required for correctness, but is an important
-    // perf win if we can avoid allocating and deallocating a node
-    if (tryWait()) {
-      return;
-    }
-
-    // allocateNode() won't compile unless Handoff has a default
-    // constructor
-    UniquePtr node = allocateNode();
-
-    auto rv = tryWaitOrPush(*node);
-    if (UNLIKELY(rv == WaitResult::SHUTDOWN)) {
-      assert(isShutdown());
-      throw ShutdownSemError("wait() would block but semaphore is shut down");
-    }
-
-    if (rv == WaitResult::PUSH) {
-      node->handoff().wait();
-      if (UNLIKELY(node->isShutdownNotice())) {
-        // this wait() didn't consume a value, it was triggered by shutdown
-        assert(isShutdown());
-        throw ShutdownSemError(
-            "blocking wait() interrupted by semaphore shutdown");
-      }
-
-      // node->handoff().wait() can't return until after the node has
-      // been popped and post()ed, so it is okay for the UniquePtr to
-      // recycle the node now
-    }
-    // else node wasn't pushed, so it is safe to recycle
-  }
-
-  /// Returns a guess at the current value, designed for debugging.
-  /// If there are no concurrent posters or waiters then this will
-  /// be correct
-  uint32_t valueGuess() const {
-    // this is actually linearizable, but we don't promise that because
-    // we may want to add striping in the future to help under heavy
-    // contention
-    auto h = head_->load(std::memory_order_acquire);
-    return h.isNodeIdx() ? 0 : h.value();
-  }
-
- protected:
-
-  enum class WaitResult {
-    PUSH,
-    DECR,
-    SHUTDOWN,
-  };
-
-  /// The type of a std::unique_ptr that will automatically return a
-  /// LifoSemNode to the appropriate IndexedMemPool
-  typedef std::unique_ptr<LifoSemNode<Handoff, Atom>,
-                          LifoSemNodeRecycler<Handoff, Atom>> UniquePtr;
-
-  /// Returns a node that can be passed to decrOrLink
-  template <typename... Args>
-  UniquePtr allocateNode(Args&&... args) {
-    auto idx = LifoSemRawNode<Atom>::pool().allocIndex();
-    if (idx != 0) {
-      auto& node = idxToNode(idx);
-      node.clearShutdownNotice();
-      try {
-        node.init(std::forward<Args>(args)...);
-      } catch (...) {
-        LifoSemRawNode<Atom>::pool().recycleIndex(idx);
-        throw;
-      }
-      return UniquePtr(&node);
-    } else {
-      return UniquePtr();
-    }
-  }
-
-  /// Returns DECR if the semaphore value was decremented (and waiterNode
-  /// was untouched), PUSH if a reference to the wait node was pushed,
-  /// or SHUTDOWN if decrement was not possible and push wasn't allowed
-  /// because isShutdown().  Ownership of the wait node remains the
-  /// responsibility of the caller, who must not release it until after
-  /// the node's Handoff has been posted.
-  WaitResult tryWaitOrPush(LifoSemNode<Handoff, Atom>& waiterNode) {
-    uint32_t n = 1;
-    return decrOrPush(n, nodeToIdx(waiterNode));
-  }
-
- private:
-  CachelinePadded<folly::AtomicStruct<LifoSemHead, Atom>> head_;
-
-  static LifoSemNode<Handoff, Atom>& idxToNode(uint32_t idx) {
-    auto raw = &LifoSemRawNode<Atom>::pool()[idx];
-    return *static_cast<LifoSemNode<Handoff, Atom>*>(raw);
-  }
-
-  static uint32_t nodeToIdx(const LifoSemNode<Handoff, Atom>& node) {
-    return LifoSemRawNode<Atom>::pool().locateElem(&node);
-  }
-
-  /// Either increments by n and returns 0, or pops a node and returns it.
-  /// If n + the stripe's value overflows, then the stripe's value
-  /// saturates silently at 2^32-1
-  uint32_t incrOrPop(uint32_t n) {
-    while (true) {
-      assert(n > 0);
-
-      auto head = head_->load(std::memory_order_acquire);
-      if (head.isNodeIdx()) {
-        auto& node = idxToNode(head.idx());
-        if (head_->compare_exchange_strong(head, head.withPop(node.next))) {
-          // successful pop
-          return head.idx();
-        }
-      } else {
-        auto after = head.withValueIncr(n);
-        if (head_->compare_exchange_strong(head, after)) {
-          // successful incr
-          return 0;
-        }
-      }
-      // retry
-    }
-  }
-
-  /// Returns DECR if some amount was decremented, with that amount
-  /// subtracted from n.  If n is 1 and this function returns DECR then n
-  /// must be 0 afterward.  Returns PUSH if no value could be decremented
-  /// and idx was pushed, or if idx was zero and no push was performed but
-  /// a push would have been performed with a valid node.  Returns SHUTDOWN
-  /// if the caller should have blocked but isShutdown().  If idx == 0,
-  /// may return PUSH even after isShutdown() or may return SHUTDOWN
-  WaitResult decrOrPush(uint32_t& n, uint32_t idx) {
-    assert(n > 0);
-
-    while (true) {
-      auto head = head_->load(std::memory_order_acquire);
-
-      if (!head.isNodeIdx() && head.value() > 0) {
-        // decr
-        auto delta = std::min(n, head.value());
-        if (head_->compare_exchange_strong(head, head.withValueDecr(delta))) {
-          n -= delta;
-          return WaitResult::DECR;
-        }
-      } else {
-        // push
-        if (idx == 0) {
-          return WaitResult::PUSH;
-        }
-
-        if (UNLIKELY(head.isShutdown())) {
-          return WaitResult::SHUTDOWN;
-        }
-
-        auto& node = idxToNode(idx);
-        node.next = head.isNodeIdx() ? head.idx() : 0;
-        if (head_->compare_exchange_strong(head, head.withPush(idx))) {
-          // push succeeded
-          return WaitResult::PUSH;
-        }
-      }
-    }
-    // retry
-  }
-};
-
-} // namespace detail
-
-template <template <typename> class Atom, class BatonType>
-struct LifoSemImpl : public detail::LifoSemBase<BatonType, Atom> {
-  constexpr explicit LifoSemImpl(uint32_t v = 0)
-    : detail::LifoSemBase<BatonType, Atom>(v) {}
-};
-
-} // namespace folly
index 37f95d1..422b7bb 100644 (file)
@@ -317,7 +317,6 @@ nobase_follyinclude_HEADERS = \
        lang/RValueReferenceWrapper.h \
        lang/SafeAssert.h \
        Lazy.h \
-       LifoSem.h \
        Likely.h \
        LockTraits.h \
        LockTraitsBoost.h \
@@ -424,6 +423,7 @@ nobase_follyinclude_HEADERS = \
        stats/TimeseriesHistogram.h \
        synchronization/AsymmetricMemoryBarrier.h \
        synchronization/CallOnce.h \
+       synchronization/LifoSem.h \
        synchronization/detail/AtomicUtils.h \
        system/MemoryMapping.h \
        system/Shell.h \
@@ -533,7 +533,6 @@ libfolly_la_SOURCES = \
        IPAddress.cpp \
        IPAddressV4.cpp \
        IPAddressV6.cpp \
-       LifoSem.cpp \
        init/Init.cpp \
        io/Cursor.cpp \
        io/IOBuf.cpp \
@@ -609,6 +608,7 @@ libfolly_la_SOURCES = \
        stats/MultiLevelTimeSeries.cpp \
        stats/TimeseriesHistogram.cpp \
        synchronization/AsymmetricMemoryBarrier.cpp \
+       synchronization/LifoSem.cpp \
        system/MemoryMapping.cpp \
        system/Shell.cpp \
        system/ThreadName.cpp \
index 9f06016..bad7d96 100644 (file)
@@ -21,9 +21,9 @@
 #include <mutex>
 #include <queue>
 
-#include <folly/LifoSem.h>
 #include <folly/executors/DrivableExecutor.h>
 #include <folly/executors/ScheduledExecutor.h>
+#include <folly/synchronization/LifoSem.h>
 
 namespace folly {
   /// A ManualExecutor only does work when you turn the crank, by calling
index 68a8606..96ec8e9 100644 (file)
@@ -16,9 +16,9 @@
 
 #pragma once
 
-#include <folly/LifoSem.h>
 #include <folly/MPMCQueue.h>
 #include <folly/executors/task_queue/BlockingQueue.h>
+#include <folly/synchronization/LifoSem.h>
 
 namespace folly {
 
index 3242628..ab9d12e 100644 (file)
@@ -17,9 +17,9 @@
 #pragma once
 
 #include <folly/Executor.h>
-#include <folly/LifoSem.h>
 #include <folly/MPMCQueue.h>
 #include <folly/executors/task_queue/BlockingQueue.h>
+#include <folly/synchronization/LifoSem.h>
 
 namespace folly {
 
index 2f29fbf..8fc8391 100644 (file)
@@ -16,9 +16,9 @@
 
 #pragma once
 
-#include <folly/LifoSem.h>
 #include <folly/Synchronized.h>
 #include <folly/executors/task_queue/BlockingQueue.h>
+#include <folly/synchronization/LifoSem.h>
 #include <queue>
 
 namespace folly {
diff --git a/folly/synchronization/LifoSem.cpp b/folly/synchronization/LifoSem.cpp
new file mode 100644 (file)
index 0000000..0cf5b48
--- /dev/null
@@ -0,0 +1,40 @@
+/*
+ * Copyright 2017 Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <folly/synchronization/LifoSem.h>
+
+/// Raw node storage is preallocated in a contiguous memory segment,
+/// but we use an anonymous mmap so the physical memory used (RSS) will
+/// only reflect the maximum number of waiters that actually existed
+/// concurrently.  For blocked threads the max node count is limited by the
+/// number of threads, so we can conservatively estimate that this will be
+/// < 10k.  For LifoEventSem, however, we could potentially have many more.
+///
+/// On a 64-bit architecture each LifoSemRawNode takes 16 bytes.  We make
+/// the pool 1 million entries.
+
+LIFOSEM_DECLARE_POOL(std::atomic, 1000000)
+
+namespace folly {
+
+ShutdownSemError::ShutdownSemError(const std::string& msg)
+  : std::runtime_error(msg)
+{}
+
+ShutdownSemError::~ShutdownSemError() noexcept {
+}
+
+} // namespace folly
diff --git a/folly/synchronization/LifoSem.h b/folly/synchronization/LifoSem.h
new file mode 100644 (file)
index 0000000..9017609
--- /dev/null
@@ -0,0 +1,600 @@
+/*
+ * Copyright 2017 Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#pragma once
+
+#include <algorithm>
+#include <atomic>
+#include <cstdint>
+#include <cstring>
+#include <memory>
+#include <system_error>
+
+#include <folly/AtomicStruct.h>
+#include <folly/Baton.h>
+#include <folly/CachelinePadded.h>
+#include <folly/IndexedMemPool.h>
+#include <folly/Likely.h>
+
+namespace folly {
+
+template <
+    template <typename> class Atom = std::atomic,
+    class BatonType = Baton<Atom>>
+struct LifoSemImpl;
+
+/// LifoSem is a semaphore that wakes its waiters in a manner intended to
+/// maximize performance rather than fairness.  It should be preferred
+/// to a mutex+condvar or POSIX sem_t solution when all of the waiters
+/// are equivalent.  It is faster than a condvar or sem_t, and it has a
+/// shutdown state that might save you a lot of complexity when it comes
+/// time to shut down your work pipelines.  LifoSem is larger than sem_t,
+/// but that is only because it uses padding and alignment to avoid
+/// false sharing.
+///
+/// LifoSem allows multi-post and multi-tryWait, and provides a shutdown
+/// state that awakens all waiters.  LifoSem is faster than sem_t because
+/// it performs exact wakeups, so it often requires fewer system calls.
+/// It provides all of the functionality of sem_t except for timed waiting.
+/// It is called LifoSem because its wakeup policy is approximately LIFO,
+/// rather than the usual FIFO.
+///
+/// The core semaphore operations provided are:
+///
+/// -- post() -- if there is a pending waiter, wake it up, otherwise
+/// increment the value of the semaphore.  If the value of the semaphore
+/// is already 2^32-1, does nothing.  Compare to sem_post().
+///
+/// -- post(n) -- equivalent to n calls to post(), but much more efficient.
+/// sem_t has no equivalent to this method.
+///
+/// -- bool tryWait() -- if the semaphore's value is positive, decrements it
+/// and returns true, otherwise returns false.  Compare to sem_trywait().
+///
+/// -- uint32_t tryWait(uint32_t n) -- attempts to decrement the semaphore's
+/// value by n, returning the amount by which it actually was decremented
+/// (a value from 0 to n inclusive).  Not atomic.  Equivalent to n calls
+/// to tryWait().  sem_t has no equivalent to this method.
+///
+/// -- wait() -- waits until tryWait() can succeed.  Compare to sem_wait().
+///
+/// LifoSem also has the notion of a shutdown state, in which any calls
+/// that would block (or are already blocked) throw ShutdownSemError.
+/// Note the difference between a call to wait() and a call to wait()
+/// that might block.  In the former case tryWait() would succeed, and no
+/// isShutdown() check is performed.  In the latter case an exception is
+/// thrown.  This behavior allows a LifoSem controlling work distribution
+/// to drain.  If you want to immediately stop all waiting on shutdown,
+/// you can just check isShutdown() yourself (preferrably wrapped in
+/// an UNLIKELY).  This fast-stop behavior is easy to add, but difficult
+/// to remove if you want the draining behavior, which is why we have
+/// chosen the former.  Since wait() is the only method that can block,
+/// it is the only one that is affected by the shutdown state.
+///
+/// All LifoSem operations operations except valueGuess() are guaranteed
+/// to be linearizable.
+typedef LifoSemImpl<> LifoSem;
+
+
+/// The exception thrown when wait()ing on an isShutdown() LifoSem
+struct ShutdownSemError : public std::runtime_error {
+  explicit ShutdownSemError(const std::string& msg);
+  ~ShutdownSemError() noexcept override;
+};
+
+namespace detail {
+
+// Internally, a LifoSem is either a value or a linked list of wait nodes.
+// This union is captured in the LifoSemHead type, which holds either a
+// value or an indexed pointer to the list.  LifoSemHead itself is a value
+// type, the head is a mutable atomic box containing a LifoSemHead value.
+// Each wait node corresponds to exactly one waiter.  Values can flow
+// through the semaphore either by going into and out of the head's value,
+// or by direct communication from a poster to a waiter.  The former path
+// is taken when there are no pending waiters, the latter otherwise.  The
+// general flow of a post is to try to increment the value or pop-and-post
+// a wait node.  Either of those have the effect of conveying one semaphore
+// unit.  Waiting is the opposite, either a decrement of the value or
+// push-and-wait of a wait node.  The generic LifoSemBase abstracts the
+// actual mechanism by which a wait node's post->wait communication is
+// performed, which is why we have LifoSemRawNode and LifoSemNode.
+
+/// LifoSemRawNode is the actual pooled storage that backs LifoSemNode
+/// for user-specified Handoff types.  This is done so that we can have
+/// a large static IndexedMemPool of nodes, instead of per-type pools
+template <template <typename> class Atom>
+struct LifoSemRawNode {
+  std::aligned_storage<sizeof(void*),alignof(void*)>::type raw;
+
+  /// The IndexedMemPool index of the next node in this chain, or 0
+  /// if none.  This will be set to uint32_t(-1) if the node is being
+  /// posted due to a shutdown-induced wakeup
+  uint32_t next;
+
+  bool isShutdownNotice() const { return next == uint32_t(-1); }
+  void clearShutdownNotice() { next = 0; }
+  void setShutdownNotice() { next = uint32_t(-1); }
+
+  typedef folly::IndexedMemPool<LifoSemRawNode<Atom>,32,200,Atom> Pool;
+
+  /// Storage for all of the waiter nodes for LifoSem-s that use Atom
+  static Pool& pool();
+};
+
+/// Use this macro to declare the static storage that backs the raw nodes
+/// for the specified atomic type
+#define LIFOSEM_DECLARE_POOL(Atom, capacity)                 \
+  namespace folly {                                          \
+  namespace detail {                                         \
+  template <>                                                \
+  LifoSemRawNode<Atom>::Pool& LifoSemRawNode<Atom>::pool() { \
+    static Pool* instance = new Pool((capacity));            \
+    return *instance;                                        \
+  }                                                          \
+  }                                                          \
+  }
+
+/// Handoff is a type not bigger than a void* that knows how to perform a
+/// single post() -> wait() communication.  It must have a post() method.
+/// If it has a wait() method then LifoSemBase's wait() implementation
+/// will work out of the box, otherwise you will need to specialize
+/// LifoSemBase::wait accordingly.
+template <typename Handoff, template <typename> class Atom>
+struct LifoSemNode : public LifoSemRawNode<Atom> {
+
+  static_assert(sizeof(Handoff) <= sizeof(LifoSemRawNode<Atom>::raw),
+      "Handoff too big for small-object optimization, use indirection");
+  static_assert(alignof(Handoff) <=
+                alignof(decltype(LifoSemRawNode<Atom>::raw)),
+      "Handoff alignment constraint not satisfied");
+
+  template <typename ...Args>
+  void init(Args&&... args) {
+    new (&this->raw) Handoff(std::forward<Args>(args)...);
+  }
+
+  void destroy() {
+    handoff().~Handoff();
+#ifndef NDEBUG
+    memset(&this->raw, 'F', sizeof(this->raw));
+#endif
+  }
+
+  Handoff& handoff() {
+    return *static_cast<Handoff*>(static_cast<void*>(&this->raw));
+  }
+
+  const Handoff& handoff() const {
+    return *static_cast<const Handoff*>(static_cast<const void*>(&this->raw));
+  }
+};
+
+template <typename Handoff, template <typename> class Atom>
+struct LifoSemNodeRecycler {
+  void operator()(LifoSemNode<Handoff,Atom>* elem) const {
+    elem->destroy();
+    auto idx = LifoSemRawNode<Atom>::pool().locateElem(elem);
+    LifoSemRawNode<Atom>::pool().recycleIndex(idx);
+  }
+};
+
+/// LifoSemHead is a 64-bit struct that holds a 32-bit value, some state
+/// bits, and a sequence number used to avoid ABA problems in the lock-free
+/// management of the LifoSem's wait lists.  The value can either hold
+/// an integral semaphore value (if there are no waiters) or a node index
+/// (see IndexedMemPool) for the head of a list of wait nodes
+class LifoSemHead {
+  // What we really want are bitfields:
+  //  uint64_t data : 32; uint64_t isNodeIdx : 1; uint64_t seq : 31;
+  // Unfortunately g++ generates pretty bad code for this sometimes (I saw
+  // -O3 code from gcc 4.7.1 copying the bitfields one at a time instead of
+  // in bulk, for example).  We can generate better code anyway by assuming
+  // that setters won't be given values that cause under/overflow, and
+  // putting the sequence at the end where its planned overflow doesn't
+  // need any masking.
+  //
+  // data == 0 (empty list) with isNodeIdx is conceptually the same
+  // as data == 0 (no unclaimed increments) with !isNodeIdx, we always
+  // convert the former into the latter to make the logic simpler.
+  enum {
+    IsNodeIdxShift = 32,
+    IsShutdownShift = 33,
+    SeqShift = 34,
+  };
+  enum : uint64_t {
+    IsNodeIdxMask = uint64_t(1) << IsNodeIdxShift,
+    IsShutdownMask = uint64_t(1) << IsShutdownShift,
+    SeqIncr = uint64_t(1) << SeqShift,
+    SeqMask = ~(SeqIncr - 1),
+  };
+
+ public:
+
+  uint64_t bits;
+
+  //////// getters
+
+  inline uint32_t idx() const {
+    assert(isNodeIdx());
+    assert(uint32_t(bits) != 0);
+    return uint32_t(bits);
+  }
+  inline uint32_t value() const {
+    assert(!isNodeIdx());
+    return uint32_t(bits);
+  }
+  inline constexpr bool isNodeIdx() const {
+    return (bits & IsNodeIdxMask) != 0;
+  }
+  inline constexpr bool isShutdown() const {
+    return (bits & IsShutdownMask) != 0;
+  }
+  inline constexpr uint32_t seq() const {
+    return uint32_t(bits >> SeqShift);
+  }
+
+  //////// setter-like things return a new struct
+
+  /// This should only be used for initial construction, not for setting
+  /// the value, because it clears the sequence number
+  static inline constexpr LifoSemHead fresh(uint32_t value) {
+    return LifoSemHead{ value };
+  }
+
+  /// Returns the LifoSemHead that results from popping a waiter node,
+  /// given the current waiter node's next ptr
+  inline LifoSemHead withPop(uint32_t idxNext) const {
+    assert(isNodeIdx());
+    if (idxNext == 0) {
+      // no isNodeIdx bit or data bits.  Wraparound of seq bits is okay
+      return LifoSemHead{ (bits & (SeqMask | IsShutdownMask)) + SeqIncr };
+    } else {
+      // preserve sequence bits (incremented with wraparound okay) and
+      // isNodeIdx bit, replace all data bits
+      return LifoSemHead{
+          (bits & (SeqMask | IsShutdownMask | IsNodeIdxMask)) +
+          SeqIncr + idxNext };
+    }
+  }
+
+  /// Returns the LifoSemHead that results from pushing a new waiter node
+  inline LifoSemHead withPush(uint32_t _idx) const {
+    assert(isNodeIdx() || value() == 0);
+    assert(!isShutdown());
+    assert(_idx != 0);
+    return LifoSemHead{ (bits & SeqMask) | IsNodeIdxMask | _idx };
+  }
+
+  /// Returns the LifoSemHead with value increased by delta, with
+  /// saturation if the maximum value is reached
+  inline LifoSemHead withValueIncr(uint32_t delta) const {
+    assert(!isNodeIdx());
+    auto rv = LifoSemHead{ bits + SeqIncr + delta };
+    if (UNLIKELY(rv.isNodeIdx())) {
+      // value has overflowed into the isNodeIdx bit
+      rv = LifoSemHead{ (rv.bits & ~IsNodeIdxMask) | (IsNodeIdxMask - 1) };
+    }
+    return rv;
+  }
+
+  /// Returns the LifoSemHead that results from decrementing the value
+  inline LifoSemHead withValueDecr(uint32_t delta) const {
+    assert(delta > 0 && delta <= value());
+    return LifoSemHead{ bits + SeqIncr - delta };
+  }
+
+  /// Returns the LifoSemHead with the same state as the current node,
+  /// but with the shutdown bit set
+  inline LifoSemHead withShutdown() const {
+    return LifoSemHead{ bits | IsShutdownMask };
+  }
+
+  inline constexpr bool operator== (const LifoSemHead& rhs) const {
+    return bits == rhs.bits;
+  }
+  inline constexpr bool operator!= (const LifoSemHead& rhs) const {
+    return !(*this == rhs);
+  }
+};
+
+/// LifoSemBase is the engine for several different types of LIFO
+/// semaphore.  LifoSemBase handles storage of positive semaphore values
+/// and wait nodes, but the actual waiting and notification mechanism is
+/// up to the client.
+///
+/// The Handoff type is responsible for arranging one wakeup notification.
+/// See LifoSemNode for more information on how to make your own.
+template <typename Handoff, template <typename> class Atom = std::atomic>
+struct LifoSemBase {
+
+  /// Constructor
+  constexpr explicit LifoSemBase(uint32_t initialValue = 0)
+      : head_(LifoSemHead::fresh(initialValue)) {}
+
+  LifoSemBase(LifoSemBase const&) = delete;
+  LifoSemBase& operator=(LifoSemBase const&) = delete;
+
+  /// Silently saturates if value is already 2^32-1
+  void post() {
+    auto idx = incrOrPop(1);
+    if (idx != 0) {
+      idxToNode(idx).handoff().post();
+    }
+  }
+
+  /// Equivalent to n calls to post(), except may be much more efficient.
+  /// At any point in time at which the semaphore's value would exceed
+  /// 2^32-1 if tracked with infinite precision, it may be silently
+  /// truncated to 2^32-1.  This saturation is not guaranteed to be exact,
+  /// although it is guaranteed that overflow won't result in wrap-around.
+  /// There would be a substantial performance and complexity cost in
+  /// guaranteeing exact saturation (similar to the cost of maintaining
+  /// linearizability near the zero value, but without as much of
+  /// a benefit).
+  void post(uint32_t n) {
+    uint32_t idx;
+    while (n > 0 && (idx = incrOrPop(n)) != 0) {
+      // pop accounts for only 1
+      idxToNode(idx).handoff().post();
+      --n;
+    }
+  }
+
+  /// Returns true iff shutdown() has been called
+  bool isShutdown() const {
+    return UNLIKELY(head_->load(std::memory_order_acquire).isShutdown());
+  }
+
+  /// Prevents blocking on this semaphore, causing all blocking wait()
+  /// calls to throw ShutdownSemError.  Both currently blocked wait() and
+  /// future calls to wait() for which tryWait() would return false will
+  /// cause an exception.  Calls to wait() for which the matching post()
+  /// has already occurred will proceed normally.
+  void shutdown() {
+    // first set the shutdown bit
+    auto h = head_->load(std::memory_order_acquire);
+    while (!h.isShutdown()) {
+      if (head_->compare_exchange_strong(h, h.withShutdown())) {
+        // success
+        h = h.withShutdown();
+        break;
+      }
+      // compare_exchange_strong rereads h, retry
+    }
+
+    // now wake up any waiters
+    while (h.isNodeIdx()) {
+      auto& node = idxToNode(h.idx());
+      auto repl = h.withPop(node.next);
+      if (head_->compare_exchange_strong(h, repl)) {
+        // successful pop, wake up the waiter and move on.  The next
+        // field is used to convey that this wakeup didn't consume a value
+        node.setShutdownNotice();
+        node.handoff().post();
+        h = repl;
+      }
+    }
+  }
+
+  /// Returns true iff value was decremented
+  bool tryWait() {
+    uint32_t n = 1;
+    auto rv = decrOrPush(n, 0);
+    assert((rv == WaitResult::DECR && n == 0) ||
+           (rv != WaitResult::DECR && n == 1));
+    // SHUTDOWN is okay here, since we don't actually wait
+    return rv == WaitResult::DECR;
+  }
+
+  /// Equivalent to (but may be much more efficient than) n calls to
+  /// tryWait().  Returns the total amount by which the semaphore's value
+  /// was decreased
+  uint32_t tryWait(uint32_t n) {
+    auto const orig = n;
+    while (n > 0) {
+#ifndef NDEBUG
+      auto prev = n;
+#endif
+      auto rv = decrOrPush(n, 0);
+      assert((rv == WaitResult::DECR && n < prev) ||
+             (rv != WaitResult::DECR && n == prev));
+      if (rv != WaitResult::DECR) {
+        break;
+      }
+    }
+    return orig - n;
+  }
+
+  /// Blocks the current thread until there is a matching post or the
+  /// semaphore is shut down.  Throws ShutdownSemError if the semaphore
+  /// has been shut down and this method would otherwise be blocking.
+  /// Note that wait() doesn't throw during shutdown if tryWait() would
+  /// return true
+  void wait() {
+    // early check isn't required for correctness, but is an important
+    // perf win if we can avoid allocating and deallocating a node
+    if (tryWait()) {
+      return;
+    }
+
+    // allocateNode() won't compile unless Handoff has a default
+    // constructor
+    UniquePtr node = allocateNode();
+
+    auto rv = tryWaitOrPush(*node);
+    if (UNLIKELY(rv == WaitResult::SHUTDOWN)) {
+      assert(isShutdown());
+      throw ShutdownSemError("wait() would block but semaphore is shut down");
+    }
+
+    if (rv == WaitResult::PUSH) {
+      node->handoff().wait();
+      if (UNLIKELY(node->isShutdownNotice())) {
+        // this wait() didn't consume a value, it was triggered by shutdown
+        assert(isShutdown());
+        throw ShutdownSemError(
+            "blocking wait() interrupted by semaphore shutdown");
+      }
+
+      // node->handoff().wait() can't return until after the node has
+      // been popped and post()ed, so it is okay for the UniquePtr to
+      // recycle the node now
+    }
+    // else node wasn't pushed, so it is safe to recycle
+  }
+
+  /// Returns a guess at the current value, designed for debugging.
+  /// If there are no concurrent posters or waiters then this will
+  /// be correct
+  uint32_t valueGuess() const {
+    // this is actually linearizable, but we don't promise that because
+    // we may want to add striping in the future to help under heavy
+    // contention
+    auto h = head_->load(std::memory_order_acquire);
+    return h.isNodeIdx() ? 0 : h.value();
+  }
+
+ protected:
+
+  enum class WaitResult {
+    PUSH,
+    DECR,
+    SHUTDOWN,
+  };
+
+  /// The type of a std::unique_ptr that will automatically return a
+  /// LifoSemNode to the appropriate IndexedMemPool
+  typedef std::unique_ptr<LifoSemNode<Handoff, Atom>,
+                          LifoSemNodeRecycler<Handoff, Atom>> UniquePtr;
+
+  /// Returns a node that can be passed to decrOrLink
+  template <typename... Args>
+  UniquePtr allocateNode(Args&&... args) {
+    auto idx = LifoSemRawNode<Atom>::pool().allocIndex();
+    if (idx != 0) {
+      auto& node = idxToNode(idx);
+      node.clearShutdownNotice();
+      try {
+        node.init(std::forward<Args>(args)...);
+      } catch (...) {
+        LifoSemRawNode<Atom>::pool().recycleIndex(idx);
+        throw;
+      }
+      return UniquePtr(&node);
+    } else {
+      return UniquePtr();
+    }
+  }
+
+  /// Returns DECR if the semaphore value was decremented (and waiterNode
+  /// was untouched), PUSH if a reference to the wait node was pushed,
+  /// or SHUTDOWN if decrement was not possible and push wasn't allowed
+  /// because isShutdown().  Ownership of the wait node remains the
+  /// responsibility of the caller, who must not release it until after
+  /// the node's Handoff has been posted.
+  WaitResult tryWaitOrPush(LifoSemNode<Handoff, Atom>& waiterNode) {
+    uint32_t n = 1;
+    return decrOrPush(n, nodeToIdx(waiterNode));
+  }
+
+ private:
+  CachelinePadded<folly::AtomicStruct<LifoSemHead, Atom>> head_;
+
+  static LifoSemNode<Handoff, Atom>& idxToNode(uint32_t idx) {
+    auto raw = &LifoSemRawNode<Atom>::pool()[idx];
+    return *static_cast<LifoSemNode<Handoff, Atom>*>(raw);
+  }
+
+  static uint32_t nodeToIdx(const LifoSemNode<Handoff, Atom>& node) {
+    return LifoSemRawNode<Atom>::pool().locateElem(&node);
+  }
+
+  /// Either increments by n and returns 0, or pops a node and returns it.
+  /// If n + the stripe's value overflows, then the stripe's value
+  /// saturates silently at 2^32-1
+  uint32_t incrOrPop(uint32_t n) {
+    while (true) {
+      assert(n > 0);
+
+      auto head = head_->load(std::memory_order_acquire);
+      if (head.isNodeIdx()) {
+        auto& node = idxToNode(head.idx());
+        if (head_->compare_exchange_strong(head, head.withPop(node.next))) {
+          // successful pop
+          return head.idx();
+        }
+      } else {
+        auto after = head.withValueIncr(n);
+        if (head_->compare_exchange_strong(head, after)) {
+          // successful incr
+          return 0;
+        }
+      }
+      // retry
+    }
+  }
+
+  /// Returns DECR if some amount was decremented, with that amount
+  /// subtracted from n.  If n is 1 and this function returns DECR then n
+  /// must be 0 afterward.  Returns PUSH if no value could be decremented
+  /// and idx was pushed, or if idx was zero and no push was performed but
+  /// a push would have been performed with a valid node.  Returns SHUTDOWN
+  /// if the caller should have blocked but isShutdown().  If idx == 0,
+  /// may return PUSH even after isShutdown() or may return SHUTDOWN
+  WaitResult decrOrPush(uint32_t& n, uint32_t idx) {
+    assert(n > 0);
+
+    while (true) {
+      auto head = head_->load(std::memory_order_acquire);
+
+      if (!head.isNodeIdx() && head.value() > 0) {
+        // decr
+        auto delta = std::min(n, head.value());
+        if (head_->compare_exchange_strong(head, head.withValueDecr(delta))) {
+          n -= delta;
+          return WaitResult::DECR;
+        }
+      } else {
+        // push
+        if (idx == 0) {
+          return WaitResult::PUSH;
+        }
+
+        if (UNLIKELY(head.isShutdown())) {
+          return WaitResult::SHUTDOWN;
+        }
+
+        auto& node = idxToNode(idx);
+        node.next = head.isNodeIdx() ? head.idx() : 0;
+        if (head_->compare_exchange_strong(head, head.withPush(idx))) {
+          // push succeeded
+          return WaitResult::PUSH;
+        }
+      }
+    }
+    // retry
+  }
+};
+
+} // namespace detail
+
+template <template <typename> class Atom, class BatonType>
+struct LifoSemImpl : public detail::LifoSemBase<BatonType, Atom> {
+  constexpr explicit LifoSemImpl(uint32_t v = 0)
+    : detail::LifoSemBase<BatonType, Atom>(v) {}
+};
+
+} // namespace folly
diff --git a/folly/synchronization/test/LifoSemTests.cpp b/folly/synchronization/test/LifoSemTests.cpp
new file mode 100644 (file)
index 0000000..fae889b
--- /dev/null
@@ -0,0 +1,447 @@
+/*
+ * Copyright 2017 Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <folly/synchronization/LifoSem.h>
+
+#include <thread>
+
+#include <folly/Benchmark.h>
+#include <folly/Random.h>
+#include <folly/portability/Asm.h>
+#include <folly/portability/GFlags.h>
+#include <folly/portability/GTest.h>
+#include <folly/portability/Semaphore.h>
+#include <folly/test/DeterministicSchedule.h>
+
+using namespace folly;
+using namespace folly::test;
+
+typedef LifoSemImpl<DeterministicAtomic> DLifoSem;
+typedef DeterministicSchedule DSched;
+
+LIFOSEM_DECLARE_POOL(DeterministicAtomic, 100000)
+
+TEST(LifoSem, basic) {
+  LifoSem sem;
+  EXPECT_FALSE(sem.tryWait());
+  sem.post();
+  EXPECT_TRUE(sem.tryWait());
+  sem.post();
+  sem.wait();
+}
+
+TEST(LifoSem, multi) {
+  LifoSem sem;
+
+  const int opsPerThread = 10000;
+  std::thread threads[10];
+  std::atomic<int> blocks(0);
+
+  for (auto& thr : threads) {
+    thr = std::thread([&]{
+      int b = 0;
+      for (int i = 0; i < opsPerThread; ++i) {
+        if (!sem.tryWait()) {
+          sem.wait();
+          ++b;
+        }
+        sem.post();
+      }
+      blocks += b;
+    });
+  }
+
+  // start the flood
+  sem.post();
+
+  for (auto& thr : threads) {
+    thr.join();
+  }
+
+  LOG(INFO) << opsPerThread * sizeof(threads)/sizeof(threads[0])
+            << " post/wait pairs, " << blocks << " blocked";
+}
+
+TEST(LifoSem, pingpong) {
+  DSched sched(DSched::uniform(0));
+
+  const int iters = 100;
+
+  for (int pass = 0; pass < 10; ++pass) {
+    DLifoSem a;
+    DLifoSem b;
+
+    auto thr = DSched::thread([&]{
+      for (int i = 0; i < iters; ++i) {
+        a.wait();
+        // main thread can't be running here
+        EXPECT_EQ(a.valueGuess(), 0);
+        EXPECT_EQ(b.valueGuess(), 0);
+        b.post();
+      }
+    });
+    for (int i = 0; i < iters; ++i) {
+      a.post();
+      b.wait();
+      // child thread can't be running here
+      EXPECT_EQ(a.valueGuess(), 0);
+      EXPECT_EQ(b.valueGuess(), 0);
+    }
+    DSched::join(thr);
+  }
+}
+
+TEST(LifoSem, mutex) {
+  DSched sched(DSched::uniform(0));
+
+  const int iters = 100;
+
+  for (int pass = 0; pass < 10; ++pass) {
+    DLifoSem a;
+
+    auto thr = DSched::thread([&]{
+      for (int i = 0; i < iters; ++i) {
+        a.wait();
+        a.post();
+      }
+    });
+    for (int i = 0; i < iters; ++i) {
+      a.post();
+      a.wait();
+    }
+    a.post();
+    DSched::join(thr);
+    a.wait();
+  }
+}
+
+TEST(LifoSem, no_blocking) {
+  long seed = folly::randomNumberSeed() % 10000;
+  LOG(INFO) << "seed=" << seed;
+  DSched sched(DSched::uniform(seed));
+
+  const int iters = 100;
+  const int numThreads = 2;
+  const int width = 10;
+
+  for (int pass = 0; pass < 10; ++pass) {
+    DLifoSem a;
+
+    std::vector<std::thread> threads;
+    while (threads.size() < numThreads) {
+      threads.emplace_back(DSched::thread([&]{
+        for (int i = 0; i < iters; ++i) {
+          a.post(width);
+          for (int w = 0; w < width; ++w) {
+            a.wait();
+          }
+        }
+      }));
+    }
+    for (auto& thr : threads) {
+      DSched::join(thr);
+    }
+  }
+}
+
+TEST(LifoSem, one_way) {
+  long seed = folly::randomNumberSeed() % 10000;
+  LOG(INFO) << "seed=" << seed;
+  DSched sched(DSched::uniformSubset(seed, 1, 6));
+
+  const int iters = 1000;
+
+  for (int pass = 0; pass < 10; ++pass) {
+    DLifoSem a;
+
+    auto thr = DSched::thread([&]{
+      for (int i = 0; i < iters; ++i) {
+        a.wait();
+      }
+    });
+    for (int i = 0; i < iters; ++i) {
+      a.post();
+    }
+    DSched::join(thr);
+  }
+}
+
+TEST(LifoSem, shutdown_race) {
+  long seed = folly::randomNumberSeed() % 10000;
+  LOG(INFO) << "seed=" << seed;
+
+  bool shutdownWon = false;
+  bool shutdownLost = false;
+  for (int pass = 0; pass < 1000; ++pass) {
+    DSched sched(DSched::uniformSubset(seed + pass, 1, 1 + (pass % 50)));
+
+    DLifoSem a;
+    int waitCount = 0;
+    auto thr = DSched::thread([&]{
+      try {
+        while (true) {
+          a.wait();
+          ++waitCount;
+        }
+      } catch (ShutdownSemError&) {
+        // expected
+        EXPECT_TRUE(a.isShutdown());
+      }
+    });
+    EXPECT_TRUE(!a.isShutdown());
+    a.shutdown();
+    EXPECT_TRUE(a.isShutdown());
+    a.post();
+    DSched::join(thr);
+    EXPECT_EQ(1, waitCount + a.valueGuess());
+    if (waitCount == 0) {
+      shutdownWon = true;
+    } else {
+      shutdownLost = true;
+    }
+  }
+  EXPECT_TRUE(shutdownWon);
+  EXPECT_TRUE(shutdownLost);
+}
+
+TEST(LifoSem, shutdown_multi) {
+  DSched sched(DSched::uniform(0));
+
+  for (int pass = 0; pass < 10; ++pass) {
+    DLifoSem a;
+    std::vector<std::thread> threads;
+    while (threads.size() < 20) {
+      threads.push_back(DSched::thread([&]{
+        try {
+          a.wait();
+          ADD_FAILURE();
+        } catch (ShutdownSemError&) {
+          // expected
+          EXPECT_TRUE(a.isShutdown());
+        }
+      }));
+    }
+    a.shutdown();
+    for (auto& thr : threads) {
+      DSched::join(thr);
+    }
+  }
+}
+
+TEST(LifoSem, multi_try_wait_simple) {
+  LifoSem sem;
+  sem.post(5);
+  auto n = sem.tryWait(10);     // this used to trigger an assert
+  ASSERT_EQ(5, n);
+}
+
+TEST(LifoSem, multi_try_wait) {
+  long seed = folly::randomNumberSeed() % 10000;
+  LOG(INFO) << "seed=" << seed;
+  DSched sched(DSched::uniform(seed));
+  DLifoSem sem;
+
+  const int NPOSTS = 1000;
+
+  auto producer = [&]{
+    for (int i=0; i<NPOSTS; ++i) {
+      sem.post();
+    }
+  };
+
+  DeterministicAtomic<bool> consumer_stop(false);
+  int consumed = 0;
+
+  auto consumer = [&]{
+    bool stop;
+    do {
+      stop = consumer_stop.load();
+      int n;
+      do {
+        n = sem.tryWait(10);
+        consumed += n;
+      } while (n > 0);
+    } while (!stop);
+  };
+
+  std::thread producer_thread(DSched::thread(producer));
+  std::thread consumer_thread(DSched::thread(consumer));
+  DSched::join(producer_thread);
+  consumer_stop.store(true);
+  DSched::join(consumer_thread);
+
+  ASSERT_EQ(NPOSTS, consumed);
+}
+
+BENCHMARK(lifo_sem_pingpong, iters) {
+  LifoSem a;
+  LifoSem b;
+  auto thr = std::thread([&]{
+    for (size_t i = 0; i < iters; ++i) {
+      a.wait();
+      b.post();
+    }
+  });
+  for (size_t i = 0; i < iters; ++i) {
+    a.post();
+    b.wait();
+  }
+  thr.join();
+}
+
+BENCHMARK(lifo_sem_oneway, iters) {
+  LifoSem a;
+  auto thr = std::thread([&]{
+    for (size_t i = 0; i < iters; ++i) {
+      a.wait();
+    }
+  });
+  for (size_t i = 0; i < iters; ++i) {
+    a.post();
+  }
+  thr.join();
+}
+
+BENCHMARK(single_thread_lifo_post, iters) {
+  LifoSem sem;
+  for (size_t n = 0; n < iters; ++n) {
+    sem.post();
+    asm_volatile_memory();
+  }
+}
+
+BENCHMARK(single_thread_lifo_wait, iters) {
+  LifoSem sem(iters);
+  for (size_t n = 0; n < iters; ++n) {
+    sem.wait();
+    asm_volatile_memory();
+  }
+}
+
+BENCHMARK(single_thread_lifo_postwait, iters) {
+  LifoSem sem;
+  for (size_t n = 0; n < iters; ++n) {
+    sem.post();
+    asm_volatile_memory();
+    sem.wait();
+    asm_volatile_memory();
+  }
+}
+
+BENCHMARK(single_thread_lifo_trywait, iters) {
+  LifoSem sem;
+  for (size_t n = 0; n < iters; ++n) {
+    EXPECT_FALSE(sem.tryWait());
+    asm_volatile_memory();
+  }
+}
+
+BENCHMARK(single_thread_posix_postwait, iters) {
+  sem_t sem;
+  EXPECT_EQ(sem_init(&sem, 0, 0), 0);
+  for (size_t n = 0; n < iters; ++n) {
+    EXPECT_EQ(sem_post(&sem), 0);
+    EXPECT_EQ(sem_wait(&sem), 0);
+  }
+  EXPECT_EQ(sem_destroy(&sem), 0);
+}
+
+BENCHMARK(single_thread_posix_trywait, iters) {
+  sem_t sem;
+  EXPECT_EQ(sem_init(&sem, 0, 0), 0);
+  for (size_t n = 0; n < iters; ++n) {
+    EXPECT_EQ(sem_trywait(&sem), -1);
+  }
+  EXPECT_EQ(sem_destroy(&sem), 0);
+}
+
+static void contendedUse(uint32_t n, int posters, int waiters) {
+  LifoSemImpl<std::atomic> sem;
+
+  std::vector<std::thread> threads;
+  std::atomic<bool> go(false);
+
+  BENCHMARK_SUSPEND {
+    for (int t = 0; t < waiters; ++t) {
+      threads.emplace_back([=,&sem] {
+        for (uint32_t i = t; i < n; i += waiters) {
+          sem.wait();
+        }
+      });
+    }
+    for (int t = 0; t < posters; ++t) {
+      threads.emplace_back([=,&sem,&go] {
+        while (!go.load()) {
+          std::this_thread::yield();
+        }
+        for (uint32_t i = t; i < n; i += posters) {
+          sem.post();
+        }
+      });
+    }
+  }
+
+  go.store(true);
+  for (auto& thr : threads) {
+    thr.join();
+  }
+}
+
+BENCHMARK_DRAW_LINE()
+BENCHMARK_NAMED_PARAM(contendedUse, 1_to_1, 1, 1)
+BENCHMARK_NAMED_PARAM(contendedUse, 1_to_4, 1, 4)
+BENCHMARK_NAMED_PARAM(contendedUse, 1_to_32, 1, 32)
+BENCHMARK_NAMED_PARAM(contendedUse, 4_to_1, 4, 1)
+BENCHMARK_NAMED_PARAM(contendedUse, 4_to_24, 4, 24)
+BENCHMARK_NAMED_PARAM(contendedUse, 8_to_100, 8, 100)
+BENCHMARK_NAMED_PARAM(contendedUse, 32_to_1, 31, 1)
+BENCHMARK_NAMED_PARAM(contendedUse, 16_to_16, 16, 16)
+BENCHMARK_NAMED_PARAM(contendedUse, 32_to_32, 32, 32)
+BENCHMARK_NAMED_PARAM(contendedUse, 32_to_1000, 32, 1000)
+
+// sudo nice -n -20 _build/opt/folly/test/LifoSemTests
+//     --benchmark --bm_min_iters=10000000 --gtest_filter=-\*
+// ============================================================================
+// folly/test/LifoSemTests.cpp                     relative  time/iter  iters/s
+// ============================================================================
+// lifo_sem_pingpong                                            1.31us  762.40K
+// lifo_sem_oneway                                            193.89ns    5.16M
+// single_thread_lifo_post                                     15.37ns   65.08M
+// single_thread_lifo_wait                                     13.60ns   73.53M
+// single_thread_lifo_postwait                                 29.43ns   33.98M
+// single_thread_lifo_trywait                                 677.69ps    1.48G
+// single_thread_posix_postwait                                25.03ns   39.95M
+// single_thread_posix_trywait                                  7.30ns  136.98M
+// ----------------------------------------------------------------------------
+// contendedUse(1_to_1)                                       158.22ns    6.32M
+// contendedUse(1_to_4)                                       574.73ns    1.74M
+// contendedUse(1_to_32)                                      592.94ns    1.69M
+// contendedUse(4_to_1)                                       118.28ns    8.45M
+// contendedUse(4_to_24)                                      667.62ns    1.50M
+// contendedUse(8_to_100)                                     701.46ns    1.43M
+// contendedUse(32_to_1)                                      165.06ns    6.06M
+// contendedUse(16_to_16)                                     238.57ns    4.19M
+// contendedUse(32_to_32)                                     219.82ns    4.55M
+// contendedUse(32_to_1000)                                   777.42ns    1.29M
+// ============================================================================
+
+int main(int argc, char ** argv) {
+  testing::InitGoogleTest(&argc, argv);
+  gflags::ParseCommandLineFlags(&argc, &argv, true);
+  int rv = RUN_ALL_TESTS();
+  folly::runBenchmarksOnFlag();
+  return rv;
+}
diff --git a/folly/test/LifoSemTests.cpp b/folly/test/LifoSemTests.cpp
deleted file mode 100644 (file)
index c6c9b45..0000000
+++ /dev/null
@@ -1,447 +0,0 @@
-/*
- * Copyright 2017 Facebook, Inc.
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- *   http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-#include <folly/LifoSem.h>
-
-#include <thread>
-
-#include <folly/Benchmark.h>
-#include <folly/Random.h>
-#include <folly/portability/Asm.h>
-#include <folly/portability/GFlags.h>
-#include <folly/portability/GTest.h>
-#include <folly/portability/Semaphore.h>
-#include <folly/test/DeterministicSchedule.h>
-
-using namespace folly;
-using namespace folly::test;
-
-typedef LifoSemImpl<DeterministicAtomic> DLifoSem;
-typedef DeterministicSchedule DSched;
-
-LIFOSEM_DECLARE_POOL(DeterministicAtomic, 100000)
-
-TEST(LifoSem, basic) {
-  LifoSem sem;
-  EXPECT_FALSE(sem.tryWait());
-  sem.post();
-  EXPECT_TRUE(sem.tryWait());
-  sem.post();
-  sem.wait();
-}
-
-TEST(LifoSem, multi) {
-  LifoSem sem;
-
-  const int opsPerThread = 10000;
-  std::thread threads[10];
-  std::atomic<int> blocks(0);
-
-  for (auto& thr : threads) {
-    thr = std::thread([&]{
-      int b = 0;
-      for (int i = 0; i < opsPerThread; ++i) {
-        if (!sem.tryWait()) {
-          sem.wait();
-          ++b;
-        }
-        sem.post();
-      }
-      blocks += b;
-    });
-  }
-
-  // start the flood
-  sem.post();
-
-  for (auto& thr : threads) {
-    thr.join();
-  }
-
-  LOG(INFO) << opsPerThread * sizeof(threads)/sizeof(threads[0])
-            << " post/wait pairs, " << blocks << " blocked";
-}
-
-TEST(LifoSem, pingpong) {
-  DSched sched(DSched::uniform(0));
-
-  const int iters = 100;
-
-  for (int pass = 0; pass < 10; ++pass) {
-    DLifoSem a;
-    DLifoSem b;
-
-    auto thr = DSched::thread([&]{
-      for (int i = 0; i < iters; ++i) {
-        a.wait();
-        // main thread can't be running here
-        EXPECT_EQ(a.valueGuess(), 0);
-        EXPECT_EQ(b.valueGuess(), 0);
-        b.post();
-      }
-    });
-    for (int i = 0; i < iters; ++i) {
-      a.post();
-      b.wait();
-      // child thread can't be running here
-      EXPECT_EQ(a.valueGuess(), 0);
-      EXPECT_EQ(b.valueGuess(), 0);
-    }
-    DSched::join(thr);
-  }
-}
-
-TEST(LifoSem, mutex) {
-  DSched sched(DSched::uniform(0));
-
-  const int iters = 100;
-
-  for (int pass = 0; pass < 10; ++pass) {
-    DLifoSem a;
-
-    auto thr = DSched::thread([&]{
-      for (int i = 0; i < iters; ++i) {
-        a.wait();
-        a.post();
-      }
-    });
-    for (int i = 0; i < iters; ++i) {
-      a.post();
-      a.wait();
-    }
-    a.post();
-    DSched::join(thr);
-    a.wait();
-  }
-}
-
-TEST(LifoSem, no_blocking) {
-  long seed = folly::randomNumberSeed() % 10000;
-  LOG(INFO) << "seed=" << seed;
-  DSched sched(DSched::uniform(seed));
-
-  const int iters = 100;
-  const int numThreads = 2;
-  const int width = 10;
-
-  for (int pass = 0; pass < 10; ++pass) {
-    DLifoSem a;
-
-    std::vector<std::thread> threads;
-    while (threads.size() < numThreads) {
-      threads.emplace_back(DSched::thread([&]{
-        for (int i = 0; i < iters; ++i) {
-          a.post(width);
-          for (int w = 0; w < width; ++w) {
-            a.wait();
-          }
-        }
-      }));
-    }
-    for (auto& thr : threads) {
-      DSched::join(thr);
-    }
-  }
-}
-
-TEST(LifoSem, one_way) {
-  long seed = folly::randomNumberSeed() % 10000;
-  LOG(INFO) << "seed=" << seed;
-  DSched sched(DSched::uniformSubset(seed, 1, 6));
-
-  const int iters = 1000;
-
-  for (int pass = 0; pass < 10; ++pass) {
-    DLifoSem a;
-
-    auto thr = DSched::thread([&]{
-      for (int i = 0; i < iters; ++i) {
-        a.wait();
-      }
-    });
-    for (int i = 0; i < iters; ++i) {
-      a.post();
-    }
-    DSched::join(thr);
-  }
-}
-
-TEST(LifoSem, shutdown_race) {
-  long seed = folly::randomNumberSeed() % 10000;
-  LOG(INFO) << "seed=" << seed;
-
-  bool shutdownWon = false;
-  bool shutdownLost = false;
-  for (int pass = 0; pass < 1000; ++pass) {
-    DSched sched(DSched::uniformSubset(seed + pass, 1, 1 + (pass % 50)));
-
-    DLifoSem a;
-    int waitCount = 0;
-    auto thr = DSched::thread([&]{
-      try {
-        while (true) {
-          a.wait();
-          ++waitCount;
-        }
-      } catch (ShutdownSemError&) {
-        // expected
-        EXPECT_TRUE(a.isShutdown());
-      }
-    });
-    EXPECT_TRUE(!a.isShutdown());
-    a.shutdown();
-    EXPECT_TRUE(a.isShutdown());
-    a.post();
-    DSched::join(thr);
-    EXPECT_EQ(1, waitCount + a.valueGuess());
-    if (waitCount == 0) {
-      shutdownWon = true;
-    } else {
-      shutdownLost = true;
-    }
-  }
-  EXPECT_TRUE(shutdownWon);
-  EXPECT_TRUE(shutdownLost);
-}
-
-TEST(LifoSem, shutdown_multi) {
-  DSched sched(DSched::uniform(0));
-
-  for (int pass = 0; pass < 10; ++pass) {
-    DLifoSem a;
-    std::vector<std::thread> threads;
-    while (threads.size() < 20) {
-      threads.push_back(DSched::thread([&]{
-        try {
-          a.wait();
-          ADD_FAILURE();
-        } catch (ShutdownSemError&) {
-          // expected
-          EXPECT_TRUE(a.isShutdown());
-        }
-      }));
-    }
-    a.shutdown();
-    for (auto& thr : threads) {
-      DSched::join(thr);
-    }
-  }
-}
-
-TEST(LifoSem, multi_try_wait_simple) {
-  LifoSem sem;
-  sem.post(5);
-  auto n = sem.tryWait(10);     // this used to trigger an assert
-  ASSERT_EQ(5, n);
-}
-
-TEST(LifoSem, multi_try_wait) {
-  long seed = folly::randomNumberSeed() % 10000;
-  LOG(INFO) << "seed=" << seed;
-  DSched sched(DSched::uniform(seed));
-  DLifoSem sem;
-
-  const int NPOSTS = 1000;
-
-  auto producer = [&]{
-    for (int i=0; i<NPOSTS; ++i) {
-      sem.post();
-    }
-  };
-
-  DeterministicAtomic<bool> consumer_stop(false);
-  int consumed = 0;
-
-  auto consumer = [&]{
-    bool stop;
-    do {
-      stop = consumer_stop.load();
-      int n;
-      do {
-        n = sem.tryWait(10);
-        consumed += n;
-      } while (n > 0);
-    } while (!stop);
-  };
-
-  std::thread producer_thread(DSched::thread(producer));
-  std::thread consumer_thread(DSched::thread(consumer));
-  DSched::join(producer_thread);
-  consumer_stop.store(true);
-  DSched::join(consumer_thread);
-
-  ASSERT_EQ(NPOSTS, consumed);
-}
-
-BENCHMARK(lifo_sem_pingpong, iters) {
-  LifoSem a;
-  LifoSem b;
-  auto thr = std::thread([&]{
-    for (size_t i = 0; i < iters; ++i) {
-      a.wait();
-      b.post();
-    }
-  });
-  for (size_t i = 0; i < iters; ++i) {
-    a.post();
-    b.wait();
-  }
-  thr.join();
-}
-
-BENCHMARK(lifo_sem_oneway, iters) {
-  LifoSem a;
-  auto thr = std::thread([&]{
-    for (size_t i = 0; i < iters; ++i) {
-      a.wait();
-    }
-  });
-  for (size_t i = 0; i < iters; ++i) {
-    a.post();
-  }
-  thr.join();
-}
-
-BENCHMARK(single_thread_lifo_post, iters) {
-  LifoSem sem;
-  for (size_t n = 0; n < iters; ++n) {
-    sem.post();
-    asm_volatile_memory();
-  }
-}
-
-BENCHMARK(single_thread_lifo_wait, iters) {
-  LifoSem sem(iters);
-  for (size_t n = 0; n < iters; ++n) {
-    sem.wait();
-    asm_volatile_memory();
-  }
-}
-
-BENCHMARK(single_thread_lifo_postwait, iters) {
-  LifoSem sem;
-  for (size_t n = 0; n < iters; ++n) {
-    sem.post();
-    asm_volatile_memory();
-    sem.wait();
-    asm_volatile_memory();
-  }
-}
-
-BENCHMARK(single_thread_lifo_trywait, iters) {
-  LifoSem sem;
-  for (size_t n = 0; n < iters; ++n) {
-    EXPECT_FALSE(sem.tryWait());
-    asm_volatile_memory();
-  }
-}
-
-BENCHMARK(single_thread_posix_postwait, iters) {
-  sem_t sem;
-  EXPECT_EQ(sem_init(&sem, 0, 0), 0);
-  for (size_t n = 0; n < iters; ++n) {
-    EXPECT_EQ(sem_post(&sem), 0);
-    EXPECT_EQ(sem_wait(&sem), 0);
-  }
-  EXPECT_EQ(sem_destroy(&sem), 0);
-}
-
-BENCHMARK(single_thread_posix_trywait, iters) {
-  sem_t sem;
-  EXPECT_EQ(sem_init(&sem, 0, 0), 0);
-  for (size_t n = 0; n < iters; ++n) {
-    EXPECT_EQ(sem_trywait(&sem), -1);
-  }
-  EXPECT_EQ(sem_destroy(&sem), 0);
-}
-
-static void contendedUse(uint32_t n, int posters, int waiters) {
-  LifoSemImpl<std::atomic> sem;
-
-  std::vector<std::thread> threads;
-  std::atomic<bool> go(false);
-
-  BENCHMARK_SUSPEND {
-    for (int t = 0; t < waiters; ++t) {
-      threads.emplace_back([=,&sem] {
-        for (uint32_t i = t; i < n; i += waiters) {
-          sem.wait();
-        }
-      });
-    }
-    for (int t = 0; t < posters; ++t) {
-      threads.emplace_back([=,&sem,&go] {
-        while (!go.load()) {
-          std::this_thread::yield();
-        }
-        for (uint32_t i = t; i < n; i += posters) {
-          sem.post();
-        }
-      });
-    }
-  }
-
-  go.store(true);
-  for (auto& thr : threads) {
-    thr.join();
-  }
-}
-
-BENCHMARK_DRAW_LINE()
-BENCHMARK_NAMED_PARAM(contendedUse, 1_to_1, 1, 1)
-BENCHMARK_NAMED_PARAM(contendedUse, 1_to_4, 1, 4)
-BENCHMARK_NAMED_PARAM(contendedUse, 1_to_32, 1, 32)
-BENCHMARK_NAMED_PARAM(contendedUse, 4_to_1, 4, 1)
-BENCHMARK_NAMED_PARAM(contendedUse, 4_to_24, 4, 24)
-BENCHMARK_NAMED_PARAM(contendedUse, 8_to_100, 8, 100)
-BENCHMARK_NAMED_PARAM(contendedUse, 32_to_1, 31, 1)
-BENCHMARK_NAMED_PARAM(contendedUse, 16_to_16, 16, 16)
-BENCHMARK_NAMED_PARAM(contendedUse, 32_to_32, 32, 32)
-BENCHMARK_NAMED_PARAM(contendedUse, 32_to_1000, 32, 1000)
-
-// sudo nice -n -20 _build/opt/folly/test/LifoSemTests
-//     --benchmark --bm_min_iters=10000000 --gtest_filter=-\*
-// ============================================================================
-// folly/test/LifoSemTests.cpp                     relative  time/iter  iters/s
-// ============================================================================
-// lifo_sem_pingpong                                            1.31us  762.40K
-// lifo_sem_oneway                                            193.89ns    5.16M
-// single_thread_lifo_post                                     15.37ns   65.08M
-// single_thread_lifo_wait                                     13.60ns   73.53M
-// single_thread_lifo_postwait                                 29.43ns   33.98M
-// single_thread_lifo_trywait                                 677.69ps    1.48G
-// single_thread_posix_postwait                                25.03ns   39.95M
-// single_thread_posix_trywait                                  7.30ns  136.98M
-// ----------------------------------------------------------------------------
-// contendedUse(1_to_1)                                       158.22ns    6.32M
-// contendedUse(1_to_4)                                       574.73ns    1.74M
-// contendedUse(1_to_32)                                      592.94ns    1.69M
-// contendedUse(4_to_1)                                       118.28ns    8.45M
-// contendedUse(4_to_24)                                      667.62ns    1.50M
-// contendedUse(8_to_100)                                     701.46ns    1.43M
-// contendedUse(32_to_1)                                      165.06ns    6.06M
-// contendedUse(16_to_16)                                     238.57ns    4.19M
-// contendedUse(32_to_32)                                     219.82ns    4.55M
-// contendedUse(32_to_1000)                                   777.42ns    1.29M
-// ============================================================================
-
-int main(int argc, char ** argv) {
-  testing::InitGoogleTest(&argc, argv);
-  gflags::ParseCommandLineFlags(&argc, &argv, true);
-  int rv = RUN_ALL_TESTS();
-  folly::runBenchmarksOnFlag();
-  return rv;
-}