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                 :            : 
#       8                 :            : /**
#       9                 :            :  * CChain implementation
#      10                 :            :  */
#      11                 :     913612 : void CChain::SetTip(CBlockIndex *pindex) {
#      12         [ +  + ]:     913612 :     if (pindex == nullptr) {
#      13                 :        789 :         vChain.clear();
#      14                 :        789 :         return;
#      15                 :        789 :     }
#      16                 :     912823 :     vChain.resize(pindex->nHeight + 1);
#      17 [ +  + ][ +  + ]:    1862662 :     while (pindex && vChain[pindex->nHeight] != pindex) {
#      18                 :     949839 :         vChain[pindex->nHeight] = pindex;
#      19                 :     949839 :         pindex = pindex->pprev;
#      20                 :     949839 :     }
#      21                 :     912823 : }
#      22                 :            : 
#      23                 :       3687 : CBlockLocator CChain::GetLocator(const CBlockIndex *pindex) const {
#      24                 :       3687 :     int nStep = 1;
#      25                 :       3687 :     std::vector<uint256> vHave;
#      26                 :       3687 :     vHave.reserve(32);
#      27                 :            : 
#      28         [ +  + ]:       3687 :     if (!pindex)
#      29                 :       2106 :         pindex = Tip();
#      30         [ +  + ]:      54508 :     while (pindex) {
#      31                 :      54497 :         vHave.push_back(pindex->GetBlockHash());
#      32                 :            :         // Stop when we have added the genesis block.
#      33         [ +  + ]:      54497 :         if (pindex->nHeight == 0)
#      34                 :       3676 :             break;
#      35                 :            :         // Exponentially larger steps back, plus the genesis block.
#      36                 :      50821 :         int nHeight = std::max(pindex->nHeight - nStep, 0);
#      37         [ +  + ]:      50821 :         if (Contains(pindex)) {
#      38                 :            :             // Use O(1) CChain index if possible.
#      39                 :      47041 :             pindex = (*this)[nHeight];
#      40                 :      47041 :         } else {
#      41                 :            :             // Otherwise, use O(log n) skiplist.
#      42                 :       3780 :             pindex = pindex->GetAncestor(nHeight);
#      43                 :       3780 :         }
#      44         [ +  + ]:      50821 :         if (vHave.size() > 10)
#      45                 :      22762 :             nStep *= 2;
#      46                 :      50821 :     }
#      47                 :            : 
#      48                 :       3687 :     return CBlockLocator(vHave);
#      49                 :       3687 : }
#      50                 :            : 
#      51                 :     133710 : const CBlockIndex *CChain::FindFork(const CBlockIndex *pindex) const {
#      52         [ +  + ]:     133710 :     if (pindex == nullptr) {
#      53                 :        404 :         return nullptr;
#      54                 :        404 :     }
#      55         [ +  + ]:     133306 :     if (pindex->nHeight > Height())
#      56                 :      66796 :         pindex = pindex->GetAncestor(Height());
#      57 [ +  + ][ +  + ]:     141477 :     while (pindex && !Contains(pindex))
#      58                 :       8171 :         pindex = pindex->pprev;
#      59                 :     133306 :     return pindex;
#      60                 :     133306 : }
#      61                 :            : 
#      62                 :            : CBlockIndex* CChain::FindEarliestAtLeast(int64_t nTime, int height) const
#      63                 :      20686 : {
#      64                 :      20686 :     std::pair<int64_t, int> blockparams = std::make_pair(nTime, height);
#      65                 :      20686 :     std::vector<CBlockIndex*>::const_iterator lower = std::lower_bound(vChain.begin(), vChain.end(), blockparams,
#      66 [ +  + ][ +  + ]:     333115 :         [](CBlockIndex* pBlock, const std::pair<int64_t, int>& blockparams) -> bool { return pBlock->GetBlockTimeMax() < blockparams.first || pBlock->nHeight < blockparams.second; });
#      67         [ +  + ]:      20686 :     return (lower == vChain.end() ? nullptr : *lower);
#      68                 :      20686 : }
#      69                 :            : 
#      70                 :            : /** Turn the lowest '1' bit in the binary representation of a number into a '0'. */
#      71                 :  132321876 : int static inline InvertLowestOne(int n) { return n & (n - 1); }
#      72                 :            : 
#      73                 :            : /** Compute what height to jump back to with the CBlockIndex::pskip pointer. */
#      74                 :   88256614 : int static inline GetSkipHeight(int height) {
#      75         [ +  + ]:   88256614 :     if (height < 2)
#      76                 :      41448 :         return 0;
#      77                 :            : 
#      78                 :            :     // Determine which height to jump back to. Any number strictly lower than height is acceptable,
#      79                 :            :     // but the following expression seems to perform well in simulations (max 110 steps to go back
#      80                 :            :     // up to 2**18 blocks).
#      81         [ +  + ]:   88215166 :     return (height & 1) ? InvertLowestOne(InvertLowestOne(height - 1)) + 1 : InvertLowestOne(height);
#      82                 :   88215166 : }
#      83                 :            : 
#      84                 :            : const CBlockIndex* CBlockIndex::GetAncestor(int height) const
#      85                 :   10727634 : {
#      86 [ +  + ][ +  + ]:   10727634 :     if (height > nHeight || height < 0) {
#      87                 :     886951 :         return nullptr;
#      88                 :     886951 :     }
#      89                 :            : 
#      90                 :    9840683 :     const CBlockIndex* pindexWalk = this;
#      91                 :    9840683 :     int heightWalk = nHeight;
#      92         [ +  + ]:   50009125 :     while (heightWalk > height) {
#      93                 :   40168442 :         int heightSkip = GetSkipHeight(heightWalk);
#      94                 :   40168442 :         int heightSkipPrev = GetSkipHeight(heightWalk - 1);
#      95         [ +  + ]:   40168442 :         if (pindexWalk->pskip != nullptr &&
#      96         [ +  + ]:   40168442 :             (heightSkip == height ||
#      97 [ +  + ][ +  + ]:   40168027 :              (heightSkip > height && !(heightSkipPrev < heightSkip - 2 &&
#      98         [ +  + ]:   20173745 :                                        heightSkipPrev >= height)))) {
#      99                 :            :             // Only follow pskip if pprev->pskip isn't better than pskip->pprev.
#     100                 :   20173745 :             pindexWalk = pindexWalk->pskip;
#     101                 :   20173745 :             heightWalk = heightSkip;
#     102                 :   20173745 :         } else {
#     103                 :   19994697 :             assert(pindexWalk->pprev);
#     104                 :   19994697 :             pindexWalk = pindexWalk->pprev;
#     105                 :   19994697 :             heightWalk--;
#     106                 :   19994697 :         }
#     107                 :   40168442 :     }
#     108                 :    9840683 :     return pindexWalk;
#     109                 :    9840683 : }
#     110                 :            : 
#     111                 :            : CBlockIndex* CBlockIndex::GetAncestor(int height)
#     112                 :    8266216 : {
#     113                 :    8266216 :     return const_cast<CBlockIndex*>(static_cast<const CBlockIndex*>(this)->GetAncestor(height));
#     114                 :    8266216 : }
#     115                 :            : 
#     116                 :            : void CBlockIndex::BuildSkip()
#     117                 :    7920068 : {
#     118         [ +  + ]:    7920068 :     if (pprev)
#     119                 :    7919730 :         pskip = pprev->GetAncestor(GetSkipHeight(nHeight));
#     120                 :    7920068 : }
#     121                 :            : 
#     122                 :            : arith_uint256 GetBlockProof(const CBlockIndex& block)
#     123                 :     170200 : {
#     124                 :     170200 :     arith_uint256 bnTarget;
#     125                 :     170200 :     bool fNegative;
#     126                 :     170200 :     bool fOverflow;
#     127                 :     170200 :     bnTarget.SetCompact(block.nBits, &fNegative, &fOverflow);
#     128 [ -  + ][ -  + ]:     170200 :     if (fNegative || fOverflow || bnTarget == 0)
#                 [ -  + ]
#     129                 :          0 :         return 0;
#     130                 :            :     // We need to compute 2**256 / (bnTarget+1), but we can't represent 2**256
#     131                 :            :     // as it's too large for an arith_uint256. However, as 2**256 is at least as large
#     132                 :            :     // as bnTarget+1, it is equal to ((2**256 - bnTarget - 1) / (bnTarget+1)) + 1,
#     133                 :            :     // or ~bnTarget / (bnTarget+1) + 1.
#     134                 :     170200 :     return (~bnTarget / (bnTarget + 1)) + 1;
#     135                 :     170200 : }
#     136                 :            : 
#     137                 :            : int64_t GetBlockProofEquivalentTime(const CBlockIndex& to, const CBlockIndex& from, const CBlockIndex& tip, const Consensus::Params& params)
#     138                 :       2210 : {
#     139                 :       2210 :     arith_uint256 r;
#     140                 :       2210 :     int sign = 1;
#     141         [ +  + ]:       2210 :     if (to.nChainWork > from.nChainWork) {
#     142                 :       1284 :         r = to.nChainWork - from.nChainWork;
#     143                 :       1284 :     } else {
#     144                 :        926 :         r = from.nChainWork - to.nChainWork;
#     145                 :        926 :         sign = -1;
#     146                 :        926 :     }
#     147                 :       2210 :     r = r * arith_uint256(params.nPowTargetSpacing) / GetBlockProof(tip);
#     148         [ -  + ]:       2210 :     if (r.bits() > 63) {
#     149                 :          0 :         return sign * std::numeric_limits<int64_t>::max();
#     150                 :          0 :     }
#     151                 :       2210 :     return sign * r.GetLow64();
#     152                 :       2210 : }
#     153                 :            : 
#     154                 :            : /** Find the last common ancestor two blocks have.
#     155                 :            :  *  Both pa and pb must be non-nullptr. */
#     156                 :     201292 : const CBlockIndex* LastCommonAncestor(const CBlockIndex* pa, const CBlockIndex* pb) {
#     157         [ -  + ]:     201292 :     if (pa->nHeight > pb->nHeight) {
#     158                 :          0 :         pa = pa->GetAncestor(pb->nHeight);
#     159         [ +  + ]:     201292 :     } else if (pb->nHeight > pa->nHeight) {
#     160                 :      47540 :         pb = pb->GetAncestor(pa->nHeight);
#     161                 :      47540 :     }
#     162                 :            : 
#     163 [ +  + ][ +  - ]:     204969 :     while (pa != pb && pa && pb) {
#                 [ +  - ]
#     164                 :       3677 :         pa = pa->pprev;
#     165                 :       3677 :         pb = pb->pprev;
#     166                 :       3677 :     }
#     167                 :            : 
#     168                 :            :     // Eventually all chain branches meet at the genesis block.
#     169                 :     201292 :     assert(pa == pb);
#     170                 :     201292 :     return pa;
#     171                 :     201292 : }