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 "txmempool.h"
6 : #include "util.h"
7 :
8 : #include "test/test_bitcoin.h"
9 :
10 : #include <boost/test/unit_test.hpp>
11 : #include <list>
12 : #include <vector>
13 :
14 1 : BOOST_FIXTURE_TEST_SUITE(mempool_tests, TestingSetup)
15 :
16 6 : BOOST_AUTO_TEST_CASE(MempoolRemoveTest)
17 : {
18 : // Test CTxMemPool::remove functionality
19 :
20 : // Parent transaction with three children,
21 : // and three grand-children:
22 1 : CMutableTransaction txParent;
23 2 : txParent.vin.resize(1);
24 2 : txParent.vin[0].scriptSig = CScript() << OP_11;
25 2 : txParent.vout.resize(3);
26 4 : for (int i = 0; i < 3; i++)
27 : {
28 9 : txParent.vout[i].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
29 6 : txParent.vout[i].nValue = 33000LL;
30 : }
31 7 : CMutableTransaction txChild[3];
32 3 : for (int i = 0; i < 3; i++)
33 : {
34 6 : txChild[i].vin.resize(1);
35 6 : 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 6 : txChild[i].vout.resize(1);
39 6 : txChild[i].vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
40 3 : txChild[i].vout[0].nValue = 11000LL;
41 : }
42 7 : CMutableTransaction txGrandChild[3];
43 3 : for (int i = 0; i < 3; i++)
44 : {
45 6 : txGrandChild[i].vin.resize(1);
46 6 : 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 6 : txGrandChild[i].vout.resize(1);
50 6 : txGrandChild[i].vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
51 3 : txGrandChild[i].vout[0].nValue = 11000LL;
52 : }
53 :
54 :
55 3 : CTxMemPool testPool(CFeeRate(0));
56 : std::list<CTransaction> removed;
57 :
58 : // Nothing in pool, remove should do nothing:
59 2 : testPool.remove(txParent, removed, true);
60 6 : BOOST_CHECK_EQUAL(removed.size(), 0);
61 :
62 : // Just the parent:
63 3 : testPool.addUnchecked(txParent.GetHash(), CTxMemPoolEntry(txParent, 0, 0, 0.0, 1));
64 2 : testPool.remove(txParent, removed, true);
65 6 : BOOST_CHECK_EQUAL(removed.size(), 1);
66 : removed.clear();
67 :
68 : // Parent, children, grandchildren:
69 3 : testPool.addUnchecked(txParent.GetHash(), CTxMemPoolEntry(txParent, 0, 0, 0.0, 1));
70 4 : for (int i = 0; i < 3; i++)
71 : {
72 9 : testPool.addUnchecked(txChild[i].GetHash(), CTxMemPoolEntry(txChild[i], 0, 0, 0.0, 1));
73 9 : testPool.addUnchecked(txGrandChild[i].GetHash(), CTxMemPoolEntry(txGrandChild[i], 0, 0, 0.0, 1));
74 : }
75 : // Remove Child[0], GrandChild[0] should be removed:
76 2 : testPool.remove(txChild[0], removed, true);
77 6 : BOOST_CHECK_EQUAL(removed.size(), 2);
78 : removed.clear();
79 : // ... make sure grandchild and child are gone:
80 2 : testPool.remove(txGrandChild[0], removed, true);
81 6 : BOOST_CHECK_EQUAL(removed.size(), 0);
82 2 : testPool.remove(txChild[0], removed, true);
83 6 : BOOST_CHECK_EQUAL(removed.size(), 0);
84 : // Remove parent, all children/grandchildren should go:
85 2 : testPool.remove(txParent, removed, true);
86 6 : BOOST_CHECK_EQUAL(removed.size(), 5);
87 5 : BOOST_CHECK_EQUAL(testPool.size(), 0);
88 : removed.clear();
89 :
90 : // Add children and grandchildren, but NOT the parent (simulate the parent being in a block)
91 4 : for (int i = 0; i < 3; i++)
92 : {
93 9 : testPool.addUnchecked(txChild[i].GetHash(), CTxMemPoolEntry(txChild[i], 0, 0, 0.0, 1));
94 9 : testPool.addUnchecked(txGrandChild[i].GetHash(), CTxMemPoolEntry(txGrandChild[i], 0, 0, 0.0, 1));
95 : }
96 : // Now remove the parent, as might happen if a block-re-org occurs but the parent cannot be
97 : // put into the mempool (maybe because it is non-standard):
98 2 : testPool.remove(txParent, removed, true);
99 6 : BOOST_CHECK_EQUAL(removed.size(), 6);
100 5 : BOOST_CHECK_EQUAL(testPool.size(), 0);
101 : removed.clear();
102 1 : }
103 :
104 7 : void CheckSort(CTxMemPool &pool, std::vector<std::string> &sortedOrder)
105 : {
106 42 : BOOST_CHECK_EQUAL(pool.size(), sortedOrder.size());
107 21 : CTxMemPool::indexed_transaction_set::nth_index<1>::type::iterator it = pool.mapTx.get<1>().begin();
108 7 : int count=0;
109 244 : for (; it != pool.mapTx.get<1>().end(); ++it, ++count) {
110 486 : BOOST_CHECK_EQUAL(it->GetTx().GetHash().ToString(), sortedOrder[count]);
111 : }
112 7 : }
113 :
114 6 : BOOST_AUTO_TEST_CASE(MempoolIndexingTest)
115 : {
116 2 : CTxMemPool pool(CFeeRate(0));
117 :
118 : /* 3rd highest fee */
119 1 : CMutableTransaction tx1 = CMutableTransaction();
120 2 : tx1.vout.resize(1);
121 2 : tx1.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
122 1 : tx1.vout[0].nValue = 10 * COIN;
123 3 : pool.addUnchecked(tx1.GetHash(), CTxMemPoolEntry(tx1, 10000LL, 0, 10.0, 1, true));
124 :
125 : /* highest fee */
126 1 : CMutableTransaction tx2 = CMutableTransaction();
127 2 : tx2.vout.resize(1);
128 2 : tx2.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
129 1 : tx2.vout[0].nValue = 2 * COIN;
130 3 : pool.addUnchecked(tx2.GetHash(), CTxMemPoolEntry(tx2, 20000LL, 0, 9.0, 1, true));
131 :
132 : /* lowest fee */
133 1 : CMutableTransaction tx3 = CMutableTransaction();
134 2 : tx3.vout.resize(1);
135 2 : tx3.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
136 1 : tx3.vout[0].nValue = 5 * COIN;
137 3 : pool.addUnchecked(tx3.GetHash(), CTxMemPoolEntry(tx3, 0LL, 0, 100.0, 1, true));
138 :
139 : /* 2nd highest fee */
140 1 : CMutableTransaction tx4 = CMutableTransaction();
141 2 : tx4.vout.resize(1);
142 2 : tx4.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
143 1 : tx4.vout[0].nValue = 6 * COIN;
144 3 : pool.addUnchecked(tx4.GetHash(), CTxMemPoolEntry(tx4, 15000LL, 0, 1.0, 1, true));
145 :
146 : /* equal fee rate to tx1, but newer */
147 1 : CMutableTransaction tx5 = CMutableTransaction();
148 2 : tx5.vout.resize(1);
149 2 : tx5.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
150 1 : tx5.vout[0].nValue = 11 * COIN;
151 3 : pool.addUnchecked(tx5.GetHash(), CTxMemPoolEntry(tx5, 10000LL, 1, 10.0, 1, true));
152 5 : BOOST_CHECK_EQUAL(pool.size(), 5);
153 :
154 1 : std::vector<std::string> sortedOrder;
155 2 : sortedOrder.resize(5);
156 2 : sortedOrder[0] = tx2.GetHash().ToString(); // 20000
157 3 : sortedOrder[1] = tx4.GetHash().ToString(); // 15000
158 3 : sortedOrder[2] = tx1.GetHash().ToString(); // 10000
159 3 : sortedOrder[3] = tx5.GetHash().ToString(); // 10000
160 3 : sortedOrder[4] = tx3.GetHash().ToString(); // 0
161 1 : CheckSort(pool, sortedOrder);
162 :
163 : /* low fee but with high fee child */
164 : /* tx6 -> tx7 -> tx8, tx9 -> tx10 */
165 1 : CMutableTransaction tx6 = CMutableTransaction();
166 2 : tx6.vout.resize(1);
167 2 : tx6.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
168 1 : tx6.vout[0].nValue = 20 * COIN;
169 3 : pool.addUnchecked(tx6.GetHash(), CTxMemPoolEntry(tx6, 0LL, 1, 10.0, 1, true));
170 5 : BOOST_CHECK_EQUAL(pool.size(), 6);
171 : // Check that at this point, tx6 is sorted low
172 2 : sortedOrder.push_back(tx6.GetHash().ToString());
173 1 : CheckSort(pool, sortedOrder);
174 :
175 : CTxMemPool::setEntries setAncestors;
176 2 : setAncestors.insert(pool.mapTx.find(tx6.GetHash()));
177 1 : CMutableTransaction tx7 = CMutableTransaction();
178 2 : tx7.vin.resize(1);
179 2 : tx7.vin[0].prevout = COutPoint(tx6.GetHash(), 0);
180 2 : tx7.vin[0].scriptSig = CScript() << OP_11;
181 2 : tx7.vout.resize(2);
182 2 : tx7.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
183 1 : tx7.vout[0].nValue = 10 * COIN;
184 2 : tx7.vout[1].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
185 1 : tx7.vout[1].nValue = 1 * COIN;
186 :
187 : CTxMemPool::setEntries setAncestorsCalculated;
188 : std::string dummy;
189 2 : CTxMemPoolEntry entry7(tx7, 2000000LL, 1, 10.0, 1, true);
190 5 : BOOST_CHECK_EQUAL(pool.CalculateMemPoolAncestors(entry7, setAncestorsCalculated, 100, 1000000, 1000, 1000000, dummy), true);
191 5 : BOOST_CHECK(setAncestorsCalculated == setAncestors);
192 :
193 3 : pool.addUnchecked(tx7.GetHash(), CTxMemPoolEntry(tx7, 2000000LL, 1, 10.0, 1, true), setAncestors);
194 5 : BOOST_CHECK_EQUAL(pool.size(), 7);
195 :
196 : // Now tx6 should be sorted higher (high fee child): tx7, tx6, tx2, ...
197 1 : sortedOrder.erase(sortedOrder.end()-1);
198 3 : sortedOrder.insert(sortedOrder.begin(), tx6.GetHash().ToString());
199 3 : sortedOrder.insert(sortedOrder.begin(), tx7.GetHash().ToString());
200 1 : CheckSort(pool, sortedOrder);
201 :
202 : /* low fee child of tx7 */
203 1 : CMutableTransaction tx8 = CMutableTransaction();
204 2 : tx8.vin.resize(1);
205 2 : tx8.vin[0].prevout = COutPoint(tx7.GetHash(), 0);
206 2 : tx8.vin[0].scriptSig = CScript() << OP_11;
207 2 : tx8.vout.resize(1);
208 2 : tx8.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
209 1 : tx8.vout[0].nValue = 10 * COIN;
210 2 : setAncestors.insert(pool.mapTx.find(tx7.GetHash()));
211 3 : pool.addUnchecked(tx8.GetHash(), CTxMemPoolEntry(tx8, 0LL, 2, 10.0, 1, true), setAncestors);
212 :
213 : // Now tx8 should be sorted low, but tx6/tx both high
214 2 : sortedOrder.push_back(tx8.GetHash().ToString());
215 1 : CheckSort(pool, sortedOrder);
216 :
217 : /* low fee child of tx7 */
218 1 : CMutableTransaction tx9 = CMutableTransaction();
219 2 : tx9.vin.resize(1);
220 2 : tx9.vin[0].prevout = COutPoint(tx7.GetHash(), 1);
221 2 : tx9.vin[0].scriptSig = CScript() << OP_11;
222 2 : tx9.vout.resize(1);
223 2 : tx9.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
224 1 : tx9.vout[0].nValue = 1 * COIN;
225 3 : pool.addUnchecked(tx9.GetHash(), CTxMemPoolEntry(tx9, 0LL, 3, 10.0, 1, true), setAncestors);
226 :
227 : // tx9 should be sorted low
228 5 : BOOST_CHECK_EQUAL(pool.size(), 9);
229 2 : sortedOrder.push_back(tx9.GetHash().ToString());
230 1 : CheckSort(pool, sortedOrder);
231 :
232 2 : std::vector<std::string> snapshotOrder = sortedOrder;
233 :
234 2 : setAncestors.insert(pool.mapTx.find(tx8.GetHash()));
235 2 : setAncestors.insert(pool.mapTx.find(tx9.GetHash()));
236 : /* tx10 depends on tx8 and tx9 and has a high fee*/
237 1 : CMutableTransaction tx10 = CMutableTransaction();
238 2 : tx10.vin.resize(2);
239 2 : tx10.vin[0].prevout = COutPoint(tx8.GetHash(), 0);
240 2 : tx10.vin[0].scriptSig = CScript() << OP_11;
241 2 : tx10.vin[1].prevout = COutPoint(tx9.GetHash(), 0);
242 2 : tx10.vin[1].scriptSig = CScript() << OP_11;
243 2 : tx10.vout.resize(1);
244 2 : tx10.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
245 1 : tx10.vout[0].nValue = 10 * COIN;
246 :
247 : setAncestorsCalculated.clear();
248 2 : CTxMemPoolEntry entry10(tx10, 200000LL, 4, 10.0, 1, true);
249 5 : BOOST_CHECK_EQUAL(pool.CalculateMemPoolAncestors(entry10, setAncestorsCalculated, 100, 1000000, 1000, 1000000, dummy), true);
250 8 : BOOST_CHECK(setAncestorsCalculated == setAncestors);
251 :
252 3 : pool.addUnchecked(tx10.GetHash(), CTxMemPoolEntry(tx10, 200000LL, 4, 10.0, 1, true), setAncestors);
253 :
254 : /**
255 : * tx8 and tx9 should both now be sorted higher
256 : * Final order after tx10 is added:
257 : *
258 : * tx7 = 2.2M (4 txs)
259 : * tx6 = 2.2M (5 txs)
260 : * tx10 = 200k (1 tx)
261 : * tx8 = 200k (2 txs)
262 : * tx9 = 200k (2 txs)
263 : * tx2 = 20000 (1)
264 : * tx4 = 15000 (1)
265 : * tx1 = 10000 (1)
266 : * tx5 = 10000 (1)
267 : * tx3 = 0 (1)
268 : */
269 1 : sortedOrder.erase(sortedOrder.end()-2, sortedOrder.end()); // take out tx8, tx9 from the end
270 4 : sortedOrder.insert(sortedOrder.begin()+2, tx10.GetHash().ToString()); // tx10 is after tx6
271 4 : sortedOrder.insert(sortedOrder.begin()+3, tx9.GetHash().ToString());
272 4 : sortedOrder.insert(sortedOrder.begin()+3, tx8.GetHash().ToString());
273 1 : CheckSort(pool, sortedOrder);
274 :
275 : // there should be 10 transactions in the mempool
276 5 : BOOST_CHECK_EQUAL(pool.size(), 10);
277 :
278 : // Now try removing tx10 and verify the sort order returns to normal
279 : std::list<CTransaction> removed;
280 3 : pool.remove(pool.mapTx.find(tx10.GetHash())->GetTx(), removed, true);
281 2 : CheckSort(pool, snapshotOrder);
282 1 : }
283 :
284 3 : BOOST_AUTO_TEST_SUITE_END()
|
