ceph/src/boost/libs/atomic/test/atomicity.cpp

   1 //  Copyright (c) 2011 Helge Bahmann
   2 //
   3 //  Distributed under the Boost Software License, Version 1.0.
   4 //  See accompanying file LICENSE_1_0.txt or copy at
   5 //  http://www.boost.org/LICENSE_1_0.txt)
   6
   7 // Attempt to determine whether the operations on atomic variables
   8 // do in fact behave atomically: Let multiple threads race modifying
   9 // a shared atomic variable and verify that it behaves as expected.
  10 //
  11 // We assume that "observable race condition" events are exponentially
  12 // distributed, with unknown "average time between observable races"
  13 // (which is just the reciprocal of exp distribution parameter lambda).
  14 // Use a non-atomic implementation that intentionally exhibits a
  15 // (hopefully tight) race to compute the maximum-likelihood estimate
  16 // for this time. From this, compute an estimate that covers the
  17 // unknown value with 0.995 confidence (using chi square quantile).
  18 //
  19 // Use this estimate to pick a timeout for the race tests of the
  20 // atomic implementations such that under the assumed distribution
  21 // we get 0.995 probability to detect a race (if there is one).
  22 //
  23 // Overall this yields 0.995 * 0.995 > 0.99 confidence that the
  24 // operations truly behave atomic if this test program does not
  25 // report an error.
  26
  27 #include <boost/atomic.hpp>
  28
  29 #include <algorithm>
  30 #include <boost/ref.hpp>
  31 #include <boost/bind.hpp>
  32 #include <boost/function.hpp>
  33 #include <boost/date_time/posix_time/posix_time_types.hpp>
  34 #include <boost/date_time/posix_time/time_formatters.hpp>
  35 #include <boost/thread/thread.hpp>
  36 #include <boost/thread/thread_time.hpp>
  37 #include <boost/thread/locks.hpp>
  38 #include <boost/thread/mutex.hpp>
  39 #include <boost/thread/condition_variable.hpp>
  40 #include <boost/core/lightweight_test.hpp>
  41
  42 /* helper class to let two instances of a function race against each
  43 other, with configurable timeout and early abort on detection of error */
  44 class concurrent_runner {
  45 public:
  46     /* concurrently run the function in two threads, until either timeout
  47     or one of the functions returns "false"; returns true if timeout
  48     was reached, or false if early abort and updates timeout accordingly */
  49     static bool
  50     execute(
  51         const boost::function<bool(size_t)> & fn,
  52         boost::posix_time::time_duration & timeout)
  53     {
  54         concurrent_runner runner(fn);
  55         runner.wait_finish(timeout);
  56         return !runner.failure();
  57     }
  58
  59
  60     concurrent_runner(
  61         const boost::function<bool(size_t)> & fn)
  62         : finished_(false), failure_(false)
  63     {
  64         boost::thread(boost::bind(&concurrent_runner::thread_function, this, fn, 0)).swap(first_thread_);
  65         boost::thread(boost::bind(&concurrent_runner::thread_function, this, fn, 1)).swap(second_thread_);
  66     }
  67
  68     void
  69     wait_finish(boost::posix_time::time_duration & timeout)
  70     {
  71         boost::system_time start = boost::get_system_time();
  72         boost::system_time end = start + timeout;
  73
  74         {
  75             boost::mutex::scoped_lock guard(m_);
  76             while (boost::get_system_time() < end && !finished())
  77                 c_.timed_wait(guard, end);
  78         }
  79
  80         finished_.store(true, boost::memory_order_relaxed);
  81
  82         first_thread_.join();
  83         second_thread_.join();
  84
  85         boost::posix_time::time_duration duration = boost::get_system_time() - start;
  86         if (duration < timeout)
  87             timeout = duration;
  88     }
  89
  90     bool
  91     finished(void) const throw() {
  92         return finished_.load(boost::memory_order_relaxed);
  93     }
  94
  95     bool
  96     failure(void) const throw() {
  97         return failure_;
  98     }
  99 private:
 100     void
 101     thread_function(boost::function<bool(size_t)> function, size_t instance)
 102     {
 103         while (!finished()) {
 104             if (!function(instance)) {
 105                 boost::mutex::scoped_lock guard(m_);
 106                 failure_ = true;
 107                 finished_.store(true, boost::memory_order_relaxed);
 108                 c_.notify_all();
 109                 break;
 110             }
 111         }
 112     }
 113
 114
 115     boost::mutex m_;
 116     boost::condition_variable c_;
 117
 118     boost::atomic<bool> finished_;
 119     bool failure_;
 120
 121     boost::thread first_thread_;
 122     boost::thread second_thread_;
 123 };
 124
 125 bool
 126 racy_add(volatile unsigned int & value, size_t instance)
 127 {
 128     size_t shift = instance * 8;
 129     unsigned int mask = 0xff << shift;
 130     for (size_t n = 0; n < 255; n++) {
 131         unsigned int tmp = value;
 132         value = tmp + (1 << shift);
 133
 134         if ((tmp & mask) != (n << shift))
 135             return false;
 136     }
 137
 138     unsigned int tmp = value;
 139     value = tmp & ~mask;
 140     if ((tmp & mask) != mask)
 141         return false;
 142
 143     return true;
 144 }
 145
 146 /* compute estimate for average time between races being observable, in usecs */
 147 static double
 148 estimate_avg_race_time(void)
 149 {
 150     double sum = 0.0;
 151
 152     /* take 10 samples */
 153     for (size_t n = 0; n < 10; n++) {
 154         boost::posix_time::time_duration timeout(0, 0, 10);
 155
 156         volatile unsigned int value(0);
 157         bool success = concurrent_runner::execute(
 158             boost::bind(racy_add, boost::ref(value), _1),
 159             timeout
 160         );
 161
 162         if (success) {
 163             BOOST_ERROR("Failed to establish baseline time for reproducing race condition");
 164         }
 165
 166         sum = sum + timeout.total_microseconds();
 167     }
 168
 169     /* determine maximum likelihood estimate for average time between
 170     race observations */
 171     double avg_race_time_mle = (sum / 10);
 172
 173     /* pick 0.995 confidence (7.44 = chi square 0.995 confidence) */
 174     double avg_race_time_995 = avg_race_time_mle * 2 * 10 / 7.44;
 175
 176     return avg_race_time_995;
 177 }
 178
 179 template<typename value_type, size_t shift_>
 180 bool
 181 test_arithmetic(boost::atomic<value_type> & shared_value, size_t instance)
 182 {
 183     size_t shift = instance * 8;
 184     value_type mask = 0xff << shift;
 185     value_type increment = 1 << shift;
 186
 187     value_type expected = 0;
 188
 189     for (size_t n = 0; n < 255; n++) {
 190         value_type tmp = shared_value.fetch_add(increment, boost::memory_order_relaxed);
 191         if ( (tmp & mask) != (expected << shift) )
 192             return false;
 193         expected ++;
 194     }
 195     for (size_t n = 0; n < 255; n++) {
 196         value_type tmp = shared_value.fetch_sub(increment, boost::memory_order_relaxed);
 197         if ( (tmp & mask) != (expected << shift) )
 198             return false;
 199         expected --;
 200     }
 201
 202     return true;
 203 }
 204
 205 template<typename value_type, size_t shift_>
 206 bool
 207 test_bitops(boost::atomic<value_type> & shared_value, size_t instance)
 208 {
 209     size_t shift = instance * 8;
 210     value_type mask = 0xff << shift;
 211
 212     value_type expected = 0;
 213
 214     for (size_t k = 0; k < 8; k++) {
 215         value_type mod = 1 << k;
 216         value_type tmp = shared_value.fetch_or(mod << shift, boost::memory_order_relaxed);
 217         if ( (tmp & mask) != (expected << shift))
 218             return false;
 219         expected = expected | mod;
 220     }
 221     for (size_t k = 0; k < 8; k++) {
 222         value_type tmp = shared_value.fetch_and( ~ (1 << (shift + k)), boost::memory_order_relaxed);
 223         if ( (tmp & mask) != (expected << shift))
 224             return false;
 225         expected = expected & ~(1<<k);
 226     }
 227     for (size_t k = 0; k < 8; k++) {
 228         value_type mod = 255 ^ (1 << k);
 229         value_type tmp = shared_value.fetch_xor(mod << shift, boost::memory_order_relaxed);
 230         if ( (tmp & mask) != (expected << shift))
 231             return false;
 232         expected = expected ^ mod;
 233     }
 234
 235     value_type tmp = shared_value.fetch_and( ~mask, boost::memory_order_relaxed);
 236     if ( (tmp & mask) != (expected << shift) )
 237         return false;
 238
 239     return true;
 240 }
 241
 242 int main(int, char *[])
 243 {
 244     boost::posix_time::time_duration reciprocal_lambda;
 245
 246     double avg_race_time = estimate_avg_race_time();
 247
 248     /* 5.298 = 0.995 quantile of exponential distribution */
 249     const boost::posix_time::time_duration timeout = boost::posix_time::microseconds((long)(5.298 * avg_race_time));
 250
 251     {
 252         boost::atomic<unsigned int> value(0);
 253
 254         /* testing two different operations in this loop, therefore
 255         enlarge timeout */
 256         boost::posix_time::time_duration tmp(timeout * 2);
 257
 258         bool success = concurrent_runner::execute(
 259             boost::bind(test_arithmetic<unsigned int, 0>, boost::ref(value), _1),
 260             tmp
 261         );
 262
 263         BOOST_TEST(success); // concurrent arithmetic error
 264     }
 265
 266     {
 267         boost::atomic<unsigned int> value(0);
 268
 269         /* testing three different operations in this loop, therefore
 270         enlarge timeout */
 271         boost::posix_time::time_duration tmp(timeout * 3);
 272
 273         bool success = concurrent_runner::execute(
 274             boost::bind(test_bitops<unsigned int, 0>, boost::ref(value), _1),
 275             tmp
 276         );
 277
 278         BOOST_TEST(success); // concurrent bit operations error
 279     }
 280
 281     return boost::report_errors();
 282 }