2 * Copyright 2013-present Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 #include <folly/test/DeterministicSchedule.h>
19 #include <folly/portability/GFlags.h>
20 #include <folly/portability/GTest.h>
22 using namespace folly::test;
24 TEST(DeterministicSchedule, uniform) {
25 auto p = DeterministicSchedule::uniform(0);
27 for (int i = 0; i < 100000; ++i) {
30 for (int i = 0; i < 10; ++i) {
31 EXPECT_TRUE(buckets[i] > 9000);
35 TEST(DeterministicSchedule, uniformSubset) {
36 auto ps = DeterministicSchedule::uniformSubset(0, 3, 100);
39 for (int i = 0; i < 100000; ++i) {
40 if (i > 0 && (i % 100) == 0) {
41 EXPECT_EQ(seen.size(), 3);
46 EXPECT_TRUE(seen.size() <= 3);
49 for (int i = 0; i < 10; ++i) {
50 EXPECT_TRUE(buckets[i] > 9000);
54 TEST(DeterministicSchedule, buggyAdd) {
55 for (bool bug : {false, true}) {
56 DeterministicSchedule sched(DeterministicSchedule::uniform(0));
58 FOLLY_TEST_DSCHED_VLOG("Test with race condition");
60 FOLLY_TEST_DSCHED_VLOG("Test without race condition");
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};
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
74 // Some threads use lock() others use try_lock()
82 int newval = test.load() + 1;
84 // Break the atomicity of the increment operation
94 for (auto& t : threads) {
95 DeterministicSchedule::join(t);
98 EXPECT_EQ(test.load(), baseline.load());
100 if (test.load() == baseline.load()) {
101 FOLLY_TEST_DSCHED_VLOG("Didn't catch the bug");
103 FOLLY_TEST_DSCHED_VLOG("Caught the bug");
110 * Test DSched support for auxiliary data and global invariants
112 * How to use DSched support for auxiliary data and global invariants
113 * (Let Foo<T, Atom> be the template to be tested):
114 * 1. Add friend AnnotatedFoo<T> to Foo<T,Atom> (Typically, in Foo.h).
115 * 2. Define a class AuxData for whatever auxiliary data is needed
116 * to maintain global knowledge of shared and private state.
118 * static AuxData* aux_;
119 * static FOLLY_TLS uint32_t tid_;
120 * 4. (Optional) Define gflags for command line options. E.g.:
121 * DEFINE_int64(seed, 0, "Seed for random number generators");
122 * 5. (Optionl) Define macros for mangement of auxiliary data. E.g.,
123 * #define AUX_THR(x) (aux_->t_[tid_]->x)
124 * 6. (Optional) Define macro for creating auxiliary actions. E.g.,
125 * #define AUX_ACT(act) \
127 * AUX_THR(func_) = __func__; \
128 * AUX_THR(line_) = __LINE__; \
129 * AuxAct auxact([&](bool success) { if (success); act}); \
130 * DeterministicSchedule::setAuxAct(auxact); \
132 * [Note: Auxiliary actions must not contain any standard shared
133 * accesses, or else deadlock will occur. Use the load_direct()
134 * member function of DeterministicAtomic instead.]
135 * 7. Define AnnotatedFoo<T> derived from Foo<T,DeterministicAtomic>.
136 * 8. Define member functions in AnnotatedFoo to manage DSched::auxChk.
137 * 9. Define member functions for logging and checkig global invariants.
138 * 10. Define member functions for direct access to data members of Foo.
139 * 11. (Optional) Add a member function dummyStep() to update
140 * auxiliary data race-free when the next step is unknoown or
141 * not conveniently accessible (e.g., in a different
142 * library). The functions adds a dummy shared step to force
143 * DSched to invoke the auxiliary action at a known point.This
144 * is needed for now because DSched allows threads to run in
145 * parallel between shared accesses. Hence, concurrent updates
146 * of shared auxiliary data can be racy if executed outside
147 * auxiliary actions. This may be obviated in the future if
148 * DSched supports fully seriallized execution.
150 * DeterministicSchedule::beforeSharedAccess();
151 * DeterministicSchedule::afterSharedAccess(true);
153 * 12. Override member functions of Foo as needed in order to
154 * annotate the code with auxiliary actions. [Note: There may be
155 * a lot of duplication of Foo's code. Alternatively, Foo can be
156 * annotated directly.]
157 * 13. Define TEST using instances of AuxData and AnnotatedFoo.
158 * 14. For debugging, iteratively add (as needed) auxiliary data,
159 * global invariants, logging details, command line flags as
160 * needed and selectively generate relevant logs to detect the
161 * race condition shortly after it occurs.
163 * In the following example Foo = AtomicCounter
166 using DSched = DeterministicSchedule;
168 /** Forward declaration of annotated template */
169 template <typename T>
170 struct AnnotatedAtomicCounter;
172 /** Original template to be tested */
173 template <typename T, template <typename> class Atom = std::atomic>
174 class AtomicCounter {
175 /** Friend declaration to allow full access */
176 friend struct AnnotatedAtomicCounter<T>;
179 explicit AtomicCounter(T val) : counter_(val) {}
182 this->counter_.fetch_add(1);
186 this->counter_.store(this->counter_.load() + 1);
190 return this->counter_.load();
194 Atom<T> counter_ = {0};
197 /** auxiliary data */
202 uint64_t step_ = {0};
203 uint64_t lastUpdate_ = {0};
213 std::vector<PerThread> t_;
215 explicit AuxData(int nthr) : t_(nthr) {}
218 static AuxData* aux_;
219 static FOLLY_TLS uint32_t tid_;
221 /* Command line flags */
222 DEFINE_int64(seed, 0, "Seed for random number generators");
223 DEFINE_int64(max_steps, 1000000, "Max. number of shared steps for the test");
224 DEFINE_int64(num_reps, 1, "Number of test repetitions");
225 DEFINE_int64(num_ops, 1000, "Number of increments per repetition");
226 DEFINE_int64(liveness_thresh, 1000000, "Liveness threshold");
227 DEFINE_int64(log_begin, 0, "Step number to start logging. No logging if <= 0");
228 DEFINE_int64(log_length, 1000, "Length of step by step log (if log_begin > 0)");
229 DEFINE_int64(log_freq, 100000, "Log every so many steps");
230 DEFINE_int32(num_threads, 1, "Number of producers");
231 DEFINE_bool(bug, false, "Introduce bug");
234 #define AUX_THR(x) (aux_->t_[tid_].x)
235 #define AUX_UPDATE() (aux_->lastUpdate_ = aux_->step_ + 1)
237 /** Macro for inline definition of auxiliary actions */
238 #define AUX_ACT(act) \
240 AUX_THR(func_) = __func__; \
241 AUX_THR(line_) = __LINE__; \
243 [&](bool success) { \
248 DeterministicSchedule::setAuxAct(auxfn); \
251 /** Alias for original class */
252 template <typename T>
253 using Base = AtomicCounter<T, DeterministicAtomic>;
255 /** Annotated shared class */
256 template <typename T>
257 struct AnnotatedAtomicCounter : public Base<T> {
258 /** Manage DSched auxChk */
266 DeterministicSchedule::setAuxChk(auxfn);
270 DeterministicSchedule::clearAuxChk();
273 /** Aux log function */
274 void auxLog(uint64_t step) {
275 if (aux_->step_ == 0) {
276 aux_->lastUpdate_ = step;
279 if (step > (uint64_t)FLAGS_max_steps) {
283 (((FLAGS_log_begin > 0) && (step >= (uint64_t)FLAGS_log_begin) &&
284 (step <= (uint64_t)FLAGS_log_begin + FLAGS_log_length)) ||
285 ((step % FLAGS_log_freq) == 0));
291 void doAuxLog(uint64_t step) {
292 std::stringstream ss;
294 ss << step << " - " << aux_->lastUpdate_ << " --";
296 ss << " counter =" << this->counter_.load_direct();
298 ss << " -- t" << tid_ << " " << AUX_THR(func_) << ":" << AUX_THR(line_);
299 ss << " count[" << tid_ << "] = " << AUX_THR(count_);
301 std::cerr << ss.str() << std::endl;
306 CHECK_LT(aux_->step_, aux_->lastUpdate_ + FLAGS_liveness_thresh);
309 for (auto& t : aux_->t_) {
312 CHECK_EQ(this->counter_.load_direct(), sum);
315 /* Direct access without going through DSched */
317 return this->counter_.load_direct();
320 /* Constructor -- calls original constructor */
321 explicit AnnotatedAtomicCounter(int val) : Base<T>(val) {}
323 /* Overloads of original member functions (as needed) */
326 AUX_ACT({ ++AUX_THR(count_); });
327 this->counter_.fetch_add(1);
332 T newval = this->counter_.load() + 1;
333 AUX_ACT({ ++AUX_THR(count_); });
334 this->counter_.store(newval);
338 using Annotated = AnnotatedAtomicCounter<int>;
340 TEST(DeterministicSchedule, global_invariants) {
341 CHECK_GT(FLAGS_num_threads, 0);
343 DSched sched(DSched::uniform(FLAGS_seed));
344 for (int i = 0; i < FLAGS_num_reps; ++i) {
345 aux_ = new AuxData(FLAGS_num_threads);
346 Annotated annotated(0);
347 annotated.setAuxChk();
349 std::vector<std::thread> threads(FLAGS_num_threads);
350 for (int tid = 0; tid < FLAGS_num_threads; ++tid) {
351 threads[tid] = DSched::thread([&, tid]() {
353 for (int j = tid; j < FLAGS_num_ops; j += FLAGS_num_threads) {
354 (FLAGS_bug) ? annotated.incBug() : annotated.inc();
358 for (auto& t : threads) {
361 std::cerr << "====== rep " << i << " completed in step " << aux_->step_
363 annotated.doAuxLog(aux_->step_);
364 std::cerr << std::endl;
365 EXPECT_EQ(annotated.loadDirect(), FLAGS_num_ops);
366 annotated.clearAuxChk();
371 int main(int argc, char** argv) {
372 testing::InitGoogleTest(&argc, argv);
373 gflags::ParseCommandLineFlags(&argc, &argv, true);
374 return RUN_ALL_TESTS();