cluster mempool: add txgraph diagrams/mining/eviction #31444

1364+        // Figure out which elements need to be moved before elem.
1365+        SetType place_before = done & depgraph.Ancestors(elem);
1366+        // Find which position to place elem in (updating j), continuously moving the elements
1367+        // in between forward.
1368+        while (place_before.Any()) {
1369+            // j cannot be 0 here; if it was, then there was necessarily nothing earlier which

651+{
652+    auto chunk_feerates = ChunkLinearization(m_depgraph, m_linearization);
653+    for (const auto& feerate : chunk_feerates) {
654+        ret.push_back(feerate);
655+    }
656+}

1864@@ -1854,6 +1865,33 @@ TxGraph::GraphIndex TxGraphImpl::CountDistinctClusters(std::span<const Ref* cons
1865     return ret;
1866 }
1867 
1868+std::pair<std::vector<FeeFrac>, std::vector<FeeFrac>> TxGraphImpl::GetMainStagingDiagrams() noexcept
1869+{
1870+    Assume(m_clustersets.size() >= 2);

1879+    for (Cluster* cluster : main_clusters) {
1880+        cluster->AppendChunkFeerates(main_feerates);
1881+    }
1882+    // Do the same for the Clusters in staging themselves.
1883+    const auto& staging = m_clustersets.back();
1884+    for (int quality = 0; quality < int(QualityLevel::NONE); ++quality) {

1906@@ -1897,6 +1907,32 @@ TxGraph::GraphIndex TxGraphImpl::CountDistinctClusters(std::span<const Ref* cons
1907     return ret;
1908 }
1909 
1910+std::pair<std::vector<FeeFrac>, std::vector<FeeFrac>> TxGraphImpl::GetMainStagingDiagrams() noexcept
1911+{
1912+    Assume(m_staging_clusterset.has_value());
1913+    MakeAllAcceptable(0);

1926+        for (const auto& cluster : m_staging_clusterset->m_clusters[quality]) {
1927+            cluster->AppendChunkFeerates(staging_feerates);
1928+        }
1929+    }
1930+    // Sort both by decreasing feerate to obtain diagrams, and return them.
1931+    std::sort(main_feerates.begin(), main_feerates.end(), [](auto& a, auto& b) { return a >> b; });

730+                assert(FeeRateCompare(main_cmp_diagram[i], main_cmp_diagram[i - 1]) <= 0);
731+            }
732+            for (size_t i = 1; i < stage_cmp_diagram.size(); ++i) {
733+                assert(FeeRateCompare(stage_cmp_diagram[i], stage_cmp_diagram[i - 1]) <= 0);
734+            }
735+            // Apply total ordering on the feerate diagrams to make them comparable (the exact

754+                                std::inserter(missing_stage_cmp, missing_stage_cmp.end()),
755+                                std::greater{});
756+            assert(stage_cmp_diagram.size() + missing_stage_cmp.size() == stage_diagram.size());
757+            // The missing chunks must be equal across main & staging (otherwise they couldn't have
758+            // been omitted).
759+            assert(missing_main_cmp == missing_stage_cmp);

195@@ -196,6 +196,10 @@ class TxGraph
196     /** Construct a block builder, drawing chunks in order, from the main graph, which cannot be
197      *  oversized. While the returned object exists, no mutators on the main graph are allowed. */
198     virtual std::unique_ptr<BlockBuilder> GetBlockBuilder() noexcept = 0;
199+    /** Get the last chunk in the main graph, i.e., the last chunk that would be returned by a

292@@ -292,6 +293,8 @@ class TxGraphImpl final : public TxGraph
293     ChunkIndex m_chunkindex;
294     /** Number of index-observing objects in existence (BlockBuilderImpl). */
295     size_t m_chunkindex_observers{0};
296+    /** Cache of discarded ChunkIndex node handles. */

161@@ -162,6 +162,10 @@ class TxGraph
162      *  main clusters are counted. Refs that do not exist in the queried graph are ignored. The
163      *  queried graph must not be oversized. */
164     virtual GraphIndex CountDistinctClusters(std::span<const Ref* const>, bool main_only = false) noexcept = 0;
165+    /** Get feerate diagrams for both main and staging (which must both exist and not be
166+     *  oversized), ignoring unmodified components in both. Use FeeFrac rather than FeePerWeight
167+     *  so CompareChunks is usable without type-conversion. */
168+    virtual std::pair<std::vector<FeeFrac>, std::vector<FeeFrac>> GetMainStagingDiagrams() noexcept = 0;

1931+            cluster->AppendChunkFeerates(staging_feerates);
1932+        }
1933+    }
1934+    // Sort both by decreasing feerate to obtain diagrams, and return them.
1935+    std::sort(main_feerates.begin(), main_feerates.end(), [](auto& a, auto& b) { return a >> b; });
1936+    std::sort(staging_feerates.begin(), staging_feerates.end(), [](auto& a, auto& b) { return a >> b; });

832+        std::reverse(chunk.begin(), chunk.end());
833+        auto [worst_chunk, worst_chunk_feerate] = real->GetWorstMainChunk();
834+        assert(chunk == worst_chunk);
835+        assert(chunk_feerate == worst_chunk_feerate);
836+
837+        // Check that the implied ordering gives rise to a combined diagram that matches the

834+        assert(chunk == worst_chunk);
835+        assert(chunk_feerate == worst_chunk_feerate);
836+
837+        // Check that the implied ordering gives rise to a combined diagram that matches the
838+        // diagram constructed from the individual cluster linearization chunkings.
839+        auto main_diagram = get_diagram_fn(true);

864+                                main_cmp_diagram.begin(), main_cmp_diagram.end(),
865+                                std::inserter(missing_main_cmp, missing_main_cmp.end()),
866+                                std::greater{});
867+            assert(main_cmp_diagram.size() + missing_main_cmp.size() == main_diagram.size());
868+            // Do the same for chunks in stage_diagram missign from stage_cmp_diagram.
869+            auto stage_diagram = get_diagram_fn(false);

266+    /** Comparator for ChunkData objects in mining order. */
267+    class ChunkOrder
268+    {
269+        const TxGraphImpl* const m_graph;
270+    public:
271+        explicit ChunkOrder(const TxGraphImpl* graph) : m_graph(graph) {}

863+            std::set_difference(main_diagram.begin(), main_diagram.end(),
864+                                main_cmp_diagram.begin(), main_cmp_diagram.end(),
865+                                std::inserter(missing_main_cmp, missing_main_cmp.end()),
866+                                std::greater{});
867+            assert(main_cmp_diagram.size() + missing_main_cmp.size() == main_diagram.size());
868+            // Do the same for chunks in stage_diagram missign from stage_cmp_diagram.

183+        /** Determine whether there are more transactions to be included. */
184+        explicit operator bool() noexcept { return m_current_chunk.has_value(); }
185+        /** Get the chunk that is currently suggested to be included. */
186+        const std::span<Ref*>& GetCurrentChunk() noexcept { return m_current_chunk->first; }
187+        /** Get the feerate of the currently suggested chunk. */
188+        const FeePerWeight& GetCurrentChunkFeerate() noexcept { return m_current_chunk->second; }

289@@ -289,6 +290,8 @@ class TxGraphImpl final : public TxGraph
290 
291     /** Index of ChunkData objects. */
292     ChunkIndex m_chunkindex;
293+    /** Number of index-observing objects in existence (BlockBuilderImpl). */
294+    size_t m_chunkindex_observers{0};

433@@ -375,6 +434,7 @@ class TxGraphImpl final : public TxGraph
434     {
435         auto& entry = m_entries[idx];
436         Assume(entry.m_ref != nullptr);
437+        Assume(m_chunkindex_observers == 0 || !entry.m_locator[0].IsPresent());

301+            auto ref = sim.GetRef(i);
302+            clusters.insert(real->GetCluster(*ref, main_only));
303+        }
304+        // Compute the chunkings of each (deduplicated) cluster.
305+        size_t num_tx{0};
306+        std::vector<FeeFrac> ret;

315+        }
316+        // Verify the number of transactions after deduplicating clusters. This implicitly verifies
317+        // that GetCluster on each element of a cluster reports the cluster transactions in the same
318+        // order.
319+        assert(num_tx == sim.GetTransactionCount());
320+        // Sort by feerate (we don't care about respecting ordering within clusters, as these are

