folly/test/DeterministicSchedule.h

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