src/test/skiplist_tests.cpp

   1 // Copyright (c) 2014-2016 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 <util.h>
   7 #include <test/test_bitcoin.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 = chain.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 = InsecureRandRange(medianTimePast);
 119             vBlocksMain[i].nTime = 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);
 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 (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)->nHeight, 0);
 162     BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(100)->nHeight, 0);
 163     BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(150)->nHeight, 3);
 164     BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(200)->nHeight, 3);
 165     BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(250)->nHeight, 6);
 166     BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(300)->nHeight, 6);
 167     BOOST_CHECK(!chain.FindEarliestAtLeast(350));
 168
 169     BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(0)->nHeight, 0);
 170     BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(-1)->nHeight, 0);
 171
 172     BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(std::numeric_limits<int64_t>::min())->nHeight, 0);
 173     BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(std::numeric_limits<unsigned int>::min())->nHeight, 0);
 174     BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(-int64_t(std::numeric_limits<unsigned int>::max()) - 1)->nHeight, 0);
 175     BOOST_CHECK(!chain.FindEarliestAtLeast(std::numeric_limits<int64_t>::max()));
 176     BOOST_CHECK(!chain.FindEarliestAtLeast(std::numeric_limits<unsigned int>::max()));
 177     BOOST_CHECK(!chain.FindEarliestAtLeast(int64_t(std::numeric_limits<unsigned int>::max()) + 1));
 178 }
 179
 180 BOOST_AUTO_TEST_SUITE_END()