Merge pull request #6722

58254aa Fix stale comment in CTxMemPool::TrimToSize. (Matt Corallo)
2bc5018 Fix comment formatting tabs (Matt Corallo)
8abe0f5 Undo GetMinFee-requires-extra-call-to-hit-0 (Matt Corallo)
9e93640 Drop minRelayTxFee to 1000 (Matt Corallo)
074cb15 Add reasonable test case for mempool trimming (Matt Corallo)
d355cf4 Only call TrimToSize once per reorg/blocks disconnect (Matt Corallo)
794a8ce Implement on-the-fly mempool size limitation. (Matt Corallo)
e6c7b36 Print mempool size in KB when adding txn (Matt Corallo)
241d607 Add CFeeRate += operator (Matt Corallo)
e8bcdce Track (and define) ::minRelayTxFee in CTxMemPool (Matt Corallo)
9c9b66f Fix calling mempool directly, instead of pool, in ATMP (Matt Corallo)
49b6fd5 Add Mempool Expire function to remove old transactions (Pieter Wuille)
78b82f4 Reverse the sort on the mempool's feerate index (Suhas Daftuar)

2 files changed, 177 insertions, 24 deletions

diff --git a/src/test/mempool_tests.cpp b/src/test/mempool_tests.cpp
index 5bf1e98e8f..0cf906a259 100644
--- a/src/test/mempool_tests.cpp
+++ b/src/test/mempool_tests.cpp
@@ -153,11 +153,11 @@ BOOST_AUTO_TEST_CASE(MempoolIndexingTest)
 
     std::vector<std::string> sortedOrder;
     sortedOrder.resize(5);
-    sortedOrder[0] = tx2.GetHash().ToString(); // 20000
-    sortedOrder[1] = tx4.GetHash().ToString(); // 15000
+    sortedOrder[0] = tx3.GetHash().ToString(); // 0
+    sortedOrder[1] = tx5.GetHash().ToString(); // 10000
     sortedOrder[2] = tx1.GetHash().ToString(); // 10000
-    sortedOrder[3] = tx5.GetHash().ToString(); // 10000
-    sortedOrder[4] = tx3.GetHash().ToString(); // 0
+    sortedOrder[3] = tx4.GetHash().ToString(); // 15000
+    sortedOrder[4] = tx2.GetHash().ToString(); // 20000
     CheckSort(pool, sortedOrder);
 
     /* low fee but with high fee child */
@@ -169,7 +169,7 @@ BOOST_AUTO_TEST_CASE(MempoolIndexingTest)
     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());
+    sortedOrder.insert(sortedOrder.begin(), tx6.GetHash().ToString());
     CheckSort(pool, sortedOrder);
 
     CTxMemPool::setEntries setAncestors;
@@ -194,9 +194,9 @@ BOOST_AUTO_TEST_CASE(MempoolIndexingTest)
     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());
+    sortedOrder.erase(sortedOrder.begin());
+    sortedOrder.push_back(tx6.GetHash().ToString());
+    sortedOrder.push_back(tx7.GetHash().ToString());
     CheckSort(pool, sortedOrder);
 
     /* low fee child of tx7 */
@@ -211,7 +211,7 @@ BOOST_AUTO_TEST_CASE(MempoolIndexingTest)
     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());
+    sortedOrder.insert(sortedOrder.begin(), tx8.GetHash().ToString());
     CheckSort(pool, sortedOrder);
 
     /* low fee child of tx7 */
@@ -226,7 +226,7 @@ BOOST_AUTO_TEST_CASE(MempoolIndexingTest)
 
     // tx9 should be sorted low
     BOOST_CHECK_EQUAL(pool.size(), 9);
-    sortedOrder.push_back(tx9.GetHash().ToString());
+    sortedOrder.insert(sortedOrder.begin(), tx9.GetHash().ToString());
     CheckSort(pool, sortedOrder);
 
     std::vector<std::string> snapshotOrder = sortedOrder;
@@ -255,21 +255,21 @@ BOOST_AUTO_TEST_CASE(MempoolIndexingTest)
      *  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)
+     *  tx5 = 10000 (1)
+     *  tx1 = 10000 (1)
+     *  tx4 = 15000 (1)
+     *  tx2 = 20000 (1)
+     *  tx9 = 200k (2 txs)
+     *  tx8 = 200k (2 txs)
+     *  tx10 = 200k (1 tx)
+     *  tx6 = 2.2M (5 txs)
+     *  tx7 = 2.2M (4 txs)
      */
