/*
- * Copyright 2016 Facebook, Inc.
+ * Copyright 2013-present Facebook, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
}
}
} // for bug
-} // TEST
-
-/// Test support for auxiliary data and global invariants
-///
-
-/// How to use DSched support for auxiliary data and global invariants:
-/// 1. Forward declare an annotated shared class
-/// 2. Add the annotated shared class as a friend of the original class(es)
-/// to be tested
-/// 3. Define auxiliary data
-/// 4. Define function(s) for updating auxiliary data to match shared updates
-/// 5. Define the annotated shared class
-/// It supports an interface to the original class along with auxiliary
-/// functions for updating aux data, checking invariants, and/or logging
-/// It may have to duplicate the steps of multi-step operations in the
-//// original code in order to manage aux data and check invariants after
-/// shared accesses other than the first access in an opeeration
-/// 6. Define function for checking global invariants and/or logging global
-/// state
-/// 7. Define function generator(s) for function object(s) that update aux
-/// data, check invariants, and/or log state
-/// 8. Define TEST using anotated shared data, aux data, and aux functions
+}
+
+/*
+ * Test DSched support for auxiliary data and global invariants
+ *
+ * How to use DSched support for auxiliary data and global invariants
+ * (Let Foo<T, Atom> be the template to be tested):
+ * 1. Add friend AnnotatedFoo<T> to Foo<T,Atom> (Typically, in Foo.h).
+ * 2. Define a class AuxData for whatever auxiliary data is needed
+ * to maintain global knowledge of shared and private state.
+ * 3. Define:
+ * static AuxData* aux_;
+ * static FOLLY_TLS uint32_t tid_;
+ * 4. (Optional) Define gflags for command line options. E.g.:
+ * DEFINE_int64(seed, 0, "Seed for random number generators");
+ * 5. (Optionl) Define macros for mangement of auxiliary data. E.g.,
+ * #define AUX_THR(x) (aux_->t_[tid_]->x)
+ * 6. (Optional) Define macro for creating auxiliary actions. E.g.,
+ * #define AUX_ACT(act) \
+ * { \
+ * AUX_THR(func_) = __func__; \
+ * AUX_THR(line_) = __LINE__; \
+ * AuxAct auxact([&](bool success) { if (success); act}); \
+ * DeterministicSchedule::setAuxAct(auxact); \
+ * }
+ * [Note: Auxiliary actions must not contain any standard shared
+ * accesses, or else deadlock will occur. Use the load_direct()
+ * member function of DeterministicAtomic instead.]
+ * 7. Define AnnotatedFoo<T> derived from Foo<T,DeterministicAtomic>.
+ * 8. Define member functions in AnnotatedFoo to manage DSched::auxChk.
+ * 9. Define member functions for logging and checkig global invariants.
+ * 10. Define member functions for direct access to data members of Foo.
+ * 11. (Optional) Add a member function dummyStep() to update
+ * auxiliary data race-free when the next step is unknoown or
+ * not conveniently accessible (e.g., in a different
+ * library). The functions adds a dummy shared step to force
+ * DSched to invoke the auxiliary action at a known point.This
+ * is needed for now because DSched allows threads to run in
+ * parallel between shared accesses. Hence, concurrent updates
+ * of shared auxiliary data can be racy if executed outside
+ * auxiliary actions. This may be obviated in the future if
+ * DSched supports fully seriallized execution.
+ * void dummyStep() {
+ * DeterministicSchedule::beforeSharedAccess();
+ * DeterministicSchedule::afterSharedAccess(true);
+ * }
+ * 12. Override member functions of Foo as needed in order to
+ * annotate the code with auxiliary actions. [Note: There may be
+ * a lot of duplication of Foo's code. Alternatively, Foo can be
+ * annotated directly.]
+ * 13. Define TEST using instances of AuxData and AnnotatedFoo.
+ * 14. For debugging, iteratively add (as needed) auxiliary data,
+ * global invariants, logging details, command line flags as
+ * needed and selectively generate relevant logs to detect the
+ * race condition shortly after it occurs.
+ *
+ * In the following example Foo = AtomicCounter
+ */
using DSched = DeterministicSchedule;
-/** forward declaration of annotated shared class */
-class AnnotatedAtomicCounter;
+/** Forward declaration of annotated template */
+template <typename T>
+struct AnnotatedAtomicCounter;
-/** original shared class to be tested */
+/** Original template to be tested */
template <typename T, template <typename> class Atom = std::atomic>
class AtomicCounter {
- friend AnnotatedAtomicCounter;
+ /** Friend declaration to allow full access */
+ friend struct AnnotatedAtomicCounter<T>;
public:
explicit AtomicCounter(T val) : counter_(val) {}
void inc() {
- counter_.fetch_add(1);
+ this->counter_.fetch_add(1);
}
- void inc_bug() {
- int newval = counter_.load() + 1;
- counter_.store(newval);
+ void incBug() {
+ this->counter_.store(this->counter_.load() + 1);
}
T load() {
- return counter_.load();
+ return this->counter_.load();
}
private:
/** auxiliary data */
struct AuxData {
- explicit AuxData(int nthr) {
- local_.resize(nthr, 0);
- }
+ using T = int;
+
+ /* General */
+ uint64_t step_ = {0};
+ uint64_t lastUpdate_ = {0};
+
+ struct PerThread {
+ /* General */
+ std::string func_;
+ int line_;
+ /* Custom */
+ T count_ = {0};
+ };
- std::vector<int> local_;
+ std::vector<PerThread> t_;
+
+ explicit AuxData(int nthr) : t_(nthr) {}
};
-/** aux update function(s) */
-void auxUpdateAfterInc(int tid, AuxData& auxdata, bool success) {
- if (success) {
- auxdata.local_[tid]++;
+static AuxData* aux_;
+static FOLLY_TLS uint32_t tid_;
+
+/* Command line flags */
+DEFINE_int64(seed, 0, "Seed for random number generators");
+DEFINE_int64(max_steps, 1000000, "Max. number of shared steps for the test");
+DEFINE_int64(num_reps, 1, "Number of test repetitions");
+DEFINE_int64(num_ops, 1000, "Number of increments per repetition");
+DEFINE_int64(liveness_thresh, 1000000, "Liveness threshold");
+DEFINE_int64(log_begin, 0, "Step number to start logging. No logging if <= 0");
+DEFINE_int64(log_length, 1000, "Length of step by step log (if log_begin > 0)");
+DEFINE_int64(log_freq, 100000, "Log every so many steps");
+DEFINE_int32(num_threads, 1, "Number of producers");
+DEFINE_bool(bug, false, "Introduce bug");
+
+/** Aux macros */
+#define AUX_THR(x) (aux_->t_[tid_].x)
+#define AUX_UPDATE() (aux_->lastUpdate_ = aux_->step_ + 1)
+
+/** Macro for inline definition of auxiliary actions */
+#define AUX_ACT(act) \
+ do { \
+ AUX_THR(func_) = __func__; \
+ AUX_THR(line_) = __LINE__; \
+ AuxAct auxfn( \
+ [&](bool success) { \
+ if (success) {} \
+ if (true) {act} \
+ } \
+ ); \
+ DeterministicSchedule::setAuxAct(auxfn); \
+ } while (0)
+
+/** Alias for original class */
+template <typename T>
+using Base = AtomicCounter<T, DeterministicAtomic>;
+
+/** Annotated shared class */
+template <typename T>
+struct AnnotatedAtomicCounter : public Base<T> {
+ /** Manage DSched auxChk */
+ void setAuxChk() {
+ AuxChk auxfn(
+ [&](uint64_t step) {
+ auxLog(step);
+ auxCheck();
+ }
+ );
+ DeterministicSchedule::setAuxChk(auxfn);
}
-}
-/** annotated shared class */
-class AnnotatedAtomicCounter {
- public:
- explicit AnnotatedAtomicCounter(int val) : shared_(val) {}
+ void clearAuxChk() {
+ DeterministicSchedule::clearAuxChk();
+ }
- void inc(AuxAct& auxfn) {
- DSched::setAuxAct(auxfn);
- /* calls the fine-grained original */
- shared_.inc();
+ /** Aux log function */
+ void auxLog(uint64_t step) {
+ if (aux_->step_ == 0) {
+ aux_->lastUpdate_ = step;
+ }
+ aux_->step_ = step;
+ if (step > (uint64_t)FLAGS_max_steps) {
+ exit(0);
+ }
+ bool doLog =
+ (((FLAGS_log_begin > 0) && (step >= (uint64_t)FLAGS_log_begin) &&
+ (step <= (uint64_t)FLAGS_log_begin + FLAGS_log_length)) ||
+ ((step % FLAGS_log_freq) == 0));
+ if (doLog) {
+ doAuxLog(step);
+ }
}
- void inc_bug(AuxAct auxfn) {
- /* duplicates the steps of the multi-access original in order to
- * annotate the second access */
- int newval = shared_.counter_.load() + 1;
- DSched::setAuxAct(auxfn);
- shared_.counter_.store(newval);
+ void doAuxLog(uint64_t step) {
+ std::stringstream ss;
+ /* General */
+ ss << step << " - " << aux_->lastUpdate_ << " --";
+ /* Shared */
+ ss << " counter =" << this->counter_.load_direct();
+ /* Thread */
+ ss << " -- t" << tid_ << " " << AUX_THR(func_) << ":" << AUX_THR(line_);
+ ss << " count[" << tid_ << "] = " << AUX_THR(count_);
+ /* Output */
+ std::cerr << ss.str() << std::endl;
}
- int load_direct() {
- return shared_.counter_.load_direct();
+ void auxCheck() {
+ /* Liveness */
+ CHECK_LT(aux_->step_, aux_->lastUpdate_ + FLAGS_liveness_thresh);
+ /* Safety */
+ int sum = {0};
+ for (auto& t : aux_->t_) {
+ sum += t.count_;
+ }
+ CHECK_EQ(this->counter_.load_direct(), sum);
}
- private:
- AtomicCounter<int, DeterministicAtomic> shared_;
-};
+ /* Direct access without going through DSched */
+ T loadDirect() {
+ return this->counter_.load_direct();
+ }
-using Annotated = AnnotatedAtomicCounter;
+ /* Constructor -- calls original constructor */
+ explicit AnnotatedAtomicCounter(int val) : Base<T>(val) {}
-/** aux log & check function */
-void auxCheck(int tid, Annotated& annotated, AuxData& auxdata) {
- /* read shared data */
- int val = annotated.load_direct();
- /* read auxiliary data */
- int sum = 0;
- for (int v : auxdata.local_) {
- sum += v;
+ /* Overloads of original member functions (as needed) */
+
+ void inc() {
+ AUX_ACT({ ++AUX_THR(count_); });
+ this->counter_.fetch_add(1);
}
- /* log state */
- VLOG(2) << "tid " << tid << " -- shared counter= " << val
- << " -- sum increments= " << sum;
- /* check invariant */
- if (val != sum) {
- LOG(ERROR) << "counter=(" << val << ") expected(" << sum << ")";
- CHECK(false);
+
+ void incBug() {
+ AUX_ACT({});
+ T newval = this->counter_.load() + 1;
+ AUX_ACT({ ++AUX_THR(count_); });
+ this->counter_.store(newval);
}
-}
+};
-/** function generator(s) */
-AuxAct auxAfterInc(int tid, Annotated& annotated, AuxData& auxdata) {
- return [&annotated, &auxdata, tid](bool success) {
- auxUpdateAfterInc(tid, auxdata, success);
- auxCheck(tid, annotated, auxdata);
- };
-}
+using Annotated = AnnotatedAtomicCounter<int>;
-DEFINE_bool(bug, false, "Introduce bug");
-DEFINE_int64(seed, 0, "Seed for random number generator");
-DEFINE_int32(num_threads, 2, "Number of threads");
-DEFINE_int32(num_iterations, 10, "Number of iterations");
-
-TEST(DSchedCustom, atomic_add) {
- bool bug = FLAGS_bug;
- long seed = FLAGS_seed;
- int nthr = FLAGS_num_threads;
- int niter = FLAGS_num_iterations;
-
- CHECK_GT(nthr, 0);
-
- Annotated annotated(0);
- AuxData auxdata(nthr);
- DSched sched(DSched::uniform(seed));
-
- std::vector<std::thread> threads(nthr);
- for (int tid = 0; tid < nthr; ++tid) {
- threads[tid] = DSched::thread([&, tid]() {
- AuxAct auxfn = auxAfterInc(tid, annotated, auxdata);
- for (int i = 0; i < niter; ++i) {
- if (bug && (tid == 0) && (i % 10 == 0)) {
- annotated.inc_bug(auxfn);
- } else {
- annotated.inc(auxfn);
+TEST(DeterministicSchedule, global_invariants) {
+ CHECK_GT(FLAGS_num_threads, 0);
+
+ DSched sched(DSched::uniform(FLAGS_seed));
+ for (int i = 0; i < FLAGS_num_reps; ++i) {
+ aux_ = new AuxData(FLAGS_num_threads);
+ Annotated annotated(0);
+ annotated.setAuxChk();
+
+ std::vector<std::thread> threads(FLAGS_num_threads);
+ for (int tid = 0; tid < FLAGS_num_threads; ++tid) {
+ threads[tid] = DSched::thread([&, tid]() {
+ tid_ = tid;
+ for (int j = tid; j < FLAGS_num_ops; j += FLAGS_num_threads) {
+ (FLAGS_bug) ? annotated.incBug() : annotated.inc();
}
- }
- });
- }
- for (auto& t : threads) {
- DSched::join(t);
+ });
+ }
+ for (auto& t : threads) {
+ DSched::join(t);
+ }
+ std::cerr << "====== rep " << i << " completed in step " << aux_->step_
+ << std::endl;
+ annotated.doAuxLog(aux_->step_);
+ std::cerr << std::endl;
+ EXPECT_EQ(annotated.loadDirect(), FLAGS_num_ops);
+ annotated.clearAuxChk();
+ delete aux_;
}
- EXPECT_EQ(annotated.load_direct(), nthr * niter);
}
int main(int argc, char** argv) {
projects / folly.git / blobdiff