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 <kernel/cs_main.h>
#include <kernel/mempool_entry.h>
#include <kernel/mempool_options.h>
#include <policy/packages.h>
#include <primitives/transaction.h>
#include <radix.h>
#include <sync.h>
#include <txconflicting.h>
#include <txorphanage.h>
#include <uint256radixkey.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 <memory>
#include <optional>
#include <set>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
 
class CChain;
class Chainstate;
class Config;
 
static const uint32_t MEMPOOL_HEIGHT = 0x7FFFFFFF;
 
// extracts a transaction id from CTxMemPoolEntry or CTransactionRef
struct mempoolentry_txid {
    typedef TxId result_type;
 
    result_type operator()(const CTxMemPoolEntryRef &entry) const {
        return entry->GetTx().GetId();
    }
 
    result_type operator()(const CTransactionRef &tx) const {
        return tx->GetId();
    }
};
 
struct MemPoolEntryRadixTreeAdapter {
    Uint256RadixKey getId(const CTxMemPoolEntry &entry) const {
        return entry.GetSharedTx()->GetId();
    }
};
 
// used by the entry_time index
struct CompareTxMemPoolEntryByEntryTime {
    bool operator()(const CTxMemPoolEntryRef &a,
                    const CTxMemPoolEntryRef &b) const {
        return a->GetTime() < b->GetTime();
    }
};
 
// used by the entry_id index
struct CompareTxMemPoolEntryByEntryId {
    bool operator()(const CTxMemPoolEntryRef &a,
                    const CTxMemPoolEntryRef &b) const {
        return a->GetEntryId() < b->GetEntryId();
    }
};
 
struct CompareTxMemPoolEntryByModifiedFeeRate {
    // Used in tests
    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();
    }
 
    bool operator()(const CTxMemPoolEntryRef &a,
                    const CTxMemPoolEntryRef &b) const {
        return operator()(*a, *b);
    }
};
 
// 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,
    AVALANCHE,
};
 
const std::string RemovalReasonToString(const MemPoolRemovalReason &r) noexcept;
 
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_load_tried GUARDED_BY(cs){false};
 
    uint64_t nextEntryId GUARDED_BY(cs) = 1;
 
    mutable Mutex cs_orphanage;
    std::unique_ptr<TxOrphanage> m_orphanage GUARDED_BY(cs_orphanage);
 
    mutable Mutex cs_conflicting;
    std::unique_ptr<TxConflicting> m_conflicting GUARDED_BY(cs_conflicting);
 
public:
    // public only for testing
    static const int ROLLING_FEE_HALFLIFE = 60 * 60 * 12;
 
    typedef boost::multi_index_container<
        CTxMemPoolEntryRef,
        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<CTxMemPoolEntryRef>,
                CompareTxMemPoolEntryByModifiedFeeRate>,
            // sorted by entry time
            boost::multi_index::ordered_non_unique<
                boost::multi_index::tag<entry_time>,
                boost::multi_index::identity<CTxMemPoolEntryRef>,
                CompareTxMemPoolEntryByEntryTime>,
            // sorted topologically (insertion order)
            boost::multi_index::ordered_unique<
                boost::multi_index::tag<entry_id>,
                boost::multi_index::identity<CTxMemPoolEntryRef>,
                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;
    typedef std::set<txiter, CompareIteratorByRevEntryId> setRevTopoEntries;
 
    RadixTree<CTxMemPoolEntry, MemPoolEntryRadixTreeAdapter> finalizedTxs;
 
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 CalculateAncestors(setEntries &setAncestors,
                            CTxMemPoolEntry::Parents &staged_ancestors) const
        EXCLUSIVE_LOCKS_REQUIRED(cs);
 
public:
    indirectmap<COutPoint, CTransactionRef> mapNextTx GUARDED_BY(cs);
    std::map<TxId, Amount> mapDeltas GUARDED_BY(cs);
 
    using Options = kernel::MemPoolOptions;
 
    const int64_t m_max_size_bytes;
    const std::chrono::seconds m_expiry;
    const CFeeRate m_min_relay_feerate;
    const CFeeRate m_dust_relay_feerate;
    const bool m_permit_bare_multisig;
    const std::optional<unsigned> m_max_datacarrier_bytes;
    const bool m_require_standard;
 
    CTxMemPool(const Options &opts);
    ~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.
    void addUnchecked(CTxMemPoolEntryRef entry)
        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 updateFeeForBlock() EXCLUSIVE_LOCKS_REQUIRED(cs);
    void removeForFinalizedBlock(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);
 
    CTransactionRef 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, MemPoolRemovalReason reason)
        EXCLUSIVE_LOCKS_REQUIRED(cs);
 
    bool CalculateMemPoolAncestors(const CTxMemPoolEntryRef &entry,
                                   setEntries &setAncestors,
                                   bool fSearchForParents = true) const
        EXCLUSIVE_LOCKS_REQUIRED(cs);
 
    void CalculateDescendants(txiter it, setEntries &setDescendants) const
        EXCLUSIVE_LOCKS_REQUIRED(cs);
 
    CFeeRate GetMinFee() const { return GetMinFee(m_max_size_bytes); }
    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)
        EXCLUSIVE_LOCKS_REQUIRED(cs, ::cs_main);
 
    bool GetLoadTried() const;
 
    void SetLoadTried(bool load_tried);
 
    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;
    }
 
    bool setAvalancheFinalized(const CTxMemPoolEntryRef &tx)
        EXCLUSIVE_LOCKS_REQUIRED(cs) {
        return finalizedTxs.insert(tx);
    }
 
    bool isAvalancheFinalized(const TxId &txid) const {
        LOCK(cs);
        return finalizedTxs.get(txid) != nullptr;
    }
 
    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;
    }
 
    template <typename Callable>
    auto withOrphanage(Callable &&func) const
        EXCLUSIVE_LOCKS_REQUIRED(!cs_orphanage) {
        LOCK(cs_orphanage);
        assert(m_orphanage);
        return func(*m_orphanage);
    }
 
    template <typename Callable>
    auto withConflicting(Callable &&func) const
        EXCLUSIVE_LOCKS_REQUIRED(!cs_conflicting) {
        LOCK(cs_conflicting);
        assert(m_conflicting);
        return func(*m_conflicting);
    }
 
private:
    void UpdateEntryForAncestors(txiter it, const setEntries *setAncestors)
        EXCLUSIVE_LOCKS_REQUIRED(cs);
    void UpdateParentsOf(bool add, txiter it) EXCLUSIVE_LOCKS_REQUIRED(cs);
    void UpdateForRemoveFromMempool(const setEntries &entriesToRemove)
        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;
 
    mutable std::unordered_set<COutPoint, SaltedOutpointHasher>
        m_non_base_coins;
 
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);
    std::unordered_set<COutPoint, SaltedOutpointHasher>
    GetNonBaseCoins() const {
        return m_non_base_coins;
    }
    void Reset();
};
 
#endif // BITCOIN_TXMEMPOOL_H