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 | |
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 | 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 | |
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([&](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 */ |
251 | template <typename T> |
252 | using Base = AtomicCounter<T, DeterministicAtomic>; |
253 | |
254 | /** Annotated shared class */ |
255 | template <typename T> |
256 | struct 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 | |
335 | using Annotated = AnnotatedAtomicCounter<int>; |
336 | |
337 | TEST(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 | |
368 | struct DSchedTimestampTest : public DSchedTimestamp { |
369 | explicit DSchedTimestampTest(size_t v) : DSchedTimestamp(v) {} |
370 | }; |
371 | |
372 | TEST(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 | |
415 | int main(int argc, char** argv) { |
416 | testing::InitGoogleTest(&argc, argv); |
417 | gflags::ParseCommandLineFlags(&argc, &argv, true); |
418 | return RUN_ALL_TESTS(); |
419 | } |
420 | |