folly::detail::LifoSemBase< Handoff, Atom > Struct Template Reference

#include <LifoSem.h>

Public Member Functions
constexpr	LifoSemBase (uint32_t initialValue=0)
	Constructor. More...
	LifoSemBase (LifoSemBase const &)=delete
LifoSemBase &	operator= (LifoSemBase const &)=delete
bool	post ()
	Silently saturates if value is already 2^32-1. More...
void	post (uint32_t n)
bool	isShutdown () const
	Returns true iff shutdown() has been called. More...
void	shutdown ()
bool	tryWait ()
	Returns true iff value was decremented. More...
uint32_t	tryWait (uint32_t n)
void	wait ()
template<typename Rep , typename Period >
bool	try_wait_for (const std::chrono::duration< Rep, Period > &timeout)
template<typename Clock , typename Duration >
bool	try_wait_until (const std::chrono::time_point< Clock, Duration > &deadline)
uint32_t	valueGuess () const

Protected Types
enum	WaitResult { WaitResult::PUSH, WaitResult::DECR, WaitResult::SHUTDOWN }
typedef std::unique_ptr< LifoSemNode< Handoff, Atom >, LifoSemNodeRecycler< Handoff, Atom > >	UniquePtr

Protected Member Functions
template<typename... Args>
UniquePtr	allocateNode (Args &&...args)
	Returns a node that can be passed to decrOrLink. More...
WaitResult	tryWaitOrPush (LifoSemNode< Handoff, Atom > &waiterNode)

Private Member Functions
bool	tryRemoveNode (const LifoSemNode< Handoff, Atom > &removenode)
uint32_t	incrOrPop (uint32_t n)
WaitResult	decrOrPush (uint32_t &n, uint32_t idx)

Static Private Member Functions
static LifoSemNode< Handoff, Atom > &	idxToNode (uint32_t idx)
static uint32_t	nodeToIdx (const LifoSemNode< Handoff, Atom > &node)

Private Attributes
CachelinePadded< folly::AtomicStruct< LifoSemHead, Atom > >	head_

Detailed Description

template<typename Handoff, template< typename > class Atom = std::atomic>
struct folly::detail::LifoSemBase< Handoff, Atom >

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.

Definition at line 352 of file LifoSem.h.

Member Typedef Documentation

template<typename Handoff, template< typename > class Atom = std::atomic>

typedef std:: unique_ptr<LifoSemNode<Handoff, Atom>, LifoSemNodeRecycler<Handoff, Atom> > folly::detail::LifoSemBase< Handoff, Atom >::UniquePtr

protected

The type of a std::unique_ptr that will automatically return a LifoSemNode to the appropriate IndexedMemPool

Definition at line 547 of file LifoSem.h.

Member Enumeration Documentation

template<typename Handoff, template< typename > class Atom = std::atomic>

enum folly::detail::LifoSemBase::WaitResult

strongprotected

Enumerator
PUSH
DECR
SHUTDOWN

Definition at line 537 of file LifoSem.h.

                        {
    PUSH,
    DECR,
    SHUTDOWN,
  };

Constructor & Destructor Documentation

template<typename Handoff, template< typename > class Atom = std::atomic>

constexpr folly::detail::LifoSemBase< Handoff, Atom >::LifoSemBase ( uint32_t  initialValue = 0 )

inlineexplicit

Constructor.

Definition at line 354 of file LifoSem.h.

      : head_(LifoSemHead::fresh(initialValue)) {}

template<typename Handoff, template< typename > class Atom = std::atomic>

folly::detail::LifoSemBase< Handoff, Atom >::LifoSemBase ( LifoSemBase< Handoff, Atom > const &  )

delete

Member Function Documentation

template<typename Handoff, template< typename > class Atom = std::atomic>

template<typename... Args>

UniquePtr folly::detail::LifoSemBase< Handoff, Atom >::allocateNode ( Args &&...  args )

inlineprotected

Returns a node that can be passed to decrOrLink.

Definition at line 551 of file LifoSem.h.

                                         {
    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();
    }
  }

template<typename Handoff, template< typename > class Atom = std::atomic>

WaitResult folly::detail::LifoSemBase< Handoff, Atom >::decrOrPush ( uint32_t &  n, uint32_t  idx  )

inlineprivate

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

