txmempool.h

Go to the documentation of this file.

// Copyright (c) 2009-2010 Satoshi Nakamoto
// Copyright (c) 2009-2016 The Bitcoin Core developers
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.
 
#ifndef BITCOIN_TXMEMPOOL_H
#define BITCOIN_TXMEMPOOL_H
 
#include <coins.h>
#include <consensus/amount.h>
#include <core_memusage.h>
#include <indirectmap.h>
#include <policy/packages.h>
#include <primitives/transaction.h>
#include <sync.h>
#include <util/hasher.h>
 
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/sequenced_index.hpp>
#include <boost/multi_index_container.hpp>
 
#include <atomic>
#include <map>
#include <optional>
#include <set>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
 
class CBlockIndex;
class CChain;
class Chainstate;
class Config;
 
extern RecursiveMutex cs_main;
 
static const uint32_t MEMPOOL_HEIGHT = 0x7FFFFFFF;
 
struct LockPoints {
    // Will be set to the blockchain height and median time past values that
    // would be necessary to satisfy all relative locktime constraints (BIP68)
    // of this tx given our view of block chain history
    int height{0};
    int64_t time{0};
    // As long as the current chain descends from the highest height block
    // containing one of the inputs used in the calculation, then the cached
    // values are still valid even after a reorg.
    CBlockIndex *maxInputBlock{nullptr};
};
 
bool TestLockPointValidity(const CChain &active_chain, const LockPoints &lp)
    EXCLUSIVE_LOCKS_REQUIRED(cs_main);
 
struct CompareIteratorById {
    // SFINAE for T where T is either a pointer type (e.g., a txiter) or a
    // reference_wrapper<T> (e.g. a wrapped CTxMemPoolEntry&)
    template <typename T>
    bool operator()(const std::reference_wrapper<T> &a,
                    const std::reference_wrapper<T> &b) const {
        return a.get().GetTx().GetId() < b.get().GetTx().GetId();
    }
    template <typename T> bool operator()(const T &a, const T &b) const {
        return a->GetTx().GetId() < b->GetTx().GetId();
    }
};
 
class CTxMemPoolEntry {
public:
    typedef std::reference_wrapper<const CTxMemPoolEntry> CTxMemPoolEntryRef;
    // two aliases, should the types ever diverge
    typedef std::set<CTxMemPoolEntryRef, CompareIteratorById> Parents;
    typedef std::set<CTxMemPoolEntryRef, CompareIteratorById> Children;
 
private:
    uint64_t entryId = 0;
 
    const CTransactionRef tx;
    mutable Parents m_parents;
    mutable Children m_children;
    const Amount nFee;
    const size_t nTxSize;
    const size_t nUsageSize;
    const int64_t nTime;
    const unsigned int entryHeight;
    const bool spendsCoinbase;
    const int64_t sigChecks;
    Amount feeDelta{Amount::zero()};
    LockPoints lockPoints;
 
    // NOTE:
    // The below members will stop being updated after Wellington activation,
    // and should be removed in the release after Wellington is checkpointed.
    //
    // Information about descendants of this transaction that are in the
    // mempool; if we remove this transaction we must remove all of these
    // descendants as well.
    uint64_t nCountWithDescendants{1};
    uint64_t nSizeWithDescendants;
    Amount nModFeesWithDescendants;
    int64_t nSigChecksWithDescendants;
 
    // Analogous statistics for ancestor transactions
    uint64_t nCountWithAncestors{1};
    uint64_t nSizeWithAncestors;
    Amount nModFeesWithAncestors;
    int64_t nSigChecksWithAncestors;
 
public:
    CTxMemPoolEntry(const CTransactionRef &_tx, const Amount fee, int64_t time,
                    unsigned int entry_height, bool spends_coinbase,
                    int64_t sigchecks, LockPoints lp);
 
    uint64_t GetEntryId() const { return entryId; }
    void SetEntryId(uint64_t eid) { entryId = eid; }
 
    const CTransaction &GetTx() const { return *this->tx; }
    CTransactionRef GetSharedTx() const { return this->tx; }
    Amount GetFee() const { return nFee; }
    size_t GetTxSize() const { return nTxSize; }
    size_t GetTxVirtualSize() const;
 
