]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
f67539c2 | 29 | #include <cstddef> |
7c673cae | 30 | #include <algorithm> |
f67539c2 | 31 | #include <boost/config.hpp> |
7c673cae | 32 | #include <boost/ref.hpp> |
7c673cae | 33 | #include <boost/function.hpp> |
f67539c2 | 34 | #include <boost/bind/bind.hpp> |
7c673cae | 35 | #include <boost/date_time/posix_time/posix_time_types.hpp> |
7c673cae FG |
36 | #include <boost/thread/thread.hpp> |
37 | #include <boost/thread/thread_time.hpp> | |
f67539c2 TL |
38 | #include <boost/thread/lock_guard.hpp> |
39 | #include <boost/thread/lock_types.hpp> | |
7c673cae FG |
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 */ | |
f67539c2 TL |
46 | class concurrent_runner |
47 | { | |
7c673cae FG |
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 */ | |
f67539c2 | 52 | static bool execute(const boost::function<bool(std::size_t)> & fn, boost::posix_time::time_duration & timeout) |
7c673cae FG |
53 | { |
54 | concurrent_runner runner(fn); | |
55 | runner.wait_finish(timeout); | |
56 | return !runner.failure(); | |
57 | } | |
58 | ||
f67539c2 TL |
59 | concurrent_runner(const boost::function<bool(std::size_t)> & fn) : |
60 | finished_(false), failure_(false) | |
7c673cae FG |
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 | ||
f67539c2 | 66 | void wait_finish(boost::posix_time::time_duration & timeout) |
7c673cae FG |
67 | { |
68 | boost::system_time start = boost::get_system_time(); | |
69 | boost::system_time end = start + timeout; | |
70 | ||
71 | { | |
f67539c2 | 72 | boost::unique_lock< boost::mutex > guard(m_); |
7c673cae FG |
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 | ||
f67539c2 TL |
87 | bool finished(void) const BOOST_NOEXCEPT_OR_NOTHROW |
88 | { | |
7c673cae FG |
89 | return finished_.load(boost::memory_order_relaxed); |
90 | } | |
91 | ||
f67539c2 TL |
92 | bool failure(void) const BOOST_NOEXCEPT_OR_NOTHROW |
93 | { | |
7c673cae FG |
94 | return failure_; |
95 | } | |
f67539c2 | 96 | |
7c673cae | 97 | private: |
f67539c2 | 98 | void thread_function(boost::function<bool(std::size_t)> function, std::size_t instance) |
7c673cae | 99 | { |
f67539c2 TL |
100 | while (!finished()) |
101 | { | |
102 | if (!function(instance)) | |
103 | { | |
104 | boost::lock_guard< boost::mutex > guard(m_); | |
7c673cae FG |
105 | failure_ = true; |
106 | finished_.store(true, boost::memory_order_relaxed); | |
107 | c_.notify_all(); | |
108 | break; | |
109 | } | |
110 | } | |
111 | } | |
112 | ||
f67539c2 | 113 | private: |
7c673cae FG |
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 | ||
f67539c2 | 124 | bool racy_add(volatile unsigned int & value, std::size_t instance) |
7c673cae | 125 | { |
f67539c2 | 126 | std::size_t shift = instance * 8; |
7c673cae | 127 | unsigned int mask = 0xff << shift; |
f67539c2 TL |
128 | for (std::size_t n = 0; n < 255; ++n) |
129 | { | |
7c673cae FG |
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 */ | |
f67539c2 | 146 | double estimate_avg_race_time(void) |
7c673cae FG |
147 | { |
148 | double sum = 0.0; | |
149 | ||
150 | /* take 10 samples */ | |
f67539c2 TL |
151 | for (std::size_t n = 0; n < 10; ++n) |
152 | { | |
7c673cae FG |
153 | boost::posix_time::time_duration timeout(0, 0, 10); |
154 | ||
155 | volatile unsigned int value(0); | |
156 | bool success = concurrent_runner::execute( | |
f67539c2 | 157 | boost::bind(racy_add, boost::ref(value), boost::placeholders::_1), |
7c673cae FG |
158 | timeout |
159 | ); | |
160 | ||
f67539c2 TL |
161 | if (success) |
162 | { | |
7c673cae FG |
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 | ||
f67539c2 TL |
179 | template<typename value_type, std::size_t shift_> |
180 | bool test_arithmetic(boost::atomic<value_type> & shared_value, std::size_t instance) | |
7c673cae | 181 | { |
f67539c2 | 182 | std::size_t shift = instance * 8; |
7c673cae FG |
183 | value_type mask = 0xff << shift; |
184 | value_type increment = 1 << shift; | |
185 | ||
186 | value_type expected = 0; | |
187 | ||
f67539c2 TL |
188 | for (std::size_t n = 0; n < 255; ++n) |
189 | { | |
7c673cae FG |
190 | value_type tmp = shared_value.fetch_add(increment, boost::memory_order_relaxed); |
191 | if ( (tmp & mask) != (expected << shift) ) | |
192 | return false; | |
f67539c2 | 193 | ++expected; |
7c673cae | 194 | } |
f67539c2 TL |
195 | for (std::size_t n = 0; n < 255; ++n) |
196 | { | |
7c673cae FG |
197 | value_type tmp = shared_value.fetch_sub(increment, boost::memory_order_relaxed); |
198 | if ( (tmp & mask) != (expected << shift) ) | |
199 | return false; | |
f67539c2 | 200 | --expected; |
7c673cae FG |
201 | } |
202 | ||
203 | return true; | |
204 | } | |
205 | ||
f67539c2 TL |
206 | template<typename value_type, std::size_t shift_> |
207 | bool test_bitops(boost::atomic<value_type> & shared_value, std::size_t instance) | |
7c673cae | 208 | { |
f67539c2 | 209 | std::size_t shift = instance * 8; |
7c673cae FG |
210 | value_type mask = 0xff << shift; |
211 | ||
212 | value_type expected = 0; | |
213 | ||
f67539c2 TL |
214 | for (std::size_t k = 0; k < 8; ++k) |
215 | { | |
216 | value_type mod = 1u << k; | |
7c673cae FG |
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 | } | |
f67539c2 TL |
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); | |
7c673cae FG |
225 | if ( (tmp & mask) != (expected << shift)) |
226 | return false; | |
f67539c2 | 227 | expected = expected & ~(1u << k); |
7c673cae | 228 | } |
f67539c2 TL |
229 | for (std::size_t k = 0; k < 8; ++k) |
230 | { | |
231 | value_type mod = 255u ^ (1u << k); | |
7c673cae FG |
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 | ||
f67539c2 | 238 | value_type tmp = shared_value.fetch_and(~mask, boost::memory_order_relaxed); |
7c673cae FG |
239 | if ( (tmp & mask) != (expected << shift) ) |
240 | return false; | |
241 | ||
242 | return true; | |
243 | } | |
244 | ||
245 | int main(int, char *[]) | |
246 | { | |
7c673cae FG |
247 | double avg_race_time = estimate_avg_race_time(); |
248 | ||
249 | /* 5.298 = 0.995 quantile of exponential distribution */ | |
250 | const boost::posix_time::time_duration timeout = boost::posix_time::microseconds((long)(5.298 * avg_race_time)); | |
251 | ||
252 | { | |
253 | boost::atomic<unsigned int> value(0); | |
254 | ||
255 | /* testing two different operations in this loop, therefore | |
256 | enlarge timeout */ | |
257 | boost::posix_time::time_duration tmp(timeout * 2); | |
258 | ||
259 | bool success = concurrent_runner::execute( | |
f67539c2 | 260 | boost::bind(test_arithmetic<unsigned int, 0>, boost::ref(value), boost::placeholders::_1), |
7c673cae FG |
261 | tmp |
262 | ); | |
263 | ||
264 | BOOST_TEST(success); // concurrent arithmetic error | |
265 | } | |
266 | ||
267 | { | |
268 | boost::atomic<unsigned int> value(0); | |
269 | ||
270 | /* testing three different operations in this loop, therefore | |
271 | enlarge timeout */ | |
272 | boost::posix_time::time_duration tmp(timeout * 3); | |
273 | ||
274 | bool success = concurrent_runner::execute( | |
f67539c2 | 275 | boost::bind(test_bitops<unsigned int, 0>, boost::ref(value), boost::placeholders::_1), |
7c673cae FG |
276 | tmp |
277 | ); | |
278 | ||
279 | BOOST_TEST(success); // concurrent bit operations error | |
280 | } | |
281 | ||
282 | return boost::report_errors(); | |
283 | } |