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