Bitcoin Core 29.99.0
P2P Digital Currency
txgraph.cpp
Go to the documentation of this file.
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>
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
20using namespace cluster_linearize;
21
22namespace {
23
27struct SimTxGraph
28{
32 static constexpr unsigned MAX_TRANSACTIONS = MAX_CLUSTER_COUNT_LIMIT * 2;
34 using SetType = BitSet<MAX_TRANSACTIONS>;
36 using Pos = DepGraphIndex;
38 static constexpr auto MISSING = Pos(-1);
39
46 std::array<std::shared_ptr<TxGraph::Ref>, MAX_TRANSACTIONS> simmap;
48 std::map<const TxGraph::Ref*, Pos> simrevmap;
50 std::vector<std::shared_ptr<TxGraph::Ref>> removed;
52 std::optional<bool> oversized;
54 DepGraphIndex max_cluster_count;
55
57 explicit SimTxGraph(DepGraphIndex max_cluster) : max_cluster_count(max_cluster) {}
58
59 // Permit copying and moving.
60 SimTxGraph(const SimTxGraph&) noexcept = default;
61 SimTxGraph& operator=(const SimTxGraph&) noexcept = default;
62 SimTxGraph(SimTxGraph&&) noexcept = default;
63 SimTxGraph& operator=(SimTxGraph&&) noexcept = default;
64
67 bool IsOversized()
68 {
69 if (!oversized.has_value()) {
70 // Only recompute when oversized isn't already known.
71 oversized = false;
72 auto todo = graph.Positions();
73 // Iterate over all connected components of the graph.
74 while (todo.Any()) {
75 auto component = graph.FindConnectedComponent(todo);
76 if (component.Count() > max_cluster_count) oversized = true;
77 todo -= component;
78 }
79 }
80 return *oversized;
81 }
82
84 DepGraphIndex GetTransactionCount() const { return graph.TxCount(); }
85
87 Pos Find(const TxGraph::Ref* ref) const
88 {
89 auto it = simrevmap.find(ref);
90 if (it != simrevmap.end()) return it->second;
91 return MISSING;
92 }
93
95 TxGraph::Ref* GetRef(Pos pos)
96 {
97 assert(graph.Positions()[pos]);
98 assert(simmap[pos]);
99 return simmap[pos].get();
100 }
101
103 TxGraph::Ref* AddTransaction(const FeePerWeight& feerate)
104 {
105 assert(graph.TxCount() < MAX_TRANSACTIONS);
106 auto simpos = graph.AddTransaction(feerate);
107 assert(graph.Positions()[simpos]);
108 simmap[simpos] = std::make_shared<TxGraph::Ref>();
109 auto ptr = simmap[simpos].get();
110 simrevmap[ptr] = simpos;
111 return ptr;
112 }
113
115 void AddDependency(TxGraph::Ref* parent, TxGraph::Ref* child)
116 {
117 auto par_pos = Find(parent);
118 if (par_pos == MISSING) return;
119 auto chl_pos = Find(child);
120 if (chl_pos == MISSING) return;
121 graph.AddDependencies(SetType::Singleton(par_pos), chl_pos);
122 // This may invalidate our cached oversized value.
123 if (oversized.has_value() && !*oversized) oversized = std::nullopt;
124 }
125
127 void SetTransactionFee(TxGraph::Ref* ref, int64_t fee)
128 {
129 auto pos = Find(ref);
130 if (pos == MISSING) return;
131 graph.FeeRate(pos).fee = fee;
132 }
133
135 void RemoveTransaction(TxGraph::Ref* ref)
136 {
137 auto pos = Find(ref);
138 if (pos == MISSING) return;
139 graph.RemoveTransactions(SetType::Singleton(pos));
140 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 removed.push_back(std::move(simmap[pos]));
144 simmap[pos].reset();
145 // This may invalidate our cached oversized value.
146 if (oversized.has_value() && *oversized) oversized = std::nullopt;
147 }
148
153 void DestroyTransaction(TxGraph::Ref* ref, bool reset_oversize)
154 {
155 auto pos = Find(ref);
156 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 auto remove = std::partition(removed.begin(), removed.end(), [&](auto& arg) { return arg.get() != ref; });
161 removed.erase(remove, removed.end());
162 } else {
163 graph.RemoveTransactions(SetType::Singleton(pos));
164 simrevmap.erase(simmap[pos].get());
165 simmap[pos].reset();
166 // This may invalidate our cached oversized value.
167 if (reset_oversize && oversized.has_value() && *oversized) {
168 oversized = std::nullopt;
169 }
170 }
171 }
172
175 SetType MakeSet(std::span<TxGraph::Ref* const> arg)
176 {
177 SetType ret;
178 for (TxGraph::Ref* ptr : arg) {
179 auto pos = Find(ptr);
180 assert(pos != Pos(-1));
181 ret.Set(pos);
182 }
183 return ret;
184 }
185
187 SetType GetAncDesc(TxGraph::Ref* arg, bool desc)
188 {
189 auto pos = Find(arg);
190 if (pos == MISSING) return {};
191 return desc ? graph.Descendants(pos) : graph.Ancestors(pos);
192 }
193
196 void IncludeAncDesc(std::vector<TxGraph::Ref*>& arg, bool desc)
197 {
198 std::vector<TxGraph::Ref*> ret;
199 for (auto ptr : arg) {
200 auto simpos = Find(ptr);
201 if (simpos != MISSING) {
202 for (auto i : desc ? graph.Descendants(simpos) : graph.Ancestors(simpos)) {
203 ret.push_back(simmap[i].get());
204 }
205 } else {
206 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 arg.clear();
212 for (auto ptr : ret) {
213 if (std::find(arg.begin(), arg.end(), ptr) == arg.end()) {
214 arg.push_back(ptr);
215 }
216 }
217 }
218};
219
220} // namespace
221
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
230 FuzzedDataProvider provider(buffer.data(), buffer.size());
231
234 InsecureRandomContext rng(0xdecade2009added + buffer.size());
235
237 TxGraph::Ref empty_ref;
238
239 // Decide the maximum number of transactions per cluster we will use in this simulation.
240 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 auto real = MakeTxGraph(max_count);
244 std::vector<SimTxGraph> sims;
245 sims.reserve(2);
246 sims.emplace_back(max_count);
247
250 auto pick_fn = [&]() noexcept -> TxGraph::Ref* {
251 size_t tx_count[2] = {sims[0].GetTransactionCount(), 0};
253 size_t choices = tx_count[0] + sims[0].removed.size() + 1;
254 if (sims.size() == 2) {
255 tx_count[1] = sims[1].GetTransactionCount();
256 choices += tx_count[1] + sims[1].removed.size();
257 }
259 auto choice = provider.ConsumeIntegralInRange<size_t>(0, choices - 1);
260 // Consider both main and (if it exists) staging.
261 for (size_t level = 0; level < sims.size(); ++level) {
262 auto& sim = sims[level];
263 if (choice < tx_count[level]) {
264 // Return from graph.
265 for (auto i : sim.graph.Positions()) {
266 if (choice == 0) return sim.GetRef(i);
267 --choice;
268 }
269 assert(false);
270 } else {
271 choice -= tx_count[level];
272 }
273 if (choice < sim.removed.size()) {
274 // Return from removed.
275 return sim.removed[choice].get();
276 } else {
277 choice -= sim.removed.size();
278 }
279 }
280 // Return empty.
281 assert(choice == 0);
282 return &empty_ref;
283 };
284
285 LIMITED_WHILE(provider.remaining_bytes() > 0, 200) {
286 // Read a one-byte command.
287 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 bool alt = command & 1;
292 bool use_main = command & 2;
293 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 auto& top_sim = sims.back();
299 auto& sel_sim = use_main ? sims[0] : top_sim;
300 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 while (true) {
305 if (top_sim.GetTransactionCount() < SimTxGraph::MAX_TRANSACTIONS && command-- == 0) {
306 // AddTransaction.
307 int64_t fee;
308 int32_t size;
309 if (alt) {
310 // If alt is true, pick fee and size from the entire range.
311 fee = provider.ConsumeIntegralInRange<int64_t>(-0x8000000000000, 0x7ffffffffffff);
312 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 fee = provider.ConsumeIntegral<uint8_t>();
317 size = provider.ConsumeIntegral<uint8_t>() + 1;
318 }
319 FeePerWeight feerate{fee, size};
320 // Create a real TxGraph::Ref.
321 auto ref = real->AddTransaction(feerate);
322 // Create a shared_ptr place in the simulation to put the Ref in.
323 auto ref_loc = top_sim.AddTransaction(feerate);
324 // Move it in place.
325 *ref_loc = std::move(ref);
326 break;
327 } else if (top_sim.GetTransactionCount() + top_sim.removed.size() > 1 && command-- == 0) {
328 // AddDependency.
329 auto par = pick_fn();
330 auto chl = pick_fn();
331 auto pos_par = top_sim.Find(par);
332 auto pos_chl = top_sim.Find(chl);
333 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 if (top_sim.graph.Ancestors(pos_par)[pos_chl]) break;
337 }
338 top_sim.AddDependency(par, chl);
339 real->AddDependency(*par, *chl);
340 break;
341 } 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 std::vector<TxGraph::Ref*> to_remove;
346 to_remove.push_back(pick_fn());
347 top_sim.IncludeAncDesc(to_remove, alt);
348 // The order in which these ancestors/descendants are removed should not matter;
349 // randomly shuffle them.
350 std::shuffle(to_remove.begin(), to_remove.end(), rng);
351 for (TxGraph::Ref* ptr : to_remove) {
352 real->RemoveTransaction(*ptr);
353 top_sim.RemoveTransaction(ptr);
354 }
355 break;
356 } 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 auto removed_pos = provider.ConsumeIntegralInRange<size_t>(0, sel_sim.removed.size() - 1);
366 if (removed_pos != sel_sim.removed.size() - 1) {
367 std::swap(sel_sim.removed[removed_pos], sel_sim.removed.back());
368 }
369 sel_sim.removed.pop_back();
370 break;
371 } else if (command-- == 0) {
372 // ~Ref (of any transaction).
373 std::vector<TxGraph::Ref*> to_destroy;
374 to_destroy.push_back(pick_fn());
375 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 auto old_size = to_destroy.size();
381 for (auto& sim : sims) sim.IncludeAncDesc(to_destroy, alt);
382 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 std::shuffle(to_destroy.begin(), to_destroy.end(), rng);
387 for (TxGraph::Ref* ptr : to_destroy) {
388 for (size_t level = 0; level < sims.size(); ++level) {
389 sims[level].DestroyTransaction(ptr, level == sims.size() - 1);
390 }
391 }
392 break;
393 } else if (command-- == 0) {
394 // SetTransactionFee.
395 int64_t fee;
396 if (alt) {
397 fee = provider.ConsumeIntegralInRange<int64_t>(-0x8000000000000, 0x7ffffffffffff);
398 } else {
399 fee = provider.ConsumeIntegral<uint8_t>();
400 }
401 auto ref = pick_fn();
402 real->SetTransactionFee(*ref, fee);
403 for (auto& sim : sims) {
404 sim.SetTransactionFee(ref, fee);
405 }
406 break;
407 } else if (command-- == 0) {
408 // GetTransactionCount.
409 assert(real->GetTransactionCount(use_main) == sel_sim.GetTransactionCount());
410 break;
411 } else if (command-- == 0) {
412 // Exists.
413 auto ref = pick_fn();
414 bool exists = real->Exists(*ref, use_main);
415 bool should_exist = sel_sim.Find(ref) != SimTxGraph::MISSING;
416 assert(exists == should_exist);
417 break;
418 } else if (command-- == 0) {
419 // IsOversized.
420 assert(sel_sim.IsOversized() == real->IsOversized(use_main));
421 break;
422 } else if (command-- == 0) {
423 // GetIndividualFeerate.
424 auto ref = pick_fn();
425 auto feerate = real->GetIndividualFeerate(*ref);
426 bool found{false};
427 for (auto& sim : sims) {
428 auto simpos = sim.Find(ref);
429 if (simpos != SimTxGraph::MISSING) {
430 found = true;
431 assert(feerate == sim.graph.FeeRate(simpos));
432 }
433 }
434 if (!found) assert(feerate.IsEmpty());
435 break;
436 } else if (!main_sim.IsOversized() && command-- == 0) {
437 // GetMainChunkFeerate.
438 auto ref = pick_fn();
439 auto feerate = real->GetMainChunkFeerate(*ref);
440 auto simpos = main_sim.Find(ref);
441 if (simpos == SimTxGraph::MISSING) {
442 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 assert(feerate.size >= main_sim.graph.FeeRate(simpos).size);
447 }
448 break;
449 } else if (!sel_sim.IsOversized() && command-- == 0) {
450 // GetAncestors/GetDescendants.
451 auto ref = pick_fn();
452 auto result = alt ? real->GetDescendants(*ref, use_main)
453 : real->GetAncestors(*ref, use_main);
454 assert(result.size() <= max_count);
455 auto result_set = sel_sim.MakeSet(result);
456 assert(result.size() == result_set.Count());
457 auto expect_set = sel_sim.GetAncDesc(ref, alt);
458 assert(result_set == expect_set);
459 break;
460 } else if (!sel_sim.IsOversized() && command-- == 0) {
461 // GetAncestorsUnion/GetDescendantsUnion.
462 std::vector<TxGraph::Ref*> refs;
463 // Gather a list of up to 15 Ref pointers.
464 auto count = provider.ConsumeIntegralInRange<size_t>(0, 15);
465 refs.resize(count);
466 for (size_t i = 0; i < count; ++i) {
467 refs[i] = pick_fn();
468 }
469 // Their order should not matter, shuffle them.
470 std::shuffle(refs.begin(), refs.end(), rng);
471 // Invoke the real function, and convert to SimPos set.
472 auto result = alt ? real->GetDescendantsUnion(refs, use_main)
473 : real->GetAncestorsUnion(refs, use_main);
474 auto result_set = sel_sim.MakeSet(result);
475 assert(result.size() == result_set.Count());
476 // Compute the expected result.
477 SimTxGraph::SetType expect_set;
478 for (TxGraph::Ref* ref : refs) expect_set |= sel_sim.GetAncDesc(ref, alt);
479 // Compare.
480 assert(result_set == expect_set);
481 break;
482 } else if (!sel_sim.IsOversized() && command-- == 0) {
483 // GetCluster.
484 auto ref = pick_fn();
485 auto result = real->GetCluster(*ref, use_main);
486 // Check cluster count limit.
487 assert(result.size() <= max_count);
488 // Require the result to be topologically valid and not contain duplicates.
489 auto left = sel_sim.graph.Positions();
490 for (auto refptr : result) {
491 auto simpos = sel_sim.Find(refptr);
492 assert(simpos != SimTxGraph::MISSING);
493 assert(left[simpos]);
494 left.Reset(simpos);
495 assert(!sel_sim.graph.Ancestors(simpos).Overlaps(left));
496 }
497 // Require the set to be connected.
498 auto result_set = sel_sim.MakeSet(result);
499 assert(sel_sim.graph.IsConnected(result_set));
500 // If ref exists, the result must contain it. If not, it must be empty.
501 auto simpos = sel_sim.Find(ref);
502 if (simpos != SimTxGraph::MISSING) {
503 assert(result_set[simpos]);
504 } else {
505 assert(result_set.None());
506 }
507 // Require the set not to have ancestors or descendants outside of it.
508 for (auto i : result_set) {
509 assert(sel_sim.graph.Ancestors(i).IsSubsetOf(result_set));
510 assert(sel_sim.graph.Descendants(i).IsSubsetOf(result_set));
511 }
512 break;
513 } else if (command-- == 0) {
514 // HaveStaging.
515 assert((sims.size() == 2) == real->HaveStaging());
516 break;
517 } else if (sims.size() < 2 && command-- == 0) {
518 // StartStaging.
519 sims.emplace_back(sims.back());
520 real->StartStaging();
521 break;
522 } else if (sims.size() > 1 && command-- == 0) {
523 // CommitStaging.
524 real->CommitStaging();
525 sims.erase(sims.begin());
526 break;
527 } else if (sims.size() > 1 && command-- == 0) {
528 // AbortStaging.
529 real->AbortStaging();
530 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 sims.back().oversized = std::nullopt;
535 break;
536 } else if (!main_sim.IsOversized() && command-- == 0) {
537 // CompareMainOrder.
538 auto ref_a = pick_fn();
539 auto ref_b = pick_fn();
540 auto sim_a = main_sim.Find(ref_a);
541 auto sim_b = main_sim.Find(ref_b);
542 // Both transactions must exist in the main graph.
543 if (sim_a == SimTxGraph::MISSING || sim_b == SimTxGraph::MISSING) break;
544 auto cmp = real->CompareMainOrder(*ref_a, *ref_b);
545 // Distinct transactions have distinct places.
546 if (sim_a != sim_b) assert(cmp != 0);
547 // Ancestors go before descendants.
548 if (main_sim.graph.Ancestors(sim_a)[sim_b]) assert(cmp >= 0);
549 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 } else if (!sel_sim.IsOversized() && command-- == 0) {
555 // CountDistinctClusters.
556 std::vector<TxGraph::Ref*> refs;
557 // Gather a list of up to 15 (or up to 255) Ref pointers.
558 auto count = provider.ConsumeIntegralInRange<size_t>(0, alt ? 255 : 15);
559 refs.resize(count);
560 for (size_t i = 0; i < count; ++i) {
561 refs[i] = pick_fn();
562 }
563 // Their order should not matter, shuffle them.
564 std::shuffle(refs.begin(), refs.end(), rng);
565 // Invoke the real function.
566 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 SimTxGraph::SetType sim_reps;
571 for (auto ref : refs) {
572 // Skip Refs that do not occur in the simulated graph.
573 auto simpos = sel_sim.Find(ref);
574 if (simpos == SimTxGraph::MISSING) continue;
575 // Find the component that includes ref.
576 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 assert(component.Any());
579 sim_reps.Set(component.First());
580 }
581 // Compare the number of deduplicated representatives with the value returned by
582 // the real function.
583 assert(result == sim_reps.Count());
584 break;
585 } else if (command-- == 0) {
586 // DoWork.
587 real->DoWork();
588 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 real->SanityCheck();
596
597 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 std::vector<SimTxGraph::Pos> vec1;
602 for (auto i : sims[0].graph.Positions()) vec1.push_back(i);
603 std::shuffle(vec1.begin(), vec1.end(), rng);
604 auto vec2 = vec1;
605 std::shuffle(vec2.begin(), vec2.end(), rng);
606 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 auto cmp = [&](SimTxGraph::Pos a, SimTxGraph::Pos b) noexcept {
610 return real->CompareMainOrder(*sims[0].GetRef(a), *sims[0].GetRef(b)) < 0;
611 };
612 std::sort(vec1.begin(), vec1.end(), cmp);
613 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 assert(vec1 == vec2);
618
619 // Verify that the ordering is topological.
620 auto todo = sims[0].graph.Positions();
621 for (auto i : vec1) {
622 todo.Reset(i);
623 assert(!sims[0].graph.Ancestors(i).Overlaps(todo));
624 }
625 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 for (size_t pos = 0; pos < vec1.size(); ++pos) {
630 auto pos_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[pos]));
631 if (pos > 0) {
632 size_t before = rng.randrange<size_t>(pos);
633 auto before_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[before]));
634 assert(FeeRateCompare(before_feerate, pos_feerate) >= 0);
635 }
636 if (pos + 1 < vec1.size()) {
637 size_t after = pos + 1 + rng.randrange<size_t>(vec1.size() - 1 - pos);
638 auto after_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[after]));
639 assert(FeeRateCompare(after_feerate, pos_feerate) <= 0);
640 }
641 }
642 }
643
644 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 for (int main_only = 0; main_only < 2; ++main_only) {
649 auto& sim = main_only ? sims[0] : sims.back();
650 // Compare simple properties of the graph with the simulation.
651 assert(real->IsOversized(main_only) == sim.IsOversized());
652 assert(real->GetTransactionCount(main_only) == sim.GetTransactionCount());
653 // If the graph (and the simulation) are not oversized, perform a full comparison.
654 if (!sim.IsOversized()) {
655 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 while (todo.Any()) {
659 auto component = sim.graph.FindConnectedComponent(todo);
660 todo -= component;
661 // Iterate over the transactions in that component.
662 for (auto i : component) {
663 // Check its individual feerate against simulation.
664 assert(sim.graph.FeeRate(i) == real->GetIndividualFeerate(*sim.GetRef(i)));
665 // Check its ancestors against simulation.
666 auto expect_anc = sim.graph.Ancestors(i);
667 auto anc = sim.MakeSet(real->GetAncestors(*sim.GetRef(i), main_only));
668 assert(anc.Count() <= max_count);
669 assert(anc == expect_anc);
670 // Check its descendants against simulation.
671 auto expect_desc = sim.graph.Descendants(i);
672 auto desc = sim.MakeSet(real->GetDescendants(*sim.GetRef(i), main_only));
673 assert(desc.Count() <= max_count);
674 assert(desc == expect_desc);
675 // Check the cluster the transaction is part of.
676 auto cluster = real->GetCluster(*sim.GetRef(i), main_only);
677 assert(cluster.size() <= max_count);
678 assert(sim.MakeSet(cluster) == component);
679 // Check that the cluster is reported in a valid topological order (its
680 // linearization).
681 std::vector<DepGraphIndex> simlin;
682 SimTxGraph::SetType done;
683 for (TxGraph::Ref* ptr : cluster) {
684 auto simpos = sim.Find(ptr);
685 assert(sim.graph.Descendants(simpos).IsSubsetOf(component - done));
686 done.Set(simpos);
687 assert(sim.graph.Ancestors(simpos).IsSubsetOf(done));
688 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 if (sims.size() == 1 || main_only) {
693 cluster_linearize::LinearizationChunking simlinchunk(sim.graph, simlin);
694 DepGraphIndex idx{0};
695 for (unsigned chunknum = 0; chunknum < simlinchunk.NumChunksLeft(); ++chunknum) {
696 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 assert(sim.graph.IsConnected(chunk.transactions));
700 // Check the chunk feerates of all transactions in the cluster.
701 while (chunk.transactions.Any()) {
702 assert(chunk.transactions[simlin[idx]]);
703 chunk.transactions.Reset(simlin[idx]);
704 assert(chunk.feerate == real->GetMainChunkFeerate(*cluster[idx]));
705 ++idx;
706 }
707 }
708 }
709 }
710 }
711 }
712 }
713
714 // Sanity check again (because invoking inspectors may modify internal unobservable state).
715 real->SanityCheck();
716
717 // Kill the TxGraph object.
718 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 sims.clear();
722}
int ret
const auto command
std::conditional_t<(BITS<=32), bitset_detail::IntBitSet< uint32_t >, std::conditional_t<(BITS<=std::numeric_limits< size_t >::digits), bitset_detail::IntBitSet< size_t >, bitset_detail::MultiIntBitSet< size_t,(BITS+std::numeric_limits< size_t >::digits - 1)/std::numeric_limits< size_t >::digits > > > BitSet
Definition: bitset.h:525
T ConsumeIntegralInRange(T min, T max)
xoroshiro128++ PRNG.
Definition: random.h:416
I randrange(I range) noexcept
Generate a random integer in the range [0..range), with range > 0.
Definition: random.h:254
Data structure that holds a transaction graph's preprocessed data (fee, size, ancestors,...
const SetType & Ancestors(DepGraphIndex i) const noexcept
Get the ancestors of a given transaction i.
const FeeFrac & FeeRate(DepGraphIndex i) const noexcept
Get the feerate of a given transaction i.
SetType FindConnectedComponent(const SetType &todo) const noexcept
Find some connected component within the subset "todo" of this graph.
DepGraphIndex AddTransaction(const FeeFrac &feefrac) noexcept
Add a new unconnected transaction to this transaction graph (in the first available position),...
void RemoveTransactions(const SetType &del) noexcept
Remove the specified positions from this DepGraph.
auto TxCount() const noexcept
Get the number of transactions in the graph.
const SetType & Descendants(DepGraphIndex i) const noexcept
Get the descendants of a given transaction i.
const SetType & Positions() const noexcept
Get the set of transactions positions in use.
void AddDependencies(const SetType &parents, DepGraphIndex child) noexcept
Modify this transaction graph, adding multiple parents to a specified child.
Data structure encapsulating the chunking of a linearization, permitting removal of subsets.
DepGraphIndex NumChunksLeft() const noexcept
Determine how many chunks remain in the linearization.
const SetInfo< SetType > & GetChunk(DepGraphIndex n) const noexcept
Access a chunk.
constexpr MaybeCoin MISSING
#define LIMITED_WHILE(condition, limit)
Can be used to limit a theoretically unbounded loop.
Definition: fuzz.h:22
uint64_t fee
Value Find(const std::map< Key, Value > &map, const Key &key)
uint32_t DepGraphIndex
Data type to represent transaction indices in DepGraphs and the clusters they represent.
int64_t fee
Definition: feefrac.h:106
int32_t size
Definition: feefrac.h:107
bool IsEmpty() const noexcept
Check if this is empty (size and fee are 0).
Definition: feefrac.h:119
Tagged wrapper around FeeFrac to avoid unit confusion.
Definition: feefrac.h:238
FUZZ_TARGET(txgraph)
Definition: txgraph.cpp:222
void SeedRandomStateForTest(SeedRand seedtype)
Seed the global RNG state for testing and log the seed value.
Definition: random.cpp:19
@ ZEROS
Seed with a compile time constant of zeros.
static int count
std::unique_ptr< TxGraph > MakeTxGraph(unsigned max_cluster_count) noexcept
Construct a new TxGraph with the specified limit on transactions within a cluster.
Definition: txgraph.cpp:2142
static constexpr unsigned MAX_CLUSTER_COUNT_LIMIT
Definition: txgraph.h:15
assert(!tx.IsCoinBase())