Branch data Line data Source code
1 : : // Copyright (c) 2012-present 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 BasicTestingSetup 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 BasicTestingSetup {
29 : 10 : NoLockLoggingTestingSetup()
30 : : #ifdef DEBUG_LOCKCONTENTION
31 : : : BasicTestingSetup{ChainType::MAIN, {.extra_args = { "-debugexclude=lock" } }} {}
32 : : #else
33 [ + - ]: 20 : : BasicTestingSetup{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 : 11738004 : std::optional<int> operator()()
54 : : {
55 : 11738004 : n_calls.fetch_add(1, std::memory_order_relaxed);
56 : 11738004 : return std::nullopt;
57 : : }
58 : : };
59 : :
60 : : struct FixedCheck
61 : : {
62 : : std::optional<int> m_result;
63 : 500500 : FixedCheck(std::optional<int> result) : m_result(result){};
64 [ + + ]: 135874 : 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 : 1554624 : MemoryCheck(const MemoryCheck& x)
89 : 1554624 : {
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 : 1554624 : 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 : 2054124 : ~MemoryCheck()
101 : : {
102 : 2054124 : fake_allocated_memory.fetch_sub(b, std::memory_order_relaxed);
103 : 2054124 : };
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 [ + + ]: 221 : for (const size_t i : range) {
166 : 217 : size_t total = i;
167 [ + - ]: 217 : FakeCheckCheckCompletion::n_calls = 0;
168 [ + - ]: 217 : CCheckQueueControl<FakeCheckCheckCompletion> control(*small_queue);
169 : 2607445 : while (total) {
170 [ + + ]: 2607228 : vChecks.clear();
171 [ + + + - ]: 2607444 : vChecks.resize(std::min<size_t>(total, m_rng.randrange(10)));
172 [ - + ]: 2607228 : total -= vChecks.size();
173 [ + - + + ]: 5214673 : control.Add(std::move(vChecks));
174 : : }
175 [ + - + - : 434 : BOOST_REQUIRE(!control.Complete().has_value());
+ - + - ]
176 [ + - + - ]: 217 : BOOST_REQUIRE_EQUAL(FakeCheckCheckCompletion::n_calls, i);
177 : 217 : }
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 [ + + + + : 421 : 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 [ + - ]: 214 : 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);
224 : : size_t remaining = i;
225 [ + + ]: 112704 : while (remaining) {
226 : 111703 : size_t r = m_rng.randrange(10);
227 : :
228 : 111703 : std::vector<FixedCheck> vChecks;
229 [ + - ]: 111703 : vChecks.reserve(r);
230 [ + + ]: 612203 : 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 [ + - ]: 223406 : control.Add(std::move(vChecks));
233 : 111703 : }
234 [ + - ]: 1001 : auto result = control.Complete();
235 [ + + ]: 1001 : if (i > 0) {
236 [ + - + - : 2000 : BOOST_REQUIRE(result.has_value());
+ - ]
237 [ + - + - ]: 2000 : BOOST_REQUIRE(*result == static_cast<int>(17 * i));
238 : : } else {
239 [ + - + - ]: 2 : BOOST_REQUIRE(!result.has_value());
240 : : }
241 : 1001 : }
242 : 1 : }
243 : : // Test that a block validation which fails does not interfere with
244 : : // future blocks, ie, the bad state is cleared.
245 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(test_CheckQueue_Recovers_From_Failure)
+ - + - -
+ + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- ]
246 : : {
247 : 1 : auto fail_queue = std::make_unique<Fixed_Queue>(QUEUE_BATCH_SIZE, SCRIPT_CHECK_THREADS);
248 [ + + ]: 11 : for (auto times = 0; times < 10; ++times) {
249 [ + + ]: 30 : for (const bool end_fails : {true, false}) {
250 [ + - ]: 20 : CCheckQueueControl<FixedCheck> control(*fail_queue);
251 : 20 : {
252 : 20 : std::vector<FixedCheck> vChecks;
253 [ + - ]: 20 : vChecks.resize(100, FixedCheck(std::nullopt));
254 [ + + + - ]: 20 : vChecks[99] = FixedCheck(end_fails ? std::make_optional<int>(2) : std::nullopt);
255 [ + - ]: 40 : control.Add(std::move(vChecks));
256 : 0 : }
257 [ + - ]: 20 : bool r = !control.Complete().has_value();
258 [ + - + - ]: 40 : BOOST_REQUIRE(r != end_fails);
259 : 20 : }
260 : : }
261 : 1 : }
262 : :
263 : : // Test that unique checks are actually all called individually, rather than
264 : : // just one check being called repeatedly. Test that checks are not called
265 : : // more than once as well
266 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(test_CheckQueue_UniqueCheck)
+ - + - -
+ + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- ]
267 : : {
268 : 1 : auto queue = std::make_unique<Unique_Queue>(QUEUE_BATCH_SIZE, SCRIPT_CHECK_THREADS);
269 : 1 : size_t COUNT = 100000;
270 : 1 : size_t total = COUNT;
271 : 1 : {
272 [ + - ]: 1 : CCheckQueueControl<UniqueCheck> control(*queue);
273 [ + + ]: 22133 : while (total) {
274 : 22132 : size_t r = m_rng.randrange(10);
275 : 22132 : std::vector<UniqueCheck> vChecks;
276 [ + + + - ]: 122132 : for (size_t k = 0; k < r && total; k++)
277 [ + - ]: 100000 : vChecks.emplace_back(--total);
278 [ + - ]: 44264 : control.Add(std::move(vChecks));
279 : 22132 : }
280 : 1 : }
281 : 1 : {
282 [ + - ]: 1 : LOCK(UniqueCheck::m);
283 : 1 : bool r = true;
284 [ + - + - ]: 1 : BOOST_REQUIRE_EQUAL(UniqueCheck::results.size(), COUNT);
285 [ + + ]: 100001 : for (size_t i = 0; i < COUNT; ++i) {
286 [ + - - + ]: 200000 : r = r && UniqueCheck::results.count(i) == 1;
287 : : }
288 [ + - + - : 2 : BOOST_REQUIRE(r);
+ - ]
289 : 0 : }
290 : 1 : }
291 : :
292 : :
293 : : // Test that blocks which might allocate lots of memory free their memory aggressively.
294 : : //
295 : : // This test attempts to catch a pathological case where by lazily freeing
296 : : // checks might mean leaving a check un-swapped out, and decreasing by 1 each
297 : : // time could leave the data hanging across a sequence of blocks.
298 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(test_CheckQueue_Memory)
+ - + - -
+ + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- ]
299 : : {
300 : 1 : auto queue = std::make_unique<Memory_Queue>(QUEUE_BATCH_SIZE, SCRIPT_CHECK_THREADS);
301 [ + + ]: 1001 : for (size_t i = 0; i < 1000; ++i) {
302 : 1000 : size_t total = i;
303 : 1000 : {
304 [ + - ]: 1000 : CCheckQueueControl<MemoryCheck> control(*queue);
305 [ + + ]: 112480 : while (total) {
306 : 111480 : size_t r = m_rng.randrange(10);
307 : 111480 : std::vector<MemoryCheck> vChecks;
308 [ + + ]: 610980 : for (size_t k = 0; k < r && total; k++) {
309 : 499500 : total--;
310 : : // Each iteration leaves data at the front, back, and middle
311 : : // to catch any sort of deallocation failure
312 [ + + + + : 997003 : vChecks.emplace_back(total == 0 || total == i || total == i/2);
+ - ]
313 : : }
314 [ + - ]: 111480 : control.Add(std::move(vChecks));
315 : 111480 : }
316 : 1000 : }
317 [ + - + - ]: 1000 : BOOST_REQUIRE_EQUAL(MemoryCheck::fake_allocated_memory, 0U);
318 : : }
319 : 1 : }
320 : :
321 : : // Test that a new verification cannot occur until all checks
322 : : // have been destructed
323 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(test_CheckQueue_FrozenCleanup)
+ - + - -
+ + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- ]
324 : : {
325 : 1 : auto queue = std::make_unique<FrozenCleanup_Queue>(QUEUE_BATCH_SIZE, SCRIPT_CHECK_THREADS);
326 : 1 : bool fails = false;
327 : 2 : std::thread t0([&]() {
328 : 1 : CCheckQueueControl<FrozenCleanupCheck> control(*queue);
329 [ + - ]: 1 : std::vector<FrozenCleanupCheck> vChecks(1);
330 [ + - ]: 1 : control.Add(std::move(vChecks));
331 [ + - ]: 1 : auto result = control.Complete(); // Hangs here
332 [ - + ]: 1 : assert(!result);
333 [ + - ]: 2 : });
334 : 1 : {
335 [ + - ]: 1 : std::unique_lock<std::mutex> l(FrozenCleanupCheck::m);
336 : : // Wait until the queue has finished all jobs and frozen
337 [ + + ]: 3 : FrozenCleanupCheck::cv.wait(l, [](){return FrozenCleanupCheck::nFrozen == 1;});
338 : 0 : }
339 : : // Try to get control of the queue a bunch of times
340 [ + + ]: 101 : for (auto x = 0; x < 100 && !fails; ++x) {
341 : 100 : fails = queue->m_control_mutex.try_lock();
342 : : }
343 : 1 : {
344 : : // Unfreeze (we need lock n case of spurious wakeup)
345 [ + - ]: 1 : std::unique_lock<std::mutex> l(FrozenCleanupCheck::m);
346 [ + - ]: 1 : FrozenCleanupCheck::nFrozen = 0;
347 : 1 : }
348 : : // Awaken frozen destructor
349 : 1 : FrozenCleanupCheck::cv.notify_one();
350 : : // Wait for control to finish
351 [ + - ]: 1 : t0.join();
352 [ + - + - ]: 2 : BOOST_REQUIRE(!fails);
353 : 1 : }
354 : :
355 : :
356 : : /** Test that CCheckQueueControl is threadsafe */
357 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(test_CheckQueueControl_Locks)
+ - + - -
+ + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- ]
358 : : {
359 : 1 : auto queue = std::make_unique<Standard_Queue>(QUEUE_BATCH_SIZE, SCRIPT_CHECK_THREADS);
360 : 1 : {
361 : 1 : std::vector<std::thread> tg;
362 [ + - ]: 1 : tg.reserve(3);
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);
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);
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()
|
