proxygen: folly::EventCount Class Reference

#include <EventCount.h>

Classes
class	Key

Public Member Functions
	EventCount () noexcept

void	notify () noexcept

void	notifyAll () noexcept

Key	prepareWait () noexcept

void	cancelWait () noexcept

void	wait (Key key) noexcept

template<class Condition >
void	await (Condition condition)

Private Member Functions
void	doNotify (int n) noexcept

	EventCount (const EventCount &)=delete

	EventCount (EventCount &&)=delete

EventCount &	operator= (const EventCount &)=delete

EventCount &	operator= (EventCount &&)=delete

Private Attributes
std::atomic< uint64_t >	val_

Static Private Attributes
static constexpr size_t	kEpochOffset = kIsLittleEndian ? 1 : 0

static constexpr uint64_t	kAddWaiter = uint64_t(1)

static constexpr uint64_t	kSubWaiter = uint64_t(-1)

static constexpr size_t	kEpochShift = 32

static constexpr uint64_t	kAddEpoch = uint64_t(1) << kEpochShift

static constexpr uint64_t	kWaiterMask = kAddEpoch - 1

Detailed Description

Event count: a condition variable for lock free algorithms.

See http://www.1024cores.net/home/lock-free-algorithms/eventcounts for details.

Event counts allow you to convert a non-blocking lock-free / wait-free algorithm into a blocking one, by isolating the blocking logic. You call prepareWait() before checking your condition and then either cancelWait() or wait() depending on whether the condition was true. When another thread makes the condition true, it must call notify() / notifyAll() just like a regular condition variable.

If "<" denotes the happens-before relationship, consider 2 threads (T1 and T2) and 3 events:

E1: T1 returns from prepareWait
E2: T1 calls wait (obviously E1 < E2, intra-thread)
E3: T2 calls notifyAll

If E1 < E3, then E2's wait will complete (and T1 will either wake up, or not block at all)

This means that you can use an EventCount in the following manner:

Waiter: if (!condition()) { // handle fast path first for (;;) { auto key = eventCount.prepareWait(); if (condition()) { eventCount.cancelWait(); break; } else { eventCount.wait(key); } } }

(This pattern is encapsulated in await())

Poster: make_condition_true(); eventCount.notifyAll();

Note that, just like with regular condition variables, the waiter needs to be tolerant of spurious wakeups and needs to recheck the condition after being woken up. Also, as there is no mutual exclusion implied, "checking" the condition likely means attempting an operation on an underlying data structure (push into a lock-free queue, etc) and returning true on success and false on failure.

Definition at line 84 of file EventCount.h.

Constructor & Destructor Documentation

folly::EventCount::EventCount ( )

inlinenoexcept

Definition at line 86 of file EventCount.h.

86 : val_(0) {}

folly::EventCount::val_

std::atomic< uint64_t > val_

Definition: EventCount.h:125

folly::EventCount::EventCount ( const EventCount & )

privatedelete

folly::EventCount::EventCount ( EventCount && )

privatedelete

Member Function Documentation

template<class Condition >

void folly::EventCount::await ( Condition condition )

Wait for condition() to become true. Will clean up appropriately if condition() throws, and then rethrow.

Definition at line 177 of file EventCount.h.

References cancelWait(), prepareWait(), and wait().

                                           {
   if (condition()) {
     return; // fast path
   }
 
   // condition() is the only thing that may throw, everything else is
   // noexcept, so we can hoist the try/catch block outside of the loop
   try {
     for (;;) {
       auto key = prepareWait();
       if (condition()) {
         cancelWait();
         break;
       } else {
         wait(key);
       }
     }
   } catch (...) {
     cancelWait();
     throw;
   }
 }

void folly::EventCount::cancelWait ( )

inlinenoexcept

Definition at line 155 of file EventCount.h.

References kSubWaiter, kWaiterMask, uint64_t, and val_.

Referenced by await(), folly::gen::detail::PMap< Predicate >::Generator< Value, Source, Input, Output >::ExecutionPipeline::predApplier(), and folly::gen::detail::ClosableMPMCQueue< InputDecayed >::writeUnlessClosed().

                                             {
   // memory_order_relaxed would suffice for correctness, but the faster
   // #waiters gets to 0, the less likely it is that we'll do spurious wakeups
   // (and thus system calls).
   uint64_t prev = val_.fetch_add(kSubWaiter, std::memory_order_seq_cst);
   DCHECK_NE((prev & kWaiterMask), 0);
 }

void folly::EventCount::doNotify ( int n )

inlineprivatenoexcept

Definition at line 142 of file EventCount.h.

References folly::detail::futexWake(), kAddEpoch, kEpochOffset, kWaiterMask, uint64_t, UNLIKELY, and val_.

Referenced by notify(), and notifyAll().

                                                {
   uint64_t prev = val_.fetch_add(kAddEpoch, std::memory_order_acq_rel);
   if (UNLIKELY(prev & kWaiterMask)) {
     detail::futexWake(
         reinterpret_cast<detail::Futex<std::atomic>*>(&val_) + kEpochOffset, n);
   }
 }

void folly::EventCount::notify ( )

inlinenoexcept

Definition at line 134 of file EventCount.h.

References doNotify().

Referenced by folly::gen::detail::PMap< Predicate >::Generator< Value, Source, Input, Output >::ExecutionPipeline::blockingWrite(), folly::gen::detail::ClosableMPMCQueue< InputDecayed >::readUnlessClosed(), folly::gen::detail::ClosableMPMCQueue< InputDecayed >::readUnlessEmpty(), folly::gen::detail::PMap< Predicate >::Generator< Value, Source, Input, Output >::ExecutionPipeline::write(), folly::gen::detail::ClosableMPMCQueue< InputDecayed >::writeUnlessClosed(), and folly::gen::detail::ClosableMPMCQueue< InputDecayed >::writeUnlessFull().

                                         {
   doNotify(1);
 }

void folly::EventCount::notifyAll ( )

inlinenoexcept

Definition at line 138 of file EventCount.h.

References doNotify().

Referenced by folly::gen::detail::ClosableMPMCQueue< InputDecayed >::closeInputProducer(), folly::gen::detail::ClosableMPMCQueue< InputDecayed >::closeOutputConsumer(), and folly::gen::detail::PMap< Predicate >::Generator< Value, Source, Input, Output >::ExecutionPipeline::stop().

                                            {
   doNotify(INT_MAX);
 }

EventCount& folly::EventCount::operator= ( const EventCount & )

privatedelete

EventCount& folly::EventCount::operator= ( EventCount && )

privatedelete

EventCount::Key folly::EventCount::prepareWait ( )

inlinenoexcept

Definition at line 150 of file EventCount.h.

References kAddWaiter, kEpochShift, folly::EventCount::Key::Key(), uint64_t, and val_.

Referenced by await(), folly::gen::detail::PMap< Predicate >::Generator< Value, Source, Input, Output >::ExecutionPipeline::predApplier(), folly::gen::detail::ClosableMPMCQueue< InputDecayed >::readUnlessClosed(), and folly::gen::detail::ClosableMPMCQueue< InputDecayed >::writeUnlessClosed().

                                                       {
   uint64_t prev = val_.fetch_add(kAddWaiter, std::memory_order_acq_rel);
   return Key(prev >> kEpochShift);
 }

void folly::EventCount::wait ( Key key )

inlinenoexcept

Definition at line 163 of file EventCount.h.

References folly::detail::futexWait(), kEpochOffset, kEpochShift, kSubWaiter, kWaiterMask, uint64_t, and val_.

                                              {
   while ((val_.load(std::memory_order_acquire) >> kEpochShift) == key.epoch_) {
     detail::futexWait(
         reinterpret_cast<detail::Futex<std::atomic>*>(&val_) + kEpochOffset,
         key.epoch_);
   }
   // memory_order_relaxed would suffice for correctness, but the faster
   // #waiters gets to 0, the less likely it is that we'll do spurious wakeups
   // (and thus system calls)
   uint64_t prev = val_.fetch_add(kSubWaiter, std::memory_order_seq_cst);
   DCHECK_NE((prev & kWaiterMask), 0);
 }

Member Data Documentation

constexpr uint64_t folly::EventCount::kAddEpoch = uint64_t(1) << kEpochShift

staticprivate

Definition at line 130 of file EventCount.h.

Referenced by doNotify().

constexpr uint64_t folly::EventCount::kAddWaiter = uint64_t(1)

staticprivate

Definition at line 127 of file EventCount.h.

Referenced by prepareWait().

constexpr size_t folly::EventCount::kEpochOffset = kIsLittleEndian ? 1 : 0

staticprivate

Definition at line 121 of file EventCount.h.

Referenced by doNotify(), and wait().

constexpr size_t folly::EventCount::kEpochShift = 32

staticprivate

Definition at line 129 of file EventCount.h.

Referenced by prepareWait(), and wait().

constexpr uint64_t folly::EventCount::kSubWaiter = uint64_t(-1)

staticprivate

Definition at line 128 of file EventCount.h.

Referenced by cancelWait(), and wait().

constexpr uint64_t folly::EventCount::kWaiterMask = kAddEpoch - 1

staticprivate

Definition at line 131 of file EventCount.h.

Referenced by cancelWait(), doNotify(), and wait().

std::atomic<uint64_t> folly::EventCount::val_

private

Definition at line 125 of file EventCount.h.

Referenced by cancelWait(), doNotify(), prepareWait(), and wait().

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

proxygen/folly/folly/experimental/EventCount.h

Classes

Public Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation