folly/test/DeterministicSchedule.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 #pragma once
  18
  19 #include <atomic>
  20 #include <functional>
  21 #include <thread>
  22 #include <unordered_set>
  23 #include <vector>
  24 #include <boost/noncopyable.hpp>
  25 #include <semaphore.h>
  26 #include <errno.h>
  27 #include <assert.h>
  28
  29 #include <folly/ScopeGuard.h>
  30 #include <folly/detail/CacheLocality.h>
  31 #include <folly/detail/Futex.h>
  32
  33 namespace folly { namespace test {
  34
  35 /**
  36  * DeterministicSchedule coordinates the inter-thread communication of a
  37  * set of threads under test, so that despite concurrency the execution is
  38  * the same every time.  It works by stashing a reference to the schedule
  39  * in a thread-local variable, then blocking all but one thread at a time.
  40  *
  41  * In order for DeterministicSchedule to work, it needs to intercept
  42  * all inter-thread communication.  To do this you should use
  43  * DeterministicAtomic<T> instead of std::atomic<T>, create threads
  44  * using DeterministicSchedule::thread() instead of the std::thread
  45  * constructor, DeterministicSchedule::join(thr) instead of thr.join(),
  46  * and access semaphores via the helper functions in DeterministicSchedule.
  47  * Locks are not yet supported, although they would be easy to add with
  48  * the same strategy as the mapping of sem_wait.
  49  *
  50  * The actual schedule is defined by a function from n -> [0,n). At
  51  * each step, the function will be given the number of active threads
  52  * (n), and it returns the index of the thread that should be run next.
  53  * Invocations of the scheduler function will be serialized, but will
  54  * occur from multiple threads.  A good starting schedule is uniform(0).
  55  */
  56 class DeterministicSchedule : boost::noncopyable {
  57  public:
  58   /**
  59    * Arranges for the current thread (and all threads created by
  60    * DeterministicSchedule::thread on a thread participating in this
  61    * schedule) to participate in a deterministic schedule.
  62    */
  63   explicit DeterministicSchedule(const std::function<int(int)>& scheduler);
  64
  65   /** Completes the schedule. */
  66   ~DeterministicSchedule();
  67
  68   /**
  69    * Returns a scheduling function that randomly chooses one of the
  70    * runnable threads at each step, with no history.  This implements
  71    * a schedule that is equivalent to one in which the steps between
  72    * inter-thread communication are random variables following a poisson
  73    * distribution.
  74    */
  75   static std::function<int(int)> uniform(long seed);
  76
  77   /**
  78    * Returns a scheduling function that chooses a subset of the active
  79    * threads and randomly chooses a member of the subset as the next
  80    * runnable thread.  The subset is chosen with size n, and the choice
  81    * is made every m steps.
  82    */
  83   static std::function<int(int)> uniformSubset(long seed, int n = 2,
  84                                                int m = 64);
  85
  86   /** Obtains permission for the current thread to perform inter-thread
  87    *  communication. */
  88   static void beforeSharedAccess();
  89
  90   /** Releases permission for the current thread to perform inter-thread
  91    *  communication. */
  92   static void afterSharedAccess();
  93
  94   /** Launches a thread that will participate in the same deterministic
  95    *  schedule as the current thread. */
  96   template <typename Func, typename... Args>
  97   static inline std::thread thread(Func&& func, Args&&... args) {
  98     // TODO: maybe future versions of gcc will allow forwarding to thread
  99     auto sched = tls_sched;
 100     auto sem = sched ? sched->beforeThreadCreate() : nullptr;
 101     auto child = std::thread([=](Args... a) {
 102       if (sched) sched->afterThreadCreate(sem);
 103       SCOPE_EXIT { if (sched) sched->beforeThreadExit(); };
 104       func(a...);
 105     }, args...);
 106     if (sched) {
 107       beforeSharedAccess();
 108       sched->active_.insert(child.get_id());
 109       afterSharedAccess();
 110     }
 111     return child;
 112   }
 113
 114   /** Calls child.join() as part of a deterministic schedule. */
 115   static void join(std::thread& child);
 116
 117   /** Calls sem_post(sem) as part of a deterministic schedule. */
 118   static void post(sem_t* sem);
 119
 120   /** Calls sem_trywait(sem) as part of a deterministic schedule, returning
 121    *  true on success and false on transient failure. */
 122   static bool tryWait(sem_t* sem);
 123
 124   /** Calls sem_wait(sem) as part of a deterministic schedule. */
 125   static void wait(sem_t* sem);
 126
 127   /** Used scheduler_ to get a random number b/w [0, n). If tls_sched is
 128    *  not set-up it falls back to std::rand() */
 129   static int getRandNumber(int n);
 130
 131  private:
 132   static __thread sem_t* tls_sem;
 133   static __thread DeterministicSchedule* tls_sched;
 134
 135   std::function<int(int)> scheduler_;
 136   std::vector<sem_t*> sems_;
 137   std::unordered_set<std::thread::id> active_;
 138
 139   sem_t* beforeThreadCreate();
 140   void afterThreadCreate(sem_t*);
 141   void beforeThreadExit();
 142 };
 143
 144
 145 /**
 146  * DeterministicAtomic<T> is a drop-in replacement std::atomic<T> that
 147  * cooperates with DeterministicSchedule.
 148  */
 149 template <typename T>
 150 struct DeterministicAtomic {
 151   std::atomic<T> data;
 152
 153   DeterministicAtomic() = default;
 154   ~DeterministicAtomic() = default;
 155   DeterministicAtomic(DeterministicAtomic<T> const &) = delete;
 156   DeterministicAtomic<T>& operator= (DeterministicAtomic<T> const &) = delete;
 157
 158   constexpr /* implicit */ DeterministicAtomic(T v) noexcept : data(v) {}
 159
 160   bool is_lock_free() const noexcept {
 161     return data.is_lock_free();
 162   }
 163
 164   bool compare_exchange_strong(
 165           T& v0, T v1,
 166           std::memory_order mo = std::memory_order_seq_cst) noexcept {
 167     DeterministicSchedule::beforeSharedAccess();
 168     bool rv = data.compare_exchange_strong(v0, v1, mo);
 169     DeterministicSchedule::afterSharedAccess();
 170     return rv;
 171   }
 172
 173   bool compare_exchange_weak(
 174           T& v0, T v1,
 175           std::memory_order mo = std::memory_order_seq_cst) noexcept {
 176     DeterministicSchedule::beforeSharedAccess();
 177     bool rv = data.compare_exchange_weak(v0, v1, mo);
 178     DeterministicSchedule::afterSharedAccess();
 179     return rv;
 180   }
 181
 182   T exchange(T v, std::memory_order mo = std::memory_order_seq_cst) noexcept {
 183     DeterministicSchedule::beforeSharedAccess();
 184     T rv = data.exchange(v, mo);
 185     DeterministicSchedule::afterSharedAccess();
 186     return rv;
 187   }
 188
 189   /* implicit */ operator T () const noexcept {
 190     DeterministicSchedule::beforeSharedAccess();
 191     T rv = data;
 192     DeterministicSchedule::afterSharedAccess();
 193     return rv;
 194   }
 195
 196   T load(std::memory_order mo = std::memory_order_seq_cst) const noexcept {
 197     DeterministicSchedule::beforeSharedAccess();
 198     T rv = data.load(mo);
 199     DeterministicSchedule::afterSharedAccess();
 200     return rv;
 201   }
 202
 203   T operator= (T v) noexcept {
 204     DeterministicSchedule::beforeSharedAccess();
 205     T rv = (data = v);
 206     DeterministicSchedule::afterSharedAccess();
 207     return rv;
 208   }
 209
 210   void store(T v, std::memory_order mo = std::memory_order_seq_cst) noexcept {
 211     DeterministicSchedule::beforeSharedAccess();
 212     data.store(v, mo);
 213     DeterministicSchedule::afterSharedAccess();
 214   }
 215
 216   T operator++ () noexcept {
 217     DeterministicSchedule::beforeSharedAccess();
 218     T rv = ++data;
 219     DeterministicSchedule::afterSharedAccess();
 220     return rv;
 221   }
 222
 223   T operator++ (int postDummy) noexcept {
 224     DeterministicSchedule::beforeSharedAccess();
 225     T rv = data++;
 226     DeterministicSchedule::afterSharedAccess();
 227     return rv;
 228   }
 229
 230   T operator-- () noexcept {
 231     DeterministicSchedule::beforeSharedAccess();
 232     T rv = --data;
 233     DeterministicSchedule::afterSharedAccess();
 234     return rv;
 235   }
 236
 237   T operator-- (int postDummy) noexcept {
 238     DeterministicSchedule::beforeSharedAccess();
 239     T rv = data--;
 240     DeterministicSchedule::afterSharedAccess();
 241     return rv;
 242   }
 243
 244   T operator+= (T v) noexcept {
 245     DeterministicSchedule::beforeSharedAccess();
 246     T rv = (data += v);
 247     DeterministicSchedule::afterSharedAccess();
 248     return rv;
 249   }
 250
 251   T operator-= (T v) noexcept {
 252     DeterministicSchedule::beforeSharedAccess();
 253     T rv = (data -= v);
 254     DeterministicSchedule::afterSharedAccess();
 255     return rv;
 256   }
 257
 258   T operator&= (T v) noexcept {
 259     DeterministicSchedule::beforeSharedAccess();
 260     T rv = (data &= v);
 261     DeterministicSchedule::afterSharedAccess();
 262     return rv;
 263   }
 264
 265   T operator|= (T v) noexcept {
 266     DeterministicSchedule::beforeSharedAccess();
 267     T rv = (data |= v);
 268     DeterministicSchedule::afterSharedAccess();
 269     return rv;
 270   }
 271 };
 272
 273 }}
 274
 275 namespace folly { namespace detail {
 276
 277 template<>
 278 bool Futex<test::DeterministicAtomic>::futexWait(uint32_t expected,
 279                                                  uint32_t waitMask);
 280
 281 /// This function ignores the time bound, and instead pseudo-randomly chooses
 282 /// whether the timeout was reached. To do otherwise would not be deterministic.
 283 FutexResult futexWaitUntilImpl(Futex<test::DeterministicAtomic> *futex,
 284                                uint32_t expected, uint32_t waitMask);
 285
 286 template<> template<class Clock, class Duration>
 287 FutexResult
 288 Futex<test::DeterministicAtomic>::futexWaitUntil(
 289           uint32_t expected,
 290           const time_point<Clock, Duration>& absTimeUnused,
 291           uint32_t waitMask) {
 292   return futexWaitUntilImpl(this, expected, waitMask);
 293 }
 294
 295 template<>
 296 int Futex<test::DeterministicAtomic>::futexWake(int count, uint32_t wakeMask);
 297
 298 }}