Merge pull request #5267

34318d7 RPC-test based on invalidateblock for mempool coinbase spends (Gavin Andresen)
7fd6219 Make CTxMemPool::remove more effecient by avoiding recursion (Matt Corallo)
b7b4318 Make CTxMemPool::check more thourough by using CheckInputs (Matt Corallo)
723d12c Remove txn which are invalidated by coinbase maturity during reorg (Matt Corallo)
868d041 Remove coinbase-dependant transactions during reorg. (Matt Corallo)

5 files changed, 171 insertions, 15 deletions

diff --git a/qa/pull-tester/rpc-tests.sh b/qa/pull-tester/rpc-tests.sh
index 071935759b..d6ee00bb7d 100755
--- a/qa/pull-tester/rpc-tests.sh
+++ b/qa/pull-tester/rpc-tests.sh
@@ -25,6 +25,7 @@ if [ "x${ENABLE_BITCOIND}${ENABLE_UTILS}${ENABLE_WALLET}" = "x111" ]; then
   ${BUILDDIR}/qa/rpc-tests/rest.py --srcdir "${BUILDDIR}/src"
   ${BUILDDIR}/qa/rpc-tests/mempool_spendcoinbase.py --srcdir "${BUILDDIR}/src"
   ${BUILDDIR}/qa/rpc-tests/httpbasics.py --srcdir "${BUILDDIR}/src"
+  ${BUILDDIR}/qa/rpc-tests/mempool_coinbase_spends.py --srcdir "${BUILDDIR}/src"
   #${BUILDDIR}/qa/rpc-tests/forknotify.py --srcdir "${BUILDDIR}/src"
 else
   echo "No rpc tests to run. Wallet, utils, and bitcoind must all be enabled"
diff --git a/qa/rpc-tests/mempool_coinbase_spends.py b/qa/rpc-tests/mempool_coinbase_spends.py
new file mode 100755
index 0000000000..7b43712768
--- /dev/null
+++ b/qa/rpc-tests/mempool_coinbase_spends.py
@@ -0,0 +1,94 @@
+#!/usr/bin/env python2
+# Copyright (c) 2014 The Bitcoin Core developers
+# Distributed under the MIT software license, see the accompanying
+# file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#
+# Test re-org scenarios with a mempool that contains transactions
+# that spend (directly or indirectly) coinbase transactions.
+#
+
+from test_framework import BitcoinTestFramework
+from bitcoinrpc.authproxy import AuthServiceProxy, JSONRPCException
+from util import *
+import os
+import shutil
+
+# Create one-input, one-output, no-fee transaction:
+class MempoolCoinbaseTest(BitcoinTestFramework):
+
+    alert_filename = None  # Set by setup_network
+
+    def setup_network(self):
+        args = ["-checkmempool", "-debug=mempool"]
+        self.nodes = []
+        self.nodes.append(start_node(0, self.options.tmpdir, args))
+        self.nodes.append(start_node(1, self.options.tmpdir, args))
+        connect_nodes(self.nodes[1], 0)
+        self.is_network_split = False
+        self.sync_all
+
+    def create_tx(self, from_txid, to_address, amount):
+        inputs = [{ "txid" : from_txid, "vout" : 0}]
+        outputs = { to_address : amount }
+        rawtx = self.nodes[0].createrawtransaction(inputs, outputs)
+        signresult = self.nodes[0].signrawtransaction(rawtx)
+        assert_equal(signresult["complete"], True)
+        return signresult["hex"]
+
+    def run_test(self):
+        start_count = self.nodes[0].getblockcount()
+
+        # Mine three blocks. After this, nodes[0] blocks
+        # 101, 102, and 103 are spend-able.
+        new_blocks = self.nodes[1].setgenerate(True, 4)
+        self.sync_all()
+
+        node0_address = self.nodes[0].getnewaddress()
+        node1_address = self.nodes[1].getnewaddress()
+
+        # Three scenarios for re-orging coinbase spends in the memory pool:
+        # 1. Direct coinbase spend  :  spend_101
+        # 2. Indirect (coinbase spend in chain, child in mempool) : spend_102 and spend_102_1
+        # 3. Indirect (coinbase and child both in chain) : spend_103 and spend_103_1
+        # Use invalidatblock to make all of the above coinbase spends invalid (immature coinbase),
+        # and make sure the mempool code behaves correctly.
+        b = [ self.nodes[0].getblockhash(n) for n in range(102, 105) ]
+        coinbase_txids = [ self.nodes[0].getblock(h)['tx'][0] for h in b ]
+        spend_101_raw = self.create_tx(coinbase_txids[0], node1_address, 50)
+        spend_102_raw = self.create_tx(coinbase_txids[1], node0_address, 50)
+        spend_103_raw = self.create_tx(coinbase_txids[2], node0_address, 50)
+
+        # Broadcast and mine spend_102 and 103:
+        spend_102_id = self.nodes[0].sendrawtransaction(spend_102_raw)
+        spend_103_id = self.nodes[0].sendrawtransaction(spend_103_raw)
+        self.nodes[0].setgenerate(True, 1)
+
+        # Create 102_1 and 103_1:
+        spend_102_1_raw = self.create_tx(spend_102_id, node1_address, 50)
+        spend_103_1_raw = self.create_tx(spend_103_id, node1_address, 50)
+
+        # Broadcast and mine 103_1:
+        spend_103_1_id = self.nodes[0].sendrawtransaction(spend_103_1_raw)
+        self.nodes[0].setgenerate(True, 1)
+
+        # ... now put spend_101 and spend_102_1 in memory pools:
+        spend_101_id = self.nodes[0].sendrawtransaction(spend_101_raw)
+        spend_102_1_id = self.nodes[0].sendrawtransaction(spend_102_1_raw)
+
+        self.sync_all()
+
+        assert_equal(set(self.nodes[0].getrawmempool()), set([ spend_101_id, spend_102_1_id ]))
+
+        # Use invalidateblock to re-org back and make all those coinbase spends
+        # immature/invalid:
+        for node in self.nodes:
+            node.invalidateblock(new_blocks[0])
+
+        self.sync_all()
+
+        # mempool should be empty.
+        assert_equal(set(self.nodes[0].getrawmempool()), set())
+
+if __name__ == '__main__':
+    MempoolCoinbaseTest().main()
diff --git a/src/main.cpp b/src/main.cpp
index 70e3973e6c..9e1c41ada7 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -1892,10 +1892,10 @@ bool static DisconnectTip(CValidationState &state) {
         // ignore validation errors in resurrected transactions
         list<CTransaction> removed;
         CValidationState stateDummy;
-        if (!tx.IsCoinBase())
-            if (!AcceptToMemoryPool(mempool, stateDummy, tx, false, NULL))
-                mempool.remove(tx, removed, true);
+        if (tx.IsCoinBase() || !AcceptToMemoryPool(mempool, stateDummy, tx, false, NULL))
+            mempool.remove(tx, removed, true);
     }
