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/random.h>
9 : : #include <txgraph.h>
10 : : #include <util/bitset.h>
11 : : #include <util/feefrac.h>
12 : :
13 : : #include <algorithm>
14 : : #include <cstdint>
15 : : #include <iterator>
16 : : #include <map>
17 : : #include <memory>
18 : : #include <set>
19 : : #include <utility>
20 : :
21 : : using namespace cluster_linearize;
22 : :
23 : : namespace {
24 : :
25 : : /** Data type representing a naive simulated TxGraph, keeping all transactions (even from
26 : : * disconnected components) in a single DepGraph. Unlike the real TxGraph, this only models
27 : : * a single graph, and multiple instances are used to simulate main/staging. */
28 : : struct SimTxGraph
29 : : {
30 : : /** Maximum number of transactions to support simultaneously. Set this higher than txgraph's
31 : : * cluster count, so we can exercise situations with more transactions than fit in one
32 : : * cluster. */
33 : : static constexpr unsigned MAX_TRANSACTIONS = MAX_CLUSTER_COUNT_LIMIT * 2;
34 : : /** Set type to use in the simulation. */
35 : : using SetType = BitSet<MAX_TRANSACTIONS>;
36 : : /** Data type for representing positions within SimTxGraph::graph. */
37 : : using Pos = DepGraphIndex;
38 : : /** Constant to mean "missing in this graph". */
39 : : static constexpr auto MISSING = Pos(-1);
40 : :
41 : : /** The dependency graph (for all transactions in the simulation, regardless of
42 : : * connectivity/clustering). */
43 : : DepGraph<SetType> graph;
44 : : /** For each position in graph, which TxGraph::Ref it corresponds with (if any). Use shared_ptr
45 : : * so that a SimTxGraph can be copied to create a staging one, while sharing Refs with
46 : : * the main graph. */
47 : : std::array<std::shared_ptr<TxGraph::Ref>, MAX_TRANSACTIONS> simmap;
48 : : /** For each TxGraph::Ref in graph, the position it corresponds with. */
49 : : std::map<const TxGraph::Ref*, Pos> simrevmap;
50 : : /** The set of TxGraph::Ref entries that have been removed, but not yet destroyed. */
51 : : std::vector<std::shared_ptr<TxGraph::Ref>> removed;
52 : : /** Whether the graph is oversized (true = yes, false = no, std::nullopt = unknown). */
53 : : std::optional<bool> oversized;
54 : : /** The configured maximum number of transactions per cluster. */
55 : : DepGraphIndex max_cluster_count;
56 : : /** Which transactions have been modified in the graph since creation, either directly or by
57 : : * being in a cluster which includes modifications. Only relevant for the staging graph. */
58 : : SetType modified;
59 : :
60 : : /** Construct a new SimTxGraph with the specified maximum cluster count. */
61 : 3709 : explicit SimTxGraph(DepGraphIndex max_cluster) : max_cluster_count(max_cluster) {}
62 : :
63 : : // Permit copying and moving.
64 [ + - + - ]: 8055 : SimTxGraph(const SimTxGraph&) noexcept = default;
65 : : SimTxGraph& operator=(const SimTxGraph&) noexcept = default;
66 : 0 : SimTxGraph(SimTxGraph&&) noexcept = default;
67 : 3821 : SimTxGraph& operator=(SimTxGraph&&) noexcept = default;
68 : :
69 : : /** Check whether this graph is oversized (contains a connected component whose number of
70 : : * transactions exceeds max_cluster_count. */
71 : 3690483 : bool IsOversized()
72 : : {
73 [ + + ]: 3690483 : if (!oversized.has_value()) {
74 : : // Only recompute when oversized isn't already known.
75 : 38139 : oversized = false;
76 : 38139 : auto todo = graph.Positions();
77 : : // Iterate over all connected components of the graph.
78 [ + + ]: 1486642 : while (todo.Any()) {
79 : 705182 : auto component = graph.FindConnectedComponent(todo);
80 [ + + ]: 705182 : if (component.Count() > max_cluster_count) oversized = true;
81 : 705182 : todo -= component;
82 : : }
83 : : }
84 : 3690483 : return *oversized;
85 : : }
86 : :
87 : 226481 : void MakeModified(DepGraphIndex index)
88 : : {
89 : 226481 : modified |= graph.GetConnectedComponent(graph.Positions(), index);
90 : 226481 : }
91 : :
92 : : /** Determine the number of (non-removed) transactions in the graph. */
93 [ + + + + : 1815021 : DepGraphIndex GetTransactionCount() const { return graph.TxCount(); }
+ + ]
94 : :
95 : : /** Get the sum of all fees/sizes in the graph. */
96 : 32238 : FeePerWeight SumAll() const
97 : : {
98 : 32238 : FeePerWeight ret;
99 [ + + ]: 681750 : for (auto i : graph.Positions()) {
100 : 649512 : ret += graph.FeeRate(i);
101 : : }
102 : 32238 : return ret;
103 : : }
104 : :
105 : : /** Get the position where ref occurs in this simulated graph, or -1 if it does not. */
106 : 2231605 : Pos Find(const TxGraph::Ref* ref) const
107 : : {
108 : 2231605 : auto it = simrevmap.find(ref);
109 [ + + ]: 2231605 : if (it != simrevmap.end()) return it->second;
110 : : return MISSING;
111 : : }
112 : :
113 : : /** Given a position in this simulated graph, get the corresponding TxGraph::Ref. */
114 : 2426586 : TxGraph::Ref* GetRef(Pos pos)
115 : : {
116 [ - + ]: 2426586 : assert(graph.Positions()[pos]);
117 [ - + ]: 2426586 : assert(simmap[pos]);
118 : 2426586 : return simmap[pos].get();
119 : : }
120 : :
121 : : /** Add a new transaction to the simulation. */
122 : 144831 : TxGraph::Ref* AddTransaction(const FeePerWeight& feerate)
123 : : {
124 [ - + ]: 144831 : assert(graph.TxCount() < MAX_TRANSACTIONS);
125 : 144831 : auto simpos = graph.AddTransaction(feerate);
126 : 144831 : MakeModified(simpos);
127 [ - + ]: 144831 : assert(graph.Positions()[simpos]);
128 [ - + ]: 144831 : simmap[simpos] = std::make_shared<TxGraph::Ref>();
129 : 144831 : auto ptr = simmap[simpos].get();
130 : 144831 : simrevmap[ptr] = simpos;
131 : 144831 : return ptr;
132 : : }
133 : :
134 : : /** Add a dependency between two positions in this graph. */
135 : 57423 : void AddDependency(TxGraph::Ref* parent, TxGraph::Ref* child)
136 : : {
137 : 57423 : auto par_pos = Find(parent);
138 [ + + ]: 57423 : if (par_pos == MISSING) return;
139 : 50614 : auto chl_pos = Find(child);
140 [ + + ]: 50614 : if (chl_pos == MISSING) return;
141 : 45324 : graph.AddDependencies(SetType::Singleton(par_pos), chl_pos);
142 : 45324 : MakeModified(par_pos);
143 : : // This may invalidate our cached oversized value.
144 [ + + + + ]: 45324 : if (oversized.has_value() && !*oversized) oversized = std::nullopt;
145 : : }
146 : :
147 : : /** Modify the transaction fee of a ref, if it exists. */
148 : 10707 : void SetTransactionFee(TxGraph::Ref* ref, int64_t fee)
149 : : {
150 : 10707 : auto pos = Find(ref);
151 [ + + ]: 10707 : if (pos == MISSING) return;
152 : : // No need to invoke MakeModified, because this equally affects main and staging.
153 : 8722 : graph.FeeRate(pos).fee = fee;
154 : : }
155 : :
156 : : /** Remove the transaction in the specified position from the graph. */
157 : 23651 : void RemoveTransaction(TxGraph::Ref* ref)
158 : : {
159 : 23651 : auto pos = Find(ref);
160 [ + + ]: 23651 : if (pos == MISSING) return;
161 : 15848 : MakeModified(pos);
162 : 15848 : graph.RemoveTransactions(SetType::Singleton(pos));
163 : 15848 : simrevmap.erase(simmap[pos].get());
164 : : // Retain the TxGraph::Ref corresponding to this position, so the Ref destruction isn't
165 : : // invoked until the simulation explicitly decided to do so.
166 : 15848 : removed.push_back(std::move(simmap[pos]));
167 : 15848 : simmap[pos].reset();
168 : : // This may invalidate our cached oversized value.
169 [ + + + + ]: 15848 : if (oversized.has_value() && *oversized) oversized = std::nullopt;
170 : : }
171 : :
172 : : /** Destroy the transaction from the graph, including from the removed set. This will
173 : : * trigger TxGraph::Ref::~Ref. reset_oversize controls whether the cached oversized
174 : : * value is cleared (destroying does not clear oversizedness in TxGraph of the main
175 : : * graph while staging exists). */
176 : 26970 : void DestroyTransaction(TxGraph::Ref* ref, bool reset_oversize)
177 : : {
178 : 26970 : auto pos = Find(ref);
179 [ + + ]: 26970 : if (pos == MISSING) {
180 : : // Wipe the ref, if it exists, from the removed vector. Use std::partition rather
181 : : // than std::erase because we don't care about the order of the entries that
182 : : // remain.
183 [ + + - + ]: 23079 : auto remove = std::partition(removed.begin(), removed.end(), [&](auto& arg) { return arg.get() != ref; });
184 : 6492 : removed.erase(remove, removed.end());
185 : : } else {
186 : 20478 : MakeModified(pos);
187 : 20478 : graph.RemoveTransactions(SetType::Singleton(pos));
188 : 20478 : simrevmap.erase(simmap[pos].get());
189 : 20478 : simmap[pos].reset();
190 : : // This may invalidate our cached oversized value.
191 [ + + + + : 20478 : if (reset_oversize && oversized.has_value() && *oversized) {
+ + ]
192 : 4119 : oversized = std::nullopt;
193 : : }
194 : : }
195 : 26970 : }
196 : :
197 : : /** Construct the set with all positions in this graph corresponding to the specified
198 : : * TxGraph::Refs. All of them must occur in this graph and not be removed. */
199 : 395470 : SetType MakeSet(std::span<TxGraph::Ref* const> arg)
200 : : {
201 : 395470 : SetType ret;
202 [ + + ]: 1249844 : for (TxGraph::Ref* ptr : arg) {
203 : 854374 : auto pos = Find(ptr);
204 [ - + ]: 854374 : assert(pos != Pos(-1));
205 : 854374 : ret.Set(pos);
206 : : }
207 : 395470 : return ret;
208 : : }
209 : :
210 : : /** Get the set of ancestors (desc=false) or descendants (desc=true) in this graph. */
211 : 56987 : SetType GetAncDesc(TxGraph::Ref* arg, bool desc)
212 : : {
213 : 56987 : auto pos = Find(arg);
214 [ + + ]: 56987 : if (pos == MISSING) return {};
215 [ + + ]: 38381 : return desc ? graph.Descendants(pos) : graph.Ancestors(pos);
216 : : }
217 : :
218 : : /** Given a set of Refs (given as a vector of pointers), expand the set to include all its
219 : : * ancestors (desc=false) or all its descendants (desc=true) in this graph. */
220 : 43553 : void IncludeAncDesc(std::vector<TxGraph::Ref*>& arg, bool desc)
221 : : {
222 : 43553 : std::vector<TxGraph::Ref*> ret;
223 [ + + ]: 93473 : for (auto ptr : arg) {
224 : 49920 : auto simpos = Find(ptr);
225 [ + + ]: 49920 : if (simpos != MISSING) {
226 [ + + + + ]: 87825 : for (auto i : desc ? graph.Descendants(simpos) : graph.Ancestors(simpos)) {
227 [ + - ]: 52435 : ret.push_back(simmap[i].get());
228 : : }
229 : : } else {
230 [ + - ]: 14530 : ret.push_back(ptr);
231 : : }
232 : : }
233 : : // Construct deduplicated version in input (do not use std::sort/std::unique for
234 : : // deduplication as it'd rely on non-deterministic pointer comparison).
235 [ + - ]: 43553 : arg.clear();
236 [ + + ]: 110518 : for (auto ptr : ret) {
237 [ + + ]: 66965 : if (std::find(arg.begin(), arg.end(), ptr) == arg.end()) {
238 [ + - ]: 57853 : arg.push_back(ptr);
239 : : }
240 : : }
241 : 43553 : }
242 : : };
243 : :
244 : : } // namespace
245 : :
246 [ + - ]: 4155 : FUZZ_TARGET(txgraph)
247 : : {
248 : : // This is a big simulation test for TxGraph, which performs a fuzz-derived sequence of valid
249 : : // operations on a TxGraph instance, as well as on a simpler (mostly) reimplementation (see
250 : : // SimTxGraph above), comparing the outcome of functions that return a result, and finally
251 : : // performing a full comparison between the two.
252 : :
253 : 3709 : SeedRandomStateForTest(SeedRand::ZEROS);
254 : 3709 : FuzzedDataProvider provider(buffer.data(), buffer.size());
255 : :
256 : : /** Internal test RNG, used only for decisions which would require significant amount of data
257 : : * to be read from the provider, without realistically impacting test sensitivity. */
258 : 3709 : InsecureRandomContext rng(0xdecade2009added + buffer.size());
259 : :
260 : : /** Variable used whenever an empty TxGraph::Ref is needed. */
261 : 3709 : TxGraph::Ref empty_ref;
262 : :
263 : : // Decide the maximum number of transactions per cluster we will use in this simulation.
264 : 3709 : auto max_count = provider.ConsumeIntegralInRange<DepGraphIndex>(1, MAX_CLUSTER_COUNT_LIMIT);
265 : :
266 : : // Construct a real graph, and a vector of simulated graphs (main, and possibly staging).
267 : 3709 : auto real = MakeTxGraph(max_count);
268 : 3709 : std::vector<SimTxGraph> sims;
269 [ + - ]: 3709 : sims.reserve(2);
270 [ + - ]: 3709 : sims.emplace_back(max_count);
271 : :
272 : : /** Struct encapsulating information about a BlockBuilder that's currently live. */
273 : 11995 : struct BlockBuilderData
274 : : {
275 : : /** BlockBuilder object from real. */
276 : : std::unique_ptr<TxGraph::BlockBuilder> builder;
277 : : /** The set of transactions marked as included in *builder. */
278 : : SimTxGraph::SetType included;
279 : : /** The set of transactions marked as included or skipped in *builder. */
280 : : SimTxGraph::SetType done;
281 : : /** The last chunk feerate returned by *builder. IsEmpty() if none yet. */
282 : : FeePerWeight last_feerate;
283 : :
284 : 4783 : BlockBuilderData(std::unique_ptr<TxGraph::BlockBuilder> builder_in) : builder(std::move(builder_in)) {}
285 : : };
286 : :
287 : : /** Currently active block builders. */
288 : 3709 : std::vector<BlockBuilderData> block_builders;
289 : :
290 : : /** Function to pick any Ref (for either sim in sims: from sim.simmap or sim.removed, or the
291 : : * empty Ref). */
292 : 552749 : auto pick_fn = [&]() noexcept -> TxGraph::Ref* {
293 [ + + ]: 549040 : size_t tx_count[2] = {sims[0].GetTransactionCount(), 0};
294 : : /** The number of possible choices. */
295 [ + + ]: 549040 : size_t choices = tx_count[0] + sims[0].removed.size() + 1;
296 [ + + ]: 549040 : if (sims.size() == 2) {
297 : 202011 : tx_count[1] = sims[1].GetTransactionCount();
298 : 202011 : choices += tx_count[1] + sims[1].removed.size();
299 : : }
300 : : /** Pick one of them. */
301 : 549040 : auto choice = provider.ConsumeIntegralInRange<size_t>(0, choices - 1);
302 : : // Consider both main and (if it exists) staging.
303 [ + + ]: 789288 : for (size_t level = 0; level < sims.size(); ++level) {
304 [ + + ]: 660033 : auto& sim = sims[level];
305 [ + + ]: 660033 : if (choice < tx_count[level]) {
306 : : // Return from graph.
307 [ + - ]: 2916982 : for (auto i : sim.graph.Positions()) {
308 [ + + ]: 2916982 : if (choice == 0) return sim.GetRef(i);
309 : 2517655 : --choice;
310 : : }
311 : 0 : assert(false);
312 : : } else {
313 : 260706 : choice -= tx_count[level];
314 : : }
315 [ + + ]: 260706 : if (choice < sim.removed.size()) {
316 : : // Return from removed.
317 : 20458 : return sim.removed[choice].get();
318 : : } else {
319 : 240248 : choice -= sim.removed.size();
320 : : }
321 : : }
322 : : // Return empty.
323 [ - + ]: 129255 : assert(choice == 0);
324 : 129255 : return &empty_ref;
325 : 3709 : };
326 : :
327 : : /** Function to construct the correct fee-size diagram a real graph has based on its graph
328 : : * order (as reported by GetCluster(), so it works for both main and staging). */
329 : 8427 : auto get_diagram_fn = [&](bool main_only) -> std::vector<FeeFrac> {
330 [ + + ]: 4718 : int level = main_only ? 0 : sims.size() - 1;
331 : 4718 : auto& sim = sims[level];
332 : : // For every transaction in the graph, request its cluster, and throw them into a set.
333 : 4718 : std::set<std::vector<TxGraph::Ref*>> clusters;
334 [ + + ]: 99555 : for (auto i : sim.graph.Positions()) {
335 : 94837 : auto ref = sim.GetRef(i);
336 [ + - ]: 189674 : clusters.insert(real->GetCluster(*ref, main_only));
337 : : }
338 : : // Compute the chunkings of each (deduplicated) cluster.
339 : 4718 : size_t num_tx{0};
340 : 4718 : std::vector<FeeFrac> chunk_feerates;
341 [ + + ]: 83245 : for (const auto& cluster : clusters) {
342 [ + - ]: 78527 : num_tx += cluster.size();
343 : 78527 : std::vector<SimTxGraph::Pos> linearization;
344 [ + - ]: 78527 : linearization.reserve(cluster.size());
345 [ + - + + ]: 173364 : for (auto refptr : cluster) linearization.push_back(sim.Find(refptr));
346 [ + + ]: 166476 : for (const FeeFrac& chunk_feerate : ChunkLinearization(sim.graph, linearization)) {
347 [ + - ]: 87949 : chunk_feerates.push_back(chunk_feerate);
348 : 78527 : }
349 : 78527 : }
350 : : // Verify the number of transactions after deduplicating clusters. This implicitly verifies
351 : : // that GetCluster on each element of a cluster reports the cluster transactions in the same
352 : : // order.
353 [ - + ]: 4718 : assert(num_tx == sim.GetTransactionCount());
354 : : // Sort by feerate only, since violating topological constraints within same-feerate
355 : : // chunks won't affect diagram comparisons.
356 : 4718 : std::sort(chunk_feerates.begin(), chunk_feerates.end(), std::greater{});
357 : 4718 : return chunk_feerates;
358 : 8427 : };
359 : :
360 [ + + + + ]: 510638 : LIMITED_WHILE(provider.remaining_bytes() > 0, 200) {
361 : : // Read a one-byte command.
362 : 506929 : int command = provider.ConsumeIntegral<uint8_t>();
363 : 506929 : int orig_command = command;
364 : :
365 : : // Treat the lowest bit of a command as a flag (which selects a variant of some of the
366 : : // operations), and the second-lowest bit as a way of selecting main vs. staging, and leave
367 : : // the rest of the bits in command.
368 : 506929 : bool alt = command & 1;
369 : 506929 : bool use_main = command & 2;
370 : 506929 : command >>= 2;
371 : :
372 : : /** Use the bottom 2 bits of command to select an entry in the block_builders vector (if
373 : : * any). These use the same bits as alt/use_main, so don't use those in actions below
374 : : * where builder_idx is used as well. */
375 [ + + ]: 506929 : int builder_idx = block_builders.empty() ? -1 : int((orig_command & 3) % block_builders.size());
376 : :
377 : : // Provide convenient aliases for the top simulated graph (main, or staging if it exists),
378 : : // one for the simulated graph selected based on use_main (for operations that can operate
379 : : // on both graphs), and one that always refers to the main graph.
380 : 506929 : auto& top_sim = sims.back();
381 [ + + ]: 506929 : auto& sel_sim = use_main ? sims[0] : top_sim;
382 : 506929 : auto& main_sim = sims[0];
383 : :
384 : : // Keep decrementing command for each applicable operation, until one is hit. Multiple
385 : : // iterations may be necessary.
386 : 840234 : while (true) {
387 [ + + + + : 840234 : if ((block_builders.empty() || sims.size() > 1) && top_sim.GetTransactionCount() < SimTxGraph::MAX_TRANSACTIONS && command-- == 0) {
+ + + + ]
388 : : // AddTransaction.
389 : 144831 : int64_t fee;
390 : 144831 : int32_t size;
391 [ + + ]: 144831 : if (alt) {
392 : : // If alt is true, pick fee and size from the entire range.
393 : 9179 : fee = provider.ConsumeIntegralInRange<int64_t>(-0x8000000000000, 0x7ffffffffffff);
394 : 9179 : size = provider.ConsumeIntegralInRange<int32_t>(1, 0x3fffff);
395 : : } else {
396 : : // Otherwise, use smaller range which consume fewer fuzz input bytes, as just
397 : : // these are likely sufficient to trigger all interesting code paths already.
398 : 135652 : fee = provider.ConsumeIntegral<uint8_t>();
399 : 135652 : size = provider.ConsumeIntegral<uint8_t>() + 1;
400 : : }
401 : 144831 : FeePerWeight feerate{fee, size};
402 : : // Create a real TxGraph::Ref.
403 : 144831 : auto ref = real->AddTransaction(feerate);
404 : : // Create a shared_ptr place in the simulation to put the Ref in.
405 [ + - ]: 144831 : auto ref_loc = top_sim.AddTransaction(feerate);
406 : : // Move it in place.
407 : 144831 : *ref_loc = std::move(ref);
408 : 144831 : break;
409 [ + + + + : 840234 : } else if ((block_builders.empty() || sims.size() > 1) && top_sim.GetTransactionCount() + top_sim.removed.size() > 1 && command-- == 0) {
+ + + + ]
410 : : // AddDependency.
411 : 69401 : auto par = pick_fn();
412 : 69401 : auto chl = pick_fn();
413 : 69401 : auto pos_par = top_sim.Find(par);
414 : 69401 : auto pos_chl = top_sim.Find(chl);
415 [ + + ]: 69401 : if (pos_par != SimTxGraph::MISSING && pos_chl != SimTxGraph::MISSING) {
416 : : // Determine if adding this would introduce a cycle (not allowed by TxGraph),
417 : : // and if so, skip.
418 [ + + ]: 57302 : if (top_sim.graph.Ancestors(pos_par)[pos_chl]) break;
419 : : }
420 : 57423 : top_sim.AddDependency(par, chl);
421 : 57423 : real->AddDependency(*par, *chl);
422 : 57423 : break;
423 [ + + + + : 626002 : } else if ((block_builders.empty() || sims.size() > 1) && top_sim.removed.size() < 100 && command-- == 0) {
+ - + + ]
424 : : // RemoveTransaction. Either all its ancestors or all its descendants are also
425 : : // removed (if any), to make sure TxGraph's reordering of removals and dependencies
426 : : // has no effect.
427 : 20027 : std::vector<TxGraph::Ref*> to_remove;
428 [ + - ]: 20027 : to_remove.push_back(pick_fn());
429 [ + - ]: 20027 : top_sim.IncludeAncDesc(to_remove, alt);
430 : : // The order in which these ancestors/descendants are removed should not matter;
431 : : // randomly shuffle them.
432 : 20027 : std::shuffle(to_remove.begin(), to_remove.end(), rng);
433 [ + + ]: 43678 : for (TxGraph::Ref* ptr : to_remove) {
434 : 23651 : real->RemoveTransaction(*ptr);
435 [ + - ]: 23651 : top_sim.RemoveTransaction(ptr);
436 : : }
437 : 20027 : break;
438 [ + + + + ]: 626002 : } else if (sel_sim.removed.size() > 0 && command-- == 0) {
439 : : // ~Ref (of an already-removed transaction). Destroying a TxGraph::Ref has an
440 : : // observable effect on the TxGraph it refers to, so this simulation permits doing
441 : : // so separately from other actions on TxGraph.
442 : :
443 : : // Pick a Ref of sel_sim.removed to destroy. Note that the same Ref may still occur
444 : : // in the other graph, and thus not actually trigger ~Ref yet (which is exactly
445 : : // what we want, as destroying Refs is only allowed when it does not refer to an
446 : : // existing transaction in either graph).
447 : 2979 : auto removed_pos = provider.ConsumeIntegralInRange<size_t>(0, sel_sim.removed.size() - 1);
448 [ + + ]: 2979 : if (removed_pos != sel_sim.removed.size() - 1) {
449 : 1100 : std::swap(sel_sim.removed[removed_pos], sel_sim.removed.back());
450 : : }
451 : 2979 : sel_sim.removed.pop_back();
452 : 2979 : break;
453 [ + + + + ]: 602996 : } else if (block_builders.empty() && command-- == 0) {
454 : : // ~Ref (of any transaction).
455 : 16814 : std::vector<TxGraph::Ref*> to_destroy;
456 [ + - ]: 16814 : to_destroy.push_back(pick_fn());
457 : 18508 : while (true) {
458 : : // Keep adding either the ancestors or descendants the already picked
459 : : // transactions have in both graphs (main and staging) combined. Destroying
460 : : // will trigger deletions in both, so to have consistent TxGraph behavior, the
461 : : // set must be closed under ancestors, or descendants, in both graphs.
462 : 18508 : auto old_size = to_destroy.size();
463 [ + - + + ]: 42034 : for (auto& sim : sims) sim.IncludeAncDesc(to_destroy, alt);
464 [ + + ]: 18508 : if (to_destroy.size() == old_size) break;
465 : : }
466 : : // The order in which these ancestors/descendants are destroyed should not matter;
467 : : // randomly shuffle them.
468 : 16814 : std::shuffle(to_destroy.begin(), to_destroy.end(), rng);
469 [ + + ]: 37937 : for (TxGraph::Ref* ptr : to_destroy) {
470 [ + + ]: 48093 : for (size_t level = 0; level < sims.size(); ++level) {
471 : 26970 : sims[level].DestroyTransaction(ptr, level == sims.size() - 1);
472 : : }
473 : : }
474 : 16814 : break;
475 [ + + + + ]: 602996 : } else if (block_builders.empty() && command-- == 0) {
476 : : // SetTransactionFee.
477 : 7170 : int64_t fee;
478 [ + + ]: 7170 : if (alt) {
479 : 2750 : fee = provider.ConsumeIntegralInRange<int64_t>(-0x8000000000000, 0x7ffffffffffff);
480 : : } else {
481 : 4420 : fee = provider.ConsumeIntegral<uint8_t>();
482 : : }
483 : 7170 : auto ref = pick_fn();
484 : 7170 : real->SetTransactionFee(*ref, fee);
485 [ + + ]: 17877 : for (auto& sim : sims) {
486 : 10707 : sim.SetTransactionFee(ref, fee);
487 : : }
488 : : break;
489 [ + + ]: 579012 : } else if (command-- == 0) {
490 : : // GetTransactionCount.
491 [ - + ]: 57617 : assert(real->GetTransactionCount(use_main) == sel_sim.GetTransactionCount());
492 : : break;
493 [ + + ]: 521395 : } else if (command-- == 0) {
494 : : // Exists.
495 : 14891 : auto ref = pick_fn();
496 : 14891 : bool exists = real->Exists(*ref, use_main);
497 : 14891 : bool should_exist = sel_sim.Find(ref) != SimTxGraph::MISSING;
498 [ - + ]: 14891 : assert(exists == should_exist);
499 : : break;
500 [ + + ]: 506504 : } else if (command-- == 0) {
501 : : // IsOversized.
502 [ - + ]: 22879 : assert(sel_sim.IsOversized() == real->IsOversized(use_main));
503 : : break;
504 [ + + ]: 483625 : } else if (command-- == 0) {
505 : : // GetIndividualFeerate.
506 : 8787 : auto ref = pick_fn();
507 : 8787 : auto feerate = real->GetIndividualFeerate(*ref);
508 : 8787 : bool found{false};
509 [ + + ]: 20196 : for (auto& sim : sims) {
510 : 11409 : auto simpos = sim.Find(ref);
511 [ + + ]: 11409 : if (simpos != SimTxGraph::MISSING) {
512 : 7845 : found = true;
513 [ + - ]: 19254 : assert(feerate == sim.graph.FeeRate(simpos));
514 : : }
515 : : }
516 [ + + - + ]: 8787 : if (!found) assert(feerate.IsEmpty());
517 : : break;
518 [ + + + + ]: 474838 : } else if (!main_sim.IsOversized() && command-- == 0) {
519 : : // GetMainChunkFeerate.
520 : 10152 : auto ref = pick_fn();
521 : 10152 : auto feerate = real->GetMainChunkFeerate(*ref);
522 : 10152 : auto simpos = main_sim.Find(ref);
523 [ + + ]: 10152 : if (simpos == SimTxGraph::MISSING) {
524 [ - + ]: 3882 : assert(feerate.IsEmpty());
525 : : } else {
526 : : // Just do some quick checks that the reported value is in range. A full
527 : : // recomputation of expected chunk feerates is done at the end.
528 [ - + ]: 6270 : assert(feerate.size >= main_sim.graph.FeeRate(simpos).size);
529 [ - + ]: 6270 : assert(feerate.size <= main_sim.SumAll().size);
530 : : }
531 : : break;
532 [ + + + + ]: 464686 : } else if (!sel_sim.IsOversized() && command-- == 0) {
533 : : // GetAncestors/GetDescendants.
534 : 7800 : auto ref = pick_fn();
535 [ + + ]: 7800 : auto result = alt ? real->GetDescendants(*ref, use_main)
536 : 7800 : : real->GetAncestors(*ref, use_main);
537 [ - + ]: 7800 : assert(result.size() <= max_count);
538 : 7800 : auto result_set = sel_sim.MakeSet(result);
539 [ - + ]: 7800 : assert(result.size() == result_set.Count());
540 : 7800 : auto expect_set = sel_sim.GetAncDesc(ref, alt);
541 [ - + ]: 7800 : assert(result_set == expect_set);
542 : 7800 : break;
543 [ + + + + ]: 464686 : } else if (!sel_sim.IsOversized() && command-- == 0) {
544 : : // GetAncestorsUnion/GetDescendantsUnion.
545 : 7730 : std::vector<TxGraph::Ref*> refs;
546 : : // Gather a list of up to 15 Ref pointers.
547 : 7730 : auto count = provider.ConsumeIntegralInRange<size_t>(0, 15);
548 [ + - ]: 7730 : refs.resize(count);
549 [ + + ]: 56917 : for (size_t i = 0; i < count; ++i) {
550 : 49187 : refs[i] = pick_fn();
551 : : }
552 : : // Their order should not matter, shuffle them.
553 : 7730 : std::shuffle(refs.begin(), refs.end(), rng);
554 : : // Invoke the real function, and convert to SimPos set.
555 [ + + ]: 7730 : auto result = alt ? real->GetDescendantsUnion(refs, use_main)
556 : 7730 : : real->GetAncestorsUnion(refs, use_main);
557 : 7730 : auto result_set = sel_sim.MakeSet(result);
558 [ - + ]: 7730 : assert(result.size() == result_set.Count());
559 : : // Compute the expected result.
560 : 7730 : SimTxGraph::SetType expect_set;
561 [ + + ]: 56917 : for (TxGraph::Ref* ref : refs) expect_set |= sel_sim.GetAncDesc(ref, alt);
562 : : // Compare.
563 [ - + ]: 7730 : assert(result_set == expect_set);
564 : 7730 : break;
565 [ + + + + ]: 456886 : } else if (!sel_sim.IsOversized() && command-- == 0) {
566 : : // GetCluster.
567 : 10652 : auto ref = pick_fn();
568 : 10652 : auto result = real->GetCluster(*ref, use_main);
569 : : // Check cluster count limit.
570 [ - + ]: 10652 : assert(result.size() <= max_count);
571 : : // Require the result to be topologically valid and not contain duplicates.
572 : 10652 : auto left = sel_sim.graph.Positions();
573 [ + + ]: 24352 : for (auto refptr : result) {
574 : 13700 : auto simpos = sel_sim.Find(refptr);
575 [ - + ]: 13700 : assert(simpos != SimTxGraph::MISSING);
576 [ - + ]: 13700 : assert(left[simpos]);
577 : 13700 : left.Reset(simpos);
578 [ - + ]: 27400 : assert(!sel_sim.graph.Ancestors(simpos).Overlaps(left));
579 : : }
580 : : // Require the set to be connected.
581 : 10652 : auto result_set = sel_sim.MakeSet(result);
582 [ - + ]: 10652 : assert(sel_sim.graph.IsConnected(result_set));
583 : : // If ref exists, the result must contain it. If not, it must be empty.
584 : 10652 : auto simpos = sel_sim.Find(ref);
585 [ + + ]: 10652 : if (simpos != SimTxGraph::MISSING) {
586 [ - + ]: 5839 : assert(result_set[simpos]);
587 : : } else {
588 [ - + ]: 4813 : assert(result_set.None());
589 : : }
590 : : // Require the set not to have ancestors or descendants outside of it.
591 [ + + ]: 24352 : for (auto i : result_set) {
592 [ - + ]: 27400 : assert(sel_sim.graph.Ancestors(i).IsSubsetOf(result_set));
593 [ - + ]: 13700 : assert(sel_sim.graph.Descendants(i).IsSubsetOf(result_set));
594 : : }
595 : 10652 : break;
596 [ + + ]: 449156 : } else if (command-- == 0) {
597 : : // HaveStaging.
598 [ - + ]: 14329 : assert((sims.size() == 2) == real->HaveStaging());
599 : : break;
600 [ + + + + ]: 424175 : } else if (sims.size() < 2 && command-- == 0) {
601 : : // StartStaging.
602 [ + - ]: 8055 : sims.emplace_back(sims.back());
603 : 8055 : sims.back().modified = SimTxGraph::SetType{};
604 : 8055 : real->StartStaging();
605 : 8055 : break;
606 [ + + + + : 416120 : } else if (block_builders.empty() && sims.size() > 1 && command-- == 0) {
+ + ]
607 : : // CommitStaging.
608 : 3821 : real->CommitStaging();
609 : 3821 : sims.erase(sims.begin());
610 : : break;
611 [ + + + + ]: 412299 : } else if (sims.size() > 1 && command-- == 0) {
612 : : // AbortStaging.
613 : 2380 : real->AbortStaging();
614 : 2380 : sims.pop_back();
615 : : // Reset the cached oversized value (if TxGraph::Ref destructions triggered
616 : : // removals of main transactions while staging was active, then aborting will
617 : : // cause it to be re-evaluated in TxGraph).
618 [ + - ]: 509309 : sims.back().oversized = std::nullopt;
619 : : break;
620 [ + + + + ]: 409919 : } else if (!main_sim.IsOversized() && command-- == 0) {
621 : : // CompareMainOrder.
622 : 9880 : auto ref_a = pick_fn();
623 : 9880 : auto ref_b = pick_fn();
624 : 9880 : auto sim_a = main_sim.Find(ref_a);
625 : 9880 : auto sim_b = main_sim.Find(ref_b);
626 : : // Both transactions must exist in the main graph.
627 [ + + ]: 9880 : if (sim_a == SimTxGraph::MISSING || sim_b == SimTxGraph::MISSING) break;
628 : 3852 : auto cmp = real->CompareMainOrder(*ref_a, *ref_b);
629 : : // Distinct transactions have distinct places.
630 [ + + - + ]: 3852 : if (sim_a != sim_b) assert(cmp != 0);
631 : : // Ancestors go before descendants.
632 [ + + - + ]: 3852 : if (main_sim.graph.Ancestors(sim_a)[sim_b]) assert(cmp >= 0);
633 [ + + - + ]: 3852 : if (main_sim.graph.Descendants(sim_a)[sim_b]) assert(cmp <= 0);
634 : : // Do not verify consistency with chunk feerates, as we cannot easily determine
635 : : // these here without making more calls to real, which could affect its internal
636 : : // state. A full comparison is done at the end.
637 : : break;
638 [ + + + + ]: 400039 : } else if (!sel_sim.IsOversized() && command-- == 0) {
639 : : // CountDistinctClusters.
640 : 10255 : std::vector<TxGraph::Ref*> refs;
641 : : // Gather a list of up to 15 (or up to 255) Ref pointers.
642 [ + + ]: 16404 : auto count = provider.ConsumeIntegralInRange<size_t>(0, alt ? 255 : 15);
643 [ + - ]: 10255 : refs.resize(count);
644 [ + + ]: 255253 : for (size_t i = 0; i < count; ++i) {
645 : 244998 : refs[i] = pick_fn();
646 : : }
647 : : // Their order should not matter, shuffle them.
648 : 10255 : std::shuffle(refs.begin(), refs.end(), rng);
649 : : // Invoke the real function.
650 : 10255 : auto result = real->CountDistinctClusters(refs, use_main);
651 : : // Build a set with representatives of the clusters the Refs occur in in the
652 : : // simulated graph. For each, remember the lowest-index transaction SimPos in the
653 : : // cluster.
654 : 10255 : SimTxGraph::SetType sim_reps;
655 [ + + ]: 255253 : for (auto ref : refs) {
656 : : // Skip Refs that do not occur in the simulated graph.
657 : 244998 : auto simpos = sel_sim.Find(ref);
658 [ + + ]: 244998 : if (simpos == SimTxGraph::MISSING) continue;
659 : : // Find the component that includes ref.
660 : 139236 : auto component = sel_sim.graph.GetConnectedComponent(sel_sim.graph.Positions(), simpos);
661 : : // Remember the lowest-index SimPos in component, as a representative for it.
662 [ - + ]: 278472 : assert(component.Any());
663 : 139236 : sim_reps.Set(component.First());
664 : : }
665 : : // Compare the number of deduplicated representatives with the value returned by
666 : : // the real function.
667 [ - + ]: 10255 : assert(result == sim_reps.Count());
668 : 10255 : break;
669 [ + + ]: 400039 : } else if (command-- == 0) {
670 : : // DoWork.
671 : 17031 : real->DoWork();
672 : 17031 : break;
673 [ + + + + : 372753 : } else if (sims.size() == 2 && !sims[0].IsOversized() && !sims[1].IsOversized() && command-- == 0) {
+ + + + ]
674 : : // GetMainStagingDiagrams()
675 : 12984 : auto [real_main_diagram, real_staged_diagram] = real->GetMainStagingDiagrams();
676 : 12984 : auto real_sum_main = std::accumulate(real_main_diagram.begin(), real_main_diagram.end(), FeeFrac{});
677 : 12984 : auto real_sum_staged = std::accumulate(real_staged_diagram.begin(), real_staged_diagram.end(), FeeFrac{});
678 : 12984 : auto real_gain = real_sum_staged - real_sum_main;
679 [ + - ]: 12984 : auto sim_gain = sims[1].SumAll() - sims[0].SumAll();
680 : : // Just check that the total fee gained/lost and size gained/lost according to the
681 : : // diagram matches the difference in these values in the simulated graph. A more
682 : : // complete check of the GetMainStagingDiagrams result is performed at the end.
683 [ + - ]: 12984 : assert(sim_gain == real_gain);
684 : : // Check that the feerates in each diagram are monotonically decreasing.
685 [ + + ]: 126458 : for (size_t i = 1; i < real_main_diagram.size(); ++i) {
686 [ - + ]: 113474 : assert(FeeRateCompare(real_main_diagram[i], real_main_diagram[i - 1]) <= 0);
687 : : }
688 [ + + ]: 176562 : for (size_t i = 1; i < real_staged_diagram.size(); ++i) {
689 [ - + ]: 163578 : assert(FeeRateCompare(real_staged_diagram[i], real_staged_diagram[i - 1]) <= 0);
690 : : }
691 : 12984 : break;
692 [ + + + + : 372753 : } else if (block_builders.size() < 4 && !main_sim.IsOversized() && command-- == 0) {
+ + ]
693 : : // GetBlockBuilder.
694 [ + - ]: 4783 : block_builders.emplace_back(real->GetBlockBuilder());
695 : 4783 : break;
696 [ + + + + ]: 354986 : } else if (!block_builders.empty() && command-- == 0) {
697 : : // ~BlockBuilder.
698 : 2346 : block_builders.erase(block_builders.begin() + builder_idx);
699 : : break;
700 [ + + + + ]: 352640 : } else if (!block_builders.empty() && command-- == 0) {
701 : : // BlockBuilder::GetCurrentChunk, followed by Include/Skip.
702 : 5882 : auto& builder_data = block_builders[builder_idx];
703 : 5882 : auto new_included = builder_data.included;
704 : 5882 : auto new_done = builder_data.done;
705 : 5882 : auto chunk = builder_data.builder->GetCurrentChunk();
706 [ + + ]: 5882 : if (chunk) {
707 : : // Chunk feerates must be monotonously decreasing.
708 [ + + ]: 2059 : if (!builder_data.last_feerate.IsEmpty()) {
709 [ - + ]: 1295 : assert(!(chunk->second >> builder_data.last_feerate));
710 : : }
711 : 2059 : builder_data.last_feerate = chunk->second;
712 : : // Verify the contents of GetCurrentChunk.
713 : 2059 : FeePerWeight sum_feerate;
714 [ + + ]: 4262 : for (TxGraph::Ref* ref : chunk->first) {
715 : : // Each transaction in the chunk must exist in the main graph.
716 : 2203 : auto simpos = main_sim.Find(ref);
717 [ - + ]: 2203 : assert(simpos != SimTxGraph::MISSING);
718 : : // Verify the claimed chunk feerate.
719 : 2203 : sum_feerate += main_sim.graph.FeeRate(simpos);
720 : : // Make sure no transaction is reported twice.
721 [ - + ]: 2203 : assert(!new_done[simpos]);
722 : 2203 : new_done.Set(simpos);
723 : : // The concatenation of all included transactions must be topologically valid.
724 : 2203 : new_included.Set(simpos);
725 [ - + ]: 4406 : assert(main_sim.graph.Ancestors(simpos).IsSubsetOf(new_included));
726 : : }
727 [ + - ]: 2059 : assert(sum_feerate == chunk->second);
728 : : } else {
729 : : // When we reach the end, if nothing was skipped, the entire graph should have
730 : : // been reported.
731 [ + + ]: 3823 : if (builder_data.done == builder_data.included) {
732 [ - + ]: 2665 : assert(builder_data.done.Count() == main_sim.GetTransactionCount());
733 : : }
734 : : }
735 : : // Possibly invoke GetCurrentChunk() again, which should give the same result.
736 [ + + ]: 5882 : if ((orig_command % 7) >= 5) {
737 : 1321 : auto chunk2 = builder_data.builder->GetCurrentChunk();
738 [ - + ]: 1321 : assert(chunk == chunk2);
739 : 1321 : }
740 : : // Skip or include.
741 [ + + ]: 5882 : if ((orig_command % 5) >= 3) {
742 : : // Skip.
743 : 2263 : builder_data.builder->Skip();
744 : : } else {
745 : : // Include.
746 : 3619 : builder_data.builder->Include();
747 : 3619 : builder_data.included = new_included;
748 : : }
749 : 5882 : builder_data.done = new_done;
750 : 5882 : break;
751 [ + + + + : 604308 : } else if (!main_sim.IsOversized() && command-- == 0) {
+ + ]
752 : : // GetWorstMainChunk.
753 [ + + ]: 13453 : auto [worst_chunk, worst_chunk_feerate] = real->GetWorstMainChunk();
754 : : // Just do some sanity checks here. Consistency with GetBlockBuilder is checked
755 : : // below.
756 [ + + ]: 13453 : if (main_sim.GetTransactionCount() == 0) {
757 [ - + ]: 6007 : assert(worst_chunk.empty());
758 [ - + ]: 6007 : assert(worst_chunk_feerate.IsEmpty());
759 : : } else {
760 [ - + ]: 7446 : assert(!worst_chunk.empty());
761 : 7446 : SimTxGraph::SetType done;
762 : 7446 : FeePerWeight sum;
763 [ + + ]: 16353 : for (TxGraph::Ref* ref : worst_chunk) {
764 : : // Each transaction in the chunk must exist in the main graph.
765 : 8907 : auto simpos = main_sim.Find(ref);
766 [ - + ]: 8907 : assert(simpos != SimTxGraph::MISSING);
767 : 8907 : sum += main_sim.graph.FeeRate(simpos);
768 : : // Make sure the chunk contains no duplicate transactions.
769 [ - + ]: 8907 : assert(!done[simpos]);
770 : 8907 : done.Set(simpos);
771 : : // All elements are preceded by all their descendants.
772 [ - + ]: 17814 : assert(main_sim.graph.Descendants(simpos).IsSubsetOf(done));
773 : : }
774 [ + - ]: 7446 : assert(sum == worst_chunk_feerate);
775 : : }
776 : 13453 : break;
777 : 13453 : }
778 : : }
779 : : }
780 : :
781 : : // After running all modifications, perform an internal sanity check (before invoking
782 : : // inspectors that may modify the internal state).
783 [ + - ]: 3709 : real->SanityCheck();
784 : :
785 [ + + ]: 3709 : if (!sims[0].IsOversized()) {
786 : : // If the main graph is not oversized, verify the total ordering implied by
787 : : // CompareMainOrder.
788 : : // First construct two distinct randomized permutations of the positions in sims[0].
789 : 3164 : std::vector<SimTxGraph::Pos> vec1;
790 [ + - + + ]: 55150 : for (auto i : sims[0].graph.Positions()) vec1.push_back(i);
791 : 3164 : std::shuffle(vec1.begin(), vec1.end(), rng);
792 [ + - ]: 3164 : auto vec2 = vec1;
793 : 3164 : std::shuffle(vec2.begin(), vec2.end(), rng);
794 [ + + ]: 3164 : if (vec1 == vec2) std::next_permutation(vec2.begin(), vec2.end());
795 : : // Sort both according to CompareMainOrder. By having randomized starting points, the order
796 : : // of CompareMainOrder invocations is somewhat randomized as well.
797 : 647949 : auto cmp = [&](SimTxGraph::Pos a, SimTxGraph::Pos b) noexcept {
798 : 644785 : return real->CompareMainOrder(*sims[0].GetRef(a), *sims[0].GetRef(b)) < 0;
799 : 3164 : };
800 : 3164 : std::sort(vec1.begin(), vec1.end(), cmp);
801 : 3164 : std::sort(vec2.begin(), vec2.end(), cmp);
802 : :
803 : : // Verify the resulting orderings are identical. This could only fail if the ordering was
804 : : // not total.
805 [ - + ]: 3164 : assert(vec1 == vec2);
806 : :
807 : : // Verify that the ordering is topological.
808 : 3164 : auto todo = sims[0].graph.Positions();
809 [ + + ]: 55150 : for (auto i : vec1) {
810 : 51986 : todo.Reset(i);
811 [ - + ]: 103972 : assert(!sims[0].graph.Ancestors(i).Overlaps(todo));
812 : : }
813 [ - + ]: 3164 : assert(todo.None());
814 : :
815 : : // For every transaction in the total ordering, find a random one before it and after it,
816 : : // and compare their chunk feerates, which must be consistent with the ordering.
817 [ + + ]: 55150 : for (size_t pos = 0; pos < vec1.size(); ++pos) {
818 : 51986 : auto pos_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[pos]));
819 [ + + ]: 51986 : if (pos > 0) {
820 : 49241 : size_t before = rng.randrange<size_t>(pos);
821 : 49241 : auto before_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[before]));
822 [ - + ]: 49241 : assert(FeeRateCompare(before_feerate, pos_feerate) >= 0);
823 : : }
824 [ + + ]: 51986 : if (pos + 1 < vec1.size()) {
825 : 49241 : size_t after = pos + 1 + rng.randrange<size_t>(vec1.size() - 1 - pos);
826 : 49241 : auto after_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[after]));
827 [ - + ]: 49241 : assert(FeeRateCompare(after_feerate, pos_feerate) <= 0);
828 : : }
829 : : }
830 : :
831 : : // The same order should be obtained through a BlockBuilder as implied by CompareMainOrder,
832 : : // if nothing is skipped.
833 : 3164 : auto builder = real->GetBlockBuilder();
834 : 3164 : std::vector<SimTxGraph::Pos> vec_builder;
835 : 3164 : std::vector<TxGraph::Ref*> last_chunk;
836 : 3164 : FeePerWeight last_chunk_feerate;
837 [ + + ]: 100466 : while (auto chunk = builder->GetCurrentChunk()) {
838 : 48651 : FeePerWeight sum;
839 [ + + ]: 100637 : for (TxGraph::Ref* ref : chunk->first) {
840 : : // The reported chunk feerate must match the chunk feerate obtained by asking
841 : : // it for each of the chunk's transactions individually.
842 [ + - ]: 51986 : assert(real->GetMainChunkFeerate(*ref) == chunk->second);
843 : : // Verify the chunk feerate matches the sum of the reported individual feerates.
844 : 51986 : sum += real->GetIndividualFeerate(*ref);
845 : : // Chunks must contain transactions that exist in the graph.
846 : 51986 : auto simpos = sims[0].Find(ref);
847 [ - + ]: 51986 : assert(simpos != SimTxGraph::MISSING);
848 [ + - ]: 51986 : vec_builder.push_back(simpos);
849 : : }
850 [ + - ]: 48651 : assert(sum == chunk->second);
851 : 48651 : last_chunk = std::move(chunk->first);
852 : 48651 : last_chunk_feerate = chunk->second;
853 : 48651 : builder->Include();
854 : 48651 : }
855 [ - + ]: 3164 : assert(vec_builder == vec1);
856 : :
857 : : // The last chunk returned by the BlockBuilder must match GetWorstMainChunk, in reverse.
858 : 3164 : std::reverse(last_chunk.begin(), last_chunk.end());
859 [ - + ]: 3164 : auto [worst_chunk, worst_chunk_feerate] = real->GetWorstMainChunk();
860 [ - + ]: 3164 : assert(last_chunk == worst_chunk);
861 [ + - ]: 3164 : assert(last_chunk_feerate == worst_chunk_feerate);
862 : :
863 : : // Check that the implied ordering gives rise to a combined diagram that matches the
864 : : // diagram constructed from the individual cluster linearization chunkings.
865 [ + - ]: 3164 : auto main_real_diagram = get_diagram_fn(/*main_only=*/true);
866 : 3164 : auto main_implied_diagram = ChunkLinearization(sims[0].graph, vec1);
867 [ + - - + ]: 3164 : assert(CompareChunks(main_real_diagram, main_implied_diagram) == 0);
868 : :
869 [ + + + + ]: 3164 : if (sims.size() >= 2 && !sims[1].IsOversized()) {
870 : : // When the staging graph is not oversized as well, call GetMainStagingDiagrams, and
871 : : // fully verify the result.
872 : 1554 : auto [main_cmp_diagram, stage_cmp_diagram] = real->GetMainStagingDiagrams();
873 : : // Check that the feerates in each diagram are monotonically decreasing.
874 [ + + ]: 8535 : for (size_t i = 1; i < main_cmp_diagram.size(); ++i) {
875 [ - + ]: 6981 : assert(FeeRateCompare(main_cmp_diagram[i], main_cmp_diagram[i - 1]) <= 0);
876 : : }
877 [ + + ]: 25020 : for (size_t i = 1; i < stage_cmp_diagram.size(); ++i) {
878 [ - + ]: 23466 : assert(FeeRateCompare(stage_cmp_diagram[i], stage_cmp_diagram[i - 1]) <= 0);
879 : : }
880 : : // Treat the diagrams as sets of chunk feerates, and sort them in the same way so that
881 : : // std::set_difference can be used on them below. The exact ordering does not matter
882 : : // here, but it has to be consistent with the one used in main_real_diagram and
883 : : // stage_real_diagram).
884 : 1554 : std::sort(main_cmp_diagram.begin(), main_cmp_diagram.end(), std::greater{});
885 : 1554 : std::sort(stage_cmp_diagram.begin(), stage_cmp_diagram.end(), std::greater{});
886 : : // Find the chunks that appear in main_diagram but are missing from main_cmp_diagram.
887 : : // This is allowed, because GetMainStagingDiagrams omits clusters in main unaffected
888 : : // by staging.
889 : 1554 : std::vector<FeeFrac> missing_main_cmp;
890 [ + - ]: 1554 : std::set_difference(main_real_diagram.begin(), main_real_diagram.end(),
891 : : main_cmp_diagram.begin(), main_cmp_diagram.end(),
892 : : std::inserter(missing_main_cmp, missing_main_cmp.end()),
893 : : std::greater{});
894 [ - + ]: 1554 : assert(main_cmp_diagram.size() + missing_main_cmp.size() == main_real_diagram.size());
895 : : // Do the same for chunks in stage_diagram missing from stage_cmp_diagram.
896 [ + - ]: 1554 : auto stage_real_diagram = get_diagram_fn(/*main_only=*/false);
897 : 1554 : std::vector<FeeFrac> missing_stage_cmp;
898 [ + - ]: 1554 : std::set_difference(stage_real_diagram.begin(), stage_real_diagram.end(),
899 : : stage_cmp_diagram.begin(), stage_cmp_diagram.end(),
900 : : std::inserter(missing_stage_cmp, missing_stage_cmp.end()),
901 : : std::greater{});
902 [ - + ]: 1554 : assert(stage_cmp_diagram.size() + missing_stage_cmp.size() == stage_real_diagram.size());
903 : : // The missing chunks must be equal across main & staging (otherwise they couldn't have
904 : : // been omitted).
905 [ - + ]: 1554 : assert(missing_main_cmp == missing_stage_cmp);
906 : :
907 : : // The missing part must include at least all transactions in staging which have not been
908 : : // modified, or been in a cluster together with modified transactions, since they were
909 : : // copied from main. Note that due to the reordering of removals w.r.t. dependency
910 : : // additions, it is possible that the real implementation found more unaffected things.
911 : 1554 : FeeFrac missing_real;
912 [ + + ]: 15928 : for (const auto& feerate : missing_main_cmp) missing_real += feerate;
913 : 1554 : FeeFrac missing_expected = sims[1].graph.FeeRate(sims[1].graph.Positions() - sims[1].modified);
914 : : // Note that missing_real.fee < missing_expected.fee is possible to due the presence of
915 : : // negative-fee transactions.
916 [ - + ]: 1554 : assert(missing_real.size >= missing_expected.size);
917 : 3108 : }
918 : 3164 : }
919 : :
920 [ - + ]: 3709 : assert(real->HaveStaging() == (sims.size() > 1));
921 : :
922 : : // Try to run a full comparison, for both main_only=false and main_only=true in TxGraph
923 : : // inspector functions that support both.
924 [ + + ]: 11127 : for (int main_only = 0; main_only < 2; ++main_only) {
925 [ + + ]: 7418 : auto& sim = main_only ? sims[0] : sims.back();
926 : : // Compare simple properties of the graph with the simulation.
927 [ - + ]: 7418 : assert(real->IsOversized(main_only) == sim.IsOversized());
928 [ - + ]: 7418 : assert(real->GetTransactionCount(main_only) == sim.GetTransactionCount());
929 : : // If the graph (and the simulation) are not oversized, perform a full comparison.
930 [ + + ]: 7418 : if (!sim.IsOversized()) {
931 : 6315 : auto todo = sim.graph.Positions();
932 : : // Iterate over all connected components of the resulting (simulated) graph, each of which
933 : : // should correspond to a cluster in the real one.
934 [ + + ]: 219498 : while (todo.Any()) {
935 : 103434 : auto component = sim.graph.FindConnectedComponent(todo);
936 : 103434 : todo -= component;
937 : : // Iterate over the transactions in that component.
938 [ + + ]: 226530 : for (auto i : component) {
939 : : // Check its individual feerate against simulation.
940 [ + - ]: 123096 : assert(sim.graph.FeeRate(i) == real->GetIndividualFeerate(*sim.GetRef(i)));
941 : : // Check its ancestors against simulation.
942 : 123096 : auto expect_anc = sim.graph.Ancestors(i);
943 : 123096 : auto anc = sim.MakeSet(real->GetAncestors(*sim.GetRef(i), main_only));
944 [ - + ]: 123096 : assert(anc.Count() <= max_count);
945 [ - + ]: 123096 : assert(anc == expect_anc);
946 : : // Check its descendants against simulation.
947 : 123096 : auto expect_desc = sim.graph.Descendants(i);
948 : 123096 : auto desc = sim.MakeSet(real->GetDescendants(*sim.GetRef(i), main_only));
949 [ - + ]: 123096 : assert(desc.Count() <= max_count);
950 [ - + ]: 123096 : assert(desc == expect_desc);
951 : : // Check the cluster the transaction is part of.
952 : 123096 : auto cluster = real->GetCluster(*sim.GetRef(i), main_only);
953 [ - + ]: 123096 : assert(cluster.size() <= max_count);
954 [ - + ]: 123096 : assert(sim.MakeSet(cluster) == component);
955 : : // Check that the cluster is reported in a valid topological order (its
956 : : // linearization).
957 : 123096 : std::vector<DepGraphIndex> simlin;
958 : 123096 : SimTxGraph::SetType done;
959 [ + + ]: 601758 : for (TxGraph::Ref* ptr : cluster) {
960 : 478662 : auto simpos = sim.Find(ptr);
961 [ - + ]: 957324 : assert(sim.graph.Descendants(simpos).IsSubsetOf(component - done));
962 : 478662 : done.Set(simpos);
963 [ - + ]: 957324 : assert(sim.graph.Ancestors(simpos).IsSubsetOf(done));
964 [ + - ]: 478662 : simlin.push_back(simpos);
965 : : }
966 : : // Construct a chunking object for the simulated graph, using the reported cluster
967 : : // linearization as ordering, and compare it against the reported chunk feerates.
968 [ + + + + ]: 123096 : if (sims.size() == 1 || main_only) {
969 : 79003 : cluster_linearize::LinearizationChunking simlinchunk(sim.graph, simlin);
970 : 79003 : DepGraphIndex idx{0};
971 [ + + ]: 275789 : for (unsigned chunknum = 0; chunknum < simlinchunk.NumChunksLeft(); ++chunknum) {
972 : 196786 : auto chunk = simlinchunk.GetChunk(chunknum);
973 : : // Require that the chunks of cluster linearizations are connected (this must
974 : : // be the case as all linearizations inside are PostLinearized).
975 [ - + ]: 196786 : assert(sim.graph.IsConnected(chunk.transactions));
976 : : // Check the chunk feerates of all transactions in the cluster.
977 [ + + ]: 980270 : while (chunk.transactions.Any()) {
978 [ - + ]: 293349 : assert(chunk.transactions[simlin[idx]]);
979 : 293349 : chunk.transactions.Reset(simlin[idx]);
980 [ + - ]: 293349 : assert(chunk.feerate == real->GetMainChunkFeerate(*cluster[idx]));
981 : 293349 : ++idx;
982 : : }
983 : : }
984 : 79003 : }
985 : 123096 : }
986 : : }
987 : : }
988 : : }
989 : :
990 : : // Sanity check again (because invoking inspectors may modify internal unobservable state).
991 [ + - ]: 3709 : real->SanityCheck();
992 : :
993 : : // Kill the block builders.
994 : 3709 : block_builders.clear();
995 : : // Kill the TxGraph object.
996 [ + - ]: 3709 : real.reset();
997 : : // Kill the simulated graphs, with all remaining Refs in it. If any, this verifies that Refs
998 : : // can outlive the TxGraph that created them.
999 : 3709 : sims.clear();
1000 : 3709 : }
|
