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 : 0 : SimpleCandidateFinder(const DepGraph<SetType>& depgraph LIFETIMEBOUND) noexcept :
39 : 0 : 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 : 0 : void MarkDone(SetType select) noexcept { m_todo -= select; }
43 : :
44 : : /** Determine whether unlinearized transactions remain. */
45 : 0 : 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 : 0 : std::pair<SetInfo<SetType>, uint64_t> FindCandidateSet(uint64_t max_iterations) const noexcept
54 : : {
55 : 0 : 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 : 0 : std::vector<std::pair<SetType, SetType>> queue;
60 : : // Initially we have just one queue element, with the entire graph in und.
61 : 0 : queue.emplace_back(SetType{}, m_todo);
62 : : // Best solution so far.
63 : 0 : SetInfo best(m_depgraph, m_todo);
64 : : // Process the queue.
65 [ # # # # ]: 0 : while (!queue.empty() && iterations_left) {
66 : 0 : --iterations_left;
67 : : // Pop top element of the queue.
68 : 0 : auto [inc, und] = queue.back();
69 : 0 : queue.pop_back();
70 : : // Look for a transaction to consider adding/removing.
71 : 0 : bool inc_none = inc.None();
72 [ # # ]: 0 : 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 [ # # # # ]: 0 : if (inc_none || inc.Overlaps(m_depgraph.Ancestors(split))) {
77 : : // Add a queue entry with split included.
78 : 0 : SetInfo new_inc(m_depgraph, inc | (m_todo & m_depgraph.Ancestors(split)));
79 : 0 : queue.emplace_back(new_inc.transactions, und - new_inc.transactions);
80 : : // Add a queue entry with split excluded.
81 : 0 : queue.emplace_back(inc, und - m_depgraph.Descendants(split));
82 : : // Update statistics to account for the candidate new_inc.
83 [ # # ]: 0 : if (new_inc.feerate > best.feerate) best = new_inc;
84 : : break;
85 : : }
86 : : }
87 : : }
88 : 0 : return {std::move(best), max_iterations - iterations_left};
89 : 0 : }
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 : 0 : ExhaustiveCandidateFinder(const DepGraph<SetType>& depgraph LIFETIMEBOUND) noexcept :
109 : 0 : 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 : 0 : void MarkDone(SetType select) noexcept { m_todo -= select; }
113 : :
114 : : /** Determine whether unlinearized transactions remain. */
115 : 0 : 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 : 0 : SetInfo<SetType> FindCandidateSet() const noexcept
122 : : {
123 : : // Best solution so far.
124 : 0 : SetInfo<SetType> best{m_todo, m_depgraph.FeeRate(m_todo)};
125 : : // The number of combinations to try.
126 : 0 : uint64_t limit = (uint64_t{1} << m_todo.Count()) - 1;
127 : : // Try the transitive closure of every non-empty subset of m_todo.
128 [ # # ]: 0 : 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 : 0 : SetType txn;
132 : 0 : auto x_shifted{x};
133 [ # # # # ]: 0 : for (auto i : m_todo) {
134 [ # # ]: 0 : if (x_shifted & 1) txn |= m_depgraph.Ancestors(i);
135 : 0 : x_shifted >>= 1;
136 : : }
137 : 0 : SetInfo cur(m_depgraph, txn & m_todo);
138 [ # # ]: 0 : if (cur.feerate > best.feerate) best = cur;
139 : : }
140 : 0 : return best;
141 : : }
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 : 0 : std::pair<std::vector<ClusterIndex>, bool> SimpleLinearize(const DepGraph<SetType>& depgraph, uint64_t max_iterations)
152 : : {
153 : 0 : std::vector<ClusterIndex> linearization;
154 : 0 : SimpleCandidateFinder finder(depgraph);
155 : 0 : SetType todo = SetType::Fill(depgraph.TxCount());
156 : 0 : bool optimal = true;
157 [ # # ]: 0 : while (todo.Any()) {
158 [ # # ]: 0 : auto [candidate, iterations_done] = finder.FindCandidateSet(max_iterations);
159 [ # # ]: 0 : if (iterations_done == max_iterations) optimal = false;
160 : 0 : depgraph.AppendTopo(linearization, candidate.transactions);
161 : 0 : todo -= candidate.transactions;
162 : 0 : finder.MarkDone(candidate.transactions);
163 : 0 : max_iterations -= iterations_done;
164 : : }
165 : 0 : return {std::move(linearization), optimal};
166 : 0 : }
167 : :
168 : : /** Given a dependency graph, and a todo set, read a topological subset of todo from reader. */
169 : : template<typename SetType>
170 : 0 : SetType ReadTopologicalSet(const DepGraph<SetType>& depgraph, const SetType& todo, SpanReader& reader)
171 : : {
172 [ # # ]: 0 : uint64_t mask{0};
173 : : try {
174 [ # # ]: 0 : reader >> VARINT(mask);
175 [ - - ]: 0 : } catch(const std::ios_base::failure&) {}
176 : 0 : SetType ret;
177 [ # # # # : 0 : for (auto i : todo) {
# # ]
178 [ # # ]: 0 : if (!ret[i]) {
179 [ # # ]: 0 : if (mask & 1) ret |= depgraph.Ancestors(i);
180 : 0 : mask >>= 1;
181 : : }
182 : : }
183 : 0 : return ret & todo;
184 : : }
185 : :
186 : : /** Given a dependency graph, construct any valid linearization for it, reading from a SpanReader. */
187 : : template<typename BS>
188 : 0 : std::vector<ClusterIndex> ReadLinearization(const DepGraph<BS>& depgraph, SpanReader& reader)
189 : : {
190 : 0 : std::vector<ClusterIndex> linearization;
191 : 0 : TestBitSet todo = TestBitSet::Fill(depgraph.TxCount());
192 : : // In every iteration one topologically-valid transaction is appended to linearization.
193 [ # # ]: 0 : while (todo.Any()) {
194 : : // Compute the set of transactions with no not-yet-included ancestors.
195 : 0 : TestBitSet potential_next;
196 [ # # # # ]: 0 : for (auto j : todo) {
197 [ # # ]: 0 : if ((depgraph.Ancestors(j) & todo) == TestBitSet::Singleton(j)) {
198 : 0 : potential_next.Set(j);
199 : : }
200 : : }
201 : : // There must always be one (otherwise there is a cycle in the graph).
202 [ # # ]: 0 : assert(potential_next.Any());
203 : : // Read a number from reader, and interpret it as index into potential_next.
204 [ # # ]: 0 : uint64_t idx{0};
205 : : try {
206 [ # # ]: 0 : reader >> VARINT(idx);
207 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
208 : 0 : idx %= potential_next.Count();
209 : : // Find out which transaction that corresponds to.
210 [ # # ]: 0 : for (auto j : potential_next) {
211 [ # # ]: 0 : if (idx == 0) {
212 : : // When found, add it to linearization and remove it from todo.
213 [ # # ]: 0 : linearization.push_back(j);
214 [ # # ]: 0 : assert(todo[j]);
215 : 0 : todo.Reset(j);
216 : : break;
217 : : }
218 : 0 : --idx;
219 : : }
220 : : }
221 : 0 : return linearization;
222 : 0 : }
223 : :
224 : : } // namespace
225 : :
226 [ # # ]: 0 : 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 : 0 : FuzzedDataProvider provider(buffer.data(), buffer.size());
233 : 0 : auto num_tx = provider.ConsumeIntegralInRange<ClusterIndex>(2, 32);
234 : 0 : Cluster<TestBitSet> cluster(num_tx, std::pair{FeeFrac{0, 1}, TestBitSet{}});
235 : : // Construct the corresponding DepGraph object (also no dependencies).
236 : 0 : DepGraph depgraph(cluster);
237 [ # # ]: 0 : SanityCheck(depgraph);
238 : : // Read (parent, child) pairs, and add them to the cluster and depgraph.
239 [ # # # # ]: 0 : LIMITED_WHILE(provider.remaining_bytes() > 0, TestBitSet::Size() * TestBitSet::Size()) {
240 : 0 : auto parent = provider.ConsumeIntegralInRange<ClusterIndex>(0, num_tx - 1);
241 : 0 : auto child = provider.ConsumeIntegralInRange<ClusterIndex>(0, num_tx - 2);
242 : 0 : child += (child >= parent);
243 : 0 : cluster[child].second.Set(parent);
244 : 0 : depgraph.AddDependency(parent, child);
245 [ # # ]: 0 : assert(depgraph.Ancestors(child)[parent]);
246 [ # # ]: 0 : assert(depgraph.Descendants(parent)[child]);
247 : : }
248 : : // Sanity check the result.
249 [ # # ]: 0 : SanityCheck(depgraph);
250 : : // Verify that the resulting DepGraph matches one recomputed from the cluster.
251 : 0 : assert(DepGraph(cluster) == depgraph);
252 : 0 : }
253 : :
254 [ # # ]: 0 : 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 : 0 : FuzzedDataProvider provider(buffer.data(), buffer.size());
261 : :
262 : : // Construct a cluster in a naive way (using a FuzzedDataProvider-based serialization).
263 : 0 : Cluster<TestBitSet> cluster;
264 : 0 : auto num_tx = provider.ConsumeIntegralInRange<ClusterIndex>(1, 32);
265 [ # # ]: 0 : cluster.resize(num_tx);
266 [ # # ]: 0 : for (ClusterIndex i = 0; i < num_tx; ++i) {
267 : 0 : cluster[i].first.size = provider.ConsumeIntegralInRange<int32_t>(1, 0x3fffff);
268 : 0 : cluster[i].first.fee = provider.ConsumeIntegralInRange<int64_t>(-0x8000000000000, 0x7ffffffffffff);
269 [ # # ]: 0 : for (ClusterIndex j = 0; j < num_tx; ++j) {
270 [ # # ]: 0 : if (i == j) continue;
271 [ # # ]: 0 : if (provider.ConsumeBool()) cluster[i].second.Set(j);
272 : : }
273 : : }
274 : :
275 : : // Construct dependency graph, and verify it matches the cluster (which includes a round-trip
276 : : // check for the serialization).
277 : 0 : DepGraph depgraph(cluster);
278 [ # # ]: 0 : VerifyDepGraphFromCluster(cluster, depgraph);
279 : 0 : }
280 : :
281 [ # # ]: 0 : 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 [ # # ]: 0 : SpanReader reader(buffer);
287 : 0 : DepGraph<TestBitSet> depgraph;
288 : 0 : try {
289 [ # # ]: 0 : reader >> Using<DepGraphFormatter>(depgraph);
290 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
291 [ # # ]: 0 : SanityCheck(depgraph);
292 : :
293 : : // Verify the graph is a DAG.
294 [ # # ]: 0 : assert(IsAcyclic(depgraph));
295 : 0 : }
296 : :
297 [ # # ]: 0 : FUZZ_TARGET(clusterlin_components)
298 : : {
299 : : // Verify the behavior of DepGraphs's FindConnectedComponent and IsConnected functions.
300 : :
301 : : // Construct a depgraph.
302 [ # # ]: 0 : SpanReader reader(buffer);
303 : 0 : DepGraph<TestBitSet> depgraph;
304 : 0 : try {
305 [ # # ]: 0 : reader >> Using<DepGraphFormatter>(depgraph);
306 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
307 : :
308 : 0 : TestBitSet todo = TestBitSet::Fill(depgraph.TxCount());
309 [ # # ]: 0 : while (todo.Any()) {
310 : : // Find a connected component inside todo.
311 : 0 : auto component = depgraph.FindConnectedComponent(todo);
312 : :
313 : : // The component must be a subset of todo and non-empty.
314 [ # # ]: 0 : assert(component.IsSubsetOf(todo));
315 [ # # ]: 0 : 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 [ # # ]: 0 : if (todo == TestBitSet::Fill(depgraph.TxCount())) {
320 [ # # # # ]: 0 : assert((component == todo) == depgraph.IsConnected());
321 : : }
322 : :
323 : : // If subset is connected, then component must match subset.
324 [ # # # # ]: 0 : assert((component == todo) == depgraph.IsConnected(todo));
325 : :
326 : : // The component cannot have any ancestors or descendants outside of component but in todo.
327 [ # # ]: 0 : for (auto i : component) {
328 [ # # ]: 0 : assert((depgraph.Ancestors(i) & todo).IsSubsetOf(component));
329 [ # # ]: 0 : assert((depgraph.Descendants(i) & todo).IsSubsetOf(component));
330 : : }
331 : :
332 : : // Starting from any component element, we must be able to reach every element.
333 [ # # ]: 0 : for (auto i : component) {
334 : : // Start with just i as reachable.
335 : 0 : TestBitSet reachable = TestBitSet::Singleton(i);
336 : : // Add in-todo descendants and ancestors to reachable until it does not change anymore.
337 : 0 : while (true) {
338 : 0 : TestBitSet new_reachable = reachable;
339 [ # # # # ]: 0 : for (auto j : new_reachable) {
340 : 0 : new_reachable |= depgraph.Ancestors(j) & todo;
341 : 0 : new_reachable |= depgraph.Descendants(j) & todo;
342 : : }
343 [ # # ]: 0 : if (new_reachable == reachable) break;
344 : 0 : reachable = new_reachable;
345 : 0 : }
346 : : // Verify that the result is the entire component.
347 [ # # ]: 0 : assert(component == reachable);
348 : : }
349 : :
350 : : // Construct an arbitrary subset of todo.
351 : 0 : uint64_t subset_bits{0};
352 : 0 : try {
353 [ # # ]: 0 : reader >> VARINT(subset_bits);
354 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
355 : 0 : TestBitSet subset;
356 [ # # ]: 0 : for (ClusterIndex i = 0; i < depgraph.TxCount(); ++i) {
357 [ # # ]: 0 : if (todo[i]) {
358 [ # # ]: 0 : if (subset_bits & 1) subset.Set(i);
359 : 0 : subset_bits >>= 1;
360 : : }
361 : : }
362 : : // Which must be non-empty.
363 [ # # # # ]: 0 : if (subset.None()) subset = TestBitSet::Singleton(todo.First());
364 : : // Remove it from todo.
365 : 0 : todo -= subset;
366 : : }
367 : :
368 : : // No components can be found in an empty subset.
369 [ # # ]: 0 : assert(depgraph.FindConnectedComponent(todo).None());
370 : 0 : }
371 : :
372 [ # # ]: 0 : FUZZ_TARGET(clusterlin_chunking)
373 : : {
374 : : // Verify the correctness of the ChunkLinearization function.
375 : :
376 : : // Construct a graph by deserializing.
377 [ # # ]: 0 : SpanReader reader(buffer);
378 : 0 : DepGraph<TestBitSet> depgraph;
379 : 0 : try {
380 [ # # ]: 0 : reader >> Using<DepGraphFormatter>(depgraph);
381 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
382 : :
383 : : // Read a valid linearization for depgraph.
384 [ # # ]: 0 : auto linearization = ReadLinearization(depgraph, reader);
385 : :
386 : : // Invoke the chunking function.
387 : 0 : auto chunking = ChunkLinearization(depgraph, linearization);
388 : :
389 : : // Verify that chunk feerates are monotonically non-increasing.
390 [ # # ]: 0 : for (size_t i = 1; i < chunking.size(); ++i) {
391 [ # # ]: 0 : assert(!(chunking[i] >> chunking[i - 1]));
392 : : }
393 : :
394 : : // Naively recompute the chunks (each is the highest-feerate prefix of what remains).
395 : 0 : auto todo = TestBitSet::Fill(depgraph.TxCount());
396 [ # # ]: 0 : for (const auto& chunk_feerate : chunking) {
397 [ # # ]: 0 : assert(todo.Any());
398 : 0 : SetInfo<TestBitSet> accumulator, best;
399 [ # # ]: 0 : for (ClusterIndex idx : linearization) {
400 [ # # ]: 0 : if (todo[idx]) {
401 : 0 : accumulator |= SetInfo(depgraph, idx);
402 [ # # # # ]: 0 : if (best.feerate.IsEmpty() || accumulator.feerate >> best.feerate) {
403 : 0 : best = accumulator;
404 : : }
405 : : }
406 : : }
407 [ # # ]: 0 : assert(chunk_feerate == best.feerate);
408 [ # # ]: 0 : assert(best.transactions.IsSubsetOf(todo));
409 : 0 : todo -= best.transactions;
410 : : }
411 [ # # ]: 0 : assert(todo.None());
412 : 0 : }
413 : :
414 [ # # ]: 0 : FUZZ_TARGET(clusterlin_ancestor_finder)
415 : : {
416 : : // Verify that AncestorCandidateFinder works as expected.
417 : :
418 : : // Retrieve a depgraph from the fuzz input.
419 [ # # ]: 0 : SpanReader reader(buffer);
420 : 0 : DepGraph<TestBitSet> depgraph;
421 : 0 : try {
422 [ # # ]: 0 : reader >> Using<DepGraphFormatter>(depgraph);
423 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
424 : :
425 : 0 : AncestorCandidateFinder anc_finder(depgraph);
426 : 0 : auto todo = TestBitSet::Fill(depgraph.TxCount());
427 [ # # ]: 0 : while (todo.Any()) {
428 : : // Call the ancestor finder's FindCandidateSet for what remains of the graph.
429 [ # # ]: 0 : assert(!anc_finder.AllDone());
430 : 0 : auto best_anc = anc_finder.FindCandidateSet();
431 : : // Sanity check the result.
432 [ # # ]: 0 : assert(best_anc.transactions.Any());
433 [ # # ]: 0 : assert(best_anc.transactions.IsSubsetOf(todo));
434 [ # # ]: 0 : assert(depgraph.FeeRate(best_anc.transactions) == best_anc.feerate);
435 [ # # ]: 0 : assert(depgraph.IsConnected(best_anc.transactions));
436 : : // Check that it is topologically valid.
437 [ # # # # ]: 0 : for (auto i : best_anc.transactions) {
438 [ # # ]: 0 : assert((depgraph.Ancestors(i) & todo).IsSubsetOf(best_anc.transactions));
439 : : }
440 : :
441 : : // Compute all remaining ancestor sets.
442 : 0 : std::optional<SetInfo<TestBitSet>> real_best_anc;
443 [ # # # # ]: 0 : for (auto i : todo) {
444 : 0 : SetInfo info(depgraph, todo & depgraph.Ancestors(i));
445 [ # # # # ]: 0 : if (!real_best_anc.has_value() || info.feerate > real_best_anc->feerate) {
446 [ # # ]: 0 : real_best_anc = info;
447 : : }
448 : : }
449 : : // The set returned by anc_finder must equal the real best ancestor sets.
450 [ # # ]: 0 : assert(real_best_anc.has_value());
451 [ # # ]: 0 : assert(*real_best_anc == best_anc);
452 : :
453 : : // Find a topologically valid subset of transactions to remove from the graph.
454 [ # # ]: 0 : auto del_set = ReadTopologicalSet(depgraph, todo, reader);
455 : : // If we did not find anything, use best_anc itself, because we should remove something.
456 [ # # ]: 0 : if (del_set.None()) del_set = best_anc.transactions;
457 : 0 : todo -= del_set;
458 : 0 : anc_finder.MarkDone(del_set);
459 : : }
460 [ # # ]: 0 : assert(anc_finder.AllDone());
461 : 0 : }
462 : :
463 : : static constexpr auto MAX_SIMPLE_ITERATIONS = 300000;
464 : :
465 [ # # ]: 0 : 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 [ # # ]: 0 : SpanReader reader(buffer);
473 : 0 : DepGraph<TestBitSet> depgraph;
474 : 0 : uint64_t rng_seed{0};
475 : 0 : try {
476 [ # # # # ]: 0 : reader >> Using<DepGraphFormatter>(depgraph) >> rng_seed;
477 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
478 : :
479 : : // Instantiate ALL the candidate finders.
480 : 0 : SearchCandidateFinder src_finder(depgraph, rng_seed);
481 : 0 : SimpleCandidateFinder smp_finder(depgraph);
482 : 0 : ExhaustiveCandidateFinder exh_finder(depgraph);
483 : 0 : AncestorCandidateFinder anc_finder(depgraph);
484 : :
485 : 0 : auto todo = TestBitSet::Fill(depgraph.TxCount());
486 [ # # ]: 0 : while (todo.Any()) {
487 [ # # ]: 0 : assert(!src_finder.AllDone());
488 [ # # ]: 0 : assert(!smp_finder.AllDone());
489 [ # # ]: 0 : assert(!exh_finder.AllDone());
490 [ # # ]: 0 : assert(!anc_finder.AllDone());
491 : :
492 : : // For each iteration, read an iteration count limit from the fuzz input.
493 : 0 : uint64_t max_iterations = 1;
494 : 0 : try {
495 [ # # ]: 0 : reader >> VARINT(max_iterations);
496 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
497 : 0 : max_iterations &= 0xfffff;
498 : :
499 : : // Read an initial subset from the fuzz input.
500 [ # # ]: 0 : SetInfo init_best(depgraph, ReadTopologicalSet(depgraph, todo, reader));
501 : :
502 : : // Call the search finder's FindCandidateSet for what remains of the graph.
503 [ # # ]: 0 : auto [found, iterations_done] = src_finder.FindCandidateSet(max_iterations, init_best);
504 : :
505 : : // Sanity check the result.
506 [ # # ]: 0 : assert(iterations_done <= max_iterations);
507 [ # # ]: 0 : assert(found.transactions.Any());
508 [ # # ]: 0 : assert(found.transactions.IsSubsetOf(todo));
509 [ # # ]: 0 : assert(depgraph.FeeRate(found.transactions) == found.feerate);
510 [ # # # # ]: 0 : if (!init_best.feerate.IsEmpty()) assert(found.feerate >= init_best.feerate);
511 : : // Check that it is topologically valid.
512 [ # # # # ]: 0 : for (auto i : found.transactions) {
513 [ # # ]: 0 : assert(found.transactions.IsSupersetOf(depgraph.Ancestors(i) & todo));
514 : : }
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 [ # # ]: 0 : assert(iterations_done <= ((uint64_t{1} << todo.Count()) - 1));
519 : :
520 : : // Perform quality checks only if SearchCandidateFinder claims an optimal result.
521 [ # # ]: 0 : if (iterations_done < max_iterations) {
522 : : // Optimal sets are always connected.
523 [ # # ]: 0 : assert(depgraph.IsConnected(found.transactions));
524 : :
525 : : // Compare with SimpleCandidateFinder.
526 [ # # ]: 0 : auto [simple, simple_iters] = smp_finder.FindCandidateSet(MAX_SIMPLE_ITERATIONS);
527 [ # # ]: 0 : assert(found.feerate >= simple.feerate);
528 [ # # ]: 0 : if (simple_iters < MAX_SIMPLE_ITERATIONS) {
529 [ # # ]: 0 : assert(found.feerate == simple.feerate);
530 : : }
531 : :
532 : : // Compare with AncestorCandidateFinder;
533 : 0 : auto anc = anc_finder.FindCandidateSet();
534 [ # # ]: 0 : 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 [ # # ]: 0 : if (todo.Count() <= 12) {
539 : 0 : auto exhaustive = exh_finder.FindCandidateSet();
540 [ # # ]: 0 : assert(exhaustive.feerate == found.feerate);
541 : : // Also compare ExhaustiveCandidateFinder with SimpleCandidateFinder (this is
542 : : // primarily a test for SimpleCandidateFinder's correctness).
543 [ # # ]: 0 : assert(exhaustive.feerate >= simple.feerate);
544 [ # # ]: 0 : if (simple_iters < MAX_SIMPLE_ITERATIONS) {
545 [ # # ]: 0 : assert(exhaustive.feerate == simple.feerate);
546 : : }
547 : : }
548 : : }
549 : :
550 : : // Find a topologically valid subset of transactions to remove from the graph.
551 [ # # ]: 0 : auto del_set = ReadTopologicalSet(depgraph, todo, reader);
552 : : // If we did not find anything, use found itself, because we should remove something.
553 [ # # ]: 0 : if (del_set.None()) del_set = found.transactions;
554 : 0 : todo -= del_set;
555 : 0 : src_finder.MarkDone(del_set);
556 : 0 : smp_finder.MarkDone(del_set);
557 : 0 : exh_finder.MarkDone(del_set);
558 : 0 : anc_finder.MarkDone(del_set);
559 : : }
560 : :
561 [ # # ]: 0 : assert(src_finder.AllDone());
562 [ # # ]: 0 : assert(smp_finder.AllDone());
563 [ # # ]: 0 : assert(exh_finder.AllDone());
564 [ # # ]: 0 : assert(anc_finder.AllDone());
565 : 0 : }
566 : :
567 [ # # ]: 0 : FUZZ_TARGET(clusterlin_linearization_chunking)
568 : : {
569 : : // Verify the behavior of LinearizationChunking.
570 : :
571 : : // Retrieve a depgraph from the fuzz input.
572 [ # # ]: 0 : SpanReader reader(buffer);
573 : 0 : DepGraph<TestBitSet> depgraph;
574 : 0 : try {
575 [ # # ]: 0 : reader >> Using<DepGraphFormatter>(depgraph);
576 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
577 : :
578 : : // Retrieve a topologically-valid subset of depgraph.
579 [ # # ]: 0 : auto todo = TestBitSet::Fill(depgraph.TxCount());
580 [ # # ]: 0 : auto subset = SetInfo(depgraph, ReadTopologicalSet(depgraph, todo, reader));
581 : :
582 : : // Retrieve a valid linearization for depgraph.
583 [ # # ]: 0 : auto linearization = ReadLinearization(depgraph, reader);
584 : :
585 : : // Construct a LinearizationChunking object, initially for the whole linearization.
586 : 0 : LinearizationChunking chunking(depgraph, linearization);
587 : :
588 : : // Incrementally remove transactions from the chunking object, and check various properties at
589 : : // every step.
590 [ # # ]: 0 : while (todo.Any()) {
591 [ # # ]: 0 : assert(chunking.NumChunksLeft() > 0);
592 : :
593 : : // Construct linearization with just todo.
594 : 0 : std::vector<ClusterIndex> linearization_left;
595 [ # # ]: 0 : for (auto i : linearization) {
596 [ # # # # ]: 0 : if (todo[i]) linearization_left.push_back(i);
597 : : }
598 : :
599 : : // Compute the chunking for linearization_left.
600 : 0 : auto chunking_left = ChunkLinearization(depgraph, linearization_left);
601 : :
602 : : // Verify that it matches the feerates of the chunks of chunking.
603 [ # # ]: 0 : assert(chunking.NumChunksLeft() == chunking_left.size());
604 [ # # ]: 0 : for (ClusterIndex i = 0; i < chunking.NumChunksLeft(); ++i) {
605 [ # # ]: 0 : assert(chunking.GetChunk(i).feerate == chunking_left[i]);
606 : : }
607 : :
608 : : // Check consistency of chunking.
609 : 0 : TestBitSet combined;
610 [ # # ]: 0 : for (ClusterIndex i = 0; i < chunking.NumChunksLeft(); ++i) {
611 [ # # ]: 0 : const auto& chunk_info = chunking.GetChunk(i);
612 : : // Chunks must be non-empty.
613 [ # # ]: 0 : assert(chunk_info.transactions.Any());
614 : : // Chunk feerates must be monotonically non-increasing.
615 [ # # # # ]: 0 : 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 [ # # ]: 0 : assert(chunk_info.transactions.IsSubsetOf(todo));
618 : : // Chunks' claimed feerates must match their transactions' aggregate feerate.
619 [ # # ]: 0 : assert(depgraph.FeeRate(chunk_info.transactions) == chunk_info.feerate);
620 : : // Chunks must be the highest-feerate remaining prefix.
621 : 0 : SetInfo<TestBitSet> accumulator, best;
622 [ # # ]: 0 : for (auto j : linearization) {
623 [ # # # # ]: 0 : if (todo[j] && !combined[j]) {
624 : 0 : accumulator |= SetInfo(depgraph, j);
625 [ # # # # ]: 0 : if (best.feerate.IsEmpty() || accumulator.feerate > best.feerate) {
626 : 0 : best = accumulator;
627 : : }
628 : : }
629 : : }
630 [ # # ]: 0 : assert(best.transactions == chunk_info.transactions);
631 [ # # ]: 0 : assert(best.feerate == chunk_info.feerate);
632 : : // Chunks cannot overlap.
633 [ # # ]: 0 : assert(!chunk_info.transactions.Overlaps(combined));
634 [ # # ]: 0 : combined |= chunk_info.transactions;
635 : : // Chunks must be topological.
636 [ # # # # ]: 0 : for (auto idx : chunk_info.transactions) {
637 [ # # ]: 0 : assert((depgraph.Ancestors(idx) & todo).IsSubsetOf(combined));
638 : : }
639 : : }
640 [ # # ]: 0 : assert(combined == todo);
641 : :
642 : : // Verify the expected properties of LinearizationChunking::IntersectPrefixes:
643 : 0 : auto intersect = chunking.IntersectPrefixes(subset);
644 : : // - Intersecting again doesn't change the result.
645 [ # # ]: 0 : assert(chunking.IntersectPrefixes(intersect) == intersect);
646 : : // - The intersection is topological.
647 : 0 : TestBitSet intersect_anc;
648 [ # # # # ]: 0 : for (auto idx : intersect.transactions) {
649 : 0 : intersect_anc |= (depgraph.Ancestors(idx) & todo);
650 : : }
651 [ # # ]: 0 : assert(intersect.transactions == intersect_anc);
652 : : // - The claimed intersection feerate matches its transactions.
653 [ # # ]: 0 : assert(intersect.feerate == depgraph.FeeRate(intersect.transactions));
654 : : // - The intersection may only be empty if its input is empty.
655 [ # # ]: 0 : assert(intersect.transactions.Any() == subset.transactions.Any());
656 : : // - The intersection feerate must be as high as the input.
657 [ # # ]: 0 : 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 : 0 : TestBitSet prefix;
661 [ # # ]: 0 : for (ClusterIndex i = 0; i < chunking.NumChunksLeft(); ++i) {
662 : 0 : prefix |= chunking.GetChunk(i).transactions;
663 : 0 : auto reintersect = SetInfo(depgraph, prefix & intersect.transactions);
664 [ # # ]: 0 : if (!reintersect.feerate.IsEmpty()) {
665 [ # # ]: 0 : assert(reintersect.feerate <= intersect.feerate);
666 : : }
667 : : }
668 : :
669 : : // Find a subset to remove from linearization.
670 [ # # ]: 0 : auto done = ReadTopologicalSet(depgraph, todo, reader);
671 [ # # ]: 0 : 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 [ # # ]: 0 : done = depgraph.Ancestors(todo.First()) & todo;
675 : : }
676 : 0 : todo -= done;
677 : 0 : chunking.MarkDone(done);
678 : 0 : subset = SetInfo(depgraph, subset.transactions - done);
679 : 0 : }
680 : :
681 [ # # ]: 0 : assert(chunking.NumChunksLeft() == 0);
682 : 0 : }
683 : :
684 [ # # ]: 0 : 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 [ # # ]: 0 : SpanReader reader(buffer);
690 : 0 : DepGraph<TestBitSet> depgraph;
691 : 0 : uint64_t rng_seed{0};
692 : 0 : uint64_t iter_count{0};
693 : 0 : try {
694 [ # # # # : 0 : reader >> VARINT(iter_count) >> Using<DepGraphFormatter>(depgraph) >> rng_seed;
# # ]
695 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
696 : :
697 : : // Optionally construct an old linearization for it.
698 : 0 : std::vector<ClusterIndex> old_linearization;
699 : 0 : {
700 : 0 : uint8_t have_old_linearization{0};
701 : 0 : try {
702 [ # # ]: 0 : reader >> have_old_linearization;
703 [ - - ]: 0 : } catch(const std::ios_base::failure&) {}
704 [ # # ]: 0 : if (have_old_linearization & 1) {
705 [ # # ]: 0 : old_linearization = ReadLinearization(depgraph, reader);
706 : 0 : SanityCheck(depgraph, old_linearization);
707 : : }
708 : : }
709 : :
710 : : // Invoke Linearize().
711 : 0 : iter_count &= 0x7ffff;
712 : 0 : auto [linearization, optimal] = Linearize(depgraph, iter_count, rng_seed, old_linearization);
713 : 0 : SanityCheck(depgraph, linearization);
714 : 0 : auto chunking = ChunkLinearization(depgraph, linearization);
715 : :
716 : : // Linearization must always be as good as the old one, if provided.
717 [ # # ]: 0 : if (!old_linearization.empty()) {
718 : 0 : auto old_chunking = ChunkLinearization(depgraph, old_linearization);
719 [ # # ]: 0 : auto cmp = CompareChunks(chunking, old_chunking);
720 [ # # ]: 0 : assert(cmp >= 0);
721 : 0 : }
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 [ # # ]: 0 : const uint64_t n = depgraph.TxCount();
727 [ # # # # ]: 0 : if (n <= 18 && iter_count > 2U * ((uint64_t{1} << n) - 1U)) {
728 [ # # ]: 0 : assert(optimal);
729 : : }
730 : :
731 : : // If Linearize claims optimal result, run quality tests.
732 [ # # ]: 0 : if (optimal) {
733 : : // It must be as good as SimpleLinearize.
734 : 0 : auto [simple_linearization, simple_optimal] = SimpleLinearize(depgraph, MAX_SIMPLE_ITERATIONS);
735 : 0 : SanityCheck(depgraph, simple_linearization);
736 : 0 : auto simple_chunking = ChunkLinearization(depgraph, simple_linearization);
737 [ # # ]: 0 : auto cmp = CompareChunks(chunking, simple_chunking);
738 [ # # ]: 0 : assert(cmp >= 0);
739 : : // If SimpleLinearize finds the optimal result too, they must be equal (if not,
740 : : // SimpleLinearize is broken).
741 [ # # # # ]: 0 : if (simple_optimal) assert(cmp == 0);
742 : :
743 : : // Only for very small clusters, test every topologically-valid permutation.
744 [ # # ]: 0 : if (depgraph.TxCount() <= 7) {
745 [ # # ]: 0 : std::vector<ClusterIndex> perm_linearization(depgraph.TxCount());
746 [ # # ]: 0 : for (ClusterIndex i = 0; i < depgraph.TxCount(); ++i) perm_linearization[i] = i;
747 : : // Iterate over all valid permutations.
748 : 0 : do {
749 : : // Determine whether perm_linearization is topological.
750 : 0 : TestBitSet perm_done;
751 : 0 : bool perm_is_topo{true};
752 [ # # ]: 0 : for (auto i : perm_linearization) {
753 [ # # ]: 0 : perm_done.Set(i);
754 [ # # ]: 0 : if (!depgraph.Ancestors(i).IsSubsetOf(perm_done)) {
755 : : perm_is_topo = false;
756 : : break;
757 : : }
758 : : }
759 : : // If so, verify that the obtained linearization is as good as the permutation.
760 [ # # ]: 0 : if (perm_is_topo) {
761 : 0 : auto perm_chunking = ChunkLinearization(depgraph, perm_linearization);
762 [ # # ]: 0 : auto cmp = CompareChunks(chunking, perm_chunking);
763 [ # # ]: 0 : assert(cmp >= 0);
764 : 0 : }
765 [ # # ]: 0 : } while(std::next_permutation(perm_linearization.begin(), perm_linearization.end()));
766 : 0 : }
767 : 0 : }
768 : 0 : }
769 : :
770 [ # # ]: 0 : FUZZ_TARGET(clusterlin_postlinearize)
771 : : {
772 : : // Verify expected properties of PostLinearize() on arbitrary linearizations.
773 : :
774 : : // Retrieve a depgraph from the fuzz input.
775 [ # # ]: 0 : SpanReader reader(buffer);
776 : 0 : DepGraph<TestBitSet> depgraph;
777 : 0 : try {
778 [ # # ]: 0 : reader >> Using<DepGraphFormatter>(depgraph);
779 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
780 : :
781 : : // Retrieve a linearization from the fuzz input.
782 : 0 : std::vector<ClusterIndex> linearization;
783 [ # # ]: 0 : linearization = ReadLinearization(depgraph, reader);
784 : 0 : SanityCheck(depgraph, linearization);
785 : :
786 : : // Produce a post-processed version.
787 [ # # ]: 0 : auto post_linearization = linearization;
788 [ # # ]: 0 : PostLinearize(depgraph, post_linearization);
789 : 0 : SanityCheck(depgraph, post_linearization);
790 : :
791 : : // Compare diagrams: post-linearization cannot worsen anywhere.
792 : 0 : auto chunking = ChunkLinearization(depgraph, linearization);
793 : 0 : auto post_chunking = ChunkLinearization(depgraph, post_linearization);
794 [ # # ]: 0 : auto cmp = CompareChunks(post_chunking, chunking);
795 [ # # ]: 0 : assert(cmp >= 0);
796 : :
797 : : // Run again, things can keep improving (and never get worse)
798 [ # # ]: 0 : auto post_post_linearization = post_linearization;
799 [ # # ]: 0 : PostLinearize(depgraph, post_post_linearization);
800 : 0 : SanityCheck(depgraph, post_post_linearization);
801 : 0 : auto post_post_chunking = ChunkLinearization(depgraph, post_post_linearization);
802 [ # # ]: 0 : cmp = CompareChunks(post_post_chunking, post_chunking);
803 [ # # ]: 0 : assert(cmp >= 0);
804 : :
805 : : // The chunks that come out of postlinearizing are always connected.
806 : 0 : LinearizationChunking linchunking(depgraph, post_linearization);
807 [ # # ]: 0 : while (linchunking.NumChunksLeft()) {
808 [ # # ]: 0 : assert(depgraph.IsConnected(linchunking.GetChunk(0).transactions));
809 : 0 : linchunking.MarkDone(linchunking.GetChunk(0).transactions);
810 : : }
811 : 0 : }
812 : :
813 [ # # ]: 0 : 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 [ # # ]: 0 : SpanReader reader(buffer);
820 : 0 : uint64_t rng_seed{0};
821 : 0 : DepGraph<TestBitSet> depgraph_gen;
822 : 0 : uint8_t direction{0};
823 : 0 : try {
824 [ # # # # : 0 : reader >> direction >> rng_seed >> Using<DepGraphFormatter>(depgraph_gen);
# # ]
825 [ - - ]: 0 : } 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 : 0 : DepGraph<TestBitSet> depgraph_tree;
830 [ # # ]: 0 : for (ClusterIndex i = 0; i < depgraph_gen.TxCount(); ++i) {
831 : 0 : depgraph_tree.AddTransaction(depgraph_gen.FeeRate(i));
832 : : }
833 [ # # ]: 0 : if (direction & 1) {
834 [ # # ]: 0 : for (ClusterIndex i = 0; i < depgraph_gen.TxCount(); ++i) {
835 [ # # ]: 0 : auto children = depgraph_gen.Descendants(i) - TestBitSet::Singleton(i);
836 : : // Remove descendants that are children of other descendants.
837 [ # # # # ]: 0 : for (auto j : children) {
838 [ # # ]: 0 : if (!children[j]) continue;
839 : 0 : children -= depgraph_gen.Descendants(j);
840 : 0 : children.Set(j);
841 : : }
842 [ # # ]: 0 : if (children.Any()) depgraph_tree.AddDependency(i, children.First());
843 : : }
844 : : } else {
845 [ # # ]: 0 : for (ClusterIndex i = 0; i < depgraph_gen.TxCount(); ++i) {
846 [ # # ]: 0 : auto parents = depgraph_gen.Ancestors(i) - TestBitSet::Singleton(i);
847 : : // Remove ancestors that are parents of other ancestors.
848 [ # # # # ]: 0 : for (auto j : parents) {
849 [ # # ]: 0 : if (!parents[j]) continue;
850 : 0 : parents -= depgraph_gen.Ancestors(j);
851 : 0 : parents.Set(j);
852 : : }
853 [ # # ]: 0 : if (parents.Any()) depgraph_tree.AddDependency(parents.First(), i);
854 : : }
855 : : }
856 : :
857 : : // Retrieve a linearization from the fuzz input.
858 : 0 : std::vector<ClusterIndex> linearization;
859 [ # # ]: 0 : linearization = ReadLinearization(depgraph_tree, reader);
860 : 0 : SanityCheck(depgraph_tree, linearization);
861 : :
862 : : // Produce a postlinearized version.
863 [ # # ]: 0 : auto post_linearization = linearization;
864 [ # # ]: 0 : PostLinearize(depgraph_tree, post_linearization);
865 : 0 : SanityCheck(depgraph_tree, post_linearization);
866 : :
867 : : // Compare diagrams.
868 : 0 : auto chunking = ChunkLinearization(depgraph_tree, linearization);
869 : 0 : auto post_chunking = ChunkLinearization(depgraph_tree, post_linearization);
870 [ # # ]: 0 : auto cmp = CompareChunks(post_chunking, chunking);
871 [ # # ]: 0 : 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 [ # # ]: 0 : auto post_post_linearization = post_linearization;
876 [ # # ]: 0 : PostLinearize(depgraph_tree, post_linearization);
877 : 0 : SanityCheck(depgraph_tree, post_linearization);
878 : 0 : auto post_post_chunking = ChunkLinearization(depgraph_tree, post_post_linearization);
879 [ # # ]: 0 : auto cmp_post = CompareChunks(post_post_chunking, post_chunking);
880 [ # # ]: 0 : 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 : 0 : auto [opt_linearization, _optimal] = Linearize(depgraph_tree, 100000, rng_seed, post_linearization);
885 : 0 : auto opt_chunking = ChunkLinearization(depgraph_tree, opt_linearization);
886 [ # # ]: 0 : auto cmp_opt = CompareChunks(opt_chunking, post_chunking);
887 [ # # ]: 0 : assert(cmp_opt == 0);
888 : 0 : }
889 : :
890 [ # # ]: 0 : 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 [ # # ]: 0 : SpanReader reader(buffer);
900 : 0 : DepGraph<TestBitSet> depgraph;
901 : 0 : int32_t fee_inc{0};
902 : 0 : try {
903 : 0 : uint64_t fee_inc_code;
904 [ # # # # ]: 0 : reader >> Using<DepGraphFormatter>(depgraph) >> VARINT(fee_inc_code);
905 : 0 : fee_inc = fee_inc_code & 0x3ffff;
906 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
907 [ # # ]: 0 : if (depgraph.TxCount() == 0) return;
908 : :
909 : : // Retrieve two linearizations from the fuzz input.
910 [ # # ]: 0 : auto lin = ReadLinearization(depgraph, reader);
911 [ # # ]: 0 : 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 : 0 : std::vector<ClusterIndex> lin_moved;
916 [ # # ]: 0 : for (auto i : lin) {
917 [ # # # # ]: 0 : if (i != lin_leaf.back()) lin_moved.push_back(i);
918 : : }
919 [ # # ]: 0 : lin_moved.push_back(lin_leaf.back());
920 : :
921 : : // Postlinearize lin_moved.
922 [ # # ]: 0 : PostLinearize(depgraph, lin_moved);
923 : 0 : SanityCheck(depgraph, lin_moved);
924 : :
925 : : // Compare diagrams (applying the fee delta after computing the old one).
926 : 0 : auto old_chunking = ChunkLinearization(depgraph, lin);
927 : 0 : depgraph.FeeRate(lin_leaf.back()).fee += fee_inc;
928 : 0 : auto new_chunking = ChunkLinearization(depgraph, lin_moved);
929 [ # # ]: 0 : auto cmp = CompareChunks(new_chunking, old_chunking);
930 [ # # ]: 0 : assert(cmp >= 0);
931 : 0 : }
932 : :
933 [ # # ]: 0 : FUZZ_TARGET(clusterlin_merge)
934 : : {
935 : : // Construct an arbitrary graph from the fuzz input.
936 [ # # ]: 0 : SpanReader reader(buffer);
937 : 0 : DepGraph<TestBitSet> depgraph;
938 : 0 : try {
939 [ # # ]: 0 : reader >> Using<DepGraphFormatter>(depgraph);
940 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
941 : :
942 : : // Retrieve two linearizations from the fuzz input.
943 [ # # ]: 0 : auto lin1 = ReadLinearization(depgraph, reader);
944 [ # # ]: 0 : auto lin2 = ReadLinearization(depgraph, reader);
945 : :
946 : : // Merge the two.
947 [ # # ]: 0 : auto lin_merged = MergeLinearizations(depgraph, lin1, lin2);
948 : :
949 : : // Compute chunkings and compare.
950 : 0 : auto chunking1 = ChunkLinearization(depgraph, lin1);
951 : 0 : auto chunking2 = ChunkLinearization(depgraph, lin2);
952 : 0 : auto chunking_merged = ChunkLinearization(depgraph, lin_merged);
953 [ # # ]: 0 : auto cmp1 = CompareChunks(chunking_merged, chunking1);
954 [ # # ]: 0 : assert(cmp1 >= 0);
955 [ # # ]: 0 : auto cmp2 = CompareChunks(chunking_merged, chunking2);
956 [ # # ]: 0 : assert(cmp2 >= 0);
957 : 0 : }
|
