Branch data Line data Source code
1 : : // Copyright (c) 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 <cluster_linearize.h>
6 : : #include <random.h>
7 : : #include <serialize.h>
8 : : #include <streams.h>
9 : : #include <test/fuzz/FuzzedDataProvider.h>
10 : : #include <test/fuzz/fuzz.h>
11 : : #include <test/util/cluster_linearize.h>
12 : : #include <util/bitset.h>
13 : : #include <util/feefrac.h>
14 : :
15 : : #include <algorithm>
16 : : #include <cstdint>
17 : : #include <utility>
18 : : #include <vector>
19 : :
20 : : /*
21 : : * The tests in this file primarily cover the candidate finder classes and linearization algorithms.
22 : : *
23 : : * <----: An implementation (at the start of the line --) is tested in the test marked with *,
24 : : * possibly by comparison with other implementations (at the end of the line ->).
25 : : * <<---: The right side is implemented using the left side.
26 : : *
27 : : * +---------------------+ +-----------+
28 : : * | SpanningForestState | <<-------------------- | Linearize |
29 : : * +---------------------+ +-----------+
30 : : * | |
31 : : * | | ^^ PRODUCTION CODE
32 : : * | | ||
33 : : * ==============================================================================================
34 : : * | | ||
35 : : * |-clusterlin_sfl* | vv TEST CODE
36 : : * | |
37 : : * \------------------------------------\ |-clusterlin_linearize*
38 : : * | |
39 : : * v v
40 : : * +-----------------------+ +-----------------+
41 : : * | SimpleCandidateFinder | <<-------------------| SimpleLinearize |
42 : : * +-----------------------+ +-----------------+
43 : : * | |
44 : : * |-clusterlin_simple_finder* |-clusterlin_simple_linearize*
45 : : * v v
46 : : * +---------------------------+ +---------------------+
47 : : * | ExhaustiveCandidateFinder | | ExhaustiveLinearize |
48 : : * +---------------------------+ +---------------------+
49 : : *
50 : : * More tests are included for lower-level and related functions and classes:
51 : : * - DepGraph tests:
52 : : * - clusterlin_depgraph_sim
53 : : * - clusterlin_depgraph_serialization
54 : : * - clusterlin_components
55 : : * - ChunkLinearization and ChunkLinearizationInfo tests:
56 : : * - clusterlin_chunking
57 : : * - PostLinearize tests:
58 : : * - clusterlin_postlinearize
59 : : * - clusterlin_postlinearize_tree
60 : : * - clusterlin_postlinearize_moved_leaf
61 : : * - MakeConnected tests (a test-only function):
62 : : * - clusterlin_make_connected
63 : : */
64 : :
65 : : using namespace cluster_linearize;
66 : :
67 : : namespace {
68 : :
69 : : /** A simple finder class for candidate sets (topologically-valid subsets with high feerate), only
70 : : * used by SimpleLinearize below. */
71 : : template<typename SetType>
72 : : class SimpleCandidateFinder
73 : : {
74 : : /** Internal dependency graph. */
75 : : const DepGraph<SetType>& m_depgraph;
76 : : /** Which transaction are left to include. */
77 : : SetType m_todo;
78 : :
79 : : public:
80 : : /** Construct an SimpleCandidateFinder for a given graph. */
81 : 2171 : SimpleCandidateFinder(const DepGraph<SetType>& depgraph LIFETIMEBOUND) noexcept :
82 : 2171 : m_depgraph(depgraph), m_todo{depgraph.Positions()} {}
83 : :
84 : : /** Remove a set of transactions from the set of to-be-linearized ones. */
85 : 26144 : void MarkDone(SetType select) noexcept { m_todo -= select; }
86 : :
87 : : /** Determine whether unlinearized transactions remain. */
88 : 2520 : bool AllDone() const noexcept { return m_todo.None(); }
89 : :
90 : : /** Find a candidate set using at most max_iterations iterations, and the number of iterations
91 : : * actually performed. If that number is less than max_iterations, then the result is optimal.
92 : : *
93 : : * Always returns a connected set of transactions.
94 : : *
95 : : * Complexity: O(N * M), where M is the number of connected topological subsets of the cluster.
96 : : * That number is bounded by M <= 2^(N-1).
97 : : */
98 : 26144 : std::pair<SetInfo<SetType>, uint64_t> FindCandidateSet(uint64_t max_iterations) const noexcept
99 : : {
100 : 26144 : uint64_t iterations_left = max_iterations;
101 : : // Queue of work units. Each consists of:
102 : : // - inc: set of transactions definitely included
103 : : // - und: set of transactions that can be added to inc still
104 : 26144 : std::vector<std::pair<SetType, SetType>> queue;
105 : : // Initially we have just one queue element, with the entire graph in und.
106 : 26144 : queue.emplace_back(SetType{}, m_todo);
107 : : // Best solution so far. Initialize with the remaining ancestors of the first remaining
108 : : // transaction.
109 : 26144 : SetInfo best(m_depgraph, m_depgraph.Ancestors(m_todo.First()) & m_todo);
110 : : // Process the queue.
111 [ + + + + ]: 81679256 : while (!queue.empty() && iterations_left) {
112 : : // Pop top element of the queue.
113 : 81653112 : auto [inc, und] = queue.back();
114 : 81653112 : queue.pop_back();
115 : : // Look for a transaction to consider adding/removing.
116 : 81653112 : bool inc_none = inc.None();
117 [ + + ]: 149833610 : for (auto split : und) {
118 : : // If inc is empty, consider any split transaction. Otherwise only consider
119 : : // transactions that share ancestry with inc so far (which means only connected
120 : : // sets will be considered).
121 [ + + + + ]: 108996560 : if (inc_none || inc.Overlaps(m_depgraph.Ancestors(split))) {
122 : 40816062 : --iterations_left;
123 : : // Add a queue entry with split included.
124 : 40816062 : SetInfo new_inc(m_depgraph, inc | (m_todo & m_depgraph.Ancestors(split)));
125 : 40816062 : queue.emplace_back(new_inc.transactions, und - new_inc.transactions);
126 : : // Add a queue entry with split excluded.
127 [ + + ]: 40816062 : queue.emplace_back(inc, und - m_depgraph.Descendants(split));
128 : : // Update statistics to account for the candidate new_inc.
129 [ + + ]: 40816062 : if (ByRatioNegSize{new_inc.feerate} > ByRatioNegSize{best.feerate}) best = new_inc;
130 : : break;
131 : : }
132 : : }
133 : : }
134 : 26144 : return {std::move(best), max_iterations - iterations_left};
135 : 26144 : }
136 : : };
137 : :
138 : : /** A very simple finder class for optimal candidate sets, which tries every subset.
139 : : *
140 : : * It is even simpler than SimpleCandidateFinder, and exists just to help test the correctness of
141 : : * SimpleCandidateFinder, so that it can be used in SimpleLinearize, which is then used to test the
142 : : * correctness of Linearize.
143 : : */
144 : : template<typename SetType>
145 : : class ExhaustiveCandidateFinder
146 : : {
147 : : /** Internal dependency graph. */
148 : : const DepGraph<SetType>& m_depgraph;
149 : : /** Which transaction are left to include. */
150 : : SetType m_todo;
151 : :
152 : : public:
153 : : /** Construct an ExhaustiveCandidateFinder for a given graph. */
154 : 258 : ExhaustiveCandidateFinder(const DepGraph<SetType>& depgraph LIFETIMEBOUND) noexcept :
155 : 258 : m_depgraph(depgraph), m_todo{depgraph.Positions()} {}
156 : :
157 : : /** Remove a set of transactions from the set of to-be-linearized ones. */
158 : 2262 : void MarkDone(SetType select) noexcept { m_todo -= select; }
159 : :
160 : : /** Determine whether unlinearized transactions remain. */
161 : 2520 : bool AllDone() const noexcept { return m_todo.None(); }
162 : :
163 : : /** Find the optimal remaining candidate set.
164 : : *
165 : : * Complexity: O(N * 2^N).
166 : : */
167 : 1437 : SetInfo<SetType> FindCandidateSet() const noexcept
168 : : {
169 : : // Best solution so far.
170 : 1437 : SetInfo<SetType> best{m_todo, m_depgraph.FeeRate(m_todo)};
171 : : // The number of combinations to try.
172 : 1437 : uint64_t limit = (uint64_t{1} << m_todo.Count()) - 1;
173 : : // Try the transitive closure of every non-empty subset of m_todo.
174 [ + + ]: 637915 : for (uint64_t x = 1; x < limit; ++x) {
175 : : // If bit number b is set in x, then the remaining ancestors of the b'th remaining
176 : : // transaction in m_todo are included.
177 : 636478 : SetType txn;
178 : 636478 : auto x_shifted{x};
179 [ + - + + ]: 8184992 : for (auto i : m_todo) {
180 [ + + ]: 6912036 : if (x_shifted & 1) txn |= m_depgraph.Ancestors(i);
181 : 6912036 : x_shifted >>= 1;
182 : : }
183 [ + + ]: 636478 : SetInfo cur(m_depgraph, txn & m_todo);
184 [ + + ]: 636478 : if (ByRatioNegSize{cur.feerate} > ByRatioNegSize{best.feerate}) best = cur;
185 : : }
186 : 1437 : return best;
187 : : }
188 : : };
189 : :
190 : : /** A simple linearization algorithm.
191 : : *
192 : : * This matches Linearize() in interface and behavior, though with fewer optimizations, lacking
193 : : * the ability to pass in an existing linearization, and linearizing by simply finding the
194 : : * consecutive remaining highest-feerate topological subset using SimpleCandidateFinder.
195 : : */
196 : : template<typename SetType>
197 : 1913 : std::pair<std::vector<DepGraphIndex>, bool> SimpleLinearize(const DepGraph<SetType>& depgraph, uint64_t max_iterations)
198 : : {
199 : 1913 : std::vector<DepGraphIndex> linearization;
200 : 1913 : SimpleCandidateFinder finder(depgraph);
201 : 1913 : SetType todo = depgraph.Positions();
202 : 1913 : bool optimal = true;
203 [ + + ]: 25795 : while (todo.Any()) {
204 [ + + ]: 23882 : auto [candidate, iterations_done] = finder.FindCandidateSet(max_iterations);
205 [ + + ]: 23882 : if (iterations_done == max_iterations) optimal = false;
206 : 23882 : depgraph.AppendTopo(linearization, candidate.transactions);
207 : 23882 : todo -= candidate.transactions;
208 : 23882 : finder.MarkDone(candidate.transactions);
209 : 23882 : max_iterations -= iterations_done;
210 : : }
211 : 1913 : return {std::move(linearization), optimal};
212 : 1913 : }
213 : :
214 : : /** An even simpler linearization algorithm that tries all permutations.
215 : : *
216 : : * This roughly matches SimpleLinearize() (and Linearize) in interface and behavior, but always
217 : : * tries all topologically-valid transaction orderings, has no way to bound how much work it does,
218 : : * and always finds the optimal. With an O(n!) complexity, it should only be used for small
219 : : * clusters.
220 : : */
221 : : template<typename SetType>
222 : 165 : std::vector<DepGraphIndex> ExhaustiveLinearize(const DepGraph<SetType>& depgraph)
223 : : {
224 : : // The best linearization so far, and its chunking.
225 : 165 : std::vector<DepGraphIndex> linearization;
226 : 165 : std::vector<FeeFrac> chunking;
227 : :
228 [ + + ]: 165 : std::vector<DepGraphIndex> perm_linearization;
229 : : // Initialize with the lexicographically-first linearization.
230 [ + + + - : 1121 : for (DepGraphIndex i : depgraph.Positions()) perm_linearization.push_back(i);
+ + ]
231 : : // Iterate over all valid permutations.
232 : : do {
233 : : /** What prefix of perm_linearization is topological. */
234 : 653664 : DepGraphIndex topo_length{0};
235 : 653664 : TestBitSet perm_done;
236 [ - + + + ]: 5617504 : while (topo_length < perm_linearization.size()) {
237 : 5033901 : auto i = perm_linearization[topo_length];
238 [ + + ]: 5033901 : perm_done.Set(i);
239 [ + + ]: 5033901 : if (!depgraph.Ancestors(i).IsSubsetOf(perm_done)) break;
240 : 4963840 : ++topo_length;
241 : : }
242 [ - + + + ]: 653664 : if (topo_length == perm_linearization.size()) {
243 : : // If all of perm_linearization is topological, check if it is perhaps our best
244 : : // linearization so far.
245 [ - + ]: 583603 : auto perm_chunking = ChunkLinearization(depgraph, perm_linearization);
246 [ - + + - ]: 583603 : auto cmp = CompareChunks(perm_chunking, chunking);
247 : : // If the diagram is better, or if it is equal but with more chunks (because we
248 : : // prefer minimal chunks), consider this better.
249 [ + + + + : 640246 : if (linearization.empty() || cmp > 0 || (cmp == 0 && perm_chunking.size() > chunking.size())) {
+ + - + +
+ ]
250 [ + - ]: 1785 : linearization = perm_linearization;
251 [ + - ]: 1785 : chunking = perm_chunking;
252 : : }
253 : 583603 : } else {
254 : : // Otherwise, fast forward to the last permutation with the same non-topological
255 : : // prefix.
256 : 70061 : auto first_non_topo = perm_linearization.begin() + topo_length;
257 [ - + ]: 70061 : assert(std::is_sorted(first_non_topo + 1, perm_linearization.end()));
258 : 70061 : std::reverse(first_non_topo + 1, perm_linearization.end());
259 : : }
260 [ + + ]: 653664 : } while(std::next_permutation(perm_linearization.begin(), perm_linearization.end()));
261 : :
262 : 165 : return linearization;
263 : 165 : }
264 : :
265 : :
266 : : /** Stitch connected components together in a DepGraph, guaranteeing its corresponding cluster is connected. */
267 : : template<typename BS>
268 : 1283 : void MakeConnected(DepGraph<BS>& depgraph)
269 : : {
270 : 1283 : auto todo = depgraph.Positions();
271 : 1283 : auto comp = depgraph.FindConnectedComponent(todo);
272 [ - + ]: 1283 : Assume(depgraph.IsConnected(comp));
273 : 1283 : todo -= comp;
274 [ + + ]: 10224 : while (todo.Any()) {
275 : 8941 : auto nextcomp = depgraph.FindConnectedComponent(todo);
276 [ - + ]: 8941 : Assume(depgraph.IsConnected(nextcomp));
277 : 8941 : depgraph.AddDependencies(BS::Singleton(comp.Last()), nextcomp.First());
278 : 8941 : todo -= nextcomp;
279 : 8941 : comp = nextcomp;
280 : : }
281 : 1283 : }
282 : :
283 : : /** Given a dependency graph, and a todo set, read a topological subset of todo from reader. */
284 : : template<typename SetType>
285 : 4465 : SetType ReadTopologicalSet(const DepGraph<SetType>& depgraph, const SetType& todo, SpanReader& reader, bool non_empty)
286 : : {
287 : : // Read a bitmask from the fuzzing input. Add 1 if non_empty, so the mask is definitely not
288 : : // zero in that case.
289 [ + + ]: 4465 : uint64_t mask{0};
290 : : try {
291 [ + + ]: 4465 : reader >> VARINT(mask);
292 [ - + ]: 3250 : } catch(const std::ios_base::failure&) {}
293 [ + + ]: 4465 : if (mask != uint64_t(-1)) mask += non_empty;
294 : :
295 : 4465 : SetType ret;
296 [ + - + + ]: 57332 : for (auto i : todo) {
297 [ + + ]: 48402 : if (!ret[i]) {
298 [ + + ]: 46150 : if (mask & 1) ret |= depgraph.Ancestors(i);
299 : 46150 : mask >>= 1;
300 : : }
301 : : }
302 : 4465 : ret &= todo;
303 : :
304 : : // While mask starts off non-zero if non_empty is true, it is still possible that all its low
305 : : // bits are 0, and ret ends up being empty. As a last resort, use the in-todo ancestry of the
306 : : // first todo position.
307 [ + - + + ]: 4465 : if (non_empty && ret.None()) {
308 [ - + ]: 317 : Assume(todo.Any());
309 [ - + ]: 317 : ret = depgraph.Ancestors(todo.First()) & todo;
310 [ - + ]: 317 : Assume(ret.Any());
311 : : }
312 : 4465 : return ret;
313 : : }
314 : :
315 : : /** Given a dependency graph, construct any valid linearization for it, reading from a SpanReader. */
316 : : template<typename BS>
317 : 13091 : std::vector<DepGraphIndex> ReadLinearization(const DepGraph<BS>& depgraph, SpanReader& reader, bool topological=true)
318 : : {
319 : 13091 : std::vector<DepGraphIndex> linearization;
320 : 13091 : TestBitSet todo = depgraph.Positions();
321 : : // In every iteration one transaction is appended to linearization.
322 [ + + ]: 324337 : while (todo.Any()) {
323 : : // Compute the set of transactions to select from.
324 : 298155 : TestBitSet potential_next;
325 [ + + ]: 298155 : if (topological) {
326 : : // Find all transactions with no not-yet-included ancestors.
327 [ + + ]: 4401322 : for (auto j : todo) {
328 [ + + ]: 6069599 : if ((depgraph.Ancestors(j) & todo) == TestBitSet::Singleton(j)) {
329 : 1959320 : potential_next.Set(j);
330 : : }
331 : : }
332 : : } else {
333 : : // Allow any element to be selected next, regardless of topology.
334 : 7112 : potential_next = todo;
335 : : }
336 : : // There must always be one (otherwise there is a cycle in the graph).
337 [ - + ]: 298155 : assert(potential_next.Any());
338 : : // Read a number from reader, and interpret it as index into potential_next.
339 [ + + ]: 298155 : uint64_t idx{0};
340 : : try {
341 [ + + + - ]: 596310 : reader >> VARINT(idx);
342 [ - + ]: 286524 : } catch (const std::ios_base::failure&) {}
343 : 298155 : idx %= potential_next.Count();
344 : : // Find out which transaction that corresponds to.
345 [ + - + - ]: 632882 : for (auto j : potential_next) {
346 [ + + ]: 334727 : if (idx == 0) {
347 : : // When found, add it to linearization and remove it from todo.
348 [ + - ]: 298155 : linearization.push_back(j);
349 [ - + ]: 298155 : assert(todo[j]);
350 : 298155 : todo.Reset(j);
351 : 298155 : break;
352 : : }
353 : 36572 : --idx;
354 : : }
355 : : }
356 : 13091 : return linearization;
357 : 0 : }
358 : :
359 : : /** Given a dependency graph, construct a tree-structured graph.
360 : : *
361 : : * Copies the nodes from the depgraph, but only keeps the first parent (even direction)
362 : : * or the first child (odd direction) for each transaction.
363 : : */
364 : : template<typename BS>
365 : 442 : DepGraph<BS> BuildTreeGraph(const DepGraph<BS>& depgraph, uint8_t direction)
366 : : {
367 : 442 : DepGraph<BS> depgraph_tree;
368 [ - + + + ]: 12249 : for (DepGraphIndex i = 0; i < depgraph.PositionRange(); ++i) {
369 [ + + ]: 11807 : if (depgraph.Positions()[i]) {
370 : 8455 : depgraph_tree.AddTransaction(depgraph.FeeRate(i));
371 : : } else {
372 : : // For holes, add a dummy transaction which is deleted below, so that non-hole
373 : : // transactions retain their position.
374 : 3352 : depgraph_tree.AddTransaction(FeeFrac{});
375 : : }
376 : : }
377 : 442 : depgraph_tree.RemoveTransactions(BS::Fill(depgraph.PositionRange()) - depgraph.Positions());
378 : :
379 [ + + ]: 442 : if (direction & 1) {
380 [ + + + + ]: 5542 : for (DepGraphIndex i : depgraph.Positions()) {
381 [ + + ]: 5045 : auto children = depgraph.GetReducedChildren(i);
382 [ + + ]: 5045 : if (children.Any()) {
383 : 3493 : depgraph_tree.AddDependencies(BS::Singleton(i), children.First());
384 : : }
385 : : }
386 : : } else {
387 [ + + + + ]: 3782 : for (DepGraphIndex i : depgraph.Positions()) {
388 [ + + ]: 3410 : auto parents = depgraph.GetReducedParents(i);
389 [ + + ]: 3410 : if (parents.Any()) {
390 : 2399 : depgraph_tree.AddDependencies(BS::Singleton(parents.First()), i);
391 : : }
392 : : }
393 : : }
394 : :
395 : 442 : return depgraph_tree;
396 : : }
397 : :
398 : : } // namespace
399 : :
400 [ + - ]: 906 : FUZZ_TARGET(clusterlin_depgraph_sim)
401 : : {
402 : : // Simulation test to verify the full behavior of DepGraph.
403 : :
404 : 430 : FuzzedDataProvider provider(buffer.data(), buffer.size());
405 : :
406 : : /** Real DepGraph being tested. */
407 : 430 : DepGraph<TestBitSet> real;
408 : : /** Simulated DepGraph (sim[i] is std::nullopt if position i does not exist; otherwise,
409 : : * sim[i]->first is its individual feerate, and sim[i]->second is its set of ancestors. */
410 : 430 : std::array<std::optional<std::pair<FeeFrac, TestBitSet>>, TestBitSet::Size()> sim;
411 : : /** The number of non-nullopt position in sim. */
412 : 430 : DepGraphIndex num_tx_sim{0};
413 : :
414 : : /** Read a valid index of a transaction from the provider. */
415 : 29300 : auto idx_fn = [&]() {
416 : 28870 : auto offset = provider.ConsumeIntegralInRange<DepGraphIndex>(0, num_tx_sim - 1);
417 [ + - ]: 219111 : for (DepGraphIndex i = 0; i < sim.size(); ++i) {
418 [ + + ]: 219111 : if (!sim[i].has_value()) continue;
419 [ + + ]: 187602 : if (offset == 0) return i;
420 : 158732 : --offset;
421 : : }
422 : 0 : assert(false);
423 : : return DepGraphIndex(-1);
424 : 430 : };
425 : :
426 : : /** Read a valid subset of the transactions from the provider. */
427 : 29300 : auto subset_fn = [&]() {
428 : 28870 : auto range = (uint64_t{1} << num_tx_sim) - 1;
429 : 28870 : const auto mask = provider.ConsumeIntegralInRange<uint64_t>(0, range);
430 : 28870 : auto mask_shifted = mask;
431 : 28870 : TestBitSet subset;
432 [ + + ]: 952710 : for (DepGraphIndex i = 0; i < sim.size(); ++i) {
433 [ + + ]: 923840 : if (!sim[i].has_value()) continue;
434 [ + + ]: 565153 : if (mask_shifted & 1) {
435 : 151461 : subset.Set(i);
436 : : }
437 : 565153 : mask_shifted >>= 1;
438 : : }
439 [ - + ]: 28870 : assert(mask_shifted == 0);
440 : 28870 : return subset;
441 : 430 : };
442 : :
443 : : /** Read any set of transactions from the provider (including unused positions). */
444 : 17686 : auto set_fn = [&]() {
445 : 17256 : auto range = (uint64_t{1} << sim.size()) - 1;
446 : 17256 : const auto mask = provider.ConsumeIntegralInRange<uint64_t>(0, range);
447 : 17256 : TestBitSet set;
448 [ + + ]: 569448 : for (DepGraphIndex i = 0; i < sim.size(); ++i) {
449 [ + + ]: 552192 : if ((mask >> i) & 1) {
450 : 189178 : set.Set(i);
451 : : }
452 : : }
453 : 17256 : return set;
454 : 430 : };
455 : :
456 : : /** Propagate ancestor information in sim. */
457 : 18116 : auto anc_update_fn = [&]() {
458 : 21167 : while (true) {
459 : 21167 : bool updates{false};
460 [ + + ]: 698511 : for (DepGraphIndex chl = 0; chl < sim.size(); ++chl) {
461 [ + + ]: 677344 : if (!sim[chl].has_value()) continue;
462 [ + - + + ]: 1712429 : for (auto par : sim[chl]->second) {
463 [ + + ]: 1035191 : if (!sim[chl]->second.IsSupersetOf(sim[par]->second)) {
464 : 14505 : sim[chl]->second |= sim[par]->second;
465 : 14505 : updates = true;
466 : : }
467 : : }
468 : : }
469 [ + + ]: 21167 : if (!updates) break;
470 : : }
471 : 18116 : };
472 : :
473 : : /** Compare the state of transaction i in the simulation with the real one. */
474 : 203368 : auto check_fn = [&](DepGraphIndex i) {
475 : : // Compare used positions.
476 [ - + ]: 202938 : assert(real.Positions()[i] == sim[i].has_value());
477 [ + + ]: 202938 : if (sim[i].has_value()) {
478 : : // Compare feerate.
479 [ + - ]: 49415 : assert(real.FeeRate(i) == sim[i]->first);
480 : : // Compare ancestors (note that SanityCheck verifies correspondence between ancestors
481 : : // and descendants, so we can restrict ourselves to ancestors here).
482 [ - + ]: 49415 : assert(real.Ancestors(i) == sim[i]->second);
483 : : }
484 : 203368 : };
485 : :
486 : 430 : auto last_compaction_pos{real.PositionRange()};
487 : :
488 [ + + + + ]: 119766 : LIMITED_WHILE (provider.remaining_bytes() > 0, 1000) {
489 : 119336 : int command = provider.ConsumeIntegral<uint8_t>() % 4;
490 : 123475 : while (true) {
491 : : // Iterate decreasing command until an applicable branch is found.
492 [ + + + + ]: 123475 : if (num_tx_sim < TestBitSet::Size() && command-- == 0) {
493 : : // AddTransaction.
494 : 49415 : auto fee = provider.ConsumeIntegralInRange<int64_t>(-0x8000000000000, 0x7ffffffffffff);
495 : 49415 : auto size = provider.ConsumeIntegralInRange<int32_t>(1, 0x3fffff);
496 : 49415 : FeeFrac feerate{fee, size};
497 : : // Apply to DepGraph.
498 : 49415 : auto idx = real.AddTransaction(feerate);
499 : : // Verify that the returned index is correct.
500 [ - + ]: 49415 : assert(!sim[idx].has_value());
501 [ + - ]: 708778 : for (DepGraphIndex i = 0; i < TestBitSet::Size(); ++i) {
502 [ + + ]: 708778 : if (!sim[i].has_value()) {
503 [ - + ]: 49415 : assert(idx == i);
504 : : break;
505 : : }
506 : : }
507 : : // Update sim.
508 [ - + ]: 49415 : sim[idx] = {feerate, TestBitSet::Singleton(idx)};
509 : 49415 : ++num_tx_sim;
510 : 49415 : break;
511 [ + + + + ]: 74060 : } else if (num_tx_sim > 0 && command-- == 0) {
512 : : // AddDependencies.
513 : 28870 : DepGraphIndex child = idx_fn();
514 : 28870 : auto parents = subset_fn();
515 : : // Apply to DepGraph.
516 : 28870 : real.AddDependencies(parents, child);
517 : : // Apply to sim.
518 : 28870 : sim[child]->second |= parents;
519 : 28870 : break;
520 [ + + + + ]: 45190 : } else if (num_tx_sim > 0 && command-- == 0) {
521 : : // Remove transactions.
522 : 17256 : auto del = set_fn();
523 : : // Propagate all ancestry information before deleting anything in the simulation (as
524 : : // intermediary transactions may be deleted which impact connectivity).
525 : 17256 : anc_update_fn();
526 : : // Compare the state of the transactions being deleted.
527 [ + + + + ]: 222267 : for (auto i : del) check_fn(i);
528 : : // Apply to DepGraph.
529 : 17256 : real.RemoveTransactions(del);
530 : : // Apply to sim.
531 [ + + ]: 569448 : for (DepGraphIndex i = 0; i < sim.size(); ++i) {
532 [ + + ]: 552192 : if (sim[i].has_value()) {
533 [ + + ]: 243226 : if (del[i]) {
534 : 42060 : --num_tx_sim;
535 [ + - ]: 594252 : sim[i] = std::nullopt;
536 : : } else {
537 : 201166 : sim[i]->second -= del;
538 : : }
539 : : }
540 : : }
541 : : break;
542 [ + + ]: 27934 : } else if (command-- == 0) {
543 : : // Compact.
544 [ - + ]: 23795 : const size_t mem_before{real.DynamicMemoryUsage()};
545 : 23795 : real.Compact();
546 [ - + ]: 23795 : const size_t mem_after{real.DynamicMemoryUsage()};
547 [ - + + + : 23795 : assert(real.PositionRange() < last_compaction_pos ? mem_after < mem_before : mem_after <= mem_before);
- + ]
548 : : last_compaction_pos = real.PositionRange();
549 : : break;
550 : : }
551 : : }
552 : : }
553 : :
554 : : // Compare the real obtained depgraph against the simulation.
555 : 430 : anc_update_fn();
556 [ + + ]: 14190 : for (DepGraphIndex i = 0; i < sim.size(); ++i) check_fn(i);
557 [ - + ]: 430 : assert(real.TxCount() == num_tx_sim);
558 : : // Sanity check the result (which includes round-tripping serialization, if applicable).
559 [ + - ]: 430 : SanityCheck(real);
560 : 430 : }
561 : :
562 [ + - ]: 765 : FUZZ_TARGET(clusterlin_depgraph_serialization)
563 : : {
564 : : // Verify that any deserialized depgraph is acyclic and roundtrips to an identical depgraph.
565 : :
566 : : // Construct a graph by deserializing.
567 : 289 : SpanReader reader(buffer);
568 : 289 : DepGraph<TestBitSet> depgraph;
569 : 289 : DepGraphIndex par_code{0}, chl_code{0};
570 : 289 : try {
571 [ + - + + : 289 : reader >> Using<DepGraphFormatter>(depgraph) >> VARINT(par_code) >> VARINT(chl_code);
+ + ]
572 [ - + ]: 252 : } catch (const std::ios_base::failure&) {}
573 [ + - ]: 289 : SanityCheck(depgraph);
574 : :
575 : : // Verify the graph is a DAG.
576 [ - + ]: 289 : assert(depgraph.IsAcyclic());
577 : :
578 : : // Introduce a cycle, and then test that IsAcyclic returns false.
579 [ + + ]: 289 : if (depgraph.TxCount() < 2) return;
580 : 267 : DepGraphIndex par(0), chl(0);
581 : : // Pick any transaction of depgraph as parent.
582 [ + - ]: 267 : par_code %= depgraph.TxCount();
583 [ + - + - ]: 1001 : for (auto i : depgraph.Positions()) {
584 [ + + ]: 734 : if (par_code == 0) {
585 : : par = i;
586 : : break;
587 : : }
588 : 467 : --par_code;
589 : : }
590 : : // Pick any ancestor of par (excluding itself) as child, if any.
591 [ + + ]: 267 : auto ancestors = depgraph.Ancestors(par) - TestBitSet::Singleton(par);
592 [ + + ]: 267 : if (ancestors.None()) return;
593 : 135 : chl_code %= ancestors.Count();
594 [ + - ]: 269 : for (auto i : ancestors) {
595 [ + + ]: 269 : if (chl_code == 0) {
596 : : chl = i;
597 : : break;
598 : : }
599 : 134 : --chl_code;
600 : : }
601 : : // Add the cycle-introducing dependency.
602 : 135 : depgraph.AddDependencies(TestBitSet::Singleton(par), chl);
603 : : // Check that we now detect a cycle.
604 [ - + ]: 135 : assert(!depgraph.IsAcyclic());
605 : 289 : }
606 : :
607 [ + - ]: 627 : FUZZ_TARGET(clusterlin_components)
608 : : {
609 : : // Verify the behavior of DepGraphs's FindConnectedComponent and IsConnected functions.
610 : :
611 : : // Construct a depgraph.
612 : 151 : SpanReader reader(buffer);
613 : 151 : DepGraph<TestBitSet> depgraph;
614 : 151 : try {
615 [ + - ]: 151 : reader >> Using<DepGraphFormatter>(depgraph);
616 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
617 : :
618 : 151 : TestBitSet todo = depgraph.Positions();
619 [ + + ]: 1660 : while (todo.Any()) {
620 : : // Pick a transaction in todo, or nothing.
621 : 1509 : std::optional<DepGraphIndex> picked;
622 : 1509 : {
623 : 1509 : uint64_t picked_num{0};
624 : 1509 : try {
625 [ + + ]: 1509 : reader >> VARINT(picked_num);
626 [ - + ]: 1030 : } catch (const std::ios_base::failure&) {}
627 [ + + + + ]: 1509 : if (picked_num < todo.Size() && todo[picked_num]) {
628 : 294 : picked = picked_num;
629 : : }
630 : : }
631 : :
632 : : // Find a connected component inside todo, including picked if any.
633 [ + + ]: 1509 : auto component = picked ? depgraph.GetConnectedComponent(todo, *picked)
634 : 1215 : : depgraph.FindConnectedComponent(todo);
635 : :
636 : : // The component must be a subset of todo and non-empty.
637 [ - + ]: 1509 : assert(component.IsSubsetOf(todo));
638 [ - + ]: 1509 : assert(component.Any());
639 : :
640 : : // If picked was provided, the component must include it.
641 [ + + - + ]: 1509 : if (picked) assert(component[*picked]);
642 : :
643 : : // If todo is the entire graph, and the entire graph is connected, then the component must
644 : : // be the entire graph.
645 [ + + ]: 1509 : if (todo == depgraph.Positions()) {
646 [ + + - + ]: 239 : assert((component == todo) == depgraph.IsConnected());
647 : : }
648 : :
649 : : // If subset is connected, then component must match subset.
650 [ + + - + ]: 2665 : assert((component == todo) == depgraph.IsConnected(todo));
651 : :
652 : : // The component cannot have any ancestors or descendants outside of component but in todo.
653 [ + - + + ]: 10430 : for (auto i : component) {
654 [ - + ]: 7412 : assert((depgraph.Ancestors(i) & todo).IsSubsetOf(component));
655 [ - + ]: 7412 : assert((depgraph.Descendants(i) & todo).IsSubsetOf(component));
656 : : }
657 : :
658 : : // Starting from any component element, we must be able to reach every element.
659 [ + - + + ]: 10430 : for (auto i : component) {
660 : : // Start with just i as reachable.
661 : 7412 : TestBitSet reachable = TestBitSet::Singleton(i);
662 : : // Add in-todo descendants and ancestors to reachable until it does not change anymore.
663 : 46162 : while (true) {
664 : 26787 : TestBitSet new_reachable = reachable;
665 [ + - + + ]: 309851 : for (auto j : new_reachable) {
666 : 256277 : new_reachable |= depgraph.Ancestors(j) & todo;
667 : 256277 : new_reachable |= depgraph.Descendants(j) & todo;
668 : : }
669 [ + + ]: 26787 : if (new_reachable == reachable) break;
670 : 19375 : reachable = new_reachable;
671 : 19375 : }
672 : : // Verify that the result is the entire component.
673 [ - + ]: 7412 : assert(component == reachable);
674 : : }
675 : :
676 : : // Construct an arbitrary subset of todo.
677 : 1509 : uint64_t subset_bits{0};
678 : 1509 : try {
679 [ + + ]: 1509 : reader >> VARINT(subset_bits);
680 [ - + ]: 1055 : } catch (const std::ios_base::failure&) {}
681 : 1509 : TestBitSet subset;
682 [ + - + + ]: 34784 : for (DepGraphIndex i : depgraph.Positions()) {
683 [ + + ]: 31766 : if (todo[i]) {
684 [ + + ]: 16505 : if (subset_bits & 1) subset.Set(i);
685 : 16505 : subset_bits >>= 1;
686 : : }
687 : : }
688 : : // Which must be non-empty.
689 [ + + ]: 1509 : if (subset.None()) subset = TestBitSet::Singleton(todo.First());
690 : : // Remove it from todo.
691 : 1509 : todo -= subset;
692 : : }
693 : :
694 : : // No components can be found in an empty subset.
695 [ - + ]: 151 : assert(depgraph.FindConnectedComponent(todo).None());
696 : 151 : }
697 : :
698 [ + - ]: 752 : FUZZ_TARGET(clusterlin_make_connected)
699 : : {
700 : : // Verify that MakeConnected makes graphs connected.
701 : :
702 : 276 : SpanReader reader(buffer);
703 : 276 : DepGraph<TestBitSet> depgraph;
704 : 276 : try {
705 [ + - ]: 276 : reader >> Using<DepGraphFormatter>(depgraph);
706 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
707 [ + - ]: 276 : MakeConnected(depgraph);
708 [ + - ]: 276 : SanityCheck(depgraph);
709 [ - + ]: 276 : assert(depgraph.IsConnected());
710 : 276 : }
711 : :
712 [ + - ]: 638 : FUZZ_TARGET(clusterlin_chunking)
713 : : {
714 : : // Verify the correctness of the ChunkLinearization function.
715 : :
716 : : // Construct a graph by deserializing.
717 : 162 : SpanReader reader(buffer);
718 : 162 : DepGraph<TestBitSet> depgraph;
719 : 162 : try {
720 [ + - ]: 162 : reader >> Using<DepGraphFormatter>(depgraph);
721 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
722 : :
723 : : // Read a valid linearization for depgraph.
724 [ + - ]: 162 : auto linearization = ReadLinearization(depgraph, reader);
725 : :
726 : : // Invoke the chunking functions.
727 [ - + ]: 162 : auto chunking = ChunkLinearization(depgraph, linearization);
728 [ - + ]: 162 : auto chunking_info = ChunkLinearizationInfo(depgraph, linearization);
729 : :
730 : : // Verify consistency between the two functions.
731 [ - + - + : 162 : assert(chunking.size() == chunking_info.size());
- + ]
732 [ - + + + ]: 860 : for (size_t i = 0; i < chunking.size(); ++i) {
733 [ + - ]: 698 : assert(chunking[i] == chunking_info[i].feerate);
734 [ + - ]: 1396 : assert(SetInfo(depgraph, chunking_info[i].transactions) == chunking_info[i]);
735 : : }
736 : :
737 : : // Verify that chunk feerates are monotonically non-increasing.
738 [ + + ]: 706 : for (size_t i = 1; i < chunking.size(); ++i) {
739 [ - + ]: 544 : assert(ByRatio{chunking[i]} <= ByRatio{chunking[i - 1]});
740 : : }
741 : :
742 : : // Naively recompute the chunks (each is the highest-feerate prefix of what remains).
743 : 162 : auto todo = depgraph.Positions();
744 [ + + ]: 860 : for (const auto& [chunk_set, chunk_feerate] : chunking_info) {
745 [ - + ]: 698 : assert(todo.Any());
746 : 698 : SetInfo<TestBitSet> accumulator, best;
747 [ + + ]: 16200 : for (DepGraphIndex idx : linearization) {
748 [ + + ]: 15502 : if (todo[idx]) {
749 : 8763 : accumulator.Set(depgraph, idx);
750 [ + + + + ]: 8763 : if (best.feerate.IsEmpty() || ByRatio{accumulator.feerate} > ByRatio{best.feerate}) {
751 : 1564 : best = accumulator;
752 : : }
753 : : }
754 : : }
755 [ + - ]: 698 : assert(chunk_feerate == best.feerate);
756 [ - + ]: 698 : assert(chunk_set == best.transactions);
757 [ - + ]: 698 : assert(best.transactions.IsSubsetOf(todo));
758 : 698 : todo -= best.transactions;
759 : : }
760 [ - + ]: 162 : assert(todo.None());
761 : 162 : }
762 : :
763 : : static constexpr auto MAX_SIMPLE_ITERATIONS = 300000;
764 : :
765 [ + - ]: 734 : FUZZ_TARGET(clusterlin_simple_finder)
766 : : {
767 : : // Verify that SimpleCandidateFinder works as expected by sanity checking the results
768 : : // and comparing them (if claimed to be optimal) against the sets found by
769 : : // ExhaustiveCandidateFinder.
770 : : //
771 : : // Note that SimpleCandidateFinder is only used in tests; the purpose of this fuzz test is to
772 : : // establish confidence in SimpleCandidateFinder, so that it can be used in SimpleLinearize,
773 : : // which is then used to test Linearize below.
774 : :
775 : : // Retrieve a depgraph from the fuzz input.
776 : 258 : SpanReader reader(buffer);
777 : 258 : DepGraph<TestBitSet> depgraph;
778 : 258 : try {
779 [ + - ]: 258 : reader >> Using<DepGraphFormatter>(depgraph);
780 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
781 : :
782 : : // Instantiate the SimpleCandidateFinder to be tested, and the ExhaustiveCandidateFinder it is
783 : : // being tested against.
784 : 258 : SimpleCandidateFinder smp_finder(depgraph);
785 : 258 : ExhaustiveCandidateFinder exh_finder(depgraph);
786 : :
787 : 258 : auto todo = depgraph.Positions();
788 [ + + ]: 2520 : while (todo.Any()) {
789 [ - + ]: 2262 : assert(!smp_finder.AllDone());
790 [ - + ]: 2262 : assert(!exh_finder.AllDone());
791 : :
792 : : // Call SimpleCandidateFinder.
793 [ - + ]: 2262 : auto [found, iterations_done] = smp_finder.FindCandidateSet(MAX_SIMPLE_ITERATIONS);
794 : 2262 : bool optimal = (iterations_done != MAX_SIMPLE_ITERATIONS);
795 : :
796 : : // Sanity check the result.
797 [ - + ]: 2262 : assert(iterations_done <= MAX_SIMPLE_ITERATIONS);
798 [ - + ]: 2262 : assert(found.transactions.Any());
799 [ - + ]: 2262 : assert(found.transactions.IsSubsetOf(todo));
800 [ + - ]: 2262 : assert(depgraph.FeeRate(found.transactions) == found.feerate);
801 : : // Check that it is topologically valid.
802 [ + - + + ]: 9015 : for (auto i : found.transactions) {
803 [ - + ]: 4491 : assert(found.transactions.IsSupersetOf(depgraph.Ancestors(i) & todo));
804 : : }
805 : :
806 : : // At most 2^(N-1) iterations can be required: the number of non-empty connected subsets a
807 : : // graph with N transactions can have. If MAX_SIMPLE_ITERATIONS exceeds this number, the
808 : : // result is necessarily optimal.
809 [ - + ]: 2262 : assert(iterations_done <= (uint64_t{1} << (todo.Count() - 1)));
810 [ + + - + ]: 2262 : if (MAX_SIMPLE_ITERATIONS > (uint64_t{1} << (todo.Count() - 1))) assert(optimal);
811 : :
812 : : // SimpleCandidateFinder only finds connected sets.
813 [ - + ]: 2262 : assert(depgraph.IsConnected(found.transactions));
814 : :
815 : : // Perform further quality checks only if SimpleCandidateFinder claims an optimal result.
816 [ + + ]: 2262 : if (optimal) {
817 [ + + ]: 2203 : if (todo.Count() <= 12) {
818 : : // Compare with ExhaustiveCandidateFinder. This quickly gets computationally
819 : : // expensive for large clusters (O(2^n)), so only do it for sufficiently small ones.
820 : 1437 : auto exhaustive = exh_finder.FindCandidateSet();
821 [ + - ]: 1437 : assert(exhaustive.feerate == found.feerate);
822 : : }
823 : :
824 : : // Compare with a non-empty topological set read from the fuzz input (comparing with an
825 : : // empty set is not interesting).
826 [ + - ]: 2203 : auto read_topo = ReadTopologicalSet(depgraph, todo, reader, /*non_empty=*/true);
827 [ - + ]: 2203 : assert(ByRatioNegSize{found.feerate} >= ByRatioNegSize{depgraph.FeeRate(read_topo)});
828 : : }
829 : :
830 : : // Find a non-empty topologically valid subset of transactions to remove from the graph.
831 : : // Using an empty set would mean the next iteration is identical to the current one, and
832 : : // could cause an infinite loop.
833 [ + - ]: 2262 : auto del_set = ReadTopologicalSet(depgraph, todo, reader, /*non_empty=*/true);
834 : 2262 : todo -= del_set;
835 : 2262 : smp_finder.MarkDone(del_set);
836 : 2262 : exh_finder.MarkDone(del_set);
837 : : }
838 : :
839 [ - + ]: 258 : assert(smp_finder.AllDone());
840 [ - + ]: 258 : assert(exh_finder.AllDone());
841 : 258 : }
842 : :
843 [ + - ]: 877 : FUZZ_TARGET(clusterlin_simple_linearize)
844 : : {
845 : : // Verify the behavior of SimpleLinearize(). Note that SimpleLinearize is only used in tests;
846 : : // the purpose of this fuzz test is to establish confidence in SimpleLinearize, so that it can
847 : : // be used to test the real Linearize function in the fuzz test below.
848 : :
849 : : // Retrieve an iteration count and a depgraph from the fuzz input.
850 : 401 : SpanReader reader(buffer);
851 : 401 : uint64_t iter_count{0};
852 : 401 : DepGraph<TestBitSet> depgraph;
853 : 401 : try {
854 [ + + + - ]: 401 : reader >> VARINT(iter_count) >> Using<DepGraphFormatter>(depgraph);
855 [ - + ]: 6 : } catch (const std::ios_base::failure&) {}
856 : 401 : iter_count %= MAX_SIMPLE_ITERATIONS;
857 : :
858 : : // Invoke SimpleLinearize().
859 [ - + ]: 401 : auto [linearization, optimal] = SimpleLinearize(depgraph, iter_count);
860 [ - + ]: 401 : SanityCheck(depgraph, linearization);
861 [ - + ]: 401 : auto simple_chunking = ChunkLinearization(depgraph, linearization);
862 : :
863 : : // If the iteration count is sufficiently high, an optimal linearization must be found.
864 : : // SimpleLinearize on k transactions can take up to 2^(k-1) iterations (one per non-empty
865 : : // connected topologically valid subset), which sums over k=1..n to (2^n)-1.
866 [ + - ]: 401 : const uint64_t n = depgraph.TxCount();
867 [ + - + + ]: 401 : if (n <= 63 && (iter_count >> n)) {
868 [ - + ]: 106 : assert(optimal);
869 : : }
870 : :
871 : : // If SimpleLinearize claims optimal result, and the cluster is sufficiently small (there are
872 : : // n! linearizations), test that the result is as good as every valid linearization.
873 [ + + + + ]: 401 : if (optimal && depgraph.TxCount() <= 8) {
874 [ + - ]: 165 : auto exh_linearization = ExhaustiveLinearize(depgraph);
875 [ - + ]: 165 : auto exh_chunking = ChunkLinearization(depgraph, exh_linearization);
876 [ - + - + : 165 : auto cmp = CompareChunks(simple_chunking, exh_chunking);
+ - ]
877 [ - + ]: 165 : assert(cmp == 0);
878 [ - + - + : 165 : assert(simple_chunking.size() == exh_chunking.size());
- + ]
879 : 165 : }
880 : :
881 [ + + ]: 401 : if (optimal) {
882 : : // Compare with a linearization read from the fuzz input.
883 [ + - ]: 326 : auto read = ReadLinearization(depgraph, reader);
884 [ - + ]: 326 : auto read_chunking = ChunkLinearization(depgraph, read);
885 [ - + - + : 326 : auto cmp = CompareChunks(simple_chunking, read_chunking);
+ - ]
886 [ - + ]: 326 : assert(cmp >= 0);
887 : 326 : }
888 : 401 : }
889 : :
890 [ + - ]: 1514 : FUZZ_TARGET(clusterlin_sfl)
891 : : {
892 : : // Verify the individual steps of the SFL algorithm.
893 : :
894 : 1038 : SpanReader reader(buffer);
895 : 1038 : DepGraph<TestBitSet> depgraph;
896 : 1038 : uint8_t flags{1};
897 : 1038 : uint64_t rng_seed{0};
898 : 1038 : try {
899 [ + + + + : 1038 : reader >> rng_seed >> flags >> Using<DepGraphFormatter>(depgraph);
+ - ]
900 [ - + ]: 6 : } catch (const std::ios_base::failure&) {}
901 [ + + ]: 1038 : if (depgraph.TxCount() <= 1) return;
902 : 1017 : InsecureRandomContext rng(rng_seed);
903 : : /** Whether to make the depgraph connected. */
904 : 1017 : const bool make_connected = flags & 1;
905 : : /** Whether to load some input linearization into the state. */
906 : 1017 : const bool load_linearization = flags & 2;
907 : : /** Whether that input linearization is topological. */
908 [ + + + + ]: 1017 : const bool load_topological = load_linearization && (flags & 4);
909 : :
910 : : // Initialize SFL state.
911 [ + + + - ]: 1017 : if (make_connected) MakeConnected(depgraph);
912 : 1017 : SpanningForestState sfl(depgraph, rng.rand64());
913 : :
914 : : // Function to test the state.
915 : 1017 : std::vector<FeeFrac> last_diagram;
916 : 1017 : bool was_optimal{false};
917 : 46383 : auto test_fn = [&](bool is_optimal = false, bool is_minimal = false) {
918 [ + + ]: 45366 : if (rng.randbits(4) == 0) {
919 : : // Perform sanity checks from time to time (too computationally expensive to do after
920 : : // every step).
921 : 4260 : sfl.SanityCheck();
922 : : }
923 : 45366 : auto diagram = sfl.GetDiagram();
924 [ + + ]: 45366 : if (rng.randbits(4) == 0) {
925 : : // Verify that the diagram of GetLinearization() is at least as good as GetDiagram(),
926 : : // from time to time.
927 : 4404 : auto lin = sfl.GetLinearization(IndexTxOrder{});
928 [ - + ]: 4404 : auto lin_diagram = ChunkLinearization(depgraph, lin);
929 [ - + - + : 4404 : auto cmp_lin = CompareChunks(lin_diagram, diagram);
+ - ]
930 [ - + ]: 4404 : assert(cmp_lin >= 0);
931 : : // If we're in an allegedly optimal state, they must match.
932 [ + + - + ]: 4404 : if (is_optimal) assert(cmp_lin == 0);
933 : : // If we're in an allegedly minimal state, they must also have the same number of
934 : : // segments.
935 [ + + - + : 4404 : if (is_minimal) assert(diagram.size() == lin_diagram.size());
- + - + ]
936 : 4404 : }
937 : : // Verify that subsequent calls to GetDiagram() never get worse/incomparable.
938 [ + + ]: 45366 : if (!last_diagram.empty()) {
939 [ - + - + : 44554 : auto cmp = CompareChunks(diagram, last_diagram);
+ - ]
940 [ - + ]: 44554 : assert(cmp >= 0);
941 : : // If the last diagram was already optimal, the new one cannot be better.
942 [ + + - + ]: 44554 : if (was_optimal) assert(cmp == 0);
943 : : // Also, if the diagram was already optimal, the number of segments can only increase.
944 [ + + - + : 44554 : if (was_optimal) assert(diagram.size() >= last_diagram.size());
- + - + ]
945 : : }
946 : 45366 : last_diagram = std::move(diagram);
947 : 45366 : was_optimal = is_optimal;
948 : 46383 : };
949 : :
950 [ + + ]: 1017 : if (load_linearization) {
951 [ + - ]: 443 : auto input_lin = ReadLinearization(depgraph, reader, load_topological);
952 [ - + ]: 443 : sfl.LoadLinearization(input_lin);
953 [ + + ]: 443 : if (load_topological) {
954 : : // The diagram of the loaded linearization forms an initial lower bound on future
955 : : // diagrams.
956 [ - + ]: 205 : last_diagram = ChunkLinearization(depgraph, input_lin);
957 : : } else {
958 : : // The input linearization may have been non-topological, so invoke MakeTopological to
959 : : // fix it still.
960 : 238 : sfl.MakeTopological();
961 : : }
962 : 443 : } else {
963 : : // Invoke MakeTopological to create an initial from-scratch topological state.
964 : 574 : sfl.MakeTopological();
965 : : }
966 : :
967 : : // Loop until optimal.
968 [ + - ]: 1017 : test_fn();
969 : 1017 : sfl.StartOptimizing();
970 : 17651 : while (true) {
971 [ + - ]: 17651 : test_fn();
972 [ + + ]: 17651 : if (!sfl.OptimizeStep()) break;
973 : : }
974 : :
975 : : // Loop until minimal.
976 [ + - ]: 1017 : test_fn(/*is_optimal=*/true);
977 : 1017 : sfl.StartMinimizing();
978 : 24664 : while (true) {
979 [ + - ]: 24664 : test_fn(/*is_optimal=*/true);
980 [ + + ]: 24664 : if (!sfl.MinimizeStep()) break;
981 : : }
982 [ + - ]: 1017 : test_fn(/*is_optimal=*/true, /*is_minimal=*/true);
983 : :
984 : : // Verify that optimality is reached within an expected amount of work. This protects against
985 : : // hypothetical bugs that hugely increase the amount of work needed to reach optimality.
986 [ - + ]: 1017 : assert(sfl.GetCost() <= MaxOptimalLinearizationCost(depgraph.TxCount()));
987 : :
988 : : // The result must be as good as SimpleLinearize.
989 [ - + ]: 1017 : auto [simple_linearization, simple_optimal] = SimpleLinearize(depgraph, MAX_SIMPLE_ITERATIONS / 10);
990 [ - + ]: 1017 : auto simple_diagram = ChunkLinearization(depgraph, simple_linearization);
991 [ - + - + : 1017 : auto simple_cmp = CompareChunks(last_diagram, simple_diagram);
+ - ]
992 [ - + ]: 1017 : assert(simple_cmp >= 0);
993 [ + + - + ]: 1017 : if (simple_optimal) assert(simple_cmp == 0);
994 : : // If the diagram matches, we must also have at least as many segments (because the SFL state
995 : : // and its produced diagram are minimal);
996 [ + + - + : 1017 : if (simple_cmp == 0) assert(last_diagram.size() >= simple_diagram.size());
- + + - ]
997 : :
998 : : // We can compare with any arbitrary linearization, and the diagram must be at least as good as
999 : : // each.
1000 [ + + ]: 11187 : for (int i = 0; i < 10; ++i) {
1001 [ + - ]: 10170 : auto read_lin = ReadLinearization(depgraph, reader);
1002 [ - + ]: 10170 : auto read_diagram = ChunkLinearization(depgraph, read_lin);
1003 [ - + - + : 10170 : auto cmp = CompareChunks(last_diagram, read_diagram);
+ - ]
1004 [ - + ]: 10170 : assert(cmp >= 0);
1005 [ + + - + : 10170 : if (cmp == 0) assert(last_diagram.size() >= read_diagram.size());
- + - + ]
1006 : 10170 : }
1007 : 1038 : }
1008 : :
1009 [ + - ]: 1129 : FUZZ_TARGET(clusterlin_linearize)
1010 : : {
1011 : : // Verify the behavior of Linearize().
1012 : :
1013 : : // Retrieve an RNG seed, a maximum amount of work, a depgraph, and whether to make it connected
1014 : : // from the fuzz input.
1015 : 653 : SpanReader reader(buffer);
1016 : 653 : DepGraph<TestBitSet> depgraph;
1017 : 653 : uint64_t rng_seed{0};
1018 : 653 : uint64_t max_cost{0};
1019 : 653 : uint8_t flags{7};
1020 : 653 : try {
1021 [ + + + - : 653 : reader >> VARINT(max_cost) >> Using<DepGraphFormatter>(depgraph) >> rng_seed >> flags;
+ + + + ]
1022 [ - + ]: 363 : } catch (const std::ios_base::failure&) {}
1023 [ + + ]: 653 : if (depgraph.TxCount() <= 1) return;
1024 : 634 : bool make_connected = flags & 1;
1025 : : // The following 3 booleans have 4 combinations:
1026 : : // - (flags & 6) == 0: do not provide input linearization.
1027 : : // - (flags & 6) == 2: provide potentially non-topological input.
1028 : : // - (flags & 6) == 4: provide topological input linearization, but do not claim it is
1029 : : // topological.
1030 : : // - (flags & 6) == 6: provide topological input linearization, and claim it is topological.
1031 : 634 : bool provide_input = flags & 6;
1032 : 634 : bool provide_topological_input = flags & 4;
1033 : 634 : bool claim_topological_input = (flags & 6) == 6;
1034 : : // The most complicated graphs are connected ones (other ones just split up). Optionally force
1035 : : // the graph to be connected.
1036 [ + + + - ]: 634 : if (make_connected) MakeConnected(depgraph);
1037 : :
1038 : : // Optionally construct an old linearization for it.
1039 : 634 : std::vector<DepGraphIndex> old_linearization;
1040 [ + + ]: 634 : if (provide_input) {
1041 [ + - ]: 1010 : old_linearization = ReadLinearization(depgraph, reader, /*topological=*/provide_topological_input);
1042 [ + + - + ]: 505 : if (provide_topological_input) SanityCheck(depgraph, old_linearization);
1043 : : }
1044 : :
1045 : : // Invoke Linearize().
1046 : 634 : max_cost &= 0x3fffff;
1047 [ - + ]: 634 : auto [linearization, optimal, cost] = Linearize(
1048 : : /*depgraph=*/depgraph,
1049 : : /*max_cost=*/max_cost,
1050 : : /*rng_seed=*/rng_seed,
1051 : : /*fallback_order=*/IndexTxOrder{},
1052 : 634 : /*old_linearization=*/old_linearization,
1053 [ - + - + ]: 634 : /*is_topological=*/claim_topological_input);
1054 [ - + ]: 634 : SanityCheck(depgraph, linearization);
1055 [ - + ]: 634 : auto chunking = ChunkLinearization(depgraph, linearization);
1056 : :
1057 : : // Linearization must always be as good as the old one, if provided and topological (even when
1058 : : // not claimed to be topological).
1059 [ + + ]: 634 : if (provide_topological_input) {
1060 [ - + ]: 432 : auto old_chunking = ChunkLinearization(depgraph, old_linearization);
1061 [ - + - + : 432 : auto cmp = CompareChunks(chunking, old_chunking);
+ - ]
1062 [ - + ]: 432 : assert(cmp >= 0);
1063 : 432 : }
1064 : :
1065 : : // If the maximum amount of work is sufficiently high, an optimal linearization must be found.
1066 [ + + ]: 634 : if (max_cost > MaxOptimalLinearizationCost(depgraph.TxCount())) {
1067 [ - + ]: 213 : assert(optimal);
1068 : : }
1069 : :
1070 : : // If Linearize claims optimal result, run quality tests.
1071 [ + + ]: 634 : if (optimal) {
1072 : : // It must be as good as SimpleLinearize.
1073 [ - + ]: 495 : auto [simple_linearization, simple_optimal] = SimpleLinearize(depgraph, MAX_SIMPLE_ITERATIONS);
1074 [ - + ]: 495 : SanityCheck(depgraph, simple_linearization);
1075 [ - + ]: 495 : auto simple_chunking = ChunkLinearization(depgraph, simple_linearization);
1076 [ - + - + : 495 : auto cmp = CompareChunks(chunking, simple_chunking);
+ - ]
1077 [ - + ]: 495 : assert(cmp >= 0);
1078 : : // If SimpleLinearize finds the optimal result too, they must be equal (if not,
1079 : : // SimpleLinearize is broken).
1080 [ + + - + ]: 495 : if (simple_optimal) assert(cmp == 0);
1081 : :
1082 : : // If simple_chunking is diagram-optimal, it cannot have more chunks than chunking (as
1083 : : // chunking is claimed to be optimal, which implies minimal chunks).
1084 [ + + - + : 495 : if (cmp == 0) assert(chunking.size() >= simple_chunking.size());
- + - + ]
1085 : :
1086 : : // Compare with a linearization read from the fuzz input.
1087 [ + - ]: 495 : auto read = ReadLinearization(depgraph, reader);
1088 [ - + ]: 495 : auto read_chunking = ChunkLinearization(depgraph, read);
1089 [ - + - + : 495 : auto cmp_read = CompareChunks(chunking, read_chunking);
+ - ]
1090 [ - + ]: 495 : assert(cmp_read >= 0);
1091 : :
1092 : : // Verify that within every chunk, the transactions are in a valid order. For any pair of
1093 : : // transactions, it should not be possible to swap them; either due to a missing
1094 : : // dependency, or because the order would be inconsistent with decreasing feerate,
1095 : : // increasing size, and fallback order (just DepGraphIndex value here).
1096 [ - + ]: 495 : auto chunking_info = ChunkLinearizationInfo(depgraph, linearization);
1097 : : /** The set of all transactions (strictly) before tx1 (see below), or (strictly) before
1098 : : * chunk1 (see even further below). */
1099 : 495 : TestBitSet done;
1100 : 495 : unsigned pos{0};
1101 [ + + ]: 6422 : for (const auto& chunk : chunking_info) {
1102 : 5927 : auto chunk_start = pos;
1103 : 5927 : auto chunk_end = pos + chunk.transactions.Count() - 1;
1104 : : // Go over all pairs of transactions. done is the set of transactions seen before pos1.
1105 [ + + ]: 18602 : for (unsigned pos1 = chunk_start; pos1 <= chunk_end; ++pos1) {
1106 : 12675 : auto tx1 = linearization[pos1];
1107 [ + + ]: 79966 : for (unsigned pos2 = pos1 + 1; pos2 <= chunk_end; ++pos2) {
1108 [ + + ]: 67291 : auto tx2 = linearization[pos2];
1109 : : // Check whether tx2 only depends on transactions that precede tx1.
1110 [ + + ]: 67291 : if ((depgraph.Ancestors(tx2) - done).Count() == 1) {
1111 : : // tx2 could take position pos1.
1112 : : // Verify that individual transaction feerate is decreasing (tie-breaking by
1113 : : // size).
1114 [ - + ]: 24571 : assert(ByRatioNegSize{depgraph.FeeRate(tx1)} >= ByRatioNegSize{depgraph.FeeRate(tx2)});
1115 : : // If feerate and size are equal, compare by DepGraphIndex.
1116 [ + + ]: 77197 : if (depgraph.FeeRate(tx1) == depgraph.FeeRate(tx2)) {
1117 [ - + ]: 7093 : assert(tx1 < tx2);
1118 : : }
1119 : : }
1120 : : }
1121 : 12675 : done.Set(tx1);
1122 : : }
1123 : 5927 : pos += chunk.transactions.Count();
1124 : : }
1125 : :
1126 : : // Verify that chunks themselves are in a valid order. For any pair of chunks, it should
1127 : : // not be possible to swap them; either due to a missing dependency, or because the order
1128 : : // would be inconsistent with decreasing chunk feerate, increasing chunk size, and order
1129 : : // of maximum fallback-ordered element (just maximum DepGraphIndex element here).
1130 : 495 : done = {};
1131 : : // Go over all pairs of chunks. done is the set of transactions seen before chunk_num1.
1132 [ - + + + ]: 6422 : for (unsigned chunk_num1 = 0; chunk_num1 < chunking_info.size(); ++chunk_num1) {
1133 : 5927 : const auto& chunk1 = chunking_info[chunk_num1];
1134 [ - + + + ]: 68500 : for (unsigned chunk_num2 = chunk_num1 + 1; chunk_num2 < chunking_info.size(); ++chunk_num2) {
1135 [ + - ]: 62573 : const auto& chunk2 = chunking_info[chunk_num2];
1136 : 62573 : TestBitSet chunk2_ancestors;
1137 [ + - + + ]: 203812 : for (auto tx : chunk2.transactions) chunk2_ancestors |= depgraph.Ancestors(tx);
1138 : : // Check whether chunk2 only depends on transactions that precede chunk1.
1139 [ + + ]: 62573 : if ((chunk2_ancestors - done).IsSubsetOf(chunk2.transactions)) {
1140 : : // chunk2 could take position chunk_num1.
1141 : : // Verify that chunk feerate is decreasing (tie-breaking by size).
1142 [ - + ]: 33490 : assert(ByRatioNegSize{chunk1.feerate} >= ByRatioNegSize{chunk2.feerate});
1143 : : // If feerate and size are equal, compare by maximum DepGraphIndex element.
1144 [ + + ]: 80960 : if (chunk1.feerate == chunk2.feerate) {
1145 [ - + ]: 16211 : assert(chunk1.transactions.Last() < chunk2.transactions.Last());
1146 : : }
1147 : : }
1148 : : }
1149 : 5927 : done |= chunk1.transactions;
1150 : : }
1151 : :
1152 : : // Redo from scratch with a different rng_seed. The resulting linearization should be
1153 : : // deterministic, if both are optimal.
1154 [ - + ]: 495 : auto [linearization2, optimal2, cost2] = Linearize(depgraph, MaxOptimalLinearizationCost(depgraph.TxCount()) + 1, rng_seed ^ 0x1337, IndexTxOrder{});
1155 [ - + ]: 495 : assert(optimal2);
1156 [ - + ]: 495 : assert(linearization2 == linearization);
1157 : 495 : }
1158 : 653 : }
1159 : :
1160 [ + - ]: 672 : FUZZ_TARGET(clusterlin_postlinearize)
1161 : : {
1162 : : // Verify expected properties of PostLinearize() on arbitrary linearizations.
1163 : :
1164 : : // Retrieve a depgraph from the fuzz input.
1165 : 196 : SpanReader reader(buffer);
1166 : 196 : DepGraph<TestBitSet> depgraph;
1167 : 196 : try {
1168 [ + - ]: 196 : reader >> Using<DepGraphFormatter>(depgraph);
1169 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
1170 : :
1171 : : // Retrieve a linearization from the fuzz input.
1172 : 196 : std::vector<DepGraphIndex> linearization;
1173 [ + - ]: 392 : linearization = ReadLinearization(depgraph, reader);
1174 [ - + ]: 196 : SanityCheck(depgraph, linearization);
1175 : :
1176 : : // Produce a post-processed version.
1177 [ + - ]: 196 : auto post_linearization = linearization;
1178 [ - + + - ]: 196 : PostLinearize(depgraph, post_linearization);
1179 [ - + ]: 196 : SanityCheck(depgraph, post_linearization);
1180 : :
1181 : : // Compare diagrams: post-linearization cannot worsen anywhere.
1182 [ - + ]: 196 : auto chunking = ChunkLinearization(depgraph, linearization);
1183 [ - + ]: 196 : auto post_chunking = ChunkLinearization(depgraph, post_linearization);
1184 [ - + - + : 196 : auto cmp = CompareChunks(post_chunking, chunking);
+ - ]
1185 [ - + ]: 196 : assert(cmp >= 0);
1186 : :
1187 : : // Run again, things can keep improving (and never get worse)
1188 [ + - ]: 196 : auto post_post_linearization = post_linearization;
1189 [ - + + - ]: 196 : PostLinearize(depgraph, post_post_linearization);
1190 [ - + ]: 196 : SanityCheck(depgraph, post_post_linearization);
1191 [ - + ]: 196 : auto post_post_chunking = ChunkLinearization(depgraph, post_post_linearization);
1192 [ - + - + : 196 : cmp = CompareChunks(post_post_chunking, post_chunking);
+ - ]
1193 [ - + ]: 196 : assert(cmp >= 0);
1194 : :
1195 : : // The chunks that come out of postlinearizing are always connected.
1196 [ - + ]: 196 : auto linchunking = ChunkLinearizationInfo(depgraph, post_linearization);
1197 [ + + ]: 1712 : for (const auto& [chunk_set, _chunk_feerate] : linchunking) {
1198 [ - + ]: 1516 : assert(depgraph.IsConnected(chunk_set));
1199 : : }
1200 : 196 : }
1201 : :
1202 [ + - ]: 918 : FUZZ_TARGET(clusterlin_postlinearize_tree)
1203 : : {
1204 : : // Verify expected properties of PostLinearize() on linearizations of graphs that form either
1205 : : // an upright or reverse tree structure.
1206 : :
1207 : : // Construct a direction, RNG seed, and an arbitrary graph from the fuzz input.
1208 : 442 : SpanReader reader(buffer);
1209 : 442 : uint64_t rng_seed{0};
1210 : 442 : DepGraph<TestBitSet> depgraph_gen;
1211 : 442 : uint8_t direction{0};
1212 : 442 : try {
1213 [ + - + + : 442 : reader >> direction >> rng_seed >> Using<DepGraphFormatter>(depgraph_gen);
+ - ]
1214 [ - + ]: 4 : } catch (const std::ios_base::failure&) {}
1215 : :
1216 : 442 : auto depgraph_tree = BuildTreeGraph(depgraph_gen, direction);
1217 : :
1218 : : // Retrieve a linearization from the fuzz input.
1219 : 442 : std::vector<DepGraphIndex> linearization;
1220 [ + - ]: 884 : linearization = ReadLinearization(depgraph_tree, reader);
1221 [ - + ]: 442 : SanityCheck(depgraph_tree, linearization);
1222 : :
1223 : : // Produce a postlinearized version.
1224 [ + - ]: 442 : auto post_linearization = linearization;
1225 [ - + + - ]: 442 : PostLinearize(depgraph_tree, post_linearization);
1226 [ - + ]: 442 : SanityCheck(depgraph_tree, post_linearization);
1227 : :
1228 : : // Compare diagrams.
1229 [ - + ]: 442 : auto chunking = ChunkLinearization(depgraph_tree, linearization);
1230 [ - + ]: 442 : auto post_chunking = ChunkLinearization(depgraph_tree, post_linearization);
1231 [ - + - + : 442 : auto cmp = CompareChunks(post_chunking, chunking);
+ - ]
1232 [ - + ]: 442 : assert(cmp >= 0);
1233 : :
1234 : : // Verify that post-linearizing again does not change the diagram. The result must be identical
1235 : : // as post_linearization ought to be optimal already with a tree-structured graph.
1236 [ + - ]: 442 : auto post_post_linearization = post_linearization;
1237 [ - + + - ]: 442 : PostLinearize(depgraph_tree, post_post_linearization);
1238 [ - + ]: 442 : SanityCheck(depgraph_tree, post_post_linearization);
1239 [ - + ]: 442 : auto post_post_chunking = ChunkLinearization(depgraph_tree, post_post_linearization);
1240 [ - + - + : 442 : auto cmp_post = CompareChunks(post_post_chunking, post_chunking);
+ - ]
1241 [ - + ]: 442 : assert(cmp_post == 0);
1242 : :
1243 : : // Try to find an even better linearization directly. This must not change the diagram for the
1244 : : // same reason.
1245 [ - + - + ]: 442 : auto [opt_linearization, _optimal, _cost] = Linearize(depgraph_tree, 1000000, rng_seed, IndexTxOrder{}, post_linearization);
1246 [ - + ]: 442 : auto opt_chunking = ChunkLinearization(depgraph_tree, opt_linearization);
1247 [ - + - + : 442 : auto cmp_opt = CompareChunks(opt_chunking, post_chunking);
+ - ]
1248 [ - + ]: 442 : assert(cmp_opt == 0);
1249 : 442 : }
1250 : :
1251 [ + - ]: 662 : FUZZ_TARGET(clusterlin_postlinearize_moved_leaf)
1252 : : {
1253 : : // Verify that taking an existing linearization, and moving a leaf to the back, potentially
1254 : : // increasing its fee, and then post-linearizing, results in something as good as the
1255 : : // original. This guarantees that in an RBF that replaces a transaction with one of the same
1256 : : // size but higher fee, applying the "remove conflicts, append new transaction, postlinearize"
1257 : : // process will never worsen linearization quality.
1258 : :
1259 : : // Construct an arbitrary graph and a fee from the fuzz input.
1260 : 186 : SpanReader reader(buffer);
1261 : 186 : DepGraph<TestBitSet> depgraph;
1262 : 186 : int32_t fee_inc{0};
1263 : 186 : try {
1264 : 186 : uint64_t fee_inc_code;
1265 [ + - + + ]: 186 : reader >> Using<DepGraphFormatter>(depgraph) >> VARINT(fee_inc_code);
1266 : 70 : fee_inc = fee_inc_code & 0x3ffff;
1267 [ - + ]: 116 : } catch (const std::ios_base::failure&) {}
1268 [ + + ]: 186 : if (depgraph.TxCount() == 0) return;
1269 : :
1270 : : // Retrieve two linearizations from the fuzz input.
1271 [ + - ]: 176 : auto lin = ReadLinearization(depgraph, reader);
1272 [ + - ]: 176 : auto lin_leaf = ReadLinearization(depgraph, reader);
1273 : :
1274 : : // Construct a linearization identical to lin, but with the tail end of lin_leaf moved to the
1275 : : // back.
1276 : 176 : std::vector<DepGraphIndex> lin_moved;
1277 [ + + ]: 2319 : for (auto i : lin) {
1278 [ + + + - ]: 2143 : if (i != lin_leaf.back()) lin_moved.push_back(i);
1279 : : }
1280 [ + - ]: 176 : lin_moved.push_back(lin_leaf.back());
1281 : :
1282 : : // Postlinearize lin_moved.
1283 [ - + + - ]: 176 : PostLinearize(depgraph, lin_moved);
1284 [ - + ]: 176 : SanityCheck(depgraph, lin_moved);
1285 : :
1286 : : // Compare diagrams (applying the fee delta after computing the old one).
1287 [ - + ]: 176 : auto old_chunking = ChunkLinearization(depgraph, lin);
1288 [ - + ]: 176 : depgraph.FeeRate(lin_leaf.back()).fee += fee_inc;
1289 [ - + ]: 176 : auto new_chunking = ChunkLinearization(depgraph, lin_moved);
1290 [ - + - + : 176 : auto cmp = CompareChunks(new_chunking, old_chunking);
+ - ]
1291 [ - + ]: 176 : assert(cmp >= 0);
1292 : 186 : }
|
