Branch data Line data Source code
1 : : // Copyright (c) 2014-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 <chain.h>
6 : : #include <test/util/random.h>
7 : : #include <test/util/setup_common.h>
8 : :
9 : : #include <algorithm>
10 : : #include <vector>
11 : : #include <utility>
12 : :
13 : : #include <boost/test/unit_test.hpp>
14 : :
15 : : #define SKIPLIST_LENGTH 300000
16 : :
17 : : BOOST_FIXTURE_TEST_SUITE(skiplist_tests, BasicTestingSetup)
18 : :
19 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(skiplist_test)
+ - + - -
+ + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- ]
20 : : {
21 : 1 : std::vector<CBlockIndex> vIndex(SKIPLIST_LENGTH);
22 : :
23 [ + + ]: 300001 : for (int i=0; i<SKIPLIST_LENGTH; i++) {
24 [ + + ]: 300000 : vIndex[i].nHeight = i;
25 [ + + ]: 300000 : vIndex[i].pprev = (i == 0) ? nullptr : &vIndex[i - 1];
26 [ + - ]: 300000 : vIndex[i].BuildSkip();
27 : : }
28 : :
29 [ + + ]: 300001 : for (int i=0; i<SKIPLIST_LENGTH; i++) {
30 [ + + ]: 300000 : if (i > 0) {
31 [ + - + - : 599998 : BOOST_CHECK(vIndex[i].pskip == &vIndex[vIndex[i].pskip->nHeight]);
+ - ]
32 [ + - + - ]: 599998 : BOOST_CHECK(vIndex[i].pskip->nHeight < i);
33 : : } else {
34 [ + - + - ]: 300001 : BOOST_CHECK(vIndex[i].pskip == nullptr);
35 : : }
36 : : }
37 : :
38 [ + + ]: 1001 : for (int i=0; i < 1000; i++) {
39 : 1000 : int from = m_rng.randrange(SKIPLIST_LENGTH - 1);
40 : 1000 : int to = m_rng.randrange(from + 1);
41 : :
42 [ + - + - : 2000 : BOOST_CHECK(vIndex[SKIPLIST_LENGTH - 1].GetAncestor(from) == &vIndex[from]);
+ - + - ]
43 [ + - + - : 2000 : BOOST_CHECK(vIndex[from].GetAncestor(to) == &vIndex[to]);
+ - + - ]
44 [ + - + - : 2000 : BOOST_CHECK(vIndex[from].GetAncestor(0) == vIndex.data());
+ - ]
45 : : }
46 : 1 : }
47 : :
48 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(getlocator_test)
+ - + - -
+ + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- ]
49 : : {
50 : : // Build a main chain 100000 blocks long.
51 : 1 : std::vector<uint256> vHashMain(100000);
52 [ + - ]: 1 : std::vector<CBlockIndex> vBlocksMain(100000);
53 [ - + + + ]: 100001 : for (unsigned int i=0; i<vBlocksMain.size(); i++) {
54 [ + - + + ]: 200000 : vHashMain[i] = ArithToUint256(i); // Set the hash equal to the height, so we can quickly check the distances.
55 : 100000 : vBlocksMain[i].nHeight = i;
56 [ + + ]: 100000 : vBlocksMain[i].pprev = i ? &vBlocksMain[i - 1] : nullptr;
57 : 100000 : vBlocksMain[i].phashBlock = &vHashMain[i];
58 [ + - ]: 100000 : vBlocksMain[i].BuildSkip();
59 [ + - + - : 100000 : BOOST_CHECK_EQUAL((int)UintToArith256(vBlocksMain[i].GetBlockHash()).GetLow64(), vBlocksMain[i].nHeight);
+ - ]
60 [ + - + + : 299999 : BOOST_CHECK(vBlocksMain[i].pprev == nullptr || vBlocksMain[i].nHeight == vBlocksMain[i].pprev->nHeight + 1);
+ - + - ]
61 : : }
62 : :
63 : : // Build a branch that splits off at block 49999, 50000 blocks long.
64 [ + - ]: 1 : std::vector<uint256> vHashSide(50000);
65 [ + - ]: 1 : std::vector<CBlockIndex> vBlocksSide(50000);
66 [ - + + + ]: 50001 : for (unsigned int i=0; i<vBlocksSide.size(); i++) {
67 [ + - + - : 100000 : vHashSide[i] = ArithToUint256(i + 50000 + (arith_uint256(1) << 128)); // Add 1<<128 to the hashes, so GetLow64() still returns the height.
+ + ]
68 : 50000 : vBlocksSide[i].nHeight = i + 50000;
69 [ + + ]: 50000 : vBlocksSide[i].pprev = i ? &vBlocksSide[i - 1] : (vBlocksMain.data()+49999);
70 : 50000 : vBlocksSide[i].phashBlock = &vHashSide[i];
71 [ + - ]: 50000 : vBlocksSide[i].BuildSkip();
72 [ + - + - : 50000 : BOOST_CHECK_EQUAL((int)UintToArith256(vBlocksSide[i].GetBlockHash()).GetLow64(), vBlocksSide[i].nHeight);
+ - ]
73 [ + - + - : 150000 : BOOST_CHECK(vBlocksSide[i].pprev == nullptr || vBlocksSide[i].nHeight == vBlocksSide[i].pprev->nHeight + 1);
+ - + - ]
74 : : }
75 : :
76 : : // Build a CChain for the main branch.
77 : 1 : CChain chain;
78 [ + - ]: 1 : chain.SetTip(vBlocksMain.back());
79 : :
80 : : // Test 100 random starting points for locators.
81 [ + + ]: 101 : for (int n=0; n<100; n++) {
82 : 100 : int r = m_rng.randrange(150000);
83 [ + + ]: 100 : CBlockIndex* tip = (r < 100000) ? &vBlocksMain[r] : &vBlocksSide[r - 100000];
84 [ + - ]: 100 : CBlockLocator locator = GetLocator(tip);
85 : :
86 : : // The first result must be the block itself, the last one must be genesis.
87 [ + - + - : 200 : BOOST_CHECK(locator.vHave.front() == tip->GetBlockHash());
+ - ]
88 [ + - + - ]: 200 : BOOST_CHECK(locator.vHave.back() == vBlocksMain[0].GetBlockHash());
89 : :
90 : : // Entries 1 through 11 (inclusive) go back one step each.
91 [ + + - + : 1200 : for (unsigned int i = 1; i < 12 && i < locator.vHave.size() - 1; i++) {
+ - ]
92 [ + - + - : 1100 : BOOST_CHECK_EQUAL(UintToArith256(locator.vHave[i]).GetLow64(), tip->nHeight - i);
+ - ]
93 : : }
94 : :
95 : : // The further ones (excluding the last one) go back with exponential steps.
96 : 100 : unsigned int dist = 2;
97 [ - + + + ]: 1510 : for (unsigned int i = 12; i < locator.vHave.size() - 1; i++) {
98 [ + - + - : 1410 : BOOST_CHECK_EQUAL(UintToArith256(locator.vHave[i - 1]).GetLow64() - UintToArith256(locator.vHave[i]).GetLow64(), dist);
+ - + - ]
99 : 1410 : dist *= 2;
100 : : }
101 : 100 : }
102 : 1 : }
103 : :
104 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(findearliestatleast_test)
+ - + - -
+ + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- ]
105 : : {
106 : 1 : std::vector<uint256> vHashMain(100000);
107 [ + - ]: 1 : std::vector<CBlockIndex> vBlocksMain(100000);
108 [ - + + + ]: 100001 : for (unsigned int i=0; i<vBlocksMain.size(); i++) {
109 [ + - + + ]: 200000 : vHashMain[i] = ArithToUint256(i); // Set the hash equal to the height
110 : 100000 : vBlocksMain[i].nHeight = i;
111 [ + + ]: 100000 : vBlocksMain[i].pprev = i ? &vBlocksMain[i - 1] : nullptr;
112 : 100000 : vBlocksMain[i].phashBlock = &vHashMain[i];
113 [ + - ]: 100000 : vBlocksMain[i].BuildSkip();
114 [ + + ]: 100000 : if (i < 10) {
115 : 10 : vBlocksMain[i].nTime = i;
116 : 10 : vBlocksMain[i].nTimeMax = i;
117 : : } else {
118 : : // randomly choose something in the range [MTP, MTP*2]
119 : 99990 : int64_t medianTimePast = vBlocksMain[i].GetMedianTimePast();
120 : 99990 : int r{int(m_rng.randrange(medianTimePast))};
121 [ + + ]: 99990 : vBlocksMain[i].nTime = uint32_t(r + medianTimePast);
122 [ + + ]: 100125 : vBlocksMain[i].nTimeMax = std::max(vBlocksMain[i].nTime, vBlocksMain[i-1].nTimeMax);
123 : : }
124 : : }
125 : : // Check that we set nTimeMax up correctly.
126 : 1 : unsigned int curTimeMax = 0;
127 [ - + + + ]: 100001 : for (unsigned int i=0; i<vBlocksMain.size(); ++i) {
128 [ + + ]: 100000 : curTimeMax = std::max(curTimeMax, vBlocksMain[i].nTime);
129 [ + - + - ]: 200000 : BOOST_CHECK(curTimeMax == vBlocksMain[i].nTimeMax);
130 : : }
131 : :
132 : : // Build a CChain for the main branch.
133 : 1 : CChain chain;
134 [ + - ]: 1 : chain.SetTip(vBlocksMain.back());
135 : :
136 : : // Verify that FindEarliestAtLeast is correct.
137 [ + + ]: 10001 : for (unsigned int i=0; i<10000; ++i) {
138 : : // Pick a random element in vBlocksMain.
139 [ - + ]: 10000 : int r = m_rng.randrange(vBlocksMain.size());
140 [ + - ]: 10000 : int64_t test_time = vBlocksMain[r].nTime;
141 [ + - ]: 10000 : CBlockIndex* ret = chain.FindEarliestAtLeast(test_time, 0);
142 [ + - + - : 20000 : BOOST_CHECK(ret->nTimeMax >= test_time);
+ - ]
143 [ + - + - : 20000 : BOOST_CHECK((ret->pprev==nullptr) || ret->pprev->nTimeMax < test_time);
- + + - +
- ]
144 [ + - + - : 20000 : BOOST_CHECK(vBlocksMain[r].GetAncestor(ret->nHeight) == ret);
+ - ]
145 : : }
146 : 1 : }
147 : :
148 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(findearliestatleast_edge_test)
+ - + - -
+ + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- ]
149 : : {
150 : 1 : std::list<CBlockIndex> blocks;
151 [ + + ]: 10 : for (const unsigned int timeMax : {100, 100, 100, 200, 200, 200, 300, 300, 300}) {
152 [ + + ]: 9 : CBlockIndex* prev = blocks.empty() ? nullptr : &blocks.back();
153 [ + - ]: 9 : blocks.emplace_back();
154 [ + + + - ]: 9 : blocks.back().nHeight = prev ? prev->nHeight + 1 : 0;
155 : 9 : blocks.back().pprev = prev;
156 [ + - ]: 9 : blocks.back().BuildSkip();
157 : 9 : blocks.back().nTimeMax = timeMax;
158 : : }
159 : :
160 : 1 : CChain chain;
161 [ + - ]: 1 : chain.SetTip(blocks.back());
162 : :
163 [ + - + - : 1 : BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(50, 0)->nHeight, 0);
+ - ]
164 [ + - + - : 1 : BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(100, 0)->nHeight, 0);
+ - ]
165 [ + - + - : 1 : BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(150, 0)->nHeight, 3);
+ - ]
166 [ + - + - : 1 : BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(200, 0)->nHeight, 3);
+ - ]
167 [ + - + - : 1 : BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(250, 0)->nHeight, 6);
+ - ]
168 [ + - + - : 1 : BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(300, 0)->nHeight, 6);
+ - ]
169 [ + - + - : 2 : BOOST_CHECK(!chain.FindEarliestAtLeast(350, 0));
+ - + - ]
170 : :
171 [ + - + - : 1 : BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(0, 0)->nHeight, 0);
+ - ]
172 [ + - + - : 1 : BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(-1, 0)->nHeight, 0);
+ - ]
173 : :
174 [ + - + - : 1 : BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(std::numeric_limits<int64_t>::min(), 0)->nHeight, 0);
+ - ]
175 [ + - + - : 1 : BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(-int64_t(std::numeric_limits<unsigned int>::max()) - 1, 0)->nHeight, 0);
+ - ]
176 [ + - + - : 2 : BOOST_CHECK(!chain.FindEarliestAtLeast(std::numeric_limits<int64_t>::max(), 0));
+ - + - ]
177 [ + - + - : 2 : BOOST_CHECK(!chain.FindEarliestAtLeast(std::numeric_limits<unsigned int>::max(), 0));
+ - + - ]
178 [ + - + - : 2 : BOOST_CHECK(!chain.FindEarliestAtLeast(int64_t(std::numeric_limits<unsigned int>::max()) + 1, 0));
+ - + - ]
179 : :
180 [ + - + - : 1 : BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(0, -1)->nHeight, 0);
+ - ]
181 [ + - + - : 1 : BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(0, 0)->nHeight, 0);
+ - ]
182 [ + - + - : 1 : BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(0, 3)->nHeight, 3);
+ - ]
183 [ + - + - : 1 : BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(0, 8)->nHeight, 8);
+ - ]
184 [ + - + - : 2 : BOOST_CHECK(!chain.FindEarliestAtLeast(0, 9));
+ - + - ]
185 : :
186 [ + - ]: 1 : CBlockIndex* ret1 = chain.FindEarliestAtLeast(100, 2);
187 [ + - + - : 2 : BOOST_CHECK(ret1->nTimeMax >= 100 && ret1->nHeight == 2);
- + + - +
- ]
188 [ + - + - : 2 : BOOST_CHECK(!chain.FindEarliestAtLeast(300, 9));
+ - + - ]
189 [ + - ]: 1 : CBlockIndex* ret2 = chain.FindEarliestAtLeast(200, 4);
190 [ + - + - : 2 : BOOST_CHECK(ret2->nTimeMax >= 200 && ret2->nHeight == 4);
- + + - ]
191 : 1 : }
192 : :
193 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(build_skip_height_test)
+ - + - -
+ + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- ]
194 : : {
195 : : // clang-format off
196 : 1 : const std::pair<int, int> TEST_DATA[]{
197 : : // EVEN values: the rightmost set bit is zeroed
198 : : // Various even values with at least 2 bits set
199 : : { 0b00010010 ,
200 : : 0b00010000 },
201 : : { 0b00100010 ,
202 : : 0b00100000 },
203 : : { 0b01000010 ,
204 : : 0b01000000 },
205 : : { 0b00010100 ,
206 : : 0b00010000 },
207 : : { 0b00011000 ,
208 : : 0b00010000 },
209 : : { 0b10101010 ,
210 : : 0b10101000 },
211 : : // ODD values: the 2nd and 3rd set bits are zeroed
212 : : // Various odd values with at least 4 bits set
213 : : { 0b10010011 ,
214 : : 0b10000001 },
215 : : { 0b10100011 ,
216 : : 0b10000001 },
217 : : { 0b11000011 ,
218 : : 0b10000001 },
219 : : { 0b10010101 ,
220 : : 0b10000001 },
221 : : { 0b10011001 ,
222 : : 0b10000001 },
223 : : { 0b10101011 ,
224 : : 0b10100001 },
225 : : // Some longer random values (even and odd)
226 : : { 0b0001011101101000 ,
227 : : 0b0001011101100000 },
228 : : { 0b0001011101101001 ,
229 : : 0b0001011101000001 },
230 : : { 0b0110101101011000 ,
231 : : 0b0110101101010000 },
232 : : { 0b0110101101011001 ,
233 : : 0b0110101101000001 },
234 : : // All values 1-20
235 : : { 1, 0 },
236 : : { 2, 0 },
237 : : { 3, 1 },
238 : : { 4, 0 },
239 : : { 5, 1 },
240 : : { 6, 4 },
241 : : { 7, 1 },
242 : : { 8, 0 },
243 : : { 9, 1 },
244 : : { 10, 8 },
245 : : { 11, 1 },
246 : : { 12, 8 },
247 : : { 13, 1 },
248 : : { 14, 12 },
249 : : { 15, 9 },
250 : : { 16, 0 },
251 : : { 17, 1 },
252 : : { 18, 16 },
253 : : { 19, 1 },
254 : : { 20, 16 },
255 : : };
256 : : // clang-format on
257 : :
258 : : // Test `CBlockIndex::BuildSkip()` and that the skip height conforms to expected logic.
259 : : // It tests that:
260 : : // - `pprev` field is set (to an earlier block index),
261 : : // - the skip is to the index as dictated by the `GetSkipHeight()` bit-manipulation logic,
262 : : // - `GetAncestor()` works as expected (indirectly).
263 : :
264 : : // Build a chain (up to the highest test input value)
265 [ + + ]: 36 : const auto max_test_input{std::ranges::max_element(TEST_DATA, [](auto& a, auto& b) { return a.first < b.first; })};
266 : 1 : const int chain_size{max_test_input->first + 1};
267 : 1 : std::vector<CBlockIndex> block_index(chain_size);
268 [ + + ]: 27483 : for (auto i{0}; i < chain_size; ++i) {
269 : : // pprev and nHeight are used by BuildSkip()
270 [ + + + - ]: 27482 : block_index[i].pprev = i == 0 ? nullptr : &block_index[i - 1];
271 : 27482 : block_index[i].nHeight = i;
272 [ + - ]: 27482 : block_index[i].BuildSkip();
273 [ + - + + : 54964 : BOOST_CHECK(block_index[i].pskip || i == 0);
- + + - ]
274 : : }
275 : :
276 [ + - + + ]: 37 : for (auto& [input, expected] : TEST_DATA) {
277 [ + - + - ]: 36 : BOOST_REQUIRE_LT(input, chain_size);
278 [ + - + - ]: 36 : BOOST_REQUIRE_GT(input, 0);
279 [ + - + - ]: 36 : BOOST_REQUIRE_LT(expected, input);
280 [ + - + - : 72 : BOOST_REQUIRE(block_index[input].pskip);
+ - ]
281 : :
282 [ + - ]: 36 : const int skip_height{block_index[input].pskip->nHeight};
283 [ + - + - ]: 36 : BOOST_CHECK_EQUAL(skip_height, expected);
284 : : }
285 : :
286 : : // Special value: height 0 (genesis) has no skip
287 [ + - + - ]: 2 : BOOST_CHECK(!block_index[0].pskip);
288 : 1 : }
289 : :
290 : : BOOST_AUTO_TEST_SUITE_END()
|
