2 * Copyright 2016 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 <gtest/gtest.h>
21 #include <folly/portability/GFlags.h>
23 using namespace folly::test;
25 TEST(DeterministicSchedule, uniform) {
26 auto p = DeterministicSchedule::uniform(0);
28 for (int i = 0; i < 100000; ++i) {
31 for (int i = 0; i < 10; ++i) {
32 EXPECT_TRUE(buckets[i] > 9000);
36 TEST(DeterministicSchedule, uniformSubset) {
37 auto ps = DeterministicSchedule::uniformSubset(0, 3, 100);
40 for (int i = 0; i < 100000; ++i) {
41 if (i > 0 && (i % 100) == 0) {
42 EXPECT_EQ(seen.size(), 3);
47 EXPECT_TRUE(seen.size() <= 3);
50 for (int i = 0; i < 10; ++i) {
51 EXPECT_TRUE(buckets[i] > 9000);
55 TEST(DeterministicSchedule, buggyAdd) {
56 for (bool bug : {false, true}) {
57 DeterministicSchedule sched(DeterministicSchedule::uniform(0));
59 FOLLY_TEST_DSCHED_VLOG("Test with race condition");
61 FOLLY_TEST_DSCHED_VLOG("Test without race condition");
64 // The use of DeterinisticAtomic is not needed here, but it makes
65 // it easier to understand the sequence of events in logs.
66 DeterministicAtomic<int> test{0};
67 DeterministicAtomic<int> baseline{0};
69 std::vector<std::thread> threads(numThreads);
70 for (int t = 0; t < numThreads; ++t) {
71 threads[t] = DeterministicSchedule::thread([&, t] {
72 baseline.fetch_add(1);
73 // Atomic increment of test protected by mutex m
75 // Some threads use lock() others use try_lock()
83 int newval = test.load() + 1;
85 // Break the atomicity of the increment operation
95 for (auto& t : threads) {
96 DeterministicSchedule::join(t);
99 EXPECT_EQ(test.load(), baseline.load());
101 if (test.load() == baseline.load()) {
102 FOLLY_TEST_DSCHED_VLOG("Didn't catch the bug");
104 FOLLY_TEST_DSCHED_VLOG("Caught the bug");
110 /// Test support for auxiliary data and global invariants
113 /// How to use DSched support for auxiliary data and global invariants:
114 /// 1. Forward declare an annotated shared class
115 /// 2. Add the annotated shared class as a friend of the original class(es)
117 /// 3. Define auxiliary data
118 /// 4. Define function(s) for updating auxiliary data to match shared updates
119 /// 5. Define the annotated shared class
120 /// It supports an interface to the original class along with auxiliary
121 /// functions for updating aux data, checking invariants, and/or logging
122 /// It may have to duplicate the steps of multi-step operations in the
123 //// original code in order to manage aux data and check invariants after
124 /// shared accesses other than the first access in an opeeration
125 /// 6. Define function for checking global invariants and/or logging global
127 /// 7. Define function generator(s) for function object(s) that update aux
128 /// data, check invariants, and/or log state
129 /// 8. Define TEST using anotated shared data, aux data, and aux functions
131 using DSched = DeterministicSchedule;
132 using AuxFn = std::function<void(uint64_t, bool)>;
134 /** forward declaration of annotated shared class */
135 class AnnotatedAtomicCounter;
137 /** original shared class to be tested */
138 template <typename T, template <typename> class Atom = std::atomic>
139 class AtomicCounter {
140 friend AnnotatedAtomicCounter;
143 explicit AtomicCounter(T val) : counter_(val) {}
146 counter_.fetch_add(1);
150 int newval = counter_.load() + 1;
151 counter_.store(newval);
155 return counter_.load();
159 Atom<T> counter_ = {0};
162 /** auxiliary data */
164 explicit AuxData(int nthr) {
165 local_.resize(nthr, 0);
168 std::vector<int> local_;
171 /** aux update function(s) */
172 void auxUpdateAfterInc(int tid, AuxData& auxdata, bool success) {
174 auxdata.local_[tid]++;
178 /** annotated shared class */
179 class AnnotatedAtomicCounter {
181 explicit AnnotatedAtomicCounter(int val) : shared_(val) {}
183 void inc(AuxFn& auxfn) {
184 DSched::setAux(auxfn);
185 /* calls the fine-grained original */
189 void inc_bug(AuxFn auxfn) {
190 /* duplicates the steps of the multi-access original in order to
191 * annotate the second access */
192 int newval = shared_.counter_.load() + 1;
193 DSched::setAux(auxfn);
194 shared_.counter_.store(newval);
198 return shared_.counter_.load_direct();
202 AtomicCounter<int, DeterministicAtomic> shared_;
205 using Annotated = AnnotatedAtomicCounter;
207 /** aux log & check function */
208 void auxCheck(int tid, uint64_t step, Annotated& annotated, AuxData& auxdata) {
209 /* read shared data */
210 int val = annotated.load_direct();
211 /* read auxiliary data */
213 for (int v : auxdata.local_) {
217 VLOG(2) << "Step " << step << " -- tid " << tid
218 << " -- shared counter= " << val << " -- sum increments= " << sum;
219 /* check invariant */
221 LOG(ERROR) << "Failed after step " << step;
222 LOG(ERROR) << "counter=(" << val << ") expected(" << sum << ")";
227 /** function generator(s) */
228 AuxFn auxAfterInc(int tid, Annotated& annotated, AuxData& auxdata) {
229 return [&annotated, &auxdata, tid](uint64_t step, bool success) {
230 auxUpdateAfterInc(tid, auxdata, success);
231 auxCheck(tid, step, annotated, auxdata);
235 DEFINE_bool(bug, false, "Introduce bug");
236 DEFINE_int64(seed, 0, "Seed for random number generator");
237 DEFINE_int32(num_threads, 2, "Number of threads");
238 DEFINE_int32(num_iterations, 10, "Number of iterations");
240 TEST(DSchedCustom, atomic_add) {
241 bool bug = FLAGS_bug;
242 long seed = FLAGS_seed;
243 int nthr = FLAGS_num_threads;
244 int niter = FLAGS_num_iterations;
248 Annotated annotated(0);
249 AuxData auxdata(nthr);
250 DSched sched(DSched::uniform(seed));
252 std::vector<std::thread> threads(nthr);
253 for (int tid = 0; tid < nthr; ++tid) {
254 threads[tid] = DSched::thread([&, tid]() {
255 AuxFn auxfn = auxAfterInc(tid, annotated, auxdata);
256 for (int i = 0; i < niter; ++i) {
257 if (bug && (tid == 0) && (i % 10 == 0)) {
258 annotated.inc_bug(auxfn);
260 annotated.inc(auxfn);
265 for (auto& t : threads) {
268 EXPECT_EQ(annotated.load_direct(), nthr * niter);
271 int main(int argc, char** argv) {
272 testing::InitGoogleTest(&argc, argv);
273 gflags::ParseCommandLineFlags(&argc, &argv, true);
274 return RUN_ALL_TESTS();