Add a score index to the mempool.

The score index is meant to represent the order of priority for being included in a block for miners.  Initially this is set to the transactions modified (by any feeDelta) fee rate.  Index improvements and unit tests by sdaftuar.

4 files changed, 106 insertions, 12 deletions

diff --git a/src/rpcblockchain.cpp b/src/rpcblockchain.cpp
index c872822759..aede797531 100644
--- a/src/rpcblockchain.cpp
+++ b/src/rpcblockchain.cpp
@@ -190,6 +190,7 @@ UniValue mempoolToJSON(bool fVerbose = false)
             UniValue info(UniValue::VOBJ);
             info.push_back(Pair("size", (int)e.GetTxSize()));
             info.push_back(Pair("fee", ValueFromAmount(e.GetFee())));
+            info.push_back(Pair("modifiedfee", ValueFromAmount(e.GetModifiedFee())));
             info.push_back(Pair("time", e.GetTime()));
             info.push_back(Pair("height", (int)e.GetHeight()));
             info.push_back(Pair("startingpriority", e.GetPriority(e.GetHeight())));
@@ -247,6 +248,7 @@ UniValue getrawmempool(const UniValue& params, bool fHelp)
             "  \"transactionid\" : {       (json object)\n"
             "    \"size\" : n,             (numeric) transaction size in bytes\n"
             "    \"fee\" : n,              (numeric) transaction fee in " + CURRENCY_UNIT + "\n"
+            "    \"modifiedfee\" : n,      (numeric) transaction fee with fee deltas used for mining priority\n"
             "    \"time\" : n,             (numeric) local time transaction entered pool in seconds since 1 Jan 1970 GMT\n"
             "    \"height\" : n,           (numeric) block height when transaction entered pool\n"
             "    \"startingpriority\" : n, (numeric) priority when transaction entered pool\n"
diff --git a/src/test/mempool_tests.cpp b/src/test/mempool_tests.cpp
index 896e1237ed..e9f7378f74 100644
--- a/src/test/mempool_tests.cpp
+++ b/src/test/mempool_tests.cpp
@@ -102,12 +102,13 @@ BOOST_AUTO_TEST_CASE(MempoolRemoveTest)
     removed.clear();
 }
 
+template<int index>
 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();
+    typename CTxMemPool::indexed_transaction_set::nth_index<index>::type::iterator it = pool.mapTx.get<index>().begin();
     int count=0;
-    for (; it != pool.mapTx.get<1>().end(); ++it, ++count) {
+    for (; it != pool.mapTx.get<index>().end(); ++it, ++count) {
         BOOST_CHECK_EQUAL(it->GetTx().GetHash().ToString(), sortedOrder[count]);
     }
 }
@@ -163,7 +164,7 @@ BOOST_AUTO_TEST_CASE(MempoolIndexingTest)
     sortedOrder[2] = tx1.GetHash().ToString(); // 10000
     sortedOrder[3] = tx4.GetHash().ToString(); // 15000
     sortedOrder[4] = tx2.GetHash().ToString(); // 20000
-    CheckSort(pool, sortedOrder);
+    CheckSort<1>(pool, sortedOrder);
 
     /* low fee but with high fee child */
     /* tx6 -> tx7 -> tx8, tx9 -> tx10 */
@@ -175,7 +176,7 @@ BOOST_AUTO_TEST_CASE(MempoolIndexingTest)
     BOOST_CHECK_EQUAL(pool.size(), 6);
     // Check that at this point, tx6 is sorted low
     sortedOrder.insert(sortedOrder.begin(), tx6.GetHash().ToString());
-    CheckSort(pool, sortedOrder);
+    CheckSort<1>(pool, sortedOrder);
 
     CTxMemPool::setEntries setAncestors;
     setAncestors.insert(pool.mapTx.find(tx6.GetHash()));
@@ -201,7 +202,7 @@ BOOST_AUTO_TEST_CASE(MempoolIndexingTest)
     sortedOrder.erase(sortedOrder.begin());
     sortedOrder.push_back(tx6.GetHash().ToString());
     sortedOrder.push_back(tx7.GetHash().ToString());
-    CheckSort(pool, sortedOrder);
+    CheckSort<1>(pool, sortedOrder);
 
     /* low fee child of tx7 */
     CMutableTransaction tx8 = CMutableTransaction();
@@ -216,7 +217,7 @@ BOOST_AUTO_TEST_CASE(MempoolIndexingTest)
 
     // Now tx8 should be sorted low, but tx6/tx both high
     sortedOrder.insert(sortedOrder.begin(), tx8.GetHash().ToString());
-    CheckSort(pool, sortedOrder);
+    CheckSort<1>(pool, sortedOrder);
 
     /* low fee child of tx7 */
     CMutableTransaction tx9 = CMutableTransaction();
