Add reasonable test case for mempool trimming

2 files changed, 157 insertions, 1 deletions

diff --git a/src/test/mempool_tests.cpp b/src/test/mempool_tests.cpp
index 79d806bd22..dce278d999 100644
--- a/src/test/mempool_tests.cpp
+++ b/src/test/mempool_tests.cpp
@@ -281,4 +281,158 @@ 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);
+    pool.GetMinFee(1);
+    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/txmempool.h b/src/txmempool.h
index e8572e7bda..319b972c3a 100644
--- a/src/txmempool.h
+++ b/src/txmempool.h
@@ -290,11 +290,13 @@ private:
     mutable int64_t lastRollingFeeUpdate;
     mutable bool blockSinceLastRollingFeeBump;
     mutable double rollingMinimumFeeRate; //! minimum fee to get into the pool, decreases exponentially
-    static const int ROLLING_FEE_HALFLIFE = 60 * 60 * 12;
 
     void trackPackageRemoved(const CFeeRate& rate);
 
 public:
+
+    static const int ROLLING_FEE_HALFLIFE = 60 * 60 * 12; // public only for testing
+
     typedef boost::multi_index_container<
         CTxMemPoolEntry,
         boost::multi_index::indexed_by<