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,75 @@ 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) { + unsigned int i = 0; + BOOST_CHECK_EQUAL(disconnectPool.GetQueuedTx().size(), expectedSize); + assert(correctlyOrderedIds.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++; + } +} + +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); + } + + // Tests the chained transactions in the following different orders. The + // first 3 txns simulate once confirmed transactions. The last 2 simulate a + // chain of unconfirmed ones. + const int tests_len = 6; + const int tests[tests_len][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 (int i = 0; i < tests_len; i++) { + // index holds the ordering information for this test + const int *indexes = tests[i]; + DisconnectedBlockTransactions disconnectPool; + // 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 + disconnectPool.addForBlock(std::vector( + {MakeTransactionRef(chainedTxn[indexes[0]]), + MakeTransactionRef(chainedTxn[indexes[1]]), + MakeTransactionRef(chainedTxn[indexes[2]])})); + CheckDisconnectPoolOrder(disconnectPool, correctlyOrderedIds, 3); + + // If the mempool is empty, importMempool doesn't change disconnectPool + CTxMemPool testPool; + disconnectPool.importMempool(testPool); + CheckDisconnectPoolOrder(disconnectPool, correctlyOrderedIds, 3); + + // The last 2 transactions go in different orders into testPool, + // simulating a chain of unconfirmed txn + TestMemPoolEntryHelper entry; + testPool.addUnchecked(chainedTxn[indexes[3]].GetId(), + entry.FromTx(chainedTxn[indexes[3]])); + testPool.addUnchecked(chainedTxn[indexes[4]].GetId(), + entry.FromTx(chainedTxn[indexes[4]])); + + // Now we test importMempool with a 2 items mempool + disconnectPool.importMempool(testPool); + BOOST_CHECK_EQUAL(testPool.size(), 0); + CheckDisconnectPoolOrder(disconnectPool, correctlyOrderedIds, 5); + 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,40 @@ } } +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 + // 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; + vtx.reserve(pool.mapTx.size()); + for (const CTxMemPoolEntry &e : pool.mapTx.get()) { + vtx.push_back(std::move(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);