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

Generated by: LCOV version 1.14