Branch data Line data Source code
1 : : // Copyright (c) 2023-present The Bitcoin Core developers
2 : : // Distributed under the MIT software license, see the accompanying
3 : : // file COPYING or https://opensource.org/license/mit/.
4 : :
5 : : #include <txgraph.h>
6 : :
7 : : #include <random.h>
8 : :
9 : : #include <boost/test/unit_test.hpp>
10 : :
11 : : #include <memory>
12 : : #include <vector>
13 : :
14 : : BOOST_AUTO_TEST_SUITE(txgraph_tests)
15 : :
16 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(txgraph_trim_zigzag)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
17 : : {
18 : : // T T T T T T T T T T T T T T (50 T's)
19 : : // \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ /
20 : : // \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ /
21 : : // B B B B B B B B B B B B B (49 B's)
22 : : //
23 : : /** The maximum cluster count used in this test. */
24 : 1 : static constexpr int MAX_CLUSTER_COUNT = 50;
25 : : /** The number of "bottom" transactions, which are in the mempool already. */
26 : 1 : static constexpr int NUM_BOTTOM_TX = 49;
27 : : /** The number of "top" transactions, which come from disconnected blocks. These are re-added
28 : : * to the mempool and, while connecting them to the already-in-mempool transactions, we
29 : : * discover the resulting cluster is oversized. */
30 : 1 : static constexpr int NUM_TOP_TX = 50;
31 : : /** The total number of transactions in the test. */
32 : 1 : static constexpr int NUM_TOTAL_TX = NUM_BOTTOM_TX + NUM_TOP_TX;
33 : 1 : static_assert(NUM_TOTAL_TX > MAX_CLUSTER_COUNT);
34 : : /** Set a very large cluster size limit so that only the count limit is triggered. */
35 : 1 : static constexpr int32_t MAX_CLUSTER_SIZE = 100'000 * 100;
36 : :
37 : : // Create a new graph for the test.
38 : 1 : auto graph = MakeTxGraph(MAX_CLUSTER_COUNT, MAX_CLUSTER_SIZE);
39 : :
40 : : // Add all transactions and store their Refs.
41 : 1 : std::vector<TxGraph::Ref> refs;
42 [ + - ]: 1 : refs.reserve(NUM_TOTAL_TX);
43 : : // First all bottom transactions: the i'th bottom transaction is at position i.
44 [ + + ]: 50 : for (unsigned int i = 0; i < NUM_BOTTOM_TX; ++i) {
45 [ + - ]: 49 : refs.push_back(graph->AddTransaction(FeePerWeight{200 - i, 100}));
46 : : }
47 : : // Then all top transactions: the i'th top transaction is at position NUM_BOTTOM_TX + i.
48 [ + + ]: 51 : for (unsigned int i = 0; i < NUM_TOP_TX; ++i) {
49 [ + - ]: 50 : refs.push_back(graph->AddTransaction(FeePerWeight{100 - i, 100}));
50 : : }
51 : :
52 : : // Create the zigzag dependency structure.
53 : : // Each transaction in the bottom row depends on two adjacent transactions from the top row.
54 [ + - ]: 1 : graph->SanityCheck();
55 [ + + ]: 50 : for (unsigned int i = 0; i < NUM_BOTTOM_TX; ++i) {
56 : 49 : graph->AddDependency(/*parent=*/refs[NUM_BOTTOM_TX + i], /*child=*/refs[i]);
57 : 49 : graph->AddDependency(/*parent=*/refs[NUM_BOTTOM_TX + i + 1], /*child=*/refs[i]);
58 : : }
59 : :
60 : : // Check that the graph is now oversized. This also forces the graph to
61 : : // group clusters and compute the oversized status.
62 [ + - ]: 1 : graph->SanityCheck();
63 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(graph->GetTransactionCount(), NUM_TOTAL_TX);
64 [ + - + - ]: 2 : BOOST_CHECK(graph->IsOversized(/*main_only=*/false));
65 : :
66 : : // Call Trim() to remove transactions and bring the cluster back within limits.
67 : 1 : auto removed_refs = graph->Trim();
68 [ + - ]: 1 : graph->SanityCheck();
69 [ + - + - : 2 : BOOST_CHECK(!graph->IsOversized(/*main_only=*/false));
+ - ]
70 : :
71 : : // We only need to trim the middle bottom transaction to end up with 2 clusters each within cluster limits.
72 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(removed_refs.size(), 1);
73 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(graph->GetTransactionCount(), MAX_CLUSTER_COUNT * 2 - 2);
74 [ + + ]: 100 : for (unsigned int i = 0; i < refs.size(); ++i) {
75 [ + - + - ]: 99 : BOOST_CHECK_EQUAL(graph->Exists(refs[i]), i != (NUM_BOTTOM_TX / 2));
76 : : }
77 : 1 : }
78 : :
79 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(txgraph_trim_flower)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
80 : : {
81 : : // We will build an oversized flower-shaped graph: all transactions are spent by 1 descendant.
82 : : //
83 : : // T T T T T T T T (100 T's)
84 : : // | | | | | | | |
85 : : // | | | | | | | |
86 : : // \---+---+---+-+-+---+---+---/
87 : : // |
88 : : // B (1 B)
89 : : //
90 : : /** The maximum cluster count used in this test. */
91 : 1 : static constexpr int MAX_CLUSTER_COUNT = 50;
92 : : /** The number of "top" transactions, which come from disconnected blocks. These are re-added
93 : : * to the mempool and, connecting them to the already-in-mempool transactions, we discover the
94 : : * resulting cluster is oversized. */
95 : 1 : static constexpr int NUM_TOP_TX = MAX_CLUSTER_COUNT * 2;
96 : : /** The total number of transactions in this test. */
97 : 1 : static constexpr int NUM_TOTAL_TX = NUM_TOP_TX + 1;
98 : : /** Set a very large cluster size limit so that only the count limit is triggered. */
99 : 1 : static constexpr int32_t MAX_CLUSTER_SIZE = 100'000 * 100;
100 : :
101 : 1 : auto graph = MakeTxGraph(MAX_CLUSTER_COUNT, MAX_CLUSTER_SIZE);
102 : :
103 : : // Add all transactions and store their Refs.
104 : 1 : std::vector<TxGraph::Ref> refs;
105 [ + - ]: 1 : refs.reserve(NUM_TOTAL_TX);
106 : :
107 : : // Add all transactions. They are in individual clusters.
108 [ + - ]: 1 : refs.push_back(graph->AddTransaction({1, 100}));
109 [ + + ]: 101 : for (unsigned int i = 0; i < NUM_TOP_TX; ++i) {
110 [ + - ]: 100 : refs.push_back(graph->AddTransaction(FeePerWeight{500 + i, 100}));
111 : : }
112 [ + - ]: 1 : graph->SanityCheck();
113 : :
114 : : // The 0th transaction spends all the top transactions.
115 [ + + ]: 101 : for (unsigned int i = 1; i < NUM_TOTAL_TX; ++i) {
116 : 100 : graph->AddDependency(/*parent=*/refs[i], /*child=*/refs[0]);
117 : : }
118 [ + - ]: 1 : graph->SanityCheck();
119 : :
120 : : // Check that the graph is now oversized. This also forces the graph to
121 : : // group clusters and compute the oversized status.
122 [ + - + - ]: 2 : BOOST_CHECK(graph->IsOversized(/*main_only=*/false));
123 : :
124 : : // Call Trim() to remove transactions and bring the cluster back within limits.
125 : 1 : auto removed_refs = graph->Trim();
126 [ + - ]: 1 : graph->SanityCheck();
127 [ + - + - : 2 : BOOST_CHECK(!graph->IsOversized(/*main_only=*/false));
+ - ]
128 : :
129 : : // Since only the bottom transaction connects these clusters, we only need to remove it.
130 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(removed_refs.size(), 1);
131 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(graph->GetTransactionCount(false), MAX_CLUSTER_COUNT * 2);
132 [ + - + - ]: 2 : BOOST_CHECK(!graph->Exists(refs[0]));
133 [ + + ]: 101 : for (unsigned int i = 1; i < refs.size(); ++i) {
134 [ + - + - ]: 200 : BOOST_CHECK(graph->Exists(refs[i]));
135 : : }
136 : 1 : }
137 : :
138 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(txgraph_trim_huge)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
139 : : {
140 : : // The from-block transactions consist of 1000 fully linear clusters, each with 64
141 : : // transactions. The mempool contains 11 transactions that together merge all of these into
142 : : // a single cluster.
143 : : //
144 : : // (1000 chains of 64 transactions, 64000 T's total)
145 : : //
146 : : // T T T T T T T T
147 : : // | | | | | | | |
148 : : // T T T T T T T T
149 : : // | | | | | | | |
150 : : // T T T T T T T T
151 : : // | | | | | | | |
152 : : // T T T T T T T T
153 : : // (64 long) (64 long) (64 long) (64 long) (64 long) (64 long) (64 long) (64 long)
154 : : // | | | | | | | |
155 : : // | | / \ | / \ | | /
156 : : // \----------+--------/ \--------+--------/ \--------+-----+----+--------/
157 : : // | | |
158 : : // B B B
159 : : //
160 : : // (11 B's, each attaching to up to 100 chains of 64 T's)
161 : : //
162 : : /** The maximum cluster count used in this test. */
163 : 1 : static constexpr int MAX_CLUSTER_COUNT = 64;
164 : : /** The number of "top" (from-block) chains of transactions. */
165 : 1 : static constexpr int NUM_TOP_CHAINS = 1000;
166 : : /** The number of transactions per top chain. */
167 : 1 : static constexpr int NUM_TX_PER_TOP_CHAIN = MAX_CLUSTER_COUNT;
168 : : /** The (maximum) number of dependencies per bottom transaction. */
169 : 1 : static constexpr int NUM_DEPS_PER_BOTTOM_TX = 100;
170 : : /** The number of bottom transactions that are expected to be created. */
171 : 1 : static constexpr int NUM_BOTTOM_TX = (NUM_TOP_CHAINS - 1 + (NUM_DEPS_PER_BOTTOM_TX - 2)) / (NUM_DEPS_PER_BOTTOM_TX - 1);
172 : : /** The total number of transactions created in this test. */
173 : 1 : static constexpr int NUM_TOTAL_TX = NUM_TOP_CHAINS * NUM_TX_PER_TOP_CHAIN + NUM_BOTTOM_TX;
174 : : /** Set a very large cluster size limit so that only the count limit is triggered. */
175 : 1 : static constexpr int32_t MAX_CLUSTER_SIZE = 100'000 * 100;
176 : :
177 : : /** Refs to all top transactions. */
178 : 1 : std::vector<TxGraph::Ref> top_refs;
179 : : /** Refs to all bottom transactions. */
180 : 1 : std::vector<TxGraph::Ref> bottom_refs;
181 : : /** Indexes into top_refs for some transaction of each component, in arbitrary order.
182 : : * Initially these are the last transactions in each chains, but as bottom transactions are
183 : : * added, entries will be removed when they get merged, and randomized. */
184 : 1 : std::vector<size_t> top_components;
185 : :
186 : 1 : FastRandomContext rng;
187 : 1 : auto graph = MakeTxGraph(MAX_CLUSTER_COUNT, MAX_CLUSTER_SIZE);
188 : :
189 : : // Construct the top chains.
190 [ + + ]: 1001 : for (int chain = 0; chain < NUM_TOP_CHAINS; ++chain) {
191 [ + + ]: 65000 : for (int chaintx = 0; chaintx < NUM_TX_PER_TOP_CHAIN; ++chaintx) {
192 : : // Use random fees, size 1.
193 : 64000 : int64_t fee = rng.randbits<27>() + 100;
194 : 64000 : FeePerWeight feerate{fee, 1};
195 [ + - ]: 64000 : top_refs.push_back(graph->AddTransaction(feerate));
196 : : // Add internal dependencies linked the chain transactions together.
197 [ + + ]: 64000 : if (chaintx > 0) {
198 : 63000 : graph->AddDependency(*(top_refs.rbegin()), *(top_refs.rbegin() + 1));
199 : : }
200 : : }
201 : : // Remember the last transaction in each chain, to attach the bottom transactions to.
202 [ + - ]: 1000 : top_components.push_back(top_refs.size() - 1);
203 : : }
204 [ + - ]: 1 : graph->SanityCheck();
205 : :
206 : : // Not oversized so far (just 1000 clusters of 64).
207 [ + - + - ]: 2 : BOOST_CHECK(!graph->IsOversized());
208 : :
209 : : // Construct the bottom transactions, and dependencies to the top chains.
210 [ + + ]: 12 : while (top_components.size() > 1) {
211 : : // Construct the transaction.
212 : 11 : int64_t fee = rng.randbits<27>() + 100;
213 : 11 : FeePerWeight feerate{fee, 1};
214 : 11 : auto bottom_tx = graph->AddTransaction(feerate);
215 : : // Determine the number of dependencies this transaction will have.
216 [ + + ]: 11 : int deps = std::min<int>(NUM_DEPS_PER_BOTTOM_TX, top_components.size());
217 [ + + ]: 1021 : for (int dep = 0; dep < deps; ++dep) {
218 : : // Pick an transaction in top_components to attach to.
219 : 1010 : auto idx = rng.randrange(top_components.size());
220 : : // Add dependency.
221 : 1010 : graph->AddDependency(/*parent=*/top_refs[top_components[idx]], /*child=*/bottom_tx);
222 : : // Unless this is the last dependency being added, remove from top_components, as
223 : : // the component will be merged with that one.
224 [ + + ]: 1010 : if (dep < deps - 1) {
225 : : // Move entry top the back.
226 [ + + ]: 999 : if (idx != top_components.size() - 1) std::swap(top_components.back(), top_components[idx]);
227 : : // And pop it.
228 : 999 : top_components.pop_back();
229 : : }
230 : : }
231 [ + - ]: 11 : bottom_refs.push_back(std::move(bottom_tx));
232 : 11 : }
233 [ + - ]: 1 : graph->SanityCheck();
234 : :
235 : : // Now we are oversized (one cluster of 64011).
236 [ + - + - ]: 2 : BOOST_CHECK(graph->IsOversized());
237 : 1 : const auto total_tx_count = graph->GetTransactionCount();
238 [ + - + - : 2 : BOOST_CHECK(total_tx_count == top_refs.size() + bottom_refs.size());
+ - ]
239 [ + - + - ]: 2 : BOOST_CHECK(total_tx_count == NUM_TOTAL_TX);
240 : :
241 : : // Call Trim() to remove transactions and bring the cluster back within limits.
242 : 1 : auto removed_refs = graph->Trim();
243 [ + - + - : 2 : BOOST_CHECK(!graph->IsOversized());
+ - ]
244 [ + - + - : 2 : BOOST_CHECK(removed_refs.size() == total_tx_count - graph->GetTransactionCount());
+ - ]
245 [ + - ]: 1 : graph->SanityCheck();
246 : :
247 : : // At least 99% of chains must survive.
248 [ + - + - ]: 2 : BOOST_CHECK(graph->GetTransactionCount() >= (NUM_TOP_CHAINS * NUM_TX_PER_TOP_CHAIN * 99) / 100);
249 : 1 : }
250 : :
251 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(txgraph_trim_big_singletons)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
252 : : {
253 : : // Mempool consists of 100 singleton clusters; there are no dependencies. Some are oversized. Trim() should remove all of the oversized ones.
254 : 1 : static constexpr int MAX_CLUSTER_COUNT = 64;
255 : 1 : static constexpr int32_t MAX_CLUSTER_SIZE = 100'000;
256 : 1 : static constexpr int NUM_TOTAL_TX = 100;
257 : :
258 : : // Create a new graph for the test.
259 : 1 : auto graph = MakeTxGraph(MAX_CLUSTER_COUNT, MAX_CLUSTER_SIZE);
260 : :
261 : : // Add all transactions and store their Refs.
262 : 1 : std::vector<TxGraph::Ref> refs;
263 [ + - ]: 1 : refs.reserve(NUM_TOTAL_TX);
264 : :
265 : : // Add all transactions. They are in individual clusters.
266 [ + + ]: 101 : for (unsigned int i = 0; i < NUM_TOTAL_TX; ++i) {
267 : : // The 88th transaction is oversized.
268 : : // Every 20th transaction is oversized.
269 [ + + + + ]: 100 : const FeePerWeight feerate{500 + i, (i == 88 || i % 20 == 0) ? MAX_CLUSTER_SIZE + 1 : 100};
270 [ + - ]: 100 : refs.push_back(graph->AddTransaction(feerate));
271 : : }
272 [ + - ]: 1 : graph->SanityCheck();
273 : :
274 : : // Check that the graph is now oversized. This also forces the graph to
275 : : // group clusters and compute the oversized status.
276 [ + - + - ]: 2 : BOOST_CHECK(graph->IsOversized(/*main_only=*/false));
277 : :
278 : : // Call Trim() to remove transactions and bring the cluster back within limits.
279 : 1 : auto removed_refs = graph->Trim();
280 [ + - ]: 1 : graph->SanityCheck();
281 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(graph->GetTransactionCount(), NUM_TOTAL_TX - 6);
282 [ + - + - ]: 2 : BOOST_CHECK(!graph->IsOversized(/*main_only=*/false));
283 : :
284 : : // Check that all the oversized transactions were removed.
285 [ + + ]: 101 : for (unsigned int i = 0; i < refs.size(); ++i) {
286 [ + - + + : 106 : BOOST_CHECK_EQUAL(graph->Exists(refs[i]), i != 88 && i % 20 != 0);
+ + + - ]
287 : : }
288 : 1 : }
289 : :
290 : : BOOST_AUTO_TEST_SUITE_END()
|