761+            // The missing part must include at least all transactions in staging which have not been
762+            // modified, or been in a cluster together with modified transactions, since they were
763+            // copied from main. Note that due to the reordering of removals w.r.t. dependency
764+            // additions, it is possible that the real implementation found more unaffected things.
765+            FeeFrac missing_real;
766+            for (const auto& feerate : missing_main_cmp) missing_real += feerate;

251+    struct ChunkData
252+    {
253+        /** The Entry which is the last transaction of the chunk. */
254+        mutable GraphIndex m_graph_index;
255+        /** How many transactions the chunk contains. */
256+        LinearizationIndex m_chunk_count;

345@@ -303,6 +346,8 @@ class TxGraphImpl final : public TxGraph
346     {
347         /** Pointer to the corresponding Ref object if any, or nullptr if unlinked. */
348         Ref* m_ref{nullptr};
349+        /** Iterator to the corresponding ChunkData, if any. */

286+
287+    /** Definition for the mining index type. */
288+    using ChunkIndex = std::set<ChunkData, ChunkOrder>;
289+
290+    /** Index of ChunkData objects. */
291+    ChunkIndex m_chunkindex;

579@@ -524,17 +580,25 @@ void Cluster::Updated(TxGraphImpl& graph) noexcept
580         // Iterate over the chunks.
581         for (unsigned chunk_idx = 0; chunk_idx < chunking.NumChunksLeft(); ++chunk_idx) {
582             auto chunk = chunking.GetChunk(chunk_idx);
583-            Assume(chunk.transactions.Any());
584+            auto chunk_count = chunk.transactions.Count();

147@@ -148,7 +148,7 @@ class Cluster
148      *  union of their descendants to output. */
149     void GetDescendantRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept;
150     /** Get a vector of Refs for all elements of this Cluster, in linearization order. */
151-    std::vector<TxGraph::Ref*> GetClusterRefs(const TxGraphImpl& graph) noexcept;
152+    void GetClusterRefs(TxGraphImpl& graph, std::span<TxGraph::Ref*> range, LinearizationIndex start_pos) noexcept;

186+         *  the same cluster as the current one will not be reported anymore. */
187+        virtual void Skip() noexcept = 0;
188+    };
189+
190+    /** Construct a block builder, drawing chunks in order, from the main graph, which cannot be
191+     *  oversized. While the returned object exists, no mutators on the main graph are allowed. */

797@@ -715,6 +798,27 @@ FUZZ_TARGET(txgraph)
798             }
799         }
800 
801+        // The same order should be obtained through a BlockBuilder, if nothing is skipped.

540+    /** Which TxGraphImpl this object is doing block building for. It will have its
541+     *  m_chunkindex_observers incremented as long as this BlockBuilderImpl exists. */
542+    TxGraphImpl* const m_graph;
543+    /** Clusters which we're not including further transactions from. */
544+    std::set<Cluster*> m_excluded_clusters;
545+    /** Iterator to the current chunk (after the current one) in the chunk index. end() if nothing

181+        /** Get the chunk that is currently suggested to be included, plus its feerate, if any. */
182+        virtual std::optional<std::pair<std::vector<Ref*>, FeePerWeight>> GetCurrentChunk() noexcept = 0;
183+        /** Mark the current chunk as included, and progress to the next one. */
184+        virtual void Include() noexcept = 0;
185+        /** Mark the current chunk as skipped, and progress to the next one. Further chunks from
186+         *  the same cluster as the current one will not be reported anymore. */

178+    public:
179+        /** Support safe inheritance. */
180+        virtual ~BlockBuilder() = default;
181+        /** Get the chunk that is currently suggested to be included, plus its feerate, if any. */
182+        virtual std::optional<std::pair<std::vector<Ref*>, FeePerWeight>> GetCurrentChunk() noexcept = 0;
183+        /** Mark the current chunk as included, and progress to the next one. */

189@@ -190,6 +190,11 @@ class TxGraph
190     /** Construct a block builder, drawing chunks in order, from the main graph, which cannot be
191      *  oversized. While the returned object exists, no mutators on the main graph are allowed. */
192     virtual std::unique_ptr<BlockBuilder> GetBlockBuilder() noexcept = 0;
193+    /** Get the last chunk in the main graph, i.e., the last chunk that would be returned by a
194+     *  BlockBuilder created now, together with its feerate. The chunk is returned in
195+     *  reverse-topological order, so every element is preceded by all its descendants. The main
196+     *  graph must not be oversized. If the graph is empty, {} is returned. */

