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 is a singleton cluster consisting of a transaction that individually exceeds the
39 : : * cluster size limit. It cannot be merged with anything. */
40 : : OVERSIZED_SINGLETON,
41 : : /** This cluster may have multiple disconnected components, which are all NEEDS_RELINEARIZE. */
42 : : NEEDS_SPLIT,
43 : : /** This cluster may have multiple disconnected components, which are all ACCEPTABLE. */
44 : : NEEDS_SPLIT_ACCEPTABLE,
45 : : /** This cluster has undergone changes that warrant re-linearization. */
46 : : NEEDS_RELINEARIZE,
47 : : /** The minimal level of linearization has been performed, but it is not known to be optimal. */
48 : : ACCEPTABLE,
49 : : /** The linearization is known to be optimal. */
50 : : OPTIMAL,
51 : : /** This cluster is not registered in any ClusterSet::m_clusters.
52 : : * This must be the last entry in QualityLevel as ClusterSet::m_clusters is sized using it. */
53 : : NONE,
54 : : };
55 : :
56 : : /** Information about a transaction inside TxGraphImpl::Trim. */
57 : 167606 : struct TrimTxData
58 : : {
59 : : // Fields populated by Cluster::AppendTrimData(). These are immutable after TrimTxData
60 : : // construction.
61 : : /** Chunk feerate for this transaction. */
62 : : FeePerWeight m_chunk_feerate;
63 : : /** GraphIndex of the transaction. */
64 : : TxGraph::GraphIndex m_index;
65 : : /** Size of the transaction. */
66 : : uint32_t m_tx_size;
67 : :
68 : : // Fields only used internally by TxGraphImpl::Trim():
69 : : /** Number of unmet dependencies this transaction has. -1 if the transaction is included. */
70 : : uint32_t m_deps_left;
71 : : /** Number of dependencies that apply to this transaction as child. */
72 : : uint32_t m_parent_count;
73 : : /** Where in deps_by_child those dependencies begin. */
74 : : uint32_t m_parent_offset;
75 : : /** Number of dependencies that apply to this transaction as parent. */
76 : : uint32_t m_children_count;
77 : : /** Where in deps_by_parent those dependencies begin. */
78 : : uint32_t m_children_offset;
79 : :
80 : : // Fields only used internally by TxGraphImpl::Trim()'s union-find implementation, and only for
81 : : // transactions that are definitely included or definitely rejected.
82 : : //
83 : : // As transactions get processed, they get organized into trees which form partitions
84 : : // representing the would-be clusters up to that point. The root of each tree is a
85 : : // representative for that partition. See
86 : : // https://en.wikipedia.org/wiki/Disjoint-set_data_structure.
87 : : //
88 : : /** Pointer to another TrimTxData, towards the root of the tree. If this is a root, m_uf_parent
89 : : * is equal to this itself. */
90 : : TrimTxData* m_uf_parent;
91 : : /** If this is a root, the total number of transactions in the partition. */
92 : : uint32_t m_uf_count;
93 : : /** If this is a root, the total size of transactions in the partition. */
94 : : uint64_t m_uf_size;
95 : : };
96 : :
97 : : /** A grouping of connected transactions inside a TxGraphImpl::ClusterSet. */
98 : : class Cluster
99 : : {
100 : : friend class TxGraphImpl;
101 : : using GraphIndex = TxGraph::GraphIndex;
102 : : using SetType = BitSet<MAX_CLUSTER_COUNT_LIMIT>;
103 : : /** The DepGraph for this cluster, holding all feerates, and ancestors/descendants. */
104 : : DepGraph<SetType> m_depgraph;
105 : : /** m_mapping[i] gives the GraphIndex for the position i transaction in m_depgraph. Values for
106 : : * positions i that do not exist in m_depgraph shouldn't ever be accessed and thus don't
107 : : * matter. m_mapping.size() equals m_depgraph.PositionRange(). */
108 : : std::vector<GraphIndex> m_mapping;
109 : : /** The current linearization of the cluster. m_linearization.size() equals
110 : : * m_depgraph.TxCount(). This is always kept topological. */
111 : : std::vector<DepGraphIndex> m_linearization;
112 : : /** The quality level of m_linearization. */
113 : : QualityLevel m_quality{QualityLevel::NONE};
114 : : /** Which position this Cluster has in Graph::ClusterSet::m_clusters[m_quality]. */
115 : : ClusterSetIndex m_setindex{ClusterSetIndex(-1)};
116 : : /** Which level this Cluster is at in the graph (-1=not inserted, 0=main, 1=staging). */
117 : : int m_level{-1};
118 : : /** Sequence number for this Cluster (for tie-breaking comparison between equal-chunk-feerate
119 : : transactions in distinct clusters). */
120 : : uint64_t m_sequence;
121 : :
122 : : public:
123 : : Cluster() noexcept = delete;
124 : : /** Construct an empty Cluster. */
125 : : explicit Cluster(uint64_t sequence) noexcept;
126 : : /** Construct a singleton Cluster. */
127 : : explicit Cluster(uint64_t sequence, TxGraphImpl& graph, const FeePerWeight& feerate, GraphIndex graph_index) noexcept;
128 : :
129 : : // Cannot move or copy (would invalidate Cluster* in Locator and ClusterSet). */
130 : : Cluster(const Cluster&) = delete;
131 : : Cluster& operator=(const Cluster&) = delete;
132 : : Cluster(Cluster&&) = delete;
133 : : Cluster& operator=(Cluster&&) = delete;
134 : :
135 : : // Generic helper functions.
136 : :
137 : : /** Whether the linearization of this Cluster can be exposed. */
138 : 4050056 : bool IsAcceptable(bool after_split = false) const noexcept
139 : : {
140 [ + + + + : 3906201 : return m_quality == QualityLevel::ACCEPTABLE || m_quality == QualityLevel::OPTIMAL ||
+ + + + ]
141 [ + + + + ]: 87590 : (after_split && m_quality == QualityLevel::NEEDS_SPLIT_ACCEPTABLE);
142 : : }
143 : : /** Whether the linearization of this Cluster is optimal. */
144 : 11197 : bool IsOptimal() const noexcept
145 : : {
146 : 11197 : return m_quality == QualityLevel::OPTIMAL;
147 : : }
148 : : /** Whether this cluster is oversized. Note that no changes that can cause oversizedness are
149 : : * ever applied, so the only way a materialized Cluster object can be oversized is by being
150 : : * an individually oversized transaction singleton. */
151 : 14580 : bool IsOversized() const noexcept { return m_quality == QualityLevel::OVERSIZED_SINGLETON; }
152 : : /** Whether this cluster requires splitting. */
153 : 3488262 : bool NeedsSplitting() const noexcept
154 : : {
155 : 3488262 : return m_quality == QualityLevel::NEEDS_SPLIT ||
156 : 62948 : m_quality == QualityLevel::NEEDS_SPLIT_ACCEPTABLE;
157 : : }
158 : : /** Get the number of transactions in this Cluster. */
159 [ + + ]: 330634 : LinearizationIndex GetTxCount() const noexcept { return m_linearization.size(); }
160 : : /** Get the total size of the transactions in this Cluster. */
161 : : uint64_t GetTotalTxSize() const noexcept;
162 : : /** Given a DepGraphIndex into this Cluster, find the corresponding GraphIndex. */
163 : 35650 : GraphIndex GetClusterEntry(DepGraphIndex index) const noexcept { return m_mapping[index]; }
164 : : /** Only called by Graph::SwapIndexes. */
165 : 16673 : void UpdateMapping(DepGraphIndex cluster_idx, GraphIndex graph_idx) noexcept { m_mapping[cluster_idx] = graph_idx; }
166 : : /** Push changes to Cluster and its linearization to the TxGraphImpl Entry objects. */
167 : : void Updated(TxGraphImpl& graph) noexcept;
168 : : /** Create a copy of this Cluster in staging, returning a pointer to it (used by PullIn). */
169 : : Cluster* CopyToStaging(TxGraphImpl& graph) const noexcept;
170 : : /** Get the list of Clusters in main that conflict with this one (which is assumed to be in staging). */
171 : : void GetConflicts(const TxGraphImpl& graph, std::vector<Cluster*>& out) const noexcept;
172 : : /** Mark all the Entry objects belonging to this staging Cluster as missing. The Cluster must be
173 : : * deleted immediately after. */
174 : : void MakeStagingTransactionsMissing(TxGraphImpl& graph) noexcept;
175 : : /** Remove all transactions from a Cluster. */
176 : : void Clear(TxGraphImpl& graph) noexcept;
177 : : /** Change a Cluster's level from 1 (staging) to 0 (main). */
178 : : void MoveToMain(TxGraphImpl& graph) noexcept;
179 : :
180 : : // Functions that implement the Cluster-specific side of internal TxGraphImpl mutations.
181 : :
182 : : /** Apply all removals from the front of to_remove that apply to this Cluster, popping them
183 : : * off. These must be at least one such entry. */
184 : : void ApplyRemovals(TxGraphImpl& graph, std::span<GraphIndex>& to_remove) noexcept;
185 : : /** Split this cluster (must have a NEEDS_SPLIT* quality). Returns whether to delete this
186 : : * Cluster afterwards. */
187 : : [[nodiscard]] bool Split(TxGraphImpl& graph) noexcept;
188 : : /** Move all transactions from cluster to *this (as separate components). */
189 : : void Merge(TxGraphImpl& graph, Cluster& cluster) noexcept;
190 : : /** Given a span of (parent, child) pairs that all belong to this Cluster, apply them. */
191 : : void ApplyDependencies(TxGraphImpl& graph, std::span<std::pair<GraphIndex, GraphIndex>> to_apply) noexcept;
192 : : /** Improve the linearization of this Cluster. Returns how much work was performed and whether
193 : : * the Cluster's QualityLevel improved as a result. */
194 : : std::pair<uint64_t, bool> Relinearize(TxGraphImpl& graph, uint64_t max_iters) noexcept;
195 : : /** For every chunk in the cluster, append its FeeFrac to ret. */
196 : : void AppendChunkFeerates(std::vector<FeeFrac>& ret) const noexcept;
197 : : /** Add a TrimTxData entry (filling m_chunk_feerate, m_index, m_tx_size) for every
198 : : * transaction in the Cluster to ret. Implicit dependencies between consecutive transactions
199 : : * in the linearization are added to deps. Return the Cluster's total transaction size. */
200 : : uint64_t AppendTrimData(std::vector<TrimTxData>& ret, std::vector<std::pair<GraphIndex, GraphIndex>>& deps) const noexcept;
201 : :
202 : : // Functions that implement the Cluster-specific side of public TxGraph functions.
203 : :
204 : : /** Process elements from the front of args that apply to this cluster, and append Refs for the
205 : : * union of their ancestors to output. */
206 : : void GetAncestorRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept;
207 : : /** Process elements from the front of args that apply to this cluster, and append Refs for the
208 : : * union of their descendants to output. */
209 : : void GetDescendantRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept;
210 : : /** Populate range with refs for the transactions in this Cluster's linearization, from
211 : : * position start_pos until start_pos+range.size()-1, inclusive. Returns whether that
212 : : * range includes the last transaction in the linearization. */
213 : : bool GetClusterRefs(TxGraphImpl& graph, std::span<TxGraph::Ref*> range, LinearizationIndex start_pos) noexcept;
214 : : /** Get the individual transaction feerate of a Cluster element. */
215 : : FeePerWeight GetIndividualFeerate(DepGraphIndex idx) noexcept;
216 : : /** Modify the fee of a Cluster element. */
217 : : void SetFee(TxGraphImpl& graph, DepGraphIndex idx, int64_t fee) noexcept;
218 : :
219 : : // Debugging functions.
220 : :
221 : : void SanityCheck(const TxGraphImpl& graph, int level) const;
222 : : };
223 : :
224 : :
225 : : /** The transaction graph, including staged changes.
226 : : *
227 : : * The overall design of the data structure consists of 3 interlinked representations:
228 : : * - The transactions (held as a vector of TxGraphImpl::Entry inside TxGraphImpl).
229 : : * - The clusters (Cluster objects in per-quality vectors inside TxGraphImpl::ClusterSet).
230 : : * - The Refs (TxGraph::Ref objects, held externally by users of the TxGraph class)
231 : : *
232 : : * The Clusters are kept in one or two ClusterSet objects, one for the "main" graph, and one for
233 : : * the proposed changes ("staging"). If a transaction occurs in both, they share the same Entry,
234 : : * but there will be a separate Cluster per graph.
235 : : *
236 : : * Clusters and Refs contain the index of the Entry objects they refer to, and the Entry objects
237 : : * refer back to the Clusters and Refs the corresponding transaction is contained in.
238 : : *
239 : : * While redundant, this permits moving all of them independently, without invalidating things
240 : : * or costly iteration to fix up everything:
241 : : * - Entry objects can be moved to fill holes left by removed transactions in the Entry vector
242 : : * (see TxGraphImpl::Compact).
243 : : * - Clusters can be rewritten continuously (removals can cause them to split, new dependencies
244 : : * can cause them to be merged).
245 : : * - Ref objects can be held outside the class, while permitting them to be moved around, and
246 : : * inherited from.
247 : : */
248 : : class TxGraphImpl final : public TxGraph
249 : : {
250 : : friend class Cluster;
251 : : friend class BlockBuilderImpl;
252 : : private:
253 : : /** Internal RNG. */
254 : : FastRandomContext m_rng;
255 : : /** This TxGraphImpl's maximum cluster count limit. */
256 : : const DepGraphIndex m_max_cluster_count;
257 : : /** This TxGraphImpl's maximum cluster size limit. */
258 : : const uint64_t m_max_cluster_size;
259 : : /** The number of linearization improvement steps needed per cluster to be considered
260 : : * acceptable. */
261 : : const uint64_t m_acceptable_iters;
262 : :
263 : : /** Information about one group of Clusters to be merged. */
264 : : struct GroupEntry
265 : : {
266 : : /** Where the clusters to be merged start in m_group_clusters. */
267 : : uint32_t m_cluster_offset;
268 : : /** How many clusters to merge. */
269 : : uint32_t m_cluster_count;
270 : : /** Where the dependencies for this cluster group in m_deps_to_add start. */
271 : : uint32_t m_deps_offset;
272 : : /** How many dependencies to add. */
273 : : uint32_t m_deps_count;
274 : : };
275 : :
276 : : /** Information about all groups of Clusters to be merged. */
277 : 104009 : struct GroupData
278 : : {
279 : : /** The groups of Clusters to be merged. */
280 : : std::vector<GroupEntry> m_groups;
281 : : /** Which clusters are to be merged. GroupEntry::m_cluster_offset indexes into this. */
282 : : std::vector<Cluster*> m_group_clusters;
283 : : };
284 : :
285 : : /** The collection of all Clusters in main or staged. */
286 : : struct ClusterSet
287 : : {
288 : : /** The vectors of clusters, one vector per quality level. ClusterSetIndex indexes into each. */
289 : : std::array<std::vector<std::unique_ptr<Cluster>>, int(QualityLevel::NONE)> m_clusters;
290 : : /** Which removals have yet to be applied. */
291 : : std::vector<GraphIndex> m_to_remove;
292 : : /** Which dependencies are to be added ((parent,child) pairs). GroupData::m_deps_offset indexes
293 : : * into this. */
294 : : std::vector<std::pair<GraphIndex, GraphIndex>> m_deps_to_add;
295 : : /** Information about the merges to be performed, if known. */
296 : : std::optional<GroupData> m_group_data = GroupData{};
297 : : /** Which entries were removed in this ClusterSet (so they can be wiped on abort). This
298 : : * includes all entries which have an (R) removed locator at this level (staging only),
299 : : * plus optionally any transaction in m_unlinked. */
300 : : std::vector<GraphIndex> m_removed;
301 : : /** Total number of transactions in this graph (sum of all transaction counts in all
302 : : * Clusters, and for staging also those inherited from the main ClusterSet). */
303 : : GraphIndex m_txcount{0};
304 : : /** Total number of individually oversized transactions in the graph. */
305 : : GraphIndex m_txcount_oversized{0};
306 : : /** Whether this graph is oversized (if known). */
307 : : std::optional<bool> m_oversized{false};
308 : :
309 : 14849 : ClusterSet() noexcept = default;
310 : : };
311 : :
312 : : /** The main ClusterSet. */
313 : : ClusterSet m_main_clusterset;
314 : : /** The staging ClusterSet, if any. */
315 : : std::optional<ClusterSet> m_staging_clusterset;
316 : : /** Next sequence number to assign to created Clusters. */
317 : : uint64_t m_next_sequence_counter{0};
318 : :
319 : : /** Information about a chunk in the main graph. */
320 : : struct ChunkData
321 : : {
322 : : /** The Entry which is the last transaction of the chunk. */
323 : : mutable GraphIndex m_graph_index;
324 : : /** How many transactions the chunk contains (-1 = singleton tail of cluster). */
325 : : LinearizationIndex m_chunk_count;
326 : :
327 : 183774 : ChunkData(GraphIndex graph_index, LinearizationIndex chunk_count) noexcept :
328 : 183774 : m_graph_index{graph_index}, m_chunk_count{chunk_count} {}
329 : : };
330 : :
331 : : /** Compare two Cluster* by their m_sequence value (while supporting nullptr). */
332 : 3433924 : static std::strong_ordering CompareClusters(Cluster* a, Cluster* b) noexcept
333 : : {
334 : : // The nullptr pointer compares before everything else.
335 [ + + ]: 3433924 : if (a == nullptr || b == nullptr) {
336 [ + + + + ]: 9625 : return (a != nullptr) <=> (b != nullptr);
337 : : }
338 : : // If neither pointer is nullptr, compare the Clusters' sequence numbers.
339 [ + + - + ]: 3424299 : Assume(a == b || a->m_sequence != b->m_sequence);
340 [ + + + + ]: 3424299 : return a->m_sequence <=> b->m_sequence;
341 : : }
342 : :
343 : : /** Compare two entries (which must both exist within the main graph). */
344 : 2333294 : std::strong_ordering CompareMainTransactions(GraphIndex a, GraphIndex b) const noexcept
345 : : {
346 [ + - - + ]: 2333294 : Assume(a < m_entries.size() && b < m_entries.size());
347 [ + + ]: 2333294 : const auto& entry_a = m_entries[a];
348 : 2333294 : const auto& entry_b = m_entries[b];
349 : : // Compare chunk feerates, and return result if it differs.
350 : 2333294 : auto feerate_cmp = FeeRateCompare(entry_b.m_main_chunk_feerate, entry_a.m_main_chunk_feerate);
351 [ + + ]: 2333294 : if (feerate_cmp < 0) return std::strong_ordering::less;
352 [ + + ]: 1929480 : if (feerate_cmp > 0) return std::strong_ordering::greater;
353 : : // Compare Cluster m_sequence as tie-break for equal chunk feerates.
354 : 1669437 : const auto& locator_a = entry_a.m_locator[0];
355 : 1669437 : const auto& locator_b = entry_b.m_locator[0];
356 : 1669437 : Assume(locator_a.IsPresent() && locator_b.IsPresent());
357 [ + + ]: 1669437 : if (locator_a.cluster != locator_b.cluster) {
358 : 1444890 : return CompareClusters(locator_a.cluster, locator_b.cluster);
359 : : }
360 : : // As final tie-break, compare position within cluster linearization.
361 [ + + + + ]: 224547 : return entry_a.m_main_lin_index <=> entry_b.m_main_lin_index;
362 : : }
363 : :
364 : : /** Comparator for ChunkData objects in mining order. */
365 : : class ChunkOrder
366 : : {
367 : : const TxGraphImpl* const m_graph;
368 : : public:
369 : 5208 : explicit ChunkOrder(const TxGraphImpl* graph) : m_graph(graph) {}
370 : :
371 : 1465439 : bool operator()(const ChunkData& a, const ChunkData& b) const noexcept
372 : : {
373 : 1465439 : return m_graph->CompareMainTransactions(a.m_graph_index, b.m_graph_index) < 0;
374 : : }
375 : : };
376 : :
377 : : /** Definition for the mining index type. */
378 : : using ChunkIndex = std::set<ChunkData, ChunkOrder>;
379 : :
380 : : /** Index of ChunkData objects, indexing the last transaction in each chunk in the main
381 : : * graph. */
382 : : ChunkIndex m_main_chunkindex;
383 : : /** Number of index-observing objects in existence (BlockBuilderImpls). */
384 : : size_t m_main_chunkindex_observers{0};
385 : : /** Cache of discarded ChunkIndex node handles to reuse, avoiding additional allocation. */
386 : : std::vector<ChunkIndex::node_type> m_main_chunkindex_discarded;
387 : :
388 : : /** A Locator that describes whether, where, and in which Cluster an Entry appears.
389 : : * Every Entry has MAX_LEVELS locators, as it may appear in one Cluster per level.
390 : : *
391 : : * Each level of a Locator is in one of three states:
392 : : *
393 : : * - (P)resent: actually occurs in a Cluster at that level.
394 : : *
395 : : * - (M)issing:
396 : : * - In the main graph: the transaction does not exist in main.
397 : : * - In the staging graph: the transaction's existence is the same as in main. If it doesn't
398 : : * exist in main, (M) in staging means it does not exist there
399 : : * either. If it does exist in main, (M) in staging means the
400 : : * cluster it is in has not been modified in staging, and thus the
401 : : * transaction implicitly exists in staging too (without explicit
402 : : * Cluster object; see PullIn() to create it in staging too).
403 : : *
404 : : * - (R)emoved: only possible in staging; it means the transaction exists in main, but is
405 : : * removed in staging.
406 : : *
407 : : * The following combinations are possible:
408 : : * - (M,M): the transaction doesn't exist in either graph.
409 : : * - (P,M): the transaction exists in both, but only exists explicitly in a Cluster object in
410 : : * main. Its existence in staging is inherited from main.
411 : : * - (P,P): the transaction exists in both, and is materialized in both. Thus, the clusters
412 : : * and/or their linearizations may be different in main and staging.
413 : : * - (M,P): the transaction is added in staging, and does not exist in main.
414 : : * - (P,R): the transaction exists in main, but is removed in staging.
415 : : *
416 : : * When staging does not exist, only (M,M) and (P,M) are possible.
417 : : */
418 : : struct Locator
419 : : {
420 : : /** Which Cluster the Entry appears in (nullptr = missing). */
421 : : Cluster* cluster{nullptr};
422 : : /** Where in the Cluster it appears (if cluster == nullptr: 0 = missing, -1 = removed). */
423 : : DepGraphIndex index{0};
424 : :
425 : : /** Mark this Locator as missing (= same as lower level, or non-existing if level 0). */
426 : 11039 : void SetMissing() noexcept { cluster = nullptr; index = 0; }
427 : : /** Mark this Locator as removed (not allowed in level 0). */
428 : 16830 : void SetRemoved() noexcept { cluster = nullptr; index = DepGraphIndex(-1); }
429 : : /** Mark this Locator as present, in the specified Cluster. */
430 : 771744 : void SetPresent(Cluster* c, DepGraphIndex i) noexcept { cluster = c; index = i; }
431 : : /** Check if this Locator is missing. */
432 [ + + + + ]: 1193716 : bool IsMissing() const noexcept { return cluster == nullptr && index == 0; }
433 : : /** Check if this Locator is removed. */
434 [ + + + - : 497250 : bool IsRemoved() const noexcept { return cluster == nullptr && index == DepGraphIndex(-1); }
+ + ]
435 : : /** Check if this Locator is present (in some Cluster). */
436 [ + + + - : 1928020 : bool IsPresent() const noexcept { return cluster != nullptr; }
- + ]
437 : : };
438 : :
439 : : /** Internal information about each transaction in a TxGraphImpl. */
440 : 228130 : struct Entry
441 : : {
442 : : /** Pointer to the corresponding Ref object if any, or nullptr if unlinked. */
443 : : Ref* m_ref{nullptr};
444 : : /** Iterator to the corresponding ChunkData, if any, and m_main_chunkindex.end() otherwise.
445 : : * This is initialized on construction of the Entry, in AddTransaction. */
446 : : ChunkIndex::iterator m_main_chunkindex_iterator;
447 : : /** Which Cluster and position therein this Entry appears in. ([0] = main, [1] = staged). */
448 : : Locator m_locator[MAX_LEVELS];
449 : : /** The chunk feerate of this transaction in main (if present in m_locator[0]). */
450 : : FeePerWeight m_main_chunk_feerate;
451 : : /** The position this transaction has in the main linearization (if present). */
452 : : LinearizationIndex m_main_lin_index;
453 : : };
454 : :
455 : : /** The set of all transactions (in all levels combined). GraphIndex values index into this. */
456 : : std::vector<Entry> m_entries;
457 : :
458 : : /** Set of Entries which have no linked Ref anymore. */
459 : : std::vector<GraphIndex> m_unlinked;
460 : :
461 : : public:
462 : : /** Construct a new TxGraphImpl with the specified limits. */
463 : 5208 : explicit TxGraphImpl(DepGraphIndex max_cluster_count, uint64_t max_cluster_size, uint64_t acceptable_iters) noexcept :
464 : 5208 : m_max_cluster_count(max_cluster_count),
465 : 5208 : m_max_cluster_size(max_cluster_size),
466 : 5208 : m_acceptable_iters(acceptable_iters),
467 : 5208 : m_main_chunkindex(ChunkOrder(this))
468 : : {
469 : 5208 : Assume(max_cluster_count >= 1);
470 : 5208 : Assume(max_cluster_count <= MAX_CLUSTER_COUNT_LIMIT);
471 : 5208 : }
472 : :
473 : : /** Destructor. */
474 : : ~TxGraphImpl() noexcept;
475 : :
476 : : // Cannot move or copy (would invalidate TxGraphImpl* in Ref, MiningOrder, EvictionOrder).
477 : : TxGraphImpl(const TxGraphImpl&) = delete;
478 : : TxGraphImpl& operator=(const TxGraphImpl&) = delete;
479 : : TxGraphImpl(TxGraphImpl&&) = delete;
480 : : TxGraphImpl& operator=(TxGraphImpl&&) = delete;
481 : :
482 : : // Simple helper functions.
483 : :
484 : : /** Swap the Entry referred to by a and the one referred to by b. */
485 : : void SwapIndexes(GraphIndex a, GraphIndex b) noexcept;
486 : : /** If idx exists in the specified level ClusterSet (explicitly, or in the level below and not
487 : : * removed), return the Cluster it is in. Otherwise, return nullptr. */
488 : : Cluster* FindCluster(GraphIndex idx, int level) const noexcept;
489 : : /** Extract a Cluster from its ClusterSet. */
490 : : std::unique_ptr<Cluster> ExtractCluster(int level, QualityLevel quality, ClusterSetIndex setindex) noexcept;
491 : : /** Delete a Cluster. */
492 : : void DeleteCluster(Cluster& cluster) noexcept;
493 : : /** Insert a Cluster into its ClusterSet. */
494 : : ClusterSetIndex InsertCluster(int level, std::unique_ptr<Cluster>&& cluster, QualityLevel quality) noexcept;
495 : : /** Change the QualityLevel of a Cluster (identified by old_quality and old_index). */
496 : : void SetClusterQuality(int level, QualityLevel old_quality, ClusterSetIndex old_index, QualityLevel new_quality) noexcept;
497 : : /** Get the index of the top level ClusterSet (staging if it exists, main otherwise). */
498 [ + - + - : 4690257 : int GetTopLevel() const noexcept { return m_staging_clusterset.has_value(); }
+ - - + -
+ - + +
+ ]
499 : : /** Get the specified level (staging if it exists and main_only is not specified, main otherwise). */
500 [ + + + + : 328724 : int GetSpecifiedLevel(bool main_only) const noexcept { return m_staging_clusterset.has_value() && !main_only; }
+ + + + +
+ + + + +
+ + + + ]
501 : : /** Get a reference to the ClusterSet at the specified level (which must exist). */
502 : : ClusterSet& GetClusterSet(int level) noexcept;
503 : : const ClusterSet& GetClusterSet(int level) const noexcept;
504 : : /** Make a transaction not exist at a specified level. It must currently exist there.
505 : : * oversized_tx indicates whether the transaction is an individually-oversized one
506 : : * (OVERSIZED_SINGLETON). */
507 : : void ClearLocator(int level, GraphIndex index, bool oversized_tx) noexcept;
508 : : /** Find which Clusters in main conflict with ones in staging. */
509 : : std::vector<Cluster*> GetConflicts() const noexcept;
510 : : /** Clear an Entry's ChunkData. */
511 : : void ClearChunkData(Entry& entry) noexcept;
512 : : /** Give an Entry a ChunkData object. */
513 : : void CreateChunkData(GraphIndex idx, LinearizationIndex chunk_count) noexcept;
514 : :
515 : : // Functions for handling Refs.
516 : :
517 : : /** Only called by Ref's move constructor/assignment to update Ref locations. */
518 : 228130 : void UpdateRef(GraphIndex idx, Ref& new_location) noexcept final
519 : : {
520 : 228130 : auto& entry = m_entries[idx];
521 : 228130 : Assume(entry.m_ref != nullptr);
522 : 228130 : entry.m_ref = &new_location;
523 : 228130 : }
524 : :
525 : : /** Only called by Ref::~Ref to unlink Refs, and Ref's move assignment. */
526 : 45968 : void UnlinkRef(GraphIndex idx) noexcept final
527 : : {
528 : 45968 : auto& entry = m_entries[idx];
529 : 45968 : Assume(entry.m_ref != nullptr);
530 [ + + + - ]: 56033 : Assume(m_main_chunkindex_observers == 0 || !entry.m_locator[0].IsPresent());
531 : 45968 : entry.m_ref = nullptr;
532 : : // Mark the transaction as to be removed in all levels where it explicitly or implicitly
533 : : // exists.
534 : 45968 : bool exists_anywhere{false};
535 : 45968 : bool exists{false};
536 [ + + ]: 97803 : for (int level = 0; level <= GetTopLevel(); ++level) {
537 [ + + ]: 51835 : if (entry.m_locator[level].IsPresent()) {
538 : : exists_anywhere = true;
539 : : exists = true;
540 [ + + ]: 33521 : } else if (entry.m_locator[level].IsRemoved()) {
541 : : exists = false;
542 : : }
543 [ + + ]: 33084 : if (exists) {
544 : 21720 : auto& clusterset = GetClusterSet(level);
545 : 21720 : clusterset.m_to_remove.push_back(idx);
546 : : // Force recomputation of grouping data.
547 [ + + ]: 21720 : clusterset.m_group_data = std::nullopt;
548 : : // Do not wipe the oversized state of main if staging exists. The reason for this
549 : : // is that the alternative would mean that cluster merges may need to be applied to
550 : : // a formerly-oversized main graph while staging exists (to satisfy chunk feerate
551 : : // queries into main, for example), and such merges could conflict with pulls of
552 : : // some of their constituents into staging.
553 [ + + + + ]: 60893 : if (level == GetTopLevel() && clusterset.m_oversized == true) {
554 : 2734 : clusterset.m_oversized = std::nullopt;
555 : : }
556 : : }
557 : : }
558 : 45968 : m_unlinked.push_back(idx);
559 [ + + ]: 45968 : if (!exists_anywhere) Compact();
560 : 45968 : }
561 : :
562 : : // Functions related to various normalization/application steps.
563 : : /** Get rid of unlinked Entry objects in m_entries, if possible (this changes the GraphIndex
564 : : * values for remaining Entry objects, so this only does something when no to-be-applied
565 : : * operations or staged removals referring to GraphIndexes remain). */
566 : : void Compact() noexcept;
567 : : /** If cluster is not in staging, copy it there, and return a pointer to it.
568 : : * Staging must exist, and this modifies the locators of its
569 : : * transactions from inherited (P,M) to explicit (P,P). */
570 : : Cluster* PullIn(Cluster* cluster) noexcept;
571 : : /** Apply all removals queued up in m_to_remove to the relevant Clusters (which get a
572 : : * NEEDS_SPLIT* QualityLevel) up to the specified level. */
573 : : void ApplyRemovals(int up_to_level) noexcept;
574 : : /** Split an individual cluster. */
575 : : void Split(Cluster& cluster) noexcept;
576 : : /** Split all clusters that need splitting up to the specified level. */
577 : : void SplitAll(int up_to_level) noexcept;
578 : : /** Populate m_group_data based on m_deps_to_add in the specified level. */
579 : : void GroupClusters(int level) noexcept;
580 : : /** Merge the specified clusters. */
581 : : void Merge(std::span<Cluster*> to_merge) noexcept;
582 : : /** Apply all m_deps_to_add to the relevant Clusters in the specified level. */
583 : : void ApplyDependencies(int level) noexcept;
584 : : /** Make a specified Cluster have quality ACCEPTABLE or OPTIMAL. */
585 : : void MakeAcceptable(Cluster& cluster) noexcept;
586 : : /** Make all Clusters at the specified level have quality ACCEPTABLE or OPTIMAL. */
587 : : void MakeAllAcceptable(int level) noexcept;
588 : :
589 : : // Implementations for the public TxGraph interface.
590 : :
591 : : Ref AddTransaction(const FeePerWeight& feerate) noexcept final;
592 : : void RemoveTransaction(const Ref& arg) noexcept final;
593 : : void AddDependency(const Ref& parent, const Ref& child) noexcept final;
594 : : void SetTransactionFee(const Ref&, int64_t fee) noexcept final;
595 : :
596 : : bool DoWork(uint64_t iters) noexcept final;
597 : :
598 : : void StartStaging() noexcept final;
599 : : void CommitStaging() noexcept final;
600 : : void AbortStaging() noexcept final;
601 : 29133 : bool HaveStaging() const noexcept final { return m_staging_clusterset.has_value(); }
602 : :
603 : : bool Exists(const Ref& arg, bool main_only = false) noexcept final;
604 : : FeePerWeight GetMainChunkFeerate(const Ref& arg) noexcept final;
605 : : FeePerWeight GetIndividualFeerate(const Ref& arg) noexcept final;
606 : : std::vector<Ref*> GetCluster(const Ref& arg, bool main_only = false) noexcept final;
607 : : std::vector<Ref*> GetAncestors(const Ref& arg, bool main_only = false) noexcept final;
608 : : std::vector<Ref*> GetDescendants(const Ref& arg, bool main_only = false) noexcept final;
609 : : std::vector<Ref*> GetAncestorsUnion(std::span<const Ref* const> args, bool main_only = false) noexcept final;
610 : : std::vector<Ref*> GetDescendantsUnion(std::span<const Ref* const> args, bool main_only = false) noexcept final;
611 : : GraphIndex GetTransactionCount(bool main_only = false) noexcept final;
612 : : bool IsOversized(bool main_only = false) noexcept final;
613 : : std::strong_ordering CompareMainOrder(const Ref& a, const Ref& b) noexcept final;
614 : : GraphIndex CountDistinctClusters(std::span<const Ref* const> refs, bool main_only = false) noexcept final;
615 : : std::pair<std::vector<FeeFrac>, std::vector<FeeFrac>> GetMainStagingDiagrams() noexcept final;
616 : : std::vector<Ref*> Trim() noexcept final;
617 : :
618 : : std::unique_ptr<BlockBuilder> GetBlockBuilder() noexcept final;
619 : : std::pair<std::vector<Ref*>, FeePerWeight> GetWorstMainChunk() noexcept final;
620 : :
621 : : void SanityCheck() const final;
622 : : };
623 : :
624 : 8406113 : TxGraphImpl::ClusterSet& TxGraphImpl::GetClusterSet(int level) noexcept
625 : : {
626 [ + + ]: 8406113 : if (level == 0) return m_main_clusterset;
627 : 1042811 : Assume(level == 1);
628 : 1042811 : Assume(m_staging_clusterset.has_value());
629 : 1042811 : return *m_staging_clusterset;
630 : : }
631 : :
632 : 26581 : const TxGraphImpl::ClusterSet& TxGraphImpl::GetClusterSet(int level) const noexcept
633 : : {
634 [ + + ]: 26581 : if (level == 0) return m_main_clusterset;
635 : 16165 : Assume(level == 1);
636 : 16165 : Assume(m_staging_clusterset.has_value());
637 : 16165 : return *m_staging_clusterset;
638 : : }
639 : :
640 : : /** Implementation of the TxGraph::BlockBuilder interface. */
641 : : class BlockBuilderImpl final : public TxGraph::BlockBuilder
642 : : {
643 : : /** Which TxGraphImpl this object is doing block building for. It will have its
644 : : * m_main_chunkindex_observers incremented as long as this BlockBuilderImpl exists. */
645 : : TxGraphImpl* const m_graph;
646 : : /** Clusters which we're not including further transactions from. */
647 : : std::set<Cluster*> m_excluded_clusters;
648 : : /** Iterator to the current chunk in the chunk index. end() if nothing further remains. */
649 : : TxGraphImpl::ChunkIndex::const_iterator m_cur_iter;
650 : : /** Which cluster the current chunk belongs to, so we can exclude further transactions from it
651 : : * when that chunk is skipped. */
652 : : Cluster* m_cur_cluster;
653 : : /** Whether we know that m_cur_iter points to the last chunk of m_cur_cluster. */
654 : : bool m_known_end_of_cluster;
655 : :
656 : : // Move m_cur_iter / m_cur_cluster to the next acceptable chunk.
657 : : void Next() noexcept;
658 : :
659 : : public:
660 : : /** Construct a new BlockBuilderImpl to build blocks for the provided graph. */
661 : : BlockBuilderImpl(TxGraphImpl& graph) noexcept;
662 : :
663 : : // Implement the public interface.
664 : : ~BlockBuilderImpl() final;
665 : : std::optional<std::pair<std::vector<TxGraph::Ref*>, FeePerWeight>> GetCurrentChunk() noexcept final;
666 : : void Include() noexcept final;
667 : : void Skip() noexcept final;
668 : : };
669 : :
670 : 572410 : void TxGraphImpl::ClearChunkData(Entry& entry) noexcept
671 : : {
672 [ + + ]: 572410 : if (entry.m_main_chunkindex_iterator != m_main_chunkindex.end()) {
673 : 93408 : Assume(m_main_chunkindex_observers == 0);
674 : : // If the Entry has a non-empty m_main_chunkindex_iterator, extract it, and move the handle
675 : : // to the cache of discarded chunkindex entries.
676 : 93408 : m_main_chunkindex_discarded.emplace_back(m_main_chunkindex.extract(entry.m_main_chunkindex_iterator));
677 : 93408 : entry.m_main_chunkindex_iterator = m_main_chunkindex.end();
678 : : }
679 : 572410 : }
680 : :
681 : 202158 : void TxGraphImpl::CreateChunkData(GraphIndex idx, LinearizationIndex chunk_count) noexcept
682 : : {
683 [ + + ]: 202158 : auto& entry = m_entries[idx];
684 [ + + ]: 202158 : if (!m_main_chunkindex_discarded.empty()) {
685 : : // Reuse an discarded node handle.
686 : 18384 : auto& node = m_main_chunkindex_discarded.back().value();
687 : 18384 : node.m_graph_index = idx;
688 : 18384 : node.m_chunk_count = chunk_count;
689 : 18384 : auto insert_result = m_main_chunkindex.insert(std::move(m_main_chunkindex_discarded.back()));
690 : 18384 : Assume(insert_result.inserted);
691 : 18384 : entry.m_main_chunkindex_iterator = insert_result.position;
692 : 18384 : m_main_chunkindex_discarded.pop_back();
693 : 18384 : } else {
694 : : // Construct a new entry.
695 : 183774 : auto emplace_result = m_main_chunkindex.emplace(idx, chunk_count);
696 : 183774 : Assume(emplace_result.second);
697 : 183774 : entry.m_main_chunkindex_iterator = emplace_result.first;
698 : : }
699 : 202158 : }
700 : :
701 : 435748 : uint64_t Cluster::GetTotalTxSize() const noexcept
702 : : {
703 : 435748 : uint64_t ret{0};
704 [ + + ]: 1138081 : for (auto i : m_linearization) {
705 : 702333 : ret += m_depgraph.FeeRate(i).size;
706 : : }
707 : 435748 : return ret;
708 : : }
709 : :
710 : 79481 : void TxGraphImpl::ClearLocator(int level, GraphIndex idx, bool oversized_tx) noexcept
711 : : {
712 : 79481 : auto& entry = m_entries[idx];
713 : 79481 : auto& clusterset = GetClusterSet(level);
714 : 79481 : Assume(entry.m_locator[level].IsPresent());
715 : : // Change the locator from Present to Missing or Removed.
716 [ + + + + ]: 79481 : if (level == 0 || !entry.m_locator[level - 1].IsPresent()) {
717 : 62651 : entry.m_locator[level].SetMissing();
718 : : } else {
719 : 16830 : entry.m_locator[level].SetRemoved();
720 : 16830 : clusterset.m_removed.push_back(idx);
721 : : }
722 : : // Update the transaction count.
723 : 79481 : --clusterset.m_txcount;
724 : 79481 : clusterset.m_txcount_oversized -= oversized_tx;
725 : : // If clearing main, adjust the status of Locators of this transaction in staging, if it exists.
726 [ + + + + ]: 79481 : if (level == 0 && GetTopLevel() == 1) {
727 [ + + ]: 8573 : if (entry.m_locator[1].IsRemoved()) {
728 : 2861 : entry.m_locator[1].SetMissing();
729 [ + + ]: 5712 : } else if (!entry.m_locator[1].IsPresent()) {
730 : 2838 : --m_staging_clusterset->m_txcount;
731 : 2838 : m_staging_clusterset->m_txcount_oversized -= oversized_tx;
732 : : }
733 : : }
734 [ + + ]: 79481 : if (level == 0) ClearChunkData(entry);
735 : 79481 : }
736 : :
737 : 372198 : void Cluster::Updated(TxGraphImpl& graph) noexcept
738 : : {
739 : : // Update all the Locators for this Cluster's Entry objects.
740 [ + + ]: 1096675 : for (DepGraphIndex idx : m_linearization) {
741 [ + + ]: 724477 : auto& entry = graph.m_entries[m_mapping[idx]];
742 : : // Discard any potential ChunkData prior to modifying the Cluster (as that could
743 : : // invalidate its ordering).
744 [ + + ]: 724477 : if (m_level == 0) graph.ClearChunkData(entry);
745 : 724477 : entry.m_locator[m_level].SetPresent(this, idx);
746 : : }
747 : : // If this is for the main graph (level = 0), and the Cluster's quality is ACCEPTABLE or
748 : : // OPTIMAL, compute its chunking and store its information in the Entry's m_main_lin_index
749 : : // and m_main_chunk_feerate. These fields are only accessed after making the entire graph
750 : : // ACCEPTABLE, so it is pointless to compute these if we haven't reached that quality level
751 : : // yet.
752 [ + + ]: 372198 : if (m_level == 0 && IsAcceptable()) {
753 : 168987 : const LinearizationChunking chunking(m_depgraph, m_linearization);
754 : 168987 : LinearizationIndex lin_idx{0};
755 : : // Iterate over the chunks.
756 [ + + ]: 371145 : for (unsigned chunk_idx = 0; chunk_idx < chunking.NumChunksLeft(); ++chunk_idx) {
757 : 202158 : auto chunk = chunking.GetChunk(chunk_idx);
758 : 202158 : auto chunk_count = chunk.transactions.Count();
759 : 202158 : Assume(chunk_count > 0);
760 : : // Iterate over the transactions in the linearization, which must match those in chunk.
761 : 225926 : while (true) {
762 : 225926 : DepGraphIndex idx = m_linearization[lin_idx];
763 : 225926 : GraphIndex graph_idx = m_mapping[idx];
764 : 225926 : auto& entry = graph.m_entries[graph_idx];
765 : 225926 : entry.m_main_lin_index = lin_idx++;
766 : 225926 : entry.m_main_chunk_feerate = FeePerWeight::FromFeeFrac(chunk.feerate);
767 : 225926 : Assume(chunk.transactions[idx]);
768 : 225926 : chunk.transactions.Reset(idx);
769 [ + + ]: 225926 : if (chunk.transactions.None()) {
770 : : // Last transaction in the chunk.
771 [ + + + + ]: 202158 : if (chunk_count == 1 && chunk_idx + 1 == chunking.NumChunksLeft()) {
772 : : // If this is the final chunk of the cluster, and it contains just a single
773 : : // transaction (which will always be true for the very common singleton
774 : : // clusters), store the special value -1 as chunk count.
775 : : chunk_count = LinearizationIndex(-1);
776 : : }
777 : 202158 : graph.CreateChunkData(graph_idx, chunk_count);
778 : 202158 : break;
779 : : }
780 : : }
781 : : }
782 : 168987 : }
783 : 372198 : }
784 : :
785 : 86828 : void Cluster::GetConflicts(const TxGraphImpl& graph, std::vector<Cluster*>& out) const noexcept
786 : : {
787 : 86828 : Assume(m_level == 1);
788 [ + + ]: 241741 : for (auto i : m_linearization) {
789 [ + + ]: 154913 : auto& entry = graph.m_entries[m_mapping[i]];
790 : : // For every transaction Entry in this Cluster, if it also exists in a lower-level Cluster,
791 : : // then that Cluster conflicts.
792 [ + + ]: 154913 : if (entry.m_locator[0].IsPresent()) {
793 : 67091 : out.push_back(entry.m_locator[0].cluster);
794 : : }
795 : : }
796 : 86828 : }
797 : :
798 : 11975 : std::vector<Cluster*> TxGraphImpl::GetConflicts() const noexcept
799 : : {
800 : 11975 : Assume(GetTopLevel() == 1);
801 : 11975 : auto& clusterset = GetClusterSet(1);
802 : 11975 : std::vector<Cluster*> ret;
803 : : // All main Clusters containing transactions in m_removed (so (P,R) ones) are conflicts.
804 [ + + ]: 24190 : for (auto i : clusterset.m_removed) {
805 [ + + ]: 12215 : auto& entry = m_entries[i];
806 [ + + ]: 12215 : if (entry.m_locator[0].IsPresent()) {
807 : 11873 : ret.push_back(entry.m_locator[0].cluster);
808 : : }
809 : : }
810 : : // Then go over all Clusters at this level, and find their conflicts (the (P,P) ones).
811 [ + + ]: 83825 : for (int quality = 0; quality < int(QualityLevel::NONE); ++quality) {
812 : 71850 : auto& clusters = clusterset.m_clusters[quality];
813 [ + + ]: 158678 : for (const auto& cluster : clusters) {
814 : 86828 : cluster->GetConflicts(*this, ret);
815 : : }
816 : : }
817 : : // Deduplicate the result (the same Cluster may appear multiple times).
818 : 423518 : std::sort(ret.begin(), ret.end(), [](Cluster* a, Cluster* b) noexcept { return CompareClusters(a, b) < 0; });
819 : 11975 : ret.erase(std::unique(ret.begin(), ret.end()), ret.end());
820 : 11975 : return ret;
821 : : }
822 : :
823 : 26855 : Cluster* Cluster::CopyToStaging(TxGraphImpl& graph) const noexcept
824 : : {
825 : : // Construct an empty Cluster.
826 : 26855 : auto ret = std::make_unique<Cluster>(graph.m_next_sequence_counter++);
827 : 26855 : auto ptr = ret.get();
828 : : // Copy depgraph, mapping, and linearization/
829 : 26855 : ptr->m_depgraph = m_depgraph;
830 : 26855 : ptr->m_mapping = m_mapping;
831 : 26855 : ptr->m_linearization = m_linearization;
832 : : // Insert the new Cluster into the graph.
833 : 26855 : graph.InsertCluster(1, std::move(ret), m_quality);
834 : : // Update its Locators.
835 : 26855 : ptr->Updated(graph);
836 : 53710 : return ptr;
837 : 26855 : }
838 : :
839 : 67654 : void Cluster::ApplyRemovals(TxGraphImpl& graph, std::span<GraphIndex>& to_remove) noexcept
840 : : {
841 : : // Iterate over the prefix of to_remove that applies to this cluster.
842 : 67654 : Assume(!to_remove.empty());
843 : 67654 : SetType todo;
844 : 124684 : do {
845 : 124684 : GraphIndex idx = to_remove.front();
846 : 124684 : Assume(idx < graph.m_entries.size());
847 [ + + ]: 124684 : auto& entry = graph.m_entries[idx];
848 : 124684 : auto& locator = entry.m_locator[m_level];
849 : : // Stop once we hit an entry that applies to another Cluster.
850 [ + + ]: 124684 : if (locator.cluster != this) break;
851 : : // - Remember it in a set of to-remove DepGraphIndexes.
852 : 74490 : todo.Set(locator.index);
853 : : // - Remove from m_mapping. This isn't strictly necessary as unused positions in m_mapping
854 : : // are just never accessed, but set it to -1 here to increase the ability to detect a bug
855 : : // that causes it to be accessed regardless.
856 [ + + ]: 74490 : m_mapping[locator.index] = GraphIndex(-1);
857 : : // - Remove its linearization index from the Entry (if in main).
858 [ + + ]: 74490 : if (m_level == 0) {
859 : 51552 : entry.m_main_lin_index = LinearizationIndex(-1);
860 : : }
861 : : // - Mark it as missing/removed in the Entry's locator.
862 : 74490 : graph.ClearLocator(m_level, idx, m_quality == QualityLevel::OVERSIZED_SINGLETON);
863 [ + + ]: 74490 : to_remove = to_remove.subspan(1);
864 [ + + ]: 74490 : } while(!to_remove.empty());
865 : :
866 : 67654 : auto quality = m_quality;
867 : 67654 : Assume(todo.Any());
868 : : // Wipe from the Cluster's DepGraph (this is O(n) regardless of the number of entries
869 : : // removed, so we benefit from batching all the removals).
870 : 67654 : m_depgraph.RemoveTransactions(todo);
871 : 67654 : m_mapping.resize(m_depgraph.PositionRange());
872 : :
873 : : // First remove all removals at the end of the linearization.
874 [ + + + + ]: 206003 : while (!m_linearization.empty() && todo[m_linearization.back()]) {
875 : 70695 : todo.Reset(m_linearization.back());
876 : 70695 : m_linearization.pop_back();
877 : : }
878 [ + + ]: 67654 : if (todo.None()) {
879 : : // If no further removals remain, and thus all removals were at the end, we may be able
880 : : // to leave the cluster at a better quality level.
881 [ + + ]: 66331 : if (IsAcceptable(/*after_split=*/true)) {
882 : : quality = QualityLevel::NEEDS_SPLIT_ACCEPTABLE;
883 : : } else {
884 : : quality = QualityLevel::NEEDS_SPLIT;
885 : : }
886 : : } else {
887 : : // If more removals remain, filter those out of m_linearization.
888 : 1327 : m_linearization.erase(std::remove_if(
889 : : m_linearization.begin(),
890 : : m_linearization.end(),
891 : 20196 : [&](auto pos) { return todo[pos]; }), m_linearization.end());
892 : 1327 : quality = QualityLevel::NEEDS_SPLIT;
893 : : }
894 : 67654 : graph.SetClusterQuality(m_level, m_quality, m_setindex, quality);
895 : 67654 : Updated(graph);
896 : 67654 : }
897 : :
898 : 3487 : void Cluster::Clear(TxGraphImpl& graph) noexcept
899 : : {
900 [ + + ]: 8478 : for (auto i : m_linearization) {
901 : 4991 : graph.ClearLocator(m_level, m_mapping[i], m_quality == QualityLevel::OVERSIZED_SINGLETON);
902 : : }
903 : 3487 : m_depgraph = {};
904 [ + - ]: 3487 : m_linearization.clear();
905 [ + - ]: 3487 : m_mapping.clear();
906 : 3487 : }
907 : :
908 : 10500 : void Cluster::MoveToMain(TxGraphImpl& graph) noexcept
909 : : {
910 : 10500 : Assume(m_level == 1);
911 [ + + ]: 23329 : for (auto i : m_linearization) {
912 : 12829 : GraphIndex idx = m_mapping[i];
913 : 12829 : auto& entry = graph.m_entries[idx];
914 : 12829 : entry.m_locator[1].SetMissing();
915 : : }
916 : 10500 : auto quality = m_quality;
917 : 10500 : auto cluster = graph.ExtractCluster(1, quality, m_setindex);
918 : 10500 : graph.InsertCluster(0, std::move(cluster), quality);
919 : 10500 : Updated(graph);
920 : 10500 : }
921 : :
922 : 129176 : void Cluster::AppendChunkFeerates(std::vector<FeeFrac>& ret) const noexcept
923 : : {
924 : 129176 : auto chunk_feerates = ChunkLinearization(m_depgraph, m_linearization);
925 : 129176 : ret.reserve(ret.size() + chunk_feerates.size());
926 : 129176 : ret.insert(ret.end(), chunk_feerates.begin(), chunk_feerates.end());
927 : 129176 : }
928 : :
929 : 92302 : uint64_t Cluster::AppendTrimData(std::vector<TrimTxData>& ret, std::vector<std::pair<GraphIndex, GraphIndex>>& deps) const noexcept
930 : : {
931 : 92302 : const LinearizationChunking linchunking(m_depgraph, m_linearization);
932 : 92302 : LinearizationIndex pos{0};
933 : 92302 : uint64_t size{0};
934 : 92302 : auto prev_index = GraphIndex(-1);
935 : : // Iterate over the chunks of this cluster's linearization.
936 [ + + ]: 216180 : for (unsigned i = 0; i < linchunking.NumChunksLeft(); ++i) {
937 : 123878 : const auto& [chunk, chunk_feerate] = linchunking.GetChunk(i);
938 : : // Iterate over the transactions of that chunk, in linearization order.
939 : 123878 : auto chunk_tx_count = chunk.Count();
940 [ + + ]: 291484 : for (unsigned j = 0; j < chunk_tx_count; ++j) {
941 : 167606 : auto cluster_idx = m_linearization[pos];
942 : : // The transaction must appear in the chunk.
943 : 167606 : Assume(chunk[cluster_idx]);
944 : : // Construct a new element in ret.
945 : 167606 : auto& entry = ret.emplace_back();
946 [ + + ]: 167606 : entry.m_chunk_feerate = FeePerWeight::FromFeeFrac(chunk_feerate);
947 [ + + ]: 167606 : entry.m_index = m_mapping[cluster_idx];
948 : : // If this is not the first transaction of the cluster linearization, it has an
949 : : // implicit dependency on its predecessor.
950 [ + + ]: 167606 : if (pos != 0) deps.emplace_back(prev_index, entry.m_index);
951 : 167606 : prev_index = entry.m_index;
952 : 167606 : entry.m_tx_size = m_depgraph.FeeRate(cluster_idx).size;
953 : 167606 : size += entry.m_tx_size;
954 : 167606 : ++pos;
955 : : }
956 : : }
957 : 92302 : return size;
958 : 92302 : }
959 : :
960 : 62948 : bool Cluster::Split(TxGraphImpl& graph) noexcept
961 : : {
962 : : // This function can only be called when the Cluster needs splitting.
963 : 62948 : Assume(NeedsSplitting());
964 : : // Determine the new quality the split-off Clusters will have.
965 [ + - ]: 62948 : QualityLevel new_quality = IsAcceptable(/*after_split=*/true) ? QualityLevel::ACCEPTABLE
966 : : : QualityLevel::NEEDS_RELINEARIZE;
967 : : // If we're going to produce ACCEPTABLE clusters (i.e., when in NEEDS_SPLIT_ACCEPTABLE), we
968 : : // need to post-linearize to make sure the split-out versions are all connected (as
969 : : // connectivity may have changed by removing part of the cluster). This could be done on each
970 : : // resulting split-out cluster separately, but it is simpler to do it once up front before
971 : : // splitting. This step is not necessary if the resulting clusters are NEEDS_RELINEARIZE, as
972 : : // they will be post-linearized anyway in MakeAcceptable().
973 : : if (new_quality == QualityLevel::ACCEPTABLE) {
974 : 38581 : PostLinearize(m_depgraph, m_linearization);
975 : : }
976 : : /** Which positions are still left in this Cluster. */
977 : 62948 : auto todo = m_depgraph.Positions();
978 : : /** Mapping from transaction positions in this Cluster to the Cluster where it ends up, and
979 : : * its position therein. */
980 : 62948 : std::vector<std::pair<Cluster*, DepGraphIndex>> remap(m_depgraph.PositionRange());
981 : 62948 : std::vector<Cluster*> new_clusters;
982 : 62948 : bool first{true};
983 : : // Iterate over the connected components of this Cluster's m_depgraph.
984 [ + + ]: 67387 : while (todo.Any()) {
985 : 6828 : auto component = m_depgraph.FindConnectedComponent(todo);
986 [ + + ]: 6828 : auto split_quality = component.Count() <= 2 ? QualityLevel::OPTIMAL : new_quality;
987 [ + + ]: 6828 : if (first && component == todo) {
988 : : // The existing Cluster is an entire component. Leave it be, but update its quality.
989 [ - + ]: 2389 : Assume(todo == m_depgraph.Positions());
990 : 2389 : graph.SetClusterQuality(m_level, m_quality, m_setindex, split_quality);
991 : : // If this made the quality ACCEPTABLE or OPTIMAL, we need to compute and cache its
992 : : // chunking.
993 : 2389 : Updated(graph);
994 : 2389 : return false;
995 : : }
996 : 4439 : first = false;
997 : : // Construct a new Cluster to hold the found component.
998 : 4439 : auto new_cluster = std::make_unique<Cluster>(graph.m_next_sequence_counter++);
999 : 4439 : new_clusters.push_back(new_cluster.get());
1000 : : // Remember that all the component's transactions go to this new Cluster. The positions
1001 : : // will be determined below, so use -1 for now.
1002 [ + - + + ]: 30489 : for (auto i : component) {
1003 : 21611 : remap[i] = {new_cluster.get(), DepGraphIndex(-1)};
1004 : : }
1005 : 4439 : graph.InsertCluster(m_level, std::move(new_cluster), split_quality);
1006 : 4439 : todo -= component;
1007 : 4439 : }
1008 : : // Redistribute the transactions.
1009 [ + + ]: 82170 : for (auto i : m_linearization) {
1010 : : /** The cluster which transaction originally in position i is moved to. */
1011 : 21611 : Cluster* new_cluster = remap[i].first;
1012 : : // Copy the transaction to the new cluster's depgraph, and remember the position.
1013 : 21611 : remap[i].second = new_cluster->m_depgraph.AddTransaction(m_depgraph.FeeRate(i));
1014 : : // Create new mapping entry.
1015 : 21611 : new_cluster->m_mapping.push_back(m_mapping[i]);
1016 : : // Create a new linearization entry. As we're only appending transactions, they equal the
1017 : : // DepGraphIndex.
1018 : 21611 : new_cluster->m_linearization.push_back(remap[i].second);
1019 : : }
1020 : : // Redistribute the dependencies.
1021 [ + + ]: 82170 : for (auto i : m_linearization) {
1022 : : /** The cluster transaction in position i is moved to. */
1023 : 21611 : Cluster* new_cluster = remap[i].first;
1024 : : // Copy its parents, translating positions.
1025 : 21611 : SetType new_parents;
1026 [ + + + + ]: 54528 : for (auto par : m_depgraph.GetReducedParents(i)) new_parents.Set(remap[par].second);
1027 : 21611 : new_cluster->m_depgraph.AddDependencies(new_parents, remap[i].second);
1028 : : }
1029 : : // Update all the Locators of moved transactions.
1030 [ + + ]: 64998 : for (Cluster* new_cluster : new_clusters) {
1031 : 4439 : new_cluster->Updated(graph);
1032 : : }
1033 : : // Wipe this Cluster, and return that it needs to be deleted.
1034 : 60559 : m_depgraph = DepGraph<SetType>{};
1035 [ + + ]: 60559 : m_mapping.clear();
1036 [ + + ]: 64148 : m_linearization.clear();
1037 : : return true;
1038 : 62948 : }
1039 : :
1040 : 44642 : void Cluster::Merge(TxGraphImpl& graph, Cluster& other) noexcept
1041 : : {
1042 : : /** Vector to store the positions in this Cluster for each position in other. */
1043 : 44642 : std::vector<DepGraphIndex> remap(other.m_depgraph.PositionRange());
1044 : : // Iterate over all transactions in the other Cluster (the one being absorbed).
1045 [ + + ]: 91909 : for (auto pos : other.m_linearization) {
1046 : 47267 : auto idx = other.m_mapping[pos];
1047 : : // Copy the transaction into this Cluster, and remember its position.
1048 : 47267 : auto new_pos = m_depgraph.AddTransaction(other.m_depgraph.FeeRate(pos));
1049 [ + + ]: 47267 : remap[pos] = new_pos;
1050 [ + + ]: 47267 : if (new_pos == m_mapping.size()) {
1051 : 45512 : m_mapping.push_back(idx);
1052 : : } else {
1053 : 1755 : m_mapping[new_pos] = idx;
1054 : : }
1055 : 47267 : m_linearization.push_back(new_pos);
1056 : : // Copy the transaction's dependencies, translating them using remap. Note that since
1057 : : // pos iterates over other.m_linearization, which is in topological order, all parents
1058 : : // of pos should already be in remap.
1059 : 47267 : SetType parents;
1060 [ + + + + ]: 52297 : for (auto par : other.m_depgraph.GetReducedParents(pos)) {
1061 : 2713 : parents.Set(remap[par]);
1062 : : }
1063 : 47267 : m_depgraph.AddDependencies(parents, remap[pos]);
1064 : : // Update the transaction's Locator. There is no need to call Updated() to update chunk
1065 : : // feerates, as Updated() will be invoked by Cluster::ApplyDependencies on the resulting
1066 : : // merged Cluster later anyway).
1067 [ + + ]: 47267 : auto& entry = graph.m_entries[idx];
1068 : : // Discard any potential ChunkData prior to modifying the Cluster (as that could
1069 : : // invalidate its ordering).
1070 [ + + ]: 47267 : if (m_level == 0) graph.ClearChunkData(entry);
1071 : 47267 : entry.m_locator[m_level].SetPresent(this, new_pos);
1072 : : }
1073 : : // Purge the other Cluster, now that everything has been moved.
1074 : 44642 : other.m_depgraph = DepGraph<SetType>{};
1075 [ + - ]: 44642 : other.m_linearization.clear();
1076 [ + - ]: 89284 : other.m_mapping.clear();
1077 : 44642 : }
1078 : :
1079 : 14580 : void Cluster::ApplyDependencies(TxGraphImpl& graph, std::span<std::pair<GraphIndex, GraphIndex>> to_apply) noexcept
1080 : : {
1081 : : // This function is invoked by TxGraphImpl::ApplyDependencies after merging groups of Clusters
1082 : : // between which dependencies are added, which simply concatenates their linearizations. Invoke
1083 : : // PostLinearize, which has the effect that the linearization becomes a merge-sort of the
1084 : : // constituent linearizations. Do this here rather than in Cluster::Merge, because this
1085 : : // function is only invoked once per merged Cluster, rather than once per constituent one.
1086 : : // This concatenation + post-linearization could be replaced with an explicit merge-sort.
1087 : 14580 : PostLinearize(m_depgraph, m_linearization);
1088 : :
1089 : : // Sort the list of dependencies to apply by child, so those can be applied in batch.
1090 [ + + + + : 341702 : std::sort(to_apply.begin(), to_apply.end(), [](auto& a, auto& b) { return a.second < b.second; });
+ + + + +
+ + + + +
+ + + + +
+ - - +
+ ]
1091 : : // Iterate over groups of to-be-added dependencies with the same child.
1092 : 14580 : auto it = to_apply.begin();
1093 [ + + ]: 59137 : while (it != to_apply.end()) {
1094 : 44557 : auto& first_child = graph.m_entries[it->second].m_locator[m_level];
1095 : 44557 : const auto child_idx = first_child.index;
1096 : : // Iterate over all to-be-added dependencies within that same child, gather the relevant
1097 : : // parents.
1098 : 44557 : SetType parents;
1099 [ + + ]: 122702 : while (it != to_apply.end()) {
1100 [ + - ]: 108122 : auto& child = graph.m_entries[it->second].m_locator[m_level];
1101 : 108122 : auto& parent = graph.m_entries[it->first].m_locator[m_level];
1102 [ + - - + ]: 108122 : Assume(child.cluster == this && parent.cluster == this);
1103 [ + + ]: 108122 : if (child.index != child_idx) break;
1104 : 78145 : parents.Set(parent.index);
1105 : 78145 : ++it;
1106 : : }
1107 : : // Push all dependencies to the underlying DepGraph. Note that this is O(N) in the size of
1108 : : // the cluster, regardless of the number of parents being added, so batching them together
1109 : : // has a performance benefit.
1110 : 44557 : m_depgraph.AddDependencies(parents, child_idx);
1111 : : }
1112 : :
1113 : : // Finally fix the linearization, as the new dependencies may have invalidated the
1114 : : // linearization, and post-linearize it to fix up the worst problems with it.
1115 : 14580 : FixLinearization(m_depgraph, m_linearization);
1116 : 14580 : PostLinearize(m_depgraph, m_linearization);
1117 : 14580 : Assume(!NeedsSplitting());
1118 : 14580 : Assume(!IsOversized());
1119 [ + + ]: 14580 : if (IsAcceptable()) {
1120 : 9872 : graph.SetClusterQuality(m_level, m_quality, m_setindex, QualityLevel::NEEDS_RELINEARIZE);
1121 : : }
1122 : :
1123 : : // Finally push the changes to graph.m_entries.
1124 : 14580 : Updated(graph);
1125 : 14580 : }
1126 : :
1127 : 10416 : TxGraphImpl::~TxGraphImpl() noexcept
1128 : : {
1129 : : // If Refs outlive the TxGraphImpl they refer to, unlink them, so that their destructor does not
1130 : : // try to reach into a non-existing TxGraphImpl anymore.
1131 [ + + ]: 199404 : for (auto& entry : m_entries) {
1132 [ + + ]: 194196 : if (entry.m_ref != nullptr) {
1133 : 182162 : GetRefGraph(*entry.m_ref) = nullptr;
1134 : : }
1135 : : }
1136 : 10416 : }
1137 : :
1138 : 214518 : std::unique_ptr<Cluster> TxGraphImpl::ExtractCluster(int level, QualityLevel quality, ClusterSetIndex setindex) noexcept
1139 : : {
1140 : 214518 : Assume(quality != QualityLevel::NONE);
1141 : :
1142 : 214518 : auto& clusterset = GetClusterSet(level);
1143 : 214518 : auto& quality_clusters = clusterset.m_clusters[int(quality)];
1144 : 214518 : Assume(setindex < quality_clusters.size());
1145 : :
1146 : : // Extract the Cluster-owning unique_ptr.
1147 [ + + ]: 214518 : std::unique_ptr<Cluster> ret = std::move(quality_clusters[setindex]);
1148 [ + + ]: 214518 : ret->m_quality = QualityLevel::NONE;
1149 : 214518 : ret->m_setindex = ClusterSetIndex(-1);
1150 : 214518 : ret->m_level = -1;
1151 : :
1152 : : // Clean up space in quality_cluster.
1153 [ + + ]: 214518 : auto max_setindex = quality_clusters.size() - 1;
1154 [ + + ]: 214518 : if (setindex != max_setindex) {
1155 : : // If the cluster was not the last element of quality_clusters, move that to take its place.
1156 : 97379 : quality_clusters.back()->m_setindex = setindex;
1157 : 97379 : quality_clusters.back()->m_level = level;
1158 : 97379 : quality_clusters[setindex] = std::move(quality_clusters.back());
1159 : : }
1160 : : // The last element of quality_clusters is now unused; drop it.
1161 : 214518 : quality_clusters.pop_back();
1162 : :
1163 : 214518 : return ret;
1164 : : }
1165 : :
1166 : 365254 : ClusterSetIndex TxGraphImpl::InsertCluster(int level, std::unique_ptr<Cluster>&& cluster, QualityLevel quality) noexcept
1167 : : {
1168 : : // Cannot insert with quality level NONE (as that would mean not inserted).
1169 : 365254 : Assume(quality != QualityLevel::NONE);
1170 : : // The passed-in Cluster must not currently be in the TxGraphImpl.
1171 : 365254 : Assume(cluster->m_quality == QualityLevel::NONE);
1172 : :
1173 : : // Append it at the end of the relevant TxGraphImpl::m_cluster.
1174 : 365254 : auto& clusterset = GetClusterSet(level);
1175 : 365254 : auto& quality_clusters = clusterset.m_clusters[int(quality)];
1176 : 365254 : ClusterSetIndex ret = quality_clusters.size();
1177 : 365254 : cluster->m_quality = quality;
1178 : 365254 : cluster->m_setindex = ret;
1179 : 365254 : cluster->m_level = level;
1180 : 365254 : quality_clusters.push_back(std::move(cluster));
1181 : 365254 : return ret;
1182 : : }
1183 : :
1184 : 96667 : void TxGraphImpl::SetClusterQuality(int level, QualityLevel old_quality, ClusterSetIndex old_index, QualityLevel new_quality) noexcept
1185 : : {
1186 : 96667 : Assume(new_quality != QualityLevel::NONE);
1187 : :
1188 : : // Don't do anything if the quality did not change.
1189 [ + + ]: 96667 : if (old_quality == new_quality) return;
1190 : : // Extract the cluster from where it currently resides.
1191 : 95330 : auto cluster_ptr = ExtractCluster(level, old_quality, old_index);
1192 : : // And re-insert it where it belongs.
1193 : 95330 : InsertCluster(level, std::move(cluster_ptr), new_quality);
1194 : 95330 : }
1195 : :
1196 : 108688 : void TxGraphImpl::DeleteCluster(Cluster& cluster) noexcept
1197 : : {
1198 : : // Extract the cluster from where it currently resides.
1199 : 108688 : auto cluster_ptr = ExtractCluster(cluster.m_level, cluster.m_quality, cluster.m_setindex);
1200 : : // And throw it away.
1201 [ + - ]: 108688 : cluster_ptr.reset();
1202 : 108688 : }
1203 : :
1204 : 4096755 : Cluster* TxGraphImpl::FindCluster(GraphIndex idx, int level) const noexcept
1205 : : {
1206 [ + - - + ]: 4096755 : Assume(level >= 0 && level <= GetTopLevel());
1207 : 4096755 : auto& entry = m_entries[idx];
1208 : : // Search the entry's locators from top to bottom.
1209 [ + + ]: 4798920 : for (int l = level; l >= 0; --l) {
1210 : : // If the locator is missing, dig deeper; it may exist at a lower level and therefore be
1211 : : // implicitly existing at this level too.
1212 [ + + ]: 5380110 : if (entry.m_locator[l].IsMissing()) continue;
1213 : : // If the locator has the entry marked as explicitly removed, stop.
1214 [ + + ]: 3975780 : if (entry.m_locator[l].IsRemoved()) break;
1215 : : // Otherwise, we have found the topmost ClusterSet that contains this entry.
1216 : : return entry.m_locator[l].cluster;
1217 : : }
1218 : : // If no non-empty locator was found, or an explicitly removed was hit, return nothing.
1219 : : return nullptr;
1220 : : }
1221 : :
1222 : 46995 : Cluster* TxGraphImpl::PullIn(Cluster* cluster) noexcept
1223 : : {
1224 : 46995 : int to_level = GetTopLevel();
1225 : 46995 : Assume(to_level == 1);
1226 : 46995 : int level = cluster->m_level;
1227 : 46995 : Assume(level <= to_level);
1228 : : // Copy the Cluster from main to staging, if it's not already there.
1229 [ + + ]: 46995 : if (level == 0) {
1230 : : // Make the Cluster Acceptable before copying. This isn't strictly necessary, but doing it
1231 : : // now avoids doing double work later.
1232 : 26855 : MakeAcceptable(*cluster);
1233 : 26855 : cluster = cluster->CopyToStaging(*this);
1234 : : }
1235 : 46995 : return cluster;
1236 : : }
1237 : :
1238 : 434580 : void TxGraphImpl::ApplyRemovals(int up_to_level) noexcept
1239 : : {
1240 [ + - - + ]: 434580 : Assume(up_to_level >= 0 && up_to_level <= GetTopLevel());
1241 [ + + ]: 924817 : for (int level = 0; level <= up_to_level; ++level) {
1242 : 490237 : auto& clusterset = GetClusterSet(level);
1243 : 490237 : auto& to_remove = clusterset.m_to_remove;
1244 : : // Skip if there is nothing to remove in this level.
1245 [ + + ]: 490237 : if (to_remove.empty()) continue;
1246 : : // Pull in all Clusters that are not in staging.
1247 [ + + ]: 18860 : if (level == 1) {
1248 [ + + ]: 31720 : for (GraphIndex index : to_remove) {
1249 : 26902 : auto cluster = FindCluster(index, level);
1250 [ + + ]: 26902 : if (cluster != nullptr) PullIn(cluster);
1251 : : }
1252 : : }
1253 : : // Group the set of to-be-removed entries by Cluster::m_sequence.
1254 : 18860 : std::sort(to_remove.begin(), to_remove.end(), [&](GraphIndex a, GraphIndex b) noexcept {
1255 : 277937 : Cluster* cluster_a = m_entries[a].m_locator[level].cluster;
1256 : 277937 : Cluster* cluster_b = m_entries[b].m_locator[level].cluster;
1257 : 277937 : return CompareClusters(cluster_a, cluster_b) < 0;
1258 : : });
1259 : : // Process per Cluster.
1260 : 18860 : std::span to_remove_span{to_remove};
1261 [ + + ]: 94475 : while (!to_remove_span.empty()) {
1262 [ + + ]: 75615 : Cluster* cluster = m_entries[to_remove_span.front()].m_locator[level].cluster;
1263 [ + + ]: 75615 : if (cluster != nullptr) {
1264 : : // If the first to_remove_span entry's Cluster exists, hand to_remove_span to it, so it
1265 : : // can pop off whatever applies to it.
1266 : 67654 : cluster->ApplyRemovals(*this, to_remove_span);
1267 : : } else {
1268 : : // Otherwise, skip this already-removed entry. This may happen when
1269 : : // RemoveTransaction was called twice on the same Ref, for example.
1270 : 7961 : to_remove_span = to_remove_span.subspan(1);
1271 : : }
1272 : : }
1273 [ + - ]: 509097 : to_remove.clear();
1274 : : }
1275 : 434580 : Compact();
1276 : 434580 : }
1277 : :
1278 : 24665 : void TxGraphImpl::SwapIndexes(GraphIndex a, GraphIndex b) noexcept
1279 : : {
1280 : 24665 : Assume(a < m_entries.size());
1281 : 24665 : Assume(b < m_entries.size());
1282 : : // Swap the Entry objects.
1283 : 24665 : std::swap(m_entries[a], m_entries[b]);
1284 : : // Iterate over both objects.
1285 [ + + ]: 73995 : for (int i = 0; i < 2; ++i) {
1286 [ + + ]: 49330 : GraphIndex idx = i ? b : a;
1287 [ + + ]: 49330 : Entry& entry = m_entries[idx];
1288 : : // Update linked Ref, if any exists.
1289 [ + + ]: 49330 : if (entry.m_ref) GetRefIndex(*entry.m_ref) = idx;
1290 : : // Update linked chunk index entries, if any exist.
1291 [ + + ]: 49330 : if (entry.m_main_chunkindex_iterator != m_main_chunkindex.end()) {
1292 : 13700 : entry.m_main_chunkindex_iterator->m_graph_index = idx;
1293 : : }
1294 : : // Update the locators for both levels. The rest of the Entry information will not change,
1295 : : // so no need to invoke Cluster::Updated().
1296 [ + + ]: 147990 : for (int level = 0; level < MAX_LEVELS; ++level) {
1297 : 98660 : Locator& locator = entry.m_locator[level];
1298 [ + + ]: 98660 : if (locator.IsPresent()) {
1299 : 16673 : locator.cluster->UpdateMapping(locator.index, idx);
1300 : : }
1301 : : }
1302 : : }
1303 : 24665 : }
1304 : :
1305 : 512992 : void TxGraphImpl::Compact() noexcept
1306 : : {
1307 : : // We cannot compact while any to-be-applied operations or staged removals remain as we'd need
1308 : : // to rewrite them. It is easier to delay the compaction until they have been applied.
1309 [ + + ]: 512992 : if (!m_main_clusterset.m_deps_to_add.empty()) return;
1310 [ + + ]: 390015 : if (!m_main_clusterset.m_to_remove.empty()) return;
1311 : 388577 : Assume(m_main_clusterset.m_removed.empty()); // non-staging m_removed is always empty
1312 [ + + ]: 388577 : if (m_staging_clusterset.has_value()) {
1313 [ + + ]: 164379 : if (!m_staging_clusterset->m_deps_to_add.empty()) return;
1314 [ + + ]: 122096 : if (!m_staging_clusterset->m_to_remove.empty()) return;
1315 [ + + ]: 119332 : if (!m_staging_clusterset->m_removed.empty()) return;
1316 : : }
1317 : :
1318 : : // Release memory used by discarded ChunkData index entries.
1319 : 288246 : ClearShrink(m_main_chunkindex_discarded);
1320 : :
1321 : : // Sort the GraphIndexes that need to be cleaned up. They are sorted in reverse, so the last
1322 : : // ones get processed first. This means earlier-processed GraphIndexes will not cause moving of
1323 : : // later-processed ones during the "swap with end of m_entries" step below (which might
1324 : : // invalidate them).
1325 : 288246 : std::sort(m_unlinked.begin(), m_unlinked.end(), std::greater{});
1326 : :
1327 : 288246 : auto last = GraphIndex(-1);
1328 [ + + ]: 322180 : for (GraphIndex idx : m_unlinked) {
1329 : : // m_unlinked should never contain the same GraphIndex twice (the code below would fail
1330 : : // if so, because GraphIndexes get invalidated by removing them).
1331 : 33934 : Assume(idx != last);
1332 : 33934 : last = idx;
1333 : :
1334 : : // Make sure the entry is unlinked.
1335 : 33934 : Entry& entry = m_entries[idx];
1336 : 33934 : Assume(entry.m_ref == nullptr);
1337 : : // Make sure the entry does not occur in the graph.
1338 [ + + ]: 101802 : for (int level = 0; level < MAX_LEVELS; ++level) {
1339 : 67868 : Assume(!entry.m_locator[level].IsPresent());
1340 : : }
1341 : :
1342 : : // Move the entry to the end.
1343 [ + + ]: 33934 : if (idx != m_entries.size() - 1) SwapIndexes(idx, m_entries.size() - 1);
1344 : : // Drop the entry for idx, now that it is at the end.
1345 : 33934 : m_entries.pop_back();
1346 : : }
1347 [ + + ]: 288246 : m_unlinked.clear();
1348 : : }
1349 : :
1350 : 62948 : void TxGraphImpl::Split(Cluster& cluster) noexcept
1351 : : {
1352 : : // To split a Cluster, first make sure all removals are applied (as we might need to split
1353 : : // again afterwards otherwise).
1354 : 62948 : ApplyRemovals(cluster.m_level);
1355 : 62948 : bool del = cluster.Split(*this);
1356 [ + + ]: 62948 : if (del) {
1357 : : // Cluster::Split reports whether the Cluster is to be deleted.
1358 : 60559 : DeleteCluster(cluster);
1359 : : }
1360 : 62948 : }
1361 : :
1362 : 41020 : void TxGraphImpl::SplitAll(int up_to_level) noexcept
1363 : : {
1364 [ + - - + ]: 41020 : Assume(up_to_level >= 0 && up_to_level <= GetTopLevel());
1365 : : // Before splitting all Cluster, first make sure all removals are applied.
1366 : 41020 : ApplyRemovals(up_to_level);
1367 [ + + ]: 93411 : for (int level = 0; level <= up_to_level; ++level) {
1368 [ + + ]: 157173 : for (auto quality : {QualityLevel::NEEDS_SPLIT, QualityLevel::NEEDS_SPLIT_ACCEPTABLE}) {
1369 : 104782 : auto& queue = GetClusterSet(level).m_clusters[int(quality)];
1370 [ + + ]: 167730 : while (!queue.empty()) {
1371 : 62948 : Split(*queue.back().get());
1372 : : }
1373 : : }
1374 : : }
1375 : 41020 : }
1376 : :
1377 : 2934508 : void TxGraphImpl::GroupClusters(int level) noexcept
1378 : : {
1379 : 2934508 : auto& clusterset = GetClusterSet(level);
1380 : : // If the groupings have been computed already, nothing is left to be done.
1381 [ + + ]: 2934508 : if (clusterset.m_group_data.has_value()) return;
1382 : :
1383 : : // Before computing which Clusters need to be merged together, first apply all removals and
1384 : : // split the Clusters into connected components. If we would group first, we might end up
1385 : : // with inefficient and/or oversized Clusters which just end up being split again anyway.
1386 : 31379 : SplitAll(level);
1387 : :
1388 : : /** Annotated clusters: an entry for each Cluster, together with the sequence number for the
1389 : : * representative for the partition it is in (initially its own, later that of the
1390 : : * to-be-merged group). */
1391 : 31379 : std::vector<std::pair<Cluster*, uint64_t>> an_clusters;
1392 : : /** Annotated dependencies: an entry for each m_deps_to_add entry (excluding ones that apply
1393 : : * to removed transactions), together with the sequence number of the representative root of
1394 : : * Clusters it applies to (initially that of the child Cluster, later that of the
1395 : : * to-be-merged group). */
1396 : 31379 : std::vector<std::pair<std::pair<GraphIndex, GraphIndex>, uint64_t>> an_deps;
1397 : :
1398 : : // Construct an an_clusters entry for every oversized cluster, including ones from levels below,
1399 : : // as they may be inherited in this one.
1400 [ + + ]: 74129 : for (int level_iter = 0; level_iter <= level; ++level_iter) {
1401 [ + + ]: 78400 : for (auto& cluster : GetClusterSet(level_iter).m_clusters[int(QualityLevel::OVERSIZED_SINGLETON)]) {
1402 : 35650 : auto graph_idx = cluster->GetClusterEntry(0);
1403 : 35650 : auto cur_cluster = FindCluster(graph_idx, level);
1404 [ + + ]: 35650 : if (cur_cluster == nullptr) continue;
1405 : 25050 : an_clusters.emplace_back(cur_cluster, cur_cluster->m_sequence);
1406 : : }
1407 : : }
1408 : :
1409 : : // Construct a an_clusters entry for every parent and child in the to-be-applied dependencies,
1410 : : // and an an_deps entry for each dependency to be applied.
1411 : 31379 : an_deps.reserve(clusterset.m_deps_to_add.size());
1412 [ + + ]: 315273 : for (const auto& [par, chl] : clusterset.m_deps_to_add) {
1413 : 283894 : auto par_cluster = FindCluster(par, level);
1414 : 283894 : auto chl_cluster = FindCluster(chl, level);
1415 : : // Skip dependencies for which the parent or child transaction is removed.
1416 [ + + + + ]: 283894 : if (par_cluster == nullptr || chl_cluster == nullptr) continue;
1417 : 235204 : an_clusters.emplace_back(par_cluster, par_cluster->m_sequence);
1418 : : // Do not include a duplicate when parent and child are identical, as it'll be removed
1419 : : // below anyway.
1420 [ + + ]: 235204 : if (chl_cluster != par_cluster) an_clusters.emplace_back(chl_cluster, chl_cluster->m_sequence);
1421 : : // Add entry to an_deps, using the child sequence number.
1422 : 235204 : an_deps.emplace_back(std::pair{par, chl}, chl_cluster->m_sequence);
1423 : : }
1424 : : // Sort and deduplicate an_clusters, so we end up with a sorted list of all involved Clusters
1425 : : // to which dependencies apply, or which are oversized.
1426 [ + + + + : 3139369 : std::sort(an_clusters.begin(), an_clusters.end(), [](auto& a, auto& b) noexcept { return a.second < b.second; });
+ + + + +
+ + + + +
+ + + + +
+ - - +
+ ]
1427 : 31379 : an_clusters.erase(std::unique(an_clusters.begin(), an_clusters.end()), an_clusters.end());
1428 : : // Sort an_deps by applying the same order to the involved child cluster.
1429 [ + + + + : 1263068 : std::sort(an_deps.begin(), an_deps.end(), [&](auto& a, auto& b) noexcept { return a.second < b.second; });
+ + + + +
+ + + + +
+ + + + +
+ - - +
+ ]
1430 : :
1431 : : // Run the union-find algorithm to to find partitions of the input Clusters which need to be
1432 : : // grouped together. See https://en.wikipedia.org/wiki/Disjoint-set_data_structure.
1433 : 31379 : {
1434 : : /** Each PartitionData entry contains information about a single input Cluster. */
1435 : 31379 : struct PartitionData
1436 : : {
1437 : : /** The sequence number of the cluster this holds information for. */
1438 : : uint64_t sequence;
1439 : : /** All PartitionData entries belonging to the same partition are organized in a tree.
1440 : : * Each element points to its parent, or to itself if it is the root. The root is then
1441 : : * a representative for the entire tree, and can be found by walking upwards from any
1442 : : * element. */
1443 : : PartitionData* parent;
1444 : : /** (only if this is a root, so when parent == this) An upper bound on the height of
1445 : : * tree for this partition. */
1446 : : unsigned rank;
1447 : : };
1448 : : /** Information about each input Cluster. Sorted by Cluster::m_sequence. */
1449 : 31379 : std::vector<PartitionData> partition_data;
1450 : :
1451 : : /** Given a Cluster, find its corresponding PartitionData. */
1452 : 367841 : auto locate_fn = [&](uint64_t sequence) noexcept -> PartitionData* {
1453 : 336462 : auto it = std::lower_bound(partition_data.begin(), partition_data.end(), sequence,
1454 [ + + ]: 1589562 : [](auto& a, uint64_t seq) noexcept { return a.sequence < seq; });
1455 : 336462 : Assume(it != partition_data.end());
1456 : 336462 : Assume(it->sequence == sequence);
1457 : 336462 : return &*it;
1458 : 31379 : };
1459 : :
1460 : : /** Given a PartitionData, find the root of the tree it is in (its representative). */
1461 : 444328 : static constexpr auto find_root_fn = [](PartitionData* data) noexcept -> PartitionData* {
1462 [ + + + + ]: 675568 : while (data->parent != data) {
1463 : : // Replace pointers to parents with pointers to grandparents.
1464 : : // See https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Finding_set_representatives.
1465 : 285904 : auto par = data->parent;
1466 : 285904 : data->parent = par->parent;
1467 : 285904 : data = par;
1468 : : }
1469 : 412949 : return data;
1470 : : };
1471 : :
1472 : : /** Given two PartitionDatas, union the partitions they are in, and return their
1473 : : * representative. */
1474 : 259324 : static constexpr auto union_fn = [](PartitionData* arg1, PartitionData* arg2) noexcept {
1475 : : // Find the roots of the trees, and bail out if they are already equal (which would
1476 : : // mean they are in the same partition already).
1477 [ + + ]: 479175 : auto rep1 = find_root_fn(arg1);
1478 : 227945 : auto rep2 = find_root_fn(arg2);
1479 [ + + ]: 227945 : if (rep1 == rep2) return rep1;
1480 : : // Pick the lower-rank root to become a child of the higher-rank one.
1481 : : // See https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Union_by_rank.
1482 [ + + ]: 127320 : if (rep1->rank < rep2->rank) std::swap(rep1, rep2);
1483 : 127320 : rep2->parent = rep1;
1484 : 127320 : rep1->rank += (rep1->rank == rep2->rank);
1485 : 127320 : return rep1;
1486 : : };
1487 : :
1488 : : // Start by initializing every Cluster as its own singleton partition.
1489 : 31379 : partition_data.resize(an_clusters.size());
1490 [ + + ]: 216383 : for (size_t i = 0; i < an_clusters.size(); ++i) {
1491 : 185004 : partition_data[i].sequence = an_clusters[i].first->m_sequence;
1492 : 185004 : partition_data[i].parent = &partition_data[i];
1493 : 185004 : partition_data[i].rank = 0;
1494 : : }
1495 : :
1496 : : // Run through all parent/child pairs in an_deps, and union the partitions their Clusters
1497 : : // are in.
1498 : 31379 : Cluster* last_chl_cluster{nullptr};
1499 : 31379 : PartitionData* last_partition{nullptr};
1500 [ + + ]: 266583 : for (const auto& [dep, _] : an_deps) {
1501 : 235204 : auto [par, chl] = dep;
1502 : 235204 : auto par_cluster = FindCluster(par, level);
1503 : 235204 : auto chl_cluster = FindCluster(chl, level);
1504 : 235204 : Assume(chl_cluster != nullptr && par_cluster != nullptr);
1505 : : // Nothing to do if parent and child are in the same Cluster.
1506 [ + + ]: 235204 : if (par_cluster == chl_cluster) continue;
1507 : 227945 : Assume(par != chl);
1508 [ + + ]: 227945 : if (chl_cluster == last_chl_cluster) {
1509 : : // If the child Clusters is the same as the previous iteration, union with the
1510 : : // tree they were in, avoiding the need for another lookup. Note that an_deps
1511 : : // is sorted by child Cluster, so batches with the same child are expected.
1512 : 119428 : last_partition = union_fn(locate_fn(par_cluster->m_sequence), last_partition);
1513 : : } else {
1514 : 108517 : last_chl_cluster = chl_cluster;
1515 : 108517 : last_partition = union_fn(locate_fn(par_cluster->m_sequence), locate_fn(chl_cluster->m_sequence));
1516 : : }
1517 : : }
1518 : :
1519 : : // Update the sequence numbers in an_clusters and an_deps to be those of the partition
1520 : : // representative.
1521 : 31379 : auto deps_it = an_deps.begin();
1522 [ + + ]: 216383 : for (size_t i = 0; i < partition_data.size(); ++i) {
1523 : 185004 : auto& data = partition_data[i];
1524 : : // Find the sequence of the representative of the partition Cluster i is in, and store
1525 : : // it with the Cluster.
1526 : 185004 : auto rep_seq = find_root_fn(&data)->sequence;
1527 : 185004 : an_clusters[i].second = rep_seq;
1528 : : // Find all dependencies whose child Cluster is Cluster i, and annotate them with rep.
1529 [ + + ]: 420208 : while (deps_it != an_deps.end()) {
1530 : 371668 : auto [par, chl] = deps_it->first;
1531 : 371668 : auto chl_cluster = FindCluster(chl, level);
1532 : 371668 : Assume(chl_cluster != nullptr);
1533 [ + + ]: 371668 : if (chl_cluster->m_sequence > data.sequence) break;
1534 : 235204 : deps_it->second = rep_seq;
1535 : 235204 : ++deps_it;
1536 : : }
1537 : : }
1538 : 31379 : }
1539 : :
1540 : : // Sort both an_clusters and an_deps by sequence number of the representative of the
1541 : : // partition they are in, grouping all those applying to the same partition together.
1542 [ - - - - : 895624 : std::sort(an_deps.begin(), an_deps.end(), [](auto& a, auto& b) noexcept { return a.second < b.second; });
+ + + + +
+ + + + +
+ + + + +
+ - - +
+ ]
1543 [ + + + + : 606648 : std::sort(an_clusters.begin(), an_clusters.end(), [](auto& a, auto& b) noexcept { return a.second < b.second; });
+ + + + +
+ + + + +
+ + + + +
+ - - +
+ ]
1544 : :
1545 : : // Translate the resulting cluster groups to the m_group_data structure, and the dependencies
1546 : : // back to m_deps_to_add.
1547 : 31379 : clusterset.m_group_data = GroupData{};
1548 : 31379 : clusterset.m_group_data->m_group_clusters.reserve(an_clusters.size());
1549 [ + + ]: 31379 : clusterset.m_deps_to_add.clear();
1550 : 31379 : clusterset.m_deps_to_add.reserve(an_deps.size());
1551 : 31379 : clusterset.m_oversized = false;
1552 : 31379 : auto an_deps_it = an_deps.begin();
1553 : 31379 : auto an_clusters_it = an_clusters.begin();
1554 [ + + ]: 89063 : while (an_clusters_it != an_clusters.end()) {
1555 : : // Process all clusters/dependencies belonging to the partition with representative rep.
1556 : 57684 : auto rep = an_clusters_it->second;
1557 : : // Create and initialize a new GroupData entry for the partition.
1558 : 57684 : auto& new_entry = clusterset.m_group_data->m_groups.emplace_back();
1559 : 57684 : new_entry.m_cluster_offset = clusterset.m_group_data->m_group_clusters.size();
1560 : 57684 : new_entry.m_cluster_count = 0;
1561 : 57684 : new_entry.m_deps_offset = clusterset.m_deps_to_add.size();
1562 : 57684 : new_entry.m_deps_count = 0;
1563 : 57684 : uint32_t total_count{0};
1564 : 57684 : uint64_t total_size{0};
1565 : : // Add all its clusters to it (copying those from an_clusters to m_group_clusters).
1566 [ + + + + ]: 242688 : while (an_clusters_it != an_clusters.end() && an_clusters_it->second == rep) {
1567 : 185004 : clusterset.m_group_data->m_group_clusters.push_back(an_clusters_it->first);
1568 : 185004 : total_count += an_clusters_it->first->GetTxCount();
1569 : 185004 : total_size += an_clusters_it->first->GetTotalTxSize();
1570 : 185004 : ++an_clusters_it;
1571 : 185004 : ++new_entry.m_cluster_count;
1572 : : }
1573 : : // Add all its dependencies to it (copying those back from an_deps to m_deps_to_add).
1574 [ + + + + ]: 292888 : while (an_deps_it != an_deps.end() && an_deps_it->second == rep) {
1575 : 235204 : clusterset.m_deps_to_add.push_back(an_deps_it->first);
1576 : 235204 : ++an_deps_it;
1577 : 235204 : ++new_entry.m_deps_count;
1578 : : }
1579 : : // Detect oversizedness.
1580 [ + + + + ]: 57684 : if (total_count > m_max_cluster_count || total_size > m_max_cluster_size) {
1581 : 36226 : clusterset.m_oversized = true;
1582 : : }
1583 : : }
1584 : 31379 : Assume(an_deps_it == an_deps.end());
1585 : 31379 : Assume(an_clusters_it == an_clusters.end());
1586 : 31379 : Compact();
1587 : 31379 : }
1588 : :
1589 : 14580 : void TxGraphImpl::Merge(std::span<Cluster*> to_merge) noexcept
1590 : : {
1591 : 14580 : Assume(!to_merge.empty());
1592 : : // Nothing to do if a group consists of just a single Cluster.
1593 [ + + ]: 14580 : if (to_merge.size() == 1) return;
1594 : :
1595 : : // Move the largest Cluster to the front of to_merge. As all transactions in other to-be-merged
1596 : : // Clusters will be moved to that one, putting the largest one first minimizes the number of
1597 : : // moves.
1598 : 13055 : size_t max_size_pos{0};
1599 : 13055 : DepGraphIndex max_size = to_merge[max_size_pos]->GetTxCount();
1600 [ + + ]: 57697 : for (size_t i = 1; i < to_merge.size(); ++i) {
1601 [ + + ]: 44642 : DepGraphIndex size = to_merge[i]->GetTxCount();
1602 [ + + ]: 44642 : if (size > max_size) {
1603 : 3045 : max_size_pos = i;
1604 : 3045 : max_size = size;
1605 : : }
1606 : : }
1607 [ + + ]: 13055 : if (max_size_pos != 0) std::swap(to_merge[0], to_merge[max_size_pos]);
1608 : :
1609 : : // Merge all further Clusters in the group into the first one, and delete them.
1610 [ + + ]: 57697 : for (size_t i = 1; i < to_merge.size(); ++i) {
1611 : 44642 : to_merge[0]->Merge(*this, *to_merge[i]);
1612 : 44642 : DeleteCluster(*to_merge[i]);
1613 : : }
1614 : : }
1615 : :
1616 : 2943967 : void TxGraphImpl::ApplyDependencies(int level) noexcept
1617 : : {
1618 : 2943967 : auto& clusterset = GetClusterSet(level);
1619 : : // Do not bother computing groups if we already know the result will be oversized.
1620 [ + + ]: 2943967 : if (clusterset.m_oversized == true) return;
1621 : : // Compute the groups of to-be-merged Clusters (which also applies all removals, and splits).
1622 : 2922214 : GroupClusters(level);
1623 : 2922214 : Assume(clusterset.m_group_data.has_value());
1624 : : // Nothing to do if there are no dependencies to be added.
1625 [ + + ]: 2922214 : if (clusterset.m_deps_to_add.empty()) return;
1626 : : // Dependencies cannot be applied if it would result in oversized clusters.
1627 [ + - ]: 13202 : if (clusterset.m_oversized == true) return;
1628 : :
1629 : : // For each group of to-be-merged Clusters.
1630 [ + + ]: 26037 : for (const auto& group_entry : clusterset.m_group_data->m_groups) {
1631 [ + + ]: 14580 : auto cluster_span = std::span{clusterset.m_group_data->m_group_clusters}
1632 [ + + ]: 14580 : .subspan(group_entry.m_cluster_offset, group_entry.m_cluster_count);
1633 : : // Pull in all the Clusters that contain dependencies.
1634 [ + + ]: 14580 : if (level == 1) {
1635 [ + + ]: 28337 : for (Cluster*& cluster : cluster_span) {
1636 : 23010 : cluster = PullIn(cluster);
1637 : : }
1638 : : }
1639 : : // Invoke Merge() to merge them into a single Cluster.
1640 : 14580 : Merge(cluster_span);
1641 : : // Actually apply all to-be-added dependencies (all parents and children from this grouping
1642 : : // belong to the same Cluster at this point because of the merging above).
1643 : 14580 : auto deps_span = std::span{clusterset.m_deps_to_add}
1644 : 14580 : .subspan(group_entry.m_deps_offset, group_entry.m_deps_count);
1645 : 14580 : Assume(!deps_span.empty());
1646 : 14580 : const auto& loc = m_entries[deps_span[0].second].m_locator[level];
1647 : 14580 : Assume(loc.IsPresent());
1648 : 14580 : loc.cluster->ApplyDependencies(*this, deps_span);
1649 : : }
1650 : :
1651 : : // Wipe the list of to-be-added dependencies now that they are applied.
1652 [ + - ]: 11457 : clusterset.m_deps_to_add.clear();
1653 : 11457 : Compact();
1654 : : // Also no further Cluster mergings are needed (note that we clear, but don't set to
1655 : : // std::nullopt, as that would imply the groupings are unknown).
1656 : 22914 : clusterset.m_group_data = GroupData{};
1657 : : }
1658 : :
1659 : 11197 : std::pair<uint64_t, bool> Cluster::Relinearize(TxGraphImpl& graph, uint64_t max_iters) noexcept
1660 : : {
1661 : : // We can only relinearize Clusters that do not need splitting.
1662 : 11197 : Assume(!NeedsSplitting());
1663 : : // No work is required for Clusters which are already optimally linearized.
1664 [ - + ]: 11197 : if (IsOptimal()) return {0, false};
1665 : : // Invoke the actual linearization algorithm (passing in the existing one).
1666 : 11197 : uint64_t rng_seed = graph.m_rng.rand64();
1667 [ + + ]: 11197 : auto [linearization, optimal, cost] = Linearize(m_depgraph, max_iters, rng_seed, m_linearization);
1668 : : // Postlinearize if the result isn't optimal already. This guarantees (among other things)
1669 : : // that the chunks of the resulting linearization are all connected.
1670 [ + + ]: 11197 : if (!optimal) PostLinearize(m_depgraph, linearization);
1671 : : // Update the linearization.
1672 : 11197 : m_linearization = std::move(linearization);
1673 : : // Update the Cluster's quality.
1674 : 11197 : bool improved = false;
1675 [ + + ]: 11197 : if (optimal) {
1676 : 8117 : graph.SetClusterQuality(m_level, m_quality, m_setindex, QualityLevel::OPTIMAL);
1677 : 8117 : improved = true;
1678 [ + + ]: 3080 : } else if (max_iters >= graph.m_acceptable_iters && !IsAcceptable()) {
1679 : 2859 : graph.SetClusterQuality(m_level, m_quality, m_setindex, QualityLevel::ACCEPTABLE);
1680 : 2859 : improved = true;
1681 : : }
1682 : : // Update the Entry objects.
1683 : 11197 : Updated(graph);
1684 : 11197 : return {cost, improved};
1685 : 11197 : }
1686 : :
1687 : 3393761 : void TxGraphImpl::MakeAcceptable(Cluster& cluster) noexcept
1688 : : {
1689 : : // Relinearize the Cluster if needed.
1690 [ + + + + ]: 3409479 : if (!cluster.NeedsSplitting() && !cluster.IsAcceptable() && !cluster.IsOversized()) {
1691 : 8232 : cluster.Relinearize(*this, m_acceptable_iters);
1692 : : }
1693 : 3393761 : }
1694 : :
1695 : 47937 : void TxGraphImpl::MakeAllAcceptable(int level) noexcept
1696 : : {
1697 : 47937 : ApplyDependencies(level);
1698 : 47937 : auto& clusterset = GetClusterSet(level);
1699 [ + - ]: 47937 : if (clusterset.m_oversized == true) return;
1700 : 47937 : auto& queue = clusterset.m_clusters[int(QualityLevel::NEEDS_RELINEARIZE)];
1701 [ + + ]: 53339 : while (!queue.empty()) {
1702 : 5402 : MakeAcceptable(*queue.back().get());
1703 : : }
1704 : : }
1705 : :
1706 : 31294 : Cluster::Cluster(uint64_t sequence) noexcept : m_sequence{sequence} {}
1707 : :
1708 : 228130 : Cluster::Cluster(uint64_t sequence, TxGraphImpl& graph, const FeePerWeight& feerate, GraphIndex graph_index) noexcept :
1709 : 228130 : m_sequence{sequence}
1710 : : {
1711 : : // Create a new transaction in the DepGraph, and remember its position in m_mapping.
1712 : 228130 : auto cluster_idx = m_depgraph.AddTransaction(feerate);
1713 : 228130 : m_mapping.push_back(graph_index);
1714 : 228130 : m_linearization.push_back(cluster_idx);
1715 : 228130 : }
1716 : :
1717 : 228130 : TxGraph::Ref TxGraphImpl::AddTransaction(const FeePerWeight& feerate) noexcept
1718 : : {
1719 [ + + + - ]: 253283 : Assume(m_main_chunkindex_observers == 0 || GetTopLevel() != 0);
1720 : 228130 : Assume(feerate.size > 0);
1721 : : // Construct a new Ref.
1722 : 228130 : Ref ret;
1723 : : // Construct a new Entry, and link it with the Ref.
1724 : 228130 : auto idx = m_entries.size();
1725 : 228130 : m_entries.emplace_back();
1726 : 228130 : auto& entry = m_entries.back();
1727 : 228130 : entry.m_main_chunkindex_iterator = m_main_chunkindex.end();
1728 : 228130 : entry.m_ref = &ret;
1729 : 228130 : GetRefGraph(ret) = this;
1730 : 228130 : GetRefIndex(ret) = idx;
1731 : : // Construct a new singleton Cluster (which is necessarily optimally linearized).
1732 : 228130 : bool oversized = uint64_t(feerate.size) > m_max_cluster_size;
1733 : 228130 : auto cluster = std::make_unique<Cluster>(m_next_sequence_counter++, *this, feerate, idx);
1734 : 228130 : auto cluster_ptr = cluster.get();
1735 : 228130 : int level = GetTopLevel();
1736 : 228130 : auto& clusterset = GetClusterSet(level);
1737 [ + + ]: 431022 : InsertCluster(level, std::move(cluster), oversized ? QualityLevel::OVERSIZED_SINGLETON : QualityLevel::OPTIMAL);
1738 : 228130 : cluster_ptr->Updated(*this);
1739 : 228130 : ++clusterset.m_txcount;
1740 : : // Deal with individually oversized transactions.
1741 [ + + ]: 228130 : if (oversized) {
1742 : 25238 : ++clusterset.m_txcount_oversized;
1743 [ + + ]: 25238 : clusterset.m_oversized = true;
1744 [ + + ]: 25238 : clusterset.m_group_data = std::nullopt;
1745 : : }
1746 : : // Return the Ref.
1747 : 456260 : return ret;
1748 : 228130 : }
1749 : :
1750 : 32192 : void TxGraphImpl::RemoveTransaction(const Ref& arg) noexcept
1751 : : {
1752 : : // Don't do anything if the Ref is empty (which may be indicative of the transaction already
1753 : : // having been removed).
1754 [ + + ]: 32192 : if (GetRefGraph(arg) == nullptr) return;
1755 : 24411 : Assume(GetRefGraph(arg) == this);
1756 [ + + + - ]: 27912 : Assume(m_main_chunkindex_observers == 0 || GetTopLevel() != 0);
1757 : : // Find the Cluster the transaction is in, and stop if it isn't in any.
1758 : 24411 : int level = GetTopLevel();
1759 : 24411 : auto cluster = FindCluster(GetRefIndex(arg), level);
1760 [ + + ]: 24411 : if (cluster == nullptr) return;
1761 : : // Remember that the transaction is to be removed.
1762 : 21047 : auto& clusterset = GetClusterSet(level);
1763 : 21047 : clusterset.m_to_remove.push_back(GetRefIndex(arg));
1764 : : // Wipe m_group_data (as it will need to be recomputed).
1765 [ + + ]: 21047 : clusterset.m_group_data.reset();
1766 [ + + ]: 23511 : if (clusterset.m_oversized == true) clusterset.m_oversized = std::nullopt;
1767 : : }
1768 : :
1769 : 162106 : void TxGraphImpl::AddDependency(const Ref& parent, const Ref& child) noexcept
1770 : : {
1771 : : // Don't do anything if either Ref is empty (which may be indicative of it having already been
1772 : : // removed).
1773 [ + + + + ]: 162106 : if (GetRefGraph(parent) == nullptr || GetRefGraph(child) == nullptr) return;
1774 [ + - - + ]: 156536 : Assume(GetRefGraph(parent) == this && GetRefGraph(child) == this);
1775 [ + + + - ]: 189241 : Assume(m_main_chunkindex_observers == 0 || GetTopLevel() != 0);
1776 : : // Don't do anything if this is a dependency on self.
1777 [ + + ]: 156536 : if (GetRefIndex(parent) == GetRefIndex(child)) return;
1778 : : // Find the Cluster the parent and child transaction are in, and stop if either appears to be
1779 : : // already removed.
1780 : 155479 : int level = GetTopLevel();
1781 : 155479 : auto par_cluster = FindCluster(GetRefIndex(parent), level);
1782 [ + + ]: 155479 : if (par_cluster == nullptr) return;
1783 : 149470 : auto chl_cluster = FindCluster(GetRefIndex(child), level);
1784 [ + + ]: 149470 : if (chl_cluster == nullptr) return;
1785 : : // Remember that this dependency is to be applied.
1786 : 143542 : auto& clusterset = GetClusterSet(level);
1787 : 143542 : clusterset.m_deps_to_add.emplace_back(GetRefIndex(parent), GetRefIndex(child));
1788 : : // Wipe m_group_data (as it will need to be recomputed).
1789 [ + + ]: 143542 : clusterset.m_group_data.reset();
1790 [ + + ]: 164870 : if (clusterset.m_oversized == false) clusterset.m_oversized = std::nullopt;
1791 : : }
1792 : :
1793 : 20778 : bool TxGraphImpl::Exists(const Ref& arg, bool main_only) noexcept
1794 : : {
1795 [ + + ]: 20778 : if (GetRefGraph(arg) == nullptr) return false;
1796 : 18075 : Assume(GetRefGraph(arg) == this);
1797 [ + + ]: 18075 : size_t level = GetSpecifiedLevel(main_only);
1798 : : // Make sure the transaction isn't scheduled for removal.
1799 : 18075 : ApplyRemovals(level);
1800 : 18075 : auto cluster = FindCluster(GetRefIndex(arg), level);
1801 : 18075 : return cluster != nullptr;
1802 : : }
1803 : :
1804 : 168396 : void Cluster::GetAncestorRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept
1805 : : {
1806 : : /** The union of all ancestors to be returned. */
1807 : 168396 : SetType ancestors_union;
1808 : : // Process elements from the front of args, as long as they apply.
1809 [ + + ]: 347486 : while (!args.empty()) {
1810 [ + + ]: 183784 : if (args.front().first != this) break;
1811 : 179090 : ancestors_union |= m_depgraph.Ancestors(args.front().second);
1812 : 179090 : args = args.subspan(1);
1813 : : }
1814 : 168396 : Assume(ancestors_union.Any());
1815 : : // Translate all ancestors (in arbitrary order) to Refs (if they have any), and return them.
1816 [ + - + + ]: 675748 : for (auto idx : ancestors_union) {
1817 : 338956 : const auto& entry = graph.m_entries[m_mapping[idx]];
1818 : 338956 : Assume(entry.m_ref != nullptr);
1819 : 338956 : output.push_back(entry.m_ref);
1820 : : }
1821 : 168396 : }
1822 : :
1823 : 169019 : void Cluster::GetDescendantRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept
1824 : : {
1825 : : /** The union of all descendants to be returned. */
1826 : 169019 : SetType descendants_union;
1827 : : // Process elements from the front of args, as long as they apply.
1828 [ + + ]: 352243 : while (!args.empty()) {
1829 [ + + ]: 189620 : if (args.front().first != this) break;
1830 : 183224 : descendants_union |= m_depgraph.Descendants(args.front().second);
1831 : 183224 : args = args.subspan(1);
1832 : : }
1833 : 169019 : Assume(descendants_union.Any());
1834 : : // Translate all descendants (in arbitrary order) to Refs (if they have any), and return them.
1835 [ + - + + ]: 678442 : for (auto idx : descendants_union) {
1836 : 340404 : const auto& entry = graph.m_entries[m_mapping[idx]];
1837 : 340404 : Assume(entry.m_ref != nullptr);
1838 : 340404 : output.push_back(entry.m_ref);
1839 : : }
1840 : 169019 : }
1841 : :
1842 : 287298 : bool Cluster::GetClusterRefs(TxGraphImpl& graph, std::span<TxGraph::Ref*> range, LinearizationIndex start_pos) noexcept
1843 : : {
1844 : : // Translate the transactions in the Cluster (in linearization order, starting at start_pos in
1845 : : // the linearization) to Refs, and fill them in range.
1846 [ + + ]: 3067245 : for (auto& ref : range) {
1847 : 2779947 : Assume(start_pos < m_linearization.size());
1848 : 2779947 : const auto& entry = graph.m_entries[m_mapping[m_linearization[start_pos++]]];
1849 : 2779947 : Assume(entry.m_ref != nullptr);
1850 : 2779947 : ref = entry.m_ref;
1851 : : }
1852 : : // Return whether start_pos has advanced to the end of the Cluster.
1853 : 287298 : return start_pos == m_linearization.size();
1854 : : }
1855 : :
1856 : 237944 : FeePerWeight Cluster::GetIndividualFeerate(DepGraphIndex idx) noexcept
1857 : : {
1858 : 237944 : return FeePerWeight::FromFeeFrac(m_depgraph.FeeRate(idx));
1859 : : }
1860 : :
1861 : 18149 : void Cluster::MakeStagingTransactionsMissing(TxGraphImpl& graph) noexcept
1862 : : {
1863 : 18149 : Assume(m_level == 1);
1864 : : // Mark all transactions of a Cluster missing, needed when aborting staging, so that the
1865 : : // corresponding Locators don't retain references into aborted Clusters.
1866 [ + + ]: 42298 : for (auto ci : m_linearization) {
1867 : 24149 : GraphIndex idx = m_mapping[ci];
1868 : 24149 : auto& entry = graph.m_entries[idx];
1869 : 24149 : entry.m_locator[1].SetMissing();
1870 : : }
1871 : 18149 : }
1872 : :
1873 : 164916 : std::vector<TxGraph::Ref*> TxGraphImpl::GetAncestors(const Ref& arg, bool main_only) noexcept
1874 : : {
1875 : : // Return the empty vector if the Ref is empty.
1876 [ + + ]: 164916 : if (GetRefGraph(arg) == nullptr) return {};
1877 : 162033 : Assume(GetRefGraph(arg) == this);
1878 : : // Apply all removals and dependencies, as the result might be incorrect otherwise.
1879 [ + + ]: 162033 : size_t level = GetSpecifiedLevel(main_only);
1880 : 162033 : ApplyDependencies(level);
1881 : : // Ancestry cannot be known if unapplied dependencies remain.
1882 : 162033 : Assume(GetClusterSet(level).m_deps_to_add.empty());
1883 : : // Find the Cluster the argument is in, and return the empty vector if it isn't in any.
1884 : 162033 : auto cluster = FindCluster(GetRefIndex(arg), level);
1885 [ + + ]: 162033 : if (cluster == nullptr) return {};
1886 : : // Dispatch to the Cluster.
1887 : 160626 : std::pair<Cluster*, DepGraphIndex> match = {cluster, m_entries[GetRefIndex(arg)].m_locator[cluster->m_level].index};
1888 : 160626 : auto matches = std::span(&match, 1);
1889 : 160626 : std::vector<TxGraph::Ref*> ret;
1890 : 160626 : cluster->GetAncestorRefs(*this, matches, ret);
1891 : 160626 : return ret;
1892 : 160626 : }
1893 : :
1894 : 162547 : std::vector<TxGraph::Ref*> TxGraphImpl::GetDescendants(const Ref& arg, bool main_only) noexcept
1895 : : {
1896 : : // Return the empty vector if the Ref is empty.
1897 [ + + ]: 162547 : if (GetRefGraph(arg) == nullptr) return {};
1898 : 159246 : Assume(GetRefGraph(arg) == this);
1899 : : // Apply all removals and dependencies, as the result might be incorrect otherwise.
1900 [ + + ]: 159246 : size_t level = GetSpecifiedLevel(main_only);
1901 : 159246 : ApplyDependencies(level);
1902 : : // Ancestry cannot be known if unapplied dependencies remain.
1903 : 159246 : Assume(GetClusterSet(level).m_deps_to_add.empty());
1904 : : // Find the Cluster the argument is in, and return the empty vector if it isn't in any.
1905 : 159246 : auto cluster = FindCluster(GetRefIndex(arg), level);
1906 [ + + ]: 159246 : if (cluster == nullptr) return {};
1907 : : // Dispatch to the Cluster.
1908 : 158713 : std::pair<Cluster*, DepGraphIndex> match = {cluster, m_entries[GetRefIndex(arg)].m_locator[cluster->m_level].index};
1909 : 158713 : auto matches = std::span(&match, 1);
1910 : 158713 : std::vector<TxGraph::Ref*> ret;
1911 : 158713 : cluster->GetDescendantRefs(*this, matches, ret);
1912 : 158713 : return ret;
1913 : 158713 : }
1914 : :
1915 : 5663 : std::vector<TxGraph::Ref*> TxGraphImpl::GetAncestorsUnion(std::span<const Ref* const> args, bool main_only) noexcept
1916 : : {
1917 : : // Apply all dependencies, as the result might be incorrect otherwise.
1918 [ + + ]: 5663 : size_t level = GetSpecifiedLevel(main_only);
1919 : 5663 : ApplyDependencies(level);
1920 : : // Ancestry cannot be known if unapplied dependencies remain.
1921 : 5663 : Assume(GetClusterSet(level).m_deps_to_add.empty());
1922 : :
1923 : : // Translate args to matches.
1924 : 5663 : std::vector<std::pair<Cluster*, DepGraphIndex>> matches;
1925 : 5663 : matches.reserve(args.size());
1926 [ + + ]: 39160 : for (auto arg : args) {
1927 : 33497 : Assume(arg);
1928 : : // Skip empty Refs.
1929 [ + + ]: 33497 : if (GetRefGraph(*arg) == nullptr) continue;
1930 : 22366 : Assume(GetRefGraph(*arg) == this);
1931 : : // Find the Cluster the argument is in, and skip if none is found.
1932 : 22366 : auto cluster = FindCluster(GetRefIndex(*arg), level);
1933 [ + + ]: 22366 : if (cluster == nullptr) continue;
1934 : : // Append to matches.
1935 : 18464 : matches.emplace_back(cluster, m_entries[GetRefIndex(*arg)].m_locator[cluster->m_level].index);
1936 : : }
1937 : : // Group by Cluster.
1938 : 47621 : std::sort(matches.begin(), matches.end(), [](auto& a, auto& b) noexcept { return CompareClusters(a.first, b.first) < 0; });
1939 : : // Dispatch to the Clusters.
1940 : 5663 : std::span match_span(matches);
1941 : 5663 : std::vector<TxGraph::Ref*> ret;
1942 [ + + ]: 13433 : while (!match_span.empty()) {
1943 : 7770 : match_span.front().first->GetAncestorRefs(*this, match_span, ret);
1944 : : }
1945 : 5663 : return ret;
1946 : 5663 : }
1947 : :
1948 : 5850 : std::vector<TxGraph::Ref*> TxGraphImpl::GetDescendantsUnion(std::span<const Ref* const> args, bool main_only) noexcept
1949 : : {
1950 : : // Apply all dependencies, as the result might be incorrect otherwise.
1951 [ + + ]: 5850 : size_t level = GetSpecifiedLevel(main_only);
1952 : 5850 : ApplyDependencies(level);
1953 : : // Ancestry cannot be known if unapplied dependencies remain.
1954 : 5850 : Assume(GetClusterSet(level).m_deps_to_add.empty());
1955 : :
1956 : : // Translate args to matches.
1957 : 5850 : std::vector<std::pair<Cluster*, DepGraphIndex>> matches;
1958 : 5850 : matches.reserve(args.size());
1959 [ + + ]: 46571 : for (auto arg : args) {
1960 : 40721 : Assume(arg);
1961 : : // Skip empty Refs.
1962 [ + + ]: 40721 : if (GetRefGraph(*arg) == nullptr) continue;
1963 : 30917 : Assume(GetRefGraph(*arg) == this);
1964 : : // Find the Cluster the argument is in, and skip if none is found.
1965 : 30917 : auto cluster = FindCluster(GetRefIndex(*arg), level);
1966 [ + + ]: 30917 : if (cluster == nullptr) continue;
1967 : : // Append to matches.
1968 : 24511 : matches.emplace_back(cluster, m_entries[GetRefIndex(*arg)].m_locator[cluster->m_level].index);
1969 : : }
1970 : : // Group by Cluster.
1971 : 66844 : std::sort(matches.begin(), matches.end(), [](auto& a, auto& b) noexcept { return CompareClusters(a.first, b.first) < 0; });
1972 : : // Dispatch to the Clusters.
1973 : 5850 : std::span match_span(matches);
1974 : 5850 : std::vector<TxGraph::Ref*> ret;
1975 [ + + ]: 16156 : while (!match_span.empty()) {
1976 : 10306 : match_span.front().first->GetDescendantRefs(*this, match_span, ret);
1977 : : }
1978 : 5850 : return ret;
1979 : 5850 : }
1980 : :
1981 : 276986 : std::vector<TxGraph::Ref*> TxGraphImpl::GetCluster(const Ref& arg, bool main_only) noexcept
1982 : : {
1983 : : // Return the empty vector if the Ref is empty (which may be indicative of the transaction
1984 : : // having been removed already.
1985 [ + + ]: 276986 : if (GetRefGraph(arg) == nullptr) return {};
1986 : 274293 : Assume(GetRefGraph(arg) == this);
1987 : : // Apply all removals and dependencies, as the result might be incorrect otherwise.
1988 [ + + ]: 274293 : size_t level = GetSpecifiedLevel(main_only);
1989 : 274293 : ApplyDependencies(level);
1990 : : // Cluster linearization cannot be known if unapplied dependencies remain.
1991 : 274293 : Assume(GetClusterSet(level).m_deps_to_add.empty());
1992 : : // Find the Cluster the argument is in, and return the empty vector if it isn't in any.
1993 : 274293 : auto cluster = FindCluster(GetRefIndex(arg), level);
1994 [ + + ]: 274293 : if (cluster == nullptr) return {};
1995 : : // Make sure the Cluster has an acceptable quality level, and then dispatch to it.
1996 : 272937 : MakeAcceptable(*cluster);
1997 : 272937 : std::vector<TxGraph::Ref*> ret(cluster->GetTxCount());
1998 : 272937 : cluster->GetClusterRefs(*this, ret, 0);
1999 : 272937 : return ret;
2000 : 272937 : }
2001 : :
2002 : 52488 : TxGraph::GraphIndex TxGraphImpl::GetTransactionCount(bool main_only) noexcept
2003 : : {
2004 [ + + ]: 52488 : size_t level = GetSpecifiedLevel(main_only);
2005 : 52488 : ApplyRemovals(level);
2006 : 52488 : return GetClusterSet(level).m_txcount;
2007 : : }
2008 : :
2009 : 245959 : FeePerWeight TxGraphImpl::GetIndividualFeerate(const Ref& arg) noexcept
2010 : : {
2011 : : // Return the empty FeePerWeight if the passed Ref is empty.
2012 [ + + ]: 245959 : if (GetRefGraph(arg) == nullptr) return {};
2013 : 239690 : Assume(GetRefGraph(arg) == this);
2014 : : // Find the cluster the argument is in (the level does not matter as individual feerates will
2015 : : // be identical if it occurs in both), and return the empty FeePerWeight if it isn't in any.
2016 : 239690 : Cluster* cluster{nullptr};
2017 [ + + ]: 260329 : for (int level = 0; level <= GetTopLevel(); ++level) {
2018 : : // Apply removals, so that we can correctly report FeePerWeight{} for non-existing
2019 : : // transactions.
2020 : 258583 : ApplyRemovals(level);
2021 [ + + ]: 258583 : if (m_entries[GetRefIndex(arg)].m_locator[level].IsPresent()) {
2022 : : cluster = m_entries[GetRefIndex(arg)].m_locator[level].cluster;
2023 : : break;
2024 : : }
2025 : : }
2026 [ + + ]: 239690 : if (cluster == nullptr) return {};
2027 : : // Dispatch to the Cluster.
2028 : 237944 : return cluster->GetIndividualFeerate(m_entries[GetRefIndex(arg)].m_locator[cluster->m_level].index);
2029 : : }
2030 : :
2031 : 1356701 : FeePerWeight TxGraphImpl::GetMainChunkFeerate(const Ref& arg) noexcept
2032 : : {
2033 : : // Return the empty FeePerWeight if the passed Ref is empty.
2034 [ + + ]: 1356701 : if (GetRefGraph(arg) == nullptr) return {};
2035 : 1354235 : Assume(GetRefGraph(arg) == this);
2036 : : // Apply all removals and dependencies, as the result might be inaccurate otherwise.
2037 : 1354235 : ApplyDependencies(/*level=*/0);
2038 : : // Chunk feerates cannot be accurately known if unapplied dependencies remain.
2039 : 1354235 : Assume(m_main_clusterset.m_deps_to_add.empty());
2040 : : // Find the cluster the argument is in, and return the empty FeePerWeight if it isn't in any.
2041 : 1354235 : auto cluster = FindCluster(GetRefIndex(arg), 0);
2042 [ + + ]: 1354235 : if (cluster == nullptr) return {};
2043 : : // Make sure the Cluster has an acceptable quality level, and then return the transaction's
2044 : : // chunk feerate.
2045 : 1352857 : MakeAcceptable(*cluster);
2046 : 1352857 : const auto& entry = m_entries[GetRefIndex(arg)];
2047 : 1352857 : return entry.m_main_chunk_feerate;
2048 : : }
2049 : :
2050 : 29727 : bool TxGraphImpl::IsOversized(bool main_only) noexcept
2051 : : {
2052 [ + + ]: 29727 : size_t level = GetSpecifiedLevel(main_only);
2053 : 29727 : auto& clusterset = GetClusterSet(level);
2054 [ + + ]: 29727 : if (clusterset.m_oversized.has_value()) {
2055 : : // Return cached value if known.
2056 : 28261 : return *clusterset.m_oversized;
2057 : : }
2058 : 1466 : ApplyRemovals(level);
2059 [ + + ]: 1466 : if (clusterset.m_txcount_oversized > 0) {
2060 : 606 : clusterset.m_oversized = true;
2061 : : } else {
2062 : : // Find which Clusters will need to be merged together, as that is where the oversize
2063 : : // property is assessed.
2064 : 860 : GroupClusters(level);
2065 : : }
2066 : 1466 : Assume(clusterset.m_oversized.has_value());
2067 : 1466 : return *clusterset.m_oversized;
2068 : : }
2069 : :
2070 : 9641 : void TxGraphImpl::StartStaging() noexcept
2071 : : {
2072 : : // Staging cannot already exist.
2073 : 9641 : Assume(!m_staging_clusterset.has_value());
2074 : : // Apply all remaining dependencies in main before creating a staging graph. Once staging
2075 : : // exists, we cannot merge Clusters anymore (because of interference with Clusters being
2076 : : // pulled into staging), so to make sure all inspectors are available (if not oversized), do
2077 : : // all merging work now. Call SplitAll() first, so that even if ApplyDependencies does not do
2078 : : // any thing due to knowing the result is oversized, splitting is still performed.
2079 : 9641 : SplitAll(0);
2080 : 9641 : ApplyDependencies(0);
2081 : : // Construct the staging ClusterSet.
2082 : 9641 : m_staging_clusterset.emplace();
2083 : : // Copy statistics, precomputed data, and to-be-applied dependencies (only if oversized) to
2084 : : // the new graph. To-be-applied removals will always be empty at this point.
2085 : 9641 : m_staging_clusterset->m_txcount = m_main_clusterset.m_txcount;
2086 : 9641 : m_staging_clusterset->m_txcount_oversized = m_main_clusterset.m_txcount_oversized;
2087 : 9641 : m_staging_clusterset->m_deps_to_add = m_main_clusterset.m_deps_to_add;
2088 : 9641 : m_staging_clusterset->m_group_data = m_main_clusterset.m_group_data;
2089 : 9641 : m_staging_clusterset->m_oversized = m_main_clusterset.m_oversized;
2090 : 9641 : Assume(m_staging_clusterset->m_oversized.has_value());
2091 : 9641 : }
2092 : :
2093 : 2903 : void TxGraphImpl::AbortStaging() noexcept
2094 : : {
2095 : : // Staging must exist.
2096 : 2903 : Assume(m_staging_clusterset.has_value());
2097 : : // Mark all removed transactions as Missing (so the staging locator for these transactions
2098 : : // can be reused if another staging is created).
2099 [ + + ]: 11440 : for (auto idx : m_staging_clusterset->m_removed) {
2100 : 8537 : m_entries[idx].m_locator[1].SetMissing();
2101 : : }
2102 : : // Do the same with the non-removed transactions in staging Clusters.
2103 [ + + ]: 20321 : for (int quality = 0; quality < int(QualityLevel::NONE); ++quality) {
2104 [ + + ]: 35567 : for (auto& cluster : m_staging_clusterset->m_clusters[quality]) {
2105 : 18149 : cluster->MakeStagingTransactionsMissing(*this);
2106 : : }
2107 : : }
2108 : : // Destroy the staging ClusterSet.
2109 : 2903 : m_staging_clusterset.reset();
2110 : 2903 : Compact();
2111 [ + + ]: 2903 : if (!m_main_clusterset.m_group_data.has_value()) {
2112 : : // In case m_oversized in main was kept after a Ref destruction while staging exists, we
2113 : : // need to re-evaluate m_oversized now.
2114 [ + + + + ]: 874 : if (m_main_clusterset.m_to_remove.empty() && m_main_clusterset.m_txcount_oversized > 0) {
2115 : : // It is possible that a Ref destruction caused a removal in main while staging existed.
2116 : : // In this case, m_txcount_oversized may be inaccurate.
2117 : 687 : m_main_clusterset.m_oversized = true;
2118 : : } else {
2119 [ + - ]: 187 : m_main_clusterset.m_oversized = std::nullopt;
2120 : : }
2121 : : }
2122 : 2903 : }
2123 : :
2124 : 4643 : void TxGraphImpl::CommitStaging() noexcept
2125 : : {
2126 : : // Staging must exist.
2127 : 4643 : Assume(m_staging_clusterset.has_value());
2128 : 4643 : Assume(m_main_chunkindex_observers == 0);
2129 : : // Delete all conflicting Clusters in main, to make place for moving the staging ones
2130 : : // there. All of these have been copied to staging in PullIn().
2131 : 4643 : auto conflicts = GetConflicts();
2132 [ + + ]: 8130 : for (Cluster* conflict : conflicts) {
2133 : 3487 : conflict->Clear(*this);
2134 : 3487 : DeleteCluster(*conflict);
2135 : : }
2136 : : // Mark the removed transactions as Missing (so the staging locator for these transactions
2137 : : // can be reused if another staging is created).
2138 [ + + ]: 7145 : for (auto idx : m_staging_clusterset->m_removed) {
2139 : 2502 : m_entries[idx].m_locator[1].SetMissing();
2140 : : }
2141 : : // Then move all Clusters in staging to main.
2142 [ + + ]: 32501 : for (int quality = 0; quality < int(QualityLevel::NONE); ++quality) {
2143 : 27858 : auto& stage_sets = m_staging_clusterset->m_clusters[quality];
2144 [ + + ]: 38358 : while (!stage_sets.empty()) {
2145 : 10500 : stage_sets.back()->MoveToMain(*this);
2146 : : }
2147 : : }
2148 : : // Move all statistics, precomputed data, and to-be-applied removals and dependencies.
2149 : 4643 : m_main_clusterset.m_deps_to_add = std::move(m_staging_clusterset->m_deps_to_add);
2150 : 4643 : m_main_clusterset.m_to_remove = std::move(m_staging_clusterset->m_to_remove);
2151 : 4643 : m_main_clusterset.m_group_data = std::move(m_staging_clusterset->m_group_data);
2152 : 4643 : m_main_clusterset.m_oversized = std::move(m_staging_clusterset->m_oversized);
2153 : 4643 : m_main_clusterset.m_txcount = std::move(m_staging_clusterset->m_txcount);
2154 : 4643 : m_main_clusterset.m_txcount_oversized = std::move(m_staging_clusterset->m_txcount_oversized);
2155 : : // Delete the old staging graph, after all its information was moved to main.
2156 : 4643 : m_staging_clusterset.reset();
2157 : 4643 : Compact();
2158 : 4643 : }
2159 : :
2160 : 10584 : void Cluster::SetFee(TxGraphImpl& graph, DepGraphIndex idx, int64_t fee) noexcept
2161 : : {
2162 : : // Make sure the specified DepGraphIndex exists in this Cluster.
2163 : 10584 : Assume(m_depgraph.Positions()[idx]);
2164 : : // Bail out if the fee isn't actually being changed.
2165 [ + + ]: 10584 : if (m_depgraph.FeeRate(idx).fee == fee) return;
2166 : : // Update the fee, remember that relinearization will be necessary, and update the Entries
2167 : : // in the same Cluster.
2168 [ + + ]: 6454 : m_depgraph.FeeRate(idx).fee = fee;
2169 [ + + ]: 6454 : if (m_quality == QualityLevel::OVERSIZED_SINGLETON) {
2170 : : // Nothing to do.
2171 [ + + ]: 5776 : } else if (!NeedsSplitting()) {
2172 : 5758 : graph.SetClusterQuality(m_level, m_quality, m_setindex, QualityLevel::NEEDS_RELINEARIZE);
2173 : : } else {
2174 : 18 : graph.SetClusterQuality(m_level, m_quality, m_setindex, QualityLevel::NEEDS_SPLIT);
2175 : : }
2176 : 6454 : Updated(graph);
2177 : : }
2178 : :
2179 : 13739 : void TxGraphImpl::SetTransactionFee(const Ref& ref, int64_t fee) noexcept
2180 : : {
2181 : : // Don't do anything if the passed Ref is empty.
2182 [ + + ]: 13739 : if (GetRefGraph(ref) == nullptr) return;
2183 : 11075 : Assume(GetRefGraph(ref) == this);
2184 : 11075 : Assume(m_main_chunkindex_observers == 0);
2185 : : // Find the entry, its locator, and inform its Cluster about the new feerate, if any.
2186 : 11075 : auto& entry = m_entries[GetRefIndex(ref)];
2187 [ + + ]: 33225 : for (int level = 0; level < MAX_LEVELS; ++level) {
2188 : 22150 : auto& locator = entry.m_locator[level];
2189 [ + + ]: 22150 : if (locator.IsPresent()) {
2190 : 10584 : locator.cluster->SetFee(*this, locator.index, fee);
2191 : : }
2192 : : }
2193 : : }
2194 : :
2195 : 867855 : std::strong_ordering TxGraphImpl::CompareMainOrder(const Ref& a, const Ref& b) noexcept
2196 : : {
2197 : : // The references must not be empty.
2198 : 867855 : Assume(GetRefGraph(a) == this);
2199 : 867855 : Assume(GetRefGraph(b) == this);
2200 : : // Apply dependencies in main.
2201 : 867855 : ApplyDependencies(0);
2202 : 867855 : Assume(m_main_clusterset.m_deps_to_add.empty());
2203 : : // Make both involved Clusters acceptable, so chunk feerates are relevant.
2204 : 867855 : const auto& entry_a = m_entries[GetRefIndex(a)];
2205 : 867855 : const auto& entry_b = m_entries[GetRefIndex(b)];
2206 : 867855 : const auto& locator_a = entry_a.m_locator[0];
2207 : 867855 : const auto& locator_b = entry_b.m_locator[0];
2208 : 867855 : Assume(locator_a.IsPresent());
2209 : 867855 : Assume(locator_b.IsPresent());
2210 : 867855 : MakeAcceptable(*locator_a.cluster);
2211 : 867855 : MakeAcceptable(*locator_b.cluster);
2212 : : // Invoke comparison logic.
2213 : 867855 : return CompareMainTransactions(GetRefIndex(a), GetRefIndex(b));
2214 : : }
2215 : :
2216 : 14524 : TxGraph::GraphIndex TxGraphImpl::CountDistinctClusters(std::span<const Ref* const> refs, bool main_only) noexcept
2217 : : {
2218 [ + + ]: 14524 : size_t level = GetSpecifiedLevel(main_only);
2219 : 14524 : ApplyDependencies(level);
2220 : 14524 : auto& clusterset = GetClusterSet(level);
2221 : 14524 : Assume(clusterset.m_deps_to_add.empty());
2222 : : // Build a vector of Clusters that the specified Refs occur in.
2223 : 14524 : std::vector<Cluster*> clusters;
2224 : 14524 : clusters.reserve(refs.size());
2225 [ + + ]: 358761 : for (const Ref* ref : refs) {
2226 : 344237 : Assume(ref);
2227 [ + + ]: 344237 : if (GetRefGraph(*ref) == nullptr) continue;
2228 : 273814 : Assume(GetRefGraph(*ref) == this);
2229 : 273814 : auto cluster = FindCluster(GetRefIndex(*ref), level);
2230 [ + + ]: 273814 : if (cluster != nullptr) clusters.push_back(cluster);
2231 : : }
2232 : : // Count the number of distinct elements in clusters.
2233 : 1211126 : std::sort(clusters.begin(), clusters.end(), [](Cluster* a, Cluster* b) noexcept { return CompareClusters(a, b) < 0; });
2234 : 14524 : Cluster* last{nullptr};
2235 : 14524 : GraphIndex ret{0};
2236 [ + + ]: 244316 : for (Cluster* cluster : clusters) {
2237 : 229792 : ret += (cluster != last);
2238 : 229792 : last = cluster;
2239 : : }
2240 : 14524 : return ret;
2241 : 14524 : }
2242 : :
2243 : 7332 : std::pair<std::vector<FeeFrac>, std::vector<FeeFrac>> TxGraphImpl::GetMainStagingDiagrams() noexcept
2244 : : {
2245 : 7332 : Assume(m_staging_clusterset.has_value());
2246 : 7332 : MakeAllAcceptable(0);
2247 : 7332 : Assume(m_main_clusterset.m_deps_to_add.empty()); // can only fail if main is oversized
2248 : 7332 : MakeAllAcceptable(1);
2249 : 7332 : Assume(m_staging_clusterset->m_deps_to_add.empty()); // can only fail if staging is oversized
2250 : : // For all Clusters in main which conflict with Clusters in staging (i.e., all that are removed
2251 : : // by, or replaced in, staging), gather their chunk feerates.
2252 : 7332 : auto main_clusters = GetConflicts();
2253 : 7332 : std::vector<FeeFrac> main_feerates, staging_feerates;
2254 [ + + ]: 60180 : for (Cluster* cluster : main_clusters) {
2255 : 52848 : cluster->AppendChunkFeerates(main_feerates);
2256 : : }
2257 : : // Do the same for the Clusters in staging themselves.
2258 [ + + ]: 51324 : for (int quality = 0; quality < int(QualityLevel::NONE); ++quality) {
2259 [ + + ]: 120320 : for (const auto& cluster : m_staging_clusterset->m_clusters[quality]) {
2260 : 76328 : cluster->AppendChunkFeerates(staging_feerates);
2261 : : }
2262 : : }
2263 : : // Sort both by decreasing feerate to obtain diagrams, and return them.
2264 [ - - - - : 272348 : std::sort(main_feerates.begin(), main_feerates.end(), [](auto& a, auto& b) { return a > b; });
+ + + + +
+ + + + +
+ + + + +
+ - - +
+ ]
2265 [ - - - - : 481875 : std::sort(staging_feerates.begin(), staging_feerates.end(), [](auto& a, auto& b) { return a > b; });
+ + + + +
+ + + + +
+ + + + +
+ - - +
+ ]
2266 : 7332 : return std::make_pair(std::move(main_feerates), std::move(staging_feerates));
2267 : 7332 : }
2268 : :
2269 : 268321 : void Cluster::SanityCheck(const TxGraphImpl& graph, int level) const
2270 : : {
2271 : : // There must be an m_mapping for each m_depgraph position (including holes).
2272 [ - + ]: 268321 : assert(m_depgraph.PositionRange() == m_mapping.size());
2273 : : // The linearization for this Cluster must contain every transaction once.
2274 [ - + ]: 268321 : assert(m_depgraph.TxCount() == m_linearization.size());
2275 : : // The number of transactions in a Cluster cannot exceed m_max_cluster_count.
2276 [ - + ]: 268321 : assert(m_linearization.size() <= graph.m_max_cluster_count);
2277 : : // The level must match the level the Cluster occurs in.
2278 [ - + ]: 268321 : assert(m_level == level);
2279 : : // The sum of their sizes cannot exceed m_max_cluster_size, unless it is an individually
2280 : : // oversized transaction singleton. Note that groups of to-be-merged clusters which would
2281 : : // exceed this limit are marked oversized, which means they are never applied.
2282 [ + + - + ]: 268321 : assert(m_quality == QualityLevel::OVERSIZED_SINGLETON || GetTotalTxSize() <= graph.m_max_cluster_size);
2283 : : // m_quality and m_setindex are checked in TxGraphImpl::SanityCheck.
2284 : :
2285 : : // OVERSIZED clusters are singletons.
2286 [ + + - + ]: 268321 : assert(m_quality != QualityLevel::OVERSIZED_SINGLETON || m_linearization.size() == 1);
2287 : :
2288 : : // Compute the chunking of m_linearization.
2289 : 268321 : LinearizationChunking linchunking(m_depgraph, m_linearization);
2290 : :
2291 : : // Verify m_linearization.
2292 : 268321 : SetType m_done;
2293 : 268321 : LinearizationIndex linindex{0};
2294 : 268321 : DepGraphIndex chunk_pos{0}; //!< position within the current chunk
2295 [ - + ]: 268321 : assert(m_depgraph.IsAcyclic());
2296 [ + + ]: 593918 : for (auto lin_pos : m_linearization) {
2297 [ - + ]: 325597 : assert(lin_pos < m_mapping.size());
2298 : 325597 : const auto& entry = graph.m_entries[m_mapping[lin_pos]];
2299 : : // Check that the linearization is topological.
2300 : 325597 : m_done.Set(lin_pos);
2301 [ - + ]: 325597 : assert(m_done.IsSupersetOf(m_depgraph.Ancestors(lin_pos)));
2302 : : // Check that the Entry has a locator pointing back to this Cluster & position within it.
2303 [ - + ]: 325597 : assert(entry.m_locator[level].cluster == this);
2304 [ - + ]: 325597 : assert(entry.m_locator[level].index == lin_pos);
2305 : : // For main-level entries, check linearization position and chunk feerate.
2306 [ + + ]: 580339 : if (level == 0 && IsAcceptable()) {
2307 [ - + ]: 229628 : assert(entry.m_main_lin_index == linindex);
2308 : 229628 : ++linindex;
2309 [ + + ]: 229628 : if (!linchunking.GetChunk(0).transactions[lin_pos]) {
2310 : 20029 : linchunking.MarkDone(linchunking.GetChunk(0).transactions);
2311 : 20029 : chunk_pos = 0;
2312 : : }
2313 [ + - ]: 229628 : assert(entry.m_main_chunk_feerate == linchunking.GetChunk(0).feerate);
2314 : : // Verify that an entry in the chunk index exists for every chunk-ending transaction.
2315 : 229628 : ++chunk_pos;
2316 [ - + ]: 229628 : bool is_chunk_end = (chunk_pos == linchunking.GetChunk(0).transactions.Count());
2317 [ - + ]: 229628 : assert((entry.m_main_chunkindex_iterator != graph.m_main_chunkindex.end()) == is_chunk_end);
2318 [ + + ]: 229628 : if (is_chunk_end) {
2319 [ + + ]: 216066 : auto& chunk_data = *entry.m_main_chunkindex_iterator;
2320 [ + + + + ]: 216066 : if (m_done == m_depgraph.Positions() && chunk_pos == 1) {
2321 [ - + ]: 194859 : assert(chunk_data.m_chunk_count == LinearizationIndex(-1));
2322 : : } else {
2323 [ - + ]: 21207 : assert(chunk_data.m_chunk_count == chunk_pos);
2324 : : }
2325 : : }
2326 : : // If this Cluster has an acceptable quality level, its chunks must be connected.
2327 [ - + ]: 229628 : assert(m_depgraph.IsConnected(linchunking.GetChunk(0).transactions));
2328 : : }
2329 : : }
2330 : : // Verify that each element of m_depgraph occurred in m_linearization.
2331 [ - + ]: 268321 : assert(m_done == m_depgraph.Positions());
2332 : 268321 : }
2333 : :
2334 : 10416 : void TxGraphImpl::SanityCheck() const
2335 : : {
2336 : : /** Which GraphIndexes ought to occur in m_unlinked, based on m_entries. */
2337 : 10416 : std::set<GraphIndex> expected_unlinked;
2338 : : /** Which Clusters ought to occur in ClusterSet::m_clusters, based on m_entries. */
2339 [ + + ]: 52080 : std::set<const Cluster*> expected_clusters[MAX_LEVELS];
2340 : : /** Which GraphIndexes ought to occur in ClusterSet::m_removed, based on m_entries. */
2341 [ + + ]: 52080 : std::set<GraphIndex> expected_removed[MAX_LEVELS];
2342 : : /** Which Cluster::m_sequence values have been encountered. */
2343 : 10416 : std::set<uint64_t> sequences;
2344 : : /** Which GraphIndexes ought to occur in m_main_chunkindex, based on m_entries. */
2345 : 10416 : std::set<GraphIndex> expected_chunkindex;
2346 : : /** Whether compaction is possible in the current state. */
2347 : 10416 : bool compact_possible{true};
2348 : :
2349 : : // Go over all Entry objects in m_entries.
2350 [ + + ]: 400218 : for (GraphIndex idx = 0; idx < m_entries.size(); ++idx) {
2351 [ + + ]: 389802 : const auto& entry = m_entries[idx];
2352 [ + + ]: 389802 : if (entry.m_ref == nullptr) {
2353 : : // Unlinked Entry must have indexes appear in m_unlinked.
2354 [ + - ]: 25478 : expected_unlinked.insert(idx);
2355 : : } else {
2356 : : // Every non-unlinked Entry must have a Ref that points back to it.
2357 [ - + ]: 364324 : assert(GetRefGraph(*entry.m_ref) == this);
2358 [ - + ]: 364324 : assert(GetRefIndex(*entry.m_ref) == idx);
2359 : : }
2360 [ + + ]: 389802 : if (entry.m_main_chunkindex_iterator != m_main_chunkindex.end()) {
2361 : : // Remember which entries we see a chunkindex entry for.
2362 [ - + ]: 216066 : assert(entry.m_locator[0].IsPresent());
2363 [ + - ]: 216066 : expected_chunkindex.insert(idx);
2364 : : }
2365 : : // Verify the Entry m_locators.
2366 : : bool was_present{false}, was_removed{false};
2367 [ + + ]: 1169406 : for (int level = 0; level < MAX_LEVELS; ++level) {
2368 : 779604 : const auto& locator = entry.m_locator[level];
2369 : : // Every Locator must be in exactly one of these 3 states.
2370 [ + + + + : 2338812 : assert(locator.IsMissing() + locator.IsRemoved() + locator.IsPresent() == 1);
- + ]
2371 [ + + ]: 779604 : if (locator.IsPresent()) {
2372 : : // Once removed, a transaction cannot be revived.
2373 [ - + ]: 325597 : assert(!was_removed);
2374 : : // Verify that the Cluster agrees with where the Locator claims the transaction is.
2375 [ - + ]: 325597 : assert(locator.cluster->GetClusterEntry(locator.index) == idx);
2376 : : // Remember that we expect said Cluster to appear in the ClusterSet::m_clusters.
2377 [ + - ]: 325597 : expected_clusters[level].insert(locator.cluster);
2378 : : was_present = true;
2379 [ + + ]: 789616 : } else if (locator.IsRemoved()) {
2380 : : // Level 0 (main) cannot have IsRemoved locators (IsMissing there means non-existing).
2381 [ - + ]: 10012 : assert(level > 0);
2382 : : // A Locator can only be IsRemoved if it was IsPresent before, and only once.
2383 [ - + ]: 10012 : assert(was_present && !was_removed);
2384 : : // Remember that we expect this GraphIndex to occur in the ClusterSet::m_removed.
2385 [ + - ]: 10012 : expected_removed[level].insert(idx);
2386 : : was_removed = true;
2387 : : }
2388 : : }
2389 : : }
2390 : :
2391 : : // For all levels (0 = main, 1 = staged)...
2392 [ + + ]: 25022 : for (int level = 0; level <= GetTopLevel(); ++level) {
2393 : 14606 : assert(level < MAX_LEVELS);
2394 : 14606 : auto& clusterset = GetClusterSet(level);
2395 : 14606 : std::set<const Cluster*> actual_clusters;
2396 : :
2397 : : // For all quality levels...
2398 [ + + ]: 102242 : for (int qual = 0; qual < int(QualityLevel::NONE); ++qual) {
2399 : 87636 : QualityLevel quality{qual};
2400 : 87636 : const auto& quality_clusters = clusterset.m_clusters[qual];
2401 : : // ... for all clusters in them ...
2402 [ + + ]: 355957 : for (ClusterSetIndex setindex = 0; setindex < quality_clusters.size(); ++setindex) {
2403 [ - + ]: 268321 : const auto& cluster = *quality_clusters[setindex];
2404 : : // Check the sequence number.
2405 [ - + ]: 268321 : assert(cluster.m_sequence < m_next_sequence_counter);
2406 [ - + ]: 268321 : assert(sequences.count(cluster.m_sequence) == 0);
2407 [ + - ]: 268321 : sequences.insert(cluster.m_sequence);
2408 : : // Remember we saw this Cluster (only if it is non-empty; empty Clusters aren't
2409 : : // expected to be referenced by the Entry vector).
2410 [ + + ]: 268321 : if (cluster.GetTxCount() != 0) {
2411 [ + - ]: 260743 : actual_clusters.insert(&cluster);
2412 : : }
2413 : : // Sanity check the cluster, according to the Cluster's internal rules.
2414 : 268321 : cluster.SanityCheck(*this, level);
2415 : : // Check that the cluster's quality and setindex matches its position in the quality list.
2416 [ - + ]: 268321 : assert(cluster.m_quality == quality);
2417 [ - + ]: 268321 : assert(cluster.m_setindex == setindex);
2418 : : }
2419 : : }
2420 : :
2421 : : // Verify that all to-be-removed transactions have valid identifiers.
2422 [ + + ]: 21028 : for (GraphIndex idx : clusterset.m_to_remove) {
2423 [ - + ]: 6422 : assert(idx < m_entries.size());
2424 : : // We cannot assert that all m_to_remove transactions are still present: ~Ref on a
2425 : : // (P,M) transaction (present in main, inherited in staging) will cause an m_to_remove
2426 : : // addition in both main and staging, but a subsequence ApplyRemovals in main will
2427 : : // cause it to disappear from staging too, leaving the m_to_remove in place.
2428 : : }
2429 : :
2430 : : // Verify that all to-be-added dependencies have valid identifiers.
2431 [ - + + + ]: 52018 : for (auto [par_idx, chl_idx] : clusterset.m_deps_to_add) {
2432 [ - + ]: 37412 : assert(par_idx != chl_idx);
2433 [ - + ]: 37412 : assert(par_idx < m_entries.size());
2434 [ - + ]: 37412 : assert(chl_idx < m_entries.size());
2435 : : }
2436 : :
2437 : : // Verify that the actually encountered clusters match the ones occurring in Entry vector.
2438 [ - + ]: 14606 : assert(actual_clusters == expected_clusters[level]);
2439 : :
2440 : : // Verify that the contents of m_removed matches what was expected based on the Entry vector.
2441 [ + - ]: 14606 : std::set<GraphIndex> actual_removed(clusterset.m_removed.begin(), clusterset.m_removed.end());
2442 [ + + ]: 50396 : for (auto i : expected_unlinked) {
2443 : : // If a transaction exists in both main and staging, and is removed from staging (adding
2444 : : // it to m_removed there), and consequently destroyed (wiping the locator completely),
2445 : : // it can remain in m_removed despite not having an IsRemoved() locator. Exclude those
2446 : : // transactions from the comparison here.
2447 : 35790 : actual_removed.erase(i);
2448 : 35790 : expected_removed[level].erase(i);
2449 : : }
2450 : :
2451 [ - + ]: 14606 : assert(actual_removed == expected_removed[level]);
2452 : :
2453 : : // If any GraphIndex entries remain in this ClusterSet, compact is not possible.
2454 [ + + ]: 14606 : if (!clusterset.m_deps_to_add.empty()) compact_possible = false;
2455 [ + + ]: 14606 : if (!clusterset.m_to_remove.empty()) compact_possible = false;
2456 [ + + ]: 14606 : if (!clusterset.m_removed.empty()) compact_possible = false;
2457 : :
2458 : : // For non-top levels, m_oversized must be known (as it cannot change until the level
2459 : : // on top is gone).
2460 [ + + - + ]: 14606 : if (level < GetTopLevel()) assert(clusterset.m_oversized.has_value());
2461 : 14606 : }
2462 : :
2463 : : // Verify that the contents of m_unlinked matches what was expected based on the Entry vector.
2464 [ + - ]: 10416 : std::set<GraphIndex> actual_unlinked(m_unlinked.begin(), m_unlinked.end());
2465 [ - + ]: 10416 : assert(actual_unlinked == expected_unlinked);
2466 : :
2467 : : // If compaction was possible, it should have been performed already, and m_unlinked must be
2468 : : // empty (to prevent memory leaks due to an ever-growing m_entries vector).
2469 [ + + ]: 10416 : if (compact_possible) {
2470 [ - + ]: 5905 : assert(actual_unlinked.empty());
2471 : : }
2472 : :
2473 : : // Finally, check the chunk index.
2474 : 10416 : std::set<GraphIndex> actual_chunkindex;
2475 : 10416 : FeeFrac last_chunk_feerate;
2476 [ + + ]: 226482 : for (const auto& chunk : m_main_chunkindex) {
2477 : 216066 : GraphIndex idx = chunk.m_graph_index;
2478 [ + - ]: 216066 : actual_chunkindex.insert(idx);
2479 [ + + ]: 216066 : auto chunk_feerate = m_entries[idx].m_main_chunk_feerate;
2480 [ + + ]: 216066 : if (!last_chunk_feerate.IsEmpty()) {
2481 [ - + ]: 206822 : assert(FeeRateCompare(last_chunk_feerate, chunk_feerate) >= 0);
2482 : : }
2483 : 216066 : last_chunk_feerate = chunk_feerate;
2484 : : }
2485 [ - + ]: 10416 : assert(actual_chunkindex == expected_chunkindex);
2486 [ + + + + : 72912 : }
- - - - ]
2487 : :
2488 : 20053 : bool TxGraphImpl::DoWork(uint64_t iters) noexcept
2489 : : {
2490 : 20053 : uint64_t iters_done{0};
2491 : : // First linearize everything in NEEDS_RELINEARIZE to an acceptable level. If more budget
2492 : : // remains after that, try to make everything optimal.
2493 [ + + ]: 59503 : for (QualityLevel quality : {QualityLevel::NEEDS_RELINEARIZE, QualityLevel::ACCEPTABLE}) {
2494 : : // First linearize staging, if it exists, then main.
2495 [ + + ]: 92231 : for (int level = GetTopLevel(); level >= 0; --level) {
2496 : : // Do not modify main if it has any observers.
2497 [ + + + + ]: 52781 : if (level == 0 && m_main_chunkindex_observers != 0) continue;
2498 : 42690 : ApplyDependencies(level);
2499 : 42690 : auto& clusterset = GetClusterSet(level);
2500 : : // Do not modify oversized levels.
2501 [ + - ]: 63211 : if (clusterset.m_oversized == true) continue;
2502 : 22169 : auto& queue = clusterset.m_clusters[int(quality)];
2503 [ + + ]: 24913 : while (!queue.empty()) {
2504 [ + + ]: 3119 : if (iters_done >= iters) return false;
2505 : : // Randomize the order in which we process, so that if the first cluster somehow
2506 : : // needs more work than what iters allows, we don't keep spending it on the same
2507 : : // one.
2508 : 2965 : auto pos = m_rng.randrange<size_t>(queue.size());
2509 : 2965 : auto iters_now = iters - iters_done;
2510 [ + + ]: 2965 : if (quality == QualityLevel::NEEDS_RELINEARIZE) {
2511 : : // If we're working with clusters that need relinearization still, only perform
2512 : : // up to m_acceptable_iters iterations. If they become ACCEPTABLE, and we still
2513 : : // have budget after all other clusters are ACCEPTABLE too, we'll spend the
2514 : : // remaining budget on trying to make them OPTIMAL.
2515 [ + + ]: 3363 : iters_now = std::min(iters_now, m_acceptable_iters);
2516 : : }
2517 [ + + ]: 2965 : auto [cost, improved] = queue[pos].get()->Relinearize(*this, iters_now);
2518 : 2965 : iters_done += cost;
2519 : : // If no improvement was made to the Cluster, it means we've essentially run out of
2520 : : // budget. Even though it may be the case that iters_done < iters still, the
2521 : : // linearizer decided there wasn't enough budget left to attempt anything with.
2522 : : // To avoid an infinite loop that keeps trying clusters with minuscule budgets,
2523 : : // stop here too.
2524 [ + + ]: 2965 : if (!improved) return false;
2525 : : }
2526 : : }
2527 : : }
2528 : : // All possible work has been performed, so we can return true. Note that this does *not* mean
2529 : : // that all clusters are optimally linearized now. It may be that there is nothing to do left
2530 : : // because all non-optimal clusters are in oversized and/or observer-bearing levels.
2531 : : return true;
2532 : : }
2533 : :
2534 : 73766 : void BlockBuilderImpl::Next() noexcept
2535 : : {
2536 : : // Don't do anything if we're already done.
2537 [ + + ]: 73766 : if (m_cur_iter == m_graph->m_main_chunkindex.end()) return;
2538 : 69083 : while (true) {
2539 : : // Advance the pointer, and stop if we reach the end.
2540 [ + + ]: 69083 : ++m_cur_iter;
2541 : 69083 : m_cur_cluster = nullptr;
2542 [ + + ]: 69083 : if (m_cur_iter == m_graph->m_main_chunkindex.end()) break;
2543 : : // Find the cluster pointed to by m_cur_iter.
2544 : 65364 : const auto& chunk_data = *m_cur_iter;
2545 : 65364 : const auto& chunk_end_entry = m_graph->m_entries[chunk_data.m_graph_index];
2546 : 65364 : m_cur_cluster = chunk_end_entry.m_locator[0].cluster;
2547 : 65364 : m_known_end_of_cluster = false;
2548 : : // If we previously skipped a chunk from this cluster we cannot include more from it.
2549 [ + + ]: 65364 : if (!m_excluded_clusters.contains(m_cur_cluster)) break;
2550 : : }
2551 : : }
2552 : :
2553 : 79220 : std::optional<std::pair<std::vector<TxGraph::Ref*>, FeePerWeight>> BlockBuilderImpl::GetCurrentChunk() noexcept
2554 : : {
2555 : 79220 : std::optional<std::pair<std::vector<TxGraph::Ref*>, FeePerWeight>> ret;
2556 : : // Populate the return value if we are not done.
2557 [ + + ]: 79220 : if (m_cur_iter != m_graph->m_main_chunkindex.end()) {
2558 : 69378 : ret.emplace();
2559 [ + + ]: 69378 : const auto& chunk_data = *m_cur_iter;
2560 [ + + ]: 69378 : const auto& chunk_end_entry = m_graph->m_entries[chunk_data.m_graph_index];
2561 [ + + ]: 69378 : if (chunk_data.m_chunk_count == LinearizationIndex(-1)) {
2562 : : // Special case in case just a single transaction remains, avoiding the need to
2563 : : // dispatch to and dereference Cluster.
2564 : 56451 : ret->first.resize(1);
2565 : 56451 : Assume(chunk_end_entry.m_ref != nullptr);
2566 : 56451 : ret->first[0] = chunk_end_entry.m_ref;
2567 : 56451 : m_known_end_of_cluster = true;
2568 : : } else {
2569 : 12927 : Assume(m_cur_cluster);
2570 : 12927 : ret->first.resize(chunk_data.m_chunk_count);
2571 : 12927 : auto start_pos = chunk_end_entry.m_main_lin_index + 1 - chunk_data.m_chunk_count;
2572 : 12927 : m_known_end_of_cluster = m_cur_cluster->GetClusterRefs(*m_graph, ret->first, start_pos);
2573 : : // If the chunk size was 1 and at end of cluster, then the special case above should
2574 : : // have been used.
2575 [ + + - + ]: 12927 : Assume(!m_known_end_of_cluster || chunk_data.m_chunk_count > 1);
2576 : : }
2577 : 69378 : ret->second = chunk_end_entry.m_main_chunk_feerate;
2578 : : }
2579 : 79220 : return ret;
2580 : : }
2581 : :
2582 : 9781 : BlockBuilderImpl::BlockBuilderImpl(TxGraphImpl& graph) noexcept : m_graph(&graph)
2583 : : {
2584 : : // Make sure all clusters in main are up to date, and acceptable.
2585 : 9781 : m_graph->MakeAllAcceptable(0);
2586 : : // There cannot remain any inapplicable dependencies (only possible if main is oversized).
2587 : 9781 : Assume(m_graph->m_main_clusterset.m_deps_to_add.empty());
2588 : : // Remember that this object is observing the graph's index, so that we can detect concurrent
2589 : : // modifications.
2590 : 9781 : ++m_graph->m_main_chunkindex_observers;
2591 : : // Find the first chunk.
2592 [ + + ]: 9781 : m_cur_iter = m_graph->m_main_chunkindex.begin();
2593 : 9781 : m_cur_cluster = nullptr;
2594 [ + + ]: 9781 : if (m_cur_iter != m_graph->m_main_chunkindex.end()) {
2595 : : // Find the cluster pointed to by m_cur_iter.
2596 : 8145 : const auto& chunk_data = *m_cur_iter;
2597 : 8145 : const auto& chunk_end_entry = m_graph->m_entries[chunk_data.m_graph_index];
2598 : 8145 : m_cur_cluster = chunk_end_entry.m_locator[0].cluster;
2599 : : }
2600 : 9781 : }
2601 : :
2602 : 19562 : BlockBuilderImpl::~BlockBuilderImpl()
2603 : : {
2604 : 9781 : Assume(m_graph->m_main_chunkindex_observers > 0);
2605 : : // Permit modifications to the main graph again after destroying the BlockBuilderImpl.
2606 : 9781 : --m_graph->m_main_chunkindex_observers;
2607 : 19562 : }
2608 : :
2609 : 70715 : void BlockBuilderImpl::Include() noexcept
2610 : : {
2611 : : // The actual inclusion of the chunk is done by the calling code. All we have to do is switch
2612 : : // to the next chunk.
2613 : 70715 : Next();
2614 : 70715 : }
2615 : :
2616 : 3051 : void BlockBuilderImpl::Skip() noexcept
2617 : : {
2618 : : // When skipping a chunk we need to not include anything more of the cluster, as that could make
2619 : : // the result topologically invalid. However, don't do this if the chunk is known to be the last
2620 : : // chunk of the cluster. This may significantly reduce the size of m_excluded_clusters,
2621 : : // especially when many singleton clusters are ignored.
2622 [ + + + + ]: 3051 : if (m_cur_cluster != nullptr && !m_known_end_of_cluster) {
2623 : 450 : m_excluded_clusters.insert(m_cur_cluster);
2624 : : }
2625 : 3051 : Next();
2626 : 3051 : }
2627 : :
2628 : 9781 : std::unique_ptr<TxGraph::BlockBuilder> TxGraphImpl::GetBlockBuilder() noexcept
2629 : : {
2630 [ - + ]: 9781 : return std::make_unique<BlockBuilderImpl>(*this);
2631 : : }
2632 : :
2633 : 23492 : std::pair<std::vector<TxGraph::Ref*>, FeePerWeight> TxGraphImpl::GetWorstMainChunk() noexcept
2634 : : {
2635 : 23492 : std::pair<std::vector<Ref*>, FeePerWeight> ret;
2636 : : // Make sure all clusters in main are up to date, and acceptable.
2637 : 23492 : MakeAllAcceptable(0);
2638 : 23492 : Assume(m_main_clusterset.m_deps_to_add.empty());
2639 : : // If the graph is not empty, populate ret.
2640 [ + + ]: 23492 : if (!m_main_chunkindex.empty()) {
2641 [ + + ]: 18811 : const auto& chunk_data = *m_main_chunkindex.rbegin();
2642 [ + + ]: 18811 : const auto& chunk_end_entry = m_entries[chunk_data.m_graph_index];
2643 : 18811 : Cluster* cluster = chunk_end_entry.m_locator[0].cluster;
2644 [ + + ]: 18811 : if (chunk_data.m_chunk_count == LinearizationIndex(-1) || chunk_data.m_chunk_count == 1) {
2645 : : // Special case for singletons.
2646 : 17377 : ret.first.resize(1);
2647 : 17377 : Assume(chunk_end_entry.m_ref != nullptr);
2648 : 17377 : ret.first[0] = chunk_end_entry.m_ref;
2649 : : } else {
2650 : 1434 : ret.first.resize(chunk_data.m_chunk_count);
2651 : 1434 : auto start_pos = chunk_end_entry.m_main_lin_index + 1 - chunk_data.m_chunk_count;
2652 : 1434 : cluster->GetClusterRefs(*this, ret.first, start_pos);
2653 : 1434 : std::reverse(ret.first.begin(), ret.first.end());
2654 : : }
2655 : 18811 : ret.second = chunk_end_entry.m_main_chunk_feerate;
2656 : : }
2657 : 23492 : return ret;
2658 : : }
2659 : :
2660 : 21726 : std::vector<TxGraph::Ref*> TxGraphImpl::Trim() noexcept
2661 : : {
2662 [ + + ]: 21726 : int level = GetTopLevel();
2663 [ + + - + ]: 21726 : Assume(m_main_chunkindex_observers == 0 || level != 0);
2664 : 21726 : std::vector<TxGraph::Ref*> ret;
2665 : :
2666 : : // Compute the groups of to-be-merged Clusters (which also applies all removals, and splits).
2667 : 21726 : auto& clusterset = GetClusterSet(level);
2668 [ + + ]: 21726 : if (clusterset.m_oversized == false) return ret;
2669 : 11434 : GroupClusters(level);
2670 : 11434 : Assume(clusterset.m_group_data.has_value());
2671 : : // Nothing to do if not oversized.
2672 : 11434 : Assume(clusterset.m_oversized.has_value());
2673 [ + - ]: 11434 : if (clusterset.m_oversized == false) return ret;
2674 : :
2675 : : // In this function, would-be clusters (as precomputed in m_group_data by GroupClusters) are
2676 : : // trimmed by removing transactions in them such that the resulting clusters satisfy the size
2677 : : // and count limits.
2678 : : //
2679 : : // It works by defining for each would-be cluster a rudimentary linearization: at every point
2680 : : // the highest-chunk-feerate remaining transaction is picked among those with no unmet
2681 : : // dependencies. "Dependency" here means either a to-be-added dependency (m_deps_to_add), or
2682 : : // an implicit dependency added between any two consecutive transaction in their current
2683 : : // cluster linearization. So it can be seen as a "merge sort" of the chunks of the clusters,
2684 : : // but respecting the dependencies being added.
2685 : : //
2686 : : // This rudimentary linearization is computed lazily, by putting all eligible (no unmet
2687 : : // dependencies) transactions in a heap, and popping the highest-feerate one from it. Along the
2688 : : // way, the counts and sizes of the would-be clusters up to that point are tracked (by
2689 : : // partitioning the involved transactions using a union-find structure). Any transaction whose
2690 : : // addition would cause a violation is removed, along with all their descendants.
2691 : : //
2692 : : // A next invocation of GroupClusters (after applying the removals) will compute the new
2693 : : // resulting clusters, and none of them will violate the limits.
2694 : :
2695 : : /** All dependencies (both to be added ones, and implicit ones between consecutive transactions
2696 : : * in existing cluster linearizations), sorted by parent. */
2697 : 7279 : std::vector<std::pair<GraphIndex, GraphIndex>> deps_by_parent;
2698 : : /** Same, but sorted by child. */
2699 : 7279 : std::vector<std::pair<GraphIndex, GraphIndex>> deps_by_child;
2700 : : /** Information about all transactions involved in a Cluster group to be trimmed, sorted by
2701 : : * GraphIndex. It contains entries both for transactions that have already been included,
2702 : : * and ones that have not yet been. */
2703 : 7279 : std::vector<TrimTxData> trim_data;
2704 : : /** Iterators into trim_data, treated as a max heap according to cmp_fn below. Each entry is
2705 : : * a transaction that has not yet been included yet, but all its ancestors have. */
2706 : 7279 : std::vector<std::vector<TrimTxData>::iterator> trim_heap;
2707 : : /** The list of representatives of the partitions a given transaction depends on. */
2708 : 7279 : std::vector<TrimTxData*> current_deps;
2709 : :
2710 : : /** Function to define the ordering of trim_heap. */
2711 : 171415 : static constexpr auto cmp_fn = [](auto a, auto b) noexcept {
2712 : : // Sort by increasing chunk feerate, and then by decreasing size.
2713 : : // We do not need to sort by cluster or within clusters, because due to the implicit
2714 : : // dependency between consecutive linearization elements, no two transactions from the
2715 : : // same Cluster will ever simultaneously be in the heap.
2716 : 164136 : return a->m_chunk_feerate < b->m_chunk_feerate;
2717 : : };
2718 : :
2719 : : /** Given a TrimTxData entry, find the representative of the partition it is in. */
2720 : 264411 : static constexpr auto find_fn = [](TrimTxData* arg) noexcept {
2721 [ + + - + ]: 379617 : while (arg != arg->m_uf_parent) {
2722 : : // Replace pointer to parent with pointer to grandparent (path splitting).
2723 : : // See https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Finding_set_representatives.
2724 : 122485 : auto par = arg->m_uf_parent;
2725 : 122485 : arg->m_uf_parent = par->m_uf_parent;
2726 : 122485 : arg = par;
2727 : : }
2728 : 257132 : return arg;
2729 : : };
2730 : :
2731 : : /** Given two TrimTxData entries, union the partitions they are in, and return the
2732 : : * representative. */
2733 : 110304 : static constexpr auto union_fn = [](TrimTxData* arg1, TrimTxData* arg2) noexcept {
2734 : : // Replace arg1 and arg2 by their representatives.
2735 [ - + ]: 206050 : auto rep1 = find_fn(arg1);
2736 : 103025 : auto rep2 = find_fn(arg2);
2737 : : // Bail out if both representatives are the same, because that means arg1 and arg2 are in
2738 : : // the same partition already.
2739 [ + - ]: 103025 : if (rep1 == rep2) return rep1;
2740 : : // Pick the lower-count root to become a child of the higher-count one.
2741 : : // See https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Union_by_size.
2742 [ + + ]: 103025 : if (rep1->m_uf_count < rep2->m_uf_count) std::swap(rep1, rep2);
2743 : 103025 : rep2->m_uf_parent = rep1;
2744 : : // Add the statistics of arg2 (which is no longer a representative) to those of arg1 (which
2745 : : // is now the representative for both).
2746 : 103025 : rep1->m_uf_size += rep2->m_uf_size;
2747 : 103025 : rep1->m_uf_count += rep2->m_uf_count;
2748 : 103025 : return rep1;
2749 : : };
2750 : :
2751 : : /** Get iterator to TrimTxData entry for a given index. */
2752 : 322057 : auto locate_fn = [&](GraphIndex index) noexcept {
2753 : 314778 : auto it = std::lower_bound(trim_data.begin(), trim_data.end(), index, [](TrimTxData& elem, GraphIndex idx) noexcept {
2754 [ + + ]: 1704427 : return elem.m_index < idx;
2755 : : });
2756 [ + - - + ]: 314778 : Assume(it != trim_data.end() && it->m_index == index);
2757 : 314778 : return it;
2758 : 7279 : };
2759 : :
2760 : : // For each group of to-be-merged Clusters.
2761 [ + + ]: 38031 : for (const auto& group_data : clusterset.m_group_data->m_groups) {
2762 [ + + ]: 30752 : trim_data.clear();
2763 [ - + ]: 30752 : trim_heap.clear();
2764 [ + + ]: 30752 : deps_by_child.clear();
2765 [ + + ]: 30752 : deps_by_parent.clear();
2766 : :
2767 : : // Gather trim data and implicit dependency data from all involved Clusters.
2768 : 30752 : auto cluster_span = std::span{clusterset.m_group_data->m_group_clusters}
2769 : 30752 : .subspan(group_data.m_cluster_offset, group_data.m_cluster_count);
2770 : 30752 : uint64_t size{0};
2771 [ + + ]: 123054 : for (Cluster* cluster : cluster_span) {
2772 : 92302 : size += cluster->AppendTrimData(trim_data, deps_by_child);
2773 : : }
2774 : : // If this group of Clusters does not violate any limits, continue to the next group.
2775 [ + + + + ]: 30752 : if (trim_data.size() <= m_max_cluster_count && size <= m_max_cluster_size) continue;
2776 : : // Sort the trim data by GraphIndex. In what follows, we will treat this sorted vector as
2777 : : // a map from GraphIndex to TrimTxData via locate_fn, and its ordering will not change
2778 : : // anymore.
2779 [ + + + + : 801974 : std::sort(trim_data.begin(), trim_data.end(), [](auto& a, auto& b) noexcept { return a.m_index < b.m_index; });
+ + + + +
+ + + + +
+ + + + +
+ - - +
+ ]
2780 : :
2781 : : // Add the explicitly added dependencies to deps_by_child.
2782 : 29115 : deps_by_child.insert(deps_by_child.end(),
2783 : 29115 : clusterset.m_deps_to_add.begin() + group_data.m_deps_offset,
2784 : 29115 : clusterset.m_deps_to_add.begin() + group_data.m_deps_offset + group_data.m_deps_count);
2785 : :
2786 : : // Sort deps_by_child by child transaction GraphIndex. The order will not be changed
2787 : : // anymore after this.
2788 [ + + + + : 1089711 : std::sort(deps_by_child.begin(), deps_by_child.end(), [](auto& a, auto& b) noexcept { return a.second < b.second; });
+ + + + +
+ + + + +
+ + + + +
+ - - +
+ ]
2789 : : // Fill m_parents_count and m_parents_offset in trim_data, as well as m_deps_left, and
2790 : : // initially populate trim_heap. Because of the sort above, all dependencies involving the
2791 : : // same child are grouped together, so a single linear scan suffices.
2792 : 29115 : auto deps_it = deps_by_child.begin();
2793 [ + + ]: 188934 : for (auto trim_it = trim_data.begin(); trim_it != trim_data.end(); ++trim_it) {
2794 : 159819 : trim_it->m_parent_offset = deps_it - deps_by_child.begin();
2795 : 159819 : trim_it->m_deps_left = 0;
2796 [ + + + + ]: 338001 : while (deps_it != deps_by_child.end() && deps_it->second == trim_it->m_index) {
2797 : 178182 : ++trim_it->m_deps_left;
2798 : 178182 : ++deps_it;
2799 : : }
2800 : 159819 : trim_it->m_parent_count = trim_it->m_deps_left;
2801 : : // If this transaction has no unmet dependencies, and is not oversized, add it to the
2802 : : // heap (just append for now, the heapification happens below).
2803 [ + + + + ]: 159819 : if (trim_it->m_deps_left == 0 && trim_it->m_tx_size <= m_max_cluster_size) {
2804 : 20454 : trim_heap.push_back(trim_it);
2805 : : }
2806 : : }
2807 : 29115 : Assume(deps_it == deps_by_child.end());
2808 : :
2809 : : // Construct deps_by_parent, sorted by parent transaction GraphIndex. The order will not be
2810 : : // changed anymore after this.
2811 : 29115 : deps_by_parent = deps_by_child;
2812 [ - - - - : 1123411 : std::sort(deps_by_parent.begin(), deps_by_parent.end(), [](auto& a, auto& b) noexcept { return a.first < b.first; });
+ + + + +
+ + + + +
+ + + + +
+ - - +
+ ]
2813 : : // Fill m_children_offset and m_children_count in trim_data. Because of the sort above, all
2814 : : // dependencies involving the same parent are grouped together, so a single linear scan
2815 : : // suffices.
2816 : 29115 : deps_it = deps_by_parent.begin();
2817 [ + + ]: 188934 : for (auto& trim_entry : trim_data) {
2818 : 159819 : trim_entry.m_children_count = 0;
2819 : 159819 : trim_entry.m_children_offset = deps_it - deps_by_parent.begin();
2820 [ + + + + ]: 338001 : while (deps_it != deps_by_parent.end() && deps_it->first == trim_entry.m_index) {
2821 : 178182 : ++trim_entry.m_children_count;
2822 : 178182 : ++deps_it;
2823 : : }
2824 : : }
2825 : 29115 : Assume(deps_it == deps_by_parent.end());
2826 : :
2827 : : // Build a heap of all transactions with 0 unmet dependencies.
2828 : 29115 : std::make_heap(trim_heap.begin(), trim_heap.end(), cmp_fn);
2829 : :
2830 : : // Iterate over to-be-included transactions, and convert them to included transactions, or
2831 : : // skip them if adding them would violate resource limits of the would-be cluster.
2832 : : //
2833 : : // It is possible that the heap empties without ever hitting either cluster limit, in case
2834 : : // the implied graph (to be added dependencies plus implicit dependency between each
2835 : : // original transaction and its predecessor in the linearization it came from) contains
2836 : : // cycles. Such cycles will be removed entirely, because each of the transactions in the
2837 : : // cycle permanently have unmet dependencies. However, this cannot occur in real scenarios
2838 : : // where Trim() is called to deal with reorganizations that would violate cluster limits,
2839 : : // as all added dependencies are in the same direction (from old mempool transactions to
2840 : : // new from-block transactions); cycles require dependencies in both directions to be
2841 : : // added.
2842 [ + + ]: 186701 : while (!trim_heap.empty()) {
2843 : : // Move the best remaining transaction to the end of trim_heap.
2844 : 128471 : std::pop_heap(trim_heap.begin(), trim_heap.end(), cmp_fn);
2845 : : // Pop it, and find its TrimTxData.
2846 [ + + ]: 128471 : auto& entry = *trim_heap.back();
2847 [ + + ]: 128471 : trim_heap.pop_back();
2848 : :
2849 : : // Initialize it as a singleton partition.
2850 : 128471 : entry.m_uf_parent = &entry;
2851 : 128471 : entry.m_uf_count = 1;
2852 : 128471 : entry.m_uf_size = entry.m_tx_size;
2853 : :
2854 : : // Find the distinct transaction partitions this entry depends on.
2855 [ + + ]: 128471 : current_deps.clear();
2856 [ + + ]: 282578 : for (auto& [par, chl] : std::span{deps_by_child}.subspan(entry.m_parent_offset, entry.m_parent_count)) {
2857 : 154107 : Assume(chl == entry.m_index);
2858 : 308214 : current_deps.push_back(find_fn(&*locate_fn(par)));
2859 : : }
2860 : 128471 : std::sort(current_deps.begin(), current_deps.end());
2861 : 128471 : current_deps.erase(std::unique(current_deps.begin(), current_deps.end()), current_deps.end());
2862 : :
2863 : : // Compute resource counts.
2864 : 128471 : uint32_t new_count = 1;
2865 : 128471 : uint64_t new_size = entry.m_tx_size;
2866 [ + + ]: 245860 : for (TrimTxData* ptr : current_deps) {
2867 : 117389 : new_count += ptr->m_uf_count;
2868 : 117389 : new_size += ptr->m_uf_size;
2869 : : }
2870 : : // Skip the entry if this would violate any limit.
2871 [ + + + + ]: 128471 : if (new_count > m_max_cluster_count || new_size > m_max_cluster_size) continue;
2872 : :
2873 : : // Union the partitions this transaction and all its dependencies are in together.
2874 : 115927 : auto rep = &entry;
2875 [ + + ]: 218952 : for (TrimTxData* ptr : current_deps) rep = union_fn(ptr, rep);
2876 : : // Mark the entry as included (so the loop below will not remove the transaction).
2877 : 115927 : entry.m_deps_left = uint32_t(-1);
2878 : : // Mark each to-be-added dependency involving this transaction as parent satisfied.
2879 [ + + ]: 276598 : for (auto& [par, chl] : std::span{deps_by_parent}.subspan(entry.m_children_offset, entry.m_children_count)) {
2880 : 160671 : Assume(par == entry.m_index);
2881 : 160671 : auto chl_it = locate_fn(chl);
2882 : : // Reduce the number of unmet dependencies of chl_it, and if that brings the number
2883 : : // to zero, add it to the heap of includable transactions.
2884 : 160671 : Assume(chl_it->m_deps_left > 0);
2885 [ + + ]: 160671 : if (--chl_it->m_deps_left == 0) {
2886 : 108017 : trim_heap.push_back(chl_it);
2887 : 108017 : std::push_heap(trim_heap.begin(), trim_heap.end(), cmp_fn);
2888 : : }
2889 : : }
2890 : : }
2891 : :
2892 : : // Remove all the transactions that were not processed above. Because nothing gets
2893 : : // processed until/unless all its dependencies are met, this automatically guarantees
2894 : : // that if a transaction is removed, all its descendants, or would-be descendants, are
2895 : : // removed as well.
2896 [ + + ]: 188934 : for (const auto& trim_entry : trim_data) {
2897 [ + + ]: 159819 : if (trim_entry.m_deps_left != uint32_t(-1)) {
2898 : 43892 : ret.push_back(m_entries[trim_entry.m_index].m_ref);
2899 : 43892 : clusterset.m_to_remove.push_back(trim_entry.m_index);
2900 : : }
2901 : : }
2902 : : }
2903 [ + - ]: 7279 : clusterset.m_group_data.reset();
2904 : 7279 : clusterset.m_oversized = false;
2905 : 7279 : Assume(!ret.empty());
2906 : 7279 : return ret;
2907 : 7279 : }
2908 : :
2909 : : } // namespace
2910 : :
2911 : 461468 : TxGraph::Ref::~Ref()
2912 : : {
2913 [ + + ]: 461468 : if (m_graph) {
2914 : : // Inform the TxGraph about the Ref being destroyed.
2915 : 45968 : m_graph->UnlinkRef(m_index);
2916 : 45968 : m_graph = nullptr;
2917 : : }
2918 : 461468 : }
2919 : :
2920 : 228130 : TxGraph::Ref& TxGraph::Ref::operator=(Ref&& other) noexcept
2921 : : {
2922 : : // Unlink the current graph, if any.
2923 [ - + ]: 228130 : if (m_graph) m_graph->UnlinkRef(m_index);
2924 : : // Inform the other's graph about the move, if any.
2925 [ + - ]: 228130 : if (other.m_graph) other.m_graph->UpdateRef(other.m_index, *this);
2926 : : // Actually update the contents.
2927 : 228130 : m_graph = other.m_graph;
2928 : 228130 : m_index = other.m_index;
2929 : 228130 : other.m_graph = nullptr;
2930 : 228130 : other.m_index = GraphIndex(-1);
2931 : 228130 : return *this;
2932 : : }
2933 : :
2934 : 0 : TxGraph::Ref::Ref(Ref&& other) noexcept
2935 : : {
2936 : : // Inform the TxGraph of other that its Ref is being moved.
2937 [ # # ]: 0 : if (other.m_graph) other.m_graph->UpdateRef(other.m_index, *this);
2938 : : // Actually move the contents.
2939 : 0 : std::swap(m_graph, other.m_graph);
2940 : 0 : std::swap(m_index, other.m_index);
2941 : 0 : }
2942 : :
2943 : 5208 : std::unique_ptr<TxGraph> MakeTxGraph(unsigned max_cluster_count, uint64_t max_cluster_size, uint64_t acceptable_iters) noexcept
2944 : : {
2945 [ - + ]: 5208 : return std::make_unique<TxGraphImpl>(max_cluster_count, max_cluster_size, acceptable_iters);
2946 : : }
|
