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 <serialize.h>
7 : : #include <streams.h>
8 : : #include <test/fuzz/fuzz.h>
9 : : #include <test/fuzz/FuzzedDataProvider.h>
10 : : #include <test/util/cluster_linearize.h>
11 : : #include <util/bitset.h>
12 : : #include <util/feefrac.h>
13 : :
14 : : #include <algorithm>
15 : : #include <stdint.h>
16 : : #include <vector>
17 : : #include <utility>
18 : :
19 : : using namespace cluster_linearize;
20 : :
21 : : namespace {
22 : :
23 : : /** A simple finder class for candidate sets.
24 : : *
25 : : * This class matches SearchCandidateFinder in interface and behavior, though with fewer
26 : : * optimizations.
27 : : */
28 : : template<typename SetType>
29 : : class SimpleCandidateFinder
30 : : {
31 : : /** Internal dependency graph. */
32 : : const DepGraph<SetType>& m_depgraph;
33 : : /** Which transaction are left to include. */
34 : : SetType m_todo;
35 : :
36 : : public:
37 : : /** Construct an SimpleCandidateFinder for a given graph. */
38 : 319 : SimpleCandidateFinder(const DepGraph<SetType>& depgraph LIFETIMEBOUND) noexcept :
39 : 319 : m_depgraph(depgraph), m_todo{SetType::Fill(depgraph.TxCount())} {}
40 : :
41 : : /** Remove a set of transactions from the set of to-be-linearized ones. */
42 : 2332 : void MarkDone(SetType select) noexcept { m_todo -= select; }
43 : :
44 : : /** Determine whether unlinearized transactions remain. */
45 : 1614 : bool AllDone() const noexcept { return m_todo.None(); }
46 : :
47 : : /** Find a candidate set using at most max_iterations iterations, and the number of iterations
48 : : * actually performed. If that number is less than max_iterations, then the result is optimal.
49 : : *
50 : : * Complexity: O(N * M), where M is the number of connected topological subsets of the cluster.
51 : : * That number is bounded by M <= 2^(N-1).
52 : : */
53 : 1421 : std::pair<SetInfo<SetType>, uint64_t> FindCandidateSet(uint64_t max_iterations) const noexcept
54 : : {
55 : 1421 : uint64_t iterations_left = max_iterations;
56 : : // Queue of work units. Each consists of:
57 : : // - inc: set of transactions definitely included
58 : : // - und: set of transactions that can be added to inc still
59 : 1421 : std::vector<std::pair<SetType, SetType>> queue;
60 : : // Initially we have just one queue element, with the entire graph in und.
61 [ + - ]: 1421 : queue.emplace_back(SetType{}, m_todo);
62 : : // Best solution so far.
63 : 1421 : SetInfo best(m_depgraph, m_todo);
64 : : // Process the queue.
65 [ + + + + ]: 3769100 : while (!queue.empty() && iterations_left) {
66 : 3767679 : --iterations_left;
67 : : // Pop top element of the queue.
68 : 14878768 : auto [inc, und] = queue.back();
69 : 3767679 : queue.pop_back();
70 : : // Look for a transaction to consider adding/removing.
71 : 7535358 : bool inc_none = inc.None();
72 [ + + ]: 11102915 : for (auto split : und) {
73 : : // If inc is empty, consider any split transaction. Otherwise only consider
74 : : // transactions that share ancestry with inc so far (which means only connected
75 : : // sets will be considered).
76 [ + + + + ]: 3567557 : if (inc_none || inc.Overlaps(m_depgraph.Ancestors(split))) {
77 : : // Add a queue entry with split included.
78 : 3766338 : SetInfo new_inc(m_depgraph, inc | (m_todo & m_depgraph.Ancestors(split)));
79 [ + - + - ]: 3766338 : queue.emplace_back(new_inc.transactions, und - new_inc.transactions);
80 : : // Add a queue entry with split excluded.
81 [ + - + - ]: 3766338 : queue.emplace_back(inc, und - m_depgraph.Descendants(split));
82 : : // Update statistics to account for the candidate new_inc.
83 [ + + ]: 1883169 : if (new_inc.feerate > best.feerate) best = new_inc;
84 : : break;
85 : 1883169 : }
86 [ + + ]: 3567557 : }
87 : 3767679 : }
88 : 1421 : return {std::move(best), max_iterations - iterations_left};
89 : 1421 : }
90 : : };
91 : :
92 : : /** A very simple finder class for optimal candidate sets, which tries every subset.
93 : : *
94 : : * It is even simpler than SimpleCandidateFinder, and is primarily included here to test the
95 : : * correctness of SimpleCandidateFinder, which is then used to test the correctness of
96 : : * SearchCandidateFinder.
97 : : */
98 : : template<typename SetType>
99 : : class ExhaustiveCandidateFinder
100 : : {
101 : : /** Internal dependency graph. */
102 : : const DepGraph<SetType>& m_depgraph;
103 : : /** Which transaction are left to include. */
104 : : SetType m_todo;
105 : :
106 : : public:
107 : : /** Construct an ExhaustiveCandidateFinder for a given graph. */
108 : 174 : ExhaustiveCandidateFinder(const DepGraph<SetType>& depgraph LIFETIMEBOUND) noexcept :
109 : 174 : m_depgraph(depgraph), m_todo{SetType::Fill(depgraph.TxCount())} {}
110 : :
111 : : /** Remove a set of transactions from the set of to-be-linearized ones. */
112 : 1440 : void MarkDone(SetType select) noexcept { m_todo -= select; }
113 : :
114 : : /** Determine whether unlinearized transactions remain. */
115 : 1614 : bool AllDone() const noexcept { return m_todo.None(); }
116 : :
117 : : /** Find the optimal remaining candidate set.
118 : : *
119 : : * Complexity: O(N * 2^N).
120 : : */
121 : 306 : SetInfo<SetType> FindCandidateSet() const noexcept
122 : : {
123 : : // Best solution so far.
124 : 306 : SetInfo<SetType> best{m_todo, m_depgraph.FeeRate(m_todo)};
125 : : // The number of combinations to try.
126 : 306 : uint64_t limit = (uint64_t{1} << m_todo.Count()) - 1;
127 : : // Try the transitive closure of every non-empty subset of m_todo.
128 [ + + ]: 165538 : for (uint64_t x = 1; x < limit; ++x) {
129 : : // If bit number b is set in x, then the remaining ancestors of the b'th remaining
130 : : // transaction in m_todo are included.
131 : 165232 : SetType txn;
132 : 165232 : auto x_shifted{x};
133 [ + + ]: 1942432 : for (auto i : m_todo) {
134 [ + + ]: 1777200 : if (x_shifted & 1) txn |= m_depgraph.Ancestors(i);
135 : 1777200 : x_shifted >>= 1;
136 : 1777200 : }
137 : 165232 : SetInfo cur(m_depgraph, txn & m_todo);
138 [ + + ]: 165232 : if (cur.feerate > best.feerate) best = cur;
139 : 165232 : }
140 : : return best;
141 : 306 : }
142 : : };
143 : :
144 : : /** A simple linearization algorithm.
145 : : *
146 : : * This matches Linearize() in interface and behavior, though with fewer optimizations, lacking
147 : : * the ability to pass in an existing linearization, and using just SimpleCandidateFinder rather
148 : : * than AncestorCandidateFinder and SearchCandidateFinder.
149 : : */
150 : : template<typename SetType>
151 : 145 : std::pair<std::vector<ClusterIndex>, bool> SimpleLinearize(const DepGraph<SetType>& depgraph, uint64_t max_iterations)
152 : : {
153 : 145 : std::vector<ClusterIndex> linearization;
154 : 145 : SimpleCandidateFinder finder(depgraph);
155 : 145 : SetType todo = SetType::Fill(depgraph.TxCount());
156 : 145 : bool optimal = true;
157 [ + + ]: 1037 : while (todo.Any()) {
158 : 924 : auto [candidate, iterations_done] = finder.FindCandidateSet(max_iterations);
159 [ + + ]: 892 : if (iterations_done == max_iterations) optimal = false;
160 : 1784 : depgraph.AppendTopo(linearization, candidate.transactions);
161 : 892 : todo -= candidate.transactions;
162 : 892 : finder.MarkDone(candidate.transactions);
163 : 892 : max_iterations -= iterations_done;
164 : 892 : }
165 : 145 : return {std::move(linearization), optimal};
166 : 145 : }
167 : :
168 : : /** Given a dependency graph, and a todo set, read a topological subset of todo from reader. */
169 : : template<typename SetType>
170 : 5156 : SetType ReadTopologicalSet(const DepGraph<SetType>& depgraph, const SetType& todo, SpanReader& reader)
171 : : {
172 : 5156 : uint64_t mask{0};
173 : : try {
174 [ + - + + ]: 5156 : reader >> VARINT(mask);
175 [ + - ]: 5156 : } catch(const std::ios_base::failure&) {}
176 : 5156 : SetType ret;
177 [ + + ]: 71827 : for (auto i : todo) {
178 [ + + ]: 66671 : if (!ret[i]) {
179 [ + + ]: 65696 : if (mask & 1) ret |= depgraph.Ancestors(i);
180 : 65696 : mask >>= 1;
181 : 65696 : }
182 : 66671 : }
183 : 5156 : return ret & todo;
184 : 8040 : }
185 : :
186 : : /** Given a dependency graph, construct any valid linearization for it, reading from a SpanReader. */
187 : : template<typename BS>
188 : 1108 : std::vector<ClusterIndex> ReadLinearization(const DepGraph<BS>& depgraph, SpanReader& reader)
189 : : {
190 : 1108 : std::vector<ClusterIndex> linearization;
191 : 1108 : TestBitSet todo = TestBitSet::Fill(depgraph.TxCount());
192 : : // In every iteration one topologically-valid transaction is appended to linearization.
193 [ + + ]: 20604 : while (todo.Any()) {
194 : : // Compute the set of transactions with no not-yet-included ancestors.
195 : 19496 : TestBitSet potential_next;
196 [ + + ]: 282675 : for (auto j : todo) {
197 [ + + ]: 263179 : if ((depgraph.Ancestors(j) & todo) == TestBitSet::Singleton(j)) {
198 : 155302 : potential_next.Set(j);
199 : 155302 : }
200 : 263179 : }
201 : : // There must always be one (otherwise there is a cycle in the graph).
202 [ + - ]: 19496 : assert(potential_next.Any());
203 : : // Read a number from reader, and interpret it as index into potential_next.
204 : 19496 : uint64_t idx{0};
205 : : try {
206 [ + - + + ]: 19496 : reader >> VARINT(idx);
207 [ - + - + ]: 19496 : } catch (const std::ios_base::failure&) {}
208 : 19496 : idx %= potential_next.Count();
209 : : // Find out which transaction that corresponds to.
210 [ + - ]: 54216 : for (auto j : potential_next) {
211 [ + + ]: 34720 : if (idx == 0) {
212 : : // When found, add it to linearization and remove it from todo.
213 [ + - ]: 19496 : linearization.push_back(j);
214 [ - + ]: 19496 : assert(todo[j]);
215 : 19496 : todo.Reset(j);
216 : 19496 : break;
217 : : }
218 : 15224 : --idx;
219 [ + + ]: 34720 : }
220 : 19496 : }
221 : 1108 : return linearization;
222 [ + - ]: 16140 : }
223 : :
224 : : } // namespace
225 : :
226 [ + - + - ]: 157 : FUZZ_TARGET(clusterlin_add_dependency)
227 : : {
228 : : // Verify that computing a DepGraph from a cluster, or building it step by step using AddDependency
229 : : // have the same effect.
230 : :
231 : : // Construct a cluster of a certain length, with no dependencies.
232 : 154 : FuzzedDataProvider provider(buffer.data(), buffer.size());
233 : 154 : auto num_tx = provider.ConsumeIntegralInRange<ClusterIndex>(2, 32);
234 [ + - ]: 154 : Cluster<TestBitSet> cluster(num_tx, std::pair{FeeFrac{0, 1}, TestBitSet{}});
235 : : // Construct the corresponding DepGraph object (also no dependencies).
236 : 154 : DepGraph depgraph(cluster);
237 [ + - ]: 154 : SanityCheck(depgraph);
238 : : // Read (parent, child) pairs, and add them to the cluster and depgraph.
239 [ + - + + : 5203 : LIMITED_WHILE(provider.remaining_bytes() > 0, TestBitSet::Size() * TestBitSet::Size()) {
+ + ]
240 [ - + ]: 5049 : auto parent = provider.ConsumeIntegralInRange<ClusterIndex>(0, num_tx - 1);
241 [ - + ]: 5049 : auto child = provider.ConsumeIntegralInRange<ClusterIndex>(0, num_tx - 2);
242 : 5049 : child += (child >= parent);
243 : 5049 : cluster[child].second.Set(parent);
244 : 5049 : depgraph.AddDependency(parent, child);
245 [ - + ]: 5049 : assert(depgraph.Ancestors(child)[parent]);
246 [ + - ]: 5049 : assert(depgraph.Descendants(parent)[child]);
247 : 5049 : }
248 : : // Sanity check the result.
249 [ + - ]: 154 : SanityCheck(depgraph);
250 : : // Verify that the resulting DepGraph matches one recomputed from the cluster.
251 [ + - ]: 154 : assert(DepGraph(cluster) == depgraph);
252 : 154 : }
253 : :
254 [ + - + - ]: 135 : FUZZ_TARGET(clusterlin_cluster_serialization)
255 : : {
256 : : // Verify that any graph of transactions has its ancestry correctly computed by DepGraph, and
257 : : // if it is a DAG, that it can be serialized as a DepGraph in a way that roundtrips. This
258 : : // guarantees that any acyclic cluster has a corresponding DepGraph serialization.
259 : :
260 : 132 : FuzzedDataProvider provider(buffer.data(), buffer.size());
261 : :
262 : : // Construct a cluster in a naive way (using a FuzzedDataProvider-based serialization).
263 : 132 : Cluster<TestBitSet> cluster;
264 [ + - ]: 132 : auto num_tx = provider.ConsumeIntegralInRange<ClusterIndex>(1, 32);
265 [ + - ]: 132 : cluster.resize(num_tx);
266 [ + + ]: 2878 : for (ClusterIndex i = 0; i < num_tx; ++i) {
267 [ + - ]: 2746 : cluster[i].first.size = provider.ConsumeIntegralInRange<int32_t>(1, 0x3fffff);
268 [ + - ]: 2746 : cluster[i].first.fee = provider.ConsumeIntegralInRange<int64_t>(-0x8000000000000, 0x7ffffffffffff);
269 [ + + ]: 78188 : for (ClusterIndex j = 0; j < num_tx; ++j) {
270 [ + + ]: 75442 : if (i == j) continue;
271 [ - + + + ]: 72696 : if (provider.ConsumeBool()) cluster[i].second.Set(j);
272 : 72696 : }
273 : 2746 : }
274 : :
275 : : // Construct dependency graph, and verify it matches the cluster (which includes a round-trip
276 : : // check for the serialization).
277 : 132 : DepGraph depgraph(cluster);
278 [ + - ]: 132 : VerifyDepGraphFromCluster(cluster, depgraph);
279 : 132 : }
280 : :
281 [ + - + - ]: 141 : FUZZ_TARGET(clusterlin_depgraph_serialization)
282 : : {
283 : : // Verify that any deserialized depgraph is acyclic and roundtrips to an identical depgraph.
284 : :
285 : : // Construct a graph by deserializing.
286 : 138 : SpanReader reader(buffer);
287 : 138 : DepGraph<TestBitSet> depgraph;
288 : : try {
289 [ + - + - ]: 138 : reader >> Using<DepGraphFormatter>(depgraph);
290 [ # # # # ]: 138 : } catch (const std::ios_base::failure&) {}
291 [ + - ]: 138 : SanityCheck(depgraph);
292 : :
293 : : // Verify the graph is a DAG.
294 [ + - ]: 138 : assert(IsAcyclic(depgraph));
295 : 138 : }
296 : :
297 [ + - + - ]: 87 : FUZZ_TARGET(clusterlin_components)
298 : : {
299 : : // Verify the behavior of DepGraphs's FindConnectedComponent and IsConnected functions.
300 : :
301 : : // Construct a depgraph.
302 : 84 : SpanReader reader(buffer);
303 : 84 : DepGraph<TestBitSet> depgraph;
304 : : try {
305 [ + - + - ]: 84 : reader >> Using<DepGraphFormatter>(depgraph);
306 [ # # # # ]: 84 : } catch (const std::ios_base::failure&) {}
307 : :
308 : 84 : TestBitSet todo = TestBitSet::Fill(depgraph.TxCount());
309 [ + + ]: 1046 : while (todo.Any()) {
310 : : // Find a connected component inside todo.
311 : 962 : auto component = depgraph.FindConnectedComponent(todo);
312 : :
313 : : // The component must be a subset of todo and non-empty.
314 [ + - ]: 962 : assert(component.IsSubsetOf(todo));
315 [ + - ]: 962 : assert(component.Any());
316 : :
317 : : // If todo is the entire graph, and the entire graph is connected, then the component must
318 : : // be the entire graph.
319 [ + + ]: 962 : if (todo == TestBitSet::Fill(depgraph.TxCount())) {
320 [ - + ]: 77 : assert((component == todo) == depgraph.IsConnected());
321 : 77 : }
322 : :
323 : : // If subset is connected, then component must match subset.
324 [ - + ]: 962 : assert((component == todo) == depgraph.IsConnected(todo));
325 : :
326 : : // The component cannot have any ancestors or descendants outside of component but in todo.
327 [ + + ]: 8335 : for (auto i : component) {
328 [ + - ]: 7373 : assert((depgraph.Ancestors(i) & todo).IsSubsetOf(component));
329 [ + - ]: 7373 : assert((depgraph.Descendants(i) & todo).IsSubsetOf(component));
330 : 7373 : }
331 : :
332 : : // Starting from any component element, we must be able to reach every element.
333 [ + + ]: 8335 : for (auto i : component) {
334 : : // Start with just i as reachable.
335 : 7373 : TestBitSet reachable = TestBitSet::Singleton(i);
336 : : // Add in-todo descendants and ancestors to reachable until it does not change anymore.
337 : 27769 : while (true) {
338 : 27769 : TestBitSet new_reachable = reachable;
339 [ + + ]: 311271 : for (auto j : new_reachable) {
340 : 283502 : new_reachable |= depgraph.Ancestors(j) & todo;
341 : 283502 : new_reachable |= depgraph.Descendants(j) & todo;
342 : 283502 : }
343 [ + + ]: 27769 : if (new_reachable == reachable) break;
344 : 20396 : reachable = new_reachable;
345 [ - + + ]: 27769 : }
346 : : // Verify that the result is the entire component.
347 [ + - ]: 7373 : assert(component == reachable);
348 : 7373 : }
349 : :
350 : : // Construct an arbitrary subset of todo.
351 : 962 : uint64_t subset_bits{0};
352 : : try {
353 [ + - + + ]: 962 : reader >> VARINT(subset_bits);
354 [ - + - + ]: 962 : } catch (const std::ios_base::failure&) {}
355 : 962 : TestBitSet subset;
356 [ + + ]: 23499 : for (ClusterIndex i = 0; i < depgraph.TxCount(); ++i) {
357 [ + + ]: 22537 : if (todo[i]) {
358 [ + + ]: 11578 : if (subset_bits & 1) subset.Set(i);
359 : 11578 : subset_bits >>= 1;
360 : 11578 : }
361 : 22537 : }
362 : : // Which must be non-empty.
363 [ + + ]: 962 : if (subset.None()) subset = TestBitSet::Singleton(todo.First());
364 : : // Remove it from todo.
365 : 962 : todo -= subset;
366 : 962 : }
367 : :
368 : : // No components can be found in an empty subset.
369 [ + - ]: 84 : assert(depgraph.FindConnectedComponent(todo).None());
370 : 919 : }
371 : :
372 [ + - + - ]: 80 : FUZZ_TARGET(clusterlin_chunking)
373 : : {
374 : : // Verify the correctness of the ChunkLinearization function.
375 : :
376 : : // Construct a graph by deserializing.
377 : 77 : SpanReader reader(buffer);
378 : 77 : DepGraph<TestBitSet> depgraph;
379 : : try {
380 [ + - + - ]: 77 : reader >> Using<DepGraphFormatter>(depgraph);
381 [ # # # # ]: 77 : } catch (const std::ios_base::failure&) {}
382 : :
383 : : // Read a valid linearization for depgraph.
384 [ + - ]: 77 : auto linearization = ReadLinearization(depgraph, reader);
385 : :
386 : : // Invoke the chunking function.
387 [ + - ]: 77 : auto chunking = ChunkLinearization(depgraph, linearization);
388 : :
389 : : // Verify that chunk feerates are monotonically non-increasing.
390 [ + + ]: 339 : for (size_t i = 1; i < chunking.size(); ++i) {
391 [ + - ]: 262 : assert(!(chunking[i] >> chunking[i - 1]));
392 : 262 : }
393 : :
394 : : // Naively recompute the chunks (each is the highest-feerate prefix of what remains).
395 : 77 : auto todo = TestBitSet::Fill(depgraph.TxCount());
396 [ + + ]: 406 : for (const auto& chunk_feerate : chunking) {
397 [ + - ]: 329 : assert(todo.Any());
398 : 329 : SetInfo<TestBitSet> accumulator, best;
399 [ + + ]: 8099 : for (ClusterIndex idx : linearization) {
400 [ + + ]: 7770 : if (todo[idx]) {
401 : 4152 : accumulator |= SetInfo(depgraph, idx);
402 [ + + + + ]: 4152 : if (best.feerate.IsEmpty() || accumulator.feerate >> best.feerate) {
403 : 754 : best = accumulator;
404 : 754 : }
405 : 4152 : }
406 : 7770 : }
407 [ - + ]: 329 : assert(chunk_feerate == best.feerate);
408 [ - + ]: 329 : assert(best.transactions.IsSubsetOf(todo));
409 : 329 : todo -= best.transactions;
410 : 329 : }
411 [ + - ]: 77 : assert(todo.None());
412 : 77 : }
413 : :
414 [ + - + - ]: 99 : FUZZ_TARGET(clusterlin_ancestor_finder)
415 : : {
416 : : // Verify that AncestorCandidateFinder works as expected.
417 : :
418 : : // Retrieve a depgraph from the fuzz input.
419 : 96 : SpanReader reader(buffer);
420 : 96 : DepGraph<TestBitSet> depgraph;
421 : : try {
422 [ + - + - ]: 96 : reader >> Using<DepGraphFormatter>(depgraph);
423 [ # # # # ]: 96 : } catch (const std::ios_base::failure&) {}
424 : :
425 : 96 : AncestorCandidateFinder anc_finder(depgraph);
426 : 96 : auto todo = TestBitSet::Fill(depgraph.TxCount());
427 [ + + ]: 978 : while (todo.Any()) {
428 : : // Call the ancestor finder's FindCandidateSet for what remains of the graph.
429 [ - + ]: 882 : assert(!anc_finder.AllDone());
430 : 882 : auto best_anc = anc_finder.FindCandidateSet();
431 : : // Sanity check the result.
432 [ - + ]: 882 : assert(best_anc.transactions.Any());
433 [ - + ]: 882 : assert(best_anc.transactions.IsSubsetOf(todo));
434 [ - + ]: 882 : assert(depgraph.FeeRate(best_anc.transactions) == best_anc.feerate);
435 [ - + ]: 882 : assert(depgraph.IsConnected(best_anc.transactions));
436 : : // Check that it is topologically valid.
437 [ + + ]: 2506 : for (auto i : best_anc.transactions) {
438 [ + - ]: 1624 : assert((depgraph.Ancestors(i) & todo).IsSubsetOf(best_anc.transactions));
439 : 1624 : }
440 : :
441 : : // Compute all remaining ancestor sets.
442 : 882 : std::optional<SetInfo<TestBitSet>> real_best_anc;
443 [ + + ]: 12075 : for (auto i : todo) {
444 : 11193 : SetInfo info(depgraph, todo & depgraph.Ancestors(i));
445 [ + + + + ]: 11193 : if (!real_best_anc.has_value() || info.feerate > real_best_anc->feerate) {
446 : 2072 : real_best_anc = info;
447 : 2072 : }
448 : 11193 : }
449 : : // The set returned by anc_finder must equal the real best ancestor sets.
450 [ - + ]: 882 : assert(real_best_anc.has_value());
451 [ - + ]: 882 : assert(*real_best_anc == best_anc);
452 : :
453 : : // Find a topologically valid subset of transactions to remove from the graph.
454 [ - + ]: 882 : auto del_set = ReadTopologicalSet(depgraph, todo, reader);
455 : : // If we did not find anything, use best_anc itself, because we should remove something.
456 [ + + ]: 882 : if (del_set.None()) del_set = best_anc.transactions;
457 : 882 : todo -= del_set;
458 : 882 : anc_finder.MarkDone(del_set);
459 : 882 : }
460 [ + - ]: 96 : assert(anc_finder.AllDone());
461 : 96 : }
462 : :
463 : : static constexpr auto MAX_SIMPLE_ITERATIONS = 300000;
464 : :
465 [ + - + - ]: 177 : FUZZ_TARGET(clusterlin_search_finder)
466 : : {
467 : : // Verify that SearchCandidateFinder works as expected by sanity checking the results
468 : : // and comparing with the results from SimpleCandidateFinder, ExhaustiveCandidateFinder, and
469 : : // AncestorCandidateFinder.
470 : :
471 : : // Retrieve an RNG seed and a depgraph from the fuzz input.
472 : 174 : SpanReader reader(buffer);
473 : 174 : DepGraph<TestBitSet> depgraph;
474 : 174 : uint64_t rng_seed{0};
475 : : try {
476 [ + - + - : 174 : reader >> Using<DepGraphFormatter>(depgraph) >> rng_seed;
+ + ]
477 [ - + + - ]: 174 : } catch (const std::ios_base::failure&) {}
478 : :
479 : : // Instantiate ALL the candidate finders.
480 : 174 : SearchCandidateFinder src_finder(depgraph, rng_seed);
481 : 174 : SimpleCandidateFinder smp_finder(depgraph);
482 : 174 : ExhaustiveCandidateFinder exh_finder(depgraph);
483 : 174 : AncestorCandidateFinder anc_finder(depgraph);
484 : :
485 : 174 : auto todo = TestBitSet::Fill(depgraph.TxCount());
486 [ + + ]: 1614 : while (todo.Any()) {
487 [ + - ]: 1440 : assert(!src_finder.AllDone());
488 [ - + ]: 1440 : assert(!smp_finder.AllDone());
489 [ - + ]: 1440 : assert(!exh_finder.AllDone());
490 [ - + ]: 1440 : assert(!anc_finder.AllDone());
491 : :
492 : : // For each iteration, read an iteration count limit from the fuzz input.
493 : 1440 : uint64_t max_iterations = 1;
494 : : try {
495 [ + - + + ]: 1440 : reader >> VARINT(max_iterations);
496 [ - + + - ]: 1440 : } catch (const std::ios_base::failure&) {}
497 : 1440 : max_iterations &= 0xfffff;
498 : :
499 : : // Read an initial subset from the fuzz input.
500 [ - + ]: 1440 : SetInfo init_best(depgraph, ReadTopologicalSet(depgraph, todo, reader));
501 : :
502 : : // Call the search finder's FindCandidateSet for what remains of the graph.
503 : 18159 : auto [found, iterations_done] = src_finder.FindCandidateSet(max_iterations, init_best);
504 : :
505 : : // Sanity check the result.
506 [ - + ]: 1440 : assert(iterations_done <= max_iterations);
507 [ - + ]: 1440 : assert(found.transactions.Any());
508 [ - + ]: 1440 : assert(found.transactions.IsSubsetOf(todo));
509 [ - + - + : 4320 : assert(depgraph.FeeRate(found.transactions) == found.feerate);
- + ]
510 [ + + - + ]: 1440 : if (!init_best.feerate.IsEmpty()) assert(found.feerate >= init_best.feerate);
511 : : // Check that it is topologically valid.
512 [ + + ]: 6122 : for (auto i : found.transactions) {
513 [ + - ]: 3242 : assert(found.transactions.IsSupersetOf(depgraph.Ancestors(i) & todo));
514 : 3242 : }
515 : :
516 : : // At most 2^N-1 iterations can be required: the number of non-empty subsets a graph with N
517 : : // transactions has.
518 [ - + ]: 1440 : assert(iterations_done <= ((uint64_t{1} << todo.Count()) - 1));
519 : :
520 : : // Perform quality checks only if SearchCandidateFinder claims an optimal result.
521 [ + + ]: 1440 : if (iterations_done < max_iterations) {
522 : : // Optimal sets are always connected.
523 [ + - ]: 529 : assert(depgraph.IsConnected(found.transactions));
524 : :
525 : : // Compare with SimpleCandidateFinder.
526 : 2199 : auto [simple, simple_iters] = smp_finder.FindCandidateSet(MAX_SIMPLE_ITERATIONS);
527 [ + - + - ]: 1058 : assert(found.feerate >= simple.feerate);
528 [ + + ]: 529 : if (simple_iters < MAX_SIMPLE_ITERATIONS) {
529 [ + - + - ]: 1050 : assert(found.feerate == simple.feerate);
530 : 525 : }
531 : :
532 : : // Compare with AncestorCandidateFinder;
533 : 529 : auto anc = anc_finder.FindCandidateSet();
534 [ + - ]: 529 : assert(found.feerate >= anc.feerate);
535 : :
536 : : // Compare with ExhaustiveCandidateFinder. This quickly gets computationally expensive
537 : : // for large clusters (O(2^n)), so only do it for sufficiently small ones.
538 [ + + ]: 529 : if (todo.Count() <= 12) {
539 : 306 : auto exhaustive = exh_finder.FindCandidateSet();
540 [ - + - + ]: 612 : assert(exhaustive.feerate == found.feerate);
541 : : // Also compare ExhaustiveCandidateFinder with SimpleCandidateFinder (this is
542 : : // primarily a test for SimpleCandidateFinder's correctness).
543 [ - + - + ]: 612 : assert(exhaustive.feerate >= simple.feerate);
544 [ - + ]: 306 : if (simple_iters < MAX_SIMPLE_ITERATIONS) {
545 [ + - + - ]: 612 : assert(exhaustive.feerate == simple.feerate);
546 : 306 : }
547 : 306 : }
548 : 529 : }
549 : :
550 : : // Find a topologically valid subset of transactions to remove from the graph.
551 [ + - ]: 1440 : auto del_set = ReadTopologicalSet(depgraph, todo, reader);
552 : : // If we did not find anything, use found itself, because we should remove something.
553 [ + + ]: 1440 : if (del_set.None()) del_set = found.transactions;
554 : 1440 : todo -= del_set;
555 : 1440 : src_finder.MarkDone(del_set);
556 : 1440 : smp_finder.MarkDone(del_set);
557 : 1440 : exh_finder.MarkDone(del_set);
558 : 1440 : anc_finder.MarkDone(del_set);
559 : 1440 : }
560 : :
561 [ + - ]: 174 : assert(src_finder.AllDone());
562 [ + - ]: 174 : assert(smp_finder.AllDone());
563 [ + - ]: 174 : assert(exh_finder.AllDone());
564 [ + - ]: 174 : assert(anc_finder.AllDone());
565 : 704 : }
566 : :
567 [ + - + - ]: 126 : FUZZ_TARGET(clusterlin_linearization_chunking)
568 : : {
569 : : // Verify the behavior of LinearizationChunking.
570 : :
571 : : // Retrieve a depgraph from the fuzz input.
572 : 123 : SpanReader reader(buffer);
573 : 123 : DepGraph<TestBitSet> depgraph;
574 : : try {
575 [ + - + - ]: 123 : reader >> Using<DepGraphFormatter>(depgraph);
576 [ # # # # ]: 123 : } catch (const std::ios_base::failure&) {}
577 : :
578 : : // Retrieve a topologically-valid subset of depgraph.
579 : 123 : auto todo = TestBitSet::Fill(depgraph.TxCount());
580 [ + - ]: 123 : auto subset = SetInfo(depgraph, ReadTopologicalSet(depgraph, todo, reader));
581 : :
582 : : // Retrieve a valid linearization for depgraph.
583 [ + - ]: 123 : auto linearization = ReadLinearization(depgraph, reader);
584 : :
585 : : // Construct a LinearizationChunking object, initially for the whole linearization.
586 [ + - ]: 123 : LinearizationChunking chunking(depgraph, linearization);
587 : :
588 : : // Incrementally remove transactions from the chunking object, and check various properties at
589 : : // every step.
590 [ + + ]: 1394 : while (todo.Any()) {
591 [ - + ]: 1271 : assert(chunking.NumChunksLeft() > 0);
592 : :
593 : : // Construct linearization with just todo.
594 : 1271 : std::vector<ClusterIndex> linearization_left;
595 [ + + ]: 31870 : for (auto i : linearization) {
596 [ + + + - ]: 30599 : if (todo[i]) linearization_left.push_back(i);
597 : 30599 : }
598 : :
599 : : // Compute the chunking for linearization_left.
600 [ - + ]: 1271 : auto chunking_left = ChunkLinearization(depgraph, linearization_left);
601 : :
602 : : // Verify that it matches the feerates of the chunks of chunking.
603 [ + - ]: 1271 : assert(chunking.NumChunksLeft() == chunking_left.size());
604 [ + + ]: 7485 : for (ClusterIndex i = 0; i < chunking.NumChunksLeft(); ++i) {
605 [ + - ]: 6214 : assert(chunking.GetChunk(i).feerate == chunking_left[i]);
606 : 6214 : }
607 : :
608 : : // Check consistency of chunking.
609 : 1271 : TestBitSet combined;
610 [ + + ]: 7485 : for (ClusterIndex i = 0; i < chunking.NumChunksLeft(); ++i) {
611 : 6214 : const auto& chunk_info = chunking.GetChunk(i);
612 : : // Chunks must be non-empty.
613 [ - + ]: 6214 : assert(chunk_info.transactions.Any());
614 : : // Chunk feerates must be monotonically non-increasing.
615 [ + + + - ]: 6214 : if (i > 0) assert(!(chunk_info.feerate >> chunking.GetChunk(i - 1).feerate));
616 : : // Chunks must be a subset of what is left of the linearization.
617 [ - + ]: 6214 : assert(chunk_info.transactions.IsSubsetOf(todo));
618 : : // Chunks' claimed feerates must match their transactions' aggregate feerate.
619 [ - + ]: 6214 : assert(depgraph.FeeRate(chunk_info.transactions) == chunk_info.feerate);
620 : : // Chunks must be the highest-feerate remaining prefix.
621 : 6214 : SetInfo<TestBitSet> accumulator, best;
622 [ + + ]: 171939 : for (auto j : linearization) {
623 [ + + + + ]: 165725 : if (todo[j] && !combined[j]) {
624 : 61558 : accumulator |= SetInfo(depgraph, j);
625 [ + + + + ]: 61558 : if (best.feerate.IsEmpty() || accumulator.feerate > best.feerate) {
626 : 11257 : best = accumulator;
627 : 11257 : }
628 : 61558 : }
629 : 165725 : }
630 [ - + ]: 6214 : assert(best.transactions == chunk_info.transactions);
631 [ - + ]: 6214 : assert(best.feerate == chunk_info.feerate);
632 : : // Chunks cannot overlap.
633 [ - + ]: 6214 : assert(!chunk_info.transactions.Overlaps(combined));
634 : 6214 : combined |= chunk_info.transactions;
635 : : // Chunks must be topological.
636 [ + + ]: 22005 : for (auto idx : chunk_info.transactions) {
637 [ + - ]: 15791 : assert((depgraph.Ancestors(idx) & todo).IsSubsetOf(combined));
638 : 15791 : }
639 : 6214 : }
640 [ + - ]: 1271 : assert(combined == todo);
641 : :
642 : : // Verify the expected properties of LinearizationChunking::IntersectPrefixes:
643 : 1271 : auto intersect = chunking.IntersectPrefixes(subset);
644 : : // - Intersecting again doesn't change the result.
645 [ + - ]: 1271 : assert(chunking.IntersectPrefixes(intersect) == intersect);
646 : : // - The intersection is topological.
647 : 1271 : TestBitSet intersect_anc;
648 [ + + ]: 3953 : for (auto idx : intersect.transactions) {
649 : 2682 : intersect_anc |= (depgraph.Ancestors(idx) & todo);
650 : 2682 : }
651 [ + - ]: 1271 : assert(intersect.transactions == intersect_anc);
652 : : // - The claimed intersection feerate matches its transactions.
653 [ + - ]: 1271 : assert(intersect.feerate == depgraph.FeeRate(intersect.transactions));
654 : : // - The intersection may only be empty if its input is empty.
655 [ + - ]: 1271 : assert(intersect.transactions.Any() == subset.transactions.Any());
656 : : // - The intersection feerate must be as high as the input.
657 [ + - ]: 1271 : assert(intersect.feerate >= subset.feerate);
658 : : // - No non-empty intersection between the intersection and a prefix of the chunks of the
659 : : // remainder of the linearization may be better than the intersection.
660 : 1271 : TestBitSet prefix;
661 [ + + ]: 7485 : for (ClusterIndex i = 0; i < chunking.NumChunksLeft(); ++i) {
662 : 6214 : prefix |= chunking.GetChunk(i).transactions;
663 : 6214 : auto reintersect = SetInfo(depgraph, prefix & intersect.transactions);
664 [ + + ]: 6214 : if (!reintersect.feerate.IsEmpty()) {
665 [ - + ]: 2672 : assert(reintersect.feerate <= intersect.feerate);
666 : 2672 : }
667 : 6214 : }
668 : :
669 : : // Find a subset to remove from linearization.
670 [ + - ]: 1271 : auto done = ReadTopologicalSet(depgraph, todo, reader);
671 [ + + ]: 1271 : if (done.None()) {
672 : : // We need to remove a non-empty subset, so fall back to the unlinearized ancestors of
673 : : // the first transaction in todo if done is empty.
674 : 1088 : done = depgraph.Ancestors(todo.First()) & todo;
675 : 1088 : }
676 : 1271 : todo -= done;
677 : 1271 : chunking.MarkDone(done);
678 : 1271 : subset = SetInfo(depgraph, subset.transactions - done);
679 : 1271 : }
680 : :
681 [ + - ]: 123 : assert(chunking.NumChunksLeft() == 0);
682 : 123 : }
683 : :
684 [ + - + - ]: 266 : FUZZ_TARGET(clusterlin_linearize)
685 : : {
686 : : // Verify the behavior of Linearize().
687 : :
688 : : // Retrieve an RNG seed, an iteration count, and a depgraph from the fuzz input.
689 : 263 : SpanReader reader(buffer);
690 : 263 : DepGraph<TestBitSet> depgraph;
691 : 263 : uint64_t rng_seed{0};
692 : 263 : uint64_t iter_count{0};
693 : : try {
694 [ + - + + : 267 : reader >> VARINT(iter_count) >> Using<DepGraphFormatter>(depgraph) >> rng_seed;
+ - + - +
+ ]
695 [ - + + - ]: 263 : } catch (const std::ios_base::failure&) {}
696 : :
697 : : // Optionally construct an old linearization for it.
698 : 263 : std::vector<ClusterIndex> old_linearization;
699 : : {
700 : 263 : uint8_t have_old_linearization{0};
701 : : try {
702 [ + + ]: 263 : reader >> have_old_linearization;
703 [ - + + - ]: 263 : } catch(const std::ios_base::failure&) {}
704 [ + + ]: 263 : if (have_old_linearization & 1) {
705 [ + - ]: 121 : old_linearization = ReadLinearization(depgraph, reader);
706 [ + - + - ]: 121 : SanityCheck(depgraph, old_linearization);
707 : 121 : }
708 : 263 : }
709 : :
710 : : // Invoke Linearize().
711 : 263 : iter_count &= 0x7ffff;
712 [ + - ]: 840 : auto [linearization, optimal] = Linearize(depgraph, iter_count, rng_seed, old_linearization);
713 [ + - + - ]: 263 : SanityCheck(depgraph, linearization);
714 [ + - + - ]: 526 : auto chunking = ChunkLinearization(depgraph, linearization);
715 : :
716 : : // Linearization must always be as good as the old one, if provided.
717 [ + + ]: 263 : if (!old_linearization.empty()) {
718 [ + - ]: 117 : auto old_chunking = ChunkLinearization(depgraph, old_linearization);
719 [ + - + - : 117 : auto cmp = CompareChunks(chunking, old_chunking);
+ - ]
720 [ + - ]: 117 : assert(cmp >= 0);
721 : 117 : }
722 : :
723 : : // If the iteration count is sufficiently high, an optimal linearization must be found.
724 : : // Each linearization step can use up to 2^k iterations, with steps k=1..n. That sum is
725 : : // 2 * (2^n - 1)
726 : 263 : const uint64_t n = depgraph.TxCount();
727 [ + + + + ]: 263 : if (n <= 18 && iter_count > 2U * ((uint64_t{1} << n) - 1U)) {
728 [ + - ]: 51 : assert(optimal);
729 : 51 : }
730 : :
731 : : // If Linearize claims optimal result, run quality tests.
732 [ + + ]: 263 : if (optimal) {
733 : : // It must be as good as SimpleLinearize.
734 [ + - ]: 435 : auto [simple_linearization, simple_optimal] = SimpleLinearize(depgraph, MAX_SIMPLE_ITERATIONS);
735 [ + - + - ]: 145 : SanityCheck(depgraph, simple_linearization);
736 [ + - + - ]: 290 : auto simple_chunking = ChunkLinearization(depgraph, simple_linearization);
737 [ + - + - : 145 : auto cmp = CompareChunks(chunking, simple_chunking);
+ - ]
738 [ + - ]: 145 : assert(cmp >= 0);
739 : : // If SimpleLinearize finds the optimal result too, they must be equal (if not,
740 : : // SimpleLinearize is broken).
741 [ + + + - ]: 145 : if (simple_optimal) assert(cmp == 0);
742 : :
743 : : // Only for very small clusters, test every topologically-valid permutation.
744 [ + + ]: 145 : if (depgraph.TxCount() <= 7) {
745 [ + - ]: 58 : std::vector<ClusterIndex> perm_linearization(depgraph.TxCount());
746 [ + + ]: 248 : for (ClusterIndex i = 0; i < depgraph.TxCount(); ++i) perm_linearization[i] = i;
747 : : // Iterate over all valid permutations.
748 : 58 : do {
749 : : // Determine whether perm_linearization is topological.
750 : 39896 : TestBitSet perm_done;
751 : 39896 : bool perm_is_topo{true};
752 [ + + ]: 145574 : for (auto i : perm_linearization) {
753 : 105678 : perm_done.Set(i);
754 [ + + ]: 105678 : if (!depgraph.Ancestors(i).IsSubsetOf(perm_done)) {
755 : 33411 : perm_is_topo = false;
756 : 33411 : break;
757 : : }
758 [ + + ]: 105678 : }
759 : : // If so, verify that the obtained linearization is as good as the permutation.
760 [ + + ]: 39896 : if (perm_is_topo) {
761 [ - + ]: 6485 : auto perm_chunking = ChunkLinearization(depgraph, perm_linearization);
762 [ + - + - : 6485 : auto cmp = CompareChunks(chunking, perm_chunking);
+ - ]
763 [ + - ]: 6485 : assert(cmp >= 0);
764 : 6485 : }
765 [ + - + + ]: 39896 : } while(std::next_permutation(perm_linearization.begin(), perm_linearization.end()));
766 : 58 : }
767 : 145 : }
768 : 570 : }
769 : :
770 [ + - + - ]: 94 : FUZZ_TARGET(clusterlin_postlinearize)
771 : : {
772 : : // Verify expected properties of PostLinearize() on arbitrary linearizations.
773 : :
774 : : // Retrieve a depgraph from the fuzz input.
775 : 91 : SpanReader reader(buffer);
776 : 91 : DepGraph<TestBitSet> depgraph;
777 : : try {
778 [ + - + - ]: 91 : reader >> Using<DepGraphFormatter>(depgraph);
779 [ # # # # ]: 91 : } catch (const std::ios_base::failure&) {}
780 : :
781 : : // Retrieve a linearization from the fuzz input.
782 : 91 : std::vector<ClusterIndex> linearization;
783 [ + - ]: 91 : linearization = ReadLinearization(depgraph, reader);
784 [ + - + - ]: 91 : SanityCheck(depgraph, linearization);
785 : :
786 : : // Produce a post-processed version.
787 [ + - ]: 91 : auto post_linearization = linearization;
788 [ + - + - ]: 91 : PostLinearize(depgraph, post_linearization);
789 [ + - + - ]: 91 : SanityCheck(depgraph, post_linearization);
790 : :
791 : : // Compare diagrams: post-linearization cannot worsen anywhere.
792 [ + - ]: 91 : auto chunking = ChunkLinearization(depgraph, linearization);
793 [ + - ]: 91 : auto post_chunking = ChunkLinearization(depgraph, post_linearization);
794 [ + - + - : 91 : auto cmp = CompareChunks(post_chunking, chunking);
+ - ]
795 [ + - ]: 91 : assert(cmp >= 0);
796 : :
797 : : // Run again, things can keep improving (and never get worse)
798 [ + - ]: 91 : auto post_post_linearization = post_linearization;
799 [ + - + - ]: 91 : PostLinearize(depgraph, post_post_linearization);
800 [ + - + - ]: 91 : SanityCheck(depgraph, post_post_linearization);
801 [ + - ]: 91 : auto post_post_chunking = ChunkLinearization(depgraph, post_post_linearization);
802 [ + - + - : 91 : cmp = CompareChunks(post_post_chunking, post_chunking);
+ - ]
803 [ + - ]: 91 : assert(cmp >= 0);
804 : :
805 : : // The chunks that come out of postlinearizing are always connected.
806 [ + - ]: 91 : LinearizationChunking linchunking(depgraph, post_linearization);
807 [ + + ]: 739 : while (linchunking.NumChunksLeft()) {
808 [ + - ]: 648 : assert(depgraph.IsConnected(linchunking.GetChunk(0).transactions));
809 : 648 : linchunking.MarkDone(linchunking.GetChunk(0).transactions);
810 : : }
811 : 91 : }
812 : :
813 [ + - + - ]: 195 : FUZZ_TARGET(clusterlin_postlinearize_tree)
814 : : {
815 : : // Verify expected properties of PostLinearize() on linearizations of graphs that form either
816 : : // an upright or reverse tree structure.
817 : :
818 : : // Construct a direction, RNG seed, and an arbitrary graph from the fuzz input.
819 : 192 : SpanReader reader(buffer);
820 : 192 : uint64_t rng_seed{0};
821 : 192 : DepGraph<TestBitSet> depgraph_gen;
822 : 192 : uint8_t direction{0};
823 : : try {
824 [ + + + + : 192 : reader >> direction >> rng_seed >> Using<DepGraphFormatter>(depgraph_gen);
+ - + - ]
825 [ - + + - ]: 192 : } catch (const std::ios_base::failure&) {}
826 : :
827 : : // Now construct a new graph, copying the nodes, but leaving only the first parent (even
828 : : // direction) or the first child (odd direction).
829 : 192 : DepGraph<TestBitSet> depgraph_tree;
830 [ + + ]: 4179 : for (ClusterIndex i = 0; i < depgraph_gen.TxCount(); ++i) {
831 : 3987 : depgraph_tree.AddTransaction(depgraph_gen.FeeRate(i));
832 : 3987 : }
833 [ + + ]: 192 : if (direction & 1) {
834 [ + + ]: 2849 : for (ClusterIndex i = 0; i < depgraph_gen.TxCount(); ++i) {
835 : 2731 : auto children = depgraph_gen.Descendants(i) - TestBitSet::Singleton(i);
836 : : // Remove descendants that are children of other descendants.
837 [ + + ]: 20548 : for (auto j : children) {
838 [ + + ]: 17817 : if (!children[j]) continue;
839 : 5282 : children -= depgraph_gen.Descendants(j);
840 : 5282 : children.Set(j);
841 [ + + ]: 17817 : }
842 [ + + ]: 2731 : if (children.Any()) depgraph_tree.AddDependency(i, children.First());
843 : 2731 : }
844 : 118 : } else {
845 [ + + ]: 1330 : for (ClusterIndex i = 0; i < depgraph_gen.TxCount(); ++i) {
846 : 1256 : auto parents = depgraph_gen.Ancestors(i) - TestBitSet::Singleton(i);
847 : : // Remove ancestors that are parents of other ancestors.
848 [ + + ]: 5461 : for (auto j : parents) {
849 [ + + ]: 4205 : if (!parents[j]) continue;
850 : 2792 : parents -= depgraph_gen.Ancestors(j);
851 : 2792 : parents.Set(j);
852 [ + + ]: 4205 : }
853 [ + + ]: 1256 : if (parents.Any()) depgraph_tree.AddDependency(parents.First(), i);
854 : 1256 : }
855 : : }
856 : :
857 : : // Retrieve a linearization from the fuzz input.
858 : 192 : std::vector<ClusterIndex> linearization;
859 [ + - ]: 192 : linearization = ReadLinearization(depgraph_tree, reader);
860 [ + - + - ]: 192 : SanityCheck(depgraph_tree, linearization);
861 : :
862 : : // Produce a postlinearized version.
863 [ + - ]: 192 : auto post_linearization = linearization;
864 [ + - + - ]: 192 : PostLinearize(depgraph_tree, post_linearization);
865 [ + - + - ]: 192 : SanityCheck(depgraph_tree, post_linearization);
866 : :
867 : : // Compare diagrams.
868 [ + - ]: 192 : auto chunking = ChunkLinearization(depgraph_tree, linearization);
869 [ + - ]: 192 : auto post_chunking = ChunkLinearization(depgraph_tree, post_linearization);
870 [ + - + - : 192 : auto cmp = CompareChunks(post_chunking, chunking);
+ - ]
871 [ + - ]: 192 : assert(cmp >= 0);
872 : :
873 : : // Verify that post-linearizing again does not change the diagram. The result must be identical
874 : : // as post_linearization ought to be optimal already with a tree-structured graph.
875 [ + - ]: 192 : auto post_post_linearization = post_linearization;
876 [ + - + - ]: 192 : PostLinearize(depgraph_tree, post_linearization);
877 [ + - + - ]: 192 : SanityCheck(depgraph_tree, post_linearization);
878 [ + - ]: 192 : auto post_post_chunking = ChunkLinearization(depgraph_tree, post_post_linearization);
879 [ + - + - : 192 : auto cmp_post = CompareChunks(post_post_chunking, post_chunking);
+ - ]
880 [ + - ]: 192 : assert(cmp_post == 0);
881 : :
882 : : // Try to find an even better linearization directly. This must not change the diagram for the
883 : : // same reason.
884 [ + - ]: 192 : auto [opt_linearization, _optimal] = Linearize(depgraph_tree, 100000, rng_seed, post_linearization);
885 [ + - + - ]: 384 : auto opt_chunking = ChunkLinearization(depgraph_tree, opt_linearization);
886 [ + - + - : 192 : auto cmp_opt = CompareChunks(opt_chunking, post_chunking);
+ - ]
887 [ + - ]: 192 : assert(cmp_opt == 0);
888 : 194 : }
889 : :
890 [ + - + - ]: 90 : FUZZ_TARGET(clusterlin_postlinearize_moved_leaf)
891 : : {
892 : : // Verify that taking an existing linearization, and moving a leaf to the back, potentially
893 : : // increasing its fee, and then post-linearizing, results in something as good as the
894 : : // original. This guarantees that in an RBF that replaces a transaction with one of the same
895 : : // size but higher fee, applying the "remove conflicts, append new transaction, postlinearize"
896 : : // process will never worsen linearization quality.
897 : :
898 : : // Construct an arbitrary graph and a fee from the fuzz input.
899 : 87 : SpanReader reader(buffer);
900 : 87 : DepGraph<TestBitSet> depgraph;
901 : 87 : int32_t fee_inc{0};
902 : : try {
903 : 87 : uint64_t fee_inc_code;
904 [ + - + - : 87 : reader >> Using<DepGraphFormatter>(depgraph) >> VARINT(fee_inc_code);
+ - + + ]
905 : 38 : fee_inc = fee_inc_code & 0x3ffff;
906 [ - + + - ]: 87 : } catch (const std::ios_base::failure&) {}
907 [ + + ]: 87 : if (depgraph.TxCount() == 0) return;
908 : :
909 : : // Retrieve two linearizations from the fuzz input.
910 [ + - ]: 77 : auto lin = ReadLinearization(depgraph, reader);
911 [ + - ]: 77 : auto lin_leaf = ReadLinearization(depgraph, reader);
912 : :
913 : : // Construct a linearization identical to lin, but with the tail end of lin_leaf moved to the
914 : : // back.
915 : 77 : std::vector<ClusterIndex> lin_moved;
916 [ + + ]: 1100 : for (auto i : lin) {
917 [ + + - + ]: 1023 : if (i != lin_leaf.back()) lin_moved.push_back(i);
918 : 1023 : }
919 [ + - ]: 77 : lin_moved.push_back(lin_leaf.back());
920 : :
921 : : // Postlinearize lin_moved.
922 [ + - + - ]: 77 : PostLinearize(depgraph, lin_moved);
923 [ + - + - ]: 77 : SanityCheck(depgraph, lin_moved);
924 : :
925 : : // Compare diagrams (applying the fee delta after computing the old one).
926 [ + - ]: 77 : auto old_chunking = ChunkLinearization(depgraph, lin);
927 : 77 : depgraph.FeeRate(lin_leaf.back()).fee += fee_inc;
928 [ + - ]: 77 : auto new_chunking = ChunkLinearization(depgraph, lin_moved);
929 [ + - + - : 77 : auto cmp = CompareChunks(new_chunking, old_chunking);
+ - ]
930 [ + - ]: 77 : assert(cmp >= 0);
931 [ - + ]: 136 : }
932 : :
933 [ + - + - ]: 178 : FUZZ_TARGET(clusterlin_merge)
934 : : {
935 : : // Construct an arbitrary graph from the fuzz input.
936 : 175 : SpanReader reader(buffer);
937 : 175 : DepGraph<TestBitSet> depgraph;
938 : : try {
939 [ + - + - ]: 175 : reader >> Using<DepGraphFormatter>(depgraph);
940 [ # # # # ]: 175 : } catch (const std::ios_base::failure&) {}
941 : :
942 : : // Retrieve two linearizations from the fuzz input.
943 [ + - ]: 175 : auto lin1 = ReadLinearization(depgraph, reader);
944 [ + - ]: 175 : auto lin2 = ReadLinearization(depgraph, reader);
945 : :
946 : : // Merge the two.
947 [ + - + - : 175 : auto lin_merged = MergeLinearizations(depgraph, lin1, lin2);
+ - ]
948 : :
949 : : // Compute chunkings and compare.
950 [ + - ]: 175 : auto chunking1 = ChunkLinearization(depgraph, lin1);
951 [ + - ]: 175 : auto chunking2 = ChunkLinearization(depgraph, lin2);
952 [ + - ]: 175 : auto chunking_merged = ChunkLinearization(depgraph, lin_merged);
953 [ + - + - : 175 : auto cmp1 = CompareChunks(chunking_merged, chunking1);
+ - ]
954 [ + - ]: 175 : assert(cmp1 >= 0);
955 [ + - + - : 175 : auto cmp2 = CompareChunks(chunking_merged, chunking2);
+ - ]
956 [ + - ]: 175 : assert(cmp2 >= 0);
957 : 175 : }
|