Bitcoin Core 29.99.0
P2P Digital Currency
txgraph.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>
7#include <test/fuzz/fuzz.h>
9#include <test/util/random.h>
10#include <txgraph.h>
11#include <util/bitset.h>
12#include <util/feefrac.h>
13
14#include <algorithm>
15#include <cstdint>
16#include <iterator>
17#include <map>
18#include <memory>
19#include <set>
20#include <utility>
21
22using namespace cluster_linearize;
23
24namespace {
25
29struct SimTxGraph
30{
34 static constexpr unsigned MAX_TRANSACTIONS = MAX_CLUSTER_COUNT_LIMIT * 2;
36 using SetType = BitSet<MAX_TRANSACTIONS>;
38 using Pos = DepGraphIndex;
40 static constexpr auto MISSING = Pos(-1);
41
48 std::array<std::shared_ptr<TxGraph::Ref>, MAX_TRANSACTIONS> simmap;
50 std::map<const TxGraph::Ref*, Pos> simrevmap;
52 std::vector<std::shared_ptr<TxGraph::Ref>> removed;
54 std::optional<bool> oversized;
56 DepGraphIndex max_cluster_count;
59 SetType modified;
61 uint64_t max_cluster_size;
63 bool real_is_optimal{false};
64
66 explicit SimTxGraph(DepGraphIndex cluster_count, uint64_t cluster_size) :
67 max_cluster_count(cluster_count), max_cluster_size(cluster_size) {}
68
69 // Permit copying and moving.
70 SimTxGraph(const SimTxGraph&) noexcept = default;
71 SimTxGraph& operator=(const SimTxGraph&) noexcept = default;
72 SimTxGraph(SimTxGraph&&) noexcept = default;
73 SimTxGraph& operator=(SimTxGraph&&) noexcept = default;
74
76 std::vector<SetType> GetComponents()
77 {
78 auto todo = graph.Positions();
79 std::vector<SetType> ret;
80 // Iterate over all connected components of the graph.
81 while (todo.Any()) {
82 auto component = graph.FindConnectedComponent(todo);
83 ret.push_back(component);
84 todo -= component;
85 }
86 return ret;
87 }
88
91 bool IsOversized()
92 {
93 if (!oversized.has_value()) {
94 // Only recompute when oversized isn't already known.
95 oversized = false;
96 for (auto component : GetComponents()) {
97 if (component.Count() > max_cluster_count) oversized = true;
98 uint64_t component_size{0};
99 for (auto i : component) component_size += graph.FeeRate(i).size;
100 if (component_size > max_cluster_size) oversized = true;
101 }
102 }
103 return *oversized;
104 }
105
106 void MakeModified(DepGraphIndex index)
107 {
108 modified |= graph.GetConnectedComponent(graph.Positions(), index);
109 }
110
112 DepGraphIndex GetTransactionCount() const { return graph.TxCount(); }
113
115 FeePerWeight SumAll() const
116 {
118 for (auto i : graph.Positions()) {
119 ret += graph.FeeRate(i);
120 }
121 return ret;
122 }
123
125 Pos Find(const TxGraph::Ref* ref) const
126 {
127 auto it = simrevmap.find(ref);
128 if (it != simrevmap.end()) return it->second;
129 return MISSING;
130 }
131
133 TxGraph::Ref* GetRef(Pos pos)
134 {
135 assert(graph.Positions()[pos]);
136 assert(simmap[pos]);
137 return simmap[pos].get();
138 }
139
141 TxGraph::Ref* AddTransaction(const FeePerWeight& feerate)
142 {
143 assert(graph.TxCount() < MAX_TRANSACTIONS);
144 auto simpos = graph.AddTransaction(feerate);
145 real_is_optimal = false;
146 MakeModified(simpos);
147 assert(graph.Positions()[simpos]);
148 simmap[simpos] = std::make_shared<TxGraph::Ref>();
149 auto ptr = simmap[simpos].get();
150 simrevmap[ptr] = simpos;
151 // This may invalidate our cached oversized value.
152 if (oversized.has_value() && !*oversized) oversized = std::nullopt;
153 return ptr;
154 }
155
157 void AddDependency(TxGraph::Ref* parent, TxGraph::Ref* child)
158 {
159 auto par_pos = Find(parent);
160 if (par_pos == MISSING) return;
161 auto chl_pos = Find(child);
162 if (chl_pos == MISSING) return;
163 graph.AddDependencies(SetType::Singleton(par_pos), chl_pos);
164 MakeModified(par_pos);
165 real_is_optimal = false;
166 // This may invalidate our cached oversized value.
167 if (oversized.has_value() && !*oversized) oversized = std::nullopt;
168 }
169
171 void SetTransactionFee(TxGraph::Ref* ref, int64_t fee)
172 {
173 auto pos = Find(ref);
174 if (pos == MISSING) return;
175 // No need to invoke MakeModified, because this equally affects main and staging.
176 real_is_optimal = false;
177 graph.FeeRate(pos).fee = fee;
178 }
179
181 void RemoveTransaction(TxGraph::Ref* ref)
182 {
183 auto pos = Find(ref);
184 if (pos == MISSING) return;
185 MakeModified(pos);
186 real_is_optimal = false;
187 graph.RemoveTransactions(SetType::Singleton(pos));
188 simrevmap.erase(simmap[pos].get());
189 // Retain the TxGraph::Ref corresponding to this position, so the Ref destruction isn't
190 // invoked until the simulation explicitly decided to do so.
191 removed.push_back(std::move(simmap[pos]));
192 simmap[pos].reset();
193 // This may invalidate our cached oversized value.
194 if (oversized.has_value() && *oversized) oversized = std::nullopt;
195 }
196
201 void DestroyTransaction(TxGraph::Ref* ref, bool reset_oversize)
202 {
203 auto pos = Find(ref);
204 if (pos == MISSING) {
205 // Wipe the ref, if it exists, from the removed vector. Use std::partition rather
206 // than std::erase because we don't care about the order of the entries that
207 // remain.
208 auto remove = std::partition(removed.begin(), removed.end(), [&](auto& arg) { return arg.get() != ref; });
209 removed.erase(remove, removed.end());
210 } else {
211 MakeModified(pos);
212 graph.RemoveTransactions(SetType::Singleton(pos));
213 real_is_optimal = false;
214 simrevmap.erase(simmap[pos].get());
215 simmap[pos].reset();
216 // This may invalidate our cached oversized value.
217 if (reset_oversize && oversized.has_value() && *oversized) {
218 oversized = std::nullopt;
219 }
220 }
221 }
222
225 SetType MakeSet(std::span<TxGraph::Ref* const> arg)
226 {
227 SetType ret;
228 for (TxGraph::Ref* ptr : arg) {
229 auto pos = Find(ptr);
230 assert(pos != Pos(-1));
231 ret.Set(pos);
232 }
233 return ret;
234 }
235
237 SetType GetAncDesc(TxGraph::Ref* arg, bool desc)
238 {
239 auto pos = Find(arg);
240 if (pos == MISSING) return {};
241 return desc ? graph.Descendants(pos) : graph.Ancestors(pos);
242 }
243
246 void IncludeAncDesc(std::vector<TxGraph::Ref*>& arg, bool desc)
247 {
248 std::vector<TxGraph::Ref*> ret;
249 for (auto ptr : arg) {
250 auto simpos = Find(ptr);
251 if (simpos != MISSING) {
252 for (auto i : desc ? graph.Descendants(simpos) : graph.Ancestors(simpos)) {
253 ret.push_back(simmap[i].get());
254 }
255 } else {
256 ret.push_back(ptr);
257 }
258 }
259 // Construct deduplicated version in input (do not use std::sort/std::unique for
260 // deduplication as it'd rely on non-deterministic pointer comparison).
261 arg.clear();
262 for (auto ptr : ret) {
263 if (std::find(arg.begin(), arg.end(), ptr) == arg.end()) {
264 arg.push_back(ptr);
265 }
266 }
267 }
268
269
272 bool MatchesOversizedClusters(const SetType& set)
273 {
274 if (set.Any() && !IsOversized()) return false;
275
276 auto todo = graph.Positions();
277 if (!set.IsSubsetOf(todo)) return false;
278
279 // Walk all clusters, and make sure all of set doesn't come from non-oversized clusters
280 while (todo.Any()) {
281 auto component = graph.FindConnectedComponent(todo);
282 // Determine whether component is oversized, due to either the size or count limit.
283 bool is_oversized = component.Count() > max_cluster_count;
284 uint64_t component_size{0};
285 for (auto i : component) component_size += graph.FeeRate(i).size;
286 is_oversized |= component_size > max_cluster_size;
287 // Check whether overlap with set matches is_oversized.
288 if (is_oversized != set.Overlaps(component)) return false;
289 todo -= component;
290 }
291 return true;
292 }
293};
294
295} // namespace
296
298{
299 // This is a big simulation test for TxGraph, which performs a fuzz-derived sequence of valid
300 // operations on a TxGraph instance, as well as on a simpler (mostly) reimplementation (see
301 // SimTxGraph above), comparing the outcome of functions that return a result, and finally
302 // performing a full comparison between the two.
303
305 FuzzedDataProvider provider(buffer.data(), buffer.size());
306
310 InsecureRandomContext rng(provider.ConsumeIntegral<uint64_t>());
311
313 TxGraph::Ref empty_ref;
314
317 auto max_cluster_count = provider.ConsumeIntegralInRange<DepGraphIndex>(1, MAX_CLUSTER_COUNT_LIMIT);
319 auto max_cluster_size = provider.ConsumeIntegralInRange<uint64_t>(1, 0x3fffff * MAX_CLUSTER_COUNT_LIMIT);
321 auto acceptable_iters = provider.ConsumeIntegralInRange<uint64_t>(0, 10000);
322
323 // Construct a real graph, and a vector of simulated graphs (main, and possibly staging).
324 auto real = MakeTxGraph(max_cluster_count, max_cluster_size, acceptable_iters);
325 std::vector<SimTxGraph> sims;
326 sims.reserve(2);
327 sims.emplace_back(max_cluster_count, max_cluster_size);
328
330 struct BlockBuilderData
331 {
333 std::unique_ptr<TxGraph::BlockBuilder> builder;
335 SimTxGraph::SetType included;
337 SimTxGraph::SetType done;
339 FeePerWeight last_feerate;
340
341 BlockBuilderData(std::unique_ptr<TxGraph::BlockBuilder> builder_in) : builder(std::move(builder_in)) {}
342 };
343
345 std::vector<BlockBuilderData> block_builders;
346
349 auto pick_fn = [&]() noexcept -> TxGraph::Ref* {
350 size_t tx_count[2] = {sims[0].GetTransactionCount(), 0};
352 size_t choices = tx_count[0] + sims[0].removed.size() + 1;
353 if (sims.size() == 2) {
354 tx_count[1] = sims[1].GetTransactionCount();
355 choices += tx_count[1] + sims[1].removed.size();
356 }
358 auto choice = provider.ConsumeIntegralInRange<size_t>(0, choices - 1);
359 // Consider both main and (if it exists) staging.
360 for (size_t level = 0; level < sims.size(); ++level) {
361 auto& sim = sims[level];
362 if (choice < tx_count[level]) {
363 // Return from graph.
364 for (auto i : sim.graph.Positions()) {
365 if (choice == 0) return sim.GetRef(i);
366 --choice;
367 }
368 assert(false);
369 } else {
370 choice -= tx_count[level];
371 }
372 if (choice < sim.removed.size()) {
373 // Return from removed.
374 return sim.removed[choice].get();
375 } else {
376 choice -= sim.removed.size();
377 }
378 }
379 // Return empty.
380 assert(choice == 0);
381 return &empty_ref;
382 };
383
386 auto get_diagram_fn = [&](bool main_only) -> std::vector<FeeFrac> {
387 int level = main_only ? 0 : sims.size() - 1;
388 auto& sim = sims[level];
389 // For every transaction in the graph, request its cluster, and throw them into a set.
390 std::set<std::vector<TxGraph::Ref*>> clusters;
391 for (auto i : sim.graph.Positions()) {
392 auto ref = sim.GetRef(i);
393 clusters.insert(real->GetCluster(*ref, main_only));
394 }
395 // Compute the chunkings of each (deduplicated) cluster.
396 size_t num_tx{0};
397 std::vector<FeeFrac> chunk_feerates;
398 for (const auto& cluster : clusters) {
399 num_tx += cluster.size();
400 std::vector<SimTxGraph::Pos> linearization;
401 linearization.reserve(cluster.size());
402 for (auto refptr : cluster) linearization.push_back(sim.Find(refptr));
403 for (const FeeFrac& chunk_feerate : ChunkLinearization(sim.graph, linearization)) {
404 chunk_feerates.push_back(chunk_feerate);
405 }
406 }
407 // Verify the number of transactions after deduplicating clusters. This implicitly verifies
408 // that GetCluster on each element of a cluster reports the cluster transactions in the same
409 // order.
410 assert(num_tx == sim.GetTransactionCount());
411 // Sort by feerate only, since violating topological constraints within same-feerate
412 // chunks won't affect diagram comparisons.
413 std::sort(chunk_feerates.begin(), chunk_feerates.end(), std::greater{});
414 return chunk_feerates;
415 };
416
417 LIMITED_WHILE(provider.remaining_bytes() > 0, 200) {
418 // Read a one-byte command.
419 int command = provider.ConsumeIntegral<uint8_t>();
420 int orig_command = command;
421
422 // Treat the lowest bit of a command as a flag (which selects a variant of some of the
423 // operations), and the second-lowest bit as a way of selecting main vs. staging, and leave
424 // the rest of the bits in command.
425 bool alt = command & 1;
426 bool use_main = command & 2;
427 command >>= 2;
428
432 int builder_idx = block_builders.empty() ? -1 : int((orig_command & 3) % block_builders.size());
433
434 // Provide convenient aliases for the top simulated graph (main, or staging if it exists),
435 // one for the simulated graph selected based on use_main (for operations that can operate
436 // on both graphs), and one that always refers to the main graph.
437 auto& top_sim = sims.back();
438 auto& sel_sim = use_main ? sims[0] : top_sim;
439 auto& main_sim = sims[0];
440
441 // Keep decrementing command for each applicable operation, until one is hit. Multiple
442 // iterations may be necessary.
443 while (true) {
444 if ((block_builders.empty() || sims.size() > 1) && top_sim.GetTransactionCount() < SimTxGraph::MAX_TRANSACTIONS && command-- == 0) {
445 // AddTransaction.
446 int64_t fee;
447 int32_t size;
448 if (alt) {
449 // If alt is true, pick fee and size from the entire range.
450 fee = provider.ConsumeIntegralInRange<int64_t>(-0x8000000000000, 0x7ffffffffffff);
451 size = provider.ConsumeIntegralInRange<int32_t>(1, 0x3fffff);
452 } else {
453 // Otherwise, use smaller range which consume fewer fuzz input bytes, as just
454 // these are likely sufficient to trigger all interesting code paths already.
455 fee = provider.ConsumeIntegral<uint8_t>();
456 size = provider.ConsumeIntegralInRange<uint32_t>(1, 0xff);
457 }
458 FeePerWeight feerate{fee, size};
459 // Create a real TxGraph::Ref.
460 auto ref = real->AddTransaction(feerate);
461 // Create a shared_ptr place in the simulation to put the Ref in.
462 auto ref_loc = top_sim.AddTransaction(feerate);
463 // Move it in place.
464 *ref_loc = std::move(ref);
465 break;
466 } else if ((block_builders.empty() || sims.size() > 1) && top_sim.GetTransactionCount() + top_sim.removed.size() > 1 && command-- == 0) {
467 // AddDependency.
468 auto par = pick_fn();
469 auto chl = pick_fn();
470 auto pos_par = top_sim.Find(par);
471 auto pos_chl = top_sim.Find(chl);
472 if (pos_par != SimTxGraph::MISSING && pos_chl != SimTxGraph::MISSING) {
473 // Determine if adding this would introduce a cycle (not allowed by TxGraph),
474 // and if so, skip.
475 if (top_sim.graph.Ancestors(pos_par)[pos_chl]) break;
476 }
477 top_sim.AddDependency(par, chl);
478 top_sim.real_is_optimal = false;
479 real->AddDependency(*par, *chl);
480 break;
481 } else if ((block_builders.empty() || sims.size() > 1) && top_sim.removed.size() < 100 && command-- == 0) {
482 // RemoveTransaction. Either all its ancestors or all its descendants are also
483 // removed (if any), to make sure TxGraph's reordering of removals and dependencies
484 // has no effect.
485 std::vector<TxGraph::Ref*> to_remove;
486 to_remove.push_back(pick_fn());
487 top_sim.IncludeAncDesc(to_remove, alt);
488 // The order in which these ancestors/descendants are removed should not matter;
489 // randomly shuffle them.
490 std::shuffle(to_remove.begin(), to_remove.end(), rng);
491 for (TxGraph::Ref* ptr : to_remove) {
492 real->RemoveTransaction(*ptr);
493 top_sim.RemoveTransaction(ptr);
494 }
495 break;
496 } else if (sel_sim.removed.size() > 0 && command-- == 0) {
497 // ~Ref (of an already-removed transaction). Destroying a TxGraph::Ref has an
498 // observable effect on the TxGraph it refers to, so this simulation permits doing
499 // so separately from other actions on TxGraph.
500
501 // Pick a Ref of sel_sim.removed to destroy. Note that the same Ref may still occur
502 // in the other graph, and thus not actually trigger ~Ref yet (which is exactly
503 // what we want, as destroying Refs is only allowed when it does not refer to an
504 // existing transaction in either graph).
505 auto removed_pos = provider.ConsumeIntegralInRange<size_t>(0, sel_sim.removed.size() - 1);
506 if (removed_pos != sel_sim.removed.size() - 1) {
507 std::swap(sel_sim.removed[removed_pos], sel_sim.removed.back());
508 }
509 sel_sim.removed.pop_back();
510 break;
511 } else if (block_builders.empty() && command-- == 0) {
512 // ~Ref (of any transaction).
513 std::vector<TxGraph::Ref*> to_destroy;
514 to_destroy.push_back(pick_fn());
515 while (true) {
516 // Keep adding either the ancestors or descendants the already picked
517 // transactions have in both graphs (main and staging) combined. Destroying
518 // will trigger deletions in both, so to have consistent TxGraph behavior, the
519 // set must be closed under ancestors, or descendants, in both graphs.
520 auto old_size = to_destroy.size();
521 for (auto& sim : sims) sim.IncludeAncDesc(to_destroy, alt);
522 if (to_destroy.size() == old_size) break;
523 }
524 // The order in which these ancestors/descendants are destroyed should not matter;
525 // randomly shuffle them.
526 std::shuffle(to_destroy.begin(), to_destroy.end(), rng);
527 for (TxGraph::Ref* ptr : to_destroy) {
528 for (size_t level = 0; level < sims.size(); ++level) {
529 sims[level].DestroyTransaction(ptr, level == sims.size() - 1);
530 }
531 }
532 break;
533 } else if (block_builders.empty() && command-- == 0) {
534 // SetTransactionFee.
535 int64_t fee;
536 if (alt) {
537 fee = provider.ConsumeIntegralInRange<int64_t>(-0x8000000000000, 0x7ffffffffffff);
538 } else {
539 fee = provider.ConsumeIntegral<uint8_t>();
540 }
541 auto ref = pick_fn();
542 real->SetTransactionFee(*ref, fee);
543 for (auto& sim : sims) {
544 sim.SetTransactionFee(ref, fee);
545 }
546 break;
547 } else if (command-- == 0) {
548 // GetTransactionCount.
549 assert(real->GetTransactionCount(use_main) == sel_sim.GetTransactionCount());
550 break;
551 } else if (command-- == 0) {
552 // Exists.
553 auto ref = pick_fn();
554 bool exists = real->Exists(*ref, use_main);
555 bool should_exist = sel_sim.Find(ref) != SimTxGraph::MISSING;
556 assert(exists == should_exist);
557 break;
558 } else if (command-- == 0) {
559 // IsOversized.
560 assert(sel_sim.IsOversized() == real->IsOversized(use_main));
561 break;
562 } else if (command-- == 0) {
563 // GetIndividualFeerate.
564 auto ref = pick_fn();
565 auto feerate = real->GetIndividualFeerate(*ref);
566 bool found{false};
567 for (auto& sim : sims) {
568 auto simpos = sim.Find(ref);
569 if (simpos != SimTxGraph::MISSING) {
570 found = true;
571 assert(feerate == sim.graph.FeeRate(simpos));
572 }
573 }
574 if (!found) assert(feerate.IsEmpty());
575 break;
576 } else if (!main_sim.IsOversized() && command-- == 0) {
577 // GetMainChunkFeerate.
578 auto ref = pick_fn();
579 auto feerate = real->GetMainChunkFeerate(*ref);
580 auto simpos = main_sim.Find(ref);
581 if (simpos == SimTxGraph::MISSING) {
582 assert(feerate.IsEmpty());
583 } else {
584 // Just do some quick checks that the reported value is in range. A full
585 // recomputation of expected chunk feerates is done at the end.
586 assert(feerate.size >= main_sim.graph.FeeRate(simpos).size);
587 assert(feerate.size <= main_sim.SumAll().size);
588 }
589 break;
590 } else if (!sel_sim.IsOversized() && command-- == 0) {
591 // GetAncestors/GetDescendants.
592 auto ref = pick_fn();
593 auto result = alt ? real->GetDescendants(*ref, use_main)
594 : real->GetAncestors(*ref, use_main);
595 assert(result.size() <= max_cluster_count);
596 auto result_set = sel_sim.MakeSet(result);
597 assert(result.size() == result_set.Count());
598 auto expect_set = sel_sim.GetAncDesc(ref, alt);
599 assert(result_set == expect_set);
600 break;
601 } else if (!sel_sim.IsOversized() && command-- == 0) {
602 // GetAncestorsUnion/GetDescendantsUnion.
603 std::vector<TxGraph::Ref*> refs;
604 // Gather a list of up to 15 Ref pointers.
605 auto count = provider.ConsumeIntegralInRange<size_t>(0, 15);
606 refs.resize(count);
607 for (size_t i = 0; i < count; ++i) {
608 refs[i] = pick_fn();
609 }
610 // Their order should not matter, shuffle them.
611 std::shuffle(refs.begin(), refs.end(), rng);
612 // Invoke the real function, and convert to SimPos set.
613 auto result = alt ? real->GetDescendantsUnion(refs, use_main)
614 : real->GetAncestorsUnion(refs, use_main);
615 auto result_set = sel_sim.MakeSet(result);
616 assert(result.size() == result_set.Count());
617 // Compute the expected result.
618 SimTxGraph::SetType expect_set;
619 for (TxGraph::Ref* ref : refs) expect_set |= sel_sim.GetAncDesc(ref, alt);
620 // Compare.
621 assert(result_set == expect_set);
622 break;
623 } else if (!sel_sim.IsOversized() && command-- == 0) {
624 // GetCluster.
625 auto ref = pick_fn();
626 auto result = real->GetCluster(*ref, use_main);
627 // Check cluster count limit.
628 assert(result.size() <= max_cluster_count);
629 // Require the result to be topologically valid and not contain duplicates.
630 auto left = sel_sim.graph.Positions();
631 uint64_t total_size{0};
632 for (auto refptr : result) {
633 auto simpos = sel_sim.Find(refptr);
634 total_size += sel_sim.graph.FeeRate(simpos).size;
635 assert(simpos != SimTxGraph::MISSING);
636 assert(left[simpos]);
637 left.Reset(simpos);
638 assert(!sel_sim.graph.Ancestors(simpos).Overlaps(left));
639 }
640 // Check cluster size limit.
641 assert(total_size <= max_cluster_size);
642 // Require the set to be connected.
643 auto result_set = sel_sim.MakeSet(result);
644 assert(sel_sim.graph.IsConnected(result_set));
645 // If ref exists, the result must contain it. If not, it must be empty.
646 auto simpos = sel_sim.Find(ref);
647 if (simpos != SimTxGraph::MISSING) {
648 assert(result_set[simpos]);
649 } else {
650 assert(result_set.None());
651 }
652 // Require the set not to have ancestors or descendants outside of it.
653 for (auto i : result_set) {
654 assert(sel_sim.graph.Ancestors(i).IsSubsetOf(result_set));
655 assert(sel_sim.graph.Descendants(i).IsSubsetOf(result_set));
656 }
657 break;
658 } else if (command-- == 0) {
659 // HaveStaging.
660 assert((sims.size() == 2) == real->HaveStaging());
661 break;
662 } else if (sims.size() < 2 && command-- == 0) {
663 // StartStaging.
664 sims.emplace_back(sims.back());
665 sims.back().modified = SimTxGraph::SetType{};
666 real->StartStaging();
667 break;
668 } else if (block_builders.empty() && sims.size() > 1 && command-- == 0) {
669 // CommitStaging.
670 real->CommitStaging();
671 // Resulting main level is only guaranteed to be optimal if all levels are
672 const bool main_optimal = std::all_of(sims.cbegin(), sims.cend(), [](const auto &sim) { return sim.real_is_optimal; });
673 sims.erase(sims.begin());
674 sims.front().real_is_optimal = main_optimal;
675 break;
676 } else if (sims.size() > 1 && command-- == 0) {
677 // AbortStaging.
678 real->AbortStaging();
679 sims.pop_back();
680 // Reset the cached oversized value (if TxGraph::Ref destructions triggered
681 // removals of main transactions while staging was active, then aborting will
682 // cause it to be re-evaluated in TxGraph).
683 sims.back().oversized = std::nullopt;
684 break;
685 } else if (!main_sim.IsOversized() && command-- == 0) {
686 // CompareMainOrder.
687 auto ref_a = pick_fn();
688 auto ref_b = pick_fn();
689 auto sim_a = main_sim.Find(ref_a);
690 auto sim_b = main_sim.Find(ref_b);
691 // Both transactions must exist in the main graph.
692 if (sim_a == SimTxGraph::MISSING || sim_b == SimTxGraph::MISSING) break;
693 auto cmp = real->CompareMainOrder(*ref_a, *ref_b);
694 // Distinct transactions have distinct places.
695 if (sim_a != sim_b) assert(cmp != 0);
696 // Ancestors go before descendants.
697 if (main_sim.graph.Ancestors(sim_a)[sim_b]) assert(cmp >= 0);
698 if (main_sim.graph.Descendants(sim_a)[sim_b]) assert(cmp <= 0);
699 // Do not verify consistency with chunk feerates, as we cannot easily determine
700 // these here without making more calls to real, which could affect its internal
701 // state. A full comparison is done at the end.
702 break;
703 } else if (!sel_sim.IsOversized() && command-- == 0) {
704 // CountDistinctClusters.
705 std::vector<TxGraph::Ref*> refs;
706 // Gather a list of up to 15 (or up to 255) Ref pointers.
707 auto count = provider.ConsumeIntegralInRange<size_t>(0, alt ? 255 : 15);
708 refs.resize(count);
709 for (size_t i = 0; i < count; ++i) {
710 refs[i] = pick_fn();
711 }
712 // Their order should not matter, shuffle them.
713 std::shuffle(refs.begin(), refs.end(), rng);
714 // Invoke the real function.
715 auto result = real->CountDistinctClusters(refs, use_main);
716 // Build a set with representatives of the clusters the Refs occur in in the
717 // simulated graph. For each, remember the lowest-index transaction SimPos in the
718 // cluster.
719 SimTxGraph::SetType sim_reps;
720 for (auto ref : refs) {
721 // Skip Refs that do not occur in the simulated graph.
722 auto simpos = sel_sim.Find(ref);
723 if (simpos == SimTxGraph::MISSING) continue;
724 // Find the component that includes ref.
725 auto component = sel_sim.graph.GetConnectedComponent(sel_sim.graph.Positions(), simpos);
726 // Remember the lowest-index SimPos in component, as a representative for it.
727 assert(component.Any());
728 sim_reps.Set(component.First());
729 }
730 // Compare the number of deduplicated representatives with the value returned by
731 // the real function.
732 assert(result == sim_reps.Count());
733 break;
734 } else if (command-- == 0) {
735 // DoWork.
736 uint64_t iters = provider.ConsumeIntegralInRange<uint64_t>(0, alt ? 10000 : 255);
737 bool ret = real->DoWork(iters);
738 uint64_t iters_for_optimal{0};
739 for (unsigned level = 0; level < sims.size(); ++level) {
740 // DoWork() will not optimize oversized levels, or the main level if a builder
741 // is present. Note that this impacts the DoWork() return value, as true means
742 // that non-optimal clusters may remain within such oversized or builder-having
743 // levels.
744 if (sims[level].IsOversized()) continue;
745 if (level == 0 && !block_builders.empty()) continue;
746 // If neither of the two above conditions holds, and DoWork() returned true,
747 // then the level is optimal.
748 if (ret) {
749 sims[level].real_is_optimal = true;
750 }
751 // Compute how many iterations would be needed to make everything optimal.
752 for (auto component : sims[level].GetComponents()) {
753 auto iters_opt_this_cluster = MaxOptimalLinearizationIters(component.Count());
754 if (iters_opt_this_cluster > acceptable_iters) {
755 // If the number of iterations required to linearize this cluster
756 // optimally exceeds acceptable_iters, DoWork() may process it in two
757 // stages: once to acceptable, and once to optimal.
758 iters_for_optimal += iters_opt_this_cluster + acceptable_iters;
759 } else {
760 iters_for_optimal += iters_opt_this_cluster;
761 }
762 }
763 }
764 if (!ret) {
765 // DoWork can only have more work left if the requested number of iterations
766 // was insufficient to linearize everything optimally within the levels it is
767 // allowed to touch.
768 assert(iters <= iters_for_optimal);
769 }
770 break;
771 } else if (sims.size() == 2 && !sims[0].IsOversized() && !sims[1].IsOversized() && command-- == 0) {
772 // GetMainStagingDiagrams()
773 auto [real_main_diagram, real_staged_diagram] = real->GetMainStagingDiagrams();
774 auto real_sum_main = std::accumulate(real_main_diagram.begin(), real_main_diagram.end(), FeeFrac{});
775 auto real_sum_staged = std::accumulate(real_staged_diagram.begin(), real_staged_diagram.end(), FeeFrac{});
776 auto real_gain = real_sum_staged - real_sum_main;
777 auto sim_gain = sims[1].SumAll() - sims[0].SumAll();
778 // Just check that the total fee gained/lost and size gained/lost according to the
779 // diagram matches the difference in these values in the simulated graph. A more
780 // complete check of the GetMainStagingDiagrams result is performed at the end.
781 assert(sim_gain == real_gain);
782 // Check that the feerates in each diagram are monotonically decreasing.
783 for (size_t i = 1; i < real_main_diagram.size(); ++i) {
784 assert(FeeRateCompare(real_main_diagram[i], real_main_diagram[i - 1]) <= 0);
785 }
786 for (size_t i = 1; i < real_staged_diagram.size(); ++i) {
787 assert(FeeRateCompare(real_staged_diagram[i], real_staged_diagram[i - 1]) <= 0);
788 }
789 break;
790 } else if (block_builders.size() < 4 && !main_sim.IsOversized() && command-- == 0) {
791 // GetBlockBuilder.
792 block_builders.emplace_back(real->GetBlockBuilder());
793 break;
794 } else if (!block_builders.empty() && command-- == 0) {
795 // ~BlockBuilder.
796 block_builders.erase(block_builders.begin() + builder_idx);
797 break;
798 } else if (!block_builders.empty() && command-- == 0) {
799 // BlockBuilder::GetCurrentChunk, followed by Include/Skip.
800 auto& builder_data = block_builders[builder_idx];
801 auto new_included = builder_data.included;
802 auto new_done = builder_data.done;
803 auto chunk = builder_data.builder->GetCurrentChunk();
804 if (chunk) {
805 // Chunk feerates must be monotonously decreasing.
806 if (!builder_data.last_feerate.IsEmpty()) {
807 assert(!(chunk->second >> builder_data.last_feerate));
808 }
809 builder_data.last_feerate = chunk->second;
810 // Verify the contents of GetCurrentChunk.
811 FeePerWeight sum_feerate;
812 for (TxGraph::Ref* ref : chunk->first) {
813 // Each transaction in the chunk must exist in the main graph.
814 auto simpos = main_sim.Find(ref);
815 assert(simpos != SimTxGraph::MISSING);
816 // Verify the claimed chunk feerate.
817 sum_feerate += main_sim.graph.FeeRate(simpos);
818 // Make sure no transaction is reported twice.
819 assert(!new_done[simpos]);
820 new_done.Set(simpos);
821 // The concatenation of all included transactions must be topologically valid.
822 new_included.Set(simpos);
823 assert(main_sim.graph.Ancestors(simpos).IsSubsetOf(new_included));
824 }
825 assert(sum_feerate == chunk->second);
826 } else {
827 // When we reach the end, if nothing was skipped, the entire graph should have
828 // been reported.
829 if (builder_data.done == builder_data.included) {
830 assert(builder_data.done.Count() == main_sim.GetTransactionCount());
831 }
832 }
833 // Possibly invoke GetCurrentChunk() again, which should give the same result.
834 if ((orig_command % 7) >= 5) {
835 auto chunk2 = builder_data.builder->GetCurrentChunk();
836 assert(chunk == chunk2);
837 }
838 // Skip or include.
839 if ((orig_command % 5) >= 3) {
840 // Skip.
841 builder_data.builder->Skip();
842 } else {
843 // Include.
844 builder_data.builder->Include();
845 builder_data.included = new_included;
846 }
847 builder_data.done = new_done;
848 break;
849 } else if (!main_sim.IsOversized() && command-- == 0) {
850 // GetWorstMainChunk.
851 auto [worst_chunk, worst_chunk_feerate] = real->GetWorstMainChunk();
852 // Just do some sanity checks here. Consistency with GetBlockBuilder is checked
853 // below.
854 if (main_sim.GetTransactionCount() == 0) {
855 assert(worst_chunk.empty());
856 assert(worst_chunk_feerate.IsEmpty());
857 } else {
858 assert(!worst_chunk.empty());
859 SimTxGraph::SetType done;
861 for (TxGraph::Ref* ref : worst_chunk) {
862 // Each transaction in the chunk must exist in the main graph.
863 auto simpos = main_sim.Find(ref);
864 assert(simpos != SimTxGraph::MISSING);
865 sum += main_sim.graph.FeeRate(simpos);
866 // Make sure the chunk contains no duplicate transactions.
867 assert(!done[simpos]);
868 done.Set(simpos);
869 // All elements are preceded by all their descendants.
870 assert(main_sim.graph.Descendants(simpos).IsSubsetOf(done));
871 }
872 assert(sum == worst_chunk_feerate);
873 }
874 break;
875 } else if ((block_builders.empty() || sims.size() > 1) && command-- == 0) {
876 // Trim.
877 bool was_oversized = top_sim.IsOversized();
878 auto removed = real->Trim();
879 // Verify that something was removed if and only if there was an oversized cluster.
880 assert(was_oversized == !removed.empty());
881 if (!was_oversized) break;
882 auto removed_set = top_sim.MakeSet(removed);
883 // The removed set must contain all its own descendants.
884 for (auto simpos : removed_set) {
885 assert(top_sim.graph.Descendants(simpos).IsSubsetOf(removed_set));
886 }
887 // Something from every oversized cluster should have been removed, and nothing
888 // else.
889 assert(top_sim.MatchesOversizedClusters(removed_set));
890
891 // Apply all removals to the simulation, and verify the result is no longer
892 // oversized. Don't query the real graph for oversizedness; it is compared
893 // against the simulation anyway later.
894 for (auto simpos : removed_set) {
895 top_sim.RemoveTransaction(top_sim.GetRef(simpos));
896 }
897 assert(!top_sim.IsOversized());
898 break;
899 } else if ((block_builders.empty() || sims.size() > 1) &&
900 top_sim.GetTransactionCount() > max_cluster_count && !top_sim.IsOversized() && command-- == 0) {
901 // Trim (special case which avoids apparent cycles in the implicit approximate
902 // dependency graph constructed inside the Trim() implementation). This is worth
903 // testing separately, because such cycles cannot occur in realistic scenarios,
904 // but this is hard to replicate in general in this fuzz test.
905
906 // First, we need to have dependencies applied and linearizations fixed to avoid
907 // circular dependencies in implied graph; trigger it via whatever means.
908 real->CountDistinctClusters({}, false);
909
910 // Gather the current clusters.
911 auto clusters = top_sim.GetComponents();
912
913 // Merge clusters randomly until at least one oversized one appears.
914 bool made_oversized = false;
915 auto merges_left = clusters.size() - 1;
916 while (merges_left > 0) {
917 --merges_left;
918 // Find positions of clusters in the clusters vector to merge together.
919 auto par_cl = rng.randrange(clusters.size());
920 auto chl_cl = rng.randrange(clusters.size() - 1);
921 chl_cl += (chl_cl >= par_cl);
922 Assume(chl_cl != par_cl);
923 // Add between 1 and 3 dependencies between them. As all are in the same
924 // direction (from the child cluster to parent cluster), no cycles are possible,
925 // regardless of what internal topology Trim() uses as approximation within the
926 // clusters.
927 int num_deps = rng.randrange(3) + 1;
928 for (int i = 0; i < num_deps; ++i) {
929 // Find a parent transaction in the parent cluster.
930 auto par_idx = rng.randrange(clusters[par_cl].Count());
931 SimTxGraph::Pos par_pos = 0;
932 for (auto j : clusters[par_cl]) {
933 if (par_idx == 0) {
934 par_pos = j;
935 break;
936 }
937 --par_idx;
938 }
939 // Find a child transaction in the child cluster.
940 auto chl_idx = rng.randrange(clusters[chl_cl].Count());
941 SimTxGraph::Pos chl_pos = 0;
942 for (auto j : clusters[chl_cl]) {
943 if (chl_idx == 0) {
944 chl_pos = j;
945 break;
946 }
947 --chl_idx;
948 }
949 // Add dependency to both simulation and real TxGraph.
950 auto par_ref = top_sim.GetRef(par_pos);
951 auto chl_ref = top_sim.GetRef(chl_pos);
952 top_sim.AddDependency(par_ref, chl_ref);
953 real->AddDependency(*par_ref, *chl_ref);
954 }
955 // Compute the combined cluster.
956 auto par_cluster = clusters[par_cl];
957 auto chl_cluster = clusters[chl_cl];
958 auto new_cluster = par_cluster | chl_cluster;
959 // Remove the parent and child cluster from clusters.
960 std::erase_if(clusters, [&](const auto& cl) noexcept { return cl == par_cluster || cl == chl_cluster; });
961 // Add the combined cluster.
962 clusters.push_back(new_cluster);
963 // If this is the first merge that causes an oversized cluster to appear, pick
964 // a random number of further merges to appear.
965 if (!made_oversized) {
966 made_oversized = new_cluster.Count() > max_cluster_count;
967 if (!made_oversized) {
968 FeeFrac total;
969 for (auto i : new_cluster) total += top_sim.graph.FeeRate(i);
970 if (uint32_t(total.size) > max_cluster_size) made_oversized = true;
971 }
972 if (made_oversized) merges_left = rng.randrange(clusters.size());
973 }
974 }
975
976 // Determine an upper bound on how many transactions are removed.
977 uint32_t max_removed = 0;
978 for (auto& cluster : clusters) {
979 // Gather all transaction sizes in the to-be-combined cluster.
980 std::vector<uint32_t> sizes;
981 for (auto i : cluster) sizes.push_back(top_sim.graph.FeeRate(i).size);
982 auto sum_sizes = std::accumulate(sizes.begin(), sizes.end(), uint64_t{0});
983 // Sort from large to small.
984 std::sort(sizes.begin(), sizes.end(), std::greater{});
985 // In the worst case, only the smallest transactions are removed.
986 while (sizes.size() > max_cluster_count || sum_sizes > max_cluster_size) {
987 sum_sizes -= sizes.back();
988 sizes.pop_back();
989 ++max_removed;
990 }
991 }
992
993 // Invoke Trim now on the definitely-oversized txgraph.
994 auto removed = real->Trim();
995 // Verify that the number of removals is within range.
996 assert(removed.size() >= 1);
997 assert(removed.size() <= max_removed);
998 // The removed set must contain all its own descendants.
999 auto removed_set = top_sim.MakeSet(removed);
1000 for (auto simpos : removed_set) {
1001 assert(top_sim.graph.Descendants(simpos).IsSubsetOf(removed_set));
1002 }
1003 // Something from every oversized cluster should have been removed, and nothing
1004 // else.
1005 assert(top_sim.MatchesOversizedClusters(removed_set));
1006
1007 // Apply all removals to the simulation, and verify the result is no longer
1008 // oversized. Don't query the real graph for oversizedness; it is compared
1009 // against the simulation anyway later.
1010 for (auto simpos : removed_set) {
1011 top_sim.RemoveTransaction(top_sim.GetRef(simpos));
1012 }
1013 assert(!top_sim.IsOversized());
1014 break;
1015 }
1016 }
1017 }
1018
1019 // After running all modifications, perform an internal sanity check (before invoking
1020 // inspectors that may modify the internal state).
1021 real->SanityCheck();
1022
1023 if (!sims[0].IsOversized()) {
1024 // If the main graph is not oversized, verify the total ordering implied by
1025 // CompareMainOrder.
1026 // First construct two distinct randomized permutations of the positions in sims[0].
1027 std::vector<SimTxGraph::Pos> vec1;
1028 for (auto i : sims[0].graph.Positions()) vec1.push_back(i);
1029 std::shuffle(vec1.begin(), vec1.end(), rng);
1030 auto vec2 = vec1;
1031 std::shuffle(vec2.begin(), vec2.end(), rng);
1032 if (vec1 == vec2) std::next_permutation(vec2.begin(), vec2.end());
1033 // Sort both according to CompareMainOrder. By having randomized starting points, the order
1034 // of CompareMainOrder invocations is somewhat randomized as well.
1035 auto cmp = [&](SimTxGraph::Pos a, SimTxGraph::Pos b) noexcept {
1036 return real->CompareMainOrder(*sims[0].GetRef(a), *sims[0].GetRef(b)) < 0;
1037 };
1038 std::sort(vec1.begin(), vec1.end(), cmp);
1039 std::sort(vec2.begin(), vec2.end(), cmp);
1040
1041 // Verify the resulting orderings are identical. This could only fail if the ordering was
1042 // not total.
1043 assert(vec1 == vec2);
1044
1045 // Verify that the ordering is topological.
1046 auto todo = sims[0].graph.Positions();
1047 for (auto i : vec1) {
1048 todo.Reset(i);
1049 assert(!sims[0].graph.Ancestors(i).Overlaps(todo));
1050 }
1051 assert(todo.None());
1052
1053 // If the real graph claims to be optimal (the last DoWork() call returned true), verify
1054 // that calling Linearize on it does not improve it further.
1055 if (sims[0].real_is_optimal) {
1056 auto real_diagram = ChunkLinearization(sims[0].graph, vec1);
1057 auto [sim_lin, _optimal, _cost] = Linearize(sims[0].graph, 300000, rng.rand64(), vec1);
1058 auto sim_diagram = ChunkLinearization(sims[0].graph, sim_lin);
1059 auto cmp = CompareChunks(real_diagram, sim_diagram);
1060 assert(cmp == 0);
1061 }
1062
1063 // For every transaction in the total ordering, find a random one before it and after it,
1064 // and compare their chunk feerates, which must be consistent with the ordering.
1065 for (size_t pos = 0; pos < vec1.size(); ++pos) {
1066 auto pos_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[pos]));
1067 if (pos > 0) {
1068 size_t before = rng.randrange<size_t>(pos);
1069 auto before_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[before]));
1070 assert(FeeRateCompare(before_feerate, pos_feerate) >= 0);
1071 }
1072 if (pos + 1 < vec1.size()) {
1073 size_t after = pos + 1 + rng.randrange<size_t>(vec1.size() - 1 - pos);
1074 auto after_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[after]));
1075 assert(FeeRateCompare(after_feerate, pos_feerate) <= 0);
1076 }
1077 }
1078
1079 // The same order should be obtained through a BlockBuilder as implied by CompareMainOrder,
1080 // if nothing is skipped.
1081 auto builder = real->GetBlockBuilder();
1082 std::vector<SimTxGraph::Pos> vec_builder;
1083 std::vector<TxGraph::Ref*> last_chunk;
1084 FeePerWeight last_chunk_feerate;
1085 while (auto chunk = builder->GetCurrentChunk()) {
1087 for (TxGraph::Ref* ref : chunk->first) {
1088 // The reported chunk feerate must match the chunk feerate obtained by asking
1089 // it for each of the chunk's transactions individually.
1090 assert(real->GetMainChunkFeerate(*ref) == chunk->second);
1091 // Verify the chunk feerate matches the sum of the reported individual feerates.
1092 sum += real->GetIndividualFeerate(*ref);
1093 // Chunks must contain transactions that exist in the graph.
1094 auto simpos = sims[0].Find(ref);
1095 assert(simpos != SimTxGraph::MISSING);
1096 vec_builder.push_back(simpos);
1097 }
1098 assert(sum == chunk->second);
1099 last_chunk = std::move(chunk->first);
1100 last_chunk_feerate = chunk->second;
1101 builder->Include();
1102 }
1103 assert(vec_builder == vec1);
1104
1105 // The last chunk returned by the BlockBuilder must match GetWorstMainChunk, in reverse.
1106 std::reverse(last_chunk.begin(), last_chunk.end());
1107 auto [worst_chunk, worst_chunk_feerate] = real->GetWorstMainChunk();
1108 assert(last_chunk == worst_chunk);
1109 assert(last_chunk_feerate == worst_chunk_feerate);
1110
1111 // Check that the implied ordering gives rise to a combined diagram that matches the
1112 // diagram constructed from the individual cluster linearization chunkings.
1113 auto main_real_diagram = get_diagram_fn(/*main_only=*/true);
1114 auto main_implied_diagram = ChunkLinearization(sims[0].graph, vec1);
1115 assert(CompareChunks(main_real_diagram, main_implied_diagram) == 0);
1116
1117 if (sims.size() >= 2 && !sims[1].IsOversized()) {
1118 // When the staging graph is not oversized as well, call GetMainStagingDiagrams, and
1119 // fully verify the result.
1120 auto [main_cmp_diagram, stage_cmp_diagram] = real->GetMainStagingDiagrams();
1121 // Check that the feerates in each diagram are monotonically decreasing.
1122 for (size_t i = 1; i < main_cmp_diagram.size(); ++i) {
1123 assert(FeeRateCompare(main_cmp_diagram[i], main_cmp_diagram[i - 1]) <= 0);
1124 }
1125 for (size_t i = 1; i < stage_cmp_diagram.size(); ++i) {
1126 assert(FeeRateCompare(stage_cmp_diagram[i], stage_cmp_diagram[i - 1]) <= 0);
1127 }
1128 // Treat the diagrams as sets of chunk feerates, and sort them in the same way so that
1129 // std::set_difference can be used on them below. The exact ordering does not matter
1130 // here, but it has to be consistent with the one used in main_real_diagram and
1131 // stage_real_diagram).
1132 std::sort(main_cmp_diagram.begin(), main_cmp_diagram.end(), std::greater{});
1133 std::sort(stage_cmp_diagram.begin(), stage_cmp_diagram.end(), std::greater{});
1134 // Find the chunks that appear in main_diagram but are missing from main_cmp_diagram.
1135 // This is allowed, because GetMainStagingDiagrams omits clusters in main unaffected
1136 // by staging.
1137 std::vector<FeeFrac> missing_main_cmp;
1138 std::set_difference(main_real_diagram.begin(), main_real_diagram.end(),
1139 main_cmp_diagram.begin(), main_cmp_diagram.end(),
1140 std::inserter(missing_main_cmp, missing_main_cmp.end()),
1141 std::greater{});
1142 assert(main_cmp_diagram.size() + missing_main_cmp.size() == main_real_diagram.size());
1143 // Do the same for chunks in stage_diagram missing from stage_cmp_diagram.
1144 auto stage_real_diagram = get_diagram_fn(/*main_only=*/false);
1145 std::vector<FeeFrac> missing_stage_cmp;
1146 std::set_difference(stage_real_diagram.begin(), stage_real_diagram.end(),
1147 stage_cmp_diagram.begin(), stage_cmp_diagram.end(),
1148 std::inserter(missing_stage_cmp, missing_stage_cmp.end()),
1149 std::greater{});
1150 assert(stage_cmp_diagram.size() + missing_stage_cmp.size() == stage_real_diagram.size());
1151 // The missing chunks must be equal across main & staging (otherwise they couldn't have
1152 // been omitted).
1153 assert(missing_main_cmp == missing_stage_cmp);
1154
1155 // The missing part must include at least all transactions in staging which have not been
1156 // modified, or been in a cluster together with modified transactions, since they were
1157 // copied from main. Note that due to the reordering of removals w.r.t. dependency
1158 // additions, it is possible that the real implementation found more unaffected things.
1159 FeeFrac missing_real;
1160 for (const auto& feerate : missing_main_cmp) missing_real += feerate;
1161 FeeFrac missing_expected = sims[1].graph.FeeRate(sims[1].graph.Positions() - sims[1].modified);
1162 // Note that missing_real.fee < missing_expected.fee is possible to due the presence of
1163 // negative-fee transactions.
1164 assert(missing_real.size >= missing_expected.size);
1165 }
1166 }
1167
1168 assert(real->HaveStaging() == (sims.size() > 1));
1169
1170 // Try to run a full comparison, for both main_only=false and main_only=true in TxGraph
1171 // inspector functions that support both.
1172 for (int main_only = 0; main_only < 2; ++main_only) {
1173 auto& sim = main_only ? sims[0] : sims.back();
1174 // Compare simple properties of the graph with the simulation.
1175 assert(real->IsOversized(main_only) == sim.IsOversized());
1176 assert(real->GetTransactionCount(main_only) == sim.GetTransactionCount());
1177 // If the graph (and the simulation) are not oversized, perform a full comparison.
1178 if (!sim.IsOversized()) {
1179 auto todo = sim.graph.Positions();
1180 // Iterate over all connected components of the resulting (simulated) graph, each of which
1181 // should correspond to a cluster in the real one.
1182 while (todo.Any()) {
1183 auto component = sim.graph.FindConnectedComponent(todo);
1184 todo -= component;
1185 // Iterate over the transactions in that component.
1186 for (auto i : component) {
1187 // Check its individual feerate against simulation.
1188 assert(sim.graph.FeeRate(i) == real->GetIndividualFeerate(*sim.GetRef(i)));
1189 // Check its ancestors against simulation.
1190 auto expect_anc = sim.graph.Ancestors(i);
1191 auto anc = sim.MakeSet(real->GetAncestors(*sim.GetRef(i), main_only));
1192 assert(anc.Count() <= max_cluster_count);
1193 assert(anc == expect_anc);
1194 // Check its descendants against simulation.
1195 auto expect_desc = sim.graph.Descendants(i);
1196 auto desc = sim.MakeSet(real->GetDescendants(*sim.GetRef(i), main_only));
1197 assert(desc.Count() <= max_cluster_count);
1198 assert(desc == expect_desc);
1199 // Check the cluster the transaction is part of.
1200 auto cluster = real->GetCluster(*sim.GetRef(i), main_only);
1201 assert(cluster.size() <= max_cluster_count);
1202 assert(sim.MakeSet(cluster) == component);
1203 // Check that the cluster is reported in a valid topological order (its
1204 // linearization).
1205 std::vector<DepGraphIndex> simlin;
1206 SimTxGraph::SetType done;
1207 uint64_t total_size{0};
1208 for (TxGraph::Ref* ptr : cluster) {
1209 auto simpos = sim.Find(ptr);
1210 assert(sim.graph.Descendants(simpos).IsSubsetOf(component - done));
1211 done.Set(simpos);
1212 assert(sim.graph.Ancestors(simpos).IsSubsetOf(done));
1213 simlin.push_back(simpos);
1214 total_size += sim.graph.FeeRate(simpos).size;
1215 }
1216 // Check cluster size.
1217 assert(total_size <= max_cluster_size);
1218 // Construct a chunking object for the simulated graph, using the reported cluster
1219 // linearization as ordering, and compare it against the reported chunk feerates.
1220 if (sims.size() == 1 || main_only) {
1221 cluster_linearize::LinearizationChunking simlinchunk(sim.graph, simlin);
1222 DepGraphIndex idx{0};
1223 for (unsigned chunknum = 0; chunknum < simlinchunk.NumChunksLeft(); ++chunknum) {
1224 auto chunk = simlinchunk.GetChunk(chunknum);
1225 // Require that the chunks of cluster linearizations are connected (this must
1226 // be the case as all linearizations inside are PostLinearized).
1227 assert(sim.graph.IsConnected(chunk.transactions));
1228 // Check the chunk feerates of all transactions in the cluster.
1229 while (chunk.transactions.Any()) {
1230 assert(chunk.transactions[simlin[idx]]);
1231 chunk.transactions.Reset(simlin[idx]);
1232 assert(chunk.feerate == real->GetMainChunkFeerate(*cluster[idx]));
1233 ++idx;
1234 }
1235 }
1236 }
1237 }
1238 }
1239 }
1240 }
1241
1242 // Sanity check again (because invoking inspectors may modify internal unobservable state).
1243 real->SanityCheck();
1244
1245 // Kill the block builders.
1246 block_builders.clear();
1247 // Kill the TxGraph object.
1248 real.reset();
1249 // Kill the simulated graphs, with all remaining Refs in it. If any, this verifies that Refs
1250 // can outlive the TxGraph that created them.
1251 sims.clear();
1252}
int ret
const auto command
std::conditional_t<(BITS<=32), bitset_detail::IntBitSet< uint32_t >, std::conditional_t<(BITS<=std::numeric_limits< size_t >::digits), bitset_detail::IntBitSet< size_t >, bitset_detail::MultiIntBitSet< size_t,(BITS+std::numeric_limits< size_t >::digits - 1)/std::numeric_limits< size_t >::digits > > > BitSet
Definition: bitset.h:525
#define Assume(val)
Assume is the identity function.
Definition: check.h:118
T ConsumeIntegralInRange(T min, T max)
xoroshiro128++ PRNG.
Definition: random.h:425
constexpr uint64_t rand64() noexcept
Definition: random.h:448
I randrange(I range) noexcept
Generate a random integer in the range [0..range), with range > 0.
Definition: random.h:254
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.
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).
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.
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.
constexpr MaybeCoin MISSING
volatile double sum
Definition: examples.cpp:10
#define LIMITED_WHILE(condition, limit)
Can be used to limit a theoretically unbounded loop.
Definition: fuzz.h:22
uint64_t fee
Value Find(const std::map< Key, Value > &map, const Key &key)
std::vector< FeeFrac > ChunkLinearization(const DepGraph< SetType > &depgraph, std::span< const DepGraphIndex > linearization) noexcept
Compute the feerates of the chunks of linearization.
std::tuple< std::vector< DepGraphIndex >, bool, uint64_t > 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.
uint32_t DepGraphIndex
Data type to represent transaction indices in DepGraphs and the clusters they represent.
Data structure storing a fee and size, ordered by increasing fee/size.
Definition: feefrac.h:40
int64_t fee
Definition: feefrac.h:107
int32_t size
Definition: feefrac.h:108
bool IsEmpty() const noexcept
Check if this is empty (size and fee are 0).
Definition: feefrac.h:120
Tagged wrapper around FeeFrac to avoid unit confusion.
Definition: feefrac.h:239
FUZZ_TARGET(txgraph)
Definition: txgraph.cpp:297
void SeedRandomStateForTest(SeedRand seedtype)
Seed the global RNG state for testing and log the seed value.
Definition: random.cpp:19
@ ZEROS
Seed with a compile time constant of zeros.
static int count
std::unique_ptr< TxGraph > MakeTxGraph(unsigned max_cluster_count, uint64_t max_cluster_size, uint64_t acceptable_iters) noexcept
Construct a new TxGraph with the specified limit on the number of transactions within a cluster,...
Definition: txgraph.cpp:2943
static constexpr unsigned MAX_CLUSTER_COUNT_LIMIT
Definition: txgraph.h:17
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())