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