Inside Bitcoin

501        if (feerate_cmp != 0) return feerate_cmp;
502        // Compare equal-feerate chunk prefix size for comparing equal chunk feerates. This does two
503        // things: it distinguishes equal-feerate chunks within the same cluster (because later
504        // ones will always have a higher prefix size), and it may distinguish equal-feerate chunks
505        // from distinct clusters.
506        if (entry_a.m_main_equal_feerate_chunk_prefix_size != entry_b.m_main_equal_feerate_chunk_prefix_size) {
507            return entry_a.m_main_equal_feerate_chunk_prefix_size <=> entry_b.m_main_equal_feerate_chunk_prefix_size;
508        }
509        // Compare by maximum m_fallback_order element to order equal-feerate chunks in distinct
510        // clusters, when the equal-feerate-prefix size is also the same.
511        const auto& locator_a = entry_a.m_locator[0];
512        const auto& locator_b = entry_b.m_locator[0];
513        Assume(locator_a.IsPresent() && locator_b.IsPresent());
514        if (locator_a.cluster != locator_b.cluster) {
515            auto fallback_cmp = m_fallback_order(*m_entries[entry_a.m_main_max_chunk_fallback].m_ref,
516                                                 *m_entries[entry_b.m_main_max_chunk_fallback].m_ref);
517            if (fallback_cmp != 0) return fallback_cmp;
518            // This shouldn't be reachable as m_fallback_order defines a strong ordering.
519            Assume(false);
520            return CompareClusters(locator_a.cluster, locator_b.cluster);
521        }
522        // Within a single chunk, sort by position within cluster linearization.
523        return entry_a.m_main_lin_index <=> entry_b.m_main_lin_index;
524    }
525
526    /** Comparator for ChunkData objects in mining order. */
527    class ChunkOrder
528    {
529        const TxGraphImpl* const m_graph;
530    public:
531        explicit ChunkOrder(const TxGraphImpl* graph) : m_graph(graph) {}
532
533        bool operator()(const ChunkData& a, const ChunkData& b) const noexcept
534        {
535            return m_graph->CompareMainTransactions(a.m_graph_index, b.m_graph_index) < 0;
536        }
537    };
538
539    /** Definition for the mining index type. */
540    using ChunkIndex = std::set<ChunkData, ChunkOrder>;
541
542    /** Index of ChunkData objects, indexing the last transaction in each chunk in the main
543     *  graph. */
544    ChunkIndex m_main_chunkindex;
545    /** Number of index-observing objects in existence (BlockBuilderImpls). */
546    size_t m_main_chunkindex_observers{0};
547    /** Cache of discarded ChunkIndex node handles to reuse, avoiding additional allocation. */
548    std::vector<ChunkIndex::node_type> m_main_chunkindex_discarded;
549
550    /** A Locator that describes whether, where, and in which Cluster an Entry appears.
551     *  Every Entry has MAX_LEVELS locators, as it may appear in one Cluster per level.
552     *
553     *  Each level of a Locator is in one of three states:
554     *
555     *  - (P)resent: actually occurs in a Cluster at that level.
556     *
557     *  - (M)issing:
558     *    - In the main graph:    the transaction does not exist in main.
559     *    - In the staging graph: the transaction's existence is the same as in main. If it doesn't
560     *                            exist in main, (M) in staging means it does not exist there
561     *                            either. If it does exist in main, (M) in staging means the
562     *                            cluster it is in has not been modified in staging, and thus the
563     *                            transaction implicitly exists in staging too (without explicit
564     *                            Cluster object; see PullIn() to create it in staging too).
565     *
566     *  - (R)emoved: only possible in staging; it means the transaction exists in main, but is
567     *               removed in staging.
568     *
569     * The following combinations are possible:
570     * - (M,M): the transaction doesn't exist in either graph.
571     * - (P,M): the transaction exists in both, but only exists explicitly in a Cluster object in
572     *          main. Its existence in staging is inherited from main.
573     * - (P,P): the transaction exists in both, and is materialized in both. Thus, the clusters
574     *          and/or their linearizations may be different in main and staging.
575     * - (M,P): the transaction is added in staging, and does not exist in main.
576     * - (P,R): the transaction exists in main, but is removed in staging.
577     *
578     * When staging does not exist, only (M,M) and (P,M) are possible.
579     */
580    struct Locator
581    {
582        /** Which Cluster the Entry appears in (nullptr = missing). */
583        Cluster* cluster{nullptr};
584        /** Where in the Cluster it appears (if cluster == nullptr: 0 = missing, -1 = removed). */
585        DepGraphIndex index{0};
586
587        /** Mark this Locator as missing (= same as lower level, or non-existing if level 0). */
588        void SetMissing() noexcept { cluster = nullptr; index = 0; }
589        /** Mark this Locator as removed (not allowed in level 0). */
590        void SetRemoved() noexcept { cluster = nullptr; index = DepGraphIndex(-1); }
591        /** Mark this Locator as present, in the specified Cluster. */
592        void SetPresent(Cluster* c, DepGraphIndex i) noexcept { cluster = c; index = i; }
593        /** Check if this Locator is missing. */
594        bool IsMissing() const noexcept { return cluster == nullptr && index == 0; }
595        /** Check if this Locator is removed. */
596        bool IsRemoved() const noexcept { return cluster == nullptr && index == DepGraphIndex(-1); }
597        /** Check if this Locator is present (in some Cluster). */
598        bool IsPresent() const noexcept { return cluster != nullptr; }
599    };
600
601    /** Internal information about each transaction in a TxGraphImpl. */
602    struct Entry
603    {
604        /** Pointer to the corresponding Ref object if any, or nullptr if unlinked. */
605        Ref* m_ref{nullptr};
606        /** Iterator to the corresponding ChunkData, if any, and m_main_chunkindex.end() otherwise.
607         *  This is initialized on construction of the Entry, in AddTransaction. */
608        ChunkIndex::iterator m_main_chunkindex_iterator;
609        /** Which Cluster and position therein this Entry appears in. ([0] = main, [1] = staged). */
610        Locator m_locator[MAX_LEVELS];
611        /** The chunk feerate of this transaction in main (if present in m_locator[0]). */
612        FeePerWeight m_main_chunk_feerate;
613        /** The equal-feerate chunk prefix size of this transaction in main. If the transaction is
614         *  part of chunk C in main, then this gives the sum of the sizes of all chunks in C's
615         *  cluster, whose feerate is equal to that of C, which do not appear after C itself in
616         *  the cluster's linearization.
617         *  This provides a way to sort equal-feerate chunks across clusters, in a way that agrees
618         *  with the within-cluster chunk ordering. */
619        int32_t m_main_equal_feerate_chunk_prefix_size;
620        /** The position this transaction has in the main linearization (if present). */
621        LinearizationIndex m_main_lin_index;
622        /** Of all transactions within this transaction's chunk in main (if present there), the
623         *  maximal one according to m_fallback_order. */
624        GraphIndex m_main_max_chunk_fallback = GraphIndex(-1);
625    };
626
627    /** The set of all transactions (in all levels combined). GraphIndex values index into this. */
628    std::vector<Entry> m_entries;
629
630    /** Set of Entries which have no linked Ref anymore. */
631    std::vector<GraphIndex> m_unlinked;
632
633public:
634    /** Construct a new TxGraphImpl with the specified limits and fallback order. */
635    explicit TxGraphImpl(
636        DepGraphIndex max_cluster_count,
637        uint64_t max_cluster_size,
638        uint64_t acceptable_cost,
639        const std::function<std::strong_ordering(const TxGraph::Ref&, const TxGraph::Ref&)>& fallback_order
640    ) noexcept :
641        m_max_cluster_count(max_cluster_count),
642        m_max_cluster_size(max_cluster_size),
643        m_acceptable_cost(acceptable_cost),
644        m_fallback_order(fallback_order),
645        m_main_chunkindex(ChunkOrder(this))
646    {
647        Assume(max_cluster_count >= 1);
648        Assume(max_cluster_count <= MAX_CLUSTER_COUNT_LIMIT);
649    }
650
651    /** Destructor. */
652    ~TxGraphImpl() noexcept;
653
654    // Cannot move or copy (would invalidate TxGraphImpl* in Ref, MiningOrder, EvictionOrder).
655    TxGraphImpl(const TxGraphImpl&) = delete;
656    TxGraphImpl& operator=(const TxGraphImpl&) = delete;
657    TxGraphImpl(TxGraphImpl&&) = delete;
658    TxGraphImpl& operator=(TxGraphImpl&&) = delete;
659
660    // Simple helper functions.
661
662    /** Swap the Entry referred to by a and the one referred to by b. Gather main clusters to
663     *  update afterwards. */
664    void SwapIndexes(GraphIndex a, GraphIndex b, std::vector<Cluster*>& affected_main) noexcept;
665    /** If idx exists in the specified level ClusterSet (explicitly, or in the level below and not
666    *   removed), return the Cluster it is in. Otherwise, return nullptr. */
667    Cluster* FindCluster(GraphIndex idx, int level) const noexcept { return FindClusterAndLevel(idx, level).first; }
668    /** Like FindCluster, but also return what level the match was found in (-1 if not found). */
669    std::pair<Cluster*, int> FindClusterAndLevel(GraphIndex idx, int level) const noexcept;
670    /** Extract a Cluster from its ClusterSet, and set its quality to QualityLevel::NONE. */
671    std::unique_ptr<Cluster> ExtractCluster(int level, QualityLevel quality, ClusterSetIndex setindex) noexcept;
672    /** Delete a Cluster. */
673    void DeleteCluster(Cluster& cluster, int level) noexcept;
674    /** Insert a Cluster into its ClusterSet. */
675    ClusterSetIndex InsertCluster(int level, std::unique_ptr<Cluster>&& cluster, QualityLevel quality) noexcept;
676    /** Change the QualityLevel of a Cluster (identified by old_quality and old_index). */
677    void SetClusterQuality(int level, QualityLevel old_quality, ClusterSetIndex old_index, QualityLevel new_quality) noexcept;
678    /** Get the index of the top level ClusterSet (staging if it exists, main otherwise). */
679    int GetTopLevel() const noexcept { return m_staging_clusterset.has_value(); }
680    /** Get the specified level (staging if it exists and level is TOP, main otherwise). */
681    int GetSpecifiedLevel(Level level) const noexcept { return level == Level::TOP && m_staging_clusterset.has_value(); }
682    /** Get a reference to the ClusterSet at the specified level (which must exist). */
683    ClusterSet& GetClusterSet(int level) noexcept;
684    const ClusterSet& GetClusterSet(int level) const noexcept;
685    /** Make a transaction not exist at a specified level. It must currently exist there.
686     *  oversized_tx indicates whether the transaction is an individually-oversized one
687     *  (OVERSIZED_SINGLETON). */
688    void ClearLocator(int level, GraphIndex index, bool oversized_tx) noexcept;
689    /** Find which Clusters in main conflict with ones in staging. */
690    std::vector<Cluster*> GetConflicts() const noexcept;
691    /** Clear an Entry's ChunkData. */
692    void ClearChunkData(Entry& entry) noexcept;
693    /** Give an Entry a ChunkData object. */
694    void CreateChunkData(GraphIndex idx, LinearizationIndex chunk_count) noexcept;
695    /** Create an empty GenericClusterImpl object. */
696    std::unique_ptr<GenericClusterImpl> CreateEmptyGenericCluster() noexcept
697    {
698        return std::make_unique<GenericClusterImpl>(m_next_sequence_counter++);
699    }
700    /** Create an empty SingletonClusterImpl object. */
701    std::unique_ptr<SingletonClusterImpl> CreateEmptySingletonCluster() noexcept
702    {
703        return std::make_unique<SingletonClusterImpl>(m_next_sequence_counter++);
704    }
705    /** Create an empty Cluster of the appropriate implementation for the specified (maximum) tx
706     *  count. */
707    std::unique_ptr<Cluster> CreateEmptyCluster(DepGraphIndex tx_count) noexcept
708    {
709        if (tx_count >= SingletonClusterImpl::MIN_INTENDED_TX_COUNT && tx_count <= SingletonClusterImpl::MAX_TX_COUNT) {
710            return CreateEmptySingletonCluster();
711        }
712        if (tx_count >= GenericClusterImpl::MIN_INTENDED_TX_COUNT && tx_count <= GenericClusterImpl::MAX_TX_COUNT) {
713            return CreateEmptyGenericCluster();
714        }
715        assert(false);
716        return {};
717    }
718
719    // Functions for handling Refs.
720
721    /** Only called by Ref's move constructor/assignment to update Ref locations. */
722    void UpdateRef(GraphIndex idx, Ref& new_location) noexcept final
723    {
724        auto& entry = m_entries[idx];
725        Assume(entry.m_ref != nullptr);
726        entry.m_ref = &new_location;
727    }
728
729    /** Only called by Ref::~Ref to unlink Refs, and Ref's move assignment. */
730    void UnlinkRef(GraphIndex idx) noexcept final
731    {
732        auto& entry = m_entries[idx];
733        Assume(entry.m_ref != nullptr);
734        Assume(m_main_chunkindex_observers == 0 || !entry.m_locator[0].IsPresent());
735        // Remove all chunk index entries for the affected cluster, to avoid any chunk indexes
736        // referencing unlinked/destroyed Refs.
737        if (entry.m_locator[0].IsPresent()) {
738            entry.m_locator[0].cluster->RemoveChunkData(*this);
739        }
740        entry.m_ref = nullptr;
741        // Mark the transaction as to be removed in all levels where it explicitly or implicitly
742        // exists.
743        bool exists_anywhere{false};
744        bool exists{false};
745        for (int level = 0; level <= GetTopLevel(); ++level) {
746            if (entry.m_locator[level].IsPresent()) {
747                exists_anywhere = true;
748                exists = true;
749            } else if (entry.m_locator[level].IsRemoved()) {
750                exists = false;