txgraph.cpp
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 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 65 /** Check whether this graph is oversized (contains a connected component whose number of 66 * transactions exceeds max_cluster_count. */ 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 83 /** Determine the number of (non-removed) transactions in the graph. */ 84 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 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 94 /** Given a position in this simulated graph, get the corresponding TxGraph::Ref. */ 95 TxGraph::Ref* GetRef(Pos pos) 96 { 97 assert(graph.Positions()[pos]); 98 assert(simmap[pos]); 99 return simmap[pos].get(); 100 } 101 102 /** Add a new transaction to the simulation. */ 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 114 /** Add a dependency between two positions in this graph. */ 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 126 /** Modify the transaction fee of a ref, if it exists. */ 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 134 /** Remove the transaction in the specified position from the graph. */ 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 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 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 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 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 186 /** Get the set of ancestors (desc=false) or descendants (desc=true) in this graph. */ 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 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 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 222 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 SeedRandomStateForTest(SeedRand::ZEROS); 230 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 InsecureRandomContext rng(0xdecade2009added + buffer.size()); 235 236 /** Variable used whenever an empty TxGraph::Ref is needed. */ 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 248 /** Function to pick any Ref (for either sim in sims: from sim.simmap or sim.removed, or the 249 * empty Ref). */ 250 auto pick_fn = [&]() noexcept -> TxGraph::Ref* { 251 size_t tx_count[2] = {sims[0].GetTransactionCount(), 0}; 252 /** The number of possible choices. */ 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 } 258 /** Pick one of them. */ 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 }