/root/bitcoin/src/txgraph.h

Source
// Copyright (c) The Bitcoin Core developers
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.

#include <compare>
#include <stdint.h>
#include <memory>
#include <vector>

#include <util/feefrac.h>

#ifndef BITCOIN_TXGRAPH_H
#define BITCOIN_TXGRAPH_H

static constexpr unsigned MAX_CLUSTER_COUNT_LIMIT{64};

/** Data structure to encapsulate fees, sizes, and dependencies for a set of transactions.
 *
 * Each TxGraph represents one or two such graphs ("main", and optionally "staging"), to allow for
 * working with batches of changes that may still be discarded.
 *
 * The connected components within each transaction graph are called clusters: whenever one
 * transaction is reachable from another, through any sequence of is-parent-of or is-child-of
 * relations, they belong to the same cluster (so clusters include parents, children, but also
 * grandparents, siblings, cousins twice removed, ...).
 *
 * For each graph, TxGraph implicitly defines an associated total ordering on its transactions
 * (its linearization) that respects topology (parents go before their children), aiming for it to
 * be close to the optimal order those transactions should be mined in if the goal is fee
 * maximization, though this is a best effort only, not a strong guarantee.
 *
 * For more explanation, see https://delvingbitcoin.org/t/introduction-to-cluster-linearization/1032
 *
 * This linearization is partitioned into chunks: groups of transactions that according to this
 * order would be mined together. Each chunk consists of the highest-feerate prefix of what remains
 * of the linearization after removing previous chunks. TxGraph guarantees that the maintained
 * linearization always results in chunks consisting of transactions that are connected. A chunk's
 * transactions always belong to the same cluster.
 *
 * The interface is designed to accommodate an implementation that only stores the transitive
 * closure of dependencies, so if B spends C, it does not distinguish between "A spending B" and
 * "A spending both B and C".
 */
class TxGraph
{
public:
    /** Internal identifier for a transaction within a TxGraph. */
    using GraphIndex = uint32_t;

    /** Data type used to reference transactions within a TxGraph.
     *
     * Every transaction within a TxGraph has exactly one corresponding TxGraph::Ref, held by users
     * of the class. Destroying the TxGraph::Ref removes the corresponding transaction (in both the
     * main and staging graphs).
     *
     * Users of the class can inherit from TxGraph::Ref. If all Refs are inherited this way, the
     * Ref* pointers returned by TxGraph functions can be cast to, and used as, this inherited type.
     */
    class Ref;

    /** Virtual destructor, so inheriting is safe. */
    virtual ~TxGraph() = default;
    /** Construct a new transaction with the specified feerate, and return a Ref to it.
     *  If a staging graph exists, the new transaction is only created there. In all
     *  further calls, only Refs created by AddTransaction() are allowed to be passed to this
     *  TxGraph object (or empty Ref objects). Ref objects may outlive the TxGraph they were
     *  created for. */
    [[nodiscard]] virtual Ref AddTransaction(const FeePerWeight& feerate) noexcept = 0;
    /** Remove the specified transaction. If a staging graph exists, the removal only happens
     *  there. This is a no-op if the transaction was already removed.
     *
     * TxGraph may internally reorder transaction removals with dependency additions for
     * performance reasons. If together with any transaction removal all its descendants, or all
     * its ancestors, are removed as well (which is what always happens in realistic scenarios),
     * this reordering will not affect the behavior of TxGraph.
     *
     * As an example, imagine 3 transactions A,B,C where B depends on A. If a dependency of C on B
     * is added, and then B is deleted, C will still depend on A. If the deletion of B is reordered
     * before the C->B dependency is added, the dependency adding has no effect. If, together with
     * the deletion of B also either A or C is deleted, there is no distinction between the
     * original order case and the reordered case.
     */
    virtual void RemoveTransaction(const Ref& arg) noexcept = 0;
    /** Add a dependency between two specified transactions. If a staging graph exists, the
     *  dependency is only added there. Parent may not be a descendant of child already (but may
     *  be an ancestor of it already, in which case this is a no-op). If either transaction is
     *  already removed, this is a no-op. */
    virtual void AddDependency(const Ref& parent, const Ref& child) noexcept = 0;
    /** Modify the fee of the specified transaction, in both the main graph and the staging
     *  graph if it exists. Wherever the transaction does not exist (or was removed), this has no
     *  effect. */
    virtual void SetTransactionFee(const Ref& arg, int64_t fee) noexcept = 0;