    std::chrono::seconds GetTime() const { return std::chrono::seconds{nTime}; }
    unsigned int GetHeight() const { return entryHeight; }
    int64_t GetSigChecks() const { return sigChecks; }
    Amount GetModifiedFee() const { return nFee + feeDelta; }
    CFeeRate GetModifiedFeeRate() const {
        return CFeeRate(GetModifiedFee(), GetTxVirtualSize());
    }
    size_t DynamicMemoryUsage() const { return nUsageSize; }
    const LockPoints &GetLockPoints() const { return lockPoints; }
 
    // Adjusts the descendant state. -- To be removed after Wellington
    void UpdateDescendantState(int64_t modifySize, Amount modifyFee,
                               int64_t modifyCount, int64_t modifySigChecks);
    // Adjusts the ancestor state -- To be removed after Wellington
    void UpdateAncestorState(int64_t modifySize, Amount modifyFee,
                             int64_t modifyCount, int64_t modifySigChecks);
 
    // Updates the fee delta used for mining priority score, and the
    // modified fees with descendants.
    void UpdateFeeDelta(Amount feeDelta);
    // Update the LockPoints after a reorg
    void UpdateLockPoints(const LockPoints &lp);
 
    uint64_t GetCountWithDescendants() const { return nCountWithDescendants; }
    uint64_t GetSizeWithDescendants() const { return nSizeWithDescendants; }
    uint64_t GetVirtualSizeWithDescendants() const;
    Amount GetModFeesWithDescendants() const { return nModFeesWithDescendants; }
    int64_t GetSigChecksWithDescendants() const {
        return nSigChecksWithDescendants;
    }
 
    bool GetSpendsCoinbase() const { return spendsCoinbase; }
 
    uint64_t GetCountWithAncestors() const { return nCountWithAncestors; }
    uint64_t GetSizeWithAncestors() const { return nSizeWithAncestors; }
    uint64_t GetVirtualSizeWithAncestors() const;
    Amount GetModFeesWithAncestors() const { return nModFeesWithAncestors; }
    int64_t GetSigChecksWithAncestors() const {
        return nSigChecksWithAncestors;
    }
 
    const Parents &GetMemPoolParentsConst() const { return m_parents; }
    const Children &GetMemPoolChildrenConst() const { return m_children; }
    Parents &GetMemPoolParents() const { return m_parents; }
    Children &GetMemPoolChildren() const { return m_children; }
};
 
// extracts a transaction id from CTxMemPoolEntry or CTransactionRef
struct mempoolentry_txid {
    typedef TxId result_type;
    result_type operator()(const CTxMemPoolEntry &entry) const {
        return entry.GetTx().GetId();
    }
 
    result_type operator()(const CTransactionRef &tx) const {
        return tx->GetId();
    }
};
 
// used by the entry_time index
struct CompareTxMemPoolEntryByEntryTime {
    bool operator()(const CTxMemPoolEntry &a, const CTxMemPoolEntry &b) const {
        return a.GetTime() < b.GetTime();
    }
};
 
// used by the entry_id index
struct CompareTxMemPoolEntryByEntryId {
    bool operator()(const CTxMemPoolEntry &a, const CTxMemPoolEntry &b) const {
        return a.GetEntryId() < b.GetEntryId();
    }
};
 
struct CompareTxMemPoolEntryByModifiedFeeRate {
    bool operator()(const CTxMemPoolEntry &a, const CTxMemPoolEntry &b) const {
        const CFeeRate frA = a.GetModifiedFeeRate();
        const CFeeRate frB = b.GetModifiedFeeRate();
 
        // Sort by modified fee rate first
        if (frA != frB) {
            return frA > frB;
        }
 
        // Ties are broken by whichever is topologically earlier
        // (this helps mining code avoid some backtracking).
        if (a.GetEntryId() != b.GetEntryId()) {
            return a.GetEntryId() < b.GetEntryId();
        }
 
        // If nothing else, sort by txid (this should never happen as entryID is
        // expected to be unique).
        return a.GetSharedTx()->GetId() < b.GetSharedTx()->GetId();
    }
};
 
