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