src/test/mempool_tests.cpp

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