src/txmempool.h

   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 #ifndef BITCOIN_TXMEMPOOL_H
   7 #define BITCOIN_TXMEMPOOL_H
   8
   9 #include <list>
  10
  11 #include "amount.h"
  12 #include "coins.h"
  13 #include "primitives/transaction.h"
  14 #include "sync.h"
  15
  16 #undef foreach
  17 #include "boost/multi_index_container.hpp"
  18 #include "boost/multi_index/ordered_index.hpp"
  19
  20 class CAutoFile;
  21
  22 inline double AllowFreeThreshold()
  23 {
  24     return COIN * 144 / 250;
  25 }
  26
  27 inline bool AllowFree(double dPriority)
  28 {
  29     // Large (in bytes) low-priority (new, small-coin) transactions
  30     // need a fee.
  31     return dPriority > AllowFreeThreshold();
  32 }
  33
  34 /** Fake height value used in CCoins to signify they are only in the memory pool (since 0.8) */
  35 static const unsigned int MEMPOOL_HEIGHT = 0x7FFFFFFF;
  36
  37 /**
  38  * CTxMemPool stores these:
  39  */
  40 class CTxMemPoolEntry
  41 {
  42 private:
  43     CTransaction tx;
  44     CAmount nFee; //! Cached to avoid expensive parent-transaction lookups
  45     size_t nTxSize; //! ... and avoid recomputing tx size
  46     size_t nModSize; //! ... and modified size for priority
  47     size_t nUsageSize; //! ... and total memory usage
  48     CFeeRate feeRate; //! ... and fee per kB
  49     int64_t nTime; //! Local time when entering the mempool
  50     double dPriority; //! Priority when entering the mempool
  51     unsigned int nHeight; //! Chain height when entering the mempool
  52     bool hadNoDependencies; //! Not dependent on any other txs when it entered the mempool
  53     bool spendsCoinbase; //! keep track of transactions that spend a coinbase
  54     uint32_t nBranchId; //! Branch ID this transaction is known to commit to, cached for efficiency
  55
  56 public:
  57     CTxMemPoolEntry(const CTransaction& _tx, const CAmount& _nFee,
  58                     int64_t _nTime, double _dPriority, unsigned int _nHeight,
  59                     bool poolHasNoInputsOf, bool spendsCoinbase, uint32_t nBranchId);
  60     CTxMemPoolEntry();
  61     CTxMemPoolEntry(const CTxMemPoolEntry& other);
  62
  63     const CTransaction& GetTx() const { return this->tx; }
  64     double GetPriority(unsigned int currentHeight) const;
  65     CAmount GetFee() const { return nFee; }
  66     CFeeRate GetFeeRate() const { return feeRate; }
  67     size_t GetTxSize() const { return nTxSize; }
  68     int64_t GetTime() const { return nTime; }
  69     unsigned int GetHeight() const { return nHeight; }
  70     bool WasClearAtEntry() const { return hadNoDependencies; }
  71     size_t DynamicMemoryUsage() const { return nUsageSize; }
  72
  73     bool GetSpendsCoinbase() const { return spendsCoinbase; }
  74     uint32_t GetValidatedBranchId() const { return nBranchId; }
  75 };
  76
  77 // extracts a TxMemPoolEntry's transaction hash
  78 struct mempoolentry_txid
  79 {
  80     typedef uint256 result_type;
  81     result_type operator() (const CTxMemPoolEntry &entry) const
  82     {
  83         return entry.GetTx().GetHash();
  84     }
  85 };
  86
  87 class CompareTxMemPoolEntryByFee
  88 {
  89 public:
  90     bool operator()(const CTxMemPoolEntry& a, const CTxMemPoolEntry& b)
  91     {
  92         if (a.GetFeeRate() == b.GetFeeRate())
  93             return a.GetTime() < b.GetTime();
  94         return a.GetFeeRate() > b.GetFeeRate();
  95     }
  96 };
  97
  98 class CBlockPolicyEstimator;
  99
 100 /** An inpoint - a combination of a transaction and an index n into its vin */
 101 class CInPoint
 102 {
 103 public:
 104     const CTransaction* ptx;
 105     uint32_t n;
 106
 107     CInPoint() { SetNull(); }
 108     CInPoint(const CTransaction* ptxIn, uint32_t nIn) { ptx = ptxIn; n = nIn; }
 109     void SetNull() { ptx = NULL; n = (uint32_t) -1; }
 110     bool IsNull() const { return (ptx == NULL && n == (uint32_t) -1); }
 111     size_t DynamicMemoryUsage() const { return 0; }
 112 };
 113
 114 /**
 115  * CTxMemPool stores valid-according-to-the-current-best-chain
 116  * transactions that may be included in the next block.
 117  *
 118  * Transactions are added when they are seen on the network
 119  * (or created by the local node), but not all transactions seen
 120  * are added to the pool: if a new transaction double-spends
 121  * an input of a transaction in the pool, it is dropped,
 122  * as are non-standard transactions.
 123  */
 124 class CTxMemPool
 125 {
 126 private:
 127     uint32_t nCheckFrequency; //! Value n means that n times in 2^32 we check.
 128     unsigned int nTransactionsUpdated;
 129     CBlockPolicyEstimator* minerPolicyEstimator;
 130
 131     uint64_t totalTxSize = 0; //! sum of all mempool tx' byte sizes
 132     uint64_t cachedInnerUsage; //! sum of dynamic memory usage of all the map elements (NOT the maps themselves)
 133
 134     std::map<uint256, const CTransaction*> mapSproutNullifiers;
 135     std::map<uint256, const CTransaction*> mapSaplingNullifiers;
 136
 137     void checkNullifiers(NullifierType type) const;
 138
 139 public:
 140     typedef boost::multi_index_container<
 141         CTxMemPoolEntry,
 142         boost::multi_index::indexed_by<
 143             // sorted by txid
 144             boost::multi_index::ordered_unique<mempoolentry_txid>,
 145             // sorted by fee rate
 146             boost::multi_index::ordered_non_unique<
 147                 boost::multi_index::identity<CTxMemPoolEntry>,
 148                 CompareTxMemPoolEntryByFee
 149             >
 150         >
 151     > indexed_transaction_set;
 152
 153     mutable CCriticalSection cs;
 154     indexed_transaction_set mapTx;
 155     std::map<COutPoint, CInPoint> mapNextTx;
 156     std::map<uint256, std::pair<double, CAmount> > mapDeltas;
 157
 158     CTxMemPool(const CFeeRate& _minRelayFee);
 159     ~CTxMemPool();
 160
 161     /**
 162      * If sanity-checking is turned on, check makes sure the pool is
 163      * consistent (does not contain two transactions that spend the same inputs,
 164      * all inputs are in the mapNextTx array). If sanity-checking is turned off,
 165      * check does nothing.
 166      */
 167     void check(const CCoinsViewCache *pcoins) const;
 168     void setSanityCheck(double dFrequency = 1.0) { nCheckFrequency = static_cast<uint32_t>(dFrequency * 4294967295.0); }
 169
 170     bool addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry, bool fCurrentEstimate = true);
 171     void remove(const CTransaction &tx, std::list<CTransaction>& removed, bool fRecursive = false);
 172     void removeWithAnchor(const uint256 &invalidRoot);
 173     void removeForReorg(const CCoinsViewCache *pcoins, unsigned int nMemPoolHeight, int flags);
 174     void removeConflicts(const CTransaction &tx, std::list<CTransaction>& removed);
 175     void removeExpired(unsigned int nBlockHeight);
 176     void removeForBlock(const std::vector<CTransaction>& vtx, unsigned int nBlockHeight,
 177                         std::list<CTransaction>& conflicts, bool fCurrentEstimate = true);
 178     void removeWithoutBranchId(uint32_t nMemPoolBranchId);
 179     void clear();
 180     void queryHashes(std::vector<uint256>& vtxid);
 181     void pruneSpent(const uint256& hash, CCoins &coins);
 182     unsigned int GetTransactionsUpdated() const;
 183     void AddTransactionsUpdated(unsigned int n);
 184     /**
 185      * Check that none of this transactions inputs are in the mempool, and thus
 186      * the tx is not dependent on other mempool transactions to be included in a block.
 187      */
 188     bool HasNoInputsOf(const CTransaction& tx) const;
 189
 190     /** Affect CreateNewBlock prioritisation of transactions */
 191     void PrioritiseTransaction(const uint256 hash, const std::string strHash, double dPriorityDelta, const CAmount& nFeeDelta);
 192     void ApplyDeltas(const uint256 hash, double &dPriorityDelta, CAmount &nFeeDelta);
 193     void ClearPrioritisation(const uint256 hash);
 194
 195     bool nullifierExists(const uint256& nullifier, NullifierType type) const;
 196
 197     unsigned long size()
 198     {
 199         LOCK(cs);
 200         return mapTx.size();
 201     }
 202
 203     uint64_t GetTotalTxSize()
 204     {
 205         LOCK(cs);
 206         return totalTxSize;
 207     }
 208
 209     bool exists(uint256 hash) const
 210     {
 211         LOCK(cs);
 212         return (mapTx.count(hash) != 0);
 213     }
 214
 215     bool lookup(uint256 hash, CTransaction& result) const;
 216
 217     /** Estimate fee rate needed to get into the next nBlocks */
 218     CFeeRate estimateFee(int nBlocks) const;
 219
 220     /** Estimate priority needed to get into the next nBlocks */
 221     double estimatePriority(int nBlocks) const;
 222
 223     /** Write/Read estimates to disk */
 224     bool WriteFeeEstimates(CAutoFile& fileout) const;
 225     bool ReadFeeEstimates(CAutoFile& filein);
 226
 227     size_t DynamicMemoryUsage() const;
 228
 229     /** Return nCheckFrequency */
 230     uint32_t GetCheckFrequency() const {
 231         return nCheckFrequency;
 232     }
 233 };
 234
 235 /**
 236  * CCoinsView that brings transactions from a memorypool into view.
 237  * It does not check for spendings by memory pool transactions.
 238  */
 239 class CCoinsViewMemPool : public CCoinsViewBacked
 240 {
 241 protected:
 242     CTxMemPool &mempool;
 243
 244 public:
 245     CCoinsViewMemPool(CCoinsView *baseIn, CTxMemPool &mempoolIn);
 246     bool GetNullifier(const uint256 &txid, NullifierType type) const;
 247     bool GetCoins(const uint256 &txid, CCoins &coins) const;
 248     bool HaveCoins(const uint256 &txid) const;
 249 };
 250
 251 #endif // BITCOIN_TXMEMPOOL_H