folly::SaturatingSemaphore< MayBlock, Atom > Class Template Reference

#include <SaturatingSemaphore.h>

Public Member Functions
constexpr	SaturatingSemaphore () noexcept
	~SaturatingSemaphore ()
FOLLY_ALWAYS_INLINE bool	ready () const noexcept
void	reset () noexcept
FOLLY_ALWAYS_INLINE void	post () noexcept
FOLLY_ALWAYS_INLINE void	wait (const WaitOptions &opt=wait_options()) noexcept
FOLLY_ALWAYS_INLINE bool	try_wait () noexcept
template<typename Clock , typename Duration >
FOLLY_ALWAYS_INLINE bool	try_wait_until (const std::chrono::time_point< Clock, Duration > &deadline, const WaitOptions &opt=wait_options()) noexcept
template<class Rep , class Period >
FOLLY_ALWAYS_INLINE bool	try_wait_for (const std::chrono::duration< Rep, Period > &duration, const WaitOptions &opt=wait_options()) noexcept
template<typename Clock , typename Duration >
FOLLY_NOINLINE bool	tryWaitSlow (const std::chrono::time_point< Clock, Duration > &deadline, const WaitOptions &opt) noexcept

Static Public Member Functions
static FOLLY_ALWAYS_INLINE WaitOptions	wait_options ()

Private Types
enum	State : uint32_t { NOTREADY = 0, READY = 1, BLOCKED = 2 }

Private Member Functions
FOLLY_ALWAYS_INLINE void	postFastWaiterMayBlock () noexcept
void	postSlowWaiterMayBlock (uint32_t before) noexcept
template<typename Clock , typename Duration >
bool	tryWaitSlow (const std::chrono::time_point< Clock, Duration > &deadline, const WaitOptions &opt) noexcept

Private Attributes
detail::Futex< Atom >	state_

Detailed Description

template<bool MayBlock, template< typename > class Atom = std::atomic>
class folly::SaturatingSemaphore< MayBlock, Atom >

SaturatingSemaphore is a flag that allows concurrent posting by multiple posters and concurrent non-destructive waiting by multiple waiters.

A SaturatingSemaphore allows one or more waiter threads to check, spin, or block, indefinitely or with timeout, for a flag to be set by one or more poster threads. By setting the flag, posters announce to waiters (that may be already waiting or will check the flag in the future) that some condition is true. Posts to an already set flag are idempotent.

SaturatingSemaphore is called so because it behaves like a hybrid binary/counted semaphore with values zero and infinity, and post() and wait() functions. It is called saturating because one post() is enough to set it to infinity and to satisfy any number of wait()-s. Once set (to infinity) it remains unchanged by subsequent post()-s and wait()-s, until it is reset() back to zero.

The implementation of SaturatingSemaphore is based on that of Baton. It includes no internal padding, and is only 4 bytes in size. Any alignment or padding to avoid false sharing is up to the user. SaturatingSemaphore differs from Baton as follows:

• Baton allows at most one call to post(); this allows any number and concurrently.
• Baton allows at most one successful call to any wait variant; this allows any number and concurrently.

Template parameter:

• bool MayBlock: If false, waiting operations spin only. If true, timed and wait operations may block; adds an atomic instruction to the critical path of posters.

Wait options: WaitOptions contains optional per call setting for spin-max duration: Calls to wait(), try_wait_until(), and try_wait_for() block only after the passage of the spin-max period. The default spin-max duration is 10 usec. The spin-max option is applicable only if MayBlock is true.

Functions: bool ready(): Returns true if the flag is set by a call to post, otherwise false. Equivalent to try_wait, but available on const receivers. void reset(); Clears the flag. void post(); Sets the flag and wakes all current waiters, i.e., causes all concurrent calls to wait, try_wait_for, and try_wait_until to return. void wait( WaitOptions opt = wait_options()); Waits for the flag to be set by a call to post. bool try_wait(); Returns true if the flag is set by a call to post, otherwise false. bool try_wait_until( time_point& deadline, WaitOptions& = wait_options()); Returns true if the flag is set by a call to post before the deadline, otherwise false. bool try_wait_for( duration&, WaitOptions& = wait_options()); Returns true if the flag is set by a call to post before the expiration of the specified duration, otherwise false.

Usage:

SaturatingSemaphore</* MayBlock = */ true> f;
ASSERT_FALSE(f.try_wait());
ASSERT_FALSE(f.try_wait_until(
    std::chrono::steady_clock::now() + std::chrono::microseconds(1)));
