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