Branch data Line data Source code
1 : : // Copyright (c) 2014-2022 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 <vector>
10 : :
11 : : #include <boost/test/unit_test.hpp>
12 : :
13 : : #define SKIPLIST_LENGTH 300000
14 : :
15 : : BOOST_FIXTURE_TEST_SUITE(skiplist_tests, BasicTestingSetup)
16 : :
17 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(skiplist_test)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
18 : : {
19 : 1 : std::vector<CBlockIndex> vIndex(SKIPLIST_LENGTH);
20 : :
21 [ + + ]: 300001 : for (int i=0; i<SKIPLIST_LENGTH; i++) {
22 [ + + ]: 300000 : vIndex[i].nHeight = i;
23 [ + + ]: 300000 : vIndex[i].pprev = (i == 0) ? nullptr : &vIndex[i - 1];
24 [ + - ]: 300000 : vIndex[i].BuildSkip();
25 : : }
26 : :
27 [ + + ]: 300001 : for (int i=0; i<SKIPLIST_LENGTH; i++) {
28 [ + + ]: 300000 : if (i > 0) {
29 [ + - + - : 599998 : BOOST_CHECK(vIndex[i].pskip == &vIndex[vIndex[i].pskip->nHeight]);
+ - ]
30 [ + - + - ]: 599998 : BOOST_CHECK(vIndex[i].pskip->nHeight < i);
31 : : } else {
32 [ + - + - ]: 2 : BOOST_CHECK(vIndex[i].pskip == nullptr);
33 : : }
34 : : }
35 : :
36 [ + + ]: 1001 : for (int i=0; i < 1000; i++) {
37 : 1000 : int from = InsecureRandRange(SKIPLIST_LENGTH - 1);
38 : 1000 : int to = InsecureRandRange(from + 1);
39 : :
40 [ + - + - : 2000 : BOOST_CHECK(vIndex[SKIPLIST_LENGTH - 1].GetAncestor(from) == &vIndex[from]);
+ - + - ]
41 [ + - + - : 2000 : BOOST_CHECK(vIndex[from].GetAncestor(to) == &vIndex[to]);
+ - + - ]
42 [ + - + - : 2000 : BOOST_CHECK(vIndex[from].GetAncestor(0) == vIndex.data());
+ - ]
43 : : }
44 : 1 : }
45 : :
46 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(getlocator_test)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
47 : : {
48 : : // Build a main chain 100000 blocks long.
49 : 1 : std::vector<uint256> vHashMain(100000);
50 [ + - ]: 1 : std::vector<CBlockIndex> vBlocksMain(100000);
51 [ + + ]: 100001 : for (unsigned int i=0; i<vBlocksMain.size(); i++) {
52 [ + - + + ]: 200000 : vHashMain[i] = ArithToUint256(i); // Set the hash equal to the height, so we can quickly check the distances.
53 : 100000 : vBlocksMain[i].nHeight = i;
54 [ + + ]: 100000 : vBlocksMain[i].pprev = i ? &vBlocksMain[i - 1] : nullptr;
55 : 100000 : vBlocksMain[i].phashBlock = &vHashMain[i];
56 [ + - ]: 100000 : vBlocksMain[i].BuildSkip();
57 [ + - + - : 100000 : BOOST_CHECK_EQUAL((int)UintToArith256(vBlocksMain[i].GetBlockHash()).GetLow64(), vBlocksMain[i].nHeight);
+ - ]
58 [ + - + + : 299999 : BOOST_CHECK(vBlocksMain[i].pprev == nullptr || vBlocksMain[i].nHeight == vBlocksMain[i].pprev->nHeight + 1);
+ - + - ]
59 : : }
60 : :
61 : : // Build a branch that splits off at block 49999, 50000 blocks long.
62 [ + - ]: 1 : std::vector<uint256> vHashSide(50000);
63 [ + - ]: 1 : std::vector<CBlockIndex> vBlocksSide(50000);
64 [ + + ]: 50001 : for (unsigned int i=0; i<vBlocksSide.size(); i++) {
65 [ + - + - : 200000 : vHashSide[i] = ArithToUint256(i + 50000 + (arith_uint256(1) << 128)); // Add 1<<128 to the hashes, so GetLow64() still returns the height.
+ + ]
66 : 50000 : vBlocksSide[i].nHeight = i + 50000;
67 [ + + ]: 50000 : vBlocksSide[i].pprev = i ? &vBlocksSide[i - 1] : (vBlocksMain.data()+49999);
68 : 50000 : vBlocksSide[i].phashBlock = &vHashSide[i];
69 [ + - ]: 50000 : vBlocksSide[i].BuildSkip();
70 [ + - + - : 50000 : BOOST_CHECK_EQUAL((int)UintToArith256(vBlocksSide[i].GetBlockHash()).GetLow64(), vBlocksSide[i].nHeight);
+ - ]
71 [ + - + - : 150000 : BOOST_CHECK(vBlocksSide[i].pprev == nullptr || vBlocksSide[i].nHeight == vBlocksSide[i].pprev->nHeight + 1);
+ - + - ]
72 : : }
73 : :
74 : : // Build a CChain for the main branch.
75 : 1 : CChain chain;
76 [ + - ]: 1 : chain.SetTip(vBlocksMain.back());
77 : :
78 : : // Test 100 random starting points for locators.
79 [ + + ]: 101 : for (int n=0; n<100; n++) {
80 : 100 : int r = InsecureRandRange(150000);
81 [ + + ]: 100 : CBlockIndex* tip = (r < 100000) ? &vBlocksMain[r] : &vBlocksSide[r - 100000];
82 [ + - ]: 100 : CBlockLocator locator = GetLocator(tip);
83 : :
84 : : // The first result must be the block itself, the last one must be genesis.
85 [ + - + - : 200 : BOOST_CHECK(locator.vHave.front() == tip->GetBlockHash());
+ - ]
86 [ + - + - ]: 200 : BOOST_CHECK(locator.vHave.back() == vBlocksMain[0].GetBlockHash());
87 : :
88 : : // Entries 1 through 11 (inclusive) go back one step each.
89 [ + + + - ]: 1200 : for (unsigned int i = 1; i < 12 && i < locator.vHave.size() - 1; i++) {
90 [ + - + - : 1100 : BOOST_CHECK_EQUAL(UintToArith256(locator.vHave[i]).GetLow64(), tip->nHeight - i);
+ - ]
91 : : }
92 : :
93 : : // The further ones (excluding the last one) go back with exponential steps.
94 : 100 : unsigned int dist = 2;
95 [ + + ]: 1519 : for (unsigned int i = 12; i < locator.vHave.size() - 1; i++) {
96 [ + - + - : 1419 : BOOST_CHECK_EQUAL(UintToArith256(locator.vHave[i - 1]).GetLow64() - UintToArith256(locator.vHave[i]).GetLow64(), dist);
+ - + - ]
97 : 1419 : dist *= 2;
98 : : }
99 : 100 : }
100 : 1 : }
101 : :
102 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(findearliestatleast_test)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
103 : : {
104 : 1 : std::vector<uint256> vHashMain(100000);
105 [ + - ]: 1 : std::vector<CBlockIndex> vBlocksMain(100000);
106 [ + + ]: 100001 : for (unsigned int i=0; i<vBlocksMain.size(); i++) {
107 [ + - + + ]: 200000 : vHashMain[i] = ArithToUint256(i); // Set the hash equal to the height
108 : 100000 : vBlocksMain[i].nHeight = i;
109 [ + + ]: 100000 : vBlocksMain[i].pprev = i ? &vBlocksMain[i - 1] : nullptr;
110 : 100000 : vBlocksMain[i].phashBlock = &vHashMain[i];
111 [ + - ]: 100000 : vBlocksMain[i].BuildSkip();
112 [ + + ]: 100000 : if (i < 10) {
113 : 10 : vBlocksMain[i].nTime = i;
114 : 10 : vBlocksMain[i].nTimeMax = i;
115 : : } else {
116 : : // randomly choose something in the range [MTP, MTP*2]
117 : 99990 : int64_t medianTimePast = vBlocksMain[i].GetMedianTimePast();
118 : 99990 : int r{int(InsecureRandRange(medianTimePast))};
119 [ + + ]: 99990 : vBlocksMain[i].nTime = uint32_t(r + medianTimePast);
120 [ + + ]: 100133 : vBlocksMain[i].nTimeMax = std::max(vBlocksMain[i].nTime, vBlocksMain[i-1].nTimeMax);
121 : : }
122 : : }
123 : : // Check that we set nTimeMax up correctly.
124 : 1 : unsigned int curTimeMax = 0;
125 [ + + ]: 100001 : for (unsigned int i=0; i<vBlocksMain.size(); ++i) {
126 [ + + ]: 100000 : curTimeMax = std::max(curTimeMax, vBlocksMain[i].nTime);
127 [ + - + - ]: 200000 : BOOST_CHECK(curTimeMax == vBlocksMain[i].nTimeMax);
128 : : }
129 : :
130 : : // Build a CChain for the main branch.
131 : 1 : CChain chain;
132 [ + - ]: 1 : chain.SetTip(vBlocksMain.back());
133 : :
134 : : // Verify that FindEarliestAtLeast is correct.
135 [ + + ]: 10001 : for (unsigned int i=0; i<10000; ++i) {
136 : : // Pick a random element in vBlocksMain.
137 : 10000 : int r = InsecureRandRange(vBlocksMain.size());
138 [ + - ]: 10000 : int64_t test_time = vBlocksMain[r].nTime;
139 [ + - ]: 10000 : CBlockIndex* ret = chain.FindEarliestAtLeast(test_time, 0);
140 [ + - + - : 20000 : BOOST_CHECK(ret->nTimeMax >= test_time);
+ - ]
141 [ + - + + : 20000 : BOOST_CHECK((ret->pprev==nullptr) || ret->pprev->nTimeMax < test_time);
- + + - +
- ]
142 [ + - + - : 20000 : BOOST_CHECK(vBlocksMain[r].GetAncestor(ret->nHeight) == ret);
+ - ]
143 : : }
144 : 1 : }
145 : :
146 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(findearliestatleast_edge_test)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
147 : : {
148 : 1 : std::list<CBlockIndex> blocks;
149 [ + + ]: 10 : for (const unsigned int timeMax : {100, 100, 100, 200, 200, 200, 300, 300, 300}) {
150 [ + + ]: 9 : CBlockIndex* prev = blocks.empty() ? nullptr : &blocks.back();
151 [ + - ]: 9 : blocks.emplace_back();
152 [ + + + - ]: 9 : blocks.back().nHeight = prev ? prev->nHeight + 1 : 0;
153 : 9 : blocks.back().pprev = prev;
154 [ + - ]: 9 : blocks.back().BuildSkip();
155 : 9 : blocks.back().nTimeMax = timeMax;
156 : : }
157 : :
158 : 1 : CChain chain;
159 [ + - ]: 1 : chain.SetTip(blocks.back());
160 : :
161 [ + - + - : 1 : BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(50, 0)->nHeight, 0);
+ - ]
162 [ + - + - : 1 : BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(100, 0)->nHeight, 0);
+ - ]
163 [ + - + - : 1 : BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(150, 0)->nHeight, 3);
+ - ]
164 [ + - + - : 1 : BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(200, 0)->nHeight, 3);
+ - ]
165 [ + - + - : 1 : BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(250, 0)->nHeight, 6);
+ - ]
166 [ + - + - : 1 : BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(300, 0)->nHeight, 6);
+ - ]
167 [ + - + - : 2 : BOOST_CHECK(!chain.FindEarliestAtLeast(350, 0));
+ - + - ]
168 : :
169 [ + - + - : 1 : BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(0, 0)->nHeight, 0);
+ - ]
170 [ + - + - : 1 : BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(-1, 0)->nHeight, 0);
+ - ]
171 : :
172 [ + - + - : 1 : BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(std::numeric_limits<int64_t>::min(), 0)->nHeight, 0);
+ - ]
173 [ + - + - : 1 : BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(-int64_t(std::numeric_limits<unsigned int>::max()) - 1, 0)->nHeight, 0);
+ - ]
174 [ + - + - : 2 : BOOST_CHECK(!chain.FindEarliestAtLeast(std::numeric_limits<int64_t>::max(), 0));
+ - + - ]
175 [ + - + - : 2 : BOOST_CHECK(!chain.FindEarliestAtLeast(std::numeric_limits<unsigned int>::max(), 0));
+ - + - ]
176 [ + - + - : 2 : BOOST_CHECK(!chain.FindEarliestAtLeast(int64_t(std::numeric_limits<unsigned int>::max()) + 1, 0));
+ - + - ]
177 : :
178 [ + - + - : 1 : BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(0, -1)->nHeight, 0);
+ - ]
179 [ + - + - : 1 : BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(0, 0)->nHeight, 0);
+ - ]
180 [ + - + - : 1 : BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(0, 3)->nHeight, 3);
+ - ]
181 [ + - + - : 1 : BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(0, 8)->nHeight, 8);
+ - ]
182 [ + - + - : 2 : BOOST_CHECK(!chain.FindEarliestAtLeast(0, 9));
+ - + - ]
183 : :
184 [ + - ]: 1 : CBlockIndex* ret1 = chain.FindEarliestAtLeast(100, 2);
185 [ + - + - : 2 : BOOST_CHECK(ret1->nTimeMax >= 100 && ret1->nHeight == 2);
- + + - +
- ]
186 [ + - + - : 2 : BOOST_CHECK(!chain.FindEarliestAtLeast(300, 9));
+ - + - ]
187 [ + - ]: 1 : CBlockIndex* ret2 = chain.FindEarliestAtLeast(200, 4);
188 [ + - + - : 2 : BOOST_CHECK(ret2->nTimeMax >= 200 && ret2->nHeight == 4);
- + + - ]
189 : 1 : }
190 : :
191 : : BOOST_AUTO_TEST_SUITE_END()
|
