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 [ + - ]: 3277 : MiniMiner::MiniMiner(const CTxMemPool& mempool, const std::vector<COutPoint>& outpoints)
25 : : {
26 [ + - ]: 3277 : 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 [ + + ]: 105289 : for (const auto& outpoint : outpoints) {
31 [ + - + + ]: 102012 : 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 [ + - ]: 9776 : m_bump_fees.emplace(outpoint, 0);
36 : 9776 : 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 [ + - + - ]: 92236 : m_requested_outpoints_by_txid[outpoint.hash].push_back(outpoint);
42 : :
43 [ + - + + ]: 92236 : 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 [ + - ]: 10594 : CTxMemPool::setEntries descendants;
54 [ + - + - ]: 21188 : mempool.CalculateDescendants(mempool.GetIter(ptx->GetHash()).value(), descendants);
55 [ + + ]: 181744 : for (const auto& desc_txiter : descendants) {
56 [ + - ]: 171150 : m_to_be_replaced.insert(desc_txiter->GetTx().GetHash());
57 : : }
58 : 10594 : }
59 : : }
60 : :
61 : : // No unconfirmed UTXOs, so nothing mempool-related needs to be calculated.
62 [ + + ]: 3277 : if (m_requested_outpoints_by_txid.empty()) return;
63 : :
64 : : // Calculate the cluster and construct the entry map.
65 [ + - ]: 2308 : auto txids_needed{m_requested_outpoints_by_txid | std::views::keys};
66 [ + - + - : 4616 : const auto cluster = mempool.GatherClusters({txids_needed.begin(), txids_needed.end()});
- + ]
67 [ - + ]: 2308 : 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 [ + + ]: 145700 : for (const auto& txiter : cluster) {
76 [ + + ]: 143392 : if (!m_to_be_replaced.count(txiter->GetTx().GetHash())) {
77 [ + - + - ]: 106746 : auto [ancestor_count, ancestor_size, ancestor_fee] = mempool.CalculateAncestorData(*txiter);
78 [ + - + - : 213492 : auto [mapiter, success] = m_entries_by_txid.emplace(txiter->GetTx().GetHash(),
+ - ]
79 [ + - + - : 320238 : MiniMinerMempoolEntry{/*tx_in=*/txiter->GetSharedTx(),
+ - ]
80 [ + - ]: 106746 : /*vsize_self=*/txiter->GetTxSize(),
81 : : /*vsize_ancestor=*/int64_t(ancestor_size),
82 : : /*fee_self=*/txiter->GetModifiedFee(),
83 [ + - + - : 213492 : /*fee_ancestor=*/ancestor_fee});
+ - ]
84 [ + - ]: 106746 : m_entries.push_back(mapiter);
85 : : } else {
86 : 36646 : auto outpoints_it = m_requested_outpoints_by_txid.find(txiter->GetTx().GetHash());
87 [ + + ]: 36646 : if (outpoints_it != m_requested_outpoints_by_txid.end()) {
88 : : // This UTXO is the output of a to-be-replaced transaction. Bump fee is 0; spending
89 : : // this UTXO is impossible as it will no longer exist after the replacement.
90 [ + + ]: 36102 : for (const auto& outpoint : outpoints_it->second) {
91 [ + - ]: 18056 : m_bump_fees.emplace(outpoint, 0);
92 : : }
93 : 18046 : m_requested_outpoints_by_txid.erase(outpoints_it);
94 : : }
95 : : }
96 : : }
97 : :
98 : : // Build the m_descendant_set_by_txid cache.
99 [ + + ]: 145700 : for (const auto& txiter : cluster) {
100 : 143392 : const auto& txid = txiter->GetTx().GetHash();
101 : : // Cache descendants for future use. Unlike the real mempool, a descendant MiniMinerMempoolEntry
102 : : // will not exist without its ancestor MiniMinerMempoolEntry, so these sets won't be invalidated.
103 : 143392 : std::vector<MockEntryMap::iterator> cached_descendants;
104 : 143392 : const bool remove{m_to_be_replaced.count(txid) > 0};
105 [ + - ]: 143392 : CTxMemPool::setEntries descendants;
106 [ + - ]: 143392 : mempool.CalculateDescendants(txiter, descendants);
107 [ - + ]: 143392 : Assume(descendants.count(txiter) > 0);
108 [ + + ]: 1787624 : for (const auto& desc_txiter : descendants) {
109 : 1644232 : const auto txid_desc = desc_txiter->GetTx().GetHash();
110 : 1644232 : const bool remove_desc{m_to_be_replaced.count(txid_desc) > 0};
111 : 1644232 : auto desc_it{m_entries_by_txid.find(txid_desc)};
112 [ - + ]: 1644232 : Assume((desc_it == m_entries_by_txid.end()) == remove_desc);
113 [ + + - + ]: 2769988 : if (remove) Assume(remove_desc);
114 : : // It's possible that remove=false but remove_desc=true.
115 [ + + ]: 1125756 : if (!remove && !remove_desc) {
116 [ + - ]: 829640 : cached_descendants.push_back(desc_it);
117 : : }
118 : : }
119 [ + + ]: 143392 : if (remove) {
120 [ - + ]: 143392 : Assume(cached_descendants.empty());
121 : : } else {
122 [ + - ]: 106746 : m_descendant_set_by_txid.emplace(txid, cached_descendants);
123 : : }
124 : 143392 : }
125 : :
126 : : // Release the mempool lock; we now have all the information we need for a subset of the entries
127 : : // we care about. We will solely operate on the MiniMinerMempoolEntry map from now on.
128 [ - + ]: 2308 : Assume(m_in_block.empty());
129 [ - + - + ]: 2308 : Assume(m_requested_outpoints_by_txid.size() <= outpoints.size());
130 [ + - ]: 2308 : SanityCheck();
131 [ + - ]: 5585 : }
132 : :
133 : 0 : MiniMiner::MiniMiner(const std::vector<MiniMinerMempoolEntry>& manual_entries,
134 : 0 : const std::map<Txid, std::set<Txid>>& descendant_caches)
135 : : {
136 [ # # ]: 0 : for (const auto& entry : manual_entries) {
137 : 0 : const auto& txid = entry.GetTx().GetHash();
138 : : // We need to know the descendant set of every transaction.
139 [ # # ]: 0 : if (!Assume(descendant_caches.count(txid) > 0)) {
140 : 0 : m_ready_to_calculate = false;
141 : 0 : return;
142 : : }
143 : : // Just forward these args onto MiniMinerMempoolEntry
144 [ # # # # ]: 0 : auto [mapiter, success] = m_entries_by_txid.emplace(txid, entry);
145 : : // Txids must be unique; this txid shouldn't already be an entry in m_entries_by_txid
146 [ # # # # : 0 : if (Assume(success)) m_entries.push_back(mapiter);
# # ]
147 : : }
148 : : // Descendant cache is already built, but we need to translate them to m_entries_by_txid iters.
149 [ # # # # ]: 0 : for (const auto& [txid, desc_txids] : descendant_caches) {
150 : : // Descendant cache should include at least the tx itself.
151 [ # # ]: 0 : if (!Assume(!desc_txids.empty())) {
152 : 0 : m_ready_to_calculate = false;
153 : 0 : return;
154 : : }
155 : 0 : std::vector<MockEntryMap::iterator> descendants;
156 [ # # ]: 0 : for (const auto& desc_txid : desc_txids) {
157 : 0 : auto desc_it{m_entries_by_txid.find(desc_txid)};
158 : : // Descendants should only include transactions with corresponding entries.
159 [ # # # # ]: 0 : if (!Assume(desc_it != m_entries_by_txid.end())) {
160 : 0 : m_ready_to_calculate = false;
161 : 0 : return;
162 : : } else {
163 [ # # ]: 0 : descendants.emplace_back(desc_it);
164 : : }
165 : : }
166 [ # # ]: 0 : m_descendant_set_by_txid.emplace(txid, descendants);
167 : 0 : }
168 [ # # ]: 0 : Assume(m_to_be_replaced.empty());
169 [ # # ]: 0 : Assume(m_requested_outpoints_by_txid.empty());
170 [ # # ]: 0 : Assume(m_bump_fees.empty());
171 [ # # ]: 0 : Assume(m_inclusion_order.empty());
172 [ # # ]: 0 : SanityCheck();
173 : 0 : }
174 : :
175 : : // Compare by min(ancestor feerate, individual feerate), then txid
176 : : //
177 : : // Under the ancestor-based mining approach, high-feerate children can pay for parents, but high-feerate
178 : : // parents do not incentive inclusion of their children. Therefore the mining algorithm only considers
179 : : // transactions for inclusion on basis of the minimum of their own feerate or their ancestor feerate.
180 : : struct AncestorFeerateComparator
181 : : {
182 : : template<typename I>
183 [ + + ]: 7851122 : bool operator()(const I& a, const I& b) const {
184 : 15702244 : auto min_feerate = [](const MiniMinerMempoolEntry& e) -> FeeFrac {
185 : 15702244 : FeeFrac self_feerate(e.GetModifiedFee(), e.GetTxSize());
186 : 15702244 : FeeFrac ancestor_feerate(e.GetModFeesWithAncestors(), e.GetSizeWithAncestors());
187 : 15702244 : return std::min(ancestor_feerate, self_feerate);
188 : : };
189 : 7851122 : FeeFrac a_feerate{min_feerate(a->second)};
190 [ + + ]: 7851122 : FeeFrac b_feerate{min_feerate(b->second)};
191 : 5738856 : if (a_feerate != b_feerate) {
192 : 2112266 : return a_feerate > b_feerate;
193 : : }
194 : : // Use txid as tiebreaker for stable sorting
195 : 5738856 : return a->first < b->first;
196 : : }
197 : : };
198 : :
199 : 45628 : void MiniMiner::DeleteAncestorPackage(const std::set<MockEntryMap::iterator, IteratorComparator>& ancestors)
200 : : {
201 [ - + ]: 45628 : Assume(ancestors.size() >= 1);
202 : : // "Mine" all transactions in this ancestor set.
203 [ + + ]: 103776 : for (auto& anc : ancestors) {
204 [ - + ]: 58148 : Assume(m_in_block.count(anc->first) == 0);
205 : 58148 : m_in_block.insert(anc->first);
206 : 58148 : m_total_fees += anc->second.GetModifiedFee();
207 : 58148 : m_total_vsize += anc->second.GetTxSize();
208 : 58148 : auto it = m_descendant_set_by_txid.find(anc->first);
209 : : // Each entry’s descendant set includes itself
210 [ - + ]: 58148 : Assume(it != m_descendant_set_by_txid.end());
211 [ + + ]: 391662 : for (auto& descendant : it->second) {
212 : : // If these fail, we must be double-deducting.
213 [ - + ]: 333514 : Assume(descendant->second.GetModFeesWithAncestors() >= anc->second.GetModifiedFee());
214 [ - + ]: 333514 : Assume(descendant->second.GetSizeWithAncestors() >= anc->second.GetTxSize());
215 : 333514 : descendant->second.UpdateAncestorState(-anc->second.GetTxSize(), -anc->second.GetModifiedFee());
216 : : }
217 : : }
218 : : // Delete these entries.
219 [ + + ]: 103776 : for (const auto& anc : ancestors) {
220 : 58148 : m_descendant_set_by_txid.erase(anc->first);
221 : : // The above loop should have deducted each ancestor's size and fees from each of their
222 : : // respective descendants exactly once.
223 [ - + ]: 58148 : Assume(anc->second.GetModFeesWithAncestors() == 0);
224 [ - + ]: 58148 : Assume(anc->second.GetSizeWithAncestors() == 0);
225 : 58148 : auto vec_it = std::find(m_entries.begin(), m_entries.end(), anc);
226 [ - + ]: 58148 : Assume(vec_it != m_entries.end());
227 : 58148 : m_entries.erase(vec_it);
228 : 58148 : m_entries_by_txid.erase(anc);
229 : : }
230 : 45628 : }
231 : :
232 : 47936 : void MiniMiner::SanityCheck() const
233 : : {
234 : : // m_entries, m_entries_by_txid, and m_descendant_set_by_txid all same size
235 [ - + - + ]: 47936 : Assume(m_entries.size() == m_entries_by_txid.size());
236 [ - + - + ]: 47936 : Assume(m_entries.size() == m_descendant_set_by_txid.size());
237 : : // Cached ancestor values should be at least as large as the transaction's own fee and size
238 [ + - + - : 1661740 : Assume(std::all_of(m_entries.begin(), m_entries.end(), [](const auto& entry) {
- + ]
239 : : return entry->second.GetSizeWithAncestors() >= entry->second.GetTxSize() &&
240 : : entry->second.GetModFeesWithAncestors() >= entry->second.GetModifiedFee();}));
241 : : // None of the entries should be to-be-replaced transactions
242 [ - + ]: 394920 : Assume(std::all_of(m_to_be_replaced.begin(), m_to_be_replaced.end(),
243 : : [&](const auto& txid){return m_entries_by_txid.find(txid) == m_entries_by_txid.end();}));
244 : 47936 : }
245 : :
246 : 3277 : void MiniMiner::BuildMockTemplate(std::optional<CFeeRate> target_feerate)
247 : : {
248 : 3277 : const auto num_txns{m_entries_by_txid.size()};
249 : 3277 : uint32_t sequence_num{0};
250 [ + + ]: 48905 : while (!m_entries_by_txid.empty()) {
251 : : // Sort again, since transaction removal may change some m_entries' ancestor feerates.
252 : 46646 : std::sort(m_entries.begin(), m_entries.end(), AncestorFeerateComparator());
253 : :
254 : : // Pick highest ancestor feerate entry.
255 [ - + ]: 46646 : auto best_iter = m_entries.begin();
256 [ - + ]: 46646 : Assume(best_iter != m_entries.end());
257 [ + - ]: 46646 : const auto ancestor_package_size = (*best_iter)->second.GetSizeWithAncestors();
258 [ + - ]: 46646 : const auto ancestor_package_fee = (*best_iter)->second.GetModFeesWithAncestors();
259 : : // Stop here. Everything that didn't "make it into the block" has bumpfee.
260 [ + - + + ]: 93292 : if (target_feerate.has_value() &&
261 : 46646 : ancestor_package_fee < target_feerate->GetFee(ancestor_package_size)) {
262 : : break;
263 : : }
264 : :
265 : : // Calculate ancestors on the fly. This lookup should be fairly cheap, and ancestor sets
266 : : // change at every iteration, so this is more efficient than maintaining a cache.
267 [ + - ]: 45628 : std::set<MockEntryMap::iterator, IteratorComparator> ancestors;
268 : 45628 : {
269 : 45628 : std::set<MockEntryMap::iterator, IteratorComparator> to_process;
270 [ + - ]: 45628 : to_process.insert(*best_iter);
271 [ + + ]: 103776 : while (!to_process.empty()) {
272 [ - + ]: 58148 : auto iter = to_process.begin();
273 [ - + ]: 58148 : Assume(iter != to_process.end());
274 [ + - ]: 58148 : ancestors.insert(*iter);
275 [ + + ]: 308200 : for (const auto& input : (*iter)->second.GetTx().vin) {
276 [ + + ]: 250052 : if (auto parent_it{m_entries_by_txid.find(input.prevout.hash)}; parent_it != m_entries_by_txid.end()) {
277 [ + + ]: 56708 : if (ancestors.count(parent_it) == 0) {
278 [ + - ]: 46906 : to_process.insert(parent_it);
279 : : }
280 : : }
281 : : }
282 : 58148 : to_process.erase(iter);
283 : : }
284 : 0 : }
285 : : // Track the order in which transactions were selected.
286 [ + + ]: 103776 : for (const auto& ancestor : ancestors) {
287 [ + - ]: 58148 : m_inclusion_order.emplace(ancestor->first, sequence_num);
288 : : }
289 [ + - ]: 45628 : DeleteAncestorPackage(ancestors);
290 [ + - ]: 45628 : SanityCheck();
291 : 45628 : ++sequence_num;
292 : 45628 : }
293 [ - + ]: 3277 : if (!target_feerate.has_value()) {
294 [ # # ]: 0 : Assume(m_in_block.size() == num_txns);
295 : : } else {
296 [ + + + - : 4783 : Assume(m_in_block.empty() || m_total_fees >= target_feerate->GetFee(m_total_vsize));
- + ]
297 : : }
298 [ + + - + : 3277 : Assume(m_in_block.empty() || sequence_num > 0);
- + ]
299 [ - + ]: 3277 : Assume(m_in_block.size() == m_inclusion_order.size());
300 : : // Do not try to continue building the block template with a different feerate.
301 : 3277 : m_ready_to_calculate = false;
302 : 3277 : }
303 : :
304 : :
305 : 0 : std::map<Txid, uint32_t> MiniMiner::Linearize()
306 : : {
307 : 0 : BuildMockTemplate(std::nullopt);
308 : 0 : return m_inclusion_order;
309 : : }
310 : :
311 : 2066 : std::map<COutPoint, CAmount> MiniMiner::CalculateBumpFees(const CFeeRate& target_feerate)
312 : : {
313 [ - + ]: 2066 : if (!m_ready_to_calculate) return {};
314 : : // Build a block template until the target feerate is hit.
315 : 2066 : BuildMockTemplate(target_feerate);
316 : :
317 : : // Each transaction that "made it into the block" has a bumpfee of 0, i.e. they are part of an
318 : : // ancestor package with at least the target feerate and don't need to be bumped.
319 [ + + ]: 31140 : for (const auto& txid : m_in_block) {
320 : : // Not all of the block transactions were necessarily requested.
321 : 29074 : auto it = m_requested_outpoints_by_txid.find(txid);
322 [ + + ]: 29074 : if (it != m_requested_outpoints_by_txid.end()) {
323 [ + + ]: 30104 : for (const auto& outpoint : it->second) {
324 : 15128 : m_bump_fees.emplace(outpoint, 0);
325 : : }
326 : 14976 : m_requested_outpoints_by_txid.erase(it);
327 : : }
328 : : }
329 : :
330 : : // A transactions and its ancestors will only be picked into a block when
331 : : // both the ancestor set feerate and the individual feerate meet the target
332 : : // feerate.
333 : : //
334 : : // We had to convince ourselves that after running the mini miner and
335 : : // picking all eligible transactions into our MockBlockTemplate, there
336 : : // could still be transactions remaining that have a lower individual
337 : : // feerate than their ancestor feerate. So here is an example:
338 : : //
339 : : // ┌─────────────────┐
340 : : // │ │
341 : : // │ Grandparent │
342 : : // │ 1700 vB │
343 : : // │ 1700 sats │ Target feerate: 10 s/vB
344 : : // │ 1 s/vB │ GP Ancestor Set Feerate (ASFR): 1 s/vB
345 : : // │ │ P1_ASFR: 9.84 s/vB
346 : : // └──────▲───▲──────┘ P2_ASFR: 2.47 s/vB
347 : : // │ │ C_ASFR: 10.27 s/vB
348 : : // ┌───────────────┐ │ │ ┌──────────────┐
349 : : // │ ├────┘ └────┤ │ ⇒ C_FR < TFR < C_ASFR
350 : : // │ Parent 1 │ │ Parent 2 │
351 : : // │ 200 vB │ │ 200 vB │
352 : : // │ 17000 sats │ │ 3000 sats │
353 : : // │ 85 s/vB │ │ 15 s/vB │
354 : : // │ │ │ │
355 : : // └───────────▲───┘ └───▲──────────┘
356 : : // │ │
357 : : // │ ┌───────────┐ │
358 : : // └────┤ ├────┘
359 : : // │ Child │
360 : : // │ 100 vB │
361 : : // │ 900 sats │
362 : : // │ 9 s/vB │
363 : : // │ │
364 : : // └───────────┘
365 : : //
366 : : // We therefore calculate both the bump fee that is necessary to elevate
367 : : // the individual transaction to the target feerate:
368 : : // target_feerate × tx_size - tx_fees
369 : : // and the bump fee that is necessary to bump the entire ancestor set to
370 : : // the target feerate:
371 : : // target_feerate × ancestor_set_size - ancestor_set_fees
372 : : // By picking the maximum from the two, we ensure that a transaction meets
373 : : // both criteria.
374 [ + + ]: 23714 : for (const auto& [txid, outpoints] : m_requested_outpoints_by_txid) {
375 : 21648 : auto it = m_entries_by_txid.find(txid);
376 [ - + ]: 21648 : Assume(it != m_entries_by_txid.end());
377 [ + - ]: 21648 : if (it != m_entries_by_txid.end()) {
378 [ + - - + ]: 43296 : Assume(target_feerate.GetFee(it->second.GetSizeWithAncestors()) > std::min(it->second.GetModifiedFee(), it->second.GetModFeesWithAncestors()));
379 : 21648 : CAmount bump_fee_with_ancestors = target_feerate.GetFee(it->second.GetSizeWithAncestors()) - it->second.GetModFeesWithAncestors();
380 [ + + ]: 21648 : CAmount bump_fee_individual = target_feerate.GetFee(it->second.GetTxSize()) - it->second.GetModifiedFee();
381 [ + + ]: 21648 : const CAmount bump_fee{std::max(bump_fee_with_ancestors, bump_fee_individual)};
382 [ - + ]: 21648 : Assume(bump_fee >= 0);
383 [ + + ]: 43610 : for (const auto& outpoint : outpoints) {
384 : 21962 : m_bump_fees.emplace(outpoint, bump_fee);
385 : : }
386 : : }
387 : : }
388 : 2066 : return m_bump_fees;
389 : : }
390 : :
391 : 1211 : std::optional<CAmount> MiniMiner::CalculateTotalBumpFees(const CFeeRate& target_feerate)
392 : : {
393 [ - + ]: 1211 : if (!m_ready_to_calculate) return std::nullopt;
394 : : // Build a block template until the target feerate is hit.
395 : 1211 : BuildMockTemplate(target_feerate);
396 : :
397 : : // All remaining ancestors that are not part of m_in_block must be bumped, but no other relatives
398 : 1211 : std::set<MockEntryMap::iterator, IteratorComparator> ancestors;
399 : 1211 : std::set<MockEntryMap::iterator, IteratorComparator> to_process;
400 [ + + ]: 37835 : for (const auto& [txid, outpoints] : m_requested_outpoints_by_txid) {
401 : : // Skip any ancestors that already have a miner score higher than the target feerate
402 : : // (already "made it" into the block)
403 [ + + ]: 36624 : if (m_in_block.count(txid)) continue;
404 : 21648 : auto iter = m_entries_by_txid.find(txid);
405 [ - + ]: 21648 : if (iter == m_entries_by_txid.end()) continue;
406 [ + - ]: 21648 : to_process.insert(iter);
407 [ + - ]: 21648 : ancestors.insert(iter);
408 : : }
409 : :
410 : 1211 : std::set<Txid> has_been_processed;
411 [ + + ]: 23856 : while (!to_process.empty()) {
412 : 22645 : auto iter = to_process.begin();
413 : 22645 : const CTransaction& tx = (*iter)->second.GetTx();
414 [ + + ]: 225093 : for (const auto& input : tx.vin) {
415 [ + + ]: 202448 : if (auto parent_it{m_entries_by_txid.find(input.prevout.hash)}; parent_it != m_entries_by_txid.end()) {
416 [ + + ]: 154308 : if (!has_been_processed.count(input.prevout.hash)) {
417 [ + - ]: 77091 : to_process.insert(parent_it);
418 : : }
419 [ + - ]: 154308 : ancestors.insert(parent_it);
420 : : }
421 : : }
422 [ + - ]: 22645 : has_been_processed.insert(tx.GetHash());
423 : 22645 : to_process.erase(iter);
424 : : }
425 : 1211 : const auto ancestor_package_size = std::accumulate(ancestors.cbegin(), ancestors.cend(), int64_t{0},
426 : 22645 : [](int64_t sum, const auto it) {return sum + it->second.GetTxSize();});
427 : 1211 : const auto ancestor_package_fee = std::accumulate(ancestors.cbegin(), ancestors.cend(), CAmount{0},
428 : 22645 : [](CAmount sum, const auto it) {return sum + it->second.GetModifiedFee();});
429 [ + - ]: 1211 : return target_feerate.GetFee(ancestor_package_size) - ancestor_package_fee;
430 : 1211 : }
431 : : } // namespace node
|
