proxygen: folly::test::DeterministicSchedule Class Reference

#include <DeterministicSchedule.h>

Inheritance diagram for folly::test::DeterministicSchedule:

Public Member Functions
	DeterministicSchedule (const std::function< size_t(size_t)> &scheduler)

	~DeterministicSchedule ()

Static Public Member Functions
static std::function< size_t(size_t)>	uniform (uint64_t seed)

static std::function< size_t(size_t)>	uniformSubset (uint64_t seed, size_t n=2, size_t m=64)

static void	beforeSharedAccess ()

static void	afterSharedAccess ()

static void	afterSharedAccess (bool success)

template<typename Func , typename... Args>
static std::thread	thread (Func &&func, Args &&...args)

static void	join (std::thread &child)

static void	post (sem_t *sem)

static bool	tryWait (sem_t *sem)

static void	wait (sem_t *sem)

static size_t	getRandNumber (size_t n)

static int	getcpu (unsigned cpu, unsigned node, void *unused)

static void	setAuxAct (AuxAct &aux)

static void	setAuxChk (AuxChk &aux)

static void	clearAuxChk ()

static sem_t *	descheduleCurrentThread ()

static void	reschedule (sem_t *sem)

Private Member Functions
sem_t *	beforeThreadCreate ()

void	afterThreadCreate (sem_t *)

void	beforeThreadExit ()

void	callAux (bool)

Private Attributes
std::function< size_t(size_t)>	scheduler_

std::vector< sem_t * >	sems_

std::unordered_set< std::thread::id >	active_

std::unordered_map< std::thread::id, sem_t * >	joins_

unsigned	nextThreadId_

uint64_t	step_

Static Private Attributes
static FOLLY_TLS sem_t *	tls_sem

static FOLLY_TLS DeterministicSchedule *	tls_sched

static FOLLY_TLS unsigned	tls_threadId

static thread_local AuxAct	tls_aux_act

static AuxChk	aux_chk

Detailed Description

DeterministicSchedule coordinates the inter-thread communication of a set of threads under test, so that despite concurrency the execution is the same every time. It works by stashing a reference to the schedule in a thread-local variable, then blocking all but one thread at a time.

In order for DeterministicSchedule to work, it needs to intercept all inter-thread communication. To do this you should use DeterministicAtomic<T> instead of std::atomic<T>, create threads using DeterministicSchedule::thread() instead of the std::thread constructor, DeterministicSchedule::join(thr) instead of thr.join(), and access semaphores via the helper functions in DeterministicSchedule. Locks are not yet supported, although they would be easy to add with the same strategy as the mapping of sem_wait.

The actual schedule is defined by a function from n -> [0,n). At each step, the function will be given the number of active threads (n), and it returns the index of the thread that should be run next. Invocations of the scheduler function will be serialized, but will occur from multiple threads. A good starting schedule is uniform(0).

Definition at line 75 of file DeterministicSchedule.h.

Constructor & Destructor Documentation

folly::test::DeterministicSchedule::DeterministicSchedule ( const std::function< size_t(size_t)> & scheduler )

explicit

Arranges for the current thread (and all threads created by DeterministicSchedule::thread on a thread participating in this schedule) to participate in a deterministic schedule.

Definition at line 47 of file DeterministicSchedule.cpp.

References sems_, tls_aux_act, tls_sched, and tls_sem.

     : scheduler_(scheduler), nextThreadId_(1), step_(0) {
   assert(tls_sem == nullptr);
   assert(tls_sched == nullptr);
   assert(tls_aux_act == nullptr);
 
   tls_sem = new sem_t;
   sem_init(tls_sem, 0, 1);
   sems_.push_back(tls_sem);
 
   tls_sched = this;
 }

folly::test::DeterministicSchedule::~DeterministicSchedule ( )

Completes the schedule.

Definition at line 61 of file DeterministicSchedule.cpp.

References beforeThreadExit(), sems_, tls_sched, and tls_sem.

                                               {
   assert(tls_sched == this);
   assert(sems_.size() == 1);
   assert(sems_[0] == tls_sem);
   beforeThreadExit();
 }

Member Function Documentation

