LCOV - code coverage report
Current view: top level - src - txorphanage.cpp (source / functions) Hit Total Coverage
Test: fuzz_coverage.info Lines: 0 144 0.0 %
Date: 2024-01-03 14:57:27 Functions: 0 10 0.0 %
Branches: 0 244 0.0 %

           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                 :            : #include <primitives/transaction.h>
      11                 :            : 
      12                 :            : #include <cassert>
      13                 :            : 
      14                 :            : /** Expiration time for orphan transactions in seconds */
      15                 :            : static constexpr int64_t ORPHAN_TX_EXPIRE_TIME = 20 * 60;
      16                 :            : /** Minimum time between orphan transactions expire time checks in seconds */
      17                 :            : static constexpr int64_t ORPHAN_TX_EXPIRE_INTERVAL = 5 * 60;
      18                 :            : 
      19                 :            : 
      20                 :          0 : bool TxOrphanage::AddTx(const CTransactionRef& tx, NodeId peer)
      21                 :            : {
      22                 :          0 :     LOCK(m_mutex);
      23                 :            : 
      24         [ #  # ]:          0 :     const Txid& hash = tx->GetHash();
      25         [ #  # ]:          0 :     const Wtxid& wtxid = tx->GetWitnessHash();
      26 [ #  # ][ #  # ]:          0 :     if (m_orphans.count(hash))
      27                 :          0 :         return false;
      28                 :            : 
      29                 :            :     // Ignore big transactions, to avoid a
      30                 :            :     // send-big-orphans memory exhaustion attack. If a peer has a legitimate
      31                 :            :     // large transaction with a missing parent then we assume
      32                 :            :     // it will rebroadcast it later, after the parent transaction(s)
      33                 :            :     // have been mined or received.
      34                 :            :     // 100 orphans, each of which is at most 100,000 bytes big is
      35                 :            :     // at most 10 megabytes of orphans and somewhat more byprev index (in the worst case):
      36         [ #  # ]:          0 :     unsigned int sz = GetTransactionWeight(*tx);
      37         [ #  # ]:          0 :     if (sz > MAX_STANDARD_TX_WEIGHT)
      38                 :            :     {
      39 [ #  # ][ #  # ]:          0 :         LogPrint(BCLog::TXPACKAGES, "ignoring large orphan tx (size: %u, txid: %s, wtxid: %s)\n", sz, hash.ToString(), wtxid.ToString());
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
      40                 :          0 :         return false;
      41                 :            :     }
      42                 :            : 
      43 [ #  # ][ #  # ]:          0 :     auto ret = m_orphans.emplace(hash, OrphanTx{tx, peer, GetTime() + ORPHAN_TX_EXPIRE_TIME, m_orphan_list.size()});
      44         [ #  # ]:          0 :     assert(ret.second);
      45         [ #  # ]:          0 :     m_orphan_list.push_back(ret.first);
      46                 :            :     // Allow for lookups in the orphan pool by wtxid, as well as txid
      47 [ #  # ][ #  # ]:          0 :     m_wtxid_to_orphan_it.emplace(tx->GetWitnessHash(), ret.first);
      48         [ #  # ]:          0 :     for (const CTxIn& txin : tx->vin) {
      49 [ #  # ][ #  # ]:          0 :         m_outpoint_to_orphan_it[txin.prevout].insert(ret.first);
      50                 :            :     }
      51                 :            : 
      52 [ #  # ][ #  # ]:          0 :     LogPrint(BCLog::TXPACKAGES, "stored orphan tx %s (wtxid=%s) (mapsz %u outsz %u)\n", hash.ToString(), wtxid.ToString(),
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
      53                 :            :              m_orphans.size(), m_outpoint_to_orphan_it.size());
      54                 :          0 :     return true;
      55                 :          0 : }
      56                 :            : 
      57                 :          0 : int TxOrphanage::EraseTx(const Txid& txid)
      58                 :            : {
      59                 :          0 :     LOCK(m_mutex);
      60         [ #  # ]:          0 :     return EraseTxNoLock(txid);
      61                 :          0 : }
      62                 :            : 
      63                 :          0 : int TxOrphanage::EraseTxNoLock(const Txid& txid)
      64                 :            : {
      65                 :          0 :     AssertLockHeld(m_mutex);
      66                 :          0 :     std::map<Txid, OrphanTx>::iterator it = m_orphans.find(txid);
      67         [ #  # ]:          0 :     if (it == m_orphans.end())
      68                 :          0 :         return 0;
      69         [ #  # ]:          0 :     for (const CTxIn& txin : it->second.tx->vin)
      70                 :            :     {
      71                 :          0 :         auto itPrev = m_outpoint_to_orphan_it.find(txin.prevout);
      72         [ #  # ]:          0 :         if (itPrev == m_outpoint_to_orphan_it.end())
      73                 :          0 :             continue;
      74                 :          0 :         itPrev->second.erase(it);
      75         [ #  # ]:          0 :         if (itPrev->second.empty())
      76                 :          0 :             m_outpoint_to_orphan_it.erase(itPrev);
      77                 :            :     }
      78                 :            : 
      79                 :          0 :     size_t old_pos = it->second.list_pos;
      80         [ #  # ]:          0 :     assert(m_orphan_list[old_pos] == it);
      81         [ #  # ]:          0 :     if (old_pos + 1 != m_orphan_list.size()) {
      82                 :            :         // Unless we're deleting the last entry in m_orphan_list, move the last
      83                 :            :         // entry to the position we're deleting.
      84                 :          0 :         auto it_last = m_orphan_list.back();
      85                 :          0 :         m_orphan_list[old_pos] = it_last;
      86                 :          0 :         it_last->second.list_pos = old_pos;
      87                 :          0 :     }
      88                 :          0 :     const auto& wtxid = it->second.tx->GetWitnessHash();
      89 [ #  # ][ #  # ]:          0 :     LogPrint(BCLog::TXPACKAGES, "   removed orphan tx %s (wtxid=%s)\n", txid.ToString(), wtxid.ToString());
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
      90                 :          0 :     m_orphan_list.pop_back();
      91                 :          0 :     m_wtxid_to_orphan_it.erase(it->second.tx->GetWitnessHash());
      92                 :            : 
      93                 :          0 :     m_orphans.erase(it);
      94                 :          0 :     return 1;
      95                 :          0 : }
      96                 :            : 
      97                 :          0 : void TxOrphanage::EraseForPeer(NodeId peer)
      98                 :            : {
      99                 :          0 :     LOCK(m_mutex);
     100                 :            : 
     101         [ #  # ]:          0 :     m_peer_work_set.erase(peer);
     102                 :            : 
     103                 :          0 :     int nErased = 0;
     104                 :          0 :     std::map<Txid, OrphanTx>::iterator iter = m_orphans.begin();
     105         [ #  # ]:          0 :     while (iter != m_orphans.end())
     106                 :            :     {
     107                 :          0 :         std::map<Txid, OrphanTx>::iterator maybeErase = iter++; // increment to avoid iterator becoming invalid
     108         [ #  # ]:          0 :         if (maybeErase->second.fromPeer == peer)
     109                 :            :         {
     110 [ #  # ][ #  # ]:          0 :             nErased += EraseTxNoLock(maybeErase->second.tx->GetHash());
     111                 :          0 :         }
     112                 :            :     }
     113 [ #  # ][ #  # ]:          0 :     if (nErased > 0) LogPrint(BCLog::TXPACKAGES, "Erased %d orphan tx from peer=%d\n", nErased, peer);
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
     114                 :          0 : }
     115                 :            : 
     116                 :          0 : void TxOrphanage::LimitOrphans(unsigned int max_orphans, FastRandomContext& rng)
     117                 :            : {
     118                 :          0 :     LOCK(m_mutex);
     119                 :            : 
     120                 :          0 :     unsigned int nEvicted = 0;
     121                 :            :     static int64_t nNextSweep;
     122         [ #  # ]:          0 :     int64_t nNow = GetTime();
     123         [ #  # ]:          0 :     if (nNextSweep <= nNow) {
     124                 :            :         // Sweep out expired orphan pool entries:
     125                 :          0 :         int nErased = 0;
     126                 :          0 :         int64_t nMinExpTime = nNow + ORPHAN_TX_EXPIRE_TIME - ORPHAN_TX_EXPIRE_INTERVAL;
     127                 :          0 :         std::map<Txid, OrphanTx>::iterator iter = m_orphans.begin();
     128         [ #  # ]:          0 :         while (iter != m_orphans.end())
     129                 :            :         {
     130                 :          0 :             std::map<Txid, OrphanTx>::iterator maybeErase = iter++;
     131         [ #  # ]:          0 :             if (maybeErase->second.nTimeExpire <= nNow) {
     132 [ #  # ][ #  # ]:          0 :                 nErased += EraseTxNoLock(maybeErase->second.tx->GetHash());
     133                 :          0 :             } else {
     134         [ #  # ]:          0 :                 nMinExpTime = std::min(maybeErase->second.nTimeExpire, nMinExpTime);
     135                 :            :             }
     136                 :            :         }
     137                 :            :         // Sweep again 5 minutes after the next entry that expires in order to batch the linear scan.
     138                 :          0 :         nNextSweep = nMinExpTime + ORPHAN_TX_EXPIRE_INTERVAL;
     139 [ #  # ][ #  # ]:          0 :         if (nErased > 0) LogPrint(BCLog::TXPACKAGES, "Erased %d orphan tx due to expiration\n", nErased);
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
     140                 :          0 :     }
     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<Txid>& 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(Wtxid::FromUint256(gtxid.GetHash()));
                 [ #  # ]
     177                 :            :     } else {
     178 [ #  # ][ #  # ]:          0 :         return m_orphans.count(Txid::FromUint256(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 :             Txid 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<Txid> 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 auto& 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 auto& 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