LCOV - code coverage report
Current view: top level - src - txorphanage.cpp (source / functions) Hit Total Coverage
Test: fuzz_coverage.info Lines: 120 143 83.9 %
Date: 2023-02-03 05:16:22 Functions: 13 14 92.9 %
Branches: 95 210 45.2 %

           Branch data     Line data    Source code
       1                 :            : // Copyright (c) 2021-2022 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 <txorphanage.h>
       6                 :            : 
       7                 :            : #include <consensus/validation.h>
       8                 :            : #include <logging.h>
       9                 :            : #include <policy/policy.h>
      10                 :            : 
      11                 :            : #include <cassert>
      12                 :            : 
      13                 :            : /** Expiration time for orphan transactions in seconds */
      14                 :            : static constexpr int64_t ORPHAN_TX_EXPIRE_TIME = 20 * 60;
      15                 :            : /** Minimum time between orphan transactions expire time checks in seconds */
      16                 :            : static constexpr int64_t ORPHAN_TX_EXPIRE_INTERVAL = 5 * 60;
      17         [ +  - ]:        190 : 
      18         [ +  - ]:        190 : 
      19                 :      98210 : bool TxOrphanage::AddTx(const CTransactionRef& tx, NodeId peer)
      20                 :            : {
      21                 :      98210 :     LOCK(m_mutex);
      22                 :            : 
      23         [ +  - ]:      98210 :     const uint256& hash = tx->GetHash();
      24   [ +  -  +  + ]:      98210 :     if (m_orphans.count(hash))
      25                 :      22506 :         return false;
      26                 :            : 
      27                 :            :     // Ignore big transactions, to avoid a
      28                 :            :     // send-big-orphans memory exhaustion attack. If a peer has a legitimate
      29                 :            :     // large transaction with a missing parent then we assume
      30                 :            :     // it will rebroadcast it later, after the parent transaction(s)
      31                 :            :     // have been mined or received.
      32                 :            :     // 100 orphans, each of which is at most 100,000 bytes big is
      33                 :            :     // at most 10 megabytes of orphans and somewhat more byprev index (in the worst case):
      34         [ +  - ]:      75704 :     unsigned int sz = GetTransactionWeight(*tx);
      35         [ +  + ]:      75704 :     if (sz > MAX_STANDARD_TX_WEIGHT)
      36                 :            :     {
      37   [ +  -  +  -  :       3694 :         LogPrint(BCLog::MEMPOOL, "ignoring large orphan tx (size: %u, hash: %s)\n", sz, hash.ToString());
          #  #  #  #  #  
                #  #  # ]
      38                 :       3694 :         return false;
      39                 :            :     }
      40                 :            : 
      41   [ +  -  +  - ]:      72010 :     auto ret = m_orphans.emplace(hash, OrphanTx{tx, peer, GetTime() + ORPHAN_TX_EXPIRE_TIME, m_orphan_list.size()});
      42         [ +  - ]:      72010 :     assert(ret.second);
      43         [ +  - ]:      72010 :     m_orphan_list.push_back(ret.first);
      44                 :            :     // Allow for lookups in the orphan pool by wtxid, as well as txid
      45   [ +  -  +  - ]:      72010 :     m_wtxid_to_orphan_it.emplace(tx->GetWitnessHash(), ret.first);
      46         [ +  + ]:    2425601 :     for (const CTxIn& txin : tx->vin) {
      47   [ +  -  +  - ]:    2353591 :         m_outpoint_to_orphan_it[txin.prevout].insert(ret.first);
      48                 :            :     }
      49                 :            : 
      50   [ +  -  +  -  :      72010 :     LogPrint(BCLog::MEMPOOL, "stored orphan tx %s (mapsz %u outsz %u)\n", hash.ToString(),
          #  #  #  #  #  
                #  #  # ]
      51                 :            :              m_orphans.size(), m_outpoint_to_orphan_it.size());
      52                 :      72010 :     return true;
      53                 :      98210 : }
      54                 :            : 
      55                 :      71564 : int TxOrphanage::EraseTx(const uint256& txid)
      56                 :            : {
      57                 :      71564 :     LOCK(m_mutex);
      58         [ +  - ]:      71564 :     return _EraseTx(txid);
      59                 :      71564 : }
      60                 :            : 
      61                 :     133183 : int TxOrphanage::_EraseTx(const uint256& txid)
      62                 :            : {
      63                 :     133183 :     AssertLockHeld(m_mutex);
      64                 :     133183 :     std::map<uint256, OrphanTx>::iterator it = m_orphans.find(txid);
      65         [ +  + ]:     133183 :     if (it == m_orphans.end())
      66                 :      65000 :         return 0;
      67         [ +  + ]:    2270069 :     for (const CTxIn& txin : it->second.tx->vin)
      68                 :            :     {
      69                 :    2201886 :         auto itPrev = m_outpoint_to_orphan_it.find(txin.prevout);
      70         [ +  + ]:    2201886 :         if (itPrev == m_outpoint_to_orphan_it.end())
      71                 :     154220 :             continue;
      72                 :    2047666 :         itPrev->second.erase(it);
      73         [ +  + ]:    2047666 :         if (itPrev->second.empty())
      74                 :    1368495 :             m_outpoint_to_orphan_it.erase(itPrev);
      75                 :            :     }
      76                 :            : 
      77                 :      68183 :     size_t old_pos = it->second.list_pos;
      78         [ +  - ]:      68183 :     assert(m_orphan_list[old_pos] == it);
      79   [ +  -  +  + ]:      68373 :     if (old_pos + 1 != m_orphan_list.size()) {
      80                 :            :         // Unless we're deleting the last entry in m_orphan_list, move the last
      81                 :            :         // entry to the position we're deleting.
      82                 :      51595 :         auto it_last = m_orphan_list.back();
      83                 :      51595 :         m_orphan_list[old_pos] = it_last;
      84                 :      51595 :         it_last->second.list_pos = old_pos;
      85                 :      51595 :     }
      86                 :      68183 :     m_orphan_list.pop_back();
      87                 :      68183 :     m_wtxid_to_orphan_it.erase(it->second.tx->GetWitnessHash());
      88                 :            : 
      89                 :      68183 :     m_orphans.erase(it);
      90                 :      68183 :     return 1;
      91                 :     133183 : }
      92                 :            : 
      93                 :     151240 : void TxOrphanage::EraseForPeer(NodeId peer)
      94                 :            : {
      95                 :     151240 :     LOCK(m_mutex);
      96                 :            : 
      97         [ +  - ]:     151240 :     m_peer_work_set.erase(peer);
      98                 :            : 
      99                 :     151240 :     int nErased = 0;
     100                 :     151240 :     std::map<uint256, OrphanTx>::iterator iter = m_orphans.begin();
     101         [ +  + ]:     261887 :     while (iter != m_orphans.end())
     102                 :            :     {
     103                 :     110647 :         std::map<uint256, OrphanTx>::iterator maybeErase = iter++; // increment to avoid iterator becoming invalid
     104         [ +  + ]:     110647 :         if (maybeErase->second.fromPeer == peer)
     105                 :            :         {
     106   [ +  -  +  - ]:      45310 :             nErased += _EraseTx(maybeErase->second.tx->GetHash());
     107                 :      45310 :         }
     108                 :            :     }
     109   [ +  +  +  -  :     151240 :     if (nErased > 0) LogPrint(BCLog::MEMPOOL, "Erased %d orphan tx from peer=%d\n", nErased, peer);
          +  -  #  #  #  
                #  #  # ]
     110                 :     151240 : }
     111                 :            : 
     112                 :      76973 : void TxOrphanage::LimitOrphans(unsigned int max_orphans)
     113                 :            : {
     114                 :      76973 :     LOCK(m_mutex);
     115                 :            : 
     116                 :      76973 :     unsigned int nEvicted = 0;
     117                 :            :     static int64_t nNextSweep;
     118         [ +  - ]:      76973 :     int64_t nNow = GetTime();
     119         [ +  + ]:      76973 :     if (nNextSweep <= nNow) {
     120                 :            :         // Sweep out expired orphan pool entries:
     121                 :         21 :         int nErased = 0;
     122                 :         21 :         int64_t nMinExpTime = nNow + ORPHAN_TX_EXPIRE_TIME - ORPHAN_TX_EXPIRE_INTERVAL;
     123                 :         21 :         std::map<uint256, OrphanTx>::iterator iter = m_orphans.begin();
     124         [ +  + ]:         41 :         while (iter != m_orphans.end())
     125                 :            :         {
     126                 :         20 :             std::map<uint256, OrphanTx>::iterator maybeErase = iter++;
     127         [ +  + ]:         20 :             if (maybeErase->second.nTimeExpire <= nNow) {
     128   [ +  -  +  - ]:          6 :                 nErased += _EraseTx(maybeErase->second.tx->GetHash());
     129                 :          6 :             } else {
     130         [ +  - ]:         14 :                 nMinExpTime = std::min(maybeErase->second.nTimeExpire, nMinExpTime);
     131                 :            :             }
     132                 :            :         }
     133                 :            :         // Sweep again 5 minutes after the next entry that expires in order to batch the linear scan.
     134                 :         21 :         nNextSweep = nMinExpTime + ORPHAN_TX_EXPIRE_INTERVAL;
     135   [ +  +  +  -  :         21 :         if (nErased > 0) LogPrint(BCLog::MEMPOOL, "Erased %d orphan tx due to expiration\n", nErased);
          +  -  #  #  #  
                #  #  # ]
     136                 :         21 :     }
     137                 :      76973 :     FastRandomContext rng;
     138         [ +  + ]:      93276 :     while (m_orphans.size() > max_orphans)
     139                 :            :     {
     140                 :            :         // Evict a random orphan:
     141                 :      16303 :         size_t randompos = rng.randrange(m_orphan_list.size());
     142         [ +  - ]:      16303 :         _EraseTx(m_orphan_list[randompos]->first);
     143                 :      16303 :         ++nEvicted;
     144                 :            :     }
     145   [ +  +  +  -  :      76973 :     if (nEvicted > 0) LogPrint(BCLog::MEMPOOL, "orphanage overflow, removed %u tx\n", nEvicted);
          +  -  #  #  #  
                #  #  # ]
     146                 :      76973 : }
     147                 :            : 
     148                 :      11187 : void TxOrphanage::AddChildrenToWorkSet(const CTransaction& tx)
     149                 :            : {
     150                 :      11187 :     LOCK(m_mutex);
     151                 :            : 
     152                 :            : 
     153         [ +  + ]:   19615175 :     for (unsigned int i = 0; i < tx.vout.size(); i++) {
     154   [ +  -  +  -  :   19603988 :         const auto it_by_prev = m_outpoint_to_orphan_it.find(COutPoint(tx.GetHash(), i));
                   +  - ]
     155         [ +  + ]:   19603988 :         if (it_by_prev != m_outpoint_to_orphan_it.end()) {
     156         [ +  + ]:      18779 :             for (const auto& elem : it_by_prev->second) {
     157                 :            :                 // Get this source peer's work set, emplacing an empty set if it didn't exist
     158                 :            :                 // (note: if this peer wasn't still connected, we would have removed the orphan tx already)
     159         [ +  - ]:      13468 :                 std::set<uint256>& orphan_work_set = m_peer_work_set.try_emplace(elem->second.fromPeer).first->second;
     160                 :            :                 // Add this tx to the work set
     161         [ +  - ]:      13468 :                 orphan_work_set.insert(elem->first);
     162                 :            :             }
     163                 :       5311 :         }
     164                 :   19603988 :     }
     165                 :      11187 : }
     166                 :            : 
     167                 :    1909323 : bool TxOrphanage::HaveTx(const GenTxid& gtxid) const
     168                 :            : {
     169                 :    1909323 :     LOCK(m_mutex);
     170   [ +  -  +  + ]:    1909323 :     if (gtxid.IsWtxid()) {
     171   [ +  -  +  - ]:     307951 :         return m_wtxid_to_orphan_it.count(gtxid.GetHash());
     172                 :            :     } else {
     173   [ +  -  +  - ]:    1601372 :         return m_orphans.count(gtxid.GetHash());
     174                 :            :     }
     175                 :    1909323 : }
     176                 :            : 
     177                 :    3669144 : CTransactionRef TxOrphanage::GetTxToReconsider(NodeId peer)
     178                 :            : {
     179                 :    3669144 :     LOCK(m_mutex);
     180                 :            : 
     181         [ +  - ]:    3669144 :     auto work_set_it = m_peer_work_set.find(peer);
     182         [ +  + ]:    3669144 :     if (work_set_it != m_peer_work_set.end()) {
     183                 :          2 :         auto& work_set = work_set_it->second;
     184         [ +  - ]:          2 :         while (!work_set.empty()) {
     185                 :          2 :             uint256 txid = *work_set.begin();
     186         [ +  - ]:          2 :             work_set.erase(work_set.begin());
     187                 :            : 
     188         [ +  - ]:          2 :             const auto orphan_it = m_orphans.find(txid);
     189         [ -  + ]:          2 :             if (orphan_it != m_orphans.end()) {
     190                 :          2 :                 return orphan_it->second.tx;
     191                 :            :             }
     192                 :            :         }
     193                 :          0 :     }
     194                 :    3669142 :     return nullptr;
     195                 :    3669144 : }
     196                 :            : 
     197                 :    1671569 : bool TxOrphanage::HaveTxToReconsider(NodeId peer)
     198                 :            : {
     199                 :    1671569 :     LOCK(m_mutex);
     200                 :            : 
     201         [ +  - ]:    1671569 :     auto work_set_it = m_peer_work_set.find(peer);
     202         [ -  + ]:    1671569 :     if (work_set_it != m_peer_work_set.end()) {
     203                 :          0 :         auto& work_set = work_set_it->second;
     204                 :          0 :         return !work_set.empty();
     205                 :            :     }
     206                 :    1671569 :     return false;
     207                 :    1671569 : }
     208                 :            : 
     209                 :          0 : void TxOrphanage::EraseForBlock(const CBlock& block)
     210                 :            : {
     211                 :          0 :     LOCK(m_mutex);
     212                 :            : 
     213                 :          0 :     std::vector<uint256> vOrphanErase;
     214                 :            : 
     215         [ #  # ]:          0 :     for (const CTransactionRef& ptx : block.vtx) {
     216                 :          0 :         const CTransaction& tx = *ptx;
     217                 :            : 
     218                 :            :         // Which orphan pool entries must we evict?
     219         [ #  # ]:          0 :         for (const auto& txin : tx.vin) {
     220         [ #  # ]:          0 :             auto itByPrev = m_outpoint_to_orphan_it.find(txin.prevout);
     221         [ #  # ]:          0 :             if (itByPrev == m_outpoint_to_orphan_it.end()) continue;
     222         [ #  # ]:          0 :             for (auto mi = itByPrev->second.begin(); mi != itByPrev->second.end(); ++mi) {
     223                 :          0 :                 const CTransaction& orphanTx = *(*mi)->second.tx;
     224         [ #  # ]:          0 :                 const uint256& orphanHash = orphanTx.GetHash();
     225         [ #  # ]:          0 :                 vOrphanErase.push_back(orphanHash);
     226                 :          0 :             }
     227                 :            :         }
     228                 :            :     }
     229                 :            : 
     230                 :            :     // Erase orphan transactions included or precluded by this block
     231         [ #  # ]:          0 :     if (vOrphanErase.size()) {
     232                 :          0 :         int nErased = 0;
     233         [ #  # ]:          0 :         for (const uint256& orphanHash : vOrphanErase) {
     234         [ #  # ]:          0 :             nErased += _EraseTx(orphanHash);
     235                 :            :         }
     236   [ #  #  #  #  :          0 :         LogPrint(BCLog::MEMPOOL, "Erased %d orphan tx included or conflicted by block\n", nErased);
          #  #  #  #  #  
                      # ]
     237                 :          0 :     }
     238                 :          0 : }

Generated by: LCOV version 1.16