Definition at line 678 of file LifoSem.h.

                                                   {
    assert(n > 0);

    while (true) {
      auto head = head_->load(std::memory_order_acquire);

      if (head.isLocked()) {
        std::this_thread::yield();
        continue;
      }

      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
  }

template<typename Handoff, template< typename > class Atom = std::atomic>

static LifoSemNode<Handoff, Atom>& folly::detail::LifoSemBase< Handoff, Atom >::idxToNode ( uint32_t  idx )

inlinestaticprivate

Definition at line 582 of file LifoSem.h.

                                                             {
    auto raw = &LifoSemRawNode<Atom>::pool()[idx];
    return *static_cast<LifoSemNode<Handoff, Atom>*>(raw);
  }

template<typename Handoff, template< typename > class Atom = std::atomic>

uint32_t folly::detail::LifoSemBase< Handoff, Atom >::incrOrPop ( uint32_t  n )

inlineprivate

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

Definition at line 645 of file LifoSem.h.

                                 {
    while (true) {
      assert(n > 0);

      auto head = head_->load(std::memory_order_acquire);
      if (head.isLocked()) {
        std::this_thread::yield();
        continue;
      }
      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
    }
  }

template<typename Handoff, template< typename > class Atom = std::atomic>

bool folly::detail::LifoSemBase< Handoff, Atom >::isShutdown ( ) const

inline

Returns true iff shutdown() has been called.

Definition at line 389 of file LifoSem.h.

Referenced by TEST_F().

                          {
    return UNLIKELY(head_->load(std::memory_order_acquire).isShutdown());
  }

template<typename Handoff, template< typename > class Atom = std::atomic>

static uint32_t folly::detail::LifoSemBase< Handoff, Atom >::nodeToIdx ( const LifoSemNode< Handoff, Atom > &  node )

inlinestaticprivate

Definition at line 587 of file LifoSem.h.

                                                                    {
    return LifoSemRawNode<Atom>::pool().locateElem(&node);
  }

template<typename Handoff, template< typename > class Atom = std::atomic>

LifoSemBase& folly::detail::LifoSemBase< Handoff, Atom >::operator= ( LifoSemBase< Handoff, Atom > const &  )

delete

template<typename Handoff, template< typename > class Atom = std::atomic>

bool folly::detail::LifoSemBase< Handoff, Atom >::post ( )

inline

Silently saturates if value is already 2^32-1.

Definition at line 361 of file LifoSem.h.

Referenced by folly::UnboundedBlockingQueue< T >::add(), folly::LifoSemMPMCQueue< T, kBehavior >::add(), folly::ManualExecutor::add(), folly::PriorityLifoSemMPMCQueue< T, kBehavior >::addWithPriority(), BENCHMARK(), folly::ManualExecutor::scheduleAt(), TEST(), and TEST_F().

              {
    auto idx = incrOrPop(1);
    if (idx != 0) {
      idxToNode(idx).handoff().post();
      return true;
    }
    return false;
  }

template<typename Handoff, template< typename > class Atom = std::atomic>

void folly::detail::LifoSemBase< Handoff, Atom >::post ( uint32_t  n )

inline

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).

Definition at line 379 of file LifoSem.h.

                        {
    uint32_t idx;
    while (n > 0 && (idx = incrOrPop(n)) != 0) {
      // pop accounts for only 1
      idxToNode(idx).handoff().post();
      --n;
    }
  }

template<typename Handoff, template< typename > class Atom = std::atomic>

void folly::detail::LifoSemBase< Handoff, Atom >::shutdown ( )

inline

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.

Definition at line 398 of file LifoSem.h.

Referenced by TEST_F().

                  {
    // 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()) {
      if (h.isLocked()) {
        std::this_thread::yield();
        h = head_->load(std::memory_order_acquire);
        continue;
      }
      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;
      }
    }
  }

template<typename Handoff, template< typename > class Atom = std::atomic>

template<typename Rep , typename Period >

bool folly::detail::LifoSemBase< Handoff, Atom >::try_wait_for ( const std::chrono::duration< Rep, Period > &  timeout )

inline

Definition at line 472 of file LifoSem.h.

Referenced by TEST_F(), folly::UnboundedBlockingQueue< T >::try_take_for(), folly::LifoSemMPMCQueue< T, kBehavior >::try_take_for(), and folly::PriorityLifoSemMPMCQueue< T, kBehavior >::try_take_for().

                                                                   {
    return try_wait_until(timeout + std::chrono::steady_clock::now());
  }

template<typename Handoff, template< typename > class Atom = std::atomic>

template<typename Clock , typename Duration >

bool folly::detail::LifoSemBase< Handoff, Atom >::try_wait_until ( const std::chrono::time_point< Clock, Duration > &  deadline )

inline

