cluster mempool: introduce TxGraph #31363

225+        Ref* m_ref;
226+        /** Which Cluster and position therein this Entry appears in. ([0] = main, [1] = staged). */
227+        Locator m_locator[MAX_LEVELS];
228+        /** The chunk feerate of this transaction in main (if present in m_locator[0]) */
229+        FeeFrac m_main_chunk_feerate;
230+        /** The position this transaction in the main linearization (if present). /*/

134-    virtual bool IsOversized() noexcept = 0;
135-    /** Get the feerate of the chunk which transaction arg is in. Returns the empty FeeFrac if arg
136-     *  does not exist. The graph must not be oversized. */
137-    virtual FeeFrac GetChunkFeerate(const Ref& arg) noexcept = 0;
138+    virtual bool IsOversized(bool main_only = false) noexcept = 0;
139+    /** Get the feerate of the chunk which transaction arg is in in the main graph. Returns the

104+    virtual FeeFrac GetChunkFeerate(const Ref& arg) noexcept = 0;
105+    /** Get the individual transaction feerate of transaction arg. Returns the empty FeeFrac if
106+     *  arg does not exist. */
107+    virtual FeeFrac GetIndividualFeerate(const Ref& arg) noexcept = 0;
108+    /** Get pointers to all transactions in the connected component ("cluster") which arg is in.
109+     *  The transactions will be returned in a topologically-valid order of acceptable quality.

1353+        // Figure out which elements elem needs to be placed before.
1354+        SetType place_before = done & depgraph.Ancestors(elem);
1355+        // Find which position to place elem in (updating j), continuously moving the elements
1356+        // in between forward.
1357+        while (place_before.Any()) {
1358+            auto to_swap = linearization[len - 1 - (j - 1)];

1143+        uint64_t val{0};
1144+        try {
1145+            reader >> VARINT(val);
1146+        } catch (const std::ios_base::failure&) {}
1147+        val %= todo.Count();
1148+        // Find which element in todo that corresponds to.

23+class TxGraphImpl;
24+
25+/** Position of a ClusterIndex within a Cluster::m_linearization. */
26+using LinearizationIndex = uint32_t;
27+/** Position of a Cluster within Graph::m_clusters. */
28+using ClusterSetIndex = uint32_t;

25+/** Position of a ClusterIndex within a Cluster::m_linearization. */
26+using LinearizationIndex = uint32_t;
27+/** Position of a Cluster within Graph::m_clusters. */
28+using ClusterSetIndex = uint32_t;
29+
30+/** Quality levels for cached linearizations. */

11@@ -12,8 +12,7 @@
12 #ifndef BITCOIN_TXGRAPH_H
13 #define BITCOIN_TXGRAPH_H
14 
15-/** No connected component within TxGraph is allowed to exceed this number of transactions. */
16-static constexpr unsigned CLUSTER_COUNT_LIMIT{64};
17+static constexpr unsigned MAX_CLUSTER_COUNT_LIMIT{64};

308+        auto& entry = m_entries[idx];
309+        Assume(entry.m_ref != nullptr);
310+        entry.m_ref = &new_location;
311+    }
312+
313+    /** Only called by Ref::~Ref to unlink Refs. */

