Line data Source code
1 : // Copyright (c) 2009-2010 Satoshi Nakamoto
2 : // Copyright (c) 2009-2014 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 "clientversion.h"
9 : #include "consensus/consensus.h"
10 : #include "consensus/validation.h"
11 : #include "main.h"
12 : #include "policy/fees.h"
13 : #include "streams.h"
14 : #include "util.h"
15 : #include "utilmoneystr.h"
16 : #include "version.h"
17 :
18 : using namespace std;
19 :
20 17445 : CTxMemPoolEntry::CTxMemPoolEntry(const CTransaction& _tx, const CAmount& _nFee,
21 : int64_t _nTime, double _dPriority,
22 : unsigned int _nHeight, bool poolHasNoInputsOf):
23 : tx(_tx), nFee(_nFee), nTime(_nTime), dPriority(_dPriority), nHeight(_nHeight),
24 17445 : hadNoDependencies(poolHasNoInputsOf)
25 : {
26 34890 : nTxSize = ::GetSerializeSize(tx, SER_NETWORK, PROTOCOL_VERSION);
27 17445 : nModSize = tx.CalculateModifiedSize(nTxSize);
28 17445 : nUsageSize = RecursiveDynamicUsage(tx);
29 :
30 17445 : nCountWithDescendants = 1;
31 17445 : nSizeWithDescendants = nTxSize;
32 17445 : nFeesWithDescendants = nFee;
33 17445 : }
34 :
35 56505 : CTxMemPoolEntry::CTxMemPoolEntry(const CTxMemPoolEntry& other)
36 : {
37 56505 : *this = other;
38 56505 : }
39 :
40 : double
41 31649 : CTxMemPoolEntry::GetPriority(unsigned int currentHeight) const
42 : {
43 31649 : CAmount nValueIn = tx.GetValueOut()+nFee;
44 31649 : double deltaPriority = ((double)(currentHeight-nHeight)*nValueIn)/nModSize;
45 31649 : double dResult = dPriority + deltaPriority;
46 31649 : return dResult;
47 : }
48 :
49 : // Update the given tx for any in-mempool descendants.
50 : // Assumes that setMemPoolChildren is correct for the given tx and all
51 : // descendants.
52 31 : bool CTxMemPool::UpdateForDescendants(txiter updateIt, int maxDescendantsToVisit, cacheMap &cachedDescendants, const std::set<uint256> &setExclude)
53 : {
54 : // Track the number of entries (outside setExclude) that we'd need to visit
55 : // (will bail out if it exceeds maxDescendantsToVisit)
56 31 : int nChildrenToVisit = 0;
57 :
58 : setEntries stageEntries, setAllDescendants;
59 31 : stageEntries = GetMemPoolChildren(updateIt);
60 :
61 46 : while (!stageEntries.empty()) {
62 30 : const txiter cit = *stageEntries.begin();
63 15 : if (cit->IsDirty()) {
64 : // Don't consider any more children if any descendant is dirty
65 0 : return false;
66 : }
67 : setAllDescendants.insert(cit);
68 : stageEntries.erase(cit);
69 15 : const setEntries &setChildren = GetMemPoolChildren(cit);
70 87 : BOOST_FOREACH(const txiter childEntry, setChildren) {
71 2 : cacheMap::iterator cacheIt = cachedDescendants.find(childEntry);
72 2 : if (cacheIt != cachedDescendants.end()) {
73 : // We've already calculated this one, just add the entries for this set
74 : // but don't traverse again.
75 0 : BOOST_FOREACH(const txiter cacheEntry, cacheIt->second) {
76 : // update visit count only for new child transactions
77 : // (outside of setExclude and stageEntries)
78 0 : if (setAllDescendants.insert(cacheEntry).second &&
79 0 : !setExclude.count(cacheEntry->GetTx().GetHash()) &&
80 : !stageEntries.count(cacheEntry)) {
81 0 : nChildrenToVisit++;
82 : }
83 : }
84 2 : } else if (!setAllDescendants.count(childEntry)) {
85 : // Schedule for later processing and update our visit count
86 10 : if (stageEntries.insert(childEntry).second && !setExclude.count(childEntry->GetTx().GetHash())) {
87 0 : nChildrenToVisit++;
88 : }
89 : }
90 2 : if (nChildrenToVisit > maxDescendantsToVisit) {
91 : return false;
92 : }
93 : }
94 : }
95 : // setAllDescendants now contains all in-mempool descendants of updateIt.
96 : // Update and add to cached descendant map
97 31 : int64_t modifySize = 0;
98 31 : CAmount modifyFee = 0;
99 31 : int64_t modifyCount = 0;
100 276 : BOOST_FOREACH(txiter cit, setAllDescendants) {
101 60 : if (!setExclude.count(cit->GetTx().GetHash())) {
102 7 : modifySize += cit->GetTxSize();
103 7 : modifyFee += cit->GetFee();
104 7 : modifyCount++;
105 7 : cachedDescendants[updateIt].insert(cit);
106 : }
107 : }
108 31 : mapTx.modify(updateIt, update_descendant_state(modifySize, modifyFee, modifyCount));
109 31 : return true;
110 : }
111 :
112 : // vHashesToUpdate is the set of transaction hashes from a disconnected block
113 : // which has been re-added to the mempool.
114 : // for each entry, look for descendants that are outside hashesToUpdate, and
115 : // add fee/size information for such descendants to the parent.
116 52 : void CTxMemPool::UpdateTransactionsFromBlock(const std::vector<uint256> &vHashesToUpdate)
117 : {
118 52 : LOCK(cs);
119 : // For each entry in vHashesToUpdate, store the set of in-mempool, but not
120 : // in-vHashesToUpdate transactions, so that we don't have to recalculate
121 : // descendants when we come across a previously seen entry.
122 : cacheMap mapMemPoolDescendantsToUpdate;
123 :
124 : // Use a set for lookups into vHashesToUpdate (these entries are already
125 : // accounted for in the state of their ancestors)
126 156 : std::set<uint256> setAlreadyIncluded(vHashesToUpdate.begin(), vHashesToUpdate.end());
127 :
128 : // Iterate in reverse, so that whenever we are looking at at a transaction
129 : // we are sure that all in-mempool descendants have already been processed.
130 : // This maximizes the benefit of the descendant cache and guarantees that
131 : // setMemPoolChildren will be updated, an assumption made in
132 : // UpdateForDescendants.
133 446 : BOOST_REVERSE_FOREACH(const uint256 &hash, vHashesToUpdate) {
134 : // we cache the in-mempool children to avoid duplicate updates
135 : setEntries setChildren;
136 : // calculate children from mapNextTx
137 31 : txiter it = mapTx.find(hash);
138 93 : if (it == mapTx.end()) {
139 : continue;
140 : }
141 62 : std::map<COutPoint, CInPoint>::iterator iter = mapNextTx.lower_bound(COutPoint(hash, 0));
142 : // First calculate the children, and update setMemPoolChildren to
143 : // include them, and update their setMemPoolParents to include this tx.
144 197 : for (; iter != mapNextTx.end() && iter->first.hash == hash; ++iter) {
145 26 : const uint256 &childHash = iter->second.ptx->GetHash();
146 13 : txiter childIter = mapTx.find(childHash);
147 39 : assert(childIter != mapTx.end());
148 : // We can skip updating entries we've encountered before or that
149 : // are in the block (which are already accounted for).
150 26 : if (setChildren.insert(childIter).second && !setAlreadyIncluded.count(childHash)) {
151 7 : UpdateChild(it, childIter, true);
152 7 : UpdateParent(childIter, it, true);
153 : }
154 : }
155 31 : if (!UpdateForDescendants(it, 100, mapMemPoolDescendantsToUpdate, setAlreadyIncluded)) {
156 : // Mark as dirty if we can't do the calculation.
157 0 : mapTx.modify(it, set_dirty());
158 : }
159 : }
160 52 : }
161 :
162 33714 : bool CTxMemPool::CalculateMemPoolAncestors(const CTxMemPoolEntry &entry, setEntries &setAncestors, uint64_t limitAncestorCount, uint64_t limitAncestorSize, uint64_t limitDescendantCount, uint64_t limitDescendantSize, std::string &errString, bool fSearchForParents /* = true */)
163 : {
164 : setEntries parentHashes;
165 33714 : const CTransaction &tx = entry.GetTx();
166 :
167 33714 : if (fSearchForParents) {
168 : // Get parents of this transaction that are in the mempool
169 : // GetMemPoolParents() is only valid for entries in the mempool, so we
170 : // iterate mapTx to find parents.
171 53263 : for (unsigned int i = 0; i < tx.vin.size(); i++) {
172 35822 : txiter piter = mapTx.find(tx.vin[i].prevout.hash);
173 53733 : if (piter != mapTx.end()) {
174 : parentHashes.insert(piter);
175 1201 : if (parentHashes.size() + 1 > limitAncestorCount) {
176 0 : errString = strprintf("too many unconfirmed parents [limit: %u]", limitAncestorCount);
177 0 : return false;
178 : }
179 : }
180 : }
181 : } else {
182 : // If we're not searching for parents, we require this to be an
183 : // entry in the mempool already.
184 32546 : txiter it = mapTx.iterator_to(entry);
185 16273 : parentHashes = GetMemPoolParents(it);
186 : }
187 :
188 33714 : size_t totalSizeWithAncestors = entry.GetTxSize();
189 :
190 576166 : while (!parentHashes.empty()) {
191 1017476 : txiter stageit = *parentHashes.begin();
192 :
193 : setAncestors.insert(stageit);
194 : parentHashes.erase(stageit);
195 508738 : totalSizeWithAncestors += stageit->GetTxSize();
196 :
197 508738 : if (stageit->GetSizeWithDescendants() + entry.GetTxSize() > limitDescendantSize) {
198 0 : errString = strprintf("exceeds descendant size limit for tx %s [limit: %u]", stageit->GetTx().GetHash().ToString(), limitDescendantSize);
199 0 : return false;
200 508738 : } else if (stageit->GetCountWithDescendants() + 1 > limitDescendantCount) {
201 0 : errString = strprintf("too many descendants for tx %s [limit: %u]", stageit->GetTx().GetHash().ToString(), limitDescendantCount);
202 0 : return false;
203 508738 : } else if (totalSizeWithAncestors > limitAncestorSize) {
204 0 : errString = strprintf("exceeds ancestor size limit [limit: %u]", limitAncestorSize);
205 0 : return false;
206 : }
207 :
208 508738 : const setEntries & setMemPoolParents = GetMemPoolParents(stageit);
209 5588846 : BOOST_FOREACH(const txiter &phash, setMemPoolParents) {
210 : // If this is a new ancestor, add it.
211 507526 : if (setAncestors.count(phash) == 0) {
212 : parentHashes.insert(phash);
213 : }
214 1015052 : if (parentHashes.size() + setAncestors.size() + 1 > limitAncestorCount) {
215 0 : errString = strprintf("too many unconfirmed ancestors [limit: %u]", limitAncestorCount);
216 0 : return false;
217 : }
218 : }
219 : }
220 :
221 : return true;
222 : }
223 :
224 33710 : void CTxMemPool::UpdateAncestorsOf(bool add, txiter it, setEntries &setAncestors)
225 : {
226 33710 : setEntries parentIters = GetMemPoolParents(it);
227 : // add or remove this tx as a child of each parent
228 209568 : BOOST_FOREACH(txiter piter, parentIters) {
229 1218 : UpdateChild(piter, it, add);
230 : }
231 33710 : const int64_t updateCount = (add ? 1 : -1);
232 33710 : const int64_t updateSize = updateCount * it->GetTxSize();
233 33710 : const CAmount updateFee = updateCount * it->GetFee();
234 3254712 : BOOST_FOREACH(txiter ancestorIt, setAncestors) {
235 508742 : mapTx.modify(ancestorIt, update_descendant_state(updateSize, updateFee, updateCount));
236 : }
237 33710 : }
238 :
239 16273 : void CTxMemPool::UpdateChildrenForRemoval(txiter it)
240 : {
241 16273 : const setEntries &setMemPoolChildren = GetMemPoolChildren(it);
242 81731 : BOOST_FOREACH(txiter updateIt, setMemPoolChildren) {
243 61 : UpdateParent(updateIt, it, false);
244 : }
245 16273 : }
246 :
247 21968 : void CTxMemPool::UpdateForRemoveFromMempool(const setEntries &entriesToRemove)
248 : {
249 : // For each entry, walk back all ancestors and decrement size associated with this
250 : // transaction
251 21968 : const uint64_t nNoLimit = std::numeric_limits<uint64_t>::max();
252 191205 : BOOST_FOREACH(txiter removeIt, entriesToRemove) {
253 : setEntries setAncestors;
254 16273 : const CTxMemPoolEntry &entry = *removeIt;
255 : std::string dummy;
256 : // Since this is a tx that is already in the mempool, we can call CMPA
257 : // with fSearchForParents = false. If the mempool is in a consistent
258 : // state, then using true or false should both be correct, though false
259 : // should be a bit faster.
260 : // However, if we happen to be in the middle of processing a reorg, then
261 : // the mempool can be in an inconsistent state. In this case, the set
262 : // of ancestors reachable via mapLinks will be the same as the set of
263 : // ancestors whose packages include this transaction, because when we
264 : // add a new transaction to the mempool in addUnchecked(), we assume it
265 : // has no children, and in the case of a reorg where that assumption is
266 : // false, the in-mempool children aren't linked to the in-block tx's
267 : // until UpdateTransactionsFromBlock() is called.
268 : // So if we're being called during a reorg, ie before
269 : // UpdateTransactionsFromBlock() has been called, then mapLinks[] will
270 : // differ from the set of mempool parents we'd calculate by searching,
271 : // and it's important that we use the mapLinks[] notion of ancestor
272 : // transactions as the set of things to update for removal.
273 16273 : CalculateMemPoolAncestors(entry, setAncestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy, false);
274 : // Note that UpdateAncestorsOf severs the child links that point to
275 : // removeIt in the entries for the parents of removeIt. This is
276 : // fine since we don't need to use the mempool children of any entries
277 : // to walk back over our ancestors (but we do need the mempool
278 : // parents!)
279 16273 : UpdateAncestorsOf(false, removeIt, setAncestors);
280 : }
281 : // After updating all the ancestor sizes, we can now sever the link between each
282 : // transaction being removed and any mempool children (ie, update setMemPoolParents
283 : // for each direct child of a transaction being removed).
284 207478 : BOOST_FOREACH(txiter removeIt, entriesToRemove) {
285 16273 : UpdateChildrenForRemoval(removeIt);
286 : }
287 21968 : }
288 :
289 0 : void CTxMemPoolEntry::SetDirty()
290 : {
291 0 : nCountWithDescendants = 0;
292 0 : nSizeWithDescendants = nTxSize;
293 0 : nFeesWithDescendants = nFee;
294 0 : }
295 :
296 508773 : void CTxMemPoolEntry::UpdateState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount)
297 : {
298 508773 : if (!IsDirty()) {
299 508773 : nSizeWithDescendants += modifySize;
300 508773 : assert(int64_t(nSizeWithDescendants) > 0);
301 508773 : nFeesWithDescendants += modifyFee;
302 508773 : assert(nFeesWithDescendants >= 0);
303 508773 : nCountWithDescendants += modifyCount;
304 508773 : assert(int64_t(nCountWithDescendants) > 0);
305 : }
306 508773 : }
307 :
308 99 : CTxMemPool::CTxMemPool(const CFeeRate& _minRelayFee) :
309 495 : nTransactionsUpdated(0)
310 : {
311 : // Sanity checks off by default for performance, because otherwise
312 : // accepting transactions becomes O(N^2) where N is the number
313 : // of transactions in the pool
314 99 : fSanityCheck = false;
315 :
316 99 : minerPolicyEstimator = new CBlockPolicyEstimator(_minRelayFee);
317 99 : }
318 :
319 594 : CTxMemPool::~CTxMemPool()
320 : {
321 99 : delete minerPolicyEstimator;
322 99 : }
323 :
324 18 : void CTxMemPool::pruneSpent(const uint256 &hashTx, CCoins &coins)
325 : {
326 18 : LOCK(cs);
327 :
328 36 : std::map<COutPoint, CInPoint>::iterator it = mapNextTx.lower_bound(COutPoint(hashTx, 0));
329 :
330 : // iterate over all COutPoints in mapNextTx whose hash equals the provided hashTx
331 86 : while (it != mapNextTx.end() && it->first.hash == hashTx) {
332 0 : coins.Spend(it->first.n); // and remove those outputs from coins
333 0 : it++;
334 : }
335 18 : }
336 :
337 0 : unsigned int CTxMemPool::GetTransactionsUpdated() const
338 : {
339 0 : LOCK(cs);
340 0 : return nTransactionsUpdated;
341 : }
342 :
343 5648 : void CTxMemPool::AddTransactionsUpdated(unsigned int n)
344 : {
345 5648 : LOCK(cs);
346 5648 : nTransactionsUpdated += n;
347 5648 : }
348 :
349 17437 : bool CTxMemPool::addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry, setEntries &setAncestors, bool fCurrentEstimate)
350 : {
351 : // Add to memory pool without checking anything.
352 : // Used by main.cpp AcceptToMemoryPool(), which DOES do
353 : // all the appropriate checks.
354 17437 : LOCK(cs);
355 34874 : indexed_transaction_set::iterator newit = mapTx.insert(entry).first;
356 69748 : mapLinks.insert(make_pair(newit, TxLinks()));
357 :
358 : // Update cachedInnerUsage to include contained transaction's usage.
359 : // (When we update the entry for in-mempool parents, memory usage will be
360 : // further updated.)
361 17437 : cachedInnerUsage += entry.DynamicMemoryUsage();
362 :
363 34874 : const CTransaction& tx = newit->GetTx();
364 : std::set<uint256> setParentTransactions;
365 70688 : for (unsigned int i = 0; i < tx.vin.size(); i++) {
366 35814 : mapNextTx[tx.vin[i].prevout] = CInPoint(&tx, i);
367 35814 : setParentTransactions.insert(tx.vin[i].prevout.hash);
368 : }
369 : // Don't bother worrying about child transactions of this one.
370 : // Normal case of a new transaction arriving is that there can't be any
371 : // children, because such children would be orphans.
372 : // An exception to that is if a transaction enters that used to be in a block.
373 : // In that case, our disconnect block logic will call UpdateTransactionsFromBlock
374 : // to clean up the mess we're leaving here.
375 :
376 : // Update ancestors with information about this tx
377 194077 : BOOST_FOREACH (const uint256 &phash, setParentTransactions) {
378 17891 : txiter pit = mapTx.find(phash);
379 53673 : if (pit != mapTx.end()) {
380 1203 : UpdateParent(newit, pit, true);
381 : }
382 : }
383 17437 : UpdateAncestorsOf(true, newit, setAncestors);
384 :
385 17437 : nTransactionsUpdated++;
386 17437 : totalTxSize += entry.GetTxSize();
387 17437 : minerPolicyEstimator->processTransaction(entry, fCurrentEstimate);
388 :
389 34874 : return true;
390 : }
391 :
392 16273 : void CTxMemPool::removeUnchecked(txiter it)
393 : {
394 32546 : const uint256 hash = it->GetTx().GetHash();
395 198102 : BOOST_FOREACH(const CTxIn& txin, it->GetTx().vin)
396 16744 : mapNextTx.erase(txin.prevout);
397 :
398 16273 : totalTxSize -= it->GetTxSize();
399 16273 : cachedInnerUsage -= it->DynamicMemoryUsage();
400 48819 : cachedInnerUsage -= memusage::DynamicUsage(mapLinks[it].parents) + memusage::DynamicUsage(mapLinks[it].children);
401 16273 : mapLinks.erase(it);
402 16273 : mapTx.erase(it);
403 16273 : nTransactionsUpdated++;
404 16273 : minerPolicyEstimator->removeTx(hash);
405 16273 : }
406 :
407 : // Calculates descendants of entry that are not already in setDescendants, and adds to
408 : // setDescendants. Assumes entryit is already a tx in the mempool and setMemPoolChildren
409 : // is correct for tx and all descendants.
410 : // Also assumes that if an entry is in setDescendants already, then all
411 : // in-mempool descendants of it are already in setDescendants as well, so that we
412 : // can save time by not iterating over those entries.
413 27 : void CTxMemPool::CalculateDescendants(txiter entryit, setEntries &setDescendants)
414 : {
415 : setEntries stage;
416 27 : if (setDescendants.count(entryit) == 0) {
417 : stage.insert(entryit);
418 : }
419 : // Traverse down the children of entry, only adding children that are not
420 : // accounted for in setDescendants already (because those children have either
421 : // already been walked, or will be walked in this iteration).
422 66 : while (!stage.empty()) {
423 78 : txiter it = *stage.begin();
424 : setDescendants.insert(it);
425 : stage.erase(it);
426 :
427 39 : const setEntries &setChildren = GetMemPoolChildren(it);
428 267 : BOOST_FOREACH(const txiter &childiter, setChildren) {
429 12 : if (!setDescendants.count(childiter)) {
430 : stage.insert(childiter);
431 : }
432 : }
433 : }
434 27 : }
435 :
436 21968 : void CTxMemPool::remove(const CTransaction &origTx, std::list<CTransaction>& removed, bool fRecursive)
437 : {
438 : // Remove transaction from memory pool
439 : {
440 21968 : LOCK(cs);
441 : setEntries txToRemove;
442 21968 : txiter origit = mapTx.find(origTx.GetHash());
443 65904 : if (origit != mapTx.end()) {
444 : txToRemove.insert(origit);
445 5710 : } else if (fRecursive) {
446 : // If recursively removing but origTx isn't in the mempool
447 : // be sure to remove any children that are in the pool. This can
448 : // happen during chain re-orgs if origTx isn't re-accepted into
449 : // the mempool for any reason.
450 207 : for (unsigned int i = 0; i < origTx.vout.size(); i++) {
451 216 : std::map<COutPoint, CInPoint>::iterator it = mapNextTx.find(COutPoint(origTx.GetHash(), i));
452 144 : if (it == mapNextTx.end())
453 69 : continue;
454 6 : txiter nextit = mapTx.find(it->second.ptx->GetHash());
455 9 : assert(nextit != mapTx.end());
456 : txToRemove.insert(nextit);
457 : }
458 : }
459 : setEntries setAllRemoves;
460 21968 : if (fRecursive) {
461 684 : BOOST_FOREACH(txiter it, txToRemove) {
462 27 : CalculateDescendants(it, setAllRemoves);
463 : }
464 : } else {
465 : setAllRemoves.swap(txToRemove);
466 : }
467 229446 : BOOST_FOREACH(txiter it, setAllRemoves) {
468 32546 : removed.push_back(it->GetTx());
469 : }
470 21968 : RemoveStaged(setAllRemoves);
471 : }
472 21968 : }
473 :
474 52 : void CTxMemPool::removeCoinbaseSpends(const CCoinsViewCache *pcoins, unsigned int nMemPoolHeight)
475 : {
476 : // Remove transactions spending a coinbase which are now immature
477 52 : LOCK(cs);
478 : list<CTransaction> transactionsToRemove;
479 552 : for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
480 146 : const CTransaction& tx = it->GetTx();
481 1077 : BOOST_FOREACH(const CTxIn& txin, tx.vin) {
482 121 : indexed_transaction_set::const_iterator it2 = mapTx.find(txin.prevout.hash);
483 363 : if (it2 != mapTx.end())
484 23 : continue;
485 98 : const CCoins *coins = pcoins->AccessCoins(txin.prevout.hash);
486 98 : if (fSanityCheck) assert(coins);
487 98 : if (!coins || (coins->IsCoinBase() && ((signed long)nMemPoolHeight) - coins->nHeight < COINBASE_MATURITY)) {
488 : transactionsToRemove.push_back(tx);
489 7 : break;
490 : }
491 : }
492 : }
493 347 : BOOST_FOREACH(const CTransaction& tx, transactionsToRemove) {
494 : list<CTransaction> removed;
495 7 : remove(tx, removed, true);
496 : }
497 52 : }
498 :
499 21881 : void CTxMemPool::removeConflicts(const CTransaction &tx, std::list<CTransaction>& removed)
500 : {
501 : // Remove transactions which depend on inputs of tx, recursively
502 : list<CTransaction> result;
503 21881 : LOCK(cs);
504 243595 : BOOST_FOREACH(const CTxIn &txin, tx.vin) {
505 44730 : std::map<COutPoint, CInPoint>::iterator it = mapNextTx.find(txin.prevout);
506 44730 : if (it != mapNextTx.end()) {
507 13 : const CTransaction &txConflict = *it->second.ptx;
508 13 : if (txConflict != tx)
509 : {
510 13 : remove(txConflict, removed, true);
511 : }
512 : }
513 : }
514 21881 : }
515 :
516 : /**
517 : * Called when a block is connected. Removes from mempool and updates the miner fee estimator.
518 : */
519 5868 : void CTxMemPool::removeForBlock(const std::vector<CTransaction>& vtx, unsigned int nBlockHeight,
520 : std::list<CTransaction>& conflicts, bool fCurrentEstimate)
521 : {
522 5868 : LOCK(cs);
523 5868 : std::vector<CTxMemPoolEntry> entries;
524 138745 : BOOST_FOREACH(const CTransaction& tx, vtx)
525 : {
526 21881 : uint256 hash = tx.GetHash();
527 :
528 21881 : indexed_transaction_set::iterator i = mapTx.find(hash);
529 65643 : if (i != mapTx.end())
530 16234 : entries.push_back(*i);
531 : }
532 138745 : BOOST_FOREACH(const CTransaction& tx, vtx)
533 : {
534 : std::list<CTransaction> dummy;
535 21881 : remove(tx, dummy, false);
536 21881 : removeConflicts(tx, conflicts);
537 21881 : ClearPrioritisation(tx.GetHash());
538 : }
539 : // After the txs in the new block have been removed from the mempool, update policy estimates
540 5868 : minerPolicyEstimator->processBlock(nBlockHeight, entries, fCurrentEstimate);
541 5868 : }
542 :
543 129 : void CTxMemPool::clear()
544 : {
545 129 : LOCK(cs);
546 129 : mapLinks.clear();
547 129 : mapTx.clear();
548 129 : mapNextTx.clear();
549 129 : totalTxSize = 0;
550 129 : cachedInnerUsage = 0;
551 129 : ++nTransactionsUpdated;
552 129 : }
553 :
554 11459 : void CTxMemPool::check(const CCoinsViewCache *pcoins) const
555 : {
556 11459 : if (!fSanityCheck)
557 744 : return;
558 :
559 21430 : LogPrint("mempool", "Checking mempool with %u transactions and %u inputs\n", (unsigned int)mapTx.size(), (unsigned int)mapNextTx.size());
560 :
561 10715 : uint64_t checkTotal = 0;
562 10715 : uint64_t innerUsage = 0;
563 :
564 10715 : CCoinsViewCache mempoolDuplicate(const_cast<CCoinsViewCache*>(pcoins));
565 :
566 10715 : LOCK(cs);
567 : list<const CTxMemPoolEntry*> waitingOnDependants;
568 63027 : for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
569 2363 : unsigned int i = 0;
570 2363 : checkTotal += it->GetTxSize();
571 2363 : innerUsage += it->DynamicMemoryUsage();
572 4726 : const CTransaction& tx = it->GetTx();
573 4726 : txlinksMap::const_iterator linksiter = mapLinks.find(it);
574 4726 : assert(linksiter != mapLinks.end());
575 2363 : const TxLinks &links = linksiter->second;
576 7089 : innerUsage += memusage::DynamicUsage(links.parents) + memusage::DynamicUsage(links.children);
577 2363 : bool fDependsWait = false;
578 : setEntries setParentCheck;
579 29145 : BOOST_FOREACH(const CTxIn &txin, tx.vin) {
580 : // Check that every mempool transaction's inputs refer to available coins, or other mempool tx's.
581 3466 : indexed_transaction_set::const_iterator it2 = mapTx.find(txin.prevout.hash);
582 10398 : if (it2 != mapTx.end()) {
583 156 : const CTransaction& tx2 = it2->GetTx();
584 468 : assert(tx2.vout.size() > txin.prevout.n && !tx2.vout[txin.prevout.n].IsNull());
585 156 : fDependsWait = true;
586 : setParentCheck.insert(it2);
587 : } else {
588 3310 : const CCoins* coins = pcoins->AccessCoins(txin.prevout.hash);
589 6620 : assert(coins && coins->IsAvailable(txin.prevout.n));
590 : }
591 : // Check whether its inputs are marked in mapNextTx.
592 6932 : std::map<COutPoint, CInPoint>::const_iterator it3 = mapNextTx.find(txin.prevout);
593 6932 : assert(it3 != mapNextTx.end());
594 3466 : assert(it3->second.ptx == &tx);
595 3466 : assert(it3->second.n == i);
596 3466 : i++;
597 : }
598 4726 : assert(setParentCheck == GetMemPoolParents(it));
599 : // Check children against mapNextTx
600 : CTxMemPool::setEntries setChildrenCheck;
601 9452 : std::map<COutPoint, CInPoint>::const_iterator iter = mapNextTx.lower_bound(COutPoint(it->GetTx().GetHash(), 0));
602 2363 : int64_t childSizes = 0;
603 2363 : CAmount childFees = 0;
604 15713 : for (; iter != mapNextTx.end() && iter->first.hash == it->GetTx().GetHash(); ++iter) {
605 312 : txiter childit = mapTx.find(iter->second.ptx->GetHash());
606 468 : assert(childit != mapTx.end()); // mapNextTx points to in-mempool transactions
607 156 : if (setChildrenCheck.insert(childit).second) {
608 156 : childSizes += childit->GetTxSize();
609 156 : childFees += childit->GetFee();
610 : }
611 : }
612 4726 : assert(setChildrenCheck == GetMemPoolChildren(it));
613 : // Also check to make sure size/fees is greater than sum with immediate children.
614 : // just a sanity check, not definitive that this calc is correct...
615 : // also check that the size is less than the size of the entire mempool.
616 2363 : if (!it->IsDirty()) {
617 4726 : assert(it->GetSizeWithDescendants() >= childSizes + it->GetTxSize());
618 4726 : assert(it->GetFeesWithDescendants() >= childFees + it->GetFee());
619 : } else {
620 0 : assert(it->GetSizeWithDescendants() == it->GetTxSize());
621 0 : assert(it->GetFeesWithDescendants() == it->GetFee());
622 : }
623 2363 : assert(it->GetFeesWithDescendants() >= 0);
624 :
625 2363 : if (fDependsWait)
626 306 : waitingOnDependants.push_back(&(*it));
627 : else {
628 : CValidationState state;
629 2210 : assert(CheckInputs(tx, state, mempoolDuplicate, false, 0, false, NULL));
630 2210 : UpdateCoins(tx, state, mempoolDuplicate, 1000000);
631 : }
632 : }
633 10715 : unsigned int stepsSinceLastRemove = 0;
634 21601 : while (!waitingOnDependants.empty()) {
635 171 : const CTxMemPoolEntry* entry = waitingOnDependants.front();
636 : waitingOnDependants.pop_front();
637 : CValidationState state;
638 342 : if (!mempoolDuplicate.HaveInputs(entry->GetTx())) {
639 : waitingOnDependants.push_back(entry);
640 18 : stepsSinceLastRemove++;
641 36 : assert(stepsSinceLastRemove < waitingOnDependants.size());
642 : } else {
643 306 : assert(CheckInputs(entry->GetTx(), state, mempoolDuplicate, false, 0, false, NULL));
644 306 : UpdateCoins(entry->GetTx(), state, mempoolDuplicate, 1000000);
645 : stepsSinceLastRemove = 0;
646 : }
647 171 : }
648 53258 : for (std::map<COutPoint, CInPoint>::const_iterator it = mapNextTx.begin(); it != mapNextTx.end(); it++) {
649 3466 : uint256 hash = it->second.ptx->GetHash();
650 3466 : indexed_transaction_set::const_iterator it2 = mapTx.find(hash);
651 6932 : const CTransaction& tx = it2->GetTx();
652 10398 : assert(it2 != mapTx.end());
653 3466 : assert(&tx == it->second.ptx);
654 10398 : assert(tx.vin.size() > it->second.n);
655 13864 : assert(it->first == it->second.ptx->vin[it->second.n].prevout);
656 : }
657 :
658 10715 : assert(totalTxSize == checkTotal);
659 21430 : assert(innerUsage == cachedInnerUsage);
660 : }
661 :
662 480 : void CTxMemPool::queryHashes(vector<uint256>& vtxid)
663 : {
664 : vtxid.clear();
665 :
666 480 : LOCK(cs);
667 480 : vtxid.reserve(mapTx.size());
668 4527 : for (indexed_transaction_set::iterator mi = mapTx.begin(); mi != mapTx.end(); ++mi)
669 2127 : vtxid.push_back(mi->GetTx().GetHash());
670 480 : }
671 :
672 17358 : bool CTxMemPool::lookup(uint256 hash, CTransaction& result) const
673 : {
674 17358 : LOCK(cs);
675 17358 : indexed_transaction_set::const_iterator i = mapTx.find(hash);
676 52074 : if (i == mapTx.end()) return false;
677 31644 : result = i->GetTx();
678 : return true;
679 : }
680 :
681 373 : CFeeRate CTxMemPool::estimateFee(int nBlocks) const
682 : {
683 373 : LOCK(cs);
684 746 : return minerPolicyEstimator->estimateFee(nBlocks);
685 : }
686 53 : double CTxMemPool::estimatePriority(int nBlocks) const
687 : {
688 53 : LOCK(cs);
689 106 : return minerPolicyEstimator->estimatePriority(nBlocks);
690 : }
691 :
692 : bool
693 94 : CTxMemPool::WriteFeeEstimates(CAutoFile& fileout) const
694 : {
695 : try {
696 94 : LOCK(cs);
697 94 : fileout << 109900; // version required to read: 0.10.99 or later
698 94 : fileout << CLIENT_VERSION; // version that wrote the file
699 94 : minerPolicyEstimator->Write(fileout);
700 : }
701 0 : catch (const std::exception&) {
702 0 : LogPrintf("CTxMemPool::WriteFeeEstimates(): unable to write policy estimator data (non-fatal)\n");
703 : return false;
704 : }
705 94 : return true;
706 : }
707 :
708 : bool
709 28 : CTxMemPool::ReadFeeEstimates(CAutoFile& filein)
710 : {
711 : try {
712 : int nVersionRequired, nVersionThatWrote;
713 28 : filein >> nVersionRequired >> nVersionThatWrote;
714 28 : if (nVersionRequired > CLIENT_VERSION)
715 0 : return error("CTxMemPool::ReadFeeEstimates(): up-version (%d) fee estimate file", nVersionRequired);
716 :
717 28 : LOCK(cs);
718 28 : minerPolicyEstimator->Read(filein);
719 : }
720 0 : catch (const std::exception&) {
721 0 : LogPrintf("CTxMemPool::ReadFeeEstimates(): unable to read policy estimator data (non-fatal)\n");
722 : return false;
723 : }
724 28 : return true;
725 : }
726 :
727 0 : void CTxMemPool::PrioritiseTransaction(const uint256 hash, const string strHash, double dPriorityDelta, const CAmount& nFeeDelta)
728 : {
729 : {
730 0 : LOCK(cs);
731 0 : std::pair<double, CAmount> &deltas = mapDeltas[hash];
732 0 : deltas.first += dPriorityDelta;
733 0 : deltas.second += nFeeDelta;
734 : }
735 0 : LogPrintf("PrioritiseTransaction: %s priority += %f, fee += %d\n", strHash, dPriorityDelta, FormatMoney(nFeeDelta));
736 0 : }
737 :
738 3049 : void CTxMemPool::ApplyDeltas(const uint256 hash, double &dPriorityDelta, CAmount &nFeeDelta)
739 : {
740 3049 : LOCK(cs);
741 6098 : std::map<uint256, std::pair<double, CAmount> >::iterator pos = mapDeltas.find(hash);
742 6098 : if (pos == mapDeltas.end())
743 3049 : return;
744 0 : const std::pair<double, CAmount> &deltas = pos->second;
745 0 : dPriorityDelta += deltas.first;
746 0 : nFeeDelta += deltas.second;
747 : }
748 :
749 21881 : void CTxMemPool::ClearPrioritisation(const uint256 hash)
750 : {
751 21881 : LOCK(cs);
752 21881 : mapDeltas.erase(hash);
753 21881 : }
754 :
755 16280 : bool CTxMemPool::HasNoInputsOf(const CTransaction &tx) const
756 : {
757 65948 : for (unsigned int i = 0; i < tx.vin.size(); i++)
758 33504 : if (exists(tx.vin[i].prevout.hash))
759 : return false;
760 : return true;
761 : }
762 :
763 580 : CCoinsViewMemPool::CCoinsViewMemPool(CCoinsView *baseIn, CTxMemPool &mempoolIn) : CCoinsViewBacked(baseIn), mempool(mempoolIn) { }
764 :
765 1598 : bool CCoinsViewMemPool::GetCoins(const uint256 &txid, CCoins &coins) const {
766 : // If an entry in the mempool exists, always return that one, as it's guaranteed to never
767 : // conflict with the underlying cache, and it cannot have pruned entries (as it contains full)
768 : // transactions. First checking the underlying cache risks returning a pruned entry instead.
769 1598 : CTransaction tx;
770 1598 : if (mempool.lookup(txid, tx)) {
771 134 : coins = CCoins(tx, MEMPOOL_HEIGHT);
772 67 : return true;
773 : }
774 1531 : return (base->GetCoins(txid, coins) && !coins.IsPruned());
775 : }
776 :
777 0 : bool CCoinsViewMemPool::HaveCoins(const uint256 &txid) const {
778 0 : return mempool.exists(txid) || base->HaveCoins(txid);
779 : }
780 :
781 1 : size_t CTxMemPool::DynamicMemoryUsage() const {
782 1 : LOCK(cs);
783 : // Estimate the overhead of mapTx to be 9 pointers + an allocation, as no exact formula for boost::multi_index_contained is implemented.
784 5 : return memusage::MallocUsage(sizeof(CTxMemPoolEntry) + 9 * sizeof(void*)) * mapTx.size() + memusage::DynamicUsage(mapNextTx) + memusage::DynamicUsage(mapDeltas) + memusage::DynamicUsage(mapLinks) + cachedInnerUsage;
785 : }
786 :
787 21968 : void CTxMemPool::RemoveStaged(setEntries &stage) {
788 21968 : AssertLockHeld(cs);
789 21968 : UpdateForRemoveFromMempool(stage);
790 229446 : BOOST_FOREACH(const txiter& it, stage) {
791 16273 : removeUnchecked(it);
792 : }
793 21968 : }
794 :
795 16909 : bool CTxMemPool::addUnchecked(const uint256&hash, const CTxMemPoolEntry &entry, bool fCurrentEstimate)
796 : {
797 16909 : LOCK(cs);
798 : setEntries setAncestors;
799 16909 : uint64_t nNoLimit = std::numeric_limits<uint64_t>::max();
800 : std::string dummy;
801 16909 : CalculateMemPoolAncestors(entry, setAncestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy);
802 33818 : return addUnchecked(hash, entry, setAncestors, fCurrentEstimate);
803 : }
804 :
805 1225 : void CTxMemPool::UpdateChild(txiter entry, txiter child, bool add)
806 : {
807 : setEntries s;
808 2435 : if (add && mapLinks[entry].children.insert(child).second) {
809 1210 : cachedInnerUsage += memusage::IncrementalDynamicUsage(s);
810 30 : } else if (!add && mapLinks[entry].children.erase(child)) {
811 15 : cachedInnerUsage -= memusage::IncrementalDynamicUsage(s);
812 : }
813 1225 : }
814 :
815 1271 : void CTxMemPool::UpdateParent(txiter entry, txiter parent, bool add)
816 : {
817 : setEntries s;
818 2481 : if (add && mapLinks[entry].parents.insert(parent).second) {
819 1210 : cachedInnerUsage += memusage::IncrementalDynamicUsage(s);
820 122 : } else if (!add && mapLinks[entry].parents.erase(parent)) {
821 61 : cachedInnerUsage -= memusage::IncrementalDynamicUsage(s);
822 : }
823 1271 : }
824 :
825 561084 : const CTxMemPool::setEntries & CTxMemPool::GetMemPoolParents(txiter entry) const
826 : {
827 1683252 : assert (entry != mapTx.end());
828 1122168 : txlinksMap::const_iterator it = mapLinks.find(entry);
829 1122168 : assert(it != mapLinks.end());
830 561084 : return it->second.parents;
831 : }
832 :
833 18721 : const CTxMemPool::setEntries & CTxMemPool::GetMemPoolChildren(txiter entry) const
834 : {
835 56163 : assert (entry != mapTx.end());
836 37442 : txlinksMap::const_iterator it = mapLinks.find(entry);
837 37442 : assert(it != mapLinks.end());
838 18721 : return it->second.children;
839 288 : }
|
