Inside Bitcoin

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 BasicTestingSetup 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 */
28struct NoLockLoggingTestingSetup : public BasicTestingSetup {
29    NoLockLoggingTestingSetup()
30#ifdef DEBUG_LOCKCONTENTION
31        : BasicTestingSetup{ChainType::MAIN, {.extra_args = { "-debugexclude=lock" } }} {}
32#else
33        : BasicTestingSetup{ChainType::MAIN} {}
34#endif
35};
36
37struct CheckQueueTest : NoLockLoggingTestingSetup {
38    void Correct_Queue_range(std::vector<size_t> range);
39};
40
41static const unsigned int QUEUE_BATCH_SIZE = 128;
42static const int SCRIPT_CHECK_THREADS = 3;
43
44struct FakeCheck {
45    std::optional<int> operator()() const
46    {
47        return std::nullopt;
48    }
49};
50
51struct 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
60struct 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
67struct 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
81struct 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
106struct 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
139std::mutex FrozenCleanupCheck::m{};
140std::atomic<uint64_t> FrozenCleanupCheck::nFrozen{0};
141std::condition_variable FrozenCleanupCheck::cv{};
142Mutex UniqueCheck::m;
143std::unordered_multiset<size_t> UniqueCheck::results;
144std::atomic<size_t> FakeCheckCheckCompletion::n_calls{0};
145std::atomic<size_t> MemoryCheck::fake_allocated_memory{0};
146
147// Queue Typedefs
148typedef CCheckQueue<FakeCheckCheckCompletion> Correct_Queue;
149typedef CCheckQueue<FakeCheck> Standard_Queue;
150typedef CCheckQueue<FixedCheck> Fixed_Queue;
151typedef CCheckQueue<UniqueCheck> Unique_Queue;
152typedef CCheckQueue<MemoryCheck> Memory_Queue;
153typedef 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 */
159void 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
180BOOST_FIXTURE_TEST_SUITE(checkqueue_tests, CheckQueueTest)
181
182/** Test that 0 checks is correct
183 */
184BOOST_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 */
192BOOST_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 */
200BOOST_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 */
208BOOST_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 */
219BOOST_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());
237            BOOST_REQUIRE(*result == static_cast<int>(17 * i));
238        } else {
239            BOOST_REQUIRE(!result.has_value());
240        }
241    }
242}
243// Test that a block validation which fails does not interfere with
244// future blocks, ie, the bad state is cleared.
245BOOST_AUTO_TEST_CASE(test_CheckQueue_Recovers_From_Failure)
246{
247    auto fail_queue = std::make_unique<Fixed_Queue>(QUEUE_BATCH_SIZE, SCRIPT_CHECK_THREADS);
248    for (auto times = 0; times < 10; ++times) {
249        for (const bool end_fails : {true, false}) {
250            CCheckQueueControl<FixedCheck> control(*fail_queue);