ASSERT_FALSE(f.try_wait_until(
    std::chrono::steady_clock::now() + std::chrono::microseconds(1),
    f.wait_options().spin_max(std::chrono::microseconds(1))));
f.post();
f.post();
f.wait();
f.wait(f.wait_options().spin_max(std::chrono::nanoseconds(100)));
ASSERT_TRUE(f.try_wait());
ASSERT_TRUE(f.try_wait_until(
    std::chrono::steady_clock::now() + std::chrono::microseconds(1)));
f.wait();
f.reset();
ASSERT_FALSE(f.try_wait());

Definition at line 120 of file SaturatingSemaphore.h.

Member Enumeration Documentation

template<bool MayBlock, template< typename > class Atom = std::atomic>

enum folly::SaturatingSemaphore::State : uint32_t

private

Enumerator
NOTREADY
READY
BLOCKED

Definition at line 123 of file SaturatingSemaphore.h.

             : uint32_t {
    NOTREADY = 0,
    READY = 1,
    BLOCKED = 2,
  };

Constructor & Destructor Documentation

template<bool MayBlock, template< typename > class Atom = std::atomic>

constexpr folly::SaturatingSemaphore< MayBlock, Atom >::SaturatingSemaphore ( )

inlinenoexcept

constructor

Definition at line 135 of file SaturatingSemaphore.h.

: state_(NOTREADY) {}

template<bool MayBlock, template< typename > class Atom = std::atomic>

folly::SaturatingSemaphore< MayBlock, Atom >::~SaturatingSemaphore ( )

inline

destructor

Definition at line 138 of file SaturatingSemaphore.h.

{}

Member Function Documentation

template<bool MayBlock, template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE void folly::SaturatingSemaphore< MayBlock, Atom >::post ( )

inlinenoexcept

post

Definition at line 151 of file SaturatingSemaphore.h.

Referenced by folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::Entry::putItem(), run_basic_test(), run_multi_poster_multi_waiter_test(), folly::FlatCombining< T, Mutex, Atom, Req >::Rec::setDisconnected(), folly::FlatCombining< T, Mutex, Atom, Req >::Rec::setDone(), folly::FlatCombining< FcSimpleExample< Mutex, Atom >, Mutex, Atom >::setPending(), folly::FlatCombining< T, Mutex, Atom, Req >::Rec::setValid(), and TEST_F().

                                           {
    if (!MayBlock) {
      state_.store(READY, std::memory_order_release);
    } else {
      postFastWaiterMayBlock();
    }
  }

template<bool MayBlock, template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE void folly::SaturatingSemaphore< MayBlock, Atom >::postFastWaiterMayBlock ( )

inlineprivatenoexcept

Definition at line 194 of file SaturatingSemaphore.h.

Referenced by folly::SaturatingSemaphore< true, Atom >::post().

                                                             {
    uint32_t before = NOTREADY;
    if (LIKELY(state_.compare_exchange_strong(
            before,
            READY,
            std::memory_order_release,
            std::memory_order_relaxed))) {
      return;
    }
    postSlowWaiterMayBlock(before);
  }

template<bool MayBlock, template< typename > class Atom>

FOLLY_NOINLINE void folly::SaturatingSemaphore< MayBlock, Atom >::postSlowWaiterMayBlock ( uint32_t  before )

privatenoexcept

Member function definitioonspostSlowWaiterMayBlock

Definition at line 220 of file SaturatingSemaphore.h.

References folly::SaturatingSemaphore< MayBlock, Atom >::BLOCKED, folly::detail::futexWake(), folly::SaturatingSemaphore< MayBlock, Atom >::NOTREADY, and folly::SaturatingSemaphore< MayBlock, Atom >::READY.

