Branch data Line data Source code
1 : : // Copyright (c) 2022 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 : : #ifndef BITCOIN_NODE_MINI_MINER_H
6 : : #define BITCOIN_NODE_MINI_MINER_H
7 : :
8 : : #include <consensus/amount.h>
9 : : #include <primitives/transaction.h>
10 : : #include <uint256.h>
11 : :
12 : : #include <map>
13 : : #include <memory>
14 : : #include <optional>
15 : : #include <set>
16 : : #include <stdint.h>
17 : : #include <vector>
18 : :
19 : : class CFeeRate;
20 : : class CTxMemPool;
21 : :
22 : : namespace node {
23 : :
24 : : // Container for tracking updates to ancestor feerate as we include ancestors in the "block"
25 [ - - + - : 271117 : class MiniMinerMempoolEntry
+ - - - ]
[ + - # #
# # # # ]
[ + - + -
+ - ]
26 : : {
27 : : const CTransactionRef tx;
28 : : const int64_t vsize_individual;
29 : : int64_t vsize_with_ancestors;
30 : : const CAmount fee_individual;
31 : : CAmount fee_with_ancestors;
32 : :
33 : : // This class must be constructed while holding mempool.cs. After construction, the object's
34 : : // methods can be called without holding that lock.
35 : :
36 : : public:
37 : 67774 : explicit MiniMinerMempoolEntry(const CTransactionRef& tx_in,
38 : : int64_t vsize_self,
39 : : int64_t vsize_ancestor,
40 : : CAmount fee_self,
41 : 67774 : CAmount fee_ancestor):
42 [ + - ][ - - : 67774 : tx{tx_in},
+ - + - -
- + - - -
+ - + - +
- + - - -
+ - + - +
- - - + -
- - - - -
- + - ]
43 : 67774 : vsize_individual{vsize_self},
44 : 67774 : vsize_with_ancestors{vsize_ancestor},
45 : 67774 : fee_individual{fee_self},
46 [ + - ]: 67774 : fee_with_ancestors{fee_ancestor}
47 : : { }
48 : :
49 [ + - ]: 67770 : CAmount GetModifiedFee() const { return fee_individual; }
50 [ + - + - : 3659265 : CAmount GetModFeesWithAncestors() const { return fee_with_ancestors; }
+ - + - +
- + - + -
+ - + + ]
51 : 67770 : int64_t GetTxSize() const { return vsize_individual; }
52 [ + - + - : 3659265 : int64_t GetSizeWithAncestors() const { return vsize_with_ancestors; }
+ - + - +
- + - + -
+ + ]
53 : 67668 : const CTransaction& GetTx() const LIFETIMEBOUND { return *tx; }
54 : 98749 : void UpdateAncestorState(int64_t vsize_change, CAmount fee_change) {
55 : 98749 : vsize_with_ancestors += vsize_change;
56 : 98749 : fee_with_ancestors += fee_change;
57 : : }
58 : : };
59 : :
60 : : // Comparator needed for std::set<MockEntryMap::iterator>
61 : : struct IteratorComparator
62 : : {
63 : : template<typename I>
64 [ + + + + : 2810 : bool operator()(const I& a, const I& b) const
+ + + + +
- ]
65 : : {
66 [ + + + + : 2810 : return a->first < b->first;
+ + + + +
- ]
67 : : }
68 : : };
69 : :
70 : : /** A minimal version of BlockAssembler, using the same ancestor set scoring algorithm. Allows us to
71 : : * run this algorithm on a limited set of transactions (e.g. subset of mempool or transactions that
72 : : * are not yet in mempool) instead of the entire mempool, ignoring consensus rules.
73 : : * Callers may use this to:
74 : : * - Calculate the "bump fee" needed to spend an unconfirmed UTXO at a given feerate
75 : : * - "Linearize" a list of transactions to see the order in which they would be selected for
76 : : * inclusion in a block
77 : : */
78 : : class MiniMiner
79 : : {
80 : : // When true, a caller may use CalculateBumpFees(). Becomes false if we failed to retrieve
81 : : // mempool entries (i.e. cluster size too large) or bump fees have already been calculated.
82 : : bool m_ready_to_calculate{true};
83 : :
84 : : // Set once per lifetime, fill in during initialization.
85 : : // txids of to-be-replaced transactions
86 : : std::set<uint256> m_to_be_replaced;
87 : :
88 : : // If multiple argument outpoints correspond to the same transaction, cache them together in
89 : : // a single entry indexed by txid. Then we can just work with txids since all outpoints from
90 : : // the same tx will have the same bumpfee. Excludes non-mempool transactions.
91 : : std::map<uint256, std::vector<COutPoint>> m_requested_outpoints_by_txid;
92 : :
93 : : // Txid to a number representing the order in which this transaction was included (smaller
94 : : // number = included earlier). Transactions included in an ancestor set together have the same
95 : : // sequence number.
96 : : std::map<Txid, uint32_t> m_inclusion_order;
97 : : // What we're trying to calculate. Outpoint to the fee needed to bring the transaction to the target feerate.
98 : : std::map<COutPoint, CAmount> m_bump_fees;
99 : :
100 : : // The constructed block template
101 : : std::set<uint256> m_in_block;
102 : :
103 : : // Information on the current status of the block
104 : : CAmount m_total_fees{0};
105 : : int32_t m_total_vsize{0};
106 : :
107 : : /** Main data structure holding the entries, can be indexed by txid */
108 : : std::map<uint256, MiniMinerMempoolEntry> m_entries_by_txid;
109 : : using MockEntryMap = decltype(m_entries_by_txid);
110 : :
111 : : /** Vector of entries, can be sorted by ancestor feerate. */
112 : : std::vector<MockEntryMap::iterator> m_entries;
113 : :
114 : : /** Map of txid to its descendants. Should be inclusive. */
115 : : std::map<uint256, std::vector<MockEntryMap::iterator>> m_descendant_set_by_txid;
116 : :
117 : : /** Consider this ancestor package "mined" so remove all these entries from our data structures. */
118 : : void DeleteAncestorPackage(const std::set<MockEntryMap::iterator, IteratorComparator>& ancestors);
119 : :
120 : : /** Perform some checks. */
121 : : void SanityCheck() const;
122 : :
123 : : public:
124 : : /** Returns true if CalculateBumpFees may be called, false if not. */
125 [ + - + - : 115 : bool IsReadyToCalculate() const { return m_ready_to_calculate; }
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - +
- ]
126 : :
127 : : /** Build a block template until the target feerate is hit. If target_feerate is not given,
128 : : * builds a block template until all transactions have been selected. */
129 : : void BuildMockTemplate(std::optional<CFeeRate> target_feerate);
130 : :
131 : : /** Returns set of txids in the block template if one has been constructed. */
132 [ + - + - : 4 : std::set<uint256> GetMockTemplateTxids() const { return m_in_block; }
+ - + - ]
133 : :
134 : : /** Constructor that takes a list of outpoints that may or may not belong to transactions in the
135 : : * mempool. Copies out information about the relevant transactions in the mempool into
136 : : * MiniMinerMempoolEntrys.
137 : : */
138 : : MiniMiner(const CTxMemPool& mempool, const std::vector<COutPoint>& outpoints);
139 : :
140 : : /** Constructor in which the MiniMinerMempoolEntry entries have been constructed manually.
141 : : * It is assumed that all entries are unique and their values are correct, otherwise results
142 : : * computed by MiniMiner may be incorrect. Callers should check IsReadyToCalculate() after
143 : : * construction.
144 : : * @param[in] descendant_caches A map from each transaction to the set of txids of this
145 : : * transaction's descendant set, including itself. Each tx in
146 : : * manual_entries must have a corresponding entry in this map, and
147 : : * all of the txids in a descendant set must correspond to a tx in
148 : : * manual_entries.
149 : : */
150 : : MiniMiner(const std::vector<MiniMinerMempoolEntry>& manual_entries,
151 : : const std::map<Txid, std::set<Txid>>& descendant_caches);
152 : :
153 : : /** Construct a new block template and, for each outpoint corresponding to a transaction that
154 : : * did not make it into the block, calculate the cost of bumping those transactions (and their
155 : : * ancestors) to the minimum feerate. Returns a map from outpoint to bump fee, or an empty map
156 : : * if they cannot be calculated. */
157 : : std::map<COutPoint, CAmount> CalculateBumpFees(const CFeeRate& target_feerate);
158 : :
159 : : /** Construct a new block template and, calculate the cost of bumping all transactions that did
160 : : * not make it into the block to the target feerate. Returns the total bump fee, or std::nullopt
161 : : * if it cannot be calculated. */
162 : : std::optional<CAmount> CalculateTotalBumpFees(const CFeeRate& target_feerate);
163 : :
164 : : /** Construct a new block template with all of the transactions and calculate the order in which
165 : : * they are selected. Returns the sequence number (lower = selected earlier) with which each
166 : : * transaction was selected, indexed by txid, or an empty map if it cannot be calculated.
167 : : */
168 : : std::map<Txid, uint32_t> Linearize();
169 : : };
170 : : } // namespace node
171 : :
172 : : #endif // BITCOIN_NODE_MINI_MINER_H
|