void folly::test::DeterministicSchedule::afterSharedAccess ( )

static

Releases permission for the current thread to perform inter-thread communication.

Definition at line 137 of file DeterministicSchedule.cpp.

References tls_sched.

Referenced by afterThreadCreate(), beforeThreadCreate(), beforeThreadExit(), folly::test::futexWaitImpl(), folly::test::futexWakeImpl(), getcpu(), join(), folly::test::DeterministicMutex::lock(), post(), folly::test::DeterministicMutex::try_lock(), tryWait(), and folly::test::DeterministicMutex::unlock().

                                               {
   auto sched = tls_sched;
   if (!sched) {
     return;
   }
   sem_post(sched->sems_[sched->scheduler_(sched->sems_.size())]);
 }

void folly::test::DeterministicSchedule::afterSharedAccess ( bool success )

static

Calls a user-defined auxiliary function if any, and releases permission for the current thread to perform inter-thread communication. The bool parameter indicates the success of the shared access (if conditional, true otherwise).

Definition at line 145 of file DeterministicSchedule.cpp.

References callAux(), and tls_sched.

                                                           {
   auto sched = tls_sched;
   if (!sched) {
     return;
   }
   sched->callAux(success);
   sem_post(sched->sems_[sched->scheduler_(sched->sems_.size())]);
 }

void folly::test::DeterministicSchedule::afterThreadCreate ( sem_t * sem )

private

Definition at line 216 of file DeterministicSchedule.cpp.

References active_, afterSharedAccess(), beforeSharedAccess(), tls_sched, and tls_sem.

                                                         {
   assert(tls_sem == nullptr);
   assert(tls_sched == nullptr);
   tls_sem = sem;
   tls_sched = this;
   bool started = false;
   while (!started) {
     beforeSharedAccess();
     if (active_.count(std::this_thread::get_id()) == 1) {
       started = true;
     }
     afterSharedAccess();
   }
 }

void folly::test::DeterministicSchedule::beforeSharedAccess ( )

static

Obtains permission for the current thread to perform inter-thread communication.

Definition at line 131 of file DeterministicSchedule.cpp.

References tls_sem.

                                                {
   if (tls_sem) {
     sem_wait(tls_sem);
   }
 }

sem_t * folly::test::DeterministicSchedule::beforeThreadCreate ( )

private

Definition at line 207 of file DeterministicSchedule.cpp.

References afterSharedAccess(), beforeSharedAccess(), s, and sems_.

Referenced by thread().

                                                  {
   sem_t* s = new sem_t;
   sem_init(s, 0, 0);
   beforeSharedAccess();
   sems_.push_back(s);
   afterSharedAccess();
   return s;
 }

void folly::test::DeterministicSchedule::beforeThreadExit ( )

private

Definition at line 231 of file DeterministicSchedule.cpp.

References active_, afterSharedAccess(), beforeSharedAccess(), FOLLY_TEST_DSCHED_VLOG, joins_, parent, reschedule(), sems_, tls_aux_act, tls_sched, and tls_sem.

Referenced by ~DeterministicSchedule().

                                              {
   assert(tls_sched == this);
   beforeSharedAccess();
   auto parent = joins_.find(std::this_thread::get_id());
   if (parent != joins_.end()) {
     reschedule(parent->second);
     joins_.erase(parent);
   }
   sems_.erase(std::find(sems_.begin(), sems_.end(), tls_sem));
   active_.erase(std::this_thread::get_id());
   if (sems_.size() > 0) {
     FOLLY_TEST_DSCHED_VLOG("exiting");
     afterSharedAccess();
   }
   sem_destroy(tls_sem);
   delete tls_sem;
   tls_sem = nullptr;
   tls_sched = nullptr;
   tls_aux_act = nullptr;
 }

void folly::test::DeterministicSchedule::callAux ( bool success )

private

Calls user-defined auxiliary function (if any)

Definition at line 271 of file DeterministicSchedule.cpp.

References aux_chk, step_, and tls_aux_act.

Referenced by afterSharedAccess().

                                                 {
   ++step_;
   if (tls_aux_act) {
     tls_aux_act(success);
     tls_aux_act = nullptr;
   }
   if (aux_chk) {
     aux_chk(step_);
   }
 }

