Branch data Line data Source code
1 : : // Copyright (c) 2009-2010 Satoshi Nakamoto
2 : : // Copyright (c) 2009-2022 The Bitcoin Core developers
3 : : // Distributed under the MIT software license, see the accompanying
4 : : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
5 : :
6 : : #include <txmempool.h>
7 : :
8 : : #include <chain.h>
9 : : #include <coins.h>
10 : : #include <common/system.h>
11 : : #include <consensus/consensus.h>
12 : : #include <consensus/tx_verify.h>
13 : : #include <consensus/validation.h>
14 : : #include <logging.h>
15 : : #include <policy/policy.h>
16 : : #include <policy/settings.h>
17 : : #include <random.h>
18 : : #include <tinyformat.h>
19 : : #include <util/check.h>
20 : : #include <util/feefrac.h>
21 : : #include <util/moneystr.h>
22 : : #include <util/overflow.h>
23 : : #include <util/result.h>
24 : : #include <util/time.h>
25 : : #include <util/trace.h>
26 : : #include <util/translation.h>
27 : : #include <validationinterface.h>
28 : :
29 : : #include <algorithm>
30 : : #include <cmath>
31 : : #include <numeric>
32 : : #include <optional>
33 : : #include <ranges>
34 : : #include <string_view>
35 : : #include <utility>
36 : :
37 : : TRACEPOINT_SEMAPHORE(mempool, added);
38 : : TRACEPOINT_SEMAPHORE(mempool, removed);
39 : :
40 : 0 : bool TestLockPointValidity(CChain& active_chain, const LockPoints& lp)
41 : : {
42 : 0 : AssertLockHeld(cs_main);
43 : : // If there are relative lock times then the maxInputBlock will be set
44 : : // If there are no relative lock times, the LockPoints don't depend on the chain
45 [ # # ]: 0 : if (lp.maxInputBlock) {
46 : : // Check whether active_chain is an extension of the block at which the LockPoints
47 : : // calculation was valid. If not LockPoints are no longer valid
48 [ # # ]: 0 : if (!active_chain.Contains(lp.maxInputBlock)) {
49 : 0 : return false;
50 : : }
51 : : }
52 : :
53 : : // LockPoints still valid
54 : : return true;
55 : : }
56 : :
57 : 104007 : std::vector<CTxMemPoolEntry::CTxMemPoolEntryRef> CTxMemPool::GetChildren(const CTxMemPoolEntry& entry) const
58 : : {
59 : 104007 : LOCK(cs);
60 : 104007 : std::vector<CTxMemPoolEntry::CTxMemPoolEntryRef> ret;
61 : 104007 : WITH_FRESH_EPOCH(m_epoch);
62 : 104007 : auto iter = mapNextTx.lower_bound(COutPoint(entry.GetTx().GetHash(), 0));
63 [ + + + + ]: 257937 : for (; iter != mapNextTx.end() && iter->first->hash == entry.GetTx().GetHash(); ++iter) {
64 [ + + ]: 153930 : if (!visited(iter->second)) {
65 [ + - ]: 63415 : ret.emplace_back(*(iter->second));
66 : : }
67 : : }
68 : 208014 : return ret;
69 [ + - ]: 208014 : }
70 : :
71 : 349744 : std::vector<CTxMemPoolEntry::CTxMemPoolEntryRef> CTxMemPool::GetParents(const CTxMemPoolEntry& entry) const
72 : : {
73 : 349744 : LOCK(cs);
74 : 349744 : std::vector<CTxMemPoolEntry::CTxMemPoolEntryRef> ret;
75 : 349744 : std::set<Txid> inputs;
76 [ + + ]: 1261717 : for (const auto& txin : entry.GetTx().vin) {
77 [ + - ]: 911973 : inputs.insert(txin.prevout.hash);
78 : : }
79 [ + + ]: 1154567 : for (const auto& hash : inputs) {
80 [ + - ]: 804823 : std::optional<txiter> piter = GetIter(hash);
81 [ + + ]: 804823 : if (piter) {
82 [ + - ]: 234514 : ret.emplace_back(**piter);
83 : : }
84 : : }
85 : 349744 : return ret;
86 [ + - ]: 699488 : }
87 : :
88 : 6288 : void CTxMemPool::UpdateTransactionsFromBlock(const std::vector<Txid>& vHashesToUpdate)
89 : : {
90 : 6288 : AssertLockHeld(cs);
91 : :
92 : : // Iterate in reverse, so that whenever we are looking at a transaction
93 : : // we are sure that all in-mempool descendants have already been processed.
94 [ + + ]: 8108 : for (const Txid& hash : vHashesToUpdate | std::views::reverse) {
95 : : // calculate children from mapNextTx
96 : 1820 : txiter it = mapTx.find(hash);
97 [ - + ]: 1820 : if (it == mapTx.end()) {
98 : 0 : continue;
99 : : }
100 : 1820 : auto iter = mapNextTx.lower_bound(COutPoint(hash, 0));
101 : 1820 : {
102 [ + + + + ]: 2036 : for (; iter != mapNextTx.end() && iter->first->hash == hash; ++iter) {
103 [ - + ]: 216 : txiter childIter = iter->second;
104 [ - + ]: 216 : assert(childIter != mapTx.end());
105 : : // Add dependencies that are discovered between transactions in the
106 : : // block and transactions that were in the mempool to txgraph.
107 : 216 : m_txgraph->AddDependency(/*parent=*/*it, /*child=*/*childIter);
108 : : }
109 : : }
110 : : }
111 : :
112 : 6288 : auto txs_to_remove = m_txgraph->Trim(); // Enforce cluster size limits.
113 [ - + ]: 6288 : for (auto txptr : txs_to_remove) {
114 : 0 : const CTxMemPoolEntry& entry = *(static_cast<const CTxMemPoolEntry*>(txptr));
115 [ # # ]: 0 : removeUnchecked(mapTx.iterator_to(entry), MemPoolRemovalReason::SIZELIMIT);
116 : : }
117 : 6288 : }
118 : :
119 : 0 : bool CTxMemPool::HasDescendants(const Txid& txid) const
120 : : {
121 : 0 : LOCK(cs);
122 [ # # ]: 0 : auto entry = GetEntry(txid);
123 [ # # ]: 0 : if (!entry) return false;
124 [ # # ]: 0 : return m_txgraph->GetDescendants(*entry, TxGraph::Level::MAIN).size() > 1;
125 : 0 : }
126 : :
127 : 12008 : CTxMemPool::setEntries CTxMemPool::CalculateMemPoolAncestors(const CTxMemPoolEntry &entry) const
128 : : {
129 : 12008 : auto ancestors = m_txgraph->GetAncestors(entry, TxGraph::Level::MAIN);
130 [ - + ]: 12008 : setEntries ret;
131 [ - + + + ]: 12008 : if (ancestors.size() > 0) {
132 [ + + ]: 254 : for (auto ancestor : ancestors) {
133 [ + + ]: 133 : if (ancestor != &entry) {
134 [ + - ]: 12 : ret.insert(mapTx.iterator_to(static_cast<const CTxMemPoolEntry&>(*ancestor)));
135 : : }
136 : : }
137 : : return ret;
138 : : }
139 : :
140 : : // If we didn't get anything back, the transaction is not in the graph.
141 : : // Find each parent and call GetAncestors on each.
142 : 11887 : setEntries staged_parents;
143 : 11887 : const CTransaction &tx = entry.GetTx();
144 : :
145 : : // Get parents of this transaction that are in the mempool
146 [ - + + + ]: 43209 : for (unsigned int i = 0; i < tx.vin.size(); i++) {
147 [ + - ]: 31322 : std::optional<txiter> piter = GetIter(tx.vin[i].prevout.hash);
148 [ + + ]: 31322 : if (piter) {
149 [ + - ]: 12191 : staged_parents.insert(*piter);
150 : : }
151 : : }
152 : :
153 [ + + ]: 22635 : for (const auto& parent : staged_parents) {
154 : 10748 : auto parent_ancestors = m_txgraph->GetAncestors(*parent, TxGraph::Level::MAIN);
155 [ + + ]: 29015 : for (auto ancestor : parent_ancestors) {
156 [ + - ]: 18267 : ret.insert(mapTx.iterator_to(static_cast<const CTxMemPoolEntry&>(*ancestor)));
157 : : }
158 : 10748 : }
159 : :
160 : 11887 : return ret;
161 : 23895 : }
162 : :
163 : 16274 : static CTxMemPool::Options&& Flatten(CTxMemPool::Options&& opts, bilingual_str& error)
164 : : {
165 [ + - ]: 16274 : opts.check_ratio = std::clamp<int>(opts.check_ratio, 0, 1'000'000);
166 : 16274 : int64_t cluster_limit_bytes = opts.limits.cluster_size_vbytes * 40;
167 [ + - + + : 16274 : if (opts.max_size_bytes < 0 || (opts.max_size_bytes > 0 && opts.max_size_bytes < cluster_limit_bytes)) {
+ + ]
168 : 358 : error = strprintf(_("-maxmempool must be at least %d MB"), std::ceil(cluster_limit_bytes / 1'000'000.0));
169 : : }
170 : 16274 : return std::move(opts);
171 : : }
172 : :
173 : 16274 : CTxMemPool::CTxMemPool(Options opts, bilingual_str& error)
174 [ + - + - ]: 16274 : : m_opts{Flatten(std::move(opts), error)}
175 : : {
176 : 16274 : m_txgraph = MakeTxGraph(m_opts.limits.cluster_count, m_opts.limits.cluster_size_vbytes * WITNESS_SCALE_FACTOR, ACCEPTABLE_ITERS);
177 : 16274 : }
178 : :
179 : 6 : bool CTxMemPool::isSpent(const COutPoint& outpoint) const
180 : : {
181 : 6 : LOCK(cs);
182 [ + - ]: 6 : return mapNextTx.count(outpoint);
183 : 6 : }
184 : :
185 : 0 : unsigned int CTxMemPool::GetTransactionsUpdated() const
186 : : {
187 : 0 : return nTransactionsUpdated;
188 : : }
189 : :
190 : 103262 : void CTxMemPool::AddTransactionsUpdated(unsigned int n)
191 : : {
192 : 103262 : nTransactionsUpdated += n;
193 : 103262 : }
194 : :
195 : 227654 : void CTxMemPool::Apply(ChangeSet* changeset)
196 : : {
197 : 227654 : AssertLockHeld(cs);
198 : 227654 : m_txgraph->CommitStaging();
199 : :
200 : 227654 : RemoveStaged(changeset->m_to_remove, MemPoolRemovalReason::REPLACED);
201 : :
202 [ - + + + ]: 455724 : for (size_t i=0; i<changeset->m_entry_vec.size(); ++i) {
203 : 228070 : auto tx_entry = changeset->m_entry_vec[i];
204 : : // First splice this entry into mapTx.
205 : 228070 : auto node_handle = changeset->m_to_add.extract(tx_entry);
206 [ + - ]: 228070 : auto result = mapTx.insert(std::move(node_handle));
207 : :
208 [ - + ]: 228070 : Assume(result.inserted);
209 : 228070 : txiter it = result.position;
210 : :
211 [ + - ]: 228070 : addNewTransaction(it);
212 [ - + ]: 228070 : }
213 : 227654 : m_txgraph->DoWork(POST_CHANGE_WORK);
214 : 227654 : }
215 : :
216 : 228070 : void CTxMemPool::addNewTransaction(CTxMemPool::txiter newit)
217 : : {
218 : 228070 : const CTxMemPoolEntry& entry = *newit;
219 : :
220 : : // Update cachedInnerUsage to include contained transaction's usage.
221 : : // (When we update the entry for in-mempool parents, memory usage will be
222 : : // further updated.)
223 : 228070 : cachedInnerUsage += entry.DynamicMemoryUsage();
224 : :
225 : 228070 : const CTransaction& tx = newit->GetTx();
226 [ - + + + ]: 891110 : for (unsigned int i = 0; i < tx.vin.size(); i++) {
227 : 663040 : mapNextTx.insert(std::make_pair(&tx.vin[i].prevout, newit));
228 : : }
229 : : // Don't bother worrying about child transactions of this one.
230 : : // Normal case of a new transaction arriving is that there can't be any
231 : : // children, because such children would be orphans.
232 : : // An exception to that is if a transaction enters that used to be in a block.
233 : : // In that case, our disconnect block logic will call UpdateTransactionsFromBlock
234 : : // to clean up the mess we're leaving here.
235 : :
236 : 228070 : nTransactionsUpdated++;
237 : 228070 : totalTxSize += entry.GetTxSize();
238 : 228070 : m_total_fee += entry.GetFee();
239 : :
240 : 228070 : txns_randomized.emplace_back(tx.GetWitnessHash(), newit);
241 [ - + ]: 228070 : newit->idx_randomized = txns_randomized.size() - 1;
242 : :
243 : : TRACEPOINT(mempool, added,
244 : : entry.GetTx().GetHash().data(),
245 : : entry.GetTxSize(),
246 : : entry.GetFee()
247 : 228070 : );
248 : 228070 : }
249 : :
250 : 24932 : void CTxMemPool::removeUnchecked(txiter it, MemPoolRemovalReason reason)
251 : : {
252 : : // We increment mempool sequence value no matter removal reason
253 : : // even if not directly reported below.
254 [ + + ]: 24932 : uint64_t mempool_sequence = GetAndIncrementSequence();
255 : :
256 [ + + + + ]: 24932 : if (reason != MemPoolRemovalReason::BLOCK && m_opts.signals) {
257 : : // Notify clients that a transaction has been removed from the mempool
258 : : // for any reason except being included in a block. Clients interested
259 : : // in transactions included in blocks can subscribe to the BlockConnected
260 : : // notification.
261 [ + - + - ]: 67332 : m_opts.signals->TransactionRemovedFromMempool(it->GetSharedTx(), reason, mempool_sequence);
262 : : }
263 : : TRACEPOINT(mempool, removed,
264 : : it->GetTx().GetHash().data(),
265 : : RemovalReasonToString(reason).c_str(),
266 : : it->GetTxSize(),
267 : : it->GetFee(),
268 : : std::chrono::duration_cast<std::chrono::duration<std::uint64_t>>(it->GetTime()).count()
269 : 24932 : );
270 : :
271 [ + + ]: 73890 : for (const CTxIn& txin : it->GetTx().vin)
272 : 48958 : mapNextTx.erase(txin.prevout);
273 : :
274 : 24932 : RemoveUnbroadcastTx(it->GetTx().GetHash(), true /* add logging because unchecked */);
275 : :
276 [ - + + + ]: 24932 : if (txns_randomized.size() > 1) {
277 : : // Remove entry from txns_randomized by replacing it with the back and deleting the back.
278 [ - + ]: 21703 : txns_randomized[it->idx_randomized] = std::move(txns_randomized.back());
279 [ - + ]: 21703 : txns_randomized[it->idx_randomized].second->idx_randomized = it->idx_randomized;
280 [ - + ]: 21703 : txns_randomized.pop_back();
281 [ - + - + : 21703 : if (txns_randomized.size() * 2 < txns_randomized.capacity()) {
+ + ]
282 : 2207 : txns_randomized.shrink_to_fit();
283 : : }
284 : : } else {
285 [ + - ]: 3229 : txns_randomized.clear();
286 : : }
287 : :
288 : 24932 : totalTxSize -= it->GetTxSize();
289 : 24932 : m_total_fee -= it->GetFee();
290 : 24932 : cachedInnerUsage -= it->DynamicMemoryUsage();
291 : 24932 : mapTx.erase(it);
292 : 24932 : nTransactionsUpdated++;
293 : 24932 : }
294 : :
295 : : // Calculates descendants of given entry and adds to setDescendants.
296 : 361454 : void CTxMemPool::CalculateDescendants(txiter entryit, setEntries& setDescendants) const
297 : : {
298 : 361454 : (void)CalculateDescendants(*entryit, setDescendants);
299 : 361454 : return;
300 : : }
301 : :
302 : 362274 : CTxMemPool::txiter CTxMemPool::CalculateDescendants(const CTxMemPoolEntry& entry, setEntries& setDescendants) const
303 : : {
304 [ + + ]: 2042343 : for (auto tx : m_txgraph->GetDescendants(entry, TxGraph::Level::MAIN)) {
305 [ + - ]: 1680069 : setDescendants.insert(mapTx.iterator_to(static_cast<const CTxMemPoolEntry&>(*tx)));
306 : : }
307 : 362274 : return mapTx.iterator_to(entry);
308 : : }
309 : :
310 : 624 : void CTxMemPool::removeRecursive(CTxMemPool::txiter to_remove, MemPoolRemovalReason reason)
311 : : {
312 : 624 : AssertLockHeld(cs);
313 [ - + ]: 624 : Assume(!m_have_changeset);
314 : 624 : auto descendants = m_txgraph->GetDescendants(*to_remove, TxGraph::Level::MAIN);
315 [ + + ]: 1280 : for (auto tx: descendants) {
316 [ + - ]: 656 : removeUnchecked(mapTx.iterator_to(static_cast<const CTxMemPoolEntry&>(*tx)), reason);
317 : : }
318 : 624 : }
319 : :
320 : 6912 : void CTxMemPool::removeRecursive(const CTransaction &origTx, MemPoolRemovalReason reason)
321 : : {
322 : : // Remove transaction from memory pool
323 : 6912 : AssertLockHeld(cs);
324 [ - + ]: 6912 : Assume(!m_have_changeset);
325 : 6912 : txiter origit = mapTx.find(origTx.GetHash());
326 [ + + ]: 6912 : if (origit != mapTx.end()) {
327 : 624 : removeRecursive(origit, reason);
328 : : } else {
329 : : // When recursively removing but origTx isn't in the mempool
330 : : // be sure to remove any descendants that are in the pool. This can
331 : : // happen during chain re-orgs if origTx isn't re-accepted into
332 : : // the mempool for any reason.
333 : 6288 : auto iter = mapNextTx.lower_bound(COutPoint(origTx.GetHash(), 0));
334 : 6288 : std::vector<const TxGraph::Ref*> to_remove;
335 [ + + - + ]: 6288 : while (iter != mapNextTx.end() && iter->first->hash == origTx.GetHash()) {
336 [ # # ]: 0 : to_remove.emplace_back(&*(iter->second));
337 : 0 : ++iter;
338 : : }
339 [ - + ]: 6288 : auto all_removes = m_txgraph->GetDescendantsUnion(to_remove, TxGraph::Level::MAIN);
340 [ - + ]: 6288 : for (auto ref : all_removes) {
341 : 0 : auto tx = mapTx.iterator_to(static_cast<const CTxMemPoolEntry&>(*ref));
342 [ # # ]: 0 : removeUnchecked(tx, reason);
343 : : }
344 : 6288 : }
345 : 6912 : }
346 : :
347 : 0 : void CTxMemPool::removeForReorg(CChain& chain, std::function<bool(txiter)> check_final_and_mature)
348 : : {
349 : : // Remove transactions spending a coinbase which are now immature and no-longer-final transactions
350 : 0 : AssertLockHeld(cs);
351 : 0 : AssertLockHeld(::cs_main);
352 [ # # ]: 0 : Assume(!m_have_changeset);
353 : :
354 : 0 : std::vector<const TxGraph::Ref*> to_remove;
355 [ # # ]: 0 : for (txiter it = mapTx.begin(); it != mapTx.end(); it++) {
356 [ # # # # ]: 0 : if (check_final_and_mature(it)) {
357 [ # # ]: 0 : to_remove.emplace_back(&*it);
358 : : }
359 : : }
360 : :
361 [ # # ]: 0 : auto all_to_remove = m_txgraph->GetDescendantsUnion(to_remove, TxGraph::Level::MAIN);
362 : :
363 [ # # ]: 0 : for (auto ref : all_to_remove) {
364 : 0 : auto it = mapTx.iterator_to(static_cast<const CTxMemPoolEntry&>(*ref));
365 [ # # ]: 0 : removeUnchecked(it, MemPoolRemovalReason::REORG);
366 : : }
367 [ # # ]: 0 : for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
368 [ # # # # ]: 0 : assert(TestLockPointValidity(chain, it->GetLockPoints()));
369 : : }
370 : 0 : m_txgraph->DoWork(POST_CHANGE_WORK);
371 : 0 : }
372 : :
373 : 3454 : void CTxMemPool::removeConflicts(const CTransaction &tx)
374 : : {
375 : : // Remove transactions which depend on inputs of tx, recursively
376 : 3454 : AssertLockHeld(cs);
377 [ + + ]: 9410 : for (const CTxIn &txin : tx.vin) {
378 : 5956 : auto it = mapNextTx.find(txin.prevout);
379 [ - + ]: 5956 : if (it != mapNextTx.end()) {
380 [ # # ]: 0 : const CTransaction &txConflict = it->second->GetTx();
381 [ # # ]: 0 : if (Assume(txConflict.GetHash() != tx.GetHash()))
382 : : {
383 : 0 : ClearPrioritisation(txConflict.GetHash());
384 : 0 : removeRecursive(it->second, MemPoolRemovalReason::CONFLICT);
385 : : }
386 : : }
387 : : }
388 : 3454 : }
389 : :
390 : 109550 : void CTxMemPool::removeForBlock(const std::vector<CTransactionRef>& vtx, unsigned int nBlockHeight)
391 : : {
392 : : // Remove confirmed txs and conflicts when a new block is connected, updating the fee logic
393 : 109550 : AssertLockHeld(cs);
394 [ - + ]: 109550 : Assume(!m_have_changeset);
395 : 109550 : std::vector<RemovedMempoolTransactionInfo> txs_removed_for_block;
396 [ + + + - : 109550 : if (mapTx.size() || mapNextTx.size() || mapDeltas.size()) {
+ + ]
397 [ - + + - ]: 1634 : txs_removed_for_block.reserve(vtx.size());
398 [ + + ]: 5088 : for (const auto& tx : vtx) {
399 [ + - ]: 3454 : txiter it = mapTx.find(tx->GetHash());
400 [ + + ]: 3454 : if (it != mapTx.end()) {
401 [ + - ]: 1820 : txs_removed_for_block.emplace_back(*it);
402 [ + - ]: 1820 : removeUnchecked(it, MemPoolRemovalReason::BLOCK);
403 : : }
404 [ + - ]: 3454 : removeConflicts(*tx);
405 [ + - ]: 3454 : ClearPrioritisation(tx->GetHash());
406 : : }
407 : : }
408 [ + + ]: 109550 : if (m_opts.signals) {
409 [ + - ]: 109067 : m_opts.signals->MempoolTransactionsRemovedForBlock(txs_removed_for_block, nBlockHeight);
410 : : }
411 [ + - ]: 109550 : lastRollingFeeUpdate = GetTime();
412 : 109550 : blockSinceLastRollingFeeBump = true;
413 : 109550 : m_txgraph->DoWork(POST_CHANGE_WORK);
414 : 109550 : }
415 : :
416 : 131457 : void CTxMemPool::check(const CCoinsViewCache& active_coins_tip, int64_t spendheight) const
417 : : {
418 [ + - ]: 131457 : if (m_opts.check_ratio == 0) return;
419 : :
420 [ + - ]: 131457 : if (FastRandomContext().randrange(m_opts.check_ratio) >= 1) return;
421 : :
422 : 131457 : AssertLockHeld(::cs_main);
423 : 131457 : LOCK(cs);
424 [ + - + + : 131457 : LogDebug(BCLog::MEMPOOL, "Checking mempool with %u transactions and %u inputs\n", (unsigned int)mapTx.size(), (unsigned int)mapNextTx.size());
+ - ]
425 : :
426 : 131457 : uint64_t checkTotal = 0;
427 : 131457 : CAmount check_total_fee{0};
428 : 131457 : CAmount check_total_modified_fee{0};
429 : 131457 : int64_t check_total_adjusted_weight{0};
430 : 131457 : uint64_t innerUsage = 0;
431 : :
432 [ - + ]: 131457 : assert(!m_txgraph->IsOversized(TxGraph::Level::MAIN));
433 [ + - ]: 131457 : m_txgraph->SanityCheck();
434 : :
435 [ + - ]: 131457 : CCoinsViewCache mempoolDuplicate(const_cast<CCoinsViewCache*>(&active_coins_tip));
436 : :
437 [ + - ]: 131457 : const auto score_with_topo{GetSortedScoreWithTopology()};
438 : :
439 : : // Number of chunks is bounded by number of transactions.
440 [ + - ]: 131457 : const auto diagram{GetFeerateDiagram()};
441 [ - + - + : 131457 : assert(diagram.size() <= score_with_topo.size() + 1);
- + ]
442 [ - + ]: 131457 : assert(diagram.size() >= 1);
443 : :
444 : 131457 : std::optional<Wtxid> last_wtxid = std::nullopt;
445 : 131457 : auto diagram_iter = diagram.cbegin();
446 : :
447 [ + + ]: 179671 : for (const auto& it : score_with_topo) {
448 : : // GetSortedScoreWithTopology() contains the same chunks as the feerate
449 : : // diagram. We do not know where the chunk boundaries are, but we can
450 : : // check that there are points at which they match the cumulative fee
451 : : // and weight.
452 : : // The feerate diagram should never get behind the current transaction
453 : : // size totals.
454 [ - + ]: 48214 : assert(diagram_iter->size >= check_total_adjusted_weight);
455 [ + + ]: 48214 : if (diagram_iter->fee == check_total_modified_fee &&
456 [ + + ]: 38085 : diagram_iter->size == check_total_adjusted_weight) {
457 : 38068 : ++diagram_iter;
458 : : }
459 [ + - ]: 48214 : checkTotal += it->GetTxSize();
460 [ + - ]: 48214 : check_total_adjusted_weight += it->GetAdjustedWeight();
461 [ + + ]: 48214 : check_total_fee += it->GetFee();
462 [ + + ]: 48214 : check_total_modified_fee += it->GetModifiedFee();
463 [ + + ]: 48214 : innerUsage += it->DynamicMemoryUsage();
464 [ + + ]: 48214 : const CTransaction& tx = it->GetTx();
465 : :
466 : : // CompareMiningScoreWithTopology should agree with GetSortedScoreWithTopology()
467 [ + + ]: 48214 : if (last_wtxid) {
468 [ + - - + ]: 45618 : assert(CompareMiningScoreWithTopology(*last_wtxid, tx.GetWitnessHash()));
469 : : }
470 [ + + ]: 48214 : last_wtxid = tx.GetWitnessHash();
471 : :
472 : 48214 : std::set<CTxMemPoolEntry::CTxMemPoolEntryRef, CompareIteratorByHash> setParentCheck;
473 : 48214 : std::set<CTxMemPoolEntry::CTxMemPoolEntryRef, CompareIteratorByHash> setParentsStored;
474 [ + + ]: 132474 : for (const CTxIn &txin : tx.vin) {
475 : : // Check that every mempool transaction's inputs refer to available coins, or other mempool tx's.
476 [ + - ]: 84260 : indexed_transaction_set::const_iterator it2 = mapTx.find(txin.prevout.hash);
477 [ + + ]: 84260 : if (it2 != mapTx.end()) {
478 [ - + ]: 29887 : const CTransaction& tx2 = it2->GetTx();
479 [ - + + - : 29887 : assert(tx2.vout.size() > txin.prevout.n && !tx2.vout[txin.prevout.n].IsNull());
- + ]
480 [ + - ]: 29887 : setParentCheck.insert(*it2);
481 : : }
482 : : // We are iterating through the mempool entries sorted
483 : : // topologically and by mining score. All parents must have been
484 : : // checked before their children and their coins added to the
485 : : // mempoolDuplicate coins cache.
486 [ + - - + ]: 84260 : assert(mempoolDuplicate.HaveCoin(txin.prevout));
487 : : // Check whether its inputs are marked in mapNextTx.
488 : 84260 : auto it3 = mapNextTx.find(txin.prevout);
489 [ - + ]: 84260 : assert(it3 != mapNextTx.end());
490 [ - + ]: 84260 : assert(it3->first == &txin.prevout);
491 [ - + ]: 84260 : assert(&it3->second->GetTx() == &tx);
492 : : }
493 : 97508 : auto comp = [](const CTxMemPoolEntry& a, const CTxMemPoolEntry& b) -> bool {
494 [ + - ]: 49294 : return a.GetTx().GetHash() == b.GetTx().GetHash();
495 : : };
496 [ + - + + ]: 72861 : for (auto &txentry : GetParents(*it)) {
497 [ + - ]: 24647 : setParentsStored.insert(dynamic_cast<const CTxMemPoolEntry&>(txentry.get()));
498 : 0 : }
499 [ - + ]: 48214 : assert(setParentCheck.size() == setParentsStored.size());
500 [ - + ]: 48214 : assert(std::equal(setParentCheck.begin(), setParentCheck.end(), setParentsStored.begin(), comp));
501 : :
502 : : // Check children against mapNextTx
503 : 48214 : std::set<CTxMemPoolEntry::CTxMemPoolEntryRef, CompareIteratorByHash> setChildrenCheck;
504 : 48214 : std::set<CTxMemPoolEntry::CTxMemPoolEntryRef, CompareIteratorByHash> setChildrenStored;
505 : 48214 : auto iter = mapNextTx.lower_bound(COutPoint(it->GetTx().GetHash(), 0));
506 [ + + + + ]: 78101 : for (; iter != mapNextTx.end() && iter->first->hash == it->GetTx().GetHash(); ++iter) {
507 [ - + ]: 29887 : txiter childit = iter->second;
508 [ - + ]: 29887 : assert(childit != mapTx.end()); // mapNextTx points to in-mempool transactions
509 [ + - ]: 29887 : setChildrenCheck.insert(*childit);
510 : : }
511 [ + - + + ]: 72861 : for (auto &txentry : GetChildren(*it)) {
512 [ + - ]: 24647 : setChildrenStored.insert(dynamic_cast<const CTxMemPoolEntry&>(txentry.get()));
513 : 0 : }
514 [ - + ]: 48214 : assert(setChildrenCheck.size() == setChildrenStored.size());
515 [ - + ]: 48214 : assert(std::equal(setChildrenCheck.begin(), setChildrenCheck.end(), setChildrenStored.begin(), comp));
516 : :
517 [ - + ]: 48214 : TxValidationState dummy_state; // Not used. CheckTxInputs() should always pass
518 : 48214 : CAmount txfee = 0;
519 [ - + ]: 48214 : assert(!tx.IsCoinBase());
520 [ + - - + ]: 48214 : assert(Consensus::CheckTxInputs(tx, dummy_state, mempoolDuplicate, spendheight, txfee));
521 [ + - + + ]: 132474 : for (const auto& input: tx.vin) mempoolDuplicate.SpendCoin(input.prevout);
522 [ + - ]: 48214 : AddCoins(mempoolDuplicate, tx, std::numeric_limits<int>::max());
523 : 48214 : }
524 [ + + ]: 215717 : for (auto it = mapNextTx.cbegin(); it != mapNextTx.cend(); it++) {
525 [ - + ]: 84260 : indexed_transaction_set::const_iterator it2 = it->second;
526 [ - + ]: 84260 : assert(it2 != mapTx.end());
527 : : }
528 : :
529 [ - + ]: 131457 : ++diagram_iter;
530 [ - + ]: 131457 : assert(diagram_iter == diagram.cend());
531 : :
532 [ - + ]: 131457 : assert(totalTxSize == checkTotal);
533 [ - + ]: 131457 : assert(m_total_fee == check_total_fee);
534 [ - + ]: 131457 : assert(diagram.back().fee == check_total_modified_fee);
535 [ - + ]: 131457 : assert(diagram.back().size == check_total_adjusted_weight);
536 [ - + ]: 131457 : assert(innerUsage == cachedInnerUsage);
537 [ + - ]: 262914 : }
538 : :
539 : 45618 : bool CTxMemPool::CompareMiningScoreWithTopology(const Wtxid& hasha, const Wtxid& hashb) const
540 : : {
541 : : /* Return `true` if hasha should be considered sooner than hashb, namely when:
542 : : * a is not in the mempool but b is, or
543 : : * both are in the mempool but a is sorted before b in the total mempool ordering
544 : : * (which takes dependencies and (chunk) feerates into account).
545 : : */
546 : 45618 : LOCK(cs);
547 [ + - ]: 45618 : auto j{GetIter(hashb)};
548 [ + - ]: 45618 : if (!j.has_value()) return false;
549 [ + - ]: 45618 : auto i{GetIter(hasha)};
550 [ + - ]: 45618 : if (!i.has_value()) return true;
551 : :
552 : 45618 : return m_txgraph->CompareMainOrder(*i.value(), *j.value()) < 0;
553 : 45618 : }
554 : :
555 : 604445 : std::vector<CTxMemPool::indexed_transaction_set::const_iterator> CTxMemPool::GetSortedScoreWithTopology() const
556 : : {
557 : 604445 : std::vector<indexed_transaction_set::const_iterator> iters;
558 : 604445 : AssertLockHeld(cs);
559 : :
560 [ + - ]: 604445 : iters.reserve(mapTx.size());
561 : :
562 [ + + + + ]: 18786197 : for (indexed_transaction_set::iterator mi = mapTx.begin(); mi != mapTx.end(); ++mi) {
563 [ + - ]: 9090876 : iters.push_back(mi);
564 : : }
565 : 604445 : std::sort(iters.begin(), iters.end(), [this](const auto& a, const auto& b) EXCLUSIVE_LOCKS_REQUIRED(cs) noexcept {
566 : 55405366 : return m_txgraph->CompareMainOrder(*a, *b) < 0;
567 : : });
568 : 604445 : return iters;
569 : 0 : }
570 : :
571 : 38 : std::vector<CTxMemPoolEntryRef> CTxMemPool::entryAll() const
572 : : {
573 : 38 : AssertLockHeld(cs);
574 : :
575 : 38 : std::vector<CTxMemPoolEntryRef> ret;
576 [ + - ]: 38 : ret.reserve(mapTx.size());
577 [ + - - + ]: 38 : for (const auto& it : GetSortedScoreWithTopology()) {
578 [ # # ]: 0 : ret.emplace_back(*it);
579 : : }
580 : 38 : return ret;
581 : 0 : }
582 : :
583 : 472950 : std::vector<TxMempoolInfo> CTxMemPool::infoAll() const
584 : : {
585 : 472950 : LOCK(cs);
586 [ + - ]: 472950 : auto iters = GetSortedScoreWithTopology();
587 : :
588 : 472950 : std::vector<TxMempoolInfo> ret;
589 [ + - ]: 472950 : ret.reserve(mapTx.size());
590 [ + + ]: 9515612 : for (auto it : iters) {
591 [ + - - + ]: 18085324 : ret.push_back(GetInfo(it));
592 : : }
593 : :
594 : 472950 : return ret;
595 [ + - ]: 945900 : }
596 : :
597 : 9012127 : const CTxMemPoolEntry* CTxMemPool::GetEntry(const Txid& txid) const
598 : : {
599 : 9012127 : AssertLockHeld(cs);
600 : 9012127 : const auto i = mapTx.find(txid);
601 [ + + ]: 9012127 : return i == mapTx.end() ? nullptr : &(*i);
602 : : }
603 : :
604 : 3829734 : CTransactionRef CTxMemPool::get(const Txid& hash) const
605 : : {
606 : 3829734 : LOCK(cs);
607 [ + - ]: 3829734 : indexed_transaction_set::const_iterator i = mapTx.find(hash);
608 [ + + ]: 3829734 : if (i == mapTx.end())
609 : 2862896 : return nullptr;
610 [ + - + - ]: 4796572 : return i->GetSharedTx();
611 : 3829734 : }
612 : :
613 : 724685 : void CTxMemPool::PrioritiseTransaction(const Txid& hash, const CAmount& nFeeDelta)
614 : : {
615 : 724685 : {
616 : 724685 : LOCK(cs);
617 [ + - ]: 724685 : CAmount &delta = mapDeltas[hash];
618 : 724685 : delta = SaturatingAdd(delta, nFeeDelta);
619 [ + - ]: 724685 : txiter it = mapTx.find(hash);
620 [ + + ]: 724685 : if (it != mapTx.end()) {
621 : : // PrioritiseTransaction calls stack on previous ones. Set the new
622 : : // transaction fee to be current modified fee + feedelta.
623 : 49652 : it->UpdateModifiedFee(nFeeDelta);
624 : 49652 : m_txgraph->SetTransactionFee(*it, it->GetModifiedFee());
625 : 49652 : ++nTransactionsUpdated;
626 : : }
627 [ + + ]: 724685 : if (delta == 0) {
628 : 4775 : mapDeltas.erase(hash);
629 [ + + + - : 9779 : LogPrintf("PrioritiseTransaction: %s (%sin mempool) delta cleared\n", hash.ToString(), it == mapTx.end() ? "not " : "");
+ - ]
630 : : } else {
631 [ + - + - : 1489243 : LogPrintf("PrioritiseTransaction: %s (%sin mempool) fee += %s, new delta=%s\n",
+ + + - +
- ]
632 : : hash.ToString(),
633 : : it == mapTx.end() ? "not " : "",
634 : : FormatMoney(nFeeDelta),
635 : : FormatMoney(delta));
636 : : }
637 : 724685 : }
638 : 724685 : }
639 : :
640 : 1082335 : void CTxMemPool::ApplyDelta(const Txid& hash, CAmount &nFeeDelta) const
641 : : {
642 : 1082335 : AssertLockHeld(cs);
643 : 1082335 : std::map<Txid, CAmount>::const_iterator pos = mapDeltas.find(hash);
644 [ + + ]: 1082335 : if (pos == mapDeltas.end())
645 : : return;
646 : 23830 : const CAmount &delta = pos->second;
647 : 23830 : nFeeDelta += delta;
648 : : }
649 : :
650 : 3454 : void CTxMemPool::ClearPrioritisation(const Txid& hash)
651 : : {
652 : 3454 : AssertLockHeld(cs);
653 : 3454 : mapDeltas.erase(hash);
654 : 3454 : }
655 : :
656 : 26 : std::vector<CTxMemPool::delta_info> CTxMemPool::GetPrioritisedTransactions() const
657 : : {
658 : 26 : AssertLockNotHeld(cs);
659 : 26 : LOCK(cs);
660 : 26 : std::vector<delta_info> result;
661 [ + - ]: 26 : result.reserve(mapDeltas.size());
662 [ + - + + ]: 222 : for (const auto& [txid, delta] : mapDeltas) {
663 [ + - ]: 196 : const auto iter{mapTx.find(txid)};
664 [ - + ]: 196 : const bool in_mempool{iter != mapTx.end()};
665 : 196 : std::optional<CAmount> modified_fee;
666 [ - + ]: 196 : if (in_mempool) modified_fee = iter->GetModifiedFee();
667 [ + - ]: 196 : result.emplace_back(delta_info{in_mempool, delta, modified_fee, txid});
668 : : }
669 [ + - ]: 26 : return result;
670 : 26 : }
671 : :
672 : 3658905 : const CTransaction* CTxMemPool::GetConflictTx(const COutPoint& prevout) const
673 : : {
674 : 3658905 : const auto it = mapNextTx.find(prevout);
675 [ + + ]: 3658905 : return it == mapNextTx.end() ? nullptr : &(it->second->GetTx());
676 : : }
677 : :
678 : 3626597 : std::optional<CTxMemPool::txiter> CTxMemPool::GetIter(const Txid& txid) const
679 : : {
680 : 3626597 : AssertLockHeld(cs);
681 : 3626597 : auto it = mapTx.find(txid);
682 [ + + ]: 3626597 : return it != mapTx.end() ? std::make_optional(it) : std::nullopt;
683 : : }
684 : :
685 : 102615 : std::optional<CTxMemPool::txiter> CTxMemPool::GetIter(const Wtxid& wtxid) const
686 : : {
687 : 102615 : AssertLockHeld(cs);
688 [ + + ]: 102615 : auto it{mapTx.project<0>(mapTx.get<index_by_wtxid>().find(wtxid))};
689 [ + + ]: 102615 : return it != mapTx.end() ? std::make_optional(it) : std::nullopt;
690 : : }
691 : :
692 : 275403 : CTxMemPool::setEntries CTxMemPool::GetIterSet(const std::set<Txid>& hashes) const
693 : : {
694 : 275403 : CTxMemPool::setEntries ret;
695 [ + + ]: 493797 : for (const auto& h : hashes) {
696 [ + - ]: 218394 : const auto mi = GetIter(h);
697 [ + - + - ]: 218394 : if (mi) ret.insert(*mi);
698 : : }
699 : 275403 : return ret;
700 : 0 : }
701 : :
702 : 0 : std::vector<CTxMemPool::txiter> CTxMemPool::GetIterVec(const std::vector<Txid>& txids) const
703 : : {
704 : 0 : AssertLockHeld(cs);
705 : 0 : std::vector<txiter> ret;
706 [ # # # # ]: 0 : ret.reserve(txids.size());
707 [ # # ]: 0 : for (const auto& txid : txids) {
708 [ # # ]: 0 : const auto it{GetIter(txid)};
709 [ # # ]: 0 : if (!it) return {};
710 [ # # ]: 0 : ret.push_back(*it);
711 : : }
712 : 0 : return ret;
713 : 0 : }
714 : :
715 : 69189 : bool CTxMemPool::HasNoInputsOf(const CTransaction &tx) const
716 : : {
717 [ - + + + ]: 141741 : for (unsigned int i = 0; i < tx.vin.size(); i++)
718 [ + + ]: 100267 : if (exists(tx.vin[i].prevout.hash))
719 : : return false;
720 : : return true;
721 : : }
722 : :
723 [ + - + - ]: 1073969 : CCoinsViewMemPool::CCoinsViewMemPool(CCoinsView* baseIn, const CTxMemPool& mempoolIn) : CCoinsViewBacked(baseIn), mempool(mempoolIn) { }
724 : :
725 : 3657570 : std::optional<Coin> CCoinsViewMemPool::GetCoin(const COutPoint& outpoint) const
726 : : {
727 : : // Check to see if the inputs are made available by another tx in the package.
728 : : // These Coins would not be available in the underlying CoinsView.
729 [ + + ]: 3657570 : if (auto it = m_temp_added.find(outpoint); it != m_temp_added.end()) {
730 : 92889 : return it->second;
731 : : }
732 : :
733 : : // If an entry in the mempool exists, always return that one, as it's guaranteed to never
734 : : // conflict with the underlying cache, and it cannot have pruned entries (as it contains full)
735 : : // transactions. First checking the underlying cache risks returning a pruned entry instead.
736 : 3564681 : CTransactionRef ptx = mempool.get(outpoint.hash);
737 [ + + ]: 3564681 : if (ptx) {
738 [ - + + + ]: 875836 : if (outpoint.n < ptx->vout.size()) {
739 : 875650 : Coin coin(ptx->vout[outpoint.n], MEMPOOL_HEIGHT, false);
740 [ + - ]: 875650 : m_non_base_coins.emplace(outpoint);
741 : 875650 : return coin;
742 : 875650 : }
743 : 186 : return std::nullopt;
744 : : }
745 [ + - ]: 2688845 : return base->GetCoin(outpoint);
746 : 3564681 : }
747 : :
748 : 79388 : void CCoinsViewMemPool::PackageAddTransaction(const CTransactionRef& tx)
749 : : {
750 [ - + + + ]: 331106 : for (unsigned int n = 0; n < tx->vout.size(); ++n) {
751 [ + - ]: 251718 : m_temp_added.emplace(COutPoint(tx->GetHash(), n), Coin(tx->vout[n], MEMPOOL_HEIGHT, false));
752 : 251718 : m_non_base_coins.emplace(tx->GetHash(), n);
753 : : }
754 : 79388 : }
755 : 1393133 : void CCoinsViewMemPool::Reset()
756 : : {
757 : 1393133 : m_temp_added.clear();
758 : 1393133 : m_non_base_coins.clear();
759 : 1393133 : }
760 : :
761 : 1647503 : size_t CTxMemPool::DynamicMemoryUsage() const {
762 : 1647503 : LOCK(cs);
763 : : // Estimate the overhead of mapTx to be 9 pointers (3 pointers per index) + an allocation, as no exact formula for boost::multi_index_contained is implemented.
764 [ - + + - ]: 3295006 : return memusage::MallocUsage(sizeof(CTxMemPoolEntry) + 9 * sizeof(void*)) * mapTx.size() + memusage::DynamicUsage(mapNextTx) + memusage::DynamicUsage(mapDeltas) + memusage::DynamicUsage(txns_randomized) + m_txgraph->GetMainMemoryUsage() + cachedInnerUsage;
765 : 1647503 : }
766 : :
767 : 24932 : void CTxMemPool::RemoveUnbroadcastTx(const Txid& txid, const bool unchecked) {
768 : 24932 : LOCK(cs);
769 : :
770 [ - + ]: 24932 : if (m_unbroadcast_txids.erase(txid))
771 : : {
772 [ # # # # : 0 : LogDebug(BCLog::MEMPOOL, "Removed %i from set of unbroadcast txns%s\n", txid.GetHex(), (unchecked ? " before confirmation that txn was sent out" : ""));
# # # # #
# ]
773 : : }
774 : 24932 : }
775 : :
776 : 413372 : void CTxMemPool::RemoveStaged(setEntries &stage, MemPoolRemovalReason reason) {
777 : 413372 : AssertLockHeld(cs);
778 [ + + ]: 434290 : for (txiter it : stage) {
779 : 20918 : removeUnchecked(it, reason);
780 : : }
781 : 413372 : }
782 : :
783 : 0 : bool CTxMemPool::CheckPolicyLimits(const CTransactionRef& tx)
784 : : {
785 : 0 : LOCK(cs);
786 : : // Use ChangeSet interface to check whether the cluster count
787 : : // limits would be violated. Note that the changeset will be destroyed
788 : : // when it goes out of scope.
789 [ # # ]: 0 : auto changeset = GetChangeSet();
790 [ # # ]: 0 : (void) changeset->StageAddition(tx, /*fee=*/0, /*time=*/0, /*entry_height=*/0, /*entry_sequence=*/0, /*spends_coinbase=*/false, /*sigops_cost=*/0, LockPoints{});
791 [ # # ]: 0 : return changeset->CheckMemPoolPolicyLimits();
792 [ # # ]: 0 : }
793 : :
794 : 185718 : int CTxMemPool::Expire(std::chrono::seconds time)
795 : : {
796 : 185718 : AssertLockHeld(cs);
797 [ - + ]: 185718 : Assume(!m_have_changeset);
798 : 185718 : indexed_transaction_set::index<entry_time>::type::iterator it = mapTx.get<entry_time>().begin();
799 : 185718 : setEntries toremove;
800 [ + + + + ]: 193619 : while (it != mapTx.get<entry_time>().end() && it->GetTime() < time) {
801 [ + - ]: 7901 : toremove.insert(mapTx.project<0>(it));
802 : 7901 : it++;
803 : : }
804 : 185718 : setEntries stage;
805 [ + + ]: 193619 : for (txiter removeit : toremove) {
806 [ + - ]: 7901 : CalculateDescendants(removeit, stage);
807 : : }
808 [ + - ]: 185718 : RemoveStaged(stage, MemPoolRemovalReason::EXPIRY);
809 : 185718 : return stage.size();
810 : 185718 : }
811 : :
812 : 237876 : CFeeRate CTxMemPool::GetMinFee(size_t sizelimit) const {
813 : 237876 : LOCK(cs);
814 [ + + + + ]: 237876 : if (!blockSinceLastRollingFeeBump || rollingMinimumFeeRate == 0)
815 : 233684 : return CFeeRate(llround(rollingMinimumFeeRate));
816 : :
817 [ + - ]: 4192 : int64_t time = GetTime();
818 [ + + ]: 4192 : if (time > lastRollingFeeUpdate + 10) {
819 : 145 : double halflife = ROLLING_FEE_HALFLIFE;
820 [ + - + - ]: 145 : if (DynamicMemoryUsage() < sizelimit / 4)
821 : : halflife /= 4;
822 [ + - - + ]: 145 : else if (DynamicMemoryUsage() < sizelimit / 2)
823 : 0 : halflife /= 2;
824 : :
825 : 145 : rollingMinimumFeeRate = rollingMinimumFeeRate / pow(2.0, (time - lastRollingFeeUpdate) / halflife);
826 : 145 : lastRollingFeeUpdate = time;
827 : :
828 [ + + ]: 145 : if (rollingMinimumFeeRate < (double)m_opts.incremental_relay_feerate.GetFeePerK() / 2) {
829 : 114 : rollingMinimumFeeRate = 0;
830 : 114 : return CFeeRate(0);
831 : : }
832 : : }
833 : 4078 : return std::max(CFeeRate(llround(rollingMinimumFeeRate)), m_opts.incremental_relay_feerate);
834 : 237876 : }
835 : :
836 : 1414 : void CTxMemPool::trackPackageRemoved(const CFeeRate& rate) {
837 : 1414 : AssertLockHeld(cs);
838 [ + + ]: 1414 : if (rate.GetFeePerK() > rollingMinimumFeeRate) {
839 : 1222 : rollingMinimumFeeRate = rate.GetFeePerK();
840 : 1222 : blockSinceLastRollingFeeBump = false;
841 : : }
842 : 1414 : }
843 : :
844 : 184333 : void CTxMemPool::TrimToSize(size_t sizelimit, std::vector<COutPoint>* pvNoSpendsRemaining) {
845 : 184333 : AssertLockHeld(cs);
846 [ - + ]: 184333 : Assume(!m_have_changeset);
847 : :
848 : 184333 : unsigned nTxnRemoved = 0;
849 : 184333 : CFeeRate maxFeeRateRemoved(0);
850 : :
851 [ + + + + ]: 185747 : while (!mapTx.empty() && DynamicMemoryUsage() > sizelimit) {
852 [ + - ]: 1414 : const auto &[worst_chunk, feeperweight] = m_txgraph->GetWorstMainChunk();
853 [ + - ]: 1414 : FeePerVSize feerate = ToFeePerVSize(feeperweight);
854 [ + - ]: 1414 : CFeeRate removed{feerate.fee, feerate.size};
855 : :
856 : : // We set the new mempool min fee to the feerate of the removed set, plus the
857 : : // "minimum reasonable fee rate" (ie some value under which we consider txn
858 : : // to have 0 fee). This way, we don't allow txn to enter mempool with feerate
859 : : // equal to txn which were removed with no block in between.
860 : 1414 : removed += m_opts.incremental_relay_feerate;
861 [ + - ]: 1414 : trackPackageRemoved(removed);
862 : 1414 : maxFeeRateRemoved = std::max(maxFeeRateRemoved, removed);
863 : :
864 [ - + ]: 1414 : nTxnRemoved += worst_chunk.size();
865 : :
866 : 1414 : std::vector<CTransaction> txn;
867 [ + + ]: 1414 : if (pvNoSpendsRemaining) {
868 [ + - ]: 1057 : txn.reserve(worst_chunk.size());
869 [ + + ]: 2234 : for (auto ref : worst_chunk) {
870 [ + - ]: 1177 : txn.emplace_back(static_cast<const CTxMemPoolEntry&>(*ref).GetTx());
871 : : }
872 : : }
873 : :
874 : 1414 : setEntries stage;
875 [ + + ]: 2952 : for (auto ref : worst_chunk) {
876 [ + - ]: 1538 : stage.insert(mapTx.iterator_to(static_cast<const CTxMemPoolEntry&>(*ref)));
877 : : }
878 [ + + ]: 2952 : for (auto e : stage) {
879 [ + - ]: 1538 : removeUnchecked(e, MemPoolRemovalReason::SIZELIMIT);
880 : : }
881 [ + + ]: 1414 : if (pvNoSpendsRemaining) {
882 [ + + ]: 2234 : for (const CTransaction& tx : txn) {
883 [ + + ]: 3094 : for (const CTxIn& txin : tx.vin) {
884 [ + - + + ]: 1917 : if (exists(txin.prevout.hash)) continue;
885 [ + - ]: 1915 : pvNoSpendsRemaining->push_back(txin.prevout);
886 : : }
887 : : }
888 : : }
889 : 2828 : }
890 : :
891 [ + + ]: 184333 : if (maxFeeRateRemoved > CFeeRate(0)) {
892 [ - + - - ]: 1075 : LogDebug(BCLog::MEMPOOL, "Removed %u txn, rolling minimum fee bumped to %s\n", nTxnRemoved, maxFeeRateRemoved.ToString());
893 : : }
894 : 184333 : }
895 : :
896 : 391992 : std::tuple<size_t, size_t, CAmount> CTxMemPool::CalculateAncestorData(const CTxMemPoolEntry& entry) const
897 : : {
898 : 391992 : auto ancestors = m_txgraph->GetAncestors(entry, TxGraph::Level::MAIN);
899 : :
900 [ - + ]: 391992 : size_t ancestor_count = ancestors.size();
901 : 391992 : size_t ancestor_size = 0;
902 : 391992 : CAmount ancestor_fees = 0;
903 [ + + ]: 1341574 : for (auto tx: ancestors) {
904 : 949582 : const CTxMemPoolEntry& anc = static_cast<const CTxMemPoolEntry&>(*tx);
905 [ + - ]: 949582 : ancestor_size += anc.GetTxSize();
906 : 949582 : ancestor_fees += anc.GetModifiedFee();
907 : : }
908 : 391992 : return {ancestor_count, ancestor_size, ancestor_fees};
909 : 391992 : }
910 : :
911 : 316364 : std::tuple<size_t, size_t, CAmount> CTxMemPool::CalculateDescendantData(const CTxMemPoolEntry& entry) const
912 : : {
913 : 316364 : auto descendants = m_txgraph->GetDescendants(entry, TxGraph::Level::MAIN);
914 [ - + ]: 316364 : size_t descendant_count = descendants.size();
915 : 316364 : size_t descendant_size = 0;
916 : 316364 : CAmount descendant_fees = 0;
917 : :
918 [ + + ]: 662790 : for (auto tx: descendants) {
919 : 346426 : const CTxMemPoolEntry &desc = static_cast<const CTxMemPoolEntry&>(*tx);
920 [ + - ]: 346426 : descendant_size += desc.GetTxSize();
921 : 346426 : descendant_fees += desc.GetModifiedFee();
922 : : }
923 : 316364 : return {descendant_count, descendant_size, descendant_fees};
924 : 316364 : }
925 : :
926 : 0 : void CTxMemPool::GetTransactionAncestry(const Txid& txid, size_t& ancestors, size_t& cluster_count, size_t* const ancestorsize, CAmount* const ancestorfees) const {
927 : 0 : LOCK(cs);
928 [ # # ]: 0 : auto it = mapTx.find(txid);
929 : 0 : ancestors = cluster_count = 0;
930 [ # # ]: 0 : if (it != mapTx.end()) {
931 [ # # # # ]: 0 : auto [ancestor_count, ancestor_size, ancestor_fees] = CalculateAncestorData(*it);
932 : 0 : ancestors = ancestor_count;
933 [ # # ]: 0 : if (ancestorsize) *ancestorsize = ancestor_size;
934 [ # # ]: 0 : if (ancestorfees) *ancestorfees = ancestor_fees;
935 [ # # ]: 0 : cluster_count = m_txgraph->GetCluster(*it, TxGraph::Level::MAIN).size();
936 : : }
937 : 0 : }
938 : :
939 : 1 : bool CTxMemPool::GetLoadTried() const
940 : : {
941 : 1 : LOCK(cs);
942 [ + - ]: 1 : return m_load_tried;
943 : 1 : }
944 : :
945 : 1435 : void CTxMemPool::SetLoadTried(bool load_tried)
946 : : {
947 : 1435 : LOCK(cs);
948 [ + - ]: 1435 : m_load_tried = load_tried;
949 : 1435 : }
950 : :
951 : 1874 : std::vector<CTxMemPool::txiter> CTxMemPool::GatherClusters(const std::vector<Txid>& txids) const
952 : : {
953 : 1874 : AssertLockHeld(cs);
954 : :
955 : 1874 : std::vector<CTxMemPool::txiter> ret;
956 : 1874 : std::set<const CTxMemPoolEntry*> unique_cluster_representatives;
957 [ + + ]: 63734 : for (auto txid : txids) {
958 [ + - ]: 61860 : auto it = mapTx.find(txid);
959 [ + - ]: 61860 : if (it != mapTx.end()) {
960 : : // Note that TxGraph::GetCluster will return results in graph
961 : : // order, which is deterministic (as long as we are not modifying
962 : : // the graph).
963 : 61860 : auto cluster = m_txgraph->GetCluster(*it, TxGraph::Level::MAIN);
964 [ + - + + ]: 61860 : if (unique_cluster_representatives.insert(static_cast<const CTxMemPoolEntry*>(&(**cluster.begin()))).second) {
965 [ + + ]: 110064 : for (auto tx : cluster) {
966 [ + - ]: 100080 : ret.emplace_back(mapTx.iterator_to(static_cast<const CTxMemPoolEntry&>(*tx)));
967 : : }
968 : : }
969 : 61860 : }
970 : : }
971 [ - + - + ]: 1874 : if (ret.size() > 500) {
972 : 0 : return {};
973 : : }
974 : 1874 : return ret;
975 : 1874 : }
976 : :
977 : 18908 : util::Result<std::pair<std::vector<FeeFrac>, std::vector<FeeFrac>>> CTxMemPool::ChangeSet::CalculateChunksForRBF()
978 : : {
979 : 18908 : LOCK(m_pool->cs);
980 : :
981 [ + - + + ]: 18908 : if (!CheckMemPoolPolicyLimits()) {
982 [ + - + - ]: 3180 : return util::Error{Untranslated("cluster size limit exceeded")};
983 : : }
984 : :
985 : 35696 : return m_pool->m_txgraph->GetMainStagingDiagrams();
986 : 18908 : }
987 : :
988 : 1082335 : CTxMemPool::ChangeSet::TxHandle CTxMemPool::ChangeSet::StageAddition(const CTransactionRef& tx, const CAmount fee, int64_t time, unsigned int entry_height, uint64_t entry_sequence, bool spends_coinbase, int64_t sigops_cost, LockPoints lp)
989 : : {
990 : 1082335 : LOCK(m_pool->cs);
991 [ + - - + ]: 1082335 : Assume(m_to_add.find(tx->GetHash()) == m_to_add.end());
992 [ - + ]: 1082335 : Assume(!m_dependencies_processed);
993 : :
994 : : // We need to process dependencies after adding a new transaction.
995 : 1082335 : m_dependencies_processed = false;
996 : :
997 : 1082335 : CAmount delta{0};
998 [ + - ]: 1082335 : m_pool->ApplyDelta(tx->GetHash(), delta);
999 : :
1000 [ + - ]: 1082335 : TxGraph::Ref ref(m_pool->m_txgraph->AddTransaction(FeePerWeight(fee, GetSigOpsAdjustedWeight(GetTransactionWeight(*tx), sigops_cost, ::nBytesPerSigOp))));
1001 [ + - ]: 1082335 : auto newit = m_to_add.emplace(std::move(ref), tx, fee, time, entry_height, entry_sequence, spends_coinbase, sigops_cost, lp).first;
1002 [ + + ]: 1082335 : if (delta) {
1003 : 23830 : newit->UpdateModifiedFee(delta);
1004 : 23830 : m_pool->m_txgraph->SetTransactionFee(*newit, newit->GetModifiedFee());
1005 : : }
1006 : :
1007 [ + - ]: 1082335 : m_entry_vec.push_back(newit);
1008 : :
1009 : 2164670 : return newit;
1010 [ + - ]: 2164670 : }
1011 : :
1012 : 118896 : void CTxMemPool::ChangeSet::StageRemoval(CTxMemPool::txiter it)
1013 : : {
1014 : 118896 : LOCK(m_pool->cs);
1015 : 118896 : m_pool->m_txgraph->RemoveTransaction(*it);
1016 [ + - ]: 118896 : m_to_remove.insert(it);
1017 : 118896 : }
1018 : :
1019 : 227654 : void CTxMemPool::ChangeSet::Apply()
1020 : : {
1021 : 227654 : LOCK(m_pool->cs);
1022 [ + + ]: 227654 : if (!m_dependencies_processed) {
1023 [ + - ]: 12 : ProcessDependencies();
1024 : : }
1025 [ + - ]: 227654 : m_pool->Apply(this);
1026 : 227654 : m_to_add.clear();
1027 : 227654 : m_to_remove.clear();
1028 [ + - ]: 227654 : m_entry_vec.clear();
1029 [ + - ]: 227654 : m_ancestors.clear();
1030 : 227654 : }
1031 : :
1032 : 767804 : void CTxMemPool::ChangeSet::ProcessDependencies()
1033 : : {
1034 : 767804 : LOCK(m_pool->cs);
1035 [ - + ]: 767804 : Assume(!m_dependencies_processed); // should only call this once.
1036 [ + + ]: 1536726 : for (const auto& entryptr : m_entry_vec) {
1037 [ + - + - : 3782829 : for (const auto &txin : entryptr->GetSharedTx()->vin) {
+ + ]
1038 [ + - ]: 1476063 : std::optional<txiter> piter = m_pool->GetIter(txin.prevout.hash);
1039 [ + + ]: 1476063 : if (!piter) {
1040 [ + - ]: 1003138 : auto it = m_to_add.find(txin.prevout.hash);
1041 [ + + ]: 1003138 : if (it != m_to_add.end()) {
1042 : 1946 : piter = std::make_optional(it);
1043 : : }
1044 : : }
1045 [ + + ]: 1476063 : if (piter) {
1046 : 474871 : m_pool->m_txgraph->AddDependency(/*parent=*/**piter, /*child=*/*entryptr);
1047 : : }
1048 : : }
1049 : : }
1050 : 767804 : m_dependencies_processed = true;
1051 [ + - ]: 767804 : return;
1052 : 767804 : }
1053 : :
1054 : 798095 : bool CTxMemPool::ChangeSet::CheckMemPoolPolicyLimits()
1055 : : {
1056 : 798095 : LOCK(m_pool->cs);
1057 [ + + ]: 798095 : if (!m_dependencies_processed) {
1058 [ + - ]: 767792 : ProcessDependencies();
1059 : : }
1060 : :
1061 [ + - ]: 798095 : return !m_pool->m_txgraph->IsOversized(TxGraph::Level::TOP);
1062 : 798095 : }
1063 : :
1064 : 131457 : std::vector<FeePerWeight> CTxMemPool::GetFeerateDiagram() const
1065 : : {
1066 : 131457 : FeePerWeight zero{};
1067 : 131457 : std::vector<FeePerWeight> ret;
1068 : :
1069 [ + - ]: 131457 : ret.emplace_back(zero);
1070 : :
1071 : 131457 : StartBlockBuilding();
1072 : :
1073 : 131457 : std::vector<CTxMemPoolEntry::CTxMemPoolEntryRef> dummy;
1074 : :
1075 [ + - ]: 131457 : FeePerWeight last_selection = GetBlockBuilderChunk(dummy);
1076 [ + + ]: 169525 : while (last_selection != FeePerWeight{}) {
1077 [ + - ]: 38068 : last_selection += ret.back();
1078 [ + - ]: 38068 : ret.emplace_back(last_selection);
1079 : 38068 : IncludeBuilderChunk();
1080 [ + - ]: 38068 : last_selection = GetBlockBuilderChunk(dummy);
1081 : : }
1082 : 131457 : StopBlockBuilding();
1083 : 131457 : return ret;
1084 : 131457 : }
|
