| // Copyright (c) 2011 Helge Bahmann |
| // |
| // 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 operations on atomic variables |
| // do in fact behave atomically: Let multiple threads race modifying |
| // a shared atomic variable and verify that it behaves as expected. |
| // |
| // We assume that "observable race condition" events are exponentially |
| // distributed, with unknown "average time between observable races" |
| // (which is just the reciprocal of exp distribution parameter lambda). |
| // Use a non-atomic implementation that intentionally exhibits a |
| // (hopefully tight) race 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 |
| // operations truly behave atomic if this test program does not |
| // report an error. |
| |
| #include <boost/atomic.hpp> |
| |
| #include <algorithm> |
| #include <boost/ref.hpp> |
| #include <boost/bind.hpp> |
| #include <boost/function.hpp> |
| #include <boost/date_time/posix_time/posix_time_types.hpp> |
| #include <boost/date_time/posix_time/time_formatters.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/core/lightweight_test.hpp> |
| |
| #define BOOST_WARN_MESSAGE(msg) warning_message_impl((msg), __FILE__, __LINE__) |
| |
| template <typename StringT> |
| void warning_message_impl(StringT msg, const char *file, int line) |
| { |
| BOOST_LIGHTWEIGHT_TEST_OSTREAM |
| << "Warning: " << (msg) << " " << (file) << ":" << line |
| << std::endl; |
| } |
| |
| /* helper class to let two instances of a function race against each |
| other, with configurable timeout and early abort on detection of error */ |
| class concurrent_runner { |
| public: |
| /* concurrently run the function in two threads, until either timeout |
| or one of the functions returns "false"; returns true if timeout |
| was reached, or false if early abort and updates timeout accordingly */ |
| static bool |
| execute( |
| const boost::function<bool(size_t)> & fn, |
| boost::posix_time::time_duration & timeout) |
| { |
| concurrent_runner runner(fn); |
| runner.wait_finish(timeout); |
| return !runner.failure(); |
| } |
| |
| |
| concurrent_runner( |
| const boost::function<bool(size_t)> & fn) |
| : finished_(false), failure_(false), |
| first_thread_(boost::bind(&concurrent_runner::thread_function, this, fn, 0)), |
| second_thread_(boost::bind(&concurrent_runner::thread_function, this, fn, 1)) |
| { |
| } |
| |
| void |
| wait_finish(boost::posix_time::time_duration & timeout) |
| { |
| boost::system_time start = boost::get_system_time(); |
| boost::system_time end = start + timeout; |
| |
| { |
| boost::mutex::scoped_lock guard(m_); |
| while (boost::get_system_time() < end && !finished()) |
| c_.timed_wait(guard, end); |
| } |
| |
| finished_.store(true, boost::memory_order_relaxed); |
| |
| first_thread_.join(); |
| second_thread_.join(); |
| |
| boost::posix_time::time_duration duration = boost::get_system_time() - start; |
| if (duration < timeout) |
| timeout = duration; |
| } |
| |
| bool |
| finished(void) const throw() { |
| return finished_.load(boost::memory_order_relaxed); |
| } |
| |
| bool |
| failure(void) const throw() { |
| return failure_; |
| } |
| private: |
| void |
| thread_function(boost::function<bool(size_t)> function, size_t instance) |
| { |
| while (!finished()) { |
| if (!function(instance)) { |
| boost::mutex::scoped_lock guard(m_); |
| failure_ = true; |
| finished_.store(true, boost::memory_order_relaxed); |
| c_.notify_all(); |
| break; |
| } |
| } |
| } |
| |
| |
| boost::mutex m_; |
| boost::condition_variable c_; |
| |
| boost::atomic<bool> finished_; |
| bool failure_; |
| |
| boost::thread first_thread_; |
| boost::thread second_thread_; |
| }; |
| |
| bool |
| racy_add(volatile unsigned int & value, size_t instance) |
| { |
| size_t shift = instance * 8; |
| unsigned int mask = 0xff << shift; |
| for (size_t n = 0; n < 255; n++) { |
| unsigned int tmp = value; |
| value = tmp + (1 << shift); |
| |
| if ((tmp & mask) != (n << shift)) |
| return false; |
| } |
| |
| unsigned int tmp = value; |
| value = tmp & ~mask; |
| if ((tmp & mask) != mask) |
| return false; |
| |
| return true; |
| } |
| |
| /* compute estimate for average time between races being observable, in usecs */ |
| static double |
| estimate_avg_race_time(void) |
| { |
| double sum = 0.0; |
| unsigned failures = 0; |
| |
| /* take 10 samples */ |
| for (size_t n = 0; n < 10; n++) { |
| boost::posix_time::time_duration timeout(0, 0, 10); |
| |
| volatile unsigned int value(0); |
| bool success = concurrent_runner::execute( |
| boost::bind(racy_add, boost::ref(value), _1), |
| timeout |
| ); |
| |
| if (success) { |
| ++failures; |
| if ((failures > 3) && (n < 4)) { |
| BOOST_WARN_MESSAGE("Failed to establish baseline time 3 times, giving up"); |
| sum = 3 * 1000000; |
| break; |
| } else { |
| BOOST_WARN_MESSAGE("Failed to establish baseline time for reproducing race condition"); |
| } |
| } |
| |
| 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; |
| |
| return avg_race_time_995; |
| } |
| |
| template<typename value_type, size_t shift_> |
| bool |
| test_arithmetic(boost::atomic<value_type> & shared_value, size_t instance) |
| { |
| size_t shift = instance * 8; |
| value_type mask = 0xff << shift; |
| value_type increment = 1 << shift; |
| |
| value_type expected = 0; |
| |
| for (size_t n = 0; n < 255; n++) { |
| value_type tmp = shared_value.fetch_add(increment, boost::memory_order_relaxed); |
| if ( (tmp & mask) != (expected << shift) ) |
| return false; |
| expected ++; |
| } |
| for (size_t n = 0; n < 255; n++) { |
| value_type tmp = shared_value.fetch_sub(increment, boost::memory_order_relaxed); |
| if ( (tmp & mask) != (expected << shift) ) |
| return false; |
| expected --; |
| } |
| |
| return true; |
| } |
| |
| template<typename value_type, size_t shift_> |
| bool |
| test_bitops(boost::atomic<value_type> & shared_value, size_t instance) |
| { |
| size_t shift = instance * 8; |
| value_type mask = 0xff << shift; |
| |
| value_type expected = 0; |
| |
| for (size_t k = 0; k < 8; k++) { |
| value_type mod = 1 << k; |
| value_type tmp = shared_value.fetch_or(mod << shift, boost::memory_order_relaxed); |
| if ( (tmp & mask) != (expected << shift)) |
| return false; |
| expected = expected | mod; |
| } |
| for (size_t k = 0; k < 8; k++) { |
| value_type tmp = shared_value.fetch_and( ~ (1 << (shift + k)), boost::memory_order_relaxed); |
| if ( (tmp & mask) != (expected << shift)) |
| return false; |
| expected = expected & ~(1<<k); |
| } |
| for (size_t k = 0; k < 8; k++) { |
| value_type mod = 255 ^ (1 << k); |
| value_type tmp = shared_value.fetch_xor(mod << shift, boost::memory_order_relaxed); |
| if ( (tmp & mask) != (expected << shift)) |
| return false; |
| expected = expected ^ mod; |
| } |
| |
| value_type tmp = shared_value.fetch_and( ~mask, boost::memory_order_relaxed); |
| if ( (tmp & mask) != (expected << shift) ) |
| return false; |
| |
| return true; |
| } |
| |
| int main(int, char *[]) |
| { |
| boost::posix_time::time_duration reciprocal_lambda; |
| |
| double avg_race_time = estimate_avg_race_time(); |
| |
| /* 5.298 = 0.995 quantile of exponential distribution */ |
| const boost::posix_time::time_duration timeout = boost::posix_time::microseconds((long)(5.298 * avg_race_time)); |
| |
| { |
| boost::atomic<unsigned int> value(0); |
| |
| /* testing two different operations in this loop, therefore |
| enlarge timeout */ |
| boost::posix_time::time_duration tmp(timeout * 2); |
| |
| bool success = concurrent_runner::execute( |
| boost::bind(test_arithmetic<unsigned int, 0>, boost::ref(value), _1), |
| tmp |
| ); |
| |
| BOOST_TEST(success); // concurrent arithmetic error |
| } |
| |
| { |
| boost::atomic<unsigned int> value(0); |
| |
| /* testing three different operations in this loop, therefore |
| enlarge timeout */ |
| boost::posix_time::time_duration tmp(timeout * 3); |
| |
| bool success = concurrent_runner::execute( |
| boost::bind(test_bitops<unsigned int, 0>, boost::ref(value), _1), |
| tmp |
| ); |
| |
| BOOST_TEST(success); // concurrent bit operations error |
| } |
| |
| return boost::report_errors(); |
| } |