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