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