LCOV - code coverage report
Current view: top level - src/test - mempool_tests.cpp (source / functions) Hit Total Coverage
Test: total_coverage.info Lines: 386 394 98.0 %
Date: 2025-02-23 09:33:43 Functions: 11 11 100.0 %

          Line data    Source code
       1             : // Copyright (c) 2011-2014 The Bitcoin Core developers
       2             : // Distributed under the MIT software license, see the accompanying
       3             : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
       4             : 
       5             : #include "test/test_pivx.h"
       6             : 
       7             : #include "policy/feerate.h"
       8             : #include "txmempool.h"
       9             : #include "util/system.h"
      10             : 
      11             : #include <boost/test/unit_test.hpp>
      12             : 
      13             : BOOST_FIXTURE_TEST_SUITE(mempool_tests, TestingSetup)
      14             : 
      15           2 : BOOST_AUTO_TEST_CASE(MempoolRemoveTest)
      16             : {
      17             :     // Test CTxMemPool::remove functionality
      18             : 
      19           1 :     TestMemPoolEntryHelper entry;
      20             :     // Parent transaction with three children,
      21             :     // and three grand-children:
      22           2 :     CMutableTransaction txParent;
      23           1 :     txParent.vin.resize(1);
      24           1 :     txParent.vin[0].scriptSig = CScript() << OP_11;
      25           1 :     txParent.vout.resize(3);
      26           4 :     for (int i = 0; i < 3; i++)
      27             :     {
      28           3 :         txParent.vout[i].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
      29           3 :         txParent.vout[i].nValue = 33000LL;
      30             :     }
      31           8 :     CMutableTransaction txChild[3];
      32           4 :     for (int i = 0; i < 3; i++)
      33             :     {
      34           3 :         txChild[i].vin.resize(1);
      35           3 :         txChild[i].vin[0].scriptSig = CScript() << OP_11;
      36           3 :         txChild[i].vin[0].prevout.hash = txParent.GetHash();
      37           3 :         txChild[i].vin[0].prevout.n = i;
      38           3 :         txChild[i].vout.resize(1);
      39           3 :         txChild[i].vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
      40           3 :         txChild[i].vout[0].nValue = 11000LL;
      41             :     }
      42           8 :     CMutableTransaction txGrandChild[3];
      43           4 :     for (int i = 0; i < 3; i++)
      44             :     {
      45           3 :         txGrandChild[i].vin.resize(1);
      46           3 :         txGrandChild[i].vin[0].scriptSig = CScript() << OP_11;
      47           3 :         txGrandChild[i].vin[0].prevout.hash = txChild[i].GetHash();
      48           3 :         txGrandChild[i].vin[0].prevout.n = 0;
      49           3 :         txGrandChild[i].vout.resize(1);
      50           3 :         txGrandChild[i].vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
      51           3 :         txGrandChild[i].vout[0].nValue = 11000LL;
      52             :     }
      53             : 
      54             : 
      55           2 :     CTxMemPool testPool(CFeeRate(0));
      56             : 
      57             :     // Nothing in pool, remove should do nothing:
      58           1 :     unsigned int poolSize = testPool.size();
      59           1 :     testPool.removeRecursive(txParent);
      60           1 :     BOOST_CHECK_EQUAL(testPool.size(), poolSize);
      61             : 
      62             :     // Just the parent:
      63           1 :     testPool.addUnchecked(txParent.GetHash(), entry.FromTx(txParent));
      64           1 :     poolSize = testPool.size();
      65           1 :     testPool.removeRecursive(txParent);
      66           1 :     BOOST_CHECK_EQUAL(testPool.size(), poolSize - 1);
      67             : 
      68             :     // Parent, children, grandchildren:
      69           1 :     testPool.addUnchecked(txParent.GetHash(), entry.FromTx(txParent));
      70           4 :     for (int i = 0; i < 3; i++)
      71             :     {
      72           3 :         testPool.addUnchecked(txChild[i].GetHash(), entry.FromTx(txChild[i]));
      73           6 :         testPool.addUnchecked(txGrandChild[i].GetHash(), entry.FromTx(txGrandChild[i]));
      74             :     }
      75             :     // Remove Child[0], GrandChild[0] should be removed:
      76           1 :     poolSize = testPool.size();
      77           1 :     testPool.removeRecursive(txChild[0]);
      78           1 :     BOOST_CHECK_EQUAL(testPool.size(), poolSize - 2);
      79             :     // ... make sure grandchild and child are gone:
      80           1 :     poolSize = testPool.size();
      81           1 :     testPool.removeRecursive(txGrandChild[0]);
      82           1 :     BOOST_CHECK_EQUAL(testPool.size(), poolSize);
      83           1 :     poolSize = testPool.size();
      84           1 :     testPool.removeRecursive(txChild[0]);
      85           1 :     BOOST_CHECK_EQUAL(testPool.size(), poolSize);
      86             :     // Remove parent, all children/grandchildren should go:
      87           1 :     poolSize = testPool.size();
      88           1 :     testPool.removeRecursive(txParent);
      89           1 :     BOOST_CHECK_EQUAL(testPool.size(), poolSize - 5);
      90           1 :     BOOST_CHECK_EQUAL(testPool.size(), 0);
      91             : 
      92             :     // Add children and grandchildren, but NOT the parent (simulate the parent being in a block)
      93           4 :     for (int i = 0; i < 3; i++)
      94             :     {
      95           3 :         testPool.addUnchecked(txChild[i].GetHash(), entry.FromTx(txChild[i]));
      96           6 :         testPool.addUnchecked(txGrandChild[i].GetHash(), entry.FromTx(txGrandChild[i]));
      97             :     }
      98             :     // Now remove the parent, as might happen if a block-re-org occurs but the parent cannot be
      99             :     // put into the mempool (maybe because it is non-standard):
     100           1 :     poolSize = testPool.size();
     101           1 :     testPool.removeRecursive(txParent);
     102           1 :     BOOST_CHECK_EQUAL(testPool.size(), poolSize - 6);
     103           1 :     BOOST_CHECK_EQUAL(testPool.size(), 0);
     104           1 : }
     105             : 
     106             : template<typename name>
     107          12 : void CheckSort(CTxMemPool &pool, std::vector<std::string> &sortedOrder)
     108             : {
     109          12 :     BOOST_CHECK_EQUAL(pool.size(), sortedOrder.size());
     110          12 :     typename CTxMemPool::indexed_transaction_set::index<name>::type::iterator it = pool.mapTx.get<name>().begin();
     111          12 :     int count=0;
     112         182 :     for (; it != pool.mapTx.get<name>().end(); ++it, ++count) {
     113         170 :         BOOST_CHECK_EQUAL(it->GetTx().GetHash().ToString(), sortedOrder[count]);
     114             :     }
     115          12 : }
     116             : 
     117           2 : BOOST_AUTO_TEST_CASE(MempoolIndexingTest)
     118             : {
     119           2 :     CTxMemPool pool(CFeeRate(0));
     120           1 :     TestMemPoolEntryHelper entry;
     121             : 
     122             :     /* 3rd highest fee */
     123           2 :     CMutableTransaction tx1 = CMutableTransaction();
     124           1 :     tx1.vout.resize(1);
     125           1 :     tx1.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
     126           1 :     tx1.vout[0].nValue = 10 * COIN;
     127           1 :     pool.addUnchecked(tx1.GetHash(), entry.Fee(10000LL).FromTx(tx1));
     128             : 
     129             :     /* highest fee */
     130           2 :     CMutableTransaction tx2 = CMutableTransaction();
     131           1 :     tx2.vout.resize(1);
     132           1 :     tx2.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
     133           1 :     tx2.vout[0].nValue = 2 * COIN;
     134           1 :     pool.addUnchecked(tx2.GetHash(), entry.Fee(20000LL).FromTx(tx2));
     135             : 
     136             :     /* lowest fee */
     137           2 :     CMutableTransaction tx3 = CMutableTransaction();
     138           1 :     tx3.vout.resize(1);
     139           1 :     tx3.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
     140           1 :     tx3.vout[0].nValue = 5 * COIN;
     141           1 :     pool.addUnchecked(tx3.GetHash(), entry.Fee(0LL).FromTx(tx3));
     142             : 
     143             :     /* 2nd highest fee */
     144           2 :     CMutableTransaction tx4 = CMutableTransaction();
     145           1 :     tx4.vout.resize(1);
     146           1 :     tx4.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
     147           1 :     tx4.vout[0].nValue = 6 * COIN;
     148           1 :     pool.addUnchecked(tx4.GetHash(), entry.Fee(15000LL).FromTx(tx4));
     149             : 
     150             :     /* equal fee rate to tx1, but newer */
     151           2 :     CMutableTransaction tx5 = CMutableTransaction();
     152           1 :     tx5.vout.resize(1);
     153           1 :     tx5.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
     154           1 :     tx5.vout[0].nValue = 11 * COIN;
     155           1 :     entry.nTime = 1;
     156           1 :     pool.addUnchecked(tx5.GetHash(), entry.Fee(10000LL).FromTx(tx5));
     157           1 :     BOOST_CHECK_EQUAL(pool.size(), 5);
     158             : 
     159           2 :     std::vector<std::string> sortedOrder;
     160           1 :     sortedOrder.resize(5);
     161           1 :     sortedOrder[0] = tx3.GetHash().ToString(); // 0
     162           1 :     sortedOrder[1] = tx5.GetHash().ToString(); // 10000
     163           1 :     sortedOrder[2] = tx1.GetHash().ToString(); // 10000
     164           1 :     sortedOrder[3] = tx4.GetHash().ToString(); // 15000
     165           1 :     sortedOrder[4] = tx2.GetHash().ToString(); // 20000
     166           1 :     CheckSort<descendant_score>(pool, sortedOrder);
     167             : 
     168             :     /* low fee but with high fee child */
     169             :     /* tx6 -> tx7 -> tx8, tx9 -> tx10 */
     170           1 :     CMutableTransaction tx6 = CMutableTransaction();
     171           1 :     tx6.vout.resize(1);
     172           1 :     tx6.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
     173           1 :     tx6.vout[0].nValue = 20 * COIN;
     174           1 :     pool.addUnchecked(tx6.GetHash(), entry.Fee(0LL).FromTx(tx6));
     175           1 :     BOOST_CHECK_EQUAL(pool.size(), 6);
     176             :     // Check that at this point, tx6 is sorted low
     177           1 :     sortedOrder.insert(sortedOrder.begin(), tx6.GetHash().ToString());
     178           1 :     CheckSort<descendant_score>(pool, sortedOrder);
     179             : 
     180           2 :     CTxMemPool::setEntries setAncestors;
     181           2 :     setAncestors.insert(pool.mapTx.find(tx6.GetHash()));
     182           2 :     CMutableTransaction tx7 = CMutableTransaction();
     183           1 :     tx7.vin.resize(1);
     184           1 :     tx7.vin[0].prevout = COutPoint(tx6.GetHash(), 0);
     185           1 :     tx7.vin[0].scriptSig = CScript() << OP_11;
     186           1 :     tx7.vout.resize(2);
     187           1 :     tx7.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
     188           1 :     tx7.vout[0].nValue = 10 * COIN;
     189           1 :     tx7.vout[1].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
     190           1 :     tx7.vout[1].nValue = 1 * COIN;
     191             : 
     192           2 :     CTxMemPool::setEntries setAncestorsCalculated;
     193           2 :     std::string dummy;
     194           2 :     BOOST_CHECK_EQUAL(pool.CalculateMemPoolAncestors(entry.Fee(2000000LL).FromTx(tx7), setAncestorsCalculated, 100, 1000000, 1000, 1000000, dummy), true);
     195           2 :     BOOST_CHECK(setAncestorsCalculated == setAncestors);
     196             : 
     197           1 :     pool.addUnchecked(tx7.GetHash(), entry.FromTx(tx7), setAncestors);
     198           1 :     BOOST_CHECK_EQUAL(pool.size(), 7);
     199             : 
     200             :     // Now tx6 should be sorted higher (high fee child): tx7, tx6, tx2, ...
     201           1 :     sortedOrder.erase(sortedOrder.begin());
     202           2 :     sortedOrder.push_back(tx6.GetHash().ToString());
     203           2 :     sortedOrder.push_back(tx7.GetHash().ToString());
     204           1 :     CheckSort<descendant_score>(pool, sortedOrder);
     205             : 
     206             :     /* low fee child of tx7 */
     207           2 :     CMutableTransaction tx8 = CMutableTransaction();
     208           1 :     tx8.vin.resize(1);
     209           1 :     tx8.vin[0].prevout = COutPoint(tx7.GetHash(), 0);
     210           1 :     tx8.vin[0].scriptSig = CScript() << OP_11;
     211           1 :     tx8.vout.resize(1);
     212           1 :     tx8.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
     213           1 :     tx8.vout[0].nValue = 10 * COIN;
     214           2 :     setAncestors.insert(pool.mapTx.find(tx7.GetHash()));
     215           1 :     pool.addUnchecked(tx8.GetHash(), entry.Fee(0LL).Time(2).FromTx(tx8), setAncestors);
     216             : 
     217             :     // Now tx8 should be sorted low, but tx6/tx both high
     218           1 :     sortedOrder.insert(sortedOrder.begin(), tx8.GetHash().ToString());
     219           1 :     CheckSort<descendant_score>(pool, sortedOrder);
     220             : 
     221             :     /* low fee child of tx7 */
     222           2 :     CMutableTransaction tx9 = CMutableTransaction();
     223           1 :     tx9.vin.resize(1);
     224           1 :     tx9.vin[0].prevout = COutPoint(tx7.GetHash(), 1);
     225           1 :     tx9.vin[0].scriptSig = CScript() << OP_11;
     226           1 :     tx9.vout.resize(1);
     227           1 :     tx9.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
     228           1 :     tx9.vout[0].nValue = 1 * COIN;
     229           1 :     pool.addUnchecked(tx9.GetHash(), entry.Fee(0LL).Time(3).FromTx(tx9), setAncestors);
     230             : 
     231             :     // tx9 should be sorted low
     232           1 :     BOOST_CHECK_EQUAL(pool.size(), 9);
     233           1 :     sortedOrder.insert(sortedOrder.begin(), tx9.GetHash().ToString());
     234           1 :     CheckSort<descendant_score>(pool, sortedOrder);
     235             : 
     236           2 :     std::vector<std::string> snapshotOrder = sortedOrder;
     237             : 
     238           2 :     setAncestors.insert(pool.mapTx.find(tx8.GetHash()));
     239           2 :     setAncestors.insert(pool.mapTx.find(tx9.GetHash()));
     240             :     /* tx10 depends on tx8 and tx9 and has a high fee*/
     241           2 :     CMutableTransaction tx10 = CMutableTransaction();
     242           1 :     tx10.vin.resize(2);
     243           1 :     tx10.vin[0].prevout = COutPoint(tx8.GetHash(), 0);
     244           1 :     tx10.vin[0].scriptSig = CScript() << OP_11;
     245           1 :     tx10.vin[1].prevout = COutPoint(tx9.GetHash(), 0);
     246           1 :     tx10.vin[1].scriptSig = CScript() << OP_11;
     247           1 :     tx10.vout.resize(1);
     248           1 :     tx10.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
     249           1 :     tx10.vout[0].nValue = 10 * COIN;
     250             : 
     251           1 :     setAncestorsCalculated.clear();
     252           2 :     BOOST_CHECK_EQUAL(pool.CalculateMemPoolAncestors(entry.Fee(200000LL).Time(4).FromTx(tx10), setAncestorsCalculated, 100, 1000000, 1000, 1000000, dummy), true);
     253           2 :     BOOST_CHECK(setAncestorsCalculated == setAncestors);
     254             : 
     255           1 :     pool.addUnchecked(tx10.GetHash(), entry.FromTx(tx10), setAncestors);
     256             : 
     257             :     /**
     258             :      *  tx8 and tx9 should both now be sorted higher
     259             :      *  Final order after tx10 is added:
     260             :      *
     261             :      *  tx3 = 0 (1)
     262             :      *  tx5 = 10000 (1)
     263             :      *  tx1 = 10000 (1)
     264             :      *  tx4 = 15000 (1)
     265             :      *  tx2 = 20000 (1)
     266             :      *  tx9 = 200k (2 txs)
     267             :      *  tx8 = 200k (2 txs)
     268             :      *  tx10 = 200k (1 tx)
     269             :      *  tx6 = 2.2M (5 txs)
     270             :      *  tx7 = 2.2M (4 txs)
     271             :      */
     272           1 :     sortedOrder.erase(sortedOrder.begin(), sortedOrder.begin()+2); // take out tx9, tx8 from the beginning
     273           1 :     sortedOrder.insert(sortedOrder.begin()+5, tx9.GetHash().ToString());
     274           1 :     sortedOrder.insert(sortedOrder.begin()+6, tx8.GetHash().ToString());
     275           1 :     sortedOrder.insert(sortedOrder.begin()+7, tx10.GetHash().ToString()); // tx10 is just before tx6
     276           1 :     CheckSort<descendant_score>(pool, sortedOrder);
     277             : 
     278             :     // there should be 10 transactions in the mempool
     279           1 :     BOOST_CHECK_EQUAL(pool.size(), 10);
     280             : 
     281             :     // Now try removing tx10 and verify the sort order returns to normal
     282           2 :     pool.removeRecursive(pool.mapTx.find(tx10.GetHash())->GetTx());
     283           1 :     CheckSort<descendant_score>(pool, snapshotOrder);
     284             : 
     285           2 :     pool.removeRecursive(pool.mapTx.find(tx9.GetHash())->GetTx());
     286           2 :     pool.removeRecursive(pool.mapTx.find(tx8.GetHash())->GetTx());
     287             :     /* Now check the sort on the mining score index.
     288             :      * Final order should be:
     289             :      *
     290             :      * tx7 (2M)
     291             :      * tx2 (20k)
     292             :      * tx4 (15000)
     293             :      * tx1/tx5 (10000)
     294             :      * tx3/6 (0)
     295             :      * (Ties resolved by hash)
     296             :      */
     297           1 :     sortedOrder.clear();
     298           2 :     sortedOrder.push_back(tx7.GetHash().ToString());
     299           2 :     sortedOrder.push_back(tx2.GetHash().ToString());
     300           2 :     sortedOrder.push_back(tx4.GetHash().ToString());
     301           1 :     if (tx1.GetHash() < tx5.GetHash()) {
     302           0 :         sortedOrder.push_back(tx5.GetHash().ToString());
     303           0 :         sortedOrder.push_back(tx1.GetHash().ToString());
     304             :     } else {
     305           2 :         sortedOrder.push_back(tx1.GetHash().ToString());
     306           2 :         sortedOrder.push_back(tx5.GetHash().ToString());
     307             :     }
     308           1 :     if (tx3.GetHash() < tx6.GetHash()) {
     309           2 :         sortedOrder.push_back(tx6.GetHash().ToString());
     310           2 :         sortedOrder.push_back(tx3.GetHash().ToString());
     311             :     } else {
     312           0 :         sortedOrder.push_back(tx3.GetHash().ToString());
     313           0 :         sortedOrder.push_back(tx6.GetHash().ToString());
     314             :     }
     315           1 :     CheckSort<mining_score>(pool, sortedOrder);
     316           1 : }
     317             : 
     318           2 : BOOST_AUTO_TEST_CASE(MempoolAncestorIndexingTest)
     319             : {
     320           2 :     CTxMemPool pool(CFeeRate(0));
     321           1 :     TestMemPoolEntryHelper entry;
     322             : 
     323             :     /* 3rd highest fee */
     324           2 :     CMutableTransaction tx1 = CMutableTransaction();
     325           1 :     tx1.vout.resize(1);
     326           1 :     tx1.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
     327           1 :     tx1.vout[0].nValue = 10 * COIN;
     328           1 :     pool.addUnchecked(tx1.GetHash(), entry.Fee(10000LL).FromTx(tx1));
     329             : 
     330             :     /* highest fee */
     331           2 :     CMutableTransaction tx2 = CMutableTransaction();
     332           1 :     tx2.vout.resize(1);
     333           1 :     tx2.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
     334           1 :     tx2.vout[0].nValue = 2 * COIN;
     335           1 :     pool.addUnchecked(tx2.GetHash(), entry.Fee(20000LL).FromTx(tx2));
     336           1 :     uint64_t tx2Size = ::GetSerializeSize(tx2, PROTOCOL_VERSION);
     337             : 
     338             :     /* lowest fee */
     339           2 :     CMutableTransaction tx3 = CMutableTransaction();
     340           1 :     tx3.vout.resize(1);
     341           1 :     tx3.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
     342           1 :     tx3.vout[0].nValue = 5 * COIN;
     343           1 :     pool.addUnchecked(tx3.GetHash(), entry.Fee(0LL).FromTx(tx3));
     344             : 
     345             :     /* 2nd highest fee */
     346           2 :     CMutableTransaction tx4 = CMutableTransaction();
     347           1 :     tx4.vout.resize(1);
     348           1 :     tx4.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
     349           1 :     tx4.vout[0].nValue = 6 * COIN;
     350           1 :     pool.addUnchecked(tx4.GetHash(), entry.Fee(15000LL).FromTx(tx4));
     351             : 
     352             :     /* equal fee rate to tx1, but newer */
     353           2 :     CMutableTransaction tx5 = CMutableTransaction();
     354           1 :     tx5.vout.resize(1);
     355           1 :     tx5.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
     356           1 :     tx5.vout[0].nValue = 11 * COIN;
     357           1 :     pool.addUnchecked(tx5.GetHash(), entry.Fee(10000LL).FromTx(tx5));
     358           1 :     BOOST_CHECK_EQUAL(pool.size(), 5);
     359             : 
     360           2 :     std::vector<std::string> sortedOrder;
     361           1 :     sortedOrder.resize(5);
     362           1 :     sortedOrder[0] = tx2.GetHash().ToString(); // 20000
     363           1 :     sortedOrder[1] = tx4.GetHash().ToString(); // 15000
     364             :     // tx1 and tx5 are both 10000
     365             :     // Ties are broken by hash, not timestamp, so determine which
     366             :     // hash comes first.
     367           1 :     if (tx1.GetHash() < tx5.GetHash()) {
     368           0 :         sortedOrder[2] = tx1.GetHash().ToString();
     369           0 :         sortedOrder[3] = tx5.GetHash().ToString();
     370             :     } else {
     371           1 :         sortedOrder[2] = tx5.GetHash().ToString();
     372           1 :         sortedOrder[3] = tx1.GetHash().ToString();
     373             :     }
     374           1 :     sortedOrder[4] = tx3.GetHash().ToString(); // 0
     375             : 
     376           1 :     CheckSort<ancestor_score>(pool, sortedOrder);
     377             : 
     378             :     /* low fee parent with high fee child */
     379             :     /* tx6 (0) -> tx7 (high) */
     380           2 :     CMutableTransaction tx6 = CMutableTransaction();
     381           1 :     tx6.vout.resize(1);
     382           1 :     tx6.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
     383           1 :     tx6.vout[0].nValue = 20 * COIN;
     384           1 :     uint64_t tx6Size = ::GetSerializeSize(tx6, PROTOCOL_VERSION);
     385             : 
     386           1 :     pool.addUnchecked(tx6.GetHash(), entry.Fee(0LL).FromTx(tx6));
     387           1 :     BOOST_CHECK_EQUAL(pool.size(), 6);
     388             :     // Ties are broken by hash
     389           1 :     if (tx3.GetHash() < tx6.GetHash())
     390           2 :         sortedOrder.push_back(tx6.GetHash().ToString());
     391             :     else
     392           0 :         sortedOrder.insert(sortedOrder.end()-1,tx6.GetHash().ToString());
     393             : 
     394           1 :     CheckSort<ancestor_score>(pool, sortedOrder);
     395             : 
     396           2 :     CMutableTransaction tx7 = CMutableTransaction();
     397           1 :     tx7.vin.resize(1);
     398           1 :     tx7.vin[0].prevout = COutPoint(tx6.GetHash(), 0);
     399           1 :     tx7.vin[0].scriptSig = CScript() << OP_11;
     400           1 :     tx7.vout.resize(1);
     401           1 :     tx7.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
     402           1 :     tx7.vout[0].nValue = 10 * COIN;
     403           1 :     uint64_t tx7Size = ::GetSerializeSize(tx7, PROTOCOL_VERSION);
     404             : 
     405             :     /* set the fee to just below tx2's feerate when including ancestor */
     406           1 :     CAmount fee = (20000/tx2Size)*(tx7Size + tx6Size) - 1;
     407             : 
     408           1 :     pool.addUnchecked(tx7.GetHash(), entry.Fee(fee).FromTx(tx7));
     409           1 :     BOOST_CHECK_EQUAL(pool.size(), 7);
     410           1 :     sortedOrder.insert(sortedOrder.begin()+1, tx7.GetHash().ToString());
     411           1 :     CheckSort<ancestor_score>(pool, sortedOrder);
     412             : 
     413             :     /* after tx6 is mined, tx7 should move up in the sort */
     414           2 :     std::vector<CTransactionRef> vtx;
     415           1 :     vtx.emplace_back(MakeTransactionRef(tx6));
     416           1 :     pool.removeForBlock(vtx, 1);
     417             : 
     418           1 :     sortedOrder.erase(sortedOrder.begin()+1);
     419             :     // Ties are broken by hash
     420           1 :     if (tx3.GetHash() < tx6.GetHash())
     421           1 :         sortedOrder.pop_back();
     422             :     else
     423           0 :         sortedOrder.erase(sortedOrder.end()-2);
     424           1 :     sortedOrder.insert(sortedOrder.begin(), tx7.GetHash().ToString());
     425           1 :     CheckSort<ancestor_score>(pool, sortedOrder);
     426           1 : }
     427             : 
     428             : 
     429           2 : BOOST_AUTO_TEST_CASE(MempoolSizeLimitTest)
     430             : {
     431           2 :     CTxMemPool pool(CFeeRate(1000));
     432           1 :     TestMemPoolEntryHelper entry;
     433             : 
     434           2 :     CMutableTransaction tx1 = CMutableTransaction();
     435           1 :     tx1.vin.resize(1);
     436           1 :     tx1.vin[0].scriptSig = CScript() << OP_1;
     437           1 :     tx1.vout.resize(1);
     438           1 :     tx1.vout[0].scriptPubKey = CScript() << OP_1 << OP_EQUAL;
     439           1 :     tx1.vout[0].nValue = 10 * COIN;
     440           1 :     pool.addUnchecked(tx1.GetHash(), entry.Fee(10000LL).FromTx(tx1));
     441             : 
     442           2 :     CMutableTransaction tx2 = CMutableTransaction();
     443           1 :     tx2.vin.resize(1);
     444           1 :     tx2.vin[0].scriptSig = CScript() << OP_2;
     445           1 :     tx2.vout.resize(1);
     446           1 :     tx2.vout[0].scriptPubKey = CScript() << OP_2 << OP_EQUAL;
     447           1 :     tx2.vout[0].nValue = 10 * COIN;
     448           1 :     pool.addUnchecked(tx2.GetHash(), entry.Fee(5000LL).FromTx(tx2));
     449             : 
     450           1 :     pool.TrimToSize(pool.DynamicMemoryUsage()); // should do nothing
     451           2 :     BOOST_CHECK(pool.exists(tx1.GetHash()));
     452           2 :     BOOST_CHECK(pool.exists(tx2.GetHash()));
     453             : 
     454           1 :     pool.TrimToSize(pool.DynamicMemoryUsage() * 3 / 4); // should remove the lower-feerate transaction
     455           2 :     BOOST_CHECK(pool.exists(tx1.GetHash()));
     456           2 :     BOOST_CHECK(!pool.exists(tx2.GetHash()));
     457             : 
     458           1 :     pool.addUnchecked(tx2.GetHash(), entry.FromTx(tx2));
     459           2 :     CMutableTransaction tx3 = CMutableTransaction();
     460           1 :     tx3.vin.resize(1);
     461           1 :     tx3.vin[0].prevout = COutPoint(tx2.GetHash(), 0);
     462           1 :     tx3.vin[0].scriptSig = CScript() << OP_2;
     463           1 :     tx3.vout.resize(1);
     464           1 :     tx3.vout[0].scriptPubKey = CScript() << OP_3 << OP_EQUAL;
     465           1 :     tx3.vout[0].nValue = 10 * COIN;
     466           1 :     pool.addUnchecked(tx3.GetHash(), entry.Fee(20000LL).FromTx(tx3));
     467             : 
     468           1 :     pool.TrimToSize(pool.DynamicMemoryUsage() * 3 / 4); // tx3 should pay for tx2 (CPFP)
     469           2 :     BOOST_CHECK(!pool.exists(tx1.GetHash()));
     470           2 :     BOOST_CHECK(pool.exists(tx2.GetHash()));
     471           2 :     BOOST_CHECK(pool.exists(tx3.GetHash()));
     472             : 
     473           1 :     pool.TrimToSize(::GetSerializeSize(CTransaction(tx1), PROTOCOL_VERSION)); // mempool is limited to tx1's size in memory usage, so nothing fits
     474           2 :     BOOST_CHECK(!pool.exists(tx1.GetHash()));
     475           2 :     BOOST_CHECK(!pool.exists(tx2.GetHash()));
     476           2 :     BOOST_CHECK(!pool.exists(tx3.GetHash()));
     477             : 
     478           1 :     CFeeRate maxFeeRateRemoved(25000, ::GetSerializeSize(CTransaction(tx3), PROTOCOL_VERSION) + ::GetSerializeSize(CTransaction(tx2), PROTOCOL_VERSION));
     479           2 :     BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), maxFeeRateRemoved.GetFeePerK() + 1000);
     480             : 
     481           2 :     CMutableTransaction tx4 = CMutableTransaction();
     482           1 :     tx4.vin.resize(2);
     483           1 :     tx4.vin[0].prevout.SetNull();
     484           1 :     tx4.vin[0].scriptSig = CScript() << OP_4;
     485           1 :     tx4.vin[1].prevout.SetNull();
     486           1 :     tx4.vin[1].scriptSig = CScript() << OP_4;
     487           1 :     tx4.vout.resize(2);
     488           1 :     tx4.vout[0].scriptPubKey = CScript() << OP_4 << OP_EQUAL;
     489           1 :     tx4.vout[0].nValue = 10 * COIN;
     490           1 :     tx4.vout[1].scriptPubKey = CScript() << OP_4 << OP_EQUAL;
     491           1 :     tx4.vout[1].nValue = 10 * COIN;
     492             : 
     493           2 :     CMutableTransaction tx5 = CMutableTransaction();
     494           1 :     tx5.vin.resize(2);
     495           1 :     tx5.vin[0].prevout = COutPoint(tx4.GetHash(), 0);
     496           1 :     tx5.vin[0].scriptSig = CScript() << OP_4;
     497           1 :     tx5.vin[1].prevout.SetNull();
     498           1 :     tx5.vin[1].scriptSig = CScript() << OP_5;
     499           1 :     tx5.vout.resize(2);
     500           1 :     tx5.vout[0].scriptPubKey = CScript() << OP_5 << OP_EQUAL;
     501           1 :     tx5.vout[0].nValue = 10 * COIN;
     502           1 :     tx5.vout[1].scriptPubKey = CScript() << OP_5 << OP_EQUAL;
     503           1 :     tx5.vout[1].nValue = 10 * COIN;
     504             : 
     505           2 :     CMutableTransaction tx6 = CMutableTransaction();
     506           1 :     tx6.vin.resize(2);
     507           1 :     tx6.vin[0].prevout = COutPoint(tx4.GetHash(), 1);
     508           1 :     tx6.vin[0].scriptSig = CScript() << OP_4;
     509           1 :     tx6.vin[1].prevout.SetNull();
     510           1 :     tx6.vin[1].scriptSig = CScript() << OP_6;
     511           1 :     tx6.vout.resize(2);
     512           1 :     tx6.vout[0].scriptPubKey = CScript() << OP_6 << OP_EQUAL;
     513           1 :     tx6.vout[0].nValue = 10 * COIN;
     514           1 :     tx6.vout[1].scriptPubKey = CScript() << OP_6 << OP_EQUAL;
     515           1 :     tx6.vout[1].nValue = 10 * COIN;
     516             : 
     517           2 :     CMutableTransaction tx7 = CMutableTransaction();
     518           1 :     tx7.vin.resize(2);
     519           1 :     tx7.vin[0].prevout = COutPoint(tx5.GetHash(), 0);
     520           1 :     tx7.vin[0].scriptSig = CScript() << OP_5;
     521           1 :     tx7.vin[1].prevout = COutPoint(tx6.GetHash(), 0);
     522           1 :     tx7.vin[1].scriptSig = CScript() << OP_6;
     523           1 :     tx7.vout.resize(2);
     524           1 :     tx7.vout[0].scriptPubKey = CScript() << OP_7 << OP_EQUAL;
     525           1 :     tx7.vout[0].nValue = 10 * COIN;
     526           1 :     tx7.vout[1].scriptPubKey = CScript() << OP_7 << OP_EQUAL;
     527           1 :     tx7.vout[1].nValue = 10 * COIN;
     528             : 
     529           1 :     pool.addUnchecked(tx4.GetHash(), entry.Fee(7000LL).FromTx(tx4));
     530           1 :     pool.addUnchecked(tx5.GetHash(), entry.Fee(1000LL).FromTx(tx5));
     531           1 :     pool.addUnchecked(tx6.GetHash(), entry.Fee(1100LL).FromTx(tx6));
     532           1 :     pool.addUnchecked(tx7.GetHash(), entry.Fee(9000LL).FromTx(tx7));
     533             : 
     534             :     // we only require this remove, at max, 2 txn, because its not clear what we're really optimizing for aside from that
     535           1 :     pool.TrimToSize(pool.DynamicMemoryUsage() - 1);
     536           2 :     BOOST_CHECK(pool.exists(tx4.GetHash()));
     537           2 :     BOOST_CHECK(pool.exists(tx6.GetHash()));
     538           2 :     BOOST_CHECK(!pool.exists(tx7.GetHash()));
     539             : 
     540           1 :     if (!pool.exists(tx5.GetHash()))
     541           2 :         pool.addUnchecked(tx5.GetHash(), entry.Fee(1000LL).FromTx(tx5));
     542           1 :     pool.addUnchecked(tx7.GetHash(), entry.Fee(9000LL).FromTx(tx7));
     543             : 
     544           1 :     pool.TrimToSize(pool.DynamicMemoryUsage() / 2); // should maximize mempool size by only removing 5/7
     545           2 :     BOOST_CHECK(pool.exists(tx4.GetHash()));
     546           2 :     BOOST_CHECK(!pool.exists(tx5.GetHash()));
     547           2 :     BOOST_CHECK(pool.exists(tx6.GetHash()));
     548           2 :     BOOST_CHECK(!pool.exists(tx7.GetHash()));
     549             : 
     550           1 :     pool.addUnchecked(tx5.GetHash(), entry.Fee(1000LL).FromTx(tx5));
     551           1 :     pool.addUnchecked(tx7.GetHash(), entry.Fee(9000LL).FromTx(tx7));
     552             : 
     553           2 :     std::vector<CTransactionRef> vtx;
     554           1 :     SetMockTime(42);
     555           1 :     SetMockTime(42 + CTxMemPool::ROLLING_FEE_HALFLIFE);
     556           2 :     BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), maxFeeRateRemoved.GetFeePerK() + 1000);
     557             :     // ... we should keep the same min fee until we get a block
     558           1 :     pool.removeForBlock(vtx, 1);
     559           1 :     SetMockTime(42 + 2*CTxMemPool::ROLLING_FEE_HALFLIFE);
     560           2 :     BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), (maxFeeRateRemoved.GetFeePerK() + 1000)/2);
     561             :     // ... then feerate should drop 1/2 each halflife
     562             : 
     563           1 :     SetMockTime(42 + 2*CTxMemPool::ROLLING_FEE_HALFLIFE + CTxMemPool::ROLLING_FEE_HALFLIFE/2);
     564           2 :     BOOST_CHECK_EQUAL(pool.GetMinFee(pool.DynamicMemoryUsage() * 5 / 2).GetFeePerK(), (maxFeeRateRemoved.GetFeePerK() + 1000)/4);
     565             :     // ... with a 1/2 halflife when mempool is < 1/2 its target size
     566             : 
     567           1 :     SetMockTime(42 + 2*CTxMemPool::ROLLING_FEE_HALFLIFE + CTxMemPool::ROLLING_FEE_HALFLIFE/2 + CTxMemPool::ROLLING_FEE_HALFLIFE/4);
     568           2 :     BOOST_CHECK_EQUAL(pool.GetMinFee(pool.DynamicMemoryUsage() * 9 / 2).GetFeePerK(), (maxFeeRateRemoved.GetFeePerK() + 1000)/8);
     569             :     // ... with a 1/4 halflife when mempool is < 1/4 its target size
     570             : 
     571           1 :     SetMockTime(42 + 7*CTxMemPool::ROLLING_FEE_HALFLIFE + CTxMemPool::ROLLING_FEE_HALFLIFE/2 + CTxMemPool::ROLLING_FEE_HALFLIFE/4);
     572           2 :     BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), 1000);
     573             :     // ... but feerate should never drop below 1000
     574             : 
     575           1 :     SetMockTime(42 + 8*CTxMemPool::ROLLING_FEE_HALFLIFE + CTxMemPool::ROLLING_FEE_HALFLIFE/2 + CTxMemPool::ROLLING_FEE_HALFLIFE/4);
     576           2 :     BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), 0);
     577             :     // ... unless it has gone all the way to 0 (after getting past 1000/2)
     578             : 
     579           1 :     SetMockTime(0);
     580           1 : }
     581             : 
     582             : BOOST_AUTO_TEST_SUITE_END()

Generated by: LCOV version 1.14