Branch data     Line data    Source code

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