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 7 #include <cluster_linearize.h> 8 #include <random.h> 9 #include <util/bitset.h> 10 #include <util/check.h> 11 #include <util/feefrac.h> 12 13 #include <compare> 14 #include <memory> 15 #include <set> 16 #include <span> 17 #include <utility> 18 19 namespace { 20 21 using namespace cluster_linearize; 22 23 /** The maximum number of levels a TxGraph can have (0 = main, 1 = staging). */ 24 static constexpr int MAX_LEVELS{2}; 25 26 // Forward declare the TxGraph implementation class. 27 class TxGraphImpl; 28 29 /** Position of a DepGraphIndex within a Cluster::m_linearization. */ 30 using LinearizationIndex = uint32_t; 31 /** Position of a Cluster within Graph::ClusterSet::m_clusters. */ 32 using ClusterSetIndex = uint32_t; 33 34 /** Quality levels for cached cluster linearizations. */ 35 enum class QualityLevel 36 { 37 /** This cluster may have multiple disconnected components, which are all NEEDS_RELINEARIZE. */ 38 NEEDS_SPLIT, 39 /** This cluster may have multiple disconnected components, which are all ACCEPTABLE. */ 40 NEEDS_SPLIT_ACCEPTABLE, 41 /** This cluster has undergone changes that warrant re-linearization. */ 42 NEEDS_RELINEARIZE, 43 /** The minimal level of linearization has been performed, but it is not known to be optimal. */ 44 ACCEPTABLE, 45 /** The linearization is known to be optimal. */ 46 OPTIMAL, 47 /** This cluster is not registered in any ClusterSet::m_clusters. 48 * This must be the last entry in QualityLevel as ClusterSet::m_clusters is sized using it. */ 49 NONE, 50 }; 51 52 /** A grouping of connected transactions inside a TxGraphImpl::ClusterSet. */ 53 class Cluster 54 { 55 friend class TxGraphImpl; 56 using GraphIndex = TxGraph::GraphIndex; 57 using SetType = BitSet<MAX_CLUSTER_COUNT_LIMIT>; 58 /** The DepGraph for this cluster, holding all feerates, and ancestors/descendants. */ 59 DepGraph<SetType> m_depgraph; 60 /** m_mapping[i] gives the GraphIndex for the position i transaction in m_depgraph. Values for 61 * positions i that do not exist in m_depgraph shouldn't ever be accessed and thus don't 62 * matter. m_mapping.size() equals m_depgraph.PositionRange(). */ 63 std::vector<GraphIndex> m_mapping; 64 /** The current linearization of the cluster. m_linearization.size() equals 65 * m_depgraph.TxCount(). This is always kept topological. */ 66 std::vector<DepGraphIndex> m_linearization; 67 /** The quality level of m_linearization. */ 68 QualityLevel m_quality{QualityLevel::NONE}; 69 /** Which position this Cluster has in Graph::ClusterSet::m_clusters[m_quality]. */ 70 ClusterSetIndex m_setindex{ClusterSetIndex(-1)}; 71 /** Which level this Cluster is at in the graph (-1=not inserted, 0=main, 1=staging). */ 72 int m_level{-1}; 73 /** Sequence number for this Cluster (for tie-breaking comparison between equal-chunk-feerate 74 transactions in distinct clusters). */ 75 uint64_t m_sequence; 76 77 public: 78 Cluster() noexcept = delete; 79 /** Construct an empty Cluster. */ 80 explicit Cluster(uint64_t sequence) noexcept; 81 /** Construct a singleton Cluster. */ 82 explicit Cluster(uint64_t sequence, TxGraphImpl& graph, const FeePerWeight& feerate, GraphIndex graph_index) noexcept; 83 84 // Cannot move or copy (would invalidate Cluster* in Locator and ClusterSet). */ 85 Cluster(const Cluster&) = delete; 86 Cluster& operator=(const Cluster&) = delete; 87 Cluster(Cluster&&) = delete; 88 Cluster& operator=(Cluster&&) = delete; 89 90 // Generic helper functions. 91 92 /** Whether the linearization of this Cluster can be exposed. */ 93 bool IsAcceptable(bool after_split = false) const noexcept 94 { 95 return m_quality == QualityLevel::ACCEPTABLE || m_quality == QualityLevel::OPTIMAL || 96 (after_split && m_quality == QualityLevel::NEEDS_SPLIT_ACCEPTABLE); 97 } 98 /** Whether the linearization of this Cluster is optimal. */ 99 bool IsOptimal() const noexcept 100 { 101 return m_quality == QualityLevel::OPTIMAL; 102 } 103 /** Whether this cluster requires splitting. */ 104 bool NeedsSplitting() const noexcept 105 { 106 return m_quality == QualityLevel::NEEDS_SPLIT || 107 m_quality == QualityLevel::NEEDS_SPLIT_ACCEPTABLE; 108 } 109 /** Get the number of transactions in this Cluster. */ 110 LinearizationIndex GetTxCount() const noexcept { return m_linearization.size(); } 111 /** Given a DepGraphIndex into this Cluster, find the corresponding GraphIndex. */ 112 GraphIndex GetClusterEntry(DepGraphIndex index) const noexcept { return m_mapping[index]; } 113 /** Only called by Graph::SwapIndexes. */ 114 void UpdateMapping(DepGraphIndex cluster_idx, GraphIndex graph_idx) noexcept { m_mapping[cluster_idx] = graph_idx; } 115 /** Push changes to Cluster and its linearization to the TxGraphImpl Entry objects. */ 116 void Updated(TxGraphImpl& graph) noexcept; 117 /** Create a copy of this Cluster in staging, returning a pointer to it (used by PullIn). */ 118 Cluster* CopyToStaging(TxGraphImpl& graph) const noexcept; 119 /** Get the list of Clusters in main that conflict with this one (which is assumed to be in staging). */ 120 void GetConflicts(const TxGraphImpl& graph, std::vector<Cluster*>& out) const noexcept; 121 /** Mark all the Entry objects belonging to this staging Cluster as missing. The Cluster must be 122 * deleted immediately after. */ 123 void MakeStagingTransactionsMissing(TxGraphImpl& graph) noexcept; 124 /** Remove all transactions from a Cluster. */ 125 void Clear(TxGraphImpl& graph) noexcept; 126 /** Change a Cluster's level from 1 (staging) to 0 (main). */ 127 void MoveToMain(TxGraphImpl& graph) noexcept; 128 129 // Functions that implement the Cluster-specific side of internal TxGraphImpl mutations. 130 131 /** Apply all removals from the front of to_remove that apply to this Cluster, popping them 132 * off. These must be at least one such entry. */ 133 void ApplyRemovals(TxGraphImpl& graph, std::span<GraphIndex>& to_remove) noexcept; 134 /** Split this cluster (must have a NEEDS_SPLIT* quality). Returns whether to delete this 135 * Cluster afterwards. */ 136 [[nodiscard]] bool Split(TxGraphImpl& graph) noexcept; 137 /** Move all transactions from cluster to *this (as separate components). */ 138 void Merge(TxGraphImpl& graph, Cluster& cluster) noexcept; 139 /** Given a span of (parent, child) pairs that all belong to this Cluster, apply them. */ 140 void ApplyDependencies(TxGraphImpl& graph, std::span<std::pair<GraphIndex, GraphIndex>> to_apply) noexcept; 141 /** Improve the linearization of this Cluster. */ 142 void Relinearize(TxGraphImpl& graph, uint64_t max_iters) noexcept; 143 144 // Functions that implement the Cluster-specific side of public TxGraph functions. 145 146 /** Process elements from the front of args that apply to this cluster, and append Refs for the 147 * union of their ancestors to output. */ 148 void GetAncestorRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept; 149 /** Process elements from the front of args that apply to this cluster, and append Refs for the 150 * union of their descendants to output. */ 151 void GetDescendantRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept; 152 /** Get a vector of Refs for all elements of this Cluster, in linearization order. */ 153 std::vector<TxGraph::Ref*> GetClusterRefs(const TxGraphImpl& graph) noexcept; 154 /** Get the individual transaction feerate of a Cluster element. */ 155 FeePerWeight GetIndividualFeerate(DepGraphIndex idx) noexcept; 156 /** Modify the fee of a Cluster element. */ 157 void SetFee(TxGraphImpl& graph, DepGraphIndex idx, int64_t fee) noexcept; 158 159 // Debugging functions. 160 161 void SanityCheck(const TxGraphImpl& graph, int level) const; 162 }; 163 164 165 /** The transaction graph, including staged changes. 166 * 167 * The overall design of the data structure consists of 3 interlinked representations: 168 * - The transactions (held as a vector of TxGraphImpl::Entry inside TxGraphImpl). 169 * - The clusters (Cluster objects in per-quality vectors inside TxGraphImpl::ClusterSet). 170 * - The Refs (TxGraph::Ref objects, held externally by users of the TxGraph class) 171 * 172 * The Clusters are kept in one or two ClusterSet objects, one for the "main" graph, and one for 173 * the proposed changes ("staging"). If a transaction occurs in both, they share the same Entry, 174 * but there will be a separate Cluster per graph. 175 * 176 * Clusters and Refs contain the index of the Entry objects they refer to, and the Entry objects 177 * refer back to the Clusters and Refs the corresponding transaction is contained in. 178 * 179 * While redundant, this permits moving all of them independently, without invalidating things 180 * or costly iteration to fix up everything: 181 * - Entry objects can be moved to fill holes left by removed transactions in the Entry vector 182 * (see TxGraphImpl::Compact). 183 * - Clusters can be rewritten continuously (removals can cause them to split, new dependencies 184 * can cause them to be merged). 185 * - Ref objects can be held outside the class, while permitting them to be moved around, and 186 * inherited from. 187 */ 188 class TxGraphImpl final : public TxGraph 189 { 190 friend class Cluster; 191 private: 192 /** Internal RNG. */ 193 FastRandomContext m_rng; 194 /** This TxGraphImpl's maximum cluster count limit. */ 195 const DepGraphIndex m_max_cluster_count; 196 197 /** Information about one group of Clusters to be merged. */ 198 struct GroupEntry 199 { 200 /** Where the clusters to be merged start in m_group_clusters. */ 201 uint32_t m_cluster_offset; 202 /** How many clusters to merge. */ 203 uint32_t m_cluster_count; 204 /** Where the dependencies for this cluster group in m_deps_to_add start. */ 205 uint32_t m_deps_offset; 206 /** How many dependencies to add. */ 207 uint32_t m_deps_count; 208 }; 209 210 /** Information about all groups of Clusters to be merged. */ 211 struct GroupData 212 { 213 /** The groups of Clusters to be merged. */ 214 std::vector<GroupEntry> m_groups; 215 /** Which clusters are to be merged. GroupEntry::m_cluster_offset indexes into this. */ 216 std::vector<Cluster*> m_group_clusters; 217 /** Whether at least one of the groups cannot be applied because it would result in a 218 * Cluster that violates the cluster count limit. */ 219 bool m_group_oversized; 220 }; 221 222 /** The collection of all Clusters in main or staged. */ 223 struct ClusterSet 224 { 225 /** The vectors of clusters, one vector per quality level. ClusterSetIndex indexes into each. */ 226 std::array<std::vector<std::unique_ptr<Cluster>>, int(QualityLevel::NONE)> m_clusters; 227 /** Which removals have yet to be applied. */ 228 std::vector<GraphIndex> m_to_remove; 229 /** Which dependencies are to be added ((parent,child) pairs). GroupData::m_deps_offset indexes 230 * into this. */ 231 std::vector<std::pair<GraphIndex, GraphIndex>> m_deps_to_add; 232 /** Information about the merges to be performed, if known. */ 233 std::optional<GroupData> m_group_data = GroupData{}; 234 /** Which entries were removed in this ClusterSet (so they can be wiped on abort). This 235 * includes all entries which have an (R) removed locator at this level (staging only), 236 * plus optionally any transaction in m_unlinked. */ 237 std::vector<GraphIndex> m_removed; 238 /** Total number of transactions in this graph (sum of all transaction counts in all 239 * Clusters, and for staging also those inherited from the main ClusterSet). */ 240 GraphIndex m_txcount{0}; 241 /** Whether this graph is oversized (if known). This roughly matches 242 * m_group_data->m_group_oversized, but may be known even if m_group_data is not. */ 243 std::optional<bool> m_oversized{false}; 244 245 ClusterSet() noexcept = default; 246 }; 247 248 /** The main ClusterSet. */ 249 ClusterSet m_main_clusterset; 250 /** The staging ClusterSet, if any. */ 251 std::optional<ClusterSet> m_staging_clusterset; 252 /** Next sequence number to assign to created Clusters. */ 253 uint64_t m_next_sequence_counter{0}; 254 255 /** A Locator that describes whether, where, and in which Cluster an Entry appears. 256 * Every Entry has MAX_LEVELS locators, as it may appear in one Cluster per level. 257 * 258 * Each level of a Locator is in one of three states: 259 * 260 * - (P)resent: actually occurs in a Cluster at that level. 261 * 262 * - (M)issing: 263 * - In the main graph: the transaction does not exist in main. 264 * - In the staging graph: the transaction's existence is the same as in main. If it doesn't 265 * exist in main, (M) in staging means it does not exist there 266 * either. If it does exist in main, (M) in staging means the 267 * cluster it is in has not been modified in staging, and thus the 268 * transaction implicitly exists in staging too (without explicit 269 * Cluster object; see PullIn() to create it in staging too). 270 * 271 * - (R)emoved: only possible in staging; it means the transaction exists in main, but is 272 * removed in staging. 273 * 274 * The following combinations are possible: 275 * - (M,M): the transaction doesn't exist in either graph. 276 * - (P,M): the transaction exists in both, but only exists explicitly in a Cluster object in 277 * main. Its existence in staging is inherited from main. 278 * - (P,P): the transaction exists in both, and is materialized in both. Thus, the clusters 279 * and/or their linearizations may be different in main and staging. 280 * - (M,P): the transaction is added in staging, and does not exist in main. 281 * - (P,R): the transaction exists in main, but is removed in staging. 282 * 283 * When staging does not exist, only (M,M) and (P,M) are possible. 284 */ 285 struct Locator 286 { 287 /** Which Cluster the Entry appears in (nullptr = missing). */ 288 Cluster* cluster{nullptr}; 289 /** Where in the Cluster it appears (if cluster == nullptr: 0 = missing, -1 = removed). */ 290 DepGraphIndex index{0}; 291 292 /** Mark this Locator as missing (= same as lower level, or non-existing if level 0). */ 293 void SetMissing() noexcept { cluster = nullptr; index = 0; } 294 /** Mark this Locator as removed (not allowed in level 0). */ 295 void SetRemoved() noexcept { cluster = nullptr; index = DepGraphIndex(-1); } 296 /** Mark this Locator as present, in the specified Cluster. */ 297 void SetPresent(Cluster* c, DepGraphIndex i) noexcept { cluster = c; index = i; } 298 /** Check if this Locator is missing. */ 299 bool IsMissing() const noexcept { return cluster == nullptr && index == 0; } 300 /** Check if this Locator is removed. */ 301 bool IsRemoved() const noexcept { return cluster == nullptr && index == DepGraphIndex(-1); } 302 /** Check if this Locator is present (in some Cluster). */ 303 bool IsPresent() const noexcept { return cluster != nullptr; } 304 }; 305 306 /** Internal information about each transaction in a TxGraphImpl. */ 307 struct Entry 308 { 309 /** Pointer to the corresponding Ref object if any, or nullptr if unlinked. */ 310 Ref* m_ref{nullptr}; 311 /** Which Cluster and position therein this Entry appears in. ([0] = main, [1] = staged). */ 312 Locator m_locator[MAX_LEVELS]; 313 /** The chunk feerate of this transaction in main (if present in m_locator[0]). */ 314 FeePerWeight m_main_chunk_feerate; 315 /** The position this transaction has in the main linearization (if present). */ 316 LinearizationIndex m_main_lin_index; 317 }; 318 319 /** The set of all transactions (in all levels combined). GraphIndex values index into this. */ 320 std::vector<Entry> m_entries; 321 322 /** Set of Entries which have no linked Ref anymore. */ 323 std::vector<GraphIndex> m_unlinked; 324 325 /** Compare two Cluster* by their m_sequence value (while supporting nullptr). */ 326 static std::strong_ordering CompareClusters(Cluster* a, Cluster* b) noexcept 327 { 328 // The nullptr pointer compares before everything else. 329 if (a == nullptr || b == nullptr) { 330 return (a != nullptr) <=> (b != nullptr); 331 } 332 // If neither pointer is nullptr, compare the Clusters' sequence numbers. 333 Assume(a == b || a->m_sequence != b->m_sequence); 334 return a->m_sequence <=> b->m_sequence; 335 } 336 337 public: 338 /** Construct a new TxGraphImpl with the specified maximum cluster count. */ 339 explicit TxGraphImpl(DepGraphIndex max_cluster_count) noexcept : 340 m_max_cluster_count(max_cluster_count) 341 { 342 Assume(max_cluster_count >= 1); 343 Assume(max_cluster_count <= MAX_CLUSTER_COUNT_LIMIT); 344 } 345 346 /** Destructor. */ 347 ~TxGraphImpl() noexcept; 348 349 // Cannot move or copy (would invalidate TxGraphImpl* in Ref, MiningOrder, EvictionOrder). 350 TxGraphImpl(const TxGraphImpl&) = delete; 351 TxGraphImpl& operator=(const TxGraphImpl&) = delete; 352 TxGraphImpl(TxGraphImpl&&) = delete; 353 TxGraphImpl& operator=(TxGraphImpl&&) = delete; 354 355 // Simple helper functions. 356 357 /** Swap the Entry referred to by a and the one referred to by b. */ 358 void SwapIndexes(GraphIndex a, GraphIndex b) noexcept; 359 /** If idx exists in the specified level ClusterSet (explicitly, or in the level below and not 360 * removed), return the Cluster it is in. Otherwise, return nullptr. */ 361 Cluster* FindCluster(GraphIndex idx, int level) const noexcept; 362 /** Extract a Cluster from its ClusterSet. */ 363 std::unique_ptr<Cluster> ExtractCluster(int level, QualityLevel quality, ClusterSetIndex setindex) noexcept; 364 /** Delete a Cluster. */ 365 void DeleteCluster(Cluster& cluster) noexcept; 366 /** Insert a Cluster into its ClusterSet. */ 367 ClusterSetIndex InsertCluster(int level, std::unique_ptr<Cluster>&& cluster, QualityLevel quality) noexcept; 368 /** Change the QualityLevel of a Cluster (identified by old_quality and old_index). */ 369 void SetClusterQuality(int level, QualityLevel old_quality, ClusterSetIndex old_index, QualityLevel new_quality) noexcept; 370 /** Get the index of the top level ClusterSet (staging if it exists, main otherwise). */ 371 int GetTopLevel() const noexcept { return m_staging_clusterset.has_value(); } 372 /** Get the specified level (staging if it exists and main_only is not specified, main otherwise). */ 373 int GetSpecifiedLevel(bool main_only) const noexcept { return m_staging_clusterset.has_value() && !main_only; } 374 /** Get a reference to the ClusterSet at the specified level (which must exist). */ 375 ClusterSet& GetClusterSet(int level) noexcept; 376 const ClusterSet& GetClusterSet(int level) const noexcept; 377 /** Make a transaction not exist at a specified level. It must currently exist there. */ 378 void ClearLocator(int level, GraphIndex index) noexcept; 379 /** Find which Clusters in main conflict with ones in staging. */ 380 std::vector<Cluster*> GetConflicts() const noexcept; 381 382 // Functions for handling Refs. 383 384 /** Only called by Ref's move constructor/assignment to update Ref locations. */ 385 void UpdateRef(GraphIndex idx, Ref& new_location) noexcept final 386 { 387 auto& entry = m_entries[idx]; 388 Assume(entry.m_ref != nullptr); 389 entry.m_ref = &new_location; 390 } 391 392 /** Only called by Ref::~Ref to unlink Refs, and Ref's move assignment. */ 393 void UnlinkRef(GraphIndex idx) noexcept final 394 { 395 auto& entry = m_entries[idx]; 396 Assume(entry.m_ref != nullptr); 397 entry.m_ref = nullptr; 398 // Mark the transaction as to be removed in all levels where it explicitly or implicitly 399 // exists. 400 bool exists_anywhere{false}; 401 bool exists{false}; 402 for (int level = 0; level <= GetTopLevel(); ++level) { 403 if (entry.m_locator[level].IsPresent()) { 404 exists_anywhere = true; 405 exists = true; 406 } else if (entry.m_locator[level].IsRemoved()) { 407 exists = false; 408 } 409 if (exists) { 410 auto& clusterset = GetClusterSet(level); 411 clusterset.m_to_remove.push_back(idx); 412 // Force recomputation of grouping data. 413 clusterset.m_group_data = std::nullopt; 414 // Do not wipe the oversized state of main if staging exists. The reason for this 415 // is that the alternative would mean that cluster merges may need to be applied to 416 // a formerly-oversized main graph while staging exists (to satisfy chunk feerate 417 // queries into main, for example), and such merges could conflict with pulls of 418 // some of their constituents into staging. 419 if (level == GetTopLevel() && clusterset.m_oversized == true) { 420 clusterset.m_oversized = std::nullopt; 421 } 422 } 423 } 424 m_unlinked.push_back(idx); 425 if (!exists_anywhere) Compact(); 426 } 427 428 // Functions related to various normalization/application steps. 429 /** Get rid of unlinked Entry objects in m_entries, if possible (this changes the GraphIndex 430 * values for remaining Entry objects, so this only does something when no to-be-applied 431 * operations or staged removals referring to GraphIndexes remain). */ 432 void Compact() noexcept; 433 /** If cluster is not in staging, copy it there, and return a pointer to it. 434 * Staging must exist, and this modifies the locators of its 435 * transactions from inherited (P,M) to explicit (P,P). */ 436 Cluster* PullIn(Cluster* cluster) noexcept; 437 /** Apply all removals queued up in m_to_remove to the relevant Clusters (which get a 438 * NEEDS_SPLIT* QualityLevel) up to the specified level. */ 439 void ApplyRemovals(int up_to_level) noexcept; 440 /** Split an individual cluster. */ 441 void Split(Cluster& cluster) noexcept; 442 /** Split all clusters that need splitting up to the specified level. */ 443 void SplitAll(int up_to_level) noexcept; 444 /** Populate m_group_data based on m_deps_to_add in the specified level. */ 445 void GroupClusters(int level) noexcept; 446 /** Merge the specified clusters. */ 447 void Merge(std::span<Cluster*> to_merge) noexcept; 448 /** Apply all m_deps_to_add to the relevant Clusters in the specified level. */ 449 void ApplyDependencies(int level) noexcept; 450 /** Make a specified Cluster have quality ACCEPTABLE or OPTIMAL. */ 451 void MakeAcceptable(Cluster& cluster) noexcept; 452 /** Make all Clusters at the specified level have quality ACCEPTABLE or OPTIMAL. */ 453 void MakeAllAcceptable(int level) noexcept; 454 455 // Implementations for the public TxGraph interface. 456 457 Ref AddTransaction(const FeePerWeight& feerate) noexcept final; 458 void RemoveTransaction(const Ref& arg) noexcept final; 459 void AddDependency(const Ref& parent, const Ref& child) noexcept final; 460 void SetTransactionFee(const Ref&, int64_t fee) noexcept final; 461 462 void DoWork() noexcept final; 463 464 void StartStaging() noexcept final; 465 void CommitStaging() noexcept final; 466 void AbortStaging() noexcept final; 467 bool HaveStaging() const noexcept final { return m_staging_clusterset.has_value(); } 468 469 bool Exists(const Ref& arg, bool main_only = false) noexcept final; 470 FeePerWeight GetMainChunkFeerate(const Ref& arg) noexcept final; 471 FeePerWeight GetIndividualFeerate(const Ref& arg) noexcept final; 472 std::vector<Ref*> GetCluster(const Ref& arg, bool main_only = false) noexcept final; 473 std::vector<Ref*> GetAncestors(const Ref& arg, bool main_only = false) noexcept final; 474 std::vector<Ref*> GetDescendants(const Ref& arg, bool main_only = false) noexcept final; 475 std::vector<Ref*> GetAncestorsUnion(std::span<const Ref* const> args, bool main_only = false) noexcept final; 476 std::vector<Ref*> GetDescendantsUnion(std::span<const Ref* const> args, bool main_only = false) noexcept final; 477 GraphIndex GetTransactionCount(bool main_only = false) noexcept final; 478 bool IsOversized(bool main_only = false) noexcept final; 479 std::strong_ordering CompareMainOrder(const Ref& a, const Ref& b) noexcept final; 480 GraphIndex CountDistinctClusters(std::span<const Ref* const> refs, bool main_only = false) noexcept final; 481 482 void SanityCheck() const final; 483 }; 484 485 TxGraphImpl::ClusterSet& TxGraphImpl::GetClusterSet(int level) noexcept 486 { 487 if (level == 0) return m_main_clusterset; 488 Assume(level == 1); 489 Assume(m_staging_clusterset.has_value()); 490 return *m_staging_clusterset; 491 } 492 493 const TxGraphImpl::ClusterSet& TxGraphImpl::GetClusterSet(int level) const noexcept 494 { 495 if (level == 0) return m_main_clusterset; 496 Assume(level == 1); 497 Assume(m_staging_clusterset.has_value()); 498 return *m_staging_clusterset; 499 } 500 501 void TxGraphImpl::ClearLocator(int level, GraphIndex idx) noexcept 502 { 503 auto& entry = m_entries[idx]; 504 auto& clusterset = GetClusterSet(level); 505 Assume(entry.m_locator[level].IsPresent()); 506 // Change the locator from Present to Missing or Removed. 507 if (level == 0 || !entry.m_locator[level - 1].IsPresent()) { 508 entry.m_locator[level].SetMissing(); 509 } else { 510 entry.m_locator[level].SetRemoved(); 511 clusterset.m_removed.push_back(idx); 512 } 513 // Update the transaction count. 514 --clusterset.m_txcount; 515 // If clearing main, adjust the status of Locators of this transaction in staging, if it exists. 516 if (level == 0 && GetTopLevel() == 1) { 517 if (entry.m_locator[1].IsRemoved()) { 518 entry.m_locator[1].SetMissing(); 519 } else if (!entry.m_locator[1].IsPresent()) { 520 --m_staging_clusterset->m_txcount; 521 } 522 } 523 } 524 525 void Cluster::Updated(TxGraphImpl& graph) noexcept 526 { 527 // Update all the Locators for this Cluster's Entry objects. 528 for (DepGraphIndex idx : m_linearization) { 529 auto& entry = graph.m_entries[m_mapping[idx]]; 530 entry.m_locator[m_level].SetPresent(this, idx); 531 } 532 // If this is for the main graph (level = 0), and the Cluster's quality is ACCEPTABLE or 533 // OPTIMAL, compute its chunking and store its information in the Entry's m_main_lin_index 534 // and m_main_chunk_feerate. These fields are only accessed after making the entire graph 535 // ACCEPTABLE, so it is pointless to compute these if we haven't reached that quality level 536 // yet. 537 if (m_level == 0 && IsAcceptable()) { 538 LinearizationChunking chunking(m_depgraph, m_linearization); 539 LinearizationIndex lin_idx{0}; 540 // Iterate over the chunks. 541 for (unsigned chunk_idx = 0; chunk_idx < chunking.NumChunksLeft(); ++chunk_idx) { 542 auto chunk = chunking.GetChunk(chunk_idx); 543 Assume(chunk.transactions.Any()); 544 // Iterate over the transactions in the linearization, which must match those in chunk. 545 do { 546 DepGraphIndex idx = m_linearization[lin_idx]; 547 GraphIndex graph_idx = m_mapping[idx]; 548 auto& entry = graph.m_entries[graph_idx]; 549 entry.m_main_lin_index = lin_idx++; 550 entry.m_main_chunk_feerate = FeePerWeight::FromFeeFrac(chunk.feerate); 551 Assume(chunk.transactions[idx]); 552 chunk.transactions.Reset(idx); 553 } while(chunk.transactions.Any()); 554 } 555 } 556 } 557 558 void Cluster::GetConflicts(const TxGraphImpl& graph, std::vector<Cluster*>& out) const noexcept 559 { 560 Assume(m_level == 1); 561 for (auto i : m_linearization) { 562 auto& entry = graph.m_entries[m_mapping[i]]; 563 // For every transaction Entry in this Cluster, if it also exists in a lower-level Cluster, 564 // then that Cluster conflicts. 565 if (entry.m_locator[0].IsPresent()) { 566 out.push_back(entry.m_locator[0].cluster); 567 } 568 } 569 } 570 571 std::vector<Cluster*> TxGraphImpl::GetConflicts() const noexcept 572 { 573 Assume(GetTopLevel() == 1); 574 auto& clusterset = GetClusterSet(1); 575 std::vector<Cluster*> ret; 576 // All main Clusters containing transactions in m_removed (so (P,R) ones) are conflicts. 577 for (auto i : clusterset.m_removed) { 578 auto& entry = m_entries[i]; 579 if (entry.m_locator[0].IsPresent()) { 580 ret.push_back(entry.m_locator[0].cluster); 581 } 582 } 583 // Then go over all Clusters at this level, and find their conflicts (the (P,P) ones). 584 for (int quality = 0; quality < int(QualityLevel::NONE); ++quality) { 585 auto& clusters = clusterset.m_clusters[quality]; 586 for (const auto& cluster : clusters) { 587 cluster->GetConflicts(*this, ret); 588 } 589 } 590 // Deduplicate the result (the same Cluster may appear multiple times). 591 std::sort(ret.begin(), ret.end(), [](Cluster* a, Cluster* b) noexcept { return CompareClusters(a, b) < 0; }); 592 ret.erase(std::unique(ret.begin(), ret.end()), ret.end()); 593 return ret; 594 } 595 596 Cluster* Cluster::CopyToStaging(TxGraphImpl& graph) const noexcept 597 { 598 // Construct an empty Cluster. 599 auto ret = std::make_unique<Cluster>(graph.m_next_sequence_counter++); 600 auto ptr = ret.get(); 601 // Copy depgraph, mapping, and linearization/ 602 ptr->m_depgraph = m_depgraph; 603 ptr->m_mapping = m_mapping; 604 ptr->m_linearization = m_linearization; 605 // Insert the new Cluster into the graph. 606 graph.InsertCluster(1, std::move(ret), m_quality); 607 // Update its Locators. 608 ptr->Updated(graph); 609 return ptr; 610 } 611 612 void Cluster::ApplyRemovals(TxGraphImpl& graph, std::span<GraphIndex>& to_remove) noexcept 613 { 614 // Iterate over the prefix of to_remove that applies to this cluster. 615 Assume(!to_remove.empty()); 616 SetType todo; 617 do { 618 GraphIndex idx = to_remove.front(); 619 Assume(idx < graph.m_entries.size()); 620 auto& entry = graph.m_entries[idx]; 621 auto& locator = entry.m_locator[m_level]; 622 // Stop once we hit an entry that applies to another Cluster. 623 if (locator.cluster != this) break; 624 // - Remember it in a set of to-remove DepGraphIndexes. 625 todo.Set(locator.index); 626 // - Remove from m_mapping. This isn't strictly necessary as unused positions in m_mapping 627 // are just never accessed, but set it to -1 here to increase the ability to detect a bug 628 // that causes it to be accessed regardless. 629 m_mapping[locator.index] = GraphIndex(-1); 630 // - Remove its linearization index from the Entry (if in main). 631 if (m_level == 0) { 632 entry.m_main_lin_index = LinearizationIndex(-1); 633 } 634 // - Mark it as missing/removed in the Entry's locator. 635 graph.ClearLocator(m_level, idx); 636 to_remove = to_remove.subspan(1); 637 } while(!to_remove.empty()); 638 639 auto quality = m_quality; 640 Assume(todo.Any()); 641 // Wipe from the Cluster's DepGraph (this is O(n) regardless of the number of entries 642 // removed, so we benefit from batching all the removals). 643 m_depgraph.RemoveTransactions(todo); 644 m_mapping.resize(m_depgraph.PositionRange()); 645 646 // First remove all removals at the end of the linearization. 647 while (!m_linearization.empty() && todo[m_linearization.back()]) { 648 todo.Reset(m_linearization.back()); 649 m_linearization.pop_back(); 650 } 651 if (todo.None()) { 652 // If no further removals remain, and thus all removals were at the end, we may be able 653 // to leave the cluster at a better quality level. 654 if (IsAcceptable(/*after_split=*/true)) { 655 quality = QualityLevel::NEEDS_SPLIT_ACCEPTABLE; 656 } else { 657 quality = QualityLevel::NEEDS_SPLIT; 658 } 659 } else { 660 // If more removals remain, filter those out of m_linearization. 661 m_linearization.erase(std::remove_if( 662 m_linearization.begin(), 663 m_linearization.end(), 664 [&](auto pos) { return todo[pos]; }), m_linearization.end()); 665 quality = QualityLevel::NEEDS_SPLIT; 666 } 667 graph.SetClusterQuality(m_level, m_quality, m_setindex, quality); 668 Updated(graph); 669 } 670 671 void Cluster::Clear(TxGraphImpl& graph) noexcept 672 { 673 for (auto i : m_linearization) { 674 graph.ClearLocator(m_level, m_mapping[i]); 675 } 676 m_depgraph = {}; 677 m_linearization.clear(); 678 m_mapping.clear(); 679 } 680 681 void Cluster::MoveToMain(TxGraphImpl& graph) noexcept 682 { 683 Assume(m_level == 1); 684 for (auto i : m_linearization) { 685 GraphIndex idx = m_mapping[i]; 686 auto& entry = graph.m_entries[idx]; 687 entry.m_locator[1].SetMissing(); 688 } 689 auto quality = m_quality; 690 auto cluster = graph.ExtractCluster(1, quality, m_setindex); 691 graph.InsertCluster(0, std::move(cluster), quality); 692 Updated(graph); 693 } 694 695 bool Cluster::Split(TxGraphImpl& graph) noexcept 696 { 697 // This function can only be called when the Cluster needs splitting. 698 Assume(NeedsSplitting()); 699 // Determine the new quality the split-off Clusters will have. 700 QualityLevel new_quality = IsAcceptable(/*after_split=*/true) ? QualityLevel::ACCEPTABLE 701 : QualityLevel::NEEDS_RELINEARIZE; 702 // If we're going to produce ACCEPTABLE clusters (i.e., when in NEEDS_SPLIT_ACCEPTABLE), we 703 // need to post-linearize to make sure the split-out versions are all connected (as 704 // connectivity may have changed by removing part of the cluster). This could be done on each 705 // resulting split-out cluster separately, but it is simpler to do it once up front before 706 // splitting. This step is not necessary if the resulting clusters are NEEDS_RELINEARIZE, as 707 // they will be post-linearized anyway in MakeAcceptable(). 708 if (new_quality == QualityLevel::ACCEPTABLE) { 709 PostLinearize(m_depgraph, m_linearization); 710 } 711 /** Which positions are still left in this Cluster. */ 712 auto todo = m_depgraph.Positions(); 713 /** Mapping from transaction positions in this Cluster to the Cluster where it ends up, and 714 * its position therein. */ 715 std::vector<std::pair<Cluster*, DepGraphIndex>> remap(m_depgraph.PositionRange()); 716 std::vector<Cluster*> new_clusters; 717 bool first{true}; 718 // Iterate over the connected components of this Cluster's m_depgraph. 719 while (todo.Any()) { 720 auto component = m_depgraph.FindConnectedComponent(todo); 721 if (first && component == todo) { 722 // The existing Cluster is an entire component. Leave it be, but update its quality. 723 Assume(todo == m_depgraph.Positions()); 724 graph.SetClusterQuality(m_level, m_quality, m_setindex, new_quality); 725 // If this made the quality ACCEPTABLE or OPTIMAL, we need to compute and cache its 726 // chunking. 727 Updated(graph); 728 return false; 729 } 730 first = false; 731 // Construct a new Cluster to hold the found component. 732 auto new_cluster = std::make_unique<Cluster>(graph.m_next_sequence_counter++); 733 new_clusters.push_back(new_cluster.get()); 734 // Remember that all the component's transactions go to this new Cluster. The positions 735 // will be determined below, so use -1 for now. 736 for (auto i : component) { 737 remap[i] = {new_cluster.get(), DepGraphIndex(-1)}; 738 } 739 graph.InsertCluster(m_level, std::move(new_cluster), new_quality); 740 todo -= component; 741 } 742 // Redistribute the transactions. 743 for (auto i : m_linearization) { 744 /** The cluster which transaction originally in position i is moved to. */ 745 Cluster* new_cluster = remap[i].first; 746 // Copy the transaction to the new cluster's depgraph, and remember the position. 747 remap[i].second = new_cluster->m_depgraph.AddTransaction(m_depgraph.FeeRate(i)); 748 // Create new mapping entry. 749 new_cluster->m_mapping.push_back(m_mapping[i]); 750 // Create a new linearization entry. As we're only appending transactions, they equal the 751 // DepGraphIndex. 752 new_cluster->m_linearization.push_back(remap[i].second); 753 } 754 // Redistribute the dependencies. 755 for (auto i : m_linearization) { 756 /** The cluster transaction in position i is moved to. */ 757 Cluster* new_cluster = remap[i].first; 758 // Copy its parents, translating positions. 759 SetType new_parents; 760 for (auto par : m_depgraph.GetReducedParents(i)) new_parents.Set(remap[par].second); 761 new_cluster->m_depgraph.AddDependencies(new_parents, remap[i].second); 762 } 763 // Update all the Locators of moved transactions. 764 for (Cluster* new_cluster : new_clusters) { 765 new_cluster->Updated(graph); 766 } 767 // Wipe this Cluster, and return that it needs to be deleted. 768 m_depgraph = DepGraph<SetType>{}; 769 m_mapping.clear(); 770 m_linearization.clear(); 771 return true; 772 } 773 774 void Cluster::Merge(TxGraphImpl& graph, Cluster& other) noexcept 775 { 776 /** Vector to store the positions in this Cluster for each position in other. */ 777 std::vector<DepGraphIndex> remap(other.m_depgraph.PositionRange()); 778 // Iterate over all transactions in the other Cluster (the one being absorbed). 779 for (auto pos : other.m_linearization) { 780 auto idx = other.m_mapping[pos]; 781 // Copy the transaction into this Cluster, and remember its position. 782 auto new_pos = m_depgraph.AddTransaction(other.m_depgraph.FeeRate(pos)); 783 remap[pos] = new_pos; 784 if (new_pos == m_mapping.size()) { 785 m_mapping.push_back(idx); 786 } else { 787 m_mapping[new_pos] = idx; 788 } 789 m_linearization.push_back(new_pos); 790 // Copy the transaction's dependencies, translating them using remap. Note that since 791 // pos iterates over other.m_linearization, which is in topological order, all parents 792 // of pos should already be in remap. 793 SetType parents; 794 for (auto par : other.m_depgraph.GetReducedParents(pos)) { 795 parents.Set(remap[par]); 796 } 797 m_depgraph.AddDependencies(parents, remap[pos]); 798 // Update the transaction's Locator. There is no need to call Updated() to update chunk 799 // feerates, as Updated() will be invoked by Cluster::ApplyDependencies on the resulting 800 // merged Cluster later anyway). 801 graph.m_entries[idx].m_locator[m_level].SetPresent(this, new_pos); 802 } 803 // Purge the other Cluster, now that everything has been moved. 804 other.m_depgraph = DepGraph<SetType>{}; 805 other.m_linearization.clear(); 806 other.m_mapping.clear(); 807 } 808 809 void Cluster::ApplyDependencies(TxGraphImpl& graph, std::span<std::pair<GraphIndex, GraphIndex>> to_apply) noexcept 810 { 811 // This function is invoked by TxGraphImpl::ApplyDependencies after merging groups of Clusters 812 // between which dependencies are added, which simply concatenates their linearizations. Invoke 813 // PostLinearize, which has the effect that the linearization becomes a merge-sort of the 814 // constituent linearizations. Do this here rather than in Cluster::Merge, because this 815 // function is only invoked once per merged Cluster, rather than once per constituent one. 816 // This concatenation + post-linearization could be replaced with an explicit merge-sort. 817 PostLinearize(m_depgraph, m_linearization); 818 819 // Sort the list of dependencies to apply by child, so those can be applied in batch. 820 std::sort(to_apply.begin(), to_apply.end(), [](auto& a, auto& b) { return a.second < b.second; }); 821 // Iterate over groups of to-be-added dependencies with the same child. 822 auto it = to_apply.begin(); 823 while (it != to_apply.end()) { 824 auto& first_child = graph.m_entries[it->second].m_locator[m_level]; 825 const auto child_idx = first_child.index; 826 // Iterate over all to-be-added dependencies within that same child, gather the relevant 827 // parents. 828 SetType parents; 829 while (it != to_apply.end()) { 830 auto& child = graph.m_entries[it->second].m_locator[m_level]; 831 auto& parent = graph.m_entries[it->first].m_locator[m_level]; 832 Assume(child.cluster == this && parent.cluster == this); 833 if (child.index != child_idx) break; 834 parents.Set(parent.index); 835 ++it; 836 } 837 // Push all dependencies to the underlying DepGraph. Note that this is O(N) in the size of 838 // the cluster, regardless of the number of parents being added, so batching them together 839 // has a performance benefit. 840 m_depgraph.AddDependencies(parents, child_idx); 841 } 842 843 // Finally fix the linearization, as the new dependencies may have invalidated the 844 // linearization, and post-linearize it to fix up the worst problems with it. 845 FixLinearization(m_depgraph, m_linearization); 846 PostLinearize(m_depgraph, m_linearization); 847 848 // Finally push the changes to graph.m_entries. 849 Updated(graph); 850 } 851 852 TxGraphImpl::~TxGraphImpl() noexcept 853 { 854 // If Refs outlive the TxGraphImpl they refer to, unlink them, so that their destructor does not 855 // try to reach into a non-existing TxGraphImpl anymore. 856 for (auto& entry : m_entries) { 857 if (entry.m_ref != nullptr) { 858 GetRefGraph(*entry.m_ref) = nullptr; 859 } 860 } 861 } 862 863 std::unique_ptr<Cluster> TxGraphImpl::ExtractCluster(int level, QualityLevel quality, ClusterSetIndex setindex) noexcept 864 { 865 Assume(quality != QualityLevel::NONE); 866 867 auto& clusterset = GetClusterSet(level); 868 auto& quality_clusters = clusterset.m_clusters[int(quality)]; 869 Assume(setindex < quality_clusters.size()); 870 871 // Extract the Cluster-owning unique_ptr. 872 std::unique_ptr<Cluster> ret = std::move(quality_clusters[setindex]); 873 ret->m_quality = QualityLevel::NONE; 874 ret->m_setindex = ClusterSetIndex(-1); 875 ret->m_level = -1; 876 877 // Clean up space in quality_cluster. 878 auto max_setindex = quality_clusters.size() - 1; 879 if (setindex != max_setindex) { 880 // If the cluster was not the last element of quality_clusters, move that to take its place. 881 quality_clusters.back()->m_setindex = setindex; 882 quality_clusters.back()->m_level = level; 883 quality_clusters[setindex] = std::move(quality_clusters.back()); 884 } 885 // The last element of quality_clusters is now unused; drop it. 886 quality_clusters.pop_back(); 887 888 return ret; 889 } 890 891 ClusterSetIndex TxGraphImpl::InsertCluster(int level, std::unique_ptr<Cluster>&& cluster, QualityLevel quality) noexcept 892 { 893 // Cannot insert with quality level NONE (as that would mean not inserted). 894 Assume(quality != QualityLevel::NONE); 895 // The passed-in Cluster must not currently be in the TxGraphImpl. 896 Assume(cluster->m_quality == QualityLevel::NONE); 897 898 // Append it at the end of the relevant TxGraphImpl::m_cluster. 899 auto& clusterset = GetClusterSet(level); 900 auto& quality_clusters = clusterset.m_clusters[int(quality)]; 901 ClusterSetIndex ret = quality_clusters.size(); 902 cluster->m_quality = quality; 903 cluster->m_setindex = ret; 904 cluster->m_level = level; 905 quality_clusters.push_back(std::move(cluster)); 906 return ret; 907 } 908 909 void TxGraphImpl::SetClusterQuality(int level, QualityLevel old_quality, ClusterSetIndex old_index, QualityLevel new_quality) noexcept 910 { 911 Assume(new_quality != QualityLevel::NONE); 912 913 // Don't do anything if the quality did not change. 914 if (old_quality == new_quality) return; 915 // Extract the cluster from where it currently resides. 916 auto cluster_ptr = ExtractCluster(level, old_quality, old_index); 917 // And re-insert it where it belongs. 918 InsertCluster(level, std::move(cluster_ptr), new_quality); 919 } 920 921 void TxGraphImpl::DeleteCluster(Cluster& cluster) noexcept 922 { 923 // Extract the cluster from where it currently resides. 924 auto cluster_ptr = ExtractCluster(cluster.m_level, cluster.m_quality, cluster.m_setindex); 925 // And throw it away. 926 cluster_ptr.reset(); 927 } 928 929 Cluster* TxGraphImpl::FindCluster(GraphIndex idx, int level) const noexcept 930 { 931 Assume(level >= 0 && level <= GetTopLevel()); 932 auto& entry = m_entries[idx]; 933 // Search the entry's locators from top to bottom. 934 for (int l = level; l >= 0; --l) { 935 // If the locator is missing, dig deeper; it may exist at a lower level and therefore be 936 // implicitly existing at this level too. 937 if (entry.m_locator[l].IsMissing()) continue; 938 // If the locator has the entry marked as explicitly removed, stop. 939 if (entry.m_locator[l].IsRemoved()) break; 940 // Otherwise, we have found the topmost ClusterSet that contains this entry. 941 return entry.m_locator[l].cluster; 942 } 943 // If no non-empty locator was found, or an explicitly removed was hit, return nothing. 944 return nullptr; 945 } 946 947 Cluster* TxGraphImpl::PullIn(Cluster* cluster) noexcept 948 { 949 int to_level = GetTopLevel(); 950 Assume(to_level == 1); 951 int level = cluster->m_level; 952 Assume(level <= to_level); 953 // Copy the Cluster from main to staging, if it's not already there. 954 if (level == 0) { 955 // Make the Cluster Acceptable before copying. This isn't strictly necessary, but doing it 956 // now avoids doing double work later. 957 MakeAcceptable(*cluster); 958 cluster = cluster->CopyToStaging(*this); 959 } 960 return cluster; 961 } 962 963 void TxGraphImpl::ApplyRemovals(int up_to_level) noexcept 964 { 965 Assume(up_to_level >= 0 && up_to_level <= GetTopLevel()); 966 for (int level = 0; level <= up_to_level; ++level) { 967 auto& clusterset = GetClusterSet(level); 968 auto& to_remove = clusterset.m_to_remove; 969 // Skip if there is nothing to remove in this level. 970 if (to_remove.empty()) continue; 971 // Pull in all Clusters that are not in staging. 972 if (level == 1) { 973 for (GraphIndex index : to_remove) { 974 auto cluster = FindCluster(index, level); 975 if (cluster != nullptr) PullIn(cluster); 976 } 977 } 978 // Group the set of to-be-removed entries by Cluster::m_sequence. 979 std::sort(to_remove.begin(), to_remove.end(), [&](GraphIndex a, GraphIndex b) noexcept { 980 Cluster* cluster_a = m_entries[a].m_locator[level].cluster; 981 Cluster* cluster_b = m_entries[b].m_locator[level].cluster; 982 return CompareClusters(cluster_a, cluster_b) < 0; 983 }); 984 // Process per Cluster. 985 std::span to_remove_span{to_remove}; 986 while (!to_remove_span.empty()) { 987 Cluster* cluster = m_entries[to_remove_span.front()].m_locator[level].cluster; 988 if (cluster != nullptr) { 989 // If the first to_remove_span entry's Cluster exists, hand to_remove_span to it, so it 990 // can pop off whatever applies to it. 991 cluster->ApplyRemovals(*this, to_remove_span); 992 } else { 993 // Otherwise, skip this already-removed entry. This may happen when 994 // RemoveTransaction was called twice on the same Ref, for example. 995 to_remove_span = to_remove_span.subspan(1); 996 } 997 } 998 to_remove.clear(); 999 } 1000 Compact(); 1001 } 1002 1003 void TxGraphImpl::SwapIndexes(GraphIndex a, GraphIndex b) noexcept 1004 { 1005 Assume(a < m_entries.size()); 1006 Assume(b < m_entries.size()); 1007 // Swap the Entry objects. 1008 std::swap(m_entries[a], m_entries[b]); 1009 // Iterate over both objects. 1010 for (int i = 0; i < 2; ++i) { 1011 GraphIndex idx = i ? b : a; 1012 Entry& entry = m_entries[idx]; 1013 // Update linked Ref, if any exists. 1014 if (entry.m_ref) GetRefIndex(*entry.m_ref) = idx; 1015 // Update the locators for both levels. The rest of the Entry information will not change, 1016 // so no need to invoke Cluster::Updated(). 1017 for (int level = 0; level < MAX_LEVELS; ++level) { 1018 Locator& locator = entry.m_locator[level]; 1019 if (locator.IsPresent()) { 1020 locator.cluster->UpdateMapping(locator.index, idx); 1021 } 1022 } 1023 } 1024 } 1025 1026 void TxGraphImpl::Compact() noexcept 1027 { 1028 // We cannot compact while any to-be-applied operations or staged removals remain as we'd need 1029 // to rewrite them. It is easier to delay the compaction until they have been applied. 1030 if (!m_main_clusterset.m_deps_to_add.empty()) return; 1031 if (!m_main_clusterset.m_to_remove.empty()) return; 1032 Assume(m_main_clusterset.m_removed.empty()); // non-staging m_removed is always empty 1033 if (m_staging_clusterset.has_value()) { 1034 if (!m_staging_clusterset->m_deps_to_add.empty()) return; 1035 if (!m_staging_clusterset->m_to_remove.empty()) return; 1036 if (!m_staging_clusterset->m_removed.empty()) return; 1037 } 1038 1039 // Sort the GraphIndexes that need to be cleaned up. They are sorted in reverse, so the last 1040 // ones get processed first. This means earlier-processed GraphIndexes will not cause moving of 1041 // later-processed ones during the "swap with end of m_entries" step below (which might 1042 // invalidate them). 1043 std::sort(m_unlinked.begin(), m_unlinked.end(), std::greater{}); 1044 1045 auto last = GraphIndex(-1); 1046 for (GraphIndex idx : m_unlinked) { 1047 // m_unlinked should never contain the same GraphIndex twice (the code below would fail 1048 // if so, because GraphIndexes get invalidated by removing them). 1049 Assume(idx != last); 1050 last = idx; 1051 1052 // Make sure the entry is unlinked. 1053 Entry& entry = m_entries[idx]; 1054 Assume(entry.m_ref == nullptr); 1055 // Make sure the entry does not occur in the graph. 1056 for (int level = 0; level < MAX_LEVELS; ++level) { 1057 Assume(!entry.m_locator[level].IsPresent()); 1058 } 1059 1060 // Move the entry to the end. 1061 if (idx != m_entries.size() - 1) SwapIndexes(idx, m_entries.size() - 1); 1062 // Drop the entry for idx, now that it is at the end. 1063 m_entries.pop_back(); 1064 } 1065 m_unlinked.clear(); 1066 } 1067 1068 void TxGraphImpl::Split(Cluster& cluster) noexcept 1069 { 1070 // To split a Cluster, first make sure all removals are applied (as we might need to split 1071 // again afterwards otherwise). 1072 ApplyRemovals(cluster.m_level); 1073 bool del = cluster.Split(*this); 1074 if (del) { 1075 // Cluster::Split reports whether the Cluster is to be deleted. 1076 DeleteCluster(cluster); 1077 } 1078 } 1079 1080 void TxGraphImpl::SplitAll(int up_to_level) noexcept 1081 { 1082 Assume(up_to_level >= 0 && up_to_level <= GetTopLevel()); 1083 // Before splitting all Cluster, first make sure all removals are applied. 1084 ApplyRemovals(up_to_level); 1085 for (int level = 0; level <= up_to_level; ++level) { 1086 for (auto quality : {QualityLevel::NEEDS_SPLIT, QualityLevel::NEEDS_SPLIT_ACCEPTABLE}) { 1087 auto& queue = GetClusterSet(level).m_clusters[int(quality)]; 1088 while (!queue.empty()) { 1089 Split(*queue.back().get()); 1090 } 1091 } 1092 } 1093 } 1094 1095 void TxGraphImpl::GroupClusters(int level) noexcept 1096 { 1097 auto& clusterset = GetClusterSet(level); 1098 // If the groupings have been computed already, nothing is left to be done. 1099 if (clusterset.m_group_data.has_value()) return; 1100 1101 // Before computing which Clusters need to be merged together, first apply all removals and 1102 // split the Clusters into connected components. If we would group first, we might end up 1103 // with inefficient and/or oversized Clusters which just end up being split again anyway. 1104 SplitAll(level); 1105 1106 /** Annotated clusters: an entry for each Cluster, together with the sequence number for the 1107 * representative for the partition it is in (initially its own, later that of the 1108 * to-be-merged group). */ 1109 std::vector<std::pair<Cluster*, uint64_t>> an_clusters; 1110 /** Annotated dependencies: an entry for each m_deps_to_add entry (excluding ones that apply 1111 * to removed transactions), together with the sequence number of the representative root of 1112 * Clusters it applies to (initially that of the child Cluster, later that of the 1113 * to-be-merged group). */ 1114 std::vector<std::pair<std::pair<GraphIndex, GraphIndex>, uint64_t>> an_deps; 1115 1116 // Construct a an_clusters entry for every parent and child in the to-be-applied dependencies, 1117 // and an an_deps entry for each dependency to be applied. 1118 an_deps.reserve(clusterset.m_deps_to_add.size()); 1119 for (const auto& [par, chl] : clusterset.m_deps_to_add) { 1120 auto par_cluster = FindCluster(par, level); 1121 auto chl_cluster = FindCluster(chl, level); 1122 // Skip dependencies for which the parent or child transaction is removed. 1123 if (par_cluster == nullptr || chl_cluster == nullptr) continue; 1124 an_clusters.emplace_back(par_cluster, par_cluster->m_sequence); 1125 // Do not include a duplicate when parent and child are identical, as it'll be removed 1126 // below anyway. 1127 if (chl_cluster != par_cluster) an_clusters.emplace_back(chl_cluster, chl_cluster->m_sequence); 1128 // Add entry to an_deps, using the child sequence number. 1129 an_deps.emplace_back(std::pair{par, chl}, chl_cluster->m_sequence); 1130 } 1131 // Sort and deduplicate an_clusters, so we end up with a sorted list of all involved Clusters 1132 // to which dependencies apply. 1133 std::sort(an_clusters.begin(), an_clusters.end(), [](auto& a, auto& b) noexcept { return a.second < b.second; }); 1134 an_clusters.erase(std::unique(an_clusters.begin(), an_clusters.end()), an_clusters.end()); 1135 // Sort an_deps by applying the same order to the involved child cluster. 1136 std::sort(an_deps.begin(), an_deps.end(), [&](auto& a, auto& b) noexcept { return a.second < b.second; }); 1137 1138 // Run the union-find algorithm to to find partitions of the input Clusters which need to be 1139 // grouped together. See https://en.wikipedia.org/wiki/Disjoint-set_data_structure. 1140 { 1141 /** Each PartitionData entry contains information about a single input Cluster. */ 1142 struct PartitionData 1143 { 1144 /** The sequence number of the cluster this holds information for. */ 1145 uint64_t sequence; 1146 /** All PartitionData entries belonging to the same partition are organized in a tree. 1147 * Each element points to its parent, or to itself if it is the root. The root is then 1148 * a representative for the entire tree, and can be found by walking upwards from any 1149 * element. */ 1150 PartitionData* parent; 1151 /** (only if this is a root, so when parent == this) An upper bound on the height of 1152 * tree for this partition. */ 1153 unsigned rank; 1154 }; 1155 /** Information about each input Cluster. Sorted by Cluster::m_sequence. */ 1156 std::vector<PartitionData> partition_data; 1157 1158 /** Given a Cluster, find its corresponding PartitionData. */ 1159 auto locate_fn = [&](uint64_t sequence) noexcept -> PartitionData* { 1160 auto it = std::lower_bound(partition_data.begin(), partition_data.end(), sequence, 1161 [](auto& a, uint64_t seq) noexcept { return a.sequence < seq; }); 1162 Assume(it != partition_data.end()); 1163 Assume(it->sequence == sequence); 1164 return &*it; 1165 }; 1166 1167 /** Given a PartitionData, find the root of the tree it is in (its representative). */ 1168 static constexpr auto find_root_fn = [](PartitionData* data) noexcept -> PartitionData* { 1169 while (data->parent != data) { 1170 // Replace pointers to parents with pointers to grandparents. 1171 // See https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Finding_set_representatives. 1172 auto par = data->parent; 1173 data->parent = par->parent; 1174 data = par; 1175 } 1176 return data; 1177 }; 1178 1179 /** Given two PartitionDatas, union the partitions they are in, and return their 1180 * representative. */ 1181 static constexpr auto union_fn = [](PartitionData* arg1, PartitionData* arg2) noexcept { 1182 // Find the roots of the trees, and bail out if they are already equal (which would 1183 // mean they are in the same partition already). 1184 auto rep1 = find_root_fn(arg1); 1185 auto rep2 = find_root_fn(arg2); 1186 if (rep1 == rep2) return rep1; 1187 // Pick the lower-rank root to become a child of the higher-rank one. 1188 // See https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Union_by_rank. 1189 if (rep1->rank < rep2->rank) std::swap(rep1, rep2); 1190 rep2->parent = rep1; 1191 rep1->rank += (rep1->rank == rep2->rank); 1192 return rep1; 1193 }; 1194 1195 // Start by initializing every Cluster as its own singleton partition. 1196 partition_data.resize(an_clusters.size()); 1197 for (size_t i = 0; i < an_clusters.size(); ++i) { 1198 partition_data[i].sequence = an_clusters[i].first->m_sequence; 1199 partition_data[i].parent = &partition_data[i]; 1200 partition_data[i].rank = 0; 1201 } 1202 1203 // Run through all parent/child pairs in an_deps, and union the partitions their Clusters 1204 // are in. 1205 Cluster* last_chl_cluster{nullptr}; 1206 PartitionData* last_partition{nullptr}; 1207 for (const auto& [dep, _] : an_deps) { 1208 auto [par, chl] = dep; 1209 auto par_cluster = FindCluster(par, level); 1210 auto chl_cluster = FindCluster(chl, level); 1211 Assume(chl_cluster != nullptr && par_cluster != nullptr); 1212 // Nothing to do if parent and child are in the same Cluster. 1213 if (par_cluster == chl_cluster) continue; 1214 Assume(par != chl); 1215 if (chl_cluster == last_chl_cluster) { 1216 // If the child Clusters is the same as the previous iteration, union with the 1217 // tree they were in, avoiding the need for another lookup. Note that an_deps 1218 // is sorted by child Cluster, so batches with the same child are expected. 1219 last_partition = union_fn(locate_fn(par_cluster->m_sequence), last_partition); 1220 } else { 1221 last_chl_cluster = chl_cluster; 1222 last_partition = union_fn(locate_fn(par_cluster->m_sequence), locate_fn(chl_cluster->m_sequence)); 1223 } 1224 } 1225 1226 // Update the sequence numbers in an_clusters and an_deps to be those of the partition 1227 // representative. 1228 auto deps_it = an_deps.begin(); 1229 for (size_t i = 0; i < partition_data.size(); ++i) { 1230 auto& data = partition_data[i]; 1231 // Find the sequence of the representative of the partition Cluster i is in, and store 1232 // it with the Cluster. 1233 auto rep_seq = find_root_fn(&data)->sequence; 1234 an_clusters[i].second = rep_seq; 1235 // Find all dependencies whose child Cluster is Cluster i, and annotate them with rep. 1236 while (deps_it != an_deps.end()) { 1237 auto [par, chl] = deps_it->first; 1238 auto chl_cluster = FindCluster(chl, level); 1239 Assume(chl_cluster != nullptr); 1240 if (chl_cluster->m_sequence > data.sequence) break; 1241 deps_it->second = rep_seq; 1242 ++deps_it; 1243 } 1244 } 1245 } 1246 1247 // Sort both an_clusters and an_deps by sequence number of the representative of the 1248 // partition they are in, grouping all those applying to the same partition together. 1249 std::sort(an_deps.begin(), an_deps.end(), [](auto& a, auto& b) noexcept { return a.second < b.second; }); 1250 std::sort(an_clusters.begin(), an_clusters.end(), [](auto& a, auto& b) noexcept { return a.second < b.second; }); 1251 1252 // Translate the resulting cluster groups to the m_group_data structure, and the dependencies 1253 // back to m_deps_to_add. 1254 clusterset.m_group_data = GroupData{}; 1255 clusterset.m_group_data->m_group_clusters.reserve(an_clusters.size()); 1256 clusterset.m_group_data->m_group_oversized = false; 1257 clusterset.m_deps_to_add.clear(); 1258 clusterset.m_deps_to_add.reserve(an_deps.size()); 1259 auto an_deps_it = an_deps.begin(); 1260 auto an_clusters_it = an_clusters.begin(); 1261 while (an_clusters_it != an_clusters.end()) { 1262 // Process all clusters/dependencies belonging to the partition with representative rep. 1263 auto rep = an_clusters_it->second; 1264 // Create and initialize a new GroupData entry for the partition. 1265 auto& new_entry = clusterset.m_group_data->m_groups.emplace_back(); 1266 new_entry.m_cluster_offset = clusterset.m_group_data->m_group_clusters.size(); 1267 new_entry.m_cluster_count = 0; 1268 new_entry.m_deps_offset = clusterset.m_deps_to_add.size(); 1269 new_entry.m_deps_count = 0; 1270 uint32_t total_count{0}; 1271 // Add all its clusters to it (copying those from an_clusters to m_group_clusters). 1272 while (an_clusters_it != an_clusters.end() && an_clusters_it->second == rep) { 1273 clusterset.m_group_data->m_group_clusters.push_back(an_clusters_it->first); 1274 total_count += an_clusters_it->first->GetTxCount(); 1275 ++an_clusters_it; 1276 ++new_entry.m_cluster_count; 1277 } 1278 // Add all its dependencies to it (copying those back from an_deps to m_deps_to_add). 1279 while (an_deps_it != an_deps.end() && an_deps_it->second == rep) { 1280 clusterset.m_deps_to_add.push_back(an_deps_it->first); 1281 ++an_deps_it; 1282 ++new_entry.m_deps_count; 1283 } 1284 // Detect oversizedness. 1285 if (total_count > m_max_cluster_count) { 1286 clusterset.m_group_data->m_group_oversized = true; 1287 } 1288 } 1289 Assume(an_deps_it == an_deps.end()); 1290 Assume(an_clusters_it == an_clusters.end()); 1291 clusterset.m_oversized = clusterset.m_group_data->m_group_oversized; 1292 Compact(); 1293 } 1294 1295 void TxGraphImpl::Merge(std::span<Cluster*> to_merge) noexcept 1296 { 1297 Assume(!to_merge.empty()); 1298 // Nothing to do if a group consists of just a single Cluster. 1299 if (to_merge.size() == 1) return; 1300 1301 // Move the largest Cluster to the front of to_merge. As all transactions in other to-be-merged 1302 // Clusters will be moved to that one, putting the largest one first minimizes the number of 1303 // moves. 1304 size_t max_size_pos{0}; 1305 DepGraphIndex max_size = to_merge[max_size_pos]->GetTxCount(); 1306 for (size_t i = 1; i < to_merge.size(); ++i) { 1307 DepGraphIndex size = to_merge[i]->GetTxCount(); 1308 if (size > max_size) { 1309 max_size_pos = i; 1310 max_size = size; 1311 } 1312 } 1313 if (max_size_pos != 0) std::swap(to_merge[0], to_merge[max_size_pos]); 1314 1315 // Merge all further Clusters in the group into the first one, and delete them. 1316 for (size_t i = 1; i < to_merge.size(); ++i) { 1317 to_merge[0]->Merge(*this, *to_merge[i]); 1318 DeleteCluster(*to_merge[i]); 1319 } 1320 } 1321 1322 void TxGraphImpl::ApplyDependencies(int level) noexcept 1323 { 1324 auto& clusterset = GetClusterSet(level); 1325 // Do not bother computing groups if we already know the result will be oversized. 1326 if (clusterset.m_oversized == true) return; 1327 // Compute the groups of to-be-merged Clusters (which also applies all removals, and splits). 1328 GroupClusters(level); 1329 Assume(clusterset.m_group_data.has_value()); 1330 // Nothing to do if there are no dependencies to be added. 1331 if (clusterset.m_deps_to_add.empty()) return; 1332 // Dependencies cannot be applied if it would result in oversized clusters. 1333 if (clusterset.m_group_data->m_group_oversized) return; 1334 1335 // For each group of to-be-merged Clusters. 1336 for (const auto& group_entry : clusterset.m_group_data->m_groups) { 1337 auto cluster_span = std::span{clusterset.m_group_data->m_group_clusters} 1338 .subspan(group_entry.m_cluster_offset, group_entry.m_cluster_count); 1339 // Pull in all the Clusters that contain dependencies. 1340 if (level == 1) { 1341 for (Cluster*& cluster : cluster_span) { 1342 cluster = PullIn(cluster); 1343 } 1344 } 1345 // Invoke Merge() to merge them into a single Cluster. 1346 Merge(cluster_span); 1347 // Actually apply all to-be-added dependencies (all parents and children from this grouping 1348 // belong to the same Cluster at this point because of the merging above). 1349 auto deps_span = std::span{clusterset.m_deps_to_add} 1350 .subspan(group_entry.m_deps_offset, group_entry.m_deps_count); 1351 Assume(!deps_span.empty()); 1352 const auto& loc = m_entries[deps_span[0].second].m_locator[level]; 1353 Assume(loc.IsPresent()); 1354 loc.cluster->ApplyDependencies(*this, deps_span); 1355 } 1356 1357 // Wipe the list of to-be-added dependencies now that they are applied. 1358 clusterset.m_deps_to_add.clear(); 1359 Compact(); 1360 // Also no further Cluster mergings are needed (note that we clear, but don't set to 1361 // std::nullopt, as that would imply the groupings are unknown). 1362 clusterset.m_group_data = GroupData{}; 1363 } 1364 1365 void Cluster::Relinearize(TxGraphImpl& graph, uint64_t max_iters) noexcept 1366 { 1367 // We can only relinearize Clusters that do not need splitting. 1368 Assume(!NeedsSplitting()); 1369 // No work is required for Clusters which are already optimally linearized. 1370 if (IsOptimal()) return; 1371 // Invoke the actual linearization algorithm (passing in the existing one). 1372 uint64_t rng_seed = graph.m_rng.rand64(); 1373 auto [linearization, optimal] = Linearize(m_depgraph, max_iters, rng_seed, m_linearization); 1374 // Postlinearize if the result isn't optimal already. This guarantees (among other things) 1375 // that the chunks of the resulting linearization are all connected. 1376 if (!optimal) PostLinearize(m_depgraph, linearization); 1377 // Update the linearization. 1378 m_linearization = std::move(linearization); 1379 // Update the Cluster's quality. 1380 auto new_quality = optimal ? QualityLevel::OPTIMAL : QualityLevel::ACCEPTABLE; 1381 graph.SetClusterQuality(m_level, m_quality, m_setindex, new_quality); 1382 // Update the Entry objects. 1383 Updated(graph); 1384 } 1385 1386 void TxGraphImpl::MakeAcceptable(Cluster& cluster) noexcept 1387 { 1388 // Relinearize the Cluster if needed. 1389 if (!cluster.NeedsSplitting() && !cluster.IsAcceptable()) { 1390 cluster.Relinearize(*this, 10000); 1391 } 1392 } 1393 1394 void TxGraphImpl::MakeAllAcceptable(int level) noexcept 1395 { 1396 ApplyDependencies(level); 1397 auto& clusterset = GetClusterSet(level); 1398 if (clusterset.m_oversized == true) return; 1399 auto& queue = clusterset.m_clusters[int(QualityLevel::NEEDS_RELINEARIZE)]; 1400 while (!queue.empty()) { 1401 MakeAcceptable(*queue.back().get()); 1402 } 1403 } 1404 1405 Cluster::Cluster(uint64_t sequence) noexcept : m_sequence{sequence} {} 1406 1407 Cluster::Cluster(uint64_t sequence, TxGraphImpl& graph, const FeePerWeight& feerate, GraphIndex graph_index) noexcept : 1408 m_sequence{sequence} 1409 { 1410 // Create a new transaction in the DepGraph, and remember its position in m_mapping. 1411 auto cluster_idx = m_depgraph.AddTransaction(feerate); 1412 m_mapping.push_back(graph_index); 1413 m_linearization.push_back(cluster_idx); 1414 } 1415 1416 TxGraph::Ref TxGraphImpl::AddTransaction(const FeePerWeight& feerate) noexcept 1417 { 1418 // Construct a new Ref. 1419 Ref ret; 1420 // Construct a new Entry, and link it with the Ref. 1421 auto idx = m_entries.size(); 1422 m_entries.emplace_back(); 1423 auto& entry = m_entries.back(); 1424 entry.m_ref = &ret; 1425 GetRefGraph(ret) = this; 1426 GetRefIndex(ret) = idx; 1427 // Construct a new singleton Cluster (which is necessarily optimally linearized). 1428 auto cluster = std::make_unique<Cluster>(m_next_sequence_counter++, *this, feerate, idx); 1429 auto cluster_ptr = cluster.get(); 1430 int level = GetTopLevel(); 1431 auto& clusterset = GetClusterSet(level); 1432 InsertCluster(level, std::move(cluster), QualityLevel::OPTIMAL); 1433 cluster_ptr->Updated(*this); 1434 ++clusterset.m_txcount; 1435 // Return the Ref. 1436 return ret; 1437 } 1438 1439 void TxGraphImpl::RemoveTransaction(const Ref& arg) noexcept 1440 { 1441 // Don't do anything if the Ref is empty (which may be indicative of the transaction already 1442 // having been removed). 1443 if (GetRefGraph(arg) == nullptr) return; 1444 Assume(GetRefGraph(arg) == this); 1445 // Find the Cluster the transaction is in, and stop if it isn't in any. 1446 int level = GetTopLevel(); 1447 auto cluster = FindCluster(GetRefIndex(arg), level); 1448 if (cluster == nullptr) return; 1449 // Remember that the transaction is to be removed. 1450 auto& clusterset = GetClusterSet(level); 1451 clusterset.m_to_remove.push_back(GetRefIndex(arg)); 1452 // Wipe m_group_data (as it will need to be recomputed). 1453 clusterset.m_group_data.reset(); 1454 if (clusterset.m_oversized == true) clusterset.m_oversized = std::nullopt; 1455 } 1456 1457 void TxGraphImpl::AddDependency(const Ref& parent, const Ref& child) noexcept 1458 { 1459 // Don't do anything if either Ref is empty (which may be indicative of it having already been 1460 // removed). 1461 if (GetRefGraph(parent) == nullptr || GetRefGraph(child) == nullptr) return; 1462 Assume(GetRefGraph(parent) == this && GetRefGraph(child) == this); 1463 // Don't do anything if this is a dependency on self. 1464 if (GetRefIndex(parent) == GetRefIndex(child)) return; 1465 // Find the Cluster the parent and child transaction are in, and stop if either appears to be 1466 // already removed. 1467 int level = GetTopLevel(); 1468 auto par_cluster = FindCluster(GetRefIndex(parent), level); 1469 if (par_cluster == nullptr) return; 1470 auto chl_cluster = FindCluster(GetRefIndex(child), level); 1471 if (chl_cluster == nullptr) return; 1472 // Remember that this dependency is to be applied. 1473 auto& clusterset = GetClusterSet(level); 1474 clusterset.m_deps_to_add.emplace_back(GetRefIndex(parent), GetRefIndex(child)); 1475 // Wipe m_group_data (as it will need to be recomputed). 1476 clusterset.m_group_data.reset(); 1477 if (clusterset.m_oversized == false) clusterset.m_oversized = std::nullopt; 1478 } 1479 1480 bool TxGraphImpl::Exists(const Ref& arg, bool main_only) noexcept 1481 { 1482 if (GetRefGraph(arg) == nullptr) return false; 1483 Assume(GetRefGraph(arg) == this); 1484 size_t level = GetSpecifiedLevel(main_only); 1485 // Make sure the transaction isn't scheduled for removal. 1486 ApplyRemovals(level); 1487 auto cluster = FindCluster(GetRefIndex(arg), level); 1488 return cluster != nullptr; 1489 } 1490 1491 void Cluster::GetAncestorRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept 1492 { 1493 /** The union of all ancestors to be returned. */ 1494 SetType ancestors_union; 1495 // Process elements from the front of args, as long as they apply. 1496 while (!args.empty()) { 1497 if (args.front().first != this) break; 1498 ancestors_union |= m_depgraph.Ancestors(args.front().second); 1499 args = args.subspan(1); 1500 } 1501 Assume(ancestors_union.Any()); 1502 // Translate all ancestors (in arbitrary order) to Refs (if they have any), and return them. 1503 for (auto idx : ancestors_union) { 1504 const auto& entry = graph.m_entries[m_mapping[idx]]; 1505 Assume(entry.m_ref != nullptr); 1506 output.push_back(entry.m_ref); 1507 } 1508 } 1509 1510 void Cluster::GetDescendantRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept 1511 { 1512 /** The union of all descendants to be returned. */ 1513 SetType descendants_union; 1514 // Process elements from the front of args, as long as they apply. 1515 while (!args.empty()) { 1516 if (args.front().first != this) break; 1517 descendants_union |= m_depgraph.Descendants(args.front().second); 1518 args = args.subspan(1); 1519 } 1520 Assume(descendants_union.Any()); 1521 // Translate all descendants (in arbitrary order) to Refs (if they have any), and return them. 1522 for (auto idx : descendants_union) { 1523 const auto& entry = graph.m_entries[m_mapping[idx]]; 1524 Assume(entry.m_ref != nullptr); 1525 output.push_back(entry.m_ref); 1526 } 1527 } 1528 1529 std::vector<TxGraph::Ref*> Cluster::GetClusterRefs(const TxGraphImpl& graph) noexcept 1530 { 1531 std::vector<TxGraph::Ref*> ret; 1532 ret.reserve(m_linearization.size()); 1533 // Translate all transactions in the Cluster (in linearization order) to Refs. 1534 for (auto idx : m_linearization) { 1535 const auto& entry = graph.m_entries[m_mapping[idx]]; 1536 Assume(entry.m_ref != nullptr); 1537 ret.push_back(entry.m_ref); 1538 } 1539 return ret; 1540 } 1541 1542 FeePerWeight Cluster::GetIndividualFeerate(DepGraphIndex idx) noexcept 1543 { 1544 return FeePerWeight::FromFeeFrac(m_depgraph.FeeRate(idx)); 1545 } 1546 1547 void Cluster::MakeStagingTransactionsMissing(TxGraphImpl& graph) noexcept 1548 { 1549 Assume(m_level == 1); 1550 // Mark all transactions of a Cluster missing, needed when aborting staging, so that the 1551 // corresponding Locators don't retain references into aborted Clusters. 1552 for (auto ci : m_linearization) { 1553 GraphIndex idx = m_mapping[ci]; 1554 auto& entry = graph.m_entries[idx]; 1555 entry.m_locator[1].SetMissing(); 1556 } 1557 } 1558 1559 std::vector<TxGraph::Ref*> TxGraphImpl::GetAncestors(const Ref& arg, bool main_only) noexcept 1560 { 1561 // Return the empty vector if the Ref is empty. 1562 if (GetRefGraph(arg) == nullptr) return {}; 1563 Assume(GetRefGraph(arg) == this); 1564 // Apply all removals and dependencies, as the result might be incorrect otherwise. 1565 size_t level = GetSpecifiedLevel(main_only); 1566 ApplyDependencies(level); 1567 // Ancestry cannot be known if unapplied dependencies remain. 1568 Assume(GetClusterSet(level).m_deps_to_add.empty()); 1569 // Find the Cluster the argument is in, and return the empty vector if it isn't in any. 1570 auto cluster = FindCluster(GetRefIndex(arg), level); 1571 if (cluster == nullptr) return {}; 1572 // Dispatch to the Cluster. 1573 std::pair<Cluster*, DepGraphIndex> match = {cluster, m_entries[GetRefIndex(arg)].m_locator[cluster->m_level].index}; 1574 auto matches = std::span(&match, 1); 1575 std::vector<TxGraph::Ref*> ret; 1576 cluster->GetAncestorRefs(*this, matches, ret); 1577 return ret; 1578 } 1579 1580 std::vector<TxGraph::Ref*> TxGraphImpl::GetDescendants(const Ref& arg, bool main_only) noexcept 1581 { 1582 // Return the empty vector if the Ref is empty. 1583 if (GetRefGraph(arg) == nullptr) return {}; 1584 Assume(GetRefGraph(arg) == this); 1585 // Apply all removals and dependencies, as the result might be incorrect otherwise. 1586 size_t level = GetSpecifiedLevel(main_only); 1587 ApplyDependencies(level); 1588 // Ancestry cannot be known if unapplied dependencies remain. 1589 Assume(GetClusterSet(level).m_deps_to_add.empty()); 1590 // Find the Cluster the argument is in, and return the empty vector if it isn't in any. 1591 auto cluster = FindCluster(GetRefIndex(arg), level); 1592 if (cluster == nullptr) return {}; 1593 // Dispatch to the Cluster. 1594 std::pair<Cluster*, DepGraphIndex> match = {cluster, m_entries[GetRefIndex(arg)].m_locator[cluster->m_level].index}; 1595 auto matches = std::span(&match, 1); 1596 std::vector<TxGraph::Ref*> ret; 1597 cluster->GetDescendantRefs(*this, matches, ret); 1598 return ret; 1599 } 1600 1601 std::vector<TxGraph::Ref*> TxGraphImpl::GetAncestorsUnion(std::span<const Ref* const> args, bool main_only) noexcept 1602 { 1603 // Apply all dependencies, as the result might be incorrect otherwise. 1604 size_t level = GetSpecifiedLevel(main_only); 1605 ApplyDependencies(level); 1606 // Ancestry cannot be known if unapplied dependencies remain. 1607 Assume(GetClusterSet(level).m_deps_to_add.empty()); 1608 1609 // Translate args to matches. 1610 std::vector<std::pair<Cluster*, DepGraphIndex>> matches; 1611 matches.reserve(args.size()); 1612 for (auto arg : args) { 1613 Assume(arg); 1614 // Skip empty Refs. 1615 if (GetRefGraph(*arg) == nullptr) continue; 1616 Assume(GetRefGraph(*arg) == this); 1617 // Find the Cluster the argument is in, and skip if none is found. 1618 auto cluster = FindCluster(GetRefIndex(*arg), level); 1619 if (cluster == nullptr) continue; 1620 // Append to matches. 1621 matches.emplace_back(cluster, m_entries[GetRefIndex(*arg)].m_locator[cluster->m_level].index); 1622 } 1623 // Group by Cluster. 1624 std::sort(matches.begin(), matches.end(), [](auto& a, auto& b) noexcept { return CompareClusters(a.first, b.first) < 0; }); 1625 // Dispatch to the Clusters. 1626 std::span match_span(matches); 1627 std::vector<TxGraph::Ref*> ret; 1628 while (!match_span.empty()) { 1629 match_span.front().first->GetAncestorRefs(*this, match_span, ret); 1630 } 1631 return ret; 1632 } 1633 1634 std::vector<TxGraph::Ref*> TxGraphImpl::GetDescendantsUnion(std::span<const Ref* const> args, bool main_only) noexcept 1635 { 1636 // Apply all dependencies, as the result might be incorrect otherwise. 1637 size_t level = GetSpecifiedLevel(main_only); 1638 ApplyDependencies(level); 1639 // Ancestry cannot be known if unapplied dependencies remain. 1640 Assume(GetClusterSet(level).m_deps_to_add.empty()); 1641 1642 // Translate args to matches. 1643 std::vector<std::pair<Cluster*, DepGraphIndex>> matches; 1644 matches.reserve(args.size()); 1645 for (auto arg : args) { 1646 Assume(arg); 1647 // Skip empty Refs. 1648 if (GetRefGraph(*arg) == nullptr) continue; 1649 Assume(GetRefGraph(*arg) == this); 1650 // Find the Cluster the argument is in, and skip if none is found. 1651 auto cluster = FindCluster(GetRefIndex(*arg), level); 1652 if (cluster == nullptr) continue; 1653 // Append to matches. 1654 matches.emplace_back(cluster, m_entries[GetRefIndex(*arg)].m_locator[cluster->m_level].index); 1655 } 1656 // Group by Cluster. 1657 std::sort(matches.begin(), matches.end(), [](auto& a, auto& b) noexcept { return CompareClusters(a.first, b.first) < 0; }); 1658 // Dispatch to the Clusters. 1659 std::span match_span(matches); 1660 std::vector<TxGraph::Ref*> ret; 1661 while (!match_span.empty()) { 1662 match_span.front().first->GetDescendantRefs(*this, match_span, ret); 1663 } 1664 return ret; 1665 } 1666 1667 std::vector<TxGraph::Ref*> TxGraphImpl::GetCluster(const Ref& arg, bool main_only) noexcept 1668 { 1669 // Return the empty vector if the Ref is empty (which may be indicative of the transaction 1670 // having been removed already. 1671 if (GetRefGraph(arg) == nullptr) return {}; 1672 Assume(GetRefGraph(arg) == this); 1673 // Apply all removals and dependencies, as the result might be incorrect otherwise. 1674 size_t level = GetSpecifiedLevel(main_only); 1675 ApplyDependencies(level); 1676 // Cluster linearization cannot be known if unapplied dependencies remain. 1677 Assume(GetClusterSet(level).m_deps_to_add.empty()); 1678 // Find the Cluster the argument is in, and return the empty vector if it isn't in any. 1679 auto cluster = FindCluster(GetRefIndex(arg), level); 1680 if (cluster == nullptr) return {}; 1681 // Make sure the Cluster has an acceptable quality level, and then dispatch to it. 1682 MakeAcceptable(*cluster); 1683 return cluster->GetClusterRefs(*this); 1684 } 1685 1686 TxGraph::GraphIndex TxGraphImpl::GetTransactionCount(bool main_only) noexcept 1687 { 1688 size_t level = GetSpecifiedLevel(main_only); 1689 ApplyRemovals(level); 1690 return GetClusterSet(level).m_txcount; 1691 } 1692 1693 FeePerWeight TxGraphImpl::GetIndividualFeerate(const Ref& arg) noexcept 1694 { 1695 // Return the empty FeePerWeight if the passed Ref is empty. 1696 if (GetRefGraph(arg) == nullptr) return {}; 1697 Assume(GetRefGraph(arg) == this); 1698 // Find the cluster the argument is in (the level does not matter as individual feerates will 1699 // be identical if it occurs in both), and return the empty FeePerWeight if it isn't in any. 1700 Cluster* cluster{nullptr}; 1701 for (int level = 0; level <= GetTopLevel(); ++level) { 1702 // Apply removals, so that we can correctly report FeePerWeight{} for non-existing 1703 // transactions. 1704 ApplyRemovals(level); 1705 if (m_entries[GetRefIndex(arg)].m_locator[level].IsPresent()) { 1706 cluster = m_entries[GetRefIndex(arg)].m_locator[level].cluster; 1707 break; 1708 } 1709 } 1710 if (cluster == nullptr) return {}; 1711 // Dispatch to the Cluster. 1712 return cluster->GetIndividualFeerate(m_entries[GetRefIndex(arg)].m_locator[cluster->m_level].index); 1713 } 1714 1715 FeePerWeight TxGraphImpl::GetMainChunkFeerate(const Ref& arg) noexcept 1716 { 1717 // Return the empty FeePerWeight if the passed Ref is empty. 1718 if (GetRefGraph(arg) == nullptr) return {}; 1719 Assume(GetRefGraph(arg) == this); 1720 // Apply all removals and dependencies, as the result might be inaccurate otherwise. 1721 ApplyDependencies(/*level=*/0); 1722 // Chunk feerates cannot be accurately known if unapplied dependencies remain. 1723 Assume(m_main_clusterset.m_deps_to_add.empty()); 1724 // Find the cluster the argument is in, and return the empty FeePerWeight if it isn't in any. 1725 auto cluster = FindCluster(GetRefIndex(arg), 0); 1726 if (cluster == nullptr) return {}; 1727 // Make sure the Cluster has an acceptable quality level, and then return the transaction's 1728 // chunk feerate. 1729 MakeAcceptable(*cluster); 1730 const auto& entry = m_entries[GetRefIndex(arg)]; 1731 return entry.m_main_chunk_feerate; 1732 } 1733 1734 bool TxGraphImpl::IsOversized(bool main_only) noexcept 1735 { 1736 size_t level = GetSpecifiedLevel(main_only); 1737 auto& clusterset = GetClusterSet(level); 1738 if (clusterset.m_oversized.has_value()) { 1739 // Return cached value if known. 1740 return *clusterset.m_oversized; 1741 } 1742 // Find which Clusters will need to be merged together, as that is where the oversize 1743 // property is assessed. 1744 GroupClusters(level); 1745 Assume(clusterset.m_group_data.has_value()); 1746 clusterset.m_oversized = clusterset.m_group_data->m_group_oversized; 1747 return *clusterset.m_oversized; 1748 } 1749 1750 void TxGraphImpl::StartStaging() noexcept 1751 { 1752 // Staging cannot already exist. 1753 Assume(!m_staging_clusterset.has_value()); 1754 // Apply all remaining dependencies in main before creating a staging graph. Once staging 1755 // exists, we cannot merge Clusters anymore (because of interference with Clusters being 1756 // pulled into staging), so to make sure all inspectors are available (if not oversized), do 1757 // all merging work now. Call SplitAll() first, so that even if ApplyDependencies does not do 1758 // any thing due to knowing the result is oversized, splitting is still performed. 1759 SplitAll(0); 1760 ApplyDependencies(0); 1761 // Construct the staging ClusterSet. 1762 m_staging_clusterset.emplace(); 1763 // Copy statistics, precomputed data, and to-be-applied dependencies (only if oversized) to 1764 // the new graph. To-be-applied removals will always be empty at this point. 1765 m_staging_clusterset->m_txcount = m_main_clusterset.m_txcount; 1766 m_staging_clusterset->m_deps_to_add = m_main_clusterset.m_deps_to_add; 1767 m_staging_clusterset->m_group_data = m_main_clusterset.m_group_data; 1768 m_staging_clusterset->m_oversized = m_main_clusterset.m_oversized; 1769 Assume(m_staging_clusterset->m_oversized.has_value()); 1770 } 1771 1772 void TxGraphImpl::AbortStaging() noexcept 1773 { 1774 // Staging must exist. 1775 Assume(m_staging_clusterset.has_value()); 1776 // Mark all removed transactions as Missing (so the staging locator for these transactions 1777 // can be reused if another staging is created). 1778 for (auto idx : m_staging_clusterset->m_removed) { 1779 m_entries[idx].m_locator[1].SetMissing(); 1780 } 1781 // Do the same with the non-removed transactions in staging Clusters. 1782 for (int quality = 0; quality < int(QualityLevel::NONE); ++quality) { 1783 for (auto& cluster : m_staging_clusterset->m_clusters[quality]) { 1784 cluster->MakeStagingTransactionsMissing(*this); 1785 } 1786 } 1787 // Destroy the staging ClusterSet. 1788 m_staging_clusterset.reset(); 1789 Compact(); 1790 if (!m_main_clusterset.m_group_data.has_value()) { 1791 // In case m_oversized in main was kept after a Ref destruction while staging exists, we 1792 // need to re-evaluate m_oversized now. 1793 m_main_clusterset.m_oversized = std::nullopt; 1794 } 1795 } 1796 1797 void TxGraphImpl::CommitStaging() noexcept 1798 { 1799 // Staging must exist. 1800 Assume(m_staging_clusterset.has_value()); 1801 // Delete all conflicting Clusters in main, to make place for moving the staging ones 1802 // there. All of these have been copied to staging in PullIn(). 1803 auto conflicts = GetConflicts(); 1804 for (Cluster* conflict : conflicts) { 1805 conflict->Clear(*this); 1806 DeleteCluster(*conflict); 1807 } 1808 // Mark the removed transactions as Missing (so the staging locator for these transactions 1809 // can be reused if another staging is created). 1810 for (auto idx : m_staging_clusterset->m_removed) { 1811 m_entries[idx].m_locator[1].SetMissing(); 1812 } 1813 // Then move all Clusters in staging to main. 1814 for (int quality = 0; quality < int(QualityLevel::NONE); ++quality) { 1815 auto& stage_sets = m_staging_clusterset->m_clusters[quality]; 1816 while (!stage_sets.empty()) { 1817 stage_sets.back()->MoveToMain(*this); 1818 } 1819 } 1820 // Move all statistics, precomputed data, and to-be-applied removals and dependencies. 1821 m_main_clusterset.m_deps_to_add = std::move(m_staging_clusterset->m_deps_to_add); 1822 m_main_clusterset.m_to_remove = std::move(m_staging_clusterset->m_to_remove); 1823 m_main_clusterset.m_group_data = std::move(m_staging_clusterset->m_group_data); 1824 m_main_clusterset.m_oversized = std::move(m_staging_clusterset->m_oversized); 1825 m_main_clusterset.m_txcount = std::move(m_staging_clusterset->m_txcount); 1826 // Delete the old staging graph, after all its information was moved to main. 1827 m_staging_clusterset.reset(); 1828 Compact(); 1829 } 1830 1831 void Cluster::SetFee(TxGraphImpl& graph, DepGraphIndex idx, int64_t fee) noexcept 1832 { 1833 // Make sure the specified DepGraphIndex exists in this Cluster. 1834 Assume(m_depgraph.Positions()[idx]); 1835 // Bail out if the fee isn't actually being changed. 1836 if (m_depgraph.FeeRate(idx).fee == fee) return; 1837 // Update the fee, remember that relinearization will be necessary, and update the Entries 1838 // in the same Cluster. 1839 m_depgraph.FeeRate(idx).fee = fee; 1840 if (!NeedsSplitting()) { 1841 graph.SetClusterQuality(m_level, m_quality, m_setindex, QualityLevel::NEEDS_RELINEARIZE); 1842 } else { 1843 graph.SetClusterQuality(m_level, m_quality, m_setindex, QualityLevel::NEEDS_SPLIT); 1844 } 1845 Updated(graph); 1846 } 1847 1848 void TxGraphImpl::SetTransactionFee(const Ref& ref, int64_t fee) noexcept 1849 { 1850 // Don't do anything if the passed Ref is empty. 1851 if (GetRefGraph(ref) == nullptr) return; 1852 Assume(GetRefGraph(ref) == this); 1853 // Find the entry, its locator, and inform its Cluster about the new feerate, if any. 1854 auto& entry = m_entries[GetRefIndex(ref)]; 1855 for (int level = 0; level < MAX_LEVELS; ++level) { 1856 auto& locator = entry.m_locator[level]; 1857 if (locator.IsPresent()) { 1858 locator.cluster->SetFee(*this, locator.index, fee); 1859 } 1860 } 1861 } 1862 1863 std::strong_ordering TxGraphImpl::CompareMainOrder(const Ref& a, const Ref& b) noexcept 1864 { 1865 // The references must not be empty. 1866 Assume(GetRefGraph(a) == this); 1867 Assume(GetRefGraph(b) == this); 1868 // Apply dependencies in main. 1869 ApplyDependencies(0); 1870 Assume(m_main_clusterset.m_deps_to_add.empty()); 1871 // Make both involved Clusters acceptable, so chunk feerates are relevant. 1872 const auto& entry_a = m_entries[GetRefIndex(a)]; 1873 const auto& entry_b = m_entries[GetRefIndex(b)]; 1874 const auto& locator_a = entry_a.m_locator[0]; 1875 const auto& locator_b = entry_b.m_locator[0]; 1876 Assume(locator_a.IsPresent()); 1877 Assume(locator_b.IsPresent()); 1878 MakeAcceptable(*locator_a.cluster); 1879 MakeAcceptable(*locator_b.cluster); 1880 // Compare chunk feerates, and return result if it differs. 1881 auto feerate_cmp = FeeRateCompare(entry_b.m_main_chunk_feerate, entry_a.m_main_chunk_feerate); 1882 if (feerate_cmp < 0) return std::strong_ordering::less; 1883 if (feerate_cmp > 0) return std::strong_ordering::greater; 1884 // Compare Cluster* as tie-break for equal chunk feerates. 1885 if (locator_a.cluster != locator_b.cluster) { 1886 return CompareClusters(locator_a.cluster, locator_b.cluster); 1887 } 1888 // As final tie-break, compare position within cluster linearization. 1889 return entry_a.m_main_lin_index <=> entry_b.m_main_lin_index; 1890 } 1891 1892 TxGraph::GraphIndex TxGraphImpl::CountDistinctClusters(std::span<const Ref* const> refs, bool main_only) noexcept 1893 { 1894 size_t level = GetSpecifiedLevel(main_only); 1895 ApplyDependencies(level); 1896 auto& clusterset = GetClusterSet(level); 1897 Assume(clusterset.m_deps_to_add.empty()); 1898 // Build a vector of Clusters that the specified Refs occur in. 1899 std::vector<Cluster*> clusters; 1900 clusters.reserve(refs.size()); 1901 for (const Ref* ref : refs) { 1902 Assume(ref); 1903 if (GetRefGraph(*ref) == nullptr) continue; 1904 Assume(GetRefGraph(*ref) == this); 1905 auto cluster = FindCluster(GetRefIndex(*ref), level); 1906 if (cluster != nullptr) clusters.push_back(cluster); 1907 } 1908 // Count the number of distinct elements in clusters. 1909 std::sort(clusters.begin(), clusters.end(), [](Cluster* a, Cluster* b) noexcept { return CompareClusters(a, b) < 0; }); 1910 Cluster* last{nullptr}; 1911 GraphIndex ret{0}; 1912 for (Cluster* cluster : clusters) { 1913 ret += (cluster != last); 1914 last = cluster; 1915 } 1916 return ret; 1917 } 1918 1919 void Cluster::SanityCheck(const TxGraphImpl& graph, int level) const 1920 { 1921 // There must be an m_mapping for each m_depgraph position (including holes). 1922 assert(m_depgraph.PositionRange() == m_mapping.size()); 1923 // The linearization for this Cluster must contain every transaction once. 1924 assert(m_depgraph.TxCount() == m_linearization.size()); 1925 // The number of transactions in a Cluster cannot exceed m_max_cluster_count. 1926 assert(m_linearization.size() <= graph.m_max_cluster_count); 1927 // The level must match the level the Cluster occurs in. 1928 assert(m_level == level); 1929 // m_quality and m_setindex are checked in TxGraphImpl::SanityCheck. 1930 1931 // Compute the chunking of m_linearization. 1932 LinearizationChunking linchunking(m_depgraph, m_linearization); 1933 1934 // Verify m_linearization. 1935 SetType m_done; 1936 LinearizationIndex linindex{0}; 1937 assert(m_depgraph.IsAcyclic()); 1938 for (auto lin_pos : m_linearization) { 1939 assert(lin_pos < m_mapping.size()); 1940 const auto& entry = graph.m_entries[m_mapping[lin_pos]]; 1941 // Check that the linearization is topological. 1942 m_done.Set(lin_pos); 1943 assert(m_done.IsSupersetOf(m_depgraph.Ancestors(lin_pos))); 1944 // Check that the Entry has a locator pointing back to this Cluster & position within it. 1945 assert(entry.m_locator[level].cluster == this); 1946 assert(entry.m_locator[level].index == lin_pos); 1947 // For main-level entries, check linearization position and chunk feerate. 1948 if (level == 0 && IsAcceptable()) { 1949 assert(entry.m_main_lin_index == linindex); 1950 ++linindex; 1951 if (!linchunking.GetChunk(0).transactions[lin_pos]) { 1952 linchunking.MarkDone(linchunking.GetChunk(0).transactions); 1953 } 1954 assert(entry.m_main_chunk_feerate == linchunking.GetChunk(0).feerate); 1955 // If this Cluster has an acceptable quality level, its chunks must be connected. 1956 assert(m_depgraph.IsConnected(linchunking.GetChunk(0).transactions)); 1957 } 1958 } 1959 // Verify that each element of m_depgraph occurred in m_linearization. 1960 assert(m_done == m_depgraph.Positions()); 1961 } 1962 1963 void TxGraphImpl::SanityCheck() const 1964 { 1965 /** Which GraphIndexes ought to occur in m_unlinked, based on m_entries. */ 1966 std::set<GraphIndex> expected_unlinked; 1967 /** Which Clusters ought to occur in ClusterSet::m_clusters, based on m_entries. */ 1968 std::set<const Cluster*> expected_clusters[MAX_LEVELS]; 1969 /** Which GraphIndexes ought to occur in ClusterSet::m_removed, based on m_entries. */ 1970 std::set<GraphIndex> expected_removed[MAX_LEVELS]; 1971 /** Which Cluster::m_sequence values have been encountered. */ 1972 std::set<uint64_t> sequences; 1973 /** Whether compaction is possible in the current state. */ 1974 bool compact_possible{true}; 1975 1976 // Go over all Entry objects in m_entries. 1977 for (GraphIndex idx = 0; idx < m_entries.size(); ++idx) { 1978 const auto& entry = m_entries[idx]; 1979 if (entry.m_ref == nullptr) { 1980 // Unlinked Entry must have indexes appear in m_unlinked. 1981 expected_unlinked.insert(idx); 1982 } else { 1983 // Every non-unlinked Entry must have a Ref that points back to it. 1984 assert(GetRefGraph(*entry.m_ref) == this); 1985 assert(GetRefIndex(*entry.m_ref) == idx); 1986 } 1987 // Verify the Entry m_locators. 1988 bool was_present{false}, was_removed{false}; 1989 for (int level = 0; level < MAX_LEVELS; ++level) { 1990 const auto& locator = entry.m_locator[level]; 1991 // Every Locator must be in exactly one of these 3 states. 1992 assert(locator.IsMissing() + locator.IsRemoved() + locator.IsPresent() == 1); 1993 if (locator.IsPresent()) { 1994 // Once removed, a transaction cannot be revived. 1995 assert(!was_removed); 1996 // Verify that the Cluster agrees with where the Locator claims the transaction is. 1997 assert(locator.cluster->GetClusterEntry(locator.index) == idx); 1998 // Remember that we expect said Cluster to appear in the ClusterSet::m_clusters. 1999 expected_clusters[level].insert(locator.cluster); 2000 was_present = true; 2001 } else if (locator.IsRemoved()) { 2002 // Level 0 (main) cannot have IsRemoved locators (IsMissing there means non-existing). 2003 assert(level > 0); 2004 // A Locator can only be IsRemoved if it was IsPresent before, and only once. 2005 assert(was_present && !was_removed); 2006 // Remember that we expect this GraphIndex to occur in the ClusterSet::m_removed. 2007 expected_removed[level].insert(idx); 2008 was_removed = true; 2009 } 2010 } 2011 } 2012 2013 // For all levels (0 = main, 1 = staged)... 2014 for (int level = 0; level <= GetTopLevel(); ++level) { 2015 assert(level < MAX_LEVELS); 2016 auto& clusterset = GetClusterSet(level); 2017 std::set<const Cluster*> actual_clusters; 2018 2019 // For all quality levels... 2020 for (int qual = 0; qual < int(QualityLevel::NONE); ++qual) { 2021 QualityLevel quality{qual}; 2022 const auto& quality_clusters = clusterset.m_clusters[qual]; 2023 // ... for all clusters in them ... 2024 for (ClusterSetIndex setindex = 0; setindex < quality_clusters.size(); ++setindex) { 2025 const auto& cluster = *quality_clusters[setindex]; 2026 // Check the sequence number. 2027 assert(cluster.m_sequence < m_next_sequence_counter); 2028 assert(sequences.count(cluster.m_sequence) == 0); 2029 sequences.insert(cluster.m_sequence); 2030 // Remember we saw this Cluster (only if it is non-empty; empty Clusters aren't 2031 // expected to be referenced by the Entry vector). 2032 if (cluster.GetTxCount() != 0) { 2033 actual_clusters.insert(&cluster); 2034 } 2035 // Sanity check the cluster, according to the Cluster's internal rules. 2036 cluster.SanityCheck(*this, level); 2037 // Check that the cluster's quality and setindex matches its position in the quality list. 2038 assert(cluster.m_quality == quality); 2039 assert(cluster.m_setindex == setindex); 2040 } 2041 } 2042 2043 // Verify that all to-be-removed transactions have valid identifiers. 2044 for (GraphIndex idx : clusterset.m_to_remove) { 2045 assert(idx < m_entries.size()); 2046 // We cannot assert that all m_to_remove transactions are still present: ~Ref on a 2047 // (P,M) transaction (present in main, inherited in staging) will cause an m_to_remove 2048 // addition in both main and staging, but a subsequence ApplyRemovals in main will 2049 // cause it to disappear from staging too, leaving the m_to_remove in place. 2050 } 2051 2052 // Verify that all to-be-added dependencies have valid identifiers. 2053 for (auto [par_idx, chl_idx] : clusterset.m_deps_to_add) { 2054 assert(par_idx != chl_idx); 2055 assert(par_idx < m_entries.size()); 2056 assert(chl_idx < m_entries.size()); 2057 } 2058 2059 // Verify that the actually encountered clusters match the ones occurring in Entry vector. 2060 assert(actual_clusters == expected_clusters[level]); 2061 2062 // Verify that the contents of m_removed matches what was expected based on the Entry vector. 2063 std::set<GraphIndex> actual_removed(clusterset.m_removed.begin(), clusterset.m_removed.end()); 2064 for (auto i : expected_unlinked) { 2065 // If a transaction exists in both main and staging, and is removed from staging (adding 2066 // it to m_removed there), and consequently destroyed (wiping the locator completely), 2067 // it can remain in m_removed despite not having an IsRemoved() locator. Exclude those 2068 // transactions from the comparison here. 2069 actual_removed.erase(i); 2070 expected_removed[level].erase(i); 2071 } 2072 2073 assert(actual_removed == expected_removed[level]); 2074 2075 // If any GraphIndex entries remain in this ClusterSet, compact is not possible. 2076 if (!clusterset.m_deps_to_add.empty()) compact_possible = false; 2077 if (!clusterset.m_to_remove.empty()) compact_possible = false; 2078 if (!clusterset.m_removed.empty()) compact_possible = false; 2079 2080 // If m_group_data exists, its m_group_oversized must match m_oversized. 2081 if (clusterset.m_group_data.has_value()) { 2082 assert(clusterset.m_oversized == clusterset.m_group_data->m_group_oversized); 2083 } 2084 2085 // For non-top levels, m_oversized must be known (as it cannot change until the level 2086 // on top is gone). 2087 if (level < GetTopLevel()) assert(clusterset.m_oversized.has_value()); 2088 } 2089 2090 // Verify that the contents of m_unlinked matches what was expected based on the Entry vector. 2091 std::set<GraphIndex> actual_unlinked(m_unlinked.begin(), m_unlinked.end()); 2092 assert(actual_unlinked == expected_unlinked); 2093 2094 // If compaction was possible, it should have been performed already, and m_unlinked must be 2095 // empty (to prevent memory leaks due to an ever-growing m_entries vector). 2096 if (compact_possible) { 2097 assert(actual_unlinked.empty()); 2098 } 2099 } 2100 2101 void TxGraphImpl::DoWork() noexcept 2102 { 2103 for (int level = 0; level <= GetTopLevel(); ++level) { 2104 MakeAllAcceptable(level); 2105 } 2106 } 2107 2108 } // namespace 2109 2110 TxGraph::Ref::~Ref() 2111 { 2112 if (m_graph) { 2113 // Inform the TxGraph about the Ref being destroyed. 2114 m_graph->UnlinkRef(m_index); 2115 m_graph = nullptr; 2116 } 2117 } 2118 2119 TxGraph::Ref& TxGraph::Ref::operator=(Ref&& other) noexcept 2120 { 2121 // Unlink the current graph, if any. 2122 if (m_graph) m_graph->UnlinkRef(m_index); 2123 // Inform the other's graph about the move, if any. 2124 if (other.m_graph) other.m_graph->UpdateRef(other.m_index, *this); 2125 // Actually update the contents. 2126 m_graph = other.m_graph; 2127 m_index = other.m_index; 2128 other.m_graph = nullptr; 2129 other.m_index = GraphIndex(-1); 2130 return *this; 2131 } 2132 2133 TxGraph::Ref::Ref(Ref&& other) noexcept 2134 { 2135 // Inform the TxGraph of other that its Ref is being moved. 2136 if (other.m_graph) other.m_graph->UpdateRef(other.m_index, *this); 2137 // Actually move the contents. 2138 std::swap(m_graph, other.m_graph); 2139 std::swap(m_index, other.m_index); 2140 } 2141 2142 std::unique_ptr<TxGraph> MakeTxGraph(unsigned max_cluster_count) noexcept 2143 { 2144 return std::make_unique<TxGraphImpl>(max_cluster_count); 2145 }