folly/test/DeterministicSchedule.h

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