diff --git a/src/txmempool.cpp b/src/txmempool.cpp index 83e73dc51..d1c604e1b 100644 --- a/src/txmempool.cpp +++ b/src/txmempool.cpp @@ -1,1118 +1,1055 @@ // 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. #include #include #include // for GetConsensus. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include -// Helpers for modifying CTxMemPool::mapTx, which is a boost multi_index. -// Remove after Wellington -struct update_descendant_state { - update_descendant_state(int64_t _modifySize, Amount _modifyFee, - int64_t _modifyCount, int64_t _modifySigChecks) - : modifySize(_modifySize), modifyFee(_modifyFee), - modifyCount(_modifyCount), modifySigChecks(_modifySigChecks) {} - - void operator()(CTxMemPoolEntry &e) { - e.UpdateDescendantState(modifySize, modifyFee, modifyCount, - modifySigChecks); - } - -private: - int64_t modifySize; - Amount modifyFee; - int64_t modifyCount; - int64_t modifySigChecks; -}; - -struct update_ancestor_state { - update_ancestor_state(int64_t _modifySize, Amount _modifyFee, - int64_t _modifyCount, int64_t _modifySigChecks) - : modifySize(_modifySize), modifyFee(_modifyFee), - modifyCount(_modifyCount), modifySigChecks(_modifySigChecks) {} - - void operator()(CTxMemPoolEntry &e) { - e.UpdateAncestorState(modifySize, modifyFee, modifyCount, - modifySigChecks); - } - -private: - int64_t modifySize; - Amount modifyFee; - int64_t modifyCount; - int64_t modifySigChecks; -}; - bool TestLockPointValidity(const CChain &active_chain, const LockPoints &lp) { AssertLockHeld(cs_main); // If there are relative lock times then the maxInputBlock will be set // If there are no relative lock times, the LockPoints don't depend on the // chain if (lp.maxInputBlock) { // Check whether active_chain is an extension of the block at which the // LockPoints calculation was valid. If not LockPoints are no longer // valid if (!active_chain.Contains(lp.maxInputBlock)) { return false; } } // LockPoints still valid return true; } CTxMemPoolEntry::CTxMemPoolEntry(const CTransactionRef &_tx, const Amount fee, int64_t time, unsigned int entry_height, bool spends_coinbase, int64_t _sigChecks, LockPoints lp) : tx{_tx}, nFee{fee}, nTxSize(tx->GetTotalSize()), nUsageSize{RecursiveDynamicUsage(tx)}, nTime(time), entryHeight{entry_height}, spendsCoinbase(spends_coinbase), sigChecks(_sigChecks), lockPoints(lp), nSizeWithDescendants{GetTxSize()}, nModFeesWithDescendants{nFee}, nSigChecksWithDescendants{sigChecks}, nSizeWithAncestors{GetTxSize()}, nModFeesWithAncestors{nFee}, nSigChecksWithAncestors{sigChecks} {} size_t CTxMemPoolEntry::GetTxVirtualSize() const { return GetVirtualTransactionSize(nTxSize, sigChecks); } // Remove after wellinggton uint64_t CTxMemPoolEntry::GetVirtualSizeWithDescendants() const { // note this is distinct from the sum of descendants' individual virtual // sizes, and may be smaller. return GetVirtualTransactionSize(nSizeWithDescendants, nSigChecksWithDescendants); } // Remove after wellinggton uint64_t CTxMemPoolEntry::GetVirtualSizeWithAncestors() const { // note this is distinct from the sum of ancestors' individual virtual // sizes, and may be smaller. return GetVirtualTransactionSize(nSizeWithAncestors, nSigChecksWithAncestors); } void CTxMemPoolEntry::UpdateFeeDelta(Amount newFeeDelta) { // Remove after wellington; this stat is unused after wellington nModFeesWithDescendants += newFeeDelta - feeDelta; nModFeesWithAncestors += newFeeDelta - feeDelta; feeDelta = newFeeDelta; } void CTxMemPoolEntry::UpdateLockPoints(const LockPoints &lp) { lockPoints = lp; } bool CTxMemPool::CalculateAncestors( setEntries &setAncestors, CTxMemPoolEntry::Parents &staged_ancestors) const { while (!staged_ancestors.empty()) { const CTxMemPoolEntry &stage = staged_ancestors.begin()->get(); txiter stageit = mapTx.iterator_to(stage); setAncestors.insert(stageit); staged_ancestors.erase(staged_ancestors.begin()); const CTxMemPoolEntry::Parents &parents = stageit->GetMemPoolParentsConst(); for (const CTxMemPoolEntry &parent : parents) { txiter parent_it = mapTx.iterator_to(parent); // If this is a new ancestor, add it. if (setAncestors.count(parent_it) == 0) { staged_ancestors.insert(parent); } } } return true; } bool CTxMemPool::CalculateMemPoolAncestors( const CTxMemPoolEntry &entry, setEntries &setAncestors, bool fSearchForParents /* = true */) const { CTxMemPoolEntry::Parents staged_ancestors; const CTransaction &tx = entry.GetTx(); if (fSearchForParents) { // Get parents of this transaction that are in the mempool // GetMemPoolParents() is only valid for entries in the mempool, so we // iterate mapTx to find parents. for (const CTxIn &in : tx.vin) { std::optional piter = GetIter(in.prevout.GetTxId()); if (!piter) { continue; } staged_ancestors.insert(**piter); } } else { // If we're not searching for parents, we require this to be an entry in // the mempool already. staged_ancestors = entry.GetMemPoolParentsConst(); } return CalculateAncestors(setAncestors, staged_ancestors); } void CTxMemPool::UpdateParentsOf(bool add, txiter it) { // add or remove this tx as a child of each parent for (const CTxMemPoolEntry &parent : it->GetMemPoolParentsConst()) { UpdateChild(mapTx.iterator_to(parent), it, add); } } void CTxMemPool::UpdateChildrenForRemoval(txiter it) { const CTxMemPoolEntry::Children &children = it->GetMemPoolChildrenConst(); for (const CTxMemPoolEntry &updateIt : children) { UpdateParent(mapTx.iterator_to(updateIt), it, false); } } void CTxMemPool::UpdateForRemoveFromMempool(const setEntries &entriesToRemove, bool updateDescendants) { for (txiter removeIt : entriesToRemove) { // Note that UpdateParentsOf severs the child links that point to // removeIt in the entries for the parents of removeIt. UpdateParentsOf(false, removeIt); } // After updating all the parent links, we can now sever the link between // each transaction being removed and any mempool children (ie, update // CTxMemPoolEntry::m_parents for each direct child of a transaction being // removed). for (txiter removeIt : entriesToRemove) { UpdateChildrenForRemoval(removeIt); } } -void CTxMemPoolEntry::UpdateDescendantState(int64_t modifySize, - Amount modifyFee, - int64_t modifyCount, - int64_t modifySigChecks) { - nSizeWithDescendants += modifySize; - assert(int64_t(nSizeWithDescendants) > 0); - nModFeesWithDescendants += modifyFee; - nCountWithDescendants += modifyCount; - assert(int64_t(nCountWithDescendants) > 0); - nSigChecksWithDescendants += modifySigChecks; - assert(nSigChecksWithDescendants >= 0); -} - -void CTxMemPoolEntry::UpdateAncestorState(int64_t modifySize, Amount modifyFee, - int64_t modifyCount, - int64_t modifySigChecks) { - nSizeWithAncestors += modifySize; - assert(int64_t(nSizeWithAncestors) > 0); - nModFeesWithAncestors += modifyFee; - nCountWithAncestors += modifyCount; - assert(int64_t(nCountWithAncestors) > 0); - nSigChecksWithAncestors += modifySigChecks; - assert(nSigChecksWithAncestors >= 0); -} - CTxMemPool::CTxMemPool(int check_ratio) : m_check_ratio(check_ratio) { // lock free clear _clear(); } CTxMemPool::~CTxMemPool() {} bool CTxMemPool::isSpent(const COutPoint &outpoint) const { LOCK(cs); return mapNextTx.count(outpoint); } unsigned int CTxMemPool::GetTransactionsUpdated() const { return nTransactionsUpdated; } void CTxMemPool::AddTransactionsUpdated(unsigned int n) { nTransactionsUpdated += n; } void CTxMemPool::addUnchecked(const CTxMemPoolEntry &entryIn, const setEntries &setAncestors) { CTxMemPoolEntry entry{entryIn}; // get a guaranteed unique id (in case tests re-use the same object) entry.SetEntryId(nextEntryId++); // Update transaction for any feeDelta created by PrioritiseTransaction { Amount feeDelta = Amount::zero(); ApplyDelta(entry.GetTx().GetId(), feeDelta); entry.UpdateFeeDelta(feeDelta); } // Add to memory pool without checking anything. // Used by AcceptToMemoryPool(), which DOES do all the appropriate checks. auto [newit, inserted] = mapTx.insert(entry); // Sanity check: It is a programming error if insertion fails (uniqueness // invariants in mapTx are violated, etc) assert(inserted); // Sanity check: We should always end up inserting at the end of the // entry_id index assert(&*mapTx.get().rbegin() == &*newit); // Update cachedInnerUsage to include contained transaction's usage. // (When we update the entry for in-mempool parents, memory usage will be // further updated.) cachedInnerUsage += entry.DynamicMemoryUsage(); const CTransaction &tx = newit->GetTx(); std::set setParentTransactions; for (const CTxIn &in : tx.vin) { mapNextTx.insert(std::make_pair(&in.prevout, &tx)); setParentTransactions.insert(in.prevout.GetTxId()); } // Don't bother worrying about child transactions of this one. It is // guaranteed that a new transaction arriving will not have any children, // because such children would be orphans. // Update ancestors with information about this tx for (const auto &pit : GetIterSet(setParentTransactions)) { UpdateParent(newit, pit, true); } UpdateParentsOf(true, newit); nTransactionsUpdated++; totalTxSize += entry.GetTxSize(); m_total_fee += entry.GetFee(); } void CTxMemPool::removeUnchecked(txiter it, MemPoolRemovalReason reason) { // We increment mempool sequence value no matter removal reason // even if not directly reported below. uint64_t mempool_sequence = GetAndIncrementSequence(); if (reason != MemPoolRemovalReason::BLOCK) { // Notify clients that a transaction has been removed from the mempool // for any reason except being included in a block. Clients interested // in transactions included in blocks can subscribe to the // BlockConnected notification. GetMainSignals().TransactionRemovedFromMempool( it->GetSharedTx(), reason, mempool_sequence); } for (const CTxIn &txin : it->GetTx().vin) { mapNextTx.erase(txin.prevout); } /* add logging because unchecked */ RemoveUnbroadcastTx(it->GetTx().GetId(), true); totalTxSize -= it->GetTxSize(); m_total_fee -= it->GetFee(); cachedInnerUsage -= it->DynamicMemoryUsage(); cachedInnerUsage -= memusage::DynamicUsage(it->GetMemPoolParentsConst()) + memusage::DynamicUsage(it->GetMemPoolChildrenConst()); mapTx.erase(it); nTransactionsUpdated++; } // Calculates descendants of entry that are not already in setDescendants, and // adds to setDescendants. Assumes entryit is already a tx in the mempool and // CTxMemPoolEntry::m_children is correct for tx and all descendants. Also // assumes that if an entry is in setDescendants already, then all in-mempool // descendants of it are already in setDescendants as well, so that we can save // time by not iterating over those entries. void CTxMemPool::CalculateDescendants(txiter entryit, setEntries &setDescendants) const { setEntries stage; if (setDescendants.count(entryit) == 0) { stage.insert(entryit); } // Traverse down the children of entry, only adding children that are not // accounted for in setDescendants already (because those children have // either already been walked, or will be walked in this iteration). while (!stage.empty()) { txiter it = *stage.begin(); setDescendants.insert(it); stage.erase(stage.begin()); const CTxMemPoolEntry::Children &children = it->GetMemPoolChildrenConst(); for (const CTxMemPoolEntry &child : children) { txiter childiter = mapTx.iterator_to(child); if (!setDescendants.count(childiter)) { stage.insert(childiter); } } } } void CTxMemPool::removeRecursive(const CTransaction &origTx, MemPoolRemovalReason reason) { // Remove transaction from memory pool. AssertLockHeld(cs); setEntries txToRemove; txiter origit = mapTx.find(origTx.GetId()); if (origit != mapTx.end()) { txToRemove.insert(origit); } else { // When recursively removing but origTx isn't in the mempool be sure to // remove any children that are in the pool. This can happen during // chain re-orgs if origTx isn't re-accepted into the mempool for any // reason. auto it = mapNextTx.lower_bound(COutPoint(origTx.GetId(), 0)); while (it != mapNextTx.end() && it->first->GetTxId() == origTx.GetId()) { txiter nextit = mapTx.find(it->second->GetId()); assert(nextit != mapTx.end()); txToRemove.insert(nextit); ++it; } } setEntries setAllRemoves; for (txiter it : txToRemove) { CalculateDescendants(it, setAllRemoves); } RemoveStaged(setAllRemoves, false, reason); } void CTxMemPool::removeConflicts(const CTransaction &tx) { // Remove transactions which depend on inputs of tx, recursively AssertLockHeld(cs); for (const CTxIn &txin : tx.vin) { auto it = mapNextTx.find(txin.prevout); if (it != mapNextTx.end()) { const CTransaction &txConflict = *it->second; if (txConflict != tx) { ClearPrioritisation(txConflict.GetId()); removeRecursive(txConflict, MemPoolRemovalReason::CONFLICT); } } } } /** * Called when a block is connected. Removes from mempool and updates the miner * fee estimator. */ void CTxMemPool::removeForBlock(const std::vector &vtx) { AssertLockHeld(cs); if (mapTx.empty() && mapDeltas.empty()) { // fast-path for IBD and/or when mempool is empty; there is no need to // do any of the set-up work below which eats precious cycles. // Note that this also skips updating the rolling fee udpate, which is // fine: it is only recomputed when the mempool has to be trimmed down // because it is full which is contradictory with this condition. return; } DisconnectedBlockTransactions disconnectpool; disconnectpool.addForBlock(vtx, *this); for (const CTransactionRef &tx : reverse_iterate(disconnectpool.GetQueuedTx().get())) { txiter it = mapTx.find(tx->GetId()); if (it != mapTx.end()) { setEntries stage; stage.insert(it); RemoveStaged(stage, true, MemPoolRemovalReason::BLOCK); } else { // Conflicting txs can only exist if the tx was not in the mempool removeConflicts(*tx); } ClearPrioritisation(tx->GetId()); } disconnectpool.clear(); lastRollingFeeUpdate = GetTime(); blockSinceLastRollingFeeBump = true; } void CTxMemPool::_clear() { mapTx.clear(); mapNextTx.clear(); totalTxSize = 0; m_total_fee = Amount::zero(); cachedInnerUsage = 0; lastRollingFeeUpdate = GetTime(); blockSinceLastRollingFeeBump = false; rollingMinimumFeeRate = 0; ++nTransactionsUpdated; } void CTxMemPool::clear() { LOCK(cs); _clear(); } void CTxMemPool::check(const CCoinsViewCache &active_coins_tip, int64_t spendheight) const { if (m_check_ratio == 0) { return; } if (GetRand(m_check_ratio) >= 1) { return; } AssertLockHeld(::cs_main); LOCK(cs); LogPrint(BCLog::MEMPOOL, "Checking mempool with %u transactions and %u inputs\n", (unsigned int)mapTx.size(), (unsigned int)mapNextTx.size()); uint64_t checkTotal = 0; Amount check_total_fee{Amount::zero()}; uint64_t innerUsage = 0; CCoinsViewCache mempoolDuplicate( const_cast(&active_coins_tip)); for (const CTxMemPoolEntry &entry : mapTx.get()) { checkTotal += entry.GetTxSize(); check_total_fee += entry.GetFee(); innerUsage += entry.DynamicMemoryUsage(); const CTransaction &tx = entry.GetTx(); innerUsage += memusage::DynamicUsage(entry.GetMemPoolParentsConst()) + memusage::DynamicUsage(entry.GetMemPoolChildrenConst()); CTxMemPoolEntry::Parents setParentCheck; for (const CTxIn &txin : tx.vin) { // Check that every mempool transaction's inputs refer to available // coins, or other mempool tx's. txiter parentIt = mapTx.find(txin.prevout.GetTxId()); if (parentIt != mapTx.end()) { const CTransaction &parentTx = parentIt->GetTx(); assert(parentTx.vout.size() > txin.prevout.GetN() && !parentTx.vout[txin.prevout.GetN()].IsNull()); setParentCheck.insert(*parentIt); // also check that parents have a topological ordering before // their children assert(parentIt->GetEntryId() < entry.GetEntryId()); } // We are iterating through the mempool entries sorted // topologically. // All parents must have been checked before their children and // their coins added to the mempoolDuplicate coins cache. assert(mempoolDuplicate.HaveCoin(txin.prevout)); // Check whether its inputs are marked in mapNextTx. auto prevoutNextIt = mapNextTx.find(txin.prevout); assert(prevoutNextIt != mapNextTx.end()); assert(prevoutNextIt->first == &txin.prevout); assert(prevoutNextIt->second == &tx); } auto comp = [](const CTxMemPoolEntry &a, const CTxMemPoolEntry &b) -> bool { return a.GetTx().GetId() == b.GetTx().GetId(); }; assert(setParentCheck.size() == entry.GetMemPoolParentsConst().size()); assert(std::equal(setParentCheck.begin(), setParentCheck.end(), entry.GetMemPoolParentsConst().begin(), comp)); // Verify ancestor state is correct. setEntries setAncestors; std::string dummy; const bool ok = CalculateMemPoolAncestors(entry, setAncestors); assert(ok); // all ancestors should have entryId < this tx's entryId for (const auto &ancestor : setAncestors) { assert(ancestor->GetEntryId() < entry.GetEntryId()); } // Check children against mapNextTx CTxMemPoolEntry::Children setChildrenCheck; auto iter = mapNextTx.lower_bound(COutPoint(entry.GetTx().GetId(), 0)); uint64_t child_sizes = 0; int64_t child_sigChecks = 0; for (; iter != mapNextTx.end() && iter->first->GetTxId() == entry.GetTx().GetId(); ++iter) { txiter childIt = mapTx.find(iter->second->GetId()); // mapNextTx points to in-mempool transactions assert(childIt != mapTx.end()); if (setChildrenCheck.insert(*childIt).second) { child_sizes += childIt->GetTxSize(); child_sigChecks += childIt->GetSigChecks(); } } assert(setChildrenCheck.size() == entry.GetMemPoolChildrenConst().size()); assert(std::equal(setChildrenCheck.begin(), setChildrenCheck.end(), entry.GetMemPoolChildrenConst().begin(), comp)); // Not used. CheckTxInputs() should always pass TxValidationState dummy_state; Amount txfee{Amount::zero()}; assert(!tx.IsCoinBase()); assert(Consensus::CheckTxInputs(tx, dummy_state, mempoolDuplicate, spendheight, txfee)); for (const auto &input : tx.vin) { mempoolDuplicate.SpendCoin(input.prevout); } AddCoins(mempoolDuplicate, tx, std::numeric_limits::max()); } for (auto &[_, nextTx] : mapNextTx) { txiter it = mapTx.find(nextTx->GetId()); assert(it != mapTx.end()); assert(&it->GetTx() == nextTx); } assert(totalTxSize == checkTotal); assert(m_total_fee == check_total_fee); assert(innerUsage == cachedInnerUsage); } bool CTxMemPool::CompareTopologically(const TxId &txida, const TxId &txidb) const { LOCK(cs); auto it1 = mapTx.find(txida); if (it1 == mapTx.end()) { return false; } auto it2 = mapTx.find(txidb); if (it2 == mapTx.end()) { return true; } return it1->GetEntryId() < it2->GetEntryId(); } void CTxMemPool::getAllTxIds(std::vector &vtxid) const { LOCK(cs); vtxid.clear(); vtxid.reserve(mapTx.size()); for (const auto &entry : mapTx.get()) { vtxid.push_back(entry.GetTx().GetId()); } } static TxMempoolInfo GetInfo(CTxMemPool::indexed_transaction_set::const_iterator it) { return TxMempoolInfo{it->GetSharedTx(), it->GetTime(), it->GetFee(), it->GetTxSize(), it->GetModifiedFee() - it->GetFee()}; } std::vector CTxMemPool::infoAll() const { LOCK(cs); std::vector ret; ret.reserve(mapTx.size()); const auto &index = mapTx.get(); for (auto it = index.begin(); it != index.end(); ++it) { ret.push_back(GetInfo(mapTx.project<0>(it))); } return ret; } CTransactionRef CTxMemPool::get(const TxId &txid) const { LOCK(cs); indexed_transaction_set::const_iterator i = mapTx.find(txid); if (i == mapTx.end()) { return nullptr; } return i->GetSharedTx(); } TxMempoolInfo CTxMemPool::info(const TxId &txid) const { LOCK(cs); indexed_transaction_set::const_iterator i = mapTx.find(txid); if (i == mapTx.end()) { return TxMempoolInfo(); } return GetInfo(i); } CFeeRate CTxMemPool::estimateFee() const { LOCK(cs); uint64_t maxMempoolSize = gArgs.GetIntArg("-maxmempool", DEFAULT_MAX_MEMPOOL_SIZE) * 1000000; // minerPolicy uses recent blocks to figure out a reasonable fee. This // may disagree with the rollingMinimumFeerate under certain scenarios // where the mempool increases rapidly, or blocks are being mined which // do not contain propagated transactions. return std::max(::minRelayTxFee, GetMinFee(maxMempoolSize)); } void CTxMemPool::PrioritiseTransaction(const TxId &txid, const Amount nFeeDelta) { { LOCK(cs); Amount &delta = mapDeltas[txid]; delta += nFeeDelta; txiter it = mapTx.find(txid); if (it != mapTx.end()) { mapTx.modify( it, [&delta](CTxMemPoolEntry &e) { e.UpdateFeeDelta(delta); }); ++nTransactionsUpdated; } } LogPrintf("PrioritiseTransaction: %s fee += %s\n", txid.ToString(), FormatMoney(nFeeDelta)); } void CTxMemPool::ApplyDelta(const TxId &txid, Amount &nFeeDelta) const { AssertLockHeld(cs); std::map::const_iterator pos = mapDeltas.find(txid); if (pos == mapDeltas.end()) { return; } nFeeDelta += pos->second; } void CTxMemPool::ClearPrioritisation(const TxId &txid) { AssertLockHeld(cs); mapDeltas.erase(txid); } const CTransaction *CTxMemPool::GetConflictTx(const COutPoint &prevout) const { const auto it = mapNextTx.find(prevout); return it == mapNextTx.end() ? nullptr : it->second; } std::optional CTxMemPool::GetIter(const TxId &txid) const { auto it = mapTx.find(txid); if (it != mapTx.end()) { return it; } return std::nullopt; } CTxMemPool::setEntries CTxMemPool::GetIterSet(const std::set &txids) const { CTxMemPool::setEntries ret; for (const auto &txid : txids) { const auto mi = GetIter(txid); if (mi) { ret.insert(*mi); } } return ret; } bool CTxMemPool::HasNoInputsOf(const CTransaction &tx) const { for (const CTxIn &in : tx.vin) { if (exists(in.prevout.GetTxId())) { return false; } } return true; } CCoinsViewMemPool::CCoinsViewMemPool(CCoinsView *baseIn, const CTxMemPool &mempoolIn) : CCoinsViewBacked(baseIn), mempool(mempoolIn) {} bool CCoinsViewMemPool::GetCoin(const COutPoint &outpoint, Coin &coin) const { // Check to see if the inputs are made available by another tx in the // package. These Coins would not be available in the underlying CoinsView. if (auto it = m_temp_added.find(outpoint); it != m_temp_added.end()) { coin = it->second; return true; } // If an entry in the mempool exists, always return that one, as it's // guaranteed to never conflict with the underlying cache, and it cannot // have pruned entries (as it contains full) transactions. First checking // the underlying cache risks returning a pruned entry instead. CTransactionRef ptx = mempool.get(outpoint.GetTxId()); if (ptx) { if (outpoint.GetN() < ptx->vout.size()) { coin = Coin(ptx->vout[outpoint.GetN()], MEMPOOL_HEIGHT, false); return true; } return false; } return base->GetCoin(outpoint, coin); } void CCoinsViewMemPool::PackageAddTransaction(const CTransactionRef &tx) { for (uint32_t n = 0; n < tx->vout.size(); ++n) { m_temp_added.emplace(COutPoint(tx->GetId(), n), Coin(tx->vout[n], MEMPOOL_HEIGHT, false)); } } size_t CTxMemPool::DynamicMemoryUsage() const { LOCK(cs); // Estimate the overhead of mapTx to be 12 pointers + an allocation, as no // exact formula for boost::multi_index_contained is implemented. return memusage::MallocUsage(sizeof(CTxMemPoolEntry) + 12 * sizeof(void *)) * mapTx.size() + memusage::DynamicUsage(mapNextTx) + memusage::DynamicUsage(mapDeltas) + cachedInnerUsage; } void CTxMemPool::RemoveUnbroadcastTx(const TxId &txid, const bool unchecked) { LOCK(cs); if (m_unbroadcast_txids.erase(txid)) { LogPrint( BCLog::MEMPOOL, "Removed %i from set of unbroadcast txns%s\n", txid.GetHex(), (unchecked ? " before confirmation that txn was sent out" : "")); } } void CTxMemPool::RemoveStaged(const setEntries &stage, bool updateDescendants, MemPoolRemovalReason reason) { AssertLockHeld(cs); UpdateForRemoveFromMempool(stage, updateDescendants); for (txiter it : stage) { removeUnchecked(it, reason); } } int CTxMemPool::Expire(std::chrono::seconds time) { AssertLockHeld(cs); indexed_transaction_set::index::type::iterator it = mapTx.get().begin(); setEntries toremove; while (it != mapTx.get().end() && it->GetTime() < time) { toremove.insert(mapTx.project<0>(it)); it++; } setEntries stage; for (txiter removeit : toremove) { CalculateDescendants(removeit, stage); } RemoveStaged(stage, false, MemPoolRemovalReason::EXPIRY); return stage.size(); } void CTxMemPool::LimitSize(CCoinsViewCache &coins_cache, size_t limit, std::chrono::seconds age) { AssertLockHeld(::cs_main); AssertLockHeld(cs); int expired = Expire(GetTime() - age); if (expired != 0) { LogPrint(BCLog::MEMPOOL, "Expired %i transactions from the memory pool\n", expired); } std::vector vNoSpendsRemaining; TrimToSize(limit, &vNoSpendsRemaining); for (const COutPoint &removed : vNoSpendsRemaining) { coins_cache.Uncache(removed); } } void CTxMemPool::addUnchecked(const CTxMemPoolEntry &entry) { setEntries setAncestors; return addUnchecked(entry, setAncestors); } void CTxMemPool::UpdateChild(txiter entry, txiter child, bool add) { AssertLockHeld(cs); CTxMemPoolEntry::Children s; if (add && entry->GetMemPoolChildren().insert(*child).second) { cachedInnerUsage += memusage::IncrementalDynamicUsage(s); } else if (!add && entry->GetMemPoolChildren().erase(*child)) { cachedInnerUsage -= memusage::IncrementalDynamicUsage(s); } } void CTxMemPool::UpdateParent(txiter entry, txiter parent, bool add) { AssertLockHeld(cs); CTxMemPoolEntry::Parents s; if (add && entry->GetMemPoolParents().insert(*parent).second) { cachedInnerUsage += memusage::IncrementalDynamicUsage(s); } else if (!add && entry->GetMemPoolParents().erase(*parent)) { cachedInnerUsage -= memusage::IncrementalDynamicUsage(s); } } CFeeRate CTxMemPool::GetMinFee(size_t sizelimit) const { LOCK(cs); if (!blockSinceLastRollingFeeBump || rollingMinimumFeeRate == 0) { return CFeeRate(int64_t(ceill(rollingMinimumFeeRate)) * SATOSHI); } int64_t time = GetTime(); if (time > lastRollingFeeUpdate + 10) { double halflife = ROLLING_FEE_HALFLIFE; if (DynamicMemoryUsage() < sizelimit / 4) { halflife /= 4; } else if (DynamicMemoryUsage() < sizelimit / 2) { halflife /= 2; } rollingMinimumFeeRate = rollingMinimumFeeRate / pow(2.0, (time - lastRollingFeeUpdate) / halflife); lastRollingFeeUpdate = time; } return CFeeRate(int64_t(ceill(rollingMinimumFeeRate)) * SATOSHI); } void CTxMemPool::trackPackageRemoved(const CFeeRate &rate) { AssertLockHeld(cs); if ((rate.GetFeePerK() / SATOSHI) > rollingMinimumFeeRate) { rollingMinimumFeeRate = rate.GetFeePerK() / SATOSHI; blockSinceLastRollingFeeBump = false; } } void CTxMemPool::TrimToSize(size_t sizelimit, std::vector *pvNoSpendsRemaining) { AssertLockHeld(cs); unsigned nTxnRemoved = 0; CFeeRate maxFeeRateRemoved(Amount::zero()); while (!mapTx.empty() && DynamicMemoryUsage() > sizelimit) { auto it = mapTx.get().end(); --it; // We set the new mempool min fee to the feerate of the removed // transaction, plus the "minimum reasonable fee rate" (ie some value // under which we consider txn to have 0 fee). This way, we don't allow // txn to enter mempool with feerate equal to txn which were removed // with no block in between. CFeeRate removed = it->GetModifiedFeeRate(); removed += MEMPOOL_FULL_FEE_INCREMENT; trackPackageRemoved(removed); maxFeeRateRemoved = std::max(maxFeeRateRemoved, removed); setEntries stage; CalculateDescendants(mapTx.project<0>(it), stage); nTxnRemoved += stage.size(); if (pvNoSpendsRemaining) { for (const txiter &iter : stage) { for (const CTxIn &txin : iter->GetTx().vin) { if (!exists(txin.prevout.GetTxId())) { pvNoSpendsRemaining->push_back(txin.prevout); } } } } RemoveStaged(stage, false, MemPoolRemovalReason::SIZELIMIT); } if (maxFeeRateRemoved > CFeeRate(Amount::zero())) { LogPrint(BCLog::MEMPOOL, "Removed %u txn, rolling minimum fee bumped to %s\n", nTxnRemoved, maxFeeRateRemoved.ToString()); } } bool CTxMemPool::IsLoaded() const { LOCK(cs); return m_is_loaded; } void CTxMemPool::SetIsLoaded(bool loaded) { LOCK(cs); m_is_loaded = loaded; } /** Maximum bytes for transactions to store for processing during reorg */ static const size_t MAX_DISCONNECTED_TX_POOL_SIZE = 20 * DEFAULT_MAX_BLOCK_SIZE; void DisconnectedBlockTransactions::addForBlock( const std::vector &vtx, CTxMemPool &pool) { AssertLockHeld(pool.cs); for (const auto &tx : reverse_iterate(vtx)) { // If we already added it, just skip. auto it = queuedTx.find(tx->GetId()); if (it != queuedTx.end()) { continue; } // Insert the transaction into the pool. addTransaction(tx); // Fill in the set of parents. std::unordered_set parents; for (const CTxIn &in : tx->vin) { parents.insert(in.prevout.GetTxId()); } // In order to make sure we keep things in topological order, we check // if we already know of the parent of the current transaction. If so, // we remove them from the set and then add them back. while (parents.size() > 0) { std::unordered_set worklist( std::move(parents)); parents.clear(); for (const TxId &txid : worklist) { // If we do not have that txid in the set, nothing needs to be // done. auto pit = queuedTx.find(txid); if (pit == queuedTx.end()) { continue; } // We have parent in our set, we reinsert them at the right // position. const CTransactionRef ptx = *pit; queuedTx.erase(pit); queuedTx.insert(ptx); // And we make sure ancestors are covered. for (const CTxIn &in : ptx->vin) { parents.insert(in.prevout.GetTxId()); } } } } // Keep the size under control. while (DynamicMemoryUsage() > MAX_DISCONNECTED_TX_POOL_SIZE) { // Drop the earliest entry, and remove its children from the // mempool. auto it = queuedTx.get().begin(); pool.removeRecursive(**it, MemPoolRemovalReason::REORG); removeEntry(it); } } void DisconnectedBlockTransactions::importMempool(CTxMemPool &pool) { AssertLockHeld(pool.cs); // addForBlock's algorithm sorts a vector of transactions back into // topological order. We use it in a separate object to create a valid // ordering of all mempool transactions, which we then splice in front of // the current queuedTx. This results in a valid sequence of transactions to // be reprocessed in updateMempoolForReorg. // We create vtx in order of the entry_id index to facilitate for // addForBlocks (which iterates in reverse order), as vtx probably end in // the correct ordering for queuedTx. std::vector vtx; vtx.reserve(pool.mapTx.size()); txInfo.reserve(pool.mapTx.size()); for (const CTxMemPoolEntry &e : pool.mapTx.get()) { vtx.push_back(e.GetSharedTx()); // save entry time, feeDelta, and height for use in // updateMempoolForReorg() txInfo.try_emplace(e.GetTx().GetId(), e.GetTime(), e.GetModifiedFee() - e.GetFee(), e.GetHeight()); // Notify all observers of this (possibly temporary) removal. This is // necessary for tracking the transactions that are removed from the // mempool during a reorg and can't be added back due to missing parent. // Transactions that are added back to the mempool will trigger another // notification. GetMainSignals().TransactionRemovedFromMempool( e.GetSharedTx(), MemPoolRemovalReason::REORG, pool.GetAndIncrementSequence()); } pool.clear(); // Use addForBlocks to sort the transactions and then splice them in front // of queuedTx DisconnectedBlockTransactions orderedTxnPool; orderedTxnPool.addForBlock(vtx, pool); cachedInnerUsage += orderedTxnPool.cachedInnerUsage; queuedTx.get().splice( queuedTx.get().begin(), orderedTxnPool.queuedTx.get()); // We limit memory usage because we can't know if more blocks will be // disconnected while (DynamicMemoryUsage() > MAX_DISCONNECTED_TX_POOL_SIZE) { // Drop the earliest entry which, by definition, has no children removeEntry(queuedTx.get().begin()); } } auto DisconnectedBlockTransactions::getTxInfo(const CTransactionRef &tx) const -> const TxInfo * { if (auto it = txInfo.find(tx->GetId()); it != txInfo.end()) { return &it->second; } return nullptr; } void DisconnectedBlockTransactions::updateMempoolForReorg( const Config &config, Chainstate &active_chainstate, bool fAddToMempool, CTxMemPool &pool) { AssertLockHeld(cs_main); AssertLockHeld(pool.cs); if (fAddToMempool) { // disconnectpool's insertion_order index sorts the entries from oldest // to newest, but the oldest entry will be the last tx from the latest // mined block that was disconnected. // Iterate disconnectpool in reverse, so that we add transactions back // to the mempool starting with the earliest transaction that had been // previously seen in a block. for (const CTransactionRef &tx : reverse_iterate(queuedTx.get())) { if (tx->IsCoinBase()) { continue; } // restore saved PrioritiseTransaction state and nAcceptTime const auto ptxInfo = getTxInfo(tx); bool hasFeeDelta = false; if (ptxInfo && ptxInfo->feeDelta != Amount::zero()) { // manipulate mapDeltas directly (faster than calling // PrioritiseTransaction) pool.mapDeltas[tx->GetId()] = ptxInfo->feeDelta; hasFeeDelta = true; } // ignore validation errors in resurrected transactions auto result = AcceptToMemoryPool( config, active_chainstate, tx, /*accept_time=*/ptxInfo ? ptxInfo->time.count() : GetTime(), /*bypass_limits=*/true, /*test_accept=*/false, /*heightOverride=*/ptxInfo ? ptxInfo->height : 0); if (result.m_result_type != MempoolAcceptResult::ResultType::VALID && hasFeeDelta) { // tx not accepted: undo mapDelta insertion from above pool.mapDeltas.erase(tx->GetId()); } } } queuedTx.clear(); txInfo.clear(); // Re-limit mempool size, in case we added any transactions pool.LimitSize(active_chainstate.CoinsTip(), gArgs.GetIntArg("-maxmempool", DEFAULT_MAX_MEMPOOL_SIZE) * 1000000, std::chrono::hours{gArgs.GetIntArg("-mempoolexpiry", DEFAULT_MEMPOOL_EXPIRY)}); } diff --git a/src/txmempool.h b/src/txmempool.h index feee64a03..784403a37 100644 --- a/src/txmempool.h +++ b/src/txmempool.h @@ -1,922 +1,915 @@ // 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 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include class CBlockIndex; class CChain; class Chainstate; class Config; extern RecursiveMutex cs_main; /** * Fake height value used in Coins to signify they are only in the memory * pool(since 0.8) */ 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}; }; /** * Test whether the LockPoints height and time are still valid on the current * chain. */ 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 (e.g. a wrapped CTxMemPoolEntry&) template bool operator()(const std::reference_wrapper &a, const std::reference_wrapper &b) const { return a.get().GetTx().GetId() < b.get().GetTx().GetId(); } template bool operator()(const T &a, const T &b) const { return a->GetTx().GetId() < b->GetTx().GetId(); } }; /** \class CTxMemPoolEntry * * CTxMemPoolEntry stores data about the corresponding transaction, as well as * data about all in-mempool transactions that depend on the transaction * ("descendant" transactions). * * When a new entry is added to the mempool, we update the descendant state * (nCountWithDescendants, nSizeWithDescendants, and nModFeesWithDescendants) * for all ancestors of the newly added transaction. */ class CTxMemPoolEntry { public: typedef std::reference_wrapper CTxMemPoolEntryRef; // two aliases, should the types ever diverge typedef std::set Parents; typedef std::set Children; private: //! Unique identifier -- used for topological sorting uint64_t entryId = 0; const CTransactionRef tx; mutable Parents m_parents; mutable Children m_children; //! Cached to avoid expensive parent-transaction lookups const Amount nFee; //! ... and avoid recomputing tx size const size_t nTxSize; //! ... and total memory usage const size_t nUsageSize; //! Local time when entering the mempool const int64_t nTime; //! Chain height when entering the mempool const unsigned int entryHeight; //! keep track of transactions that spend a coinbase const bool spendsCoinbase; //! Total sigChecks const int64_t sigChecks; //! Used for determining the priority of the transaction for mining in a //! block Amount feeDelta{Amount::zero()}; //! Track the height and time at which tx was final 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. //! number of descendant transactions uint64_t nCountWithDescendants{1}; //! ... and size uint64_t nSizeWithDescendants; //! ... and total fees (all including us) Amount nModFeesWithDescendants; //! ... and sichecks 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; } //! This should only be set by addUnchecked() before entry insertion into //! mempool 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(); } }; /** * \class CompareTxMemPoolEntryByModifiedFeeRate * * Sort by feerate of entry (modfee/vsize) in descending order. * This is used by the block assembler (mining). */ 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 {}; /** * Information about a mempool transaction. */ struct TxMempoolInfo { /** The transaction itself */ CTransactionRef tx; /** Time the transaction entered the mempool. */ std::chrono::seconds m_time; /** Fee of the transaction. */ Amount fee; /** Virtual size of the transaction. */ size_t vsize; /** The fee delta. */ Amount nFeeDelta; }; /** * Reason why a transaction was removed from the mempool, this is passed to the * notification signal. */ enum class MemPoolRemovalReason { //! Expired from mempool EXPIRY, //! Removed in size limiting SIZELIMIT, //! Removed for reorganization REORG, //! Removed for block BLOCK, //! Removed for conflict with in-block transaction CONFLICT, //! Removed for replacement REPLACED }; /** * CTxMemPool stores valid-according-to-the-current-best-chain transactions that * may be included in the next block. * * Transactions are added when they are seen on the network (or created by the * local node), but not all transactions seen are added to the pool. For * example, the following new transactions will not be added to the mempool: * - a transaction which doesn't meet the minimum fee requirements. * - a new transaction that double-spends an input of a transaction already in * the pool. * - a non-standard transaction. * * CTxMemPool::mapTx, and CTxMemPoolEntry bookkeeping: * * mapTx is a boost::multi_index that sorts the mempool on 3 criteria: * - transaction hash * - time in mempool * - entry id (this is a topological index) * * Note: the term "descendant" refers to in-mempool transactions that depend on * this one, while "ancestor" refers to in-mempool transactions that a given * transaction depends on. * * When a new transaction is added to the mempool, it has no in-mempool children * (because any such children would be an orphan). So in addUnchecked(), we: * - update a new entry's setMemPoolParents to include all in-mempool parents * - update the new entry's direct parents to include the new tx as a child * * When a transaction is removed from the mempool, we must: * - update all in-mempool parents to not track the tx in setMemPoolChildren * - update all in-mempool children to not include it as a parent * * These happen in UpdateForRemoveFromMempool(). (Note that when removing a * transaction along with its descendants, we must calculate that set of * transactions to be removed before doing the removal, or else the mempool can * be in an inconsistent state where it's impossible to walk the ancestors of a * transaction.) * * In the event of a reorg, the invariant that all newly-added tx's have no * in-mempool children must be maintained. On top of this, we use a topological * index (GetEntryId). As such, we always dump mempool tx's into a disconnect * pool on reorg, and simply add them one by one, along with tx's from * disconnected blocks, when the reorg is complete. * * Computational limits: * * Updating all in-mempool ancestors of a newly added transaction before * wellington activates can be slow. After wellington, no bound exists on how * many in-mempool ancestors there may be. */ class CTxMemPool { private: //! Value n means that 1 times in n we check. const int m_check_ratio; //! Used by getblocktemplate to trigger CreateNewBlock() invocation std::atomic nTransactionsUpdated{0}; //! sum of all mempool tx's sizes. uint64_t totalTxSize GUARDED_BY(cs); //! sum of all mempool tx's fees (NOT modified fee) Amount m_total_fee GUARDED_BY(cs); //! sum of dynamic memory usage of all the map elements (NOT the maps //! themselves) uint64_t cachedInnerUsage GUARDED_BY(cs); mutable int64_t lastRollingFeeUpdate GUARDED_BY(cs); mutable bool blockSinceLastRollingFeeBump GUARDED_BY(cs); //! minimum fee to get into the pool, decreases exponentially 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}; //! Used by addUnchecked to generate ever-increasing //! CTxMemPoolEntry::entryId's 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, boost::multi_index::identity, CompareTxMemPoolEntryByModifiedFeeRate>, // sorted by entry time boost::multi_index::ordered_non_unique< boost::multi_index::tag, boost::multi_index::identity, CompareTxMemPoolEntryByEntryTime>, // sorted topologically (insertion order) boost::multi_index::ordered_unique< boost::multi_index::tag, boost::multi_index::identity, CompareTxMemPoolEntryByEntryId>>> indexed_transaction_set; /** * This mutex needs to be locked when accessing `mapTx` or other members * that are guarded by it. * * @par Consistency guarantees * * By design, it is guaranteed that: * * 1. Locking both `cs_main` and `mempool.cs` will give a view of mempool * that is consistent with current chain tip (`ActiveChain()` and * `CoinsTip()`) and is fully populated. Fully populated means that if * the current active chain is missing transactions that were present in * a previously active chain, all the missing transactions will have been * re-added to the mempool and should be present if they meet size and * consistency constraints. * * 2. Locking `mempool.cs` without `cs_main` will give a view of a mempool * consistent with some chain that was active since `cs_main` was last * locked, and that is fully populated as described above. It is ok for * code that only needs to query or remove transactions from the mempool * to lock just `mempool.cs` without `cs_main`. * * To provide these guarantees, it is necessary to lock both `cs_main` and * `mempool.cs` whenever adding transactions to the mempool and whenever * changing the chain tip. It's necessary to keep both mutexes locked until * the mempool is consistent with the new chain tip and fully populated. */ mutable RecursiveMutex cs; indexed_transaction_set mapTx GUARDED_BY(cs); using txiter = indexed_transaction_set::nth_index<0>::type::const_iterator; typedef std::set setEntries; 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); /** * Track locally submitted transactions to periodically retry initial * broadcast */ std::set m_unbroadcast_txids GUARDED_BY(cs); /** * Helper function to calculate all in-mempool ancestors of staged_ancestors * param@[in] staged_ancestors Should contain entries in the mempool. * param@[out] setAncestors Will be populated with all mempool * ancestors. */ bool CalculateAncestors(setEntries &setAncestors, CTxMemPoolEntry::Parents &staged_ancestors) const EXCLUSIVE_LOCKS_REQUIRED(cs); public: indirectmap mapNextTx GUARDED_BY(cs); std::map mapDeltas GUARDED_BY(cs); /** * Create a new CTxMemPool. * Sanity checks will be off by default for performance, because otherwise * accepting transactions becomes O(N^2) where N is the number of * transactions in the pool. * * @param[in] check_ratio is the ratio used to determine how often sanity * checks will run. */ CTxMemPool(int check_ratio = 0); ~CTxMemPool(); /** * If sanity-checking is turned on, check makes sure the pool is consistent * (does not contain two transactions that spend the same inputs, all inputs * are in the mapNextTx array). If sanity-checking is turned off, check does * nothing. */ 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 &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 &vtxid) const; bool isSpent(const COutPoint &outpoint) const; unsigned int GetTransactionsUpdated() const; void AddTransactionsUpdated(unsigned int n); /** * Check that none of this transactions inputs are in the mempool, and thus * the tx is not dependent on other mempool transactions to be included in a * block. */ bool HasNoInputsOf(const CTransaction &tx) const EXCLUSIVE_LOCKS_REQUIRED(cs); /** Affect CreateNewBlock prioritisation of transactions */ 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); /** Get the transaction in the pool that spends the same prevout */ const CTransaction *GetConflictTx(const COutPoint &prevout) const EXCLUSIVE_LOCKS_REQUIRED(cs); /** Returns an iterator to the given txid, if found */ std::optional GetIter(const TxId &txid) const EXCLUSIVE_LOCKS_REQUIRED(cs); /** * Translate a set of txids into a set of pool iterators to avoid repeated * lookups. */ setEntries GetIterSet(const std::set &txids) const EXCLUSIVE_LOCKS_REQUIRED(cs); /** * Remove a set of transactions from the mempool. If a transaction is in * this set, then all in-mempool descendants must also be in the set, unless * this transaction is being removed for being in a block. Set * updateDescendants to true when removing a tx that was in a block, so that * any in-mempool descendants have their ancestor state updated (only * evaluated before wellington activation). */ void RemoveStaged(const setEntries &stage, bool updateDescendants, MemPoolRemovalReason reason) EXCLUSIVE_LOCKS_REQUIRED(cs); /** * Try to calculate all in-mempool ancestors of entry. * (these are all calculated including the tx itself) * fSearchForParents = whether to search a tx's vin for in-mempool parents, * or look up parents from m_parents. Must be true for entries not in the * mempool */ bool CalculateMemPoolAncestors(const CTxMemPoolEntry &entry, setEntries &setAncestors, bool fSearchForParents = true) const EXCLUSIVE_LOCKS_REQUIRED(cs); /** * Calculate all in-mempool ancestors of a set of transactions not already * in the mempool and check ancestor and descendant limits. Heuristics are * used to estimate the ancestor and descendant count of all entries if the * package were to be added to the mempool. The limits are applied to the * union of all package transactions. For example, if the package has 3 * transactions and limitAncestorCount = 50, the union of all 3 sets of * ancestors (including the transactions themselves) must be <= 47. * @param[in] package Transaction package being * evaluated for acceptance to mempool. The transactions need not be * direct ancestors/descendants of each other. * @param[in] limitAncestorCount Max number of txns including * ancestors. * @param[in] limitAncestorSize Max size including ancestors. * @param[in] limitDescendantCount Max number of txns including * descendants. * @param[in] limitDescendantSize Max size including descendants. * @param[out] errString Populated with error reason if * a limit is hit. */ 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); /** * Populate setDescendants with all in-mempool descendants of hash. * Assumes that setDescendants includes all in-mempool descendants of * anything already in it. */ void CalculateDescendants(txiter it, setEntries &setDescendants) const EXCLUSIVE_LOCKS_REQUIRED(cs); /** * The minimum fee to get into the mempool, which may itself not be enough * for larger-sized transactions. The incrementalRelayFee policy variable is * used to bound the time it takes the fee rate to go back down all the way * to 0. When the feerate would otherwise be half of this, it is set to 0 * instead. */ CFeeRate GetMinFee(size_t sizelimit) const; /** * Remove transactions from the mempool until its dynamic size is <= * sizelimit. pvNoSpendsRemaining, if set, will be populated with the list * of outpoints which are not in mempool which no longer have any spends in * this mempool. */ void TrimToSize(size_t sizelimit, std::vector *pvNoSpendsRemaining = nullptr) EXCLUSIVE_LOCKS_REQUIRED(cs); /** * Expire all transaction (and their dependencies) in the mempool older than * time. Return the number of removed transactions. */ int Expire(std::chrono::seconds time) EXCLUSIVE_LOCKS_REQUIRED(cs); /** * Reduce the size of the mempool by expiring and then trimming the mempool. */ void LimitSize(CCoinsViewCache &coins_cache, size_t limit, std::chrono::seconds age) EXCLUSIVE_LOCKS_REQUIRED(cs, ::cs_main); /** @returns true if the mempool is fully loaded */ bool IsLoaded() const; /** Sets the current loaded state */ 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 infoAll() const; CFeeRate estimateFee() const; size_t DynamicMemoryUsage() const; /** Adds a transaction to the unbroadcast set */ 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); } } /** Removes a transaction from the unbroadcast set */ void RemoveUnbroadcastTx(const TxId &txid, const bool unchecked = false); /** Returns transactions in unbroadcast set */ std::set GetUnbroadcastTxs() const { LOCK(cs); return m_unbroadcast_txids; } /** Returns whether a txid is in the unbroadcast set */ bool IsUnbroadcastTx(const TxId &txid) const EXCLUSIVE_LOCKS_REQUIRED(cs) { AssertLockHeld(cs); return (m_unbroadcast_txids.count(txid) != 0); } /** Guards this internal counter for external reporting */ 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: /** Set ancestor state for an entry */ void UpdateEntryForAncestors(txiter it, const setEntries *setAncestors) EXCLUSIVE_LOCKS_REQUIRED(cs); /** * Update parents of `it` to add/remove it as a child transaction. */ void UpdateParentsOf(bool add, txiter it) EXCLUSIVE_LOCKS_REQUIRED(cs); /** * For each transaction being removed, update ancestors and any direct * children. If updateDescendants is true, then also update in-mempool * descendants' ancestor state. Note that ancestors are only updated before * wellington activation. */ void UpdateForRemoveFromMempool(const setEntries &entriesToRemove, bool updateDescendants) EXCLUSIVE_LOCKS_REQUIRED(cs); /** Sever link between specified transaction and direct children. */ void UpdateChildrenForRemoval(txiter entry) EXCLUSIVE_LOCKS_REQUIRED(cs); /** * Before calling removeUnchecked for a given transaction, * UpdateForRemoveFromMempool must be called on the entire (dependent) set * of transactions being removed at the same time. We use each * CTxMemPoolEntry's setMemPoolParents in order to walk ancestors of a given * transaction that is removed, so we can't remove intermediate transactions * in a chain before we've updated all the state for the removal. */ void removeUnchecked(txiter entry, MemPoolRemovalReason reason) EXCLUSIVE_LOCKS_REQUIRED(cs); }; /** * CCoinsView that brings transactions from a mempool into view. * It does not check for spendings by memory pool transactions. * Instead, it provides access to all Coins which are either unspent in the * base CCoinsView, are outputs from any mempool transaction, or are * tracked temporarily to allow transaction dependencies in package validation. * This allows transaction replacement to work as expected, as you want to * have all inputs "available" to check signatures, and any cycles in the * dependency graph are checked directly in AcceptToMemoryPool. * It also allows you to sign a double-spend directly in * signrawtransactionwithkey and signrawtransactionwithwallet, * as long as the conflicting transaction is not yet confirmed. */ class CCoinsViewMemPool : public CCoinsViewBacked { /** * Coins made available by transactions being validated. Tracking these * allows for package validation, since we can access transaction outputs * without submitting them to mempool. */ std::unordered_map m_temp_added; protected: const CTxMemPool &mempool; public: CCoinsViewMemPool(CCoinsView *baseIn, const CTxMemPool &mempoolIn); bool GetCoin(const COutPoint &outpoint, Coin &coin) const override; /** * Add the coins created by this transaction. These coins are only * temporarily stored in m_temp_added and cannot be flushed to the back end. * Only used for package validation. */ void PackageAddTransaction(const CTransactionRef &tx); }; /** * DisconnectedBlockTransactions * * During the reorg, it's desirable to re-add previously confirmed transactions * to the mempool, so that anything not re-confirmed in the new chain is * available to be mined. However, it's more efficient to wait until the reorg * is complete and process all still-unconfirmed transactions at that time, * since we expect most confirmed transactions to (typically) still be * confirmed in the new chain, and re-accepting to the memory pool is expensive * (and therefore better to not do in the middle of reorg-processing). * Instead, store the disconnected transactions (in order!) as we go, remove any * that are included in blocks in the new chain, and then process the remaining * still-unconfirmed transactions at the end. * * It also enables efficient reprocessing of current mempool entries, useful * when (de)activating forks that result in in-mempool transactions becoming * invalid */ // 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, mempoolentry_txid, SaltedTxIdHasher>, // sorted by order in the blockchain boost::multi_index::sequenced< boost::multi_index::tag>>> 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; /// populated by importMempool(); the original tx entry times and feeDeltas TxInfoMap txInfo; void addTransaction(const CTransactionRef &tx) { queuedTx.insert(tx); cachedInnerUsage += RecursiveDynamicUsage(tx); } /// @returns a pointer into the txInfo map if tx->GetId() exists in the map, /// or nullptr otherwise. Note that the returned pointer is only valid for /// as long as its underlying map node is valid. 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 &vtx, CTxMemPool &pool) EXCLUSIVE_LOCKS_REQUIRED(pool.cs); // Remove entries based on txid_index, and update memory usage. void removeForBlock(const std::vector &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().erase(entry); } bool isEmpty() const { return queuedTx.empty(); } void clear() { cachedInnerUsage = 0; queuedTx.clear(); txInfo.clear(); } /** * Make mempool consistent after a reorg, by re-adding or recursively * erasing disconnected block transactions from the mempool, and also * removing any other transactions from the mempool that are no longer valid * given the new tip/height. * * Note: we assume that disconnectpool only contains transactions that are * NOT confirmed in the current chain nor already in the mempool (otherwise, * in-mempool descendants of such transactions would be removed). * * Passing fAddToMempool=false will skip trying to add the transactions * back, and instead just erase from the mempool as needed. */ void updateMempoolForReorg(const Config &config, Chainstate &active_chainstate, bool fAddToMempool, CTxMemPool &pool) EXCLUSIVE_LOCKS_REQUIRED(cs_main, pool.cs); }; #endif // BITCOIN_TXMEMPOOL_H