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