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