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