checkqueue_tests.cpp
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 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 NoLockLoggingTestingSetup() 30 #ifdef DEBUG_LOCKCONTENTION 31 : TestingSetup{ChainType::MAIN, {.extra_args = { "-debugexclude=lock" } }} {} 32 #else 33 : TestingSetup{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()