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 : 429 : SimpleCandidateFinder(const DepGraph<SetType>& depgraph LIFETIMEBOUND) noexcept :
40 : 429 : m_depgraph(depgraph), m_todo{depgraph.Positions()} {}
41 : :
42 : : /** Remove a set of transactions from the set of to-be-linearized ones. */
43 : 2992 : void MarkDone(SetType select) noexcept { m_todo -= select; }
44 : :
45 : : /** Determine whether unlinearized transactions remain. */
46 : 1941 : 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 : 2203 : std::pair<SetInfo<SetType>, uint64_t> FindCandidateSet(uint64_t max_iterations) const noexcept
55 : : {
56 : 2203 : 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 : 2203 : std::vector<std::pair<SetType, SetType>> queue;
61 : : // Initially we have just one queue element, with the entire graph in und.
62 : 2203 : queue.emplace_back(SetType{}, m_todo);
63 : : // Best solution so far.
64 : 2203 : SetInfo best(m_depgraph, m_todo);
65 : : // Process the queue.
66 [ + + + + ]: 7036532 : while (!queue.empty() && iterations_left) {
67 : 7034329 : --iterations_left;
68 : : // Pop top element of the queue.
69 : 7034329 : auto [inc, und] = queue.back();
70 : 7034329 : queue.pop_back();
71 : : // Look for a transaction to consider adding/removing.
72 : 7034329 : bool inc_none = inc.None();
73 [ + + ]: 10424779 : 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 [ + + + + ]: 6906600 : if (inc_none || inc.Overlaps(m_depgraph.Ancestors(split))) {
78 : : // Add a queue entry with split included.
79 : 3516150 : SetInfo new_inc(m_depgraph, inc | (m_todo & m_depgraph.Ancestors(split)));
80 : 3516150 : queue.emplace_back(new_inc.transactions, und - new_inc.transactions);
81 : : // Add a queue entry with split excluded.
82 : 3516150 : queue.emplace_back(inc, und - m_depgraph.Descendants(split));
83 : : // Update statistics to account for the candidate new_inc.
84 [ + + ]: 3516150 : if (new_inc.feerate > best.feerate) best = new_inc;
85 : : break;
86 : : }
87 : : }
88 : : }
89 : 2203 : return {std::move(best), max_iterations - iterations_left};
90 : 2203 : }
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 : 229 : ExhaustiveCandidateFinder(const DepGraph<SetType>& depgraph LIFETIMEBOUND) noexcept :
110 : 229 : m_depgraph(depgraph), m_todo{depgraph.Positions()} {}
111 : :
112 : : /** Remove a set of transactions from the set of to-be-linearized ones. */
113 : 1712 : void MarkDone(SetType select) noexcept { m_todo -= select; }
114 : :
115 : : /** Determine whether unlinearized transactions remain. */
116 : 1941 : 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 : 478 : SetInfo<SetType> FindCandidateSet() const noexcept
123 : : {
124 : : // Best solution so far.
125 : 478 : SetInfo<SetType> best{m_todo, m_depgraph.FeeRate(m_todo)};
126 : : // The number of combinations to try.
127 : 478 : uint64_t limit = (uint64_t{1} << m_todo.Count()) - 1;
128 : : // Try the transitive closure of every non-empty subset of m_todo.
129 [ + + ]: 209984 : 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 : 209506 : SetType txn;
133 : 209506 : auto x_shifted{x};
134 [ + - + + ]: 2694964 : for (auto i : m_todo) {
135 [ + + ]: 2275952 : if (x_shifted & 1) txn |= m_depgraph.Ancestors(i);
136 : 2275952 : x_shifted >>= 1;
137 : : }
138 : 209506 : SetInfo cur(m_depgraph, txn & m_todo);
139 [ + + ]: 209506 : if (cur.feerate > best.feerate) best = cur;
140 : : }
141 : 478 : 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 : 200 : std::pair<std::vector<DepGraphIndex>, bool> SimpleLinearize(const DepGraph<SetType>& depgraph, uint64_t max_iterations)
153 : : {
154 : 200 : std::vector<DepGraphIndex> linearization;
155 : 200 : SimpleCandidateFinder finder(depgraph);
156 : 200 : SetType todo = depgraph.Positions();
157 : 200 : bool optimal = true;
158 [ + + ]: 1480 : while (todo.Any()) {
159 [ + + ]: 1280 : auto [candidate, iterations_done] = finder.FindCandidateSet(max_iterations);
160 [ + + ]: 1280 : if (iterations_done == max_iterations) optimal = false;
161 : 1280 : depgraph.AppendTopo(linearization, candidate.transactions);
162 : 1280 : todo -= candidate.transactions;
163 : 1280 : finder.MarkDone(candidate.transactions);
164 : 1280 : max_iterations -= iterations_done;
165 : : }
166 : 200 : return {std::move(linearization), optimal};
167 : 200 : }
168 : :
169 : : /** Stitch connected components together in a DepGraph, guaranteeing its corresponding cluster is connected. */
170 : : template<typename BS>
171 : 592 : void MakeConnected(DepGraph<BS>& depgraph)
172 : : {
173 : 592 : auto todo = depgraph.Positions();
174 : 592 : auto comp = depgraph.FindConnectedComponent(todo);
175 : 592 : Assume(depgraph.IsConnected(comp));
176 : 592 : todo -= comp;
177 [ + + ]: 7533 : while (todo.Any()) {
178 : 6941 : auto nextcomp = depgraph.FindConnectedComponent(todo);
179 : 6941 : Assume(depgraph.IsConnected(nextcomp));
180 : 6941 : depgraph.AddDependencies(BS::Singleton(comp.Last()), nextcomp.First());
181 : 6941 : todo -= nextcomp;
182 : 6941 : comp = nextcomp;
183 : : }
184 : 592 : }
185 : :
186 : : /** Given a dependency graph, and a todo set, read a topological subset of todo from reader. */
187 : : template<typename SetType>
188 : 5106 : SetType ReadTopologicalSet(const DepGraph<SetType>& depgraph, const SetType& todo, SpanReader& reader)
189 : : {
190 [ + + ]: 5106 : uint64_t mask{0};
191 : : try {
192 [ + + ]: 5106 : reader >> VARINT(mask);
193 [ - + ]: 3272 : } catch(const std::ios_base::failure&) {}
194 : 5106 : SetType ret;
195 [ + + + + ]: 77702 : for (auto i : todo) {
196 [ + + ]: 67495 : if (!ret[i]) {
197 [ + + ]: 66334 : if (mask & 1) ret |= depgraph.Ancestors(i);
198 : 66334 : mask >>= 1;
199 : : }
200 : : }
201 : 5106 : 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 : 960 : std::vector<DepGraphIndex> ReadLinearization(const DepGraph<BS>& depgraph, SpanReader& reader)
207 : : {
208 : 960 : std::vector<DepGraphIndex> linearization;
209 : 960 : TestBitSet todo = depgraph.Positions();
210 : : // In every iteration one topologically-valid transaction is appended to linearization.
211 [ + + ]: 18393 : while (todo.Any()) {
212 : : // Compute the set of transactions with no not-yet-included ancestors.
213 : 16473 : TestBitSet potential_next;
214 [ + + ]: 234528 : for (auto j : todo) {
215 [ + + ]: 354784 : if ((depgraph.Ancestors(j) & todo) == TestBitSet::Singleton(j)) {
216 : 136729 : potential_next.Set(j);
217 : : }
218 : : }
219 : : // There must always be one (otherwise there is a cycle in the graph).
220 [ - + ]: 16473 : assert(potential_next.Any());
221 : : // Read a number from reader, and interpret it as index into potential_next.
222 [ + + ]: 16473 : uint64_t idx{0};
223 : : try {
224 [ + + + - ]: 32946 : reader >> VARINT(idx);
225 [ - + ]: 13934 : } catch (const std::ios_base::failure&) {}
226 : 16473 : idx %= potential_next.Count();
227 : : // Find out which transaction that corresponds to.
228 [ + - + - ]: 41200 : for (auto j : potential_next) {
229 [ + + ]: 24727 : if (idx == 0) {
230 : : // When found, add it to linearization and remove it from todo.
231 [ + - ]: 16473 : linearization.push_back(j);
232 [ - + ]: 16473 : assert(todo[j]);
233 : 16473 : todo.Reset(j);
234 : 16473 : break;
235 : : }
236 : 8254 : --idx;
237 : : }
238 : : }
239 : 960 : return linearization;
240 : 0 : }
241 : :
242 : : } // namespace
243 : :
244 [ + - ]: 585 : FUZZ_TARGET(clusterlin_depgraph_sim)
245 : : {
246 : : // Simulation test to verify the full behavior of DepGraph.
247 : :
248 : 145 : FuzzedDataProvider provider(buffer.data(), buffer.size());
249 : :
250 : : /** Real DepGraph being tested. */
251 : 145 : 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 : 145 : std::array<std::optional<std::pair<FeeFrac, TestBitSet>>, TestBitSet::Size()> sim;
255 : : /** The number of non-nullopt position in sim. */
256 : 145 : DepGraphIndex num_tx_sim{0};
257 : :
258 : : /** Read a valid index of a transaction from the provider. */
259 : 5326 : auto idx_fn = [&]() {
260 : 5181 : auto offset = provider.ConsumeIntegralInRange<DepGraphIndex>(0, num_tx_sim - 1);
261 [ + - ]: 33032 : for (DepGraphIndex i = 0; i < sim.size(); ++i) {
262 [ + + ]: 33032 : if (!sim[i].has_value()) continue;
263 [ + + ]: 29253 : if (offset == 0) return i;
264 : 24072 : --offset;
265 : : }
266 : 0 : assert(false);
267 : : return DepGraphIndex(-1);
268 : 145 : };
269 : :
270 : : /** Read a valid subset of the transactions from the provider. */
271 : 5326 : auto subset_fn = [&]() {
272 : 5181 : auto range = (uint64_t{1} << num_tx_sim) - 1;
273 : 5181 : const auto mask = provider.ConsumeIntegralInRange<uint64_t>(0, range);
274 : 5181 : auto mask_shifted = mask;
275 : 5181 : TestBitSet subset;
276 [ + + ]: 170973 : for (DepGraphIndex i = 0; i < sim.size(); ++i) {
277 [ + + ]: 165792 : if (!sim[i].has_value()) continue;
278 [ + + ]: 71986 : if (mask_shifted & 1) {
279 : 22658 : subset.Set(i);
280 : : }
281 : 71986 : mask_shifted >>= 1;
282 : : }
283 [ - + ]: 5181 : assert(mask_shifted == 0);
284 : 5181 : return subset;
285 : 145 : };
286 : :
287 : : /** Read any set of transactions from the provider (including unused positions). */
288 : 3923 : auto set_fn = [&]() {
289 : 3778 : auto range = (uint64_t{1} << sim.size()) - 1;
290 : 3778 : const auto mask = provider.ConsumeIntegralInRange<uint64_t>(0, range);
291 : 3778 : TestBitSet set;
292 [ + + ]: 124674 : for (DepGraphIndex i = 0; i < sim.size(); ++i) {
293 [ + + ]: 120896 : if ((mask >> i) & 1) {
294 : 45914 : set.Set(i);
295 : : }
296 : : }
297 : 3778 : return set;
298 : 145 : };
299 : :
300 : : /** Propagate ancestor information in sim. */
301 : 4068 : auto anc_update_fn = [&]() {
302 : 4354 : while (true) {
303 : 4354 : bool updates{false};
304 [ + + ]: 143682 : for (DepGraphIndex chl = 0; chl < sim.size(); ++chl) {
305 [ + + ]: 139328 : if (!sim[chl].has_value()) continue;
306 [ + - + + ]: 189233 : for (auto par : sim[chl]->second) {
307 [ + + ]: 107053 : if (!sim[chl]->second.IsSupersetOf(sim[par]->second)) {
308 : 1660 : sim[chl]->second |= sim[par]->second;
309 : 1660 : updates = true;
310 : : }
311 : : }
312 : : }
313 [ + + ]: 4354 : if (!updates) break;
314 : : }
315 : 4068 : };
316 : :
317 : : /** Compare the state of transaction i in the simulation with the real one. */
318 : 50699 : auto check_fn = [&](DepGraphIndex i) {
319 : : // Compare used positions.
320 [ - + ]: 50554 : assert(real.Positions()[i] == sim[i].has_value());
321 [ + + ]: 50554 : if (sim[i].has_value()) {
322 : : // Compare feerate.
323 [ + - ]: 5542 : 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 [ - + ]: 5542 : assert(real.Ancestors(i) == sim[i]->second);
327 : : }
328 : 50699 : };
329 : :
330 [ + + + + ]: 14646 : LIMITED_WHILE(provider.remaining_bytes() > 0, 1000) {
331 : 14501 : uint8_t command = provider.ConsumeIntegral<uint8_t>();
332 [ + + + + : 14501 : if (num_tx_sim == 0 || ((command % 3) <= 0 && num_tx_sim < TestBitSet::Size())) {
+ + ]
333 : : // AddTransaction.
334 : 5542 : auto fee = provider.ConsumeIntegralInRange<int64_t>(-0x8000000000000, 0x7ffffffffffff);
335 : 5542 : auto size = provider.ConsumeIntegralInRange<int32_t>(1, 0x3fffff);
336 : 5542 : FeeFrac feerate{fee, size};
337 : : // Apply to DepGraph.
338 : 5542 : auto idx = real.AddTransaction(feerate);
339 : : // Verify that the returned index is correct.
340 [ - + ]: 5542 : assert(!sim[idx].has_value());
341 [ + - ]: 72515 : for (DepGraphIndex i = 0; i < TestBitSet::Size(); ++i) {
342 [ + + ]: 72515 : if (!sim[i].has_value()) {
343 [ - + ]: 5542 : assert(idx == i);
344 : : break;
345 : : }
346 : : }
347 : : // Update sim.
348 [ - + ]: 5542 : sim[idx] = {feerate, TestBitSet::Singleton(idx)};
349 : 5542 : ++num_tx_sim;
350 : 5542 : continue;
351 : 5542 : }
352 [ + + ]: 8959 : if ((command % 3) <= 1 && num_tx_sim > 0) {
353 : : // AddDependencies.
354 : 5181 : DepGraphIndex child = idx_fn();
355 : 5181 : auto parents = subset_fn();
356 : : // Apply to DepGraph.
357 : 5181 : real.AddDependencies(parents, child);
358 : : // Apply to sim.
359 : 5181 : sim[child]->second |= parents;
360 : 5181 : continue;
361 : 5181 : }
362 : 3778 : if (num_tx_sim > 0) {
363 : : // Remove transactions.
364 : 3778 : 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 : 3778 : anc_update_fn();
368 : : // Compare the state of the transactions being deleted.
369 [ + + + + ]: 52955 : for (auto i : del) check_fn(i);
370 : : // Apply to DepGraph.
371 : 3778 : real.RemoveTransactions(del);
372 : : // Apply to sim.
373 [ + + ]: 124674 : for (DepGraphIndex i = 0; i < sim.size(); ++i) {
374 [ + + ]: 120896 : if (sim[i].has_value()) {
375 [ + + ]: 29917 : if (del[i]) {
376 : 3416 : --num_tx_sim;
377 [ + - ]: 124312 : sim[i] = std::nullopt;
378 : : } else {
379 : 26501 : sim[i]->second -= del;
380 : : }
381 : : }
382 : : }
383 : 3778 : continue;
384 : 3778 : }
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 : 145 : anc_update_fn();
391 [ + + ]: 4785 : for (DepGraphIndex i = 0; i < sim.size(); ++i) check_fn(i);
392 [ - + ]: 145 : assert(real.TxCount() == num_tx_sim);
393 : : // Sanity check the result (which includes round-tripping serialization, if applicable).
394 [ + - ]: 145 : SanityCheck(real);
395 : 145 : }
396 : :
397 [ + - ]: 551 : 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 [ + - ]: 111 : SpanReader reader(buffer);
403 : 111 : DepGraph<TestBitSet> depgraph;
404 : 111 : DepGraphIndex par_code{0}, chl_code{0};
405 : 111 : try {
406 [ + - + + : 111 : reader >> Using<DepGraphFormatter>(depgraph) >> VARINT(par_code) >> VARINT(chl_code);
+ - ]
407 [ - + ]: 107 : } catch (const std::ios_base::failure&) {}
408 [ + - ]: 111 : SanityCheck(depgraph);
409 : :
410 : : // Verify the graph is a DAG.
411 [ - + ]: 111 : assert(depgraph.IsAcyclic());
412 : :
413 : : // Introduce a cycle, and then test that IsAcyclic returns false.
414 [ + + ]: 111 : if (depgraph.TxCount() < 2) return;
415 : 102 : DepGraphIndex par(0), chl(0);
416 : : // Pick any transaction of depgraph as parent.
417 [ + - ]: 102 : par_code %= depgraph.TxCount();
418 [ + - + - ]: 232 : for (auto i : depgraph.Positions()) {
419 [ + + ]: 130 : if (par_code == 0) {
420 : : par = i;
421 : : break;
422 : : }
423 : 28 : --par_code;
424 : : }
425 : : // Pick any ancestor of par (excluding itself) as child, if any.
426 [ + + ]: 102 : auto ancestors = depgraph.Ancestors(par) - TestBitSet::Singleton(par);
427 [ + + ]: 102 : if (ancestors.None()) return;
428 : 42 : chl_code %= ancestors.Count();
429 [ + - ]: 45 : for (auto i : ancestors) {
430 [ + + ]: 45 : if (chl_code == 0) {
431 : : chl = i;
432 : : break;
433 : : }
434 : 3 : --chl_code;
435 : : }
436 : : // Add the cycle-introducing dependency.
437 : 42 : depgraph.AddDependencies(TestBitSet::Singleton(par), chl);
438 : : // Check that we now detect a cycle.
439 [ - + ]: 42 : assert(!depgraph.IsAcyclic());
440 : 111 : }
441 : :
442 [ + - ]: 515 : FUZZ_TARGET(clusterlin_components)
443 : : {
444 : : // Verify the behavior of DepGraphs's FindConnectedComponent and IsConnected functions.
445 : :
446 : : // Construct a depgraph.
447 [ + - ]: 75 : SpanReader reader(buffer);
448 : 75 : DepGraph<TestBitSet> depgraph;
449 : 75 : std::vector<DepGraphIndex> linearization;
450 : 75 : try {
451 [ + - ]: 75 : reader >> Using<DepGraphFormatter>(depgraph);
452 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
453 : :
454 : 75 : TestBitSet todo = depgraph.Positions();
455 [ + + ]: 920 : while (todo.Any()) {
456 : : // Pick a transaction in todo, or nothing.
457 : 845 : std::optional<DepGraphIndex> picked;
458 : 845 : {
459 : 845 : uint64_t picked_num{0};
460 : 845 : try {
461 [ + + ]: 845 : reader >> VARINT(picked_num);
462 [ - + ]: 723 : } catch (const std::ios_base::failure&) {}
463 [ + + + + ]: 845 : if (picked_num < todo.Size() && todo[picked_num]) {
464 : 49 : picked = picked_num;
465 : : }
466 : : }
467 : :
468 : : // Find a connected component inside todo, including picked if any.
469 [ + + ]: 845 : auto component = picked ? depgraph.GetConnectedComponent(todo, *picked)
470 : 796 : : depgraph.FindConnectedComponent(todo);
471 : :
472 : : // The component must be a subset of todo and non-empty.
473 [ - + ]: 845 : assert(component.IsSubsetOf(todo));
474 [ - + ]: 845 : assert(component.Any());
475 : :
476 : : // If picked was provided, the component must include it.
477 [ + + - + ]: 845 : 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 [ + + ]: 845 : if (todo == depgraph.Positions()) {
482 [ + + - + ]: 119 : assert((component == todo) == depgraph.IsConnected());
483 : : }
484 : :
485 : : // If subset is connected, then component must match subset.
486 [ + + - + ]: 1430 : assert((component == todo) == depgraph.IsConnected(todo));
487 : :
488 : : // The component cannot have any ancestors or descendants outside of component but in todo.
489 [ + - + + ]: 6780 : for (auto i : component) {
490 [ - + ]: 5090 : assert((depgraph.Ancestors(i) & todo).IsSubsetOf(component));
491 [ - + ]: 5090 : assert((depgraph.Descendants(i) & todo).IsSubsetOf(component));
492 : : }
493 : :
494 : : // Starting from any component element, we must be able to reach every element.
495 [ + - + + ]: 6780 : for (auto i : component) {
496 : : // Start with just i as reachable.
497 : 5090 : TestBitSet reachable = TestBitSet::Singleton(i);
498 : : // Add in-todo descendants and ancestors to reachable until it does not change anymore.
499 : 43254 : while (true) {
500 : 24172 : TestBitSet new_reachable = reachable;
501 [ + - + + ]: 309898 : for (auto j : new_reachable) {
502 : 261554 : new_reachable |= depgraph.Ancestors(j) & todo;
503 : 261554 : new_reachable |= depgraph.Descendants(j) & todo;
504 : : }
505 [ + + ]: 24172 : if (new_reachable == reachable) break;
506 : 19082 : reachable = new_reachable;
507 : 19082 : }
508 : : // Verify that the result is the entire component.
509 [ - + ]: 5090 : assert(component == reachable);
510 : : }
511 : :
512 : : // Construct an arbitrary subset of todo.
513 : 845 : uint64_t subset_bits{0};
514 : 845 : try {
515 [ + + ]: 845 : reader >> VARINT(subset_bits);
516 [ - + ]: 733 : } catch (const std::ios_base::failure&) {}
517 : 845 : TestBitSet subset;
518 [ + - + + ]: 20329 : for (DepGraphIndex i : depgraph.Positions()) {
519 [ + + ]: 18639 : if (todo[i]) {
520 [ + + ]: 9717 : if (subset_bits & 1) subset.Set(i);
521 : 9717 : subset_bits >>= 1;
522 : : }
523 : : }
524 : : // Which must be non-empty.
525 [ + + ]: 845 : if (subset.None()) subset = TestBitSet::Singleton(todo.First());
526 : : // Remove it from todo.
527 : 845 : todo -= subset;
528 : : }
529 : :
530 : : // No components can be found in an empty subset.
531 [ - + ]: 75 : assert(depgraph.FindConnectedComponent(todo).None());
532 : 75 : }
533 : :
534 [ + - ]: 562 : FUZZ_TARGET(clusterlin_make_connected)
535 : : {
536 : : // Verify that MakeConnected makes graphs connected.
537 : :
538 [ + - ]: 122 : SpanReader reader(buffer);
539 : 122 : DepGraph<TestBitSet> depgraph;
540 : 122 : try {
541 [ + - ]: 122 : reader >> Using<DepGraphFormatter>(depgraph);
542 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
543 [ + - ]: 122 : MakeConnected(depgraph);
544 [ + - ]: 122 : SanityCheck(depgraph);
545 [ - + ]: 122 : assert(depgraph.IsConnected());
546 : 122 : }
547 : :
548 [ + - ]: 504 : FUZZ_TARGET(clusterlin_chunking)
549 : : {
550 : : // Verify the correctness of the ChunkLinearization function.
551 : :
552 : : // Construct a graph by deserializing.
553 [ + - ]: 64 : SpanReader reader(buffer);
554 : 64 : DepGraph<TestBitSet> depgraph;
555 : 64 : try {
556 [ + - ]: 64 : reader >> Using<DepGraphFormatter>(depgraph);
557 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
558 : :
559 : : // Read a valid linearization for depgraph.
560 [ + - ]: 64 : auto linearization = ReadLinearization(depgraph, reader);
561 : :
562 : : // Invoke the chunking function.
563 : 64 : auto chunking = ChunkLinearization(depgraph, linearization);
564 : :
565 : : // Verify that chunk feerates are monotonically non-increasing.
566 [ + + ]: 267 : for (size_t i = 1; i < chunking.size(); ++i) {
567 [ - + ]: 203 : assert(!(chunking[i] >> chunking[i - 1]));
568 : : }
569 : :
570 : : // Naively recompute the chunks (each is the highest-feerate prefix of what remains).
571 : 64 : auto todo = depgraph.Positions();
572 [ + + ]: 327 : for (const auto& chunk_feerate : chunking) {
573 [ - + ]: 263 : assert(todo.Any());
574 : 263 : SetInfo<TestBitSet> accumulator, best;
575 [ + + ]: 5715 : for (DepGraphIndex idx : linearization) {
576 [ + + ]: 5452 : if (todo[idx]) {
577 : 3109 : accumulator.Set(depgraph, idx);
578 [ + + + + ]: 3109 : if (best.feerate.IsEmpty() || accumulator.feerate >> best.feerate) {
579 : 541 : best = accumulator;
580 : : }
581 : : }
582 : : }
583 [ + - ]: 263 : assert(chunk_feerate == best.feerate);
584 [ - + ]: 263 : assert(best.transactions.IsSubsetOf(todo));
585 : 263 : todo -= best.transactions;
586 : : }
587 [ - + ]: 64 : assert(todo.None());
588 : 64 : }
589 : :
590 [ + - ]: 522 : FUZZ_TARGET(clusterlin_ancestor_finder)
591 : : {
592 : : // Verify that AncestorCandidateFinder works as expected.
593 : :
594 : : // Retrieve a depgraph from the fuzz input.
595 [ + - ]: 82 : SpanReader reader(buffer);
596 : 82 : DepGraph<TestBitSet> depgraph;
597 : 82 : try {
598 [ + - ]: 82 : reader >> Using<DepGraphFormatter>(depgraph);
599 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
600 : :
601 : 82 : AncestorCandidateFinder anc_finder(depgraph);
602 : 82 : auto todo = depgraph.Positions();
603 [ + + ]: 764 : while (todo.Any()) {
604 : : // Call the ancestor finder's FindCandidateSet for what remains of the graph.
605 [ - + ]: 682 : assert(!anc_finder.AllDone());
606 [ - + ]: 682 : assert(todo.Count() == anc_finder.NumRemaining());
607 : 682 : auto best_anc = anc_finder.FindCandidateSet();
608 : : // Sanity check the result.
609 [ - + ]: 682 : assert(best_anc.transactions.Any());
610 [ - + ]: 682 : assert(best_anc.transactions.IsSubsetOf(todo));
611 [ + - ]: 682 : assert(depgraph.FeeRate(best_anc.transactions) == best_anc.feerate);
612 [ - + ]: 682 : assert(depgraph.IsConnected(best_anc.transactions));
613 : : // Check that it is topologically valid.
614 [ + - + + ]: 2792 : for (auto i : best_anc.transactions) {
615 [ - + ]: 1428 : assert((depgraph.Ancestors(i) & todo).IsSubsetOf(best_anc.transactions));
616 : : }
617 : :
618 : : // Compute all remaining ancestor sets.
619 : 682 : std::optional<SetInfo<TestBitSet>> real_best_anc;
620 [ + - + + ]: 8897 : for (auto i : todo) {
621 : 7533 : SetInfo info(depgraph, todo & depgraph.Ancestors(i));
622 [ + + + + ]: 7533 : if (!real_best_anc.has_value() || info.feerate > real_best_anc->feerate) {
623 [ + + ]: 9158 : real_best_anc = info;
624 : : }
625 : : }
626 : : // The set returned by anc_finder must equal the real best ancestor sets.
627 [ - + ]: 682 : assert(real_best_anc.has_value());
628 [ + - ]: 682 : assert(*real_best_anc == best_anc);
629 : :
630 : : // Find a topologically valid subset of transactions to remove from the graph.
631 [ + - ]: 682 : auto del_set = ReadTopologicalSet(depgraph, todo, reader);
632 : : // If we did not find anything, use best_anc itself, because we should remove something.
633 [ + + ]: 682 : if (del_set.None()) del_set = best_anc.transactions;
634 : 682 : todo -= del_set;
635 : 682 : anc_finder.MarkDone(del_set);
636 : : }
637 [ - + ]: 82 : assert(anc_finder.AllDone());
638 [ - + ]: 82 : assert(anc_finder.NumRemaining() == 0);
639 : 82 : }
640 : :
641 : : static constexpr auto MAX_SIMPLE_ITERATIONS = 300000;
642 : :
643 [ + - ]: 669 : 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 [ + - ]: 229 : SpanReader reader(buffer);
651 : 229 : DepGraph<TestBitSet> depgraph;
652 : 229 : uint64_t rng_seed{0};
653 : 229 : uint8_t make_connected{1};
654 : 229 : try {
655 [ + - + + : 229 : reader >> Using<DepGraphFormatter>(depgraph) >> rng_seed >> make_connected;
+ - ]
656 [ - + ]: 114 : } 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 [ + + + - ]: 229 : if (make_connected) MakeConnected(depgraph);
660 : :
661 : : // Instantiate ALL the candidate finders.
662 : 229 : SearchCandidateFinder src_finder(depgraph, rng_seed);
663 : 229 : SimpleCandidateFinder smp_finder(depgraph);
664 : 229 : ExhaustiveCandidateFinder exh_finder(depgraph);
665 : 229 : AncestorCandidateFinder anc_finder(depgraph);
666 : :
667 : 229 : auto todo = depgraph.Positions();
668 [ + + ]: 1941 : while (todo.Any()) {
669 [ - + ]: 1712 : assert(!src_finder.AllDone());
670 [ - + ]: 1712 : assert(!smp_finder.AllDone());
671 [ - + ]: 1712 : assert(!exh_finder.AllDone());
672 [ - + ]: 1712 : assert(!anc_finder.AllDone());
673 [ - + ]: 1712 : assert(anc_finder.NumRemaining() == todo.Count());
674 : :
675 : : // For each iteration, read an iteration count limit from the fuzz input.
676 : 1712 : uint64_t max_iterations = 1;
677 : 1712 : try {
678 [ + + ]: 1712 : reader >> VARINT(max_iterations);
679 [ - + ]: 911 : } catch (const std::ios_base::failure&) {}
680 : 1712 : max_iterations &= 0xfffff;
681 : :
682 : : // Read an initial subset from the fuzz input.
683 [ + - ]: 1712 : SetInfo init_best(depgraph, ReadTopologicalSet(depgraph, todo, reader));
684 : :
685 : : // Call the search finder's FindCandidateSet for what remains of the graph.
686 [ - + ]: 1712 : auto [found, iterations_done] = src_finder.FindCandidateSet(max_iterations, init_best);
687 : :
688 : : // Sanity check the result.
689 [ - + ]: 1712 : assert(iterations_done <= max_iterations);
690 [ - + ]: 1712 : assert(found.transactions.Any());
691 [ - + ]: 1712 : assert(found.transactions.IsSubsetOf(todo));
692 [ + - ]: 1712 : assert(depgraph.FeeRate(found.transactions) == found.feerate);
693 [ + + - + ]: 1712 : if (!init_best.feerate.IsEmpty()) assert(found.feerate >= init_best.feerate);
694 : : // Check that it is topologically valid.
695 [ + - + + ]: 9151 : for (auto i : found.transactions) {
696 [ - + ]: 5727 : 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 [ - + ]: 1712 : 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 [ + + + - ]: 1712 : if (iterations_done >= 1 && todo.Count() <= 63) {
708 [ + - ]: 1152 : 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 [ + + ]: 1712 : if (iterations_done < max_iterations) {
713 : : // Optimal sets are always connected.
714 [ - + ]: 923 : assert(depgraph.IsConnected(found.transactions));
715 : :
716 : : // Compare with SimpleCandidateFinder.
717 [ - + ]: 923 : auto [simple, simple_iters] = smp_finder.FindCandidateSet(MAX_SIMPLE_ITERATIONS);
718 [ - + ]: 923 : assert(found.feerate >= simple.feerate);
719 [ + + ]: 923 : if (simple_iters < MAX_SIMPLE_ITERATIONS) {
720 [ + - ]: 907 : assert(found.feerate == simple.feerate);
721 : : }
722 : :
723 : : // Compare with AncestorCandidateFinder;
724 : 923 : auto anc = anc_finder.FindCandidateSet();
725 [ - + ]: 923 : 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 [ + + ]: 923 : if (todo.Count() <= 12) {
730 : 478 : auto exhaustive = exh_finder.FindCandidateSet();
731 [ + - ]: 478 : assert(exhaustive.feerate == found.feerate);
732 : : // Also compare ExhaustiveCandidateFinder with SimpleCandidateFinder (this is
733 : : // primarily a test for SimpleCandidateFinder's correctness).
734 [ - + ]: 478 : assert(exhaustive.feerate >= simple.feerate);
735 [ + - ]: 478 : if (simple_iters < MAX_SIMPLE_ITERATIONS) {
736 [ + - ]: 478 : assert(exhaustive.feerate == simple.feerate);
737 : : }
738 : : }
739 : : }
740 : :
741 : : // Find a topologically valid subset of transactions to remove from the graph.
742 [ + - ]: 1712 : auto del_set = ReadTopologicalSet(depgraph, todo, reader);
743 : : // If we did not find anything, use found itself, because we should remove something.
744 [ + + ]: 1712 : if (del_set.None()) del_set = found.transactions;
745 : 1712 : todo -= del_set;
746 : 1712 : src_finder.MarkDone(del_set);
747 : 1712 : smp_finder.MarkDone(del_set);
748 : 1712 : exh_finder.MarkDone(del_set);
749 : 1712 : anc_finder.MarkDone(del_set);
750 : : }
751 : :
752 [ - + ]: 229 : assert(src_finder.AllDone());
753 [ - + ]: 229 : assert(smp_finder.AllDone());
754 [ - + ]: 229 : assert(exh_finder.AllDone());
755 [ - + ]: 229 : assert(anc_finder.AllDone());
756 [ - + ]: 229 : assert(anc_finder.NumRemaining() == 0);
757 : 229 : }
758 : :
759 [ + - ]: 537 : FUZZ_TARGET(clusterlin_linearization_chunking)
760 : : {
761 : : // Verify the behavior of LinearizationChunking.
762 : :
763 : : // Retrieve a depgraph from the fuzz input.
764 [ + - ]: 97 : SpanReader reader(buffer);
765 : 97 : DepGraph<TestBitSet> depgraph;
766 : 97 : try {
767 [ + - ]: 97 : reader >> Using<DepGraphFormatter>(depgraph);
768 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
769 : :
770 : : // Retrieve a topologically-valid subset of depgraph.
771 : 97 : auto todo = depgraph.Positions();
772 [ + - ]: 97 : auto subset = SetInfo(depgraph, ReadTopologicalSet(depgraph, todo, reader));
773 : :
774 : : // Retrieve a valid linearization for depgraph.
775 [ + - ]: 97 : auto linearization = ReadLinearization(depgraph, reader);
776 : :
777 : : // Construct a LinearizationChunking object, initially for the whole linearization.
778 : 97 : LinearizationChunking chunking(depgraph, linearization);
779 : :
780 : : // Incrementally remove transactions from the chunking object, and check various properties at
781 : : // every step.
782 [ + + ]: 1097 : while (todo.Any()) {
783 [ - + ]: 903 : assert(chunking.NumChunksLeft() > 0);
784 : :
785 : : // Construct linearization with just todo.
786 : 903 : std::vector<DepGraphIndex> linearization_left;
787 [ + + ]: 20598 : for (auto i : linearization) {
788 [ + + + - ]: 19695 : if (todo[i]) linearization_left.push_back(i);
789 : : }
790 : :
791 : : // Compute the chunking for linearization_left.
792 : 903 : auto chunking_left = ChunkLinearization(depgraph, linearization_left);
793 : :
794 : : // Verify that it matches the feerates of the chunks of chunking.
795 [ - + ]: 903 : assert(chunking.NumChunksLeft() == chunking_left.size());
796 [ + + ]: 5730 : for (DepGraphIndex i = 0; i < chunking.NumChunksLeft(); ++i) {
797 [ + - ]: 9654 : assert(chunking.GetChunk(i).feerate == chunking_left[i]);
798 : : }
799 : :
800 : : // Check consistency of chunking.
801 : 903 : TestBitSet combined;
802 [ + + ]: 5730 : for (DepGraphIndex i = 0; i < chunking.NumChunksLeft(); ++i) {
803 : 4827 : const auto& chunk_info = chunking.GetChunk(i);
804 : : // Chunks must be non-empty.
805 [ - + ]: 4827 : assert(chunk_info.transactions.Any());
806 : : // Chunk feerates must be monotonically non-increasing.
807 [ + + - + ]: 4827 : 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 [ - + ]: 4827 : assert(chunk_info.transactions.IsSubsetOf(todo));
810 : : // Chunks' claimed feerates must match their transactions' aggregate feerate.
811 [ + - ]: 4827 : assert(depgraph.FeeRate(chunk_info.transactions) == chunk_info.feerate);
812 : : // Chunks must be the highest-feerate remaining prefix.
813 : 4827 : SetInfo<TestBitSet> accumulator, best;
814 [ + + ]: 131630 : for (auto j : linearization) {
815 [ + + + + ]: 126803 : if (todo[j] && !combined[j]) {
816 : 44547 : accumulator.Set(depgraph, j);
817 [ + + + + ]: 44547 : if (best.feerate.IsEmpty() || accumulator.feerate > best.feerate) {
818 : 8434 : best = accumulator;
819 : : }
820 : : }
821 : : }
822 [ - + ]: 4827 : assert(best.transactions == chunk_info.transactions);
823 [ + - ]: 4827 : assert(best.feerate == chunk_info.feerate);
824 : : // Chunks cannot overlap.
825 [ - + ]: 4827 : assert(!chunk_info.transactions.Overlaps(combined));
826 [ + - ]: 4827 : combined |= chunk_info.transactions;
827 : : // Chunks must be topological.
828 [ + - + + ]: 19672 : for (auto idx : chunk_info.transactions) {
829 [ - + ]: 10018 : assert((depgraph.Ancestors(idx) & todo).IsSubsetOf(combined));
830 : : }
831 : : }
832 [ - + ]: 903 : assert(combined == todo);
833 : :
834 : : // Verify the expected properties of LinearizationChunking::IntersectPrefixes:
835 : 903 : auto intersect = chunking.IntersectPrefixes(subset);
836 : : // - Intersecting again doesn't change the result.
837 [ + - ]: 903 : assert(chunking.IntersectPrefixes(intersect) == intersect);
838 : : // - The intersection is topological.
839 : 903 : TestBitSet intersect_anc;
840 [ + + + + ]: 2786 : for (auto idx : intersect.transactions) {
841 : 1511 : intersect_anc |= (depgraph.Ancestors(idx) & todo);
842 : : }
843 [ - + ]: 903 : assert(intersect.transactions == intersect_anc);
844 : : // - The claimed intersection feerate matches its transactions.
845 [ + - ]: 903 : assert(intersect.feerate == depgraph.FeeRate(intersect.transactions));
846 : : // - The intersection may only be empty if its input is empty.
847 [ - + ]: 903 : assert(intersect.transactions.Any() == subset.transactions.Any());
848 : : // - The intersection feerate must be as high as the input.
849 [ - + ]: 903 : 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 : 903 : TestBitSet prefix;
853 [ + + ]: 5730 : for (DepGraphIndex i = 0; i < chunking.NumChunksLeft(); ++i) {
854 : 4827 : prefix |= chunking.GetChunk(i).transactions;
855 : 4827 : auto reintersect = SetInfo(depgraph, prefix & intersect.transactions);
856 [ + + ]: 4827 : if (!reintersect.feerate.IsEmpty()) {
857 [ - + ]: 2196 : assert(reintersect.feerate <= intersect.feerate);
858 : : }
859 : : }
860 : :
861 : : // Find a subset to remove from linearization.
862 [ + - ]: 903 : auto done = ReadTopologicalSet(depgraph, todo, reader);
863 [ + + ]: 903 : 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 : 800 : done = depgraph.Ancestors(todo.First()) & todo;
867 : : }
868 : 903 : todo -= done;
869 : 903 : chunking.MarkDone(done);
870 : 903 : subset = SetInfo(depgraph, subset.transactions - done);
871 : 903 : }
872 : :
873 [ - + ]: 97 : assert(chunking.NumChunksLeft() == 0);
874 : 97 : }
875 : :
876 [ + - ]: 731 : 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 [ + + ]: 291 : SpanReader reader(buffer);
883 : 291 : DepGraph<TestBitSet> depgraph;
884 : 291 : uint64_t rng_seed{0};
885 : 291 : uint64_t iter_count{0};
886 : 291 : uint8_t make_connected{1};
887 : 291 : try {
888 [ + + + - : 291 : reader >> VARINT(iter_count) >> Using<DepGraphFormatter>(depgraph) >> rng_seed >> make_connected;
+ + + + ]
889 [ - + ]: 241 : } 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 [ + + + - ]: 291 : if (make_connected) MakeConnected(depgraph);
893 : :
894 : : // Optionally construct an old linearization for it.
895 : 291 : std::vector<DepGraphIndex> old_linearization;
896 : 291 : {
897 : 291 : uint8_t have_old_linearization{0};
898 : 291 : try {
899 [ + + ]: 291 : reader >> have_old_linearization;
900 [ - + ]: 200 : } catch(const std::ios_base::failure&) {}
901 [ + + ]: 291 : if (have_old_linearization & 1) {
902 [ + - ]: 154 : old_linearization = ReadLinearization(depgraph, reader);
903 : 77 : SanityCheck(depgraph, old_linearization);
904 : : }
905 : : }
906 : :
907 : : // Invoke Linearize().
908 : 291 : iter_count &= 0x7ffff;
909 : 291 : auto [linearization, optimal] = Linearize(depgraph, iter_count, rng_seed, old_linearization);
910 : 291 : SanityCheck(depgraph, linearization);
911 : 291 : auto chunking = ChunkLinearization(depgraph, linearization);
912 : :
913 : : // Linearization must always be as good as the old one, if provided.
914 [ + + ]: 291 : if (!old_linearization.empty()) {
915 : 76 : auto old_chunking = ChunkLinearization(depgraph, old_linearization);
916 [ + - ]: 76 : auto cmp = CompareChunks(chunking, old_chunking);
917 [ - + ]: 76 : assert(cmp >= 0);
918 : 76 : }
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 [ + + ]: 291 : const uint64_t n = depgraph.TxCount();
924 [ + + + + ]: 291 : if (n <= 19 && iter_count > (uint64_t{1} << n)) {
925 [ - + ]: 34 : 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 : 291 : 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 [ + - + + ]: 291 : if (n < std::size(MAX_OPTIMAL_ITERS) && iter_count >= MAX_OPTIMAL_ITERS[n]) {
937 [ + - ]: 67 : Assume(optimal);
938 : : }
939 : :
940 : : // If Linearize claims optimal result, run quality tests.
941 [ + + ]: 291 : if (optimal) {
942 : : // It must be as good as SimpleLinearize.
943 : 200 : auto [simple_linearization, simple_optimal] = SimpleLinearize(depgraph, MAX_SIMPLE_ITERATIONS);
944 : 200 : SanityCheck(depgraph, simple_linearization);
945 : 200 : auto simple_chunking = ChunkLinearization(depgraph, simple_linearization);
946 [ + - ]: 200 : auto cmp = CompareChunks(chunking, simple_chunking);
947 [ - + ]: 200 : assert(cmp >= 0);
948 : : // If SimpleLinearize finds the optimal result too, they must be equal (if not,
949 : : // SimpleLinearize is broken).
950 [ + + - + ]: 200 : if (simple_optimal) assert(cmp == 0);
951 : :
952 : : // Only for very small clusters, test every topologically-valid permutation.
953 [ + + ]: 200 : if (depgraph.TxCount() <= 7) {
954 : 41 : std::vector<DepGraphIndex> perm_linearization;
955 [ + + + - : 232 : for (DepGraphIndex i : depgraph.Positions()) perm_linearization.push_back(i);
+ + ]
956 : : // Iterate over all valid permutations.
957 : 43861 : do {
958 : : // Determine whether perm_linearization is topological.
959 : 43861 : TestBitSet perm_done;
960 : 43861 : bool perm_is_topo{true};
961 [ + + ]: 74789 : for (auto i : perm_linearization) {
962 : 73853 : perm_done.Set(i);
963 [ + + ]: 73853 : 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 [ + + ]: 43861 : if (perm_is_topo) {
970 : 936 : auto perm_chunking = ChunkLinearization(depgraph, perm_linearization);
971 [ + - ]: 936 : auto cmp = CompareChunks(chunking, perm_chunking);
972 [ - + ]: 936 : assert(cmp >= 0);
973 : 936 : }
974 [ + + ]: 43861 : } while(std::next_permutation(perm_linearization.begin(), perm_linearization.end()));
975 : 41 : }
976 : 200 : }
977 : 291 : }
978 : :
979 [ + - ]: 514 : FUZZ_TARGET(clusterlin_postlinearize)
980 : : {
981 : : // Verify expected properties of PostLinearize() on arbitrary linearizations.
982 : :
983 : : // Retrieve a depgraph from the fuzz input.
984 [ + - ]: 74 : SpanReader reader(buffer);
985 : 74 : DepGraph<TestBitSet> depgraph;
986 : 74 : try {
987 [ + - ]: 74 : reader >> Using<DepGraphFormatter>(depgraph);
988 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
989 : :
990 : : // Retrieve a linearization from the fuzz input.
991 : 74 : std::vector<DepGraphIndex> linearization;
992 [ + - ]: 148 : linearization = ReadLinearization(depgraph, reader);
993 : 74 : SanityCheck(depgraph, linearization);
994 : :
995 : : // Produce a post-processed version.
996 [ + - ]: 74 : auto post_linearization = linearization;
997 [ + - ]: 74 : PostLinearize(depgraph, post_linearization);
998 : 74 : SanityCheck(depgraph, post_linearization);
999 : :
1000 : : // Compare diagrams: post-linearization cannot worsen anywhere.
1001 : 74 : auto chunking = ChunkLinearization(depgraph, linearization);
1002 : 74 : auto post_chunking = ChunkLinearization(depgraph, post_linearization);
1003 [ + - ]: 74 : auto cmp = CompareChunks(post_chunking, chunking);
1004 [ - + ]: 74 : assert(cmp >= 0);
1005 : :
1006 : : // Run again, things can keep improving (and never get worse)
1007 [ + - ]: 74 : auto post_post_linearization = post_linearization;
1008 [ + - ]: 74 : PostLinearize(depgraph, post_post_linearization);
1009 : 74 : SanityCheck(depgraph, post_post_linearization);
1010 : 74 : auto post_post_chunking = ChunkLinearization(depgraph, post_post_linearization);
1011 [ + - ]: 74 : cmp = CompareChunks(post_post_chunking, post_chunking);
1012 [ - + ]: 74 : assert(cmp >= 0);
1013 : :
1014 : : // The chunks that come out of postlinearizing are always connected.
1015 : 74 : LinearizationChunking linchunking(depgraph, post_linearization);
1016 [ + + ]: 680 : while (linchunking.NumChunksLeft()) {
1017 [ - + ]: 532 : assert(depgraph.IsConnected(linchunking.GetChunk(0).transactions));
1018 : 532 : linchunking.MarkDone(linchunking.GetChunk(0).transactions);
1019 : : }
1020 : 74 : }
1021 : :
1022 [ + - ]: 698 : 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 [ + - ]: 258 : SpanReader reader(buffer);
1029 : 258 : uint64_t rng_seed{0};
1030 : 258 : DepGraph<TestBitSet> depgraph_gen;
1031 : 258 : uint8_t direction{0};
1032 : 258 : try {
1033 [ + - + + : 258 : 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 : 258 : DepGraph<TestBitSet> depgraph_tree;
1039 [ + + ]: 7699 : for (DepGraphIndex i = 0; i < depgraph_gen.PositionRange(); ++i) {
1040 [ + + ]: 7441 : if (depgraph_gen.Positions()[i]) {
1041 : 5988 : 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 : 1453 : depgraph_tree.AddTransaction(FeeFrac{});
1046 : : }
1047 : : }
1048 : 258 : depgraph_tree.RemoveTransactions(TestBitSet::Fill(depgraph_gen.PositionRange()) - depgraph_gen.Positions());
1049 : :
1050 [ + + ]: 258 : if (direction & 1) {
1051 [ + + ]: 3791 : for (DepGraphIndex i = 0; i < depgraph_gen.TxCount(); ++i) {
1052 : 3631 : auto children = depgraph_gen.GetReducedChildren(i);
1053 [ + + ]: 3631 : if (children.Any()) {
1054 : 2197 : depgraph_tree.AddDependencies(TestBitSet::Singleton(i), children.First());
1055 : : }
1056 : : }
1057 : : } else {
1058 [ + + ]: 2455 : for (DepGraphIndex i = 0; i < depgraph_gen.TxCount(); ++i) {
1059 : 2357 : auto parents = depgraph_gen.GetReducedParents(i);
1060 [ + + ]: 2357 : if (parents.Any()) {
1061 : 845 : depgraph_tree.AddDependencies(TestBitSet::Singleton(parents.First()), i);
1062 : : }
1063 : : }
1064 : : }
1065 : :
1066 : : // Retrieve a linearization from the fuzz input.
1067 : 258 : std::vector<DepGraphIndex> linearization;
1068 [ + - ]: 516 : linearization = ReadLinearization(depgraph_tree, reader);
1069 : 258 : SanityCheck(depgraph_tree, linearization);
1070 : :
1071 : : // Produce a postlinearized version.
1072 [ + - ]: 258 : auto post_linearization = linearization;
1073 [ + - ]: 258 : PostLinearize(depgraph_tree, post_linearization);
1074 : 258 : SanityCheck(depgraph_tree, post_linearization);
1075 : :
1076 : : // Compare diagrams.
1077 : 258 : auto chunking = ChunkLinearization(depgraph_tree, linearization);
1078 : 258 : auto post_chunking = ChunkLinearization(depgraph_tree, post_linearization);
1079 [ + - ]: 258 : auto cmp = CompareChunks(post_chunking, chunking);
1080 [ - + ]: 258 : 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 [ + - ]: 258 : auto post_post_linearization = post_linearization;
1085 [ + - ]: 258 : PostLinearize(depgraph_tree, post_linearization);
1086 : 258 : SanityCheck(depgraph_tree, post_linearization);
1087 : 258 : auto post_post_chunking = ChunkLinearization(depgraph_tree, post_post_linearization);
1088 [ + - ]: 258 : auto cmp_post = CompareChunks(post_post_chunking, post_chunking);
1089 [ - + ]: 258 : 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 : 258 : auto [opt_linearization, _optimal] = Linearize(depgraph_tree, 100000, rng_seed, post_linearization);
1094 : 258 : auto opt_chunking = ChunkLinearization(depgraph_tree, opt_linearization);
1095 [ + - ]: 258 : auto cmp_opt = CompareChunks(opt_chunking, post_chunking);
1096 [ - + ]: 258 : assert(cmp_opt == 0);
1097 : 258 : }
1098 : :
1099 [ + - ]: 515 : 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 [ + - ]: 75 : SpanReader reader(buffer);
1109 : 75 : DepGraph<TestBitSet> depgraph;
1110 : 75 : int32_t fee_inc{0};
1111 : 75 : try {
1112 : 75 : uint64_t fee_inc_code;
1113 [ + - + + ]: 75 : reader >> Using<DepGraphFormatter>(depgraph) >> VARINT(fee_inc_code);
1114 : 21 : fee_inc = fee_inc_code & 0x3ffff;
1115 [ - + ]: 54 : } catch (const std::ios_base::failure&) {}
1116 [ + + ]: 75 : if (depgraph.TxCount() == 0) return;
1117 : :
1118 : : // Retrieve two linearizations from the fuzz input.
1119 [ + - ]: 68 : auto lin = ReadLinearization(depgraph, reader);
1120 [ + - ]: 68 : 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 : 68 : std::vector<DepGraphIndex> lin_moved;
1125 [ + + ]: 870 : for (auto i : lin) {
1126 [ + + + - ]: 802 : if (i != lin_leaf.back()) lin_moved.push_back(i);
1127 : : }
1128 [ + - ]: 68 : lin_moved.push_back(lin_leaf.back());
1129 : :
1130 : : // Postlinearize lin_moved.
1131 [ + - ]: 68 : PostLinearize(depgraph, lin_moved);
1132 : 68 : SanityCheck(depgraph, lin_moved);
1133 : :
1134 : : // Compare diagrams (applying the fee delta after computing the old one).
1135 : 68 : auto old_chunking = ChunkLinearization(depgraph, lin);
1136 : 68 : depgraph.FeeRate(lin_leaf.back()).fee += fee_inc;
1137 : 68 : auto new_chunking = ChunkLinearization(depgraph, lin_moved);
1138 [ + - ]: 68 : auto cmp = CompareChunks(new_chunking, old_chunking);
1139 [ - + ]: 68 : assert(cmp >= 0);
1140 : 75 : }
1141 : :
1142 [ + - ]: 567 : FUZZ_TARGET(clusterlin_merge)
1143 : : {
1144 : : // Construct an arbitrary graph from the fuzz input.
1145 [ + - ]: 127 : SpanReader reader(buffer);
1146 : 127 : DepGraph<TestBitSet> depgraph;
1147 : 127 : try {
1148 [ + - ]: 127 : reader >> Using<DepGraphFormatter>(depgraph);
1149 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
1150 : :
1151 : : // Retrieve two linearizations from the fuzz input.
1152 [ + - ]: 127 : auto lin1 = ReadLinearization(depgraph, reader);
1153 [ + - ]: 127 : auto lin2 = ReadLinearization(depgraph, reader);
1154 : :
1155 : : // Merge the two.
1156 [ + - ]: 127 : auto lin_merged = MergeLinearizations(depgraph, lin1, lin2);
1157 : :
1158 : : // Compute chunkings and compare.
1159 : 127 : auto chunking1 = ChunkLinearization(depgraph, lin1);
1160 : 127 : auto chunking2 = ChunkLinearization(depgraph, lin2);
1161 : 127 : auto chunking_merged = ChunkLinearization(depgraph, lin_merged);
1162 [ + - ]: 127 : auto cmp1 = CompareChunks(chunking_merged, chunking1);
1163 [ - + ]: 127 : assert(cmp1 >= 0);
1164 [ + - ]: 127 : auto cmp2 = CompareChunks(chunking_merged, chunking2);
1165 [ - + ]: 127 : assert(cmp2 >= 0);
1166 : 127 : }
1167 : :
1168 [ + - ]: 440 : 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 [ # # ]: 0 : SpanReader reader(buffer);
1174 : 0 : DepGraph<TestBitSet> depgraph;
1175 : 0 : try {
1176 [ # # ]: 0 : reader >> Using<DepGraphFormatter>(depgraph);
1177 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
1178 : :
1179 : : // Construct an arbitrary linearization (not necessarily topological for depgraph).
1180 : 0 : std::vector<DepGraphIndex> linearization;
1181 : : /** Which transactions of depgraph are yet to be included in linearization. */
1182 : 0 : TestBitSet todo = depgraph.Positions();
1183 [ # # ]: 0 : while (todo.Any()) {
1184 : : // Read a number from the fuzz input in range [0, todo.Count()).
1185 : 0 : uint64_t val{0};
1186 : 0 : try {
1187 [ # # ]: 0 : reader >> VARINT(val);
1188 [ - - ]: 0 : } catch (const std::ios_base::failure&) {}
1189 [ # # ]: 0 : val %= todo.Count();
1190 : : // Find the val'th element in todo, remove it from todo, and append it to linearization.
1191 [ # # # # ]: 0 : for (auto idx : todo) {
1192 [ # # ]: 0 : if (val == 0) {
1193 [ # # ]: 0 : linearization.push_back(idx);
1194 : 0 : todo.Reset(idx);
1195 : 0 : break;
1196 : : }
1197 : 0 : --val;
1198 : : }
1199 : : }
1200 [ # # ]: 0 : 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 : 0 : size_t topo_prefix = 0;
1206 : 0 : todo = depgraph.Positions();
1207 [ # # ]: 0 : while (topo_prefix < linearization.size()) {
1208 : 0 : DepGraphIndex idx = linearization[topo_prefix];
1209 : 0 : todo.Reset(idx);
1210 [ # # ]: 0 : if (todo.Overlaps(depgraph.Ancestors(idx))) break;
1211 : 0 : ++topo_prefix;
1212 : : }
1213 : :
1214 : : // Then make a fixed copy of linearization.
1215 [ # # ]: 0 : auto linearization_fixed = linearization;
1216 : 0 : FixLinearization(depgraph, linearization_fixed);
1217 : : // Sanity check it (which includes testing whether it is topological).
1218 : 0 : SanityCheck(depgraph, linearization_fixed);
1219 : :
1220 : : // FixLinearization does not modify the topological prefix of linearization.
1221 [ # # ]: 0 : 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 [ # # ]: 0 : if (topo_prefix == linearization.size()) {
1226 [ # # ]: 0 : assert(linearization == linearization_fixed);
1227 : : }
1228 : 0 : }
|
