• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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);
detected_conflict(void) const65     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>
total_store_order_test(void)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>
run(boost::posix_time::time_duration & timeout)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>
thread1fn(void)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>
thread2fn(void)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>
check_conflict(void)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 
test_seq_cst(void)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 
main(int,char * [])271 int main(int, char *[])
272 {
273     test_seq_cst();
274 
275     return boost::report_errors();
276 }
277