Bitcoin Core 30.99.0
P2P Digital Currency
txgraph.cpp
Go to the documentation of this file.
1// Copyright (c) The Bitcoin Core developers
2// Distributed under the MIT software license, see the accompanying
3// file COPYING or http://www.opensource.org/licenses/mit-license.php.
4
5#include <txgraph.h>
6
7#include <cluster_linearize.h>
8#include <random.h>
9#include <util/bitset.h>
10#include <util/check.h>
11#include <util/feefrac.h>
12#include <util/vector.h>
13
14#include <compare>
15#include <functional>
16#include <memory>
17#include <set>
18#include <span>
19#include <unordered_set>
20#include <utility>
21
22namespace {
23
24using namespace cluster_linearize;
25
27static constexpr int MAX_LEVELS{2};
28
29// Forward declare the TxGraph implementation class.
30class TxGraphImpl;
31
33using LinearizationIndex = uint32_t;
35using ClusterSetIndex = uint32_t;
36
38enum class QualityLevel
39{
42 OVERSIZED_SINGLETON,
44 NEEDS_SPLIT,
46 NEEDS_SPLIT_ACCEPTABLE,
48 NEEDS_RELINEARIZE,
50 ACCEPTABLE,
52 OPTIMAL,
55 NONE,
56};
57
59struct TrimTxData
60{
61 // Fields populated by Cluster::AppendTrimData(). These are immutable after TrimTxData
62 // construction.
64 FeePerWeight m_chunk_feerate;
66 TxGraph::GraphIndex m_index;
68 uint32_t m_tx_size;
69
70 // Fields only used internally by TxGraphImpl::Trim():
72 uint32_t m_deps_left;
74 uint32_t m_parent_count;
76 uint32_t m_parent_offset;
78 uint32_t m_children_count;
80 uint32_t m_children_offset;
81
82 // Fields only used internally by TxGraphImpl::Trim()'s union-find implementation, and only for
83 // transactions that are definitely included or definitely rejected.
84 //
85 // As transactions get processed, they get organized into trees which form partitions
86 // representing the would-be clusters up to that point. The root of each tree is a
87 // representative for that partition. See
88 // https://en.wikipedia.org/wiki/Disjoint-set_data_structure.
89 //
92 TrimTxData* m_uf_parent;
94 uint32_t m_uf_count;
96 uint64_t m_uf_size;
97};
98
100class Cluster
101{
102 friend class TxGraphImpl;
103 friend class BlockBuilderImpl;
104
105protected:
106 using GraphIndex = TxGraph::GraphIndex;
107 using SetType = BitSet<MAX_CLUSTER_COUNT_LIMIT>;
109 QualityLevel m_quality{QualityLevel::NONE};
111 ClusterSetIndex m_setindex{ClusterSetIndex(-1)};
114 uint64_t m_sequence;
115
116 explicit Cluster(uint64_t sequence) noexcept : m_sequence(sequence) {}
117
118public:
119 // Provide virtual destructor, for safe polymorphic usage inside std::unique_ptr.
120 virtual ~Cluster() = default;
121
122 // Cannot move or copy (would invalidate Cluster* in Locator and ClusterSet). */
123 Cluster(const Cluster&) = delete;
124 Cluster& operator=(const Cluster&) = delete;
125 Cluster(Cluster&&) = delete;
126 Cluster& operator=(Cluster&&) = delete;
127
128 // Generic helper functions.
129
131 bool IsAcceptable(bool after_split = false) const noexcept
132 {
133 return m_quality == QualityLevel::ACCEPTABLE || m_quality == QualityLevel::OPTIMAL ||
134 (after_split && m_quality == QualityLevel::NEEDS_SPLIT_ACCEPTABLE);
135 }
137 bool IsOptimal() const noexcept
138 {
139 return m_quality == QualityLevel::OPTIMAL;
140 }
144 bool IsOversized() const noexcept { return m_quality == QualityLevel::OVERSIZED_SINGLETON; }
146 bool NeedsSplitting() const noexcept
147 {
148 return m_quality == QualityLevel::NEEDS_SPLIT ||
149 m_quality == QualityLevel::NEEDS_SPLIT_ACCEPTABLE;
150 }
151
153 virtual DepGraphIndex GetMinIntendedTxCount() const noexcept = 0;
155 virtual DepGraphIndex GetMaxTxCount() const noexcept = 0;
158 virtual size_t TotalMemoryUsage() const noexcept = 0;
160 virtual DepGraphIndex GetDepGraphIndexRange() const noexcept = 0;
162 virtual LinearizationIndex GetTxCount() const noexcept = 0;
164 virtual uint64_t GetTotalTxSize() const noexcept = 0;
166 virtual GraphIndex GetClusterEntry(DepGraphIndex index) const noexcept = 0;
169 virtual DepGraphIndex AppendTransaction(GraphIndex graph_idx, FeePerWeight feerate) noexcept = 0;
171 virtual void AddDependencies(SetType parents, DepGraphIndex child) noexcept = 0;
173 virtual void ExtractTransactions(const std::function<void (DepGraphIndex, GraphIndex, FeePerWeight, SetType)>& visit_fn) noexcept = 0;
176 virtual int GetLevel(const TxGraphImpl& graph) const noexcept = 0;
178 virtual void UpdateMapping(DepGraphIndex cluster_idx, GraphIndex graph_idx) noexcept = 0;
180 virtual void Updated(TxGraphImpl& graph, int level) noexcept = 0;
182 virtual Cluster* CopyToStaging(TxGraphImpl& graph) const noexcept = 0;
184 virtual void GetConflicts(const TxGraphImpl& graph, std::vector<Cluster*>& out) const noexcept = 0;
187 virtual void MakeStagingTransactionsMissing(TxGraphImpl& graph) noexcept = 0;
189 virtual void Clear(TxGraphImpl& graph, int level) noexcept = 0;
191 virtual void MoveToMain(TxGraphImpl& graph) noexcept = 0;
193 virtual void Compact() noexcept = 0;
194
195 // Functions that implement the Cluster-specific side of internal TxGraphImpl mutations.
196
199 virtual void ApplyRemovals(TxGraphImpl& graph, int level, std::span<GraphIndex>& to_remove) noexcept = 0;
202 [[nodiscard]] virtual bool Split(TxGraphImpl& graph, int level) noexcept = 0;
204 virtual void Merge(TxGraphImpl& graph, int level, Cluster& cluster) noexcept = 0;
206 virtual void ApplyDependencies(TxGraphImpl& graph, int level, std::span<std::pair<GraphIndex, GraphIndex>> to_apply) noexcept = 0;
209 virtual std::pair<uint64_t, bool> Relinearize(TxGraphImpl& graph, int level, uint64_t max_iters) noexcept = 0;
211 virtual void AppendChunkFeerates(std::vector<FeeFrac>& ret) const noexcept = 0;
215 virtual uint64_t AppendTrimData(std::vector<TrimTxData>& ret, std::vector<std::pair<GraphIndex, GraphIndex>>& deps) const noexcept = 0;
216
217 // Functions that implement the Cluster-specific side of public TxGraph functions.
218
221 virtual void GetAncestorRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept = 0;
224 virtual void GetDescendantRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept = 0;
228 virtual bool GetClusterRefs(TxGraphImpl& graph, std::span<TxGraph::Ref*> range, LinearizationIndex start_pos) noexcept = 0;
230 virtual FeePerWeight GetIndividualFeerate(DepGraphIndex idx) noexcept = 0;
232 virtual void SetFee(TxGraphImpl& graph, int level, DepGraphIndex idx, int64_t fee) noexcept = 0;
233
234 // Debugging functions.
235
236 virtual void SanityCheck(const TxGraphImpl& graph, int level) const = 0;
237};
238
241class GenericClusterImpl final : public Cluster
242{
243 friend class TxGraphImpl;
245 DepGraph<SetType> m_depgraph;
249 std::vector<GraphIndex> m_mapping;
252 std::vector<DepGraphIndex> m_linearization;
253
254public:
256 static constexpr DepGraphIndex MIN_INTENDED_TX_COUNT{2};
258 static constexpr DepGraphIndex MAX_TX_COUNT{SetType::Size()};
259
260 GenericClusterImpl() noexcept = delete;
262 explicit GenericClusterImpl(uint64_t sequence) noexcept;
263
264 size_t TotalMemoryUsage() const noexcept final;
265 constexpr DepGraphIndex GetMinIntendedTxCount() const noexcept final { return MIN_INTENDED_TX_COUNT; }
266 constexpr DepGraphIndex GetMaxTxCount() const noexcept final { return MAX_TX_COUNT; }
267 DepGraphIndex GetDepGraphIndexRange() const noexcept final { return m_depgraph.PositionRange(); }
268 LinearizationIndex GetTxCount() const noexcept final { return m_linearization.size(); }
269 uint64_t GetTotalTxSize() const noexcept final;
270 GraphIndex GetClusterEntry(DepGraphIndex index) const noexcept final { return m_mapping[index]; }
271 DepGraphIndex AppendTransaction(GraphIndex graph_idx, FeePerWeight feerate) noexcept final;
272 void AddDependencies(SetType parents, DepGraphIndex child) noexcept final;
273 void ExtractTransactions(const std::function<void (DepGraphIndex, GraphIndex, FeePerWeight, SetType)>& visit_fn) noexcept final;
274 int GetLevel(const TxGraphImpl& graph) const noexcept final;
275 void UpdateMapping(DepGraphIndex cluster_idx, GraphIndex graph_idx) noexcept final { m_mapping[cluster_idx] = graph_idx; }
276 void Updated(TxGraphImpl& graph, int level) noexcept final;
277 Cluster* CopyToStaging(TxGraphImpl& graph) const noexcept final;
278 void GetConflicts(const TxGraphImpl& graph, std::vector<Cluster*>& out) const noexcept final;
279 void MakeStagingTransactionsMissing(TxGraphImpl& graph) noexcept final;
280 void Clear(TxGraphImpl& graph, int level) noexcept final;
281 void MoveToMain(TxGraphImpl& graph) noexcept final;
282 void Compact() noexcept final;
283 void ApplyRemovals(TxGraphImpl& graph, int level, std::span<GraphIndex>& to_remove) noexcept final;
284 [[nodiscard]] bool Split(TxGraphImpl& graph, int level) noexcept final;
285 void Merge(TxGraphImpl& graph, int level, Cluster& cluster) noexcept final;
286 void ApplyDependencies(TxGraphImpl& graph, int level, std::span<std::pair<GraphIndex, GraphIndex>> to_apply) noexcept final;
287 std::pair<uint64_t, bool> Relinearize(TxGraphImpl& graph, int level, uint64_t max_iters) noexcept final;
288 void AppendChunkFeerates(std::vector<FeeFrac>& ret) const noexcept final;
289 uint64_t AppendTrimData(std::vector<TrimTxData>& ret, std::vector<std::pair<GraphIndex, GraphIndex>>& deps) const noexcept final;
290 void GetAncestorRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept final;
291 void GetDescendantRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept final;
292 bool GetClusterRefs(TxGraphImpl& graph, std::span<TxGraph::Ref*> range, LinearizationIndex start_pos) noexcept final;
293 FeePerWeight GetIndividualFeerate(DepGraphIndex idx) noexcept final;
294 void SetFee(TxGraphImpl& graph, int level, DepGraphIndex idx, int64_t fee) noexcept final;
295 void SanityCheck(const TxGraphImpl& graph, int level) const final;
296};
297
299class SingletonClusterImpl final : public Cluster
300{
301 friend class TxGraphImpl;
302
304 FeePerWeight m_feerate;
306 static constexpr auto NO_GRAPH_INDEX = GraphIndex(-1);
308 GraphIndex m_graph_index = NO_GRAPH_INDEX;
309
310public:
312 static constexpr DepGraphIndex MIN_INTENDED_TX_COUNT{1};
314 static constexpr DepGraphIndex MAX_TX_COUNT{1};
315
316 SingletonClusterImpl() noexcept = delete;
318 explicit SingletonClusterImpl(uint64_t sequence) noexcept : Cluster(sequence) {}
319
320 size_t TotalMemoryUsage() const noexcept final;
321 constexpr DepGraphIndex GetMinIntendedTxCount() const noexcept final { return MIN_INTENDED_TX_COUNT; }
322 constexpr DepGraphIndex GetMaxTxCount() const noexcept final { return MAX_TX_COUNT; }
323 LinearizationIndex GetTxCount() const noexcept final { return m_graph_index != NO_GRAPH_INDEX; }
324 DepGraphIndex GetDepGraphIndexRange() const noexcept final { return GetTxCount(); }
325 uint64_t GetTotalTxSize() const noexcept final { return GetTxCount() ? m_feerate.size : 0; }
326 GraphIndex GetClusterEntry(DepGraphIndex index) const noexcept final { Assume(index == 0); Assume(GetTxCount()); return m_graph_index; }
327 DepGraphIndex AppendTransaction(GraphIndex graph_idx, FeePerWeight feerate) noexcept final;
328 void AddDependencies(SetType parents, DepGraphIndex child) noexcept final;
329 void ExtractTransactions(const std::function<void (DepGraphIndex, GraphIndex, FeePerWeight, SetType)>& visit_fn) noexcept final;
330 int GetLevel(const TxGraphImpl& graph) const noexcept final;
331 void UpdateMapping(DepGraphIndex cluster_idx, GraphIndex graph_idx) noexcept final { Assume(cluster_idx == 0); m_graph_index = graph_idx; }
332 void Updated(TxGraphImpl& graph, int level) noexcept final;
333 Cluster* CopyToStaging(TxGraphImpl& graph) const noexcept final;
334 void GetConflicts(const TxGraphImpl& graph, std::vector<Cluster*>& out) const noexcept final;
335 void MakeStagingTransactionsMissing(TxGraphImpl& graph) noexcept final;
336 void Clear(TxGraphImpl& graph, int level) noexcept final;
337 void MoveToMain(TxGraphImpl& graph) noexcept final;
338 void Compact() noexcept final;
339 void ApplyRemovals(TxGraphImpl& graph, int level, std::span<GraphIndex>& to_remove) noexcept final;
340 [[nodiscard]] bool Split(TxGraphImpl& graph, int level) noexcept final;
341 void Merge(TxGraphImpl& graph, int level, Cluster& cluster) noexcept final;
342 void ApplyDependencies(TxGraphImpl& graph, int level, std::span<std::pair<GraphIndex, GraphIndex>> to_apply) noexcept final;
343 std::pair<uint64_t, bool> Relinearize(TxGraphImpl& graph, int level, uint64_t max_iters) noexcept final;
344 void AppendChunkFeerates(std::vector<FeeFrac>& ret) const noexcept final;
345 uint64_t AppendTrimData(std::vector<TrimTxData>& ret, std::vector<std::pair<GraphIndex, GraphIndex>>& deps) const noexcept final;
346 void GetAncestorRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept final;
347 void GetDescendantRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept final;
348 bool GetClusterRefs(TxGraphImpl& graph, std::span<TxGraph::Ref*> range, LinearizationIndex start_pos) noexcept final;
349 FeePerWeight GetIndividualFeerate(DepGraphIndex idx) noexcept final;
350 void SetFee(TxGraphImpl& graph, int level, DepGraphIndex idx, int64_t fee) noexcept final;
351 void SanityCheck(const TxGraphImpl& graph, int level) const final;
352};
353
377class TxGraphImpl final : public TxGraph
378{
379 friend class Cluster;
380 friend class SingletonClusterImpl;
381 friend class GenericClusterImpl;
382 friend class BlockBuilderImpl;
383private:
385 FastRandomContext m_rng;
387 const DepGraphIndex m_max_cluster_count;
389 const uint64_t m_max_cluster_size;
392 const uint64_t m_acceptable_iters;
393
395 struct GroupEntry
396 {
398 uint32_t m_cluster_offset;
400 uint32_t m_cluster_count;
402 uint32_t m_deps_offset;
404 uint32_t m_deps_count;
405 };
406
408 struct GroupData
409 {
411 std::vector<GroupEntry> m_groups;
413 std::vector<Cluster*> m_group_clusters;
414 };
415
417 struct ClusterSet
418 {
420 std::array<std::vector<std::unique_ptr<Cluster>>, int(QualityLevel::NONE)> m_clusters;
422 std::vector<GraphIndex> m_to_remove;
425 std::vector<std::pair<GraphIndex, GraphIndex>> m_deps_to_add;
427 std::optional<GroupData> m_group_data = GroupData{};
431 std::vector<GraphIndex> m_removed;
434 GraphIndex m_txcount{0};
436 GraphIndex m_txcount_oversized{0};
438 std::optional<bool> m_oversized{false};
441 size_t m_cluster_usage{0};
442
443 ClusterSet() noexcept = default;
444 };
445
447 ClusterSet m_main_clusterset;
449 std::optional<ClusterSet> m_staging_clusterset;
451 uint64_t m_next_sequence_counter{0};
452
454 struct ChunkData
455 {
457 mutable GraphIndex m_graph_index;
459 LinearizationIndex m_chunk_count;
460
461 ChunkData(GraphIndex graph_index, LinearizationIndex chunk_count) noexcept :
462 m_graph_index{graph_index}, m_chunk_count{chunk_count} {}
463 };
464
466 static std::strong_ordering CompareClusters(Cluster* a, Cluster* b) noexcept
467 {
468 // The nullptr pointer compares before everything else.
469 if (a == nullptr || b == nullptr) {
470 return (a != nullptr) <=> (b != nullptr);
471 }
472 // If neither pointer is nullptr, compare the Clusters' sequence numbers.
473 Assume(a == b || a->m_sequence != b->m_sequence);
474 return a->m_sequence <=> b->m_sequence;
475 }
476
478 std::strong_ordering CompareMainTransactions(GraphIndex a, GraphIndex b) const noexcept
479 {
480 Assume(a < m_entries.size() && b < m_entries.size());
481 const auto& entry_a = m_entries[a];
482 const auto& entry_b = m_entries[b];
483 // Compare chunk feerates, and return result if it differs.
484 auto feerate_cmp = FeeRateCompare(entry_b.m_main_chunk_feerate, entry_a.m_main_chunk_feerate);
485 if (feerate_cmp < 0) return std::strong_ordering::less;
486 if (feerate_cmp > 0) return std::strong_ordering::greater;
487 // Compare Cluster m_sequence as tie-break for equal chunk feerates.
488 const auto& locator_a = entry_a.m_locator[0];
489 const auto& locator_b = entry_b.m_locator[0];
490 Assume(locator_a.IsPresent() && locator_b.IsPresent());
491 if (locator_a.cluster != locator_b.cluster) {
492 return CompareClusters(locator_a.cluster, locator_b.cluster);
493 }
494 // As final tie-break, compare position within cluster linearization.
495 return entry_a.m_main_lin_index <=> entry_b.m_main_lin_index;
496 }
497
499 class ChunkOrder
500 {
501 const TxGraphImpl* const m_graph;
502 public:
503 explicit ChunkOrder(const TxGraphImpl* graph) : m_graph(graph) {}
504
505 bool operator()(const ChunkData& a, const ChunkData& b) const noexcept
506 {
507 return m_graph->CompareMainTransactions(a.m_graph_index, b.m_graph_index) < 0;
508 }
509 };
510
512 using ChunkIndex = std::set<ChunkData, ChunkOrder>;
513
516 ChunkIndex m_main_chunkindex;
518 size_t m_main_chunkindex_observers{0};
520 std::vector<ChunkIndex::node_type> m_main_chunkindex_discarded;
521
552 struct Locator
553 {
555 Cluster* cluster{nullptr};
557 DepGraphIndex index{0};
558
560 void SetMissing() noexcept { cluster = nullptr; index = 0; }
562 void SetRemoved() noexcept { cluster = nullptr; index = DepGraphIndex(-1); }
564 void SetPresent(Cluster* c, DepGraphIndex i) noexcept { cluster = c; index = i; }
566 bool IsMissing() const noexcept { return cluster == nullptr && index == 0; }
568 bool IsRemoved() const noexcept { return cluster == nullptr && index == DepGraphIndex(-1); }
570 bool IsPresent() const noexcept { return cluster != nullptr; }
571 };
572
574 struct Entry
575 {
577 Ref* m_ref{nullptr};
580 ChunkIndex::iterator m_main_chunkindex_iterator;
582 Locator m_locator[MAX_LEVELS];
584 FeePerWeight m_main_chunk_feerate;
586 LinearizationIndex m_main_lin_index;
587 };
588
590 std::vector<Entry> m_entries;
591
593 std::vector<GraphIndex> m_unlinked;
594
595public:
597 explicit TxGraphImpl(DepGraphIndex max_cluster_count, uint64_t max_cluster_size, uint64_t acceptable_iters) noexcept :
598 m_max_cluster_count(max_cluster_count),
599 m_max_cluster_size(max_cluster_size),
600 m_acceptable_iters(acceptable_iters),
601 m_main_chunkindex(ChunkOrder(this))
602 {
603 Assume(max_cluster_count >= 1);
604 Assume(max_cluster_count <= MAX_CLUSTER_COUNT_LIMIT);
605 }
606
608 ~TxGraphImpl() noexcept;
609
610 // Cannot move or copy (would invalidate TxGraphImpl* in Ref, MiningOrder, EvictionOrder).
611 TxGraphImpl(const TxGraphImpl&) = delete;
612 TxGraphImpl& operator=(const TxGraphImpl&) = delete;
613 TxGraphImpl(TxGraphImpl&&) = delete;
614 TxGraphImpl& operator=(TxGraphImpl&&) = delete;
615
616 // Simple helper functions.
617
619 void SwapIndexes(GraphIndex a, GraphIndex b) noexcept;
622 Cluster* FindCluster(GraphIndex idx, int level) const noexcept { return FindClusterAndLevel(idx, level).first; }
624 std::pair<Cluster*, int> FindClusterAndLevel(GraphIndex idx, int level) const noexcept;
626 std::unique_ptr<Cluster> ExtractCluster(int level, QualityLevel quality, ClusterSetIndex setindex) noexcept;
628 void DeleteCluster(Cluster& cluster, int level) noexcept;
630 ClusterSetIndex InsertCluster(int level, std::unique_ptr<Cluster>&& cluster, QualityLevel quality) noexcept;
632 void SetClusterQuality(int level, QualityLevel old_quality, ClusterSetIndex old_index, QualityLevel new_quality) noexcept;
634 int GetTopLevel() const noexcept { return m_staging_clusterset.has_value(); }
636 int GetSpecifiedLevel(Level level) const noexcept { return level == Level::TOP && m_staging_clusterset.has_value(); }
638 ClusterSet& GetClusterSet(int level) noexcept;
639 const ClusterSet& GetClusterSet(int level) const noexcept;
643 void ClearLocator(int level, GraphIndex index, bool oversized_tx) noexcept;
645 std::vector<Cluster*> GetConflicts() const noexcept;
647 void ClearChunkData(Entry& entry) noexcept;
649 void CreateChunkData(GraphIndex idx, LinearizationIndex chunk_count) noexcept;
651 std::unique_ptr<GenericClusterImpl> CreateEmptyGenericCluster() noexcept
652 {
653 return std::make_unique<GenericClusterImpl>(m_next_sequence_counter++);
654 }
656 std::unique_ptr<SingletonClusterImpl> CreateEmptySingletonCluster() noexcept
657 {
658 return std::make_unique<SingletonClusterImpl>(m_next_sequence_counter++);
659 }
662 std::unique_ptr<Cluster> CreateEmptyCluster(DepGraphIndex tx_count) noexcept
663 {
664 if (tx_count >= SingletonClusterImpl::MIN_INTENDED_TX_COUNT && tx_count <= SingletonClusterImpl::MAX_TX_COUNT) {
665 return CreateEmptySingletonCluster();
666 }
667 if (tx_count >= GenericClusterImpl::MIN_INTENDED_TX_COUNT && tx_count <= GenericClusterImpl::MAX_TX_COUNT) {
668 return CreateEmptyGenericCluster();
669 }
670 assert(false);
671 return {};
672 }
673
674 // Functions for handling Refs.
675
677 void UpdateRef(GraphIndex idx, Ref& new_location) noexcept final
678 {
679 auto& entry = m_entries[idx];
680 Assume(entry.m_ref != nullptr);
681 entry.m_ref = &new_location;
682 }
683
685 void UnlinkRef(GraphIndex idx) noexcept final
686 {
687 auto& entry = m_entries[idx];
688 Assume(entry.m_ref != nullptr);
689 Assume(m_main_chunkindex_observers == 0 || !entry.m_locator[0].IsPresent());
690 entry.m_ref = nullptr;
691 // Mark the transaction as to be removed in all levels where it explicitly or implicitly
692 // exists.
693 bool exists_anywhere{false};
694 bool exists{false};
695 for (int level = 0; level <= GetTopLevel(); ++level) {
696 if (entry.m_locator[level].IsPresent()) {
697 exists_anywhere = true;
698 exists = true;
699 } else if (entry.m_locator[level].IsRemoved()) {
700 exists = false;
701 }
702 if (exists) {
703 auto& clusterset = GetClusterSet(level);
704 clusterset.m_to_remove.push_back(idx);
705 // Force recomputation of grouping data.
706 clusterset.m_group_data = std::nullopt;
707 // Do not wipe the oversized state of main if staging exists. The reason for this
708 // is that the alternative would mean that cluster merges may need to be applied to
709 // a formerly-oversized main graph while staging exists (to satisfy chunk feerate
710 // queries into main, for example), and such merges could conflict with pulls of
711 // some of their constituents into staging.
712 if (level == GetTopLevel() && clusterset.m_oversized == true) {
713 clusterset.m_oversized = std::nullopt;
714 }
715 }
716 }
717 m_unlinked.push_back(idx);
718 if (!exists_anywhere) Compact();
719 }
720
721 // Functions related to various normalization/application steps.
725 void Compact() noexcept;
729 Cluster* PullIn(Cluster* cluster, int level) noexcept;
732 void ApplyRemovals(int up_to_level) noexcept;
734 void Split(Cluster& cluster, int level) noexcept;
736 void SplitAll(int up_to_level) noexcept;
738 void GroupClusters(int level) noexcept;
740 void Merge(std::span<Cluster*> to_merge, int level) noexcept;
742 void ApplyDependencies(int level) noexcept;
744 void MakeAcceptable(Cluster& cluster, int level) noexcept;
746 void MakeAllAcceptable(int level) noexcept;
747
748 // Implementations for the public TxGraph interface.
749
750 Ref AddTransaction(const FeePerWeight& feerate) noexcept final;
751 void RemoveTransaction(const Ref& arg) noexcept final;
752 void AddDependency(const Ref& parent, const Ref& child) noexcept final;
753 void SetTransactionFee(const Ref&, int64_t fee) noexcept final;
754
755 bool DoWork(uint64_t iters) noexcept final;
756
757 void StartStaging() noexcept final;
758 void CommitStaging() noexcept final;
759 void AbortStaging() noexcept final;
760 bool HaveStaging() const noexcept final { return m_staging_clusterset.has_value(); }
761
762 bool Exists(const Ref& arg, Level level) noexcept final;
763 FeePerWeight GetMainChunkFeerate(const Ref& arg) noexcept final;
764 FeePerWeight GetIndividualFeerate(const Ref& arg) noexcept final;
765 std::vector<Ref*> GetCluster(const Ref& arg, Level level) noexcept final;
766 std::vector<Ref*> GetAncestors(const Ref& arg, Level level) noexcept final;
767 std::vector<Ref*> GetDescendants(const Ref& arg, Level level) noexcept final;
768 std::vector<Ref*> GetAncestorsUnion(std::span<const Ref* const> args, Level level) noexcept final;
769 std::vector<Ref*> GetDescendantsUnion(std::span<const Ref* const> args, Level level) noexcept final;
770 GraphIndex GetTransactionCount(Level level) noexcept final;
771 bool IsOversized(Level level) noexcept final;
772 std::strong_ordering CompareMainOrder(const Ref& a, const Ref& b) noexcept final;
773 GraphIndex CountDistinctClusters(std::span<const Ref* const> refs, Level level) noexcept final;
774 std::pair<std::vector<FeeFrac>, std::vector<FeeFrac>> GetMainStagingDiagrams() noexcept final;
775 std::vector<Ref*> Trim() noexcept final;
776
777 std::unique_ptr<BlockBuilder> GetBlockBuilder() noexcept final;
778 std::pair<std::vector<Ref*>, FeePerWeight> GetWorstMainChunk() noexcept final;
779
780 size_t GetMainMemoryUsage() noexcept final;
781
782 void SanityCheck() const final;
783};
784
785TxGraphImpl::ClusterSet& TxGraphImpl::GetClusterSet(int level) noexcept
786{
787 if (level == 0) return m_main_clusterset;
788 Assume(level == 1);
789 Assume(m_staging_clusterset.has_value());
790 return *m_staging_clusterset;
791}
792
793const TxGraphImpl::ClusterSet& TxGraphImpl::GetClusterSet(int level) const noexcept
794{
795 if (level == 0) return m_main_clusterset;
796 Assume(level == 1);
797 Assume(m_staging_clusterset.has_value());
798 return *m_staging_clusterset;
799}
800
802class BlockBuilderImpl final : public TxGraph::BlockBuilder
803{
806 TxGraphImpl* const m_graph;
808 std::unordered_set<uint64_t> m_excluded_clusters;
810 TxGraphImpl::ChunkIndex::const_iterator m_cur_iter;
813 Cluster* m_cur_cluster;
815 bool m_known_end_of_cluster;
816
817 // Move m_cur_iter / m_cur_cluster to the next acceptable chunk.
818 void Next() noexcept;
819
820public:
822 BlockBuilderImpl(TxGraphImpl& graph) noexcept;
823
824 // Implement the public interface.
825 ~BlockBuilderImpl() final;
826 std::optional<std::pair<std::vector<TxGraph::Ref*>, FeePerWeight>> GetCurrentChunk() noexcept final;
827 void Include() noexcept final;
828 void Skip() noexcept final;
829};
830
831void TxGraphImpl::ClearChunkData(Entry& entry) noexcept
832{
833 if (entry.m_main_chunkindex_iterator != m_main_chunkindex.end()) {
834 Assume(m_main_chunkindex_observers == 0);
835 // If the Entry has a non-empty m_main_chunkindex_iterator, extract it, and move the handle
836 // to the cache of discarded chunkindex entries.
837 m_main_chunkindex_discarded.emplace_back(m_main_chunkindex.extract(entry.m_main_chunkindex_iterator));
838 entry.m_main_chunkindex_iterator = m_main_chunkindex.end();
839 }
840}
841
842void TxGraphImpl::CreateChunkData(GraphIndex idx, LinearizationIndex chunk_count) noexcept
843{
844 auto& entry = m_entries[idx];
845 if (!m_main_chunkindex_discarded.empty()) {
846 // Reuse an discarded node handle.
847 auto& node = m_main_chunkindex_discarded.back().value();
848 node.m_graph_index = idx;
849 node.m_chunk_count = chunk_count;
850 auto insert_result = m_main_chunkindex.insert(std::move(m_main_chunkindex_discarded.back()));
851 Assume(insert_result.inserted);
852 entry.m_main_chunkindex_iterator = insert_result.position;
853 m_main_chunkindex_discarded.pop_back();
854 } else {
855 // Construct a new entry.
856 auto emplace_result = m_main_chunkindex.emplace(idx, chunk_count);
857 Assume(emplace_result.second);
858 entry.m_main_chunkindex_iterator = emplace_result.first;
859 }
860}
861
862size_t GenericClusterImpl::TotalMemoryUsage() const noexcept
863{
864 return // Dynamic memory allocated in this Cluster.
865 memusage::DynamicUsage(m_mapping) + memusage::DynamicUsage(m_linearization) +
866 // Dynamic memory usage inside m_depgraph.
867 m_depgraph.DynamicMemoryUsage() +
868 // Memory usage of the allocated Cluster itself.
869 memusage::MallocUsage(sizeof(GenericClusterImpl)) +
870 // Memory usage of the ClusterSet::m_clusters entry.
871 sizeof(std::unique_ptr<Cluster>);
872}
873
874size_t SingletonClusterImpl::TotalMemoryUsage() const noexcept
875{
876 return // Memory usage of the allocated SingletonClusterImpl itself.
877 memusage::MallocUsage(sizeof(SingletonClusterImpl)) +
878 // Memory usage of the ClusterSet::m_clusters entry.
879 sizeof(std::unique_ptr<Cluster>);
880}
881
882uint64_t GenericClusterImpl::GetTotalTxSize() const noexcept
883{
884 uint64_t ret{0};
885 for (auto i : m_linearization) {
886 ret += m_depgraph.FeeRate(i).size;
887 }
888 return ret;
889}
890
891DepGraphIndex GenericClusterImpl::AppendTransaction(GraphIndex graph_idx, FeePerWeight feerate) noexcept
892{
893 Assume(graph_idx != GraphIndex(-1));
894 auto ret = m_depgraph.AddTransaction(feerate);
895 m_mapping.push_back(graph_idx);
896 m_linearization.push_back(ret);
897 return ret;
898}
899
900DepGraphIndex SingletonClusterImpl::AppendTransaction(GraphIndex graph_idx, FeePerWeight feerate) noexcept
901{
902 Assume(!GetTxCount());
903 m_graph_index = graph_idx;
904 m_feerate = feerate;
905 return 0;
906}
907
908void GenericClusterImpl::AddDependencies(SetType parents, DepGraphIndex child) noexcept
909{
910 m_depgraph.AddDependencies(parents, child);
911}
912
913void SingletonClusterImpl::AddDependencies(SetType parents, DepGraphIndex child) noexcept
914{
915 // Singletons cannot have any dependencies.
916 Assume(child == 0);
917 Assume(parents == SetType{} || parents == SetType::Fill(0));
918}
919
920void GenericClusterImpl::ExtractTransactions(const std::function<void (DepGraphIndex, GraphIndex, FeePerWeight, SetType)>& visit_fn) noexcept
921{
922 for (auto pos : m_linearization) {
923 visit_fn(pos, m_mapping[pos], FeePerWeight::FromFeeFrac(m_depgraph.FeeRate(pos)), m_depgraph.GetReducedParents(pos));
924 }
925 // Purge this Cluster, now that everything has been moved.
926 m_depgraph = DepGraph<SetType>{};
927 m_linearization.clear();
928 m_mapping.clear();
929}
930
931void SingletonClusterImpl::ExtractTransactions(const std::function<void (DepGraphIndex, GraphIndex, FeePerWeight, SetType)>& visit_fn) noexcept
932{
933 if (GetTxCount()) {
934 visit_fn(0, m_graph_index, m_feerate, SetType{});
935 m_graph_index = NO_GRAPH_INDEX;
936 }
937}
938
939int GenericClusterImpl::GetLevel(const TxGraphImpl& graph) const noexcept
940{
941 // GetLevel() does not work for empty Clusters.
942 if (!Assume(!m_linearization.empty())) return -1;
943
944 // Pick an arbitrary Entry that occurs in this Cluster.
945 const auto& entry = graph.m_entries[m_mapping[m_linearization.front()]];
946 // See if there is a level whose Locator matches this Cluster, if so return that level.
947 for (int level = 0; level < MAX_LEVELS; ++level) {
948 if (entry.m_locator[level].cluster == this) return level;
949 }
950 // Given that we started with an Entry that occurs in this Cluster, one of its Locators must
951 // point back to it.
952 assert(false);
953 return -1;
954}
955
956int SingletonClusterImpl::GetLevel(const TxGraphImpl& graph) const noexcept
957{
958 // GetLevel() does not work for empty Clusters.
959 if (!Assume(GetTxCount())) return -1;
960
961 // Get the Entry in this Cluster.
962 const auto& entry = graph.m_entries[m_graph_index];
963 // See if there is a level whose Locator matches this Cluster, if so return that level.
964 for (int level = 0; level < MAX_LEVELS; ++level) {
965 if (entry.m_locator[level].cluster == this) return level;
966 }
967 // Given that we started with an Entry that occurs in this Cluster, one of its Locators must
968 // point back to it.
969 assert(false);
970 return -1;
971}
972
973void TxGraphImpl::ClearLocator(int level, GraphIndex idx, bool oversized_tx) noexcept
974{
975 auto& entry = m_entries[idx];
976 auto& clusterset = GetClusterSet(level);
977 Assume(entry.m_locator[level].IsPresent());
978 // Change the locator from Present to Missing or Removed.
979 if (level == 0 || !entry.m_locator[level - 1].IsPresent()) {
980 entry.m_locator[level].SetMissing();
981 } else {
982 entry.m_locator[level].SetRemoved();
983 clusterset.m_removed.push_back(idx);
984 }
985 // Update the transaction count.
986 --clusterset.m_txcount;
987 clusterset.m_txcount_oversized -= oversized_tx;
988 // If clearing main, adjust the status of Locators of this transaction in staging, if it exists.
989 if (level == 0 && GetTopLevel() == 1) {
990 if (entry.m_locator[1].IsRemoved()) {
991 entry.m_locator[1].SetMissing();
992 } else if (!entry.m_locator[1].IsPresent()) {
993 --m_staging_clusterset->m_txcount;
994 m_staging_clusterset->m_txcount_oversized -= oversized_tx;
995 }
996 }
997 if (level == 0) ClearChunkData(entry);
998}
999
1000void GenericClusterImpl::Updated(TxGraphImpl& graph, int level) noexcept
1001{
1002 // Update all the Locators for this Cluster's Entry objects.
1003 for (DepGraphIndex idx : m_linearization) {
1004 auto& entry = graph.m_entries[m_mapping[idx]];
1005 // Discard any potential ChunkData prior to modifying the Cluster (as that could
1006 // invalidate its ordering).
1007 if (level == 0) graph.ClearChunkData(entry);
1008 entry.m_locator[level].SetPresent(this, idx);
1009 }
1010 // If this is for the main graph (level = 0), and the Cluster's quality is ACCEPTABLE or
1011 // OPTIMAL, compute its chunking and store its information in the Entry's m_main_lin_index
1012 // and m_main_chunk_feerate. These fields are only accessed after making the entire graph
1013 // ACCEPTABLE, so it is pointless to compute these if we haven't reached that quality level
1014 // yet.
1015 if (level == 0 && IsAcceptable()) {
1016 const LinearizationChunking chunking(m_depgraph, m_linearization);
1017 LinearizationIndex lin_idx{0};
1018 // Iterate over the chunks.
1019 for (unsigned chunk_idx = 0; chunk_idx < chunking.NumChunksLeft(); ++chunk_idx) {
1020 auto chunk = chunking.GetChunk(chunk_idx);
1021 auto chunk_count = chunk.transactions.Count();
1022 Assume(chunk_count > 0);
1023 // Iterate over the transactions in the linearization, which must match those in chunk.
1024 while (true) {
1025 DepGraphIndex idx = m_linearization[lin_idx];
1026 GraphIndex graph_idx = m_mapping[idx];
1027 auto& entry = graph.m_entries[graph_idx];
1028 entry.m_main_lin_index = lin_idx++;
1029 entry.m_main_chunk_feerate = FeePerWeight::FromFeeFrac(chunk.feerate);
1030 Assume(chunk.transactions[idx]);
1031 chunk.transactions.Reset(idx);
1032 if (chunk.transactions.None()) {
1033 // Last transaction in the chunk.
1034 if (chunk_count == 1 && chunk_idx + 1 == chunking.NumChunksLeft()) {
1035 // If this is the final chunk of the cluster, and it contains just a single
1036 // transaction (which will always be true for the very common singleton
1037 // clusters), store the special value -1 as chunk count.
1038 chunk_count = LinearizationIndex(-1);
1039 }
1040 graph.CreateChunkData(graph_idx, chunk_count);
1041 break;
1042 }
1043 }
1044 }
1045 }
1046}
1047
1048void SingletonClusterImpl::Updated(TxGraphImpl& graph, int level) noexcept
1049{
1050 // Don't do anything if this is empty.
1051 if (GetTxCount() == 0) return;
1052
1053 auto& entry = graph.m_entries[m_graph_index];
1054 // Discard any potential ChunkData prior to modifying the Cluster (as that could
1055 // invalidate its ordering).
1056 if (level == 0) graph.ClearChunkData(entry);
1057 entry.m_locator[level].SetPresent(this, 0);
1058 // If this is for the main graph (level = 0), compute its chunking and store its information in
1059 // the Entry's m_main_lin_index and m_main_chunk_feerate.
1060 if (level == 0 && IsAcceptable()) {
1061 entry.m_main_lin_index = 0;
1062 entry.m_main_chunk_feerate = m_feerate;
1063 // Always use the special LinearizationIndex(-1), indicating singleton chunk at end of
1064 // Cluster, here.
1065 graph.CreateChunkData(m_graph_index, LinearizationIndex(-1));
1066 }
1067}
1068
1069void GenericClusterImpl::GetConflicts(const TxGraphImpl& graph, std::vector<Cluster*>& out) const noexcept
1070{
1071 for (auto i : m_linearization) {
1072 auto& entry = graph.m_entries[m_mapping[i]];
1073 // For every transaction Entry in this Cluster, if it also exists in a lower-level Cluster,
1074 // then that Cluster conflicts.
1075 if (entry.m_locator[0].IsPresent()) {
1076 out.push_back(entry.m_locator[0].cluster);
1077 }
1078 }
1079}
1080
1081void SingletonClusterImpl::GetConflicts(const TxGraphImpl& graph, std::vector<Cluster*>& out) const noexcept
1082{
1083 // Empty clusters have no conflicts.
1084 if (GetTxCount() == 0) return;
1085
1086 auto& entry = graph.m_entries[m_graph_index];
1087 // If the transaction in this Cluster also exists in a lower-level Cluster, then that Cluster
1088 // conflicts.
1089 if (entry.m_locator[0].IsPresent()) {
1090 out.push_back(entry.m_locator[0].cluster);
1091 }
1092}
1093
1094std::vector<Cluster*> TxGraphImpl::GetConflicts() const noexcept
1095{
1096 Assume(GetTopLevel() == 1);
1097 auto& clusterset = GetClusterSet(1);
1098 std::vector<Cluster*> ret;
1099 // All main Clusters containing transactions in m_removed (so (P,R) ones) are conflicts.
1100 for (auto i : clusterset.m_removed) {
1101 auto& entry = m_entries[i];
1102 if (entry.m_locator[0].IsPresent()) {
1103 ret.push_back(entry.m_locator[0].cluster);
1104 }
1105 }
1106 // Then go over all Clusters at this level, and find their conflicts (the (P,P) ones).
1107 for (int quality = 0; quality < int(QualityLevel::NONE); ++quality) {
1108 auto& clusters = clusterset.m_clusters[quality];
1109 for (const auto& cluster : clusters) {
1110 cluster->GetConflicts(*this, ret);
1111 }
1112 }
1113 // Deduplicate the result (the same Cluster may appear multiple times).
1114 std::sort(ret.begin(), ret.end(), [](Cluster* a, Cluster* b) noexcept { return CompareClusters(a, b) < 0; });
1115 ret.erase(std::unique(ret.begin(), ret.end()), ret.end());
1116 return ret;
1117}
1118
1119Cluster* GenericClusterImpl::CopyToStaging(TxGraphImpl& graph) const noexcept
1120{
1121 // Construct an empty Cluster.
1122 auto ret = graph.CreateEmptyGenericCluster();
1123 auto ptr = ret.get();
1124 // Copy depgraph, mapping, and linearization.
1125 ptr->m_depgraph = m_depgraph;
1126 ptr->m_mapping = m_mapping;
1127 ptr->m_linearization = m_linearization;
1128 // Insert the new Cluster into the graph.
1129 graph.InsertCluster(/*level=*/1, std::move(ret), m_quality);
1130 // Update its Locators.
1131 ptr->Updated(graph, /*level=*/1);
1132 // Update memory usage.
1133 graph.GetClusterSet(/*level=*/1).m_cluster_usage += ptr->TotalMemoryUsage();
1134 return ptr;
1135}
1136
1137Cluster* SingletonClusterImpl::CopyToStaging(TxGraphImpl& graph) const noexcept
1138{
1139 // Construct an empty Cluster.
1140 auto ret = graph.CreateEmptySingletonCluster();
1141 auto ptr = ret.get();
1142 // Copy data.
1143 ptr->m_graph_index = m_graph_index;
1144 ptr->m_feerate = m_feerate;
1145 // Insert the new Cluster into the graph.
1146 graph.InsertCluster(/*level=*/1, std::move(ret), m_quality);
1147 // Update its Locators.
1148 ptr->Updated(graph, /*level=*/1);
1149 // Update memory usage.
1150 graph.GetClusterSet(/*level=*/1).m_cluster_usage += ptr->TotalMemoryUsage();
1151 return ptr;
1152}
1153
1154void GenericClusterImpl::ApplyRemovals(TxGraphImpl& graph, int level, std::span<GraphIndex>& to_remove) noexcept
1155{
1156 // Iterate over the prefix of to_remove that applies to this cluster.
1157 Assume(!to_remove.empty());
1158 SetType todo;
1159 graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage();
1160 do {
1161 GraphIndex idx = to_remove.front();
1162 Assume(idx < graph.m_entries.size());
1163 auto& entry = graph.m_entries[idx];
1164 auto& locator = entry.m_locator[level];
1165 // Stop once we hit an entry that applies to another Cluster.
1166 if (locator.cluster != this) break;
1167 // - Remember it in a set of to-remove DepGraphIndexes.
1168 todo.Set(locator.index);
1169 // - Remove from m_mapping. This isn't strictly necessary as unused positions in m_mapping
1170 // are just never accessed, but set it to -1 here to increase the ability to detect a bug
1171 // that causes it to be accessed regardless.
1172 m_mapping[locator.index] = GraphIndex(-1);
1173 // - Remove its linearization index from the Entry (if in main).
1174 if (level == 0) {
1175 entry.m_main_lin_index = LinearizationIndex(-1);
1176 }
1177 // - Mark it as missing/removed in the Entry's locator.
1178 graph.ClearLocator(level, idx, m_quality == QualityLevel::OVERSIZED_SINGLETON);
1179 to_remove = to_remove.subspan(1);
1180 } while(!to_remove.empty());
1181
1182 auto quality = m_quality;
1183 Assume(todo.Any());
1184 // Wipe from the Cluster's DepGraph (this is O(n) regardless of the number of entries
1185 // removed, so we benefit from batching all the removals).
1186 m_depgraph.RemoveTransactions(todo);
1187 m_mapping.resize(m_depgraph.PositionRange());
1188
1189 // First remove all removals at the end of the linearization.
1190 while (!m_linearization.empty() && todo[m_linearization.back()]) {
1191 todo.Reset(m_linearization.back());
1192 m_linearization.pop_back();
1193 }
1194 if (todo.None()) {
1195 // If no further removals remain, and thus all removals were at the end, we may be able
1196 // to leave the cluster at a better quality level.
1197 if (IsAcceptable(/*after_split=*/true)) {
1198 quality = QualityLevel::NEEDS_SPLIT_ACCEPTABLE;
1199 } else {
1200 quality = QualityLevel::NEEDS_SPLIT;
1201 }
1202 } else {
1203 // If more removals remain, filter those out of m_linearization.
1204 m_linearization.erase(std::remove_if(
1205 m_linearization.begin(),
1206 m_linearization.end(),
1207 [&](auto pos) { return todo[pos]; }), m_linearization.end());
1208 quality = QualityLevel::NEEDS_SPLIT;
1209 }
1210 Compact();
1211 graph.GetClusterSet(level).m_cluster_usage += TotalMemoryUsage();
1212 graph.SetClusterQuality(level, m_quality, m_setindex, quality);
1213 Updated(graph, level);
1214}
1215
1216void SingletonClusterImpl::ApplyRemovals(TxGraphImpl& graph, int level, std::span<GraphIndex>& to_remove) noexcept
1217{
1218 // We can only remove the one transaction this Cluster has.
1219 Assume(!to_remove.empty());
1220 Assume(GetTxCount());
1221 Assume(to_remove.front() == m_graph_index);
1222 // Pop all copies of m_graph_index from the front of to_remove (at least one, but there may be
1223 // multiple).
1224 do {
1225 to_remove = to_remove.subspan(1);
1226 } while (!to_remove.empty() && to_remove.front() == m_graph_index);
1227 // Clear this cluster.
1228 graph.ClearLocator(level, m_graph_index, m_quality == QualityLevel::OVERSIZED_SINGLETON);
1229 m_graph_index = NO_GRAPH_INDEX;
1230 graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::NEEDS_SPLIT);
1231 // No need to account for m_cluster_usage changes here, as SingletonClusterImpl has constant
1232 // memory usage.
1233}
1234
1235void GenericClusterImpl::Clear(TxGraphImpl& graph, int level) noexcept
1236{
1237 Assume(GetTxCount());
1238 graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage();
1239 for (auto i : m_linearization) {
1240 graph.ClearLocator(level, m_mapping[i], m_quality == QualityLevel::OVERSIZED_SINGLETON);
1241 }
1242 m_depgraph = {};
1243 m_linearization.clear();
1244 m_mapping.clear();
1245}
1246
1247void SingletonClusterImpl::Clear(TxGraphImpl& graph, int level) noexcept
1248{
1249 Assume(GetTxCount());
1250 graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage();
1251 graph.ClearLocator(level, m_graph_index, m_quality == QualityLevel::OVERSIZED_SINGLETON);
1252 m_graph_index = NO_GRAPH_INDEX;
1253}
1254
1255void GenericClusterImpl::MoveToMain(TxGraphImpl& graph) noexcept
1256{
1257 for (auto i : m_linearization) {
1258 GraphIndex idx = m_mapping[i];
1259 auto& entry = graph.m_entries[idx];
1260 entry.m_locator[1].SetMissing();
1261 }
1262 auto quality = m_quality;
1263 // Subtract memory usage from staging and add it to main.
1264 graph.GetClusterSet(/*level=*/1).m_cluster_usage -= TotalMemoryUsage();
1265 graph.GetClusterSet(/*level=*/0).m_cluster_usage += TotalMemoryUsage();
1266 // Remove cluster itself from staging and add it to main.
1267 auto cluster = graph.ExtractCluster(1, quality, m_setindex);
1268 graph.InsertCluster(/*level=*/0, std::move(cluster), quality);
1269 Updated(graph, /*level=*/0);
1270}
1271
1272void SingletonClusterImpl::MoveToMain(TxGraphImpl& graph) noexcept
1273{
1274 if (GetTxCount()) {
1275 auto& entry = graph.m_entries[m_graph_index];
1276 entry.m_locator[1].SetMissing();
1277 }
1278 auto quality = m_quality;
1279 graph.GetClusterSet(/*level=*/1).m_cluster_usage -= TotalMemoryUsage();
1280 auto cluster = graph.ExtractCluster(/*level=*/1, quality, m_setindex);
1281 graph.InsertCluster(/*level=*/0, std::move(cluster), quality);
1282 graph.GetClusterSet(/*level=*/0).m_cluster_usage += TotalMemoryUsage();
1283 Updated(graph, /*level=*/0);
1284}
1285
1286void GenericClusterImpl::Compact() noexcept
1287{
1288 m_linearization.shrink_to_fit();
1289 m_mapping.shrink_to_fit();
1290 m_depgraph.Compact();
1291}
1292
1293void SingletonClusterImpl::Compact() noexcept
1294{
1295 // Nothing to compact; SingletonClusterImpl is constant size.
1296}
1297
1298void GenericClusterImpl::AppendChunkFeerates(std::vector<FeeFrac>& ret) const noexcept
1299{
1300 auto chunk_feerates = ChunkLinearization(m_depgraph, m_linearization);
1301 ret.reserve(ret.size() + chunk_feerates.size());
1302 ret.insert(ret.end(), chunk_feerates.begin(), chunk_feerates.end());
1303}
1304
1305void SingletonClusterImpl::AppendChunkFeerates(std::vector<FeeFrac>& ret) const noexcept
1306{
1307 if (GetTxCount()) {
1308 ret.push_back(m_feerate);
1309 }
1310}
1311
1312uint64_t GenericClusterImpl::AppendTrimData(std::vector<TrimTxData>& ret, std::vector<std::pair<GraphIndex, GraphIndex>>& deps) const noexcept
1313{
1314 const LinearizationChunking linchunking(m_depgraph, m_linearization);
1315 LinearizationIndex pos{0};
1316 uint64_t size{0};
1317 auto prev_index = GraphIndex(-1);
1318 // Iterate over the chunks of this cluster's linearization.
1319 for (unsigned i = 0; i < linchunking.NumChunksLeft(); ++i) {
1320 const auto& [chunk, chunk_feerate] = linchunking.GetChunk(i);
1321 // Iterate over the transactions of that chunk, in linearization order.
1322 auto chunk_tx_count = chunk.Count();
1323 for (unsigned j = 0; j < chunk_tx_count; ++j) {
1324 auto cluster_idx = m_linearization[pos];
1325 // The transaction must appear in the chunk.
1326 Assume(chunk[cluster_idx]);
1327 // Construct a new element in ret.
1328 auto& entry = ret.emplace_back();
1329 entry.m_chunk_feerate = FeePerWeight::FromFeeFrac(chunk_feerate);
1330 entry.m_index = m_mapping[cluster_idx];
1331 // If this is not the first transaction of the cluster linearization, it has an
1332 // implicit dependency on its predecessor.
1333 if (pos != 0) deps.emplace_back(prev_index, entry.m_index);
1334 prev_index = entry.m_index;
1335 entry.m_tx_size = m_depgraph.FeeRate(cluster_idx).size;
1336 size += entry.m_tx_size;
1337 ++pos;
1338 }
1339 }
1340 return size;
1341}
1342
1343uint64_t SingletonClusterImpl::AppendTrimData(std::vector<TrimTxData>& ret, std::vector<std::pair<GraphIndex, GraphIndex>>& deps) const noexcept
1344{
1345 if (!GetTxCount()) return 0;
1346 auto& entry = ret.emplace_back();
1347 entry.m_chunk_feerate = m_feerate;
1348 entry.m_index = m_graph_index;
1349 entry.m_tx_size = m_feerate.size;
1350 return m_feerate.size;
1351}
1352
1353bool GenericClusterImpl::Split(TxGraphImpl& graph, int level) noexcept
1354{
1355 // This function can only be called when the Cluster needs splitting.
1356 Assume(NeedsSplitting());
1357 // Determine the new quality the split-off Clusters will have.
1358 QualityLevel new_quality = IsAcceptable(/*after_split=*/true) ? QualityLevel::ACCEPTABLE
1359 : QualityLevel::NEEDS_RELINEARIZE;
1360 // If we're going to produce ACCEPTABLE clusters (i.e., when in NEEDS_SPLIT_ACCEPTABLE), we
1361 // need to post-linearize to make sure the split-out versions are all connected (as
1362 // connectivity may have changed by removing part of the cluster). This could be done on each
1363 // resulting split-out cluster separately, but it is simpler to do it once up front before
1364 // splitting. This step is not necessary if the resulting clusters are NEEDS_RELINEARIZE, as
1365 // they will be post-linearized anyway in MakeAcceptable().
1366 if (new_quality == QualityLevel::ACCEPTABLE) {
1367 PostLinearize(m_depgraph, m_linearization);
1368 }
1370 auto todo = m_depgraph.Positions();
1373 std::vector<std::pair<Cluster*, DepGraphIndex>> remap(m_depgraph.PositionRange());
1374 std::vector<Cluster*> new_clusters;
1375 bool first{true};
1376 // Iterate over the connected components of this Cluster's m_depgraph.
1377 while (todo.Any()) {
1378 auto component = m_depgraph.FindConnectedComponent(todo);
1379 auto component_size = component.Count();
1380 auto split_quality = component_size <= 2 ? QualityLevel::OPTIMAL : new_quality;
1381 if (first && component == todo && SetType::Fill(component_size) == component && component_size >= MIN_INTENDED_TX_COUNT) {
1382 // The existing Cluster is an entire component, without holes. Leave it be, but update
1383 // its quality. If there are holes, we continue, so that the Cluster is reconstructed
1384 // without holes, reducing memory usage. If the component's size is below the intended
1385 // transaction count for this Cluster implementation, continue so that it can get
1386 // converted.
1387 Assume(todo == m_depgraph.Positions());
1388 graph.SetClusterQuality(level, m_quality, m_setindex, split_quality);
1389 // If this made the quality ACCEPTABLE or OPTIMAL, we need to compute and cache its
1390 // chunking.
1391 Updated(graph, level);
1392 return false;
1393 }
1394 first = false;
1395 // Construct a new Cluster to hold the found component.
1396 auto new_cluster = graph.CreateEmptyCluster(component_size);
1397 new_clusters.push_back(new_cluster.get());
1398 // Remember that all the component's transactions go to this new Cluster. The positions
1399 // will be determined below, so use -1 for now.
1400 for (auto i : component) {
1401 remap[i] = {new_cluster.get(), DepGraphIndex(-1)};
1402 }
1403 graph.InsertCluster(level, std::move(new_cluster), split_quality);
1404 todo -= component;
1405 }
1406 // We have to split the Cluster up. Remove accounting for the existing one first.
1407 graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage();
1408 // Redistribute the transactions.
1409 for (auto i : m_linearization) {
1411 Cluster* new_cluster = remap[i].first;
1412 // Copy the transaction to the new cluster's depgraph, and remember the position.
1413 remap[i].second = new_cluster->AppendTransaction(m_mapping[i], FeePerWeight::FromFeeFrac(m_depgraph.FeeRate(i)));
1414 }
1415 // Redistribute the dependencies.
1416 for (auto i : m_linearization) {
1418 Cluster* new_cluster = remap[i].first;
1419 // Copy its parents, translating positions.
1420 SetType new_parents;
1421 for (auto par : m_depgraph.GetReducedParents(i)) new_parents.Set(remap[par].second);
1422 new_cluster->AddDependencies(new_parents, remap[i].second);
1423 }
1424 // Update all the Locators of moved transactions, and memory usage.
1425 for (Cluster* new_cluster : new_clusters) {
1426 new_cluster->Updated(graph, level);
1427 new_cluster->Compact();
1428 graph.GetClusterSet(level).m_cluster_usage += new_cluster->TotalMemoryUsage();
1429 }
1430 // Wipe this Cluster, and return that it needs to be deleted.
1431 m_depgraph = DepGraph<SetType>{};
1432 m_mapping.clear();
1433 m_linearization.clear();
1434 return true;
1435}
1436
1437bool SingletonClusterImpl::Split(TxGraphImpl& graph, int level) noexcept
1438{
1439 Assume(NeedsSplitting());
1440 if (GetTxCount() == 0) {
1441 // The cluster is now empty.
1442 graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage();
1443 return true;
1444 } else {
1445 // Nothing changed.
1446 graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::OPTIMAL);
1447 Updated(graph, level);
1448 return false;
1449 }
1450}
1451
1452void GenericClusterImpl::Merge(TxGraphImpl& graph, int level, Cluster& other) noexcept
1453{
1455 std::vector<DepGraphIndex> remap(other.GetDepGraphIndexRange());
1456 // Iterate over all transactions in the other Cluster (the one being absorbed).
1457 other.ExtractTransactions([&](DepGraphIndex pos, GraphIndex idx, FeePerWeight feerate, SetType other_parents) noexcept {
1458 // Copy the transaction into this Cluster, and remember its position.
1459 auto new_pos = m_depgraph.AddTransaction(feerate);
1460 // Since this cluster must have been made hole-free before being merged into, all added
1461 // transactions should appear at the end.
1462 Assume(new_pos == m_mapping.size());
1463 remap[pos] = new_pos;
1464 m_mapping.push_back(idx);
1465 m_linearization.push_back(new_pos);
1466 // Copy the transaction's dependencies, translating them using remap. Note that since
1467 // pos iterates in linearization order, which is topological, all parents of pos should
1468 // already be in remap.
1469 SetType parents;
1470 for (auto par : other_parents) {
1471 parents.Set(remap[par]);
1472 }
1473 m_depgraph.AddDependencies(parents, remap[pos]);
1474 // Update the transaction's Locator. There is no need to call Updated() to update chunk
1475 // feerates, as Updated() will be invoked by Cluster::ApplyDependencies on the resulting
1476 // merged Cluster later anyway.
1477 auto& entry = graph.m_entries[idx];
1478 // Discard any potential ChunkData prior to modifying the Cluster (as that could
1479 // invalidate its ordering).
1480 if (level == 0) graph.ClearChunkData(entry);
1481 entry.m_locator[level].SetPresent(this, new_pos);
1482 });
1483}
1484
1485void SingletonClusterImpl::Merge(TxGraphImpl& graph, int level, Cluster& other_abstract) noexcept
1486{
1487 // Nothing can be merged into a singleton; it should have been converted to GenericClusterImpl
1488 // first.
1489 Assume(false);
1490}
1491
1492void GenericClusterImpl::ApplyDependencies(TxGraphImpl& graph, int level, std::span<std::pair<GraphIndex, GraphIndex>> to_apply) noexcept
1493{
1494 // This function is invoked by TxGraphImpl::ApplyDependencies after merging groups of Clusters
1495 // between which dependencies are added, which simply concatenates their linearizations. Invoke
1496 // PostLinearize, which has the effect that the linearization becomes a merge-sort of the
1497 // constituent linearizations. Do this here rather than in Cluster::Merge, because this
1498 // function is only invoked once per merged Cluster, rather than once per constituent one.
1499 // This concatenation + post-linearization could be replaced with an explicit merge-sort.
1500 PostLinearize(m_depgraph, m_linearization);
1501
1502 // Sort the list of dependencies to apply by child, so those can be applied in batch.
1503 std::sort(to_apply.begin(), to_apply.end(), [](auto& a, auto& b) { return a.second < b.second; });
1504 // Iterate over groups of to-be-added dependencies with the same child.
1505 auto it = to_apply.begin();
1506 while (it != to_apply.end()) {
1507 auto& first_child = graph.m_entries[it->second].m_locator[level];
1508 const auto child_idx = first_child.index;
1509 // Iterate over all to-be-added dependencies within that same child, gather the relevant
1510 // parents.
1511 SetType parents;
1512 while (it != to_apply.end()) {
1513 auto& child = graph.m_entries[it->second].m_locator[level];
1514 auto& parent = graph.m_entries[it->first].m_locator[level];
1515 Assume(child.cluster == this && parent.cluster == this);
1516 if (child.index != child_idx) break;
1517 parents.Set(parent.index);
1518 ++it;
1519 }
1520 // Push all dependencies to the underlying DepGraph. Note that this is O(N) in the size of
1521 // the cluster, regardless of the number of parents being added, so batching them together
1522 // has a performance benefit.
1523 m_depgraph.AddDependencies(parents, child_idx);
1524 }
1525
1526 // Finally fix the linearization, as the new dependencies may have invalidated the
1527 // linearization, and post-linearize it to fix up the worst problems with it.
1528 FixLinearization(m_depgraph, m_linearization);
1529 PostLinearize(m_depgraph, m_linearization);
1530 Assume(!NeedsSplitting());
1531 Assume(!IsOversized());
1532 if (IsAcceptable()) {
1533 graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::NEEDS_RELINEARIZE);
1534 }
1535
1536 // Finally push the changes to graph.m_entries.
1537 Updated(graph, level);
1538}
1539
1540void SingletonClusterImpl::ApplyDependencies(TxGraphImpl& graph, int level, std::span<std::pair<GraphIndex, GraphIndex>> to_apply) noexcept
1541{
1542 // Nothing can actually be applied.
1543 for (auto& [par, chl] : to_apply) {
1544 Assume(par == m_graph_index);
1545 Assume(chl == m_graph_index);
1546 }
1547}
1548
1549TxGraphImpl::~TxGraphImpl() noexcept
1550{
1551 // If Refs outlive the TxGraphImpl they refer to, unlink them, so that their destructor does not
1552 // try to reach into a non-existing TxGraphImpl anymore.
1553 for (auto& entry : m_entries) {
1554 if (entry.m_ref != nullptr) {
1555 GetRefGraph(*entry.m_ref) = nullptr;
1556 }
1557 }
1558}
1559
1560std::unique_ptr<Cluster> TxGraphImpl::ExtractCluster(int level, QualityLevel quality, ClusterSetIndex setindex) noexcept
1561{
1562 Assume(quality != QualityLevel::NONE);
1563
1564 auto& clusterset = GetClusterSet(level);
1565 auto& quality_clusters = clusterset.m_clusters[int(quality)];
1566 Assume(setindex < quality_clusters.size());
1567
1568 // Extract the Cluster-owning unique_ptr.
1569 std::unique_ptr<Cluster> ret = std::move(quality_clusters[setindex]);
1570 ret->m_quality = QualityLevel::NONE;
1571 ret->m_setindex = ClusterSetIndex(-1);
1572
1573 // Clean up space in quality_cluster.
1574 auto max_setindex = quality_clusters.size() - 1;
1575 if (setindex != max_setindex) {
1576 // If the cluster was not the last element of quality_clusters, move that to take its place.
1577 quality_clusters.back()->m_setindex = setindex;
1578 quality_clusters[setindex] = std::move(quality_clusters.back());
1579 }
1580 // The last element of quality_clusters is now unused; drop it.
1581 quality_clusters.pop_back();
1582
1583 return ret;
1584}
1585
1586ClusterSetIndex TxGraphImpl::InsertCluster(int level, std::unique_ptr<Cluster>&& cluster, QualityLevel quality) noexcept
1587{
1588 // Cannot insert with quality level NONE (as that would mean not inserted).
1589 Assume(quality != QualityLevel::NONE);
1590 // The passed-in Cluster must not currently be in the TxGraphImpl.
1591 Assume(cluster->m_quality == QualityLevel::NONE);
1592
1593 // Append it at the end of the relevant TxGraphImpl::m_cluster.
1594 auto& clusterset = GetClusterSet(level);
1595 auto& quality_clusters = clusterset.m_clusters[int(quality)];
1596 ClusterSetIndex ret = quality_clusters.size();
1597 cluster->m_quality = quality;
1598 cluster->m_setindex = ret;
1599 quality_clusters.push_back(std::move(cluster));
1600 return ret;
1601}
1602
1603void TxGraphImpl::SetClusterQuality(int level, QualityLevel old_quality, ClusterSetIndex old_index, QualityLevel new_quality) noexcept
1604{
1605 Assume(new_quality != QualityLevel::NONE);
1606
1607 // Don't do anything if the quality did not change.
1608 if (old_quality == new_quality) return;
1609 // Extract the cluster from where it currently resides.
1610 auto cluster_ptr = ExtractCluster(level, old_quality, old_index);
1611 // And re-insert it where it belongs.
1612 InsertCluster(level, std::move(cluster_ptr), new_quality);
1613}
1614
1615void TxGraphImpl::DeleteCluster(Cluster& cluster, int level) noexcept
1616{
1617 // Extract the cluster from where it currently resides.
1618 auto cluster_ptr = ExtractCluster(level, cluster.m_quality, cluster.m_setindex);
1619 // And throw it away.
1620 cluster_ptr.reset();
1621}
1622
1623std::pair<Cluster*, int> TxGraphImpl::FindClusterAndLevel(GraphIndex idx, int level) const noexcept
1624{
1625 Assume(level >= 0 && level <= GetTopLevel());
1626 auto& entry = m_entries[idx];
1627 // Search the entry's locators from top to bottom.
1628 for (int l = level; l >= 0; --l) {
1629 // If the locator is missing, dig deeper; it may exist at a lower level and therefore be
1630 // implicitly existing at this level too.
1631 if (entry.m_locator[l].IsMissing()) continue;
1632 // If the locator has the entry marked as explicitly removed, stop.
1633 if (entry.m_locator[l].IsRemoved()) break;
1634 // Otherwise, we have found the topmost ClusterSet that contains this entry.
1635 return {entry.m_locator[l].cluster, l};
1636 }
1637 // If no non-empty locator was found, or an explicitly removed was hit, return nothing.
1638 return {nullptr, -1};
1639}
1640
1641Cluster* TxGraphImpl::PullIn(Cluster* cluster, int level) noexcept
1642{
1643 int to_level = GetTopLevel();
1644 Assume(to_level == 1);
1645 Assume(level <= to_level);
1646 // Copy the Cluster from main to staging, if it's not already there.
1647 if (level == 0) {
1648 // Make the Cluster Acceptable before copying. This isn't strictly necessary, but doing it
1649 // now avoids doing double work later.
1650 MakeAcceptable(*cluster, level);
1651 cluster = cluster->CopyToStaging(*this);
1652 }
1653 return cluster;
1654}
1655
1656void TxGraphImpl::ApplyRemovals(int up_to_level) noexcept
1657{
1658 Assume(up_to_level >= 0 && up_to_level <= GetTopLevel());
1659 for (int level = 0; level <= up_to_level; ++level) {
1660 auto& clusterset = GetClusterSet(level);
1661 auto& to_remove = clusterset.m_to_remove;
1662 // Skip if there is nothing to remove in this level.
1663 if (to_remove.empty()) continue;
1664 // Pull in all Clusters that are not in staging.
1665 if (level == 1) {
1666 for (GraphIndex index : to_remove) {
1667 auto [cluster, cluster_level] = FindClusterAndLevel(index, level);
1668 if (cluster != nullptr) PullIn(cluster, cluster_level);
1669 }
1670 }
1671 // Group the set of to-be-removed entries by Cluster::m_sequence.
1672 std::sort(to_remove.begin(), to_remove.end(), [&](GraphIndex a, GraphIndex b) noexcept {
1673 Cluster* cluster_a = m_entries[a].m_locator[level].cluster;
1674 Cluster* cluster_b = m_entries[b].m_locator[level].cluster;
1675 return CompareClusters(cluster_a, cluster_b) < 0;
1676 });
1677 // Process per Cluster.
1678 std::span to_remove_span{to_remove};
1679 while (!to_remove_span.empty()) {
1680 Cluster* cluster = m_entries[to_remove_span.front()].m_locator[level].cluster;
1681 if (cluster != nullptr) {
1682 // If the first to_remove_span entry's Cluster exists, hand to_remove_span to it, so it
1683 // can pop off whatever applies to it.
1684 cluster->ApplyRemovals(*this, level, to_remove_span);
1685 } else {
1686 // Otherwise, skip this already-removed entry. This may happen when
1687 // RemoveTransaction was called twice on the same Ref, for example.
1688 to_remove_span = to_remove_span.subspan(1);
1689 }
1690 }
1691 to_remove.clear();
1692 }
1693 Compact();
1694}
1695
1696void TxGraphImpl::SwapIndexes(GraphIndex a, GraphIndex b) noexcept
1697{
1698 Assume(a < m_entries.size());
1699 Assume(b < m_entries.size());
1700 // Swap the Entry objects.
1701 std::swap(m_entries[a], m_entries[b]);
1702 // Iterate over both objects.
1703 for (int i = 0; i < 2; ++i) {
1704 GraphIndex idx = i ? b : a;
1705 Entry& entry = m_entries[idx];
1706 // Update linked Ref, if any exists.
1707 if (entry.m_ref) GetRefIndex(*entry.m_ref) = idx;
1708 // Update linked chunk index entries, if any exist.
1709 if (entry.m_main_chunkindex_iterator != m_main_chunkindex.end()) {
1710 entry.m_main_chunkindex_iterator->m_graph_index = idx;
1711 }
1712 // Update the locators for both levels. The rest of the Entry information will not change,
1713 // so no need to invoke Cluster::Updated().
1714 for (int level = 0; level < MAX_LEVELS; ++level) {
1715 Locator& locator = entry.m_locator[level];
1716 if (locator.IsPresent()) {
1717 locator.cluster->UpdateMapping(locator.index, idx);
1718 }
1719 }
1720 }
1721}
1722
1723void TxGraphImpl::Compact() noexcept
1724{
1725 // We cannot compact while any to-be-applied operations or staged removals remain as we'd need
1726 // to rewrite them. It is easier to delay the compaction until they have been applied.
1727 if (!m_main_clusterset.m_deps_to_add.empty()) return;
1728 if (!m_main_clusterset.m_to_remove.empty()) return;
1729 Assume(m_main_clusterset.m_removed.empty()); // non-staging m_removed is always empty
1730 if (m_staging_clusterset.has_value()) {
1731 if (!m_staging_clusterset->m_deps_to_add.empty()) return;
1732 if (!m_staging_clusterset->m_to_remove.empty()) return;
1733 if (!m_staging_clusterset->m_removed.empty()) return;
1734 }
1735
1736 // Release memory used by discarded ChunkData index entries.
1737 ClearShrink(m_main_chunkindex_discarded);
1738
1739 // Sort the GraphIndexes that need to be cleaned up. They are sorted in reverse, so the last
1740 // ones get processed first. This means earlier-processed GraphIndexes will not cause moving of
1741 // later-processed ones during the "swap with end of m_entries" step below (which might
1742 // invalidate them).
1743 std::sort(m_unlinked.begin(), m_unlinked.end(), std::greater{});
1744
1745 auto last = GraphIndex(-1);
1746 for (GraphIndex idx : m_unlinked) {
1747 // m_unlinked should never contain the same GraphIndex twice (the code below would fail
1748 // if so, because GraphIndexes get invalidated by removing them).
1749 Assume(idx != last);
1750 last = idx;
1751
1752 // Make sure the entry is unlinked.
1753 Entry& entry = m_entries[idx];
1754 Assume(entry.m_ref == nullptr);
1755 // Make sure the entry does not occur in the graph.
1756 for (int level = 0; level < MAX_LEVELS; ++level) {
1757 Assume(!entry.m_locator[level].IsPresent());
1758 }
1759
1760 // Move the entry to the end.
1761 if (idx != m_entries.size() - 1) SwapIndexes(idx, m_entries.size() - 1);
1762 // Drop the entry for idx, now that it is at the end.
1763 m_entries.pop_back();
1764 }
1765 m_unlinked.clear();
1766}
1767
1768void TxGraphImpl::Split(Cluster& cluster, int level) noexcept
1769{
1770 // To split a Cluster, first make sure all removals are applied (as we might need to split
1771 // again afterwards otherwise).
1772 ApplyRemovals(level);
1773 bool del = cluster.Split(*this, level);
1774 if (del) {
1775 // Cluster::Split reports whether the Cluster is to be deleted.
1776 DeleteCluster(cluster, level);
1777 }
1778}
1779
1780void TxGraphImpl::SplitAll(int up_to_level) noexcept
1781{
1782 Assume(up_to_level >= 0 && up_to_level <= GetTopLevel());
1783 // Before splitting all Cluster, first make sure all removals are applied.
1784 ApplyRemovals(up_to_level);
1785 for (int level = 0; level <= up_to_level; ++level) {
1786 for (auto quality : {QualityLevel::NEEDS_SPLIT, QualityLevel::NEEDS_SPLIT_ACCEPTABLE}) {
1787 auto& queue = GetClusterSet(level).m_clusters[int(quality)];
1788 while (!queue.empty()) {
1789 Split(*queue.back().get(), level);
1790 }
1791 }
1792 }
1793}
1794
1795void TxGraphImpl::GroupClusters(int level) noexcept
1796{
1797 auto& clusterset = GetClusterSet(level);
1798 // If the groupings have been computed already, nothing is left to be done.
1799 if (clusterset.m_group_data.has_value()) return;
1800
1801 // Before computing which Clusters need to be merged together, first apply all removals and
1802 // split the Clusters into connected components. If we would group first, we might end up
1803 // with inefficient and/or oversized Clusters which just end up being split again anyway.
1804 SplitAll(level);
1805
1809 std::vector<std::pair<Cluster*, uint64_t>> an_clusters;
1814 std::vector<std::pair<std::pair<GraphIndex, GraphIndex>, uint64_t>> an_deps;
1815
1816 // Construct an an_clusters entry for every oversized cluster, including ones from levels below,
1817 // as they may be inherited in this one.
1818 for (int level_iter = 0; level_iter <= level; ++level_iter) {
1819 for (auto& cluster : GetClusterSet(level_iter).m_clusters[int(QualityLevel::OVERSIZED_SINGLETON)]) {
1820 auto graph_idx = cluster->GetClusterEntry(0);
1821 auto cur_cluster = FindCluster(graph_idx, level);
1822 if (cur_cluster == nullptr) continue;
1823 an_clusters.emplace_back(cur_cluster, cur_cluster->m_sequence);
1824 }
1825 }
1826
1827 // Construct a an_clusters entry for every parent and child in the to-be-applied dependencies,
1828 // and an an_deps entry for each dependency to be applied.
1829 an_deps.reserve(clusterset.m_deps_to_add.size());
1830 for (const auto& [par, chl] : clusterset.m_deps_to_add) {
1831 auto par_cluster = FindCluster(par, level);
1832 auto chl_cluster = FindCluster(chl, level);
1833 // Skip dependencies for which the parent or child transaction is removed.
1834 if (par_cluster == nullptr || chl_cluster == nullptr) continue;
1835 an_clusters.emplace_back(par_cluster, par_cluster->m_sequence);
1836 // Do not include a duplicate when parent and child are identical, as it'll be removed
1837 // below anyway.
1838 if (chl_cluster != par_cluster) an_clusters.emplace_back(chl_cluster, chl_cluster->m_sequence);
1839 // Add entry to an_deps, using the child sequence number.
1840 an_deps.emplace_back(std::pair{par, chl}, chl_cluster->m_sequence);
1841 }
1842 // Sort and deduplicate an_clusters, so we end up with a sorted list of all involved Clusters
1843 // to which dependencies apply, or which are oversized.
1844 std::sort(an_clusters.begin(), an_clusters.end(), [](auto& a, auto& b) noexcept { return a.second < b.second; });
1845 an_clusters.erase(std::unique(an_clusters.begin(), an_clusters.end()), an_clusters.end());
1846 // Sort an_deps by applying the same order to the involved child cluster.
1847 std::sort(an_deps.begin(), an_deps.end(), [&](auto& a, auto& b) noexcept { return a.second < b.second; });
1848
1849 // Run the union-find algorithm to to find partitions of the input Clusters which need to be
1850 // grouped together. See https://en.wikipedia.org/wiki/Disjoint-set_data_structure.
1851 {
1853 struct PartitionData
1854 {
1856 uint64_t sequence;
1861 PartitionData* parent;
1864 unsigned rank;
1865 };
1867 std::vector<PartitionData> partition_data;
1868
1870 auto locate_fn = [&](uint64_t sequence) noexcept -> PartitionData* {
1871 auto it = std::lower_bound(partition_data.begin(), partition_data.end(), sequence,
1872 [](auto& a, uint64_t seq) noexcept { return a.sequence < seq; });
1873 Assume(it != partition_data.end());
1874 Assume(it->sequence == sequence);
1875 return &*it;
1876 };
1877
1879 static constexpr auto find_root_fn = [](PartitionData* data) noexcept -> PartitionData* {
1880 while (data->parent != data) {
1881 // Replace pointers to parents with pointers to grandparents.
1882 // See https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Finding_set_representatives.
1883 auto par = data->parent;
1884 data->parent = par->parent;
1885 data = par;
1886 }
1887 return data;
1888 };
1889
1892 static constexpr auto union_fn = [](PartitionData* arg1, PartitionData* arg2) noexcept {
1893 // Find the roots of the trees, and bail out if they are already equal (which would
1894 // mean they are in the same partition already).
1895 auto rep1 = find_root_fn(arg1);
1896 auto rep2 = find_root_fn(arg2);
1897 if (rep1 == rep2) return rep1;
1898 // Pick the lower-rank root to become a child of the higher-rank one.
1899 // See https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Union_by_rank.
1900 if (rep1->rank < rep2->rank) std::swap(rep1, rep2);
1901 rep2->parent = rep1;
1902 rep1->rank += (rep1->rank == rep2->rank);
1903 return rep1;
1904 };
1905
1906 // Start by initializing every Cluster as its own singleton partition.
1907 partition_data.resize(an_clusters.size());
1908 for (size_t i = 0; i < an_clusters.size(); ++i) {
1909 partition_data[i].sequence = an_clusters[i].first->m_sequence;
1910 partition_data[i].parent = &partition_data[i];
1911 partition_data[i].rank = 0;
1912 }
1913
1914 // Run through all parent/child pairs in an_deps, and union the partitions their Clusters
1915 // are in.
1916 Cluster* last_chl_cluster{nullptr};
1917 PartitionData* last_partition{nullptr};
1918 for (const auto& [dep, _] : an_deps) {
1919 auto [par, chl] = dep;
1920 auto par_cluster = FindCluster(par, level);
1921 auto chl_cluster = FindCluster(chl, level);
1922 Assume(chl_cluster != nullptr && par_cluster != nullptr);
1923 // Nothing to do if parent and child are in the same Cluster.
1924 if (par_cluster == chl_cluster) continue;
1925 Assume(par != chl);
1926 if (chl_cluster == last_chl_cluster) {
1927 // If the child Clusters is the same as the previous iteration, union with the
1928 // tree they were in, avoiding the need for another lookup. Note that an_deps
1929 // is sorted by child Cluster, so batches with the same child are expected.
1930 last_partition = union_fn(locate_fn(par_cluster->m_sequence), last_partition);
1931 } else {
1932 last_chl_cluster = chl_cluster;
1933 last_partition = union_fn(locate_fn(par_cluster->m_sequence), locate_fn(chl_cluster->m_sequence));
1934 }
1935 }
1936
1937 // Update the sequence numbers in an_clusters and an_deps to be those of the partition
1938 // representative.
1939 auto deps_it = an_deps.begin();
1940 for (size_t i = 0; i < partition_data.size(); ++i) {
1941 auto& data = partition_data[i];
1942 // Find the sequence of the representative of the partition Cluster i is in, and store
1943 // it with the Cluster.
1944 auto rep_seq = find_root_fn(&data)->sequence;
1945 an_clusters[i].second = rep_seq;
1946 // Find all dependencies whose child Cluster is Cluster i, and annotate them with rep.
1947 while (deps_it != an_deps.end()) {
1948 auto [par, chl] = deps_it->first;
1949 auto chl_cluster = FindCluster(chl, level);
1950 Assume(chl_cluster != nullptr);
1951 if (chl_cluster->m_sequence > data.sequence) break;
1952 deps_it->second = rep_seq;
1953 ++deps_it;
1954 }
1955 }
1956 }
1957
1958 // Sort both an_clusters and an_deps by sequence number of the representative of the
1959 // partition they are in, grouping all those applying to the same partition together.
1960 std::sort(an_deps.begin(), an_deps.end(), [](auto& a, auto& b) noexcept { return a.second < b.second; });
1961 std::sort(an_clusters.begin(), an_clusters.end(), [](auto& a, auto& b) noexcept { return a.second < b.second; });
1962
1963 // Translate the resulting cluster groups to the m_group_data structure, and the dependencies
1964 // back to m_deps_to_add.
1965 clusterset.m_group_data = GroupData{};
1966 clusterset.m_group_data->m_group_clusters.reserve(an_clusters.size());
1967 clusterset.m_deps_to_add.clear();
1968 clusterset.m_deps_to_add.reserve(an_deps.size());
1969 clusterset.m_oversized = false;
1970 auto an_deps_it = an_deps.begin();
1971 auto an_clusters_it = an_clusters.begin();
1972 while (an_clusters_it != an_clusters.end()) {
1973 // Process all clusters/dependencies belonging to the partition with representative rep.
1974 auto rep = an_clusters_it->second;
1975 // Create and initialize a new GroupData entry for the partition.
1976 auto& new_entry = clusterset.m_group_data->m_groups.emplace_back();
1977 new_entry.m_cluster_offset = clusterset.m_group_data->m_group_clusters.size();
1978 new_entry.m_cluster_count = 0;
1979 new_entry.m_deps_offset = clusterset.m_deps_to_add.size();
1980 new_entry.m_deps_count = 0;
1981 uint32_t total_count{0};
1982 uint64_t total_size{0};
1983 // Add all its clusters to it (copying those from an_clusters to m_group_clusters).
1984 while (an_clusters_it != an_clusters.end() && an_clusters_it->second == rep) {
1985 clusterset.m_group_data->m_group_clusters.push_back(an_clusters_it->first);
1986 total_count += an_clusters_it->first->GetTxCount();
1987 total_size += an_clusters_it->first->GetTotalTxSize();
1988 ++an_clusters_it;
1989 ++new_entry.m_cluster_count;
1990 }
1991 // Add all its dependencies to it (copying those back from an_deps to m_deps_to_add).
1992 while (an_deps_it != an_deps.end() && an_deps_it->second == rep) {
1993 clusterset.m_deps_to_add.push_back(an_deps_it->first);
1994 ++an_deps_it;
1995 ++new_entry.m_deps_count;
1996 }
1997 // Detect oversizedness.
1998 if (total_count > m_max_cluster_count || total_size > m_max_cluster_size) {
1999 clusterset.m_oversized = true;
2000 }
2001 }
2002 Assume(an_deps_it == an_deps.end());
2003 Assume(an_clusters_it == an_clusters.end());
2004 Compact();
2005}
2006
2007void TxGraphImpl::Merge(std::span<Cluster*> to_merge, int level) noexcept
2008{
2009 Assume(!to_merge.empty());
2010 // Nothing to do if a group consists of just a single Cluster.
2011 if (to_merge.size() == 1) return;
2012
2013 // Move the largest Cluster to the front of to_merge. As all transactions in other to-be-merged
2014 // Clusters will be moved to that one, putting the largest one first minimizes the number of
2015 // moves.
2016 size_t max_size_pos{0};
2017 DepGraphIndex max_size = to_merge[max_size_pos]->GetTxCount();
2018 GetClusterSet(level).m_cluster_usage -= to_merge[max_size_pos]->TotalMemoryUsage();
2019 DepGraphIndex total_size = max_size;
2020 for (size_t i = 1; i < to_merge.size(); ++i) {
2021 GetClusterSet(level).m_cluster_usage -= to_merge[i]->TotalMemoryUsage();
2022 DepGraphIndex size = to_merge[i]->GetTxCount();
2023 total_size += size;
2024 if (size > max_size) {
2025 max_size_pos = i;
2026 max_size = size;
2027 }
2028 }
2029 if (max_size_pos != 0) std::swap(to_merge[0], to_merge[max_size_pos]);
2030
2031 size_t start_idx = 1;
2032 Cluster* into_cluster = to_merge[0];
2033 if (total_size > into_cluster->GetMaxTxCount()) {
2034 // The into_merge cluster is too small to fit all transactions being merged. Construct a
2035 // a new Cluster using an implementation that matches the total size, and merge everything
2036 // in there.
2037 auto new_cluster = CreateEmptyCluster(total_size);
2038 into_cluster = new_cluster.get();
2039 InsertCluster(level, std::move(new_cluster), QualityLevel::OPTIMAL);
2040 start_idx = 0;
2041 }
2042
2043 // Merge all further Clusters in the group into the result (first one, or new one), and delete
2044 // them.
2045 for (size_t i = start_idx; i < to_merge.size(); ++i) {
2046 into_cluster->Merge(*this, level, *to_merge[i]);
2047 DeleteCluster(*to_merge[i], level);
2048 }
2049 into_cluster->Compact();
2050 GetClusterSet(level).m_cluster_usage += into_cluster->TotalMemoryUsage();
2051}
2052
2053void TxGraphImpl::ApplyDependencies(int level) noexcept
2054{
2055 auto& clusterset = GetClusterSet(level);
2056 // Do not bother computing groups if we already know the result will be oversized.
2057 if (clusterset.m_oversized == true) return;
2058 // Compute the groups of to-be-merged Clusters (which also applies all removals, and splits).
2059 GroupClusters(level);
2060 Assume(clusterset.m_group_data.has_value());
2061 // Nothing to do if there are no dependencies to be added.
2062 if (clusterset.m_deps_to_add.empty()) return;
2063 // Dependencies cannot be applied if it would result in oversized clusters.
2064 if (clusterset.m_oversized == true) return;
2065
2066 // For each group of to-be-merged Clusters.
2067 for (const auto& group_entry : clusterset.m_group_data->m_groups) {
2068 auto cluster_span = std::span{clusterset.m_group_data->m_group_clusters}
2069 .subspan(group_entry.m_cluster_offset, group_entry.m_cluster_count);
2070 // Pull in all the Clusters that contain dependencies.
2071 if (level == 1) {
2072 for (Cluster*& cluster : cluster_span) {
2073 cluster = PullIn(cluster, cluster->GetLevel(*this));
2074 }
2075 }
2076 // Invoke Merge() to merge them into a single Cluster.
2077 Merge(cluster_span, level);
2078 // Actually apply all to-be-added dependencies (all parents and children from this grouping
2079 // belong to the same Cluster at this point because of the merging above).
2080 auto deps_span = std::span{clusterset.m_deps_to_add}
2081 .subspan(group_entry.m_deps_offset, group_entry.m_deps_count);
2082 Assume(!deps_span.empty());
2083 const auto& loc = m_entries[deps_span[0].second].m_locator[level];
2084 Assume(loc.IsPresent());
2085 loc.cluster->ApplyDependencies(*this, level, deps_span);
2086 }
2087
2088 // Wipe the list of to-be-added dependencies now that they are applied.
2089 clusterset.m_deps_to_add.clear();
2090 Compact();
2091 // Also no further Cluster mergings are needed (note that we clear, but don't set to
2092 // std::nullopt, as that would imply the groupings are unknown).
2093 clusterset.m_group_data = GroupData{};
2094}
2095
2096std::pair<uint64_t, bool> GenericClusterImpl::Relinearize(TxGraphImpl& graph, int level, uint64_t max_iters) noexcept
2097{
2098 // We can only relinearize Clusters that do not need splitting.
2099 Assume(!NeedsSplitting());
2100 // No work is required for Clusters which are already optimally linearized.
2101 if (IsOptimal()) return {0, false};
2102 // Invoke the actual linearization algorithm (passing in the existing one).
2103 uint64_t rng_seed = graph.m_rng.rand64();
2104 auto [linearization, optimal, cost] = Linearize(m_depgraph, max_iters, rng_seed, m_linearization);
2105 // Postlinearize if the result isn't optimal already. This guarantees (among other things)
2106 // that the chunks of the resulting linearization are all connected.
2107 if (!optimal) PostLinearize(m_depgraph, linearization);
2108 // Update the linearization.
2109 m_linearization = std::move(linearization);
2110 // Update the Cluster's quality.
2111 bool improved = false;
2112 if (optimal) {
2113 graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::OPTIMAL);
2114 improved = true;
2115 } else if (max_iters >= graph.m_acceptable_iters && !IsAcceptable()) {
2116 graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::ACCEPTABLE);
2117 improved = true;
2118 }
2119 // Update the Entry objects.
2120 Updated(graph, level);
2121 return {cost, improved};
2122}
2123
2124std::pair<uint64_t, bool> SingletonClusterImpl::Relinearize(TxGraphImpl& graph, int level, uint64_t max_iters) noexcept
2125{
2126 // All singletons are optimal, oversized, or need splitting. Each of these precludes
2127 // Relinearize from being called.
2128 assert(false);
2129 return {0, false};
2130}
2131
2132void TxGraphImpl::MakeAcceptable(Cluster& cluster, int level) noexcept
2133{
2134 // Relinearize the Cluster if needed.
2135 if (!cluster.NeedsSplitting() && !cluster.IsAcceptable() && !cluster.IsOversized()) {
2136 cluster.Relinearize(*this, level, m_acceptable_iters);
2137 }
2138}
2139
2140void TxGraphImpl::MakeAllAcceptable(int level) noexcept
2141{
2142 ApplyDependencies(level);
2143 auto& clusterset = GetClusterSet(level);
2144 if (clusterset.m_oversized == true) return;
2145 auto& queue = clusterset.m_clusters[int(QualityLevel::NEEDS_RELINEARIZE)];
2146 while (!queue.empty()) {
2147 MakeAcceptable(*queue.back().get(), level);
2148 }
2149}
2150
2151GenericClusterImpl::GenericClusterImpl(uint64_t sequence) noexcept : Cluster{sequence} {}
2152
2153TxGraph::Ref TxGraphImpl::AddTransaction(const FeePerWeight& feerate) noexcept
2154{
2155 Assume(m_main_chunkindex_observers == 0 || GetTopLevel() != 0);
2156 Assume(feerate.size > 0);
2157 // Construct a new Ref.
2158 Ref ret;
2159 // Construct a new Entry, and link it with the Ref.
2160 auto idx = m_entries.size();
2161 m_entries.emplace_back();
2162 auto& entry = m_entries.back();
2163 entry.m_main_chunkindex_iterator = m_main_chunkindex.end();
2164 entry.m_ref = &ret;
2165 GetRefGraph(ret) = this;
2166 GetRefIndex(ret) = idx;
2167 // Construct a new singleton Cluster (which is necessarily optimally linearized).
2168 bool oversized = uint64_t(feerate.size) > m_max_cluster_size;
2169 auto cluster = CreateEmptyCluster(1);
2170 cluster->AppendTransaction(idx, feerate);
2171 auto cluster_ptr = cluster.get();
2172 int level = GetTopLevel();
2173 auto& clusterset = GetClusterSet(level);
2174 InsertCluster(level, std::move(cluster), oversized ? QualityLevel::OVERSIZED_SINGLETON : QualityLevel::OPTIMAL);
2175 cluster_ptr->Updated(*this, level);
2176 clusterset.m_cluster_usage += cluster_ptr->TotalMemoryUsage();
2177 ++clusterset.m_txcount;
2178 // Deal with individually oversized transactions.
2179 if (oversized) {
2180 ++clusterset.m_txcount_oversized;
2181 clusterset.m_oversized = true;
2182 clusterset.m_group_data = std::nullopt;
2183 }
2184 // Return the Ref.
2185 return ret;
2186}
2187
2188void TxGraphImpl::RemoveTransaction(const Ref& arg) noexcept
2189{
2190 // Don't do anything if the Ref is empty (which may be indicative of the transaction already
2191 // having been removed).
2192 if (GetRefGraph(arg) == nullptr) return;
2193 Assume(GetRefGraph(arg) == this);
2194 Assume(m_main_chunkindex_observers == 0 || GetTopLevel() != 0);
2195 // Find the Cluster the transaction is in, and stop if it isn't in any.
2196 int level = GetTopLevel();
2197 auto cluster = FindCluster(GetRefIndex(arg), level);
2198 if (cluster == nullptr) return;
2199 // Remember that the transaction is to be removed.
2200 auto& clusterset = GetClusterSet(level);
2201 clusterset.m_to_remove.push_back(GetRefIndex(arg));
2202 // Wipe m_group_data (as it will need to be recomputed).
2203 clusterset.m_group_data.reset();
2204 if (clusterset.m_oversized == true) clusterset.m_oversized = std::nullopt;
2205}
2206
2207void TxGraphImpl::AddDependency(const Ref& parent, const Ref& child) noexcept
2208{
2209 // Don't do anything if either Ref is empty (which may be indicative of it having already been
2210 // removed).
2211 if (GetRefGraph(parent) == nullptr || GetRefGraph(child) == nullptr) return;
2212 Assume(GetRefGraph(parent) == this && GetRefGraph(child) == this);
2213 Assume(m_main_chunkindex_observers == 0 || GetTopLevel() != 0);
2214 // Don't do anything if this is a dependency on self.
2215 if (GetRefIndex(parent) == GetRefIndex(child)) return;
2216 // Find the Cluster the parent and child transaction are in, and stop if either appears to be
2217 // already removed.
2218 int level = GetTopLevel();
2219 auto par_cluster = FindCluster(GetRefIndex(parent), level);
2220 if (par_cluster == nullptr) return;
2221 auto chl_cluster = FindCluster(GetRefIndex(child), level);
2222 if (chl_cluster == nullptr) return;
2223 // Remember that this dependency is to be applied.
2224 auto& clusterset = GetClusterSet(level);
2225 clusterset.m_deps_to_add.emplace_back(GetRefIndex(parent), GetRefIndex(child));
2226 // Wipe m_group_data (as it will need to be recomputed).
2227 clusterset.m_group_data.reset();
2228 if (clusterset.m_oversized == false) clusterset.m_oversized = std::nullopt;
2229}
2230
2231bool TxGraphImpl::Exists(const Ref& arg, Level level_select) noexcept
2232{
2233 if (GetRefGraph(arg) == nullptr) return false;
2234 Assume(GetRefGraph(arg) == this);
2235 size_t level = GetSpecifiedLevel(level_select);
2236 // Make sure the transaction isn't scheduled for removal.
2237 ApplyRemovals(level);
2238 auto cluster = FindCluster(GetRefIndex(arg), level);
2239 return cluster != nullptr;
2240}
2241
2242void GenericClusterImpl::GetAncestorRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept
2243{
2245 SetType ancestors_union;
2246 // Process elements from the front of args, as long as they apply.
2247 while (!args.empty()) {
2248 if (args.front().first != this) break;
2249 ancestors_union |= m_depgraph.Ancestors(args.front().second);
2250 args = args.subspan(1);
2251 }
2252 Assume(ancestors_union.Any());
2253 // Translate all ancestors (in arbitrary order) to Refs (if they have any), and return them.
2254 for (auto idx : ancestors_union) {
2255 const auto& entry = graph.m_entries[m_mapping[idx]];
2256 Assume(entry.m_ref != nullptr);
2257 output.push_back(entry.m_ref);
2258 }
2259}
2260
2261void SingletonClusterImpl::GetAncestorRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept
2262{
2263 Assume(GetTxCount());
2264 while (!args.empty()) {
2265 if (args.front().first != this) break;
2266 args = args.subspan(1);
2267 }
2268 const auto& entry = graph.m_entries[m_graph_index];
2269 Assume(entry.m_ref != nullptr);
2270 output.push_back(entry.m_ref);
2271}
2272
2273void GenericClusterImpl::GetDescendantRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept
2274{
2276 SetType descendants_union;
2277 // Process elements from the front of args, as long as they apply.
2278 while (!args.empty()) {
2279 if (args.front().first != this) break;
2280 descendants_union |= m_depgraph.Descendants(args.front().second);
2281 args = args.subspan(1);
2282 }
2283 Assume(descendants_union.Any());
2284 // Translate all descendants (in arbitrary order) to Refs (if they have any), and return them.
2285 for (auto idx : descendants_union) {
2286 const auto& entry = graph.m_entries[m_mapping[idx]];
2287 Assume(entry.m_ref != nullptr);
2288 output.push_back(entry.m_ref);
2289 }
2290}
2291
2292void SingletonClusterImpl::GetDescendantRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept
2293{
2294 // In a singleton cluster, the ancestors or descendants are always just the entire cluster.
2295 GetAncestorRefs(graph, args, output);
2296}
2297
2298bool GenericClusterImpl::GetClusterRefs(TxGraphImpl& graph, std::span<TxGraph::Ref*> range, LinearizationIndex start_pos) noexcept
2299{
2300 // Translate the transactions in the Cluster (in linearization order, starting at start_pos in
2301 // the linearization) to Refs, and fill them in range.
2302 for (auto& ref : range) {
2303 Assume(start_pos < m_linearization.size());
2304 const auto& entry = graph.m_entries[m_mapping[m_linearization[start_pos++]]];
2305 Assume(entry.m_ref != nullptr);
2306 ref = entry.m_ref;
2307 }
2308 // Return whether start_pos has advanced to the end of the Cluster.
2309 return start_pos == m_linearization.size();
2310}
2311
2312bool SingletonClusterImpl::GetClusterRefs(TxGraphImpl& graph, std::span<TxGraph::Ref*> range, LinearizationIndex start_pos) noexcept
2313{
2314 Assume(!range.empty());
2315 Assume(GetTxCount());
2316 Assume(start_pos == 0);
2317 const auto& entry = graph.m_entries[m_graph_index];
2318 Assume(entry.m_ref != nullptr);
2319 range[0] = entry.m_ref;
2320 return true;
2321}
2322
2323FeePerWeight GenericClusterImpl::GetIndividualFeerate(DepGraphIndex idx) noexcept
2324{
2325 return FeePerWeight::FromFeeFrac(m_depgraph.FeeRate(idx));
2326}
2327
2328FeePerWeight SingletonClusterImpl::GetIndividualFeerate(DepGraphIndex idx) noexcept
2329{
2330 Assume(GetTxCount());
2331 Assume(idx == 0);
2332 return m_feerate;
2333}
2334
2335void GenericClusterImpl::MakeStagingTransactionsMissing(TxGraphImpl& graph) noexcept
2336{
2337 // Mark all transactions of a Cluster missing, needed when aborting staging, so that the
2338 // corresponding Locators don't retain references into aborted Clusters.
2339 for (auto ci : m_linearization) {
2340 GraphIndex idx = m_mapping[ci];
2341 auto& entry = graph.m_entries[idx];
2342 entry.m_locator[1].SetMissing();
2343 }
2344}
2345
2346void SingletonClusterImpl::MakeStagingTransactionsMissing(TxGraphImpl& graph) noexcept
2347{
2348 if (GetTxCount()) {
2349 auto& entry = graph.m_entries[m_graph_index];
2350 entry.m_locator[1].SetMissing();
2351 }
2352}
2353
2354std::vector<TxGraph::Ref*> TxGraphImpl::GetAncestors(const Ref& arg, Level level_select) noexcept
2355{
2356 // Return the empty vector if the Ref is empty.
2357 if (GetRefGraph(arg) == nullptr) return {};
2358 Assume(GetRefGraph(arg) == this);
2359 // Apply all removals and dependencies, as the result might be incorrect otherwise.
2360 size_t level = GetSpecifiedLevel(level_select);
2361 ApplyDependencies(level);
2362 // Ancestry cannot be known if unapplied dependencies remain.
2363 Assume(GetClusterSet(level).m_deps_to_add.empty());
2364 // Find the Cluster the argument is in, and return the empty vector if it isn't in any.
2365 auto [cluster, cluster_level] = FindClusterAndLevel(GetRefIndex(arg), level);
2366 if (cluster == nullptr) return {};
2367 // Dispatch to the Cluster.
2368 std::pair<Cluster*, DepGraphIndex> match = {cluster, m_entries[GetRefIndex(arg)].m_locator[cluster_level].index};
2369 auto matches = std::span(&match, 1);
2370 std::vector<TxGraph::Ref*> ret;
2371 cluster->GetAncestorRefs(*this, matches, ret);
2372 return ret;
2373}
2374
2375std::vector<TxGraph::Ref*> TxGraphImpl::GetDescendants(const Ref& arg, Level level_select) noexcept
2376{
2377 // Return the empty vector if the Ref is empty.
2378 if (GetRefGraph(arg) == nullptr) return {};
2379 Assume(GetRefGraph(arg) == this);
2380 // Apply all removals and dependencies, as the result might be incorrect otherwise.
2381 size_t level = GetSpecifiedLevel(level_select);
2382 ApplyDependencies(level);
2383 // Ancestry cannot be known if unapplied dependencies remain.
2384 Assume(GetClusterSet(level).m_deps_to_add.empty());
2385 // Find the Cluster the argument is in, and return the empty vector if it isn't in any.
2386 auto [cluster, cluster_level] = FindClusterAndLevel(GetRefIndex(arg), level);
2387 if (cluster == nullptr) return {};
2388 // Dispatch to the Cluster.
2389 std::pair<Cluster*, DepGraphIndex> match = {cluster, m_entries[GetRefIndex(arg)].m_locator[cluster_level].index};
2390 auto matches = std::span(&match, 1);
2391 std::vector<TxGraph::Ref*> ret;
2392 cluster->GetDescendantRefs(*this, matches, ret);
2393 return ret;
2394}
2395
2396std::vector<TxGraph::Ref*> TxGraphImpl::GetAncestorsUnion(std::span<const Ref* const> args, Level level_select) noexcept
2397{
2398 // Apply all dependencies, as the result might be incorrect otherwise.
2399 size_t level = GetSpecifiedLevel(level_select);
2400 ApplyDependencies(level);
2401 // Ancestry cannot be known if unapplied dependencies remain.
2402 Assume(GetClusterSet(level).m_deps_to_add.empty());
2403
2404 // Translate args to matches.
2405 std::vector<std::pair<Cluster*, DepGraphIndex>> matches;
2406 matches.reserve(args.size());
2407 for (auto arg : args) {
2408 Assume(arg);
2409 // Skip empty Refs.
2410 if (GetRefGraph(*arg) == nullptr) continue;
2411 Assume(GetRefGraph(*arg) == this);
2412 // Find the Cluster the argument is in, and skip if none is found.
2413 auto [cluster, cluster_level] = FindClusterAndLevel(GetRefIndex(*arg), level);
2414 if (cluster == nullptr) continue;
2415 // Append to matches.
2416 matches.emplace_back(cluster, m_entries[GetRefIndex(*arg)].m_locator[cluster_level].index);
2417 }
2418 // Group by Cluster.
2419 std::sort(matches.begin(), matches.end(), [](auto& a, auto& b) noexcept { return CompareClusters(a.first, b.first) < 0; });
2420 // Dispatch to the Clusters.
2421 std::span match_span(matches);
2422 std::vector<TxGraph::Ref*> ret;
2423 while (!match_span.empty()) {
2424 match_span.front().first->GetAncestorRefs(*this, match_span, ret);
2425 }
2426 return ret;
2427}
2428
2429std::vector<TxGraph::Ref*> TxGraphImpl::GetDescendantsUnion(std::span<const Ref* const> args, Level level_select) noexcept
2430{
2431 // Apply all dependencies, as the result might be incorrect otherwise.
2432 size_t level = GetSpecifiedLevel(level_select);
2433 ApplyDependencies(level);
2434 // Ancestry cannot be known if unapplied dependencies remain.
2435 Assume(GetClusterSet(level).m_deps_to_add.empty());
2436
2437 // Translate args to matches.
2438 std::vector<std::pair<Cluster*, DepGraphIndex>> matches;
2439 matches.reserve(args.size());
2440 for (auto arg : args) {
2441 Assume(arg);
2442 // Skip empty Refs.
2443 if (GetRefGraph(*arg) == nullptr) continue;
2444 Assume(GetRefGraph(*arg) == this);
2445 // Find the Cluster the argument is in, and skip if none is found.
2446 auto [cluster, cluster_level] = FindClusterAndLevel(GetRefIndex(*arg), level);
2447 if (cluster == nullptr) continue;
2448 // Append to matches.
2449 matches.emplace_back(cluster, m_entries[GetRefIndex(*arg)].m_locator[cluster_level].index);
2450 }
2451 // Group by Cluster.
2452 std::sort(matches.begin(), matches.end(), [](auto& a, auto& b) noexcept { return CompareClusters(a.first, b.first) < 0; });
2453 // Dispatch to the Clusters.
2454 std::span match_span(matches);
2455 std::vector<TxGraph::Ref*> ret;
2456 while (!match_span.empty()) {
2457 match_span.front().first->GetDescendantRefs(*this, match_span, ret);
2458 }
2459 return ret;
2460}
2461
2462std::vector<TxGraph::Ref*> TxGraphImpl::GetCluster(const Ref& arg, Level level_select) noexcept
2463{
2464 // Return the empty vector if the Ref is empty (which may be indicative of the transaction
2465 // having been removed already.
2466 if (GetRefGraph(arg) == nullptr) return {};
2467 Assume(GetRefGraph(arg) == this);
2468 // Apply all removals and dependencies, as the result might be incorrect otherwise.
2469 size_t level = GetSpecifiedLevel(level_select);
2470 ApplyDependencies(level);
2471 // Cluster linearization cannot be known if unapplied dependencies remain.
2472 Assume(GetClusterSet(level).m_deps_to_add.empty());
2473 // Find the Cluster the argument is in, and return the empty vector if it isn't in any.
2474 auto [cluster, cluster_level] = FindClusterAndLevel(GetRefIndex(arg), level);
2475 if (cluster == nullptr) return {};
2476 // Make sure the Cluster has an acceptable quality level, and then dispatch to it.
2477 MakeAcceptable(*cluster, cluster_level);
2478 std::vector<TxGraph::Ref*> ret(cluster->GetTxCount());
2479 cluster->GetClusterRefs(*this, ret, 0);
2480 return ret;
2481}
2482
2483TxGraph::GraphIndex TxGraphImpl::GetTransactionCount(Level level_select) noexcept
2484{
2485 size_t level = GetSpecifiedLevel(level_select);
2486 ApplyRemovals(level);
2487 return GetClusterSet(level).m_txcount;
2488}
2489
2490FeePerWeight TxGraphImpl::GetIndividualFeerate(const Ref& arg) noexcept
2491{
2492 // Return the empty FeePerWeight if the passed Ref is empty.
2493 if (GetRefGraph(arg) == nullptr) return {};
2494 Assume(GetRefGraph(arg) == this);
2495 // Find the cluster the argument is in (the level does not matter as individual feerates will
2496 // be identical if it occurs in both), and return the empty FeePerWeight if it isn't in any.
2497 Cluster* cluster{nullptr};
2498 int level;
2499 for (level = 0; level <= GetTopLevel(); ++level) {
2500 // Apply removals, so that we can correctly report FeePerWeight{} for non-existing
2501 // transactions.
2502 ApplyRemovals(level);
2503 if (m_entries[GetRefIndex(arg)].m_locator[level].IsPresent()) {
2504 cluster = m_entries[GetRefIndex(arg)].m_locator[level].cluster;
2505 break;
2506 }
2507 }
2508 if (cluster == nullptr) return {};
2509 // Dispatch to the Cluster.
2510 return cluster->GetIndividualFeerate(m_entries[GetRefIndex(arg)].m_locator[level].index);
2511}
2512
2513FeePerWeight TxGraphImpl::GetMainChunkFeerate(const Ref& arg) noexcept
2514{
2515 // Return the empty FeePerWeight if the passed Ref is empty.
2516 if (GetRefGraph(arg) == nullptr) return {};
2517 Assume(GetRefGraph(arg) == this);
2518 // Apply all removals and dependencies, as the result might be inaccurate otherwise.
2519 ApplyDependencies(/*level=*/0);
2520 // Chunk feerates cannot be accurately known if unapplied dependencies remain.
2521 Assume(m_main_clusterset.m_deps_to_add.empty());
2522 // Find the cluster the argument is in, and return the empty FeePerWeight if it isn't in any.
2523 auto [cluster, cluster_level] = FindClusterAndLevel(GetRefIndex(arg), /*level=*/0);
2524 if (cluster == nullptr) return {};
2525 // Make sure the Cluster has an acceptable quality level, and then return the transaction's
2526 // chunk feerate.
2527 MakeAcceptable(*cluster, cluster_level);
2528 const auto& entry = m_entries[GetRefIndex(arg)];
2529 return entry.m_main_chunk_feerate;
2530}
2531
2532bool TxGraphImpl::IsOversized(Level level_select) noexcept
2533{
2534 size_t level = GetSpecifiedLevel(level_select);
2535 auto& clusterset = GetClusterSet(level);
2536 if (clusterset.m_oversized.has_value()) {
2537 // Return cached value if known.
2538 return *clusterset.m_oversized;
2539 }
2540 ApplyRemovals(level);
2541 if (clusterset.m_txcount_oversized > 0) {
2542 clusterset.m_oversized = true;
2543 } else {
2544 // Find which Clusters will need to be merged together, as that is where the oversize
2545 // property is assessed.
2546 GroupClusters(level);
2547 }
2548 Assume(clusterset.m_oversized.has_value());
2549 return *clusterset.m_oversized;
2550}
2551
2552void TxGraphImpl::StartStaging() noexcept
2553{
2554 // Staging cannot already exist.
2555 Assume(!m_staging_clusterset.has_value());
2556 // Apply all remaining dependencies in main before creating a staging graph. Once staging
2557 // exists, we cannot merge Clusters anymore (because of interference with Clusters being
2558 // pulled into staging), so to make sure all inspectors are available (if not oversized), do
2559 // all merging work now. Call SplitAll() first, so that even if ApplyDependencies does not do
2560 // any thing due to knowing the result is oversized, splitting is still performed.
2561 SplitAll(0);
2562 ApplyDependencies(0);
2563 // Construct the staging ClusterSet.
2564 m_staging_clusterset.emplace();
2565 // Copy statistics, precomputed data, and to-be-applied dependencies (only if oversized) to
2566 // the new graph. To-be-applied removals will always be empty at this point.
2567 m_staging_clusterset->m_txcount = m_main_clusterset.m_txcount;
2568 m_staging_clusterset->m_txcount_oversized = m_main_clusterset.m_txcount_oversized;
2569 m_staging_clusterset->m_deps_to_add = m_main_clusterset.m_deps_to_add;
2570 m_staging_clusterset->m_group_data = m_main_clusterset.m_group_data;
2571 m_staging_clusterset->m_oversized = m_main_clusterset.m_oversized;
2572 Assume(m_staging_clusterset->m_oversized.has_value());
2573 m_staging_clusterset->m_cluster_usage = 0;
2574}
2575
2576void TxGraphImpl::AbortStaging() noexcept
2577{
2578 // Staging must exist.
2579 Assume(m_staging_clusterset.has_value());
2580 // Mark all removed transactions as Missing (so the staging locator for these transactions
2581 // can be reused if another staging is created).
2582 for (auto idx : m_staging_clusterset->m_removed) {
2583 m_entries[idx].m_locator[1].SetMissing();
2584 }
2585 // Do the same with the non-removed transactions in staging Clusters.
2586 for (int quality = 0; quality < int(QualityLevel::NONE); ++quality) {
2587 for (auto& cluster : m_staging_clusterset->m_clusters[quality]) {
2588 cluster->MakeStagingTransactionsMissing(*this);
2589 }
2590 }
2591 // Destroy the staging ClusterSet.
2592 m_staging_clusterset.reset();
2593 Compact();
2594 if (!m_main_clusterset.m_group_data.has_value()) {
2595 // In case m_oversized in main was kept after a Ref destruction while staging exists, we
2596 // need to re-evaluate m_oversized now.
2597 if (m_main_clusterset.m_to_remove.empty() && m_main_clusterset.m_txcount_oversized > 0) {
2598 // It is possible that a Ref destruction caused a removal in main while staging existed.
2599 // In this case, m_txcount_oversized may be inaccurate.
2600 m_main_clusterset.m_oversized = true;
2601 } else {
2602 m_main_clusterset.m_oversized = std::nullopt;
2603 }
2604 }
2605}
2606
2607void TxGraphImpl::CommitStaging() noexcept
2608{
2609 // Staging must exist.
2610 Assume(m_staging_clusterset.has_value());
2611 Assume(m_main_chunkindex_observers == 0);
2612 // Delete all conflicting Clusters in main, to make place for moving the staging ones
2613 // there. All of these have been copied to staging in PullIn().
2614 auto conflicts = GetConflicts();
2615 for (Cluster* conflict : conflicts) {
2616 conflict->Clear(*this, /*level=*/0);
2617 DeleteCluster(*conflict, /*level=*/0);
2618 }
2619 // Mark the removed transactions as Missing (so the staging locator for these transactions
2620 // can be reused if another staging is created).
2621 for (auto idx : m_staging_clusterset->m_removed) {
2622 m_entries[idx].m_locator[1].SetMissing();
2623 }
2624 // Then move all Clusters in staging to main.
2625 for (int quality = 0; quality < int(QualityLevel::NONE); ++quality) {
2626 auto& stage_sets = m_staging_clusterset->m_clusters[quality];
2627 while (!stage_sets.empty()) {
2628 stage_sets.back()->MoveToMain(*this);
2629 }
2630 }
2631 // Move all statistics, precomputed data, and to-be-applied removals and dependencies.
2632 m_main_clusterset.m_deps_to_add = std::move(m_staging_clusterset->m_deps_to_add);
2633 m_main_clusterset.m_to_remove = std::move(m_staging_clusterset->m_to_remove);
2634 m_main_clusterset.m_group_data = std::move(m_staging_clusterset->m_group_data);
2635 m_main_clusterset.m_oversized = std::move(m_staging_clusterset->m_oversized);
2636 m_main_clusterset.m_txcount = std::move(m_staging_clusterset->m_txcount);
2637 m_main_clusterset.m_txcount_oversized = std::move(m_staging_clusterset->m_txcount_oversized);
2638 // Delete the old staging graph, after all its information was moved to main.
2639 m_staging_clusterset.reset();
2640 Compact();
2641}
2642
2643void GenericClusterImpl::SetFee(TxGraphImpl& graph, int level, DepGraphIndex idx, int64_t fee) noexcept
2644{
2645 // Make sure the specified DepGraphIndex exists in this Cluster.
2646 Assume(m_depgraph.Positions()[idx]);
2647 // Bail out if the fee isn't actually being changed.
2648 if (m_depgraph.FeeRate(idx).fee == fee) return;
2649 // Update the fee, remember that relinearization will be necessary, and update the Entries
2650 // in the same Cluster.
2651 m_depgraph.FeeRate(idx).fee = fee;
2652 if (m_quality == QualityLevel::OVERSIZED_SINGLETON) {
2653 // Nothing to do.
2654 } else if (!NeedsSplitting()) {
2655 graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::NEEDS_RELINEARIZE);
2656 } else {
2657 graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::NEEDS_SPLIT);
2658 }
2659 Updated(graph, level);
2660}
2661
2662void SingletonClusterImpl::SetFee(TxGraphImpl& graph, int level, DepGraphIndex idx, int64_t fee) noexcept
2663{
2664 Assume(GetTxCount());
2665 Assume(idx == 0);
2666 m_feerate.fee = fee;
2667 Updated(graph, level);
2668}
2669
2670void TxGraphImpl::SetTransactionFee(const Ref& ref, int64_t fee) noexcept
2671{
2672 // Don't do anything if the passed Ref is empty.
2673 if (GetRefGraph(ref) == nullptr) return;
2674 Assume(GetRefGraph(ref) == this);
2675 Assume(m_main_chunkindex_observers == 0);
2676 // Find the entry, its locator, and inform its Cluster about the new feerate, if any.
2677 auto& entry = m_entries[GetRefIndex(ref)];
2678 for (int level = 0; level < MAX_LEVELS; ++level) {
2679 auto& locator = entry.m_locator[level];
2680 if (locator.IsPresent()) {
2681 locator.cluster->SetFee(*this, level, locator.index, fee);
2682 }
2683 }
2684}
2685
2686std::strong_ordering TxGraphImpl::CompareMainOrder(const Ref& a, const Ref& b) noexcept
2687{
2688 // The references must not be empty.
2689 Assume(GetRefGraph(a) == this);
2690 Assume(GetRefGraph(b) == this);
2691 // Apply dependencies in main.
2692 ApplyDependencies(0);
2693 Assume(m_main_clusterset.m_deps_to_add.empty());
2694 // Make both involved Clusters acceptable, so chunk feerates are relevant.
2695 const auto& entry_a = m_entries[GetRefIndex(a)];
2696 const auto& entry_b = m_entries[GetRefIndex(b)];
2697 const auto& locator_a = entry_a.m_locator[0];
2698 const auto& locator_b = entry_b.m_locator[0];
2699 Assume(locator_a.IsPresent());
2700 Assume(locator_b.IsPresent());
2701 MakeAcceptable(*locator_a.cluster, /*level=*/0);
2702 MakeAcceptable(*locator_b.cluster, /*level=*/0);
2703 // Invoke comparison logic.
2704 return CompareMainTransactions(GetRefIndex(a), GetRefIndex(b));
2705}
2706
2707TxGraph::GraphIndex TxGraphImpl::CountDistinctClusters(std::span<const Ref* const> refs, Level level_select) noexcept
2708{
2709 size_t level = GetSpecifiedLevel(level_select);
2710 ApplyDependencies(level);
2711 auto& clusterset = GetClusterSet(level);
2712 Assume(clusterset.m_deps_to_add.empty());
2713 // Build a vector of Clusters that the specified Refs occur in.
2714 std::vector<Cluster*> clusters;
2715 clusters.reserve(refs.size());
2716 for (const Ref* ref : refs) {
2717 Assume(ref);
2718 if (GetRefGraph(*ref) == nullptr) continue;
2719 Assume(GetRefGraph(*ref) == this);
2720 auto cluster = FindCluster(GetRefIndex(*ref), level);
2721 if (cluster != nullptr) clusters.push_back(cluster);
2722 }
2723 // Count the number of distinct elements in clusters.
2724 std::sort(clusters.begin(), clusters.end(), [](Cluster* a, Cluster* b) noexcept { return CompareClusters(a, b) < 0; });
2725 Cluster* last{nullptr};
2726 GraphIndex ret{0};
2727 for (Cluster* cluster : clusters) {
2728 ret += (cluster != last);
2729 last = cluster;
2730 }
2731 return ret;
2732}
2733
2734std::pair<std::vector<FeeFrac>, std::vector<FeeFrac>> TxGraphImpl::GetMainStagingDiagrams() noexcept
2735{
2736 Assume(m_staging_clusterset.has_value());
2737 MakeAllAcceptable(0);
2738 Assume(m_main_clusterset.m_deps_to_add.empty()); // can only fail if main is oversized
2739 MakeAllAcceptable(1);
2740 Assume(m_staging_clusterset->m_deps_to_add.empty()); // can only fail if staging is oversized
2741 // For all Clusters in main which conflict with Clusters in staging (i.e., all that are removed
2742 // by, or replaced in, staging), gather their chunk feerates.
2743 auto main_clusters = GetConflicts();
2744 std::vector<FeeFrac> main_feerates, staging_feerates;
2745 for (Cluster* cluster : main_clusters) {
2746 cluster->AppendChunkFeerates(main_feerates);
2747 }
2748 // Do the same for the Clusters in staging themselves.
2749 for (int quality = 0; quality < int(QualityLevel::NONE); ++quality) {
2750 for (const auto& cluster : m_staging_clusterset->m_clusters[quality]) {
2751 cluster->AppendChunkFeerates(staging_feerates);
2752 }
2753 }
2754 // Sort both by decreasing feerate to obtain diagrams, and return them.
2755 std::sort(main_feerates.begin(), main_feerates.end(), [](auto& a, auto& b) { return a > b; });
2756 std::sort(staging_feerates.begin(), staging_feerates.end(), [](auto& a, auto& b) { return a > b; });
2757 return std::make_pair(std::move(main_feerates), std::move(staging_feerates));
2758}
2759
2760void GenericClusterImpl::SanityCheck(const TxGraphImpl& graph, int level) const
2761{
2762 // There must be an m_mapping for each m_depgraph position (including holes).
2763 assert(m_depgraph.PositionRange() == m_mapping.size());
2764 // The linearization for this Cluster must contain every transaction once.
2765 assert(m_depgraph.TxCount() == m_linearization.size());
2766 // Unless a split is to be applied, the cluster cannot have any holes.
2767 if (!NeedsSplitting()) {
2768 assert(m_depgraph.Positions() == SetType::Fill(m_depgraph.TxCount()));
2769 }
2770
2771 // Compute the chunking of m_linearization.
2772 LinearizationChunking linchunking(m_depgraph, m_linearization);
2773
2774 // Verify m_linearization.
2775 SetType m_done;
2776 LinearizationIndex linindex{0};
2777 DepGraphIndex chunk_pos{0};
2778 assert(m_depgraph.IsAcyclic());
2779 for (auto lin_pos : m_linearization) {
2780 assert(lin_pos < m_mapping.size());
2781 const auto& entry = graph.m_entries[m_mapping[lin_pos]];
2782 // Check that the linearization is topological.
2783 m_done.Set(lin_pos);
2784 assert(m_done.IsSupersetOf(m_depgraph.Ancestors(lin_pos)));
2785 // Check that the Entry has a locator pointing back to this Cluster & position within it.
2786 assert(entry.m_locator[level].cluster == this);
2787 assert(entry.m_locator[level].index == lin_pos);
2788 // For main-level entries, check linearization position and chunk feerate.
2789 if (level == 0 && IsAcceptable()) {
2790 assert(entry.m_main_lin_index == linindex);
2791 ++linindex;
2792 if (!linchunking.GetChunk(0).transactions[lin_pos]) {
2793 linchunking.MarkDone(linchunking.GetChunk(0).transactions);
2794 chunk_pos = 0;
2795 }
2796 assert(entry.m_main_chunk_feerate == linchunking.GetChunk(0).feerate);
2797 // Verify that an entry in the chunk index exists for every chunk-ending transaction.
2798 ++chunk_pos;
2799 bool is_chunk_end = (chunk_pos == linchunking.GetChunk(0).transactions.Count());
2800 assert((entry.m_main_chunkindex_iterator != graph.m_main_chunkindex.end()) == is_chunk_end);
2801 if (is_chunk_end) {
2802 auto& chunk_data = *entry.m_main_chunkindex_iterator;
2803 if (m_done == m_depgraph.Positions() && chunk_pos == 1) {
2804 assert(chunk_data.m_chunk_count == LinearizationIndex(-1));
2805 } else {
2806 assert(chunk_data.m_chunk_count == chunk_pos);
2807 }
2808 }
2809 // If this Cluster has an acceptable quality level, its chunks must be connected.
2810 assert(m_depgraph.IsConnected(linchunking.GetChunk(0).transactions));
2811 }
2812 }
2813 // Verify that each element of m_depgraph occurred in m_linearization.
2814 assert(m_done == m_depgraph.Positions());
2815}
2816
2817void SingletonClusterImpl::SanityCheck(const TxGraphImpl& graph, int level) const
2818{
2819 // All singletons are optimal, oversized, or need splitting.
2820 Assume(IsOptimal() || IsOversized() || NeedsSplitting());
2821 if (GetTxCount()) {
2822 const auto& entry = graph.m_entries[m_graph_index];
2823 // Check that the Entry has a locator pointing back to this Cluster & position within it.
2824 assert(entry.m_locator[level].cluster == this);
2825 assert(entry.m_locator[level].index == 0);
2826 // For main-level entries, check linearization position and chunk feerate.
2827 if (level == 0 && IsAcceptable()) {
2828 assert(entry.m_main_lin_index == 0);
2829 assert(entry.m_main_chunk_feerate == m_feerate);
2830 assert(entry.m_main_chunkindex_iterator != graph.m_main_chunkindex.end());
2831 auto& chunk_data = *entry.m_main_chunkindex_iterator;
2832 assert(chunk_data.m_chunk_count == LinearizationIndex(-1));
2833 }
2834 }
2835}
2836
2837void TxGraphImpl::SanityCheck() const
2838{
2840 std::set<GraphIndex> expected_unlinked;
2842 std::set<const Cluster*> expected_clusters[MAX_LEVELS];
2844 std::set<GraphIndex> expected_removed[MAX_LEVELS];
2846 std::set<uint64_t> sequences;
2848 std::set<GraphIndex> expected_chunkindex;
2850 bool compact_possible{true};
2851
2852 // Go over all Entry objects in m_entries.
2853 for (GraphIndex idx = 0; idx < m_entries.size(); ++idx) {
2854 const auto& entry = m_entries[idx];
2855 if (entry.m_ref == nullptr) {
2856 // Unlinked Entry must have indexes appear in m_unlinked.
2857 expected_unlinked.insert(idx);
2858 } else {
2859 // Every non-unlinked Entry must have a Ref that points back to it.
2860 assert(GetRefGraph(*entry.m_ref) == this);
2861 assert(GetRefIndex(*entry.m_ref) == idx);
2862 }
2863 if (entry.m_main_chunkindex_iterator != m_main_chunkindex.end()) {
2864 // Remember which entries we see a chunkindex entry for.
2865 assert(entry.m_locator[0].IsPresent());
2866 expected_chunkindex.insert(idx);
2867 }
2868 // Verify the Entry m_locators.
2869 bool was_present{false}, was_removed{false};
2870 for (int level = 0; level < MAX_LEVELS; ++level) {
2871 const auto& locator = entry.m_locator[level];
2872 // Every Locator must be in exactly one of these 3 states.
2873 assert(locator.IsMissing() + locator.IsRemoved() + locator.IsPresent() == 1);
2874 if (locator.IsPresent()) {
2875 // Once removed, a transaction cannot be revived.
2876 assert(!was_removed);
2877 // Verify that the Cluster agrees with where the Locator claims the transaction is.
2878 assert(locator.cluster->GetClusterEntry(locator.index) == idx);
2879 // Remember that we expect said Cluster to appear in the ClusterSet::m_clusters.
2880 expected_clusters[level].insert(locator.cluster);
2881 was_present = true;
2882 } else if (locator.IsRemoved()) {
2883 // Level 0 (main) cannot have IsRemoved locators (IsMissing there means non-existing).
2884 assert(level > 0);
2885 // A Locator can only be IsRemoved if it was IsPresent before, and only once.
2886 assert(was_present && !was_removed);
2887 // Remember that we expect this GraphIndex to occur in the ClusterSet::m_removed.
2888 expected_removed[level].insert(idx);
2889 was_removed = true;
2890 }
2891 }
2892 }
2893
2894 // For all levels (0 = main, 1 = staged)...
2895 for (int level = 0; level <= GetTopLevel(); ++level) {
2896 assert(level < MAX_LEVELS);
2897 auto& clusterset = GetClusterSet(level);
2898 std::set<const Cluster*> actual_clusters;
2899 size_t recomputed_cluster_usage{0};
2900
2901 // For all quality levels...
2902 for (int qual = 0; qual < int(QualityLevel::NONE); ++qual) {
2903 QualityLevel quality{qual};
2904 const auto& quality_clusters = clusterset.m_clusters[qual];
2905 // ... for all clusters in them ...
2906 for (ClusterSetIndex setindex = 0; setindex < quality_clusters.size(); ++setindex) {
2907 const auto& cluster = *quality_clusters[setindex];
2908 // The number of transactions in a Cluster cannot exceed m_max_cluster_count.
2909 assert(cluster.GetTxCount() <= m_max_cluster_count);
2910 // The level must match the Cluster's own idea of what level it is in (but GetLevel
2911 // can only be called for non-empty Clusters).
2912 assert(cluster.GetTxCount() == 0 || level == cluster.GetLevel(*this));
2913 // The sum of their sizes cannot exceed m_max_cluster_size, unless it is an
2914 // individually oversized transaction singleton. Note that groups of to-be-merged
2915 // clusters which would exceed this limit are marked oversized, which means they
2916 // are never applied.
2917 assert(cluster.IsOversized() || cluster.GetTotalTxSize() <= m_max_cluster_size);
2918 // OVERSIZED clusters are singletons.
2919 assert(!cluster.IsOversized() || cluster.GetTxCount() == 1);
2920 // Transaction counts cannot exceed the Cluster implementation's maximum
2921 // supported transactions count.
2922 assert(cluster.GetTxCount() <= cluster.GetMaxTxCount());
2923 // Unless a Split is yet to be applied, the number of transactions must not be
2924 // below the Cluster implementation's intended transaction count.
2925 if (!cluster.NeedsSplitting()) {
2926 assert(cluster.GetTxCount() >= cluster.GetMinIntendedTxCount());
2927 }
2928
2929 // Check the sequence number.
2930 assert(cluster.m_sequence < m_next_sequence_counter);
2931 assert(sequences.count(cluster.m_sequence) == 0);
2932 sequences.insert(cluster.m_sequence);
2933 // Remember we saw this Cluster (only if it is non-empty; empty Clusters aren't
2934 // expected to be referenced by the Entry vector).
2935 if (cluster.GetTxCount() != 0) {
2936 actual_clusters.insert(&cluster);
2937 }
2938 // Sanity check the cluster, according to the Cluster's internal rules.
2939 cluster.SanityCheck(*this, level);
2940 // Check that the cluster's quality and setindex matches its position in the quality list.
2941 assert(cluster.m_quality == quality);
2942 assert(cluster.m_setindex == setindex);
2943 // Count memory usage.
2944 recomputed_cluster_usage += cluster.TotalMemoryUsage();
2945 }
2946 }
2947
2948 // Verify memory usage.
2949 assert(clusterset.m_cluster_usage == recomputed_cluster_usage);
2950
2951 // Verify that all to-be-removed transactions have valid identifiers.
2952 for (GraphIndex idx : clusterset.m_to_remove) {
2953 assert(idx < m_entries.size());
2954 // We cannot assert that all m_to_remove transactions are still present: ~Ref on a
2955 // (P,M) transaction (present in main, inherited in staging) will cause an m_to_remove
2956 // addition in both main and staging, but a subsequence ApplyRemovals in main will
2957 // cause it to disappear from staging too, leaving the m_to_remove in place.
2958 }
2959
2960 // Verify that all to-be-added dependencies have valid identifiers.
2961 for (auto [par_idx, chl_idx] : clusterset.m_deps_to_add) {
2962 assert(par_idx != chl_idx);
2963 assert(par_idx < m_entries.size());
2964 assert(chl_idx < m_entries.size());
2965 }
2966
2967 // Verify that the actually encountered clusters match the ones occurring in Entry vector.
2968 assert(actual_clusters == expected_clusters[level]);
2969
2970 // Verify that the contents of m_removed matches what was expected based on the Entry vector.
2971 std::set<GraphIndex> actual_removed(clusterset.m_removed.begin(), clusterset.m_removed.end());
2972 for (auto i : expected_unlinked) {
2973 // If a transaction exists in both main and staging, and is removed from staging (adding
2974 // it to m_removed there), and consequently destroyed (wiping the locator completely),
2975 // it can remain in m_removed despite not having an IsRemoved() locator. Exclude those
2976 // transactions from the comparison here.
2977 actual_removed.erase(i);
2978 expected_removed[level].erase(i);
2979 }
2980
2981 assert(actual_removed == expected_removed[level]);
2982
2983 // If any GraphIndex entries remain in this ClusterSet, compact is not possible.
2984 if (!clusterset.m_deps_to_add.empty()) compact_possible = false;
2985 if (!clusterset.m_to_remove.empty()) compact_possible = false;
2986 if (!clusterset.m_removed.empty()) compact_possible = false;
2987
2988 // For non-top levels, m_oversized must be known (as it cannot change until the level
2989 // on top is gone).
2990 if (level < GetTopLevel()) assert(clusterset.m_oversized.has_value());
2991 }
2992
2993 // Verify that the contents of m_unlinked matches what was expected based on the Entry vector.
2994 std::set<GraphIndex> actual_unlinked(m_unlinked.begin(), m_unlinked.end());
2995 assert(actual_unlinked == expected_unlinked);
2996
2997 // If compaction was possible, it should have been performed already, and m_unlinked must be
2998 // empty (to prevent memory leaks due to an ever-growing m_entries vector).
2999 if (compact_possible) {
3000 assert(actual_unlinked.empty());
3001 }
3002
3003 // Finally, check the chunk index.
3004 std::set<GraphIndex> actual_chunkindex;
3005 FeeFrac last_chunk_feerate;
3006 for (const auto& chunk : m_main_chunkindex) {
3007 GraphIndex idx = chunk.m_graph_index;
3008 actual_chunkindex.insert(idx);
3009 auto chunk_feerate = m_entries[idx].m_main_chunk_feerate;
3010 if (!last_chunk_feerate.IsEmpty()) {
3011 assert(FeeRateCompare(last_chunk_feerate, chunk_feerate) >= 0);
3012 }
3013 last_chunk_feerate = chunk_feerate;
3014 }
3015 assert(actual_chunkindex == expected_chunkindex);
3016}
3017
3018bool TxGraphImpl::DoWork(uint64_t iters) noexcept
3019{
3020 uint64_t iters_done{0};
3021 // First linearize everything in NEEDS_RELINEARIZE to an acceptable level. If more budget
3022 // remains after that, try to make everything optimal.
3023 for (QualityLevel quality : {QualityLevel::NEEDS_RELINEARIZE, QualityLevel::ACCEPTABLE}) {
3024 // First linearize staging, if it exists, then main.
3025 for (int level = GetTopLevel(); level >= 0; --level) {
3026 // Do not modify main if it has any observers.
3027 if (level == 0 && m_main_chunkindex_observers != 0) continue;
3028 ApplyDependencies(level);
3029 auto& clusterset = GetClusterSet(level);
3030 // Do not modify oversized levels.
3031 if (clusterset.m_oversized == true) continue;
3032 auto& queue = clusterset.m_clusters[int(quality)];
3033 while (!queue.empty()) {
3034 if (iters_done >= iters) return false;
3035 // Randomize the order in which we process, so that if the first cluster somehow
3036 // needs more work than what iters allows, we don't keep spending it on the same
3037 // one.
3038 auto pos = m_rng.randrange<size_t>(queue.size());
3039 auto iters_now = iters - iters_done;
3040 if (quality == QualityLevel::NEEDS_RELINEARIZE) {
3041 // If we're working with clusters that need relinearization still, only perform
3042 // up to m_acceptable_iters iterations. If they become ACCEPTABLE, and we still
3043 // have budget after all other clusters are ACCEPTABLE too, we'll spend the
3044 // remaining budget on trying to make them OPTIMAL.
3045 iters_now = std::min(iters_now, m_acceptable_iters);
3046 }
3047 auto [cost, improved] = queue[pos].get()->Relinearize(*this, level, iters_now);
3048 iters_done += cost;
3049 // If no improvement was made to the Cluster, it means we've essentially run out of
3050 // budget. Even though it may be the case that iters_done < iters still, the
3051 // linearizer decided there wasn't enough budget left to attempt anything with.
3052 // To avoid an infinite loop that keeps trying clusters with minuscule budgets,
3053 // stop here too.
3054 if (!improved) return false;
3055 }
3056 }
3057 }
3058 // All possible work has been performed, so we can return true. Note that this does *not* mean
3059 // that all clusters are optimally linearized now. It may be that there is nothing to do left
3060 // because all non-optimal clusters are in oversized and/or observer-bearing levels.
3061 return true;
3062}
3063
3064void BlockBuilderImpl::Next() noexcept
3065{
3066 // Don't do anything if we're already done.
3067 if (m_cur_iter == m_graph->m_main_chunkindex.end()) return;
3068 while (true) {
3069 // Advance the pointer, and stop if we reach the end.
3070 ++m_cur_iter;
3071 m_cur_cluster = nullptr;
3072 if (m_cur_iter == m_graph->m_main_chunkindex.end()) break;
3073 // Find the cluster pointed to by m_cur_iter.
3074 const auto& chunk_data = *m_cur_iter;
3075 const auto& chunk_end_entry = m_graph->m_entries[chunk_data.m_graph_index];
3076 m_cur_cluster = chunk_end_entry.m_locator[0].cluster;
3077 m_known_end_of_cluster = false;
3078 // If we previously skipped a chunk from this cluster we cannot include more from it.
3079 if (!m_excluded_clusters.contains(m_cur_cluster->m_sequence)) break;
3080 }
3081}
3082
3083std::optional<std::pair<std::vector<TxGraph::Ref*>, FeePerWeight>> BlockBuilderImpl::GetCurrentChunk() noexcept
3084{
3085 std::optional<std::pair<std::vector<TxGraph::Ref*>, FeePerWeight>> ret;
3086 // Populate the return value if we are not done.
3087 if (m_cur_iter != m_graph->m_main_chunkindex.end()) {
3088 ret.emplace();
3089 const auto& chunk_data = *m_cur_iter;
3090 const auto& chunk_end_entry = m_graph->m_entries[chunk_data.m_graph_index];
3091 if (chunk_data.m_chunk_count == LinearizationIndex(-1)) {
3092 // Special case in case just a single transaction remains, avoiding the need to
3093 // dispatch to and dereference Cluster.
3094 ret->first.resize(1);
3095 Assume(chunk_end_entry.m_ref != nullptr);
3096 ret->first[0] = chunk_end_entry.m_ref;
3097 m_known_end_of_cluster = true;
3098 } else {
3099 Assume(m_cur_cluster);
3100 ret->first.resize(chunk_data.m_chunk_count);
3101 auto start_pos = chunk_end_entry.m_main_lin_index + 1 - chunk_data.m_chunk_count;
3102 m_known_end_of_cluster = m_cur_cluster->GetClusterRefs(*m_graph, ret->first, start_pos);
3103 // If the chunk size was 1 and at end of cluster, then the special case above should
3104 // have been used.
3105 Assume(!m_known_end_of_cluster || chunk_data.m_chunk_count > 1);
3106 }
3107 ret->second = chunk_end_entry.m_main_chunk_feerate;
3108 }
3109 return ret;
3110}
3111
3112BlockBuilderImpl::BlockBuilderImpl(TxGraphImpl& graph) noexcept : m_graph(&graph)
3113{
3114 // Make sure all clusters in main are up to date, and acceptable.
3115 m_graph->MakeAllAcceptable(0);
3116 // There cannot remain any inapplicable dependencies (only possible if main is oversized).
3117 Assume(m_graph->m_main_clusterset.m_deps_to_add.empty());
3118 // Remember that this object is observing the graph's index, so that we can detect concurrent
3119 // modifications.
3120 ++m_graph->m_main_chunkindex_observers;
3121 // Find the first chunk.
3122 m_cur_iter = m_graph->m_main_chunkindex.begin();
3123 m_cur_cluster = nullptr;
3124 if (m_cur_iter != m_graph->m_main_chunkindex.end()) {
3125 // Find the cluster pointed to by m_cur_iter.
3126 const auto& chunk_data = *m_cur_iter;
3127 const auto& chunk_end_entry = m_graph->m_entries[chunk_data.m_graph_index];
3128 m_cur_cluster = chunk_end_entry.m_locator[0].cluster;
3129 }
3130}
3131
3132BlockBuilderImpl::~BlockBuilderImpl()
3133{
3134 Assume(m_graph->m_main_chunkindex_observers > 0);
3135 // Permit modifications to the main graph again after destroying the BlockBuilderImpl.
3136 --m_graph->m_main_chunkindex_observers;
3137}
3138
3139void BlockBuilderImpl::Include() noexcept
3140{
3141 // The actual inclusion of the chunk is done by the calling code. All we have to do is switch
3142 // to the next chunk.
3143 Next();
3144}
3145
3146void BlockBuilderImpl::Skip() noexcept
3147{
3148 // When skipping a chunk we need to not include anything more of the cluster, as that could make
3149 // the result topologically invalid. However, don't do this if the chunk is known to be the last
3150 // chunk of the cluster. This may significantly reduce the size of m_excluded_clusters,
3151 // especially when many singleton clusters are ignored.
3152 if (m_cur_cluster != nullptr && !m_known_end_of_cluster) {
3153 m_excluded_clusters.insert(m_cur_cluster->m_sequence);
3154 }
3155 Next();
3156}
3157
3158std::unique_ptr<TxGraph::BlockBuilder> TxGraphImpl::GetBlockBuilder() noexcept
3159{
3160 return std::make_unique<BlockBuilderImpl>(*this);
3161}
3162
3163std::pair<std::vector<TxGraph::Ref*>, FeePerWeight> TxGraphImpl::GetWorstMainChunk() noexcept
3164{
3165 std::pair<std::vector<Ref*>, FeePerWeight> ret;
3166 // Make sure all clusters in main are up to date, and acceptable.
3167 MakeAllAcceptable(0);
3168 Assume(m_main_clusterset.m_deps_to_add.empty());
3169 // If the graph is not empty, populate ret.
3170 if (!m_main_chunkindex.empty()) {
3171 const auto& chunk_data = *m_main_chunkindex.rbegin();
3172 const auto& chunk_end_entry = m_entries[chunk_data.m_graph_index];
3173 Cluster* cluster = chunk_end_entry.m_locator[0].cluster;
3174 if (chunk_data.m_chunk_count == LinearizationIndex(-1) || chunk_data.m_chunk_count == 1) {
3175 // Special case for singletons.
3176 ret.first.resize(1);
3177 Assume(chunk_end_entry.m_ref != nullptr);
3178 ret.first[0] = chunk_end_entry.m_ref;
3179 } else {
3180 ret.first.resize(chunk_data.m_chunk_count);
3181 auto start_pos = chunk_end_entry.m_main_lin_index + 1 - chunk_data.m_chunk_count;
3182 cluster->GetClusterRefs(*this, ret.first, start_pos);
3183 std::reverse(ret.first.begin(), ret.first.end());
3184 }
3185 ret.second = chunk_end_entry.m_main_chunk_feerate;
3186 }
3187 return ret;
3188}
3189
3190std::vector<TxGraph::Ref*> TxGraphImpl::Trim() noexcept
3191{
3192 int level = GetTopLevel();
3193 Assume(m_main_chunkindex_observers == 0 || level != 0);
3194 std::vector<TxGraph::Ref*> ret;
3195
3196 // Compute the groups of to-be-merged Clusters (which also applies all removals, and splits).
3197 auto& clusterset = GetClusterSet(level);
3198 if (clusterset.m_oversized == false) return ret;
3199 GroupClusters(level);
3200 Assume(clusterset.m_group_data.has_value());
3201 // Nothing to do if not oversized.
3202 Assume(clusterset.m_oversized.has_value());
3203 if (clusterset.m_oversized == false) return ret;
3204
3205 // In this function, would-be clusters (as precomputed in m_group_data by GroupClusters) are
3206 // trimmed by removing transactions in them such that the resulting clusters satisfy the size
3207 // and count limits.
3208 //
3209 // It works by defining for each would-be cluster a rudimentary linearization: at every point
3210 // the highest-chunk-feerate remaining transaction is picked among those with no unmet
3211 // dependencies. "Dependency" here means either a to-be-added dependency (m_deps_to_add), or
3212 // an implicit dependency added between any two consecutive transaction in their current
3213 // cluster linearization. So it can be seen as a "merge sort" of the chunks of the clusters,
3214 // but respecting the dependencies being added.
3215 //
3216 // This rudimentary linearization is computed lazily, by putting all eligible (no unmet
3217 // dependencies) transactions in a heap, and popping the highest-feerate one from it. Along the
3218 // way, the counts and sizes of the would-be clusters up to that point are tracked (by
3219 // partitioning the involved transactions using a union-find structure). Any transaction whose
3220 // addition would cause a violation is removed, along with all their descendants.
3221 //
3222 // A next invocation of GroupClusters (after applying the removals) will compute the new
3223 // resulting clusters, and none of them will violate the limits.
3224
3227 std::vector<std::pair<GraphIndex, GraphIndex>> deps_by_parent;
3229 std::vector<std::pair<GraphIndex, GraphIndex>> deps_by_child;
3233 std::vector<TrimTxData> trim_data;
3236 std::vector<std::vector<TrimTxData>::iterator> trim_heap;
3238 std::vector<TrimTxData*> current_deps;
3239
3241 static constexpr auto cmp_fn = [](auto a, auto b) noexcept {
3242 // Sort by increasing chunk feerate, and then by decreasing size.
3243 // We do not need to sort by cluster or within clusters, because due to the implicit
3244 // dependency between consecutive linearization elements, no two transactions from the
3245 // same Cluster will ever simultaneously be in the heap.
3246 return a->m_chunk_feerate < b->m_chunk_feerate;
3247 };
3248
3250 static constexpr auto find_fn = [](TrimTxData* arg) noexcept {
3251 while (arg != arg->m_uf_parent) {
3252 // Replace pointer to parent with pointer to grandparent (path splitting).
3253 // See https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Finding_set_representatives.
3254 auto par = arg->m_uf_parent;
3255 arg->m_uf_parent = par->m_uf_parent;
3256 arg = par;
3257 }
3258 return arg;
3259 };
3260
3263 static constexpr auto union_fn = [](TrimTxData* arg1, TrimTxData* arg2) noexcept {
3264 // Replace arg1 and arg2 by their representatives.
3265 auto rep1 = find_fn(arg1);
3266 auto rep2 = find_fn(arg2);
3267 // Bail out if both representatives are the same, because that means arg1 and arg2 are in
3268 // the same partition already.
3269 if (rep1 == rep2) return rep1;
3270 // Pick the lower-count root to become a child of the higher-count one.
3271 // See https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Union_by_size.
3272 if (rep1->m_uf_count < rep2->m_uf_count) std::swap(rep1, rep2);
3273 rep2->m_uf_parent = rep1;
3274 // Add the statistics of arg2 (which is no longer a representative) to those of arg1 (which
3275 // is now the representative for both).
3276 rep1->m_uf_size += rep2->m_uf_size;
3277 rep1->m_uf_count += rep2->m_uf_count;
3278 return rep1;
3279 };
3280
3282 auto locate_fn = [&](GraphIndex index) noexcept {
3283 auto it = std::lower_bound(trim_data.begin(), trim_data.end(), index, [](TrimTxData& elem, GraphIndex idx) noexcept {
3284 return elem.m_index < idx;
3285 });
3286 Assume(it != trim_data.end() && it->m_index == index);
3287 return it;
3288 };
3289
3290 // For each group of to-be-merged Clusters.
3291 for (const auto& group_data : clusterset.m_group_data->m_groups) {
3292 trim_data.clear();
3293 trim_heap.clear();
3294 deps_by_child.clear();
3295 deps_by_parent.clear();
3296
3297 // Gather trim data and implicit dependency data from all involved Clusters.
3298 auto cluster_span = std::span{clusterset.m_group_data->m_group_clusters}
3299 .subspan(group_data.m_cluster_offset, group_data.m_cluster_count);
3300 uint64_t size{0};
3301 for (Cluster* cluster : cluster_span) {
3302 size += cluster->AppendTrimData(trim_data, deps_by_child);
3303 }
3304 // If this group of Clusters does not violate any limits, continue to the next group.
3305 if (trim_data.size() <= m_max_cluster_count && size <= m_max_cluster_size) continue;
3306 // Sort the trim data by GraphIndex. In what follows, we will treat this sorted vector as
3307 // a map from GraphIndex to TrimTxData via locate_fn, and its ordering will not change
3308 // anymore.
3309 std::sort(trim_data.begin(), trim_data.end(), [](auto& a, auto& b) noexcept { return a.m_index < b.m_index; });
3310
3311 // Add the explicitly added dependencies to deps_by_child.
3312 deps_by_child.insert(deps_by_child.end(),
3313 clusterset.m_deps_to_add.begin() + group_data.m_deps_offset,
3314 clusterset.m_deps_to_add.begin() + group_data.m_deps_offset + group_data.m_deps_count);
3315
3316 // Sort deps_by_child by child transaction GraphIndex. The order will not be changed
3317 // anymore after this.
3318 std::sort(deps_by_child.begin(), deps_by_child.end(), [](auto& a, auto& b) noexcept { return a.second < b.second; });
3319 // Fill m_parents_count and m_parents_offset in trim_data, as well as m_deps_left, and
3320 // initially populate trim_heap. Because of the sort above, all dependencies involving the
3321 // same child are grouped together, so a single linear scan suffices.
3322 auto deps_it = deps_by_child.begin();
3323 for (auto trim_it = trim_data.begin(); trim_it != trim_data.end(); ++trim_it) {
3324 trim_it->m_parent_offset = deps_it - deps_by_child.begin();
3325 trim_it->m_deps_left = 0;
3326 while (deps_it != deps_by_child.end() && deps_it->second == trim_it->m_index) {
3327 ++trim_it->m_deps_left;
3328 ++deps_it;
3329 }
3330 trim_it->m_parent_count = trim_it->m_deps_left;
3331 // If this transaction has no unmet dependencies, and is not oversized, add it to the
3332 // heap (just append for now, the heapification happens below).
3333 if (trim_it->m_deps_left == 0 && trim_it->m_tx_size <= m_max_cluster_size) {
3334 trim_heap.push_back(trim_it);
3335 }
3336 }
3337 Assume(deps_it == deps_by_child.end());
3338
3339 // Construct deps_by_parent, sorted by parent transaction GraphIndex. The order will not be
3340 // changed anymore after this.
3341 deps_by_parent = deps_by_child;
3342 std::sort(deps_by_parent.begin(), deps_by_parent.end(), [](auto& a, auto& b) noexcept { return a.first < b.first; });
3343 // Fill m_children_offset and m_children_count in trim_data. Because of the sort above, all
3344 // dependencies involving the same parent are grouped together, so a single linear scan
3345 // suffices.
3346 deps_it = deps_by_parent.begin();
3347 for (auto& trim_entry : trim_data) {
3348 trim_entry.m_children_count = 0;
3349 trim_entry.m_children_offset = deps_it - deps_by_parent.begin();
3350 while (deps_it != deps_by_parent.end() && deps_it->first == trim_entry.m_index) {
3351 ++trim_entry.m_children_count;
3352 ++deps_it;
3353 }
3354 }
3355 Assume(deps_it == deps_by_parent.end());
3356
3357 // Build a heap of all transactions with 0 unmet dependencies.
3358 std::make_heap(trim_heap.begin(), trim_heap.end(), cmp_fn);
3359
3360 // Iterate over to-be-included transactions, and convert them to included transactions, or
3361 // skip them if adding them would violate resource limits of the would-be cluster.
3362 //
3363 // It is possible that the heap empties without ever hitting either cluster limit, in case
3364 // the implied graph (to be added dependencies plus implicit dependency between each
3365 // original transaction and its predecessor in the linearization it came from) contains
3366 // cycles. Such cycles will be removed entirely, because each of the transactions in the
3367 // cycle permanently have unmet dependencies. However, this cannot occur in real scenarios
3368 // where Trim() is called to deal with reorganizations that would violate cluster limits,
3369 // as all added dependencies are in the same direction (from old mempool transactions to
3370 // new from-block transactions); cycles require dependencies in both directions to be
3371 // added.
3372 while (!trim_heap.empty()) {
3373 // Move the best remaining transaction to the end of trim_heap.
3374 std::pop_heap(trim_heap.begin(), trim_heap.end(), cmp_fn);
3375 // Pop it, and find its TrimTxData.
3376 auto& entry = *trim_heap.back();
3377 trim_heap.pop_back();
3378
3379 // Initialize it as a singleton partition.
3380 entry.m_uf_parent = &entry;
3381 entry.m_uf_count = 1;
3382 entry.m_uf_size = entry.m_tx_size;
3383
3384 // Find the distinct transaction partitions this entry depends on.
3385 current_deps.clear();
3386 for (auto& [par, chl] : std::span{deps_by_child}.subspan(entry.m_parent_offset, entry.m_parent_count)) {
3387 Assume(chl == entry.m_index);
3388 current_deps.push_back(find_fn(&*locate_fn(par)));
3389 }
3390 std::sort(current_deps.begin(), current_deps.end());
3391 current_deps.erase(std::unique(current_deps.begin(), current_deps.end()), current_deps.end());
3392
3393 // Compute resource counts.
3394 uint32_t new_count = 1;
3395 uint64_t new_size = entry.m_tx_size;
3396 for (TrimTxData* ptr : current_deps) {
3397 new_count += ptr->m_uf_count;
3398 new_size += ptr->m_uf_size;
3399 }
3400 // Skip the entry if this would violate any limit.
3401 if (new_count > m_max_cluster_count || new_size > m_max_cluster_size) continue;
3402
3403 // Union the partitions this transaction and all its dependencies are in together.
3404 auto rep = &entry;
3405 for (TrimTxData* ptr : current_deps) rep = union_fn(ptr, rep);
3406 // Mark the entry as included (so the loop below will not remove the transaction).
3407 entry.m_deps_left = uint32_t(-1);
3408 // Mark each to-be-added dependency involving this transaction as parent satisfied.
3409 for (auto& [par, chl] : std::span{deps_by_parent}.subspan(entry.m_children_offset, entry.m_children_count)) {
3410 Assume(par == entry.m_index);
3411 auto chl_it = locate_fn(chl);
3412 // Reduce the number of unmet dependencies of chl_it, and if that brings the number
3413 // to zero, add it to the heap of includable transactions.
3414 Assume(chl_it->m_deps_left > 0);
3415 if (--chl_it->m_deps_left == 0) {
3416 trim_heap.push_back(chl_it);
3417 std::push_heap(trim_heap.begin(), trim_heap.end(), cmp_fn);
3418 }
3419 }
3420 }
3421
3422 // Remove all the transactions that were not processed above. Because nothing gets
3423 // processed until/unless all its dependencies are met, this automatically guarantees
3424 // that if a transaction is removed, all its descendants, or would-be descendants, are
3425 // removed as well.
3426 for (const auto& trim_entry : trim_data) {
3427 if (trim_entry.m_deps_left != uint32_t(-1)) {
3428 ret.push_back(m_entries[trim_entry.m_index].m_ref);
3429 clusterset.m_to_remove.push_back(trim_entry.m_index);
3430 }
3431 }
3432 }
3433 clusterset.m_group_data.reset();
3434 clusterset.m_oversized = false;
3435 Assume(!ret.empty());
3436 return ret;
3437}
3438
3439size_t TxGraphImpl::GetMainMemoryUsage() noexcept
3440{
3441 // Make sure splits/merges are applied, as memory usage may not be representative otherwise.
3442 SplitAll(/*up_to_level=*/0);
3443 ApplyDependencies(/*level=*/0);
3444 // Compute memory usage
3445 size_t usage = /* From clusters */
3446 m_main_clusterset.m_cluster_usage +
3447 /* From Entry objects. */
3448 sizeof(Entry) * m_main_clusterset.m_txcount +
3449 /* From the chunk index. */
3450 memusage::DynamicUsage(m_main_chunkindex);
3451 return usage;
3452}
3453
3454} // namespace
3455
3457{
3458 if (m_graph) {
3459 // Inform the TxGraph about the Ref being destroyed.
3460 m_graph->UnlinkRef(m_index);
3461 m_graph = nullptr;
3462 }
3463}
3464
3466{
3467 // Unlink the current graph, if any.
3468 if (m_graph) m_graph->UnlinkRef(m_index);
3469 // Inform the other's graph about the move, if any.
3470 if (other.m_graph) other.m_graph->UpdateRef(other.m_index, *this);
3471 // Actually update the contents.
3472 m_graph = other.m_graph;
3473 m_index = other.m_index;
3474 other.m_graph = nullptr;
3475 other.m_index = GraphIndex(-1);
3476 return *this;
3477}
3478
3479TxGraph::Ref::Ref(Ref&& other) noexcept
3480{
3481 // Inform the TxGraph of other that its Ref is being moved.
3482 if (other.m_graph) other.m_graph->UpdateRef(other.m_index, *this);
3483 // Actually move the contents.
3484 std::swap(m_graph, other.m_graph);
3485 std::swap(m_index, other.m_index);
3486}
3487
3488std::unique_ptr<TxGraph> MakeTxGraph(unsigned max_cluster_count, uint64_t max_cluster_size, uint64_t acceptable_iters) noexcept
3489{
3490 return std::make_unique<TxGraphImpl>(max_cluster_count, max_cluster_size, acceptable_iters);
3491}
int ret
ArgsManager & args
Definition: bitcoind.cpp:282
std::conditional_t<(BITS<=32), bitset_detail::IntBitSet< uint32_t >, std::conditional_t<(BITS<=std::numeric_limits< size_t >::digits), bitset_detail::IntBitSet< size_t >, bitset_detail::MultiIntBitSet< size_t,(BITS+std::numeric_limits< size_t >::digits - 1)/std::numeric_limits< size_t >::digits > > > BitSet
Definition: bitset.h:525
#define Assume(val)
Assume is the identity function.
Definition: check.h:118
Fast randomness source.
Definition: random.h:386
I randrange(I range) noexcept
Generate a random integer in the range [0..range), with range > 0.
Definition: random.h:254
Interface returned by GetBlockBuilder.
Definition: txgraph.h:179
TxGraph * m_graph
Which Graph the Entry lives in.
Definition: txgraph.h:234
virtual ~Ref()
Destroy this Ref.
Definition: txgraph.cpp:3456
Ref & operator=(Ref &&other) noexcept
Definition: txgraph.cpp:3465
Ref() noexcept=default
Construct an empty Ref.
Data structure to encapsulate fees, sizes, and dependencies for a set of transactions.
Definition: txgraph.h:47
virtual void UpdateRef(GraphIndex index, Ref &new_location) noexcept=0
Inform the TxGraph implementation that a TxGraph::Ref has moved.
uint32_t GraphIndex
Internal identifier for a transaction within a TxGraph.
Definition: txgraph.h:50
Data structure that holds a transaction graph's preprocessed data (fee, size, ancestors,...
const SetType & Ancestors(DepGraphIndex i) const noexcept
Get the ancestors of a given transaction i.
SetType GetReducedParents(DepGraphIndex i) const noexcept
Compute the (reduced) set of parents of node i in this graph.
const FeeFrac & FeeRate(DepGraphIndex i) const noexcept
Get the feerate of a given transaction i.
bool IsConnected(const SetType &subset) const noexcept
Determine if a subset is connected.
DepGraphIndex PositionRange() const noexcept
Get the range of positions in this DepGraph.
SetType FindConnectedComponent(const SetType &todo) const noexcept
Find some connected component within the subset "todo" of this graph.
DepGraphIndex AddTransaction(const FeeFrac &feefrac) noexcept
Add a new unconnected transaction to this transaction graph (in the first available position),...
void RemoveTransactions(const SetType &del) noexcept
Remove the specified positions from this DepGraph.
auto TxCount() const noexcept
Get the number of transactions in the graph.
const SetType & Descendants(DepGraphIndex i) const noexcept
Get the descendants of a given transaction i.
size_t DynamicMemoryUsage() const noexcept
const SetType & Positions() const noexcept
Get the set of transactions positions in use.
void Compact() noexcept
Reduce memory usage if possible.
void AddDependencies(const SetType &parents, DepGraphIndex child) noexcept
Modify this transaction graph, adding multiple parents to a specified child.
bool IsAcyclic() const noexcept
Check if this graph is acyclic.
Data structure encapsulating the chunking of a linearization, permitting removal of subsets.
uint64_t fee
uint64_t sequence
Level
Definition: logging.h:99
@ NONE
Definition: logging.h:65
std::vector< FeeFrac > ChunkLinearization(const DepGraph< SetType > &depgraph, std::span< const DepGraphIndex > linearization) noexcept
Compute the feerates of the chunks of linearization.
std::tuple< std::vector< DepGraphIndex >, bool, uint64_t > Linearize(const DepGraph< SetType > &depgraph, uint64_t max_iterations, uint64_t rng_seed, std::span< const DepGraphIndex > old_linearization={}) noexcept
Find or improve a linearization for a cluster.
void FixLinearization(const DepGraph< SetType > &depgraph, std::span< DepGraphIndex > linearization) noexcept
Make linearization topological, retaining its ordering where possible.
uint32_t DepGraphIndex
Data type to represent transaction indices in DepGraphs and the clusters they represent.
void PostLinearize(const DepGraph< SetType > &depgraph, std::span< DepGraphIndex > linearization)
Improve a given linearization.
static size_t DynamicUsage(const int8_t &v)
Dynamic memory usage for built-in types is zero.
Definition: memusage.h:31
static size_t MallocUsage(size_t alloc)
Compute the total memory used by allocating alloc bytes.
Definition: memusage.h:52
Definition: messages.h:20
std::vector< T > Split(const std::span< const char > &sp, std::string_view separators, bool include_sep=false)
Split a string on any char found in separators, returning a vector.
Definition: string.h:115
Data structure storing a fee and size, ordered by increasing fee/size.
Definition: feefrac.h:40
int64_t fee
Definition: feefrac.h:107
int32_t size
Definition: feefrac.h:108
bool IsEmpty() const noexcept
Check if this is empty (size and fee are 0).
Definition: feefrac.h:120
Tagged wrapper around FeeFrac to avoid unit confusion.
Definition: feefrac.h:239
static FeePerUnit FromFeeFrac(const FeeFrac &feefrac) noexcept
Convert a FeeFrac to a FeePerUnit.
Definition: feefrac.h:244
consteval auto _(util::TranslatedLiteral str)
Definition: translation.h:79
std::unique_ptr< TxGraph > MakeTxGraph(unsigned max_cluster_count, uint64_t max_cluster_size, uint64_t acceptable_iters) noexcept
Construct a new TxGraph with the specified limit on the number of transactions within a cluster,...
Definition: txgraph.cpp:3488
static constexpr unsigned MAX_CLUSTER_COUNT_LIMIT
Definition: txgraph.h:17
assert(!tx.IsCoinBase())
void ClearShrink(V &v) noexcept
Clear a vector (or std::deque) and release its allocated memory.
Definition: vector.h:56