Referenced by folly::SaturatingSemaphore< true, Atom >::postFastWaiterMayBlock().

                              {
  while (true) {
    if (before == NOTREADY) {
      if (state_.compare_exchange_strong(
              before,
              READY,
              std::memory_order_release,
              std::memory_order_relaxed)) {
        return;
      }
    }
    if (before == READY) { // Only if multiple posters
      // The reason for not simply returning (without the following
      // steps) is to prevent the following case:
      //
      //  T1:             T2:             T3:
      //  local1.post();  local2.post();  global.wait();
      //  global.post();  global.post();  global.reset();
      //                                  seq_cst fence
      //                                  local1.try_wait() == true;
      //                                  local2.try_wait() == false;
      //
      // This following steps correspond to T2's global.post(), where
      // global is already posted by T1.
      //
      // The following fence and load guarantee that T3 does not miss
      // T2's prior stores, i.e., local2.post() in this example.
      //
      // The following case is prevented:
      //
      // Starting with local2 == NOTREADY and global == READY
      //
      // T2:                              T3:
      // store READY to local2 // post    store NOTREADY to global // reset
      // seq_cst fenc                     seq_cst fence
      // load READY from global // post   load NOTREADY from local2 // try_wait
      //
      std::atomic_thread_fence(std::memory_order_seq_cst);
      before = state_.load(std::memory_order_relaxed);
      if (before == READY) {
        return;
      }
      continue;
    }
    DCHECK_EQ(before, BLOCKED);
    if (state_.compare_exchange_strong(
            before,
            READY,
            std::memory_order_release,
            std::memory_order_relaxed)) {
      detail::futexWake(&state_);
      return;
    }
  }
}

template<bool MayBlock, template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE bool folly::SaturatingSemaphore< MayBlock, Atom >::ready ( ) const

inlinenoexcept

ready

Definition at line 141 of file SaturatingSemaphore.h.

Referenced by folly::FlatCombining< T, Mutex, Atom, Req >::Rec::isDisconnected(), folly::FlatCombining< T, Mutex, Atom, Req >::Rec::isDone(), folly::FlatCombining< FcSimpleExample< Mutex, Atom >, Mutex, Atom >::isPending(), folly::FlatCombining< T, Mutex, Atom, Req >::Rec::isValid(), run_basic_test(), run_multi_poster_multi_waiter_test(), folly::SaturatingSemaphore< true, Atom >::try_wait(), and folly::SaturatingSemaphore< MayBlock, Atom >::tryWaitSlow().

                                                  {
    return state_.load(std::memory_order_acquire) == READY;
  }

template<bool MayBlock, template< typename > class Atom = std::atomic>

void folly::SaturatingSemaphore< MayBlock, Atom >::reset ( )

inlinenoexcept

reset

Definition at line 146 of file SaturatingSemaphore.h.

Referenced by folly::FlatCombining< T, Mutex, Atom, Req >::Rec::clearDisconnected(), folly::FlatCombining< T, Mutex, Atom, Req >::Rec::clearDone(), folly::FlatCombining< FcSimpleExample< Mutex, Atom >, Mutex, Atom >::clearPending(), folly::FlatCombining< T, Mutex, Atom, Req >::Rec::clearValid(), run_basic_test(), and TEST_F().

                        {
    state_.store(NOTREADY, std::memory_order_relaxed);
  }

template<bool MayBlock, template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE bool folly::SaturatingSemaphore< MayBlock, Atom >::try_wait ( )

inlinenoexcept

try_wait

Definition at line 166 of file SaturatingSemaphore.h.

Referenced by run_basic_test(), run_multi_poster_multi_waiter_test(), folly::SaturatingSemaphore< true, Atom >::try_wait_for(), and folly::SaturatingSemaphore< true, Atom >::try_wait_until().

                                               {
    return ready();
  }

template<bool MayBlock, template< typename > class Atom = std::atomic>

template<class Rep , class Period >

FOLLY_ALWAYS_INLINE bool folly::SaturatingSemaphore< MayBlock, Atom >::try_wait_for ( const std::chrono::duration< Rep, Period > &  duration, const WaitOptions &  opt = wait_options()  )

inlinenoexcept

try_wait_for

Definition at line 183 of file SaturatingSemaphore.h.

Referenced by run_multi_poster_multi_waiter_test().

                                                        {
    if (LIKELY(try_wait())) {
      return true;
    }
    auto deadline = std::chrono::steady_clock::now() + duration;
    return tryWaitSlow(deadline, opt);
  }

template<bool MayBlock, template< typename > class Atom = std::atomic>

template<typename Clock , typename Duration >

FOLLY_ALWAYS_INLINE bool folly::SaturatingSemaphore< MayBlock, Atom >::try_wait_until ( const std::chrono::time_point< Clock, Duration > &  deadline, const WaitOptions &  opt = wait_options()  )

inlinenoexcept

try_wait_until

Definition at line 172 of file SaturatingSemaphore.h.

Referenced by run_basic_test(), run_multi_poster_multi_waiter_test(), TEST_F(), folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::Entry::tryWaitUntil(), and folly::SaturatingSemaphore< true, Atom >::wait().

                                                        {
    if (LIKELY(try_wait())) {
      return true;
    }
    return tryWaitSlow(deadline, opt);
  }

