Branch data Line data Source code
# 1 : : // Copyright (c) 2021 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 : :
# 18 : : RecursiveMutex g_cs_orphans;
# 19 : :
# 20 : : bool TxOrphanage::AddTx(const CTransactionRef& tx, NodeId peer)
# 21 : 350 : {
# 22 : 350 : AssertLockHeld(g_cs_orphans);
# 23 : :
# 24 : 350 : const uint256& hash = tx->GetHash();
# 25 [ + + ]: 350 : if (m_orphans.count(hash))
# 26 : 42 : 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 : 308 : unsigned int sz = GetTransactionWeight(*tx);
# 36 [ + + ]: 308 : if (sz > MAX_STANDARD_TX_WEIGHT)
# 37 : 20 : {
# 38 [ + - ]: 20 : LogPrint(BCLog::MEMPOOL, "ignoring large orphan tx (size: %u, hash: %s)\n", sz, hash.ToString());
# 39 : 20 : return false;
# 40 : 20 : }
# 41 : :
# 42 : 288 : auto ret = m_orphans.emplace(hash, OrphanTx{tx, peer, GetTime() + ORPHAN_TX_EXPIRE_TIME, m_orphan_list.size()});
# 43 : 288 : assert(ret.second);
# 44 : 288 : m_orphan_list.push_back(ret.first);
# 45 : : // Allow for lookups in the orphan pool by wtxid, as well as txid
# 46 : 288 : m_wtxid_to_orphan_it.emplace(tx->GetWitnessHash(), ret.first);
# 47 [ + + ]: 289 : for (const CTxIn& txin : tx->vin) {
# 48 : 289 : m_outpoint_to_orphan_it[txin.prevout].insert(ret.first);
# 49 : 289 : }
# 50 : :
# 51 [ + - ]: 288 : LogPrint(BCLog::MEMPOOL, "stored orphan tx %s (mapsz %u outsz %u)\n", hash.ToString(),
# 52 : 288 : m_orphans.size(), m_outpoint_to_orphan_it.size());
# 53 : 288 : return true;
# 54 : 288 : }
# 55 : :
# 56 : : int TxOrphanage::EraseTx(const uint256& txid)
# 57 : 288 : {
# 58 : 288 : AssertLockHeld(g_cs_orphans);
# 59 : 288 : std::map<uint256, OrphanTx>::iterator it = m_orphans.find(txid);
# 60 [ - + ]: 288 : if (it == m_orphans.end())
# 61 : 0 : return 0;
# 62 [ + + ]: 288 : for (const CTxIn& txin : it->second.tx->vin)
# 63 : 289 : {
# 64 : 289 : auto itPrev = m_outpoint_to_orphan_it.find(txin.prevout);
# 65 [ - + ]: 289 : if (itPrev == m_outpoint_to_orphan_it.end())
# 66 : 0 : continue;
# 67 : 289 : itPrev->second.erase(it);
# 68 [ + - ]: 289 : if (itPrev->second.empty())
# 69 : 289 : m_outpoint_to_orphan_it.erase(itPrev);
# 70 : 289 : }
# 71 : :
# 72 : 288 : size_t old_pos = it->second.list_pos;
# 73 : 288 : assert(m_orphan_list[old_pos] == it);
# 74 [ + + ]: 288 : if (old_pos + 1 != m_orphan_list.size()) {
# 75 : : // Unless we're deleting the last entry in m_orphan_list, move the last
# 76 : : // entry to the position we're deleting.
# 77 : 265 : auto it_last = m_orphan_list.back();
# 78 : 265 : m_orphan_list[old_pos] = it_last;
# 79 : 265 : it_last->second.list_pos = old_pos;
# 80 : 265 : }
# 81 : 288 : m_orphan_list.pop_back();
# 82 : 288 : m_wtxid_to_orphan_it.erase(it->second.tx->GetWitnessHash());
# 83 : :
# 84 : 288 : m_orphans.erase(it);
# 85 : 288 : return 1;
# 86 : 288 : }
# 87 : :
# 88 : : void TxOrphanage::EraseForPeer(NodeId peer)
# 89 : 1010 : {
# 90 : 1010 : AssertLockHeld(g_cs_orphans);
# 91 : :
# 92 : 1010 : int nErased = 0;
# 93 : 1010 : std::map<uint256, OrphanTx>::iterator iter = m_orphans.begin();
# 94 [ + + ]: 1577 : while (iter != m_orphans.end())
# 95 : 567 : {
# 96 : 567 : std::map<uint256, OrphanTx>::iterator maybeErase = iter++; // increment to avoid iterator becoming invalid
# 97 [ + + ]: 567 : if (maybeErase->second.fromPeer == peer)
# 98 : 115 : {
# 99 : 115 : nErased += EraseTx(maybeErase->second.tx->GetHash());
# 100 : 115 : }
# 101 : 567 : }
# 102 [ + + ][ + - ]: 1010 : if (nErased > 0) LogPrint(BCLog::MEMPOOL, "Erased %d orphan tx from peer=%d\n", nErased, peer);
# 103 : 1010 : }
# 104 : :
# 105 : : unsigned int TxOrphanage::LimitOrphans(unsigned int max_orphans)
# 106 : 136 : {
# 107 : 136 : AssertLockHeld(g_cs_orphans);
# 108 : :
# 109 : 136 : unsigned int nEvicted = 0;
# 110 : 136 : static int64_t nNextSweep;
# 111 : 136 : int64_t nNow = GetTime();
# 112 [ + + ]: 136 : if (nNextSweep <= nNow) {
# 113 : : // Sweep out expired orphan pool entries:
# 114 : 7 : int nErased = 0;
# 115 : 7 : int64_t nMinExpTime = nNow + ORPHAN_TX_EXPIRE_TIME - ORPHAN_TX_EXPIRE_INTERVAL;
# 116 : 7 : std::map<uint256, OrphanTx>::iterator iter = m_orphans.begin();
# 117 [ + + ]: 160 : while (iter != m_orphans.end())
# 118 : 153 : {
# 119 : 153 : std::map<uint256, OrphanTx>::iterator maybeErase = iter++;
# 120 [ - + ]: 153 : if (maybeErase->second.nTimeExpire <= nNow) {
# 121 : 0 : nErased += EraseTx(maybeErase->second.tx->GetHash());
# 122 : 153 : } else {
# 123 : 153 : nMinExpTime = std::min(maybeErase->second.nTimeExpire, nMinExpTime);
# 124 : 153 : }
# 125 : 153 : }
# 126 : : // Sweep again 5 minutes after the next entry that expires in order to batch the linear scan.
# 127 : 7 : nNextSweep = nMinExpTime + ORPHAN_TX_EXPIRE_INTERVAL;
# 128 [ - + ][ # # ]: 7 : if (nErased > 0) LogPrint(BCLog::MEMPOOL, "Erased %d orphan tx due to expiration\n", nErased);
# 129 : 7 : }
# 130 : 136 : FastRandomContext rng;
# 131 [ + + ]: 285 : while (m_orphans.size() > max_orphans)
# 132 : 149 : {
# 133 : : // Evict a random orphan:
# 134 : 149 : size_t randompos = rng.randrange(m_orphan_list.size());
# 135 : 149 : EraseTx(m_orphan_list[randompos]->first);
# 136 : 149 : ++nEvicted;
# 137 : 149 : }
# 138 : 136 : return nEvicted;
# 139 : 136 : }
# 140 : :
# 141 : : void TxOrphanage::AddChildrenToWorkSet(const CTransaction& tx, std::set<uint256>& orphan_work_set) const
# 142 : 9719 : {
# 143 : 9719 : AssertLockHeld(g_cs_orphans);
# 144 [ + + ]: 31761 : for (unsigned int i = 0; i < tx.vout.size(); i++) {
# 145 : 22042 : const auto it_by_prev = m_outpoint_to_orphan_it.find(COutPoint(tx.GetHash(), i));
# 146 [ + + ]: 22042 : if (it_by_prev != m_outpoint_to_orphan_it.end()) {
# 147 [ + + ]: 5 : for (const auto& elem : it_by_prev->second) {
# 148 : 5 : orphan_work_set.insert(elem->first);
# 149 : 5 : }
# 150 : 5 : }
# 151 : 22042 : }
# 152 : 9719 : }
# 153 : :
# 154 : : bool TxOrphanage::HaveTx(const GenTxid& gtxid) const
# 155 : 54379 : {
# 156 : 54379 : LOCK(g_cs_orphans);
# 157 [ + + ]: 54379 : if (gtxid.IsWtxid()) {
# 158 : 54226 : return m_wtxid_to_orphan_it.count(gtxid.GetHash());
# 159 : 54226 : } else {
# 160 : 153 : return m_orphans.count(gtxid.GetHash());
# 161 : 153 : }
# 162 : 54379 : }
# 163 : :
# 164 : : std::pair<CTransactionRef, NodeId> TxOrphanage::GetTx(const uint256& txid) const
# 165 : 5 : {
# 166 : 5 : AssertLockHeld(g_cs_orphans);
# 167 : :
# 168 : 5 : const auto it = m_orphans.find(txid);
# 169 [ - + ]: 5 : if (it == m_orphans.end()) return {nullptr, -1};
# 170 : 5 : return {it->second.tx, it->second.fromPeer};
# 171 : 5 : }
# 172 : :
# 173 : : void TxOrphanage::EraseForBlock(const CBlock& block)
# 174 : 62992 : {
# 175 : 62992 : LOCK(g_cs_orphans);
# 176 : :
# 177 : 62992 : std::vector<uint256> vOrphanErase;
# 178 : :
# 179 [ + + ]: 114398 : for (const CTransactionRef& ptx : block.vtx) {
# 180 : 114398 : const CTransaction& tx = *ptx;
# 181 : :
# 182 : : // Which orphan pool entries must we evict?
# 183 [ + + ]: 152767 : for (const auto& txin : tx.vin) {
# 184 : 152767 : auto itByPrev = m_outpoint_to_orphan_it.find(txin.prevout);
# 185 [ + + ]: 152767 : if (itByPrev == m_outpoint_to_orphan_it.end()) continue;
# 186 [ + + ]: 38 : for (auto mi = itByPrev->second.begin(); mi != itByPrev->second.end(); ++mi) {
# 187 : 19 : const CTransaction& orphanTx = *(*mi)->second.tx;
# 188 : 19 : const uint256& orphanHash = orphanTx.GetHash();
# 189 : 19 : vOrphanErase.push_back(orphanHash);
# 190 : 19 : }
# 191 : 19 : }
# 192 : 114398 : }
# 193 : :
# 194 : : // Erase orphan transactions included or precluded by this block
# 195 [ + + ]: 62992 : if (vOrphanErase.size()) {
# 196 : 1 : int nErased = 0;
# 197 [ + + ]: 19 : for (const uint256& orphanHash : vOrphanErase) {
# 198 : 19 : nErased += EraseTx(orphanHash);
# 199 : 19 : }
# 200 [ + - ]: 1 : LogPrint(BCLog::MEMPOOL, "Erased %d orphan tx included or conflicted by block\n", nErased);
# 201 : 1 : }
# 202 : 62992 : }
|
