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