Branch data Line data Source code
1 : : // Copyright (c) The Bitcoin Core developers
2 : : // Distributed under the MIT software license, see the accompanying
3 : : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 : :
5 : : #include <cluster_linearize.h>
6 : : #include <random.h>
7 : : #include <serialize.h>
8 : : #include <streams.h>
9 : : #include <test/fuzz/FuzzedDataProvider.h>
10 : : #include <test/fuzz/fuzz.h>
11 : : #include <test/util/cluster_linearize.h>
12 : : #include <util/bitset.h>
13 : : #include <util/feefrac.h>
14 : :
15 : : #include <algorithm>
16 : : #include <cstdint>
17 : : #include <utility>
18 : : #include <vector>
19 : :
20 : : 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 : 536 : SimpleCandidateFinder(const DepGraph<SetType>& depgraph LIFETIMEBOUND) noexcept :
40 : 536 : m_depgraph(depgraph), m_todo{depgraph.Positions()} {}
41 : :
42 : : /** Remove a set of transactions from the set of to-be-linearized ones. */
43 : 3748 : void MarkDone(SetType select) noexcept { m_todo -= select; }
44 : :
45 : : /** Determine whether unlinearized transactions remain. */
46 : 2434 : 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 : 2750 : std::pair<SetInfo<SetType>, uint64_t> FindCandidateSet(uint64_t max_iterations) const noexcept
55 : : {
56 : 2750 : 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 : 2750 : std::vector<std::pair<SetType, SetType>> queue;
61 : : // Initially we have just one queue element, with the entire graph in und.
62 : 2750 : queue.emplace_back(SetType{}, m_todo);
63 : : // Best solution so far.
64 : 2750 : SetInfo best(m_depgraph, m_todo);
65 : : // Process the queue.
66 [ + + + + ]: 9831967 : while (!queue.empty() && iterations_left) {
67 : 9829217 : --iterations_left;
68 : : // Pop top element of the queue.
69 : 9829217 : auto [inc, und] = queue.back();
70 : 9829217 : queue.pop_back();
71 : : // Look for a transaction to consider adding/removing.
72 : 9829217 : bool inc_none = inc.None();
73 [ + + ]: 13929834 : 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 [ + + + + ]: 9013963 : if (inc_none || inc.Overlaps(m_depgraph.Ancestors(split))) {
78 : : // Add a queue entry with split included.
79 : 4913346 : SetInfo new_inc(m_depgraph, inc | (m_todo & m_depgraph.Ancestors(split)));
80 : 4913346 : queue.emplace_back(new_inc.transactions, und - new_inc.transactions);
81 : : // Add a queue entry with split excluded.
82 : 4913346 : queue.emplace_back(inc, und - m_depgraph.Descendants(split));
83 : : // Update statistics to account for the candidate new_inc.
84 [ + + ]: 4913346 : if (new_inc.feerate > best.feerate) best = new_inc;
85 : : break;
86 : : }
87 : : }
88 : : }
89 : 2750 : return {std::move(best), max_iterations - iterations_left};
90 : 2750 : }
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 : 281 : ExhaustiveCandidateFinder(const DepGraph<SetType>& depgraph LIFETIMEBOUND) noexcept :
110 : 281 : m_depgraph(depgraph), m_todo{depgraph.Positions()} {}
111 : :
112 : : /** Remove a set of transactions from the set of to-be-linearized ones. */
113 : 2153 : void MarkDone(SetType select) noexcept { m_todo -= select; }
114 : :
115 : : /** Determine whether unlinearized transactions remain. */
116 : 2434 : 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 : 613 : SetInfo<SetType> FindCandidateSet() const noexcept
123 : : {
124 : : // Best solution so far.
125 : 613 : SetInfo<SetType> best{m_todo, m_depgraph.FeeRate(m_todo)};
126 : : // The number of combinations to try.
127 : 613 : uint64_t limit = (uint64_t{1} << m_todo.Count()) - 1;
128 : : // Try the transitive closure of every non-empty subset of m_todo.
129 [ + + ]: 267021 : 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 : 266408 : SetType txn;
133 : 266408 : auto x_shifted{x};
134 [ + - + + ]: 3435908 : for (auto i : m_todo) {
135 [ + + ]: 2903092 : if (x_shifted & 1) txn |= m_depgraph.Ancestors(i);
136 : 2903092 : x_shifted >>= 1;
137 : : }
138 : 266408 : SetInfo cur(m_depgraph, txn & m_todo);
139 [ + + ]: 266408 : if (cur.feerate > best.feerate) best = cur;
140 : : }
141 : 613 : 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 : 255 : std::pair<std::vector<DepGraphIndex>, bool> SimpleLinearize(const DepGraph<SetType>& depgraph, uint64_t max_iterations)
153 : : {
154 : 255 : std::vector<DepGraphIndex> linearization;
155 : 255 : SimpleCandidateFinder finder(depgraph);
156 : 255 : SetType todo = depgraph.Positions();
157 : 255 : bool optimal = true;
158 [ + + ]: 1850 : while (todo.Any()) {
159 [ + + ]: 1595 : auto [candidate, iterations_done] = finder.FindCandidateSet(max_iterations);
160 [ + + ]: 1595 : if (iterations_done == max_iterations) optimal = false;
161 : 1595 : depgraph.AppendTopo(linearization, candidate.transactions);
162 : 1595 : todo -= candidate.transactions;
163 : 1595 : finder.MarkDone(candidate.transactions);
164 : 1595 : max_iterations -= iterations_done;
165 : : }
166 : 255 : return {std::move(linearization), optimal};
167 : 255 : }
168 : :
169 : : /** Stitch connected components together in a DepGraph, guaranteeing its corresponding cluster is connected. */
170 : : template<typename BS>
171 : 737 : void MakeConnected(DepGraph<BS>& depgraph)
172 : : {
173 : 737 : auto todo = depgraph.Positions();
174 : 737 : auto comp = depgraph.FindConnectedComponent(todo);
175 : 737 : Assume(depgraph.IsConnected(comp));
176 : 737 : todo -= comp;
177 [ + + ]: 8822 : while (todo.Any()) {
178 : 8085 : auto nextcomp = depgraph.FindConnectedComponent(todo);
179 : 8085 : Assume(depgraph.IsConnected(nextcomp));
180 : 8085 : depgraph.AddDependencies(BS::Singleton(comp.Last()), nextcomp.First());
181 : 8085 : todo -= nextcomp;
182 : 8085 : comp = nextcomp;
183 : : }
184 : 737 : }
185 : :
186 : : /** Given a dependency graph, and a todo set, read a topological subset of todo from reader. */
187 : : template<typename SetType>
188 : 6668 : SetType ReadTopologicalSet(const DepGraph<SetType>& depgraph, const SetType& todo, SpanReader& reader)
189 : : {
190 [ + + ]: 6668 : uint64_t mask{0};
191 : : try {
192 [ + + ]: 6668 : reader >> VARINT(mask);
193 [ - + ]: 4109 : } catch(const std::ios_base::failure&) {}
194 : 6668 : SetType ret;
195 [ + + + + ]: 101665 : for (auto i : todo) {
196 [ + + ]: 88334 : if (!ret[i]) {
197 [ + + ]: 86742 : if (mask & 1) ret |= depgraph.Ancestors(i);
198 : 86742 : mask >>= 1;
199 : : }
200 : : }
201 : 6668 : 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 : 1294 : std::vector<DepGraphIndex> ReadLinearization(const DepGraph<BS>& depgraph, SpanReader& reader)
207 : : {
208 : 1294 : std::vector<DepGraphIndex> linearization;
209 : 1294 : TestBitSet todo = depgraph.Positions();
210 : : // In every iteration one topologically-valid transaction is appended to linearization.
211 [ + + ]: 25587 : while (todo.Any()) {
212 : : // Compute the set of transactions with no not-yet-included ancestors.
213 : 22999 : TestBitSet potential_next;
214 [ + + ]: 331499 : for (auto j : todo) {
215 [ + + ]: 494362 : if ((depgraph.Ancestors(j) & todo) == TestBitSet::Singleton(j)) {
216 : 185862 : potential_next.Set(j);
217 : : }
218 : : }
219 : : // There must always be one (otherwise there is a cycle in the graph).
220 [ - + ]: 22999 : assert(potential_next.Any());
221 : : // Read a number from reader, and interpret it as index into potential_next.
222 [ + + ]: 22999 : uint64_t idx{0};
223 : : try {
224 [ + + + - ]: 45998 : reader >> VARINT(idx);
225 [ - + ]: 18108 : } catch (const std::ios_base::failure&) {}
226 : 22999 : idx %= potential_next.Count();
227 : : // Find out which transaction that corresponds to.
228 [ + - + - ]: 60376 : for (auto j : potential_next) {
229 [ + + ]: 37377 : if (idx == 0) {
230 : : // When found, add it to linearization and remove it from todo.
231 [ + - ]: 22999 : linearization.push_back(j);
232 [ - + ]: 22999 : assert(todo[j]);
233 : 22999 : todo.Reset(j);
234 : 22999 : break;
235 : : }
236 : 14378 : --idx;
237 : : }
238 : : }
239 : 1294 : return linearization;
240 : 0 : }
241 : :
242 : : } // namespace
243 : :
244 [ + - ]: 633 : FUZZ_TARGET(clusterlin_depgraph_sim)
245 : : {
246 : : // Simulation test to verify the full behavior of DepGraph.
247 : :
248 : 189 : FuzzedDataProvider provider(buffer.data(), buffer.size());
249 : :
250 : : /** Real DepGraph being tested. */
251 : 189 : 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 : 189 : std::array<std::optional<std::pair<FeeFrac, TestBitSet>>, TestBitSet::Size()> sim;
255 : : /** The number of non-nullopt position in sim. */
256 : 189 : DepGraphIndex num_tx_sim{0};
257 : :
258 : : /** Read a valid index of a transaction from the provider. */
259 : 7674 : auto idx_fn = [&]() {
260 : 7485 : auto offset = provider.ConsumeIntegralInRange<DepGraphIndex>(0, num_tx_sim - 1);
261 [ + - ]: 49052 : for (DepGraphIndex i = 0; i < sim.size(); ++i) {
262 [ + + ]: 49052 : if (!sim[i].has_value()) continue;
263 [ + + ]: 43098 : if (offset == 0) return i;
264 : 35613 : --offset;
265 : : }
266 : 0 : assert(false);
267 : : return DepGraphIndex(-1);
268 : 189 : };
269 : :
270 : : /** Read a valid subset of the transactions from the provider. */
271 : 7674 : auto subset_fn = [&]() {
272 : 7485 : auto range = (uint64_t{1} << num_tx_sim) - 1;
273 : 7485 : const auto mask = provider.ConsumeIntegralInRange<uint64_t>(0, range);
274 : 7485 : auto mask_shifted = mask;
275 : 7485 : TestBitSet subset;
276 [ + + ]: 247005 : for (DepGraphIndex i = 0; i < sim.size(); ++i) {
277 [ + + ]: 239520 : if (!sim[i].has_value()) continue;
278 [ + + ]: 128517 : if (mask_shifted & 1) {
279 : 38126 : subset.Set(i);
280 : : }
281 : 128517 : mask_shifted >>= 1;
282 : : }
283 [ - + ]: 7485 : assert(mask_shifted == 0);
284 : 7485 : return subset;
285 : 189 : };
286 : :
287 : : /** Read any set of transactions from the provider (including unused positions). */
288 : 6996 : auto set_fn = [&]() {
289 : 6807 : auto range = (uint64_t{1} << sim.size()) - 1;
290 : 6807 : const auto mask = provider.ConsumeIntegralInRange<uint64_t>(0, range);
291 : 6807 : TestBitSet set;
292 [ + + ]: 224631 : for (DepGraphIndex i = 0; i < sim.size(); ++i) {
293 [ + + ]: 217824 : if ((mask >> i) & 1) {
294 : 82561 : set.Set(i);
295 : : }
296 : : }
297 : 6807 : return set;
298 : 189 : };
299 : :
300 : : /** Propagate ancestor information in sim. */
301 : 7185 : auto anc_update_fn = [&]() {
302 : 7643 : while (true) {
303 : 7643 : bool updates{false};
304 [ + + ]: 252219 : for (DepGraphIndex chl = 0; chl < sim.size(); ++chl) {
305 [ + + ]: 244576 : if (!sim[chl].has_value()) continue;
306 [ + - + + ]: 395220 : for (auto par : sim[chl]->second) {
307 [ + + ]: 209666 : if (!sim[chl]->second.IsSupersetOf(sim[par]->second)) {
308 : 2330 : sim[chl]->second |= sim[par]->second;
309 : 2330 : updates = true;
310 : : }
311 : : }
312 : : }
313 [ + + ]: 7643 : if (!updates) break;
314 : : }
315 : 7185 : };
316 : :
317 : : /** Compare the state of transaction i in the simulation with the real one. */
318 : 88798 : auto check_fn = [&](DepGraphIndex i) {
319 : : // Compare used positions.
320 [ - + ]: 88609 : assert(real.Positions()[i] == sim[i].has_value());
321 [ + + ]: 88609 : if (sim[i].has_value()) {
322 : : // Compare feerate.
323 [ + - ]: 10318 : 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 [ - + ]: 10318 : assert(real.Ancestors(i) == sim[i]->second);
327 : : }
328 : 88798 : };
329 : :
330 [ + + + + ]: 24799 : LIMITED_WHILE(provider.remaining_bytes() > 0, 1000) {
331 : 24610 : uint8_t command = provider.ConsumeIntegral<uint8_t>();
332 [ + + + + : 24610 : if (num_tx_sim == 0 || ((command % 3) <= 0 && num_tx_sim < TestBitSet::Size())) {
+ + ]
333 : : // AddTransaction.
334 : 10318 : auto fee = provider.ConsumeIntegralInRange<int64_t>(-0x8000000000000, 0x7ffffffffffff);
335 : 10318 : auto size = provider.ConsumeIntegralInRange<int32_t>(1, 0x3fffff);
336 : 10318 : FeeFrac feerate{fee, size};
337 : : // Apply to DepGraph.
338 : 10318 : auto idx = real.AddTransaction(feerate);
339 : : // Verify that the returned index is correct.
340 [ - + ]: 10318 : assert(!sim[idx].has_value());
341 [ + - ]: 145948 : for (DepGraphIndex i = 0; i < TestBitSet::Size(); ++i) {
342 [ + + ]: 145948 : if (!sim[i].has_value()) {
343 [ - + ]: 10318 : assert(idx == i);
344 : : break;
345 : : }
346 : : }
347 : : // Update sim.
348 [ - + ]: 10318 : sim[idx] = {feerate, TestBitSet::Singleton(idx)};
349 : 10318 : ++num_tx_sim;
350 : 10318 : continue;
351 : 10318 : }
352 [ + + ]: 14292 : if ((command % 3) <= 1 && num_tx_sim > 0) {
353 : : // AddDependencies.
354 : 7485 : DepGraphIndex child = idx_fn();
355 : 7485 : auto parents = subset_fn();
356 : : // Apply to DepGraph.
357 : 7485 : real.AddDependencies(parents, child);
358 : : // Apply to sim.
359 : 7485 : sim[child]->second |= parents;
360 : 7485 : continue;
361 : 7485 : }
362 : 6807 : if (num_tx_sim > 0) {
363 : : // Remove transactions.
364 : 6807 : 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 : 6807 : anc_update_fn();
368 : : // Compare the state of the transactions being deleted.
369 [ + + + + ]: 95033 : for (auto i : del) check_fn(i);
370 : : // Apply to DepGraph.
371 : 6807 : real.RemoveTransactions(del);
372 : : // Apply to sim.
373 [ + + ]: 224631 : for (DepGraphIndex i = 0; i < sim.size(); ++i) {
374 [ + + ]: 217824 : if (sim[i].has_value()) {
375 [ + + ]: 75294 : if (del[i]) {
376 : 7594 : --num_tx_sim;
377 [ + - ]: 225418 : sim[i] = std::nullopt;
378 : : } else {
379 : 67700 : sim[i]->second -= del;
380 : : }
381 : : }
382 : : }
383 : 6807 : continue;
384 : 6807 : }
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 : 189 : anc_update_fn();
391 [ + + ]: 6237 : for (DepGraphIndex i = 0; i < sim.size(); ++i) check_fn(i);
392 [ - + ]: 189 : assert(real.TxCount() == num_tx_sim);
393 : : // Sanity check the result (which includes round-tripping serialization, if applicable).
394 [ + - ]: 189 : SanityCheck(real);
395 : 189 : }
396 : :
397 [ + - ]: 602 : 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 [ + - ]: 158 : SpanReader reader(buffer);
403 : 158 : DepGraph<TestBitSet> depgraph;
404 : 158 : DepGraphIndex par_code{0}, chl_code{0};
405 : 158 : try {
406 [ + - + + : 158 : reader >> Using<DepGraphFormatter>(depgraph) >> VARINT(par_code) >> VARINT(chl_code);
+ + ]
407 [ - + ]: 135 : } catch (const std::ios_base::failure&) {}
408 [ + - ]: 158 : SanityCheck(depgraph);
409 : :
410 : : // Verify the graph is a DAG.
411 [ - + ]: 158 : assert(depgraph.IsAcyclic());
412 : :
413 : : // Introduce a cycle, and then test that IsAcyclic returns false.
414 [ + + ]: 158 : if (depgraph.TxCount() < 2) return;
415 : 145 : DepGraphIndex par(0), chl(0);
416 : : // Pick any transaction of depgraph as parent.
417 [ + - ]: 145 : par_code %= depgraph.TxCount();
418 [ + - + - ]: 431 : for (auto i : depgraph.Positions()) {
419 [ + + ]: 286 : if (par_code == 0) {
420 : : par = i;
421 : : break;
422 : : }
423 : 141 : --par_code;
424 : : }
425 : : // Pick any ancestor of par (excluding itself) as child, if any.
426 [ + + ]: 145 : auto ancestors = depgraph.Ancestors(par) - TestBitSet::Singleton(par);
427 [ + + ]: 145 : if (ancestors.None()) return;
428 : 63 : chl_code %= ancestors.Count();
429 [ + - ]: 109 : for (auto i : ancestors) {
430 [ + + ]: 109 : if (chl_code == 0) {
431 : : chl = i;
432 : : break;
433 : : }
434 : 46 : --chl_code;
435 : : }
436 : : // Add the cycle-introducing dependency.
437 : 63 : depgraph.AddDependencies(TestBitSet::Singleton(par), chl);
438 : : // Check that we now detect a cycle.
439 [ - + ]: 63 : assert(!depgraph.IsAcyclic());
440 : 158 : }
441 : :
442 [ + - ]: 550 : FUZZ_TARGET(clusterlin_components)
443 : : {
444 : : // Verify the behavior of DepGraphs's FindConnectedComponent and IsConnected functions.
445 : :
446 : : // Construct a depgraph.
447 [ + - ]: 106 : SpanReader reader(buffer);
448 : 106 : DepGraph<TestBitSet> depgraph;
449 : 106 : std::vector<DepGraphIndex> linearization;
450 : 106 : try {
451 [ + - ]: 106 : reader >> Using<DepGraphFormatter>(depgraph);
452 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
453 : :
454 : 106 : TestBitSet todo = depgraph.Positions();
455 [ + + ]: 1438 : while (todo.Any()) {
456 : : // Pick a transaction in todo, or nothing.
457 : 1332 : std::optional<DepGraphIndex> picked;
458 : 1332 : {
459 : 1332 : uint64_t picked_num{0};
460 : 1332 : try {
461 [ + + ]: 1332 : reader >> VARINT(picked_num);
462 [ - + ]: 961 : } catch (const std::ios_base::failure&) {}
463 [ + + + + ]: 1332 : if (picked_num < todo.Size() && todo[picked_num]) {
464 : 138 : picked = picked_num;
465 : : }
466 : : }
467 : :
468 : : // Find a connected component inside todo, including picked if any.
469 [ + + ]: 1332 : auto component = picked ? depgraph.GetConnectedComponent(todo, *picked)
470 : 1194 : : depgraph.FindConnectedComponent(todo);
471 : :
472 : : // The component must be a subset of todo and non-empty.
473 [ - + ]: 1332 : assert(component.IsSubsetOf(todo));
474 [ - + ]: 1332 : assert(component.Any());
475 : :
476 : : // If picked was provided, the component must include it.
477 [ + + - + ]: 1332 : if (picked) assert(component[*picked]);
478 : :
479 : : // If todo is the entire graph, and the entire graph is connected, then the component must
480 : : // be the entire graph.
481 [ + + ]: 1332 : if (todo == depgraph.Positions()) {
482 [ + + - + ]: 169 : assert((component == todo) == depgraph.IsConnected());
483 : : }
484 : :
485 : : // If subset is connected, then component must match subset.
486 [ + + - + ]: 2258 : assert((component == todo) == depgraph.IsConnected(todo));
487 : :
488 : : // The component cannot have any ancestors or descendants outside of component but in todo.
489 [ + - + + ]: 10581 : for (auto i : component) {
490 [ - + ]: 7917 : assert((depgraph.Ancestors(i) & todo).IsSubsetOf(component));
491 [ - + ]: 7917 : assert((depgraph.Descendants(i) & todo).IsSubsetOf(component));
492 : : }
493 : :
494 : : // Starting from any component element, we must be able to reach every element.
495 [ + - + + ]: 10581 : for (auto i : component) {
496 : : // Start with just i as reachable.
497 : 7917 : TestBitSet reachable = TestBitSet::Singleton(i);
498 : : // Add in-todo descendants and ancestors to reachable until it does not change anymore.
499 : 59877 : while (true) {
500 : 33897 : TestBitSet new_reachable = reachable;
501 [ + - + + ]: 430257 : for (auto j : new_reachable) {
502 : 362463 : new_reachable |= depgraph.Ancestors(j) & todo;
503 : 362463 : new_reachable |= depgraph.Descendants(j) & todo;
504 : : }
505 [ + + ]: 33897 : if (new_reachable == reachable) break;
506 : 25980 : reachable = new_reachable;
507 : 25980 : }
508 : : // Verify that the result is the entire component.
509 [ - + ]: 7917 : assert(component == reachable);
510 : : }
511 : :
512 : : // Construct an arbitrary subset of todo.
513 : 1332 : uint64_t subset_bits{0};
514 : 1332 : try {
515 [ + + ]: 1332 : reader >> VARINT(subset_bits);
516 [ - + ]: 977 : } catch (const std::ios_base::failure&) {}
517 : 1332 : TestBitSet subset;
518 [ + - + + ]: 34007 : for (DepGraphIndex i : depgraph.Positions()) {
519 [ + + ]: 31343 : if (todo[i]) {
520 [ + + ]: 16212 : if (subset_bits & 1) subset.Set(i);
521 : 16212 : subset_bits >>= 1;
522 : : }
523 : : }
524 : : // Which must be non-empty.
525 [ + + ]: 1332 : if (subset.None()) subset = TestBitSet::Singleton(todo.First());
526 : : // Remove it from todo.
527 : 1332 : todo -= subset;
528 : : }
529 : :
530 : : // No components can be found in an empty subset.
531 [ - + ]: 106 : assert(depgraph.FindConnectedComponent(todo).None());
532 : 106 : }
533 : :
534 [ + - ]: 600 : FUZZ_TARGET(clusterlin_make_connected)
535 : : {
536 : : // Verify that MakeConnected makes graphs connected.
537 : :
538 [ + - ]: 156 : SpanReader reader(buffer);
539 : 156 : DepGraph<TestBitSet> depgraph;
540 : 156 : try {
541 [ + - ]: 156 : reader >> Using<DepGraphFormatter>(depgraph);
542 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
543 [ + - ]: 156 : MakeConnected(depgraph);
544 [ + - ]: 156 : SanityCheck(depgraph);
545 [ - + ]: 156 : assert(depgraph.IsConnected());
546 : 156 : }
547 : :
548 [ + - ]: 531 : FUZZ_TARGET(clusterlin_chunking)
549 : : {
550 : : // Verify the correctness of the ChunkLinearization function.
551 : :
552 : : // Construct a graph by deserializing.
553 [ + - ]: 87 : SpanReader reader(buffer);
554 : 87 : DepGraph<TestBitSet> depgraph;
555 : 87 : try {
556 [ + - ]: 87 : reader >> Using<DepGraphFormatter>(depgraph);
557 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
558 : :
559 : : // Read a valid linearization for depgraph.
560 [ + - ]: 87 : auto linearization = ReadLinearization(depgraph, reader);
561 : :
562 : : // Invoke the chunking function.
563 : 87 : auto chunking = ChunkLinearization(depgraph, linearization);
564 : :
565 : : // Verify that chunk feerates are monotonically non-increasing.
566 [ + + ]: 381 : for (size_t i = 1; i < chunking.size(); ++i) {
567 [ - + ]: 294 : assert(!(chunking[i] >> chunking[i - 1]));
568 : : }
569 : :
570 : : // Naively recompute the chunks (each is the highest-feerate prefix of what remains).
571 : 87 : auto todo = depgraph.Positions();
572 [ + + ]: 464 : for (const auto& chunk_feerate : chunking) {
573 [ - + ]: 377 : assert(todo.Any());
574 : 377 : SetInfo<TestBitSet> accumulator, best;
575 [ + + ]: 8340 : for (DepGraphIndex idx : linearization) {
576 [ + + ]: 7963 : if (todo[idx]) {
577 : 4363 : accumulator.Set(depgraph, idx);
578 [ + + + + ]: 4363 : if (best.feerate.IsEmpty() || accumulator.feerate >> best.feerate) {
579 : 782 : best = accumulator;
580 : : }
581 : : }
582 : : }
583 [ + - ]: 377 : assert(chunk_feerate == best.feerate);
584 [ - + ]: 377 : assert(best.transactions.IsSubsetOf(todo));
585 : 377 : todo -= best.transactions;
586 : : }
587 [ - + ]: 87 : assert(todo.None());
588 : 87 : }
589 : :
590 [ + - ]: 555 : FUZZ_TARGET(clusterlin_ancestor_finder)
591 : : {
592 : : // Verify that AncestorCandidateFinder works as expected.
593 : :
594 : : // Retrieve a depgraph from the fuzz input.
595 [ + - ]: 111 : SpanReader reader(buffer);
596 : 111 : DepGraph<TestBitSet> depgraph;
597 : 111 : try {
598 [ + - ]: 111 : reader >> Using<DepGraphFormatter>(depgraph);
599 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
600 : :
601 : 111 : AncestorCandidateFinder anc_finder(depgraph);
602 : 111 : auto todo = depgraph.Positions();
603 [ + + ]: 1055 : while (todo.Any()) {
604 : : // Call the ancestor finder's FindCandidateSet for what remains of the graph.
605 [ - + ]: 944 : assert(!anc_finder.AllDone());
606 [ - + ]: 944 : assert(todo.Count() == anc_finder.NumRemaining());
607 : 944 : auto best_anc = anc_finder.FindCandidateSet();
608 : : // Sanity check the result.
609 [ - + ]: 944 : assert(best_anc.transactions.Any());
610 [ - + ]: 944 : assert(best_anc.transactions.IsSubsetOf(todo));
611 [ + - ]: 944 : assert(depgraph.FeeRate(best_anc.transactions) == best_anc.feerate);
612 [ - + ]: 944 : assert(depgraph.IsConnected(best_anc.transactions));
613 : : // Check that it is topologically valid.
614 [ + - + + ]: 3892 : for (auto i : best_anc.transactions) {
615 [ - + ]: 2004 : assert((depgraph.Ancestors(i) & todo).IsSubsetOf(best_anc.transactions));
616 : : }
617 : :
618 : : // Compute all remaining ancestor sets.
619 : 944 : std::optional<SetInfo<TestBitSet>> real_best_anc;
620 [ + - + + ]: 12248 : for (auto i : todo) {
621 : 10360 : SetInfo info(depgraph, todo & depgraph.Ancestors(i));
622 [ + + + + ]: 10360 : if (!real_best_anc.has_value() || info.feerate > real_best_anc->feerate) {
623 [ + + ]: 12564 : real_best_anc = info;
624 : : }
625 : : }
626 : : // The set returned by anc_finder must equal the real best ancestor sets.
627 [ - + ]: 944 : assert(real_best_anc.has_value());
628 [ + - ]: 944 : assert(*real_best_anc == best_anc);
629 : :
630 : : // Find a topologically valid subset of transactions to remove from the graph.
631 [ + - ]: 944 : auto del_set = ReadTopologicalSet(depgraph, todo, reader);
632 : : // If we did not find anything, use best_anc itself, because we should remove something.
633 [ + + ]: 944 : if (del_set.None()) del_set = best_anc.transactions;
634 : 944 : todo -= del_set;
635 : 944 : anc_finder.MarkDone(del_set);
636 : : }
637 [ - + ]: 111 : assert(anc_finder.AllDone());
638 [ - + ]: 111 : assert(anc_finder.NumRemaining() == 0);
639 : 111 : }
640 : :
641 : : static constexpr auto MAX_SIMPLE_ITERATIONS = 300000;
642 : :
643 [ + - ]: 725 : FUZZ_TARGET(clusterlin_search_finder)
644 : : {
645 : : // Verify that SearchCandidateFinder works as expected by sanity checking the results
646 : : // and comparing with the results from SimpleCandidateFinder, ExhaustiveCandidateFinder, and
647 : : // AncestorCandidateFinder.
648 : :
649 : : // Retrieve an RNG seed, a depgraph, and whether to make it connected, from the fuzz input.
650 [ + - ]: 281 : SpanReader reader(buffer);
651 : 281 : DepGraph<TestBitSet> depgraph;
652 : 281 : uint64_t rng_seed{0};
653 : 281 : uint8_t make_connected{1};
654 : 281 : try {
655 [ + - + + : 281 : reader >> Using<DepGraphFormatter>(depgraph) >> rng_seed >> make_connected;
+ - ]
656 [ - + ]: 127 : } catch (const std::ios_base::failure&) {}
657 : : // The most complicated graphs are connected ones (other ones just split up). Optionally force
658 : : // the graph to be connected.
659 [ + + + - ]: 281 : if (make_connected) MakeConnected(depgraph);
660 : :
661 : : // Instantiate ALL the candidate finders.
662 : 281 : SearchCandidateFinder src_finder(depgraph, rng_seed);
663 : 281 : SimpleCandidateFinder smp_finder(depgraph);
664 : 281 : ExhaustiveCandidateFinder exh_finder(depgraph);
665 : 281 : AncestorCandidateFinder anc_finder(depgraph);
666 : :
667 : 281 : auto todo = depgraph.Positions();
668 [ + + ]: 2434 : while (todo.Any()) {
669 [ - + ]: 2153 : assert(!src_finder.AllDone());
670 [ - + ]: 2153 : assert(!smp_finder.AllDone());
671 [ - + ]: 2153 : assert(!exh_finder.AllDone());
672 [ - + ]: 2153 : assert(!anc_finder.AllDone());
673 [ - + ]: 2153 : assert(anc_finder.NumRemaining() == todo.Count());
674 : :
675 : : // For each iteration, read an iteration count limit from the fuzz input.
676 : 2153 : uint64_t max_iterations = 1;
677 : 2153 : try {
678 [ + + ]: 2153 : reader >> VARINT(max_iterations);
679 [ - + ]: 1075 : } catch (const std::ios_base::failure&) {}
680 : 2153 : max_iterations &= 0xfffff;
681 : :
682 : : // Read an initial subset from the fuzz input.
683 [ + - ]: 2153 : SetInfo init_best(depgraph, ReadTopologicalSet(depgraph, todo, reader));
684 : :
685 : : // Call the search finder's FindCandidateSet for what remains of the graph.
686 [ - + ]: 2153 : auto [found, iterations_done] = src_finder.FindCandidateSet(max_iterations, init_best);
687 : :
688 : : // Sanity check the result.
689 [ - + ]: 2153 : assert(iterations_done <= max_iterations);
690 [ - + ]: 2153 : assert(found.transactions.Any());
691 [ - + ]: 2153 : assert(found.transactions.IsSubsetOf(todo));
692 [ + - ]: 2153 : assert(depgraph.FeeRate(found.transactions) == found.feerate);
693 [ + + - + ]: 2153 : if (!init_best.feerate.IsEmpty()) assert(found.feerate >= init_best.feerate);
694 : : // Check that it is topologically valid.
695 [ + - + + ]: 11365 : for (auto i : found.transactions) {
696 [ - + ]: 7059 : assert(found.transactions.IsSupersetOf(depgraph.Ancestors(i) & todo));
697 : : }
698 : :
699 : : // At most 2^(N-1) iterations can be required: the maximum number of non-empty topological
700 : : // subsets a (connected) cluster with N transactions can have. Even when the cluster is no
701 : : // longer connected after removing certain transactions, this holds, because the connected
702 : : // components are searched separately.
703 [ - + ]: 2153 : assert(iterations_done <= (uint64_t{1} << (todo.Count() - 1)));
704 : : // Additionally, test that no more than sqrt(2^N)+1 iterations are required. This is just
705 : : // an empirical bound that seems to hold, without proof. Still, add a test for it so we
706 : : // can learn about counterexamples if they exist.
707 [ + + + - ]: 2153 : if (iterations_done >= 1 && todo.Count() <= 63) {
708 [ + - ]: 1463 : Assume((iterations_done - 1) * (iterations_done - 1) <= uint64_t{1} << todo.Count());
709 : : }
710 : :
711 : : // Perform quality checks only if SearchCandidateFinder claims an optimal result.
712 [ + + ]: 2153 : if (iterations_done < max_iterations) {
713 : : // Optimal sets are always connected.
714 [ - + ]: 1155 : assert(depgraph.IsConnected(found.transactions));
715 : :
716 : : // Compare with SimpleCandidateFinder.
717 [ - + ]: 1155 : auto [simple, simple_iters] = smp_finder.FindCandidateSet(MAX_SIMPLE_ITERATIONS);
718 [ - + ]: 1155 : assert(found.feerate >= simple.feerate);
719 [ + + ]: 1155 : if (simple_iters < MAX_SIMPLE_ITERATIONS) {
720 [ + - ]: 1136 : assert(found.feerate == simple.feerate);
721 : : }
722 : :
723 : : // Compare with AncestorCandidateFinder;
724 : 1155 : auto anc = anc_finder.FindCandidateSet();
725 [ - + ]: 1155 : assert(found.feerate >= anc.feerate);
726 : :
727 : : // Compare with ExhaustiveCandidateFinder. This quickly gets computationally expensive
728 : : // for large clusters (O(2^n)), so only do it for sufficiently small ones.
729 [ + + ]: 1155 : if (todo.Count() <= 12) {
730 : 613 : auto exhaustive = exh_finder.FindCandidateSet();
731 [ + - ]: 613 : assert(exhaustive.feerate == found.feerate);
732 : : // Also compare ExhaustiveCandidateFinder with SimpleCandidateFinder (this is
733 : : // primarily a test for SimpleCandidateFinder's correctness).
734 [ - + ]: 613 : assert(exhaustive.feerate >= simple.feerate);
735 [ + - ]: 613 : if (simple_iters < MAX_SIMPLE_ITERATIONS) {
736 [ + - ]: 613 : assert(exhaustive.feerate == simple.feerate);
737 : : }
738 : : }
739 : : }
740 : :
741 : : // Find a topologically valid subset of transactions to remove from the graph.
742 [ + - ]: 2153 : auto del_set = ReadTopologicalSet(depgraph, todo, reader);
743 : : // If we did not find anything, use found itself, because we should remove something.
744 [ + + ]: 2153 : if (del_set.None()) del_set = found.transactions;
745 : 2153 : todo -= del_set;
746 : 2153 : src_finder.MarkDone(del_set);
747 : 2153 : smp_finder.MarkDone(del_set);
748 : 2153 : exh_finder.MarkDone(del_set);
749 : 2153 : anc_finder.MarkDone(del_set);
750 : : }
751 : :
752 [ - + ]: 281 : assert(src_finder.AllDone());
753 [ - + ]: 281 : assert(smp_finder.AllDone());
754 [ - + ]: 281 : assert(exh_finder.AllDone());
755 [ - + ]: 281 : assert(anc_finder.AllDone());
756 [ - + ]: 281 : assert(anc_finder.NumRemaining() == 0);
757 : 281 : }
758 : :
759 [ + - ]: 571 : FUZZ_TARGET(clusterlin_linearization_chunking)
760 : : {
761 : : // Verify the behavior of LinearizationChunking.
762 : :
763 : : // Retrieve a depgraph from the fuzz input.
764 [ + - ]: 127 : SpanReader reader(buffer);
765 : 127 : DepGraph<TestBitSet> depgraph;
766 : 127 : try {
767 [ + - ]: 127 : reader >> Using<DepGraphFormatter>(depgraph);
768 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
769 : :
770 : : // Retrieve a topologically-valid subset of depgraph.
771 : 127 : auto todo = depgraph.Positions();
772 [ + - ]: 127 : auto subset = SetInfo(depgraph, ReadTopologicalSet(depgraph, todo, reader));
773 : :
774 : : // Retrieve a valid linearization for depgraph.
775 [ + - ]: 127 : auto linearization = ReadLinearization(depgraph, reader);
776 : :
777 : : // Construct a LinearizationChunking object, initially for the whole linearization.
778 : 127 : LinearizationChunking chunking(depgraph, linearization);
779 : :
780 : : // Incrementally remove transactions from the chunking object, and check various properties at
781 : : // every step.
782 [ + + ]: 1545 : while (todo.Any()) {
783 [ - + ]: 1291 : assert(chunking.NumChunksLeft() > 0);
784 : :
785 : : // Construct linearization with just todo.
786 : 1291 : std::vector<DepGraphIndex> linearization_left;
787 [ + + ]: 31399 : for (auto i : linearization) {
788 [ + + + - ]: 30108 : if (todo[i]) linearization_left.push_back(i);
789 : : }
790 : :
791 : : // Compute the chunking for linearization_left.
792 : 1291 : auto chunking_left = ChunkLinearization(depgraph, linearization_left);
793 : :
794 : : // Verify that it matches the feerates of the chunks of chunking.
795 [ - + ]: 1291 : assert(chunking.NumChunksLeft() == chunking_left.size());
796 [ + + ]: 7906 : for (DepGraphIndex i = 0; i < chunking.NumChunksLeft(); ++i) {
797 [ + - ]: 13230 : assert(chunking.GetChunk(i).feerate == chunking_left[i]);
798 : : }
799 : :
800 : : // Check consistency of chunking.
801 : 1291 : TestBitSet combined;
802 [ + + ]: 7906 : for (DepGraphIndex i = 0; i < chunking.NumChunksLeft(); ++i) {
803 : 6615 : const auto& chunk_info = chunking.GetChunk(i);
804 : : // Chunks must be non-empty.
805 [ - + ]: 6615 : assert(chunk_info.transactions.Any());
806 : : // Chunk feerates must be monotonically non-increasing.
807 [ + + - + ]: 6615 : if (i > 0) assert(!(chunk_info.feerate >> chunking.GetChunk(i - 1).feerate));
808 : : // Chunks must be a subset of what is left of the linearization.
809 [ - + ]: 6615 : assert(chunk_info.transactions.IsSubsetOf(todo));
810 : : // Chunks' claimed feerates must match their transactions' aggregate feerate.
811 [ + - ]: 6615 : assert(depgraph.FeeRate(chunk_info.transactions) == chunk_info.feerate);
812 : : // Chunks must be the highest-feerate remaining prefix.
813 : 6615 : SetInfo<TestBitSet> accumulator, best;
814 [ + + ]: 185473 : for (auto j : linearization) {
815 [ + + + + ]: 178858 : if (todo[j] && !combined[j]) {
816 : 61898 : accumulator.Set(depgraph, j);
817 [ + + + + ]: 61898 : if (best.feerate.IsEmpty() || accumulator.feerate > best.feerate) {
818 : 12680 : best = accumulator;
819 : : }
820 : : }
821 : : }
822 [ - + ]: 6615 : assert(best.transactions == chunk_info.transactions);
823 [ + - ]: 6615 : assert(best.feerate == chunk_info.feerate);
824 : : // Chunks cannot overlap.
825 [ - + ]: 6615 : assert(!chunk_info.transactions.Overlaps(combined));
826 [ + - ]: 6615 : combined |= chunk_info.transactions;
827 : : // Chunks must be topological.
828 [ + - + + ]: 28559 : for (auto idx : chunk_info.transactions) {
829 [ - + ]: 15329 : assert((depgraph.Ancestors(idx) & todo).IsSubsetOf(combined));
830 : : }
831 : : }
832 [ - + ]: 1291 : assert(combined == todo);
833 : :
834 : : // Verify the expected properties of LinearizationChunking::IntersectPrefixes:
835 : 1291 : auto intersect = chunking.IntersectPrefixes(subset);
836 : : // - Intersecting again doesn't change the result.
837 [ + - ]: 1291 : assert(chunking.IntersectPrefixes(intersect) == intersect);
838 : : // - The intersection is topological.
839 : 1291 : TestBitSet intersect_anc;
840 [ + + + + ]: 4270 : for (auto idx : intersect.transactions) {
841 : 2372 : intersect_anc |= (depgraph.Ancestors(idx) & todo);
842 : : }
843 [ - + ]: 1291 : assert(intersect.transactions == intersect_anc);
844 : : // - The claimed intersection feerate matches its transactions.
845 [ + - ]: 1291 : assert(intersect.feerate == depgraph.FeeRate(intersect.transactions));
846 : : // - The intersection may only be empty if its input is empty.
847 [ - + ]: 1291 : assert(intersect.transactions.Any() == subset.transactions.Any());
848 : : // - The intersection feerate must be as high as the input.
849 [ - + ]: 1291 : assert(intersect.feerate >= subset.feerate);
850 : : // - No non-empty intersection between the intersection and a prefix of the chunks of the
851 : : // remainder of the linearization may be better than the intersection.
852 : 1291 : TestBitSet prefix;
853 [ + + ]: 7906 : for (DepGraphIndex i = 0; i < chunking.NumChunksLeft(); ++i) {
854 : 6615 : prefix |= chunking.GetChunk(i).transactions;
855 : 6615 : auto reintersect = SetInfo(depgraph, prefix & intersect.transactions);
856 [ + + ]: 6615 : if (!reintersect.feerate.IsEmpty()) {
857 [ - + ]: 3454 : assert(reintersect.feerate <= intersect.feerate);
858 : : }
859 : : }
860 : :
861 : : // Find a subset to remove from linearization.
862 [ + - ]: 1291 : auto done = ReadTopologicalSet(depgraph, todo, reader);
863 [ + + ]: 1291 : if (done.None()) {
864 : : // We need to remove a non-empty subset, so fall back to the unlinearized ancestors of
865 : : // the first transaction in todo if done is empty.
866 : 1156 : done = depgraph.Ancestors(todo.First()) & todo;
867 : : }
868 : 1291 : todo -= done;
869 : 1291 : chunking.MarkDone(done);
870 : 1291 : subset = SetInfo(depgraph, subset.transactions - done);
871 : 1291 : }
872 : :
873 [ - + ]: 127 : assert(chunking.NumChunksLeft() == 0);
874 : 127 : }
875 : :
876 [ + - ]: 812 : FUZZ_TARGET(clusterlin_linearize)
877 : : {
878 : : // Verify the behavior of Linearize().
879 : :
880 : : // Retrieve an RNG seed, an iteration count, a depgraph, and whether to make it connected from
881 : : // the fuzz input.
882 [ + + ]: 368 : SpanReader reader(buffer);
883 : 368 : DepGraph<TestBitSet> depgraph;
884 : 368 : uint64_t rng_seed{0};
885 : 368 : uint64_t iter_count{0};
886 : 368 : uint8_t make_connected{1};
887 : 368 : try {
888 [ + + + - : 368 : reader >> VARINT(iter_count) >> Using<DepGraphFormatter>(depgraph) >> rng_seed >> make_connected;
+ + + + ]
889 [ - + ]: 282 : } catch (const std::ios_base::failure&) {}
890 : : // The most complicated graphs are connected ones (other ones just split up). Optionally force
891 : : // the graph to be connected.
892 [ + + + - ]: 368 : if (make_connected) MakeConnected(depgraph);
893 : :
894 : : // Optionally construct an old linearization for it.
895 : 368 : std::vector<DepGraphIndex> old_linearization;
896 : 368 : {
897 : 368 : uint8_t have_old_linearization{0};
898 : 368 : try {
899 [ + + ]: 368 : reader >> have_old_linearization;
900 [ - + ]: 225 : } catch(const std::ios_base::failure&) {}
901 [ + + ]: 368 : if (have_old_linearization & 1) {
902 [ + - ]: 242 : old_linearization = ReadLinearization(depgraph, reader);
903 : 121 : SanityCheck(depgraph, old_linearization);
904 : : }
905 : : }
906 : :
907 : : // Invoke Linearize().
908 : 368 : iter_count &= 0x7ffff;
909 : 368 : auto [linearization, optimal] = Linearize(depgraph, iter_count, rng_seed, old_linearization);
910 : 368 : SanityCheck(depgraph, linearization);
911 : 368 : auto chunking = ChunkLinearization(depgraph, linearization);
912 : :
913 : : // Linearization must always be as good as the old one, if provided.
914 [ + + ]: 368 : if (!old_linearization.empty()) {
915 : 120 : auto old_chunking = ChunkLinearization(depgraph, old_linearization);
916 [ + - ]: 120 : auto cmp = CompareChunks(chunking, old_chunking);
917 [ - + ]: 120 : assert(cmp >= 0);
918 : 120 : }
919 : :
920 : : // If the iteration count is sufficiently high, an optimal linearization must be found.
921 : : // Each linearization step can use up to 2^(k-1) iterations, with steps k=1..n. That sum is
922 : : // 2^n - 1.
923 [ + + ]: 368 : const uint64_t n = depgraph.TxCount();
924 [ + + + + ]: 368 : if (n <= 19 && iter_count > (uint64_t{1} << n)) {
925 [ - + ]: 51 : assert(optimal);
926 : : }
927 : : // Additionally, if the assumption of sqrt(2^k)+1 iterations per step holds, plus ceil(k/4)
928 : : // start-up cost per step, plus ceil(n^2/64) start-up cost overall, we can compute the upper
929 : : // bound for a whole linearization (summing for k=1..n) using the Python expression
930 : : // [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)]:
931 : 368 : static constexpr uint64_t MAX_OPTIMAL_ITERS[] = {
932 : : 0, 4, 8, 12, 18, 26, 37, 51, 70, 97, 133, 182, 251, 346, 480, 666, 927, 1296, 1815, 2545,
933 : : 3576, 5031, 7087, 9991, 14094, 19895, 28096, 39690, 56083, 79263, 112041, 158391, 223936,
934 : : 316629, 447712
935 : : };
936 [ + - + + ]: 368 : if (n < std::size(MAX_OPTIMAL_ITERS) && iter_count >= MAX_OPTIMAL_ITERS[n]) {
937 [ + - ]: 94 : Assume(optimal);
938 : : }
939 : :
940 : : // If Linearize claims optimal result, run quality tests.
941 [ + + ]: 368 : if (optimal) {
942 : : // It must be as good as SimpleLinearize.
943 : 255 : auto [simple_linearization, simple_optimal] = SimpleLinearize(depgraph, MAX_SIMPLE_ITERATIONS);
944 : 255 : SanityCheck(depgraph, simple_linearization);
945 : 255 : auto simple_chunking = ChunkLinearization(depgraph, simple_linearization);
946 [ + - ]: 255 : auto cmp = CompareChunks(chunking, simple_chunking);
947 [ - + ]: 255 : assert(cmp >= 0);
948 : : // If SimpleLinearize finds the optimal result too, they must be equal (if not,
949 : : // SimpleLinearize is broken).
950 [ + + - + ]: 255 : if (simple_optimal) assert(cmp == 0);
951 : :
952 : : // Only for very small clusters, test every topologically-valid permutation.
953 [ + + ]: 255 : if (depgraph.TxCount() <= 7) {
954 : 60 : std::vector<DepGraphIndex> perm_linearization;
955 [ + + + - : 356 : for (DepGraphIndex i : depgraph.Positions()) perm_linearization.push_back(i);
+ + ]
956 : : // Iterate over all valid permutations.
957 : 66540 : do {
958 : : // Determine whether perm_linearization is topological.
959 : 66540 : TestBitSet perm_done;
960 : 66540 : bool perm_is_topo{true};
961 [ + + ]: 119591 : for (auto i : perm_linearization) {
962 : 117776 : perm_done.Set(i);
963 [ + + ]: 117776 : if (!depgraph.Ancestors(i).IsSubsetOf(perm_done)) {
964 : : perm_is_topo = false;
965 : : break;
966 : : }
967 : : }
968 : : // If so, verify that the obtained linearization is as good as the permutation.
969 [ + + ]: 66540 : if (perm_is_topo) {
970 : 1815 : auto perm_chunking = ChunkLinearization(depgraph, perm_linearization);
971 [ + - ]: 1815 : auto cmp = CompareChunks(chunking, perm_chunking);
972 [ - + ]: 1815 : assert(cmp >= 0);
973 : 1815 : }
974 [ + + ]: 66540 : } while(std::next_permutation(perm_linearization.begin(), perm_linearization.end()));
975 : 60 : }
976 : 255 : }
977 : 368 : }
978 : :
979 [ + - ]: 546 : FUZZ_TARGET(clusterlin_postlinearize)
980 : : {
981 : : // Verify expected properties of PostLinearize() on arbitrary linearizations.
982 : :
983 : : // Retrieve a depgraph from the fuzz input.
984 [ + - ]: 102 : SpanReader reader(buffer);
985 : 102 : DepGraph<TestBitSet> depgraph;
986 : 102 : try {
987 [ + - ]: 102 : reader >> Using<DepGraphFormatter>(depgraph);
988 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
989 : :
990 : : // Retrieve a linearization from the fuzz input.
991 : 102 : std::vector<DepGraphIndex> linearization;
992 [ + - ]: 204 : linearization = ReadLinearization(depgraph, reader);
993 : 102 : SanityCheck(depgraph, linearization);
994 : :
995 : : // Produce a post-processed version.
996 [ + - ]: 102 : auto post_linearization = linearization;
997 [ + - ]: 102 : PostLinearize(depgraph, post_linearization);
998 : 102 : SanityCheck(depgraph, post_linearization);
999 : :
1000 : : // Compare diagrams: post-linearization cannot worsen anywhere.
1001 : 102 : auto chunking = ChunkLinearization(depgraph, linearization);
1002 : 102 : auto post_chunking = ChunkLinearization(depgraph, post_linearization);
1003 [ + - ]: 102 : auto cmp = CompareChunks(post_chunking, chunking);
1004 [ - + ]: 102 : assert(cmp >= 0);
1005 : :
1006 : : // Run again, things can keep improving (and never get worse)
1007 [ + - ]: 102 : auto post_post_linearization = post_linearization;
1008 [ + - ]: 102 : PostLinearize(depgraph, post_post_linearization);
1009 : 102 : SanityCheck(depgraph, post_post_linearization);
1010 : 102 : auto post_post_chunking = ChunkLinearization(depgraph, post_post_linearization);
1011 [ + - ]: 102 : cmp = CompareChunks(post_post_chunking, post_chunking);
1012 [ - + ]: 102 : assert(cmp >= 0);
1013 : :
1014 : : // The chunks that come out of postlinearizing are always connected.
1015 : 102 : LinearizationChunking linchunking(depgraph, post_linearization);
1016 [ + + ]: 1035 : while (linchunking.NumChunksLeft()) {
1017 [ - + ]: 831 : assert(depgraph.IsConnected(linchunking.GetChunk(0).transactions));
1018 : 831 : linchunking.MarkDone(linchunking.GetChunk(0).transactions);
1019 : : }
1020 : 102 : }
1021 : :
1022 [ + - ]: 779 : FUZZ_TARGET(clusterlin_postlinearize_tree)
1023 : : {
1024 : : // Verify expected properties of PostLinearize() on linearizations of graphs that form either
1025 : : // an upright or reverse tree structure.
1026 : :
1027 : : // Construct a direction, RNG seed, and an arbitrary graph from the fuzz input.
1028 [ + - ]: 335 : SpanReader reader(buffer);
1029 : 335 : uint64_t rng_seed{0};
1030 : 335 : DepGraph<TestBitSet> depgraph_gen;
1031 : 335 : uint8_t direction{0};
1032 : 335 : try {
1033 [ + - + + : 335 : reader >> direction >> rng_seed >> Using<DepGraphFormatter>(depgraph_gen);
+ - ]
1034 [ - + ]: 1 : } catch (const std::ios_base::failure&) {}
1035 : :
1036 : : // Now construct a new graph, copying the nodes, but leaving only the first parent (even
1037 : : // direction) or the first child (odd direction).
1038 : 335 : DepGraph<TestBitSet> depgraph_tree;
1039 [ + + ]: 10084 : for (DepGraphIndex i = 0; i < depgraph_gen.PositionRange(); ++i) {
1040 [ + + ]: 9749 : if (depgraph_gen.Positions()[i]) {
1041 : 7893 : depgraph_tree.AddTransaction(depgraph_gen.FeeRate(i));
1042 : : } else {
1043 : : // For holes, add a dummy transaction which is deleted below, so that non-hole
1044 : : // transactions retain their position.
1045 : 1856 : depgraph_tree.AddTransaction(FeeFrac{});
1046 : : }
1047 : : }
1048 : 335 : depgraph_tree.RemoveTransactions(TestBitSet::Fill(depgraph_gen.PositionRange()) - depgraph_gen.Positions());
1049 : :
1050 [ + + ]: 335 : if (direction & 1) {
1051 [ + + ]: 5149 : for (DepGraphIndex i = 0; i < depgraph_gen.TxCount(); ++i) {
1052 : 4937 : auto children = depgraph_gen.GetReducedChildren(i);
1053 [ + + ]: 4937 : if (children.Any()) {
1054 : 3181 : depgraph_tree.AddDependencies(TestBitSet::Singleton(i), children.First());
1055 : : }
1056 : : }
1057 : : } else {
1058 [ + + ]: 3079 : for (DepGraphIndex i = 0; i < depgraph_gen.TxCount(); ++i) {
1059 : 2956 : auto parents = depgraph_gen.GetReducedParents(i);
1060 [ + + ]: 2956 : if (parents.Any()) {
1061 : 1231 : depgraph_tree.AddDependencies(TestBitSet::Singleton(parents.First()), i);
1062 : : }
1063 : : }
1064 : : }
1065 : :
1066 : : // Retrieve a linearization from the fuzz input.
1067 : 335 : std::vector<DepGraphIndex> linearization;
1068 [ + - ]: 670 : linearization = ReadLinearization(depgraph_tree, reader);
1069 : 335 : SanityCheck(depgraph_tree, linearization);
1070 : :
1071 : : // Produce a postlinearized version.
1072 [ + - ]: 335 : auto post_linearization = linearization;
1073 [ + - ]: 335 : PostLinearize(depgraph_tree, post_linearization);
1074 : 335 : SanityCheck(depgraph_tree, post_linearization);
1075 : :
1076 : : // Compare diagrams.
1077 : 335 : auto chunking = ChunkLinearization(depgraph_tree, linearization);
1078 : 335 : auto post_chunking = ChunkLinearization(depgraph_tree, post_linearization);
1079 [ + - ]: 335 : auto cmp = CompareChunks(post_chunking, chunking);
1080 [ - + ]: 335 : assert(cmp >= 0);
1081 : :
1082 : : // Verify that post-linearizing again does not change the diagram. The result must be identical
1083 : : // as post_linearization ought to be optimal already with a tree-structured graph.
1084 [ + - ]: 335 : auto post_post_linearization = post_linearization;
1085 [ + - ]: 335 : PostLinearize(depgraph_tree, post_linearization);
1086 : 335 : SanityCheck(depgraph_tree, post_linearization);
1087 : 335 : auto post_post_chunking = ChunkLinearization(depgraph_tree, post_post_linearization);
1088 [ + - ]: 335 : auto cmp_post = CompareChunks(post_post_chunking, post_chunking);
1089 [ - + ]: 335 : assert(cmp_post == 0);
1090 : :
1091 : : // Try to find an even better linearization directly. This must not change the diagram for the
1092 : : // same reason.
1093 : 335 : auto [opt_linearization, _optimal] = Linearize(depgraph_tree, 100000, rng_seed, post_linearization);
1094 : 335 : auto opt_chunking = ChunkLinearization(depgraph_tree, opt_linearization);
1095 [ + - ]: 335 : auto cmp_opt = CompareChunks(opt_chunking, post_chunking);
1096 [ - + ]: 335 : assert(cmp_opt == 0);
1097 : 335 : }
1098 : :
1099 [ + - ]: 546 : FUZZ_TARGET(clusterlin_postlinearize_moved_leaf)
1100 : : {
1101 : : // Verify that taking an existing linearization, and moving a leaf to the back, potentially
1102 : : // increasing its fee, and then post-linearizing, results in something as good as the
1103 : : // original. This guarantees that in an RBF that replaces a transaction with one of the same
1104 : : // size but higher fee, applying the "remove conflicts, append new transaction, postlinearize"
1105 : : // process will never worsen linearization quality.
1106 : :
1107 : : // Construct an arbitrary graph and a fee from the fuzz input.
1108 [ + - ]: 102 : SpanReader reader(buffer);
1109 : 102 : DepGraph<TestBitSet> depgraph;
1110 : 102 : int32_t fee_inc{0};
1111 : 102 : try {
1112 : 102 : uint64_t fee_inc_code;
1113 [ + - + + ]: 102 : reader >> Using<DepGraphFormatter>(depgraph) >> VARINT(fee_inc_code);
1114 : 37 : fee_inc = fee_inc_code & 0x3ffff;
1115 [ - + ]: 65 : } catch (const std::ios_base::failure&) {}
1116 [ + + ]: 102 : if (depgraph.TxCount() == 0) return;
1117 : :
1118 : : // Retrieve two linearizations from the fuzz input.
1119 [ + - ]: 95 : auto lin = ReadLinearization(depgraph, reader);
1120 [ + - ]: 95 : auto lin_leaf = ReadLinearization(depgraph, reader);
1121 : :
1122 : : // Construct a linearization identical to lin, but with the tail end of lin_leaf moved to the
1123 : : // back.
1124 : 95 : std::vector<DepGraphIndex> lin_moved;
1125 [ + + ]: 1320 : for (auto i : lin) {
1126 [ + + + - ]: 1225 : if (i != lin_leaf.back()) lin_moved.push_back(i);
1127 : : }
1128 [ + - ]: 95 : lin_moved.push_back(lin_leaf.back());
1129 : :
1130 : : // Postlinearize lin_moved.
1131 [ + - ]: 95 : PostLinearize(depgraph, lin_moved);
1132 : 95 : SanityCheck(depgraph, lin_moved);
1133 : :
1134 : : // Compare diagrams (applying the fee delta after computing the old one).
1135 : 95 : auto old_chunking = ChunkLinearization(depgraph, lin);
1136 : 95 : depgraph.FeeRate(lin_leaf.back()).fee += fee_inc;
1137 : 95 : auto new_chunking = ChunkLinearization(depgraph, lin_moved);
1138 [ + - ]: 95 : auto cmp = CompareChunks(new_chunking, old_chunking);
1139 [ - + ]: 95 : assert(cmp >= 0);
1140 : 102 : }
1141 : :
1142 [ + - ]: 610 : FUZZ_TARGET(clusterlin_merge)
1143 : : {
1144 : : // Construct an arbitrary graph from the fuzz input.
1145 [ + - ]: 166 : SpanReader reader(buffer);
1146 : 166 : DepGraph<TestBitSet> depgraph;
1147 : 166 : try {
1148 [ + - ]: 166 : reader >> Using<DepGraphFormatter>(depgraph);
1149 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
1150 : :
1151 : : // Retrieve two linearizations from the fuzz input.
1152 [ + - ]: 166 : auto lin1 = ReadLinearization(depgraph, reader);
1153 [ + - ]: 166 : auto lin2 = ReadLinearization(depgraph, reader);
1154 : :
1155 : : // Merge the two.
1156 [ + - ]: 166 : auto lin_merged = MergeLinearizations(depgraph, lin1, lin2);
1157 : :
1158 : : // Compute chunkings and compare.
1159 : 166 : auto chunking1 = ChunkLinearization(depgraph, lin1);
1160 : 166 : auto chunking2 = ChunkLinearization(depgraph, lin2);
1161 : 166 : auto chunking_merged = ChunkLinearization(depgraph, lin_merged);
1162 [ + - ]: 166 : auto cmp1 = CompareChunks(chunking_merged, chunking1);
1163 [ - + ]: 166 : assert(cmp1 >= 0);
1164 [ + - ]: 166 : auto cmp2 = CompareChunks(chunking_merged, chunking2);
1165 [ - + ]: 166 : assert(cmp2 >= 0);
1166 : 166 : }
1167 : :
1168 [ + - ]: 641 : FUZZ_TARGET(clusterlin_fix_linearization)
1169 : : {
1170 : : // Verify expected properties of FixLinearization() on arbitrary linearizations.
1171 : :
1172 : : // Retrieve a depgraph from the fuzz input.
1173 [ + - ]: 197 : SpanReader reader(buffer);
1174 : 197 : DepGraph<TestBitSet> depgraph;
1175 : 197 : try {
1176 [ + - ]: 197 : reader >> Using<DepGraphFormatter>(depgraph);
1177 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
1178 : :
1179 : : // Construct an arbitrary linearization (not necessarily topological for depgraph).
1180 : 197 : std::vector<DepGraphIndex> linearization;
1181 : : /** Which transactions of depgraph are yet to be included in linearization. */
1182 : 197 : TestBitSet todo = depgraph.Positions();
1183 [ + + ]: 2125 : while (todo.Any()) {
1184 : : // Read a number from the fuzz input in range [0, todo.Count()).
1185 : 1731 : uint64_t val{0};
1186 : 1731 : try {
1187 [ + + ]: 1731 : reader >> VARINT(val);
1188 [ - + ]: 1475 : } catch (const std::ios_base::failure&) {}
1189 [ + - ]: 1731 : val %= todo.Count();
1190 : : // Find the val'th element in todo, remove it from todo, and append it to linearization.
1191 [ + - + - ]: 4244 : for (auto idx : todo) {
1192 [ + + ]: 2513 : if (val == 0) {
1193 [ + - ]: 1731 : linearization.push_back(idx);
1194 : 1731 : todo.Reset(idx);
1195 : 1731 : break;
1196 : : }
1197 : 782 : --val;
1198 : : }
1199 : : }
1200 [ - + ]: 197 : assert(linearization.size() == depgraph.TxCount());
1201 : :
1202 : : // Determine what prefix of linearization is topological, i.e., the position of the first entry
1203 : : // in linearization which corresponds to a transaction that is not preceded by all its
1204 : : // ancestors.
1205 : 197 : size_t topo_prefix = 0;
1206 : 197 : todo = depgraph.Positions();
1207 [ + + ]: 1159 : while (topo_prefix < linearization.size()) {
1208 : 1027 : DepGraphIndex idx = linearization[topo_prefix];
1209 : 1027 : todo.Reset(idx);
1210 [ + + ]: 1027 : if (todo.Overlaps(depgraph.Ancestors(idx))) break;
1211 : 962 : ++topo_prefix;
1212 : : }
1213 : :
1214 : : // Then make a fixed copy of linearization.
1215 [ + - ]: 197 : auto linearization_fixed = linearization;
1216 : 197 : FixLinearization(depgraph, linearization_fixed);
1217 : : // Sanity check it (which includes testing whether it is topological).
1218 : 197 : SanityCheck(depgraph, linearization_fixed);
1219 : :
1220 : : // FixLinearization does not modify the topological prefix of linearization.
1221 [ - + ]: 197 : assert(std::equal(linearization.begin(), linearization.begin() + topo_prefix,
1222 : : linearization_fixed.begin()));
1223 : : // This also means that if linearization was entirely topological, FixLinearization cannot have
1224 : : // modified it. This is implied by the assertion above already, but repeat it explicitly.
1225 [ + + ]: 197 : if (topo_prefix == linearization.size()) {
1226 [ - + ]: 132 : assert(linearization == linearization_fixed);
1227 : : }
1228 : 197 : }
|
