Track transaction packages in CTxMemPoolEntry

Associate with each CTxMemPoolEntry all the size/fees of descendant
mempool transactions.  Sort mempool by max(feerate of entry, feerate
of descendants).  Update statistics on-the-fly as transactions enter
or leave the mempool.

Also add ancestor and descendant limiting, so that transactions can
be rejected if the number or size of unconfirmed ancestors exceeds
a target, or if adding a transaction would cause some other mempool
entry to have too many (or too large) a set of unconfirmed in-
mempool descendants.

1 files changed, 266 insertions, 7 deletions

diff --git a/src/txmempool.h b/src/txmempool.h
index 6b6b05454a..f0c3f7e0f1 100644
--- a/src/txmempool.h
+++ b/src/txmempool.h
@@ -7,6 +7,7 @@
 #define BITCOIN_TXMEMPOOL_H
 
 #include <list>
+#include <set>
 
 #include "amount.h"
 #include "coins.h"
@@ -34,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:
@@ -45,27 +62,69 @@ private:
     size_t nTxSize; //! ... and avoid recomputing tx size
     size_t nModSize; //! ... and modified size for priority
     size_t nUsageSize; //! ... and total memory usage
-    CFeeRate feeRate; //! ... and fee per kB
     int64_t nTime; //! Local time when entering the mempool
     double dPriority; //! Priority when entering the mempool
     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; }
     double GetPriority(unsigned int currentHeight) const;
     CAmount GetFee() const { return nFee; }
-    CFeeRate GetFeeRate() const { return feeRate; }
     size_t GetTxSize() const { return nTxSize; }
     int64_t GetTime() const { return nTime; }
     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
@@ -78,14 +137,49 @@ struct mempoolentry_txid
     }
 };
 
+/** \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)
     {
-        if (a.GetFeeRate() == b.GetFeeRate())
+        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 a.GetFeeRate() > b.GetFeeRate();
+        }
+        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();
     }
 };
 
@@ -114,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
 {
@@ -141,6 +300,31 @@ public:
 
     mutable CCriticalSection cs;
     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;
 
@@ -156,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);
@@ -178,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);
@@ -209,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);
 };
 
 /**