Branch data Line data Source code
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 : 1120589 : 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 : 6423779 : 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 : 0 : 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 : 531994622 : bool IsAcceptable() const noexcept
134 : : {
135 : 531994622 : return m_quality == QualityLevel::ACCEPTABLE || m_quality == QualityLevel::OPTIMAL;
136 : : }
137 : : /** Whether the linearization of this Cluster is topological. */
138 : 2499911 : bool IsTopological() const noexcept
139 : : {
140 : 2499911 : return m_quality != QualityLevel::NEEDS_FIX && m_quality != QualityLevel::NEEDS_SPLIT_FIX;
141 : : }
142 : : /** Whether the linearization of this Cluster is optimal. */
143 : 1768459 : bool IsOptimal() const noexcept
144 : : {
145 : 1768459 : 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 : 1923806 : bool IsOversized() const noexcept { return m_quality == QualityLevel::OVERSIZED_SINGLETON; }
151 : : /** Whether this cluster requires splitting. */
152 : 529859450 : bool NeedsSplitting() const noexcept
153 : : {
154 : 529859450 : 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 : 60209 : constexpr DepGraphIndex GetMinIntendedTxCount() const noexcept final { return MIN_INTENDED_TX_COUNT; }
277 : 284977 : constexpr DepGraphIndex GetMaxTxCount() const noexcept final { return MAX_TX_COUNT; }
278 [ - + ]: 27115 : DepGraphIndex GetDepGraphIndexRange() const noexcept final { return m_depgraph.PositionRange(); }
279 [ - + ]: 1360680 : LinearizationIndex GetTxCount() const noexcept final { return m_linearization.size(); }
280 : : uint64_t GetTotalTxSize() const noexcept final;
281 : 417380 : 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 : 59624 : 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 : 0 : 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 : 5437637 : explicit SingletonClusterImpl(uint64_t sequence) noexcept : Cluster(sequence) {}
331 : :
332 : : size_t TotalMemoryUsage() const noexcept final;
333 : 521922 : constexpr DepGraphIndex GetMinIntendedTxCount() const noexcept final { return MIN_INTENDED_TX_COUNT; }
334 : 1043605 : constexpr DepGraphIndex GetMaxTxCount() const noexcept final { return MAX_TX_COUNT; }
335 : 45240772 : LinearizationIndex GetTxCount() const noexcept final { return m_graph_index != NO_GRAPH_INDEX; }
336 : 1610573 : DepGraphIndex GetDepGraphIndexRange() const noexcept final { return GetTxCount(); }
337 [ + + ]: 3513227 : uint64_t GetTotalTxSize() const noexcept final { return GetTxCount() ? m_feerate.size : 0; }
338 [ - + - + ]: 718331 : 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 [ - + ]: 79729 : 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 : 7123971 : 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 : 4143401 : 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 : 6026191 : ChunkData(GraphIndex graph_index, LinearizationIndex chunk_count) noexcept :
476 : 6026191 : 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 : 49768249 : static std::strong_ordering CompareClusters(Cluster* a, Cluster* b) noexcept
481 : : {
482 : : // The nullptr pointer compares before everything else.
483 [ + + ]: 49768249 : if (a == nullptr || b == nullptr) {
484 [ + + + + ]: 36267 : return (a != nullptr) <=> (b != nullptr);
485 : : }
486 : : // If neither pointer is nullptr, compare the Clusters' sequence numbers.
487 [ + + - + : 49731982 : Assume(a == b || a->m_sequence != b->m_sequence);
- + ]
488 [ + + + + ]: 49731982 : return a->m_sequence <=> b->m_sequence;
489 : : }
490 : :
491 : : /** Compare two entries (which must both exist within the main graph). */
492 : 315807698 : std::strong_ordering CompareMainTransactions(GraphIndex a, GraphIndex b) const noexcept
493 : : {
494 [ + + ]: 315807698 : if (a == b) return std::strong_ordering::equal;
495 [ - + + - : 315803949 : Assume(a < m_entries.size() && b < m_entries.size());
- + - + ]
496 [ + + ]: 315803949 : const auto& entry_a = m_entries[a];
497 : 315803949 : const auto& entry_b = m_entries[b];
498 : : // Compare chunk feerates, and return result if it differs.
499 : 315803949 : auto feerate_cmp = FeeRateCompare(entry_b.m_main_chunk_feerate, entry_a.m_main_chunk_feerate);
500 [ + + ]: 315803949 : if (feerate_cmp < 0) return std::strong_ordering::less;
501 [ + + ]: 174702313 : 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 [ + + ]: 91681118 : if (entry_a.m_main_equal_feerate_chunk_prefix_size != entry_b.m_main_equal_feerate_chunk_prefix_size) {
507 [ + + ]: 15924021 : 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 : 75757097 : const auto& locator_a = entry_a.m_locator[0];
512 : 75757097 : const auto& locator_b = entry_b.m_locator[0];
513 [ - + ]: 75757097 : Assume(locator_a.IsPresent() && locator_b.IsPresent());
514 [ + + ]: 75757097 : if (locator_a.cluster != locator_b.cluster) {
515 : 53018152 : auto fallback_cmp = m_fallback_order(*m_entries[entry_a.m_main_max_chunk_fallback].m_ref,
516 : 53018152 : *m_entries[entry_b.m_main_max_chunk_fallback].m_ref);
517 [ + - ]: 53018152 : if (fallback_cmp != 0) return fallback_cmp;
518 : : // This shouldn't be reachable as m_fallback_order defines a strong ordering.
519 : 0 : Assume(false);
520 : 0 : return CompareClusters(locator_a.cluster, locator_b.cluster);
521 : : }
522 : : // Within a single chunk, sort by position within cluster linearization.
523 [ + - + + ]: 22738945 : 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 [ - + ]: 40313 : explicit ChunkOrder(const TxGraphImpl* graph) : m_graph(graph) {}
532 : :
533 : 57180083 : bool operator()(const ChunkData& a, const ChunkData& b) const noexcept
534 : : {
535 : 57180083 : 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 : 1137084 : void SetMissing() noexcept { cluster = nullptr; index = 0; }
589 : : /** Mark this Locator as removed (not allowed in level 0). */
590 : 1157701 : void SetRemoved() noexcept { cluster = nullptr; index = DepGraphIndex(-1); }
591 : : /** Mark this Locator as present, in the specified Cluster. */
592 : 32397547 : void SetPresent(Cluster* c, DepGraphIndex i) noexcept { cluster = c; index = i; }
593 : : /** Check if this Locator is missing. */
594 [ + + + + ]: 18278221 : bool IsMissing() const noexcept { return cluster == nullptr && index == 0; }
595 : : /** Check if this Locator is removed. */
596 [ + + - + : 1434978 : bool IsRemoved() const noexcept { return cluster == nullptr && index == DepGraphIndex(-1); }
+ + ]
597 : : /** Check if this Locator is present (in some Cluster). */
598 [ + + + - : 76478617 : bool IsPresent() const noexcept { return cluster != nullptr; }
- + ]
599 : : };
600 : :
601 : : /** Internal information about each transaction in a TxGraphImpl. */
602 : 4658903 : 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 : 40313 : 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 : 40313 : ) noexcept :
641 : 40313 : m_max_cluster_count(max_cluster_count),
642 : 40313 : m_max_cluster_size(max_cluster_size),
643 : 40313 : m_acceptable_cost(acceptable_cost),
644 : 40313 : m_fallback_order(fallback_order),
645 [ - + ]: 80626 : m_main_chunkindex(ChunkOrder(this))
646 : : {
647 [ - + ]: 40313 : Assume(max_cluster_count >= 1);
648 [ - + ]: 40313 : Assume(max_cluster_count <= MAX_CLUSTER_COUNT_LIMIT);
649 : 40313 : }
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 : 5368497 : 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 [ + - + - : 71146552 : 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 [ + + + + : 4326308 : 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 : 986142 : std::unique_ptr<GenericClusterImpl> CreateEmptyGenericCluster() noexcept
697 : : {
698 : 986142 : return std::make_unique<GenericClusterImpl>(m_next_sequence_counter++);
699 : : }
700 : : /** Create an empty SingletonClusterImpl object. */
701 : 5437637 : std::unique_ptr<SingletonClusterImpl> CreateEmptySingletonCluster() noexcept
702 : : {
703 : 5437637 : 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 : 5366378 : std::unique_ptr<Cluster> CreateEmptyCluster(DepGraphIndex tx_count) noexcept
708 : : {
709 [ + + ]: 5366378 : if (tx_count >= SingletonClusterImpl::MIN_INTENDED_TX_COUNT && tx_count <= SingletonClusterImpl::MAX_TX_COUNT) {
710 : 4785509 : return CreateEmptySingletonCluster();
711 : : }
712 [ + - ]: 580869 : if (tx_count >= GenericClusterImpl::MIN_INTENDED_TX_COUNT && tx_count <= GenericClusterImpl::MAX_TX_COUNT) {
713 [ - + ]: 580869 : return CreateEmptyGenericCluster();
714 : : }
715 : 0 : 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 : 0 : void UpdateRef(GraphIndex idx, Ref& new_location) noexcept final
723 : : {
724 [ # # ]: 0 : auto& entry = m_entries[idx];
725 [ # # ]: 0 : Assume(entry.m_ref != nullptr);
726 : 0 : entry.m_ref = &new_location;
727 : 0 : }
728 : :
729 : : /** Only called by Ref::~Ref to unlink Refs, and Ref's move assignment. */
730 : 4320374 : void UnlinkRef(GraphIndex idx) noexcept final
731 : : {
732 [ - + ]: 4320374 : auto& entry = m_entries[idx];
733 [ - + ]: 4320374 : Assume(entry.m_ref != nullptr);
734 [ + + + - : 4334511 : 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 [ + + ]: 4320374 : if (entry.m_locator[0].IsPresent()) {
738 : 1701058 : entry.m_locator[0].cluster->RemoveChunkData(*this);
739 : : }
740 : 4320374 : entry.m_ref = nullptr;
741 : : // Mark the transaction as to be removed in all levels where it explicitly or implicitly
742 : : // exists.
743 : 4320374 : bool exists_anywhere{false};
744 : 4320374 : bool exists{false};
745 [ + + ]: 8653714 : for (int level = 0; level <= GetTopLevel(); ++level) {
746 [ + + ]: 4333340 : if (entry.m_locator[level].IsPresent()) {
747 : : exists_anywhere = true;
748 : : exists = true;
749 [ + + ]: 2628023 : } else if (entry.m_locator[level].IsRemoved()) {
750 : : exists = false;
751 : : }
752 [ + + ]: 2626597 : if (exists) {
753 : 1711930 : auto& clusterset = GetClusterSet(level);
754 : 1711930 : clusterset.m_to_remove.push_back(idx);
755 : : // Force recomputation of grouping data.
756 [ + + ]: 1711930 : 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 [ + + + + ]: 6029746 : if (level == GetTopLevel() && clusterset.m_oversized == true) {
763 : 3850 : clusterset.m_oversized = std::nullopt;
764 : : }
765 : : }
766 : : }
767 : 4320374 : m_unlinked.push_back(idx);
768 [ + + ]: 4320374 : if (!exists_anywhere) Compact();
769 : 4320374 : }
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 : 4110205 : 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 : 685250539 : TxGraphImpl::ClusterSet& TxGraphImpl::GetClusterSet(int level) noexcept
836 : : {
837 [ + + ]: 685250539 : if (level == 0) return m_main_clusterset;
838 [ - + ]: 39480983 : Assume(level == 1);
839 [ - + ]: 39480983 : Assume(m_staging_clusterset.has_value());
840 : 39480983 : return *m_staging_clusterset;
841 : : }
842 : :
843 : 2070664 : const TxGraphImpl::ClusterSet& TxGraphImpl::GetClusterSet(int level) const noexcept
844 : : {
845 [ + + ]: 2070664 : if (level == 0) return m_main_clusterset;
846 [ - + ]: 1861536 : Assume(level == 1);
847 [ - + ]: 1861536 : Assume(m_staging_clusterset.has_value());
848 : 1861536 : 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 : 29627721 : void TxGraphImpl::ClearChunkData(Entry& entry) noexcept
882 : : {
883 [ + + ]: 29627721 : if (entry.m_main_chunkindex_iterator != m_main_chunkindex.end()) {
884 [ - + ]: 6100467 : 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 : 6100467 : m_main_chunkindex_discarded.emplace_back(m_main_chunkindex.extract(entry.m_main_chunkindex_iterator));
888 : 6100467 : entry.m_main_chunkindex_iterator = m_main_chunkindex.end();
889 : : }
890 : 29627721 : }
891 : :
892 : 6311584 : void TxGraphImpl::CreateChunkData(GraphIndex idx, LinearizationIndex chunk_count) noexcept
893 : : {
894 [ - + ]: 6311584 : 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 [ - + ]: 6311584 : Assume(entry.m_ref != nullptr);
898 [ + + ]: 6311584 : if (!m_main_chunkindex_discarded.empty()) {
899 : : // Reuse an discarded node handle.
900 : 285393 : auto& node = m_main_chunkindex_discarded.back().value();
901 : 285393 : node.m_graph_index = idx;
902 : 285393 : node.m_chunk_count = chunk_count;
903 : 285393 : auto insert_result = m_main_chunkindex.insert(std::move(m_main_chunkindex_discarded.back()));
904 [ - + ]: 285393 : Assume(insert_result.inserted);
905 : 285393 : entry.m_main_chunkindex_iterator = insert_result.position;
906 : 285393 : m_main_chunkindex_discarded.pop_back();
907 : 285393 : } else {
908 : : // Construct a new entry.
909 : 6026191 : auto emplace_result = m_main_chunkindex.emplace(idx, chunk_count);
910 [ - + ]: 6026191 : Assume(emplace_result.second);
911 : 6026191 : entry.m_main_chunkindex_iterator = emplace_result.first;
912 : : }
913 : 6311584 : }
914 : :
915 : 2864591 : size_t GenericClusterImpl::TotalMemoryUsage() const noexcept
916 : : {
917 : 2864591 : return // Dynamic memory allocated in this Cluster.
918 [ - + - + ]: 5729182 : memusage::DynamicUsage(m_mapping) + memusage::DynamicUsage(m_linearization) +
919 : : // Dynamic memory usage inside m_depgraph.
920 [ - + ]: 2864591 : m_depgraph.DynamicMemoryUsage() +
921 : : // Memory usage of the allocated Cluster itself.
922 : 2864591 : memusage::MallocUsage(sizeof(GenericClusterImpl)) +
923 : : // Memory usage of the ClusterSet::m_clusters entry.
924 : 2864591 : sizeof(std::unique_ptr<Cluster>);
925 : : }
926 : :
927 : 9821499 : size_t SingletonClusterImpl::TotalMemoryUsage() const noexcept
928 : : {
929 : 9821499 : return // Memory usage of the allocated SingletonClusterImpl itself.
930 : 9821499 : memusage::MallocUsage(sizeof(SingletonClusterImpl)) +
931 : : // Memory usage of the ClusterSet::m_clusters entry.
932 : 9821499 : sizeof(std::unique_ptr<Cluster>);
933 : : }
934 : :
935 : 406811 : uint64_t GenericClusterImpl::GetTotalTxSize() const noexcept
936 : : {
937 : 406811 : uint64_t ret{0};
938 [ + + ]: 6981550 : for (auto i : m_linearization) {
939 : 6574739 : ret += m_depgraph.FeeRate(i).size;
940 : : }
941 : 406811 : return ret;
942 : : }
943 : :
944 : 1238557 : DepGraphIndex GenericClusterImpl::AppendTransaction(GraphIndex graph_idx, FeePerWeight feerate) noexcept
945 : : {
946 [ - + ]: 1238557 : Assume(graph_idx != GraphIndex(-1));
947 : 1238557 : auto ret = m_depgraph.AddTransaction(feerate);
948 : 1238557 : m_mapping.push_back(graph_idx);
949 : 1238557 : m_linearization.push_back(ret);
950 : 1238557 : return ret;
951 : : }
952 : :
953 : 4785509 : DepGraphIndex SingletonClusterImpl::AppendTransaction(GraphIndex graph_idx, FeePerWeight feerate) noexcept
954 : : {
955 [ - + ]: 4785509 : Assume(!GetTxCount());
956 : 4785509 : m_graph_index = graph_idx;
957 : 4785509 : m_feerate = feerate;
958 : 4785509 : return 0;
959 : : }
960 : :
961 : 1238557 : void GenericClusterImpl::AddDependencies(SetType parents, DepGraphIndex child) noexcept
962 : : {
963 : 1238557 : m_depgraph.AddDependencies(parents, child);
964 : 1238557 : }
965 : :
966 : 126606 : void SingletonClusterImpl::AddDependencies(SetType parents, DepGraphIndex child) noexcept
967 : : {
968 : : // Singletons cannot have any dependencies.
969 [ - + ]: 126606 : Assume(child == 0);
970 [ - + - + ]: 126606 : Assume(parents == SetType{} || parents == SetType::Fill(0));
971 : 126606 : }
972 : :
973 : 27115 : void GenericClusterImpl::ExtractTransactions(const std::function<void (DepGraphIndex, GraphIndex, FeePerWeight)>& visit1_fn, const std::function<void (DepGraphIndex, GraphIndex, SetType)>& visit2_fn) noexcept
974 : : {
975 [ + + ]: 138521 : for (auto pos : m_linearization) {
976 : 111406 : visit1_fn(pos, m_mapping[pos], FeePerWeight::FromFeeFrac(m_depgraph.FeeRate(pos)));
977 : : }
978 [ + + ]: 138521 : for (auto pos : m_linearization) {
979 : 111406 : visit2_fn(pos, m_mapping[pos], m_depgraph.GetReducedParents(pos));
980 : : }
981 : : // Purge this Cluster, now that everything has been moved.
982 : 27115 : m_depgraph = DepGraph<SetType>{};
983 [ + - ]: 27115 : m_linearization.clear();
984 [ + - ]: 27115 : m_mapping.clear();
985 : 27115 : }
986 : :
987 : 1610573 : void SingletonClusterImpl::ExtractTransactions(const std::function<void (DepGraphIndex, GraphIndex, FeePerWeight)>& visit1_fn, const std::function<void (DepGraphIndex, GraphIndex, SetType)>& visit2_fn) noexcept
988 : : {
989 [ + - ]: 1610573 : if (GetTxCount()) {
990 : 1610573 : visit1_fn(0, m_graph_index, m_feerate);
991 : 1610573 : visit2_fn(0, m_graph_index, SetType{});
992 : 1610573 : m_graph_index = NO_GRAPH_INDEX;
993 : : }
994 : 1610573 : }
995 : :
996 : 173817 : int GenericClusterImpl::GetLevel(const TxGraphImpl& graph) const noexcept
997 : : {
998 : : // GetLevel() does not work for empty Clusters.
999 [ - + - - ]: 173817 : if (!Assume(!m_linearization.empty())) return -1;
1000 : :
1001 : : // Pick an arbitrary Entry that occurs in this Cluster.
1002 : 173817 : 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 [ + - ]: 249864 : for (int level = 0; level < MAX_LEVELS; ++level) {
1005 [ + + ]: 249864 : 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 : 0 : assert(false);
1010 : : return -1;
1011 : : }
1012 : :
1013 : 1579842 : int SingletonClusterImpl::GetLevel(const TxGraphImpl& graph) const noexcept
1014 : : {
1015 : : // GetLevel() does not work for empty Clusters.
1016 [ + - ]: 1579842 : if (!Assume(GetTxCount())) return -1;
1017 : :
1018 : : // Get the Entry in this Cluster.
1019 : 1579842 : 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 [ + - ]: 1800509 : for (int level = 0; level < MAX_LEVELS; ++level) {
1022 [ + + ]: 1800509 : 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 : 0 : assert(false);
1027 : : return -1;
1028 : : }
1029 : :
1030 : 1764433 : void TxGraphImpl::ClearLocator(int level, GraphIndex idx, bool oversized_tx) noexcept
1031 : : {
1032 : 1764433 : auto& entry = m_entries[idx];
1033 : 1764433 : auto& clusterset = GetClusterSet(level);
1034 [ - + ]: 1764433 : Assume(entry.m_locator[level].IsPresent());
1035 : : // Change the locator from Present to Missing or Removed.
1036 [ + + + + ]: 1764433 : if (level == 0 || !entry.m_locator[level - 1].IsPresent()) {
1037 : 606732 : entry.m_locator[level].SetMissing();
1038 : : } else {
1039 : 1157701 : entry.m_locator[level].SetRemoved();
1040 : 1157701 : clusterset.m_removed.push_back(idx);
1041 : : }
1042 : : // Update the transaction count.
1043 : 1764433 : --clusterset.m_txcount;
1044 : 1764433 : clusterset.m_txcount_oversized -= oversized_tx;
1045 : : // If clearing main, adjust the status of Locators of this transaction in staging, if it exists.
1046 [ + + + + ]: 1764433 : if (level == 0 && GetTopLevel() == 1) {
1047 [ + + ]: 399419 : if (entry.m_locator[1].IsRemoved()) {
1048 : 68432 : entry.m_locator[1].SetMissing();
1049 [ + + ]: 330987 : } else if (!entry.m_locator[1].IsPresent()) {
1050 : 6061 : --m_staging_clusterset->m_txcount;
1051 : 6061 : m_staging_clusterset->m_txcount_oversized -= oversized_tx;
1052 : : }
1053 : : }
1054 [ + + ]: 1764433 : if (level == 0) ClearChunkData(entry);
1055 : 1764433 : }
1056 : :
1057 : 1061873 : void GenericClusterImpl::RemoveChunkData(TxGraphImpl& graph) noexcept
1058 : : {
1059 [ + + ]: 11383832 : for (DepGraphIndex idx : m_linearization) {
1060 : 10321959 : auto& entry = graph.m_entries[m_mapping[idx]];
1061 : 10321959 : graph.ClearChunkData(entry);
1062 : : }
1063 : 1061873 : }
1064 : :
1065 : 639185 : void SingletonClusterImpl::RemoveChunkData(TxGraphImpl& graph) noexcept
1066 : : {
1067 [ + - ]: 639185 : if (GetTxCount() == 0) return;
1068 : 639185 : auto& entry = graph.m_entries[m_graph_index];
1069 : 639185 : graph.ClearChunkData(entry);
1070 : : }
1071 : :
1072 : 3448174 : void GenericClusterImpl::Updated(TxGraphImpl& graph, int level, bool rename) noexcept
1073 : : {
1074 : : // Update all the Locators for this Cluster's Entry objects.
1075 [ + + ]: 26746493 : for (DepGraphIndex idx : m_linearization) {
1076 [ + + ]: 23298319 : 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 [ + + ]: 23298319 : if (level == 0 && !rename) graph.ClearChunkData(entry);
1080 : 23298319 : 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 [ + + + + : 3448174 : if (level == 0 && (rename || IsAcceptable())) {
+ + ]
1091 [ - + ]: 1166213 : auto chunking = ChunkLinearizationInfo(m_depgraph, m_linearization);
1092 : 1166213 : 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 : 1166213 : FeeFrac equal_feerate_chunk_feerate;
1096 : : // Iterate over the chunks.
1097 [ - + + + ]: 5679046 : for (unsigned chunk_idx = 0; chunk_idx < chunking.size(); ++chunk_idx) {
1098 [ - + ]: 4512833 : auto& chunk = chunking[chunk_idx];
1099 [ - + ]: 4512833 : auto chunk_count = chunk.transactions.Count();
1100 [ - + ]: 4512833 : Assume(chunk_count > 0);
1101 : : // Update equal_feerate_chunk_feerate to include this chunk, starting over when the
1102 : : // feerate changed.
1103 [ + + ]: 4512833 : if (chunk.feerate << equal_feerate_chunk_feerate) {
1104 : 2136033 : 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 : 2376800 : equal_feerate_chunk_feerate += chunk.feerate;
1109 : : }
1110 : : // Determine the m_fallback_order maximum transaction in the chunk.
1111 [ + - ]: 4512833 : auto it = chunk.transactions.begin();
1112 : 4512833 : GraphIndex max_element = m_mapping[*it];
1113 : 4512833 : ++it;
1114 [ + + ]: 12215698 : while (it != chunk.transactions.end()) {
1115 : 3190032 : GraphIndex this_element = m_mapping[*it];
1116 [ + + ]: 3190032 : if (graph.m_fallback_order(*graph.m_entries[this_element].m_ref, *graph.m_entries[max_element].m_ref) > 0) {
1117 : 985203 : max_element = this_element;
1118 : : }
1119 : 3190032 : ++it;
1120 : : }
1121 : : // Iterate over the transactions in the linearization, which must match those in chunk.
1122 : 7702865 : while (true) {
1123 : 7702865 : DepGraphIndex idx = m_linearization[lin_idx];
1124 : 7702865 : GraphIndex graph_idx = m_mapping[idx];
1125 : 7702865 : auto& entry = graph.m_entries[graph_idx];
1126 : 7702865 : entry.m_main_lin_index = lin_idx++;
1127 : 7702865 : entry.m_main_chunk_feerate = FeePerWeight::FromFeeFrac(chunk.feerate);
1128 : 7702865 : entry.m_main_equal_feerate_chunk_prefix_size = equal_feerate_chunk_feerate.size;
1129 : 7702865 : entry.m_main_max_chunk_fallback = max_element;
1130 [ - + ]: 7702865 : Assume(chunk.transactions[idx]);
1131 : 7702865 : chunk.transactions.Reset(idx);
1132 [ + + ]: 7702865 : if (chunk.transactions.None()) {
1133 : : // Last transaction in the chunk.
1134 [ + + - + : 4512833 : 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 [ + + ]: 4512833 : if (!rename) graph.CreateChunkData(graph_idx, chunk_count);
1141 : 4512833 : break;
1142 : : }
1143 : : }
1144 : : }
1145 : 1166213 : }
1146 : 3448174 : }
1147 : :
1148 : 7379834 : void SingletonClusterImpl::Updated(TxGraphImpl& graph, int level, bool rename) noexcept
1149 : : {
1150 : : // Don't do anything if this is empty.
1151 [ + + ]: 7379834 : if (GetTxCount() == 0) return;
1152 : :
1153 [ + + ]: 7377249 : 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 [ + + ]: 7377249 : if (level == 0 && !rename) graph.ClearChunkData(entry);
1157 : 7377249 : 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 [ + + + + : 7377249 : if (level == 0 && (rename || IsAcceptable())) {
+ + ]
1161 : 2093791 : entry.m_main_lin_index = 0;
1162 : 2093791 : entry.m_main_chunk_feerate = m_feerate;
1163 : 2093791 : entry.m_main_equal_feerate_chunk_prefix_size = m_feerate.size;
1164 : 2093791 : 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 [ + + ]: 2093791 : if (!rename) graph.CreateChunkData(m_graph_index, LinearizationIndex(-1));
1168 : : }
1169 : : }
1170 : :
1171 : 202217 : void GenericClusterImpl::GetConflicts(const TxGraphImpl& graph, std::vector<Cluster*>& out) const noexcept
1172 : : {
1173 [ + + ]: 2445267 : for (auto i : m_linearization) {
1174 [ + + ]: 2243050 : 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 [ + + ]: 2243050 : if (entry.m_locator[0].IsPresent()) {
1178 : 2091475 : out.push_back(entry.m_locator[0].cluster);
1179 : : }
1180 : : }
1181 : 202217 : }
1182 : :
1183 : 2109972 : void SingletonClusterImpl::GetConflicts(const TxGraphImpl& graph, std::vector<Cluster*>& out) const noexcept
1184 : : {
1185 : : // Empty clusters have no conflicts.
1186 [ + + ]: 2109972 : if (GetTxCount() == 0) return;
1187 : :
1188 [ + + ]: 2107387 : 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 [ + + ]: 2107387 : if (entry.m_locator[0].IsPresent()) {
1192 : 114847 : out.push_back(entry.m_locator[0].cluster);
1193 : : }
1194 : : }
1195 : :
1196 : 1855860 : std::vector<Cluster*> TxGraphImpl::GetConflicts() const noexcept
1197 : : {
1198 [ - + ]: 1855860 : Assume(GetTopLevel() == 1);
1199 : 1855860 : auto& clusterset = GetClusterSet(1);
1200 : 1855860 : std::vector<Cluster*> ret;
1201 : : // All main Clusters containing transactions in m_removed (so (P,R) ones) are conflicts.
1202 [ + + ]: 3959685 : for (auto i : clusterset.m_removed) {
1203 [ + + ]: 2103825 : auto& entry = m_entries[i];
1204 [ + + ]: 2103825 : if (entry.m_locator[0].IsPresent()) {
1205 : 2101535 : 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 [ + + ]: 14846880 : for (int quality = 0; quality < int(QualityLevel::NONE); ++quality) {
1210 : 12991020 : auto& clusters = clusterset.m_clusters[quality];
1211 [ + + ]: 15303209 : for (const auto& cluster : clusters) {
1212 : 2312189 : cluster->GetConflicts(*this, ret);
1213 : : }
1214 : : }
1215 : : // Deduplicate the result (the same Cluster may appear multiple times).
1216 : 35764422 : std::sort(ret.begin(), ret.end(), [](Cluster* a, Cluster* b) noexcept { return CompareClusters(a, b) < 0; });
1217 : 1855860 : ret.erase(std::unique(ret.begin(), ret.end()), ret.end());
1218 : 1855860 : return ret;
1219 : : }
1220 : :
1221 : 405273 : Cluster* GenericClusterImpl::CopyToStaging(TxGraphImpl& graph) const noexcept
1222 : : {
1223 : : // Construct an empty Cluster.
1224 : 405273 : auto ret = graph.CreateEmptyGenericCluster();
1225 : 405273 : auto ptr = ret.get();
1226 : : // Copy depgraph, mapping, and linearization.
1227 : 405273 : ptr->m_depgraph = m_depgraph;
1228 : 405273 : ptr->m_mapping = m_mapping;
1229 : 405273 : ptr->m_linearization = m_linearization;
1230 : : // Insert the new Cluster into the graph.
1231 : 405273 : graph.InsertCluster(/*level=*/1, std::move(ret), m_quality);
1232 : : // Update its Locators.
1233 : 405273 : ptr->Updated(graph, /*level=*/1, /*rename=*/false);
1234 : : // Update memory usage.
1235 : 405273 : graph.GetClusterSet(/*level=*/1).m_cluster_usage += ptr->TotalMemoryUsage();
1236 [ - + ]: 405273 : return ptr;
1237 : 405273 : }
1238 : :
1239 : 652128 : Cluster* SingletonClusterImpl::CopyToStaging(TxGraphImpl& graph) const noexcept
1240 : : {
1241 : : // Construct an empty Cluster.
1242 : 652128 : auto ret = graph.CreateEmptySingletonCluster();
1243 : 652128 : auto ptr = ret.get();
1244 : : // Copy data.
1245 : 652128 : ptr->m_graph_index = m_graph_index;
1246 : 652128 : ptr->m_feerate = m_feerate;
1247 : : // Insert the new Cluster into the graph.
1248 : 652128 : graph.InsertCluster(/*level=*/1, std::move(ret), m_quality);
1249 : : // Update its Locators.
1250 : 652128 : ptr->Updated(graph, /*level=*/1, /*rename=*/false);
1251 : : // Update memory usage.
1252 : 652128 : graph.GetClusterSet(/*level=*/1).m_cluster_usage += ptr->TotalMemoryUsage();
1253 : 1304256 : return ptr;
1254 : 652128 : }
1255 : :
1256 : 418179 : 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 [ - + ]: 418179 : Assume(!to_remove.empty());
1260 : 418179 : SetType todo;
1261 : 418179 : graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage();
1262 : 1173806 : do {
1263 [ - + ]: 1173806 : GraphIndex idx = to_remove.front();
1264 [ - + - + ]: 1173806 : Assume(idx < graph.m_entries.size());
1265 [ + + ]: 1173806 : auto& entry = graph.m_entries[idx];
1266 : 1173806 : auto& locator = entry.m_locator[level];
1267 : : // Stop once we hit an entry that applies to another Cluster.
1268 [ + + ]: 1173806 : if (locator.cluster != this) break;
1269 : : // - Remember it in a set of to-remove DepGraphIndexes.
1270 : 858666 : 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 [ + + ]: 858666 : m_mapping[locator.index] = GraphIndex(-1);
1275 : : // - Remove its linearization index from the Entry (if in main).
1276 [ + + ]: 858666 : if (level == 0) {
1277 : 63106 : entry.m_main_lin_index = LinearizationIndex(-1);
1278 : : }
1279 : : // - Mark it as missing/removed in the Entry's locator.
1280 : 858666 : graph.ClearLocator(level, idx, m_quality == QualityLevel::OVERSIZED_SINGLETON);
1281 [ + + ]: 858666 : to_remove = to_remove.subspan(1);
1282 [ + + ]: 858666 : } while(!to_remove.empty());
1283 : :
1284 [ - + ]: 418179 : 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 : 418179 : m_depgraph.RemoveTransactions(todo);
1288 [ - + ]: 418179 : m_mapping.resize(m_depgraph.PositionRange());
1289 : :
1290 : : // Filter removed transactions out of m_linearization.
1291 : 418179 : m_linearization.erase(std::remove_if(m_linearization.begin(), m_linearization.end(),
1292 : 2393163 : [&](auto pos) { return todo[pos]; }),
1293 : 418179 : m_linearization.end());
1294 : :
1295 : 418179 : Compact();
1296 : 418179 : graph.GetClusterSet(level).m_cluster_usage += TotalMemoryUsage();
1297 [ + + ]: 418179 : auto new_quality = IsTopological() ? QualityLevel::NEEDS_SPLIT : QualityLevel::NEEDS_SPLIT_FIX;
1298 : 418179 : graph.SetClusterQuality(level, m_quality, m_setindex, new_quality);
1299 : 418179 : Updated(graph, /*level=*/level, /*rename=*/false);
1300 : 418179 : }
1301 : :
1302 : 515374 : 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 [ - + ]: 515374 : Assume(!to_remove.empty());
1306 [ - + ]: 515374 : Assume(GetTxCount());
1307 [ - + ]: 515374 : 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 : 520450 : do {
1311 [ + + ]: 520450 : to_remove = to_remove.subspan(1);
1312 [ + + + + : 945560 : } while (!to_remove.empty() && to_remove.front() == m_graph_index);
+ + ]
1313 : : // Clear this cluster.
1314 : 515374 : graph.ClearLocator(level, m_graph_index, m_quality == QualityLevel::OVERSIZED_SINGLETON);
1315 : 515374 : m_graph_index = NO_GRAPH_INDEX;
1316 : 515374 : 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 : 515374 : }
1320 : :
1321 : 37626 : void GenericClusterImpl::Clear(TxGraphImpl& graph, int level) noexcept
1322 : : {
1323 [ - + - + ]: 37626 : Assume(GetTxCount());
1324 : 37626 : graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage();
1325 [ + + ]: 394699 : for (auto i : m_linearization) {
1326 : 357073 : graph.ClearLocator(level, m_mapping[i], m_quality == QualityLevel::OVERSIZED_SINGLETON);
1327 : : }
1328 : 37626 : m_depgraph = {};
1329 [ + - ]: 37626 : m_linearization.clear();
1330 [ + - ]: 37626 : m_mapping.clear();
1331 : 37626 : }
1332 : :
1333 : 33320 : void SingletonClusterImpl::Clear(TxGraphImpl& graph, int level) noexcept
1334 : : {
1335 [ - + ]: 33320 : Assume(GetTxCount());
1336 : 33320 : graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage();
1337 : 33320 : graph.ClearLocator(level, m_graph_index, m_quality == QualityLevel::OVERSIZED_SINGLETON);
1338 : 33320 : m_graph_index = NO_GRAPH_INDEX;
1339 : 33320 : }
1340 : :
1341 : 35290 : void GenericClusterImpl::MoveToMain(TxGraphImpl& graph) noexcept
1342 : : {
1343 [ + + ]: 383243 : for (auto i : m_linearization) {
1344 : 347953 : GraphIndex idx = m_mapping[i];
1345 : 347953 : auto& entry = graph.m_entries[idx];
1346 : 347953 : entry.m_locator[1].SetMissing();
1347 : : }
1348 : 35290 : auto quality = m_quality;
1349 : : // Subtract memory usage from staging and add it to main.
1350 : 35290 : graph.GetClusterSet(/*level=*/1).m_cluster_usage -= TotalMemoryUsage();
1351 : 35290 : graph.GetClusterSet(/*level=*/0).m_cluster_usage += TotalMemoryUsage();
1352 : : // Remove cluster itself from staging and add it to main.
1353 : 35290 : auto cluster = graph.ExtractCluster(1, quality, m_setindex);
1354 : 35290 : graph.InsertCluster(/*level=*/0, std::move(cluster), quality);
1355 : 35290 : Updated(graph, /*level=*/0, /*rename=*/false);
1356 : 35290 : }
1357 : :
1358 : 1706636 : void SingletonClusterImpl::MoveToMain(TxGraphImpl& graph) noexcept
1359 : : {
1360 [ + + ]: 1706636 : if (GetTxCount()) {
1361 : 1704051 : auto& entry = graph.m_entries[m_graph_index];
1362 : 1704051 : entry.m_locator[1].SetMissing();
1363 : : }
1364 : 1706636 : auto quality = m_quality;
1365 : 1706636 : graph.GetClusterSet(/*level=*/1).m_cluster_usage -= TotalMemoryUsage();
1366 : 1706636 : auto cluster = graph.ExtractCluster(/*level=*/1, quality, m_setindex);
1367 : 1706636 : graph.InsertCluster(/*level=*/0, std::move(cluster), quality);
1368 : 1706636 : graph.GetClusterSet(/*level=*/0).m_cluster_usage += TotalMemoryUsage();
1369 : 1706636 : Updated(graph, /*level=*/0, /*rename=*/false);
1370 : 1706636 : }
1371 : :
1372 : 1223403 : void GenericClusterImpl::Compact() noexcept
1373 : : {
1374 : 1223403 : m_linearization.shrink_to_fit();
1375 : 1223403 : m_mapping.shrink_to_fit();
1376 : 1223403 : m_depgraph.Compact();
1377 : 1223403 : }
1378 : :
1379 : 126606 : void SingletonClusterImpl::Compact() noexcept
1380 : : {
1381 : : // Nothing to compact; SingletonClusterImpl is constant size.
1382 : 126606 : }
1383 : :
1384 : 841655 : void GenericClusterImpl::AppendChunkFeerates(std::vector<FeeFrac>& ret) const noexcept
1385 : : {
1386 [ - + ]: 841655 : auto chunk_feerates = ChunkLinearization(m_depgraph, m_linearization);
1387 [ - + - + ]: 841655 : ret.reserve(ret.size() + chunk_feerates.size());
1388 : 841655 : ret.insert(ret.end(), chunk_feerates.begin(), chunk_feerates.end());
1389 : 841655 : }
1390 : :
1391 : 1601706 : void SingletonClusterImpl::AppendChunkFeerates(std::vector<FeeFrac>& ret) const noexcept
1392 : : {
1393 [ + - ]: 1601706 : if (GetTxCount()) {
1394 : 1601706 : ret.push_back(m_feerate);
1395 : : }
1396 : 1601706 : }
1397 : :
1398 : 37987 : uint64_t GenericClusterImpl::AppendTrimData(std::vector<TrimTxData>& ret, std::vector<std::pair<GraphIndex, GraphIndex>>& deps) const noexcept
1399 : : {
1400 [ - + ]: 37987 : Assume(IsAcceptable());
1401 [ - + ]: 37987 : auto linchunking = ChunkLinearizationInfo(m_depgraph, m_linearization);
1402 : 37987 : LinearizationIndex pos{0};
1403 : 37987 : uint64_t size{0};
1404 : 37987 : auto prev_index = GraphIndex(-1);
1405 : : // Iterate over the chunks of this cluster's linearization.
1406 [ + + ]: 285958 : for (const auto& [chunk, chunk_feerate] : linchunking) {
1407 : : // Iterate over the transactions of that chunk, in linearization order.
1408 : 247971 : auto chunk_tx_count = chunk.Count();
1409 [ + + ]: 740223 : for (unsigned j = 0; j < chunk_tx_count; ++j) {
1410 : 492252 : auto cluster_idx = m_linearization[pos];
1411 : : // The transaction must appear in the chunk.
1412 [ - + ]: 492252 : Assume(chunk[cluster_idx]);
1413 : : // Construct a new element in ret.
1414 : 492252 : auto& entry = ret.emplace_back();
1415 [ + + ]: 492252 : entry.m_chunk_feerate = FeePerWeight::FromFeeFrac(chunk_feerate);
1416 [ + + ]: 492252 : 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 [ + + ]: 492252 : if (pos != 0) deps.emplace_back(prev_index, entry.m_index);
1420 : 492252 : prev_index = entry.m_index;
1421 : 492252 : entry.m_tx_size = m_depgraph.FeeRate(cluster_idx).size;
1422 : 492252 : size += entry.m_tx_size;
1423 : 492252 : ++pos;
1424 : : }
1425 : : }
1426 : 37987 : return size;
1427 : 37987 : }
1428 : :
1429 : 628337 : uint64_t SingletonClusterImpl::AppendTrimData(std::vector<TrimTxData>& ret, std::vector<std::pair<GraphIndex, GraphIndex>>& deps) const noexcept
1430 : : {
1431 [ + - ]: 628337 : if (!GetTxCount()) return 0;
1432 : 628337 : auto& entry = ret.emplace_back();
1433 : 628337 : entry.m_chunk_feerate = m_feerate;
1434 : 628337 : entry.m_index = m_graph_index;
1435 : 628337 : entry.m_tx_size = m_feerate.size;
1436 : 628337 : return m_feerate.size;
1437 : : }
1438 : :
1439 : 416816 : bool GenericClusterImpl::Split(TxGraphImpl& graph, int level) noexcept
1440 : : {
1441 : : // This function can only be called when the Cluster needs splitting.
1442 [ - + ]: 416816 : Assume(NeedsSplitting());
1443 : : // Determine the new quality the split-off Clusters will have.
1444 [ + + ]: 416816 : QualityLevel new_quality = IsTopological() ? QualityLevel::NEEDS_RELINEARIZE : QualityLevel::NEEDS_FIX;
1445 : : /** Which positions are still left in this Cluster. */
1446 : 416816 : 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 [ - + ]: 416816 : std::vector<std::pair<Cluster*, DepGraphIndex>> remap(m_depgraph.PositionRange());
1450 : 416816 : std::vector<Cluster*> new_clusters;
1451 : 416816 : bool first{true};
1452 : : // Iterate over the connected components of this Cluster's m_depgraph.
1453 [ + + ]: 610311 : while (todo.Any()) {
1454 : 212873 : auto component = m_depgraph.FindConnectedComponent(todo);
1455 [ + + ]: 212873 : auto component_size = component.Count();
1456 [ + + ]: 212873 : auto split_quality = component_size <= 1 ? QualityLevel::OPTIMAL : new_quality;
1457 [ + + + + : 316822 : 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 [ - + - + ]: 19378 : Assume(todo == m_depgraph.Positions());
1464 : 19378 : 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 : 19378 : Updated(graph, /*level=*/level, /*rename=*/false);
1468 : 19378 : return false;
1469 : : }
1470 : 193495 : first = false;
1471 : : // Construct a new Cluster to hold the found component.
1472 : 193495 : auto new_cluster = graph.CreateEmptyCluster(component_size);
1473 : 193495 : 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 [ + - + + ]: 1752153 : for (auto i : component) {
1477 : 1365163 : remap[i] = {new_cluster.get(), DepGraphIndex(-1)};
1478 : : }
1479 : 193495 : graph.InsertCluster(level, std::move(new_cluster), split_quality);
1480 : 193495 : todo -= component;
1481 : 193495 : }
1482 : : // We have to split the Cluster up. Remove accounting for the existing one first.
1483 : 397438 : graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage();
1484 : : // Redistribute the transactions.
1485 [ + + ]: 1762601 : for (auto i : m_linearization) {
1486 : : /** The cluster which transaction originally in position i is moved to. */
1487 : 1365163 : Cluster* new_cluster = remap[i].first;
1488 : : // Copy the transaction to the new cluster's depgraph, and remember the position.
1489 : 1365163 : remap[i].second = new_cluster->AppendTransaction(m_mapping[i], FeePerWeight::FromFeeFrac(m_depgraph.FeeRate(i)));
1490 : : }
1491 : : // Redistribute the dependencies.
1492 [ + + ]: 1762601 : for (auto i : m_linearization) {
1493 : : /** The cluster transaction in position i is moved to. */
1494 : 1365163 : Cluster* new_cluster = remap[i].first;
1495 : : // Copy its parents, translating positions.
1496 : 1365163 : SetType new_parents;
1497 [ + + + + ]: 3502019 : for (auto par : m_depgraph.GetReducedParents(i)) new_parents.Set(remap[par].second);
1498 : 1365163 : new_cluster->AddDependencies(new_parents, remap[i].second);
1499 : : }
1500 : : // Update all the Locators of moved transactions, and memory usage.
1501 [ + + ]: 590933 : for (Cluster* new_cluster : new_clusters) {
1502 : 193495 : new_cluster->Updated(graph, /*level=*/level, /*rename=*/false);
1503 : 193495 : new_cluster->Compact();
1504 : 193495 : graph.GetClusterSet(level).m_cluster_usage += new_cluster->TotalMemoryUsage();
1505 : : }
1506 : : // Wipe this Cluster, and return that it needs to be deleted.
1507 : 397438 : m_depgraph = DepGraph<SetType>{};
1508 [ + + ]: 397438 : m_mapping.clear();
1509 [ + + ]: 542342 : m_linearization.clear();
1510 : : return true;
1511 : 416816 : }
1512 : :
1513 : 503708 : bool SingletonClusterImpl::Split(TxGraphImpl& graph, int level) noexcept
1514 : : {
1515 [ - + ]: 503708 : Assume(NeedsSplitting());
1516 [ - + ]: 503708 : Assume(!GetTxCount());
1517 : 503708 : graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage();
1518 : 503708 : return true;
1519 : : }
1520 : :
1521 : 1637688 : 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 : 1637688 : std::vector<DepGraphIndex> remap(other.GetDepGraphIndexRange());
1525 : : // Iterate over all transactions in the other Cluster (the one being absorbed).
1526 : 1637688 : other.ExtractTransactions([&](DepGraphIndex pos, GraphIndex idx, FeePerWeight feerate) noexcept {
1527 : : // Copy the transaction into this Cluster, and remember its position.
1528 : 1721979 : 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 [ - + - + ]: 1721979 : Assume(new_pos == m_mapping.size());
1532 : 1721979 : remap[pos] = new_pos;
1533 : 1721979 : m_mapping.push_back(idx);
1534 : 1721979 : m_linearization.push_back(new_pos);
1535 : 3275376 : }, [&](DepGraphIndex pos, GraphIndex idx, SetType other_parents) noexcept {
1536 : : // Copy the transaction's dependencies, translating them using remap.
1537 : 1721979 : SetType parents;
1538 [ + + + + ]: 1878186 : for (auto par : other_parents) {
1539 : 85241 : parents.Set(remap[par]);
1540 : : }
1541 : 1721979 : 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 [ + + ]: 1721979 : auto& entry = graph.m_entries[idx];
1546 : : // Discard any potential ChunkData prior to modifying the Cluster (as that could
1547 : : // invalidate its ordering).
1548 [ + + ]: 1721979 : if (level == 0) graph.ClearChunkData(entry);
1549 : 1721979 : entry.m_locator[level].SetPresent(this, remap[pos]);
1550 : 1721979 : });
1551 : 1637688 : }
1552 : :
1553 : 0 : 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 : 0 : Assume(false);
1557 : 0 : }
1558 : :
1559 : 743312 : 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 [ + + + + : 6463898 : 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 : 743312 : auto it = to_apply.begin();
1565 [ + + ]: 1742415 : while (it != to_apply.end()) {
1566 : 999103 : auto& first_child = graph.m_entries[it->second].m_locator[level];
1567 : 999103 : 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 : 999103 : SetType parents;
1571 [ + + ]: 3022180 : while (it != to_apply.end()) {
1572 [ + - ]: 2278868 : auto& child = graph.m_entries[it->second].m_locator[level];
1573 : 2278868 : auto& parent = graph.m_entries[it->first].m_locator[level];
1574 [ + - - + : 2278868 : Assume(child.cluster == this && parent.cluster == this);
- + ]
1575 [ + + ]: 2278868 : if (child.index != child_idx) break;
1576 : 2023077 : parents.Set(parent.index);
1577 : 2023077 : ++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 : 999103 : 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 [ - + ]: 743312 : Assume(!NeedsSplitting());
1588 [ - + ]: 743312 : Assume(!IsOversized());
1589 : 743312 : graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::NEEDS_FIX);
1590 : :
1591 : : // Finally push the changes to graph.m_entries.
1592 : 743312 : Updated(graph, /*level=*/level, /*rename=*/false);
1593 : 743312 : }
1594 : :
1595 : 0 : void SingletonClusterImpl::ApplyDependencies(TxGraphImpl&, int, std::span<std::pair<GraphIndex, GraphIndex>>) noexcept
1596 : : {
1597 : : // Nothing can actually be applied.
1598 : 0 : Assume(false);
1599 : 0 : }
1600 : :
1601 : 80626 : 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 [ + + ]: 1929273 : for (auto& entry : m_entries) {
1606 [ + + ]: 1888960 : if (entry.m_ref != nullptr) {
1607 : 338529 : GetRefGraph(*entry.m_ref) = nullptr;
1608 : : }
1609 : : }
1610 : 120939 : }
1611 : :
1612 : 7738022 : std::unique_ptr<Cluster> TxGraphImpl::ExtractCluster(int level, QualityLevel quality, ClusterSetIndex setindex) noexcept
1613 : : {
1614 [ - + ]: 7738022 : Assume(quality != QualityLevel::NONE);
1615 : :
1616 : 7738022 : auto& clusterset = GetClusterSet(level);
1617 [ - + ]: 7738022 : auto& quality_clusters = clusterset.m_clusters[int(quality)];
1618 [ - + - + ]: 7738022 : Assume(setindex < quality_clusters.size());
1619 : :
1620 : : // Extract the Cluster-owning unique_ptr.
1621 [ - + ]: 7738022 : std::unique_ptr<Cluster> ret = std::move(quality_clusters[setindex]);
1622 [ - + ]: 7738022 : ret->m_quality = QualityLevel::NONE;
1623 : 7738022 : ret->m_setindex = ClusterSetIndex(-1);
1624 : :
1625 : : // Clean up space in quality_cluster.
1626 [ - + ]: 7738022 : auto max_setindex = quality_clusters.size() - 1;
1627 [ + + ]: 7738022 : if (setindex != max_setindex) {
1628 : : // If the cluster was not the last element of quality_clusters, move that to take its place.
1629 : 1870811 : quality_clusters.back()->m_setindex = setindex;
1630 : 1870811 : quality_clusters[setindex] = std::move(quality_clusters.back());
1631 : : }
1632 : : // The last element of quality_clusters is now unused; drop it.
1633 : 7738022 : quality_clusters.pop_back();
1634 : :
1635 : 7738022 : return ret;
1636 : : }
1637 : :
1638 : 11552021 : 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 [ - + ]: 11552021 : Assume(quality != QualityLevel::NONE);
1642 : : // The passed-in Cluster must not currently be in the TxGraphImpl.
1643 [ - + ]: 11552021 : Assume(cluster->m_quality == QualityLevel::NONE);
1644 : :
1645 : : // Append it at the end of the relevant TxGraphImpl::m_cluster.
1646 : 11552021 : auto& clusterset = GetClusterSet(level);
1647 [ - + ]: 11552021 : auto& quality_clusters = clusterset.m_clusters[int(quality)];
1648 [ - + ]: 11552021 : ClusterSetIndex ret = quality_clusters.size();
1649 : 11552021 : cluster->m_quality = quality;
1650 : 11552021 : cluster->m_setindex = ret;
1651 : 11552021 : quality_clusters.push_back(std::move(cluster));
1652 : 11552021 : return ret;
1653 : : }
1654 : :
1655 : 3389042 : void TxGraphImpl::SetClusterQuality(int level, QualityLevel old_quality, ClusterSetIndex old_index, QualityLevel new_quality) noexcept
1656 : : {
1657 [ - + ]: 3389042 : Assume(new_quality != QualityLevel::NONE);
1658 : :
1659 : : // Don't do anything if the quality did not change.
1660 [ + + ]: 3389042 : if (old_quality == new_quality) return;
1661 : : // Extract the cluster from where it currently resides.
1662 : 3386316 : auto cluster_ptr = ExtractCluster(level, old_quality, old_index);
1663 : : // And re-insert it where it belongs.
1664 : 3386316 : InsertCluster(level, std::move(cluster_ptr), new_quality);
1665 : 3386316 : }
1666 : :
1667 : 2609780 : void TxGraphImpl::DeleteCluster(Cluster& cluster, int level) noexcept
1668 : : {
1669 : : // Extract the cluster from where it currently resides.
1670 : 2609780 : auto cluster_ptr = ExtractCluster(level, cluster.m_quality, cluster.m_setindex);
1671 : : // And throw it away.
1672 [ + - ]: 2609780 : cluster_ptr.reset();
1673 : 2609780 : }
1674 : :
1675 : 46912870 : std::pair<Cluster*, int> TxGraphImpl::FindClusterAndLevel(GraphIndex idx, int level) const noexcept
1676 : : {
1677 [ + - - + : 46912870 : Assume(level >= 0 && level <= GetTopLevel());
- + ]
1678 : 46912870 : auto& entry = m_entries[idx];
1679 : : // Search the entry's locators from top to bottom.
1680 [ + + ]: 63830606 : 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 [ + + ]: 80557072 : if (entry.m_locator[l].IsMissing()) continue;
1684 : : // If the locator has the entry marked as explicitly removed, stop.
1685 [ + + ]: 46721600 : if (entry.m_locator[l].IsRemoved()) break;
1686 : : // Otherwise, we have found the topmost ClusterSet that contains this entry.
1687 : 46397851 : 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 : 515019 : return {nullptr, -1};
1691 : : }
1692 : :
1693 : 1680636 : Cluster* TxGraphImpl::PullIn(Cluster* cluster, int level) noexcept
1694 : : {
1695 [ - + ]: 1680636 : int to_level = GetTopLevel();
1696 [ - + ]: 1680636 : Assume(to_level == 1);
1697 [ - + ]: 1680636 : Assume(level <= to_level);
1698 : : // Copy the Cluster from main to staging, if it's not already there.
1699 [ + + ]: 1680636 : 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 : 1057401 : MakeAcceptable(*cluster, level);
1703 : 1057401 : cluster = cluster->CopyToStaging(*this);
1704 : : }
1705 : 1680636 : return cluster;
1706 : : }
1707 : :
1708 : 13993626 : void TxGraphImpl::ApplyRemovals(int up_to_level) noexcept
1709 : : {
1710 [ + - - + : 13993626 : Assume(up_to_level >= 0 && up_to_level <= GetTopLevel());
- + ]
1711 [ + + ]: 32558359 : for (int level = 0; level <= up_to_level; ++level) {
1712 : 18564733 : auto& clusterset = GetClusterSet(level);
1713 : 18564733 : auto& to_remove = clusterset.m_to_remove;
1714 : : // Skip if there is nothing to remove in this level.
1715 [ + + ]: 18564733 : if (to_remove.empty()) continue;
1716 : : // Pull in all Clusters that are not in staging.
1717 [ + + ]: 194292 : if (level == 1) {
1718 [ + + ]: 1318139 : for (GraphIndex index : to_remove) {
1719 [ + + ]: 1183024 : auto [cluster, cluster_level] = FindClusterAndLevel(index, level);
1720 [ + + ]: 1183024 : if (cluster != nullptr) PullIn(cluster, cluster_level);
1721 : : }
1722 : : }
1723 : : // Group the set of to-be-removed entries by Cluster::m_sequence.
1724 : 194292 : std::sort(to_remove.begin(), to_remove.end(), [&](GraphIndex a, GraphIndex b) noexcept {
1725 : 13038404 : Cluster* cluster_a = m_entries[a].m_locator[level].cluster;
1726 : 13038404 : Cluster* cluster_b = m_entries[b].m_locator[level].cluster;
1727 : 13038404 : return CompareClusters(cluster_a, cluster_b) < 0;
1728 : : });
1729 : : // Process per Cluster.
1730 [ - + ]: 194292 : std::span to_remove_span{to_remove};
1731 [ + + ]: 1135611 : while (!to_remove_span.empty()) {
1732 [ + + ]: 941319 : Cluster* cluster = m_entries[to_remove_span.front()].m_locator[level].cluster;
1733 [ + + ]: 941319 : 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 : 933553 : 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 : 7766 : to_remove_span = to_remove_span.subspan(1);
1741 : : }
1742 : : }
1743 [ + - ]: 18759025 : to_remove.clear();
1744 : : }
1745 : 13993626 : Compact();
1746 : 13993626 : }
1747 : :
1748 : 152951 : void TxGraphImpl::SwapIndexes(GraphIndex a, GraphIndex b, std::vector<Cluster*>& affected_main) noexcept
1749 : : {
1750 [ - + - + ]: 152951 : Assume(a < m_entries.size());
1751 [ - + - + ]: 152951 : Assume(b < m_entries.size());
1752 : : // Swap the Entry objects.
1753 : 152951 : std::swap(m_entries[a], m_entries[b]);
1754 : : // Iterate over both objects.
1755 [ + + ]: 458853 : for (int i = 0; i < 2; ++i) {
1756 [ + + ]: 305902 : GraphIndex idx = i ? b : a;
1757 [ + + ]: 305902 : Entry& entry = m_entries[idx];
1758 : : // Update linked Ref, if any exists.
1759 [ + + ]: 305902 : if (entry.m_ref) GetRefIndex(*entry.m_ref) = idx;
1760 : : // Update linked chunk index entries, if any exist.
1761 [ + + ]: 305902 : if (entry.m_main_chunkindex_iterator != m_main_chunkindex.end()) {
1762 : 116406 : entry.m_main_chunkindex_iterator->m_graph_index = idx;
1763 : : }
1764 : : // Update the locators for both levels.
1765 [ + + ]: 917706 : for (int level = 0; level < MAX_LEVELS; ++level) {
1766 : 611804 : Locator& locator = entry.m_locator[level];
1767 [ + + ]: 611804 : if (locator.IsPresent()) {
1768 : 139353 : locator.cluster->UpdateMapping(locator.index, idx);
1769 [ + + ]: 139353 : if (level == 0) affected_main.push_back(locator.cluster);
1770 : : }
1771 : : }
1772 : : }
1773 : 152951 : }
1774 : :
1775 : 22553357 : 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 [ + + ]: 22553357 : if (!m_main_clusterset.m_deps_to_add.empty()) return;
1780 [ + + ]: 21823010 : if (!m_main_clusterset.m_to_remove.empty()) return;
1781 [ - + ]: 21820391 : Assume(m_main_clusterset.m_removed.empty()); // non-staging m_removed is always empty
1782 [ + + ]: 21820391 : if (m_staging_clusterset.has_value()) {
1783 [ + + ]: 6068913 : if (!m_staging_clusterset->m_deps_to_add.empty()) return;
1784 [ + + ]: 2162448 : if (!m_staging_clusterset->m_to_remove.empty()) return;
1785 [ + + ]: 2152571 : if (!m_staging_clusterset->m_removed.empty()) return;
1786 : : }
1787 : :
1788 : : // Release memory used by discarded ChunkData index entries.
1789 : 17003743 : 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 : 17003743 : std::sort(m_unlinked.begin(), m_unlinked.end(), std::greater{});
1796 : :
1797 : 17003743 : std::vector<Cluster*> affected_main;
1798 : 17003743 : auto last = GraphIndex(-1);
1799 [ + + ]: 19773686 : 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 [ - + ]: 2769943 : Assume(idx != last);
1803 : 2769943 : last = idx;
1804 : :
1805 : : // Make sure the entry is unlinked.
1806 [ - + ]: 2769943 : Entry& entry = m_entries[idx];
1807 [ - + ]: 2769943 : Assume(entry.m_ref == nullptr);
1808 : : // Make sure the entry does not occur in the graph.
1809 [ + + ]: 8309829 : for (int level = 0; level < MAX_LEVELS; ++level) {
1810 [ - + ]: 5539886 : Assume(!entry.m_locator[level].IsPresent());
1811 : : }
1812 : :
1813 : : // Move the entry to the end.
1814 [ - + + + ]: 2769943 : 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 : 2769943 : 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 : 17003743 : std::sort(affected_main.begin(), affected_main.end());
1822 : 17003743 : affected_main.erase(std::unique(affected_main.begin(), affected_main.end()), affected_main.end());
1823 [ + + ]: 17096062 : for (Cluster* cluster : affected_main) {
1824 : 92319 : cluster->Updated(*this, /*level=*/0, /*rename=*/true);
1825 : : }
1826 [ + + ]: 19652863 : m_unlinked.clear();
1827 : 17003743 : }
1828 : :
1829 : 920524 : 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 : 920524 : ApplyRemovals(level);
1834 : 920524 : bool del = cluster.Split(*this, level);
1835 [ + + ]: 920524 : if (del) {
1836 : : // Cluster::Split reports whether the Cluster is to be deleted.
1837 : 901146 : DeleteCluster(cluster, level);
1838 : : }
1839 : 920524 : }
1840 : :
1841 : 9573135 : void TxGraphImpl::SplitAll(int up_to_level) noexcept
1842 : : {
1843 [ + - - + : 9573135 : Assume(up_to_level >= 0 && up_to_level <= GetTopLevel());
- + ]
1844 : : // Before splitting all Cluster, first make sure all removals are applied.
1845 : 9573135 : ApplyRemovals(up_to_level);
1846 [ + + ]: 20209641 : for (int level = 0; level <= up_to_level; ++level) {
1847 [ + + ]: 31909518 : for (auto quality : {QualityLevel::NEEDS_SPLIT_FIX, QualityLevel::NEEDS_SPLIT}) {
1848 : 21273012 : auto& queue = GetClusterSet(level).m_clusters[int(quality)];
1849 [ + + ]: 22193536 : while (!queue.empty()) {
1850 : 920524 : Split(*queue.back().get(), level);
1851 : : }
1852 : : }
1853 : : }
1854 : 9573135 : }
1855 : :
1856 : 291149512 : void TxGraphImpl::GroupClusters(int level) noexcept
1857 : : {
1858 : 291149512 : auto& clusterset = GetClusterSet(level);
1859 : : // If the groupings have been computed already, nothing is left to be done.
1860 [ + + ]: 291149512 : 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 : 1137639 : 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 : 1137639 : 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 : 1137639 : 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 [ + + ]: 3338649 : for (int level_iter = 0; level_iter <= level; ++level_iter) {
1880 [ + + ]: 2397419 : for (auto& cluster : GetClusterSet(level_iter).m_clusters[int(QualityLevel::OVERSIZED_SINGLETON)]) {
1881 : 196409 : auto graph_idx = cluster->GetClusterEntry(0);
1882 : 196409 : auto cur_cluster = FindCluster(graph_idx, level);
1883 [ + + ]: 196409 : if (cur_cluster == nullptr) continue;
1884 : 165930 : 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 [ - + ]: 1137639 : an_deps.reserve(clusterset.m_deps_to_add.size());
1891 [ + + ]: 5053052 : for (const auto& [par, chl] : clusterset.m_deps_to_add) {
1892 : 3915413 : auto par_cluster = FindCluster(par, level);
1893 : 3915413 : auto chl_cluster = FindCluster(chl, level);
1894 : : // Skip dependencies for which the parent or child transaction is removed.
1895 [ + + + + ]: 3915413 : if (par_cluster == nullptr || chl_cluster == nullptr) continue;
1896 : 3657446 : 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 [ + + ]: 3657446 : 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 : 3657446 : 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 [ + + + + : 41474278 : std::sort(an_clusters.begin(), an_clusters.end(), [](auto& a, auto& b) noexcept { return a.second < b.second; });
+ + + + +
+ + + + +
+ + + + +
+ - - +
+ ]
1906 : 1137639 : 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 [ + + + + : 16857333 : 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 : 1137639 : {
1913 : : /** Each PartitionData entry contains information about a single input Cluster. */
1914 : 1137639 : 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 : 1137639 : std::vector<PartitionData> partition_data;
1929 : :
1930 : : /** Given a Cluster, find its corresponding PartitionData. */
1931 : 6565018 : auto locate_fn = [&](uint64_t sequence) noexcept -> PartitionData* {
1932 : 5427379 : auto it = std::lower_bound(partition_data.begin(), partition_data.end(), sequence,
1933 [ + + ]: 21402003 : [](auto& a, uint64_t seq) noexcept { return a.sequence < seq; });
1934 [ - + ]: 5427379 : Assume(it != partition_data.end());
1935 [ - + ]: 5427379 : Assume(it->sequence == sequence);
1936 : 5427379 : return &*it;
1937 : 1137639 : };
1938 : :
1939 : : /** Given a PartitionData, find the root of the tree it is in (its representative). */
1940 : 8140261 : static constexpr auto find_root_fn = [](PartitionData* data) noexcept -> PartitionData* {
1941 [ + + + + ]: 10587600 : 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 : 3860308 : auto par = data->parent;
1945 : 3860308 : data->parent = par->parent;
1946 : 3860308 : data = par;
1947 : : }
1948 : 7002622 : return data;
1949 : : };
1950 : :
1951 : : /** Given two PartitionDatas, union the partitions they are in, and return their
1952 : : * representative. */
1953 : 4778559 : 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 [ + + ]: 7557170 : auto rep1 = find_root_fn(arg1);
1957 : 3640920 : auto rep2 = find_root_fn(arg2);
1958 [ + + ]: 3640920 : 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 [ + + ]: 2069556 : if (rep1->rank < rep2->rank) std::swap(rep1, rep2);
1962 : 2069556 : rep2->parent = rep1;
1963 : 2069556 : rep1->rank += (rep1->rank == rep2->rank);
1964 : 2069556 : return rep1;
1965 : : };
1966 : :
1967 : : // Start by initializing every Cluster as its own singleton partition.
1968 [ - + ]: 1137639 : partition_data.resize(an_clusters.size());
1969 [ - + + + ]: 4499341 : for (size_t i = 0; i < an_clusters.size(); ++i) {
1970 : 3361702 : partition_data[i].sequence = an_clusters[i].first->m_sequence;
1971 : 3361702 : partition_data[i].parent = &partition_data[i];
1972 : 3361702 : 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 : 1137639 : Cluster* last_chl_cluster{nullptr};
1978 : 1137639 : PartitionData* last_partition{nullptr};
1979 [ + + ]: 4795085 : for (const auto& [dep, _] : an_deps) {
1980 : 3657446 : auto [par, chl] = dep;
1981 : 3657446 : auto par_cluster = FindCluster(par, level);
1982 : 3657446 : auto chl_cluster = FindCluster(chl, level);
1983 [ - + ]: 3657446 : Assume(chl_cluster != nullptr && par_cluster != nullptr);
1984 : : // Nothing to do if parent and child are in the same Cluster.
1985 [ + + ]: 3657446 : if (par_cluster == chl_cluster) continue;
1986 [ - + ]: 3640920 : Assume(par != chl);
1987 [ + + ]: 3640920 : 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 : 1854461 : last_partition = union_fn(locate_fn(par_cluster->m_sequence), last_partition);
1992 : : } else {
1993 : 1786459 : last_chl_cluster = chl_cluster;
1994 : 1786459 : 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 : 1137639 : auto deps_it = an_deps.begin();
2001 [ - + + + ]: 4499341 : for (size_t i = 0; i < partition_data.size(); ++i) {
2002 : 3361702 : 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 : 3361702 : auto rep_seq = find_root_fn(&data)->sequence;
2006 : 3361702 : an_clusters[i].second = rep_seq;
2007 : : // Find all dependencies whose child Cluster is Cluster i, and annotate them with rep.
2008 [ + + ]: 7019148 : while (deps_it != an_deps.end()) {
2009 : 5775286 : auto [par, chl] = deps_it->first;
2010 : 5775286 : auto chl_cluster = FindCluster(chl, level);
2011 [ - + ]: 5775286 : Assume(chl_cluster != nullptr);
2012 [ + + ]: 5775286 : if (chl_cluster->m_sequence > data.sequence) break;
2013 : 3657446 : deps_it->second = rep_seq;
2014 : 3657446 : ++deps_it;
2015 : : }
2016 : : }
2017 : 1137639 : }
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 [ + + + + : 12630835 : std::sort(an_deps.begin(), an_deps.end(), [](auto& a, auto& b) noexcept { return a.second < b.second; });
+ + + + +
+ + + + +
+ + + + +
+ - - +
+ ]
2022 [ + + + + : 9325183 : 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 : 1137639 : clusterset.m_group_data = GroupData{};
2027 [ - + ]: 1137639 : clusterset.m_group_data->m_group_clusters.reserve(an_clusters.size());
2028 [ + + ]: 1137639 : clusterset.m_deps_to_add.clear();
2029 [ - + ]: 1137639 : clusterset.m_deps_to_add.reserve(an_deps.size());
2030 : 1137639 : clusterset.m_oversized = false;
2031 : 1137639 : auto an_deps_it = an_deps.begin();
2032 : 1137639 : auto an_clusters_it = an_clusters.begin();
2033 [ + + ]: 2429785 : while (an_clusters_it != an_clusters.end()) {
2034 : : // Process all clusters/dependencies belonging to the partition with representative rep.
2035 : 1292146 : auto rep = an_clusters_it->second;
2036 : : // Create and initialize a new GroupData entry for the partition.
2037 : 1292146 : auto& new_entry = clusterset.m_group_data->m_groups.emplace_back();
2038 [ - + ]: 1292146 : new_entry.m_cluster_offset = clusterset.m_group_data->m_group_clusters.size();
2039 : 1292146 : new_entry.m_cluster_count = 0;
2040 [ - + ]: 1292146 : new_entry.m_deps_offset = clusterset.m_deps_to_add.size();
2041 : 1292146 : new_entry.m_deps_count = 0;
2042 : 1292146 : uint32_t total_count{0};
2043 : 1292146 : uint64_t total_size{0};
2044 : : // Add all its clusters to it (copying those from an_clusters to m_group_clusters).
2045 [ + + + + ]: 4653848 : while (an_clusters_it != an_clusters.end() && an_clusters_it->second == rep) {
2046 : 3361702 : clusterset.m_group_data->m_group_clusters.push_back(an_clusters_it->first);
2047 : 3361702 : total_count += an_clusters_it->first->GetTxCount();
2048 : 3361702 : total_size += an_clusters_it->first->GetTotalTxSize();
2049 : 3361702 : ++an_clusters_it;
2050 : 3361702 : ++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 [ + + + + ]: 4949592 : while (an_deps_it != an_deps.end() && an_deps_it->second == rep) {
2054 : 3657446 : clusterset.m_deps_to_add.push_back(an_deps_it->first);
2055 : 3657446 : ++an_deps_it;
2056 : 3657446 : ++new_entry.m_deps_count;
2057 : : }
2058 : : // Detect oversizedness.
2059 [ + + + + ]: 1292146 : if (total_count > m_max_cluster_count || total_size > m_max_cluster_size) {
2060 : 467635 : clusterset.m_oversized = true;
2061 : : }
2062 : : }
2063 [ - + ]: 1137639 : Assume(an_deps_it == an_deps.end());
2064 [ - + ]: 1137639 : Assume(an_clusters_it == an_clusters.end());
2065 : 1137639 : Compact();
2066 : 1137639 : }
2067 : :
2068 : 743312 : void TxGraphImpl::Merge(std::span<Cluster*> to_merge, int level) noexcept
2069 : : {
2070 [ - + ]: 743312 : Assume(!to_merge.empty());
2071 : : // Nothing to do if a group consists of just a single Cluster.
2072 [ + + ]: 743312 : 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 : 738335 : size_t max_size_pos{0};
2078 : 738335 : DepGraphIndex max_size = to_merge[max_size_pos]->GetTxCount();
2079 : 738335 : GetClusterSet(level).m_cluster_usage -= to_merge[max_size_pos]->TotalMemoryUsage();
2080 : 738335 : DepGraphIndex total_size = max_size;
2081 [ + + ]: 1862043 : for (size_t i = 1; i < to_merge.size(); ++i) {
2082 : 1123708 : GetClusterSet(level).m_cluster_usage -= to_merge[i]->TotalMemoryUsage();
2083 : 1123708 : DepGraphIndex size = to_merge[i]->GetTxCount();
2084 : 1123708 : total_size += size;
2085 [ + + ]: 1123708 : if (size > max_size) {
2086 : 64372 : max_size_pos = i;
2087 : 64372 : max_size = size;
2088 : : }
2089 : : }
2090 [ + + ]: 738335 : if (max_size_pos != 0) std::swap(to_merge[0], to_merge[max_size_pos]);
2091 : :
2092 : 738335 : size_t start_idx = 1;
2093 : 738335 : Cluster* into_cluster = to_merge[0];
2094 [ + + ]: 738335 : 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 : 513980 : auto new_cluster = CreateEmptyCluster(total_size);
2099 : 513980 : into_cluster = new_cluster.get();
2100 : 513980 : InsertCluster(level, std::move(new_cluster), QualityLevel::OPTIMAL);
2101 : 513980 : start_idx = 0;
2102 : 513980 : }
2103 : :
2104 : : // Merge all further Clusters in the group into the result (first one, or new one), and delete
2105 : : // them.
2106 [ + + ]: 2376023 : for (size_t i = start_idx; i < to_merge.size(); ++i) {
2107 : 1637688 : into_cluster->Merge(*this, level, *to_merge[i]);
2108 : 1637688 : DeleteCluster(*to_merge[i], level);
2109 : : }
2110 : 738335 : into_cluster->Compact();
2111 : 738335 : GetClusterSet(level).m_cluster_usage += into_cluster->TotalMemoryUsage();
2112 : : }
2113 : :
2114 : 290165580 : void TxGraphImpl::ApplyDependencies(int level) noexcept
2115 : : {
2116 : 290165580 : auto& clusterset = GetClusterSet(level);
2117 : : // Do not bother computing groups if we already know the result will be oversized.
2118 [ + + ]: 290165580 : if (clusterset.m_oversized == true) return;
2119 : : // Compute the groups of to-be-merged Clusters (which also applies all removals, and splits).
2120 : 290116556 : GroupClusters(level);
2121 [ - + ]: 290116556 : Assume(clusterset.m_group_data.has_value());
2122 : : // Nothing to do if there are no dependencies to be added.
2123 [ + + ]: 290116556 : if (clusterset.m_deps_to_add.empty()) return;
2124 : : // Dependencies cannot be applied if it would result in oversized clusters.
2125 [ + - ]: 707088 : if (clusterset.m_oversized == true) return;
2126 : :
2127 : : // For each group of to-be-merged Clusters.
2128 [ + + ]: 1448475 : for (const auto& group_entry : clusterset.m_group_data->m_groups) {
2129 [ - + ]: 743312 : auto cluster_span = std::span{clusterset.m_group_data->m_group_clusters}
2130 [ + + ]: 743312 : .subspan(group_entry.m_cluster_offset, group_entry.m_cluster_count);
2131 : : // Pull in all the Clusters that contain dependencies.
2132 [ + + ]: 743312 : if (level == 1) {
2133 [ + + ]: 626459 : for (Cluster*& cluster : cluster_span) {
2134 : 504967 : cluster = PullIn(cluster, cluster->GetLevel(*this));
2135 : : }
2136 : : }
2137 : : // Invoke Merge() to merge them into a single Cluster.
2138 : 743312 : 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 [ - + ]: 743312 : auto deps_span = std::span{clusterset.m_deps_to_add}
2142 [ - + ]: 743312 : .subspan(group_entry.m_deps_offset, group_entry.m_deps_count);
2143 [ - + ]: 743312 : Assume(!deps_span.empty());
2144 [ - + ]: 743312 : const auto& loc = m_entries[deps_span[0].second].m_locator[level];
2145 [ - + ]: 743312 : Assume(loc.IsPresent());
2146 : 743312 : loc.cluster->ApplyDependencies(*this, level, deps_span);
2147 : : }
2148 : :
2149 : : // Wipe the list of to-be-added dependencies now that they are applied.
2150 [ + - ]: 705163 : clusterset.m_deps_to_add.clear();
2151 : 705163 : 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 : 1410326 : clusterset.m_group_data = GroupData{};
2155 : : }
2156 : :
2157 : 1238834 : 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 [ - + ]: 1238834 : Assume(!NeedsSplitting());
2161 : : // No work is required for Clusters which are already optimally linearized.
2162 [ - + ]: 1238834 : if (IsOptimal()) return {0, false};
2163 : : // Invoke the actual linearization algorithm (passing in the existing one).
2164 : 1238834 : uint64_t rng_seed = graph.m_rng.rand64();
2165 : 9809409 : const auto fallback_order = [&](DepGraphIndex a, DepGraphIndex b) noexcept {
2166 : 8570575 : const auto ref_a = graph.m_entries[m_mapping[a]].m_ref;
2167 : 8570575 : const auto ref_b = graph.m_entries[m_mapping[b]].m_ref;
2168 : 8570575 : return graph.m_fallback_order(*ref_a, *ref_b);
2169 : 1238834 : };
2170 [ - + ]: 1238834 : auto [linearization, optimal, cost] = Linearize(
2171 : 1238834 : /*depgraph=*/m_depgraph,
2172 : : /*max_cost=*/max_cost,
2173 : : /*rng_seed=*/rng_seed,
2174 : : /*fallback_order=*/fallback_order,
2175 : 2477668 : /*old_linearization=*/m_linearization,
2176 [ - + - + ]: 1238834 : /*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 [ - + ]: 1238834 : PostLinearize(m_depgraph, linearization);
2180 : : // Update the linearization.
2181 : 1238834 : m_linearization = std::move(linearization);
2182 : : // Update the Cluster's quality.
2183 : 1238834 : bool improved = false;
2184 [ + + ]: 1238834 : if (optimal) {
2185 : 1196026 : graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::OPTIMAL);
2186 : 1196026 : improved = true;
2187 [ + + + + ]: 42808 : } else if (max_cost >= graph.m_acceptable_cost && !IsAcceptable()) {
2188 : 34106 : graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::ACCEPTABLE);
2189 : 34106 : improved = true;
2190 [ + + ]: 8702 : } else if (!IsTopological()) {
2191 : 816 : graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::NEEDS_RELINEARIZE);
2192 : 816 : improved = true;
2193 : : }
2194 : : // Update the Entry objects.
2195 : 1238834 : Updated(graph, /*level=*/level, /*rename=*/false);
2196 : 1238834 : return {cost, improved};
2197 : 1238834 : }
2198 : :
2199 : 0 : 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 : 0 : assert(false);
2204 : : return {0, false};
2205 : : }
2206 : :
2207 : 526298208 : void TxGraphImpl::MakeAcceptable(Cluster& cluster, int level) noexcept
2208 : : {
2209 : : // Relinearize the Cluster if needed.
2210 [ + + + + : 526298208 : if (!cluster.NeedsSplitting() && !cluster.IsAcceptable() && !cluster.IsOversized()) {
+ + ]
2211 : 247376 : cluster.Relinearize(*this, level, m_acceptable_cost);
2212 : : }
2213 : 526298208 : }
2214 : :
2215 : 746793 : void TxGraphImpl::MakeAllAcceptable(int level) noexcept
2216 : : {
2217 : 746793 : ApplyDependencies(level);
2218 : 746793 : auto& clusterset = GetClusterSet(level);
2219 [ + - ]: 746793 : if (clusterset.m_oversized == true) return;
2220 [ + + ]: 2240379 : for (auto quality : {QualityLevel::NEEDS_FIX, QualityLevel::NEEDS_RELINEARIZE}) {
2221 : 1493586 : auto& queue = clusterset.m_clusters[int(quality)];
2222 [ + + ]: 1637722 : while (!queue.empty()) {
2223 : 144136 : MakeAcceptable(*queue.back().get(), level);
2224 : : }
2225 : : }
2226 : : }
2227 : :
2228 : 986142 : GenericClusterImpl::GenericClusterImpl(uint64_t sequence) noexcept : Cluster{sequence} {}
2229 : :
2230 : 4658903 : void TxGraphImpl::AddTransaction(Ref& arg, const FeePerWeight& feerate) noexcept
2231 : : {
2232 [ + + + - : 4677751 : Assume(m_main_chunkindex_observers == 0 || GetTopLevel() != 0);
- + ]
2233 [ - + ]: 4658903 : Assume(feerate.size > 0);
2234 [ - + ]: 4658903 : Assume(GetRefGraph(arg) == nullptr);
2235 : : // Construct a new Entry, and link it with the Ref.
2236 [ - + ]: 4658903 : auto idx = m_entries.size();
2237 : 4658903 : m_entries.emplace_back();
2238 : 4658903 : auto& entry = m_entries.back();
2239 : 4658903 : entry.m_main_chunkindex_iterator = m_main_chunkindex.end();
2240 : 4658903 : entry.m_ref = &arg;
2241 : 4658903 : GetRefGraph(arg) = this;
2242 : 4658903 : GetRefIndex(arg) = idx;
2243 : : // Construct a new singleton Cluster (which is necessarily optimally linearized).
2244 : 4658903 : bool oversized = uint64_t(feerate.size) > m_max_cluster_size;
2245 : 4658903 : auto cluster = CreateEmptyCluster(1);
2246 : 4658903 : cluster->AppendTransaction(idx, feerate);
2247 : 4658903 : auto cluster_ptr = cluster.get();
2248 : 4658903 : int level = GetTopLevel();
2249 : 4658903 : auto& clusterset = GetClusterSet(level);
2250 [ + + ]: 8208899 : InsertCluster(level, std::move(cluster), oversized ? QualityLevel::OVERSIZED_SINGLETON : QualityLevel::OPTIMAL);
2251 : 4658903 : cluster_ptr->Updated(*this, /*level=*/level, /*rename=*/false);
2252 : 4658903 : clusterset.m_cluster_usage += cluster_ptr->TotalMemoryUsage();
2253 : 4658903 : ++clusterset.m_txcount;
2254 : : // Deal with individually oversized transactions.
2255 [ + + ]: 4658903 : if (oversized) {
2256 : 1108907 : ++clusterset.m_txcount_oversized;
2257 : 1108907 : clusterset.m_oversized = true;
2258 [ + + ]: 1108907 : clusterset.m_group_data = std::nullopt;
2259 : : }
2260 : 4658903 : }
2261 : :
2262 : 1199342 : 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 [ + + ]: 1199342 : if (GetRefGraph(arg) == nullptr) return;
2267 [ - + ]: 1197291 : Assume(GetRefGraph(arg) == this);
2268 [ + + + - : 1198780 : 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 : 1197291 : int level = GetTopLevel();
2271 : 1197291 : auto cluster = FindCluster(GetRefIndex(arg), level);
2272 [ + + ]: 1197291 : if (cluster == nullptr) return;
2273 : : // Remember that the transaction is to be removed.
2274 : 1194084 : auto& clusterset = GetClusterSet(level);
2275 : 1194084 : clusterset.m_to_remove.push_back(GetRefIndex(arg));
2276 : : // Wipe m_group_data (as it will need to be recomputed).
2277 [ + + ]: 1194084 : clusterset.m_group_data.reset();
2278 [ + + ]: 1197223 : if (clusterset.m_oversized == true) clusterset.m_oversized = std::nullopt;
2279 : : }
2280 : :
2281 : 3074034 : 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 [ + + + + ]: 3074034 : if (GetRefGraph(parent) == nullptr || GetRefGraph(child) == nullptr) return;
2286 [ + - - + : 3071200 : Assume(GetRefGraph(parent) == this && GetRefGraph(child) == this);
- + ]
2287 [ + + + - : 3126773 : Assume(m_main_chunkindex_observers == 0 || GetTopLevel() != 0);
- + ]
2288 : : // Don't do anything if this is a dependency on self.
2289 [ + + ]: 3071200 : 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 : 3070189 : int level = GetTopLevel();
2293 : 3070189 : auto par_cluster = FindCluster(GetRefIndex(parent), level);
2294 [ + + ]: 3070189 : if (par_cluster == nullptr) return;
2295 : 3068261 : auto chl_cluster = FindCluster(GetRefIndex(child), level);
2296 [ + + ]: 3068261 : if (chl_cluster == nullptr) return;
2297 : : // Remember that this dependency is to be applied.
2298 : 3066776 : auto& clusterset = GetClusterSet(level);
2299 : 3066776 : clusterset.m_deps_to_add.emplace_back(GetRefIndex(parent), GetRefIndex(child));
2300 : : // Wipe m_group_data (as it will need to be recomputed).
2301 [ + + ]: 3066776 : clusterset.m_group_data.reset();
2302 [ + + ]: 4107358 : if (clusterset.m_oversized == false) clusterset.m_oversized = std::nullopt;
2303 : : }
2304 : :
2305 : 13503 : bool TxGraphImpl::Exists(const Ref& arg, Level level_select) noexcept
2306 : : {
2307 [ + + ]: 13503 : if (GetRefGraph(arg) == nullptr) return false;
2308 [ - + ]: 12205 : Assume(GetRefGraph(arg) == this);
2309 [ + + ]: 12205 : size_t level = GetSpecifiedLevel(level_select);
2310 : : // Make sure the transaction isn't scheduled for removal.
2311 : 12205 : ApplyRemovals(level);
2312 : 12205 : auto cluster = FindCluster(GetRefIndex(arg), level);
2313 : 12205 : return cluster != nullptr;
2314 : : }
2315 : :
2316 : 1732558 : 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 : 1732558 : SetType ancestors_union;
2320 : : // Process elements from the front of args, as long as they apply.
2321 [ + + ]: 3468615 : while (!args.empty()) {
2322 [ + + ]: 1736798 : if (args.front().first != this) break;
2323 : 1736057 : ancestors_union |= m_depgraph.Ancestors(args.front().second);
2324 : 1736057 : args = args.subspan(1);
2325 : : }
2326 [ - + ]: 1732558 : Assume(ancestors_union.Any());
2327 : : // Translate all ancestors (in arbitrary order) to Refs (if they have any), and return them.
2328 [ + - + + ]: 8087988 : for (auto idx : ancestors_union) {
2329 [ - + ]: 4622872 : const auto& entry = graph.m_entries[m_mapping[idx]];
2330 [ - + ]: 4622872 : Assume(entry.m_ref != nullptr);
2331 : 4622872 : output.push_back(entry.m_ref);
2332 : : }
2333 : 1732558 : }
2334 : :
2335 : 4350365 : void SingletonClusterImpl::GetAncestorRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept
2336 : : {
2337 [ - + ]: 4350365 : Assume(GetTxCount());
2338 [ + + ]: 8732589 : while (!args.empty()) {
2339 [ + + ]: 4397627 : if (args.front().first != this) break;
2340 : 4382224 : args = args.subspan(1);
2341 : : }
2342 [ - + ]: 4350365 : const auto& entry = graph.m_entries[m_graph_index];
2343 [ - + ]: 4350365 : Assume(entry.m_ref != nullptr);
2344 : 4350365 : output.push_back(entry.m_ref);
2345 : 4350365 : }
2346 : :
2347 : 2792538 : 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 : 2792538 : SetType descendants_union;
2351 : : // Process elements from the front of args, as long as they apply.
2352 [ + + ]: 5590429 : while (!args.empty()) {
2353 [ + + ]: 2799126 : if (args.front().first != this) break;
2354 : 2797891 : descendants_union |= m_depgraph.Descendants(args.front().second);
2355 : 2797891 : args = args.subspan(1);
2356 : : }
2357 [ - + ]: 2792538 : Assume(descendants_union.Any());
2358 : : // Translate all descendants (in arbitrary order) to Refs (if they have any), and return them.
2359 [ + - + + ]: 13485693 : for (auto idx : descendants_union) {
2360 [ - + ]: 7900617 : const auto& entry = graph.m_entries[m_mapping[idx]];
2361 [ - + ]: 7900617 : Assume(entry.m_ref != nullptr);
2362 : 7900617 : output.push_back(entry.m_ref);
2363 : : }
2364 : 2792538 : }
2365 : :
2366 : 2407815 : 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 : 2407815 : GetAncestorRefs(graph, args, output);
2370 : 2407815 : }
2371 : :
2372 : 607469 : 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 [ + + ]: 18929892 : for (auto& ref : range) {
2377 [ - + - + ]: 18322423 : Assume(start_pos < m_linearization.size());
2378 [ - + ]: 18322423 : const auto& entry = graph.m_entries[m_mapping[m_linearization[start_pos++]]];
2379 [ - + ]: 18322423 : Assume(entry.m_ref != nullptr);
2380 : 18322423 : ref = entry.m_ref;
2381 : : }
2382 : : // Return whether start_pos has advanced to the end of the Cluster.
2383 [ - + ]: 607469 : return start_pos == m_linearization.size();
2384 : : }
2385 : :
2386 : 471656 : bool SingletonClusterImpl::GetClusterRefs(TxGraphImpl& graph, std::span<TxGraph::Ref*> range, LinearizationIndex start_pos) noexcept
2387 : : {
2388 [ - + ]: 471656 : Assume(!range.empty());
2389 [ - + ]: 471656 : Assume(GetTxCount());
2390 [ - + ]: 471656 : Assume(start_pos == 0);
2391 [ - + ]: 471656 : const auto& entry = graph.m_entries[m_graph_index];
2392 [ - + ]: 471656 : Assume(entry.m_ref != nullptr);
2393 : 471656 : range[0] = entry.m_ref;
2394 : 471656 : return true;
2395 : : }
2396 : :
2397 : 261065 : FeePerWeight GenericClusterImpl::GetIndividualFeerate(DepGraphIndex idx) noexcept
2398 : : {
2399 : 261065 : return FeePerWeight::FromFeeFrac(m_depgraph.FeeRate(idx));
2400 : : }
2401 : :
2402 : 432707 : FeePerWeight SingletonClusterImpl::GetIndividualFeerate(DepGraphIndex idx) noexcept
2403 : : {
2404 [ - + ]: 432707 : Assume(GetTxCount());
2405 [ - + ]: 432707 : Assume(idx == 0);
2406 : 432707 : return m_feerate;
2407 : : }
2408 : :
2409 : 102609 : 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 [ + + ]: 1437846 : for (auto ci : m_linearization) {
2414 : 1335237 : GraphIndex idx = m_mapping[ci];
2415 : 1335237 : auto& entry = graph.m_entries[idx];
2416 : 1335237 : entry.m_locator[1].SetMissing();
2417 : : }
2418 : 102609 : }
2419 : :
2420 : 2557713 : void SingletonClusterImpl::MakeStagingTransactionsMissing(TxGraphImpl& graph) noexcept
2421 : : {
2422 [ + + ]: 2557713 : if (GetTxCount()) {
2423 : 2550800 : auto& entry = graph.m_entries[m_graph_index];
2424 : 2550800 : entry.m_locator[1].SetMissing();
2425 : : }
2426 : 2557713 : }
2427 : :
2428 : 3733735 : 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 [ + + ]: 3733735 : if (GetRefGraph(arg) == nullptr) return {};
2432 [ - + ]: 3732251 : Assume(GetRefGraph(arg) == this);
2433 : : // Apply all removals and dependencies, as the result might be incorrect otherwise.
2434 [ + + ]: 3732251 : size_t level = GetSpecifiedLevel(level_select);
2435 : 3732251 : ApplyDependencies(level);
2436 : : // Ancestry cannot be known if unapplied dependencies remain.
2437 [ - + ]: 3732251 : 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 [ + + ]: 3732251 : auto [cluster, cluster_level] = FindClusterAndLevel(GetRefIndex(arg), level);
2440 [ + + ]: 3732251 : if (cluster == nullptr) return {};
2441 : : // Dispatch to the Cluster.
2442 : 3664028 : std::pair<Cluster*, DepGraphIndex> match = {cluster, m_entries[GetRefIndex(arg)].m_locator[cluster_level].index};
2443 : 3664028 : auto matches = std::span(&match, 1);
2444 : 3664028 : std::vector<TxGraph::Ref*> ret;
2445 : 3664028 : cluster->GetAncestorRefs(*this, matches, ret);
2446 : 3664028 : return ret;
2447 : 3664028 : }
2448 : :
2449 : 5188229 : 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 [ + + ]: 5188229 : if (GetRefGraph(arg) == nullptr) return {};
2453 [ - + ]: 5186849 : Assume(GetRefGraph(arg) == this);
2454 : : // Apply all removals and dependencies, as the result might be incorrect otherwise.
2455 [ + + ]: 5186849 : size_t level = GetSpecifiedLevel(level_select);
2456 : 5186849 : ApplyDependencies(level);
2457 : : // Ancestry cannot be known if unapplied dependencies remain.
2458 [ - + ]: 5186849 : 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 [ + + ]: 5186849 : auto [cluster, cluster_level] = FindClusterAndLevel(GetRefIndex(arg), level);
2461 [ + + ]: 5186849 : if (cluster == nullptr) return {};
2462 : : // Dispatch to the Cluster.
2463 : 5185469 : std::pair<Cluster*, DepGraphIndex> match = {cluster, m_entries[GetRefIndex(arg)].m_locator[cluster_level].index};
2464 : 5185469 : auto matches = std::span(&match, 1);
2465 : 5185469 : std::vector<TxGraph::Ref*> ret;
2466 : 5185469 : cluster->GetDescendantRefs(*this, matches, ret);
2467 : 5185469 : return ret;
2468 : 5185469 : }
2469 : :
2470 : 6605 : 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 [ + + ]: 6605 : size_t level = GetSpecifiedLevel(level_select);
2474 : 6605 : ApplyDependencies(level);
2475 : : // Ancestry cannot be known if unapplied dependencies remain.
2476 [ - + ]: 6605 : Assume(GetClusterSet(level).m_deps_to_add.empty());
2477 : :
2478 : : // Translate args to matches.
2479 : 6605 : std::vector<std::pair<Cluster*, DepGraphIndex>> matches;
2480 : 6605 : matches.reserve(args.size());
2481 [ + + ]: 47769 : for (auto arg : args) {
2482 [ - + ]: 41164 : Assume(arg);
2483 : : // Skip empty Refs.
2484 [ + + ]: 41164 : if (GetRefGraph(*arg) == nullptr) continue;
2485 [ - + ]: 34138 : Assume(GetRefGraph(*arg) == this);
2486 : : // Find the Cluster the argument is in, and skip if none is found.
2487 [ + + ]: 34138 : auto [cluster, cluster_level] = FindClusterAndLevel(GetRefIndex(*arg), level);
2488 [ + + ]: 34138 : if (cluster == nullptr) continue;
2489 : : // Append to matches.
2490 : 31284 : matches.emplace_back(cluster, m_entries[GetRefIndex(*arg)].m_locator[cluster_level].index);
2491 : : }
2492 : : // Group by Cluster.
2493 : 78301 : std::sort(matches.begin(), matches.end(), [](auto& a, auto& b) noexcept { return CompareClusters(a.first, b.first) < 0; });
2494 : : // Dispatch to the Clusters.
2495 [ - + ]: 6605 : std::span match_span(matches);
2496 : 6605 : std::vector<TxGraph::Ref*> ret;
2497 [ + + ]: 17685 : while (!match_span.empty()) {
2498 : 11080 : match_span.front().first->GetAncestorRefs(*this, match_span, ret);
2499 : : }
2500 : 6605 : return ret;
2501 : 6605 : }
2502 : :
2503 : 19315 : 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 [ + + ]: 19315 : size_t level = GetSpecifiedLevel(level_select);
2507 : 19315 : ApplyDependencies(level);
2508 : : // Ancestry cannot be known if unapplied dependencies remain.
2509 [ - + ]: 19315 : Assume(GetClusterSet(level).m_deps_to_add.empty());
2510 : :
2511 : : // Translate args to matches.
2512 : 19315 : std::vector<std::pair<Cluster*, DepGraphIndex>> matches;
2513 : 19315 : matches.reserve(args.size());
2514 [ + + ]: 65586 : for (auto arg : args) {
2515 [ - + ]: 46271 : Assume(arg);
2516 : : // Skip empty Refs.
2517 [ + + ]: 46271 : if (GetRefGraph(*arg) == nullptr) continue;
2518 [ - + ]: 38606 : Assume(GetRefGraph(*arg) == this);
2519 : : // Find the Cluster the argument is in, and skip if none is found.
2520 [ + + ]: 38606 : auto [cluster, cluster_level] = FindClusterAndLevel(GetRefIndex(*arg), level);
2521 [ + + ]: 38606 : if (cluster == nullptr) continue;
2522 : : // Append to matches.
2523 : 35391 : matches.emplace_back(cluster, m_entries[GetRefIndex(*arg)].m_locator[cluster_level].index);
2524 : : }
2525 : : // Group by Cluster.
2526 : 113923 : std::sort(matches.begin(), matches.end(), [](auto& a, auto& b) noexcept { return CompareClusters(a.first, b.first) < 0; });
2527 : : // Dispatch to the Clusters.
2528 [ - + ]: 19315 : std::span match_span(matches);
2529 : 19315 : std::vector<TxGraph::Ref*> ret;
2530 [ + + ]: 34199 : while (!match_span.empty()) {
2531 : 14884 : match_span.front().first->GetDescendantRefs(*this, match_span, ret);
2532 : : }
2533 : 19315 : return ret;
2534 : 19315 : }
2535 : :
2536 : 939625 : 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 [ + + ]: 939625 : if (GetRefGraph(arg) == nullptr) return {};
2541 [ - + ]: 937103 : Assume(GetRefGraph(arg) == this);
2542 : : // Apply all removals and dependencies, as the result might be incorrect otherwise.
2543 [ + + ]: 937103 : size_t level = GetSpecifiedLevel(level_select);
2544 : 937103 : ApplyDependencies(level);
2545 : : // Cluster linearization cannot be known if unapplied dependencies remain.
2546 [ - + ]: 937103 : 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 [ + + ]: 937103 : auto [cluster, cluster_level] = FindClusterAndLevel(GetRefIndex(arg), level);
2549 [ + + ]: 937103 : if (cluster == nullptr) return {};
2550 : : // Make sure the Cluster has an acceptable quality level, and then dispatch to it.
2551 : 931980 : MakeAcceptable(*cluster, cluster_level);
2552 [ - + ]: 931980 : std::vector<TxGraph::Ref*> ret(cluster->GetTxCount());
2553 [ - + ]: 931980 : cluster->GetClusterRefs(*this, ret, 0);
2554 : 931980 : return ret;
2555 : 931980 : }
2556 : :
2557 : 46185 : TxGraph::GraphIndex TxGraphImpl::GetTransactionCount(Level level_select) noexcept
2558 : : {
2559 [ + + ]: 46185 : size_t level = GetSpecifiedLevel(level_select);
2560 : 46185 : ApplyRemovals(level);
2561 : 46185 : return GetClusterSet(level).m_txcount;
2562 : : }
2563 : :
2564 : 696818 : FeePerWeight TxGraphImpl::GetIndividualFeerate(const Ref& arg) noexcept
2565 : : {
2566 : : // Return the empty FeePerWeight if the passed Ref is empty.
2567 [ + + ]: 696818 : if (GetRefGraph(arg) == nullptr) return {};
2568 [ - + ]: 694935 : 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 : 722683 : Cluster* cluster{nullptr};
2572 : : int level;
2573 [ + + ]: 722683 : for (level = 0; level <= GetTopLevel(); ++level) {
2574 : : // Apply removals, so that we can correctly report FeePerWeight{} for non-existing
2575 : : // transactions.
2576 : 721520 : ApplyRemovals(level);
2577 [ + + ]: 721520 : if (m_entries[GetRefIndex(arg)].m_locator[level].IsPresent()) {
2578 : : cluster = m_entries[GetRefIndex(arg)].m_locator[level].cluster;
2579 : : break;
2580 : : }
2581 : : }
2582 [ + + ]: 694935 : if (cluster == nullptr) return {};
2583 : : // Dispatch to the Cluster.
2584 : 693772 : return cluster->GetIndividualFeerate(m_entries[GetRefIndex(arg)].m_locator[level].index);
2585 : : }
2586 : :
2587 : 6245909 : FeePerWeight TxGraphImpl::GetMainChunkFeerate(const Ref& arg) noexcept
2588 : : {
2589 : : // Return the empty FeePerWeight if the passed Ref is empty.
2590 [ + + ]: 6245909 : if (GetRefGraph(arg) == nullptr) return {};
2591 [ - + ]: 6244800 : Assume(GetRefGraph(arg) == this);
2592 : : // Apply all removals and dependencies, as the result might be inaccurate otherwise.
2593 : 6244800 : ApplyDependencies(/*level=*/0);
2594 : : // Chunk feerates cannot be accurately known if unapplied dependencies remain.
2595 [ - + ]: 6244800 : 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 [ + + ]: 6244800 : auto [cluster, cluster_level] = FindClusterAndLevel(GetRefIndex(arg), /*level=*/0);
2598 [ + + ]: 6244800 : if (cluster == nullptr) return {};
2599 : : // Make sure the Cluster has an acceptable quality level, and then return the transaction's
2600 : : // chunk feerate.
2601 : 6243137 : MakeAcceptable(*cluster, cluster_level);
2602 : 6243137 : const auto& entry = m_entries[GetRefIndex(arg)];
2603 : 6243137 : return entry.m_main_chunk_feerate;
2604 : : }
2605 : :
2606 : 4105915 : bool TxGraphImpl::IsOversized(Level level_select) noexcept
2607 : : {
2608 [ + + ]: 4105915 : size_t level = GetSpecifiedLevel(level_select);
2609 : 4105915 : auto& clusterset = GetClusterSet(level);
2610 [ + + ]: 4105915 : if (clusterset.m_oversized.has_value()) {
2611 : : // Return cached value if known.
2612 : 3097287 : return *clusterset.m_oversized;
2613 : : }
2614 : 1008628 : ApplyRemovals(level);
2615 [ + + ]: 1008628 : if (clusterset.m_txcount_oversized > 0) {
2616 : 1924 : 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 : 1006704 : GroupClusters(level);
2621 : : }
2622 [ - + ]: 1008628 : Assume(clusterset.m_oversized.has_value());
2623 : 1008628 : return *clusterset.m_oversized;
2624 : : }
2625 : :
2626 : 4103088 : void TxGraphImpl::StartStaging() noexcept
2627 : : {
2628 : : // Staging cannot already exist.
2629 [ - + ]: 4103088 : 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 : 4103088 : SplitAll(0);
2636 : 4103088 : ApplyDependencies(0);
2637 : : // Construct the staging ClusterSet.
2638 : 4103088 : 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 : 4103088 : m_staging_clusterset->m_txcount = m_main_clusterset.m_txcount;
2642 : 4103088 : m_staging_clusterset->m_txcount_oversized = m_main_clusterset.m_txcount_oversized;
2643 : 4103088 : m_staging_clusterset->m_deps_to_add = m_main_clusterset.m_deps_to_add;
2644 : 4103088 : m_staging_clusterset->m_group_data = m_main_clusterset.m_group_data;
2645 [ - + ]: 4103088 : m_staging_clusterset->m_oversized = m_main_clusterset.m_oversized;
2646 [ - + ]: 4103088 : Assume(m_staging_clusterset->m_oversized.has_value());
2647 : 4103088 : m_staging_clusterset->m_cluster_usage = 0;
2648 : 4103088 : }
2649 : :
2650 : 2388821 : void TxGraphImpl::AbortStaging() noexcept
2651 : : {
2652 : : // Staging must exist.
2653 [ - + ]: 2388821 : 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 [ + + ]: 3458619 : for (auto idx : m_staging_clusterset->m_removed) {
2657 : 1069798 : m_entries[idx].m_locator[1].SetMissing();
2658 : : }
2659 : : // Do the same with the non-removed transactions in staging Clusters.
2660 [ + + ]: 19110568 : for (int quality = 0; quality < int(QualityLevel::NONE); ++quality) {
2661 [ + + ]: 19382069 : for (auto& cluster : m_staging_clusterset->m_clusters[quality]) {
2662 : 2660322 : cluster->MakeStagingTransactionsMissing(*this);
2663 : : }
2664 : : }
2665 : : // Destroy the staging ClusterSet.
2666 : 2388821 : m_staging_clusterset.reset();
2667 : 2388821 : Compact();
2668 [ + + ]: 2388821 : 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 [ + + + + ]: 828 : 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 : 446 : m_main_clusterset.m_oversized = true;
2675 : : } else {
2676 [ + - ]: 382 : m_main_clusterset.m_oversized = std::nullopt;
2677 : : }
2678 : : }
2679 : 2388821 : }
2680 : :
2681 : 1711429 : void TxGraphImpl::CommitStaging() noexcept
2682 : : {
2683 : : // Staging must exist.
2684 [ - + ]: 1711429 : Assume(m_staging_clusterset.has_value());
2685 [ - + ]: 1711429 : 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 : 1711429 : 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 : 1711429 : auto conflicts = GetConflicts();
2693 [ + + ]: 1782375 : for (Cluster* conflict : conflicts) {
2694 : 70946 : conflict->Clear(*this, /*level=*/0);
2695 : 70946 : 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 [ + + ]: 1778715 : for (auto idx : m_staging_clusterset->m_removed) {
2700 : 67286 : m_entries[idx].m_locator[1].SetMissing();
2701 : : }
2702 : : // Then move all Clusters in staging to main.
2703 [ + + ]: 13691432 : for (int quality = 0; quality < int(QualityLevel::NONE); ++quality) {
2704 : 11980003 : auto& stage_sets = m_staging_clusterset->m_clusters[quality];
2705 [ + + ]: 13721929 : while (!stage_sets.empty()) {
2706 : 1741926 : stage_sets.back()->MoveToMain(*this);
2707 : : }
2708 : : }
2709 : : // Move all statistics, precomputed data, and to-be-applied removals and dependencies.
2710 : 1711429 : m_main_clusterset.m_deps_to_add = std::move(m_staging_clusterset->m_deps_to_add);
2711 : 1711429 : m_main_clusterset.m_to_remove = std::move(m_staging_clusterset->m_to_remove);
2712 : 1711429 : m_main_clusterset.m_group_data = std::move(m_staging_clusterset->m_group_data);
2713 : 1711429 : m_main_clusterset.m_oversized = std::move(m_staging_clusterset->m_oversized);
2714 : 1711429 : m_main_clusterset.m_txcount = std::move(m_staging_clusterset->m_txcount);
2715 : 1711429 : 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 : 1711429 : m_staging_clusterset.reset();
2718 : 1711429 : Compact();
2719 : 1711429 : }
2720 : :
2721 : 473946 : 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 [ - + ]: 473946 : Assume(m_depgraph.Positions()[idx]);
2725 : : // Bail out if the fee isn't actually being changed.
2726 [ + + ]: 473946 : 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 [ + - ]: 471757 : m_depgraph.FeeRate(idx).fee = fee;
2730 [ + - ]: 471757 : if (m_quality == QualityLevel::OVERSIZED_SINGLETON) {
2731 : : // Nothing to do.
2732 [ + + ]: 471757 : } else if (IsAcceptable()) {
2733 : 461851 : graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::NEEDS_RELINEARIZE);
2734 : : }
2735 : 471757 : Updated(graph, /*level=*/level, /*rename=*/false);
2736 : : }
2737 : :
2738 : 192504 : void SingletonClusterImpl::SetFee(TxGraphImpl& graph, int level, DepGraphIndex idx, int64_t fee) noexcept
2739 : : {
2740 [ - + ]: 192504 : Assume(GetTxCount());
2741 [ - + ]: 192504 : Assume(idx == 0);
2742 : 192504 : m_feerate.fee = fee;
2743 : 192504 : Updated(graph, /*level=*/level, /*rename=*/false);
2744 : 192504 : }
2745 : :
2746 : 668418 : void TxGraphImpl::SetTransactionFee(const Ref& ref, int64_t fee) noexcept
2747 : : {
2748 : : // Don't do anything if the passed Ref is empty.
2749 [ + + ]: 668418 : if (GetRefGraph(ref) == nullptr) return;
2750 [ - + ]: 666692 : Assume(GetRefGraph(ref) == this);
2751 [ - + ]: 666692 : Assume(m_main_chunkindex_observers == 0);
2752 : : // Find the entry, its locator, and inform its Cluster about the new feerate, if any.
2753 : 666692 : auto& entry = m_entries[GetRefIndex(ref)];
2754 [ + + ]: 2000076 : for (int level = 0; level < MAX_LEVELS; ++level) {
2755 : 1333384 : auto& locator = entry.m_locator[level];
2756 [ + + ]: 1333384 : if (locator.IsPresent()) {
2757 : 666450 : locator.cluster->SetFee(*this, level, locator.index, fee);
2758 : : }
2759 : : }
2760 : : }
2761 : :
2762 : 258627615 : std::strong_ordering TxGraphImpl::CompareMainOrder(const Ref& a, const Ref& b) noexcept
2763 : : {
2764 : : // The references must not be empty.
2765 [ - + ]: 258627615 : Assume(GetRefGraph(a) == this);
2766 [ - + ]: 258627615 : Assume(GetRefGraph(b) == this);
2767 : : // Apply dependencies in main.
2768 : 258627615 : ApplyDependencies(0);
2769 [ - + ]: 258627615 : Assume(m_main_clusterset.m_deps_to_add.empty());
2770 : : // Make both involved Clusters acceptable, so chunk feerates are relevant.
2771 [ - + ]: 258627615 : const auto& entry_a = m_entries[GetRefIndex(a)];
2772 : 258627615 : const auto& entry_b = m_entries[GetRefIndex(b)];
2773 : 258627615 : const auto& locator_a = entry_a.m_locator[0];
2774 : 258627615 : const auto& locator_b = entry_b.m_locator[0];
2775 [ - + ]: 258627615 : Assume(locator_a.IsPresent());
2776 [ - + ]: 258627615 : Assume(locator_b.IsPresent());
2777 : 258627615 : MakeAcceptable(*locator_a.cluster, /*level=*/0);
2778 : 258627615 : MakeAcceptable(*locator_b.cluster, /*level=*/0);
2779 : : // Invoke comparison logic.
2780 : 258627615 : return CompareMainTransactions(GetRefIndex(a), GetRefIndex(b));
2781 : : }
2782 : :
2783 : 501464 : TxGraph::GraphIndex TxGraphImpl::CountDistinctClusters(std::span<const Ref* const> refs, Level level_select) noexcept
2784 : : {
2785 [ + + ]: 501464 : size_t level = GetSpecifiedLevel(level_select);
2786 : 501464 : ApplyDependencies(level);
2787 : 501464 : auto& clusterset = GetClusterSet(level);
2788 [ - + ]: 501464 : Assume(clusterset.m_deps_to_add.empty());
2789 : : // Build a vector of Clusters that the specified Refs occur in.
2790 : 501464 : std::vector<Cluster*> clusters;
2791 : 501464 : clusters.reserve(refs.size());
2792 [ + + ]: 1646373 : for (const Ref* ref : refs) {
2793 [ - + ]: 1144909 : Assume(ref);
2794 [ + + ]: 1144909 : if (GetRefGraph(*ref) == nullptr) continue;
2795 [ - + ]: 1090740 : Assume(GetRefGraph(*ref) == this);
2796 : 1090740 : auto cluster = FindCluster(GetRefIndex(*ref), level);
2797 [ + + ]: 1090740 : if (cluster != nullptr) clusters.push_back(cluster);
2798 : : }
2799 : : // Count the number of distinct elements in clusters.
2800 : 3156443 : std::sort(clusters.begin(), clusters.end(), [](Cluster* a, Cluster* b) noexcept { return CompareClusters(a, b) < 0; });
2801 : 501464 : Cluster* last{nullptr};
2802 : 501464 : GraphIndex ret{0};
2803 [ + + ]: 1548777 : for (Cluster* cluster : clusters) {
2804 : 1047313 : ret += (cluster != last);
2805 : 1047313 : last = cluster;
2806 : : }
2807 : 501464 : return ret;
2808 : 501464 : }
2809 : :
2810 : 144431 : std::pair<std::vector<FeeFrac>, std::vector<FeeFrac>> TxGraphImpl::GetMainStagingDiagrams() noexcept
2811 : : {
2812 [ - + ]: 144431 : Assume(m_staging_clusterset.has_value());
2813 : 144431 : MakeAllAcceptable(0);
2814 [ - + ]: 144431 : Assume(m_main_clusterset.m_deps_to_add.empty()); // can only fail if main is oversized
2815 : 144431 : MakeAllAcceptable(1);
2816 [ - + ]: 144431 : 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 : 144431 : auto main_clusters = GetConflicts();
2820 : 144431 : std::vector<FeeFrac> main_feerates, staging_feerates;
2821 [ + + ]: 2017529 : for (Cluster* cluster : main_clusters) {
2822 : 1873098 : cluster->AppendChunkFeerates(main_feerates);
2823 : : }
2824 : : // Do the same for the Clusters in staging themselves.
2825 [ + + ]: 1155448 : for (int quality = 0; quality < int(QualityLevel::NONE); ++quality) {
2826 [ + + ]: 1581280 : for (const auto& cluster : m_staging_clusterset->m_clusters[quality]) {
2827 : 570263 : cluster->AppendChunkFeerates(staging_feerates);
2828 : : }
2829 : : }
2830 : : // Sort both by decreasing feerate to obtain diagrams, and return them.
2831 [ + + + + : 21964284 : std::sort(main_feerates.begin(), main_feerates.end(), [](auto& a, auto& b) { return a > b; });
+ + + + +
+ + + + +
+ + + + +
+ - - +
+ ]
2832 [ + + + + : 6746102 : std::sort(staging_feerates.begin(), staging_feerates.end(), [](auto& a, auto& b) { return a > b; });
+ + + + +
+ + + + +
+ + + + +
+ - - +
+ ]
2833 : 144431 : return std::make_pair(std::move(main_feerates), std::move(staging_feerates));
2834 : 144431 : }
2835 : :
2836 : 60622 : 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 [ - + - + : 60622 : assert(m_depgraph.PositionRange() == m_mapping.size());
- + ]
2840 : : // The linearization for this Cluster must contain every transaction once.
2841 [ - + - + ]: 60622 : assert(m_depgraph.TxCount() == m_linearization.size());
2842 : : // Unless a split is to be applied, the cluster cannot have any holes.
2843 [ + + ]: 60622 : if (!NeedsSplitting()) {
2844 [ - + ]: 60209 : assert(m_depgraph.Positions() == SetType::Fill(m_depgraph.TxCount()));
2845 : : }
2846 : :
2847 : : // Compute the chunking of m_linearization.
2848 [ - + ]: 60622 : auto linchunking = ChunkLinearizationInfo(m_depgraph, m_linearization);
2849 : 60622 : unsigned chunk_num{0};
2850 : :
2851 : : // Verify m_linearization.
2852 : 60622 : SetType m_done;
2853 : 60622 : LinearizationIndex linindex{0};
2854 : 60622 : DepGraphIndex chunk_pos{0}; //!< position within the current chunk
2855 [ - + ]: 60622 : assert(m_depgraph.IsAcyclic());
2856 [ + + ]: 60622 : if (m_linearization.empty()) return;
2857 : 60446 : FeeFrac equal_feerate_prefix = linchunking[chunk_num].feerate;
2858 [ + + ]: 477826 : for (auto lin_pos : m_linearization) {
2859 [ - + - + ]: 417380 : assert(lin_pos < m_mapping.size());
2860 : 417380 : const auto& entry = graph.m_entries[m_mapping[lin_pos]];
2861 : : // Check that the linearization is topological.
2862 : 417380 : m_done.Set(lin_pos);
2863 [ + + ]: 417380 : if (IsTopological()) {
2864 [ - + ]: 393512 : 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 [ - + ]: 417380 : assert(entry.m_locator[level].cluster == this);
2868 [ - + ]: 417380 : assert(entry.m_locator[level].index == lin_pos);
2869 : : // For main-level entries, check linearization position and chunk feerate.
2870 [ + + + + ]: 417380 : if (level == 0 && IsAcceptable()) {
2871 [ - + ]: 319937 : assert(entry.m_main_lin_index == linindex);
2872 : 319937 : ++linindex;
2873 [ + + ]: 319937 : if (!linchunking[chunk_num].transactions[lin_pos]) {
2874 : : // First transaction of a new chunk.
2875 : 150603 : ++chunk_num;
2876 [ - + - + ]: 150603 : assert(chunk_num < linchunking.size());
2877 : 150603 : chunk_pos = 0;
2878 [ + + ]: 150603 : if (linchunking[chunk_num].feerate << equal_feerate_prefix) {
2879 : 88450 : equal_feerate_prefix = linchunking[chunk_num].feerate;
2880 : : } else {
2881 [ - + ]: 62153 : assert(!(linchunking[chunk_num].feerate >> equal_feerate_prefix));
2882 : 62153 : equal_feerate_prefix += linchunking[chunk_num].feerate;
2883 : : }
2884 : : }
2885 [ + - ]: 319937 : assert(entry.m_main_chunk_feerate == linchunking[chunk_num].feerate);
2886 [ - + ]: 319937 : 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 : 319937 : ++chunk_pos;
2889 [ + + ]: 319937 : if (graph.m_main_clusterset.m_to_remove.empty()) {
2890 [ - + ]: 298363 : bool is_chunk_end = (chunk_pos == linchunking[chunk_num].transactions.Count());
2891 [ - + ]: 298363 : assert((entry.m_main_chunkindex_iterator != graph.m_main_chunkindex.end()) == is_chunk_end);
2892 [ + + ]: 298363 : if (is_chunk_end) {
2893 [ + + ]: 185866 : auto& chunk_data = *entry.m_main_chunkindex_iterator;
2894 [ + + + + ]: 185866 : if (m_done == m_depgraph.Positions() && chunk_pos == 1) {
2895 [ - + ]: 31080 : assert(chunk_data.m_chunk_count == LinearizationIndex(-1));
2896 : : } else {
2897 [ - + ]: 154786 : 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 [ - + ]: 319937 : assert(m_depgraph.IsConnected(linchunking[chunk_num].transactions));
2903 : : }
2904 : : }
2905 : : // Verify that each element of m_depgraph occurred in m_linearization.
2906 [ - + ]: 60446 : assert(m_done == m_depgraph.Positions());
2907 : 60622 : }
2908 : :
2909 : 529625 : void SingletonClusterImpl::SanityCheck(const TxGraphImpl& graph, int level) const
2910 : : {
2911 : : // All singletons are optimal, oversized, or need splitting.
2912 [ + + + + : 537328 : Assume(IsOptimal() || IsOversized() || NeedsSplitting());
+ - - + ]
2913 [ + + ]: 529625 : if (GetTxCount()) {
2914 [ - + ]: 521922 : 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 [ - + ]: 521922 : assert(entry.m_locator[level].cluster == this);
2917 [ - + ]: 521922 : assert(entry.m_locator[level].index == 0);
2918 : : // For main-level entries, check linearization position and chunk feerate.
2919 [ + + + + ]: 521922 : if (level == 0 && IsAcceptable()) {
2920 [ - + ]: 440263 : assert(entry.m_main_lin_index == 0);
2921 [ + - ]: 440263 : assert(entry.m_main_chunk_feerate == m_feerate);
2922 [ - + ]: 440263 : assert(entry.m_main_equal_feerate_chunk_prefix_size == m_feerate.size);
2923 [ + + ]: 440263 : if (graph.m_main_clusterset.m_to_remove.empty()) {
2924 [ - + ]: 393394 : assert(entry.m_main_chunkindex_iterator != graph.m_main_chunkindex.end());
2925 [ - + ]: 393394 : auto& chunk_data = *entry.m_main_chunkindex_iterator;
2926 [ - + ]: 393394 : assert(chunk_data.m_chunk_count == LinearizationIndex(-1));
2927 : : }
2928 : : }
2929 : : }
2930 : 529625 : }
2931 : :
2932 : 209128 : void TxGraphImpl::SanityCheck() const
2933 : : {
2934 : : /** Which GraphIndexes ought to occur in m_unlinked, based on m_entries. */
2935 : 209128 : std::set<GraphIndex> expected_unlinked;
2936 : : /** Which Clusters ought to occur in ClusterSet::m_clusters, based on m_entries. */
2937 [ + + ]: 1045640 : std::set<const Cluster*> expected_clusters[MAX_LEVELS];
2938 : : /** Which GraphIndexes ought to occur in ClusterSet::m_removed, based on m_entries. */
2939 [ + + ]: 1045640 : std::set<GraphIndex> expected_removed[MAX_LEVELS];
2940 : : /** Which Cluster::m_sequence values have been encountered. */
2941 : 209128 : std::set<uint64_t> sequences;
2942 : : /** Which GraphIndexes ought to occur in m_main_chunkindex, based on m_entries. */
2943 : 209128 : std::set<GraphIndex> expected_chunkindex;
2944 : : /** Whether compaction is possible in the current state. */
2945 : 209128 : bool compact_possible{true};
2946 : :
2947 : : // Go over all Entry objects in m_entries.
2948 [ - + + + ]: 1197147 : for (GraphIndex idx = 0; idx < m_entries.size(); ++idx) {
2949 [ + + ]: 988019 : const auto& entry = m_entries[idx];
2950 [ + + ]: 988019 : if (entry.m_ref == nullptr) {
2951 : : // Unlinked Entry must have indexes appear in m_unlinked.
2952 [ + - ]: 31775 : expected_unlinked.insert(idx);
2953 : : } else {
2954 : : // Every non-unlinked Entry must have a Ref that points back to it.
2955 [ - + ]: 956244 : assert(GetRefGraph(*entry.m_ref) == this);
2956 [ - + ]: 956244 : assert(GetRefIndex(*entry.m_ref) == idx);
2957 : : }
2958 [ + + ]: 988019 : if (entry.m_main_chunkindex_iterator != m_main_chunkindex.end()) {
2959 : : // Remember which entries we see a chunkindex entry for.
2960 [ - + ]: 632689 : assert(entry.m_locator[0].IsPresent());
2961 [ + - ]: 632689 : expected_chunkindex.insert(idx);
2962 : : }
2963 : : // Verify the Entry m_locators.
2964 : : bool was_present{false}, was_removed{false};
2965 [ + + ]: 2964057 : for (int level = 0; level < MAX_LEVELS; ++level) {
2966 : 1976038 : const auto& locator = entry.m_locator[level];
2967 : : // Every Locator must be in exactly one of these 3 states.
2968 [ + + + + : 5928114 : assert(locator.IsMissing() + locator.IsRemoved() + locator.IsPresent() == 1);
- + ]
2969 [ + + ]: 1976038 : if (locator.IsPresent()) {
2970 : : // Once removed, a transaction cannot be revived.
2971 [ - + ]: 939302 : assert(!was_removed);
2972 : : // Verify that the Cluster agrees with where the Locator claims the transaction is.
2973 [ - + ]: 939302 : assert(locator.cluster->GetClusterEntry(locator.index) == idx);
2974 : : // Remember that we expect said Cluster to appear in the ClusterSet::m_clusters.
2975 [ + - ]: 939302 : expected_clusters[level].insert(locator.cluster);
2976 : : was_present = true;
2977 [ + + ]: 2011571 : } else if (locator.IsRemoved()) {
2978 : : // Level 0 (main) cannot have IsRemoved locators (IsMissing there means non-existing).
2979 [ - + ]: 35533 : assert(level > 0);
2980 : : // A Locator can only be IsRemoved if it was IsPresent before, and only once.
2981 [ - + ]: 35533 : assert(was_present && !was_removed);
2982 : : // Remember that we expect this GraphIndex to occur in the ClusterSet::m_removed.
2983 [ + - ]: 35533 : expected_removed[level].insert(idx);
2984 : : was_removed = true;
2985 : : }
2986 : : }
2987 : : }
2988 : :
2989 : : // For all levels (0 = main, 1 = staged)...
2990 [ + + ]: 423932 : for (int level = 0; level <= GetTopLevel(); ++level) {
2991 : 214804 : assert(level < MAX_LEVELS);
2992 : 214804 : auto& clusterset = GetClusterSet(level);
2993 : 214804 : std::set<const Cluster*> actual_clusters;
2994 : 214804 : size_t recomputed_cluster_usage{0};
2995 : :
2996 : : // For all quality levels...
2997 [ + + ]: 1718432 : for (int qual = 0; qual < int(QualityLevel::NONE); ++qual) {
2998 : 1503628 : QualityLevel quality{qual};
2999 : 1503628 : const auto& quality_clusters = clusterset.m_clusters[qual];
3000 : : // ... for all clusters in them ...
3001 [ - + + + ]: 2093875 : for (ClusterSetIndex setindex = 0; setindex < quality_clusters.size(); ++setindex) {
3002 : 590247 : const auto& cluster = *quality_clusters[setindex];
3003 : : // The number of transactions in a Cluster cannot exceed m_max_cluster_count.
3004 [ - + ]: 590247 : 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 [ + + - + ]: 590247 : 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 [ + + - + ]: 590247 : assert(cluster.IsOversized() || cluster.GetTotalTxSize() <= m_max_cluster_size);
3013 : : // OVERSIZED clusters are singletons.
3014 [ + + - + ]: 590247 : assert(!cluster.IsOversized() || cluster.GetTxCount() == 1);
3015 : : // Transaction counts cannot exceed the Cluster implementation's maximum
3016 : : // supported transactions count.
3017 [ - + ]: 590247 : 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 [ + + ]: 590247 : if (!cluster.NeedsSplitting()) {
3021 [ - + ]: 582131 : assert(cluster.GetTxCount() >= cluster.GetMinIntendedTxCount());
3022 : : }
3023 : :
3024 : : // Check the sequence number.
3025 [ - + ]: 590247 : assert(cluster.m_sequence < m_next_sequence_counter);
3026 [ - + ]: 590247 : assert(!sequences.contains(cluster.m_sequence));
3027 [ + - ]: 590247 : 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 [ + + ]: 590247 : if (cluster.GetTxCount() != 0) {
3031 [ + - ]: 582368 : actual_clusters.insert(&cluster);
3032 : : }
3033 : : // Sanity check the cluster, according to the Cluster's internal rules.
3034 [ + - ]: 590247 : cluster.SanityCheck(*this, level);
3035 : : // Check that the cluster's quality and setindex matches its position in the quality list.
3036 [ - + ]: 590247 : assert(cluster.m_quality == quality);
3037 [ - + ]: 590247 : assert(cluster.m_setindex == setindex);
3038 : : // Count memory usage.
3039 : 590247 : recomputed_cluster_usage += cluster.TotalMemoryUsage();
3040 : : }
3041 : : }
3042 : :
3043 : : // Verify memory usage.
3044 [ - + ]: 214804 : assert(clusterset.m_cluster_usage == recomputed_cluster_usage);
3045 : :
3046 : : // Verify that all to-be-removed transactions have valid identifiers.
3047 [ + + ]: 238057 : for (GraphIndex idx : clusterset.m_to_remove) {
3048 [ - + - + ]: 23253 : 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 [ - + + + ]: 261058 : for (auto [par_idx, chl_idx] : clusterset.m_deps_to_add) {
3057 [ - + ]: 46254 : assert(par_idx != chl_idx);
3058 [ - + - + ]: 46254 : assert(par_idx < m_entries.size());
3059 [ - + ]: 46254 : assert(chl_idx < m_entries.size());
3060 : : }
3061 : :
3062 : : // Verify that the actually encountered clusters match the ones occurring in Entry vector.
3063 [ - + ]: 214804 : 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 [ + - ]: 214804 : std::set<GraphIndex> actual_removed(clusterset.m_removed.begin(), clusterset.m_removed.end());
3067 [ + + ]: 260767 : 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 : 45963 : actual_removed.erase(i);
3073 : 45963 : expected_removed[level].erase(i);
3074 : : }
3075 : :
3076 [ - + ]: 214804 : assert(actual_removed == expected_removed[level]);
3077 : :
3078 : : // If any GraphIndex entries remain in this ClusterSet, compact is not possible.
3079 [ + + ]: 214804 : if (!clusterset.m_deps_to_add.empty()) compact_possible = false;
3080 [ + + ]: 214804 : if (!clusterset.m_to_remove.empty()) compact_possible = false;
3081 [ + + ]: 214804 : 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 [ + + - + ]: 214804 : if (level < GetTopLevel()) assert(clusterset.m_oversized.has_value());
3086 : 214804 : }
3087 : :
3088 : : // Verify that the contents of m_unlinked matches what was expected based on the Entry vector.
3089 [ + - ]: 209128 : std::set<GraphIndex> actual_unlinked(m_unlinked.begin(), m_unlinked.end());
3090 [ - + ]: 209128 : 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 [ + + ]: 209128 : if (compact_possible) {
3095 [ - + ]: 200627 : assert(actual_unlinked.empty());
3096 : : }
3097 : :
3098 : : // Finally, check the chunk index.
3099 : 209128 : std::set<GraphIndex> actual_chunkindex;
3100 : 209128 : FeeFrac last_chunk_feerate;
3101 [ + + ]: 841817 : for (const auto& chunk : m_main_chunkindex) {
3102 : 632689 : GraphIndex idx = chunk.m_graph_index;
3103 [ + - ]: 632689 : actual_chunkindex.insert(idx);
3104 [ + + ]: 632689 : auto chunk_feerate = m_entries[idx].m_main_chunk_feerate;
3105 [ + + ]: 632689 : if (!last_chunk_feerate.IsEmpty()) {
3106 [ - + ]: 608406 : assert(FeeRateCompare(last_chunk_feerate, chunk_feerate) >= 0);
3107 : : }
3108 : 632689 : last_chunk_feerate = chunk_feerate;
3109 : : }
3110 [ - + ]: 209128 : assert(actual_chunkindex == expected_chunkindex);
3111 [ + + + + : 1463896 : }
- - - - ]
3112 : :
3113 : 1905753 : bool TxGraphImpl::DoWork(uint64_t max_cost) noexcept
3114 : : {
3115 : 1905753 : 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 [ + + ]: 7606639 : for (QualityLevel quality : {QualityLevel::NEEDS_FIX, QualityLevel::NEEDS_RELINEARIZE, QualityLevel::ACCEPTABLE}) {
3119 : : // First linearize staging, if it exists, then main.
3120 [ + + ]: 11444030 : for (int level = GetTopLevel(); level >= 0; --level) {
3121 : : // Do not modify main if it has any observers.
3122 [ + + + + ]: 5743144 : if (level == 0 && m_main_chunkindex_observers != 0) continue;
3123 : 5727289 : ApplyDependencies(level);
3124 : 5727289 : auto& clusterset = GetClusterSet(level);
3125 : : // Do not modify oversized levels.
3126 [ + - ]: 5761040 : if (clusterset.m_oversized == true) continue;
3127 : 5693538 : auto& queue = clusterset.m_clusters[int(quality)];
3128 [ + + ]: 6677110 : while (!queue.empty()) {
3129 [ + + ]: 993270 : 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 [ - + ]: 991458 : auto pos = m_rng.randrange<size_t>(queue.size());
3134 : 991458 : auto cost_now = max_cost - cost_done;
3135 [ + + ]: 991458 : 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 [ + + ]: 991947 : cost_now = std::min(cost_now, m_acceptable_cost);
3141 : : }
3142 [ + + ]: 991458 : auto [cost, improved] = queue[pos].get()->Relinearize(*this, level, cost_now);
3143 : 991458 : 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 [ + + ]: 991458 : 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 : 479095 : void BlockBuilderImpl::Next() noexcept
3160 : : {
3161 : : // Don't do anything if we're already done.
3162 [ + + ]: 479095 : if (m_cur_iter == m_graph->m_main_chunkindex.end()) return;
3163 : 482316 : while (true) {
3164 : : // Advance the pointer, and stop if we reach the end.
3165 [ + + ]: 482316 : ++m_cur_iter;
3166 : 482316 : m_cur_cluster = nullptr;
3167 [ + + ]: 482316 : if (m_cur_iter == m_graph->m_main_chunkindex.end()) break;
3168 : : // Find the cluster pointed to by m_cur_iter.
3169 : 459946 : const auto& chunk_data = *m_cur_iter;
3170 : 459946 : const auto& chunk_end_entry = m_graph->m_entries[chunk_data.m_graph_index];
3171 : 459946 : m_cur_cluster = chunk_end_entry.m_locator[0].cluster;
3172 : 459946 : m_known_end_of_cluster = false;
3173 : : // If we previously skipped a chunk from this cluster we cannot include more from it.
3174 [ + + ]: 459946 : if (!m_excluded_clusters.contains(m_cur_cluster->m_sequence)) break;
3175 : : }
3176 : : }
3177 : :
3178 : 879586 : std::optional<std::pair<std::vector<TxGraph::Ref*>, FeePerWeight>> BlockBuilderImpl::GetCurrentChunk() noexcept
3179 : : {
3180 : 879586 : std::optional<std::pair<std::vector<TxGraph::Ref*>, FeePerWeight>> ret;
3181 : : // Populate the return value if we are not done.
3182 [ + + ]: 879586 : if (m_cur_iter != m_graph->m_main_chunkindex.end()) {
3183 : 478114 : ret.emplace();
3184 [ + + ]: 478114 : const auto& chunk_data = *m_cur_iter;
3185 [ + + ]: 478114 : const auto& chunk_end_entry = m_graph->m_entries[chunk_data.m_graph_index];
3186 [ + + ]: 478114 : 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 : 336380 : ret->first.resize(1);
3190 [ - + ]: 336380 : Assume(chunk_end_entry.m_ref != nullptr);
3191 : 336380 : ret->first[0] = chunk_end_entry.m_ref;
3192 : 336380 : m_known_end_of_cluster = true;
3193 : : } else {
3194 [ - + ]: 141734 : Assume(m_cur_cluster);
3195 : 141734 : ret->first.resize(chunk_data.m_chunk_count);
3196 : 141734 : auto start_pos = chunk_end_entry.m_main_lin_index + 1 - chunk_data.m_chunk_count;
3197 [ - + ]: 141734 : 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 [ + + - + : 141734 : Assume(!m_known_end_of_cluster || chunk_data.m_chunk_count > 1);
- + ]
3201 : : }
3202 : 478114 : ret->second = chunk_end_entry.m_main_chunk_feerate;
3203 : : }
3204 : 879586 : return ret;
3205 : : }
3206 : :
3207 : 403845 : BlockBuilderImpl::BlockBuilderImpl(TxGraphImpl& graph) noexcept : m_graph(&graph)
3208 : : {
3209 : : // Make sure all clusters in main are up to date, and acceptable.
3210 : 403845 : m_graph->MakeAllAcceptable(0);
3211 : : // There cannot remain any inapplicable dependencies (only possible if main is oversized).
3212 [ - + ]: 403845 : 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 : 403845 : ++m_graph->m_main_chunkindex_observers;
3216 : : // Find the first chunk.
3217 [ + + ]: 403845 : m_cur_iter = m_graph->m_main_chunkindex.begin();
3218 : 403845 : m_cur_cluster = nullptr;
3219 [ + + ]: 403845 : if (m_cur_iter != m_graph->m_main_chunkindex.end()) {
3220 : : // Find the cluster pointed to by m_cur_iter.
3221 : 27679 : const auto& chunk_data = *m_cur_iter;
3222 : 27679 : const auto& chunk_end_entry = m_graph->m_entries[chunk_data.m_graph_index];
3223 : 27679 : m_cur_cluster = chunk_end_entry.m_locator[0].cluster;
3224 : : }
3225 : 403845 : }
3226 : :
3227 : 807690 : BlockBuilderImpl::~BlockBuilderImpl()
3228 : : {
3229 [ - + ]: 403845 : Assume(m_graph->m_main_chunkindex_observers > 0);
3230 : : // Permit modifications to the main graph again after destroying the BlockBuilderImpl.
3231 : 403845 : --m_graph->m_main_chunkindex_observers;
3232 : 807690 : }
3233 : :
3234 : 461478 : 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 : 461478 : Next();
3239 : 461478 : }
3240 : :
3241 : 17617 : 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 [ + + + + ]: 17617 : if (m_cur_cluster != nullptr && !m_known_end_of_cluster) {
3248 : 2613 : m_excluded_clusters.insert(m_cur_cluster->m_sequence);
3249 : : }
3250 : 17617 : Next();
3251 : 17617 : }
3252 : :
3253 : 403845 : std::unique_ptr<TxGraph::BlockBuilder> TxGraphImpl::GetBlockBuilder() noexcept
3254 : : {
3255 [ - + ]: 403845 : return std::make_unique<BlockBuilderImpl>(*this);
3256 : : }
3257 : :
3258 : 54086 : std::pair<std::vector<TxGraph::Ref*>, FeePerWeight> TxGraphImpl::GetWorstMainChunk() noexcept
3259 : : {
3260 : 54086 : std::pair<std::vector<Ref*>, FeePerWeight> ret;
3261 : : // Make sure all clusters in main are up to date, and acceptable.
3262 : 54086 : MakeAllAcceptable(0);
3263 [ - + ]: 54086 : Assume(m_main_clusterset.m_deps_to_add.empty());
3264 : : // If the graph is not empty, populate ret.
3265 [ + + ]: 54086 : if (!m_main_chunkindex.empty()) {
3266 [ + + ]: 51199 : const auto& chunk_data = *m_main_chunkindex.rbegin();
3267 [ + + ]: 51199 : const auto& chunk_end_entry = m_entries[chunk_data.m_graph_index];
3268 : 51199 : Cluster* cluster = chunk_end_entry.m_locator[0].cluster;
3269 [ + + ]: 51199 : if (chunk_data.m_chunk_count == LinearizationIndex(-1) || chunk_data.m_chunk_count == 1) {
3270 : : // Special case for singletons.
3271 : 45788 : ret.first.resize(1);
3272 [ - + ]: 45788 : Assume(chunk_end_entry.m_ref != nullptr);
3273 : 45788 : ret.first[0] = chunk_end_entry.m_ref;
3274 : : } else {
3275 : 5411 : ret.first.resize(chunk_data.m_chunk_count);
3276 : 5411 : auto start_pos = chunk_end_entry.m_main_lin_index + 1 - chunk_data.m_chunk_count;
3277 [ - + ]: 5411 : cluster->GetClusterRefs(*this, ret.first, start_pos);
3278 : 5411 : std::reverse(ret.first.begin(), ret.first.end());
3279 : : }
3280 : 51199 : ret.second = chunk_end_entry.m_main_chunk_feerate;
3281 : : }
3282 : 54086 : return ret;
3283 : : }
3284 : :
3285 : 57178 : std::vector<TxGraph::Ref*> TxGraphImpl::Trim() noexcept
3286 : : {
3287 [ + + ]: 57178 : int level = GetTopLevel();
3288 [ + + - + : 57178 : Assume(m_main_chunkindex_observers == 0 || level != 0);
- + ]
3289 : 57178 : std::vector<TxGraph::Ref*> ret;
3290 : :
3291 : : // Compute the groups of to-be-merged Clusters (which also applies all removals, and splits).
3292 : 57178 : auto& clusterset = GetClusterSet(level);
3293 [ + + ]: 57178 : if (clusterset.m_oversized == false) return ret;
3294 : 26252 : GroupClusters(level);
3295 [ - + ]: 26252 : Assume(clusterset.m_group_data.has_value());
3296 : : // Nothing to do if not oversized.
3297 [ - + ]: 26252 : Assume(clusterset.m_oversized.has_value());
3298 [ + - ]: 26252 : 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 : 23360 : std::vector<std::pair<GraphIndex, GraphIndex>> deps_by_parent;
3323 : : /** Same, but sorted by child. */
3324 : 23360 : 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 : 23360 : 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 : 23360 : std::vector<std::vector<TrimTxData>::iterator> trim_heap;
3332 : : /** The list of representatives of the partitions a given transaction depends on. */
3333 : 23360 : std::vector<TrimTxData*> current_deps;
3334 : :
3335 : : /** Function to define the ordering of trim_heap. */
3336 : 1862428 : 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 : 1839068 : 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 : 2068342 : static constexpr auto find_fn = [](TrimTxData* arg) noexcept {
3346 [ + + - + ]: 3093525 : 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 : 1048543 : auto par = arg->m_uf_parent;
3350 : 1048543 : arg->m_uf_parent = par->m_uf_parent;
3351 : 1048543 : arg = par;
3352 : : }
3353 : 2044982 : return arg;
3354 : : };
3355 : :
3356 : : /** Given two TrimTxData entries, union the partitions they are in, and return the
3357 : : * representative. */
3358 : 805742 : static constexpr auto union_fn = [](TrimTxData* arg1, TrimTxData* arg2) noexcept {
3359 : : // Replace arg1 and arg2 by their representatives.
3360 [ - + ]: 1564764 : auto rep1 = find_fn(arg1);
3361 : 782382 : 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 [ + - ]: 782382 : 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 [ + + ]: 782382 : if (rep1->m_uf_count < rep2->m_uf_count) std::swap(rep1, rep2);
3368 : 782382 : 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 : 782382 : rep1->m_uf_size += rep2->m_uf_size;
3372 : 782382 : rep1->m_uf_count += rep2->m_uf_count;
3373 : 782382 : return rep1;
3374 : : };
3375 : :
3376 : : /** Get iterator to TrimTxData entry for a given index. */
3377 : 2610743 : auto locate_fn = [&](GraphIndex index) noexcept {
3378 : 2587383 : auto it = std::lower_bound(trim_data.begin(), trim_data.end(), index, [](TrimTxData& elem, GraphIndex idx) noexcept {
3379 [ + + ]: 14910311 : return elem.m_index < idx;
3380 : : });
3381 [ + - - + : 2587383 : Assume(it != trim_data.end() && it->m_index == index);
- + ]
3382 : 2587383 : return it;
3383 : 23360 : };
3384 : :
3385 : : // For each group of to-be-merged Clusters.
3386 [ + + ]: 120453 : for (const auto& group_data : clusterset.m_group_data->m_groups) {
3387 [ + + ]: 97093 : trim_data.clear();
3388 [ - + ]: 97093 : trim_heap.clear();
3389 [ + + ]: 97093 : deps_by_child.clear();
3390 [ + + ]: 97093 : deps_by_parent.clear();
3391 : :
3392 : : // Gather trim data and implicit dependency data from all involved Clusters.
3393 [ - + ]: 97093 : auto cluster_span = std::span{clusterset.m_group_data->m_group_clusters}
3394 : 97093 : .subspan(group_data.m_cluster_offset, group_data.m_cluster_count);
3395 : 97093 : uint64_t size{0};
3396 [ + + ]: 763417 : for (Cluster* cluster : cluster_span) {
3397 : 666324 : MakeAcceptable(*cluster, cluster->GetLevel(*this));
3398 : 666324 : 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 [ - + + + : 97093 : 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 [ + + + + : 6343507 : 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 : 77023 : deps_by_child.insert(deps_by_child.end(),
3409 : 77023 : clusterset.m_deps_to_add.begin() + group_data.m_deps_offset,
3410 : 77023 : 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 [ + + + + : 9745578 : 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 : 77023 : auto deps_it = deps_by_child.begin();
3419 [ + + ]: 1100574 : for (auto trim_it = trim_data.begin(); trim_it != trim_data.end(); ++trim_it) {
3420 : 1023551 : trim_it->m_parent_offset = deps_it - deps_by_child.begin();
3421 : 1023551 : trim_it->m_deps_left = 0;
3422 [ + + + + ]: 2472829 : while (deps_it != deps_by_child.end() && deps_it->second == trim_it->m_index) {
3423 : 1449278 : ++trim_it->m_deps_left;
3424 : 1449278 : ++deps_it;
3425 : : }
3426 : 1023551 : 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 [ + + + + ]: 1023551 : if (trim_it->m_deps_left == 0 && trim_it->m_tx_size <= m_max_cluster_size) {
3430 : 144067 : trim_heap.push_back(trim_it);
3431 : : }
3432 : : }
3433 [ - + ]: 77023 : 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 : 77023 : deps_by_parent = deps_by_child;
3438 [ + + + + : 10031964 : 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 : 77023 : deps_it = deps_by_parent.begin();
3443 [ + + ]: 1100574 : for (auto& trim_entry : trim_data) {
3444 : 1023551 : trim_entry.m_children_count = 0;
3445 : 1023551 : trim_entry.m_children_offset = deps_it - deps_by_parent.begin();
3446 [ + + + + ]: 2472829 : while (deps_it != deps_by_parent.end() && deps_it->first == trim_entry.m_index) {
3447 : 1449278 : ++trim_entry.m_children_count;
3448 : 1449278 : ++deps_it;
3449 : : }
3450 : : }
3451 [ - + ]: 77023 : Assume(deps_it == deps_by_parent.end());
3452 : :
3453 : : // Build a heap of all transactions with 0 unmet dependencies.
3454 : 77023 : 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 [ + + ]: 1054669 : while (!trim_heap.empty()) {
3469 : : // Move the best remaining transaction to the end of trim_heap.
3470 : 900623 : std::pop_heap(trim_heap.begin(), trim_heap.end(), cmp_fn);
3471 : : // Pop it, and find its TrimTxData.
3472 [ + + ]: 900623 : auto& entry = *trim_heap.back();
3473 [ + + ]: 900623 : trim_heap.pop_back();
3474 : :
3475 : : // Initialize it as a singleton partition.
3476 : 900623 : entry.m_uf_parent = &entry;
3477 : 900623 : entry.m_uf_count = 1;
3478 : 900623 : entry.m_uf_size = entry.m_tx_size;
3479 : :
3480 : : // Find the distinct transaction partitions this entry depends on.
3481 [ + + ]: 900623 : current_deps.clear();
3482 [ - + - + : 2163223 : for (auto& [par, chl] : std::span{deps_by_child}.subspan(entry.m_parent_offset, entry.m_parent_count)) {
+ + ]
3483 [ - + ]: 1262600 : Assume(chl == entry.m_index);
3484 : 2525200 : current_deps.push_back(find_fn(&*locate_fn(par)));
3485 : : }
3486 : 900623 : std::sort(current_deps.begin(), current_deps.end());
3487 : 900623 : current_deps.erase(std::unique(current_deps.begin(), current_deps.end()), current_deps.end());
3488 : :
3489 : : // Compute resource counts.
3490 : 900623 : uint32_t new_count = 1;
3491 : 900623 : uint64_t new_size = entry.m_tx_size;
3492 [ + + ]: 1757099 : for (TrimTxData* ptr : current_deps) {
3493 : 856476 : new_count += ptr->m_uf_count;
3494 : 856476 : new_size += ptr->m_uf_size;
3495 : : }
3496 : : // Skip the entry if this would violate any limit.
3497 [ + + + + ]: 900623 : 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 : 844065 : auto rep = &entry;
3501 [ + + ]: 1626447 : 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 : 844065 : entry.m_deps_left = uint32_t(-1);
3504 : : // Mark each to-be-added dependency involving this transaction as parent satisfied.
3505 [ - + - + : 2168848 : for (auto& [par, chl] : std::span{deps_by_parent}.subspan(entry.m_children_offset, entry.m_children_count)) {
+ + ]
3506 [ - + ]: 1324783 : Assume(par == entry.m_index);
3507 : 1324783 : 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 [ - + ]: 1324783 : Assume(chl_it->m_deps_left > 0);
3511 [ + + ]: 1324783 : if (--chl_it->m_deps_left == 0) {
3512 : 756556 : trim_heap.push_back(chl_it);
3513 : 756556 : 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 [ + + ]: 1100574 : for (const auto& trim_entry : trim_data) {
3523 [ + + ]: 1023551 : if (trim_entry.m_deps_left != uint32_t(-1)) {
3524 : 179486 : ret.push_back(m_entries[trim_entry.m_index].m_ref);
3525 : 179486 : clusterset.m_to_remove.push_back(trim_entry.m_index);
3526 : : }
3527 : : }
3528 : : }
3529 [ + - ]: 23360 : clusterset.m_group_data.reset();
3530 : 23360 : clusterset.m_oversized = false;
3531 [ - + ]: 23360 : Assume(!ret.empty());
3532 : 23360 : return ret;
3533 : 23360 : }
3534 : :
3535 : 4332408 : size_t TxGraphImpl::GetMainMemoryUsage() noexcept
3536 : : {
3537 : : // Make sure splits/merges are applied, as memory usage may not be representative otherwise.
3538 : 4332408 : SplitAll(/*up_to_level=*/0);
3539 : 4332408 : ApplyDependencies(/*level=*/0);
3540 : : // Compute memory usage
3541 : 4332408 : size_t usage = /* From clusters */
3542 : 4332408 : m_main_clusterset.m_cluster_usage +
3543 : : /* From Entry objects. */
3544 : 4332408 : sizeof(Entry) * m_main_clusterset.m_txcount +
3545 : : /* From the chunk index. */
3546 : 4332408 : memusage::DynamicUsage(m_main_chunkindex);
3547 : 4332408 : return usage;
3548 : : }
3549 : :
3550 : : } // namespace
3551 : :
3552 : 7453652 : TxGraph::Ref::~Ref()
3553 : : {
3554 [ + + ]: 7453652 : if (m_graph) {
3555 : : // Inform the TxGraph about the Ref being destroyed.
3556 : 4320374 : m_graph->UnlinkRef(m_index);
3557 : 4320374 : m_graph = nullptr;
3558 : : }
3559 : 7453652 : }
3560 : :
3561 : 66191 : TxGraph::Ref::Ref(Ref&& other) noexcept
3562 : : {
3563 : : // Inform the TxGraph of other that its Ref is being moved.
3564 [ - + ]: 66191 : if (other.m_graph) other.m_graph->UpdateRef(other.m_index, *this);
3565 : : // Actually move the contents.
3566 : 66191 : std::swap(m_graph, other.m_graph);
3567 : 66191 : std::swap(m_index, other.m_index);
3568 : 66191 : }
3569 : :
3570 : 40313 : 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 [ - + ]: 40313 : 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 [ - + ]: 40313 : /*fallback_order=*/fallback_order);
3581 : : }
|
