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