// Multi_index tag names
struct entry_time {};
struct modified_feerate {};
struct entry_id {};
 
struct TxMempoolInfo {
    CTransactionRef tx;
 
    std::chrono::seconds m_time;
 
    Amount fee;
 
    size_t vsize;
 
    Amount nFeeDelta;
};
 
enum class MemPoolRemovalReason {
    EXPIRY,
    SIZELIMIT,
    REORG,
    BLOCK,
    CONFLICT,
    REPLACED
};
 
class CTxMemPool {
private:
    const int m_check_ratio;
    std::atomic<uint32_t> nTransactionsUpdated{0};
 
    uint64_t totalTxSize GUARDED_BY(cs);
    Amount m_total_fee GUARDED_BY(cs);
    uint64_t cachedInnerUsage GUARDED_BY(cs);
 
    mutable int64_t lastRollingFeeUpdate GUARDED_BY(cs);
    mutable bool blockSinceLastRollingFeeBump GUARDED_BY(cs);
    mutable double rollingMinimumFeeRate GUARDED_BY(cs);
 
    // In-memory counter for external mempool tracking purposes.
    // This number is incremented once every time a transaction
    // is added or removed from the mempool for any reason.
    mutable uint64_t m_sequence_number GUARDED_BY(cs){1};
 
    void trackPackageRemoved(const CFeeRate &rate) EXCLUSIVE_LOCKS_REQUIRED(cs);
 
    bool m_is_loaded GUARDED_BY(cs){false};
 
    uint64_t nextEntryId GUARDED_BY(cs) = 1;
 
public:
    // public only for testing
    static const int ROLLING_FEE_HALFLIFE = 60 * 60 * 12;
 
    typedef boost::multi_index_container<
        CTxMemPoolEntry, boost::multi_index::indexed_by<
                             // indexed by txid
                             boost::multi_index::hashed_unique<
                                 mempoolentry_txid, SaltedTxIdHasher>,
                             // sorted by fee rate
                             boost::multi_index::ordered_non_unique<
                                 boost::multi_index::tag<modified_feerate>,
                                 boost::multi_index::identity<CTxMemPoolEntry>,
                                 CompareTxMemPoolEntryByModifiedFeeRate>,
                             // sorted by entry time
                             boost::multi_index::ordered_non_unique<
                                 boost::multi_index::tag<entry_time>,
                                 boost::multi_index::identity<CTxMemPoolEntry>,
                                 CompareTxMemPoolEntryByEntryTime>,
                             // sorted topologically (insertion order)
                             boost::multi_index::ordered_unique<
                                 boost::multi_index::tag<entry_id>,
                                 boost::multi_index::identity<CTxMemPoolEntry>,
                                 CompareTxMemPoolEntryByEntryId>>>
        indexed_transaction_set;
 
    mutable RecursiveMutex cs;
    indexed_transaction_set mapTx GUARDED_BY(cs);
 
    using txiter = indexed_transaction_set::nth_index<0>::type::const_iterator;
    typedef std::set<txiter, CompareIteratorById> setEntries;
 
    uint64_t CalculateDescendantMaximum(txiter entry) const
        EXCLUSIVE_LOCKS_REQUIRED(cs);
 
private:
    void UpdateParent(txiter entry, txiter parent, bool add)
        EXCLUSIVE_LOCKS_REQUIRED(cs);
    void UpdateChild(txiter entry, txiter child, bool add)
        EXCLUSIVE_LOCKS_REQUIRED(cs);
 
    std::set<TxId> m_unbroadcast_txids GUARDED_BY(cs);
 
    bool CalculateAncestorsAndCheckLimits(
        size_t entry_size, size_t entry_count, setEntries &setAncestors,
        CTxMemPoolEntry::Parents &staged_ancestors, uint64_t limitAncestorCount,
        uint64_t limitAncestorSize, uint64_t limitDescendantCount,
        uint64_t limitDescendantSize, std::string &errString) const
        EXCLUSIVE_LOCKS_REQUIRED(cs);
 
public:
    indirectmap<COutPoint, const CTransaction *> mapNextTx GUARDED_BY(cs);
    std::map<TxId, Amount> mapDeltas GUARDED_BY(cs);
 
