2 * Copyright 2012 Facebook, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
17 #ifndef FOLLY_EXPERIMENTAL_EVENTCOUNT_H_
18 #define FOLLY_EXPERIMENTAL_EVENTCOUNT_H_
21 #include <linux/futex.h>
32 inline int futex(int* uaddr, int op, int val, const timespec* timeout,
33 int* uaddr2, int val3) noexcept {
34 return syscall(SYS_futex, uaddr, op, val, timeout, uaddr2, val3);
40 * Event count: a condition variable for lock free algorithms.
42 * See http://www.1024cores.net/home/lock-free-algorithms/eventcounts for
45 * Event counts allow you to convert a non-blocking lock-free / wait-free
46 * algorithm into a blocking one, by isolating the blocking logic. You call
47 * prepareWait() before checking your condition and then either cancelWait()
48 * or wait() depending on whether the condition was true. When another
49 * thread makes the condition true, it must call notify() / notifyAll() just
50 * like a regular condition variable.
52 * If "<" denotes the happens-before relationship, consider 2 threads (T1 and
54 * - E1: T1 returns from prepareWait
56 * (obviously E1 < E2, intra-thread)
57 * - E3: T2 calls notifyAll
59 * If E1 < E3, then E2's wait will complete (and T1 will either wake up,
60 * or not block at all)
62 * This means that you can use an EventCount in the following manner:
65 * if (!condition()) { // handle fast path first
67 * auto key = eventCount.prepareWait();
69 * eventCount.cancelWait();
72 * eventCount.wait(key);
77 * (This pattern is encapsulated in await())
80 * make_condition_true();
81 * eventCount.notifyAll();
83 * Note that, just like with regular condition variables, the waiter needs to
84 * be tolerant of spurious wakeups and needs to recheck the condition after
85 * being woken up. Also, as there is no mutual exclusion implied, "checking"
86 * the condition likely means attempting an operation on an underlying
87 * data structure (push into a lock-free queue, etc) and returning true on
88 * success and false on failure.
92 EventCount() noexcept : epoch_(0), waiters_(0) { }
95 friend class EventCount;
96 explicit Key(int e) noexcept : epoch_(e) { }
100 void notify() noexcept;
101 void notifyAll() noexcept;
102 Key prepareWait() noexcept;
103 void cancelWait() noexcept;
104 void wait(Key key) noexcept;
107 * Wait for condition() to become true. Will clean up appropriately if
108 * condition() throws, and then rethrow.
110 template <class Condition>
111 void await(Condition condition);
114 void doNotify(int n) noexcept;
115 EventCount(const EventCount&) = delete;
116 EventCount(EventCount&&) = delete;
117 EventCount& operator=(const EventCount&) = delete;
118 EventCount& operator=(EventCount&&) = delete;
120 std::atomic<int> epoch_;
121 std::atomic<int> waiters_;
124 inline void EventCount::notify() noexcept {
128 inline void EventCount::notifyAll() noexcept {
132 inline void EventCount::doNotify(int n) noexcept {
133 // The order is important: epoch_ is incremented before waiters_ is checked.
134 // prepareWait() increments waiters_ before checking epoch_, so it is
135 // impossible to miss a wakeup.
138 detail::futex(reinterpret_cast<int*>(&epoch_), FUTEX_WAKE, n, nullptr,
143 inline EventCount::Key EventCount::prepareWait() noexcept {
148 inline void EventCount::cancelWait() noexcept {
152 inline void EventCount::wait(Key key) noexcept {
153 while (epoch_ == key.epoch_) {
154 detail::futex(reinterpret_cast<int*>(&epoch_), FUTEX_WAIT, key.epoch_,
155 nullptr, nullptr, 0);
160 template <class Condition>
161 void EventCount::await(Condition condition) {
162 if (condition()) return; // fast path
164 // condition() is the only thing that may throw, everything else is
165 // noexcept, so we can hoist the try/catch block outside of the loop
168 auto key = prepareWait();
184 #endif /* FOLLY_EXPERIMENTAL_EVENTCOUNT_H_ */