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