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