f494ad37618ca76fae9b139c9a2066ee49577ee2
[folly.git] / 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 } // TEST
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 }