2 * Copyright 2015 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.
22 #include <boost/noncopyable.hpp>
26 #include <folly/detail/Futex.h>
27 #include <folly/detail/MemoryIdler.h>
31 /// A Baton allows a thread to block once and be awoken: it captures
32 /// a single handoff. During its lifecycle (from construction/reset to
33 /// destruction/reset) a baton must either be post()ed and wait()ed exactly
34 /// once each, or not at all.
36 /// Baton includes no internal padding, and is only 4 bytes in size.
37 /// Any alignment or padding to avoid false sharing is up to the user.
39 /// This is basically a stripped-down semaphore that supports only a
40 /// single call to sem_post and a single call to sem_wait. The current
41 /// posix semaphore sem_t isn't too bad, but this provides more a bit more
42 /// speed, inlining, smaller size, a guarantee that the implementation
43 /// won't change, and compatibility with DeterministicSchedule. By having
44 /// a much more restrictive lifecycle we can also add a bunch of assertions
45 /// that can help to catch race conditions ahead of time.
46 template <template<typename> class Atom = std::atomic>
47 struct Baton : boost::noncopyable {
48 Baton() : state_(INIT) {}
50 /// It is an error to destroy a Baton on which a thread is currently
51 /// wait()ing. In practice this means that the waiter usually takes
52 /// responsibility for destroying the Baton.
54 // The docblock for this function says that it can't be called when
55 // there is a concurrent waiter. We assume a strong version of this
56 // requirement in which the caller must _know_ that this is true, they
57 // are not allowed to be merely lucky. If two threads are involved,
58 // the destroying thread must actually have synchronized with the
59 // waiting thread after wait() returned. To convey causality the the
60 // waiting thread must have used release semantics and the destroying
61 // thread must have used acquire semantics for that communication,
62 // so we are guaranteed to see the post-wait() value of state_,
63 // which cannot be WAITING.
65 // Note that since we only care about a single memory location,
66 // the only two plausible memory orders here are relaxed and seq_cst.
67 assert(state_.load(std::memory_order_relaxed) != WAITING);
70 /// Equivalent to destroying the Baton and creating a new one. It is
71 /// a bug to call this while there is a waiting thread, so in practice
72 /// the waiter will be the one that resets the baton.
74 // See ~Baton for a discussion about why relaxed is okay here
75 assert(state_.load(std::memory_order_relaxed) != WAITING);
77 // We use a similar argument to justify the use of a relaxed store
78 // here. Since both wait() and post() are required to be called
79 // only once per lifetime, no thread can actually call those methods
80 // correctly after a reset() unless it synchronizes with the thread
81 // that performed the reset(). If a post() or wait() on another thread
82 // didn't synchronize, then regardless of what operation we performed
83 // here there would be a race on proper use of the Baton's spec
84 // (although not on any particular load and store). Put another way,
85 // we don't need to synchronize here because anybody that might rely
86 // on such synchronization is required by the baton rules to perform
87 // an additional synchronization that has the desired effect anyway.
89 // There is actually a similar argument to be made about the
90 // constructor, in which the fenceless constructor initialization
91 // of state_ is piggybacked on whatever synchronization mechanism
92 // distributes knowledge of the Baton's existence
93 state_.store(INIT, std::memory_order_relaxed);
96 /// Causes wait() to wake up. For each lifetime of a Baton (where a
97 /// lifetime starts at construction or reset() and ends at destruction
98 /// or reset()) there can be at most one call to post(). Any thread
101 /// Although we could implement a more generic semaphore semantics
102 /// without any extra size or CPU overhead, the single-call limitation
103 /// allows us to have better assert-ions during debug builds.
105 uint32_t before = state_.load(std::memory_order_acquire);
107 assert(before == INIT || before == WAITING || before == TIMED_OUT);
109 if (before == INIT &&
110 state_.compare_exchange_strong(before, EARLY_DELIVERY)) {
114 assert(before == WAITING || before == TIMED_OUT);
116 if (before == TIMED_OUT) {
120 assert(before == WAITING);
121 state_.store(LATE_DELIVERY, std::memory_order_release);
125 /// Waits until post() has been called in the current Baton lifetime.
126 /// May be called at most once during a Baton lifetime (construction
127 /// |reset until destruction|reset). If post is called before wait in
128 /// the current lifetime then this method returns immediately.
130 /// The restriction that there can be at most one wait() per lifetime
131 /// could be relaxed somewhat without any perf or size regressions,
132 /// but by making this condition very restrictive we can provide better
133 /// checking in debug builds.
135 if (spinWaitForEarlyDelivery()) {
136 assert(state_.load(std::memory_order_acquire) == EARLY_DELIVERY);
140 // guess we have to block :(
141 uint32_t expected = INIT;
142 if (!state_.compare_exchange_strong(expected, WAITING)) {
143 // CAS failed, last minute reprieve
144 assert(expected == EARLY_DELIVERY);
149 detail::MemoryIdler::futexWait(state_, WAITING);
151 // state_ is the truth even if FUTEX_WAIT reported a matching
152 // FUTEX_WAKE, since we aren't using type-stable storage and we
153 // don't guarantee reuse. The scenario goes like this: thread
154 // A's last touch of a Baton is a call to wake(), which stores
155 // LATE_DELIVERY and gets an unlucky context switch before delivering
156 // the corresponding futexWake. Thread B sees LATE_DELIVERY
157 // without consuming a futex event, because it calls futexWait
158 // with an expected value of WAITING and hence doesn't go to sleep.
159 // B returns, so the Baton's memory is reused and becomes another
160 // Baton (or a reuse of this one). B calls futexWait on the new
161 // Baton lifetime, then A wakes up and delivers a spurious futexWake
162 // to the same memory location. B's futexWait will then report a
163 // consumed wake event even though state_ is still WAITING.
165 // It would be possible to add an extra state_ dance to communicate
166 // that the futexWake has been sent so that we can be sure to consume
167 // it before returning, but that would be a perf and complexity hit.
168 uint32_t s = state_.load(std::memory_order_acquire);
169 assert(s == WAITING || s == LATE_DELIVERY);
171 if (s == LATE_DELIVERY) {
178 /// Similar to wait, but with a timeout. The thread is unblocked if the
180 /// Note: Only a single call to timed_wait/wait is allowed during a baton's
181 /// life-cycle (from construction/reset to destruction/reset). In other
182 /// words, after timed_wait the caller can't invoke wait/timed_wait/try_wait
183 /// again on the same baton without resetting it.
185 /// @param deadline Time until which the thread can block
186 /// @return true if the baton was posted to before timeout,
188 template <typename Clock, typename Duration = typename Clock::duration>
189 bool timed_wait(const std::chrono::time_point<Clock,Duration>& deadline) {
190 if (spinWaitForEarlyDelivery()) {
191 assert(state_.load(std::memory_order_acquire) == EARLY_DELIVERY);
195 // guess we have to block :(
196 uint32_t expected = INIT;
197 if (!state_.compare_exchange_strong(expected, WAITING)) {
198 // CAS failed, last minute reprieve
199 assert(expected == EARLY_DELIVERY);
204 auto rv = state_.futexWaitUntil(WAITING, deadline);
205 if (rv == folly::detail::FutexResult::TIMEDOUT) {
206 state_.store(TIMED_OUT, std::memory_order_release);
210 uint32_t s = state_.load(std::memory_order_acquire);
211 assert(s == WAITING || s == LATE_DELIVERY);
212 if (s == LATE_DELIVERY) {
218 /// Similar to wait, but doesn't block the thread if it hasn't been posted.
220 /// try_wait has the following semantics:
221 /// - It is ok to call try_wait any number times on the same baton until
222 /// try_wait reports that the baton has been posted.
223 /// - It is ok to call timed_wait or wait on the same baton if try_wait
224 /// reports that baton hasn't been posted.
225 /// - If try_wait indicates that the baton has been posted, it is invalid to
226 /// call wait, try_wait or timed_wait on the same baton without resetting
228 /// @return true if baton has been posted, false othewise
230 auto s = state_.load(std::memory_order_acquire);
231 assert(s == INIT || s == EARLY_DELIVERY);
232 return s == EARLY_DELIVERY;
236 enum State : uint32_t {
245 // Must be positive. If multiple threads are actively using a
246 // higher-level data structure that uses batons internally, it is
247 // likely that the post() and wait() calls happen almost at the same
248 // time. In this state, we lose big 50% of the time if the wait goes
249 // to sleep immediately. On circa-2013 devbox hardware it costs about
250 // 7 usec to FUTEX_WAIT and then be awoken (half the t/iter as the
251 // posix_sem_pingpong test in BatonTests). We can improve our chances
252 // of EARLY_DELIVERY by spinning for a bit, although we have to balance
253 // this against the loss if we end up sleeping any way. Spins on this
254 // hw take about 7 nanos (all but 0.5 nanos is the pause instruction).
255 // We give ourself 300 spins, which is about 2 usec of waiting. As a
256 // partial consolation, since we are using the pause instruction we
257 // are giving a speed boost to the colocated hyperthread.
258 PreBlockAttempts = 300,
261 // Spin for "some time" (see discussion on PreBlockAttempts) waiting
264 // @return true if we received an early delivery during the wait,
265 // false otherwise. If the function returns true then
266 // state_ is guaranteed to be EARLY_DELIVERY
267 bool spinWaitForEarlyDelivery() {
269 static_assert(PreBlockAttempts > 0,
270 "isn't this assert clearer than an uninitialized variable warning?");
271 for (int i = 0; i < PreBlockAttempts; ++i) {
277 // The pause instruction is the polite way to spin, but it doesn't
278 // actually affect correctness to omit it if we don't have it.
279 // Pausing donates the full capabilities of the current core to
280 // its other hyperthreads for a dozen cycles or so
281 asm volatile ("pause");
288 detail::Futex<Atom> state_;