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 : 4540 : bool TestLockPointValidity(CChain& active_chain, const LockPoints& lp)
41 : : {
42 : 4540 : 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 [ + - ]: 4540 : 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 [ + + ]: 4540 : if (!active_chain.Contains(lp.maxInputBlock)) {
49 : 229 : return false;
50 : : }
51 : : }
52 : :
53 : : // LockPoints still valid
54 : : return true;
55 : : }
56 : :
57 : 8678290 : std::vector<CTxMemPoolEntry::CTxMemPoolEntryRef> CTxMemPool::GetChildren(const CTxMemPoolEntry& entry) const
58 : : {
59 : 8678290 : LOCK(cs);
60 : 8678290 : std::vector<CTxMemPoolEntry::CTxMemPoolEntryRef> ret;
61 : 8678290 : WITH_FRESH_EPOCH(m_epoch);
62 : 8678290 : auto iter = mapNextTx.lower_bound(COutPoint(entry.GetTx().GetHash(), 0));
63 [ + + + + ]: 8871434 : for (; iter != mapNextTx.end() && iter->first->hash == entry.GetTx().GetHash(); ++iter) {
64 [ + + ]: 193144 : if (!visited(iter->second)) {
65 [ + - ]: 193033 : ret.emplace_back(*(iter->second));
66 : : }
67 : : }
68 : 17356580 : return ret;
69 [ + - ]: 17356580 : }
70 : :
71 : 8700735 : std::vector<CTxMemPoolEntry::CTxMemPoolEntryRef> CTxMemPool::GetParents(const CTxMemPoolEntry& entry) const
72 : : {
73 : 8700735 : LOCK(cs);
74 : 8700735 : std::vector<CTxMemPoolEntry::CTxMemPoolEntryRef> ret;
75 : 8700735 : std::set<Txid> inputs;
76 [ + + ]: 19858353 : for (const auto& txin : entry.GetTx().vin) {
77 [ + - ]: 11157618 : inputs.insert(txin.prevout.hash);
78 : : }
79 [ + + ]: 19844182 : for (const auto& hash : inputs) {
80 [ + - ]: 11143447 : std::optional<txiter> piter = GetIter(hash);
81 [ + + ]: 11143447 : if (piter) {
82 [ + - ]: 192891 : ret.emplace_back(**piter);
83 : : }
84 : : }
85 : 8700735 : return ret;
86 [ + - ]: 17401470 : }
87 : :
88 : 3241 : void CTxMemPool::UpdateTransactionsFromBlock(const std::vector<Txid>& vHashesToUpdate)
89 : : {
90 : 3241 : 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 [ + + ]: 4056 : for (const Txid& hash : vHashesToUpdate | std::views::reverse) {
95 : : // calculate children from mapNextTx
96 : 815 : txiter it = mapTx.find(hash);
97 [ - + ]: 815 : if (it == mapTx.end()) {
98 : 0 : continue;
99 : : }
100 : 815 : auto iter = mapNextTx.lower_bound(COutPoint(hash, 0));
101 : 815 : {
102 [ + + + + ]: 3266 : for (; iter != mapNextTx.end() && iter->first->hash == hash; ++iter) {
103 [ - + ]: 2451 : txiter childIter = iter->second;
104 [ - + ]: 2451 : 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 : 2451 : m_txgraph->AddDependency(/*parent=*/*it, /*child=*/*childIter);
108 : : }
109 : : }
110 : : }
111 : :
112 : 3241 : auto txs_to_remove = m_txgraph->Trim(); // Enforce cluster size limits.
113 [ - + ]: 3241 : 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 : 3241 : }
118 : :
119 : 223 : bool CTxMemPool::HasDescendants(const Txid& txid) const
120 : : {
121 : 223 : LOCK(cs);
122 [ + - ]: 223 : auto entry = GetEntry(txid);
123 [ + + ]: 223 : if (!entry) return false;
124 [ - + ]: 222 : return m_txgraph->GetDescendants(*entry, TxGraph::Level::MAIN).size() > 1;
125 : 223 : }
126 : :
127 : 3617 : CTxMemPool::setEntries CTxMemPool::CalculateMemPoolAncestors(const CTxMemPoolEntry &entry) const
128 : : {
129 : 3617 : auto ancestors = m_txgraph->GetAncestors(entry, TxGraph::Level::MAIN);
130 [ - + ]: 3617 : setEntries ret;
131 [ - + + + ]: 3617 : if (ancestors.size() > 0) {
132 [ + + ]: 18229 : for (auto ancestor : ancestors) {
133 [ + + ]: 15866 : if (ancestor != &entry) {
134 [ + - ]: 13503 : 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 : 1254 : setEntries staged_parents;
143 : 1254 : const CTransaction &tx = entry.GetTx();
144 : :
145 : : // Get parents of this transaction that are in the mempool
146 [ - + + + ]: 2840 : for (unsigned int i = 0; i < tx.vin.size(); i++) {
147 [ + - ]: 1586 : std::optional<txiter> piter = GetIter(tx.vin[i].prevout.hash);
148 [ + + ]: 1586 : if (piter) {
149 [ + - ]: 233 : staged_parents.insert(*piter);
150 : : }
151 : : }
152 : :
153 [ + + ]: 1461 : for (const auto& parent : staged_parents) {
154 : 207 : auto parent_ancestors = m_txgraph->GetAncestors(*parent, TxGraph::Level::MAIN);
155 [ + + ]: 692 : for (auto ancestor : parent_ancestors) {
156 [ + - ]: 485 : ret.insert(mapTx.iterator_to(static_cast<const CTxMemPoolEntry&>(*ancestor)));
157 : : }
158 : 207 : }
159 : :
160 : 1254 : return ret;
161 : 4871 : }
162 : :
163 : 1244 : static CTxMemPool::Options&& Flatten(CTxMemPool::Options&& opts, bilingual_str& error)
164 : : {
165 [ + - ]: 1244 : opts.check_ratio = std::clamp<int>(opts.check_ratio, 0, 1'000'000);
166 : 1244 : int64_t cluster_limit_bytes = opts.limits.cluster_size_vbytes * 40;
167 [ + - + - : 1244 : if (opts.max_size_bytes < 0 || (opts.max_size_bytes > 0 && opts.max_size_bytes < cluster_limit_bytes)) {
+ + ]
168 : 2 : error = strprintf(_("-maxmempool must be at least %d MB"), std::ceil(cluster_limit_bytes / 1'000'000.0));
169 : : }
170 : 1244 : return std::move(opts);
171 : : }
172 : :
173 : 1244 : CTxMemPool::CTxMemPool(Options opts, bilingual_str& error)
174 [ + - + - ]: 1244 : : m_opts{Flatten(std::move(opts), error)}
175 : : {
176 : 1244 : m_txgraph = MakeTxGraph(m_opts.limits.cluster_count, m_opts.limits.cluster_size_vbytes * WITNESS_SCALE_FACTOR, ACCEPTABLE_ITERS);
177 : 1244 : }
178 : :
179 : 54 : bool CTxMemPool::isSpent(const COutPoint& outpoint) const
180 : : {
181 : 54 : LOCK(cs);
182 [ + - ]: 54 : return mapNextTx.count(outpoint);
183 : 54 : }
184 : :
185 : 2082 : unsigned int CTxMemPool::GetTransactionsUpdated() const
186 : : {
187 : 2082 : return nTransactionsUpdated;
188 : : }
189 : :
190 : 146992 : void CTxMemPool::AddTransactionsUpdated(unsigned int n)
191 : : {
192 : 146992 : nTransactionsUpdated += n;
193 : 146992 : }
194 : :
195 : 50375 : void CTxMemPool::Apply(ChangeSet* changeset)
196 : : {
197 : 50375 : AssertLockHeld(cs);
198 : 50375 : m_txgraph->CommitStaging();
199 : :
200 : 50375 : RemoveStaged(changeset->m_to_remove, MemPoolRemovalReason::REPLACED);
201 : :
202 [ - + + + ]: 100804 : for (size_t i=0; i<changeset->m_entry_vec.size(); ++i) {
203 : 50429 : auto tx_entry = changeset->m_entry_vec[i];
204 : : // First splice this entry into mapTx.
205 : 50429 : auto node_handle = changeset->m_to_add.extract(tx_entry);
206 [ + - ]: 50429 : auto result = mapTx.insert(std::move(node_handle));
207 : :
208 [ + - ]: 50429 : Assume(result.inserted);
209 : 50429 : txiter it = result.position;
210 : :
211 [ + - ]: 50429 : addNewTransaction(it);
212 [ - + ]: 50429 : }
213 : 50375 : m_txgraph->DoWork(POST_CHANGE_WORK);
214 : 50375 : }
215 : :
216 : 50429 : void CTxMemPool::addNewTransaction(CTxMemPool::txiter newit)
217 : : {
218 : 50429 : 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 : 50429 : cachedInnerUsage += entry.DynamicMemoryUsage();
224 : :
225 : 50429 : const CTransaction& tx = newit->GetTx();
226 [ - + + + ]: 113250 : for (unsigned int i = 0; i < tx.vin.size(); i++) {
227 : 62821 : 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 : 50429 : nTransactionsUpdated++;
237 : 50429 : totalTxSize += entry.GetTxSize();
238 : 50429 : m_total_fee += entry.GetFee();
239 : :
240 : 50429 : txns_randomized.emplace_back(tx.GetWitnessHash(), newit);
241 [ - + ]: 50429 : newit->idx_randomized = txns_randomized.size() - 1;
242 : :
243 : : TRACEPOINT(mempool, added,
244 : : entry.GetTx().GetHash().data(),
245 : : entry.GetTxSize(),
246 : : entry.GetFee()
247 : 50429 : );
248 : 50429 : }
249 : :
250 : 46647 : 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 [ + + ]: 46647 : uint64_t mempool_sequence = GetAndIncrementSequence();
255 : :
256 [ + + + - ]: 46647 : 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 [ + - + - ]: 5349 : 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 : 46647 : );
270 : :
271 [ + + ]: 104823 : for (const CTxIn& txin : it->GetTx().vin)
272 : 58176 : mapNextTx.erase(txin.prevout);
273 : :
274 : 46647 : RemoveUnbroadcastTx(it->GetTx().GetHash(), true /* add logging because unchecked */);
275 : :
276 [ - + + + ]: 46647 : if (txns_randomized.size() > 1) {
277 : : // Remove entry from txns_randomized by replacing it with the back and deleting the back.
278 [ - + ]: 44582 : txns_randomized[it->idx_randomized] = std::move(txns_randomized.back());
279 [ - + ]: 44582 : txns_randomized[it->idx_randomized].second->idx_randomized = it->idx_randomized;
280 [ - + ]: 44582 : txns_randomized.pop_back();
281 [ - + - + : 44582 : if (txns_randomized.size() * 2 < txns_randomized.capacity()) {
+ + ]
282 : 3210 : txns_randomized.shrink_to_fit();
283 : : }
284 : : } else {
285 [ + - ]: 2065 : txns_randomized.clear();
286 : : }
287 : :
288 : 46647 : totalTxSize -= it->GetTxSize();
289 : 46647 : m_total_fee -= it->GetFee();
290 : 46647 : cachedInnerUsage -= it->DynamicMemoryUsage();
291 : 46647 : mapTx.erase(it);
292 : 46647 : nTransactionsUpdated++;
293 : 46647 : }
294 : :
295 : : // Calculates descendants of given entry and adds to setDescendants.
296 : 79902 : void CTxMemPool::CalculateDescendants(txiter entryit, setEntries& setDescendants) const
297 : : {
298 : 79902 : (void)CalculateDescendants(*entryit, setDescendants);
299 : 79902 : return;
300 : : }
301 : :
302 : 79964 : CTxMemPool::txiter CTxMemPool::CalculateDescendants(const CTxMemPoolEntry& entry, setEntries& setDescendants) const
303 : : {
304 [ + + ]: 361868 : for (auto tx : m_txgraph->GetDescendants(entry, TxGraph::Level::MAIN)) {
305 [ + - ]: 281904 : setDescendants.insert(mapTx.iterator_to(static_cast<const CTxMemPoolEntry&>(*tx)));
306 : : }
307 : 79964 : return mapTx.iterator_to(entry);
308 : : }
309 : :
310 : 67 : void CTxMemPool::removeRecursive(CTxMemPool::txiter to_remove, MemPoolRemovalReason reason)
311 : : {
312 : 67 : AssertLockHeld(cs);
313 : 67 : Assume(!m_have_changeset);
314 : 67 : auto descendants = m_txgraph->GetDescendants(*to_remove, TxGraph::Level::MAIN);
315 [ + + ]: 141 : for (auto tx: descendants) {
316 [ + - ]: 74 : removeUnchecked(mapTx.iterator_to(static_cast<const CTxMemPoolEntry&>(*tx)), reason);
317 : : }
318 : 67 : }
319 : :
320 : 19264 : void CTxMemPool::removeRecursive(const CTransaction &origTx, MemPoolRemovalReason reason)
321 : : {
322 : : // Remove transaction from memory pool
323 : 19264 : AssertLockHeld(cs);
324 : 19264 : Assume(!m_have_changeset);
325 : 19264 : txiter origit = mapTx.find(origTx.GetHash());
326 [ + + ]: 19264 : if (origit != mapTx.end()) {
327 : 7 : 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 : 19257 : auto iter = mapNextTx.lower_bound(COutPoint(origTx.GetHash(), 0));
334 : 19257 : std::vector<const TxGraph::Ref*> to_remove;
335 [ + + + + ]: 19331 : while (iter != mapNextTx.end() && iter->first->hash == origTx.GetHash()) {
336 [ + - ]: 74 : to_remove.emplace_back(&*(iter->second));
337 : 74 : ++iter;
338 : : }
339 [ - + ]: 19257 : auto all_removes = m_txgraph->GetDescendantsUnion(to_remove, TxGraph::Level::MAIN);
340 [ + + ]: 19334 : for (auto ref : all_removes) {
341 : 77 : auto tx = mapTx.iterator_to(static_cast<const CTxMemPoolEntry&>(*ref));
342 [ + - ]: 77 : removeUnchecked(tx, reason);
343 : : }
344 : 19257 : }
345 : 19264 : }
346 : :
347 : 3241 : 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 : 3241 : AssertLockHeld(cs);
351 : 3241 : AssertLockHeld(::cs_main);
352 : 3241 : Assume(!m_have_changeset);
353 : :
354 : 3241 : std::vector<const TxGraph::Ref*> to_remove;
355 [ + + ]: 5531 : for (txiter it = mapTx.begin(); it != mapTx.end(); it++) {
356 [ + - + + ]: 2290 : if (check_final_and_mature(it)) {
357 [ + - ]: 15 : to_remove.emplace_back(&*it);
358 : : }
359 : : }
360 : :
361 [ - + ]: 3241 : auto all_to_remove = m_txgraph->GetDescendantsUnion(to_remove, TxGraph::Level::MAIN);
362 : :
363 [ + + ]: 3278 : for (auto ref : all_to_remove) {
364 : 37 : auto it = mapTx.iterator_to(static_cast<const CTxMemPoolEntry&>(*ref));
365 [ + - ]: 37 : removeUnchecked(it, MemPoolRemovalReason::REORG);
366 : : }
367 [ + + ]: 5494 : for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
368 [ + - - + ]: 2253 : assert(TestLockPointValidity(chain, it->GetLockPoints()));
369 : : }
370 : 3241 : m_txgraph->DoWork(POST_CHANGE_WORK);
371 : 3241 : }
372 : :
373 : 57108 : void CTxMemPool::removeConflicts(const CTransaction &tx)
374 : : {
375 : : // Remove transactions which depend on inputs of tx, recursively
376 : 57108 : AssertLockHeld(cs);
377 [ + + ]: 125726 : for (const CTxIn &txin : tx.vin) {
378 : 68618 : auto it = mapNextTx.find(txin.prevout);
379 [ + + ]: 68618 : if (it != mapNextTx.end()) {
380 [ + - ]: 60 : const CTransaction &txConflict = it->second->GetTx();
381 [ + - ]: 60 : if (Assume(txConflict.GetHash() != tx.GetHash()))
382 : : {
383 : 60 : ClearPrioritisation(txConflict.GetHash());
384 : 60 : removeRecursive(it->second, MemPoolRemovalReason::CONFLICT);
385 : : }
386 : : }
387 : : }
388 : 57108 : }
389 : :
390 : 132458 : 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 : 132458 : AssertLockHeld(cs);
394 [ + + ]: 132458 : Assume(!m_have_changeset);
395 : 132458 : std::vector<RemovedMempoolTransactionInfo> txs_removed_for_block;
396 [ + + + - : 132458 : if (mapTx.size() || mapNextTx.size() || mapDeltas.size()) {
+ + ]
397 [ - + + - ]: 7812 : txs_removed_for_block.reserve(vtx.size());
398 [ + + ]: 64920 : for (const auto& tx : vtx) {
399 [ + - ]: 57108 : txiter it = mapTx.find(tx->GetHash());
400 [ + + ]: 57108 : if (it != mapTx.end()) {
401 [ + - ]: 44864 : txs_removed_for_block.emplace_back(*it);
402 [ + - ]: 44864 : removeUnchecked(it, MemPoolRemovalReason::BLOCK);
403 : : }
404 [ + - ]: 57108 : removeConflicts(*tx);
405 [ + - ]: 57108 : ClearPrioritisation(tx->GetHash());
406 : : }
407 : : }
408 [ + - ]: 132458 : if (m_opts.signals) {
409 [ + - ]: 132458 : m_opts.signals->MempoolTransactionsRemovedForBlock(txs_removed_for_block, nBlockHeight);
410 : : }
411 [ + - ]: 132458 : lastRollingFeeUpdate = GetTime();
412 : 132458 : blockSinceLastRollingFeeBump = true;
413 : 132458 : m_txgraph->DoWork(POST_CHANGE_WORK);
414 : 132458 : }
415 : :
416 : 156455 : void CTxMemPool::check(const CCoinsViewCache& active_coins_tip, int64_t spendheight) const
417 : : {
418 [ + + ]: 156455 : if (m_opts.check_ratio == 0) return;
419 : :
420 [ + - ]: 154408 : if (FastRandomContext().randrange(m_opts.check_ratio) >= 1) return;
421 : :
422 : 154408 : AssertLockHeld(::cs_main);
423 : 154408 : LOCK(cs);
424 [ + - + - : 154408 : LogDebug(BCLog::MEMPOOL, "Checking mempool with %u transactions and %u inputs\n", (unsigned int)mapTx.size(), (unsigned int)mapNextTx.size());
+ - ]
425 : :
426 : 154408 : uint64_t checkTotal = 0;
427 : 154408 : CAmount check_total_fee{0};
428 : 154408 : CAmount check_total_modified_fee{0};
429 : 154408 : int64_t check_total_adjusted_weight{0};
430 : 154408 : uint64_t innerUsage = 0;
431 : :
432 [ - + ]: 154408 : assert(!m_txgraph->IsOversized(TxGraph::Level::MAIN));
433 [ + - ]: 154408 : m_txgraph->SanityCheck();
434 : :
435 [ + - ]: 154408 : CCoinsViewCache mempoolDuplicate(const_cast<CCoinsViewCache*>(&active_coins_tip));
436 : :
437 [ + - ]: 154408 : const auto score_with_topo{GetSortedScoreWithTopology()};
438 : :
439 : : // Number of chunks is bounded by number of transactions.
440 [ + - ]: 154408 : const auto diagram{GetFeerateDiagram()};
441 [ - + - + : 154408 : assert(diagram.size() <= score_with_topo.size() + 1);
- + ]
442 [ - + ]: 154408 : assert(diagram.size() >= 1);
443 : :
444 : 154408 : std::optional<Wtxid> last_wtxid = std::nullopt;
445 : 154408 : auto diagram_iter = diagram.cbegin();
446 : :
447 [ + + ]: 8823445 : 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 [ - + ]: 8669037 : assert(diagram_iter->size >= check_total_adjusted_weight);
455 [ + + ]: 8669037 : if (diagram_iter->fee == check_total_modified_fee &&
456 [ + - ]: 8653350 : diagram_iter->size == check_total_adjusted_weight) {
457 : 8653350 : ++diagram_iter;
458 : : }
459 [ + - ]: 8669037 : checkTotal += it->GetTxSize();
460 [ + - ]: 8669037 : check_total_adjusted_weight += it->GetAdjustedWeight();
461 [ + + ]: 8669037 : check_total_fee += it->GetFee();
462 [ + + ]: 8669037 : check_total_modified_fee += it->GetModifiedFee();
463 [ + + ]: 8669037 : innerUsage += it->DynamicMemoryUsage();
464 [ + + ]: 8669037 : const CTransaction& tx = it->GetTx();
465 : :
466 : : // CompareMiningScoreWithTopology should agree with GetSortedScoreWithTopology()
467 [ + + ]: 8669037 : if (last_wtxid) {
468 [ + - - + ]: 8638962 : assert(CompareMiningScoreWithTopology(*last_wtxid, tx.GetWitnessHash()));
469 : : }
470 [ + + ]: 8669037 : last_wtxid = tx.GetWitnessHash();
471 : :
472 : 8669037 : std::set<CTxMemPoolEntry::CTxMemPoolEntryRef, CompareIteratorByHash> setParentCheck;
473 : 8669037 : std::set<CTxMemPoolEntry::CTxMemPoolEntryRef, CompareIteratorByHash> setParentsStored;
474 [ + + ]: 19776208 : for (const CTxIn &txin : tx.vin) {
475 : : // Check that every mempool transaction's inputs refer to available coins, or other mempool tx's.
476 [ + - ]: 11107171 : indexed_transaction_set::const_iterator it2 = mapTx.find(txin.prevout.hash);
477 [ + + ]: 11107171 : if (it2 != mapTx.end()) {
478 [ - + ]: 186040 : const CTransaction& tx2 = it2->GetTx();
479 [ - + + - : 186040 : assert(tx2.vout.size() > txin.prevout.n && !tx2.vout[txin.prevout.n].IsNull());
- + ]
480 [ + - ]: 186040 : 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 [ + - - + ]: 11107171 : assert(mempoolDuplicate.HaveCoin(txin.prevout));
487 : : // Check whether its inputs are marked in mapNextTx.
488 : 11107171 : auto it3 = mapNextTx.find(txin.prevout);
489 [ - + ]: 11107171 : assert(it3 != mapNextTx.end());
490 [ - + ]: 11107171 : assert(it3->first == &txin.prevout);
491 [ - + ]: 11107171 : assert(&it3->second->GetTx() == &tx);
492 : : }
493 : 9040895 : auto comp = [](const CTxMemPoolEntry& a, const CTxMemPoolEntry& b) -> bool {
494 [ + - ]: 371858 : return a.GetTx().GetHash() == b.GetTx().GetHash();
495 : : };
496 [ + - + + ]: 8854966 : for (auto &txentry : GetParents(*it)) {
497 [ + - ]: 185929 : setParentsStored.insert(dynamic_cast<const CTxMemPoolEntry&>(txentry.get()));
498 : 0 : }
499 [ - + ]: 8669037 : assert(setParentCheck.size() == setParentsStored.size());
500 [ - + ]: 8669037 : assert(std::equal(setParentCheck.begin(), setParentCheck.end(), setParentsStored.begin(), comp));
501 : :
502 : : // Check children against mapNextTx
503 : 8669037 : std::set<CTxMemPoolEntry::CTxMemPoolEntryRef, CompareIteratorByHash> setChildrenCheck;
504 : 8669037 : std::set<CTxMemPoolEntry::CTxMemPoolEntryRef, CompareIteratorByHash> setChildrenStored;
505 : 8669037 : auto iter = mapNextTx.lower_bound(COutPoint(it->GetTx().GetHash(), 0));
506 [ + + + + ]: 8855077 : for (; iter != mapNextTx.end() && iter->first->hash == it->GetTx().GetHash(); ++iter) {
507 [ - + ]: 186040 : txiter childit = iter->second;
508 [ - + ]: 186040 : assert(childit != mapTx.end()); // mapNextTx points to in-mempool transactions
509 [ + - ]: 186040 : setChildrenCheck.insert(*childit);
510 : : }
511 [ + - + + ]: 8854966 : for (auto &txentry : GetChildren(*it)) {
512 [ + - ]: 185929 : setChildrenStored.insert(dynamic_cast<const CTxMemPoolEntry&>(txentry.get()));
513 : 0 : }
514 [ - + ]: 8669037 : assert(setChildrenCheck.size() == setChildrenStored.size());
515 [ - + ]: 8669037 : assert(std::equal(setChildrenCheck.begin(), setChildrenCheck.end(), setChildrenStored.begin(), comp));
516 : :
517 [ - + ]: 8669037 : TxValidationState dummy_state; // Not used. CheckTxInputs() should always pass
518 : 8669037 : CAmount txfee = 0;
519 [ - + ]: 8669037 : assert(!tx.IsCoinBase());
520 [ + - - + ]: 8669037 : assert(Consensus::CheckTxInputs(tx, dummy_state, mempoolDuplicate, spendheight, txfee));
521 [ + - + + ]: 19776208 : for (const auto& input: tx.vin) mempoolDuplicate.SpendCoin(input.prevout);
522 [ + - ]: 8669037 : AddCoins(mempoolDuplicate, tx, std::numeric_limits<int>::max());
523 : 8669037 : }
524 [ + + ]: 11261579 : for (auto it = mapNextTx.cbegin(); it != mapNextTx.cend(); it++) {
525 [ - + ]: 11107171 : indexed_transaction_set::const_iterator it2 = it->second;
526 [ - + ]: 11107171 : assert(it2 != mapTx.end());
527 : : }
528 : :
529 [ - + ]: 154408 : ++diagram_iter;
530 [ - + ]: 154408 : assert(diagram_iter == diagram.cend());
531 : :
532 [ - + ]: 154408 : assert(totalTxSize == checkTotal);
533 [ - + ]: 154408 : assert(m_total_fee == check_total_fee);
534 [ - + ]: 154408 : assert(diagram.back().fee == check_total_modified_fee);
535 [ - + ]: 154408 : assert(diagram.back().size == check_total_adjusted_weight);
536 [ - + ]: 154408 : assert(innerUsage == cachedInnerUsage);
537 [ + - ]: 308816 : }
538 : :
539 : 8663846 : 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 : 8663846 : LOCK(cs);
547 [ + - ]: 8663846 : auto j{GetIter(hashb)};
548 [ + + ]: 8663846 : if (!j.has_value()) return false;
549 [ + - ]: 8657391 : auto i{GetIter(hasha)};
550 [ + + ]: 8657391 : if (!i.has_value()) return true;
551 : :
552 : 8657104 : return m_txgraph->CompareMainOrder(*i.value(), *j.value()) < 0;
553 : 8663846 : }
554 : :
555 : 164256 : std::vector<CTxMemPool::indexed_transaction_set::const_iterator> CTxMemPool::GetSortedScoreWithTopology() const
556 : : {
557 : 164256 : std::vector<indexed_transaction_set::const_iterator> iters;
558 : 164256 : AssertLockHeld(cs);
559 : :
560 [ + - ]: 164256 : iters.reserve(mapTx.size());
561 : :
562 [ + + + + ]: 18035100 : for (indexed_transaction_set::iterator mi = mapTx.begin(); mi != mapTx.end(); ++mi) {
563 [ + - ]: 8935422 : iters.push_back(mi);
564 : : }
565 : 164256 : std::sort(iters.begin(), iters.end(), [this](const auto& a, const auto& b) EXCLUSIVE_LOCKS_REQUIRED(cs) noexcept {
566 : 99646462 : return m_txgraph->CompareMainOrder(*a, *b) < 0;
567 : : });
568 : 164256 : return iters;
569 : 0 : }
570 : :
571 : 8906 : std::vector<CTxMemPoolEntryRef> CTxMemPool::entryAll() const
572 : : {
573 : 8906 : AssertLockHeld(cs);
574 : :
575 : 8906 : std::vector<CTxMemPoolEntryRef> ret;
576 [ + - ]: 8906 : ret.reserve(mapTx.size());
577 [ + - + + ]: 273789 : for (const auto& it : GetSortedScoreWithTopology()) {
578 [ + - ]: 264883 : ret.emplace_back(*it);
579 : : }
580 : 8906 : return ret;
581 : 0 : }
582 : :
583 : 942 : std::vector<TxMempoolInfo> CTxMemPool::infoAll() const
584 : : {
585 : 942 : LOCK(cs);
586 [ + - ]: 942 : auto iters = GetSortedScoreWithTopology();
587 : :
588 : 942 : std::vector<TxMempoolInfo> ret;
589 [ + - ]: 942 : ret.reserve(mapTx.size());
590 [ + + ]: 2444 : for (auto it : iters) {
591 [ + - - + ]: 3004 : ret.push_back(GetInfo(it));
592 : : }
593 : :
594 : 942 : return ret;
595 [ + - ]: 1884 : }
596 : :
597 : 4604 : const CTxMemPoolEntry* CTxMemPool::GetEntry(const Txid& txid) const
598 : : {
599 : 4604 : AssertLockHeld(cs);
600 : 4604 : const auto i = mapTx.find(txid);
601 [ + + ]: 4604 : return i == mapTx.end() ? nullptr : &(*i);
602 : : }
603 : :
604 : 206689 : CTransactionRef CTxMemPool::get(const Txid& hash) const
605 : : {
606 : 206689 : LOCK(cs);
607 [ + - ]: 206689 : indexed_transaction_set::const_iterator i = mapTx.find(hash);
608 [ + + ]: 206689 : if (i == mapTx.end())
609 : 146915 : return nullptr;
610 [ + - + - ]: 266463 : return i->GetSharedTx();
611 : 206689 : }
612 : :
613 : 768 : void CTxMemPool::PrioritiseTransaction(const Txid& hash, const CAmount& nFeeDelta)
614 : : {
615 : 768 : {
616 : 768 : LOCK(cs);
617 [ + - ]: 768 : CAmount &delta = mapDeltas[hash];
618 : 768 : delta = SaturatingAdd(delta, nFeeDelta);
619 [ + - ]: 768 : txiter it = mapTx.find(hash);
620 [ + + ]: 768 : if (it != mapTx.end()) {
621 : : // PrioritiseTransaction calls stack on previous ones. Set the new
622 : : // transaction fee to be current modified fee + feedelta.
623 : 262 : it->UpdateModifiedFee(nFeeDelta);
624 : 262 : m_txgraph->SetTransactionFee(*it, it->GetModifiedFee());
625 : 262 : ++nTransactionsUpdated;
626 : : }
627 [ + + ]: 768 : if (delta == 0) {
628 : 9 : mapDeltas.erase(hash);
629 [ + + + - : 25 : LogInfo("PrioritiseTransaction: %s (%sin mempool) delta cleared\n", hash.ToString(), it == mapTx.end() ? "not " : "");
+ - ]
630 : : } else {
631 [ + - + - : 1773 : LogInfo("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 : 768 : }
638 : 768 : }
639 : :
640 : 61899 : void CTxMemPool::ApplyDelta(const Txid& hash, CAmount &nFeeDelta) const
641 : : {
642 : 61899 : AssertLockHeld(cs);
643 : 61899 : std::map<Txid, CAmount>::const_iterator pos = mapDeltas.find(hash);
644 [ + + ]: 61899 : if (pos == mapDeltas.end())
645 : : return;
646 : 38 : const CAmount &delta = pos->second;
647 : 38 : nFeeDelta += delta;
648 : : }
649 : :
650 : 57169 : void CTxMemPool::ClearPrioritisation(const Txid& hash)
651 : : {
652 : 57169 : AssertLockHeld(cs);
653 : 57169 : mapDeltas.erase(hash);
654 : 57169 : }
655 : :
656 : 28 : std::vector<CTxMemPool::delta_info> CTxMemPool::GetPrioritisedTransactions() const
657 : : {
658 : 28 : AssertLockNotHeld(cs);
659 : 28 : LOCK(cs);
660 : 28 : std::vector<delta_info> result;
661 [ + - ]: 28 : result.reserve(mapDeltas.size());
662 [ + - + + ]: 56 : for (const auto& [txid, delta] : mapDeltas) {
663 [ + - ]: 28 : const auto iter{mapTx.find(txid)};
664 [ + + ]: 28 : const bool in_mempool{iter != mapTx.end()};
665 : 28 : std::optional<CAmount> modified_fee;
666 [ + + ]: 28 : if (in_mempool) modified_fee = iter->GetModifiedFee();
667 [ + - ]: 28 : result.emplace_back(delta_info{in_mempool, delta, modified_fee, txid});
668 : : }
669 [ + - ]: 28 : return result;
670 : 28 : }
671 : :
672 : 111357 : const CTransaction* CTxMemPool::GetConflictTx(const COutPoint& prevout) const
673 : : {
674 : 111357 : const auto it = mapNextTx.find(prevout);
675 [ + + ]: 111357 : return it == mapNextTx.end() ? nullptr : &(it->second->GetTx());
676 : : }
677 : :
678 : 11271539 : std::optional<CTxMemPool::txiter> CTxMemPool::GetIter(const Txid& txid) const
679 : : {
680 : 11271539 : AssertLockHeld(cs);
681 : 11271539 : auto it = mapTx.find(txid);
682 [ + + ]: 11271539 : return it != mapTx.end() ? std::make_optional(it) : std::nullopt;
683 : : }
684 : :
685 : 17353022 : std::optional<CTxMemPool::txiter> CTxMemPool::GetIter(const Wtxid& wtxid) const
686 : : {
687 : 17353022 : AssertLockHeld(cs);
688 [ + + ]: 17353022 : auto it{mapTx.project<0>(mapTx.get<index_by_wtxid>().find(wtxid))};
689 [ + + ]: 17353022 : return it != mapTx.end() ? std::make_optional(it) : std::nullopt;
690 : : }
691 : :
692 : 31684 : CTxMemPool::setEntries CTxMemPool::GetIterSet(const std::set<Txid>& hashes) const
693 : : {
694 : 31684 : CTxMemPool::setEntries ret;
695 [ + + ]: 33955 : for (const auto& h : hashes) {
696 [ + - ]: 2271 : const auto mi = GetIter(h);
697 [ + - + - ]: 2271 : if (mi) ret.insert(*mi);
698 : : }
699 : 31684 : return ret;
700 : 0 : }
701 : :
702 : 2 : std::vector<CTxMemPool::txiter> CTxMemPool::GetIterVec(const std::vector<Txid>& txids) const
703 : : {
704 : 2 : AssertLockHeld(cs);
705 : 2 : std::vector<txiter> ret;
706 [ - + + - ]: 2 : ret.reserve(txids.size());
707 [ + + ]: 565 : for (const auto& txid : txids) {
708 [ + - ]: 563 : const auto it{GetIter(txid)};
709 [ - + ]: 563 : if (!it) return {};
710 [ + - ]: 563 : ret.push_back(*it);
711 : : }
712 : 2 : return ret;
713 : 2 : }
714 : :
715 : 23846 : bool CTxMemPool::HasNoInputsOf(const CTransaction &tx) const
716 : : {
717 [ - + + + ]: 54394 : for (unsigned int i = 0; i < tx.vin.size(); i++)
718 [ + + ]: 33803 : if (exists(tx.vin[i].prevout.hash))
719 : : return false;
720 : : return true;
721 : : }
722 : :
723 [ + - + - ]: 39630 : CCoinsViewMemPool::CCoinsViewMemPool(CCoinsView* baseIn, const CTxMemPool& mempoolIn) : CCoinsViewBacked(baseIn), mempool(mempoolIn) { }
724 : :
725 : 62817 : 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 [ + + ]: 62817 : if (auto it = m_temp_added.find(outpoint); it != m_temp_added.end()) {
730 : 594 : 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 : 62223 : CTransactionRef ptx = mempool.get(outpoint.hash);
737 [ + + ]: 62223 : if (ptx) {
738 [ - + + - ]: 8270 : if (outpoint.n < ptx->vout.size()) {
739 : 8270 : Coin coin(ptx->vout[outpoint.n], MEMPOOL_HEIGHT, false);
740 [ + - ]: 8270 : m_non_base_coins.emplace(outpoint);
741 : 8270 : return coin;
742 : 8270 : }
743 : 0 : return std::nullopt;
744 : : }
745 [ + - ]: 53953 : return base->GetCoin(outpoint);
746 : 62223 : }
747 : :
748 : 753 : void CCoinsViewMemPool::PackageAddTransaction(const CTransactionRef& tx)
749 : : {
750 [ - + + + ]: 1537 : for (unsigned int n = 0; n < tx->vout.size(); ++n) {
751 [ + - ]: 784 : m_temp_added.emplace(COutPoint(tx->GetHash(), n), Coin(tx->vout[n], MEMPOOL_HEIGHT, false));
752 : 784 : m_non_base_coins.emplace(tx->GetHash(), n);
753 : : }
754 : 753 : }
755 : 61385 : void CCoinsViewMemPool::Reset()
756 : : {
757 : 61385 : m_temp_added.clear();
758 : 61385 : m_non_base_coins.clear();
759 : 61385 : }
760 : :
761 : 528447 : size_t CTxMemPool::DynamicMemoryUsage() const {
762 : 528447 : 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 [ - + + - ]: 1056894 : 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 : 528447 : }
766 : :
767 : 58793 : void CTxMemPool::RemoveUnbroadcastTx(const Txid& txid, const bool unchecked) {
768 : 58793 : LOCK(cs);
769 : :
770 [ + + ]: 58793 : if (m_unbroadcast_txids.erase(txid))
771 : : {
772 [ + - + - : 27563 : LogDebug(BCLog::MEMPOOL, "Removed %i from set of unbroadcast txns%s\n", txid.GetHex(), (unchecked ? " before confirmation that txn was sent out" : ""));
+ + + - +
- ]
773 : : }
774 : 58793 : }
775 : :
776 : 76559 : void CTxMemPool::RemoveStaged(setEntries &stage, MemPoolRemovalReason reason) {
777 : 76559 : AssertLockHeld(cs);
778 [ + + ]: 78093 : for (txiter it : stage) {
779 : 1534 : removeUnchecked(it, reason);
780 : : }
781 : 76559 : }
782 : :
783 : 3391 : bool CTxMemPool::CheckPolicyLimits(const CTransactionRef& tx)
784 : : {
785 : 3391 : 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 [ + - ]: 3391 : auto changeset = GetChangeSet();
790 [ + - ]: 3391 : (void) changeset->StageAddition(tx, /*fee=*/0, /*time=*/0, /*entry_height=*/0, /*entry_sequence=*/0, /*spends_coinbase=*/false, /*sigops_cost=*/0, LockPoints{});
791 [ + - ]: 3391 : return changeset->CheckMemPoolPolicyLimits();
792 [ + - ]: 6782 : }
793 : :
794 : 26184 : int CTxMemPool::Expire(std::chrono::seconds time)
795 : : {
796 : 26184 : AssertLockHeld(cs);
797 : 26184 : Assume(!m_have_changeset);
798 : 26184 : indexed_transaction_set::index<entry_time>::type::iterator it = mapTx.get<entry_time>().begin();
799 : 26184 : setEntries toremove;
800 [ + + + + ]: 26188 : while (it != mapTx.get<entry_time>().end() && it->GetTime() < time) {
801 [ + - ]: 4 : toremove.insert(mapTx.project<0>(it));
802 : 4 : it++;
803 : : }
804 : 26184 : setEntries stage;
805 [ + + ]: 26188 : for (txiter removeit : toremove) {
806 [ + - ]: 4 : CalculateDescendants(removeit, stage);
807 : : }
808 [ + - ]: 26184 : RemoveStaged(stage, MemPoolRemovalReason::EXPIRY);
809 : 26184 : return stage.size();
810 : 26184 : }
811 : :
812 : 469297 : CFeeRate CTxMemPool::GetMinFee(size_t sizelimit) const {
813 : 469297 : LOCK(cs);
814 [ + + + + ]: 469297 : if (!blockSinceLastRollingFeeBump || rollingMinimumFeeRate == 0)
815 : 469240 : return CFeeRate(llround(rollingMinimumFeeRate));
816 : :
817 [ + - ]: 57 : int64_t time = GetTime();
818 [ + + ]: 57 : if (time > lastRollingFeeUpdate + 10) {
819 : 6 : double halflife = ROLLING_FEE_HALFLIFE;
820 [ + - + + ]: 6 : if (DynamicMemoryUsage() < sizelimit / 4)
821 : : halflife /= 4;
822 [ + - + + ]: 5 : else if (DynamicMemoryUsage() < sizelimit / 2)
823 : 1 : halflife /= 2;
824 : :
825 : 6 : rollingMinimumFeeRate = rollingMinimumFeeRate / pow(2.0, (time - lastRollingFeeUpdate) / halflife);
826 : 6 : lastRollingFeeUpdate = time;
827 : :
828 [ + + ]: 6 : if (rollingMinimumFeeRate < (double)m_opts.incremental_relay_feerate.GetFeePerK() / 2) {
829 : 1 : rollingMinimumFeeRate = 0;
830 : 1 : return CFeeRate(0);
831 : : }
832 : : }
833 : 56 : return std::max(CFeeRate(llround(rollingMinimumFeeRate)), m_opts.incremental_relay_feerate);
834 : 469297 : }
835 : :
836 : 55 : void CTxMemPool::trackPackageRemoved(const CFeeRate& rate) {
837 : 55 : AssertLockHeld(cs);
838 [ + + ]: 55 : if (rate.GetFeePerK() > rollingMinimumFeeRate) {
839 : 53 : rollingMinimumFeeRate = rate.GetFeePerK();
840 : 53 : blockSinceLastRollingFeeBump = false;
841 : : }
842 : 55 : }
843 : :
844 : 26193 : void CTxMemPool::TrimToSize(size_t sizelimit, std::vector<COutPoint>* pvNoSpendsRemaining) {
845 : 26193 : AssertLockHeld(cs);
846 : 26193 : Assume(!m_have_changeset);
847 : :
848 : 26193 : unsigned nTxnRemoved = 0;
849 : 26193 : CFeeRate maxFeeRateRemoved(0);
850 : :
851 [ + + + + ]: 26248 : while (!mapTx.empty() && DynamicMemoryUsage() > sizelimit) {
852 [ + - ]: 55 : const auto &[worst_chunk, feeperweight] = m_txgraph->GetWorstMainChunk();
853 [ + - ]: 55 : FeePerVSize feerate = ToFeePerVSize(feeperweight);
854 [ + - ]: 55 : 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 : 55 : removed += m_opts.incremental_relay_feerate;
861 [ + - ]: 55 : trackPackageRemoved(removed);
862 : 55 : maxFeeRateRemoved = std::max(maxFeeRateRemoved, removed);
863 : :
864 [ - + ]: 55 : nTxnRemoved += worst_chunk.size();
865 : :
866 : 55 : std::vector<CTransaction> txn;
867 [ + + ]: 55 : if (pvNoSpendsRemaining) {
868 [ + - ]: 47 : txn.reserve(worst_chunk.size());
869 [ + + ]: 95 : for (auto ref : worst_chunk) {
870 [ + - ]: 48 : txn.emplace_back(static_cast<const CTxMemPoolEntry&>(*ref).GetTx());
871 : : }
872 : : }
873 : :
874 : 55 : setEntries stage;
875 [ + + ]: 116 : for (auto ref : worst_chunk) {
876 [ + - ]: 61 : stage.insert(mapTx.iterator_to(static_cast<const CTxMemPoolEntry&>(*ref)));
877 : : }
878 [ + + ]: 116 : for (auto e : stage) {
879 [ + - ]: 61 : removeUnchecked(e, MemPoolRemovalReason::SIZELIMIT);
880 : : }
881 [ + + ]: 55 : if (pvNoSpendsRemaining) {
882 [ + + ]: 95 : for (const CTransaction& tx : txn) {
883 [ + + ]: 96 : for (const CTxIn& txin : tx.vin) {
884 [ + - + + ]: 48 : if (exists(txin.prevout.hash)) continue;
885 [ + - ]: 47 : pvNoSpendsRemaining->push_back(txin.prevout);
886 : : }
887 : : }
888 : : }
889 : 110 : }
890 : :
891 [ + + ]: 26193 : if (maxFeeRateRemoved > CFeeRate(0)) {
892 [ + - + - ]: 88 : LogDebug(BCLog::MEMPOOL, "Removed %u txn, rolling minimum fee bumped to %s\n", nTxnRemoved, maxFeeRateRemoved.ToString());
893 : : }
894 : 26193 : }
895 : :
896 : 125115 : std::tuple<size_t, size_t, CAmount> CTxMemPool::CalculateAncestorData(const CTxMemPoolEntry& entry) const
897 : : {
898 : 125115 : auto ancestors = m_txgraph->GetAncestors(entry, TxGraph::Level::MAIN);
899 : :
900 [ - + ]: 125115 : size_t ancestor_count = ancestors.size();
901 : 125115 : size_t ancestor_size = 0;
902 : 125115 : CAmount ancestor_fees = 0;
903 [ + + ]: 444842 : for (auto tx: ancestors) {
904 : 319727 : const CTxMemPoolEntry& anc = static_cast<const CTxMemPoolEntry&>(*tx);
905 [ + - ]: 319727 : ancestor_size += anc.GetTxSize();
906 : 319727 : ancestor_fees += anc.GetModifiedFee();
907 : : }
908 : 125115 : return {ancestor_count, ancestor_size, ancestor_fees};
909 : 125115 : }
910 : :
911 : 9253 : std::tuple<size_t, size_t, CAmount> CTxMemPool::CalculateDescendantData(const CTxMemPoolEntry& entry) const
912 : : {
913 : 9253 : auto descendants = m_txgraph->GetDescendants(entry, TxGraph::Level::MAIN);
914 [ - + ]: 9253 : size_t descendant_count = descendants.size();
915 : 9253 : size_t descendant_size = 0;
916 : 9253 : CAmount descendant_fees = 0;
917 : :
918 [ + + ]: 164285 : for (auto tx: descendants) {
919 : 155032 : const CTxMemPoolEntry &desc = static_cast<const CTxMemPoolEntry&>(*tx);
920 [ + - ]: 155032 : descendant_size += desc.GetTxSize();
921 : 155032 : descendant_fees += desc.GetModifiedFee();
922 : : }
923 : 9253 : return {descendant_count, descendant_size, descendant_fees};
924 : 9253 : }
925 : :
926 : 580795 : void CTxMemPool::GetTransactionAncestry(const Txid& txid, size_t& ancestors, size_t& cluster_count, size_t* const ancestorsize, CAmount* const ancestorfees) const {
927 : 580795 : LOCK(cs);
928 [ + - ]: 580795 : auto it = mapTx.find(txid);
929 : 580795 : ancestors = cluster_count = 0;
930 [ + + ]: 580795 : if (it != mapTx.end()) {
931 [ + - + + ]: 47786 : auto [ancestor_count, ancestor_size, ancestor_fees] = CalculateAncestorData(*it);
932 : 47786 : ancestors = ancestor_count;
933 [ + + ]: 47786 : if (ancestorsize) *ancestorsize = ancestor_size;
934 [ + + ]: 47786 : if (ancestorfees) *ancestorfees = ancestor_fees;
935 [ - + ]: 47786 : cluster_count = m_txgraph->GetCluster(*it, TxGraph::Level::MAIN).size();
936 : : }
937 : 580795 : }
938 : :
939 : 2334 : bool CTxMemPool::GetLoadTried() const
940 : : {
941 : 2334 : LOCK(cs);
942 [ + - ]: 2334 : return m_load_tried;
943 : 2334 : }
944 : :
945 : 1021 : void CTxMemPool::SetLoadTried(bool load_tried)
946 : : {
947 : 1021 : LOCK(cs);
948 [ + - ]: 1021 : m_load_tried = load_tried;
949 : 1021 : }
950 : :
951 : 3045 : std::vector<CTxMemPool::txiter> CTxMemPool::GatherClusters(const std::vector<Txid>& txids) const
952 : : {
953 : 3045 : AssertLockHeld(cs);
954 : :
955 : 3045 : std::vector<CTxMemPool::txiter> ret;
956 : 3045 : std::set<const CTxMemPoolEntry*> unique_cluster_representatives;
957 [ + + ]: 52689 : for (auto txid : txids) {
958 [ + - ]: 49644 : auto it = mapTx.find(txid);
959 [ + - ]: 49644 : 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 : 49644 : auto cluster = m_txgraph->GetCluster(*it, TxGraph::Level::MAIN);
964 [ + - + + ]: 49644 : if (unique_cluster_representatives.insert(static_cast<const CTxMemPoolEntry*>(&(**cluster.begin()))).second) {
965 [ + + ]: 118923 : for (auto tx : cluster) {
966 [ + - ]: 69442 : ret.emplace_back(mapTx.iterator_to(static_cast<const CTxMemPoolEntry&>(*tx)));
967 : : }
968 : : }
969 : 49644 : }
970 : : }
971 [ - + + + ]: 3045 : if (ret.size() > 500) {
972 : 1 : return {};
973 : : }
974 : 3044 : return ret;
975 : 3045 : }
976 : :
977 : 1281 : util::Result<std::pair<std::vector<FeeFrac>, std::vector<FeeFrac>>> CTxMemPool::ChangeSet::CalculateChunksForRBF()
978 : : {
979 : 1281 : LOCK(m_pool->cs);
980 : :
981 [ + - - + ]: 1281 : if (!CheckMemPoolPolicyLimits()) {
982 [ # # # # ]: 0 : return util::Error{Untranslated("cluster size limit exceeded")};
983 : : }
984 : :
985 : 2562 : return m_pool->m_txgraph->GetMainStagingDiagrams();
986 : 1281 : }
987 : :
988 : 61899 : 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 : 61899 : LOCK(m_pool->cs);
991 [ + - + - ]: 61899 : Assume(m_to_add.find(tx->GetHash()) == m_to_add.end());
992 : 61899 : Assume(!m_dependencies_processed);
993 : :
994 : : // We need to process dependencies after adding a new transaction.
995 : 61899 : m_dependencies_processed = false;
996 : :
997 : 61899 : CAmount delta{0};
998 [ + - ]: 61899 : m_pool->ApplyDelta(tx->GetHash(), delta);
999 : :
1000 [ + - ]: 61899 : TxGraph::Ref ref(m_pool->m_txgraph->AddTransaction(FeePerWeight(fee, GetSigOpsAdjustedWeight(GetTransactionWeight(*tx), sigops_cost, ::nBytesPerSigOp))));
1001 [ + - ]: 61899 : auto newit = m_to_add.emplace(std::move(ref), tx, fee, time, entry_height, entry_sequence, spends_coinbase, sigops_cost, lp).first;
1002 [ + + ]: 61899 : if (delta) {
1003 : 38 : newit->UpdateModifiedFee(delta);
1004 : 38 : m_pool->m_txgraph->SetTransactionFee(*newit, newit->GetModifiedFee());
1005 : : }
1006 : :
1007 [ + - ]: 61899 : m_entry_vec.push_back(newit);
1008 : :
1009 : 123798 : return newit;
1010 [ + - ]: 123798 : }
1011 : :
1012 : 2123 : void CTxMemPool::ChangeSet::StageRemoval(CTxMemPool::txiter it)
1013 : : {
1014 : 2123 : LOCK(m_pool->cs);
1015 : 2123 : m_pool->m_txgraph->RemoveTransaction(*it);
1016 [ + - ]: 2123 : m_to_remove.insert(it);
1017 : 2123 : }
1018 : :
1019 : 50375 : void CTxMemPool::ChangeSet::Apply()
1020 : : {
1021 : 50375 : LOCK(m_pool->cs);
1022 [ + + ]: 50375 : if (!m_dependencies_processed) {
1023 [ + - ]: 3 : ProcessDependencies();
1024 : : }
1025 [ + - ]: 50375 : m_pool->Apply(this);
1026 : 50375 : m_to_add.clear();
1027 : 50375 : m_to_remove.clear();
1028 [ + - ]: 50375 : m_entry_vec.clear();
1029 [ + - ]: 50375 : m_ancestors.clear();
1030 : 50375 : }
1031 : :
1032 : 60966 : void CTxMemPool::ChangeSet::ProcessDependencies()
1033 : : {
1034 : 60966 : LOCK(m_pool->cs);
1035 : 60966 : Assume(!m_dependencies_processed); // should only call this once.
1036 [ + + ]: 122504 : for (const auto& entryptr : m_entry_vec) {
1037 [ + - + - : 272173 : for (const auto &txin : entryptr->GetSharedTx()->vin) {
+ + ]
1038 [ + - ]: 87559 : std::optional<txiter> piter = m_pool->GetIter(txin.prevout.hash);
1039 [ + + ]: 87559 : if (!piter) {
1040 [ + - ]: 77792 : auto it = m_to_add.find(txin.prevout.hash);
1041 [ + + ]: 77792 : if (it != m_to_add.end()) {
1042 : 565 : piter = std::make_optional(it);
1043 : : }
1044 : : }
1045 [ + + ]: 87559 : if (piter) {
1046 : 10332 : m_pool->m_txgraph->AddDependency(/*parent=*/**piter, /*child=*/*entryptr);
1047 : : }
1048 : : }
1049 : : }
1050 : 60966 : m_dependencies_processed = true;
1051 [ + - ]: 60966 : return;
1052 : 60966 : }
1053 : :
1054 : 63496 : bool CTxMemPool::ChangeSet::CheckMemPoolPolicyLimits()
1055 : : {
1056 : 63496 : LOCK(m_pool->cs);
1057 [ + + ]: 63496 : if (!m_dependencies_processed) {
1058 [ + - ]: 60963 : ProcessDependencies();
1059 : : }
1060 : :
1061 [ + - ]: 63496 : return !m_pool->m_txgraph->IsOversized(TxGraph::Level::TOP);
1062 : 63496 : }
1063 : :
1064 : 154413 : std::vector<FeePerWeight> CTxMemPool::GetFeerateDiagram() const
1065 : : {
1066 : 154413 : FeePerWeight zero{};
1067 : 154413 : std::vector<FeePerWeight> ret;
1068 : :
1069 [ + - ]: 154413 : ret.emplace_back(zero);
1070 : :
1071 : 154413 : StartBlockBuilding();
1072 : :
1073 : 154413 : std::vector<CTxMemPoolEntry::CTxMemPoolEntryRef> dummy;
1074 : :
1075 [ + - ]: 154413 : FeePerWeight last_selection = GetBlockBuilderChunk(dummy);
1076 [ + + ]: 8807889 : while (last_selection != FeePerWeight{}) {
1077 [ + - ]: 8653476 : last_selection += ret.back();
1078 [ + - ]: 8653476 : ret.emplace_back(last_selection);
1079 : 8653476 : IncludeBuilderChunk();
1080 [ + - ]: 8653476 : last_selection = GetBlockBuilderChunk(dummy);
1081 : : }
1082 : 154413 : StopBlockBuilding();
1083 : 154413 : return ret;
1084 : 154413 : }
|
