/workdir/bitcoin/src/txmempool.cpp
Line | Count | Source (jump to first uncovered line) |
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 | | bool TestLockPointValidity(CChain& active_chain, const LockPoints& lp) |
38 | 0 | { |
39 | 0 | AssertLockHeld(cs_main); |
40 | | // If there are relative lock times then the maxInputBlock will be set |
41 | | // If there are no relative lock times, the LockPoints don't depend on the chain |
42 | 0 | if (lp.maxInputBlock) { Branch (42:9): [True: 0, False: 0]
|
43 | | // Check whether active_chain is an extension of the block at which the LockPoints |
44 | | // calculation was valid. If not LockPoints are no longer valid |
45 | 0 | if (!active_chain.Contains(lp.maxInputBlock)) { Branch (45:13): [True: 0, False: 0]
|
46 | 0 | return false; |
47 | 0 | } |
48 | 0 | } |
49 | | |
50 | | // LockPoints still valid |
51 | 0 | return true; |
52 | 0 | } |
53 | | |
54 | | void CTxMemPool::UpdateForDescendants(txiter updateIt, cacheMap& cachedDescendants, |
55 | | const std::set<uint256>& setExclude, std::set<uint256>& descendants_to_remove) |
56 | 0 | { |
57 | 0 | CTxMemPoolEntry::Children stageEntries, descendants; |
58 | 0 | stageEntries = updateIt->GetMemPoolChildrenConst(); |
59 | |
|
60 | 0 | while (!stageEntries.empty()) { Branch (60:12): [True: 0, False: 0]
|
61 | 0 | const CTxMemPoolEntry& descendant = *stageEntries.begin(); |
62 | 0 | descendants.insert(descendant); |
63 | 0 | stageEntries.erase(descendant); |
64 | 0 | const CTxMemPoolEntry::Children& children = descendant.GetMemPoolChildrenConst(); |
65 | 0 | for (const CTxMemPoolEntry& childEntry : children) { Branch (65:48): [True: 0, False: 0]
|
66 | 0 | cacheMap::iterator cacheIt = cachedDescendants.find(mapTx.iterator_to(childEntry)); |
67 | 0 | if (cacheIt != cachedDescendants.end()) { Branch (67:17): [True: 0, False: 0]
|
68 | | // We've already calculated this one, just add the entries for this set |
69 | | // but don't traverse again. |
70 | 0 | for (txiter cacheEntry : cacheIt->second) { Branch (70:40): [True: 0, False: 0]
|
71 | 0 | descendants.insert(*cacheEntry); |
72 | 0 | } |
73 | 0 | } else if (!descendants.count(childEntry)) { Branch (73:24): [True: 0, False: 0]
|
74 | | // Schedule for later processing |
75 | 0 | stageEntries.insert(childEntry); |
76 | 0 | } |
77 | 0 | } |
78 | 0 | } |
79 | | // descendants now contains all in-mempool descendants of updateIt. |
80 | | // Update and add to cached descendant map |
81 | 0 | int32_t modifySize = 0; |
82 | 0 | CAmount modifyFee = 0; |
83 | 0 | int64_t modifyCount = 0; |
84 | 0 | for (const CTxMemPoolEntry& descendant : descendants) { Branch (84:44): [True: 0, False: 0]
|
85 | 0 | if (!setExclude.count(descendant.GetTx().GetHash())) { Branch (85:13): [True: 0, False: 0]
|
86 | 0 | modifySize += descendant.GetTxSize(); |
87 | 0 | modifyFee += descendant.GetModifiedFee(); |
88 | 0 | modifyCount++; |
89 | 0 | cachedDescendants[updateIt].insert(mapTx.iterator_to(descendant)); |
90 | | // Update ancestor state for each descendant |
91 | 0 | mapTx.modify(mapTx.iterator_to(descendant), [=](CTxMemPoolEntry& e) { |
92 | 0 | e.UpdateAncestorState(updateIt->GetTxSize(), updateIt->GetModifiedFee(), 1, updateIt->GetSigOpCost()); |
93 | 0 | }); |
94 | | // Don't directly remove the transaction here -- doing so would |
95 | | // invalidate iterators in cachedDescendants. Mark it for removal |
96 | | // by inserting into descendants_to_remove. |
97 | 0 | if (descendant.GetCountWithAncestors() > uint64_t(m_opts.limits.ancestor_count) || descendant.GetSizeWithAncestors() > m_opts.limits.ancestor_size_vbytes) { Branch (97:17): [True: 0, False: 0]
Branch (97:96): [True: 0, False: 0]
|
98 | 0 | descendants_to_remove.insert(descendant.GetTx().GetHash()); |
99 | 0 | } |
100 | 0 | } |
101 | 0 | } |
102 | 0 | mapTx.modify(updateIt, [=](CTxMemPoolEntry& e) { e.UpdateDescendantState(modifySize, modifyFee, modifyCount); }); |
103 | 0 | } |
104 | | |
105 | | void CTxMemPool::UpdateTransactionsFromBlock(const std::vector<uint256>& vHashesToUpdate) |
106 | 0 | { |
107 | 0 | AssertLockHeld(cs); |
108 | | // For each entry in vHashesToUpdate, store the set of in-mempool, but not |
109 | | // in-vHashesToUpdate transactions, so that we don't have to recalculate |
110 | | // descendants when we come across a previously seen entry. |
111 | 0 | cacheMap mapMemPoolDescendantsToUpdate; |
112 | | |
113 | | // Use a set for lookups into vHashesToUpdate (these entries are already |
114 | | // accounted for in the state of their ancestors) |
115 | 0 | std::set<uint256> setAlreadyIncluded(vHashesToUpdate.begin(), vHashesToUpdate.end()); |
116 | |
|
117 | 0 | std::set<uint256> descendants_to_remove; |
118 | | |
119 | | // Iterate in reverse, so that whenever we are looking at a transaction |
120 | | // we are sure that all in-mempool descendants have already been processed. |
121 | | // This maximizes the benefit of the descendant cache and guarantees that |
122 | | // CTxMemPoolEntry::m_children will be updated, an assumption made in |
123 | | // UpdateForDescendants. |
124 | 0 | for (const uint256& hash : vHashesToUpdate | std::views::reverse) { Branch (124:30): [True: 0, False: 0]
|
125 | | // calculate children from mapNextTx |
126 | 0 | txiter it = mapTx.find(hash); |
127 | 0 | if (it == mapTx.end()) { Branch (127:13): [True: 0, False: 0]
|
128 | 0 | continue; |
129 | 0 | } |
130 | 0 | auto iter = mapNextTx.lower_bound(COutPoint(Txid::FromUint256(hash), 0)); |
131 | | // First calculate the children, and update CTxMemPoolEntry::m_children to |
132 | | // include them, and update their CTxMemPoolEntry::m_parents to include this tx. |
133 | | // we cache the in-mempool children to avoid duplicate updates |
134 | 0 | { |
135 | 0 | WITH_FRESH_EPOCH(m_epoch); |
136 | 0 | for (; iter != mapNextTx.end() && iter->first->hash == hash; ++iter) { Branch (136:20): [True: 0, False: 0]
Branch (136:20): [True: 0, False: 0]
Branch (136:47): [True: 0, False: 0]
|
137 | 0 | const uint256 &childHash = iter->second->GetHash(); |
138 | 0 | txiter childIter = mapTx.find(childHash); |
139 | 0 | assert(childIter != mapTx.end()); |
140 | | // We can skip updating entries we've encountered before or that |
141 | | // are in the block (which are already accounted for). |
142 | 0 | if (!visited(childIter) && !setAlreadyIncluded.count(childHash)) { Branch (142:21): [True: 0, False: 0]
Branch (142:44): [True: 0, False: 0]
|
143 | 0 | UpdateChild(it, childIter, true); |
144 | 0 | UpdateParent(childIter, it, true); |
145 | 0 | } |
146 | 0 | } |
147 | 0 | } // release epoch guard for UpdateForDescendants |
148 | 0 | UpdateForDescendants(it, mapMemPoolDescendantsToUpdate, setAlreadyIncluded, descendants_to_remove); |
149 | 0 | } |
150 | | |
151 | 0 | for (const auto& txid : descendants_to_remove) { Branch (151:27): [True: 0, False: 0]
|
152 | | // This txid may have been removed already in a prior call to removeRecursive. |
153 | | // Therefore we ensure it is not yet removed already. |
154 | 0 | if (const std::optional<txiter> txiter = GetIter(txid)) { Branch (154:41): [True: 0, False: 0]
|
155 | 0 | removeRecursive((*txiter)->GetTx(), MemPoolRemovalReason::SIZELIMIT); |
156 | 0 | } |
157 | 0 | } |
158 | 0 | } |
159 | | |
160 | | util::Result<CTxMemPool::setEntries> CTxMemPool::CalculateAncestorsAndCheckLimits( |
161 | | int64_t entry_size, |
162 | | size_t entry_count, |
163 | | CTxMemPoolEntry::Parents& staged_ancestors, |
164 | | const Limits& limits) const |
165 | 0 | { |
166 | 0 | int64_t totalSizeWithAncestors = entry_size; |
167 | 0 | setEntries ancestors; |
168 | |
|
169 | 0 | while (!staged_ancestors.empty()) { Branch (169:12): [True: 0, False: 0]
|
170 | 0 | const CTxMemPoolEntry& stage = staged_ancestors.begin()->get(); |
171 | 0 | txiter stageit = mapTx.iterator_to(stage); |
172 | |
|
173 | 0 | ancestors.insert(stageit); |
174 | 0 | staged_ancestors.erase(stage); |
175 | 0 | totalSizeWithAncestors += stageit->GetTxSize(); |
176 | |
|
177 | 0 | if (stageit->GetSizeWithDescendants() + entry_size > limits.descendant_size_vbytes) { Branch (177:13): [True: 0, False: 0]
|
178 | 0 | return util::Error{Untranslated(strprintf("exceeds descendant size limit for tx %s [limit: %u]", stageit->GetTx().GetHash().ToString(), limits.descendant_size_vbytes))}; |
179 | 0 | } else if (stageit->GetCountWithDescendants() + entry_count > static_cast<uint64_t>(limits.descendant_count)) { Branch (179:20): [True: 0, False: 0]
|
180 | 0 | return util::Error{Untranslated(strprintf("too many descendants for tx %s [limit: %u]", stageit->GetTx().GetHash().ToString(), limits.descendant_count))}; |
181 | 0 | } else if (totalSizeWithAncestors > limits.ancestor_size_vbytes) { Branch (181:20): [True: 0, False: 0]
|
182 | 0 | return util::Error{Untranslated(strprintf("exceeds ancestor size limit [limit: %u]", limits.ancestor_size_vbytes))}; |
183 | 0 | } |
184 | | |
185 | 0 | const CTxMemPoolEntry::Parents& parents = stageit->GetMemPoolParentsConst(); |
186 | 0 | for (const CTxMemPoolEntry& parent : parents) { Branch (186:44): [True: 0, False: 0]
|
187 | 0 | txiter parent_it = mapTx.iterator_to(parent); |
188 | | |
189 | | // If this is a new ancestor, add it. |
190 | 0 | if (ancestors.count(parent_it) == 0) { Branch (190:17): [True: 0, False: 0]
|
191 | 0 | staged_ancestors.insert(parent); |
192 | 0 | } |
193 | 0 | if (staged_ancestors.size() + ancestors.size() + entry_count > static_cast<uint64_t>(limits.ancestor_count)) { Branch (193:17): [True: 0, False: 0]
|
194 | 0 | return util::Error{Untranslated(strprintf("too many unconfirmed ancestors [limit: %u]", limits.ancestor_count))}; |
195 | 0 | } |
196 | 0 | } |
197 | 0 | } |
198 | | |
199 | 0 | return ancestors; |
200 | 0 | } |
201 | | |
202 | | util::Result<void> CTxMemPool::CheckPackageLimits(const Package& package, |
203 | | const int64_t total_vsize) const |
204 | 0 | { |
205 | 0 | size_t pack_count = package.size(); |
206 | | |
207 | | // Package itself is busting mempool limits; should be rejected even if no staged_ancestors exist |
208 | 0 | if (pack_count > static_cast<uint64_t>(m_opts.limits.ancestor_count)) { Branch (208:9): [True: 0, False: 0]
|
209 | 0 | return util::Error{Untranslated(strprintf("package count %u exceeds ancestor count limit [limit: %u]", pack_count, m_opts.limits.ancestor_count))}; |
210 | 0 | } else if (pack_count > static_cast<uint64_t>(m_opts.limits.descendant_count)) { Branch (210:16): [True: 0, False: 0]
|
211 | 0 | return util::Error{Untranslated(strprintf("package count %u exceeds descendant count limit [limit: %u]", pack_count, m_opts.limits.descendant_count))}; |
212 | 0 | } else if (total_vsize > m_opts.limits.ancestor_size_vbytes) { Branch (212:16): [True: 0, False: 0]
|
213 | 0 | return util::Error{Untranslated(strprintf("package size %u exceeds ancestor size limit [limit: %u]", total_vsize, m_opts.limits.ancestor_size_vbytes))}; |
214 | 0 | } else if (total_vsize > m_opts.limits.descendant_size_vbytes) { Branch (214:16): [True: 0, False: 0]
|
215 | 0 | return util::Error{Untranslated(strprintf("package size %u exceeds descendant size limit [limit: %u]", total_vsize, m_opts.limits.descendant_size_vbytes))}; |
216 | 0 | } |
217 | | |
218 | 0 | CTxMemPoolEntry::Parents staged_ancestors; |
219 | 0 | for (const auto& tx : package) { Branch (219:25): [True: 0, False: 0]
|
220 | 0 | for (const auto& input : tx->vin) { Branch (220:32): [True: 0, False: 0]
|
221 | 0 | std::optional<txiter> piter = GetIter(input.prevout.hash); |
222 | 0 | if (piter) { Branch (222:17): [True: 0, False: 0]
|
223 | 0 | staged_ancestors.insert(**piter); |
224 | 0 | if (staged_ancestors.size() + package.size() > static_cast<uint64_t>(m_opts.limits.ancestor_count)) { Branch (224:21): [True: 0, False: 0]
|
225 | 0 | return util::Error{Untranslated(strprintf("too many unconfirmed parents [limit: %u]", m_opts.limits.ancestor_count))}; |
226 | 0 | } |
227 | 0 | } |
228 | 0 | } |
229 | 0 | } |
230 | | // When multiple transactions are passed in, the ancestors and descendants of all transactions |
231 | | // considered together must be within limits even if they are not interdependent. This may be |
232 | | // stricter than the limits for each individual transaction. |
233 | 0 | const auto ancestors{CalculateAncestorsAndCheckLimits(total_vsize, package.size(), |
234 | 0 | staged_ancestors, m_opts.limits)}; |
235 | | // It's possible to overestimate the ancestor/descendant totals. |
236 | 0 | if (!ancestors.has_value()) return util::Error{Untranslated("possibly " + util::ErrorString(ancestors).original)}; Branch (236:9): [True: 0, False: 0]
|
237 | 0 | return {}; |
238 | 0 | } |
239 | | |
240 | | util::Result<CTxMemPool::setEntries> CTxMemPool::CalculateMemPoolAncestors( |
241 | | const CTxMemPoolEntry &entry, |
242 | | const Limits& limits, |
243 | | bool fSearchForParents /* = true */) const |
244 | 0 | { |
245 | 0 | CTxMemPoolEntry::Parents staged_ancestors; |
246 | 0 | const CTransaction &tx = entry.GetTx(); |
247 | |
|
248 | 0 | if (fSearchForParents) { Branch (248:9): [True: 0, False: 0]
|
249 | | // Get parents of this transaction that are in the mempool |
250 | | // GetMemPoolParents() is only valid for entries in the mempool, so we |
251 | | // iterate mapTx to find parents. |
252 | 0 | for (unsigned int i = 0; i < tx.vin.size(); i++) { Branch (252:34): [True: 0, False: 0]
|
253 | 0 | std::optional<txiter> piter = GetIter(tx.vin[i].prevout.hash); |
254 | 0 | if (piter) { Branch (254:17): [True: 0, False: 0]
|
255 | 0 | staged_ancestors.insert(**piter); |
256 | 0 | if (staged_ancestors.size() + 1 > static_cast<uint64_t>(limits.ancestor_count)) { Branch (256:21): [True: 0, False: 0]
|
257 | 0 | return util::Error{Untranslated(strprintf("too many unconfirmed parents [limit: %u]", limits.ancestor_count))}; |
258 | 0 | } |
259 | 0 | } |
260 | 0 | } |
261 | 0 | } else { |
262 | | // If we're not searching for parents, we require this to already be an |
263 | | // entry in the mempool and use the entry's cached parents. |
264 | 0 | txiter it = mapTx.iterator_to(entry); |
265 | 0 | staged_ancestors = it->GetMemPoolParentsConst(); |
266 | 0 | } |
267 | | |
268 | 0 | return CalculateAncestorsAndCheckLimits(entry.GetTxSize(), /*entry_count=*/1, staged_ancestors, |
269 | 0 | limits); |
270 | 0 | } |
271 | | |
272 | | CTxMemPool::setEntries CTxMemPool::AssumeCalculateMemPoolAncestors( |
273 | | std::string_view calling_fn_name, |
274 | | const CTxMemPoolEntry &entry, |
275 | | const Limits& limits, |
276 | | bool fSearchForParents /* = true */) const |
277 | 0 | { |
278 | 0 | auto result{CalculateMemPoolAncestors(entry, limits, fSearchForParents)}; |
279 | 0 | if (!Assume(result)) { Branch (279:9): [True: 0, False: 0]
|
280 | 0 | LogPrintLevel(BCLog::MEMPOOL, BCLog::Level::Error, "%s: CalculateMemPoolAncestors failed unexpectedly, continuing with empty ancestor set (%s)\n", |
281 | 0 | calling_fn_name, util::ErrorString(result).original); |
282 | 0 | } |
283 | 0 | return std::move(result).value_or(CTxMemPool::setEntries{}); |
284 | 0 | } |
285 | | |
286 | | void CTxMemPool::UpdateAncestorsOf(bool add, txiter it, setEntries &setAncestors) |
287 | 0 | { |
288 | 0 | const CTxMemPoolEntry::Parents& parents = it->GetMemPoolParentsConst(); |
289 | | // add or remove this tx as a child of each parent |
290 | 0 | for (const CTxMemPoolEntry& parent : parents) { Branch (290:40): [True: 0, False: 0]
|
291 | 0 | UpdateChild(mapTx.iterator_to(parent), it, add); |
292 | 0 | } |
293 | 0 | const int32_t updateCount = (add ? 1 : -1); Branch (293:34): [True: 0, False: 0]
|
294 | 0 | const int32_t updateSize{updateCount * it->GetTxSize()}; |
295 | 0 | const CAmount updateFee = updateCount * it->GetModifiedFee(); |
296 | 0 | for (txiter ancestorIt : setAncestors) { Branch (296:28): [True: 0, False: 0]
|
297 | 0 | mapTx.modify(ancestorIt, [=](CTxMemPoolEntry& e) { e.UpdateDescendantState(updateSize, updateFee, updateCount); }); |
298 | 0 | } |
299 | 0 | } |
300 | | |
301 | | void CTxMemPool::UpdateEntryForAncestors(txiter it, const setEntries &setAncestors) |
302 | 0 | { |
303 | 0 | int64_t updateCount = setAncestors.size(); |
304 | 0 | int64_t updateSize = 0; |
305 | 0 | CAmount updateFee = 0; |
306 | 0 | int64_t updateSigOpsCost = 0; |
307 | 0 | for (txiter ancestorIt : setAncestors) { Branch (307:28): [True: 0, False: 0]
|
308 | 0 | updateSize += ancestorIt->GetTxSize(); |
309 | 0 | updateFee += ancestorIt->GetModifiedFee(); |
310 | 0 | updateSigOpsCost += ancestorIt->GetSigOpCost(); |
311 | 0 | } |
312 | 0 | mapTx.modify(it, [=](CTxMemPoolEntry& e){ e.UpdateAncestorState(updateSize, updateFee, updateCount, updateSigOpsCost); }); |
313 | 0 | } |
314 | | |
315 | | void CTxMemPool::UpdateChildrenForRemoval(txiter it) |
316 | 0 | { |
317 | 0 | const CTxMemPoolEntry::Children& children = it->GetMemPoolChildrenConst(); |
318 | 0 | for (const CTxMemPoolEntry& updateIt : children) { Branch (318:42): [True: 0, False: 0]
|
319 | 0 | UpdateParent(mapTx.iterator_to(updateIt), it, false); |
320 | 0 | } |
321 | 0 | } |
322 | | |
323 | | void CTxMemPool::UpdateForRemoveFromMempool(const setEntries &entriesToRemove, bool updateDescendants) |
324 | 0 | { |
325 | | // For each entry, walk back all ancestors and decrement size associated with this |
326 | | // transaction |
327 | 0 | if (updateDescendants) { Branch (327:9): [True: 0, False: 0]
|
328 | | // updateDescendants should be true whenever we're not recursively |
329 | | // removing a tx and all its descendants, eg when a transaction is |
330 | | // confirmed in a block. |
331 | | // Here we only update statistics and not data in CTxMemPool::Parents |
332 | | // and CTxMemPoolEntry::Children (which we need to preserve until we're |
333 | | // finished with all operations that need to traverse the mempool). |
334 | 0 | for (txiter removeIt : entriesToRemove) { Branch (334:30): [True: 0, False: 0]
|
335 | 0 | setEntries setDescendants; |
336 | 0 | CalculateDescendants(removeIt, setDescendants); |
337 | 0 | setDescendants.erase(removeIt); // don't update state for self |
338 | 0 | int32_t modifySize = -removeIt->GetTxSize(); |
339 | 0 | CAmount modifyFee = -removeIt->GetModifiedFee(); |
340 | 0 | int modifySigOps = -removeIt->GetSigOpCost(); |
341 | 0 | for (txiter dit : setDescendants) { Branch (341:29): [True: 0, False: 0]
|
342 | 0 | mapTx.modify(dit, [=](CTxMemPoolEntry& e){ e.UpdateAncestorState(modifySize, modifyFee, -1, modifySigOps); }); |
343 | 0 | } |
344 | 0 | } |
345 | 0 | } |
346 | 0 | for (txiter removeIt : entriesToRemove) { Branch (346:26): [True: 0, False: 0]
|
347 | 0 | const CTxMemPoolEntry &entry = *removeIt; |
348 | | // Since this is a tx that is already in the mempool, we can call CMPA |
349 | | // with fSearchForParents = false. If the mempool is in a consistent |
350 | | // state, then using true or false should both be correct, though false |
351 | | // should be a bit faster. |
352 | | // However, if we happen to be in the middle of processing a reorg, then |
353 | | // the mempool can be in an inconsistent state. In this case, the set |
354 | | // of ancestors reachable via GetMemPoolParents()/GetMemPoolChildren() |
355 | | // will be the same as the set of ancestors whose packages include this |
356 | | // transaction, because when we add a new transaction to the mempool in |
357 | | // addUnchecked(), we assume it has no children, and in the case of a |
358 | | // reorg where that assumption is false, the in-mempool children aren't |
359 | | // linked to the in-block tx's until UpdateTransactionsFromBlock() is |
360 | | // called. |
361 | | // So if we're being called during a reorg, ie before |
362 | | // UpdateTransactionsFromBlock() has been called, then |
363 | | // GetMemPoolParents()/GetMemPoolChildren() will differ from the set of |
364 | | // mempool parents we'd calculate by searching, and it's important that |
365 | | // we use the cached notion of ancestor transactions as the set of |
366 | | // things to update for removal. |
367 | 0 | auto ancestors{AssumeCalculateMemPoolAncestors(__func__, entry, Limits::NoLimits(), /*fSearchForParents=*/false)}; |
368 | | // Note that UpdateAncestorsOf severs the child links that point to |
369 | | // removeIt in the entries for the parents of removeIt. |
370 | 0 | UpdateAncestorsOf(false, removeIt, ancestors); |
371 | 0 | } |
372 | | // After updating all the ancestor sizes, we can now sever the link between each |
373 | | // transaction being removed and any mempool children (ie, update CTxMemPoolEntry::m_parents |
374 | | // for each direct child of a transaction being removed). |
375 | 0 | for (txiter removeIt : entriesToRemove) { Branch (375:26): [True: 0, False: 0]
|
376 | 0 | UpdateChildrenForRemoval(removeIt); |
377 | 0 | } |
378 | 0 | } |
379 | | |
380 | | void CTxMemPoolEntry::UpdateDescendantState(int32_t modifySize, CAmount modifyFee, int64_t modifyCount) |
381 | 0 | { |
382 | 0 | nSizeWithDescendants += modifySize; |
383 | 0 | assert(nSizeWithDescendants > 0); |
384 | 0 | nModFeesWithDescendants = SaturatingAdd(nModFeesWithDescendants, modifyFee); |
385 | 0 | m_count_with_descendants += modifyCount; |
386 | 0 | assert(m_count_with_descendants > 0); |
387 | 0 | } |
388 | | |
389 | | void CTxMemPoolEntry::UpdateAncestorState(int32_t modifySize, CAmount modifyFee, int64_t modifyCount, int64_t modifySigOps) |
390 | 0 | { |
391 | 0 | nSizeWithAncestors += modifySize; |
392 | 0 | assert(nSizeWithAncestors > 0); |
393 | 0 | nModFeesWithAncestors = SaturatingAdd(nModFeesWithAncestors, modifyFee); |
394 | 0 | m_count_with_ancestors += modifyCount; |
395 | 0 | assert(m_count_with_ancestors > 0); |
396 | 0 | nSigOpCostWithAncestors += modifySigOps; |
397 | 0 | assert(int(nSigOpCostWithAncestors) >= 0); |
398 | 0 | } |
399 | | |
400 | | //! Clamp option values and populate the error if options are not valid. |
401 | | static CTxMemPool::Options&& Flatten(CTxMemPool::Options&& opts, bilingual_str& error) |
402 | 0 | { |
403 | 0 | opts.check_ratio = std::clamp<int>(opts.check_ratio, 0, 1'000'000); |
404 | 0 | int64_t descendant_limit_bytes = opts.limits.descendant_size_vbytes * 40; |
405 | 0 | if (opts.max_size_bytes < 0 || opts.max_size_bytes < descendant_limit_bytes) { Branch (405:9): [True: 0, False: 0]
Branch (405:36): [True: 0, False: 0]
|
406 | 0 | error = strprintf(_("-maxmempool must be at least %d MB"), std::ceil(descendant_limit_bytes / 1'000'000.0)); |
407 | 0 | } |
408 | 0 | return std::move(opts); |
409 | 0 | } |
410 | | |
411 | | CTxMemPool::CTxMemPool(Options opts, bilingual_str& error) |
412 | 0 | : m_opts{Flatten(std::move(opts), error)} |
413 | 0 | { |
414 | 0 | } |
415 | | |
416 | | bool CTxMemPool::isSpent(const COutPoint& outpoint) const |
417 | 0 | { |
418 | 0 | LOCK(cs); |
419 | 0 | return mapNextTx.count(outpoint); |
420 | 0 | } |
421 | | |
422 | | unsigned int CTxMemPool::GetTransactionsUpdated() const |
423 | 0 | { |
424 | 0 | return nTransactionsUpdated; |
425 | 0 | } |
426 | | |
427 | | void CTxMemPool::AddTransactionsUpdated(unsigned int n) |
428 | 0 | { |
429 | 0 | nTransactionsUpdated += n; |
430 | 0 | } |
431 | | |
432 | | void CTxMemPool::addUnchecked(const CTxMemPoolEntry &entry, setEntries &setAncestors) |
433 | 0 | { |
434 | | // Add to memory pool without checking anything. |
435 | | // Used by AcceptToMemoryPool(), which DOES do |
436 | | // all the appropriate checks. |
437 | 0 | indexed_transaction_set::iterator newit = mapTx.emplace(CTxMemPoolEntry::ExplicitCopy, entry).first; |
438 | | |
439 | | // Update transaction for any feeDelta created by PrioritiseTransaction |
440 | 0 | CAmount delta{0}; |
441 | 0 | ApplyDelta(entry.GetTx().GetHash(), delta); |
442 | | // The following call to UpdateModifiedFee assumes no previous fee modifications |
443 | 0 | Assume(entry.GetFee() == entry.GetModifiedFee()); |
444 | 0 | if (delta) { Branch (444:9): [True: 0, False: 0]
|
445 | 0 | mapTx.modify(newit, [&delta](CTxMemPoolEntry& e) { e.UpdateModifiedFee(delta); }); |
446 | 0 | } |
447 | | |
448 | | // Update cachedInnerUsage to include contained transaction's usage. |
449 | | // (When we update the entry for in-mempool parents, memory usage will be |
450 | | // further updated.) |
451 | 0 | cachedInnerUsage += entry.DynamicMemoryUsage(); |
452 | |
|
453 | 0 | const CTransaction& tx = newit->GetTx(); |
454 | 0 | std::set<Txid> setParentTransactions; |
455 | 0 | for (unsigned int i = 0; i < tx.vin.size(); i++) { Branch (455:30): [True: 0, False: 0]
|
456 | 0 | mapNextTx.insert(std::make_pair(&tx.vin[i].prevout, &tx)); |
457 | 0 | setParentTransactions.insert(tx.vin[i].prevout.hash); |
458 | 0 | } |
459 | | // Don't bother worrying about child transactions of this one. |
460 | | // Normal case of a new transaction arriving is that there can't be any |
461 | | // children, because such children would be orphans. |
462 | | // An exception to that is if a transaction enters that used to be in a block. |
463 | | // In that case, our disconnect block logic will call UpdateTransactionsFromBlock |
464 | | // to clean up the mess we're leaving here. |
465 | | |
466 | | // Update ancestors with information about this tx |
467 | 0 | for (const auto& pit : GetIterSet(setParentTransactions)) { Branch (467:26): [True: 0, False: 0]
|
468 | 0 | UpdateParent(newit, pit, true); |
469 | 0 | } |
470 | 0 | UpdateAncestorsOf(true, newit, setAncestors); |
471 | 0 | UpdateEntryForAncestors(newit, setAncestors); |
472 | |
|
473 | 0 | nTransactionsUpdated++; |
474 | 0 | totalTxSize += entry.GetTxSize(); |
475 | 0 | m_total_fee += entry.GetFee(); |
476 | |
|
477 | 0 | txns_randomized.emplace_back(newit->GetSharedTx()); |
478 | 0 | newit->idx_randomized = txns_randomized.size() - 1; |
479 | |
|
480 | 0 | TRACE3(mempool, added, |
481 | 0 | entry.GetTx().GetHash().data(), |
482 | 0 | entry.GetTxSize(), |
483 | 0 | entry.GetFee() |
484 | 0 | ); |
485 | 0 | } |
486 | | |
487 | | void CTxMemPool::removeUnchecked(txiter it, MemPoolRemovalReason reason) |
488 | 0 | { |
489 | | // We increment mempool sequence value no matter removal reason |
490 | | // even if not directly reported below. |
491 | 0 | uint64_t mempool_sequence = GetAndIncrementSequence(); |
492 | |
|
493 | 0 | if (reason != MemPoolRemovalReason::BLOCK && m_opts.signals) { Branch (493:9): [True: 0, False: 0]
Branch (493:50): [True: 0, False: 0]
|
494 | | // Notify clients that a transaction has been removed from the mempool |
495 | | // for any reason except being included in a block. Clients interested |
496 | | // in transactions included in blocks can subscribe to the BlockConnected |
497 | | // notification. |
498 | 0 | m_opts.signals->TransactionRemovedFromMempool(it->GetSharedTx(), reason, mempool_sequence); |
499 | 0 | } |
500 | 0 | TRACE5(mempool, removed, |
501 | 0 | it->GetTx().GetHash().data(), |
502 | 0 | RemovalReasonToString(reason).c_str(), |
503 | 0 | it->GetTxSize(), |
504 | 0 | it->GetFee(), |
505 | 0 | std::chrono::duration_cast<std::chrono::duration<std::uint64_t>>(it->GetTime()).count() |
506 | 0 | ); |
507 | |
|
508 | 0 | for (const CTxIn& txin : it->GetTx().vin) Branch (508:28): [True: 0, False: 0]
|
509 | 0 | mapNextTx.erase(txin.prevout); |
510 | |
|
511 | 0 | RemoveUnbroadcastTx(it->GetTx().GetHash(), true /* add logging because unchecked */); |
512 | |
|
513 | 0 | if (txns_randomized.size() > 1) { Branch (513:9): [True: 0, False: 0]
|
514 | | // Update idx_randomized of the to-be-moved entry. |
515 | 0 | Assert(GetEntry(txns_randomized.back()->GetHash()))->idx_randomized = it->idx_randomized; |
516 | | // Remove entry from txns_randomized by replacing it with the back and deleting the back. |
517 | 0 | txns_randomized[it->idx_randomized] = std::move(txns_randomized.back()); |
518 | 0 | txns_randomized.pop_back(); |
519 | 0 | if (txns_randomized.size() * 2 < txns_randomized.capacity()) Branch (519:13): [True: 0, False: 0]
|
520 | 0 | txns_randomized.shrink_to_fit(); |
521 | 0 | } else |
522 | 0 | txns_randomized.clear(); |
523 | |
|
524 | 0 | totalTxSize -= it->GetTxSize(); |
525 | 0 | m_total_fee -= it->GetFee(); |
526 | 0 | cachedInnerUsage -= it->DynamicMemoryUsage(); |
527 | 0 | cachedInnerUsage -= memusage::DynamicUsage(it->GetMemPoolParentsConst()) + memusage::DynamicUsage(it->GetMemPoolChildrenConst()); |
528 | 0 | mapTx.erase(it); |
529 | 0 | nTransactionsUpdated++; |
530 | 0 | } |
531 | | |
532 | | // Calculates descendants of entry that are not already in setDescendants, and adds to |
533 | | // setDescendants. Assumes entryit is already a tx in the mempool and CTxMemPoolEntry::m_children |
534 | | // is correct for tx and all descendants. |
535 | | // Also assumes that if an entry is in setDescendants already, then all |
536 | | // in-mempool descendants of it are already in setDescendants as well, so that we |
537 | | // can save time by not iterating over those entries. |
538 | | void CTxMemPool::CalculateDescendants(txiter entryit, setEntries& setDescendants) const |
539 | 0 | { |
540 | 0 | setEntries stage; |
541 | 0 | if (setDescendants.count(entryit) == 0) { Branch (541:9): [True: 0, False: 0]
|
542 | 0 | stage.insert(entryit); |
543 | 0 | } |
544 | | // Traverse down the children of entry, only adding children that are not |
545 | | // accounted for in setDescendants already (because those children have either |
546 | | // already been walked, or will be walked in this iteration). |
547 | 0 | while (!stage.empty()) { Branch (547:12): [True: 0, False: 0]
|
548 | 0 | txiter it = *stage.begin(); |
549 | 0 | setDescendants.insert(it); |
550 | 0 | stage.erase(it); |
551 | |
|
552 | 0 | const CTxMemPoolEntry::Children& children = it->GetMemPoolChildrenConst(); |
553 | 0 | for (const CTxMemPoolEntry& child : children) { Branch (553:43): [True: 0, False: 0]
|
554 | 0 | txiter childiter = mapTx.iterator_to(child); |
555 | 0 | if (!setDescendants.count(childiter)) { Branch (555:17): [True: 0, False: 0]
|
556 | 0 | stage.insert(childiter); |
557 | 0 | } |
558 | 0 | } |
559 | 0 | } |
560 | 0 | } |
561 | | |
562 | | void CTxMemPool::removeRecursive(const CTransaction &origTx, MemPoolRemovalReason reason) |
563 | 0 | { |
564 | | // Remove transaction from memory pool |
565 | 0 | AssertLockHeld(cs); |
566 | 0 | setEntries txToRemove; |
567 | 0 | txiter origit = mapTx.find(origTx.GetHash()); |
568 | 0 | if (origit != mapTx.end()) { Branch (568:13): [True: 0, False: 0]
|
569 | 0 | txToRemove.insert(origit); |
570 | 0 | } else { |
571 | | // When recursively removing but origTx isn't in the mempool |
572 | | // be sure to remove any children that are in the pool. This can |
573 | | // happen during chain re-orgs if origTx isn't re-accepted into |
574 | | // the mempool for any reason. |
575 | 0 | for (unsigned int i = 0; i < origTx.vout.size(); i++) { Branch (575:38): [True: 0, False: 0]
|
576 | 0 | auto it = mapNextTx.find(COutPoint(origTx.GetHash(), i)); |
577 | 0 | if (it == mapNextTx.end()) Branch (577:21): [True: 0, False: 0]
|
578 | 0 | continue; |
579 | 0 | txiter nextit = mapTx.find(it->second->GetHash()); |
580 | 0 | assert(nextit != mapTx.end()); |
581 | 0 | txToRemove.insert(nextit); |
582 | 0 | } |
583 | 0 | } |
584 | 0 | setEntries setAllRemoves; |
585 | 0 | for (txiter it : txToRemove) { Branch (585:24): [True: 0, False: 0]
|
586 | 0 | CalculateDescendants(it, setAllRemoves); |
587 | 0 | } |
588 | |
|
589 | 0 | RemoveStaged(setAllRemoves, false, reason); |
590 | 0 | } |
591 | | |
592 | | void CTxMemPool::removeForReorg(CChain& chain, std::function<bool(txiter)> check_final_and_mature) |
593 | 0 | { |
594 | | // Remove transactions spending a coinbase which are now immature and no-longer-final transactions |
595 | 0 | AssertLockHeld(cs); |
596 | 0 | AssertLockHeld(::cs_main); |
597 | |
|
598 | 0 | setEntries txToRemove; |
599 | 0 | for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) { Branch (599:70): [True: 0, False: 0]
|
600 | 0 | if (check_final_and_mature(it)) txToRemove.insert(it); Branch (600:13): [True: 0, False: 0]
|
601 | 0 | } |
602 | 0 | setEntries setAllRemoves; |
603 | 0 | for (txiter it : txToRemove) { Branch (603:20): [True: 0, False: 0]
|
604 | 0 | CalculateDescendants(it, setAllRemoves); |
605 | 0 | } |
606 | 0 | RemoveStaged(setAllRemoves, false, MemPoolRemovalReason::REORG); |
607 | 0 | for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) { Branch (607:70): [True: 0, False: 0]
|
608 | 0 | assert(TestLockPointValidity(chain, it->GetLockPoints())); |
609 | 0 | } |
610 | 0 | } |
611 | | |
612 | | void CTxMemPool::removeConflicts(const CTransaction &tx) |
613 | 0 | { |
614 | | // Remove transactions which depend on inputs of tx, recursively |
615 | 0 | AssertLockHeld(cs); |
616 | 0 | for (const CTxIn &txin : tx.vin) { Branch (616:28): [True: 0, False: 0]
|
617 | 0 | auto it = mapNextTx.find(txin.prevout); |
618 | 0 | if (it != mapNextTx.end()) { Branch (618:13): [True: 0, False: 0]
|
619 | 0 | const CTransaction &txConflict = *it->second; |
620 | 0 | if (txConflict != tx) Branch (620:17): [True: 0, False: 0]
|
621 | 0 | { |
622 | 0 | ClearPrioritisation(txConflict.GetHash()); |
623 | 0 | removeRecursive(txConflict, MemPoolRemovalReason::CONFLICT); |
624 | 0 | } |
625 | 0 | } |
626 | 0 | } |
627 | 0 | } |
628 | | |
629 | | /** |
630 | | * Called when a block is connected. Removes from mempool. |
631 | | */ |
632 | | void CTxMemPool::removeForBlock(const std::vector<CTransactionRef>& vtx, unsigned int nBlockHeight) |
633 | 0 | { |
634 | 0 | AssertLockHeld(cs); |
635 | 0 | std::vector<RemovedMempoolTransactionInfo> txs_removed_for_block; |
636 | 0 | txs_removed_for_block.reserve(vtx.size()); |
637 | 0 | for (const auto& tx : vtx) Branch (637:25): [True: 0, False: 0]
|
638 | 0 | { |
639 | 0 | txiter it = mapTx.find(tx->GetHash()); |
640 | 0 | if (it != mapTx.end()) { Branch (640:13): [True: 0, False: 0]
|
641 | 0 | setEntries stage; |
642 | 0 | stage.insert(it); |
643 | 0 | txs_removed_for_block.emplace_back(*it); |
644 | 0 | RemoveStaged(stage, true, MemPoolRemovalReason::BLOCK); |
645 | 0 | } |
646 | 0 | removeConflicts(*tx); |
647 | 0 | ClearPrioritisation(tx->GetHash()); |
648 | 0 | } |
649 | 0 | if (m_opts.signals) { Branch (649:9): [True: 0, False: 0]
|
650 | 0 | m_opts.signals->MempoolTransactionsRemovedForBlock(txs_removed_for_block, nBlockHeight); |
651 | 0 | } |
652 | 0 | lastRollingFeeUpdate = GetTime(); |
653 | 0 | blockSinceLastRollingFeeBump = true; |
654 | 0 | } |
655 | | |
656 | | void CTxMemPool::check(const CCoinsViewCache& active_coins_tip, int64_t spendheight) const |
657 | 0 | { |
658 | 0 | if (m_opts.check_ratio == 0) return; Branch (658:9): [True: 0, False: 0]
|
659 | | |
660 | 0 | if (FastRandomContext().randrange(m_opts.check_ratio) >= 1) return; Branch (660:9): [True: 0, False: 0]
|
661 | | |
662 | 0 | AssertLockHeld(::cs_main); |
663 | 0 | LOCK(cs); |
664 | 0 | LogPrint(BCLog::MEMPOOL, "Checking mempool with %u transactions and %u inputs\n", (unsigned int)mapTx.size(), (unsigned int)mapNextTx.size()); |
665 | |
|
666 | 0 | uint64_t checkTotal = 0; |
667 | 0 | CAmount check_total_fee{0}; |
668 | 0 | uint64_t innerUsage = 0; |
669 | 0 | uint64_t prev_ancestor_count{0}; |
670 | |
|
671 | 0 | CCoinsViewCache mempoolDuplicate(const_cast<CCoinsViewCache*>(&active_coins_tip)); |
672 | |
|
673 | 0 | for (const auto& it : GetSortedDepthAndScore()) { Branch (673:25): [True: 0, False: 0]
|
674 | 0 | checkTotal += it->GetTxSize(); |
675 | 0 | check_total_fee += it->GetFee(); |
676 | 0 | innerUsage += it->DynamicMemoryUsage(); |
677 | 0 | const CTransaction& tx = it->GetTx(); |
678 | 0 | innerUsage += memusage::DynamicUsage(it->GetMemPoolParentsConst()) + memusage::DynamicUsage(it->GetMemPoolChildrenConst()); |
679 | 0 | CTxMemPoolEntry::Parents setParentCheck; |
680 | 0 | for (const CTxIn &txin : tx.vin) { Branch (680:32): [True: 0, False: 0]
|
681 | | // Check that every mempool transaction's inputs refer to available coins, or other mempool tx's. |
682 | 0 | indexed_transaction_set::const_iterator it2 = mapTx.find(txin.prevout.hash); |
683 | 0 | if (it2 != mapTx.end()) { Branch (683:17): [True: 0, False: 0]
|
684 | 0 | const CTransaction& tx2 = it2->GetTx(); |
685 | 0 | assert(tx2.vout.size() > txin.prevout.n && !tx2.vout[txin.prevout.n].IsNull()); |
686 | 0 | setParentCheck.insert(*it2); |
687 | 0 | } |
688 | | // We are iterating through the mempool entries sorted in order by ancestor count. |
689 | | // All parents must have been checked before their children and their coins added to |
690 | | // the mempoolDuplicate coins cache. |
691 | 0 | assert(mempoolDuplicate.HaveCoin(txin.prevout)); |
692 | | // Check whether its inputs are marked in mapNextTx. |
693 | 0 | auto it3 = mapNextTx.find(txin.prevout); |
694 | 0 | assert(it3 != mapNextTx.end()); |
695 | 0 | assert(it3->first == &txin.prevout); |
696 | 0 | assert(it3->second == &tx); |
697 | 0 | } |
698 | 0 | auto comp = [](const CTxMemPoolEntry& a, const CTxMemPoolEntry& b) -> bool { |
699 | 0 | return a.GetTx().GetHash() == b.GetTx().GetHash(); |
700 | 0 | }; |
701 | 0 | assert(setParentCheck.size() == it->GetMemPoolParentsConst().size()); |
702 | 0 | assert(std::equal(setParentCheck.begin(), setParentCheck.end(), it->GetMemPoolParentsConst().begin(), comp)); |
703 | | // Verify ancestor state is correct. |
704 | 0 | auto ancestors{AssumeCalculateMemPoolAncestors(__func__, *it, Limits::NoLimits())}; |
705 | 0 | uint64_t nCountCheck = ancestors.size() + 1; |
706 | 0 | int32_t nSizeCheck = it->GetTxSize(); |
707 | 0 | CAmount nFeesCheck = it->GetModifiedFee(); |
708 | 0 | int64_t nSigOpCheck = it->GetSigOpCost(); |
709 | |
|
710 | 0 | for (txiter ancestorIt : ancestors) { Branch (710:32): [True: 0, False: 0]
|
711 | 0 | nSizeCheck += ancestorIt->GetTxSize(); |
712 | 0 | nFeesCheck += ancestorIt->GetModifiedFee(); |
713 | 0 | nSigOpCheck += ancestorIt->GetSigOpCost(); |
714 | 0 | } |
715 | |
|
716 | 0 | assert(it->GetCountWithAncestors() == nCountCheck); |
717 | 0 | assert(it->GetSizeWithAncestors() == nSizeCheck); |
718 | 0 | assert(it->GetSigOpCostWithAncestors() == nSigOpCheck); |
719 | 0 | assert(it->GetModFeesWithAncestors() == nFeesCheck); |
720 | | // Sanity check: we are walking in ascending ancestor count order. |
721 | 0 | assert(prev_ancestor_count <= it->GetCountWithAncestors()); |
722 | 0 | prev_ancestor_count = it->GetCountWithAncestors(); |
723 | | |
724 | | // Check children against mapNextTx |
725 | 0 | CTxMemPoolEntry::Children setChildrenCheck; |
726 | 0 | auto iter = mapNextTx.lower_bound(COutPoint(it->GetTx().GetHash(), 0)); |
727 | 0 | int32_t child_sizes{0}; |
728 | 0 | for (; iter != mapNextTx.end() && iter->first->hash == it->GetTx().GetHash(); ++iter) { Branch (728:16): [True: 0, False: 0]
Branch (728:16): [True: 0, False: 0]
Branch (728:43): [True: 0, False: 0]
|
729 | 0 | txiter childit = mapTx.find(iter->second->GetHash()); |
730 | 0 | assert(childit != mapTx.end()); // mapNextTx points to in-mempool transactions |
731 | 0 | if (setChildrenCheck.insert(*childit).second) { Branch (731:17): [True: 0, False: 0]
|
732 | 0 | child_sizes += childit->GetTxSize(); |
733 | 0 | } |
734 | 0 | } |
735 | 0 | assert(setChildrenCheck.size() == it->GetMemPoolChildrenConst().size()); |
736 | 0 | assert(std::equal(setChildrenCheck.begin(), setChildrenCheck.end(), it->GetMemPoolChildrenConst().begin(), comp)); |
737 | | // Also check to make sure size is greater than sum with immediate children. |
738 | | // just a sanity check, not definitive that this calc is correct... |
739 | 0 | assert(it->GetSizeWithDescendants() >= child_sizes + it->GetTxSize()); |
740 | | |
741 | 0 | TxValidationState dummy_state; // Not used. CheckTxInputs() should always pass |
742 | 0 | CAmount txfee = 0; |
743 | 0 | assert(!tx.IsCoinBase()); |
744 | 0 | assert(Consensus::CheckTxInputs(tx, dummy_state, mempoolDuplicate, spendheight, txfee)); |
745 | 0 | for (const auto& input: tx.vin) mempoolDuplicate.SpendCoin(input.prevout); Branch (745:31): [True: 0, False: 0]
|
746 | 0 | AddCoins(mempoolDuplicate, tx, std::numeric_limits<int>::max()); |
747 | 0 | } |
748 | 0 | for (auto it = mapNextTx.cbegin(); it != mapNextTx.cend(); it++) { Branch (748:40): [True: 0, False: 0]
|
749 | 0 | uint256 hash = it->second->GetHash(); |
750 | 0 | indexed_transaction_set::const_iterator it2 = mapTx.find(hash); |
751 | 0 | const CTransaction& tx = it2->GetTx(); |
752 | 0 | assert(it2 != mapTx.end()); |
753 | 0 | assert(&tx == it->second); |
754 | 0 | } |
755 | | |
756 | 0 | assert(totalTxSize == checkTotal); |
757 | 0 | assert(m_total_fee == check_total_fee); |
758 | 0 | assert(innerUsage == cachedInnerUsage); |
759 | 0 | } |
760 | | |
761 | | bool CTxMemPool::CompareDepthAndScore(const uint256& hasha, const uint256& hashb, bool wtxid) |
762 | 0 | { |
763 | | /* Return `true` if hasha should be considered sooner than hashb. Namely when: |
764 | | * a is not in the mempool, but b is |
765 | | * both are in the mempool and a has fewer ancestors than b |
766 | | * both are in the mempool and a has a higher score than b |
767 | | */ |
768 | 0 | LOCK(cs); |
769 | 0 | indexed_transaction_set::const_iterator j = wtxid ? get_iter_from_wtxid(hashb) : mapTx.find(hashb); Branch (769:49): [True: 0, False: 0]
|
770 | 0 | if (j == mapTx.end()) return false; Branch (770:9): [True: 0, False: 0]
|
771 | 0 | indexed_transaction_set::const_iterator i = wtxid ? get_iter_from_wtxid(hasha) : mapTx.find(hasha); Branch (771:49): [True: 0, False: 0]
|
772 | 0 | if (i == mapTx.end()) return true; Branch (772:9): [True: 0, False: 0]
|
773 | 0 | uint64_t counta = i->GetCountWithAncestors(); |
774 | 0 | uint64_t countb = j->GetCountWithAncestors(); |
775 | 0 | if (counta == countb) { Branch (775:9): [True: 0, False: 0]
|
776 | 0 | return CompareTxMemPoolEntryByScore()(*i, *j); |
777 | 0 | } |
778 | 0 | return counta < countb; |
779 | 0 | } |
780 | | |
781 | | namespace { |
782 | | class DepthAndScoreComparator |
783 | | { |
784 | | public: |
785 | | bool operator()(const CTxMemPool::indexed_transaction_set::const_iterator& a, const CTxMemPool::indexed_transaction_set::const_iterator& b) |
786 | 0 | { |
787 | 0 | uint64_t counta = a->GetCountWithAncestors(); |
788 | 0 | uint64_t countb = b->GetCountWithAncestors(); |
789 | 0 | if (counta == countb) { Branch (789:13): [True: 0, False: 0]
|
790 | 0 | return CompareTxMemPoolEntryByScore()(*a, *b); |
791 | 0 | } |
792 | 0 | return counta < countb; |
793 | 0 | } |
794 | | }; |
795 | | } // namespace |
796 | | |
797 | | std::vector<CTxMemPool::indexed_transaction_set::const_iterator> CTxMemPool::GetSortedDepthAndScore() const |
798 | 0 | { |
799 | 0 | std::vector<indexed_transaction_set::const_iterator> iters; |
800 | 0 | AssertLockHeld(cs); |
801 | |
|
802 | 0 | iters.reserve(mapTx.size()); |
803 | |
|
804 | 0 | for (indexed_transaction_set::iterator mi = mapTx.begin(); mi != mapTx.end(); ++mi) { Branch (804:64): [True: 0, False: 0]
|
805 | 0 | iters.push_back(mi); |
806 | 0 | } |
807 | 0 | std::sort(iters.begin(), iters.end(), DepthAndScoreComparator()); |
808 | 0 | return iters; |
809 | 0 | } |
810 | | |
811 | 0 | static TxMempoolInfo GetInfo(CTxMemPool::indexed_transaction_set::const_iterator it) { |
812 | 0 | return TxMempoolInfo{it->GetSharedTx(), it->GetTime(), it->GetFee(), it->GetTxSize(), it->GetModifiedFee() - it->GetFee()}; |
813 | 0 | } |
814 | | |
815 | | std::vector<CTxMemPoolEntryRef> CTxMemPool::entryAll() const |
816 | 0 | { |
817 | 0 | AssertLockHeld(cs); |
818 | |
|
819 | 0 | std::vector<CTxMemPoolEntryRef> ret; |
820 | 0 | ret.reserve(mapTx.size()); |
821 | 0 | for (const auto& it : GetSortedDepthAndScore()) { Branch (821:25): [True: 0, False: 0]
|
822 | 0 | ret.emplace_back(*it); |
823 | 0 | } |
824 | 0 | return ret; |
825 | 0 | } |
826 | | |
827 | | std::vector<TxMempoolInfo> CTxMemPool::infoAll() const |
828 | 0 | { |
829 | 0 | LOCK(cs); |
830 | 0 | auto iters = GetSortedDepthAndScore(); |
831 | |
|
832 | 0 | std::vector<TxMempoolInfo> ret; |
833 | 0 | ret.reserve(mapTx.size()); |
834 | 0 | for (auto it : iters) { Branch (834:18): [True: 0, False: 0]
|
835 | 0 | ret.push_back(GetInfo(it)); |
836 | 0 | } |
837 | |
|
838 | 0 | return ret; |
839 | 0 | } |
840 | | |
841 | | const CTxMemPoolEntry* CTxMemPool::GetEntry(const Txid& txid) const |
842 | 0 | { |
843 | 0 | AssertLockHeld(cs); |
844 | 0 | const auto i = mapTx.find(txid); |
845 | 0 | return i == mapTx.end() ? nullptr : &(*i); Branch (845:12): [True: 0, False: 0]
|
846 | 0 | } |
847 | | |
848 | | CTransactionRef CTxMemPool::get(const uint256& hash) const |
849 | 0 | { |
850 | 0 | LOCK(cs); |
851 | 0 | indexed_transaction_set::const_iterator i = mapTx.find(hash); |
852 | 0 | if (i == mapTx.end()) Branch (852:9): [True: 0, False: 0]
|
853 | 0 | return nullptr; |
854 | 0 | return i->GetSharedTx(); |
855 | 0 | } |
856 | | |
857 | | TxMempoolInfo CTxMemPool::info(const GenTxid& gtxid) const |
858 | 0 | { |
859 | 0 | LOCK(cs); |
860 | 0 | indexed_transaction_set::const_iterator i = (gtxid.IsWtxid() ? get_iter_from_wtxid(gtxid.GetHash()) : mapTx.find(gtxid.GetHash())); Branch (860:50): [True: 0, False: 0]
|
861 | 0 | if (i == mapTx.end()) Branch (861:9): [True: 0, False: 0]
|
862 | 0 | return TxMempoolInfo(); |
863 | 0 | return GetInfo(i); |
864 | 0 | } |
865 | | |
866 | | TxMempoolInfo CTxMemPool::info_for_relay(const GenTxid& gtxid, uint64_t last_sequence) const |
867 | 0 | { |
868 | 0 | LOCK(cs); |
869 | 0 | indexed_transaction_set::const_iterator i = (gtxid.IsWtxid() ? get_iter_from_wtxid(gtxid.GetHash()) : mapTx.find(gtxid.GetHash())); Branch (869:50): [True: 0, False: 0]
|
870 | 0 | if (i != mapTx.end() && i->GetSequence() < last_sequence) { Branch (870:9): [True: 0, False: 0]
Branch (870:9): [True: 0, False: 0]
Branch (870:29): [True: 0, False: 0]
|
871 | 0 | return GetInfo(i); |
872 | 0 | } else { |
873 | 0 | return TxMempoolInfo(); |
874 | 0 | } |
875 | 0 | } |
876 | | |
877 | | void CTxMemPool::PrioritiseTransaction(const uint256& hash, const CAmount& nFeeDelta) |
878 | 0 | { |
879 | 0 | { |
880 | 0 | LOCK(cs); |
881 | 0 | CAmount &delta = mapDeltas[hash]; |
882 | 0 | delta = SaturatingAdd(delta, nFeeDelta); |
883 | 0 | txiter it = mapTx.find(hash); |
884 | 0 | if (it != mapTx.end()) { Branch (884:13): [True: 0, False: 0]
|
885 | 0 | mapTx.modify(it, [&nFeeDelta](CTxMemPoolEntry& e) { e.UpdateModifiedFee(nFeeDelta); }); |
886 | | // Now update all ancestors' modified fees with descendants |
887 | 0 | auto ancestors{AssumeCalculateMemPoolAncestors(__func__, *it, Limits::NoLimits(), /*fSearchForParents=*/false)}; |
888 | 0 | for (txiter ancestorIt : ancestors) { Branch (888:36): [True: 0, False: 0]
|
889 | 0 | mapTx.modify(ancestorIt, [=](CTxMemPoolEntry& e){ e.UpdateDescendantState(0, nFeeDelta, 0);}); |
890 | 0 | } |
891 | | // Now update all descendants' modified fees with ancestors |
892 | 0 | setEntries setDescendants; |
893 | 0 | CalculateDescendants(it, setDescendants); |
894 | 0 | setDescendants.erase(it); |
895 | 0 | for (txiter descendantIt : setDescendants) { Branch (895:38): [True: 0, False: 0]
|
896 | 0 | mapTx.modify(descendantIt, [=](CTxMemPoolEntry& e){ e.UpdateAncestorState(0, nFeeDelta, 0, 0); }); |
897 | 0 | } |
898 | 0 | ++nTransactionsUpdated; |
899 | 0 | } |
900 | 0 | if (delta == 0) { Branch (900:13): [True: 0, False: 0]
|
901 | 0 | mapDeltas.erase(hash); |
902 | 0 | LogPrintf("PrioritiseTransaction: %s (%sin mempool) delta cleared\n", hash.ToString(), it == mapTx.end() ? "not " : ""); |
903 | 0 | } else { |
904 | 0 | LogPrintf("PrioritiseTransaction: %s (%sin mempool) fee += %s, new delta=%s\n", |
905 | 0 | hash.ToString(), |
906 | 0 | it == mapTx.end() ? "not " : "", |
907 | 0 | FormatMoney(nFeeDelta), |
908 | 0 | FormatMoney(delta)); |
909 | 0 | } |
910 | 0 | } |
911 | 0 | } |
912 | | |
913 | | void CTxMemPool::ApplyDelta(const uint256& hash, CAmount &nFeeDelta) const |
914 | 0 | { |
915 | 0 | AssertLockHeld(cs); |
916 | 0 | std::map<uint256, CAmount>::const_iterator pos = mapDeltas.find(hash); |
917 | 0 | if (pos == mapDeltas.end()) Branch (917:9): [True: 0, False: 0]
|
918 | 0 | return; |
919 | 0 | const CAmount &delta = pos->second; |
920 | 0 | nFeeDelta += delta; |
921 | 0 | } |
922 | | |
923 | | void CTxMemPool::ClearPrioritisation(const uint256& hash) |
924 | 0 | { |
925 | 0 | AssertLockHeld(cs); |
926 | 0 | mapDeltas.erase(hash); |
927 | 0 | } |
928 | | |
929 | | std::vector<CTxMemPool::delta_info> CTxMemPool::GetPrioritisedTransactions() const |
930 | 0 | { |
931 | 0 | AssertLockNotHeld(cs); |
932 | 0 | LOCK(cs); |
933 | 0 | std::vector<delta_info> result; |
934 | 0 | result.reserve(mapDeltas.size()); |
935 | 0 | for (const auto& [txid, delta] : mapDeltas) { Branch (935:36): [True: 0, False: 0]
|
936 | 0 | const auto iter{mapTx.find(txid)}; |
937 | 0 | const bool in_mempool{iter != mapTx.end()}; |
938 | 0 | std::optional<CAmount> modified_fee; |
939 | 0 | if (in_mempool) modified_fee = iter->GetModifiedFee(); Branch (939:13): [True: 0, False: 0]
|
940 | 0 | result.emplace_back(delta_info{in_mempool, delta, modified_fee, txid}); |
941 | 0 | } |
942 | 0 | return result; |
943 | 0 | } |
944 | | |
945 | | const CTransaction* CTxMemPool::GetConflictTx(const COutPoint& prevout) const |
946 | 0 | { |
947 | 0 | const auto it = mapNextTx.find(prevout); |
948 | 0 | return it == mapNextTx.end() ? nullptr : it->second; Branch (948:12): [True: 0, False: 0]
|
949 | 0 | } |
950 | | |
951 | | std::optional<CTxMemPool::txiter> CTxMemPool::GetIter(const uint256& txid) const |
952 | 0 | { |
953 | 0 | auto it = mapTx.find(txid); |
954 | 0 | if (it != mapTx.end()) return it; Branch (954:9): [True: 0, False: 0]
|
955 | 0 | return std::nullopt; |
956 | 0 | } |
957 | | |
958 | | CTxMemPool::setEntries CTxMemPool::GetIterSet(const std::set<Txid>& hashes) const |
959 | 0 | { |
960 | 0 | CTxMemPool::setEntries ret; |
961 | 0 | for (const auto& h : hashes) { Branch (961:24): [True: 0, False: 0]
|
962 | 0 | const auto mi = GetIter(h); |
963 | 0 | if (mi) ret.insert(*mi); Branch (963:13): [True: 0, False: 0]
|
964 | 0 | } |
965 | 0 | return ret; |
966 | 0 | } |
967 | | |
968 | | std::vector<CTxMemPool::txiter> CTxMemPool::GetIterVec(const std::vector<uint256>& txids) const |
969 | 0 | { |
970 | 0 | AssertLockHeld(cs); |
971 | 0 | std::vector<txiter> ret; |
972 | 0 | ret.reserve(txids.size()); |
973 | 0 | for (const auto& txid : txids) { Branch (973:27): [True: 0, False: 0]
|
974 | 0 | const auto it{GetIter(txid)}; |
975 | 0 | if (!it) return {}; Branch (975:13): [True: 0, False: 0]
|
976 | 0 | ret.push_back(*it); |
977 | 0 | } |
978 | 0 | return ret; |
979 | 0 | } |
980 | | |
981 | | bool CTxMemPool::HasNoInputsOf(const CTransaction &tx) const |
982 | 0 | { |
983 | 0 | for (unsigned int i = 0; i < tx.vin.size(); i++) Branch (983:30): [True: 0, False: 0]
|
984 | 0 | if (exists(GenTxid::Txid(tx.vin[i].prevout.hash))) Branch (984:13): [True: 0, False: 0]
|
985 | 0 | return false; |
986 | 0 | return true; |
987 | 0 | } |
988 | | |
989 | 0 | CCoinsViewMemPool::CCoinsViewMemPool(CCoinsView* baseIn, const CTxMemPool& mempoolIn) : CCoinsViewBacked(baseIn), mempool(mempoolIn) { } |
990 | | |
991 | 0 | bool CCoinsViewMemPool::GetCoin(const COutPoint &outpoint, Coin &coin) const { |
992 | | // Check to see if the inputs are made available by another tx in the package. |
993 | | // These Coins would not be available in the underlying CoinsView. |
994 | 0 | if (auto it = m_temp_added.find(outpoint); it != m_temp_added.end()) { Branch (994:48): [True: 0, False: 0]
|
995 | 0 | coin = it->second; |
996 | 0 | return true; |
997 | 0 | } |
998 | | |
999 | | // If an entry in the mempool exists, always return that one, as it's guaranteed to never |
1000 | | // conflict with the underlying cache, and it cannot have pruned entries (as it contains full) |
1001 | | // transactions. First checking the underlying cache risks returning a pruned entry instead. |
1002 | 0 | CTransactionRef ptx = mempool.get(outpoint.hash); |
1003 | 0 | if (ptx) { Branch (1003:9): [True: 0, False: 0]
|
1004 | 0 | if (outpoint.n < ptx->vout.size()) { Branch (1004:13): [True: 0, False: 0]
|
1005 | 0 | coin = Coin(ptx->vout[outpoint.n], MEMPOOL_HEIGHT, false); |
1006 | 0 | m_non_base_coins.emplace(outpoint); |
1007 | 0 | return true; |
1008 | 0 | } else { |
1009 | 0 | return false; |
1010 | 0 | } |
1011 | 0 | } |
1012 | 0 | return base->GetCoin(outpoint, coin); |
1013 | 0 | } |
1014 | | |
1015 | | void CCoinsViewMemPool::PackageAddTransaction(const CTransactionRef& tx) |
1016 | 0 | { |
1017 | 0 | for (unsigned int n = 0; n < tx->vout.size(); ++n) { Branch (1017:30): [True: 0, False: 0]
|
1018 | 0 | m_temp_added.emplace(COutPoint(tx->GetHash(), n), Coin(tx->vout[n], MEMPOOL_HEIGHT, false)); |
1019 | 0 | m_non_base_coins.emplace(tx->GetHash(), n); |
1020 | 0 | } |
1021 | 0 | } |
1022 | | void CCoinsViewMemPool::Reset() |
1023 | 0 | { |
1024 | 0 | m_temp_added.clear(); |
1025 | 0 | m_non_base_coins.clear(); |
1026 | 0 | } |
1027 | | |
1028 | 0 | size_t CTxMemPool::DynamicMemoryUsage() const { |
1029 | 0 | LOCK(cs); |
1030 | | // Estimate the overhead of mapTx to be 15 pointers + an allocation, as no exact formula for boost::multi_index_contained is implemented. |
1031 | 0 | return memusage::MallocUsage(sizeof(CTxMemPoolEntry) + 15 * sizeof(void*)) * mapTx.size() + memusage::DynamicUsage(mapNextTx) + memusage::DynamicUsage(mapDeltas) + memusage::DynamicUsage(txns_randomized) + cachedInnerUsage; |
1032 | 0 | } |
1033 | | |
1034 | 0 | void CTxMemPool::RemoveUnbroadcastTx(const uint256& txid, const bool unchecked) { |
1035 | 0 | LOCK(cs); |
1036 | |
|
1037 | 0 | if (m_unbroadcast_txids.erase(txid)) Branch (1037:9): [True: 0, False: 0]
|
1038 | 0 | { |
1039 | 0 | LogPrint(BCLog::MEMPOOL, "Removed %i from set of unbroadcast txns%s\n", txid.GetHex(), (unchecked ? " before confirmation that txn was sent out" : "")); |
1040 | 0 | } |
1041 | 0 | } |
1042 | | |
1043 | 0 | void CTxMemPool::RemoveStaged(setEntries &stage, bool updateDescendants, MemPoolRemovalReason reason) { |
1044 | 0 | AssertLockHeld(cs); |
1045 | 0 | UpdateForRemoveFromMempool(stage, updateDescendants); |
1046 | 0 | for (txiter it : stage) { Branch (1046:20): [True: 0, False: 0]
|
1047 | 0 | removeUnchecked(it, reason); |
1048 | 0 | } |
1049 | 0 | } |
1050 | | |
1051 | | int CTxMemPool::Expire(std::chrono::seconds time) |
1052 | 0 | { |
1053 | 0 | AssertLockHeld(cs); |
1054 | 0 | indexed_transaction_set::index<entry_time>::type::iterator it = mapTx.get<entry_time>().begin(); |
1055 | 0 | setEntries toremove; |
1056 | 0 | while (it != mapTx.get<entry_time>().end() && it->GetTime() < time) { Branch (1056:12): [True: 0, False: 0]
Branch (1056:12): [True: 0, False: 0]
Branch (1056:51): [True: 0, False: 0]
|
1057 | 0 | toremove.insert(mapTx.project<0>(it)); |
1058 | 0 | it++; |
1059 | 0 | } |
1060 | 0 | setEntries stage; |
1061 | 0 | for (txiter removeit : toremove) { Branch (1061:26): [True: 0, False: 0]
|
1062 | 0 | CalculateDescendants(removeit, stage); |
1063 | 0 | } |
1064 | 0 | RemoveStaged(stage, false, MemPoolRemovalReason::EXPIRY); |
1065 | 0 | return stage.size(); |
1066 | 0 | } |
1067 | | |
1068 | | void CTxMemPool::addUnchecked(const CTxMemPoolEntry &entry) |
1069 | 0 | { |
1070 | 0 | auto ancestors{AssumeCalculateMemPoolAncestors(__func__, entry, Limits::NoLimits())}; |
1071 | 0 | return addUnchecked(entry, ancestors); |
1072 | 0 | } |
1073 | | |
1074 | | void CTxMemPool::UpdateChild(txiter entry, txiter child, bool add) |
1075 | 0 | { |
1076 | 0 | AssertLockHeld(cs); |
1077 | 0 | CTxMemPoolEntry::Children s; |
1078 | 0 | if (add && entry->GetMemPoolChildren().insert(*child).second) { Branch (1078:9): [True: 0, False: 0]
Branch (1078:9): [True: 0, False: 0]
Branch (1078:16): [True: 0, False: 0]
|
1079 | 0 | cachedInnerUsage += memusage::IncrementalDynamicUsage(s); |
1080 | 0 | } else if (!add && entry->GetMemPoolChildren().erase(*child)) { Branch (1080:16): [True: 0, False: 0]
Branch (1080:16): [True: 0, False: 0]
Branch (1080:24): [True: 0, False: 0]
|
1081 | 0 | cachedInnerUsage -= memusage::IncrementalDynamicUsage(s); |
1082 | 0 | } |
1083 | 0 | } |
1084 | | |
1085 | | void CTxMemPool::UpdateParent(txiter entry, txiter parent, bool add) |
1086 | 0 | { |
1087 | 0 | AssertLockHeld(cs); |
1088 | 0 | CTxMemPoolEntry::Parents s; |
1089 | 0 | if (add && entry->GetMemPoolParents().insert(*parent).second) { Branch (1089:9): [True: 0, False: 0]
Branch (1089:9): [True: 0, False: 0]
Branch (1089:16): [True: 0, False: 0]
|
1090 | 0 | cachedInnerUsage += memusage::IncrementalDynamicUsage(s); |
1091 | 0 | } else if (!add && entry->GetMemPoolParents().erase(*parent)) { Branch (1091:16): [True: 0, False: 0]
Branch (1091:16): [True: 0, False: 0]
Branch (1091:24): [True: 0, False: 0]
|
1092 | 0 | cachedInnerUsage -= memusage::IncrementalDynamicUsage(s); |
1093 | 0 | } |
1094 | 0 | } |
1095 | | |
1096 | 10.5k | CFeeRate CTxMemPool::GetMinFee(size_t sizelimit) const { |
1097 | 10.5k | LOCK(cs); |
1098 | 10.5k | if (!blockSinceLastRollingFeeBump || rollingMinimumFeeRate == 0) Branch (1098:9): [True: 0, False: 10.5k]
Branch (1098:42): [True: 10.5k, False: 0]
|
1099 | 10.5k | return CFeeRate(llround(rollingMinimumFeeRate)); |
1100 | | |
1101 | 0 | int64_t time = GetTime(); |
1102 | 0 | if (time > lastRollingFeeUpdate + 10) { Branch (1102:9): [True: 0, False: 0]
|
1103 | 0 | double halflife = ROLLING_FEE_HALFLIFE; |
1104 | 0 | if (DynamicMemoryUsage() < sizelimit / 4) Branch (1104:13): [True: 0, False: 0]
|
1105 | 0 | halflife /= 4; |
1106 | 0 | else if (DynamicMemoryUsage() < sizelimit / 2) Branch (1106:18): [True: 0, False: 0]
|
1107 | 0 | halflife /= 2; |
1108 | |
|
1109 | 0 | rollingMinimumFeeRate = rollingMinimumFeeRate / pow(2.0, (time - lastRollingFeeUpdate) / halflife); |
1110 | 0 | lastRollingFeeUpdate = time; |
1111 | |
|
1112 | 0 | if (rollingMinimumFeeRate < (double)m_opts.incremental_relay_feerate.GetFeePerK() / 2) { Branch (1112:13): [True: 0, False: 0]
|
1113 | 0 | rollingMinimumFeeRate = 0; |
1114 | 0 | return CFeeRate(0); |
1115 | 0 | } |
1116 | 0 | } |
1117 | 0 | return std::max(CFeeRate(llround(rollingMinimumFeeRate)), m_opts.incremental_relay_feerate); |
1118 | 0 | } |
1119 | | |
1120 | 0 | void CTxMemPool::trackPackageRemoved(const CFeeRate& rate) { |
1121 | 0 | AssertLockHeld(cs); |
1122 | 0 | if (rate.GetFeePerK() > rollingMinimumFeeRate) { Branch (1122:9): [True: 0, False: 0]
|
1123 | 0 | rollingMinimumFeeRate = rate.GetFeePerK(); |
1124 | 0 | blockSinceLastRollingFeeBump = false; |
1125 | 0 | } |
1126 | 0 | } |
1127 | | |
1128 | 0 | void CTxMemPool::TrimToSize(size_t sizelimit, std::vector<COutPoint>* pvNoSpendsRemaining) { |
1129 | 0 | AssertLockHeld(cs); |
1130 | |
|
1131 | 0 | unsigned nTxnRemoved = 0; |
1132 | 0 | CFeeRate maxFeeRateRemoved(0); |
1133 | 0 | while (!mapTx.empty() && DynamicMemoryUsage() > sizelimit) { Branch (1133:12): [True: 0, False: 0]
Branch (1133:30): [True: 0, False: 0]
|
1134 | 0 | indexed_transaction_set::index<descendant_score>::type::iterator it = mapTx.get<descendant_score>().begin(); |
1135 | | |
1136 | | // We set the new mempool min fee to the feerate of the removed set, plus the |
1137 | | // "minimum reasonable fee rate" (ie some value under which we consider txn |
1138 | | // to have 0 fee). This way, we don't allow txn to enter mempool with feerate |
1139 | | // equal to txn which were removed with no block in between. |
1140 | 0 | CFeeRate removed(it->GetModFeesWithDescendants(), it->GetSizeWithDescendants()); |
1141 | 0 | removed += m_opts.incremental_relay_feerate; |
1142 | 0 | trackPackageRemoved(removed); |
1143 | 0 | maxFeeRateRemoved = std::max(maxFeeRateRemoved, removed); |
1144 | |
|
1145 | 0 | setEntries stage; |
1146 | 0 | CalculateDescendants(mapTx.project<0>(it), stage); |
1147 | 0 | nTxnRemoved += stage.size(); |
1148 | |
|
1149 | 0 | std::vector<CTransaction> txn; |
1150 | 0 | if (pvNoSpendsRemaining) { Branch (1150:13): [True: 0, False: 0]
|
1151 | 0 | txn.reserve(stage.size()); |
1152 | 0 | for (txiter iter : stage) Branch (1152:30): [True: 0, False: 0]
|
1153 | 0 | txn.push_back(iter->GetTx()); |
1154 | 0 | } |
1155 | 0 | RemoveStaged(stage, false, MemPoolRemovalReason::SIZELIMIT); |
1156 | 0 | if (pvNoSpendsRemaining) { Branch (1156:13): [True: 0, False: 0]
|
1157 | 0 | for (const CTransaction& tx : txn) { Branch (1157:41): [True: 0, False: 0]
|
1158 | 0 | for (const CTxIn& txin : tx.vin) { Branch (1158:40): [True: 0, False: 0]
|
1159 | 0 | if (exists(GenTxid::Txid(txin.prevout.hash))) continue; Branch (1159:25): [True: 0, False: 0]
|
1160 | 0 | pvNoSpendsRemaining->push_back(txin.prevout); |
1161 | 0 | } |
1162 | 0 | } |
1163 | 0 | } |
1164 | 0 | } |
1165 | |
|
1166 | 0 | if (maxFeeRateRemoved > CFeeRate(0)) { Branch (1166:9): [True: 0, False: 0]
|
1167 | 0 | LogPrint(BCLog::MEMPOOL, "Removed %u txn, rolling minimum fee bumped to %s\n", nTxnRemoved, maxFeeRateRemoved.ToString()); |
1168 | 0 | } |
1169 | 0 | } |
1170 | | |
1171 | 0 | uint64_t CTxMemPool::CalculateDescendantMaximum(txiter entry) const { |
1172 | | // find parent with highest descendant count |
1173 | 0 | std::vector<txiter> candidates; |
1174 | 0 | setEntries counted; |
1175 | 0 | candidates.push_back(entry); |
1176 | 0 | uint64_t maximum = 0; |
1177 | 0 | while (candidates.size()) { Branch (1177:12): [True: 0, False: 0]
|
1178 | 0 | txiter candidate = candidates.back(); |
1179 | 0 | candidates.pop_back(); |
1180 | 0 | if (!counted.insert(candidate).second) continue; Branch (1180:13): [True: 0, False: 0]
|
1181 | 0 | const CTxMemPoolEntry::Parents& parents = candidate->GetMemPoolParentsConst(); |
1182 | 0 | if (parents.size() == 0) { Branch (1182:13): [True: 0, False: 0]
|
1183 | 0 | maximum = std::max(maximum, candidate->GetCountWithDescendants()); |
1184 | 0 | } else { |
1185 | 0 | for (const CTxMemPoolEntry& i : parents) { Branch (1185:43): [True: 0, False: 0]
|
1186 | 0 | candidates.push_back(mapTx.iterator_to(i)); |
1187 | 0 | } |
1188 | 0 | } |
1189 | 0 | } |
1190 | 0 | return maximum; |
1191 | 0 | } |
1192 | | |
1193 | 0 | void CTxMemPool::GetTransactionAncestry(const uint256& txid, size_t& ancestors, size_t& descendants, size_t* const ancestorsize, CAmount* const ancestorfees) const { |
1194 | 0 | LOCK(cs); |
1195 | 0 | auto it = mapTx.find(txid); |
1196 | 0 | ancestors = descendants = 0; |
1197 | 0 | if (it != mapTx.end()) { Branch (1197:9): [True: 0, False: 0]
|
1198 | 0 | ancestors = it->GetCountWithAncestors(); |
1199 | 0 | if (ancestorsize) *ancestorsize = it->GetSizeWithAncestors(); Branch (1199:13): [True: 0, False: 0]
|
1200 | 0 | if (ancestorfees) *ancestorfees = it->GetModFeesWithAncestors(); Branch (1200:13): [True: 0, False: 0]
|
1201 | 0 | descendants = CalculateDescendantMaximum(it); |
1202 | 0 | } |
1203 | 0 | } |
1204 | | |
1205 | | bool CTxMemPool::GetLoadTried() const |
1206 | 0 | { |
1207 | 0 | LOCK(cs); |
1208 | 0 | return m_load_tried; |
1209 | 0 | } |
1210 | | |
1211 | | void CTxMemPool::SetLoadTried(bool load_tried) |
1212 | 0 | { |
1213 | 0 | LOCK(cs); |
1214 | 0 | m_load_tried = load_tried; |
1215 | 0 | } |
1216 | | |
1217 | | std::vector<CTxMemPool::txiter> CTxMemPool::GatherClusters(const std::vector<uint256>& txids) const |
1218 | 0 | { |
1219 | 0 | AssertLockHeld(cs); |
1220 | 0 | std::vector<txiter> clustered_txs{GetIterVec(txids)}; |
1221 | | // Use epoch: visiting an entry means we have added it to the clustered_txs vector. It does not |
1222 | | // necessarily mean the entry has been processed. |
1223 | 0 | WITH_FRESH_EPOCH(m_epoch); |
1224 | 0 | for (const auto& it : clustered_txs) { Branch (1224:25): [True: 0, False: 0]
|
1225 | 0 | visited(it); |
1226 | 0 | } |
1227 | | // i = index of where the list of entries to process starts |
1228 | 0 | for (size_t i{0}; i < clustered_txs.size(); ++i) { Branch (1228:23): [True: 0, False: 0]
|
1229 | | // DoS protection: if there are 500 or more entries to process, just quit. |
1230 | 0 | if (clustered_txs.size() > 500) return {}; Branch (1230:13): [True: 0, False: 0]
|
1231 | 0 | const txiter& tx_iter = clustered_txs.at(i); |
1232 | 0 | for (const auto& entries : {tx_iter->GetMemPoolParentsConst(), tx_iter->GetMemPoolChildrenConst()}) { Branch (1232:34): [True: 0, False: 0]
|
1233 | 0 | for (const CTxMemPoolEntry& entry : entries) { Branch (1233:47): [True: 0, False: 0]
|
1234 | 0 | const auto entry_it = mapTx.iterator_to(entry); |
1235 | 0 | if (!visited(entry_it)) { Branch (1235:21): [True: 0, False: 0]
|
1236 | 0 | clustered_txs.push_back(entry_it); |
1237 | 0 | } |
1238 | 0 | } |
1239 | 0 | } |
1240 | 0 | } |
1241 | 0 | return clustered_txs; |
1242 | 0 | } |
1243 | | |
1244 | | std::optional<std::string> CTxMemPool::CheckConflictTopology(const setEntries& direct_conflicts) |
1245 | 0 | { |
1246 | 0 | for (const auto& direct_conflict : direct_conflicts) { Branch (1246:38): [True: 0, False: 0]
|
1247 | | // Ancestor and descendant counts are inclusive of the tx itself. |
1248 | 0 | const auto ancestor_count{direct_conflict->GetCountWithAncestors()}; |
1249 | 0 | const auto descendant_count{direct_conflict->GetCountWithDescendants()}; |
1250 | 0 | const bool has_ancestor{ancestor_count > 1}; |
1251 | 0 | const bool has_descendant{descendant_count > 1}; |
1252 | 0 | const auto& txid_string{direct_conflict->GetSharedTx()->GetHash().ToString()}; |
1253 | | // The only allowed configurations are: |
1254 | | // 1 ancestor and 0 descendant |
1255 | | // 0 ancestor and 1 descendant |
1256 | | // 0 ancestor and 0 descendant |
1257 | 0 | if (ancestor_count > 2) { Branch (1257:13): [True: 0, False: 0]
|
1258 | 0 | return strprintf("%s has %u ancestors, max 1 allowed", txid_string, ancestor_count - 1); |
1259 | 0 | } else if (descendant_count > 2) { Branch (1259:20): [True: 0, False: 0]
|
1260 | 0 | return strprintf("%s has %u descendants, max 1 allowed", txid_string, descendant_count - 1); |
1261 | 0 | } else if (has_ancestor && has_descendant) { Branch (1261:20): [True: 0, False: 0]
Branch (1261:36): [True: 0, False: 0]
|
1262 | 0 | return strprintf("%s has both ancestor and descendant, exceeding cluster limit of 2", txid_string); |
1263 | 0 | } |
1264 | | // Additionally enforce that: |
1265 | | // If we have a child, we are its only parent. |
1266 | | // If we have a parent, we are its only child. |
1267 | 0 | if (has_descendant) { Branch (1267:13): [True: 0, False: 0]
|
1268 | 0 | const auto& our_child = direct_conflict->GetMemPoolChildrenConst().begin(); |
1269 | 0 | if (our_child->get().GetCountWithAncestors() > 2) { Branch (1269:17): [True: 0, False: 0]
|
1270 | 0 | return strprintf("%s is not the only parent of child %s", |
1271 | 0 | txid_string, our_child->get().GetSharedTx()->GetHash().ToString()); |
1272 | 0 | } |
1273 | 0 | } else if (has_ancestor) { Branch (1273:20): [True: 0, False: 0]
|
1274 | 0 | const auto& our_parent = direct_conflict->GetMemPoolParentsConst().begin(); |
1275 | 0 | if (our_parent->get().GetCountWithDescendants() > 2) { Branch (1275:17): [True: 0, False: 0]
|
1276 | 0 | return strprintf("%s is not the only child of parent %s", |
1277 | 0 | txid_string, our_parent->get().GetSharedTx()->GetHash().ToString()); |
1278 | 0 | } |
1279 | 0 | } |
1280 | 0 | } |
1281 | 0 | return std::nullopt; |
1282 | 0 | } |
1283 | | |
1284 | | util::Result<std::pair<std::vector<FeeFrac>, std::vector<FeeFrac>>> CTxMemPool::CalculateChunksForRBF(CAmount replacement_fees, int64_t replacement_vsize, const setEntries& direct_conflicts, const setEntries& all_conflicts) |
1285 | 0 | { |
1286 | 0 | Assume(replacement_vsize > 0); |
1287 | |
|
1288 | 0 | auto err_string{CheckConflictTopology(direct_conflicts)}; |
1289 | 0 | if (err_string.has_value()) { Branch (1289:9): [True: 0, False: 0]
|
1290 | | // Unsupported topology for calculating a feerate diagram |
1291 | 0 | return util::Error{Untranslated(err_string.value())}; |
1292 | 0 | } |
1293 | | |
1294 | | // new diagram will have chunks that consist of each ancestor of |
1295 | | // direct_conflicts that is at its own fee/size, along with the replacement |
1296 | | // tx/package at its own fee/size |
1297 | | |
1298 | | // old diagram will consist of the ancestors and descendants of each element of |
1299 | | // all_conflicts. every such transaction will either be at its own feerate (followed |
1300 | | // by any descendant at its own feerate), or as a single chunk at the descendant's |
1301 | | // ancestor feerate. |
1302 | | |
1303 | 0 | std::vector<FeeFrac> old_chunks; |
1304 | | // Step 1: build the old diagram. |
1305 | | |
1306 | | // The above clusters are all trivially linearized; |
1307 | | // they have a strict topology of 1 or two connected transactions. |
1308 | | |
1309 | | // OLD: Compute existing chunks from all affected clusters |
1310 | 0 | for (auto txiter : all_conflicts) { Branch (1310:22): [True: 0, False: 0]
|
1311 | | // Does this transaction have descendants? |
1312 | 0 | if (txiter->GetCountWithDescendants() > 1) { Branch (1312:13): [True: 0, False: 0]
|
1313 | | // Consider this tx when we consider the descendant. |
1314 | 0 | continue; |
1315 | 0 | } |
1316 | | // Does this transaction have ancestors? |
1317 | 0 | FeeFrac individual{txiter->GetModifiedFee(), txiter->GetTxSize()}; |
1318 | 0 | if (txiter->GetCountWithAncestors() > 1) { Branch (1318:13): [True: 0, False: 0]
|
1319 | | // We'll add chunks for either the ancestor by itself and this tx |
1320 | | // by itself, or for a combined package. |
1321 | 0 | FeeFrac package{txiter->GetModFeesWithAncestors(), static_cast<int32_t>(txiter->GetSizeWithAncestors())}; |
1322 | 0 | if (individual >> package) { Branch (1322:17): [True: 0, False: 0]
|
1323 | | // The individual feerate is higher than the package, and |
1324 | | // therefore higher than the parent's fee. Chunk these |
1325 | | // together. |
1326 | 0 | old_chunks.emplace_back(package); |
1327 | 0 | } else { |
1328 | | // Add two points, one for the parent and one for this child. |
1329 | 0 | old_chunks.emplace_back(package - individual); |
1330 | 0 | old_chunks.emplace_back(individual); |
1331 | 0 | } |
1332 | 0 | } else { |
1333 | 0 | old_chunks.emplace_back(individual); |
1334 | 0 | } |
1335 | 0 | } |
1336 | | |
1337 | | // No topology restrictions post-chunking; sort |
1338 | 0 | std::sort(old_chunks.begin(), old_chunks.end(), std::greater()); |
1339 | |
|
1340 | 0 | std::vector<FeeFrac> new_chunks; |
1341 | | |
1342 | | /* Step 2: build the NEW diagram |
1343 | | * CON = Conflicts of proposed chunk |
1344 | | * CNK = Proposed chunk |
1345 | | * NEW = OLD - CON + CNK: New diagram includes all chunks in OLD, minus |
1346 | | * the conflicts, plus the proposed chunk |
1347 | | */ |
1348 | | |
1349 | | // OLD - CON: Add any parents of direct conflicts that are not conflicted themselves |
1350 | 0 | for (auto direct_conflict : direct_conflicts) { Branch (1350:31): [True: 0, False: 0]
|
1351 | | // If a direct conflict has an ancestor that is not in all_conflicts, |
1352 | | // it can be affected by the replacement of the child. |
1353 | 0 | if (direct_conflict->GetMemPoolParentsConst().size() > 0) { Branch (1353:13): [True: 0, False: 0]
|
1354 | | // Grab the parent. |
1355 | 0 | const CTxMemPoolEntry& parent = direct_conflict->GetMemPoolParentsConst().begin()->get(); |
1356 | 0 | if (!all_conflicts.count(mapTx.iterator_to(parent))) { Branch (1356:17): [True: 0, False: 0]
|
1357 | | // This transaction would be left over, so add to the NEW |
1358 | | // diagram. |
1359 | 0 | new_chunks.emplace_back(parent.GetModifiedFee(), parent.GetTxSize()); |
1360 | 0 | } |
1361 | 0 | } |
1362 | 0 | } |
1363 | | // + CNK: Add the proposed chunk itself |
1364 | 0 | new_chunks.emplace_back(replacement_fees, int32_t(replacement_vsize)); |
1365 | | |
1366 | | // No topology restrictions post-chunking; sort |
1367 | 0 | std::sort(new_chunks.begin(), new_chunks.end(), std::greater()); |
1368 | 0 | return std::make_pair(old_chunks, new_chunks); |
1369 | 0 | } |