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 : :
13 : : #include <compare>
14 : : #include <memory>
15 : : #include <set>
16 : : #include <span>
17 : : #include <utility>
18 : :
19 : : namespace {
20 : :
21 : : using namespace cluster_linearize;
22 : :
23 : : /** The maximum number of levels a TxGraph can have (0 = main, 1 = staging). */
24 : : static constexpr int MAX_LEVELS{2};
25 : :
26 : : // Forward declare the TxGraph implementation class.
27 : : class TxGraphImpl;
28 : :
29 : : /** Position of a DepGraphIndex within a Cluster::m_linearization. */
30 : : using LinearizationIndex = uint32_t;
31 : : /** Position of a Cluster within Graph::ClusterSet::m_clusters. */
32 : : using ClusterSetIndex = uint32_t;
33 : :
34 : : /** Quality levels for cached cluster linearizations. */
35 : : enum class QualityLevel
36 : : {
37 : : /** This cluster may have multiple disconnected components, which are all NEEDS_RELINEARIZE. */
38 : : NEEDS_SPLIT,
39 : : /** This cluster may have multiple disconnected components, which are all ACCEPTABLE. */
40 : : NEEDS_SPLIT_ACCEPTABLE,
41 : : /** This cluster has undergone changes that warrant re-linearization. */
42 : : NEEDS_RELINEARIZE,
43 : : /** The minimal level of linearization has been performed, but it is not known to be optimal. */
44 : : ACCEPTABLE,
45 : : /** The linearization is known to be optimal. */
46 : : OPTIMAL,
47 : : /** This cluster is not registered in any ClusterSet::m_clusters.
48 : : * This must be the last entry in QualityLevel as ClusterSet::m_clusters is sized using it. */
49 : : NONE,
50 : : };
51 : :
52 : : /** A grouping of connected transactions inside a TxGraphImpl::ClusterSet. */
53 : : class Cluster
54 : : {
55 : : friend class TxGraphImpl;
56 : : using GraphIndex = TxGraph::GraphIndex;
57 : : using SetType = BitSet<MAX_CLUSTER_COUNT_LIMIT>;
58 : : /** The DepGraph for this cluster, holding all feerates, and ancestors/descendants. */
59 : : DepGraph<SetType> m_depgraph;
60 : : /** m_mapping[i] gives the GraphIndex for the position i transaction in m_depgraph. Values for
61 : : * positions i that do not exist in m_depgraph shouldn't ever be accessed and thus don't
62 : : * matter. m_mapping.size() equals m_depgraph.PositionRange(). */
63 : : std::vector<GraphIndex> m_mapping;
64 : : /** The current linearization of the cluster. m_linearization.size() equals
65 : : * m_depgraph.TxCount(). This is always kept topological. */
66 : : std::vector<DepGraphIndex> m_linearization;
67 : : /** The quality level of m_linearization. */
68 : : QualityLevel m_quality{QualityLevel::NONE};
69 : : /** Which position this Cluster has in Graph::ClusterSet::m_clusters[m_quality]. */
70 : : ClusterSetIndex m_setindex{ClusterSetIndex(-1)};
71 : : /** Which level this Cluster is at in the graph (-1=not inserted, 0=main, 1=staging). */
72 : : int m_level{-1};
73 : : /** Sequence number for this Cluster (for tie-breaking comparison between equal-chunk-feerate
74 : : transactions in distinct clusters). */
75 : : uint64_t m_sequence;
76 : :
77 : : public:
78 : : Cluster() noexcept = delete;
79 : : /** Construct an empty Cluster. */
80 : : explicit Cluster(uint64_t sequence) noexcept;
81 : : /** Construct a singleton Cluster. */
82 : : explicit Cluster(uint64_t sequence, TxGraphImpl& graph, const FeePerWeight& feerate, GraphIndex graph_index) noexcept;
83 : :
84 : : // Cannot move or copy (would invalidate Cluster* in Locator and ClusterSet). */
85 : : Cluster(const Cluster&) = delete;
86 : : Cluster& operator=(const Cluster&) = delete;
87 : : Cluster(Cluster&&) = delete;
88 : : Cluster& operator=(Cluster&&) = delete;
89 : :
90 : : // Generic helper functions.
91 : :
92 : : /** Whether the linearization of this Cluster can be exposed. */
93 : 1841937 : bool IsAcceptable(bool after_split = false) const noexcept
94 : : {
95 [ + + + + : 1811789 : return m_quality == QualityLevel::ACCEPTABLE || m_quality == QualityLevel::OPTIMAL ||
+ + ]
96 [ + + + + ]: 16330 : (after_split && m_quality == QualityLevel::NEEDS_SPLIT_ACCEPTABLE);
97 : : }
98 : : /** Whether the linearization of this Cluster is optimal. */
99 : 4698 : bool IsOptimal() const noexcept
100 : : {
101 : 4698 : return m_quality == QualityLevel::OPTIMAL;
102 : : }
103 : : /** Whether this cluster requires splitting. */
104 : 1633716 : bool NeedsSplitting() const noexcept
105 : : {
106 : 1633716 : return m_quality == QualityLevel::NEEDS_SPLIT ||
107 : 15479 : m_quality == QualityLevel::NEEDS_SPLIT_ACCEPTABLE;
108 : : }
109 : : /** Get the number of transactions in this Cluster. */
110 [ + + ]: 23561 : LinearizationIndex GetTxCount() const noexcept { return m_linearization.size(); }
111 : : /** Given a DepGraphIndex into this Cluster, find the corresponding GraphIndex. */
112 : 122531 : GraphIndex GetClusterEntry(DepGraphIndex index) const noexcept { return m_mapping[index]; }
113 : : /** Only called by Graph::SwapIndexes. */
114 : 10134 : void UpdateMapping(DepGraphIndex cluster_idx, GraphIndex graph_idx) noexcept { m_mapping[cluster_idx] = graph_idx; }
115 : : /** Push changes to Cluster and its linearization to the TxGraphImpl Entry objects. */
116 : : void Updated(TxGraphImpl& graph) noexcept;
117 : : /** Create a copy of this Cluster in staging, returning a pointer to it (used by PullIn). */
118 : : Cluster* CopyToStaging(TxGraphImpl& graph) const noexcept;
119 : : /** Get the list of Clusters in main that conflict with this one (which is assumed to be in staging). */
120 : : void GetConflicts(const TxGraphImpl& graph, std::vector<Cluster*>& out) const noexcept;
121 : : /** Mark all the Entry objects belonging to this staging Cluster as missing. The Cluster must be
122 : : * deleted immediately after. */
123 : : void MakeStagingTransactionsMissing(TxGraphImpl& graph) noexcept;
124 : : /** Remove all transactions from a Cluster. */
125 : : void Clear(TxGraphImpl& graph) noexcept;
126 : : /** Change a Cluster's level from 1 (staging) to 0 (main). */
127 : : void MoveToMain(TxGraphImpl& graph) noexcept;
128 : :
129 : : // Functions that implement the Cluster-specific side of internal TxGraphImpl mutations.
130 : :
131 : : /** Apply all removals from the front of to_remove that apply to this Cluster, popping them
132 : : * off. These must be at least one such entry. */
133 : : void ApplyRemovals(TxGraphImpl& graph, std::span<GraphIndex>& to_remove) noexcept;
134 : : /** Split this cluster (must have a NEEDS_SPLIT* quality). Returns whether to delete this
135 : : * Cluster afterwards. */
136 : : [[nodiscard]] bool Split(TxGraphImpl& graph) noexcept;
137 : : /** Move all transactions from cluster to *this (as separate components). */
138 : : void Merge(TxGraphImpl& graph, Cluster& cluster) noexcept;
139 : : /** Given a span of (parent, child) pairs that all belong to this Cluster, apply them. */
140 : : void ApplyDependencies(TxGraphImpl& graph, std::span<std::pair<GraphIndex, GraphIndex>> to_apply) noexcept;
141 : : /** Improve the linearization of this Cluster. */
142 : : void Relinearize(TxGraphImpl& graph, uint64_t max_iters) noexcept;
143 : :
144 : : // Functions that implement the Cluster-specific side of public TxGraph functions.
145 : :
146 : : /** Process elements from the front of args that apply to this cluster, and append Refs for the
147 : : * union of their ancestors to output. */
148 : : void GetAncestorRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept;
149 : : /** Process elements from the front of args that apply to this cluster, and append Refs for the
150 : : * union of their descendants to output. */
151 : : void GetDescendantRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept;
152 : : /** Get a vector of Refs for all elements of this Cluster, in linearization order. */
153 : : std::vector<TxGraph::Ref*> GetClusterRefs(const TxGraphImpl& graph) noexcept;
154 : : /** Get the individual transaction feerate of a Cluster element. */
155 : : FeePerWeight GetIndividualFeerate(DepGraphIndex idx) noexcept;
156 : : /** Modify the fee of a Cluster element. */
157 : : void SetFee(TxGraphImpl& graph, DepGraphIndex idx, int64_t fee) noexcept;
158 : :
159 : : // Debugging functions.
160 : :
161 : : void SanityCheck(const TxGraphImpl& graph, int level) const;
162 : : };
163 : :
164 : :
165 : : /** The transaction graph, including staged changes.
166 : : *
167 : : * The overall design of the data structure consists of 3 interlinked representations:
168 : : * - The transactions (held as a vector of TxGraphImpl::Entry inside TxGraphImpl).
169 : : * - The clusters (Cluster objects in per-quality vectors inside TxGraphImpl::ClusterSet).
170 : : * - The Refs (TxGraph::Ref objects, held externally by users of the TxGraph class)
171 : : *
172 : : * The Clusters are kept in one or two ClusterSet objects, one for the "main" graph, and one for
173 : : * the proposed changes ("staging"). If a transaction occurs in both, they share the same Entry,
174 : : * but there will be a separate Cluster per graph.
175 : : *
176 : : * Clusters and Refs contain the index of the Entry objects they refer to, and the Entry objects
177 : : * refer back to the Clusters and Refs the corresponding transaction is contained in.
178 : : *
179 : : * While redundant, this permits moving all of them independently, without invalidating things
180 : : * or costly iteration to fix up everything:
181 : : * - Entry objects can be moved to fill holes left by removed transactions in the Entry vector
182 : : * (see TxGraphImpl::Compact).
183 : : * - Clusters can be rewritten continuously (removals can cause them to split, new dependencies
184 : : * can cause them to be merged).
185 : : * - Ref objects can be held outside the class, while permitting them to be moved around, and
186 : : * inherited from.
187 : : */
188 : : class TxGraphImpl final : public TxGraph
189 : : {
190 : : friend class Cluster;
191 : : private:
192 : : /** Internal RNG. */
193 : : FastRandomContext m_rng;
194 : : /** This TxGraphImpl's maximum cluster count limit. */
195 : : const DepGraphIndex m_max_cluster_count;
196 : :
197 : : /** Information about one group of Clusters to be merged. */
198 : : struct GroupEntry
199 : : {
200 : : /** Where the clusters to be merged start in m_group_clusters. */
201 : : uint32_t m_cluster_offset;
202 : : /** How many clusters to merge. */
203 : : uint32_t m_cluster_count;
204 : : /** Where the dependencies for this cluster group in m_deps_to_add start. */
205 : : uint32_t m_deps_offset;
206 : : /** How many dependencies to add. */
207 : : uint32_t m_deps_count;
208 : : };
209 : :
210 : : /** Information about all groups of Clusters to be merged. */
211 : 58987 : struct GroupData
212 : : {
213 : : /** The groups of Clusters to be merged. */
214 : : std::vector<GroupEntry> m_groups;
215 : : /** Which clusters are to be merged. GroupEntry::m_cluster_offset indexes into this. */
216 : : std::vector<Cluster*> m_group_clusters;
217 : : /** Whether at least one of the groups cannot be applied because it would result in a
218 : : * Cluster that violates the cluster count limit. */
219 : : bool m_group_oversized;
220 : : };
221 : :
222 : : /** The collection of all Clusters in main or staged. */
223 : : struct ClusterSet
224 : : {
225 : : /** The vectors of clusters, one vector per quality level. ClusterSetIndex indexes into each. */
226 : : std::array<std::vector<std::unique_ptr<Cluster>>, int(QualityLevel::NONE)> m_clusters;
227 : : /** Which removals have yet to be applied. */
228 : : std::vector<GraphIndex> m_to_remove;
229 : : /** Which dependencies are to be added ((parent,child) pairs). GroupData::m_deps_offset indexes
230 : : * into this. */
231 : : std::vector<std::pair<GraphIndex, GraphIndex>> m_deps_to_add;
232 : : /** Information about the merges to be performed, if known. */
233 : : std::optional<GroupData> m_group_data = GroupData{};
234 : : /** Which entries were removed in this ClusterSet (so they can be wiped on abort). This
235 : : * includes all entries which have an (R) removed locator at this level (staging only),
236 : : * plus optionally any transaction in m_unlinked. */
237 : : std::vector<GraphIndex> m_removed;
238 : : /** Total number of transactions in this graph (sum of all transaction counts in all
239 : : * Clusters, and for staging also those inherited from the main ClusterSet). */
240 : : GraphIndex m_txcount{0};
241 : : /** Whether this graph is oversized (if known). This roughly matches
242 : : * m_group_data->m_group_oversized, but may be known even if m_group_data is not. */
243 : : std::optional<bool> m_oversized{false};
244 : :
245 : 9369 : ClusterSet() noexcept = default;
246 : : };
247 : :
248 : : /** The main ClusterSet. */
249 : : ClusterSet m_main_clusterset;
250 : : /** The staging ClusterSet, if any. */
251 : : std::optional<ClusterSet> m_staging_clusterset;
252 : : /** Next sequence number to assign to created Clusters. */
253 : : uint64_t m_next_sequence_counter{0};
254 : :
255 : : /** A Locator that describes whether, where, and in which Cluster an Entry appears.
256 : : * Every Entry has MAX_LEVELS locators, as it may appear in one Cluster per level.
257 : : *
258 : : * Each level of a Locator is in one of three states:
259 : : *
260 : : * - (P)resent: actually occurs in a Cluster at that level.
261 : : *
262 : : * - (M)issing:
263 : : * - In the main graph: the transaction does not exist in main.
264 : : * - In the staging graph: the transaction's existence is the same as in main. If it doesn't
265 : : * exist in main, (M) in staging means it does not exist there
266 : : * either. If it does exist in main, (M) in staging means the
267 : : * cluster it is in has not been modified in staging, and thus the
268 : : * transaction implicitly exists in staging too (without explicit
269 : : * Cluster object; see PullIn() to create it in staging too).
270 : : *
271 : : * - (R)emoved: only possible in staging; it means the transaction exists in main, but is
272 : : * removed in staging.
273 : : *
274 : : * The following combinations are possible:
275 : : * - (M,M): the transaction doesn't exist in either graph.
276 : : * - (P,M): the transaction exists in both, but only exists explicitly in a Cluster object in
277 : : * main. Its existence in staging is inherited from main.
278 : : * - (P,P): the transaction exists in both, and is materialized in both. Thus, the clusters
279 : : * and/or their linearizations may be different in main and staging.
280 : : * - (M,P): the transaction is added in staging, and does not exist in main.
281 : : * - (P,R): the transaction exists in main, but is removed in staging.
282 : : *
283 : : * When staging does not exist, only (M,M) and (P,M) are possible.
284 : : */
285 : : struct Locator
286 : : {
287 : : /** Which Cluster the Entry appears in (nullptr = missing). */
288 : : Cluster* cluster{nullptr};
289 : : /** Where in the Cluster it appears (if cluster == nullptr: 0 = missing, -1 = removed). */
290 : : DepGraphIndex index{0};
291 : :
292 : : /** Mark this Locator as missing (= same as lower level, or non-existing if level 0). */
293 : 1040 : void SetMissing() noexcept { cluster = nullptr; index = 0; }
294 : : /** Mark this Locator as removed (not allowed in level 0). */
295 : 2416 : void SetRemoved() noexcept { cluster = nullptr; index = DepGraphIndex(-1); }
296 : : /** Mark this Locator as present, in the specified Cluster. */
297 : 314596 : void SetPresent(Cluster* c, DepGraphIndex i) noexcept { cluster = c; index = i; }
298 : : /** Check if this Locator is missing. */
299 [ + + + + ]: 274201 : bool IsMissing() const noexcept { return cluster == nullptr && index == 0; }
300 : : /** Check if this Locator is removed. */
301 [ + + + - : 159587 : bool IsRemoved() const noexcept { return cluster == nullptr && index == DepGraphIndex(-1); }
+ + ]
302 : : /** Check if this Locator is present (in some Cluster). */
303 [ + + ]: 96309 : bool IsPresent() const noexcept { return cluster != nullptr; }
304 : : };
305 : :
306 : : /** Internal information about each transaction in a TxGraphImpl. */
307 : 82496 : struct Entry
308 : : {
309 : : /** Pointer to the corresponding Ref object if any, or nullptr if unlinked. */
310 : : Ref* m_ref{nullptr};
311 : : /** Which Cluster and position therein this Entry appears in. ([0] = main, [1] = staged). */
312 : : Locator m_locator[MAX_LEVELS];
313 : : /** The chunk feerate of this transaction in main (if present in m_locator[0]). */
314 : : FeePerWeight m_main_chunk_feerate;
315 : : /** The position this transaction has in the main linearization (if present). */
316 : : LinearizationIndex m_main_lin_index;
317 : : };
318 : :
319 : : /** The set of all transactions (in all levels combined). GraphIndex values index into this. */
320 : : std::vector<Entry> m_entries;
321 : :
322 : : /** Set of Entries which have no linked Ref anymore. */
323 : : std::vector<GraphIndex> m_unlinked;
324 : :
325 : : /** Compare two Cluster* by their m_sequence value (while supporting nullptr). */
326 : 578226 : static std::strong_ordering CompareClusters(Cluster* a, Cluster* b) noexcept
327 : : {
328 : : // The nullptr pointer compares before everything else.
329 [ + + ]: 578226 : if (a == nullptr || b == nullptr) {
330 [ + + + + ]: 6781 : return (a != nullptr) <=> (b != nullptr);
331 : : }
332 : : // If neither pointer is nullptr, compare the Clusters' sequence numbers.
333 [ + + - + ]: 571445 : Assume(a == b || a->m_sequence != b->m_sequence);
334 [ + + + + ]: 571445 : return a->m_sequence <=> b->m_sequence;
335 : : }
336 : :
337 : : public:
338 : : /** Construct a new TxGraphImpl with the specified maximum cluster count. */
339 : 2258 : explicit TxGraphImpl(DepGraphIndex max_cluster_count) noexcept :
340 : 2258 : m_max_cluster_count(max_cluster_count)
341 : : {
342 : 2258 : Assume(max_cluster_count >= 1);
343 : 2258 : Assume(max_cluster_count <= MAX_CLUSTER_COUNT_LIMIT);
344 : 2258 : }
345 : :
346 : : /** Destructor. */
347 : : ~TxGraphImpl() noexcept;
348 : :
349 : : // Cannot move or copy (would invalidate TxGraphImpl* in Ref, MiningOrder, EvictionOrder).
350 : : TxGraphImpl(const TxGraphImpl&) = delete;
351 : : TxGraphImpl& operator=(const TxGraphImpl&) = delete;
352 : : TxGraphImpl(TxGraphImpl&&) = delete;
353 : : TxGraphImpl& operator=(TxGraphImpl&&) = delete;
354 : :
355 : : // Simple helper functions.
356 : :
357 : : /** Swap the Entry referred to by a and the one referred to by b. */
358 : : void SwapIndexes(GraphIndex a, GraphIndex b) noexcept;
359 : : /** If idx exists in the specified level ClusterSet (explicitly, or in the level below and not
360 : : * removed), return the Cluster it is in. Otherwise, return nullptr. */
361 : : Cluster* FindCluster(GraphIndex idx, int level) const noexcept;
362 : : /** Extract a Cluster from its ClusterSet. */
363 : : std::unique_ptr<Cluster> ExtractCluster(int level, QualityLevel quality, ClusterSetIndex setindex) noexcept;
364 : : /** Delete a Cluster. */
365 : : void DeleteCluster(Cluster& cluster) noexcept;
366 : : /** Insert a Cluster into its ClusterSet. */
367 : : ClusterSetIndex InsertCluster(int level, std::unique_ptr<Cluster>&& cluster, QualityLevel quality) noexcept;
368 : : /** Change the QualityLevel of a Cluster (identified by old_quality and old_index). */
369 : : void SetClusterQuality(int level, QualityLevel old_quality, ClusterSetIndex old_index, QualityLevel new_quality) noexcept;
370 : : /** Get the index of the top level ClusterSet (staging if it exists, main otherwise). */
371 [ - + - + : 1468317 : int GetTopLevel() const noexcept { return m_staging_clusterset.has_value(); }
- + + + ]
372 : : /** Get the specified level (staging if it exists and main_only is not specified, main otherwise). */
373 [ + + + + : 129488 : int GetSpecifiedLevel(bool main_only) const noexcept { return m_staging_clusterset.has_value() && !main_only; }
+ + + + +
+ + + + +
+ + + + ]
374 : : /** Get a reference to the ClusterSet at the specified level (which must exist). */
375 : : ClusterSet& GetClusterSet(int level) noexcept;
376 : : const ClusterSet& GetClusterSet(int level) const noexcept;
377 : : /** Make a transaction not exist at a specified level. It must currently exist there. */
378 : : void ClearLocator(int level, GraphIndex index) noexcept;
379 : : /** Find which Clusters in main conflict with ones in staging. */
380 : : std::vector<Cluster*> GetConflicts() const noexcept;
381 : :
382 : : // Functions for handling Refs.
383 : :
384 : : /** Only called by Ref's move constructor/assignment to update Ref locations. */
385 : 82496 : void UpdateRef(GraphIndex idx, Ref& new_location) noexcept final
386 : : {
387 : 82496 : auto& entry = m_entries[idx];
388 : 82496 : Assume(entry.m_ref != nullptr);
389 : 82496 : entry.m_ref = &new_location;
390 : 82496 : }
391 : :
392 : : /** Only called by Ref::~Ref to unlink Refs, and Ref's move assignment. */
393 : 21406 : void UnlinkRef(GraphIndex idx) noexcept final
394 : : {
395 : 21406 : auto& entry = m_entries[idx];
396 : 21406 : Assume(entry.m_ref != nullptr);
397 : 21406 : entry.m_ref = nullptr;
398 : : // Mark the transaction as to be removed in all levels where it explicitly or implicitly
399 : : // exists.
400 : 21406 : bool exists_anywhere{false};
401 : 21406 : bool exists{false};
402 [ + + ]: 47726 : for (int level = 0; level <= GetTopLevel(); ++level) {
403 [ + + ]: 26320 : if (entry.m_locator[level].IsPresent()) {
404 : : exists_anywhere = true;
405 : : exists = true;
406 [ + + ]: 13891 : } else if (entry.m_locator[level].IsRemoved()) {
407 : : exists = false;
408 : : }
409 [ + + ]: 13374 : if (exists) {
410 : 15031 : auto& clusterset = GetClusterSet(level);
411 : 15031 : clusterset.m_to_remove.push_back(idx);
412 : : // Force recomputation of grouping data.
413 [ + + ]: 15031 : clusterset.m_group_data = std::nullopt;
414 : : // Do not wipe the oversized state of main if staging exists. The reason for this
415 : : // is that the alternative would mean that cluster merges may need to be applied to
416 : : // a formerly-oversized main graph while staging exists (to satisfy chunk feerate
417 : : // queries into main, for example), and such merges could conflict with pulls of
418 : : // some of their constituents into staging.
419 [ + + + + ]: 32651 : if (level == GetTopLevel() && clusterset.m_oversized == true) {
420 : 1756 : clusterset.m_oversized = std::nullopt;
421 : : }
422 : : }
423 : : }
424 : 21406 : m_unlinked.push_back(idx);
425 [ + + ]: 21406 : if (!exists_anywhere) Compact();
426 : 21406 : }
427 : :
428 : : // Functions related to various normalization/application steps.
429 : : /** Get rid of unlinked Entry objects in m_entries, if possible (this changes the GraphIndex
430 : : * values for remaining Entry objects, so this only does something when no to-be-applied
431 : : * operations or staged removals referring to GraphIndexes remain). */
432 : : void Compact() noexcept;
433 : : /** If cluster is not in staging, copy it there, and return a pointer to it.
434 : : * Staging must exist, and this modifies the locators of its
435 : : * transactions from inherited (P,M) to explicit (P,P). */
436 : : Cluster* PullIn(Cluster* cluster) noexcept;
437 : : /** Apply all removals queued up in m_to_remove to the relevant Clusters (which get a
438 : : * NEEDS_SPLIT* QualityLevel) up to the specified level. */
439 : : void ApplyRemovals(int up_to_level) noexcept;
440 : : /** Split an individual cluster. */
441 : : void Split(Cluster& cluster) noexcept;
442 : : /** Split all clusters that need splitting up to the specified level. */
443 : : void SplitAll(int up_to_level) noexcept;
444 : : /** Populate m_group_data based on m_deps_to_add in the specified level. */
445 : : void GroupClusters(int level) noexcept;
446 : : /** Merge the specified clusters. */
447 : : void Merge(std::span<Cluster*> to_merge) noexcept;
448 : : /** Apply all m_deps_to_add to the relevant Clusters in the specified level. */
449 : : void ApplyDependencies(int level) noexcept;
450 : : /** Make a specified Cluster have quality ACCEPTABLE or OPTIMAL. */
451 : : void MakeAcceptable(Cluster& cluster) noexcept;
452 : : /** Make all Clusters at the specified level have quality ACCEPTABLE or OPTIMAL. */
453 : : void MakeAllAcceptable(int level) noexcept;
454 : :
455 : : // Implementations for the public TxGraph interface.
456 : :
457 : : Ref AddTransaction(const FeePerWeight& feerate) noexcept final;
458 : : void RemoveTransaction(const Ref& arg) noexcept final;
459 : : void AddDependency(const Ref& parent, const Ref& child) noexcept final;
460 : : void SetTransactionFee(const Ref&, int64_t fee) noexcept final;
461 : :
462 : : void DoWork() noexcept final;
463 : :
464 : : void StartStaging() noexcept final;
465 : : void CommitStaging() noexcept final;
466 : : void AbortStaging() noexcept final;
467 : 14371 : bool HaveStaging() const noexcept final { return m_staging_clusterset.has_value(); }
468 : :
469 : : bool Exists(const Ref& arg, bool main_only = false) noexcept final;
470 : : FeePerWeight GetMainChunkFeerate(const Ref& arg) noexcept final;
471 : : FeePerWeight GetIndividualFeerate(const Ref& arg) noexcept final;
472 : : std::vector<Ref*> GetCluster(const Ref& arg, bool main_only = false) noexcept final;
473 : : std::vector<Ref*> GetAncestors(const Ref& arg, bool main_only = false) noexcept final;
474 : : std::vector<Ref*> GetDescendants(const Ref& arg, bool main_only = false) noexcept final;
475 : : std::vector<Ref*> GetAncestorsUnion(std::span<const Ref* const> args, bool main_only = false) noexcept final;
476 : : std::vector<Ref*> GetDescendantsUnion(std::span<const Ref* const> args, bool main_only = false) noexcept final;
477 : : GraphIndex GetTransactionCount(bool main_only = false) noexcept final;
478 : : bool IsOversized(bool main_only = false) noexcept final;
479 : : std::strong_ordering CompareMainOrder(const Ref& a, const Ref& b) noexcept final;
480 : : GraphIndex CountDistinctClusters(std::span<const Ref* const> refs, bool main_only = false) noexcept final;
481 : :
482 : : void SanityCheck() const final;
483 : : };
484 : :
485 : 3532546 : TxGraphImpl::ClusterSet& TxGraphImpl::GetClusterSet(int level) noexcept
486 : : {
487 [ + + ]: 3532546 : if (level == 0) return m_main_clusterset;
488 : 332824 : Assume(level == 1);
489 : 332824 : Assume(m_staging_clusterset.has_value());
490 : 332824 : return *m_staging_clusterset;
491 : : }
492 : :
493 : 11586 : const TxGraphImpl::ClusterSet& TxGraphImpl::GetClusterSet(int level) const noexcept
494 : : {
495 [ + + ]: 11586 : if (level == 0) return m_main_clusterset;
496 : 7070 : Assume(level == 1);
497 : 7070 : Assume(m_staging_clusterset.has_value());
498 : 7070 : return *m_staging_clusterset;
499 : : }
500 : :
501 : 29894 : void TxGraphImpl::ClearLocator(int level, GraphIndex idx) noexcept
502 : : {
503 : 29894 : auto& entry = m_entries[idx];
504 : 29894 : auto& clusterset = GetClusterSet(level);
505 : 29894 : Assume(entry.m_locator[level].IsPresent());
506 : : // Change the locator from Present to Missing or Removed.
507 [ + + + + ]: 29894 : if (level == 0 || !entry.m_locator[level - 1].IsPresent()) {
508 : 27478 : entry.m_locator[level].SetMissing();
509 : : } else {
510 : 2416 : entry.m_locator[level].SetRemoved();
511 : 2416 : clusterset.m_removed.push_back(idx);
512 : : }
513 : : // Update the transaction count.
514 : 29894 : --clusterset.m_txcount;
515 : : // If clearing main, adjust the status of Locators of this transaction in staging, if it exists.
516 [ + + + + ]: 29894 : if (level == 0 && GetTopLevel() == 1) {
517 [ + + ]: 13480 : if (entry.m_locator[1].IsRemoved()) {
518 : 1155 : entry.m_locator[1].SetMissing();
519 [ + + ]: 12325 : } else if (!entry.m_locator[1].IsPresent()) {
520 : 1763 : --m_staging_clusterset->m_txcount;
521 : : }
522 : : }
523 : 29894 : }
524 : :
525 : 139827 : void Cluster::Updated(TxGraphImpl& graph) noexcept
526 : : {
527 : : // Update all the Locators for this Cluster's Entry objects.
528 [ + + ]: 438316 : for (DepGraphIndex idx : m_linearization) {
529 : 298489 : auto& entry = graph.m_entries[m_mapping[idx]];
530 : 298489 : entry.m_locator[m_level].SetPresent(this, idx);
531 : : }
532 : : // If this is for the main graph (level = 0), and the Cluster's quality is ACCEPTABLE or
533 : : // OPTIMAL, compute its chunking and store its information in the Entry's m_main_lin_index
534 : : // and m_main_chunk_feerate. These fields are only accessed after making the entire graph
535 : : // ACCEPTABLE, so it is pointless to compute these if we haven't reached that quality level
536 : : // yet.
537 [ + + ]: 139827 : if (m_level == 0 && IsAcceptable()) {
538 : 78054 : LinearizationChunking chunking(m_depgraph, m_linearization);
539 : 78054 : LinearizationIndex lin_idx{0};
540 : : // Iterate over the chunks.
541 [ + + ]: 209952 : for (unsigned chunk_idx = 0; chunk_idx < chunking.NumChunksLeft(); ++chunk_idx) {
542 : 131898 : auto chunk = chunking.GetChunk(chunk_idx);
543 : 131898 : Assume(chunk.transactions.Any());
544 : : // Iterate over the transactions in the linearization, which must match those in chunk.
545 : 161676 : do {
546 : 161676 : DepGraphIndex idx = m_linearization[lin_idx];
547 : 161676 : GraphIndex graph_idx = m_mapping[idx];
548 : 161676 : auto& entry = graph.m_entries[graph_idx];
549 : 161676 : entry.m_main_lin_index = lin_idx++;
550 : 161676 : entry.m_main_chunk_feerate = FeePerWeight::FromFeeFrac(chunk.feerate);
551 : 161676 : Assume(chunk.transactions[idx]);
552 : 161676 : chunk.transactions.Reset(idx);
553 [ + + ]: 161676 : } while(chunk.transactions.Any());
554 : : }
555 : 78054 : }
556 : 139827 : }
557 : :
558 : 14114 : void Cluster::GetConflicts(const TxGraphImpl& graph, std::vector<Cluster*>& out) const noexcept
559 : : {
560 : 14114 : Assume(m_level == 1);
561 [ + + ]: 37170 : for (auto i : m_linearization) {
562 [ + + ]: 23056 : auto& entry = graph.m_entries[m_mapping[i]];
563 : : // For every transaction Entry in this Cluster, if it also exists in a lower-level Cluster,
564 : : // then that Cluster conflicts.
565 [ + + ]: 23056 : if (entry.m_locator[0].IsPresent()) {
566 : 10282 : out.push_back(entry.m_locator[0].cluster);
567 : : }
568 : : }
569 : 14114 : }
570 : :
571 : 5290 : std::vector<Cluster*> TxGraphImpl::GetConflicts() const noexcept
572 : : {
573 : 5290 : Assume(GetTopLevel() == 1);
574 : 5290 : auto& clusterset = GetClusterSet(1);
575 : 5290 : std::vector<Cluster*> ret;
576 : : // All main Clusters containing transactions in m_removed (so (P,R) ones) are conflicts.
577 [ + + ]: 6066 : for (auto i : clusterset.m_removed) {
578 [ + + ]: 776 : auto& entry = m_entries[i];
579 [ + + ]: 776 : if (entry.m_locator[0].IsPresent()) {
580 : 651 : ret.push_back(entry.m_locator[0].cluster);
581 : : }
582 : : }
583 : : // Then go over all Clusters at this level, and find their conflicts (the (P,P) ones).
584 [ + + ]: 31740 : for (int quality = 0; quality < int(QualityLevel::NONE); ++quality) {
585 : 26450 : auto& clusters = clusterset.m_clusters[quality];
586 [ + + ]: 40564 : for (const auto& cluster : clusters) {
587 : 14114 : cluster->GetConflicts(*this, ret);
588 : : }
589 : : }
590 : : // Deduplicate the result (the same Cluster may appear multiple times).
591 : 35601 : std::sort(ret.begin(), ret.end(), [](Cluster* a, Cluster* b) noexcept { return CompareClusters(a, b) < 0; });
592 : 5290 : ret.erase(std::unique(ret.begin(), ret.end()), ret.end());
593 : 5290 : return ret;
594 : : }
595 : :
596 : 4995 : Cluster* Cluster::CopyToStaging(TxGraphImpl& graph) const noexcept
597 : : {
598 : : // Construct an empty Cluster.
599 : 4995 : auto ret = std::make_unique<Cluster>(graph.m_next_sequence_counter++);
600 : 4995 : auto ptr = ret.get();
601 : : // Copy depgraph, mapping, and linearization/
602 : 4995 : ptr->m_depgraph = m_depgraph;
603 : 4995 : ptr->m_mapping = m_mapping;
604 : 4995 : ptr->m_linearization = m_linearization;
605 : : // Insert the new Cluster into the graph.
606 : 4995 : graph.InsertCluster(1, std::move(ret), m_quality);
607 : : // Update its Locators.
608 : 4995 : ptr->Updated(graph);
609 : 9990 : return ptr;
610 : 4995 : }
611 : :
612 : 15686 : void Cluster::ApplyRemovals(TxGraphImpl& graph, std::span<GraphIndex>& to_remove) noexcept
613 : : {
614 : : // Iterate over the prefix of to_remove that applies to this cluster.
615 : 15686 : Assume(!to_remove.empty());
616 : 15686 : SetType todo;
617 : 27976 : do {
618 : 27976 : GraphIndex idx = to_remove.front();
619 : 27976 : Assume(idx < graph.m_entries.size());
620 [ + + ]: 27976 : auto& entry = graph.m_entries[idx];
621 : 27976 : auto& locator = entry.m_locator[m_level];
622 : : // Stop once we hit an entry that applies to another Cluster.
623 [ + + ]: 27976 : if (locator.cluster != this) break;
624 : : // - Remember it in a set of to-remove DepGraphIndexes.
625 : 18961 : todo.Set(locator.index);
626 : : // - Remove from m_mapping. This isn't strictly necessary as unused positions in m_mapping
627 : : // are just never accessed, but set it to -1 here to increase the ability to detect a bug
628 : : // that causes it to be accessed regardless.
629 [ + + ]: 18961 : m_mapping[locator.index] = GraphIndex(-1);
630 : : // - Remove its linearization index from the Entry (if in main).
631 [ + + ]: 18961 : if (m_level == 0) {
632 : 15319 : entry.m_main_lin_index = LinearizationIndex(-1);
633 : : }
634 : : // - Mark it as missing/removed in the Entry's locator.
635 : 18961 : graph.ClearLocator(m_level, idx);
636 [ + + ]: 18961 : to_remove = to_remove.subspan(1);
637 [ + + ]: 18961 : } while(!to_remove.empty());
638 : :
639 : 15686 : auto quality = m_quality;
640 : 15686 : Assume(todo.Any());
641 : : // Wipe from the Cluster's DepGraph (this is O(n) regardless of the number of entries
642 : : // removed, so we benefit from batching all the removals).
643 : 15686 : m_depgraph.RemoveTransactions(todo);
644 : 15686 : m_mapping.resize(m_depgraph.PositionRange());
645 : :
646 : : // First remove all removals at the end of the linearization.
647 [ + + + + ]: 48460 : while (!m_linearization.empty() && todo[m_linearization.back()]) {
648 : 17088 : todo.Reset(m_linearization.back());
649 : 17088 : m_linearization.pop_back();
650 : : }
651 [ + + ]: 15686 : if (todo.None()) {
652 : : // If no further removals remain, and thus all removals were at the end, we may be able
653 : : // to leave the cluster at a better quality level.
654 [ + + ]: 14679 : if (IsAcceptable(/*after_split=*/true)) {
655 : : quality = QualityLevel::NEEDS_SPLIT_ACCEPTABLE;
656 : : } else {
657 : : quality = QualityLevel::NEEDS_SPLIT;
658 : : }
659 : : } else {
660 : : // If more removals remain, filter those out of m_linearization.
661 : 1017 : m_linearization.erase(std::remove_if(
662 : : m_linearization.begin(),
663 : : m_linearization.end(),
664 : 15391 : [&](auto pos) { return todo[pos]; }), m_linearization.end());
665 : 1017 : quality = QualityLevel::NEEDS_SPLIT;
666 : : }
667 : 15686 : graph.SetClusterQuality(m_level, m_quality, m_setindex, quality);
668 : 15686 : Updated(graph);
669 : 15686 : }
670 : :
671 : 2575 : void Cluster::Clear(TxGraphImpl& graph) noexcept
672 : : {
673 [ + + ]: 13508 : for (auto i : m_linearization) {
674 : 10933 : graph.ClearLocator(m_level, m_mapping[i]);
675 : : }
676 : 2575 : m_depgraph = {};
677 [ + - ]: 2575 : m_linearization.clear();
678 [ + - ]: 2575 : m_mapping.clear();
679 : 2575 : }
680 : :
681 : 14114 : void Cluster::MoveToMain(TxGraphImpl& graph) noexcept
682 : : {
683 : 14114 : Assume(m_level == 1);
684 [ + + ]: 37170 : for (auto i : m_linearization) {
685 : 23056 : GraphIndex idx = m_mapping[i];
686 : 23056 : auto& entry = graph.m_entries[idx];
687 : 23056 : entry.m_locator[1].SetMissing();
688 : : }
689 : 14114 : auto quality = m_quality;
690 : 14114 : auto cluster = graph.ExtractCluster(1, quality, m_setindex);
691 : 14114 : graph.InsertCluster(0, std::move(cluster), quality);
692 : 14114 : Updated(graph);
693 : 14114 : }
694 : :
695 : 15479 : bool Cluster::Split(TxGraphImpl& graph) noexcept
696 : : {
697 : : // This function can only be called when the Cluster needs splitting.
698 : 15479 : Assume(NeedsSplitting());
699 : : // Determine the new quality the split-off Clusters will have.
700 [ + - ]: 15479 : QualityLevel new_quality = IsAcceptable(/*after_split=*/true) ? QualityLevel::ACCEPTABLE
701 : : : QualityLevel::NEEDS_RELINEARIZE;
702 : : // If we're going to produce ACCEPTABLE clusters (i.e., when in NEEDS_SPLIT_ACCEPTABLE), we
703 : : // need to post-linearize to make sure the split-out versions are all connected (as
704 : : // connectivity may have changed by removing part of the cluster). This could be done on each
705 : : // resulting split-out cluster separately, but it is simpler to do it once up front before
706 : : // splitting. This step is not necessary if the resulting clusters are NEEDS_RELINEARIZE, as
707 : : // they will be post-linearized anyway in MakeAcceptable().
708 : : if (new_quality == QualityLevel::ACCEPTABLE) {
709 : 13678 : PostLinearize(m_depgraph, m_linearization);
710 : : }
711 : : /** Which positions are still left in this Cluster. */
712 : 15479 : auto todo = m_depgraph.Positions();
713 : : /** Mapping from transaction positions in this Cluster to the Cluster where it ends up, and
714 : : * its position therein. */
715 : 15479 : std::vector<std::pair<Cluster*, DepGraphIndex>> remap(m_depgraph.PositionRange());
716 : 15479 : std::vector<Cluster*> new_clusters;
717 : 15479 : bool first{true};
718 : : // Iterate over the connected components of this Cluster's m_depgraph.
719 [ + + ]: 17487 : while (todo.Any()) {
720 : 2834 : auto component = m_depgraph.FindConnectedComponent(todo);
721 [ + + ]: 2834 : if (first && component == todo) {
722 : : // The existing Cluster is an entire component. Leave it be, but update its quality.
723 [ - + ]: 826 : Assume(todo == m_depgraph.Positions());
724 : 826 : graph.SetClusterQuality(m_level, m_quality, m_setindex, new_quality);
725 : : // If this made the quality ACCEPTABLE or OPTIMAL, we need to compute and cache its
726 : : // chunking.
727 : 826 : Updated(graph);
728 : 826 : return false;
729 : : }
730 : 2008 : first = false;
731 : : // Construct a new Cluster to hold the found component.
732 : 2008 : auto new_cluster = std::make_unique<Cluster>(graph.m_next_sequence_counter++);
733 : 2008 : new_clusters.push_back(new_cluster.get());
734 : : // Remember that all the component's transactions go to this new Cluster. The positions
735 : : // will be determined below, so use -1 for now.
736 [ + - + + ]: 8095 : for (auto i : component) {
737 : 4079 : remap[i] = {new_cluster.get(), DepGraphIndex(-1)};
738 : : }
739 : 2008 : graph.InsertCluster(m_level, std::move(new_cluster), new_quality);
740 : 2008 : todo -= component;
741 : 2008 : }
742 : : // Redistribute the transactions.
743 [ + + ]: 18732 : for (auto i : m_linearization) {
744 : : /** The cluster which transaction originally in position i is moved to. */
745 : 4079 : Cluster* new_cluster = remap[i].first;
746 : : // Copy the transaction to the new cluster's depgraph, and remember the position.
747 : 4079 : remap[i].second = new_cluster->m_depgraph.AddTransaction(m_depgraph.FeeRate(i));
748 : : // Create new mapping entry.
749 : 4079 : new_cluster->m_mapping.push_back(m_mapping[i]);
750 : : // Create a new linearization entry. As we're only appending transactions, they equal the
751 : : // DepGraphIndex.
752 : 4079 : new_cluster->m_linearization.push_back(remap[i].second);
753 : : }
754 : : // Redistribute the dependencies.
755 [ + + ]: 18732 : for (auto i : m_linearization) {
756 : : /** The cluster transaction in position i is moved to. */
757 : 4079 : Cluster* new_cluster = remap[i].first;
758 : : // Copy its parents, translating positions.
759 : 4079 : SetType new_parents;
760 [ + + + + ]: 8077 : for (auto par : m_depgraph.GetReducedParents(i)) new_parents.Set(remap[par].second);
761 : 4079 : new_cluster->m_depgraph.AddDependencies(new_parents, remap[i].second);
762 : : }
763 : : // Update all the Locators of moved transactions.
764 [ + + ]: 16661 : for (Cluster* new_cluster : new_clusters) {
765 : 2008 : new_cluster->Updated(graph);
766 : : }
767 : : // Wipe this Cluster, and return that it needs to be deleted.
768 : 14653 : m_depgraph = DepGraph<SetType>{};
769 [ + + ]: 14653 : m_mapping.clear();
770 [ + + ]: 15856 : m_linearization.clear();
771 : : return true;
772 : 15479 : }
773 : :
774 : 15267 : void Cluster::Merge(TxGraphImpl& graph, Cluster& other) noexcept
775 : : {
776 : : /** Vector to store the positions in this Cluster for each position in other. */
777 : 15267 : std::vector<DepGraphIndex> remap(other.m_depgraph.PositionRange());
778 : : // Iterate over all transactions in the other Cluster (the one being absorbed).
779 [ + + ]: 31374 : for (auto pos : other.m_linearization) {
780 : 16107 : auto idx = other.m_mapping[pos];
781 : : // Copy the transaction into this Cluster, and remember its position.
782 : 16107 : auto new_pos = m_depgraph.AddTransaction(other.m_depgraph.FeeRate(pos));
783 [ + + ]: 16107 : remap[pos] = new_pos;
784 [ + + ]: 16107 : if (new_pos == m_mapping.size()) {
785 : 15749 : m_mapping.push_back(idx);
786 : : } else {
787 : 358 : m_mapping[new_pos] = idx;
788 : : }
789 : 16107 : m_linearization.push_back(new_pos);
790 : : // Copy the transaction's dependencies, translating them using remap. Note that since
791 : : // pos iterates over other.m_linearization, which is in topological order, all parents
792 : : // of pos should already be in remap.
793 : 16107 : SetType parents;
794 [ + + + + ]: 17732 : for (auto par : other.m_depgraph.GetReducedParents(pos)) {
795 : 840 : parents.Set(remap[par]);
796 : : }
797 : 16107 : m_depgraph.AddDependencies(parents, remap[pos]);
798 : : // Update the transaction's Locator. There is no need to call Updated() to update chunk
799 : : // feerates, as Updated() will be invoked by Cluster::ApplyDependencies on the resulting
800 : : // merged Cluster later anyway).
801 : 16107 : graph.m_entries[idx].m_locator[m_level].SetPresent(this, new_pos);
802 : : }
803 : : // Purge the other Cluster, now that everything has been moved.
804 : 15267 : other.m_depgraph = DepGraph<SetType>{};
805 [ + - ]: 15267 : other.m_linearization.clear();
806 [ + - ]: 30534 : other.m_mapping.clear();
807 : 15267 : }
808 : :
809 : 9458 : void Cluster::ApplyDependencies(TxGraphImpl& graph, std::span<std::pair<GraphIndex, GraphIndex>> to_apply) noexcept
810 : : {
811 : : // This function is invoked by TxGraphImpl::ApplyDependencies after merging groups of Clusters
812 : : // between which dependencies are added, which simply concatenates their linearizations. Invoke
813 : : // PostLinearize, which has the effect that the linearization becomes a merge-sort of the
814 : : // constituent linearizations. Do this here rather than in Cluster::Merge, because this
815 : : // function is only invoked once per merged Cluster, rather than once per constituent one.
816 : : // This concatenation + post-linearization could be replaced with an explicit merge-sort.
817 : 9458 : PostLinearize(m_depgraph, m_linearization);
818 : :
819 : : // Sort the list of dependencies to apply by child, so those can be applied in batch.
820 [ - - - - : 37531 : std::sort(to_apply.begin(), to_apply.end(), [](auto& a, auto& b) { return a.second < b.second; });
+ + + + +
+ + + + +
+ + + + +
+ - - +
+ ]
821 : : // Iterate over groups of to-be-added dependencies with the same child.
822 : 9458 : auto it = to_apply.begin();
823 [ + + ]: 28824 : while (it != to_apply.end()) {
824 : 19366 : auto& first_child = graph.m_entries[it->second].m_locator[m_level];
825 : 19366 : const auto child_idx = first_child.index;
826 : : // Iterate over all to-be-added dependencies within that same child, gather the relevant
827 : : // parents.
828 : 19366 : SetType parents;
829 [ + + ]: 40373 : while (it != to_apply.end()) {
830 [ + - ]: 30915 : auto& child = graph.m_entries[it->second].m_locator[m_level];
831 : 30915 : auto& parent = graph.m_entries[it->first].m_locator[m_level];
832 [ + - - + ]: 30915 : Assume(child.cluster == this && parent.cluster == this);
833 [ + + ]: 30915 : if (child.index != child_idx) break;
834 : 21007 : parents.Set(parent.index);
835 : 21007 : ++it;
836 : : }
837 : : // Push all dependencies to the underlying DepGraph. Note that this is O(N) in the size of
838 : : // the cluster, regardless of the number of parents being added, so batching them together
839 : : // has a performance benefit.
840 : 19366 : m_depgraph.AddDependencies(parents, child_idx);
841 : : }
842 : :
843 : : // Finally fix the linearization, as the new dependencies may have invalidated the
844 : : // linearization, and post-linearize it to fix up the worst problems with it.
845 : 9458 : FixLinearization(m_depgraph, m_linearization);
846 : 9458 : PostLinearize(m_depgraph, m_linearization);
847 : :
848 : : // Finally push the changes to graph.m_entries.
849 : 9458 : Updated(graph);
850 : 9458 : }
851 : :
852 : 4516 : TxGraphImpl::~TxGraphImpl() noexcept
853 : : {
854 : : // If Refs outlive the TxGraphImpl they refer to, unlink them, so that their destructor does not
855 : : // try to reach into a non-existing TxGraphImpl anymore.
856 [ + + ]: 69873 : for (auto& entry : m_entries) {
857 [ + + ]: 67615 : if (entry.m_ref != nullptr) {
858 : 61090 : GetRefGraph(*entry.m_ref) = nullptr;
859 : : }
860 : : }
861 : 4516 : }
862 : :
863 : 72363 : std::unique_ptr<Cluster> TxGraphImpl::ExtractCluster(int level, QualityLevel quality, ClusterSetIndex setindex) noexcept
864 : : {
865 : 72363 : Assume(quality != QualityLevel::NONE);
866 : :
867 : 72363 : auto& clusterset = GetClusterSet(level);
868 : 72363 : auto& quality_clusters = clusterset.m_clusters[int(quality)];
869 : 72363 : Assume(setindex < quality_clusters.size());
870 : :
871 : : // Extract the Cluster-owning unique_ptr.
872 [ + + ]: 72363 : std::unique_ptr<Cluster> ret = std::move(quality_clusters[setindex]);
873 [ + + ]: 72363 : ret->m_quality = QualityLevel::NONE;
874 : 72363 : ret->m_setindex = ClusterSetIndex(-1);
875 : 72363 : ret->m_level = -1;
876 : :
877 : : // Clean up space in quality_cluster.
878 [ + + ]: 72363 : auto max_setindex = quality_clusters.size() - 1;
879 [ + + ]: 72363 : if (setindex != max_setindex) {
880 : : // If the cluster was not the last element of quality_clusters, move that to take its place.
881 : 32126 : quality_clusters.back()->m_setindex = setindex;
882 : 32126 : quality_clusters.back()->m_level = level;
883 : 32126 : quality_clusters[setindex] = std::move(quality_clusters.back());
884 : : }
885 : : // The last element of quality_clusters is now unused; drop it.
886 : 72363 : quality_clusters.pop_back();
887 : :
888 : 72363 : return ret;
889 : : }
890 : :
891 : 129367 : ClusterSetIndex TxGraphImpl::InsertCluster(int level, std::unique_ptr<Cluster>&& cluster, QualityLevel quality) noexcept
892 : : {
893 : : // Cannot insert with quality level NONE (as that would mean not inserted).
894 : 129367 : Assume(quality != QualityLevel::NONE);
895 : : // The passed-in Cluster must not currently be in the TxGraphImpl.
896 : 129367 : Assume(cluster->m_quality == QualityLevel::NONE);
897 : :
898 : : // Append it at the end of the relevant TxGraphImpl::m_cluster.
899 : 129367 : auto& clusterset = GetClusterSet(level);
900 : 129367 : auto& quality_clusters = clusterset.m_clusters[int(quality)];
901 : 129367 : ClusterSetIndex ret = quality_clusters.size();
902 : 129367 : cluster->m_quality = quality;
903 : 129367 : cluster->m_setindex = ret;
904 : 129367 : cluster->m_level = level;
905 : 129367 : quality_clusters.push_back(std::move(cluster));
906 : 129367 : return ret;
907 : : }
908 : :
909 : 26756 : void TxGraphImpl::SetClusterQuality(int level, QualityLevel old_quality, ClusterSetIndex old_index, QualityLevel new_quality) noexcept
910 : : {
911 : 26756 : Assume(new_quality != QualityLevel::NONE);
912 : :
913 : : // Don't do anything if the quality did not change.
914 [ + + ]: 26756 : if (old_quality == new_quality) return;
915 : : // Extract the cluster from where it currently resides.
916 : 25754 : auto cluster_ptr = ExtractCluster(level, old_quality, old_index);
917 : : // And re-insert it where it belongs.
918 : 25754 : InsertCluster(level, std::move(cluster_ptr), new_quality);
919 : 25754 : }
920 : :
921 : 32495 : void TxGraphImpl::DeleteCluster(Cluster& cluster) noexcept
922 : : {
923 : : // Extract the cluster from where it currently resides.
924 : 32495 : auto cluster_ptr = ExtractCluster(cluster.m_level, cluster.m_quality, cluster.m_setindex);
925 : : // And throw it away.
926 [ + - ]: 32495 : cluster_ptr.reset();
927 : 32495 : }
928 : :
929 : 1256324 : Cluster* TxGraphImpl::FindCluster(GraphIndex idx, int level) const noexcept
930 : : {
931 [ + - - + ]: 1256324 : Assume(level >= 0 && level <= GetTopLevel());
932 : 1256324 : auto& entry = m_entries[idx];
933 : : // Search the entry's locators from top to bottom.
934 [ + + ]: 1373856 : for (int l = level; l >= 0; --l) {
935 : : // If the locator is missing, dig deeper; it may exist at a lower level and therefore be
936 : : // implicitly existing at this level too.
937 [ + + ]: 1472006 : if (entry.m_locator[l].IsMissing()) continue;
938 : : // If the locator has the entry marked as explicitly removed, stop.
939 [ + + ]: 1236942 : if (entry.m_locator[l].IsRemoved()) break;
940 : : // Otherwise, we have found the topmost ClusterSet that contains this entry.
941 : : return entry.m_locator[l].cluster;
942 : : }
943 : : // If no non-empty locator was found, or an explicitly removed was hit, return nothing.
944 : : return nullptr;
945 : : }
946 : :
947 : 8391 : Cluster* TxGraphImpl::PullIn(Cluster* cluster) noexcept
948 : : {
949 : 8391 : int to_level = GetTopLevel();
950 : 8391 : Assume(to_level == 1);
951 : 8391 : int level = cluster->m_level;
952 : 8391 : Assume(level <= to_level);
953 : : // Copy the Cluster from main to staging, if it's not already there.
954 [ + + ]: 8391 : if (level == 0) {
955 : : // Make the Cluster Acceptable before copying. This isn't strictly necessary, but doing it
956 : : // now avoids doing double work later.
957 : 4995 : MakeAcceptable(*cluster);
958 : 4995 : cluster = cluster->CopyToStaging(*this);
959 : : }
960 : 8391 : return cluster;
961 : : }
962 : :
963 : 162788 : void TxGraphImpl::ApplyRemovals(int up_to_level) noexcept
964 : : {
965 [ + - - + ]: 162788 : Assume(up_to_level >= 0 && up_to_level <= GetTopLevel());
966 [ + + ]: 341413 : for (int level = 0; level <= up_to_level; ++level) {
967 : 178625 : auto& clusterset = GetClusterSet(level);
968 : 178625 : auto& to_remove = clusterset.m_to_remove;
969 : : // Skip if there is nothing to remove in this level.
970 [ + + ]: 178625 : if (to_remove.empty()) continue;
971 : : // Pull in all Clusters that are not in staging.
972 [ + + ]: 7202 : if (level == 1) {
973 [ + + ]: 7236 : for (GraphIndex index : to_remove) {
974 : 5964 : auto cluster = FindCluster(index, level);
975 [ + + ]: 5964 : if (cluster != nullptr) PullIn(cluster);
976 : : }
977 : : }
978 : : // Group the set of to-be-removed entries by Cluster::m_sequence.
979 : 7202 : std::sort(to_remove.begin(), to_remove.end(), [&](GraphIndex a, GraphIndex b) noexcept {
980 : 69406 : Cluster* cluster_a = m_entries[a].m_locator[level].cluster;
981 : 69406 : Cluster* cluster_b = m_entries[b].m_locator[level].cluster;
982 : 69406 : return CompareClusters(cluster_a, cluster_b) < 0;
983 : : });
984 : : // Process per Cluster.
985 : 7202 : std::span to_remove_span{to_remove};
986 [ + + ]: 28299 : while (!to_remove_span.empty()) {
987 [ + + ]: 21097 : Cluster* cluster = m_entries[to_remove_span.front()].m_locator[level].cluster;
988 [ + + ]: 21097 : if (cluster != nullptr) {
989 : : // If the first to_remove_span entry's Cluster exists, hand to_remove_span to it, so it
990 : : // can pop off whatever applies to it.
991 : 15686 : cluster->ApplyRemovals(*this, to_remove_span);
992 : : } else {
993 : : // Otherwise, skip this already-removed entry. This may happen when
994 : : // RemoveTransaction was called twice on the same Ref, for example.
995 : 5411 : to_remove_span = to_remove_span.subspan(1);
996 : : }
997 : : }
998 [ + - ]: 185827 : to_remove.clear();
999 : : }
1000 : 162788 : Compact();
1001 : 162788 : }
1002 : :
1003 : 11609 : void TxGraphImpl::SwapIndexes(GraphIndex a, GraphIndex b) noexcept
1004 : : {
1005 : 11609 : Assume(a < m_entries.size());
1006 : 11609 : Assume(b < m_entries.size());
1007 : : // Swap the Entry objects.
1008 : 11609 : std::swap(m_entries[a], m_entries[b]);
1009 : : // Iterate over both objects.
1010 [ + + ]: 34827 : for (int i = 0; i < 2; ++i) {
1011 [ + + ]: 23218 : GraphIndex idx = i ? b : a;
1012 [ + + ]: 23218 : Entry& entry = m_entries[idx];
1013 : : // Update linked Ref, if any exists.
1014 [ + + ]: 23218 : if (entry.m_ref) GetRefIndex(*entry.m_ref) = idx;
1015 : : // Update the locators for both levels. The rest of the Entry information will not change,
1016 : : // so no need to invoke Cluster::Updated().
1017 [ + + ]: 69654 : for (int level = 0; level < MAX_LEVELS; ++level) {
1018 : 46436 : Locator& locator = entry.m_locator[level];
1019 [ + + ]: 46436 : if (locator.IsPresent()) {
1020 : 10134 : locator.cluster->UpdateMapping(locator.index, idx);
1021 : : }
1022 : : }
1023 : : }
1024 : 11609 : }
1025 : :
1026 : 202738 : void TxGraphImpl::Compact() noexcept
1027 : : {
1028 : : // We cannot compact while any to-be-applied operations or staged removals remain as we'd need
1029 : : // to rewrite them. It is easier to delay the compaction until they have been applied.
1030 [ + + ]: 202738 : if (!m_main_clusterset.m_deps_to_add.empty()) return;
1031 [ + + ]: 142769 : if (!m_main_clusterset.m_to_remove.empty()) return;
1032 : 141523 : Assume(m_main_clusterset.m_removed.empty()); // non-staging m_removed is always empty
1033 [ + + ]: 141523 : if (m_staging_clusterset.has_value()) {
1034 [ + + ]: 59485 : if (!m_staging_clusterset->m_deps_to_add.empty()) return;
1035 [ + + ]: 45738 : if (!m_staging_clusterset->m_to_remove.empty()) return;
1036 [ + + ]: 44552 : if (!m_staging_clusterset->m_removed.empty()) return;
1037 : : }
1038 : :
1039 : : // Sort the GraphIndexes that need to be cleaned up. They are sorted in reverse, so the last
1040 : : // ones get processed first. This means earlier-processed GraphIndexes will not cause moving of
1041 : : // later-processed ones during the "swap with end of m_entries" step below (which might
1042 : : // invalidate them).
1043 : 105164 : std::sort(m_unlinked.begin(), m_unlinked.end(), std::greater{});
1044 : :
1045 : 105164 : auto last = GraphIndex(-1);
1046 [ + + ]: 120045 : for (GraphIndex idx : m_unlinked) {
1047 : : // m_unlinked should never contain the same GraphIndex twice (the code below would fail
1048 : : // if so, because GraphIndexes get invalidated by removing them).
1049 : 14881 : Assume(idx != last);
1050 : 14881 : last = idx;
1051 : :
1052 : : // Make sure the entry is unlinked.
1053 : 14881 : Entry& entry = m_entries[idx];
1054 : 14881 : Assume(entry.m_ref == nullptr);
1055 : : // Make sure the entry does not occur in the graph.
1056 [ + + ]: 44643 : for (int level = 0; level < MAX_LEVELS; ++level) {
1057 : 29762 : Assume(!entry.m_locator[level].IsPresent());
1058 : : }
1059 : :
1060 : : // Move the entry to the end.
1061 [ + + ]: 14881 : if (idx != m_entries.size() - 1) SwapIndexes(idx, m_entries.size() - 1);
1062 : : // Drop the entry for idx, now that it is at the end.
1063 : 14881 : m_entries.pop_back();
1064 : : }
1065 [ + + ]: 105164 : m_unlinked.clear();
1066 : : }
1067 : :
1068 : 15479 : void TxGraphImpl::Split(Cluster& cluster) noexcept
1069 : : {
1070 : : // To split a Cluster, first make sure all removals are applied (as we might need to split
1071 : : // again afterwards otherwise).
1072 : 15479 : ApplyRemovals(cluster.m_level);
1073 : 15479 : bool del = cluster.Split(*this);
1074 [ + + ]: 15479 : if (del) {
1075 : : // Cluster::Split reports whether the Cluster is to be deleted.
1076 : 14653 : DeleteCluster(cluster);
1077 : : }
1078 : 15479 : }
1079 : :
1080 : 22953 : void TxGraphImpl::SplitAll(int up_to_level) noexcept
1081 : : {
1082 [ + - - + ]: 22953 : Assume(up_to_level >= 0 && up_to_level <= GetTopLevel());
1083 : : // Before splitting all Cluster, first make sure all removals are applied.
1084 : 22953 : ApplyRemovals(up_to_level);
1085 [ + + ]: 48045 : for (int level = 0; level <= up_to_level; ++level) {
1086 [ + + ]: 75276 : for (auto quality : {QualityLevel::NEEDS_SPLIT, QualityLevel::NEEDS_SPLIT_ACCEPTABLE}) {
1087 : 50184 : auto& queue = GetClusterSet(level).m_clusters[int(quality)];
1088 [ + + ]: 65663 : while (!queue.empty()) {
1089 : 15479 : Split(*queue.back().get());
1090 : : }
1091 : : }
1092 : : }
1093 : 22953 : }
1094 : :
1095 : 1304663 : void TxGraphImpl::GroupClusters(int level) noexcept
1096 : : {
1097 : 1304663 : auto& clusterset = GetClusterSet(level);
1098 : : // If the groupings have been computed already, nothing is left to be done.
1099 [ + + ]: 1304663 : if (clusterset.m_group_data.has_value()) return;
1100 : :
1101 : : // Before computing which Clusters need to be merged together, first apply all removals and
1102 : : // split the Clusters into connected components. If we would group first, we might end up
1103 : : // with inefficient and/or oversized Clusters which just end up being split again anyway.
1104 : 15842 : SplitAll(level);
1105 : :
1106 : : /** Annotated clusters: an entry for each Cluster, together with the sequence number for the
1107 : : * representative for the partition it is in (initially its own, later that of the
1108 : : * to-be-merged group). */
1109 : 15842 : std::vector<std::pair<Cluster*, uint64_t>> an_clusters;
1110 : : /** Annotated dependencies: an entry for each m_deps_to_add entry (excluding ones that apply
1111 : : * to removed transactions), together with the sequence number of the representative root of
1112 : : * Clusters it applies to (initially that of the child Cluster, later that of the
1113 : : * to-be-merged group). */
1114 : 15842 : std::vector<std::pair<std::pair<GraphIndex, GraphIndex>, uint64_t>> an_deps;
1115 : :
1116 : : // Construct a an_clusters entry for every parent and child in the to-be-applied dependencies,
1117 : : // and an an_deps entry for each dependency to be applied.
1118 : 15842 : an_deps.reserve(clusterset.m_deps_to_add.size());
1119 [ + + ]: 75169 : for (const auto& [par, chl] : clusterset.m_deps_to_add) {
1120 : 59327 : auto par_cluster = FindCluster(par, level);
1121 : 59327 : auto chl_cluster = FindCluster(chl, level);
1122 : : // Skip dependencies for which the parent or child transaction is removed.
1123 [ + + + + ]: 59327 : if (par_cluster == nullptr || chl_cluster == nullptr) continue;
1124 : 53339 : an_clusters.emplace_back(par_cluster, par_cluster->m_sequence);
1125 : : // Do not include a duplicate when parent and child are identical, as it'll be removed
1126 : : // below anyway.
1127 [ + + ]: 53339 : if (chl_cluster != par_cluster) an_clusters.emplace_back(chl_cluster, chl_cluster->m_sequence);
1128 : : // Add entry to an_deps, using the child sequence number.
1129 : 53339 : an_deps.emplace_back(std::pair{par, chl}, chl_cluster->m_sequence);
1130 : : }
1131 : : // Sort and deduplicate an_clusters, so we end up with a sorted list of all involved Clusters
1132 : : // to which dependencies apply.
1133 [ - - - - : 390681 : std::sort(an_clusters.begin(), an_clusters.end(), [](auto& a, auto& b) noexcept { return a.second < b.second; });
+ + + + +
+ + + + +
+ + + + +
+ - - +
+ ]
1134 : 15842 : an_clusters.erase(std::unique(an_clusters.begin(), an_clusters.end()), an_clusters.end());
1135 : : // Sort an_deps by applying the same order to the involved child cluster.
1136 [ - - - - : 162263 : std::sort(an_deps.begin(), an_deps.end(), [&](auto& a, auto& b) noexcept { return a.second < b.second; });
+ + + + +
+ + + + +
+ + + + +
+ - - +
+ ]
1137 : :
1138 : : // Run the union-find algorithm to to find partitions of the input Clusters which need to be
1139 : : // grouped together. See https://en.wikipedia.org/wiki/Disjoint-set_data_structure.
1140 : 15842 : {
1141 : : /** Each PartitionData entry contains information about a single input Cluster. */
1142 : 15842 : struct PartitionData
1143 : : {
1144 : : /** The sequence number of the cluster this holds information for. */
1145 : : uint64_t sequence;
1146 : : /** All PartitionData entries belonging to the same partition are organized in a tree.
1147 : : * Each element points to its parent, or to itself if it is the root. The root is then
1148 : : * a representative for the entire tree, and can be found by walking upwards from any
1149 : : * element. */
1150 : : PartitionData* parent;
1151 : : /** (only if this is a root, so when parent == this) An upper bound on the height of
1152 : : * tree for this partition. */
1153 : : unsigned rank;
1154 : : };
1155 : : /** Information about each input Cluster. Sorted by Cluster::m_sequence. */
1156 : 15842 : std::vector<PartitionData> partition_data;
1157 : :
1158 : : /** Given a Cluster, find its corresponding PartitionData. */
1159 : 101517 : auto locate_fn = [&](uint64_t sequence) noexcept -> PartitionData* {
1160 : 85675 : auto it = std::lower_bound(partition_data.begin(), partition_data.end(), sequence,
1161 [ + + ]: 293934 : [](auto& a, uint64_t seq) noexcept { return a.sequence < seq; });
1162 : 85675 : Assume(it != partition_data.end());
1163 : 85675 : Assume(it->sequence == sequence);
1164 : 85675 : return &*it;
1165 : 15842 : };
1166 : :
1167 : : /** Given a PartitionData, find the root of the tree it is in (its representative). */
1168 : 121352 : static constexpr auto find_root_fn = [](PartitionData* data) noexcept -> PartitionData* {
1169 [ + + + + ]: 161983 : while (data->parent != data) {
1170 : : // Replace pointers to parents with pointers to grandparents.
1171 : : // See https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Finding_set_representatives.
1172 : 57700 : auto par = data->parent;
1173 : 57700 : data->parent = par->parent;
1174 : 57700 : data = par;
1175 : : }
1176 : 105510 : return data;
1177 : : };
1178 : :
1179 : : /** Given two PartitionDatas, union the partitions they are in, and return their
1180 : : * representative. */
1181 : 63920 : static constexpr auto union_fn = [](PartitionData* arg1, PartitionData* arg2) noexcept {
1182 : : // Find the roots of the trees, and bail out if they are already equal (which would
1183 : : // mean they are in the same partition already).
1184 [ + + ]: 97383 : auto rep1 = find_root_fn(arg1);
1185 : 48078 : auto rep2 = find_root_fn(arg2);
1186 [ + + ]: 48078 : if (rep1 == rep2) return rep1;
1187 : : // Pick the lower-rank root to become a child of the higher-rank one.
1188 : : // See https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Union_by_rank.
1189 [ + + ]: 40693 : if (rep1->rank < rep2->rank) std::swap(rep1, rep2);
1190 : 40693 : rep2->parent = rep1;
1191 : 40693 : rep1->rank += (rep1->rank == rep2->rank);
1192 : 40693 : return rep1;
1193 : : };
1194 : :
1195 : : // Start by initializing every Cluster as its own singleton partition.
1196 : 15842 : partition_data.resize(an_clusters.size());
1197 [ + + ]: 73274 : for (size_t i = 0; i < an_clusters.size(); ++i) {
1198 : 57432 : partition_data[i].sequence = an_clusters[i].first->m_sequence;
1199 : 57432 : partition_data[i].parent = &partition_data[i];
1200 : 57432 : partition_data[i].rank = 0;
1201 : : }
1202 : :
1203 : : // Run through all parent/child pairs in an_deps, and union the partitions their Clusters
1204 : : // are in.
1205 : 15842 : Cluster* last_chl_cluster{nullptr};
1206 : 15842 : PartitionData* last_partition{nullptr};
1207 [ + + ]: 69181 : for (const auto& [dep, _] : an_deps) {
1208 : 53339 : auto [par, chl] = dep;
1209 : 53339 : auto par_cluster = FindCluster(par, level);
1210 : 53339 : auto chl_cluster = FindCluster(chl, level);
1211 : 53339 : Assume(chl_cluster != nullptr && par_cluster != nullptr);
1212 : : // Nothing to do if parent and child are in the same Cluster.
1213 [ + + ]: 53339 : if (par_cluster == chl_cluster) continue;
1214 : 48078 : Assume(par != chl);
1215 [ + + ]: 48078 : if (chl_cluster == last_chl_cluster) {
1216 : : // If the child Clusters is the same as the previous iteration, union with the
1217 : : // tree they were in, avoiding the need for another lookup. Note that an_deps
1218 : : // is sorted by child Cluster, so batches with the same child are expected.
1219 : 10481 : last_partition = union_fn(locate_fn(par_cluster->m_sequence), last_partition);
1220 : : } else {
1221 : 37597 : last_chl_cluster = chl_cluster;
1222 : 37597 : last_partition = union_fn(locate_fn(par_cluster->m_sequence), locate_fn(chl_cluster->m_sequence));
1223 : : }
1224 : : }
1225 : :
1226 : : // Update the sequence numbers in an_clusters and an_deps to be those of the partition
1227 : : // representative.
1228 : 15842 : auto deps_it = an_deps.begin();
1229 [ + + ]: 73274 : for (size_t i = 0; i < partition_data.size(); ++i) {
1230 : 57432 : auto& data = partition_data[i];
1231 : : // Find the sequence of the representative of the partition Cluster i is in, and store
1232 : : // it with the Cluster.
1233 : 57432 : auto rep_seq = find_root_fn(&data)->sequence;
1234 : 57432 : an_clusters[i].second = rep_seq;
1235 : : // Find all dependencies whose child Cluster is Cluster i, and annotate them with rep.
1236 [ + + ]: 110771 : while (deps_it != an_deps.end()) {
1237 : 94577 : auto [par, chl] = deps_it->first;
1238 : 94577 : auto chl_cluster = FindCluster(chl, level);
1239 : 94577 : Assume(chl_cluster != nullptr);
1240 [ + + ]: 94577 : if (chl_cluster->m_sequence > data.sequence) break;
1241 : 53339 : deps_it->second = rep_seq;
1242 : 53339 : ++deps_it;
1243 : : }
1244 : : }
1245 : 15842 : }
1246 : :
1247 : : // Sort both an_clusters and an_deps by sequence number of the representative of the
1248 : : // partition they are in, grouping all those applying to the same partition together.
1249 [ - - - - : 121304 : std::sort(an_deps.begin(), an_deps.end(), [](auto& a, auto& b) noexcept { return a.second < b.second; });
+ + + + +
+ + + + +
+ + + + +
+ - - +
+ ]
1250 [ - - - - : 134764 : std::sort(an_clusters.begin(), an_clusters.end(), [](auto& a, auto& b) noexcept { return a.second < b.second; });
+ + + + +
+ + + + +
+ + + + +
+ - - +
+ ]
1251 : :
1252 : : // Translate the resulting cluster groups to the m_group_data structure, and the dependencies
1253 : : // back to m_deps_to_add.
1254 : 15842 : clusterset.m_group_data = GroupData{};
1255 : 15842 : clusterset.m_group_data->m_group_clusters.reserve(an_clusters.size());
1256 [ + + ]: 15842 : clusterset.m_group_data->m_group_oversized = false;
1257 [ + + ]: 15842 : clusterset.m_deps_to_add.clear();
1258 : 15842 : clusterset.m_deps_to_add.reserve(an_deps.size());
1259 : 15842 : auto an_deps_it = an_deps.begin();
1260 : 15842 : auto an_clusters_it = an_clusters.begin();
1261 [ + + ]: 48423 : while (an_clusters_it != an_clusters.end()) {
1262 : : // Process all clusters/dependencies belonging to the partition with representative rep.
1263 : 16739 : auto rep = an_clusters_it->second;
1264 : : // Create and initialize a new GroupData entry for the partition.
1265 : 16739 : auto& new_entry = clusterset.m_group_data->m_groups.emplace_back();
1266 : 16739 : new_entry.m_cluster_offset = clusterset.m_group_data->m_group_clusters.size();
1267 : 16739 : new_entry.m_cluster_count = 0;
1268 : 16739 : new_entry.m_deps_offset = clusterset.m_deps_to_add.size();
1269 : 16739 : new_entry.m_deps_count = 0;
1270 : 16739 : uint32_t total_count{0};
1271 : : // Add all its clusters to it (copying those from an_clusters to m_group_clusters).
1272 [ + + + + ]: 74171 : while (an_clusters_it != an_clusters.end() && an_clusters_it->second == rep) {
1273 : 57432 : clusterset.m_group_data->m_group_clusters.push_back(an_clusters_it->first);
1274 : 57432 : total_count += an_clusters_it->first->GetTxCount();
1275 : 57432 : ++an_clusters_it;
1276 : 57432 : ++new_entry.m_cluster_count;
1277 : : }
1278 : : // Add all its dependencies to it (copying those back from an_deps to m_deps_to_add).
1279 [ + + + + ]: 70078 : while (an_deps_it != an_deps.end() && an_deps_it->second == rep) {
1280 : 53339 : clusterset.m_deps_to_add.push_back(an_deps_it->first);
1281 : 53339 : ++an_deps_it;
1282 : 53339 : ++new_entry.m_deps_count;
1283 : : }
1284 : : // Detect oversizedness.
1285 [ + + ]: 16739 : if (total_count > m_max_cluster_count) {
1286 : 5222 : clusterset.m_group_data->m_group_oversized = true;
1287 : : }
1288 : : }
1289 : 15842 : Assume(an_deps_it == an_deps.end());
1290 : 15842 : Assume(an_clusters_it == an_clusters.end());
1291 : 15842 : clusterset.m_oversized = clusterset.m_group_data->m_group_oversized;
1292 : 15842 : Compact();
1293 : 15842 : }
1294 : :
1295 : 9458 : void TxGraphImpl::Merge(std::span<Cluster*> to_merge) noexcept
1296 : : {
1297 : 9458 : Assume(!to_merge.empty());
1298 : : // Nothing to do if a group consists of just a single Cluster.
1299 [ + + ]: 9458 : if (to_merge.size() == 1) return;
1300 : :
1301 : : // Move the largest Cluster to the front of to_merge. As all transactions in other to-be-merged
1302 : : // Clusters will be moved to that one, putting the largest one first minimizes the number of
1303 : : // moves.
1304 : 8294 : size_t max_size_pos{0};
1305 : 8294 : DepGraphIndex max_size = to_merge[max_size_pos]->GetTxCount();
1306 [ + + ]: 23561 : for (size_t i = 1; i < to_merge.size(); ++i) {
1307 [ + + ]: 15267 : DepGraphIndex size = to_merge[i]->GetTxCount();
1308 [ + + ]: 15267 : if (size > max_size) {
1309 : 2072 : max_size_pos = i;
1310 : 2072 : max_size = size;
1311 : : }
1312 : : }
1313 [ + + ]: 8294 : if (max_size_pos != 0) std::swap(to_merge[0], to_merge[max_size_pos]);
1314 : :
1315 : : // Merge all further Clusters in the group into the first one, and delete them.
1316 [ + + ]: 23561 : for (size_t i = 1; i < to_merge.size(); ++i) {
1317 : 15267 : to_merge[0]->Merge(*this, *to_merge[i]);
1318 : 15267 : DeleteCluster(*to_merge[i]);
1319 : : }
1320 : : }
1321 : :
1322 : 1304029 : void TxGraphImpl::ApplyDependencies(int level) noexcept
1323 : : {
1324 : 1304029 : auto& clusterset = GetClusterSet(level);
1325 : : // Do not bother computing groups if we already know the result will be oversized.
1326 [ + + ]: 1304029 : if (clusterset.m_oversized == true) return;
1327 : : // Compute the groups of to-be-merged Clusters (which also applies all removals, and splits).
1328 : 1301248 : GroupClusters(level);
1329 : 1301248 : Assume(clusterset.m_group_data.has_value());
1330 : : // Nothing to do if there are no dependencies to be added.
1331 [ + + ]: 1301248 : if (clusterset.m_deps_to_add.empty()) return;
1332 : : // Dependencies cannot be applied if it would result in oversized clusters.
1333 [ + + ]: 10180 : if (clusterset.m_group_data->m_group_oversized) return;
1334 : :
1335 : : // For each group of to-be-merged Clusters.
1336 [ + + ]: 18004 : for (const auto& group_entry : clusterset.m_group_data->m_groups) {
1337 [ + + ]: 9458 : auto cluster_span = std::span{clusterset.m_group_data->m_group_clusters}
1338 [ + + ]: 9458 : .subspan(group_entry.m_cluster_offset, group_entry.m_cluster_count);
1339 : : // Pull in all the Clusters that contain dependencies.
1340 [ + + ]: 9458 : if (level == 1) {
1341 [ + + ]: 5585 : for (Cluster*& cluster : cluster_span) {
1342 : 4105 : cluster = PullIn(cluster);
1343 : : }
1344 : : }
1345 : : // Invoke Merge() to merge them into a single Cluster.
1346 : 9458 : Merge(cluster_span);
1347 : : // Actually apply all to-be-added dependencies (all parents and children from this grouping
1348 : : // belong to the same Cluster at this point because of the merging above).
1349 : 9458 : auto deps_span = std::span{clusterset.m_deps_to_add}
1350 : 9458 : .subspan(group_entry.m_deps_offset, group_entry.m_deps_count);
1351 : 9458 : Assume(!deps_span.empty());
1352 : 9458 : const auto& loc = m_entries[deps_span[0].second].m_locator[level];
1353 : 9458 : Assume(loc.IsPresent());
1354 : 9458 : loc.cluster->ApplyDependencies(*this, deps_span);
1355 : : }
1356 : :
1357 : : // Wipe the list of to-be-added dependencies now that they are applied.
1358 [ + - ]: 8546 : clusterset.m_deps_to_add.clear();
1359 : 8546 : Compact();
1360 : : // Also no further Cluster mergings are needed (note that we clear, but don't set to
1361 : : // std::nullopt, as that would imply the groupings are unknown).
1362 : 17092 : clusterset.m_group_data = GroupData{};
1363 : : }
1364 : :
1365 : 4698 : void Cluster::Relinearize(TxGraphImpl& graph, uint64_t max_iters) noexcept
1366 : : {
1367 : : // We can only relinearize Clusters that do not need splitting.
1368 : 4698 : Assume(!NeedsSplitting());
1369 : : // No work is required for Clusters which are already optimally linearized.
1370 [ + - ]: 4698 : if (IsOptimal()) return;
1371 : : // Invoke the actual linearization algorithm (passing in the existing one).
1372 : 4698 : uint64_t rng_seed = graph.m_rng.rand64();
1373 [ - + ]: 4698 : auto [linearization, optimal] = Linearize(m_depgraph, max_iters, rng_seed, m_linearization);
1374 : : // Postlinearize if the result isn't optimal already. This guarantees (among other things)
1375 : : // that the chunks of the resulting linearization are all connected.
1376 [ - + ]: 4698 : if (!optimal) PostLinearize(m_depgraph, linearization);
1377 : : // Update the linearization.
1378 : 4698 : m_linearization = std::move(linearization);
1379 : : // Update the Cluster's quality.
1380 [ - + ]: 4698 : auto new_quality = optimal ? QualityLevel::OPTIMAL : QualityLevel::ACCEPTABLE;
1381 : 4698 : graph.SetClusterQuality(m_level, m_quality, m_setindex, new_quality);
1382 : : // Update the Entry objects.
1383 : 4698 : Updated(graph);
1384 : 4698 : }
1385 : :
1386 : 1607993 : void TxGraphImpl::MakeAcceptable(Cluster& cluster) noexcept
1387 : : {
1388 : : // Relinearize the Cluster if needed.
1389 [ + + ]: 1607993 : if (!cluster.NeedsSplitting() && !cluster.IsAcceptable()) {
1390 : 4698 : cluster.Relinearize(*this, 10000);
1391 : : }
1392 : 1607993 : }
1393 : :
1394 : 9043 : void TxGraphImpl::MakeAllAcceptable(int level) noexcept
1395 : : {
1396 : 9043 : ApplyDependencies(level);
1397 : 9043 : auto& clusterset = GetClusterSet(level);
1398 [ + - ]: 9043 : if (clusterset.m_oversized == true) return;
1399 : 5815 : auto& queue = clusterset.m_clusters[int(QualityLevel::NEEDS_RELINEARIZE)];
1400 [ + + ]: 6906 : while (!queue.empty()) {
1401 : 1091 : MakeAcceptable(*queue.back().get());
1402 : : }
1403 : : }
1404 : :
1405 : 7003 : Cluster::Cluster(uint64_t sequence) noexcept : m_sequence{sequence} {}
1406 : :
1407 : 82496 : Cluster::Cluster(uint64_t sequence, TxGraphImpl& graph, const FeePerWeight& feerate, GraphIndex graph_index) noexcept :
1408 : 82496 : m_sequence{sequence}
1409 : : {
1410 : : // Create a new transaction in the DepGraph, and remember its position in m_mapping.
1411 : 82496 : auto cluster_idx = m_depgraph.AddTransaction(feerate);
1412 : 82496 : m_mapping.push_back(graph_index);
1413 : 82496 : m_linearization.push_back(cluster_idx);
1414 : 82496 : }
1415 : :
1416 : 82496 : TxGraph::Ref TxGraphImpl::AddTransaction(const FeePerWeight& feerate) noexcept
1417 : : {
1418 : : // Construct a new Ref.
1419 : 82496 : Ref ret;
1420 : : // Construct a new Entry, and link it with the Ref.
1421 : 82496 : auto idx = m_entries.size();
1422 : 82496 : m_entries.emplace_back();
1423 : 82496 : auto& entry = m_entries.back();
1424 : 82496 : entry.m_ref = &ret;
1425 : 82496 : GetRefGraph(ret) = this;
1426 : 82496 : GetRefIndex(ret) = idx;
1427 : : // Construct a new singleton Cluster (which is necessarily optimally linearized).
1428 : 82496 : auto cluster = std::make_unique<Cluster>(m_next_sequence_counter++, *this, feerate, idx);
1429 : 82496 : auto cluster_ptr = cluster.get();
1430 : 82496 : int level = GetTopLevel();
1431 : 82496 : auto& clusterset = GetClusterSet(level);
1432 : 82496 : InsertCluster(level, std::move(cluster), QualityLevel::OPTIMAL);
1433 : 82496 : cluster_ptr->Updated(*this);
1434 : 82496 : ++clusterset.m_txcount;
1435 : : // Return the Ref.
1436 : 164992 : return ret;
1437 : 82496 : }
1438 : :
1439 : 12715 : void TxGraphImpl::RemoveTransaction(const Ref& arg) noexcept
1440 : : {
1441 : : // Don't do anything if the Ref is empty (which may be indicative of the transaction already
1442 : : // having been removed).
1443 [ + + ]: 12715 : if (GetRefGraph(arg) == nullptr) return;
1444 : 11878 : Assume(GetRefGraph(arg) == this);
1445 : : // Find the Cluster the transaction is in, and stop if it isn't in any.
1446 : 11878 : int level = GetTopLevel();
1447 : 11878 : auto cluster = FindCluster(GetRefIndex(arg), level);
1448 [ + + ]: 11878 : if (cluster == nullptr) return;
1449 : : // Remember that the transaction is to be removed.
1450 : 10824 : auto& clusterset = GetClusterSet(level);
1451 : 10824 : clusterset.m_to_remove.push_back(GetRefIndex(arg));
1452 : : // Wipe m_group_data (as it will need to be recomputed).
1453 [ + + ]: 10824 : clusterset.m_group_data.reset();
1454 [ + + ]: 11340 : if (clusterset.m_oversized == true) clusterset.m_oversized = std::nullopt;
1455 : : }
1456 : :
1457 : 36138 : void TxGraphImpl::AddDependency(const Ref& parent, const Ref& child) noexcept
1458 : : {
1459 : : // Don't do anything if either Ref is empty (which may be indicative of it having already been
1460 : : // removed).
1461 [ + + + + ]: 36138 : if (GetRefGraph(parent) == nullptr || GetRefGraph(child) == nullptr) return;
1462 [ + - - + ]: 33830 : Assume(GetRefGraph(parent) == this && GetRefGraph(child) == this);
1463 : : // Don't do anything if this is a dependency on self.
1464 [ + + ]: 33830 : if (GetRefIndex(parent) == GetRefIndex(child)) return;
1465 : : // Find the Cluster the parent and child transaction are in, and stop if either appears to be
1466 : : // already removed.
1467 : 32968 : int level = GetTopLevel();
1468 : 32968 : auto par_cluster = FindCluster(GetRefIndex(parent), level);
1469 [ + + ]: 32968 : if (par_cluster == nullptr) return;
1470 : 32114 : auto chl_cluster = FindCluster(GetRefIndex(child), level);
1471 [ + + ]: 32114 : if (chl_cluster == nullptr) return;
1472 : : // Remember that this dependency is to be applied.
1473 : 31203 : auto& clusterset = GetClusterSet(level);
1474 : 31203 : clusterset.m_deps_to_add.emplace_back(GetRefIndex(parent), GetRefIndex(child));
1475 : : // Wipe m_group_data (as it will need to be recomputed).
1476 [ + + ]: 31203 : clusterset.m_group_data.reset();
1477 [ + + ]: 42800 : if (clusterset.m_oversized == false) clusterset.m_oversized = std::nullopt;
1478 : : }
1479 : :
1480 : 13176 : bool TxGraphImpl::Exists(const Ref& arg, bool main_only) noexcept
1481 : : {
1482 [ + + ]: 13176 : if (GetRefGraph(arg) == nullptr) return false;
1483 : 12441 : Assume(GetRefGraph(arg) == this);
1484 [ + + ]: 12441 : size_t level = GetSpecifiedLevel(main_only);
1485 : : // Make sure the transaction isn't scheduled for removal.
1486 : 12441 : ApplyRemovals(level);
1487 : 12441 : auto cluster = FindCluster(GetRefIndex(arg), level);
1488 : 12441 : return cluster != nullptr;
1489 : : }
1490 : :
1491 : 90030 : void Cluster::GetAncestorRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept
1492 : : {
1493 : : /** The union of all ancestors to be returned. */
1494 : 90030 : SetType ancestors_union;
1495 : : // Process elements from the front of args, as long as they apply.
1496 [ + + ]: 185958 : while (!args.empty()) {
1497 [ + + ]: 97218 : if (args.front().first != this) break;
1498 : 95928 : ancestors_union |= m_depgraph.Ancestors(args.front().second);
1499 : 95928 : args = args.subspan(1);
1500 : : }
1501 : 90030 : Assume(ancestors_union.Any());
1502 : : // Translate all ancestors (in arbitrary order) to Refs (if they have any), and return them.
1503 [ + - + + ]: 311212 : for (auto idx : ancestors_union) {
1504 : 131152 : const auto& entry = graph.m_entries[m_mapping[idx]];
1505 : 131152 : Assume(entry.m_ref != nullptr);
1506 : 131152 : output.push_back(entry.m_ref);
1507 : : }
1508 : 90030 : }
1509 : :
1510 : 88352 : void Cluster::GetDescendantRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept
1511 : : {
1512 : : /** The union of all descendants to be returned. */
1513 : 88352 : SetType descendants_union;
1514 : : // Process elements from the front of args, as long as they apply.
1515 [ + + ]: 180058 : while (!args.empty()) {
1516 [ + + ]: 92345 : if (args.front().first != this) break;
1517 : 91706 : descendants_union |= m_depgraph.Descendants(args.front().second);
1518 : 91706 : args = args.subspan(1);
1519 : : }
1520 : 88352 : Assume(descendants_union.Any());
1521 : : // Translate all descendants (in arbitrary order) to Refs (if they have any), and return them.
1522 [ + - + + ]: 305505 : for (auto idx : descendants_union) {
1523 : 128801 : const auto& entry = graph.m_entries[m_mapping[idx]];
1524 : 128801 : Assume(entry.m_ref != nullptr);
1525 : 128801 : output.push_back(entry.m_ref);
1526 : : }
1527 : 88352 : }
1528 : :
1529 : 88426 : std::vector<TxGraph::Ref*> Cluster::GetClusterRefs(const TxGraphImpl& graph) noexcept
1530 : : {
1531 : 88426 : std::vector<TxGraph::Ref*> ret;
1532 : 88426 : ret.reserve(m_linearization.size());
1533 : : // Translate all transactions in the Cluster (in linearization order) to Refs.
1534 [ + + ]: 576815 : for (auto idx : m_linearization) {
1535 : 488389 : const auto& entry = graph.m_entries[m_mapping[idx]];
1536 : 488389 : Assume(entry.m_ref != nullptr);
1537 : 488389 : ret.push_back(entry.m_ref);
1538 : : }
1539 : 88426 : return ret;
1540 : : }
1541 : :
1542 : 89146 : FeePerWeight Cluster::GetIndividualFeerate(DepGraphIndex idx) noexcept
1543 : : {
1544 : 89146 : return FeePerWeight::FromFeeFrac(m_depgraph.FeeRate(idx));
1545 : : }
1546 : :
1547 : 7868 : void Cluster::MakeStagingTransactionsMissing(TxGraphImpl& graph) noexcept
1548 : : {
1549 : 7868 : Assume(m_level == 1);
1550 : : // Mark all transactions of a Cluster missing, needed when aborting staging, so that the
1551 : : // corresponding Locators don't retain references into aborted Clusters.
1552 [ + + ]: 15843 : for (auto ci : m_linearization) {
1553 : 7975 : GraphIndex idx = m_mapping[ci];
1554 : 7975 : auto& entry = graph.m_entries[idx];
1555 : 7975 : entry.m_locator[1].SetMissing();
1556 : : }
1557 : 7868 : }
1558 : :
1559 : 88479 : std::vector<TxGraph::Ref*> TxGraphImpl::GetAncestors(const Ref& arg, bool main_only) noexcept
1560 : : {
1561 : : // Return the empty vector if the Ref is empty.
1562 [ + + ]: 88479 : if (GetRefGraph(arg) == nullptr) return {};
1563 : 88295 : Assume(GetRefGraph(arg) == this);
1564 : : // Apply all removals and dependencies, as the result might be incorrect otherwise.
1565 [ + + ]: 88295 : size_t level = GetSpecifiedLevel(main_only);
1566 : 88295 : ApplyDependencies(level);
1567 : : // Ancestry cannot be known if unapplied dependencies remain.
1568 : 88295 : Assume(GetClusterSet(level).m_deps_to_add.empty());
1569 : : // Find the Cluster the argument is in, and return the empty vector if it isn't in any.
1570 : 88295 : auto cluster = FindCluster(GetRefIndex(arg), level);
1571 [ + + ]: 88295 : if (cluster == nullptr) return {};
1572 : : // Dispatch to the Cluster.
1573 : 87456 : std::pair<Cluster*, DepGraphIndex> match = {cluster, m_entries[GetRefIndex(arg)].m_locator[cluster->m_level].index};
1574 : 87456 : auto matches = std::span(&match, 1);
1575 : 87456 : std::vector<TxGraph::Ref*> ret;
1576 : 87456 : cluster->GetAncestorRefs(*this, matches, ret);
1577 : 87456 : return ret;
1578 : 87456 : }
1579 : :
1580 : 88419 : std::vector<TxGraph::Ref*> TxGraphImpl::GetDescendants(const Ref& arg, bool main_only) noexcept
1581 : : {
1582 : : // Return the empty vector if the Ref is empty.
1583 [ + + ]: 88419 : if (GetRefGraph(arg) == nullptr) return {};
1584 : 87493 : Assume(GetRefGraph(arg) == this);
1585 : : // Apply all removals and dependencies, as the result might be incorrect otherwise.
1586 [ + + ]: 87493 : size_t level = GetSpecifiedLevel(main_only);
1587 : 87493 : ApplyDependencies(level);
1588 : : // Ancestry cannot be known if unapplied dependencies remain.
1589 : 87493 : Assume(GetClusterSet(level).m_deps_to_add.empty());
1590 : : // Find the Cluster the argument is in, and return the empty vector if it isn't in any.
1591 : 87493 : auto cluster = FindCluster(GetRefIndex(arg), level);
1592 [ + + ]: 87493 : if (cluster == nullptr) return {};
1593 : : // Dispatch to the Cluster.
1594 : 86974 : std::pair<Cluster*, DepGraphIndex> match = {cluster, m_entries[GetRefIndex(arg)].m_locator[cluster->m_level].index};
1595 : 86974 : auto matches = std::span(&match, 1);
1596 : 86974 : std::vector<TxGraph::Ref*> ret;
1597 : 86974 : cluster->GetDescendantRefs(*this, matches, ret);
1598 : 86974 : return ret;
1599 : 86974 : }
1600 : :
1601 : 2713 : std::vector<TxGraph::Ref*> TxGraphImpl::GetAncestorsUnion(std::span<const Ref* const> args, bool main_only) noexcept
1602 : : {
1603 : : // Apply all dependencies, as the result might be incorrect otherwise.
1604 [ + + ]: 2713 : size_t level = GetSpecifiedLevel(main_only);
1605 : 2713 : ApplyDependencies(level);
1606 : : // Ancestry cannot be known if unapplied dependencies remain.
1607 : 2713 : Assume(GetClusterSet(level).m_deps_to_add.empty());
1608 : :
1609 : : // Translate args to matches.
1610 : 2713 : std::vector<std::pair<Cluster*, DepGraphIndex>> matches;
1611 : 2713 : matches.reserve(args.size());
1612 [ + + ]: 17147 : for (auto arg : args) {
1613 : 14434 : Assume(arg);
1614 : : // Skip empty Refs.
1615 [ + + ]: 14434 : if (GetRefGraph(*arg) == nullptr) continue;
1616 : 9760 : Assume(GetRefGraph(*arg) == this);
1617 : : // Find the Cluster the argument is in, and skip if none is found.
1618 : 9760 : auto cluster = FindCluster(GetRefIndex(*arg), level);
1619 [ + + ]: 9760 : if (cluster == nullptr) continue;
1620 : : // Append to matches.
1621 : 8472 : matches.emplace_back(cluster, m_entries[GetRefIndex(*arg)].m_locator[cluster->m_level].index);
1622 : : }
1623 : : // Group by Cluster.
1624 : 19999 : std::sort(matches.begin(), matches.end(), [](auto& a, auto& b) noexcept { return CompareClusters(a.first, b.first) < 0; });
1625 : : // Dispatch to the Clusters.
1626 : 2713 : std::span match_span(matches);
1627 : 2713 : std::vector<TxGraph::Ref*> ret;
1628 [ + + ]: 5287 : while (!match_span.empty()) {
1629 : 2574 : match_span.front().first->GetAncestorRefs(*this, match_span, ret);
1630 : : }
1631 : 2713 : return ret;
1632 : 2713 : }
1633 : :
1634 : 1839 : std::vector<TxGraph::Ref*> TxGraphImpl::GetDescendantsUnion(std::span<const Ref* const> args, bool main_only) noexcept
1635 : : {
1636 : : // Apply all dependencies, as the result might be incorrect otherwise.
1637 [ + + ]: 1839 : size_t level = GetSpecifiedLevel(main_only);
1638 : 1839 : ApplyDependencies(level);
1639 : : // Ancestry cannot be known if unapplied dependencies remain.
1640 : 1839 : Assume(GetClusterSet(level).m_deps_to_add.empty());
1641 : :
1642 : : // Translate args to matches.
1643 : 1839 : std::vector<std::pair<Cluster*, DepGraphIndex>> matches;
1644 : 1839 : matches.reserve(args.size());
1645 [ + + ]: 12705 : for (auto arg : args) {
1646 : 10866 : Assume(arg);
1647 : : // Skip empty Refs.
1648 [ + + ]: 10866 : if (GetRefGraph(*arg) == nullptr) continue;
1649 : 5895 : Assume(GetRefGraph(*arg) == this);
1650 : : // Find the Cluster the argument is in, and skip if none is found.
1651 : 5895 : auto cluster = FindCluster(GetRefIndex(*arg), level);
1652 [ + + ]: 5895 : if (cluster == nullptr) continue;
1653 : : // Append to matches.
1654 : 4732 : matches.emplace_back(cluster, m_entries[GetRefIndex(*arg)].m_locator[cluster->m_level].index);
1655 : : }
1656 : : // Group by Cluster.
1657 : 12269 : std::sort(matches.begin(), matches.end(), [](auto& a, auto& b) noexcept { return CompareClusters(a.first, b.first) < 0; });
1658 : : // Dispatch to the Clusters.
1659 : 1839 : std::span match_span(matches);
1660 : 1839 : std::vector<TxGraph::Ref*> ret;
1661 [ + + ]: 3217 : while (!match_span.empty()) {
1662 : 1378 : match_span.front().first->GetDescendantRefs(*this, match_span, ret);
1663 : : }
1664 : 1839 : return ret;
1665 : 1839 : }
1666 : :
1667 : 90463 : std::vector<TxGraph::Ref*> TxGraphImpl::GetCluster(const Ref& arg, bool main_only) noexcept
1668 : : {
1669 : : // Return the empty vector if the Ref is empty (which may be indicative of the transaction
1670 : : // having been removed already.
1671 [ + + ]: 90463 : if (GetRefGraph(arg) == nullptr) return {};
1672 : 89375 : Assume(GetRefGraph(arg) == this);
1673 : : // Apply all removals and dependencies, as the result might be incorrect otherwise.
1674 [ + + ]: 89375 : size_t level = GetSpecifiedLevel(main_only);
1675 : 89375 : ApplyDependencies(level);
1676 : : // Cluster linearization cannot be known if unapplied dependencies remain.
1677 : 89375 : Assume(GetClusterSet(level).m_deps_to_add.empty());
1678 : : // Find the Cluster the argument is in, and return the empty vector if it isn't in any.
1679 : 89375 : auto cluster = FindCluster(GetRefIndex(arg), level);
1680 [ + + ]: 89375 : if (cluster == nullptr) return {};
1681 : : // Make sure the Cluster has an acceptable quality level, and then dispatch to it.
1682 : 88426 : MakeAcceptable(*cluster);
1683 : 88426 : return cluster->GetClusterRefs(*this);
1684 : : }
1685 : :
1686 : 15606 : TxGraph::GraphIndex TxGraphImpl::GetTransactionCount(bool main_only) noexcept
1687 : : {
1688 [ + + ]: 15606 : size_t level = GetSpecifiedLevel(main_only);
1689 : 15606 : ApplyRemovals(level);
1690 : 15606 : return GetClusterSet(level).m_txcount;
1691 : : }
1692 : :
1693 : 91386 : FeePerWeight TxGraphImpl::GetIndividualFeerate(const Ref& arg) noexcept
1694 : : {
1695 : : // Return the empty FeePerWeight if the passed Ref is empty.
1696 [ + + ]: 91386 : if (GetRefGraph(arg) == nullptr) return {};
1697 : 89727 : Assume(GetRefGraph(arg) == this);
1698 : : // Find the cluster the argument is in (the level does not matter as individual feerates will
1699 : : // be identical if it occurs in both), and return the empty FeePerWeight if it isn't in any.
1700 : 89727 : Cluster* cluster{nullptr};
1701 [ + + ]: 96890 : for (int level = 0; level <= GetTopLevel(); ++level) {
1702 : : // Apply removals, so that we can correctly report FeePerWeight{} for non-existing
1703 : : // transactions.
1704 : 96309 : ApplyRemovals(level);
1705 [ + + ]: 96309 : if (m_entries[GetRefIndex(arg)].m_locator[level].IsPresent()) {
1706 : : cluster = m_entries[GetRefIndex(arg)].m_locator[level].cluster;
1707 : : break;
1708 : : }
1709 : : }
1710 [ + + ]: 89727 : if (cluster == nullptr) return {};
1711 : : // Dispatch to the Cluster.
1712 : 89146 : return cluster->GetIndividualFeerate(m_entries[GetRefIndex(arg)].m_locator[cluster->m_level].index);
1713 : : }
1714 : :
1715 : 516174 : FeePerWeight TxGraphImpl::GetMainChunkFeerate(const Ref& arg) noexcept
1716 : : {
1717 : : // Return the empty FeePerWeight if the passed Ref is empty.
1718 [ + + ]: 516174 : if (GetRefGraph(arg) == nullptr) return {};
1719 : 514392 : Assume(GetRefGraph(arg) == this);
1720 : : // Apply all removals and dependencies, as the result might be inaccurate otherwise.
1721 : 514392 : ApplyDependencies(/*level=*/0);
1722 : : // Chunk feerates cannot be accurately known if unapplied dependencies remain.
1723 : 514392 : Assume(m_main_clusterset.m_deps_to_add.empty());
1724 : : // Find the cluster the argument is in, and return the empty FeePerWeight if it isn't in any.
1725 : 514392 : auto cluster = FindCluster(GetRefIndex(arg), 0);
1726 [ + + ]: 514392 : if (cluster == nullptr) return {};
1727 : : // Make sure the Cluster has an acceptable quality level, and then return the transaction's
1728 : : // chunk feerate.
1729 : 513927 : MakeAcceptable(*cluster);
1730 : 513927 : const auto& entry = m_entries[GetRefIndex(arg)];
1731 : 513927 : return entry.m_main_chunk_feerate;
1732 : : }
1733 : :
1734 : 25512 : bool TxGraphImpl::IsOversized(bool main_only) noexcept
1735 : : {
1736 [ + + ]: 25512 : size_t level = GetSpecifiedLevel(main_only);
1737 : 25512 : auto& clusterset = GetClusterSet(level);
1738 [ + + ]: 25512 : if (clusterset.m_oversized.has_value()) {
1739 : : // Return cached value if known.
1740 : 22097 : return *clusterset.m_oversized;
1741 : : }
1742 : : // Find which Clusters will need to be merged together, as that is where the oversize
1743 : : // property is assessed.
1744 : 3415 : GroupClusters(level);
1745 : 3415 : Assume(clusterset.m_group_data.has_value());
1746 : 3415 : clusterset.m_oversized = clusterset.m_group_data->m_group_oversized;
1747 : 3415 : return *clusterset.m_oversized;
1748 : : }
1749 : :
1750 : 7111 : void TxGraphImpl::StartStaging() noexcept
1751 : : {
1752 : : // Staging cannot already exist.
1753 : 7111 : Assume(!m_staging_clusterset.has_value());
1754 : : // Apply all remaining dependencies in main before creating a staging graph. Once staging
1755 : : // exists, we cannot merge Clusters anymore (because of interference with Clusters being
1756 : : // pulled into staging), so to make sure all inspectors are available (if not oversized), do
1757 : : // all merging work now. Call SplitAll() first, so that even if ApplyDependencies does not do
1758 : : // any thing due to knowing the result is oversized, splitting is still performed.
1759 : 7111 : SplitAll(0);
1760 : 7111 : ApplyDependencies(0);
1761 : : // Construct the staging ClusterSet.
1762 : 7111 : m_staging_clusterset.emplace();
1763 : : // Copy statistics, precomputed data, and to-be-applied dependencies (only if oversized) to
1764 : : // the new graph. To-be-applied removals will always be empty at this point.
1765 : 7111 : m_staging_clusterset->m_txcount = m_main_clusterset.m_txcount;
1766 : 7111 : m_staging_clusterset->m_deps_to_add = m_main_clusterset.m_deps_to_add;
1767 : 7111 : m_staging_clusterset->m_group_data = m_main_clusterset.m_group_data;
1768 : 7111 : m_staging_clusterset->m_oversized = m_main_clusterset.m_oversized;
1769 : 7111 : Assume(m_staging_clusterset->m_oversized.has_value());
1770 : 7111 : }
1771 : :
1772 : 931 : void TxGraphImpl::AbortStaging() noexcept
1773 : : {
1774 : : // Staging must exist.
1775 : 931 : Assume(m_staging_clusterset.has_value());
1776 : : // Mark all removed transactions as Missing (so the staging locator for these transactions
1777 : : // can be reused if another staging is created).
1778 [ + + ]: 1195 : for (auto idx : m_staging_clusterset->m_removed) {
1779 : 264 : m_entries[idx].m_locator[1].SetMissing();
1780 : : }
1781 : : // Do the same with the non-removed transactions in staging Clusters.
1782 [ + + ]: 5586 : for (int quality = 0; quality < int(QualityLevel::NONE); ++quality) {
1783 [ + + ]: 12523 : for (auto& cluster : m_staging_clusterset->m_clusters[quality]) {
1784 : 7868 : cluster->MakeStagingTransactionsMissing(*this);
1785 : : }
1786 : : }
1787 : : // Destroy the staging ClusterSet.
1788 : 931 : m_staging_clusterset.reset();
1789 : 931 : Compact();
1790 [ + + ]: 931 : if (!m_main_clusterset.m_group_data.has_value()) {
1791 : : // In case m_oversized in main was kept after a Ref destruction while staging exists, we
1792 : : // need to re-evaluate m_oversized now.
1793 [ + - ]: 300 : m_main_clusterset.m_oversized = std::nullopt;
1794 : : }
1795 : 931 : }
1796 : :
1797 : 5290 : void TxGraphImpl::CommitStaging() noexcept
1798 : : {
1799 : : // Staging must exist.
1800 : 5290 : Assume(m_staging_clusterset.has_value());
1801 : : // Delete all conflicting Clusters in main, to make place for moving the staging ones
1802 : : // there. All of these have been copied to staging in PullIn().
1803 : 5290 : auto conflicts = GetConflicts();
1804 [ + + ]: 7865 : for (Cluster* conflict : conflicts) {
1805 : 2575 : conflict->Clear(*this);
1806 : 2575 : DeleteCluster(*conflict);
1807 : : }
1808 : : // Mark the removed transactions as Missing (so the staging locator for these transactions
1809 : : // can be reused if another staging is created).
1810 [ + + ]: 6066 : for (auto idx : m_staging_clusterset->m_removed) {
1811 : 776 : m_entries[idx].m_locator[1].SetMissing();
1812 : : }
1813 : : // Then move all Clusters in staging to main.
1814 [ + + ]: 31740 : for (int quality = 0; quality < int(QualityLevel::NONE); ++quality) {
1815 : 26450 : auto& stage_sets = m_staging_clusterset->m_clusters[quality];
1816 [ + + ]: 40564 : while (!stage_sets.empty()) {
1817 : 14114 : stage_sets.back()->MoveToMain(*this);
1818 : : }
1819 : : }
1820 : : // Move all statistics, precomputed data, and to-be-applied removals and dependencies.
1821 : 5290 : m_main_clusterset.m_deps_to_add = std::move(m_staging_clusterset->m_deps_to_add);
1822 : 5290 : m_main_clusterset.m_to_remove = std::move(m_staging_clusterset->m_to_remove);
1823 : 5290 : m_main_clusterset.m_group_data = std::move(m_staging_clusterset->m_group_data);
1824 : 5290 : m_main_clusterset.m_oversized = std::move(m_staging_clusterset->m_oversized);
1825 : 5290 : m_main_clusterset.m_txcount = std::move(m_staging_clusterset->m_txcount);
1826 : : // Delete the old staging graph, after all its information was moved to main.
1827 : 5290 : m_staging_clusterset.reset();
1828 : 5290 : Compact();
1829 : 5290 : }
1830 : :
1831 : 8233 : void Cluster::SetFee(TxGraphImpl& graph, DepGraphIndex idx, int64_t fee) noexcept
1832 : : {
1833 : : // Make sure the specified DepGraphIndex exists in this Cluster.
1834 : 8233 : Assume(m_depgraph.Positions()[idx]);
1835 : : // Bail out if the fee isn't actually being changed.
1836 [ + + ]: 8233 : if (m_depgraph.FeeRate(idx).fee == fee) return;
1837 : : // Update the fee, remember that relinearization will be necessary, and update the Entries
1838 : : // in the same Cluster.
1839 [ + + ]: 5546 : m_depgraph.FeeRate(idx).fee = fee;
1840 [ + + ]: 5546 : if (!NeedsSplitting()) {
1841 : 5456 : graph.SetClusterQuality(m_level, m_quality, m_setindex, QualityLevel::NEEDS_RELINEARIZE);
1842 : : } else {
1843 : 90 : graph.SetClusterQuality(m_level, m_quality, m_setindex, QualityLevel::NEEDS_SPLIT);
1844 : : }
1845 : 5546 : Updated(graph);
1846 : : }
1847 : :
1848 : 8816 : void TxGraphImpl::SetTransactionFee(const Ref& ref, int64_t fee) noexcept
1849 : : {
1850 : : // Don't do anything if the passed Ref is empty.
1851 [ + + ]: 8816 : if (GetRefGraph(ref) == nullptr) return;
1852 : 8186 : Assume(GetRefGraph(ref) == this);
1853 : : // Find the entry, its locator, and inform its Cluster about the new feerate, if any.
1854 : 8186 : auto& entry = m_entries[GetRefIndex(ref)];
1855 [ + + ]: 24558 : for (int level = 0; level < MAX_LEVELS; ++level) {
1856 : 16372 : auto& locator = entry.m_locator[level];
1857 [ + + ]: 16372 : if (locator.IsPresent()) {
1858 : 8233 : locator.cluster->SetFee(*this, locator.index, fee);
1859 : : }
1860 : : }
1861 : : }
1862 : :
1863 : 499777 : std::strong_ordering TxGraphImpl::CompareMainOrder(const Ref& a, const Ref& b) noexcept
1864 : : {
1865 : : // The references must not be empty.
1866 : 499777 : Assume(GetRefGraph(a) == this);
1867 : 499777 : Assume(GetRefGraph(b) == this);
1868 : : // Apply dependencies in main.
1869 : 499777 : ApplyDependencies(0);
1870 : 499777 : Assume(m_main_clusterset.m_deps_to_add.empty());
1871 : : // Make both involved Clusters acceptable, so chunk feerates are relevant.
1872 : 499777 : const auto& entry_a = m_entries[GetRefIndex(a)];
1873 : 499777 : const auto& entry_b = m_entries[GetRefIndex(b)];
1874 : 499777 : const auto& locator_a = entry_a.m_locator[0];
1875 : 499777 : const auto& locator_b = entry_b.m_locator[0];
1876 : 499777 : Assume(locator_a.IsPresent());
1877 : 499777 : Assume(locator_b.IsPresent());
1878 : 499777 : MakeAcceptable(*locator_a.cluster);
1879 : 499777 : MakeAcceptable(*locator_b.cluster);
1880 : : // Compare chunk feerates, and return result if it differs.
1881 : 499777 : auto feerate_cmp = FeeRateCompare(entry_b.m_main_chunk_feerate, entry_a.m_main_chunk_feerate);
1882 [ + + ]: 499777 : if (feerate_cmp < 0) return std::strong_ordering::less;
1883 [ + + ]: 380965 : if (feerate_cmp > 0) return std::strong_ordering::greater;
1884 : : // Compare Cluster* as tie-break for equal chunk feerates.
1885 [ + + ]: 300753 : if (locator_a.cluster != locator_b.cluster) {
1886 : 245705 : return CompareClusters(locator_a.cluster, locator_b.cluster);
1887 : : }
1888 : : // As final tie-break, compare position within cluster linearization.
1889 [ + + + + ]: 55048 : return entry_a.m_main_lin_index <=> entry_b.m_main_lin_index;
1890 : : }
1891 : :
1892 : 3991 : TxGraph::GraphIndex TxGraphImpl::CountDistinctClusters(std::span<const Ref* const> refs, bool main_only) noexcept
1893 : : {
1894 [ + + ]: 3991 : size_t level = GetSpecifiedLevel(main_only);
1895 : 3991 : ApplyDependencies(level);
1896 : 3991 : auto& clusterset = GetClusterSet(level);
1897 : 3991 : Assume(clusterset.m_deps_to_add.empty());
1898 : : // Build a vector of Clusters that the specified Refs occur in.
1899 : 3991 : std::vector<Cluster*> clusters;
1900 : 3991 : clusters.reserve(refs.size());
1901 [ + + ]: 57358 : for (const Ref* ref : refs) {
1902 : 53367 : Assume(ref);
1903 [ + + ]: 53367 : if (GetRefGraph(*ref) == nullptr) continue;
1904 : 45840 : Assume(GetRefGraph(*ref) == this);
1905 : 45840 : auto cluster = FindCluster(GetRefIndex(*ref), level);
1906 [ + + ]: 45840 : if (cluster != nullptr) clusters.push_back(cluster);
1907 : : }
1908 : : // Count the number of distinct elements in clusters.
1909 : 209079 : std::sort(clusters.begin(), clusters.end(), [](Cluster* a, Cluster* b) noexcept { return CompareClusters(a, b) < 0; });
1910 : 3991 : Cluster* last{nullptr};
1911 : 3991 : GraphIndex ret{0};
1912 [ + + ]: 46740 : for (Cluster* cluster : clusters) {
1913 : 42749 : ret += (cluster != last);
1914 : 42749 : last = cluster;
1915 : : }
1916 : 3991 : return ret;
1917 : 3991 : }
1918 : :
1919 : 100541 : void Cluster::SanityCheck(const TxGraphImpl& graph, int level) const
1920 : : {
1921 : : // There must be an m_mapping for each m_depgraph position (including holes).
1922 [ - + ]: 100541 : assert(m_depgraph.PositionRange() == m_mapping.size());
1923 : : // The linearization for this Cluster must contain every transaction once.
1924 [ - + ]: 100541 : assert(m_depgraph.TxCount() == m_linearization.size());
1925 : : // The number of transactions in a Cluster cannot exceed m_max_cluster_count.
1926 [ - + ]: 100541 : assert(m_linearization.size() <= graph.m_max_cluster_count);
1927 : : // The level must match the level the Cluster occurs in.
1928 [ - + ]: 100541 : assert(m_level == level);
1929 : : // m_quality and m_setindex are checked in TxGraphImpl::SanityCheck.
1930 : :
1931 : : // Compute the chunking of m_linearization.
1932 : 100541 : LinearizationChunking linchunking(m_depgraph, m_linearization);
1933 : :
1934 : : // Verify m_linearization.
1935 : 100541 : SetType m_done;
1936 : 100541 : LinearizationIndex linindex{0};
1937 [ - + ]: 100541 : assert(m_depgraph.IsAcyclic());
1938 [ + + ]: 223072 : for (auto lin_pos : m_linearization) {
1939 [ - + ]: 122531 : assert(lin_pos < m_mapping.size());
1940 : 122531 : const auto& entry = graph.m_entries[m_mapping[lin_pos]];
1941 : : // Check that the linearization is topological.
1942 : 122531 : m_done.Set(lin_pos);
1943 [ - + ]: 122531 : assert(m_done.IsSupersetOf(m_depgraph.Ancestors(lin_pos)));
1944 : : // Check that the Entry has a locator pointing back to this Cluster & position within it.
1945 [ - + ]: 122531 : assert(entry.m_locator[level].cluster == this);
1946 [ - + ]: 122531 : assert(entry.m_locator[level].index == lin_pos);
1947 : : // For main-level entries, check linearization position and chunk feerate.
1948 [ + + ]: 225998 : if (level == 0 && IsAcceptable()) {
1949 [ - + ]: 97262 : assert(entry.m_main_lin_index == linindex);
1950 : 97262 : ++linindex;
1951 [ + + ]: 97262 : if (!linchunking.GetChunk(0).transactions[lin_pos]) {
1952 : 9215 : linchunking.MarkDone(linchunking.GetChunk(0).transactions);
1953 : : }
1954 [ + - ]: 97262 : assert(entry.m_main_chunk_feerate == linchunking.GetChunk(0).feerate);
1955 : : // If this Cluster has an acceptable quality level, its chunks must be connected.
1956 [ - + ]: 97262 : assert(m_depgraph.IsConnected(linchunking.GetChunk(0).transactions));
1957 : : }
1958 : : }
1959 : : // Verify that each element of m_depgraph occurred in m_linearization.
1960 [ - + ]: 100541 : assert(m_done == m_depgraph.Positions());
1961 : 100541 : }
1962 : :
1963 : 4516 : void TxGraphImpl::SanityCheck() const
1964 : : {
1965 : : /** Which GraphIndexes ought to occur in m_unlinked, based on m_entries. */
1966 : 4516 : std::set<GraphIndex> expected_unlinked;
1967 : : /** Which Clusters ought to occur in ClusterSet::m_clusters, based on m_entries. */
1968 [ + + ]: 22580 : std::set<const Cluster*> expected_clusters[MAX_LEVELS];
1969 : : /** Which GraphIndexes ought to occur in ClusterSet::m_removed, based on m_entries. */
1970 [ + + ]: 22580 : std::set<GraphIndex> expected_removed[MAX_LEVELS];
1971 : : /** Which Cluster::m_sequence values have been encountered. */
1972 : 4516 : std::set<uint64_t> sequences;
1973 : : /** Whether compaction is possible in the current state. */
1974 : 4516 : bool compact_possible{true};
1975 : :
1976 : : // Go over all Entry objects in m_entries.
1977 [ + + ]: 141848 : for (GraphIndex idx = 0; idx < m_entries.size(); ++idx) {
1978 [ + + ]: 137332 : const auto& entry = m_entries[idx];
1979 [ + + ]: 137332 : if (entry.m_ref == nullptr) {
1980 : : // Unlinked Entry must have indexes appear in m_unlinked.
1981 [ + - ]: 15152 : expected_unlinked.insert(idx);
1982 : : } else {
1983 : : // Every non-unlinked Entry must have a Ref that points back to it.
1984 [ - + ]: 122180 : assert(GetRefGraph(*entry.m_ref) == this);
1985 [ - + ]: 122180 : assert(GetRefIndex(*entry.m_ref) == idx);
1986 : : }
1987 : : // Verify the Entry m_locators.
1988 : : bool was_present{false}, was_removed{false};
1989 [ + + ]: 411996 : for (int level = 0; level < MAX_LEVELS; ++level) {
1990 : 274664 : const auto& locator = entry.m_locator[level];
1991 : : // Every Locator must be in exactly one of these 3 states.
1992 [ + + + + : 823992 : assert(locator.IsMissing() + locator.IsRemoved() + locator.IsPresent() == 1);
- + ]
1993 [ + + ]: 274664 : if (locator.IsPresent()) {
1994 : : // Once removed, a transaction cannot be revived.
1995 [ - + ]: 122531 : assert(!was_removed);
1996 : : // Verify that the Cluster agrees with where the Locator claims the transaction is.
1997 [ - + ]: 122531 : assert(locator.cluster->GetClusterEntry(locator.index) == idx);
1998 : : // Remember that we expect said Cluster to appear in the ClusterSet::m_clusters.
1999 [ + - ]: 122531 : expected_clusters[level].insert(locator.cluster);
2000 : : was_present = true;
2001 [ + + ]: 276375 : } else if (locator.IsRemoved()) {
2002 : : // Level 0 (main) cannot have IsRemoved locators (IsMissing there means non-existing).
2003 [ - + ]: 1711 : assert(level > 0);
2004 : : // A Locator can only be IsRemoved if it was IsPresent before, and only once.
2005 [ - + ]: 1711 : assert(was_present && !was_removed);
2006 : : // Remember that we expect this GraphIndex to occur in the ClusterSet::m_removed.
2007 [ + - ]: 1711 : expected_removed[level].insert(idx);
2008 : : was_removed = true;
2009 : : }
2010 : : }
2011 : : }
2012 : :
2013 : : // For all levels (0 = main, 1 = staged)...
2014 [ + + ]: 10812 : for (int level = 0; level <= GetTopLevel(); ++level) {
2015 : 6296 : assert(level < MAX_LEVELS);
2016 : 6296 : auto& clusterset = GetClusterSet(level);
2017 : 6296 : std::set<const Cluster*> actual_clusters;
2018 : :
2019 : : // For all quality levels...
2020 [ + + ]: 37776 : for (int qual = 0; qual < int(QualityLevel::NONE); ++qual) {
2021 : 31480 : QualityLevel quality{qual};
2022 : 31480 : const auto& quality_clusters = clusterset.m_clusters[qual];
2023 : : // ... for all clusters in them ...
2024 [ + + ]: 132021 : for (ClusterSetIndex setindex = 0; setindex < quality_clusters.size(); ++setindex) {
2025 [ - + ]: 100541 : const auto& cluster = *quality_clusters[setindex];
2026 : : // Check the sequence number.
2027 [ - + ]: 100541 : assert(cluster.m_sequence < m_next_sequence_counter);
2028 [ - + ]: 100541 : assert(sequences.count(cluster.m_sequence) == 0);
2029 [ + - ]: 100541 : sequences.insert(cluster.m_sequence);
2030 : : // Remember we saw this Cluster (only if it is non-empty; empty Clusters aren't
2031 : : // expected to be referenced by the Entry vector).
2032 [ + + ]: 100541 : if (cluster.GetTxCount() != 0) {
2033 [ + - ]: 99301 : actual_clusters.insert(&cluster);
2034 : : }
2035 : : // Sanity check the cluster, according to the Cluster's internal rules.
2036 : 100541 : cluster.SanityCheck(*this, level);
2037 : : // Check that the cluster's quality and setindex matches its position in the quality list.
2038 [ - + ]: 100541 : assert(cluster.m_quality == quality);
2039 [ - + ]: 100541 : assert(cluster.m_setindex == setindex);
2040 : : }
2041 : : }
2042 : :
2043 : : // Verify that all to-be-removed transactions have valid identifiers.
2044 [ + + ]: 9933 : for (GraphIndex idx : clusterset.m_to_remove) {
2045 [ - + ]: 3637 : assert(idx < m_entries.size());
2046 : : // We cannot assert that all m_to_remove transactions are still present: ~Ref on a
2047 : : // (P,M) transaction (present in main, inherited in staging) will cause an m_to_remove
2048 : : // addition in both main and staging, but a subsequence ApplyRemovals in main will
2049 : : // cause it to disappear from staging too, leaving the m_to_remove in place.
2050 : : }
2051 : :
2052 : : // Verify that all to-be-added dependencies have valid identifiers.
2053 [ - + + + ]: 15693 : for (auto [par_idx, chl_idx] : clusterset.m_deps_to_add) {
2054 [ - + ]: 9397 : assert(par_idx != chl_idx);
2055 [ - + ]: 9397 : assert(par_idx < m_entries.size());
2056 [ - + ]: 9397 : assert(chl_idx < m_entries.size());
2057 : : }
2058 : :
2059 : : // Verify that the actually encountered clusters match the ones occurring in Entry vector.
2060 [ - + ]: 6296 : assert(actual_clusters == expected_clusters[level]);
2061 : :
2062 : : // Verify that the contents of m_removed matches what was expected based on the Entry vector.
2063 [ + - ]: 6296 : std::set<GraphIndex> actual_removed(clusterset.m_removed.begin(), clusterset.m_removed.end());
2064 [ + + ]: 27606 : for (auto i : expected_unlinked) {
2065 : : // If a transaction exists in both main and staging, and is removed from staging (adding
2066 : : // it to m_removed there), and consequently destroyed (wiping the locator completely),
2067 : : // it can remain in m_removed despite not having an IsRemoved() locator. Exclude those
2068 : : // transactions from the comparison here.
2069 : 21310 : actual_removed.erase(i);
2070 : 21310 : expected_removed[level].erase(i);
2071 : : }
2072 : :
2073 [ - + ]: 6296 : assert(actual_removed == expected_removed[level]);
2074 : :
2075 : : // If any GraphIndex entries remain in this ClusterSet, compact is not possible.
2076 [ + + ]: 6296 : if (!clusterset.m_deps_to_add.empty()) compact_possible = false;
2077 [ + + ]: 6296 : if (!clusterset.m_to_remove.empty()) compact_possible = false;
2078 [ + + ]: 6296 : if (!clusterset.m_removed.empty()) compact_possible = false;
2079 : :
2080 : : // If m_group_data exists, its m_group_oversized must match m_oversized.
2081 [ + + ]: 6296 : if (clusterset.m_group_data.has_value()) {
2082 [ + - ]: 5015 : assert(clusterset.m_oversized == clusterset.m_group_data->m_group_oversized);
2083 : : }
2084 : :
2085 : : // For non-top levels, m_oversized must be known (as it cannot change until the level
2086 : : // on top is gone).
2087 [ + + - + ]: 6296 : if (level < GetTopLevel()) assert(clusterset.m_oversized.has_value());
2088 : 6296 : }
2089 : :
2090 : : // Verify that the contents of m_unlinked matches what was expected based on the Entry vector.
2091 [ + - ]: 4516 : std::set<GraphIndex> actual_unlinked(m_unlinked.begin(), m_unlinked.end());
2092 [ - + ]: 4516 : assert(actual_unlinked == expected_unlinked);
2093 : :
2094 : : // If compaction was possible, it should have been performed already, and m_unlinked must be
2095 : : // empty (to prevent memory leaks due to an ever-growing m_entries vector).
2096 [ + + ]: 4516 : if (compact_possible) {
2097 [ - + ]: 2634 : assert(actual_unlinked.empty());
2098 : : }
2099 [ + + + + : 31612 : }
- - - - ]
2100 : :
2101 : 6769 : void TxGraphImpl::DoWork() noexcept
2102 : : {
2103 [ + + ]: 15812 : for (int level = 0; level <= GetTopLevel(); ++level) {
2104 : 9043 : MakeAllAcceptable(level);
2105 : : }
2106 : 6769 : }
2107 : :
2108 : : } // namespace
2109 : :
2110 : 167250 : TxGraph::Ref::~Ref()
2111 : : {
2112 [ + + ]: 167250 : if (m_graph) {
2113 : : // Inform the TxGraph about the Ref being destroyed.
2114 : 21406 : m_graph->UnlinkRef(m_index);
2115 : 21406 : m_graph = nullptr;
2116 : : }
2117 : 167250 : }
2118 : :
2119 : 82496 : TxGraph::Ref& TxGraph::Ref::operator=(Ref&& other) noexcept
2120 : : {
2121 : : // Unlink the current graph, if any.
2122 [ - + ]: 82496 : if (m_graph) m_graph->UnlinkRef(m_index);
2123 : : // Inform the other's graph about the move, if any.
2124 [ + - ]: 82496 : if (other.m_graph) other.m_graph->UpdateRef(other.m_index, *this);
2125 : : // Actually update the contents.
2126 : 82496 : m_graph = other.m_graph;
2127 : 82496 : m_index = other.m_index;
2128 : 82496 : other.m_graph = nullptr;
2129 : 82496 : other.m_index = GraphIndex(-1);
2130 : 82496 : return *this;
2131 : : }
2132 : :
2133 : 0 : TxGraph::Ref::Ref(Ref&& other) noexcept
2134 : : {
2135 : : // Inform the TxGraph of other that its Ref is being moved.
2136 [ # # ]: 0 : if (other.m_graph) other.m_graph->UpdateRef(other.m_index, *this);
2137 : : // Actually move the contents.
2138 : 0 : std::swap(m_graph, other.m_graph);
2139 : 0 : std::swap(m_index, other.m_index);
2140 : 0 : }
2141 : :
2142 : 2258 : std::unique_ptr<TxGraph> MakeTxGraph(unsigned max_cluster_count) noexcept
2143 : : {
2144 [ - + ]: 2258 : return std::make_unique<TxGraphImpl>(max_cluster_count);
2145 : : }
|