    /** TxGraph is internally lazy, and will not compute many things until they are needed.
     *  Calling DoWork will compute everything now, so that future operations are fast. This can be
     *  invoked while oversized. */
    virtual void DoWork() noexcept = 0;

    /** Create a staging graph (which cannot exist already). This acts as if a full copy of
     *  the transaction graph is made, upon which further modifications are made. This copy can
     *  be inspected, and then either discarded, or the main graph can be replaced by it by
     *  committing it. */
    virtual void StartStaging() noexcept = 0;
    /** Discard the existing active staging graph (which must exist). */
    virtual void AbortStaging() noexcept = 0;
    /** Replace the main graph with the staging graph (which must exist). */
    virtual void CommitStaging() noexcept = 0;
    /** Check whether a staging graph exists. */
    virtual bool HaveStaging() const noexcept = 0;

    /** Determine whether the graph is oversized (contains a connected component of more than the
     *  configured maximum cluster count). If main_only is false and a staging graph exists, it is
     *  queried; otherwise the main graph is queried. Some of the functions below are not available
     *  for oversized graphs. The mutators above are always available. Removing a transaction by
     *  destroying its Ref while staging exists will not clear main's oversizedness until staging
     *  is aborted or committed. */
    virtual bool IsOversized(bool main_only = false) noexcept = 0;
    /** Determine whether arg exists in the graph (i.e., was not removed). If main_only is false
     *  and a staging graph exists, it is queried; otherwise the main graph is queried. This is
     *  available even for oversized graphs. */
    virtual bool Exists(const Ref& arg, bool main_only = false) noexcept = 0;
    /** Get the individual transaction feerate of transaction arg. Returns the empty FeePerWeight
     *  if arg does not exist in either main or staging. This is available even for oversized
     *  graphs. */
    virtual FeePerWeight GetIndividualFeerate(const Ref& arg) noexcept = 0;
    /** Get the feerate of the chunk which transaction arg is in, in the main graph. Returns the
     *  empty FeePerWeight if arg does not exist in the main graph. The main graph must not be
     *  oversized. */
    virtual FeePerWeight GetMainChunkFeerate(const Ref& arg) noexcept = 0;
    /** Get pointers to all transactions in the cluster which arg is in. The transactions are
     *  returned in graph order. If main_only is false and a staging graph exists, it is queried;
     *  otherwise the main graph is queried. The queried graph must not be oversized. Returns {} if
     *  arg does not exist in the queried graph. */
    virtual std::vector<Ref*> GetCluster(const Ref& arg, bool main_only = false) noexcept = 0;
    /** Get pointers to all ancestors of the specified transaction (including the transaction
     *  itself), in unspecified order. If main_only is false and a staging graph exists, it is
     *  queried; otherwise the main graph is queried. The queried graph must not be oversized.
     *  Returns {} if arg does not exist in the graph. */
    virtual std::vector<Ref*> GetAncestors(const Ref& arg, bool main_only = false) noexcept = 0;
    /** Get pointers to all descendants of the specified transaction (including the transaction
     *  itself), in unspecified order. If main_only is false and a staging graph exists, it is
     *  queried; otherwise the main graph is queried. The queried graph must not be oversized.
     *  Returns {} if arg does not exist in the graph. */
    virtual std::vector<Ref*> GetDescendants(const Ref& arg, bool main_only = false) noexcept = 0;
    /** Like GetAncestors, but return the Refs for all transactions in the union of the provided
     *  arguments' ancestors (each transaction is only reported once). Refs that do not exist in
     *  the queried graph are ignored. Null refs are not allowed. */
    virtual std::vector<Ref*> GetAncestorsUnion(std::span<const Ref* const> args, bool main_only = false) noexcept = 0;
    /** Like GetDescendants, but return the Refs for all transactions in the union of the provided
     *  arguments' descendants (each transaction is only reported once). Refs that do not exist in
     *  the queried graph are ignored. Null refs are not allowed. */
    virtual std::vector<Ref*> GetDescendantsUnion(std::span<const Ref* const> args, bool main_only = false) noexcept = 0;
    /** Get the total number of transactions in the graph. If main_only is false and a staging
     *  graph exists, it is queried; otherwise the main graph is queried. This is available even
     *  for oversized graphs. */
    virtual GraphIndex GetTransactionCount(bool main_only = false) noexcept = 0;
    /** Compare two transactions according to their order in the main graph. Both transactions must
     *  be in the main graph. The main graph must not be oversized. */
    virtual std::strong_ordering CompareMainOrder(const Ref& a, const Ref& b) noexcept = 0;
    /** Count the number of distinct clusters that the specified transactions belong to. If
     *  main_only is false and a staging graph exists, staging clusters are counted. Otherwise,
     *  main clusters are counted. Refs that do not exist in the queried graph are ignored. Refs
     *  can not be null. The queried graph must not be oversized. */
    virtual GraphIndex CountDistinctClusters(std::span<const Ref* const>, bool main_only = false) noexcept = 0;

