Inside Bitcoin

251     *    to lock just `mempool.cs` without `cs_main`.
252     *
253     * To provide these guarantees, it is necessary to lock both `cs_main` and
254     * `mempool.cs` whenever adding transactions to the mempool and whenever
255     * changing the chain tip. It's necessary to keep both mutexes locked until
256     * the mempool is consistent with the new chain tip and fully populated.
257     */
258    mutable RecursiveMutex cs ACQUIRED_AFTER(::cs_main);
259    std::unique_ptr<TxGraph> m_txgraph GUARDED_BY(cs);
260    mutable std::unique_ptr<TxGraph::BlockBuilder> m_builder GUARDED_BY(cs);
261    indexed_transaction_set mapTx GUARDED_BY(cs);
262
263    using txiter = indexed_transaction_set::nth_index<0>::type::const_iterator;
264    std::vector<std::pair<Wtxid, txiter>> txns_randomized GUARDED_BY(cs); //!< All transactions in mapTx with their wtxids, in arbitrary order
265
266    typedef std::set<txiter, CompareIteratorByHash> setEntries;
267
268    using Limits = kernel::MemPoolLimits;
269
270    std::tuple<size_t, size_t, CAmount> CalculateAncestorData(const CTxMemPoolEntry& entry) const EXCLUSIVE_LOCKS_REQUIRED(cs);
271    std::tuple<size_t, size_t, CAmount> CalculateDescendantData(const CTxMemPoolEntry& entry) const EXCLUSIVE_LOCKS_REQUIRED(cs);
272    int64_t GetDescendantCount(txiter it) const { LOCK(cs); return m_txgraph->GetDescendants(*it, TxGraph::Level::MAIN).size(); }
273    int64_t GetDescendantCount(const CTxMemPoolEntry &e) const { LOCK(cs); return m_txgraph->GetDescendants(e, TxGraph::Level::MAIN).size(); }
274    int64_t GetAncestorCount(const CTxMemPoolEntry &e) const { LOCK(cs); return m_txgraph->GetAncestors(e, TxGraph::Level::MAIN).size(); }
275    std::vector<CTxMemPoolEntry::CTxMemPoolEntryRef> GetChildren(const CTxMemPoolEntry &entry) const;
276    std::vector<CTxMemPoolEntry::CTxMemPoolEntryRef> GetParents(const CTxMemPoolEntry &entry) const;
277
278private:
279    std::vector<indexed_transaction_set::const_iterator> GetSortedScoreWithTopology() const EXCLUSIVE_LOCKS_REQUIRED(cs);
280
281    /**
282     * Track locally submitted transactions to periodically retry initial broadcast.
283     */
284    std::set<Txid> m_unbroadcast_txids GUARDED_BY(cs);
285
286    static TxMempoolInfo GetInfo(CTxMemPool::indexed_transaction_set::const_iterator it)
287    {
288        return TxMempoolInfo{it->GetSharedTx(), it->GetTime(), it->GetFee(), it->GetTxSize(), it->GetModifiedFee() - it->GetFee()};
289    }
290
291    // Helper to remove all transactions that conflict with a given
292    // transaction (used for transactions appearing in a block).
293    void removeConflicts(const CTransaction& tx) EXCLUSIVE_LOCKS_REQUIRED(cs);
294
295public:
296    indirectmap<COutPoint, txiter> mapNextTx GUARDED_BY(cs);
297    std::map<Txid, CAmount> mapDeltas GUARDED_BY(cs);
298
299    using Options = kernel::MemPoolOptions;
300
301    const Options m_opts;
302
303    /** Create a new CTxMemPool.
304     * Sanity checks will be off by default for performance, because otherwise
305     * accepting transactions becomes O(N^2) where N is the number of transactions
306     * in the pool.
307     */
308    explicit CTxMemPool(Options opts, bilingual_str& error);
309
310    /**
311     * If sanity-checking is turned on, check makes sure the pool is
312     * consistent (does not contain two transactions that spend the same inputs,
313     * all inputs are in the mapNextTx array). If sanity-checking is turned off,
314     * check does nothing.
315     */
316    void check(const CCoinsViewCache& active_coins_tip, int64_t spendheight) const EXCLUSIVE_LOCKS_REQUIRED(::cs_main);
317
318    /**
319     * Remove a transaction from the mempool along with any descendants.
320     * If the transaction is not already in the mempool, find any descendants
321     * and remove them.
322     */
323    void removeRecursive(const CTransaction& tx, MemPoolRemovalReason reason) EXCLUSIVE_LOCKS_REQUIRED(cs);
324    /** After reorg, filter the entries that would no longer be valid in the next block, and update
325     * the entries' cached LockPoints if needed.  The mempool does not have any knowledge of
326     * consensus rules. It just applies the callable function and removes the ones for which it
327     * returns true.
328     * @param[in]   filter_final_and_mature   Predicate that checks the relevant validation rules
329     *                                        and updates an entry's LockPoints.
330     * */
331    void removeForReorg(CChain& chain, std::function<bool(txiter)> filter_final_and_mature) EXCLUSIVE_LOCKS_REQUIRED(cs, cs_main);
332    std::vector<RemovedMempoolTransactionInfo> removeForBlock(const std::vector<CTransactionRef>& vtx) EXCLUSIVE_LOCKS_REQUIRED(cs);
333
334    /** Look up wtxids in the mempool and (partially) sort by mining score.
335     *
336     * The @p n_to_sort best entries are removed from @p wtxids and their
337     * corresponding txiter entries are returned. In addition wtxids
338     * that are duplicates or were not found in the mempool are silently
339     * dropped from @p wtxids. The returned vector is ordered from best
340     * to worst (by CompareMainOrder). Entries remaining in @p wtxids
341     * are in unspecified order.
342     *
343     * Note that the returned `txiter` values may become invalidated once
344     * mempool.cs is released.
345     */
346    std::vector<txiter> ExtractBestByMiningScoreWithTopology(std::vector<Wtxid>& wtxids, size_t n_to_sort) const EXCLUSIVE_LOCKS_REQUIRED(cs);
347    bool isSpent(const COutPoint& outpoint) const;
348    unsigned int GetTransactionsUpdated() const;
349    void AddTransactionsUpdated(unsigned int n);
350    /**
351     * Check that none of this transactions inputs are in the mempool, and thus
352     * the tx is not dependent on other mempool transactions to be included in a block.
353     */
354    bool HasNoInputsOf(const CTransaction& tx) const EXCLUSIVE_LOCKS_REQUIRED(cs);
355
356    /** Affect CreateNewBlock prioritisation of transactions */
357    void PrioritiseTransaction(const Txid& hash, const CAmount& nFeeDelta);
358    void ApplyDelta(const Txid& hash, CAmount &nFeeDelta) const EXCLUSIVE_LOCKS_REQUIRED(cs);
359    void ClearPrioritisation(const Txid& hash) EXCLUSIVE_LOCKS_REQUIRED(cs);
360
361    struct delta_info {
362        /** Whether this transaction is in the mempool. */
363        const bool in_mempool;
364        /** The fee delta added using PrioritiseTransaction(). */
365        const CAmount delta;
366        /** The modified fee (base fee + delta) of this entry. Only present if in_mempool=true. */
367        std::optional<CAmount> modified_fee;
368        /** The prioritised transaction's txid. */
369        const Txid txid;
370    };
371    /** Return a vector of all entries in mapDeltas with their corresponding delta_info. */
372    std::vector<delta_info> GetPrioritisedTransactions() const EXCLUSIVE_LOCKS_REQUIRED(!cs);
373
374    /** Get the transaction in the pool that spends the same prevout */
375    const CTransaction* GetConflictTx(const COutPoint& prevout) const EXCLUSIVE_LOCKS_REQUIRED(cs);
376
377    /** Returns an iterator to the given hash, if found */
378    std::optional<txiter> GetIter(const Txid& txid) const EXCLUSIVE_LOCKS_REQUIRED(cs);
379    std::optional<txiter> GetIter(const Wtxid& wtxid) const EXCLUSIVE_LOCKS_REQUIRED(cs);
380
381    /** Translate a set of hashes into a set of pool iterators to avoid repeated lookups.
382     * Does not require that all of the hashes correspond to actual transactions in the mempool,
383     * only returns the ones that exist. */
384    setEntries GetIterSet(const std::set<Txid>& hashes) const EXCLUSIVE_LOCKS_REQUIRED(cs);
385
386    /** Translate a list of hashes into a list of mempool iterators to avoid repeated lookups.
387     * The nth element in txids becomes the nth element in the returned vector. If any of the txids
388     * don't actually exist in the mempool, returns an empty vector. */
389    std::vector<txiter> GetIterVec(const std::vector<Txid>& txids) const EXCLUSIVE_LOCKS_REQUIRED(cs);
390
391    /** UpdateTransactionsFromBlock is called when adding transactions from a
392     * disconnected block back to the mempool, new mempool entries may have
393     * children in the mempool (which is generally not the case when otherwise
394     * adding transactions).
395     *  @post updated descendant state for descendants of each transaction in
396     *        vHashesToUpdate (excluding any child transactions present in
397     *        vHashesToUpdate, which are already accounted for). Updated state
398     *        includes add fee/size information for such descendants to the
399     *        parent and updated ancestor state to include the parent.
400     *
401     * @param[in] vHashesToUpdate          The set of txids from the
402     *     disconnected block that have been accepted back into the mempool.
403     */
404    void UpdateTransactionsFromBlock(const std::vector<Txid>& vHashesToUpdate) EXCLUSIVE_LOCKS_REQUIRED(cs, cs_main);
405
406    std::vector<FeePerWeight> GetFeerateDiagram() const EXCLUSIVE_LOCKS_REQUIRED(cs);
407    FeePerWeight GetMainChunkFeerate(const CTxMemPoolEntry& tx) const EXCLUSIVE_LOCKS_REQUIRED(cs) {
408        return m_txgraph->GetMainChunkFeerate(tx);
409    }
410    std::vector<const CTxMemPoolEntry*> GetCluster(Txid txid) const EXCLUSIVE_LOCKS_REQUIRED(cs) {
411        auto tx = GetIter(txid);
412        if (!tx) return {};
413        auto cluster = m_txgraph->GetCluster(**tx, TxGraph::Level::MAIN);
414        std::vector<const CTxMemPoolEntry*> ret;
415        ret.reserve(cluster.size());
416        for (const auto& tx : cluster) {
417            ret.emplace_back(static_cast<const CTxMemPoolEntry*>(tx));
418        }
419        return ret;
420    }
421
422
423    size_t GetUniqueClusterCount(const setEntries& iters_conflicting) const EXCLUSIVE_LOCKS_REQUIRED(cs) {
424        std::vector<const TxGraph::Ref *> entries;
425        entries.reserve(iters_conflicting.size());
426        for (auto it : iters_conflicting) {
427            entries.emplace_back(&*it);
428        }
429        Assume(!m_txgraph->IsOversized(TxGraph::Level::MAIN));
430        return m_txgraph->CountDistinctClusters(entries, TxGraph::Level::MAIN);
431    }
432
433    /**
434     * Calculate all in-mempool ancestors of entry (not including the tx itself)
435     *
436     * @param[in]   entry               CTxMemPoolEntry of which all in-mempool ancestors are calculated
437     *
438     * @return all in-mempool ancestors
439     */
440    setEntries CalculateMemPoolAncestors(const CTxMemPoolEntry& entry) const EXCLUSIVE_LOCKS_REQUIRED(cs);
441
442    bool HasDescendants(const Txid& txid) const;
443
444    /** Collect the entire cluster of connected transactions for each transaction in txids.
445     * All txids must correspond to transaction entries in the mempool, otherwise this returns an
446     * empty vector. This call will also exit early and return an empty vector if it collects 500 or
447     * more transactions as a DoS protection. */
448    std::vector<txiter> GatherClusters(const std::vector<Txid>& txids) const EXCLUSIVE_LOCKS_REQUIRED(cs);
449
450    /** Populate setDescendants with all in-mempool descendants of given transaction.
451     *  Assumes that setDescendants includes all in-mempool descendants of anything
452     *  already in it.  */
453    void CalculateDescendants(txiter it, setEntries& setDescendants) const EXCLUSIVE_LOCKS_REQUIRED(cs);
454    CTxMemPool::txiter CalculateDescendants(const CTxMemPoolEntry& entry, setEntries& setDescendants) const EXCLUSIVE_LOCKS_REQUIRED(cs);
455
456    /** The minimum fee to get into the mempool, which may itself not be enough
457     *  for larger-sized transactions.
458     *  The m_incremental_relay_feerate policy variable is used to bound the time it
459     *  takes the fee rate to go back down all the way to 0. When the feerate
460     *  would otherwise be half of this, it is set to 0 instead.
461     */
462    CFeeRate GetMinFee() const {
463        return GetMinFee(m_opts.max_size_bytes);
464    }
465
466    /** Remove transactions from the mempool until its dynamic size is <= sizelimit.
467      *  pvNoSpendsRemaining, if set, will be populated with the list of outpoints
468      *  which are not in mempool which no longer have any spends in this mempool.
469      */
470    void TrimToSize(size_t sizelimit, std::vector<COutPoint>* pvNoSpendsRemaining = nullptr) EXCLUSIVE_LOCKS_REQUIRED(cs);
471
472    /** Expire all transaction (and their dependencies) in the mempool older than time. Return the number of removed transactions. */
473    int Expire(std::chrono::seconds time) EXCLUSIVE_LOCKS_REQUIRED(cs);
474
475    /**
476     * Calculate the ancestor and cluster count for the given transaction.
477     * The counts include the transaction itself.
478     * When ancestors is non-zero (ie, the transaction itself is in the mempool),
479     * ancestorsize and ancestorfees will also be set to the appropriate values.
480     */
481    void GetTransactionAncestry(const Txid& txid, size_t& ancestors, size_t& cluster_count, size_t* ancestorsize = nullptr, CAmount* ancestorfees = nullptr) const;
482
483    /**
484     * @returns true if an initial attempt to load the persisted mempool was made, regardless of
485     *          whether the attempt was successful or not
486     */
487    bool GetLoadTried() const;
488
489    /**
490     * Set whether or not an initial attempt to load the persisted mempool was made (regardless
491     * of whether the attempt was successful or not)
492     */
493    void SetLoadTried(bool load_tried);
494
495    unsigned long size() const
496    {
497        LOCK(cs);
498        return mapTx.size();
499    }
500