void folly::test::DeterministicSchedule::clearAuxChk ( )

static

Clears the function set by setAuxChk

Definition at line 187 of file DeterministicSchedule.cpp.

References aux_chk.

Referenced by AnnotatedAtomicCounter< T >::clearAuxChk().

                                         {
   aux_chk = nullptr;
 }

sem_t * folly::test::DeterministicSchedule::descheduleCurrentThread ( )

static

Remove the current thread's semaphore from sems_

Definition at line 198 of file DeterministicSchedule.cpp.

References sems_, tls_sched, and tls_sem.

Referenced by join(), and folly::test::DeterministicMutex::lock().

                                                       {
   auto sched = tls_sched;
   if (sched) {
     sched->sems_.erase(
         std::find(sched->sems_.begin(), sched->sems_.end(), tls_sem));
   }
   return tls_sem;
 }

int folly::test::DeterministicSchedule::getcpu	(	unsigned *	cpu,
		unsigned *	node,
		void *	unused
	)

static

Deterministic implemencation of getcpu

Definition at line 161 of file DeterministicSchedule.cpp.

References afterSharedAccess(), beforeSharedAccess(), nextThreadId_, tls_sched, and tls_threadId.

Referenced by folly::AccessSpreader< Atom >::pickGetcpuFunc().

              {
   if (!tls_threadId && tls_sched) {
     beforeSharedAccess();
     tls_threadId = tls_sched->nextThreadId_++;
     afterSharedAccess();
   }
   if (cpu) {
     *cpu = tls_threadId;
   }
   if (node) {
     *node = tls_threadId;
   }
   return 0;
 }

size_t folly::test::DeterministicSchedule::getRandNumber ( size_t n )

static

Used scheduler_ to get a random number b/w [0, n). If tls_sched is not set-up it falls back to std::rand()

Definition at line 154 of file DeterministicSchedule.cpp.

References folly::Random::rand32(), scheduler_, and tls_sched.

Referenced by folly::test::futexWaitImpl().

                                                     {
   if (tls_sched) {
     return tls_sched->scheduler_(n);
   }
   return Random::rand32() % n;
 }

void folly::test::DeterministicSchedule::join ( std::thread & child )

static

Calls child.join() as part of a deterministic schedule.

Definition at line 252 of file DeterministicSchedule.cpp.

References afterSharedAccess(), beforeSharedAccess(), descheduleCurrentThread(), FOLLY_TEST_DSCHED_VLOG, and tls_sched.

Referenced by folly::test::atomic_notify_one(), cleanup_test(), DSchedMixedTest(), lifo_test(), liveClockWaitUntilTests(), mt_linked_test(), priv_dtor_test(), producerConsumerBench(), run_basic_tests(), run_mt_sequencer_test(), run_multi_poster_multi_waiter_test(), folly::test::run_pingpong_test(), run_pingpong_test(), folly::test::run_timed_wait_regular_test(), folly::test::run_timed_wait_tmo_tests(), run_wake_blocked_test(), runAllAndValidate(), runContendedReaders(), runMixed(), runNeverFailTest(), runPingPong(), runRemoteUnlock(), runTryEnqDeqTest(), swmr_test(), TEST(), folly::TEST(), and TEST_F().

                                                  {
   auto sched = tls_sched;
   if (sched) {
     beforeSharedAccess();
     assert(sched->joins_.count(child.get_id()) == 0);
     if (sched->active_.count(child.get_id())) {
       sem_t* sem = descheduleCurrentThread();
       sched->joins_.insert({child.get_id(), sem});
       afterSharedAccess();
       // Wait to be scheduled by exiting child thread
       beforeSharedAccess();
       assert(!sched->active_.count(child.get_id()));
     }
     afterSharedAccess();
   }
   FOLLY_TEST_DSCHED_VLOG("joined " << std::hex << child.get_id());
   child.join();
 }

void folly::test::DeterministicSchedule::post ( sem_t * sem )

static

Calls sem_post(sem) as part of a deterministic schedule.

Definition at line 282 of file DeterministicSchedule.cpp.

