checkqueue_tests.cpp raw
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 struct NoLockLoggingTestingSetup : public BasicTestingSetup {
29 NoLockLoggingTestingSetup()
30 #ifdef DEBUG_LOCKCONTENTION
31 : BasicTestingSetup{ChainType::MAIN, {.extra_args = { "-debugexclude=lock" } }} {}
32 #else
33 : BasicTestingSetup{ChainType::MAIN} {}
34 #endif
35 };
36
37 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 std::optional<int> operator()() const
46 {
47 return std::nullopt;
48 }
49 };
50
51 struct FakeCheckCheckCompletion {
52 static std::atomic<size_t> n_calls;
53 std::optional<int> operator()()
54 {
55 n_calls.fetch_add(1, std::memory_order_relaxed);
56 return std::nullopt;
57 }
58 };
59
60 struct FixedCheck
61 {
62 std::optional<int> m_result;
63 FixedCheck(std::optional<int> result) : m_result(result){};
64 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 UniqueCheck(size_t check_id_in) : check_id(check_id_in){};
72 std::optional<int> operator()()
73 {
74 LOCK(m);
75 results.insert(check_id);
76 return std::nullopt;
77 }
78 };
79
80
81 struct MemoryCheck {
82 static std::atomic<size_t> fake_allocated_memory;
83 bool b {false};
84 std::optional<int> operator()() const
85 {
86 return std::nullopt;
87 }
88 MemoryCheck(const MemoryCheck& x)
89 {
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 fake_allocated_memory.fetch_add(b, std::memory_order_relaxed);
95 };
96 MemoryCheck(bool b_) : b(b_)
97 {
98 fake_allocated_memory.fetch_add(b, std::memory_order_relaxed);
99 };
100 ~MemoryCheck()
101 {
102 fake_allocated_memory.fetch_sub(b, std::memory_order_relaxed);
103 };
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 std::optional<int> operator()() const
112 {
113 return std::nullopt;
114 }
115 FrozenCleanupCheck() = default;
116 ~FrozenCleanupCheck()
117 {
118 if (should_freeze) {
119 std::unique_lock<std::mutex> l(m);
120 nFrozen.store(1, std::memory_order_relaxed);
121 cv.notify_one();
122 cv.wait(l, []{ return nFrozen.load(std::memory_order_relaxed) == 0;});
123 }
124 }
125 FrozenCleanupCheck(FrozenCleanupCheck&& other) noexcept
126 {
127 should_freeze = other.should_freeze;
128 other.should_freeze = false;
129 }
130 FrozenCleanupCheck& operator=(FrozenCleanupCheck&& other) noexcept
131 {
132 should_freeze = other.should_freeze;
133 other.should_freeze = false;
134 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 void CheckQueueTest::Correct_Queue_range(std::vector<size_t> range)
160 {
161 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 std::vector<FakeCheckCheckCompletion> vChecks;
164 vChecks.reserve(9);
165 for (const size_t i : range) {
166 size_t total = i;
167 FakeCheckCheckCompletion::n_calls = 0;
168 CCheckQueueControl<FakeCheckCheckCompletion> control(*small_queue);
169 while (total) {
170 vChecks.clear();
171 vChecks.resize(std::min<size_t>(total, m_rng.randrange(10)));
172 total -= vChecks.size();
173 control.Add(std::move(vChecks));
174 }
175 BOOST_REQUIRE(!control.Complete().has_value());
176 BOOST_REQUIRE_EQUAL(FakeCheckCheckCompletion::n_calls, i);
177 }
178 }
179
180 BOOST_FIXTURE_TEST_SUITE(checkqueue_tests, CheckQueueTest)
181
182 /** Test that 0 checks is correct
183 */
184 BOOST_AUTO_TEST_CASE(test_CheckQueue_Correct_Zero)
185 {
186 std::vector<size_t> range;
187 range.push_back(size_t{0});
188 Correct_Queue_range(range);
189 }
190 /** Test that 1 check is correct
191 */
192 BOOST_AUTO_TEST_CASE(test_CheckQueue_Correct_One)
193 {
194 std::vector<size_t> range;
195 range.push_back(size_t{1});
196 Correct_Queue_range(range);
197 }
198 /** Test that MAX check is correct
199 */
200 BOOST_AUTO_TEST_CASE(test_CheckQueue_Correct_Max)
201 {
202 std::vector<size_t> range;
203 range.push_back(100000);
204 Correct_Queue_range(range);
205 }
206 /** Test that random numbers of checks are correct
207 */
208 BOOST_AUTO_TEST_CASE(test_CheckQueue_Correct_Random)
209 {
210 std::vector<size_t> range;
211 range.reserve(100000/1000);
212 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 range.push_back(i);
214 Correct_Queue_range(range);
215 }
216
217
218 /** Test that distinct failing checks are caught */
219 BOOST_AUTO_TEST_CASE(test_CheckQueue_Catches_Failure)
220 {
221 auto fixed_queue = std::make_unique<Fixed_Queue>(QUEUE_BATCH_SIZE, SCRIPT_CHECK_THREADS);
222 for (size_t i = 0; i < 1001; ++i) {
223 CCheckQueueControl<FixedCheck> control(*fixed_queue);
224 size_t remaining = i;
225 while (remaining) {
226 size_t r = m_rng.randrange(10);
227
228 std::vector<FixedCheck> vChecks;
229 vChecks.reserve(r);
230 for (size_t k = 0; k < r && remaining; k++, remaining--)
231 vChecks.emplace_back(remaining == 1 ? std::make_optional<int>(17 * i) : std::nullopt);
232 control.Add(std::move(vChecks));
233 }
234 auto result = control.Complete();
235 if (i > 0) {
236 BOOST_REQUIRE(result.has_value() && *result == static_cast<int>(17 * i));
237 } else {
238 BOOST_REQUIRE(!result.has_value());
239 }
240 }
241 }
242 // Test that a block validation which fails does not interfere with
243 // future blocks, ie, the bad state is cleared.
244 BOOST_AUTO_TEST_CASE(test_CheckQueue_Recovers_From_Failure)
245 {
246 auto fail_queue = std::make_unique<Fixed_Queue>(QUEUE_BATCH_SIZE, SCRIPT_CHECK_THREADS);
247 for (auto times = 0; times < 10; ++times) {
248 for (const bool end_fails : {true, false}) {
249 CCheckQueueControl<FixedCheck> control(*fail_queue);
250 {
251 std::vector<FixedCheck> vChecks;
252 vChecks.resize(100, FixedCheck(std::nullopt));
253 vChecks[99] = FixedCheck(end_fails ? std::make_optional<int>(2) : std::nullopt);
254 control.Add(std::move(vChecks));
255 }
256 bool r = !control.Complete().has_value();
257 BOOST_REQUIRE(r != end_fails);
258 }
259 }
260 }
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 BOOST_AUTO_TEST_CASE(test_CheckQueue_UniqueCheck)
266 {
267 auto queue = std::make_unique<Unique_Queue>(QUEUE_BATCH_SIZE, SCRIPT_CHECK_THREADS);
268 size_t COUNT = 100000;
269 size_t total = COUNT;
270 {
271 CCheckQueueControl<UniqueCheck> control(*queue);
272 while (total) {
273 size_t r = m_rng.randrange(10);
274 std::vector<UniqueCheck> vChecks;
275 for (size_t k = 0; k < r && total; k++)
276 vChecks.emplace_back(--total);
277 control.Add(std::move(vChecks));
278 }
279 }
280 {
281 LOCK(UniqueCheck::m);
282 bool r = true;
283 BOOST_REQUIRE_EQUAL(UniqueCheck::results.size(), COUNT);
284 for (size_t i = 0; i < COUNT; ++i) {
285 r = r && UniqueCheck::results.count(i) == 1;
286 }
287 BOOST_REQUIRE(r);
288 }
289 }
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 BOOST_AUTO_TEST_CASE(test_CheckQueue_Memory)
298 {
299 auto queue = std::make_unique<Memory_Queue>(QUEUE_BATCH_SIZE, SCRIPT_CHECK_THREADS);
300 for (size_t i = 0; i < 1000; ++i) {
301 size_t total = i;
302 {
303 CCheckQueueControl<MemoryCheck> control(*queue);
304 while (total) {
305 size_t r = m_rng.randrange(10);
306 std::vector<MemoryCheck> vChecks;
307 for (size_t k = 0; k < r && total; k++) {
308 total--;
309 // Each iteration leaves data at the front, back, and middle
310 // to catch any sort of deallocation failure
311 vChecks.emplace_back(total == 0 || total == i || total == i/2);
312 }
313 control.Add(std::move(vChecks));
314 }
315 }
316 BOOST_REQUIRE_EQUAL(MemoryCheck::fake_allocated_memory, 0U);
317 }
318 }
319
320 // Test that a new verification cannot occur until all checks
321 // have been destructed
322 BOOST_AUTO_TEST_CASE(test_CheckQueue_FrozenCleanup)
323 {
324 auto queue = std::make_unique<FrozenCleanup_Queue>(QUEUE_BATCH_SIZE, SCRIPT_CHECK_THREADS);
325 bool fails = false;
326 std::thread t0([&]() {
327 CCheckQueueControl<FrozenCleanupCheck> control(*queue);
328 std::vector<FrozenCleanupCheck> vChecks(1);
329 control.Add(std::move(vChecks));
330 auto result = control.Complete(); // Hangs here
331 assert(!result);
332 });
333 {
334 std::unique_lock<std::mutex> l(FrozenCleanupCheck::m);
335 // Wait until the queue has finished all jobs and frozen
336 FrozenCleanupCheck::cv.wait(l, [](){return FrozenCleanupCheck::nFrozen == 1;});
337 }
338 // Try to get control of the queue a bunch of times
339 for (auto x = 0; x < 100 && !fails; ++x) {
340 fails = queue->m_control_mutex.try_lock();
341 }
342 {
343 // Unfreeze (we need lock n case of spurious wakeup)
344 std::unique_lock<std::mutex> l(FrozenCleanupCheck::m);
345 FrozenCleanupCheck::nFrozen = 0;
346 }
347 // Awaken frozen destructor
348 FrozenCleanupCheck::cv.notify_one();
349 // Wait for control to finish
350 t0.join();
351 BOOST_REQUIRE(!fails);
352 }
353
354
355 /** Test that CCheckQueueControl is threadsafe */
356 BOOST_AUTO_TEST_CASE(test_CheckQueueControl_Locks)
357 {
358 auto queue = std::make_unique<Standard_Queue>(QUEUE_BATCH_SIZE, SCRIPT_CHECK_THREADS);
359 {
360 std::vector<std::thread> tg;
361 tg.reserve(3);
362 std::atomic<int> nThreads {0};
363 std::atomic<int> fails {0};
364 for (size_t i = 0; i < 3; ++i) {
365 tg.emplace_back(
366 [&]{
367 CCheckQueueControl<FakeCheck> control(*queue);
368 // While sleeping, no other thread should execute to this point
369 auto observed = ++nThreads;
370 UninterruptibleSleep(std::chrono::milliseconds{10});
371 fails += observed != nThreads;
372 });
373 }
374 for (auto& thread: tg) {
375 if (thread.joinable()) thread.join();
376 }
377 BOOST_REQUIRE_EQUAL(fails, 0);
378 }
379 {
380 std::vector<std::thread> tg;
381 std::mutex m;
382 std::condition_variable cv;
383 bool has_lock{false};
384 bool has_tried{false};
385 bool done{false};
386 bool done_ack{false};
387 {
388 std::unique_lock<std::mutex> l(m);
389 tg.emplace_back([&]{
390 CCheckQueueControl<FakeCheck> control(*queue);
391 std::unique_lock<std::mutex> ll(m);
392 has_lock = true;
393 cv.notify_one();
394 cv.wait(ll, [&]{return has_tried;});
395 done = true;
396 cv.notify_one();
397 // Wait until the done is acknowledged
398 //
399 cv.wait(ll, [&]{return done_ack;});
400 });
401 // Wait for thread to get the lock
402 cv.wait(l, [&](){return has_lock;});
403 bool fails = false;
404 for (auto x = 0; x < 100 && !fails; ++x) {
405 fails = queue->m_control_mutex.try_lock();
406 }
407 has_tried = true;
408 cv.notify_one();
409 cv.wait(l, [&](){return done;});
410 // Acknowledge the done
411 done_ack = true;
412 cv.notify_one();
413 BOOST_REQUIRE(!fails);
414 }
415 for (auto& thread: tg) {
416 if (thread.joinable()) thread.join();
417 }
418 }
419 }
420 BOOST_AUTO_TEST_SUITE_END()
421