748+                // GetWorstMainChunk.
749+                auto [worst_chunk, worst_chunk_feerate] = real->GetWorstMainChunk();
750+                // Just do some sanity checks here. Consistency with GetBlockBuilder is checked
751+                // below.
752+                if (main_sim.GetTransactionCount() == 0) {
753+                    assert(worst_chunk.empty());

846+            last_chunk_feerate = chunk->second;
847             builder->Include();
848         }
849         assert(vec_builder == vec1);
850 
851+        // The last chunk returned by the BlockBuilder must match GetWorstMainChunk, in reverse.

147@@ -148,8 +148,9 @@ class Cluster
148     /** Process elements from the front of args that apply to this cluster, and append Refs for the
149      *  union of their descendants to output. */
150     void GetDescendantRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept;
151-    /** Get a vector of Refs for all elements of this Cluster, in linearization order. */
152-    void GetClusterRefs(TxGraphImpl& graph, std::span<TxGraph::Ref*> range, LinearizationIndex start_pos) noexcept;
153+    /** Get a vector of Refs for all elements of this Cluster, in linearization order. Returns
154+     *  the range ends at the end of the cluster. */

1676@@ -1675,6 +1677,8 @@ void Cluster::GetClusterRefs(TxGraphImpl& graph, std::span<TxGraph::Ref*> range,
1677         Assume(entry.m_ref != nullptr);
1678         ref = entry.m_ref;
1679     }
1680+    // Return whether this was the end of the Cluster.
1681+    return start_pos == m_linearization.size();

147@@ -148,8 +148,9 @@ class Cluster
148     /** Process elements from the front of args that apply to this cluster, and append Refs for the
149      *  union of their descendants to output. */
150     void GetDescendantRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept;
151-    /** Get a vector of Refs for all elements of this Cluster, in linearization order. */
152-    void GetClusterRefs(TxGraphImpl& graph, std::span<TxGraph::Ref*> range, LinearizationIndex start_pos) noexcept;
153+    /** Get a vector of Refs for all elements of this Cluster, in linearization order. Returns

2343-            Assume(cluster == m_cur_cluster);
2344+            ret->first.resize(chunk_data.m_chunk_count);
2345+            auto start_pos = chunk_end_entry.m_main_lin_index + 1 - chunk_data.m_chunk_count;
2346+            bool is_end = cluster->GetClusterRefs(*m_graph, ret->first, start_pos);
2347+            if (is_end) {
2348+                m_cur_cluster = nullptr;

161@@ -162,6 +162,10 @@ class TxGraph
162      *  main clusters are counted. Refs that do not exist in the queried graph are ignored. The
163      *  queried graph must not be oversized. */
164     virtual GraphIndex CountDistinctClusters(std::span<const Ref* const>, bool main_only = false) noexcept = 0;
165+    /** Get feerate diagrams for both main and staging (which must both exist and not be

581@@ -524,17 +582,25 @@ void Cluster::Updated(TxGraphImpl& graph) noexcept
582         // Iterate over the chunks.
583         for (unsigned chunk_idx = 0; chunk_idx < chunking.NumChunksLeft(); ++chunk_idx) {

2297+        ret.emplace();
2298+        const auto& chunk_data = *m_cur_iter;
2299+        const auto& chunk_end_entry = m_graph->m_entries[chunk_data.m_graph_index];
2300+        ret->first.resize(chunk_data.m_chunk_count);
2301+        auto start_pos = chunk_end_entry.m_main_lin_index + 1 - chunk_data.m_chunk_count;
2302+        m_cur_cluster->GetClusterRefs(*m_graph, ret->first, start_pos);

763+            assert(missing_main_cmp == missing_stage_cmp);
764+
765+            // The missing part must include at least all transactions in staging which have not been
766+            // modified, or been in a cluster together with modified transactions, since they were
767+            // copied from main. Note that due to the reordering of removals w.r.t. dependency
768+            // additions, it is possible that the real implementation found more unaffected things.

1631-    // Translate all transactions in the Cluster (in linearization order) to Refs.
1632-    for (auto idx : m_linearization) {
1633-        const auto& entry = graph.m_entries[m_mapping[idx]];
1634+    // Translate the transactions in the Cluster (in linearization order, starting at start_pos in
1635+    // the linearization) to Refs, and fill them in range.
1636+    for (auto& ref : range) {

561+    /** Which TxGraphImpl this object is doing block building for. It will have its
562+     *  m_main_chunkindex_observers incremented as long as this BlockBuilderImpl exists. */
563+    TxGraphImpl* const m_graph;
564+    /** Clusters which we're not including further transactions from. */
565+    std::set<Cluster*> m_excluded_clusters;
566+    /** Iterator to the current chunk (after the current one) in the chunk index. end() if nothing

653+                auto diagram_gain = sum_staged - sum_main;
654+                auto real_gain = sims[1].SumAll() - sims[0].SumAll();
655+                // Just check that the total fee gained/lost and size gained/lost according to the
656+                // diagram matches the difference in these values in the simulated graph. A more
657+                // complete check of the GetMainStagingDiagrams result is performed at the end.
658+                assert(diagram_gain == real_gain);

660+                for (size_t i = 1; i < main_diagram.size(); ++i) {
661+                    assert(FeeRateCompare(main_diagram[i], main_diagram[i - 1]) <= 0);
662+                }
663+                for (size_t i = 1; i < staged_diagram.size(); ++i) {
664+                    assert(FeeRateCompare(staged_diagram[i], staged_diagram[i - 1]) <= 0);
665+                }

716@@ -639,6 +717,62 @@ FUZZ_TARGET(txgraph)
717                 assert(FeeRateCompare(after_feerate, pos_feerate) <= 0);
718             }
719         }
720+
721+        // Check that the implied ordering gives rise to a combined diagram that matches the
722+        // diagram constructed from the individual cluster linearization chunkings.
723+        auto main_real_diagram = get_diagram_fn(/*main_only=*/true);
724+        auto main_implied_diagram = ChunkLinearization(sims[0].graph, vec1);

