Branch data Line data Source code
1 : : // Copyright (c) The Bitcoin Core developers
2 : : // Distributed under the MIT software license, see the accompanying
3 : : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 : :
5 : : #include <txgraph.h>
6 : : #include <cluster_linearize.h>
7 : : #include <test/fuzz/fuzz.h>
8 : : #include <test/fuzz/FuzzedDataProvider.h>
9 : : #include <test/util/random.h>
10 : : #include <util/bitset.h>
11 : : #include <util/feefrac.h>
12 : :
13 : : #include <algorithm>
14 : : #include <map>
15 : : #include <memory>
16 : : #include <set>
17 : : #include <stdint.h>
18 : : #include <utility>
19 : :
20 : : using namespace cluster_linearize;
21 : :
22 : : namespace {
23 : :
24 : : /** Data type representing a naive simulated TxGraph, keeping all transactions (even from
25 : : * disconnected components) in a single DepGraph. Unlike the real TxGraph, this only models
26 : : * a single graph, and multiple instances are used to simulate main/staging. */
27 : : struct SimTxGraph
28 : : {
29 : : /** Maximum number of transactions to support simultaneously. Set this higher than txgraph's
30 : : * cluster count, so we can exercise situations with more transactions than fit in one
31 : : * cluster. */
32 : : static constexpr unsigned MAX_TRANSACTIONS = MAX_CLUSTER_COUNT_LIMIT * 2;
33 : : /** Set type to use in the simulation. */
34 : : using SetType = BitSet<MAX_TRANSACTIONS>;
35 : : /** Data type for representing positions within SimTxGraph::graph. */
36 : : using Pos = DepGraphIndex;
37 : : /** Constant to mean "missing in this graph". */
38 : : static constexpr auto MISSING = Pos(-1);
39 : :
40 : : /** The dependency graph (for all transactions in the simulation, regardless of
41 : : * connectivity/clustering). */
42 : : DepGraph<SetType> graph;
43 : : /** For each position in graph, which TxGraph::Ref it corresponds with (if any). Use shared_ptr
44 : : * so that a SimTxGraph can be copied to create a staging one, while sharing Refs with
45 : : * the main graph. */
46 : : std::array<std::shared_ptr<TxGraph::Ref>, MAX_TRANSACTIONS> simmap;
47 : : /** For each TxGraph::Ref in graph, the position it corresponds with. */
48 : : std::map<const TxGraph::Ref*, Pos> simrevmap;
49 : : /** The set of TxGraph::Ref entries that have been removed, but not yet destroyed. */
50 : : std::vector<std::shared_ptr<TxGraph::Ref>> removed;
51 : : /** Whether the graph is oversized (true = yes, false = no, std::nullopt = unknown). */
52 : : std::optional<bool> oversized;
53 : : /** The configured maximum number of transactions per cluster. */
54 : : DepGraphIndex max_cluster_count;
55 : :
56 : : /** Construct a new SimTxGraph with the specified maximum cluster count. */
57 : 2258 : explicit SimTxGraph(DepGraphIndex max_cluster) : max_cluster_count(max_cluster) {}
58 : :
59 : : // Permit copying and moving.
60 [ + - + - ]: 7111 : SimTxGraph(const SimTxGraph&) noexcept = default;
61 : : SimTxGraph& operator=(const SimTxGraph&) noexcept = default;
62 : 0 : SimTxGraph(SimTxGraph&&) noexcept = default;
63 : 5290 : SimTxGraph& operator=(SimTxGraph&&) noexcept = default;
64 : :
65 : : /** Check whether this graph is oversized (contains a connected component whose number of
66 : : * transactions exceeds max_cluster_count. */
67 : 1583115 : bool IsOversized()
68 : : {
69 [ + + ]: 1583115 : if (!oversized.has_value()) {
70 : : // Only recompute when oversized isn't already known.
71 : 25019 : oversized = false;
72 : 25019 : auto todo = graph.Positions();
73 : : // Iterate over all connected components of the graph.
74 [ + + ]: 1004402 : while (todo.Any()) {
75 : 477182 : auto component = graph.FindConnectedComponent(todo);
76 [ + + ]: 477182 : if (component.Count() > max_cluster_count) oversized = true;
77 : 477182 : todo -= component;
78 : : }
79 : : }
80 : 1583115 : return *oversized;
81 : : }
82 : :
83 : : /** Determine the number of (non-removed) transactions in the graph. */
84 [ + + ]: 241748 : DepGraphIndex GetTransactionCount() const { return graph.TxCount(); }
85 : :
86 : : /** Get the position where ref occurs in this simulated graph, or -1 if it does not. */
87 : 1598757 : Pos Find(const TxGraph::Ref* ref) const
88 : : {
89 : 1598757 : auto it = simrevmap.find(ref);
90 [ + + ]: 1598757 : if (it != simrevmap.end()) return it->second;
91 : : return MISSING;
92 : : }
93 : :
94 : : /** Given a position in this simulated graph, get the corresponding TxGraph::Ref. */
95 : 1648025 : TxGraph::Ref* GetRef(Pos pos)
96 : : {
97 [ - + ]: 1648025 : assert(graph.Positions()[pos]);
98 [ - + ]: 1648025 : assert(simmap[pos]);
99 : 1648025 : return simmap[pos].get();
100 : : }
101 : :
102 : : /** Add a new transaction to the simulation. */
103 : 82496 : TxGraph::Ref* AddTransaction(const FeePerWeight& feerate)
104 : : {
105 [ - + ]: 82496 : assert(graph.TxCount() < MAX_TRANSACTIONS);
106 : 82496 : auto simpos = graph.AddTransaction(feerate);
107 [ - + ]: 82496 : assert(graph.Positions()[simpos]);
108 [ - + ]: 82496 : simmap[simpos] = std::make_shared<TxGraph::Ref>();
109 : 82496 : auto ptr = simmap[simpos].get();
110 : 82496 : simrevmap[ptr] = simpos;
111 : 82496 : return ptr;
112 : : }
113 : :
114 : : /** Add a dependency between two positions in this graph. */
115 : 36138 : void AddDependency(TxGraph::Ref* parent, TxGraph::Ref* child)
116 : : {
117 : 36138 : auto par_pos = Find(parent);
118 [ + + ]: 36138 : if (par_pos == MISSING) return;
119 : 33096 : auto chl_pos = Find(child);
120 [ + + ]: 33096 : if (chl_pos == MISSING) return;
121 : 30441 : graph.AddDependencies(SetType::Singleton(par_pos), chl_pos);
122 : : // This may invalidate our cached oversized value.
123 [ + + + + ]: 30441 : if (oversized.has_value() && !*oversized) oversized = std::nullopt;
124 : : }
125 : :
126 : : /** Modify the transaction fee of a ref, if it exists. */
127 : 14727 : void SetTransactionFee(TxGraph::Ref* ref, int64_t fee)
128 : : {
129 : 14727 : auto pos = Find(ref);
130 [ + + ]: 14727 : if (pos == MISSING) return;
131 : 10709 : graph.FeeRate(pos).fee = fee;
132 : : }
133 : :
134 : : /** Remove the transaction in the specified position from the graph. */
135 : 12715 : void RemoveTransaction(TxGraph::Ref* ref)
136 : : {
137 : 12715 : auto pos = Find(ref);
138 [ + + ]: 12715 : if (pos == MISSING) return;
139 : 7681 : graph.RemoveTransactions(SetType::Singleton(pos));
140 : 7681 : simrevmap.erase(simmap[pos].get());
141 : : // Retain the TxGraph::Ref corresponding to this position, so the Ref destruction isn't
142 : : // invoked until the simulation explicitly decided to do so.
143 : 7681 : removed.push_back(std::move(simmap[pos]));
144 : 7681 : simmap[pos].reset();
145 : : // This may invalidate our cached oversized value.
146 [ + + + + ]: 7681 : if (oversized.has_value() && *oversized) oversized = std::nullopt;
147 : : }
148 : :
149 : : /** Destroy the transaction from the graph, including from the removed set. This will
150 : : * trigger TxGraph::Ref::~Ref. reset_oversize controls whether the cached oversized
151 : : * value is cleared (destroying does not clear oversizedness in TxGraph of the main
152 : : * graph while staging exists). */
153 : 19621 : void DestroyTransaction(TxGraph::Ref* ref, bool reset_oversize)
154 : : {
155 : 19621 : auto pos = Find(ref);
156 [ + + ]: 19621 : if (pos == MISSING) {
157 : : // Wipe the ref, if it exists, from the removed vector. Use std::partition rather
158 : : // than std::erase because we don't care about the order of the entries that
159 : : // remain.
160 [ + + - + ]: 20675 : auto remove = std::partition(removed.begin(), removed.end(), [&](auto& arg) { return arg.get() != ref; });
161 : 5229 : removed.erase(remove, removed.end());
162 : : } else {
163 : 14392 : graph.RemoveTransactions(SetType::Singleton(pos));
164 : 14392 : simrevmap.erase(simmap[pos].get());
165 : 14392 : simmap[pos].reset();
166 : : // This may invalidate our cached oversized value.
167 [ + + + + : 14392 : if (reset_oversize && oversized.has_value() && *oversized) {
+ + ]
168 : 2534 : oversized = std::nullopt;
169 : : }
170 : : }
171 : 19621 : }
172 : :
173 : : /** Construct the set with all positions in this graph corresponding to the specified
174 : : * TxGraph::Refs. All of them must occur in this graph and not be removed. */
175 : 271913 : SetType MakeSet(std::span<TxGraph::Ref* const> arg)
176 : : {
177 : 271913 : SetType ret;
178 [ + + ]: 1020255 : for (TxGraph::Ref* ptr : arg) {
179 : 748342 : auto pos = Find(ptr);
180 [ - + ]: 748342 : assert(pos != Pos(-1));
181 : 748342 : ret.Set(pos);
182 : : }
183 : 271913 : return ret;
184 : : }
185 : :
186 : : /** Get the set of ancestors (desc=false) or descendants (desc=true) in this graph. */
187 : 30626 : SetType GetAncDesc(TxGraph::Ref* arg, bool desc)
188 : : {
189 : 30626 : auto pos = Find(arg);
190 [ + + ]: 30626 : if (pos == MISSING) return {};
191 [ + + ]: 16062 : return desc ? graph.Descendants(pos) : graph.Ancestors(pos);
192 : : }
193 : :
194 : : /** Given a set of Refs (given as a vector of pointers), expand the set to include all its
195 : : * ancestors (desc=false) or all its descendants (desc=true) in this graph. */
196 : 26620 : void IncludeAncDesc(std::vector<TxGraph::Ref*>& arg, bool desc)
197 : : {
198 : 26620 : std::vector<TxGraph::Ref*> ret;
199 [ + + ]: 59443 : for (auto ptr : arg) {
200 : 32823 : auto simpos = Find(ptr);
201 [ + + ]: 32823 : if (simpos != MISSING) {
202 [ + + + + ]: 55846 : for (auto i : desc ? graph.Descendants(simpos) : graph.Ancestors(simpos)) {
203 [ + - ]: 33806 : ret.push_back(simmap[i].get());
204 : : }
205 : : } else {
206 [ + - ]: 10783 : ret.push_back(ptr);
207 : : }
208 : : }
209 : : // Construct deduplicated version in input (do not use std::sort/std::unique for
210 : : // deduplication as it'd rely on non-deterministic pointer comparison).
211 [ + - ]: 26620 : arg.clear();
212 [ + + ]: 71209 : for (auto ptr : ret) {
213 [ + + ]: 44589 : if (std::find(arg.begin(), arg.end(), ptr) == arg.end()) {
214 [ + - ]: 38138 : arg.push_back(ptr);
215 : : }
216 : : }
217 : 26620 : }
218 : : };
219 : :
220 : : } // namespace
221 : :
222 [ + - ]: 2702 : FUZZ_TARGET(txgraph)
223 : : {
224 : : // This is a big simulation test for TxGraph, which performs a fuzz-derived sequence of valid
225 : : // operations on a TxGraph instance, as well as on a simpler (mostly) reimplementation (see
226 : : // SimTxGraph above), comparing the outcome of functions that return a result, and finally
227 : : // performing a full comparison between the two.
228 : :
229 : 2258 : SeedRandomStateForTest(SeedRand::ZEROS);
230 : 2258 : FuzzedDataProvider provider(buffer.data(), buffer.size());
231 : :
232 : : /** Internal test RNG, used only for decisions which would require significant amount of data
233 : : * to be read from the provider, without realistically impacting test sensitivity. */
234 : 2258 : InsecureRandomContext rng(0xdecade2009added + buffer.size());
235 : :
236 : : /** Variable used whenever an empty TxGraph::Ref is needed. */
237 : 2258 : TxGraph::Ref empty_ref;
238 : :
239 : : // Decide the maximum number of transactions per cluster we will use in this simulation.
240 : 2258 : auto max_count = provider.ConsumeIntegralInRange<DepGraphIndex>(1, MAX_CLUSTER_COUNT_LIMIT);
241 : :
242 : : // Construct a real graph, and a vector of simulated graphs (main, and possibly staging).
243 : 2258 : auto real = MakeTxGraph(max_count);
244 : 2258 : std::vector<SimTxGraph> sims;
245 [ + - ]: 2258 : sims.reserve(2);
246 [ + - ]: 2258 : sims.emplace_back(max_count);
247 : :
248 : : /** Function to pick any Ref (for either sim in sims: from sim.simmap or sim.removed, or the
249 : : * empty Ref). */
250 : 244006 : auto pick_fn = [&]() noexcept -> TxGraph::Ref* {
251 [ + + ]: 241748 : size_t tx_count[2] = {sims[0].GetTransactionCount(), 0};
252 : : /** The number of possible choices. */
253 [ + + ]: 241748 : size_t choices = tx_count[0] + sims[0].removed.size() + 1;
254 [ + + ]: 241748 : if (sims.size() == 2) {
255 : 93201 : tx_count[1] = sims[1].GetTransactionCount();
256 : 93201 : choices += tx_count[1] + sims[1].removed.size();
257 : : }
258 : : /** Pick one of them. */
259 : 241748 : auto choice = provider.ConsumeIntegralInRange<size_t>(0, choices - 1);
260 : : // Consider both main and (if it exists) staging.
261 [ + + ]: 315585 : for (size_t level = 0; level < sims.size(); ++level) {
262 [ + + ]: 283025 : auto& sim = sims[level];
263 [ + + ]: 283025 : if (choice < tx_count[level]) {
264 : : // Return from graph.
265 [ + - ]: 1549092 : for (auto i : sim.graph.Positions()) {
266 [ + + ]: 1549092 : if (choice == 0) return sim.GetRef(i);
267 : 1353229 : --choice;
268 : : }
269 : 0 : assert(false);
270 : : } else {
271 : 87162 : choice -= tx_count[level];
272 : : }
273 [ + + ]: 87162 : if (choice < sim.removed.size()) {
274 : : // Return from removed.
275 : 13325 : return sim.removed[choice].get();
276 : : } else {
277 : 73837 : choice -= sim.removed.size();
278 : : }
279 : : }
280 : : // Return empty.
281 [ - + ]: 32560 : assert(choice == 0);
282 : 32560 : return &empty_ref;
283 : 2258 : };
284 : :
285 [ + + + + ]: 275961 : LIMITED_WHILE(provider.remaining_bytes() > 0, 200) {
286 : : // Read a one-byte command.
287 : 273703 : int command = provider.ConsumeIntegral<uint8_t>();
288 : : // Treat the lowest bit of a command as a flag (which selects a variant of some of the
289 : : // operations), and the second-lowest bit as a way of selecting main vs. staging, and leave
290 : : // the rest of the bits in command.
291 : 273703 : bool alt = command & 1;
292 : 273703 : bool use_main = command & 2;
293 : 273703 : command >>= 2;
294 : :
295 : : // Provide convenient aliases for the top simulated graph (main, or staging if it exists),
296 : : // one for the simulated graph selected based on use_main (for operations that can operate
297 : : // on both graphs), and one that always refers to the main graph.
298 : 273703 : auto& top_sim = sims.back();
299 [ + + ]: 273703 : auto& sel_sim = use_main ? sims[0] : top_sim;
300 : 273703 : auto& main_sim = sims[0];
301 : :
302 : : // Keep decrementing command for each applicable operation, until one is hit. Multiple
303 : : // iterations may be necessary.
304 : 490882 : while (true) {
305 [ + + + + ]: 490882 : if (top_sim.GetTransactionCount() < SimTxGraph::MAX_TRANSACTIONS && command-- == 0) {
306 : : // AddTransaction.
307 : 82496 : int64_t fee;
308 : 82496 : int32_t size;
309 [ + + ]: 82496 : if (alt) {
310 : : // If alt is true, pick fee and size from the entire range.
311 : 2583 : fee = provider.ConsumeIntegralInRange<int64_t>(-0x8000000000000, 0x7ffffffffffff);
312 : 2583 : size = provider.ConsumeIntegralInRange<int32_t>(1, 0x3fffff);
313 : : } else {
314 : : // Otherwise, use smaller range which consume fewer fuzz input bytes, as just
315 : : // these are likely sufficient to trigger all interesting code paths already.
316 : 79913 : fee = provider.ConsumeIntegral<uint8_t>();
317 : 79913 : size = provider.ConsumeIntegral<uint8_t>() + 1;
318 : : }
319 : 82496 : FeePerWeight feerate{fee, size};
320 : : // Create a real TxGraph::Ref.
321 : 82496 : auto ref = real->AddTransaction(feerate);
322 : : // Create a shared_ptr place in the simulation to put the Ref in.
323 [ + - ]: 82496 : auto ref_loc = top_sim.AddTransaction(feerate);
324 : : // Move it in place.
325 : 82496 : *ref_loc = std::move(ref);
326 : 82496 : break;
327 [ + + + + ]: 490882 : } else if (top_sim.GetTransactionCount() + top_sim.removed.size() > 1 && command-- == 0) {
328 : : // AddDependency.
329 : 41473 : auto par = pick_fn();
330 : 41473 : auto chl = pick_fn();
331 : 41473 : auto pos_par = top_sim.Find(par);
332 : 41473 : auto pos_chl = top_sim.Find(chl);
333 [ + + ]: 41473 : if (pos_par != SimTxGraph::MISSING && pos_chl != SimTxGraph::MISSING) {
334 : : // Determine if adding this would introduce a cycle (not allowed by TxGraph),
335 : : // and if so, skip.
336 [ + + ]: 35776 : if (top_sim.graph.Ancestors(pos_par)[pos_chl]) break;
337 : : }
338 : 36138 : top_sim.AddDependency(par, chl);
339 : 36138 : real->AddDependency(*par, *chl);
340 : 36138 : break;
341 [ + - + + ]: 366913 : } else if (top_sim.removed.size() < 100 && command-- == 0) {
342 : : // RemoveTransaction. Either all its ancestors or all its descendants are also
343 : : // removed (if any), to make sure TxGraph's reordering of removals and dependencies
344 : : // has no effect.
345 : 10415 : std::vector<TxGraph::Ref*> to_remove;
346 [ + - ]: 10415 : to_remove.push_back(pick_fn());
347 [ + - ]: 10415 : top_sim.IncludeAncDesc(to_remove, alt);
348 : : // The order in which these ancestors/descendants are removed should not matter;
349 : : // randomly shuffle them.
350 : 10415 : std::shuffle(to_remove.begin(), to_remove.end(), rng);
351 [ + + ]: 23130 : for (TxGraph::Ref* ptr : to_remove) {
352 : 12715 : real->RemoveTransaction(*ptr);
353 [ + - ]: 12715 : top_sim.RemoveTransaction(ptr);
354 : : }
355 : 10415 : break;
356 [ + + + + ]: 366913 : } else if (sel_sim.removed.size() > 0 && command-- == 0) {
357 : : // ~Ref (of an already-removed transaction). Destroying a TxGraph::Ref has an
358 : : // observable effect on the TxGraph it refers to, so this simulation permits doing
359 : : // so separately from other actions on TxGraph.
360 : :
361 : : // Pick a Ref of sel_sim.removed to destroy. Note that the same Ref may still occur
362 : : // in the other graph, and thus not actually trigger ~Ref yet (which is exactly
363 : : // what we want, as destroying Refs is only allowed when it does not refer to an
364 : : // existing transaction in either graph).
365 : 2688 : auto removed_pos = provider.ConsumeIntegralInRange<size_t>(0, sel_sim.removed.size() - 1);
366 [ + + ]: 2688 : if (removed_pos != sel_sim.removed.size() - 1) {
367 : 1181 : std::swap(sel_sim.removed[removed_pos], sel_sim.removed.back());
368 : : }
369 : 2688 : sel_sim.removed.pop_back();
370 : 2688 : break;
371 [ + + + + : 353810 : } else if (command-- == 0) {
+ + ]
372 : : // ~Ref (of any transaction).
373 : 11522 : std::vector<TxGraph::Ref*> to_destroy;
374 [ + - ]: 11522 : to_destroy.push_back(pick_fn());
375 : 12489 : while (true) {
376 : : // Keep adding either the ancestors or descendants the already picked
377 : : // transactions have in both graphs (main and staging) combined. Destroying
378 : : // will trigger deletions in both, so to have consistent TxGraph behavior, the
379 : : // set must be closed under ancestors, or descendants, in both graphs.
380 : 12489 : auto old_size = to_destroy.size();
381 [ + - + + ]: 28694 : for (auto& sim : sims) sim.IncludeAncDesc(to_destroy, alt);
382 [ + + ]: 12489 : if (to_destroy.size() == old_size) break;
383 : : }
384 : : // The order in which these ancestors/descendants are destroyed should not matter;
385 : : // randomly shuffle them.
386 : 11522 : std::shuffle(to_destroy.begin(), to_destroy.end(), rng);
387 [ + + ]: 26059 : for (TxGraph::Ref* ptr : to_destroy) {
388 [ + + ]: 34158 : for (size_t level = 0; level < sims.size(); ++level) {
389 : 19621 : sims[level].DestroyTransaction(ptr, level == sims.size() - 1);
390 : : }
391 : : }
392 : 11522 : break;
393 : 11522 : } else if (command-- == 0) {
394 : : // SetTransactionFee.
395 : 8816 : int64_t fee;
396 [ + + ]: 8816 : if (alt) {
397 : 2939 : fee = provider.ConsumeIntegralInRange<int64_t>(-0x8000000000000, 0x7ffffffffffff);
398 : : } else {
399 : 5877 : fee = provider.ConsumeIntegral<uint8_t>();
400 : : }
401 : 8816 : auto ref = pick_fn();
402 : 8816 : real->SetTransactionFee(*ref, fee);
403 [ + + ]: 23543 : for (auto& sim : sims) {
404 : 14727 : sim.SetTransactionFee(ref, fee);
405 : : }
406 : : break;
407 : : } else if (command-- == 0) {
408 : : // GetTransactionCount.
409 [ - + ]: 11090 : assert(real->GetTransactionCount(use_main) == sel_sim.GetTransactionCount());
410 : : break;
411 : : } else if (command-- == 0) {
412 : : // Exists.
413 : 13176 : auto ref = pick_fn();
414 : 13176 : bool exists = real->Exists(*ref, use_main);
415 : 13176 : bool should_exist = sel_sim.Find(ref) != SimTxGraph::MISSING;
416 [ - + ]: 13176 : assert(exists == should_exist);
417 : : break;
418 : : } else if (command-- == 0) {
419 : : // IsOversized.
420 [ - + ]: 20996 : assert(sel_sim.IsOversized() == real->IsOversized(use_main));
421 : : break;
422 [ + + ]: 288210 : } else if (command-- == 0) {
423 : : // GetIndividualFeerate.
424 : 5600 : auto ref = pick_fn();
425 : 5600 : auto feerate = real->GetIndividualFeerate(*ref);
426 : 5600 : bool found{false};
427 [ + + ]: 13111 : for (auto& sim : sims) {
428 : 7511 : auto simpos = sim.Find(ref);
429 [ + + ]: 7511 : if (simpos != SimTxGraph::MISSING) {
430 : 4171 : found = true;
431 [ + - ]: 11682 : assert(feerate == sim.graph.FeeRate(simpos));
432 : : }
433 : : }
434 [ + + - + ]: 5600 : if (!found) assert(feerate.IsEmpty());
435 : : break;
436 [ + + + + ]: 282610 : } else if (!main_sim.IsOversized() && command-- == 0) {
437 : : // GetMainChunkFeerate.
438 : 8739 : auto ref = pick_fn();
439 : 8739 : auto feerate = real->GetMainChunkFeerate(*ref);
440 : 8739 : auto simpos = main_sim.Find(ref);
441 [ + + ]: 8739 : if (simpos == SimTxGraph::MISSING) {
442 [ - + ]: 2247 : assert(feerate.IsEmpty());
443 : : } else {
444 : : // Just do some quick checks that the reported value is in range. A full
445 : : // recomputation of expected chunk feerates is done at the end.
446 [ - + ]: 6492 : assert(feerate.size >= main_sim.graph.FeeRate(simpos).size);
447 : : }
448 : : break;
449 [ + + + + ]: 273871 : } else if (!sel_sim.IsOversized() && command-- == 0) {
450 : : // GetAncestors/GetDescendants.
451 : 5326 : auto ref = pick_fn();
452 [ + + ]: 5326 : auto result = alt ? real->GetDescendants(*ref, use_main)
453 : 5326 : : real->GetAncestors(*ref, use_main);
454 [ - + ]: 5326 : assert(result.size() <= max_count);
455 : 5326 : auto result_set = sel_sim.MakeSet(result);
456 [ - + ]: 5326 : assert(result.size() == result_set.Count());
457 : 5326 : auto expect_set = sel_sim.GetAncDesc(ref, alt);
458 [ - + ]: 5326 : assert(result_set == expect_set);
459 : 5326 : break;
460 [ + + + + ]: 273871 : } else if (!sel_sim.IsOversized() && command-- == 0) {
461 : : // GetAncestorsUnion/GetDescendantsUnion.
462 : 4552 : std::vector<TxGraph::Ref*> refs;
463 : : // Gather a list of up to 15 Ref pointers.
464 : 4552 : auto count = provider.ConsumeIntegralInRange<size_t>(0, 15);
465 [ + - ]: 4552 : refs.resize(count);
466 [ + + ]: 29852 : for (size_t i = 0; i < count; ++i) {
467 : 25300 : refs[i] = pick_fn();
468 : : }
469 : : // Their order should not matter, shuffle them.
470 : 4552 : std::shuffle(refs.begin(), refs.end(), rng);
471 : : // Invoke the real function, and convert to SimPos set.
472 [ + + ]: 4552 : auto result = alt ? real->GetDescendantsUnion(refs, use_main)
473 : 4552 : : real->GetAncestorsUnion(refs, use_main);
474 : 4552 : auto result_set = sel_sim.MakeSet(result);
475 [ - + ]: 4552 : assert(result.size() == result_set.Count());
476 : : // Compute the expected result.
477 : 4552 : SimTxGraph::SetType expect_set;
478 [ + + ]: 29852 : for (TxGraph::Ref* ref : refs) expect_set |= sel_sim.GetAncDesc(ref, alt);
479 : : // Compare.
480 [ - + ]: 4552 : assert(result_set == expect_set);
481 : 4552 : break;
482 [ + + + + ]: 268545 : } else if (!sel_sim.IsOversized() && command-- == 0) {
483 : : // GetCluster.
484 : 4677 : auto ref = pick_fn();
485 : 4677 : auto result = real->GetCluster(*ref, use_main);
486 : : // Check cluster count limit.
487 [ - + ]: 4677 : assert(result.size() <= max_count);
488 : : // Require the result to be topologically valid and not contain duplicates.
489 : 4677 : auto left = sel_sim.graph.Positions();
490 [ + + ]: 15574 : for (auto refptr : result) {
491 : 10897 : auto simpos = sel_sim.Find(refptr);
492 [ - + ]: 10897 : assert(simpos != SimTxGraph::MISSING);
493 [ - + ]: 10897 : assert(left[simpos]);
494 : 10897 : left.Reset(simpos);
495 [ - + ]: 21794 : assert(!sel_sim.graph.Ancestors(simpos).Overlaps(left));
496 : : }
497 : : // Require the set to be connected.
498 : 4677 : auto result_set = sel_sim.MakeSet(result);
499 [ - + ]: 4677 : assert(sel_sim.graph.IsConnected(result_set));
500 : : // If ref exists, the result must contain it. If not, it must be empty.
501 : 4677 : auto simpos = sel_sim.Find(ref);
502 [ + + ]: 4677 : if (simpos != SimTxGraph::MISSING) {
503 [ - + ]: 2640 : assert(result_set[simpos]);
504 : : } else {
505 [ - + ]: 2037 : assert(result_set.None());
506 : : }
507 : : // Require the set not to have ancestors or descendants outside of it.
508 [ + + ]: 15574 : for (auto i : result_set) {
509 [ - + ]: 21794 : assert(sel_sim.graph.Ancestors(i).IsSubsetOf(result_set));
510 [ - + ]: 10897 : assert(sel_sim.graph.Descendants(i).IsSubsetOf(result_set));
511 : : }
512 : 4677 : break;
513 [ + + ]: 263993 : } else if (command-- == 0) {
514 : : // HaveStaging.
515 [ - + ]: 12113 : assert((sims.size() == 2) == real->HaveStaging());
516 : : break;
517 [ + + + + ]: 247203 : } else if (sims.size() < 2 && command-- == 0) {
518 : : // StartStaging.
519 [ + - ]: 7111 : sims.emplace_back(sims.back());
520 : 7111 : real->StartStaging();
521 : 7111 : break;
522 [ + + + + ]: 240092 : } else if (sims.size() > 1 && command-- == 0) {
523 : : // CommitStaging.
524 : 5290 : real->CommitStaging();
525 : 5290 : sims.erase(sims.begin());
526 : : break;
527 [ + + + + ]: 234802 : } else if (sims.size() > 1 && command-- == 0) {
528 : : // AbortStaging.
529 : 931 : real->AbortStaging();
530 : 931 : sims.pop_back();
531 : : // Reset the cached oversized value (if TxGraph::Ref destructions triggered
532 : : // removals of main transactions while staging was active, then aborting will
533 : : // cause it to be re-evaluated in TxGraph).
534 [ + - ]: 274634 : sims.back().oversized = std::nullopt;
535 : : break;
536 [ + + + + ]: 233871 : } else if (!main_sim.IsOversized() && command-- == 0) {
537 : : // CompareMainOrder.
538 : 5932 : auto ref_a = pick_fn();
539 : 5932 : auto ref_b = pick_fn();
540 : 5932 : auto sim_a = main_sim.Find(ref_a);
541 : 5932 : auto sim_b = main_sim.Find(ref_b);
542 : : // Both transactions must exist in the main graph.
543 [ + + ]: 5932 : if (sim_a == SimTxGraph::MISSING || sim_b == SimTxGraph::MISSING) break;
544 : 3933 : auto cmp = real->CompareMainOrder(*ref_a, *ref_b);
545 : : // Distinct transactions have distinct places.
546 [ + + - + ]: 3933 : if (sim_a != sim_b) assert(cmp != 0);
547 : : // Ancestors go before descendants.
548 [ + + - + ]: 3933 : if (main_sim.graph.Ancestors(sim_a)[sim_b]) assert(cmp >= 0);
549 [ + + - + ]: 3933 : if (main_sim.graph.Descendants(sim_a)[sim_b]) assert(cmp <= 0);
550 : : // Do not verify consistency with chunk feerates, as we cannot easily determine
551 : : // these here without making more calls to real, which could affect its internal
552 : : // state. A full comparison is done at the end.
553 : : break;
554 [ + + + + ]: 227939 : } else if (!sel_sim.IsOversized() && command-- == 0) {
555 : : // CountDistinctClusters.
556 : 3991 : std::vector<TxGraph::Ref*> refs;
557 : : // Gather a list of up to 15 (or up to 255) Ref pointers.
558 [ + + ]: 7318 : auto count = provider.ConsumeIntegralInRange<size_t>(0, alt ? 255 : 15);
559 [ + - ]: 3991 : refs.resize(count);
560 [ + + ]: 57358 : for (size_t i = 0; i < count; ++i) {
561 : 53367 : refs[i] = pick_fn();
562 : : }
563 : : // Their order should not matter, shuffle them.
564 : 3991 : std::shuffle(refs.begin(), refs.end(), rng);
565 : : // Invoke the real function.
566 : 3991 : auto result = real->CountDistinctClusters(refs, use_main);
567 : : // Build a set with representatives of the clusters the Refs occur in in the
568 : : // simulated graph. For each, remember the lowest-index transaction SimPos in the
569 : : // cluster.
570 : 3991 : SimTxGraph::SetType sim_reps;
571 [ + + ]: 57358 : for (auto ref : refs) {
572 : : // Skip Refs that do not occur in the simulated graph.
573 : 53367 : auto simpos = sel_sim.Find(ref);
574 [ + + ]: 53367 : if (simpos == SimTxGraph::MISSING) continue;
575 : : // Find the component that includes ref.
576 : 42749 : auto component = sel_sim.graph.GetConnectedComponent(sel_sim.graph.Positions(), simpos);
577 : : // Remember the lowest-index SimPos in component, as a representative for it.
578 [ - + ]: 85498 : assert(component.Any());
579 : 42749 : sim_reps.Set(component.First());
580 : : }
581 : : // Compare the number of deduplicated representatives with the value returned by
582 : : // the real function.
583 [ - + ]: 3991 : assert(result == sim_reps.Count());
584 : 3991 : break;
585 [ + + ]: 227939 : } else if (command-- == 0) {
586 : : // DoWork.
587 : 6769 : real->DoWork();
588 : 6769 : break;
589 : : }
590 : : }
591 : : }
592 : :
593 : : // After running all modifications, perform an internal sanity check (before invoking
594 : : // inspectors that may modify the internal state).
595 [ + - ]: 2258 : real->SanityCheck();
596 : :
597 [ + + ]: 2258 : if (!sims[0].IsOversized()) {
598 : : // If the main graph is not oversized, verify the total ordering implied by
599 : : // CompareMainOrder.
600 : : // First construct two distinct randomized permutations of the positions in sims[0].
601 : 1896 : std::vector<SimTxGraph::Pos> vec1;
602 [ + - + + ]: 42184 : for (auto i : sims[0].graph.Positions()) vec1.push_back(i);
603 : 1896 : std::shuffle(vec1.begin(), vec1.end(), rng);
604 [ + - ]: 1896 : auto vec2 = vec1;
605 : 1896 : std::shuffle(vec2.begin(), vec2.end(), rng);
606 [ + + ]: 1896 : if (vec1 == vec2) std::next_permutation(vec2.begin(), vec2.end());
607 : : // Sort both according to CompareMainOrder. By having randomized starting points, the order
608 : : // of CompareMainOrder invocations is somewhat randomized as well.
609 : 497740 : auto cmp = [&](SimTxGraph::Pos a, SimTxGraph::Pos b) noexcept {
610 : 495844 : return real->CompareMainOrder(*sims[0].GetRef(a), *sims[0].GetRef(b)) < 0;
611 : 1896 : };
612 : 1896 : std::sort(vec1.begin(), vec1.end(), cmp);
613 : 1896 : std::sort(vec2.begin(), vec2.end(), cmp);
614 : :
615 : : // Verify the resulting orderings are identical. This could only fail if the ordering was
616 : : // not total.
617 [ - + ]: 1896 : assert(vec1 == vec2);
618 : :
619 : : // Verify that the ordering is topological.
620 : 1896 : auto todo = sims[0].graph.Positions();
621 [ + + ]: 42184 : for (auto i : vec1) {
622 : 40288 : todo.Reset(i);
623 [ - + ]: 80576 : assert(!sims[0].graph.Ancestors(i).Overlaps(todo));
624 : : }
625 [ - + ]: 1896 : assert(todo.None());
626 : :
627 : : // For every transaction in the total ordering, find a random one before it and after it,
628 : : // and compare their chunk feerates, which must be consistent with the ordering.
629 [ + + ]: 42184 : for (size_t pos = 0; pos < vec1.size(); ++pos) {
630 : 40288 : auto pos_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[pos]));
631 [ + + ]: 40288 : if (pos > 0) {
632 : 38521 : size_t before = rng.randrange<size_t>(pos);
633 : 38521 : auto before_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[before]));
634 [ - + ]: 38521 : assert(FeeRateCompare(before_feerate, pos_feerate) >= 0);
635 : : }
636 [ + + ]: 40288 : if (pos + 1 < vec1.size()) {
637 : 38521 : size_t after = pos + 1 + rng.randrange<size_t>(vec1.size() - 1 - pos);
638 : 38521 : auto after_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[after]));
639 [ - + ]: 38521 : assert(FeeRateCompare(after_feerate, pos_feerate) <= 0);
640 : : }
641 : : }
642 : 1896 : }
643 : :
644 [ - + ]: 2258 : assert(real->HaveStaging() == (sims.size() > 1));
645 : :
646 : : // Try to run a full comparison, for both main_only=false and main_only=true in TxGraph
647 : : // inspector functions that support both.
648 [ + + ]: 6774 : for (int main_only = 0; main_only < 2; ++main_only) {
649 [ + + ]: 4516 : auto& sim = main_only ? sims[0] : sims.back();
650 : : // Compare simple properties of the graph with the simulation.
651 [ - + ]: 4516 : assert(real->IsOversized(main_only) == sim.IsOversized());
652 [ - + ]: 4516 : assert(real->GetTransactionCount(main_only) == sim.GetTransactionCount());
653 : : // If the graph (and the simulation) are not oversized, perform a full comparison.
654 [ + + ]: 4516 : if (!sim.IsOversized()) {
655 : 3786 : auto todo = sim.graph.Positions();
656 : : // Iterate over all connected components of the resulting (simulated) graph, each of which
657 : : // should correspond to a cluster in the real one.
658 [ + + ]: 140788 : while (todo.Any()) {
659 : 66608 : auto component = sim.graph.FindConnectedComponent(todo);
660 : 66608 : todo -= component;
661 : : // Iterate over the transactions in that component.
662 [ + + ]: 152394 : for (auto i : component) {
663 : : // Check its individual feerate against simulation.
664 [ + - ]: 85786 : assert(sim.graph.FeeRate(i) == real->GetIndividualFeerate(*sim.GetRef(i)));
665 : : // Check its ancestors against simulation.
666 : 85786 : auto expect_anc = sim.graph.Ancestors(i);
667 : 85786 : auto anc = sim.MakeSet(real->GetAncestors(*sim.GetRef(i), main_only));
668 [ - + ]: 85786 : assert(anc.Count() <= max_count);
669 [ - + ]: 85786 : assert(anc == expect_anc);
670 : : // Check its descendants against simulation.
671 : 85786 : auto expect_desc = sim.graph.Descendants(i);
672 : 85786 : auto desc = sim.MakeSet(real->GetDescendants(*sim.GetRef(i), main_only));
673 [ - + ]: 85786 : assert(desc.Count() <= max_count);
674 [ - + ]: 85786 : assert(desc == expect_desc);
675 : : // Check the cluster the transaction is part of.
676 : 85786 : auto cluster = real->GetCluster(*sim.GetRef(i), main_only);
677 [ - + ]: 85786 : assert(cluster.size() <= max_count);
678 [ - + ]: 85786 : assert(sim.MakeSet(cluster) == component);
679 : : // Check that the cluster is reported in a valid topological order (its
680 : : // linearization).
681 : 85786 : std::vector<DepGraphIndex> simlin;
682 : 85786 : SimTxGraph::SetType done;
683 [ + + ]: 563278 : for (TxGraph::Ref* ptr : cluster) {
684 : 477492 : auto simpos = sim.Find(ptr);
685 [ - + ]: 954984 : assert(sim.graph.Descendants(simpos).IsSubsetOf(component - done));
686 : 477492 : done.Set(simpos);
687 [ - + ]: 954984 : assert(sim.graph.Ancestors(simpos).IsSubsetOf(done));
688 [ + - ]: 477492 : simlin.push_back(simpos);
689 : : }
690 : : // Construct a chunking object for the simulated graph, using the reported cluster
691 : : // linearization as ordering, and compare it against the reported chunk feerates.
692 [ + + + + ]: 85786 : if (sims.size() == 1 || main_only) {
693 : 66481 : cluster_linearize::LinearizationChunking simlinchunk(sim.graph, simlin);
694 : 66481 : DepGraphIndex idx{0};
695 [ + + ]: 313594 : for (unsigned chunknum = 0; chunknum < simlinchunk.NumChunksLeft(); ++chunknum) {
696 : 247113 : auto chunk = simlinchunk.GetChunk(chunknum);
697 : : // Require that the chunks of cluster linearizations are connected (this must
698 : : // be the case as all linearizations inside are PostLinearized).
699 [ - + ]: 247113 : assert(sim.graph.IsConnected(chunk.transactions));
700 : : // Check the chunk feerates of all transactions in the cluster.
701 [ + + ]: 1274436 : while (chunk.transactions.Any()) {
702 [ - + ]: 390105 : assert(chunk.transactions[simlin[idx]]);
703 : 390105 : chunk.transactions.Reset(simlin[idx]);
704 [ + - ]: 390105 : assert(chunk.feerate == real->GetMainChunkFeerate(*cluster[idx]));
705 : 390105 : ++idx;
706 : : }
707 : : }
708 : 66481 : }
709 : 85786 : }
710 : : }
711 : : }
712 : : }
713 : :
714 : : // Sanity check again (because invoking inspectors may modify internal unobservable state).
715 [ + - ]: 2258 : real->SanityCheck();
716 : :
717 : : // Kill the TxGraph object.
718 [ + - ]: 2258 : real.reset();
719 : : // Kill the simulated graphs, with all remaining Refs in it. If any, this verifies that Refs
720 : : // can outlive the TxGraph that created them.
721 : 2258 : sims.clear();
722 : 2258 : }
|
