diff --git a/src/net_processing.cpp b/src/net_processing.cpp
--- a/src/net_processing.cpp
+++ b/src/net_processing.cpp
@@ -6494,14 +6494,14 @@
CTxMemPool *mp;
public:
- explicit CompareInvMempoolOrder(CTxMemPool *_mempool) { mp = _mempool; }
+ explicit CompareInvMempoolOrder(CTxMemPool *_mempool) : mp(_mempool) {}
bool operator()(std::set<TxId>::iterator a, std::set<TxId>::iterator b) {
/**
- * As std::make_heap produces a max-heap, we want the entries with the
- * fewest ancestors/highest fee to sort later.
+ * As std::make_heap produces a max-heap, we want the entries which
+ * are topologically earlier to sort later.
*/
- return mp->CompareDepthAndScore(*b, *a);
+ return mp->CompareTopologically(*b, *a);
}
};
} // namespace
@@ -6937,9 +6937,10 @@
LOCK(pto->m_tx_relay->cs_feeFilter);
filterrate = CFeeRate(pto->m_tx_relay->minFeeFilter);
}
- // Topologically and fee-rate sort the inventory we send for
- // privacy and priority reasons. A heap is used so that not
- // all items need sorting if only a few are being sent.
+ // Send out the inventory in the order of admission to our
+ // mempool, which is guaranteed to be a topological sort order.
+ // A heap is used so that not all items need sorting if only a
+ // few are being sent.
CompareInvMempoolOrder compareInvMempoolOrder(&m_mempool);
std::make_heap(vInvTx.begin(), vInvTx.end(),
compareInvMempoolOrder);
diff --git a/src/txmempool.h b/src/txmempool.h
--- a/src/txmempool.h
+++ b/src/txmempool.h
@@ -26,6 +26,7 @@
#include <optional>
#include <set>
#include <string>
+#include <unordered_map>
#include <utility>
#include <vector>
@@ -93,6 +94,9 @@
typedef std::set<CTxMemPoolEntryRef, CompareIteratorById> Children;
private:
+ //! Unique identifier -- used for topological sorting
+ uint64_t entryId = 0;
+
const CTransactionRef tx;
mutable Parents m_parents;
mutable Children m_children;
@@ -139,9 +143,14 @@
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; }
- const Amount GetFee() const { return nFee; }
+ Amount GetFee() const { return nFee; }
size_t GetTxSize() const { return nTxSize; }
size_t GetTxVirtualSize() const;
@@ -206,29 +215,17 @@
}
};
-/** \class CompareTxMemPoolEntryByScore
- *
- * Sort by feerate of entry (fee/size) in descending order
- * This is only used for transaction relay, so we use GetFee()
- * instead of GetModifiedFee() to avoid leaking prioritization
- * information via the sort order.
- */
-class CompareTxMemPoolEntryByScore {
-public:
+// used by the entry_time index
+struct CompareTxMemPoolEntryByEntryTime {
bool operator()(const CTxMemPoolEntry &a, const CTxMemPoolEntry &b) const {
- double f1 = b.GetTxSize() * (a.GetFee() / SATOSHI);
- double f2 = a.GetTxSize() * (b.GetFee() / SATOSHI);
- if (f1 == f2) {
- return b.GetTx().GetId() < a.GetTx().GetId();
- }
- return f1 > f2;
+ return a.GetTime() < b.GetTime();
}
};
-class CompareTxMemPoolEntryByEntryTime {
-public:
+// used by the entry_id index
+struct CompareTxMemPoolEntryByEntryId {
bool operator()(const CTxMemPoolEntry &a, const CTxMemPoolEntry &b) const {
- return a.GetTime() < b.GetTime();
+ return a.GetEntryId() < b.GetEntryId();
}
};
@@ -261,6 +258,7 @@
// Multi_index tag names
struct entry_time {};
struct modified_feerate {};
+struct entry_id {};
/**
* Information about a mempool transaction.
@@ -318,22 +316,14 @@
* mapTx is a boost::multi_index that sorts the mempool on 3 criteria:
* - transaction hash
* - time in mempool
- * - ancestor feerate [we use min(feerate of tx, feerate of tx with all
- * unconfirmed ancestors)]
+ * - 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.
*
- * In order for the feerate sort to remain correct, we must update transactions
- * in the mempool when new descendants arrive. To facilitate this, we track the
- * set of in-mempool direct parents and direct children in m_parents and
- * m_children. Within each CTxMemPoolEntry, we track the size and fees of all
- * descendants.
- *
- * Usually 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:
+ * 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
* - update all ancestors of the transaction to include the new tx's size/fee
@@ -349,21 +339,11 @@
* be in an inconsistent state where it's impossible to walk the ancestors of a
* transaction.)
*
- * In the event of a reorg, the assumption that a newly added tx has no
- * in-mempool children is false. In particular, the mempool is in an
- * inconsistent state while new transactions are being added, because there may
- * be descendant transactions of a tx coming from a disconnected block that are
- * unreachable from just looking at transactions in the mempool (the linking
- * transactions may also be in the disconnected block, waiting to be added).
- * Because of this, there's not much benefit in trying to search for in-mempool
- * children in addUnchecked(). Instead, in the special case of transactions
- * being added from a disconnected block, we require the caller to clean up the
- * state, to account for in-mempool, out-of-block descendants for all the
- * in-block transactions by calling UpdateTransactionsFromBlock(). Note that
- * until this is called, the mempool state is not consistent, and in particular
- * m_parents and m_children may not be correct (and therefore functions like
- * CalculateMemPoolAncestors() and CalculateDescendants() that rely on them to
- * walk the mempool are not generally safe to use).
+ * 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:
*
@@ -402,6 +382,10 @@
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;
@@ -420,7 +404,12 @@
boost::multi_index::ordered_non_unique<
boost::multi_index::tag<entry_time>,
boost::multi_index::identity<CTxMemPoolEntry>,
- CompareTxMemPoolEntryByEntryTime>>>
+ CompareTxMemPoolEntryByEntryTime>,
+ // sorted topologically (insertion order)
+ boost::multi_index::ordered_unique<
+ boost::multi_index::tag<entry_id>,
+ boost::multi_index::identity<CTxMemPoolEntry>,
+ CompareTxMemPoolEntryByEntryId>>>
indexed_transaction_set;
/**
@@ -460,16 +449,11 @@
EXCLUSIVE_LOCKS_REQUIRED(cs);
private:
- typedef std::map<txiter, setEntries, CompareIteratorById> cacheMap;
-
void UpdateParent(txiter entry, txiter parent, bool add)
EXCLUSIVE_LOCKS_REQUIRED(cs);
void UpdateChild(txiter entry, txiter child, bool add)
EXCLUSIVE_LOCKS_REQUIRED(cs);
- std::vector<indexed_transaction_set::const_iterator>
- GetSortedDepthAndScore() const EXCLUSIVE_LOCKS_REQUIRED(cs);
-
/**
* Track locally submitted transactions to periodically retry initial
* broadcast
@@ -533,18 +517,6 @@
void removeRecursive(const CTransaction &tx, MemPoolRemovalReason reason)
EXCLUSIVE_LOCKS_REQUIRED(cs);
- /**
- * After reorg, filter the entries that would no longer be valid in the
- * next block, and update the entries' cached LockPoints if needed.
- * The mempool does not have any knowledge of consensus rules. It just
- * applies the callable function and removes the ones for which it
- * returns true.
- * @param[in] filter_final_and_mature Predicate that checks the
- * relevant validation rules and updates an entry's LockPoints.
- */
- void removeForReorg(const Config &config, CChain &chain,
- std::function<bool(txiter)> filter_final_and_mature)
- EXCLUSIVE_LOCKS_REQUIRED(cs, cs_main);
void removeConflicts(const CTransaction &tx) EXCLUSIVE_LOCKS_REQUIRED(cs);
void removeForBlock(const std::vector<CTransactionRef> &vtx,
unsigned int nBlockHeight) EXCLUSIVE_LOCKS_REQUIRED(cs);
@@ -552,7 +524,7 @@
void clear();
// lock free
void _clear() EXCLUSIVE_LOCKS_REQUIRED(cs);
- bool CompareDepthAndScore(const TxId &txida, const TxId &txidb);
+ bool CompareTopologically(const TxId &txida, const TxId &txidb) const;
void getAllTxIds(std::vector<TxId> &vtxid) const;
bool isSpent(const COutPoint &outpoint) const;
unsigned int GetTransactionsUpdated() const;
@@ -596,29 +568,6 @@
void RemoveStaged(setEntries &stage, bool updateDescendants,
MemPoolRemovalReason reason) EXCLUSIVE_LOCKS_REQUIRED(cs);
- /**
- * UpdateTransactionsFromBlock is called when adding transactions from a
- * disconnected block back to the mempool, new mempool entries may have
- * children in the mempool (which is generally not the case when otherwise
- * adding transactions).
- * @post updated descendant state for descendants of each transaction in
- * txidsToUpdate (excluding any child transactions present in
- * txidsToUpdate, which are already accounted for). Updated state
- * includes add fee/size information for such descendants to the
- * parent and updated ancestor state to include the parent.
- *
- * @param[in] txidsToUpdate The set of txids from the
- * disconnected block that have been accepted back into the mempool.
- * @param[in] ancestor_size_limit The maximum allowed size in virtual
- * bytes of an entry and its ancestors
- * @param[in] ancestor_count_limit The maximum allowed number of
- * transactions including the entry and its ancestors.
- */
- void UpdateTransactionsFromBlock(const std::vector<TxId> &txidsToUpdate,
- uint64_t ancestor_size_limit,
- uint64_t ancestor_count_limit)
- EXCLUSIVE_LOCKS_REQUIRED(cs, cs_main) LOCKS_EXCLUDED(m_epoch);
-
/**
* Try to calculate all in-mempool ancestors of entry.
* (these are all calculated including the tx itself)
@@ -786,47 +735,6 @@
}
private:
- /**
- * UpdateForDescendants is used by UpdateTransactionsFromBlock to update
- * the descendants for a single transaction that has been added to the
- * mempool but may have child transactions in the mempool, eg during a
- * chain reorg.
- *
- * @pre CTxMemPool::m_children is correct for the given tx and all
- * descendants.
- * @pre cachedDescendants is an accurate cache where each entry has all
- * descendants of the corresponding key, including those that should
- * be removed for violation of ancestor limits.
- * @post if updateIt has any non-excluded descendants, cachedDescendants
- * has a new cache line for updateIt.
- * @post descendants_to_remove has a new entry for any descendant which
- * exceeded ancestor limits relative to updateIt.
- *
- * @param[in] updateIt the entry to update for its descendants
- * @param[in,out] cachedDescendants a cache where each line corresponds to
- * all descendants. It will be updated with the descendants of the
- * transaction being updated, so that future invocations don't need to
- * walk the same transaction again, if encountered in another
- * transaction chain.
- * @param[in] setExclude the set of descendant transactions in the mempool
- * that must not be accounted for (because any descendants in
- * setExclude were added to the mempool after the transaction being
- * updated and hence their state is already reflected in the parent
- * state).
- * @param[out] descendants_to_remove Populated with the txids of entries
- * that exceed ancestor limits. It's the responsibility of the caller
- * to removeRecursive them.
- * @param[in] ancestor_size_limit the max number of ancestral bytes allowed
- * for any descendant
- * @param[in] ancestor_count_limit the max number of ancestor transactions
- * allowed for any descendant
- */
- void UpdateForDescendants(txiter updateIt, cacheMap &cachedDescendants,
- const std::set<TxId> &setExclude,
- std::set<TxId> &descendants_to_remove,
- uint64_t ancestor_size_limit,
- uint64_t ancestor_count_limit)
- EXCLUSIVE_LOCKS_REQUIRED(cs);
/**
* Update ancestors of hash to add/remove it as a descendant transaction.
*/
@@ -940,7 +848,7 @@
private:
typedef boost::multi_index_container<
CTransactionRef, boost::multi_index::indexed_by<
- // sorted by txid
+ // hashed by txid
boost::multi_index::hashed_unique<
boost::multi_index::tag<txid_index>,
mempoolentry_txid, SaltedTxIdHasher>,
@@ -952,11 +860,25 @@
indexed_disconnected_transactions queuedTx;
uint64_t cachedInnerUsage = 0;
+ struct TxInfo {
+ const std::chrono::seconds time;
+ const Amount feeDelta;
+ };
+
+ using TxInfoMap = std::unordered_map<TxId, TxInfo, SaltedTxIdHasher>;
+ /// 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
@@ -974,7 +896,7 @@
return memusage::MallocUsage(sizeof(CTransactionRef) +
6 * sizeof(void *)) *
queuedTx.size() +
- cachedInnerUsage;
+ memusage::DynamicUsage(txInfo) + cachedInnerUsage;
}
const indexed_disconnected_transactions &GetQueuedTx() const {
@@ -1002,6 +924,7 @@
if (it != queuedTx.end()) {
cachedInnerUsage -= RecursiveDynamicUsage(*it);
queuedTx.erase(it);
+ txInfo.erase(tx->GetId());
}
}
}
@@ -1010,6 +933,7 @@
void removeEntry(indexed_disconnected_transactions::index<
insertion_order>::type::iterator entry) {
cachedInnerUsage -= RecursiveDynamicUsage(*entry);
+ txInfo.erase((*entry)->GetId());
queuedTx.get<insertion_order>().erase(entry);
}
@@ -1018,6 +942,7 @@
void clear() {
cachedInnerUsage = 0;
queuedTx.clear();
+ txInfo.clear();
}
/**
diff --git a/src/txmempool.cpp b/src/txmempool.cpp
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -18,6 +18,7 @@
#include <policy/policy.h>
#include <policy/settings.h>
#include <reverse_iterator.h>
+#include <undo.h>
#include <util/moneystr.h>
#include <util/system.h>
#include <util/time.h>
@@ -123,131 +124,6 @@
lockPoints = lp;
}
-void CTxMemPool::UpdateForDescendants(txiter updateIt,
- cacheMap &cachedDescendants,
- const std::set<TxId> &setExclude,
- std::set<TxId> &descendants_to_remove,
- uint64_t ancestor_size_limit,
- uint64_t ancestor_count_limit) {
- 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;
- int64_t modifyCount = 0;
- Amount modifyFee = Amount::zero();
- int64_t modifySigChecks = 0;
- for (const CTxMemPoolEntry &descendant : descendants) {
- if (!setExclude.count(descendant.GetTx().GetId())) {
- modifySize += descendant.GetTxSize();
- modifyFee += descendant.GetModifiedFee();
- modifyCount++;
- modifySigChecks += descendant.GetSigChecks();
- 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->GetSigChecks()));
- // Don't directly remove the transaction here -- doing so would
- // invalidate iterators in cachedDescendants. Mark it for removal
- // by inserting into descendants_to_remove.
- if (descendant.GetCountWithAncestors() > ancestor_count_limit ||
- descendant.GetSizeWithAncestors() > ancestor_size_limit) {
- descendants_to_remove.insert(descendant.GetTx().GetId());
- }
- }
- }
- mapTx.modify(updateIt,
- update_descendant_state(modifySize, modifyFee, modifyCount,
- modifySigChecks));
-}
-
-void CTxMemPool::UpdateTransactionsFromBlock(
- const std::vector<TxId> &txidsToUpdate, uint64_t ancestor_size_limit,
- uint64_t ancestor_count_limit) {
- AssertLockHeld(cs);
- // For each entry in txidsToUpdate, store the set of in-mempool, but not
- // in-txidsToUpdate 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 txidsToUpdate (these entries are already
- // accounted for in the state of their ancestors)
- std::set<TxId> setAlreadyIncluded(txidsToUpdate.begin(),
- txidsToUpdate.end());
-
- std::set<TxId> descendants_to_remove;
-
- // 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 TxId &txid : reverse_iterate(txidsToUpdate)) {
- // calculate children from mapNextTx
- txiter it = mapTx.find(txid);
- if (it == mapTx.end()) {
- continue;
- }
-
- auto iter = mapNextTx.lower_bound(COutPoint(txid, 0));
- // 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
- {
- WITH_FRESH_EPOCH(m_epoch);
- for (; iter != mapNextTx.end() && iter->first->GetTxId() == txid;
- ++iter) {
- const TxId &childTxId = iter->second->GetId();
- txiter childIter = mapTx.find(childTxId);
- 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(childTxId)) {
- UpdateChild(it, childIter, true);
- UpdateParent(childIter, it, true);
- }
- }
- } // release epoch guard for UpdateForDescendants
- UpdateForDescendants(it, mapMemPoolDescendantsToUpdate,
- setAlreadyIncluded, descendants_to_remove,
- ancestor_size_limit, ancestor_count_limit);
- }
-
- for (const auto &txid : descendants_to_remove) {
- // This txid may have been removed already in a prior call to
- // removeRecursive. Therefore we ensure it is not yet removed already.
- if (const std::optional<txiter> txiter = GetIter(txid)) {
- removeRecursive((*txiter)->GetTx(),
- MemPoolRemovalReason::SIZELIMIT);
- }
- }
-}
-
bool CTxMemPool::CalculateAncestorsAndCheckLimits(
size_t entry_size, size_t entry_count, setEntries &setAncestors,
CTxMemPoolEntry::Parents &staged_ancestors, uint64_t limitAncestorCount,
@@ -535,21 +411,29 @@
nTransactionsUpdated += n;
}
-void CTxMemPool::addUnchecked(const CTxMemPoolEntry &entry,
+void CTxMemPool::addUnchecked(const CTxMemPoolEntry &entryIn,
setEntries &setAncestors) {
- // 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;
+ 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);
- if (feeDelta != Amount::zero()) {
- mapTx.modify(newit, [&feeDelta](CTxMemPoolEntry &e) {
- e.UpdateFeeDelta(feeDelta);
- });
+ {
+ 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<entry_id>().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.)
@@ -561,12 +445,9 @@
mapNextTx.insert(std::make_pair(&in.prevout, &tx));
setParentTransactions.insert(in.prevout.GetTxId());
}
- // 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.
+ // 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)) {
@@ -654,15 +535,13 @@
// 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 (size_t i = 0; i < origTx.vout.size(); i++) {
- auto it = mapNextTx.find(COutPoint(origTx.GetId(), i));
- if (it == mapNextTx.end()) {
- continue;
- }
-
+ 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;
}
}
@@ -674,32 +553,6 @@
RemoveStaged(setAllRemoves, false, reason);
}
-void CTxMemPool::removeForReorg(
- const Config &config, CChain &chain,
- std::function<bool(txiter)> check_final_and_mature) {
- // Remove transactions spending a coinbase which are now immature and
- // no-longer-final transactions.
- AssertLockHeld(cs);
- AssertLockHeld(::cs_main);
-
- setEntries txToRemove;
- for (indexed_transaction_set::const_iterator it = mapTx.begin();
- it != mapTx.end(); it++) {
- if (check_final_and_mature(it)) {
- txToRemove.insert(it);
- }
- }
- setEntries setAllRemoves;
- for (txiter it : txToRemove) {
- CalculateDescendants(it, setAllRemoves);
- }
- RemoveStaged(setAllRemoves, false, MemPoolRemovalReason::REORG);
- for (indexed_transaction_set::const_iterator it = mapTx.begin();
- it != mapTx.end(); it++) {
- assert(TestLockPointValidity(chain, it->GetLockPoints()));
- }
-}
-
void CTxMemPool::removeConflicts(const CTransaction &tx) {
// Remove transactions which depend on inputs of tx, recursively
AssertLockHeld(cs);
@@ -791,12 +644,12 @@
uint64_t checkTotal = 0;
Amount check_total_fee{Amount::zero()};
uint64_t innerUsage = 0;
- uint64_t prev_ancestor_count{0};
CCoinsViewCache mempoolDuplicate(
const_cast<CCoinsViewCache *>(&active_coins_tip));
- for (const auto &it : GetSortedDepthAndScore()) {
+ const auto &index = mapTx.get<entry_id>();
+ for (auto it = index.begin(); it != index.end(); ++it) {
checkTotal += it->GetTxSize();
check_total_fee += it->GetFee();
innerUsage += it->DynamicMemoryUsage();
@@ -807,16 +660,18 @@
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.GetTxId());
+ txiter it2 = mapTx.find(txin.prevout.GetTxId());
if (it2 != mapTx.end()) {
const CTransaction &tx2 = it2->GetTx();
assert(tx2.vout.size() > txin.prevout.GetN() &&
!tx2.vout[txin.prevout.GetN()].IsNull());
setParentCheck.insert(*it2);
+ // also check that parents have a topological ordering before
+ // their children
+ assert(it2->GetEntryId() < it->GetEntryId());
}
- // We are iterating through the mempool entries sorted in order by
- // ancestor count.
+ // 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));
@@ -854,9 +709,11 @@
assert(it->GetSizeWithAncestors() == nSizeCheck);
assert(it->GetSigChecksWithAncestors() == nSigChecksCheck);
assert(it->GetModFeesWithAncestors() == nFeesCheck);
- // Sanity check: we are walking in ascending ancestor count order.
- assert(prev_ancestor_count <= it->GetCountWithAncestors());
- prev_ancestor_count = it->GetCountWithAncestors();
+
+ // all ancestors should have entryId < this tx's entryId
+ for (const auto &ancestor : setAncestors) {
+ assert(ancestor->GetEntryId() < it->GetEntryId());
+ }
// Check children against mapNextTx
CTxMemPoolEntry::Children setChildrenCheck;
@@ -909,64 +766,28 @@
assert(innerUsage == cachedInnerUsage);
}
-bool CTxMemPool::CompareDepthAndScore(const TxId &txida, const TxId &txidb) {
+bool CTxMemPool::CompareTopologically(const TxId &txida,
+ const TxId &txidb) const {
LOCK(cs);
- indexed_transaction_set::const_iterator i = mapTx.find(txida);
- if (i == mapTx.end()) {
+ auto it1 = mapTx.find(txida);
+ if (it1 == mapTx.end()) {
return false;
}
- indexed_transaction_set::const_iterator j = mapTx.find(txidb);
- if (j == mapTx.end()) {
+ auto it2 = mapTx.find(txidb);
+ if (it2 == 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;
- }
-};
-} // namespace
-
-std::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;
+ return it1->GetEntryId() < it2->GetEntryId();
}
void CTxMemPool::getAllTxIds(std::vector<TxId> &vtxid) const {
LOCK(cs);
- auto iters = GetSortedDepthAndScore();
vtxid.clear();
vtxid.reserve(mapTx.size());
- for (auto it : iters) {
- vtxid.push_back(it->GetTx().GetId());
+ for (const auto &entry : mapTx.get<entry_id>()) {
+ vtxid.push_back(entry.GetTx().GetId());
}
}
@@ -978,12 +799,13 @@
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));
+
+ const auto &index = mapTx.get<entry_id>();
+ for (auto it = index.begin(); it != index.end(); ++it) {
+ ret.push_back(GetInfo(mapTx.project<0>(it)));
}
return ret;
@@ -1143,9 +965,10 @@
size_t CTxMemPool::DynamicMemoryUsage() const {
LOCK(cs);
- // Estimate the overhead of mapTx to be 9 pointers + an allocation, as no
+ // 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) + 9 * sizeof(void *)) *
+ return memusage::MallocUsage(sizeof(CTxMemPoolEntry) +
+ 12 * sizeof(void *)) *
mapTx.size() +
memusage::DynamicUsage(mapNextTx) +
memusage::DynamicUsage(mapDeltas) + cachedInnerUsage;
@@ -1436,14 +1259,27 @@
// the current queuedTx. This results in a valid sequence of transactions to
// be reprocessed in updateMempoolForReorg.
- // We create vtx in order of the entry_time index to facilitate for
+ // 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<CTransactionRef> vtx;
vtx.reserve(pool.mapTx.size());
- for (const CTxMemPoolEntry &e : pool.mapTx.get<entry_time>()) {
+ txInfo.reserve(pool.mapTx.size());
+ for (const CTxMemPoolEntry &e : pool.mapTx.get<entry_id>()) {
vtx.push_back(e.GetSharedTx());
+ // save entry time and feeDelta for use in updateMempoolForReorg()
+ txInfo.try_emplace(
+ e.GetTx().GetId(),
+ TxInfo{e.GetTime(), e.GetModifiedFee() - e.GetFee()});
+ // 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();
@@ -1464,123 +1300,58 @@
}
}
+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);
- std::vector<TxId> txidsUpdate;
-
- // 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<insertion_order>())) {
- // ignore validation errors in resurrected transactions
- if (!fAddToMempool || tx->IsCoinBase() ||
- AcceptToMemoryPool(config, active_chainstate, tx, GetTime(),
- /*bypass_limits=*/true,
- /*test_accept=*/false)
- .m_result_type != MempoolAcceptResult::ResultType::VALID) {
- // If the transaction doesn't make it in to the mempool, remove any
- // transactions that depend on it (which would now be orphans).
- pool.removeRecursive(*tx, MemPoolRemovalReason::REORG);
- } else if (pool.exists(tx->GetId())) {
- txidsUpdate.push_back(tx->GetId());
- }
- }
-
- queuedTx.clear();
- // AcceptToMemoryPool/addUnchecked all assume that new mempool entries have
- // no in-mempool children, which is generally not true when adding
- // previously-confirmed transactions back to the mempool.
- // UpdateTransactionsFromBlock finds descendants of any transactions in the
- // disconnectpool that were added back and cleans up the mempool state.
- const uint64_t ancestor_count_limit =
- gArgs.GetIntArg("-limitancestorcount", DEFAULT_ANCESTOR_LIMIT);
- const uint64_t ancestor_size_limit =
- gArgs.GetIntArg("-limitancestorsize", DEFAULT_ANCESTOR_SIZE_LIMIT) *
- 1000;
- pool.UpdateTransactionsFromBlock(txidsUpdate, ancestor_size_limit,
- ancestor_count_limit);
-
- // Predicate to use for filtering transactions in removeForReorg.
- // Checks whether the transaction is still final and, if it spends a
- // coinbase output, mature.
- // Also updates valid entries' cached LockPoints if needed.
- // If false, the tx is still valid and its lockpoints are updated.
- // If true, the tx would be invalid in the next block; remove this entry
- // and all of its descendants.
- const auto filter_final_and_mature =
- [&pool, &active_chainstate,
- &config](CTxMemPool::txiter it) EXCLUSIVE_LOCKS_REQUIRED(pool.cs,
- ::cs_main) {
- AssertLockHeld(pool.cs);
- AssertLockHeld(::cs_main);
- const CTransaction &tx = it->GetTx();
-
- // The transaction must be final.
- TxValidationState state;
- if (!ContextualCheckTransactionForCurrentBlock(
- active_chainstate.m_chain.Tip(),
- config.GetChainParams().GetConsensus(), tx, state)) {
- return true;
+ 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<insertion_order>())) {
+ if (tx->IsCoinBase()) {
+ continue;
}
- LockPoints lp = it->GetLockPoints();
- const bool validLP{
- TestLockPointValidity(active_chainstate.m_chain, lp)};
- CCoinsViewMemPool view_mempool(&active_chainstate.CoinsTip(), pool);
-
- // CheckSequenceLocksAtTip checks if the transaction will be final
- // in the next block to be created on top of the new chain. We use
- // useExistingLockPoints=false so that, instead of using the
- // information in lp (which might now refer to a block that no
- // longer exists in the chain), it will update lp to contain
- // LockPoints relevant to the new chain.
- if (!CheckSequenceLocksAtTip(active_chainstate.m_chain.Tip(),
- view_mempool, tx, &lp, validLP)) {
- // If CheckSequenceLocksAtTip fails, remove the tx and don't
- // depend on the LockPoints.
- return true;
+ // 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;
}
- if (!validLP) {
- // If CheckSequenceLocksAtTip succeeded, it also updated the
- // LockPoints. Now update the mempool entry lockpoints as well.
- pool.mapTx.modify(
- it, [&lp](CTxMemPoolEntry &e) { e.UpdateLockPoints(lp); });
+ // ignore validation errors in resurrected transactions
+ auto result = AcceptToMemoryPool(
+ config, active_chainstate, tx,
+ /*accept_time=*/ptxInfo ? ptxInfo->time.count() : GetTime(),
+ /*bypass_limits=*/true);
+ if (result.m_result_type !=
+ MempoolAcceptResult::ResultType::VALID &&
+ hasFeeDelta) {
+ // tx not accepted: undo mapDelta insertion from above
+ pool.mapDeltas.erase(tx->GetId());
}
+ }
+ }
- // If the transaction spends any coinbase outputs, it must be
- // mature.
- if (it->GetSpendsCoinbase()) {
- for (const CTxIn &txin : tx.vin) {
- auto it2 = pool.mapTx.find(txin.prevout.GetTxId());
- if (it2 != pool.mapTx.end()) {
- continue;
- }
- const Coin &coin{
- active_chainstate.CoinsTip().AccessCoin(txin.prevout)};
- assert(!coin.IsSpent());
- const auto mempool_spend_height{
- active_chainstate.m_chain.Tip()->nHeight + 1};
- if (coin.IsCoinBase() &&
- mempool_spend_height - coin.GetHeight() <
- COINBASE_MATURITY) {
- return true;
- }
- }
- }
- // Transaction is still valid and cached LockPoints are updated.
- return false;
- };
-
- // We also need to remove any now-immature transactions
- pool.removeForReorg(config, active_chainstate.m_chain,
- filter_final_and_mature);
+ queuedTx.clear();
+ txInfo.clear();
// Re-limit mempool size, in case we added any transactions
pool.LimitSize(active_chainstate.CoinsTip(),
diff --git a/src/validation.cpp b/src/validation.cpp
--- a/src/validation.cpp
+++ b/src/validation.cpp
@@ -908,6 +908,27 @@
return MempoolAcceptResult::Failure(ws.m_state);
}
+ const TxId txid = ptx->GetId();
+
+ // Mempool sanity check -- in our new mempool no tx can be added if its
+ // outputs are already spent in the mempool (that is, no children before
+ // parents allowed; the mempool must be consistent at all times).
+ //
+ // This means that on reorg, the disconnectpool *must* always import
+ // the existing mempool tx's, clear the mempool, and then re-add
+ // remaining tx's in topological order via this function. Our new mempool
+ // has fast adds, so this is ok.
+ if (auto it = m_pool.mapNextTx.lower_bound(COutPoint{txid, 0});
+ it != m_pool.mapNextTx.end() && it->first->GetTxId() == txid) {
+ LogPrintf("%s: BUG! PLEASE REPORT THIS! Attempt to add txid %s, but "
+ "its outputs are already spent in the "
+ "mempool\n",
+ __func__, txid.ToString());
+ ws.m_state.Invalid(TxValidationResult::TX_CONFLICT,
+ "txn-mempool-conflict");
+ return MempoolAcceptResult::Failure(ws.m_state);
+ }
+
// Tx was accepted, but not added
if (args.m_test_accept) {
return MempoolAcceptResult::Success(ws.m_vsize, ws.m_base_fees);
@@ -2918,6 +2939,14 @@
bool fBlocksDisconnected = false;
DisconnectedBlockTransactions disconnectpool;
while (m_chain.Tip() && m_chain.Tip() != pindexFork) {
+ if (!fBlocksDisconnected) {
+ // Import and clear mempool; we must do this to preserve
+ // topological ordering in the mempool index. This is ok since
+ // inserts into the mempool are very fast now in our new
+ // implementation.
+ disconnectpool.importMempool(*m_mempool);
+ }
+
if (!DisconnectTip(state, &disconnectpool)) {
// This is likely a fatal error, but keep the mempool consistent,
// just in case. Only remove from the mempool in this case.
@@ -3250,6 +3279,15 @@
return ActivateBestChain(config, state);
}
+namespace {
+// Leverage RAII to run a functor at scope end
+template <typename Func> struct Defer {
+ Func func;
+ Defer(Func &&f) : func(std::move(f)) {}
+ ~Defer() { func(); }
+};
+} // namespace
+
bool Chainstate::UnwindBlock(const Config &config, BlockValidationState &state,
CBlockIndex *pindex, bool invalidate) {
// Genesis block can't be invalidated or parked
@@ -3297,99 +3335,136 @@
}
}
- // Disconnect (descendants of) pindex, and mark them invalid.
- while (true) {
- if (ShutdownRequested()) {
- break;
- }
-
- // Make sure the queue of validation callbacks doesn't grow unboundedly.
- LimitValidationInterfaceQueue();
-
+ {
LOCK(cs_main);
// Lock for as long as disconnectpool is in scope to make sure
// UpdateMempoolForReorg is called after DisconnectTip without unlocking
// in between
LOCK(MempoolMutex());
- if (!m_chain.Contains(pindex)) {
- break;
- }
+ constexpr int maxDisconnectPoolBlocks = 10;
+ bool ret = false;
+ DisconnectedBlockTransactions disconnectpool;
+ // After 10 blocks this becomes nullptr, so that DisconnectTip will
+ // stop giving us unwound block txs if we are doing a deep unwind.
+ DisconnectedBlockTransactions *optDisconnectPool = &disconnectpool;
+
+ // Disable thread safety analysis because we can't require m_mempool->cs
+ // as m_mempool can be null. We keep the runtime analysis though.
+ Defer deferred([&]() NO_THREAD_SAFETY_ANALYSIS {
+ AssertLockHeld(cs_main);
+ if (m_mempool && !disconnectpool.isEmpty()) {
+ AssertLockHeld(m_mempool->cs);
+ // DisconnectTip will add transactions to disconnectpool.
+ // When all unwinding is done and we are on a new tip, we must
+ // add all transactions back to the mempool against the new tip.
+ disconnectpool.updateMempoolForReorg(config, *this,
+ /* fAddToMempool = */ ret,
+ *m_mempool);
+ }
+ });
- pindex_was_in_chain = true;
- CBlockIndex *invalid_walk_tip = m_chain.Tip();
+ // Disconnect (descendants of) pindex, and mark them invalid.
+ while (true) {
+ if (ShutdownRequested()) {
+ break;
+ }
- // ActivateBestChain considers blocks already in m_chain
- // unconditionally valid already, so force disconnect away from it.
+ // Make sure the queue of validation callbacks doesn't grow
+ // unboundedly.
+ // FIXME this commented code is a regression and could cause OOM if
+ // a very old block is invalidated via the invalidateblock RPC.
+ // This can be uncommented if the main signals are moved away from
+ // cs_main or this code is refactored so that cs_main can be
+ // released at this point.
+ //
+ // LimitValidationInterfaceQueue();
+
+ if (!m_chain.Contains(pindex)) {
+ break;
+ }
- DisconnectedBlockTransactions disconnectpool;
+ if (m_mempool && disconnected == 0) {
+ // On first iteration, we grab all the mempool txs to preserve
+ // topological ordering. This has the side-effect of temporarily
+ // clearing the mempool, but we will re-add later in
+ // updateMempoolForReorg() (above). This technique guarantees
+ // mempool consistency as well as ensures that our topological
+ // entry_id index is always correct.
+ disconnectpool.importMempool(*m_mempool);
+ }
- bool ret = DisconnectTip(state, &disconnectpool);
+ pindex_was_in_chain = true;
+ CBlockIndex *invalid_walk_tip = m_chain.Tip();
- // DisconnectTip will add transactions to disconnectpool.
- // Adjust the mempool to be consistent with the new tip, adding
- // transactions back to the mempool if disconnecting was successful,
- // and we're not doing a very deep invalidation (in which case
- // keeping the mempool up to date is probably futile anyway).
- if (m_mempool) {
- disconnectpool.updateMempoolForReorg(
- config, *this,
- /* fAddToMempool = */ (++disconnected <= 10) && ret,
- *m_mempool);
- }
+ // ActivateBestChain considers blocks already in m_chain
+ // unconditionally valid already, so force disconnect away from it.
- if (!ret) {
- return false;
- }
+ ret = DisconnectTip(state, optDisconnectPool);
+ ++disconnected;
- assert(invalid_walk_tip->pprev == m_chain.Tip());
-
- // We immediately mark the disconnected blocks as invalid.
- // This prevents a case where pruned nodes may fail to invalidateblock
- // and be left unable to start as they have no tip candidates (as there
- // are no blocks that meet the "have data and are not invalid per
- // nStatus" criteria for inclusion in setBlockIndexCandidates).
-
- invalid_walk_tip->nStatus =
- invalidate ? invalid_walk_tip->nStatus.withFailed()
- : invalid_walk_tip->nStatus.withParked();
-
- m_blockman.m_dirty_blockindex.insert(invalid_walk_tip);
- setBlockIndexCandidates.insert(invalid_walk_tip->pprev);
-
- if (invalid_walk_tip == to_mark_failed_or_parked->pprev &&
- (invalidate ? to_mark_failed_or_parked->nStatus.hasFailed()
- : to_mark_failed_or_parked->nStatus.isParked())) {
- // We only want to mark the last disconnected block as
- // Failed (or Parked); its children need to be FailedParent (or
- // ParkedParent) instead.
- to_mark_failed_or_parked->nStatus =
- (invalidate
- ? to_mark_failed_or_parked->nStatus.withFailed(false)
- .withFailedParent()
- : to_mark_failed_or_parked->nStatus.withParked(false)
- .withParkedParent());
-
- m_blockman.m_dirty_blockindex.insert(to_mark_failed_or_parked);
- }
-
- // Add any equal or more work headers to setBlockIndexCandidates
- auto candidate_it = candidate_blocks_by_work.lower_bound(
- invalid_walk_tip->pprev->nChainWork);
- while (candidate_it != candidate_blocks_by_work.end()) {
- if (!CBlockIndexWorkComparator()(candidate_it->second,
- invalid_walk_tip->pprev)) {
- setBlockIndexCandidates.insert(candidate_it->second);
- candidate_it = candidate_blocks_by_work.erase(candidate_it);
- } else {
- ++candidate_it;
+ if (optDisconnectPool && disconnected > maxDisconnectPoolBlocks) {
+ // Stop using the disconnect pool after 10 blocks. After 10
+ // blocks we no longer add block tx's to the disconnectpool.
+ // However, when this scope ends we will reconcile what's
+ // in the pool with the new tip (in the deferred d'tor above).
+ optDisconnectPool = nullptr;
+ }
+
+ if (!ret) {
+ return false;
+ }
+
+ assert(invalid_walk_tip->pprev == m_chain.Tip());
+
+ // We immediately mark the disconnected blocks as invalid.
+ // This prevents a case where pruned nodes may fail to
+ // invalidateblock and be left unable to start as they have no tip
+ // candidates (as there are no blocks that meet the "have data and
+ // are not invalid per nStatus" criteria for inclusion in
+ // setBlockIndexCandidates).
+
+ invalid_walk_tip->nStatus =
+ invalidate ? invalid_walk_tip->nStatus.withFailed()
+ : invalid_walk_tip->nStatus.withParked();
+
+ m_blockman.m_dirty_blockindex.insert(invalid_walk_tip);
+ setBlockIndexCandidates.insert(invalid_walk_tip->pprev);
+
+ if (invalid_walk_tip == to_mark_failed_or_parked->pprev &&
+ (invalidate ? to_mark_failed_or_parked->nStatus.hasFailed()
+ : to_mark_failed_or_parked->nStatus.isParked())) {
+ // We only want to mark the last disconnected block as
+ // Failed (or Parked); its children need to be FailedParent (or
+ // ParkedParent) instead.
+ to_mark_failed_or_parked->nStatus =
+ (invalidate
+ ? to_mark_failed_or_parked->nStatus.withFailed(false)
+ .withFailedParent()
+ : to_mark_failed_or_parked->nStatus.withParked(false)
+ .withParkedParent());
+
+ m_blockman.m_dirty_blockindex.insert(to_mark_failed_or_parked);
+ }
+
+ // Add any equal or more work headers to setBlockIndexCandidates
+ auto candidate_it = candidate_blocks_by_work.lower_bound(
+ invalid_walk_tip->pprev->nChainWork);
+ while (candidate_it != candidate_blocks_by_work.end()) {
+ if (!CBlockIndexWorkComparator()(candidate_it->second,
+ invalid_walk_tip->pprev)) {
+ setBlockIndexCandidates.insert(candidate_it->second);
+ candidate_it = candidate_blocks_by_work.erase(candidate_it);
+ } else {
+ ++candidate_it;
+ }
}
- }
- // Track the last disconnected block, so we can correct its
- // FailedParent (or ParkedParent) status in future iterations, or, if
- // it's the last one, call InvalidChainFound on it.
- to_mark_failed_or_parked = invalid_walk_tip;
+ // Track the last disconnected block, so we can correct its
+ // FailedParent (or ParkedParent) status in future iterations, or,
+ // if it's the last one, call InvalidChainFound on it.
+ to_mark_failed_or_parked = invalid_walk_tip;
+ }
}
CheckBlockIndex();
diff --git a/test/functional/interface_zmq.py b/test/functional/interface_zmq.py
--- a/test/functional/interface_zmq.py
+++ b/test/functional/interface_zmq.py
@@ -306,6 +306,9 @@
hashtx.receive().hex(),
self.nodes[1].getblock(
connect_blocks[1])["tx"][0])
+ # And the payment transaction again due to mempool entry (it was removed
+ # from the mempool due to the reorg)
+ assert_equal(hashtx.receive().hex(), payment_txid)
# And the current tip
assert_equal(
hashtx.receive().hex(),
@@ -473,6 +476,9 @@
assert self.nodes[0].getrawmempool(
mempool_sequence=True)["mempool_sequence"] > seq_num
+ assert_equal((payment_txid_2, "R", seq_num),
+ seq.receive_sequence())
+ seq_num += 1
assert_equal((best_hash, "D", None), seq.receive_sequence())
assert_equal((payment_txid, "A", seq_num), seq.receive_sequence())
seq_num += 1
diff --git a/test/functional/mempool_updatefromblock.py b/test/functional/mempool_updatefromblock.py
--- a/test/functional/mempool_updatefromblock.py
+++ b/test/functional/mempool_updatefromblock.py
@@ -17,14 +17,13 @@
class MempoolUpdateFromBlockTest(BitcoinTestFramework):
def set_test_params(self):
self.num_nodes = 1
- self.limitancestorcount = 60
- self.limitdescendantcount = 15
+ self.limit_ancestor_descendant_count = 60
self.extra_args = [
[
'-limitdescendantsize=5000',
'-limitancestorsize=5000',
- f'-limitancestorcount={self.limitancestorcount}',
- f'-limitdescendantcount={self.limitdescendantcount}',
+ f'-limitancestorcount={self.limit_ancestor_descendant_count}',
+ f'-limitdescendantcount={self.limit_ancestor_descendant_count}',
],
]
@@ -153,12 +152,16 @@
assert_equal(entry['ancestorsize'], sum(tx_size[0:(k + 1)]))
def run_test(self):
- # Use batch size limited to self.limitdescendantcount to not fire
- # "too many unconfirmed descendants" error.
+ # Mine the transactions in batches so we get reorg_depth blocks
+ # reorg'ed
+ reorg_depth = 4
self.transaction_graph_test(
- size=self.limitancestorcount,
- n_tx_to_mine=range(0, self.limitancestorcount,
- self.limitdescendantcount),
+ size=self.limit_ancestor_descendant_count,
+ n_tx_to_mine=range(
+ 0,
+ self.limit_ancestor_descendant_count,
+ self.limit_ancestor_descendant_count // reorg_depth,
+ ),
)