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/fuzz.h>
10 : : #include <test/fuzz/FuzzedDataProvider.h>
11 : : #include <test/util/cluster_linearize.h>
12 : : #include <util/bitset.h>
13 : : #include <util/feefrac.h>
14 : :
15 : : #include <algorithm>
16 : : #include <stdint.h>
17 : : #include <vector>
18 : : #include <utility>
19 : :
20 : : using namespace cluster_linearize;
21 : :
22 : : namespace {
23 : :
24 : : /** A simple finder class for candidate sets.
25 : : *
26 : : * This class matches SearchCandidateFinder in interface and behavior, though with fewer
27 : : * optimizations.
28 : : */
29 : : template<typename SetType>
30 : : class SimpleCandidateFinder
31 : : {
32 : : /** Internal dependency graph. */
33 : : const DepGraph<SetType>& m_depgraph;
34 : : /** Which transaction are left to include. */
35 : : SetType m_todo;
36 : :
37 : : public:
38 : : /** Construct an SimpleCandidateFinder for a given graph. */
39 : 646 : SimpleCandidateFinder(const DepGraph<SetType>& depgraph LIFETIMEBOUND) noexcept :
40 : 646 : m_depgraph(depgraph), m_todo{depgraph.Positions()} {}
41 : :
42 : : /** Remove a set of transactions from the set of to-be-linearized ones. */
43 : 4282 : void MarkDone(SetType select) noexcept { m_todo -= select; }
44 : :
45 : : /** Determine whether unlinearized transactions remain. */
46 : 2662 : bool AllDone() const noexcept { return m_todo.None(); }
47 : :
48 : : /** Find a candidate set using at most max_iterations iterations, and the number of iterations
49 : : * actually performed. If that number is less than max_iterations, then the result is optimal.
50 : : *
51 : : * Complexity: O(N * M), where M is the number of connected topological subsets of the cluster.
52 : : * That number is bounded by M <= 2^(N-1).
53 : : */
54 : 3375 : std::pair<SetInfo<SetType>, uint64_t> FindCandidateSet(uint64_t max_iterations) const noexcept
55 : : {
56 : 3375 : uint64_t iterations_left = max_iterations;
57 : : // Queue of work units. Each consists of:
58 : : // - inc: set of transactions definitely included
59 : : // - und: set of transactions that can be added to inc still
60 : 3375 : std::vector<std::pair<SetType, SetType>> queue;
61 : : // Initially we have just one queue element, with the entire graph in und.
62 : 3375 : queue.emplace_back(SetType{}, m_todo);
63 : : // Best solution so far.
64 : 3375 : SetInfo best(m_depgraph, m_todo);
65 : : // Process the queue.
66 [ + + + + ]: 8841396 : while (!queue.empty() && iterations_left) {
67 : 8838021 : --iterations_left;
68 : : // Pop top element of the queue.
69 : 8838021 : auto [inc, und] = queue.back();
70 : 8838021 : queue.pop_back();
71 : : // Look for a transaction to consider adding/removing.
72 : 8838021 : bool inc_none = inc.None();
73 [ + + ]: 14650337 : for (auto split : und) {
74 : : // If inc is empty, consider any split transaction. Otherwise only consider
75 : : // transactions that share ancestry with inc so far (which means only connected
76 : : // sets will be considered).
77 [ + + + + ]: 10229741 : if (inc_none || inc.Overlaps(m_depgraph.Ancestors(split))) {
78 : : // Add a queue entry with split included.
79 : 4417425 : SetInfo new_inc(m_depgraph, inc | (m_todo & m_depgraph.Ancestors(split)));
80 : 4417425 : queue.emplace_back(new_inc.transactions, und - new_inc.transactions);
81 : : // Add a queue entry with split excluded.
82 : 4417425 : queue.emplace_back(inc, und - m_depgraph.Descendants(split));
83 : : // Update statistics to account for the candidate new_inc.
84 [ + + ]: 4417425 : if (new_inc.feerate > best.feerate) best = new_inc;
85 : : break;
86 : : }
87 : : }
88 : : }
89 : 3375 : return {std::move(best), max_iterations - iterations_left};
90 : 3375 : }
91 : : };
92 : :
93 : : /** A very simple finder class for optimal candidate sets, which tries every subset.
94 : : *
95 : : * It is even simpler than SimpleCandidateFinder, and is primarily included here to test the
96 : : * correctness of SimpleCandidateFinder, which is then used to test the correctness of
97 : : * SearchCandidateFinder.
98 : : */
99 : : template<typename SetType>
100 : : class ExhaustiveCandidateFinder
101 : : {
102 : : /** Internal dependency graph. */
103 : : const DepGraph<SetType>& m_depgraph;
104 : : /** Which transaction are left to include. */
105 : : SetType m_todo;
106 : :
107 : : public:
108 : : /** Construct an ExhaustiveCandidateFinder for a given graph. */
109 : 331 : ExhaustiveCandidateFinder(const DepGraph<SetType>& depgraph LIFETIMEBOUND) noexcept :
110 : 331 : m_depgraph(depgraph), m_todo{depgraph.Positions()} {}
111 : :
112 : : /** Remove a set of transactions from the set of to-be-linearized ones. */
113 : 2331 : void MarkDone(SetType select) noexcept { m_todo -= select; }
114 : :
115 : : /** Determine whether unlinearized transactions remain. */
116 : 2662 : bool AllDone() const noexcept { return m_todo.None(); }
117 : :
118 : : /** Find the optimal remaining candidate set.
119 : : *
120 : : * Complexity: O(N * 2^N).
121 : : */
122 : 820 : SetInfo<SetType> FindCandidateSet() const noexcept
123 : : {
124 : : // Best solution so far.
125 : 820 : SetInfo<SetType> best{m_todo, m_depgraph.FeeRate(m_todo)};
126 : : // The number of combinations to try.
127 : 820 : uint64_t limit = (uint64_t{1} << m_todo.Count()) - 1;
128 : : // Try the transitive closure of every non-empty subset of m_todo.
129 [ + + ]: 342318 : for (uint64_t x = 1; x < limit; ++x) {
130 : : // If bit number b is set in x, then the remaining ancestors of the b'th remaining
131 : : // transaction in m_todo are included.
132 : 341498 : SetType txn;
133 : 341498 : auto x_shifted{x};
134 [ + - + + ]: 4386076 : for (auto i : m_todo) {
135 [ + + ]: 3703080 : if (x_shifted & 1) txn |= m_depgraph.Ancestors(i);
136 : 3703080 : x_shifted >>= 1;
137 : : }
138 : 341498 : SetInfo cur(m_depgraph, txn & m_todo);
139 [ + + ]: 341498 : if (cur.feerate > best.feerate) best = cur;
140 : : }
141 : 820 : return best;
142 : : }
143 : : };
144 : :
145 : : /** A simple linearization algorithm.
146 : : *
147 : : * This matches Linearize() in interface and behavior, though with fewer optimizations, lacking
148 : : * the ability to pass in an existing linearization, and using just SimpleCandidateFinder rather
149 : : * than AncestorCandidateFinder and SearchCandidateFinder.
150 : : */
151 : : template<typename SetType>
152 : 315 : std::pair<std::vector<ClusterIndex>, bool> SimpleLinearize(const DepGraph<SetType>& depgraph, uint64_t max_iterations)
153 : : {
154 : 315 : std::vector<ClusterIndex> linearization;
155 : 315 : SimpleCandidateFinder finder(depgraph);
156 : 315 : SetType todo = depgraph.Positions();
157 : 315 : bool optimal = true;
158 [ + + ]: 2266 : while (todo.Any()) {
159 [ + + ]: 1951 : auto [candidate, iterations_done] = finder.FindCandidateSet(max_iterations);
160 [ + + ]: 1951 : if (iterations_done == max_iterations) optimal = false;
161 : 1951 : depgraph.AppendTopo(linearization, candidate.transactions);
162 : 1951 : todo -= candidate.transactions;
163 : 1951 : finder.MarkDone(candidate.transactions);
164 : 1951 : max_iterations -= iterations_done;
165 : : }
166 : 315 : return {std::move(linearization), optimal};
167 : 315 : }
168 : :
169 : : /** Stitch connected components together in a DepGraph, guaranteeing its corresponding cluster is connected. */
170 : : template<typename BS>
171 : 922 : void MakeConnected(DepGraph<BS>& depgraph)
172 : : {
173 : 922 : auto todo = depgraph.Positions();
174 : 922 : auto comp = depgraph.FindConnectedComponent(todo);
175 : 922 : Assume(depgraph.IsConnected(comp));
176 : 922 : todo -= comp;
177 [ + + ]: 9703 : while (todo.Any()) {
178 : 8781 : auto nextcomp = depgraph.FindConnectedComponent(todo);
179 : 8781 : Assume(depgraph.IsConnected(nextcomp));
180 : 8781 : depgraph.AddDependencies(BS::Singleton(comp.Last()), nextcomp.First());
181 : 8781 : todo -= nextcomp;
182 : 8781 : comp = nextcomp;
183 : : }
184 : 922 : }
185 : :
186 : : /** Given a dependency graph, and a todo set, read a topological subset of todo from reader. */
187 : : template<typename SetType>
188 : 7134 : SetType ReadTopologicalSet(const DepGraph<SetType>& depgraph, const SetType& todo, SpanReader& reader)
189 : : {
190 [ + + ]: 7134 : uint64_t mask{0};
191 : : try {
192 [ + + ]: 7134 : reader >> VARINT(mask);
193 [ - + ]: 4152 : } catch(const std::ios_base::failure&) {}
194 : 7134 : SetType ret;
195 [ + + + + ]: 103613 : for (auto i : todo) {
196 [ + + ]: 89352 : if (!ret[i]) {
197 [ + + ]: 86563 : if (mask & 1) ret |= depgraph.Ancestors(i);
198 : 86563 : mask >>= 1;
199 : : }
200 : : }
201 : 7134 : return ret & todo;
202 : : }
203 : :
204 : : /** Given a dependency graph, construct any valid linearization for it, reading from a SpanReader. */
205 : : template<typename BS>
206 : 1500 : std::vector<ClusterIndex> ReadLinearization(const DepGraph<BS>& depgraph, SpanReader& reader)
207 : : {
208 : 1500 : std::vector<ClusterIndex> linearization;
209 : 1500 : TestBitSet todo = depgraph.Positions();
210 : : // In every iteration one topologically-valid transaction is appended to linearization.
211 [ + + ]: 31898 : while (todo.Any()) {
212 : : // Compute the set of transactions with no not-yet-included ancestors.
213 : 28898 : TestBitSet potential_next;
214 [ + + ]: 428104 : for (auto j : todo) {
215 [ + + ]: 631994 : if ((depgraph.Ancestors(j) & todo) == TestBitSet::Singleton(j)) {
216 : 232788 : potential_next.Set(j);
217 : : }
218 : : }
219 : : // There must always be one (otherwise there is a cycle in the graph).
220 [ - + ]: 28898 : assert(potential_next.Any());
221 : : // Read a number from reader, and interpret it as index into potential_next.
222 [ + + ]: 28898 : uint64_t idx{0};
223 : : try {
224 [ + + + - ]: 57796 : reader >> VARINT(idx);
225 [ - + ]: 22616 : } catch (const std::ios_base::failure&) {}
226 : 28898 : idx %= potential_next.Count();
227 : : // Find out which transaction that corresponds to.
228 [ + - + - ]: 78772 : for (auto j : potential_next) {
229 [ + + ]: 49874 : if (idx == 0) {
230 : : // When found, add it to linearization and remove it from todo.
231 [ + - ]: 28898 : linearization.push_back(j);
232 [ - + ]: 28898 : assert(todo[j]);
233 : 28898 : todo.Reset(j);
234 : 28898 : break;
235 : : }
236 : 20976 : --idx;
237 : : }
238 : : }
239 : 1500 : return linearization;
240 : 0 : }
241 : :
242 : : } // namespace
243 : :
244 [ + - ]: 551 : FUZZ_TARGET(clusterlin_depgraph_sim)
245 : : {
246 : : // Simulation test to verify the full behavior of DepGraph.
247 : :
248 : 139 : FuzzedDataProvider provider(buffer.data(), buffer.size());
249 : :
250 : : /** Real DepGraph being tested. */
251 : 139 : DepGraph<TestBitSet> real;
252 : : /** Simulated DepGraph (sim[i] is std::nullopt if position i does not exist; otherwise,
253 : : * sim[i]->first is its individual feerate, and sim[i]->second is its set of ancestors. */
254 : 139 : std::array<std::optional<std::pair<FeeFrac, TestBitSet>>, TestBitSet::Size()> sim;
255 : : /** The number of non-nullopt position in sim. */
256 : 139 : ClusterIndex num_tx_sim{0};
257 : :
258 : : /** Read a valid index of a transaction from the provider. */
259 : 10137 : auto idx_fn = [&]() {
260 : 9998 : auto offset = provider.ConsumeIntegralInRange<ClusterIndex>(0, num_tx_sim - 1);
261 [ + - ]: 121017 : for (ClusterIndex i = 0; i < sim.size(); ++i) {
262 [ + + ]: 121017 : if (!sim[i].has_value()) continue;
263 [ + + ]: 103266 : if (offset == 0) return i;
264 : 93268 : --offset;
265 : : }
266 : 0 : assert(false);
267 : : return ClusterIndex(-1);
268 : 139 : };
269 : :
270 : : /** Read a valid subset of the transactions from the provider. */
271 : 10137 : auto subset_fn = [&]() {
272 : 9998 : auto range = (uint64_t{1} << num_tx_sim) - 1;
273 : 9998 : const auto mask = provider.ConsumeIntegralInRange<uint64_t>(0, range);
274 : 9998 : auto mask_shifted = mask;
275 : 9998 : TestBitSet subset;
276 [ + + ]: 329934 : for (ClusterIndex i = 0; i < sim.size(); ++i) {
277 [ + + ]: 319936 : if (!sim[i].has_value()) continue;
278 [ + + ]: 183675 : if (mask_shifted & 1) {
279 : 78431 : subset.Set(i);
280 : : }
281 : 183675 : mask_shifted >>= 1;
282 : : }
283 [ - + ]: 9998 : assert(mask_shifted == 0);
284 : 9998 : return subset;
285 : 139 : };
286 : :
287 : : /** Read any set of transactions from the provider (including unused positions). */
288 : 3977 : auto set_fn = [&]() {
289 : 3838 : auto range = (uint64_t{1} << sim.size()) - 1;
290 : 3838 : const auto mask = provider.ConsumeIntegralInRange<uint64_t>(0, range);
291 : 3838 : TestBitSet set;
292 [ + + ]: 126654 : for (ClusterIndex i = 0; i < sim.size(); ++i) {
293 [ + + ]: 122816 : if ((mask >> i) & 1) {
294 : 45802 : set.Set(i);
295 : : }
296 : : }
297 : 3838 : return set;
298 : 139 : };
299 : :
300 : : /** Propagate ancestor information in sim. */
301 : 4116 : auto anc_update_fn = [&]() {
302 : 4403 : while (true) {
303 : 4403 : bool updates{false};
304 [ + + ]: 145299 : for (ClusterIndex chl = 0; chl < sim.size(); ++chl) {
305 [ + + ]: 140896 : if (!sim[chl].has_value()) continue;
306 [ + - + + ]: 196709 : for (auto par : sim[chl]->second) {
307 [ + + ]: 115885 : if (!sim[chl]->second.IsSupersetOf(sim[par]->second)) {
308 : 1820 : sim[chl]->second |= sim[par]->second;
309 : 1820 : updates = true;
310 : : }
311 : : }
312 : : }
313 [ + + ]: 4403 : if (!updates) break;
314 : : }
315 : 4116 : };
316 : :
317 : : /** Compare the state of transaction i in the simulation with the real one. */
318 : 50389 : auto check_fn = [&](ClusterIndex i) {
319 : : // Compare used positions.
320 [ - + ]: 50250 : assert(real.Positions()[i] == sim[i].has_value());
321 [ + + ]: 50250 : if (sim[i].has_value()) {
322 : : // Compare feerate.
323 [ + - ]: 6450 : assert(real.FeeRate(i) == sim[i]->first);
324 : : // Compare ancestors (note that SanityCheck verifies correspondence between ancestors
325 : : // and descendants, so we can restrict ourselves to ancestors here).
326 [ - + ]: 6450 : assert(real.Ancestors(i) == sim[i]->second);
327 : : }
328 : 50389 : };
329 : :
330 [ + + + + ]: 20425 : LIMITED_WHILE(provider.remaining_bytes() > 0, 1000) {
331 : 20286 : uint8_t command = provider.ConsumeIntegral<uint8_t>();
332 [ + + + + : 20286 : if (num_tx_sim == 0 || ((command % 3) <= 0 && num_tx_sim < TestBitSet::Size())) {
+ + ]
333 : : // AddTransaction.
334 : 6450 : auto fee = provider.ConsumeIntegralInRange<int64_t>(-0x8000000000000, 0x7ffffffffffff);
335 : 6450 : auto size = provider.ConsumeIntegralInRange<int32_t>(1, 0x3fffff);
336 : 6450 : FeeFrac feerate{fee, size};
337 : : // Apply to DepGraph.
338 : 6450 : auto idx = real.AddTransaction(feerate);
339 : : // Verify that the returned index is correct.
340 [ - + ]: 6450 : assert(!sim[idx].has_value());
341 [ + - ]: 80361 : for (ClusterIndex i = 0; i < TestBitSet::Size(); ++i) {
342 [ + + ]: 80361 : if (!sim[i].has_value()) {
343 [ - + ]: 6450 : assert(idx == i);
344 : : break;
345 : : }
346 : : }
347 : : // Update sim.
348 [ - + ]: 6450 : sim[idx] = {feerate, TestBitSet::Singleton(idx)};
349 : 6450 : ++num_tx_sim;
350 : 6450 : continue;
351 : 6450 : }
352 [ + + ]: 13836 : if ((command % 3) <= 1 && num_tx_sim > 0) {
353 : : // AddDependencies.
354 : 9998 : ClusterIndex child = idx_fn();
355 : 9998 : auto parents = subset_fn();
356 : : // Apply to DepGraph.
357 : 9998 : real.AddDependencies(parents, child);
358 : : // Apply to sim.
359 : 9998 : sim[child]->second |= parents;
360 : 9998 : continue;
361 : 9998 : }
362 : 3838 : if (num_tx_sim > 0) {
363 : : // Remove transactions.
364 : 3838 : auto del = set_fn();
365 : : // Propagate all ancestry information before deleting anything in the simulation (as
366 : : // intermediary transactions may be deleted which impact connectivity).
367 : 3838 : anc_update_fn();
368 : : // Compare the state of the transactions being deleted.
369 [ + + + + ]: 53176 : for (auto i : del) check_fn(i);
370 : : // Apply to DepGraph.
371 : 3838 : real.RemoveTransactions(del);
372 : : // Apply to sim.
373 [ + + ]: 126654 : for (ClusterIndex i = 0; i < sim.size(); ++i) {
374 [ + + ]: 122816 : if (sim[i].has_value()) {
375 [ + + ]: 30300 : if (del[i]) {
376 : 4409 : --num_tx_sim;
377 [ + - ]: 127225 : sim[i] = std::nullopt;
378 : : } else {
379 : 25891 : sim[i]->second -= del;
380 : : }
381 : : }
382 : : }
383 : 3838 : continue;
384 : 3838 : }
385 : : // This should be unreachable (one of the 3 above actions should always be possible).
386 : : assert(false);
387 : : }
388 : :
389 : : // Compare the real obtained depgraph against the simulation.
390 : 139 : anc_update_fn();
391 [ + + ]: 4587 : for (ClusterIndex i = 0; i < sim.size(); ++i) check_fn(i);
392 [ - + ]: 139 : assert(real.TxCount() == num_tx_sim);
393 : : // Sanity check the result (which includes round-tripping serialization, if applicable).
394 [ + - ]: 139 : SanityCheck(real);
395 : 139 : }
396 : :
397 [ + - ]: 589 : FUZZ_TARGET(clusterlin_depgraph_serialization)
398 : : {
399 : : // Verify that any deserialized depgraph is acyclic and roundtrips to an identical depgraph.
400 : :
401 : : // Construct a graph by deserializing.
402 [ + - ]: 177 : SpanReader reader(buffer);
403 : 177 : DepGraph<TestBitSet> depgraph;
404 : 177 : try {
405 [ + - ]: 177 : reader >> Using<DepGraphFormatter>(depgraph);
406 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
407 [ + - ]: 177 : SanityCheck(depgraph);
408 : :
409 : : // Verify the graph is a DAG.
410 [ - + ]: 177 : assert(IsAcyclic(depgraph));
411 : 177 : }
412 : :
413 [ + - ]: 506 : FUZZ_TARGET(clusterlin_components)
414 : : {
415 : : // Verify the behavior of DepGraphs's FindConnectedComponent and IsConnected functions.
416 : :
417 : : // Construct a depgraph.
418 [ + - ]: 94 : SpanReader reader(buffer);
419 : 94 : DepGraph<TestBitSet> depgraph;
420 : 94 : try {
421 [ + - ]: 94 : reader >> Using<DepGraphFormatter>(depgraph);
422 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
423 : :
424 : 94 : TestBitSet todo = depgraph.Positions();
425 [ + + ]: 1199 : while (todo.Any()) {
426 : : // Find a connected component inside todo.
427 : 1105 : auto component = depgraph.FindConnectedComponent(todo);
428 : :
429 : : // The component must be a subset of todo and non-empty.
430 [ - + ]: 1105 : assert(component.IsSubsetOf(todo));
431 [ - + ]: 1105 : assert(component.Any());
432 : :
433 : : // If todo is the entire graph, and the entire graph is connected, then the component must
434 : : // be the entire graph.
435 [ + + ]: 1105 : if (todo == depgraph.Positions()) {
436 [ + + - + ]: 150 : assert((component == todo) == depgraph.IsConnected());
437 : : }
438 : :
439 : : // If subset is connected, then component must match subset.
440 [ + + - + ]: 1901 : assert((component == todo) == depgraph.IsConnected(todo));
441 : :
442 : : // The component cannot have any ancestors or descendants outside of component but in todo.
443 [ + + ]: 7785 : for (auto i : component) {
444 [ - + ]: 6680 : assert((depgraph.Ancestors(i) & todo).IsSubsetOf(component));
445 [ - + ]: 6680 : assert((depgraph.Descendants(i) & todo).IsSubsetOf(component));
446 : : }
447 : :
448 : : // Starting from any component element, we must be able to reach every element.
449 [ + + ]: 7785 : for (auto i : component) {
450 : : // Start with just i as reachable.
451 : 6680 : TestBitSet reachable = TestBitSet::Singleton(i);
452 : : // Add in-todo descendants and ancestors to reachable until it does not change anymore.
453 : 51950 : while (true) {
454 : 29315 : TestBitSet new_reachable = reachable;
455 [ + - + + ]: 363262 : for (auto j : new_reachable) {
456 : 304632 : new_reachable |= depgraph.Ancestors(j) & todo;
457 : 304632 : new_reachable |= depgraph.Descendants(j) & todo;
458 : : }
459 [ + + ]: 29315 : if (new_reachable == reachable) break;
460 : 22635 : reachable = new_reachable;
461 : 22635 : }
462 : : // Verify that the result is the entire component.
463 [ - + ]: 6680 : assert(component == reachable);
464 : : }
465 : :
466 : : // Construct an arbitrary subset of todo.
467 : 1105 : uint64_t subset_bits{0};
468 : 1105 : try {
469 [ + + ]: 1105 : reader >> VARINT(subset_bits);
470 [ - + ]: 903 : } catch (const std::ios_base::failure&) {}
471 : 1105 : TestBitSet subset;
472 [ + - + + ]: 27002 : for (ClusterIndex i : depgraph.Positions()) {
473 [ + + ]: 24792 : if (todo[i]) {
474 [ + + ]: 12788 : if (subset_bits & 1) subset.Set(i);
475 : 12788 : subset_bits >>= 1;
476 : : }
477 : : }
478 : : // Which must be non-empty.
479 [ + + ]: 1105 : if (subset.None()) subset = TestBitSet::Singleton(todo.First());
480 : : // Remove it from todo.
481 : 1105 : todo -= subset;
482 : : }
483 : :
484 : : // No components can be found in an empty subset.
485 [ - + ]: 94 : assert(depgraph.FindConnectedComponent(todo).None());
486 : 94 : }
487 : :
488 [ + - ]: 604 : FUZZ_TARGET(clusterlin_make_connected)
489 : : {
490 : : // Verify that MakeConnected makes graphs connected.
491 : :
492 [ + - ]: 192 : SpanReader reader(buffer);
493 : 192 : DepGraph<TestBitSet> depgraph;
494 : 192 : try {
495 [ + - ]: 192 : reader >> Using<DepGraphFormatter>(depgraph);
496 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
497 [ + - ]: 192 : MakeConnected(depgraph);
498 [ + - ]: 192 : SanityCheck(depgraph);
499 [ - + ]: 192 : assert(depgraph.IsConnected());
500 : 192 : }
501 : :
502 [ + - ]: 503 : FUZZ_TARGET(clusterlin_chunking)
503 : : {
504 : : // Verify the correctness of the ChunkLinearization function.
505 : :
506 : : // Construct a graph by deserializing.
507 [ + - ]: 91 : SpanReader reader(buffer);
508 : 91 : DepGraph<TestBitSet> depgraph;
509 : 91 : try {
510 [ + - ]: 91 : reader >> Using<DepGraphFormatter>(depgraph);
511 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
512 : :
513 : : // Read a valid linearization for depgraph.
514 [ + - ]: 91 : auto linearization = ReadLinearization(depgraph, reader);
515 : :
516 : : // Invoke the chunking function.
517 : 91 : auto chunking = ChunkLinearization(depgraph, linearization);
518 : :
519 : : // Verify that chunk feerates are monotonically non-increasing.
520 [ + + ]: 381 : for (size_t i = 1; i < chunking.size(); ++i) {
521 [ - + ]: 290 : assert(!(chunking[i] >> chunking[i - 1]));
522 : : }
523 : :
524 : : // Naively recompute the chunks (each is the highest-feerate prefix of what remains).
525 : 91 : auto todo = depgraph.Positions();
526 [ + + ]: 466 : for (const auto& chunk_feerate : chunking) {
527 [ - + ]: 375 : assert(todo.Any());
528 : 375 : SetInfo<TestBitSet> accumulator, best;
529 [ + + ]: 8300 : for (ClusterIndex idx : linearization) {
530 [ + + ]: 7925 : if (todo[idx]) {
531 : 4247 : accumulator.Set(depgraph, idx);
532 [ + + + + ]: 4247 : if (best.feerate.IsEmpty() || accumulator.feerate >> best.feerate) {
533 : 794 : best = accumulator;
534 : : }
535 : : }
536 : : }
537 [ + - ]: 375 : assert(chunk_feerate == best.feerate);
538 [ - + ]: 375 : assert(best.transactions.IsSubsetOf(todo));
539 : 375 : todo -= best.transactions;
540 : : }
541 [ - + ]: 91 : assert(todo.None());
542 : 91 : }
543 : :
544 [ + - ]: 515 : FUZZ_TARGET(clusterlin_ancestor_finder)
545 : : {
546 : : // Verify that AncestorCandidateFinder works as expected.
547 : :
548 : : // Retrieve a depgraph from the fuzz input.
549 [ + - ]: 103 : SpanReader reader(buffer);
550 : 103 : DepGraph<TestBitSet> depgraph;
551 : 103 : try {
552 [ + - ]: 103 : reader >> Using<DepGraphFormatter>(depgraph);
553 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
554 : :
555 : 103 : AncestorCandidateFinder anc_finder(depgraph);
556 : 103 : auto todo = depgraph.Positions();
557 [ + + ]: 1047 : while (todo.Any()) {
558 : : // Call the ancestor finder's FindCandidateSet for what remains of the graph.
559 [ - + ]: 944 : assert(!anc_finder.AllDone());
560 [ - + ]: 944 : assert(todo.Count() == anc_finder.NumRemaining());
561 : 944 : auto best_anc = anc_finder.FindCandidateSet();
562 : : // Sanity check the result.
563 [ - + ]: 944 : assert(best_anc.transactions.Any());
564 [ - + ]: 944 : assert(best_anc.transactions.IsSubsetOf(todo));
565 [ + - ]: 944 : assert(depgraph.FeeRate(best_anc.transactions) == best_anc.feerate);
566 [ - + ]: 944 : assert(depgraph.IsConnected(best_anc.transactions));
567 : : // Check that it is topologically valid.
568 [ + - + + ]: 3484 : for (auto i : best_anc.transactions) {
569 [ - + ]: 1596 : assert((depgraph.Ancestors(i) & todo).IsSubsetOf(best_anc.transactions));
570 : : }
571 : :
572 : : // Compute all remaining ancestor sets.
573 : 944 : std::optional<SetInfo<TestBitSet>> real_best_anc;
574 [ + - + + ]: 12753 : for (auto i : todo) {
575 : 10865 : SetInfo info(depgraph, todo & depgraph.Ancestors(i));
576 [ + + + + ]: 10865 : if (!real_best_anc.has_value() || info.feerate > real_best_anc->feerate) {
577 [ + + ]: 13081 : real_best_anc = info;
578 : : }
579 : : }
580 : : // The set returned by anc_finder must equal the real best ancestor sets.
581 [ - + ]: 944 : assert(real_best_anc.has_value());
582 [ + - ]: 944 : assert(*real_best_anc == best_anc);
583 : :
584 : : // Find a topologically valid subset of transactions to remove from the graph.
585 [ + - ]: 944 : auto del_set = ReadTopologicalSet(depgraph, todo, reader);
586 : : // If we did not find anything, use best_anc itself, because we should remove something.
587 [ + + ]: 944 : if (del_set.None()) del_set = best_anc.transactions;
588 : 944 : todo -= del_set;
589 : 944 : anc_finder.MarkDone(del_set);
590 : : }
591 [ - + ]: 103 : assert(anc_finder.AllDone());
592 [ - + ]: 103 : assert(anc_finder.NumRemaining() == 0);
593 : 103 : }
594 : :
595 : : static constexpr auto MAX_SIMPLE_ITERATIONS = 300000;
596 : :
597 [ + - ]: 743 : FUZZ_TARGET(clusterlin_search_finder)
598 : : {
599 : : // Verify that SearchCandidateFinder works as expected by sanity checking the results
600 : : // and comparing with the results from SimpleCandidateFinder, ExhaustiveCandidateFinder, and
601 : : // AncestorCandidateFinder.
602 : :
603 : : // Retrieve an RNG seed, a depgraph, and whether to make it connected, from the fuzz input.
604 [ + - ]: 331 : SpanReader reader(buffer);
605 : 331 : DepGraph<TestBitSet> depgraph;
606 : 331 : uint64_t rng_seed{0};
607 : 331 : uint8_t make_connected{1};
608 : 331 : try {
609 [ + - + + : 331 : reader >> Using<DepGraphFormatter>(depgraph) >> rng_seed >> make_connected;
+ + ]
610 [ - + ]: 132 : } catch (const std::ios_base::failure&) {}
611 : : // The most complicated graphs are connected ones (other ones just split up). Optionally force
612 : : // the graph to be connected.
613 [ + + + - ]: 331 : if (make_connected) MakeConnected(depgraph);
614 : :
615 : : // Instantiate ALL the candidate finders.
616 : 331 : SearchCandidateFinder src_finder(depgraph, rng_seed);
617 : 331 : SimpleCandidateFinder smp_finder(depgraph);
618 : 331 : ExhaustiveCandidateFinder exh_finder(depgraph);
619 : 331 : AncestorCandidateFinder anc_finder(depgraph);
620 : :
621 : 331 : auto todo = depgraph.Positions();
622 [ + + ]: 2662 : while (todo.Any()) {
623 [ - + ]: 2331 : assert(!src_finder.AllDone());
624 [ - + ]: 2331 : assert(!smp_finder.AllDone());
625 [ - + ]: 2331 : assert(!exh_finder.AllDone());
626 [ - + ]: 2331 : assert(!anc_finder.AllDone());
627 [ - + ]: 2331 : assert(anc_finder.NumRemaining() == todo.Count());
628 : :
629 : : // For each iteration, read an iteration count limit from the fuzz input.
630 : 2331 : uint64_t max_iterations = 1;
631 : 2331 : try {
632 [ + + ]: 2331 : reader >> VARINT(max_iterations);
633 [ - + ]: 1028 : } catch (const std::ios_base::failure&) {}
634 : 2331 : max_iterations &= 0xfffff;
635 : :
636 : : // Read an initial subset from the fuzz input.
637 [ + - ]: 2331 : SetInfo init_best(depgraph, ReadTopologicalSet(depgraph, todo, reader));
638 : :
639 : : // Call the search finder's FindCandidateSet for what remains of the graph.
640 [ - + ]: 2331 : auto [found, iterations_done] = src_finder.FindCandidateSet(max_iterations, init_best);
641 : :
642 : : // Sanity check the result.
643 [ - + ]: 2331 : assert(iterations_done <= max_iterations);
644 [ - + ]: 2331 : assert(found.transactions.Any());
645 [ - + ]: 2331 : assert(found.transactions.IsSubsetOf(todo));
646 [ + - ]: 2331 : assert(depgraph.FeeRate(found.transactions) == found.feerate);
647 [ + + - + ]: 2331 : if (!init_best.feerate.IsEmpty()) assert(found.feerate >= init_best.feerate);
648 : : // Check that it is topologically valid.
649 [ + - + + ]: 11361 : for (auto i : found.transactions) {
650 [ - + ]: 6699 : assert(found.transactions.IsSupersetOf(depgraph.Ancestors(i) & todo));
651 : : }
652 : :
653 : : // At most 2^(N-1) iterations can be required: the maximum number of non-empty topological
654 : : // subsets a (connected) cluster with N transactions can have. Even when the cluster is no
655 : : // longer connected after removing certain transactions, this holds, because the connected
656 : : // components are searched separately.
657 [ - + ]: 2331 : assert(iterations_done <= (uint64_t{1} << (todo.Count() - 1)));
658 : : // Additionally, test that no more than sqrt(2^N)+1 iterations are required. This is just
659 : : // an empirical bound that seems to hold, without proof. Still, add a test for it so we
660 : : // can learn about counterexamples if they exist.
661 [ + + + - ]: 2331 : if (iterations_done >= 1 && todo.Count() <= 63) {
662 [ + - ]: 1642 : Assume((iterations_done - 1) * (iterations_done - 1) <= uint64_t{1} << todo.Count());
663 : : }
664 : :
665 : : // Perform quality checks only if SearchCandidateFinder claims an optimal result.
666 [ + + ]: 2331 : if (iterations_done < max_iterations) {
667 : : // Optimal sets are always connected.
668 [ - + ]: 1424 : assert(depgraph.IsConnected(found.transactions));
669 : :
670 : : // Compare with SimpleCandidateFinder.
671 [ - + ]: 1424 : auto [simple, simple_iters] = smp_finder.FindCandidateSet(MAX_SIMPLE_ITERATIONS);
672 [ - + ]: 1424 : assert(found.feerate >= simple.feerate);
673 [ + + ]: 1424 : if (simple_iters < MAX_SIMPLE_ITERATIONS) {
674 [ + - ]: 1410 : assert(found.feerate == simple.feerate);
675 : : }
676 : :
677 : : // Compare with AncestorCandidateFinder;
678 : 1424 : auto anc = anc_finder.FindCandidateSet();
679 [ - + ]: 1424 : assert(found.feerate >= anc.feerate);
680 : :
681 : : // Compare with ExhaustiveCandidateFinder. This quickly gets computationally expensive
682 : : // for large clusters (O(2^n)), so only do it for sufficiently small ones.
683 [ + + ]: 1424 : if (todo.Count() <= 12) {
684 : 820 : auto exhaustive = exh_finder.FindCandidateSet();
685 [ + - ]: 820 : assert(exhaustive.feerate == found.feerate);
686 : : // Also compare ExhaustiveCandidateFinder with SimpleCandidateFinder (this is
687 : : // primarily a test for SimpleCandidateFinder's correctness).
688 [ - + ]: 820 : assert(exhaustive.feerate >= simple.feerate);
689 [ + - ]: 820 : if (simple_iters < MAX_SIMPLE_ITERATIONS) {
690 [ + - ]: 820 : assert(exhaustive.feerate == simple.feerate);
691 : : }
692 : : }
693 : : }
694 : :
695 : : // Find a topologically valid subset of transactions to remove from the graph.
696 [ + - ]: 2331 : auto del_set = ReadTopologicalSet(depgraph, todo, reader);
697 : : // If we did not find anything, use found itself, because we should remove something.
698 [ + + ]: 2331 : if (del_set.None()) del_set = found.transactions;
699 : 2331 : todo -= del_set;
700 : 2331 : src_finder.MarkDone(del_set);
701 : 2331 : smp_finder.MarkDone(del_set);
702 : 2331 : exh_finder.MarkDone(del_set);
703 : 2331 : anc_finder.MarkDone(del_set);
704 : : }
705 : :
706 [ - + ]: 331 : assert(src_finder.AllDone());
707 [ - + ]: 331 : assert(smp_finder.AllDone());
708 [ - + ]: 331 : assert(exh_finder.AllDone());
709 [ - + ]: 331 : assert(anc_finder.AllDone());
710 [ - + ]: 331 : assert(anc_finder.NumRemaining() == 0);
711 : 331 : }
712 : :
713 [ + - ]: 548 : FUZZ_TARGET(clusterlin_linearization_chunking)
714 : : {
715 : : // Verify the behavior of LinearizationChunking.
716 : :
717 : : // Retrieve a depgraph from the fuzz input.
718 [ + - ]: 136 : SpanReader reader(buffer);
719 : 136 : DepGraph<TestBitSet> depgraph;
720 : 136 : try {
721 [ + - ]: 136 : reader >> Using<DepGraphFormatter>(depgraph);
722 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
723 : :
724 : : // Retrieve a topologically-valid subset of depgraph.
725 : 136 : auto todo = depgraph.Positions();
726 [ + - ]: 136 : auto subset = SetInfo(depgraph, ReadTopologicalSet(depgraph, todo, reader));
727 : :
728 : : // Retrieve a valid linearization for depgraph.
729 [ + - ]: 136 : auto linearization = ReadLinearization(depgraph, reader);
730 : :
731 : : // Construct a LinearizationChunking object, initially for the whole linearization.
732 : 136 : LinearizationChunking chunking(depgraph, linearization);
733 : :
734 : : // Incrementally remove transactions from the chunking object, and check various properties at
735 : : // every step.
736 [ + + ]: 1664 : while (todo.Any()) {
737 [ - + ]: 1392 : assert(chunking.NumChunksLeft() > 0);
738 : :
739 : : // Construct linearization with just todo.
740 : 1392 : std::vector<ClusterIndex> linearization_left;
741 [ + + ]: 33637 : for (auto i : linearization) {
742 [ + + + - ]: 32245 : if (todo[i]) linearization_left.push_back(i);
743 : : }
744 : :
745 : : // Compute the chunking for linearization_left.
746 : 1392 : auto chunking_left = ChunkLinearization(depgraph, linearization_left);
747 : :
748 : : // Verify that it matches the feerates of the chunks of chunking.
749 [ - + ]: 1392 : assert(chunking.NumChunksLeft() == chunking_left.size());
750 [ + + ]: 8129 : for (ClusterIndex i = 0; i < chunking.NumChunksLeft(); ++i) {
751 [ + - ]: 13474 : assert(chunking.GetChunk(i).feerate == chunking_left[i]);
752 : : }
753 : :
754 : : // Check consistency of chunking.
755 : 1392 : TestBitSet combined;
756 [ + + ]: 8129 : for (ClusterIndex i = 0; i < chunking.NumChunksLeft(); ++i) {
757 : 6737 : const auto& chunk_info = chunking.GetChunk(i);
758 : : // Chunks must be non-empty.
759 [ - + ]: 6737 : assert(chunk_info.transactions.Any());
760 : : // Chunk feerates must be monotonically non-increasing.
761 [ + + - + ]: 6737 : if (i > 0) assert(!(chunk_info.feerate >> chunking.GetChunk(i - 1).feerate));
762 : : // Chunks must be a subset of what is left of the linearization.
763 [ - + ]: 6737 : assert(chunk_info.transactions.IsSubsetOf(todo));
764 : : // Chunks' claimed feerates must match their transactions' aggregate feerate.
765 [ + - ]: 6737 : assert(depgraph.FeeRate(chunk_info.transactions) == chunk_info.feerate);
766 : : // Chunks must be the highest-feerate remaining prefix.
767 : 6737 : SetInfo<TestBitSet> accumulator, best;
768 [ + + ]: 186828 : for (auto j : linearization) {
769 [ + + + + ]: 180091 : if (todo[j] && !combined[j]) {
770 : 63271 : accumulator.Set(depgraph, j);
771 [ + + + + ]: 63271 : if (best.feerate.IsEmpty() || accumulator.feerate > best.feerate) {
772 : 12502 : best = accumulator;
773 : : }
774 : : }
775 : : }
776 [ - + ]: 6737 : assert(best.transactions == chunk_info.transactions);
777 [ + - ]: 6737 : assert(best.feerate == chunk_info.feerate);
778 : : // Chunks cannot overlap.
779 [ - + ]: 6737 : assert(!chunk_info.transactions.Overlaps(combined));
780 [ + - ]: 6737 : combined |= chunk_info.transactions;
781 : : // Chunks must be topological.
782 [ + - + + ]: 29605 : for (auto idx : chunk_info.transactions) {
783 [ - + ]: 16131 : assert((depgraph.Ancestors(idx) & todo).IsSubsetOf(combined));
784 : : }
785 : : }
786 [ - + ]: 1392 : assert(combined == todo);
787 : :
788 : : // Verify the expected properties of LinearizationChunking::IntersectPrefixes:
789 : 1392 : auto intersect = chunking.IntersectPrefixes(subset);
790 : : // - Intersecting again doesn't change the result.
791 [ + - ]: 1392 : assert(chunking.IntersectPrefixes(intersect) == intersect);
792 : : // - The intersection is topological.
793 : 1392 : TestBitSet intersect_anc;
794 [ + + + + ]: 5156 : for (auto idx : intersect.transactions) {
795 : 2957 : intersect_anc |= (depgraph.Ancestors(idx) & todo);
796 : : }
797 [ - + ]: 1392 : assert(intersect.transactions == intersect_anc);
798 : : // - The claimed intersection feerate matches its transactions.
799 [ + - ]: 1392 : assert(intersect.feerate == depgraph.FeeRate(intersect.transactions));
800 : : // - The intersection may only be empty if its input is empty.
801 [ - + ]: 1392 : assert(intersect.transactions.Any() == subset.transactions.Any());
802 : : // - The intersection feerate must be as high as the input.
803 [ - + ]: 1392 : assert(intersect.feerate >= subset.feerate);
804 : : // - No non-empty intersection between the intersection and a prefix of the chunks of the
805 : : // remainder of the linearization may be better than the intersection.
806 : 1392 : TestBitSet prefix;
807 [ + + ]: 8129 : for (ClusterIndex i = 0; i < chunking.NumChunksLeft(); ++i) {
808 : 6737 : prefix |= chunking.GetChunk(i).transactions;
809 : 6737 : auto reintersect = SetInfo(depgraph, prefix & intersect.transactions);
810 [ + + ]: 6737 : if (!reintersect.feerate.IsEmpty()) {
811 [ - + ]: 3933 : assert(reintersect.feerate <= intersect.feerate);
812 : : }
813 : : }
814 : :
815 : : // Find a subset to remove from linearization.
816 [ + - ]: 1392 : auto done = ReadTopologicalSet(depgraph, todo, reader);
817 [ + + ]: 1392 : if (done.None()) {
818 : : // We need to remove a non-empty subset, so fall back to the unlinearized ancestors of
819 : : // the first transaction in todo if done is empty.
820 : 1203 : done = depgraph.Ancestors(todo.First()) & todo;
821 : : }
822 : 1392 : todo -= done;
823 : 1392 : chunking.MarkDone(done);
824 : 1392 : subset = SetInfo(depgraph, subset.transactions - done);
825 : 1392 : }
826 : :
827 [ - + ]: 136 : assert(chunking.NumChunksLeft() == 0);
828 : 136 : }
829 : :
830 [ + - ]: 858 : FUZZ_TARGET(clusterlin_linearize)
831 : : {
832 : : // Verify the behavior of Linearize().
833 : :
834 : : // Retrieve an RNG seed, an iteration count, a depgraph, and whether to make it connected from
835 : : // the fuzz input.
836 [ + + ]: 446 : SpanReader reader(buffer);
837 : 446 : DepGraph<TestBitSet> depgraph;
838 : 446 : uint64_t rng_seed{0};
839 : 446 : uint64_t iter_count{0};
840 : 446 : uint8_t make_connected{1};
841 : 446 : try {
842 [ + + + - : 446 : reader >> VARINT(iter_count) >> Using<DepGraphFormatter>(depgraph) >> rng_seed >> make_connected;
+ + + + ]
843 [ - + ]: 323 : } catch (const std::ios_base::failure&) {}
844 : : // The most complicated graphs are connected ones (other ones just split up). Optionally force
845 : : // the graph to be connected.
846 [ + + + - ]: 446 : if (make_connected) MakeConnected(depgraph);
847 : :
848 : : // Optionally construct an old linearization for it.
849 : 446 : std::vector<ClusterIndex> old_linearization;
850 : 446 : {
851 : 446 : uint8_t have_old_linearization{0};
852 : 446 : try {
853 [ + + ]: 446 : reader >> have_old_linearization;
854 [ - + ]: 212 : } catch(const std::ios_base::failure&) {}
855 [ + + ]: 446 : if (have_old_linearization & 1) {
856 [ + - ]: 328 : old_linearization = ReadLinearization(depgraph, reader);
857 : 164 : SanityCheck(depgraph, old_linearization);
858 : : }
859 : : }
860 : :
861 : : // Invoke Linearize().
862 : 446 : iter_count &= 0x7ffff;
863 : 446 : auto [linearization, optimal] = Linearize(depgraph, iter_count, rng_seed, old_linearization);
864 : 446 : SanityCheck(depgraph, linearization);
865 : 446 : auto chunking = ChunkLinearization(depgraph, linearization);
866 : :
867 : : // Linearization must always be as good as the old one, if provided.
868 [ + + ]: 446 : if (!old_linearization.empty()) {
869 : 162 : auto old_chunking = ChunkLinearization(depgraph, old_linearization);
870 [ + - ]: 162 : auto cmp = CompareChunks(chunking, old_chunking);
871 [ - + ]: 162 : assert(cmp >= 0);
872 : 162 : }
873 : :
874 : : // If the iteration count is sufficiently high, an optimal linearization must be found.
875 : : // Each linearization step can use up to 2^(k-1) iterations, with steps k=1..n. That sum is
876 : : // 2^n - 1.
877 [ + + ]: 446 : const uint64_t n = depgraph.TxCount();
878 [ + + + + ]: 446 : if (n <= 19 && iter_count > (uint64_t{1} << n)) {
879 [ - + ]: 63 : assert(optimal);
880 : : }
881 : : // Additionally, if the assumption of sqrt(2^k)+1 iterations per step holds, plus ceil(k/4)
882 : : // start-up cost per step, plus ceil(n^2/64) start-up cost overall, we can compute the upper
883 : : // bound for a whole linearization (summing for k=1..n) using the Python expression
884 : : // [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)]:
885 : 446 : static constexpr uint64_t MAX_OPTIMAL_ITERS[] = {
886 : : 0, 4, 8, 12, 18, 26, 37, 51, 70, 97, 133, 182, 251, 346, 480, 666, 927, 1296, 1815, 2545,
887 : : 3576, 5031, 7087, 9991, 14094, 19895, 28096, 39690, 56083, 79263, 112041, 158391, 223936,
888 : : 316629, 447712
889 : : };
890 [ + - + + ]: 446 : if (n < std::size(MAX_OPTIMAL_ITERS) && iter_count >= MAX_OPTIMAL_ITERS[n]) {
891 [ + - ]: 137 : Assume(optimal);
892 : : }
893 : :
894 : : // If Linearize claims optimal result, run quality tests.
895 [ + + ]: 446 : if (optimal) {
896 : : // It must be as good as SimpleLinearize.
897 : 315 : auto [simple_linearization, simple_optimal] = SimpleLinearize(depgraph, MAX_SIMPLE_ITERATIONS);
898 : 315 : SanityCheck(depgraph, simple_linearization);
899 : 315 : auto simple_chunking = ChunkLinearization(depgraph, simple_linearization);
900 [ + - ]: 315 : auto cmp = CompareChunks(chunking, simple_chunking);
901 [ - + ]: 315 : assert(cmp >= 0);
902 : : // If SimpleLinearize finds the optimal result too, they must be equal (if not,
903 : : // SimpleLinearize is broken).
904 [ + + - + ]: 315 : if (simple_optimal) assert(cmp == 0);
905 : :
906 : : // Only for very small clusters, test every topologically-valid permutation.
907 [ + + ]: 315 : if (depgraph.TxCount() <= 7) {
908 : 68 : std::vector<ClusterIndex> perm_linearization;
909 [ + + + - : 385 : for (ClusterIndex i : depgraph.Positions()) perm_linearization.push_back(i);
+ + ]
910 : : // Iterate over all valid permutations.
911 : 80951 : do {
912 : : // Determine whether perm_linearization is topological.
913 : 80951 : TestBitSet perm_done;
914 : 80951 : bool perm_is_topo{true};
915 [ + + ]: 135644 : for (auto i : perm_linearization) {
916 : 133961 : perm_done.Set(i);
917 [ + + ]: 133961 : if (!depgraph.Ancestors(i).IsSubsetOf(perm_done)) {
918 : : perm_is_topo = false;
919 : : break;
920 : : }
921 : : }
922 : : // If so, verify that the obtained linearization is as good as the permutation.
923 [ + + ]: 80951 : if (perm_is_topo) {
924 : 1683 : auto perm_chunking = ChunkLinearization(depgraph, perm_linearization);
925 [ + - ]: 1683 : auto cmp = CompareChunks(chunking, perm_chunking);
926 [ - + ]: 1683 : assert(cmp >= 0);
927 : 1683 : }
928 [ + + ]: 80951 : } while(std::next_permutation(perm_linearization.begin(), perm_linearization.end()));
929 : 68 : }
930 : 315 : }
931 : 446 : }
932 : :
933 [ + - ]: 515 : FUZZ_TARGET(clusterlin_postlinearize)
934 : : {
935 : : // Verify expected properties of PostLinearize() on arbitrary linearizations.
936 : :
937 : : // Retrieve a depgraph from the fuzz input.
938 [ + - ]: 103 : SpanReader reader(buffer);
939 : 103 : DepGraph<TestBitSet> depgraph;
940 : 103 : try {
941 [ + - ]: 103 : reader >> Using<DepGraphFormatter>(depgraph);
942 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
943 : :
944 : : // Retrieve a linearization from the fuzz input.
945 : 103 : std::vector<ClusterIndex> linearization;
946 [ + - ]: 206 : linearization = ReadLinearization(depgraph, reader);
947 : 103 : SanityCheck(depgraph, linearization);
948 : :
949 : : // Produce a post-processed version.
950 [ + - ]: 103 : auto post_linearization = linearization;
951 [ + - ]: 103 : PostLinearize(depgraph, post_linearization);
952 : 103 : SanityCheck(depgraph, post_linearization);
953 : :
954 : : // Compare diagrams: post-linearization cannot worsen anywhere.
955 : 103 : auto chunking = ChunkLinearization(depgraph, linearization);
956 : 103 : auto post_chunking = ChunkLinearization(depgraph, post_linearization);
957 [ + - ]: 103 : auto cmp = CompareChunks(post_chunking, chunking);
958 [ - + ]: 103 : assert(cmp >= 0);
959 : :
960 : : // Run again, things can keep improving (and never get worse)
961 [ + - ]: 103 : auto post_post_linearization = post_linearization;
962 [ + - ]: 103 : PostLinearize(depgraph, post_post_linearization);
963 : 103 : SanityCheck(depgraph, post_post_linearization);
964 : 103 : auto post_post_chunking = ChunkLinearization(depgraph, post_post_linearization);
965 [ + - ]: 103 : cmp = CompareChunks(post_post_chunking, post_chunking);
966 [ - + ]: 103 : assert(cmp >= 0);
967 : :
968 : : // The chunks that come out of postlinearizing are always connected.
969 : 103 : LinearizationChunking linchunking(depgraph, post_linearization);
970 [ + + ]: 1054 : while (linchunking.NumChunksLeft()) {
971 [ - + ]: 848 : assert(depgraph.IsConnected(linchunking.GetChunk(0).transactions));
972 : 848 : linchunking.MarkDone(linchunking.GetChunk(0).transactions);
973 : : }
974 : 103 : }
975 : :
976 [ + - ]: 782 : FUZZ_TARGET(clusterlin_postlinearize_tree)
977 : : {
978 : : // Verify expected properties of PostLinearize() on linearizations of graphs that form either
979 : : // an upright or reverse tree structure.
980 : :
981 : : // Construct a direction, RNG seed, and an arbitrary graph from the fuzz input.
982 [ + - ]: 370 : SpanReader reader(buffer);
983 : 370 : uint64_t rng_seed{0};
984 : 370 : DepGraph<TestBitSet> depgraph_gen;
985 : 370 : uint8_t direction{0};
986 : 370 : try {
987 [ + - + + : 370 : reader >> direction >> rng_seed >> Using<DepGraphFormatter>(depgraph_gen);
+ - ]
988 [ - + ]: 1 : } catch (const std::ios_base::failure&) {}
989 : :
990 : : // Now construct a new graph, copying the nodes, but leaving only the first parent (even
991 : : // direction) or the first child (odd direction).
992 : 370 : DepGraph<TestBitSet> depgraph_tree;
993 [ + + ]: 11274 : for (ClusterIndex i = 0; i < depgraph_gen.PositionRange(); ++i) {
994 [ + + ]: 10904 : if (depgraph_gen.Positions()[i]) {
995 : 8863 : depgraph_tree.AddTransaction(depgraph_gen.FeeRate(i));
996 : : } else {
997 : : // For holes, add a dummy transaction which is deleted below, so that non-hole
998 : : // transactions retain their position.
999 : 2041 : depgraph_tree.AddTransaction(FeeFrac{});
1000 : : }
1001 : : }
1002 : 370 : depgraph_tree.RemoveTransactions(TestBitSet::Fill(depgraph_gen.PositionRange()) - depgraph_gen.Positions());
1003 : :
1004 [ + + ]: 370 : if (direction & 1) {
1005 [ + + ]: 5814 : for (ClusterIndex i = 0; i < depgraph_gen.TxCount(); ++i) {
1006 : 5587 : auto children = depgraph_gen.GetReducedChildren(i);
1007 [ + + ]: 5587 : if (children.Any()) {
1008 : 3787 : depgraph_tree.AddDependencies(TestBitSet::Singleton(i), children.First());
1009 : : }
1010 : : }
1011 : : } else {
1012 [ + + ]: 3419 : for (ClusterIndex i = 0; i < depgraph_gen.TxCount(); ++i) {
1013 : 3276 : auto parents = depgraph_gen.GetReducedParents(i);
1014 [ + + ]: 3276 : if (parents.Any()) {
1015 : 1286 : depgraph_tree.AddDependencies(TestBitSet::Singleton(parents.First()), i);
1016 : : }
1017 : : }
1018 : : }
1019 : :
1020 : : // Retrieve a linearization from the fuzz input.
1021 : 370 : std::vector<ClusterIndex> linearization;
1022 [ + - ]: 740 : linearization = ReadLinearization(depgraph_tree, reader);
1023 : 370 : SanityCheck(depgraph_tree, linearization);
1024 : :
1025 : : // Produce a postlinearized version.
1026 [ + - ]: 370 : auto post_linearization = linearization;
1027 [ + - ]: 370 : PostLinearize(depgraph_tree, post_linearization);
1028 : 370 : SanityCheck(depgraph_tree, post_linearization);
1029 : :
1030 : : // Compare diagrams.
1031 : 370 : auto chunking = ChunkLinearization(depgraph_tree, linearization);
1032 : 370 : auto post_chunking = ChunkLinearization(depgraph_tree, post_linearization);
1033 [ + - ]: 370 : auto cmp = CompareChunks(post_chunking, chunking);
1034 [ - + ]: 370 : assert(cmp >= 0);
1035 : :
1036 : : // Verify that post-linearizing again does not change the diagram. The result must be identical
1037 : : // as post_linearization ought to be optimal already with a tree-structured graph.
1038 [ + - ]: 370 : auto post_post_linearization = post_linearization;
1039 [ + - ]: 370 : PostLinearize(depgraph_tree, post_linearization);
1040 : 370 : SanityCheck(depgraph_tree, post_linearization);
1041 : 370 : auto post_post_chunking = ChunkLinearization(depgraph_tree, post_post_linearization);
1042 [ + - ]: 370 : auto cmp_post = CompareChunks(post_post_chunking, post_chunking);
1043 [ - + ]: 370 : assert(cmp_post == 0);
1044 : :
1045 : : // Try to find an even better linearization directly. This must not change the diagram for the
1046 : : // same reason.
1047 : 370 : auto [opt_linearization, _optimal] = Linearize(depgraph_tree, 100000, rng_seed, post_linearization);
1048 : 370 : auto opt_chunking = ChunkLinearization(depgraph_tree, opt_linearization);
1049 [ + - ]: 370 : auto cmp_opt = CompareChunks(opt_chunking, post_chunking);
1050 [ - + ]: 370 : assert(cmp_opt == 0);
1051 : 370 : }
1052 : :
1053 [ + - ]: 519 : FUZZ_TARGET(clusterlin_postlinearize_moved_leaf)
1054 : : {
1055 : : // Verify that taking an existing linearization, and moving a leaf to the back, potentially
1056 : : // increasing its fee, and then post-linearizing, results in something as good as the
1057 : : // original. This guarantees that in an RBF that replaces a transaction with one of the same
1058 : : // size but higher fee, applying the "remove conflicts, append new transaction, postlinearize"
1059 : : // process will never worsen linearization quality.
1060 : :
1061 : : // Construct an arbitrary graph and a fee from the fuzz input.
1062 [ + - ]: 107 : SpanReader reader(buffer);
1063 : 107 : DepGraph<TestBitSet> depgraph;
1064 : 107 : int32_t fee_inc{0};
1065 : 107 : try {
1066 : 107 : uint64_t fee_inc_code;
1067 [ + - + + ]: 107 : reader >> Using<DepGraphFormatter>(depgraph) >> VARINT(fee_inc_code);
1068 : 41 : fee_inc = fee_inc_code & 0x3ffff;
1069 [ - + ]: 66 : } catch (const std::ios_base::failure&) {}
1070 [ + + ]: 107 : if (depgraph.TxCount() == 0) return;
1071 : :
1072 : : // Retrieve two linearizations from the fuzz input.
1073 [ + - ]: 98 : auto lin = ReadLinearization(depgraph, reader);
1074 [ + - ]: 98 : auto lin_leaf = ReadLinearization(depgraph, reader);
1075 : :
1076 : : // Construct a linearization identical to lin, but with the tail end of lin_leaf moved to the
1077 : : // back.
1078 : 98 : std::vector<ClusterIndex> lin_moved;
1079 [ + + ]: 1408 : for (auto i : lin) {
1080 [ + + + - ]: 1310 : if (i != lin_leaf.back()) lin_moved.push_back(i);
1081 : : }
1082 [ + - ]: 98 : lin_moved.push_back(lin_leaf.back());
1083 : :
1084 : : // Postlinearize lin_moved.
1085 [ + - ]: 98 : PostLinearize(depgraph, lin_moved);
1086 : 98 : SanityCheck(depgraph, lin_moved);
1087 : :
1088 : : // Compare diagrams (applying the fee delta after computing the old one).
1089 : 98 : auto old_chunking = ChunkLinearization(depgraph, lin);
1090 : 98 : depgraph.FeeRate(lin_leaf.back()).fee += fee_inc;
1091 : 98 : auto new_chunking = ChunkLinearization(depgraph, lin_moved);
1092 [ + - ]: 98 : auto cmp = CompareChunks(new_chunking, old_chunking);
1093 [ - + ]: 98 : assert(cmp >= 0);
1094 : 107 : }
1095 : :
1096 [ + - ]: 632 : FUZZ_TARGET(clusterlin_merge)
1097 : : {
1098 : : // Construct an arbitrary graph from the fuzz input.
1099 [ + - ]: 220 : SpanReader reader(buffer);
1100 : 220 : DepGraph<TestBitSet> depgraph;
1101 : 220 : try {
1102 [ + - ]: 220 : reader >> Using<DepGraphFormatter>(depgraph);
1103 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
1104 : :
1105 : : // Retrieve two linearizations from the fuzz input.
1106 [ + - ]: 220 : auto lin1 = ReadLinearization(depgraph, reader);
1107 [ + - ]: 220 : auto lin2 = ReadLinearization(depgraph, reader);
1108 : :
1109 : : // Merge the two.
1110 [ + - ]: 220 : auto lin_merged = MergeLinearizations(depgraph, lin1, lin2);
1111 : :
1112 : : // Compute chunkings and compare.
1113 : 220 : auto chunking1 = ChunkLinearization(depgraph, lin1);
1114 : 220 : auto chunking2 = ChunkLinearization(depgraph, lin2);
1115 : 220 : auto chunking_merged = ChunkLinearization(depgraph, lin_merged);
1116 [ + - ]: 220 : auto cmp1 = CompareChunks(chunking_merged, chunking1);
1117 [ - + ]: 220 : assert(cmp1 >= 0);
1118 [ + - ]: 220 : auto cmp2 = CompareChunks(chunking_merged, chunking2);
1119 [ - + ]: 220 : assert(cmp2 >= 0);
1120 : 220 : }
|
