Line data    Source code

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