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 <iterator>
15#include <map>
16#include <memory>
17#include <set>
18#include <stdint.h>
19#include <utility>
20
21using namespace cluster_linearize;
22
23namespace {
24
28struct SimTxGraph
29{
33 static constexpr unsigned MAX_TRANSACTIONS = MAX_CLUSTER_COUNT_LIMIT * 2;
35 using SetType = BitSet<MAX_TRANSACTIONS>;
37 using Pos = DepGraphIndex;
39 static constexpr auto MISSING = Pos(-1);
40
47 std::array<std::shared_ptr<TxGraph::Ref>, MAX_TRANSACTIONS> simmap;
49 std::map<const TxGraph::Ref*, Pos> simrevmap;
51 std::vector<std::shared_ptr<TxGraph::Ref>> removed;
53 std::optional<bool> oversized;
55 DepGraphIndex max_cluster_count;
58 SetType modified;
59
61 explicit SimTxGraph(DepGraphIndex max_cluster) : max_cluster_count(max_cluster) {}
62
63 // Permit copying and moving.
64 SimTxGraph(const SimTxGraph&) noexcept = default;
65 SimTxGraph& operator=(const SimTxGraph&) noexcept = default;
66 SimTxGraph(SimTxGraph&&) noexcept = default;
67 SimTxGraph& operator=(SimTxGraph&&) noexcept = default;
68
71 bool IsOversized()
72 {
73 if (!oversized.has_value()) {
74 // Only recompute when oversized isn't already known.
75 oversized = false;
76 auto todo = graph.Positions();
77 // Iterate over all connected components of the graph.
78 while (todo.Any()) {
79 auto component = graph.FindConnectedComponent(todo);
80 if (component.Count() > max_cluster_count) oversized = true;
81 todo -= component;
82 }
83 }
84 return *oversized;
85 }
86
87 void MakeModified(DepGraphIndex index)
88 {
89 modified |= graph.GetConnectedComponent(graph.Positions(), index);
90 }
91
93 DepGraphIndex GetTransactionCount() const { return graph.TxCount(); }
94
96 FeePerWeight SumAll() const
97 {
99 for (auto i : graph.Positions()) {
100 ret += graph.FeeRate(i);
101 }
102 return ret;
103 }
104
106 Pos Find(const TxGraph::Ref* ref) const
107 {
108 auto it = simrevmap.find(ref);
109 if (it != simrevmap.end()) return it->second;
110 return MISSING;
111 }
112
114 TxGraph::Ref* GetRef(Pos pos)
115 {
116 assert(graph.Positions()[pos]);
117 assert(simmap[pos]);
118 return simmap[pos].get();
119 }
120
122 TxGraph::Ref* AddTransaction(const FeePerWeight& feerate)
123 {
124 assert(graph.TxCount() < MAX_TRANSACTIONS);
125 auto simpos = graph.AddTransaction(feerate);
126 MakeModified(simpos);
127 assert(graph.Positions()[simpos]);
128 simmap[simpos] = std::make_shared<TxGraph::Ref>();
129 auto ptr = simmap[simpos].get();
130 simrevmap[ptr] = simpos;
131 return ptr;
132 }
133
135 void AddDependency(TxGraph::Ref* parent, TxGraph::Ref* child)
136 {
137 auto par_pos = Find(parent);
138 if (par_pos == MISSING) return;
139 auto chl_pos = Find(child);
140 if (chl_pos == MISSING) return;
141 graph.AddDependencies(SetType::Singleton(par_pos), chl_pos);
142 MakeModified(par_pos);
143 // This may invalidate our cached oversized value.
144 if (oversized.has_value() && !*oversized) oversized = std::nullopt;
145 }
146
148 void SetTransactionFee(TxGraph::Ref* ref, int64_t fee)
149 {
150 auto pos = Find(ref);
151 if (pos == MISSING) return;
152 // No need to invoke MakeModified, because this equally affects main and staging.
153 graph.FeeRate(pos).fee = fee;
154 }
155
157 void RemoveTransaction(TxGraph::Ref* ref)
158 {
159 auto pos = Find(ref);
160 if (pos == MISSING) return;
161 MakeModified(pos);
162 graph.RemoveTransactions(SetType::Singleton(pos));
163 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 removed.push_back(std::move(simmap[pos]));
167 simmap[pos].reset();
168 // This may invalidate our cached oversized value.
169 if (oversized.has_value() && *oversized) oversized = std::nullopt;
170 }
171
176 void DestroyTransaction(TxGraph::Ref* ref, bool reset_oversize)
177 {
178 auto pos = Find(ref);
179 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 auto remove = std::partition(removed.begin(), removed.end(), [&](auto& arg) { return arg.get() != ref; });
184 removed.erase(remove, removed.end());
185 } else {
186 MakeModified(pos);
187 graph.RemoveTransactions(SetType::Singleton(pos));
188 simrevmap.erase(simmap[pos].get());
189 simmap[pos].reset();
190 // This may invalidate our cached oversized value.
191 if (reset_oversize && oversized.has_value() && *oversized) {
192 oversized = std::nullopt;
193 }
194 }
195 }
196
199 SetType MakeSet(std::span<TxGraph::Ref* const> arg)
200 {
201 SetType ret;
202 for (TxGraph::Ref* ptr : arg) {
203 auto pos = Find(ptr);
204 assert(pos != Pos(-1));
205 ret.Set(pos);
206 }
207 return ret;
208 }
209
211 SetType GetAncDesc(TxGraph::Ref* arg, bool desc)
212 {
213 auto pos = Find(arg);
214 if (pos == MISSING) return {};
215 return desc ? graph.Descendants(pos) : graph.Ancestors(pos);
216 }
217
220 void IncludeAncDesc(std::vector<TxGraph::Ref*>& arg, bool desc)
221 {
222 std::vector<TxGraph::Ref*> ret;
223 for (auto ptr : arg) {
224 auto simpos = Find(ptr);
225 if (simpos != MISSING) {
226 for (auto i : desc ? graph.Descendants(simpos) : graph.Ancestors(simpos)) {
227 ret.push_back(simmap[i].get());
228 }
229 } else {
230 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 arg.clear();
236 for (auto ptr : ret) {
237 if (std::find(arg.begin(), arg.end(), ptr) == arg.end()) {
238 arg.push_back(ptr);
239 }
240 }
241 }
242};
243
244} // namespace
245
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
254 FuzzedDataProvider provider(buffer.data(), buffer.size());
255
258 InsecureRandomContext rng(0xdecade2009added + buffer.size());
259
261 TxGraph::Ref empty_ref;
262
263 // Decide the maximum number of transactions per cluster we will use in this simulation.
264 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 auto real = MakeTxGraph(max_count);
268 std::vector<SimTxGraph> sims;
269 sims.reserve(2);
270 sims.emplace_back(max_count);
271
273 struct BlockBuilderData
274 {
276 std::unique_ptr<TxGraph::BlockBuilder> builder;
278 SimTxGraph::SetType included;
280 SimTxGraph::SetType done;
282 FeePerWeight last_feerate;
283
284 BlockBuilderData(std::unique_ptr<TxGraph::BlockBuilder> builder_in) : builder(std::move(builder_in)) {}
285 };
286
288 std::vector<BlockBuilderData> block_builders;
289
292 auto pick_fn = [&]() noexcept -> TxGraph::Ref* {
293 size_t tx_count[2] = {sims[0].GetTransactionCount(), 0};
295 size_t choices = tx_count[0] + sims[0].removed.size() + 1;
296 if (sims.size() == 2) {
297 tx_count[1] = sims[1].GetTransactionCount();
298 choices += tx_count[1] + sims[1].removed.size();
299 }
301 auto choice = provider.ConsumeIntegralInRange<size_t>(0, choices - 1);
302 // Consider both main and (if it exists) staging.
303 for (size_t level = 0; level < sims.size(); ++level) {
304 auto& sim = sims[level];
305 if (choice < tx_count[level]) {
306 // Return from graph.
307 for (auto i : sim.graph.Positions()) {
308 if (choice == 0) return sim.GetRef(i);
309 --choice;
310 }
311 assert(false);
312 } else {
313 choice -= tx_count[level];
314 }
315 if (choice < sim.removed.size()) {
316 // Return from removed.
317 return sim.removed[choice].get();
318 } else {
319 choice -= sim.removed.size();
320 }
321 }
322 // Return empty.
323 assert(choice == 0);
324 return &empty_ref;
325 };
326
329 auto get_diagram_fn = [&](bool main_only) -> std::vector<FeeFrac> {
330 int level = main_only ? 0 : sims.size() - 1;
331 auto& sim = sims[level];
332 // For every transaction in the graph, request its cluster, and throw them into a set.
333 std::set<std::vector<TxGraph::Ref*>> clusters;
334 for (auto i : sim.graph.Positions()) {
335 auto ref = sim.GetRef(i);
336 clusters.insert(real->GetCluster(*ref, main_only));
337 }
338 // Compute the chunkings of each (deduplicated) cluster.
339 size_t num_tx{0};
340 std::vector<FeeFrac> chunk_feerates;
341 for (const auto& cluster : clusters) {
342 num_tx += cluster.size();
343 std::vector<SimTxGraph::Pos> linearization;
344 linearization.reserve(cluster.size());
345 for (auto refptr : cluster) linearization.push_back(sim.Find(refptr));
346 for (const FeeFrac& chunk_feerate : ChunkLinearization(sim.graph, linearization)) {
347 chunk_feerates.push_back(chunk_feerate);
348 }
349 }
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 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 std::sort(chunk_feerates.begin(), chunk_feerates.end(), std::greater{});
357 return chunk_feerates;
358 };
359
360 LIMITED_WHILE(provider.remaining_bytes() > 0, 200) {
361 // Read a one-byte command.
362 int command = provider.ConsumeIntegral<uint8_t>();
363 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 bool alt = command & 1;
369 bool use_main = command & 2;
370 command >>= 2;
371
375 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 auto& top_sim = sims.back();
381 auto& sel_sim = use_main ? sims[0] : top_sim;
382 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 while (true) {
387 if ((block_builders.empty() || sims.size() > 1) && top_sim.GetTransactionCount() < SimTxGraph::MAX_TRANSACTIONS && command-- == 0) {
388 // AddTransaction.
389 int64_t fee;
390 int32_t size;
391 if (alt) {
392 // If alt is true, pick fee and size from the entire range.
393 fee = provider.ConsumeIntegralInRange<int64_t>(-0x8000000000000, 0x7ffffffffffff);
394 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 fee = provider.ConsumeIntegral<uint8_t>();
399 size = provider.ConsumeIntegral<uint8_t>() + 1;
400 }
401 FeePerWeight feerate{fee, size};
402 // Create a real TxGraph::Ref.
403 auto ref = real->AddTransaction(feerate);
404 // Create a shared_ptr place in the simulation to put the Ref in.
405 auto ref_loc = top_sim.AddTransaction(feerate);
406 // Move it in place.
407 *ref_loc = std::move(ref);
408 break;
409 } else if ((block_builders.empty() || sims.size() > 1) && top_sim.GetTransactionCount() + top_sim.removed.size() > 1 && command-- == 0) {
410 // AddDependency.
411 auto par = pick_fn();
412 auto chl = pick_fn();
413 auto pos_par = top_sim.Find(par);
414 auto pos_chl = top_sim.Find(chl);
415 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 if (top_sim.graph.Ancestors(pos_par)[pos_chl]) break;
419 }
420 top_sim.AddDependency(par, chl);
421 real->AddDependency(*par, *chl);
422 break;
423 } 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 std::vector<TxGraph::Ref*> to_remove;
428 to_remove.push_back(pick_fn());
429 top_sim.IncludeAncDesc(to_remove, alt);
430 // The order in which these ancestors/descendants are removed should not matter;
431 // randomly shuffle them.
432 std::shuffle(to_remove.begin(), to_remove.end(), rng);
433 for (TxGraph::Ref* ptr : to_remove) {
434 real->RemoveTransaction(*ptr);
435 top_sim.RemoveTransaction(ptr);
436 }
437 break;
438 } 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 auto removed_pos = provider.ConsumeIntegralInRange<size_t>(0, sel_sim.removed.size() - 1);
448 if (removed_pos != sel_sim.removed.size() - 1) {
449 std::swap(sel_sim.removed[removed_pos], sel_sim.removed.back());
450 }
451 sel_sim.removed.pop_back();
452 break;
453 } else if (block_builders.empty() && command-- == 0) {
454 // ~Ref (of any transaction).
455 std::vector<TxGraph::Ref*> to_destroy;
456 to_destroy.push_back(pick_fn());
457 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 auto old_size = to_destroy.size();
463 for (auto& sim : sims) sim.IncludeAncDesc(to_destroy, alt);
464 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 std::shuffle(to_destroy.begin(), to_destroy.end(), rng);
469 for (TxGraph::Ref* ptr : to_destroy) {
470 for (size_t level = 0; level < sims.size(); ++level) {
471 sims[level].DestroyTransaction(ptr, level == sims.size() - 1);
472 }
473 }
474 break;
475 } else if (block_builders.empty() && command-- == 0) {
476 // SetTransactionFee.
477 int64_t fee;
478 if (alt) {
479 fee = provider.ConsumeIntegralInRange<int64_t>(-0x8000000000000, 0x7ffffffffffff);
480 } else {
481 fee = provider.ConsumeIntegral<uint8_t>();
482 }
483 auto ref = pick_fn();
484 real->SetTransactionFee(*ref, fee);
485 for (auto& sim : sims) {
486 sim.SetTransactionFee(ref, fee);
487 }
488 break;
489 } else if (command-- == 0) {
490 // GetTransactionCount.
491 assert(real->GetTransactionCount(use_main) == sel_sim.GetTransactionCount());
492 break;
493 } else if (command-- == 0) {
494 // Exists.
495 auto ref = pick_fn();
496 bool exists = real->Exists(*ref, use_main);
497 bool should_exist = sel_sim.Find(ref) != SimTxGraph::MISSING;
498 assert(exists == should_exist);
499 break;
500 } else if (command-- == 0) {
501 // IsOversized.
502 assert(sel_sim.IsOversized() == real->IsOversized(use_main));
503 break;
504 } else if (command-- == 0) {
505 // GetIndividualFeerate.
506 auto ref = pick_fn();
507 auto feerate = real->GetIndividualFeerate(*ref);
508 bool found{false};
509 for (auto& sim : sims) {
510 auto simpos = sim.Find(ref);
511 if (simpos != SimTxGraph::MISSING) {
512 found = true;
513 assert(feerate == sim.graph.FeeRate(simpos));
514 }
515 }
516 if (!found) assert(feerate.IsEmpty());
517 break;
518 } else if (!main_sim.IsOversized() && command-- == 0) {
519 // GetMainChunkFeerate.
520 auto ref = pick_fn();
521 auto feerate = real->GetMainChunkFeerate(*ref);
522 auto simpos = main_sim.Find(ref);
523 if (simpos == SimTxGraph::MISSING) {
524 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 assert(feerate.size >= main_sim.graph.FeeRate(simpos).size);
529 assert(feerate.size <= main_sim.SumAll().size);
530 }
531 break;
532 } else if (!sel_sim.IsOversized() && command-- == 0) {
533 // GetAncestors/GetDescendants.
534 auto ref = pick_fn();
535 auto result = alt ? real->GetDescendants(*ref, use_main)
536 : real->GetAncestors(*ref, use_main);
537 assert(result.size() <= max_count);
538 auto result_set = sel_sim.MakeSet(result);
539 assert(result.size() == result_set.Count());
540 auto expect_set = sel_sim.GetAncDesc(ref, alt);
541 assert(result_set == expect_set);
542 break;
543 } else if (!sel_sim.IsOversized() && command-- == 0) {
544 // GetAncestorsUnion/GetDescendantsUnion.
545 std::vector<TxGraph::Ref*> refs;
546 // Gather a list of up to 15 Ref pointers.
547 auto count = provider.ConsumeIntegralInRange<size_t>(0, 15);
548 refs.resize(count);
549 for (size_t i = 0; i < count; ++i) {
550 refs[i] = pick_fn();
551 }
552 // Their order should not matter, shuffle them.
553 std::shuffle(refs.begin(), refs.end(), rng);
554 // Invoke the real function, and convert to SimPos set.
555 auto result = alt ? real->GetDescendantsUnion(refs, use_main)
556 : real->GetAncestorsUnion(refs, use_main);
557 auto result_set = sel_sim.MakeSet(result);
558 assert(result.size() == result_set.Count());
559 // Compute the expected result.
560 SimTxGraph::SetType expect_set;
561 for (TxGraph::Ref* ref : refs) expect_set |= sel_sim.GetAncDesc(ref, alt);
562 // Compare.
563 assert(result_set == expect_set);
564 break;
565 } else if (!sel_sim.IsOversized() && command-- == 0) {
566 // GetCluster.
567 auto ref = pick_fn();
568 auto result = real->GetCluster(*ref, use_main);
569 // Check cluster count limit.
570 assert(result.size() <= max_count);
571 // Require the result to be topologically valid and not contain duplicates.
572 auto left = sel_sim.graph.Positions();
573 for (auto refptr : result) {
574 auto simpos = sel_sim.Find(refptr);
575 assert(simpos != SimTxGraph::MISSING);
576 assert(left[simpos]);
577 left.Reset(simpos);
578 assert(!sel_sim.graph.Ancestors(simpos).Overlaps(left));
579 }
580 // Require the set to be connected.
581 auto result_set = sel_sim.MakeSet(result);
582 assert(sel_sim.graph.IsConnected(result_set));
583 // If ref exists, the result must contain it. If not, it must be empty.
584 auto simpos = sel_sim.Find(ref);
585 if (simpos != SimTxGraph::MISSING) {
586 assert(result_set[simpos]);
587 } else {
588 assert(result_set.None());
589 }
590 // Require the set not to have ancestors or descendants outside of it.
591 for (auto i : result_set) {
592 assert(sel_sim.graph.Ancestors(i).IsSubsetOf(result_set));
593 assert(sel_sim.graph.Descendants(i).IsSubsetOf(result_set));
594 }
595 break;
596 } else if (command-- == 0) {
597 // HaveStaging.
598 assert((sims.size() == 2) == real->HaveStaging());
599 break;
600 } else if (sims.size() < 2 && command-- == 0) {
601 // StartStaging.
602 sims.emplace_back(sims.back());
603 sims.back().modified = SimTxGraph::SetType{};
604 real->StartStaging();
605 break;
606 } else if (block_builders.empty() && sims.size() > 1 && command-- == 0) {
607 // CommitStaging.
608 real->CommitStaging();
609 sims.erase(sims.begin());
610 break;
611 } else if (sims.size() > 1 && command-- == 0) {
612 // AbortStaging.
613 real->AbortStaging();
614 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 sims.back().oversized = std::nullopt;
619 break;
620 } else if (!main_sim.IsOversized() && command-- == 0) {
621 // CompareMainOrder.
622 auto ref_a = pick_fn();
623 auto ref_b = pick_fn();
624 auto sim_a = main_sim.Find(ref_a);
625 auto sim_b = main_sim.Find(ref_b);
626 // Both transactions must exist in the main graph.
627 if (sim_a == SimTxGraph::MISSING || sim_b == SimTxGraph::MISSING) break;
628 auto cmp = real->CompareMainOrder(*ref_a, *ref_b);
629 // Distinct transactions have distinct places.
630 if (sim_a != sim_b) assert(cmp != 0);
631 // Ancestors go before descendants.
632 if (main_sim.graph.Ancestors(sim_a)[sim_b]) assert(cmp >= 0);
633 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 } else if (!sel_sim.IsOversized() && command-- == 0) {
639 // CountDistinctClusters.
640 std::vector<TxGraph::Ref*> refs;
641 // Gather a list of up to 15 (or up to 255) Ref pointers.
642 auto count = provider.ConsumeIntegralInRange<size_t>(0, alt ? 255 : 15);
643 refs.resize(count);
644 for (size_t i = 0; i < count; ++i) {
645 refs[i] = pick_fn();
646 }
647 // Their order should not matter, shuffle them.
648 std::shuffle(refs.begin(), refs.end(), rng);
649 // Invoke the real function.
650 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 SimTxGraph::SetType sim_reps;
655 for (auto ref : refs) {
656 // Skip Refs that do not occur in the simulated graph.
657 auto simpos = sel_sim.Find(ref);
658 if (simpos == SimTxGraph::MISSING) continue;
659 // Find the component that includes ref.
660 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 assert(component.Any());
663 sim_reps.Set(component.First());
664 }
665 // Compare the number of deduplicated representatives with the value returned by
666 // the real function.
667 assert(result == sim_reps.Count());
668 break;
669 } else if (command-- == 0) {
670 // DoWork.
671 real->DoWork();
672 break;
673 } else if (sims.size() == 2 && !sims[0].IsOversized() && !sims[1].IsOversized() && command-- == 0) {
674 // GetMainStagingDiagrams()
675 auto [real_main_diagram, real_staged_diagram] = real->GetMainStagingDiagrams();
676 auto real_sum_main = std::accumulate(real_main_diagram.begin(), real_main_diagram.end(), FeeFrac{});
677 auto real_sum_staged = std::accumulate(real_staged_diagram.begin(), real_staged_diagram.end(), FeeFrac{});
678 auto real_gain = real_sum_staged - real_sum_main;
679 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 assert(sim_gain == real_gain);
684 // Check that the feerates in each diagram are monotonically decreasing.
685 for (size_t i = 1; i < real_main_diagram.size(); ++i) {
686 assert(FeeRateCompare(real_main_diagram[i], real_main_diagram[i - 1]) <= 0);
687 }
688 for (size_t i = 1; i < real_staged_diagram.size(); ++i) {
689 assert(FeeRateCompare(real_staged_diagram[i], real_staged_diagram[i - 1]) <= 0);
690 }
691 break;
692 } else if (block_builders.size() < 4 && !main_sim.IsOversized() && command-- == 0) {
693 // GetBlockBuilder.
694 block_builders.emplace_back(real->GetBlockBuilder());
695 break;
696 } else if (!block_builders.empty() && command-- == 0) {
697 // ~BlockBuilder.
698 block_builders.erase(block_builders.begin() + builder_idx);
699 break;
700 } else if (!block_builders.empty() && command-- == 0) {
701 // BlockBuilder::GetCurrentChunk, followed by Include/Skip.
702 auto& builder_data = block_builders[builder_idx];
703 auto new_included = builder_data.included;
704 auto new_done = builder_data.done;
705 auto chunk = builder_data.builder->GetCurrentChunk();
706 if (chunk) {
707 // Chunk feerates must be monotonously decreasing.
708 if (!builder_data.last_feerate.IsEmpty()) {
709 assert(!(chunk->second >> builder_data.last_feerate));
710 }
711 builder_data.last_feerate = chunk->second;
712 // Verify the contents of GetCurrentChunk.
713 FeePerWeight sum_feerate;
714 for (TxGraph::Ref* ref : chunk->first) {
715 // Each transaction in the chunk must exist in the main graph.
716 auto simpos = main_sim.Find(ref);
717 assert(simpos != SimTxGraph::MISSING);
718 // Verify the claimed chunk feerate.
719 sum_feerate += main_sim.graph.FeeRate(simpos);
720 // Make sure no transaction is reported twice.
721 assert(!new_done[simpos]);
722 new_done.Set(simpos);
723 // The concatenation of all included transactions must be topologically valid.
724 new_included.Set(simpos);
725 assert(main_sim.graph.Ancestors(simpos).IsSubsetOf(new_included));
726 }
727 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 if (builder_data.done == builder_data.included) {
732 assert(builder_data.done.Count() == main_sim.GetTransactionCount());
733 }
734 }
735 // Possibly invoke GetCurrentChunk() again, which should give the same result.
736 if ((orig_command % 7) >= 5) {
737 auto chunk2 = builder_data.builder->GetCurrentChunk();
738 assert(chunk == chunk2);
739 }
740 // Skip or include.
741 if ((orig_command % 5) >= 3) {
742 // Skip.
743 builder_data.builder->Skip();
744 } else {
745 // Include.
746 builder_data.builder->Include();
747 builder_data.included = new_included;
748 }
749 builder_data.done = new_done;
750 break;
751 } else if (!main_sim.IsOversized() && command-- == 0) {
752 // GetWorstMainChunk.
753 auto [worst_chunk, worst_chunk_feerate] = real->GetWorstMainChunk();
754 // Just do some sanity checks here. Consistency with GetBlockBuilder is checked
755 // below.
756 if (main_sim.GetTransactionCount() == 0) {
757 assert(worst_chunk.empty());
758 assert(worst_chunk_feerate.IsEmpty());
759 } else {
760 assert(!worst_chunk.empty());
761 SimTxGraph::SetType done;
763 for (TxGraph::Ref* ref : worst_chunk) {
764 // Each transaction in the chunk must exist in the main graph.
765 auto simpos = main_sim.Find(ref);
766 assert(simpos != SimTxGraph::MISSING);
767 sum += main_sim.graph.FeeRate(simpos);
768 // Make sure the chunk contains no duplicate transactions.
769 assert(!done[simpos]);
770 done.Set(simpos);
771 // All elements are preceded by all their descendants.
772 assert(main_sim.graph.Descendants(simpos).IsSubsetOf(done));
773 }
774 assert(sum == worst_chunk_feerate);
775 }
776 break;
777 }
778 }
779 }
780
781 // After running all modifications, perform an internal sanity check (before invoking
782 // inspectors that may modify the internal state).
783 real->SanityCheck();
784
785 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 std::vector<SimTxGraph::Pos> vec1;
790 for (auto i : sims[0].graph.Positions()) vec1.push_back(i);
791 std::shuffle(vec1.begin(), vec1.end(), rng);
792 auto vec2 = vec1;
793 std::shuffle(vec2.begin(), vec2.end(), rng);
794 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 auto cmp = [&](SimTxGraph::Pos a, SimTxGraph::Pos b) noexcept {
798 return real->CompareMainOrder(*sims[0].GetRef(a), *sims[0].GetRef(b)) < 0;
799 };
800 std::sort(vec1.begin(), vec1.end(), cmp);
801 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 assert(vec1 == vec2);
806
807 // Verify that the ordering is topological.
808 auto todo = sims[0].graph.Positions();
809 for (auto i : vec1) {
810 todo.Reset(i);
811 assert(!sims[0].graph.Ancestors(i).Overlaps(todo));
812 }
813 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 for (size_t pos = 0; pos < vec1.size(); ++pos) {
818 auto pos_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[pos]));
819 if (pos > 0) {
820 size_t before = rng.randrange<size_t>(pos);
821 auto before_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[before]));
822 assert(FeeRateCompare(before_feerate, pos_feerate) >= 0);
823 }
824 if (pos + 1 < vec1.size()) {
825 size_t after = pos + 1 + rng.randrange<size_t>(vec1.size() - 1 - pos);
826 auto after_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[after]));
827 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 auto builder = real->GetBlockBuilder();
834 std::vector<SimTxGraph::Pos> vec_builder;
835 std::vector<TxGraph::Ref*> last_chunk;
836 FeePerWeight last_chunk_feerate;
837 while (auto chunk = builder->GetCurrentChunk()) {
839 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 assert(real->GetMainChunkFeerate(*ref) == chunk->second);
843 // Verify the chunk feerate matches the sum of the reported individual feerates.
844 sum += real->GetIndividualFeerate(*ref);
845 // Chunks must contain transactions that exist in the graph.
846 auto simpos = sims[0].Find(ref);
847 assert(simpos != SimTxGraph::MISSING);
848 vec_builder.push_back(simpos);
849 }
850 assert(sum == chunk->second);
851 last_chunk = std::move(chunk->first);
852 last_chunk_feerate = chunk->second;
853 builder->Include();
854 }
855 assert(vec_builder == vec1);
856
857 // The last chunk returned by the BlockBuilder must match GetWorstMainChunk, in reverse.
858 std::reverse(last_chunk.begin(), last_chunk.end());
859 auto [worst_chunk, worst_chunk_feerate] = real->GetWorstMainChunk();
860 assert(last_chunk == worst_chunk);
861 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 auto main_real_diagram = get_diagram_fn(/*main_only=*/true);
866 auto main_implied_diagram = ChunkLinearization(sims[0].graph, vec1);
867 assert(CompareChunks(main_real_diagram, main_implied_diagram) == 0);
868
869 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 auto [main_cmp_diagram, stage_cmp_diagram] = real->GetMainStagingDiagrams();
873 // Check that the feerates in each diagram are monotonically decreasing.
874 for (size_t i = 1; i < main_cmp_diagram.size(); ++i) {
875 assert(FeeRateCompare(main_cmp_diagram[i], main_cmp_diagram[i - 1]) <= 0);
876 }
877 for (size_t i = 1; i < stage_cmp_diagram.size(); ++i) {
878 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 std::sort(main_cmp_diagram.begin(), main_cmp_diagram.end(), std::greater{});
885 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 std::vector<FeeFrac> missing_main_cmp;
890 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 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 auto stage_real_diagram = get_diagram_fn(/*main_only=*/false);
897 std::vector<FeeFrac> missing_stage_cmp;
898 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 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 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 FeeFrac missing_real;
912 for (const auto& feerate : missing_main_cmp) missing_real += feerate;
913 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 assert(missing_real.size >= missing_expected.size);
917 }
918 }
919
920 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 for (int main_only = 0; main_only < 2; ++main_only) {
925 auto& sim = main_only ? sims[0] : sims.back();
926 // Compare simple properties of the graph with the simulation.
927 assert(real->IsOversized(main_only) == sim.IsOversized());
928 assert(real->GetTransactionCount(main_only) == sim.GetTransactionCount());
929 // If the graph (and the simulation) are not oversized, perform a full comparison.
930 if (!sim.IsOversized()) {
931 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 while (todo.Any()) {
935 auto component = sim.graph.FindConnectedComponent(todo);
936 todo -= component;
937 // Iterate over the transactions in that component.
938 for (auto i : component) {
939 // Check its individual feerate against simulation.
940 assert(sim.graph.FeeRate(i) == real->GetIndividualFeerate(*sim.GetRef(i)));
941 // Check its ancestors against simulation.
942 auto expect_anc = sim.graph.Ancestors(i);
943 auto anc = sim.MakeSet(real->GetAncestors(*sim.GetRef(i), main_only));
944 assert(anc.Count() <= max_count);
945 assert(anc == expect_anc);
946 // Check its descendants against simulation.
947 auto expect_desc = sim.graph.Descendants(i);
948 auto desc = sim.MakeSet(real->GetDescendants(*sim.GetRef(i), main_only));
949 assert(desc.Count() <= max_count);
950 assert(desc == expect_desc);
951 // Check the cluster the transaction is part of.
952 auto cluster = real->GetCluster(*sim.GetRef(i), main_only);
953 assert(cluster.size() <= max_count);
954 assert(sim.MakeSet(cluster) == component);
955 // Check that the cluster is reported in a valid topological order (its
956 // linearization).
957 std::vector<DepGraphIndex> simlin;
958 SimTxGraph::SetType done;
959 for (TxGraph::Ref* ptr : cluster) {
960 auto simpos = sim.Find(ptr);
961 assert(sim.graph.Descendants(simpos).IsSubsetOf(component - done));
962 done.Set(simpos);
963 assert(sim.graph.Ancestors(simpos).IsSubsetOf(done));
964 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 if (sims.size() == 1 || main_only) {
969 cluster_linearize::LinearizationChunking simlinchunk(sim.graph, simlin);
970 DepGraphIndex idx{0};
971 for (unsigned chunknum = 0; chunknum < simlinchunk.NumChunksLeft(); ++chunknum) {
972 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 assert(sim.graph.IsConnected(chunk.transactions));
976 // Check the chunk feerates of all transactions in the cluster.
977 while (chunk.transactions.Any()) {
978 assert(chunk.transactions[simlin[idx]]);
979 chunk.transactions.Reset(simlin[idx]);
980 assert(chunk.feerate == real->GetMainChunkFeerate(*cluster[idx]));
981 ++idx;
982 }
983 }
984 }
985 }
986 }
987 }
988 }
989
990 // Sanity check again (because invoking inspectors may modify internal unobservable state).
991 real->SanityCheck();
992
993 // Kill the block builders.
994 block_builders.clear();
995 // Kill the TxGraph object.
996 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 sims.clear();
1000}
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 GetConnectedComponent(const SetType &todo, DepGraphIndex tx) const noexcept
Get the connected component within the subset "todo" that contains tx (which must be in todo).
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
volatile double sum
Definition: examples.cpp:10
#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)
std::vector< FeeFrac > ChunkLinearization(const DepGraph< SetType > &depgraph, std::span< const DepGraphIndex > linearization) noexcept
Compute the feerates of the chunks of linearization.
uint32_t DepGraphIndex
Data type to represent transaction indices in DepGraphs and the clusters they represent.
Data structure storing a fee and size, ordered by increasing fee/size.
Definition: feefrac.h:39
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:246
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:2503
static constexpr unsigned MAX_CLUSTER_COUNT_LIMIT
Definition: txgraph.h:17
std::partial_ordering CompareChunks(std::span< const FeeFrac > chunks0, std::span< const FeeFrac > chunks1)
Compare the feerate diagrams implied by the provided sorted chunks data.
Definition: feefrac.cpp:10
assert(!tx.IsCoinBase())