    std::atomic<bool> wellingtonLatched{false};
 
    CTxMemPool(int check_ratio = 0);
    ~CTxMemPool();
 
    void check(const CCoinsViewCache &active_coins_tip,
               int64_t spendheight) const EXCLUSIVE_LOCKS_REQUIRED(::cs_main);
 
    // addUnchecked must update state for all parents of a given transaction,
    // updating child links as necessary.
    // Pre-wellington: automatically calculates setAncestors, calls
    // addUnchecked(entry, setAncestors)
    // Post-wellington: identical to just calling addUnchecked(entry, {})
    // These 2 overloads should be collapsed down into 1 post-wellington (just a
    // single-argument version).
    void addUnchecked(const CTxMemPoolEntry &entry)
        EXCLUSIVE_LOCKS_REQUIRED(cs, cs_main);
    void
    addUnchecked(const CTxMemPoolEntry &entry,
                 const setEntries &setAncestors /* only used pre-wellington */)
        EXCLUSIVE_LOCKS_REQUIRED(cs, cs_main);
 
    void removeRecursive(const CTransaction &tx, MemPoolRemovalReason reason)
        EXCLUSIVE_LOCKS_REQUIRED(cs);
    void removeConflicts(const CTransaction &tx) EXCLUSIVE_LOCKS_REQUIRED(cs);
    void removeForBlock(const std::vector<CTransactionRef> &vtx)
        EXCLUSIVE_LOCKS_REQUIRED(cs);
 
    void clear();
    // lock free
    void _clear() EXCLUSIVE_LOCKS_REQUIRED(cs);
    bool CompareTopologically(const TxId &txida, const TxId &txidb) const;
    void getAllTxIds(std::vector<TxId> &vtxid) const;
    bool isSpent(const COutPoint &outpoint) const;
    unsigned int GetTransactionsUpdated() const;
    void AddTransactionsUpdated(unsigned int n);
    bool HasNoInputsOf(const CTransaction &tx) const
        EXCLUSIVE_LOCKS_REQUIRED(cs);
 
    void PrioritiseTransaction(const TxId &txid, const Amount nFeeDelta);
    void ApplyDelta(const TxId &txid, Amount &nFeeDelta) const
        EXCLUSIVE_LOCKS_REQUIRED(cs);
    void ClearPrioritisation(const TxId &txid) EXCLUSIVE_LOCKS_REQUIRED(cs);
 
    const CTransaction *GetConflictTx(const COutPoint &prevout) const
        EXCLUSIVE_LOCKS_REQUIRED(cs);
 
    std::optional<txiter> GetIter(const TxId &txid) const
        EXCLUSIVE_LOCKS_REQUIRED(cs);
 
    setEntries GetIterSet(const std::set<TxId> &txids) const
        EXCLUSIVE_LOCKS_REQUIRED(cs);
 
    void RemoveStaged(const setEntries &stage, bool updateDescendants,
                      MemPoolRemovalReason reason) EXCLUSIVE_LOCKS_REQUIRED(cs);
 
    bool CalculateMemPoolAncestors(
        const CTxMemPoolEntry &entry, setEntries &setAncestors,
        uint64_t limitAncestorCount, uint64_t limitAncestorSize,
        uint64_t limitDescendantCount, uint64_t limitDescendantSize,
        std::string &errString, bool fSearchForParents = true) const
        EXCLUSIVE_LOCKS_REQUIRED(cs);
 
    bool CheckPackageLimits(const Package &package, uint64_t limitAncestorCount,
                            uint64_t limitAncestorSize,
                            uint64_t limitDescendantCount,
                            uint64_t limitDescendantSize,
                            std::string &errString) const
        EXCLUSIVE_LOCKS_REQUIRED(cs);
 
    void CalculateDescendants(txiter it, setEntries &setDescendants) const
        EXCLUSIVE_LOCKS_REQUIRED(cs);
 
    CFeeRate GetMinFee(size_t sizelimit) const;
 
    void TrimToSize(size_t sizelimit,
                    std::vector<COutPoint> *pvNoSpendsRemaining = nullptr)
        EXCLUSIVE_LOCKS_REQUIRED(cs);
 
