X-Git-Url: http://plrg.eecs.uci.edu/git/?p=folly.git;a=blobdiff_plain;f=folly%2Ftest%2FDeterministicSchedule.h;h=a9b1ca5d9997c6dbdb92e0ec5cf728269bcf9a6a;hp=b04e613a1f0ee5f5a79e40d1f3ecabe74385d2c4;hb=b67b22f4e27773e2e2c155a3629ff8d468bb1286;hpb=95c95660338c5a24fdf1a27a4da2f5fe4d12359a

diff --git a/folly/test/DeterministicSchedule.h b/folly/test/DeterministicSchedule.h
index b04e613a..a9b1ca5d 100644
--- a/folly/test/DeterministicSchedule.h
+++ b/folly/test/DeterministicSchedule.h
@@ -1,5 +1,5 @@
 /*
- * Copyright 2016 Facebook, Inc.
+ * Copyright 2013-present Facebook, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -20,7 +20,6 @@
 #include <boost/noncopyable.hpp>
 #include <errno.h>
 #include <glog/logging.h>
-#include <semaphore.h>
 #include <atomic>
 #include <functional>
 #include <mutex>
@@ -29,21 +28,28 @@
 #include <vector>
 
 #include <folly/ScopeGuard.h>
-#include <folly/detail/CacheLocality.h>
+#include <folly/concurrency/CacheLocality.h>
 #include <folly/detail/Futex.h>
+#include <folly/portability/Semaphore.h>
+#include <folly/synchronization/detail/AtomicUtils.h>
 
 namespace folly {
 namespace test {
 
 // This is ugly, but better perf for DeterministicAtomic translates
 // directly to more states explored and tested
-#define FOLLY_TEST_DSCHED_VLOG(msg...)                                  \
-  do {                                                                  \
-    if (false) {                                                        \
-      VLOG(2) << std::hex << std::this_thread::get_id() << ": " << msg; \
-    }                                                                   \
+#define FOLLY_TEST_DSCHED_VLOG(...)                             \
+  do {                                                          \
+    if (false) {                                                \
+      VLOG(2) << std::hex << std::this_thread::get_id() << ": " \
+              << __VA_ARGS__;                                   \
+    }                                                           \
   } while (false)
 
+/* signatures of user-defined auxiliary functions */
+using AuxAct = std::function<void(bool)>;
+using AuxChk = std::function<void(uint64_t)>;
+
 /**
  * DeterministicSchedule coordinates the inter-thread communication of a
  * set of threads under test, so that despite concurrency the execution is
@@ -72,7 +78,8 @@ class DeterministicSchedule : boost::noncopyable {
    * DeterministicSchedule::thread on a thread participating in this
    * schedule) to participate in a deterministic schedule.
    */
-  explicit DeterministicSchedule(const std::function<int(int)>& scheduler);
+  explicit DeterministicSchedule(
+      const std::function<size_t(size_t)>& scheduler);
 
   /** Completes the schedule. */
   ~DeterministicSchedule();
