folly/test/DeterministicScheduleTest.cpp

   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 #include <folly/test/DeterministicSchedule.h>
  18
  19 #include <folly/portability/GFlags.h>
  20 #include <folly/portability/GTest.h>
  21
  22 using namespace folly::test;
  23
  24 TEST(DeterministicSchedule, uniform) {
  25   auto p = DeterministicSchedule::uniform(0);
  26   int buckets[10] = {};
  27   for (int i = 0; i < 100000; ++i) {
  28     buckets[p(10)]++;
  29   }
  30   for (int i = 0; i < 10; ++i) {
  31     EXPECT_TRUE(buckets[i] > 9000);
  32   }
  33 }
  34
  35 TEST(DeterministicSchedule, uniformSubset) {
  36   auto ps = DeterministicSchedule::uniformSubset(0, 3, 100);
  37   int buckets[10] = {};
  38   std::set<int> seen;
  39   for (int i = 0; i < 100000; ++i) {
  40     if (i > 0 && (i % 100) == 0) {
  41       EXPECT_EQ(seen.size(), 3);
  42       seen.clear();
  43     }
  44     int x = ps(10);
  45     seen.insert(x);
  46     EXPECT_TRUE(seen.size() <= 3);
  47     buckets[x]++;
  48   }
  49   for (int i = 0; i < 10; ++i) {
  50     EXPECT_TRUE(buckets[i] > 9000);
  51   }
  52 }
  53
  54 TEST(DeterministicSchedule, buggyAdd) {
  55   for (bool bug : {false, true}) {
  56     DeterministicSchedule sched(DeterministicSchedule::uniform(0));
  57     if (bug) {
  58       FOLLY_TEST_DSCHED_VLOG("Test with race condition");
  59     } else {
  60       FOLLY_TEST_DSCHED_VLOG("Test without race condition");
  61     }
  62     DeterministicMutex m;
  63     // The use of DeterinisticAtomic is not needed here, but it makes
  64     // it easier to understand the sequence of events in logs.
  65     DeterministicAtomic<int> test{0};
  66     DeterministicAtomic<int> baseline{0};
  67     int numThreads = 10;
  68     std::vector<std::thread> threads(numThreads);
  69     for (int t = 0; t < numThreads; ++t) {
  70       threads[t] = DeterministicSchedule::thread([&, t] {
  71         baseline.fetch_add(1);
  72         // Atomic increment of test protected by mutex m
  73         do {
  74           // Some threads use lock() others use try_lock()
  75           if ((t & 1) == 0) {
  76             m.lock();
  77           } else {
  78             if (!m.try_lock()) {
  79               continue;
  80             }
  81           }
  82           int newval = test.load() + 1;
  83           if (bug) {
  84             // Break the atomicity of the increment operation
  85             m.unlock();
  86             m.lock();
  87           }
  88           test.store(newval);
  89           m.unlock();
  90           break;
  91         } while (true);
  92       }); // thread lambda
  93     } // for t
  94     for (auto& t : threads) {
  95       DeterministicSchedule::join(t);
  96     }
  97     if (!bug) {
  98       EXPECT_EQ(test.load(), baseline.load());
  99     } else {
 100       if (test.load() == baseline.load()) {
 101         FOLLY_TEST_DSCHED_VLOG("Didn't catch the bug");
 102       } else {
 103         FOLLY_TEST_DSCHED_VLOG("Caught the bug");
 104       }
 105     }
 106   } // for bug
 107 }
 108
 109 /// Test DSched support for auxiliary data and global invariants
 110 ///
 111 /// How to use DSched support for auxiliary data and global invariants
 112 /// (Let Foo<T, Atom> be the template to be tested):
 113 ///   1. Add friend AnnotatedFoo<T> to Foo<T,Atom> (Typically, in Foo.h).
 114 ///   2. Define a class AuxData for whatever auxiliary data is needed
 115 ///      to maintain global knowledge of shared and private state.
 116 ///   3. Define:
 117 ///        static AuxData* aux_;
 118 ///        static FOLLY_TLS uint32_t tid_;
 119 ///   4. (Optional) Define gflags for command line options. E.g.:
 120 ///        DEFINE_int64(seed, 0, "Seed for random number generators");
 121 ///   5. (Optionl) Define macros for mangement of auxiliary data. E.g.,
 122 ///        #define AUX_THR(x)    (aux_->t_[tid_]->x)
 123 ///   6. (Optional) Define macro for creating auxiliary actions. E.g.,
 124 ///        #define AUX_ACT(act)                                       \
 125 ///          {                                                        \
 126 ///            AUX_THR(func_) = __func__;                             \
 127 ///            AUX_THR(line_) = __LINE__;                             \
 128 ///            AuxAct auxact([&](bool success) { if (success); act}); \
 129 ///            DeterministicSchedule::setAuxAct(auxact);              \
 130 ///          }
 131 ///      [Note: Auxiliary actions must not contain any standard shared
 132 ///      accesses, or else deadlock will occur. Use the load_direct()
 133 ///      member function of DeterministicAtomic instead.]
 134 ///   7. Define AnnotatedFoo<T> derived from Foo<T,DeterministicAtomic>.
 135 ///   8. Define member functions in AnnotatedFoo to manage DSched::auxChk.
 136 ///   9. Define member functions for logging and checkig global invariants.
 137 ///  10. Define member functions for direct access to data members of Foo.
 138 ///  11. (Optional) Add a member function dummyStep() to update
 139 ///      auxiliary data race-free when the next step is unknoown or
 140 ///      not conveniently accessible (e.g., in a different
 141 ///      library). The functions adds a dummy shared step to force
 142 ///      DSched to invoke the auxiliary action at a known point.This
 143 ///      is needed for now because DSched allows threads to run in
 144 ///      parallel between shared accesses. Hence, concurrent updates
 145 ///      of shared auxiliary data can be racy if executed outside
 146 ///      auxiliary actions. This may be obviated in the future if
 147 ///      DSched supports fully seriallized execution.
 148 ///        void dummyStep() {
 149 ///          DeterministicSchedule::beforeSharedAccess();
 150 ///          DeterministicSchedule::afterSharedAccess(true);
 151 ///        }
 152 ///  12. Override member functions of Foo as needed in order to
 153 ///      annotate the code with auxiliary actions. [Note: There may be
 154 ///      a lot of duplication of Foo's code. Alternatively, Foo can be
 155 ///      annotated directly.]
 156 ///  13. Define TEST using instances of AuxData and AnnotatedFoo.
 157 ///  14. For debugging, iteratively add (as needed) auxiliary data,
 158 ///      global invariants, logging details, command line flags as
 159 ///      needed and selectively generate relevant logs to detect the
 160 ///      race condition shortly after it occurs.
 161 ///
 162 /// In the following example Foo = AtomicCounter
 163
 164 using DSched = DeterministicSchedule;
 165
 166 /** Forward declaration of annotated template */
 167 template <typename T>
 168 struct AnnotatedAtomicCounter;
 169
 170 /** Original template to be tested */
 171 template <typename T, template <typename> class Atom = std::atomic>
 172 class AtomicCounter {
 173   /** Friend declaration to allow full access */
 174   friend struct AnnotatedAtomicCounter<T>;
 175
 176  public:
 177   explicit AtomicCounter(T val) : counter_(val) {}
 178
 179   void inc() {
 180     this->counter_.fetch_add(1);
 181   }
 182
 183   void incBug() {
 184     this->counter_.store(this->counter_.load() + 1);
 185   }
 186
 187   T load() {
 188     return this->counter_.load();
 189   }
 190
 191  private:
 192   Atom<T> counter_ = {0};
 193 };
 194
 195 /** auxiliary data */
 196 struct AuxData {
 197   using T = int;
 198
 199   /* General */
 200   uint64_t step_ = {0};
 201   uint64_t lastUpdate_ = {0};
 202
 203   struct PerThread {
 204     /* General */
 205     std::string func_;
 206     int line_;
 207     /* Custom */
 208     T count_ = {0};
 209   };
 210
 211   std::vector<PerThread> t_;
 212
 213   explicit AuxData(int nthr) : t_(nthr) {}
 214 };
 215
 216 static AuxData* aux_;
 217 static FOLLY_TLS uint32_t tid_;
 218
 219 /* Command line flags */
 220 DEFINE_int64(seed, 0, "Seed for random number generators");
 221 DEFINE_int64(max_steps, 1000000, "Max. number of shared steps for the test");
 222 DEFINE_int64(num_reps, 1, "Number of test repetitions");
 223 DEFINE_int64(num_ops, 1000, "Number of increments per repetition");
 224 DEFINE_int64(liveness_thresh, 1000000, "Liveness threshold");
 225 DEFINE_int64(log_begin, 0, "Step number to start logging. No logging if <= 0");
 226 DEFINE_int64(log_length, 1000, "Length of step by step log (if log_begin > 0)");
 227 DEFINE_int64(log_freq, 100000, "Log every so many steps");
 228 DEFINE_int32(num_threads, 1, "Number of producers");
 229 DEFINE_bool(bug, false, "Introduce bug");
 230
 231 /** Aux macros */
 232 #define AUX_THR(x) (aux_->t_[tid_].x)
 233 #define AUX_UPDATE() (aux_->lastUpdate_ = aux_->step_ + 1)
 234
 235 /** Macro for inline definition of auxiliary actions */
 236 #define AUX_ACT(act)                          \
 237   do {                                        \
 238     AUX_THR(func_) = __func__;                \
 239     AUX_THR(line_) = __LINE__;                \
 240     AuxAct auxfn(                             \
 241       [&](bool success) {                     \
 242         if (success) {}                       \
 243         if (true) {act}                       \
 244       }                                       \
 245     );                                        \
 246     DeterministicSchedule::setAuxAct(auxfn);  \
 247   } while (0)
 248
 249 /** Alias for original class */
 250 template <typename T>
 251 using Base = AtomicCounter<T, DeterministicAtomic>;
 252
 253 /** Annotated shared class */
 254 template <typename T>
 255 struct AnnotatedAtomicCounter : public Base<T> {
 256   /** Manage DSched auxChk */
 257   void setAuxChk() {
 258     AuxChk auxfn(
 259       [&](uint64_t step) {
 260         auxLog(step);
 261         auxCheck();
 262       }
 263     );
 264     DeterministicSchedule::setAuxChk(auxfn);
 265   }
 266
 267   void clearAuxChk() {
 268     DeterministicSchedule::clearAuxChk();
 269   }
 270
 271   /** Aux log function */
 272   void auxLog(uint64_t step) {
 273     if (aux_->step_ == 0) {
 274       aux_->lastUpdate_ = step;
 275     }
 276     aux_->step_ = step;
 277     if (step > (uint64_t)FLAGS_max_steps) {
 278       exit(0);
 279     }
 280     bool doLog =
 281         (((FLAGS_log_begin > 0) && (step >= (uint64_t)FLAGS_log_begin) &&
 282           (step <= (uint64_t)FLAGS_log_begin + FLAGS_log_length)) ||
 283          ((step % FLAGS_log_freq) == 0));
 284     if (doLog) {
 285       doAuxLog(step);
 286     }
 287   }
 288
 289   void doAuxLog(uint64_t step) {
 290     std::stringstream ss;
 291     /* General */
 292     ss << step << " - " << aux_->lastUpdate_ << " --";
 293     /* Shared */
 294     ss << " counter =" << this->counter_.load_direct();
 295     /* Thread */
 296     ss << " -- t" << tid_ << " " << AUX_THR(func_) << ":" << AUX_THR(line_);
 297     ss << " count[" << tid_ << "] = " << AUX_THR(count_);
 298     /* Output */
 299     std::cerr << ss.str() << std::endl;
 300   }
 301
 302   void auxCheck() {
 303     /* Liveness */
 304     CHECK_LT(aux_->step_, aux_->lastUpdate_ + FLAGS_liveness_thresh);
 305     /* Safety */
 306     int sum = {0};
 307     for (auto& t : aux_->t_) {
 308       sum += t.count_;
 309     }
 310     CHECK_EQ(this->counter_.load_direct(), sum);
 311   }
 312
 313   /* Direct access without going through DSched */
 314   T loadDirect() {
 315     return this->counter_.load_direct();
 316   }
 317
 318   /* Constructor -- calls original constructor */
 319   explicit AnnotatedAtomicCounter(int val) : Base<T>(val) {}
 320
 321   /* Overloads of original member functions (as needed) */
 322
 323   void inc() {
 324     AUX_ACT({ ++AUX_THR(count_); });
 325     this->counter_.fetch_add(1);
 326   }
 327
 328   void incBug() {
 329     AUX_ACT({});
 330     T newval = this->counter_.load() + 1;
 331     AUX_ACT({ ++AUX_THR(count_); });
 332     this->counter_.store(newval);
 333   }
 334 };
 335
 336 using Annotated = AnnotatedAtomicCounter<int>;
 337
 338 TEST(DeterministicSchedule, global_invariants) {
 339   CHECK_GT(FLAGS_num_threads, 0);
 340
 341   DSched sched(DSched::uniform(FLAGS_seed));
 342   for (int i = 0; i < FLAGS_num_reps; ++i) {
 343     aux_ = new AuxData(FLAGS_num_threads);
 344     Annotated annotated(0);
 345     annotated.setAuxChk();
 346
 347     std::vector<std::thread> threads(FLAGS_num_threads);
 348     for (int tid = 0; tid < FLAGS_num_threads; ++tid) {
 349       threads[tid] = DSched::thread([&, tid]() {
 350         tid_ = tid;
 351         for (int j = tid; j < FLAGS_num_ops; j += FLAGS_num_threads) {
 352           (FLAGS_bug) ? annotated.incBug() : annotated.inc();
 353         }
 354       });
 355     }
 356     for (auto& t : threads) {
 357       DSched::join(t);
 358     }
 359     std::cerr << "====== rep " << i << " completed in step " << aux_->step_
 360               << std::endl;
 361     annotated.doAuxLog(aux_->step_);
 362     std::cerr << std::endl;
 363     EXPECT_EQ(annotated.loadDirect(), FLAGS_num_ops);
 364     annotated.clearAuxChk();
 365     delete aux_;
 366   }
 367 }
 368
 369 int main(int argc, char** argv) {
 370   testing::InitGoogleTest(&argc, argv);
 371   gflags::ParseCommandLineFlags(&argc, &argv, true);
 372   return RUN_ALL_TESTS();
 373 }