cluster mempool: add TxGraph reorg functionality #31553

I'm not sure how this is intended to be used, but storing a stack address seems like a problem? RVO may help but that seems brittle. I imagine the caller should be passing in their own Ref instead?

I believe it is safe, both with NRVO and without.

With NRVO, ret is constructed directly in the caller's target destination, so this isn't a pointer to local stack space.

Without NRVO, the Ref(Ref&&) move constructor is invoked by return ret;, which will update the pointer to the caller's destination.

Ah, right, I missed that the move ctor would handle the update. Thanks for explaining.

Why is this doing an effective swap? I would expect this to call UnlinkRef on the moved-from value and reset its m_graph and m_index. Otherwise it wouldn't be unlinked until the moved-from variable goes out of scope, no?

Why is this doing an effective swap?

I think this is quite common, that move-construction is effectively performing a swap.

I would expect this to call UnlinkRef on the moved-from value and reset its m_graph and m_index

That's possible too, and slightly more efficient I guess.

Otherwise it wouldn't be unlinked until the moved-from variable goes out of scope, no?

Indeed. I don't think that's a problem.

Anyway, done!

Why is this doing an effective swap?

I think this is quite common, that move-construction is effectively performing a swap.

I would expect this to call UnlinkRef on the moved-from value and reset its m_graph and m_index

That's possible too, and slightly more efficient I guess.

Otherwise it wouldn't be unlinked until the moved-from variable goes out of scope, no?

Indeed. I don't think that's a problem.

Afaik the move/swap idiom is only safe if the swapped-to value's dtor doesn't have any interesting ordering requirements or side-effects.

As a contrived example, a user may do something like:

std::vector<TxGraph::Ref> vec;

vec.push_back(txgraph->AddTransaction(fee));
auto ref = txgraph->AddTransaction(fee2);
...
ref = std::move(vec.back());

The vector now holds the old ref and UnlinkRef will not be called until that element is removed. I realize it's allowed to be a "valid but unspecified state", but I wouldn't expect a ref to be hanging around.

m_ref{nullptr};

Done.

Trying to convince myself this is guaranteed to terminate...

do{} while (!chunk.transactions.None()) rather than the break for readability? Or just while() if we need to guard against an empty linearization (presumably not?)

It terminates because:

• Every chunk contains at least one element (added an Assume for that)
• In the inner loop, one element from that chunk is Reset() (added an Assume that it indeed resets a bit that was previously set).

I've changed it to a do {} while(chunk.transactions.Any()); loop in the first commits, though it reverts back to a while (true) { ... } loop later, when the loop becomes a bit more complex.

Assume !to_remove.empty() or early return if it's allowed?

Done. I've also added a comment to the Cluster::ApplyRemovals() function definition stating that at least one element from the front of to_remove must belong to this Cluster (which is really why that requirement exists).

Looks like these 3 functions could reserve() for their ret vectors.

Done. The third one disappears in a later commit, though.

FYI -- in my rebase of #28676, I'm seeing tx_pool fuzz test failures due to this line. Not clear to me whether we should require the caller to enforce the policy requirement that a single tx be below the cluster size limit, or just let the caller discover a changeset is oversized and then reject?

Right. That rule exists because the alternative requires existing clusters to be oversized as AddTransaction constructs a singleton cluster instantly. All other forms of oversizedness happen as a result of applying dependencies, which are done lazily.

I'll think about relaxing this.

Done, it is now allowed to have individually oversized transactions.

            // j cannot be 0 or less; if it was, then there was necessarily nothing earlier which

if it was, then there was necessarily nothing earlier which elem needs to be place before anymore, and place_before would be empty.

This comment seems jumbled and hard to understand. Is it possible to word this better?

        // Reuse a discarded node handle.

462429bc159b1b5ddb5443c484c9bdeae985ad26

nitty: max_agg_size

I have changed the variable names to max_cluster_count and max_cluster_size everywhere.

