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 : 1064 : SimpleCandidateFinder(const DepGraph<SetType>& depgraph LIFETIMEBOUND) noexcept :
97 : 1064 : m_depgraph(depgraph), m_todo{depgraph.Positions()} {}
98 : :
99 : : /** Remove a set of transactions from the set of to-be-linearized ones. */
100 : 10784 : void MarkDone(SetType select) noexcept { m_todo -= select; }
101 : :
102 : : /** Determine whether unlinearized transactions remain. */
103 : 7809 : 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 : 6465 : std::pair<SetInfo<SetType>, uint64_t> FindCandidateSet(uint64_t max_iterations) const noexcept
114 : : {
115 : 6465 : 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 : 6465 : std::vector<std::pair<SetType, SetType>> queue;
120 : : // Initially we have just one queue element, with the entire graph in und.
121 : 6465 : queue.emplace_back(SetType{}, m_todo);
122 : : // Best solution so far. Initialize with the remaining ancestors of the first remaining
123 : : // transaction.
124 : 6465 : SetInfo best(m_depgraph, m_depgraph.Ancestors(m_todo.First()) & m_todo);
125 : : // Process the queue.
126 [ + + + + ]: 51849965 : while (!queue.empty() && iterations_left) {
127 : : // Pop top element of the queue.
128 : 51843500 : auto [inc, und] = queue.back();
129 : 51843500 : queue.pop_back();
130 : : // Look for a transaction to consider adding/removing.
131 : 51843500 : bool inc_none = inc.None();
132 [ + + ]: 88089276 : 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 [ + + + + ]: 62164969 : if (inc_none || inc.Overlaps(m_depgraph.Ancestors(split))) {
137 : 25919193 : --iterations_left;
138 : : // Add a queue entry with split included.
139 : 25919193 : SetInfo new_inc(m_depgraph, inc | (m_todo & m_depgraph.Ancestors(split)));
140 : 25919193 : queue.emplace_back(new_inc.transactions, und - new_inc.transactions);
141 : : // Add a queue entry with split excluded.
142 : 25919193 : queue.emplace_back(inc, und - m_depgraph.Descendants(split));
143 : : // Update statistics to account for the candidate new_inc.
144 [ + + ]: 25919193 : if (new_inc.feerate > best.feerate) best = new_inc;
145 : : break;
146 : : }
147 : : }
148 : : }
149 : 6465 : return {std::move(best), max_iterations - iterations_left};
150 : 6465 : }
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 : 131 : ExhaustiveCandidateFinder(const DepGraph<SetType>& depgraph LIFETIMEBOUND) noexcept :
169 : 131 : m_depgraph(depgraph), m_todo{depgraph.Positions()} {}
170 : :
171 : : /** Remove a set of transactions from the set of to-be-linearized ones. */
172 : 1210 : void MarkDone(SetType select) noexcept { m_todo -= select; }
173 : :
174 : : /** Determine whether unlinearized transactions remain. */
175 : 1341 : 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 : 761 : SetInfo<SetType> FindCandidateSet() const noexcept
182 : : {
183 : : // Best solution so far.
184 : 761 : SetInfo<SetType> best{m_todo, m_depgraph.FeeRate(m_todo)};
185 : : // The number of combinations to try.
186 : 761 : uint64_t limit = (uint64_t{1} << m_todo.Count()) - 1;
187 : : // Try the transitive closure of every non-empty subset of m_todo.
188 [ + + ]: 351073 : 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 : 350312 : SetType txn;
192 : 350312 : auto x_shifted{x};
193 [ + - + + ]: 4511682 : for (auto i : m_todo) {
194 [ + + ]: 3811058 : if (x_shifted & 1) txn |= m_depgraph.Ancestors(i);
195 : 3811058 : x_shifted >>= 1;
196 : : }
197 : 350312 : SetInfo cur(m_depgraph, txn & m_todo);
198 [ + + ]: 350312 : if (cur.feerate > best.feerate) best = cur;
199 : : }
200 : 761 : 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 : 575 : std::pair<std::vector<DepGraphIndex>, bool> SimpleLinearize(const DepGraph<SetType>& depgraph, uint64_t max_iterations)
212 : : {
213 : 575 : std::vector<DepGraphIndex> linearization;
214 : 575 : SimpleCandidateFinder finder(depgraph);
215 : 575 : SetType todo = depgraph.Positions();
216 : 575 : bool optimal = true;
217 [ + + ]: 4039 : while (todo.Any()) {
218 [ + + ]: 3464 : auto [candidate, iterations_done] = finder.FindCandidateSet(max_iterations);
219 [ + + ]: 3464 : if (iterations_done == max_iterations) optimal = false;
220 : 3464 : depgraph.AppendTopo(linearization, candidate.transactions);
221 : 3464 : todo -= candidate.transactions;
222 : 3464 : finder.MarkDone(candidate.transactions);
223 : 3464 : max_iterations -= iterations_done;
224 : : }
225 : 575 : return {std::move(linearization), optimal};
226 : 575 : }
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 : 108 : std::vector<DepGraphIndex> ExhaustiveLinearize(const DepGraph<SetType>& depgraph)
237 : : {
238 : : // The best linearization so far, and its chunking.
239 : 108 : std::vector<DepGraphIndex> linearization;
240 : 108 : std::vector<FeeFrac> chunking;
241 : :
242 [ + + ]: 108 : std::vector<DepGraphIndex> perm_linearization;
243 : : // Initialize with the lexicographically-first linearization.
244 [ + + + - : 737 : 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 : 500425 : DepGraphIndex topo_length{0};
249 : 500425 : TestBitSet perm_done;
250 [ - + + + ]: 4311001 : while (topo_length < perm_linearization.size()) {
251 : 3863971 : auto i = perm_linearization[topo_length];
252 [ + + ]: 3863971 : perm_done.Set(i);
253 [ + + ]: 3863971 : if (!depgraph.Ancestors(i).IsSubsetOf(perm_done)) break;
254 : 3810576 : ++topo_length;
255 : : }
256 [ - + + + ]: 500425 : 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 [ - + ]: 447030 : auto perm_chunking = ChunkLinearization(depgraph, perm_linearization);
260 [ - + + - ]: 447030 : 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 [ + + + + : 500366 : if (linearization.empty() || cmp > 0 || (cmp == 0 && perm_chunking.size() > chunking.size())) {
+ + - + +
+ ]
264 [ + - ]: 1243 : linearization = perm_linearization;
265 [ + - ]: 1243 : chunking = perm_chunking;
266 : : }
267 : 447030 : } else {
268 : : // Otherwise, fast forward to the last permutation with the same non-topological
269 : : // prefix.
270 : 53395 : auto first_non_topo = perm_linearization.begin() + topo_length;
271 [ - + ]: 53395 : assert(std::is_sorted(first_non_topo + 1, perm_linearization.end()));
272 : 53395 : std::reverse(first_non_topo + 1, perm_linearization.end());
273 : : }
274 [ + + ]: 500425 : } while(std::next_permutation(perm_linearization.begin(), perm_linearization.end()));
275 : :
276 : 108 : return linearization;
277 : 108 : }
278 : :
279 : :
280 : : /** Stitch connected components together in a DepGraph, guaranteeing its corresponding cluster is connected. */
281 : : template<typename BS>
282 : 916 : void MakeConnected(DepGraph<BS>& depgraph)
283 : : {
284 : 916 : auto todo = depgraph.Positions();
285 : 916 : auto comp = depgraph.FindConnectedComponent(todo);
286 : 916 : Assume(depgraph.IsConnected(comp));
287 : 916 : todo -= comp;
288 [ + + ]: 11870 : while (todo.Any()) {
289 : 10954 : auto nextcomp = depgraph.FindConnectedComponent(todo);
290 : 10954 : Assume(depgraph.IsConnected(nextcomp));
291 : 10954 : depgraph.AddDependencies(BS::Singleton(comp.Last()), nextcomp.First());
292 : 10954 : todo -= nextcomp;
293 : 10954 : comp = nextcomp;
294 : : }
295 : 916 : }
296 : :
297 : : /** Given a dependency graph, and a todo set, read a topological subset of todo from reader. */
298 : : template<typename SetType>
299 : 18785 : 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 [ + + ]: 18785 : uint64_t mask{0};
304 : : try {
305 [ + + ]: 18785 : reader >> VARINT(mask);
306 [ - + ]: 15054 : } catch(const std::ios_base::failure&) {}
307 [ + + ]: 18785 : if (mask != uint64_t(-1)) mask += non_empty;
308 : :
309 : 18785 : SetType ret;
310 [ + + + + ]: 281407 : for (auto i : todo) {
311 [ + + ]: 243843 : if (!ret[i]) {
312 [ + + ]: 238634 : if (mask & 1) ret |= depgraph.Ancestors(i);
313 : 238634 : mask >>= 1;
314 : : }
315 : : }
316 : 18785 : 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 [ + + + + ]: 18785 : if (non_empty && ret.None()) {
322 : 331 : Assume(todo.Any());
323 : 331 : ret = depgraph.Ancestors(todo.First()) & todo;
324 : 331 : Assume(ret.Any());
325 : : }
326 : 18785 : return ret;
327 : : }
328 : :
329 : : /** Given a dependency graph, construct any valid linearization for it, reading from a SpanReader. */
330 : : template<typename BS>
331 : 1920 : std::vector<DepGraphIndex> ReadLinearization(const DepGraph<BS>& depgraph, SpanReader& reader)
332 : : {
333 : 1920 : std::vector<DepGraphIndex> linearization;
334 : 1920 : TestBitSet todo = depgraph.Positions();
335 : : // In every iteration one topologically-valid transaction is appended to linearization.
336 [ + + ]: 38412 : while (todo.Any()) {
337 : : // Compute the set of transactions with no not-yet-included ancestors.
338 : 34572 : TestBitSet potential_next;
339 [ + + ]: 496494 : for (auto j : todo) {
340 [ + + ]: 709888 : if ((depgraph.Ancestors(j) & todo) == TestBitSet::Singleton(j)) {
341 : 247966 : potential_next.Set(j);
342 : : }
343 : : }
344 : : // There must always be one (otherwise there is a cycle in the graph).
345 [ - + ]: 34572 : assert(potential_next.Any());
346 : : // Read a number from reader, and interpret it as index into potential_next.
347 [ + + ]: 34572 : uint64_t idx{0};
348 : : try {
349 [ + + + - ]: 69144 : reader >> VARINT(idx);
350 [ - + ]: 29595 : } catch (const std::ios_base::failure&) {}
351 : 34572 : idx %= potential_next.Count();
352 : : // Find out which transaction that corresponds to.
353 [ + - + - ]: 84609 : for (auto j : potential_next) {
354 [ + + ]: 50037 : if (idx == 0) {
355 : : // When found, add it to linearization and remove it from todo.
356 [ + - ]: 34572 : linearization.push_back(j);
357 [ - + ]: 34572 : assert(todo[j]);
358 : 34572 : todo.Reset(j);
359 : 34572 : break;
360 : : }
361 : 15465 : --idx;
362 : : }
363 : : }
364 : 1920 : return linearization;
365 : 0 : }
366 : :
367 : : } // namespace
368 : :
369 [ + - ]: 709 : FUZZ_TARGET(clusterlin_depgraph_sim)
370 : : {
371 : : // Simulation test to verify the full behavior of DepGraph.
372 : :
373 : 251 : FuzzedDataProvider provider(buffer.data(), buffer.size());
374 : :
375 : : /** Real DepGraph being tested. */
376 : 251 : 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 : 251 : std::array<std::optional<std::pair<FeeFrac, TestBitSet>>, TestBitSet::Size()> sim;
380 : : /** The number of non-nullopt position in sim. */
381 : 251 : DepGraphIndex num_tx_sim{0};
382 : :
383 : : /** Read a valid index of a transaction from the provider. */
384 : 14648 : auto idx_fn = [&]() {
385 : 14397 : auto offset = provider.ConsumeIntegralInRange<DepGraphIndex>(0, num_tx_sim - 1);
386 [ + - ]: 75610 : for (DepGraphIndex i = 0; i < sim.size(); ++i) {
387 [ + + ]: 75610 : if (!sim[i].has_value()) continue;
388 [ + + ]: 67311 : if (offset == 0) return i;
389 : 52914 : --offset;
390 : : }
391 : 0 : assert(false);
392 : : return DepGraphIndex(-1);
393 : 251 : };
394 : :
395 : : /** Read a valid subset of the transactions from the provider. */
396 : 14648 : auto subset_fn = [&]() {
397 : 14397 : auto range = (uint64_t{1} << num_tx_sim) - 1;
398 : 14397 : const auto mask = provider.ConsumeIntegralInRange<uint64_t>(0, range);
399 : 14397 : auto mask_shifted = mask;
400 : 14397 : TestBitSet subset;
401 [ + + ]: 475101 : for (DepGraphIndex i = 0; i < sim.size(); ++i) {
402 [ + + ]: 460704 : if (!sim[i].has_value()) continue;
403 [ + + ]: 279172 : if (mask_shifted & 1) {
404 : 66178 : subset.Set(i);
405 : : }
406 : 279172 : mask_shifted >>= 1;
407 : : }
408 [ - + ]: 14397 : assert(mask_shifted == 0);
409 : 14397 : return subset;
410 : 251 : };
411 : :
412 : : /** Read any set of transactions from the provider (including unused positions). */
413 : 5228 : auto set_fn = [&]() {
414 : 4977 : auto range = (uint64_t{1} << sim.size()) - 1;
415 : 4977 : const auto mask = provider.ConsumeIntegralInRange<uint64_t>(0, range);
416 : 4977 : TestBitSet set;
417 [ + + ]: 164241 : for (DepGraphIndex i = 0; i < sim.size(); ++i) {
418 [ + + ]: 159264 : if ((mask >> i) & 1) {
419 : 60677 : set.Set(i);
420 : : }
421 : : }
422 : 4977 : return set;
423 : 251 : };
424 : :
425 : : /** Propagate ancestor information in sim. */
426 : 5479 : auto anc_update_fn = [&]() {
427 : 5981 : while (true) {
428 : 5981 : bool updates{false};
429 [ + + ]: 197373 : for (DepGraphIndex chl = 0; chl < sim.size(); ++chl) {
430 [ + + ]: 191392 : if (!sim[chl].has_value()) continue;
431 [ + - + + ]: 365227 : for (auto par : sim[chl]->second) {
432 [ + + ]: 213253 : if (!sim[chl]->second.IsSupersetOf(sim[par]->second)) {
433 : 2557 : sim[chl]->second |= sim[par]->second;
434 : 2557 : updates = true;
435 : : }
436 : : }
437 : : }
438 [ + + ]: 5981 : if (!updates) break;
439 : : }
440 : 5479 : };
441 : :
442 : : /** Compare the state of transaction i in the simulation with the real one. */
443 : 68960 : auto check_fn = [&](DepGraphIndex i) {
444 : : // Compare used positions.
445 [ - + ]: 68709 : assert(real.Positions()[i] == sim[i].has_value());
446 [ + + ]: 68709 : if (sim[i].has_value()) {
447 : : // Compare feerate.
448 [ + - ]: 12160 : 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 [ - + ]: 12160 : assert(real.Ancestors(i) == sim[i]->second);
452 : : }
453 : 68960 : };
454 : :
455 : 251 : auto last_compaction_pos{real.PositionRange()};
456 : :
457 [ + + + + ]: 55476 : LIMITED_WHILE(provider.remaining_bytes() > 0, 1000) {
458 : 55225 : int command = provider.ConsumeIntegral<uint8_t>() % 4;
459 : 58629 : while (true) {
460 : : // Iterate decreasing command until an applicable branch is found.
461 [ + + + + ]: 58629 : if (num_tx_sim < TestBitSet::Size() && command-- == 0) {
462 : : // AddTransaction.
463 : 12160 : auto fee = provider.ConsumeIntegralInRange<int64_t>(-0x8000000000000, 0x7ffffffffffff);
464 : 12160 : auto size = provider.ConsumeIntegralInRange<int32_t>(1, 0x3fffff);
465 : 12160 : FeeFrac feerate{fee, size};
466 : : // Apply to DepGraph.
467 : 12160 : auto idx = real.AddTransaction(feerate);
468 : : // Verify that the returned index is correct.
469 [ - + ]: 12160 : assert(!sim[idx].has_value());
470 [ + - ]: 145992 : for (DepGraphIndex i = 0; i < TestBitSet::Size(); ++i) {
471 [ + + ]: 145992 : if (!sim[i].has_value()) {
472 [ - + ]: 12160 : assert(idx == i);
473 : : break;
474 : : }
475 : : }
476 : : // Update sim.
477 [ - + ]: 12160 : sim[idx] = {feerate, TestBitSet::Singleton(idx)};
478 : 12160 : ++num_tx_sim;
479 : 12160 : break;
480 [ + + + + ]: 46469 : } else if (num_tx_sim > 0 && command-- == 0) {
481 : : // AddDependencies.
482 : 14397 : DepGraphIndex child = idx_fn();
483 : 14397 : auto parents = subset_fn();
484 : : // Apply to DepGraph.
485 : 14397 : real.AddDependencies(parents, child);
486 : : // Apply to sim.
487 : 14397 : sim[child]->second |= parents;
488 : 14397 : break;
489 [ + + + + ]: 32072 : } else if (num_tx_sim > 0 && command-- == 0) {
490 : : // Remove transactions.
491 : 4977 : auto del = set_fn();
492 : : // Propagate all ancestry information before deleting anything in the simulation (as
493 : : // intermediary transactions may be deleted which impact connectivity).
494 : 4977 : anc_update_fn();
495 : : // Compare the state of the transactions being deleted.
496 [ + + + + ]: 70010 : for (auto i : del) check_fn(i);
497 : : // Apply to DepGraph.
498 : 4977 : real.RemoveTransactions(del);
499 : : // Apply to sim.
500 [ + + ]: 164241 : for (DepGraphIndex i = 0; i < sim.size(); ++i) {
501 [ + + ]: 159264 : if (sim[i].has_value()) {
502 [ + + ]: 54961 : if (del[i]) {
503 : 9536 : --num_tx_sim;
504 [ + - ]: 168800 : sim[i] = std::nullopt;
505 : : } else {
506 : 45425 : sim[i]->second -= del;
507 : : }
508 : : }
509 : : }
510 : : break;
511 [ + + ]: 27095 : } else if (command-- == 0) {
512 : : // Compact.
513 [ - + ]: 23691 : const size_t mem_before{real.DynamicMemoryUsage()};
514 : 23691 : real.Compact();
515 [ - + ]: 23691 : const size_t mem_after{real.DynamicMemoryUsage()};
516 [ - + + + : 23691 : assert(real.PositionRange() < last_compaction_pos ? mem_after < mem_before : mem_after <= mem_before);
- + ]
517 : : last_compaction_pos = real.PositionRange();
518 : : break;
519 : : }
520 : : }
521 : : }
522 : :
523 : : // Compare the real obtained depgraph against the simulation.
524 : 251 : anc_update_fn();
525 [ + + ]: 8283 : for (DepGraphIndex i = 0; i < sim.size(); ++i) check_fn(i);
526 [ - + ]: 251 : assert(real.TxCount() == num_tx_sim);
527 : : // Sanity check the result (which includes round-tripping serialization, if applicable).
528 [ + - ]: 251 : SanityCheck(real);
529 : 251 : }
530 : :
531 [ + - ]: 651 : FUZZ_TARGET(clusterlin_depgraph_serialization)
532 : : {
533 : : // Verify that any deserialized depgraph is acyclic and roundtrips to an identical depgraph.
534 : :
535 : : // Construct a graph by deserializing.
536 : 193 : SpanReader reader(buffer);
537 : 193 : DepGraph<TestBitSet> depgraph;
538 : 193 : DepGraphIndex par_code{0}, chl_code{0};
539 : 193 : try {
540 [ + - + + : 193 : reader >> Using<DepGraphFormatter>(depgraph) >> VARINT(par_code) >> VARINT(chl_code);
+ + ]
541 [ - + ]: 165 : } catch (const std::ios_base::failure&) {}
542 [ + - ]: 193 : SanityCheck(depgraph);
543 : :
544 : : // Verify the graph is a DAG.
545 [ - + ]: 193 : assert(depgraph.IsAcyclic());
546 : :
547 : : // Introduce a cycle, and then test that IsAcyclic returns false.
548 [ + + ]: 193 : if (depgraph.TxCount() < 2) return;
549 : 178 : DepGraphIndex par(0), chl(0);
550 : : // Pick any transaction of depgraph as parent.
551 [ + - ]: 178 : par_code %= depgraph.TxCount();
552 [ + - + - ]: 612 : for (auto i : depgraph.Positions()) {
553 [ + + ]: 434 : if (par_code == 0) {
554 : : par = i;
555 : : break;
556 : : }
557 : 256 : --par_code;
558 : : }
559 : : // Pick any ancestor of par (excluding itself) as child, if any.
560 [ + + ]: 178 : auto ancestors = depgraph.Ancestors(par) - TestBitSet::Singleton(par);
561 [ + + ]: 178 : if (ancestors.None()) return;
562 : 91 : chl_code %= ancestors.Count();
563 [ + - ]: 177 : for (auto i : ancestors) {
564 [ + + ]: 177 : if (chl_code == 0) {
565 : : chl = i;
566 : : break;
567 : : }
568 : 86 : --chl_code;
569 : : }
570 : : // Add the cycle-introducing dependency.
571 : 91 : depgraph.AddDependencies(TestBitSet::Singleton(par), chl);
572 : : // Check that we now detect a cycle.
573 [ - + ]: 91 : assert(!depgraph.IsAcyclic());
574 : 193 : }
575 : :
576 [ + - ]: 563 : FUZZ_TARGET(clusterlin_components)
577 : : {
578 : : // Verify the behavior of DepGraphs's FindConnectedComponent and IsConnected functions.
579 : :
580 : : // Construct a depgraph.
581 : 105 : SpanReader reader(buffer);
582 : 105 : DepGraph<TestBitSet> depgraph;
583 : 105 : std::vector<DepGraphIndex> linearization;
584 : 105 : try {
585 [ + - ]: 105 : reader >> Using<DepGraphFormatter>(depgraph);
586 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
587 : :
588 : 105 : TestBitSet todo = depgraph.Positions();
589 [ + + ]: 1222 : while (todo.Any()) {
590 : : // Pick a transaction in todo, or nothing.
591 : 1117 : std::optional<DepGraphIndex> picked;
592 : 1117 : {
593 : 1117 : uint64_t picked_num{0};
594 : 1117 : try {
595 [ + + ]: 1117 : reader >> VARINT(picked_num);
596 [ - + ]: 793 : } catch (const std::ios_base::failure&) {}
597 [ + + + + ]: 1117 : if (picked_num < todo.Size() && todo[picked_num]) {
598 : 161 : picked = picked_num;
599 : : }
600 : : }
601 : :
602 : : // Find a connected component inside todo, including picked if any.
603 [ + + ]: 1117 : auto component = picked ? depgraph.GetConnectedComponent(todo, *picked)
604 : 956 : : depgraph.FindConnectedComponent(todo);
605 : :
606 : : // The component must be a subset of todo and non-empty.
607 [ - + ]: 1117 : assert(component.IsSubsetOf(todo));
608 [ - + ]: 1117 : assert(component.Any());
609 : :
610 : : // If picked was provided, the component must include it.
611 [ + + - + ]: 1117 : if (picked) assert(component[*picked]);
612 : :
613 : : // If todo is the entire graph, and the entire graph is connected, then the component must
614 : : // be the entire graph.
615 [ + + ]: 1117 : if (todo == depgraph.Positions()) {
616 [ + + - + ]: 165 : assert((component == todo) == depgraph.IsConnected());
617 : : }
618 : :
619 : : // If subset is connected, then component must match subset.
620 [ + + - + ]: 1908 : assert((component == todo) == depgraph.IsConnected(todo));
621 : :
622 : : // The component cannot have any ancestors or descendants outside of component but in todo.
623 [ + - + + ]: 8141 : for (auto i : component) {
624 [ - + ]: 5907 : assert((depgraph.Ancestors(i) & todo).IsSubsetOf(component));
625 [ - + ]: 5907 : assert((depgraph.Descendants(i) & todo).IsSubsetOf(component));
626 : : }
627 : :
628 : : // Starting from any component element, we must be able to reach every element.
629 [ + - + + ]: 8141 : for (auto i : component) {
630 : : // Start with just i as reachable.
631 : 5907 : TestBitSet reachable = TestBitSet::Singleton(i);
632 : : // Add in-todo descendants and ancestors to reachable until it does not change anymore.
633 : 36803 : while (true) {
634 : 21355 : TestBitSet new_reachable = reachable;
635 [ + - + + ]: 249773 : for (auto j : new_reachable) {
636 : 207063 : new_reachable |= depgraph.Ancestors(j) & todo;
637 : 207063 : new_reachable |= depgraph.Descendants(j) & todo;
638 : : }
639 [ + + ]: 21355 : if (new_reachable == reachable) break;
640 : 15448 : reachable = new_reachable;
641 : 15448 : }
642 : : // Verify that the result is the entire component.
643 [ - + ]: 5907 : assert(component == reachable);
644 : : }
645 : :
646 : : // Construct an arbitrary subset of todo.
647 : 1117 : uint64_t subset_bits{0};
648 : 1117 : try {
649 [ + + ]: 1117 : reader >> VARINT(subset_bits);
650 [ - + ]: 807 : } catch (const std::ios_base::failure&) {}
651 : 1117 : TestBitSet subset;
652 [ + - + + ]: 26259 : for (DepGraphIndex i : depgraph.Positions()) {
653 [ + + ]: 24025 : if (todo[i]) {
654 [ + + ]: 12658 : if (subset_bits & 1) subset.Set(i);
655 : 12658 : subset_bits >>= 1;
656 : : }
657 : : }
658 : : // Which must be non-empty.
659 [ + + ]: 1117 : if (subset.None()) subset = TestBitSet::Singleton(todo.First());
660 : : // Remove it from todo.
661 : 1117 : todo -= subset;
662 : : }
663 : :
664 : : // No components can be found in an empty subset.
665 [ - + ]: 105 : assert(depgraph.FindConnectedComponent(todo).None());
666 : 105 : }
667 : :
668 [ + - ]: 616 : FUZZ_TARGET(clusterlin_make_connected)
669 : : {
670 : : // Verify that MakeConnected makes graphs connected.
671 : :
672 : 158 : SpanReader reader(buffer);
673 : 158 : DepGraph<TestBitSet> depgraph;
674 : 158 : try {
675 [ + - ]: 158 : reader >> Using<DepGraphFormatter>(depgraph);
676 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
677 [ + - ]: 158 : MakeConnected(depgraph);
678 [ + - ]: 158 : SanityCheck(depgraph);
679 [ - + ]: 158 : assert(depgraph.IsConnected());
680 : 158 : }
681 : :
682 [ + - ]: 552 : FUZZ_TARGET(clusterlin_chunking)
683 : : {
684 : : // Verify the correctness of the ChunkLinearization function.
685 : :
686 : : // Construct a graph by deserializing.
687 : 94 : SpanReader reader(buffer);
688 : 94 : DepGraph<TestBitSet> depgraph;
689 : 94 : try {
690 [ + - ]: 94 : reader >> Using<DepGraphFormatter>(depgraph);
691 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
692 : :
693 : : // Read a valid linearization for depgraph.
694 [ + - ]: 94 : auto linearization = ReadLinearization(depgraph, reader);
695 : :
696 : : // Invoke the chunking function.
697 [ - + ]: 94 : auto chunking = ChunkLinearization(depgraph, linearization);
698 : :
699 : : // Verify that chunk feerates are monotonically non-increasing.
700 [ - + + + ]: 349 : for (size_t i = 1; i < chunking.size(); ++i) {
701 [ - + ]: 255 : assert(!(chunking[i] >> chunking[i - 1]));
702 : : }
703 : :
704 : : // Naively recompute the chunks (each is the highest-feerate prefix of what remains).
705 : 94 : auto todo = depgraph.Positions();
706 [ + + ]: 437 : for (const auto& chunk_feerate : chunking) {
707 [ - + ]: 343 : assert(todo.Any());
708 : 343 : SetInfo<TestBitSet> accumulator, best;
709 [ + + ]: 7090 : for (DepGraphIndex idx : linearization) {
710 [ + + ]: 6747 : if (todo[idx]) {
711 : 3672 : accumulator.Set(depgraph, idx);
712 [ + + + + ]: 3672 : if (best.feerate.IsEmpty() || accumulator.feerate >> best.feerate) {
713 : 760 : best = accumulator;
714 : : }
715 : : }
716 : : }
717 [ + - ]: 343 : assert(chunk_feerate == best.feerate);
718 [ - + ]: 343 : assert(best.transactions.IsSubsetOf(todo));
719 : 343 : todo -= best.transactions;
720 : : }
721 [ - + ]: 94 : assert(todo.None());
722 : 94 : }
723 : :
724 [ + - ]: 568 : FUZZ_TARGET(clusterlin_ancestor_finder)
725 : : {
726 : : // Verify that AncestorCandidateFinder works as expected.
727 : :
728 : : // Retrieve a depgraph from the fuzz input.
729 : 110 : SpanReader reader(buffer);
730 : 110 : DepGraph<TestBitSet> depgraph;
731 : 110 : try {
732 [ + - ]: 110 : reader >> Using<DepGraphFormatter>(depgraph);
733 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
734 : :
735 : 110 : AncestorCandidateFinder anc_finder(depgraph);
736 : 110 : auto todo = depgraph.Positions();
737 [ + + ]: 1090 : while (todo.Any()) {
738 : : // Call the ancestor finder's FindCandidateSet for what remains of the graph.
739 [ - + ]: 980 : assert(!anc_finder.AllDone());
740 [ - + ]: 980 : assert(todo.Count() == anc_finder.NumRemaining());
741 : 980 : auto best_anc = anc_finder.FindCandidateSet();
742 : : // Sanity check the result.
743 [ - + ]: 980 : assert(best_anc.transactions.Any());
744 [ - + ]: 980 : assert(best_anc.transactions.IsSubsetOf(todo));
745 [ + - ]: 980 : assert(depgraph.FeeRate(best_anc.transactions) == best_anc.feerate);
746 [ - + ]: 980 : assert(depgraph.IsConnected(best_anc.transactions));
747 : : // Check that it is topologically valid.
748 [ + - + + ]: 3972 : for (auto i : best_anc.transactions) {
749 [ - + ]: 2012 : assert((depgraph.Ancestors(i) & todo).IsSubsetOf(best_anc.transactions));
750 : : }
751 : :
752 : : // Compute all remaining ancestor sets.
753 : 980 : std::optional<SetInfo<TestBitSet>> real_best_anc;
754 [ + - + + ]: 13336 : for (auto i : todo) {
755 : 11376 : SetInfo info(depgraph, todo & depgraph.Ancestors(i));
756 [ + + + + ]: 11376 : if (!real_best_anc.has_value() || info.feerate > real_best_anc->feerate) {
757 [ + + ]: 13963 : real_best_anc = info;
758 : : }
759 : : }
760 : : // The set returned by anc_finder must equal the real best ancestor sets.
761 [ - + ]: 980 : assert(real_best_anc.has_value());
762 [ + - ]: 980 : assert(*real_best_anc == best_anc);
763 : :
764 : : // Find a non-empty topologically valid subset of transactions to remove from the graph.
765 : : // Using an empty set would mean the next iteration is identical to the current one, and
766 : : // could cause an infinite loop.
767 [ + - ]: 980 : auto del_set = ReadTopologicalSet(depgraph, todo, reader, /*non_empty=*/true);
768 : 980 : todo -= del_set;
769 : 980 : anc_finder.MarkDone(del_set);
770 : : }
771 [ - + ]: 110 : assert(anc_finder.AllDone());
772 [ - + ]: 110 : assert(anc_finder.NumRemaining() == 0);
773 : 110 : }
774 : :
775 : : static constexpr auto MAX_SIMPLE_ITERATIONS = 300000;
776 : :
777 [ + - ]: 589 : FUZZ_TARGET(clusterlin_simple_finder)
778 : : {
779 : : // Verify that SimpleCandidateFinder works as expected by sanity checking the results
780 : : // and comparing them (if claimed to be optimal) against the sets found by
781 : : // ExhaustiveCandidateFinder and AncestorCandidateFinder.
782 : : //
783 : : // Note that SimpleCandidateFinder is only used in tests; the purpose of this fuzz test is to
784 : : // establish confidence in SimpleCandidateFinder, so that it can be used to test
785 : : // SearchCandidateFinder below.
786 : :
787 : : // Retrieve a depgraph from the fuzz input.
788 : 131 : SpanReader reader(buffer);
789 : 131 : DepGraph<TestBitSet> depgraph;
790 : 131 : try {
791 [ + - ]: 131 : reader >> Using<DepGraphFormatter>(depgraph);
792 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
793 : :
794 : : // Instantiate the SimpleCandidateFinder to be tested, and the ExhaustiveCandidateFinder and
795 : : // AncestorCandidateFinder it is being tested against.
796 : 131 : SimpleCandidateFinder smp_finder(depgraph);
797 : 131 : ExhaustiveCandidateFinder exh_finder(depgraph);
798 : 131 : AncestorCandidateFinder anc_finder(depgraph);
799 : :
800 : 131 : auto todo = depgraph.Positions();
801 [ + + ]: 1341 : while (todo.Any()) {
802 [ - + ]: 1210 : assert(!smp_finder.AllDone());
803 [ - + ]: 1210 : assert(!exh_finder.AllDone());
804 [ - + ]: 1210 : assert(!anc_finder.AllDone());
805 [ - + ]: 1210 : assert(anc_finder.NumRemaining() == todo.Count());
806 : :
807 : : // Call SimpleCandidateFinder.
808 [ - + ]: 1210 : auto [found, iterations_done] = smp_finder.FindCandidateSet(MAX_SIMPLE_ITERATIONS);
809 : 1210 : bool optimal = (iterations_done != MAX_SIMPLE_ITERATIONS);
810 : :
811 : : // Sanity check the result.
812 [ - + ]: 1210 : assert(iterations_done <= MAX_SIMPLE_ITERATIONS);
813 [ - + ]: 1210 : assert(found.transactions.Any());
814 [ - + ]: 1210 : assert(found.transactions.IsSubsetOf(todo));
815 [ + - ]: 1210 : assert(depgraph.FeeRate(found.transactions) == found.feerate);
816 : : // Check that it is topologically valid.
817 [ + - + + ]: 4575 : for (auto i : found.transactions) {
818 [ - + ]: 2155 : assert(found.transactions.IsSupersetOf(depgraph.Ancestors(i) & todo));
819 : : }
820 : :
821 : : // At most 2^(N-1) iterations can be required: the number of non-empty connected subsets a
822 : : // graph with N transactions can have. If MAX_SIMPLE_ITERATIONS exceeds this number, the
823 : : // result is necessarily optimal.
824 [ - + ]: 1210 : assert(iterations_done <= (uint64_t{1} << (todo.Count() - 1)));
825 [ + + - + ]: 1210 : if (MAX_SIMPLE_ITERATIONS > (uint64_t{1} << (todo.Count() - 1))) assert(optimal);
826 : :
827 : : // SimpleCandidateFinder only finds connected sets.
828 [ - + ]: 1210 : assert(depgraph.IsConnected(found.transactions));
829 : :
830 : : // Perform further quality checks only if SimpleCandidateFinder claims an optimal result.
831 [ + + ]: 1210 : if (optimal) {
832 : : // Compare with AncestorCandidateFinder.
833 : 1193 : auto anc = anc_finder.FindCandidateSet();
834 [ - + ]: 1193 : assert(anc.feerate <= found.feerate);
835 : :
836 [ + + ]: 1193 : if (todo.Count() <= 12) {
837 : : // Compare with ExhaustiveCandidateFinder. This quickly gets computationally
838 : : // expensive for large clusters (O(2^n)), so only do it for sufficiently small ones.
839 : 761 : auto exhaustive = exh_finder.FindCandidateSet();
840 [ + - ]: 761 : assert(exhaustive.feerate == found.feerate);
841 : : }
842 : :
843 : : // Compare with a non-empty topological set read from the fuzz input (comparing with an
844 : : // empty set is not interesting).
845 [ + - ]: 1193 : auto read_topo = ReadTopologicalSet(depgraph, todo, reader, /*non_empty=*/true);
846 [ - + ]: 1193 : assert(found.feerate >= depgraph.FeeRate(read_topo));
847 : : }
848 : :
849 : : // Find a non-empty topologically valid subset of transactions to remove from the graph.
850 : : // Using an empty set would mean the next iteration is identical to the current one, and
851 : : // could cause an infinite loop.
852 [ + - ]: 1210 : auto del_set = ReadTopologicalSet(depgraph, todo, reader, /*non_empty=*/true);
853 : 1210 : todo -= del_set;
854 : 1210 : smp_finder.MarkDone(del_set);
855 : 1210 : exh_finder.MarkDone(del_set);
856 : 1210 : anc_finder.MarkDone(del_set);
857 : : }
858 : :
859 [ - + ]: 131 : assert(smp_finder.AllDone());
860 [ - + ]: 131 : assert(exh_finder.AllDone());
861 [ - + ]: 131 : assert(anc_finder.AllDone());
862 [ - + ]: 131 : assert(anc_finder.NumRemaining() == 0);
863 : 131 : }
864 : :
865 [ + - ]: 816 : FUZZ_TARGET(clusterlin_search_finder)
866 : : {
867 : : // Verify that SearchCandidateFinder works as expected by sanity checking the results
868 : : // and comparing with the results from SimpleCandidateFinder and AncestorCandidateFinder,
869 : : // if the result is claimed to be optimal.
870 : :
871 : : // Retrieve an RNG seed, a depgraph, and whether to make it connected, from the fuzz input.
872 : 358 : SpanReader reader(buffer);
873 : 358 : DepGraph<TestBitSet> depgraph;
874 : 358 : uint64_t rng_seed{0};
875 : 358 : uint8_t make_connected{1};
876 : 358 : try {
877 [ + - + + : 358 : reader >> Using<DepGraphFormatter>(depgraph) >> rng_seed >> make_connected;
+ + ]
878 [ - + ]: 198 : } catch (const std::ios_base::failure&) {}
879 : : // The most complicated graphs are connected ones (other ones just split up). Optionally force
880 : : // the graph to be connected.
881 [ + + + - ]: 358 : if (make_connected) MakeConnected(depgraph);
882 : :
883 : : // Instantiate the candidate finders.
884 : 358 : SearchCandidateFinder src_finder(depgraph, rng_seed);
885 : 358 : SimpleCandidateFinder smp_finder(depgraph);
886 : 358 : AncestorCandidateFinder anc_finder(depgraph);
887 : :
888 : 358 : auto todo = depgraph.Positions();
889 [ + + ]: 6468 : while (todo.Any()) {
890 [ - + ]: 6110 : assert(!src_finder.AllDone());
891 [ - + ]: 6110 : assert(!smp_finder.AllDone());
892 [ - + ]: 6110 : assert(!anc_finder.AllDone());
893 [ - + ]: 6110 : assert(anc_finder.NumRemaining() == todo.Count());
894 : :
895 : : // For each iteration, read an iteration count limit from the fuzz input.
896 : 6110 : uint64_t max_iterations = 1;
897 : 6110 : try {
898 [ + + ]: 6110 : reader >> VARINT(max_iterations);
899 [ - + ]: 5022 : } catch (const std::ios_base::failure&) {}
900 : 6110 : max_iterations &= 0xfffff;
901 : :
902 : : // Read an initial subset from the fuzz input (allowed to be empty).
903 [ + - ]: 6110 : auto init_set = ReadTopologicalSet(depgraph, todo, reader, /*non_empty=*/false);
904 : 6110 : SetInfo init_best(depgraph, init_set);
905 : :
906 : : // Call the search finder's FindCandidateSet for what remains of the graph.
907 [ - + ]: 6110 : auto [found, iterations_done] = src_finder.FindCandidateSet(max_iterations, init_best);
908 : 6110 : bool optimal = iterations_done < max_iterations;
909 : :
910 : : // Sanity check the result.
911 [ - + ]: 6110 : assert(iterations_done <= max_iterations);
912 [ - + ]: 6110 : assert(found.transactions.Any());
913 [ - + ]: 6110 : assert(found.transactions.IsSubsetOf(todo));
914 [ + - ]: 6110 : assert(depgraph.FeeRate(found.transactions) == found.feerate);
915 [ + + - + ]: 6110 : if (!init_best.feerate.IsEmpty()) assert(found.feerate >= init_best.feerate);
916 : : // Check that it is topologically valid.
917 [ + - + + ]: 46563 : for (auto i : found.transactions) {
918 [ - + ]: 34343 : assert(found.transactions.IsSupersetOf(depgraph.Ancestors(i) & todo));
919 : : }
920 : :
921 : : // At most 2^(N-1) iterations can be required: the maximum number of non-empty topological
922 : : // subsets a (connected) cluster with N transactions can have. Even when the cluster is no
923 : : // longer connected after removing certain transactions, this holds, because the connected
924 : : // components are searched separately.
925 [ - + ]: 6110 : assert(iterations_done <= (uint64_t{1} << (todo.Count() - 1)));
926 : : // Additionally, test that no more than sqrt(2^N)+1 iterations are required. This is just
927 : : // an empirical bound that seems to hold, without proof. Still, add a test for it so we
928 : : // can learn about counterexamples if they exist.
929 [ + + + - ]: 6110 : if (iterations_done >= 1 && todo.Count() <= 63) {
930 [ + - ]: 4808 : Assume((iterations_done - 1) * (iterations_done - 1) <= uint64_t{1} << todo.Count());
931 : : }
932 : :
933 : : // Perform quality checks only if SearchCandidateFinder claims an optimal result.
934 [ + + ]: 6110 : if (optimal) {
935 : : // Optimal sets are always connected.
936 [ - + ]: 1791 : assert(depgraph.IsConnected(found.transactions));
937 : :
938 : : // Compare with SimpleCandidateFinder.
939 [ - + ]: 1791 : auto [simple, simple_iters] = smp_finder.FindCandidateSet(MAX_SIMPLE_ITERATIONS);
940 [ - + ]: 1791 : assert(found.feerate >= simple.feerate);
941 [ + + ]: 1791 : if (simple_iters < MAX_SIMPLE_ITERATIONS) {
942 [ + - ]: 1753 : assert(found.feerate == simple.feerate);
943 : : }
944 : :
945 : : // Compare with AncestorCandidateFinder;
946 : 1791 : auto anc = anc_finder.FindCandidateSet();
947 [ - + ]: 1791 : assert(found.feerate >= anc.feerate);
948 : :
949 : : // Compare with a non-empty topological set read from the fuzz input (comparing with an
950 : : // empty set is not interesting).
951 [ + - ]: 1791 : auto read_topo = ReadTopologicalSet(depgraph, todo, reader, /*non_empty=*/true);
952 [ - + ]: 1791 : assert(found.feerate >= depgraph.FeeRate(read_topo));
953 : : }
954 : :
955 : : // Find a non-empty topologically valid subset of transactions to remove from the graph.
956 : : // Using an empty set would mean the next iteration is identical to the current one, and
957 : : // could cause an infinite loop.
958 [ + - ]: 6110 : auto del_set = ReadTopologicalSet(depgraph, todo, reader, /*non_empty=*/true);
959 : 6110 : todo -= del_set;
960 : 6110 : src_finder.MarkDone(del_set);
961 : 6110 : smp_finder.MarkDone(del_set);
962 : 6110 : anc_finder.MarkDone(del_set);
963 : : }
964 : :
965 [ - + ]: 358 : assert(src_finder.AllDone());
966 [ - + ]: 358 : assert(smp_finder.AllDone());
967 [ - + ]: 358 : assert(anc_finder.AllDone());
968 [ - + ]: 358 : assert(anc_finder.NumRemaining() == 0);
969 : 358 : }
970 : :
971 [ + - ]: 588 : FUZZ_TARGET(clusterlin_linearization_chunking)
972 : : {
973 : : // Verify the behavior of LinearizationChunking.
974 : :
975 : : // Retrieve a depgraph from the fuzz input.
976 : 130 : SpanReader reader(buffer);
977 : 130 : DepGraph<TestBitSet> depgraph;
978 : 130 : try {
979 [ + - ]: 130 : reader >> Using<DepGraphFormatter>(depgraph);
980 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
981 : :
982 : : // Retrieve a topologically-valid subset of depgraph (allowed to be empty, because the argument
983 : : // to LinearizationChunking::Intersect is allowed to be empty).
984 : 130 : auto todo = depgraph.Positions();
985 [ + - ]: 130 : auto subset = SetInfo(depgraph, ReadTopologicalSet(depgraph, todo, reader, /*non_empty=*/false));
986 : :
987 : : // Retrieve a valid linearization for depgraph.
988 [ + - ]: 130 : auto linearization = ReadLinearization(depgraph, reader);
989 : :
990 : : // Construct a LinearizationChunking object, initially for the whole linearization.
991 [ - + ]: 130 : LinearizationChunking chunking(depgraph, linearization);
992 : :
993 : : // Incrementally remove transactions from the chunking object, and check various properties at
994 : : // every step.
995 [ + + ]: 1521 : while (todo.Any()) {
996 [ - + - + ]: 1261 : assert(chunking.NumChunksLeft() > 0);
997 : :
998 : : // Construct linearization with just todo.
999 : 1261 : std::vector<DepGraphIndex> linearization_left;
1000 [ + + ]: 29803 : for (auto i : linearization) {
1001 [ + + + - ]: 28542 : if (todo[i]) linearization_left.push_back(i);
1002 : : }
1003 : :
1004 : : // Compute the chunking for linearization_left.
1005 [ - + ]: 1261 : auto chunking_left = ChunkLinearization(depgraph, linearization_left);
1006 : :
1007 : : // Verify that it matches the feerates of the chunks of chunking.
1008 [ - + - + : 1261 : assert(chunking.NumChunksLeft() == chunking_left.size());
- + ]
1009 [ - + + + ]: 7981 : for (DepGraphIndex i = 0; i < chunking.NumChunksLeft(); ++i) {
1010 [ + - ]: 13440 : assert(chunking.GetChunk(i).feerate == chunking_left[i]);
1011 : : }
1012 : :
1013 : : // Check consistency of chunking.
1014 : 1261 : TestBitSet combined;
1015 [ - + + + ]: 7981 : for (DepGraphIndex i = 0; i < chunking.NumChunksLeft(); ++i) {
1016 : 6720 : const auto& chunk_info = chunking.GetChunk(i);
1017 : : // Chunks must be non-empty.
1018 [ - + ]: 6720 : assert(chunk_info.transactions.Any());
1019 : : // Chunk feerates must be monotonically non-increasing.
1020 [ + + - + ]: 6720 : if (i > 0) assert(!(chunk_info.feerate >> chunking.GetChunk(i - 1).feerate));
1021 : : // Chunks must be a subset of what is left of the linearization.
1022 [ - + ]: 6720 : assert(chunk_info.transactions.IsSubsetOf(todo));
1023 : : // Chunks' claimed feerates must match their transactions' aggregate feerate.
1024 [ + - ]: 6720 : assert(depgraph.FeeRate(chunk_info.transactions) == chunk_info.feerate);
1025 : : // Chunks must be the highest-feerate remaining prefix.
1026 : 6720 : SetInfo<TestBitSet> accumulator, best;
1027 [ + + ]: 187570 : for (auto j : linearization) {
1028 [ + + + + ]: 180850 : if (todo[j] && !combined[j]) {
1029 : 64623 : accumulator.Set(depgraph, j);
1030 [ + + + + ]: 64623 : if (best.feerate.IsEmpty() || accumulator.feerate > best.feerate) {
1031 : 12196 : best = accumulator;
1032 : : }
1033 : : }
1034 : : }
1035 [ - + ]: 6720 : assert(best.transactions == chunk_info.transactions);
1036 [ + - ]: 6720 : assert(best.feerate == chunk_info.feerate);
1037 : : // Chunks cannot overlap.
1038 [ - + ]: 6720 : assert(!chunk_info.transactions.Overlaps(combined));
1039 [ + - ]: 6720 : combined |= chunk_info.transactions;
1040 : : // Chunks must be topological.
1041 [ + - + + ]: 27996 : for (auto idx : chunk_info.transactions) {
1042 [ - + ]: 14556 : assert((depgraph.Ancestors(idx) & todo).IsSubsetOf(combined));
1043 : : }
1044 : : }
1045 [ - + ]: 1261 : assert(combined == todo);
1046 : :
1047 : : // Verify the expected properties of LinearizationChunking::IntersectPrefixes:
1048 : 1261 : auto intersect = chunking.IntersectPrefixes(subset);
1049 : : // - Intersecting again doesn't change the result.
1050 [ + - ]: 1261 : assert(chunking.IntersectPrefixes(intersect) == intersect);
1051 : : // - The intersection is topological.
1052 : 1261 : TestBitSet intersect_anc;
1053 [ + + + + ]: 4463 : for (auto idx : intersect.transactions) {
1054 : 2572 : intersect_anc |= (depgraph.Ancestors(idx) & todo);
1055 : : }
1056 [ - + ]: 1261 : assert(intersect.transactions == intersect_anc);
1057 : : // - The claimed intersection feerate matches its transactions.
1058 [ + - ]: 1261 : assert(intersect.feerate == depgraph.FeeRate(intersect.transactions));
1059 : : // - The intersection may only be empty if its input is empty.
1060 [ - + ]: 1261 : assert(intersect.transactions.Any() == subset.transactions.Any());
1061 : : // - The intersection feerate must be as high as the input.
1062 [ - + ]: 1261 : assert(intersect.feerate >= subset.feerate);
1063 : : // - No non-empty intersection between the intersection and a prefix of the chunks of the
1064 : : // remainder of the linearization may be better than the intersection.
1065 : 1261 : TestBitSet prefix;
1066 [ - + + + ]: 7981 : for (DepGraphIndex i = 0; i < chunking.NumChunksLeft(); ++i) {
1067 : 6720 : prefix |= chunking.GetChunk(i).transactions;
1068 : 6720 : auto reintersect = SetInfo(depgraph, prefix & intersect.transactions);
1069 [ + + ]: 6720 : if (!reintersect.feerate.IsEmpty()) {
1070 [ - + ]: 3478 : assert(reintersect.feerate <= intersect.feerate);
1071 : : }
1072 : : }
1073 : :
1074 : : // Find a non-empty topologically valid subset of transactions to remove from the graph.
1075 : : // Using an empty set would mean the next iteration is identical to the current one, and
1076 : : // could cause an infinite loop.
1077 [ + - ]: 1261 : auto done = ReadTopologicalSet(depgraph, todo, reader, /*non_empty=*/true);
1078 : 1261 : todo -= done;
1079 : 1261 : chunking.MarkDone(done);
1080 : 1261 : subset = SetInfo(depgraph, subset.transactions - done);
1081 : 1261 : }
1082 : :
1083 [ - + - + ]: 130 : assert(chunking.NumChunksLeft() == 0);
1084 : 130 : }
1085 : :
1086 [ + - ]: 703 : FUZZ_TARGET(clusterlin_simple_linearize)
1087 : : {
1088 : : // Verify the behavior of SimpleLinearize(). Note that SimpleLinearize is only used in tests;
1089 : : // the purpose of this fuzz test is to establish confidence in SimpleLinearize, so that it can
1090 : : // be used to test the real Linearize function in the fuzz test below.
1091 : :
1092 : : // Retrieve an iteration count and a depgraph from the fuzz input.
1093 : 245 : SpanReader reader(buffer);
1094 : 245 : uint64_t iter_count{0};
1095 : 245 : DepGraph<TestBitSet> depgraph;
1096 : 245 : try {
1097 [ + + + - ]: 245 : reader >> VARINT(iter_count) >> Using<DepGraphFormatter>(depgraph);
1098 [ - + ]: 4 : } catch (const std::ios_base::failure&) {}
1099 : 245 : iter_count %= MAX_SIMPLE_ITERATIONS;
1100 : :
1101 : : // Invoke SimpleLinearize().
1102 [ - + ]: 245 : auto [linearization, optimal] = SimpleLinearize(depgraph, iter_count);
1103 [ - + ]: 245 : SanityCheck(depgraph, linearization);
1104 [ - + ]: 245 : auto simple_chunking = ChunkLinearization(depgraph, linearization);
1105 : :
1106 : : // If the iteration count is sufficiently high, an optimal linearization must be found.
1107 : : // SimpleLinearize on k transactions can take up to 2^(k-1) iterations (one per non-empty
1108 : : // connected topologically valid subset), which sums over k=1..n to (2^n)-1.
1109 [ + - ]: 245 : const uint64_t n = depgraph.TxCount();
1110 [ + - + + ]: 245 : if (n <= 63 && (iter_count >> n)) {
1111 [ - + ]: 57 : assert(optimal);
1112 : : }
1113 : :
1114 : : // If SimpleLinearize claims optimal result, and the cluster is sufficiently small (there are
1115 : : // n! linearizations), test that the result is as good as every valid linearization.
1116 [ + + + + ]: 245 : if (optimal && depgraph.TxCount() <= 8) {
1117 [ + - ]: 108 : auto exh_linearization = ExhaustiveLinearize(depgraph);
1118 [ - + ]: 108 : auto exh_chunking = ChunkLinearization(depgraph, exh_linearization);
1119 [ - + - + : 108 : auto cmp = CompareChunks(simple_chunking, exh_chunking);
+ - ]
1120 [ - + ]: 108 : assert(cmp == 0);
1121 [ - + - + : 108 : assert(simple_chunking.size() == exh_chunking.size());
- + ]
1122 : 108 : }
1123 : :
1124 [ + + ]: 245 : if (optimal) {
1125 : : // Compare with a linearization read from the fuzz input.
1126 [ + - ]: 186 : auto read = ReadLinearization(depgraph, reader);
1127 [ - + ]: 186 : auto read_chunking = ChunkLinearization(depgraph, read);
1128 [ - + - + : 186 : auto cmp = CompareChunks(simple_chunking, read_chunking);
+ - ]
1129 [ - + ]: 186 : assert(cmp >= 0);
1130 : 186 : }
1131 : 245 : }
1132 : :
1133 [ + - ]: 931 : FUZZ_TARGET(clusterlin_linearize)
1134 : : {
1135 : : // Verify the behavior of Linearize().
1136 : :
1137 : : // Retrieve an RNG seed, an iteration count, a depgraph, and whether to make it connected from
1138 : : // the fuzz input.
1139 : 473 : SpanReader reader(buffer);
1140 : 473 : DepGraph<TestBitSet> depgraph;
1141 : 473 : uint64_t rng_seed{0};
1142 : 473 : uint64_t iter_count{0};
1143 : 473 : uint8_t make_connected{1};
1144 : 473 : try {
1145 [ + + + - : 473 : reader >> VARINT(iter_count) >> Using<DepGraphFormatter>(depgraph) >> rng_seed >> make_connected;
+ + + + ]
1146 [ - + ]: 368 : } catch (const std::ios_base::failure&) {}
1147 : : // The most complicated graphs are connected ones (other ones just split up). Optionally force
1148 : : // the graph to be connected.
1149 [ + + + - ]: 473 : if (make_connected) MakeConnected(depgraph);
1150 : :
1151 : : // Optionally construct an old linearization for it.
1152 : 473 : std::vector<DepGraphIndex> old_linearization;
1153 : 473 : {
1154 : 473 : uint8_t have_old_linearization{0};
1155 : 473 : try {
1156 [ + + ]: 473 : reader >> have_old_linearization;
1157 [ - + ]: 313 : } catch(const std::ios_base::failure&) {}
1158 [ + + ]: 473 : if (have_old_linearization & 1) {
1159 [ + - ]: 264 : old_linearization = ReadLinearization(depgraph, reader);
1160 [ - + ]: 132 : SanityCheck(depgraph, old_linearization);
1161 : : }
1162 : : }
1163 : :
1164 : : // Invoke Linearize().
1165 : 473 : iter_count &= 0x7ffff;
1166 [ - + - + ]: 473 : auto [linearization, optimal, cost] = Linearize(depgraph, iter_count, rng_seed, old_linearization);
1167 [ - + ]: 473 : assert(cost <= iter_count);
1168 [ - + ]: 473 : SanityCheck(depgraph, linearization);
1169 [ - + ]: 473 : auto chunking = ChunkLinearization(depgraph, linearization);
1170 : :
1171 : : // Linearization must always be as good as the old one, if provided.
1172 [ + + ]: 473 : if (!old_linearization.empty()) {
1173 [ - + ]: 128 : auto old_chunking = ChunkLinearization(depgraph, old_linearization);
1174 [ - + - + : 128 : auto cmp = CompareChunks(chunking, old_chunking);
+ - ]
1175 [ - + ]: 128 : assert(cmp >= 0);
1176 : 128 : }
1177 : :
1178 : : // If the iteration count is sufficiently high, an optimal linearization must be found.
1179 [ + + ]: 473 : if (iter_count >= MaxOptimalLinearizationIters(depgraph.TxCount())) {
1180 [ - + ]: 98 : assert(optimal);
1181 : : }
1182 : :
1183 : : // If Linearize claims optimal result, run quality tests.
1184 [ + + ]: 473 : if (optimal) {
1185 : : // It must be as good as SimpleLinearize.
1186 [ - + ]: 330 : auto [simple_linearization, simple_optimal] = SimpleLinearize(depgraph, MAX_SIMPLE_ITERATIONS);
1187 [ - + ]: 330 : SanityCheck(depgraph, simple_linearization);
1188 [ - + ]: 330 : auto simple_chunking = ChunkLinearization(depgraph, simple_linearization);
1189 [ - + - + : 330 : auto cmp = CompareChunks(chunking, simple_chunking);
+ - ]
1190 [ - + ]: 330 : assert(cmp >= 0);
1191 : : // If SimpleLinearize finds the optimal result too, they must be equal (if not,
1192 : : // SimpleLinearize is broken).
1193 [ + + - + ]: 330 : if (simple_optimal) assert(cmp == 0);
1194 : : // If simple_chunking is diagram-optimal, it cannot have more chunks than chunking (as
1195 : : // chunking is claimed to be optimal, which implies minimal chunks).
1196 [ + + - + : 330 : if (cmp == 0) assert(chunking.size() >= simple_chunking.size());
- + - + ]
1197 : :
1198 : : // Compare with a linearization read from the fuzz input.
1199 [ + - ]: 330 : auto read = ReadLinearization(depgraph, reader);
1200 [ - + ]: 330 : auto read_chunking = ChunkLinearization(depgraph, read);
1201 [ - + - + : 330 : auto cmp_read = CompareChunks(chunking, read_chunking);
+ - ]
1202 [ - + ]: 330 : assert(cmp_read >= 0);
1203 : 330 : }
1204 : 473 : }
1205 : :
1206 [ + - ]: 557 : FUZZ_TARGET(clusterlin_postlinearize)
1207 : : {
1208 : : // Verify expected properties of PostLinearize() on arbitrary linearizations.
1209 : :
1210 : : // Retrieve a depgraph from the fuzz input.
1211 : 99 : SpanReader reader(buffer);
1212 : 99 : DepGraph<TestBitSet> depgraph;
1213 : 99 : try {
1214 [ + - ]: 99 : reader >> Using<DepGraphFormatter>(depgraph);
1215 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
1216 : :
1217 : : // Retrieve a linearization from the fuzz input.
1218 : 99 : std::vector<DepGraphIndex> linearization;
1219 [ + - ]: 198 : linearization = ReadLinearization(depgraph, reader);
1220 [ - + ]: 99 : SanityCheck(depgraph, linearization);
1221 : :
1222 : : // Produce a post-processed version.
1223 [ + - ]: 99 : auto post_linearization = linearization;
1224 [ - + + - ]: 99 : PostLinearize(depgraph, post_linearization);
1225 [ - + ]: 99 : SanityCheck(depgraph, post_linearization);
1226 : :
1227 : : // Compare diagrams: post-linearization cannot worsen anywhere.
1228 [ - + ]: 99 : auto chunking = ChunkLinearization(depgraph, linearization);
1229 [ - + ]: 99 : auto post_chunking = ChunkLinearization(depgraph, post_linearization);
1230 [ - + - + : 99 : auto cmp = CompareChunks(post_chunking, chunking);
+ - ]
1231 [ - + ]: 99 : assert(cmp >= 0);
1232 : :
1233 : : // Run again, things can keep improving (and never get worse)
1234 [ + - ]: 99 : auto post_post_linearization = post_linearization;
1235 [ - + + - ]: 99 : PostLinearize(depgraph, post_post_linearization);
1236 [ - + ]: 99 : SanityCheck(depgraph, post_post_linearization);
1237 [ - + ]: 99 : auto post_post_chunking = ChunkLinearization(depgraph, post_post_linearization);
1238 [ - + - + : 99 : cmp = CompareChunks(post_post_chunking, post_chunking);
+ - ]
1239 [ - + ]: 99 : assert(cmp >= 0);
1240 : :
1241 : : // The chunks that come out of postlinearizing are always connected.
1242 [ - + ]: 99 : LinearizationChunking linchunking(depgraph, post_linearization);
1243 [ - + + + ]: 988 : while (linchunking.NumChunksLeft()) {
1244 [ - + ]: 790 : assert(depgraph.IsConnected(linchunking.GetChunk(0).transactions));
1245 : 790 : linchunking.MarkDone(linchunking.GetChunk(0).transactions);
1246 : : }
1247 : 99 : }
1248 : :
1249 [ + - ]: 857 : FUZZ_TARGET(clusterlin_postlinearize_tree)
1250 : : {
1251 : : // Verify expected properties of PostLinearize() on linearizations of graphs that form either
1252 : : // an upright or reverse tree structure.
1253 : :
1254 : : // Construct a direction, RNG seed, and an arbitrary graph from the fuzz input.
1255 : 399 : SpanReader reader(buffer);
1256 : 399 : uint64_t rng_seed{0};
1257 : 399 : DepGraph<TestBitSet> depgraph_gen;
1258 : 399 : uint8_t direction{0};
1259 : 399 : try {
1260 [ + - + + : 399 : reader >> direction >> rng_seed >> Using<DepGraphFormatter>(depgraph_gen);
+ - ]
1261 [ - + ]: 1 : } catch (const std::ios_base::failure&) {}
1262 : :
1263 : : // Now construct a new graph, copying the nodes, but leaving only the first parent (even
1264 : : // direction) or the first child (odd direction).
1265 : 399 : DepGraph<TestBitSet> depgraph_tree;
1266 [ - + + + ]: 11811 : for (DepGraphIndex i = 0; i < depgraph_gen.PositionRange(); ++i) {
1267 [ + + ]: 11412 : if (depgraph_gen.Positions()[i]) {
1268 : 9131 : depgraph_tree.AddTransaction(depgraph_gen.FeeRate(i));
1269 : : } else {
1270 : : // For holes, add a dummy transaction which is deleted below, so that non-hole
1271 : : // transactions retain their position.
1272 : 2281 : depgraph_tree.AddTransaction(FeeFrac{});
1273 : : }
1274 : : }
1275 : 399 : depgraph_tree.RemoveTransactions(TestBitSet::Fill(depgraph_gen.PositionRange()) - depgraph_gen.Positions());
1276 : :
1277 [ + + ]: 399 : if (direction & 1) {
1278 [ + + ]: 5932 : for (DepGraphIndex i = 0; i < depgraph_gen.TxCount(); ++i) {
1279 : 5693 : auto children = depgraph_gen.GetReducedChildren(i);
1280 [ + + ]: 5693 : if (children.Any()) {
1281 : 3104 : depgraph_tree.AddDependencies(TestBitSet::Singleton(i), children.First());
1282 : : }
1283 : : }
1284 : : } else {
1285 [ + + ]: 3598 : for (DepGraphIndex i = 0; i < depgraph_gen.TxCount(); ++i) {
1286 : 3438 : auto parents = depgraph_gen.GetReducedParents(i);
1287 [ + + ]: 3438 : if (parents.Any()) {
1288 : 1535 : depgraph_tree.AddDependencies(TestBitSet::Singleton(parents.First()), i);
1289 : : }
1290 : : }
1291 : : }
1292 : :
1293 : : // Retrieve a linearization from the fuzz input.
1294 : 399 : std::vector<DepGraphIndex> linearization;
1295 [ + - ]: 798 : linearization = ReadLinearization(depgraph_tree, reader);
1296 [ - + ]: 399 : SanityCheck(depgraph_tree, linearization);
1297 : :
1298 : : // Produce a postlinearized version.
1299 [ + - ]: 399 : auto post_linearization = linearization;
1300 [ - + + - ]: 399 : PostLinearize(depgraph_tree, post_linearization);
1301 [ - + ]: 399 : SanityCheck(depgraph_tree, post_linearization);
1302 : :
1303 : : // Compare diagrams.
1304 [ - + ]: 399 : auto chunking = ChunkLinearization(depgraph_tree, linearization);
1305 [ - + ]: 399 : auto post_chunking = ChunkLinearization(depgraph_tree, post_linearization);
1306 [ - + - + : 399 : auto cmp = CompareChunks(post_chunking, chunking);
+ - ]
1307 [ - + ]: 399 : assert(cmp >= 0);
1308 : :
1309 : : // Verify that post-linearizing again does not change the diagram. The result must be identical
1310 : : // as post_linearization ought to be optimal already with a tree-structured graph.
1311 [ + - ]: 399 : auto post_post_linearization = post_linearization;
1312 [ - + + - ]: 399 : PostLinearize(depgraph_tree, post_linearization);
1313 [ - + ]: 399 : SanityCheck(depgraph_tree, post_linearization);
1314 [ - + ]: 399 : auto post_post_chunking = ChunkLinearization(depgraph_tree, post_post_linearization);
1315 [ - + - + : 399 : auto cmp_post = CompareChunks(post_post_chunking, post_chunking);
+ - ]
1316 [ - + ]: 399 : assert(cmp_post == 0);
1317 : :
1318 : : // Try to find an even better linearization directly. This must not change the diagram for the
1319 : : // same reason.
1320 [ - + - + ]: 399 : auto [opt_linearization, _optimal, _cost] = Linearize(depgraph_tree, 100000, rng_seed, post_linearization);
1321 [ - + ]: 399 : auto opt_chunking = ChunkLinearization(depgraph_tree, opt_linearization);
1322 [ - + - + : 399 : auto cmp_opt = CompareChunks(opt_chunking, post_chunking);
+ - ]
1323 [ - + ]: 399 : assert(cmp_opt == 0);
1324 : 399 : }
1325 : :
1326 [ + - ]: 572 : FUZZ_TARGET(clusterlin_postlinearize_moved_leaf)
1327 : : {
1328 : : // Verify that taking an existing linearization, and moving a leaf to the back, potentially
1329 : : // increasing its fee, and then post-linearizing, results in something as good as the
1330 : : // original. This guarantees that in an RBF that replaces a transaction with one of the same
1331 : : // size but higher fee, applying the "remove conflicts, append new transaction, postlinearize"
1332 : : // process will never worsen linearization quality.
1333 : :
1334 : : // Construct an arbitrary graph and a fee from the fuzz input.
1335 : 114 : SpanReader reader(buffer);
1336 : 114 : DepGraph<TestBitSet> depgraph;
1337 : 114 : int32_t fee_inc{0};
1338 : 114 : try {
1339 : 114 : uint64_t fee_inc_code;
1340 [ + - + + ]: 114 : reader >> Using<DepGraphFormatter>(depgraph) >> VARINT(fee_inc_code);
1341 : 36 : fee_inc = fee_inc_code & 0x3ffff;
1342 [ - + ]: 78 : } catch (const std::ios_base::failure&) {}
1343 [ + + ]: 114 : if (depgraph.TxCount() == 0) return;
1344 : :
1345 : : // Retrieve two linearizations from the fuzz input.
1346 [ + - ]: 105 : auto lin = ReadLinearization(depgraph, reader);
1347 [ + - ]: 105 : auto lin_leaf = ReadLinearization(depgraph, reader);
1348 : :
1349 : : // Construct a linearization identical to lin, but with the tail end of lin_leaf moved to the
1350 : : // back.
1351 : 105 : std::vector<DepGraphIndex> lin_moved;
1352 [ + + ]: 1265 : for (auto i : lin) {
1353 [ + + + - ]: 1160 : if (i != lin_leaf.back()) lin_moved.push_back(i);
1354 : : }
1355 [ + - ]: 105 : lin_moved.push_back(lin_leaf.back());
1356 : :
1357 : : // Postlinearize lin_moved.
1358 [ - + + - ]: 105 : PostLinearize(depgraph, lin_moved);
1359 [ - + ]: 105 : SanityCheck(depgraph, lin_moved);
1360 : :
1361 : : // Compare diagrams (applying the fee delta after computing the old one).
1362 [ - + ]: 105 : auto old_chunking = ChunkLinearization(depgraph, lin);
1363 [ - + ]: 105 : depgraph.FeeRate(lin_leaf.back()).fee += fee_inc;
1364 [ - + ]: 105 : auto new_chunking = ChunkLinearization(depgraph, lin_moved);
1365 [ - + - + : 105 : auto cmp = CompareChunks(new_chunking, old_chunking);
+ - ]
1366 [ - + ]: 105 : assert(cmp >= 0);
1367 : 114 : }
1368 : :
1369 [ + - ]: 628 : FUZZ_TARGET(clusterlin_merge)
1370 : : {
1371 : : // Construct an arbitrary graph from the fuzz input.
1372 : 170 : SpanReader reader(buffer);
1373 : 170 : DepGraph<TestBitSet> depgraph;
1374 : 170 : try {
1375 [ + - ]: 170 : reader >> Using<DepGraphFormatter>(depgraph);
1376 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
1377 : :
1378 : : // Retrieve two linearizations from the fuzz input.
1379 [ + - ]: 170 : auto lin1 = ReadLinearization(depgraph, reader);
1380 [ + - ]: 170 : auto lin2 = ReadLinearization(depgraph, reader);
1381 : :
1382 : : // Merge the two.
1383 [ - + - + : 170 : auto lin_merged = MergeLinearizations(depgraph, lin1, lin2);
+ - ]
1384 : :
1385 : : // Compute chunkings and compare.
1386 [ - + ]: 170 : auto chunking1 = ChunkLinearization(depgraph, lin1);
1387 [ - + ]: 170 : auto chunking2 = ChunkLinearization(depgraph, lin2);
1388 [ - + ]: 170 : auto chunking_merged = ChunkLinearization(depgraph, lin_merged);
1389 [ - + - + : 170 : auto cmp1 = CompareChunks(chunking_merged, chunking1);
+ - ]
1390 [ - + ]: 170 : assert(cmp1 >= 0);
1391 [ - + - + : 170 : auto cmp2 = CompareChunks(chunking_merged, chunking2);
+ - ]
1392 [ - + ]: 170 : assert(cmp2 >= 0);
1393 : 170 : }
1394 : :
1395 [ + - ]: 554 : FUZZ_TARGET(clusterlin_fix_linearization)
1396 : : {
1397 : : // Verify expected properties of FixLinearization() on arbitrary linearizations.
1398 : :
1399 : : // Retrieve a depgraph from the fuzz input.
1400 : 96 : SpanReader reader(buffer);
1401 : 96 : DepGraph<TestBitSet> depgraph;
1402 : 96 : try {
1403 [ + - ]: 96 : reader >> Using<DepGraphFormatter>(depgraph);
1404 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
1405 : :
1406 : : // Construct an arbitrary linearization (not necessarily topological for depgraph).
1407 : 96 : std::vector<DepGraphIndex> linearization;
1408 : : /** Which transactions of depgraph are yet to be included in linearization. */
1409 : 96 : TestBitSet todo = depgraph.Positions();
1410 [ + + ]: 1120 : while (todo.Any()) {
1411 : : // Read a number from the fuzz input in range [0, todo.Count()).
1412 : 928 : uint64_t val{0};
1413 : 928 : try {
1414 [ + + ]: 928 : reader >> VARINT(val);
1415 [ - + ]: 706 : } catch (const std::ios_base::failure&) {}
1416 [ + - ]: 928 : val %= todo.Count();
1417 : : // Find the val'th element in todo, remove it from todo, and append it to linearization.
1418 [ + - + - ]: 2557 : for (auto idx : todo) {
1419 [ + + ]: 1629 : if (val == 0) {
1420 [ + - ]: 928 : linearization.push_back(idx);
1421 : 928 : todo.Reset(idx);
1422 : 928 : break;
1423 : : }
1424 : 701 : --val;
1425 : : }
1426 : : }
1427 [ - + - + ]: 96 : assert(linearization.size() == depgraph.TxCount());
1428 : :
1429 : : // Determine what prefix of linearization is topological, i.e., the position of the first entry
1430 : : // in linearization which corresponds to a transaction that is not preceded by all its
1431 : : // ancestors.
1432 : 96 : size_t topo_prefix = 0;
1433 : 96 : todo = depgraph.Positions();
1434 [ - + + + ]: 614 : while (topo_prefix < linearization.size()) {
1435 : 552 : DepGraphIndex idx = linearization[topo_prefix];
1436 : 552 : todo.Reset(idx);
1437 [ + + ]: 552 : if (todo.Overlaps(depgraph.Ancestors(idx))) break;
1438 : 518 : ++topo_prefix;
1439 : : }
1440 : :
1441 : : // Then make a fixed copy of linearization.
1442 [ + - ]: 96 : auto linearization_fixed = linearization;
1443 [ - + ]: 96 : FixLinearization(depgraph, linearization_fixed);
1444 : : // Sanity check it (which includes testing whether it is topological).
1445 [ - + ]: 96 : SanityCheck(depgraph, linearization_fixed);
1446 : :
1447 : : // FixLinearization does not modify the topological prefix of linearization.
1448 [ - + ]: 96 : assert(std::equal(linearization.begin(), linearization.begin() + topo_prefix,
1449 : : linearization_fixed.begin()));
1450 : : // This also means that if linearization was entirely topological, FixLinearization cannot have
1451 : : // modified it. This is implied by the assertion above already, but repeat it explicitly.
1452 [ - + + + ]: 96 : if (topo_prefix == linearization.size()) {
1453 [ - + ]: 62 : assert(linearization == linearization_fixed);
1454 : : }
1455 : 96 : }
|
