src/txmempool.cpp

   1 // Copyright (c) 2009-2010 Satoshi Nakamoto
   2 // Copyright (c) 2009-2014 The Bitcoin Core developers
   3 // Distributed under the MIT software license, see the accompanying
   4 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
   5
   6 #include "txmempool.h"
   7
   8 #include "clientversion.h"
   9 #include "main.h"
  10 #include "streams.h"
  11 #include "util.h"
  12 #include "utilmoneystr.h"
  13 #include "version.h"
  14
  15 #include <boost/circular_buffer.hpp>
  16
  17 using namespace std;
  18
  19 CTxMemPoolEntry::CTxMemPoolEntry():
  20     nFee(0), nTxSize(0), nModSize(0), nTime(0), dPriority(0.0)
  21 {
  22     nHeight = MEMPOOL_HEIGHT;
  23 }
  24
  25 CTxMemPoolEntry::CTxMemPoolEntry(const CTransaction& _tx, const CAmount& _nFee,
  26                                  int64_t _nTime, double _dPriority,
  27                                  unsigned int _nHeight):
  28     tx(_tx), nFee(_nFee), nTime(_nTime), dPriority(_dPriority), nHeight(_nHeight)
  29 {
  30     nTxSize = ::GetSerializeSize(tx, SER_NETWORK, PROTOCOL_VERSION);
  31
  32     nModSize = tx.CalculateModifiedSize(nTxSize);
  33 }
  34
  35 CTxMemPoolEntry::CTxMemPoolEntry(const CTxMemPoolEntry& other)
  36 {
  37     *this = other;
  38 }
  39
  40 double
  41 CTxMemPoolEntry::GetPriority(unsigned int currentHeight) const
  42 {
  43     CAmount nValueIn = tx.GetValueOut()+nFee;
  44     double deltaPriority = ((double)(currentHeight-nHeight)*nValueIn)/nModSize;
  45     double dResult = dPriority + deltaPriority;
  46     return dResult;
  47 }
  48
  49 /**
  50  * Keep track of fee/priority for transactions confirmed within N blocks
  51  */
  52 class CBlockAverage
  53 {
  54 private:
  55     boost::circular_buffer<CFeeRate> feeSamples;
  56     boost::circular_buffer<double> prioritySamples;
  57
  58     template<typename T> std::vector<T> buf2vec(boost::circular_buffer<T> buf) const
  59     {
  60         std::vector<T> vec(buf.begin(), buf.end());
  61         return vec;
  62     }
  63
  64 public:
  65     CBlockAverage() : feeSamples(100), prioritySamples(100) { }
  66
  67     void RecordFee(const CFeeRate& feeRate) {
  68         feeSamples.push_back(feeRate);
  69     }
  70
  71     void RecordPriority(double priority) {
  72         prioritySamples.push_back(priority);
  73     }
  74
  75     size_t FeeSamples() const { return feeSamples.size(); }
  76     size_t GetFeeSamples(std::vector<CFeeRate>& insertInto) const
  77     {
  78         BOOST_FOREACH(const CFeeRate& f, feeSamples)
  79             insertInto.push_back(f);
  80         return feeSamples.size();
  81     }
  82     size_t PrioritySamples() const { return prioritySamples.size(); }
  83     size_t GetPrioritySamples(std::vector<double>& insertInto) const
  84     {
  85         BOOST_FOREACH(double d, prioritySamples)
  86             insertInto.push_back(d);
  87         return prioritySamples.size();
  88     }
  89
  90     /**
  91      * Used as belt-and-suspenders check when reading to detect
  92      * file corruption
  93      */
  94     static bool AreSane(const CFeeRate fee, const CFeeRate& minRelayFee)
  95     {
  96         if (fee < CFeeRate(0))
  97             return false;
  98         if (fee.GetFeePerK() > minRelayFee.GetFeePerK() * 10000)
  99             return false;
 100         return true;
 101     }
 102     static bool AreSane(const std::vector<CFeeRate>& vecFee, const CFeeRate& minRelayFee)
 103     {
 104         BOOST_FOREACH(CFeeRate fee, vecFee)
 105         {
 106             if (!AreSane(fee, minRelayFee))
 107                 return false;
 108         }
 109         return true;
 110     }
 111     static bool AreSane(const double priority)
 112     {
 113         return priority >= 0;
 114     }
 115     static bool AreSane(const std::vector<double> vecPriority)
 116     {
 117         BOOST_FOREACH(double priority, vecPriority)
 118         {
 119             if (!AreSane(priority))
 120                 return false;
 121         }
 122         return true;
 123     }
 124
 125     void Write(CAutoFile& fileout) const
 126     {
 127         std::vector<CFeeRate> vecFee = buf2vec(feeSamples);
 128         fileout << vecFee;
 129         std::vector<double> vecPriority = buf2vec(prioritySamples);
 130         fileout << vecPriority;
 131     }
 132
 133     void Read(CAutoFile& filein, const CFeeRate& minRelayFee) {
 134         std::vector<CFeeRate> vecFee;
 135         filein >> vecFee;
 136         if (AreSane(vecFee, minRelayFee))
 137             feeSamples.insert(feeSamples.end(), vecFee.begin(), vecFee.end());
 138         else
 139             throw runtime_error("Corrupt fee value in estimates file.");
 140         std::vector<double> vecPriority;
 141         filein >> vecPriority;
 142         if (AreSane(vecPriority))
 143             prioritySamples.insert(prioritySamples.end(), vecPriority.begin(), vecPriority.end());
 144         else
 145             throw runtime_error("Corrupt priority value in estimates file.");
 146         if (feeSamples.size() + prioritySamples.size() > 0)
 147             LogPrint("estimatefee", "Read %d fee samples and %d priority samples\n",
 148                      feeSamples.size(), prioritySamples.size());
 149     }
 150 };
 151
 152 class CMinerPolicyEstimator
 153 {
 154 private:
 155     /**
 156      * Records observed averages transactions that confirmed within one block, two blocks,
 157      * three blocks etc.
 158      */
 159     std::vector<CBlockAverage> history;
 160     std::vector<CFeeRate> sortedFeeSamples;
 161     std::vector<double> sortedPrioritySamples;
 162
 163     int nBestSeenHeight;
 164
 165     /**
 166      * nBlocksAgo is 0 based, i.e. transactions that confirmed in the highest seen block are
 167      * nBlocksAgo == 0, transactions in the block before that are nBlocksAgo == 1 etc.
 168      */
 169     void seenTxConfirm(const CFeeRate& feeRate, const CFeeRate& minRelayFee, double dPriority, int nBlocksAgo)
 170     {
 171         // Last entry records "everything else".
 172         int nBlocksTruncated = min(nBlocksAgo, (int) history.size() - 1);
 173         assert(nBlocksTruncated >= 0);
 174
 175         // We need to guess why the transaction was included in a block-- either
 176         // because it is high-priority or because it has sufficient fees.
 177         bool sufficientFee = (feeRate > minRelayFee);
 178         bool sufficientPriority = AllowFree(dPriority);
 179         const char* assignedTo = "unassigned";
 180         if (sufficientFee && !sufficientPriority && CBlockAverage::AreSane(feeRate, minRelayFee))
 181         {
 182             history[nBlocksTruncated].RecordFee(feeRate);
 183             assignedTo = "fee";
 184         }
 185         else if (sufficientPriority && !sufficientFee && CBlockAverage::AreSane(dPriority))
 186         {
 187             history[nBlocksTruncated].RecordPriority(dPriority);
 188             assignedTo = "priority";
 189         }
 190         else
 191         {
 192             // Neither or both fee and priority sufficient to get confirmed:
 193             // don't know why they got confirmed.
 194         }
 195         LogPrint("estimatefee", "Seen TX confirm: %s : %s fee/%g priority, took %d blocks\n",
 196                  assignedTo, feeRate.ToString(), dPriority, nBlocksAgo);
 197     }
 198
 199 public:
 200     CMinerPolicyEstimator(int nEntries) : nBestSeenHeight(0)
 201     {
 202         history.resize(nEntries);
 203     }
 204
 205     void seenBlock(const std::vector<CTxMemPoolEntry>& entries, int nBlockHeight, const CFeeRate minRelayFee)
 206     {
 207         if (nBlockHeight <= nBestSeenHeight)
 208         {
 209             // Ignore side chains and re-orgs; assuming they are random
 210             // they don't affect the estimate.
 211             // And if an attacker can re-org the chain at will, then
 212             // you've got much bigger problems than "attacker can influence
 213             // transaction fees."
 214             return;
 215         }
 216         nBestSeenHeight = nBlockHeight;
 217
 218         // Fill up the history buckets based on how long transactions took
 219         // to confirm.
 220         std::vector<std::vector<const CTxMemPoolEntry*> > entriesByConfirmations;
 221         entriesByConfirmations.resize(history.size());
 222         BOOST_FOREACH(const CTxMemPoolEntry& entry, entries)
 223         {
 224             // How many blocks did it take for miners to include this transaction?
 225             int delta = nBlockHeight - entry.GetHeight();
 226             if (delta <= 0)
 227             {
 228                 // Re-org made us lose height, this should only happen if we happen
 229                 // to re-org on a difficulty transition point: very rare!
 230                 continue;
 231             }
 232             if ((delta-1) >= (int)history.size())
 233                 delta = history.size(); // Last bucket is catch-all
 234             entriesByConfirmations.at(delta-1).push_back(&entry);
 235         }
 236         for (size_t i = 0; i < entriesByConfirmations.size(); i++)
 237         {
 238             std::vector<const CTxMemPoolEntry*> &e = entriesByConfirmations.at(i);
 239             // Insert at most 10 random entries per bucket, otherwise a single block
 240             // can dominate an estimate:
 241             if (e.size() > 10) {
 242                 std::random_shuffle(e.begin(), e.end());
 243                 e.resize(10);
 244             }
 245             BOOST_FOREACH(const CTxMemPoolEntry* entry, e)
 246             {
 247                 // Fees are stored and reported as BTC-per-kb:
 248                 CFeeRate feeRate(entry->GetFee(), entry->GetTxSize());
 249                 double dPriority = entry->GetPriority(entry->GetHeight()); // Want priority when it went IN
 250                 seenTxConfirm(feeRate, minRelayFee, dPriority, i);
 251             }
 252         }
 253
 254         // After new samples are added, we have to clear the sorted lists,
 255         // so they'll be resorted the next time someone asks for an estimate
 256         sortedFeeSamples.clear();
 257         sortedPrioritySamples.clear();
 258
 259         for (size_t i = 0; i < history.size(); i++) {
 260             if (history[i].FeeSamples() + history[i].PrioritySamples() > 0)
 261                 LogPrint("estimatefee", "estimates: for confirming within %d blocks based on %d/%d samples, fee=%s, prio=%g\n",
 262                          i,
 263                          history[i].FeeSamples(), history[i].PrioritySamples(),
 264                          estimateFee(i+1).ToString(), estimatePriority(i+1));
 265         }
 266     }
 267
 268     /**
 269      * Can return CFeeRate(0) if we don't have any data for that many blocks back. nBlocksToConfirm is 1 based.
 270      */
 271     CFeeRate estimateFee(int nBlocksToConfirm)
 272     {
 273         nBlocksToConfirm--;
 274
 275         if (nBlocksToConfirm < 0 || nBlocksToConfirm >= (int)history.size())
 276             return CFeeRate(0);
 277
 278         if (sortedFeeSamples.size() == 0)
 279         {
 280             for (size_t i = 0; i < history.size(); i++)
 281                 history.at(i).GetFeeSamples(sortedFeeSamples);
 282             std::sort(sortedFeeSamples.begin(), sortedFeeSamples.end(),
 283                       std::greater<CFeeRate>());
 284         }
 285         if (sortedFeeSamples.size() < 11)
 286         {
 287             // Eleven is Gavin's Favorite Number
 288             // ... but we also take a maximum of 10 samples per block so eleven means
 289             // we're getting samples from at least two different blocks
 290             return CFeeRate(0);
 291         }
 292
 293         int nBucketSize = history.at(nBlocksToConfirm).FeeSamples();
 294
 295         // Estimates should not increase as number of confirmations goes up,
 296         // but the estimates are noisy because confirmations happen discretely
 297         // in blocks. To smooth out the estimates, use all samples in the history
 298         // and use the nth highest where n is (number of samples in previous bucket +
 299         // half the samples in nBlocksToConfirm bucket):
 300         size_t nPrevSize = 0;
 301         for (int i = 0; i < nBlocksToConfirm; i++)
 302             nPrevSize += history.at(i).FeeSamples();
 303         size_t index = min(nPrevSize + nBucketSize/2, sortedFeeSamples.size()-1);
 304         return sortedFeeSamples[index];
 305     }
 306     double estimatePriority(int nBlocksToConfirm)
 307     {
 308         nBlocksToConfirm--;
 309
 310         if (nBlocksToConfirm < 0 || nBlocksToConfirm >= (int)history.size())
 311             return -1;
 312
 313         if (sortedPrioritySamples.size() == 0)
 314         {
 315             for (size_t i = 0; i < history.size(); i++)
 316                 history.at(i).GetPrioritySamples(sortedPrioritySamples);
 317             std::sort(sortedPrioritySamples.begin(), sortedPrioritySamples.end(),
 318                       std::greater<double>());
 319         }
 320         if (sortedPrioritySamples.size() < 11)
 321             return -1.0;
 322
 323         int nBucketSize = history.at(nBlocksToConfirm).PrioritySamples();
 324
 325         // Estimates should not increase as number of confirmations needed goes up,
 326         // but the estimates are noisy because confirmations happen discretely
 327         // in blocks. To smooth out the estimates, use all samples in the history
 328         // and use the nth highest where n is (number of samples in previous buckets +
 329         // half the samples in nBlocksToConfirm bucket).
 330         size_t nPrevSize = 0;
 331         for (int i = 0; i < nBlocksToConfirm; i++)
 332             nPrevSize += history.at(i).PrioritySamples();
 333         size_t index = min(nPrevSize + nBucketSize/2, sortedPrioritySamples.size()-1);
 334         return sortedPrioritySamples[index];
 335     }
 336
 337     void Write(CAutoFile& fileout) const
 338     {
 339         fileout << nBestSeenHeight;
 340         fileout << history.size();
 341         BOOST_FOREACH(const CBlockAverage& entry, history)
 342         {
 343             entry.Write(fileout);
 344         }
 345     }
 346
 347     void Read(CAutoFile& filein, const CFeeRate& minRelayFee)
 348     {
 349         int nFileBestSeenHeight;
 350         filein >> nFileBestSeenHeight;
 351         size_t numEntries;
 352         filein >> numEntries;
 353         if (numEntries <= 0 || numEntries > 10000)
 354             throw runtime_error("Corrupt estimates file. Must have between 1 and 10k entries.");
 355
 356         std::vector<CBlockAverage> fileHistory;
 357
 358         for (size_t i = 0; i < numEntries; i++)
 359         {
 360             CBlockAverage entry;
 361             entry.Read(filein, minRelayFee);
 362             fileHistory.push_back(entry);
 363         }
 364
 365         // Now that we've processed the entire fee estimate data file and not
 366         // thrown any errors, we can copy it to our history
 367         nBestSeenHeight = nFileBestSeenHeight;
 368         history = fileHistory;
 369         assert(history.size() > 0);
 370     }
 371 };
 372
 373
 374 CTxMemPool::CTxMemPool(const CFeeRate& _minRelayFee) :
 375     nTransactionsUpdated(0),
 376     minRelayFee(_minRelayFee)
 377 {
 378     // Sanity checks off by default for performance, because otherwise
 379     // accepting transactions becomes O(N^2) where N is the number
 380     // of transactions in the pool
 381     fSanityCheck = false;
 382
 383     // 25 blocks is a compromise between using a lot of disk/memory and
 384     // trying to give accurate estimates to people who might be willing
 385     // to wait a day or two to save a fraction of a penny in fees.
 386     // Confirmation times for very-low-fee transactions that take more
 387     // than an hour or three to confirm are highly variable.
 388     minerPolicyEstimator = new CMinerPolicyEstimator(25);
 389 }
 390
 391 CTxMemPool::~CTxMemPool()
 392 {
 393     delete minerPolicyEstimator;
 394 }
 395
 396 void CTxMemPool::pruneSpent(const uint256 &hashTx, CCoins &coins)
 397 {
 398     LOCK(cs);
 399
 400     std::map<COutPoint, CInPoint>::iterator it = mapNextTx.lower_bound(COutPoint(hashTx, 0));
 401
 402     // iterate over all COutPoints in mapNextTx whose hash equals the provided hashTx
 403     while (it != mapNextTx.end() && it->first.hash == hashTx) {
 404         coins.Spend(it->first.n); // and remove those outputs from coins
 405         it++;
 406     }
 407 }
 408
 409 unsigned int CTxMemPool::GetTransactionsUpdated() const
 410 {
 411     LOCK(cs);
 412     return nTransactionsUpdated;
 413 }
 414
 415 void CTxMemPool::AddTransactionsUpdated(unsigned int n)
 416 {
 417     LOCK(cs);
 418     nTransactionsUpdated += n;
 419 }
 420
 421
 422 bool CTxMemPool::addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry)
 423 {
 424     // Add to memory pool without checking anything.
 425     // Used by main.cpp AcceptToMemoryPool(), which DOES do
 426     // all the appropriate checks.
 427     LOCK(cs);
 428     {
 429         mapTx[hash] = entry;
 430         const CTransaction& tx = mapTx[hash].GetTx();
 431         for (unsigned int i = 0; i < tx.vin.size(); i++)
 432             mapNextTx[tx.vin[i].prevout] = CInPoint(&tx, i);
 433         nTransactionsUpdated++;
 434         totalTxSize += entry.GetTxSize();
 435     }
 436     return true;
 437 }
 438
 439
 440 void CTxMemPool::remove(const CTransaction &origTx, std::list<CTransaction>& removed, bool fRecursive)
 441 {
 442     // Remove transaction from memory pool
 443     {
 444         LOCK(cs);
 445         std::deque<uint256> txToRemove;
 446         txToRemove.push_back(origTx.GetHash());
 447         while (!txToRemove.empty())
 448         {
 449             uint256 hash = txToRemove.front();
 450             txToRemove.pop_front();
 451             if (!mapTx.count(hash))
 452                 continue;
 453             const CTransaction& tx = mapTx[hash].GetTx();
 454             if (fRecursive) {
 455                 for (unsigned int i = 0; i < tx.vout.size(); i++) {
 456                     std::map<COutPoint, CInPoint>::iterator it = mapNextTx.find(COutPoint(hash, i));
 457                     if (it == mapNextTx.end())
 458                         continue;
 459                     txToRemove.push_back(it->second.ptx->GetHash());
 460                 }
 461             }
 462             BOOST_FOREACH(const CTxIn& txin, tx.vin)
 463                 mapNextTx.erase(txin.prevout);
 464
 465             removed.push_back(tx);
 466             totalTxSize -= mapTx[hash].GetTxSize();
 467             mapTx.erase(hash);
 468             nTransactionsUpdated++;
 469         }
 470     }
 471 }
 472
 473 void CTxMemPool::removeCoinbaseSpends(const CCoinsViewCache *pcoins, unsigned int nMemPoolHeight)
 474 {
 475     // Remove transactions spending a coinbase which are now immature
 476     LOCK(cs);
 477     list<CTransaction> transactionsToRemove;
 478     for (std::map<uint256, CTxMemPoolEntry>::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
 479         const CTransaction& tx = it->second.GetTx();
 480         BOOST_FOREACH(const CTxIn& txin, tx.vin) {
 481             std::map<uint256, CTxMemPoolEntry>::const_iterator it2 = mapTx.find(txin.prevout.hash);
 482             if (it2 != mapTx.end())
 483                 continue;
 484             const CCoins *coins = pcoins->AccessCoins(txin.prevout.hash);
 485             if (fSanityCheck) assert(coins);
 486             if (!coins || (coins->IsCoinBase() && nMemPoolHeight - coins->nHeight < COINBASE_MATURITY)) {
 487                 transactionsToRemove.push_back(tx);
 488                 break;
 489             }
 490         }
 491     }
 492     BOOST_FOREACH(const CTransaction& tx, transactionsToRemove) {
 493         list<CTransaction> removed;
 494         remove(tx, removed, true);
 495     }
 496 }
 497
 498 void CTxMemPool::removeConflicts(const CTransaction &tx, std::list<CTransaction>& removed)
 499 {
 500     // Remove transactions which depend on inputs of tx, recursively
 501     list<CTransaction> result;
 502     LOCK(cs);
 503     BOOST_FOREACH(const CTxIn &txin, tx.vin) {
 504         std::map<COutPoint, CInPoint>::iterator it = mapNextTx.find(txin.prevout);
 505         if (it != mapNextTx.end()) {
 506             const CTransaction &txConflict = *it->second.ptx;
 507             if (txConflict != tx)
 508             {
 509                 remove(txConflict, removed, true);
 510             }
 511         }
 512     }
 513 }
 514
 515 /**
 516  * Called when a block is connected. Removes from mempool and updates the miner fee estimator.
 517  */
 518 void CTxMemPool::removeForBlock(const std::vector<CTransaction>& vtx, unsigned int nBlockHeight,
 519                                 std::list<CTransaction>& conflicts)
 520 {
 521     LOCK(cs);
 522     std::vector<CTxMemPoolEntry> entries;
 523     BOOST_FOREACH(const CTransaction& tx, vtx)
 524     {
 525         uint256 hash = tx.GetHash();
 526         if (mapTx.count(hash))
 527             entries.push_back(mapTx[hash]);
 528     }
 529     minerPolicyEstimator->seenBlock(entries, nBlockHeight, minRelayFee);
 530     BOOST_FOREACH(const CTransaction& tx, vtx)
 531     {
 532         std::list<CTransaction> dummy;
 533         remove(tx, dummy, false);
 534         removeConflicts(tx, conflicts);
 535         ClearPrioritisation(tx.GetHash());
 536     }
 537 }
 538
 539
 540 void CTxMemPool::clear()
 541 {
 542     LOCK(cs);
 543     mapTx.clear();
 544     mapNextTx.clear();
 545     totalTxSize = 0;
 546     ++nTransactionsUpdated;
 547 }
 548
 549 void CTxMemPool::check(const CCoinsViewCache *pcoins) const
 550 {
 551     if (!fSanityCheck)
 552         return;
 553
 554     LogPrint("mempool", "Checking mempool with %u transactions and %u inputs\n", (unsigned int)mapTx.size(), (unsigned int)mapNextTx.size());
 555
 556     uint64_t checkTotal = 0;
 557
 558     CCoinsViewCache mempoolDuplicate(const_cast<CCoinsViewCache*>(pcoins));
 559
 560     LOCK(cs);
 561     list<const CTxMemPoolEntry*> waitingOnDependants;
 562     for (std::map<uint256, CTxMemPoolEntry>::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
 563         unsigned int i = 0;
 564         checkTotal += it->second.GetTxSize();
 565         const CTransaction& tx = it->second.GetTx();
 566         bool fDependsWait = false;
 567         BOOST_FOREACH(const CTxIn &txin, tx.vin) {
 568             // Check that every mempool transaction's inputs refer to available coins, or other mempool tx's.
 569             std::map<uint256, CTxMemPoolEntry>::const_iterator it2 = mapTx.find(txin.prevout.hash);
 570             if (it2 != mapTx.end()) {
 571                 const CTransaction& tx2 = it2->second.GetTx();
 572                 assert(tx2.vout.size() > txin.prevout.n && !tx2.vout[txin.prevout.n].IsNull());
 573                 fDependsWait = true;
 574             } else {
 575                 const CCoins* coins = pcoins->AccessCoins(txin.prevout.hash);
 576                 assert(coins && coins->IsAvailable(txin.prevout.n));
 577             }
 578             // Check whether its inputs are marked in mapNextTx.
 579             std::map<COutPoint, CInPoint>::const_iterator it3 = mapNextTx.find(txin.prevout);
 580             assert(it3 != mapNextTx.end());
 581             assert(it3->second.ptx == &tx);
 582             assert(it3->second.n == i);
 583             i++;
 584         }
 585         if (fDependsWait)
 586             waitingOnDependants.push_back(&it->second);
 587         else {
 588             CValidationState state; CTxUndo undo;
 589             assert(CheckInputs(tx, state, mempoolDuplicate, false, 0, false, NULL));
 590             UpdateCoins(tx, state, mempoolDuplicate, undo, 1000000);
 591         }
 592     }
 593     unsigned int stepsSinceLastRemove = 0;
 594     while (!waitingOnDependants.empty()) {
 595         const CTxMemPoolEntry* entry = waitingOnDependants.front();
 596         waitingOnDependants.pop_front();
 597         CValidationState state;
 598         if (!mempoolDuplicate.HaveInputs(entry->GetTx())) {
 599             waitingOnDependants.push_back(entry);
 600             stepsSinceLastRemove++;
 601             assert(stepsSinceLastRemove < waitingOnDependants.size());
 602         } else {
 603             assert(CheckInputs(entry->GetTx(), state, mempoolDuplicate, false, 0, false, NULL));
 604             CTxUndo undo;
 605             UpdateCoins(entry->GetTx(), state, mempoolDuplicate, undo, 1000000);
 606             stepsSinceLastRemove = 0;
 607         }
 608     }
 609     for (std::map<COutPoint, CInPoint>::const_iterator it = mapNextTx.begin(); it != mapNextTx.end(); it++) {
 610         uint256 hash = it->second.ptx->GetHash();
 611         map<uint256, CTxMemPoolEntry>::const_iterator it2 = mapTx.find(hash);
 612         const CTransaction& tx = it2->second.GetTx();
 613         assert(it2 != mapTx.end());
 614         assert(&tx == it->second.ptx);
 615         assert(tx.vin.size() > it->second.n);
 616         assert(it->first == it->second.ptx->vin[it->second.n].prevout);
 617     }
 618
 619     assert(totalTxSize == checkTotal);
 620 }
 621
 622 void CTxMemPool::queryHashes(vector<uint256>& vtxid)
 623 {
 624     vtxid.clear();
 625
 626     LOCK(cs);
 627     vtxid.reserve(mapTx.size());
 628     for (map<uint256, CTxMemPoolEntry>::iterator mi = mapTx.begin(); mi != mapTx.end(); ++mi)
 629         vtxid.push_back((*mi).first);
 630 }
 631
 632 bool CTxMemPool::lookup(uint256 hash, CTransaction& result) const
 633 {
 634     LOCK(cs);
 635     map<uint256, CTxMemPoolEntry>::const_iterator i = mapTx.find(hash);
 636     if (i == mapTx.end()) return false;
 637     result = i->second.GetTx();
 638     return true;
 639 }
 640
 641 CFeeRate CTxMemPool::estimateFee(int nBlocks) const
 642 {
 643     LOCK(cs);
 644     return minerPolicyEstimator->estimateFee(nBlocks);
 645 }
 646 double CTxMemPool::estimatePriority(int nBlocks) const
 647 {
 648     LOCK(cs);
 649     return minerPolicyEstimator->estimatePriority(nBlocks);
 650 }
 651
 652 bool
 653 CTxMemPool::WriteFeeEstimates(CAutoFile& fileout) const
 654 {
 655     try {
 656         LOCK(cs);
 657         fileout << 99900; // version required to read: 0.9.99 or later
 658         fileout << CLIENT_VERSION; // version that wrote the file
 659         minerPolicyEstimator->Write(fileout);
 660     }
 661     catch (const std::exception&) {
 662         LogPrintf("CTxMemPool::WriteFeeEstimates() : unable to write policy estimator data (non-fatal)");
 663         return false;
 664     }
 665     return true;
 666 }
 667
 668 bool
 669 CTxMemPool::ReadFeeEstimates(CAutoFile& filein)
 670 {
 671     try {
 672         int nVersionRequired, nVersionThatWrote;
 673         filein >> nVersionRequired >> nVersionThatWrote;
 674         if (nVersionRequired > CLIENT_VERSION)
 675             return error("CTxMemPool::ReadFeeEstimates() : up-version (%d) fee estimate file", nVersionRequired);
 676
 677         LOCK(cs);
 678         minerPolicyEstimator->Read(filein, minRelayFee);
 679     }
 680     catch (const std::exception&) {
 681         LogPrintf("CTxMemPool::ReadFeeEstimates() : unable to read policy estimator data (non-fatal)");
 682         return false;
 683     }
 684     return true;
 685 }
 686
 687 void CTxMemPool::PrioritiseTransaction(const uint256 hash, const string strHash, double dPriorityDelta, const CAmount& nFeeDelta)
 688 {
 689     {
 690         LOCK(cs);
 691         std::pair<double, CAmount> &deltas = mapDeltas[hash];
 692         deltas.first += dPriorityDelta;
 693         deltas.second += nFeeDelta;
 694     }
 695     LogPrintf("PrioritiseTransaction: %s priority += %f, fee += %d\n", strHash, dPriorityDelta, FormatMoney(nFeeDelta));
 696 }
 697
 698 void CTxMemPool::ApplyDeltas(const uint256 hash, double &dPriorityDelta, CAmount &nFeeDelta)
 699 {
 700     LOCK(cs);
 701     std::map<uint256, std::pair<double, CAmount> >::iterator pos = mapDeltas.find(hash);
 702     if (pos == mapDeltas.end())
 703         return;
 704     const std::pair<double, CAmount> &deltas = pos->second;
 705     dPriorityDelta += deltas.first;
 706     nFeeDelta += deltas.second;
 707 }
 708
 709 void CTxMemPool::ClearPrioritisation(const uint256 hash)
 710 {
 711     LOCK(cs);
 712     mapDeltas.erase(hash);
 713 }
 714
 715
 716 CCoinsViewMemPool::CCoinsViewMemPool(CCoinsView *baseIn, CTxMemPool &mempoolIn) : CCoinsViewBacked(baseIn), mempool(mempoolIn) { }
 717
 718 bool CCoinsViewMemPool::GetCoins(const uint256 &txid, CCoins &coins) const {
 719     // If an entry in the mempool exists, always return that one, as it's guaranteed to never
 720     // conflict with the underlying cache, and it cannot have pruned entries (as it contains full)
 721     // transactions. First checking the underlying cache risks returning a pruned entry instead.
 722     CTransaction tx;
 723     if (mempool.lookup(txid, tx)) {
 724         coins = CCoins(tx, MEMPOOL_HEIGHT);
 725         return true;
 726     }
 727     return (base->GetCoins(txid, coins) && !coins.IsPruned());
 728 }
 729
 730 bool CCoinsViewMemPool::HaveCoins(const uint256 &txid) const {
 731     return mempool.exists(txid) || base->HaveCoins(txid);
 732 }