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 #include <util/vector.h> 13 14 #include <compare> 15 #include <functional> 16 #include <memory> 17 #include <set> 18 #include <span> 19 #include <unordered_set> 20 #include <utility> 21 22 namespace { 23 24 using namespace cluster_linearize; 25 26 /** The maximum number of levels a TxGraph can have (0 = main, 1 = staging). */ 27 static constexpr int MAX_LEVELS{2}; 28 29 // Forward declare the TxGraph implementation class. 30 class TxGraphImpl; 31 32 /** Position of a DepGraphIndex within a Cluster::m_linearization. */ 33 using LinearizationIndex = uint32_t; 34 /** Position of a Cluster within TxGraphImpl::ClusterSet::m_clusters. */ 35 using ClusterSetIndex = uint32_t; 36 37 /** Quality levels for cached cluster linearizations. */ 38 enum class QualityLevel 39 { 40 /** This is a singleton cluster consisting of a transaction that individually exceeds the 41 * cluster size limit. It cannot be merged with anything. */ 42 OVERSIZED_SINGLETON, 43 /** This cluster may have multiple disconnected components, which are all NEEDS_FIX. */ 44 NEEDS_SPLIT_FIX, 45 /** This cluster may have multiple disconnected components, which are all NEEDS_RELINEARIZE. */ 46 NEEDS_SPLIT, 47 /** This cluster may be non-topological. */ 48 NEEDS_FIX, 49 /** This cluster has undergone changes that warrant re-linearization. */ 50 NEEDS_RELINEARIZE, 51 /** The minimal level of linearization has been performed, but it is not known to be optimal. */ 52 ACCEPTABLE, 53 /** The linearization is known to be optimal. */ 54 OPTIMAL, 55 /** This cluster is not registered in any ClusterSet::m_clusters. 56 * This must be the last entry in QualityLevel as ClusterSet::m_clusters is sized using it. */ 57 NONE, 58 }; 59 60 /** Information about a transaction inside TxGraphImpl::Trim. */ 61 struct TrimTxData 62 { 63 // Fields populated by Cluster::AppendTrimData(). These are immutable after TrimTxData 64 // construction. 65 /** Chunk feerate for this transaction. */ 66 FeePerWeight m_chunk_feerate; 67 /** GraphIndex of the transaction. */ 68 TxGraph::GraphIndex m_index; 69 /** Size of the transaction. */ 70 uint32_t m_tx_size; 71 72 // Fields only used internally by TxGraphImpl::Trim(): 73 /** Number of unmet dependencies this transaction has. -1 if the transaction is included. */ 74 uint32_t m_deps_left; 75 /** Number of dependencies that apply to this transaction as child. */ 76 uint32_t m_parent_count; 77 /** Where in deps_by_child those dependencies begin. */ 78 uint32_t m_parent_offset; 79 /** Number of dependencies that apply to this transaction as parent. */ 80 uint32_t m_children_count; 81 /** Where in deps_by_parent those dependencies begin. */ 82 uint32_t m_children_offset; 83 84 // Fields only used internally by TxGraphImpl::Trim()'s union-find implementation, and only for 85 // transactions that are definitely included or definitely rejected. 86 // 87 // As transactions get processed, they get organized into trees which form partitions 88 // representing the would-be clusters up to that point. The root of each tree is a 89 // representative for that partition. See 90 // https://en.wikipedia.org/wiki/Disjoint-set_data_structure. 91 // 92 /** Pointer to another TrimTxData, towards the root of the tree. If this is a root, m_uf_parent 93 * is equal to this itself. */ 94 TrimTxData* m_uf_parent; 95 /** If this is a root, the total number of transactions in the partition. */ 96 uint32_t m_uf_count; 97 /** If this is a root, the total size of transactions in the partition. */ 98 uint64_t m_uf_size; 99 }; 100 101 /** A grouping of connected transactions inside a TxGraphImpl::ClusterSet. */ 102 class Cluster 103 { 104 friend class TxGraphImpl; 105 friend class BlockBuilderImpl; 106 107 protected: 108 using GraphIndex = TxGraph::GraphIndex; 109 using SetType = BitSet<MAX_CLUSTER_COUNT_LIMIT>; 110 /** The quality level of m_linearization. */ 111 QualityLevel m_quality{QualityLevel::NONE}; 112 /** Which position this Cluster has in TxGraphImpl::ClusterSet::m_clusters[m_quality]. */ 113 ClusterSetIndex m_setindex{ClusterSetIndex(-1)}; 114 /** Sequence number for this Cluster (for tie-breaking comparison between equal-chunk-feerate 115 transactions in distinct clusters). */ 116 uint64_t m_sequence; 117 118 explicit Cluster(uint64_t sequence) noexcept : m_sequence(sequence) {} 119 120 public: 121 // Provide virtual destructor, for safe polymorphic usage inside std::unique_ptr. 122 virtual ~Cluster() = default; 123 124 // Cannot move or copy (would invalidate Cluster* in Locator and ClusterSet). */ 125 Cluster(const Cluster&) = delete; 126 Cluster& operator=(const Cluster&) = delete; 127 Cluster(Cluster&&) = delete; 128 Cluster& operator=(Cluster&&) = delete; 129 130 // Generic helper functions. 131 132 /** Whether the linearization of this Cluster can be exposed. */ 133 bool IsAcceptable() const noexcept 134 { 135 return m_quality == QualityLevel::ACCEPTABLE || m_quality == QualityLevel::OPTIMAL; 136 } 137 /** Whether the linearization of this Cluster is topological. */ 138 bool IsTopological() const noexcept 139 { 140 return m_quality != QualityLevel::NEEDS_FIX && m_quality != QualityLevel::NEEDS_SPLIT_FIX; 141 } 142 /** Whether the linearization of this Cluster is optimal. */ 143 bool IsOptimal() const noexcept 144 { 145 return m_quality == QualityLevel::OPTIMAL; 146 } 147 /** Whether this cluster is oversized. Note that no changes that can cause oversizedness are 148 * ever applied, so the only way a materialized Cluster object can be oversized is by being 149 * an individually oversized transaction singleton. */ 150 bool IsOversized() const noexcept { return m_quality == QualityLevel::OVERSIZED_SINGLETON; } 151 /** Whether this cluster requires splitting. */ 152 bool NeedsSplitting() const noexcept 153 { 154 return m_quality == QualityLevel::NEEDS_SPLIT || m_quality == QualityLevel::NEEDS_SPLIT_FIX; 155 } 156 157 /** Get the smallest number of transactions this Cluster is intended for. */ 158 virtual DepGraphIndex GetMinIntendedTxCount() const noexcept = 0; 159 /** Get the maximum number of transactions this Cluster supports. */ 160 virtual DepGraphIndex GetMaxTxCount() const noexcept = 0; 161 /** Total memory usage currently for this Cluster, including all its dynamic memory, plus Cluster 162 * structure itself, and ClusterSet::m_clusters entry. */ 163 virtual size_t TotalMemoryUsage() const noexcept = 0; 164 /** Determine the range of DepGraphIndexes used by this Cluster. */ 165 virtual DepGraphIndex GetDepGraphIndexRange() const noexcept = 0; 166 /** Get the number of transactions in this Cluster. */ 167 virtual LinearizationIndex GetTxCount() const noexcept = 0; 168 /** Get the total size of the transactions in this Cluster. */ 169 virtual uint64_t GetTotalTxSize() const noexcept = 0; 170 /** Given a DepGraphIndex into this Cluster, find the corresponding GraphIndex. */ 171 virtual GraphIndex GetClusterEntry(DepGraphIndex index) const noexcept = 0; 172 /** Append a transaction with given GraphIndex at the end of this Cluster and its 173 * linearization. Return the DepGraphIndex it was placed at. */ 174 virtual DepGraphIndex AppendTransaction(GraphIndex graph_idx, FeePerWeight feerate) noexcept = 0; 175 /** Add dependencies to a given child in this cluster. */ 176 virtual void AddDependencies(SetType parents, DepGraphIndex child) noexcept = 0; 177 /** Invoke visit1_fn for each transaction in the cluster, in linearization order, then 178 * visit2_fn in the same order, then wipe this Cluster. */ 179 virtual void ExtractTransactions(const std::function<void (DepGraphIndex, GraphIndex, FeePerWeight)>& visit1_fn, const std::function<void (DepGraphIndex, GraphIndex, SetType)>& visit2_fn) noexcept = 0; 180 /** Figure out what level this Cluster exists at in the graph. In most cases this is known by 181 * the caller already (see all "int level" arguments below), but not always. */ 182 virtual int GetLevel(const TxGraphImpl& graph) const noexcept = 0; 183 /** Only called by TxGraphImpl::SwapIndexes. */ 184 virtual void UpdateMapping(DepGraphIndex cluster_idx, GraphIndex graph_idx) noexcept = 0; 185 /** Push changes to Cluster and its linearization to the TxGraphImpl Entry objects. Main chunk 186 * information is computed if the cluster is acceptable, or when rename is set. Rename is used 187 * when called from Compact, to recompute after GraphIndexes may have changed; in this case, 188 * no chunk index objects are removed or created either. */ 189 virtual void Updated(TxGraphImpl& graph, int level, bool rename) noexcept = 0; 190 /** Remove all chunk index entries for this cluster (level=0 only). */ 191 virtual void RemoveChunkData(TxGraphImpl& graph) noexcept = 0; 192 /** Create a copy of this Cluster in staging, returning a pointer to it (used by PullIn). */ 193 virtual Cluster* CopyToStaging(TxGraphImpl& graph) const noexcept = 0; 194 /** Get the list of Clusters in main that conflict with this one (which is assumed to be in staging). */ 195 virtual void GetConflicts(const TxGraphImpl& graph, std::vector<Cluster*>& out) const noexcept = 0; 196 /** Mark all the Entry objects belonging to this staging Cluster as missing. The Cluster must be 197 * deleted immediately after. */ 198 virtual void MakeStagingTransactionsMissing(TxGraphImpl& graph) noexcept = 0; 199 /** Remove all transactions from a (non-empty) Cluster. */ 200 virtual void Clear(TxGraphImpl& graph, int level) noexcept = 0; 201 /** Change a Cluster's level from 1 (staging) to 0 (main). */ 202 virtual void MoveToMain(TxGraphImpl& graph) noexcept = 0; 203 /** Minimize this Cluster's memory usage. */ 204 virtual void Compact() noexcept = 0; 205 206 // Functions that implement the Cluster-specific side of internal TxGraphImpl mutations. 207 208 /** Apply all removals from the front of to_remove that apply to this Cluster, popping them 209 * off. There must be at least one such entry. */ 210 virtual void ApplyRemovals(TxGraphImpl& graph, int level, std::span<GraphIndex>& to_remove) noexcept = 0; 211 /** Split this cluster (must have a NEEDS_SPLIT* quality). Returns whether to delete this 212 * Cluster afterwards. */ 213 [[nodiscard]] virtual bool Split(TxGraphImpl& graph, int level) noexcept = 0; 214 /** Move all transactions from cluster to *this (as separate components). */ 215 virtual void Merge(TxGraphImpl& graph, int level, Cluster& cluster) noexcept = 0; 216 /** Given a span of (parent, child) pairs that all belong to this Cluster, apply them. */ 217 virtual void ApplyDependencies(TxGraphImpl& graph, int level, std::span<std::pair<GraphIndex, GraphIndex>> to_apply) noexcept = 0; 218 /** Improve the linearization of this Cluster. Returns how much work was performed and whether 219 * the Cluster's QualityLevel improved as a result. */ 220 virtual std::pair<uint64_t, bool> Relinearize(TxGraphImpl& graph, int level, uint64_t max_cost) noexcept = 0; 221 /** For every chunk in the cluster, append its FeeFrac to ret. */ 222 virtual void AppendChunkFeerates(std::vector<FeeFrac>& ret) const noexcept = 0; 223 /** Add a TrimTxData entry (filling m_chunk_feerate, m_index, m_tx_size) for every 224 * transaction in the Cluster to ret. Implicit dependencies between consecutive transactions 225 * in the linearization are added to deps. Return the Cluster's total transaction size. */ 226 virtual uint64_t AppendTrimData(std::vector<TrimTxData>& ret, std::vector<std::pair<GraphIndex, GraphIndex>>& deps) const noexcept = 0; 227 228 // Functions that implement the Cluster-specific side of public TxGraph functions. 229 230 /** Process elements from the front of args that apply to this cluster, and append Refs for the 231 * union of their ancestors to output. */ 232 virtual void GetAncestorRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept = 0; 233 /** Process elements from the front of args that apply to this cluster, and append Refs for the 234 * union of their descendants to output. */ 235 virtual void GetDescendantRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept = 0; 236 /** Populate range with refs for the transactions in this Cluster's linearization, from 237 * position start_pos until start_pos+range.size()-1, inclusive. Returns whether that 238 * range includes the last transaction in the linearization. */ 239 virtual bool GetClusterRefs(TxGraphImpl& graph, std::span<TxGraph::Ref*> range, LinearizationIndex start_pos) noexcept = 0; 240 /** Get the individual transaction feerate of a Cluster element. */ 241 virtual FeePerWeight GetIndividualFeerate(DepGraphIndex idx) noexcept = 0; 242 /** Modify the fee of a Cluster element. */ 243 virtual void SetFee(TxGraphImpl& graph, int level, DepGraphIndex idx, int64_t fee) noexcept = 0; 244 245 // Debugging functions. 246 247 virtual void SanityCheck(const TxGraphImpl& graph, int level) const = 0; 248 }; 249 250 /** An implementation of Cluster that uses a DepGraph and vectors, to support arbitrary numbers of 251 * transactions up to MAX_CLUSTER_COUNT_LIMIT. */ 252 class GenericClusterImpl final : public Cluster 253 { 254 friend class TxGraphImpl; 255 /** The DepGraph for this cluster, holding all feerates, and ancestors/descendants. */ 256 DepGraph<SetType> m_depgraph; 257 /** m_mapping[i] gives the GraphIndex for the position i transaction in m_depgraph. Values for 258 * positions i that do not exist in m_depgraph shouldn't ever be accessed and thus don't 259 * matter. m_mapping.size() equals m_depgraph.PositionRange(). */ 260 std::vector<GraphIndex> m_mapping; 261 /** The current linearization of the cluster. m_linearization.size() equals 262 * m_depgraph.TxCount(). This is always kept topological. */ 263 std::vector<DepGraphIndex> m_linearization; 264 265 public: 266 /** The smallest number of transactions this Cluster implementation is intended for. */ 267 static constexpr DepGraphIndex MIN_INTENDED_TX_COUNT{2}; 268 /** The largest number of transactions this Cluster implementation supports. */ 269 static constexpr DepGraphIndex MAX_TX_COUNT{SetType::Size()}; 270 271 GenericClusterImpl() noexcept = delete; 272 /** Construct an empty GenericClusterImpl. */ 273 explicit GenericClusterImpl(uint64_t sequence) noexcept; 274 275 size_t TotalMemoryUsage() const noexcept final; 276 constexpr DepGraphIndex GetMinIntendedTxCount() const noexcept final { return MIN_INTENDED_TX_COUNT; } 277 constexpr DepGraphIndex GetMaxTxCount() const noexcept final { return MAX_TX_COUNT; } 278 DepGraphIndex GetDepGraphIndexRange() const noexcept final { return m_depgraph.PositionRange(); } 279 LinearizationIndex GetTxCount() const noexcept final { return m_linearization.size(); } 280 uint64_t GetTotalTxSize() const noexcept final; 281 GraphIndex GetClusterEntry(DepGraphIndex index) const noexcept final { return m_mapping[index]; } 282 DepGraphIndex AppendTransaction(GraphIndex graph_idx, FeePerWeight feerate) noexcept final; 283 void AddDependencies(SetType parents, DepGraphIndex child) noexcept final; 284 void ExtractTransactions(const std::function<void (DepGraphIndex, GraphIndex, FeePerWeight)>& visit1_fn, const std::function<void (DepGraphIndex, GraphIndex, SetType)>& visit2_fn) noexcept final; 285 int GetLevel(const TxGraphImpl& graph) const noexcept final; 286 void UpdateMapping(DepGraphIndex cluster_idx, GraphIndex graph_idx) noexcept final { m_mapping[cluster_idx] = graph_idx; } 287 void Updated(TxGraphImpl& graph, int level, bool rename) noexcept final; 288 void RemoveChunkData(TxGraphImpl& graph) noexcept final; 289 Cluster* CopyToStaging(TxGraphImpl& graph) const noexcept final; 290 void GetConflicts(const TxGraphImpl& graph, std::vector<Cluster*>& out) const noexcept final; 291 void MakeStagingTransactionsMissing(TxGraphImpl& graph) noexcept final; 292 void Clear(TxGraphImpl& graph, int level) noexcept final; 293 void MoveToMain(TxGraphImpl& graph) noexcept final; 294 void Compact() noexcept final; 295 void ApplyRemovals(TxGraphImpl& graph, int level, std::span<GraphIndex>& to_remove) noexcept final; 296 [[nodiscard]] bool Split(TxGraphImpl& graph, int level) noexcept final; 297 void Merge(TxGraphImpl& graph, int level, Cluster& cluster) noexcept final; 298 void ApplyDependencies(TxGraphImpl& graph, int level, std::span<std::pair<GraphIndex, GraphIndex>> to_apply) noexcept final; 299 std::pair<uint64_t, bool> Relinearize(TxGraphImpl& graph, int level, uint64_t max_cost) noexcept final; 300 void AppendChunkFeerates(std::vector<FeeFrac>& ret) const noexcept final; 301 uint64_t AppendTrimData(std::vector<TrimTxData>& ret, std::vector<std::pair<GraphIndex, GraphIndex>>& deps) const noexcept final; 302 void GetAncestorRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept final; 303 void GetDescendantRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept final; 304 bool GetClusterRefs(TxGraphImpl& graph, std::span<TxGraph::Ref*> range, LinearizationIndex start_pos) noexcept final; 305 FeePerWeight GetIndividualFeerate(DepGraphIndex idx) noexcept final; 306 void SetFee(TxGraphImpl& graph, int level, DepGraphIndex idx, int64_t fee) noexcept final; 307 void SanityCheck(const TxGraphImpl& graph, int level) const final; 308 }; 309 310 /** An implementation of Cluster that only supports 1 transaction. */ 311 class SingletonClusterImpl final : public Cluster 312 { 313 friend class TxGraphImpl; 314 315 /** The feerate of the (singular) transaction in this Cluster. */ 316 FeePerWeight m_feerate; 317 /** Constant to indicate that this Cluster is empty. */ 318 static constexpr auto NO_GRAPH_INDEX = GraphIndex(-1); 319 /** The GraphIndex of the transaction. NO_GRAPH_INDEX if this Cluster is empty. */ 320 GraphIndex m_graph_index = NO_GRAPH_INDEX; 321 322 public: 323 /** The smallest number of transactions this Cluster implementation is intended for. */ 324 static constexpr DepGraphIndex MIN_INTENDED_TX_COUNT{1}; 325 /** The largest number of transactions this Cluster implementation supports. */ 326 static constexpr DepGraphIndex MAX_TX_COUNT{1}; 327 328 SingletonClusterImpl() noexcept = delete; 329 /** Construct an empty SingletonClusterImpl. */ 330 explicit SingletonClusterImpl(uint64_t sequence) noexcept : Cluster(sequence) {} 331 332 size_t TotalMemoryUsage() const noexcept final; 333 constexpr DepGraphIndex GetMinIntendedTxCount() const noexcept final { return MIN_INTENDED_TX_COUNT; } 334 constexpr DepGraphIndex GetMaxTxCount() const noexcept final { return MAX_TX_COUNT; } 335 LinearizationIndex GetTxCount() const noexcept final { return m_graph_index != NO_GRAPH_INDEX; } 336 DepGraphIndex GetDepGraphIndexRange() const noexcept final { return GetTxCount(); } 337 uint64_t GetTotalTxSize() const noexcept final { return GetTxCount() ? m_feerate.size : 0; } 338 GraphIndex GetClusterEntry(DepGraphIndex index) const noexcept final { Assume(index == 0); Assume(GetTxCount()); return m_graph_index; } 339 DepGraphIndex AppendTransaction(GraphIndex graph_idx, FeePerWeight feerate) noexcept final; 340 void AddDependencies(SetType parents, DepGraphIndex child) noexcept final; 341 void ExtractTransactions(const std::function<void (DepGraphIndex, GraphIndex, FeePerWeight)>& visit1_fn, const std::function<void (DepGraphIndex, GraphIndex, SetType)>& visit2_fn) noexcept final; 342 int GetLevel(const TxGraphImpl& graph) const noexcept final; 343 void UpdateMapping(DepGraphIndex cluster_idx, GraphIndex graph_idx) noexcept final { Assume(cluster_idx == 0); m_graph_index = graph_idx; } 344 void Updated(TxGraphImpl& graph, int level, bool rename) noexcept final; 345 void RemoveChunkData(TxGraphImpl& graph) noexcept final; 346 Cluster* CopyToStaging(TxGraphImpl& graph) const noexcept final; 347 void GetConflicts(const TxGraphImpl& graph, std::vector<Cluster*>& out) const noexcept final; 348 void MakeStagingTransactionsMissing(TxGraphImpl& graph) noexcept final; 349 void Clear(TxGraphImpl& graph, int level) noexcept final; 350 void MoveToMain(TxGraphImpl& graph) noexcept final; 351 void Compact() noexcept final; 352 void ApplyRemovals(TxGraphImpl& graph, int level, std::span<GraphIndex>& to_remove) noexcept final; 353 [[nodiscard]] bool Split(TxGraphImpl& graph, int level) noexcept final; 354 void Merge(TxGraphImpl& graph, int level, Cluster& cluster) noexcept final; 355 void ApplyDependencies(TxGraphImpl& graph, int level, std::span<std::pair<GraphIndex, GraphIndex>> to_apply) noexcept final; 356 std::pair<uint64_t, bool> Relinearize(TxGraphImpl& graph, int level, uint64_t max_cost) noexcept final; 357 void AppendChunkFeerates(std::vector<FeeFrac>& ret) const noexcept final; 358 uint64_t AppendTrimData(std::vector<TrimTxData>& ret, std::vector<std::pair<GraphIndex, GraphIndex>>& deps) const noexcept final; 359 void GetAncestorRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept final; 360 void GetDescendantRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept final; 361 bool GetClusterRefs(TxGraphImpl& graph, std::span<TxGraph::Ref*> range, LinearizationIndex start_pos) noexcept final; 362 FeePerWeight GetIndividualFeerate(DepGraphIndex idx) noexcept final; 363 void SetFee(TxGraphImpl& graph, int level, DepGraphIndex idx, int64_t fee) noexcept final; 364 void SanityCheck(const TxGraphImpl& graph, int level) const final; 365 }; 366 367 /** The transaction graph, including staged changes. 368 * 369 * The overall design of the data structure consists of 3 interlinked representations: 370 * - The transactions (held as a vector of TxGraphImpl::Entry inside TxGraphImpl). 371 * - The clusters (Cluster objects in per-quality vectors inside TxGraphImpl::ClusterSet). 372 * - The Refs (TxGraph::Ref objects, held externally by users of the TxGraph class) 373 * 374 * The Clusters are kept in one or two ClusterSet objects, one for the "main" graph, and one for 375 * the proposed changes ("staging"). If a transaction occurs in both, they share the same Entry, 376 * but there will be a separate Cluster per graph. 377 * 378 * Clusters and Refs contain the index of the Entry objects they refer to, and the Entry objects 379 * refer back to the Clusters and Refs the corresponding transaction is contained in. 380 * 381 * While redundant, this permits moving all of them independently, without invalidating things 382 * or costly iteration to fix up everything: 383 * - Entry objects can be moved to fill holes left by removed transactions in the Entry vector 384 * (see TxGraphImpl::Compact). 385 * - Clusters can be rewritten continuously (removals can cause them to split, new dependencies 386 * can cause them to be merged). 387 * - Ref objects can be held outside the class, while permitting them to be moved around, and 388 * inherited from. 389 */ 390 class TxGraphImpl final : public TxGraph 391 { 392 friend class Cluster; 393 friend class SingletonClusterImpl; 394 friend class GenericClusterImpl; 395 friend class BlockBuilderImpl; 396 private: 397 /** Internal RNG. */ 398 FastRandomContext m_rng; 399 /** This TxGraphImpl's maximum cluster count limit. */ 400 const DepGraphIndex m_max_cluster_count; 401 /** This TxGraphImpl's maximum cluster size limit. */ 402 const uint64_t m_max_cluster_size; 403 /** The amount of linearization work needed per cluster to be considered acceptable. */ 404 const uint64_t m_acceptable_cost; 405 /** Fallback ordering for transactions. */ 406 const std::function<std::strong_ordering(const TxGraph::Ref&, const TxGraph::Ref&)> m_fallback_order; 407 408 /** Information about one group of Clusters to be merged. */ 409 struct GroupEntry 410 { 411 /** Where the clusters to be merged start in m_group_clusters. */ 412 uint32_t m_cluster_offset; 413 /** How many clusters to merge. */ 414 uint32_t m_cluster_count; 415 /** Where the dependencies for this cluster group in m_deps_to_add start. */ 416 uint32_t m_deps_offset; 417 /** How many dependencies to add. */ 418 uint32_t m_deps_count; 419 }; 420 421 /** Information about all groups of Clusters to be merged. */ 422 struct GroupData 423 { 424 /** The groups of Clusters to be merged. */ 425 std::vector<GroupEntry> m_groups; 426 /** Which clusters are to be merged. GroupEntry::m_cluster_offset indexes into this. */ 427 std::vector<Cluster*> m_group_clusters; 428 }; 429 430 /** The collection of all Clusters in main or staged. */ 431 struct ClusterSet 432 { 433 /** The vectors of clusters, one vector per quality level. ClusterSetIndex indexes into each. */ 434 std::array<std::vector<std::unique_ptr<Cluster>>, int(QualityLevel::NONE)> m_clusters; 435 /** Which removals have yet to be applied. */ 436 std::vector<GraphIndex> m_to_remove; 437 /** Which dependencies are to be added ((parent,child) pairs). GroupData::m_deps_offset indexes 438 * into this. */ 439 std::vector<std::pair<GraphIndex, GraphIndex>> m_deps_to_add; 440 /** Information about the merges to be performed, if known. */ 441 std::optional<GroupData> m_group_data = GroupData{}; 442 /** Which entries were removed in this ClusterSet (so they can be wiped on abort). This 443 * includes all entries which have an (R) removed locator at this level (staging only), 444 * plus optionally any transaction in m_unlinked. */ 445 std::vector<GraphIndex> m_removed; 446 /** Total number of transactions in this graph (sum of all transaction counts in all 447 * Clusters, and for staging also those inherited from the main ClusterSet). */ 448 GraphIndex m_txcount{0}; 449 /** Total number of individually oversized transactions in the graph. */ 450 GraphIndex m_txcount_oversized{0}; 451 /** Whether this graph is oversized (if known). */ 452 std::optional<bool> m_oversized{false}; 453 /** The combined TotalMemoryUsage of all clusters in this level (only Clusters that 454 * are materialized; in staging, implicit Clusters from main are not counted), */ 455 size_t m_cluster_usage{0}; 456 457 ClusterSet() noexcept = default; 458 }; 459 460 /** The main ClusterSet. */ 461 ClusterSet m_main_clusterset; 462 /** The staging ClusterSet, if any. */ 463 std::optional<ClusterSet> m_staging_clusterset; 464 /** Next sequence number to assign to created Clusters. */ 465 uint64_t m_next_sequence_counter{0}; 466 467 /** Information about a chunk in the main graph. */ 468 struct ChunkData 469 { 470 /** The Entry which is the last transaction of the chunk. */ 471 mutable GraphIndex m_graph_index; 472 /** How many transactions the chunk contains (-1 = singleton tail of cluster). */ 473 LinearizationIndex m_chunk_count; 474 475 ChunkData(GraphIndex graph_index, LinearizationIndex chunk_count) noexcept : 476 m_graph_index{graph_index}, m_chunk_count{chunk_count} {} 477 }; 478 479 /** Compare two Cluster* by their m_sequence value (while supporting nullptr). */ 480 static std::strong_ordering CompareClusters(Cluster* a, Cluster* b) noexcept 481 { 482 // The nullptr pointer compares before everything else. 483 if (a == nullptr || b == nullptr) { 484 return (a != nullptr) <=> (b != nullptr); 485 } 486 // If neither pointer is nullptr, compare the Clusters' sequence numbers. 487 Assume(a == b || a->m_sequence != b->m_sequence); 488 return a->m_sequence <=> b->m_sequence; 489 } 490 491 /** Compare two entries (which must both exist within the main graph). */ 492 std::strong_ordering CompareMainTransactions(GraphIndex a, GraphIndex b) const noexcept 493 { 494 if (a == b) return std::strong_ordering::equal; 495 Assume(a < m_entries.size() && b < m_entries.size()); 496 const auto& entry_a = m_entries[a]; 497 const auto& entry_b = m_entries[b]; 498 // Compare chunk feerates, and return result if it differs. 499 auto feerate_cmp = FeeRateCompare(entry_b.m_main_chunk_feerate, entry_a.m_main_chunk_feerate); 500 if (feerate_cmp < 0) return std::strong_ordering::less; 501 if (feerate_cmp > 0) return std::strong_ordering::greater; 502 // Compare equal-feerate chunk prefix size for comparing equal chunk feerates. This does two 503 // things: it distinguishes equal-feerate chunks within the same cluster (because later 504 // ones will always have a higher prefix size), and it may distinguish equal-feerate chunks 505 // from distinct clusters. 506 if (entry_a.m_main_equal_feerate_chunk_prefix_size != entry_b.m_main_equal_feerate_chunk_prefix_size) { 507 return entry_a.m_main_equal_feerate_chunk_prefix_size <=> entry_b.m_main_equal_feerate_chunk_prefix_size; 508 } 509 // Compare by maximum m_fallback_order element to order equal-feerate chunks in distinct 510 // clusters, when the equal-feerate-prefix size is also the same. 511 const auto& locator_a = entry_a.m_locator[0]; 512 const auto& locator_b = entry_b.m_locator[0]; 513 Assume(locator_a.IsPresent() && locator_b.IsPresent()); 514 if (locator_a.cluster != locator_b.cluster) { 515 auto fallback_cmp = m_fallback_order(*m_entries[entry_a.m_main_max_chunk_fallback].m_ref, 516 *m_entries[entry_b.m_main_max_chunk_fallback].m_ref); 517 if (fallback_cmp != 0) return fallback_cmp; 518 // This shouldn't be reachable as m_fallback_order defines a strong ordering. 519 Assume(false); 520 return CompareClusters(locator_a.cluster, locator_b.cluster); 521 } 522 // Within a single chunk, sort by position within cluster linearization. 523 return entry_a.m_main_lin_index <=> entry_b.m_main_lin_index; 524 } 525 526 /** Comparator for ChunkData objects in mining order. */ 527 class ChunkOrder 528 { 529 const TxGraphImpl* const m_graph; 530 public: 531 explicit ChunkOrder(const TxGraphImpl* graph) : m_graph(graph) {} 532 533 bool operator()(const ChunkData& a, const ChunkData& b) const noexcept 534 { 535 return m_graph->CompareMainTransactions(a.m_graph_index, b.m_graph_index) < 0; 536 } 537 }; 538 539 /** Definition for the mining index type. */ 540 using ChunkIndex = std::set<ChunkData, ChunkOrder>; 541 542 /** Index of ChunkData objects, indexing the last transaction in each chunk in the main 543 * graph. */ 544 ChunkIndex m_main_chunkindex; 545 /** Number of index-observing objects in existence (BlockBuilderImpls). */ 546 size_t m_main_chunkindex_observers{0}; 547 /** Cache of discarded ChunkIndex node handles to reuse, avoiding additional allocation. */ 548 std::vector<ChunkIndex::node_type> m_main_chunkindex_discarded; 549 550 /** A Locator that describes whether, where, and in which Cluster an Entry appears. 551 * Every Entry has MAX_LEVELS locators, as it may appear in one Cluster per level. 552 * 553 * Each level of a Locator is in one of three states: 554 * 555 * - (P)resent: actually occurs in a Cluster at that level. 556 * 557 * - (M)issing: 558 * - In the main graph: the transaction does not exist in main. 559 * - In the staging graph: the transaction's existence is the same as in main. If it doesn't 560 * exist in main, (M) in staging means it does not exist there 561 * either. If it does exist in main, (M) in staging means the 562 * cluster it is in has not been modified in staging, and thus the 563 * transaction implicitly exists in staging too (without explicit 564 * Cluster object; see PullIn() to create it in staging too). 565 * 566 * - (R)emoved: only possible in staging; it means the transaction exists in main, but is 567 * removed in staging. 568 * 569 * The following combinations are possible: 570 * - (M,M): the transaction doesn't exist in either graph. 571 * - (P,M): the transaction exists in both, but only exists explicitly in a Cluster object in 572 * main. Its existence in staging is inherited from main. 573 * - (P,P): the transaction exists in both, and is materialized in both. Thus, the clusters 574 * and/or their linearizations may be different in main and staging. 575 * - (M,P): the transaction is added in staging, and does not exist in main. 576 * - (P,R): the transaction exists in main, but is removed in staging. 577 * 578 * When staging does not exist, only (M,M) and (P,M) are possible. 579 */ 580 struct Locator 581 { 582 /** Which Cluster the Entry appears in (nullptr = missing). */ 583 Cluster* cluster{nullptr}; 584 /** Where in the Cluster it appears (if cluster == nullptr: 0 = missing, -1 = removed). */ 585 DepGraphIndex index{0}; 586 587 /** Mark this Locator as missing (= same as lower level, or non-existing if level 0). */ 588 void SetMissing() noexcept { cluster = nullptr; index = 0; } 589 /** Mark this Locator as removed (not allowed in level 0). */ 590 void SetRemoved() noexcept { cluster = nullptr; index = DepGraphIndex(-1); } 591 /** Mark this Locator as present, in the specified Cluster. */ 592 void SetPresent(Cluster* c, DepGraphIndex i) noexcept { cluster = c; index = i; } 593 /** Check if this Locator is missing. */ 594 bool IsMissing() const noexcept { return cluster == nullptr && index == 0; } 595 /** Check if this Locator is removed. */ 596 bool IsRemoved() const noexcept { return cluster == nullptr && index == DepGraphIndex(-1); } 597 /** Check if this Locator is present (in some Cluster). */ 598 bool IsPresent() const noexcept { return cluster != nullptr; } 599 }; 600 601 /** Internal information about each transaction in a TxGraphImpl. */ 602 struct Entry 603 { 604 /** Pointer to the corresponding Ref object if any, or nullptr if unlinked. */ 605 Ref* m_ref{nullptr}; 606 /** Iterator to the corresponding ChunkData, if any, and m_main_chunkindex.end() otherwise. 607 * This is initialized on construction of the Entry, in AddTransaction. */ 608 ChunkIndex::iterator m_main_chunkindex_iterator; 609 /** Which Cluster and position therein this Entry appears in. ([0] = main, [1] = staged). */ 610 Locator m_locator[MAX_LEVELS]; 611 /** The chunk feerate of this transaction in main (if present in m_locator[0]). */ 612 FeePerWeight m_main_chunk_feerate; 613 /** The equal-feerate chunk prefix size of this transaction in main. If the transaction is 614 * part of chunk C in main, then this gives the sum of the sizes of all chunks in C's 615 * cluster, whose feerate is equal to that of C, which do not appear after C itself in 616 * the cluster's linearization. 617 * This provides a way to sort equal-feerate chunks across clusters, in a way that agrees 618 * with the within-cluster chunk ordering. */ 619 int32_t m_main_equal_feerate_chunk_prefix_size; 620 /** The position this transaction has in the main linearization (if present). */ 621 LinearizationIndex m_main_lin_index; 622 /** Of all transactions within this transaction's chunk in main (if present there), the 623 * maximal one according to m_fallback_order. */ 624 GraphIndex m_main_max_chunk_fallback = GraphIndex(-1); 625 }; 626 627 /** The set of all transactions (in all levels combined). GraphIndex values index into this. */ 628 std::vector<Entry> m_entries; 629 630 /** Set of Entries which have no linked Ref anymore. */ 631 std::vector<GraphIndex> m_unlinked; 632 633 public: 634 /** Construct a new TxGraphImpl with the specified limits and fallback order. */ 635 explicit TxGraphImpl( 636 DepGraphIndex max_cluster_count, 637 uint64_t max_cluster_size, 638 uint64_t acceptable_cost, 639 const std::function<std::strong_ordering(const TxGraph::Ref&, const TxGraph::Ref&)>& fallback_order 640 ) noexcept : 641 m_max_cluster_count(max_cluster_count), 642 m_max_cluster_size(max_cluster_size), 643 m_acceptable_cost(acceptable_cost), 644 m_fallback_order(fallback_order), 645 m_main_chunkindex(ChunkOrder(this)) 646 { 647 Assume(max_cluster_count >= 1); 648 Assume(max_cluster_count <= MAX_CLUSTER_COUNT_LIMIT); 649 } 650 651 /** Destructor. */ 652 ~TxGraphImpl() noexcept; 653 654 // Cannot move or copy (would invalidate TxGraphImpl* in Ref, MiningOrder, EvictionOrder). 655 TxGraphImpl(const TxGraphImpl&) = delete; 656 TxGraphImpl& operator=(const TxGraphImpl&) = delete; 657 TxGraphImpl(TxGraphImpl&&) = delete; 658 TxGraphImpl& operator=(TxGraphImpl&&) = delete; 659 660 // Simple helper functions. 661 662 /** Swap the Entry referred to by a and the one referred to by b. Gather main clusters to 663 * update afterwards. */ 664 void SwapIndexes(GraphIndex a, GraphIndex b, std::vector<Cluster*>& affected_main) noexcept; 665 /** If idx exists in the specified level ClusterSet (explicitly, or in the level below and not 666 * removed), return the Cluster it is in. Otherwise, return nullptr. */ 667 Cluster* FindCluster(GraphIndex idx, int level) const noexcept { return FindClusterAndLevel(idx, level).first; } 668 /** Like FindCluster, but also return what level the match was found in (-1 if not found). */ 669 std::pair<Cluster*, int> FindClusterAndLevel(GraphIndex idx, int level) const noexcept; 670 /** Extract a Cluster from its ClusterSet, and set its quality to QualityLevel::NONE. */ 671 std::unique_ptr<Cluster> ExtractCluster(int level, QualityLevel quality, ClusterSetIndex setindex) noexcept; 672 /** Delete a Cluster. */ 673 void DeleteCluster(Cluster& cluster, int level) noexcept; 674 /** Insert a Cluster into its ClusterSet. */ 675 ClusterSetIndex InsertCluster(int level, std::unique_ptr<Cluster>&& cluster, QualityLevel quality) noexcept; 676 /** Change the QualityLevel of a Cluster (identified by old_quality and old_index). */ 677 void SetClusterQuality(int level, QualityLevel old_quality, ClusterSetIndex old_index, QualityLevel new_quality) noexcept; 678 /** Get the index of the top level ClusterSet (staging if it exists, main otherwise). */ 679 int GetTopLevel() const noexcept { return m_staging_clusterset.has_value(); } 680 /** Get the specified level (staging if it exists and level is TOP, main otherwise). */ 681 int GetSpecifiedLevel(Level level) const noexcept { return level == Level::TOP && m_staging_clusterset.has_value(); } 682 /** Get a reference to the ClusterSet at the specified level (which must exist). */ 683 ClusterSet& GetClusterSet(int level) noexcept; 684 const ClusterSet& GetClusterSet(int level) const noexcept; 685 /** Make a transaction not exist at a specified level. It must currently exist there. 686 * oversized_tx indicates whether the transaction is an individually-oversized one 687 * (OVERSIZED_SINGLETON). */ 688 void ClearLocator(int level, GraphIndex index, bool oversized_tx) noexcept; 689 /** Find which Clusters in main conflict with ones in staging. */ 690 std::vector<Cluster*> GetConflicts() const noexcept; 691 /** Clear an Entry's ChunkData. */ 692 void ClearChunkData(Entry& entry) noexcept; 693 /** Give an Entry a ChunkData object. */ 694 void CreateChunkData(GraphIndex idx, LinearizationIndex chunk_count) noexcept; 695 /** Create an empty GenericClusterImpl object. */ 696 std::unique_ptr<GenericClusterImpl> CreateEmptyGenericCluster() noexcept 697 { 698 return std::make_unique<GenericClusterImpl>(m_next_sequence_counter++); 699 } 700 /** Create an empty SingletonClusterImpl object. */ 701 std::unique_ptr<SingletonClusterImpl> CreateEmptySingletonCluster() noexcept 702 { 703 return std::make_unique<SingletonClusterImpl>(m_next_sequence_counter++); 704 } 705 /** Create an empty Cluster of the appropriate implementation for the specified (maximum) tx 706 * count. */ 707 std::unique_ptr<Cluster> CreateEmptyCluster(DepGraphIndex tx_count) noexcept 708 { 709 if (tx_count >= SingletonClusterImpl::MIN_INTENDED_TX_COUNT && tx_count <= SingletonClusterImpl::MAX_TX_COUNT) { 710 return CreateEmptySingletonCluster(); 711 } 712 if (tx_count >= GenericClusterImpl::MIN_INTENDED_TX_COUNT && tx_count <= GenericClusterImpl::MAX_TX_COUNT) { 713 return CreateEmptyGenericCluster(); 714 } 715 assert(false); 716 return {}; 717 } 718 719 // Functions for handling Refs. 720 721 /** Only called by Ref's move constructor/assignment to update Ref locations. */ 722 void UpdateRef(GraphIndex idx, Ref& new_location) noexcept final 723 { 724 auto& entry = m_entries[idx]; 725 Assume(entry.m_ref != nullptr); 726 entry.m_ref = &new_location; 727 } 728 729 /** Only called by Ref::~Ref to unlink Refs, and Ref's move assignment. */ 730 void UnlinkRef(GraphIndex idx) noexcept final 731 { 732 auto& entry = m_entries[idx]; 733 Assume(entry.m_ref != nullptr); 734 Assume(m_main_chunkindex_observers == 0 || !entry.m_locator[0].IsPresent()); 735 // Remove all chunk index entries for the affected cluster, to avoid any chunk indexes 736 // referencing unlinked/destroyed Refs. 737 if (entry.m_locator[0].IsPresent()) { 738 entry.m_locator[0].cluster->RemoveChunkData(*this); 739 } 740 entry.m_ref = nullptr; 741 // Mark the transaction as to be removed in all levels where it explicitly or implicitly 742 // exists. 743 bool exists_anywhere{false}; 744 bool exists{false}; 745 for (int level = 0; level <= GetTopLevel(); ++level) { 746 if (entry.m_locator[level].IsPresent()) { 747 exists_anywhere = true; 748 exists = true; 749 } else if (entry.m_locator[level].IsRemoved()) { 750 exists = false; 751 } 752 if (exists) { 753 auto& clusterset = GetClusterSet(level); 754 clusterset.m_to_remove.push_back(idx); 755 // Force recomputation of grouping data. 756 clusterset.m_group_data = std::nullopt; 757 // Do not wipe the oversized state of main if staging exists. The reason for this 758 // is that the alternative would mean that cluster merges may need to be applied to 759 // a formerly-oversized main graph while staging exists (to satisfy chunk feerate 760 // queries into main, for example), and such merges could conflict with pulls of 761 // some of their constituents into staging. 762 if (level == GetTopLevel() && clusterset.m_oversized == true) { 763 clusterset.m_oversized = std::nullopt; 764 } 765 } 766 } 767 m_unlinked.push_back(idx); 768 if (!exists_anywhere) Compact(); 769 } 770 771 // Functions related to various normalization/application steps. 772 /** Get rid of unlinked Entry objects in m_entries, if possible (this changes the GraphIndex 773 * values for remaining Entry objects, so this only does something when no to-be-applied 774 * operations or staged removals referring to GraphIndexes remain). */ 775 void Compact() noexcept; 776 /** If cluster is not in staging, copy it there, and return a pointer to it. 777 * Staging must exist, and this modifies the locators of its 778 * transactions from inherited (P,M) to explicit (P,P). */ 779 Cluster* PullIn(Cluster* cluster, int level) noexcept; 780 /** Apply all removals queued up in m_to_remove to the relevant Clusters (which get a 781 * NEEDS_SPLIT* QualityLevel) up to the specified level. */ 782 void ApplyRemovals(int up_to_level) noexcept; 783 /** Split an individual cluster. */ 784 void Split(Cluster& cluster, int level) noexcept; 785 /** Split all clusters that need splitting up to the specified level. */ 786 void SplitAll(int up_to_level) noexcept; 787 /** Populate m_group_data based on m_deps_to_add in the specified level. */ 788 void GroupClusters(int level) noexcept; 789 /** Merge the specified clusters. */ 790 void Merge(std::span<Cluster*> to_merge, int level) noexcept; 791 /** Apply all m_deps_to_add to the relevant Clusters in the specified level. */ 792 void ApplyDependencies(int level) noexcept; 793 /** Make a specified Cluster have quality ACCEPTABLE or OPTIMAL. */ 794 void MakeAcceptable(Cluster& cluster, int level) noexcept; 795 /** Make all Clusters at the specified level have quality ACCEPTABLE or OPTIMAL. */ 796 void MakeAllAcceptable(int level) noexcept; 797 798 // Implementations for the public TxGraph interface. 799 800 void AddTransaction(Ref& arg, const FeePerWeight& feerate) noexcept final; 801 void RemoveTransaction(const Ref& arg) noexcept final; 802 void AddDependency(const Ref& parent, const Ref& child) noexcept final; 803 void SetTransactionFee(const Ref&, int64_t fee) noexcept final; 804 805 bool DoWork(uint64_t max_cost) noexcept final; 806 807 void StartStaging() noexcept final; 808 void CommitStaging() noexcept final; 809 void AbortStaging() noexcept final; 810 bool HaveStaging() const noexcept final { return m_staging_clusterset.has_value(); } 811 812 bool Exists(const Ref& arg, Level level) noexcept final; 813 FeePerWeight GetMainChunkFeerate(const Ref& arg) noexcept final; 814 FeePerWeight GetIndividualFeerate(const Ref& arg) noexcept final; 815 std::vector<Ref*> GetCluster(const Ref& arg, Level level) noexcept final; 816 std::vector<Ref*> GetAncestors(const Ref& arg, Level level) noexcept final; 817 std::vector<Ref*> GetDescendants(const Ref& arg, Level level) noexcept final; 818 std::vector<Ref*> GetAncestorsUnion(std::span<const Ref* const> args, Level level) noexcept final; 819 std::vector<Ref*> GetDescendantsUnion(std::span<const Ref* const> args, Level level) noexcept final; 820 GraphIndex GetTransactionCount(Level level) noexcept final; 821 bool IsOversized(Level level) noexcept final; 822 std::strong_ordering CompareMainOrder(const Ref& a, const Ref& b) noexcept final; 823 GraphIndex CountDistinctClusters(std::span<const Ref* const> refs, Level level) noexcept final; 824 std::pair<std::vector<FeeFrac>, std::vector<FeeFrac>> GetMainStagingDiagrams() noexcept final; 825 std::vector<Ref*> Trim() noexcept final; 826 827 std::unique_ptr<BlockBuilder> GetBlockBuilder() noexcept final; 828 std::pair<std::vector<Ref*>, FeePerWeight> GetWorstMainChunk() noexcept final; 829 830 size_t GetMainMemoryUsage() noexcept final; 831 832 void SanityCheck() const final; 833 }; 834 835 TxGraphImpl::ClusterSet& TxGraphImpl::GetClusterSet(int level) noexcept 836 { 837 if (level == 0) return m_main_clusterset; 838 Assume(level == 1); 839 Assume(m_staging_clusterset.has_value()); 840 return *m_staging_clusterset; 841 } 842 843 const TxGraphImpl::ClusterSet& TxGraphImpl::GetClusterSet(int level) const noexcept 844 { 845 if (level == 0) return m_main_clusterset; 846 Assume(level == 1); 847 Assume(m_staging_clusterset.has_value()); 848 return *m_staging_clusterset; 849 } 850 851 /** Implementation of the TxGraph::BlockBuilder interface. */ 852 class BlockBuilderImpl final : public TxGraph::BlockBuilder 853 { 854 /** Which TxGraphImpl this object is doing block building for. It will have its 855 * m_main_chunkindex_observers incremented as long as this BlockBuilderImpl exists. */ 856 TxGraphImpl* const m_graph; 857 /** Cluster sequence numbers which we're not including further transactions from. */ 858 std::unordered_set<uint64_t> m_excluded_clusters; 859 /** Iterator to the current chunk in the chunk index. end() if nothing further remains. */ 860 TxGraphImpl::ChunkIndex::const_iterator m_cur_iter; 861 /** Which cluster the current chunk belongs to, so we can exclude further transactions from it 862 * when that chunk is skipped. */ 863 Cluster* m_cur_cluster; 864 /** Whether we know that m_cur_iter points to the last chunk of m_cur_cluster. */ 865 bool m_known_end_of_cluster; 866 867 // Move m_cur_iter / m_cur_cluster to the next acceptable chunk. 868 void Next() noexcept; 869 870 public: 871 /** Construct a new BlockBuilderImpl to build blocks for the provided graph. */ 872 BlockBuilderImpl(TxGraphImpl& graph) noexcept; 873 874 // Implement the public interface. 875 ~BlockBuilderImpl() final; 876 std::optional<std::pair<std::vector<TxGraph::Ref*>, FeePerWeight>> GetCurrentChunk() noexcept final; 877 void Include() noexcept final; 878 void Skip() noexcept final; 879 }; 880 881 void TxGraphImpl::ClearChunkData(Entry& entry) noexcept 882 { 883 if (entry.m_main_chunkindex_iterator != m_main_chunkindex.end()) { 884 Assume(m_main_chunkindex_observers == 0); 885 // If the Entry has a non-empty m_main_chunkindex_iterator, extract it, and move the handle 886 // to the cache of discarded chunkindex entries. 887 m_main_chunkindex_discarded.emplace_back(m_main_chunkindex.extract(entry.m_main_chunkindex_iterator)); 888 entry.m_main_chunkindex_iterator = m_main_chunkindex.end(); 889 } 890 } 891 892 void TxGraphImpl::CreateChunkData(GraphIndex idx, LinearizationIndex chunk_count) noexcept 893 { 894 auto& entry = m_entries[idx]; 895 // Make sure to not create chunk data for unlinked entries, which would make invoking 896 // m_fallback_order on them impossible. 897 Assume(entry.m_ref != nullptr); 898 if (!m_main_chunkindex_discarded.empty()) { 899 // Reuse an discarded node handle. 900 auto& node = m_main_chunkindex_discarded.back().value(); 901 node.m_graph_index = idx; 902 node.m_chunk_count = chunk_count; 903 auto insert_result = m_main_chunkindex.insert(std::move(m_main_chunkindex_discarded.back())); 904 Assume(insert_result.inserted); 905 entry.m_main_chunkindex_iterator = insert_result.position; 906 m_main_chunkindex_discarded.pop_back(); 907 } else { 908 // Construct a new entry. 909 auto emplace_result = m_main_chunkindex.emplace(idx, chunk_count); 910 Assume(emplace_result.second); 911 entry.m_main_chunkindex_iterator = emplace_result.first; 912 } 913 } 914 915 size_t GenericClusterImpl::TotalMemoryUsage() const noexcept 916 { 917 return // Dynamic memory allocated in this Cluster. 918 memusage::DynamicUsage(m_mapping) + memusage::DynamicUsage(m_linearization) + 919 // Dynamic memory usage inside m_depgraph. 920 m_depgraph.DynamicMemoryUsage() + 921 // Memory usage of the allocated Cluster itself. 922 memusage::MallocUsage(sizeof(GenericClusterImpl)) + 923 // Memory usage of the ClusterSet::m_clusters entry. 924 sizeof(std::unique_ptr<Cluster>); 925 } 926 927 size_t SingletonClusterImpl::TotalMemoryUsage() const noexcept 928 { 929 return // Memory usage of the allocated SingletonClusterImpl itself. 930 memusage::MallocUsage(sizeof(SingletonClusterImpl)) + 931 // Memory usage of the ClusterSet::m_clusters entry. 932 sizeof(std::unique_ptr<Cluster>); 933 } 934 935 uint64_t GenericClusterImpl::GetTotalTxSize() const noexcept 936 { 937 uint64_t ret{0}; 938 for (auto i : m_linearization) { 939 ret += m_depgraph.FeeRate(i).size; 940 } 941 return ret; 942 } 943 944 DepGraphIndex GenericClusterImpl::AppendTransaction(GraphIndex graph_idx, FeePerWeight feerate) noexcept 945 { 946 Assume(graph_idx != GraphIndex(-1)); 947 auto ret = m_depgraph.AddTransaction(feerate); 948 m_mapping.push_back(graph_idx); 949 m_linearization.push_back(ret); 950 return ret; 951 } 952 953 DepGraphIndex SingletonClusterImpl::AppendTransaction(GraphIndex graph_idx, FeePerWeight feerate) noexcept 954 { 955 Assume(!GetTxCount()); 956 m_graph_index = graph_idx; 957 m_feerate = feerate; 958 return 0; 959 } 960 961 void GenericClusterImpl::AddDependencies(SetType parents, DepGraphIndex child) noexcept 962 { 963 m_depgraph.AddDependencies(parents, child); 964 } 965 966 void SingletonClusterImpl::AddDependencies(SetType parents, DepGraphIndex child) noexcept 967 { 968 // Singletons cannot have any dependencies. 969 Assume(child == 0); 970 Assume(parents == SetType{} || parents == SetType::Fill(0)); 971 } 972 973 void GenericClusterImpl::ExtractTransactions(const std::function<void (DepGraphIndex, GraphIndex, FeePerWeight)>& visit1_fn, const std::function<void (DepGraphIndex, GraphIndex, SetType)>& visit2_fn) noexcept 974 { 975 for (auto pos : m_linearization) { 976 visit1_fn(pos, m_mapping[pos], FeePerWeight::FromFeeFrac(m_depgraph.FeeRate(pos))); 977 } 978 for (auto pos : m_linearization) { 979 visit2_fn(pos, m_mapping[pos], m_depgraph.GetReducedParents(pos)); 980 } 981 // Purge this Cluster, now that everything has been moved. 982 m_depgraph = DepGraph<SetType>{}; 983 m_linearization.clear(); 984 m_mapping.clear(); 985 } 986 987 void SingletonClusterImpl::ExtractTransactions(const std::function<void (DepGraphIndex, GraphIndex, FeePerWeight)>& visit1_fn, const std::function<void (DepGraphIndex, GraphIndex, SetType)>& visit2_fn) noexcept 988 { 989 if (GetTxCount()) { 990 visit1_fn(0, m_graph_index, m_feerate); 991 visit2_fn(0, m_graph_index, SetType{}); 992 m_graph_index = NO_GRAPH_INDEX; 993 } 994 } 995 996 int GenericClusterImpl::GetLevel(const TxGraphImpl& graph) const noexcept 997 { 998 // GetLevel() does not work for empty Clusters. 999 if (!Assume(!m_linearization.empty())) return -1; 1000 1001 // Pick an arbitrary Entry that occurs in this Cluster. 1002 const auto& entry = graph.m_entries[m_mapping[m_linearization.front()]]; 1003 // See if there is a level whose Locator matches this Cluster, if so return that level. 1004 for (int level = 0; level < MAX_LEVELS; ++level) { 1005 if (entry.m_locator[level].cluster == this) return level; 1006 } 1007 // Given that we started with an Entry that occurs in this Cluster, one of its Locators must 1008 // point back to it. 1009 assert(false); 1010 return -1; 1011 } 1012 1013 int SingletonClusterImpl::GetLevel(const TxGraphImpl& graph) const noexcept 1014 { 1015 // GetLevel() does not work for empty Clusters. 1016 if (!Assume(GetTxCount())) return -1; 1017 1018 // Get the Entry in this Cluster. 1019 const auto& entry = graph.m_entries[m_graph_index]; 1020 // See if there is a level whose Locator matches this Cluster, if so return that level. 1021 for (int level = 0; level < MAX_LEVELS; ++level) { 1022 if (entry.m_locator[level].cluster == this) return level; 1023 } 1024 // Given that we started with an Entry that occurs in this Cluster, one of its Locators must 1025 // point back to it. 1026 assert(false); 1027 return -1; 1028 } 1029 1030 void TxGraphImpl::ClearLocator(int level, GraphIndex idx, bool oversized_tx) noexcept 1031 { 1032 auto& entry = m_entries[idx]; 1033 auto& clusterset = GetClusterSet(level); 1034 Assume(entry.m_locator[level].IsPresent()); 1035 // Change the locator from Present to Missing or Removed. 1036 if (level == 0 || !entry.m_locator[level - 1].IsPresent()) { 1037 entry.m_locator[level].SetMissing(); 1038 } else { 1039 entry.m_locator[level].SetRemoved(); 1040 clusterset.m_removed.push_back(idx); 1041 } 1042 // Update the transaction count. 1043 --clusterset.m_txcount; 1044 clusterset.m_txcount_oversized -= oversized_tx; 1045 // If clearing main, adjust the status of Locators of this transaction in staging, if it exists. 1046 if (level == 0 && GetTopLevel() == 1) { 1047 if (entry.m_locator[1].IsRemoved()) { 1048 entry.m_locator[1].SetMissing(); 1049 } else if (!entry.m_locator[1].IsPresent()) { 1050 --m_staging_clusterset->m_txcount; 1051 m_staging_clusterset->m_txcount_oversized -= oversized_tx; 1052 } 1053 } 1054 if (level == 0) ClearChunkData(entry); 1055 } 1056 1057 void GenericClusterImpl::RemoveChunkData(TxGraphImpl& graph) noexcept 1058 { 1059 for (DepGraphIndex idx : m_linearization) { 1060 auto& entry = graph.m_entries[m_mapping[idx]]; 1061 graph.ClearChunkData(entry); 1062 } 1063 } 1064 1065 void SingletonClusterImpl::RemoveChunkData(TxGraphImpl& graph) noexcept 1066 { 1067 if (GetTxCount() == 0) return; 1068 auto& entry = graph.m_entries[m_graph_index]; 1069 graph.ClearChunkData(entry); 1070 } 1071 1072 void GenericClusterImpl::Updated(TxGraphImpl& graph, int level, bool rename) noexcept 1073 { 1074 // Update all the Locators for this Cluster's Entry objects. 1075 for (DepGraphIndex idx : m_linearization) { 1076 auto& entry = graph.m_entries[m_mapping[idx]]; 1077 // Discard any potential ChunkData prior to modifying the Cluster (as that could 1078 // invalidate its ordering). 1079 if (level == 0 && !rename) graph.ClearChunkData(entry); 1080 entry.m_locator[level].SetPresent(this, idx); 1081 } 1082 // If this is for the main graph (level = 0), and the Cluster's quality is ACCEPTABLE or 1083 // OPTIMAL, compute its chunking and store its information in the Entry's m_main_lin_index 1084 // and m_main_chunk_feerate. These fields are only accessed after making the entire graph 1085 // ACCEPTABLE, so it is pointless to compute these if we haven't reached that quality level 1086 // yet. 1087 // When rename=true, this is always performed for level 0, to make sure the values inside the 1088 // entries remain consistent with the chunk index (otherwise unrelated chunk index operations 1089 // could cause the index to become corrupted, by inserting elements in the wrong place). 1090 if (level == 0 && (rename || IsAcceptable())) { 1091 auto chunking = ChunkLinearizationInfo(m_depgraph, m_linearization); 1092 LinearizationIndex lin_idx{0}; 1093 /** The sum of all chunk feerate FeeFracs with the same feerate as the current chunk, 1094 * up to and including the current chunk. */ 1095 FeeFrac equal_feerate_chunk_feerate; 1096 // Iterate over the chunks. 1097 for (unsigned chunk_idx = 0; chunk_idx < chunking.size(); ++chunk_idx) { 1098 auto& chunk = chunking[chunk_idx]; 1099 auto chunk_count = chunk.transactions.Count(); 1100 Assume(chunk_count > 0); 1101 // Update equal_feerate_chunk_feerate to include this chunk, starting over when the 1102 // feerate changed. 1103 if (chunk.feerate << equal_feerate_chunk_feerate) { 1104 equal_feerate_chunk_feerate = chunk.feerate; 1105 } else { 1106 // Note that this is adding fees to fees, and sizes to sizes, so the overall 1107 // ratio remains the same; it's just accounting for the size of the added chunk. 1108 equal_feerate_chunk_feerate += chunk.feerate; 1109 } 1110 // Determine the m_fallback_order maximum transaction in the chunk. 1111 auto it = chunk.transactions.begin(); 1112 GraphIndex max_element = m_mapping[*it]; 1113 ++it; 1114 while (it != chunk.transactions.end()) { 1115 GraphIndex this_element = m_mapping[*it]; 1116 if (graph.m_fallback_order(*graph.m_entries[this_element].m_ref, *graph.m_entries[max_element].m_ref) > 0) { 1117 max_element = this_element; 1118 } 1119 ++it; 1120 } 1121 // Iterate over the transactions in the linearization, which must match those in chunk. 1122 while (true) { 1123 DepGraphIndex idx = m_linearization[lin_idx]; 1124 GraphIndex graph_idx = m_mapping[idx]; 1125 auto& entry = graph.m_entries[graph_idx]; 1126 entry.m_main_lin_index = lin_idx++; 1127 entry.m_main_chunk_feerate = FeePerWeight::FromFeeFrac(chunk.feerate); 1128 entry.m_main_equal_feerate_chunk_prefix_size = equal_feerate_chunk_feerate.size; 1129 entry.m_main_max_chunk_fallback = max_element; 1130 Assume(chunk.transactions[idx]); 1131 chunk.transactions.Reset(idx); 1132 if (chunk.transactions.None()) { 1133 // Last transaction in the chunk. 1134 if (chunk_count == 1 && chunk_idx + 1 == chunking.size()) { 1135 // If this is the final chunk of the cluster, and it contains just a single 1136 // transaction (which will always be true for the very common singleton 1137 // clusters), store the special value -1 as chunk count. 1138 chunk_count = LinearizationIndex(-1); 1139 } 1140 if (!rename) graph.CreateChunkData(graph_idx, chunk_count); 1141 break; 1142 } 1143 } 1144 } 1145 } 1146 } 1147 1148 void SingletonClusterImpl::Updated(TxGraphImpl& graph, int level, bool rename) noexcept 1149 { 1150 // Don't do anything if this is empty. 1151 if (GetTxCount() == 0) return; 1152 1153 auto& entry = graph.m_entries[m_graph_index]; 1154 // Discard any potential ChunkData prior to modifying the Cluster (as that could 1155 // invalidate its ordering). 1156 if (level == 0 && !rename) graph.ClearChunkData(entry); 1157 entry.m_locator[level].SetPresent(this, 0); 1158 // If this is for the main graph (level = 0), compute its chunking and store its information in 1159 // the Entry's m_main_lin_index and m_main_chunk_feerate. 1160 if (level == 0 && (rename || IsAcceptable())) { 1161 entry.m_main_lin_index = 0; 1162 entry.m_main_chunk_feerate = m_feerate; 1163 entry.m_main_equal_feerate_chunk_prefix_size = m_feerate.size; 1164 entry.m_main_max_chunk_fallback = m_graph_index; 1165 // Always use the special LinearizationIndex(-1), indicating singleton chunk at end of 1166 // Cluster, here. 1167 if (!rename) graph.CreateChunkData(m_graph_index, LinearizationIndex(-1)); 1168 } 1169 } 1170 1171 void GenericClusterImpl::GetConflicts(const TxGraphImpl& graph, std::vector<Cluster*>& out) const noexcept 1172 { 1173 for (auto i : m_linearization) { 1174 auto& entry = graph.m_entries[m_mapping[i]]; 1175 // For every transaction Entry in this Cluster, if it also exists in a lower-level Cluster, 1176 // then that Cluster conflicts. 1177 if (entry.m_locator[0].IsPresent()) { 1178 out.push_back(entry.m_locator[0].cluster); 1179 } 1180 } 1181 } 1182 1183 void SingletonClusterImpl::GetConflicts(const TxGraphImpl& graph, std::vector<Cluster*>& out) const noexcept 1184 { 1185 // Empty clusters have no conflicts. 1186 if (GetTxCount() == 0) return; 1187 1188 auto& entry = graph.m_entries[m_graph_index]; 1189 // If the transaction in this Cluster also exists in a lower-level Cluster, then that Cluster 1190 // conflicts. 1191 if (entry.m_locator[0].IsPresent()) { 1192 out.push_back(entry.m_locator[0].cluster); 1193 } 1194 } 1195 1196 std::vector<Cluster*> TxGraphImpl::GetConflicts() const noexcept 1197 { 1198 Assume(GetTopLevel() == 1); 1199 auto& clusterset = GetClusterSet(1); 1200 std::vector<Cluster*> ret; 1201 // All main Clusters containing transactions in m_removed (so (P,R) ones) are conflicts. 1202 for (auto i : clusterset.m_removed) { 1203 auto& entry = m_entries[i]; 1204 if (entry.m_locator[0].IsPresent()) { 1205 ret.push_back(entry.m_locator[0].cluster); 1206 } 1207 } 1208 // Then go over all Clusters at this level, and find their conflicts (the (P,P) ones). 1209 for (int quality = 0; quality < int(QualityLevel::NONE); ++quality) { 1210 auto& clusters = clusterset.m_clusters[quality]; 1211 for (const auto& cluster : clusters) { 1212 cluster->GetConflicts(*this, ret); 1213 } 1214 } 1215 // Deduplicate the result (the same Cluster may appear multiple times). 1216 std::sort(ret.begin(), ret.end(), [](Cluster* a, Cluster* b) noexcept { return CompareClusters(a, b) < 0; }); 1217 ret.erase(std::unique(ret.begin(), ret.end()), ret.end()); 1218 return ret; 1219 } 1220 1221 Cluster* GenericClusterImpl::CopyToStaging(TxGraphImpl& graph) const noexcept 1222 { 1223 // Construct an empty Cluster. 1224 auto ret = graph.CreateEmptyGenericCluster(); 1225 auto ptr = ret.get(); 1226 // Copy depgraph, mapping, and linearization. 1227 ptr->m_depgraph = m_depgraph; 1228 ptr->m_mapping = m_mapping; 1229 ptr->m_linearization = m_linearization; 1230 // Insert the new Cluster into the graph. 1231 graph.InsertCluster(/*level=*/1, std::move(ret), m_quality); 1232 // Update its Locators. 1233 ptr->Updated(graph, /*level=*/1, /*rename=*/false); 1234 // Update memory usage. 1235 graph.GetClusterSet(/*level=*/1).m_cluster_usage += ptr->TotalMemoryUsage(); 1236 return ptr; 1237 } 1238 1239 Cluster* SingletonClusterImpl::CopyToStaging(TxGraphImpl& graph) const noexcept 1240 { 1241 // Construct an empty Cluster. 1242 auto ret = graph.CreateEmptySingletonCluster(); 1243 auto ptr = ret.get(); 1244 // Copy data. 1245 ptr->m_graph_index = m_graph_index; 1246 ptr->m_feerate = m_feerate; 1247 // Insert the new Cluster into the graph. 1248 graph.InsertCluster(/*level=*/1, std::move(ret), m_quality); 1249 // Update its Locators. 1250 ptr->Updated(graph, /*level=*/1, /*rename=*/false); 1251 // Update memory usage. 1252 graph.GetClusterSet(/*level=*/1).m_cluster_usage += ptr->TotalMemoryUsage(); 1253 return ptr; 1254 } 1255 1256 void GenericClusterImpl::ApplyRemovals(TxGraphImpl& graph, int level, std::span<GraphIndex>& to_remove) noexcept 1257 { 1258 // Iterate over the prefix of to_remove that applies to this cluster. 1259 Assume(!to_remove.empty()); 1260 SetType todo; 1261 graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage(); 1262 do { 1263 GraphIndex idx = to_remove.front(); 1264 Assume(idx < graph.m_entries.size()); 1265 auto& entry = graph.m_entries[idx]; 1266 auto& locator = entry.m_locator[level]; 1267 // Stop once we hit an entry that applies to another Cluster. 1268 if (locator.cluster != this) break; 1269 // - Remember it in a set of to-remove DepGraphIndexes. 1270 todo.Set(locator.index); 1271 // - Remove from m_mapping. This isn't strictly necessary as unused positions in m_mapping 1272 // are just never accessed, but set it to -1 here to increase the ability to detect a bug 1273 // that causes it to be accessed regardless. 1274 m_mapping[locator.index] = GraphIndex(-1); 1275 // - Remove its linearization index from the Entry (if in main). 1276 if (level == 0) { 1277 entry.m_main_lin_index = LinearizationIndex(-1); 1278 } 1279 // - Mark it as missing/removed in the Entry's locator. 1280 graph.ClearLocator(level, idx, m_quality == QualityLevel::OVERSIZED_SINGLETON); 1281 to_remove = to_remove.subspan(1); 1282 } while(!to_remove.empty()); 1283 1284 Assume(todo.Any()); 1285 // Wipe from the Cluster's DepGraph (this is O(n) regardless of the number of entries 1286 // removed, so we benefit from batching all the removals). 1287 m_depgraph.RemoveTransactions(todo); 1288 m_mapping.resize(m_depgraph.PositionRange()); 1289 1290 // Filter removed transactions out of m_linearization. 1291 m_linearization.erase(std::remove_if(m_linearization.begin(), m_linearization.end(), 1292 [&](auto pos) { return todo[pos]; }), 1293 m_linearization.end()); 1294 1295 Compact(); 1296 graph.GetClusterSet(level).m_cluster_usage += TotalMemoryUsage(); 1297 auto new_quality = IsTopological() ? QualityLevel::NEEDS_SPLIT : QualityLevel::NEEDS_SPLIT_FIX; 1298 graph.SetClusterQuality(level, m_quality, m_setindex, new_quality); 1299 Updated(graph, /*level=*/level, /*rename=*/false); 1300 } 1301 1302 void SingletonClusterImpl::ApplyRemovals(TxGraphImpl& graph, int level, std::span<GraphIndex>& to_remove) noexcept 1303 { 1304 // We can only remove the one transaction this Cluster has. 1305 Assume(!to_remove.empty()); 1306 Assume(GetTxCount()); 1307 Assume(to_remove.front() == m_graph_index); 1308 // Pop all copies of m_graph_index from the front of to_remove (at least one, but there may be 1309 // multiple). 1310 do { 1311 to_remove = to_remove.subspan(1); 1312 } while (!to_remove.empty() && to_remove.front() == m_graph_index); 1313 // Clear this cluster. 1314 graph.ClearLocator(level, m_graph_index, m_quality == QualityLevel::OVERSIZED_SINGLETON); 1315 m_graph_index = NO_GRAPH_INDEX; 1316 graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::NEEDS_SPLIT); 1317 // No need to account for m_cluster_usage changes here, as SingletonClusterImpl has constant 1318 // memory usage. 1319 } 1320 1321 void GenericClusterImpl::Clear(TxGraphImpl& graph, int level) noexcept 1322 { 1323 Assume(GetTxCount()); 1324 graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage(); 1325 for (auto i : m_linearization) { 1326 graph.ClearLocator(level, m_mapping[i], m_quality == QualityLevel::OVERSIZED_SINGLETON); 1327 } 1328 m_depgraph = {}; 1329 m_linearization.clear(); 1330 m_mapping.clear(); 1331 } 1332 1333 void SingletonClusterImpl::Clear(TxGraphImpl& graph, int level) noexcept 1334 { 1335 Assume(GetTxCount()); 1336 graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage(); 1337 graph.ClearLocator(level, m_graph_index, m_quality == QualityLevel::OVERSIZED_SINGLETON); 1338 m_graph_index = NO_GRAPH_INDEX; 1339 } 1340 1341 void GenericClusterImpl::MoveToMain(TxGraphImpl& graph) noexcept 1342 { 1343 for (auto i : m_linearization) { 1344 GraphIndex idx = m_mapping[i]; 1345 auto& entry = graph.m_entries[idx]; 1346 entry.m_locator[1].SetMissing(); 1347 } 1348 auto quality = m_quality; 1349 // Subtract memory usage from staging and add it to main. 1350 graph.GetClusterSet(/*level=*/1).m_cluster_usage -= TotalMemoryUsage(); 1351 graph.GetClusterSet(/*level=*/0).m_cluster_usage += TotalMemoryUsage(); 1352 // Remove cluster itself from staging and add it to main. 1353 auto cluster = graph.ExtractCluster(1, quality, m_setindex); 1354 graph.InsertCluster(/*level=*/0, std::move(cluster), quality); 1355 Updated(graph, /*level=*/0, /*rename=*/false); 1356 } 1357 1358 void SingletonClusterImpl::MoveToMain(TxGraphImpl& graph) noexcept 1359 { 1360 if (GetTxCount()) { 1361 auto& entry = graph.m_entries[m_graph_index]; 1362 entry.m_locator[1].SetMissing(); 1363 } 1364 auto quality = m_quality; 1365 graph.GetClusterSet(/*level=*/1).m_cluster_usage -= TotalMemoryUsage(); 1366 auto cluster = graph.ExtractCluster(/*level=*/1, quality, m_setindex); 1367 graph.InsertCluster(/*level=*/0, std::move(cluster), quality); 1368 graph.GetClusterSet(/*level=*/0).m_cluster_usage += TotalMemoryUsage(); 1369 Updated(graph, /*level=*/0, /*rename=*/false); 1370 } 1371 1372 void GenericClusterImpl::Compact() noexcept 1373 { 1374 m_linearization.shrink_to_fit(); 1375 m_mapping.shrink_to_fit(); 1376 m_depgraph.Compact(); 1377 } 1378 1379 void SingletonClusterImpl::Compact() noexcept 1380 { 1381 // Nothing to compact; SingletonClusterImpl is constant size. 1382 } 1383 1384 void GenericClusterImpl::AppendChunkFeerates(std::vector<FeeFrac>& ret) const noexcept 1385 { 1386 auto chunk_feerates = ChunkLinearization(m_depgraph, m_linearization); 1387 ret.reserve(ret.size() + chunk_feerates.size()); 1388 ret.insert(ret.end(), chunk_feerates.begin(), chunk_feerates.end()); 1389 } 1390 1391 void SingletonClusterImpl::AppendChunkFeerates(std::vector<FeeFrac>& ret) const noexcept 1392 { 1393 if (GetTxCount()) { 1394 ret.push_back(m_feerate); 1395 } 1396 } 1397 1398 uint64_t GenericClusterImpl::AppendTrimData(std::vector<TrimTxData>& ret, std::vector<std::pair<GraphIndex, GraphIndex>>& deps) const noexcept 1399 { 1400 Assume(IsAcceptable()); 1401 auto linchunking = ChunkLinearizationInfo(m_depgraph, m_linearization); 1402 LinearizationIndex pos{0}; 1403 uint64_t size{0}; 1404 auto prev_index = GraphIndex(-1); 1405 // Iterate over the chunks of this cluster's linearization. 1406 for (const auto& [chunk, chunk_feerate] : linchunking) { 1407 // Iterate over the transactions of that chunk, in linearization order. 1408 auto chunk_tx_count = chunk.Count(); 1409 for (unsigned j = 0; j < chunk_tx_count; ++j) { 1410 auto cluster_idx = m_linearization[pos]; 1411 // The transaction must appear in the chunk. 1412 Assume(chunk[cluster_idx]); 1413 // Construct a new element in ret. 1414 auto& entry = ret.emplace_back(); 1415 entry.m_chunk_feerate = FeePerWeight::FromFeeFrac(chunk_feerate); 1416 entry.m_index = m_mapping[cluster_idx]; 1417 // If this is not the first transaction of the cluster linearization, it has an 1418 // implicit dependency on its predecessor. 1419 if (pos != 0) deps.emplace_back(prev_index, entry.m_index); 1420 prev_index = entry.m_index; 1421 entry.m_tx_size = m_depgraph.FeeRate(cluster_idx).size; 1422 size += entry.m_tx_size; 1423 ++pos; 1424 } 1425 } 1426 return size; 1427 } 1428 1429 uint64_t SingletonClusterImpl::AppendTrimData(std::vector<TrimTxData>& ret, std::vector<std::pair<GraphIndex, GraphIndex>>& deps) const noexcept 1430 { 1431 if (!GetTxCount()) return 0; 1432 auto& entry = ret.emplace_back(); 1433 entry.m_chunk_feerate = m_feerate; 1434 entry.m_index = m_graph_index; 1435 entry.m_tx_size = m_feerate.size; 1436 return m_feerate.size; 1437 } 1438 1439 bool GenericClusterImpl::Split(TxGraphImpl& graph, int level) noexcept 1440 { 1441 // This function can only be called when the Cluster needs splitting. 1442 Assume(NeedsSplitting()); 1443 // Determine the new quality the split-off Clusters will have. 1444 QualityLevel new_quality = IsTopological() ? QualityLevel::NEEDS_RELINEARIZE : QualityLevel::NEEDS_FIX; 1445 /** Which positions are still left in this Cluster. */ 1446 auto todo = m_depgraph.Positions(); 1447 /** Mapping from transaction positions in this Cluster to the Cluster where it ends up, and 1448 * its position therein. */ 1449 std::vector<std::pair<Cluster*, DepGraphIndex>> remap(m_depgraph.PositionRange()); 1450 std::vector<Cluster*> new_clusters; 1451 bool first{true}; 1452 // Iterate over the connected components of this Cluster's m_depgraph. 1453 while (todo.Any()) { 1454 auto component = m_depgraph.FindConnectedComponent(todo); 1455 auto component_size = component.Count(); 1456 auto split_quality = component_size <= 1 ? QualityLevel::OPTIMAL : new_quality; 1457 if (first && component == todo && SetType::Fill(component_size) == component && component_size >= MIN_INTENDED_TX_COUNT) { 1458 // The existing Cluster is an entire component, without holes. Leave it be, but update 1459 // its quality. If there are holes, we continue, so that the Cluster is reconstructed 1460 // without holes, reducing memory usage. If the component's size is below the intended 1461 // transaction count for this Cluster implementation, continue so that it can get 1462 // converted. 1463 Assume(todo == m_depgraph.Positions()); 1464 graph.SetClusterQuality(level, m_quality, m_setindex, split_quality); 1465 // If this made the quality ACCEPTABLE or OPTIMAL, we need to compute and cache its 1466 // chunking. 1467 Updated(graph, /*level=*/level, /*rename=*/false); 1468 return false; 1469 } 1470 first = false; 1471 // Construct a new Cluster to hold the found component. 1472 auto new_cluster = graph.CreateEmptyCluster(component_size); 1473 new_clusters.push_back(new_cluster.get()); 1474 // Remember that all the component's transactions go to this new Cluster. The positions 1475 // will be determined below, so use -1 for now. 1476 for (auto i : component) { 1477 remap[i] = {new_cluster.get(), DepGraphIndex(-1)}; 1478 } 1479 graph.InsertCluster(level, std::move(new_cluster), split_quality); 1480 todo -= component; 1481 } 1482 // We have to split the Cluster up. Remove accounting for the existing one first. 1483 graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage(); 1484 // Redistribute the transactions. 1485 for (auto i : m_linearization) { 1486 /** The cluster which transaction originally in position i is moved to. */ 1487 Cluster* new_cluster = remap[i].first; 1488 // Copy the transaction to the new cluster's depgraph, and remember the position. 1489 remap[i].second = new_cluster->AppendTransaction(m_mapping[i], FeePerWeight::FromFeeFrac(m_depgraph.FeeRate(i))); 1490 } 1491 // Redistribute the dependencies. 1492 for (auto i : m_linearization) { 1493 /** The cluster transaction in position i is moved to. */ 1494 Cluster* new_cluster = remap[i].first; 1495 // Copy its parents, translating positions. 1496 SetType new_parents; 1497 for (auto par : m_depgraph.GetReducedParents(i)) new_parents.Set(remap[par].second); 1498 new_cluster->AddDependencies(new_parents, remap[i].second); 1499 } 1500 // Update all the Locators of moved transactions, and memory usage. 1501 for (Cluster* new_cluster : new_clusters) { 1502 new_cluster->Updated(graph, /*level=*/level, /*rename=*/false); 1503 new_cluster->Compact(); 1504 graph.GetClusterSet(level).m_cluster_usage += new_cluster->TotalMemoryUsage(); 1505 } 1506 // Wipe this Cluster, and return that it needs to be deleted. 1507 m_depgraph = DepGraph<SetType>{}; 1508 m_mapping.clear(); 1509 m_linearization.clear(); 1510 return true; 1511 } 1512 1513 bool SingletonClusterImpl::Split(TxGraphImpl& graph, int level) noexcept 1514 { 1515 Assume(NeedsSplitting()); 1516 Assume(!GetTxCount()); 1517 graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage(); 1518 return true; 1519 } 1520 1521 void GenericClusterImpl::Merge(TxGraphImpl& graph, int level, Cluster& other) noexcept 1522 { 1523 /** Vector to store the positions in this Cluster for each position in other. */ 1524 std::vector<DepGraphIndex> remap(other.GetDepGraphIndexRange()); 1525 // Iterate over all transactions in the other Cluster (the one being absorbed). 1526 other.ExtractTransactions([&](DepGraphIndex pos, GraphIndex idx, FeePerWeight feerate) noexcept { 1527 // Copy the transaction into this Cluster, and remember its position. 1528 auto new_pos = m_depgraph.AddTransaction(feerate); 1529 // Since this cluster must have been made hole-free before being merged into, all added 1530 // transactions should appear at the end. 1531 Assume(new_pos == m_mapping.size()); 1532 remap[pos] = new_pos; 1533 m_mapping.push_back(idx); 1534 m_linearization.push_back(new_pos); 1535 }, [&](DepGraphIndex pos, GraphIndex idx, SetType other_parents) noexcept { 1536 // Copy the transaction's dependencies, translating them using remap. 1537 SetType parents; 1538 for (auto par : other_parents) { 1539 parents.Set(remap[par]); 1540 } 1541 m_depgraph.AddDependencies(parents, remap[pos]); 1542 // Update the transaction's Locator. There is no need to call Updated() to update chunk 1543 // feerates, as Updated() will be invoked by Cluster::ApplyDependencies on the resulting 1544 // merged Cluster later anyway. 1545 auto& entry = graph.m_entries[idx]; 1546 // Discard any potential ChunkData prior to modifying the Cluster (as that could 1547 // invalidate its ordering). 1548 if (level == 0) graph.ClearChunkData(entry); 1549 entry.m_locator[level].SetPresent(this, remap[pos]); 1550 }); 1551 } 1552 1553 void SingletonClusterImpl::Merge(TxGraphImpl&, int, Cluster&) noexcept 1554 { 1555 // Nothing can be merged into a singleton; it should have been converted to GenericClusterImpl first. 1556 Assume(false); 1557 } 1558 1559 void GenericClusterImpl::ApplyDependencies(TxGraphImpl& graph, int level, std::span<std::pair<GraphIndex, GraphIndex>> to_apply) noexcept 1560 { 1561 // Sort the list of dependencies to apply by child, so those can be applied in batch. 1562 std::sort(to_apply.begin(), to_apply.end(), [](auto& a, auto& b) { return a.second < b.second; }); 1563 // Iterate over groups of to-be-added dependencies with the same child. 1564 auto it = to_apply.begin(); 1565 while (it != to_apply.end()) { 1566 auto& first_child = graph.m_entries[it->second].m_locator[level]; 1567 const auto child_idx = first_child.index; 1568 // Iterate over all to-be-added dependencies within that same child, gather the relevant 1569 // parents. 1570 SetType parents; 1571 while (it != to_apply.end()) { 1572 auto& child = graph.m_entries[it->second].m_locator[level]; 1573 auto& parent = graph.m_entries[it->first].m_locator[level]; 1574 Assume(child.cluster == this && parent.cluster == this); 1575 if (child.index != child_idx) break; 1576 parents.Set(parent.index); 1577 ++it; 1578 } 1579 // Push all dependencies to the underlying DepGraph. Note that this is O(N) in the size of 1580 // the cluster, regardless of the number of parents being added, so batching them together 1581 // has a performance benefit. 1582 m_depgraph.AddDependencies(parents, child_idx); 1583 } 1584 1585 // Finally set the cluster to NEEDS_FIX, so its linearization is fixed the next time it is 1586 // attempted to be made ACCEPTABLE. 1587 Assume(!NeedsSplitting()); 1588 Assume(!IsOversized()); 1589 graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::NEEDS_FIX); 1590 1591 // Finally push the changes to graph.m_entries. 1592 Updated(graph, /*level=*/level, /*rename=*/false); 1593 } 1594 1595 void SingletonClusterImpl::ApplyDependencies(TxGraphImpl&, int, std::span<std::pair<GraphIndex, GraphIndex>>) noexcept 1596 { 1597 // Nothing can actually be applied. 1598 Assume(false); 1599 } 1600 1601 TxGraphImpl::~TxGraphImpl() noexcept 1602 { 1603 // If Refs outlive the TxGraphImpl they refer to, unlink them, so that their destructor does not 1604 // try to reach into a non-existing TxGraphImpl anymore. 1605 for (auto& entry : m_entries) { 1606 if (entry.m_ref != nullptr) { 1607 GetRefGraph(*entry.m_ref) = nullptr; 1608 } 1609 } 1610 } 1611 1612 std::unique_ptr<Cluster> TxGraphImpl::ExtractCluster(int level, QualityLevel quality, ClusterSetIndex setindex) noexcept 1613 { 1614 Assume(quality != QualityLevel::NONE); 1615 1616 auto& clusterset = GetClusterSet(level); 1617 auto& quality_clusters = clusterset.m_clusters[int(quality)]; 1618 Assume(setindex < quality_clusters.size()); 1619 1620 // Extract the Cluster-owning unique_ptr. 1621 std::unique_ptr<Cluster> ret = std::move(quality_clusters[setindex]); 1622 ret->m_quality = QualityLevel::NONE; 1623 ret->m_setindex = ClusterSetIndex(-1); 1624 1625 // Clean up space in quality_cluster. 1626 auto max_setindex = quality_clusters.size() - 1; 1627 if (setindex != max_setindex) { 1628 // If the cluster was not the last element of quality_clusters, move that to take its place. 1629 quality_clusters.back()->m_setindex = setindex; 1630 quality_clusters[setindex] = std::move(quality_clusters.back()); 1631 } 1632 // The last element of quality_clusters is now unused; drop it. 1633 quality_clusters.pop_back(); 1634 1635 return ret; 1636 } 1637 1638 ClusterSetIndex TxGraphImpl::InsertCluster(int level, std::unique_ptr<Cluster>&& cluster, QualityLevel quality) noexcept 1639 { 1640 // Cannot insert with quality level NONE (as that would mean not inserted). 1641 Assume(quality != QualityLevel::NONE); 1642 // The passed-in Cluster must not currently be in the TxGraphImpl. 1643 Assume(cluster->m_quality == QualityLevel::NONE); 1644 1645 // Append it at the end of the relevant TxGraphImpl::m_cluster. 1646 auto& clusterset = GetClusterSet(level); 1647 auto& quality_clusters = clusterset.m_clusters[int(quality)]; 1648 ClusterSetIndex ret = quality_clusters.size(); 1649 cluster->m_quality = quality; 1650 cluster->m_setindex = ret; 1651 quality_clusters.push_back(std::move(cluster)); 1652 return ret; 1653 } 1654 1655 void TxGraphImpl::SetClusterQuality(int level, QualityLevel old_quality, ClusterSetIndex old_index, QualityLevel new_quality) noexcept 1656 { 1657 Assume(new_quality != QualityLevel::NONE); 1658 1659 // Don't do anything if the quality did not change. 1660 if (old_quality == new_quality) return; 1661 // Extract the cluster from where it currently resides. 1662 auto cluster_ptr = ExtractCluster(level, old_quality, old_index); 1663 // And re-insert it where it belongs. 1664 InsertCluster(level, std::move(cluster_ptr), new_quality); 1665 } 1666 1667 void TxGraphImpl::DeleteCluster(Cluster& cluster, int level) noexcept 1668 { 1669 // Extract the cluster from where it currently resides. 1670 auto cluster_ptr = ExtractCluster(level, cluster.m_quality, cluster.m_setindex); 1671 // And throw it away. 1672 cluster_ptr.reset(); 1673 } 1674 1675 std::pair<Cluster*, int> TxGraphImpl::FindClusterAndLevel(GraphIndex idx, int level) const noexcept 1676 { 1677 Assume(level >= 0 && level <= GetTopLevel()); 1678 auto& entry = m_entries[idx]; 1679 // Search the entry's locators from top to bottom. 1680 for (int l = level; l >= 0; --l) { 1681 // If the locator is missing, dig deeper; it may exist at a lower level and therefore be 1682 // implicitly existing at this level too. 1683 if (entry.m_locator[l].IsMissing()) continue; 1684 // If the locator has the entry marked as explicitly removed, stop. 1685 if (entry.m_locator[l].IsRemoved()) break; 1686 // Otherwise, we have found the topmost ClusterSet that contains this entry. 1687 return {entry.m_locator[l].cluster, l}; 1688 } 1689 // If no non-empty locator was found, or an explicitly removed was hit, return nothing. 1690 return {nullptr, -1}; 1691 } 1692 1693 Cluster* TxGraphImpl::PullIn(Cluster* cluster, int level) noexcept 1694 { 1695 int to_level = GetTopLevel(); 1696 Assume(to_level == 1); 1697 Assume(level <= to_level); 1698 // Copy the Cluster from main to staging, if it's not already there. 1699 if (level == 0) { 1700 // Make the Cluster Acceptable before copying. This isn't strictly necessary, but doing it 1701 // now avoids doing double work later. 1702 MakeAcceptable(*cluster, level); 1703 cluster = cluster->CopyToStaging(*this); 1704 } 1705 return cluster; 1706 } 1707 1708 void TxGraphImpl::ApplyRemovals(int up_to_level) noexcept 1709 { 1710 Assume(up_to_level >= 0 && up_to_level <= GetTopLevel()); 1711 for (int level = 0; level <= up_to_level; ++level) { 1712 auto& clusterset = GetClusterSet(level); 1713 auto& to_remove = clusterset.m_to_remove; 1714 // Skip if there is nothing to remove in this level. 1715 if (to_remove.empty()) continue; 1716 // Pull in all Clusters that are not in staging. 1717 if (level == 1) { 1718 for (GraphIndex index : to_remove) { 1719 auto [cluster, cluster_level] = FindClusterAndLevel(index, level); 1720 if (cluster != nullptr) PullIn(cluster, cluster_level); 1721 } 1722 } 1723 // Group the set of to-be-removed entries by Cluster::m_sequence. 1724 std::sort(to_remove.begin(), to_remove.end(), [&](GraphIndex a, GraphIndex b) noexcept { 1725 Cluster* cluster_a = m_entries[a].m_locator[level].cluster; 1726 Cluster* cluster_b = m_entries[b].m_locator[level].cluster; 1727 return CompareClusters(cluster_a, cluster_b) < 0; 1728 }); 1729 // Process per Cluster. 1730 std::span to_remove_span{to_remove}; 1731 while (!to_remove_span.empty()) { 1732 Cluster* cluster = m_entries[to_remove_span.front()].m_locator[level].cluster; 1733 if (cluster != nullptr) { 1734 // If the first to_remove_span entry's Cluster exists, hand to_remove_span to it, so it 1735 // can pop off whatever applies to it. 1736 cluster->ApplyRemovals(*this, level, to_remove_span); 1737 } else { 1738 // Otherwise, skip this already-removed entry. This may happen when 1739 // RemoveTransaction was called twice on the same Ref, for example. 1740 to_remove_span = to_remove_span.subspan(1); 1741 } 1742 } 1743 to_remove.clear(); 1744 } 1745 Compact(); 1746 } 1747 1748 void TxGraphImpl::SwapIndexes(GraphIndex a, GraphIndex b, std::vector<Cluster*>& affected_main) noexcept 1749 { 1750 Assume(a < m_entries.size()); 1751 Assume(b < m_entries.size()); 1752 // Swap the Entry objects. 1753 std::swap(m_entries[a], m_entries[b]); 1754 // Iterate over both objects. 1755 for (int i = 0; i < 2; ++i) { 1756 GraphIndex idx = i ? b : a; 1757 Entry& entry = m_entries[idx]; 1758 // Update linked Ref, if any exists. 1759 if (entry.m_ref) GetRefIndex(*entry.m_ref) = idx; 1760 // Update linked chunk index entries, if any exist. 1761 if (entry.m_main_chunkindex_iterator != m_main_chunkindex.end()) { 1762 entry.m_main_chunkindex_iterator->m_graph_index = idx; 1763 } 1764 // Update the locators for both levels. 1765 for (int level = 0; level < MAX_LEVELS; ++level) { 1766 Locator& locator = entry.m_locator[level]; 1767 if (locator.IsPresent()) { 1768 locator.cluster->UpdateMapping(locator.index, idx); 1769 if (level == 0) affected_main.push_back(locator.cluster); 1770 } 1771 } 1772 } 1773 } 1774 1775 void TxGraphImpl::Compact() noexcept 1776 { 1777 // We cannot compact while any to-be-applied operations or staged removals remain as we'd need 1778 // to rewrite them. It is easier to delay the compaction until they have been applied. 1779 if (!m_main_clusterset.m_deps_to_add.empty()) return; 1780 if (!m_main_clusterset.m_to_remove.empty()) return; 1781 Assume(m_main_clusterset.m_removed.empty()); // non-staging m_removed is always empty 1782 if (m_staging_clusterset.has_value()) { 1783 if (!m_staging_clusterset->m_deps_to_add.empty()) return; 1784 if (!m_staging_clusterset->m_to_remove.empty()) return; 1785 if (!m_staging_clusterset->m_removed.empty()) return; 1786 } 1787 1788 // Release memory used by discarded ChunkData index entries. 1789 ClearShrink(m_main_chunkindex_discarded); 1790 1791 // Sort the GraphIndexes that need to be cleaned up. They are sorted in reverse, so the last 1792 // ones get processed first. This means earlier-processed GraphIndexes will not cause moving of 1793 // later-processed ones during the "swap with end of m_entries" step below (which might 1794 // invalidate them). 1795 std::sort(m_unlinked.begin(), m_unlinked.end(), std::greater{}); 1796 1797 std::vector<Cluster*> affected_main; 1798 auto last = GraphIndex(-1); 1799 for (GraphIndex idx : m_unlinked) { 1800 // m_unlinked should never contain the same GraphIndex twice (the code below would fail 1801 // if so, because GraphIndexes get invalidated by removing them). 1802 Assume(idx != last); 1803 last = idx; 1804 1805 // Make sure the entry is unlinked. 1806 Entry& entry = m_entries[idx]; 1807 Assume(entry.m_ref == nullptr); 1808 // Make sure the entry does not occur in the graph. 1809 for (int level = 0; level < MAX_LEVELS; ++level) { 1810 Assume(!entry.m_locator[level].IsPresent()); 1811 } 1812 1813 // Move the entry to the end. 1814 if (idx != m_entries.size() - 1) SwapIndexes(idx, m_entries.size() - 1, affected_main); 1815 // Drop the entry for idx, now that it is at the end. 1816 m_entries.pop_back(); 1817 } 1818 1819 // Update the affected clusters, to fixup Entry::m_main_max_chunk_fallback values which may 1820 // have become outdated due to the compaction above. 1821 std::sort(affected_main.begin(), affected_main.end()); 1822 affected_main.erase(std::unique(affected_main.begin(), affected_main.end()), affected_main.end()); 1823 for (Cluster* cluster : affected_main) { 1824 cluster->Updated(*this, /*level=*/0, /*rename=*/true); 1825 } 1826 m_unlinked.clear(); 1827 } 1828 1829 void TxGraphImpl::Split(Cluster& cluster, int level) noexcept 1830 { 1831 // To split a Cluster, first make sure all removals are applied (as we might need to split 1832 // again afterwards otherwise). 1833 ApplyRemovals(level); 1834 bool del = cluster.Split(*this, level); 1835 if (del) { 1836 // Cluster::Split reports whether the Cluster is to be deleted. 1837 DeleteCluster(cluster, level); 1838 } 1839 } 1840 1841 void TxGraphImpl::SplitAll(int up_to_level) noexcept 1842 { 1843 Assume(up_to_level >= 0 && up_to_level <= GetTopLevel()); 1844 // Before splitting all Cluster, first make sure all removals are applied. 1845 ApplyRemovals(up_to_level); 1846 for (int level = 0; level <= up_to_level; ++level) { 1847 for (auto quality : {QualityLevel::NEEDS_SPLIT_FIX, QualityLevel::NEEDS_SPLIT}) { 1848 auto& queue = GetClusterSet(level).m_clusters[int(quality)]; 1849 while (!queue.empty()) { 1850 Split(*queue.back().get(), level); 1851 } 1852 } 1853 } 1854 } 1855 1856 void TxGraphImpl::GroupClusters(int level) noexcept 1857 { 1858 auto& clusterset = GetClusterSet(level); 1859 // If the groupings have been computed already, nothing is left to be done. 1860 if (clusterset.m_group_data.has_value()) return; 1861 1862 // Before computing which Clusters need to be merged together, first apply all removals and 1863 // split the Clusters into connected components. If we would group first, we might end up 1864 // with inefficient and/or oversized Clusters which just end up being split again anyway. 1865 SplitAll(level); 1866 1867 /** Annotated clusters: an entry for each Cluster, together with the sequence number for the 1868 * representative for the partition it is in (initially its own, later that of the 1869 * to-be-merged group). */ 1870 std::vector<std::pair<Cluster*, uint64_t>> an_clusters; 1871 /** Annotated dependencies: an entry for each m_deps_to_add entry (excluding ones that apply 1872 * to removed transactions), together with the sequence number of the representative root of 1873 * Clusters it applies to (initially that of the child Cluster, later that of the 1874 * to-be-merged group). */ 1875 std::vector<std::pair<std::pair<GraphIndex, GraphIndex>, uint64_t>> an_deps; 1876 1877 // Construct an an_clusters entry for every oversized cluster, including ones from levels below, 1878 // as they may be inherited in this one. 1879 for (int level_iter = 0; level_iter <= level; ++level_iter) { 1880 for (auto& cluster : GetClusterSet(level_iter).m_clusters[int(QualityLevel::OVERSIZED_SINGLETON)]) { 1881 auto graph_idx = cluster->GetClusterEntry(0); 1882 auto cur_cluster = FindCluster(graph_idx, level); 1883 if (cur_cluster == nullptr) continue; 1884 an_clusters.emplace_back(cur_cluster, cur_cluster->m_sequence); 1885 } 1886 } 1887 1888 // Construct a an_clusters entry for every parent and child in the to-be-applied dependencies, 1889 // and an an_deps entry for each dependency to be applied. 1890 an_deps.reserve(clusterset.m_deps_to_add.size()); 1891 for (const auto& [par, chl] : clusterset.m_deps_to_add) { 1892 auto par_cluster = FindCluster(par, level); 1893 auto chl_cluster = FindCluster(chl, level); 1894 // Skip dependencies for which the parent or child transaction is removed. 1895 if (par_cluster == nullptr || chl_cluster == nullptr) continue; 1896 an_clusters.emplace_back(par_cluster, par_cluster->m_sequence); 1897 // Do not include a duplicate when parent and child are identical, as it'll be removed 1898 // below anyway. 1899 if (chl_cluster != par_cluster) an_clusters.emplace_back(chl_cluster, chl_cluster->m_sequence); 1900 // Add entry to an_deps, using the child sequence number. 1901 an_deps.emplace_back(std::pair{par, chl}, chl_cluster->m_sequence); 1902 } 1903 // Sort and deduplicate an_clusters, so we end up with a sorted list of all involved Clusters 1904 // to which dependencies apply, or which are oversized. 1905 std::sort(an_clusters.begin(), an_clusters.end(), [](auto& a, auto& b) noexcept { return a.second < b.second; }); 1906 an_clusters.erase(std::unique(an_clusters.begin(), an_clusters.end()), an_clusters.end()); 1907 // Sort an_deps by applying the same order to the involved child cluster. 1908 std::sort(an_deps.begin(), an_deps.end(), [&](auto& a, auto& b) noexcept { return a.second < b.second; }); 1909 1910 // Run the union-find algorithm to find partitions of the input Clusters which need to be 1911 // grouped together. See https://en.wikipedia.org/wiki/Disjoint-set_data_structure. 1912 { 1913 /** Each PartitionData entry contains information about a single input Cluster. */ 1914 struct PartitionData 1915 { 1916 /** The sequence number of the cluster this holds information for. */ 1917 uint64_t sequence; 1918 /** All PartitionData entries belonging to the same partition are organized in a tree. 1919 * Each element points to its parent, or to itself if it is the root. The root is then 1920 * a representative for the entire tree, and can be found by walking upwards from any 1921 * element. */ 1922 PartitionData* parent; 1923 /** (only if this is a root, so when parent == this) An upper bound on the height of 1924 * tree for this partition. */ 1925 unsigned rank; 1926 }; 1927 /** Information about each input Cluster. Sorted by Cluster::m_sequence. */ 1928 std::vector<PartitionData> partition_data; 1929 1930 /** Given a Cluster, find its corresponding PartitionData. */ 1931 auto locate_fn = [&](uint64_t sequence) noexcept -> PartitionData* { 1932 auto it = std::lower_bound(partition_data.begin(), partition_data.end(), sequence, 1933 [](auto& a, uint64_t seq) noexcept { return a.sequence < seq; }); 1934 Assume(it != partition_data.end()); 1935 Assume(it->sequence == sequence); 1936 return &*it; 1937 }; 1938 1939 /** Given a PartitionData, find the root of the tree it is in (its representative). */ 1940 static constexpr auto find_root_fn = [](PartitionData* data) noexcept -> PartitionData* { 1941 while (data->parent != data) { 1942 // Replace pointers to parents with pointers to grandparents. 1943 // See https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Finding_set_representatives. 1944 auto par = data->parent; 1945 data->parent = par->parent; 1946 data = par; 1947 } 1948 return data; 1949 }; 1950 1951 /** Given two PartitionDatas, union the partitions they are in, and return their 1952 * representative. */ 1953 static constexpr auto union_fn = [](PartitionData* arg1, PartitionData* arg2) noexcept { 1954 // Find the roots of the trees, and bail out if they are already equal (which would 1955 // mean they are in the same partition already). 1956 auto rep1 = find_root_fn(arg1); 1957 auto rep2 = find_root_fn(arg2); 1958 if (rep1 == rep2) return rep1; 1959 // Pick the lower-rank root to become a child of the higher-rank one. 1960 // See https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Union_by_rank. 1961 if (rep1->rank < rep2->rank) std::swap(rep1, rep2); 1962 rep2->parent = rep1; 1963 rep1->rank += (rep1->rank == rep2->rank); 1964 return rep1; 1965 }; 1966 1967 // Start by initializing every Cluster as its own singleton partition. 1968 partition_data.resize(an_clusters.size()); 1969 for (size_t i = 0; i < an_clusters.size(); ++i) { 1970 partition_data[i].sequence = an_clusters[i].first->m_sequence; 1971 partition_data[i].parent = &partition_data[i]; 1972 partition_data[i].rank = 0; 1973 } 1974 1975 // Run through all parent/child pairs in an_deps, and union the partitions their Clusters 1976 // are in. 1977 Cluster* last_chl_cluster{nullptr}; 1978 PartitionData* last_partition{nullptr}; 1979 for (const auto& [dep, _] : an_deps) { 1980 auto [par, chl] = dep; 1981 auto par_cluster = FindCluster(par, level); 1982 auto chl_cluster = FindCluster(chl, level); 1983 Assume(chl_cluster != nullptr && par_cluster != nullptr); 1984 // Nothing to do if parent and child are in the same Cluster. 1985 if (par_cluster == chl_cluster) continue; 1986 Assume(par != chl); 1987 if (chl_cluster == last_chl_cluster) { 1988 // If the child Clusters is the same as the previous iteration, union with the 1989 // tree they were in, avoiding the need for another lookup. Note that an_deps 1990 // is sorted by child Cluster, so batches with the same child are expected. 1991 last_partition = union_fn(locate_fn(par_cluster->m_sequence), last_partition); 1992 } else { 1993 last_chl_cluster = chl_cluster; 1994 last_partition = union_fn(locate_fn(par_cluster->m_sequence), locate_fn(chl_cluster->m_sequence)); 1995 } 1996 } 1997 1998 // Update the sequence numbers in an_clusters and an_deps to be those of the partition 1999 // representative. 2000 auto deps_it = an_deps.begin(); 2001 for (size_t i = 0; i < partition_data.size(); ++i) { 2002 auto& data = partition_data[i]; 2003 // Find the sequence of the representative of the partition Cluster i is in, and store 2004 // it with the Cluster. 2005 auto rep_seq = find_root_fn(&data)->sequence; 2006 an_clusters[i].second = rep_seq; 2007 // Find all dependencies whose child Cluster is Cluster i, and annotate them with rep. 2008 while (deps_it != an_deps.end()) { 2009 auto [par, chl] = deps_it->first; 2010 auto chl_cluster = FindCluster(chl, level); 2011 Assume(chl_cluster != nullptr); 2012 if (chl_cluster->m_sequence > data.sequence) break; 2013 deps_it->second = rep_seq; 2014 ++deps_it; 2015 } 2016 } 2017 } 2018 2019 // Sort both an_clusters and an_deps by sequence number of the representative of the 2020 // partition they are in, grouping all those applying to the same partition together. 2021 std::sort(an_deps.begin(), an_deps.end(), [](auto& a, auto& b) noexcept { return a.second < b.second; }); 2022 std::sort(an_clusters.begin(), an_clusters.end(), [](auto& a, auto& b) noexcept { return a.second < b.second; }); 2023 2024 // Translate the resulting cluster groups to the m_group_data structure, and the dependencies 2025 // back to m_deps_to_add. 2026 clusterset.m_group_data = GroupData{}; 2027 clusterset.m_group_data->m_group_clusters.reserve(an_clusters.size()); 2028 clusterset.m_deps_to_add.clear(); 2029 clusterset.m_deps_to_add.reserve(an_deps.size()); 2030 clusterset.m_oversized = false; 2031 auto an_deps_it = an_deps.begin(); 2032 auto an_clusters_it = an_clusters.begin(); 2033 while (an_clusters_it != an_clusters.end()) { 2034 // Process all clusters/dependencies belonging to the partition with representative rep. 2035 auto rep = an_clusters_it->second; 2036 // Create and initialize a new GroupData entry for the partition. 2037 auto& new_entry = clusterset.m_group_data->m_groups.emplace_back(); 2038 new_entry.m_cluster_offset = clusterset.m_group_data->m_group_clusters.size(); 2039 new_entry.m_cluster_count = 0; 2040 new_entry.m_deps_offset = clusterset.m_deps_to_add.size(); 2041 new_entry.m_deps_count = 0; 2042 uint32_t total_count{0}; 2043 uint64_t total_size{0}; 2044 // Add all its clusters to it (copying those from an_clusters to m_group_clusters). 2045 while (an_clusters_it != an_clusters.end() && an_clusters_it->second == rep) { 2046 clusterset.m_group_data->m_group_clusters.push_back(an_clusters_it->first); 2047 total_count += an_clusters_it->first->GetTxCount(); 2048 total_size += an_clusters_it->first->GetTotalTxSize(); 2049 ++an_clusters_it; 2050 ++new_entry.m_cluster_count; 2051 } 2052 // Add all its dependencies to it (copying those back from an_deps to m_deps_to_add). 2053 while (an_deps_it != an_deps.end() && an_deps_it->second == rep) { 2054 clusterset.m_deps_to_add.push_back(an_deps_it->first); 2055 ++an_deps_it; 2056 ++new_entry.m_deps_count; 2057 } 2058 // Detect oversizedness. 2059 if (total_count > m_max_cluster_count || total_size > m_max_cluster_size) { 2060 clusterset.m_oversized = true; 2061 } 2062 } 2063 Assume(an_deps_it == an_deps.end()); 2064 Assume(an_clusters_it == an_clusters.end()); 2065 Compact(); 2066 } 2067 2068 void TxGraphImpl::Merge(std::span<Cluster*> to_merge, int level) noexcept 2069 { 2070 Assume(!to_merge.empty()); 2071 // Nothing to do if a group consists of just a single Cluster. 2072 if (to_merge.size() == 1) return; 2073 2074 // Move the largest Cluster to the front of to_merge. As all transactions in other to-be-merged 2075 // Clusters will be moved to that one, putting the largest one first minimizes the number of 2076 // moves. 2077 size_t max_size_pos{0}; 2078 DepGraphIndex max_size = to_merge[max_size_pos]->GetTxCount(); 2079 GetClusterSet(level).m_cluster_usage -= to_merge[max_size_pos]->TotalMemoryUsage(); 2080 DepGraphIndex total_size = max_size; 2081 for (size_t i = 1; i < to_merge.size(); ++i) { 2082 GetClusterSet(level).m_cluster_usage -= to_merge[i]->TotalMemoryUsage(); 2083 DepGraphIndex size = to_merge[i]->GetTxCount(); 2084 total_size += size; 2085 if (size > max_size) { 2086 max_size_pos = i; 2087 max_size = size; 2088 } 2089 } 2090 if (max_size_pos != 0) std::swap(to_merge[0], to_merge[max_size_pos]); 2091 2092 size_t start_idx = 1; 2093 Cluster* into_cluster = to_merge[0]; 2094 if (total_size > into_cluster->GetMaxTxCount()) { 2095 // The into_merge cluster is too small to fit all transactions being merged. Construct a 2096 // a new Cluster using an implementation that matches the total size, and merge everything 2097 // in there. 2098 auto new_cluster = CreateEmptyCluster(total_size); 2099 into_cluster = new_cluster.get(); 2100 InsertCluster(level, std::move(new_cluster), QualityLevel::OPTIMAL); 2101 start_idx = 0; 2102 } 2103 2104 // Merge all further Clusters in the group into the result (first one, or new one), and delete 2105 // them. 2106 for (size_t i = start_idx; i < to_merge.size(); ++i) { 2107 into_cluster->Merge(*this, level, *to_merge[i]); 2108 DeleteCluster(*to_merge[i], level); 2109 } 2110 into_cluster->Compact(); 2111 GetClusterSet(level).m_cluster_usage += into_cluster->TotalMemoryUsage(); 2112 } 2113 2114 void TxGraphImpl::ApplyDependencies(int level) noexcept 2115 { 2116 auto& clusterset = GetClusterSet(level); 2117 // Do not bother computing groups if we already know the result will be oversized. 2118 if (clusterset.m_oversized == true) return; 2119 // Compute the groups of to-be-merged Clusters (which also applies all removals, and splits). 2120 GroupClusters(level); 2121 Assume(clusterset.m_group_data.has_value()); 2122 // Nothing to do if there are no dependencies to be added. 2123 if (clusterset.m_deps_to_add.empty()) return; 2124 // Dependencies cannot be applied if it would result in oversized clusters. 2125 if (clusterset.m_oversized == true) return; 2126 2127 // For each group of to-be-merged Clusters. 2128 for (const auto& group_entry : clusterset.m_group_data->m_groups) { 2129 auto cluster_span = std::span{clusterset.m_group_data->m_group_clusters} 2130 .subspan(group_entry.m_cluster_offset, group_entry.m_cluster_count); 2131 // Pull in all the Clusters that contain dependencies. 2132 if (level == 1) { 2133 for (Cluster*& cluster : cluster_span) { 2134 cluster = PullIn(cluster, cluster->GetLevel(*this)); 2135 } 2136 } 2137 // Invoke Merge() to merge them into a single Cluster. 2138 Merge(cluster_span, level); 2139 // Actually apply all to-be-added dependencies (all parents and children from this grouping 2140 // belong to the same Cluster at this point because of the merging above). 2141 auto deps_span = std::span{clusterset.m_deps_to_add} 2142 .subspan(group_entry.m_deps_offset, group_entry.m_deps_count); 2143 Assume(!deps_span.empty()); 2144 const auto& loc = m_entries[deps_span[0].second].m_locator[level]; 2145 Assume(loc.IsPresent()); 2146 loc.cluster->ApplyDependencies(*this, level, deps_span); 2147 } 2148 2149 // Wipe the list of to-be-added dependencies now that they are applied. 2150 clusterset.m_deps_to_add.clear(); 2151 Compact(); 2152 // Also no further Cluster mergings are needed (note that we clear, but don't set to 2153 // std::nullopt, as that would imply the groupings are unknown). 2154 clusterset.m_group_data = GroupData{}; 2155 } 2156 2157 std::pair<uint64_t, bool> GenericClusterImpl::Relinearize(TxGraphImpl& graph, int level, uint64_t max_cost) noexcept 2158 { 2159 // We can only relinearize Clusters that do not need splitting. 2160 Assume(!NeedsSplitting()); 2161 // No work is required for Clusters which are already optimally linearized. 2162 if (IsOptimal()) return {0, false}; 2163 // Invoke the actual linearization algorithm (passing in the existing one). 2164 uint64_t rng_seed = graph.m_rng.rand64(); 2165 const auto fallback_order = [&](DepGraphIndex a, DepGraphIndex b) noexcept { 2166 const auto ref_a = graph.m_entries[m_mapping[a]].m_ref; 2167 const auto ref_b = graph.m_entries[m_mapping[b]].m_ref; 2168 return graph.m_fallback_order(*ref_a, *ref_b); 2169 }; 2170 auto [linearization, optimal, cost] = Linearize( 2171 /*depgraph=*/m_depgraph, 2172 /*max_cost=*/max_cost, 2173 /*rng_seed=*/rng_seed, 2174 /*fallback_order=*/fallback_order, 2175 /*old_linearization=*/m_linearization, 2176 /*is_topological=*/IsTopological()); 2177 // Postlinearize to improve the linearization (if optimal, only the sub-chunk order). 2178 // This also guarantees that all chunks are connected (even when non-optimal). 2179 PostLinearize(m_depgraph, linearization); 2180 // Update the linearization. 2181 m_linearization = std::move(linearization); 2182 // Update the Cluster's quality. 2183 bool improved = false; 2184 if (optimal) { 2185 graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::OPTIMAL); 2186 improved = true; 2187 } else if (max_cost >= graph.m_acceptable_cost && !IsAcceptable()) { 2188 graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::ACCEPTABLE); 2189 improved = true; 2190 } else if (!IsTopological()) { 2191 graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::NEEDS_RELINEARIZE); 2192 improved = true; 2193 } 2194 // Update the Entry objects. 2195 Updated(graph, /*level=*/level, /*rename=*/false); 2196 return {cost, improved}; 2197 } 2198 2199 std::pair<uint64_t, bool> SingletonClusterImpl::Relinearize(TxGraphImpl& graph, int level, uint64_t max_cost) noexcept 2200 { 2201 // All singletons are optimal, oversized, or need splitting. Each of these precludes 2202 // Relinearize from being called. 2203 assert(false); 2204 return {0, false}; 2205 } 2206 2207 void TxGraphImpl::MakeAcceptable(Cluster& cluster, int level) noexcept 2208 { 2209 // Relinearize the Cluster if needed. 2210 if (!cluster.NeedsSplitting() && !cluster.IsAcceptable() && !cluster.IsOversized()) { 2211 cluster.Relinearize(*this, level, m_acceptable_cost); 2212 } 2213 } 2214 2215 void TxGraphImpl::MakeAllAcceptable(int level) noexcept 2216 { 2217 ApplyDependencies(level); 2218 auto& clusterset = GetClusterSet(level); 2219 if (clusterset.m_oversized == true) return; 2220 for (auto quality : {QualityLevel::NEEDS_FIX, QualityLevel::NEEDS_RELINEARIZE}) { 2221 auto& queue = clusterset.m_clusters[int(quality)]; 2222 while (!queue.empty()) { 2223 MakeAcceptable(*queue.back().get(), level); 2224 } 2225 } 2226 } 2227 2228 GenericClusterImpl::GenericClusterImpl(uint64_t sequence) noexcept : Cluster{sequence} {} 2229 2230 void TxGraphImpl::AddTransaction(Ref& arg, const FeePerWeight& feerate) noexcept 2231 { 2232 Assume(m_main_chunkindex_observers == 0 || GetTopLevel() != 0); 2233 Assume(feerate.size > 0); 2234 Assume(GetRefGraph(arg) == nullptr); 2235 // Construct a new Entry, and link it with the Ref. 2236 auto idx = m_entries.size(); 2237 m_entries.emplace_back(); 2238 auto& entry = m_entries.back(); 2239 entry.m_main_chunkindex_iterator = m_main_chunkindex.end(); 2240 entry.m_ref = &arg; 2241 GetRefGraph(arg) = this; 2242 GetRefIndex(arg) = idx; 2243 // Construct a new singleton Cluster (which is necessarily optimally linearized). 2244 bool oversized = uint64_t(feerate.size) > m_max_cluster_size; 2245 auto cluster = CreateEmptyCluster(1); 2246 cluster->AppendTransaction(idx, feerate); 2247 auto cluster_ptr = cluster.get(); 2248 int level = GetTopLevel(); 2249 auto& clusterset = GetClusterSet(level); 2250 InsertCluster(level, std::move(cluster), oversized ? QualityLevel::OVERSIZED_SINGLETON : QualityLevel::OPTIMAL); 2251 cluster_ptr->Updated(*this, /*level=*/level, /*rename=*/false); 2252 clusterset.m_cluster_usage += cluster_ptr->TotalMemoryUsage(); 2253 ++clusterset.m_txcount; 2254 // Deal with individually oversized transactions. 2255 if (oversized) { 2256 ++clusterset.m_txcount_oversized; 2257 clusterset.m_oversized = true; 2258 clusterset.m_group_data = std::nullopt; 2259 } 2260 } 2261 2262 void TxGraphImpl::RemoveTransaction(const Ref& arg) noexcept 2263 { 2264 // Don't do anything if the Ref is empty (which may be indicative of the transaction already 2265 // having been removed). 2266 if (GetRefGraph(arg) == nullptr) return; 2267 Assume(GetRefGraph(arg) == this); 2268 Assume(m_main_chunkindex_observers == 0 || GetTopLevel() != 0); 2269 // Find the Cluster the transaction is in, and stop if it isn't in any. 2270 int level = GetTopLevel(); 2271 auto cluster = FindCluster(GetRefIndex(arg), level); 2272 if (cluster == nullptr) return; 2273 // Remember that the transaction is to be removed. 2274 auto& clusterset = GetClusterSet(level); 2275 clusterset.m_to_remove.push_back(GetRefIndex(arg)); 2276 // Wipe m_group_data (as it will need to be recomputed). 2277 clusterset.m_group_data.reset(); 2278 if (clusterset.m_oversized == true) clusterset.m_oversized = std::nullopt; 2279 } 2280 2281 void TxGraphImpl::AddDependency(const Ref& parent, const Ref& child) noexcept 2282 { 2283 // Don't do anything if either Ref is empty (which may be indicative of it having already been 2284 // removed). 2285 if (GetRefGraph(parent) == nullptr || GetRefGraph(child) == nullptr) return; 2286 Assume(GetRefGraph(parent) == this && GetRefGraph(child) == this); 2287 Assume(m_main_chunkindex_observers == 0 || GetTopLevel() != 0); 2288 // Don't do anything if this is a dependency on self. 2289 if (GetRefIndex(parent) == GetRefIndex(child)) return; 2290 // Find the Cluster the parent and child transaction are in, and stop if either appears to be 2291 // already removed. 2292 int level = GetTopLevel(); 2293 auto par_cluster = FindCluster(GetRefIndex(parent), level); 2294 if (par_cluster == nullptr) return; 2295 auto chl_cluster = FindCluster(GetRefIndex(child), level); 2296 if (chl_cluster == nullptr) return; 2297 // Remember that this dependency is to be applied. 2298 auto& clusterset = GetClusterSet(level); 2299 clusterset.m_deps_to_add.emplace_back(GetRefIndex(parent), GetRefIndex(child)); 2300 // Wipe m_group_data (as it will need to be recomputed). 2301 clusterset.m_group_data.reset(); 2302 if (clusterset.m_oversized == false) clusterset.m_oversized = std::nullopt; 2303 } 2304 2305 bool TxGraphImpl::Exists(const Ref& arg, Level level_select) noexcept 2306 { 2307 if (GetRefGraph(arg) == nullptr) return false; 2308 Assume(GetRefGraph(arg) == this); 2309 size_t level = GetSpecifiedLevel(level_select); 2310 // Make sure the transaction isn't scheduled for removal. 2311 ApplyRemovals(level); 2312 auto cluster = FindCluster(GetRefIndex(arg), level); 2313 return cluster != nullptr; 2314 } 2315 2316 void GenericClusterImpl::GetAncestorRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept 2317 { 2318 /** The union of all ancestors to be returned. */ 2319 SetType ancestors_union; 2320 // Process elements from the front of args, as long as they apply. 2321 while (!args.empty()) { 2322 if (args.front().first != this) break; 2323 ancestors_union |= m_depgraph.Ancestors(args.front().second); 2324 args = args.subspan(1); 2325 } 2326 Assume(ancestors_union.Any()); 2327 // Translate all ancestors (in arbitrary order) to Refs (if they have any), and return them. 2328 for (auto idx : ancestors_union) { 2329 const auto& entry = graph.m_entries[m_mapping[idx]]; 2330 Assume(entry.m_ref != nullptr); 2331 output.push_back(entry.m_ref); 2332 } 2333 } 2334 2335 void SingletonClusterImpl::GetAncestorRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept 2336 { 2337 Assume(GetTxCount()); 2338 while (!args.empty()) { 2339 if (args.front().first != this) break; 2340 args = args.subspan(1); 2341 } 2342 const auto& entry = graph.m_entries[m_graph_index]; 2343 Assume(entry.m_ref != nullptr); 2344 output.push_back(entry.m_ref); 2345 } 2346 2347 void GenericClusterImpl::GetDescendantRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept 2348 { 2349 /** The union of all descendants to be returned. */ 2350 SetType descendants_union; 2351 // Process elements from the front of args, as long as they apply. 2352 while (!args.empty()) { 2353 if (args.front().first != this) break; 2354 descendants_union |= m_depgraph.Descendants(args.front().second); 2355 args = args.subspan(1); 2356 } 2357 Assume(descendants_union.Any()); 2358 // Translate all descendants (in arbitrary order) to Refs (if they have any), and return them. 2359 for (auto idx : descendants_union) { 2360 const auto& entry = graph.m_entries[m_mapping[idx]]; 2361 Assume(entry.m_ref != nullptr); 2362 output.push_back(entry.m_ref); 2363 } 2364 } 2365 2366 void SingletonClusterImpl::GetDescendantRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept 2367 { 2368 // In a singleton cluster, the ancestors or descendants are always just the entire cluster. 2369 GetAncestorRefs(graph, args, output); 2370 } 2371 2372 bool GenericClusterImpl::GetClusterRefs(TxGraphImpl& graph, std::span<TxGraph::Ref*> range, LinearizationIndex start_pos) noexcept 2373 { 2374 // Translate the transactions in the Cluster (in linearization order, starting at start_pos in 2375 // the linearization) to Refs, and fill them in range. 2376 for (auto& ref : range) { 2377 Assume(start_pos < m_linearization.size()); 2378 const auto& entry = graph.m_entries[m_mapping[m_linearization[start_pos++]]]; 2379 Assume(entry.m_ref != nullptr); 2380 ref = entry.m_ref; 2381 } 2382 // Return whether start_pos has advanced to the end of the Cluster. 2383 return start_pos == m_linearization.size(); 2384 } 2385 2386 bool SingletonClusterImpl::GetClusterRefs(TxGraphImpl& graph, std::span<TxGraph::Ref*> range, LinearizationIndex start_pos) noexcept 2387 { 2388 Assume(!range.empty()); 2389 Assume(GetTxCount()); 2390 Assume(start_pos == 0); 2391 const auto& entry = graph.m_entries[m_graph_index]; 2392 Assume(entry.m_ref != nullptr); 2393 range[0] = entry.m_ref; 2394 return true; 2395 } 2396 2397 FeePerWeight GenericClusterImpl::GetIndividualFeerate(DepGraphIndex idx) noexcept 2398 { 2399 return FeePerWeight::FromFeeFrac(m_depgraph.FeeRate(idx)); 2400 } 2401 2402 FeePerWeight SingletonClusterImpl::GetIndividualFeerate(DepGraphIndex idx) noexcept 2403 { 2404 Assume(GetTxCount()); 2405 Assume(idx == 0); 2406 return m_feerate; 2407 } 2408 2409 void GenericClusterImpl::MakeStagingTransactionsMissing(TxGraphImpl& graph) noexcept 2410 { 2411 // Mark all transactions of a Cluster missing, needed when aborting staging, so that the 2412 // corresponding Locators don't retain references into aborted Clusters. 2413 for (auto ci : m_linearization) { 2414 GraphIndex idx = m_mapping[ci]; 2415 auto& entry = graph.m_entries[idx]; 2416 entry.m_locator[1].SetMissing(); 2417 } 2418 } 2419 2420 void SingletonClusterImpl::MakeStagingTransactionsMissing(TxGraphImpl& graph) noexcept 2421 { 2422 if (GetTxCount()) { 2423 auto& entry = graph.m_entries[m_graph_index]; 2424 entry.m_locator[1].SetMissing(); 2425 } 2426 } 2427 2428 std::vector<TxGraph::Ref*> TxGraphImpl::GetAncestors(const Ref& arg, Level level_select) noexcept 2429 { 2430 // Return the empty vector if the Ref is empty. 2431 if (GetRefGraph(arg) == nullptr) return {}; 2432 Assume(GetRefGraph(arg) == this); 2433 // Apply all removals and dependencies, as the result might be incorrect otherwise. 2434 size_t level = GetSpecifiedLevel(level_select); 2435 ApplyDependencies(level); 2436 // Ancestry cannot be known if unapplied dependencies remain. 2437 Assume(GetClusterSet(level).m_deps_to_add.empty()); 2438 // Find the Cluster the argument is in, and return the empty vector if it isn't in any. 2439 auto [cluster, cluster_level] = FindClusterAndLevel(GetRefIndex(arg), level); 2440 if (cluster == nullptr) return {}; 2441 // Dispatch to the Cluster. 2442 std::pair<Cluster*, DepGraphIndex> match = {cluster, m_entries[GetRefIndex(arg)].m_locator[cluster_level].index}; 2443 auto matches = std::span(&match, 1); 2444 std::vector<TxGraph::Ref*> ret; 2445 cluster->GetAncestorRefs(*this, matches, ret); 2446 return ret; 2447 } 2448 2449 std::vector<TxGraph::Ref*> TxGraphImpl::GetDescendants(const Ref& arg, Level level_select) noexcept 2450 { 2451 // Return the empty vector if the Ref is empty. 2452 if (GetRefGraph(arg) == nullptr) return {}; 2453 Assume(GetRefGraph(arg) == this); 2454 // Apply all removals and dependencies, as the result might be incorrect otherwise. 2455 size_t level = GetSpecifiedLevel(level_select); 2456 ApplyDependencies(level); 2457 // Ancestry cannot be known if unapplied dependencies remain. 2458 Assume(GetClusterSet(level).m_deps_to_add.empty()); 2459 // Find the Cluster the argument is in, and return the empty vector if it isn't in any. 2460 auto [cluster, cluster_level] = FindClusterAndLevel(GetRefIndex(arg), level); 2461 if (cluster == nullptr) return {}; 2462 // Dispatch to the Cluster. 2463 std::pair<Cluster*, DepGraphIndex> match = {cluster, m_entries[GetRefIndex(arg)].m_locator[cluster_level].index}; 2464 auto matches = std::span(&match, 1); 2465 std::vector<TxGraph::Ref*> ret; 2466 cluster->GetDescendantRefs(*this, matches, ret); 2467 return ret; 2468 } 2469 2470 std::vector<TxGraph::Ref*> TxGraphImpl::GetAncestorsUnion(std::span<const Ref* const> args, Level level_select) noexcept 2471 { 2472 // Apply all dependencies, as the result might be incorrect otherwise. 2473 size_t level = GetSpecifiedLevel(level_select); 2474 ApplyDependencies(level); 2475 // Ancestry cannot be known if unapplied dependencies remain. 2476 Assume(GetClusterSet(level).m_deps_to_add.empty()); 2477 2478 // Translate args to matches. 2479 std::vector<std::pair<Cluster*, DepGraphIndex>> matches; 2480 matches.reserve(args.size()); 2481 for (auto arg : args) { 2482 Assume(arg); 2483 // Skip empty Refs. 2484 if (GetRefGraph(*arg) == nullptr) continue; 2485 Assume(GetRefGraph(*arg) == this); 2486 // Find the Cluster the argument is in, and skip if none is found. 2487 auto [cluster, cluster_level] = FindClusterAndLevel(GetRefIndex(*arg), level); 2488 if (cluster == nullptr) continue; 2489 // Append to matches. 2490 matches.emplace_back(cluster, m_entries[GetRefIndex(*arg)].m_locator[cluster_level].index); 2491 } 2492 // Group by Cluster. 2493 std::sort(matches.begin(), matches.end(), [](auto& a, auto& b) noexcept { return CompareClusters(a.first, b.first) < 0; }); 2494 // Dispatch to the Clusters. 2495 std::span match_span(matches); 2496 std::vector<TxGraph::Ref*> ret; 2497 while (!match_span.empty()) { 2498 match_span.front().first->GetAncestorRefs(*this, match_span, ret); 2499 } 2500 return ret; 2501 } 2502 2503 std::vector<TxGraph::Ref*> TxGraphImpl::GetDescendantsUnion(std::span<const Ref* const> args, Level level_select) noexcept 2504 { 2505 // Apply all dependencies, as the result might be incorrect otherwise. 2506 size_t level = GetSpecifiedLevel(level_select); 2507 ApplyDependencies(level); 2508 // Ancestry cannot be known if unapplied dependencies remain. 2509 Assume(GetClusterSet(level).m_deps_to_add.empty()); 2510 2511 // Translate args to matches. 2512 std::vector<std::pair<Cluster*, DepGraphIndex>> matches; 2513 matches.reserve(args.size()); 2514 for (auto arg : args) { 2515 Assume(arg); 2516 // Skip empty Refs. 2517 if (GetRefGraph(*arg) == nullptr) continue; 2518 Assume(GetRefGraph(*arg) == this); 2519 // Find the Cluster the argument is in, and skip if none is found. 2520 auto [cluster, cluster_level] = FindClusterAndLevel(GetRefIndex(*arg), level); 2521 if (cluster == nullptr) continue; 2522 // Append to matches. 2523 matches.emplace_back(cluster, m_entries[GetRefIndex(*arg)].m_locator[cluster_level].index); 2524 } 2525 // Group by Cluster. 2526 std::sort(matches.begin(), matches.end(), [](auto& a, auto& b) noexcept { return CompareClusters(a.first, b.first) < 0; }); 2527 // Dispatch to the Clusters. 2528 std::span match_span(matches); 2529 std::vector<TxGraph::Ref*> ret; 2530 while (!match_span.empty()) { 2531 match_span.front().first->GetDescendantRefs(*this, match_span, ret); 2532 } 2533 return ret; 2534 } 2535 2536 std::vector<TxGraph::Ref*> TxGraphImpl::GetCluster(const Ref& arg, Level level_select) noexcept 2537 { 2538 // Return the empty vector if the Ref is empty (which may be indicative of the transaction 2539 // having been removed already. 2540 if (GetRefGraph(arg) == nullptr) return {}; 2541 Assume(GetRefGraph(arg) == this); 2542 // Apply all removals and dependencies, as the result might be incorrect otherwise. 2543 size_t level = GetSpecifiedLevel(level_select); 2544 ApplyDependencies(level); 2545 // Cluster linearization cannot be known if unapplied dependencies remain. 2546 Assume(GetClusterSet(level).m_deps_to_add.empty()); 2547 // Find the Cluster the argument is in, and return the empty vector if it isn't in any. 2548 auto [cluster, cluster_level] = FindClusterAndLevel(GetRefIndex(arg), level); 2549 if (cluster == nullptr) return {}; 2550 // Make sure the Cluster has an acceptable quality level, and then dispatch to it. 2551 MakeAcceptable(*cluster, cluster_level); 2552 std::vector<TxGraph::Ref*> ret(cluster->GetTxCount()); 2553 cluster->GetClusterRefs(*this, ret, 0); 2554 return ret; 2555 } 2556 2557 TxGraph::GraphIndex TxGraphImpl::GetTransactionCount(Level level_select) noexcept 2558 { 2559 size_t level = GetSpecifiedLevel(level_select); 2560 ApplyRemovals(level); 2561 return GetClusterSet(level).m_txcount; 2562 } 2563 2564 FeePerWeight TxGraphImpl::GetIndividualFeerate(const Ref& arg) noexcept 2565 { 2566 // Return the empty FeePerWeight if the passed Ref is empty. 2567 if (GetRefGraph(arg) == nullptr) return {}; 2568 Assume(GetRefGraph(arg) == this); 2569 // Find the cluster the argument is in (the level does not matter as individual feerates will 2570 // be identical if it occurs in both), and return the empty FeePerWeight if it isn't in any. 2571 Cluster* cluster{nullptr}; 2572 int level; 2573 for (level = 0; level <= GetTopLevel(); ++level) { 2574 // Apply removals, so that we can correctly report FeePerWeight{} for non-existing 2575 // transactions. 2576 ApplyRemovals(level); 2577 if (m_entries[GetRefIndex(arg)].m_locator[level].IsPresent()) { 2578 cluster = m_entries[GetRefIndex(arg)].m_locator[level].cluster; 2579 break; 2580 } 2581 } 2582 if (cluster == nullptr) return {}; 2583 // Dispatch to the Cluster. 2584 return cluster->GetIndividualFeerate(m_entries[GetRefIndex(arg)].m_locator[level].index); 2585 } 2586 2587 FeePerWeight TxGraphImpl::GetMainChunkFeerate(const Ref& arg) noexcept 2588 { 2589 // Return the empty FeePerWeight if the passed Ref is empty. 2590 if (GetRefGraph(arg) == nullptr) return {}; 2591 Assume(GetRefGraph(arg) == this); 2592 // Apply all removals and dependencies, as the result might be inaccurate otherwise. 2593 ApplyDependencies(/*level=*/0); 2594 // Chunk feerates cannot be accurately known if unapplied dependencies remain. 2595 Assume(m_main_clusterset.m_deps_to_add.empty()); 2596 // Find the cluster the argument is in, and return the empty FeePerWeight if it isn't in any. 2597 auto [cluster, cluster_level] = FindClusterAndLevel(GetRefIndex(arg), /*level=*/0); 2598 if (cluster == nullptr) return {}; 2599 // Make sure the Cluster has an acceptable quality level, and then return the transaction's 2600 // chunk feerate. 2601 MakeAcceptable(*cluster, cluster_level); 2602 const auto& entry = m_entries[GetRefIndex(arg)]; 2603 return entry.m_main_chunk_feerate; 2604 } 2605 2606 bool TxGraphImpl::IsOversized(Level level_select) noexcept 2607 { 2608 size_t level = GetSpecifiedLevel(level_select); 2609 auto& clusterset = GetClusterSet(level); 2610 if (clusterset.m_oversized.has_value()) { 2611 // Return cached value if known. 2612 return *clusterset.m_oversized; 2613 } 2614 ApplyRemovals(level); 2615 if (clusterset.m_txcount_oversized > 0) { 2616 clusterset.m_oversized = true; 2617 } else { 2618 // Find which Clusters will need to be merged together, as that is where the oversize 2619 // property is assessed. 2620 GroupClusters(level); 2621 } 2622 Assume(clusterset.m_oversized.has_value()); 2623 return *clusterset.m_oversized; 2624 } 2625 2626 void TxGraphImpl::StartStaging() noexcept 2627 { 2628 // Staging cannot already exist. 2629 Assume(!m_staging_clusterset.has_value()); 2630 // Apply all remaining dependencies in main before creating a staging graph. Once staging 2631 // exists, we cannot merge Clusters anymore (because of interference with Clusters being 2632 // pulled into staging), so to make sure all inspectors are available (if not oversized), do 2633 // all merging work now. Call SplitAll() first, so that even if ApplyDependencies does not do 2634 // any thing due to knowing the result is oversized, splitting is still performed. 2635 SplitAll(0); 2636 ApplyDependencies(0); 2637 // Construct the staging ClusterSet. 2638 m_staging_clusterset.emplace(); 2639 // Copy statistics, precomputed data, and to-be-applied dependencies (only if oversized) to 2640 // the new graph. To-be-applied removals will always be empty at this point. 2641 m_staging_clusterset->m_txcount = m_main_clusterset.m_txcount; 2642 m_staging_clusterset->m_txcount_oversized = m_main_clusterset.m_txcount_oversized; 2643 m_staging_clusterset->m_deps_to_add = m_main_clusterset.m_deps_to_add; 2644 m_staging_clusterset->m_group_data = m_main_clusterset.m_group_data; 2645 m_staging_clusterset->m_oversized = m_main_clusterset.m_oversized; 2646 Assume(m_staging_clusterset->m_oversized.has_value()); 2647 m_staging_clusterset->m_cluster_usage = 0; 2648 } 2649 2650 void TxGraphImpl::AbortStaging() noexcept 2651 { 2652 // Staging must exist. 2653 Assume(m_staging_clusterset.has_value()); 2654 // Mark all removed transactions as Missing (so the staging locator for these transactions 2655 // can be reused if another staging is created). 2656 for (auto idx : m_staging_clusterset->m_removed) { 2657 m_entries[idx].m_locator[1].SetMissing(); 2658 } 2659 // Do the same with the non-removed transactions in staging Clusters. 2660 for (int quality = 0; quality < int(QualityLevel::NONE); ++quality) { 2661 for (auto& cluster : m_staging_clusterset->m_clusters[quality]) { 2662 cluster->MakeStagingTransactionsMissing(*this); 2663 } 2664 } 2665 // Destroy the staging ClusterSet. 2666 m_staging_clusterset.reset(); 2667 Compact(); 2668 if (!m_main_clusterset.m_group_data.has_value()) { 2669 // In case m_oversized in main was kept after a Ref destruction while staging exists, we 2670 // need to re-evaluate m_oversized now. 2671 if (m_main_clusterset.m_to_remove.empty() && m_main_clusterset.m_txcount_oversized > 0) { 2672 // It is possible that a Ref destruction caused a removal in main while staging existed. 2673 // In this case, m_txcount_oversized may be inaccurate. 2674 m_main_clusterset.m_oversized = true; 2675 } else { 2676 m_main_clusterset.m_oversized = std::nullopt; 2677 } 2678 } 2679 } 2680 2681 void TxGraphImpl::CommitStaging() noexcept 2682 { 2683 // Staging must exist. 2684 Assume(m_staging_clusterset.has_value()); 2685 Assume(m_main_chunkindex_observers == 0); 2686 // Get rid of removed transactions in staging before moving to main, so they do not need to be 2687 // added to the chunk index there. Doing so is impossible if they were unlinked, and thus have 2688 // no Ref anymore to pass to the fallback comparator. 2689 ApplyRemovals(/*up_to_level=*/1); 2690 // Delete all conflicting Clusters in main, to make place for moving the staging ones 2691 // there. All of these have been copied to staging in PullIn(). 2692 auto conflicts = GetConflicts(); 2693 for (Cluster* conflict : conflicts) { 2694 conflict->Clear(*this, /*level=*/0); 2695 DeleteCluster(*conflict, /*level=*/0); 2696 } 2697 // Mark the removed transactions as Missing (so the staging locator for these transactions 2698 // can be reused if another staging is created). 2699 for (auto idx : m_staging_clusterset->m_removed) { 2700 m_entries[idx].m_locator[1].SetMissing(); 2701 } 2702 // Then move all Clusters in staging to main. 2703 for (int quality = 0; quality < int(QualityLevel::NONE); ++quality) { 2704 auto& stage_sets = m_staging_clusterset->m_clusters[quality]; 2705 while (!stage_sets.empty()) { 2706 stage_sets.back()->MoveToMain(*this); 2707 } 2708 } 2709 // Move all statistics, precomputed data, and to-be-applied removals and dependencies. 2710 m_main_clusterset.m_deps_to_add = std::move(m_staging_clusterset->m_deps_to_add); 2711 m_main_clusterset.m_to_remove = std::move(m_staging_clusterset->m_to_remove); 2712 m_main_clusterset.m_group_data = std::move(m_staging_clusterset->m_group_data); 2713 m_main_clusterset.m_oversized = std::move(m_staging_clusterset->m_oversized); 2714 m_main_clusterset.m_txcount = std::move(m_staging_clusterset->m_txcount); 2715 m_main_clusterset.m_txcount_oversized = std::move(m_staging_clusterset->m_txcount_oversized); 2716 // Delete the old staging graph, after all its information was moved to main. 2717 m_staging_clusterset.reset(); 2718 Compact(); 2719 } 2720 2721 void GenericClusterImpl::SetFee(TxGraphImpl& graph, int level, DepGraphIndex idx, int64_t fee) noexcept 2722 { 2723 // Make sure the specified DepGraphIndex exists in this Cluster. 2724 Assume(m_depgraph.Positions()[idx]); 2725 // Bail out if the fee isn't actually being changed. 2726 if (m_depgraph.FeeRate(idx).fee == fee) return; 2727 // Update the fee, remember that relinearization will be necessary, and update the Entries 2728 // in the same Cluster. 2729 m_depgraph.FeeRate(idx).fee = fee; 2730 if (m_quality == QualityLevel::OVERSIZED_SINGLETON) { 2731 // Nothing to do. 2732 } else if (IsAcceptable()) { 2733 graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::NEEDS_RELINEARIZE); 2734 } 2735 Updated(graph, /*level=*/level, /*rename=*/false); 2736 } 2737 2738 void SingletonClusterImpl::SetFee(TxGraphImpl& graph, int level, DepGraphIndex idx, int64_t fee) noexcept 2739 { 2740 Assume(GetTxCount()); 2741 Assume(idx == 0); 2742 m_feerate.fee = fee; 2743 Updated(graph, /*level=*/level, /*rename=*/false); 2744 } 2745 2746 void TxGraphImpl::SetTransactionFee(const Ref& ref, int64_t fee) noexcept 2747 { 2748 // Don't do anything if the passed Ref is empty. 2749 if (GetRefGraph(ref) == nullptr) return; 2750 Assume(GetRefGraph(ref) == this); 2751 Assume(m_main_chunkindex_observers == 0); 2752 // Find the entry, its locator, and inform its Cluster about the new feerate, if any. 2753 auto& entry = m_entries[GetRefIndex(ref)]; 2754 for (int level = 0; level < MAX_LEVELS; ++level) { 2755 auto& locator = entry.m_locator[level]; 2756 if (locator.IsPresent()) { 2757 locator.cluster->SetFee(*this, level, locator.index, fee); 2758 } 2759 } 2760 } 2761 2762 std::strong_ordering TxGraphImpl::CompareMainOrder(const Ref& a, const Ref& b) noexcept 2763 { 2764 // The references must not be empty. 2765 Assume(GetRefGraph(a) == this); 2766 Assume(GetRefGraph(b) == this); 2767 // Apply dependencies in main. 2768 ApplyDependencies(0); 2769 Assume(m_main_clusterset.m_deps_to_add.empty()); 2770 // Make both involved Clusters acceptable, so chunk feerates are relevant. 2771 const auto& entry_a = m_entries[GetRefIndex(a)]; 2772 const auto& entry_b = m_entries[GetRefIndex(b)]; 2773 const auto& locator_a = entry_a.m_locator[0]; 2774 const auto& locator_b = entry_b.m_locator[0]; 2775 Assume(locator_a.IsPresent()); 2776 Assume(locator_b.IsPresent()); 2777 MakeAcceptable(*locator_a.cluster, /*level=*/0); 2778 MakeAcceptable(*locator_b.cluster, /*level=*/0); 2779 // Invoke comparison logic. 2780 return CompareMainTransactions(GetRefIndex(a), GetRefIndex(b)); 2781 } 2782 2783 TxGraph::GraphIndex TxGraphImpl::CountDistinctClusters(std::span<const Ref* const> refs, Level level_select) noexcept 2784 { 2785 size_t level = GetSpecifiedLevel(level_select); 2786 ApplyDependencies(level); 2787 auto& clusterset = GetClusterSet(level); 2788 Assume(clusterset.m_deps_to_add.empty()); 2789 // Build a vector of Clusters that the specified Refs occur in. 2790 std::vector<Cluster*> clusters; 2791 clusters.reserve(refs.size()); 2792 for (const Ref* ref : refs) { 2793 Assume(ref); 2794 if (GetRefGraph(*ref) == nullptr) continue; 2795 Assume(GetRefGraph(*ref) == this); 2796 auto cluster = FindCluster(GetRefIndex(*ref), level); 2797 if (cluster != nullptr) clusters.push_back(cluster); 2798 } 2799 // Count the number of distinct elements in clusters. 2800 std::sort(clusters.begin(), clusters.end(), [](Cluster* a, Cluster* b) noexcept { return CompareClusters(a, b) < 0; }); 2801 Cluster* last{nullptr}; 2802 GraphIndex ret{0}; 2803 for (Cluster* cluster : clusters) { 2804 ret += (cluster != last); 2805 last = cluster; 2806 } 2807 return ret; 2808 } 2809 2810 std::pair<std::vector<FeeFrac>, std::vector<FeeFrac>> TxGraphImpl::GetMainStagingDiagrams() noexcept 2811 { 2812 Assume(m_staging_clusterset.has_value()); 2813 MakeAllAcceptable(0); 2814 Assume(m_main_clusterset.m_deps_to_add.empty()); // can only fail if main is oversized 2815 MakeAllAcceptable(1); 2816 Assume(m_staging_clusterset->m_deps_to_add.empty()); // can only fail if staging is oversized 2817 // For all Clusters in main which conflict with Clusters in staging (i.e., all that are removed 2818 // by, or replaced in, staging), gather their chunk feerates. 2819 auto main_clusters = GetConflicts(); 2820 std::vector<FeeFrac> main_feerates, staging_feerates; 2821 for (Cluster* cluster : main_clusters) { 2822 cluster->AppendChunkFeerates(main_feerates); 2823 } 2824 // Do the same for the Clusters in staging themselves. 2825 for (int quality = 0; quality < int(QualityLevel::NONE); ++quality) { 2826 for (const auto& cluster : m_staging_clusterset->m_clusters[quality]) { 2827 cluster->AppendChunkFeerates(staging_feerates); 2828 } 2829 } 2830 // Sort both by decreasing feerate to obtain diagrams, and return them. 2831 std::sort(main_feerates.begin(), main_feerates.end(), [](auto& a, auto& b) { return a > b; }); 2832 std::sort(staging_feerates.begin(), staging_feerates.end(), [](auto& a, auto& b) { return a > b; }); 2833 return std::make_pair(std::move(main_feerates), std::move(staging_feerates)); 2834 } 2835 2836 void GenericClusterImpl::SanityCheck(const TxGraphImpl& graph, int level) const 2837 { 2838 // There must be an m_mapping for each m_depgraph position (including holes). 2839 assert(m_depgraph.PositionRange() == m_mapping.size()); 2840 // The linearization for this Cluster must contain every transaction once. 2841 assert(m_depgraph.TxCount() == m_linearization.size()); 2842 // Unless a split is to be applied, the cluster cannot have any holes. 2843 if (!NeedsSplitting()) { 2844 assert(m_depgraph.Positions() == SetType::Fill(m_depgraph.TxCount())); 2845 } 2846 2847 // Compute the chunking of m_linearization. 2848 auto linchunking = ChunkLinearizationInfo(m_depgraph, m_linearization); 2849 unsigned chunk_num{0}; 2850 2851 // Verify m_linearization. 2852 SetType m_done; 2853 LinearizationIndex linindex{0}; 2854 DepGraphIndex chunk_pos{0}; //!< position within the current chunk 2855 assert(m_depgraph.IsAcyclic()); 2856 if (m_linearization.empty()) return; 2857 FeeFrac equal_feerate_prefix = linchunking[chunk_num].feerate; 2858 for (auto lin_pos : m_linearization) { 2859 assert(lin_pos < m_mapping.size()); 2860 const auto& entry = graph.m_entries[m_mapping[lin_pos]]; 2861 // Check that the linearization is topological. 2862 m_done.Set(lin_pos); 2863 if (IsTopological()) { 2864 assert(m_done.IsSupersetOf(m_depgraph.Ancestors(lin_pos))); 2865 } 2866 // Check that the Entry has a locator pointing back to this Cluster & position within it. 2867 assert(entry.m_locator[level].cluster == this); 2868 assert(entry.m_locator[level].index == lin_pos); 2869 // For main-level entries, check linearization position and chunk feerate. 2870 if (level == 0 && IsAcceptable()) { 2871 assert(entry.m_main_lin_index == linindex); 2872 ++linindex; 2873 if (!linchunking[chunk_num].transactions[lin_pos]) { 2874 // First transaction of a new chunk. 2875 ++chunk_num; 2876 assert(chunk_num < linchunking.size()); 2877 chunk_pos = 0; 2878 if (linchunking[chunk_num].feerate << equal_feerate_prefix) { 2879 equal_feerate_prefix = linchunking[chunk_num].feerate; 2880 } else { 2881 assert(!(linchunking[chunk_num].feerate >> equal_feerate_prefix)); 2882 equal_feerate_prefix += linchunking[chunk_num].feerate; 2883 } 2884 } 2885 assert(entry.m_main_chunk_feerate == linchunking[chunk_num].feerate); 2886 assert(entry.m_main_equal_feerate_chunk_prefix_size == equal_feerate_prefix.size); 2887 // Verify that an entry in the chunk index exists for every chunk-ending transaction. 2888 ++chunk_pos; 2889 if (graph.m_main_clusterset.m_to_remove.empty()) { 2890 bool is_chunk_end = (chunk_pos == linchunking[chunk_num].transactions.Count()); 2891 assert((entry.m_main_chunkindex_iterator != graph.m_main_chunkindex.end()) == is_chunk_end); 2892 if (is_chunk_end) { 2893 auto& chunk_data = *entry.m_main_chunkindex_iterator; 2894 if (m_done == m_depgraph.Positions() && chunk_pos == 1) { 2895 assert(chunk_data.m_chunk_count == LinearizationIndex(-1)); 2896 } else { 2897 assert(chunk_data.m_chunk_count == chunk_pos); 2898 } 2899 } 2900 } 2901 // If this Cluster has an acceptable quality level, its chunks must be connected. 2902 assert(m_depgraph.IsConnected(linchunking[chunk_num].transactions)); 2903 } 2904 } 2905 // Verify that each element of m_depgraph occurred in m_linearization. 2906 assert(m_done == m_depgraph.Positions()); 2907 } 2908 2909 void SingletonClusterImpl::SanityCheck(const TxGraphImpl& graph, int level) const 2910 { 2911 // All singletons are optimal, oversized, or need splitting. 2912 Assume(IsOptimal() || IsOversized() || NeedsSplitting()); 2913 if (GetTxCount()) { 2914 const auto& entry = graph.m_entries[m_graph_index]; 2915 // Check that the Entry has a locator pointing back to this Cluster & position within it. 2916 assert(entry.m_locator[level].cluster == this); 2917 assert(entry.m_locator[level].index == 0); 2918 // For main-level entries, check linearization position and chunk feerate. 2919 if (level == 0 && IsAcceptable()) { 2920 assert(entry.m_main_lin_index == 0); 2921 assert(entry.m_main_chunk_feerate == m_feerate); 2922 assert(entry.m_main_equal_feerate_chunk_prefix_size == m_feerate.size); 2923 if (graph.m_main_clusterset.m_to_remove.empty()) { 2924 assert(entry.m_main_chunkindex_iterator != graph.m_main_chunkindex.end()); 2925 auto& chunk_data = *entry.m_main_chunkindex_iterator; 2926 assert(chunk_data.m_chunk_count == LinearizationIndex(-1)); 2927 } 2928 } 2929 } 2930 } 2931 2932 void TxGraphImpl::SanityCheck() const 2933 { 2934 /** Which GraphIndexes ought to occur in m_unlinked, based on m_entries. */ 2935 std::set<GraphIndex> expected_unlinked; 2936 /** Which Clusters ought to occur in ClusterSet::m_clusters, based on m_entries. */ 2937 std::set<const Cluster*> expected_clusters[MAX_LEVELS]; 2938 /** Which GraphIndexes ought to occur in ClusterSet::m_removed, based on m_entries. */ 2939 std::set<GraphIndex> expected_removed[MAX_LEVELS]; 2940 /** Which Cluster::m_sequence values have been encountered. */ 2941 std::set<uint64_t> sequences; 2942 /** Which GraphIndexes ought to occur in m_main_chunkindex, based on m_entries. */ 2943 std::set<GraphIndex> expected_chunkindex; 2944 /** Whether compaction is possible in the current state. */ 2945 bool compact_possible{true}; 2946 2947 // Go over all Entry objects in m_entries. 2948 for (GraphIndex idx = 0; idx < m_entries.size(); ++idx) { 2949 const auto& entry = m_entries[idx]; 2950 if (entry.m_ref == nullptr) { 2951 // Unlinked Entry must have indexes appear in m_unlinked. 2952 expected_unlinked.insert(idx); 2953 } else { 2954 // Every non-unlinked Entry must have a Ref that points back to it. 2955 assert(GetRefGraph(*entry.m_ref) == this); 2956 assert(GetRefIndex(*entry.m_ref) == idx); 2957 } 2958 if (entry.m_main_chunkindex_iterator != m_main_chunkindex.end()) { 2959 // Remember which entries we see a chunkindex entry for. 2960 assert(entry.m_locator[0].IsPresent()); 2961 expected_chunkindex.insert(idx); 2962 } 2963 // Verify the Entry m_locators. 2964 bool was_present{false}, was_removed{false}; 2965 for (int level = 0; level < MAX_LEVELS; ++level) { 2966 const auto& locator = entry.m_locator[level]; 2967 // Every Locator must be in exactly one of these 3 states. 2968 assert(locator.IsMissing() + locator.IsRemoved() + locator.IsPresent() == 1); 2969 if (locator.IsPresent()) { 2970 // Once removed, a transaction cannot be revived. 2971 assert(!was_removed); 2972 // Verify that the Cluster agrees with where the Locator claims the transaction is. 2973 assert(locator.cluster->GetClusterEntry(locator.index) == idx); 2974 // Remember that we expect said Cluster to appear in the ClusterSet::m_clusters. 2975 expected_clusters[level].insert(locator.cluster); 2976 was_present = true; 2977 } else if (locator.IsRemoved()) { 2978 // Level 0 (main) cannot have IsRemoved locators (IsMissing there means non-existing). 2979 assert(level > 0); 2980 // A Locator can only be IsRemoved if it was IsPresent before, and only once. 2981 assert(was_present && !was_removed); 2982 // Remember that we expect this GraphIndex to occur in the ClusterSet::m_removed. 2983 expected_removed[level].insert(idx); 2984 was_removed = true; 2985 } 2986 } 2987 } 2988 2989 // For all levels (0 = main, 1 = staged)... 2990 for (int level = 0; level <= GetTopLevel(); ++level) { 2991 assert(level < MAX_LEVELS); 2992 auto& clusterset = GetClusterSet(level); 2993 std::set<const Cluster*> actual_clusters; 2994 size_t recomputed_cluster_usage{0}; 2995 2996 // For all quality levels... 2997 for (int qual = 0; qual < int(QualityLevel::NONE); ++qual) { 2998 QualityLevel quality{qual}; 2999 const auto& quality_clusters = clusterset.m_clusters[qual]; 3000 // ... for all clusters in them ... 3001 for (ClusterSetIndex setindex = 0; setindex < quality_clusters.size(); ++setindex) { 3002 const auto& cluster = *quality_clusters[setindex]; 3003 // The number of transactions in a Cluster cannot exceed m_max_cluster_count. 3004 assert(cluster.GetTxCount() <= m_max_cluster_count); 3005 // The level must match the Cluster's own idea of what level it is in (but GetLevel 3006 // can only be called for non-empty Clusters). 3007 assert(cluster.GetTxCount() == 0 || level == cluster.GetLevel(*this)); 3008 // The sum of their sizes cannot exceed m_max_cluster_size, unless it is an 3009 // individually oversized transaction singleton. Note that groups of to-be-merged 3010 // clusters which would exceed this limit are marked oversized, which means they 3011 // are never applied. 3012 assert(cluster.IsOversized() || cluster.GetTotalTxSize() <= m_max_cluster_size); 3013 // OVERSIZED clusters are singletons. 3014 assert(!cluster.IsOversized() || cluster.GetTxCount() == 1); 3015 // Transaction counts cannot exceed the Cluster implementation's maximum 3016 // supported transactions count. 3017 assert(cluster.GetTxCount() <= cluster.GetMaxTxCount()); 3018 // Unless a Split is yet to be applied, the number of transactions must not be 3019 // below the Cluster implementation's intended transaction count. 3020 if (!cluster.NeedsSplitting()) { 3021 assert(cluster.GetTxCount() >= cluster.GetMinIntendedTxCount()); 3022 } 3023 3024 // Check the sequence number. 3025 assert(cluster.m_sequence < m_next_sequence_counter); 3026 assert(!sequences.contains(cluster.m_sequence)); 3027 sequences.insert(cluster.m_sequence); 3028 // Remember we saw this Cluster (only if it is non-empty; empty Clusters aren't 3029 // expected to be referenced by the Entry vector). 3030 if (cluster.GetTxCount() != 0) { 3031 actual_clusters.insert(&cluster); 3032 } 3033 // Sanity check the cluster, according to the Cluster's internal rules. 3034 cluster.SanityCheck(*this, level); 3035 // Check that the cluster's quality and setindex matches its position in the quality list. 3036 assert(cluster.m_quality == quality); 3037 assert(cluster.m_setindex == setindex); 3038 // Count memory usage. 3039 recomputed_cluster_usage += cluster.TotalMemoryUsage(); 3040 } 3041 } 3042 3043 // Verify memory usage. 3044 assert(clusterset.m_cluster_usage == recomputed_cluster_usage); 3045 3046 // Verify that all to-be-removed transactions have valid identifiers. 3047 for (GraphIndex idx : clusterset.m_to_remove) { 3048 assert(idx < m_entries.size()); 3049 // We cannot assert that all m_to_remove transactions are still present: ~Ref on a 3050 // (P,M) transaction (present in main, inherited in staging) will cause an m_to_remove 3051 // addition in both main and staging, but a subsequence ApplyRemovals in main will 3052 // cause it to disappear from staging too, leaving the m_to_remove in place. 3053 } 3054 3055 // Verify that all to-be-added dependencies have valid identifiers. 3056 for (auto [par_idx, chl_idx] : clusterset.m_deps_to_add) { 3057 assert(par_idx != chl_idx); 3058 assert(par_idx < m_entries.size()); 3059 assert(chl_idx < m_entries.size()); 3060 } 3061 3062 // Verify that the actually encountered clusters match the ones occurring in Entry vector. 3063 assert(actual_clusters == expected_clusters[level]); 3064 3065 // Verify that the contents of m_removed matches what was expected based on the Entry vector. 3066 std::set<GraphIndex> actual_removed(clusterset.m_removed.begin(), clusterset.m_removed.end()); 3067 for (auto i : expected_unlinked) { 3068 // If a transaction exists in both main and staging, and is removed from staging (adding 3069 // it to m_removed there), and consequently destroyed (wiping the locator completely), 3070 // it can remain in m_removed despite not having an IsRemoved() locator. Exclude those 3071 // transactions from the comparison here. 3072 actual_removed.erase(i); 3073 expected_removed[level].erase(i); 3074 } 3075 3076 assert(actual_removed == expected_removed[level]); 3077 3078 // If any GraphIndex entries remain in this ClusterSet, compact is not possible. 3079 if (!clusterset.m_deps_to_add.empty()) compact_possible = false; 3080 if (!clusterset.m_to_remove.empty()) compact_possible = false; 3081 if (!clusterset.m_removed.empty()) compact_possible = false; 3082 3083 // For non-top levels, m_oversized must be known (as it cannot change until the level 3084 // on top is gone). 3085 if (level < GetTopLevel()) assert(clusterset.m_oversized.has_value()); 3086 } 3087 3088 // Verify that the contents of m_unlinked matches what was expected based on the Entry vector. 3089 std::set<GraphIndex> actual_unlinked(m_unlinked.begin(), m_unlinked.end()); 3090 assert(actual_unlinked == expected_unlinked); 3091 3092 // If compaction was possible, it should have been performed already, and m_unlinked must be 3093 // empty (to prevent memory leaks due to an ever-growing m_entries vector). 3094 if (compact_possible) { 3095 assert(actual_unlinked.empty()); 3096 } 3097 3098 // Finally, check the chunk index. 3099 std::set<GraphIndex> actual_chunkindex; 3100 FeeFrac last_chunk_feerate; 3101 for (const auto& chunk : m_main_chunkindex) { 3102 GraphIndex idx = chunk.m_graph_index; 3103 actual_chunkindex.insert(idx); 3104 auto chunk_feerate = m_entries[idx].m_main_chunk_feerate; 3105 if (!last_chunk_feerate.IsEmpty()) { 3106 assert(FeeRateCompare(last_chunk_feerate, chunk_feerate) >= 0); 3107 } 3108 last_chunk_feerate = chunk_feerate; 3109 } 3110 assert(actual_chunkindex == expected_chunkindex); 3111 } 3112 3113 bool TxGraphImpl::DoWork(uint64_t max_cost) noexcept 3114 { 3115 uint64_t cost_done{0}; 3116 // First linearize everything in NEEDS_RELINEARIZE to an acceptable level. If more budget 3117 // remains after that, try to make everything optimal. 3118 for (QualityLevel quality : {QualityLevel::NEEDS_FIX, QualityLevel::NEEDS_RELINEARIZE, QualityLevel::ACCEPTABLE}) { 3119 // First linearize staging, if it exists, then main. 3120 for (int level = GetTopLevel(); level >= 0; --level) { 3121 // Do not modify main if it has any observers. 3122 if (level == 0 && m_main_chunkindex_observers != 0) continue; 3123 ApplyDependencies(level); 3124 auto& clusterset = GetClusterSet(level); 3125 // Do not modify oversized levels. 3126 if (clusterset.m_oversized == true) continue; 3127 auto& queue = clusterset.m_clusters[int(quality)]; 3128 while (!queue.empty()) { 3129 if (cost_done >= max_cost) return false; 3130 // Randomize the order in which we process, so that if the first cluster somehow 3131 // needs more work than what max_cost allows, we don't keep spending it on the same 3132 // one. 3133 auto pos = m_rng.randrange<size_t>(queue.size()); 3134 auto cost_now = max_cost - cost_done; 3135 if (quality == QualityLevel::NEEDS_FIX || quality == QualityLevel::NEEDS_RELINEARIZE) { 3136 // If we're working with clusters that need relinearization still, only perform 3137 // up to m_acceptable_cost work. If they become ACCEPTABLE, and we still 3138 // have budget after all other clusters are ACCEPTABLE too, we'll spend the 3139 // remaining budget on trying to make them OPTIMAL. 3140 cost_now = std::min(cost_now, m_acceptable_cost); 3141 } 3142 auto [cost, improved] = queue[pos].get()->Relinearize(*this, level, cost_now); 3143 cost_done += cost; 3144 // If no improvement was made to the Cluster, it means we've essentially run out of 3145 // budget. Even though it may be the case that cost_done < max_cost still, the 3146 // linearizer decided there wasn't enough budget left to attempt anything with. 3147 // To avoid an infinite loop that keeps trying clusters with minuscule budgets, 3148 // stop here too. 3149 if (!improved) return false; 3150 } 3151 } 3152 } 3153 // All possible work has been performed, so we can return true. Note that this does *not* mean 3154 // that all clusters are optimally linearized now. It may be that there is nothing to do left 3155 // because all non-optimal clusters are in oversized and/or observer-bearing levels. 3156 return true; 3157 } 3158 3159 void BlockBuilderImpl::Next() noexcept 3160 { 3161 // Don't do anything if we're already done. 3162 if (m_cur_iter == m_graph->m_main_chunkindex.end()) return; 3163 while (true) { 3164 // Advance the pointer, and stop if we reach the end. 3165 ++m_cur_iter; 3166 m_cur_cluster = nullptr; 3167 if (m_cur_iter == m_graph->m_main_chunkindex.end()) break; 3168 // Find the cluster pointed to by m_cur_iter. 3169 const auto& chunk_data = *m_cur_iter; 3170 const auto& chunk_end_entry = m_graph->m_entries[chunk_data.m_graph_index]; 3171 m_cur_cluster = chunk_end_entry.m_locator[0].cluster; 3172 m_known_end_of_cluster = false; 3173 // If we previously skipped a chunk from this cluster we cannot include more from it. 3174 if (!m_excluded_clusters.contains(m_cur_cluster->m_sequence)) break; 3175 } 3176 } 3177 3178 std::optional<std::pair<std::vector<TxGraph::Ref*>, FeePerWeight>> BlockBuilderImpl::GetCurrentChunk() noexcept 3179 { 3180 std::optional<std::pair<std::vector<TxGraph::Ref*>, FeePerWeight>> ret; 3181 // Populate the return value if we are not done. 3182 if (m_cur_iter != m_graph->m_main_chunkindex.end()) { 3183 ret.emplace(); 3184 const auto& chunk_data = *m_cur_iter; 3185 const auto& chunk_end_entry = m_graph->m_entries[chunk_data.m_graph_index]; 3186 if (chunk_data.m_chunk_count == LinearizationIndex(-1)) { 3187 // Special case in case just a single transaction remains, avoiding the need to 3188 // dispatch to and dereference Cluster. 3189 ret->first.resize(1); 3190 Assume(chunk_end_entry.m_ref != nullptr); 3191 ret->first[0] = chunk_end_entry.m_ref; 3192 m_known_end_of_cluster = true; 3193 } else { 3194 Assume(m_cur_cluster); 3195 ret->first.resize(chunk_data.m_chunk_count); 3196 auto start_pos = chunk_end_entry.m_main_lin_index + 1 - chunk_data.m_chunk_count; 3197 m_known_end_of_cluster = m_cur_cluster->GetClusterRefs(*m_graph, ret->first, start_pos); 3198 // If the chunk size was 1 and at end of cluster, then the special case above should 3199 // have been used. 3200 Assume(!m_known_end_of_cluster || chunk_data.m_chunk_count > 1); 3201 } 3202 ret->second = chunk_end_entry.m_main_chunk_feerate; 3203 } 3204 return ret; 3205 } 3206 3207 BlockBuilderImpl::BlockBuilderImpl(TxGraphImpl& graph) noexcept : m_graph(&graph) 3208 { 3209 // Make sure all clusters in main are up to date, and acceptable. 3210 m_graph->MakeAllAcceptable(0); 3211 // There cannot remain any inapplicable dependencies (only possible if main is oversized). 3212 Assume(m_graph->m_main_clusterset.m_deps_to_add.empty()); 3213 // Remember that this object is observing the graph's index, so that we can detect concurrent 3214 // modifications. 3215 ++m_graph->m_main_chunkindex_observers; 3216 // Find the first chunk. 3217 m_cur_iter = m_graph->m_main_chunkindex.begin(); 3218 m_cur_cluster = nullptr; 3219 if (m_cur_iter != m_graph->m_main_chunkindex.end()) { 3220 // Find the cluster pointed to by m_cur_iter. 3221 const auto& chunk_data = *m_cur_iter; 3222 const auto& chunk_end_entry = m_graph->m_entries[chunk_data.m_graph_index]; 3223 m_cur_cluster = chunk_end_entry.m_locator[0].cluster; 3224 } 3225 } 3226 3227 BlockBuilderImpl::~BlockBuilderImpl() 3228 { 3229 Assume(m_graph->m_main_chunkindex_observers > 0); 3230 // Permit modifications to the main graph again after destroying the BlockBuilderImpl. 3231 --m_graph->m_main_chunkindex_observers; 3232 } 3233 3234 void BlockBuilderImpl::Include() noexcept 3235 { 3236 // The actual inclusion of the chunk is done by the calling code. All we have to do is switch 3237 // to the next chunk. 3238 Next(); 3239 } 3240 3241 void BlockBuilderImpl::Skip() noexcept 3242 { 3243 // When skipping a chunk we need to not include anything more of the cluster, as that could make 3244 // the result topologically invalid. However, don't do this if the chunk is known to be the last 3245 // chunk of the cluster. This may significantly reduce the size of m_excluded_clusters, 3246 // especially when many singleton clusters are ignored. 3247 if (m_cur_cluster != nullptr && !m_known_end_of_cluster) { 3248 m_excluded_clusters.insert(m_cur_cluster->m_sequence); 3249 } 3250 Next(); 3251 } 3252 3253 std::unique_ptr<TxGraph::BlockBuilder> TxGraphImpl::GetBlockBuilder() noexcept 3254 { 3255 return std::make_unique<BlockBuilderImpl>(*this); 3256 } 3257 3258 std::pair<std::vector<TxGraph::Ref*>, FeePerWeight> TxGraphImpl::GetWorstMainChunk() noexcept 3259 { 3260 std::pair<std::vector<Ref*>, FeePerWeight> ret; 3261 // Make sure all clusters in main are up to date, and acceptable. 3262 MakeAllAcceptable(0); 3263 Assume(m_main_clusterset.m_deps_to_add.empty()); 3264 // If the graph is not empty, populate ret. 3265 if (!m_main_chunkindex.empty()) { 3266 const auto& chunk_data = *m_main_chunkindex.rbegin(); 3267 const auto& chunk_end_entry = m_entries[chunk_data.m_graph_index]; 3268 Cluster* cluster = chunk_end_entry.m_locator[0].cluster; 3269 if (chunk_data.m_chunk_count == LinearizationIndex(-1) || chunk_data.m_chunk_count == 1) { 3270 // Special case for singletons. 3271 ret.first.resize(1); 3272 Assume(chunk_end_entry.m_ref != nullptr); 3273 ret.first[0] = chunk_end_entry.m_ref; 3274 } else { 3275 ret.first.resize(chunk_data.m_chunk_count); 3276 auto start_pos = chunk_end_entry.m_main_lin_index + 1 - chunk_data.m_chunk_count; 3277 cluster->GetClusterRefs(*this, ret.first, start_pos); 3278 std::reverse(ret.first.begin(), ret.first.end()); 3279 } 3280 ret.second = chunk_end_entry.m_main_chunk_feerate; 3281 } 3282 return ret; 3283 } 3284 3285 std::vector<TxGraph::Ref*> TxGraphImpl::Trim() noexcept 3286 { 3287 int level = GetTopLevel(); 3288 Assume(m_main_chunkindex_observers == 0 || level != 0); 3289 std::vector<TxGraph::Ref*> ret; 3290 3291 // Compute the groups of to-be-merged Clusters (which also applies all removals, and splits). 3292 auto& clusterset = GetClusterSet(level); 3293 if (clusterset.m_oversized == false) return ret; 3294 GroupClusters(level); 3295 Assume(clusterset.m_group_data.has_value()); 3296 // Nothing to do if not oversized. 3297 Assume(clusterset.m_oversized.has_value()); 3298 if (clusterset.m_oversized == false) return ret; 3299 3300 // In this function, would-be clusters (as precomputed in m_group_data by GroupClusters) are 3301 // trimmed by removing transactions in them such that the resulting clusters satisfy the size 3302 // and count limits. 3303 // 3304 // It works by defining for each would-be cluster a rudimentary linearization: at every point 3305 // the highest-chunk-feerate remaining transaction is picked among those with no unmet 3306 // dependencies. "Dependency" here means either a to-be-added dependency (m_deps_to_add), or 3307 // an implicit dependency added between any two consecutive transaction in their current 3308 // cluster linearization. So it can be seen as a "merge sort" of the chunks of the clusters, 3309 // but respecting the dependencies being added. 3310 // 3311 // This rudimentary linearization is computed lazily, by putting all eligible (no unmet 3312 // dependencies) transactions in a heap, and popping the highest-feerate one from it. Along the 3313 // way, the counts and sizes of the would-be clusters up to that point are tracked (by 3314 // partitioning the involved transactions using a union-find structure). Any transaction whose 3315 // addition would cause a violation is removed, along with all their descendants. 3316 // 3317 // A next invocation of GroupClusters (after applying the removals) will compute the new 3318 // resulting clusters, and none of them will violate the limits. 3319 3320 /** All dependencies (both to be added ones, and implicit ones between consecutive transactions 3321 * in existing cluster linearizations), sorted by parent. */ 3322 std::vector<std::pair<GraphIndex, GraphIndex>> deps_by_parent; 3323 /** Same, but sorted by child. */ 3324 std::vector<std::pair<GraphIndex, GraphIndex>> deps_by_child; 3325 /** Information about all transactions involved in a Cluster group to be trimmed, sorted by 3326 * GraphIndex. It contains entries both for transactions that have already been included, 3327 * and ones that have not yet been. */ 3328 std::vector<TrimTxData> trim_data; 3329 /** Iterators into trim_data, treated as a max heap according to cmp_fn below. Each entry is 3330 * a transaction that has not yet been included yet, but all its ancestors have. */ 3331 std::vector<std::vector<TrimTxData>::iterator> trim_heap; 3332 /** The list of representatives of the partitions a given transaction depends on. */ 3333 std::vector<TrimTxData*> current_deps; 3334 3335 /** Function to define the ordering of trim_heap. */ 3336 static constexpr auto cmp_fn = [](auto a, auto b) noexcept { 3337 // Sort by increasing chunk feerate, and then by decreasing size. 3338 // We do not need to sort by cluster or within clusters, because due to the implicit 3339 // dependency between consecutive linearization elements, no two transactions from the 3340 // same Cluster will ever simultaneously be in the heap. 3341 return a->m_chunk_feerate < b->m_chunk_feerate; 3342 }; 3343 3344 /** Given a TrimTxData entry, find the representative of the partition it is in. */ 3345 static constexpr auto find_fn = [](TrimTxData* arg) noexcept { 3346 while (arg != arg->m_uf_parent) { 3347 // Replace pointer to parent with pointer to grandparent (path splitting). 3348 // See https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Finding_set_representatives. 3349 auto par = arg->m_uf_parent; 3350 arg->m_uf_parent = par->m_uf_parent; 3351 arg = par; 3352 } 3353 return arg; 3354 }; 3355 3356 /** Given two TrimTxData entries, union the partitions they are in, and return the 3357 * representative. */ 3358 static constexpr auto union_fn = [](TrimTxData* arg1, TrimTxData* arg2) noexcept { 3359 // Replace arg1 and arg2 by their representatives. 3360 auto rep1 = find_fn(arg1); 3361 auto rep2 = find_fn(arg2); 3362 // Bail out if both representatives are the same, because that means arg1 and arg2 are in 3363 // the same partition already. 3364 if (rep1 == rep2) return rep1; 3365 // Pick the lower-count root to become a child of the higher-count one. 3366 // See https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Union_by_size. 3367 if (rep1->m_uf_count < rep2->m_uf_count) std::swap(rep1, rep2); 3368 rep2->m_uf_parent = rep1; 3369 // Add the statistics of arg2 (which is no longer a representative) to those of arg1 (which 3370 // is now the representative for both). 3371 rep1->m_uf_size += rep2->m_uf_size; 3372 rep1->m_uf_count += rep2->m_uf_count; 3373 return rep1; 3374 }; 3375 3376 /** Get iterator to TrimTxData entry for a given index. */ 3377 auto locate_fn = [&](GraphIndex index) noexcept { 3378 auto it = std::lower_bound(trim_data.begin(), trim_data.end(), index, [](TrimTxData& elem, GraphIndex idx) noexcept { 3379 return elem.m_index < idx; 3380 }); 3381 Assume(it != trim_data.end() && it->m_index == index); 3382 return it; 3383 }; 3384 3385 // For each group of to-be-merged Clusters. 3386 for (const auto& group_data : clusterset.m_group_data->m_groups) { 3387 trim_data.clear(); 3388 trim_heap.clear(); 3389 deps_by_child.clear(); 3390 deps_by_parent.clear(); 3391 3392 // Gather trim data and implicit dependency data from all involved Clusters. 3393 auto cluster_span = std::span{clusterset.m_group_data->m_group_clusters} 3394 .subspan(group_data.m_cluster_offset, group_data.m_cluster_count); 3395 uint64_t size{0}; 3396 for (Cluster* cluster : cluster_span) { 3397 MakeAcceptable(*cluster, cluster->GetLevel(*this)); 3398 size += cluster->AppendTrimData(trim_data, deps_by_child); 3399 } 3400 // If this group of Clusters does not violate any limits, continue to the next group. 3401 if (trim_data.size() <= m_max_cluster_count && size <= m_max_cluster_size) continue; 3402 // Sort the trim data by GraphIndex. In what follows, we will treat this sorted vector as 3403 // a map from GraphIndex to TrimTxData via locate_fn, and its ordering will not change 3404 // anymore. 3405 std::sort(trim_data.begin(), trim_data.end(), [](auto& a, auto& b) noexcept { return a.m_index < b.m_index; }); 3406 3407 // Add the explicitly added dependencies to deps_by_child. 3408 deps_by_child.insert(deps_by_child.end(), 3409 clusterset.m_deps_to_add.begin() + group_data.m_deps_offset, 3410 clusterset.m_deps_to_add.begin() + group_data.m_deps_offset + group_data.m_deps_count); 3411 3412 // Sort deps_by_child by child transaction GraphIndex. The order will not be changed 3413 // anymore after this. 3414 std::sort(deps_by_child.begin(), deps_by_child.end(), [](auto& a, auto& b) noexcept { return a.second < b.second; }); 3415 // Fill m_parents_count and m_parents_offset in trim_data, as well as m_deps_left, and 3416 // initially populate trim_heap. Because of the sort above, all dependencies involving the 3417 // same child are grouped together, so a single linear scan suffices. 3418 auto deps_it = deps_by_child.begin(); 3419 for (auto trim_it = trim_data.begin(); trim_it != trim_data.end(); ++trim_it) { 3420 trim_it->m_parent_offset = deps_it - deps_by_child.begin(); 3421 trim_it->m_deps_left = 0; 3422 while (deps_it != deps_by_child.end() && deps_it->second == trim_it->m_index) { 3423 ++trim_it->m_deps_left; 3424 ++deps_it; 3425 } 3426 trim_it->m_parent_count = trim_it->m_deps_left; 3427 // If this transaction has no unmet dependencies, and is not oversized, add it to the 3428 // heap (just append for now, the heapification happens below). 3429 if (trim_it->m_deps_left == 0 && trim_it->m_tx_size <= m_max_cluster_size) { 3430 trim_heap.push_back(trim_it); 3431 } 3432 } 3433 Assume(deps_it == deps_by_child.end()); 3434 3435 // Construct deps_by_parent, sorted by parent transaction GraphIndex. The order will not be 3436 // changed anymore after this. 3437 deps_by_parent = deps_by_child; 3438 std::sort(deps_by_parent.begin(), deps_by_parent.end(), [](auto& a, auto& b) noexcept { return a.first < b.first; }); 3439 // Fill m_children_offset and m_children_count in trim_data. Because of the sort above, all 3440 // dependencies involving the same parent are grouped together, so a single linear scan 3441 // suffices. 3442 deps_it = deps_by_parent.begin(); 3443 for (auto& trim_entry : trim_data) { 3444 trim_entry.m_children_count = 0; 3445 trim_entry.m_children_offset = deps_it - deps_by_parent.begin(); 3446 while (deps_it != deps_by_parent.end() && deps_it->first == trim_entry.m_index) { 3447 ++trim_entry.m_children_count; 3448 ++deps_it; 3449 } 3450 } 3451 Assume(deps_it == deps_by_parent.end()); 3452 3453 // Build a heap of all transactions with 0 unmet dependencies. 3454 std::make_heap(trim_heap.begin(), trim_heap.end(), cmp_fn); 3455 3456 // Iterate over to-be-included transactions, and convert them to included transactions, or 3457 // skip them if adding them would violate resource limits of the would-be cluster. 3458 // 3459 // It is possible that the heap empties without ever hitting either cluster limit, in case 3460 // the implied graph (to be added dependencies plus implicit dependency between each 3461 // original transaction and its predecessor in the linearization it came from) contains 3462 // cycles. Such cycles will be removed entirely, because each of the transactions in the 3463 // cycle permanently have unmet dependencies. However, this cannot occur in real scenarios 3464 // where Trim() is called to deal with reorganizations that would violate cluster limits, 3465 // as all added dependencies are in the same direction (from old mempool transactions to 3466 // new from-block transactions); cycles require dependencies in both directions to be 3467 // added. 3468 while (!trim_heap.empty()) { 3469 // Move the best remaining transaction to the end of trim_heap. 3470 std::pop_heap(trim_heap.begin(), trim_heap.end(), cmp_fn); 3471 // Pop it, and find its TrimTxData. 3472 auto& entry = *trim_heap.back(); 3473 trim_heap.pop_back(); 3474 3475 // Initialize it as a singleton partition. 3476 entry.m_uf_parent = &entry; 3477 entry.m_uf_count = 1; 3478 entry.m_uf_size = entry.m_tx_size; 3479 3480 // Find the distinct transaction partitions this entry depends on. 3481 current_deps.clear(); 3482 for (auto& [par, chl] : std::span{deps_by_child}.subspan(entry.m_parent_offset, entry.m_parent_count)) { 3483 Assume(chl == entry.m_index); 3484 current_deps.push_back(find_fn(&*locate_fn(par))); 3485 } 3486 std::sort(current_deps.begin(), current_deps.end()); 3487 current_deps.erase(std::unique(current_deps.begin(), current_deps.end()), current_deps.end()); 3488 3489 // Compute resource counts. 3490 uint32_t new_count = 1; 3491 uint64_t new_size = entry.m_tx_size; 3492 for (TrimTxData* ptr : current_deps) { 3493 new_count += ptr->m_uf_count; 3494 new_size += ptr->m_uf_size; 3495 } 3496 // Skip the entry if this would violate any limit. 3497 if (new_count > m_max_cluster_count || new_size > m_max_cluster_size) continue; 3498 3499 // Union the partitions this transaction and all its dependencies are in together. 3500 auto rep = &entry; 3501 for (TrimTxData* ptr : current_deps) rep = union_fn(ptr, rep); 3502 // Mark the entry as included (so the loop below will not remove the transaction). 3503 entry.m_deps_left = uint32_t(-1); 3504 // Mark each to-be-added dependency involving this transaction as parent satisfied. 3505 for (auto& [par, chl] : std::span{deps_by_parent}.subspan(entry.m_children_offset, entry.m_children_count)) { 3506 Assume(par == entry.m_index); 3507 auto chl_it = locate_fn(chl); 3508 // Reduce the number of unmet dependencies of chl_it, and if that brings the number 3509 // to zero, add it to the heap of includable transactions. 3510 Assume(chl_it->m_deps_left > 0); 3511 if (--chl_it->m_deps_left == 0) { 3512 trim_heap.push_back(chl_it); 3513 std::push_heap(trim_heap.begin(), trim_heap.end(), cmp_fn); 3514 } 3515 } 3516 } 3517 3518 // Remove all the transactions that were not processed above. Because nothing gets 3519 // processed until/unless all its dependencies are met, this automatically guarantees 3520 // that if a transaction is removed, all its descendants, or would-be descendants, are 3521 // removed as well. 3522 for (const auto& trim_entry : trim_data) { 3523 if (trim_entry.m_deps_left != uint32_t(-1)) { 3524 ret.push_back(m_entries[trim_entry.m_index].m_ref); 3525 clusterset.m_to_remove.push_back(trim_entry.m_index); 3526 } 3527 } 3528 } 3529 clusterset.m_group_data.reset(); 3530 clusterset.m_oversized = false; 3531 Assume(!ret.empty()); 3532 return ret; 3533 } 3534 3535 size_t TxGraphImpl::GetMainMemoryUsage() noexcept 3536 { 3537 // Make sure splits/merges are applied, as memory usage may not be representative otherwise. 3538 SplitAll(/*up_to_level=*/0); 3539 ApplyDependencies(/*level=*/0); 3540 // Compute memory usage 3541 size_t usage = /* From clusters */ 3542 m_main_clusterset.m_cluster_usage + 3543 /* From Entry objects. */ 3544 sizeof(Entry) * m_main_clusterset.m_txcount + 3545 /* From the chunk index. */ 3546 memusage::DynamicUsage(m_main_chunkindex); 3547 return usage; 3548 } 3549 3550 } // namespace 3551 3552 TxGraph::Ref::~Ref() 3553 { 3554 if (m_graph) { 3555 // Inform the TxGraph about the Ref being destroyed. 3556 m_graph->UnlinkRef(m_index); 3557 m_graph = nullptr; 3558 } 3559 } 3560 3561 TxGraph::Ref::Ref(Ref&& other) noexcept 3562 { 3563 // Inform the TxGraph of other that its Ref is being moved. 3564 if (other.m_graph) other.m_graph->UpdateRef(other.m_index, *this); 3565 // Actually move the contents. 3566 std::swap(m_graph, other.m_graph); 3567 std::swap(m_index, other.m_index); 3568 } 3569 3570 std::unique_ptr<TxGraph> MakeTxGraph( 3571 unsigned max_cluster_count, 3572 uint64_t max_cluster_size, 3573 uint64_t acceptable_cost, 3574 const std::function<std::strong_ordering(const TxGraph::Ref&, const TxGraph::Ref&)>& fallback_order) noexcept 3575 { 3576 return std::make_unique<TxGraphImpl>( 3577 /*max_cluster_count=*/max_cluster_count, 3578 /*max_cluster_size=*/max_cluster_size, 3579 /*acceptable_cost=*/acceptable_cost, 3580 /*fallback_order=*/fallback_order); 3581 }