462429bc159b1b5ddb5443c484c9bdeae985ad26

misinterpreted the commit message that the aggregate size should not be hit when adding transaction, rather than each individual txn shouldn't exceed this limit. Maybe make this crystal clear.

Do you mean in the TxGraph::AddTransaction definition in txgraph.h? I have expanded the comments in the fuzz test around this a bit.

Does :+1: mean "That is what I meant" or "It's fixed now"?

comments appear clear enough now

462429bc159b1b5ddb5443c484c9bdeae985ad26

nitty: GetTotalTxSize? GetAggTxSize? GetTxsSize?

GetTotalTxSize is a nice color.

462429bc159b1b5ddb5443c484c9bdeae985ad26

nit: docstring for m_group_oversized should be updated

Done, but also removed in a later commit.

and can't also be 0? Didn't double check this was already the case, but an assertion is added in 462429bc159b1b5ddb5443c484c9bdeae985ad26

Added as comment.

462429bc159b1b5ddb5443c484c9bdeae985ad26

Was a bit confusing at first, but this must be true because clusters are never merged (via dependency application) when to-be-merged-clusters would be oversized.

I've added a comment to highlight that.

439ccf713b8f9de1dff1d02678bb68d0f29ea175

commit message maybe could get beefed up a bit with motivation since at first blush it seems odd to add singletons we wouldn't have relayed in the first place

I have expanded the commit message of both Trim commits.

439ccf713b8f9de1dff1d02678bb68d0f29ea175

nit: SINGLETON_OVERSIZED to reduce later mental gymnastics

Good idea, I went with OVERSIZED_SINGLETON.

439ccf713b8f9de1dff1d02678bb68d0f29ea175

please add documentation on what oversized_tx should be

Done.

439ccf713b8f9de1dff1d02678bb68d0f29ea175

is this a future optimization? these types of clusters were already being marked as NEED_SPLIT_*

I have simplified this to just a m_linearization.empty() || in the if conditional below.

        Assume(m_level == 0);
        graph.ClearLocator(m_level, m_mapping[i], /*oversized_tx=*/false);

Instead of this big unintuitive comment, I have replaced it with /*oversized_tx=*/m_quality == QualityLevel::OVERSIZED_SINGLETON. With that, I don't think the Assume is neccesary?

much better thanks

acb2b6a90a47567773268a024bcf2f1ddfcc60df

FYI this condition doesn't appear to be hit in the fuzz harness

Both assert(rep1 == rep2) and assert(rep1 != rep2) instantly trigger failures when fuzzing for me.

curious. Coverage report may be off.

439ccf713b8f9de1dff1d02678bb68d0f29ea175

Should this function have clearer naming/documentation to avoid future regressions in use? Seems brittle to me.

See above, I have dropped the constraints on ClearLocator instead.

better thanks

439ccf713b8f9de1dff1d02678bb68d0f29ea175

Do we need m_group_oversized? Seems like a variable we have to keep in sync for no reason:

diff --git a/src/txgraph.cpp b/src/txgraph.cpp
index 01076b763b..853f8530a0 100644
--- a/src/txgraph.cpp
+++ b/src/txgraph.cpp
@@ -231,7 +231,4 @@ private:
         /** Which clusters are to be merged. GroupEntry::m_cluster_offset indexes into this. */
         std::vector<Cluster*> m_group_clusters;
-        /** Whether at least one of the groups cannot be applied because it would result in a
-         *  Cluster that violates the cluster count limit. */
-        bool m_group_oversized;
     };
 
@@ -257,7 +254,5 @@ private:
         /** Total number of individually oversized transactions in the graph. */
         GraphIndex m_txcount_oversized{0};
-        /** Whether this graph is oversized (if known). This roughly matches
-         *  m_group_data->m_group_oversized || (m_txcount_oversized > 0), but may be known even if
-         *  m_group_data is not. */
+        /** Whether this graph is oversized (if known). */
         std::optional<bool> m_oversized{false};
 
