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