722+        // diagram constructed from the individual cluster linearization chunkings.
723+        auto main_real_diagram = get_diagram_fn(/*main_only=*/true);
724+        auto main_implied_diagram = ChunkLinearization(sims[0].graph, vec1);
725+        assert(CompareChunks(main_real_diagram, main_implied_diagram) == 0);
726+
727+        if (sims.size() >= 2 && !sims[1].IsOversized()) {

738+            // Treat the diagrams as sets of chunk feerates, and sort them in the same way so that
739+            // std::set_difference can be used on them below. The exact ordering does not matter
740+            // here, but it has to be consistent with the one used in main_diagram and
741+            // stage_diagram).
742+            std::sort(main_cmp_diagram.begin(), main_cmp_diagram.end(), std::greater{});
743+            std::sort(stage_cmp_diagram.begin(), stage_cmp_diagram.end(), std::greater{});

736+                assert(FeeRateCompare(stage_cmp_diagram[i], stage_cmp_diagram[i - 1]) <= 0);
737+            }
738+            // Treat the diagrams as sets of chunk feerates, and sort them in the same way so that
739+            // std::set_difference can be used on them below. The exact ordering does not matter
740+            // here, but it has to be consistent with the one used in main_diagram and
741+            // stage_diagram).

1925@@ -1916,6 +1926,32 @@ TxGraph::GraphIndex TxGraphImpl::CountDistinctClusters(std::span<const Ref* cons
1926     return ret;
1927 }
1928 
1929+std::pair<std::vector<FeeFrac>, std::vector<FeeFrac>> TxGraphImpl::GetMainStagingDiagrams() noexcept
1930+{
1931+    Assume(m_staging_clusterset.has_value());

177+        /** Make constructor non-public (use TxGraph::GetBlockBuilder()). */
178+        BlockBuilder() noexcept = default;
179+    public:
180+        /** Support safe inheritance. */
181+        virtual ~BlockBuilder() = default;
182+        /** Get the chunk that is currently suggested to be included, plus its feerate, if any. */

593+    void Skip() noexcept final;
594+};
595+
596+void TxGraphImpl::ClearChunkData(Entry& entry) noexcept
597+{
598+    if (entry.m_main_chunkindex_iterator != m_main_chunkindex.end()) {