folly/Baton.h

   1 /*
   2  * Copyright 2014 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 #ifndef FOLLY_BATON_H
  18 #define FOLLY_BATON_H
  19
  20 #include <stdint.h>
  21 #include <atomic>
  22 #include <boost/noncopyable.hpp>
  23 #include <errno.h>
  24 #include <assert.h>
  25
  26 #include <folly/detail/Futex.h>
  27 #include <folly/detail/MemoryIdler.h>
  28
  29 namespace folly {
  30
  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.
  35 ///
  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.
  38 ///
  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) {}
  49
  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.
  53   ~Baton() {
  54     // The docblock for this function says that is 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.
  64     //
  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);
  68   }
  69
  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.
  73   void reset() {
  74     // See ~Baton for a discussion about why relaxed is okay here
  75     assert(state_.load(std::memory_order_relaxed) != WAITING);
  76
  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.
  88     //
  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);
  94   }
  95
  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
  99   /// may call post().
 100   ///
 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.
 104   void post() {
 105     uint32_t before = state_.load(std::memory_order_acquire);
 106     assert(before == INIT || before == WAITING);
 107     if (before != INIT ||
 108         !state_.compare_exchange_strong(before, EARLY_DELIVERY)) {
 109       // we didn't get to state_ before wait(), so we need to call futex()
 110       assert(before == WAITING);
 111
 112       state_.store(LATE_DELIVERY, std::memory_order_release);
 113       state_.futexWake(1);
 114     }
 115   }
 116
 117   /// Waits until post() has been called in the current Baton lifetime.
 118   /// May be called at most once during a Baton lifetime (construction
 119   /// |reset until destruction|reset).  If post is called before wait in
 120   /// the current lifetime then this method returns immediately.
 121   ///
 122   /// The restriction that there can be at most one wait() per lifetime
 123   /// could be relaxed somewhat without any perf or size regressions,
 124   /// but by making this condition very restrictive we can provide better
 125   /// checking in debug builds.
 126   void wait() {
 127     uint32_t before;
 128
 129     static_assert(PreBlockAttempts > 0,
 130         "isn't this assert clearer than an uninitialized variable warning?");
 131     for (int i = 0; i < PreBlockAttempts; ++i) {
 132       before = state_.load(std::memory_order_acquire);
 133       if (before == EARLY_DELIVERY) {
 134         // hooray!
 135         return;
 136       }
 137       assert(before == INIT);
 138 #if FOLLY_X64
 139       // The pause instruction is the polite way to spin, but it doesn't
 140       // actually affect correctness to omit it if we don't have it.
 141       // Pausing donates the full capabilities of the current core to
 142       // its other hyperthreads for a dozen cycles or so
 143       asm volatile ("pause");
 144 #endif
 145     }
 146
 147     // guess we have to block :(
 148     if (!state_.compare_exchange_strong(before, WAITING)) {
 149       // CAS failed, last minute reprieve
 150       assert(before == EARLY_DELIVERY);
 151       return;
 152     }
 153
 154     while (true) {
 155       detail::MemoryIdler::futexWait(state_, WAITING);
 156
 157       // state_ is the truth even if FUTEX_WAIT reported a matching
 158       // FUTEX_WAKE, since we aren't using type-stable storage and we
 159       // don't guarantee reuse.  The scenario goes like this: thread
 160       // A's last touch of a Baton is a call to wake(), which stores
 161       // LATE_DELIVERY and gets an unlucky context switch before delivering
 162       // the corresponding futexWake.  Thread B sees LATE_DELIVERY
 163       // without consuming a futex event, because it calls futexWait
 164       // with an expected value of WAITING and hence doesn't go to sleep.
 165       // B returns, so the Baton's memory is reused and becomes another
 166       // Baton (or a reuse of this one).  B calls futexWait on the new
 167       // Baton lifetime, then A wakes up and delivers a spurious futexWake
 168       // to the same memory location.  B's futexWait will then report a
 169       // consumed wake event even though state_ is still WAITING.
 170       //
 171       // It would be possible to add an extra state_ dance to communicate
 172       // that the futexWake has been sent so that we can be sure to consume
 173       // it before returning, but that would be a perf and complexity hit.
 174       uint32_t s = state_.load(std::memory_order_acquire);
 175       assert(s == WAITING || s == LATE_DELIVERY);
 176
 177       if (s == LATE_DELIVERY) {
 178         return;
 179       }
 180       // retry
 181     }
 182   }
 183
 184  private:
 185   enum State : uint32_t {
 186     INIT = 0,
 187     EARLY_DELIVERY = 1,
 188     WAITING = 2,
 189     LATE_DELIVERY = 3,
 190   };
 191
 192   enum {
 193     // Must be positive.  If multiple threads are actively using a
 194     // higher-level data structure that uses batons internally, it is
 195     // likely that the post() and wait() calls happen almost at the same
 196     // time.  In this state, we lose big 50% of the time if the wait goes
 197     // to sleep immediately.  On circa-2013 devbox hardware it costs about
 198     // 7 usec to FUTEX_WAIT and then be awoken (half the t/iter as the
 199     // posix_sem_pingpong test in BatonTests).  We can improve our chances
 200     // of EARLY_DELIVERY by spinning for a bit, although we have to balance
 201     // this against the loss if we end up sleeping any way.  Spins on this
 202     // hw take about 7 nanos (all but 0.5 nanos is the pause instruction).
 203     // We give ourself 300 spins, which is about 2 usec of waiting.  As a
 204     // partial consolation, since we are using the pause instruction we
 205     // are giving a speed boost to the colocated hyperthread.
 206     PreBlockAttempts = 300,
 207   };
 208
 209   detail::Futex<Atom> state_;
 210 };
 211
 212 } // namespace folly
 213
 214 #endif