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/thread/thread.hpp>
  35 #include <boost/thread/thread_time.hpp>
  36 #include <boost/thread/locks.hpp>
  37 #include <boost/thread/mutex.hpp>
  38 #include <boost/thread/condition_variable.hpp>
  39 #include <boost/core/lightweight_test.hpp>
  40
  41 /* helper class to let two instances of a function race against each
  42 other, with configurable timeout and early abort on detection of error */
  43 class concurrent_runner {
  44 public:
  45     /* concurrently run the function in two threads, until either timeout
  46     or one of the functions returns "false"; returns true if timeout
  47     was reached, or false if early abort and updates timeout accordingly */
  48     static bool
  49     execute(
  50         const boost::function<bool(size_t)> & fn,
  51         boost::posix_time::time_duration & timeout)
  52     {
  53         concurrent_runner runner(fn);
  54         runner.wait_finish(timeout);
  55         return !runner.failure();
  56     }
  57
  58
  59     concurrent_runner(
  60         const boost::function<bool(size_t)> & fn)
  61         : finished_(false), failure_(false)
  62     {
  63         boost::thread(boost::bind(&concurrent_runner::thread_function, this, fn, 0)).swap(first_thread_);
  64         boost::thread(boost::bind(&concurrent_runner::thread_function, this, fn, 1)).swap(second_thread_);
  65     }
  66
  67     void
  68     wait_finish(boost::posix_time::time_duration & timeout)
  69     {
  70         boost::system_time start = boost::get_system_time();
  71         boost::system_time end = start + timeout;
  72
  73         {
  74             boost::mutex::scoped_lock guard(m_);
  75             while (boost::get_system_time() < end && !finished())
  76                 c_.timed_wait(guard, end);
  77         }
  78
  79         finished_.store(true, boost::memory_order_relaxed);
  80
  81         first_thread_.join();
  82         second_thread_.join();
  83
  84         boost::posix_time::time_duration duration = boost::get_system_time() - start;
  85         if (duration < timeout)
  86             timeout = duration;
  87     }
  88
  89     bool
  90     finished(void) const throw() {
  91         return finished_.load(boost::memory_order_relaxed);
  92     }
  93
  94     bool
  95     failure(void) const throw() {
  96         return failure_;
  97     }
  98 private:
  99     void
 100     thread_function(boost::function<bool(size_t)> function, size_t instance)
 101     {
 102         while (!finished()) {
 103             if (!function(instance)) {
 104                 boost::mutex::scoped_lock guard(m_);
 105                 failure_ = true;
 106                 finished_.store(true, boost::memory_order_relaxed);
 107                 c_.notify_all();
 108                 break;
 109             }
 110         }
 111     }
 112
 113
 114     boost::mutex m_;
 115     boost::condition_variable c_;
 116
 117     boost::atomic<bool> finished_;
 118     bool failure_;
 119
 120     boost::thread first_thread_;
 121     boost::thread second_thread_;
 122 };
 123
 124 bool
 125 racy_add(volatile unsigned int & value, size_t instance)
 126 {
 127     size_t shift = instance * 8;
 128     unsigned int mask = 0xff << shift;
 129     for (size_t n = 0; n < 255; n++) {
 130         unsigned int tmp = value;
 131         value = tmp + (1 << shift);
 132
 133         if ((tmp & mask) != (n << shift))
 134             return false;
 135     }
 136
 137     unsigned int tmp = value;
 138     value = tmp & ~mask;
 139     if ((tmp & mask) != mask)
 140         return false;
 141
 142     return true;
 143 }
 144
 145 /* compute estimate for average time between races being observable, in usecs */
 146 static double
 147 estimate_avg_race_time(void)
 148 {
 149     double sum = 0.0;
 150
 151     /* take 10 samples */
 152     for (size_t n = 0; n < 10; n++) {
 153         boost::posix_time::time_duration timeout(0, 0, 10);
 154
 155         volatile unsigned int value(0);
 156         bool success = concurrent_runner::execute(
 157             boost::bind(racy_add, boost::ref(value), _1),
 158             timeout
 159         );
 160
 161         if (success) {
 162             BOOST_ERROR("Failed to establish baseline time for reproducing race condition");
 163         }
 164
 165         sum = sum + timeout.total_microseconds();
 166     }
 167
 168     /* determine maximum likelihood estimate for average time between
 169     race observations */
 170     double avg_race_time_mle = (sum / 10);
 171
 172     /* pick 0.995 confidence (7.44 = chi square 0.995 confidence) */
 173     double avg_race_time_995 = avg_race_time_mle * 2 * 10 / 7.44;
 174
 175     return avg_race_time_995;
 176 }
 177
 178 template<typename value_type, size_t shift_>
 179 bool
 180 test_arithmetic(boost::atomic<value_type> & shared_value, size_t instance)
 181 {
 182     size_t shift = instance * 8;
 183     value_type mask = 0xff << shift;
 184     value_type increment = 1 << shift;
 185
 186     value_type expected = 0;
 187
 188     for (size_t n = 0; n < 255; n++) {
 189         value_type tmp = shared_value.fetch_add(increment, boost::memory_order_relaxed);
 190         if ( (tmp & mask) != (expected << shift) )
 191             return false;
 192         expected ++;
 193     }
 194     for (size_t n = 0; n < 255; n++) {
 195         value_type tmp = shared_value.fetch_sub(increment, boost::memory_order_relaxed);
 196         if ( (tmp & mask) != (expected << shift) )
 197             return false;
 198         expected --;
 199     }
 200
 201     return true;
 202 }
 203
 204 template<typename value_type, size_t shift_>
 205 bool
 206 test_bitops(boost::atomic<value_type> & shared_value, size_t instance)
 207 {
 208     size_t shift = instance * 8;
 209     value_type mask = 0xff << shift;
 210
 211     value_type expected = 0;
 212
 213     for (size_t k = 0; k < 8; k++) {
 214         value_type mod = 1 << k;
 215         value_type tmp = shared_value.fetch_or(mod << shift, boost::memory_order_relaxed);
 216         if ( (tmp & mask) != (expected << shift))
 217             return false;
 218         expected = expected | mod;
 219     }
 220     for (size_t k = 0; k < 8; k++) {
 221         value_type tmp = shared_value.fetch_and( ~ (1 << (shift + k)), boost::memory_order_relaxed);
 222         if ( (tmp & mask) != (expected << shift))
 223             return false;
 224         expected = expected & ~(1<<k);
 225     }
 226     for (size_t k = 0; k < 8; k++) {
 227         value_type mod = 255 ^ (1 << k);
 228         value_type tmp = shared_value.fetch_xor(mod << shift, boost::memory_order_relaxed);
 229         if ( (tmp & mask) != (expected << shift))
 230             return false;
 231         expected = expected ^ mod;
 232     }
 233
 234     value_type tmp = shared_value.fetch_and( ~mask, boost::memory_order_relaxed);
 235     if ( (tmp & mask) != (expected << shift) )
 236         return false;
 237
 238     return true;
 239 }
 240
 241 int main(int, char *[])
 242 {
 243     boost::posix_time::time_duration reciprocal_lambda;
 244
 245     double avg_race_time = estimate_avg_race_time();
 246
 247     /* 5.298 = 0.995 quantile of exponential distribution */
 248     const boost::posix_time::time_duration timeout = boost::posix_time::microseconds((long)(5.298 * avg_race_time));
 249
 250     {
 251         boost::atomic<unsigned int> value(0);
 252
 253         /* testing two different operations in this loop, therefore
 254         enlarge timeout */
 255         boost::posix_time::time_duration tmp(timeout * 2);
 256
 257         bool success = concurrent_runner::execute(
 258             boost::bind(test_arithmetic<unsigned int, 0>, boost::ref(value), _1),
 259             tmp
 260         );
 261
 262         BOOST_TEST(success); // concurrent arithmetic error
 263     }
 264
 265     {
 266         boost::atomic<unsigned int> value(0);
 267
 268         /* testing three different operations in this loop, therefore
 269         enlarge timeout */
 270         boost::posix_time::time_duration tmp(timeout * 3);
 271
 272         bool success = concurrent_runner::execute(
 273             boost::bind(test_bitops<unsigned int, 0>, boost::ref(value), _1),
 274             tmp
 275         );
 276
 277         BOOST_TEST(success); // concurrent bit operations error
 278     }
 279
 280     return boost::report_errors();
 281 }