    int Expire(std::chrono::seconds time) EXCLUSIVE_LOCKS_REQUIRED(cs);
 
    void LimitSize(CCoinsViewCache &coins_cache, size_t limit,
                   std::chrono::seconds age)
        EXCLUSIVE_LOCKS_REQUIRED(cs, ::cs_main);
 
    void GetTransactionAncestry(const TxId &txid, size_t &ancestors,
                                size_t &descendants,
                                size_t *ancestorsize = nullptr,
                                Amount *ancestorfees = nullptr) const;
 
    bool IsLoaded() const;
 
    void SetIsLoaded(bool loaded);
 
    unsigned long size() const {
        LOCK(cs);
        return mapTx.size();
    }
 
    uint64_t GetTotalTxSize() const EXCLUSIVE_LOCKS_REQUIRED(cs) {
        AssertLockHeld(cs);
        return totalTxSize;
    }
 
    Amount GetTotalFee() const EXCLUSIVE_LOCKS_REQUIRED(cs) {
        AssertLockHeld(cs);
        return m_total_fee;
    }
 
    bool exists(const TxId &txid) const {
        LOCK(cs);
        return mapTx.count(txid) != 0;
    }
 
    CTransactionRef get(const TxId &txid) const;
    TxMempoolInfo info(const TxId &txid) const;
    std::vector<TxMempoolInfo> infoAll() const;
 
    CFeeRate estimateFee() const;
 
    size_t DynamicMemoryUsage() const;
 
    void AddUnbroadcastTx(const TxId &txid) {
        LOCK(cs);
        // Sanity check the transaction is in the mempool & insert into
        // unbroadcast set.
        if (exists(txid)) {
            m_unbroadcast_txids.insert(txid);
        }
    }
 
    void RemoveUnbroadcastTx(const TxId &txid, const bool unchecked = false);
 
    std::set<TxId> GetUnbroadcastTxs() const {
        LOCK(cs);
        return m_unbroadcast_txids;
    }
 
    bool IsUnbroadcastTx(const TxId &txid) const EXCLUSIVE_LOCKS_REQUIRED(cs) {
        AssertLockHeld(cs);
        return (m_unbroadcast_txids.count(txid) != 0);
    }
 
    uint64_t GetAndIncrementSequence() const EXCLUSIVE_LOCKS_REQUIRED(cs) {
        return m_sequence_number++;
    }
 
    uint64_t GetSequence() const EXCLUSIVE_LOCKS_REQUIRED(cs) {
        return m_sequence_number;
    }
 
private:
    void UpdateEntryForAncestors(txiter it, const setEntries *setAncestors)
        EXCLUSIVE_LOCKS_REQUIRED(cs);
    void UpdateParentsOf(
        bool add, txiter it,
        const setEntries *setAncestors = nullptr /* only used pre-wellington */)
        EXCLUSIVE_LOCKS_REQUIRED(cs);
    void UpdateForRemoveFromMempool(const setEntries &entriesToRemove,
                                    bool updateDescendants)
        EXCLUSIVE_LOCKS_REQUIRED(cs);
    void UpdateChildrenForRemoval(txiter entry) EXCLUSIVE_LOCKS_REQUIRED(cs);
 
    void removeUnchecked(txiter entry, MemPoolRemovalReason reason)
        EXCLUSIVE_LOCKS_REQUIRED(cs);
};
 
class CCoinsViewMemPool : public CCoinsViewBacked {
    std::unordered_map<COutPoint, Coin, SaltedOutpointHasher> m_temp_added;
 
protected:
    const CTxMemPool &mempool;
 
public:
    CCoinsViewMemPool(CCoinsView *baseIn, const CTxMemPool &mempoolIn);
    bool GetCoin(const COutPoint &outpoint, Coin &coin) const override;
    void PackageAddTransaction(const CTransactionRef &tx);
};
 
// multi_index tag names
struct txid_index {};
struct insertion_order {};
 
