Bitcoin Core  27.99.0
P2P Digital Currency
skiplist_tests.cpp
Go to the documentation of this file.
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>
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 BOOST_AUTO_TEST_CASE(skiplist_test)
18 {
19  std::vector<CBlockIndex> vIndex(SKIPLIST_LENGTH);
20 
21  for (int i=0; i<SKIPLIST_LENGTH; i++) {
22  vIndex[i].nHeight = i;
23  vIndex[i].pprev = (i == 0) ? nullptr : &vIndex[i - 1];
24  vIndex[i].BuildSkip();
25  }
26 
27  for (int i=0; i<SKIPLIST_LENGTH; i++) {
28  if (i > 0) {
29  BOOST_CHECK(vIndex[i].pskip == &vIndex[vIndex[i].pskip->nHeight]);
30  BOOST_CHECK(vIndex[i].pskip->nHeight < i);
31  } else {
32  BOOST_CHECK(vIndex[i].pskip == nullptr);
33  }
34  }
35 
36  for (int i=0; i < 1000; i++) {
37  int from = InsecureRandRange(SKIPLIST_LENGTH - 1);
38  int to = InsecureRandRange(from + 1);
39 
40  BOOST_CHECK(vIndex[SKIPLIST_LENGTH - 1].GetAncestor(from) == &vIndex[from]);
41  BOOST_CHECK(vIndex[from].GetAncestor(to) == &vIndex[to]);
42  BOOST_CHECK(vIndex[from].GetAncestor(0) == vIndex.data());
43  }
44 }
45 
46 BOOST_AUTO_TEST_CASE(getlocator_test)
47 {
48  // Build a main chain 100000 blocks long.
49  std::vector<uint256> vHashMain(100000);
50  std::vector<CBlockIndex> vBlocksMain(100000);
51  for (unsigned int i=0; i<vBlocksMain.size(); i++) {
52  vHashMain[i] = ArithToUint256(i); // Set the hash equal to the height, so we can quickly check the distances.
53  vBlocksMain[i].nHeight = i;
54  vBlocksMain[i].pprev = i ? &vBlocksMain[i - 1] : nullptr;
55  vBlocksMain[i].phashBlock = &vHashMain[i];
56  vBlocksMain[i].BuildSkip();
57  BOOST_CHECK_EQUAL((int)UintToArith256(vBlocksMain[i].GetBlockHash()).GetLow64(), vBlocksMain[i].nHeight);
58  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  std::vector<uint256> vHashSide(50000);
63  std::vector<CBlockIndex> vBlocksSide(50000);
64  for (unsigned int i=0; i<vBlocksSide.size(); i++) {
65  vHashSide[i] = ArithToUint256(i + 50000 + (arith_uint256(1) << 128)); // Add 1<<128 to the hashes, so GetLow64() still returns the height.
66  vBlocksSide[i].nHeight = i + 50000;
67  vBlocksSide[i].pprev = i ? &vBlocksSide[i - 1] : (vBlocksMain.data()+49999);
68  vBlocksSide[i].phashBlock = &vHashSide[i];
69  vBlocksSide[i].BuildSkip();
70  BOOST_CHECK_EQUAL((int)UintToArith256(vBlocksSide[i].GetBlockHash()).GetLow64(), vBlocksSide[i].nHeight);
71  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  CChain chain;
76  chain.SetTip(vBlocksMain.back());
77 
78  // Test 100 random starting points for locators.
79  for (int n=0; n<100; n++) {
80  int r = InsecureRandRange(150000);
81  CBlockIndex* tip = (r < 100000) ? &vBlocksMain[r] : &vBlocksSide[r - 100000];
82  CBlockLocator locator = GetLocator(tip);
83 
84  // The first result must be the block itself, the last one must be genesis.
85  BOOST_CHECK(locator.vHave.front() == tip->GetBlockHash());
86  BOOST_CHECK(locator.vHave.back() == vBlocksMain[0].GetBlockHash());
87 
88  // Entries 1 through 11 (inclusive) go back one step each.
89  for (unsigned int i = 1; i < 12 && i < locator.vHave.size() - 1; i++) {
90  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  unsigned int dist = 2;
95  for (unsigned int i = 12; i < locator.vHave.size() - 1; i++) {
96  BOOST_CHECK_EQUAL(UintToArith256(locator.vHave[i - 1]).GetLow64() - UintToArith256(locator.vHave[i]).GetLow64(), dist);
97  dist *= 2;
98  }
99  }
100 }
101 
102 BOOST_AUTO_TEST_CASE(findearliestatleast_test)
103 {
104  std::vector<uint256> vHashMain(100000);
105  std::vector<CBlockIndex> vBlocksMain(100000);
106  for (unsigned int i=0; i<vBlocksMain.size(); i++) {
107  vHashMain[i] = ArithToUint256(i); // Set the hash equal to the height
108  vBlocksMain[i].nHeight = i;
109  vBlocksMain[i].pprev = i ? &vBlocksMain[i - 1] : nullptr;
110  vBlocksMain[i].phashBlock = &vHashMain[i];
111  vBlocksMain[i].BuildSkip();
112  if (i < 10) {
113  vBlocksMain[i].nTime = i;
114  vBlocksMain[i].nTimeMax = i;
115  } else {
116  // randomly choose something in the range [MTP, MTP*2]
117  int64_t medianTimePast = vBlocksMain[i].GetMedianTimePast();
118  int r{int(InsecureRandRange(medianTimePast))};
119  vBlocksMain[i].nTime = uint32_t(r + medianTimePast);
120  vBlocksMain[i].nTimeMax = std::max(vBlocksMain[i].nTime, vBlocksMain[i-1].nTimeMax);
121  }
122  }
123  // Check that we set nTimeMax up correctly.
124  unsigned int curTimeMax = 0;
125  for (unsigned int i=0; i<vBlocksMain.size(); ++i) {
126  curTimeMax = std::max(curTimeMax, vBlocksMain[i].nTime);
127  BOOST_CHECK(curTimeMax == vBlocksMain[i].nTimeMax);
128  }
129 
130  // Build a CChain for the main branch.
131  CChain chain;
132  chain.SetTip(vBlocksMain.back());
133 
134  // Verify that FindEarliestAtLeast is correct.
135  for (unsigned int i=0; i<10000; ++i) {
136  // Pick a random element in vBlocksMain.
137  int r = InsecureRandRange(vBlocksMain.size());
138  int64_t test_time = vBlocksMain[r].nTime;
139  CBlockIndex* ret = chain.FindEarliestAtLeast(test_time, 0);
140  BOOST_CHECK(ret->nTimeMax >= test_time);
141  BOOST_CHECK((ret->pprev==nullptr) || ret->pprev->nTimeMax < test_time);
142  BOOST_CHECK(vBlocksMain[r].GetAncestor(ret->nHeight) == ret);
143  }
144 }
145 
146 BOOST_AUTO_TEST_CASE(findearliestatleast_edge_test)
147 {
148  std::list<CBlockIndex> blocks;
149  for (const unsigned int timeMax : {100, 100, 100, 200, 200, 200, 300, 300, 300}) {
150  CBlockIndex* prev = blocks.empty() ? nullptr : &blocks.back();
151  blocks.emplace_back();
152  blocks.back().nHeight = prev ? prev->nHeight + 1 : 0;
153  blocks.back().pprev = prev;
154  blocks.back().BuildSkip();
155  blocks.back().nTimeMax = timeMax;
156  }
157 
158  CChain chain;
159  chain.SetTip(blocks.back());
160 
162  BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(100, 0)->nHeight, 0);
163  BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(150, 0)->nHeight, 3);
164  BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(200, 0)->nHeight, 3);
165  BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(250, 0)->nHeight, 6);
166  BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(300, 0)->nHeight, 6);
167  BOOST_CHECK(!chain.FindEarliestAtLeast(350, 0));
168 
171 
172  BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(std::numeric_limits<int64_t>::min(), 0)->nHeight, 0);
173  BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(-int64_t(std::numeric_limits<unsigned int>::max()) - 1, 0)->nHeight, 0);
174  BOOST_CHECK(!chain.FindEarliestAtLeast(std::numeric_limits<int64_t>::max(), 0));
175  BOOST_CHECK(!chain.FindEarliestAtLeast(std::numeric_limits<unsigned int>::max(), 0));
176  BOOST_CHECK(!chain.FindEarliestAtLeast(int64_t(std::numeric_limits<unsigned int>::max()) + 1, 0));
177 
182  BOOST_CHECK(!chain.FindEarliestAtLeast(0, 9));
183 
184  CBlockIndex* ret1 = chain.FindEarliestAtLeast(100, 2);
185  BOOST_CHECK(ret1->nTimeMax >= 100 && ret1->nHeight == 2);
186  BOOST_CHECK(!chain.FindEarliestAtLeast(300, 9));
187  CBlockIndex* ret2 = chain.FindEarliestAtLeast(200, 4);
188  BOOST_CHECK(ret2->nTimeMax >= 200 && ret2->nHeight == 4);
189 }
190 
arith_uint256 UintToArith256(const uint256 &a)
uint256 ArithToUint256(const arith_uint256 &a)
int ret
CBlockLocator GetLocator(const CBlockIndex *index)
Get a locator for a block index entry.
Definition: chain.cpp:50
The block chain is a tree shaped structure starting with the genesis block at the root,...
Definition: chain.h:141
void BuildSkip()
Build the skiplist pointer for this entry.
Definition: chain.cpp:125
unsigned int nTimeMax
(memory only) Maximum nTime in the chain up to and including this block.
Definition: chain.h:198
uint256 GetBlockHash() const
Definition: chain.h:244
int nHeight
height of the entry in the chain. The genesis block has height 0
Definition: chain.h:153
An in-memory indexed chain of blocks.
Definition: chain.h:418
void SetTip(CBlockIndex &block)
Set/initialize a chain with a given tip.
Definition: chain.cpp:21
CBlockIndex * FindEarliestAtLeast(int64_t nTime, int height) const
Find the earliest block with timestamp equal or greater than the given time and height equal or great...
Definition: chain.cpp:71
256-bit unsigned big integer.
uint64_t GetLow64() const
BOOST_AUTO_TEST_SUITE_END()
unsigned int nHeight
#define BOOST_CHECK_EQUAL(v1, v2)
Definition: object.cpp:18
#define BOOST_CHECK(expr)
Definition: object.cpp:17
#define SKIPLIST_LENGTH
BOOST_AUTO_TEST_CASE(skiplist_test)
Basic testing setup.
Definition: setup_common.h:52
Describes a place in the block chain to another node such that if the other node doesn't have the sam...
Definition: block.h:124
std::vector< uint256 > vHave
Definition: block.h:134
static uint64_t InsecureRandRange(uint64_t range)
Definition: random.h:60