folly/synchronization/Baton.h

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