aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/init.cpp4
-rw-r--r--src/main.cpp27
-rw-r--r--src/main.h8
-rw-r--r--src/memusage.h18
-rw-r--r--src/miner.cpp8
-rw-r--r--src/rpcblockchain.cpp11
-rw-r--r--src/test/mempool_tests.cpp181
-rw-r--r--src/txmempool.cpp501
-rw-r--r--src/txmempool.h307
9 files changed, 990 insertions, 75 deletions
diff --git a/src/init.cpp b/src/init.cpp
index f03388120c..9f1c1f6864 100644
--- a/src/init.cpp
+++ b/src/init.cpp
@@ -411,6 +411,10 @@ std::string HelpMessage(HelpMessageMode mode)
strUsage += HelpMessageOpt("-fuzzmessagestest=<n>", "Randomly fuzz 1 of every <n> network messages");
strUsage += HelpMessageOpt("-flushwallet", strprintf("Run a thread to flush wallet periodically (default: %u)", 1));
strUsage += HelpMessageOpt("-stopafterblockimport", strprintf("Stop running after importing blocks from disk (default: %u)", 0));
+ strUsage += HelpMessageOpt("-limitancestorcount=<n>", strprintf("Do not accept transactions if number of in-mempool ancestors is <n> or more (default: %u)", DEFAULT_ANCESTOR_LIMIT));
+ strUsage += HelpMessageOpt("-limitancestorsize=<n>", strprintf("Do not accept transactions whose size with all in-mempool ancestors exceeds <n> kilobytes (default: %u)", DEFAULT_ANCESTOR_SIZE_LIMIT));
+ strUsage += HelpMessageOpt("-limitdescendantcount=<n>", strprintf("Do not accept transactions if any ancestor would have <n> or more in-mempool descendants (default: %u)", DEFAULT_DESCENDANT_LIMIT));
+ strUsage += HelpMessageOpt("-limitdescendantsize=<n>", strprintf("Do not accept transactions if any ancestor would have more than <n> kilobytes of in-mempool descendants (default: %u).", DEFAULT_DESCENDANT_SIZE_LIMIT));
}
string debugCategories = "addrman, alert, bench, coindb, db, lock, rand, rpc, selectcoins, mempool, mempoolrej, net, proxy, prune, http"; // Don't translate these and qt below
if (mode == HMM_BITCOIN_QT)
diff --git a/src/main.cpp b/src/main.cpp
index 27278b977a..2a24d38e52 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -921,6 +921,17 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa
REJECT_HIGHFEE, "absurdly-high-fee",
strprintf("%d > %d", nFees, ::minRelayTxFee.GetFee(nSize) * 10000));
+ // Calculate in-mempool ancestors, up to a limit.
+ CTxMemPool::setEntries setAncestors;
+ size_t nLimitAncestors = GetArg("-limitancestorcount", DEFAULT_ANCESTOR_LIMIT);
+ size_t nLimitAncestorSize = GetArg("-limitancestorsize", DEFAULT_ANCESTOR_SIZE_LIMIT)*1000;
+ size_t nLimitDescendants = GetArg("-limitdescendantcount", DEFAULT_DESCENDANT_LIMIT);
+ size_t nLimitDescendantSize = GetArg("-limitdescendantsize", DEFAULT_DESCENDANT_SIZE_LIMIT)*1000;
+ std::string errString;
+ if (!pool.CalculateMemPoolAncestors(entry, setAncestors, nLimitAncestors, nLimitAncestorSize, nLimitDescendants, nLimitDescendantSize, errString)) {
+ return state.DoS(0, false, REJECT_NONSTANDARD, "too-long-mempool-chain", false, errString);
+ }
+
// Check against previous transactions
// This is done last to help prevent CPU exhaustion denial-of-service attacks.
if (!CheckInputs(tx, state, view, true, STANDARD_SCRIPT_VERIFY_FLAGS, true))
@@ -942,7 +953,7 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa
}
// Store transaction in memory
- pool.addUnchecked(hash, entry, !IsInitialBlockDownload());
+ pool.addUnchecked(hash, entry, setAncestors, !IsInitialBlockDownload());
}
SyncWithWallets(tx, NULL);
@@ -2033,13 +2044,23 @@ bool static DisconnectTip(CValidationState &state) {
if (!FlushStateToDisk(state, FLUSH_STATE_IF_NEEDED))
return false;
// Resurrect mempool transactions from the disconnected block.
+ std::vector<uint256> vHashUpdate;
BOOST_FOREACH(const CTransaction &tx, block.vtx) {
// ignore validation errors in resurrected transactions
list<CTransaction> removed;
CValidationState stateDummy;
- if (tx.IsCoinBase() || !AcceptToMemoryPool(mempool, stateDummy, tx, false, NULL))
+ if (tx.IsCoinBase() || !AcceptToMemoryPool(mempool, stateDummy, tx, false, NULL)) {
mempool.remove(tx, removed, true);
+ } else if (mempool.exists(tx.GetHash())) {
+ vHashUpdate.push_back(tx.GetHash());
+ }
}
+ // AcceptToMemoryPool/addUnchecked all assume that new mempool entries have
+ // no in-mempool children, which is generally not true when adding
+ // previously-confirmed transactions back to the mempool.
+ // UpdateTransactionsFromBlock finds descendants of any transactions in this
+ // block that were added back and cleans up the mempool state.
+ mempool.UpdateTransactionsFromBlock(vHashUpdate);
mempool.removeCoinbaseSpends(pcoinsTip, pindexDelete->nHeight);
mempool.check(pcoinsTip);
// Update chainActive and related variables.
@@ -4258,7 +4279,7 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv,
LogPrint("mempool", "AcceptToMemoryPool: peer=%d %s: accepted %s (poolsz %u)\n",
pfrom->id, pfrom->cleanSubVer,
tx.GetHash().ToString(),
- mempool.mapTx.size());
+ mempool.size());
// Recursively process any orphan transactions that depended on this one
set<NodeId> setMisbehaving;
diff --git a/src/main.h b/src/main.h
index e3479b4b3b..a6001eed8f 100644
--- a/src/main.h
+++ b/src/main.h
@@ -43,6 +43,14 @@ struct CNodeStateStats;
static const bool DEFAULT_ALERTS = true;
/** Default for -maxorphantx, maximum number of orphan transactions kept in memory */
static const unsigned int DEFAULT_MAX_ORPHAN_TRANSACTIONS = 100;
+/** Default for -limitancestorcount, max number of in-mempool ancestors */
+static const unsigned int DEFAULT_ANCESTOR_LIMIT = 100;
+/** Default for -limitancestorsize, maximum kilobytes of tx + all in-mempool ancestors */
+static const unsigned int DEFAULT_ANCESTOR_SIZE_LIMIT = 900;
+/** Default for -limitdescendantcount, max number of in-mempool descendants */
+static const unsigned int DEFAULT_DESCENDANT_LIMIT = 1000;
+/** Default for -limitdescendantsize, maximum kilobytes of in-mempool descendants */
+static const unsigned int DEFAULT_DESCENDANT_SIZE_LIMIT = 2500;
/** The maximum size of a blk?????.dat file (since 0.8) */
static const unsigned int MAX_BLOCKFILE_SIZE = 0x8000000; // 128 MiB
/** The pre-allocation chunk size for blk?????.dat files (since 0.8) */
diff --git a/src/memusage.h b/src/memusage.h
index be3964df1b..b475c3313b 100644
--- a/src/memusage.h
+++ b/src/memusage.h
@@ -74,18 +74,30 @@ static inline size_t DynamicUsage(const std::vector<X>& v)
return MallocUsage(v.capacity() * sizeof(X));
}
-template<typename X>
-static inline size_t DynamicUsage(const std::set<X>& s)
+template<typename X, typename Y>
+static inline size_t DynamicUsage(const std::set<X, Y>& s)
{
return MallocUsage(sizeof(stl_tree_node<X>)) * s.size();
}
template<typename X, typename Y>
-static inline size_t DynamicUsage(const std::map<X, Y>& m)
+static inline size_t IncrementalDynamicUsage(const std::set<X, Y>& s)
+{
+ return MallocUsage(sizeof(stl_tree_node<X>));
+}
+
+template<typename X, typename Y, typename Z>
+static inline size_t DynamicUsage(const std::map<X, Y, Z>& m)
{
return MallocUsage(sizeof(stl_tree_node<std::pair<const X, Y> >)) * m.size();
}
+template<typename X, typename Y, typename Z>
+static inline size_t IncrementalDynamicUsage(const std::map<X, Y, Z>& m)
+{
+ return MallocUsage(sizeof(stl_tree_node<std::pair<const X, Y> >));
+}
+
// Boost data structures
template<typename X>
diff --git a/src/miner.cpp b/src/miner.cpp
index 9dd1d459b5..b2a356e52d 100644
--- a/src/miner.cpp
+++ b/src/miner.cpp
@@ -158,10 +158,10 @@ CBlockTemplate* CreateNewBlock(const CScript& scriptPubKeyIn)
// This vector will be sorted into a priority queue:
vector<TxPriority> vecPriority;
vecPriority.reserve(mempool.mapTx.size());
- for (map<uint256, CTxMemPoolEntry>::iterator mi = mempool.mapTx.begin();
+ for (CTxMemPool::indexed_transaction_set::iterator mi = mempool.mapTx.begin();
mi != mempool.mapTx.end(); ++mi)
{
- const CTransaction& tx = mi->second.GetTx();
+ const CTransaction& tx = mi->GetTx();
if (tx.IsCoinBase() || !IsFinalTx(tx, nHeight, pblock->nTime))
continue;
@@ -196,7 +196,7 @@ CBlockTemplate* CreateNewBlock(const CScript& scriptPubKeyIn)
}
mapDependers[txin.prevout.hash].push_back(porphan);
porphan->setDependsOn.insert(txin.prevout.hash);
- nTotalIn += mempool.mapTx[txin.prevout.hash].GetTx().vout[txin.prevout.n].nValue;
+ nTotalIn += mempool.mapTx.find(txin.prevout.hash)->GetTx().vout[txin.prevout.n].nValue;
continue;
}
const CCoins* coins = view.AccessCoins(txin.prevout.hash);
@@ -226,7 +226,7 @@ CBlockTemplate* CreateNewBlock(const CScript& scriptPubKeyIn)
porphan->feeRate = feeRate;
}
else
- vecPriority.push_back(TxPriority(dPriority, feeRate, &mi->second.GetTx()));
+ vecPriority.push_back(TxPriority(dPriority, feeRate, &(mi->GetTx())));
}
// Collect transactions into block
diff --git a/src/rpcblockchain.cpp b/src/rpcblockchain.cpp
index e6751de96b..1c201ef99d 100644
--- a/src/rpcblockchain.cpp
+++ b/src/rpcblockchain.cpp
@@ -181,10 +181,9 @@ UniValue mempoolToJSON(bool fVerbose = false)
{
LOCK(mempool.cs);
UniValue o(UniValue::VOBJ);
- BOOST_FOREACH(const PAIRTYPE(uint256, CTxMemPoolEntry)& entry, mempool.mapTx)
+ BOOST_FOREACH(const CTxMemPoolEntry& e, mempool.mapTx)
{
- const uint256& hash = entry.first;
- const CTxMemPoolEntry& e = entry.second;
+ const uint256& hash = e.GetTx().GetHash();
UniValue info(UniValue::VOBJ);
info.push_back(Pair("size", (int)e.GetTxSize()));
info.push_back(Pair("fee", ValueFromAmount(e.GetFee())));
@@ -192,6 +191,9 @@ UniValue mempoolToJSON(bool fVerbose = false)
info.push_back(Pair("height", (int)e.GetHeight()));
info.push_back(Pair("startingpriority", e.GetPriority(e.GetHeight())));
info.push_back(Pair("currentpriority", e.GetPriority(chainActive.Height())));
+ info.push_back(Pair("descendantcount", e.GetCountWithDescendants()));
+ info.push_back(Pair("descendantsize", e.GetSizeWithDescendants()));
+ info.push_back(Pair("descendantfees", e.GetFeesWithDescendants()));
const CTransaction& tx = e.GetTx();
set<string> setDepends;
BOOST_FOREACH(const CTxIn& txin, tx.vin)
@@ -246,6 +248,9 @@ UniValue getrawmempool(const UniValue& params, bool fHelp)
" \"height\" : n, (numeric) block height when transaction entered pool\n"
" \"startingpriority\" : n, (numeric) priority when transaction entered pool\n"
" \"currentpriority\" : n, (numeric) transaction priority now\n"
+ " \"descendantcount\" : n, (numeric) number of in-mempool descendant transactions (including this one)\n"
+ " \"descendantsize\" : n, (numeric) size of in-mempool descendants (including this one)\n"
+ " \"descendantfees\" : n, (numeric) fees of in-mempool descendants (including this one)\n"
" \"depends\" : [ (array) unconfirmed transactions used as inputs for this transaction\n"
" \"transactionid\", (string) parent transaction id\n"
" ... ]\n"
diff --git a/src/test/mempool_tests.cpp b/src/test/mempool_tests.cpp
index 2439689d7f..5bf1e98e8f 100644
--- a/src/test/mempool_tests.cpp
+++ b/src/test/mempool_tests.cpp
@@ -9,6 +9,7 @@
#include <boost/test/unit_test.hpp>
#include <list>
+#include <vector>
BOOST_FIXTURE_TEST_SUITE(mempool_tests, TestingSetup)
@@ -100,4 +101,184 @@ BOOST_AUTO_TEST_CASE(MempoolRemoveTest)
removed.clear();
}
+void CheckSort(CTxMemPool &pool, std::vector<std::string> &sortedOrder)
+{
+ BOOST_CHECK_EQUAL(pool.size(), sortedOrder.size());
+ CTxMemPool::indexed_transaction_set::nth_index<1>::type::iterator it = pool.mapTx.get<1>().begin();
+ int count=0;
+ for (; it != pool.mapTx.get<1>().end(); ++it, ++count) {
+ BOOST_CHECK_EQUAL(it->GetTx().GetHash().ToString(), sortedOrder[count]);
+ }
+}
+
+BOOST_AUTO_TEST_CASE(MempoolIndexingTest)
+{
+ CTxMemPool pool(CFeeRate(0));
+
+ /* 3rd highest fee */
+ CMutableTransaction tx1 = CMutableTransaction();
+ tx1.vout.resize(1);
+ tx1.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
+ tx1.vout[0].nValue = 10 * COIN;
+ pool.addUnchecked(tx1.GetHash(), CTxMemPoolEntry(tx1, 10000LL, 0, 10.0, 1, true));
+
+ /* highest fee */
+ CMutableTransaction tx2 = CMutableTransaction();
+ tx2.vout.resize(1);
+ tx2.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
+ tx2.vout[0].nValue = 2 * COIN;
+ pool.addUnchecked(tx2.GetHash(), CTxMemPoolEntry(tx2, 20000LL, 0, 9.0, 1, true));
+
+ /* lowest fee */
+ CMutableTransaction tx3 = CMutableTransaction();
+ tx3.vout.resize(1);
+ tx3.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
+ tx3.vout[0].nValue = 5 * COIN;
+ pool.addUnchecked(tx3.GetHash(), CTxMemPoolEntry(tx3, 0LL, 0, 100.0, 1, true));
+
+ /* 2nd highest fee */
+ CMutableTransaction tx4 = CMutableTransaction();
+ tx4.vout.resize(1);
+ tx4.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
+ tx4.vout[0].nValue = 6 * COIN;
+ pool.addUnchecked(tx4.GetHash(), CTxMemPoolEntry(tx4, 15000LL, 0, 1.0, 1, true));
+
+ /* equal fee rate to tx1, but newer */
+ CMutableTransaction tx5 = CMutableTransaction();
+ tx5.vout.resize(1);
+ tx5.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
+ tx5.vout[0].nValue = 11 * COIN;
+ pool.addUnchecked(tx5.GetHash(), CTxMemPoolEntry(tx5, 10000LL, 1, 10.0, 1, true));
+ BOOST_CHECK_EQUAL(pool.size(), 5);
+
+ std::vector<std::string> sortedOrder;
+ sortedOrder.resize(5);
+ sortedOrder[0] = tx2.GetHash().ToString(); // 20000
+ sortedOrder[1] = tx4.GetHash().ToString(); // 15000
+ sortedOrder[2] = tx1.GetHash().ToString(); // 10000
+ sortedOrder[3] = tx5.GetHash().ToString(); // 10000
+ sortedOrder[4] = tx3.GetHash().ToString(); // 0
+ CheckSort(pool, sortedOrder);
+
+ /* low fee but with high fee child */
+ /* tx6 -> tx7 -> tx8, tx9 -> tx10 */
+ CMutableTransaction tx6 = CMutableTransaction();
+ tx6.vout.resize(1);
+ tx6.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
+ tx6.vout[0].nValue = 20 * COIN;
+ pool.addUnchecked(tx6.GetHash(), CTxMemPoolEntry(tx6, 0LL, 1, 10.0, 1, true));
+ BOOST_CHECK_EQUAL(pool.size(), 6);
+ // Check that at this point, tx6 is sorted low
+ sortedOrder.push_back(tx6.GetHash().ToString());
+ CheckSort(pool, sortedOrder);
+
+ CTxMemPool::setEntries setAncestors;
+ setAncestors.insert(pool.mapTx.find(tx6.GetHash()));
+ CMutableTransaction tx7 = CMutableTransaction();
+ tx7.vin.resize(1);
+ tx7.vin[0].prevout = COutPoint(tx6.GetHash(), 0);
+ tx7.vin[0].scriptSig = CScript() << OP_11;
+ tx7.vout.resize(2);
+ tx7.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
+ tx7.vout[0].nValue = 10 * COIN;
+ tx7.vout[1].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
+ tx7.vout[1].nValue = 1 * COIN;
+
+ CTxMemPool::setEntries setAncestorsCalculated;
+ std::string dummy;
+ CTxMemPoolEntry entry7(tx7, 2000000LL, 1, 10.0, 1, true);
+ BOOST_CHECK_EQUAL(pool.CalculateMemPoolAncestors(entry7, setAncestorsCalculated, 100, 1000000, 1000, 1000000, dummy), true);
+ BOOST_CHECK(setAncestorsCalculated == setAncestors);
+
+ pool.addUnchecked(tx7.GetHash(), CTxMemPoolEntry(tx7, 2000000LL, 1, 10.0, 1, true), setAncestors);
+ BOOST_CHECK_EQUAL(pool.size(), 7);
+
+ // Now tx6 should be sorted higher (high fee child): tx7, tx6, tx2, ...
+ sortedOrder.erase(sortedOrder.end()-1);
+ sortedOrder.insert(sortedOrder.begin(), tx6.GetHash().ToString());
+ sortedOrder.insert(sortedOrder.begin(), tx7.GetHash().ToString());
+ CheckSort(pool, sortedOrder);
+
+ /* low fee child of tx7 */
+ CMutableTransaction tx8 = CMutableTransaction();
+ tx8.vin.resize(1);
+ tx8.vin[0].prevout = COutPoint(tx7.GetHash(), 0);
+ tx8.vin[0].scriptSig = CScript() << OP_11;
+ tx8.vout.resize(1);
+ tx8.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
+ tx8.vout[0].nValue = 10 * COIN;
+ setAncestors.insert(pool.mapTx.find(tx7.GetHash()));
+ pool.addUnchecked(tx8.GetHash(), CTxMemPoolEntry(tx8, 0LL, 2, 10.0, 1, true), setAncestors);
+
+ // Now tx8 should be sorted low, but tx6/tx both high
+ sortedOrder.push_back(tx8.GetHash().ToString());
+ CheckSort(pool, sortedOrder);
+
+ /* low fee child of tx7 */
+ CMutableTransaction tx9 = CMutableTransaction();
+ tx9.vin.resize(1);
+ tx9.vin[0].prevout = COutPoint(tx7.GetHash(), 1);
+ tx9.vin[0].scriptSig = CScript() << OP_11;
+ tx9.vout.resize(1);
+ tx9.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
+ tx9.vout[0].nValue = 1 * COIN;
+ pool.addUnchecked(tx9.GetHash(), CTxMemPoolEntry(tx9, 0LL, 3, 10.0, 1, true), setAncestors);
+
+ // tx9 should be sorted low
+ BOOST_CHECK_EQUAL(pool.size(), 9);
+ sortedOrder.push_back(tx9.GetHash().ToString());
+ CheckSort(pool, sortedOrder);
+
+ std::vector<std::string> snapshotOrder = sortedOrder;
+
+ setAncestors.insert(pool.mapTx.find(tx8.GetHash()));
+ setAncestors.insert(pool.mapTx.find(tx9.GetHash()));
+ /* tx10 depends on tx8 and tx9 and has a high fee*/
+ CMutableTransaction tx10 = CMutableTransaction();
+ tx10.vin.resize(2);
+ tx10.vin[0].prevout = COutPoint(tx8.GetHash(), 0);
+ tx10.vin[0].scriptSig = CScript() << OP_11;
+ tx10.vin[1].prevout = COutPoint(tx9.GetHash(), 0);
+ tx10.vin[1].scriptSig = CScript() << OP_11;
+ tx10.vout.resize(1);
+ tx10.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
+ tx10.vout[0].nValue = 10 * COIN;
+
+ setAncestorsCalculated.clear();
+ CTxMemPoolEntry entry10(tx10, 200000LL, 4, 10.0, 1, true);
+ BOOST_CHECK_EQUAL(pool.CalculateMemPoolAncestors(entry10, setAncestorsCalculated, 100, 1000000, 1000, 1000000, dummy), true);
+ BOOST_CHECK(setAncestorsCalculated == setAncestors);
+
+ pool.addUnchecked(tx10.GetHash(), CTxMemPoolEntry(tx10, 200000LL, 4, 10.0, 1, true), setAncestors);
+
+ /**
+ * tx8 and tx9 should both now be sorted higher
+ * Final order after tx10 is added:
+ *
+ * tx7 = 2.2M (4 txs)
+ * tx6 = 2.2M (5 txs)
+ * tx10 = 200k (1 tx)
+ * tx8 = 200k (2 txs)
+ * tx9 = 200k (2 txs)
+ * tx2 = 20000 (1)
+ * tx4 = 15000 (1)
+ * tx1 = 10000 (1)
+ * tx5 = 10000 (1)
+ * tx3 = 0 (1)
+ */
+ sortedOrder.erase(sortedOrder.end()-2, sortedOrder.end()); // take out tx8, tx9 from the end
+ sortedOrder.insert(sortedOrder.begin()+2, tx10.GetHash().ToString()); // tx10 is after tx6
+ sortedOrder.insert(sortedOrder.begin()+3, tx9.GetHash().ToString());
+ sortedOrder.insert(sortedOrder.begin()+3, tx8.GetHash().ToString());
+ CheckSort(pool, sortedOrder);
+
+ // there should be 10 transactions in the mempool
+ BOOST_CHECK_EQUAL(pool.size(), 10);
+
+ // Now try removing tx10 and verify the sort order returns to normal
+ std::list<CTransaction> removed;
+ pool.remove(pool.mapTx.find(tx10.GetHash())->GetTx(), removed, true);
+ CheckSort(pool, snapshotOrder);
+}
+
BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/txmempool.cpp b/src/txmempool.cpp
index c921dae45d..2f603e3c9f 100644
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -17,12 +17,6 @@
using namespace std;
-CTxMemPoolEntry::CTxMemPoolEntry():
- nFee(0), nTxSize(0), nModSize(0), nUsageSize(0), nTime(0), dPriority(0.0), hadNoDependencies(false)
-{
- nHeight = MEMPOOL_HEIGHT;
-}
-
CTxMemPoolEntry::CTxMemPoolEntry(const CTransaction& _tx, const CAmount& _nFee,
int64_t _nTime, double _dPriority,
unsigned int _nHeight, bool poolHasNoInputsOf):
@@ -32,6 +26,10 @@ CTxMemPoolEntry::CTxMemPoolEntry(const CTransaction& _tx, const CAmount& _nFee,
nTxSize = ::GetSerializeSize(tx, SER_NETWORK, PROTOCOL_VERSION);
nModSize = tx.CalculateModifiedSize(nTxSize);
nUsageSize = RecursiveDynamicUsage(tx);
+
+ nCountWithDescendants = 1;
+ nSizeWithDescendants = nTxSize;
+ nFeesWithDescendants = nFee;
}
CTxMemPoolEntry::CTxMemPoolEntry(const CTxMemPoolEntry& other)
@@ -48,6 +46,244 @@ CTxMemPoolEntry::GetPriority(unsigned int currentHeight) const
return dResult;
}
+// Update the given tx for any in-mempool descendants.
+// Assumes that setMemPoolChildren is correct for the given tx and all
+// descendants.
+bool CTxMemPool::UpdateForDescendants(txiter updateIt, int maxDescendantsToVisit, cacheMap &cachedDescendants, const std::set<uint256> &setExclude)
+{
+ // Track the number of entries (outside setExclude) that we'd need to visit
+ // (will bail out if it exceeds maxDescendantsToVisit)
+ int nChildrenToVisit = 0;
+
+ setEntries stageEntries, setAllDescendants;
+ stageEntries = GetMemPoolChildren(updateIt);
+
+ while (!stageEntries.empty()) {
+ const txiter cit = *stageEntries.begin();
+ if (cit->IsDirty()) {
+ // Don't consider any more children if any descendant is dirty
+ return false;
+ }
+ setAllDescendants.insert(cit);
+ stageEntries.erase(cit);
+ const setEntries &setChildren = GetMemPoolChildren(cit);
+ BOOST_FOREACH(const txiter childEntry, setChildren) {
+ cacheMap::iterator cacheIt = cachedDescendants.find(childEntry);
+ if (cacheIt != cachedDescendants.end()) {
+ // We've already calculated this one, just add the entries for this set
+ // but don't traverse again.
+ BOOST_FOREACH(const txiter cacheEntry, cacheIt->second) {
+ // update visit count only for new child transactions
+ // (outside of setExclude and stageEntries)
+ if (setAllDescendants.insert(cacheEntry).second &&
+ !setExclude.count(cacheEntry->GetTx().GetHash()) &&
+ !stageEntries.count(cacheEntry)) {
+ nChildrenToVisit++;
+ }
+ }
+ } else if (!setAllDescendants.count(childEntry)) {
+ // Schedule for later processing and update our visit count
+ if (stageEntries.insert(childEntry).second && !setExclude.count(childEntry->GetTx().GetHash())) {
+ nChildrenToVisit++;
+ }
+ }
+ if (nChildrenToVisit > maxDescendantsToVisit) {
+ return false;
+ }
+ }
+ }
+ // setAllDescendants now contains all in-mempool descendants of updateIt.
+ // Update and add to cached descendant map
+ int64_t modifySize = 0;
+ CAmount modifyFee = 0;
+ int64_t modifyCount = 0;
+ BOOST_FOREACH(txiter cit, setAllDescendants) {
+ if (!setExclude.count(cit->GetTx().GetHash())) {
+ modifySize += cit->GetTxSize();
+ modifyFee += cit->GetFee();
+ modifyCount++;
+ cachedDescendants[updateIt].insert(cit);
+ }
+ }
+ mapTx.modify(updateIt, update_descendant_state(modifySize, modifyFee, modifyCount));
+ return true;
+}
+
+// vHashesToUpdate is the set of transaction hashes from a disconnected block
+// which has been re-added to the mempool.
+// for each entry, look for descendants that are outside hashesToUpdate, and
+// add fee/size information for such descendants to the parent.
+void CTxMemPool::UpdateTransactionsFromBlock(const std::vector<uint256> &vHashesToUpdate)
+{
+ LOCK(cs);
+ // For each entry in vHashesToUpdate, store the set of in-mempool, but not
+ // in-vHashesToUpdate transactions, so that we don't have to recalculate
+ // descendants when we come across a previously seen entry.
+ cacheMap mapMemPoolDescendantsToUpdate;
+
+ // Use a set for lookups into vHashesToUpdate (these entries are already
+ // accounted for in the state of their ancestors)
+ std::set<uint256> setAlreadyIncluded(vHashesToUpdate.begin(), vHashesToUpdate.end());
+
+ // Iterate in reverse, so that whenever we are looking at at a transaction
+ // we are sure that all in-mempool descendants have already been processed.
+ // This maximizes the benefit of the descendant cache and guarantees that
+ // setMemPoolChildren will be updated, an assumption made in
+ // UpdateForDescendants.
+ BOOST_REVERSE_FOREACH(const uint256 &hash, vHashesToUpdate) {
+ // we cache the in-mempool children to avoid duplicate updates
+ setEntries setChildren;
+ // calculate children from mapNextTx
+ txiter it = mapTx.find(hash);
+ if (it == mapTx.end()) {
+ continue;
+ }
+ std::map<COutPoint, CInPoint>::iterator iter = mapNextTx.lower_bound(COutPoint(hash, 0));
+ // First calculate the children, and update setMemPoolChildren to
+ // include them, and update their setMemPoolParents to include this tx.
+ for (; iter != mapNextTx.end() && iter->first.hash == hash; ++iter) {
+ const uint256 &childHash = iter->second.ptx->GetHash();
+ txiter childIter = mapTx.find(childHash);
+ assert(childIter != mapTx.end());
+ // We can skip updating entries we've encountered before or that
+ // are in the block (which are already accounted for).
+ if (setChildren.insert(childIter).second && !setAlreadyIncluded.count(childHash)) {
+ UpdateChild(it, childIter, true);
+ UpdateParent(childIter, it, true);
+ }
+ }
+ if (!UpdateForDescendants(it, 100, mapMemPoolDescendantsToUpdate, setAlreadyIncluded)) {
+ // Mark as dirty if we can't do the calculation.
+ mapTx.modify(it, set_dirty());
+ }
+ }
+}
+
+bool CTxMemPool::CalculateMemPoolAncestors(const CTxMemPoolEntry &entry, setEntries &setAncestors, uint64_t limitAncestorCount, uint64_t limitAncestorSize, uint64_t limitDescendantCount, uint64_t limitDescendantSize, std::string &errString)
+{
+ setEntries parentHashes;
+ const CTransaction &tx = entry.GetTx();
+
+ // Get parents of this transaction that are in the mempool
+ // Entry may or may not already be in the mempool, and GetMemPoolParents()
+ // is only valid for entries in the mempool, so we iterate mapTx to find
+ // parents.
+ // TODO: optimize this so that we only check limits and walk
+ // tx.vin when called on entries not already in the mempool.
+ for (unsigned int i = 0; i < tx.vin.size(); i++) {
+ txiter piter = mapTx.find(tx.vin[i].prevout.hash);
+ if (piter != mapTx.end()) {
+ parentHashes.insert(piter);
+ if (parentHashes.size() + 1 > limitAncestorCount) {
+ errString = strprintf("too many unconfirmed parents [limit: %u]", limitAncestorCount);
+ return false;
+ }
+ }
+ }
+
+ size_t totalSizeWithAncestors = entry.GetTxSize();
+
+ while (!parentHashes.empty()) {
+ txiter stageit = *parentHashes.begin();
+
+ setAncestors.insert(stageit);
+ parentHashes.erase(stageit);
+ totalSizeWithAncestors += stageit->GetTxSize();
+
+ if (stageit->GetSizeWithDescendants() + entry.GetTxSize() > limitDescendantSize) {
+ errString = strprintf("exceeds descendant size limit for tx %s [limit: %u]", stageit->GetTx().GetHash().ToString(), limitDescendantSize);
+ return false;
+ } else if (stageit->GetCountWithDescendants() + 1 > limitDescendantCount) {
+ errString = strprintf("too many descendants for tx %s [limit: %u]", stageit->GetTx().GetHash().ToString(), limitDescendantCount);
+ return false;
+ } else if (totalSizeWithAncestors > limitAncestorSize) {
+ errString = strprintf("exceeds ancestor size limit [limit: %u]", limitAncestorSize);
+ return false;
+ }
+
+ const setEntries & setMemPoolParents = GetMemPoolParents(stageit);
+ BOOST_FOREACH(const txiter &phash, setMemPoolParents) {
+ // If this is a new ancestor, add it.
+ if (setAncestors.count(phash) == 0) {
+ parentHashes.insert(phash);
+ }
+ if (parentHashes.size() + setAncestors.size() + 1 > limitAncestorCount) {
+ errString = strprintf("too many unconfirmed ancestors [limit: %u]", limitAncestorCount);
+ return false;
+ }
+ }
+ }
+
+ return true;
+}
+
+void CTxMemPool::UpdateAncestorsOf(bool add, txiter it, setEntries &setAncestors)
+{
+ setEntries parentIters = GetMemPoolParents(it);
+ // add or remove this tx as a child of each parent
+ BOOST_FOREACH(txiter piter, parentIters) {
+ UpdateChild(piter, it, add);
+ }
+ const int64_t updateCount = (add ? 1 : -1);
+ const int64_t updateSize = updateCount * it->GetTxSize();
+ const CAmount updateFee = updateCount * it->GetFee();
+ BOOST_FOREACH(txiter ancestorIt, setAncestors) {
+ mapTx.modify(ancestorIt, update_descendant_state(updateSize, updateFee, updateCount));
+ }
+}
+
+void CTxMemPool::UpdateChildrenForRemoval(txiter it)
+{
+ const setEntries &setMemPoolChildren = GetMemPoolChildren(it);
+ BOOST_FOREACH(txiter updateIt, setMemPoolChildren) {
+ UpdateParent(updateIt, it, false);
+ }
+}
+
+void CTxMemPool::UpdateForRemoveFromMempool(const setEntries &entriesToRemove)
+{
+ // For each entry, walk back all ancestors and decrement size associated with this
+ // transaction
+ const uint64_t nNoLimit = std::numeric_limits<uint64_t>::max();
+ BOOST_FOREACH(txiter removeIt, entriesToRemove) {
+ setEntries setAncestors;
+ const CTxMemPoolEntry &entry = *removeIt;
+ std::string dummy;
+ CalculateMemPoolAncestors(entry, setAncestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy);
+ // Note that UpdateAncestorsOf severs the child links that point to
+ // removeIt in the entries for the parents of removeIt. This is
+ // fine since we don't need to use the mempool children of any entries
+ // to walk back over our ancestors (but we do need the mempool
+ // parents!)
+ UpdateAncestorsOf(false, removeIt, setAncestors);
+ }
+ // After updating all the ancestor sizes, we can now sever the link between each
+ // transaction being removed and any mempool children (ie, update setMemPoolParents
+ // for each direct child of a transaction being removed).
+ BOOST_FOREACH(txiter removeIt, entriesToRemove) {
+ UpdateChildrenForRemoval(removeIt);
+ }
+}
+
+void CTxMemPoolEntry::SetDirty()
+{
+ nCountWithDescendants = 0;
+ nSizeWithDescendants = nTxSize;
+ nFeesWithDescendants = nFee;
+}
+
+void CTxMemPoolEntry::UpdateState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount)
+{
+ if (!IsDirty()) {
+ nSizeWithDescendants += modifySize;
+ assert(int64_t(nSizeWithDescendants) > 0);
+ nFeesWithDescendants += modifyFee;
+ assert(nFeesWithDescendants >= 0);
+ nCountWithDescendants += modifyCount;
+ assert(int64_t(nCountWithDescendants) > 0);
+ }
+}
+
CTxMemPool::CTxMemPool(const CFeeRate& _minRelayFee) :
nTransactionsUpdated(0)
{
@@ -89,34 +325,103 @@ void CTxMemPool::AddTransactionsUpdated(unsigned int n)
nTransactionsUpdated += n;
}
-
-bool CTxMemPool::addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry, bool fCurrentEstimate)
+bool CTxMemPool::addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry, setEntries &setAncestors, bool fCurrentEstimate)
{
// Add to memory pool without checking anything.
// Used by main.cpp AcceptToMemoryPool(), which DOES do
// all the appropriate checks.
LOCK(cs);
- mapTx[hash] = entry;
- const CTransaction& tx = mapTx[hash].GetTx();
- for (unsigned int i = 0; i < tx.vin.size(); i++)
+ indexed_transaction_set::iterator newit = mapTx.insert(entry).first;
+ mapLinks.insert(make_pair(newit, TxLinks()));
+
+ // Update cachedInnerUsage to include contained transaction's usage.
+ // (When we update the entry for in-mempool parents, memory usage will be
+ // further updated.)
+ cachedInnerUsage += entry.DynamicMemoryUsage();
+
+ const CTransaction& tx = newit->GetTx();
+ std::set<uint256> setParentTransactions;
+ for (unsigned int i = 0; i < tx.vin.size(); i++) {
mapNextTx[tx.vin[i].prevout] = CInPoint(&tx, i);
+ setParentTransactions.insert(tx.vin[i].prevout.hash);
+ }
+ // Don't bother worrying about child transactions of this one.
+ // Normal case of a new transaction arriving is that there can't be any
+ // children, because such children would be orphans.
+ // An exception to that is if a transaction enters that used to be in a block.
+ // In that case, our disconnect block logic will call UpdateTransactionsFromBlock
+ // to clean up the mess we're leaving here.
+
+ // Update ancestors with information about this tx
+ BOOST_FOREACH (const uint256 &phash, setParentTransactions) {
+ txiter pit = mapTx.find(phash);
+ if (pit != mapTx.end()) {
+ UpdateParent(newit, pit, true);
+ }
+ }
+ UpdateAncestorsOf(true, newit, setAncestors);
+
nTransactionsUpdated++;
totalTxSize += entry.GetTxSize();
- cachedInnerUsage += entry.DynamicMemoryUsage();
minerPolicyEstimator->processTransaction(entry, fCurrentEstimate);
return true;
}
+void CTxMemPool::removeUnchecked(txiter it)
+{
+ const uint256 hash = it->GetTx().GetHash();
+ BOOST_FOREACH(const CTxIn& txin, it->GetTx().vin)
+ mapNextTx.erase(txin.prevout);
+
+ totalTxSize -= it->GetTxSize();
+ cachedInnerUsage -= it->DynamicMemoryUsage();
+ cachedInnerUsage -= memusage::DynamicUsage(mapLinks[it].parents) + memusage::DynamicUsage(mapLinks[it].children);
+ mapLinks.erase(it);
+ mapTx.erase(it);
+ nTransactionsUpdated++;
+ minerPolicyEstimator->removeTx(hash);
+}
+
+// Calculates descendants of entry that are not already in setDescendants, and adds to
+// setDescendants. Assumes entryit is already a tx in the mempool and setMemPoolChildren
+// is correct for tx and all descendants.
+// Also assumes that if an entry is in setDescendants already, then all
+// in-mempool descendants of it are already in setDescendants as well, so that we
+// can save time by not iterating over those entries.
+void CTxMemPool::CalculateDescendants(txiter entryit, setEntries &setDescendants)
+{
+ setEntries stage;
+ if (setDescendants.count(entryit) == 0) {
+ stage.insert(entryit);
+ }
+ // Traverse down the children of entry, only adding children that are not
+ // accounted for in setDescendants already (because those children have either
+ // already been walked, or will be walked in this iteration).
+ while (!stage.empty()) {
+ txiter it = *stage.begin();
+ setDescendants.insert(it);
+ stage.erase(it);
+
+ const setEntries &setChildren = GetMemPoolChildren(it);
+ BOOST_FOREACH(const txiter &childiter, setChildren) {
+ if (!setDescendants.count(childiter)) {
+ stage.insert(childiter);
+ }
+ }
+ }
+}
void CTxMemPool::remove(const CTransaction &origTx, std::list<CTransaction>& removed, bool fRecursive)
{
// Remove transaction from memory pool
{
LOCK(cs);
- std::deque<uint256> txToRemove;
- txToRemove.push_back(origTx.GetHash());
- if (fRecursive && !mapTx.count(origTx.GetHash())) {
+ setEntries txToRemove;
+ txiter origit = mapTx.find(origTx.GetHash());
+ if (origit != mapTx.end()) {
+ txToRemove.insert(origit);
+ } else if (fRecursive) {
// If recursively removing but origTx isn't in the mempool
// be sure to remove any children that are in the pool. This can
// happen during chain re-orgs if origTx isn't re-accepted into
@@ -125,34 +430,23 @@ void CTxMemPool::remove(const CTransaction &origTx, std::list<CTransaction>& rem
std::map<COutPoint, CInPoint>::iterator it = mapNextTx.find(COutPoint(origTx.GetHash(), i));
if (it == mapNextTx.end())
continue;
- txToRemove.push_back(it->second.ptx->GetHash());
+ txiter nextit = mapTx.find(it->second.ptx->GetHash());
+ assert(nextit != mapTx.end());
+ txToRemove.insert(nextit);
}
}
- while (!txToRemove.empty())
- {
- uint256 hash = txToRemove.front();
- txToRemove.pop_front();
- if (!mapTx.count(hash))
- continue;
- const CTransaction& tx = mapTx[hash].GetTx();
- if (fRecursive) {
- for (unsigned int i = 0; i < tx.vout.size(); i++) {
- std::map<COutPoint, CInPoint>::iterator it = mapNextTx.find(COutPoint(hash, i));
- if (it == mapNextTx.end())
- continue;
- txToRemove.push_back(it->second.ptx->GetHash());
- }
+ setEntries setAllRemoves;
+ if (fRecursive) {
+ BOOST_FOREACH(txiter it, txToRemove) {
+ CalculateDescendants(it, setAllRemoves);
}
- BOOST_FOREACH(const CTxIn& txin, tx.vin)
- mapNextTx.erase(txin.prevout);
-
- removed.push_back(tx);
- totalTxSize -= mapTx[hash].GetTxSize();
- cachedInnerUsage -= mapTx[hash].DynamicMemoryUsage();
- mapTx.erase(hash);
- nTransactionsUpdated++;
- minerPolicyEstimator->removeTx(hash);
+ } else {
+ setAllRemoves.swap(txToRemove);
}
+ BOOST_FOREACH(txiter it, setAllRemoves) {
+ removed.push_back(it->GetTx());
+ }
+ RemoveStaged(setAllRemoves);
}
}
@@ -161,10 +455,10 @@ void CTxMemPool::removeCoinbaseSpends(const CCoinsViewCache *pcoins, unsigned in
// Remove transactions spending a coinbase which are now immature
LOCK(cs);
list<CTransaction> transactionsToRemove;
- for (std::map<uint256, CTxMemPoolEntry>::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
- const CTransaction& tx = it->second.GetTx();
+ for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
+ const CTransaction& tx = it->GetTx();
BOOST_FOREACH(const CTxIn& txin, tx.vin) {
- std::map<uint256, CTxMemPoolEntry>::const_iterator it2 = mapTx.find(txin.prevout.hash);
+ indexed_transaction_set::const_iterator it2 = mapTx.find(txin.prevout.hash);
if (it2 != mapTx.end())
continue;
const CCoins *coins = pcoins->AccessCoins(txin.prevout.hash);
@@ -209,8 +503,10 @@ void CTxMemPool::removeForBlock(const std::vector<CTransaction>& vtx, unsigned i
BOOST_FOREACH(const CTransaction& tx, vtx)
{
uint256 hash = tx.GetHash();
- if (mapTx.count(hash))
- entries.push_back(mapTx[hash]);
+
+ indexed_transaction_set::iterator i = mapTx.find(hash);
+ if (i != mapTx.end())
+ entries.push_back(*i);
}
BOOST_FOREACH(const CTransaction& tx, vtx)
{
@@ -226,6 +522,7 @@ void CTxMemPool::removeForBlock(const std::vector<CTransaction>& vtx, unsigned i
void CTxMemPool::clear()
{
LOCK(cs);
+ mapLinks.clear();
mapTx.clear();
mapNextTx.clear();
totalTxSize = 0;
@@ -247,19 +544,25 @@ void CTxMemPool::check(const CCoinsViewCache *pcoins) const
LOCK(cs);
list<const CTxMemPoolEntry*> waitingOnDependants;
- for (std::map<uint256, CTxMemPoolEntry>::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
+ for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
unsigned int i = 0;
- checkTotal += it->second.GetTxSize();
- innerUsage += it->second.DynamicMemoryUsage();
- const CTransaction& tx = it->second.GetTx();
+ checkTotal += it->GetTxSize();
+ innerUsage += it->DynamicMemoryUsage();
+ const CTransaction& tx = it->GetTx();
+ txlinksMap::const_iterator linksiter = mapLinks.find(it);
+ assert(linksiter != mapLinks.end());
+ const TxLinks &links = linksiter->second;
+ innerUsage += memusage::DynamicUsage(links.parents) + memusage::DynamicUsage(links.children);
bool fDependsWait = false;
+ setEntries setParentCheck;
BOOST_FOREACH(const CTxIn &txin, tx.vin) {
// Check that every mempool transaction's inputs refer to available coins, or other mempool tx's.
- std::map<uint256, CTxMemPoolEntry>::const_iterator it2 = mapTx.find(txin.prevout.hash);
+ indexed_transaction_set::const_iterator it2 = mapTx.find(txin.prevout.hash);
if (it2 != mapTx.end()) {
- const CTransaction& tx2 = it2->second.GetTx();
+ const CTransaction& tx2 = it2->GetTx();
assert(tx2.vout.size() > txin.prevout.n && !tx2.vout[txin.prevout.n].IsNull());
fDependsWait = true;
+ setParentCheck.insert(it2);
} else {
const CCoins* coins = pcoins->AccessCoins(txin.prevout.hash);
assert(coins && coins->IsAvailable(txin.prevout.n));
@@ -271,8 +574,35 @@ void CTxMemPool::check(const CCoinsViewCache *pcoins) const
assert(it3->second.n == i);
i++;
}
+ assert(setParentCheck == GetMemPoolParents(it));
+ // Check children against mapNextTx
+ CTxMemPool::setEntries setChildrenCheck;
+ std::map<COutPoint, CInPoint>::const_iterator iter = mapNextTx.lower_bound(COutPoint(it->GetTx().GetHash(), 0));
+ int64_t childSizes = 0;
+ CAmount childFees = 0;
+ for (; iter != mapNextTx.end() && iter->first.hash == it->GetTx().GetHash(); ++iter) {
+ txiter childit = mapTx.find(iter->second.ptx->GetHash());
+ assert(childit != mapTx.end()); // mapNextTx points to in-mempool transactions
+ if (setChildrenCheck.insert(childit).second) {
+ childSizes += childit->GetTxSize();
+ childFees += childit->GetFee();
+ }
+ }
+ assert(setChildrenCheck == GetMemPoolChildren(it));
+ // Also check to make sure size/fees is greater than sum with immediate children.
+ // just a sanity check, not definitive that this calc is correct...
+ // also check that the size is less than the size of the entire mempool.
+ if (!it->IsDirty()) {
+ assert(it->GetSizeWithDescendants() >= childSizes + it->GetTxSize());
+ assert(it->GetFeesWithDescendants() >= childFees + it->GetFee());
+ } else {
+ assert(it->GetSizeWithDescendants() == it->GetTxSize());
+ assert(it->GetFeesWithDescendants() == it->GetFee());
+ }
+ assert(it->GetFeesWithDescendants() >= 0);
+
if (fDependsWait)
- waitingOnDependants.push_back(&it->second);
+ waitingOnDependants.push_back(&(*it));
else {
CValidationState state;
assert(CheckInputs(tx, state, mempoolDuplicate, false, 0, false, NULL));
@@ -296,8 +626,8 @@ void CTxMemPool::check(const CCoinsViewCache *pcoins) const
}
for (std::map<COutPoint, CInPoint>::const_iterator it = mapNextTx.begin(); it != mapNextTx.end(); it++) {
uint256 hash = it->second.ptx->GetHash();
- map<uint256, CTxMemPoolEntry>::const_iterator it2 = mapTx.find(hash);
- const CTransaction& tx = it2->second.GetTx();
+ indexed_transaction_set::const_iterator it2 = mapTx.find(hash);
+ const CTransaction& tx = it2->GetTx();
assert(it2 != mapTx.end());
assert(&tx == it->second.ptx);
assert(tx.vin.size() > it->second.n);
@@ -314,16 +644,16 @@ void CTxMemPool::queryHashes(vector<uint256>& vtxid)
LOCK(cs);
vtxid.reserve(mapTx.size());
- for (map<uint256, CTxMemPoolEntry>::iterator mi = mapTx.begin(); mi != mapTx.end(); ++mi)
- vtxid.push_back((*mi).first);
+ for (indexed_transaction_set::iterator mi = mapTx.begin(); mi != mapTx.end(); ++mi)
+ vtxid.push_back(mi->GetTx().GetHash());
}
bool CTxMemPool::lookup(uint256 hash, CTransaction& result) const
{
LOCK(cs);
- map<uint256, CTxMemPoolEntry>::const_iterator i = mapTx.find(hash);
+ indexed_transaction_set::const_iterator i = mapTx.find(hash);
if (i == mapTx.end()) return false;
- result = i->second.GetTx();
+ result = i->GetTx();
return true;
}
@@ -429,5 +759,60 @@ bool CCoinsViewMemPool::HaveCoins(const uint256 &txid) const {
size_t CTxMemPool::DynamicMemoryUsage() const {
LOCK(cs);
- return memusage::DynamicUsage(mapTx) + memusage::DynamicUsage(mapNextTx) + memusage::DynamicUsage(mapDeltas) + cachedInnerUsage;
+ // Estimate the overhead of mapTx to be 9 pointers + an allocation, as no exact formula for boost::multi_index_contained is implemented.
+ return memusage::MallocUsage(sizeof(CTxMemPoolEntry) + 9 * sizeof(void*)) * mapTx.size() + memusage::DynamicUsage(mapNextTx) + memusage::DynamicUsage(mapDeltas) + memusage::DynamicUsage(mapLinks) + cachedInnerUsage;
+}
+
+void CTxMemPool::RemoveStaged(setEntries &stage) {
+ AssertLockHeld(cs);
+ UpdateForRemoveFromMempool(stage);
+ BOOST_FOREACH(const txiter& it, stage) {
+ removeUnchecked(it);
+ }
+}
+
+bool CTxMemPool::addUnchecked(const uint256&hash, const CTxMemPoolEntry &entry, bool fCurrentEstimate)
+{
+ LOCK(cs);
+ setEntries setAncestors;
+ uint64_t nNoLimit = std::numeric_limits<uint64_t>::max();
+ std::string dummy;
+ CalculateMemPoolAncestors(entry, setAncestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy);
+ return addUnchecked(hash, entry, setAncestors, fCurrentEstimate);
+}
+
+void CTxMemPool::UpdateChild(txiter entry, txiter child, bool add)
+{
+ setEntries s;
+ if (add && mapLinks[entry].children.insert(child).second) {
+ cachedInnerUsage += memusage::IncrementalDynamicUsage(s);
+ } else if (!add && mapLinks[entry].children.erase(child)) {
+ cachedInnerUsage -= memusage::IncrementalDynamicUsage(s);
+ }
+}
+
+void CTxMemPool::UpdateParent(txiter entry, txiter parent, bool add)
+{
+ setEntries s;
+ if (add && mapLinks[entry].parents.insert(parent).second) {
+ cachedInnerUsage += memusage::IncrementalDynamicUsage(s);
+ } else if (!add && mapLinks[entry].parents.erase(parent)) {
+ cachedInnerUsage -= memusage::IncrementalDynamicUsage(s);
+ }
+}
+
+const CTxMemPool::setEntries & CTxMemPool::GetMemPoolParents(txiter entry) const
+{
+ assert (entry != mapTx.end());
+ txlinksMap::const_iterator it = mapLinks.find(entry);
+ assert(it != mapLinks.end());
+ return it->second.parents;
+}
+
+const CTxMemPool::setEntries & CTxMemPool::GetMemPoolChildren(txiter entry) const
+{
+ assert (entry != mapTx.end());
+ txlinksMap::const_iterator it = mapLinks.find(entry);
+ assert(it != mapLinks.end());
+ return it->second.children;
}
diff --git a/src/txmempool.h b/src/txmempool.h
index ea36ce1ad5..f0c3f7e0f1 100644
--- a/src/txmempool.h
+++ b/src/txmempool.h
@@ -7,12 +7,17 @@
#define BITCOIN_TXMEMPOOL_H
#include <list>
+#include <set>
#include "amount.h"
#include "coins.h"
#include "primitives/transaction.h"
#include "sync.h"
+#undef foreach
+#include "boost/multi_index_container.hpp"
+#include "boost/multi_index/ordered_index.hpp"
+
class CAutoFile;
inline double AllowFreeThreshold()
@@ -30,9 +35,25 @@ inline bool AllowFree(double dPriority)
/** Fake height value used in CCoins to signify they are only in the memory pool (since 0.8) */
static const unsigned int MEMPOOL_HEIGHT = 0x7FFFFFFF;
-/**
- * CTxMemPool stores these:
+class CTxMemPool;
+
+/** \class CTxMemPoolEntry
+ *
+ * CTxMemPoolEntry stores data about the correponding transaction, as well
+ * as data about all in-mempool transactions that depend on the transaction
+ * ("descendant" transactions).
+ *
+ * When a new entry is added to the mempool, we update the descendant state
+ * (nCountWithDescendants, nSizeWithDescendants, and nFeesWithDescendants) for
+ * all ancestors of the newly added transaction.
+ *
+ * If updating the descendant state is skipped, we can mark the entry as
+ * "dirty", and set nSizeWithDescendants/nFeesWithDescendants to equal nTxSize/
+ * nTxFee. (This can potentially happen during a reorg, where we limit the
+ * amount of work we're willing to do to avoid consuming too much CPU.)
+ *
*/
+
class CTxMemPoolEntry
{
private:
@@ -46,10 +67,18 @@ private:
unsigned int nHeight; //! Chain height when entering the mempool
bool hadNoDependencies; //! Not dependent on any other txs when it entered the mempool
+ // Information about descendants of this transaction that are in the
+ // mempool; if we remove this transaction we must remove all of these
+ // descendants as well. if nCountWithDescendants is 0, treat this entry as
+ // dirty, and nSizeWithDescendants and nFeesWithDescendants will not be
+ // correct.
+ uint64_t nCountWithDescendants; //! number of descendant transactions
+ uint64_t nSizeWithDescendants; //! ... and size
+ CAmount nFeesWithDescendants; //! ... and total fees (all including us)
+
public:
CTxMemPoolEntry(const CTransaction& _tx, const CAmount& _nFee,
int64_t _nTime, double _dPriority, unsigned int _nHeight, bool poolHasNoInputsOf = false);
- CTxMemPoolEntry();
CTxMemPoolEntry(const CTxMemPoolEntry& other);
const CTransaction& GetTx() const { return this->tx; }
@@ -60,6 +89,98 @@ public:
unsigned int GetHeight() const { return nHeight; }
bool WasClearAtEntry() const { return hadNoDependencies; }
size_t DynamicMemoryUsage() const { return nUsageSize; }
+
+ // Adjusts the descendant state, if this entry is not dirty.
+ void UpdateState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount);
+
+ /** We can set the entry to be dirty if doing the full calculation of in-
+ * mempool descendants will be too expensive, which can potentially happen
+ * when re-adding transactions from a block back to the mempool.
+ */
+ void SetDirty();
+ bool IsDirty() const { return nCountWithDescendants == 0; }
+
+ uint64_t GetCountWithDescendants() const { return nCountWithDescendants; }
+ uint64_t GetSizeWithDescendants() const { return nSizeWithDescendants; }
+ CAmount GetFeesWithDescendants() const { return nFeesWithDescendants; }
+};
+
+// Helpers for modifying CTxMemPool::mapTx, which is a boost multi_index.
+struct update_descendant_state
+{
+ update_descendant_state(int64_t _modifySize, CAmount _modifyFee, int64_t _modifyCount) :
+ modifySize(_modifySize), modifyFee(_modifyFee), modifyCount(_modifyCount)
+ {}
+
+ void operator() (CTxMemPoolEntry &e)
+ { e.UpdateState(modifySize, modifyFee, modifyCount); }
+
+ private:
+ int64_t modifySize;
+ CAmount modifyFee;
+ int64_t modifyCount;
+};
+
+struct set_dirty
+{
+ void operator() (CTxMemPoolEntry &e)
+ { e.SetDirty(); }
+};
+
+// extracts a TxMemPoolEntry's transaction hash
+struct mempoolentry_txid
+{
+ typedef uint256 result_type;
+ result_type operator() (const CTxMemPoolEntry &entry) const
+ {
+ return entry.GetTx().GetHash();
+ }
+};
+
+/** \class CompareTxMemPoolEntryByFee
+ *
+ * Sort an entry by max(feerate of entry's tx, feerate with all descendants).
+ */
+class CompareTxMemPoolEntryByFee
+{
+public:
+ bool operator()(const CTxMemPoolEntry& a, const CTxMemPoolEntry& b)
+ {
+ bool fUseADescendants = UseDescendantFeeRate(a);
+ bool fUseBDescendants = UseDescendantFeeRate(b);
+
+ double aFees = fUseADescendants ? a.GetFeesWithDescendants() : a.GetFee();
+ double aSize = fUseADescendants ? a.GetSizeWithDescendants() : a.GetTxSize();
+
+ double bFees = fUseBDescendants ? b.GetFeesWithDescendants() : b.GetFee();
+ double bSize = fUseBDescendants ? b.GetSizeWithDescendants() : b.GetTxSize();
+
+ // Avoid division by rewriting (a/b > c/d) as (a*d > c*b).
+ double f1 = aFees * bSize;
+ double f2 = aSize * bFees;
+
+ if (f1 == f2) {
+ return a.GetTime() < b.GetTime();
+ }
+ return f1 > f2;
+ }
+
+ // Calculate which feerate to use for an entry (avoiding division).
+ bool UseDescendantFeeRate(const CTxMemPoolEntry &a)
+ {
+ double f1 = (double)a.GetFee() * a.GetSizeWithDescendants();
+ double f2 = (double)a.GetFeesWithDescendants() * a.GetTxSize();
+ return f2 > f1;
+ }
+};
+
+class CompareTxMemPoolEntryByEntryTime
+{
+public:
+ bool operator()(const CTxMemPoolEntry& a, const CTxMemPoolEntry& b)
+ {
+ return a.GetTime() < b.GetTime();
+ }
};
class CBlockPolicyEstimator;
@@ -87,6 +208,71 @@ public:
* are added to the pool: if a new transaction double-spends
* an input of a transaction in the pool, it is dropped,
* as are non-standard transactions.
+ *
+ * CTxMemPool::mapTx, and CTxMemPoolEntry bookkeeping:
+ *
+ * mapTx is a boost::multi_index that sorts the mempool on 2 criteria:
+ * - transaction hash
+ * - feerate [we use max(feerate of tx, feerate of tx with all descendants)]
+ *
+ * Note: the term "descendant" refers to in-mempool transactions that depend on
+ * this one, while "ancestor" refers to in-mempool transactions that a given
+ * transaction depends on.
+ *
+ * In order for the feerate sort to remain correct, we must update transactions
+ * in the mempool when new descendants arrive. To facilitate this, we track
+ * the set of in-mempool direct parents and direct children in mapLinks. Within
+ * each CTxMemPoolEntry, we track the size and fees of all descendants.
+ *
+ * Usually when a new transaction is added to the mempool, it has no in-mempool
+ * children (because any such children would be an orphan). So in
+ * addUnchecked(), we:
+ * - update a new entry's setMemPoolParents to include all in-mempool parents
+ * - update the new entry's direct parents to include the new tx as a child
+ * - update all ancestors of the transaction to include the new tx's size/fee
+ *
+ * When a transaction is removed from the mempool, we must:
+ * - update all in-mempool parents to not track the tx in setMemPoolChildren
+ * - update all ancestors to not include the tx's size/fees in descendant state
+ * - update all in-mempool children to not include it as a parent
+ *
+ * These happen in UpdateForRemoveFromMempool(). (Note that when removing a
+ * transaction along with its descendants, we must calculate that set of
+ * transactions to be removed before doing the removal, or else the mempool can
+ * be in an inconsistent state where it's impossible to walk the ancestors of
+ * a transaction.)
+ *
+ * In the event of a reorg, the assumption that a newly added tx has no
+ * in-mempool children is false. In particular, the mempool is in an
+ * inconsistent state while new transactions are being added, because there may
+ * be descendant transactions of a tx coming from a disconnected block that are
+ * unreachable from just looking at transactions in the mempool (the linking
+ * transactions may also be in the disconnected block, waiting to be added).
+ * Because of this, there's not much benefit in trying to search for in-mempool
+ * children in addUnchecked(). Instead, in the special case of transactions
+ * being added from a disconnected block, we require the caller to clean up the
+ * state, to account for in-mempool, out-of-block descendants for all the
+ * in-block transactions by calling UpdateTransactionsFromBlock(). Note that
+ * until this is called, the mempool state is not consistent, and in particular
+ * mapLinks may not be correct (and therefore functions like
+ * CalculateMemPoolAncestors() and CalculateDescendants() that rely
+ * on them to walk the mempool are not generally safe to use).
+ *
+ * Computational limits:
+ *
+ * Updating all in-mempool ancestors of a newly added transaction can be slow,
+ * if no bound exists on how many in-mempool ancestors there may be.
+ * CalculateMemPoolAncestors() takes configurable limits that are designed to
+ * prevent these calculations from being too CPU intensive.
+ *
+ * Adding transactions from a disconnected block can be very time consuming,
+ * because we don't have a way to limit the number of in-mempool descendants.
+ * To bound CPU processing, we limit the amount of work we're willing to do
+ * to properly update the descendant information for a tx being added from
+ * a disconnected block. If we would exceed the limit, then we instead mark
+ * the entry as "dirty", and set the feerate for sorting purposes to be equal
+ * the feerate of the transaction without any descendants.
+ *
*/
class CTxMemPool
{
@@ -99,8 +285,46 @@ private:
uint64_t cachedInnerUsage; //! sum of dynamic memory usage of all the map elements (NOT the maps themselves)
public:
+ typedef boost::multi_index_container<
+ CTxMemPoolEntry,
+ boost::multi_index::indexed_by<
+ // sorted by txid
+ boost::multi_index::ordered_unique<mempoolentry_txid>,
+ // sorted by fee rate
+ boost::multi_index::ordered_non_unique<
+ boost::multi_index::identity<CTxMemPoolEntry>,
+ CompareTxMemPoolEntryByFee
+ >
+ >
+ > indexed_transaction_set;
+
mutable CCriticalSection cs;
- std::map<uint256, CTxMemPoolEntry> mapTx;
+ indexed_transaction_set mapTx;
+ typedef indexed_transaction_set::nth_index<0>::type::iterator txiter;
+ struct CompareIteratorByHash {
+ bool operator()(const txiter &a, const txiter &b) const {
+ return a->GetTx().GetHash() < b->GetTx().GetHash();
+ }
+ };
+ typedef std::set<txiter, CompareIteratorByHash> setEntries;
+
+private:
+ typedef std::map<txiter, setEntries, CompareIteratorByHash> cacheMap;
+
+ struct TxLinks {
+ setEntries parents;
+ setEntries children;
+ };
+
+ typedef std::map<txiter, TxLinks, CompareIteratorByHash> txlinksMap;
+ txlinksMap mapLinks;
+
+ const setEntries & GetMemPoolParents(txiter entry) const;
+ const setEntries & GetMemPoolChildren(txiter entry) const;
+ void UpdateParent(txiter entry, txiter parent, bool add);
+ void UpdateChild(txiter entry, txiter child, bool add);
+
+public:
std::map<COutPoint, CInPoint> mapNextTx;
std::map<uint256, std::pair<double, CAmount> > mapDeltas;
@@ -116,7 +340,13 @@ public:
void check(const CCoinsViewCache *pcoins) const;
void setSanityCheck(bool _fSanityCheck) { fSanityCheck = _fSanityCheck; }
+ // addUnchecked must updated state for all ancestors of a given transaction,
+ // to track size/count of descendant transactions. First version of
+ // addUnchecked can be used to have it call CalculateMemPoolAncestors(), and
+ // then invoke the second version.
bool addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry, bool fCurrentEstimate = true);
+ bool addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry, setEntries &setAncestors, bool fCurrentEstimate = true);
+
void remove(const CTransaction &tx, std::list<CTransaction>& removed, bool fRecursive = false);
void removeCoinbaseSpends(const CCoinsViewCache *pcoins, unsigned int nMemPoolHeight);
void removeConflicts(const CTransaction &tx, std::list<CTransaction>& removed);
@@ -138,6 +368,33 @@ public:
void ApplyDeltas(const uint256 hash, double &dPriorityDelta, CAmount &nFeeDelta);
void ClearPrioritisation(const uint256 hash);
+public:
+ /** Remove a set of transactions from the mempool.
+ * If a transaction is in this set, then all in-mempool descendants must
+ * also be in the set.*/
+ void RemoveStaged(setEntries &stage);
+
+ /** When adding transactions from a disconnected block back to the mempool,
+ * new mempool entries may have children in the mempool (which is generally
+ * not the case when otherwise adding transactions).
+ * UpdateTransactionsFromBlock() will find child transactions and update the
+ * descendant state for each transaction in hashesToUpdate (excluding any
+ * child transactions present in hashesToUpdate, which are already accounted
+ * for). Note: hashesToUpdate should be the set of transactions from the
+ * disconnected block that have been accepted back into the mempool.
+ */
+ void UpdateTransactionsFromBlock(const std::vector<uint256> &hashesToUpdate);
+
+ /** Try to calculate all in-mempool ancestors of entry.
+ * (these are all calculated including the tx itself)
+ * limitAncestorCount = max number of ancestors
+ * limitAncestorSize = max size of ancestors
+ * limitDescendantCount = max number of descendants any ancestor can have
+ * limitDescendantSize = max size of descendants any ancestor can have
+ * errString = populated with error reason if any limits are hit
+ */
+ bool CalculateMemPoolAncestors(const CTxMemPoolEntry &entry, setEntries &setAncestors, uint64_t limitAncestorCount, uint64_t limitAncestorSize, uint64_t limitDescendantCount, uint64_t limitDescendantSize, std::string &errString);
+
unsigned long size()
{
LOCK(cs);
@@ -169,6 +426,48 @@ public:
bool ReadFeeEstimates(CAutoFile& filein);
size_t DynamicMemoryUsage() const;
+
+private:
+ /** UpdateForDescendants is used by UpdateTransactionsFromBlock to update
+ * the descendants for a single transaction that has been added to the
+ * mempool but may have child transactions in the mempool, eg during a
+ * chain reorg. setExclude is the set of descendant transactions in the
+ * mempool that must not be accounted for (because any descendants in
+ * setExclude were added to the mempool after the transaction being
+ * updated and hence their state is already reflected in the parent
+ * state).
+ *
+ * If updating an entry requires looking at more than maxDescendantsToVisit
+ * transactions, outside of the ones in setExclude, then give up.
+ *
+ * cachedDescendants will be updated with the descendants of the transaction
+ * being updated, so that future invocations don't need to walk the
+ * same transaction again, if encountered in another transaction chain.
+ */
+ bool UpdateForDescendants(txiter updateIt,
+ int maxDescendantsToVisit,
+ cacheMap &cachedDescendants,
+ const std::set<uint256> &setExclude);
+ /** Update ancestors of hash to add/remove it as a descendant transaction. */
+ void UpdateAncestorsOf(bool add, txiter hash, setEntries &setAncestors);
+ /** For each transaction being removed, update ancestors and any direct children. */
+ void UpdateForRemoveFromMempool(const setEntries &entriesToRemove);
+ /** Sever link between specified transaction and direct children. */
+ void UpdateChildrenForRemoval(txiter entry);
+ /** Populate setDescendants with all in-mempool descendants of hash.
+ * Assumes that setDescendants includes all in-mempool descendants of anything
+ * already in it. */
+ void CalculateDescendants(txiter it, setEntries &setDescendants);
+
+ /** Before calling removeUnchecked for a given transaction,
+ * UpdateForRemoveFromMempool must be called on the entire (dependent) set
+ * of transactions being removed at the same time. We use each
+ * CTxMemPoolEntry's setMemPoolParents in order to walk ancestors of a
+ * given transaction that is removed, so we can't remove intermediate
+ * transactions in a chain before we've updated all the state for the
+ * removal.
+ */
+ void removeUnchecked(txiter entry);
};
/**
generated by cgit v1.2.3 (git 2.26.2) at 2024-11-01 16:51:33 +0000