src/txmempool.cpp

   1 // Copyright (c) 2009-2010 Satoshi Nakamoto
   2 // Copyright (c) 2009-2016 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 "consensus/consensus.h"
   9 #include "consensus/tx_verify.h"
  10 #include "consensus/validation.h"
  11 #include "validation.h"
  12 #include "policy/policy.h"
  13 #include "policy/fees.h"
  14 #include "reverse_iterator.h"
  15 #include "streams.h"
  16 #include "timedata.h"
  17 #include "util.h"
  18 #include "utilmoneystr.h"
  19 #include "utiltime.h"
  20
  21 CTxMemPoolEntry::CTxMemPoolEntry(const CTransactionRef& _tx, const CAmount& _nFee,
  22                                  int64_t _nTime, unsigned int _entryHeight,
  23                                  bool _spendsCoinbase, int64_t _sigOpsCost, LockPoints lp):
  24     tx(_tx), nFee(_nFee), nTime(_nTime), entryHeight(_entryHeight),
  25     spendsCoinbase(_spendsCoinbase), sigOpCost(_sigOpsCost), lockPoints(lp)
  26 {
  27     nTxWeight = GetTransactionWeight(*tx);
  28     nUsageSize = RecursiveDynamicUsage(tx);
  29
  30     nCountWithDescendants = 1;
  31     nSizeWithDescendants = GetTxSize();
  32     nModFeesWithDescendants = nFee;
  33
  34     feeDelta = 0;
  35
  36     nCountWithAncestors = 1;
  37     nSizeWithAncestors = GetTxSize();
  38     nModFeesWithAncestors = nFee;
  39     nSigOpCostWithAncestors = sigOpCost;
  40 }
  41
  42 void CTxMemPoolEntry::UpdateFeeDelta(int64_t newFeeDelta)
  43 {
  44     nModFeesWithDescendants += newFeeDelta - feeDelta;
  45     nModFeesWithAncestors += newFeeDelta - feeDelta;
  46     feeDelta = newFeeDelta;
  47 }
  48
  49 void CTxMemPoolEntry::UpdateLockPoints(const LockPoints& lp)
  50 {
  51     lockPoints = lp;
  52 }
  53
  54 size_t CTxMemPoolEntry::GetTxSize() const
  55 {
  56     return GetVirtualTransactionSize(nTxWeight, sigOpCost);
  57 }
  58
  59 // Update the given tx for any in-mempool descendants.
  60 // Assumes that setMemPoolChildren is correct for the given tx and all
  61 // descendants.
  62 void CTxMemPool::UpdateForDescendants(txiter updateIt, cacheMap &cachedDescendants, const std::set<uint256> &setExclude)
  63 {
  64     setEntries stageEntries, setAllDescendants;
  65     stageEntries = GetMemPoolChildren(updateIt);
  66
  67     while (!stageEntries.empty()) {
  68         const txiter cit = *stageEntries.begin();
  69         setAllDescendants.insert(cit);
  70         stageEntries.erase(cit);
  71         const setEntries &setChildren = GetMemPoolChildren(cit);
  72         for (const txiter childEntry : setChildren) {
  73             cacheMap::iterator cacheIt = cachedDescendants.find(childEntry);
  74             if (cacheIt != cachedDescendants.end()) {
  75                 // We've already calculated this one, just add the entries for this set
  76                 // but don't traverse again.
  77                 for (const txiter cacheEntry : cacheIt->second) {
  78                     setAllDescendants.insert(cacheEntry);
  79                 }
  80             } else if (!setAllDescendants.count(childEntry)) {
  81                 // Schedule for later processing
  82                 stageEntries.insert(childEntry);
  83             }
  84         }
  85     }
  86     // setAllDescendants now contains all in-mempool descendants of updateIt.
  87     // Update and add to cached descendant map
  88     int64_t modifySize = 0;
  89     CAmount modifyFee = 0;
  90     int64_t modifyCount = 0;
  91     for (txiter cit : setAllDescendants) {
  92         if (!setExclude.count(cit->GetTx().GetHash())) {
  93             modifySize += cit->GetTxSize();
  94             modifyFee += cit->GetModifiedFee();
  95             modifyCount++;
  96             cachedDescendants[updateIt].insert(cit);
  97             // Update ancestor state for each descendant
  98             mapTx.modify(cit, update_ancestor_state(updateIt->GetTxSize(), updateIt->GetModifiedFee(), 1, updateIt->GetSigOpCost()));
  99         }
 100     }
 101     mapTx.modify(updateIt, update_descendant_state(modifySize, modifyFee, modifyCount));
 102 }
 103
 104 // vHashesToUpdate is the set of transaction hashes from a disconnected block
 105 // which has been re-added to the mempool.
 106 // for each entry, look for descendants that are outside vHashesToUpdate, and
 107 // add fee/size information for such descendants to the parent.
 108 // for each such descendant, also update the ancestor state to include the parent.
 109 void CTxMemPool::UpdateTransactionsFromBlock(const std::vector<uint256> &vHashesToUpdate)
 110 {
 111     LOCK(cs);
 112     // For each entry in vHashesToUpdate, store the set of in-mempool, but not
 113     // in-vHashesToUpdate transactions, so that we don't have to recalculate
 114     // descendants when we come across a previously seen entry.
 115     cacheMap mapMemPoolDescendantsToUpdate;
 116
 117     // Use a set for lookups into vHashesToUpdate (these entries are already
 118     // accounted for in the state of their ancestors)
 119     std::set<uint256> setAlreadyIncluded(vHashesToUpdate.begin(), vHashesToUpdate.end());
 120
 121     // Iterate in reverse, so that whenever we are looking at a transaction
 122     // we are sure that all in-mempool descendants have already been processed.
 123     // This maximizes the benefit of the descendant cache and guarantees that
 124     // setMemPoolChildren will be updated, an assumption made in
 125     // UpdateForDescendants.
 126     for (const uint256 &hash : reverse_iterate(vHashesToUpdate)) {
 127         // we cache the in-mempool children to avoid duplicate updates
 128         setEntries setChildren;
 129         // calculate children from mapNextTx
 130         txiter it = mapTx.find(hash);
 131         if (it == mapTx.end()) {
 132             continue;
 133         }
 134         auto iter = mapNextTx.lower_bound(COutPoint(hash, 0));
 135         // First calculate the children, and update setMemPoolChildren to
 136         // include them, and update their setMemPoolParents to include this tx.
 137         for (; iter != mapNextTx.end() && iter->first->hash == hash; ++iter) {
 138             const uint256 &childHash = iter->second->GetHash();
 139             txiter childIter = mapTx.find(childHash);
 140             assert(childIter != mapTx.end());
 141             // We can skip updating entries we've encountered before or that
 142             // are in the block (which are already accounted for).
 143             if (setChildren.insert(childIter).second && !setAlreadyIncluded.count(childHash)) {
 144                 UpdateChild(it, childIter, true);
 145                 UpdateParent(childIter, it, true);
 146             }
 147         }
 148         UpdateForDescendants(it, mapMemPoolDescendantsToUpdate, setAlreadyIncluded);
 149     }
 150 }
 151
 152 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 */) const
 153 {
 154     LOCK(cs);
 155
 156     setEntries parentHashes;
 157     const CTransaction &tx = entry.GetTx();
 158
 159     if (fSearchForParents) {
 160         // Get parents of this transaction that are in the mempool
 161         // GetMemPoolParents() is only valid for entries in the mempool, so we
 162         // iterate mapTx to find parents.
 163         for (unsigned int i = 0; i < tx.vin.size(); i++) {
 164             txiter piter = mapTx.find(tx.vin[i].prevout.hash);
 165             if (piter != mapTx.end()) {
 166                 parentHashes.insert(piter);
 167                 if (parentHashes.size() + 1 > limitAncestorCount) {
 168                     errString = strprintf("too many unconfirmed parents [limit: %u]", limitAncestorCount);
 169                     return false;
 170                 }
 171             }
 172         }
 173     } else {
 174         // If we're not searching for parents, we require this to be an
 175         // entry in the mempool already.
 176         txiter it = mapTx.iterator_to(entry);
 177         parentHashes = GetMemPoolParents(it);
 178     }
 179
 180     size_t totalSizeWithAncestors = entry.GetTxSize();
 181
 182     while (!parentHashes.empty()) {
 183         txiter stageit = *parentHashes.begin();
 184
 185         setAncestors.insert(stageit);
 186         parentHashes.erase(stageit);
 187         totalSizeWithAncestors += stageit->GetTxSize();
 188
 189         if (stageit->GetSizeWithDescendants() + entry.GetTxSize() > limitDescendantSize) {
 190             errString = strprintf("exceeds descendant size limit for tx %s [limit: %u]", stageit->GetTx().GetHash().ToString(), limitDescendantSize);
 191             return false;
 192         } else if (stageit->GetCountWithDescendants() + 1 > limitDescendantCount) {
 193             errString = strprintf("too many descendants for tx %s [limit: %u]", stageit->GetTx().GetHash().ToString(), limitDescendantCount);
 194             return false;
 195         } else if (totalSizeWithAncestors > limitAncestorSize) {
 196             errString = strprintf("exceeds ancestor size limit [limit: %u]", limitAncestorSize);
 197             return false;
 198         }
 199
 200         const setEntries & setMemPoolParents = GetMemPoolParents(stageit);
 201         for (const txiter &phash : setMemPoolParents) {
 202             // If this is a new ancestor, add it.
 203             if (setAncestors.count(phash) == 0) {
 204                 parentHashes.insert(phash);
 205             }
 206             if (parentHashes.size() + setAncestors.size() + 1 > limitAncestorCount) {
 207                 errString = strprintf("too many unconfirmed ancestors [limit: %u]", limitAncestorCount);
 208                 return false;
 209             }
 210         }
 211     }
 212
 213     return true;
 214 }
 215
 216 void CTxMemPool::UpdateAncestorsOf(bool add, txiter it, setEntries &setAncestors)
 217 {
 218     setEntries parentIters = GetMemPoolParents(it);
 219     // add or remove this tx as a child of each parent
 220     for (txiter piter : parentIters) {
 221         UpdateChild(piter, it, add);
 222     }
 223     const int64_t updateCount = (add ? 1 : -1);
 224     const int64_t updateSize = updateCount * it->GetTxSize();
 225     const CAmount updateFee = updateCount * it->GetModifiedFee();
 226     for (txiter ancestorIt : setAncestors) {
 227         mapTx.modify(ancestorIt, update_descendant_state(updateSize, updateFee, updateCount));
 228     }
 229 }
 230
 231 void CTxMemPool::UpdateEntryForAncestors(txiter it, const setEntries &setAncestors)
 232 {
 233     int64_t updateCount = setAncestors.size();
 234     int64_t updateSize = 0;
 235     CAmount updateFee = 0;
 236     int64_t updateSigOpsCost = 0;
 237     for (txiter ancestorIt : setAncestors) {
 238         updateSize += ancestorIt->GetTxSize();
 239         updateFee += ancestorIt->GetModifiedFee();
 240         updateSigOpsCost += ancestorIt->GetSigOpCost();
 241     }
 242     mapTx.modify(it, update_ancestor_state(updateSize, updateFee, updateCount, updateSigOpsCost));
 243 }
 244
 245 void CTxMemPool::UpdateChildrenForRemoval(txiter it)
 246 {
 247     const setEntries &setMemPoolChildren = GetMemPoolChildren(it);
 248     for (txiter updateIt : setMemPoolChildren) {
 249         UpdateParent(updateIt, it, false);
 250     }
 251 }
 252
 253 void CTxMemPool::UpdateForRemoveFromMempool(const setEntries &entriesToRemove, bool updateDescendants)
 254 {
 255     // For each entry, walk back all ancestors and decrement size associated with this
 256     // transaction
 257     const uint64_t nNoLimit = std::numeric_limits<uint64_t>::max();
 258     if (updateDescendants) {
 259         // updateDescendants should be true whenever we're not recursively
 260         // removing a tx and all its descendants, eg when a transaction is
 261         // confirmed in a block.
 262         // Here we only update statistics and not data in mapLinks (which
 263         // we need to preserve until we're finished with all operations that
 264         // need to traverse the mempool).
 265         for (txiter removeIt : entriesToRemove) {
 266             setEntries setDescendants;
 267             CalculateDescendants(removeIt, setDescendants);
 268             setDescendants.erase(removeIt); // don't update state for self
 269             int64_t modifySize = -((int64_t)removeIt->GetTxSize());
 270             CAmount modifyFee = -removeIt->GetModifiedFee();
 271             int modifySigOps = -removeIt->GetSigOpCost();
 272             for (txiter dit : setDescendants) {
 273                 mapTx.modify(dit, update_ancestor_state(modifySize, modifyFee, -1, modifySigOps));
 274             }
 275         }
 276     }
 277     for (txiter removeIt : entriesToRemove) {
 278         setEntries setAncestors;
 279         const CTxMemPoolEntry &entry = *removeIt;
 280         std::string dummy;
 281         // Since this is a tx that is already in the mempool, we can call CMPA
 282         // with fSearchForParents = false.  If the mempool is in a consistent
 283         // state, then using true or false should both be correct, though false
 284         // should be a bit faster.
 285         // However, if we happen to be in the middle of processing a reorg, then
 286         // the mempool can be in an inconsistent state.  In this case, the set
 287         // of ancestors reachable via mapLinks will be the same as the set of
 288         // ancestors whose packages include this transaction, because when we
 289         // add a new transaction to the mempool in addUnchecked(), we assume it
 290         // has no children, and in the case of a reorg where that assumption is
 291         // false, the in-mempool children aren't linked to the in-block tx's
 292         // until UpdateTransactionsFromBlock() is called.
 293         // So if we're being called during a reorg, ie before
 294         // UpdateTransactionsFromBlock() has been called, then mapLinks[] will
 295         // differ from the set of mempool parents we'd calculate by searching,
 296         // and it's important that we use the mapLinks[] notion of ancestor
 297         // transactions as the set of things to update for removal.
 298         CalculateMemPoolAncestors(entry, setAncestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy, false);
 299         // Note that UpdateAncestorsOf severs the child links that point to
 300         // removeIt in the entries for the parents of removeIt.
 301         UpdateAncestorsOf(false, removeIt, setAncestors);
 302     }
 303     // After updating all the ancestor sizes, we can now sever the link between each
 304     // transaction being removed and any mempool children (ie, update setMemPoolParents
 305     // for each direct child of a transaction being removed).
 306     for (txiter removeIt : entriesToRemove) {
 307         UpdateChildrenForRemoval(removeIt);
 308     }
 309 }
 310
 311 void CTxMemPoolEntry::UpdateDescendantState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount)
 312 {
 313     nSizeWithDescendants += modifySize;
 314     assert(int64_t(nSizeWithDescendants) > 0);
 315     nModFeesWithDescendants += modifyFee;
 316     nCountWithDescendants += modifyCount;
 317     assert(int64_t(nCountWithDescendants) > 0);
 318 }
 319
 320 void CTxMemPoolEntry::UpdateAncestorState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount, int modifySigOps)
 321 {
 322     nSizeWithAncestors += modifySize;
 323     assert(int64_t(nSizeWithAncestors) > 0);
 324     nModFeesWithAncestors += modifyFee;
 325     nCountWithAncestors += modifyCount;
 326     assert(int64_t(nCountWithAncestors) > 0);
 327     nSigOpCostWithAncestors += modifySigOps;
 328     assert(int(nSigOpCostWithAncestors) >= 0);
 329 }
 330
 331 CTxMemPool::CTxMemPool(CBlockPolicyEstimator* estimator) :
 332     nTransactionsUpdated(0), minerPolicyEstimator(estimator)
 333 {
 334     _clear(); //lock free clear
 335
 336     // Sanity checks off by default for performance, because otherwise
 337     // accepting transactions becomes O(N^2) where N is the number
 338     // of transactions in the pool
 339     nCheckFrequency = 0;
 340 }
 341
 342 bool CTxMemPool::isSpent(const COutPoint& outpoint)
 343 {
 344     LOCK(cs);
 345     return mapNextTx.count(outpoint);
 346 }
 347
 348 unsigned int CTxMemPool::GetTransactionsUpdated() const
 349 {
 350     LOCK(cs);
 351     return nTransactionsUpdated;
 352 }
 353
 354 void CTxMemPool::AddTransactionsUpdated(unsigned int n)
 355 {
 356     LOCK(cs);
 357     nTransactionsUpdated += n;
 358 }
 359
 360 bool CTxMemPool::addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry, setEntries &setAncestors, bool validFeeEstimate)
 361 {
 362     NotifyEntryAdded(entry.GetSharedTx());
 363     // Add to memory pool without checking anything.
 364     // Used by AcceptToMemoryPool(), which DOES do
 365     // all the appropriate checks.
 366     LOCK(cs);
 367     indexed_transaction_set::iterator newit = mapTx.insert(entry).first;
 368     mapLinks.insert(make_pair(newit, TxLinks()));
 369
 370     // Update transaction for any feeDelta created by PrioritiseTransaction
 371     // TODO: refactor so that the fee delta is calculated before inserting
 372     // into mapTx.
 373     std::map<uint256, CAmount>::const_iterator pos = mapDeltas.find(hash);
 374     if (pos != mapDeltas.end()) {
 375         const CAmount &delta = pos->second;
 376         if (delta) {
 377             mapTx.modify(newit, update_fee_delta(delta));
 378         }
 379     }
 380
 381     // Update cachedInnerUsage to include contained transaction's usage.
 382     // (When we update the entry for in-mempool parents, memory usage will be
 383     // further updated.)
 384     cachedInnerUsage += entry.DynamicMemoryUsage();
 385
 386     const CTransaction& tx = newit->GetTx();
 387     std::set<uint256> setParentTransactions;
 388     for (unsigned int i = 0; i < tx.vin.size(); i++) {
 389         mapNextTx.insert(std::make_pair(&tx.vin[i].prevout, &tx));
 390         setParentTransactions.insert(tx.vin[i].prevout.hash);
 391     }
 392     // Don't bother worrying about child transactions of this one.
 393     // Normal case of a new transaction arriving is that there can't be any
 394     // children, because such children would be orphans.
 395     // An exception to that is if a transaction enters that used to be in a block.
 396     // In that case, our disconnect block logic will call UpdateTransactionsFromBlock
 397     // to clean up the mess we're leaving here.
 398
 399     // Update ancestors with information about this tx
 400     for (const uint256 &phash : setParentTransactions) {
 401         txiter pit = mapTx.find(phash);
 402         if (pit != mapTx.end()) {
 403             UpdateParent(newit, pit, true);
 404         }
 405     }
 406     UpdateAncestorsOf(true, newit, setAncestors);
 407     UpdateEntryForAncestors(newit, setAncestors);
 408
 409     nTransactionsUpdated++;
 410     totalTxSize += entry.GetTxSize();
 411     if (minerPolicyEstimator) {minerPolicyEstimator->processTransaction(entry, validFeeEstimate);}
 412
 413     vTxHashes.emplace_back(tx.GetWitnessHash(), newit);
 414     newit->vTxHashesIdx = vTxHashes.size() - 1;
 415
 416     return true;
 417 }
 418
 419 void CTxMemPool::removeUnchecked(txiter it, MemPoolRemovalReason reason)
 420 {
 421     NotifyEntryRemoved(it->GetSharedTx(), reason);
 422     const uint256 hash = it->GetTx().GetHash();
 423     for (const CTxIn& txin : it->GetTx().vin)
 424         mapNextTx.erase(txin.prevout);
 425
 426     if (vTxHashes.size() > 1) {
 427         vTxHashes[it->vTxHashesIdx] = std::move(vTxHashes.back());
 428         vTxHashes[it->vTxHashesIdx].second->vTxHashesIdx = it->vTxHashesIdx;
 429         vTxHashes.pop_back();
 430         if (vTxHashes.size() * 2 < vTxHashes.capacity())
 431             vTxHashes.shrink_to_fit();
 432     } else
 433         vTxHashes.clear();
 434
 435     totalTxSize -= it->GetTxSize();
 436     cachedInnerUsage -= it->DynamicMemoryUsage();
 437     cachedInnerUsage -= memusage::DynamicUsage(mapLinks[it].parents) + memusage::DynamicUsage(mapLinks[it].children);
 438     mapLinks.erase(it);
 439     mapTx.erase(it);
 440     nTransactionsUpdated++;
 441     if (minerPolicyEstimator) {minerPolicyEstimator->removeTx(hash, false);}
 442 }
 443
 444 // Calculates descendants of entry that are not already in setDescendants, and adds to
 445 // setDescendants. Assumes entryit is already a tx in the mempool and setMemPoolChildren
 446 // is correct for tx and all descendants.
 447 // Also assumes that if an entry is in setDescendants already, then all
 448 // in-mempool descendants of it are already in setDescendants as well, so that we
 449 // can save time by not iterating over those entries.
 450 void CTxMemPool::CalculateDescendants(txiter entryit, setEntries &setDescendants)
 451 {
 452     setEntries stage;
 453     if (setDescendants.count(entryit) == 0) {
 454         stage.insert(entryit);
 455     }
 456     // Traverse down the children of entry, only adding children that are not
 457     // accounted for in setDescendants already (because those children have either
 458     // already been walked, or will be walked in this iteration).
 459     while (!stage.empty()) {
 460         txiter it = *stage.begin();
 461         setDescendants.insert(it);
 462         stage.erase(it);
 463
 464         const setEntries &setChildren = GetMemPoolChildren(it);
 465         for (const txiter &childiter : setChildren) {
 466             if (!setDescendants.count(childiter)) {
 467                 stage.insert(childiter);
 468             }
 469         }
 470     }
 471 }
 472
 473 void CTxMemPool::removeRecursive(const CTransaction &origTx, MemPoolRemovalReason reason)
 474 {
 475     // Remove transaction from memory pool
 476     {
 477         LOCK(cs);
 478         setEntries txToRemove;
 479         txiter origit = mapTx.find(origTx.GetHash());
 480         if (origit != mapTx.end()) {
 481             txToRemove.insert(origit);
 482         } else {
 483             // When recursively removing but origTx isn't in the mempool
 484             // be sure to remove any children that are in the pool. This can
 485             // happen during chain re-orgs if origTx isn't re-accepted into
 486             // the mempool for any reason.
 487             for (unsigned int i = 0; i < origTx.vout.size(); i++) {
 488                 auto it = mapNextTx.find(COutPoint(origTx.GetHash(), i));
 489                 if (it == mapNextTx.end())
 490                     continue;
 491                 txiter nextit = mapTx.find(it->second->GetHash());
 492                 assert(nextit != mapTx.end());
 493                 txToRemove.insert(nextit);
 494             }
 495         }
 496         setEntries setAllRemoves;
 497         for (txiter it : txToRemove) {
 498             CalculateDescendants(it, setAllRemoves);
 499         }
 500
 501         RemoveStaged(setAllRemoves, false, reason);
 502     }
 503 }
 504
 505 void CTxMemPool::removeForReorg(const CCoinsViewCache *pcoins, unsigned int nMemPoolHeight, int flags)
 506 {
 507     // Remove transactions spending a coinbase which are now immature and no-longer-final transactions
 508     LOCK(cs);
 509     setEntries txToRemove;
 510     for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
 511         const CTransaction& tx = it->GetTx();
 512         LockPoints lp = it->GetLockPoints();
 513         bool validLP =  TestLockPointValidity(&lp);
 514         if (!CheckFinalTx(tx, flags) || !CheckSequenceLocks(tx, flags, &lp, validLP)) {
 515             // Note if CheckSequenceLocks fails the LockPoints may still be invalid
 516             // So it's critical that we remove the tx and not depend on the LockPoints.
 517             txToRemove.insert(it);
 518         } else if (it->GetSpendsCoinbase()) {
 519             for (const CTxIn& txin : tx.vin) {
 520                 indexed_transaction_set::const_iterator it2 = mapTx.find(txin.prevout.hash);
 521                 if (it2 != mapTx.end())
 522                     continue;
 523                 const Coin &coin = pcoins->AccessCoin(txin.prevout);
 524                 if (nCheckFrequency != 0) assert(!coin.IsSpent());
 525                 if (coin.IsSpent() || (coin.IsCoinBase() && ((signed long)nMemPoolHeight) - coin.nHeight < COINBASE_MATURITY)) {
 526                     txToRemove.insert(it);
 527                     break;
 528                 }
 529             }
 530         }
 531         if (!validLP) {
 532             mapTx.modify(it, update_lock_points(lp));
 533         }
 534     }
 535     setEntries setAllRemoves;
 536     for (txiter it : txToRemove) {
 537         CalculateDescendants(it, setAllRemoves);
 538     }
 539     RemoveStaged(setAllRemoves, false, MemPoolRemovalReason::REORG);
 540 }
 541
 542 void CTxMemPool::removeConflicts(const CTransaction &tx)
 543 {
 544     // Remove transactions which depend on inputs of tx, recursively
 545     LOCK(cs);
 546     for (const CTxIn &txin : tx.vin) {
 547         auto it = mapNextTx.find(txin.prevout);
 548         if (it != mapNextTx.end()) {
 549             const CTransaction &txConflict = *it->second;
 550             if (txConflict != tx)
 551             {
 552                 ClearPrioritisation(txConflict.GetHash());
 553                 removeRecursive(txConflict, MemPoolRemovalReason::CONFLICT);
 554             }
 555         }
 556     }
 557 }
 558
 559 /**
 560  * Called when a block is connected. Removes from mempool and updates the miner fee estimator.
 561  */
 562 void CTxMemPool::removeForBlock(const std::vector<CTransactionRef>& vtx, unsigned int nBlockHeight)
 563 {
 564     LOCK(cs);
 565     std::vector<const CTxMemPoolEntry*> entries;
 566     for (const auto& tx : vtx)
 567     {
 568         uint256 hash = tx->GetHash();
 569
 570         indexed_transaction_set::iterator i = mapTx.find(hash);
 571         if (i != mapTx.end())
 572             entries.push_back(&*i);
 573     }
 574     // Before the txs in the new block have been removed from the mempool, update policy estimates
 575     if (minerPolicyEstimator) {minerPolicyEstimator->processBlock(nBlockHeight, entries);}
 576     for (const auto& tx : vtx)
 577     {
 578         txiter it = mapTx.find(tx->GetHash());
 579         if (it != mapTx.end()) {
 580             setEntries stage;
 581             stage.insert(it);
 582             RemoveStaged(stage, true, MemPoolRemovalReason::BLOCK);
 583         }
 584         removeConflicts(*tx);
 585         ClearPrioritisation(tx->GetHash());
 586     }
 587     lastRollingFeeUpdate = GetTime();
 588     blockSinceLastRollingFeeBump = true;
 589 }
 590
 591 void CTxMemPool::_clear()
 592 {
 593     mapLinks.clear();
 594     mapTx.clear();
 595     mapNextTx.clear();
 596     totalTxSize = 0;
 597     cachedInnerUsage = 0;
 598     lastRollingFeeUpdate = GetTime();
 599     blockSinceLastRollingFeeBump = false;
 600     rollingMinimumFeeRate = 0;
 601     ++nTransactionsUpdated;
 602 }
 603
 604 void CTxMemPool::clear()
 605 {
 606     LOCK(cs);
 607     _clear();
 608 }
 609
 610 void CTxMemPool::check(const CCoinsViewCache *pcoins) const
 611 {
 612     if (nCheckFrequency == 0)
 613         return;
 614
 615     if (GetRand(std::numeric_limits<uint32_t>::max()) >= nCheckFrequency)
 616         return;
 617
 618     LogPrint(BCLog::MEMPOOL, "Checking mempool with %u transactions and %u inputs\n", (unsigned int)mapTx.size(), (unsigned int)mapNextTx.size());
 619
 620     uint64_t checkTotal = 0;
 621     uint64_t innerUsage = 0;
 622
 623     CCoinsViewCache mempoolDuplicate(const_cast<CCoinsViewCache*>(pcoins));
 624     const int64_t nSpendHeight = GetSpendHeight(mempoolDuplicate);
 625
 626     LOCK(cs);
 627     std::list<const CTxMemPoolEntry*> waitingOnDependants;
 628     for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
 629         unsigned int i = 0;
 630         checkTotal += it->GetTxSize();
 631         innerUsage += it->DynamicMemoryUsage();
 632         const CTransaction& tx = it->GetTx();
 633         txlinksMap::const_iterator linksiter = mapLinks.find(it);
 634         assert(linksiter != mapLinks.end());
 635         const TxLinks &links = linksiter->second;
 636         innerUsage += memusage::DynamicUsage(links.parents) + memusage::DynamicUsage(links.children);
 637         bool fDependsWait = false;
 638         setEntries setParentCheck;
 639         int64_t parentSizes = 0;
 640         int64_t parentSigOpCost = 0;
 641         for (const CTxIn &txin : tx.vin) {
 642             // Check that every mempool transaction's inputs refer to available coins, or other mempool tx's.
 643             indexed_transaction_set::const_iterator it2 = mapTx.find(txin.prevout.hash);
 644             if (it2 != mapTx.end()) {
 645                 const CTransaction& tx2 = it2->GetTx();
 646                 assert(tx2.vout.size() > txin.prevout.n && !tx2.vout[txin.prevout.n].IsNull());
 647                 fDependsWait = true;
 648                 if (setParentCheck.insert(it2).second) {
 649                     parentSizes += it2->GetTxSize();
 650                     parentSigOpCost += it2->GetSigOpCost();
 651                 }
 652             } else {
 653                 assert(pcoins->HaveCoin(txin.prevout));
 654             }
 655             // Check whether its inputs are marked in mapNextTx.
 656             auto it3 = mapNextTx.find(txin.prevout);
 657             assert(it3 != mapNextTx.end());
 658             assert(it3->first == &txin.prevout);
 659             assert(it3->second == &tx);
 660             i++;
 661         }
 662         assert(setParentCheck == GetMemPoolParents(it));
 663         // Verify ancestor state is correct.
 664         setEntries setAncestors;
 665         uint64_t nNoLimit = std::numeric_limits<uint64_t>::max();
 666         std::string dummy;
 667         CalculateMemPoolAncestors(*it, setAncestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy);
 668         uint64_t nCountCheck = setAncestors.size() + 1;
 669         uint64_t nSizeCheck = it->GetTxSize();
 670         CAmount nFeesCheck = it->GetModifiedFee();
 671         int64_t nSigOpCheck = it->GetSigOpCost();
 672
 673         for (txiter ancestorIt : setAncestors) {
 674             nSizeCheck += ancestorIt->GetTxSize();
 675             nFeesCheck += ancestorIt->GetModifiedFee();
 676             nSigOpCheck += ancestorIt->GetSigOpCost();
 677         }
 678
 679         assert(it->GetCountWithAncestors() == nCountCheck);
 680         assert(it->GetSizeWithAncestors() == nSizeCheck);
 681         assert(it->GetSigOpCostWithAncestors() == nSigOpCheck);
 682         assert(it->GetModFeesWithAncestors() == nFeesCheck);
 683
 684         // Check children against mapNextTx
 685         CTxMemPool::setEntries setChildrenCheck;
 686         auto iter = mapNextTx.lower_bound(COutPoint(it->GetTx().GetHash(), 0));
 687         int64_t childSizes = 0;
 688         for (; iter != mapNextTx.end() && iter->first->hash == it->GetTx().GetHash(); ++iter) {
 689             txiter childit = mapTx.find(iter->second->GetHash());
 690             assert(childit != mapTx.end()); // mapNextTx points to in-mempool transactions
 691             if (setChildrenCheck.insert(childit).second) {
 692                 childSizes += childit->GetTxSize();
 693             }
 694         }
 695         assert(setChildrenCheck == GetMemPoolChildren(it));
 696         // Also check to make sure size is greater than sum with immediate children.
 697         // just a sanity check, not definitive that this calc is correct...
 698         assert(it->GetSizeWithDescendants() >= childSizes + it->GetTxSize());
 699
 700         if (fDependsWait)
 701             waitingOnDependants.push_back(&(*it));
 702         else {
 703             CValidationState state;
 704             bool fCheckResult = tx.IsCoinBase() ||
 705                 Consensus::CheckTxInputs(tx, state, mempoolDuplicate, nSpendHeight);
 706             assert(fCheckResult);
 707             UpdateCoins(tx, mempoolDuplicate, 1000000);
 708         }
 709     }
 710     unsigned int stepsSinceLastRemove = 0;
 711     while (!waitingOnDependants.empty()) {
 712         const CTxMemPoolEntry* entry = waitingOnDependants.front();
 713         waitingOnDependants.pop_front();
 714         CValidationState state;
 715         if (!mempoolDuplicate.HaveInputs(entry->GetTx())) {
 716             waitingOnDependants.push_back(entry);
 717             stepsSinceLastRemove++;
 718             assert(stepsSinceLastRemove < waitingOnDependants.size());
 719         } else {
 720             bool fCheckResult = entry->GetTx().IsCoinBase() ||
 721                 Consensus::CheckTxInputs(entry->GetTx(), state, mempoolDuplicate, nSpendHeight);
 722             assert(fCheckResult);
 723             UpdateCoins(entry->GetTx(), mempoolDuplicate, 1000000);
 724             stepsSinceLastRemove = 0;
 725         }
 726     }
 727     for (auto it = mapNextTx.cbegin(); it != mapNextTx.cend(); it++) {
 728         uint256 hash = it->second->GetHash();
 729         indexed_transaction_set::const_iterator it2 = mapTx.find(hash);
 730         const CTransaction& tx = it2->GetTx();
 731         assert(it2 != mapTx.end());
 732         assert(&tx == it->second);
 733     }
 734
 735     assert(totalTxSize == checkTotal);
 736     assert(innerUsage == cachedInnerUsage);
 737 }
 738
 739 bool CTxMemPool::CompareDepthAndScore(const uint256& hasha, const uint256& hashb)
 740 {
 741     LOCK(cs);
 742     indexed_transaction_set::const_iterator i = mapTx.find(hasha);
 743     if (i == mapTx.end()) return false;
 744     indexed_transaction_set::const_iterator j = mapTx.find(hashb);
 745     if (j == mapTx.end()) return true;
 746     uint64_t counta = i->GetCountWithAncestors();
 747     uint64_t countb = j->GetCountWithAncestors();
 748     if (counta == countb) {
 749         return CompareTxMemPoolEntryByScore()(*i, *j);
 750     }
 751     return counta < countb;
 752 }
 753
 754 namespace {
 755 class DepthAndScoreComparator
 756 {
 757 public:
 758     bool operator()(const CTxMemPool::indexed_transaction_set::const_iterator& a, const CTxMemPool::indexed_transaction_set::const_iterator& b)
 759     {
 760         uint64_t counta = a->GetCountWithAncestors();
 761         uint64_t countb = b->GetCountWithAncestors();
 762         if (counta == countb) {
 763             return CompareTxMemPoolEntryByScore()(*a, *b);
 764         }
 765         return counta < countb;
 766     }
 767 };
 768 } // namespace
 769
 770 std::vector<CTxMemPool::indexed_transaction_set::const_iterator> CTxMemPool::GetSortedDepthAndScore() const
 771 {
 772     std::vector<indexed_transaction_set::const_iterator> iters;
 773     AssertLockHeld(cs);
 774
 775     iters.reserve(mapTx.size());
 776
 777     for (indexed_transaction_set::iterator mi = mapTx.begin(); mi != mapTx.end(); ++mi) {
 778         iters.push_back(mi);
 779     }
 780     std::sort(iters.begin(), iters.end(), DepthAndScoreComparator());
 781     return iters;
 782 }
 783
 784 void CTxMemPool::queryHashes(std::vector<uint256>& vtxid)
 785 {
 786     LOCK(cs);
 787     auto iters = GetSortedDepthAndScore();
 788
 789     vtxid.clear();
 790     vtxid.reserve(mapTx.size());
 791
 792     for (auto it : iters) {
 793         vtxid.push_back(it->GetTx().GetHash());
 794     }
 795 }
 796
 797 static TxMempoolInfo GetInfo(CTxMemPool::indexed_transaction_set::const_iterator it) {
 798     return TxMempoolInfo{it->GetSharedTx(), it->GetTime(), CFeeRate(it->GetFee(), it->GetTxSize()), it->GetModifiedFee() - it->GetFee()};
 799 }
 800
 801 std::vector<TxMempoolInfo> CTxMemPool::infoAll() const
 802 {
 803     LOCK(cs);
 804     auto iters = GetSortedDepthAndScore();
 805
 806     std::vector<TxMempoolInfo> ret;
 807     ret.reserve(mapTx.size());
 808     for (auto it : iters) {
 809         ret.push_back(GetInfo(it));
 810     }
 811
 812     return ret;
 813 }
 814
 815 CTransactionRef CTxMemPool::get(const uint256& hash) const
 816 {
 817     LOCK(cs);
 818     indexed_transaction_set::const_iterator i = mapTx.find(hash);
 819     if (i == mapTx.end())
 820         return nullptr;
 821     return i->GetSharedTx();
 822 }
 823
 824 TxMempoolInfo CTxMemPool::info(const uint256& hash) const
 825 {
 826     LOCK(cs);
 827     indexed_transaction_set::const_iterator i = mapTx.find(hash);
 828     if (i == mapTx.end())
 829         return TxMempoolInfo();
 830     return GetInfo(i);
 831 }
 832
 833 void CTxMemPool::PrioritiseTransaction(const uint256& hash, const CAmount& nFeeDelta)
 834 {
 835     {
 836         LOCK(cs);
 837         CAmount &delta = mapDeltas[hash];
 838         delta += nFeeDelta;
 839         txiter it = mapTx.find(hash);
 840         if (it != mapTx.end()) {
 841             mapTx.modify(it, update_fee_delta(delta));
 842             // Now update all ancestors' modified fees with descendants
 843             setEntries setAncestors;
 844             uint64_t nNoLimit = std::numeric_limits<uint64_t>::max();
 845             std::string dummy;
 846             CalculateMemPoolAncestors(*it, setAncestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy, false);
 847             for (txiter ancestorIt : setAncestors) {
 848                 mapTx.modify(ancestorIt, update_descendant_state(0, nFeeDelta, 0));
 849             }
 850             // Now update all descendants' modified fees with ancestors
 851             setEntries setDescendants;
 852             CalculateDescendants(it, setDescendants);
 853             setDescendants.erase(it);
 854             for (txiter descendantIt : setDescendants) {
 855                 mapTx.modify(descendantIt, update_ancestor_state(0, nFeeDelta, 0, 0));
 856             }
 857             ++nTransactionsUpdated;
 858         }
 859     }
 860     LogPrintf("PrioritiseTransaction: %s feerate += %s\n", hash.ToString(), FormatMoney(nFeeDelta));
 861 }
 862
 863 void CTxMemPool::ApplyDelta(const uint256 hash, CAmount &nFeeDelta) const
 864 {
 865     LOCK(cs);
 866     std::map<uint256, CAmount>::const_iterator pos = mapDeltas.find(hash);
 867     if (pos == mapDeltas.end())
 868         return;
 869     const CAmount &delta = pos->second;
 870     nFeeDelta += delta;
 871 }
 872
 873 void CTxMemPool::ClearPrioritisation(const uint256 hash)
 874 {
 875     LOCK(cs);
 876     mapDeltas.erase(hash);
 877 }
 878
 879 bool CTxMemPool::HasNoInputsOf(const CTransaction &tx) const
 880 {
 881     for (unsigned int i = 0; i < tx.vin.size(); i++)
 882         if (exists(tx.vin[i].prevout.hash))
 883             return false;
 884     return true;
 885 }
 886
 887 CCoinsViewMemPool::CCoinsViewMemPool(CCoinsView* baseIn, const CTxMemPool& mempoolIn) : CCoinsViewBacked(baseIn), mempool(mempoolIn) { }
 888
 889 bool CCoinsViewMemPool::GetCoin(const COutPoint &outpoint, Coin &coin) const {
 890     // If an entry in the mempool exists, always return that one, as it's guaranteed to never
 891     // conflict with the underlying cache, and it cannot have pruned entries (as it contains full)
 892     // transactions. First checking the underlying cache risks returning a pruned entry instead.
 893     CTransactionRef ptx = mempool.get(outpoint.hash);
 894     if (ptx) {
 895         if (outpoint.n < ptx->vout.size()) {
 896             coin = Coin(ptx->vout[outpoint.n], MEMPOOL_HEIGHT, false);
 897             return true;
 898         } else {
 899             return false;
 900         }
 901     }
 902     return base->GetCoin(outpoint, coin);
 903 }
 904
 905 size_t CTxMemPool::DynamicMemoryUsage() const {
 906     LOCK(cs);
 907     // Estimate the overhead of mapTx to be 15 pointers + an allocation, as no exact formula for boost::multi_index_contained is implemented.
 908     return memusage::MallocUsage(sizeof(CTxMemPoolEntry) + 15 * sizeof(void*)) * mapTx.size() + memusage::DynamicUsage(mapNextTx) + memusage::DynamicUsage(mapDeltas) + memusage::DynamicUsage(mapLinks) + memusage::DynamicUsage(vTxHashes) + cachedInnerUsage;
 909 }
 910
 911 void CTxMemPool::RemoveStaged(setEntries &stage, bool updateDescendants, MemPoolRemovalReason reason) {
 912     AssertLockHeld(cs);
 913     UpdateForRemoveFromMempool(stage, updateDescendants);
 914     for (const txiter& it : stage) {
 915         removeUnchecked(it, reason);
 916     }
 917 }
 918
 919 int CTxMemPool::Expire(int64_t time) {
 920     LOCK(cs);
 921     indexed_transaction_set::index<entry_time>::type::iterator it = mapTx.get<entry_time>().begin();
 922     setEntries toremove;
 923     while (it != mapTx.get<entry_time>().end() && it->GetTime() < time) {
 924         toremove.insert(mapTx.project<0>(it));
 925         it++;
 926     }
 927     setEntries stage;
 928     for (txiter removeit : toremove) {
 929         CalculateDescendants(removeit, stage);
 930     }
 931     RemoveStaged(stage, false, MemPoolRemovalReason::EXPIRY);
 932     return stage.size();
 933 }
 934
 935 bool CTxMemPool::addUnchecked(const uint256&hash, const CTxMemPoolEntry &entry, bool validFeeEstimate)
 936 {
 937     LOCK(cs);
 938     setEntries setAncestors;
 939     uint64_t nNoLimit = std::numeric_limits<uint64_t>::max();
 940     std::string dummy;
 941     CalculateMemPoolAncestors(entry, setAncestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy);
 942     return addUnchecked(hash, entry, setAncestors, validFeeEstimate);
 943 }
 944
 945 void CTxMemPool::UpdateChild(txiter entry, txiter child, bool add)
 946 {
 947     setEntries s;
 948     if (add && mapLinks[entry].children.insert(child).second) {
 949         cachedInnerUsage += memusage::IncrementalDynamicUsage(s);
 950     } else if (!add && mapLinks[entry].children.erase(child)) {
 951         cachedInnerUsage -= memusage::IncrementalDynamicUsage(s);
 952     }
 953 }
 954
 955 void CTxMemPool::UpdateParent(txiter entry, txiter parent, bool add)
 956 {
 957     setEntries s;
 958     if (add && mapLinks[entry].parents.insert(parent).second) {
 959         cachedInnerUsage += memusage::IncrementalDynamicUsage(s);
 960     } else if (!add && mapLinks[entry].parents.erase(parent)) {
 961         cachedInnerUsage -= memusage::IncrementalDynamicUsage(s);
 962     }
 963 }
 964
 965 const CTxMemPool::setEntries & CTxMemPool::GetMemPoolParents(txiter entry) const
 966 {
 967     assert (entry != mapTx.end());
 968     txlinksMap::const_iterator it = mapLinks.find(entry);
 969     assert(it != mapLinks.end());
 970     return it->second.parents;
 971 }
 972
 973 const CTxMemPool::setEntries & CTxMemPool::GetMemPoolChildren(txiter entry) const
 974 {
 975     assert (entry != mapTx.end());
 976     txlinksMap::const_iterator it = mapLinks.find(entry);
 977     assert(it != mapLinks.end());
 978     return it->second.children;
 979 }
 980
 981 CFeeRate CTxMemPool::GetMinFee(size_t sizelimit) const {
 982     LOCK(cs);
 983     if (!blockSinceLastRollingFeeBump || rollingMinimumFeeRate == 0)
 984         return CFeeRate(rollingMinimumFeeRate);
 985
 986     int64_t time = GetTime();
 987     if (time > lastRollingFeeUpdate + 10) {
 988         double halflife = ROLLING_FEE_HALFLIFE;
 989         if (DynamicMemoryUsage() < sizelimit / 4)
 990             halflife /= 4;
 991         else if (DynamicMemoryUsage() < sizelimit / 2)
 992             halflife /= 2;
 993
 994         rollingMinimumFeeRate = rollingMinimumFeeRate / pow(2.0, (time - lastRollingFeeUpdate) / halflife);
 995         lastRollingFeeUpdate = time;
 996
 997         if (rollingMinimumFeeRate < (double)incrementalRelayFee.GetFeePerK() / 2) {
 998             rollingMinimumFeeRate = 0;
 999             return CFeeRate(0);
1000         }
1001     }
1002     return std::max(CFeeRate(rollingMinimumFeeRate), incrementalRelayFee);
1003 }
1004
1005 void CTxMemPool::trackPackageRemoved(const CFeeRate& rate) {
1006     AssertLockHeld(cs);
1007     if (rate.GetFeePerK() > rollingMinimumFeeRate) {
1008         rollingMinimumFeeRate = rate.GetFeePerK();
1009         blockSinceLastRollingFeeBump = false;
1010     }
1011 }
1012
1013 void CTxMemPool::TrimToSize(size_t sizelimit, std::vector<COutPoint>* pvNoSpendsRemaining) {
1014     LOCK(cs);
1015
1016     unsigned nTxnRemoved = 0;
1017     CFeeRate maxFeeRateRemoved(0);
1018     while (!mapTx.empty() && DynamicMemoryUsage() > sizelimit) {
1019         indexed_transaction_set::index<descendant_score>::type::iterator it = mapTx.get<descendant_score>().begin();
1020
1021         // We set the new mempool min fee to the feerate of the removed set, plus the
1022         // "minimum reasonable fee rate" (ie some value under which we consider txn
1023         // to have 0 fee). This way, we don't allow txn to enter mempool with feerate
1024         // equal to txn which were removed with no block in between.
1025         CFeeRate removed(it->GetModFeesWithDescendants(), it->GetSizeWithDescendants());
1026         removed += incrementalRelayFee;
1027         trackPackageRemoved(removed);
1028         maxFeeRateRemoved = std::max(maxFeeRateRemoved, removed);
1029
1030         setEntries stage;
1031         CalculateDescendants(mapTx.project<0>(it), stage);
1032         nTxnRemoved += stage.size();
1033
1034         std::vector<CTransaction> txn;
1035         if (pvNoSpendsRemaining) {
1036             txn.reserve(stage.size());
1037             for (txiter iter : stage)
1038                 txn.push_back(iter->GetTx());
1039         }
1040         RemoveStaged(stage, false, MemPoolRemovalReason::SIZELIMIT);
1041         if (pvNoSpendsRemaining) {
1042             for (const CTransaction& tx : txn) {
1043                 for (const CTxIn& txin : tx.vin) {
1044                     if (exists(txin.prevout.hash)) continue;
1045                     pvNoSpendsRemaining->push_back(txin.prevout);
1046                 }
1047             }
1048         }
1049     }
1050
1051     if (maxFeeRateRemoved > CFeeRate(0)) {
1052         LogPrint(BCLog::MEMPOOL, "Removed %u txn, rolling minimum fee bumped to %s\n", nTxnRemoved, maxFeeRateRemoved.ToString());
1053     }
1054 }
1055
1056 bool CTxMemPool::TransactionWithinChainLimit(const uint256& txid, size_t chainLimit) const {
1057     LOCK(cs);
1058     auto it = mapTx.find(txid);
1059     return it == mapTx.end() || (it->GetCountWithAncestors() < chainLimit &&
1060        it->GetCountWithDescendants() < chainLimit);
1061 }
1062
1063 SaltedTxidHasher::SaltedTxidHasher() : k0(GetRand(std::numeric_limits<uint64_t>::max())), k1(GetRand(std::numeric_limits<uint64_t>::max())) {}