folly/Baton.h

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