-    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());
+    sortedOrder.erase(sortedOrder.begin(), sortedOrder.begin()+2); // take out tx9, tx8 from the beginning
+    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);
 
     // there should be 10 transactions in the mempool
@@ -281,4 +281,157 @@ BOOST_AUTO_TEST_CASE(MempoolIndexingTest)
     CheckSort(pool, snapshotOrder);
 }
 
+BOOST_AUTO_TEST_CASE(MempoolSizeLimitTest)
+{
+    CTxMemPool pool(CFeeRate(1000));
+
+    CMutableTransaction tx1 = CMutableTransaction();
+    tx1.vin.resize(1);
+    tx1.vin[0].scriptSig = CScript() << OP_1;
+    tx1.vout.resize(1);
+    tx1.vout[0].scriptPubKey = CScript() << OP_1 << OP_EQUAL;
+    tx1.vout[0].nValue = 10 * COIN;
+    pool.addUnchecked(tx1.GetHash(), CTxMemPoolEntry(tx1, 10000LL, 0, 10.0, 1, pool.HasNoInputsOf(tx1)));
+
+    CMutableTransaction tx2 = CMutableTransaction();
+    tx2.vin.resize(1);
+    tx2.vin[0].scriptSig = CScript() << OP_2;
+    tx2.vout.resize(1);
+    tx2.vout[0].scriptPubKey = CScript() << OP_2 << OP_EQUAL;
+    tx2.vout[0].nValue = 10 * COIN;
+    pool.addUnchecked(tx2.GetHash(), CTxMemPoolEntry(tx2, 5000LL, 0, 10.0, 1, pool.HasNoInputsOf(tx2)));
+
+    pool.TrimToSize(pool.DynamicMemoryUsage()); // should do nothing
+    BOOST_CHECK(pool.exists(tx1.GetHash()));
+    BOOST_CHECK(pool.exists(tx2.GetHash()));
+
+    pool.TrimToSize(pool.DynamicMemoryUsage() * 3 / 4); // should remove the lower-feerate transaction
+    BOOST_CHECK(pool.exists(tx1.GetHash()));
+    BOOST_CHECK(!pool.exists(tx2.GetHash()));
+
+    pool.addUnchecked(tx2.GetHash(), CTxMemPoolEntry(tx2, 5000LL, 0, 10.0, 1, pool.HasNoInputsOf(tx2)));
+    CMutableTransaction tx3 = CMutableTransaction();
+    tx3.vin.resize(1);
+    tx3.vin[0].prevout = COutPoint(tx2.GetHash(), 0);
+    tx3.vin[0].scriptSig = CScript() << OP_2;
+    tx3.vout.resize(1);
+    tx3.vout[0].scriptPubKey = CScript() << OP_3 << OP_EQUAL;
+    tx3.vout[0].nValue = 10 * COIN;
+    pool.addUnchecked(tx3.GetHash(), CTxMemPoolEntry(tx3, 20000LL, 0, 10.0, 1, pool.HasNoInputsOf(tx3)));
+
+    pool.TrimToSize(pool.DynamicMemoryUsage() * 3 / 4); // tx3 should pay for tx2 (CPFP)
+    BOOST_CHECK(!pool.exists(tx1.GetHash()));
+    BOOST_CHECK(pool.exists(tx2.GetHash()));
+    BOOST_CHECK(pool.exists(tx3.GetHash()));
+
+    pool.TrimToSize(::GetSerializeSize(CTransaction(tx1), SER_NETWORK, PROTOCOL_VERSION)); // mempool is limited to tx1's size in memory usage, so nothing fits
+    BOOST_CHECK(!pool.exists(tx1.GetHash()));
+    BOOST_CHECK(!pool.exists(tx2.GetHash()));
+    BOOST_CHECK(!pool.exists(tx3.GetHash()));
+
+    CFeeRate maxFeeRateRemoved(25000, ::GetSerializeSize(CTransaction(tx3), SER_NETWORK, PROTOCOL_VERSION) + ::GetSerializeSize(CTransaction(tx2), SER_NETWORK, PROTOCOL_VERSION));
+    BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), maxFeeRateRemoved.GetFeePerK() + 1000);
+
+    CMutableTransaction tx4 = CMutableTransaction();
+    tx4.vin.resize(2);
+    tx4.vin[0].prevout.SetNull();
+    tx4.vin[0].scriptSig = CScript() << OP_4;
+    tx4.vin[1].prevout.SetNull();
+    tx4.vin[1].scriptSig = CScript() << OP_4;
+    tx4.vout.resize(2);
+    tx4.vout[0].scriptPubKey = CScript() << OP_4 << OP_EQUAL;
+    tx4.vout[0].nValue = 10 * COIN;
+    tx4.vout[1].scriptPubKey = CScript() << OP_4 << OP_EQUAL;
+    tx4.vout[1].nValue = 10 * COIN;
+
+    CMutableTransaction tx5 = CMutableTransaction();
+    tx5.vin.resize(2);
+    tx5.vin[0].prevout = COutPoint(tx4.GetHash(), 0);
+    tx5.vin[0].scriptSig = CScript() << OP_4;
+    tx5.vin[1].prevout.SetNull();
+    tx5.vin[1].scriptSig = CScript() << OP_5;
+    tx5.vout.resize(2);
+    tx5.vout[0].scriptPubKey = CScript() << OP_5 << OP_EQUAL;
+    tx5.vout[0].nValue = 10 * COIN;
+    tx5.vout[1].scriptPubKey = CScript() << OP_5 << OP_EQUAL;
+    tx5.vout[1].nValue = 10 * COIN;
+
+    CMutableTransaction tx6 = CMutableTransaction();
+    tx6.vin.resize(2);
+    tx6.vin[0].prevout = COutPoint(tx4.GetHash(), 1);
+    tx6.vin[0].scriptSig = CScript() << OP_4;
+    tx6.vin[1].prevout.SetNull();
+    tx6.vin[1].scriptSig = CScript() << OP_6;
+    tx6.vout.resize(2);
+    tx6.vout[0].scriptPubKey = CScript() << OP_6 << OP_EQUAL;
+    tx6.vout[0].nValue = 10 * COIN;
+    tx6.vout[1].scriptPubKey = CScript() << OP_6 << OP_EQUAL;
+    tx6.vout[1].nValue = 10 * COIN;
+
+    CMutableTransaction tx7 = CMutableTransaction();
+    tx7.vin.resize(2);
+    tx7.vin[0].prevout = COutPoint(tx5.GetHash(), 0);
+    tx7.vin[0].scriptSig = CScript() << OP_5;
+    tx7.vin[1].prevout = COutPoint(tx6.GetHash(), 0);
+    tx7.vin[1].scriptSig = CScript() << OP_6;
+    tx7.vout.resize(2);
+    tx7.vout[0].scriptPubKey = CScript() << OP_7 << OP_EQUAL;
+    tx7.vout[0].nValue = 10 * COIN;
+    tx7.vout[0].scriptPubKey = CScript() << OP_7 << OP_EQUAL;
+    tx7.vout[0].nValue = 10 * COIN;
+
+    pool.addUnchecked(tx4.GetHash(), CTxMemPoolEntry(tx4, 7000LL, 0, 10.0, 1, pool.HasNoInputsOf(tx4)));
+    pool.addUnchecked(tx5.GetHash(), CTxMemPoolEntry(tx5, 1000LL, 0, 10.0, 1, pool.HasNoInputsOf(tx5)));
+    pool.addUnchecked(tx6.GetHash(), CTxMemPoolEntry(tx6, 1100LL, 0, 10.0, 1, pool.HasNoInputsOf(tx6)));
+    pool.addUnchecked(tx7.GetHash(), CTxMemPoolEntry(tx7, 9000LL, 0, 10.0, 1, pool.HasNoInputsOf(tx7)));
+
+    // we only require this remove, at max, 2 txn, because its not clear what we're really optimizing for aside from that
+    pool.TrimToSize(pool.DynamicMemoryUsage() - 1);
+    BOOST_CHECK(pool.exists(tx4.GetHash()));
+    BOOST_CHECK(pool.exists(tx6.GetHash()));
+    BOOST_CHECK(!pool.exists(tx7.GetHash()));
+
+    if (!pool.exists(tx5.GetHash()))
+        pool.addUnchecked(tx5.GetHash(), CTxMemPoolEntry(tx5, 1000LL, 0, 10.0, 1, pool.HasNoInputsOf(tx5)));
+    pool.addUnchecked(tx7.GetHash(), CTxMemPoolEntry(tx7, 9000LL, 0, 10.0, 1, pool.HasNoInputsOf(tx7)));
+
+    pool.TrimToSize(pool.DynamicMemoryUsage() / 2); // should maximize mempool size by only removing 5/7
+    BOOST_CHECK(pool.exists(tx4.GetHash()));
+    BOOST_CHECK(!pool.exists(tx5.GetHash()));
+    BOOST_CHECK(pool.exists(tx6.GetHash()));
+    BOOST_CHECK(!pool.exists(tx7.GetHash()));
+
+    pool.addUnchecked(tx5.GetHash(), CTxMemPoolEntry(tx5, 1000LL, 0, 10.0, 1, pool.HasNoInputsOf(tx5)));
+    pool.addUnchecked(tx7.GetHash(), CTxMemPoolEntry(tx7, 9000LL, 0, 10.0, 1, pool.HasNoInputsOf(tx7)));
+
+    std::vector<CTransaction> vtx;
+    std::list<CTransaction> conflicts;
+    SetMockTime(42);
+    SetMockTime(42 + CTxMemPool::ROLLING_FEE_HALFLIFE);
+    BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), maxFeeRateRemoved.GetFeePerK() + 1000);
+    // ... we should keep the same min fee until we get a block
+    pool.removeForBlock(vtx, 1, conflicts);
+    SetMockTime(42 + 2*CTxMemPool::ROLLING_FEE_HALFLIFE);
+    BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), (maxFeeRateRemoved.GetFeePerK() + 1000)/2);
+    // ... then feerate should drop 1/2 each halflife
+
+    SetMockTime(42 + 2*CTxMemPool::ROLLING_FEE_HALFLIFE + CTxMemPool::ROLLING_FEE_HALFLIFE/2);
+    BOOST_CHECK_EQUAL(pool.GetMinFee(pool.DynamicMemoryUsage() * 5 / 2).GetFeePerK(), (maxFeeRateRemoved.GetFeePerK() + 1000)/4);
+    // ... with a 1/2 halflife when mempool is < 1/2 its target size
+
+    SetMockTime(42 + 2*CTxMemPool::ROLLING_FEE_HALFLIFE + CTxMemPool::ROLLING_FEE_HALFLIFE/2 + CTxMemPool::ROLLING_FEE_HALFLIFE/4);
+    BOOST_CHECK_EQUAL(pool.GetMinFee(pool.DynamicMemoryUsage() * 9 / 2).GetFeePerK(), (maxFeeRateRemoved.GetFeePerK() + 1000)/8);
+    // ... with a 1/4 halflife when mempool is < 1/4 its target size
+
+    SetMockTime(42 + 7*CTxMemPool::ROLLING_FEE_HALFLIFE + CTxMemPool::ROLLING_FEE_HALFLIFE/2 + CTxMemPool::ROLLING_FEE_HALFLIFE/4);
+    BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), 1000);
+    // ... but feerate should never drop below 1000
+
+    SetMockTime(42 + 8*CTxMemPool::ROLLING_FEE_HALFLIFE + CTxMemPool::ROLLING_FEE_HALFLIFE/2 + CTxMemPool::ROLLING_FEE_HALFLIFE/4);
+    BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), 0);
+    // ... unless it has gone all the way to 0 (after getting past 1000/2)
+
+    SetMockTime(0);
+}
+
 BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/test/txvalidationcache_tests.cpp b/src/test/txvalidationcache_tests.cpp
index edad18644e..9b8e1c088b 100644
--- a/src/test/txvalidationcache_tests.cpp
+++ b/src/test/txvalidationcache_tests.cpp
@@ -23,7 +23,7 @@ ToMemPool(CMutableTransaction& tx)
     LOCK(cs_main);
 
     CValidationState state;
-    return AcceptToMemoryPool(mempool, state, tx, false, NULL, false);
+    return AcceptToMemoryPool(mempool, state, tx, false, NULL, true, false);
 }
 
 BOOST_FIXTURE_TEST_CASE(tx_mempool_block_doublespend, TestChain100Setup)