1/*
2 * Copyright 2013-present 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
22using namespace folly::test;
23
24TEST(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
35TEST(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
54TEST(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 DeterministicSchedule::joinAll(threads);
95 if (!bug) {
96 EXPECT_EQ(test.load(), baseline.load());
97 } else {
98 if (test.load() == baseline.load()) {
99 FOLLY_TEST_DSCHED_VLOG("Didn't catch the bug");
100 } else {
101 FOLLY_TEST_DSCHED_VLOG("Caught the bug");
102 }
103 }
104 } // for bug
105}
106
107/*
108 * Test DSched support for auxiliary data and global invariants
109 *
110 * How to use DSched support for auxiliary data and global invariants
111 * (Let Foo<T, Atom> be the template to be tested):
112 * 1. Add friend AnnotatedFoo<T> to Foo<T,Atom> (Typically, in Foo.h).
113 * 2. Define a class AuxData for whatever auxiliary data is needed
114 * to maintain global knowledge of shared and private state.
115 * 3. Define:
116 * static AuxData* aux_;
117 * static FOLLY_TLS uint32_t tid_;
118 * 4. (Optional) Define gflags for command line options. E.g.:
119 * DEFINE_int64(seed, 0, "Seed for random number generators");
120 * 5. (Optionl) Define macros for mangement of auxiliary data. E.g.,
121 * #define AUX_THR(x) (aux_->t_[tid_]->x)
122 * 6. (Optional) Define macro for creating auxiliary actions. E.g.,
123 * #define AUX_ACT(act) \
124 * { \
125 * AUX_THR(func_) = __func__; \
126 * AUX_THR(line_) = __LINE__; \
127 * AuxAct auxact([&](bool success) { if (success); act}); \
128 * DeterministicSchedule::setAuxAct(auxact); \
129 * }
130 * [Note: Auxiliary actions must not contain any standard shared
131 * accesses, or else deadlock will occur. Use the load_direct()
132 * member function of DeterministicAtomic instead.]
133 * 7. Define AnnotatedFoo<T> derived from Foo<T,DeterministicAtomic>.
134 * 8. Define member functions in AnnotatedFoo to manage DSched::auxChk.
135 * 9. Define member functions for logging and checkig global invariants.
136 * 10. Define member functions for direct access to data members of Foo.
137 * 11. (Optional) Add a member function dummyStep() to update
138 * auxiliary data race-free when the next step is unknoown or
139 * not conveniently accessible (e.g., in a different
140 * library). The functions adds a dummy shared step to force
141 * DSched to invoke the auxiliary action at a known point.This
142 * is needed for now because DSched allows threads to run in
143 * parallel between shared accesses. Hence, concurrent updates
144 * of shared auxiliary data can be racy if executed outside
145 * auxiliary actions. This may be obviated in the future if
146 * DSched supports fully seriallized execution.
147 * void dummyStep() {
148 * DeterministicSchedule::beforeSharedAccess();
149 * DeterministicSchedule::afterSharedAccess(true);
150 * }
151 * 12. Override member functions of Foo as needed in order to
152 * annotate the code with auxiliary actions. [Note: There may be
153 * a lot of duplication of Foo's code. Alternatively, Foo can be
154 * annotated directly.]
155 * 13. Define TEST using instances of AuxData and AnnotatedFoo.
156 * 14. For debugging, iteratively add (as needed) auxiliary data,
157 * global invariants, logging details, command line flags as
158 * needed and selectively generate relevant logs to detect the
159 * race condition shortly after it occurs.
160 *
161 * In the following example Foo = AtomicCounter
162 */
163
164using DSched = DeterministicSchedule;
165
166/** Forward declaration of annotated template */
167template <typename T>
168struct AnnotatedAtomicCounter;
169
170/** Original template to be tested */
171template <typename T, template <typename> class Atom = std::atomic>
172class 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 */
196struct 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
216static AuxData* aux_;
217static FOLLY_TLS uint32_t tid_;
218
219/* Command line flags */
220DEFINE_int64(seed, 0, "Seed for random number generators");
221DEFINE_int64(max_steps, 1000000, "Max. number of shared steps for the test");
222DEFINE_int64(num_reps, 1, "Number of test repetitions");
223DEFINE_int64(num_ops, 1000, "Number of increments per repetition");
224DEFINE_int64(liveness_thresh, 1000000, "Liveness threshold");
225DEFINE_int64(log_begin, 0, "Step number to start logging. No logging if <= 0");
226DEFINE_int64(log_length, 1000, "Length of step by step log (if log_begin > 0)");
227DEFINE_int64(log_freq, 100000, "Log every so many steps");
228DEFINE_int32(num_threads, 1, "Number of producers");
229DEFINE_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([&](bool success) { \
241 if (success) { \
242 } \
243 if (true) { \
244 act \
245 } \
246 }); \
247 DeterministicSchedule::setAuxAct(auxfn); \
248 } while (0)
249
250/** Alias for original class */
251template <typename T>
252using Base = AtomicCounter<T, DeterministicAtomic>;
253
254/** Annotated shared class */
255template <typename T>
256struct AnnotatedAtomicCounter : public Base<T> {
257 /** Manage DSched auxChk */
258 void setAuxChk() {
259 AuxChk auxfn([&](uint64_t step) {
260 auxLog(step);
261 auxCheck();
262 });
263 DeterministicSchedule::setAuxChk(auxfn);
264 }
265
266 void clearAuxChk() {
267 DeterministicSchedule::clearAuxChk();
268 }
269
270 /** Aux log function */
271 void auxLog(uint64_t step) {
272 if (aux_->step_ == 0) {
273 aux_->lastUpdate_ = step;
274 }
275 aux_->step_ = step;
276 if (step > (uint64_t)FLAGS_max_steps) {
277 exit(0);
278 }
279 bool doLog =
280 (((FLAGS_log_begin > 0) && (step >= (uint64_t)FLAGS_log_begin) &&
281 (step <= (uint64_t)FLAGS_log_begin + FLAGS_log_length)) ||
282 ((step % FLAGS_log_freq) == 0));
283 if (doLog) {
284 doAuxLog(step);
285 }
286 }
287
288 void doAuxLog(uint64_t step) {
289 std::stringstream ss;
290 /* General */
291 ss << step << " - " << aux_->lastUpdate_ << " --";
292 /* Shared */
293 ss << " counter =" << this->counter_.load_direct();
294 /* Thread */
295 ss << " -- t" << tid_ << " " << AUX_THR(func_) << ":" << AUX_THR(line_);
296 ss << " count[" << tid_ << "] = " << AUX_THR(count_);
297 /* Output */
298 std::cerr << ss.str() << std::endl;
299 }
300
301 void auxCheck() {
302 /* Liveness */
303 CHECK_LT(aux_->step_, aux_->lastUpdate_ + FLAGS_liveness_thresh);
304 /* Safety */
305 int sum = {0};
306 for (auto& t : aux_->t_) {
307 sum += t.count_;
308 }
309 CHECK_EQ(this->counter_.load_direct(), sum);
310 }
311
312 /* Direct access without going through DSched */
313 T loadDirect() {
314 return this->counter_.load_direct();
315 }
316
317 /* Constructor -- calls original constructor */
318 explicit AnnotatedAtomicCounter(int val) : Base<T>(val) {}
319
320 /* Overloads of original member functions (as needed) */
321
322 void inc() {
323 AUX_ACT({ ++AUX_THR(count_); });
324 this->counter_.fetch_add(1);
325 }
326
327 void incBug() {
328 AUX_ACT({});
329 T newval = this->counter_.load() + 1;
330 AUX_ACT({ ++AUX_THR(count_); });
331 this->counter_.store(newval);
332 }
333};
334
335using Annotated = AnnotatedAtomicCounter<int>;
336
337TEST(DeterministicSchedule, global_invariants) {
338 CHECK_GT(FLAGS_num_threads, 0);
339
340 DSched sched(DSched::uniform(FLAGS_seed));
341 for (int i = 0; i < FLAGS_num_reps; ++i) {
342 aux_ = new AuxData(FLAGS_num_threads);
343 Annotated annotated(0);
344 annotated.setAuxChk();
345
346 std::vector<std::thread> threads(FLAGS_num_threads);
347 for (int tid = 0; tid < FLAGS_num_threads; ++tid) {
348 threads[tid] = DSched::thread([&, tid]() {
349 tid_ = tid;
350 for (int j = tid; j < FLAGS_num_ops; j += FLAGS_num_threads) {
351 (FLAGS_bug) ? annotated.incBug() : annotated.inc();
352 }
353 });
354 }
355 for (auto& t : threads) {
356 DSched::join(t);
357 }
358 std::cerr << "====== rep " << i << " completed in step " << aux_->step_
359 << std::endl;
360 annotated.doAuxLog(aux_->step_);
361 std::cerr << std::endl;
362 EXPECT_EQ(annotated.loadDirect(), FLAGS_num_ops);
363 annotated.clearAuxChk();
364 delete aux_;
365 }
366}
367
368struct DSchedTimestampTest : public DSchedTimestamp {
369 explicit DSchedTimestampTest(size_t v) : DSchedTimestamp(v) {}
370};
371
372TEST(DeterministicSchedule, thread_timestamps) {
373 ThreadTimestamps tss;
374 DSchedThreadId tid0(0);
375 DSchedThreadId tid1(1);
376
377 ASSERT_FALSE(tss.atLeastAsRecentAs(tid0, DSchedTimestampTest(1)));
378
379 tss.setIfNotPresent(tid0, DSchedTimestampTest(1));
380 ASSERT_TRUE(tss.atLeastAsRecentAs(tid0, DSchedTimestampTest(1)));
381 ASSERT_FALSE(tss.atLeastAsRecentAs(tid0, DSchedTimestampTest(2)));
382 ASSERT_FALSE(tss.atLeastAsRecentAs(tid1, DSchedTimestampTest(1)));
383
384 tss.setIfNotPresent(tid0, DSchedTimestampTest(2));
385 ASSERT_FALSE(tss.atLeastAsRecentAs(tid0, DSchedTimestampTest(2)));
386
387 auto ts = tss.advance(tid0);
388 ASSERT_TRUE(ts.atLeastAsRecentAs(DSchedTimestampTest(2)));
389 ASSERT_FALSE(ts.atLeastAsRecentAs(DSchedTimestampTest(3)));
390 ASSERT_TRUE(tss.atLeastAsRecentAs(tid0, DSchedTimestampTest(2)));
391 ASSERT_FALSE(tss.atLeastAsRecentAs(tid1, DSchedTimestampTest(1)));
392
393 ThreadTimestamps tss2;
394 tss2.setIfNotPresent(tid1, DSchedTimestampTest(3));
395 ASSERT_FALSE(tss2.atLeastAsRecentAs(tid1, DSchedTimestampTest(4)));
396 ASSERT_TRUE(tss2.atLeastAsRecentAs(tid1, DSchedTimestampTest(3)));
397
398 ASSERT_FALSE(tss.atLeastAsRecentAsAny(tss2));
399 tss.sync(tss2);
400 ASSERT_TRUE(tss.atLeastAsRecentAs(tid1, DSchedTimestampTest(3)));
401 ASSERT_FALSE(tss.atLeastAsRecentAs(tid1, DSchedTimestampTest(4)));
402
403 ThreadTimestamps tss3;
404 tss3.setIfNotPresent(tid1, DSchedTimestampTest(4));
405 ASSERT_TRUE(tss3.atLeastAsRecentAsAny(tss2));
406 ASSERT_FALSE(tss2.atLeastAsRecentAsAny(tss3));
407
408 ThreadTimestamps tss4, tss5;
409 tss4.setIfNotPresent(DSchedThreadId(10), DSchedTimestampTest(5));
410 tss5.setIfNotPresent(DSchedThreadId(11), DSchedTimestampTest(5));
411 ASSERT_FALSE(tss4.atLeastAsRecentAsAny(tss5));
412 ASSERT_FALSE(tss5.atLeastAsRecentAsAny(tss4));
413}
414
415int main(int argc, char** argv) {
416 testing::InitGoogleTest(&argc, argv);
417 gflags::ParseCommandLineFlags(&argc, &argv, true);
418 return RUN_ALL_TESTS();
419}
420