Branch data Line data Source code
1 : : // Copyright (c) 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 <boost/test/unit_test.hpp>
6 : :
7 : : #include <chain.h>
8 : : #include <test/util/setup_common.h>
9 : :
10 : : #include <array>
11 : : #include <memory>
12 : :
13 : : BOOST_FIXTURE_TEST_SUITE(chain_tests, BasicTestingSetup)
14 : :
15 : : namespace {
16 : :
17 : 100000 : const CBlockIndex* NaiveGetAncestor(const CBlockIndex* a, int height)
18 : : {
19 [ + + ]: 6430303 : while (a->nHeight > height) {
20 : 6330303 : a = a->pprev;
21 : : }
22 [ + - ]: 100000 : BOOST_REQUIRE_EQUAL(a->nHeight, height);
23 : 100000 : return a;
24 : : }
25 : :
26 : 100000 : const CBlockIndex* NaiveLastCommonAncestor(const CBlockIndex* a, const CBlockIndex* b)
27 : : {
28 [ + + ]: 3449857 : while (a->nHeight > b->nHeight) {
29 : 3349857 : a = a->pprev;
30 : : }
31 [ + + ]: 3446839 : while (b->nHeight > a->nHeight) {
32 : 3346839 : b = b->pprev;
33 : : }
34 [ + + ]: 5852581 : while (a != b) {
35 [ + - ]: 5752581 : BOOST_REQUIRE_EQUAL(a->nHeight, b->nHeight);
36 : 5752581 : a = a->pprev;
37 : 5752581 : b = b->pprev;
38 : : }
39 [ + - ]: 100000 : BOOST_REQUIRE_EQUAL(a, b);
40 : 100000 : return a;
41 : : }
42 : :
43 : : } // namespace
44 : :
45 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(basic_tests)
+ - + - -
+ + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- ]
46 : : {
47 : : // An empty chain
48 : 1 : const CChain chain_0;
49 : : // A chain with 2 blocks
50 : 1 : CChain chain_2;
51 : :
52 : 1 : CBlockIndex genesis;
53 : 1 : genesis.nHeight = 0;
54 [ + - ]: 1 : chain_2.SetTip(genesis);
55 : :
56 : 1 : CBlockIndex bi1;
57 : 1 : bi1.pprev = &genesis;
58 : 1 : bi1.nHeight = 1;
59 [ + - ]: 1 : chain_2.SetTip(bi1);
60 : :
61 [ + - - + : 1 : BOOST_CHECK_EQUAL(chain_0.Height(), -1);
+ - ]
62 [ + - - + : 1 : BOOST_CHECK_EQUAL(chain_2.Height(), 1);
+ - ]
63 : :
64 [ + - - + : 2 : BOOST_CHECK_EQUAL(chain_0.Tip(), nullptr);
+ - ]
65 [ + - - + : 2 : BOOST_CHECK_EQUAL(chain_2.Tip(), &bi1);
+ - ]
66 : :
67 : : // Indexer accessor: call with valid and invalid (low & high) values
68 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(chain_2[-1], nullptr);
69 [ + - - + : 2 : BOOST_CHECK_EQUAL(chain_2[0], &genesis);
+ - ]
70 [ + - - + : 2 : BOOST_CHECK_EQUAL(chain_2[1], &bi1);
+ - ]
71 [ + - - + : 2 : BOOST_CHECK_EQUAL(chain_2[2], nullptr);
+ - ]
72 : :
73 : : // Contains: call with contained & non-contained blocks
74 [ + - + - : 2 : BOOST_CHECK(chain_2.Contains(genesis));
+ - ]
75 [ + - + - : 2 : BOOST_CHECK(chain_2.Contains(bi1));
+ - ]
76 [ + - + - : 2 : BOOST_CHECK(!chain_0.Contains(genesis));
+ - ]
77 : :
78 : : // Call with non-tip & tip blocks
79 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(chain_2.Next(genesis), &bi1);
80 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(chain_2.Next(bi1), nullptr);
81 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(chain_0.Next(genesis), nullptr);
82 : :
83 [ + - - + : 3 : BOOST_CHECK_EQUAL(chain_2.Genesis(), &genesis);
+ - + - ]
84 [ + - - + : 2 : BOOST_CHECK_EQUAL(chain_0.Genesis(), nullptr);
+ - ]
85 : 1 : }
86 : :
87 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(findfork_tests)
+ - + - -
+ + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- ]
88 : : {
89 : : // Create a forking chain
90 : 1 : const auto init_branch{[](auto& blocks, CBlockIndex* parent, int start_height) {
91 [ + + + + : 28 : for (size_t i{0}; i < blocks.size(); ++i) {
+ + ]
92 [ + + + + : 25 : blocks[i].pprev = i == 0 ? parent : &blocks[i - 1];
+ + ]
93 : 25 : blocks[i].nHeight = start_height + i;
94 : : }
95 : : }};
96 : :
97 : 5 : const auto check_same{[](const CChain& chain, const auto& blocks) {
98 [ + + ]: 39 : for (const auto& block : blocks) {
99 [ + - ]: 35 : BOOST_CHECK_EQUAL(chain.FindFork(block), &block);
100 : : }
101 : 4 : }};
102 : :
103 : 3 : const auto check_fork_point{[](const CChain& chain, const auto& blocks, const CBlockIndex& fork_point) {
104 [ + + ]: 17 : for (const auto& block : blocks) {
105 [ + - ]: 15 : BOOST_CHECK_EQUAL(chain.FindFork(block), &fork_point);
106 : : }
107 : 2 : }};
108 : :
109 [ + + ]: 9 : std::array<CBlockIndex, 10> blocks_common;
110 : 1 : init_branch(blocks_common, nullptr, 0);
111 : :
112 [ + + ]: 9 : std::array<CBlockIndex, 10> blocks_long;
113 : 1 : init_branch(blocks_long, &blocks_common.back(), blocks_common.size());
114 : :
115 [ + + ]: 4 : std::array<CBlockIndex, 5> blocks_short;
116 : 1 : init_branch(blocks_short, &blocks_common.back(), blocks_common.size());
117 : :
118 : : // Create a chain with the longer fork
119 : 1 : CChain chain_long;
120 [ + - ]: 1 : chain_long.SetTip(blocks_long.back());
121 [ + - - + : 1 : BOOST_CHECK_EQUAL(chain_long.Height(), 10 + 10 - 1);
+ - ]
122 : : // Test the blocks in the common part -> result should be the same
123 [ + - ]: 1 : check_same(chain_long, blocks_common);
124 : : // Test the blocks on the longer fork -> result should be the same
125 [ + - ]: 1 : check_same(chain_long, blocks_long);
126 : : // Test the blocks on the other shorter fork -> result should be the fork point
127 [ + - ]: 1 : check_fork_point(chain_long, blocks_short, blocks_common.back());
128 : :
129 : : // Create a chain with the shorter fork
130 : 1 : CChain chain_short;
131 [ + - ]: 1 : chain_short.SetTip(blocks_short.back());
132 [ + - - + : 1 : BOOST_CHECK_EQUAL(chain_short.Height(), 10 + 5 - 1);
+ - ]
133 : : // Test the blocks in the common part -> result should be the same
134 [ + - ]: 1 : check_same(chain_short, blocks_common);
135 : : // Test the blocks on the shorter fork -> result should be the same
136 [ + - ]: 1 : check_same(chain_short, blocks_short);
137 : : // Test the blocks on the other longer fork -> result should be the fork point
138 [ + - ]: 1 : check_fork_point(chain_short, blocks_long, blocks_common.back());
139 : :
140 : : // Invalid test case. Mixing chains is not supported
141 : 1 : CBlockIndex block_on_unrelated_chain;
142 [ + - + - : 1 : BOOST_CHECK_EQUAL(chain_long.FindFork(block_on_unrelated_chain), nullptr);
+ - ]
143 : 1 : }
144 : :
145 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(chain_test)
+ - + - -
+ + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- ]
146 : : {
147 : 1 : FastRandomContext ctx;
148 : 1 : std::vector<std::unique_ptr<CBlockIndex>> block_index;
149 : : // Run 10 iterations of the whole test.
150 [ + + ]: 11 : for (int i = 0; i < 10; ++i) {
151 : 10 : block_index.clear();
152 : : // Create genesis block.
153 [ + - ]: 10 : auto genesis = std::make_unique<CBlockIndex>();
154 [ + - ]: 10 : genesis->nHeight = 0;
155 [ + - ]: 10 : block_index.push_back(std::move(genesis));
156 : : // Create 10000 more blocks.
157 [ + + ]: 100010 : for (int b = 0; b < 10000; ++b) {
158 [ + - ]: 100000 : auto new_index = std::make_unique<CBlockIndex>();
159 : : // 95% of blocks build on top of the last block; the others fork off randomly.
160 [ + + ]: 100000 : if (ctx.randrange(20) != 0) {
161 : 95000 : new_index->pprev = block_index.back().get();
162 : : } else {
163 [ - + ]: 5000 : new_index->pprev = block_index[ctx.randrange(block_index.size())].get();
164 : : }
165 [ + - ]: 100000 : new_index->nHeight = new_index->pprev->nHeight + 1;
166 [ + - ]: 100000 : new_index->BuildSkip();
167 [ + - ]: 100000 : block_index.push_back(std::move(new_index));
168 : 100000 : }
169 : : // Run 10000 random GetAncestor queries.
170 [ + + ]: 100010 : for (int q = 0; q < 10000; ++q) {
171 [ - + ]: 100000 : const CBlockIndex* block = block_index[ctx.randrange(block_index.size())].get();
172 : 100000 : unsigned height = ctx.randrange<unsigned>(block->nHeight + 1);
173 [ + - ]: 100000 : const CBlockIndex* result = block->GetAncestor(height);
174 [ + - + - : 200000 : BOOST_CHECK(result == NaiveGetAncestor(block, height));
+ - ]
175 : : }
176 : : // Run 10000 random LastCommonAncestor queries.
177 [ + + ]: 100010 : for (int q = 0; q < 10000; ++q) {
178 [ - + - + ]: 100000 : const CBlockIndex* block1 = block_index[ctx.randrange(block_index.size())].get();
179 [ - + + - ]: 100000 : const CBlockIndex* block2 = block_index[ctx.randrange(block_index.size())].get();
180 [ + - ]: 100000 : const CBlockIndex* result = LastCommonAncestor(block1, block2);
181 [ + - + - : 200000 : BOOST_CHECK(result == NaiveLastCommonAncestor(block1, block2));
+ - ]
182 : : }
183 : 10 : }
184 : 1 : }
185 : :
186 : : BOOST_AUTO_TEST_SUITE_END()
|