References afterSharedAccess(), beforeSharedAccess(), and FOLLY_TEST_DSCHED_VLOG.

                                            {
   beforeSharedAccess();
   sem_post(sem);
   FOLLY_TEST_DSCHED_VLOG("sem_post(" << sem << ")");
   afterSharedAccess();
 }

void folly::test::DeterministicSchedule::reschedule ( sem_t * sem )

static

Add sem back into sems_

Definition at line 191 of file DeterministicSchedule.cpp.

References sems_, and tls_sched.

Referenced by beforeThreadExit(), and folly::test::DeterministicMutex::unlock().

                                                  {
   auto sched = tls_sched;
   if (sched) {
     sched->sems_.push_back(sem);
   }
 }

void folly::test::DeterministicSchedule::setAuxAct ( AuxAct & aux )

static

Sets up a thread-specific function for call immediately after the next shared access by the thread for managing auxiliary data. The function takes a bool parameter that indicates the success of the shared access (if it is conditional, true otherwise). The function is cleared after one use.

Definition at line 179 of file DeterministicSchedule.cpp.

References tls_aux_act.

                                                  {
   tls_aux_act = aux;
 }

void folly::test::DeterministicSchedule::setAuxChk ( AuxChk & aux )

static

Sets up a function to be called after every subsequent shared access (until clearAuxChk() is called) for checking global invariants and logging. The function takes a uint64_t parameter that indicates the number of shared accesses so far.

Definition at line 183 of file DeterministicSchedule.cpp.

References aux_chk.

Referenced by AnnotatedAtomicCounter< T >::setAuxChk().

                                                  {
   aux_chk = aux;
 }

template<typename Func , typename... Args>

static std::thread folly::test::DeterministicSchedule::thread	(	Func &&	func,
		Args &&...	args
	)

inlinestatic

Launches a thread that will participate in the same deterministic schedule as the current thread.

Definition at line 123 of file DeterministicSchedule.h.

References a, testing::Args(), beforeThreadCreate(), child, SCOPE_EXIT, and tls_sched.

                                                               {
     // TODO: maybe future versions of gcc will allow forwarding to thread
     auto sched = tls_sched;
     auto sem = sched ? sched->beforeThreadCreate() : nullptr;
     auto child = std::thread(
         [=](Args... a) {
           if (sched) {
             sched->afterThreadCreate(sem);
             beforeSharedAccess();
             FOLLY_TEST_DSCHED_VLOG("running");
             afterSharedAccess();
           }
           SCOPE_EXIT {
             if (sched) {
               sched->beforeThreadExit();
             }
           };
           func(a...);
         },
         args...);
     if (sched) {
       beforeSharedAccess();
       sched->active_.insert(child.get_id());
       FOLLY_TEST_DSCHED_VLOG("forked " << std::hex << child.get_id());
       afterSharedAccess();
     }
     return child;
   }

bool folly::test::DeterministicSchedule::tryWait ( sem_t * sem )

static

Calls sem_trywait(sem) as part of a deterministic schedule, returning true on success and false on transient failure.

Definition at line 289 of file DeterministicSchedule.cpp.

References afterSharedAccess(), beforeSharedAccess(), and FOLLY_TEST_DSCHED_VLOG.

Referenced by wait().

                                               {
   beforeSharedAccess();
   int rv = sem_trywait(sem);
   int e = rv == 0 ? 0 : errno;
   FOLLY_TEST_DSCHED_VLOG(
       "sem_trywait(" << sem << ") = " << rv << " errno=" << e);
   afterSharedAccess();
   if (rv == 0) {
     return true;
   } else {
     assert(e == EAGAIN);
     return false;
   }
 }

std::function< size_t(size_t)> folly::test::DeterministicSchedule::uniform ( uint64_t seed )

static

Returns a scheduling function that randomly chooses one of the runnable threads at each step, with no history. This implements a schedule that is equivalent to one in which the steps between inter-thread communication are random variables following a poisson distribution.

Definition at line 68 of file DeterministicSchedule.cpp.

References dist, and seed.

