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