]>
Commit | Line | Data |
---|---|---|
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 ordering.cpp by Helge Bahmann and Tim Blechmann. | |
8 | // The test Was modified to use atomic_ref template instead of atomic. | |
9 | ||
10 | // Attempt to determine whether the memory ordering/ fence operations | |
11 | // work as expected: | |
12 | // Let two threads race accessing multiple shared variables and | |
13 | // verify that "observable" order of operations matches with the | |
14 | // ordering constraints specified. | |
15 | // | |
16 | // We assume that "memory ordering violation" events are exponentially | |
17 | // distributed, with unknown "average time between violations" | |
18 | // (which is just the reciprocal of exp distribution parameter lambda). | |
19 | // Use a "relaxed ordering" implementation that intentionally exhibits | |
20 | // a (hopefully observable) such violation to compute the maximum-likelihood | |
21 | // estimate for this time. From this, compute an estimate that covers the | |
22 | // unknown value with 0.995 confidence (using chi square quantile). | |
23 | // | |
24 | // Use this estimate to pick a timeout for the race tests of the | |
25 | // atomic implementations such that under the assumed distribution | |
26 | // we get 0.995 probability to detect a race (if there is one). | |
27 | // | |
28 | // Overall this yields 0.995 * 0.995 > 0.99 confidence that the | |
29 | // fences work as expected if this test program does not | |
30 | // report an error. | |
31 | ||
32 | #include <boost/memory_order.hpp> | |
33 | #include <boost/atomic/atomic.hpp> | |
34 | #include <boost/atomic/atomic_ref.hpp> | |
35 | ||
36 | #include <cstddef> | |
37 | #include <boost/bind/bind.hpp> | |
38 | #include <boost/date_time/posix_time/posix_time_types.hpp> | |
39 | #include <boost/thread/thread.hpp> | |
40 | #include <boost/thread/thread_time.hpp> | |
41 | #include <boost/thread/lock_guard.hpp> | |
42 | #include <boost/thread/lock_types.hpp> | |
43 | #include <boost/thread/mutex.hpp> | |
44 | #include <boost/thread/condition_variable.hpp> | |
45 | #include <boost/thread/barrier.hpp> | |
46 | #include <boost/core/lightweight_test.hpp> | |
47 | ||
48 | // Two threads perform the following operations: | |
49 | // | |
50 | // thread # 1 thread # 2 | |
51 | // store(a, 1) store(b, 1) | |
52 | // x = read(b) y = read(a) | |
53 | // | |
54 | // Under relaxed memory ordering, the case (x, y) == (0, 0) is | |
55 | // possible. Under sequential consistency, this case is impossible. | |
56 | // | |
57 | // This "problem" is reproducible on all platforms, even x86. | |
58 | template<boost::memory_order store_order, boost::memory_order load_order> | |
59 | class total_store_order_test | |
60 | { | |
61 | public: | |
62 | total_store_order_test(void); | |
63 | ||
64 | void run(boost::posix_time::time_duration & timeout); | |
65 | bool detected_conflict(void) const { return detected_conflict_; } | |
66 | ||
67 | private: | |
68 | void thread1fn(void); | |
69 | void thread2fn(void); | |
70 | void check_conflict(void); | |
71 | ||
72 | private: | |
73 | int a_value_; | |
74 | boost::atomic_ref<int> a_; | |
75 | /* insert a bit of padding to push the two variables into | |
76 | different cache lines and increase the likelihood of detecting | |
77 | a conflict */ | |
78 | char pad1_[512]; | |
79 | int b_value_; | |
80 | boost::atomic_ref<int> b_; | |
81 | ||
82 | char pad2_[512]; | |
83 | boost::barrier barrier_; | |
84 | ||
85 | int vrfyb1_, vrfya2_; | |
86 | ||
87 | boost::atomic<bool> terminate_threads_; | |
88 | boost::atomic<int> termination_consensus_; | |
89 | ||
90 | bool detected_conflict_; | |
91 | boost::mutex m_; | |
92 | boost::condition_variable c_; | |
93 | }; | |
94 | ||
95 | template<boost::memory_order store_order, boost::memory_order load_order> | |
96 | total_store_order_test<store_order, load_order>::total_store_order_test(void) : | |
97 | a_value_(0), a_(a_value_), b_value_(0), b_(b_value_), barrier_(2), | |
98 | vrfyb1_(0), vrfya2_(0), | |
99 | terminate_threads_(false), termination_consensus_(0), | |
100 | detected_conflict_(false) | |
101 | { | |
102 | } | |
103 | ||
104 | template<boost::memory_order store_order, boost::memory_order load_order> | |
105 | void total_store_order_test<store_order, load_order>::run(boost::posix_time::time_duration & timeout) | |
106 | { | |
107 | boost::system_time start = boost::get_system_time(); | |
108 | boost::system_time end = start + timeout; | |
109 | ||
110 | boost::thread t1(boost::bind(&total_store_order_test::thread1fn, this)); | |
111 | boost::thread t2(boost::bind(&total_store_order_test::thread2fn, this)); | |
112 | ||
113 | { | |
114 | boost::unique_lock< boost::mutex > guard(m_); | |
115 | while (boost::get_system_time() < end && !detected_conflict_) | |
116 | c_.timed_wait(guard, end); | |
117 | } | |
118 | ||
119 | terminate_threads_.store(true, boost::memory_order_relaxed); | |
120 | ||
121 | t2.join(); | |
122 | t1.join(); | |
123 | ||
124 | boost::posix_time::time_duration duration = boost::get_system_time() - start; | |
125 | if (duration < timeout) | |
126 | timeout = duration; | |
127 | } | |
128 | ||
129 | volatile int backoff_dummy; | |
130 | ||
131 | template<boost::memory_order store_order, boost::memory_order load_order> | |
132 | void total_store_order_test<store_order, load_order>::thread1fn(void) | |
133 | { | |
134 | while (true) | |
135 | { | |
136 | a_.store(1, store_order); | |
137 | int b = b_.load(load_order); | |
138 | ||
139 | barrier_.wait(); | |
140 | ||
141 | vrfyb1_ = b; | |
142 | ||
143 | barrier_.wait(); | |
144 | ||
145 | check_conflict(); | |
146 | ||
147 | /* both threads synchronize via barriers, so either | |
148 | both threads must exit here, or they must both do | |
149 | another round, otherwise one of them will wait forever */ | |
150 | if (terminate_threads_.load(boost::memory_order_relaxed)) | |
151 | { | |
152 | while (true) | |
153 | { | |
154 | int tmp = termination_consensus_.fetch_or(1, boost::memory_order_relaxed); | |
155 | ||
156 | if (tmp == 3) | |
157 | return; | |
158 | if (tmp & 4) | |
159 | break; | |
160 | } | |
161 | } | |
162 | ||
163 | termination_consensus_.fetch_xor(4, boost::memory_order_relaxed); | |
164 | ||
165 | unsigned int delay = rand() % 10000; | |
166 | a_.store(0, boost::memory_order_relaxed); | |
167 | ||
168 | barrier_.wait(); | |
169 | ||
170 | while (delay--) | |
171 | backoff_dummy = delay; | |
172 | } | |
173 | } | |
174 | ||
175 | template<boost::memory_order store_order, boost::memory_order load_order> | |
176 | void total_store_order_test<store_order, load_order>::thread2fn(void) | |
177 | { | |
178 | while (true) | |
179 | { | |
180 | b_.store(1, store_order); | |
181 | int a = a_.load(load_order); | |
182 | ||
183 | barrier_.wait(); | |
184 | ||
185 | vrfya2_ = a; | |
186 | ||
187 | barrier_.wait(); | |
188 | ||
189 | check_conflict(); | |
190 | ||
191 | /* both threads synchronize via barriers, so either | |
192 | both threads must exit here, or they must both do | |
193 | another round, otherwise one of them will wait forever */ | |
194 | if (terminate_threads_.load(boost::memory_order_relaxed)) | |
195 | { | |
196 | while (true) | |
197 | { | |
198 | int tmp = termination_consensus_.fetch_or(2, boost::memory_order_relaxed); | |
199 | ||
200 | if (tmp == 3) | |
201 | return; | |
202 | if (tmp & 4) | |
203 | break; | |
204 | } | |
205 | } | |
206 | ||
207 | termination_consensus_.fetch_xor(4, boost::memory_order_relaxed); | |
208 | ||
209 | unsigned int delay = rand() % 10000; | |
210 | b_.store(0, boost::memory_order_relaxed); | |
211 | ||
212 | barrier_.wait(); | |
213 | ||
214 | while (delay--) | |
215 | backoff_dummy = delay; | |
216 | } | |
217 | } | |
218 | ||
219 | template<boost::memory_order store_order, boost::memory_order load_order> | |
220 | void total_store_order_test<store_order, load_order>::check_conflict(void) | |
221 | { | |
222 | if (vrfyb1_ == 0 && vrfya2_ == 0) | |
223 | { | |
224 | boost::lock_guard< boost::mutex > guard(m_); | |
225 | detected_conflict_ = true; | |
226 | terminate_threads_.store(true, boost::memory_order_relaxed); | |
227 | c_.notify_all(); | |
228 | } | |
229 | } | |
230 | ||
231 | void test_seq_cst(void) | |
232 | { | |
233 | double sum = 0.0; | |
234 | ||
235 | /* take 10 samples */ | |
236 | for (std::size_t n = 0; n < 10; n++) | |
237 | { | |
238 | boost::posix_time::time_duration timeout(0, 0, 10); | |
239 | ||
240 | total_store_order_test<boost::memory_order_relaxed, boost::memory_order_relaxed> test; | |
241 | test.run(timeout); | |
242 | if (!test.detected_conflict()) | |
243 | { | |
244 | std::cout << "Failed to detect order=seq_cst violation while ith order=relaxed -- intrinsic ordering too strong for this test\n"; | |
245 | return; | |
246 | } | |
247 | ||
248 | std::cout << "seq_cst violation with order=relaxed after " << timeout.total_microseconds() << " us\n"; | |
249 | ||
250 | sum = sum + timeout.total_microseconds(); | |
251 | } | |
252 | ||
253 | /* determine maximum likelihood estimate for average time between | |
254 | race observations */ | |
255 | double avg_race_time_mle = (sum / 10); | |
256 | ||
257 | /* pick 0.995 confidence (7.44 = chi square 0.995 confidence) */ | |
258 | double avg_race_time_995 = avg_race_time_mle * 2 * 10 / 7.44; | |
259 | ||
260 | /* 5.298 = 0.995 quantile of exponential distribution */ | |
261 | boost::posix_time::time_duration timeout = boost::posix_time::microseconds((long)(5.298 * avg_race_time_995)); | |
262 | ||
263 | std::cout << "run seq_cst for " << timeout.total_microseconds() << " us\n"; | |
264 | ||
265 | total_store_order_test<boost::memory_order_seq_cst, boost::memory_order_seq_cst> test; | |
266 | test.run(timeout); | |
267 | ||
268 | BOOST_TEST(!test.detected_conflict()); // sequential consistency error | |
269 | } | |
270 | ||
271 | int main(int, char *[]) | |
272 | { | |
273 | test_seq_cst(); | |
274 | ||
275 | return boost::report_errors(); | |
276 | } |