git / moonbite-core / src/txmempool.cpp · raw
// Copyright (c) 2009-2010 Satoshi Nakamoto// Copyright (c) 2009-2020 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 <txmempool.h>#include <consensus/consensus.h>#include <consensus/tx_verify.h>#include <consensus/validation.h>#include <optional.h>#include <validation.h>#include <policy/policy.h>#include <policy/fees.h>#include <policy/settings.h>#include <reverse_iterator.h>#include <util/system.h>#include <util/moneystr.h>#include <util/time.h>#include <validationinterface.h>CTxMemPoolEntry::CTxMemPoolEntry(const CTransactionRef& _tx, const CAmount& _nFee, int64_t _nTime, unsigned int _entryHeight, bool _spendsCoinbase, int64_t _sigOpsCost, LockPoints lp) : tx(_tx), nFee(_nFee), nTxWeight(GetTransactionWeight(*tx)), mweb_weight(tx->mweb_tx.GetMWEBWeight()), nUsageSize(RecursiveDynamicUsage(tx)), nTime(_nTime), entryHeight(_entryHeight), spendsCoinbase(_spendsCoinbase), sigOpCost(_sigOpsCost), lockPoints(lp), m_epoch(0){ nCountWithDescendants = 1; nSizeWithDescendants = GetTxSize(); nModFeesWithDescendants = nFee; nMWEBWeightWithDescendants = mweb_weight; feeDelta = 0; nCountWithAncestors = 1; nSizeWithAncestors = GetTxSize(); nModFeesWithAncestors = nFee; nSigOpCostWithAncestors = sigOpCost; nMWEBWeightWithAncestors = mweb_weight;}void CTxMemPoolEntry::UpdateFeeDelta(int64_t newFeeDelta){ nModFeesWithDescendants += newFeeDelta - feeDelta; nModFeesWithAncestors += newFeeDelta - feeDelta; feeDelta = newFeeDelta;}void CTxMemPoolEntry::UpdateLockPoints(const LockPoints& lp){ lockPoints = lp;}size_t CTxMemPoolEntry::GetTxSize() const{ return GetVirtualTransactionSize(nTxWeight, sigOpCost);}// Update the given tx for any in-mempool descendants.// Assumes that CTxMemPool::m_children is correct for the given tx and all// descendants.void CTxMemPool::UpdateForDescendants(txiter updateIt, cacheMap &cachedDescendants, const std::set<uint256> &setExclude){ CTxMemPoolEntry::Children stageEntries, descendants; stageEntries = updateIt->GetMemPoolChildrenConst(); while (!stageEntries.empty()) { const CTxMemPoolEntry& descendant = *stageEntries.begin(); descendants.insert(descendant); stageEntries.erase(descendant); const CTxMemPoolEntry::Children& children = descendant.GetMemPoolChildrenConst(); for (const CTxMemPoolEntry& childEntry : children) { cacheMap::iterator cacheIt = cachedDescendants.find(mapTx.iterator_to(childEntry)); if (cacheIt != cachedDescendants.end()) { // We've already calculated this one, just add the entries for this set // but don't traverse again. for (txiter cacheEntry : cacheIt->second) { descendants.insert(*cacheEntry); } } else if (!descendants.count(childEntry)) { // Schedule for later processing stageEntries.insert(childEntry); } } } // descendants now contains all in-mempool descendants of updateIt. // Update and add to cached descendant map int64_t modifySize = 0; CAmount modifyFee = 0; int64_t modifyCount = 0; int64_t modifyMWEBWeight = 0; for (const CTxMemPoolEntry& descendant : descendants) { if (!setExclude.count(descendant.GetTx().GetHash())) { modifySize += descendant.GetTxSize(); modifyFee += descendant.GetModifiedFee(); modifyMWEBWeight += descendant.GetMWEBWeight(); modifyCount++; cachedDescendants[updateIt].insert(mapTx.iterator_to(descendant)); // Update ancestor state for each descendant mapTx.modify(mapTx.iterator_to(descendant), update_ancestor_state(updateIt->GetTxSize(), updateIt->GetModifiedFee(), 1, updateIt->GetSigOpCost(), updateIt->GetMWEBWeight())); } } mapTx.modify(updateIt, update_descendant_state(modifySize, modifyFee, modifyCount, modifyMWEBWeight));}// vHashesToUpdate is the set of transaction hashes from a disconnected block// which has been re-added to the mempool.// for each entry, look for descendants that are outside vHashesToUpdate, and// add fee/size information for such descendants to the parent.// for each such descendant, also update the ancestor state to include the parent.void CTxMemPool::UpdateTransactionsFromBlock(const std::vector<uint256> &vHashesToUpdate){ AssertLockHeld(cs); // For each entry in vHashesToUpdate, store the set of in-mempool, but not // in-vHashesToUpdate transactions, so that we don't have to recalculate // descendants when we come across a previously seen entry. cacheMap mapMemPoolDescendantsToUpdate; // Use a set for lookups into vHashesToUpdate (these entries are already // accounted for in the state of their ancestors) std::set<uint256> setAlreadyIncluded(vHashesToUpdate.begin(), vHashesToUpdate.end()); // Iterate in reverse, so that whenever we are looking at a transaction // we are sure that all in-mempool descendants have already been processed. // This maximizes the benefit of the descendant cache and guarantees that // CTxMemPool::m_children will be updated, an assumption made in // UpdateForDescendants. for (const uint256 &hash : reverse_iterate(vHashesToUpdate)) { // calculate children from mapNextTx txiter it = mapTx.find(hash); if (it == mapTx.end()) { continue; } // First calculate the children, and update CTxMemPool::m_children to // include them, and update their CTxMemPoolEntry::m_parents to include this tx. // we cache the in-mempool children to avoid duplicate updates { const auto epoch = GetFreshEpoch(); for (const CTxOutput& output : it->GetTx().GetOutputs()) { auto iter = mapNextTx.find(output.GetIndex()); if (iter != mapNextTx.end()) { const uint256& childHash = iter->second->GetHash(); txiter childIter = mapTx.find(childHash); assert(childIter != mapTx.end()); // We can skip updating entries we've encountered before or that // are in the block (which are already accounted for). if (!visited(childIter) && !setAlreadyIncluded.count(childHash)) { UpdateChild(it, childIter, true); UpdateParent(childIter, it, true); } } } } // release epoch guard for UpdateForDescendants UpdateForDescendants(it, mapMemPoolDescendantsToUpdate, setAlreadyIncluded); }}bool CTxMemPool::CalculateMemPoolAncestors(const CTxMemPoolEntry &entry, setEntries &setAncestors, uint64_t limitAncestorCount, uint64_t limitAncestorSize, uint64_t limitDescendantCount, uint64_t limitDescendantSize, std::string &errString, bool fSearchForParents /* = true */) const{ 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 CTxInput& txin : tx.GetInputs()) { Optional<txiter> piter = GetIter(txin); if (piter) { staged_ancestors.insert(**piter); if (staged_ancestors.size() + 1 > limitAncestorCount) { errString = strprintf("too many unconfirmed parents [limit: %u]", limitAncestorCount); return false; } } } } else { // If we're not searching for parents, we require this to be an // entry in the mempool already. txiter it = mapTx.iterator_to(entry); staged_ancestors = it->GetMemPoolParentsConst(); } size_t totalSizeWithAncestors = entry.GetTxSize(); while (!staged_ancestors.empty()) { const CTxMemPoolEntry& stage = staged_ancestors.begin()->get(); txiter stageit = mapTx.iterator_to(stage); setAncestors.insert(stageit); staged_ancestors.erase(stage); totalSizeWithAncestors += stageit->GetTxSize(); if (stageit->GetSizeWithDescendants() + entry.GetTxSize() > limitDescendantSize) { errString = strprintf("exceeds descendant size limit for tx %s [limit: %u]", stageit->GetTx().GetHash().ToString(), limitDescendantSize); return false; } else if (stageit->GetCountWithDescendants() + 1 > limitDescendantCount) { errString = strprintf("too many descendants for tx %s [limit: %u]", stageit->GetTx().GetHash().ToString(), limitDescendantCount); return false; } else if (totalSizeWithAncestors > limitAncestorSize) { errString = strprintf("exceeds ancestor size limit [limit: %u]", limitAncestorSize); return false; } 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); } if (staged_ancestors.size() + setAncestors.size() + 1 > limitAncestorCount) { errString = strprintf("too many unconfirmed ancestors [limit: %u]", limitAncestorCount); return false; } } } return true;}void CTxMemPool::UpdateAncestorsOf(bool add, txiter it, setEntries &setAncestors){ CTxMemPoolEntry::Parents parents = it->GetMemPoolParents(); // add or remove this tx as a child of each parent for (const CTxMemPoolEntry& parent : parents) { UpdateChild(mapTx.iterator_to(parent), it, add); } const int64_t updateCount = (add ? 1 : -1); const int64_t updateSize = updateCount * it->GetTxSize(); const CAmount updateFee = updateCount * it->GetModifiedFee(); const int64_t updateMWEBWeight = updateCount * it->GetMWEBWeight(); for (txiter ancestorIt : setAncestors) { mapTx.modify(ancestorIt, update_descendant_state(updateSize, updateFee, updateCount, updateMWEBWeight)); }}void CTxMemPool::UpdateEntryForAncestors(txiter it, const setEntries &setAncestors){ int64_t updateCount = setAncestors.size(); int64_t updateSize = 0; CAmount updateFee = 0; int64_t updateSigOpsCost = 0; int64_t updateMWEBWeight = 0; for (txiter ancestorIt : setAncestors) { updateSize += ancestorIt->GetTxSize(); updateFee += ancestorIt->GetModifiedFee(); updateSigOpsCost += ancestorIt->GetSigOpCost(); updateMWEBWeight += ancestorIt->GetMWEBWeight(); } mapTx.modify(it, update_ancestor_state(updateSize, updateFee, updateCount, updateSigOpsCost, updateMWEBWeight));}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 each entry, walk back all ancestors and decrement size associated with this // transaction const uint64_t nNoLimit = std::numeric_limits<uint64_t>::max(); if (updateDescendants) { // updateDescendants should be true whenever we're not recursively // removing a tx and all its descendants, eg when a transaction is // confirmed in a block. // Here we only update statistics and not data in CTxMemPool::Parents // and CTxMemPoolEntry::Children (which we need to preserve until we're // finished with all operations that need to traverse the mempool). for (txiter removeIt : entriesToRemove) { setEntries setDescendants; CalculateDescendants(removeIt, setDescendants); setDescendants.erase(removeIt); // don't update state for self int64_t modifySize = -((int64_t)removeIt->GetTxSize()); CAmount modifyFee = -removeIt->GetModifiedFee(); int modifySigOps = -removeIt->GetSigOpCost(); int64_t modifyMWEBWeight = -((int64_t)removeIt->GetMWEBWeight()); for (txiter dit : setDescendants) { mapTx.modify(dit, update_ancestor_state(modifySize, modifyFee, -1, modifySigOps, modifyMWEBWeight)); } } } for (txiter removeIt : entriesToRemove) { setEntries setAncestors; const CTxMemPoolEntry &entry = *removeIt; std::string dummy; // Since this is a tx that is already in the mempool, we can call CMPA // with fSearchForParents = false. If the mempool is in a consistent // state, then using true or false should both be correct, though false // should be a bit faster. // However, if we happen to be in the middle of processing a reorg, then // the mempool can be in an inconsistent state. In this case, the set // of ancestors reachable via GetMemPoolParents()/GetMemPoolChildren() // will be the same as the set of ancestors whose packages include this // transaction, because when we add a new transaction to the mempool in // addUnchecked(), we assume it has no children, and in the case of a // reorg where that assumption is false, the in-mempool children aren't // linked to the in-block tx's until UpdateTransactionsFromBlock() is // called. // So if we're being called during a reorg, ie before // UpdateTransactionsFromBlock() has been called, then // GetMemPoolParents()/GetMemPoolChildren() will differ from the set of // mempool parents we'd calculate by searching, and it's important that // we use the cached notion of ancestor transactions as the set of // things to update for removal. CalculateMemPoolAncestors(entry, setAncestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy, false); // Note that UpdateAncestorsOf severs the child links that point to // removeIt in the entries for the parents of removeIt. UpdateAncestorsOf(false, removeIt, setAncestors); } // After updating all the ancestor sizes, 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, CAmount modifyFee, int64_t modifyCount, int64_t modifyMWEBWeight){ nSizeWithDescendants += modifySize; assert(int64_t(nSizeWithDescendants) >= 0); nModFeesWithDescendants += modifyFee; nCountWithDescendants += modifyCount; assert(int64_t(nCountWithDescendants) > 0); nMWEBWeightWithDescendants += modifyMWEBWeight; assert(int64_t(nMWEBWeightWithDescendants) >= 0);}void CTxMemPoolEntry::UpdateAncestorState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount, int64_t modifySigOps, int64_t modifyMWEBWeight){ nSizeWithAncestors += modifySize; assert(int64_t(nSizeWithAncestors) >= 0); nModFeesWithAncestors += modifyFee; nCountWithAncestors += modifyCount; assert(int64_t(nCountWithAncestors) > 0); nSigOpCostWithAncestors += modifySigOps; assert(int(nSigOpCostWithAncestors) >= 0); nMWEBWeightWithAncestors += modifyMWEBWeight; assert(int64_t(nMWEBWeightWithAncestors) >= 0);}CTxMemPool::CTxMemPool(CBlockPolicyEstimator* estimator) : nTransactionsUpdated(0), minerPolicyEstimator(estimator), m_epoch(0), m_has_epoch_guard(false){ _clear(); //lock free clear // Sanity checks off by default for performance, because otherwise // accepting transactions becomes O(N^2) where N is the number // of transactions in the pool nCheckFrequency = 0;}bool CTxMemPool::isSpent(const OutputIndex& 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 &entry, setEntries &setAncestors, bool validFeeEstimate){ // Add to memory pool without checking anything. // Used by AcceptToMemoryPool(), which DOES do // all the appropriate checks. indexed_transaction_set::iterator newit = mapTx.insert(entry).first; // Update transaction for any feeDelta created by PrioritiseTransaction // TODO: refactor so that the fee delta is calculated before inserting // into mapTx. CAmount delta{0}; ApplyDelta(entry.GetTx().GetHash(), delta); if (delta) { mapTx.modify(newit, update_fee_delta(delta)); } // 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<uint256> setParentTransactions; for (const CTxInput& input : tx.GetInputs()) { mapNextTx.insert(std::make_pair(input.GetIndex(), &tx)); if (input.IsMWEB()) { auto parentIter = mapTxOutputs_MWEB.find(input.ToMWEB()); if (parentIter != mapTxOutputs_MWEB.end()) { setParentTransactions.insert(parentIter->second->GetHash()); } } else { setParentTransactions.insert(input.GetTxIn().prevout.hash); } } // MWEB: Add transaction to mapTxOutputs_MWEB for each output for (const mw::Hash& output_id : tx.mweb_tx.GetOutputIDs()) { mapTxOutputs_MWEB.insert(std::make_pair(output_id, &tx)); } // Don't bother worrying about child transactions of this one. // Normal case of a new transaction arriving is that there can't be any // children, because such children would be orphans. // An exception to that is if a transaction enters that used to be in a block. // In that case, our disconnect block logic will call UpdateTransactionsFromBlock // to clean up the mess we're leaving here. // Update ancestors with information about this tx for (const auto& pit : GetIterSet(setParentTransactions)) { UpdateParent(newit, pit, true); } UpdateAncestorsOf(true, newit, setAncestors); UpdateEntryForAncestors(newit, setAncestors); nTransactionsUpdated++; totalTxSize += entry.GetTxSize(); if (minerPolicyEstimator) {minerPolicyEstimator->processTransaction(entry, validFeeEstimate);} vTxHashes.emplace_back(tx.GetWitnessHash(), newit); newit->vTxHashesIdx = vTxHashes.size() - 1;}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); } CTransactionRef ptx = it->GetSharedTx(); const uint256 hash = ptx->GetHash(); for (const CTxInput& txin : ptx->GetInputs()) mapNextTx.erase(txin.GetIndex()); // MWEB: Remove transaction from mapTxOutputs_MWEB for each output for (const mw::Hash& output_id : ptx->mweb_tx.GetOutputIDs()) { mapTxOutputs_MWEB.erase(output_id); } // MWEB: When removing MWEB transactions from the mempool after a block is connected, // cache the original tx in recentTxsByKernel, in case we need to replay it during a reorg. if (reason == MemPoolRemovalReason::BLOCK || reason == MemPoolRemovalReason::REORG) { for (const mw::Hash& kernel_id : ptx->mweb_tx.GetKernelIDs()) { recentTxsByKernel.Put(kernel_id, ptx); } } RemoveUnbroadcastTx(hash, true /* add logging because unchecked */ ); if (vTxHashes.size() > 1) { vTxHashes[it->vTxHashesIdx] = std::move(vTxHashes.back()); vTxHashes[it->vTxHashesIdx].second->vTxHashesIdx = it->vTxHashesIdx; vTxHashes.pop_back(); if (vTxHashes.size() * 2 < vTxHashes.capacity()) vTxHashes.shrink_to_fit(); } else vTxHashes.clear(); totalTxSize -= it->GetTxSize(); cachedInnerUsage -= it->DynamicMemoryUsage(); cachedInnerUsage -= memusage::DynamicUsage(it->GetMemPoolParentsConst()) + memusage::DynamicUsage(it->GetMemPoolChildrenConst()); mapTx.erase(it); nTransactionsUpdated++; if (minerPolicyEstimator) {minerPolicyEstimator->removeTx(hash, false);}}// 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(it); 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.GetHash()); 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. for (const CTxOutput& output : origTx.GetOutputs()) { auto it = mapNextTx.find(output.GetIndex()); if (it == mapNextTx.end()) continue; txiter nextit = mapTx.find(it->second->GetHash()); assert(nextit != mapTx.end()); txToRemove.insert(nextit); } } setEntries setAllRemoves; for (txiter it : txToRemove) { CalculateDescendants(it, setAllRemoves); } RemoveStaged(setAllRemoves, false, reason);}void CTxMemPool::removeForReorg(const CCoinsViewCache *pcoins, unsigned int nMemPoolHeight, int flags){ // Remove transactions spending a coinbase which are now immature and no-longer-final transactions AssertLockHeld(cs); setEntries txToRemove; for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) { const CTransaction& tx = it->GetTx(); LockPoints lp = it->GetLockPoints(); bool validLP = TestLockPointValidity(&lp); if (!CheckFinalTx(tx, flags) || !CheckSequenceLocks(*this, tx, flags, &lp, validLP)) { // Note if CheckSequenceLocks fails the LockPoints may still be invalid // So it's critical that we remove the tx and not depend on the LockPoints. txToRemove.insert(it); } else if (it->GetSpendsCoinbase()) { for (const CTxIn& txin : tx.vin) { indexed_transaction_set::const_iterator it2 = mapTx.find(txin.prevout.hash); if (it2 != mapTx.end()) continue; const Coin &coin = pcoins->AccessCoin(txin.prevout); if (nCheckFrequency != 0) assert(!coin.IsSpent()); if (coin.IsSpent() || (coin.IsCoinBase() && ((signed long)nMemPoolHeight) - coin.nHeight < COINBASE_MATURITY)) { txToRemove.insert(it); break; } // MWEB: Remove pegout if immature if (coin.IsPegout() && ((signed long)nMemPoolHeight) - coin.nHeight < PEGOUT_MATURITY) { txToRemove.insert(it); break; } } } if (!validLP) { mapTx.modify(it, update_lock_points(lp)); } } setEntries setAllRemoves; for (txiter it : txToRemove) { CalculateDescendants(it, setAllRemoves); } RemoveStaged(setAllRemoves, false, MemPoolRemovalReason::REORG);}void CTxMemPool::removeConflicts(const CTransaction &tx){ // Remove transactions which depend on inputs of tx, recursively AssertLockHeld(cs); for (const CTxInput& input : tx.GetInputs()) { auto it = mapNextTx.find(input.GetIndex()); if (it != mapNextTx.end()) { const CTransaction &txConflict = *it->second; if (txConflict != tx) { ClearPrioritisation(txConflict.GetHash()); removeRecursive(txConflict, MemPoolRemovalReason::CONFLICT); } } }}/** * Called when a block is connected. Removes from mempool and updates the miner fee estimator. */void CTxMemPool::removeForBlock(const CBlock& block, unsigned int nBlockHeight, DisconnectedBlockTransactions* disconnectpool){ AssertLockHeld(cs); std::vector<const CTxMemPoolEntry*> entries; for (const auto& tx : block.vtx) { indexed_transaction_set::iterator i = mapTx.find(tx->GetHash()); if (i != mapTx.end()) entries.push_back(&*i); } // MWEB: Check for transactions with kernels included in the block. // If we add a map of txs by kernel hash in the future, this can be made more efficient. std::vector<CTransactionRef> txs = block.vtx; if (!block.mweb_block.IsNull()) { auto block_kernels = block.mweb_block.GetKernelIDs(); for (txiter it = mapTx.begin(); it != mapTx.end(); ++it) { CTransactionRef ptx = it->GetSharedTx(); if (!ptx->HasMWEBTx()) continue; const auto& tx_kernels = ptx->mweb_tx.GetKernelIDs(); bool remove_tx = std::any_of(tx_kernels.begin(), tx_kernels.end(), [&block_kernels](const mw::Hash& kernel_id) { return block_kernels.count(kernel_id) != 0; } ); if (remove_tx) { entries.push_back(&*it); txs.push_back(ptx); } } } // Before the txs in the new block have been removed from the mempool, update policy estimates if (minerPolicyEstimator) {minerPolicyEstimator->processBlock(nBlockHeight, entries);} for (const auto& tx : txs) { txiter it = mapTx.find(tx->GetHash()); if (it != mapTx.end()) { setEntries stage; stage.insert(it); RemoveStaged(stage, true, MemPoolRemovalReason::BLOCK); } removeConflicts(*tx); ClearPrioritisation(tx->GetHash()); } lastRollingFeeUpdate = GetTime(); blockSinceLastRollingFeeBump = true; if (disconnectpool) { disconnectpool->removeForBlock(txs); }}void CTxMemPool::_clear(){ mapTx.clear(); mapNextTx.clear(); mapTxOutputs_MWEB.clear(); totalTxSize = 0; cachedInnerUsage = 0; lastRollingFeeUpdate = GetTime(); blockSinceLastRollingFeeBump = false; rollingMinimumFeeRate = 0; ++nTransactionsUpdated;}void CTxMemPool::clear(){ LOCK(cs); _clear();}static void CheckInputsAndUpdateCoins(const CTransaction& tx, CCoinsViewCache& mempoolDuplicate, const int64_t spendheight){ TxValidationState dummy_state; // Not used. CheckTxInputs() should always pass CAmount txfee = 0; bool fCheckResult = tx.IsCoinBase() || Consensus::CheckTxInputs(tx, dummy_state, mempoolDuplicate, spendheight, txfee); assert(fCheckResult); UpdateCoins(tx, mempoolDuplicate, std::numeric_limits<int>::max());}void CTxMemPool::check(const CCoinsViewCache *pcoins) const{ LOCK(cs); if (nCheckFrequency == 0) return; if (GetRand(std::numeric_limits<uint32_t>::max()) >= nCheckFrequency) return; LogPrint(BCLog::MEMPOOL, "Checking mempool with %u transactions and %u inputs\n", (unsigned int)mapTx.size(), (unsigned int)mapNextTx.size()); uint64_t checkTotal = 0; uint64_t innerUsage = 0; CCoinsViewCache mempoolDuplicate(const_cast<CCoinsViewCache*>(pcoins)); const int64_t spendheight = GetSpendHeight(mempoolDuplicate); std::list<const CTxMemPoolEntry*> waitingOnDependants; for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) { unsigned int i = 0; checkTotal += it->GetTxSize(); innerUsage += it->DynamicMemoryUsage(); const CTransaction& tx = it->GetTx(); innerUsage += memusage::DynamicUsage(it->GetMemPoolParentsConst()) + memusage::DynamicUsage(it->GetMemPoolChildrenConst()); bool fDependsWait = false; CTxMemPoolEntry::Parents setParentCheck; for (const CTxInput& input : tx.GetInputs()) { // Check that every mempool transaction's inputs refer to available coins, or other mempool tx's. auto opt_it2 = GetIter(input); if (opt_it2) { auto it2 = *opt_it2; //const CTransaction& tx2 = it2->GetTx(); //assert(tx2.vout.size() > txin.prevout.n && !tx2.vout[txin.prevout.n].IsNull()); // MW: TODO - fDependsWait = true; setParentCheck.insert(*it2); } else { assert(pcoins->HaveCoin(input.GetIndex())); } // Check whether its inputs are marked in mapNextTx. auto it3 = mapNextTx.find(input.GetIndex()); assert(it3 != mapNextTx.end()); assert(it3->first == input.GetIndex()); assert(it3->second == &tx); i++; } auto comp = [](const CTxMemPoolEntry& a, const CTxMemPoolEntry& b) -> bool { return a.GetTx().GetHash() == b.GetTx().GetHash(); }; assert(setParentCheck.size() == it->GetMemPoolParentsConst().size()); assert(std::equal(setParentCheck.begin(), setParentCheck.end(), it->GetMemPoolParentsConst().begin(), comp)); // Verify ancestor state is correct. setEntries setAncestors; uint64_t nNoLimit = std::numeric_limits<uint64_t>::max(); std::string dummy; CalculateMemPoolAncestors(*it, setAncestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy); uint64_t nCountCheck = setAncestors.size() + 1; uint64_t nSizeCheck = it->GetTxSize(); CAmount nFeesCheck = it->GetModifiedFee(); int64_t nSigOpCheck = it->GetSigOpCost(); uint64_t nMWEBWeightCheck = it->GetMWEBWeight(); for (txiter ancestorIt : setAncestors) { nSizeCheck += ancestorIt->GetTxSize(); nFeesCheck += ancestorIt->GetModifiedFee(); nSigOpCheck += ancestorIt->GetSigOpCost(); nMWEBWeightCheck += ancestorIt->GetMWEBWeight(); } assert(it->GetCountWithAncestors() == nCountCheck); assert(it->GetSizeWithAncestors() == nSizeCheck); assert(it->GetSigOpCostWithAncestors() == nSigOpCheck); assert(it->GetModFeesWithAncestors() == nFeesCheck); assert(it->GetMWEBWeightWithAncestors() == nMWEBWeightCheck); // Check children against mapNextTx CTxMemPoolEntry::Children setChildrenCheck; uint64_t child_sizes = 0; uint64_t child_mweb_weights = 0; for (const CTxOutput& output : it->GetTx().GetOutputs()) { auto iter = mapNextTx.find(output.GetIndex()); if (iter != mapNextTx.end()) { txiter childit = mapTx.find(iter->second->GetHash()); assert(childit != mapTx.end()); // mapNextTx points to in-mempool transactions if (setChildrenCheck.insert(*childit).second) { child_sizes += childit->GetTxSize(); child_mweb_weights += childit->GetMWEBWeight(); } } } assert(setChildrenCheck.size() == it->GetMemPoolChildrenConst().size()); assert(std::equal(setChildrenCheck.begin(), setChildrenCheck.end(), it->GetMemPoolChildrenConst().begin(), comp)); // Also check to make sure size is greater than sum with immediate children. // just a sanity check, not definitive that this calc is correct... assert(it->GetSizeWithDescendants() >= child_sizes + it->GetTxSize()); assert(it->GetMWEBWeightWithDescendants() >= child_mweb_weights + it->GetMWEBWeight()); if (fDependsWait) waitingOnDependants.push_back(&(*it)); else { CheckInputsAndUpdateCoins(tx, mempoolDuplicate, spendheight); } } unsigned int stepsSinceLastRemove = 0; while (!waitingOnDependants.empty()) { const CTxMemPoolEntry* entry = waitingOnDependants.front(); waitingOnDependants.pop_front(); if (!mempoolDuplicate.HaveInputs(entry->GetTx())) { waitingOnDependants.push_back(entry); stepsSinceLastRemove++; assert(stepsSinceLastRemove < waitingOnDependants.size()); } else { CheckInputsAndUpdateCoins(entry->GetTx(), mempoolDuplicate, spendheight); stepsSinceLastRemove = 0; } } for (auto it = mapNextTx.cbegin(); it != mapNextTx.cend(); it++) { uint256 hash = it->second->GetHash(); indexed_transaction_set::const_iterator it2 = mapTx.find(hash); const CTransaction& tx = it2->GetTx(); assert(it2 != mapTx.end()); assert(&tx == it->second); } assert(totalTxSize == checkTotal); assert(innerUsage == cachedInnerUsage);}bool CTxMemPool::CompareDepthAndScore(const uint256& hasha, const uint256& hashb, bool wtxid){ /* Return `true` if hasha should be considered sooner than hashb. Namely when: * a is not in the mempool, but b is * both are in the mempool and a has fewer ancestors than b * both are in the mempool and a has a higher score than b */ LOCK(cs); indexed_transaction_set::const_iterator j = wtxid ? get_iter_from_wtxid(hashb) : mapTx.find(hashb); if (j == mapTx.end()) return false; indexed_transaction_set::const_iterator i = wtxid ? get_iter_from_wtxid(hasha) : mapTx.find(hasha); if (i == mapTx.end()) return true; uint64_t counta = i->GetCountWithAncestors(); uint64_t countb = j->GetCountWithAncestors(); if (counta == countb) { return CompareTxMemPoolEntryByScore()(*i, *j); } return counta < countb;}namespace {class DepthAndScoreComparator{public: bool operator()(const CTxMemPool::indexed_transaction_set::const_iterator& a, const CTxMemPool::indexed_transaction_set::const_iterator& b) { uint64_t counta = a->GetCountWithAncestors(); uint64_t countb = b->GetCountWithAncestors(); if (counta == countb) { return CompareTxMemPoolEntryByScore()(*a, *b); } return counta < countb; }};} // namespacestd::vector<CTxMemPool::indexed_transaction_set::const_iterator> CTxMemPool::GetSortedDepthAndScore() const{ std::vector<indexed_transaction_set::const_iterator> iters; AssertLockHeld(cs); iters.reserve(mapTx.size()); for (indexed_transaction_set::iterator mi = mapTx.begin(); mi != mapTx.end(); ++mi) { iters.push_back(mi); } std::sort(iters.begin(), iters.end(), DepthAndScoreComparator()); return iters;}void CTxMemPool::queryHashes(std::vector<uint256>& vtxid) const{ LOCK(cs); auto iters = GetSortedDepthAndScore(); vtxid.clear(); vtxid.reserve(mapTx.size()); for (auto it : iters) { vtxid.push_back(it->GetTx().GetHash()); }}static TxMempoolInfo GetInfo(CTxMemPool::indexed_transaction_set::const_iterator it) { return TxMempoolInfo{it->GetSharedTx(), it->GetTime(), it->GetFee(), it->GetTxSize(), it->GetMWEBWeight(), it->GetModifiedFee() - it->GetFee()};}std::vector<TxMempoolInfo> CTxMemPool::infoAll() const{ LOCK(cs); auto iters = GetSortedDepthAndScore(); std::vector<TxMempoolInfo> ret; ret.reserve(mapTx.size()); for (auto it : iters) { ret.push_back(GetInfo(it)); } return ret;}CTransactionRef CTxMemPool::get(const uint256& hash) const{ LOCK(cs); indexed_transaction_set::const_iterator i = mapTx.find(hash); if (i == mapTx.end()) return nullptr; return i->GetSharedTx();}TxMempoolInfo CTxMemPool::info(const GenTxid& gtxid) const{ LOCK(cs); indexed_transaction_set::const_iterator i = (gtxid.IsWtxid() ? get_iter_from_wtxid(gtxid.GetHash()) : mapTx.find(gtxid.GetHash())); if (i == mapTx.end()) return TxMempoolInfo(); return GetInfo(i);}TxMempoolInfo CTxMemPool::info(const uint256& txid) const { return info(GenTxid{false, txid}); }void CTxMemPool::PrioritiseTransaction(const uint256& hash, const CAmount& nFeeDelta){ { LOCK(cs); CAmount &delta = mapDeltas[hash]; delta += nFeeDelta; txiter it = mapTx.find(hash); if (it != mapTx.end()) { mapTx.modify(it, update_fee_delta(delta)); // Now update all ancestors' modified fees with descendants setEntries setAncestors; uint64_t nNoLimit = std::numeric_limits<uint64_t>::max(); std::string dummy; CalculateMemPoolAncestors(*it, setAncestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy, false); for (txiter ancestorIt : setAncestors) { mapTx.modify(ancestorIt, update_descendant_state(0, nFeeDelta, 0, 0)); } // Now update all descendants' modified fees with ancestors setEntries setDescendants; CalculateDescendants(it, setDescendants); setDescendants.erase(it); for (txiter descendantIt : setDescendants) { mapTx.modify(descendantIt, update_ancestor_state(0, nFeeDelta, 0, 0, 0)); } ++nTransactionsUpdated; } } LogPrintf("PrioritiseTransaction: %s feerate += %s\n", hash.ToString(), FormatMoney(nFeeDelta));}void CTxMemPool::ApplyDelta(const uint256& hash, CAmount &nFeeDelta) const{ AssertLockHeld(cs); std::map<uint256, CAmount>::const_iterator pos = mapDeltas.find(hash); if (pos == mapDeltas.end()) return; const CAmount &delta = pos->second; nFeeDelta += delta;}void CTxMemPool::ClearPrioritisation(const uint256& hash){ AssertLockHeld(cs); mapDeltas.erase(hash);}const CTransaction* CTxMemPool::GetConflictTx(const OutputIndex& prevout) const{ const auto it = mapNextTx.find(prevout); return it == mapNextTx.end() ? nullptr : it->second;}Optional<CTxMemPool::txiter> CTxMemPool::GetIter(const uint256& txid) const{ auto it = mapTx.find(txid); if (it != mapTx.end()) return it; return Optional<txiter>{};}Optional<CTxMemPool::txiter> CTxMemPool::GetIter(const CTxInput& input) const{ if (input.IsMWEB()) { auto iter = mapTxOutputs_MWEB.find(input.ToMWEB()); if (iter != mapTxOutputs_MWEB.end()) { return GetIter(iter->second->GetHash()); } } else { return GetIter(input.GetTxIn().prevout.hash); } return Optional<txiter>{};}CTxMemPool::setEntries CTxMemPool::GetIterSet(const std::set<uint256>& hashes) const{ CTxMemPool::setEntries ret; for (const auto& h : hashes) { const auto mi = GetIter(h); if (mi) ret.insert(*mi); } return ret;}bool CTxMemPool::HasNoInputsOf(const CTransaction &tx) const{ for (const CTxInput& input : tx.GetInputs()) { if (input.IsMWEB()) { if (mapTxOutputs_MWEB.find(input.ToMWEB()) != mapTxOutputs_MWEB.end()) { return false; } } else if (exists(input.GetTxIn().prevout.hash)) { return false; } } return true;}CCoinsViewMemPool::CCoinsViewMemPool(CCoinsView* baseIn, const CTxMemPool& mempoolIn) : CCoinsViewBacked(baseIn), mempool(mempoolIn) { }bool CCoinsViewMemPool::GetCoin(const COutPoint &outpoint, Coin &coin) const { // 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.hash); if (ptx) { if (outpoint.n < ptx->vout.size()) { coin = Coin(ptx->vout[outpoint.n], MEMPOOL_HEIGHT, false, ptx->mweb_tx.HasPegOut()); return true; } else { return false; } } return base->GetCoin(outpoint, coin);}bool CCoinsViewMemPool::HaveCoin(const OutputIndex& index) const { if (index.type() == typeid(mw::Hash)) { if (mempool.mapNextTx.find(index) != mempool.mapNextTx.end()) { return false; } auto iter = mempool.mapTxOutputs_MWEB.find(boost::get<mw::Hash>(index)); if (iter != mempool.mapTxOutputs_MWEB.end()) { assert(mempool.mapTx.count(iter->second->GetHash()) > 0); return true; } return GetMWEBView()->HasCoin(boost::get<mw::Hash>(index)); } else { return base->HaveCoin(index); }}bool CCoinsViewMemPool::GetMWEBCoin(const mw::Hash& output_id, Output& coin) const{ if (mempool.mapNextTx.find(output_id) != mempool.mapNextTx.end()) { return false; } auto iter = mempool.mapTxOutputs_MWEB.find(output_id); if (iter != mempool.mapTxOutputs_MWEB.end()) { //assert(mempool.mapTx.count(iter->second->GetHash()) > 0); //assert(!iter->second->mweb_tx.IsNull()); return iter->second->mweb_tx.GetOutput(output_id, coin); } UTXO::CPtr pUTXO = GetMWEBView()->GetUTXO(output_id); if (pUTXO) { coin = pUTXO->GetOutput(); return true; } return false;}size_t CTxMemPool::DynamicMemoryUsage() const { LOCK(cs); // Estimate the overhead of mapTx to be 15 pointers + an allocation, as no exact formula for boost::multi_index_contained is implemented. return memusage::MallocUsage(sizeof(CTxMemPoolEntry) + 15 * sizeof(void*)) * mapTx.size() + memusage::DynamicUsage(mapNextTx) + memusage::DynamicUsage(mapTxOutputs_MWEB) + memusage::DynamicUsage(mapDeltas) + memusage::DynamicUsage(vTxHashes) + cachedInnerUsage;}void CTxMemPool::RemoveUnbroadcastTx(const uint256& 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(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<entry_time>::type::iterator it = mapTx.get<entry_time>().begin(); setEntries toremove; while (it != mapTx.get<entry_time>().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::addUnchecked(const CTxMemPoolEntry &entry, bool validFeeEstimate){ setEntries setAncestors; uint64_t nNoLimit = std::numeric_limits<uint64_t>::max(); std::string dummy; CalculateMemPoolAncestors(entry, setAncestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy); return addUnchecked(entry, setAncestors, validFeeEstimate);}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(llround(rollingMinimumFeeRate)); 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; if (rollingMinimumFeeRate < (double)incrementalRelayFee.GetFeePerK() / 2) { rollingMinimumFeeRate = 0; return CFeeRate(0); } } return std::max(CFeeRate(llround(rollingMinimumFeeRate)), incrementalRelayFee);}void CTxMemPool::trackPackageRemoved(const CFeeRate& rate) { AssertLockHeld(cs); if (rate.GetFeePerK() > rollingMinimumFeeRate) { rollingMinimumFeeRate = rate.GetFeePerK(); blockSinceLastRollingFeeBump = false; }}void CTxMemPool::TrimToSize(size_t sizelimit, std::vector<COutPoint>* pvNoSpendsRemaining) { AssertLockHeld(cs); unsigned nTxnRemoved = 0; CFeeRate maxFeeRateRemoved(0); while (!mapTx.empty() && DynamicMemoryUsage() > sizelimit) { indexed_transaction_set::index<descendant_score>::type::iterator it = mapTx.get<descendant_score>().begin(); // We set the new mempool min fee to the feerate of the removed set, 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->GetModFeesWithDescendants(), it->GetSizeWithDescendants(), it->GetMWEBWeightWithDescendants()); removed += incrementalRelayFee; trackPackageRemoved(removed); maxFeeRateRemoved = std::max(maxFeeRateRemoved, removed); setEntries stage; CalculateDescendants(mapTx.project<0>(it), stage); nTxnRemoved += stage.size(); std::vector<CTransaction> txn; if (pvNoSpendsRemaining) { txn.reserve(stage.size()); for (txiter iter : stage) txn.push_back(iter->GetTx()); } RemoveStaged(stage, false, MemPoolRemovalReason::SIZELIMIT); if (pvNoSpendsRemaining) { for (const CTransaction& tx : txn) { for (const CTxIn& txin : tx.vin) { if (exists(txin.prevout.hash)) continue; pvNoSpendsRemaining->push_back(txin.prevout); } } } } if (maxFeeRateRemoved > CFeeRate(0)) { LogPrint(BCLog::MEMPOOL, "Removed %u txn, rolling minimum fee bumped to %s\n", nTxnRemoved, maxFeeRateRemoved.ToString()); }}uint64_t CTxMemPool::CalculateDescendantMaximum(txiter entry) const { // find parent with highest descendant count std::vector<txiter> candidates; setEntries counted; candidates.push_back(entry); uint64_t maximum = 0; while (candidates.size()) { txiter candidate = candidates.back(); candidates.pop_back(); if (!counted.insert(candidate).second) continue; const CTxMemPoolEntry::Parents& parents = candidate->GetMemPoolParentsConst(); if (parents.size() == 0) { maximum = std::max(maximum, candidate->GetCountWithDescendants()); } else { for (const CTxMemPoolEntry& i : parents) { candidates.push_back(mapTx.iterator_to(i)); } } } return maximum;}void CTxMemPool::GetTransactionAncestry(const uint256& txid, size_t& ancestors, size_t& descendants) const { LOCK(cs); auto it = mapTx.find(txid); ancestors = descendants = 0; if (it != mapTx.end()) { ancestors = it->GetCountWithAncestors(); descendants = CalculateDescendantMaximum(it); }}bool CTxMemPool::IsLoaded() const{ LOCK(cs); return m_is_loaded;}void CTxMemPool::SetIsLoaded(bool loaded){ LOCK(cs); m_is_loaded = loaded;}CTxMemPool::EpochGuard CTxMemPool::GetFreshEpoch() const{ return EpochGuard(*this);}CTxMemPool::EpochGuard::EpochGuard(const CTxMemPool& in) : pool(in){ assert(!pool.m_has_epoch_guard); ++pool.m_epoch; pool.m_has_epoch_guard = true;}CTxMemPool::EpochGuard::~EpochGuard(){ // prevents stale results being used ++pool.m_epoch; pool.m_has_epoch_guard = false;}SaltedTxidHasher::SaltedTxidHasher() : k0(GetRand(std::numeric_limits<uint64_t>::max())), k1(GetRand(std::numeric_limits<uint64_t>::max())) {}