Inside Bitcoin

251/** An implementation of Cluster that uses a DepGraph and vectors, to support arbitrary numbers of
252 *  transactions up to MAX_CLUSTER_COUNT_LIMIT. */
253class GenericClusterImpl final : public Cluster
254{
255    friend class TxGraphImpl;
256    /** The DepGraph for this cluster, holding all feerates, and ancestors/descendants. */
257    DepGraph<SetType> m_depgraph;
258    /** m_mapping[i] gives the GraphIndex for the position i transaction in m_depgraph. Values for
259     *  positions i that do not exist in m_depgraph shouldn't ever be accessed and thus don't
260     *  matter. m_mapping.size() equals m_depgraph.PositionRange(). */
261    std::vector<GraphIndex> m_mapping;
262    /** The current linearization of the cluster. m_linearization.size() equals
263     *  m_depgraph.TxCount(). This is always kept topological. */
264    std::vector<DepGraphIndex> m_linearization;
265
266public:
267    /** The smallest number of transactions this Cluster implementation is intended for. */
268    static constexpr DepGraphIndex MIN_INTENDED_TX_COUNT{2};
269    /** The largest number of transactions this Cluster implementation supports. */
270    static constexpr DepGraphIndex MAX_TX_COUNT{SetType::Size()};
271
272    GenericClusterImpl() noexcept = delete;
273    /** Construct an empty GenericClusterImpl. */
274    explicit GenericClusterImpl(uint64_t sequence) noexcept;
275
276    size_t TotalMemoryUsage() const noexcept final;
277    constexpr DepGraphIndex GetMinIntendedTxCount() const noexcept final { return MIN_INTENDED_TX_COUNT; }
278    constexpr DepGraphIndex GetMaxTxCount() const noexcept final { return MAX_TX_COUNT; }
279    DepGraphIndex GetDepGraphIndexRange() const noexcept final { return m_depgraph.PositionRange(); }
280    LinearizationIndex GetTxCount() const noexcept final { return m_linearization.size(); }
281    uint64_t GetTotalTxSize() const noexcept final;
282    GraphIndex GetClusterEntry(DepGraphIndex index) const noexcept final { return m_mapping[index]; }
283    DepGraphIndex AppendTransaction(GraphIndex graph_idx, FeePerWeight feerate) noexcept final;
284    void AddDependencies(SetType parents, DepGraphIndex child) noexcept final;
285    void ExtractTransactions(const std::function<void (DepGraphIndex, GraphIndex, FeePerWeight)>& visit1_fn, const std::function<void (DepGraphIndex, GraphIndex, SetType)>& visit2_fn) noexcept final;
286    int GetLevel(const TxGraphImpl& graph) const noexcept final;
287    void UpdateMapping(DepGraphIndex cluster_idx, GraphIndex graph_idx) noexcept final { m_mapping[cluster_idx] = graph_idx; }
288    void Updated(TxGraphImpl& graph, int level, bool rename) noexcept final;
289    void RemoveChunkData(TxGraphImpl& graph) noexcept final;
290    Cluster* CopyToStaging(TxGraphImpl& graph) const noexcept final;
291    void GetConflicts(const TxGraphImpl& graph, std::vector<Cluster*>& out) const noexcept final;
292    void MakeStagingTransactionsMissing(TxGraphImpl& graph) noexcept final;
293    void Clear(TxGraphImpl& graph, int level) noexcept final;
294    void MoveToMain(TxGraphImpl& graph) noexcept final;
295    void Compact() noexcept final;
296    void ApplyRemovals(TxGraphImpl& graph, int level, std::span<GraphIndex>& to_remove) noexcept final;
297    [[nodiscard]] bool Split(TxGraphImpl& graph, int level) noexcept final;
298    void Merge(TxGraphImpl& graph, int level, Cluster& cluster) noexcept final;
299    void ApplyDependencies(TxGraphImpl& graph, int level, std::span<std::pair<GraphIndex, GraphIndex>> to_apply) noexcept final;
300    std::pair<uint64_t, bool> Relinearize(TxGraphImpl& graph, int level, uint64_t max_cost) noexcept final;
301    void AppendChunkFeerates(std::vector<FeeFrac>& ret) const noexcept final;
302    uint64_t AppendTrimData(std::vector<TrimTxData>& ret, std::vector<std::pair<GraphIndex, GraphIndex>>& deps) const noexcept final;
303    void GetAncestorRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept final;
304    void GetDescendantRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept final;
305    bool GetClusterRefs(TxGraphImpl& graph, std::span<TxGraph::Ref*> range, LinearizationIndex start_pos) noexcept final;
306    FeePerWeight GetIndividualFeerate(DepGraphIndex idx) noexcept final;
307    void SetFee(TxGraphImpl& graph, int level, DepGraphIndex idx, int64_t fee) noexcept final;
308    void SanityCheck(const TxGraphImpl& graph, int level) const final;
309};
310
311/** An implementation of Cluster that only supports 1 transaction. */
312class SingletonClusterImpl final : public Cluster
313{
314    friend class TxGraphImpl;
315
316    /** The feerate of the (singular) transaction in this Cluster. */
317    FeePerWeight m_feerate;
318    /** Constant to indicate that this Cluster is empty. */
319    static constexpr auto NO_GRAPH_INDEX = GraphIndex(-1);
320    /** The GraphIndex of the transaction. NO_GRAPH_INDEX if this Cluster is empty. */
321    GraphIndex m_graph_index = NO_GRAPH_INDEX;
322
323public:
324    /** The smallest number of transactions this Cluster implementation is intended for. */
325    static constexpr DepGraphIndex MIN_INTENDED_TX_COUNT{1};
326    /** The largest number of transactions this Cluster implementation supports. */
327    static constexpr DepGraphIndex MAX_TX_COUNT{1};
328
329    SingletonClusterImpl() noexcept = delete;
330    /** Construct an empty SingletonClusterImpl. */
331    explicit SingletonClusterImpl(uint64_t sequence) noexcept : Cluster(sequence) {}
332
333    size_t TotalMemoryUsage() const noexcept final;
334    constexpr DepGraphIndex GetMinIntendedTxCount() const noexcept final { return MIN_INTENDED_TX_COUNT; }
335    constexpr DepGraphIndex GetMaxTxCount() const noexcept final { return MAX_TX_COUNT; }
336    LinearizationIndex GetTxCount() const noexcept final { return m_graph_index != NO_GRAPH_INDEX; }
337    DepGraphIndex GetDepGraphIndexRange() const noexcept final { return GetTxCount(); }
338    uint64_t GetTotalTxSize() const noexcept final { return GetTxCount() ? m_feerate.size : 0; }
339    GraphIndex GetClusterEntry(DepGraphIndex index) const noexcept final { Assume(index == 0); Assume(GetTxCount()); return m_graph_index; }
340    DepGraphIndex AppendTransaction(GraphIndex graph_idx, FeePerWeight feerate) noexcept final;
341    void AddDependencies(SetType parents, DepGraphIndex child) noexcept final;
342    void ExtractTransactions(const std::function<void (DepGraphIndex, GraphIndex, FeePerWeight)>& visit1_fn, const std::function<void (DepGraphIndex, GraphIndex, SetType)>& visit2_fn) noexcept final;
343    int GetLevel(const TxGraphImpl& graph) const noexcept final;
344    void UpdateMapping(DepGraphIndex cluster_idx, GraphIndex graph_idx) noexcept final { Assume(cluster_idx == 0); m_graph_index = graph_idx; }
345    void Updated(TxGraphImpl& graph, int level, bool rename) noexcept final;
346    void RemoveChunkData(TxGraphImpl& graph) noexcept final;
347    Cluster* CopyToStaging(TxGraphImpl& graph) const noexcept final;
348    void GetConflicts(const TxGraphImpl& graph, std::vector<Cluster*>& out) const noexcept final;
349    void MakeStagingTransactionsMissing(TxGraphImpl& graph) noexcept final;
350    void Clear(TxGraphImpl& graph, int level) noexcept final;
351    void MoveToMain(TxGraphImpl& graph) noexcept final;
352    void Compact() noexcept final;
353    void ApplyRemovals(TxGraphImpl& graph, int level, std::span<GraphIndex>& to_remove) noexcept final;
354    [[nodiscard]] bool Split(TxGraphImpl& graph, int level) noexcept final;
355    void Merge(TxGraphImpl& graph, int level, Cluster& cluster) noexcept final;
356    void ApplyDependencies(TxGraphImpl& graph, int level, std::span<std::pair<GraphIndex, GraphIndex>> to_apply) noexcept final;
357    std::pair<uint64_t, bool> Relinearize(TxGraphImpl& graph, int level, uint64_t max_cost) noexcept final;
358    void AppendChunkFeerates(std::vector<FeeFrac>& ret) const noexcept final;
359    uint64_t AppendTrimData(std::vector<TrimTxData>& ret, std::vector<std::pair<GraphIndex, GraphIndex>>& deps) const noexcept final;
360    void GetAncestorRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept final;
361    void GetDescendantRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept final;
362    bool GetClusterRefs(TxGraphImpl& graph, std::span<TxGraph::Ref*> range, LinearizationIndex start_pos) noexcept final;
363    FeePerWeight GetIndividualFeerate(DepGraphIndex idx) noexcept final;
364    void SetFee(TxGraphImpl& graph, int level, DepGraphIndex idx, int64_t fee) noexcept final;
365    void SanityCheck(const TxGraphImpl& graph, int level) const final;
366};
367
368/** The transaction graph, including staged changes.
369 *
370 * The overall design of the data structure consists of 3 interlinked representations:
371 * - The transactions (held as a vector of TxGraphImpl::Entry inside TxGraphImpl).
372 * - The clusters (Cluster objects in per-quality vectors inside TxGraphImpl::ClusterSet).
373 * - The Refs (TxGraph::Ref objects, held externally by users of the TxGraph class)
374 *
375 * The Clusters are kept in one or two ClusterSet objects, one for the "main" graph, and one for
376 * the proposed changes ("staging"). If a transaction occurs in both, they share the same Entry,
377 * but there will be a separate Cluster per graph.
378 *
379 * Clusters and Refs contain the index of the Entry objects they refer to, and the Entry objects
380 * refer back to the Clusters and Refs the corresponding transaction is contained in.
381 *
382 * While redundant, this permits moving all of them independently, without invalidating things
383 * or costly iteration to fix up everything:
384 * - Entry objects can be moved to fill holes left by removed transactions in the Entry vector
385 *   (see TxGraphImpl::Compact).
386 * - Clusters can be rewritten continuously (removals can cause them to split, new dependencies
387 *   can cause them to be merged).
388 * - Ref objects can be held outside the class, while permitting them to be moved around, and
389 *   inherited from.
390 */
391class TxGraphImpl final : public TxGraph
392{
393    friend class Cluster;
394    friend class SingletonClusterImpl;
395    friend class GenericClusterImpl;
396    friend class BlockBuilderImpl;
397private:
398    /** Internal RNG. */
399    FastRandomContext m_rng;
400    /** This TxGraphImpl's maximum cluster count limit. */
401    const DepGraphIndex m_max_cluster_count;
402    /** This TxGraphImpl's maximum cluster size limit. */
403    const uint64_t m_max_cluster_size;
404    /** The amount of linearization work needed per cluster to be considered acceptable. */
405    const uint64_t m_acceptable_cost;
406    /** Fallback ordering for transactions. */
407    const std::function<std::strong_ordering(const TxGraph::Ref&, const TxGraph::Ref&)> m_fallback_order;
408
409    /** Information about one group of Clusters to be merged. */
410    struct GroupEntry
411    {
412        /** Where the clusters to be merged start in m_group_clusters. */
413        uint32_t m_cluster_offset;
414        /** How many clusters to merge. */
415        uint32_t m_cluster_count;
416        /** Where the dependencies for this cluster group in m_deps_to_add start. */
417        uint32_t m_deps_offset;
418        /** How many dependencies to add. */
419        uint32_t m_deps_count;
420    };
421
422    /** Information about all groups of Clusters to be merged. */
423    struct GroupData
424    {
425        /** The groups of Clusters to be merged. */
426        std::vector<GroupEntry> m_groups;
427        /** Which clusters are to be merged. GroupEntry::m_cluster_offset indexes into this. */
428        std::vector<Cluster*> m_group_clusters;
429    };
430
431    /** The collection of all Clusters in main or staged. */
432    struct ClusterSet
433    {
434        /** The vectors of clusters, one vector per quality level. ClusterSetIndex indexes into each. */
435        std::array<std::vector<std::unique_ptr<Cluster>>, int(QualityLevel::NONE)> m_clusters;
436        /** Which removals have yet to be applied. */
437        std::vector<GraphIndex> m_to_remove;
438        /** Which dependencies are to be added ((parent,child) pairs). GroupData::m_deps_offset indexes
439         *  into this. */
440        std::vector<std::pair<GraphIndex, GraphIndex>> m_deps_to_add;
441        /** Information about the merges to be performed, if known. */
442        std::optional<GroupData> m_group_data = GroupData{};
443        /** Which entries were removed in this ClusterSet (so they can be wiped on abort). This
444         *  includes all entries which have an (R) removed locator at this level (staging only),
445         *  plus optionally any transaction in m_unlinked. */
446        std::vector<GraphIndex> m_removed;
447        /** Total number of transactions in this graph (sum of all transaction counts in all
448         *  Clusters, and for staging also those inherited from the main ClusterSet). */
449        GraphIndex m_txcount{0};
450        /** Total number of individually oversized transactions in the graph. */
451        GraphIndex m_txcount_oversized{0};
452        /** Whether this graph is oversized (if known). */
453        std::optional<bool> m_oversized{false};
454        /** The combined TotalMemoryUsage of all clusters in this level (only Clusters that
455         *  are materialized; in staging, implicit Clusters from main are not counted), */
456        size_t m_cluster_usage{0};
457
458        ClusterSet() noexcept = default;
459    };
460
461    /** The main ClusterSet. */
462    ClusterSet m_main_clusterset;
463    /** The staging ClusterSet, if any. */
464    std::optional<ClusterSet> m_staging_clusterset;
465    /** Next sequence number to assign to created Clusters. */
466    uint64_t m_next_sequence_counter{0};
467
468    /** Information about a chunk in the main graph. */
469    struct ChunkData
470    {
471        /** The Entry which is the last transaction of the chunk. */
472        mutable GraphIndex m_graph_index;
473        /** How many transactions the chunk contains (-1 = singleton tail of cluster). */
474        LinearizationIndex m_chunk_count;
475
476        ChunkData(GraphIndex graph_index, LinearizationIndex chunk_count) noexcept :
477            m_graph_index{graph_index}, m_chunk_count{chunk_count} {}
478    };
479
480    /** Compare two Cluster* by their m_sequence value (while supporting nullptr). */
481    static std::strong_ordering CompareClusters(Cluster* a, Cluster* b) noexcept
482    {
483        // The nullptr pointer compares before everything else.
484        if (a == nullptr || b == nullptr) {
485            return (a != nullptr) <=> (b != nullptr);
486        }
487        // If neither pointer is nullptr, compare the Clusters' sequence numbers.
488        Assume(a == b || a->m_sequence != b->m_sequence);
489        return a->m_sequence <=> b->m_sequence;
490    }
491
492    /** Compare two entries (which must both exist within the main graph). */
493    std::strong_ordering CompareMainTransactions(GraphIndex a, GraphIndex b) const noexcept
494    {
495        if (a == b) return std::strong_ordering::equal;
496        Assume(a < m_entries.size() && b < m_entries.size());
497        const auto& entry_a = m_entries[a];
498        const auto& entry_b = m_entries[b];
499        // Compare chunk feerates, and return result if it differs.
500        auto feerate_cmp = ByRatio{entry_b.m_main_chunk_feerate} <=> ByRatio{entry_a.m_main_chunk_feerate};