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 <cstdint>
7 #include <functional>
8 #include <memory>
9 #include <optional>
10 #include <utility>
11 #include <vector>
12 13 #include <util/feefrac.h>
14 15 #ifndef BITCOIN_TXGRAPH_H
16 #define BITCOIN_TXGRAPH_H
17 18 static constexpr unsigned MAX_CLUSTER_COUNT_LIMIT{64};
19 20 /** Data structure to encapsulate fees, sizes, and dependencies for a set of transactions.
21 *
22 * Each TxGraph represents one or two such graphs ("main", and optionally "staging"), to allow for
23 * working with batches of changes that may still be discarded.
24 *
25 * The connected components within each transaction graph are called clusters: whenever one
26 * transaction is reachable from another, through any sequence of is-parent-of or is-child-of
27 * relations, they belong to the same cluster (so clusters include parents, children, but also
28 * grandparents, siblings, cousins twice removed, ...).
29 *
30 * For each graph, TxGraph implicitly defines an associated total ordering on its transactions
31 * (its linearization) that respects topology (parents go before their children), aiming for it to
32 * be close to the optimal order those transactions should be mined in if the goal is fee
33 * maximization, though this is a best effort only, not a strong guarantee.
34 *
35 * For more explanation, see https://delvingbitcoin.org/t/introduction-to-cluster-linearization/1032
36 *
37 * This linearization is partitioned into chunks: groups of transactions that according to this
38 * order would be mined together. Each chunk consists of the highest-feerate prefix of what remains
39 * of the linearization after removing previous chunks. TxGraph guarantees that the maintained
40 * linearization always results in chunks consisting of transactions that are connected. A chunk's
41 * transactions always belong to the same cluster.
42 *
43 * The interface is designed to accommodate an implementation that only stores the transitive
44 * closure of dependencies, so if B spends C, it does not distinguish between "A spending B" and
45 * "A spending both B and C".
46 */
47 class TxGraph
48 {
49 public:
50 /** Internal identifier for a transaction within a TxGraph. */
51 using GraphIndex = uint32_t;
52 53 /** Data type used to reference transactions within a TxGraph.
54 *
55 * Every transaction within a TxGraph has exactly one corresponding TxGraph::Ref, held by users
56 * of the class. Destroying the TxGraph::Ref removes the corresponding transaction (in both the
57 * main and staging graphs).
58 *
59 * Users of the class can inherit from TxGraph::Ref. If all Refs are inherited this way, the
60 * Ref* pointers returned by TxGraph functions can be cast to, and used as, this inherited type.
61 */
62 class Ref;
63 64 enum class Level {
65 TOP, //!< Refers to staging if it exists, main otherwise.
66 MAIN //!< Always refers to the main graph, whether staging is present or not.
67 };
68 69 /** Virtual destructor, so inheriting is safe. */
70 virtual ~TxGraph() = default;
71 /** Initialize arg (which must be an empty Ref) to refer to a new transaction in this graph
72 * with the specified feerate.
73 *
74 * If a staging graph exists, the new transaction is only created there. feerate.size must be
75 * strictly positive. In all further calls, only Refs passed to AddTransaction() are allowed
76 * to be passed to this TxGraph object (or empty Ref objects). Ref objects may outlive the
77 * TxGraph they were added to. */
78 virtual void AddTransaction(Ref& arg, const FeePerWeight& feerate) noexcept = 0;
79 /** Remove the specified transaction. If a staging graph exists, the removal only happens
80 * there. This is a no-op if the transaction was already removed.
81 *
82 * TxGraph may internally reorder transaction removals with dependency additions for
83 * performance reasons. If together with any transaction removal all its descendants, or all
84 * its ancestors, are removed as well (which is what always happens in realistic scenarios),
85 * this reordering will not affect the behavior of TxGraph.
86 *
87 * As an example, imagine 3 transactions A,B,C where B depends on A. If a dependency of C on B
88 * is added, and then B is deleted, C will still depend on A. If the deletion of B is reordered
89 * before the C->B dependency is added, the dependency adding has no effect. If, together with
90 * the deletion of B also either A or C is deleted, there is no distinction between the
91 * original order case and the reordered case.
92 */
93 virtual void RemoveTransaction(const Ref& arg) noexcept = 0;
94 /** Add a dependency between two specified transactions. If a staging graph exists, the
95 * dependency is only added there. Parent may not be a descendant of child already (but may
96 * be an ancestor of it already, in which case this is a no-op). If either transaction is
97 * already removed, this is a no-op. */
98 virtual void AddDependency(const Ref& parent, const Ref& child) noexcept = 0;
99 /** Modify the fee of the specified transaction, in both the main graph and the staging
100 * graph if it exists. Wherever the transaction does not exist (or was removed), this has no
101 * effect. */
102 virtual void SetTransactionFee(const Ref& arg, int64_t fee) noexcept = 0;
103 104 /** TxGraph is internally lazy, and will not compute many things until they are needed.
105 * Calling DoWork will perform some work now (controlled by max_cost) so that future operations
106 * are fast, if there is any. Returns whether all currently-available work is done. This can
107 * be invoked while oversized, but oversized graphs will be skipped by this call. */
108 virtual bool DoWork(uint64_t max_cost) noexcept = 0;
109 110 /** Create a staging graph (which cannot exist already). This acts as if a full copy of
111 * the transaction graph is made, upon which further modifications are made. This copy can
112 * be inspected, and then either discarded, or the main graph can be replaced by it by
113 * committing it. */
114 virtual void StartStaging() noexcept = 0;
115 /** Discard the existing active staging graph (which must exist). */
116 virtual void AbortStaging() noexcept = 0;
117 /** Replace the main graph with the staging graph (which must exist). */
118 virtual void CommitStaging() noexcept = 0;
119 /** Check whether a staging graph exists. */
120 virtual bool HaveStaging() const noexcept = 0;
121 122 /** Determine whether the graph is oversized (contains a connected component of more than the
123 * configured maximum cluster count). Some of the functions below are not available
124 * for oversized graphs. The mutators above are always available. Removing a transaction by
125 * destroying its Ref while staging exists will not clear main's oversizedness until staging
126 * is aborted or committed. */
127 virtual bool IsOversized(Level level) noexcept = 0;
128 /** Determine whether arg exists in the graph (i.e., was not removed). This is
129 * available even for oversized graphs. */
130 virtual bool Exists(const Ref& arg, Level level) noexcept = 0;
131 /** Get the individual transaction feerate of transaction arg. Returns the empty FeePerWeight
132 * if arg does not exist in either main or staging. This is available even for oversized
133 * graphs. */
134 virtual FeePerWeight GetIndividualFeerate(const Ref& arg) noexcept = 0;
135 /** Get the feerate of the chunk which transaction arg is in, in the main graph. Returns the
136 * empty FeePerWeight if arg does not exist in the main graph. The main graph must not be
137 * oversized. */
138 virtual FeePerWeight GetMainChunkFeerate(const Ref& arg) noexcept = 0;
139 /** Get pointers to all transactions in the cluster which arg is in. The transactions are
140 * returned in graph order. The queried graph must not be oversized. Returns {} if
141 * arg does not exist in the queried graph. */
142 virtual std::vector<Ref*> GetCluster(const Ref& arg, Level level) noexcept = 0;
143 /** Get pointers to all ancestors of the specified transaction (including the transaction
144 * itself), in unspecified order. The queried graph must not be oversized.
145 * Returns {} if arg does not exist in the graph. */
146 virtual std::vector<Ref*> GetAncestors(const Ref& arg, Level level) noexcept = 0;
147 /** Get pointers to all descendants of the specified transaction (including the transaction
148 * itself), in unspecified order. The queried graph must not be oversized.
149 * Returns {} if arg does not exist in the graph. */
150 virtual std::vector<Ref*> GetDescendants(const Ref& arg, Level level) noexcept = 0;
151 /** Like GetAncestors, but return the Refs for all transactions in the union of the provided
152 * arguments' ancestors (each transaction is only reported once). Refs that do not exist in
153 * the queried graph are ignored. Null refs are not allowed. */
154 virtual std::vector<Ref*> GetAncestorsUnion(std::span<const Ref* const> args, Level level) noexcept = 0;
155 /** Like GetDescendants, but return the Refs for all transactions in the union of the provided
156 * arguments' descendants (each transaction is only reported once). Refs that do not exist in
157 * the queried graph are ignored. Null refs are not allowed. */
158 virtual std::vector<Ref*> GetDescendantsUnion(std::span<const Ref* const> args, Level level) noexcept = 0;
159 /** Get the total number of transactions in the graph. This is available even
160 * for oversized graphs. */
161 virtual GraphIndex GetTransactionCount(Level level) noexcept = 0;
162 /** Compare two transactions according to their order in the main graph. Both transactions must
163 * be in the main graph. The main graph must not be oversized. */
164 virtual std::strong_ordering CompareMainOrder(const Ref& a, const Ref& b) noexcept = 0;
165 /** Count the number of distinct clusters that the specified transactions belong to. Refs that
166 * do not exist in the queried graph are ignored. Refs can not be null. The queried graph must
167 * not be oversized. */
168 virtual GraphIndex CountDistinctClusters(std::span<const Ref* const>, Level level) noexcept = 0;
169 /** For both main and staging (which must both exist and not be oversized), return the combined
170 * respective feerate diagrams, including chunks from all clusters, but excluding clusters
171 * that appear identically in both. Use FeeFrac rather than FeePerWeight so CompareChunks is
172 * usable without type-conversion. */
173 virtual std::pair<std::vector<FeeFrac>, std::vector<FeeFrac>> GetMainStagingDiagrams() noexcept = 0;
174 /** Remove transactions (including their own descendants) according to a fast but best-effort
175 * strategy such that the TxGraph's cluster and size limits are respected. Applies to staging
176 * if it exists, and to main otherwise. Returns the list of all removed transactions in
177 * unspecified order. This has no effect unless the relevant graph is oversized. */
178 virtual std::vector<Ref*> Trim() noexcept = 0;
179 180 /** Interface returned by GetBlockBuilder. */
181 class BlockBuilder
182 {
183 protected:
184 /** Make constructor non-public (use TxGraph::GetBlockBuilder()). */
185 BlockBuilder() noexcept = default;
186 public:
187 /** Support safe inheritance. */
188 virtual ~BlockBuilder() = default;
189 /** Get the chunk that is currently suggested to be included, plus its feerate, if any. */
190 virtual std::optional<std::pair<std::vector<Ref*>, FeePerWeight>> GetCurrentChunk() noexcept = 0;
191 /** Mark the current chunk as included, and progress to the next one. */
192 virtual void Include() noexcept = 0;
193 /** Mark the current chunk as skipped, and progress to the next one. Further chunks from
194 * the same cluster as the current one will not be reported anymore. */
195 virtual void Skip() noexcept = 0;
196 };
197 198 /** Construct a block builder, drawing chunks in order, from the main graph, which cannot be
199 * oversized. While the returned object exists, no mutators on the main graph are allowed.
200 * The BlockBuilder object must not outlive the TxGraph it was created with. */
201 virtual std::unique_ptr<BlockBuilder> GetBlockBuilder() noexcept = 0;
202 /** Get the last chunk in the main graph, i.e., the last chunk that would be returned by a
203 * BlockBuilder created now, together with its feerate. The chunk is returned in
204 * reverse-topological order, so every element is preceded by all its descendants. The main
205 * graph must not be oversized. If the graph is empty, {{}, FeePerWeight{}} is returned. */
206 virtual std::pair<std::vector<Ref*>, FeePerWeight> GetWorstMainChunk() noexcept = 0;
207 208 /** Get the approximate memory usage for this object, just counting the main graph. If a
209 * staging graph is present, return a number corresponding to memory usage after
210 * AbortStaging() would be called. BlockBuilders' memory usage, memory usage of internally
211 * queued operations, and memory due to temporary caches, is not included here. Can always be
212 * called. */
213 virtual size_t GetMainMemoryUsage() noexcept = 0;
214 215 /** Perform an internal consistency check on this object. */
216 virtual void SanityCheck() const = 0;
217 218 protected:
219 // Allow TxGraph::Ref to call UpdateRef and UnlinkRef.
220 friend class TxGraph::Ref;
221 /** Inform the TxGraph implementation that a TxGraph::Ref has moved. */
222 virtual void UpdateRef(GraphIndex index, Ref& new_location) noexcept = 0;
223 /** Inform the TxGraph implementation that a TxGraph::Ref was destroyed. */
224 virtual void UnlinkRef(GraphIndex index) noexcept = 0;
225 // Allow TxGraph implementations (inheriting from it) to access Ref internals.
226 static TxGraph*& GetRefGraph(Ref& arg) noexcept { return arg.m_graph; }
227 static TxGraph* GetRefGraph(const Ref& arg) noexcept { return arg.m_graph; }
228 static GraphIndex& GetRefIndex(Ref& arg) noexcept { return arg.m_index; }
229 static GraphIndex GetRefIndex(const Ref& arg) noexcept { return arg.m_index; }
230 231 public:
232 class Ref
233 {
234 // Allow TxGraph's GetRefGraph and GetRefIndex to access internals.
235 friend class TxGraph;
236 /** Which Graph the Entry lives in. nullptr if this Ref is empty. */
237 TxGraph* m_graph = nullptr;
238 /** Index into the Graph's m_entries. Only used if m_graph != nullptr. */
239 GraphIndex m_index = GraphIndex(-1);
240 public:
241 /** Construct an empty Ref. It can be initialized through TxGraph::AddTransaction. */
242 Ref() noexcept = default;
243 /** Destroy this Ref. If it is not empty, the corresponding transaction is removed (in both
244 * main and staging, if it exists). */
245 virtual ~Ref();
246 // Support move-constructing a Ref.
247 Ref& operator=(Ref&& other) noexcept = delete;
248 Ref(Ref&& other) noexcept;
249 // Do not permit copy constructing or copy assignment. A TxGraph entry can have at most one
250 // Ref pointing to it.
251 Ref& operator=(const Ref&) = delete;
252 Ref(const Ref&) = delete;
253 };
254 };
255 256 /** Construct a new TxGraph with the specified limit on the number of transactions within a cluster,
257 * and on the sum of transaction sizes within a cluster.
258 *
259 * - max_cluster_count cannot exceed MAX_CLUSTER_COUNT_LIMIT.
260 * - acceptable_cost controls how much linearization optimization work will be performed per
261 * cluster before they are considered to be of acceptable quality.
262 * - fallback_order determines how to break tie-breaks between transactions:
263 * fallback_order(a, b) < 0 means a is "better" than b, and will (in case of ties) be placed
264 * first. This ordering must be stable over the transactions' lifetimes.
265 */
266 std::unique_ptr<TxGraph> MakeTxGraph(
267 unsigned max_cluster_count,
268 uint64_t max_cluster_size,
269 uint64_t acceptable_cost,
270 const std::function<std::strong_ordering(const TxGraph::Ref&, const TxGraph::Ref&)>& fallback_order
271 ) noexcept;
272 273 #endif // BITCOIN_TXGRAPH_H
274