Branch data Line data Source code
1 : : // Copyright (c) 2012-2022 The Bitcoin Core developers
2 : : // Distributed under the MIT software license, see the accompanying
3 : : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 : :
5 : : #include <checkqueue.h>
6 : : #include <common/args.h>
7 : : #include <sync.h>
8 : : #include <test/util/random.h>
9 : : #include <test/util/setup_common.h>
10 : : #include <util/chaintype.h>
11 : : #include <util/time.h>
12 : :
13 : : #include <boost/test/unit_test.hpp>
14 : :
15 : : #include <atomic>
16 : : #include <condition_variable>
17 : : #include <mutex>
18 : : #include <thread>
19 : : #include <unordered_set>
20 : : #include <utility>
21 : : #include <vector>
22 : :
23 : : /**
24 : : * Identical to TestingSetup but excludes lock contention logging if
25 : : * `DEBUG_LOCKCONTENTION` is defined, as some of these tests are designed to be
26 : : * heavily contested to trigger race conditions or other issues.
27 : : */
28 : 20 : struct NoLockLoggingTestingSetup : public TestingSetup {
29 : 10 : NoLockLoggingTestingSetup()
30 : : #ifdef DEBUG_LOCKCONTENTION
31 : : : TestingSetup{ChainType::MAIN, {.extra_args = { "-debugexclude=lock" } }} {}
32 : : #else
33 [ + - ]: 20 : : TestingSetup{ChainType::MAIN} {}
34 : : #endif
35 : : };
36 : :
37 : 30 : struct CheckQueueTest : NoLockLoggingTestingSetup {
38 : : void Correct_Queue_range(std::vector<size_t> range);
39 : : };
40 : :
41 : : static const unsigned int QUEUE_BATCH_SIZE = 128;
42 : : static const int SCRIPT_CHECK_THREADS = 3;
43 : :
44 : : struct FakeCheck {
45 : : bool operator()() const
46 : : {
47 : : return true;
48 : : }
49 : : };
50 : :
51 : : struct FakeCheckCheckCompletion {
52 : : static std::atomic<size_t> n_calls;
53 : 11858799 : bool operator()()
54 : : {
55 : 11858799 : n_calls.fetch_add(1, std::memory_order_relaxed);
56 : 11858799 : return true;
57 : : }
58 : : };
59 : :
60 : : struct FailingCheck {
61 : : bool fails;
62 : 500500 : FailingCheck(bool _fails) : fails(_fails){};
63 : 482968 : bool operator()() const
64 : : {
65 : 482968 : return !fails;
66 : : }
67 : : };
68 : :
69 : : struct UniqueCheck {
70 : : static Mutex m;
71 : : static std::unordered_multiset<size_t> results GUARDED_BY(m);
72 : : size_t check_id;
73 : 100000 : UniqueCheck(size_t check_id_in) : check_id(check_id_in){};
74 : 100000 : bool operator()()
75 : : {
76 : 100000 : LOCK(m);
77 [ + - ]: 100000 : results.insert(check_id);
78 [ + - ]: 100000 : return true;
79 : 100000 : }
80 : : };
81 : :
82 : :
83 : : struct MemoryCheck {
84 : : static std::atomic<size_t> fake_allocated_memory;
85 : : bool b {false};
86 : : bool operator()() const
87 : : {
88 : : return true;
89 : : }
90 : 1553388 : MemoryCheck(const MemoryCheck& x)
91 : 1553388 : {
92 : : // We have to do this to make sure that destructor calls are paired
93 : : //
94 : : // Really, copy constructor should be deletable, but CCheckQueue breaks
95 : : // if it is deleted because of internal push_back.
96 : 1553388 : fake_allocated_memory.fetch_add(b, std::memory_order_relaxed);
97 : : };
98 : 499500 : MemoryCheck(bool b_) : b(b_)
99 : : {
100 : 499500 : fake_allocated_memory.fetch_add(b, std::memory_order_relaxed);
101 : : };
102 : 2052888 : ~MemoryCheck()
103 : : {
104 : 2052888 : fake_allocated_memory.fetch_sub(b, std::memory_order_relaxed);
105 : 2052888 : };
106 : : };
107 : :
108 : : struct FrozenCleanupCheck {
109 : : static std::atomic<uint64_t> nFrozen;
110 : : static std::condition_variable cv;
111 : : static std::mutex m;
112 : : bool should_freeze{true};
113 : : bool operator()() const
114 : : {
115 : : return true;
116 : : }
117 : 1 : FrozenCleanupCheck() = default;
118 : 3 : ~FrozenCleanupCheck()
119 : : {
120 [ + + ]: 3 : if (should_freeze) {
121 : 1 : std::unique_lock<std::mutex> l(m);
122 : 1 : nFrozen.store(1, std::memory_order_relaxed);
123 : 1 : cv.notify_one();
124 [ + + + - ]: 3 : cv.wait(l, []{ return nFrozen.load(std::memory_order_relaxed) == 0;});
125 : 1 : }
126 : 3 : }
127 : 2 : FrozenCleanupCheck(FrozenCleanupCheck&& other) noexcept
128 : 2 : {
129 : 2 : should_freeze = other.should_freeze;
130 : 2 : other.should_freeze = false;
131 : : }
132 : 0 : FrozenCleanupCheck& operator=(FrozenCleanupCheck&& other) noexcept
133 : : {
134 : 0 : should_freeze = other.should_freeze;
135 : 0 : other.should_freeze = false;
136 : 0 : return *this;
137 : : }
138 : : };
139 : :
140 : : // Static Allocations
141 : : std::mutex FrozenCleanupCheck::m{};
142 : : std::atomic<uint64_t> FrozenCleanupCheck::nFrozen{0};
143 : : std::condition_variable FrozenCleanupCheck::cv{};
144 : : Mutex UniqueCheck::m;
145 : : std::unordered_multiset<size_t> UniqueCheck::results;
146 : : std::atomic<size_t> FakeCheckCheckCompletion::n_calls{0};
147 : : std::atomic<size_t> MemoryCheck::fake_allocated_memory{0};
148 : :
149 : : // Queue Typedefs
150 : : typedef CCheckQueue<FakeCheckCheckCompletion> Correct_Queue;
151 : : typedef CCheckQueue<FakeCheck> Standard_Queue;
152 : : typedef CCheckQueue<FailingCheck> Failing_Queue;
153 : : typedef CCheckQueue<UniqueCheck> Unique_Queue;
154 : : typedef CCheckQueue<MemoryCheck> Memory_Queue;
155 : : typedef CCheckQueue<FrozenCleanupCheck> FrozenCleanup_Queue;
156 : :
157 : :
158 : : /** This test case checks that the CCheckQueue works properly
159 : : * with each specified size_t Checks pushed.
160 : : */
161 : 4 : void CheckQueueTest::Correct_Queue_range(std::vector<size_t> range)
162 : : {
163 : 4 : auto small_queue = std::make_unique<Correct_Queue>(QUEUE_BATCH_SIZE, SCRIPT_CHECK_THREADS);
164 : : // Make vChecks here to save on malloc (this test can be slow...)
165 : 4 : std::vector<FakeCheckCheckCompletion> vChecks;
166 [ + - ]: 4 : vChecks.reserve(9);
167 [ + + ]: 229 : for (const size_t i : range) {
168 : 225 : size_t total = i;
169 [ + - ]: 225 : FakeCheckCheckCompletion::n_calls = 0;
170 [ + - ]: 225 : CCheckQueueControl<FakeCheckCheckCompletion> control(small_queue.get());
171 : 2634398 : while (total) {
172 [ + + ]: 2634173 : vChecks.clear();
173 [ + + + - ]: 2634397 : vChecks.resize(std::min<size_t>(total, m_rng.randrange(10)));
174 [ - + ]: 2634173 : total -= vChecks.size();
175 [ - + + + ]: 5268571 : control.Add(std::move(vChecks));
176 : : }
177 [ + - + - : 450 : BOOST_REQUIRE(control.Wait());
+ - + - ]
178 [ + - + - ]: 225 : BOOST_REQUIRE_EQUAL(FakeCheckCheckCompletion::n_calls, i);
179 : 225 : }
180 : 4 : }
181 : :
182 : : BOOST_FIXTURE_TEST_SUITE(checkqueue_tests, CheckQueueTest)
183 : :
184 : : /** Test that 0 checks is correct
185 : : */
186 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(test_CheckQueue_Correct_Zero)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
187 : : {
188 : 1 : std::vector<size_t> range;
189 [ + - ]: 1 : range.push_back(size_t{0});
190 [ + - + - ]: 2 : Correct_Queue_range(range);
191 : 1 : }
192 : : /** Test that 1 check is correct
193 : : */
194 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(test_CheckQueue_Correct_One)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
195 : : {
196 : 1 : std::vector<size_t> range;
197 [ + - ]: 1 : range.push_back(size_t{1});
198 [ + - + - ]: 2 : Correct_Queue_range(range);
199 : 1 : }
200 : : /** Test that MAX check is correct
201 : : */
202 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(test_CheckQueue_Correct_Max)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
203 : : {
204 : 1 : std::vector<size_t> range;
205 [ + - ]: 1 : range.push_back(100000);
206 [ + - + - ]: 2 : Correct_Queue_range(range);
207 : 1 : }
208 : : /** Test that random numbers of checks are correct
209 : : */
210 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(test_CheckQueue_Correct_Random)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
211 : : {
212 : 1 : std::vector<size_t> range;
213 [ + - ]: 1 : range.reserve(100000/1000);
214 [ + + + + : 438 : for (size_t i = 2; i < 100000; i += std::max((size_t)1, (size_t)m_rng.randrange(std::min((size_t)1000, ((size_t)100000) - i))))
+ + ]
215 [ + - ]: 222 : range.push_back(i);
216 [ + - + - ]: 2 : Correct_Queue_range(range);
217 : 1 : }
218 : :
219 : :
220 : : /** Test that failing checks are caught */
221 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(test_CheckQueue_Catches_Failure)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
222 : : {
223 : 1 : auto fail_queue = std::make_unique<Failing_Queue>(QUEUE_BATCH_SIZE, SCRIPT_CHECK_THREADS);
224 [ + + ]: 1002 : for (size_t i = 0; i < 1001; ++i) {
225 [ + - ]: 1001 : CCheckQueueControl<FailingCheck> control(fail_queue.get());
226 : : size_t remaining = i;
227 [ + + ]: 112731 : while (remaining) {
228 : 111730 : size_t r = m_rng.randrange(10);
229 : :
230 : 111730 : std::vector<FailingCheck> vChecks;
231 [ + - ]: 111730 : vChecks.reserve(r);
232 [ + + ]: 612230 : for (size_t k = 0; k < r && remaining; k++, remaining--)
233 [ + - ]: 500500 : vChecks.emplace_back(remaining == 1);
234 [ + - ]: 223460 : control.Add(std::move(vChecks));
235 : 111730 : }
236 [ + - ]: 1001 : bool success = control.Wait();
237 [ + + ]: 1001 : if (i > 0) {
238 [ + - + - ]: 2000 : BOOST_REQUIRE(!success);
239 : 1 : } else if (i == 0) {
240 [ + - + - ]: 2 : BOOST_REQUIRE(success);
241 : : }
242 : 1001 : }
243 : 1 : }
244 : : // Test that a block validation which fails does not interfere with
245 : : // future blocks, ie, the bad state is cleared.
246 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(test_CheckQueue_Recovers_From_Failure)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
247 : : {
248 : 1 : auto fail_queue = std::make_unique<Failing_Queue>(QUEUE_BATCH_SIZE, SCRIPT_CHECK_THREADS);
249 [ + + ]: 11 : for (auto times = 0; times < 10; ++times) {
250 [ + + ]: 30 : for (const bool end_fails : {true, false}) {
251 [ + - ]: 20 : CCheckQueueControl<FailingCheck> control(fail_queue.get());
252 : 20 : {
253 : 20 : std::vector<FailingCheck> vChecks;
254 [ + - ]: 20 : vChecks.resize(100, false);
255 [ + - ]: 20 : vChecks[99] = end_fails;
256 [ + - ]: 40 : control.Add(std::move(vChecks));
257 : 0 : }
258 [ + - ]: 20 : bool r =control.Wait();
259 [ + - + - ]: 40 : BOOST_REQUIRE(r != end_fails);
260 : 20 : }
261 : : }
262 : 1 : }
263 : :
264 : : // Test that unique checks are actually all called individually, rather than
265 : : // just one check being called repeatedly. Test that checks are not called
266 : : // more than once as well
267 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(test_CheckQueue_UniqueCheck)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
268 : : {
269 : 1 : auto queue = std::make_unique<Unique_Queue>(QUEUE_BATCH_SIZE, SCRIPT_CHECK_THREADS);
270 : 1 : size_t COUNT = 100000;
271 : 1 : size_t total = COUNT;
272 : 1 : {
273 [ + - ]: 1 : CCheckQueueControl<UniqueCheck> control(queue.get());
274 [ + + ]: 22152 : while (total) {
275 : 22151 : size_t r = m_rng.randrange(10);
276 : 22151 : std::vector<UniqueCheck> vChecks;
277 [ + + + + ]: 122151 : for (size_t k = 0; k < r && total; k++)
278 [ + - ]: 100000 : vChecks.emplace_back(--total);
279 [ + - ]: 44302 : control.Add(std::move(vChecks));
280 : 22151 : }
281 : 1 : }
282 : 1 : {
283 [ + - ]: 1 : LOCK(UniqueCheck::m);
284 : 1 : bool r = true;
285 [ + - + - ]: 1 : BOOST_REQUIRE_EQUAL(UniqueCheck::results.size(), COUNT);
286 [ + + ]: 100001 : for (size_t i = 0; i < COUNT; ++i) {
287 [ + - - + ]: 200000 : r = r && UniqueCheck::results.count(i) == 1;
288 : : }
289 [ + - + - : 2 : BOOST_REQUIRE(r);
+ - ]
290 : 0 : }
291 : 1 : }
292 : :
293 : :
294 : : // Test that blocks which might allocate lots of memory free their memory aggressively.
295 : : //
296 : : // This test attempts to catch a pathological case where by lazily freeing
297 : : // checks might mean leaving a check un-swapped out, and decreasing by 1 each
298 : : // time could leave the data hanging across a sequence of blocks.
299 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(test_CheckQueue_Memory)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
300 : : {
301 : 1 : auto queue = std::make_unique<Memory_Queue>(QUEUE_BATCH_SIZE, SCRIPT_CHECK_THREADS);
302 [ + + ]: 1001 : for (size_t i = 0; i < 1000; ++i) {
303 : 1000 : size_t total = i;
304 : 1000 : {
305 [ + - ]: 1000 : CCheckQueueControl<MemoryCheck> control(queue.get());
306 [ + + ]: 112520 : while (total) {
307 : 111520 : size_t r = m_rng.randrange(10);
308 : 111520 : std::vector<MemoryCheck> vChecks;
309 [ + + ]: 611020 : for (size_t k = 0; k < r && total; k++) {
310 : 499500 : total--;
311 : : // Each iteration leaves data at the front, back, and middle
312 : : // to catch any sort of deallocation failure
313 [ + + + + : 997003 : vChecks.emplace_back(total == 0 || total == i || total == i/2);
+ - ]
314 : : }
315 [ + - ]: 111520 : control.Add(std::move(vChecks));
316 : 111520 : }
317 : 1000 : }
318 [ + - + - ]: 1000 : BOOST_REQUIRE_EQUAL(MemoryCheck::fake_allocated_memory, 0U);
319 : : }
320 : 1 : }
321 : :
322 : : // Test that a new verification cannot occur until all checks
323 : : // have been destructed
324 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(test_CheckQueue_FrozenCleanup)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
325 : : {
326 : 1 : auto queue = std::make_unique<FrozenCleanup_Queue>(QUEUE_BATCH_SIZE, SCRIPT_CHECK_THREADS);
327 : 1 : bool fails = false;
328 : 2 : std::thread t0([&]() {
329 [ + - ]: 1 : CCheckQueueControl<FrozenCleanupCheck> control(queue.get());
330 [ + - ]: 1 : std::vector<FrozenCleanupCheck> vChecks(1);
331 [ + - ]: 1 : control.Add(std::move(vChecks));
332 [ + - ]: 1 : bool waitResult = control.Wait(); // Hangs here
333 [ - + ]: 1 : assert(waitResult);
334 [ + - ]: 2 : });
335 : 1 : {
336 [ + - ]: 1 : std::unique_lock<std::mutex> l(FrozenCleanupCheck::m);
337 : : // Wait until the queue has finished all jobs and frozen
338 [ + + ]: 3 : FrozenCleanupCheck::cv.wait(l, [](){return FrozenCleanupCheck::nFrozen == 1;});
339 : 0 : }
340 : : // Try to get control of the queue a bunch of times
341 [ + + ]: 101 : for (auto x = 0; x < 100 && !fails; ++x) {
342 : 100 : fails = queue->m_control_mutex.try_lock();
343 : : }
344 : 1 : {
345 : : // Unfreeze (we need lock n case of spurious wakeup)
346 [ + - ]: 1 : std::unique_lock<std::mutex> l(FrozenCleanupCheck::m);
347 [ + - ]: 1 : FrozenCleanupCheck::nFrozen = 0;
348 : 1 : }
349 : : // Awaken frozen destructor
350 : 1 : FrozenCleanupCheck::cv.notify_one();
351 : : // Wait for control to finish
352 [ + - ]: 1 : t0.join();
353 [ + - + - ]: 2 : BOOST_REQUIRE(!fails);
354 : 1 : }
355 : :
356 : :
357 : : /** Test that CCheckQueueControl is threadsafe */
358 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(test_CheckQueueControl_Locks)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
359 : : {
360 : 1 : auto queue = std::make_unique<Standard_Queue>(QUEUE_BATCH_SIZE, SCRIPT_CHECK_THREADS);
361 : 1 : {
362 : 1 : std::vector<std::thread> tg;
363 : 1 : std::atomic<int> nThreads {0};
364 : 1 : std::atomic<int> fails {0};
365 [ + + ]: 4 : for (size_t i = 0; i < 3; ++i) {
366 : 3 : tg.emplace_back(
367 [ + - ]: 6 : [&]{
368 [ + - ]: 3 : CCheckQueueControl<FakeCheck> control(queue.get());
369 : : // While sleeping, no other thread should execute to this point
370 : 3 : auto observed = ++nThreads;
371 [ + - ]: 3 : UninterruptibleSleep(std::chrono::milliseconds{10});
372 : 3 : fails += observed != nThreads;
373 : 3 : });
374 : : }
375 [ + + ]: 4 : for (auto& thread: tg) {
376 [ + - + - ]: 3 : if (thread.joinable()) thread.join();
377 : : }
378 [ + - + - ]: 1 : BOOST_REQUIRE_EQUAL(fails, 0);
379 : 1 : }
380 : 1 : {
381 : 1 : std::vector<std::thread> tg;
382 : 1 : std::mutex m;
383 : 1 : std::condition_variable cv;
384 : 1 : bool has_lock{false};
385 : 1 : bool has_tried{false};
386 : 1 : bool done{false};
387 : 1 : bool done_ack{false};
388 : 1 : {
389 [ + - ]: 1 : std::unique_lock<std::mutex> l(m);
390 [ + - ]: 2 : tg.emplace_back([&]{
391 [ + - ]: 1 : CCheckQueueControl<FakeCheck> control(queue.get());
392 [ + - ]: 1 : std::unique_lock<std::mutex> ll(m);
393 : 1 : has_lock = true;
394 : 1 : cv.notify_one();
395 [ + + ]: 2 : cv.wait(ll, [&]{return has_tried;});
396 : 1 : done = true;
397 : 1 : cv.notify_one();
398 : : // Wait until the done is acknowledged
399 : : //
400 [ + + + - ]: 2 : cv.wait(ll, [&]{return done_ack;});
401 : 1 : });
402 : : // Wait for thread to get the lock
403 [ + + ]: 2 : cv.wait(l, [&](){return has_lock;});
404 : : bool fails = false;
405 [ + + ]: 101 : for (auto x = 0; x < 100 && !fails; ++x) {
406 : 100 : fails = queue->m_control_mutex.try_lock();
407 : : }
408 : 1 : has_tried = true;
409 : 1 : cv.notify_one();
410 [ + + ]: 2 : cv.wait(l, [&](){return done;});
411 : : // Acknowledge the done
412 : 1 : done_ack = true;
413 : 1 : cv.notify_one();
414 [ + - + - : 2 : BOOST_REQUIRE(!fails);
+ - ]
415 : 0 : }
416 [ + + ]: 2 : for (auto& thread: tg) {
417 [ + - + - ]: 1 : if (thread.joinable()) thread.join();
418 : : }
419 : 1 : }
420 : 1 : }
421 : : BOOST_AUTO_TEST_SUITE_END()
|