@@ -1470,7 +1465,7 @@ void TxGraphImpl::GroupClusters(int level) noexcept
     clusterset.m_group_data = GroupData{};
     clusterset.m_group_data->m_group_clusters.reserve(an_clusters.size());
-    clusterset.m_group_data->m_group_oversized = false;
     clusterset.m_deps_to_add.clear();
     clusterset.m_deps_to_add.reserve(an_deps.size());
+    clusterset.m_oversized = false;
     auto an_deps_it = an_deps.begin();
     auto an_clusters_it = an_clusters.begin();
@@ -1502,10 +1497,9 @@ void TxGraphImpl::GroupClusters(int level) noexcept
         // Detect oversizedness.
         if (total_count > m_max_cluster_count || total_size > m_max_cluster_size) {
-            clusterset.m_group_data->m_group_oversized = true;
+            clusterset.m_oversized = true;
         }
     }
     Assume(an_deps_it == an_deps.end());
     Assume(an_clusters_it == an_clusters.end());
-    clusterset.m_oversized = clusterset.m_group_data->m_group_oversized;
     Compact();
 }
@@ -2371,11 +2365,4 @@ void TxGraphImpl::SanityCheck() const
         if (!clusterset.m_removed.empty()) compact_possible = false;
 
-        // If m_group_data exists, and no outstanding removals remain, m_group_oversized must match
-        // m_group_oversized || (m_txcount_oversized > 0).
-        if (clusterset.m_group_data.has_value() && clusterset.m_to_remove.empty()) {
-            assert(clusterset.m_oversized ==
-                   (clusterset.m_group_data->m_group_oversized || (clusterset.m_txcount_oversized > 0)));
-        }
-
         // For non-top levels, m_oversized must be known (as it cannot change until the level
         // on top is gone).

Nice catch, after the changes in "Permit transactions that exceed cluster size limit", m_group_oversized is never read anymore. Included this patch as a separate simplification commit.

acb2b6a90a47567773268a024bcf2f1ddfcc60df

Some of this commit message should probably go in ce825731e8bea294e71b339015eccdb087e760c7 ? First paragraph at least.

I have expanded the commit messages.

Here are a couple suggestions to tighten up the checks on what we're trimming. Attempted to state that:

1. non-oversized clusters remain untouched
2. transactions with no ancestors that are undersized should never be trimmed (this seems natural but the interface doesn't guarantee it)

Mostly trying to avoid degenerate behavior like entire mempool being wiped, or any oversized cluster being completely wiped needlessly.

diff --git a/src/test/fuzz/txgraph.cpp b/src/test/fuzz/txgraph.cpp
index 47ad5792bf..bdf759f485 100644
--- a/src/test/fuzz/txgraph.cpp
+++ b/src/test/fuzz/txgraph.cpp
@@ -91,4 +91,28 @@ struct SimTxGraph
     }
 
+    /** Returns true if all positions in the given set are in oversized clusters, false otherwise. */
+    bool AllInOversizedClusters(SetType set)
+    {
+        if (set.Any() && !IsOversized()) return false;
+
+        auto todo = graph.Positions();
+        if (!set.IsSubsetOf(todo)) return false;
+
+        // Walk all clusters, and make sure all of `set` doesn't come from non-oversized clusters
+        while (todo.Any()) {
+            auto component = graph.FindConnectedComponent(todo);
+            bool is_oversized{component.Count() > max_cluster_count};
+            uint64_t component_size{0};
+            for (auto i : component) component_size += graph.FeeRate(i).size;
+            is_oversized |= component_size > max_cluster_size;
+            // Some element existed in a non-oversized cluster
+            if (!is_oversized && set.Overlaps(component)) {
+                return false;
+            }
+            todo -= component;
+        }
+        return true;
+    }
+
     void MakeModified(DepGraphIndex index)
     {
@@ -798,8 +822,16 @@ FUZZ_TARGET(txgraph)
                 }
                 auto removed_set = top_sim.MakeSet(removed);
