From 1b0bcc5f9573406bff1c3ffaf73826b0142d23cc Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Fri, 10 Jun 2016 16:07:14 +0200 Subject: Track orphan by prev COutPoint rather than prev hash --- src/main.cpp | 58 ++++++++++++++++++++++++++++++++++++---------------------- 1 file changed, 36 insertions(+), 22 deletions(-) (limited to 'src/main.cpp') diff --git a/src/main.cpp b/src/main.cpp index 6d006e8789..17867c869c 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -88,12 +88,21 @@ CAmount maxTxFee = DEFAULT_TRANSACTION_MAXFEE; CTxMemPool mempool(::minRelayTxFee); FeeFilterRounder filterRounder(::minRelayTxFee); +struct IteratorComparator +{ + template + bool operator()(const I& a, const I& b) + { + return &(*a) < &(*b); + } +}; + struct COrphanTx { CTransaction tx; NodeId fromPeer; }; map mapOrphanTransactions GUARDED_BY(cs_main); -map > mapOrphanTransactionsByPrev GUARDED_BY(cs_main); +map::iterator, IteratorComparator>> mapOrphanTransactionsByPrev GUARDED_BY(cs_main); void EraseOrphansFor(NodeId peer) EXCLUSIVE_LOCKS_REQUIRED(cs_main); /** @@ -632,31 +641,33 @@ bool AddOrphanTx(const CTransaction& tx, NodeId peer) EXCLUSIVE_LOCKS_REQUIRED(c return false; } - mapOrphanTransactions[hash].tx = tx; - mapOrphanTransactions[hash].fromPeer = peer; - BOOST_FOREACH(const CTxIn& txin, tx.vin) - mapOrphanTransactionsByPrev[txin.prevout.hash].insert(hash); + auto ret = mapOrphanTransactions.emplace(hash, COrphanTx{tx, peer}); + assert(ret.second); + BOOST_FOREACH(const CTxIn& txin, tx.vin) { + mapOrphanTransactionsByPrev[txin.prevout].insert(ret.first); + } - LogPrint("mempool", "stored orphan tx %s (mapsz %u prevsz %u)\n", hash.ToString(), + LogPrint("mempool", "stored orphan tx %s (mapsz %u outsz %u)\n", hash.ToString(), mapOrphanTransactions.size(), mapOrphanTransactionsByPrev.size()); return true; } -void static EraseOrphanTx(uint256 hash) EXCLUSIVE_LOCKS_REQUIRED(cs_main) +int static EraseOrphanTx(uint256 hash) EXCLUSIVE_LOCKS_REQUIRED(cs_main) { map::iterator it = mapOrphanTransactions.find(hash); if (it == mapOrphanTransactions.end()) - return; + return 0; BOOST_FOREACH(const CTxIn& txin, it->second.tx.vin) { - map >::iterator itPrev = mapOrphanTransactionsByPrev.find(txin.prevout.hash); + auto itPrev = mapOrphanTransactionsByPrev.find(txin.prevout); if (itPrev == mapOrphanTransactionsByPrev.end()) continue; - itPrev->second.erase(hash); + itPrev->second.erase(it); if (itPrev->second.empty()) mapOrphanTransactionsByPrev.erase(itPrev); } mapOrphanTransactions.erase(it); + return 1; } void EraseOrphansFor(NodeId peer) @@ -668,8 +679,7 @@ void EraseOrphansFor(NodeId peer) map::iterator maybeErase = iter++; // increment to avoid iterator becoming invalid if (maybeErase->second.fromPeer == peer) { - EraseOrphanTx(maybeErase->second.tx.GetHash()); - ++nErased; + nErased += EraseOrphanTx(maybeErase->second.tx.GetHash()); } } if (nErased > 0) LogPrint("mempool", "Erased %d orphan tx from peer %d\n", nErased, peer); @@ -5019,7 +5029,7 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv, return true; } - vector vWorkQueue; + deque vWorkQueue; vector vEraseQueue; CTransaction tx; vRecv >> tx; @@ -5038,7 +5048,9 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv, if (!AlreadyHave(inv) && AcceptToMemoryPool(mempool, state, tx, true, &fMissingInputs)) { mempool.check(pcoinsTip); RelayTransaction(tx); - vWorkQueue.push_back(inv.hash); + for (unsigned int i = 0; i < tx.vout.size(); i++) { + vWorkQueue.emplace_back(inv.hash, i); + } LogPrint("mempool", "AcceptToMemoryPool: peer=%d: accepted %s (poolsz %u txn, %u kB)\n", pfrom->id, @@ -5047,18 +5059,18 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv, // Recursively process any orphan transactions that depended on this one set setMisbehaving; - for (unsigned int i = 0; i < vWorkQueue.size(); i++) - { - map >::iterator itByPrev = mapOrphanTransactionsByPrev.find(vWorkQueue[i]); + while (!vWorkQueue.empty()) { + auto itByPrev = mapOrphanTransactionsByPrev.find(vWorkQueue.front()); + vWorkQueue.pop_front(); if (itByPrev == mapOrphanTransactionsByPrev.end()) continue; - for (set::iterator mi = itByPrev->second.begin(); + for (auto mi = itByPrev->second.begin(); mi != itByPrev->second.end(); ++mi) { - const uint256& orphanHash = *mi; - const CTransaction& orphanTx = mapOrphanTransactions[orphanHash].tx; - NodeId fromPeer = mapOrphanTransactions[orphanHash].fromPeer; + const CTransaction& orphanTx = (*mi)->second.tx; + const uint256& orphanHash = orphanTx.GetHash(); + NodeId fromPeer = (*mi)->second.fromPeer; bool fMissingInputs2 = false; // Use a dummy CValidationState so someone can't setup nodes to counter-DoS based on orphan // resolution (that is, feeding people an invalid transaction based on LegitTxX in order to get @@ -5071,7 +5083,9 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv, if (AcceptToMemoryPool(mempool, stateDummy, orphanTx, true, &fMissingInputs2)) { LogPrint("mempool", " accepted orphan tx %s\n", orphanHash.ToString()); RelayTransaction(orphanTx); - vWorkQueue.push_back(orphanHash); + for (unsigned int i = 0; i < orphanTx.vout.size(); i++) { + vWorkQueue.emplace_back(orphanHash, i); + } vEraseQueue.push_back(orphanHash); } else if (!fMissingInputs2) -- cgit v1.2.3 From db0ffe80a0919653f058ab0f1fc735f46bb902f3 Mon Sep 17 00:00:00 2001 From: Gregory Maxwell Date: Fri, 10 Jun 2016 20:41:49 +0000 Subject: This eliminates the primary leak that causes the orphan map to always grow to its maximum size. This does not go so far as to attempt to connect orphans made connectable by a new block. Keeping the orphan map less full helps improve the reliability of relaying chains of transactions. --- src/main.cpp | 21 +++++++++++++++++++++ 1 file changed, 21 insertions(+) (limited to 'src/main.cpp') diff --git a/src/main.cpp b/src/main.cpp index 17867c869c..c80a4ac922 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -2345,6 +2345,7 @@ bool ConnectBlock(const CBlock& block, CValidationState& state, CBlockIndex* pin CCheckQueueControl control(fScriptChecks && nScriptCheckThreads ? &scriptcheckqueue : NULL); + std::vector vOrphanErase; std::vector prevheights; CAmount nFees = 0; int nInputs = 0; @@ -2377,6 +2378,17 @@ bool ConnectBlock(const CBlock& block, CValidationState& state, CBlockIndex* pin prevheights[j] = view.AccessCoins(tx.vin[j].prevout.hash)->nHeight; } + // Which orphan pool entries must we evict? + for (size_t j = 0; j < tx.vin.size(); j++) { + auto itByPrev = mapOrphanTransactionsByPrev.find(tx.vin[j].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); + } + } + if (!SequenceLocks(tx, nLockTimeFlags, &prevheights, *pindex)) { return state.DoS(100, error("%s: contains a non-BIP68-final transaction", __func__), REJECT_INVALID, "bad-txns-nonfinal"); @@ -2464,6 +2476,15 @@ bool ConnectBlock(const CBlock& block, CValidationState& state, CBlockIndex* pin GetMainSignals().UpdatedTransaction(hashPrevBestCoinBase); hashPrevBestCoinBase = block.vtx[0].GetHash(); + // Erase orphan transactions include or precluded by this block + if (vOrphanErase.size()) { + int nErased = 0; + BOOST_FOREACH(uint256 &orphanHash, vOrphanErase) { + nErased += EraseOrphanTx(orphanHash); + } + LogPrint("mempool", "Erased %d orphan tx included or conflicted by block\n", nErased); + } + int64_t nTime6 = GetTimeMicros(); nTimeCallbacks += nTime6 - nTime5; LogPrint("bench", " - Callbacks: %.2fms [%.2fs]\n", 0.001 * (nTime6 - nTime5), nTimeCallbacks * 0.000001); -- cgit v1.2.3 From 11cc143895e730002749f0881c4c95635fa54bd5 Mon Sep 17 00:00:00 2001 From: Gregory Maxwell Date: Sat, 11 Jun 2016 00:26:16 +0000 Subject: Adds an expiration time for orphan tx. This prevents higher order orphans and other junk from holding positions in the orphan map. Parents delayed twenty minutes are more are unlikely to ever arrive. The freed space will improve the orphan matching success rate for other transactions. --- src/main.cpp | 23 ++++++++++++++++++++++- 1 file changed, 22 insertions(+), 1 deletion(-) (limited to 'src/main.cpp') diff --git a/src/main.cpp b/src/main.cpp index c80a4ac922..44d96d614e 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -100,6 +100,7 @@ struct IteratorComparator struct COrphanTx { CTransaction tx; NodeId fromPeer; + int64_t nTimeExpire; }; map mapOrphanTransactions GUARDED_BY(cs_main); map::iterator, IteratorComparator>> mapOrphanTransactionsByPrev GUARDED_BY(cs_main); @@ -641,7 +642,7 @@ bool AddOrphanTx(const CTransaction& tx, NodeId peer) EXCLUSIVE_LOCKS_REQUIRED(c return false; } - auto ret = mapOrphanTransactions.emplace(hash, COrphanTx{tx, peer}); + auto ret = mapOrphanTransactions.emplace(hash, COrphanTx{tx, peer, GetTime() + ORPHAN_TX_EXPIRE_TIME}); assert(ret.second); BOOST_FOREACH(const CTxIn& txin, tx.vin) { mapOrphanTransactionsByPrev[txin.prevout].insert(ret.first); @@ -689,6 +690,26 @@ void EraseOrphansFor(NodeId peer) unsigned int LimitOrphanTxSize(unsigned int nMaxOrphans) EXCLUSIVE_LOCKS_REQUIRED(cs_main) { 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; + map::iterator iter = mapOrphanTransactions.begin(); + while (iter != mapOrphanTransactions.end()) + { + map::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("mempool", "Erased %d orphan tx due to expiration\n", nErased); + } while (mapOrphanTransactions.size() > nMaxOrphans) { // Evict a random orphan: -- cgit v1.2.3 From 8c99d1b525562ab3b733e9d7ef770882646bad5c Mon Sep 17 00:00:00 2001 From: Gregory Maxwell Date: Mon, 13 Jun 2016 17:27:44 +0000 Subject: Treat orphans as implicit inv for parents, discard when parents rejected. An orphan whos parents were rejected is never going to connect, so there is little utility in keeping it. Orphans also helpfully tell us what we're missing, so go ahead and treat it as INVed. --- src/main.cpp | 28 ++++++++++++++++++++++------ 1 file changed, 22 insertions(+), 6 deletions(-) (limited to 'src/main.cpp') diff --git a/src/main.cpp b/src/main.cpp index 44d96d614e..6a2290bc05 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -5156,13 +5156,29 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv, } else if (fMissingInputs) { - AddOrphanTx(tx, pfrom->GetId()); + bool fRejectedParents = false; // It may be the case that the orphans parents have all been rejected + BOOST_FOREACH(const CTxIn& txin, tx.vin) { + if (recentRejects->contains(txin.prevout.hash)) { + fRejectedParents = true; + break; + } + } + if (!fRejectedParents) { + BOOST_FOREACH(const CTxIn& txin, tx.vin) { + CInv inv(MSG_TX, txin.prevout.hash); + pfrom->AddInventoryKnown(inv); + if (!AlreadyHave(inv)) pfrom->AskFor(inv); + } + AddOrphanTx(tx, pfrom->GetId()); - // DoS prevention: do not allow mapOrphanTransactions to grow unbounded - unsigned int nMaxOrphanTx = (unsigned int)std::max((int64_t)0, GetArg("-maxorphantx", DEFAULT_MAX_ORPHAN_TRANSACTIONS)); - unsigned int nEvicted = LimitOrphanTxSize(nMaxOrphanTx); - if (nEvicted > 0) - LogPrint("mempool", "mapOrphan overflow, removed %u tx\n", nEvicted); + // DoS prevention: do not allow mapOrphanTransactions to grow unbounded + unsigned int nMaxOrphanTx = (unsigned int)std::max((int64_t)0, GetArg("-maxorphantx", DEFAULT_MAX_ORPHAN_TRANSACTIONS)); + unsigned int nEvicted = LimitOrphanTxSize(nMaxOrphanTx); + if (nEvicted > 0) + LogPrint("mempool", "mapOrphan overflow, removed %u tx\n", nEvicted); + } else { + LogPrint("mempool", "not keeping orphan with rejected parents %s\n",tx.GetHash().ToString()); + } } else { assert(recentRejects); recentRejects->insert(tx.GetHash()); -- cgit v1.2.3 From 54326a6808a7026eef9d3a26f91f93b77f00a793 Mon Sep 17 00:00:00 2001 From: Gregory Maxwell Date: Sat, 11 Jun 2016 00:28:48 +0000 Subject: Increase maximum orphan size to 100,000 bytes. Although this increases node memory usage in the worst case by perhaps 30MB, the current behavior causes severe issues with dependent tx relay. --- src/main.cpp | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'src/main.cpp') diff --git a/src/main.cpp b/src/main.cpp index 6a2290bc05..d4ab32744f 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -633,10 +633,10 @@ bool AddOrphanTx(const CTransaction& tx, NodeId peer) EXCLUSIVE_LOCKS_REQUIRED(c // large transaction with a missing parent then we assume // it will rebroadcast it later, after the parent transaction(s) // have been mined or received. - // 10,000 orphans, each of which is at most 5,000 bytes big is - // at most 500 megabytes of orphans: + // 100 orphans, each of which is at most 99,999 bytes big is + // at most 10 megabytes of orphans and somewhat more byprev index (in the worst case): unsigned int sz = tx.GetSerializeSize(SER_NETWORK, CTransaction::CURRENT_VERSION); - if (sz > 5000) + if (sz >= MAX_STANDARD_TX_SIZE) { LogPrint("mempool", "ignoring large orphan tx (size: %u, hash: %s)\n", sz, hash.ToString()); return false; -- cgit v1.2.3