Branch data Line data Source code
1 : : // Copyright (c) 2023 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 <node/mini_miner.h>
6 : :
7 : : #include <boost/multi_index/detail/hash_index_iterator.hpp>
8 : : #include <boost/operators.hpp>
9 : : #include <consensus/amount.h>
10 : : #include <policy/feerate.h>
11 : : #include <primitives/transaction.h>
12 : : #include <sync.h>
13 : : #include <txmempool.h>
14 : : #include <uint256.h>
15 : : #include <util/check.h>
16 : :
17 : : #include <algorithm>
18 : : #include <numeric>
19 : : #include <ranges>
20 : : #include <utility>
21 : :
22 : : namespace node {
23 : :
24 [ + - ]: 4540 : MiniMiner::MiniMiner(const CTxMemPool& mempool, const std::vector<COutPoint>& outpoints)
25 : : {
26 [ + - ]: 4540 : LOCK(mempool.cs);
27 : : // Find which outpoints to calculate bump fees for.
28 : : // Anything that's spent by the mempool is to-be-replaced
29 : : // Anything otherwise unavailable just has a bump fee of 0
30 [ + + ]: 381814 : for (const auto& outpoint : outpoints) {
31 [ + - + + ]: 377274 : if (!mempool.exists(outpoint.hash)) {
32 : : // This UTXO is either confirmed or not yet submitted to mempool.
33 : : // If it's confirmed, no bump fee is required.
34 : : // If it's not yet submitted, we have no information, so return 0.
35 [ + - ]: 73205 : m_bump_fees.emplace(outpoint, 0);
36 : 73205 : continue;
37 : : }
38 : :
39 : : // UXTO is created by transaction in mempool, add to map.
40 : : // Note: This will either create a missing entry or add the outpoint to an existing entry
41 [ + - + - ]: 304069 : m_requested_outpoints_by_txid[outpoint.hash].push_back(outpoint);
42 : :
43 [ + - + + ]: 304069 : if (const auto ptx{mempool.GetConflictTx(outpoint)}) {
44 : : // This outpoint is already being spent by another transaction in the mempool. We
45 : : // assume that the caller wants to replace this transaction and its descendants. It
46 : : // would be unusual for the transaction to have descendants as the wallet won’t normally
47 : : // attempt to replace transactions with descendants. If the outpoint is from a mempool
48 : : // transaction, we still need to calculate its ancestors bump fees (added to
49 : : // m_requested_outpoints_by_txid below), but after removing the to-be-replaced entries.
50 : : //
51 : : // Note that the descendants of a transaction include the transaction itself. Also note,
52 : : // that this is only calculating bump fees. RBF fee rules should be handled separately.
53 [ + - ]: 37022 : CTxMemPool::setEntries descendants;
54 [ + - + - ]: 74044 : mempool.CalculateDescendants(mempool.GetIter(ptx->GetHash()).value(), descendants);
55 [ + + ]: 4056312 : for (const auto& desc_txiter : descendants) {
56 [ + - ]: 4019290 : m_to_be_replaced.insert(desc_txiter->GetTx().GetHash());
57 : : }
58 : 37022 : }
59 : : }
60 : :
61 : : // No unconfirmed UTXOs, so nothing mempool-related needs to be calculated.
62 [ + + ]: 4540 : if (m_requested_outpoints_by_txid.empty()) return;
63 : :
64 : : // Calculate the cluster and construct the entry map.
65 [ + - ]: 2806 : auto txids_needed{m_requested_outpoints_by_txid | std::views::keys};
66 [ + - + - : 5612 : const auto cluster = mempool.GatherClusters({txids_needed.begin(), txids_needed.end()});
- + ]
67 [ - + ]: 2806 : if (cluster.empty()) {
68 : : // An empty cluster means that at least one of the transactions is missing from the mempool
69 : : // (should not be possible given processing above) or DoS limit was hit.
70 : 0 : m_ready_to_calculate = false;
71 : 0 : return;
72 : : }
73 : :
74 : : // Add every entry to m_entries_by_txid and m_entries, except the ones that will be replaced.
75 [ + + ]: 392075 : for (const auto& txiter : cluster) {
76 [ + + ]: 389269 : if (!m_to_be_replaced.count(txiter->GetTx().GetHash())) {
77 [ + - + - : 454114 : auto [mapiter, success] = m_entries_by_txid.emplace(txiter->GetTx().GetHash(),
+ - ]
78 [ + - + - : 681171 : MiniMinerMempoolEntry{/*tx_in=*/txiter->GetSharedTx(),
+ - ]
79 [ + - ]: 227057 : /*vsize_self=*/txiter->GetTxSize(),
80 : : /*vsize_ancestor=*/txiter->GetSizeWithAncestors(),
81 : : /*fee_self=*/txiter->GetModifiedFee(),
82 [ + - + - : 454114 : /*fee_ancestor=*/txiter->GetModFeesWithAncestors()});
+ - ]
83 [ + - ]: 227057 : m_entries.push_back(mapiter);
84 : : } else {
85 : 162212 : auto outpoints_it = m_requested_outpoints_by_txid.find(txiter->GetTx().GetHash());
86 [ + + ]: 162212 : if (outpoints_it != m_requested_outpoints_by_txid.end()) {
87 : : // This UTXO is the output of a to-be-replaced transaction. Bump fee is 0; spending
88 : : // this UTXO is impossible as it will no longer exist after the replacement.
89 [ + + ]: 193730 : for (const auto& outpoint : outpoints_it->second) {
90 [ + - ]: 96870 : m_bump_fees.emplace(outpoint, 0);
91 : : }
92 : 96860 : m_requested_outpoints_by_txid.erase(outpoints_it);
93 : : }
94 : : }
95 : : }
96 : :
97 : : // Build the m_descendant_set_by_txid cache.
98 [ + + ]: 392075 : for (const auto& txiter : cluster) {
99 : 389269 : const auto& txid = txiter->GetTx().GetHash();
100 : : // Cache descendants for future use. Unlike the real mempool, a descendant MiniMinerMempoolEntry
101 : : // will not exist without its ancestor MiniMinerMempoolEntry, so these sets won't be invalidated.
102 : 389269 : std::vector<MockEntryMap::iterator> cached_descendants;
103 : 389269 : const bool remove{m_to_be_replaced.count(txid) > 0};
104 [ + - ]: 389269 : CTxMemPool::setEntries descendants;
105 [ + - ]: 389269 : mempool.CalculateDescendants(txiter, descendants);
106 [ + - ]: 389269 : Assume(descendants.count(txiter) > 0);
107 [ + + ]: 38359623 : for (const auto& desc_txiter : descendants) {
108 : 37970354 : const auto txid_desc = desc_txiter->GetTx().GetHash();
109 : 37970354 : const bool remove_desc{m_to_be_replaced.count(txid_desc) > 0};
110 : 37970354 : auto desc_it{m_entries_by_txid.find(txid_desc)};
111 [ + - ]: 37970354 : Assume((desc_it == m_entries_by_txid.end()) == remove_desc);
112 [ + + + - ]: 37970354 : if (remove) Assume(remove_desc);
113 : : // It's possible that remove=false but remove_desc=true.
114 [ + + ]: 18586404 : if (!remove && !remove_desc) {
115 [ + - ]: 11886356 : cached_descendants.push_back(desc_it);
116 : : }
117 : : }
118 [ + + ]: 389269 : if (remove) {
119 [ + - ]: 162212 : Assume(cached_descendants.empty());
120 : : } else {
121 [ + - ]: 227057 : m_descendant_set_by_txid.emplace(txid, cached_descendants);
122 : : }
123 : 389269 : }
124 : :
125 : : // Release the mempool lock; we now have all the information we need for a subset of the entries
126 : : // we care about. We will solely operate on the MiniMinerMempoolEntry map from now on.
127 [ + - ]: 2806 : Assume(m_in_block.empty());
128 [ - + + - ]: 2806 : Assume(m_requested_outpoints_by_txid.size() <= outpoints.size());
129 [ + - ]: 2806 : SanityCheck();
130 [ + - ]: 7346 : }
131 : :
132 : 0 : MiniMiner::MiniMiner(const std::vector<MiniMinerMempoolEntry>& manual_entries,
133 : 0 : const std::map<Txid, std::set<Txid>>& descendant_caches)
134 : : {
135 [ # # ]: 0 : for (const auto& entry : manual_entries) {
136 : 0 : const auto& txid = entry.GetTx().GetHash();
137 : : // We need to know the descendant set of every transaction.
138 [ # # # # ]: 0 : if (!Assume(descendant_caches.count(txid) > 0)) {
139 : 0 : m_ready_to_calculate = false;
140 : 0 : return;
141 : : }
142 : : // Just forward these args onto MiniMinerMempoolEntry
143 [ # # # # ]: 0 : auto [mapiter, success] = m_entries_by_txid.emplace(txid, entry);
144 : : // Txids must be unique; this txid shouldn't already be an entry in m_entries_by_txid
145 [ # # # # : 0 : if (Assume(success)) m_entries.push_back(mapiter);
# # ]
146 : : }
147 : : // Descendant cache is already built, but we need to translate them to m_entries_by_txid iters.
148 [ # # # # ]: 0 : for (const auto& [txid, desc_txids] : descendant_caches) {
149 : : // Descendant cache should include at least the tx itself.
150 [ # # # # ]: 0 : if (!Assume(!desc_txids.empty())) {
151 : 0 : m_ready_to_calculate = false;
152 : 0 : return;
153 : : }
154 : 0 : std::vector<MockEntryMap::iterator> descendants;
155 [ # # ]: 0 : for (const auto& desc_txid : desc_txids) {
156 : 0 : auto desc_it{m_entries_by_txid.find(desc_txid)};
157 : : // Descendants should only include transactions with corresponding entries.
158 [ # # # # ]: 0 : if (!Assume(desc_it != m_entries_by_txid.end())) {
159 : 0 : m_ready_to_calculate = false;
160 : 0 : return;
161 : : } else {
162 [ # # ]: 0 : descendants.emplace_back(desc_it);
163 : : }
164 : : }
165 [ # # ]: 0 : m_descendant_set_by_txid.emplace(txid, descendants);
166 : 0 : }
167 [ # # ]: 0 : Assume(m_to_be_replaced.empty());
168 [ # # ]: 0 : Assume(m_requested_outpoints_by_txid.empty());
169 [ # # ]: 0 : Assume(m_bump_fees.empty());
170 [ # # ]: 0 : Assume(m_inclusion_order.empty());
171 [ # # ]: 0 : SanityCheck();
172 : 0 : }
173 : :
174 : : // Compare by min(ancestor feerate, individual feerate), then txid
175 : : //
176 : : // Under the ancestor-based mining approach, high-feerate children can pay for parents, but high-feerate
177 : : // parents do not incentive inclusion of their children. Therefore the mining algorithm only considers
178 : : // transactions for inclusion on basis of the minimum of their own feerate or their ancestor feerate.
179 : : struct AncestorFeerateComparator
180 : : {
181 : : template<typename I>
182 [ + + ]: 82594883 : bool operator()(const I& a, const I& b) const {
183 : 165189766 : auto min_feerate = [](const MiniMinerMempoolEntry& e) -> FeeFrac {
184 : 165189766 : FeeFrac self_feerate(e.GetModifiedFee(), e.GetTxSize());
185 : 165189766 : FeeFrac ancestor_feerate(e.GetModFeesWithAncestors(), e.GetSizeWithAncestors());
186 : 165189766 : return std::min(ancestor_feerate, self_feerate);
187 : : };
188 : 82594883 : FeeFrac a_feerate{min_feerate(a->second)};
189 [ + + ]: 82594883 : FeeFrac b_feerate{min_feerate(b->second)};
190 : 54359002 : if (a_feerate != b_feerate) {
191 : 28235881 : return a_feerate > b_feerate;
192 : : }
193 : : // Use txid as tiebreaker for stable sorting
194 : 54359002 : return a->first < b->first;
195 : : }
196 : : };
197 : :
198 : 100868 : void MiniMiner::DeleteAncestorPackage(const std::set<MockEntryMap::iterator, IteratorComparator>& ancestors)
199 : : {
200 : 100868 : Assume(ancestors.size() >= 1);
201 : : // "Mine" all transactions in this ancestor set.
202 [ + + ]: 292281 : for (auto& anc : ancestors) {
203 : 191413 : Assume(m_in_block.count(anc->first) == 0);
204 : 191413 : m_in_block.insert(anc->first);
205 : 191413 : m_total_fees += anc->second.GetModifiedFee();
206 : 191413 : m_total_vsize += anc->second.GetTxSize();
207 : 191413 : auto it = m_descendant_set_by_txid.find(anc->first);
208 : : // Each entry’s descendant set includes itself
209 : 191413 : Assume(it != m_descendant_set_by_txid.end());
210 [ + + ]: 9578656 : for (auto& descendant : it->second) {
211 : : // If these fail, we must be double-deducting.
212 : 9387243 : Assume(descendant->second.GetModFeesWithAncestors() >= anc->second.GetModifiedFee());
213 : 9387243 : Assume(descendant->second.GetSizeWithAncestors() >= anc->second.GetTxSize());
214 : 9387243 : descendant->second.UpdateAncestorState(-anc->second.GetTxSize(), -anc->second.GetModifiedFee());
215 : : }
216 : : }
217 : : // Delete these entries.
218 [ + + ]: 292281 : for (const auto& anc : ancestors) {
219 : 191413 : m_descendant_set_by_txid.erase(anc->first);
220 : : // The above loop should have deducted each ancestor's size and fees from each of their
221 : : // respective descendants exactly once.
222 : 191413 : Assume(anc->second.GetModFeesWithAncestors() == 0);
223 : 191413 : Assume(anc->second.GetSizeWithAncestors() == 0);
224 : 191413 : auto vec_it = std::find(m_entries.begin(), m_entries.end(), anc);
225 : 191413 : Assume(vec_it != m_entries.end());
226 : 191413 : m_entries.erase(vec_it);
227 : 191413 : m_entries_by_txid.erase(anc);
228 : : }
229 : 100868 : }
230 : :
231 : 103674 : void MiniMiner::SanityCheck() const
232 : : {
233 : : // m_entries, m_entries_by_txid, and m_descendant_set_by_txid all same size
234 [ - + ]: 103674 : Assume(m_entries.size() == m_entries_by_txid.size());
235 [ - + ]: 103674 : Assume(m_entries.size() == m_descendant_set_by_txid.size());
236 : : // Cached ancestor values should be at least as large as the transaction's own fee and size
237 [ + - + - ]: 11339989 : Assume(std::all_of(m_entries.begin(), m_entries.end(), [](const auto& entry) {
238 : : return entry->second.GetSizeWithAncestors() >= entry->second.GetTxSize() &&
239 : : entry->second.GetModFeesWithAncestors() >= entry->second.GetModifiedFee();}));
240 : : // None of the entries should be to-be-replaced transactions
241 : 4603338 : Assume(std::all_of(m_to_be_replaced.begin(), m_to_be_replaced.end(),
242 : : [&](const auto& txid){return m_entries_by_txid.find(txid) == m_entries_by_txid.end();}));
243 : 103674 : }
244 : :
245 : 4540 : void MiniMiner::BuildMockTemplate(std::optional<CFeeRate> target_feerate)
246 : : {
247 : 4540 : const auto num_txns{m_entries_by_txid.size()};
248 : 4540 : uint32_t sequence_num{0};
249 [ + + ]: 105408 : while (!m_entries_by_txid.empty()) {
250 : : // Sort again, since transaction removal may change some m_entries' ancestor feerates.
251 : 101629 : std::sort(m_entries.begin(), m_entries.end(), AncestorFeerateComparator());
252 : :
253 : : // Pick highest ancestor feerate entry.
254 : 101629 : auto best_iter = m_entries.begin();
255 : 101629 : Assume(best_iter != m_entries.end());
256 [ + - ]: 101629 : const auto ancestor_package_size = (*best_iter)->second.GetSizeWithAncestors();
257 [ + - ]: 101629 : const auto ancestor_package_fee = (*best_iter)->second.GetModFeesWithAncestors();
258 : : // Stop here. Everything that didn't "make it into the block" has bumpfee.
259 [ + - + + ]: 203258 : if (target_feerate.has_value() &&
260 : 101629 : ancestor_package_fee < target_feerate->GetFee(ancestor_package_size)) {
261 : : break;
262 : : }
263 : :
264 : : // Calculate ancestors on the fly. This lookup should be fairly cheap, and ancestor sets
265 : : // change at every iteration, so this is more efficient than maintaining a cache.
266 [ + - ]: 100868 : std::set<MockEntryMap::iterator, IteratorComparator> ancestors;
267 : 100868 : {
268 : 100868 : std::set<MockEntryMap::iterator, IteratorComparator> to_process;
269 [ + - ]: 100868 : to_process.insert(*best_iter);
270 [ + + ]: 292281 : while (!to_process.empty()) {
271 [ + - ]: 191413 : auto iter = to_process.begin();
272 [ + - ]: 191413 : Assume(iter != to_process.end());
273 [ + - ]: 191413 : ancestors.insert(*iter);
274 [ + + ]: 1234058 : for (const auto& input : (*iter)->second.GetTx().vin) {
275 [ + + ]: 1042645 : if (auto parent_it{m_entries_by_txid.find(input.prevout.hash)}; parent_it != m_entries_by_txid.end()) {
276 [ + + ]: 710371 : if (ancestors.count(parent_it) == 0) {
277 [ + - ]: 550234 : to_process.insert(parent_it);
278 : : }
279 : : }
280 : : }
281 : 191413 : to_process.erase(iter);
282 : : }
283 : 0 : }
284 : : // Track the order in which transactions were selected.
285 [ + + ]: 292281 : for (const auto& ancestor : ancestors) {
286 [ + - ]: 191413 : m_inclusion_order.emplace(ancestor->first, sequence_num);
287 : : }
288 [ + - ]: 100868 : DeleteAncestorPackage(ancestors);
289 [ + - ]: 100868 : SanityCheck();
290 : 100868 : ++sequence_num;
291 : 100868 : }
292 [ - + ]: 4540 : if (!target_feerate.has_value()) {
293 : 0 : Assume(m_in_block.size() == num_txns);
294 : : } else {
295 [ + + + - ]: 6941 : Assume(m_in_block.empty() || m_total_fees >= target_feerate->GetFee(m_total_vsize));
296 : : }
297 [ + + - + ]: 4540 : Assume(m_in_block.empty() || sequence_num > 0);
298 : 4540 : Assume(m_in_block.size() == m_inclusion_order.size());
299 : : // Do not try to continue building the block template with a different feerate.
300 : 4540 : m_ready_to_calculate = false;
301 : 4540 : }
302 : :
303 : :
304 : 0 : std::map<Txid, uint32_t> MiniMiner::Linearize()
305 : : {
306 : 0 : BuildMockTemplate(std::nullopt);
307 : 0 : return m_inclusion_order;
308 : : }
309 : :
310 : 2604 : std::map<COutPoint, CAmount> MiniMiner::CalculateBumpFees(const CFeeRate& target_feerate)
311 : : {
312 [ - + ]: 2604 : if (!m_ready_to_calculate) return {};
313 : : // Build a block template until the target feerate is hit.
314 : 2604 : BuildMockTemplate(target_feerate);
315 : :
316 : : // Each transaction that "made it into the block" has a bumpfee of 0, i.e. they are part of an
317 : : // ancestor package with at least the target feerate and don't need to be bumped.
318 [ + + ]: 74237 : for (const auto& txid : m_in_block) {
319 : : // Not all of the block transactions were necessarily requested.
320 : 71633 : auto it = m_requested_outpoints_by_txid.find(txid);
321 [ + + ]: 71633 : if (it != m_requested_outpoints_by_txid.end()) {
322 [ + + ]: 87036 : for (const auto& outpoint : it->second) {
323 : 43614 : m_bump_fees.emplace(outpoint, 0);
324 : : }
325 : 43422 : m_requested_outpoints_by_txid.erase(it);
326 : : }
327 : : }
328 : :
329 : : // A transactions and its ancestors will only be picked into a block when
330 : : // both the ancestor set feerate and the individual feerate meet the target
331 : : // feerate.
332 : : //
333 : : // We had to convince ourselves that after running the mini miner and
334 : : // picking all eligible transactions into our MockBlockTemplate, there
335 : : // could still be transactions remaining that have a lower individual
336 : : // feerate than their ancestor feerate. So here is an example:
337 : : //
338 : : // ┌─────────────────┐
339 : : // │ │
340 : : // │ Grandparent │
341 : : // │ 1700 vB │
342 : : // │ 1700 sats │ Target feerate: 10 s/vB
343 : : // │ 1 s/vB │ GP Ancestor Set Feerate (ASFR): 1 s/vB
344 : : // │ │ P1_ASFR: 9.84 s/vB
345 : : // └──────▲───▲──────┘ P2_ASFR: 2.47 s/vB
346 : : // │ │ C_ASFR: 10.27 s/vB
347 : : // ┌───────────────┐ │ │ ┌──────────────┐
348 : : // │ ├────┘ └────┤ │ ⇒ C_FR < TFR < C_ASFR
349 : : // │ Parent 1 │ │ Parent 2 │
350 : : // │ 200 vB │ │ 200 vB │
351 : : // │ 17000 sats │ │ 3000 sats │
352 : : // │ 85 s/vB │ │ 15 s/vB │
353 : : // │ │ │ │
354 : : // └───────────▲───┘ └───▲──────────┘
355 : : // │ │
356 : : // │ ┌───────────┐ │
357 : : // └────┤ ├────┘
358 : : // │ Child │
359 : : // │ 100 vB │
360 : : // │ 900 sats │
361 : : // │ 9 s/vB │
362 : : // │ │
363 : : // └───────────┘
364 : : //
365 : : // We therefore calculate both the bump fee that is necessary to elevate
366 : : // the individual transaction to the target feerate:
367 : : // target_feerate × tx_size - tx_fees
368 : : // and the bump fee that is necessary to bump the entire ancestor set to
369 : : // the target feerate:
370 : : // target_feerate × ancestor_set_size - ancestor_set_fees
371 : : // By picking the maximum from the two, we ensure that a transaction meets
372 : : // both criteria.
373 [ + + ]: 17208 : for (const auto& [txid, outpoints] : m_requested_outpoints_by_txid) {
374 : 14604 : auto it = m_entries_by_txid.find(txid);
375 : 14604 : Assume(it != m_entries_by_txid.end());
376 [ + - ]: 14604 : if (it != m_entries_by_txid.end()) {
377 [ + - ]: 29208 : Assume(target_feerate.GetFee(it->second.GetSizeWithAncestors()) > std::min(it->second.GetModifiedFee(), it->second.GetModFeesWithAncestors()));
378 : 14604 : CAmount bump_fee_with_ancestors = target_feerate.GetFee(it->second.GetSizeWithAncestors()) - it->second.GetModFeesWithAncestors();
379 [ + + ]: 14604 : CAmount bump_fee_individual = target_feerate.GetFee(it->second.GetTxSize()) - it->second.GetModifiedFee();
380 [ + + ]: 14604 : const CAmount bump_fee{std::max(bump_fee_with_ancestors, bump_fee_individual)};
381 : 14604 : Assume(bump_fee >= 0);
382 [ + + ]: 29474 : for (const auto& outpoint : outpoints) {
383 : 14870 : m_bump_fees.emplace(outpoint, bump_fee);
384 : : }
385 : : }
386 : : }
387 : 2604 : return m_bump_fees;
388 : : }
389 : :
390 : 1049 : std::optional<CAmount> MiniMiner::CalculateTotalBumpFees(const CFeeRate& target_feerate)
391 : : {
392 [ - + ]: 1049 : if (!m_ready_to_calculate) return std::nullopt;
393 : : // Build a block template until the target feerate is hit.
394 : 1049 : BuildMockTemplate(target_feerate);
395 : :
396 : : // All remaining ancestors that are not part of m_in_block must be bumped, but no other relatives
397 : 1049 : std::set<MockEntryMap::iterator, IteratorComparator> ancestors;
398 : 1049 : std::set<MockEntryMap::iterator, IteratorComparator> to_process;
399 [ + + ]: 59075 : for (const auto& [txid, outpoints] : m_requested_outpoints_by_txid) {
400 : : // Skip any ancestors that already have a miner score higher than the target feerate
401 : : // (already "made it" into the block)
402 [ + + ]: 58026 : if (m_in_block.count(txid)) continue;
403 : 14604 : auto iter = m_entries_by_txid.find(txid);
404 [ - + ]: 14604 : if (iter == m_entries_by_txid.end()) continue;
405 [ + - ]: 14604 : to_process.insert(iter);
406 [ + - ]: 14604 : ancestors.insert(iter);
407 : : }
408 : :
409 : 1049 : std::set<Txid> has_been_processed;
410 [ + + ]: 16877 : while (!to_process.empty()) {
411 : 15828 : auto iter = to_process.begin();
412 : 15828 : const CTransaction& tx = (*iter)->second.GetTx();
413 [ + + ]: 183108 : for (const auto& input : tx.vin) {
414 [ + + ]: 167280 : if (auto parent_it{m_entries_by_txid.find(input.prevout.hash)}; parent_it != m_entries_by_txid.end()) {
415 [ + + ]: 144635 : if (!has_been_processed.count(input.prevout.hash)) {
416 [ + - ]: 71659 : to_process.insert(parent_it);
417 : : }
418 [ + - ]: 144635 : ancestors.insert(parent_it);
419 : : }
420 : : }
421 [ + - ]: 15828 : has_been_processed.insert(tx.GetHash());
422 : 15828 : to_process.erase(iter);
423 : : }
424 : 1049 : const auto ancestor_package_size = std::accumulate(ancestors.cbegin(), ancestors.cend(), int64_t{0},
425 : 15828 : [](int64_t sum, const auto it) {return sum + it->second.GetTxSize();});
426 : 1049 : const auto ancestor_package_fee = std::accumulate(ancestors.cbegin(), ancestors.cend(), CAmount{0},
427 : 15828 : [](CAmount sum, const auto it) {return sum + it->second.GetModifiedFee();});
428 [ + - ]: 1049 : return target_feerate.GetFee(ancestor_package_size) - ancestor_package_fee;
429 : 1049 : }
430 : : } // namespace node
|
