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