Branch data Line data Source code
1 : : // Copyright (c) 2011-2022 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/txmempool.h>
8 : : #include <txmempool.h>
9 : : #include <util/time.h>
10 : :
11 : : #include <test/util/setup_common.h>
12 : :
13 : : #include <boost/test/unit_test.hpp>
14 : : #include <vector>
15 : :
16 : : BOOST_FIXTURE_TEST_SUITE(mempool_tests, TestingSetup)
17 : :
18 : : static constexpr auto REMOVAL_REASON_DUMMY = MemPoolRemovalReason::REPLACED;
19 : :
20 : : class MemPoolTest final : public CTxMemPool
21 : : {
22 : : public:
23 : : using CTxMemPool::GetMinFee;
24 : : };
25 : :
26 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(MempoolRemoveTest)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
27 : : {
28 : : // Test CTxMemPool::remove functionality
29 : :
30 : 1 : TestMemPoolEntryHelper entry;
31 : : // Parent transaction with three children,
32 : : // and three grand-children:
33 : 1 : CMutableTransaction txParent;
34 [ + - ]: 1 : txParent.vin.resize(1);
35 [ + - ]: 1 : txParent.vin[0].scriptSig = CScript() << OP_11;
36 [ + - ]: 1 : txParent.vout.resize(3);
37 [ + + ]: 4 : for (int i = 0; i < 3; i++)
38 : : {
39 [ + - + - ]: 3 : txParent.vout[i].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
40 : 3 : txParent.vout[i].nValue = 33000LL;
41 : : }
42 [ + - + + : 10 : CMutableTransaction txChild[3];
- - ]
43 [ + + ]: 4 : for (int i = 0; i < 3; i++)
44 : : {
45 [ + - ]: 3 : txChild[i].vin.resize(1);
46 [ + - ]: 3 : txChild[i].vin[0].scriptSig = CScript() << OP_11;
47 [ + - + - ]: 3 : txChild[i].vin[0].prevout.hash = txParent.GetHash();
48 : 3 : txChild[i].vin[0].prevout.n = i;
49 [ + - ]: 3 : txChild[i].vout.resize(1);
50 [ + - + - ]: 3 : txChild[i].vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
51 : 3 : txChild[i].vout[0].nValue = 11000LL;
52 : : }
53 [ + - + + : 11 : CMutableTransaction txGrandChild[3];
- - ]
54 [ + + ]: 4 : for (int i = 0; i < 3; i++)
55 : : {
56 [ + - ]: 3 : txGrandChild[i].vin.resize(1);
57 [ + - ]: 3 : txGrandChild[i].vin[0].scriptSig = CScript() << OP_11;
58 [ + - + - ]: 3 : txGrandChild[i].vin[0].prevout.hash = txChild[i].GetHash();
59 : 3 : txGrandChild[i].vin[0].prevout.n = 0;
60 [ + - ]: 3 : txGrandChild[i].vout.resize(1);
61 [ + - + - ]: 3 : txGrandChild[i].vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
62 : 3 : txGrandChild[i].vout[0].nValue = 11000LL;
63 : : }
64 : :
65 : :
66 [ + - + - ]: 1 : CTxMemPool& testPool = *Assert(m_node.mempool);
67 [ + - + - ]: 1 : LOCK2(::cs_main, testPool.cs);
68 : :
69 : : // Nothing in pool, remove should do nothing:
70 [ + - ]: 1 : unsigned int poolSize = testPool.size();
71 [ + - + - ]: 1 : testPool.removeRecursive(CTransaction(txParent), REMOVAL_REASON_DUMMY);
72 [ + - + - : 1 : BOOST_CHECK_EQUAL(testPool.size(), poolSize);
+ - ]
73 : :
74 : : // Just the parent:
75 [ + - + - ]: 1 : testPool.addUnchecked(entry.FromTx(txParent));
76 [ + - ]: 1 : poolSize = testPool.size();
77 [ + - + - ]: 1 : testPool.removeRecursive(CTransaction(txParent), REMOVAL_REASON_DUMMY);
78 [ + - + - : 1 : BOOST_CHECK_EQUAL(testPool.size(), poolSize - 1);
+ - ]
79 : :
80 : : // Parent, children, grandchildren:
81 [ + - + - ]: 1 : testPool.addUnchecked(entry.FromTx(txParent));
82 [ + + ]: 4 : for (int i = 0; i < 3; i++)
83 : : {
84 [ + - + - ]: 3 : testPool.addUnchecked(entry.FromTx(txChild[i]));
85 [ + - + - ]: 3 : testPool.addUnchecked(entry.FromTx(txGrandChild[i]));
86 : : }
87 : : // Remove Child[0], GrandChild[0] should be removed:
88 [ + - ]: 1 : poolSize = testPool.size();
89 [ + - + - ]: 1 : testPool.removeRecursive(CTransaction(txChild[0]), REMOVAL_REASON_DUMMY);
90 [ + - + - : 1 : BOOST_CHECK_EQUAL(testPool.size(), poolSize - 2);
+ - ]
91 : : // ... make sure grandchild and child are gone:
92 [ + - ]: 1 : poolSize = testPool.size();
93 [ + - + - ]: 1 : testPool.removeRecursive(CTransaction(txGrandChild[0]), REMOVAL_REASON_DUMMY);
94 [ + - + - : 1 : BOOST_CHECK_EQUAL(testPool.size(), poolSize);
+ - ]
95 [ + - ]: 1 : poolSize = testPool.size();
96 [ + - + - ]: 1 : testPool.removeRecursive(CTransaction(txChild[0]), REMOVAL_REASON_DUMMY);
97 [ + - + - : 1 : BOOST_CHECK_EQUAL(testPool.size(), poolSize);
+ - ]
98 : : // Remove parent, all children/grandchildren should go:
99 [ + - ]: 1 : poolSize = testPool.size();
100 [ + - + - ]: 1 : testPool.removeRecursive(CTransaction(txParent), REMOVAL_REASON_DUMMY);
101 [ + - + - : 1 : BOOST_CHECK_EQUAL(testPool.size(), poolSize - 5);
+ - ]
102 [ + - + - : 1 : BOOST_CHECK_EQUAL(testPool.size(), 0U);
+ - ]
103 : :
104 : : // Add children and grandchildren, but NOT the parent (simulate the parent being in a block)
105 [ + + ]: 4 : for (int i = 0; i < 3; i++)
106 : : {
107 [ + - + - ]: 3 : testPool.addUnchecked(entry.FromTx(txChild[i]));
108 [ + - + - ]: 3 : testPool.addUnchecked(entry.FromTx(txGrandChild[i]));
109 : : }
110 : : // Now remove the parent, as might happen if a block-re-org occurs but the parent cannot be
111 : : // put into the mempool (maybe because it is non-standard):
112 [ + - ]: 1 : poolSize = testPool.size();
113 [ + - + - ]: 1 : testPool.removeRecursive(CTransaction(txParent), REMOVAL_REASON_DUMMY);
114 [ + - + - : 1 : BOOST_CHECK_EQUAL(testPool.size(), poolSize - 6);
+ - ]
115 [ + - + - : 1 : BOOST_CHECK_EQUAL(testPool.size(), 0U);
+ - + - ]
116 [ + - + + : 10 : }
+ + - - -
- ]
117 : :
118 : : template <typename name>
119 : 12 : static void CheckSort(CTxMemPool& pool, std::vector<std::string>& sortedOrder) EXCLUSIVE_LOCKS_REQUIRED(pool.cs)
120 : : {
121 [ + - ]: 12 : BOOST_CHECK_EQUAL(pool.size(), sortedOrder.size());
122 : 12 : typename CTxMemPool::indexed_transaction_set::index<name>::type::iterator it = pool.mapTx.get<name>().begin();
123 : 12 : int count = 0;
124 [ + + ]: 97 : for (; it != pool.mapTx.get<name>().end(); ++it, ++count) {
125 [ + - ]: 85 : BOOST_CHECK_EQUAL(it->GetTx().GetHash().ToString(), sortedOrder[count]);
126 : : }
127 : 12 : }
128 : :
129 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(MempoolIndexingTest)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
130 : : {
131 : 1 : CTxMemPool& pool = *Assert(m_node.mempool);
132 [ + - ]: 1 : LOCK2(cs_main, pool.cs);
133 : 1 : TestMemPoolEntryHelper entry;
134 : :
135 : : /* 3rd highest fee */
136 [ + - ]: 1 : CMutableTransaction tx1 = CMutableTransaction();
137 [ + - ]: 1 : tx1.vout.resize(1);
138 [ + - + - ]: 1 : tx1.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
139 [ + - ]: 1 : tx1.vout[0].nValue = 10 * COIN;
140 [ + - + - ]: 1 : pool.addUnchecked(entry.Fee(10000LL).FromTx(tx1));
141 : :
142 : : /* highest fee */
143 [ + - ]: 1 : CMutableTransaction tx2 = CMutableTransaction();
144 [ + - ]: 1 : tx2.vout.resize(1);
145 [ + - + - ]: 1 : tx2.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
146 [ + - ]: 1 : tx2.vout[0].nValue = 2 * COIN;
147 [ + - + - ]: 1 : pool.addUnchecked(entry.Fee(20000LL).FromTx(tx2));
148 : :
149 : : /* lowest fee */
150 [ + - ]: 1 : CMutableTransaction tx3 = CMutableTransaction();
151 [ + - ]: 1 : tx3.vout.resize(1);
152 [ + - + - ]: 1 : tx3.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
153 [ + - ]: 1 : tx3.vout[0].nValue = 5 * COIN;
154 [ + - + - ]: 1 : pool.addUnchecked(entry.Fee(0LL).FromTx(tx3));
155 : :
156 : : /* 2nd highest fee */
157 [ + - ]: 1 : CMutableTransaction tx4 = CMutableTransaction();
158 [ + - ]: 1 : tx4.vout.resize(1);
159 [ + - + - ]: 1 : tx4.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
160 [ + - ]: 1 : tx4.vout[0].nValue = 6 * COIN;
161 [ + - + - ]: 1 : pool.addUnchecked(entry.Fee(15000LL).FromTx(tx4));
162 : :
163 : : /* equal fee rate to tx1, but newer */
164 [ + - ]: 1 : CMutableTransaction tx5 = CMutableTransaction();
165 [ + - ]: 1 : tx5.vout.resize(1);
166 [ + - + - ]: 1 : tx5.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
167 [ + - ]: 1 : tx5.vout[0].nValue = 11 * COIN;
168 [ + - ]: 1 : entry.time = NodeSeconds{1s};
169 [ + - + - ]: 1 : pool.addUnchecked(entry.Fee(10000LL).FromTx(tx5));
170 [ + - + - : 1 : BOOST_CHECK_EQUAL(pool.size(), 5U);
+ - ]
171 : :
172 : 1 : std::vector<std::string> sortedOrder;
173 [ + - ]: 1 : sortedOrder.resize(5);
174 [ + - ]: 2 : sortedOrder[0] = tx3.GetHash().ToString(); // 0
175 [ + - ]: 2 : sortedOrder[1] = tx5.GetHash().ToString(); // 10000
176 [ + - ]: 2 : sortedOrder[2] = tx1.GetHash().ToString(); // 10000
177 [ + - ]: 2 : sortedOrder[3] = tx4.GetHash().ToString(); // 15000
178 [ + - ]: 2 : sortedOrder[4] = tx2.GetHash().ToString(); // 20000
179 [ + - ]: 1 : CheckSort<descendant_score>(pool, sortedOrder);
180 : :
181 : : /* low fee but with high fee child */
182 : : /* tx6 -> tx7 -> tx8, tx9 -> tx10 */
183 [ + - ]: 1 : CMutableTransaction tx6 = CMutableTransaction();
184 [ + - ]: 1 : tx6.vout.resize(1);
185 [ + - + - ]: 1 : tx6.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
186 [ + - ]: 1 : tx6.vout[0].nValue = 20 * COIN;
187 [ + - + - ]: 1 : pool.addUnchecked(entry.Fee(0LL).FromTx(tx6));
188 [ + - + - : 1 : BOOST_CHECK_EQUAL(pool.size(), 6U);
+ - ]
189 : : // Check that at this point, tx6 is sorted low
190 [ + - + - ]: 2 : sortedOrder.insert(sortedOrder.begin(), tx6.GetHash().ToString());
191 [ + - ]: 1 : CheckSort<descendant_score>(pool, sortedOrder);
192 : :
193 [ + - ]: 1 : CTxMemPool::setEntries setAncestors;
194 [ + - + - : 2 : setAncestors.insert(pool.GetIter(tx6.GetHash()).value());
+ - ]
195 [ + - ]: 1 : CMutableTransaction tx7 = CMutableTransaction();
196 [ + - ]: 1 : tx7.vin.resize(1);
197 [ + - + - ]: 1 : tx7.vin[0].prevout = COutPoint(tx6.GetHash(), 0);
198 [ + - ]: 1 : tx7.vin[0].scriptSig = CScript() << OP_11;
199 [ + - ]: 1 : tx7.vout.resize(2);
200 [ + - + - ]: 1 : tx7.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
201 [ + - ]: 1 : tx7.vout[0].nValue = 10 * COIN;
202 [ + - + - ]: 1 : tx7.vout[1].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
203 [ + - ]: 1 : tx7.vout[1].nValue = 1 * COIN;
204 : :
205 : 1 : {
206 [ + - + - ]: 1 : auto ancestors_calculated{pool.CalculateMemPoolAncestors(entry.Fee(2000000LL).FromTx(tx7), CTxMemPool::Limits::NoLimits())};
207 [ + - + - : 2 : BOOST_REQUIRE(ancestors_calculated.has_value());
+ - ]
208 [ + - + - ]: 2 : BOOST_CHECK(*ancestors_calculated == setAncestors);
209 : 0 : }
210 : :
211 [ + - + - ]: 1 : pool.addUnchecked(entry.FromTx(tx7), setAncestors);
212 [ + - + - : 1 : BOOST_CHECK_EQUAL(pool.size(), 7U);
+ - ]
213 : :
214 : : // Now tx6 should be sorted higher (high fee child): tx7, tx6, tx2, ...
215 : 1 : sortedOrder.erase(sortedOrder.begin());
216 [ + - + - ]: 2 : sortedOrder.push_back(tx6.GetHash().ToString());
217 [ + - + - ]: 2 : sortedOrder.push_back(tx7.GetHash().ToString());
218 [ + - ]: 1 : CheckSort<descendant_score>(pool, sortedOrder);
219 : :
220 : : /* low fee child of tx7 */
221 [ + - ]: 1 : CMutableTransaction tx8 = CMutableTransaction();
222 [ + - ]: 1 : tx8.vin.resize(1);
223 [ + - + - ]: 1 : tx8.vin[0].prevout = COutPoint(tx7.GetHash(), 0);
224 [ + - ]: 1 : tx8.vin[0].scriptSig = CScript() << OP_11;
225 [ + - ]: 1 : tx8.vout.resize(1);
226 [ + - + - ]: 1 : tx8.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
227 [ + - ]: 1 : tx8.vout[0].nValue = 10 * COIN;
228 [ + - + - : 2 : setAncestors.insert(pool.GetIter(tx7.GetHash()).value());
+ - ]
229 [ + - + - ]: 1 : pool.addUnchecked(entry.Fee(0LL).Time(NodeSeconds{2s}).FromTx(tx8), setAncestors);
230 : :
231 : : // Now tx8 should be sorted low, but tx6/tx both high
232 [ + - + - ]: 2 : sortedOrder.insert(sortedOrder.begin(), tx8.GetHash().ToString());
233 [ + - ]: 1 : CheckSort<descendant_score>(pool, sortedOrder);
234 : :
235 : : /* low fee child of tx7 */
236 [ + - ]: 1 : CMutableTransaction tx9 = CMutableTransaction();
237 [ + - ]: 1 : tx9.vin.resize(1);
238 [ + - + - ]: 1 : tx9.vin[0].prevout = COutPoint(tx7.GetHash(), 1);
239 [ + - ]: 1 : tx9.vin[0].scriptSig = CScript() << OP_11;
240 [ + - ]: 1 : tx9.vout.resize(1);
241 [ + - + - ]: 1 : tx9.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
242 [ + - ]: 1 : tx9.vout[0].nValue = 1 * COIN;
243 [ + - + - ]: 1 : pool.addUnchecked(entry.Fee(0LL).Time(NodeSeconds{3s}).FromTx(tx9), setAncestors);
244 : :
245 : : // tx9 should be sorted low
246 [ + - + - : 1 : BOOST_CHECK_EQUAL(pool.size(), 9U);
+ - ]
247 [ + - + - ]: 2 : sortedOrder.insert(sortedOrder.begin(), tx9.GetHash().ToString());
248 [ + - ]: 1 : CheckSort<descendant_score>(pool, sortedOrder);
249 : :
250 [ + - ]: 1 : std::vector<std::string> snapshotOrder = sortedOrder;
251 : :
252 [ + - + - : 2 : setAncestors.insert(pool.GetIter(tx8.GetHash()).value());
+ - ]
253 [ + - + - : 2 : setAncestors.insert(pool.GetIter(tx9.GetHash()).value());
+ - ]
254 : : /* tx10 depends on tx8 and tx9 and has a high fee*/
255 [ + - ]: 1 : CMutableTransaction tx10 = CMutableTransaction();
256 [ + - ]: 1 : tx10.vin.resize(2);
257 [ + - + - ]: 1 : tx10.vin[0].prevout = COutPoint(tx8.GetHash(), 0);
258 [ + - ]: 1 : tx10.vin[0].scriptSig = CScript() << OP_11;
259 [ + - + - ]: 1 : tx10.vin[1].prevout = COutPoint(tx9.GetHash(), 0);
260 [ + - ]: 1 : tx10.vin[1].scriptSig = CScript() << OP_11;
261 [ + - ]: 1 : tx10.vout.resize(1);
262 [ + - + - ]: 1 : tx10.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
263 [ + - ]: 1 : tx10.vout[0].nValue = 10 * COIN;
264 : :
265 : 1 : {
266 [ + - + - ]: 1 : auto ancestors_calculated{pool.CalculateMemPoolAncestors(entry.Fee(200000LL).Time(NodeSeconds{4s}).FromTx(tx10), CTxMemPool::Limits::NoLimits())};
267 [ + - + - : 2 : BOOST_REQUIRE(ancestors_calculated);
+ - ]
268 [ + - + - ]: 2 : BOOST_CHECK(*ancestors_calculated == setAncestors);
269 : 0 : }
270 : :
271 [ + - + - ]: 1 : pool.addUnchecked(entry.FromTx(tx10), setAncestors);
272 : :
273 : : /**
274 : : * tx8 and tx9 should both now be sorted higher
275 : : * Final order after tx10 is added:
276 : : *
277 : : * tx3 = 0 (1)
278 : : * tx5 = 10000 (1)
279 : : * tx1 = 10000 (1)
280 : : * tx4 = 15000 (1)
281 : : * tx2 = 20000 (1)
282 : : * tx9 = 200k (2 txs)
283 : : * tx8 = 200k (2 txs)
284 : : * tx10 = 200k (1 tx)
285 : : * tx6 = 2.2M (5 txs)
286 : : * tx7 = 2.2M (4 txs)
287 : : */
288 : 1 : sortedOrder.erase(sortedOrder.begin(), sortedOrder.begin()+2); // take out tx9, tx8 from the beginning
289 [ + - + - ]: 2 : sortedOrder.insert(sortedOrder.begin()+5, tx9.GetHash().ToString());
290 [ + - + - ]: 2 : sortedOrder.insert(sortedOrder.begin()+6, tx8.GetHash().ToString());
291 [ + - + - ]: 2 : sortedOrder.insert(sortedOrder.begin()+7, tx10.GetHash().ToString()); // tx10 is just before tx6
292 [ + - ]: 1 : CheckSort<descendant_score>(pool, sortedOrder);
293 : :
294 : : // there should be 10 transactions in the mempool
295 [ + - + - : 1 : BOOST_CHECK_EQUAL(pool.size(), 10U);
+ - ]
296 : :
297 : : // Now try removing tx10 and verify the sort order returns to normal
298 [ + - + - : 1 : pool.removeRecursive(*Assert(pool.get(tx10.GetHash())), REMOVAL_REASON_DUMMY);
+ - + - ]
299 [ + - ]: 1 : CheckSort<descendant_score>(pool, snapshotOrder);
300 : :
301 [ + - + - : 1 : pool.removeRecursive(*Assert(pool.get(tx9.GetHash())), REMOVAL_REASON_DUMMY);
+ - + - ]
302 [ + - + - : 2 : pool.removeRecursive(*Assert(pool.get(tx8.GetHash())), REMOVAL_REASON_DUMMY);
+ - + - ]
303 [ + - + - ]: 12 : }
304 : :
305 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(MempoolAncestorIndexingTest)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
306 : : {
307 : 1 : CTxMemPool& pool = *Assert(m_node.mempool);
308 [ + - ]: 1 : LOCK2(cs_main, pool.cs);
309 : 1 : TestMemPoolEntryHelper entry;
310 : :
311 : : /* 3rd highest fee */
312 [ + - ]: 1 : CMutableTransaction tx1 = CMutableTransaction();
313 [ + - ]: 1 : tx1.vout.resize(1);
314 [ + - + - ]: 1 : tx1.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
315 [ + - ]: 1 : tx1.vout[0].nValue = 10 * COIN;
316 [ + - + - ]: 1 : pool.addUnchecked(entry.Fee(10000LL).FromTx(tx1));
317 : :
318 : : /* highest fee */
319 [ + - ]: 1 : CMutableTransaction tx2 = CMutableTransaction();
320 [ + - ]: 1 : tx2.vout.resize(1);
321 [ + - + - ]: 1 : tx2.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
322 [ + - ]: 1 : tx2.vout[0].nValue = 2 * COIN;
323 [ + - + - ]: 1 : pool.addUnchecked(entry.Fee(20000LL).FromTx(tx2));
324 [ + - ]: 2 : uint64_t tx2Size = GetVirtualTransactionSize(CTransaction(tx2));
325 : :
326 : : /* lowest fee */
327 [ + - ]: 1 : CMutableTransaction tx3 = CMutableTransaction();
328 [ + - ]: 1 : tx3.vout.resize(1);
329 [ + - + - ]: 1 : tx3.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
330 [ + - ]: 1 : tx3.vout[0].nValue = 5 * COIN;
331 [ + - + - ]: 1 : pool.addUnchecked(entry.Fee(0LL).FromTx(tx3));
332 : :
333 : : /* 2nd highest fee */
334 [ + - ]: 1 : CMutableTransaction tx4 = CMutableTransaction();
335 [ + - ]: 1 : tx4.vout.resize(1);
336 [ + - + - ]: 1 : tx4.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
337 [ + - ]: 1 : tx4.vout[0].nValue = 6 * COIN;
338 [ + - + - ]: 1 : pool.addUnchecked(entry.Fee(15000LL).FromTx(tx4));
339 : :
340 : : /* equal fee rate to tx1, but newer */
341 [ + - ]: 1 : CMutableTransaction tx5 = CMutableTransaction();
342 [ + - ]: 1 : tx5.vout.resize(1);
343 [ + - + - ]: 1 : tx5.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
344 [ + - ]: 1 : tx5.vout[0].nValue = 11 * COIN;
345 [ + - + - ]: 1 : pool.addUnchecked(entry.Fee(10000LL).FromTx(tx5));
346 [ + - + - : 1 : BOOST_CHECK_EQUAL(pool.size(), 5U);
+ - ]
347 : :
348 : 1 : std::vector<std::string> sortedOrder;
349 [ + - ]: 1 : sortedOrder.resize(5);
350 [ + - ]: 2 : sortedOrder[0] = tx2.GetHash().ToString(); // 20000
351 [ + - ]: 2 : sortedOrder[1] = tx4.GetHash().ToString(); // 15000
352 : : // tx1 and tx5 are both 10000
353 : : // Ties are broken by hash, not timestamp, so determine which
354 : : // hash comes first.
355 [ + - + - : 1 : if (tx1.GetHash() < tx5.GetHash()) {
+ - ]
356 [ + - ]: 2 : sortedOrder[2] = tx1.GetHash().ToString();
357 [ + - ]: 2 : sortedOrder[3] = tx5.GetHash().ToString();
358 : : } else {
359 [ # # ]: 0 : sortedOrder[2] = tx5.GetHash().ToString();
360 [ # # ]: 0 : sortedOrder[3] = tx1.GetHash().ToString();
361 : : }
362 [ + - ]: 2 : sortedOrder[4] = tx3.GetHash().ToString(); // 0
363 : :
364 [ + - ]: 1 : CheckSort<ancestor_score>(pool, sortedOrder);
365 : :
366 : : /* low fee parent with high fee child */
367 : : /* tx6 (0) -> tx7 (high) */
368 [ + - ]: 1 : CMutableTransaction tx6 = CMutableTransaction();
369 [ + - ]: 1 : tx6.vout.resize(1);
370 [ + - + - ]: 1 : tx6.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
371 [ + - ]: 1 : tx6.vout[0].nValue = 20 * COIN;
372 [ + - ]: 2 : uint64_t tx6Size = GetVirtualTransactionSize(CTransaction(tx6));
373 : :
374 [ + - + - ]: 1 : pool.addUnchecked(entry.Fee(0LL).FromTx(tx6));
375 [ + - + - : 1 : BOOST_CHECK_EQUAL(pool.size(), 6U);
+ - ]
376 : : // Ties are broken by hash
377 [ + - + - : 1 : if (tx3.GetHash() < tx6.GetHash())
- + ]
378 [ # # # # ]: 0 : sortedOrder.push_back(tx6.GetHash().ToString());
379 : : else
380 [ + - + - ]: 2 : sortedOrder.insert(sortedOrder.end()-1,tx6.GetHash().ToString());
381 : :
382 [ + - ]: 1 : CheckSort<ancestor_score>(pool, sortedOrder);
383 : :
384 [ + - ]: 1 : CMutableTransaction tx7 = CMutableTransaction();
385 [ + - ]: 1 : tx7.vin.resize(1);
386 [ + - + - ]: 1 : tx7.vin[0].prevout = COutPoint(tx6.GetHash(), 0);
387 [ + - ]: 1 : tx7.vin[0].scriptSig = CScript() << OP_11;
388 [ + - ]: 1 : tx7.vout.resize(1);
389 [ + - + - ]: 1 : tx7.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
390 [ + - ]: 1 : tx7.vout[0].nValue = 10 * COIN;
391 [ + - ]: 2 : uint64_t tx7Size = GetVirtualTransactionSize(CTransaction(tx7));
392 : :
393 : : /* set the fee to just below tx2's feerate when including ancestor */
394 : 1 : CAmount fee = (20000/tx2Size)*(tx7Size + tx6Size) - 1;
395 : :
396 [ + - + - ]: 1 : pool.addUnchecked(entry.Fee(fee).FromTx(tx7));
397 [ + - + - : 1 : BOOST_CHECK_EQUAL(pool.size(), 7U);
+ - ]
398 [ + - + - ]: 2 : sortedOrder.insert(sortedOrder.begin()+1, tx7.GetHash().ToString());
399 [ + - ]: 1 : CheckSort<ancestor_score>(pool, sortedOrder);
400 : :
401 : : /* after tx6 is mined, tx7 should move up in the sort */
402 : 1 : std::vector<CTransactionRef> vtx;
403 [ + - + - : 2 : vtx.push_back(MakeTransactionRef(tx6));
- + ]
404 [ + - ]: 1 : pool.removeForBlock(vtx, 1);
405 : :
406 : 1 : sortedOrder.erase(sortedOrder.begin()+1);
407 : : // Ties are broken by hash
408 [ + - + - : 1 : if (tx3.GetHash() < tx6.GetHash())
- + ]
409 : 0 : sortedOrder.pop_back();
410 : : else
411 : 1 : sortedOrder.erase(sortedOrder.end()-2);
412 [ + - + - ]: 2 : sortedOrder.insert(sortedOrder.begin(), tx7.GetHash().ToString());
413 [ + - ]: 1 : CheckSort<ancestor_score>(pool, sortedOrder);
414 : :
415 : : // High-fee parent, low-fee child
416 : : // tx7 -> tx8
417 [ + - ]: 1 : CMutableTransaction tx8 = CMutableTransaction();
418 [ + - ]: 1 : tx8.vin.resize(1);
419 [ + - + - ]: 1 : tx8.vin[0].prevout = COutPoint(tx7.GetHash(), 0);
420 [ + - ]: 1 : tx8.vin[0].scriptSig = CScript() << OP_11;
421 [ + - ]: 1 : tx8.vout.resize(1);
422 [ + - + - ]: 1 : tx8.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
423 [ + - ]: 1 : tx8.vout[0].nValue = 10*COIN;
424 : :
425 : : // Check that we sort by min(feerate, ancestor_feerate):
426 : : // set the fee so that the ancestor feerate is above tx1/5,
427 : : // but the transaction's own feerate is lower
428 [ + - + - ]: 1 : pool.addUnchecked(entry.Fee(5000LL).FromTx(tx8));
429 [ + - + - ]: 2 : sortedOrder.insert(sortedOrder.end()-1, tx8.GetHash().ToString());
430 [ + - ]: 1 : CheckSort<ancestor_score>(pool, sortedOrder);
431 [ + - + - ]: 10 : }
432 : :
433 : :
434 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(MempoolSizeLimitTest)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
435 : : {
436 : 1 : auto& pool = static_cast<MemPoolTest&>(*Assert(m_node.mempool));
437 [ + - ]: 1 : LOCK2(cs_main, pool.cs);
438 : 1 : TestMemPoolEntryHelper entry;
439 : :
440 [ + - ]: 1 : CMutableTransaction tx1 = CMutableTransaction();
441 [ + - ]: 1 : tx1.vin.resize(1);
442 [ + - ]: 1 : tx1.vin[0].scriptSig = CScript() << OP_1;
443 [ + - ]: 1 : tx1.vout.resize(1);
444 [ + - + - ]: 1 : tx1.vout[0].scriptPubKey = CScript() << OP_1 << OP_EQUAL;
445 [ + - ]: 1 : tx1.vout[0].nValue = 10 * COIN;
446 [ + - + - ]: 1 : pool.addUnchecked(entry.Fee(10000LL).FromTx(tx1));
447 : :
448 [ + - ]: 1 : CMutableTransaction tx2 = CMutableTransaction();
449 [ + - ]: 1 : tx2.vin.resize(1);
450 [ + - ]: 1 : tx2.vin[0].scriptSig = CScript() << OP_2;
451 [ + - ]: 1 : tx2.vout.resize(1);
452 [ + - + - ]: 1 : tx2.vout[0].scriptPubKey = CScript() << OP_2 << OP_EQUAL;
453 [ + - ]: 1 : tx2.vout[0].nValue = 10 * COIN;
454 [ + - + - ]: 1 : pool.addUnchecked(entry.Fee(5000LL).FromTx(tx2));
455 : :
456 [ + - + - ]: 1 : pool.TrimToSize(pool.DynamicMemoryUsage()); // should do nothing
457 [ + - + - : 2 : BOOST_CHECK(pool.exists(GenTxid::Txid(tx1.GetHash())));
+ - + - +
- ]
458 [ + - + - : 2 : BOOST_CHECK(pool.exists(GenTxid::Txid(tx2.GetHash())));
+ - + - +
- ]
459 : :
460 [ + - + - ]: 1 : pool.TrimToSize(pool.DynamicMemoryUsage() * 3 / 4); // should remove the lower-feerate transaction
461 [ + - + - : 2 : BOOST_CHECK(pool.exists(GenTxid::Txid(tx1.GetHash())));
+ - + - +
- ]
462 [ + - + - : 2 : BOOST_CHECK(!pool.exists(GenTxid::Txid(tx2.GetHash())));
+ - + - +
- ]
463 : :
464 [ + - + - ]: 1 : pool.addUnchecked(entry.FromTx(tx2));
465 [ + - ]: 1 : CMutableTransaction tx3 = CMutableTransaction();
466 [ + - ]: 1 : tx3.vin.resize(1);
467 [ + - + - ]: 1 : tx3.vin[0].prevout = COutPoint(tx2.GetHash(), 0);
468 [ + - ]: 1 : tx3.vin[0].scriptSig = CScript() << OP_2;
469 [ + - ]: 1 : tx3.vout.resize(1);
470 [ + - + - ]: 1 : tx3.vout[0].scriptPubKey = CScript() << OP_3 << OP_EQUAL;
471 [ + - ]: 1 : tx3.vout[0].nValue = 10 * COIN;
472 [ + - + - ]: 1 : pool.addUnchecked(entry.Fee(20000LL).FromTx(tx3));
473 : :
474 [ + - + - ]: 1 : pool.TrimToSize(pool.DynamicMemoryUsage() * 3 / 4); // tx3 should pay for tx2 (CPFP)
475 [ + - + - : 2 : BOOST_CHECK(!pool.exists(GenTxid::Txid(tx1.GetHash())));
+ - + - +
- ]
476 [ + - + - : 2 : BOOST_CHECK(pool.exists(GenTxid::Txid(tx2.GetHash())));
+ - + - +
- ]
477 [ + - + - : 2 : BOOST_CHECK(pool.exists(GenTxid::Txid(tx3.GetHash())));
+ - + - +
- ]
478 : :
479 [ + - + - ]: 2 : pool.TrimToSize(GetVirtualTransactionSize(CTransaction(tx1))); // mempool is limited to tx1's size in memory usage, so nothing fits
480 [ + - + - : 2 : BOOST_CHECK(!pool.exists(GenTxid::Txid(tx1.GetHash())));
+ - + - +
- ]
481 [ + - + - : 2 : BOOST_CHECK(!pool.exists(GenTxid::Txid(tx2.GetHash())));
+ - + - +
- ]
482 [ + - + - : 2 : BOOST_CHECK(!pool.exists(GenTxid::Txid(tx3.GetHash())));
+ - + - +
- ]
483 : :
484 [ + - + - : 4 : CFeeRate maxFeeRateRemoved(25000, GetVirtualTransactionSize(CTransaction(tx3)) + GetVirtualTransactionSize(CTransaction(tx2)));
+ - ]
485 [ + - + - : 1 : BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), maxFeeRateRemoved.GetFeePerK() + 1000);
+ - ]
486 : :
487 [ + - ]: 1 : CMutableTransaction tx4 = CMutableTransaction();
488 [ + - ]: 1 : tx4.vin.resize(2);
489 : 1 : tx4.vin[0].prevout.SetNull();
490 [ + - ]: 1 : tx4.vin[0].scriptSig = CScript() << OP_4;
491 : 1 : tx4.vin[1].prevout.SetNull();
492 [ + - ]: 1 : tx4.vin[1].scriptSig = CScript() << OP_4;
493 [ + - ]: 1 : tx4.vout.resize(2);
494 [ + - + - ]: 1 : tx4.vout[0].scriptPubKey = CScript() << OP_4 << OP_EQUAL;
495 [ + - ]: 1 : tx4.vout[0].nValue = 10 * COIN;
496 [ + - + - ]: 1 : tx4.vout[1].scriptPubKey = CScript() << OP_4 << OP_EQUAL;
497 [ + - ]: 1 : tx4.vout[1].nValue = 10 * COIN;
498 : :
499 [ + - ]: 1 : CMutableTransaction tx5 = CMutableTransaction();
500 [ + - ]: 1 : tx5.vin.resize(2);
501 [ + - + - ]: 1 : tx5.vin[0].prevout = COutPoint(tx4.GetHash(), 0);
502 [ + - ]: 1 : tx5.vin[0].scriptSig = CScript() << OP_4;
503 : 1 : tx5.vin[1].prevout.SetNull();
504 [ + - ]: 1 : tx5.vin[1].scriptSig = CScript() << OP_5;
505 [ + - ]: 1 : tx5.vout.resize(2);
506 [ + - + - ]: 1 : tx5.vout[0].scriptPubKey = CScript() << OP_5 << OP_EQUAL;
507 [ + - ]: 1 : tx5.vout[0].nValue = 10 * COIN;
508 [ + - + - ]: 1 : tx5.vout[1].scriptPubKey = CScript() << OP_5 << OP_EQUAL;
509 [ + - ]: 1 : tx5.vout[1].nValue = 10 * COIN;
510 : :
511 [ + - ]: 1 : CMutableTransaction tx6 = CMutableTransaction();
512 [ + - ]: 1 : tx6.vin.resize(2);
513 [ + - + - ]: 1 : tx6.vin[0].prevout = COutPoint(tx4.GetHash(), 1);
514 [ + - ]: 1 : tx6.vin[0].scriptSig = CScript() << OP_4;
515 : 1 : tx6.vin[1].prevout.SetNull();
516 [ + - ]: 1 : tx6.vin[1].scriptSig = CScript() << OP_6;
517 [ + - ]: 1 : tx6.vout.resize(2);
518 [ + - + - ]: 1 : tx6.vout[0].scriptPubKey = CScript() << OP_6 << OP_EQUAL;
519 [ + - ]: 1 : tx6.vout[0].nValue = 10 * COIN;
520 [ + - + - ]: 1 : tx6.vout[1].scriptPubKey = CScript() << OP_6 << OP_EQUAL;
521 [ + - ]: 1 : tx6.vout[1].nValue = 10 * COIN;
522 : :
523 [ + - ]: 1 : CMutableTransaction tx7 = CMutableTransaction();
524 [ + - ]: 1 : tx7.vin.resize(2);
525 [ + - + - ]: 1 : tx7.vin[0].prevout = COutPoint(tx5.GetHash(), 0);
526 [ + - ]: 1 : tx7.vin[0].scriptSig = CScript() << OP_5;
527 [ + - + - ]: 1 : tx7.vin[1].prevout = COutPoint(tx6.GetHash(), 0);
528 [ + - ]: 1 : tx7.vin[1].scriptSig = CScript() << OP_6;
529 [ + - ]: 1 : tx7.vout.resize(2);
530 [ + - + - ]: 1 : tx7.vout[0].scriptPubKey = CScript() << OP_7 << OP_EQUAL;
531 [ + - ]: 1 : tx7.vout[0].nValue = 10 * COIN;
532 [ + - + - ]: 1 : tx7.vout[1].scriptPubKey = CScript() << OP_7 << OP_EQUAL;
533 [ + - ]: 1 : tx7.vout[1].nValue = 10 * COIN;
534 : :
535 [ + - + - ]: 1 : pool.addUnchecked(entry.Fee(7000LL).FromTx(tx4));
536 [ + - + - ]: 1 : pool.addUnchecked(entry.Fee(1000LL).FromTx(tx5));
537 [ + - + - ]: 1 : pool.addUnchecked(entry.Fee(1100LL).FromTx(tx6));
538 [ + - + - ]: 1 : pool.addUnchecked(entry.Fee(9000LL).FromTx(tx7));
539 : :
540 : : // we only require this to remove, at max, 2 txn, because it's not clear what we're really optimizing for aside from that
541 [ + - + - ]: 1 : pool.TrimToSize(pool.DynamicMemoryUsage() - 1);
542 [ + - + - : 2 : BOOST_CHECK(pool.exists(GenTxid::Txid(tx4.GetHash())));
+ - + - +
- ]
543 [ + - + - : 2 : BOOST_CHECK(pool.exists(GenTxid::Txid(tx6.GetHash())));
+ - + - +
- ]
544 [ + - + - : 2 : BOOST_CHECK(!pool.exists(GenTxid::Txid(tx7.GetHash())));
+ - + - +
- ]
545 : :
546 [ + - + - : 1 : if (!pool.exists(GenTxid::Txid(tx5.GetHash())))
+ - ]
547 [ + - + - ]: 1 : pool.addUnchecked(entry.Fee(1000LL).FromTx(tx5));
548 [ + - + - ]: 1 : pool.addUnchecked(entry.Fee(9000LL).FromTx(tx7));
549 : :
550 [ + - + - ]: 1 : pool.TrimToSize(pool.DynamicMemoryUsage() / 2); // should maximize mempool size by only removing 5/7
551 [ + - + - : 2 : BOOST_CHECK(pool.exists(GenTxid::Txid(tx4.GetHash())));
+ - + - +
- ]
552 [ + - + - : 2 : BOOST_CHECK(!pool.exists(GenTxid::Txid(tx5.GetHash())));
+ - + - +
- ]
553 [ + - + - : 2 : BOOST_CHECK(pool.exists(GenTxid::Txid(tx6.GetHash())));
+ - + - +
- ]
554 [ + - + - : 2 : BOOST_CHECK(!pool.exists(GenTxid::Txid(tx7.GetHash())));
+ - + - +
- ]
555 : :
556 [ + - + - ]: 1 : pool.addUnchecked(entry.Fee(1000LL).FromTx(tx5));
557 [ + - + - ]: 1 : pool.addUnchecked(entry.Fee(9000LL).FromTx(tx7));
558 : :
559 : 1 : std::vector<CTransactionRef> vtx;
560 [ + - ]: 1 : SetMockTime(42);
561 [ + - ]: 1 : SetMockTime(42 + CTxMemPool::ROLLING_FEE_HALFLIFE);
562 [ + - + - : 1 : BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), maxFeeRateRemoved.GetFeePerK() + 1000);
+ - ]
563 : : // ... we should keep the same min fee until we get a block
564 [ + - ]: 1 : pool.removeForBlock(vtx, 1);
565 [ + - ]: 1 : SetMockTime(42 + 2*CTxMemPool::ROLLING_FEE_HALFLIFE);
566 [ + - + - : 1 : BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), llround((maxFeeRateRemoved.GetFeePerK() + 1000)/2.0));
+ - ]
567 : : // ... then feerate should drop 1/2 each halflife
568 : :
569 [ + - ]: 1 : SetMockTime(42 + 2*CTxMemPool::ROLLING_FEE_HALFLIFE + CTxMemPool::ROLLING_FEE_HALFLIFE/2);
570 [ + - + - : 1 : BOOST_CHECK_EQUAL(pool.GetMinFee(pool.DynamicMemoryUsage() * 5 / 2).GetFeePerK(), llround((maxFeeRateRemoved.GetFeePerK() + 1000)/4.0));
+ - + - ]
571 : : // ... with a 1/2 halflife when mempool is < 1/2 its target size
572 : :
573 [ + - ]: 1 : SetMockTime(42 + 2*CTxMemPool::ROLLING_FEE_HALFLIFE + CTxMemPool::ROLLING_FEE_HALFLIFE/2 + CTxMemPool::ROLLING_FEE_HALFLIFE/4);
574 [ + - + - : 1 : BOOST_CHECK_EQUAL(pool.GetMinFee(pool.DynamicMemoryUsage() * 9 / 2).GetFeePerK(), llround((maxFeeRateRemoved.GetFeePerK() + 1000)/8.0));
+ - + - ]
575 : : // ... with a 1/4 halflife when mempool is < 1/4 its target size
576 : :
577 [ + - ]: 1 : SetMockTime(42 + 7*CTxMemPool::ROLLING_FEE_HALFLIFE + CTxMemPool::ROLLING_FEE_HALFLIFE/2 + CTxMemPool::ROLLING_FEE_HALFLIFE/4);
578 [ + - + - : 1 : BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), 1000);
+ - ]
579 : : // ... but feerate should never drop below 1000
580 : :
581 [ + - ]: 1 : SetMockTime(42 + 8*CTxMemPool::ROLLING_FEE_HALFLIFE + CTxMemPool::ROLLING_FEE_HALFLIFE/2 + CTxMemPool::ROLLING_FEE_HALFLIFE/4);
582 [ + - + - : 1 : BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), 0);
+ - ]
583 : : // ... unless it has gone all the way to 0 (after getting past 1000/2)
584 [ + - + - ]: 10 : }
585 : :
586 : 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>())
587 : : {
588 : 14 : CMutableTransaction tx = CMutableTransaction();
589 [ + - ]: 14 : tx.vin.resize(inputs.size());
590 [ + - ]: 14 : tx.vout.resize(output_values.size());
591 [ + + ]: 27 : for (size_t i = 0; i < inputs.size(); ++i) {
592 [ + + ]: 13 : tx.vin[i].prevout.hash = inputs[i]->GetHash();
593 [ + + ]: 13 : tx.vin[i].prevout.n = input_indices.size() > i ? input_indices[i] : 0;
594 : : }
595 [ + + ]: 32 : for (size_t i = 0; i < output_values.size(); ++i) {
596 [ + - + - ]: 18 : tx.vout[i].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
597 : 18 : tx.vout[i].nValue = output_values[i];
598 : : }
599 [ + - ]: 28 : return MakeTransactionRef(tx);
600 : 14 : }
601 : :
602 : :
603 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(MempoolAncestryTests)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
604 : : {
605 : 1 : size_t ancestors, descendants;
606 : :
607 : 1 : CTxMemPool& pool = *Assert(m_node.mempool);
608 [ + - ]: 1 : LOCK2(cs_main, pool.cs);
609 : 1 : TestMemPoolEntryHelper entry;
610 : :
611 : : /* Base transaction */
612 : : //
613 : : // [tx1]
614 : : //
615 [ + - + - ]: 2 : CTransactionRef tx1 = make_tx(/*output_values=*/{10 * COIN});
616 [ + - + - ]: 1 : pool.addUnchecked(entry.Fee(10000LL).FromTx(tx1));
617 : :
618 : : // Ancestors / descendants should be 1 / 1 (itself / itself)
619 [ + - ]: 1 : pool.GetTransactionAncestry(tx1->GetHash(), ancestors, descendants);
620 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 1ULL);
621 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(descendants, 1ULL);
622 : :
623 : : /* Child transaction */
624 : : //
625 : : // [tx1].0 <- [tx2]
626 : : //
627 [ + - + - : 4 : CTransactionRef tx2 = make_tx(/*output_values=*/{495 * CENT, 5 * COIN}, /*inputs=*/{tx1});
+ - + + +
- - - -
- ]
628 [ + - + - ]: 1 : pool.addUnchecked(entry.Fee(10000LL).FromTx(tx2));
629 : :
630 : : // Ancestors / descendants should be:
631 : : // transaction ancestors descendants
632 : : // ============ =========== ===========
633 : : // tx1 1 (tx1) 2 (tx1,2)
634 : : // tx2 2 (tx1,2) 2 (tx1,2)
635 [ + - ]: 1 : pool.GetTransactionAncestry(tx1->GetHash(), ancestors, descendants);
636 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 1ULL);
637 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(descendants, 2ULL);
638 [ + - ]: 1 : pool.GetTransactionAncestry(tx2->GetHash(), ancestors, descendants);
639 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 2ULL);
640 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(descendants, 2ULL);
641 : :
642 : : /* Grand-child 1 */
643 : : //
644 : : // [tx1].0 <- [tx2].0 <- [tx3]
645 : : //
646 [ + - + - : 4 : CTransactionRef tx3 = make_tx(/*output_values=*/{290 * CENT, 200 * CENT}, /*inputs=*/{tx2});
+ - + + +
- - - -
- ]
647 [ + - + - ]: 1 : pool.addUnchecked(entry.Fee(10000LL).FromTx(tx3));
648 : :
649 : : // Ancestors / descendants should be:
650 : : // transaction ancestors descendants
651 : : // ============ =========== ===========
652 : : // tx1 1 (tx1) 3 (tx1,2,3)
653 : : // tx2 2 (tx1,2) 3 (tx1,2,3)
654 : : // tx3 3 (tx1,2,3) 3 (tx1,2,3)
655 [ + - ]: 1 : pool.GetTransactionAncestry(tx1->GetHash(), ancestors, descendants);
656 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 1ULL);
657 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(descendants, 3ULL);
658 [ + - ]: 1 : pool.GetTransactionAncestry(tx2->GetHash(), ancestors, descendants);
659 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 2ULL);
660 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(descendants, 3ULL);
661 [ + - ]: 1 : pool.GetTransactionAncestry(tx3->GetHash(), ancestors, descendants);
662 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 3ULL);
663 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(descendants, 3ULL);
664 : :
665 : : /* Grand-child 2 */
666 : : //
667 : : // [tx1].0 <- [tx2].0 <- [tx3]
668 : : // |
669 : : // \---1 <- [tx4]
670 : : //
671 [ + - + - : 5 : CTransactionRef tx4 = make_tx(/*output_values=*/{290 * CENT, 250 * CENT}, /*inputs=*/{tx2}, /*input_indices=*/{1});
+ - + + +
- + - - -
- - ]
672 [ + - + - ]: 1 : pool.addUnchecked(entry.Fee(10000LL).FromTx(tx4));
673 : :
674 : : // Ancestors / descendants should be:
675 : : // transaction ancestors descendants
676 : : // ============ =========== ===========
677 : : // tx1 1 (tx1) 4 (tx1,2,3,4)
678 : : // tx2 2 (tx1,2) 4 (tx1,2,3,4)
679 : : // tx3 3 (tx1,2,3) 4 (tx1,2,3,4)
680 : : // tx4 3 (tx1,2,4) 4 (tx1,2,3,4)
681 [ + - ]: 1 : pool.GetTransactionAncestry(tx1->GetHash(), ancestors, descendants);
682 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 1ULL);
683 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(descendants, 4ULL);
684 [ + - ]: 1 : pool.GetTransactionAncestry(tx2->GetHash(), ancestors, descendants);
685 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 2ULL);
686 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(descendants, 4ULL);
687 [ + - ]: 1 : pool.GetTransactionAncestry(tx3->GetHash(), ancestors, descendants);
688 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 3ULL);
689 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(descendants, 4ULL);
690 [ + - ]: 1 : pool.GetTransactionAncestry(tx4->GetHash(), ancestors, descendants);
691 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 3ULL);
692 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(descendants, 4ULL);
693 : :
694 : : /* Make an alternate branch that is longer and connect it to tx3 */
695 : : //
696 : : // [ty1].0 <- [ty2].0 <- [ty3].0 <- [ty4].0 <- [ty5].0
697 : : // |
698 : : // [tx1].0 <- [tx2].0 <- [tx3].0 <- [ty6] --->--/
699 : : // |
700 : : // \---1 <- [tx4]
701 : : //
702 : 1 : CTransactionRef ty1, ty2, ty3, ty4, ty5;
703 : 1 : CTransactionRef* ty[5] = {&ty1, &ty2, &ty3, &ty4, &ty5};
704 : 1 : CAmount v = 5 * COIN;
705 [ + + ]: 6 : for (uint64_t i = 0; i < 5; i++) {
706 : 5 : CTransactionRef& tyi = *ty[i];
707 [ + + + - : 22 : tyi = make_tx(/*output_values=*/{v}, /*inputs=*/i > 0 ? std::vector<CTransactionRef>{*ty[i - 1]} : std::vector<CTransactionRef>{});
+ - + - -
+ + + + +
+ - - - -
- - - ]
708 : 5 : v -= 50 * CENT;
709 [ + - + - ]: 5 : pool.addUnchecked(entry.Fee(10000LL).FromTx(tyi));
710 [ + - ]: 5 : pool.GetTransactionAncestry(tyi->GetHash(), ancestors, descendants);
711 [ + - + - ]: 5 : BOOST_CHECK_EQUAL(ancestors, i+1);
712 [ + - + - ]: 5 : BOOST_CHECK_EQUAL(descendants, i+1);
713 : : }
714 [ + - + - : 5 : CTransactionRef ty6 = make_tx(/*output_values=*/{5 * COIN}, /*inputs=*/{tx3, ty5});
+ - + + +
- - - -
- ]
715 [ + - + - ]: 1 : pool.addUnchecked(entry.Fee(10000LL).FromTx(ty6));
716 : :
717 : : // Ancestors / descendants should be:
718 : : // transaction ancestors descendants
719 : : // ============ =================== ===========
720 : : // tx1 1 (tx1) 5 (tx1,2,3,4, ty6)
721 : : // tx2 2 (tx1,2) 5 (tx1,2,3,4, ty6)
722 : : // tx3 3 (tx1,2,3) 5 (tx1,2,3,4, ty6)
723 : : // tx4 3 (tx1,2,4) 5 (tx1,2,3,4, ty6)
724 : : // ty1 1 (ty1) 6 (ty1,2,3,4,5,6)
725 : : // ty2 2 (ty1,2) 6 (ty1,2,3,4,5,6)
726 : : // ty3 3 (ty1,2,3) 6 (ty1,2,3,4,5,6)
727 : : // ty4 4 (y1234) 6 (ty1,2,3,4,5,6)
728 : : // ty5 5 (y12345) 6 (ty1,2,3,4,5,6)
729 : : // ty6 9 (tx123, ty123456) 6 (ty1,2,3,4,5,6)
730 [ + - ]: 1 : pool.GetTransactionAncestry(tx1->GetHash(), ancestors, descendants);
731 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 1ULL);
732 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(descendants, 5ULL);
733 [ + - ]: 1 : pool.GetTransactionAncestry(tx2->GetHash(), ancestors, descendants);
734 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 2ULL);
735 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(descendants, 5ULL);
736 [ + - ]: 1 : pool.GetTransactionAncestry(tx3->GetHash(), ancestors, descendants);
737 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 3ULL);
738 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(descendants, 5ULL);
739 [ + - ]: 1 : pool.GetTransactionAncestry(tx4->GetHash(), ancestors, descendants);
740 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 3ULL);
741 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(descendants, 5ULL);
742 [ + - ]: 1 : pool.GetTransactionAncestry(ty1->GetHash(), ancestors, descendants);
743 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 1ULL);
744 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(descendants, 6ULL);
745 [ + - ]: 1 : pool.GetTransactionAncestry(ty2->GetHash(), ancestors, descendants);
746 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 2ULL);
747 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(descendants, 6ULL);
748 [ + - ]: 1 : pool.GetTransactionAncestry(ty3->GetHash(), ancestors, descendants);
749 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 3ULL);
750 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(descendants, 6ULL);
751 [ + - ]: 1 : pool.GetTransactionAncestry(ty4->GetHash(), ancestors, descendants);
752 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 4ULL);
753 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(descendants, 6ULL);
754 [ + - ]: 1 : pool.GetTransactionAncestry(ty5->GetHash(), ancestors, descendants);
755 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 5ULL);
756 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(descendants, 6ULL);
757 [ + - ]: 1 : pool.GetTransactionAncestry(ty6->GetHash(), ancestors, descendants);
758 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 9ULL);
759 [ + - + - : 1 : BOOST_CHECK_EQUAL(descendants, 6ULL);
+ - ]
760 [ + - + - : 25 : }
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - ]
761 : :
762 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(MempoolAncestryTestsDiamond)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
763 : : {
764 : 1 : size_t ancestors, descendants;
765 : :
766 : 1 : CTxMemPool& pool = *Assert(m_node.mempool);
767 [ + - ]: 1 : LOCK2(::cs_main, pool.cs);
768 : 1 : TestMemPoolEntryHelper entry;
769 : :
770 : : /* Ancestors represented more than once ("diamond") */
771 : : //
772 : : // [ta].0 <- [tb].0 -----<------- [td].0
773 : : // | |
774 : : // \---1 <- [tc].0 --<--/
775 : : //
776 : 1 : CTransactionRef ta, tb, tc, td;
777 [ + - + - : 2 : ta = make_tx(/*output_values=*/{10 * COIN});
- + ]
778 [ + - + - : 4 : tb = make_tx(/*output_values=*/{5 * COIN, 3 * COIN}, /*inputs=*/ {ta});
+ - - + +
+ + - - -
- - ]
779 [ + - + - : 5 : tc = make_tx(/*output_values=*/{2 * COIN}, /*inputs=*/{tb}, /*input_indices=*/{1});
+ - - + +
+ + - + -
- - - - ]
780 [ + - + - : 6 : td = make_tx(/*output_values=*/{6 * COIN}, /*inputs=*/{tb, tc}, /*input_indices=*/{0, 0});
+ - - + +
+ + - + -
- - - - ]
781 [ + - + - ]: 1 : pool.addUnchecked(entry.Fee(10000LL).FromTx(ta));
782 [ + - + - ]: 1 : pool.addUnchecked(entry.Fee(10000LL).FromTx(tb));
783 [ + - + - ]: 1 : pool.addUnchecked(entry.Fee(10000LL).FromTx(tc));
784 [ + - + - ]: 1 : pool.addUnchecked(entry.Fee(10000LL).FromTx(td));
785 : :
786 : : // Ancestors / descendants should be:
787 : : // transaction ancestors descendants
788 : : // ============ =================== ===========
789 : : // ta 1 (ta 4 (ta,tb,tc,td)
790 : : // tb 2 (ta,tb) 4 (ta,tb,tc,td)
791 : : // tc 3 (ta,tb,tc) 4 (ta,tb,tc,td)
792 : : // td 4 (ta,tb,tc,td) 4 (ta,tb,tc,td)
793 [ + - ]: 1 : pool.GetTransactionAncestry(ta->GetHash(), ancestors, descendants);
794 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 1ULL);
795 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(descendants, 4ULL);
796 [ + - ]: 1 : pool.GetTransactionAncestry(tb->GetHash(), ancestors, descendants);
797 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 2ULL);
798 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(descendants, 4ULL);
799 [ + - ]: 1 : pool.GetTransactionAncestry(tc->GetHash(), ancestors, descendants);
800 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 3ULL);
801 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(descendants, 4ULL);
802 [ + - ]: 1 : pool.GetTransactionAncestry(td->GetHash(), ancestors, descendants);
803 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ancestors, 4ULL);
804 [ + - + - : 1 : BOOST_CHECK_EQUAL(descendants, 4ULL);
+ - ]
805 [ + - + - : 13 : }
+ - + - +
- + - + -
+ - + - +
- + - +
- ]
806 : :
807 : : BOOST_AUTO_TEST_SUITE_END()
|
