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