template<bool MayBlock, template< typename > class Atom = std::atomic>

template<typename Clock , typename Duration >

bool folly::SaturatingSemaphore< MayBlock, Atom >::tryWaitSlow ( const std::chrono::time_point< Clock, Duration > &  deadline, const WaitOptions &  opt  )

privatenoexcept

Referenced by folly::SaturatingSemaphore< true, Atom >::postFastWaiterMayBlock(), folly::SaturatingSemaphore< true, Atom >::try_wait_for(), and folly::SaturatingSemaphore< true, Atom >::try_wait_until().

template<bool MayBlock, template< typename > class Atom = std::atomic>

template<typename Clock , typename Duration >

FOLLY_NOINLINE bool folly::SaturatingSemaphore< MayBlock, Atom >::tryWaitSlow ( const std::chrono::time_point< Clock, Duration > &  deadline, const WaitOptions &  opt  )

noexcept

tryWaitSlow

Definition at line 280 of file SaturatingSemaphore.h.

References folly::detail::advance, folly::SaturatingSemaphore< MayBlock, Atom >::BLOCKED, folly::detail::MemoryIdler::futexWaitUntil(), max, folly::SaturatingSemaphore< MayBlock, Atom >::NOTREADY, folly::SaturatingSemaphore< MayBlock, Atom >::READY, folly::SaturatingSemaphore< MayBlock, Atom >::ready(), folly::detail::spin_pause_until(), folly::detail::spin_yield_until(), folly::detail::success, folly::detail::TIMEDOUT, and folly::detail::timeout.

                                     {
  switch (detail::spin_pause_until(deadline, opt, [=] { return ready(); })) {
    case detail::spin_result::success:
      return true;
    case detail::spin_result::timeout:
      return false;
    case detail::spin_result::advance:
      break;
  }

  if (!MayBlock) {
    switch (detail::spin_yield_until(deadline, [=] { return ready(); })) {
      case detail::spin_result::success:
        return true;
      case detail::spin_result::timeout:
        return false;
      case detail::spin_result::advance:
        break;
    }
  }

  auto before = state_.load(std::memory_order_relaxed);
  while (before == NOTREADY &&
         !state_.compare_exchange_strong(
             before,
             BLOCKED,
             std::memory_order_relaxed,
             std::memory_order_relaxed)) {
    if (before == READY) {
      // TODO: move the acquire to the compare_exchange failure load after C++17
      std::atomic_thread_fence(std::memory_order_acquire);
      return true;
    }
  }

  while (true) {
    auto rv = detail::MemoryIdler::futexWaitUntil(state_, BLOCKED, deadline);
    if (rv == detail::FutexResult::TIMEDOUT) {
      assert(deadline != (std::chrono::time_point<Clock, Duration>::max()));
      return false;
    }

    if (ready()) {
      return true;
    }
  }
}

template<bool MayBlock, template< typename > class Atom = std::atomic>

FOLLY_ALWAYS_INLINE void folly::SaturatingSemaphore< MayBlock, Atom >::wait ( const WaitOptions &  opt = wait_options() )

inlinenoexcept

wait

Definition at line 161 of file SaturatingSemaphore.h.

Referenced by folly::FlatCombining< T, Mutex, Atom, Req >::Rec::awaitDone(), folly::FlatCombining< FcSimpleExample< Mutex, Atom >, Mutex, Atom >::awaitPending(), folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::Entry::peekItem(), run_basic_test(), run_multi_poster_multi_waiter_test(), and folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::Entry::takeItem().

                                                              {
    try_wait_until(std::chrono::steady_clock::time_point::max(), opt);
  }

template<bool MayBlock, template< typename > class Atom = std::atomic>

static FOLLY_ALWAYS_INLINE WaitOptions folly::SaturatingSemaphore< MayBlock, Atom >::wait_options ( )

inlinestatic

Definition at line 130 of file SaturatingSemaphore.h.

Referenced by run_basic_test(), run_multi_poster_multi_waiter_test(), and folly::UnboundedQueue< T, SingleProducer, SingleConsumer, MayBlock, LgSegmentSize, LgAlign, Atom >::Entry::tryWaitUntil().

                                                        {
    return {};
  }

Member Data Documentation

template<bool MayBlock, template< typename > class Atom = std::atomic>

detail::Futex<Atom> folly::SaturatingSemaphore< MayBlock, Atom >::state_

private

Definition at line 121 of file SaturatingSemaphore.h.

---

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

• proxygen/folly/folly/synchronization/SaturatingSemaphore.h