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 : : * | SearchCandidateFinder | <<---------------------\
29 : : * +-----------------------+ |
30 : : * | +-----------+
31 : : * | | Linearize |
32 : : * | +-----------+
33 : : * | +-------------------------+ | |
34 : : * | | AncestorCandidateFinder | <<--------/ |
35 : : * | +-------------------------+ |
36 : : * | | ^ | ^^ PRODUCTION CODE
37 : : * | | | | ||
38 : : * ==============================================================================================
39 : : * | | | | ||
40 : : * | clusterlin_ancestor_finder* | | vv TEST CODE
41 : : * | | |
42 : : * |-clusterlin_search_finder* | |-clusterlin_linearize*
43 : : * | | |
44 : : * v | v
45 : : * +-----------------------+ | +-----------------+
46 : : * | SimpleCandidateFinder | <<-------------------| SimpleLinearize |
47 : : * +-----------------------+ | +-----------------+
48 : : * | | |
49 : : * +-------------------/ |
50 : : * | |
51 : : * |-clusterlin_simple_finder* |-clusterlin_simple_linearize*
52 : : * v v
53 : : * +---------------------------+ +---------------------+
54 : : * | ExhaustiveCandidateFinder | | ExhaustiveLinearize |
55 : : * +---------------------------+ +---------------------+
56 : : *
57 : : * More tests are included for lower-level and related functions and classes:
58 : : * - DepGraph tests:
59 : : * - clusterlin_depgraph_sim
60 : : * - clusterlin_depgraph_serialization
61 : : * - clusterlin_components
62 : : * - ChunkLinearization and LinearizationChunking tests:
63 : : * - clusterlin_chunking
64 : : * - clusterlin_linearization_chunking
65 : : * - PostLinearize tests:
66 : : * - clusterlin_postlinearize
67 : : * - clusterlin_postlinearize_tree
68 : : * - clusterlin_postlinearize_moved_leaf
69 : : * - MergeLinearization tests:
70 : : * - clusterlin_merge
71 : : * - FixLinearization tests:
72 : : * - clusterlin_fix_linearization
73 : : * - MakeConnected tests (a test-only function):
74 : : * - clusterlin_make_connected
75 : : */
76 : :
77 : : using namespace cluster_linearize;
78 : :
79 : : namespace {
80 : :
81 : : /** A simple finder class for candidate sets.
82 : : *
83 : : * This class matches SearchCandidateFinder in interface and behavior, though with fewer
84 : : * optimizations.
85 : : */
86 : : template<typename SetType>
87 : : class SimpleCandidateFinder
88 : : {
89 : : /** Internal dependency graph. */
90 : : const DepGraph<SetType>& m_depgraph;
91 : : /** Which transaction are left to include. */
92 : : SetType m_todo;
93 : :
94 : : public:
95 : : /** Construct an SimpleCandidateFinder for a given graph. */
96 : 1060 : SimpleCandidateFinder(const DepGraph<SetType>& depgraph LIFETIMEBOUND) noexcept :
97 : 1060 : m_depgraph(depgraph), m_todo{depgraph.Positions()} {}
98 : :
99 : : /** Remove a set of transactions from the set of to-be-linearized ones. */
100 : 10175 : void MarkDone(SetType select) noexcept { m_todo -= select; }
101 : :
102 : : /** Determine whether unlinearized transactions remain. */
103 : 7215 : bool AllDone() const noexcept { return m_todo.None(); }
104 : :
105 : : /** Find a candidate set using at most max_iterations iterations, and the number of iterations
106 : : * actually performed. If that number is less than max_iterations, then the result is optimal.
107 : : *
108 : : * Always returns a connected set of transactions.
109 : : *
110 : : * Complexity: O(N * M), where M is the number of connected topological subsets of the cluster.
111 : : * That number is bounded by M <= 2^(N-1).
112 : : */
113 : 5936 : std::pair<SetInfo<SetType>, uint64_t> FindCandidateSet(uint64_t max_iterations) const noexcept
114 : : {
115 : 5936 : uint64_t iterations_left = max_iterations;
116 : : // Queue of work units. Each consists of:
117 : : // - inc: set of transactions definitely included
118 : : // - und: set of transactions that can be added to inc still
119 : 5936 : std::vector<std::pair<SetType, SetType>> queue;
120 : : // Initially we have just one queue element, with the entire graph in und.
121 : 5936 : queue.emplace_back(SetType{}, m_todo);
122 : : // Best solution so far. Initialize with the remaining ancestors of the first remaining
123 : : // transaction.
124 : 5936 : SetInfo best(m_depgraph, m_depgraph.Ancestors(m_todo.First()) & m_todo);
125 : : // Process the queue.
126 [ + + + + ]: 27124033 : while (!queue.empty() && iterations_left) {
127 : : // Pop top element of the queue.
128 : 27118097 : auto [inc, und] = queue.back();
129 : 27118097 : queue.pop_back();
130 : : // Look for a transaction to consider adding/removing.
131 : 27118097 : bool inc_none = inc.None();
132 [ + + ]: 38527719 : for (auto split : und) {
133 : : // If inc is empty, consider any split transaction. Otherwise only consider
134 : : // transactions that share ancestry with inc so far (which means only connected
135 : : // sets will be considered).
136 [ + + + + ]: 24966106 : if (inc_none || inc.Overlaps(m_depgraph.Ancestors(split))) {
137 : 13556484 : --iterations_left;
138 : : // Add a queue entry with split included.
139 : 13556484 : SetInfo new_inc(m_depgraph, inc | (m_todo & m_depgraph.Ancestors(split)));
140 : 13556484 : queue.emplace_back(new_inc.transactions, und - new_inc.transactions);
141 : : // Add a queue entry with split excluded.
142 : 13556484 : queue.emplace_back(inc, und - m_depgraph.Descendants(split));
143 : : // Update statistics to account for the candidate new_inc.
144 [ + + ]: 13556484 : if (new_inc.feerate > best.feerate) best = new_inc;
145 : : break;
146 : : }
147 : : }
148 : : }
149 : 5936 : return {std::move(best), max_iterations - iterations_left};
150 : 5936 : }
151 : : };
152 : :
153 : : /** A very simple finder class for optimal candidate sets, which tries every subset.
154 : : *
155 : : * It is even simpler than SimpleCandidateFinder, and exists just to help test the correctness of
156 : : * SimpleCandidateFinder, which is then used to test the correctness of SearchCandidateFinder.
157 : : */
158 : : template<typename SetType>
159 : : class ExhaustiveCandidateFinder
160 : : {
161 : : /** Internal dependency graph. */
162 : : const DepGraph<SetType>& m_depgraph;
163 : : /** Which transaction are left to include. */
164 : : SetType m_todo;
165 : :
166 : : public:
167 : : /** Construct an ExhaustiveCandidateFinder for a given graph. */
168 : 85 : ExhaustiveCandidateFinder(const DepGraph<SetType>& depgraph LIFETIMEBOUND) noexcept :
169 : 85 : m_depgraph(depgraph), m_todo{depgraph.Positions()} {}
170 : :
171 : : /** Remove a set of transactions from the set of to-be-linearized ones. */
172 : 762 : void MarkDone(SetType select) noexcept { m_todo -= select; }
173 : :
174 : : /** Determine whether unlinearized transactions remain. */
175 : 847 : bool AllDone() const noexcept { return m_todo.None(); }
176 : :
177 : : /** Find the optimal remaining candidate set.
178 : : *
179 : : * Complexity: O(N * 2^N).
180 : : */
181 : 488 : SetInfo<SetType> FindCandidateSet() const noexcept
182 : : {
183 : : // Best solution so far.
184 : 488 : SetInfo<SetType> best{m_todo, m_depgraph.FeeRate(m_todo)};
185 : : // The number of combinations to try.
186 : 488 : uint64_t limit = (uint64_t{1} << m_todo.Count()) - 1;
187 : : // Try the transitive closure of every non-empty subset of m_todo.
188 [ + + ]: 221504 : for (uint64_t x = 1; x < limit; ++x) {
189 : : // If bit number b is set in x, then the remaining ancestors of the b'th remaining
190 : : // transaction in m_todo are included.
191 : 221016 : SetType txn;
192 : 221016 : auto x_shifted{x};
193 [ + - + + ]: 2839276 : for (auto i : m_todo) {
194 [ + + ]: 2397244 : if (x_shifted & 1) txn |= m_depgraph.Ancestors(i);
195 : 2397244 : x_shifted >>= 1;
196 : : }
197 : 221016 : SetInfo cur(m_depgraph, txn & m_todo);
198 [ + + ]: 221016 : if (cur.feerate > best.feerate) best = cur;
199 : : }
200 : 488 : return best;
201 : : }
202 : : };
203 : :
204 : : /** A simple linearization algorithm.
205 : : *
206 : : * This matches Linearize() in interface and behavior, though with fewer optimizations, lacking
207 : : * the ability to pass in an existing linearization, and using just SimpleCandidateFinder rather
208 : : * than AncestorCandidateFinder and SearchCandidateFinder.
209 : : */
210 : : template<typename SetType>
211 : 536 : std::pair<std::vector<DepGraphIndex>, bool> SimpleLinearize(const DepGraph<SetType>& depgraph, uint64_t max_iterations)
212 : : {
213 : 536 : std::vector<DepGraphIndex> linearization;
214 : 536 : SimpleCandidateFinder finder(depgraph);
215 : 536 : SetType todo = depgraph.Positions();
216 : 536 : bool optimal = true;
217 [ + + ]: 4020 : while (todo.Any()) {
218 [ + + ]: 3484 : auto [candidate, iterations_done] = finder.FindCandidateSet(max_iterations);
219 [ + + ]: 3484 : if (iterations_done == max_iterations) optimal = false;
220 : 3484 : depgraph.AppendTopo(linearization, candidate.transactions);
221 : 3484 : todo -= candidate.transactions;
222 : 3484 : finder.MarkDone(candidate.transactions);
223 : 3484 : max_iterations -= iterations_done;
224 : : }
225 : 536 : return {std::move(linearization), optimal};
226 : 536 : }
227 : :
228 : : /** An even simpler linearization algorithm that tries all permutations.
229 : : *
230 : : * This roughly matches SimpleLinearize() (and Linearize) in interface and behavior, but always
231 : : * tries all topologically-valid transaction orderings, has no way to bound how much work it does,
232 : : * and always finds the optimal. With an O(n!) complexity, it should only be used for small
233 : : * clusters.
234 : : */
235 : : template<typename SetType>
236 : 61 : std::vector<DepGraphIndex> ExhaustiveLinearize(const DepGraph<SetType>& depgraph)
237 : : {
238 : : // The best linearization so far, and its chunking.
239 : 61 : std::vector<DepGraphIndex> linearization;
240 : 61 : std::vector<FeeFrac> chunking;
241 : :
242 [ + + ]: 61 : std::vector<DepGraphIndex> perm_linearization;
243 : : // Initialize with the lexicographically-first linearization.
244 [ + + + - : 440 : for (DepGraphIndex i : depgraph.Positions()) perm_linearization.push_back(i);
+ + ]
245 : : // Iterate over all valid permutations.
246 : : do {
247 : : /** What prefix of perm_linearization is topological. */
248 : 324005 : DepGraphIndex topo_length{0};
249 : 324005 : TestBitSet perm_done;
250 [ - + + + ]: 2767105 : while (topo_length < perm_linearization.size()) {
251 : 2483355 : auto i = perm_linearization[topo_length];
252 [ + + ]: 2483355 : perm_done.Set(i);
253 [ + + ]: 2483355 : if (!depgraph.Ancestors(i).IsSubsetOf(perm_done)) break;
254 : 2443100 : ++topo_length;
255 : : }
256 [ - + + + ]: 324005 : if (topo_length == perm_linearization.size()) {
257 : : // If all of perm_linearization is topological, check if it is perhaps our best
258 : : // linearization so far.
259 [ - + ]: 283750 : auto perm_chunking = ChunkLinearization(depgraph, perm_linearization);
260 [ - + + - ]: 283750 : auto cmp = CompareChunks(perm_chunking, chunking);
261 : : // If the diagram is better, or if it is equal but with more chunks (because we
262 : : // prefer minimal chunks), consider this better.
263 [ + + + + : 330381 : if (linearization.empty() || cmp > 0 || (cmp == 0 && perm_chunking.size() > chunking.size())) {
+ + - + +
+ ]
264 [ + - ]: 587 : linearization = perm_linearization;
265 [ + - ]: 587 : chunking = perm_chunking;
266 : : }
267 : 283750 : } else {
268 : : // Otherwise, fast forward to the last permutation with the same non-topological
269 : : // prefix.
270 : 40255 : auto first_non_topo = perm_linearization.begin() + topo_length;
271 [ - + ]: 40255 : assert(std::is_sorted(first_non_topo + 1, perm_linearization.end()));
272 : 40255 : std::reverse(first_non_topo + 1, perm_linearization.end());
273 : : }
274 [ + + ]: 324005 : } while(std::next_permutation(perm_linearization.begin(), perm_linearization.end()));
275 : :
276 : 61 : return linearization;
277 : 61 : }
278 : :
279 : :
280 : : /** Stitch connected components together in a DepGraph, guaranteeing its corresponding cluster is connected. */
281 : : template<typename BS>
282 : 1139 : void MakeConnected(DepGraph<BS>& depgraph)
283 : : {
284 : 1139 : auto todo = depgraph.Positions();
285 : 1139 : auto comp = depgraph.FindConnectedComponent(todo);
286 : 1139 : Assume(depgraph.IsConnected(comp));
287 : 1139 : todo -= comp;
288 [ + + ]: 13327 : while (todo.Any()) {
289 : 12188 : auto nextcomp = depgraph.FindConnectedComponent(todo);
290 : 12188 : Assume(depgraph.IsConnected(nextcomp));
291 : 12188 : depgraph.AddDependencies(BS::Singleton(comp.Last()), nextcomp.First());
292 : 12188 : todo -= nextcomp;
293 : 12188 : comp = nextcomp;
294 : : }
295 : 1139 : }
296 : :
297 : : /** Given a dependency graph, and a todo set, read a topological subset of todo from reader. */
298 : : template<typename SetType>
299 : 18177 : SetType ReadTopologicalSet(const DepGraph<SetType>& depgraph, const SetType& todo, SpanReader& reader, bool non_empty)
300 : : {
301 : : // Read a bitmask from the fuzzing input. Add 1 if non_empty, so the mask is definitely not
302 : : // zero in that case.
303 [ + + ]: 18177 : uint64_t mask{0};
304 : : try {
305 [ + + ]: 18177 : reader >> VARINT(mask);
306 [ - + ]: 14208 : } catch(const std::ios_base::failure&) {}
307 [ + + ]: 18177 : if (mask != uint64_t(-1)) mask += non_empty;
308 : :
309 : 18177 : SetType ret;
310 [ + + + + ]: 263206 : for (auto i : todo) {
311 [ + + ]: 226859 : if (!ret[i]) {
312 [ + + ]: 221150 : if (mask & 1) ret |= depgraph.Ancestors(i);
313 : 221150 : mask >>= 1;
314 : : }
315 : : }
316 : 18177 : ret &= todo;
317 : :
318 : : // While mask starts off non-zero if non_empty is true, it is still possible that all its low
319 : : // bits are 0, and ret ends up being empty. As a last resort, use the in-todo ancestry of the
320 : : // first todo position.
321 [ + + + + ]: 18177 : if (non_empty && ret.None()) {
322 : 157 : Assume(todo.Any());
323 : 157 : ret = depgraph.Ancestors(todo.First()) & todo;
324 : 157 : Assume(ret.Any());
325 : : }
326 : 18177 : return ret;
327 : : }
328 : :
329 : : /** Given a dependency graph, construct any valid linearization for it, reading from a SpanReader. */
330 : : template<typename BS>
331 : 2433 : std::vector<DepGraphIndex> ReadLinearization(const DepGraph<BS>& depgraph, SpanReader& reader)
332 : : {
333 : 2433 : std::vector<DepGraphIndex> linearization;
334 : 2433 : TestBitSet todo = depgraph.Positions();
335 : : // In every iteration one topologically-valid transaction is appended to linearization.
336 [ + + ]: 49881 : while (todo.Any()) {
337 : : // Compute the set of transactions with no not-yet-included ancestors.
338 : 45015 : TestBitSet potential_next;
339 [ + + ]: 654308 : for (auto j : todo) {
340 [ + + ]: 944652 : if ((depgraph.Ancestors(j) & todo) == TestBitSet::Singleton(j)) {
341 : 335359 : potential_next.Set(j);
342 : : }
343 : : }
344 : : // There must always be one (otherwise there is a cycle in the graph).
345 [ - + ]: 45015 : assert(potential_next.Any());
346 : : // Read a number from reader, and interpret it as index into potential_next.
347 [ + + ]: 45015 : uint64_t idx{0};
348 : : try {
349 [ + + + - ]: 90030 : reader >> VARINT(idx);
350 [ - + ]: 36580 : } catch (const std::ios_base::failure&) {}
351 : 45015 : idx %= potential_next.Count();
352 : : // Find out which transaction that corresponds to.
353 [ + - + - ]: 115966 : for (auto j : potential_next) {
354 [ + + ]: 70951 : if (idx == 0) {
355 : : // When found, add it to linearization and remove it from todo.
356 [ + - ]: 45015 : linearization.push_back(j);
357 [ - + ]: 45015 : assert(todo[j]);
358 : 45015 : todo.Reset(j);
359 : 45015 : break;
360 : : }
361 : 25936 : --idx;
362 : : }
363 : : }
364 : 2433 : return linearization;
365 : 0 : }
366 : :
367 : : } // namespace
368 : :
369 [ + - ]: 785 : FUZZ_TARGET(clusterlin_depgraph_sim)
370 : : {
371 : : // Simulation test to verify the full behavior of DepGraph.
372 : :
373 : 329 : FuzzedDataProvider provider(buffer.data(), buffer.size());
374 : :
375 : : /** Real DepGraph being tested. */
376 : 329 : DepGraph<TestBitSet> real;
377 : : /** Simulated DepGraph (sim[i] is std::nullopt if position i does not exist; otherwise,
378 : : * sim[i]->first is its individual feerate, and sim[i]->second is its set of ancestors. */
379 : 329 : std::array<std::optional<std::pair<FeeFrac, TestBitSet>>, TestBitSet::Size()> sim;
380 : : /** The number of non-nullopt position in sim. */
381 : 329 : DepGraphIndex num_tx_sim{0};
382 : :
383 : : /** Read a valid index of a transaction from the provider. */
384 : 24946 : auto idx_fn = [&]() {
385 : 24617 : auto offset = provider.ConsumeIntegralInRange<DepGraphIndex>(0, num_tx_sim - 1);
386 [ + - ]: 212756 : for (DepGraphIndex i = 0; i < sim.size(); ++i) {
387 [ + + ]: 212756 : if (!sim[i].has_value()) continue;
388 [ + + ]: 189207 : if (offset == 0) return i;
389 : 164590 : --offset;
390 : : }
391 : 0 : assert(false);
392 : : return DepGraphIndex(-1);
393 : 329 : };
394 : :
395 : : /** Read a valid subset of the transactions from the provider. */
396 : 24946 : auto subset_fn = [&]() {
397 : 24617 : auto range = (uint64_t{1} << num_tx_sim) - 1;
398 : 24617 : const auto mask = provider.ConsumeIntegralInRange<uint64_t>(0, range);
399 : 24617 : auto mask_shifted = mask;
400 : 24617 : TestBitSet subset;
401 [ + + ]: 812361 : for (DepGraphIndex i = 0; i < sim.size(); ++i) {
402 [ + + ]: 787744 : if (!sim[i].has_value()) continue;
403 [ + + ]: 499379 : if (mask_shifted & 1) {
404 : 164550 : subset.Set(i);
405 : : }
406 : 499379 : mask_shifted >>= 1;
407 : : }
408 [ - + ]: 24617 : assert(mask_shifted == 0);
409 : 24617 : return subset;
410 : 329 : };
411 : :
412 : : /** Read any set of transactions from the provider (including unused positions). */
413 : 13485 : auto set_fn = [&]() {
414 : 13156 : auto range = (uint64_t{1} << sim.size()) - 1;
415 : 13156 : const auto mask = provider.ConsumeIntegralInRange<uint64_t>(0, range);
416 : 13156 : TestBitSet set;
417 [ + + ]: 434148 : for (DepGraphIndex i = 0; i < sim.size(); ++i) {
418 [ + + ]: 420992 : if ((mask >> i) & 1) {
419 : 127949 : set.Set(i);
420 : : }
421 : : }
422 : 13156 : return set;
423 : 329 : };
424 : :
425 : : /** Propagate ancestor information in sim. */
426 : 13814 : auto anc_update_fn = [&]() {
427 : 15880 : while (true) {
428 : 15880 : bool updates{false};
429 [ + + ]: 524040 : for (DepGraphIndex chl = 0; chl < sim.size(); ++chl) {
430 [ + + ]: 508160 : if (!sim[chl].has_value()) continue;
431 [ + - + + ]: 1305111 : for (auto par : sim[chl]->second) {
432 [ + + ]: 821529 : if (!sim[chl]->second.IsSupersetOf(sim[par]->second)) {
433 : 12321 : sim[chl]->second |= sim[par]->second;
434 : 12321 : updates = true;
435 : : }
436 : : }
437 : : }
438 [ + + ]: 15880 : if (!updates) break;
439 : : }
440 : 13814 : };
441 : :
442 : : /** Compare the state of transaction i in the simulation with the real one. */
443 : 138806 : auto check_fn = [&](DepGraphIndex i) {
444 : : // Compare used positions.
445 [ - + ]: 138477 : assert(real.Positions()[i] == sim[i].has_value());
446 [ + + ]: 138477 : if (sim[i].has_value()) {
447 : : // Compare feerate.
448 [ + - ]: 26919 : assert(real.FeeRate(i) == sim[i]->first);
449 : : // Compare ancestors (note that SanityCheck verifies correspondence between ancestors
450 : : // and descendants, so we can restrict ourselves to ancestors here).
451 [ - + ]: 26919 : assert(real.Ancestors(i) == sim[i]->second);
452 : : }
453 : 138806 : };
454 : :
455 [ + + + + ]: 65021 : LIMITED_WHILE(provider.remaining_bytes() > 0, 1000) {
456 : 64692 : uint8_t command = provider.ConsumeIntegral<uint8_t>();
457 [ + + + + : 64692 : if (num_tx_sim == 0 || ((command % 3) <= 0 && num_tx_sim < TestBitSet::Size())) {
+ + ]
458 : : // AddTransaction.
459 : 26919 : auto fee = provider.ConsumeIntegralInRange<int64_t>(-0x8000000000000, 0x7ffffffffffff);
460 : 26919 : auto size = provider.ConsumeIntegralInRange<int32_t>(1, 0x3fffff);
461 : 26919 : FeeFrac feerate{fee, size};
462 : : // Apply to DepGraph.
463 : 26919 : auto idx = real.AddTransaction(feerate);
464 : : // Verify that the returned index is correct.
465 [ - + ]: 26919 : assert(!sim[idx].has_value());
466 [ + - ]: 393654 : for (DepGraphIndex i = 0; i < TestBitSet::Size(); ++i) {
467 [ + + ]: 393654 : if (!sim[i].has_value()) {
468 [ - + ]: 26919 : assert(idx == i);
469 : : break;
470 : : }
471 : : }
472 : : // Update sim.
473 [ - + ]: 26919 : sim[idx] = {feerate, TestBitSet::Singleton(idx)};
474 : 26919 : ++num_tx_sim;
475 : 26919 : continue;
476 : 26919 : }
477 [ + + ]: 37773 : if ((command % 3) <= 1 && num_tx_sim > 0) {
478 : : // AddDependencies.
479 : 24617 : DepGraphIndex child = idx_fn();
480 : 24617 : auto parents = subset_fn();
481 : : // Apply to DepGraph.
482 : 24617 : real.AddDependencies(parents, child);
483 : : // Apply to sim.
484 : 24617 : sim[child]->second |= parents;
485 : 24617 : continue;
486 : 24617 : }
487 : 13156 : if (num_tx_sim > 0) {
488 : : // Remove transactions.
489 : 13156 : auto del = set_fn();
490 : : // Propagate all ancestry information before deleting anything in the simulation (as
491 : : // intermediary transactions may be deleted which impact connectivity).
492 : 13156 : anc_update_fn();
493 : : // Compare the state of the transactions being deleted.
494 [ + + + + ]: 152095 : for (auto i : del) check_fn(i);
495 : : // Apply to DepGraph.
496 : 13156 : real.RemoveTransactions(del);
497 : : // Apply to sim.
498 [ + + ]: 434148 : for (DepGraphIndex i = 0; i < sim.size(); ++i) {
499 [ + + ]: 420992 : if (sim[i].has_value()) {
500 [ + + ]: 181340 : if (del[i]) {
501 : 21650 : --num_tx_sim;
502 [ + - ]: 442642 : sim[i] = std::nullopt;
503 : : } else {
504 : 159690 : sim[i]->second -= del;
505 : : }
506 : : }
507 : : }
508 : 13156 : continue;
509 : 13156 : }
510 : : // This should be unreachable (one of the 3 above actions should always be possible).
511 : : assert(false);
512 : : }
513 : :
514 : : // Compare the real obtained depgraph against the simulation.
515 : 329 : anc_update_fn();
516 [ + + ]: 10857 : for (DepGraphIndex i = 0; i < sim.size(); ++i) check_fn(i);
517 [ - + ]: 329 : assert(real.TxCount() == num_tx_sim);
518 : : // Sanity check the result (which includes round-tripping serialization, if applicable).
519 [ + - ]: 329 : SanityCheck(real);
520 : 329 : }
521 : :
522 [ + - ]: 692 : FUZZ_TARGET(clusterlin_depgraph_serialization)
523 : : {
524 : : // Verify that any deserialized depgraph is acyclic and roundtrips to an identical depgraph.
525 : :
526 : : // Construct a graph by deserializing.
527 : 236 : SpanReader reader(buffer);
528 : 236 : DepGraph<TestBitSet> depgraph;
529 : 236 : DepGraphIndex par_code{0}, chl_code{0};
530 : 236 : try {
531 [ + - + + : 236 : reader >> Using<DepGraphFormatter>(depgraph) >> VARINT(par_code) >> VARINT(chl_code);
+ + ]
532 [ - + ]: 192 : } catch (const std::ios_base::failure&) {}
533 [ + - ]: 236 : SanityCheck(depgraph);
534 : :
535 : : // Verify the graph is a DAG.
536 [ - + ]: 236 : assert(depgraph.IsAcyclic());
537 : :
538 : : // Introduce a cycle, and then test that IsAcyclic returns false.
539 [ + + ]: 236 : if (depgraph.TxCount() < 2) return;
540 : 216 : DepGraphIndex par(0), chl(0);
541 : : // Pick any transaction of depgraph as parent.
542 [ + - ]: 216 : par_code %= depgraph.TxCount();
543 [ + - + - ]: 713 : for (auto i : depgraph.Positions()) {
544 [ + + ]: 497 : if (par_code == 0) {
545 : : par = i;
546 : : break;
547 : : }
548 : 281 : --par_code;
549 : : }
550 : : // Pick any ancestor of par (excluding itself) as child, if any.
551 [ + + ]: 216 : auto ancestors = depgraph.Ancestors(par) - TestBitSet::Singleton(par);
552 [ + + ]: 216 : if (ancestors.None()) return;
553 : 106 : chl_code %= ancestors.Count();
554 [ + - ]: 209 : for (auto i : ancestors) {
555 [ + + ]: 209 : if (chl_code == 0) {
556 : : chl = i;
557 : : break;
558 : : }
559 : 103 : --chl_code;
560 : : }
561 : : // Add the cycle-introducing dependency.
562 : 106 : depgraph.AddDependencies(TestBitSet::Singleton(par), chl);
563 : : // Check that we now detect a cycle.
564 [ - + ]: 106 : assert(!depgraph.IsAcyclic());
565 : 236 : }
566 : :
567 [ + - ]: 610 : FUZZ_TARGET(clusterlin_components)
568 : : {
569 : : // Verify the behavior of DepGraphs's FindConnectedComponent and IsConnected functions.
570 : :
571 : : // Construct a depgraph.
572 : 154 : SpanReader reader(buffer);
573 : 154 : DepGraph<TestBitSet> depgraph;
574 : 154 : std::vector<DepGraphIndex> linearization;
575 : 154 : try {
576 [ + - ]: 154 : reader >> Using<DepGraphFormatter>(depgraph);
577 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
578 : :
579 : 154 : TestBitSet todo = depgraph.Positions();
580 [ + + ]: 2041 : while (todo.Any()) {
581 : : // Pick a transaction in todo, or nothing.
582 : 1887 : std::optional<DepGraphIndex> picked;
583 : 1887 : {
584 : 1887 : uint64_t picked_num{0};
585 : 1887 : try {
586 [ + + ]: 1887 : reader >> VARINT(picked_num);
587 [ - + ]: 1291 : } catch (const std::ios_base::failure&) {}
588 [ + + + + ]: 1887 : if (picked_num < todo.Size() && todo[picked_num]) {
589 : 203 : picked = picked_num;
590 : : }
591 : : }
592 : :
593 : : // Find a connected component inside todo, including picked if any.
594 [ + + ]: 1887 : auto component = picked ? depgraph.GetConnectedComponent(todo, *picked)
595 : 1684 : : depgraph.FindConnectedComponent(todo);
596 : :
597 : : // The component must be a subset of todo and non-empty.
598 [ - + ]: 1887 : assert(component.IsSubsetOf(todo));
599 [ - + ]: 1887 : assert(component.Any());
600 : :
601 : : // If picked was provided, the component must include it.
602 [ + + - + ]: 1887 : if (picked) assert(component[*picked]);
603 : :
604 : : // If todo is the entire graph, and the entire graph is connected, then the component must
605 : : // be the entire graph.
606 [ + + ]: 1887 : if (todo == depgraph.Positions()) {
607 [ + + - + ]: 252 : assert((component == todo) == depgraph.IsConnected());
608 : : }
609 : :
610 : : // If subset is connected, then component must match subset.
611 [ + + - + ]: 3271 : assert((component == todo) == depgraph.IsConnected(todo));
612 : :
613 : : // The component cannot have any ancestors or descendants outside of component but in todo.
614 [ + - + + ]: 14122 : for (auto i : component) {
615 [ - + ]: 10348 : assert((depgraph.Ancestors(i) & todo).IsSubsetOf(component));
616 [ - + ]: 10348 : assert((depgraph.Descendants(i) & todo).IsSubsetOf(component));
617 : : }
618 : :
619 : : // Starting from any component element, we must be able to reach every element.
620 [ + - + + ]: 14122 : for (auto i : component) {
621 : : // Start with just i as reachable.
622 : 10348 : TestBitSet reachable = TestBitSet::Singleton(i);
623 : : // Add in-todo descendants and ancestors to reachable until it does not change anymore.
624 : 75984 : while (true) {
625 : 43166 : TestBitSet new_reachable = reachable;
626 [ + - + + ]: 528355 : for (auto j : new_reachable) {
627 : 442023 : new_reachable |= depgraph.Ancestors(j) & todo;
628 : 442023 : new_reachable |= depgraph.Descendants(j) & todo;
629 : : }
630 [ + + ]: 43166 : if (new_reachable == reachable) break;
631 : 32818 : reachable = new_reachable;
632 : 32818 : }
633 : : // Verify that the result is the entire component.
634 [ - + ]: 10348 : assert(component == reachable);
635 : : }
636 : :
637 : : // Construct an arbitrary subset of todo.
638 : 1887 : uint64_t subset_bits{0};
639 : 1887 : try {
640 [ + + ]: 1887 : reader >> VARINT(subset_bits);
641 [ - + ]: 1313 : } catch (const std::ios_base::failure&) {}
642 : 1887 : TestBitSet subset;
643 [ + - + + ]: 47113 : for (DepGraphIndex i : depgraph.Positions()) {
644 [ + + ]: 43339 : if (todo[i]) {
645 [ + + ]: 22499 : if (subset_bits & 1) subset.Set(i);
646 : 22499 : subset_bits >>= 1;
647 : : }
648 : : }
649 : : // Which must be non-empty.
650 [ + + ]: 1887 : if (subset.None()) subset = TestBitSet::Singleton(todo.First());
651 : : // Remove it from todo.
652 : 1887 : todo -= subset;
653 : : }
654 : :
655 : : // No components can be found in an empty subset.
656 [ - + ]: 154 : assert(depgraph.FindConnectedComponent(todo).None());
657 : 154 : }
658 : :
659 [ + - ]: 692 : FUZZ_TARGET(clusterlin_make_connected)
660 : : {
661 : : // Verify that MakeConnected makes graphs connected.
662 : :
663 : 236 : SpanReader reader(buffer);
664 : 236 : DepGraph<TestBitSet> depgraph;
665 : 236 : try {
666 [ + - ]: 236 : reader >> Using<DepGraphFormatter>(depgraph);
667 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
668 [ + - ]: 236 : MakeConnected(depgraph);
669 [ + - ]: 236 : SanityCheck(depgraph);
670 [ - + ]: 236 : assert(depgraph.IsConnected());
671 : 236 : }
672 : :
673 [ + - ]: 568 : FUZZ_TARGET(clusterlin_chunking)
674 : : {
675 : : // Verify the correctness of the ChunkLinearization function.
676 : :
677 : : // Construct a graph by deserializing.
678 : 112 : SpanReader reader(buffer);
679 : 112 : DepGraph<TestBitSet> depgraph;
680 : 112 : try {
681 [ + - ]: 112 : reader >> Using<DepGraphFormatter>(depgraph);
682 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
683 : :
684 : : // Read a valid linearization for depgraph.
685 [ + - ]: 112 : auto linearization = ReadLinearization(depgraph, reader);
686 : :
687 : : // Invoke the chunking function.
688 [ - + ]: 112 : auto chunking = ChunkLinearization(depgraph, linearization);
689 : :
690 : : // Verify that chunk feerates are monotonically non-increasing.
691 [ - + + + ]: 467 : for (size_t i = 1; i < chunking.size(); ++i) {
692 [ - + ]: 355 : assert(!(chunking[i] >> chunking[i - 1]));
693 : : }
694 : :
695 : : // Naively recompute the chunks (each is the highest-feerate prefix of what remains).
696 : 112 : auto todo = depgraph.Positions();
697 [ + + ]: 572 : for (const auto& chunk_feerate : chunking) {
698 [ - + ]: 460 : assert(todo.Any());
699 : 460 : SetInfo<TestBitSet> accumulator, best;
700 [ + + ]: 9999 : for (DepGraphIndex idx : linearization) {
701 [ + + ]: 9539 : if (todo[idx]) {
702 : 5091 : accumulator.Set(depgraph, idx);
703 [ + + + + ]: 5091 : if (best.feerate.IsEmpty() || accumulator.feerate >> best.feerate) {
704 : 1001 : best = accumulator;
705 : : }
706 : : }
707 : : }
708 [ + - ]: 460 : assert(chunk_feerate == best.feerate);
709 [ - + ]: 460 : assert(best.transactions.IsSubsetOf(todo));
710 : 460 : todo -= best.transactions;
711 : : }
712 [ - + ]: 112 : assert(todo.None());
713 : 112 : }
714 : :
715 [ + - ]: 622 : FUZZ_TARGET(clusterlin_ancestor_finder)
716 : : {
717 : : // Verify that AncestorCandidateFinder works as expected.
718 : :
719 : : // Retrieve a depgraph from the fuzz input.
720 : 166 : SpanReader reader(buffer);
721 : 166 : DepGraph<TestBitSet> depgraph;
722 : 166 : try {
723 [ + - ]: 166 : reader >> Using<DepGraphFormatter>(depgraph);
724 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
725 : :
726 : 166 : AncestorCandidateFinder anc_finder(depgraph);
727 : 166 : auto todo = depgraph.Positions();
728 [ + + ]: 1442 : while (todo.Any()) {
729 : : // Call the ancestor finder's FindCandidateSet for what remains of the graph.
730 [ - + ]: 1276 : assert(!anc_finder.AllDone());
731 [ - + ]: 1276 : assert(todo.Count() == anc_finder.NumRemaining());
732 : 1276 : auto best_anc = anc_finder.FindCandidateSet();
733 : : // Sanity check the result.
734 [ - + ]: 1276 : assert(best_anc.transactions.Any());
735 [ - + ]: 1276 : assert(best_anc.transactions.IsSubsetOf(todo));
736 [ + - ]: 1276 : assert(depgraph.FeeRate(best_anc.transactions) == best_anc.feerate);
737 [ - + ]: 1276 : assert(depgraph.IsConnected(best_anc.transactions));
738 : : // Check that it is topologically valid.
739 [ + - + + ]: 5325 : for (auto i : best_anc.transactions) {
740 [ - + ]: 2773 : assert((depgraph.Ancestors(i) & todo).IsSubsetOf(best_anc.transactions));
741 : : }
742 : :
743 : : // Compute all remaining ancestor sets.
744 : 1276 : std::optional<SetInfo<TestBitSet>> real_best_anc;
745 [ + - + + ]: 16635 : for (auto i : todo) {
746 : 14083 : SetInfo info(depgraph, todo & depgraph.Ancestors(i));
747 [ + + + + ]: 14083 : if (!real_best_anc.has_value() || info.feerate > real_best_anc->feerate) {
748 [ + + ]: 17207 : real_best_anc = info;
749 : : }
750 : : }
751 : : // The set returned by anc_finder must equal the real best ancestor sets.
752 [ - + ]: 1276 : assert(real_best_anc.has_value());
753 [ + - ]: 1276 : assert(*real_best_anc == best_anc);
754 : :
755 : : // Find a non-empty topologically valid subset of transactions to remove from the graph.
756 : : // Using an empty set would mean the next iteration is identical to the current one, and
757 : : // could cause an infinite loop.
758 [ + - ]: 1276 : auto del_set = ReadTopologicalSet(depgraph, todo, reader, /*non_empty=*/true);
759 : 1276 : todo -= del_set;
760 : 1276 : anc_finder.MarkDone(del_set);
761 : : }
762 [ - + ]: 166 : assert(anc_finder.AllDone());
763 [ - + ]: 166 : assert(anc_finder.NumRemaining() == 0);
764 : 166 : }
765 : :
766 : : static constexpr auto MAX_SIMPLE_ITERATIONS = 300000;
767 : :
768 [ + - ]: 541 : 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 and AncestorCandidateFinder.
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 to test
776 : : // SearchCandidateFinder below.
777 : :
778 : : // Retrieve a depgraph from the fuzz input.
779 : 85 : SpanReader reader(buffer);
780 : 85 : DepGraph<TestBitSet> depgraph;
781 : 85 : try {
782 [ + - ]: 85 : reader >> Using<DepGraphFormatter>(depgraph);
783 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
784 : :
785 : : // Instantiate the SimpleCandidateFinder to be tested, and the ExhaustiveCandidateFinder and
786 : : // AncestorCandidateFinder it is being tested against.
787 : 85 : SimpleCandidateFinder smp_finder(depgraph);
788 : 85 : ExhaustiveCandidateFinder exh_finder(depgraph);
789 : 85 : AncestorCandidateFinder anc_finder(depgraph);
790 : :
791 : 85 : auto todo = depgraph.Positions();
792 [ + + ]: 847 : while (todo.Any()) {
793 [ - + ]: 762 : assert(!smp_finder.AllDone());
794 [ - + ]: 762 : assert(!exh_finder.AllDone());
795 [ - + ]: 762 : assert(!anc_finder.AllDone());
796 [ - + ]: 762 : assert(anc_finder.NumRemaining() == todo.Count());
797 : :
798 : : // Call SimpleCandidateFinder.
799 [ - + ]: 762 : auto [found, iterations_done] = smp_finder.FindCandidateSet(MAX_SIMPLE_ITERATIONS);
800 : 762 : bool optimal = (iterations_done != MAX_SIMPLE_ITERATIONS);
801 : :
802 : : // Sanity check the result.
803 [ - + ]: 762 : assert(iterations_done <= MAX_SIMPLE_ITERATIONS);
804 [ - + ]: 762 : assert(found.transactions.Any());
805 [ - + ]: 762 : assert(found.transactions.IsSubsetOf(todo));
806 [ + - ]: 762 : assert(depgraph.FeeRate(found.transactions) == found.feerate);
807 : : // Check that it is topologically valid.
808 [ + - + + ]: 2787 : for (auto i : found.transactions) {
809 [ - + ]: 1263 : assert(found.transactions.IsSupersetOf(depgraph.Ancestors(i) & todo));
810 : : }
811 : :
812 : : // At most 2^(N-1) iterations can be required: the number of non-empty connected subsets a
813 : : // graph with N transactions can have. If MAX_SIMPLE_ITERATIONS exceeds this number, the
814 : : // result is necessarily optimal.
815 [ - + ]: 762 : assert(iterations_done <= (uint64_t{1} << (todo.Count() - 1)));
816 [ + + - + ]: 762 : if (MAX_SIMPLE_ITERATIONS > (uint64_t{1} << (todo.Count() - 1))) assert(optimal);
817 : :
818 : : // SimpleCandidateFinder only finds connected sets.
819 [ - + ]: 762 : assert(depgraph.IsConnected(found.transactions));
820 : :
821 : : // Perform further quality checks only if SimpleCandidateFinder claims an optimal result.
822 [ + + ]: 762 : if (optimal) {
823 : : // Compare with AncestorCandidateFinder.
824 : 747 : auto anc = anc_finder.FindCandidateSet();
825 [ - + ]: 747 : assert(anc.feerate <= found.feerate);
826 : :
827 [ + + ]: 747 : if (todo.Count() <= 12) {
828 : : // Compare with ExhaustiveCandidateFinder. This quickly gets computationally
829 : : // expensive for large clusters (O(2^n)), so only do it for sufficiently small ones.
830 : 488 : auto exhaustive = exh_finder.FindCandidateSet();
831 [ + - ]: 488 : assert(exhaustive.feerate == found.feerate);
832 : : }
833 : :
834 : : // Compare with a non-empty topological set read from the fuzz input (comparing with an
835 : : // empty set is not interesting).
836 [ + - ]: 747 : auto read_topo = ReadTopologicalSet(depgraph, todo, reader, /*non_empty=*/true);
837 [ - + ]: 747 : assert(found.feerate >= depgraph.FeeRate(read_topo));
838 : : }
839 : :
840 : : // Find a non-empty topologically valid subset of transactions to remove from the graph.
841 : : // Using an empty set would mean the next iteration is identical to the current one, and
842 : : // could cause an infinite loop.
843 [ + - ]: 762 : auto del_set = ReadTopologicalSet(depgraph, todo, reader, /*non_empty=*/true);
844 : 762 : todo -= del_set;
845 : 762 : smp_finder.MarkDone(del_set);
846 : 762 : exh_finder.MarkDone(del_set);
847 : 762 : anc_finder.MarkDone(del_set);
848 : : }
849 : :
850 [ - + ]: 85 : assert(smp_finder.AllDone());
851 [ - + ]: 85 : assert(exh_finder.AllDone());
852 [ - + ]: 85 : assert(anc_finder.AllDone());
853 [ - + ]: 85 : assert(anc_finder.NumRemaining() == 0);
854 : 85 : }
855 : :
856 [ + - ]: 895 : FUZZ_TARGET(clusterlin_search_finder)
857 : : {
858 : : // Verify that SearchCandidateFinder works as expected by sanity checking the results
859 : : // and comparing with the results from SimpleCandidateFinder and AncestorCandidateFinder,
860 : : // if the result is claimed to be optimal.
861 : :
862 : : // Retrieve an RNG seed, a depgraph, and whether to make it connected, from the fuzz input.
863 : 439 : SpanReader reader(buffer);
864 : 439 : DepGraph<TestBitSet> depgraph;
865 : 439 : uint64_t rng_seed{0};
866 : 439 : uint8_t make_connected{1};
867 : 439 : try {
868 [ + - + + : 439 : reader >> Using<DepGraphFormatter>(depgraph) >> rng_seed >> make_connected;
+ - ]
869 [ - + ]: 210 : } catch (const std::ios_base::failure&) {}
870 : : // The most complicated graphs are connected ones (other ones just split up). Optionally force
871 : : // the graph to be connected.
872 [ + + + - ]: 439 : if (make_connected) MakeConnected(depgraph);
873 : :
874 : : // Instantiate the candidate finders.
875 : 439 : SearchCandidateFinder src_finder(depgraph, rng_seed);
876 : 439 : SimpleCandidateFinder smp_finder(depgraph);
877 : 439 : AncestorCandidateFinder anc_finder(depgraph);
878 : :
879 : 439 : auto todo = depgraph.Positions();
880 [ + + ]: 6368 : while (todo.Any()) {
881 [ - + ]: 5929 : assert(!src_finder.AllDone());
882 [ - + ]: 5929 : assert(!smp_finder.AllDone());
883 [ - + ]: 5929 : assert(!anc_finder.AllDone());
884 [ - + ]: 5929 : assert(anc_finder.NumRemaining() == todo.Count());
885 : :
886 : : // For each iteration, read an iteration count limit from the fuzz input.
887 : 5929 : uint64_t max_iterations = 1;
888 : 5929 : try {
889 [ + + ]: 5929 : reader >> VARINT(max_iterations);
890 [ - + ]: 4717 : } catch (const std::ios_base::failure&) {}
891 : 5929 : max_iterations &= 0xfffff;
892 : :
893 : : // Read an initial subset from the fuzz input (allowed to be empty).
894 [ + - ]: 5929 : auto init_set = ReadTopologicalSet(depgraph, todo, reader, /*non_empty=*/false);
895 : 5929 : SetInfo init_best(depgraph, init_set);
896 : :
897 : : // Call the search finder's FindCandidateSet for what remains of the graph.
898 [ - + ]: 5929 : auto [found, iterations_done] = src_finder.FindCandidateSet(max_iterations, init_best);
899 : 5929 : bool optimal = iterations_done < max_iterations;
900 : :
901 : : // Sanity check the result.
902 [ - + ]: 5929 : assert(iterations_done <= max_iterations);
903 [ - + ]: 5929 : assert(found.transactions.Any());
904 [ - + ]: 5929 : assert(found.transactions.IsSubsetOf(todo));
905 [ + - ]: 5929 : assert(depgraph.FeeRate(found.transactions) == found.feerate);
906 [ + + - + ]: 5929 : if (!init_best.feerate.IsEmpty()) assert(found.feerate >= init_best.feerate);
907 : : // Check that it is topologically valid.
908 [ + - + + ]: 45952 : for (auto i : found.transactions) {
909 [ - + ]: 34094 : assert(found.transactions.IsSupersetOf(depgraph.Ancestors(i) & todo));
910 : : }
911 : :
912 : : // At most 2^(N-1) iterations can be required: the maximum number of non-empty topological
913 : : // subsets a (connected) cluster with N transactions can have. Even when the cluster is no
914 : : // longer connected after removing certain transactions, this holds, because the connected
915 : : // components are searched separately.
916 [ - + ]: 5929 : assert(iterations_done <= (uint64_t{1} << (todo.Count() - 1)));
917 : : // Additionally, test that no more than sqrt(2^N)+1 iterations are required. This is just
918 : : // an empirical bound that seems to hold, without proof. Still, add a test for it so we
919 : : // can learn about counterexamples if they exist.
920 [ + + + - ]: 5929 : if (iterations_done >= 1 && todo.Count() <= 63) {
921 [ + - ]: 4609 : Assume((iterations_done - 1) * (iterations_done - 1) <= uint64_t{1} << todo.Count());
922 : : }
923 : :
924 : : // Perform quality checks only if SearchCandidateFinder claims an optimal result.
925 [ + + ]: 5929 : if (optimal) {
926 : : // Optimal sets are always connected.
927 [ - + ]: 1690 : assert(depgraph.IsConnected(found.transactions));
928 : :
929 : : // Compare with SimpleCandidateFinder.
930 [ - + ]: 1690 : auto [simple, simple_iters] = smp_finder.FindCandidateSet(MAX_SIMPLE_ITERATIONS);
931 [ - + ]: 1690 : assert(found.feerate >= simple.feerate);
932 [ + + ]: 1690 : if (simple_iters < MAX_SIMPLE_ITERATIONS) {
933 [ + - ]: 1683 : assert(found.feerate == simple.feerate);
934 : : }
935 : :
936 : : // Compare with AncestorCandidateFinder;
937 : 1690 : auto anc = anc_finder.FindCandidateSet();
938 [ - + ]: 1690 : assert(found.feerate >= anc.feerate);
939 : :
940 : : // Compare with a non-empty topological set read from the fuzz input (comparing with an
941 : : // empty set is not interesting).
942 [ + - ]: 1690 : auto read_topo = ReadTopologicalSet(depgraph, todo, reader, /*non_empty=*/true);
943 [ - + ]: 1690 : assert(found.feerate >= depgraph.FeeRate(read_topo));
944 : : }
945 : :
946 : : // Find a non-empty topologically valid subset of transactions to remove from the graph.
947 : : // Using an empty set would mean the next iteration is identical to the current one, and
948 : : // could cause an infinite loop.
949 [ + - ]: 5929 : auto del_set = ReadTopologicalSet(depgraph, todo, reader, /*non_empty=*/true);
950 : 5929 : todo -= del_set;
951 : 5929 : src_finder.MarkDone(del_set);
952 : 5929 : smp_finder.MarkDone(del_set);
953 : 5929 : anc_finder.MarkDone(del_set);
954 : : }
955 : :
956 [ - + ]: 439 : assert(src_finder.AllDone());
957 [ - + ]: 439 : assert(smp_finder.AllDone());
958 [ - + ]: 439 : assert(anc_finder.AllDone());
959 [ - + ]: 439 : assert(anc_finder.NumRemaining() == 0);
960 : 439 : }
961 : :
962 [ + - ]: 621 : FUZZ_TARGET(clusterlin_linearization_chunking)
963 : : {
964 : : // Verify the behavior of LinearizationChunking.
965 : :
966 : : // Retrieve a depgraph from the fuzz input.
967 : 165 : SpanReader reader(buffer);
968 : 165 : DepGraph<TestBitSet> depgraph;
969 : 165 : try {
970 [ + - ]: 165 : reader >> Using<DepGraphFormatter>(depgraph);
971 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
972 : :
973 : : // Retrieve a topologically-valid subset of depgraph (allowed to be empty, because the argument
974 : : // to LinearizationChunking::Intersect is allowed to be empty).
975 : 165 : auto todo = depgraph.Positions();
976 [ + - ]: 165 : auto subset = SetInfo(depgraph, ReadTopologicalSet(depgraph, todo, reader, /*non_empty=*/false));
977 : :
978 : : // Retrieve a valid linearization for depgraph.
979 [ + - ]: 165 : auto linearization = ReadLinearization(depgraph, reader);
980 : :
981 : : // Construct a LinearizationChunking object, initially for the whole linearization.
982 [ - + ]: 165 : LinearizationChunking chunking(depgraph, linearization);
983 : :
984 : : // Incrementally remove transactions from the chunking object, and check various properties at
985 : : // every step.
986 [ + + ]: 2009 : while (todo.Any()) {
987 [ - + - + ]: 1679 : assert(chunking.NumChunksLeft() > 0);
988 : :
989 : : // Construct linearization with just todo.
990 : 1679 : std::vector<DepGraphIndex> linearization_left;
991 [ + + ]: 40777 : for (auto i : linearization) {
992 [ + + + - ]: 39098 : if (todo[i]) linearization_left.push_back(i);
993 : : }
994 : :
995 : : // Compute the chunking for linearization_left.
996 [ - + ]: 1679 : auto chunking_left = ChunkLinearization(depgraph, linearization_left);
997 : :
998 : : // Verify that it matches the feerates of the chunks of chunking.
999 [ - + - + : 1679 : assert(chunking.NumChunksLeft() == chunking_left.size());
- + ]
1000 [ - + + + ]: 10816 : for (DepGraphIndex i = 0; i < chunking.NumChunksLeft(); ++i) {
1001 [ + - ]: 18274 : assert(chunking.GetChunk(i).feerate == chunking_left[i]);
1002 : : }
1003 : :
1004 : : // Check consistency of chunking.
1005 : 1679 : TestBitSet combined;
1006 [ - + + + ]: 10816 : for (DepGraphIndex i = 0; i < chunking.NumChunksLeft(); ++i) {
1007 : 9137 : const auto& chunk_info = chunking.GetChunk(i);
1008 : : // Chunks must be non-empty.
1009 [ - + ]: 9137 : assert(chunk_info.transactions.Any());
1010 : : // Chunk feerates must be monotonically non-increasing.
1011 [ + + - + ]: 9137 : if (i > 0) assert(!(chunk_info.feerate >> chunking.GetChunk(i - 1).feerate));
1012 : : // Chunks must be a subset of what is left of the linearization.
1013 [ - + ]: 9137 : assert(chunk_info.transactions.IsSubsetOf(todo));
1014 : : // Chunks' claimed feerates must match their transactions' aggregate feerate.
1015 [ + - ]: 9137 : assert(depgraph.FeeRate(chunk_info.transactions) == chunk_info.feerate);
1016 : : // Chunks must be the highest-feerate remaining prefix.
1017 : 9137 : SetInfo<TestBitSet> accumulator, best;
1018 [ + + ]: 260048 : for (auto j : linearization) {
1019 [ + + + + ]: 250911 : if (todo[j] && !combined[j]) {
1020 : 86795 : accumulator.Set(depgraph, j);
1021 [ + + + + ]: 86795 : if (best.feerate.IsEmpty() || accumulator.feerate > best.feerate) {
1022 : 16521 : best = accumulator;
1023 : : }
1024 : : }
1025 : : }
1026 [ - + ]: 9137 : assert(best.transactions == chunk_info.transactions);
1027 [ + - ]: 9137 : assert(best.feerate == chunk_info.feerate);
1028 : : // Chunks cannot overlap.
1029 [ - + ]: 9137 : assert(!chunk_info.transactions.Overlaps(combined));
1030 [ + - ]: 9137 : combined |= chunk_info.transactions;
1031 : : // Chunks must be topological.
1032 [ + - + + ]: 38137 : for (auto idx : chunk_info.transactions) {
1033 [ - + ]: 19863 : assert((depgraph.Ancestors(idx) & todo).IsSubsetOf(combined));
1034 : : }
1035 : : }
1036 [ - + ]: 1679 : assert(combined == todo);
1037 : :
1038 : : // Verify the expected properties of LinearizationChunking::IntersectPrefixes:
1039 : 1679 : auto intersect = chunking.IntersectPrefixes(subset);
1040 : : // - Intersecting again doesn't change the result.
1041 [ + - ]: 1679 : assert(chunking.IntersectPrefixes(intersect) == intersect);
1042 : : // - The intersection is topological.
1043 : 1679 : TestBitSet intersect_anc;
1044 [ + + + + ]: 5587 : for (auto idx : intersect.transactions) {
1045 : 3089 : intersect_anc |= (depgraph.Ancestors(idx) & todo);
1046 : : }
1047 [ - + ]: 1679 : assert(intersect.transactions == intersect_anc);
1048 : : // - The claimed intersection feerate matches its transactions.
1049 [ + - ]: 1679 : assert(intersect.feerate == depgraph.FeeRate(intersect.transactions));
1050 : : // - The intersection may only be empty if its input is empty.
1051 [ - + ]: 1679 : assert(intersect.transactions.Any() == subset.transactions.Any());
1052 : : // - The intersection feerate must be as high as the input.
1053 [ - + ]: 1679 : assert(intersect.feerate >= subset.feerate);
1054 : : // - No non-empty intersection between the intersection and a prefix of the chunks of the
1055 : : // remainder of the linearization may be better than the intersection.
1056 : 1679 : TestBitSet prefix;
1057 [ - + + + ]: 10816 : for (DepGraphIndex i = 0; i < chunking.NumChunksLeft(); ++i) {
1058 : 9137 : prefix |= chunking.GetChunk(i).transactions;
1059 : 9137 : auto reintersect = SetInfo(depgraph, prefix & intersect.transactions);
1060 [ + + ]: 9137 : if (!reintersect.feerate.IsEmpty()) {
1061 [ - + ]: 4864 : assert(reintersect.feerate <= intersect.feerate);
1062 : : }
1063 : : }
1064 : :
1065 : : // Find a non-empty topologically valid subset of transactions to remove from the graph.
1066 : : // Using an empty set would mean the next iteration is identical to the current one, and
1067 : : // could cause an infinite loop.
1068 [ + - ]: 1679 : auto done = ReadTopologicalSet(depgraph, todo, reader, /*non_empty=*/true);
1069 : 1679 : todo -= done;
1070 : 1679 : chunking.MarkDone(done);
1071 : 1679 : subset = SetInfo(depgraph, subset.transactions - done);
1072 : 1679 : }
1073 : :
1074 [ - + - + ]: 165 : assert(chunking.NumChunksLeft() == 0);
1075 : 165 : }
1076 : :
1077 [ + - ]: 597 : FUZZ_TARGET(clusterlin_simple_linearize)
1078 : : {
1079 : : // Verify the behavior of SimpleLinearize(). Note that SimpleLinearize is only used in tests;
1080 : : // the purpose of this fuzz test is to establish confidence in SimpleLinearize, so that it can
1081 : : // be used to test the real Linearize function in the fuzz test below.
1082 : :
1083 : : // Retrieve an iteration count and a depgraph from the fuzz input.
1084 : 141 : SpanReader reader(buffer);
1085 : 141 : uint64_t iter_count{0};
1086 : 141 : DepGraph<TestBitSet> depgraph;
1087 : 141 : try {
1088 [ + + + - ]: 141 : reader >> VARINT(iter_count) >> Using<DepGraphFormatter>(depgraph);
1089 [ - + ]: 1 : } catch (const std::ios_base::failure&) {}
1090 : 141 : iter_count %= MAX_SIMPLE_ITERATIONS;
1091 : :
1092 : : // Invoke SimpleLinearize().
1093 [ - + ]: 141 : auto [linearization, optimal] = SimpleLinearize(depgraph, iter_count);
1094 [ - + ]: 141 : SanityCheck(depgraph, linearization);
1095 [ - + ]: 141 : auto simple_chunking = ChunkLinearization(depgraph, linearization);
1096 : :
1097 : : // If the iteration count is sufficiently high, an optimal linearization must be found.
1098 : : // SimpleLinearize on k transactions can take up to 2^(k-1) iterations (one per non-empty
1099 : : // connected topologically valid subset), which sums over k=1..n to (2^n)-1.
1100 [ + - ]: 141 : const uint64_t n = depgraph.TxCount();
1101 [ + - + + ]: 141 : if (n <= 63 && (iter_count >> n)) {
1102 [ - + ]: 34 : assert(optimal);
1103 : : }
1104 : :
1105 : : // If SimpleLinearize claims optimal result, and the cluster is sufficiently small (there are
1106 : : // n! linearizations), test that the result is as good as every valid linearization.
1107 [ + + + + ]: 141 : if (optimal && depgraph.TxCount() <= 8) {
1108 [ + - ]: 61 : auto exh_linearization = ExhaustiveLinearize(depgraph);
1109 [ - + ]: 61 : auto exh_chunking = ChunkLinearization(depgraph, exh_linearization);
1110 [ - + - + : 61 : auto cmp = CompareChunks(simple_chunking, exh_chunking);
+ - ]
1111 [ - + ]: 61 : assert(cmp == 0);
1112 [ - + - + : 61 : assert(simple_chunking.size() == exh_chunking.size());
- + ]
1113 : 61 : }
1114 : :
1115 [ + + ]: 141 : if (optimal) {
1116 : : // Compare with a linearization read from the fuzz input.
1117 [ + - ]: 94 : auto read = ReadLinearization(depgraph, reader);
1118 [ - + ]: 94 : auto read_chunking = ChunkLinearization(depgraph, read);
1119 [ - + - + : 94 : auto cmp = CompareChunks(simple_chunking, read_chunking);
+ - ]
1120 [ - + ]: 94 : assert(cmp >= 0);
1121 : 94 : }
1122 : 141 : }
1123 : :
1124 [ + - ]: 1025 : FUZZ_TARGET(clusterlin_linearize)
1125 : : {
1126 : : // Verify the behavior of Linearize().
1127 : :
1128 : : // Retrieve an RNG seed, an iteration count, a depgraph, and whether to make it connected from
1129 : : // the fuzz input.
1130 : 569 : SpanReader reader(buffer);
1131 : 569 : DepGraph<TestBitSet> depgraph;
1132 : 569 : uint64_t rng_seed{0};
1133 : 569 : uint64_t iter_count{0};
1134 : 569 : uint8_t make_connected{1};
1135 : 569 : try {
1136 [ + + + - : 569 : reader >> VARINT(iter_count) >> Using<DepGraphFormatter>(depgraph) >> rng_seed >> make_connected;
+ + + + ]
1137 [ - + ]: 444 : } catch (const std::ios_base::failure&) {}
1138 : : // The most complicated graphs are connected ones (other ones just split up). Optionally force
1139 : : // the graph to be connected.
1140 [ + + + - ]: 569 : if (make_connected) MakeConnected(depgraph);
1141 : :
1142 : : // Optionally construct an old linearization for it.
1143 : 569 : std::vector<DepGraphIndex> old_linearization;
1144 : 569 : {
1145 : 569 : uint8_t have_old_linearization{0};
1146 : 569 : try {
1147 [ + + ]: 569 : reader >> have_old_linearization;
1148 [ - + ]: 363 : } catch(const std::ios_base::failure&) {}
1149 [ + + ]: 569 : if (have_old_linearization & 1) {
1150 [ + - ]: 344 : old_linearization = ReadLinearization(depgraph, reader);
1151 [ - + ]: 172 : SanityCheck(depgraph, old_linearization);
1152 : : }
1153 : : }
1154 : :
1155 : : // Invoke Linearize().
1156 : 569 : iter_count &= 0x7ffff;
1157 [ - + - + ]: 569 : auto [linearization, optimal, cost] = Linearize(depgraph, iter_count, rng_seed, old_linearization);
1158 [ - + ]: 569 : assert(cost <= iter_count);
1159 [ - + ]: 569 : SanityCheck(depgraph, linearization);
1160 [ - + ]: 569 : auto chunking = ChunkLinearization(depgraph, linearization);
1161 : :
1162 : : // Linearization must always be as good as the old one, if provided.
1163 [ + + ]: 569 : if (!old_linearization.empty()) {
1164 [ - + ]: 171 : auto old_chunking = ChunkLinearization(depgraph, old_linearization);
1165 [ - + - + : 171 : auto cmp = CompareChunks(chunking, old_chunking);
+ - ]
1166 [ - + ]: 171 : assert(cmp >= 0);
1167 : 171 : }
1168 : :
1169 : : // If the iteration count is sufficiently high, an optimal linearization must be found.
1170 [ + + ]: 569 : if (iter_count >= MaxOptimalLinearizationIters(depgraph.TxCount())) {
1171 [ - + ]: 139 : assert(optimal);
1172 : : }
1173 : :
1174 : : // If Linearize claims optimal result, run quality tests.
1175 [ + + ]: 569 : if (optimal) {
1176 : : // It must be as good as SimpleLinearize.
1177 [ - + ]: 395 : auto [simple_linearization, simple_optimal] = SimpleLinearize(depgraph, MAX_SIMPLE_ITERATIONS);
1178 [ - + ]: 395 : SanityCheck(depgraph, simple_linearization);
1179 [ - + ]: 395 : auto simple_chunking = ChunkLinearization(depgraph, simple_linearization);
1180 [ - + - + : 395 : auto cmp = CompareChunks(chunking, simple_chunking);
+ - ]
1181 [ - + ]: 395 : assert(cmp >= 0);
1182 : : // If SimpleLinearize finds the optimal result too, they must be equal (if not,
1183 : : // SimpleLinearize is broken).
1184 [ + + - + ]: 395 : if (simple_optimal) assert(cmp == 0);
1185 : : // If simple_chunking is diagram-optimal, it cannot have more chunks than chunking (as
1186 : : // chunking is claimed to be optimal, which implies minimal chunks).
1187 [ + + - + : 395 : if (cmp == 0) assert(chunking.size() >= simple_chunking.size());
- + - + ]
1188 : :
1189 : : // Compare with a linearization read from the fuzz input.
1190 [ + - ]: 395 : auto read = ReadLinearization(depgraph, reader);
1191 [ - + ]: 395 : auto read_chunking = ChunkLinearization(depgraph, read);
1192 [ - + - + : 395 : auto cmp_read = CompareChunks(chunking, read_chunking);
+ - ]
1193 [ - + ]: 395 : assert(cmp_read >= 0);
1194 : 395 : }
1195 : 569 : }
1196 : :
1197 [ + - ]: 601 : FUZZ_TARGET(clusterlin_postlinearize)
1198 : : {
1199 : : // Verify expected properties of PostLinearize() on arbitrary linearizations.
1200 : :
1201 : : // Retrieve a depgraph from the fuzz input.
1202 : 145 : SpanReader reader(buffer);
1203 : 145 : DepGraph<TestBitSet> depgraph;
1204 : 145 : try {
1205 [ + - ]: 145 : reader >> Using<DepGraphFormatter>(depgraph);
1206 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
1207 : :
1208 : : // Retrieve a linearization from the fuzz input.
1209 : 145 : std::vector<DepGraphIndex> linearization;
1210 [ + - ]: 290 : linearization = ReadLinearization(depgraph, reader);
1211 [ - + ]: 145 : SanityCheck(depgraph, linearization);
1212 : :
1213 : : // Produce a post-processed version.
1214 [ + - ]: 145 : auto post_linearization = linearization;
1215 [ - + + - ]: 145 : PostLinearize(depgraph, post_linearization);
1216 [ - + ]: 145 : SanityCheck(depgraph, post_linearization);
1217 : :
1218 : : // Compare diagrams: post-linearization cannot worsen anywhere.
1219 [ - + ]: 145 : auto chunking = ChunkLinearization(depgraph, linearization);
1220 [ - + ]: 145 : auto post_chunking = ChunkLinearization(depgraph, post_linearization);
1221 [ - + - + : 145 : auto cmp = CompareChunks(post_chunking, chunking);
+ - ]
1222 [ - + ]: 145 : assert(cmp >= 0);
1223 : :
1224 : : // Run again, things can keep improving (and never get worse)
1225 [ + - ]: 145 : auto post_post_linearization = post_linearization;
1226 [ - + + - ]: 145 : PostLinearize(depgraph, post_post_linearization);
1227 [ - + ]: 145 : SanityCheck(depgraph, post_post_linearization);
1228 [ - + ]: 145 : auto post_post_chunking = ChunkLinearization(depgraph, post_post_linearization);
1229 [ - + - + : 145 : cmp = CompareChunks(post_post_chunking, post_chunking);
+ - ]
1230 [ - + ]: 145 : assert(cmp >= 0);
1231 : :
1232 : : // The chunks that come out of postlinearizing are always connected.
1233 [ - + ]: 145 : LinearizationChunking linchunking(depgraph, post_linearization);
1234 [ - + + + ]: 1498 : while (linchunking.NumChunksLeft()) {
1235 [ - + ]: 1208 : assert(depgraph.IsConnected(linchunking.GetChunk(0).transactions));
1236 : 1208 : linchunking.MarkDone(linchunking.GetChunk(0).transactions);
1237 : : }
1238 : 145 : }
1239 : :
1240 [ + - ]: 992 : FUZZ_TARGET(clusterlin_postlinearize_tree)
1241 : : {
1242 : : // Verify expected properties of PostLinearize() on linearizations of graphs that form either
1243 : : // an upright or reverse tree structure.
1244 : :
1245 : : // Construct a direction, RNG seed, and an arbitrary graph from the fuzz input.
1246 : 536 : SpanReader reader(buffer);
1247 : 536 : uint64_t rng_seed{0};
1248 : 536 : DepGraph<TestBitSet> depgraph_gen;
1249 : 536 : uint8_t direction{0};
1250 : 536 : try {
1251 [ + - + + : 536 : reader >> direction >> rng_seed >> Using<DepGraphFormatter>(depgraph_gen);
+ - ]
1252 [ - + ]: 1 : } catch (const std::ios_base::failure&) {}
1253 : :
1254 : : // Now construct a new graph, copying the nodes, but leaving only the first parent (even
1255 : : // direction) or the first child (odd direction).
1256 : 536 : DepGraph<TestBitSet> depgraph_tree;
1257 [ - + + + ]: 15995 : for (DepGraphIndex i = 0; i < depgraph_gen.PositionRange(); ++i) {
1258 [ + + ]: 15459 : if (depgraph_gen.Positions()[i]) {
1259 : 12587 : depgraph_tree.AddTransaction(depgraph_gen.FeeRate(i));
1260 : : } else {
1261 : : // For holes, add a dummy transaction which is deleted below, so that non-hole
1262 : : // transactions retain their position.
1263 : 2872 : depgraph_tree.AddTransaction(FeeFrac{});
1264 : : }
1265 : : }
1266 : 536 : depgraph_tree.RemoveTransactions(TestBitSet::Fill(depgraph_gen.PositionRange()) - depgraph_gen.Positions());
1267 : :
1268 [ + + ]: 536 : if (direction & 1) {
1269 [ + + ]: 7967 : for (DepGraphIndex i = 0; i < depgraph_gen.TxCount(); ++i) {
1270 : 7642 : auto children = depgraph_gen.GetReducedChildren(i);
1271 [ + + ]: 7642 : if (children.Any()) {
1272 : 4676 : depgraph_tree.AddDependencies(TestBitSet::Singleton(i), children.First());
1273 : : }
1274 : : }
1275 : : } else {
1276 [ + + ]: 5156 : for (DepGraphIndex i = 0; i < depgraph_gen.TxCount(); ++i) {
1277 : 4945 : auto parents = depgraph_gen.GetReducedParents(i);
1278 [ + + ]: 4945 : if (parents.Any()) {
1279 : 2086 : depgraph_tree.AddDependencies(TestBitSet::Singleton(parents.First()), i);
1280 : : }
1281 : : }
1282 : : }
1283 : :
1284 : : // Retrieve a linearization from the fuzz input.
1285 : 536 : std::vector<DepGraphIndex> linearization;
1286 [ + - ]: 1072 : linearization = ReadLinearization(depgraph_tree, reader);
1287 [ - + ]: 536 : SanityCheck(depgraph_tree, linearization);
1288 : :
1289 : : // Produce a postlinearized version.
1290 [ + - ]: 536 : auto post_linearization = linearization;
1291 [ - + + - ]: 536 : PostLinearize(depgraph_tree, post_linearization);
1292 [ - + ]: 536 : SanityCheck(depgraph_tree, post_linearization);
1293 : :
1294 : : // Compare diagrams.
1295 [ - + ]: 536 : auto chunking = ChunkLinearization(depgraph_tree, linearization);
1296 [ - + ]: 536 : auto post_chunking = ChunkLinearization(depgraph_tree, post_linearization);
1297 [ - + - + : 536 : auto cmp = CompareChunks(post_chunking, chunking);
+ - ]
1298 [ - + ]: 536 : assert(cmp >= 0);
1299 : :
1300 : : // Verify that post-linearizing again does not change the diagram. The result must be identical
1301 : : // as post_linearization ought to be optimal already with a tree-structured graph.
1302 [ + - ]: 536 : auto post_post_linearization = post_linearization;
1303 [ - + + - ]: 536 : PostLinearize(depgraph_tree, post_linearization);
1304 [ - + ]: 536 : SanityCheck(depgraph_tree, post_linearization);
1305 [ - + ]: 536 : auto post_post_chunking = ChunkLinearization(depgraph_tree, post_post_linearization);
1306 [ - + - + : 536 : auto cmp_post = CompareChunks(post_post_chunking, post_chunking);
+ - ]
1307 [ - + ]: 536 : assert(cmp_post == 0);
1308 : :
1309 : : // Try to find an even better linearization directly. This must not change the diagram for the
1310 : : // same reason.
1311 [ - + - + ]: 536 : auto [opt_linearization, _optimal, _cost] = Linearize(depgraph_tree, 100000, rng_seed, post_linearization);
1312 [ - + ]: 536 : auto opt_chunking = ChunkLinearization(depgraph_tree, opt_linearization);
1313 [ - + - + : 536 : auto cmp_opt = CompareChunks(opt_chunking, post_chunking);
+ - ]
1314 [ - + ]: 536 : assert(cmp_opt == 0);
1315 : 536 : }
1316 : :
1317 [ + - ]: 615 : FUZZ_TARGET(clusterlin_postlinearize_moved_leaf)
1318 : : {
1319 : : // Verify that taking an existing linearization, and moving a leaf to the back, potentially
1320 : : // increasing its fee, and then post-linearizing, results in something as good as the
1321 : : // original. This guarantees that in an RBF that replaces a transaction with one of the same
1322 : : // size but higher fee, applying the "remove conflicts, append new transaction, postlinearize"
1323 : : // process will never worsen linearization quality.
1324 : :
1325 : : // Construct an arbitrary graph and a fee from the fuzz input.
1326 : 159 : SpanReader reader(buffer);
1327 : 159 : DepGraph<TestBitSet> depgraph;
1328 : 159 : int32_t fee_inc{0};
1329 : 159 : try {
1330 : 159 : uint64_t fee_inc_code;
1331 [ + - + + ]: 159 : reader >> Using<DepGraphFormatter>(depgraph) >> VARINT(fee_inc_code);
1332 : 63 : fee_inc = fee_inc_code & 0x3ffff;
1333 [ - + ]: 96 : } catch (const std::ios_base::failure&) {}
1334 [ + + ]: 159 : if (depgraph.TxCount() == 0) return;
1335 : :
1336 : : // Retrieve two linearizations from the fuzz input.
1337 [ + - ]: 150 : auto lin = ReadLinearization(depgraph, reader);
1338 [ + - ]: 150 : auto lin_leaf = ReadLinearization(depgraph, reader);
1339 : :
1340 : : // Construct a linearization identical to lin, but with the tail end of lin_leaf moved to the
1341 : : // back.
1342 : 150 : std::vector<DepGraphIndex> lin_moved;
1343 [ + + ]: 2161 : for (auto i : lin) {
1344 [ + + + - ]: 2011 : if (i != lin_leaf.back()) lin_moved.push_back(i);
1345 : : }
1346 [ + - ]: 150 : lin_moved.push_back(lin_leaf.back());
1347 : :
1348 : : // Postlinearize lin_moved.
1349 [ - + + - ]: 150 : PostLinearize(depgraph, lin_moved);
1350 [ - + ]: 150 : SanityCheck(depgraph, lin_moved);
1351 : :
1352 : : // Compare diagrams (applying the fee delta after computing the old one).
1353 [ - + ]: 150 : auto old_chunking = ChunkLinearization(depgraph, lin);
1354 [ - + ]: 150 : depgraph.FeeRate(lin_leaf.back()).fee += fee_inc;
1355 [ - + ]: 150 : auto new_chunking = ChunkLinearization(depgraph, lin_moved);
1356 [ - + - + : 150 : auto cmp = CompareChunks(new_chunking, old_chunking);
+ - ]
1357 [ - + ]: 150 : assert(cmp >= 0);
1358 : 159 : }
1359 : :
1360 [ + - ]: 713 : FUZZ_TARGET(clusterlin_merge)
1361 : : {
1362 : : // Construct an arbitrary graph from the fuzz input.
1363 : 257 : SpanReader reader(buffer);
1364 : 257 : DepGraph<TestBitSet> depgraph;
1365 : 257 : try {
1366 [ + - ]: 257 : reader >> Using<DepGraphFormatter>(depgraph);
1367 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
1368 : :
1369 : : // Retrieve two linearizations from the fuzz input.
1370 [ + - ]: 257 : auto lin1 = ReadLinearization(depgraph, reader);
1371 [ + - ]: 257 : auto lin2 = ReadLinearization(depgraph, reader);
1372 : :
1373 : : // Merge the two.
1374 [ - + - + : 257 : auto lin_merged = MergeLinearizations(depgraph, lin1, lin2);
+ - ]
1375 : :
1376 : : // Compute chunkings and compare.
1377 [ - + ]: 257 : auto chunking1 = ChunkLinearization(depgraph, lin1);
1378 [ - + ]: 257 : auto chunking2 = ChunkLinearization(depgraph, lin2);
1379 [ - + ]: 257 : auto chunking_merged = ChunkLinearization(depgraph, lin_merged);
1380 [ - + - + : 257 : auto cmp1 = CompareChunks(chunking_merged, chunking1);
+ - ]
1381 [ - + ]: 257 : assert(cmp1 >= 0);
1382 [ - + - + : 257 : auto cmp2 = CompareChunks(chunking_merged, chunking2);
+ - ]
1383 [ - + ]: 257 : assert(cmp2 >= 0);
1384 : 257 : }
1385 : :
1386 [ + - ]: 691 : FUZZ_TARGET(clusterlin_fix_linearization)
1387 : : {
1388 : : // Verify expected properties of FixLinearization() on arbitrary linearizations.
1389 : :
1390 : : // Retrieve a depgraph from the fuzz input.
1391 : 235 : SpanReader reader(buffer);
1392 : 235 : DepGraph<TestBitSet> depgraph;
1393 : 235 : try {
1394 [ + - ]: 235 : reader >> Using<DepGraphFormatter>(depgraph);
1395 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
1396 : :
1397 : : // Construct an arbitrary linearization (not necessarily topological for depgraph).
1398 : 235 : std::vector<DepGraphIndex> linearization;
1399 : : /** Which transactions of depgraph are yet to be included in linearization. */
1400 : 235 : TestBitSet todo = depgraph.Positions();
1401 [ + + ]: 2691 : while (todo.Any()) {
1402 : : // Read a number from the fuzz input in range [0, todo.Count()).
1403 : 2221 : uint64_t val{0};
1404 : 2221 : try {
1405 [ + + ]: 2221 : reader >> VARINT(val);
1406 [ - + ]: 1879 : } catch (const std::ios_base::failure&) {}
1407 [ + - ]: 2221 : val %= todo.Count();
1408 : : // Find the val'th element in todo, remove it from todo, and append it to linearization.
1409 [ + - + - ]: 5447 : for (auto idx : todo) {
1410 [ + + ]: 3226 : if (val == 0) {
1411 [ + - ]: 2221 : linearization.push_back(idx);
1412 : 2221 : todo.Reset(idx);
1413 : 2221 : break;
1414 : : }
1415 : 1005 : --val;
1416 : : }
1417 : : }
1418 [ - + - + ]: 235 : assert(linearization.size() == depgraph.TxCount());
1419 : :
1420 : : // Determine what prefix of linearization is topological, i.e., the position of the first entry
1421 : : // in linearization which corresponds to a transaction that is not preceded by all its
1422 : : // ancestors.
1423 : 235 : size_t topo_prefix = 0;
1424 : 235 : todo = depgraph.Positions();
1425 [ - + + + ]: 1376 : while (topo_prefix < linearization.size()) {
1426 : 1228 : DepGraphIndex idx = linearization[topo_prefix];
1427 : 1228 : todo.Reset(idx);
1428 [ + + ]: 1228 : if (todo.Overlaps(depgraph.Ancestors(idx))) break;
1429 : 1141 : ++topo_prefix;
1430 : : }
1431 : :
1432 : : // Then make a fixed copy of linearization.
1433 [ + - ]: 235 : auto linearization_fixed = linearization;
1434 [ - + ]: 235 : FixLinearization(depgraph, linearization_fixed);
1435 : : // Sanity check it (which includes testing whether it is topological).
1436 [ - + ]: 235 : SanityCheck(depgraph, linearization_fixed);
1437 : :
1438 : : // FixLinearization does not modify the topological prefix of linearization.
1439 [ - + ]: 235 : assert(std::equal(linearization.begin(), linearization.begin() + topo_prefix,
1440 : : linearization_fixed.begin()));
1441 : : // This also means that if linearization was entirely topological, FixLinearization cannot have
1442 : : // modified it. This is implied by the assertion above already, but repeat it explicitly.
1443 [ - + + + ]: 235 : if (topo_prefix == linearization.size()) {
1444 [ - + ]: 148 : assert(linearization == linearization_fixed);
1445 : : }
1446 : 235 : }
|
