diff --git a/src/test/mempool_tests.cpp b/src/test/mempool_tests.cpp --- a/src/test/mempool_tests.cpp +++ b/src/test/mempool_tests.cpp @@ -3,6 +3,7 @@ // file COPYING or http://www.opensource.org/licenses/mit-license.php. #include "policy/policy.h" +#include "reverse_iterator.h" #include "txmempool.h" #include "util.h" @@ -793,4 +794,94 @@ SetMockTime(0); } +// expectedSize can be smaller than correctlyOrderedIds.size(), since we +// might be testing intermediary states. Just avoiding some slice operations, +void CheckDisconnectPoolOrder(DisconnectedBlockTransactions &disconnectPool, + std::vector correctlyOrderedIds, + unsigned int expectedSize) { + int i = 0; + BOOST_CHECK_EQUAL(disconnectPool.GetQueuedTx().size(), expectedSize); + // Txns in queuedTx's insertion_order index are sorted from children to + // parent txn + for (const CTransactionRef &tx : + reverse_iterate(disconnectPool.GetQueuedTx().get())) { + BOOST_CHECK(tx->GetId() == correctlyOrderedIds[i]); + i++; + } +} + +typedef std::vector vecptx; + +BOOST_AUTO_TEST_CASE(TestImportMempool) { + CMutableTransaction chainedTxn[5]; + std::vector correctlyOrderedIds; + COutPoint lastOutpoint; + + // Construct a chain of 5 transactions + for (int i = 0; i < 5; i++) { + chainedTxn[i].vin.emplace_back(lastOutpoint); + chainedTxn[i].vout.emplace_back(10 * SATOSHI, CScript() << OP_TRUE); + correctlyOrderedIds.push_back(chainedTxn[i].GetId()); + lastOutpoint = COutPoint(correctlyOrderedIds[i], 0); + } + + // The first 3 txns simulate once confirmed transactions that have been + // disconnected. We test 3 different orders: in order, one case of mixed + // order and inverted order. + vecptx disconnectedTxnsInOrder = {&chainedTxn[0], &chainedTxn[1], + &chainedTxn[2]}; + vecptx disconnectedTxnsMixedOrder = {&chainedTxn[1], &chainedTxn[2], + &chainedTxn[0]}; + vecptx disconnectedTxnsInvertedOrder = {&chainedTxn[2], &chainedTxn[1], + &chainedTxn[0]}; + + // The last 2 txns simulate a chain of unconfirmed transactions in the + // mempool. We test 2 different orders: in and out of order. + vecptx unconfTxnsInOrder = {&chainedTxn[3], &chainedTxn[4]}; + vecptx unconfTxnsOutOfOrder = {&chainedTxn[4], &chainedTxn[3]}; + + // Now we test all combinations of the previously defined orders for + // disconnected and unconfirmed txns. The expected outcome is to have these + // transactions in the correct order in queuedTx, as defined in + // correctlyOrderedIds. + for (auto &disconnectedTxns : + {disconnectedTxnsInOrder, disconnectedTxnsMixedOrder, + disconnectedTxnsInvertedOrder}) { + for (auto &unconfTxns : {unconfTxnsInOrder, unconfTxnsOutOfOrder}) { + // addForBlock inserts disconnectTxns in disconnectPool. They + // simulate transactions that were once confirmed in a block + std::vector vtx; + for (auto tx : disconnectedTxns) { + vtx.push_back(MakeTransactionRef(*tx)); + } + DisconnectedBlockTransactions disconnectPool; + disconnectPool.addForBlock(vtx); + CheckDisconnectPoolOrder(disconnectPool, correctlyOrderedIds, + disconnectedTxns.size()); + + // If the mempool is empty, importMempool doesn't change + // disconnectPool + CTxMemPool testPool; + disconnectPool.importMempool(testPool); + CheckDisconnectPoolOrder(disconnectPool, correctlyOrderedIds, + disconnectedTxns.size()); + + // Add all unconfirmed transactions in testPool + for (auto tx : unconfTxns) { + TestMemPoolEntryHelper entry; + testPool.addUnchecked(tx->GetId(), entry.FromTx(*tx)); + } + + // Now we test importMempool with a non empty mempool + disconnectPool.importMempool(testPool); + CheckDisconnectPoolOrder(disconnectPool, correctlyOrderedIds, + disconnectedTxns.size() + + unconfTxns.size()); + // We must clear disconnectPool to not trigger the assert in its + // destructor + disconnectPool.clear(); + } + } +} + BOOST_AUTO_TEST_SUITE_END() diff --git a/src/txmempool.h b/src/txmempool.h --- a/src/txmempool.h +++ b/src/txmempool.h @@ -844,6 +844,10 @@ * Instead, store the disconnected transactions (in order!) as we go, remove any * that are included in blocks in the new chain, and then process the remaining * still-unconfirmed transactions at the end. + * + * It also enables efficient reprocessing of current mempool entries, useful + * when (de)activating forks that result in in-mempool transactions becoming + * invalid */ // multi_index tag names struct txid_index {}; @@ -894,6 +898,11 @@ return queuedTx; } + // Import mempool entries in topological order into queuedTx and clear the + // mempool. Caller should call updateMempoolForReorg to reprocess these + // transactions + void importMempool(CTxMemPool &pool); + // Add entries for a block while reconstructing the topological ordering so // they can be added back to the mempool simply. void addForBlock(const std::vector &vtx); diff --git a/src/txmempool.cpp b/src/txmempool.cpp --- a/src/txmempool.cpp +++ b/src/txmempool.cpp @@ -1321,6 +1321,43 @@ } } +void DisconnectedBlockTransactions::importMempool(CTxMemPool &pool) { + // addForBlock's algorithm sorts a vector of transactions back into + // topological order. We use it in a separate object to create a valid + // ordering of all mempool transactions, which we then splice in front of + // the current queuedTx. This results in a valid sequence of transactions to + // be reprocessed in updateMempoolForReorg. + + // We create vtx in order of the entry_time index to facilitate for + // addForBlocks (which iterates in reverse order), as vtx probably end in + // the correct ordering for queuedTx. + std::vector vtx; + { + LOCK(pool.cs); + vtx.reserve(pool.mapTx.size()); + for (const CTxMemPoolEntry &e : pool.mapTx.get()) { + vtx.push_back(e.GetSharedTx()); + } + pool.clear(); + } + + // Use addForBlocks to sort the transactions and then splice them in front + // of queuedTx + DisconnectedBlockTransactions orderedTxnPool; + orderedTxnPool.addForBlock(vtx); + cachedInnerUsage += orderedTxnPool.cachedInnerUsage; + queuedTx.get().splice( + queuedTx.get().begin(), + orderedTxnPool.queuedTx.get()); + + // We limit memory usage because we can't know if more blocks will be + // disconnected + while (DynamicMemoryUsage() > MAX_DISCONNECTED_TX_POOL_SIZE) { + // Drop the earliest entry which, by definition, has no children + removeEntry(queuedTx.get().begin()); + } +} + void DisconnectedBlockTransactions::updateMempoolForReorg(const Config &config, bool fAddToMempool) { AssertLockHeld(cs_main);