diff options
Diffstat (limited to 'src')
-rw-r--r-- | src/Makefile.am | 6 | ||||
-rw-r--r-- | src/init.cpp | 1 | ||||
-rw-r--r-- | src/net_processing.cpp | 284 | ||||
-rw-r--r-- | src/net_processing.h | 1 | ||||
-rw-r--r-- | src/test/denialofservice_tests.cpp | 69 | ||||
-rw-r--r-- | src/test/fuzz/process_message.cpp | 1 | ||||
-rw-r--r-- | src/test/fuzz/process_messages.cpp | 1 | ||||
-rw-r--r-- | src/txorphanage.cpp | 202 | ||||
-rw-r--r-- | src/txorphanage.h | 85 |
9 files changed, 361 insertions, 289 deletions
diff --git a/src/Makefile.am b/src/Makefile.am index 1c6d97b714..b36d67bab0 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -225,8 +225,9 @@ BITCOIN_CORE_H = \ timedata.h \ torcontrol.h \ txdb.h \ - txrequest.h \ txmempool.h \ + txorphanage.h \ + txrequest.h \ undo.h \ util/asmap.h \ util/bip32.h \ @@ -350,8 +351,9 @@ libbitcoin_server_a_SOURCES = \ timedata.cpp \ torcontrol.cpp \ txdb.cpp \ - txrequest.cpp \ txmempool.cpp \ + txorphanage.cpp \ + txrequest.cpp \ validation.cpp \ validationinterface.cpp \ versionbits.cpp \ diff --git a/src/init.cpp b/src/init.cpp index f40cf7975b..f760c069ac 100644 --- a/src/init.cpp +++ b/src/init.cpp @@ -52,6 +52,7 @@ #include <torcontrol.h> #include <txdb.h> #include <txmempool.h> +#include <txorphanage.h> #include <util/asmap.h> #include <util/check.h> #include <util/moneystr.h> diff --git a/src/net_processing.cpp b/src/net_processing.cpp index c97f7ced46..af61e7064e 100644 --- a/src/net_processing.cpp +++ b/src/net_processing.cpp @@ -26,6 +26,7 @@ #include <streams.h> #include <tinyformat.h> #include <txmempool.h> +#include <txorphanage.h> #include <txrequest.h> #include <util/check.h> // For NDEBUG compile time check #include <util/strencodings.h> @@ -35,10 +36,6 @@ #include <memory> #include <typeinfo> -/** Expiration time for orphan transactions in seconds */ -static constexpr int64_t ORPHAN_TX_EXPIRE_TIME = 20 * 60; -/** Minimum time between orphan transactions expire time checks in seconds */ -static constexpr int64_t ORPHAN_TX_EXPIRE_INTERVAL = 5 * 60; /** How long to cache transactions in mapRelay for normal relay */ static constexpr std::chrono::seconds RELAY_TX_CACHE_TIME = std::chrono::minutes{15}; /** How long a transaction has to be in the mempool before it can unconditionally be relayed (even when not in mapRelay). */ @@ -148,25 +145,6 @@ static constexpr uint32_t MAX_GETCFHEADERS_SIZE = 2000; /** the maximum percentage of addresses from our addrman to return in response to a getaddr message. */ static constexpr size_t MAX_PCT_ADDR_TO_SEND = 23; -struct COrphanTx { - // When modifying, adapt the copy of this definition in tests/DoS_tests. - CTransactionRef tx; - NodeId fromPeer; - int64_t nTimeExpire; - size_t list_pos; -}; - -/** Guards orphan transactions and extra txs for compact blocks */ -RecursiveMutex g_cs_orphans; -/** Map from txid to orphan transaction record. Limited by - * -maxorphantx/DEFAULT_MAX_ORPHAN_TRANSACTIONS */ -std::map<uint256, COrphanTx> mapOrphanTransactions GUARDED_BY(g_cs_orphans); -/** Index from wtxid into the mapOrphanTransactions to lookup orphan - * transactions using their witness ids. */ -std::map<uint256, std::map<uint256, COrphanTx>::iterator> g_orphans_by_wtxid GUARDED_BY(g_cs_orphans); - -void EraseOrphansFor(NodeId peer); - // Internal stuff namespace { /** Blocks that are in flight, and that are in the queue to be downloaded. */ @@ -479,35 +457,23 @@ private: /** Number of peers from which we're downloading blocks. */ int nPeersWithValidatedDownloads GUARDED_BY(cs_main) = 0; -}; -} // namespace + /** Storage for orphan information */ + TxOrphanage m_orphanage; -namespace { - - /** Number of preferable block download peers. */ - int nPreferredDownload GUARDED_BY(cs_main) = 0; - - struct IteratorComparator - { - template<typename I> - bool operator()(const I& a, const I& b) const - { - return &(*a) < &(*b); - } - }; - - /** Index from the parents' COutPoint into the mapOrphanTransactions. Used - * to remove orphan transactions from the mapOrphanTransactions */ - std::map<COutPoint, std::set<std::map<uint256, COrphanTx>::iterator, IteratorComparator>> mapOrphanTransactionsByPrev GUARDED_BY(g_cs_orphans); - /** Orphan transactions in vector for quick random eviction */ - std::vector<std::map<uint256, COrphanTx>::iterator> g_orphan_list GUARDED_BY(g_cs_orphans); + void AddToCompactExtraTransactions(const CTransactionRef& tx) EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans); /** Orphan/conflicted/etc transactions that are kept for compact block reconstruction. * The last -blockreconstructionextratxn/DEFAULT_BLOCK_RECONSTRUCTION_EXTRA_TXN of * these are kept in a ring buffer */ - static std::vector<std::pair<uint256, CTransactionRef>> vExtraTxnForCompact GUARDED_BY(g_cs_orphans); + std::vector<std::pair<uint256, CTransactionRef>> vExtraTxnForCompact GUARDED_BY(g_cs_orphans); /** Offset into vExtraTxnForCompact to insert the next tx */ - static size_t vExtraTxnForCompactIt GUARDED_BY(g_cs_orphans) = 0; + size_t vExtraTxnForCompactIt GUARDED_BY(g_cs_orphans) = 0; +}; +} // namespace + +namespace { + /** Number of preferable block download peers. */ + int nPreferredDownload GUARDED_BY(cs_main) = 0; } // namespace namespace { @@ -1040,7 +1006,7 @@ void PeerManagerImpl::FinalizeNode(const CNode& node, bool& fUpdateConnectionTim for (const QueuedBlock& entry : state->vBlocksInFlight) { mapBlocksInFlight.erase(entry.hash); } - EraseOrphansFor(nodeid); + WITH_LOCK(g_cs_orphans, m_orphanage.EraseForPeer(nodeid)); m_txrequest.DisconnectedPeer(nodeid); nPreferredDownload -= state->fPreferredDownload; nPeersWithValidatedDownloads -= (state->nBlocksInFlightValidHeaders != 0); @@ -1117,12 +1083,7 @@ bool PeerManagerImpl::GetNodeStateStats(NodeId nodeid, CNodeStateStats &stats) return true; } -////////////////////////////////////////////////////////////////////////////// -// -// mapOrphanTransactions -// - -static void AddToCompactExtraTransactions(const CTransactionRef& tx) EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans) +void PeerManagerImpl::AddToCompactExtraTransactions(const CTransactionRef& tx) { size_t max_extra_txn = gArgs.GetArg("-blockreconstructionextratxn", DEFAULT_BLOCK_RECONSTRUCTION_EXTRA_TXN); if (max_extra_txn <= 0) @@ -1133,126 +1094,6 @@ static void AddToCompactExtraTransactions(const CTransactionRef& tx) EXCLUSIVE_L vExtraTxnForCompactIt = (vExtraTxnForCompactIt + 1) % max_extra_txn; } -bool AddOrphanTx(const CTransactionRef& tx, NodeId peer) EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans) -{ - const uint256& hash = tx->GetHash(); - if (mapOrphanTransactions.count(hash)) - return false; - - // Ignore big transactions, to avoid a - // send-big-orphans memory exhaustion attack. If a peer has a legitimate - // large transaction with a missing parent then we assume - // it will rebroadcast it later, after the parent transaction(s) - // have been mined or received. - // 100 orphans, each of which is at most 100,000 bytes big is - // at most 10 megabytes of orphans and somewhat more byprev index (in the worst case): - unsigned int sz = GetTransactionWeight(*tx); - if (sz > MAX_STANDARD_TX_WEIGHT) - { - LogPrint(BCLog::MEMPOOL, "ignoring large orphan tx (size: %u, hash: %s)\n", sz, hash.ToString()); - return false; - } - - auto ret = mapOrphanTransactions.emplace(hash, COrphanTx{tx, peer, GetTime() + ORPHAN_TX_EXPIRE_TIME, g_orphan_list.size()}); - assert(ret.second); - g_orphan_list.push_back(ret.first); - // Allow for lookups in the orphan pool by wtxid, as well as txid - g_orphans_by_wtxid.emplace(tx->GetWitnessHash(), ret.first); - for (const CTxIn& txin : tx->vin) { - mapOrphanTransactionsByPrev[txin.prevout].insert(ret.first); - } - - AddToCompactExtraTransactions(tx); - - LogPrint(BCLog::MEMPOOL, "stored orphan tx %s (mapsz %u outsz %u)\n", hash.ToString(), - mapOrphanTransactions.size(), mapOrphanTransactionsByPrev.size()); - return true; -} - -int static EraseOrphanTx(uint256 hash) EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans) -{ - std::map<uint256, COrphanTx>::iterator it = mapOrphanTransactions.find(hash); - if (it == mapOrphanTransactions.end()) - return 0; - for (const CTxIn& txin : it->second.tx->vin) - { - auto itPrev = mapOrphanTransactionsByPrev.find(txin.prevout); - if (itPrev == mapOrphanTransactionsByPrev.end()) - continue; - itPrev->second.erase(it); - if (itPrev->second.empty()) - mapOrphanTransactionsByPrev.erase(itPrev); - } - - size_t old_pos = it->second.list_pos; - assert(g_orphan_list[old_pos] == it); - if (old_pos + 1 != g_orphan_list.size()) { - // Unless we're deleting the last entry in g_orphan_list, move the last - // entry to the position we're deleting. - auto it_last = g_orphan_list.back(); - g_orphan_list[old_pos] = it_last; - it_last->second.list_pos = old_pos; - } - g_orphan_list.pop_back(); - g_orphans_by_wtxid.erase(it->second.tx->GetWitnessHash()); - - mapOrphanTransactions.erase(it); - return 1; -} - -void EraseOrphansFor(NodeId peer) -{ - LOCK(g_cs_orphans); - int nErased = 0; - std::map<uint256, COrphanTx>::iterator iter = mapOrphanTransactions.begin(); - while (iter != mapOrphanTransactions.end()) - { - std::map<uint256, COrphanTx>::iterator maybeErase = iter++; // increment to avoid iterator becoming invalid - if (maybeErase->second.fromPeer == peer) - { - nErased += EraseOrphanTx(maybeErase->second.tx->GetHash()); - } - } - if (nErased > 0) LogPrint(BCLog::MEMPOOL, "Erased %d orphan tx from peer=%d\n", nErased, peer); -} - - -unsigned int LimitOrphanTxSize(unsigned int nMaxOrphans) -{ - LOCK(g_cs_orphans); - - unsigned int nEvicted = 0; - static int64_t nNextSweep; - int64_t nNow = GetTime(); - if (nNextSweep <= nNow) { - // Sweep out expired orphan pool entries: - int nErased = 0; - int64_t nMinExpTime = nNow + ORPHAN_TX_EXPIRE_TIME - ORPHAN_TX_EXPIRE_INTERVAL; - std::map<uint256, COrphanTx>::iterator iter = mapOrphanTransactions.begin(); - while (iter != mapOrphanTransactions.end()) - { - std::map<uint256, COrphanTx>::iterator maybeErase = iter++; - if (maybeErase->second.nTimeExpire <= nNow) { - nErased += EraseOrphanTx(maybeErase->second.tx->GetHash()); - } else { - nMinExpTime = std::min(maybeErase->second.nTimeExpire, nMinExpTime); - } - } - // Sweep again 5 minutes after the next entry that expires in order to batch the linear scan. - nNextSweep = nMinExpTime + ORPHAN_TX_EXPIRE_INTERVAL; - if (nErased > 0) LogPrint(BCLog::MEMPOOL, "Erased %d orphan tx due to expiration\n", nErased); - } - FastRandomContext rng; - while (mapOrphanTransactions.size() > nMaxOrphans) - { - // Evict a random orphan: - size_t randompos = rng.randrange(g_orphan_list.size()); - EraseOrphanTx(g_orphan_list[randompos]->first); - ++nEvicted; - } - return nEvicted; -} - void PeerManagerImpl::Misbehaving(const NodeId pnode, const int howmuch, const std::string& message) { assert(howmuch > 0); @@ -1412,43 +1253,15 @@ PeerManagerImpl::PeerManagerImpl(const CChainParams& chainparams, CConnman& conn } /** - * Evict orphan txn pool entries (EraseOrphanTx) based on a newly connected + * Evict orphan txn pool entries based on a newly connected * block, remember the recently confirmed transactions, and delete tracked * announcements for them. Also save the time of the last tip update. */ void PeerManagerImpl::BlockConnected(const std::shared_ptr<const CBlock>& pblock, const CBlockIndex* pindex) { - { - LOCK(g_cs_orphans); - - std::vector<uint256> vOrphanErase; - - for (const CTransactionRef& ptx : pblock->vtx) { - const CTransaction& tx = *ptx; - - // Which orphan pool entries must we evict? - for (const auto& txin : tx.vin) { - auto itByPrev = mapOrphanTransactionsByPrev.find(txin.prevout); - if (itByPrev == mapOrphanTransactionsByPrev.end()) continue; - for (auto mi = itByPrev->second.begin(); mi != itByPrev->second.end(); ++mi) { - const CTransaction& orphanTx = *(*mi)->second.tx; - const uint256& orphanHash = orphanTx.GetHash(); - vOrphanErase.push_back(orphanHash); - } - } - } + m_orphanage.EraseForBlock(*pblock); + m_last_tip_update = GetTime(); - // Erase orphan transactions included or precluded by this block - if (vOrphanErase.size()) { - int nErased = 0; - for (const uint256& orphanHash : vOrphanErase) { - nErased += EraseOrphanTx(orphanHash); - } - LogPrint(BCLog::MEMPOOL, "Erased %d orphan tx included or conflicted by block\n", nErased); - } - - m_last_tip_update = GetTime(); - } { LOCK(m_recent_confirmed_transactions_mutex); for (const auto& ptx : pblock->vtx) { @@ -1630,14 +1443,7 @@ bool PeerManagerImpl::AlreadyHaveTx(const GenTxid& gtxid) const uint256& hash = gtxid.GetHash(); - { - LOCK(g_cs_orphans); - if (!gtxid.IsWtxid() && mapOrphanTransactions.count(hash)) { - return true; - } else if (gtxid.IsWtxid() && g_orphans_by_wtxid.count(hash)) { - return true; - } - } + if (m_orphanage.HaveTx(gtxid)) return true; { LOCK(m_recent_confirmed_transactions_mutex); @@ -2232,25 +2038,17 @@ void PeerManagerImpl::ProcessOrphanTx(std::set<uint256>& orphan_work_set) const uint256 orphanHash = *orphan_work_set.begin(); orphan_work_set.erase(orphan_work_set.begin()); - auto orphan_it = mapOrphanTransactions.find(orphanHash); - if (orphan_it == mapOrphanTransactions.end()) continue; + const auto [porphanTx, from_peer] = m_orphanage.GetTx(orphanHash); + if (porphanTx == nullptr) continue; - const CTransactionRef porphanTx = orphan_it->second.tx; const MempoolAcceptResult result = AcceptToMemoryPool(::ChainstateActive(), m_mempool, porphanTx, false /* bypass_limits */); const TxValidationState& state = result.m_state; if (result.m_result_type == MempoolAcceptResult::ResultType::VALID) { LogPrint(BCLog::MEMPOOL, " accepted orphan tx %s\n", orphanHash.ToString()); RelayTransaction(orphanHash, porphanTx->GetWitnessHash(), m_connman); - for (unsigned int i = 0; i < porphanTx->vout.size(); i++) { - auto it_by_prev = mapOrphanTransactionsByPrev.find(COutPoint(orphanHash, i)); - if (it_by_prev != mapOrphanTransactionsByPrev.end()) { - for (const auto& elem : it_by_prev->second) { - orphan_work_set.insert(elem->first); - } - } - } - EraseOrphanTx(orphanHash); + m_orphanage.AddChildrenToWorkSet(*porphanTx, orphan_work_set); + m_orphanage.EraseTx(orphanHash); for (const CTransactionRef& removedTx : result.m_replaced_transactions.value()) { AddToCompactExtraTransactions(removedTx); } @@ -2259,10 +2057,10 @@ void PeerManagerImpl::ProcessOrphanTx(std::set<uint256>& orphan_work_set) if (state.IsInvalid()) { LogPrint(BCLog::MEMPOOL, " invalid orphan tx %s from peer=%d. %s\n", orphanHash.ToString(), - orphan_it->second.fromPeer, + from_peer, state.ToString()); // Maybe punish peer that gave us an invalid orphan tx - MaybePunishNodeForTx(orphan_it->second.fromPeer, state); + MaybePunishNodeForTx(from_peer, state); } // Has inputs but not accepted to mempool // Probably non-standard or insufficient fee @@ -2297,7 +2095,7 @@ void PeerManagerImpl::ProcessOrphanTx(std::set<uint256>& orphan_work_set) recentRejects->insert(porphanTx->GetHash()); } } - EraseOrphanTx(orphanHash); + m_orphanage.EraseTx(orphanHash); break; } } @@ -3268,14 +3066,7 @@ void PeerManagerImpl::ProcessMessage(CNode& pfrom, const std::string& msg_type, m_txrequest.ForgetTxHash(tx.GetHash()); m_txrequest.ForgetTxHash(tx.GetWitnessHash()); RelayTransaction(tx.GetHash(), tx.GetWitnessHash(), m_connman); - for (unsigned int i = 0; i < tx.vout.size(); i++) { - auto it_by_prev = mapOrphanTransactionsByPrev.find(COutPoint(txid, i)); - if (it_by_prev != mapOrphanTransactionsByPrev.end()) { - for (const auto& elem : it_by_prev->second) { - peer->m_orphan_work_set.insert(elem->first); - } - } - } + m_orphanage.AddChildrenToWorkSet(tx, peer->m_orphan_work_set); pfrom.nLastTXTime = GetTime(); @@ -3324,17 +3115,20 @@ void PeerManagerImpl::ProcessMessage(CNode& pfrom, const std::string& msg_type, pfrom.AddKnownTx(parent_txid); if (!AlreadyHaveTx(gtxid)) AddTxAnnouncement(pfrom, gtxid, current_time); } - AddOrphanTx(ptx, pfrom.GetId()); + + if (m_orphanage.AddTx(ptx, pfrom.GetId())) { + AddToCompactExtraTransactions(ptx); + } // Once added to the orphan pool, a tx is considered AlreadyHave, and we shouldn't request it anymore. m_txrequest.ForgetTxHash(tx.GetHash()); m_txrequest.ForgetTxHash(tx.GetWitnessHash()); - // DoS prevention: do not allow mapOrphanTransactions to grow unbounded (see CVE-2012-3789) + // DoS prevention: do not allow m_orphanage to grow unbounded (see CVE-2012-3789) unsigned int nMaxOrphanTx = (unsigned int)std::max((int64_t)0, gArgs.GetArg("-maxorphantx", DEFAULT_MAX_ORPHAN_TRANSACTIONS)); - unsigned int nEvicted = LimitOrphanTxSize(nMaxOrphanTx); + unsigned int nEvicted = m_orphanage.LimitOrphans(nMaxOrphanTx); if (nEvicted > 0) { - LogPrint(BCLog::MEMPOOL, "mapOrphan overflow, removed %u tx\n", nEvicted); + LogPrint(BCLog::MEMPOOL, "orphanage overflow, removed %u tx\n", nEvicted); } } else { LogPrint(BCLog::MEMPOOL, "not keeping orphan with rejected parents %s\n",tx.GetHash().ToString()); @@ -4948,15 +4742,3 @@ bool PeerManagerImpl::SendMessages(CNode* pto) return true; } -class CNetProcessingCleanup -{ -public: - CNetProcessingCleanup() {} - ~CNetProcessingCleanup() { - // orphan transactions - mapOrphanTransactions.clear(); - mapOrphanTransactionsByPrev.clear(); - g_orphans_by_wtxid.clear(); - } -}; -static CNetProcessingCleanup instance_of_cnetprocessingcleanup; diff --git a/src/net_processing.h b/src/net_processing.h index d7be453df5..3b09907443 100644 --- a/src/net_processing.h +++ b/src/net_processing.h @@ -15,7 +15,6 @@ class CTxMemPool; class ChainstateManager; extern RecursiveMutex cs_main; -extern RecursiveMutex g_cs_orphans; /** Default for -maxorphantx, maximum number of orphan transactions kept in memory */ static const unsigned int DEFAULT_MAX_ORPHAN_TRANSACTIONS = 100; diff --git a/src/test/denialofservice_tests.cpp b/src/test/denialofservice_tests.cpp index 0d480e35ea..5906913b58 100644 --- a/src/test/denialofservice_tests.cpp +++ b/src/test/denialofservice_tests.cpp @@ -14,6 +14,7 @@ #include <script/signingprovider.h> #include <script/standard.h> #include <serialize.h> +#include <txorphanage.h> #include <util/memory.h> #include <util/string.h> #include <util/system.h> @@ -43,18 +44,6 @@ struct CConnmanTest : public CConnman { } }; -// Tests these internal-to-net_processing.cpp methods: -extern bool AddOrphanTx(const CTransactionRef& tx, NodeId peer); -extern void EraseOrphansFor(NodeId peer); -extern unsigned int LimitOrphanTxSize(unsigned int nMaxOrphans); - -struct COrphanTx { - CTransactionRef tx; - NodeId fromPeer; - int64_t nTimeExpire; -}; -extern std::map<uint256, COrphanTx> mapOrphanTransactions GUARDED_BY(g_cs_orphans); - static CService ip(uint32_t i) { struct in_addr s; @@ -295,15 +284,23 @@ BOOST_AUTO_TEST_CASE(DoS_bantime) peerLogic->FinalizeNode(dummyNode, dummy); } -static CTransactionRef RandomOrphan() +class TxOrphanageTest : public TxOrphanage { - std::map<uint256, COrphanTx>::iterator it; - LOCK2(cs_main, g_cs_orphans); - it = mapOrphanTransactions.lower_bound(InsecureRand256()); - if (it == mapOrphanTransactions.end()) - it = mapOrphanTransactions.begin(); - return it->second.tx; -} +public: + inline size_t CountOrphans() const EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans) + { + return m_orphans.size(); + } + + CTransactionRef RandomOrphan() EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans) + { + std::map<uint256, OrphanTx>::iterator it; + it = m_orphans.lower_bound(InsecureRand256()); + if (it == m_orphans.end()) + it = m_orphans.begin(); + return it->second.tx; + } +}; static void MakeNewKeyWithFastRandomContext(CKey& key) { @@ -323,11 +320,14 @@ BOOST_AUTO_TEST_CASE(DoS_mapOrphans) // signature's R and S values have leading zeros. g_insecure_rand_ctx = FastRandomContext(ArithToUint256(arith_uint256(33))); + TxOrphanageTest orphanage; CKey key; MakeNewKeyWithFastRandomContext(key); FillableSigningProvider keystore; BOOST_CHECK(keystore.AddKey(key)); + LOCK(g_cs_orphans); + // 50 orphan transactions: for (int i = 0; i < 50; i++) { @@ -340,13 +340,13 @@ BOOST_AUTO_TEST_CASE(DoS_mapOrphans) tx.vout[0].nValue = 1*CENT; tx.vout[0].scriptPubKey = GetScriptForDestination(PKHash(key.GetPubKey())); - AddOrphanTx(MakeTransactionRef(tx), i); + orphanage.AddTx(MakeTransactionRef(tx), i); } // ... and 50 that depend on other orphans: for (int i = 0; i < 50; i++) { - CTransactionRef txPrev = RandomOrphan(); + CTransactionRef txPrev = orphanage.RandomOrphan(); CMutableTransaction tx; tx.vin.resize(1); @@ -357,13 +357,13 @@ BOOST_AUTO_TEST_CASE(DoS_mapOrphans) tx.vout[0].scriptPubKey = GetScriptForDestination(PKHash(key.GetPubKey())); BOOST_CHECK(SignSignature(keystore, *txPrev, tx, 0, SIGHASH_ALL)); - AddOrphanTx(MakeTransactionRef(tx), i); + orphanage.AddTx(MakeTransactionRef(tx), i); } // This really-big orphan should be ignored: for (int i = 0; i < 10; i++) { - CTransactionRef txPrev = RandomOrphan(); + CTransactionRef txPrev = orphanage.RandomOrphan(); CMutableTransaction tx; tx.vout.resize(1); @@ -381,25 +381,24 @@ BOOST_AUTO_TEST_CASE(DoS_mapOrphans) for (unsigned int j = 1; j < tx.vin.size(); j++) tx.vin[j].scriptSig = tx.vin[0].scriptSig; - BOOST_CHECK(!AddOrphanTx(MakeTransactionRef(tx), i)); + BOOST_CHECK(!orphanage.AddTx(MakeTransactionRef(tx), i)); } - LOCK2(cs_main, g_cs_orphans); // Test EraseOrphansFor: for (NodeId i = 0; i < 3; i++) { - size_t sizeBefore = mapOrphanTransactions.size(); - EraseOrphansFor(i); - BOOST_CHECK(mapOrphanTransactions.size() < sizeBefore); + size_t sizeBefore = orphanage.CountOrphans(); + orphanage.EraseForPeer(i); + BOOST_CHECK(orphanage.CountOrphans() < sizeBefore); } // Test LimitOrphanTxSize() function: - LimitOrphanTxSize(40); - BOOST_CHECK(mapOrphanTransactions.size() <= 40); - LimitOrphanTxSize(10); - BOOST_CHECK(mapOrphanTransactions.size() <= 10); - LimitOrphanTxSize(0); - BOOST_CHECK(mapOrphanTransactions.empty()); + orphanage.LimitOrphans(40); + BOOST_CHECK(orphanage.CountOrphans() <= 40); + orphanage.LimitOrphans(10); + BOOST_CHECK(orphanage.CountOrphans() <= 10); + orphanage.LimitOrphans(0); + BOOST_CHECK(orphanage.CountOrphans() == 0); } BOOST_AUTO_TEST_SUITE_END() diff --git a/src/test/fuzz/process_message.cpp b/src/test/fuzz/process_message.cpp index e3571e15b7..0289d49ccc 100644 --- a/src/test/fuzz/process_message.cpp +++ b/src/test/fuzz/process_message.cpp @@ -18,6 +18,7 @@ #include <test/util/net.h> #include <test/util/setup_common.h> #include <test/util/validation.h> +#include <txorphanage.h> #include <util/memory.h> #include <validationinterface.h> #include <version.h> diff --git a/src/test/fuzz/process_messages.cpp b/src/test/fuzz/process_messages.cpp index f62a0c64ed..617a71ea60 100644 --- a/src/test/fuzz/process_messages.cpp +++ b/src/test/fuzz/process_messages.cpp @@ -13,6 +13,7 @@ #include <test/util/net.h> #include <test/util/setup_common.h> #include <test/util/validation.h> +#include <txorphanage.h> #include <util/memory.h> #include <validation.h> #include <validationinterface.h> diff --git a/src/txorphanage.cpp b/src/txorphanage.cpp new file mode 100644 index 0000000000..ed4783f1a5 --- /dev/null +++ b/src/txorphanage.cpp @@ -0,0 +1,202 @@ +// Copyright (c) 2021 The Bitcoin Core developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#include <txorphanage.h> + +#include <consensus/validation.h> +#include <logging.h> +#include <policy/policy.h> + +#include <cassert> + +/** Expiration time for orphan transactions in seconds */ +static constexpr int64_t ORPHAN_TX_EXPIRE_TIME = 20 * 60; +/** Minimum time between orphan transactions expire time checks in seconds */ +static constexpr int64_t ORPHAN_TX_EXPIRE_INTERVAL = 5 * 60; + +RecursiveMutex g_cs_orphans; + +bool TxOrphanage::AddTx(const CTransactionRef& tx, NodeId peer) +{ + AssertLockHeld(g_cs_orphans); + + const uint256& hash = tx->GetHash(); + if (m_orphans.count(hash)) + return false; + + // Ignore big transactions, to avoid a + // send-big-orphans memory exhaustion attack. If a peer has a legitimate + // large transaction with a missing parent then we assume + // it will rebroadcast it later, after the parent transaction(s) + // have been mined or received. + // 100 orphans, each of which is at most 100,000 bytes big is + // at most 10 megabytes of orphans and somewhat more byprev index (in the worst case): + unsigned int sz = GetTransactionWeight(*tx); + if (sz > MAX_STANDARD_TX_WEIGHT) + { + LogPrint(BCLog::MEMPOOL, "ignoring large orphan tx (size: %u, hash: %s)\n", sz, hash.ToString()); + return false; + } + + auto ret = m_orphans.emplace(hash, OrphanTx{tx, peer, GetTime() + ORPHAN_TX_EXPIRE_TIME, m_orphan_list.size()}); + assert(ret.second); + m_orphan_list.push_back(ret.first); + // Allow for lookups in the orphan pool by wtxid, as well as txid + m_wtxid_to_orphan_it.emplace(tx->GetWitnessHash(), ret.first); + for (const CTxIn& txin : tx->vin) { + m_outpoint_to_orphan_it[txin.prevout].insert(ret.first); + } + + LogPrint(BCLog::MEMPOOL, "stored orphan tx %s (mapsz %u outsz %u)\n", hash.ToString(), + m_orphans.size(), m_outpoint_to_orphan_it.size()); + return true; +} + +int TxOrphanage::EraseTx(const uint256& txid) +{ + AssertLockHeld(g_cs_orphans); + std::map<uint256, OrphanTx>::iterator it = m_orphans.find(txid); + if (it == m_orphans.end()) + return 0; + for (const CTxIn& txin : it->second.tx->vin) + { + auto itPrev = m_outpoint_to_orphan_it.find(txin.prevout); + if (itPrev == m_outpoint_to_orphan_it.end()) + continue; + itPrev->second.erase(it); + if (itPrev->second.empty()) + m_outpoint_to_orphan_it.erase(itPrev); + } + + size_t old_pos = it->second.list_pos; + assert(m_orphan_list[old_pos] == it); + if (old_pos + 1 != m_orphan_list.size()) { + // Unless we're deleting the last entry in m_orphan_list, move the last + // entry to the position we're deleting. + auto it_last = m_orphan_list.back(); + m_orphan_list[old_pos] = it_last; + it_last->second.list_pos = old_pos; + } + m_orphan_list.pop_back(); + m_wtxid_to_orphan_it.erase(it->second.tx->GetWitnessHash()); + + m_orphans.erase(it); + return 1; +} + +void TxOrphanage::EraseForPeer(NodeId peer) +{ + AssertLockHeld(g_cs_orphans); + + int nErased = 0; + std::map<uint256, OrphanTx>::iterator iter = m_orphans.begin(); + while (iter != m_orphans.end()) + { + std::map<uint256, OrphanTx>::iterator maybeErase = iter++; // increment to avoid iterator becoming invalid + if (maybeErase->second.fromPeer == peer) + { + nErased += EraseTx(maybeErase->second.tx->GetHash()); + } + } + if (nErased > 0) LogPrint(BCLog::MEMPOOL, "Erased %d orphan tx from peer=%d\n", nErased, peer); +} + +unsigned int TxOrphanage::LimitOrphans(unsigned int max_orphans) +{ + AssertLockHeld(g_cs_orphans); + + unsigned int nEvicted = 0; + static int64_t nNextSweep; + int64_t nNow = GetTime(); + if (nNextSweep <= nNow) { + // Sweep out expired orphan pool entries: + int nErased = 0; + int64_t nMinExpTime = nNow + ORPHAN_TX_EXPIRE_TIME - ORPHAN_TX_EXPIRE_INTERVAL; + std::map<uint256, OrphanTx>::iterator iter = m_orphans.begin(); + while (iter != m_orphans.end()) + { + std::map<uint256, OrphanTx>::iterator maybeErase = iter++; + if (maybeErase->second.nTimeExpire <= nNow) { + nErased += EraseTx(maybeErase->second.tx->GetHash()); + } else { + nMinExpTime = std::min(maybeErase->second.nTimeExpire, nMinExpTime); + } + } + // Sweep again 5 minutes after the next entry that expires in order to batch the linear scan. + nNextSweep = nMinExpTime + ORPHAN_TX_EXPIRE_INTERVAL; + if (nErased > 0) LogPrint(BCLog::MEMPOOL, "Erased %d orphan tx due to expiration\n", nErased); + } + FastRandomContext rng; + while (m_orphans.size() > max_orphans) + { + // Evict a random orphan: + size_t randompos = rng.randrange(m_orphan_list.size()); + EraseTx(m_orphan_list[randompos]->first); + ++nEvicted; + } + return nEvicted; +} + +void TxOrphanage::AddChildrenToWorkSet(const CTransaction& tx, std::set<uint256>& orphan_work_set) const +{ + AssertLockHeld(g_cs_orphans); + for (unsigned int i = 0; i < tx.vout.size(); i++) { + const auto it_by_prev = m_outpoint_to_orphan_it.find(COutPoint(tx.GetHash(), i)); + if (it_by_prev != m_outpoint_to_orphan_it.end()) { + for (const auto& elem : it_by_prev->second) { + orphan_work_set.insert(elem->first); + } + } + } +} + +bool TxOrphanage::HaveTx(const GenTxid& gtxid) const +{ + LOCK(g_cs_orphans); + if (gtxid.IsWtxid()) { + return m_wtxid_to_orphan_it.count(gtxid.GetHash()); + } else { + return m_orphans.count(gtxid.GetHash()); + } +} + +std::pair<CTransactionRef, NodeId> TxOrphanage::GetTx(const uint256& txid) const +{ + AssertLockHeld(g_cs_orphans); + + const auto it = m_orphans.find(txid); + if (it == m_orphans.end()) return {nullptr, -1}; + return {it->second.tx, it->second.fromPeer}; +} + +void TxOrphanage::EraseForBlock(const CBlock& block) +{ + LOCK(g_cs_orphans); + + std::vector<uint256> vOrphanErase; + + for (const CTransactionRef& ptx : block.vtx) { + const CTransaction& tx = *ptx; + + // Which orphan pool entries must we evict? + for (const auto& txin : tx.vin) { + auto itByPrev = m_outpoint_to_orphan_it.find(txin.prevout); + if (itByPrev == m_outpoint_to_orphan_it.end()) continue; + for (auto mi = itByPrev->second.begin(); mi != itByPrev->second.end(); ++mi) { + const CTransaction& orphanTx = *(*mi)->second.tx; + const uint256& orphanHash = orphanTx.GetHash(); + vOrphanErase.push_back(orphanHash); + } + } + } + + // Erase orphan transactions included or precluded by this block + if (vOrphanErase.size()) { + int nErased = 0; + for (const uint256& orphanHash : vOrphanErase) { + nErased += EraseTx(orphanHash); + } + LogPrint(BCLog::MEMPOOL, "Erased %d orphan tx included or conflicted by block\n", nErased); + } +} diff --git a/src/txorphanage.h b/src/txorphanage.h new file mode 100644 index 0000000000..df55cdb3be --- /dev/null +++ b/src/txorphanage.h @@ -0,0 +1,85 @@ +// Copyright (c) 2021 The Bitcoin Core developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#ifndef BITCOIN_TXORPHANAGE_H +#define BITCOIN_TXORPHANAGE_H + +#include <net.h> +#include <primitives/block.h> +#include <primitives/transaction.h> +#include <sync.h> + +/** Guards orphan transactions and extra txs for compact blocks */ +extern RecursiveMutex g_cs_orphans; + +/** A class to track orphan transactions (failed on TX_MISSING_INPUTS) + * Since we cannot distinguish orphans from bad transactions with + * non-existent inputs, we heavily limit the number of orphans + * we keep and the duration we keep them for. + */ +class TxOrphanage { +public: + /** Add a new orphan transaction */ + bool AddTx(const CTransactionRef& tx, NodeId peer) EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans); + + /** Check if we already have an orphan transaction (by txid or wtxid) */ + bool HaveTx(const GenTxid& gtxid) const EXCLUSIVE_LOCKS_REQUIRED(!g_cs_orphans); + + /** Get an orphan transaction and its orginating peer + * (Transaction ref will be nullptr if not found) + */ + std::pair<CTransactionRef, NodeId> GetTx(const uint256& txid) const EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans); + + /** Erase an orphan by txid */ + int EraseTx(const uint256& txid) EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans); + + /** Erase all orphans announced by a peer (eg, after that peer disconnects) */ + void EraseForPeer(NodeId peer) EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans); + + /** Erase all orphans included in or invalidated by a new block */ + void EraseForBlock(const CBlock& block) EXCLUSIVE_LOCKS_REQUIRED(!g_cs_orphans); + + /** Limit the orphanage to the given maximum */ + unsigned int LimitOrphans(unsigned int max_orphans) EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans); + + /** Add any orphans that list a particular tx as a parent into a peer's work set + * (ie orphans that may have found their final missing parent, and so should be reconsidered for the mempool) */ + void AddChildrenToWorkSet(const CTransaction& tx, std::set<uint256>& orphan_work_set) const EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans); + +protected: + struct OrphanTx { + CTransactionRef tx; + NodeId fromPeer; + int64_t nTimeExpire; + size_t list_pos; + }; + + /** Map from txid to orphan transaction record. Limited by + * -maxorphantx/DEFAULT_MAX_ORPHAN_TRANSACTIONS */ + std::map<uint256, OrphanTx> m_orphans GUARDED_BY(g_cs_orphans); + + using OrphanMap = decltype(m_orphans); + + struct IteratorComparator + { + template<typename I> + bool operator()(const I& a, const I& b) const + { + return &(*a) < &(*b); + } + }; + + /** Index from the parents' COutPoint into the m_orphans. Used + * to remove orphan transactions from the m_orphans */ + std::map<COutPoint, std::set<OrphanMap::iterator, IteratorComparator>> m_outpoint_to_orphan_it GUARDED_BY(g_cs_orphans); + + /** Orphan transactions in vector for quick random eviction */ + std::vector<OrphanMap::iterator> m_orphan_list GUARDED_BY(g_cs_orphans); + + /** Index from wtxid into the m_orphans to lookup orphan + * transactions using their witness ids. */ + std::map<uint256, OrphanMap::iterator> m_wtxid_to_orphan_it GUARDED_BY(g_cs_orphans); +}; + +#endif // BITCOIN_TXORPHANAGE_H |