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,71 @@ SetMockTime(0); } +void CheckDisconnectPoolSort(DisconnectedBlockTransactions &disconnectPool, + std::vector correctlyOrderedIds) { + 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() == correctlyOrderedIds[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); + } + + // Tests the 5 transactions in the following 6 different orders. The + // first 3 txns simulate once confirmed transactions. The last 2 simulate a + // chain of unconfirmed ones. + unsigned int tests[6][5] = {{1, 2, 0, 4, 3}, {1, 2, 0, 3, 4}, + {0, 1, 2, 4, 3}, {0, 1, 2, 3, 4}, + {2, 1, 0, 4, 3}, {2, 1, 0, 3, 4}}; + for (unsigned int i = 0; i < 6; i++) { + // The first 3 transactions go in different orders to addForBlock, which + // sorts them into disconnectPool. They simulate transactions that were + // once confirmed in a block in not necessarily topological order + std::vector vtx = { + MakeTransactionRef(chainedTxn[tests[i][0]]), + MakeTransactionRef(chainedTxn[tests[i][1]]), + MakeTransactionRef(chainedTxn[tests[i][2]])}; + 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 different orders into testPool, + // simulating a chain of unconfirmed txn + testPool.addUnchecked(ids[tests[i][3]], + entry.FromTx(chainedTxn[tests[i][3]])); + testPool.addUnchecked(ids[tests[i][4]], + entry.FromTx(chainedTxn[tests[i][4]])); + + // 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); diff --git a/src/txmempool.cpp b/src/txmempool.cpp --- a/src/txmempool.cpp +++ b/src/txmempool.cpp @@ -1321,6 +1321,38 @@ } } +void DisconnectedBlockTransactions::importMempool(CTxMemPool &pool) { + 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);