2 * Copyright 2014 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_
22 #include <linux/futex.h>
29 #include <folly/Bits.h>
30 #include <folly/Likely.h>
37 inline int futex(int* uaddr, int op, int val, const timespec* timeout,
38 int* uaddr2, int val3) noexcept {
39 return syscall(SYS_futex, uaddr, op, val, timeout, uaddr2, val3);
45 * Event count: a condition variable for lock free algorithms.
47 * See http://www.1024cores.net/home/lock-free-algorithms/eventcounts for
50 * Event counts allow you to convert a non-blocking lock-free / wait-free
51 * algorithm into a blocking one, by isolating the blocking logic. You call
52 * prepareWait() before checking your condition and then either cancelWait()
53 * or wait() depending on whether the condition was true. When another
54 * thread makes the condition true, it must call notify() / notifyAll() just
55 * like a regular condition variable.
57 * If "<" denotes the happens-before relationship, consider 2 threads (T1 and
59 * - E1: T1 returns from prepareWait
61 * (obviously E1 < E2, intra-thread)
62 * - E3: T2 calls notifyAll
64 * If E1 < E3, then E2's wait will complete (and T1 will either wake up,
65 * or not block at all)
67 * This means that you can use an EventCount in the following manner:
70 * if (!condition()) { // handle fast path first
72 * auto key = eventCount.prepareWait();
74 * eventCount.cancelWait();
77 * eventCount.wait(key);
82 * (This pattern is encapsulated in await())
85 * make_condition_true();
86 * eventCount.notifyAll();
88 * Note that, just like with regular condition variables, the waiter needs to
89 * be tolerant of spurious wakeups and needs to recheck the condition after
90 * being woken up. Also, as there is no mutual exclusion implied, "checking"
91 * the condition likely means attempting an operation on an underlying
92 * data structure (push into a lock-free queue, etc) and returning true on
93 * success and false on failure.
97 EventCount() noexcept : val_(0) { }
100 friend class EventCount;
101 explicit Key(uint32_t e) noexcept : epoch_(e) { }
105 void notify() noexcept;
106 void notifyAll() noexcept;
107 Key prepareWait() noexcept;
108 void cancelWait() noexcept;
109 void wait(Key key) noexcept;
112 * Wait for condition() to become true. Will clean up appropriately if
113 * condition() throws, and then rethrow.
115 template <class Condition>
116 void await(Condition condition);
119 void doNotify(int n) noexcept;
120 EventCount(const EventCount&) = delete;
121 EventCount(EventCount&&) = delete;
122 EventCount& operator=(const EventCount&) = delete;
123 EventCount& operator=(EventCount&&) = delete;
125 // This requires 64-bit
126 static_assert(sizeof(int) == 4, "bad platform");
127 static_assert(sizeof(uint32_t) == 4, "bad platform");
128 static_assert(sizeof(uint64_t) == 8, "bad platform");
130 #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
131 static constexpr size_t kEpochOffset = 1;
132 #elif __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
133 static constexpr size_t kEpochOffset = 0; // in units of sizeof(int)
135 # error Your machine uses a weird endianness!
138 // val_ stores the epoch in the most significant 32 bits and the
139 // waiter count in the least significant 32 bits.
140 std::atomic<uint64_t> val_;
142 static constexpr uint64_t kAddWaiter = uint64_t(1);
143 static constexpr uint64_t kSubWaiter = uint64_t(-1);
144 static constexpr size_t kEpochShift = 32;
145 static constexpr uint64_t kAddEpoch = uint64_t(1) << kEpochShift;
146 static constexpr uint64_t kWaiterMask = kAddEpoch - 1;
149 inline void EventCount::notify() noexcept {
153 inline void EventCount::notifyAll() noexcept {
157 inline void EventCount::doNotify(int n) noexcept {
158 uint64_t prev = val_.fetch_add(kAddEpoch, std::memory_order_acq_rel);
159 if (UNLIKELY(prev & kWaiterMask)) {
160 detail::futex(reinterpret_cast<int*>(&val_) + kEpochOffset,
161 FUTEX_WAKE, n, nullptr, nullptr, 0);
165 inline EventCount::Key EventCount::prepareWait() noexcept {
166 uint64_t prev = val_.fetch_add(kAddWaiter, std::memory_order_acq_rel);
167 return Key(prev >> kEpochShift);
170 inline void EventCount::cancelWait() noexcept {
171 // memory_order_relaxed would suffice for correctness, but the faster
172 // #waiters gets to 0, the less likely it is that we'll do spurious wakeups
173 // (and thus system calls).
174 uint64_t prev = val_.fetch_add(kSubWaiter, std::memory_order_seq_cst);
175 assert((prev & kWaiterMask) != 0);
178 inline void EventCount::wait(Key key) noexcept {
179 while ((val_.load(std::memory_order_acquire) >> kEpochShift) == key.epoch_) {
180 detail::futex(reinterpret_cast<int*>(&val_) + kEpochOffset,
181 FUTEX_WAIT, key.epoch_, nullptr, nullptr, 0);
183 // memory_order_relaxed would suffice for correctness, but the faster
184 // #waiters gets to 0, the less likely it is that we'll do spurious wakeups
185 // (and thus system calls)
186 uint64_t prev = val_.fetch_add(kSubWaiter, std::memory_order_seq_cst);
187 assert((prev & kWaiterMask) != 0);
190 template <class Condition>
191 void EventCount::await(Condition condition) {
192 if (condition()) return; // fast path
194 // condition() is the only thing that may throw, everything else is
195 // noexcept, so we can hoist the try/catch block outside of the loop
198 auto key = prepareWait();
214 #endif /* FOLLY_EXPERIMENTAL_EVENTCOUNT_H_ */