@@ -231,7 +232,7 @@ BOOST_AUTO_TEST_CASE(MempoolIndexingTest)
     // tx9 should be sorted low
     BOOST_CHECK_EQUAL(pool.size(), 9);
     sortedOrder.insert(sortedOrder.begin(), tx9.GetHash().ToString());
-    CheckSort(pool, sortedOrder);
+    CheckSort<1>(pool, sortedOrder);
 
     std::vector<std::string> snapshotOrder = sortedOrder;
 
@@ -273,7 +274,7 @@ BOOST_AUTO_TEST_CASE(MempoolIndexingTest)
     sortedOrder.insert(sortedOrder.begin()+5, tx9.GetHash().ToString());
     sortedOrder.insert(sortedOrder.begin()+6, tx8.GetHash().ToString());
     sortedOrder.insert(sortedOrder.begin()+7, tx10.GetHash().ToString()); // tx10 is just before tx6
-    CheckSort(pool, sortedOrder);
+    CheckSort<1>(pool, sortedOrder);
 
     // there should be 10 transactions in the mempool
     BOOST_CHECK_EQUAL(pool.size(), 10);
@@ -281,9 +282,42 @@ BOOST_AUTO_TEST_CASE(MempoolIndexingTest)
     // 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);
+    CheckSort<1>(pool, snapshotOrder);
+
+    pool.remove(pool.mapTx.find(tx9.GetHash())->GetTx(), removed, true);
+    pool.remove(pool.mapTx.find(tx8.GetHash())->GetTx(), removed, true);
+    /* Now check the sort on the mining score index.
+     * Final order should be:
+     *
+     * tx7 (2M)
+     * tx2 (20k)
+     * tx4 (15000)
+     * tx1/tx5 (10000)
+     * tx3/6 (0)
+     * (Ties resolved by hash)
+     */
+    sortedOrder.clear();
+    sortedOrder.push_back(tx7.GetHash().ToString());
+    sortedOrder.push_back(tx2.GetHash().ToString());
+    sortedOrder.push_back(tx4.GetHash().ToString());
+    if (tx1.GetHash() < tx5.GetHash()) {
+        sortedOrder.push_back(tx5.GetHash().ToString());
+        sortedOrder.push_back(tx1.GetHash().ToString());
+    } else {
+        sortedOrder.push_back(tx1.GetHash().ToString());
+        sortedOrder.push_back(tx5.GetHash().ToString());
+    }
+    if (tx3.GetHash() < tx6.GetHash()) {
+        sortedOrder.push_back(tx6.GetHash().ToString());
+        sortedOrder.push_back(tx3.GetHash().ToString());
+    } else {
+        sortedOrder.push_back(tx3.GetHash().ToString());
+        sortedOrder.push_back(tx6.GetHash().ToString());
+    }
+    CheckSort<3>(pool, sortedOrder);
 }
 
+
 BOOST_AUTO_TEST_CASE(MempoolSizeLimitTest)
 {
     CTxMemPool pool(CFeeRate(1000));
diff --git a/src/txmempool.cpp b/src/txmempool.cpp
index fa62cbf166..35be216287 100644
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -36,6 +36,8 @@ CTxMemPoolEntry::CTxMemPoolEntry(const CTransaction& _tx, const CAmount& _nFee,
     nFeesWithDescendants = nFee;
     CAmount nValueIn = tx.GetValueOut()+nFee;
     assert(inChainInputValue <= nValueIn);
+
+    feeDelta = 0;
 }
 
 CTxMemPoolEntry::CTxMemPoolEntry(const CTxMemPoolEntry& other)
@@ -53,6 +55,11 @@ CTxMemPoolEntry::GetPriority(unsigned int currentHeight) const
     return dResult;
 }
 
+void CTxMemPoolEntry::UpdateFeeDelta(int64_t newFeeDelta)
+{
+    feeDelta = newFeeDelta;
+}
+
 // Update the given tx for any in-mempool descendants.
 // Assumes that setMemPoolChildren is correct for the given tx and all
 // descendants.
@@ -392,6 +399,15 @@ bool CTxMemPool::addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry,
     }
     UpdateAncestorsOf(true, newit, setAncestors);
 
+    // Update transaction's score for any feeDelta created by PrioritiseTransaction
+    std::map<uint256, std::pair<double, CAmount> >::const_iterator pos = mapDeltas.find(hash);
+    if (pos != mapDeltas.end()) {
+        const std::pair<double, CAmount> &deltas = pos->second;
+        if (deltas.second) {
+            mapTx.modify(newit, update_fee_delta(deltas.second));
+        }
+    }
+
     nTransactionsUpdated++;
     totalTxSize += entry.GetTxSize();
     minerPolicyEstimator->processTransaction(entry, fCurrentEstimate);
