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 : 744 : SimpleCandidateFinder(const DepGraph<SetType>& depgraph LIFETIMEBOUND) noexcept :
97 : 744 : m_depgraph(depgraph), m_todo{depgraph.Positions()} {}
98 : :
99 : : /** Remove a set of transactions from the set of to-be-linearized ones. */
100 : 7779 : void MarkDone(SetType select) noexcept { m_todo -= select; }
101 : :
102 : : /** Determine whether unlinearized transactions remain. */
103 : 5773 : 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 : 3828 : std::pair<SetInfo<SetType>, uint64_t> FindCandidateSet(uint64_t max_iterations) const noexcept
114 : : {
115 : 3828 : 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 : 3828 : std::vector<std::pair<SetType, SetType>> queue;
120 : : // Initially we have just one queue element, with the entire graph in und.
121 : 3828 : queue.emplace_back(SetType{}, m_todo);
122 : : // Best solution so far. Initialize with the remaining ancestors of the first remaining
123 : : // transaction.
124 : 3828 : SetInfo best(m_depgraph, m_depgraph.Ancestors(m_todo.First()) & m_todo);
125 : : // Process the queue.
126 [ + + + + ]: 14584394 : while (!queue.empty() && iterations_left) {
127 : : // Pop top element of the queue.
128 : 14580566 : auto [inc, und] = queue.back();
129 : 14580566 : queue.pop_back();
130 : : // Look for a transaction to consider adding/removing.
131 : 14580566 : bool inc_none = inc.None();
132 [ + + ]: 19937743 : 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 [ + + + + ]: 12645614 : if (inc_none || inc.Overlaps(m_depgraph.Ancestors(split))) {
137 : 7288437 : --iterations_left;
138 : : // Add a queue entry with split included.
139 : 7288437 : SetInfo new_inc(m_depgraph, inc | (m_todo & m_depgraph.Ancestors(split)));
140 : 7288437 : queue.emplace_back(new_inc.transactions, und - new_inc.transactions);
141 : : // Add a queue entry with split excluded.
142 : 7288437 : queue.emplace_back(inc, und - m_depgraph.Descendants(split));
143 : : // Update statistics to account for the candidate new_inc.
144 [ + + ]: 7288437 : if (new_inc.feerate > best.feerate) best = new_inc;
145 : : break;
146 : : }
147 : : }
148 : : }
149 : 3828 : return {std::move(best), max_iterations - iterations_left};
150 : 3828 : }
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 : 0 : ExhaustiveCandidateFinder(const DepGraph<SetType>& depgraph LIFETIMEBOUND) noexcept :
169 : 0 : m_depgraph(depgraph), m_todo{depgraph.Positions()} {}
170 : :
171 : : /** Remove a set of transactions from the set of to-be-linearized ones. */
172 : 0 : void MarkDone(SetType select) noexcept { m_todo -= select; }
173 : :
174 : : /** Determine whether unlinearized transactions remain. */
175 : 0 : 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 : 0 : SetInfo<SetType> FindCandidateSet() const noexcept
182 : : {
183 : : // Best solution so far.
184 : 0 : SetInfo<SetType> best{m_todo, m_depgraph.FeeRate(m_todo)};
185 : : // The number of combinations to try.
186 : 0 : uint64_t limit = (uint64_t{1} << m_todo.Count()) - 1;
187 : : // Try the transitive closure of every non-empty subset of m_todo.
188 [ # # ]: 0 : 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 : 0 : SetType txn;
192 : 0 : auto x_shifted{x};
193 [ # # # # ]: 0 : for (auto i : m_todo) {
194 [ # # ]: 0 : if (x_shifted & 1) txn |= m_depgraph.Ancestors(i);
195 : 0 : x_shifted >>= 1;
196 : : }
197 : 0 : SetInfo cur(m_depgraph, txn & m_todo);
198 [ # # ]: 0 : if (cur.feerate > best.feerate) best = cur;
199 : : }
200 : 0 : 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 : 355 : std::pair<std::vector<DepGraphIndex>, bool> SimpleLinearize(const DepGraph<SetType>& depgraph, uint64_t max_iterations)
212 : : {
213 : 355 : std::vector<DepGraphIndex> linearization;
214 : 355 : SimpleCandidateFinder finder(depgraph);
215 : 355 : SetType todo = depgraph.Positions();
216 : 355 : bool optimal = true;
217 [ + + ]: 2750 : while (todo.Any()) {
218 [ + + ]: 2395 : auto [candidate, iterations_done] = finder.FindCandidateSet(max_iterations);
219 [ + + ]: 2395 : if (iterations_done == max_iterations) optimal = false;
220 : 2395 : depgraph.AppendTopo(linearization, candidate.transactions);
221 : 2395 : todo -= candidate.transactions;
222 : 2395 : finder.MarkDone(candidate.transactions);
223 : 2395 : max_iterations -= iterations_done;
224 : : }
225 : 355 : return {std::move(linearization), optimal};
226 : 355 : }
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 : 0 : std::vector<DepGraphIndex> ExhaustiveLinearize(const DepGraph<SetType>& depgraph)
237 : : {
238 : : // The best linearization so far, and its chunking.
239 : 0 : std::vector<DepGraphIndex> linearization;
240 : 0 : std::vector<FeeFrac> chunking;
241 : :
242 [ # # ]: 0 : std::vector<DepGraphIndex> perm_linearization;
243 : : // Initialize with the lexicographically-first linearization.
244 [ # # # # : 0 : 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 : 0 : DepGraphIndex topo_length{0};
249 : 0 : TestBitSet perm_done;
250 [ # # ]: 0 : while (topo_length < perm_linearization.size()) {
251 : 0 : auto i = perm_linearization[topo_length];
252 [ # # ]: 0 : perm_done.Set(i);
253 [ # # ]: 0 : if (!depgraph.Ancestors(i).IsSubsetOf(perm_done)) break;
254 : 0 : ++topo_length;
255 : : }
256 [ # # ]: 0 : 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 [ # # ]: 0 : auto perm_chunking = ChunkLinearization(depgraph, perm_linearization);
260 [ # # ]: 0 : 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 [ # # # # : 0 : if (linearization.empty() || cmp > 0 || (cmp == 0 && perm_chunking.size() > chunking.size())) {
# # # # ]
264 [ # # ]: 0 : linearization = perm_linearization;
265 [ # # ]: 0 : chunking = perm_chunking;
266 : : }
267 : 0 : } else {
268 : : // Otherwise, fast forward to the last permutation with the same non-topological
269 : : // prefix.
270 : 0 : auto first_non_topo = perm_linearization.begin() + topo_length;
271 [ # # ]: 0 : assert(std::is_sorted(first_non_topo + 1, perm_linearization.end()));
272 : 0 : std::reverse(first_non_topo + 1, perm_linearization.end());
273 : : }
274 [ # # ]: 0 : } while(std::next_permutation(perm_linearization.begin(), perm_linearization.end()));
275 : :
276 : 0 : return linearization;
277 : 0 : }
278 : :
279 : :
280 : : /** Stitch connected components together in a DepGraph, guaranteeing its corresponding cluster is connected. */
281 : : template<typename BS>
282 : 1013 : void MakeConnected(DepGraph<BS>& depgraph)
283 : : {
284 : 1013 : auto todo = depgraph.Positions();
285 : 1013 : auto comp = depgraph.FindConnectedComponent(todo);
286 : 1013 : Assume(depgraph.IsConnected(comp));
287 : 1013 : todo -= comp;
288 [ + + ]: 12049 : while (todo.Any()) {
289 : 11036 : auto nextcomp = depgraph.FindConnectedComponent(todo);
290 : 11036 : Assume(depgraph.IsConnected(nextcomp));
291 : 11036 : depgraph.AddDependencies(BS::Singleton(comp.Last()), nextcomp.First());
292 : 11036 : todo -= nextcomp;
293 : 11036 : comp = nextcomp;
294 : : }
295 : 1013 : }
296 : :
297 : : /** Given a dependency graph, and a todo set, read a topological subset of todo from reader. */
298 : : template<typename SetType>
299 : 15061 : 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 [ + + ]: 15061 : uint64_t mask{0};
304 : : try {
305 [ + + ]: 15061 : reader >> VARINT(mask);
306 [ - + ]: 12086 : } catch(const std::ios_base::failure&) {}
307 : 15061 : mask += non_empty;
308 : :
309 : 15061 : SetType ret;
310 [ + + + + ]: 220329 : for (auto i : todo) {
311 [ + + ]: 190214 : if (!ret[i]) {
312 [ + + ]: 186165 : if (mask & 1) ret |= depgraph.Ancestors(i);
313 : 186165 : mask >>= 1;
314 : : }
315 : : }
316 : 15061 : 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 [ + + + + ]: 15061 : if (non_empty && ret.None()) {
322 : 64 : Assume(todo.Any());
323 : 64 : ret = depgraph.Ancestors(todo.First()) & todo;
324 : 64 : Assume(ret.Any());
325 : : }
326 : 15061 : return ret;
327 : : }
328 : :
329 : : /** Given a dependency graph, construct any valid linearization for it, reading from a SpanReader. */
330 : : template<typename BS>
331 : 2049 : std::vector<DepGraphIndex> ReadLinearization(const DepGraph<BS>& depgraph, SpanReader& reader)
332 : : {
333 : 2049 : std::vector<DepGraphIndex> linearization;
334 : 2049 : TestBitSet todo = depgraph.Positions();
335 : : // In every iteration one topologically-valid transaction is appended to linearization.
336 [ + + ]: 41610 : while (todo.Any()) {
337 : : // Compute the set of transactions with no not-yet-included ancestors.
338 : 37512 : TestBitSet potential_next;
339 [ + + ]: 543395 : for (auto j : todo) {
340 [ + + ]: 783307 : if ((depgraph.Ancestors(j) & todo) == TestBitSet::Singleton(j)) {
341 : 277424 : potential_next.Set(j);
342 : : }
343 : : }
344 : : // There must always be one (otherwise there is a cycle in the graph).
345 [ - + ]: 37512 : assert(potential_next.Any());
346 : : // Read a number from reader, and interpret it as index into potential_next.
347 [ + + ]: 37512 : uint64_t idx{0};
348 : : try {
349 [ + + + - ]: 75024 : reader >> VARINT(idx);
350 [ - + ]: 31526 : } catch (const std::ios_base::failure&) {}
351 : 37512 : idx %= potential_next.Count();
352 : : // Find out which transaction that corresponds to.
353 [ + - + - ]: 93393 : for (auto j : potential_next) {
354 [ + + ]: 55881 : if (idx == 0) {
355 : : // When found, add it to linearization and remove it from todo.
356 [ + - ]: 37512 : linearization.push_back(j);
357 [ - + ]: 37512 : assert(todo[j]);
358 : 37512 : todo.Reset(j);
359 : 37512 : break;
360 : : }
361 : 18369 : --idx;
362 : : }
363 : : }
364 : 2049 : return linearization;
365 : 0 : }
366 : :
367 : : } // namespace
368 : :
369 [ + - ]: 750 : FUZZ_TARGET(clusterlin_depgraph_sim)
370 : : {
371 : : // Simulation test to verify the full behavior of DepGraph.
372 : :
373 : 300 : FuzzedDataProvider provider(buffer.data(), buffer.size());
374 : :
375 : : /** Real DepGraph being tested. */
376 : 300 : 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 : 300 : std::array<std::optional<std::pair<FeeFrac, TestBitSet>>, TestBitSet::Size()> sim;
380 : : /** The number of non-nullopt position in sim. */
381 : 300 : DepGraphIndex num_tx_sim{0};
382 : :
383 : : /** Read a valid index of a transaction from the provider. */
384 : 21480 : auto idx_fn = [&]() {
385 : 21180 : auto offset = provider.ConsumeIntegralInRange<DepGraphIndex>(0, num_tx_sim - 1);
386 [ + - ]: 186180 : for (DepGraphIndex i = 0; i < sim.size(); ++i) {
387 [ + + ]: 186180 : if (!sim[i].has_value()) continue;
388 [ + + ]: 167218 : if (offset == 0) return i;
389 : 146038 : --offset;
390 : : }
391 : 0 : assert(false);
392 : : return DepGraphIndex(-1);
393 : 300 : };
394 : :
395 : : /** Read a valid subset of the transactions from the provider. */
396 : 21480 : auto subset_fn = [&]() {
397 : 21180 : auto range = (uint64_t{1} << num_tx_sim) - 1;
398 : 21180 : const auto mask = provider.ConsumeIntegralInRange<uint64_t>(0, range);
399 : 21180 : auto mask_shifted = mask;
400 : 21180 : TestBitSet subset;
401 [ + + ]: 698940 : for (DepGraphIndex i = 0; i < sim.size(); ++i) {
402 [ + + ]: 677760 : if (!sim[i].has_value()) continue;
403 [ + + ]: 427437 : if (mask_shifted & 1) {
404 : 144683 : subset.Set(i);
405 : : }
406 : 427437 : mask_shifted >>= 1;
407 : : }
408 [ - + ]: 21180 : assert(mask_shifted == 0);
409 : 21180 : return subset;
410 : 300 : };
411 : :
412 : : /** Read any set of transactions from the provider (including unused positions). */
413 : 12018 : auto set_fn = [&]() {
414 : 11718 : auto range = (uint64_t{1} << sim.size()) - 1;
415 : 11718 : const auto mask = provider.ConsumeIntegralInRange<uint64_t>(0, range);
416 : 11718 : TestBitSet set;
417 [ + + ]: 386694 : for (DepGraphIndex i = 0; i < sim.size(); ++i) {
418 [ + + ]: 374976 : if ((mask >> i) & 1) {
419 : 116635 : set.Set(i);
420 : : }
421 : : }
422 : 11718 : return set;
423 : 300 : };
424 : :
425 : : /** Propagate ancestor information in sim. */
426 : 12318 : auto anc_update_fn = [&]() {
427 : 14174 : while (true) {
428 : 14174 : bool updates{false};
429 [ + + ]: 467742 : for (DepGraphIndex chl = 0; chl < sim.size(); ++chl) {
430 [ + + ]: 453568 : if (!sim[chl].has_value()) continue;
431 [ + - + + ]: 1139616 : for (auto par : sim[chl]->second) {
432 [ + + ]: 723688 : if (!sim[chl]->second.IsSupersetOf(sim[par]->second)) {
433 : 11395 : sim[chl]->second |= sim[par]->second;
434 : 11395 : updates = true;
435 : : }
436 : : }
437 : : }
438 [ + + ]: 14174 : if (!updates) break;
439 : : }
440 : 12318 : };
441 : :
442 : : /** Compare the state of transaction i in the simulation with the real one. */
443 : 126535 : auto check_fn = [&](DepGraphIndex i) {
444 : : // Compare used positions.
445 [ - + ]: 126235 : assert(real.Positions()[i] == sim[i].has_value());
446 [ + + ]: 126235 : if (sim[i].has_value()) {
447 : : // Compare feerate.
448 [ + - ]: 23561 : 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 [ - + ]: 23561 : assert(real.Ancestors(i) == sim[i]->second);
452 : : }
453 : 126535 : };
454 : :
455 [ + + + + ]: 56759 : LIMITED_WHILE(provider.remaining_bytes() > 0, 1000) {
456 : 56459 : uint8_t command = provider.ConsumeIntegral<uint8_t>();
457 [ + + + + : 56459 : if (num_tx_sim == 0 || ((command % 3) <= 0 && num_tx_sim < TestBitSet::Size())) {
+ + ]
458 : : // AddTransaction.
459 : 23561 : auto fee = provider.ConsumeIntegralInRange<int64_t>(-0x8000000000000, 0x7ffffffffffff);
460 : 23561 : auto size = provider.ConsumeIntegralInRange<int32_t>(1, 0x3fffff);
461 : 23561 : FeeFrac feerate{fee, size};
462 : : // Apply to DepGraph.
463 : 23561 : auto idx = real.AddTransaction(feerate);
464 : : // Verify that the returned index is correct.
465 [ - + ]: 23561 : assert(!sim[idx].has_value());
466 [ + - ]: 332393 : for (DepGraphIndex i = 0; i < TestBitSet::Size(); ++i) {
467 [ + + ]: 332393 : if (!sim[i].has_value()) {
468 [ - + ]: 23561 : assert(idx == i);
469 : : break;
470 : : }
471 : : }
472 : : // Update sim.
473 [ - + ]: 23561 : sim[idx] = {feerate, TestBitSet::Singleton(idx)};
474 : 23561 : ++num_tx_sim;
475 : 23561 : continue;
476 : 23561 : }
477 [ + + ]: 32898 : if ((command % 3) <= 1 && num_tx_sim > 0) {
478 : : // AddDependencies.
479 : 21180 : DepGraphIndex child = idx_fn();
480 : 21180 : auto parents = subset_fn();
481 : : // Apply to DepGraph.
482 : 21180 : real.AddDependencies(parents, child);
483 : : // Apply to sim.
484 : 21180 : sim[child]->second |= parents;
485 : 21180 : continue;
486 : 21180 : }
487 : 11718 : if (num_tx_sim > 0) {
488 : : // Remove transactions.
489 : 11718 : 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 : 11718 : anc_update_fn();
493 : : // Compare the state of the transactions being deleted.
494 [ + + + + ]: 138373 : for (auto i : del) check_fn(i);
495 : : // Apply to DepGraph.
496 : 11718 : real.RemoveTransactions(del);
497 : : // Apply to sim.
498 [ + + ]: 386694 : for (DepGraphIndex i = 0; i < sim.size(); ++i) {
499 [ + + ]: 374976 : if (sim[i].has_value()) {
500 [ + + ]: 154411 : if (del[i]) {
501 : 18722 : --num_tx_sim;
502 [ + - ]: 393698 : sim[i] = std::nullopt;
503 : : } else {
504 : 135689 : sim[i]->second -= del;
505 : : }
506 : : }
507 : : }
508 : 11718 : continue;
509 : 11718 : }
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 : 300 : anc_update_fn();
516 [ + + ]: 9900 : for (DepGraphIndex i = 0; i < sim.size(); ++i) check_fn(i);
517 [ - + ]: 300 : assert(real.TxCount() == num_tx_sim);
518 : : // Sanity check the result (which includes round-tripping serialization, if applicable).
519 [ + - ]: 300 : SanityCheck(real);
520 : 300 : }
521 : :
522 [ + - ]: 656 : 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 : 206 : SpanReader reader(buffer);
528 : 206 : DepGraph<TestBitSet> depgraph;
529 : 206 : DepGraphIndex par_code{0}, chl_code{0};
530 : 206 : try {
531 [ + - + + : 206 : reader >> Using<DepGraphFormatter>(depgraph) >> VARINT(par_code) >> VARINT(chl_code);
+ + ]
532 [ - + ]: 175 : } catch (const std::ios_base::failure&) {}
533 [ + - ]: 206 : SanityCheck(depgraph);
534 : :
535 : : // Verify the graph is a DAG.
536 [ - + ]: 206 : assert(depgraph.IsAcyclic());
537 : :
538 : : // Introduce a cycle, and then test that IsAcyclic returns false.
539 [ + + ]: 206 : if (depgraph.TxCount() < 2) return;
540 : 188 : DepGraphIndex par(0), chl(0);
541 : : // Pick any transaction of depgraph as parent.
542 [ + - ]: 188 : par_code %= depgraph.TxCount();
543 [ + - + - ]: 571 : for (auto i : depgraph.Positions()) {
544 [ + + ]: 383 : if (par_code == 0) {
545 : : par = i;
546 : : break;
547 : : }
548 : 195 : --par_code;
549 : : }
550 : : // Pick any ancestor of par (excluding itself) as child, if any.
551 [ + + ]: 188 : auto ancestors = depgraph.Ancestors(par) - TestBitSet::Singleton(par);
552 [ + + ]: 188 : if (ancestors.None()) return;
553 : 87 : chl_code %= ancestors.Count();
554 [ + - ]: 173 : for (auto i : ancestors) {
555 [ + + ]: 173 : if (chl_code == 0) {
556 : : chl = i;
557 : : break;
558 : : }
559 : 86 : --chl_code;
560 : : }
561 : : // Add the cycle-introducing dependency.
562 : 87 : depgraph.AddDependencies(TestBitSet::Singleton(par), chl);
563 : : // Check that we now detect a cycle.
564 [ - + ]: 87 : assert(!depgraph.IsAcyclic());
565 : 206 : }
566 : :
567 [ + - ]: 585 : FUZZ_TARGET(clusterlin_components)
568 : : {
569 : : // Verify the behavior of DepGraphs's FindConnectedComponent and IsConnected functions.
570 : :
571 : : // Construct a depgraph.
572 : 135 : SpanReader reader(buffer);
573 : 135 : DepGraph<TestBitSet> depgraph;
574 : 135 : std::vector<DepGraphIndex> linearization;
575 : 135 : try {
576 [ + - ]: 135 : reader >> Using<DepGraphFormatter>(depgraph);
577 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
578 : :
579 : 135 : TestBitSet todo = depgraph.Positions();
580 [ + + ]: 1809 : while (todo.Any()) {
581 : : // Pick a transaction in todo, or nothing.
582 : 1674 : std::optional<DepGraphIndex> picked;
583 : 1674 : {
584 : 1674 : uint64_t picked_num{0};
585 : 1674 : try {
586 [ + + ]: 1674 : reader >> VARINT(picked_num);
587 [ - + ]: 1211 : } catch (const std::ios_base::failure&) {}
588 [ + + + + ]: 1674 : if (picked_num < todo.Size() && todo[picked_num]) {
589 : 167 : picked = picked_num;
590 : : }
591 : : }
592 : :
593 : : // Find a connected component inside todo, including picked if any.
594 [ + + ]: 1674 : auto component = picked ? depgraph.GetConnectedComponent(todo, *picked)
595 : 1507 : : depgraph.FindConnectedComponent(todo);
596 : :
597 : : // The component must be a subset of todo and non-empty.
598 [ - + ]: 1674 : assert(component.IsSubsetOf(todo));
599 [ - + ]: 1674 : assert(component.Any());
600 : :
601 : : // If picked was provided, the component must include it.
602 [ + + - + ]: 1674 : 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 [ + + ]: 1674 : if (todo == depgraph.Positions()) {
607 [ + + - + ]: 220 : assert((component == todo) == depgraph.IsConnected());
608 : : }
609 : :
610 : : // If subset is connected, then component must match subset.
611 [ + + - + ]: 2895 : assert((component == todo) == depgraph.IsConnected(todo));
612 : :
613 : : // The component cannot have any ancestors or descendants outside of component but in todo.
614 [ + - + + ]: 12587 : for (auto i : component) {
615 [ - + ]: 9239 : assert((depgraph.Ancestors(i) & todo).IsSubsetOf(component));
616 [ - + ]: 9239 : assert((depgraph.Descendants(i) & todo).IsSubsetOf(component));
617 : : }
618 : :
619 : : // Starting from any component element, we must be able to reach every element.
620 [ + - + + ]: 12587 : for (auto i : component) {
621 : : // Start with just i as reachable.
622 : 9239 : TestBitSet reachable = TestBitSet::Singleton(i);
623 : : // Add in-todo descendants and ancestors to reachable until it does not change anymore.
624 : 70571 : while (true) {
625 : 39905 : TestBitSet new_reachable = reachable;
626 [ + - + + ]: 492430 : for (auto j : new_reachable) {
627 : 412620 : new_reachable |= depgraph.Ancestors(j) & todo;
628 : 412620 : new_reachable |= depgraph.Descendants(j) & todo;
629 : : }
630 [ + + ]: 39905 : if (new_reachable == reachable) break;
631 : 30666 : reachable = new_reachable;
632 : 30666 : }
633 : : // Verify that the result is the entire component.
634 [ - + ]: 9239 : assert(component == reachable);
635 : : }
636 : :
637 : : // Construct an arbitrary subset of todo.
638 : 1674 : uint64_t subset_bits{0};
639 : 1674 : try {
640 [ + + ]: 1674 : reader >> VARINT(subset_bits);
641 [ - + ]: 1231 : } catch (const std::ios_base::failure&) {}
642 : 1674 : TestBitSet subset;
643 [ + - + + ]: 41995 : for (DepGraphIndex i : depgraph.Positions()) {
644 [ + + ]: 38647 : if (todo[i]) {
645 [ + + ]: 19987 : if (subset_bits & 1) subset.Set(i);
646 : 19987 : subset_bits >>= 1;
647 : : }
648 : : }
649 : : // Which must be non-empty.
650 [ + + ]: 1674 : if (subset.None()) subset = TestBitSet::Singleton(todo.First());
651 : : // Remove it from todo.
652 : 1674 : todo -= subset;
653 : : }
654 : :
655 : : // No components can be found in an empty subset.
656 [ - + ]: 135 : assert(depgraph.FindConnectedComponent(todo).None());
657 : 135 : }
658 : :
659 [ + - ]: 655 : FUZZ_TARGET(clusterlin_make_connected)
660 : : {
661 : : // Verify that MakeConnected makes graphs connected.
662 : :
663 : 205 : SpanReader reader(buffer);
664 : 205 : DepGraph<TestBitSet> depgraph;
665 : 205 : try {
666 [ + - ]: 205 : reader >> Using<DepGraphFormatter>(depgraph);
667 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
668 [ + - ]: 205 : MakeConnected(depgraph);
669 [ + - ]: 205 : SanityCheck(depgraph);
670 [ - + ]: 205 : assert(depgraph.IsConnected());
671 : 205 : }
672 : :
673 [ + - ]: 553 : FUZZ_TARGET(clusterlin_chunking)
674 : : {
675 : : // Verify the correctness of the ChunkLinearization function.
676 : :
677 : : // Construct a graph by deserializing.
678 : 103 : SpanReader reader(buffer);
679 : 103 : DepGraph<TestBitSet> depgraph;
680 : 103 : try {
681 [ + - ]: 103 : reader >> Using<DepGraphFormatter>(depgraph);
682 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
683 : :
684 : : // Read a valid linearization for depgraph.
685 [ + - ]: 103 : auto linearization = ReadLinearization(depgraph, reader);
686 : :
687 : : // Invoke the chunking function.
688 : 103 : auto chunking = ChunkLinearization(depgraph, linearization);
689 : :
690 : : // Verify that chunk feerates are monotonically non-increasing.
691 [ + + ]: 434 : for (size_t i = 1; i < chunking.size(); ++i) {
692 [ - + ]: 331 : assert(!(chunking[i] >> chunking[i - 1]));
693 : : }
694 : :
695 : : // Naively recompute the chunks (each is the highest-feerate prefix of what remains).
696 : 103 : auto todo = depgraph.Positions();
697 [ + + ]: 530 : for (const auto& chunk_feerate : chunking) {
698 [ - + ]: 427 : assert(todo.Any());
699 : 427 : SetInfo<TestBitSet> accumulator, best;
700 [ + + ]: 9393 : for (DepGraphIndex idx : linearization) {
701 [ + + ]: 8966 : if (todo[idx]) {
702 : 4784 : accumulator.Set(depgraph, idx);
703 [ + + + + ]: 4784 : if (best.feerate.IsEmpty() || accumulator.feerate >> best.feerate) {
704 : 919 : best = accumulator;
705 : : }
706 : : }
707 : : }
708 [ + - ]: 427 : assert(chunk_feerate == best.feerate);
709 [ - + ]: 427 : assert(best.transactions.IsSubsetOf(todo));
710 : 427 : todo -= best.transactions;
711 : : }
712 [ - + ]: 103 : assert(todo.None());
713 : 103 : }
714 : :
715 [ + - ]: 591 : FUZZ_TARGET(clusterlin_ancestor_finder)
716 : : {
717 : : // Verify that AncestorCandidateFinder works as expected.
718 : :
719 : : // Retrieve a depgraph from the fuzz input.
720 : 141 : SpanReader reader(buffer);
721 : 141 : DepGraph<TestBitSet> depgraph;
722 : 141 : try {
723 [ + - ]: 141 : reader >> Using<DepGraphFormatter>(depgraph);
724 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
725 : :
726 : 141 : AncestorCandidateFinder anc_finder(depgraph);
727 : 141 : auto todo = depgraph.Positions();
728 [ + + ]: 1157 : while (todo.Any()) {
729 : : // Call the ancestor finder's FindCandidateSet for what remains of the graph.
730 [ - + ]: 1016 : assert(!anc_finder.AllDone());
731 [ - + ]: 1016 : assert(todo.Count() == anc_finder.NumRemaining());
732 : 1016 : auto best_anc = anc_finder.FindCandidateSet();
733 : : // Sanity check the result.
734 [ - + ]: 1016 : assert(best_anc.transactions.Any());
735 [ - + ]: 1016 : assert(best_anc.transactions.IsSubsetOf(todo));
736 [ + - ]: 1016 : assert(depgraph.FeeRate(best_anc.transactions) == best_anc.feerate);
737 [ - + ]: 1016 : assert(depgraph.IsConnected(best_anc.transactions));
738 : : // Check that it is topologically valid.
739 [ + - + + ]: 4214 : for (auto i : best_anc.transactions) {
740 [ - + ]: 2182 : assert((depgraph.Ancestors(i) & todo).IsSubsetOf(best_anc.transactions));
741 : : }
742 : :
743 : : // Compute all remaining ancestor sets.
744 : 1016 : std::optional<SetInfo<TestBitSet>> real_best_anc;
745 [ + - + + ]: 12890 : for (auto i : todo) {
746 : 10858 : SetInfo info(depgraph, todo & depgraph.Ancestors(i));
747 [ + + + + ]: 10858 : if (!real_best_anc.has_value() || info.feerate > real_best_anc->feerate) {
748 [ + + ]: 13161 : real_best_anc = info;
749 : : }
750 : : }
751 : : // The set returned by anc_finder must equal the real best ancestor sets.
752 [ - + ]: 1016 : assert(real_best_anc.has_value());
753 [ + - ]: 1016 : 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 [ + - ]: 1016 : auto del_set = ReadTopologicalSet(depgraph, todo, reader, /*non_empty=*/true);
759 : 1016 : todo -= del_set;
760 : 1016 : anc_finder.MarkDone(del_set);
761 : : }
762 [ - + ]: 141 : assert(anc_finder.AllDone());
763 [ - + ]: 141 : assert(anc_finder.NumRemaining() == 0);
764 : 141 : }
765 : :
766 : : static constexpr auto MAX_SIMPLE_ITERATIONS = 300000;
767 : :
768 [ + - ]: 450 : 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 : 0 : SpanReader reader(buffer);
780 : 0 : DepGraph<TestBitSet> depgraph;
781 : 0 : try {
782 [ # # ]: 0 : 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 : 0 : SimpleCandidateFinder smp_finder(depgraph);
788 : 0 : ExhaustiveCandidateFinder exh_finder(depgraph);
789 : 0 : AncestorCandidateFinder anc_finder(depgraph);
790 : :
791 : 0 : auto todo = depgraph.Positions();
792 [ # # ]: 0 : while (todo.Any()) {
793 [ # # ]: 0 : assert(!smp_finder.AllDone());
794 [ # # ]: 0 : assert(!exh_finder.AllDone());
795 [ # # ]: 0 : assert(!anc_finder.AllDone());
796 [ # # ]: 0 : assert(anc_finder.NumRemaining() == todo.Count());
797 : :
798 : : // Call SimpleCandidateFinder.
799 [ # # ]: 0 : auto [found, iterations_done] = smp_finder.FindCandidateSet(MAX_SIMPLE_ITERATIONS);
800 : 0 : bool optimal = (iterations_done != MAX_SIMPLE_ITERATIONS);
801 : :
802 : : // Sanity check the result.
803 [ # # ]: 0 : assert(iterations_done <= MAX_SIMPLE_ITERATIONS);
804 [ # # ]: 0 : assert(found.transactions.Any());
805 [ # # ]: 0 : assert(found.transactions.IsSubsetOf(todo));
806 [ # # ]: 0 : assert(depgraph.FeeRate(found.transactions) == found.feerate);
807 : : // Check that it is topologically valid.
808 [ # # # # ]: 0 : for (auto i : found.transactions) {
809 [ # # ]: 0 : 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 [ # # ]: 0 : assert(iterations_done <= (uint64_t{1} << (todo.Count() - 1)));
816 [ # # # # ]: 0 : if (MAX_SIMPLE_ITERATIONS > (uint64_t{1} << (todo.Count() - 1))) assert(optimal);
817 : :
818 : : // SimpleCandidateFinder only finds connected sets.
819 [ # # ]: 0 : assert(depgraph.IsConnected(found.transactions));
820 : :
821 : : // Perform further quality checks only if SimpleCandidateFinder claims an optimal result.
822 [ # # ]: 0 : if (optimal) {
823 : : // Compare with AncestorCandidateFinder.
824 : 0 : auto anc = anc_finder.FindCandidateSet();
825 [ # # ]: 0 : assert(anc.feerate <= found.feerate);
826 : :
827 [ # # ]: 0 : 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 : 0 : auto exhaustive = exh_finder.FindCandidateSet();
831 [ # # ]: 0 : 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 [ # # ]: 0 : auto read_topo = ReadTopologicalSet(depgraph, todo, reader, /*non_empty=*/true);
837 [ # # ]: 0 : 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 [ # # ]: 0 : auto del_set = ReadTopologicalSet(depgraph, todo, reader, /*non_empty=*/true);
844 : 0 : todo -= del_set;
845 : 0 : smp_finder.MarkDone(del_set);
846 : 0 : exh_finder.MarkDone(del_set);
847 : 0 : anc_finder.MarkDone(del_set);
848 : : }
849 : :
850 [ # # ]: 0 : assert(smp_finder.AllDone());
851 [ # # ]: 0 : assert(exh_finder.AllDone());
852 [ # # ]: 0 : assert(anc_finder.AllDone());
853 [ # # ]: 0 : assert(anc_finder.NumRemaining() == 0);
854 : 0 : }
855 : :
856 [ + - ]: 839 : 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 : 389 : SpanReader reader(buffer);
864 : 389 : DepGraph<TestBitSet> depgraph;
865 : 389 : uint64_t rng_seed{0};
866 : 389 : uint8_t make_connected{1};
867 : 389 : try {
868 [ + - + + : 389 : reader >> Using<DepGraphFormatter>(depgraph) >> rng_seed >> make_connected;
+ - ]
869 [ - + ]: 197 : } 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 [ + + + - ]: 389 : if (make_connected) MakeConnected(depgraph);
873 : :
874 : : // Instantiate the candidate finders.
875 : 389 : SearchCandidateFinder src_finder(depgraph, rng_seed);
876 : 389 : SimpleCandidateFinder smp_finder(depgraph);
877 : 389 : AncestorCandidateFinder anc_finder(depgraph);
878 : :
879 : 389 : auto todo = depgraph.Positions();
880 [ + + ]: 5773 : while (todo.Any()) {
881 [ - + ]: 5384 : assert(!src_finder.AllDone());
882 [ - + ]: 5384 : assert(!smp_finder.AllDone());
883 [ - + ]: 5384 : assert(!anc_finder.AllDone());
884 [ - + ]: 5384 : assert(anc_finder.NumRemaining() == todo.Count());
885 : :
886 : : // For each iteration, read an iteration count limit from the fuzz input.
887 : 5384 : uint64_t max_iterations = 1;
888 : 5384 : try {
889 [ + + ]: 5384 : reader >> VARINT(max_iterations);
890 [ - + ]: 4390 : } catch (const std::ios_base::failure&) {}
891 : 5384 : max_iterations &= 0xfffff;
892 : :
893 : : // Read an initial subset from the fuzz input (allowed to be empty).
894 [ + - ]: 5384 : auto init_set = ReadTopologicalSet(depgraph, todo, reader, /*non_empty=*/false);
895 : 5384 : SetInfo init_best(depgraph, init_set);
896 : :
897 : : // Call the search finder's FindCandidateSet for what remains of the graph.
898 [ - + ]: 5384 : auto [found, iterations_done] = src_finder.FindCandidateSet(max_iterations, init_best);
899 : 5384 : bool optimal = iterations_done < max_iterations;
900 : :
901 : : // Sanity check the result.
902 [ - + ]: 5384 : assert(iterations_done <= max_iterations);
903 [ - + ]: 5384 : assert(found.transactions.Any());
904 [ - + ]: 5384 : assert(found.transactions.IsSubsetOf(todo));
905 [ + - ]: 5384 : assert(depgraph.FeeRate(found.transactions) == found.feerate);
906 [ + + - + ]: 5384 : if (!init_best.feerate.IsEmpty()) assert(found.feerate >= init_best.feerate);
907 : : // Check that it is topologically valid.
908 [ + - + + ]: 42535 : for (auto i : found.transactions) {
909 [ - + ]: 31767 : 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 [ - + ]: 5384 : 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 [ + + + - ]: 5384 : if (iterations_done >= 1 && todo.Count() <= 63) {
921 [ + - ]: 4222 : 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 [ + + ]: 5384 : if (optimal) {
926 : : // Optimal sets are always connected.
927 [ - + ]: 1433 : assert(depgraph.IsConnected(found.transactions));
928 : :
929 : : // Compare with SimpleCandidateFinder.
930 [ - + ]: 1433 : auto [simple, simple_iters] = smp_finder.FindCandidateSet(MAX_SIMPLE_ITERATIONS);
931 [ - + ]: 1433 : assert(found.feerate >= simple.feerate);
932 [ + + ]: 1433 : if (simple_iters < MAX_SIMPLE_ITERATIONS) {
933 [ + - ]: 1428 : assert(found.feerate == simple.feerate);
934 : : }
935 : :
936 : : // Compare with AncestorCandidateFinder;
937 : 1433 : auto anc = anc_finder.FindCandidateSet();
938 [ - + ]: 1433 : 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 [ + - ]: 1433 : auto read_topo = ReadTopologicalSet(depgraph, todo, reader, /*non_empty=*/true);
943 [ - + ]: 1433 : 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 [ + - ]: 5384 : auto del_set = ReadTopologicalSet(depgraph, todo, reader, /*non_empty=*/true);
950 : 5384 : todo -= del_set;
951 : 5384 : src_finder.MarkDone(del_set);
952 : 5384 : smp_finder.MarkDone(del_set);
953 : 5384 : anc_finder.MarkDone(del_set);
954 : : }
955 : :
956 [ - + ]: 389 : assert(src_finder.AllDone());
957 [ - + ]: 389 : assert(smp_finder.AllDone());
958 [ - + ]: 389 : assert(anc_finder.AllDone());
959 [ - + ]: 389 : assert(anc_finder.NumRemaining() == 0);
960 : 389 : }
961 : :
962 [ + - ]: 615 : 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 [ + - ]: 450 : 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 : 0 : SpanReader reader(buffer);
1085 : 0 : uint64_t iter_count{0};
1086 : 0 : DepGraph<TestBitSet> depgraph;
1087 : 0 : try {
1088 [ # # # # ]: 0 : reader >> VARINT(iter_count) >> Using<DepGraphFormatter>(depgraph);
1089 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
1090 : 0 : iter_count %= MAX_SIMPLE_ITERATIONS;
1091 : :
1092 : : // Invoke SimpleLinearize().
1093 : 0 : auto [linearization, optimal] = SimpleLinearize(depgraph, iter_count);
1094 : 0 : SanityCheck(depgraph, linearization);
1095 : 0 : 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 [ # # ]: 0 : const uint64_t n = depgraph.TxCount();
1101 [ # # # # ]: 0 : if (n <= 63 && (iter_count >> n)) {
1102 [ # # ]: 0 : 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 [ # # # # ]: 0 : if (optimal && depgraph.TxCount() <= 8) {
1108 [ # # ]: 0 : auto exh_linearization = ExhaustiveLinearize(depgraph);
1109 : 0 : auto exh_chunking = ChunkLinearization(depgraph, exh_linearization);
1110 [ # # ]: 0 : auto cmp = CompareChunks(simple_chunking, exh_chunking);
1111 [ # # ]: 0 : assert(cmp == 0);
1112 [ # # ]: 0 : assert(simple_chunking.size() == exh_chunking.size());
1113 : 0 : }
1114 : :
1115 [ # # ]: 0 : if (optimal) {
1116 : : // Compare with a linearization read from the fuzz input.
1117 [ # # ]: 0 : auto read = ReadLinearization(depgraph, reader);
1118 : 0 : auto read_chunking = ChunkLinearization(depgraph, read);
1119 [ # # ]: 0 : auto cmp = CompareChunks(simple_chunking, read_chunking);
1120 [ # # ]: 0 : assert(cmp >= 0);
1121 : 0 : }
1122 : 0 : }
1123 : :
1124 [ + - ]: 958 : 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 : 508 : SpanReader reader(buffer);
1131 : 508 : DepGraph<TestBitSet> depgraph;
1132 : 508 : uint64_t rng_seed{0};
1133 : 508 : uint64_t iter_count{0};
1134 : 508 : uint8_t make_connected{1};
1135 : 508 : try {
1136 [ + + + - : 508 : reader >> VARINT(iter_count) >> Using<DepGraphFormatter>(depgraph) >> rng_seed >> make_connected;
+ + + + ]
1137 [ - + ]: 406 : } 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 [ + + + - ]: 508 : if (make_connected) MakeConnected(depgraph);
1141 : :
1142 : : // Optionally construct an old linearization for it.
1143 : 508 : std::vector<DepGraphIndex> old_linearization;
1144 : 508 : {
1145 : 508 : uint8_t have_old_linearization{0};
1146 : 508 : try {
1147 [ + + ]: 508 : reader >> have_old_linearization;
1148 [ - + ]: 336 : } catch(const std::ios_base::failure&) {}
1149 [ + + ]: 508 : if (have_old_linearization & 1) {
1150 [ + - ]: 296 : old_linearization = ReadLinearization(depgraph, reader);
1151 : 148 : SanityCheck(depgraph, old_linearization);
1152 : : }
1153 : : }
1154 : :
1155 : : // Invoke Linearize().
1156 : 508 : iter_count &= 0x7ffff;
1157 : 508 : auto [linearization, optimal] = Linearize(depgraph, iter_count, rng_seed, old_linearization);
1158 : 508 : SanityCheck(depgraph, linearization);
1159 : 508 : auto chunking = ChunkLinearization(depgraph, linearization);
1160 : :
1161 : : // Linearization must always be as good as the old one, if provided.
1162 [ + + ]: 508 : if (!old_linearization.empty()) {
1163 : 147 : auto old_chunking = ChunkLinearization(depgraph, old_linearization);
1164 [ + - ]: 147 : auto cmp = CompareChunks(chunking, old_chunking);
1165 [ - + ]: 147 : assert(cmp >= 0);
1166 : 147 : }
1167 : :
1168 : : // If the iteration count is sufficiently high, an optimal linearization must be found.
1169 : : // Each linearization step can use up to 2^(k-1) iterations, with steps k=1..n. That sum is
1170 : : // 2^n - 1.
1171 [ + + ]: 508 : const uint64_t n = depgraph.TxCount();
1172 [ + + + + ]: 508 : if (n <= 19 && iter_count > (uint64_t{1} << n)) {
1173 [ - + ]: 65 : assert(optimal);
1174 : : }
1175 : : // Additionally, if the assumption of sqrt(2^k)+1 iterations per step holds, plus ceil(k/4)
1176 : : // start-up cost per step, plus ceil(n^2/64) start-up cost overall, we can compute the upper
1177 : : // bound for a whole linearization (summing for k=1..n) using the Python expression
1178 : : // [sum((k+3)//4 + int(math.sqrt(2**k)) + 1 for k in range(1, n + 1)) + (n**2 + 63) // 64 for n in range(0, 35)]:
1179 : 508 : static constexpr uint64_t MAX_OPTIMAL_ITERS[] = {
1180 : : 0, 4, 8, 12, 18, 26, 37, 51, 70, 97, 133, 182, 251, 346, 480, 666, 927, 1296, 1815, 2545,
1181 : : 3576, 5031, 7087, 9991, 14094, 19895, 28096, 39690, 56083, 79263, 112041, 158391, 223936,
1182 : : 316629, 447712
1183 : : };
1184 [ + - + + ]: 508 : if (n < std::size(MAX_OPTIMAL_ITERS) && iter_count >= MAX_OPTIMAL_ITERS[n]) {
1185 [ + - ]: 126 : Assume(optimal);
1186 : : }
1187 : :
1188 : : // If Linearize claims optimal result, run quality tests.
1189 [ + + ]: 508 : if (optimal) {
1190 : : // It must be as good as SimpleLinearize.
1191 : 355 : auto [simple_linearization, simple_optimal] = SimpleLinearize(depgraph, MAX_SIMPLE_ITERATIONS);
1192 : 355 : SanityCheck(depgraph, simple_linearization);
1193 : 355 : auto simple_chunking = ChunkLinearization(depgraph, simple_linearization);
1194 [ + - ]: 355 : auto cmp = CompareChunks(chunking, simple_chunking);
1195 [ - + ]: 355 : assert(cmp >= 0);
1196 : : // If SimpleLinearize finds the optimal result too, they must be equal (if not,
1197 : : // SimpleLinearize is broken).
1198 [ + + - + ]: 355 : if (simple_optimal) assert(cmp == 0);
1199 : : // If simple_chunking is diagram-optimal, it cannot have more chunks than chunking (as
1200 : : // chunking is claimed to be optimal, which implies minimal chunks).
1201 [ + + - + ]: 355 : if (cmp == 0) assert(chunking.size() >= simple_chunking.size());
1202 : :
1203 : : // Compare with a linearization read from the fuzz input.
1204 [ + - ]: 355 : auto read = ReadLinearization(depgraph, reader);
1205 : 355 : auto read_chunking = ChunkLinearization(depgraph, read);
1206 [ + - ]: 355 : auto cmp_read = CompareChunks(chunking, read_chunking);
1207 [ - + ]: 355 : assert(cmp_read >= 0);
1208 : 355 : }
1209 : 508 : }
1210 : :
1211 [ + - ]: 579 : FUZZ_TARGET(clusterlin_postlinearize)
1212 : : {
1213 : : // Verify expected properties of PostLinearize() on arbitrary linearizations.
1214 : :
1215 : : // Retrieve a depgraph from the fuzz input.
1216 : 129 : SpanReader reader(buffer);
1217 : 129 : DepGraph<TestBitSet> depgraph;
1218 : 129 : try {
1219 [ + - ]: 129 : reader >> Using<DepGraphFormatter>(depgraph);
1220 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
1221 : :
1222 : : // Retrieve a linearization from the fuzz input.
1223 : 129 : std::vector<DepGraphIndex> linearization;
1224 [ + - ]: 258 : linearization = ReadLinearization(depgraph, reader);
1225 : 129 : SanityCheck(depgraph, linearization);
1226 : :
1227 : : // Produce a post-processed version.
1228 [ + - ]: 129 : auto post_linearization = linearization;
1229 [ + - ]: 129 : PostLinearize(depgraph, post_linearization);
1230 : 129 : SanityCheck(depgraph, post_linearization);
1231 : :
1232 : : // Compare diagrams: post-linearization cannot worsen anywhere.
1233 : 129 : auto chunking = ChunkLinearization(depgraph, linearization);
1234 : 129 : auto post_chunking = ChunkLinearization(depgraph, post_linearization);
1235 [ + - ]: 129 : auto cmp = CompareChunks(post_chunking, chunking);
1236 [ - + ]: 129 : assert(cmp >= 0);
1237 : :
1238 : : // Run again, things can keep improving (and never get worse)
1239 [ + - ]: 129 : auto post_post_linearization = post_linearization;
1240 [ + - ]: 129 : PostLinearize(depgraph, post_post_linearization);
1241 : 129 : SanityCheck(depgraph, post_post_linearization);
1242 : 129 : auto post_post_chunking = ChunkLinearization(depgraph, post_post_linearization);
1243 [ + - ]: 129 : cmp = CompareChunks(post_post_chunking, post_chunking);
1244 [ - + ]: 129 : assert(cmp >= 0);
1245 : :
1246 : : // The chunks that come out of postlinearizing are always connected.
1247 : 129 : LinearizationChunking linchunking(depgraph, post_linearization);
1248 [ + + ]: 1282 : while (linchunking.NumChunksLeft()) {
1249 [ - + ]: 1024 : assert(depgraph.IsConnected(linchunking.GetChunk(0).transactions));
1250 : 1024 : linchunking.MarkDone(linchunking.GetChunk(0).transactions);
1251 : : }
1252 : 129 : }
1253 : :
1254 [ + - ]: 915 : FUZZ_TARGET(clusterlin_postlinearize_tree)
1255 : : {
1256 : : // Verify expected properties of PostLinearize() on linearizations of graphs that form either
1257 : : // an upright or reverse tree structure.
1258 : :
1259 : : // Construct a direction, RNG seed, and an arbitrary graph from the fuzz input.
1260 : 465 : SpanReader reader(buffer);
1261 : 465 : uint64_t rng_seed{0};
1262 : 465 : DepGraph<TestBitSet> depgraph_gen;
1263 : 465 : uint8_t direction{0};
1264 : 465 : try {
1265 [ + - + + : 465 : reader >> direction >> rng_seed >> Using<DepGraphFormatter>(depgraph_gen);
+ - ]
1266 [ - + ]: 1 : } catch (const std::ios_base::failure&) {}
1267 : :
1268 : : // Now construct a new graph, copying the nodes, but leaving only the first parent (even
1269 : : // direction) or the first child (odd direction).
1270 : 465 : DepGraph<TestBitSet> depgraph_tree;
1271 [ + + ]: 13805 : for (DepGraphIndex i = 0; i < depgraph_gen.PositionRange(); ++i) {
1272 [ + + ]: 13340 : if (depgraph_gen.Positions()[i]) {
1273 : 10767 : depgraph_tree.AddTransaction(depgraph_gen.FeeRate(i));
1274 : : } else {
1275 : : // For holes, add a dummy transaction which is deleted below, so that non-hole
1276 : : // transactions retain their position.
1277 : 2573 : depgraph_tree.AddTransaction(FeeFrac{});
1278 : : }
1279 : : }
1280 : 465 : depgraph_tree.RemoveTransactions(TestBitSet::Fill(depgraph_gen.PositionRange()) - depgraph_gen.Positions());
1281 : :
1282 [ + + ]: 465 : if (direction & 1) {
1283 [ + + ]: 7007 : for (DepGraphIndex i = 0; i < depgraph_gen.TxCount(); ++i) {
1284 : 6719 : auto children = depgraph_gen.GetReducedChildren(i);
1285 [ + + ]: 6719 : if (children.Any()) {
1286 : 4140 : depgraph_tree.AddDependencies(TestBitSet::Singleton(i), children.First());
1287 : : }
1288 : : }
1289 : : } else {
1290 [ + + ]: 4225 : for (DepGraphIndex i = 0; i < depgraph_gen.TxCount(); ++i) {
1291 : 4048 : auto parents = depgraph_gen.GetReducedParents(i);
1292 [ + + ]: 4048 : if (parents.Any()) {
1293 : 1671 : depgraph_tree.AddDependencies(TestBitSet::Singleton(parents.First()), i);
1294 : : }
1295 : : }
1296 : : }
1297 : :
1298 : : // Retrieve a linearization from the fuzz input.
1299 : 465 : std::vector<DepGraphIndex> linearization;
1300 [ + - ]: 930 : linearization = ReadLinearization(depgraph_tree, reader);
1301 : 465 : SanityCheck(depgraph_tree, linearization);
1302 : :
1303 : : // Produce a postlinearized version.
1304 [ + - ]: 465 : auto post_linearization = linearization;
1305 [ + - ]: 465 : PostLinearize(depgraph_tree, post_linearization);
1306 : 465 : SanityCheck(depgraph_tree, post_linearization);
1307 : :
1308 : : // Compare diagrams.
1309 : 465 : auto chunking = ChunkLinearization(depgraph_tree, linearization);
1310 : 465 : auto post_chunking = ChunkLinearization(depgraph_tree, post_linearization);
1311 [ + - ]: 465 : auto cmp = CompareChunks(post_chunking, chunking);
1312 [ - + ]: 465 : assert(cmp >= 0);
1313 : :
1314 : : // Verify that post-linearizing again does not change the diagram. The result must be identical
1315 : : // as post_linearization ought to be optimal already with a tree-structured graph.
1316 [ + - ]: 465 : auto post_post_linearization = post_linearization;
1317 [ + - ]: 465 : PostLinearize(depgraph_tree, post_linearization);
1318 : 465 : SanityCheck(depgraph_tree, post_linearization);
1319 : 465 : auto post_post_chunking = ChunkLinearization(depgraph_tree, post_post_linearization);
1320 [ + - ]: 465 : auto cmp_post = CompareChunks(post_post_chunking, post_chunking);
1321 [ - + ]: 465 : assert(cmp_post == 0);
1322 : :
1323 : : // Try to find an even better linearization directly. This must not change the diagram for the
1324 : : // same reason.
1325 : 465 : auto [opt_linearization, _optimal] = Linearize(depgraph_tree, 100000, rng_seed, post_linearization);
1326 : 465 : auto opt_chunking = ChunkLinearization(depgraph_tree, opt_linearization);
1327 [ + - ]: 465 : auto cmp_opt = CompareChunks(opt_chunking, post_chunking);
1328 [ - + ]: 465 : assert(cmp_opt == 0);
1329 : 465 : }
1330 : :
1331 [ + - ]: 581 : FUZZ_TARGET(clusterlin_postlinearize_moved_leaf)
1332 : : {
1333 : : // Verify that taking an existing linearization, and moving a leaf to the back, potentially
1334 : : // increasing its fee, and then post-linearizing, results in something as good as the
1335 : : // original. This guarantees that in an RBF that replaces a transaction with one of the same
1336 : : // size but higher fee, applying the "remove conflicts, append new transaction, postlinearize"
1337 : : // process will never worsen linearization quality.
1338 : :
1339 : : // Construct an arbitrary graph and a fee from the fuzz input.
1340 : 131 : SpanReader reader(buffer);
1341 : 131 : DepGraph<TestBitSet> depgraph;
1342 : 131 : int32_t fee_inc{0};
1343 : 131 : try {
1344 : 131 : uint64_t fee_inc_code;
1345 [ + - + + ]: 131 : reader >> Using<DepGraphFormatter>(depgraph) >> VARINT(fee_inc_code);
1346 : 50 : fee_inc = fee_inc_code & 0x3ffff;
1347 [ - + ]: 81 : } catch (const std::ios_base::failure&) {}
1348 [ + + ]: 131 : if (depgraph.TxCount() == 0) return;
1349 : :
1350 : : // Retrieve two linearizations from the fuzz input.
1351 [ + - ]: 123 : auto lin = ReadLinearization(depgraph, reader);
1352 [ + - ]: 123 : auto lin_leaf = ReadLinearization(depgraph, reader);
1353 : :
1354 : : // Construct a linearization identical to lin, but with the tail end of lin_leaf moved to the
1355 : : // back.
1356 : 123 : std::vector<DepGraphIndex> lin_moved;
1357 [ + + ]: 1666 : for (auto i : lin) {
1358 [ + + + - ]: 1543 : if (i != lin_leaf.back()) lin_moved.push_back(i);
1359 : : }
1360 [ + - ]: 123 : lin_moved.push_back(lin_leaf.back());
1361 : :
1362 : : // Postlinearize lin_moved.
1363 [ + - ]: 123 : PostLinearize(depgraph, lin_moved);
1364 : 123 : SanityCheck(depgraph, lin_moved);
1365 : :
1366 : : // Compare diagrams (applying the fee delta after computing the old one).
1367 : 123 : auto old_chunking = ChunkLinearization(depgraph, lin);
1368 : 123 : depgraph.FeeRate(lin_leaf.back()).fee += fee_inc;
1369 : 123 : auto new_chunking = ChunkLinearization(depgraph, lin_moved);
1370 [ + - ]: 123 : auto cmp = CompareChunks(new_chunking, old_chunking);
1371 [ - + ]: 123 : assert(cmp >= 0);
1372 : 131 : }
1373 : :
1374 [ + - ]: 669 : FUZZ_TARGET(clusterlin_merge)
1375 : : {
1376 : : // Construct an arbitrary graph from the fuzz input.
1377 : 219 : SpanReader reader(buffer);
1378 : 219 : DepGraph<TestBitSet> depgraph;
1379 : 219 : try {
1380 [ + - ]: 219 : reader >> Using<DepGraphFormatter>(depgraph);
1381 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
1382 : :
1383 : : // Retrieve two linearizations from the fuzz input.
1384 [ + - ]: 219 : auto lin1 = ReadLinearization(depgraph, reader);
1385 [ + - ]: 219 : auto lin2 = ReadLinearization(depgraph, reader);
1386 : :
1387 : : // Merge the two.
1388 [ + - ]: 219 : auto lin_merged = MergeLinearizations(depgraph, lin1, lin2);
1389 : :
1390 : : // Compute chunkings and compare.
1391 : 219 : auto chunking1 = ChunkLinearization(depgraph, lin1);
1392 : 219 : auto chunking2 = ChunkLinearization(depgraph, lin2);
1393 : 219 : auto chunking_merged = ChunkLinearization(depgraph, lin_merged);
1394 [ + - ]: 219 : auto cmp1 = CompareChunks(chunking_merged, chunking1);
1395 [ - + ]: 219 : assert(cmp1 >= 0);
1396 [ + - ]: 219 : auto cmp2 = CompareChunks(chunking_merged, chunking2);
1397 [ - + ]: 219 : assert(cmp2 >= 0);
1398 : 219 : }
1399 : :
1400 [ + - ]: 671 : FUZZ_TARGET(clusterlin_fix_linearization)
1401 : : {
1402 : : // Verify expected properties of FixLinearization() on arbitrary linearizations.
1403 : :
1404 : : // Retrieve a depgraph from the fuzz input.
1405 : 221 : SpanReader reader(buffer);
1406 : 221 : DepGraph<TestBitSet> depgraph;
1407 : 221 : try {
1408 [ + - ]: 221 : reader >> Using<DepGraphFormatter>(depgraph);
1409 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
1410 : :
1411 : : // Construct an arbitrary linearization (not necessarily topological for depgraph).
1412 : 221 : std::vector<DepGraphIndex> linearization;
1413 : : /** Which transactions of depgraph are yet to be included in linearization. */
1414 : 221 : TestBitSet todo = depgraph.Positions();
1415 [ + + ]: 2419 : while (todo.Any()) {
1416 : : // Read a number from the fuzz input in range [0, todo.Count()).
1417 : 1977 : uint64_t val{0};
1418 : 1977 : try {
1419 [ + + ]: 1977 : reader >> VARINT(val);
1420 [ - + ]: 1708 : } catch (const std::ios_base::failure&) {}
1421 [ + - ]: 1977 : val %= todo.Count();
1422 : : // Find the val'th element in todo, remove it from todo, and append it to linearization.
1423 [ + - + - ]: 4767 : for (auto idx : todo) {
1424 [ + + ]: 2790 : if (val == 0) {
1425 [ + - ]: 1977 : linearization.push_back(idx);
1426 : 1977 : todo.Reset(idx);
1427 : 1977 : break;
1428 : : }
1429 : 813 : --val;
1430 : : }
1431 : : }
1432 [ - + ]: 221 : assert(linearization.size() == depgraph.TxCount());
1433 : :
1434 : : // Determine what prefix of linearization is topological, i.e., the position of the first entry
1435 : : // in linearization which corresponds to a transaction that is not preceded by all its
1436 : : // ancestors.
1437 : 221 : size_t topo_prefix = 0;
1438 : 221 : todo = depgraph.Positions();
1439 [ + + ]: 1304 : while (topo_prefix < linearization.size()) {
1440 : 1160 : DepGraphIndex idx = linearization[topo_prefix];
1441 : 1160 : todo.Reset(idx);
1442 [ + + ]: 1160 : if (todo.Overlaps(depgraph.Ancestors(idx))) break;
1443 : 1083 : ++topo_prefix;
1444 : : }
1445 : :
1446 : : // Then make a fixed copy of linearization.
1447 [ + - ]: 221 : auto linearization_fixed = linearization;
1448 : 221 : FixLinearization(depgraph, linearization_fixed);
1449 : : // Sanity check it (which includes testing whether it is topological).
1450 : 221 : SanityCheck(depgraph, linearization_fixed);
1451 : :
1452 : : // FixLinearization does not modify the topological prefix of linearization.
1453 [ - + ]: 221 : assert(std::equal(linearization.begin(), linearization.begin() + topo_prefix,
1454 : : linearization_fixed.begin()));
1455 : : // This also means that if linearization was entirely topological, FixLinearization cannot have
1456 : : // modified it. This is implied by the assertion above already, but repeat it explicitly.
1457 [ + + ]: 221 : if (topo_prefix == linearization.size()) {
1458 [ - + ]: 144 : assert(linearization == linearization_fixed);
1459 : : }
1460 : 221 : }
|
