src/test/checkqueue_tests.cpp

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