class DisconnectedBlockTransactions {
private:
    typedef boost::multi_index_container<
        CTransactionRef, boost::multi_index::indexed_by<
                             // hashed by txid
                             boost::multi_index::hashed_unique<
                                 boost::multi_index::tag<txid_index>,
                                 mempoolentry_txid, SaltedTxIdHasher>,
                             // sorted by order in the blockchain
                             boost::multi_index::sequenced<
                                 boost::multi_index::tag<insertion_order>>>>
        indexed_disconnected_transactions;
 
    indexed_disconnected_transactions queuedTx;
    uint64_t cachedInnerUsage = 0;
 
    struct TxInfo {
        const std::chrono::seconds time;
        const Amount feeDelta;
        const unsigned height;
        TxInfo(const std::chrono::seconds &time_, Amount feeDelta_,
               unsigned height_) noexcept
            : time(time_), feeDelta(feeDelta_), height(height_) {}
    };
 
    using TxInfoMap = std::unordered_map<TxId, TxInfo, SaltedTxIdHasher>;
    TxInfoMap txInfo;
 
    void addTransaction(const CTransactionRef &tx) {
        queuedTx.insert(tx);
        cachedInnerUsage += RecursiveDynamicUsage(tx);
    }
 
    const TxInfo *getTxInfo(const CTransactionRef &tx) const;
 
public:
    // It's almost certainly a logic bug if we don't clear out queuedTx before
    // destruction, as we add to it while disconnecting blocks, and then we
    // need to re-process remaining transactions to ensure mempool consistency.
    // For now, assert() that we've emptied out this object on destruction.
    // This assert() can always be removed if the reorg-processing code were
    // to be refactored such that this assumption is no longer true (for
    // instance if there was some other way we cleaned up the mempool after a
    // reorg, besides draining this object).
    ~DisconnectedBlockTransactions() { assert(queuedTx.empty()); }
 
    // Estimate the overhead of queuedTx to be 6 pointers + an allocation, as
    // no exact formula for boost::multi_index_contained is implemented.
    size_t DynamicMemoryUsage() const {
        return memusage::MallocUsage(sizeof(CTransactionRef) +
                                     6 * sizeof(void *)) *
                   queuedTx.size() +
               memusage::DynamicUsage(txInfo) + cachedInnerUsage;
    }
 
    const indexed_disconnected_transactions &GetQueuedTx() const {
        return queuedTx;
    }
 
    // Import mempool entries in topological order into queuedTx and clear the
    // mempool. Caller should call updateMempoolForReorg to reprocess these
    // transactions
    void importMempool(CTxMemPool &pool) EXCLUSIVE_LOCKS_REQUIRED(pool.cs);
 
    // Add entries for a block while reconstructing the topological ordering so
    // they can be added back to the mempool simply.
    void addForBlock(const std::vector<CTransactionRef> &vtx, CTxMemPool &pool)
        EXCLUSIVE_LOCKS_REQUIRED(pool.cs);
 
    // Remove entries based on txid_index, and update memory usage.
    void removeForBlock(const std::vector<CTransactionRef> &vtx) {
        // Short-circuit in the common case of a block being added to the tip
        if (queuedTx.empty()) {
            return;
        }
        for (auto const &tx : vtx) {
            auto it = queuedTx.find(tx->GetId());
            if (it != queuedTx.end()) {
                cachedInnerUsage -= RecursiveDynamicUsage(*it);
                queuedTx.erase(it);
                txInfo.erase(tx->GetId());
            }
        }
    }
 
    // Remove an entry by insertion_order index, and update memory usage.
    void removeEntry(indexed_disconnected_transactions::index<
                     insertion_order>::type::iterator entry) {
        cachedInnerUsage -= RecursiveDynamicUsage(*entry);
        txInfo.erase((*entry)->GetId());
        queuedTx.get<insertion_order>().erase(entry);
    }
 
    bool isEmpty() const { return queuedTx.empty(); }
 
    void clear() {
        cachedInnerUsage = 0;
        queuedTx.clear();
        txInfo.clear();
    }
 
    void updateMempoolForReorg(const Config &config,
                               Chainstate &active_chainstate,
                               bool fAddToMempool, CTxMemPool &pool)
        EXCLUSIVE_LOCKS_REQUIRED(cs_main, pool.cs);
};
 
#endif // BITCOIN_TXMEMPOOL_H