Definition at line 477 of file LifoSem.h.

                                                            {
    // 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 true;
    }

    // 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) {
      if (!node->handoff().try_wait_until(deadline)) {
        if (tryRemoveNode(*node)) {
          return false;
        } else {
          // We could not remove our node. Return to waiting.
          //
          // This only happens if we lose a removal race with post(),
          // so we are not likely to wait long.  This is only
          // necessary to ensure we don't return node's memory back to
          // IndexedMemPool before post() has had a chance to post to
          // handoff().  In a stronger memory reclamation scheme, such
          // as hazptr or rcu, this would not be necessary.
          node->handoff().wait();
        }
      }
      if (UNLIKELY(node->isShutdownNotice())) {
        // this wait() didn't consume a value, it was triggered by shutdown
        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
    return true;
  }

template<typename Handoff, template< typename > class Atom = std::atomic>

bool folly::detail::LifoSemBase< Handoff, Atom >::tryRemoveNode ( const LifoSemNode< Handoff, Atom > &  removenode )

inlineprivate

Definition at line 594 of file LifoSem.h.

                                                                   {
    auto removeidx = nodeToIdx(removenode);
    auto head = head_->load(std::memory_order_acquire);
    // Try to lock the head.
    while (true) {
      if (head.isLocked()) {
        std::this_thread::yield();
        head = head_->load(std::memory_order_acquire);
        continue;
      }
      if (!head.isNodeIdx()) {
        return false;
      }
      if (head_->compare_exchange_weak(
              head,
              head.withLock(),
              std::memory_order_acquire,
              std::memory_order_relaxed)) {
        break;
      }
    }
    // Update local var to what head_ is, for better assert() checking.
    head = head.withLock();
    bool result = false;
    auto idx = head.idx();
    if (idx == removeidx) {
      // pop from head.  Head seqno is updated.
      head_->store(
          head.withoutLock(removenode.next), std::memory_order_release);
      return true;
    }
    auto node = &idxToNode(idx);
    idx = node->next;
    while (idx) {
      if (idx == removeidx) {
        // Pop from mid-list.
        node->next = removenode.next;
        result = true;
        break;
      }
      node = &idxToNode(idx);
      idx = node->next;
    }
    // Unlock and return result
    head_->store(head.withoutLock(head.idx()), std::memory_order_release);
    return result;
  }

template<typename Handoff, template< typename > class Atom = std::atomic>

bool folly::detail::LifoSemBase< Handoff, Atom >::tryWait ( )

inline

Returns true iff value was decremented.

Definition at line 430 of file LifoSem.h.

Referenced by BENCHMARK(), folly::ManualExecutor::run(), TEST(), and TEST_F().

                 {
    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;
  }

template<typename Handoff, template< typename > class Atom = std::atomic>

uint32_t folly::detail::LifoSemBase< Handoff, Atom >::tryWait ( uint32_t  n )

inline

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

Definition at line 443 of file LifoSem.h.

                               {
    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;
  }

template<typename Handoff, template< typename > class Atom = std::atomic>

WaitResult folly::detail::LifoSemBase< Handoff, Atom >::tryWaitOrPush ( LifoSemNode< Handoff, Atom > &  waiterNode )

inlineprotected

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.

Definition at line 574 of file LifoSem.h.

                                                                   {
    uint32_t n = 1;
    return decrOrPush(n, nodeToIdx(waiterNode));
  }

template<typename Handoff, template< typename > class Atom = std::atomic>

uint32_t folly::detail::LifoSemBase< Handoff, Atom >::valueGuess ( ) const

inline

Returns a guess at the current value, designed for debugging. If there are no concurrent posters or waiters then this will be correct

Definition at line 528 of file LifoSem.h.

Referenced by TEST_F().

                              {
    // 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();
  }

template<typename Handoff, template< typename > class Atom = std::atomic>

void folly::detail::LifoSemBase< Handoff, Atom >::wait ( )

inline

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

Definition at line 465 of file LifoSem.h.

Referenced by BENCHMARK(), folly::UnboundedBlockingQueue< T >::take(), folly::LifoSemMPMCQueue< T, kBehavior >::take(), folly::PriorityLifoSemMPMCQueue< T, kBehavior >::take(), TEST(), TEST_F(), and folly::ManualExecutor::wait().

              {
    auto const deadline = std::chrono::steady_clock::time_point::max();
    auto res = try_wait_until(deadline);
    FOLLY_SAFE_DCHECK(res, "infinity time has passed");
  }

Member Data Documentation

template<typename Handoff, template< typename > class Atom = std::atomic>

CachelinePadded<folly::AtomicStruct<LifoSemHead, Atom> > folly::detail::LifoSemBase< Handoff, Atom >::head_

private

Definition at line 580 of file LifoSem.h.

---

The documentation for this struct was generated from the following file:

• proxygen/folly/folly/synchronization/LifoSem.h