Branch data Line data Source code
# 1 : : // Copyright (c) 2009-2010 Satoshi Nakamoto
# 2 : : // Copyright (c) 2009-2019 The Bitcoin Core developers
# 3 : : // Distributed under the MIT software license, see the accompanying
# 4 : : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
# 5 : :
# 6 : : #include <chain.h>
# 7 : : #include <util/time.h>
# 8 : :
# 9 : : std::string CBlockFileInfo::ToString() const
# 10 : 948 : {
# 11 : 948 : return strprintf("CBlockFileInfo(blocks=%u, size=%u, heights=%u...%u, time=%s...%s)", nBlocks, nSize, nHeightFirst, nHeightLast, FormatISO8601Date(nTimeFirst), FormatISO8601Date(nTimeLast));
# 12 : 948 : }
# 13 : :
# 14 : 907926 : void CChain::SetTip(CBlockIndex *pindex) {
# 15 [ + + ]: 907926 : if (pindex == nullptr) {
# 16 : 2096 : vChain.clear();
# 17 : 2096 : return;
# 18 : 2096 : }
# 19 : 905830 : vChain.resize(pindex->nHeight + 1);
# 20 [ + + ][ + + ]: 1865255 : while (pindex && vChain[pindex->nHeight] != pindex) {
# 21 : 959425 : vChain[pindex->nHeight] = pindex;
# 22 : 959425 : pindex = pindex->pprev;
# 23 : 959425 : }
# 24 : 905830 : }
# 25 : :
# 26 : 4070 : CBlockLocator CChain::GetLocator(const CBlockIndex *pindex) const {
# 27 : 4070 : int nStep = 1;
# 28 : 4070 : std::vector<uint256> vHave;
# 29 : 4070 : vHave.reserve(32);
# 30 : :
# 31 [ + + ]: 4070 : if (!pindex)
# 32 : 2159 : pindex = Tip();
# 33 [ + + ]: 59587 : while (pindex) {
# 34 : 59583 : vHave.push_back(pindex->GetBlockHash());
# 35 : : // Stop when we have added the genesis block.
# 36 [ + + ]: 59583 : if (pindex->nHeight == 0)
# 37 : 4066 : break;
# 38 : : // Exponentially larger steps back, plus the genesis block.
# 39 : 55517 : int nHeight = std::max(pindex->nHeight - nStep, 0);
# 40 [ + + ]: 55517 : if (Contains(pindex)) {
# 41 : : // Use O(1) CChain index if possible.
# 42 : 51138 : pindex = (*this)[nHeight];
# 43 : 51138 : } else {
# 44 : : // Otherwise, use O(log n) skiplist.
# 45 : 4379 : pindex = pindex->GetAncestor(nHeight);
# 46 : 4379 : }
# 47 [ + + ]: 55517 : if (vHave.size() > 10)
# 48 : 24675 : nStep *= 2;
# 49 : 55517 : }
# 50 : :
# 51 : 4070 : return CBlockLocator(vHave);
# 52 : 4070 : }
# 53 : :
# 54 : 126102 : const CBlockIndex *CChain::FindFork(const CBlockIndex *pindex) const {
# 55 [ + + ]: 126102 : if (pindex == nullptr) {
# 56 : 470 : return nullptr;
# 57 : 470 : }
# 58 [ + + ]: 125632 : if (pindex->nHeight > Height())
# 59 : 63030 : pindex = pindex->GetAncestor(Height());
# 60 [ + + ][ + + ]: 131495 : while (pindex && !Contains(pindex))
# 61 : 5863 : pindex = pindex->pprev;
# 62 : 125632 : return pindex;
# 63 : 126102 : }
# 64 : :
# 65 : : CBlockIndex* CChain::FindEarliestAtLeast(int64_t nTime, int height) const
# 66 : 20862 : {
# 67 : 20862 : std::pair<int64_t, int> blockparams = std::make_pair(nTime, height);
# 68 : 20862 : std::vector<CBlockIndex*>::const_iterator lower = std::lower_bound(vChain.begin(), vChain.end(), blockparams,
# 69 [ + + ][ + + ]: 338403 : [](CBlockIndex* pBlock, const std::pair<int64_t, int>& blockparams) -> bool { return pBlock->GetBlockTimeMax() < blockparams.first || pBlock->nHeight < blockparams.second; });
# 70 [ + + ]: 20862 : return (lower == vChain.end() ? nullptr : *lower);
# 71 : 20862 : }
# 72 : :
# 73 : : /** Turn the lowest '1' bit in the binary representation of a number into a '0'. */
# 74 : 125418850 : int static inline InvertLowestOne(int n) { return n & (n - 1); }
# 75 : :
# 76 : : /** Compute what height to jump back to with the CBlockIndex::pskip pointer. */
# 77 : 83659224 : int static inline GetSkipHeight(int height) {
# 78 [ + + ]: 83659224 : if (height < 2)
# 79 : 45851 : return 0;
# 80 : :
# 81 : : // Determine which height to jump back to. Any number strictly lower than height is acceptable,
# 82 : : // but the following expression seems to perform well in simulations (max 110 steps to go back
# 83 : : // up to 2**18 blocks).
# 84 [ + + ]: 83613373 : return (height & 1) ? InvertLowestOne(InvertLowestOne(height - 1)) + 1 : InvertLowestOne(height);
# 85 : 83659224 : }
# 86 : :
# 87 : : const CBlockIndex* CBlockIndex::GetAncestor(int height) const
# 88 : 10491781 : {
# 89 [ + + ][ + + ]: 10491781 : if (height > nHeight || height < 0) {
# 90 : 883622 : return nullptr;
# 91 : 883622 : }
# 92 : :
# 93 : 9608159 : const CBlockIndex* pindexWalk = this;
# 94 : 9608159 : int heightWalk = nHeight;
# 95 [ + + ]: 47472117 : while (heightWalk > height) {
# 96 : 37863958 : int heightSkip = GetSkipHeight(heightWalk);
# 97 : 37863958 : int heightSkipPrev = GetSkipHeight(heightWalk - 1);
# 98 [ + + ]: 37863958 : if (pindexWalk->pskip != nullptr &&
# 99 [ + + ]: 37863958 : (heightSkip == height ||
# 100 [ + + ][ + + ]: 37863518 : (heightSkip > height && !(heightSkipPrev < heightSkip - 2 &&
# 101 [ + + ]: 19182420 : heightSkipPrev >= height)))) {
# 102 : : // Only follow pskip if pprev->pskip isn't better than pskip->pprev.
# 103 : 19182420 : pindexWalk = pindexWalk->pskip;
# 104 : 19182420 : heightWalk = heightSkip;
# 105 : 19182420 : } else {
# 106 : 18681538 : assert(pindexWalk->pprev);
# 107 : 0 : pindexWalk = pindexWalk->pprev;
# 108 : 18681538 : heightWalk--;
# 109 : 18681538 : }
# 110 : 37863958 : }
# 111 : 9608159 : return pindexWalk;
# 112 : 10491781 : }
# 113 : :
# 114 : : CBlockIndex* CBlockIndex::GetAncestor(int height)
# 115 : 8260049 : {
# 116 : 8260049 : return const_cast<CBlockIndex*>(static_cast<const CBlockIndex*>(this)->GetAncestor(height));
# 117 : 8260049 : }
# 118 : :
# 119 : : void CBlockIndex::BuildSkip()
# 120 : 7931646 : {
# 121 [ + + ]: 7931646 : if (pprev)
# 122 : 7931308 : pskip = pprev->GetAncestor(GetSkipHeight(nHeight));
# 123 : 7931646 : }
# 124 : :
# 125 : : arith_uint256 GetBlockProof(const CBlockIndex& block)
# 126 : 185887 : {
# 127 : 185887 : arith_uint256 bnTarget;
# 128 : 185887 : bool fNegative;
# 129 : 185887 : bool fOverflow;
# 130 : 185887 : bnTarget.SetCompact(block.nBits, &fNegative, &fOverflow);
# 131 [ - + ][ - + ]: 185887 : if (fNegative || fOverflow || bnTarget == 0)
# [ - + ]
# 132 : 0 : return 0;
# 133 : : // We need to compute 2**256 / (bnTarget+1), but we can't represent 2**256
# 134 : : // as it's too large for an arith_uint256. However, as 2**256 is at least as large
# 135 : : // as bnTarget+1, it is equal to ((2**256 - bnTarget - 1) / (bnTarget+1)) + 1,
# 136 : : // or ~bnTarget / (bnTarget+1) + 1.
# 137 : 185887 : return (~bnTarget / (bnTarget + 1)) + 1;
# 138 : 185887 : }
# 139 : :
# 140 : : int64_t GetBlockProofEquivalentTime(const CBlockIndex& to, const CBlockIndex& from, const CBlockIndex& tip, const Consensus::Params& params)
# 141 : 2211 : {
# 142 : 2211 : arith_uint256 r;
# 143 : 2211 : int sign = 1;
# 144 [ + + ]: 2211 : if (to.nChainWork > from.nChainWork) {
# 145 : 1229 : r = to.nChainWork - from.nChainWork;
# 146 : 1229 : } else {
# 147 : 982 : r = from.nChainWork - to.nChainWork;
# 148 : 982 : sign = -1;
# 149 : 982 : }
# 150 : 2211 : r = r * arith_uint256(params.nPowTargetSpacing) / GetBlockProof(tip);
# 151 [ - + ]: 2211 : if (r.bits() > 63) {
# 152 : 0 : return sign * std::numeric_limits<int64_t>::max();
# 153 : 0 : }
# 154 : 2211 : return sign * int64_t(r.GetLow64());
# 155 : 2211 : }
# 156 : :
# 157 : : /** Find the last common ancestor two blocks have.
# 158 : : * Both pa and pb must be non-nullptr. */
# 159 : 148724 : const CBlockIndex* LastCommonAncestor(const CBlockIndex* pa, const CBlockIndex* pb) {
# 160 [ - + ]: 148724 : if (pa->nHeight > pb->nHeight) {
# 161 : 0 : pa = pa->GetAncestor(pb->nHeight);
# 162 [ + + ]: 148724 : } else if (pb->nHeight > pa->nHeight) {
# 163 : 45774 : pb = pb->GetAncestor(pa->nHeight);
# 164 : 45774 : }
# 165 : :
# 166 [ + + ][ + - ]: 151321 : while (pa != pb && pa && pb) {
# [ + - ]
# 167 : 2597 : pa = pa->pprev;
# 168 : 2597 : pb = pb->pprev;
# 169 : 2597 : }
# 170 : :
# 171 : : // Eventually all chain branches meet at the genesis block.
# 172 : 148724 : assert(pa == pb);
# 173 : 0 : return pa;
# 174 : 148724 : }
|
