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     std::map<uint256, const CTransaction*> mapSproutNullifiers;
 137     std::map<uint256, const CTransaction*> mapSaplingNullifiers;
 138
 139     void checkNullifiers(ShieldedType type) const;
 140
 141 public:
 142     typedef boost::multi_index_container<
 143         CTxMemPoolEntry,
 144         boost::multi_index::indexed_by<
 145             // sorted by txid
 146             boost::multi_index::ordered_unique<mempoolentry_txid>,
 147             // sorted by fee rate
 148             boost::multi_index::ordered_non_unique<
 149                 boost::multi_index::identity<CTxMemPoolEntry>,
 150                 CompareTxMemPoolEntryByFee
 151             >
 152         >
 153     > indexed_transaction_set;
 154
 155     mutable CCriticalSection cs;
 156     indexed_transaction_set mapTx;
 157
 158 private:
 159     typedef std::map<CMempoolAddressDeltaKey, CMempoolAddressDelta, CMempoolAddressDeltaKeyCompare> addressDeltaMap;
 160     addressDeltaMap mapAddress;
 161
 162     typedef std::map<uint256, std::vector<CMempoolAddressDeltaKey> > addressDeltaMapInserted;
 163     addressDeltaMapInserted mapAddressInserted;
 164
 165     typedef std::map<CSpentIndexKey, CSpentIndexValue, CSpentIndexKeyCompare> mapSpentIndex;
 166     mapSpentIndex mapSpent;
 167
 168     typedef std::map<uint256, std::vector<CSpentIndexKey> > mapSpentIndexInserted;
 169     mapSpentIndexInserted mapSpentInserted;
 170
 171 public:
 172     std::map<COutPoint, CInPoint> mapNextTx;
 173     std::map<uint256, std::pair<double, CAmount> > mapDeltas;
 174
 175     CTxMemPool(const CFeeRate& _minRelayFee);
 176     ~CTxMemPool();
 177
 178     /**
 179      * If sanity-checking is turned on, check makes sure the pool is
 180      * consistent (does not contain two transactions that spend the same inputs,
 181      * all inputs are in the mapNextTx array). If sanity-checking is turned off,
 182      * check does nothing.
 183      */
 184     void check(const CCoinsViewCache *pcoins) const;
 185     void setSanityCheck(double dFrequency = 1.0) { nCheckFrequency = static_cast<uint32_t>(dFrequency * 4294967295.0); }
 186
 187     bool addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry, bool fCurrentEstimate = true);
 188     void addAddressIndex(const CTxMemPoolEntry &entry, const CCoinsViewCache &view);
 189     bool getAddressIndex(std::vector<std::pair<uint160, int> > &addresses,
 190                          std::vector<std::pair<CMempoolAddressDeltaKey, CMempoolAddressDelta> > &results);
 191     bool removeAddressIndex(const uint256 txhash);
 192
 193     void addSpentIndex(const CTxMemPoolEntry &entry, const CCoinsViewCache &view);
 194     bool getSpentIndex(CSpentIndexKey &key, CSpentIndexValue &value);
 195     bool removeSpentIndex(const uint256 txhash);
 196     void remove(const CTransaction &tx, std::list<CTransaction>& removed, bool fRecursive = false);
 197     void removeWithAnchor(const uint256 &invalidRoot, ShieldedType type);
 198     void removeForReorg(const CCoinsViewCache *pcoins, unsigned int nMemPoolHeight, int flags);
 199     void removeConflicts(const CTransaction &tx, std::list<CTransaction>& removed);
 200     void removeExpired(unsigned int nBlockHeight);
 201     void removeForBlock(const std::vector<CTransaction>& vtx, unsigned int nBlockHeight,
 202                         std::list<CTransaction>& conflicts, bool fCurrentEstimate = true);
 203     void removeWithoutBranchId(uint32_t nMemPoolBranchId);
 204     void clear();
 205     void queryHashes(std::vector<uint256>& vtxid);
 206     void pruneSpent(const uint256& hash, CCoins &coins);
 207     unsigned int GetTransactionsUpdated() const;
 208     void AddTransactionsUpdated(unsigned int n);
 209     /**
 210      * Check that none of this transactions inputs are in the mempool, and thus
 211      * the tx is not dependent on other mempool transactions to be included in a block.
 212      */
 213     bool HasNoInputsOf(const CTransaction& tx) const;
 214
 215     /** Affect CreateNewBlock prioritisation of transactions */
 216     void PrioritiseTransaction(const uint256 hash, const std::string strHash, double dPriorityDelta, const CAmount& nFeeDelta);
 217     void ApplyDeltas(const uint256 hash, double &dPriorityDelta, CAmount &nFeeDelta);
 218     void ClearPrioritisation(const uint256 hash);
 219
 220     bool nullifierExists(const uint256& nullifier, ShieldedType type) const;
 221
 222     unsigned long size()
 223     {
 224         LOCK(cs);
 225         return mapTx.size();
 226     }
 227
 228     uint64_t GetTotalTxSize()
 229     {
 230         LOCK(cs);
 231         return totalTxSize;
 232     }
 233
 234     bool exists(uint256 hash) const
 235     {
 236         LOCK(cs);
 237         return (mapTx.count(hash) != 0);
 238     }
 239
 240     bool lookup(uint256 hash, CTransaction& result) const;
 241
 242     /** Estimate fee rate needed to get into the next nBlocks */
 243     CFeeRate estimateFee(int nBlocks) const;
 244
 245     /** Estimate priority needed to get into the next nBlocks */
 246     double estimatePriority(int nBlocks) const;
 247
 248     /** Write/Read estimates to disk */
 249     bool WriteFeeEstimates(CAutoFile& fileout) const;
 250     bool ReadFeeEstimates(CAutoFile& filein);
 251
 252     size_t DynamicMemoryUsage() const;
 253
 254     /** Return nCheckFrequency */
 255     uint32_t GetCheckFrequency() const {
 256         return nCheckFrequency;
 257     }
 258 };
 259
 260 /**
 261  * CCoinsView that brings transactions from a memorypool into view.
 262  * It does not check for spendings by memory pool transactions.
 263  */
 264 class CCoinsViewMemPool : public CCoinsViewBacked
 265 {
 266 protected:
 267     CTxMemPool &mempool;
 268
 269 public:
 270     CCoinsViewMemPool(CCoinsView *baseIn, CTxMemPool &mempoolIn);
 271     bool GetNullifier(const uint256 &txid, ShieldedType type) const;
 272     bool GetCoins(const uint256 &txid, CCoins &coins) const;
 273     bool HaveCoins(const uint256 &txid) const;
 274 };
 275
 276 #endif // BITCOIN_TXMEMPOOL_H