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      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      static TxGraph*& GetRefGraph(Ref& arg) noexcept { return arg.m_graph; }
178      static TxGraph* GetRefGraph(const Ref& arg) noexcept { return arg.m_graph; }
179      static GraphIndex& GetRefIndex(Ref& arg) noexcept { return arg.m_index; }
180      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          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