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