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()
|