Branch data Line data Source code
1 : : // Copyright (c) The Bitcoin Core developers
2 : : // Distributed under the MIT software license, see the accompanying
3 : : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 : :
5 : : #include <txgraph.h>
6 : :
7 : : #include <cluster_linearize.h>
8 : : #include <test/fuzz/FuzzedDataProvider.h>
9 : : #include <test/fuzz/fuzz.h>
10 : : #include <test/util/cluster_linearize.h>
11 : : #include <test/util/random.h>
12 : : #include <util/bitset.h>
13 : : #include <util/check.h>
14 : : #include <util/feefrac.h>
15 : :
16 : : #include <algorithm>
17 : : #include <cstdint>
18 : : #include <iterator>
19 : : #include <map>
20 : : #include <memory>
21 : : #include <ranges>
22 : : #include <set>
23 : : #include <utility>
24 : :
25 : : using namespace cluster_linearize;
26 : :
27 : : namespace {
28 : :
29 : 31297 : struct SimTxObject : public TxGraph::Ref
30 : : {
31 : : // Use random uint64_t as txids for this simulation (0 = empty object).
32 : : const uint64_t m_txid{0};
33 : : SimTxObject() noexcept = default;
34 : 261497 : explicit SimTxObject(uint64_t txid) noexcept : m_txid(txid) {}
35 : : };
36 : :
37 : : /** Data type representing a naive simulated TxGraph, keeping all transactions (even from
38 : : * disconnected components) in a single DepGraph. Unlike the real TxGraph, this only models
39 : : * a single graph, and multiple instances are used to simulate main/staging. */
40 : : struct SimTxGraph
41 : : {
42 : : /** Maximum number of transactions to support simultaneously. Set this higher than txgraph's
43 : : * cluster count, so we can exercise situations with more transactions than fit in one
44 : : * cluster. */
45 : : static constexpr unsigned MAX_TRANSACTIONS = MAX_CLUSTER_COUNT_LIMIT * 2;
46 : : /** Set type to use in the simulation. */
47 : : using SetType = BitSet<MAX_TRANSACTIONS>;
48 : : /** Data type for representing positions within SimTxGraph::graph. */
49 : : using Pos = DepGraphIndex;
50 : : /** Constant to mean "missing in this graph". */
51 : : static constexpr auto MISSING = Pos(-1);
52 : :
53 : : /** The dependency graph (for all transactions in the simulation, regardless of
54 : : * connectivity/clustering). */
55 : : DepGraph<SetType> graph;
56 : : /** For each position in graph, which SimTxObject it corresponds with (if any). Use shared_ptr
57 : : * so that a SimTxGraph can be copied to create a staging one, while sharing Refs with
58 : : * the main graph. */
59 : : std::array<std::shared_ptr<SimTxObject>, MAX_TRANSACTIONS> simmap;
60 : : /** For each TxGraph::Ref in graph, the position it corresponds with. */
61 : : std::map<const TxGraph::Ref*, Pos> simrevmap;
62 : : /** The set of SimTxObject entries that have been removed, but not yet destroyed. */
63 : : std::vector<std::shared_ptr<SimTxObject>> removed;
64 : : /** Whether the graph is oversized (true = yes, false = no, std::nullopt = unknown). */
65 : : std::optional<bool> oversized;
66 : : /** The configured maximum number of transactions per cluster. */
67 : : DepGraphIndex max_cluster_count;
68 : : /** Which transactions have been modified in the graph since creation, either directly or by
69 : : * being in a cluster which includes modifications. Only relevant for the staging graph. */
70 : : SetType modified;
71 : : /** The configured maximum total size of transactions per cluster. */
72 : : uint64_t max_cluster_size;
73 : : /** Whether the corresponding real graph is known to be optimally linearized. */
74 : : bool real_is_optimal{false};
75 : :
76 : : /** Construct a new SimTxGraph with the specified maximum cluster count and size. */
77 : 3590 : explicit SimTxGraph(DepGraphIndex cluster_count, uint64_t cluster_size) :
78 : 3590 : max_cluster_count(cluster_count), max_cluster_size(cluster_size) {}
79 : :
80 : : // Permit copying and moving.
81 [ + - + - ]: 17180 : SimTxGraph(const SimTxGraph&) noexcept = default;
82 : : SimTxGraph& operator=(const SimTxGraph&) noexcept = default;
83 : 0 : SimTxGraph(SimTxGraph&&) noexcept = default;
84 : 3870 : SimTxGraph& operator=(SimTxGraph&&) noexcept = default;
85 : :
86 : : /** Get the connected components within this simulated transaction graph. */
87 : 137222 : std::vector<SetType> GetComponents()
88 : : {
89 : 137222 : auto todo = graph.Positions();
90 : 137222 : std::vector<SetType> ret;
91 : : // Iterate over all connected components of the graph.
92 [ + + ]: 7080096 : while (todo.Any()) {
93 : 3402826 : auto component = graph.FindConnectedComponent(todo);
94 [ + - ]: 3402826 : ret.push_back(component);
95 : 3402826 : todo -= component;
96 : : }
97 : 137222 : return ret;
98 : 0 : }
99 : :
100 : : /** Check whether this graph is oversized (contains a connected component whose number of
101 : : * transactions exceeds max_cluster_count. */
102 : 3147636 : bool IsOversized()
103 : : {
104 [ + + ]: 3147636 : if (!oversized.has_value()) {
105 : : // Only recompute when oversized isn't already known.
106 : 104660 : oversized = false;
107 [ + + ]: 2527384 : for (auto component : GetComponents()) {
108 [ + + ]: 2422724 : if (component.Count() > max_cluster_count) oversized = true;
109 : 2422724 : uint64_t component_size{0};
110 [ + + ]: 7005091 : for (auto i : component) component_size += graph.FeeRate(i).size;
111 [ + + ]: 2422724 : if (component_size > max_cluster_size) oversized = true;
112 : 104660 : }
113 : : }
114 : 3147636 : return *oversized;
115 : : }
116 : :
117 : 1654346 : void MakeModified(DepGraphIndex index)
118 : : {
119 : 1654346 : modified |= graph.GetConnectedComponent(graph.Positions(), index);
120 : 1654346 : }
121 : :
122 : : /** Determine the number of (non-removed) transactions in the graph. */
123 [ + + - + : 1952839 : DepGraphIndex GetTransactionCount() const { return graph.TxCount(); }
+ + - + -
+ ]
124 : :
125 : : /** Get the sum of all fees/sizes in the graph. */
126 : 46060 : FeePerWeight SumAll() const
127 : : {
128 : 46060 : FeePerWeight ret;
129 [ + + ]: 1815183 : for (auto i : graph.Positions()) {
130 : 1769123 : ret += graph.FeeRate(i);
131 : : }
132 : 46060 : return ret;
133 : : }
134 : :
135 : : /** Get the position where ref occurs in this simulated graph, or -1 if it does not. */
136 : 12072755 : Pos Find(const TxGraph::Ref* ref) const
137 : : {
138 : 12072755 : auto it = simrevmap.find(ref);
139 [ + + ]: 12072755 : if (it != simrevmap.end()) return it->second;
140 : : return MISSING;
141 : : }
142 : :
143 : : /** Given a position in this simulated graph, get the corresponding SimTxObject. */
144 : 8024573 : SimTxObject* GetRef(Pos pos)
145 : : {
146 [ - + ]: 8024573 : assert(graph.Positions()[pos]);
147 [ - + ]: 8024573 : assert(simmap[pos]);
148 : 8024573 : return simmap[pos].get();
149 : : }
150 : :
151 : : /** Add a new transaction to the simulation and the specified real graph. */
152 : 230200 : void AddTransaction(TxGraph& txgraph, const FeePerWeight& feerate, uint64_t txid)
153 : : {
154 [ - + ]: 230200 : assert(graph.TxCount() < MAX_TRANSACTIONS);
155 : 230200 : auto simpos = graph.AddTransaction(feerate);
156 : 230200 : real_is_optimal = false;
157 : 230200 : MakeModified(simpos);
158 [ - + ]: 230200 : assert(graph.Positions()[simpos]);
159 [ - + ]: 230200 : simmap[simpos] = std::make_shared<SimTxObject>(txid);
160 : 230200 : txgraph.AddTransaction(*simmap[simpos], feerate);
161 : 230200 : auto ptr = simmap[simpos].get();
162 : 230200 : simrevmap[ptr] = simpos;
163 : : // This may invalidate our cached oversized value.
164 [ + + + + ]: 230200 : if (oversized.has_value() && !*oversized) oversized = std::nullopt;
165 : 230200 : }
166 : :
167 : : /** Add a dependency between two positions in this graph. */
168 : 1204321 : void AddDependency(TxGraph::Ref* parent, TxGraph::Ref* child)
169 : : {
170 : 1204321 : auto par_pos = Find(parent);
171 [ + + ]: 1204321 : if (par_pos == MISSING) return;
172 : 1201399 : auto chl_pos = Find(child);
173 [ + + ]: 1201399 : if (chl_pos == MISSING) return;
174 : 1199058 : graph.AddDependencies(SetType::Singleton(par_pos), chl_pos);
175 : 1199058 : MakeModified(par_pos);
176 : 1199058 : real_is_optimal = false;
177 : : // This may invalidate our cached oversized value.
178 [ + + + + ]: 1199058 : if (oversized.has_value() && !*oversized) oversized = std::nullopt;
179 : : }
180 : :
181 : : /** Modify the transaction fee of a ref, if it exists. */
182 : 8291 : void SetTransactionFee(TxGraph::Ref* ref, int64_t fee)
183 : : {
184 : 8291 : auto pos = Find(ref);
185 [ + + ]: 8291 : if (pos == MISSING) return;
186 : : // No need to invoke MakeModified, because this equally affects main and staging.
187 : 5582 : real_is_optimal = false;
188 : 5582 : graph.FeeRate(pos).fee = fee;
189 : : }
190 : :
191 : : /** Remove the transaction in the specified position from the graph. */
192 : 204956 : void RemoveTransaction(TxGraph::Ref* ref)
193 : : {
194 : 204956 : auto pos = Find(ref);
195 [ + + ]: 204956 : if (pos == MISSING) return;
196 : 198259 : MakeModified(pos);
197 : 198259 : real_is_optimal = false;
198 : 198259 : graph.RemoveTransactions(SetType::Singleton(pos));
199 : 198259 : simrevmap.erase(simmap[pos].get());
200 : : // Retain the TxGraph::Ref corresponding to this position, so the Ref destruction isn't
201 : : // invoked until the simulation explicitly decided to do so.
202 : 198259 : removed.push_back(std::move(simmap[pos]));
203 : 198259 : simmap[pos].reset();
204 : : // This may invalidate our cached oversized value.
205 [ + + + + ]: 198259 : if (oversized.has_value() && *oversized) oversized = std::nullopt;
206 : : }
207 : :
208 : : /** Destroy the transaction from the graph, including from the removed set. This will
209 : : * trigger TxGraph::Ref::~Ref. reset_oversize controls whether the cached oversized
210 : : * value is cleared (destroying does not clear oversizedness in TxGraph of the main
211 : : * graph while staging exists). */
212 : 35519 : void DestroyTransaction(TxGraph::Ref* ref, bool reset_oversize)
213 : : {
214 : 35519 : auto pos = Find(ref);
215 [ + + ]: 35519 : if (pos == MISSING) {
216 : : // Wipe the ref, if it exists, from the removed vector. Use std::partition rather
217 : : // than std::erase because we don't care about the order of the entries that
218 : : // remain.
219 [ + + - + ]: 156340 : auto remove = std::partition(removed.begin(), removed.end(), [&](auto& arg) { return arg.get() != ref; });
220 : 8690 : removed.erase(remove, removed.end());
221 : : } else {
222 : 26829 : MakeModified(pos);
223 : 26829 : graph.RemoveTransactions(SetType::Singleton(pos));
224 : 26829 : real_is_optimal = false;
225 : 26829 : simrevmap.erase(simmap[pos].get());
226 : 26829 : simmap[pos].reset();
227 : : // This may invalidate our cached oversized value.
228 [ + + + + : 26829 : if (reset_oversize && oversized.has_value() && *oversized) {
+ + ]
229 : 3960 : oversized = std::nullopt;
230 : : }
231 : : }
232 : 35519 : }
233 : :
234 : : /** Construct the set with all positions in this graph corresponding to the specified
235 : : * TxGraph::Refs. All of them must occur in this graph and not be removed. */
236 : 752851 : SetType MakeSet(std::span<TxGraph::Ref* const> arg)
237 : : {
238 : 752851 : SetType ret;
239 [ + + ]: 5803138 : for (TxGraph::Ref* ptr : arg) {
240 : 5050287 : auto pos = Find(ptr);
241 [ - + ]: 5050287 : assert(pos != Pos(-1));
242 : 5050287 : ret.Set(pos);
243 : : }
244 : 752851 : return ret;
245 : : }
246 : :
247 : : /** Get the set of ancestors (desc=false) or descendants (desc=true) in this graph. */
248 : 61960 : SetType GetAncDesc(TxGraph::Ref* arg, bool desc)
249 : : {
250 : 61960 : auto pos = Find(arg);
251 [ + + ]: 61960 : if (pos == MISSING) return {};
252 [ + + ]: 43269 : return desc ? graph.Descendants(pos) : graph.Ancestors(pos);
253 : : }
254 : :
255 : : /** Given a set of Refs (given as a vector of pointers), expand the set to include all its
256 : : * ancestors (desc=false) or all its descendants (desc=true) in this graph. */
257 : 40232 : void IncludeAncDesc(std::vector<TxGraph::Ref*>& arg, bool desc)
258 : : {
259 : 40232 : std::vector<TxGraph::Ref*> ret;
260 [ + + ]: 94084 : for (auto ptr : arg) {
261 : 53852 : auto simpos = Find(ptr);
262 [ + + ]: 53852 : if (simpos != MISSING) {
263 [ + + + + ]: 113551 : for (auto i : desc ? graph.Descendants(simpos) : graph.Ancestors(simpos)) {
264 [ + - ]: 76574 : ret.push_back(simmap[i].get());
265 : : }
266 : : } else {
267 [ + - ]: 16875 : ret.push_back(ptr);
268 : : }
269 : : }
270 : : // Construct deduplicated version in input (do not use std::sort/std::unique for
271 : : // deduplication as it'd rely on non-deterministic pointer comparison).
272 [ + - ]: 40232 : arg.clear();
273 [ + + ]: 133681 : for (auto ptr : ret) {
274 [ + + ]: 93449 : if (std::find(arg.begin(), arg.end(), ptr) == arg.end()) {
275 [ + - ]: 61533 : arg.push_back(ptr);
276 : : }
277 : : }
278 : 40232 : }
279 : :
280 : :
281 : : /** Verify that set contains transactions from every oversized cluster, and nothing from
282 : : * non-oversized ones. */
283 : 22282 : bool MatchesOversizedClusters(const SetType& set)
284 : : {
285 [ + - + - ]: 44564 : if (set.Any() && !IsOversized()) return false;
286 : :
287 : 22282 : auto todo = graph.Positions();
288 [ + - ]: 44564 : if (!set.IsSubsetOf(todo)) return false;
289 : :
290 : : // Walk all clusters, and make sure all of set doesn't come from non-oversized clusters
291 [ + + ]: 445196 : while (todo.Any()) {
292 : 200316 : auto component = graph.FindConnectedComponent(todo);
293 : : // Determine whether component is oversized, due to either the size or count limit.
294 : 200316 : bool is_oversized = component.Count() > max_cluster_count;
295 : 200316 : uint64_t component_size{0};
296 [ + + ]: 1337404 : for (auto i : component) component_size += graph.FeeRate(i).size;
297 : 200316 : is_oversized |= component_size > max_cluster_size;
298 : : // Check whether overlap with set matches is_oversized.
299 [ + - ]: 400632 : if (is_oversized != set.Overlaps(component)) return false;
300 : 200316 : todo -= component;
301 : : }
302 : : return true;
303 : : }
304 : : };
305 : :
306 : : } // namespace
307 : :
308 [ + - ]: 4066 : FUZZ_TARGET(txgraph)
309 : : {
310 : : // This is a big simulation test for TxGraph, which performs a fuzz-derived sequence of valid
311 : : // operations on a TxGraph instance, as well as on a simpler (mostly) reimplementation (see
312 : : // SimTxGraph above), comparing the outcome of functions that return a result, and finally
313 : : // performing a full comparison between the two.
314 : :
315 : 3590 : SeedRandomStateForTest(SeedRand::ZEROS);
316 : 3590 : FuzzedDataProvider provider(buffer.data(), buffer.size());
317 : :
318 : : /** Internal test RNG, used only for decisions which would require significant amount of data
319 : : * to be read from the provider, without realistically impacting test sensitivity, and for
320 : : * specialized test cases that are hard to perform more generically. */
321 : 3590 : InsecureRandomContext rng(provider.ConsumeIntegral<uint64_t>());
322 : :
323 : : /** Variable used whenever an empty SimTxObject is needed. */
324 : 3590 : SimTxObject empty_ref;
325 : :
326 : : /** The maximum number of transactions per (non-oversized) cluster we will use in this
327 : : * simulation. */
328 : 3590 : auto max_cluster_count = provider.ConsumeIntegralInRange<DepGraphIndex>(1, MAX_CLUSTER_COUNT_LIMIT);
329 : : /** The maximum total size of transactions in a (non-oversized) cluster. */
330 : 3590 : auto max_cluster_size = provider.ConsumeIntegralInRange<uint64_t>(1, 0x3fffff * MAX_CLUSTER_COUNT_LIMIT);
331 : : /** The amount of work to consider a cluster acceptably linearized. */
332 : 3590 : auto acceptable_cost = provider.ConsumeIntegralInRange<uint64_t>(0, 10000);
333 : :
334 : : /** The set of uint64_t "txid"s that have been assigned before. */
335 : 3590 : std::set<uint64_t> assigned_txids;
336 : :
337 : : // Construct a real graph, and a vector of simulated graphs (main, and possibly staging).
338 : 2663909 : auto fallback_order = [&](const TxGraph::Ref& a, const TxGraph::Ref& b) noexcept {
339 : 2660319 : uint64_t txid_a = static_cast<const SimTxObject&>(a).m_txid;
340 : 2660319 : uint64_t txid_b = static_cast<const SimTxObject&>(b).m_txid;
341 [ - + ]: 2660319 : assert(assigned_txids.contains(txid_a));
342 [ - + ]: 2660319 : assert(assigned_txids.contains(txid_b));
343 [ + - + + ]: 2660319 : return txid_a <=> txid_b;
344 : 3590 : };
345 : 3590 : auto real = MakeTxGraph(
346 : : /*max_cluster_count=*/max_cluster_count,
347 : : /*max_cluster_size=*/max_cluster_size,
348 : : /*acceptable_cost=*/acceptable_cost,
349 : 3590 : /*fallback_order=*/fallback_order);
350 : :
351 : 3590 : std::vector<SimTxGraph> sims;
352 [ + - ]: 3590 : sims.reserve(2);
353 [ + - ]: 3590 : sims.emplace_back(max_cluster_count, max_cluster_size);
354 : :
355 : : /** Struct encapsulating information about a BlockBuilder that's currently live. */
356 : 7687 : struct BlockBuilderData
357 : : {
358 : : /** BlockBuilder object from real. */
359 : : std::unique_ptr<TxGraph::BlockBuilder> builder;
360 : : /** The set of transactions marked as included in *builder. */
361 : : SimTxGraph::SetType included;
362 : : /** The set of transactions marked as included or skipped in *builder. */
363 : : SimTxGraph::SetType done;
364 : : /** The last chunk feerate returned by *builder. IsEmpty() if none yet. */
365 : : FeePerWeight last_feerate;
366 : :
367 : 2128 : BlockBuilderData(std::unique_ptr<TxGraph::BlockBuilder> builder_in) : builder(std::move(builder_in)) {}
368 : : };
369 : :
370 : : /** Currently active block builders. */
371 : 3590 : std::vector<BlockBuilderData> block_builders;
372 : :
373 : : /** Function to pick any SimTxObject (for either sim in sims: from sim.simmap or sim.removed, or the
374 : : * empty one). */
375 : 449058 : auto pick_fn = [&]() noexcept -> SimTxObject* {
376 [ - + ]: 445468 : size_t tx_count[2] = {sims[0].GetTransactionCount(), 0};
377 : : /** The number of possible choices. */
378 [ - + ]: 445468 : size_t choices = tx_count[0] + sims[0].removed.size() + 1;
379 [ - + + + ]: 445468 : if (sims.size() == 2) {
380 [ - + ]: 121859 : tx_count[1] = sims[1].GetTransactionCount();
381 [ - + ]: 121859 : choices += tx_count[1] + sims[1].removed.size();
382 : : }
383 : : /** Pick one of them. */
384 : 445468 : auto choice = provider.ConsumeIntegralInRange<size_t>(0, choices - 1);
385 : : // Consider both main and (if it exists) staging.
386 [ - + + + ]: 582331 : for (size_t level = 0; level < sims.size(); ++level) {
387 [ + + ]: 508256 : auto& sim = sims[level];
388 [ + + ]: 508256 : if (choice < tx_count[level]) {
389 : : // Return from graph.
390 [ + - ]: 3741325 : for (auto i : sim.graph.Positions()) {
391 [ + + ]: 3741325 : if (choice == 0) return sim.GetRef(i);
392 : 3397482 : --choice;
393 : : }
394 : 0 : assert(false);
395 : : } else {
396 : 164413 : choice -= tx_count[level];
397 : : }
398 [ - + + + ]: 164413 : if (choice < sim.removed.size()) {
399 : : // Return from removed.
400 : 27550 : return sim.removed[choice].get();
401 : : } else {
402 : 136863 : choice -= sim.removed.size();
403 : : }
404 : : }
405 : : // Return empty.
406 [ - + ]: 74075 : assert(choice == 0);
407 : 74075 : return &empty_ref;
408 : 3590 : };
409 : :
410 : : /** Function to construct the correct fee-size diagram a real graph has based on its graph
411 : : * order (as reported by GetCluster(), so it works for both main and staging). */
412 : 7981 : auto get_diagram_fn = [&](TxGraph::Level level_select) -> std::vector<FeeFrac> {
413 [ + + - + ]: 4391 : int level = level_select == TxGraph::Level::MAIN ? 0 : sims.size() - 1;
414 : 4391 : auto& sim = sims[level];
415 : : // For every transaction in the graph, request its cluster, and throw them into a set.
416 : 4391 : std::set<std::vector<TxGraph::Ref*>> clusters;
417 [ + + ]: 180952 : for (auto i : sim.graph.Positions()) {
418 : 176561 : auto ref = sim.GetRef(i);
419 [ + - ]: 353122 : clusters.insert(real->GetCluster(*ref, level_select));
420 : : }
421 : : // Compute the chunkings of each (deduplicated) cluster.
422 : 4391 : size_t num_tx{0};
423 : 4391 : std::vector<FeeFrac> chunk_feerates;
424 [ + + ]: 109082 : for (const auto& cluster : clusters) {
425 [ - + ]: 104691 : num_tx += cluster.size();
426 : 104691 : std::vector<SimTxGraph::Pos> linearization;
427 [ + - ]: 104691 : linearization.reserve(cluster.size());
428 [ + - + + ]: 281252 : for (auto refptr : cluster) linearization.push_back(sim.Find(refptr));
429 [ - + + + ]: 250803 : for (const FeeFrac& chunk_feerate : ChunkLinearization(sim.graph, linearization)) {
430 [ + - ]: 146112 : chunk_feerates.push_back(chunk_feerate);
431 : 104691 : }
432 : 104691 : }
433 : : // Verify the number of transactions after deduplicating clusters. This implicitly verifies
434 : : // that GetCluster on each element of a cluster reports the cluster transactions in the same
435 : : // order.
436 [ - + ]: 4391 : assert(num_tx == sim.GetTransactionCount());
437 : : // Sort by feerate only, since violating topological constraints within same-feerate
438 : : // chunks won't affect diagram comparisons.
439 : 4391 : std::ranges::sort(chunk_feerates, std::greater<ByRatioNegSize<FeeFrac>>{});
440 : 4391 : return chunk_feerates;
441 : 7981 : };
442 : :
443 [ + + + + ]: 493876 : LIMITED_WHILE (provider.remaining_bytes() > 0, 200) {
444 : : // Read a one-byte command.
445 : 490286 : int command = provider.ConsumeIntegral<uint8_t>();
446 : 490286 : int orig_command = command;
447 : :
448 : : // Treat the lowest bit of a command as a flag (which selects a variant of some of the
449 : : // operations), and the second-lowest bit as a way of selecting main vs. staging, and leave
450 : : // the rest of the bits in command.
451 : 490286 : bool alt = command & 1;
452 : 490286 : TxGraph::Level level_select = (command & 2) ? TxGraph::Level::MAIN : TxGraph::Level::TOP;
453 : 490286 : command >>= 2;
454 : :
455 : : /** Use the bottom 2 bits of command to select an entry in the block_builders vector (if
456 : : * any). These use the same bits as alt/level_select, so don't use those in actions below
457 : : * where builder_idx is used as well. */
458 [ - + + + ]: 490286 : int builder_idx = block_builders.empty() ? -1 : int((orig_command & 3) % block_builders.size());
459 : :
460 : : // Provide convenient aliases for the top simulated graph (main, or staging if it exists),
461 : : // one for the simulated graph selected based on level_select (for operations that can operate
462 : : // on both graphs), and one that always refers to the main graph.
463 : 490286 : auto& top_sim = sims.back();
464 [ + + ]: 490286 : auto& sel_sim = level_select == TxGraph::Level::MAIN ? sims[0] : top_sim;
465 : 490286 : auto& main_sim = sims[0];
466 : :
467 : : // Keep decrementing command for each applicable operation, until one is hit. Multiple
468 : : // iterations may be necessary.
469 : 711597 : while (true) {
470 [ + + + + : 776916 : if ((block_builders.empty() || sims.size() > 1) && top_sim.GetTransactionCount() < SimTxGraph::MAX_TRANSACTIONS && command-- == 0) {
+ + + + ]
471 : : // AddTransaction.
472 : 230200 : int64_t fee;
473 : 230200 : int32_t size;
474 [ + + ]: 230200 : if (alt) {
475 : : // If alt is true, pick fee and size from the entire range.
476 : 5285 : fee = provider.ConsumeIntegralInRange<int64_t>(-0x8000000000000, 0x7ffffffffffff);
477 : 5285 : size = provider.ConsumeIntegralInRange<int32_t>(1, 0x3fffff);
478 : : } else {
479 : : // Otherwise, use smaller range which consume fewer fuzz input bytes, as just
480 : : // these are likely sufficient to trigger all interesting code paths already.
481 : 224915 : fee = provider.ConsumeIntegral<uint8_t>();
482 : 224915 : size = provider.ConsumeIntegralInRange<uint32_t>(1, 0xff);
483 : : }
484 : 230200 : FeePerWeight feerate{fee, size};
485 : : // Pick a novel txid (and not 0, which is reserved for empty_ref).
486 : 230200 : uint64_t txid;
487 : 230200 : do {
488 : 230200 : txid = rng.rand64();
489 [ + - - + : 230200 : } while (txid == 0 || assigned_txids.contains(txid));
- + ]
490 [ + - ]: 230200 : assigned_txids.insert(txid);
491 : : // Create the transaction in the simulation and the real graph.
492 [ + - ]: 230200 : top_sim.AddTransaction(*real, feerate, txid);
493 : : break;
494 [ + + + + : 539793 : } else if ((block_builders.empty() || sims.size() > 1) && top_sim.GetTransactionCount() + top_sim.removed.size() > 1 && command-- == 0) {
- + + + +
+ ]
495 : : // AddDependency.
496 : 25042 : auto par = pick_fn();
497 : 25042 : auto chl = pick_fn();
498 : 25042 : auto pos_par = top_sim.Find(par);
499 : 25042 : auto pos_chl = top_sim.Find(chl);
500 [ + + ]: 25042 : if (pos_par != SimTxGraph::MISSING && pos_chl != SimTxGraph::MISSING) {
501 : : // Determine if adding this would introduce a cycle (not allowed by TxGraph),
502 : : // and if so, skip.
503 [ + + ]: 19779 : if (top_sim.graph.Ancestors(pos_par)[pos_chl]) break;
504 : : }
505 : 20658 : top_sim.AddDependency(par, chl);
506 : 20658 : top_sim.real_is_optimal = false;
507 : 20658 : real->AddDependency(*par, *chl);
508 : 20658 : break;
509 [ + + + + : 513747 : } else if ((block_builders.empty() || sims.size() > 1) && top_sim.removed.size() < 100 && command-- == 0) {
- + + + +
+ ]
510 : : // RemoveTransaction. Either all its ancestors or all its descendants are also
511 : : // removed (if any), to make sure TxGraph's reordering of removals and dependencies
512 : : // has no effect.
513 : 11754 : std::vector<TxGraph::Ref*> to_remove;
514 [ + - ]: 11754 : to_remove.push_back(pick_fn());
515 [ + - ]: 11754 : top_sim.IncludeAncDesc(to_remove, alt);
516 : : // The order in which these ancestors/descendants are removed should not matter;
517 : : // randomly shuffle them.
518 : 11754 : std::shuffle(to_remove.begin(), to_remove.end(), rng);
519 [ + + ]: 25437 : for (TxGraph::Ref* ptr : to_remove) {
520 : 13683 : real->RemoveTransaction(*ptr);
521 [ + - ]: 13683 : top_sim.RemoveTransaction(ptr);
522 : : }
523 : 11754 : break;
524 [ - + + + : 456355 : } else if (sel_sim.removed.size() > 0 && command-- == 0) {
+ + ]
525 : : // ~Ref (of an already-removed transaction). Destroying a TxGraph::Ref has an
526 : : // observable effect on the TxGraph it refers to, so this simulation permits doing
527 : : // so separately from other actions on TxGraph.
528 : :
529 : : // Pick a Ref of sel_sim.removed to destroy. Note that the same Ref may still occur
530 : : // in the other graph, and thus not actually trigger ~Ref yet (which is exactly
531 : : // what we want, as destroying Refs is only allowed when it does not refer to an
532 : : // existing transaction in either graph).
533 : 3461 : auto removed_pos = provider.ConsumeIntegralInRange<size_t>(0, sel_sim.removed.size() - 1);
534 [ - + + + ]: 3461 : if (removed_pos != sel_sim.removed.size() - 1) {
535 : 2020 : std::swap(sel_sim.removed[removed_pos], sel_sim.removed.back());
536 : : }
537 : 3461 : sel_sim.removed.pop_back();
538 : 3461 : break;
539 [ + + + + ]: 441140 : } else if (block_builders.empty() && command-- == 0) {
540 : : // ~Ref (of any transaction).
541 : 16451 : std::vector<TxGraph::Ref*> to_destroy;
542 [ + - ]: 16451 : to_destroy.push_back(pick_fn());
543 : 18275 : while (true) {
544 : : // Keep adding either the ancestors or descendants the already picked
545 : : // transactions have in both graphs (main and staging) combined. Destroying
546 : : // will trigger deletions in both, so to have consistent TxGraph behavior, the
547 : : // set must be closed under ancestors, or descendants, in both graphs.
548 [ - + ]: 18275 : auto old_size = to_destroy.size();
549 [ + - + + ]: 46753 : for (auto& sim : sims) sim.IncludeAncDesc(to_destroy, alt);
550 [ - + + + ]: 18275 : if (to_destroy.size() == old_size) break;
551 : : }
552 : : // The order in which these ancestors/descendants are destroyed should not matter;
553 : : // randomly shuffle them.
554 : 16451 : std::shuffle(to_destroy.begin(), to_destroy.end(), rng);
555 [ + + ]: 38654 : for (TxGraph::Ref* ptr : to_destroy) {
556 [ - + + + ]: 57722 : for (size_t level = 0; level < sims.size(); ++level) {
557 : 35519 : sims[level].DestroyTransaction(ptr, level == sims.size() - 1);
558 : : }
559 : : }
560 : 16451 : break;
561 [ + + + + ]: 441140 : } else if (block_builders.empty() && command-- == 0) {
562 : : // SetTransactionFee.
563 : 6549 : int64_t fee;
564 [ + + ]: 6549 : if (alt) {
565 : 2316 : fee = provider.ConsumeIntegralInRange<int64_t>(-0x8000000000000, 0x7ffffffffffff);
566 : : } else {
567 : 4233 : fee = provider.ConsumeIntegral<uint8_t>();
568 : : }
569 : 6549 : auto ref = pick_fn();
570 : 6549 : real->SetTransactionFee(*ref, fee);
571 [ + + ]: 14840 : for (auto& sim : sims) {
572 : 8291 : sim.SetTransactionFee(ref, fee);
573 : : }
574 : : break;
575 [ + + ]: 418140 : } else if (command-- == 0) {
576 : : // GetTransactionCount.
577 [ - + ]: 6594 : assert(real->GetTransactionCount(level_select) == sel_sim.GetTransactionCount());
578 : : break;
579 [ + + ]: 411546 : } else if (command-- == 0) {
580 : : // Exists.
581 : 6081 : auto ref = pick_fn();
582 : 6081 : bool exists = real->Exists(*ref, level_select);
583 : 6081 : bool should_exist = sel_sim.Find(ref) != SimTxGraph::MISSING;
584 [ - + ]: 6081 : assert(exists == should_exist);
585 : : break;
586 [ + + ]: 405465 : } else if (command-- == 0) {
587 : : // IsOversized.
588 [ + - - + ]: 9938 : assert(sel_sim.IsOversized() == real->IsOversized(level_select));
589 : : break;
590 [ + + ]: 395527 : } else if (command-- == 0) {
591 : : // GetIndividualFeerate.
592 : 5730 : auto ref = pick_fn();
593 : 5730 : auto feerate = real->GetIndividualFeerate(*ref);
594 : 5730 : bool found{false};
595 [ + + ]: 13894 : for (auto& sim : sims) {
596 : 8164 : auto simpos = sim.Find(ref);
597 [ + + ]: 8164 : if (simpos != SimTxGraph::MISSING) {
598 : 3885 : found = true;
599 [ + - ]: 12049 : assert(feerate == sim.graph.FeeRate(simpos));
600 : : }
601 : : }
602 [ + + - + ]: 5730 : if (!found) assert(feerate.IsEmpty());
603 : : break;
604 [ + - + + : 389797 : } else if (!main_sim.IsOversized() && command-- == 0) {
+ + ]
605 : : // GetMainChunkFeerate.
606 : 4928 : auto ref = pick_fn();
607 : 4928 : auto feerate = real->GetMainChunkFeerate(*ref);
608 : 4928 : auto simpos = main_sim.Find(ref);
609 [ + + ]: 4928 : if (simpos == SimTxGraph::MISSING) {
610 [ - + ]: 1878 : assert(feerate.IsEmpty());
611 : : } else {
612 : : // Just do some quick checks that the reported value is in range. A full
613 : : // recomputation of expected chunk feerates is done at the end.
614 [ - + ]: 3050 : assert(feerate.size >= main_sim.graph.FeeRate(simpos).size);
615 [ - + ]: 3050 : assert(feerate.size <= main_sim.SumAll().size);
616 : : }
617 : : break;
618 [ + - + + : 384869 : } else if (!sel_sim.IsOversized() && command-- == 0) {
+ + ]
619 : : // GetAncestors/GetDescendants.
620 : 8062 : auto ref = pick_fn();
621 [ + + ]: 8062 : auto result = alt ? real->GetDescendants(*ref, level_select)
622 : 8062 : : real->GetAncestors(*ref, level_select);
623 [ - + - + ]: 8062 : assert(result.size() <= max_cluster_count);
624 : 8062 : auto result_set = sel_sim.MakeSet(result);
625 [ - + - + ]: 8062 : assert(result.size() == result_set.Count());
626 : 8062 : auto expect_set = sel_sim.GetAncDesc(ref, alt);
627 [ - + ]: 8062 : assert(result_set == expect_set);
628 : 8062 : break;
629 [ + - + + : 384869 : } else if (!sel_sim.IsOversized() && command-- == 0) {
+ + ]
630 : : // GetAncestorsUnion/GetDescendantsUnion.
631 : 9159 : std::vector<TxGraph::Ref*> refs;
632 : : // Gather a list of up to 15 Ref pointers.
633 : 9159 : auto count = provider.ConsumeIntegralInRange<size_t>(0, 15);
634 [ + - ]: 9159 : refs.resize(count);
635 [ + + ]: 63057 : for (size_t i = 0; i < count; ++i) {
636 : 53898 : refs[i] = pick_fn();
637 : : }
638 : : // Their order should not matter, shuffle them.
639 : 9159 : std::shuffle(refs.begin(), refs.end(), rng);
640 : : // Invoke the real function, and convert to SimPos set.
641 [ + + ]: 9159 : auto result = alt ? real->GetDescendantsUnion(refs, level_select)
642 [ - + - + ]: 9159 : : real->GetAncestorsUnion(refs, level_select);
643 [ - + ]: 9159 : auto result_set = sel_sim.MakeSet(result);
644 [ - + - + ]: 9159 : assert(result.size() == result_set.Count());
645 : : // Compute the expected result.
646 : 9159 : SimTxGraph::SetType expect_set;
647 [ + + ]: 63057 : for (TxGraph::Ref* ref : refs) expect_set |= sel_sim.GetAncDesc(ref, alt);
648 : : // Compare.
649 [ - + ]: 9159 : assert(result_set == expect_set);
650 : 9159 : break;
651 [ + - + + : 376807 : } else if (!sel_sim.IsOversized() && command-- == 0) {
+ + ]
652 : : // GetCluster.
653 : 6998 : auto ref = pick_fn();
654 : 6998 : auto result = real->GetCluster(*ref, level_select);
655 : : // Check cluster count limit.
656 [ - + - + ]: 6998 : assert(result.size() <= max_cluster_count);
657 : : // Require the result to be topologically valid and not contain duplicates.
658 : 6998 : auto left = sel_sim.graph.Positions();
659 : 6998 : uint64_t total_size{0};
660 [ + + ]: 38805 : for (auto refptr : result) {
661 : 31807 : auto simpos = sel_sim.Find(refptr);
662 [ - + ]: 31807 : total_size += sel_sim.graph.FeeRate(simpos).size;
663 [ - + ]: 31807 : assert(simpos != SimTxGraph::MISSING);
664 [ - + ]: 31807 : assert(left[simpos]);
665 : 31807 : left.Reset(simpos);
666 [ - + ]: 63614 : assert(!sel_sim.graph.Ancestors(simpos).Overlaps(left));
667 : : }
668 : : // Check cluster size limit.
669 [ - + ]: 6998 : assert(total_size <= max_cluster_size);
670 : : // Require the set to be connected.
671 [ - + ]: 6998 : auto result_set = sel_sim.MakeSet(result);
672 [ - + ]: 6998 : assert(sel_sim.graph.IsConnected(result_set));
673 : : // If ref exists, the result must contain it. If not, it must be empty.
674 : 6998 : auto simpos = sel_sim.Find(ref);
675 [ + + ]: 6998 : if (simpos != SimTxGraph::MISSING) {
676 [ - + ]: 3537 : assert(result_set[simpos]);
677 : : } else {
678 [ - + ]: 3461 : assert(result_set.None());
679 : : }
680 : : // Require the set not to have ancestors or descendants outside of it.
681 [ + + ]: 38805 : for (auto i : result_set) {
682 [ - + ]: 63614 : assert(sel_sim.graph.Ancestors(i).IsSubsetOf(result_set));
683 [ - + ]: 31807 : assert(sel_sim.graph.Descendants(i).IsSubsetOf(result_set));
684 : : }
685 : 6998 : break;
686 [ + + ]: 367648 : } else if (command-- == 0) {
687 : : // HaveStaging.
688 [ - + - + ]: 6295 : assert((sims.size() == 2) == real->HaveStaging());
689 : : break;
690 [ - + + + : 354355 : } else if (sims.size() < 2 && command-- == 0) {
+ + ]
691 : : // StartStaging.
692 [ + - ]: 17180 : sims.emplace_back(sims.back());
693 : 17180 : sims.back().modified = SimTxGraph::SetType{};
694 : 17180 : real->StartStaging();
695 : 17180 : break;
696 [ + + + + : 337175 : } else if (block_builders.empty() && sims.size() > 1 && command-- == 0) {
+ + ]
697 : : // CommitStaging.
698 : 3870 : real->CommitStaging();
699 : : // Resulting main level is only guaranteed to be optimal if all levels are
700 [ + + ]: 8104 : const bool main_optimal = std::all_of(sims.cbegin(), sims.cend(), [](const auto &sim) { return sim.real_is_optimal; });
701 : 3870 : sims.erase(sims.begin());
702 : 3870 : sims.front().real_is_optimal = main_optimal;
703 : 3870 : break;
704 [ + + + + ]: 333305 : } else if (sims.size() > 1 && command-- == 0) {
705 : : // AbortStaging.
706 : 11540 : real->AbortStaging();
707 : 11540 : sims.pop_back();
708 : : // Reset the cached oversized value (if TxGraph::Ref destructions triggered
709 : : // removals of main transactions while staging was active, then aborting will
710 : : // cause it to be re-evaluated in TxGraph).
711 [ + - ]: 501826 : sims.back().oversized = std::nullopt;
712 : : break;
713 [ + - + + : 321765 : } else if (!main_sim.IsOversized() && command-- == 0) {
+ + ]
714 : : // CompareMainOrder.
715 : 5922 : auto ref_a = pick_fn();
716 : 5922 : auto ref_b = pick_fn();
717 : 5922 : auto sim_a = main_sim.Find(ref_a);
718 : 5922 : auto sim_b = main_sim.Find(ref_b);
719 : : // Both transactions must exist in the main graph.
720 [ + + ]: 5922 : if (sim_a == SimTxGraph::MISSING || sim_b == SimTxGraph::MISSING) break;
721 : 3024 : auto cmp = real->CompareMainOrder(*ref_a, *ref_b);
722 : : // Distinct transactions have distinct places.
723 [ + + - + ]: 3024 : if (sim_a != sim_b) assert(cmp != 0);
724 : : // Ancestors go before descendants.
725 [ + + - + ]: 3024 : if (main_sim.graph.Ancestors(sim_a)[sim_b]) assert(cmp >= 0);
726 [ + + - + ]: 3024 : if (main_sim.graph.Descendants(sim_a)[sim_b]) assert(cmp <= 0);
727 : : // Do not verify consistency with chunk feerates, as we cannot easily determine
728 : : // these here without making more calls to real, which could affect its internal
729 : : // state. A full comparison is done at the end.
730 : : break;
731 [ + - + + : 315843 : } else if (!sel_sim.IsOversized() && command-- == 0) {
+ + ]
732 : : // CountDistinctClusters.
733 : 6720 : std::vector<TxGraph::Ref*> refs;
734 : : // Gather a list of up to 15 (or up to 255) Ref pointers.
735 [ + + ]: 11299 : auto count = provider.ConsumeIntegralInRange<size_t>(0, alt ? 255 : 15);
736 [ + - ]: 6720 : refs.resize(count);
737 [ + + ]: 269809 : for (size_t i = 0; i < count; ++i) {
738 : 263089 : refs[i] = pick_fn();
739 : : }
740 : : // Their order should not matter, shuffle them.
741 : 6720 : std::shuffle(refs.begin(), refs.end(), rng);
742 : : // Invoke the real function.
743 [ - + ]: 6720 : auto result = real->CountDistinctClusters(refs, level_select);
744 : : // Build a set with representatives of the clusters the Refs occur in the
745 : : // simulated graph. For each, remember the lowest-index transaction SimPos in the
746 : : // cluster.
747 : 6720 : SimTxGraph::SetType sim_reps;
748 [ + + ]: 269809 : for (auto ref : refs) {
749 : : // Skip Refs that do not occur in the simulated graph.
750 : 263089 : auto simpos = sel_sim.Find(ref);
751 [ + + ]: 263089 : if (simpos == SimTxGraph::MISSING) continue;
752 : : // Find the component that includes ref.
753 : 201586 : auto component = sel_sim.graph.GetConnectedComponent(sel_sim.graph.Positions(), simpos);
754 : : // Remember the lowest-index SimPos in component, as a representative for it.
755 [ - + ]: 403172 : assert(component.Any());
756 : 201586 : sim_reps.Set(component.First());
757 : : }
758 : : // Compare the number of deduplicated representatives with the value returned by
759 : : // the real function.
760 [ - + ]: 6720 : assert(result == sim_reps.Count());
761 : 6720 : break;
762 [ + + ]: 315843 : } else if (command-- == 0) {
763 : : // DoWork.
764 [ + + ]: 19876 : uint64_t max_cost = provider.ConsumeIntegralInRange<uint64_t>(0, alt ? 10000 : 255);
765 : 13536 : bool ret = real->DoWork(max_cost);
766 : 13536 : uint64_t cost_for_optimal{0};
767 [ - + + + ]: 32870 : for (unsigned level = 0; level < sims.size(); ++level) {
768 : : // DoWork() will not optimize oversized levels, or the main level if a builder
769 : : // is present. Note that this impacts the DoWork() return value, as true means
770 : : // that non-optimal clusters may remain within such oversized or builder-having
771 : : // levels.
772 [ + - + + ]: 19334 : if (sims[level].IsOversized()) continue;
773 [ + + + + ]: 15540 : if (level == 0 && !block_builders.empty()) continue;
774 : : // If neither of the two above conditions holds, and DoWork() returned true,
775 : : // then the level is optimal.
776 [ + + ]: 12461 : if (ret) {
777 : 5141 : sims[level].real_is_optimal = true;
778 : : }
779 : : // Compute how much work would be needed to make everything optimal.
780 [ + - + + ]: 289660 : for (auto component : sims[level].GetComponents()) {
781 : 277199 : auto cost_opt_this_cluster = MaxOptimalLinearizationCost(component.Count());
782 [ + + ]: 277199 : if (cost_opt_this_cluster > acceptable_cost) {
783 : : // If the amount of work required to linearize this cluster
784 : : // optimally exceeds acceptable_cost, DoWork() may process it in two
785 : : // stages: once to acceptable, and once to optimal.
786 : 16605 : cost_for_optimal += cost_opt_this_cluster + acceptable_cost;
787 : : } else {
788 : 260594 : cost_for_optimal += cost_opt_this_cluster;
789 : : }
790 : 12461 : }
791 : : }
792 [ + + ]: 13536 : if (!ret) {
793 : : // DoWork can only have more work left if the requested amount of work
794 : : // was insufficient to linearize everything optimally within the levels it is
795 : : // allowed to touch.
796 [ - + ]: 5746 : assert(max_cost <= cost_for_optimal);
797 : : }
798 : : break;
799 : 295587 : } else if (sims.size() == 2 && !sims[0].IsOversized() && !sims[1].IsOversized() && command-- == 0) {
[ - + + +
+ - + + +
- + + +
+ ]
800 : : // GetMainStagingDiagrams()
801 : 21505 : auto [real_main_diagram, real_staged_diagram] = real->GetMainStagingDiagrams();
802 : 21505 : auto real_sum_main = std::accumulate(real_main_diagram.begin(), real_main_diagram.end(), FeeFrac{});
803 : 21505 : auto real_sum_staged = std::accumulate(real_staged_diagram.begin(), real_staged_diagram.end(), FeeFrac{});
804 : 21505 : auto real_gain = real_sum_staged - real_sum_main;
805 [ + - ]: 21505 : auto sim_gain = sims[1].SumAll() - sims[0].SumAll();
806 : : // Just check that the total fee gained/lost and size gained/lost according to the
807 : : // diagram matches the difference in these values in the simulated graph. A more
808 : : // complete check of the GetMainStagingDiagrams result is performed at the end.
809 [ + - ]: 21505 : assert(sim_gain == real_gain);
810 : : // Check that the feerates in each diagram are monotonically decreasing.
811 [ - + + + ]: 647482 : for (size_t i = 1; i < real_main_diagram.size(); ++i) {
812 [ - + ]: 625977 : assert(ByRatio{real_main_diagram[i]} <= ByRatio{real_main_diagram[i - 1]});
813 : : }
814 [ - + + + ]: 495621 : for (size_t i = 1; i < real_staged_diagram.size(); ++i) {
815 [ - + ]: 474116 : assert(ByRatio{real_staged_diagram[i]} <= ByRatio{real_staged_diagram[i - 1]});
816 : : }
817 : 21505 : break;
818 [ - + + + : 295587 : } else if (block_builders.size() < 4 && !main_sim.IsOversized() && command-- == 0) {
+ - + + +
+ ]
819 : : // GetBlockBuilder.
820 [ + - ]: 2128 : block_builders.emplace_back(real->GetBlockBuilder());
821 : 2128 : break;
822 [ + + + + ]: 271954 : } else if (!block_builders.empty() && command-- == 0) {
823 : : // ~BlockBuilder.
824 : 1068 : block_builders.erase(block_builders.begin() + builder_idx);
825 : : break;
826 [ + + + + ]: 270886 : } else if (!block_builders.empty() && command-- == 0) {
827 : : // BlockBuilder::GetCurrentChunk, followed by Include/Skip.
828 : 4937 : auto& builder_data = block_builders[builder_idx];
829 : 4937 : auto new_included = builder_data.included;
830 : 4937 : auto new_done = builder_data.done;
831 : 4937 : auto chunk = builder_data.builder->GetCurrentChunk();
832 [ + + ]: 4937 : if (chunk) {
833 : : // Chunk feerates must be monotonously decreasing.
834 [ + + ]: 3159 : if (!builder_data.last_feerate.IsEmpty()) {
835 [ - + ]: 2509 : assert(ByRatio{chunk->second} <= ByRatio{builder_data.last_feerate});
836 : : }
837 : 3159 : builder_data.last_feerate = chunk->second;
838 : : // Verify the contents of GetCurrentChunk.
839 : 3159 : FeePerWeight sum_feerate;
840 [ + + ]: 7466 : for (TxGraph::Ref* ref : chunk->first) {
841 : : // Each transaction in the chunk must exist in the main graph.
842 : 4307 : auto simpos = main_sim.Find(ref);
843 [ - + ]: 4307 : assert(simpos != SimTxGraph::MISSING);
844 : : // Verify the claimed chunk feerate.
845 : 4307 : sum_feerate += main_sim.graph.FeeRate(simpos);
846 : : // Make sure no transaction is reported twice.
847 [ - + ]: 4307 : assert(!new_done[simpos]);
848 : 4307 : new_done.Set(simpos);
849 : : // The concatenation of all included transactions must be topologically valid.
850 : 4307 : new_included.Set(simpos);
851 [ - + ]: 8614 : assert(main_sim.graph.Ancestors(simpos).IsSubsetOf(new_included));
852 : : }
853 [ + - ]: 3159 : assert(sum_feerate == chunk->second);
854 : : } else {
855 : : // When we reach the end, if nothing was skipped, the entire graph should have
856 : : // been reported.
857 [ + + ]: 1778 : if (builder_data.done == builder_data.included) {
858 [ - + ]: 1009 : assert(builder_data.done.Count() == main_sim.GetTransactionCount());
859 : : }
860 : : }
861 : : // Possibly invoke GetCurrentChunk() again, which should give the same result.
862 [ + + ]: 4937 : if ((orig_command % 7) >= 5) {
863 : 1459 : auto chunk2 = builder_data.builder->GetCurrentChunk();
864 [ - + ]: 1459 : assert(chunk == chunk2);
865 : 1459 : }
866 : : // Skip or include.
867 [ + + ]: 4937 : if ((orig_command % 5) >= 3) {
868 : : // Skip.
869 : 3019 : builder_data.builder->Skip();
870 : : } else {
871 : : // Include.
872 : 1918 : builder_data.builder->Include();
873 : 1918 : builder_data.included = new_included;
874 : : }
875 : 4937 : builder_data.done = new_done;
876 : 4937 : break;
877 [ + - + + : 270886 : } else if (!main_sim.IsOversized() && command-- == 0) {
+ + ]
878 : : // GetWorstMainChunk.
879 [ + + ]: 8926 : auto [worst_chunk, worst_chunk_feerate] = real->GetWorstMainChunk();
880 : : // Just do some sanity checks here. Consistency with GetBlockBuilder is checked
881 : : // below.
882 [ + + ]: 8926 : if (main_sim.GetTransactionCount() == 0) {
883 [ - + ]: 919 : assert(worst_chunk.empty());
884 [ - + ]: 919 : assert(worst_chunk_feerate.IsEmpty());
885 : : } else {
886 [ - + ]: 8007 : assert(!worst_chunk.empty());
887 : 8007 : SimTxGraph::SetType done;
888 : 8007 : FeePerWeight sum;
889 [ + + ]: 28114 : for (TxGraph::Ref* ref : worst_chunk) {
890 : : // Each transaction in the chunk must exist in the main graph.
891 : 20107 : auto simpos = main_sim.Find(ref);
892 [ - + ]: 20107 : assert(simpos != SimTxGraph::MISSING);
893 : 20107 : sum += main_sim.graph.FeeRate(simpos);
894 : : // Make sure the chunk contains no duplicate transactions.
895 [ - + ]: 20107 : assert(!done[simpos]);
896 : 20107 : done.Set(simpos);
897 : : // All elements are preceded by all their descendants.
898 [ - + ]: 40214 : assert(main_sim.graph.Descendants(simpos).IsSubsetOf(done));
899 : : }
900 [ + - ]: 8007 : assert(sum == worst_chunk_feerate);
901 : : }
902 : 8926 : break;
903 [ + + + + : 295468 : } else if ((block_builders.empty() || sims.size() > 1) && command-- == 0) {
+ + ]
904 : : // Trim.
905 [ + - ]: 8909 : bool was_oversized = top_sim.IsOversized();
906 : 8909 : auto removed = real->Trim();
907 : : // Verify that something was removed if and only if there was an oversized cluster.
908 [ - + ]: 8909 : assert(was_oversized == !removed.empty());
909 [ + + ]: 8909 : if (!was_oversized) break;
910 [ - + ]: 2740 : auto removed_set = top_sim.MakeSet(removed);
911 : : // The removed set must contain all its own descendants.
912 [ + + ]: 64460 : for (auto simpos : removed_set) {
913 [ - + ]: 123440 : assert(top_sim.graph.Descendants(simpos).IsSubsetOf(removed_set));
914 : : }
915 : : // Something from every oversized cluster should have been removed, and nothing
916 : : // else.
917 [ + - - + ]: 2740 : assert(top_sim.MatchesOversizedClusters(removed_set));
918 : :
919 : : // Apply all removals to the simulation, and verify the result is no longer
920 : : // oversized. Don't query the real graph for oversizedness; it is compared
921 : : // against the simulation anyway later.
922 [ + + ]: 64460 : for (auto simpos : removed_set) {
923 [ + - ]: 61720 : top_sim.RemoveTransaction(top_sim.GetRef(simpos));
924 : : }
925 [ + - - + ]: 2740 : assert(!top_sim.IsOversized());
926 : : break;
927 [ + + ]: 37158 : } else if ((block_builders.empty() || sims.size() > 1) &&
928 [ + + + + : 265521 : top_sim.GetTransactionCount() > max_cluster_count && !top_sim.IsOversized() && command-- == 0) {
+ - + + +
+ ]
929 : : // Trim (special case which avoids apparent cycles in the implicit approximate
930 : : // dependency graph constructed inside the Trim() implementation). This is worth
931 : : // testing separately, because such cycles cannot occur in realistic scenarios,
932 : : // but this is hard to replicate in general in this fuzz test.
933 : :
934 : : // First, we need to have dependencies applied and linearizations fixed to avoid
935 : : // circular dependencies in implied graph; trigger it via whatever means.
936 : 19542 : real->CountDistinctClusters({}, TxGraph::Level::TOP);
937 : :
938 : : // Gather the current clusters.
939 [ + - ]: 19542 : auto clusters = top_sim.GetComponents();
940 : :
941 : : // Merge clusters randomly until at least one oversized one appears.
942 : 19542 : bool made_oversized = false;
943 [ - + ]: 19542 : auto merges_left = clusters.size() - 1;
944 [ + + ]: 611541 : while (merges_left > 0) {
945 : 591999 : --merges_left;
946 : : // Find positions of clusters in the clusters vector to merge together.
947 [ - + ]: 591999 : auto par_cl = rng.randrange(clusters.size());
948 [ - + ]: 591999 : auto chl_cl = rng.randrange(clusters.size() - 1);
949 : 591999 : chl_cl += (chl_cl >= par_cl);
950 [ + - ]: 591999 : Assume(chl_cl != par_cl);
951 : : // Add between 1 and 3 dependencies between them. As all are in the same
952 : : // direction (from the child cluster to parent cluster), no cycles are possible,
953 : : // regardless of what internal topology Trim() uses as approximation within the
954 : : // clusters.
955 : 591999 : int num_deps = rng.randrange(3) + 1;
956 [ + + ]: 1775662 : for (int i = 0; i < num_deps; ++i) {
957 : : // Find a parent transaction in the parent cluster.
958 : 1183663 : auto par_idx = rng.randrange(clusters[par_cl].Count());
959 : 1183663 : SimTxGraph::Pos par_pos = 0;
960 [ + - ]: 2841125 : for (auto j : clusters[par_cl]) {
961 [ + + ]: 2841125 : if (par_idx == 0) {
962 : : par_pos = j;
963 : : break;
964 : : }
965 : 1657462 : --par_idx;
966 : : }
967 : : // Find a child transaction in the child cluster.
968 : 1183663 : auto chl_idx = rng.randrange(clusters[chl_cl].Count());
969 : 1183663 : SimTxGraph::Pos chl_pos = 0;
970 [ + - ]: 2834771 : for (auto j : clusters[chl_cl]) {
971 [ + + ]: 2834771 : if (chl_idx == 0) {
972 : : chl_pos = j;
973 : : break;
974 : : }
975 : 1651108 : --chl_idx;
976 : : }
977 : : // Add dependency to both simulation and real TxGraph.
978 : 1183663 : auto par_ref = top_sim.GetRef(par_pos);
979 : 1183663 : auto chl_ref = top_sim.GetRef(chl_pos);
980 : 1183663 : top_sim.AddDependency(par_ref, chl_ref);
981 : 1183663 : real->AddDependency(*par_ref, *chl_ref);
982 : : }
983 : : // Compute the combined cluster.
984 : 591999 : auto par_cluster = clusters[par_cl];
985 : 591999 : auto chl_cluster = clusters[chl_cl];
986 : 591999 : auto new_cluster = par_cluster | chl_cluster;
987 : : // Remove the parent and child cluster from clusters.
988 [ + + + + ]: 22780145 : std::erase_if(clusters, [&](const auto& cl) noexcept { return cl == par_cluster || cl == chl_cluster; });
989 : : // Add the combined cluster.
990 [ + - ]: 591999 : clusters.push_back(new_cluster);
991 : : // If this is the first merge that causes an oversized cluster to appear, pick
992 : : // a random number of further merges to appear.
993 [ + + ]: 591999 : if (!made_oversized) {
994 : 518673 : made_oversized = new_cluster.Count() > max_cluster_count;
995 [ + + ]: 518673 : if (!made_oversized) {
996 : 499535 : FeeFrac total;
997 [ + + ]: 3618470 : for (auto i : new_cluster) total += top_sim.graph.FeeRate(i);
998 [ + + ]: 499535 : if (uint32_t(total.size) > max_cluster_size) made_oversized = true;
999 : : }
1000 [ + + - + ]: 518673 : if (made_oversized) merges_left = rng.randrange(clusters.size());
1001 : : }
1002 : : }
1003 : :
1004 : : // Determine an upper bound on how many transactions are removed.
1005 : 19542 : uint32_t max_removed = 0;
1006 [ + + ]: 113163 : for (auto& cluster : clusters) {
1007 : : // Gather all transaction sizes in the to-be-combined cluster.
1008 : 93621 : std::vector<uint32_t> sizes;
1009 [ + - + + ]: 1112111 : for (auto i : cluster) sizes.push_back(top_sim.graph.FeeRate(i).size);
1010 : 93621 : auto sum_sizes = std::accumulate(sizes.begin(), sizes.end(), uint64_t{0});
1011 : : // Sort from large to small.
1012 : 93621 : std::ranges::sort(sizes, std::greater{});
1013 : : // In the worst case, only the smallest transactions are removed.
1014 [ - + + + : 293040 : while (sizes.size() > max_cluster_count || sum_sizes > max_cluster_size) {
+ + ]
1015 : 199419 : sum_sizes -= sizes.back();
1016 : 199419 : sizes.pop_back();
1017 : 199419 : ++max_removed;
1018 : : }
1019 : 93621 : }
1020 : :
1021 : : // Invoke Trim now on the definitely-oversized txgraph.
1022 : 19542 : auto removed = real->Trim();
1023 : : // Verify that the number of removals is within range.
1024 [ - + - + ]: 19542 : assert(removed.size() >= 1);
1025 [ - + ]: 19542 : assert(removed.size() <= max_removed);
1026 : : // The removed set must contain all its own descendants.
1027 : 19542 : auto removed_set = top_sim.MakeSet(removed);
1028 [ + + ]: 149095 : for (auto simpos : removed_set) {
1029 [ - + ]: 259106 : assert(top_sim.graph.Descendants(simpos).IsSubsetOf(removed_set));
1030 : : }
1031 : : // Something from every oversized cluster should have been removed, and nothing
1032 : : // else.
1033 [ + - - + ]: 19542 : assert(top_sim.MatchesOversizedClusters(removed_set));
1034 : :
1035 : : // Apply all removals to the simulation, and verify the result is no longer
1036 : : // oversized. Don't query the real graph for oversizedness; it is compared
1037 : : // against the simulation anyway later.
1038 [ + + ]: 149095 : for (auto simpos : removed_set) {
1039 [ + - ]: 129553 : top_sim.RemoveTransaction(top_sim.GetRef(simpos));
1040 : : }
1041 [ + - - + ]: 19542 : assert(!top_sim.IsOversized());
1042 : 19542 : break;
1043 [ + + ]: 248114 : } else if (command-- == 0) {
1044 : : // GetMainMemoryUsage().
1045 : 7261 : auto usage = real->GetMainMemoryUsage();
1046 : : // Test stability.
1047 [ + + ]: 7261 : if (alt) {
1048 : 3177 : auto usage2 = real->GetMainMemoryUsage();
1049 [ - + ]: 3177 : assert(usage == usage2);
1050 : : }
1051 : : // Only empty graphs have 0 memory usage.
1052 [ + + ]: 7261 : if (main_sim.GetTransactionCount() == 0) {
1053 [ - + ]: 1016 : assert(usage == 0);
1054 : : } else {
1055 [ - + ]: 6245 : assert(usage > 0);
1056 : : }
1057 : : break;
1058 : : }
1059 : : }
1060 : : }
1061 : :
1062 : : // After running all modifications, perform an internal sanity check (before invoking
1063 : : // inspectors that may modify the internal state).
1064 [ + - ]: 3590 : real->SanityCheck();
1065 : :
1066 [ + - + + ]: 3590 : if (!sims[0].IsOversized()) {
1067 : : // If the main graph is not oversized, verify the total ordering implied by
1068 : : // CompareMainOrder.
1069 : : // First construct two distinct randomized permutations of the positions in sims[0].
1070 : 2941 : std::vector<SimTxGraph::Pos> vec1;
1071 [ + - + + ]: 120915 : for (auto i : sims[0].graph.Positions()) vec1.push_back(i);
1072 : 2941 : std::shuffle(vec1.begin(), vec1.end(), rng);
1073 [ + - ]: 2941 : auto vec2 = vec1;
1074 : 2941 : std::shuffle(vec2.begin(), vec2.end(), rng);
1075 [ + + ]: 2941 : if (vec1 == vec2) std::next_permutation(vec2.begin(), vec2.end());
1076 : : // Sort both according to CompareMainOrder. By having randomized starting points, the order
1077 : : // of CompareMainOrder invocations is somewhat randomized as well.
1078 : 1706766 : auto cmp = [&](SimTxGraph::Pos a, SimTxGraph::Pos b) noexcept {
1079 : 1703825 : return real->CompareMainOrder(*sims[0].GetRef(a), *sims[0].GetRef(b)) < 0;
1080 : 2941 : };
1081 : 2941 : std::ranges::sort(vec1, cmp);
1082 : 2941 : std::ranges::sort(vec2, cmp);
1083 : :
1084 : : // Verify the resulting orderings are identical. This could only fail if the ordering was
1085 : : // not total.
1086 [ - + ]: 2941 : assert(vec1 == vec2);
1087 : :
1088 : : // Verify that the ordering is topological.
1089 : 2941 : auto todo = sims[0].graph.Positions();
1090 [ + + ]: 120915 : for (auto i : vec1) {
1091 : 117974 : todo.Reset(i);
1092 [ - + ]: 235948 : assert(!sims[0].graph.Ancestors(i).Overlaps(todo));
1093 : : }
1094 [ - + ]: 2941 : assert(todo.None());
1095 : :
1096 : : // If the real graph claims to be optimal (the last DoWork() call returned true), verify
1097 : : // that calling Linearize on it does not improve it further.
1098 [ + + ]: 2941 : if (sims[0].real_is_optimal) {
1099 [ - + ]: 559 : auto real_diagram = ChunkLinearization(sims[0].graph, vec1);
1100 : 93013 : auto fallback_order_sim = [&](DepGraphIndex a, DepGraphIndex b) noexcept {
1101 : 92454 : auto txid_a = sims[0].GetRef(a)->m_txid;
1102 : 92454 : auto txid_b = sims[0].GetRef(b)->m_txid;
1103 [ + - + + ]: 92454 : return txid_a <=> txid_b;
1104 : 559 : };
1105 [ - + - + ]: 559 : auto [sim_lin, sim_optimal, _cost] = Linearize(sims[0].graph, 300000, rng.rand64(), fallback_order_sim, vec1);
1106 [ - + + - ]: 559 : PostLinearize(sims[0].graph, sim_lin);
1107 [ - + ]: 559 : auto sim_diagram = ChunkLinearization(sims[0].graph, sim_lin);
1108 [ - + - + : 559 : auto cmp = CompareChunks(real_diagram, sim_diagram);
+ - ]
1109 [ - + ]: 559 : assert(cmp == 0);
1110 : :
1111 : : // Verify consistency of cross-cluster chunk ordering with tie-break (equal-feerate
1112 : : // prefix size).
1113 [ - + ]: 559 : auto real_chunking = ChunkLinearizationInfo(sims[0].graph, vec1);
1114 : : /** Map with one entry per component of the sim main graph. Key is the first Pos of the
1115 : : * component. Value is the sum of all chunk sizes from that component seen
1116 : : * already, at the current chunk feerate. */
1117 : 559 : std::map<SimTxGraph::Pos, int32_t> comp_prefix_sizes;
1118 : : /** Current chunk feerate. */
1119 : 559 : FeeFrac last_chunk_feerate;
1120 : : /** Largest seen (equal-feerate chunk prefix size, max txid). */
1121 : 559 : std::pair<int32_t, uint64_t> max_chunk_tiebreak{0, 0};
1122 [ + + ]: 26494 : for (const auto& chunk : real_chunking) {
1123 : : // If this is the first chunk with a strictly lower feerate, reset.
1124 [ + + ]: 25935 : if (ByRatio{chunk.feerate} < ByRatio{last_chunk_feerate}) {
1125 : 6169 : comp_prefix_sizes.clear();
1126 : 6169 : max_chunk_tiebreak = {0, 0};
1127 : : }
1128 : 25935 : last_chunk_feerate = chunk.feerate;
1129 : : // Find which sim component this chunk belongs to.
1130 : 25935 : auto component = sims[0].graph.GetConnectedComponent(sims[0].graph.Positions(), chunk.transactions.First());
1131 [ - + ]: 51870 : assert(chunk.transactions.IsSubsetOf(component));
1132 : 25935 : auto comp_key = component.First();
1133 [ + - ]: 25935 : auto& comp_prefix_size = comp_prefix_sizes[comp_key];
1134 : 25935 : comp_prefix_size += chunk.feerate.size;
1135 : : // Determine the chunk's max txid.
1136 : 25935 : uint64_t chunk_max_txid{0};
1137 [ + + ]: 57232 : for (auto tx : chunk.transactions) {
1138 : 31297 : auto txid = sims[0].GetRef(tx)->m_txid;
1139 [ + + ]: 58611 : chunk_max_txid = std::max(txid, chunk_max_txid);
1140 : : }
1141 : : // Verify consistency: within each group of equal-feerate chunks, the
1142 : : // (equal-feerate chunk prefix size, max txid) must be increasing.
1143 [ - + ]: 25935 : std::pair<int32_t, uint64_t> chunk_tiebreak{comp_prefix_size, chunk_max_txid};
1144 [ - + ]: 25935 : assert(chunk_tiebreak > max_chunk_tiebreak);
1145 : 25935 : max_chunk_tiebreak = chunk_tiebreak;
1146 : : }
1147 : :
1148 : : // Verify that within each cluster, the internal ordering matches that of the
1149 : : // simulation if that is optimal too, since per-cluster optimal orderings are
1150 : : // deterministic. Note that both have been PostLinearize()'ed.
1151 [ + - ]: 559 : if (sim_optimal) {
1152 [ + - + + ]: 17842 : for (const auto& component : sims[0].GetComponents()) {
1153 : 17283 : std::vector<DepGraphIndex> sim_chunk_lin, real_chunk_lin;
1154 [ + + ]: 1598294 : for (auto i : sim_lin) {
1155 [ + + + - ]: 1581011 : if (component[i]) sim_chunk_lin.push_back(i);
1156 : : }
1157 [ + + ]: 1598294 : for (auto i : vec1) {
1158 [ + + + - ]: 1581011 : if (component[i]) real_chunk_lin.push_back(i);
1159 : : }
1160 [ - + ]: 17283 : assert(sim_chunk_lin == real_chunk_lin);
1161 : 17842 : }
1162 : : }
1163 : :
1164 : : // Verify that a fresh TxGraph, with the same transactions and txids, but constructed
1165 : : // in a different order, and with a different RNG state, recreates the exact same
1166 : : // ordering, showing that for optimal graphs, the full mempool ordering is
1167 : : // deterministic.
1168 : 559 : auto real_redo = MakeTxGraph(
1169 : : /*max_cluster_count=*/max_cluster_count,
1170 : : /*max_cluster_size=*/max_cluster_size,
1171 : : /*acceptable_cost=*/acceptable_cost,
1172 : 559 : /*fallback_order=*/fallback_order);
1173 : : /** Vector (indexed by SimTxGraph::Pos) of TxObjects in real_redo). */
1174 : 559 : std::vector<std::optional<SimTxObject>> txobjects_redo;
1175 [ - + + - ]: 559 : txobjects_redo.resize(sims[0].graph.PositionRange());
1176 : : // Recreate the graph's transactions with same feerate and txid.
1177 : 559 : std::vector<DepGraphIndex> positions;
1178 [ + - + + ]: 31856 : for (auto i : sims[0].graph.Positions()) positions.push_back(i);
1179 : 559 : std::shuffle(positions.begin(), positions.end(), rng);
1180 [ + + ]: 31856 : for (auto i : positions) {
1181 : 31297 : txobjects_redo[i].emplace(sims[0].GetRef(i)->m_txid);
1182 : 31297 : real_redo->AddTransaction(*txobjects_redo[i], FeePerWeight::FromFeeFrac(sims[0].graph.FeeRate(i)));
1183 : : }
1184 : : // Recreate the graph's dependencies.
1185 : 559 : std::vector<std::pair<DepGraphIndex, DepGraphIndex>> deps;
1186 [ + + ]: 31856 : for (auto i : sims[0].graph.Positions()) {
1187 [ + + ]: 46916 : for (auto j : sims[0].graph.GetReducedParents(i)) {
1188 [ + - ]: 15619 : deps.emplace_back(j, i);
1189 : : }
1190 : : }
1191 : 559 : std::shuffle(deps.begin(), deps.end(), rng);
1192 [ + + ]: 16178 : for (auto [parent, child] : deps) {
1193 : 15619 : real_redo->AddDependency(*txobjects_redo[parent], *txobjects_redo[child]);
1194 : : }
1195 : : // Do work to reach optimality.
1196 [ + - ]: 559 : if (real_redo->DoWork(300000)) {
1197 : : // Start from a random permutation.
1198 [ + - ]: 559 : auto vec_redo = vec1;
1199 : 559 : std::shuffle(vec_redo.begin(), vec_redo.end(), rng);
1200 [ + + ]: 559 : if (vec_redo == vec1) std::next_permutation(vec_redo.begin(), vec_redo.end());
1201 : : // Sort it according to the main graph order in real_redo.
1202 : 242259 : auto cmp_redo = [&](SimTxGraph::Pos a, SimTxGraph::Pos b) noexcept {
1203 : 241700 : return real_redo->CompareMainOrder(*txobjects_redo[a], *txobjects_redo[b]) < 0;
1204 : 559 : };
1205 : 559 : std::ranges::sort(vec_redo, cmp_redo);
1206 : : // Compare with the ordering we got from real.
1207 [ - + ]: 559 : assert(vec1 == vec_redo);
1208 : 559 : }
1209 : 559 : }
1210 : :
1211 : : // For every transaction in the total ordering, find a random one before it and after it,
1212 : : // and compare their chunk feerates, which must be consistent with the ordering.
1213 [ - + + + ]: 120915 : for (size_t pos = 0; pos < vec1.size(); ++pos) {
1214 : 117974 : auto pos_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[pos]));
1215 [ + + ]: 117974 : if (pos > 0) {
1216 : 115322 : size_t before = rng.randrange<size_t>(pos);
1217 : 115322 : auto before_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[before]));
1218 [ - + ]: 115322 : assert(ByRatio{before_feerate} >= ByRatio{pos_feerate});
1219 : : }
1220 [ - + + + ]: 117974 : if (pos + 1 < vec1.size()) {
1221 : 115322 : size_t after = pos + 1 + rng.randrange<size_t>(vec1.size() - 1 - pos);
1222 : 115322 : auto after_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[after]));
1223 [ - + ]: 115322 : assert(ByRatio{after_feerate} <= ByRatio{pos_feerate});
1224 : : }
1225 : : }
1226 : :
1227 : : // The same order should be obtained through a BlockBuilder as implied by CompareMainOrder,
1228 : : // if nothing is skipped.
1229 : 2941 : auto builder = real->GetBlockBuilder();
1230 : 2941 : std::vector<SimTxGraph::Pos> vec_builder;
1231 : 2941 : std::vector<TxGraph::Ref*> last_chunk;
1232 : 2941 : FeePerWeight last_chunk_feerate;
1233 [ + + ]: 205719 : while (auto chunk = builder->GetCurrentChunk()) {
1234 : 101389 : FeePerWeight sum;
1235 [ + + ]: 219363 : for (TxGraph::Ref* ref : chunk->first) {
1236 : : // The reported chunk feerate must match the chunk feerate obtained by asking
1237 : : // it for each of the chunk's transactions individually.
1238 [ + - ]: 117974 : assert(real->GetMainChunkFeerate(*ref) == chunk->second);
1239 : : // Verify the chunk feerate matches the sum of the reported individual feerates.
1240 : 117974 : sum += real->GetIndividualFeerate(*ref);
1241 : : // Chunks must contain transactions that exist in the graph.
1242 : 117974 : auto simpos = sims[0].Find(ref);
1243 [ - + ]: 117974 : assert(simpos != SimTxGraph::MISSING);
1244 [ + - ]: 117974 : vec_builder.push_back(simpos);
1245 : : }
1246 [ + - ]: 101389 : assert(sum == chunk->second);
1247 : 101389 : last_chunk = std::move(chunk->first);
1248 : 101389 : last_chunk_feerate = chunk->second;
1249 : 101389 : builder->Include();
1250 : 101389 : }
1251 [ - + ]: 2941 : assert(vec_builder == vec1);
1252 : :
1253 : : // The last chunk returned by the BlockBuilder must match GetWorstMainChunk, in reverse.
1254 : 2941 : std::reverse(last_chunk.begin(), last_chunk.end());
1255 [ - + ]: 2941 : auto [worst_chunk, worst_chunk_feerate] = real->GetWorstMainChunk();
1256 [ - + ]: 2941 : assert(last_chunk == worst_chunk);
1257 [ + - ]: 2941 : assert(last_chunk_feerate == worst_chunk_feerate);
1258 : :
1259 : : // Check that the implied ordering gives rise to a combined diagram that matches the
1260 : : // diagram constructed from the individual cluster linearization chunkings.
1261 [ + - ]: 2941 : auto main_real_diagram = get_diagram_fn(TxGraph::Level::MAIN);
1262 [ - + ]: 2941 : auto main_implied_diagram = ChunkLinearization(sims[0].graph, vec1);
1263 [ - + - + : 2941 : assert(CompareChunks(main_real_diagram, main_implied_diagram) == 0);
+ - - + ]
1264 : :
1265 [ - + + + : 2941 : if (sims.size() >= 2 && !sims[1].IsOversized()) {
+ - + + ]
1266 : : // When the staging graph is not oversized as well, call GetMainStagingDiagrams, and
1267 : : // fully verify the result.
1268 : 1450 : auto [main_cmp_diagram, stage_cmp_diagram] = real->GetMainStagingDiagrams();
1269 : : // Check that the feerates in each diagram are monotonically decreasing.
1270 [ - + + + ]: 33644 : for (size_t i = 1; i < main_cmp_diagram.size(); ++i) {
1271 [ - + ]: 32194 : assert(ByRatio{main_cmp_diagram[i]} <= ByRatio{main_cmp_diagram[i - 1]});
1272 : : }
1273 [ - + + + ]: 25303 : for (size_t i = 1; i < stage_cmp_diagram.size(); ++i) {
1274 [ - + ]: 23853 : assert(ByRatio{stage_cmp_diagram[i]} <= ByRatio{stage_cmp_diagram[i - 1]});
1275 : : }
1276 : : // Treat the diagrams as sets of chunk feerates, and sort them in the same way so that
1277 : : // std::set_difference can be used on them below. The exact ordering does not matter
1278 : : // here, but it has to be consistent with the one used in main_real_diagram and
1279 : : // stage_real_diagram).
1280 : 1450 : std::ranges::sort(main_cmp_diagram, std::greater<ByRatioNegSize<FeeFrac>>{});
1281 : 1450 : std::ranges::sort(stage_cmp_diagram, std::greater<ByRatioNegSize<FeeFrac>>{});
1282 : : // Find the chunks that appear in main_diagram but are missing from main_cmp_diagram.
1283 : : // This is allowed, because GetMainStagingDiagrams omits clusters in main unaffected
1284 : : // by staging.
1285 : 1450 : std::vector<FeeFrac> missing_main_cmp;
1286 [ + - ]: 1450 : std::set_difference(main_real_diagram.begin(), main_real_diagram.end(),
1287 : : main_cmp_diagram.begin(), main_cmp_diagram.end(),
1288 : : std::inserter(missing_main_cmp, missing_main_cmp.end()),
1289 : : std::greater<ByRatioNegSize<FeeFrac>>{});
1290 [ - + - + : 1450 : assert(main_cmp_diagram.size() + missing_main_cmp.size() == main_real_diagram.size());
- + - + ]
1291 : : // Do the same for chunks in stage_diagram missing from stage_cmp_diagram.
1292 [ + - ]: 1450 : auto stage_real_diagram = get_diagram_fn(TxGraph::Level::TOP);
1293 : 1450 : std::vector<FeeFrac> missing_stage_cmp;
1294 [ + - ]: 1450 : std::set_difference(stage_real_diagram.begin(), stage_real_diagram.end(),
1295 : : stage_cmp_diagram.begin(), stage_cmp_diagram.end(),
1296 : : std::inserter(missing_stage_cmp, missing_stage_cmp.end()),
1297 : : std::greater<ByRatioNegSize<FeeFrac>>{});
1298 [ - + - + : 1450 : assert(stage_cmp_diagram.size() + missing_stage_cmp.size() == stage_real_diagram.size());
- + - + ]
1299 : : // The missing chunks must be equal across main & staging (otherwise they couldn't have
1300 : : // been omitted).
1301 [ - + ]: 1450 : assert(missing_main_cmp == missing_stage_cmp);
1302 : :
1303 : : // The missing part must include at least all transactions in staging which have not been
1304 : : // modified, or been in a cluster together with modified transactions, since they were
1305 : : // copied from main. Note that due to the reordering of removals w.r.t. dependency
1306 : : // additions, it is possible that the real implementation found more unaffected things.
1307 : 1450 : FeeFrac missing_real;
1308 [ + + ]: 21161 : for (const auto& feerate : missing_main_cmp) missing_real += feerate;
1309 : 1450 : FeeFrac missing_expected = sims[1].graph.FeeRate(sims[1].graph.Positions() - sims[1].modified);
1310 : : // Note that missing_real.fee < missing_expected.fee is possible to due the presence of
1311 : : // negative-fee transactions.
1312 [ - + ]: 1450 : assert(missing_real.size >= missing_expected.size);
1313 : 2900 : }
1314 : 2941 : }
1315 : :
1316 [ - + - + ]: 3590 : assert(real->HaveStaging() == (sims.size() > 1));
1317 : :
1318 : : // Try to run a full comparison, for both TxGraph::Level::MAIN and TxGraph::Level::TOP in
1319 : : // TxGraph inspector functions that support both.
1320 [ + + ]: 10770 : for (auto level : {TxGraph::Level::TOP, TxGraph::Level::MAIN}) {
1321 [ + + ]: 7180 : auto& sim = level == TxGraph::Level::TOP ? sims.back() : sims.front();
1322 : : // Compare simple properties of the graph with the simulation.
1323 [ + - - + ]: 7180 : assert(real->IsOversized(level) == sim.IsOversized());
1324 [ - + ]: 7180 : assert(real->GetTransactionCount(level) == sim.GetTransactionCount());
1325 : : // If the graph (and the simulation) are not oversized, perform a full comparison.
1326 [ + - + + ]: 7180 : if (!sim.IsOversized()) {
1327 : 5948 : auto todo = sim.graph.Positions();
1328 : : // Iterate over all connected components of the resulting (simulated) graph, each of which
1329 : : // should correspond to a cluster in the real one.
1330 [ + + ]: 285734 : while (todo.Any()) {
1331 : 136919 : auto component = sim.graph.FindConnectedComponent(todo);
1332 : 136919 : todo -= component;
1333 : : // Iterate over the transactions in that component.
1334 [ + + ]: 372369 : for (auto i : component) {
1335 : : // Check its individual feerate against simulation.
1336 [ + - ]: 235450 : assert(sim.graph.FeeRate(i) == real->GetIndividualFeerate(*sim.GetRef(i)));
1337 : : // Check its ancestors against simulation.
1338 : 235450 : auto expect_anc = sim.graph.Ancestors(i);
1339 [ - + ]: 235450 : auto anc = sim.MakeSet(real->GetAncestors(*sim.GetRef(i), level));
1340 [ - + ]: 235450 : assert(anc.Count() <= max_cluster_count);
1341 [ - + ]: 235450 : assert(anc == expect_anc);
1342 : : // Check its descendants against simulation.
1343 : 235450 : auto expect_desc = sim.graph.Descendants(i);
1344 [ - + ]: 235450 : auto desc = sim.MakeSet(real->GetDescendants(*sim.GetRef(i), level));
1345 [ - + ]: 235450 : assert(desc.Count() <= max_cluster_count);
1346 [ - + ]: 235450 : assert(desc == expect_desc);
1347 : : // Check the cluster the transaction is part of.
1348 : 235450 : auto cluster = real->GetCluster(*sim.GetRef(i), level);
1349 [ - + - + ]: 235450 : assert(cluster.size() <= max_cluster_count);
1350 [ - + ]: 235450 : assert(sim.MakeSet(cluster) == component);
1351 : : // Check that the cluster is reported in a valid topological order (its
1352 : : // linearization).
1353 : 235450 : std::vector<DepGraphIndex> simlin;
1354 : 235450 : SimTxGraph::SetType done;
1355 : 235450 : uint64_t total_size{0};
1356 [ + + ]: 3785676 : for (TxGraph::Ref* ptr : cluster) {
1357 : 3550226 : auto simpos = sim.Find(ptr);
1358 [ - + ]: 7100452 : assert(sim.graph.Descendants(simpos).IsSubsetOf(component - done));
1359 : 3550226 : done.Set(simpos);
1360 [ - + ]: 7100452 : assert(sim.graph.Ancestors(simpos).IsSubsetOf(done));
1361 [ + - ]: 3550226 : simlin.push_back(simpos);
1362 : 3550226 : total_size += sim.graph.FeeRate(simpos).size;
1363 : : }
1364 : : // Check cluster size.
1365 [ - + ]: 235450 : assert(total_size <= max_cluster_size);
1366 : : // Construct a chunking object for the simulated graph, using the reported cluster
1367 : : // linearization as ordering, and compare it against the reported chunk feerates.
1368 [ - + + + : 235450 : if (sims.size() == 1 || level == TxGraph::Level::MAIN) {
+ + ]
1369 [ - + ]: 175433 : auto simlinchunk = ChunkLinearizationInfo(sim.graph, simlin);
1370 : 175433 : DepGraphIndex idx{0};
1371 [ + + ]: 1469993 : for (auto& chunk : simlinchunk) {
1372 : : // Require that the chunks of cluster linearizations are connected (this must
1373 : : // be the case as all linearizations inside are PostLinearized).
1374 [ - + ]: 1294560 : assert(sim.graph.IsConnected(chunk.transactions));
1375 : : // Check the chunk feerates of all transactions in the cluster.
1376 [ + + ]: 7212070 : while (chunk.transactions.Any()) {
1377 [ - + ]: 2311475 : assert(chunk.transactions[simlin[idx]]);
1378 : 2311475 : chunk.transactions.Reset(simlin[idx]);
1379 [ + - ]: 2311475 : assert(chunk.feerate == real->GetMainChunkFeerate(*cluster[idx]));
1380 : 2311475 : ++idx;
1381 : : }
1382 : : }
1383 : 175433 : }
1384 : 235450 : }
1385 : : }
1386 : : }
1387 : : }
1388 : :
1389 : : // Sanity check again (because invoking inspectors may modify internal unobservable state).
1390 [ + - ]: 3590 : real->SanityCheck();
1391 : :
1392 : : // Kill the block builders.
1393 : 3590 : block_builders.clear();
1394 : : // Kill the TxGraph object.
1395 [ + - ]: 3590 : real.reset();
1396 : : // Kill the simulated graphs, with all remaining Refs in it. If any, this verifies that Refs
1397 : : // can outlive the TxGraph that created them.
1398 : 3590 : sims.clear();
1399 : 3590 : }
|