@@ -769,6 +785,10 @@ void CTxMemPool::PrioritiseTransaction(const uint256 hash, const string strHash,
         std::pair<double, CAmount> &deltas = mapDeltas[hash];
         deltas.first += dPriorityDelta;
         deltas.second += nFeeDelta;
+        txiter it = mapTx.find(hash);
+        if (it != mapTx.end()) {
+            mapTx.modify(it, update_fee_delta(deltas.second));
+        }
     }
     LogPrintf("PrioritiseTransaction: %s priority += %f, fee += %d\n", strHash, dPriorityDelta, FormatMoney(nFeeDelta));
 }
@@ -818,8 +838,8 @@ bool CCoinsViewMemPool::HaveCoins(const uint256 &txid) const {
 
 size_t CTxMemPool::DynamicMemoryUsage() const {
     LOCK(cs);
-    // 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;
+    // Estimate the overhead of mapTx to be 12 pointers + an allocation, as no exact formula for boost::multi_index_contained is implemented.
+    return memusage::MallocUsage(sizeof(CTxMemPoolEntry) + 12 * sizeof(void*)) * mapTx.size() + memusage::DynamicUsage(mapNextTx) + memusage::DynamicUsage(mapDeltas) + memusage::DynamicUsage(mapLinks) + cachedInnerUsage;
 }
 
 void CTxMemPool::RemoveStaged(setEntries &stage) {
diff --git a/src/txmempool.h b/src/txmempool.h
index 334b547823..b011c38827 100644
--- a/src/txmempool.h
+++ b/src/txmempool.h
@@ -69,6 +69,7 @@ private:
     CAmount inChainInputValue; //! Sum of all txin values that are already in blockchain
     bool spendsCoinbase; //! keep track of transactions that spend a coinbase
     unsigned int sigOpCount; //! Legacy sig ops plus P2SH sig op count
+    int64_t feeDelta; //! Used for determining the priority of the transaction for mining in a block
 
     // Information about descendants of this transaction that are in the
     // mempool; if we remove this transaction we must remove all of these
@@ -98,10 +99,13 @@ public:
     unsigned int GetHeight() const { return entryHeight; }
     bool WasClearAtEntry() const { return hadNoDependencies; }
     unsigned int GetSigOpCount() const { return sigOpCount; }
+    int64_t GetModifiedFee() const { return nFee + feeDelta; }
     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);
+    // Updates the fee delta used for mining priority score
+    void UpdateFeeDelta(int64_t feeDelta);
 
     /** 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
@@ -139,6 +143,16 @@ struct set_dirty
         { e.SetDirty(); }
 };
 
+struct update_fee_delta
+{
+    update_fee_delta(int64_t _feeDelta) : feeDelta(_feeDelta) { }
+
+    void operator() (CTxMemPoolEntry &e) { e.UpdateFeeDelta(feeDelta); }
+
+private:
+    int64_t feeDelta;
+};
+
 // extracts a TxMemPoolEntry's transaction hash
 struct mempoolentry_txid
 {
@@ -186,6 +200,24 @@ public:
     }
 };
 
+/** \class CompareTxMemPoolEntryByScore
+ *
+ *  Sort by score of entry ((fee+delta)/size) in descending order
+ */
+class CompareTxMemPoolEntryByScore
+{
+public:
+    bool operator()(const CTxMemPoolEntry& a, const CTxMemPoolEntry& b)
+    {
+        double f1 = (double)a.GetModifiedFee() * b.GetTxSize();
+        double f2 = (double)b.GetModifiedFee() * a.GetTxSize();
+        if (f1 == f2) {
+            return b.GetTx().GetHash() < a.GetTx().GetHash();
+        }
+        return f1 > f2;
+    }
+};
+
 class CompareTxMemPoolEntryByEntryTime
 {
 public:
@@ -223,10 +255,11 @@ public:
  *
  * CTxMemPool::mapTx, and CTxMemPoolEntry bookkeeping:
  *
- * mapTx is a boost::multi_index that sorts the mempool on 3 criteria:
+ * mapTx is a boost::multi_index that sorts the mempool on 4 criteria:
  * - transaction hash
  * - feerate [we use max(feerate of tx, feerate of tx with all descendants)]
  * - time in mempool
+ * - mining score (feerate modified by any fee deltas from PrioritiseTransaction)
  *
  * Note: the term "descendant" refers to in-mempool transactions that depend on
  * this one, while "ancestor" refers to in-mempool transactions that a given
@@ -323,6 +356,11 @@ public:
             boost::multi_index::ordered_non_unique<
                 boost::multi_index::identity<CTxMemPoolEntry>,
                 CompareTxMemPoolEntryByEntryTime
+                >,
+            // sorted by score (for mining prioritization)
+            boost::multi_index::ordered_unique<
+                boost::multi_index::identity<CTxMemPoolEntry>,
+                CompareTxMemPoolEntryByScore
             >
         >
     > indexed_transaction_set;