From f701dbadd9f705adc862ca3c81874149b3d1b928 Mon Sep 17 00:00:00 2001 From: Maged Michael Date: Wed, 5 Oct 2016 05:18:09 -0700 Subject: [PATCH] Updated example and methodology for using DeterministicSchedule support for auxiliary data and global invariants Summary: Depends on D3792669 Updating the test and methodology based on the experience with fine-grained testing dynamic MPMCQueue using DeterministicSchedule's support for auxiliary data and global invariants. Updates D3675447 Reviewed By: djwatson Differential Revision: D3794217 fbshipit-source-id: d2862895cb8dea120e758beeb24d6ae15191b013 --- folly/test/DeterministicScheduleTest.cpp | 325 +++++++++++++++-------- 1 file changed, 213 insertions(+), 112 deletions(-) diff --git a/folly/test/DeterministicScheduleTest.cpp b/folly/test/DeterministicScheduleTest.cpp index 7153f2b5..bdf7ebcb 100644 --- a/folly/test/DeterministicScheduleTest.cpp +++ b/folly/test/DeterministicScheduleTest.cpp @@ -106,51 +106,86 @@ TEST(DeterministicSchedule, buggyAdd) { } // for bug } // TEST -/// Test support for auxiliary data and global invariants +/// Test DSched 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 +/// How to use DSched support for auxiliary data and global invariants +/// (Let Foo be the template to be tested): +/// 1. Add friend AnnotatedFoo to Foo (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 derived from Foo. +/// 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 +struct AnnotatedAtomicCounter; -/** original shared class to be tested */ +/** Original template to be tested */ template class Atom = std::atomic> class AtomicCounter { - friend AnnotatedAtomicCounter; + /** Friend declaration to allow full access */ + friend struct AnnotatedAtomicCounter; 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: @@ -159,110 +194,176 @@ class AtomicCounter { /** 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 t_; - std::vector local_; + 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) \ + { \ + AUX_THR(func_) = __func__; \ + AUX_THR(line_) = __LINE__; \ + AuxAct auxfn( \ + [&](bool success) { \ + if (success); \ + if (true) {act} \ + } \ + ); \ + DeterministicSchedule::setAuxAct(auxfn); \ } -} -/** annotated shared class */ -class AnnotatedAtomicCounter { - public: - explicit AnnotatedAtomicCounter(int val) : shared_(val) {} +/** Alias for original class */ +template +using Base = AtomicCounter; + +/** Annotated shared class */ +template +struct AnnotatedAtomicCounter : public Base { + /** Manage DSched auxChk */ + void setAuxChk() { + AuxChk auxfn( + [&](uint64_t step) { + auxLog(step); + auxCheck(); + } + ); + DeterministicSchedule::setAuxChk(auxfn); + } - void inc(AuxAct& auxfn) { - DSched::setAuxAct(auxfn); - /* calls the fine-grained original */ - shared_.inc(); + void clearAuxChk() { + DeterministicSchedule::clearAuxChk(); } - 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); + /** 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); + } } - int load_direct() { - return shared_.counter_.load_direct(); + 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; } - private: - AtomicCounter shared_; -}; + 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); + } -using Annotated = AnnotatedAtomicCounter; + /* Direct access without going through DSched */ + T loadDirect() { + return this->counter_.load_direct(); + } + + /* Constructor -- calls original constructor */ + AnnotatedAtomicCounter(int val) : Base(val) {} + + /* Overloads of original member functions (as needed) */ -/** 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; + 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; -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 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 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) { -- 2.34.1