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 /// Testing support for auxiliary variables and global invariants
112 /** auxiliary variables for atomic counter test */
113 struct AtomicCounterAux {
114 std::vector<int> local_;
116 explicit AtomicCounterAux(int nthr) {
117 local_.resize(nthr, 0);
121 /** auxiliary function for checking global invariants and logging
122 * steps of atomic counter test */
123 void checkAtomicCounter(
126 DeterministicAtomic<int>& shared,
127 AtomicCounterAux& aux) {
128 /* read shared data */
129 int val = shared.load_direct();
130 /* read auxiliary variables */
132 for (int v : aux.local_) {
136 VLOG(2) << "Step " << step << " -- tid " << tid << " -- shared counter "
137 << val << " -- sum increments " << sum;
138 /* check invariant */
140 LOG(ERROR) << "Failed after step " << step;
141 LOG(ERROR) << "counter=(" << val << ") expected(" << sum << ")";
146 std::function<void(uint64_t, bool)> auxAtomicCounter(
147 DeterministicAtomic<int>& shared,
148 AtomicCounterAux& aux,
150 return [&shared, &aux, tid](uint64_t step, bool success) {
151 // update auxiliary data
156 checkAtomicCounter(tid, step, shared, aux);
160 DEFINE_bool(bug, false, "Introduce bug");
161 DEFINE_int64(seed, 0, "Seed for random number generator");
162 DEFINE_int32(num_threads, 2, "Number of threads");
163 DEFINE_int32(num_iterations, 10, "Number of iterations");
165 TEST(DSchedCustom, atomic_add) {
166 bool bug = FLAGS_bug;
167 long seed = FLAGS_seed;
168 int nthr = FLAGS_num_threads;
169 int niter = FLAGS_num_iterations;
173 DeterministicAtomic<int> counter{0};
174 AtomicCounterAux auxData(nthr);
175 DeterministicSchedule sched(DeterministicSchedule::uniform(seed));
177 std::vector<std::thread> threads(nthr);
178 for (int tid = 0; tid < nthr; ++tid) {
179 threads[tid] = DeterministicSchedule::thread([&, tid]() {
180 auto auxFn = auxAtomicCounter(counter, auxData, tid);
181 for (int i = 0; i < niter; ++i) {
182 if (bug && (tid == 0) && (i % 10 == 0)) {
183 int newval = counter.load() + 1;
184 DeterministicSchedule::setAux(auxFn);
185 counter.store(newval);
187 DeterministicSchedule::setAux(auxFn);
188 counter.fetch_add(1);
193 for (auto& t : threads) {
194 DeterministicSchedule::join(t);
196 EXPECT_EQ(counter.load_direct(), nthr * niter);
199 int main(int argc, char** argv) {
200 testing::InitGoogleTest(&argc, argv);
201 gflags::ParseCommandLineFlags(&argc, &argv, true);
202 return RUN_ALL_TESTS();