-                // The removed set must contain all its own descendants.
                 for (auto simpos : removed_set) {
+                    // The removed set must contain all its own descendants.
                     assert(top_sim.graph.Descendants(simpos).IsSubsetOf(removed_set));
+
+                    // Nothing removed should have no ancestors and be undersized itself
+                    assert(!(top_sim.GetAncDesc(top_sim.GetRef(simpos), /*desc=*/false).Count() == 0 &&
+                        (uint64_t) top_sim.graph.FeeRate(simpos).size <= top_sim.max_cluster_size));
                 }
+
+                // Nothing from not-oversized-clusters should have been removed
+                assert(top_sim.AllInOversizedClusters(removed_set));
+
                 // Apply all removals to the simulation, and verify the result is no longer
                 // oversized. Don't query the real graph for oversizedness; it is compared

Taken, except for:

+                  assert(!(top_sim.GetAncDesc(top_sim.GetRef(simpos), /*desc=*/false).Count() == 0 &&
+                        (uint64_t) top_sim.graph.FeeRate(simpos).size <= top_sim.max_cluster_size));

because Count() == 0 will never be true (ancestors always includes the transaction itself), and the test fails when I change it to Count() == 1.

Ah, I see it now. Both variants of the Trim() algorithm can definitely remove these types of transactions.

f.e. if cluster limit is 2 and you have: TxA <- TxB <- TxC TxA <- TxE TxD <- TxE

You may select TxA+TxB only (after stopping at TxC), evicting TxC+TxD+TxE, if TxD's cfr is low.

If TxD's cfr is higher than TxB or TxC, then you could retain A+B+D

After a bunch of debugging, I was able to figure out a stronger check, if we constrain the scenario from a non-oversized to oversized transition with pending dependencies applied: https://github.com/instagibbs/bitcoin/tree/2025-05-applytrim

Added a commit with a test like this, with some changes. LMK what you think.

    const LinearizationChunking linchunking(m_depgraph, m_linearization);

Done.

nit: 3 out of the N fields are being set here, could we be specific which ones for clarity?

Done. Also organized the fields of struct TrimTxData a bit more logically, into "Populated by Cluster::AppendTxData" and "Only used internally in TxGraphImpl::Trim" sections.

nit: leave a comment that deps is also being added to here, briefly forgot

Done.

        // Append explicit deps, and sort it by child.

Done.

        // Fill m_deps_left in trim_data and initially populate trim_heap. Because of the sort above, all

Done.

        // Sort deps by parent by graph index. The order is unchanged from now on.

Done.

        // a map from GraphIndex to TrimTxData via locate_fn, and its ordering will not change anymore.

Done.

    Assume(!ret.empty());
    return ret;

Done.

This method's name aligns with its functionality.

However with the addition of this commit I think there is ambiguity currently between the size oversize, the count oversize and both. This makes it a bit confusing to follow.

maybe separate the two.

oversize should be for size.

overlimit or something like it for both

To be clear, Cluster::IsOversized() returns whether the Cluster is oversized in general. It's just the case that changes to clusters which bring it over the size/count limit are never applied, so the only way an actually materialized Cluster can be oversized is if it's a singleton transaction which is oversized on its own.

To be clear, Cluster::IsOversized() returns whether the Cluster is oversized in general.

huh, I missed thanks for the clarity. I think you can add this comment as well or anything that would make this explicit and clearer will be appreciated.

Expanded the comment to say that.

if there is nothing in the cluster? why should it be marked as needs_split_acceptable? Also I see no crashes after removing the new or condition.

You're right, this doesn't matter at all. The Cluster will just be deleted by Split anyway. Removed it.

assert that we trim when oversized ?

                assert(!removed.empty());
                auto removed_set = top_sim.MakeSet(removed);

Done.

check both ways

            }
            // No element exist in set and cluster is oversized 
            if (is_oversized && !set.Overlaps(component)){
               return false;
            }

