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