skiplist_tests.cpp
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 <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 = m_rng.randrange(SKIPLIST_LENGTH - 1); 38 int to = m_rng.randrange(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 = m_rng.randrange(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(m_rng.randrange(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 = m_rng.randrange(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 161 BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(50, 0)->nHeight, 0); 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 169 BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(0, 0)->nHeight, 0); 170 BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(-1, 0)->nHeight, 0); 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 178 BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(0, -1)->nHeight, 0); 179 BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(0, 0)->nHeight, 0); 180 BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(0, 3)->nHeight, 3); 181 BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(0, 8)->nHeight, 8); 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 191 BOOST_AUTO_TEST_SUITE_END()