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