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