@@ -84,7 +91,7 @@ class DeterministicSchedule : boost::noncopyable {
    * inter-thread communication are random variables following a poisson
    * distribution.
    */
-  static std::function<int(int)> uniform(long seed);
+  static std::function<size_t(size_t)> uniform(uint64_t seed);
 
   /**
    * Returns a scheduling function that chooses a subset of the active
@@ -92,9 +99,8 @@ class DeterministicSchedule : boost::noncopyable {
    * runnable thread.  The subset is chosen with size n, and the choice
    * is made every m steps.
    */
-  static std::function<int(int)> uniformSubset(long seed,
-                                               int n = 2,
-                                               int m = 64);
+  static std::function<size_t(size_t)>
+  uniformSubset(uint64_t seed, size_t n = 2, size_t m = 64);
 
   /** Obtains permission for the current thread to perform inter-thread
    *  communication. */
@@ -104,6 +110,12 @@ class DeterministicSchedule : boost::noncopyable {
    *  communication. */
   static void afterSharedAccess();
 
+  /** Calls a user-defined auxiliary function if any, and releases
+   *  permission for the current thread to perform inter-thread
+   *  communication. The bool parameter indicates the success of the
+   *  shared access (if conditional, true otherwise). */
+  static void afterSharedAccess(bool success);
+
   /** Launches a thread that will participate in the same deterministic
    *  schedule as the current thread. */
   template <typename Func, typename... Args>
@@ -149,24 +161,51 @@ class DeterministicSchedule : boost::noncopyable {
 
   /** Used scheduler_ to get a random number b/w [0, n). If tls_sched is
    *  not set-up it falls back to std::rand() */
-  static int getRandNumber(int n);
+  static size_t getRandNumber(size_t n);
 
   /** Deterministic implemencation of getcpu */
   static int getcpu(unsigned* cpu, unsigned* node, void* unused);
 
+  /** Sets up a thread-specific function for call immediately after
+   *  the next shared access by the thread for managing auxiliary
+   *  data. The function takes a bool parameter that indicates the
+   *  success of the shared access (if it is conditional, true
+   *  otherwise). The function is cleared after one use. */
+  static void setAuxAct(AuxAct& aux);
+
+  /** Sets up a function to be called after every subsequent shared
+   *  access (until clearAuxChk() is called) for checking global
+   *  invariants and logging. The function takes a uint64_t parameter
+   *  that indicates the number of shared accesses so far. */
+  static void setAuxChk(AuxChk& aux);
+
+  /** Clears the function set by setAuxChk */
+  static void clearAuxChk();
+
  private:
   static FOLLY_TLS sem_t* tls_sem;
   static FOLLY_TLS DeterministicSchedule* tls_sched;
   static FOLLY_TLS unsigned tls_threadId;
+  static thread_local AuxAct tls_aux_act;
+  static AuxChk aux_chk;
 
-  std::function<int(int)> scheduler_;
+  std::function<size_t(size_t)> scheduler_;
   std::vector<sem_t*> sems_;
   std::unordered_set<std::thread::id> active_;
   unsigned nextThreadId_;
+  /* step_ keeps count of shared accesses that correspond to user
+   * synchronization steps (atomic accesses for now).
+   * The reason for keeping track of this here and not just with
+   * auxiliary data is to provide users with warning signs (e.g.,
+   * skipped steps) if they inadvertently forget to set up aux
+   * functions for some shared accesses. */
+  uint64_t step_;
 
   sem_t* beforeThreadCreate();
   void afterThreadCreate(sem_t*);
   void beforeThreadExit();
+  /** Calls user-defined auxiliary function (if any) */
+  void callAux(bool);
 };
 
 /**
@@ -187,26 +226,46 @@ struct DeterministicAtomic {
   bool is_lock_free() const noexcept { return data.is_lock_free(); }
 
   bool compare_exchange_strong(
-      T& v0, T v1, std::memory_order mo = std::memory_order_seq_cst) noexcept {
+      T& v0,
+      T v1,
+      std::memory_order mo = std::memory_order_seq_cst) noexcept {
+    return compare_exchange_strong(
+        v0, v1, mo, detail::default_failure_memory_order(mo));
+  }
+  bool compare_exchange_strong(
+      T& v0,
+      T v1,
+      std::memory_order success,
+      std::memory_order failure) noexcept {
     DeterministicSchedule::beforeSharedAccess();
     auto orig = v0;
-    bool rv = data.compare_exchange_strong(v0, v1, mo);
+    bool rv = data.compare_exchange_strong(v0, v1, success, failure);
     FOLLY_TEST_DSCHED_VLOG(this << ".compare_exchange_strong(" << std::hex
                                 << orig << ", " << std::hex << v1 << ") -> "
                                 << rv << "," << std::hex << v0);
-    DeterministicSchedule::afterSharedAccess();
+    DeterministicSchedule::afterSharedAccess(rv);
     return rv;
   }
 
   bool compare_exchange_weak(
-      T& v0, T v1, std::memory_order mo = std::memory_order_seq_cst) noexcept {
+      T& v0,
+      T v1,
+      std::memory_order mo = std::memory_order_seq_cst) noexcept {
+    return compare_exchange_weak(
+        v0, v1, mo, detail::default_failure_memory_order(mo));
+  }
+  bool compare_exchange_weak(
+      T& v0,
+      T v1,
+      std::memory_order success,
+      std::memory_order failure) noexcept {
     DeterministicSchedule::beforeSharedAccess();
     auto orig = v0;
-    bool rv = data.compare_exchange_weak(v0, v1, mo);
+    bool rv = data.compare_exchange_weak(v0, v1, success, failure);
     FOLLY_TEST_DSCHED_VLOG(this << ".compare_exchange_weak(" << std::hex << orig
                                 << ", " << std::hex << v1 << ") -> " << rv
                                 << "," << std::hex << v0);
-    DeterministicSchedule::afterSharedAccess();
+    DeterministicSchedule::afterSharedAccess(rv);
     return rv;
   }
 
@@ -215,7 +274,7 @@ struct DeterministicAtomic {
     T rv = data.exchange(v, mo);
     FOLLY_TEST_DSCHED_VLOG(this << ".exchange(" << std::hex << v << ") -> "
                                 << std::hex << rv);
-    DeterministicSchedule::afterSharedAccess();
+    DeterministicSchedule::afterSharedAccess(true);
     return rv;
   }
 
@@ -223,7 +282,7 @@ struct DeterministicAtomic {
     DeterministicSchedule::beforeSharedAccess();
     T rv = data;
     FOLLY_TEST_DSCHED_VLOG(this << "() -> " << std::hex << rv);
-    DeterministicSchedule::afterSharedAccess();
+    DeterministicSchedule::afterSharedAccess(true);
     return rv;
   }
 
@@ -231,7 +290,7 @@ struct DeterministicAtomic {
     DeterministicSchedule::beforeSharedAccess();
     T rv = data.load(mo);
     FOLLY_TEST_DSCHED_VLOG(this << ".load() -> " << std::hex << rv);
-    DeterministicSchedule::afterSharedAccess();
+    DeterministicSchedule::afterSharedAccess(true);
     return rv;
   }
 
@@ -239,7 +298,7 @@ struct DeterministicAtomic {
     DeterministicSchedule::beforeSharedAccess();
     T rv = (data = v);
     FOLLY_TEST_DSCHED_VLOG(this << " = " << std::hex << v);
-    DeterministicSchedule::afterSharedAccess();
+    DeterministicSchedule::afterSharedAccess(true);
     return rv;
   }
 
@@ -247,14 +306,14 @@ struct DeterministicAtomic {
     DeterministicSchedule::beforeSharedAccess();
     data.store(v, mo);
     FOLLY_TEST_DSCHED_VLOG(this << ".store(" << std::hex << v << ")");
-    DeterministicSchedule::afterSharedAccess();
+    DeterministicSchedule::afterSharedAccess(true);
   }
 
   T operator++() noexcept {
     DeterministicSchedule::beforeSharedAccess();
     T rv = ++data;
     FOLLY_TEST_DSCHED_VLOG(this << " pre++ -> " << std::hex << rv);
-    DeterministicSchedule::afterSharedAccess();
+    DeterministicSchedule::afterSharedAccess(true);
     return rv;
   }
 
@@ -262,7 +321,7 @@ struct DeterministicAtomic {
     DeterministicSchedule::beforeSharedAccess();
     T rv = data++;
     FOLLY_TEST_DSCHED_VLOG(this << " post++ -> " << std::hex << rv);
-    DeterministicSchedule::afterSharedAccess();
+    DeterministicSchedule::afterSharedAccess(true);
     return rv;
   }
 
@@ -270,7 +329,7 @@ struct DeterministicAtomic {
     DeterministicSchedule::beforeSharedAccess();
     T rv = --data;
     FOLLY_TEST_DSCHED_VLOG(this << " pre-- -> " << std::hex << rv);
-    DeterministicSchedule::afterSharedAccess();
+    DeterministicSchedule::afterSharedAccess(true);
     return rv;
   }
 
@@ -278,7 +337,7 @@ struct DeterministicAtomic {
     DeterministicSchedule::beforeSharedAccess();
     T rv = data--;
     FOLLY_TEST_DSCHED_VLOG(this << " post-- -> " << std::hex << rv);
-    DeterministicSchedule::afterSharedAccess();
+    DeterministicSchedule::afterSharedAccess(true);
     return rv;
   }
 
@@ -287,7 +346,7 @@ struct DeterministicAtomic {
     T rv = (data += v);
     FOLLY_TEST_DSCHED_VLOG(this << " += " << std::hex << v << " -> " << std::hex
                                 << rv);
-    DeterministicSchedule::afterSharedAccess();
+    DeterministicSchedule::afterSharedAccess(true);
     return rv;
   }
 
@@ -298,7 +357,7 @@ struct DeterministicAtomic {
     data += v;
     FOLLY_TEST_DSCHED_VLOG(this << ".fetch_add(" << std::hex << v << ") -> "
                                 << std::hex << rv);
-    DeterministicSchedule::afterSharedAccess();
+    DeterministicSchedule::afterSharedAccess(true);
     return rv;
   }
 
@@ -307,7 +366,7 @@ struct DeterministicAtomic {
     T rv = (data -= v);
     FOLLY_TEST_DSCHED_VLOG(this << " -= " << std::hex << v << " -> " << std::hex
                                 << rv);
-    DeterministicSchedule::afterSharedAccess();
+    DeterministicSchedule::afterSharedAccess(true);
     return rv;
   }
 
@@ -318,7 +377,7 @@ struct DeterministicAtomic {
     data -= v;
     FOLLY_TEST_DSCHED_VLOG(this << ".fetch_sub(" << std::hex << v << ") -> "
                                 << std::hex << rv);
-    DeterministicSchedule::afterSharedAccess();
+    DeterministicSchedule::afterSharedAccess(true);
     return rv;
   }
 
@@ -327,7 +386,7 @@ struct DeterministicAtomic {
     T rv = (data &= v);
     FOLLY_TEST_DSCHED_VLOG(this << " &= " << std::hex << v << " -> " << std::hex
                                 << rv);
-    DeterministicSchedule::afterSharedAccess();
+    DeterministicSchedule::afterSharedAccess(true);
     return rv;
   }
 
@@ -338,7 +397,7 @@ struct DeterministicAtomic {
     data &= v;
     FOLLY_TEST_DSCHED_VLOG(this << ".fetch_and(" << std::hex << v << ") -> "
                                 << std::hex << rv);
-    DeterministicSchedule::afterSharedAccess();
+    DeterministicSchedule::afterSharedAccess(true);
     return rv;
   }
 
@@ -347,7 +406,7 @@ struct DeterministicAtomic {
     T rv = (data |= v);
     FOLLY_TEST_DSCHED_VLOG(this << " |= " << std::hex << v << " -> " << std::hex
                                 << rv);
-    DeterministicSchedule::afterSharedAccess();
+    DeterministicSchedule::afterSharedAccess(true);
     return rv;
   }
 
@@ -358,7 +417,7 @@ struct DeterministicAtomic {
     data |= v;
     FOLLY_TEST_DSCHED_VLOG(this << ".fetch_or(" << std::hex << v << ") -> "
                                 << std::hex << rv);
-    DeterministicSchedule::afterSharedAccess();
+    DeterministicSchedule::afterSharedAccess(true);
     return rv;
   }
 
@@ -367,7 +426,7 @@ struct DeterministicAtomic {
     T rv = (data ^= v);
     FOLLY_TEST_DSCHED_VLOG(this << " ^= " << std::hex << v << " -> " << std::hex
                                 << rv);
-    DeterministicSchedule::afterSharedAccess();
+    DeterministicSchedule::afterSharedAccess(true);
     return rv;
   }
 
@@ -378,9 +437,14 @@ struct DeterministicAtomic {
     data ^= v;
     FOLLY_TEST_DSCHED_VLOG(this << ".fetch_xor(" << std::hex << v << ") -> "
                                 << std::hex << rv);
-    DeterministicSchedule::afterSharedAccess();
+    DeterministicSchedule::afterSharedAccess(true);
     return rv;
   }
+
+  /** Read the value of the atomic variable without context switching */
+  T load_direct() const noexcept {
+    return data.load(std::memory_order_relaxed);
+  }
 };
 
 /**
@@ -418,8 +482,8 @@ struct DeterministicMutex {
     m.unlock();
   }
 };
-}
-} // namespace folly::test
+} // namespace test
+} // namespace folly
 
 /* Specialization declarations */
 
@@ -435,8 +499,9 @@ FutexResult Futex<test::DeterministicAtomic>::futexWaitImpl(
     std::chrono::time_point<std::chrono::system_clock>* absSystemTime,
     std::chrono::time_point<std::chrono::steady_clock>* absSteadyTime,
     uint32_t waitMask);
+} // namespace detail
 
 template <>
 Getcpu::Func AccessSpreader<test::DeterministicAtomic>::pickGetcpuFunc();
-}
-} // namespace folly::detail
+
+} // namespace folly