    /** Perform an internal consistency check on this object. */
    virtual void SanityCheck() const = 0;

protected:
    // Allow TxGraph::Ref to call UpdateRef and UnlinkRef.
    friend class TxGraph::Ref;
    /** Inform the TxGraph implementation that a TxGraph::Ref has moved. */
    virtual void UpdateRef(GraphIndex index, Ref& new_location) noexcept = 0;
    /** Inform the TxGraph implementation that a TxGraph::Ref was destroyed. */
    virtual void UnlinkRef(GraphIndex index) noexcept = 0;
    // Allow TxGraph implementations (inheriting from it) to access Ref internals.
    static TxGraph*& GetRefGraph(Ref& arg) noexcept { return arg.m_graph; }
    static TxGraph* GetRefGraph(const Ref& arg) noexcept { return arg.m_graph; }
    static GraphIndex& GetRefIndex(Ref& arg) noexcept { return arg.m_index; }
    static GraphIndex GetRefIndex(const Ref& arg) noexcept { return arg.m_index; }

public:
    class Ref
    {
        // Allow TxGraph's GetRefGraph and GetRefIndex to access internals.
        friend class TxGraph;
        /** Which Graph the Entry lives in. nullptr if this Ref is empty. */
        TxGraph* m_graph = nullptr;
        /** Index into the Graph's m_entries. Only used if m_graph != nullptr. */
        GraphIndex m_index = GraphIndex(-1);
    public:
        /** Construct an empty Ref. Non-empty Refs can only be created using
         *  TxGraph::AddTransaction. */
        Ref() noexcept = default;
        /** Destroy this Ref. If it is not empty, the corresponding transaction is removed (in both
         *  main and staging, if it exists). */
        virtual ~Ref();
        // Support moving a Ref.
        Ref& operator=(Ref&& other) noexcept;
        Ref(Ref&& other) noexcept;
        // Do not permit copy constructing or copy assignment. A TxGraph entry can have at most one
        // Ref pointing to it.
        Ref& operator=(const Ref&) = delete;
        Ref(const Ref&) = delete;
    };
};

/** Construct a new TxGraph with the specified limit on transactions within a cluster. That
 *  number cannot exceed MAX_CLUSTER_COUNT_LIMIT. */
std::unique_ptr<TxGraph> MakeTxGraph(unsigned max_cluster_count) noexcept;

#endif // BITCOIN_TXGRAPH_H

Coverage Report

Created: 2025-05-14 12:32

