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