Branch data Line data Source code
1 : : // Copyright (c) 2011-present 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 <common/system.h>
6 : : #include <policy/policy.h>
7 : : #include <test/util/time.h>
8 : : #include <test/util/txmempool.h>
9 : : #include <txmempool.h>
10 : : #include <util/time.h>
11 : :
12 : : #include <test/util/setup_common.h>
13 : :
14 : : #include <boost/test/unit_test.hpp>
15 : : #include <vector>
16 : :
17 : : BOOST_FIXTURE_TEST_SUITE(mempool_tests, TestingSetup)
18 : :
19 : : static constexpr auto REMOVAL_REASON_DUMMY = MemPoolRemovalReason::REPLACED;
20 : :
21 : : class MemPoolTest final : public CTxMemPool
22 : : {
23 : : public:
24 : : using CTxMemPool::GetMinFee;
25 : : };
26 : :
27 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(MempoolLookupTest)
+ - + - -
+ + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- ]
28 : : {
29 [ - + ]: 1 : auto& pool = static_cast<MemPoolTest&>(*Assert(m_node.mempool));
30 [ + - ]: 1 : LOCK2(cs_main, pool.cs);
31 : 1 : TestMemPoolEntryHelper entry;
32 : :
33 [ + - ]: 1 : CMutableTransaction tx = CMutableTransaction();
34 [ + - ]: 1 : tx.vin.resize(1);
35 [ + - ]: 1 : tx.vin[0].scriptSig = CScript() << OP_1;
36 [ + - ]: 1 : tx.vout.resize(1);
37 [ + - + - ]: 1 : tx.vout[0].scriptPubKey = CScript() << OP_1 << OP_EQUAL;
38 [ + - ]: 1 : tx.vout[0].nValue = 10 * COIN;
39 : :
40 : : // Not in the mempool, so can't find it by txid or wtxid
41 [ + - + - : 2 : BOOST_CHECK(!pool.get(tx.GetHash()));
+ - + - -
+ + - ]
42 [ + - + - : 3 : BOOST_CHECK(!pool.get(CTransaction(tx).GetWitnessHash()));
+ - + - -
+ + - ]
43 : :
44 [ + - + - ]: 1 : TryAddToMempool(pool, entry.Fee(1000LL).FromTx(tx));
45 : :
46 : : // Lookup by Txid
47 [ + - + - : 3 : BOOST_CHECK(pool.get(tx.GetHash()));
+ - + - +
- + - ]
48 : :
49 : : // Lookup by Wtxid
50 [ + - + - : 4 : BOOST_CHECK(pool.get(CTransaction(tx).GetWitnessHash()));
+ - + - +
- ]
51 [ + - + - ]: 3 : }
52 : :
53 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(MempoolRemoveTest)
+ - + - -
+ + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- ]
54 : : {
55 : : // Test CTxMemPool::remove functionality
56 : :
57 : 1 : TestMemPoolEntryHelper entry;
58 : : // Parent transaction with three children,
59 : : // and three grand-children:
60 : 1 : CMutableTransaction txParent;
61 [ + - ]: 1 : txParent.vin.resize(1);
62 [ + - ]: 1 : txParent.vin[0].scriptSig = CScript() << OP_11;
63 [ + - ]: 1 : txParent.vout.resize(3);
64 [ + + ]: 4 : for (int i = 0; i < 3; i++)
65 : : {
66 [ + - + - ]: 3 : txParent.vout[i].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
67 : 3 : txParent.vout[i].nValue = 33000LL;
68 : : }
69 [ + - + + : 10 : CMutableTransaction txChild[3];
- - ]
70 [ + + ]: 4 : for (int i = 0; i < 3; i++)
71 : : {
72 [ + - ]: 3 : txChild[i].vin.resize(1);
73 [ + - ]: 3 : txChild[i].vin[0].scriptSig = CScript() << OP_11;
74 [ + - + - ]: 3 : txChild[i].vin[0].prevout.hash = txParent.GetHash();
75 : 3 : txChild[i].vin[0].prevout.n = i;
76 [ + - ]: 3 : txChild[i].vout.resize(1);
77 [ + - + - ]: 3 : txChild[i].vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
78 : 3 : txChild[i].vout[0].nValue = 11000LL;
79 : : }
80 [ + - + + : 11 : CMutableTransaction txGrandChild[3];
- - ]
81 [ + + ]: 4 : for (int i = 0; i < 3; i++)
82 : : {
83 [ + - ]: 3 : txGrandChild[i].vin.resize(1);
84 [ + - ]: 3 : txGrandChild[i].vin[0].scriptSig = CScript() << OP_11;
85 [ + - + - ]: 3 : txGrandChild[i].vin[0].prevout.hash = txChild[i].GetHash();
86 : 3 : txGrandChild[i].vin[0].prevout.n = 0;
87 [ + - ]: 3 : txGrandChild[i].vout.resize(1);
88 [ + - + - ]: 3 : txGrandChild[i].vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
89 : 3 : txGrandChild[i].vout[0].nValue = 11000LL;
90 : : }
91 : :
92 : :
93 [ - + + - ]: 1 : CTxMemPool& testPool = *Assert(m_node.mempool);
94 [ + - + - ]: 1 : LOCK2(::cs_main, testPool.cs);
95 : :
96 : : // Nothing in pool, remove should do nothing:
97 [ + - ]: 1 : unsigned int poolSize = testPool.size();
98 [ + - + - ]: 1 : testPool.removeRecursive(CTransaction(txParent), REMOVAL_REASON_DUMMY);
99 [ + - + - : 1 : BOOST_CHECK_EQUAL(testPool.size(), poolSize);
+ - ]
100 : :
101 : : // Just the parent:
102 [ + - + - ]: 1 : TryAddToMempool(testPool, entry.FromTx(txParent));
103 [ + - ]: 1 : poolSize = testPool.size();
104 [ + - + - ]: 1 : testPool.removeRecursive(CTransaction(txParent), REMOVAL_REASON_DUMMY);
105 [ + - + - : 1 : BOOST_CHECK_EQUAL(testPool.size(), poolSize - 1);
+ - ]
106 : :
107 : : // Parent, children, grandchildren:
108 [ + - + - ]: 1 : TryAddToMempool(testPool, entry.FromTx(txParent));
109 [ + + ]: 4 : for (int i = 0; i < 3; i++)
110 : : {
111 [ + - + - ]: 3 : TryAddToMempool(testPool, entry.FromTx(txChild[i]));
112 [ + - + - ]: 3 : TryAddToMempool(testPool, entry.FromTx(txGrandChild[i]));
113 : : }
114 : : // Remove Child[0], GrandChild[0] should be removed:
115 [ + - ]: 1 : poolSize = testPool.size();
116 [ + - + - ]: 1 : testPool.removeRecursive(CTransaction(txChild[0]), REMOVAL_REASON_DUMMY);
117 [ + - + - : 1 : BOOST_CHECK_EQUAL(testPool.size(), poolSize - 2);
+ - ]
118 : : // ... make sure grandchild and child are gone:
119 [ + - ]: 1 : poolSize = testPool.size();
120 [ + - + - ]: 1 : testPool.removeRecursive(CTransaction(txGrandChild[0]), REMOVAL_REASON_DUMMY);
121 [ + - + - : 1 : BOOST_CHECK_EQUAL(testPool.size(), poolSize);
+ - ]
122 [ + - ]: 1 : poolSize = testPool.size();
123 [ + - + - ]: 1 : testPool.removeRecursive(CTransaction(txChild[0]), REMOVAL_REASON_DUMMY);
124 [ + - + - : 1 : BOOST_CHECK_EQUAL(testPool.size(), poolSize);
+ - ]
125 : : // Remove parent, all children/grandchildren should go:
126 [ + - ]: 1 : poolSize = testPool.size();
127 [ + - + - ]: 1 : testPool.removeRecursive(CTransaction(txParent), REMOVAL_REASON_DUMMY);
128 [ + - + - : 1 : BOOST_CHECK_EQUAL(testPool.size(), poolSize - 5);
+ - ]
129 [ + - + - : 1 : BOOST_CHECK_EQUAL(testPool.size(), 0U);
+ - ]
130 : :
131 : : // Add children and grandchildren, but NOT the parent (simulate the parent being in a block)
132 [ + + ]: 4 : for (int i = 0; i < 3; i++)
133 : : {
134 [ + - + - ]: 3 : TryAddToMempool(testPool, entry.FromTx(txChild[i]));
135 [ + - + - ]: 3 : TryAddToMempool(testPool, entry.FromTx(txGrandChild[i]));
136 : : }
137 : : // Now remove the parent, as might happen if a block-re-org occurs but the parent cannot be
138 : : // put into the mempool (maybe because it is non-standard):
139 [ + - ]: 1 : poolSize = testPool.size();
140 [ + - + - ]: 1 : testPool.removeRecursive(CTransaction(txParent), REMOVAL_REASON_DUMMY);
141 [ + - + - : 1 : BOOST_CHECK_EQUAL(testPool.size(), poolSize - 6);
+ - ]
142 [ + - + - : 1 : BOOST_CHECK_EQUAL(testPool.size(), 0U);
+ - + - ]
143 [ + - + + : 10 : }
+ + - - -
- ]
144 : :
145 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(MempoolSizeLimitTest)
+ - + - -
+ + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- ]
146 : : {
147 [ - + ]: 1 : auto& pool = static_cast<MemPoolTest&>(*Assert(m_node.mempool));
148 [ + - ]: 1 : LOCK2(cs_main, pool.cs);
149 : 1 : TestMemPoolEntryHelper entry;
150 : :
151 [ + - ]: 1 : CMutableTransaction tx1 = CMutableTransaction();
152 [ + - ]: 1 : tx1.vin.resize(1);
153 [ + - ]: 1 : tx1.vin[0].scriptSig = CScript() << OP_1;
154 [ + - ]: 1 : tx1.vout.resize(1);
155 [ + - + - ]: 1 : tx1.vout[0].scriptPubKey = CScript() << OP_1 << OP_EQUAL;
156 [ + - ]: 1 : tx1.vout[0].nValue = 10 * COIN;
157 [ + - + - ]: 1 : TryAddToMempool(pool, entry.Fee(1000LL).FromTx(tx1));
158 : :
159 [ + - ]: 1 : CMutableTransaction tx2 = CMutableTransaction();
160 [ + - ]: 1 : tx2.vin.resize(1);
161 [ + - ]: 1 : tx2.vin[0].scriptSig = CScript() << OP_2;
162 [ + - ]: 1 : tx2.vout.resize(1);
163 [ + - + - ]: 1 : tx2.vout[0].scriptPubKey = CScript() << OP_2 << OP_EQUAL;
164 [ + - ]: 1 : tx2.vout[0].nValue = 10 * COIN;
165 [ + - + - ]: 1 : TryAddToMempool(pool, entry.Fee(500LL).FromTx(tx2));
166 : :
167 [ + - + - ]: 1 : pool.TrimToSize(pool.DynamicMemoryUsage()); // should do nothing
168 [ + - + - : 2 : BOOST_CHECK(pool.exists(tx1.GetHash()));
+ - + - +
- ]
169 [ + - + - : 2 : BOOST_CHECK(pool.exists(tx2.GetHash()));
+ - + - +
- ]
170 : :
171 [ + - + - ]: 1 : pool.TrimToSize(pool.DynamicMemoryUsage() * 3 / 4); // should remove the lower-feerate transaction
172 [ + - + - : 2 : BOOST_CHECK(pool.exists(tx1.GetHash()));
+ - + - +
- ]
173 [ + - + - : 2 : BOOST_CHECK(!pool.exists(tx2.GetHash()));
+ - + - +
- ]
174 : :
175 [ + - + - ]: 1 : TryAddToMempool(pool, entry.FromTx(tx2));
176 [ + - ]: 1 : CMutableTransaction tx3 = CMutableTransaction();
177 [ + - ]: 1 : tx3.vin.resize(1);
178 [ + - + - ]: 1 : tx3.vin[0].prevout = COutPoint(tx2.GetHash(), 0);
179 [ + - ]: 1 : tx3.vin[0].scriptSig = CScript() << OP_2;
180 [ + - ]: 1 : tx3.vout.resize(1);
181 [ + - + - ]: 1 : tx3.vout[0].scriptPubKey = CScript() << OP_3 << OP_EQUAL;
182 [ + - ]: 1 : tx3.vout[0].nValue = 10 * COIN;
183 [ + - + - ]: 1 : TryAddToMempool(pool, entry.Fee(2000LL).FromTx(tx3));
184 : :
185 [ + - + - ]: 1 : pool.TrimToSize(pool.DynamicMemoryUsage() * 3 / 4); // tx3 should pay for tx2 (CPFP)
186 [ + - + - : 2 : BOOST_CHECK(!pool.exists(tx1.GetHash()));
+ - + - +
- ]
187 [ + - + - : 2 : BOOST_CHECK(pool.exists(tx2.GetHash()));
+ - + - +
- ]
188 [ + - + - : 2 : BOOST_CHECK(pool.exists(tx3.GetHash()));
+ - + - +
- ]
189 : :
190 [ + - + - ]: 2 : pool.TrimToSize(GetVirtualTransactionSize(CTransaction(tx1))); // mempool is limited to tx1's size in memory usage, so nothing fits
191 [ + - + - : 2 : BOOST_CHECK(!pool.exists(tx1.GetHash()));
+ - + - +
- ]
192 [ + - + - : 2 : BOOST_CHECK(!pool.exists(tx2.GetHash()));
+ - + - +
- ]
193 [ + - + - : 2 : BOOST_CHECK(!pool.exists(tx3.GetHash()));
+ - + - +
- ]
194 : :
195 [ + - + - : 4 : CFeeRate maxFeeRateRemoved(2500, GetVirtualTransactionSize(CTransaction(tx3)) + GetVirtualTransactionSize(CTransaction(tx2)));
+ - ]
196 [ + - + - : 1 : BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), maxFeeRateRemoved.GetFeePerK() + DEFAULT_INCREMENTAL_RELAY_FEE);
+ - ]
197 : :
198 [ + - ]: 1 : CMutableTransaction tx4 = CMutableTransaction();
199 [ + - ]: 1 : tx4.vin.resize(2);
200 : 1 : tx4.vin[0].prevout.SetNull();
201 [ + - ]: 1 : tx4.vin[0].scriptSig = CScript() << OP_4;
202 : 1 : tx4.vin[1].prevout.SetNull();
203 [ + - ]: 1 : tx4.vin[1].scriptSig = CScript() << OP_4;
204 [ + - ]: 1 : tx4.vout.resize(2);
205 [ + - + - ]: 1 : tx4.vout[0].scriptPubKey = CScript() << OP_4 << OP_EQUAL;
206 [ + - ]: 1 : tx4.vout[0].nValue = 10 * COIN;
207 [ + - + - ]: 1 : tx4.vout[1].scriptPubKey = CScript() << OP_4 << OP_EQUAL;
208 [ + - ]: 1 : tx4.vout[1].nValue = 10 * COIN;
209 : :
210 [ + - ]: 1 : CMutableTransaction tx5 = CMutableTransaction();
211 [ + - ]: 1 : tx5.vin.resize(2);
212 [ + - + - ]: 1 : tx5.vin[0].prevout = COutPoint(tx4.GetHash(), 0);
213 [ + - ]: 1 : tx5.vin[0].scriptSig = CScript() << OP_4;
214 : 1 : tx5.vin[1].prevout.SetNull();
215 [ + - ]: 1 : tx5.vin[1].scriptSig = CScript() << OP_5;
216 [ + - ]: 1 : tx5.vout.resize(2);
217 [ + - + - ]: 1 : tx5.vout[0].scriptPubKey = CScript() << OP_5 << OP_EQUAL;
218 [ + - ]: 1 : tx5.vout[0].nValue = 10 * COIN;
219 [ + - + - ]: 1 : tx5.vout[1].scriptPubKey = CScript() << OP_5 << OP_EQUAL;
220 [ + - ]: 1 : tx5.vout[1].nValue = 10 * COIN;
221 : :
222 [ + - ]: 1 : CMutableTransaction tx6 = CMutableTransaction();
223 [ + - ]: 1 : tx6.vin.resize(2);
224 [ + - + - ]: 1 : tx6.vin[0].prevout = COutPoint(tx4.GetHash(), 1);
225 [ + - ]: 1 : tx6.vin[0].scriptSig = CScript() << OP_4;
226 : 1 : tx6.vin[1].prevout.SetNull();
227 [ + - ]: 1 : tx6.vin[1].scriptSig = CScript() << OP_6;
228 [ + - ]: 1 : tx6.vout.resize(2);
229 [ + - + - ]: 1 : tx6.vout[0].scriptPubKey = CScript() << OP_6 << OP_EQUAL;
230 [ + - ]: 1 : tx6.vout[0].nValue = 10 * COIN;
231 [ + - + - ]: 1 : tx6.vout[1].scriptPubKey = CScript() << OP_6 << OP_EQUAL;
232 [ + - ]: 1 : tx6.vout[1].nValue = 10 * COIN;
233 : :
234 [ + - ]: 1 : CMutableTransaction tx7 = CMutableTransaction();
235 [ + - ]: 1 : tx7.vin.resize(2);
236 [ + - + - ]: 1 : tx7.vin[0].prevout = COutPoint(tx5.GetHash(), 0);
237 [ + - ]: 1 : tx7.vin[0].scriptSig = CScript() << OP_5;
238 [ + - + - ]: 1 : tx7.vin[1].prevout = COutPoint(tx6.GetHash(), 0);
239 [ + - ]: 1 : tx7.vin[1].scriptSig = CScript() << OP_6;
240 [ + - ]: 1 : tx7.vout.resize(2);
241 [ + - + - ]: 1 : tx7.vout[0].scriptPubKey = CScript() << OP_7 << OP_EQUAL;
242 [ + - ]: 1 : tx7.vout[0].nValue = 10 * COIN;
243 [ + - + - ]: 1 : tx7.vout[1].scriptPubKey = CScript() << OP_7 << OP_EQUAL;
244 [ + - ]: 1 : tx7.vout[1].nValue = 10 * COIN;
245 : :
246 [ + - + - ]: 1 : TryAddToMempool(pool, entry.Fee(700LL).FromTx(tx4));
247 [ + - ]: 1 : auto usage_with_tx4_only = pool.DynamicMemoryUsage();
248 [ + - + - ]: 1 : TryAddToMempool(pool, entry.Fee(100LL).FromTx(tx5));
249 [ + - + - ]: 1 : TryAddToMempool(pool, entry.Fee(110LL).FromTx(tx6));
250 [ + - + - ]: 1 : TryAddToMempool(pool, entry.Fee(900LL).FromTx(tx7));
251 : :
252 : : // From the topology above, tx7 must be sorted last, so it should
253 : : // definitely evicted first if we must trim. tx4 should definitely remain
254 : : // in the mempool since it has a higher feerate than its descendants and
255 : : // should be in its own chunk.
256 [ + - + - ]: 1 : pool.TrimToSize(pool.DynamicMemoryUsage() - 1);
257 [ + - + - : 2 : BOOST_CHECK(pool.exists(tx4.GetHash()));
+ - + - +
- ]
258 [ + - + - : 2 : BOOST_CHECK(!pool.exists(tx7.GetHash()));
+ - + - +
- ]
259 : :
260 : : // Tx5 and Tx6 may be removed as well because they're in the same chunk as
261 : : // tx7, but this behavior need not be guaranteed.
262 : :
263 [ + - + - : 1 : if (!pool.exists(tx5.GetHash()))
+ - ]
264 [ + - + - ]: 1 : TryAddToMempool(pool, entry.Fee(100LL).FromTx(tx5));
265 [ + - + - : 1 : if (!pool.exists(tx6.GetHash()))
+ - ]
266 [ + - + - ]: 1 : TryAddToMempool(pool, entry.Fee(110LL).FromTx(tx6));
267 [ + - + - ]: 1 : TryAddToMempool(pool, entry.Fee(900LL).FromTx(tx7));
268 : :
269 : : // If we trim sufficiently, everything but tx4 should be removed.
270 [ + - ]: 1 : pool.TrimToSize(usage_with_tx4_only + 1);
271 [ + - + - : 2 : BOOST_CHECK(pool.exists(tx4.GetHash()));
+ - + - +
- ]
272 [ + - + - : 2 : BOOST_CHECK(!pool.exists(tx5.GetHash()));
+ - + - +
- ]
273 [ + - + - : 2 : BOOST_CHECK(!pool.exists(tx6.GetHash()));
+ - + - +
- ]
274 [ + - + - : 2 : BOOST_CHECK(!pool.exists(tx7.GetHash()));
+ - + - +
- ]
275 : :
276 [ + - + - ]: 1 : TryAddToMempool(pool, entry.Fee(100LL).FromTx(tx5));
277 [ + - + - ]: 1 : TryAddToMempool(pool, entry.Fee(110LL).FromTx(tx6));
278 [ + - + - ]: 1 : TryAddToMempool(pool, entry.Fee(900LL).FromTx(tx7));
279 : :
280 : 1 : std::vector<CTransactionRef> vtx;
281 [ + - ]: 1 : FakeNodeClock clock{42s};
282 : 1 : constexpr std::chrono::seconds HALFLIFE{CTxMemPool::ROLLING_FEE_HALFLIFE};
283 [ + - ]: 1 : clock += HALFLIFE;
284 [ + - + - : 1 : BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), maxFeeRateRemoved.GetFeePerK() + DEFAULT_INCREMENTAL_RELAY_FEE);
+ - ]
285 : : // ... we should keep the same min fee until we get a block
286 [ + - ]: 1 : pool.removeForBlock(vtx, 1);
287 [ + - ]: 1 : clock += HALFLIFE;
288 [ + - + - : 1 : BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), llround((maxFeeRateRemoved.GetFeePerK() + DEFAULT_INCREMENTAL_RELAY_FEE)/2.0));
+ - ]
289 : : // ... then feerate should drop 1/2 each halflife
290 : :
291 [ + - ]: 1 : clock += HALFLIFE / 2;
292 [ + - + - : 1 : BOOST_CHECK_EQUAL(pool.GetMinFee(pool.DynamicMemoryUsage() * 5 / 2).GetFeePerK(), llround((maxFeeRateRemoved.GetFeePerK() + DEFAULT_INCREMENTAL_RELAY_FEE)/4.0));
+ - + - ]
293 : : // ... with a 1/2 halflife when mempool is < 1/2 its target size
294 : :
295 [ + - ]: 1 : clock += HALFLIFE / 4;
296 [ + - + - : 1 : BOOST_CHECK_EQUAL(pool.GetMinFee(pool.DynamicMemoryUsage() * 9 / 2).GetFeePerK(), llround((maxFeeRateRemoved.GetFeePerK() + DEFAULT_INCREMENTAL_RELAY_FEE)/8.0));
+ - + - ]
297 : : // ... with a 1/4 halflife when mempool is < 1/4 its target size
298 : :
299 [ + - ]: 1 : clock += 5 * HALFLIFE;
300 [ + - + - : 1 : BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), DEFAULT_INCREMENTAL_RELAY_FEE);
+ - ]
301 : : // ... but feerate should never drop below DEFAULT_INCREMENTAL_RELAY_FEE
302 : :
303 [ + - ]: 1 : clock += HALFLIFE;
304 [ + - + - : 1 : BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), 0);
+ - ]
305 : : // ... unless it has gone all the way to 0 (after getting past DEFAULT_INCREMENTAL_RELAY_FEE/2)
306 [ + - + - ]: 10 : }
307 : :
308 : 14 : inline CTransactionRef make_tx(std::vector<CAmount>&& output_values, std::vector<CTransactionRef>&& inputs=std::vector<CTransactionRef>(), std::vector<uint32_t>&& input_indices=std::vector<uint32_t>())
309 : : {
310 : 14 : CMutableTransaction tx = CMutableTransaction();
311 [ - + + - ]: 14 : tx.vin.resize(inputs.size());
312 [ - + + - ]: 14 : tx.vout.resize(output_values.size());
313 [ - + + + ]: 27 : for (size_t i = 0; i < inputs.size(); ++i) {
314 [ - + ]: 13 : tx.vin[i].prevout.hash = inputs[i]->GetHash();
315 [ - + + + ]: 13 : tx.vin[i].prevout.n = input_indices.size() > i ? input_indices[i] : 0;
316 : : }
317 [ - + + + ]: 32 : for (size_t i = 0; i < output_values.size(); ++i) {
318 [ + - + - ]: 18 : tx.vout[i].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
319 : 18 : tx.vout[i].nValue = output_values[i];
320 : : }
321 [ + - ]: 28 : return MakeTransactionRef(tx);
322 : 14 : }
323 : :
324 : :
325 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(MempoolAncestryTests)
+ - + - -
+ + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- ]
326 : : {
327 : 1 : size_t ancestors, clustersize;
328 : :
329 [ - + ]: 1 : CTxMemPool& pool = *Assert(m_node.mempool);
330 [ + - ]: 1 : LOCK2(cs_main, pool.cs);
331 : 1 : TestMemPoolEntryHelper entry;
332 : :
333 : : /* Base transaction */
334 : : //
335 : : // [tx1]
336 : : //
337 [ + - + - ]: 2 : CTransactionRef tx1 = make_tx(/*output_values=*/{10 * COIN});
338 [ + - + - ]: 1 : TryAddToMempool(pool, entry.Fee(10000LL).FromTx(tx1));
339 : :
340 : : // Ancestors / clustersize should be 1 / 1 (itself / itself)
341 [ + - ]: 1 : pool.GetTransactionAncestry(tx1->GetHash(), ancestors, clustersize);
342 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 1ULL);
343 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(clustersize, 1ULL);
344 : :
345 : : /* Child transaction */
346 : : //
347 : : // [tx1].0 <- [tx2]
348 : : //
349 [ + - + - : 3 : CTransactionRef tx2 = make_tx(/*output_values=*/{495 * CENT, 5 * COIN}, /*inputs=*/{tx1});
+ + + - -
- - - ]
350 [ + - + - ]: 1 : TryAddToMempool(pool, entry.Fee(10000LL).FromTx(tx2));
351 : :
352 : : // Ancestors / clustersize should be:
353 : : // transaction ancestors clustersize
354 : : // ============ =========== ===========
355 : : // tx1 1 (tx1) 2 (tx1,2)
356 : : // tx2 2 (tx1,2) 2 (tx1,2)
357 [ + - ]: 1 : pool.GetTransactionAncestry(tx1->GetHash(), ancestors, clustersize);
358 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 1ULL);
359 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(clustersize, 2ULL);
360 [ + - ]: 1 : pool.GetTransactionAncestry(tx2->GetHash(), ancestors, clustersize);
361 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 2ULL);
362 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(clustersize, 2ULL);
363 : :
364 : : /* Grand-child 1 */
365 : : //
366 : : // [tx1].0 <- [tx2].0 <- [tx3]
367 : : //
368 [ + - + - : 3 : CTransactionRef tx3 = make_tx(/*output_values=*/{290 * CENT, 200 * CENT}, /*inputs=*/{tx2});
+ + + - -
- - - ]
369 [ + - + - ]: 1 : TryAddToMempool(pool, entry.Fee(10000LL).FromTx(tx3));
370 : :
371 : : // Ancestors / clustersize should be:
372 : : // transaction ancestors clustersize
373 : : // ============ =========== ===========
374 : : // tx1 1 (tx1) 3 (tx1,2,3)
375 : : // tx2 2 (tx1,2) 3 (tx1,2,3)
376 : : // tx3 3 (tx1,2,3) 3 (tx1,2,3)
377 [ + - ]: 1 : pool.GetTransactionAncestry(tx1->GetHash(), ancestors, clustersize);
378 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 1ULL);
379 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(clustersize, 3ULL);
380 [ + - ]: 1 : pool.GetTransactionAncestry(tx2->GetHash(), ancestors, clustersize);
381 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 2ULL);
382 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(clustersize, 3ULL);
383 [ + - ]: 1 : pool.GetTransactionAncestry(tx3->GetHash(), ancestors, clustersize);
384 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 3ULL);
385 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(clustersize, 3ULL);
386 : :
387 : : /* Grand-child 2 */
388 : : //
389 : : // [tx1].0 <- [tx2].0 <- [tx3]
390 : : // |
391 : : // \---1 <- [tx4]
392 : : //
393 [ + - + - : 5 : CTransactionRef tx4 = make_tx(/*output_values=*/{290 * CENT, 250 * CENT}, /*inputs=*/{tx2}, /*input_indices=*/{1});
+ - + + +
- + - - -
- - ]
394 [ + - + - ]: 1 : TryAddToMempool(pool, entry.Fee(10000LL).FromTx(tx4));
395 : :
396 : : // Ancestors / clustersize should be:
397 : : // transaction ancestors clustersize
398 : : // ============ =========== ===========
399 : : // tx1 1 (tx1) 4 (tx1,2,3,4)
400 : : // tx2 2 (tx1,2) 4 (tx1,2,3,4)
401 : : // tx3 3 (tx1,2,3) 4 (tx1,2,3,4)
402 : : // tx4 3 (tx1,2,4) 4 (tx1,2,3,4)
403 [ + - ]: 1 : pool.GetTransactionAncestry(tx1->GetHash(), ancestors, clustersize);
404 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 1ULL);
405 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(clustersize, 4ULL);
406 [ + - ]: 1 : pool.GetTransactionAncestry(tx2->GetHash(), ancestors, clustersize);
407 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 2ULL);
408 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(clustersize, 4ULL);
409 [ + - ]: 1 : pool.GetTransactionAncestry(tx3->GetHash(), ancestors, clustersize);
410 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 3ULL);
411 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(clustersize, 4ULL);
412 [ + - ]: 1 : pool.GetTransactionAncestry(tx4->GetHash(), ancestors, clustersize);
413 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 3ULL);
414 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(clustersize, 4ULL);
415 : :
416 : : /* Make an alternate branch that is longer and connect it to tx3 */
417 : : //
418 : : // [ty1].0 <- [ty2].0 <- [ty3].0 <- [ty4].0 <- [ty5].0
419 : : // |
420 : : // [tx1].0 <- [tx2].0 <- [tx3].0 <- [ty6] --->--/
421 : : // |
422 : : // \---1 <- [tx4]
423 : : //
424 : 1 : CTransactionRef ty1, ty2, ty3, ty4, ty5;
425 : 1 : CTransactionRef* ty[5] = {&ty1, &ty2, &ty3, &ty4, &ty5};
426 : 1 : CAmount v = 5 * COIN;
427 [ + + ]: 6 : for (uint64_t i = 0; i < 5; i++) {
428 : 5 : CTransactionRef& tyi = *ty[i];
429 [ + + + - : 22 : tyi = make_tx(/*output_values=*/{v}, /*inputs=*/i > 0 ? std::vector<CTransactionRef>{*ty[i - 1]} : std::vector<CTransactionRef>{});
+ - + - -
+ + + + +
+ - - - -
- - - ]
430 : 5 : v -= 50 * CENT;
431 [ + - + - ]: 5 : TryAddToMempool(pool, entry.Fee(10000LL).FromTx(tyi));
432 [ + - ]: 5 : pool.GetTransactionAncestry(tyi->GetHash(), ancestors, clustersize);
433 [ + - + - ]: 5 : BOOST_CHECK_EQUAL(ancestors, i+1);
434 [ + - + - ]: 5 : BOOST_CHECK_EQUAL(clustersize, i+1);
435 : : }
436 [ + - + - : 4 : CTransactionRef ty6 = make_tx(/*output_values=*/{5 * COIN}, /*inputs=*/{tx3, ty5});
+ + + - -
- - - ]
437 [ + - + - ]: 1 : TryAddToMempool(pool, entry.Fee(10000LL).FromTx(ty6));
438 : :
439 : : // Ancestors / clustersize should be:
440 : : // transaction ancestors clustersize
441 : : // ============ =================== ===========
442 : : // tx1 1 (tx1) 10 (tx1-5, ty1-5)
443 : : // tx2 2 (tx1,2) 10
444 : : // tx3 3 (tx1,2,3) 10
445 : : // tx4 3 (tx1,2,4) 10
446 : : // ty1 1 (ty1) 10
447 : : // ty2 2 (ty1,2) 10
448 : : // ty3 3 (ty1,2,3) 10
449 : : // ty4 4 (y1234) 10
450 : : // ty5 5 (y12345) 10
451 : : // ty6 9 (tx123, ty123456) 10
452 [ + - ]: 1 : pool.GetTransactionAncestry(tx1->GetHash(), ancestors, clustersize);
453 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 1ULL);
454 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(clustersize, 10ULL);
455 [ + - ]: 1 : pool.GetTransactionAncestry(tx2->GetHash(), ancestors, clustersize);
456 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 2ULL);
457 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(clustersize, 10ULL);
458 [ + - ]: 1 : pool.GetTransactionAncestry(tx3->GetHash(), ancestors, clustersize);
459 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 3ULL);
460 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(clustersize, 10ULL);
461 [ + - ]: 1 : pool.GetTransactionAncestry(tx4->GetHash(), ancestors, clustersize);
462 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 3ULL);
463 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(clustersize, 10ULL);
464 [ + - ]: 1 : pool.GetTransactionAncestry(ty1->GetHash(), ancestors, clustersize);
465 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 1ULL);
466 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(clustersize, 10ULL);
467 [ + - ]: 1 : pool.GetTransactionAncestry(ty2->GetHash(), ancestors, clustersize);
468 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 2ULL);
469 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(clustersize, 10ULL);
470 [ + - ]: 1 : pool.GetTransactionAncestry(ty3->GetHash(), ancestors, clustersize);
471 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 3ULL);
472 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(clustersize, 10ULL);
473 [ + - ]: 1 : pool.GetTransactionAncestry(ty4->GetHash(), ancestors, clustersize);
474 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 4ULL);
475 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(clustersize, 10ULL);
476 [ + - ]: 1 : pool.GetTransactionAncestry(ty5->GetHash(), ancestors, clustersize);
477 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 5ULL);
478 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(clustersize, 10ULL);
479 [ + - ]: 1 : pool.GetTransactionAncestry(ty6->GetHash(), ancestors, clustersize);
480 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 9ULL);
481 [ + - + - : 1 : BOOST_CHECK_EQUAL(clustersize, 10ULL);
+ - ]
482 [ + - + - : 25 : }
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - ]
483 : :
484 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(MempoolAncestryTestsDiamond)
+ - + - -
+ + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- ]
485 : : {
486 : 1 : size_t ancestors, descendants;
487 : :
488 [ - + ]: 1 : CTxMemPool& pool = *Assert(m_node.mempool);
489 [ + - ]: 1 : LOCK2(::cs_main, pool.cs);
490 : 1 : TestMemPoolEntryHelper entry;
491 : :
492 : : /* Ancestors represented more than once ("diamond") */
493 : : //
494 : : // [ta].0 <- [tb].0 -----<------- [td].0
495 : : // | |
496 : : // \---1 <- [tc].0 --<--/
497 : : //
498 : 1 : CTransactionRef ta, tb, tc, td;
499 [ + - + - : 2 : ta = make_tx(/*output_values=*/{10 * COIN});
- + ]
500 [ + - + - : 3 : tb = make_tx(/*output_values=*/{5 * COIN, 3 * COIN}, /*inputs=*/ {ta});
- + + + +
- - - -
- ]
501 [ + - + - : 5 : tc = make_tx(/*output_values=*/{2 * COIN}, /*inputs=*/{tb}, /*input_indices=*/{1});
+ - - + +
+ + - + -
- - - - ]
502 [ + - + - : 6 : td = make_tx(/*output_values=*/{6 * COIN}, /*inputs=*/{tb, tc}, /*input_indices=*/{0, 0});
+ - - + +
+ + - + -
- - - - ]
503 [ + - + - ]: 1 : TryAddToMempool(pool, entry.Fee(10000LL).FromTx(ta));
504 [ + - + - ]: 1 : TryAddToMempool(pool, entry.Fee(10000LL).FromTx(tb));
505 [ + - + - ]: 1 : TryAddToMempool(pool, entry.Fee(10000LL).FromTx(tc));
506 [ + - + - ]: 1 : TryAddToMempool(pool, entry.Fee(10000LL).FromTx(td));
507 : :
508 : : // Ancestors / descendants should be:
509 : : // transaction ancestors descendants
510 : : // ============ =================== ===========
511 : : // ta 1 (ta 4 (ta,tb,tc,td)
512 : : // tb 2 (ta,tb) 4 (ta,tb,tc,td)
513 : : // tc 3 (ta,tb,tc) 4 (ta,tb,tc,td)
514 : : // td 4 (ta,tb,tc,td) 4 (ta,tb,tc,td)
515 [ + - ]: 1 : pool.GetTransactionAncestry(ta->GetHash(), ancestors, descendants);
516 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 1ULL);
517 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(descendants, 4ULL);
518 [ + - ]: 1 : pool.GetTransactionAncestry(tb->GetHash(), ancestors, descendants);
519 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 2ULL);
520 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(descendants, 4ULL);
521 [ + - ]: 1 : pool.GetTransactionAncestry(tc->GetHash(), ancestors, descendants);
522 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 3ULL);
523 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(descendants, 4ULL);
524 [ + - ]: 1 : pool.GetTransactionAncestry(td->GetHash(), ancestors, descendants);
525 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 4ULL);
526 [ + - + - : 1 : BOOST_CHECK_EQUAL(descendants, 4ULL);
+ - ]
527 [ + - + - : 13 : }
+ - + - +
- + - + -
+ - + - +
- + - +
- ]
528 : :
529 : : BOOST_AUTO_TEST_SUITE_END()
|
