diff options
Diffstat (limited to 'src/test/mempool_tests.cpp')
| -rw-r--r-- | src/test/mempool_tests.cpp | 334 |
1 files changed, 334 insertions, 0 deletions
diff --git a/src/test/mempool_tests.cpp b/src/test/mempool_tests.cpp index 2439689d7..0cf906a25 100644 --- a/src/test/mempool_tests.cpp +++ b/src/test/mempool_tests.cpp @@ -9,6 +9,7 @@ #include <boost/test/unit_test.hpp> #include <list> +#include <vector> BOOST_FIXTURE_TEST_SUITE(mempool_tests, TestingSetup) @@ -100,4 +101,337 @@ BOOST_AUTO_TEST_CASE(MempoolRemoveTest) removed.clear(); } +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(); + int count=0; + for (; it != pool.mapTx.get<1>().end(); ++it, ++count) { + BOOST_CHECK_EQUAL(it->GetTx().GetHash().ToString(), sortedOrder[count]); + } +} + +BOOST_AUTO_TEST_CASE(MempoolIndexingTest) +{ + CTxMemPool pool(CFeeRate(0)); + + /* 3rd highest fee */ + CMutableTransaction tx1 = CMutableTransaction(); + tx1.vout.resize(1); + tx1.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; + tx1.vout[0].nValue = 10 * COIN; + pool.addUnchecked(tx1.GetHash(), CTxMemPoolEntry(tx1, 10000LL, 0, 10.0, 1, true)); + + /* highest fee */ + CMutableTransaction tx2 = CMutableTransaction(); + tx2.vout.resize(1); + tx2.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; + tx2.vout[0].nValue = 2 * COIN; + pool.addUnchecked(tx2.GetHash(), CTxMemPoolEntry(tx2, 20000LL, 0, 9.0, 1, true)); + + /* lowest fee */ + CMutableTransaction tx3 = CMutableTransaction(); + tx3.vout.resize(1); + tx3.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; + tx3.vout[0].nValue = 5 * COIN; + pool.addUnchecked(tx3.GetHash(), CTxMemPoolEntry(tx3, 0LL, 0, 100.0, 1, true)); + + /* 2nd highest fee */ + CMutableTransaction tx4 = CMutableTransaction(); + tx4.vout.resize(1); + tx4.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; + tx4.vout[0].nValue = 6 * COIN; + pool.addUnchecked(tx4.GetHash(), CTxMemPoolEntry(tx4, 15000LL, 0, 1.0, 1, true)); + + /* equal fee rate to tx1, but newer */ + CMutableTransaction tx5 = CMutableTransaction(); + tx5.vout.resize(1); + tx5.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; + tx5.vout[0].nValue = 11 * COIN; + pool.addUnchecked(tx5.GetHash(), CTxMemPoolEntry(tx5, 10000LL, 1, 10.0, 1, true)); + BOOST_CHECK_EQUAL(pool.size(), 5); + + std::vector<std::string> sortedOrder; + sortedOrder.resize(5); + sortedOrder[0] = tx3.GetHash().ToString(); // 0 + sortedOrder[1] = tx5.GetHash().ToString(); // 10000 + sortedOrder[2] = tx1.GetHash().ToString(); // 10000 + sortedOrder[3] = tx4.GetHash().ToString(); // 15000 + sortedOrder[4] = tx2.GetHash().ToString(); // 20000 + CheckSort(pool, sortedOrder); + + /* low fee but with high fee child */ + /* tx6 -> tx7 -> tx8, tx9 -> tx10 */ + CMutableTransaction tx6 = CMutableTransaction(); + tx6.vout.resize(1); + tx6.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; + tx6.vout[0].nValue = 20 * COIN; + 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.insert(sortedOrder.begin(), tx6.GetHash().ToString()); + CheckSort(pool, sortedOrder); + + CTxMemPool::setEntries setAncestors; + setAncestors.insert(pool.mapTx.find(tx6.GetHash())); + CMutableTransaction tx7 = CMutableTransaction(); + tx7.vin.resize(1); + tx7.vin[0].prevout = COutPoint(tx6.GetHash(), 0); + tx7.vin[0].scriptSig = CScript() << OP_11; + tx7.vout.resize(2); + tx7.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; + tx7.vout[0].nValue = 10 * COIN; + tx7.vout[1].scriptPubKey = CScript() << OP_11 << OP_EQUAL; + tx7.vout[1].nValue = 1 * COIN; + + CTxMemPool::setEntries setAncestorsCalculated; + std::string dummy; + CTxMemPoolEntry entry7(tx7, 2000000LL, 1, 10.0, 1, true); + BOOST_CHECK_EQUAL(pool.CalculateMemPoolAncestors(entry7, setAncestorsCalculated, 100, 1000000, 1000, 1000000, dummy), true); + BOOST_CHECK(setAncestorsCalculated == setAncestors); + + pool.addUnchecked(tx7.GetHash(), CTxMemPoolEntry(tx7, 2000000LL, 1, 10.0, 1, true), setAncestors); + BOOST_CHECK_EQUAL(pool.size(), 7); + + // Now tx6 should be sorted higher (high fee child): tx7, tx6, tx2, ... + sortedOrder.erase(sortedOrder.begin()); + sortedOrder.push_back(tx6.GetHash().ToString()); + sortedOrder.push_back(tx7.GetHash().ToString()); + CheckSort(pool, sortedOrder); + + /* low fee child of tx7 */ + CMutableTransaction tx8 = CMutableTransaction(); + tx8.vin.resize(1); + tx8.vin[0].prevout = COutPoint(tx7.GetHash(), 0); + tx8.vin[0].scriptSig = CScript() << OP_11; + tx8.vout.resize(1); + tx8.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; + tx8.vout[0].nValue = 10 * COIN; + setAncestors.insert(pool.mapTx.find(tx7.GetHash())); + 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.insert(sortedOrder.begin(), tx8.GetHash().ToString()); + CheckSort(pool, sortedOrder); + + /* low fee child of tx7 */ + CMutableTransaction tx9 = CMutableTransaction(); + tx9.vin.resize(1); + tx9.vin[0].prevout = COutPoint(tx7.GetHash(), 1); + tx9.vin[0].scriptSig = CScript() << OP_11; + tx9.vout.resize(1); + tx9.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; + tx9.vout[0].nValue = 1 * COIN; + pool.addUnchecked(tx9.GetHash(), CTxMemPoolEntry(tx9, 0LL, 3, 10.0, 1, true), setAncestors); + + // tx9 should be sorted low + BOOST_CHECK_EQUAL(pool.size(), 9); + sortedOrder.insert(sortedOrder.begin(), tx9.GetHash().ToString()); + CheckSort(pool, sortedOrder); + + std::vector<std::string> snapshotOrder = sortedOrder; + + setAncestors.insert(pool.mapTx.find(tx8.GetHash())); + setAncestors.insert(pool.mapTx.find(tx9.GetHash())); + /* tx10 depends on tx8 and tx9 and has a high fee*/ + CMutableTransaction tx10 = CMutableTransaction(); + tx10.vin.resize(2); + tx10.vin[0].prevout = COutPoint(tx8.GetHash(), 0); + tx10.vin[0].scriptSig = CScript() << OP_11; + tx10.vin[1].prevout = COutPoint(tx9.GetHash(), 0); + tx10.vin[1].scriptSig = CScript() << OP_11; + tx10.vout.resize(1); + tx10.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; + tx10.vout[0].nValue = 10 * COIN; + + setAncestorsCalculated.clear(); + CTxMemPoolEntry entry10(tx10, 200000LL, 4, 10.0, 1, true); + BOOST_CHECK_EQUAL(pool.CalculateMemPoolAncestors(entry10, setAncestorsCalculated, 100, 1000000, 1000, 1000000, dummy), true); + BOOST_CHECK(setAncestorsCalculated == setAncestors); + + pool.addUnchecked(tx10.GetHash(), CTxMemPoolEntry(tx10, 200000LL, 4, 10.0, 1, true), setAncestors); + + /** + * tx8 and tx9 should both now be sorted higher + * Final order after tx10 is added: + * + * 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.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 + BOOST_CHECK_EQUAL(pool.size(), 10); + + // 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); +} + +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() |