Interesting, done! I have renamed the function to MatchesOversizedClusters and added a comment to clarify what it does.

I've also simplified it to just if (is_oversized != set.Overlaps(component)) return false;.

Indicate that it should not be called when their is an instance of block builder.

The GetBlockBuilder function already states "While the returned object exists, no mutators on the main graph are allowed.". I'm open to putting a comment to that effect on each of the mutators where it matters (incl. Trim), but I feel like it should be done consistently.

nano-nit while we're driving by: max_cluster_count should be > 0

Forgot to take this. Will leave open for now.

https://github.com/instagibbs/bitcoin/tree/2025-05-applytrim

Worked on a test attempts to cover the claim here. It ended up being more complicated than that (claim a bit wrong?) due to the lazy application of dependencies. For this property to hold, I believe you have to touch the TxGraph in any way that applies dependencies when undersized, then transition to oversized graph for the circular dependencies to not occur in the implied graph.

Without the dependencies applied, the linearization order can be "nonsensical", which then creates a contradictory dependency, iow cycle. This cycle ends up dropping sometimes the entire cluster ala

EhBGLQYGhDOENwYAr6+vr682AAYAAHoAAAAAAEr/EIQGBi0GBoQ0BjYQLUYGBoQzAEAzhAYGhDcG ADIABgAAMwAAMQCEBgY=

This can be tested by commenting out the CountDistinctClusters invocation in the new test.

The good news is this usage pattern is "natural", so in practice each new transaction (package) will have a TxGraph with all dependencies applied except for the new package. It's just weird and I'm unsure how to do better. Perhaps Trim could pre-emptively apply dependencies + FixLinearization for each grouped cluster.

In this graph, T2 is the implied parent of T1 thanks to to-be-applied dependencies not being applied yet, causing the trim heap to never get an entry:

I've written a test based on this, which randomly adds dependencies but in a "directed" sense that never introduces cycles (rather than just has 2 specific scenarios).

    // continues as long as the number or size of all picked transactions together does not exceed the

Done.

Perhaps worth noting (for future visitors) that these two limits have pretty different purposes even though they both contribute to the oversizedness property. Max cluster count helps bound linearization complexity, but max cluster size's purpose is largely external to TxGraph. It is only a parameter so that TxGraph can help enforce it.

Yes and no.

I've come to think of them as both being a feature that TxGraph offers to the mempool/net_processing code to help enforce its policy limits. So in this regard, they are equivalent.

The reason for the existence of the policy limits differs however: weight is there to bound how good/predictable transaction quality can be through linearization (avoiding binpacking), while count is there to keep the TxGraphImpl implementation efficient. But it isn't the case that this directly determines the count limit, otherwise e.g. more performant machines should have a higher limit for example.

Fair enough, I suppose they are both external policy limits!

in 221de30171acc1a20549079309b545612f727efb, do I understand correctly that we also don't ever expect OVERSIZED_SINGLETON to occur in the wild (i.e. we wouldn't accept any transactions above standard size in reorgs and max standard size > max cluster size), but TxGraph must handle this case as part of handling oversizedness in general?

I believe that's correct. @sdaftuar ?

From the commit message:

With this change, the responsibility for enforcing cluster size limits can be localized purely in TxGraph, without callers (and in particular, tests) needing to duplicate the enforcement for individual transactions.

micro-nit: main_only could be annotated and true to make it clear we're not looking at staging (even though it doesn't exist)

Done.

nit: can just assert this number rather than put in comment

I've added a computation for it, and assertion.

nit in 2b2df98747f

    // We only need to trim the middle bottom transaction to end up with 2 clusters each within cluster limits.

Done.

I tested that Trim() always removes oversized singletons, even if there are no clusters to be merged, using a simple unit test

