aboutsummaryrefslogtreecommitdiff
path: root/src/txmempool.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/txmempool.h')
-rw-r--r--src/txmempool.h309
1 files changed, 305 insertions, 4 deletions
diff --git a/src/txmempool.h b/src/txmempool.h
index ea36ce1ad5..c0eef0dd22 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,35 @@ 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
+ * fSearchForParents = whether to search a tx's vin for in-mempool parents, or
+ * look up parents from mapLinks. Must be true for entries not in the mempool
+ */
+ bool CalculateMemPoolAncestors(const CTxMemPoolEntry &entry, setEntries &setAncestors, uint64_t limitAncestorCount, uint64_t limitAncestorSize, uint64_t limitDescendantCount, uint64_t limitDescendantSize, std::string &errString, bool fSearchForParents = true);
+
unsigned long size()
{
LOCK(cs);
@@ -169,6 +428,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);
};
/**