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 <cstddef>
  30 #include <algorithm>
  31 #include <boost/config.hpp>
  32 #include <boost/ref.hpp>
  33 #include <boost/function.hpp>
  34 #include <boost/bind/bind.hpp>
  35 #include <boost/date_time/posix_time/posix_time_types.hpp>
  36 #include <boost/thread/thread.hpp>
  37 #include <boost/thread/thread_time.hpp>
  38 #include <boost/thread/lock_guard.hpp>
  39 #include <boost/thread/lock_types.hpp>
  40 #include <boost/thread/mutex.hpp>
  41 #include <boost/thread/condition_variable.hpp>
  42 #include <boost/core/lightweight_test.hpp>
  43
  44 /* helper class to let two instances of a function race against each
  45 other, with configurable timeout and early abort on detection of error */
  46 class concurrent_runner
  47 {
  48 public:
  49     /* concurrently run the function in two threads, until either timeout
  50     or one of the functions returns "false"; returns true if timeout
  51     was reached, or false if early abort and updates timeout accordingly */
  52     static bool execute(const boost::function<bool(std::size_t)> & fn, boost::posix_time::time_duration & timeout)
  53     {
  54         concurrent_runner runner(fn);
  55         runner.wait_finish(timeout);
  56         return !runner.failure();
  57     }
  58
  59     concurrent_runner(const boost::function<bool(std::size_t)> & fn) :
  60         finished_(false), failure_(false)
  61     {
  62         boost::thread(boost::bind(&concurrent_runner::thread_function, this, fn, 0)).swap(first_thread_);
  63         boost::thread(boost::bind(&concurrent_runner::thread_function, this, fn, 1)).swap(second_thread_);
  64     }
  65
  66     void wait_finish(boost::posix_time::time_duration & timeout)
  67     {
  68         boost::system_time start = boost::get_system_time();
  69         boost::system_time end = start + timeout;
  70
  71         {
  72             boost::unique_lock< boost::mutex > guard(m_);
  73             while (boost::get_system_time() < end && !finished())
  74                 c_.timed_wait(guard, end);
  75         }
  76
  77         finished_.store(true, boost::memory_order_relaxed);
  78
  79         first_thread_.join();
  80         second_thread_.join();
  81
  82         boost::posix_time::time_duration duration = boost::get_system_time() - start;
  83         if (duration < timeout)
  84             timeout = duration;
  85     }
  86
  87     bool finished(void) const BOOST_NOEXCEPT_OR_NOTHROW
  88     {
  89         return finished_.load(boost::memory_order_relaxed);
  90     }
  91
  92     bool failure(void) const BOOST_NOEXCEPT_OR_NOTHROW
  93     {
  94         return failure_;
  95     }
  96
  97 private:
  98     void thread_function(boost::function<bool(std::size_t)> function, std::size_t instance)
  99     {
 100         while (!finished())
 101         {
 102             if (!function(instance))
 103             {
 104                 boost::lock_guard< boost::mutex > guard(m_);
 105                 failure_ = true;
 106                 finished_.store(true, boost::memory_order_relaxed);
 107                 c_.notify_all();
 108                 break;
 109             }
 110         }
 111     }
 112
 113 private:
 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 racy_add(volatile unsigned int & value, std::size_t instance)
 125 {
 126     std::size_t shift = instance * 8;
 127     unsigned int mask = 0xff << shift;
 128     for (std::size_t n = 0; n < 255; ++n)
 129     {
 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 double estimate_avg_race_time(void)
 147 {
 148     double sum = 0.0;
 149
 150     /* take 10 samples */
 151     for (std::size_t n = 0; n < 10; ++n)
 152     {
 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), boost::placeholders::_1),
 158             timeout
 159         );
 160
 161         if (success)
 162         {
 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, std::size_t shift_>
 180 bool test_arithmetic(boost::atomic<value_type> & shared_value, std::size_t instance)
 181 {
 182     std::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 (std::size_t n = 0; n < 255; ++n)
 189     {
 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 (std::size_t n = 0; n < 255; ++n)
 196     {
 197         value_type tmp = shared_value.fetch_sub(increment, boost::memory_order_relaxed);
 198         if ( (tmp & mask) != (expected << shift) )
 199             return false;
 200         --expected;
 201     }
 202
 203     return true;
 204 }
 205
 206 template<typename value_type, std::size_t shift_>
 207 bool test_bitops(boost::atomic<value_type> & shared_value, std::size_t instance)
 208 {
 209     std::size_t shift = instance * 8;
 210     value_type mask = 0xff << shift;
 211
 212     value_type expected = 0;
 213
 214     for (std::size_t k = 0; k < 8; ++k)
 215     {
 216         value_type mod = 1u << k;
 217         value_type tmp = shared_value.fetch_or(mod << shift, boost::memory_order_relaxed);
 218         if ( (tmp & mask) != (expected << shift))
 219             return false;
 220         expected = expected | mod;
 221     }
 222     for (std::size_t k = 0; k < 8; ++k)
 223     {
 224         value_type tmp = shared_value.fetch_and(~(1u << (shift + k)), boost::memory_order_relaxed);
 225         if ( (tmp & mask) != (expected << shift))
 226             return false;
 227         expected = expected & ~(1u << k);
 228     }
 229     for (std::size_t k = 0; k < 8; ++k)
 230     {
 231         value_type mod = 255u ^ (1u << k);
 232         value_type tmp = shared_value.fetch_xor(mod << shift, boost::memory_order_relaxed);
 233         if ( (tmp & mask) != (expected << shift))
 234             return false;
 235         expected = expected ^ mod;
 236     }
 237
 238     value_type tmp = shared_value.fetch_and(~mask, boost::memory_order_relaxed);
 239     if ( (tmp & mask) != (expected << shift) )
 240         return false;
 241
 242     return true;
 243 }
 244
 245 int main(int, char *[])
 246 {
 247     boost::posix_time::time_duration reciprocal_lambda;
 248
 249     double avg_race_time = estimate_avg_race_time();
 250
 251     /* 5.298 = 0.995 quantile of exponential distribution */
 252     const boost::posix_time::time_duration timeout = boost::posix_time::microseconds((long)(5.298 * avg_race_time));
 253
 254     {
 255         boost::atomic<unsigned int> value(0);
 256
 257         /* testing two different operations in this loop, therefore
 258         enlarge timeout */
 259         boost::posix_time::time_duration tmp(timeout * 2);
 260
 261         bool success = concurrent_runner::execute(
 262             boost::bind(test_arithmetic<unsigned int, 0>, boost::ref(value), boost::placeholders::_1),
 263             tmp
 264         );
 265
 266         BOOST_TEST(success); // concurrent arithmetic error
 267     }
 268
 269     {
 270         boost::atomic<unsigned int> value(0);
 271
 272         /* testing three different operations in this loop, therefore
 273         enlarge timeout */
 274         boost::posix_time::time_duration tmp(timeout * 3);
 275
 276         bool success = concurrent_runner::execute(
 277             boost::bind(test_bitops<unsigned int, 0>, boost::ref(value), boost::placeholders::_1),
 278             tmp
 279         );
 280
 281         BOOST_TEST(success); // concurrent bit operations error
 282     }
 283
 284     return boost::report_errors();
 285 }