folly/experimental/EventCount.h

   1 /*
   2  * Copyright 2013 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
  28
  29 namespace folly {
  30
  31 namespace detail {
  32
  33 inline int futex(int* uaddr, int op, int val, const timespec* timeout,
  34                  int* uaddr2, int val3) noexcept {
  35   return syscall(SYS_futex, uaddr, op, val, timeout, uaddr2, val3);
  36 }
  37
  38 }  // namespace detail
  39
  40 /**
  41  * Event count: a condition variable for lock free algorithms.
  42  *
  43  * See http://www.1024cores.net/home/lock-free-algorithms/eventcounts for
  44  * details.
  45  *
  46  * Event counts allow you to convert a non-blocking lock-free / wait-free
  47  * algorithm into a blocking one, by isolating the blocking logic.  You call
  48  * prepareWait() before checking your condition and then either cancelWait()
  49  * or wait() depending on whether the condition was true.  When another
  50  * thread makes the condition true, it must call notify() / notifyAll() just
  51  * like a regular condition variable.
  52  *
  53  * If "<" denotes the happens-before relationship, consider 2 threads (T1 and
  54  * T2) and 3 events:
  55  * - E1: T1 returns from prepareWait
  56  * - E2: T1 calls wait
  57  *   (obviously E1 < E2, intra-thread)
  58  * - E3: T2 calls notifyAll
  59  *
  60  * If E1 < E3, then E2's wait will complete (and T1 will either wake up,
  61  * or not block at all)
  62  *
  63  * This means that you can use an EventCount in the following manner:
  64  *
  65  * Waiter:
  66  *   if (!condition()) {  // handle fast path first
  67  *     for (;;) {
  68  *       auto key = eventCount.prepareWait();
  69  *       if (condition()) {
  70  *         eventCount.cancelWait();
  71  *         break;
  72  *       } else {
  73  *         eventCount.wait(key);
  74  *       }
  75  *     }
  76  *  }
  77  *
  78  *  (This pattern is encapsulated in await())
  79  *
  80  * Poster:
  81  *   make_condition_true();
  82  *   eventCount.notifyAll();
  83  *
  84  * Note that, just like with regular condition variables, the waiter needs to
  85  * be tolerant of spurious wakeups and needs to recheck the condition after
  86  * being woken up.  Also, as there is no mutual exclusion implied, "checking"
  87  * the condition likely means attempting an operation on an underlying
  88  * data structure (push into a lock-free queue, etc) and returning true on
  89  * success and false on failure.
  90  */
  91 class EventCount {
  92  public:
  93   EventCount() noexcept : epoch_(0), waiters_(0) { }
  94
  95   class Key {
  96     friend class EventCount;
  97     explicit Key(int e) noexcept : epoch_(e) { }
  98     int epoch_;
  99   };
 100
 101   void notify() noexcept;
 102   void notifyAll() noexcept;
 103   Key prepareWait() noexcept;
 104   void cancelWait() noexcept;
 105   void wait(Key key) noexcept;
 106
 107   /**
 108    * Wait for condition() to become true.  Will clean up appropriately if
 109    * condition() throws, and then rethrow.
 110    */
 111   template <class Condition>
 112   void await(Condition condition);
 113
 114  private:
 115   void doNotify(int n) noexcept;
 116   EventCount(const EventCount&) = delete;
 117   EventCount(EventCount&&) = delete;
 118   EventCount& operator=(const EventCount&) = delete;
 119   EventCount& operator=(EventCount&&) = delete;
 120
 121   std::atomic<int> epoch_;
 122   std::atomic<int> waiters_;
 123 };
 124
 125 inline void EventCount::notify() noexcept {
 126   doNotify(1);
 127 }
 128
 129 inline void EventCount::notifyAll() noexcept {
 130   doNotify(INT_MAX);
 131 }
 132
 133 inline void EventCount::doNotify(int n) noexcept {
 134   // The order is important: epoch_ is incremented before waiters_ is checked.
 135   // prepareWait() increments waiters_ before checking epoch_, so it is
 136   // impossible to miss a wakeup.
 137   ++epoch_;
 138   if (waiters_ != 0) {
 139     detail::futex(reinterpret_cast<int*>(&epoch_), FUTEX_WAKE, n, nullptr,
 140                   nullptr, 0);
 141   }
 142 }
 143
 144 inline EventCount::Key EventCount::prepareWait() noexcept {
 145   ++waiters_;
 146   return Key(epoch_);
 147 }
 148
 149 inline void EventCount::cancelWait() noexcept {
 150   --waiters_;
 151 }
 152
 153 inline void EventCount::wait(Key key) noexcept {
 154   while (epoch_ == key.epoch_) {
 155     detail::futex(reinterpret_cast<int*>(&epoch_), FUTEX_WAIT, key.epoch_,
 156                   nullptr, nullptr, 0);
 157   }
 158   --waiters_;
 159 }
 160
 161 template <class Condition>
 162 void EventCount::await(Condition condition) {
 163   if (condition()) return;  // fast path
 164
 165   // condition() is the only thing that may throw, everything else is
 166   // noexcept, so we can hoist the try/catch block outside of the loop
 167   try {
 168     for (;;) {
 169       auto key = prepareWait();
 170       if (condition()) {
 171         cancelWait();
 172         break;
 173       } else {
 174         wait(key);
 175       }
 176     }
 177   } catch (...) {
 178     cancelWait();
 179     throw;
 180   }
 181 }
 182
 183 }  // namespace folly
 184
 185 #endif /* FOLLY_EXPERIMENTAL_EVENTCOUNT_H_ */
 186