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 @@ -8,6 +8,7 @@ #include "test/test_bitcoin.h" +#include "reverse_iterator.h" #include #include #include @@ -793,4 +794,60 @@ SetMockTime(0); } +void CheckDisconnectPoolSort(DisconnectedBlockTransactions &disconnectPool, + std::vector ids) { + unsigned int i = 0; + // 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() == ids[i]); + i++; + } +} + +BOOST_AUTO_TEST_CASE(TestImportMempool) { + CTxMemPool testPool; + DisconnectedBlockTransactions disconnectPool; + TestMemPoolEntryHelper entry; + CMutableTransaction chainedTxn[5]; + std::vector ids; + COutPoint lastOutpoint; + + // Construct a chain of 5 transactions + for (unsigned int i = 0; i < 5; i++) { + chainedTxn[i].vin.emplace_back(lastOutpoint); + chainedTxn[i].vout.emplace_back(10 * SATOSHI, CScript() << OP_TRUE); + ids.push_back(chainedTxn[i].GetId()); + lastOutpoint = COutPoint(ids[i], 0); + } + + // The first 3 transactions go in mixed order into disconnectPool via + // addForBlock. They simulate transactions that were once confirmed in a + // block in non-topological order + std::vector vtx = {MakeTransactionRef(chainedTxn[1]), + MakeTransactionRef(chainedTxn[2]), + MakeTransactionRef(chainedTxn[0])}; + disconnectPool.addForBlock(vtx); + BOOST_CHECK_EQUAL(disconnectPool.GetQueuedTx().size(), 3); + CheckDisconnectPoolSort(disconnectPool, ids); + + // If the mempool is empty, importMempool doesn't change disconnectPool + disconnectPool.importMempool(testPool); + BOOST_CHECK_EQUAL(disconnectPool.GetQueuedTx().size(), 3); + CheckDisconnectPoolSort(disconnectPool, ids); + + // The last 2 transactions go in inverted order into testPool, simulating a + // chain of unconfirmed txn + testPool.addUnchecked(ids[4], entry.FromTx(chainedTxn[4])); + testPool.addUnchecked(ids[3], entry.FromTx(chainedTxn[3])); + + // Now we test importMempool with a 2 items mempool + disconnectPool.importMempool(testPool); + BOOST_CHECK_EQUAL(testPool.size(), 0); + BOOST_CHECK_EQUAL(disconnectPool.GetQueuedTx().size(), 5); + CheckDisconnectPoolSort(disconnectPool, ids); + 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); @@ -920,6 +929,8 @@ queuedTx.get().erase(entry); } + bool isEmpty() { return queuedTx.empty(); } + void clear() { cachedInnerUsage = 0; queuedTx.clear(); diff --git a/src/txmempool.cpp b/src/txmempool.cpp --- a/src/txmempool.cpp +++ b/src/txmempool.cpp @@ -1321,6 +1321,39 @@ } } +void DisconnectedBlockTransactions::importMempool(CTxMemPool &pool) { + // pool.cs is probably locked already, but re-take it anyway + LOCK(pool.cs); + // 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 + DisconnectedBlockTransactions ordered_mempool; + std::vector vtx; + vtx.reserve(pool.mapTx.size()); + // We copy 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 + for (const CTxMemPoolEntry &e : pool.mapTx.get()) { + vtx.push_back(e.GetSharedTx()); + } + pool.clear(); + ordered_mempool.addForBlock(vtx); + cachedInnerUsage += ordered_mempool.cachedInnerUsage; + queuedTx.get().splice( + queuedTx.get().begin(), + ordered_mempool.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 + auto it = queuedTx.get().begin(); + removeEntry(it); + } +} + void DisconnectedBlockTransactions::updateMempoolForReorg(const Config &config, bool fAddToMempool) { AssertLockHeld(cs_main);