123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256 |
- // Copyright (c) 2011 Helge Bahmann
- // Copyright (c) 2012 Tim Blechmann
- //
- // Distributed under the Boost Software License, Version 1.0.
- // See accompanying file LICENSE_1_0.txt or copy at
- // http://www.boost.org/LICENSE_1_0.txt)
- // Attempt to determine whether the memory ordering/ fence operations
- // work as expected:
- // Let two threads race accessing multiple shared variables and
- // verify that "observable" order of operations matches with the
- // ordering constraints specified.
- //
- // We assume that "memory ordering violation" events are exponentially
- // distributed, with unknown "average time between violations"
- // (which is just the reciprocal of exp distribution parameter lambda).
- // Use a "relaxed ordering" implementation that intentionally exhibits
- // a (hopefully observable) such violation to compute the maximum-likelihood
- // estimate for this time. From this, compute an estimate that covers the
- // unknown value with 0.995 confidence (using chi square quantile).
- //
- // Use this estimate to pick a timeout for the race tests of the
- // atomic implementations such that under the assumed distribution
- // we get 0.995 probability to detect a race (if there is one).
- //
- // Overall this yields 0.995 * 0.995 > 0.99 confidence that the
- // fences work as expected if this test program does not
- // report an error.
- #include <boost/atomic.hpp>
- #include <boost/bind.hpp>
- #include <boost/date_time/posix_time/posix_time_types.hpp>
- #include <boost/thread/thread.hpp>
- #include <boost/thread/thread_time.hpp>
- #include <boost/thread/locks.hpp>
- #include <boost/thread/mutex.hpp>
- #include <boost/thread/condition_variable.hpp>
- #include <boost/thread/barrier.hpp>
- #include <boost/core/lightweight_test.hpp>
- // Two threads perform the following operations:
- //
- // thread # 1 thread # 2
- // store(a, 1) store(b, 1)
- // x = read(b) y = read(a)
- //
- // Under relaxed memory ordering, the case (x, y) == (0, 0) is
- // possible. Under sequential consistency, this case is impossible.
- //
- // This "problem" is reproducible on all platforms, even x86.
- template<boost::memory_order store_order, boost::memory_order load_order>
- class total_store_order_test {
- public:
- total_store_order_test(void);
- void run(boost::posix_time::time_duration & timeout);
- bool detected_conflict(void) const { return detected_conflict_; }
- private:
- void thread1fn(void);
- void thread2fn(void);
- void check_conflict(void);
- boost::atomic<int> a_;
- /* insert a bit of padding to push the two variables into
- different cache lines and increase the likelihood of detecting
- a conflict */
- char pad1_[512];
- boost::atomic<int> b_;
- char pad2_[512];
- boost::barrier barrier_;
- int vrfyb1_, vrfya2_;
- boost::atomic<bool> terminate_threads_;
- boost::atomic<int> termination_consensus_;
- bool detected_conflict_;
- boost::mutex m_;
- boost::condition_variable c_;
- };
- template<boost::memory_order store_order, boost::memory_order load_order>
- total_store_order_test<store_order, load_order>::total_store_order_test(void)
- : a_(0), b_(0), barrier_(2),
- vrfyb1_(0), vrfya2_(0),
- terminate_threads_(false), termination_consensus_(0),
- detected_conflict_(false)
- {
- }
- template<boost::memory_order store_order, boost::memory_order load_order>
- void
- total_store_order_test<store_order, load_order>::run(boost::posix_time::time_duration & timeout)
- {
- boost::system_time start = boost::get_system_time();
- boost::system_time end = start + timeout;
- boost::thread t1(boost::bind(&total_store_order_test::thread1fn, this));
- boost::thread t2(boost::bind(&total_store_order_test::thread2fn, this));
- {
- boost::mutex::scoped_lock guard(m_);
- while (boost::get_system_time() < end && !detected_conflict_)
- c_.timed_wait(guard, end);
- }
- terminate_threads_.store(true, boost::memory_order_relaxed);
- t2.join();
- t1.join();
- boost::posix_time::time_duration duration = boost::get_system_time() - start;
- if (duration < timeout)
- timeout = duration;
- }
- volatile int backoff_dummy;
- template<boost::memory_order store_order, boost::memory_order load_order>
- void
- total_store_order_test<store_order, load_order>::thread1fn(void)
- {
- for (;;) {
- a_.store(1, store_order);
- int b = b_.load(load_order);
- barrier_.wait();
- vrfyb1_ = b;
- barrier_.wait();
- check_conflict();
- /* both threads synchronize via barriers, so either
- both threads must exit here, or they must both do
- another round, otherwise one of them will wait forever */
- if (terminate_threads_.load(boost::memory_order_relaxed)) for (;;) {
- int tmp = termination_consensus_.fetch_or(1, boost::memory_order_relaxed);
- if (tmp == 3)
- return;
- if (tmp & 4)
- break;
- }
- termination_consensus_.fetch_xor(4, boost::memory_order_relaxed);
- unsigned int delay = rand() % 10000;
- a_.store(0, boost::memory_order_relaxed);
- barrier_.wait();
- while(delay--) { backoff_dummy = delay; }
- }
- }
- template<boost::memory_order store_order, boost::memory_order load_order>
- void
- total_store_order_test<store_order, load_order>::thread2fn(void)
- {
- for (;;) {
- b_.store(1, store_order);
- int a = a_.load(load_order);
- barrier_.wait();
- vrfya2_ = a;
- barrier_.wait();
- check_conflict();
- /* both threads synchronize via barriers, so either
- both threads must exit here, or they must both do
- another round, otherwise one of them will wait forever */
- if (terminate_threads_.load(boost::memory_order_relaxed)) for (;;) {
- int tmp = termination_consensus_.fetch_or(2, boost::memory_order_relaxed);
- if (tmp == 3)
- return;
- if (tmp & 4)
- break;
- }
- termination_consensus_.fetch_xor(4, boost::memory_order_relaxed);
- unsigned int delay = rand() % 10000;
- b_.store(0, boost::memory_order_relaxed);
- barrier_.wait();
- while(delay--) { backoff_dummy = delay; }
- }
- }
- template<boost::memory_order store_order, boost::memory_order load_order>
- void
- total_store_order_test<store_order, load_order>::check_conflict(void)
- {
- if (vrfyb1_ == 0 && vrfya2_ == 0) {
- boost::mutex::scoped_lock guard(m_);
- detected_conflict_ = true;
- terminate_threads_.store(true, boost::memory_order_relaxed);
- c_.notify_all();
- }
- }
- void
- test_seq_cst(void)
- {
- double sum = 0.0;
- /* take 10 samples */
- for (size_t n = 0; n < 10; n++) {
- boost::posix_time::time_duration timeout(0, 0, 10);
- total_store_order_test<boost::memory_order_relaxed, boost::memory_order_relaxed> test;
- test.run(timeout);
- if (!test.detected_conflict()) {
- std::cout << "Failed to detect order=seq_cst violation while ith order=relaxed -- intrinsic ordering too strong for this test\n";
- return;
- }
- std::cout << "seq_cst violation with order=relaxed after " << timeout.total_microseconds() << " us\n";
- sum = sum + timeout.total_microseconds();
- }
- /* determine maximum likelihood estimate for average time between
- race observations */
- double avg_race_time_mle = (sum / 10);
- /* pick 0.995 confidence (7.44 = chi square 0.995 confidence) */
- double avg_race_time_995 = avg_race_time_mle * 2 * 10 / 7.44;
- /* 5.298 = 0.995 quantile of exponential distribution */
- boost::posix_time::time_duration timeout = boost::posix_time::microseconds((long)(5.298 * avg_race_time_995));
- std::cout << "run seq_cst for " << timeout.total_microseconds() << " us\n";
- total_store_order_test<boost::memory_order_seq_cst, boost::memory_order_seq_cst> test;
- test.run(timeout);
- BOOST_TEST(!test.detected_conflict()); // sequential consistency error
- }
- int main(int, char *[])
- {
- test_seq_cst();
- return boost::report_errors();
- }
|