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 : 0 : std::optional<int> operator()() const
46 : : {
47 : 0 : return std::nullopt;
48 : : }
49 : : };
50 : :
51 : : struct FakeCheckCheckCompletion {
52 : : static std::atomic<size_t> n_calls;
53 : 11308766 : std::optional<int> operator()()
54 : : {
55 : 11308766 : n_calls.fetch_add(1, std::memory_order_relaxed);
56 : 11308766 : return std::nullopt;
57 : : }
58 : : };
59 : :
60 : : struct FixedCheck
61 : : {
62 : : std::optional<int> m_result;
63 [ + - ]: 500520 : FixedCheck(std::optional<int> result) : m_result(result){};
64 [ + + ]: 479088 : std::optional<int> operator()() const { return m_result; }
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 : std::optional<int> operator()()
73 : : {
74 : 100000 : LOCK(m);
75 [ + - ]: 100000 : results.insert(check_id);
76 [ + - ]: 100000 : return std::nullopt;
77 : 100000 : }
78 : : };
79 : :
80 : :
81 : : struct MemoryCheck {
82 : : static std::atomic<size_t> fake_allocated_memory;
83 : : bool b {false};
84 : 499500 : std::optional<int> operator()() const
85 : : {
86 : 499500 : return std::nullopt;
87 : : }
88 : 1555276 : MemoryCheck(const MemoryCheck& x)
89 : 1555276 : {
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 : 1555276 : 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 : 2054776 : ~MemoryCheck()
101 : : {
102 : 2054776 : fake_allocated_memory.fetch_sub(b, std::memory_order_relaxed);
103 : 2054776 : };
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 : 1 : std::optional<int> operator()() const
112 : : {
113 : 1 : return std::nullopt;
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<FixedCheck> Fixed_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 : void CheckQueueTest::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 [ + + ]: 222 : for (const size_t i : range) {
166 : 218 : size_t total = i;
167 [ + - ]: 218 : FakeCheckCheckCompletion::n_calls = 0;
168 [ + - ]: 218 : CCheckQueueControl<FakeCheckCheckCompletion> control(small_queue.get());
169 : 2515363 : while (total) {
170 [ + + ]: 6540303 : vChecks.clear();
171 [ + + + - ]: 2515362 : vChecks.resize(std::min<size_t>(total, m_rng.randrange(10)));
172 [ - + ]: 2515145 : total -= vChecks.size();
173 [ - + + + ]: 5030508 : control.Add(std::move(vChecks));
174 : : }
175 [ + - + - : 436 : BOOST_REQUIRE(!control.Complete().has_value());
+ - + - ]
176 [ + - + - ]: 218 : BOOST_REQUIRE_EQUAL(FakeCheckCheckCompletion::n_calls, i);
177 : 218 : }
178 : 4 : }
179 : :
180 : : BOOST_FIXTURE_TEST_SUITE(checkqueue_tests, CheckQueueTest)
181 : :
182 : : /** Test that 0 checks is correct
183 : : */
184 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(test_CheckQueue_Correct_Zero)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
185 : : {
186 : 1 : std::vector<size_t> range;
187 [ + - ]: 1 : range.push_back(size_t{0});
188 [ + - + - ]: 2 : Correct_Queue_range(range);
189 : 1 : }
190 : : /** Test that 1 check is correct
191 : : */
192 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(test_CheckQueue_Correct_One)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
193 : : {
194 : 1 : std::vector<size_t> range;
195 [ + - ]: 1 : range.push_back(size_t{1});
196 [ + - + - ]: 2 : Correct_Queue_range(range);
197 : 1 : }
198 : : /** Test that MAX check is correct
199 : : */
200 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(test_CheckQueue_Correct_Max)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
201 : : {
202 : 1 : std::vector<size_t> range;
203 [ + - ]: 1 : range.push_back(100000);
204 [ + - + - ]: 2 : Correct_Queue_range(range);
205 : 1 : }
206 : : /** Test that random numbers of checks are correct
207 : : */
208 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(test_CheckQueue_Correct_Random)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
209 : : {
210 : 1 : std::vector<size_t> range;
211 [ + - ]: 1 : range.reserve(100000/1000);
212 [ + + + + : 425 : 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))))
+ + ]
213 [ + - ]: 215 : range.push_back(i);
214 [ + - + - ]: 2 : Correct_Queue_range(range);
215 : 1 : }
216 : :
217 : :
218 : : /** Test that distinct failing checks are caught */
219 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(test_CheckQueue_Catches_Failure)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
220 : : {
221 : 1 : auto fixed_queue = std::make_unique<Fixed_Queue>(QUEUE_BATCH_SIZE, SCRIPT_CHECK_THREADS);
222 [ + + ]: 1002 : for (size_t i = 0; i < 1001; ++i) {
223 [ + - ]: 1001 : CCheckQueueControl<FixedCheck> control(fixed_queue.get());
224 : : size_t remaining = i;
225 [ + + ]: 112649 : while (remaining) {
226 : 111648 : size_t r = m_rng.randrange(10);
227 : :
228 : 111648 : std::vector<FixedCheck> vChecks;
229 [ + - ]: 111648 : vChecks.reserve(r);
230 [ + + ]: 612148 : for (size_t k = 0; k < r && remaining; k++, remaining--)
231 [ + + + - ]: 500500 : vChecks.emplace_back(remaining == 1 ? std::make_optional<int>(17 * i) : std::nullopt);
232 [ + - ]: 223296 : control.Add(std::move(vChecks));
233 : 111648 : }
234 [ + - ]: 1001 : auto result = control.Complete();
235 [ + + ]: 1001 : if (i > 0) {
236 [ + - + - : 2000 : BOOST_REQUIRE(result.has_value() && *result == static_cast<int>(17 * i));
- + + - ]
237 : : } else {
238 [ + - + - ]: 2 : BOOST_REQUIRE(!result.has_value());
239 : : }
240 : 1001 : }
241 : 1 : }
242 : : // Test that a block validation which fails does not interfere with
243 : : // future blocks, ie, the bad state is cleared.
244 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(test_CheckQueue_Recovers_From_Failure)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
245 : : {
246 : 1 : auto fail_queue = std::make_unique<Fixed_Queue>(QUEUE_BATCH_SIZE, SCRIPT_CHECK_THREADS);
247 [ + + ]: 11 : for (auto times = 0; times < 10; ++times) {
248 [ + + ]: 30 : for (const bool end_fails : {true, false}) {
249 [ + - ]: 20 : CCheckQueueControl<FixedCheck> control(fail_queue.get());
250 : 20 : {
251 : 20 : std::vector<FixedCheck> vChecks;
252 [ + - ]: 20 : vChecks.resize(100, FixedCheck(std::nullopt));
253 [ + + + - ]: 20 : vChecks[99] = FixedCheck(end_fails ? std::make_optional<int>(2) : std::nullopt);
254 [ + - ]: 40 : control.Add(std::move(vChecks));
255 : 0 : }
256 [ + - ]: 20 : bool r = !control.Complete().has_value();
257 [ + - + - ]: 40 : BOOST_REQUIRE(r != end_fails);
258 : 20 : }
259 : : }
260 : 1 : }
261 : :
262 : : // Test that unique checks are actually all called individually, rather than
263 : : // just one check being called repeatedly. Test that checks are not called
264 : : // more than once as well
265 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(test_CheckQueue_UniqueCheck)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
266 : : {
267 : 1 : auto queue = std::make_unique<Unique_Queue>(QUEUE_BATCH_SIZE, SCRIPT_CHECK_THREADS);
268 : 1 : size_t COUNT = 100000;
269 : 1 : size_t total = COUNT;
270 : 1 : {
271 [ + - ]: 1 : CCheckQueueControl<UniqueCheck> control(queue.get());
272 [ + + ]: 22241 : while (total) {
273 : 22240 : size_t r = m_rng.randrange(10);
274 : 22240 : std::vector<UniqueCheck> vChecks;
275 [ + + + - ]: 122240 : for (size_t k = 0; k < r && total; k++)
276 [ + - ]: 100000 : vChecks.emplace_back(--total);
277 [ + - ]: 44480 : control.Add(std::move(vChecks));
278 : 22240 : }
279 : 1 : }
280 : 1 : {
281 [ + - ]: 1 : LOCK(UniqueCheck::m);
282 : 1 : bool r = true;
283 [ + - + - ]: 1 : BOOST_REQUIRE_EQUAL(UniqueCheck::results.size(), COUNT);
284 [ + + ]: 100001 : for (size_t i = 0; i < COUNT; ++i) {
285 [ + - - + ]: 200000 : r = r && UniqueCheck::results.count(i) == 1;
286 : : }
287 [ + - + - : 2 : BOOST_REQUIRE(r);
+ - ]
288 : 0 : }
289 : 1 : }
290 : :
291 : :
292 : : // Test that blocks which might allocate lots of memory free their memory aggressively.
293 : : //
294 : : // This test attempts to catch a pathological case where by lazily freeing
295 : : // checks might mean leaving a check un-swapped out, and decreasing by 1 each
296 : : // time could leave the data hanging across a sequence of blocks.
297 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(test_CheckQueue_Memory)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
298 : : {
299 : 1 : auto queue = std::make_unique<Memory_Queue>(QUEUE_BATCH_SIZE, SCRIPT_CHECK_THREADS);
300 [ + + ]: 1001 : for (size_t i = 0; i < 1000; ++i) {
301 : 1000 : size_t total = i;
302 : 1000 : {
303 [ + - ]: 1000 : CCheckQueueControl<MemoryCheck> control(queue.get());
304 [ + + ]: 112440 : while (total) {
305 : 111440 : size_t r = m_rng.randrange(10);
306 : 111440 : std::vector<MemoryCheck> vChecks;
307 [ + + ]: 610940 : for (size_t k = 0; k < r && total; k++) {
308 : 499500 : total--;
309 : : // Each iteration leaves data at the front, back, and middle
310 : : // to catch any sort of deallocation failure
311 [ + + + + : 997003 : vChecks.emplace_back(total == 0 || total == i || total == i/2);
+ - ]
312 : : }
313 [ + - ]: 111440 : control.Add(std::move(vChecks));
314 : 111440 : }
315 : 1000 : }
316 [ + - + - ]: 1000 : BOOST_REQUIRE_EQUAL(MemoryCheck::fake_allocated_memory, 0U);
317 : : }
318 : 1 : }
319 : :
320 : : // Test that a new verification cannot occur until all checks
321 : : // have been destructed
322 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(test_CheckQueue_FrozenCleanup)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
323 : : {
324 : 1 : auto queue = std::make_unique<FrozenCleanup_Queue>(QUEUE_BATCH_SIZE, SCRIPT_CHECK_THREADS);
325 : 1 : bool fails = false;
326 : 2 : std::thread t0([&]() {
327 [ + - ]: 1 : CCheckQueueControl<FrozenCleanupCheck> control(queue.get());
328 [ + - ]: 1 : std::vector<FrozenCleanupCheck> vChecks(1);
329 [ + - ]: 1 : control.Add(std::move(vChecks));
330 [ + - ]: 1 : auto result = control.Complete(); // Hangs here
331 [ - + ]: 1 : assert(!result);
332 [ + - ]: 2 : });
333 : 1 : {
334 [ + - ]: 1 : std::unique_lock<std::mutex> l(FrozenCleanupCheck::m);
335 : : // Wait until the queue has finished all jobs and frozen
336 [ + + ]: 3 : FrozenCleanupCheck::cv.wait(l, [](){return FrozenCleanupCheck::nFrozen == 1;});
337 : 0 : }
338 : : // Try to get control of the queue a bunch of times
339 [ + + ]: 101 : for (auto x = 0; x < 100 && !fails; ++x) {
340 : 100 : fails = queue->m_control_mutex.try_lock();
341 : : }
342 : 1 : {
343 : : // Unfreeze (we need lock n case of spurious wakeup)
344 [ + - ]: 1 : std::unique_lock<std::mutex> l(FrozenCleanupCheck::m);
345 [ + - ]: 1 : FrozenCleanupCheck::nFrozen = 0;
346 : 1 : }
347 : : // Awaken frozen destructor
348 : 1 : FrozenCleanupCheck::cv.notify_one();
349 : : // Wait for control to finish
350 [ + - ]: 1 : t0.join();
351 [ + - + - ]: 2 : BOOST_REQUIRE(!fails);
352 : 1 : }
353 : :
354 : :
355 : : /** Test that CCheckQueueControl is threadsafe */
356 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(test_CheckQueueControl_Locks)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
357 : : {
358 : 1 : auto queue = std::make_unique<Standard_Queue>(QUEUE_BATCH_SIZE, SCRIPT_CHECK_THREADS);
359 : 1 : {
360 : 1 : std::vector<std::thread> tg;
361 [ + - ]: 1 : tg.reserve(3);
362 : 1 : std::atomic<int> nThreads {0};
363 : 1 : std::atomic<int> fails {0};
364 [ + + ]: 4 : for (size_t i = 0; i < 3; ++i) {
365 : 3 : tg.emplace_back(
366 [ + - ]: 6 : [&]{
367 [ + - ]: 3 : CCheckQueueControl<FakeCheck> control(queue.get());
368 : : // While sleeping, no other thread should execute to this point
369 : 3 : auto observed = ++nThreads;
370 [ + - ]: 3 : UninterruptibleSleep(std::chrono::milliseconds{10});
371 : 3 : fails += observed != nThreads;
372 : 3 : });
373 : : }
374 [ + + ]: 4 : for (auto& thread: tg) {
375 [ + - + - ]: 3 : if (thread.joinable()) thread.join();
376 : : }
377 [ + - + - ]: 1 : BOOST_REQUIRE_EQUAL(fails, 0);
378 : 1 : }
379 : 1 : {
380 : 1 : std::vector<std::thread> tg;
381 : 1 : std::mutex m;
382 : 1 : std::condition_variable cv;
383 : 1 : bool has_lock{false};
384 : 1 : bool has_tried{false};
385 : 1 : bool done{false};
386 : 1 : bool done_ack{false};
387 : 1 : {
388 [ + - ]: 1 : std::unique_lock<std::mutex> l(m);
389 [ + - ]: 2 : tg.emplace_back([&]{
390 [ + - ]: 1 : CCheckQueueControl<FakeCheck> control(queue.get());
391 [ + - ]: 1 : std::unique_lock<std::mutex> ll(m);
392 : 1 : has_lock = true;
393 : 1 : cv.notify_one();
394 [ + + ]: 2 : cv.wait(ll, [&]{return has_tried;});
395 : 1 : done = true;
396 : 1 : cv.notify_one();
397 : : // Wait until the done is acknowledged
398 : : //
399 [ + + + - ]: 2 : cv.wait(ll, [&]{return done_ack;});
400 : 1 : });
401 : : // Wait for thread to get the lock
402 [ + + ]: 2 : cv.wait(l, [&](){return has_lock;});
403 : : bool fails = false;
404 [ + + ]: 101 : for (auto x = 0; x < 100 && !fails; ++x) {
405 : 100 : fails = queue->m_control_mutex.try_lock();
406 : : }
407 : 1 : has_tried = true;
408 : 1 : cv.notify_one();
409 [ + + ]: 2 : cv.wait(l, [&](){return done;});
410 : : // Acknowledge the done
411 : 1 : done_ack = true;
412 : 1 : cv.notify_one();
413 [ + - + - : 2 : BOOST_REQUIRE(!fails);
+ - ]
414 : 0 : }
415 [ + + ]: 2 : for (auto& thread: tg) {
416 [ + - + - ]: 1 : if (thread.joinable()) thread.join();
417 : : }
418 : 1 : }
419 : 1 : }
420 : : BOOST_AUTO_TEST_SUITE_END()
|