542+
543+void TxGraphImpl::ApplyRemovals() noexcept
544+{
545+    auto& to_remove = m_to_remove;
546+    // Skip if there is nothing to remove.
547+    if (to_remove.empty()) return;

1335@@ -1336,6 +1336,38 @@ std::vector<ClusterIndex> MergeLinearizations(const DepGraph<SetType>& depgraph,
1336     return ret;
1337 }
1338 
1339+/** Make linearization topological, retaining its ordering where possible. */
1340+template<typename SetType>
1341+void FixLinearization(const DepGraph<SetType>& depgraph, Span<ClusterIndex> linearization) noexcept
1342+{
1343+    // This algorithm can be summarized as moving every element in the linearization backwards
1344+    // until it is placed after all this ancestors.

1348+    for (ClusterIndex i = 0; i < len; ++i) {
1349+        /** The element at that position. */
1350+        ClusterIndex elem = linearization[len - 1 - i];
1351+        /** j represents how far from the back of the linearization elem should be placed. */
1352+        ClusterIndex j = i;
1353+        // Figure out which elements elem needs to be placed before.

1355+        // Find which position to place elem in (updating j), continuously moving the elements
1356+        // in between forward.
1357+        while (place_before.Any()) {
1358+            // j cannot be 0 here; if it was, then there was necessarily nothing earlier which
1359+            // elem needs to be place before anymore, and place_before would be empty.
1360+            Assume(j > 0);

406@@ -407,7 +407,7 @@ FUZZ_TARGET(clusterlin_depgraph_serialization)
407     SanityCheck(depgraph);
408 
409     // Verify the graph is a DAG.
410-    assert(IsAcyclic(depgraph));

279@@ -280,6 +280,7 @@ add_library(bitcoin_node STATIC EXCLUDE_FROM_ALL
280   signet.cpp
281   torcontrol.cpp
282   txdb.cpp
283+  txgraph.cpp

40+        GraphIndex m_index = GraphIndex(-1);
41+    public:
42+        /** Construct an empty Ref. Non-empty Refs can only be created using
43+         *  TxGraph::AddTransaction. */
44+        Ref() noexcept = default;
45+        /** Destroy this Ref. This is only allowed when it is empty, or the transaction it refers

79+     * its ancestors, are removed as well (which is what always happens in realistic scenarios),
80+     * this reordering will not affect the behavior of TxGraph.
81+     *
82+     * As an example, imagine 3 transactions A,B,C where B depends on A. If a dependency of C on B
83+     * is added, and then B is deleted, C will still depend on A. If the deletion of B is reordered
84+     * before the C->B dependency is added, it has no effect instead. If, together with the

154+    /** Which dependencies are to be added ((parent,child) pairs). GroupData::m_deps_offset indexes
155+     *  into this. */
156+    std::vector<std::pair<GraphIndex, GraphIndex>> m_deps_to_add;
157+    /** Information about the merges to be performed, if known. */
158+    std::optional<std::vector<GroupEntry>> m_group_data = std::vector<GroupEntry>{};
159+    /** Total number of transactions in this ClusterSet (explicit + implicit). */

177+
178+    /** A class of objects held internally in TxGraphImpl, with information about a single
179+     *  transaction. */
180+    struct Entry
181+    {
182+        /** Pointer to the corresponding Ref object, if any. */

82+    /** Push changes to Cluster and its linearization to the TxGraphImpl Entry objects. */
83+    void Updated(TxGraphImpl& graph) noexcept;
84+
85+    // Functions that implement the Cluster-specific side of internal TxGraphImpl mutations.
86+
87+    /** Apply any number of removals from the front of to_remove, popping them off. At least one

301+}
302+
303+void Cluster::ApplyRemovals(TxGraphImpl& graph, std::span<GraphIndex>& to_remove) noexcept
304+{
305+    // Iterate over the prefix of to_remove that applies to this cluster.
306+    Assume(!to_remove.empty());

304+{
305+    // Iterate over the prefix of to_remove that applies to this cluster.
306+    Assume(!to_remove.empty());
307+    SetType todo;
308+    do {
309+        GraphIndex idx = to_remove.front();

49+    friend class TxGraphImpl;
50+    using GraphIndex = TxGraph::GraphIndex;
51+    using SetType = BitSet<CLUSTER_COUNT_LIMIT>;
52+    /** The DepGraph for this cluster, holding all feerates, and ancestors/descendants. */
53+    DepGraph<SetType> m_depgraph;
54+    /** m_mapping[i] gives the GraphIndex for the position i transaction in m_depgraph. */

51+    using SetType = BitSet<CLUSTER_COUNT_LIMIT>;
52+    /** The DepGraph for this cluster, holding all feerates, and ancestors/descendants. */
53+    DepGraph<SetType> m_depgraph;
54+    /** m_mapping[i] gives the GraphIndex for the position i transaction in m_depgraph. */
55+    std::vector<GraphIndex> m_mapping;
56+    /** The current linearization of the cluster. Size equals m_mapping.TxCount().

349+    std::vector<Cluster*> new_clusters;
350+    bool first{true};
351+    // Iterate over the connected components of this Cluster's m_depgraph.
352+    while (todo.Any()) {
353+        auto component = m_depgraph.FindConnectedComponent(todo);
354+        if (first && component == todo) {

360+        }
361+        first = false;
362+        // Construct a new Cluster to hold the found component.
363+        auto new_cluster = std::make_unique<Cluster>();
364+        new_clusters.push_back(new_cluster.get());
365+        // Remember that all the component's transaction go to this new Cluster. The positions

419+        }
420+        m_linearization.push_back(new_pos);
421+        // Copy the transaction's dependencies, translating them using remap.
422+        SetType parents;
423+        for (auto par : other.m_depgraph.GetReducedParents(pos)) {
424+            parents.Set(remap[par]);

441+    // between which dependencies are added, which simply concatenates their linearizations. Invoke
442+    // PostLinearize, which has the effect that the linearization becomes a merge-sort of the
443+    // constituent linearizations. Do this here rather than in Cluster::Merge, because this
444+    // function is only invoked once per merged Cluster, rather than once per constituent one.
445+    // This concatenation + post-linearization could be replaced with an explicit merge-sort.
446+    PostLinearize(m_depgraph, m_linearization);

90+    /** Split this cluster (must have a NEEDS_SPLIT* quality). Returns whether to delete this
91+     *  Cluster afterwards. */
92+    [[nodiscard]] bool Split(TxGraphImpl& graph) noexcept;
93+    /** Move all transactions from cluster to *this (as separate components). */
94+    void Merge(TxGraphImpl& graph, Cluster& cluster) noexcept;
95+    /** Given a span of (parent, child) pairs that all belong to this Cluster (or be removed),

449+    std::sort(to_apply.begin(), to_apply.end(), [](auto& a, auto& b) { return a.second < b.second; });
450+    // Iterate over groups of to-be-added dependencies with the same child.
451+    auto it = to_apply.begin();
452+    while (it != to_apply.end()) {
453+        auto& first_child = graph.m_entries[it->second].m_locator;
454+        DepGraphIndex child_idx = first_child.index;

492+
493+    // Clean up space in quality_cluster.
494+    auto max_setindex = quality_clusters.size() - 1;
495+    if (setindex != max_setindex) {
496+        // If the cluster was not the last element of quality_clusters, move that to take its place.
497+        quality_clusters.back()->m_quality = quality;

556+        if (cluster != nullptr) {
557+            // If the first to_remove_span entry's Cluster exists, hand to_remove_span to it, so it
558+            // can pop off whatever applies to it.
559+            cluster->ApplyRemovals(*this, to_remove_span);
560+        } else {
561+            // Otherwise, skip this already-removed entry.

353+        auto component = m_depgraph.FindConnectedComponent(todo);
354+        if (first && component == todo) {
355+            // The existing Cluster is an entire component. Leave it be, but update its quality.
356+            graph.SetClusterQuality(m_quality, m_setindex, QualityLevel::NEEDS_RELINEARIZE);
357+            // We need to recompute and cache its chunking.
358+            Updated(graph);

82+     * As an example, imagine 3 transactions A,B,C where B depends on A. If a dependency of C on B
83+     * is added, and then B is deleted, C will still depend on A. If the deletion of B is reordered
84+     * before the C->B dependency is added, it has no effect instead. If, together with the
85+     * deletion of B also either A or C is deleted, there is no distinction.
86+     */
87+    virtual void RemoveTransaction(const Ref& arg) noexcept = 0;

391+        for (auto par : m_depgraph.GetReducedParents(i)) new_parents.Set(remap[par].second);
392+        new_cluster->m_depgraph.AddDependencies(new_parents, remap[i].second);
393+    }
394+    // Update all the Locators of moved transactions.
395+    for (Cluster* new_cluster : new_clusters) {
396+        new_cluster->Updated(graph);

594+    if (!m_deps_to_add.empty()) return;
595+    if (!m_to_remove.empty()) return;
596+
597+    // Sort the GraphIndexes that need to be cleaned up. They are sorted in reverse, so the last
598+    // ones get processed first. This means earlier-processed GraphIndexes will not cause moving of
599+    // later-processed ones during the "swap with end of m_entries" step (which might invalidate

654+    if (m_group_data.has_value()) return;
655+
656+    /** Annotated clusters: an entry for each Cluster, together with the representative for the
657+     *  partition it is in if known, or with nullptr if not yet known. */
658+    std::vector<std::pair<Cluster*, Cluster*>> an_clusters;
659+    /** Annotated dependencies: an entry for each m_deps_to_apply entry (excluding ones that apply

1005+std::vector<TxGraph::Ref*> TxGraphImpl::GetAncestors(const Ref& arg) noexcept
1006+{
1007+    // Return the empty vector if the Ref is empty.
1008+    if (GetRefGraph(arg) == nullptr) return {};
1009+    Assume(GetRefGraph(arg) == this);
1010+    // Apply all dependencies, as the result might be incorrect otherwise.

88+    /** Add a dependency between two specified transactions. Parent may not be a descendant of
89+     *  child already (but may be an ancestor of it already, in which case this is a no-op). If
90+     *  either transaction is already removed, this is a no-op. */
91+    virtual void AddDependency(const Ref& parent, const Ref& child) noexcept = 0;
92+    /** Modify the fee of the specified transaction. If the transaction does not exist (or was
93+     *  removed), this has no effect. */

1099+
1100+void TxGraphImpl::SetTransactionFee(const Ref& ref, int64_t fee) noexcept
1101+{
1102+    // Don't do anything if the passed Ref is empty.
1103+    if (GetRefGraph(ref) == nullptr) return;
1104+    Assume(GetRefGraph(ref) == this);

1067+
1068+FeePerWeight TxGraphImpl::GetChunkFeerate(const Ref& arg) noexcept
1069+{
1070+    // Return the empty FeePerWeight if the passed Ref is empty.
1071+    if (GetRefGraph(arg) == nullptr) return {};
1072+    Assume(GetRefGraph(arg) == this);

17+
18+/** Data structure to encapsulate fees, sizes, and dependencies for a set of transactions. */
19+class TxGraph
20+{
21+public:
22+    /** Internal identifier for a transaction within a TxGraph. */

841+    Assume(m_group_data.has_value());
842+    // Nothing to do if there are no dependencies to be added.
843+    if (m_deps_to_add.empty()) return;
844+
845+    // For each group of to-be-merged Clusters.
846+    Assume(m_group_data.has_value());

141+    /** Information about one group of Clusters to be merged. */
142+    struct GroupEntry
143+    {
144+        /** Which clusters are to be merged. */
145+        std::vector<Cluster*> m_clusters;
146+        /** Which dependencies are to be applied to those merged clusters. */

845+    // For each group of to-be-merged Clusters.
846+    Assume(m_group_data.has_value());
847+    for (auto& group_data : *m_group_data) {
848+        // Invoke Merge() to merge them into a single Cluster.
849+        Merge(group_data.m_clusters);
850+        // Actually apply all to-be-added dependencies (for each, parent and child belong to the

663+
664+    // Construct a an_clusters entry for every parent and child in the to-be-applied dependencies.
665+    for (const auto& [par, chl] : m_deps_to_add) {
666+        auto par_cluster = m_entries[par].m_locator.cluster;
667+        auto chl_cluster = m_entries[chl].m_locator.cluster;
668+        // Skip dependencies for which the parent or child transaction is removed.

690+             *  a representative for the entire tree, and can be found by walking upwards from any
691+             *  element. */
692+            PartitionData* parent;
693+            /** (only if this is a root, so when parent == this) An upper bound on the height of
694+             *  tree for this partition. */
695+            unsigned rank;

705+            Assume(it->cluster == arg);
706+            return &*it;
707+        };
708+
709+        /** Given a PartitionData, find the root of the tree it is in (its representative). */
710+        static constexpr auto find_uf = [](PartitionData* data) noexcept -> PartitionData* {

759+        for (size_t i = 0; i < partition_data.size(); ++i) {
760+            auto& data = partition_data[i];
761+            // Find the representative of the partition Cluster i is in, and store it with the
762+            // Cluster.
763+            auto rep = find_uf(&data)->cluster;
764+            an_clusters[i].second = rep;

167+
168+    // Construct a real and a simulated graph.
169+    auto real = MakeTxGraph();
170+    SimTxGraph sim;
171+
172+    /** Function to pick any Ref (in sim real, sim.removed, or empty). */

310@@ -311,7 +311,7 @@ void Cluster::ApplyRemovals(TxGraphImpl& graph, std::span<GraphIndex>& to_remove
311         auto& locator = entry.m_locator;
312         // Stop once we hit an entry that applies to another Cluster.
313         if (locator.cluster != this) break;
314-        // - Remember it in a set of to-remove ClusterIndexes.
315+        // - Remember it in a set of to-remove DepGraphIndexes.

100+        auto pos = Find(ref);
101+        if (pos == MISSING) return;
102+        graph.RemoveTransactions(SetType::Singleton(pos));
103+        simrevmap.erase(simmap[pos].get());
104+        // Retain the TxGraph::Ref corresponding to this position, until explicitly destroyed.
105+        // to see it when calling Cleanup().

210+        while (true) {
211+            if (sim.GetTransactionCount() < SimTxGraph::MAX_TRANSACTIONS && command-- == 0) {
212+                // AddTransaction.
213+                int64_t fee;
214+                int32_t size;
215+                if (alt) {

250+                    if (oversize) break;
251+                }
252+                sim.AddDependency(par, chl);
253+                real->AddDependency(*par, *chl);
254+                break;
255+            } else if (sim.removed.size() < 100 && command-- == 0) {

266+                    real->RemoveTransaction(*ptr);
267+                    sim.RemoveTransaction(ptr);
268+                }
269+                break;
270+            } else if (sim.removed.size() > 0 && command-- == 0) {
271+                // ~Ref

274+                if (removed_pos != sim.removed.size() - 1) {
275+                    std::swap(sim.removed[removed_pos], sim.removed.back());
276+                }
277+                sim.removed.pop_back();
278+                break;
279+            } else if (sim.GetTransactionCount() > 0 && command-- == 0) {

173+    auto pick_fn = [&]() noexcept -> TxGraph::Ref* {
174+        auto tx_count = sim.GetTransactionCount();
175+        /** The number of possible choices. */
176+        size_t choices = tx_count + sim.removed.size() + 1;
177+        /** Pick one of them. */
178+        auto choice = provider.ConsumeIntegralInRange<size_t>(0, choices - 1);

77+    }
78+
79+    /** Add a dependency between two positions in this graph. */
80+    void AddDependency(TxGraph::Ref* parent, TxGraph::Ref* child)
81+    {
82+        auto par_pos = Find(parent);

195+        // Return empty.
196+        assert(choice == 0);
197+        return &empty_ref;
198+    };
199+
200+    LIMITED_WHILE(provider.remaining_bytes() > 0, 200) {

1196+        // ... for all clusters in them ...
1197+        for (ClusterSetIndex setindex = 0; setindex < quality_clusters.size(); ++setindex) {
1198+            const auto& cluster = *quality_clusters[setindex];
1199+            // Remember we saw this Cluster (only if it is non-empty; empty Clusters aren't
1200+            // expected to be referenced by the Entry vector).
1201+            if (cluster.GetTxCount() != 0) {

1158+    assert(m_done == m_depgraph.Positions());
1159+}
1160+
1161+void TxGraphImpl::SanityCheck() const
1162+{
1163+    /** Which GraphIndexes ought to occur in m_wiped, based on m_entries. */

1144+        // Check that the Entry has a locator pointing back to this Cluster & position within it.
1145+        assert(entry.m_locator.cluster == this);
1146+        assert(entry.m_locator.index == lin_pos);
1147+        // Check linearization position and chunk feerate.
1148+        if (!linchunking.GetChunk(0).transactions[lin_pos]) {
1149+            linchunking.MarkDone(linchunking.GetChunk(0).transactions);

833+            while (deps_it != m_deps_to_add.end()) {
834+                auto [par, chl] = *deps_it;
835+                auto chl_cluster = m_entries[chl].m_locator.cluster;
836+                // Skip dependencies that apply to earlier Clusters (those necessary are for
837+                // deleted transactions, as otherwise we'd have processed them already).
838+                if (!std::less{}(chl_cluster, data.cluster)) {

418+           m_quality == QualityLevel::NEEDS_SPLIT_ACCEPTABLE);
419+    // Determine the new quality the split-off Clusters will have.
420+    QualityLevel new_quality = m_quality == QualityLevel::NEEDS_SPLIT ? QualityLevel::NEEDS_RELINEARIZE :
421+                               m_quality == QualityLevel::NEEDS_SPLIT_OPTIMAL ? QualityLevel::OPTIMAL :
422+                               QualityLevel::ACCEPTABLE;
423+    // If the cluster was NEEDS_SPLIT_OPTIMAL, and we're thus going to produce OPTIMAL clusters, we

1017@@ -997,6 +1018,7 @@ void TxGraphImpl::AddDependency(const Ref& parent, const Ref& child) noexcept
1018     m_group_data.reset();
1019     // Remember that this dependency is to be applied.
1020     m_deps_to_add.emplace_back(GetRefIndex(parent), GetRefIndex(child));
1021+    m_group_data.reset();

336-        } while(chunk.transactions.Any());
337+    // If the Cluster's quality is ACCEPTABLE or OPTIMAL, compute its chunking and store its
338+    // information in the Entry's m_chunk_feerate. These fields are only accessed after making
339+    // the entire graph ACCEPTABLE, so it is pointless to compute these if we haven't reached that
340+    // quality level yet.
341+    if (m_quality == QualityLevel::OPTIMAL || m_quality == QualityLevel::ACCEPTABLE) {

259@@ -260,6 +260,8 @@ class TxGraphImpl final : public TxGraph
260     ClusterSetIndex InsertCluster(std::unique_ptr<Cluster>&& cluster, QualityLevel quality) noexcept;
261     /** Change the QualityLevel of a Cluster (identified by old_quality and old_index). */
262     void SetClusterQuality(QualityLevel old_quality, ClusterSetIndex old_index, QualityLevel new_quality) noexcept;
263+    /** Make a transaction not exist. */

304@@ -252,16 +305,21 @@ class TxGraphImpl final : public TxGraph
305 
306     /** Swap the Entrys referred to by a and b. */
307     void SwapIndexes(GraphIndex a, GraphIndex b) noexcept;
308-    /** Extract a Cluster. */
309-    std::unique_ptr<Cluster> ExtractCluster(QualityLevel quality, ClusterSetIndex setindex) noexcept;
310+    /** If idx exists in the specified level ClusterSet (explicitly or implicitly), return the

 94@@ -90,6 +95,17 @@ class Cluster
 95     void UpdateMapping(DepGraphIndex cluster_idx, GraphIndex graph_idx) noexcept { m_mapping[cluster_idx] = graph_idx; }
 96     /** Push changes to Cluster and its linearization to the TxGraphImpl Entry objects. */
 97     void Updated(TxGraphImpl& graph) noexcept;
 98+    /** Create a copy of this Cluster, returning a pointer to it (used by PullIn). */
 99+    Cluster* CopyTo(TxGraphImpl& graph, int to_level) const noexcept;
100+    /** Get the list of Clusters that conflict with this one (at level-1). */

208@@ -189,28 +209,59 @@ class TxGraphImpl final : public TxGraph
209         std::vector<std::pair<GraphIndex, GraphIndex>> m_deps_to_add;
210         /** Information about the merges to be performed, if known. */
211         std::optional<GroupData> m_group_data = GroupData{};
212+        /** Which entries were removed in this ClusterSet (so they can be wiped on abort). */