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::iterator a, std::set::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 #include #include +#include #include #include @@ -93,6 +94,9 @@ typedef std::set Children; private: + //! Unique identifier -- used for topological sorting + uint64_t entryId = 0; + const CTransactionRef tx; mutable Parents m_parents; mutable Children m_children; @@ -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, boost::multi_index::identity, - CompareTxMemPoolEntryByEntryTime>>> + CompareTxMemPoolEntryByEntryTime>, + // sorted topologically (insertion order) + boost::multi_index::ordered_unique< + boost::multi_index::tag, + boost::multi_index::identity, + CompareTxMemPoolEntryByEntryId>>> indexed_transaction_set; /** @@ -460,16 +449,11 @@ EXCLUSIVE_LOCKS_REQUIRED(cs); private: - typedef std::map 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 - 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 filter_final_and_mature) - EXCLUSIVE_LOCKS_REQUIRED(cs, cs_main); void removeConflicts(const CTransaction &tx) EXCLUSIVE_LOCKS_REQUIRED(cs); void removeForBlock(const std::vector &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 &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 &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 &setExclude, - std::set &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, 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; + /// 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().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 #include #include +#include #include #include #include @@ -123,131 +124,6 @@ lockPoints = lp; } -void CTxMemPool::UpdateForDescendants(txiter updateIt, - cacheMap &cachedDescendants, - const std::set &setExclude, - std::set &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 &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 setAlreadyIncluded(txidsToUpdate.begin(), - txidsToUpdate.end()); - - std::set 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 = 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().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 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(&active_coins_tip)); - for (const auto &it : GetSortedDepthAndScore()) { + const auto &index = mapTx.get(); + 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::GetSortedDepthAndScore() const { - std::vector 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 &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()) { + vtxid.push_back(entry.GetTx().GetId()); } } @@ -978,12 +799,13 @@ std::vector CTxMemPool::infoAll() const { LOCK(cs); - auto iters = GetSortedDepthAndScore(); std::vector ret; ret.reserve(mapTx.size()); - for (auto it : iters) { - ret.push_back(GetInfo(it)); + + const auto &index = mapTx.get(); + 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 vtx; vtx.reserve(pool.mapTx.size()); - for (const CTxMemPoolEntry &e : pool.mapTx.get()) { + txInfo.reserve(pool.mapTx.size()); + for (const CTxMemPoolEntry &e : pool.mapTx.get()) { 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 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())) { - // 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())) { + 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 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, + ), )