Event count

A standalone adaptation of folly::EventCount utilizing C++20’s atomic wait facilities.

This file has been adapted from:

class event_count : private lf::impl::immovable<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 prepare_wait() before checking your condition and then either cancel_wait() or wait() depending on whether the condition was true. When another thread makes the condition true, it must call notify() / notify_all() 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 prepare_wait.

• E2: T1 calls wait (obviously E1 < E2, intra-thread).

• E3: T2 calls notify_all().

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 event_count in the following manner:

Waiter:

if (!condition()) {  // handle fast path first
  for (;;) {

    auto key = eventCount.prepare_wait();

    if (condition()) {
      eventCount.cancel_wait();
      break;
    } else {
      eventCount.wait(key);
    }
  }
}

(This pattern is encapsulated in the await() method.)

Poster:

make_condition_true();
eventCount.notify_all();

Note

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.

Public Functions

template<typename Pred>
void await(Pred const &condition) noexcept(std::is_nothrow_invocable_r_v<bool, Pred const&>)

Wait for condition() to become true.

Cleans up appropriately if condition() throws, and then rethrow.

inline auto cancel_wait() noexcept -> void

Cancel a wait that was prepared with prepare_wait().

inline auto notify_all() noexcept -> void

Wake up all waiters.

inline auto notify_one() noexcept -> void

Wake up one waiter.

inline auto prepare_wait() noexcept -> key

Prepare to wait.

Once this has been called, you must either call wait() with the key or cancel_wait().

inline auto wait(key in_key) noexcept -> void

Wait for a notification, this blocks the current thread.

class key

The return type of prepare_wait().