From 46d955d196043cc297834baeebce31ff778dff80 Mon Sep 17 00:00:00 2001 From: Jeremy Rubin Date: Tue, 21 Jan 2020 13:48:57 -0800 Subject: Remove mapLinks in favor of entry inlined structs with iterator type erasure --- src/txmempool.cpp | 181 +++++++++++++++++++++++++++--------------------------- 1 file changed, 91 insertions(+), 90 deletions(-) (limited to 'src/txmempool.cpp') diff --git a/src/txmempool.cpp b/src/txmempool.cpp index f60809e196..e24d8d7b98 100644 --- a/src/txmempool.cpp +++ b/src/txmempool.cpp @@ -55,45 +55,45 @@ size_t CTxMemPoolEntry::GetTxSize() const } // Update the given tx for any in-mempool descendants. -// Assumes that setMemPoolChildren is correct for the given tx and all +// Assumes that CTxMemPool::m_children is correct for the given tx and all // descendants. void CTxMemPool::UpdateForDescendants(txiter updateIt, cacheMap &cachedDescendants, const std::set &setExclude) { - setEntries stageEntries, setAllDescendants; - stageEntries = GetMemPoolChildren(updateIt); + CTxMemPoolEntry::Children stageEntries, descendants; + stageEntries = updateIt->GetMemPoolChildrenConst(); while (!stageEntries.empty()) { - const txiter cit = *stageEntries.begin(); - setAllDescendants.insert(cit); - stageEntries.erase(cit); - const setEntries &setChildren = GetMemPoolChildren(cit); - for (txiter childEntry : setChildren) { - cacheMap::iterator cacheIt = cachedDescendants.find(childEntry); + 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) { - setAllDescendants.insert(cacheEntry); + descendants.insert(*cacheEntry); } - } else if (!setAllDescendants.count(childEntry)) { + } else if (!descendants.count(childEntry)) { // Schedule for later processing stageEntries.insert(childEntry); } } } - // setAllDescendants now contains all in-mempool descendants of updateIt. + // 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; - for (txiter cit : setAllDescendants) { - if (!setExclude.count(cit->GetTx().GetHash())) { - modifySize += cit->GetTxSize(); - modifyFee += cit->GetModifiedFee(); + for (const CTxMemPoolEntry& descendant : descendants) { + if (!setExclude.count(descendant.GetTx().GetHash())) { + modifySize += descendant.GetTxSize(); + modifyFee += descendant.GetModifiedFee(); modifyCount++; - cachedDescendants[updateIt].insert(cit); + cachedDescendants[updateIt].insert(mapTx.iterator_to(descendant)); // Update ancestor state for each descendant - mapTx.modify(cit, update_ancestor_state(updateIt->GetTxSize(), updateIt->GetModifiedFee(), 1, updateIt->GetSigOpCost())); + mapTx.modify(mapTx.iterator_to(descendant), update_ancestor_state(updateIt->GetTxSize(), updateIt->GetModifiedFee(), 1, updateIt->GetSigOpCost())); } } mapTx.modify(updateIt, update_descendant_state(modifySize, modifyFee, modifyCount)); @@ -119,7 +119,7 @@ void CTxMemPool::UpdateTransactionsFromBlock(const std::vector &vHashes // 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 - // setMemPoolChildren will be updated, an assumption made in + // CTxMemPool::m_children will be updated, an assumption made in // UpdateForDescendants. for (const uint256 &hash : reverse_iterate(vHashesToUpdate)) { // calculate children from mapNextTx @@ -128,8 +128,8 @@ void CTxMemPool::UpdateTransactionsFromBlock(const std::vector &vHashes continue; } auto iter = mapNextTx.lower_bound(COutPoint(hash, 0)); - // First calculate the children, and update setMemPoolChildren to - // include them, and update their setMemPoolParents to include this tx. + // 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(); @@ -151,7 +151,7 @@ void CTxMemPool::UpdateTransactionsFromBlock(const std::vector &vHashes 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 { - setEntries parentHashes; + CTxMemPoolEntry::Parents staged_ancestors; const CTransaction &tx = entry.GetTx(); if (fSearchForParents) { @@ -161,8 +161,8 @@ bool CTxMemPool::CalculateMemPoolAncestors(const CTxMemPoolEntry &entry, setEntr for (unsigned int i = 0; i < tx.vin.size(); i++) { Optional piter = GetIter(tx.vin[i].prevout.hash); if (piter) { - parentHashes.insert(*piter); - if (parentHashes.size() + 1 > limitAncestorCount) { + staged_ancestors.insert(**piter); + if (staged_ancestors.size() + 1 > limitAncestorCount) { errString = strprintf("too many unconfirmed parents [limit: %u]", limitAncestorCount); return false; } @@ -172,16 +172,17 @@ bool CTxMemPool::CalculateMemPoolAncestors(const CTxMemPoolEntry &entry, setEntr // If we're not searching for parents, we require this to be an // entry in the mempool already. txiter it = mapTx.iterator_to(entry); - parentHashes = GetMemPoolParents(it); + staged_ancestors = it->GetMemPoolParentsConst(); } size_t totalSizeWithAncestors = entry.GetTxSize(); - while (!parentHashes.empty()) { - txiter stageit = *parentHashes.begin(); + while (!staged_ancestors.empty()) { + const CTxMemPoolEntry& stage = staged_ancestors.begin()->get(); + txiter stageit = mapTx.iterator_to(stage); setAncestors.insert(stageit); - parentHashes.erase(stageit); + staged_ancestors.erase(stage); totalSizeWithAncestors += stageit->GetTxSize(); if (stageit->GetSizeWithDescendants() + entry.GetTxSize() > limitDescendantSize) { @@ -195,13 +196,15 @@ bool CTxMemPool::CalculateMemPoolAncestors(const CTxMemPoolEntry &entry, setEntr return false; } - const setEntries & setMemPoolParents = GetMemPoolParents(stageit); - for (txiter phash : setMemPoolParents) { + 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(phash) == 0) { - parentHashes.insert(phash); + if (setAncestors.count(parent_it) == 0) { + staged_ancestors.insert(parent); } - if (parentHashes.size() + setAncestors.size() + 1 > limitAncestorCount) { + if (staged_ancestors.size() + setAncestors.size() + 1 > limitAncestorCount) { errString = strprintf("too many unconfirmed ancestors [limit: %u]", limitAncestorCount); return false; } @@ -213,10 +216,10 @@ bool CTxMemPool::CalculateMemPoolAncestors(const CTxMemPoolEntry &entry, setEntr void CTxMemPool::UpdateAncestorsOf(bool add, txiter it, setEntries &setAncestors) { - setEntries parentIters = GetMemPoolParents(it); + CTxMemPoolEntry::Parents parents = it->GetMemPoolParents(); // add or remove this tx as a child of each parent - for (txiter piter : parentIters) { - UpdateChild(piter, it, add); + 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(); @@ -242,9 +245,9 @@ void CTxMemPool::UpdateEntryForAncestors(txiter it, const setEntries &setAncesto void CTxMemPool::UpdateChildrenForRemoval(txiter it) { - const setEntries &setMemPoolChildren = GetMemPoolChildren(it); - for (txiter updateIt : setMemPoolChildren) { - UpdateParent(updateIt, it, false); + const CTxMemPoolEntry::Children& children = it->GetMemPoolChildrenConst(); + for (const CTxMemPoolEntry& updateIt : children) { + UpdateParent(mapTx.iterator_to(updateIt), it, false); } } @@ -257,9 +260,9 @@ void CTxMemPool::UpdateForRemoveFromMempool(const setEntries &entriesToRemove, b // 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 mapLinks (which - // we need to preserve until we're finished with all operations that - // need to traverse the mempool). + // 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); @@ -282,24 +285,26 @@ void CTxMemPool::UpdateForRemoveFromMempool(const setEntries &entriesToRemove, b // 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 mapLinks 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. + // 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 mapLinks[] will - // differ from the set of mempool parents we'd calculate by searching, - // and it's important that we use the mapLinks[] notion of ancestor - // transactions as the set of things to update for removal. + // 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 setMemPoolParents + // 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); @@ -359,7 +364,6 @@ void CTxMemPool::addUnchecked(const CTxMemPoolEntry &entry, setEntries &setAnces // Used by AcceptToMemoryPool(), which DOES do // all the appropriate checks. indexed_transaction_set::iterator newit = mapTx.insert(entry).first; - mapLinks.insert(make_pair(newit, TxLinks())); // Update transaction for any feeDelta created by PrioritiseTransaction // TODO: refactor so that the fee delta is calculated before inserting @@ -430,15 +434,14 @@ void CTxMemPool::removeUnchecked(txiter it, MemPoolRemovalReason reason) totalTxSize -= it->GetTxSize(); cachedInnerUsage -= it->DynamicMemoryUsage(); - cachedInnerUsage -= memusage::DynamicUsage(mapLinks[it].parents) + memusage::DynamicUsage(mapLinks[it].children); - mapLinks.erase(it); + 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 setMemPoolChildren +// 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 @@ -457,8 +460,9 @@ void CTxMemPool::CalculateDescendants(txiter entryit, setEntries& setDescendants setDescendants.insert(it); stage.erase(it); - const setEntries &setChildren = GetMemPoolChildren(it); - for (txiter childiter : setChildren) { + const CTxMemPoolEntry::Children& children = it->GetMemPoolChildrenConst(); + for (const CTxMemPoolEntry& child : children) { + txiter childiter = mapTx.iterator_to(child); if (!setDescendants.count(childiter)) { stage.insert(childiter); } @@ -584,7 +588,6 @@ void CTxMemPool::removeForBlock(const std::vector& vtx, unsigne void CTxMemPool::_clear() { - mapLinks.clear(); mapTx.clear(); mapNextTx.clear(); totalTxSize = 0; @@ -633,12 +636,9 @@ void CTxMemPool::check(const CCoinsViewCache *pcoins) const checkTotal += it->GetTxSize(); innerUsage += it->DynamicMemoryUsage(); const CTransaction& tx = it->GetTx(); - txlinksMap::const_iterator linksiter = mapLinks.find(it); - assert(linksiter != mapLinks.end()); - const TxLinks &links = linksiter->second; - innerUsage += memusage::DynamicUsage(links.parents) + memusage::DynamicUsage(links.children); + innerUsage += memusage::DynamicUsage(it->GetMemPoolParentsConst()) + memusage::DynamicUsage(it->GetMemPoolChildrenConst()); bool fDependsWait = false; - setEntries setParentCheck; + 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. indexed_transaction_set::const_iterator it2 = mapTx.find(txin.prevout.hash); @@ -646,7 +646,7 @@ void CTxMemPool::check(const CCoinsViewCache *pcoins) const const CTransaction& tx2 = it2->GetTx(); assert(tx2.vout.size() > txin.prevout.n && !tx2.vout[txin.prevout.n].IsNull()); fDependsWait = true; - setParentCheck.insert(it2); + setParentCheck.insert(*it2); } else { assert(pcoins->HaveCoin(txin.prevout)); } @@ -657,7 +657,11 @@ void CTxMemPool::check(const CCoinsViewCache *pcoins) const assert(it3->second == &tx); i++; } - assert(setParentCheck == GetMemPoolParents(it)); + 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::max(); @@ -680,17 +684,18 @@ void CTxMemPool::check(const CCoinsViewCache *pcoins) const assert(it->GetModFeesWithAncestors() == nFeesCheck); // Check children against mapNextTx - CTxMemPool::setEntries setChildrenCheck; + CTxMemPoolEntry::Children setChildrenCheck; auto iter = mapNextTx.lower_bound(COutPoint(it->GetTx().GetHash(), 0)); uint64_t child_sizes = 0; for (; iter != mapNextTx.end() && iter->first->hash == it->GetTx().GetHash(); ++iter) { txiter childit = mapTx.find(iter->second->GetHash()); assert(childit != mapTx.end()); // mapNextTx points to in-mempool transactions - if (setChildrenCheck.insert(childit).second) { + if (setChildrenCheck.insert(*childit).second) { child_sizes += childit->GetTxSize(); } } - assert(setChildrenCheck == GetMemPoolChildren(it)); + 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()); @@ -920,7 +925,7 @@ bool CCoinsViewMemPool::GetCoin(const COutPoint &outpoint, Coin &coin) const { 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(mapDeltas) + memusage::DynamicUsage(mapLinks) + memusage::DynamicUsage(vTxHashes) + cachedInnerUsage; + return memusage::MallocUsage(sizeof(CTxMemPoolEntry) + 15 * sizeof(void*)) * mapTx.size() + memusage::DynamicUsage(mapNextTx) + memusage::DynamicUsage(mapDeltas) + memusage::DynamicUsage(vTxHashes) + cachedInnerUsage; } void CTxMemPool::RemoveUnbroadcastTx(const uint256& txid, const bool unchecked) { @@ -969,10 +974,10 @@ void CTxMemPool::addUnchecked(const CTxMemPoolEntry &entry, bool validFeeEstimat void CTxMemPool::UpdateChild(txiter entry, txiter child, bool add) { AssertLockHeld(cs); - setEntries s; - if (add && mapLinks[entry].children.insert(child).second) { + CTxMemPoolEntry::Children s; + if (add && entry->GetMemPoolChildren().insert(*child).second) { cachedInnerUsage += memusage::IncrementalDynamicUsage(s); - } else if (!add && mapLinks[entry].children.erase(child)) { + } else if (!add && entry->GetMemPoolChildren().erase(*child)) { cachedInnerUsage -= memusage::IncrementalDynamicUsage(s); } } @@ -980,28 +985,24 @@ void CTxMemPool::UpdateChild(txiter entry, txiter child, bool add) void CTxMemPool::UpdateParent(txiter entry, txiter parent, bool add) { AssertLockHeld(cs); - setEntries s; - if (add && mapLinks[entry].parents.insert(parent).second) { + CTxMemPoolEntry::Parents s; + if (add && entry->GetMemPoolParents().insert(*parent).second) { cachedInnerUsage += memusage::IncrementalDynamicUsage(s); - } else if (!add && mapLinks[entry].parents.erase(parent)) { + } else if (!add && entry->GetMemPoolParents().erase(*parent)) { cachedInnerUsage -= memusage::IncrementalDynamicUsage(s); } } -const CTxMemPool::setEntries & CTxMemPool::GetMemPoolParents(txiter entry) const +const CTxMemPoolEntry::Parents & CTxMemPool::GetMemPoolParents(txiter entry) const { - assert (entry != mapTx.end()); - txlinksMap::const_iterator it = mapLinks.find(entry); - assert(it != mapLinks.end()); - return it->second.parents; + assert(entry != mapTx.end()); + return entry->GetMemPoolParentsConst(); } -const CTxMemPool::setEntries & CTxMemPool::GetMemPoolChildren(txiter entry) const +const CTxMemPoolEntry::Children & CTxMemPool::GetMemPoolChildren(txiter entry) const { - assert (entry != mapTx.end()); - txlinksMap::const_iterator it = mapLinks.find(entry); - assert(it != mapLinks.end()); - return it->second.children; + assert(entry != mapTx.end()); + return entry->GetMemPoolChildrenConst(); } CFeeRate CTxMemPool::GetMinFee(size_t sizelimit) const { @@ -1089,12 +1090,12 @@ uint64_t CTxMemPool::CalculateDescendantMaximum(txiter entry) const { txiter candidate = candidates.back(); candidates.pop_back(); if (!counted.insert(candidate).second) continue; - const setEntries& parents = GetMemPoolParents(candidate); + const CTxMemPoolEntry::Parents& parents = candidate->GetMemPoolParentsConst(); if (parents.size() == 0) { maximum = std::max(maximum, candidate->GetCountWithDescendants()); } else { - for (txiter i : parents) { - candidates.push_back(i); + for (const CTxMemPoolEntry& i : parents) { + candidates.push_back(mapTx.iterator_to(i)); } } } -- cgit v1.2.3