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