I'm wondering what the best way of catching stuff that should be missing on both sides being added to both diagrams erroneously.
You could imagine a degenerate case where a bug turns this into a whole mempool check. (and implies we're doing a bunch of work maintaining these clusters for no reason)
A rough suggestion to think about, perhaps you can tighten the bounds?
diff --git a/src/test/fuzz/txgraph.cpp b/src/test/fuzz/txgraph.cpp
index 7249827103..f30b650313 100644
--- a/src/test/fuzz/txgraph.cpp
+++ b/src/test/fuzz/txgraph.cpp
@@ -338,10 +338,17 @@ FUZZ_TARGET(txgraph)
// just feerates).
std::sort(ret.begin(), ret.end(), std::greater{});
return ret;
};
+ // When entering staging reset to 0
+ // This is used to upper-bound the possible diagram size in number of entries
+ // to catch any regression where erroneous entries are on both sides of the
+ // computed diagram when they shouldn't have been added at all.
+ uint32_t num_possible_conflicted_entries_main{0};
+ uint32_t num_possible_pulled_in_entries_staged{0};
+
LIMITED_WHILE(provider.remaining_bytes() > 0, 200) {
// Read a one-byte command.
int command = provider.ConsumeIntegral<uint8_t>();
/** Use the bottom 2 bits of command to select an entry in the block_builders vector (if
@@ -377,10 +384,11 @@ FUZZ_TARGET(txgraph)
// Otherwise, use smaller range which consume fewer fuzz input bytes, as just
// these are likely sufficient to trigger all interesting code paths already.
fee = provider.ConsumeIntegral<uint8_t>();
size = provider.ConsumeIntegral<uint8_t>() + 1;
}
+ num_possible_pulled_in_entries_staged++;
FeePerWeight feerate{fee, size};
// Create a real TxGraph::Ref.
auto ref = real->AddTransaction(feerate);
// Create a shared_ptr place in the simulation to put the Ref in.
auto ref_loc = top_sim.AddTransaction(feerate);
@@ -398,10 +406,22 @@ FUZZ_TARGET(txgraph)
// and if so, skip.
if (top_sim.graph.Ancestors(pos_par)[pos_chl]) break;
}
top_sim.AddDependency(par, chl);
real->AddDependency(*par, *chl);
+ if (pos_par != SimTxGraph::MISSING && pos_chl != SimTxGraph::MISSING) {
+ if (!top_sim.IsOversized() && !main_sim.IsOversized()) {
+ // If both are real, add resulting cluster count to num_possible_pulled_in_entries_*
+ const auto max_count{std::max(real->GetCluster(*par, false).size(), real->GetCluster(*par, true).size())};
+ num_possible_conflicted_entries_main += max_count;
+ num_possible_pulled_in_entries_staged += max_count;
+ } else {
+ // If ever oversized, add max count to "turn it off"
+ num_possible_conflicted_entries_main += SimTxGraph::MAX_TRANSACTIONS;
+ num_possible_pulled_in_entries_staged += SimTxGraph::MAX_TRANSACTIONS;
+ }
+ }
break;
} else if ((block_builders.empty() || sims.size() > 1) && top_sim.removed.size() < 100 && command-- == 0) {
// RemoveTransaction. Either all its ancestors or all its descendants are also
// removed (if any), to make sure TxGraph's reordering of removals and dependencies
// has no effect.
@@ -410,10 +430,20 @@ FUZZ_TARGET(txgraph)
top_sim.IncludeAncDesc(to_remove, alt);
// The order in which these ancestors/descendants are removed should not matter;
// randomly shuffle them.
std::shuffle(to_remove.begin(), to_remove.end(), rng);
for (TxGraph::Ref* ptr : to_remove) {
+ if (!top_sim.IsOversized() && !main_sim.IsOversized()) {
+ const auto max_count{std::max(real->GetCluster(*ptr, false).size(), real->GetCluster(*ptr, true).size())};
+ // Overestimate number of pulled in items
+ num_possible_conflicted_entries_main += max_count;
+ num_possible_pulled_in_entries_staged += max_count;
+ } else {
+ // If ever oversized, add max count to "turn it off"
+ num_possible_conflicted_entries_main += SimTxGraph::MAX_TRANSACTIONS;
+ num_possible_pulled_in_entries_staged += SimTxGraph::MAX_TRANSACTIONS;
+ }
real->RemoveTransaction(*ptr);
top_sim.RemoveTransaction(ptr);
}
break;
} else if (sel_sim.removed.size() > 0 && command-- == 0) {
@@ -446,10 +476,20 @@ FUZZ_TARGET(txgraph)
}
// The order in which these ancestors/descendants are destroyed should not matter;
// randomly shuffle them.
std::shuffle(to_destroy.begin(), to_destroy.end(), rng);
for (TxGraph::Ref* ptr : to_destroy) {
+ if (!top_sim.IsOversized() && !main_sim.IsOversized()) {
+ const auto max_count{std::max(real->GetCluster(*ptr, false).size(), real->GetCluster(*ptr, true).size())};
+ // Overestimate number of pulled in items
+ num_possible_conflicted_entries_main += max_count;
+ num_possible_pulled_in_entries_staged += max_count;
+ } else {
+ // If ever oversized, add max count to "turn it off"
+ num_possible_conflicted_entries_main += SimTxGraph::MAX_TRANSACTIONS;
+ num_possible_pulled_in_entries_staged += SimTxGraph::MAX_TRANSACTIONS;
+ }
for (size_t level = 0; level < sims.size(); ++level) {
sims[level].DestroyTransaction(ptr, level == sims.size() - 1);
}
}
break;
@@ -580,10 +620,14 @@ FUZZ_TARGET(txgraph)
break;
} else if (sims.size() < 2 && command-- == 0) {
// StartStaging.
sims.emplace_back(sims.back());
real->StartStaging();
+
+ // Start counting upper-bound on open of staging
+ num_possible_conflicted_entries_main = 0;
+ num_possible_pulled_in_entries_staged = 0;
break;
} else if (block_builders.empty() && sims.size() > 1 && command-- == 0) {
// CommitStaging.
real->CommitStaging();
sims.erase(sims.begin());
@@ -668,10 +712,17 @@ FUZZ_TARGET(txgraph)
auto [main_diagram, staged_diagram] = real->GetMainStagingDiagrams();
auto sum_main = std::accumulate(main_diagram.begin(), main_diagram.end(), FeeFrac{});
auto sum_staged = std::accumulate(staged_diagram.begin(), staged_diagram.end(), FeeFrac{});
auto diagram_gain = sum_staged - sum_main;
auto real_gain = sims[1].SumAll() - sims[0].SumAll();
+
+ // Sanity check sizes of diagrams
+ assert(main_diagram.size() <= num_possible_conflicted_entries_main);
+ assert(main_diagram.size() <= SimTxGraph::MAX_TRANSACTIONS);
+ assert(staged_diagram.size() <= num_possible_pulled_in_entries_staged);
+ assert(staged_diagram.size() <= SimTxGraph::MAX_TRANSACTIONS);
+
// Just check that the total fee gained/lost and size gained/lost according to the
// diagram matches the difference in these values in the simulated graph. A more
// complete check of the GetMainStagingDiagrams result is performed at the end.
assert(diagram_gain == real_gain);
// Check that the feerates in each diagram are monotonically decreasing.
