folly/experimental/EventCount.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 #ifndef FOLLY_EXPERIMENTAL_EVENTCOUNT_H_
  18 #define FOLLY_EXPERIMENTAL_EVENTCOUNT_H_
  19
  20 #include <unistd.h>
  21 #include <syscall.h>
  22 #include <linux/futex.h>
  23 #include <sys/time.h>
  24 #include <climits>
  25 #include <atomic>
  26 #include <thread>
  27 #include <glog/logging.h>
  28
  29 #include <folly/Bits.h>
  30 #include <folly/Likely.h>
  31
  32
  33 namespace folly {
  34
  35 namespace detail {
  36
  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);
  40 }
  41
  42 }  // namespace detail
  43
  44 /**
  45  * Event count: a condition variable for lock free algorithms.
  46  *
  47  * See http://www.1024cores.net/home/lock-free-algorithms/eventcounts for
  48  * details.
  49  *
  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.
  56  *
  57  * If "<" denotes the happens-before relationship, consider 2 threads (T1 and
  58  * T2) and 3 events:
  59  * - E1: T1 returns from prepareWait
  60  * - E2: T1 calls wait
  61  *   (obviously E1 < E2, intra-thread)
  62  * - E3: T2 calls notifyAll
  63  *
  64  * If E1 < E3, then E2's wait will complete (and T1 will either wake up,
  65  * or not block at all)
  66  *
  67  * This means that you can use an EventCount in the following manner:
  68  *
  69  * Waiter:
  70  *   if (!condition()) {  // handle fast path first
  71  *     for (;;) {
  72  *       auto key = eventCount.prepareWait();
  73  *       if (condition()) {
  74  *         eventCount.cancelWait();
  75  *         break;
  76  *       } else {
  77  *         eventCount.wait(key);
  78  *       }
  79  *     }
  80  *  }
  81  *
  82  *  (This pattern is encapsulated in await())
  83  *
  84  * Poster:
  85  *   make_condition_true();
  86  *   eventCount.notifyAll();
  87  *
  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.
  94  */
  95 class EventCount {
  96  public:
  97   EventCount() noexcept : val_(0) { }
  98
  99   class Key {
 100     friend class EventCount;
 101     explicit Key(uint32_t e) noexcept : epoch_(e) { }
 102     uint32_t epoch_;
 103   };
 104
 105   void notify() noexcept;
 106   void notifyAll() noexcept;
 107   Key prepareWait() noexcept;
 108   void cancelWait() noexcept;
 109   void wait(Key key) noexcept;
 110
 111   /**
 112    * Wait for condition() to become true.  Will clean up appropriately if
 113    * condition() throws, and then rethrow.
 114    */
 115   template <class Condition>
 116   void await(Condition condition);
 117
 118  private:
 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;
 124
 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");
 129
 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)
 134 #else
 135 # error Your machine uses a weird endianness!
 136 #endif
 137
 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_;
 141
 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;
 147 };
 148
 149 inline void EventCount::notify() noexcept {
 150   doNotify(1);
 151 }
 152
 153 inline void EventCount::notifyAll() noexcept {
 154   doNotify(INT_MAX);
 155 }
 156
 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);
 162   }
 163 }
 164
 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);
 168 }
 169
 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   DCHECK_NE((prev & kWaiterMask), 0);
 176 }
 177
 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);
 182   }
 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   DCHECK_NE((prev & kWaiterMask), 0);
 188 }
 189
 190 template <class Condition>
 191 void EventCount::await(Condition condition) {
 192   if (condition()) return;  // fast path
 193
 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
 196   try {
 197     for (;;) {
 198       auto key = prepareWait();
 199       if (condition()) {
 200         cancelWait();
 201         break;
 202       } else {
 203         wait(key);
 204       }
 205     }
 206   } catch (...) {
 207     cancelWait();
 208     throw;
 209   }
 210 }
 211
 212 }  // namespace folly
 213
 214 #endif /* FOLLY_EXPERIMENTAL_EVENTCOUNT_H_ */