folly/test/DeterministicSchedule.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 #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 #include <glog/logging.h>
  29
  30 #include <folly/ScopeGuard.h>
  31 #include <folly/detail/CacheLocality.h>
  32 #include <folly/detail/Futex.h>
  33
  34 namespace folly {
  35 namespace test {
  36
  37 // This is ugly, but better perf for DeterministicAtomic translates
  38 // directly to more states explored and tested
  39 #define FOLLY_TEST_DSCHED_VLOG(msg...)                                  \
  40   do {                                                                  \
  41     if (false) {                                                        \
  42       VLOG(2) << std::hex << std::this_thread::get_id() << ": " << msg; \
  43     }                                                                   \
  44   } while (false)
  45
  46 /**
  47  * DeterministicSchedule coordinates the inter-thread communication of a
  48  * set of threads under test, so that despite concurrency the execution is
  49  * the same every time.  It works by stashing a reference to the schedule
  50  * in a thread-local variable, then blocking all but one thread at a time.
  51  *
  52  * In order for DeterministicSchedule to work, it needs to intercept
  53  * all inter-thread communication.  To do this you should use
  54  * DeterministicAtomic<T> instead of std::atomic<T>, create threads
  55  * using DeterministicSchedule::thread() instead of the std::thread
  56  * constructor, DeterministicSchedule::join(thr) instead of thr.join(),
  57  * and access semaphores via the helper functions in DeterministicSchedule.
  58  * Locks are not yet supported, although they would be easy to add with
  59  * the same strategy as the mapping of sem_wait.
  60  *
  61  * The actual schedule is defined by a function from n -> [0,n). At
  62  * each step, the function will be given the number of active threads
  63  * (n), and it returns the index of the thread that should be run next.
  64  * Invocations of the scheduler function will be serialized, but will
  65  * occur from multiple threads.  A good starting schedule is uniform(0).
  66  */
  67 class DeterministicSchedule : boost::noncopyable {
  68  public:
  69   /**
  70    * Arranges for the current thread (and all threads created by
  71    * DeterministicSchedule::thread on a thread participating in this
  72    * schedule) to participate in a deterministic schedule.
  73    */
  74   explicit DeterministicSchedule(const std::function<int(int)>& scheduler);
  75
  76   /** Completes the schedule. */
  77   ~DeterministicSchedule();
  78
  79   /**
  80    * Returns a scheduling function that randomly chooses one of the
  81    * runnable threads at each step, with no history.  This implements
  82    * a schedule that is equivalent to one in which the steps between
  83    * inter-thread communication are random variables following a poisson
  84    * distribution.
  85    */
  86   static std::function<int(int)> uniform(long seed);
  87
  88   /**
  89    * Returns a scheduling function that chooses a subset of the active
  90    * threads and randomly chooses a member of the subset as the next
  91    * runnable thread.  The subset is chosen with size n, and the choice
  92    * is made every m steps.
  93    */
  94   static std::function<int(int)> uniformSubset(long seed,
  95                                                int n = 2,
  96                                                int m = 64);
  97
  98   /** Obtains permission for the current thread to perform inter-thread
  99    *  communication. */
 100   static void beforeSharedAccess();
 101
 102   /** Releases permission for the current thread to perform inter-thread
 103    *  communication. */
 104   static void afterSharedAccess();
 105
 106   /** Launches a thread that will participate in the same deterministic
 107    *  schedule as the current thread. */
 108   template <typename Func, typename... Args>
 109   static inline std::thread thread(Func&& func, Args&&... args) {
 110     // TODO: maybe future versions of gcc will allow forwarding to thread
 111     auto sched = tls_sched;
 112     auto sem = sched ? sched->beforeThreadCreate() : nullptr;
 113     auto child = std::thread([=](Args... a) {
 114       if (sched) {
 115         sched->afterThreadCreate(sem);
 116         beforeSharedAccess();
 117         FOLLY_TEST_DSCHED_VLOG("running");
 118         afterSharedAccess();
 119       }
 120       SCOPE_EXIT {
 121         if (sched) {
 122           sched->beforeThreadExit();
 123         }
 124       };
 125       func(a...);
 126     }, args...);
 127     if (sched) {
 128       beforeSharedAccess();
 129       sched->active_.insert(child.get_id());
 130       FOLLY_TEST_DSCHED_VLOG("forked " << std::hex << child.get_id());
 131       afterSharedAccess();
 132     }
 133     return child;
 134   }
 135
 136   /** Calls child.join() as part of a deterministic schedule. */
 137   static void join(std::thread& child);
 138
 139   /** Calls sem_post(sem) as part of a deterministic schedule. */
 140   static void post(sem_t* sem);
 141
 142   /** Calls sem_trywait(sem) as part of a deterministic schedule, returning
 143    *  true on success and false on transient failure. */
 144   static bool tryWait(sem_t* sem);
 145
 146   /** Calls sem_wait(sem) as part of a deterministic schedule. */
 147   static void wait(sem_t* sem);
 148
 149   /** Used scheduler_ to get a random number b/w [0, n). If tls_sched is
 150    *  not set-up it falls back to std::rand() */
 151   static int getRandNumber(int n);
 152
 153   /** Deterministic implemencation of getcpu */
 154   static int getcpu(unsigned* cpu, unsigned* node, void* unused);
 155
 156  private:
 157   static FOLLY_TLS sem_t* tls_sem;
 158   static FOLLY_TLS DeterministicSchedule* tls_sched;
 159   static FOLLY_TLS unsigned tls_threadId;
 160
 161   std::function<int(int)> scheduler_;
 162   std::vector<sem_t*> sems_;
 163   std::unordered_set<std::thread::id> active_;
 164   unsigned nextThreadId_;
 165
 166   sem_t* beforeThreadCreate();
 167   void afterThreadCreate(sem_t*);
 168   void beforeThreadExit();
 169 };
 170
 171 /**
 172  * DeterministicAtomic<T> is a drop-in replacement std::atomic<T> that
 173  * cooperates with DeterministicSchedule.
 174  */
 175 template <typename T>
 176 struct DeterministicAtomic {
 177   std::atomic<T> data;
 178
 179   DeterministicAtomic() = default;
 180   ~DeterministicAtomic() = default;
 181   DeterministicAtomic(DeterministicAtomic<T> const&) = delete;
 182   DeterministicAtomic<T>& operator=(DeterministicAtomic<T> const&) = delete;
 183
 184   constexpr /* implicit */ DeterministicAtomic(T v) noexcept : data(v) {}
 185
 186   bool is_lock_free() const noexcept { return data.is_lock_free(); }
 187
 188   bool compare_exchange_strong(
 189       T& v0, T v1, std::memory_order mo = std::memory_order_seq_cst) noexcept {
 190     DeterministicSchedule::beforeSharedAccess();
 191     auto orig = v0;
 192     bool rv = data.compare_exchange_strong(v0, v1, mo);
 193     FOLLY_TEST_DSCHED_VLOG(this << ".compare_exchange_strong(" << std::hex
 194                                 << orig << ", " << std::hex << v1 << ") -> "
 195                                 << rv << "," << std::hex << v0);
 196     DeterministicSchedule::afterSharedAccess();
 197     return rv;
 198   }
 199
 200   bool compare_exchange_weak(
 201       T& v0, T v1, std::memory_order mo = std::memory_order_seq_cst) noexcept {
 202     DeterministicSchedule::beforeSharedAccess();
 203     auto orig = v0;
 204     bool rv = data.compare_exchange_weak(v0, v1, mo);
 205     FOLLY_TEST_DSCHED_VLOG(this << ".compare_exchange_weak(" << std::hex << orig
 206                                 << ", " << std::hex << v1 << ") -> " << rv
 207                                 << "," << std::hex << v0);
 208     DeterministicSchedule::afterSharedAccess();
 209     return rv;
 210   }
 211
 212   T exchange(T v, std::memory_order mo = std::memory_order_seq_cst) noexcept {
 213     DeterministicSchedule::beforeSharedAccess();
 214     T rv = data.exchange(v, mo);
 215     FOLLY_TEST_DSCHED_VLOG(this << ".exchange(" << std::hex << v << ") -> "
 216                                 << std::hex << rv);
 217     DeterministicSchedule::afterSharedAccess();
 218     return rv;
 219   }
 220
 221   /* implicit */ operator T() const noexcept {
 222     DeterministicSchedule::beforeSharedAccess();
 223     T rv = data;
 224     FOLLY_TEST_DSCHED_VLOG(this << "() -> " << std::hex << rv);
 225     DeterministicSchedule::afterSharedAccess();
 226     return rv;
 227   }
 228
 229   T load(std::memory_order mo = std::memory_order_seq_cst) const noexcept {
 230     DeterministicSchedule::beforeSharedAccess();
 231     T rv = data.load(mo);
 232     FOLLY_TEST_DSCHED_VLOG(this << ".load() -> " << std::hex << rv);
 233     DeterministicSchedule::afterSharedAccess();
 234     return rv;
 235   }
 236
 237   T operator=(T v) noexcept {
 238     DeterministicSchedule::beforeSharedAccess();
 239     T rv = (data = v);
 240     FOLLY_TEST_DSCHED_VLOG(this << " = " << std::hex << v);
 241     DeterministicSchedule::afterSharedAccess();
 242     return rv;
 243   }
 244
 245   void store(T v, std::memory_order mo = std::memory_order_seq_cst) noexcept {
 246     DeterministicSchedule::beforeSharedAccess();
 247     data.store(v, mo);
 248     FOLLY_TEST_DSCHED_VLOG(this << ".store(" << std::hex << v << ")");
 249     DeterministicSchedule::afterSharedAccess();
 250   }
 251
 252   T operator++() noexcept {
 253     DeterministicSchedule::beforeSharedAccess();
 254     T rv = ++data;
 255     FOLLY_TEST_DSCHED_VLOG(this << " pre++ -> " << std::hex << rv);
 256     DeterministicSchedule::afterSharedAccess();
 257     return rv;
 258   }
 259
 260   T operator++(int /* postDummy */) noexcept {
 261     DeterministicSchedule::beforeSharedAccess();
 262     T rv = data++;
 263     FOLLY_TEST_DSCHED_VLOG(this << " post++ -> " << std::hex << rv);
 264     DeterministicSchedule::afterSharedAccess();
 265     return rv;
 266   }
 267
 268   T operator--() noexcept {
 269     DeterministicSchedule::beforeSharedAccess();
 270     T rv = --data;
 271     FOLLY_TEST_DSCHED_VLOG(this << " pre-- -> " << std::hex << rv);
 272     DeterministicSchedule::afterSharedAccess();
 273     return rv;
 274   }
 275
 276   T operator--(int /* postDummy */) noexcept {
 277     DeterministicSchedule::beforeSharedAccess();
 278     T rv = data--;
 279     FOLLY_TEST_DSCHED_VLOG(this << " post-- -> " << std::hex << rv);
 280     DeterministicSchedule::afterSharedAccess();
 281     return rv;
 282   }
 283
 284   T operator+=(T v) noexcept {
 285     DeterministicSchedule::beforeSharedAccess();
 286     T rv = (data += v);
 287     FOLLY_TEST_DSCHED_VLOG(this << " += " << std::hex << v << " -> " << std::hex
 288                                 << rv);
 289     DeterministicSchedule::afterSharedAccess();
 290     return rv;
 291   }
 292
 293   T fetch_add(T v,
 294               std::memory_order /* mo */ = std::memory_order_seq_cst) noexcept {
 295     DeterministicSchedule::beforeSharedAccess();
 296     T rv = data;
 297     data += v;
 298     FOLLY_TEST_DSCHED_VLOG(this << ".fetch_add(" << std::hex << v << ") -> "
 299                                 << std::hex << rv);
 300     DeterministicSchedule::afterSharedAccess();
 301     return rv;
 302   }
 303
 304   T operator-=(T v) noexcept {
 305     DeterministicSchedule::beforeSharedAccess();
 306     T rv = (data -= v);
 307     FOLLY_TEST_DSCHED_VLOG(this << " -= " << std::hex << v << " -> " << std::hex
 308                                 << rv);
 309     DeterministicSchedule::afterSharedAccess();
 310     return rv;
 311   }
 312
 313   T fetch_sub(T v,
 314               std::memory_order /* mo */ = std::memory_order_seq_cst) noexcept {
 315     DeterministicSchedule::beforeSharedAccess();
 316     T rv = data;
 317     data -= v;
 318     FOLLY_TEST_DSCHED_VLOG(this << ".fetch_sub(" << std::hex << v << ") -> "
 319                                 << std::hex << rv);
 320     DeterministicSchedule::afterSharedAccess();
 321     return rv;
 322   }
 323
 324   T operator&=(T v) noexcept {
 325     DeterministicSchedule::beforeSharedAccess();
 326     T rv = (data &= v);
 327     FOLLY_TEST_DSCHED_VLOG(this << " &= " << std::hex << v << " -> " << std::hex
 328                                 << rv);
 329     DeterministicSchedule::afterSharedAccess();
 330     return rv;
 331   }
 332
 333   T fetch_and(T v,
 334               std::memory_order /* mo */ = std::memory_order_seq_cst) noexcept {
 335     DeterministicSchedule::beforeSharedAccess();
 336     T rv = data;
 337     data &= v;
 338     FOLLY_TEST_DSCHED_VLOG(this << ".fetch_and(" << std::hex << v << ") -> "
 339                                 << std::hex << rv);
 340     DeterministicSchedule::afterSharedAccess();
 341     return rv;
 342   }
 343
 344   T operator|=(T v) noexcept {
 345     DeterministicSchedule::beforeSharedAccess();
 346     T rv = (data |= v);
 347     FOLLY_TEST_DSCHED_VLOG(this << " |= " << std::hex << v << " -> " << std::hex
 348                                 << rv);
 349     DeterministicSchedule::afterSharedAccess();
 350     return rv;
 351   }
 352
 353   T fetch_or(T v,
 354              std::memory_order /* mo */ = std::memory_order_seq_cst) noexcept {
 355     DeterministicSchedule::beforeSharedAccess();
 356     T rv = data;
 357     data |= v;
 358     FOLLY_TEST_DSCHED_VLOG(this << ".fetch_or(" << std::hex << v << ") -> "
 359                                 << std::hex << rv);
 360     DeterministicSchedule::afterSharedAccess();
 361     return rv;
 362   }
 363
 364   T operator^=(T v) noexcept {
 365     DeterministicSchedule::beforeSharedAccess();
 366     T rv = (data ^= v);
 367     FOLLY_TEST_DSCHED_VLOG(this << " ^= " << std::hex << v << " -> " << std::hex
 368                                 << rv);
 369     DeterministicSchedule::afterSharedAccess();
 370     return rv;
 371   }
 372
 373   T fetch_xor(T v,
 374               std::memory_order /* mo */ = std::memory_order_seq_cst) noexcept {
 375     DeterministicSchedule::beforeSharedAccess();
 376     T rv = data;
 377     data ^= v;
 378     FOLLY_TEST_DSCHED_VLOG(this << ".fetch_xor(" << std::hex << v << ") -> "
 379                                 << std::hex << rv);
 380     DeterministicSchedule::afterSharedAccess();
 381     return rv;
 382   }
 383 };
 384 }
 385 } // namespace folly::test
 386
 387 /* Specialization declarations */
 388
 389 namespace folly {
 390 namespace detail {
 391
 392 template <>
 393 int Futex<test::DeterministicAtomic>::futexWake(int count, uint32_t wakeMask);
 394
 395 template <>
 396 FutexResult Futex<test::DeterministicAtomic>::futexWaitImpl(
 397     uint32_t expected,
 398     std::chrono::time_point<std::chrono::system_clock>* absSystemTime,
 399     std::chrono::time_point<std::chrono::steady_clock>* absSteadyTime,
 400     uint32_t waitMask);
 401
 402 template <>
 403 Getcpu::Func AccessSpreader<test::DeterministicAtomic>::pickGetcpuFunc(
 404     size_t numStripes);
 405 }
 406 } // namespace folly::detail