+    mempool.removeCoinbaseSpends(pcoinsTip, pindexDelete->nHeight);
     mempool.check(pcoinsTip);
     // Update chainActive and related variables.
     UpdateTip(pindexDelete->pprev);
diff --git a/src/txmempool.cpp b/src/txmempool.cpp
index e13f1cc350..840eb536ba 100644
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -6,6 +6,7 @@
 #include "txmempool.h"
 
 #include "clientversion.h"
+#include "main.h"
 #include "streams.h"
 #include "util.h"
 #include "utilmoneystr.h"
@@ -426,26 +427,32 @@ bool CTxMemPool::addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry)
 }
 
 
-void CTxMemPool::remove(const CTransaction &tx, std::list<CTransaction>& removed, bool fRecursive)
+void CTxMemPool::remove(const CTransaction &origTx, std::list<CTransaction>& removed, bool fRecursive)
 {
     // Remove transaction from memory pool
     {
         LOCK(cs);
-        uint256 hash = tx.GetHash();
-        if (fRecursive) {
-            for (unsigned int i = 0; i < tx.vout.size(); i++) {
-                std::map<COutPoint, CInPoint>::iterator it = mapNextTx.find(COutPoint(hash, i));
-                if (it == mapNextTx.end())
-                    continue;
-                remove(*it->second.ptx, removed, true);
-            }
-        }
-        if (mapTx.count(hash))
+        std::deque<uint256> txToRemove;
+        txToRemove.push_back(origTx.GetHash());
+        while (!txToRemove.empty())
         {
-            removed.push_front(tx);
+            uint256 hash = txToRemove.front();
+            txToRemove.pop_front();
+            if (!mapTx.count(hash))
+                continue;
+            const CTransaction& tx = mapTx[hash].GetTx();
+            if (fRecursive) {
+                for (unsigned int i = 0; i < tx.vout.size(); i++) {
+                    std::map<COutPoint, CInPoint>::iterator it = mapNextTx.find(COutPoint(hash, i));
+                    if (it == mapNextTx.end())
+                        continue;
+                    txToRemove.push_back(it->second.ptx->GetHash());
+                }
+            }
             BOOST_FOREACH(const CTxIn& txin, tx.vin)
                 mapNextTx.erase(txin.prevout);
 
+            removed.push_back(tx);
             totalTxSize -= mapTx[hash].GetTxSize();
             mapTx.erase(hash);
             nTransactionsUpdated++;
@@ -453,6 +460,31 @@ void CTxMemPool::remove(const CTransaction &tx, std::list<CTransaction>& removed
     }
 }
 
+void CTxMemPool::removeCoinbaseSpends(const CCoinsViewCache *pcoins, unsigned int nMemPoolHeight)
+{
+    // Remove transactions spending a coinbase which are now immature
+    LOCK(cs);
+    list<CTransaction> transactionsToRemove;
+    for (std::map<uint256, CTxMemPoolEntry>::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
+        const CTransaction& tx = it->second.GetTx();
+        BOOST_FOREACH(const CTxIn& txin, tx.vin) {
+            std::map<uint256, CTxMemPoolEntry>::const_iterator it2 = mapTx.find(txin.prevout.hash);
+            if (it2 != mapTx.end())
+                continue;
+            const CCoins *coins = pcoins->AccessCoins(txin.prevout.hash);
+            if (fSanityCheck) assert(coins);
+            if (!coins || (coins->IsCoinBase() && nMemPoolHeight - coins->nHeight < COINBASE_MATURITY)) {
+                transactionsToRemove.push_back(tx);
+                break;
+            }
+        }
+    }
+    BOOST_FOREACH(const CTransaction& tx, transactionsToRemove) {
+        list<CTransaction> removed;
+        remove(tx, removed, true);
+    }
+}
+
 void CTxMemPool::removeConflicts(const CTransaction &tx, std::list<CTransaction>& removed)
 {
     // Remove transactions which depend on inputs of tx, recursively
@@ -513,17 +545,22 @@ void CTxMemPool::check(const CCoinsViewCache *pcoins) const
 
     uint64_t checkTotal = 0;
 
+    CCoinsViewCache mempoolDuplicate(const_cast<CCoinsViewCache*>(pcoins));
+
     LOCK(cs);
+    list<const CTxMemPoolEntry*> waitingOnDependants;
     for (std::map<uint256, CTxMemPoolEntry>::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
         unsigned int i = 0;
         checkTotal += it->second.GetTxSize();
         const CTransaction& tx = it->second.GetTx();
+        bool fDependsWait = false;
         BOOST_FOREACH(const CTxIn &txin, tx.vin) {
             // Check that every mempool transaction's inputs refer to available coins, or other mempool tx's.
             std::map<uint256, CTxMemPoolEntry>::const_iterator it2 = mapTx.find(txin.prevout.hash);
             if (it2 != mapTx.end()) {
                 const CTransaction& tx2 = it2->second.GetTx();
                 assert(tx2.vout.size() > txin.prevout.n && !tx2.vout[txin.prevout.n].IsNull());
+                fDependsWait = true;
             } else {
                 const CCoins* coins = pcoins->AccessCoins(txin.prevout.hash);
                 assert(coins && coins->IsAvailable(txin.prevout.n));
@@ -535,6 +572,29 @@ void CTxMemPool::check(const CCoinsViewCache *pcoins) const
             assert(it3->second.n == i);
             i++;
         }
+        if (fDependsWait)
+            waitingOnDependants.push_back(&it->second);
+        else {
+            CValidationState state; CTxUndo undo;
+            assert(CheckInputs(tx, state, mempoolDuplicate, false, 0, false, NULL));
+            UpdateCoins(tx, state, mempoolDuplicate, undo, 1000000);
+        }
+    }
+    unsigned int stepsSinceLastRemove = 0;
+    while (!waitingOnDependants.empty()) {
+        const CTxMemPoolEntry* entry = waitingOnDependants.front();
+        waitingOnDependants.pop_front();
+        CValidationState state;
+        if (!mempoolDuplicate.HaveInputs(entry->GetTx())) {
+            waitingOnDependants.push_back(entry);
+            stepsSinceLastRemove++;
+            assert(stepsSinceLastRemove < waitingOnDependants.size());
+        } else {
+            assert(CheckInputs(entry->GetTx(), state, mempoolDuplicate, false, 0, false, NULL));
+            CTxUndo undo;
+            UpdateCoins(entry->GetTx(), state, mempoolDuplicate, undo, 1000000);
+            stepsSinceLastRemove = 0;
+        }
     }
     for (std::map<COutPoint, CInPoint>::const_iterator it = mapNextTx.begin(); it != mapNextTx.end(); it++) {
         uint256 hash = it->second.ptx->GetHash();
diff --git a/src/txmempool.h b/src/txmempool.h
index d00bdd0616..f671352b58 100644
--- a/src/txmempool.h
+++ b/src/txmempool.h
@@ -113,6 +113,7 @@ public:
 
     bool addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry);
     void remove(const CTransaction &tx, std::list<CTransaction>& removed, bool fRecursive = false);
+    void removeCoinbaseSpends(const CCoinsViewCache *pcoins, unsigned int nMemPoolHeight);
     void removeConflicts(const CTransaction &tx, std::list<CTransaction>& removed);
     void removeForBlock(const std::vector<CTransaction>& vtx, unsigned int nBlockHeight,
                         std::list<CTransaction>& conflicts);