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