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