Line	Count	Source
1		// Copyright (c) The Bitcoin Core developers
2		// Distributed under the MIT software license, see the accompanying
3		// file COPYING or http://www.opensource.org/licenses/mit-license.php.
4
5		#include <compare>
6		#include <stdint.h>
7		#include <memory>
8		#include <vector>
9
10		#include <util/feefrac.h>
11
12		#ifndef BITCOIN_TXGRAPH_H
13		#define BITCOIN_TXGRAPH_H
14
15		static constexpr unsigned MAX_CLUSTER_COUNT_LIMIT{64};
16
17		/** Data structure to encapsulate fees, sizes, and dependencies for a set of transactions.
18		*
19		* Each TxGraph represents one or two such graphs ("main", and optionally "staging"), to allow for
20		* working with batches of changes that may still be discarded.
21		*
22		* The connected components within each transaction graph are called clusters: whenever one
23		* transaction is reachable from another, through any sequence of is-parent-of or is-child-of
24		* relations, they belong to the same cluster (so clusters include parents, children, but also
25		* grandparents, siblings, cousins twice removed, ...).
26		*
27		* For each graph, TxGraph implicitly defines an associated total ordering on its transactions
28		* (its linearization) that respects topology (parents go before their children), aiming for it to
29		* be close to the optimal order those transactions should be mined in if the goal is fee
30		* maximization, though this is a best effort only, not a strong guarantee.
31		*
32		* For more explanation, see https://delvingbitcoin.org/t/introduction-to-cluster-linearization/1032
33		*
34		* This linearization is partitioned into chunks: groups of transactions that according to this
35		* order would be mined together. Each chunk consists of the highest-feerate prefix of what remains
36		* of the linearization after removing previous chunks. TxGraph guarantees that the maintained
37		* linearization always results in chunks consisting of transactions that are connected. A chunk's
38		* transactions always belong to the same cluster.
39		*
40		* The interface is designed to accommodate an implementation that only stores the transitive
41		* closure of dependencies, so if B spends C, it does not distinguish between "A spending B" and
42		* "A spending both B and C".
43		*/
44		class TxGraph
45		{
46		public:
47		/** Internal identifier for a transaction within a TxGraph. */
48		using GraphIndex = uint32_t;
49
50		/** Data type used to reference transactions within a TxGraph.
51		*
52		* Every transaction within a TxGraph has exactly one corresponding TxGraph::Ref, held by users
53		* of the class. Destroying the TxGraph::Ref removes the corresponding transaction (in both the
54		* main and staging graphs).
55		*
56		* Users of the class can inherit from TxGraph::Ref. If all Refs are inherited this way, the
57		* Ref* pointers returned by TxGraph functions can be cast to, and used as, this inherited type.
58		*/
59		class Ref;
60
61		/** Virtual destructor, so inheriting is safe. */
62	0	virtual ~TxGraph() = default;
63		/** Construct a new transaction with the specified feerate, and return a Ref to it.
64		* If a staging graph exists, the new transaction is only created there. In all
65		* further calls, only Refs created by AddTransaction() are allowed to be passed to this
66		* TxGraph object (or empty Ref objects). Ref objects may outlive the TxGraph they were
67		* created for. */
68		[[nodiscard]] virtual Ref AddTransaction(const FeePerWeight& feerate) noexcept = 0;
69		/** Remove the specified transaction. If a staging graph exists, the removal only happens
70		* there. This is a no-op if the transaction was already removed.
71		*
72		* TxGraph may internally reorder transaction removals with dependency additions for
73		* performance reasons. If together with any transaction removal all its descendants, or all
74		* its ancestors, are removed as well (which is what always happens in realistic scenarios),
75		* this reordering will not affect the behavior of TxGraph.
76		*
77		* As an example, imagine 3 transactions A,B,C where B depends on A. If a dependency of C on B
78		* is added, and then B is deleted, C will still depend on A. If the deletion of B is reordered
79		* before the C->B dependency is added, the dependency adding has no effect. If, together with
80		* the deletion of B also either A or C is deleted, there is no distinction between the
81		* original order case and the reordered case.
82		*/
83		virtual void RemoveTransaction(const Ref& arg) noexcept = 0;
84		/** Add a dependency between two specified transactions. If a staging graph exists, the
85		* dependency is only added there. Parent may not be a descendant of child already (but may
86		* be an ancestor of it already, in which case this is a no-op). If either transaction is
87		* already removed, this is a no-op. */
88		virtual void AddDependency(const Ref& parent, const Ref& child) noexcept = 0;
89		/** Modify the fee of the specified transaction, in both the main graph and the staging
90		* graph if it exists. Wherever the transaction does not exist (or was removed), this has no
91		* effect. */
92		virtual void SetTransactionFee(const Ref& arg, int64_t fee) noexcept = 0;
93
94		/** TxGraph is internally lazy, and will not compute many things until they are needed.
95		* Calling DoWork will compute everything now, so that future operations are fast. This can be
96		* invoked while oversized. */
97		virtual void DoWork() noexcept = 0;
98
99		/** Create a staging graph (which cannot exist already). This acts as if a full copy of
100		* the transaction graph is made, upon which further modifications are made. This copy can
101		* be inspected, and then either discarded, or the main graph can be replaced by it by
102		* committing it. */
103		virtual void StartStaging() noexcept = 0;
104		/** Discard the existing active staging graph (which must exist). */
105		virtual void AbortStaging() noexcept = 0;
106		/** Replace the main graph with the staging graph (which must exist). */
107		virtual void CommitStaging() noexcept = 0;
108		/** Check whether a staging graph exists. */
109		virtual bool HaveStaging() const noexcept = 0;
110
111		/** Determine whether the graph is oversized (contains a connected component of more than the
112		* configured maximum cluster count). If main_only is false and a staging graph exists, it is
113		* queried; otherwise the main graph is queried. Some of the functions below are not available
114		* for oversized graphs. The mutators above are always available. Removing a transaction by
115		* destroying its Ref while staging exists will not clear main's oversizedness until staging
116		* is aborted or committed. */
117		virtual bool IsOversized(bool main_only = false) noexcept = 0;
118		/** Determine whether arg exists in the graph (i.e., was not removed). If main_only is false
119		* and a staging graph exists, it is queried; otherwise the main graph is queried. This is
120		* available even for oversized graphs. */
121		virtual bool Exists(const Ref& arg, bool main_only = false) noexcept = 0;
122		/** Get the individual transaction feerate of transaction arg. Returns the empty FeePerWeight
123		* if arg does not exist in either main or staging. This is available even for oversized
124		* graphs. */
125		virtual FeePerWeight GetIndividualFeerate(const Ref& arg) noexcept = 0;
126		/** Get the feerate of the chunk which transaction arg is in, in the main graph. Returns the
127		* empty FeePerWeight if arg does not exist in the main graph. The main graph must not be
128		* oversized. */
129		virtual FeePerWeight GetMainChunkFeerate(const Ref& arg) noexcept = 0;
130		/** Get pointers to all transactions in the cluster which arg is in. The transactions are
131		* returned in graph order. If main_only is false and a staging graph exists, it is queried;
132		* otherwise the main graph is queried. The queried graph must not be oversized. Returns {} if
133		* arg does not exist in the queried graph. */
134		virtual std::vector<Ref*> GetCluster(const Ref& arg, bool main_only = false) noexcept = 0;
135		/** Get pointers to all ancestors of the specified transaction (including the transaction
136		* itself), in unspecified order. If main_only is false and a staging graph exists, it is
137		* queried; otherwise the main graph is queried. The queried graph must not be oversized.
138		* Returns {} if arg does not exist in the graph. */
139		virtual std::vector<Ref*> GetAncestors(const Ref& arg, bool main_only = false) noexcept = 0;
140		/** Get pointers to all descendants of the specified transaction (including the transaction
141		* itself), in unspecified order. If main_only is false and a staging graph exists, it is
142		* queried; otherwise the main graph is queried. The queried graph must not be oversized.
143		* Returns {} if arg does not exist in the graph. */
144		virtual std::vector<Ref*> GetDescendants(const Ref& arg, bool main_only = false) noexcept = 0;
145		/** Like GetAncestors, but return the Refs for all transactions in the union of the provided
146		* arguments' ancestors (each transaction is only reported once). Refs that do not exist in
147		* the queried graph are ignored. Null refs are not allowed. */
148		virtual std::vector<Ref> GetAncestorsUnion(std::span<const Ref const> args, bool main_only = false) noexcept = 0;
149		/** Like GetDescendants, but return the Refs for all transactions in the union of the provided
150		* arguments' descendants (each transaction is only reported once). Refs that do not exist in
151		* the queried graph are ignored. Null refs are not allowed. */
152		virtual std::vector<Ref> GetDescendantsUnion(std::span<const Ref const> args, bool main_only = false) noexcept = 0;
153		/** Get the total number of transactions in the graph. If main_only is false and a staging
154		* graph exists, it is queried; otherwise the main graph is queried. This is available even
155		* for oversized graphs. */
156		virtual GraphIndex GetTransactionCount(bool main_only = false) noexcept = 0;
157		/** Compare two transactions according to their order in the main graph. Both transactions must
158		* be in the main graph. The main graph must not be oversized. */
159		virtual std::strong_ordering CompareMainOrder(const Ref& a, const Ref& b) noexcept = 0;
160		/** Count the number of distinct clusters that the specified transactions belong to. If
161		* main_only is false and a staging graph exists, staging clusters are counted. Otherwise,
162		* main clusters are counted. Refs that do not exist in the queried graph are ignored. Refs
163		* can not be null. The queried graph must not be oversized. */
164		virtual GraphIndex CountDistinctClusters(std::span<const Ref* const>, bool main_only = false) noexcept = 0;
165
166		/** Perform an internal consistency check on this object. */
167		virtual void SanityCheck() const = 0;
168
169		protected:
170		// Allow TxGraph::Ref to call UpdateRef and UnlinkRef.
171		friend class TxGraph::Ref;
172		/** Inform the TxGraph implementation that a TxGraph::Ref has moved. */
173		virtual void UpdateRef(GraphIndex index, Ref& new_location) noexcept = 0;
174		/** Inform the TxGraph implementation that a TxGraph::Ref was destroyed. */
175		virtual void UnlinkRef(GraphIndex index) noexcept = 0;
176		// Allow TxGraph implementations (inheriting from it) to access Ref internals.
177	0	static TxGraph*& GetRefGraph(Ref& arg) noexcept { return arg.m_graph; }
178	0	static TxGraph* GetRefGraph(const Ref& arg) noexcept { return arg.m_graph; }
179	0	static GraphIndex& GetRefIndex(Ref& arg) noexcept { return arg.m_index; }
180	0	static GraphIndex GetRefIndex(const Ref& arg) noexcept { return arg.m_index; }
181
182		public:
183		class Ref
184		{
185		// Allow TxGraph's GetRefGraph and GetRefIndex to access internals.
186		friend class TxGraph;
187		/** Which Graph the Entry lives in. nullptr if this Ref is empty. */
188		TxGraph* m_graph = nullptr;
189		/** Index into the Graph's m_entries. Only used if m_graph != nullptr. */
190		GraphIndex m_index = GraphIndex(-1);
191		public:
192		/** Construct an empty Ref. Non-empty Refs can only be created using
193		* TxGraph::AddTransaction. */
194	0	Ref() noexcept = default;
195		/** Destroy this Ref. If it is not empty, the corresponding transaction is removed (in both
196		* main and staging, if it exists). */
197		virtual ~Ref();
198		// Support moving a Ref.
199		Ref& operator=(Ref&& other) noexcept;
200		Ref(Ref&& other) noexcept;
201		// Do not permit copy constructing or copy assignment. A TxGraph entry can have at most one
202		// Ref pointing to it.
203		Ref& operator=(const Ref&) = delete;
204		Ref(const Ref&) = delete;
205		};
206		};
207
208		/** Construct a new TxGraph with the specified limit on transactions within a cluster. That
209		* number cannot exceed MAX_CLUSTER_COUNT_LIMIT. */
210		std::unique_ptr<TxGraph> MakeTxGraph(unsigned max_cluster_count) noexcept;
211
212		#endif // BITCOIN_TXGRAPH_H