diff --git a/src/test/txgraph_tests.cpp b/src/test/txgraph_tests.cpp
index 9f9ad04ff37..d90afd8819d 100644
--- a/src/test/txgraph_tests.cpp
+++ b/src/test/txgraph_tests.cpp
@@ -248,4 +248,43 @@ BOOST_AUTO_TEST_CASE(txgraph_trim_huge)
     BOOST_CHECK(graph->GetTransactionCount() >= (NUM_TOP_CHAINS * NUM_TX_PER_TOP_CHAIN * 99) / 100);
 }
 
+BOOST_AUTO_TEST_CASE(txgraph_trim_big_singletons)
+{
+    // Mempool consists of 100 singleton clusters; there are no dependencies. Some are oversized. Trim() should remove all of the oversized ones.
+    static constexpr int MAX_CLUSTER_COUNT = 64;
+    static constexpr int32_t MAX_CLUSTER_SIZE = 100'000;
+    static constexpr int NUM_TOTAL_TX = 100;
+
+    // Create a new graph for the test.
+    auto graph = MakeTxGraph(MAX_CLUSTER_COUNT, MAX_CLUSTER_SIZE);
+
+    // Add all transactions and store their Refs.
+    std::vector<TxGraph::Ref> refs;
+    refs.reserve(NUM_TOTAL_TX);
+
+    // Add all transactions. They are in individual clusters.
+    for (unsigned int i = 0; i < NUM_TOTAL_TX; ++i) {
+        // The 88th transaction is oversized.
+        // Every 20th transaction is oversized.
+        const FeePerWeight feerate{500 + i, (i == 88 || i % 20 == 0) ? MAX_CLUSTER_SIZE + 1 : 100};
+        refs.push_back(graph->AddTransaction(feerate));
+    }
+    graph->SanityCheck();
+
+    // Check that the graph is now oversized. This also forces the graph to
+    // group clusters and compute the oversized status.
+    BOOST_CHECK(graph->IsOversized(/*main_only=*/false));
+
+    // Call Trim() to remove transactions and bring the cluster back within limits.
+    auto removed_refs = graph->Trim();
+    graph->SanityCheck();
+    BOOST_CHECK_EQUAL(graph->GetTransactionCount(), NUM_TOTAL_TX - 6);
+    BOOST_CHECK(!graph->IsOversized(/*main_only=*/false));
+
+    // Check that all the oversized transactions were removed.
+    for (unsigned int i = 0; i < refs.size(); ++i) {
+        BOOST_CHECK_EQUAL(graph->Exists(refs[i]), i != 88 && i % 20 != 0);
+    }
+}
+
 BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/txgraph.cpp b/src/txgraph.cpp
index 1b29a05e534..26eef54d321 100644
--- a/src/txgraph.cpp
+++ b/src/txgraph.cpp
@@ -2745,7 +2745,7 @@ std::vector<TxGraph::Ref*> TxGraphImpl::Trim() noexcept
             trim_it->m_parent_count = trim_it->m_deps_left;
             // If this transaction has no unmet dependencies, and is not oversized, add it to the
             // heap (just append for now, the heapification happens below).
-            if (trim_it->m_deps_left == 0 && trim_it->m_tx_size <= m_max_cluster_size) {
+            if (trim_it->m_deps_left == 0) {
                 trim_heap.push_back(trim_it);
             }
         }
@@ -2813,7 +2813,7 @@ std::vector<TxGraph::Ref*> TxGraphImpl::Trim() noexcept
                 new_size += ptr->m_uf_size;
             }
             // Skip the entry if this would violate any limit.
-            if (new_count > m_max_cluster_count || new_size > m_max_cluster_size) continue;
+            if (new_count > m_max_cluster_count) continue;
 
             // Union the partitions this transaction and all its dependencies are in together.
             auto rep = &entry;

Great, incorporated. I'm assuming the txgraph.cpp changes above are to demonstrate the test works?

Yes, those shouldn't be included!

fwiw I commented out the IsOversized check and the test passes still as expected, with singletons

True, there isn't actually anything to group in this test. Just copied from the other tests.

We start being oversized at i = 24 iteration.