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