Referenced by runMtNeverFailDeterministic(), runMtProdConsDeterministic(), runMtProdConsDeterministicDynamic(), TEST(), folly::TEST(), and TEST_F().

                                                                         {
   auto rand = std::make_shared<std::ranlux48>(seed);
   return [rand](size_t numActive) {
     auto dist = std::uniform_int_distribution<size_t>(0, numActive - 1);
     return dist(*rand);
   };
 }

std::function< size_t(size_t)> folly::test::DeterministicSchedule::uniformSubset	(	uint64_t	seed,
		size_t	n = `2`,
		size_t	m = `64`
	)

static

Returns a scheduling function that chooses a subset of the active threads and randomly chooses a member of the subset as the next runnable thread. The subset is chosen with size n, and the choice is made every m steps.

Definition at line 126 of file DeterministicSchedule.cpp.

References m, and seed.

Referenced by runMtNeverFailDeterministic(), TEST(), and TEST_F().

                                                                       {
   auto gen = std::make_shared<UniformSubset>(seed, n, m);
   return [=](size_t numActive) { return (*gen)(numActive); };
 }

void folly::test::DeterministicSchedule::wait ( sem_t * sem )

static

Calls sem_wait(sem) as part of a deterministic schedule.

Definition at line 304 of file DeterministicSchedule.cpp.

References tryWait().

                                            {
   while (!tryWait(sem)) {
     // we're not busy waiting because this is a deterministic schedule
   }
 }

Member Data Documentation

std::unordered_set<std::thread::id> folly::test::DeterministicSchedule::active_

private

Definition at line 203 of file DeterministicSchedule.h.

Referenced by afterThreadCreate(), and beforeThreadExit().

AuxChk folly::test::DeterministicSchedule::aux_chk

staticprivate

Definition at line 199 of file DeterministicSchedule.h.

Referenced by callAux(), clearAuxChk(), and setAuxChk().

std::unordered_map<std::thread::id, sem_t*> folly::test::DeterministicSchedule::joins_

private

Definition at line 204 of file DeterministicSchedule.h.

Referenced by beforeThreadExit().

unsigned folly::test::DeterministicSchedule::nextThreadId_

private

Definition at line 205 of file DeterministicSchedule.h.

Referenced by getcpu().

std::function<size_t(size_t)> folly::test::DeterministicSchedule::scheduler_

private

Definition at line 201 of file DeterministicSchedule.h.

Referenced by getRandNumber().

std::vector<sem_t*> folly::test::DeterministicSchedule::sems_

private

Definition at line 202 of file DeterministicSchedule.h.

Referenced by beforeThreadCreate(), beforeThreadExit(), descheduleCurrentThread(), DeterministicSchedule(), reschedule(), and ~DeterministicSchedule().

uint64_t folly::test::DeterministicSchedule::step_

private

Definition at line 212 of file DeterministicSchedule.h.

Referenced by callAux().

thread_local AuxAct folly::test::DeterministicSchedule::tls_aux_act

staticprivate

Definition at line 198 of file DeterministicSchedule.h.

Referenced by beforeThreadExit(), callAux(), DeterministicSchedule(), and setAuxAct().

FOLLY_TLS DeterministicSchedule * folly::test::DeterministicSchedule::tls_sched

staticprivate

Definition at line 196 of file DeterministicSchedule.h.

Referenced by afterSharedAccess(), afterThreadCreate(), beforeThreadExit(), descheduleCurrentThread(), DeterministicSchedule(), getcpu(), getRandNumber(), join(), reschedule(), thread(), and ~DeterministicSchedule().

FOLLY_TLS sem_t * folly::test::DeterministicSchedule::tls_sem

staticprivate

Definition at line 195 of file DeterministicSchedule.h.

Referenced by afterThreadCreate(), beforeSharedAccess(), beforeThreadExit(), descheduleCurrentThread(), DeterministicSchedule(), and ~DeterministicSchedule().

FOLLY_TLS unsigned folly::test::DeterministicSchedule::tls_threadId

staticprivate

Definition at line 197 of file DeterministicSchedule.h.

Referenced by getcpu().

The documentation for this class was generated from the following files:

proxygen/folly/folly/test/DeterministicSchedule.h
proxygen/folly/folly/test/DeterministicSchedule.cpp

Public Member Functions

Static Public Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation