DeterministicScheduleTest.cpp File Reference

#include <folly/test/DeterministicSchedule.h>
#include <folly/portability/GFlags.h>
#include <folly/portability/GTest.h>

Go to the source code of this file.

Classes
struct	AnnotatedAtomicCounter< T >
class	AtomicCounter< T, Atom >
struct	AuxData
struct	AuxData::PerThread
struct	AnnotatedAtomicCounter< T >

Macros
#define	AUX_THR(x)   (aux_->t_[tid_].x)
#define	AUX_UPDATE()   (aux_->lastUpdate_ = aux_->step_ + 1)
#define	AUX_ACT(act)

Typedefs
using	DSched = DeterministicSchedule
template<typename T >
using	Base = AtomicCounter< T, DeterministicAtomic >
using	Annotated = AnnotatedAtomicCounter< int >

Functions
	TEST (DeterministicSchedule, uniform)
	TEST (DeterministicSchedule, uniformSubset)
	TEST (DeterministicSchedule, buggyAdd)
	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")
	TEST (DeterministicSchedule, global_invariants)
int	main (int argc, char **argv)

Variables
static AuxData *	aux_
static FOLLY_TLS uint32_t	tid_

Macro Definition Documentation

#define AUX_ACT

(

act

)

Value:

do {                                       \
    AUX_THR(func_) = __func__;               \
    AUX_THR(line_) = __LINE__;               \
    AuxAct auxfn([&](bool success) {         \
      if (success) {                         \
      }                                      \
      if (true) {                            \
        act                                  \
      }                                      \
    });                                      \
    DeterministicSchedule::setAuxAct(auxfn); \
  } while (0)

Macro for inline definition of auxiliary actions

Definition at line 238 of file DeterministicScheduleTest.cpp.

Referenced by AnnotatedAtomicCounter< T >::inc(), and AnnotatedAtomicCounter< T >::incBug().

#define AUX_THR

(

x

)

(aux_->t_[tid_].x)

Aux macros

Definition at line 234 of file DeterministicScheduleTest.cpp.

Referenced by AnnotatedAtomicCounter< T >::doAuxLog(), AnnotatedAtomicCounter< T >::inc(), and AnnotatedAtomicCounter< T >::incBug().

#define AUX_UPDATE

(

)

(aux_->lastUpdate_ = aux_->step_ + 1)

Definition at line 235 of file DeterministicScheduleTest.cpp.

Typedef Documentation

using Annotated = AnnotatedAtomicCounter<int>

Definition at line 337 of file DeterministicScheduleTest.cpp.

template<typename T >

using Base = AtomicCounter<T, DeterministicAtomic>

Alias for original class

Examples:

/facebook/proxygen/proxygen/folly/folly/container/Iterator.h.

Definition at line 254 of file DeterministicScheduleTest.cpp.

using DSched = DeterministicSchedule

Definition at line 166 of file DeterministicScheduleTest.cpp.

Function Documentation

DEFINE_bool	(	bug	,
		false	,
		"Introduce bug"
	)

DEFINE_int32	(	num_threads	,
		1	,
		"Number of producers"
	)

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"
	)

int main	(	int	argc,
		char **	argv
	)

Definition at line 370 of file DeterministicScheduleTest.cpp.

References testing::InitGoogleTest(), and RUN_ALL_TESTS().

                                {
  testing::InitGoogleTest(&argc, argv);
  gflags::ParseCommandLineFlags(&argc, &argv, true);
  return RUN_ALL_TESTS();
}

TEST	(	DeterministicSchedule	,
		uniform
	)

Definition at line 24 of file DeterministicScheduleTest.cpp.

References EXPECT_TRUE, i, and folly::test::DeterministicSchedule::uniform().

                                     {
  auto p = DeterministicSchedule::uniform(0);
  int buckets[10] = {};
  for (int i = 0; i < 100000; ++i) {
    buckets[p(10)]++;
  }
  for (int i = 0; i < 10; ++i) {
    EXPECT_TRUE(buckets[i] > 9000);
  }
}

TEST	(	DeterministicSchedule	,
		uniformSubset
	)

Definition at line 35 of file DeterministicScheduleTest.cpp.

References EXPECT_EQ, EXPECT_TRUE, i, seen, folly::test::DeterministicSchedule::uniformSubset(), and x.

                                           {
  auto ps = DeterministicSchedule::uniformSubset(0, 3, 100);
  int buckets[10] = {};
  std::set<int> seen;
  for (int i = 0; i < 100000; ++i) {
    if (i > 0 && (i % 100) == 0) {
      EXPECT_EQ(seen.size(), 3);
      seen.clear();
    }
    int x = ps(10);
    seen.insert(x);
    EXPECT_TRUE(seen.size() <= 3);
    buckets[x]++;
  }
  for (int i = 0; i < 10; ++i) {
    EXPECT_TRUE(buckets[i] > 9000);
  }
}

TEST	(	DeterministicSchedule	,
		buggyAdd
	)

Definition at line 54 of file DeterministicScheduleTest.cpp.

References EXPECT_EQ, FOLLY_TEST_DSCHED_VLOG, folly::test::DeterministicSchedule::join(), folly::test::DeterministicMutex::lock(), m, folly::pushmi::detail::t, folly::test::DeterministicSchedule::thread(), threads, folly::test::DeterministicMutex::try_lock(), folly::test::DeterministicSchedule::uniform(), and folly::test::DeterministicMutex::unlock().

                                      {
  for (bool bug : {false, true}) {
    DeterministicSchedule sched(DeterministicSchedule::uniform(0));
    if (bug) {
      FOLLY_TEST_DSCHED_VLOG("Test with race condition");
    } else {
      FOLLY_TEST_DSCHED_VLOG("Test without race condition");
    }
    DeterministicMutex m;
    // The use of DeterinisticAtomic is not needed here, but it makes
    // it easier to understand the sequence of events in logs.
    DeterministicAtomic<int> test{0};
    DeterministicAtomic<int> baseline{0};
    int numThreads = 10;
    std::vector<std::thread> threads(numThreads);
    for (int t = 0; t < numThreads; ++t) {
      threads[t] = DeterministicSchedule::thread([&, t] {
        baseline.fetch_add(1);
        // Atomic increment of test protected by mutex m
        do {
          // Some threads use lock() others use try_lock()
          if ((t & 1) == 0) {
            m.lock();
          } else {
            if (!m.try_lock()) {
              continue;
            }
          }
          int newval = test.load() + 1;
          if (bug) {
            // Break the atomicity of the increment operation
            m.unlock();
            m.lock();
          }
          test.store(newval);
          m.unlock();
          break;
        } while (true);
      }); // thread lambda
    } // for t
    for (auto& t : threads) {
      DeterministicSchedule::join(t);
    }
    if (!bug) {
      EXPECT_EQ(test.load(), baseline.load());
    } else {
      if (test.load() == baseline.load()) {
        FOLLY_TEST_DSCHED_VLOG("Didn't catch the bug");
      } else {
        FOLLY_TEST_DSCHED_VLOG("Caught the bug");
      }
    }
  } // for bug
}

TEST	(	DeterministicSchedule	,
		global_invariants
	)

Definition at line 339 of file DeterministicScheduleTest.cpp.

References aux_, AnnotatedAtomicCounter< T >::clearAuxChk(), AnnotatedAtomicCounter< T >::doAuxLog(), EXPECT_EQ, i, AnnotatedAtomicCounter< T >::inc(), AnnotatedAtomicCounter< T >::incBug(), folly::test::DeterministicSchedule::join(), AnnotatedAtomicCounter< T >::loadDirect(), AnnotatedAtomicCounter< T >::setAuxChk(), AuxData::step_, folly::pushmi::detail::t, folly::test::DeterministicSchedule::thread(), threads, tid_, and folly::test::DeterministicSchedule::uniform().

                                               {
  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);
    }
    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_;
  }
}

Variable Documentation

AuxData* aux_

static

Definition at line 218 of file DeterministicScheduleTest.cpp.

Referenced by TEST().

FOLLY_TLS uint32_t tid_

static

Definition at line 219 of file DeterministicScheduleTest.cpp.

Referenced by AnnotatedAtomicCounter< T >::doAuxLog(), folly::TimePoint::reset(), and TEST().