diff options
| -rw-r--r-- | src/coins.cpp | 37 | ||||
| -rw-r--r-- | src/coins.h | 5 | ||||
| -rw-r--r-- | src/test/coins_tests.cpp | 199 | ||||
| -rw-r--r-- | src/validation.cpp | 2 |
4 files changed, 181 insertions, 62 deletions
diff --git a/src/coins.cpp b/src/coins.cpp index 8ff652b474..fe474fdda2 100644 --- a/src/coins.cpp +++ b/src/coins.cpp @@ -117,17 +117,37 @@ CCoinsModifier CCoinsViewCache::ModifyCoins(const uint256 &txid) { return CCoinsModifier(*this, ret.first, cachedCoinUsage); } -// ModifyNewCoins has to know whether the new outputs its creating are for a -// coinbase or not. If they are for a coinbase, it can not mark them as fresh. -// This is to ensure that the historical duplicate coinbases before BIP30 was -// in effect will still be properly overwritten when spent. +/* ModifyNewCoins allows for faster coin modification when creating the new + * outputs from a transaction. It assumes that BIP 30 (no duplicate txids) + * applies and has already been tested for (or the test is not required due to + * BIP 34, height in coinbase). If we can assume BIP 30 then we know that any + * non-coinbase transaction we are adding to the UTXO must not already exist in + * the utxo unless it is fully spent. Thus we can check only if it exists DIRTY + * at the current level of the cache, in which case it is not safe to mark it + * FRESH (b/c then its spentness still needs to flushed). If it's not dirty and + * doesn't exist or is pruned in the current cache, we know it either doesn't + * exist or is pruned in parent caches, which is the definition of FRESH. The + * exception to this is the two historical violations of BIP 30 in the chain, + * both of which were coinbases. We do not mark these fresh so we we can ensure + * that they will still be properly overwritten when spent. + */ CCoinsModifier CCoinsViewCache::ModifyNewCoins(const uint256 &txid, bool coinbase) { assert(!hasModifier); std::pair<CCoinsMap::iterator, bool> ret = cacheCoins.insert(std::make_pair(txid, CCoinsCacheEntry())); - ret.first->second.coins.Clear(); if (!coinbase) { - ret.first->second.flags = CCoinsCacheEntry::FRESH; + // New coins must not already exist. + if (!ret.first->second.coins.IsPruned()) + throw std::logic_error("ModifyNewCoins should not find pre-existing coins on a non-coinbase unless they are pruned!"); + + if (!(ret.first->second.flags & CCoinsCacheEntry::DIRTY)) { + // If the coin is known to be pruned (have no unspent outputs) in + // the current view and the cache entry is not dirty, we know the + // coin also must be pruned in the parent view as well, so it is safe + // to mark this fresh. + ret.first->second.flags |= CCoinsCacheEntry::FRESH; + } } + ret.first->second.coins.Clear(); ret.first->second.flags |= CCoinsCacheEntry::DIRTY; return CCoinsModifier(*this, ret.first, 0); } @@ -200,6 +220,11 @@ bool CCoinsViewCache::BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlockIn itUs->second.coins.swap(it->second.coins); cachedCoinsUsage += itUs->second.coins.DynamicMemoryUsage(); itUs->second.flags |= CCoinsCacheEntry::DIRTY; + // NOTE: It is possible the child has a FRESH flag here in + // the event the entry we found in the parent is pruned. But + // we must not copy that FRESH flag to the parent as that + // pruned state likely still needs to be communicated to the + // grandparent. } } } diff --git a/src/coins.h b/src/coins.h index dd6ef6cc3a..6244606356 100644 --- a/src/coins.h +++ b/src/coins.h @@ -269,6 +269,11 @@ struct CCoinsCacheEntry enum Flags { DIRTY = (1 << 0), // This cache entry is potentially different from the version in the parent view. FRESH = (1 << 1), // The parent view does not have this entry (or it is pruned). + /* Note that FRESH is a performance optimization with which we can + * erase coins that are fully spent if we know we do not need to + * flush the changes to the parent cache. It is always safe to + * not mark FRESH if that condition is not guaranteed. + */ }; CCoinsCacheEntry() : coins(), flags(0) {} diff --git a/src/test/coins_tests.cpp b/src/test/coins_tests.cpp index 09fe0bf158..94a11d1768 100644 --- a/src/test/coins_tests.cpp +++ b/src/test/coins_tests.cpp @@ -5,6 +5,7 @@ #include "coins.h" #include "script/standard.h" #include "uint256.h" +#include "undo.h" #include "utilstrencodings.h" #include "test/test_bitcoin.h" #include "test/test_random.h" @@ -16,6 +17,9 @@ #include <boost/test/unit_test.hpp> +bool ApplyTxInUndo(const CTxInUndo& undo, CCoinsViewCache& view, const COutPoint& out); +void UpdateCoins(const CTransaction& tx, CCoinsViewCache& inputs, CTxUndo &txundo, int nHeight); + namespace { class CCoinsViewTest : public CCoinsView @@ -213,6 +217,22 @@ BOOST_AUTO_TEST_CASE(coins_cache_simulation_test) BOOST_CHECK(missed_an_entry); } +typedef std::tuple<CTransaction,CTxUndo,CCoins> TxData; +// Store of all necessary tx and undo data for next test +std::map<uint256, TxData> alltxs; + +TxData &FindRandomFrom(const std::set<uint256> &txidset) { + assert(txidset.size()); + std::set<uint256>::iterator txIt = txidset.lower_bound(GetRandHash()); + if (txIt == txidset.end()) { + txIt = txidset.begin(); + } + std::map<uint256, TxData>::iterator txdit = alltxs.find(*txIt); + assert(txdit != alltxs.end()); + return txdit->second; +} + + // This test is similar to the previous test // except the emphasis is on testing the functionality of UpdateCoins // random txs are created and UpdateCoins is used to update the cache stack @@ -229,77 +249,139 @@ BOOST_AUTO_TEST_CASE(updatecoins_simulation_test) std::vector<CCoinsViewCacheTest*> stack; // A stack of CCoinsViewCaches on top. stack.push_back(new CCoinsViewCacheTest(&base)); // Start with one cache. - // Track the txids we've used and whether they have been spent or not - std::map<uint256, CAmount> coinbaseids; - std::set<uint256> alltxids; + // Track the txids we've used in various sets + std::set<uint256> coinbaseids; + std::set<uint256> disconnectedids; std::set<uint256> duplicateids; + std::set<uint256> utxoset; for (unsigned int i = 0; i < NUM_SIMULATION_ITERATIONS; i++) { - { + uint32_t randiter = insecure_rand(); + + // 19/20 txs add a new transaction + if (randiter % 20 < 19) { CMutableTransaction tx; tx.vin.resize(1); tx.vout.resize(1); tx.vout[0].nValue = i; //Keep txs unique unless intended to duplicate unsigned int height = insecure_rand(); + CCoins oldcoins; - // 1/10 times create a coinbase - if (insecure_rand() % 10 == 0 || coinbaseids.size() < 10) { - // 1/100 times create a duplicate coinbase + // 2/20 times create a new coinbase + if (randiter % 20 < 2 || coinbaseids.size() < 10) { + // 1/10 of those times create a duplicate coinbase if (insecure_rand() % 10 == 0 && coinbaseids.size()) { - std::map<uint256, CAmount>::iterator coinbaseIt = coinbaseids.lower_bound(GetRandHash()); - if (coinbaseIt == coinbaseids.end()) { - coinbaseIt = coinbaseids.begin(); - } - //Use same random value to have same hash and be a true duplicate - tx.vout[0].nValue = coinbaseIt->second; - assert(tx.GetHash() == coinbaseIt->first); - duplicateids.insert(coinbaseIt->first); + TxData &txd = FindRandomFrom(coinbaseids); + // Reuse the exact same coinbase + tx = std::get<0>(txd); + // shouldn't be available for reconnection if its been duplicated + disconnectedids.erase(tx.GetHash()); + + duplicateids.insert(tx.GetHash()); } else { - coinbaseids[tx.GetHash()] = tx.vout[0].nValue; + coinbaseids.insert(tx.GetHash()); } assert(CTransaction(tx).IsCoinBase()); } - // 9/10 times create a regular tx + + // 17/20 times reconnect previous or add a regular tx else { + uint256 prevouthash; - // equally likely to spend coinbase or non coinbase - std::set<uint256>::iterator txIt = alltxids.lower_bound(GetRandHash()); - if (txIt == alltxids.end()) { - txIt = alltxids.begin(); + // 1/20 times reconnect a previously disconnected tx + if (randiter % 20 == 2 && disconnectedids.size()) { + TxData &txd = FindRandomFrom(disconnectedids); + tx = std::get<0>(txd); + prevouthash = tx.vin[0].prevout.hash; + if (!CTransaction(tx).IsCoinBase() && !utxoset.count(prevouthash)) { + disconnectedids.erase(tx.GetHash()); + continue; + } + + // If this tx is already IN the UTXO, then it must be a coinbase, and it must be a duplicate + if (utxoset.count(tx.GetHash())) { + assert(CTransaction(tx).IsCoinBase()); + assert(duplicateids.count(tx.GetHash())); + } + disconnectedids.erase(tx.GetHash()); } - prevouthash = *txIt; - // Construct the tx to spend the coins of prevouthash - tx.vin[0].prevout.hash = prevouthash; - tx.vin[0].prevout.n = 0; + // 16/20 times create a regular tx + else { + TxData &txd = FindRandomFrom(utxoset); + prevouthash = std::get<0>(txd).GetHash(); + // Construct the tx to spend the coins of prevouthash + tx.vin[0].prevout.hash = prevouthash; + tx.vin[0].prevout.n = 0; + assert(!CTransaction(tx).IsCoinBase()); + } + // In this simple test coins only have two states, spent or unspent, save the unspent state to restore + oldcoins = result[prevouthash]; // Update the expected result of prevouthash to know these coins are spent - CCoins& oldcoins = result[prevouthash]; - oldcoins.Clear(); + result[prevouthash].Clear(); - // It is of particular importance here that once we spend a coinbase tx hash - // it is no longer available to be duplicated (or spent again) - // BIP 34 in conjunction with enforcing BIP 30 (at least until BIP 34 was active) - // results in the fact that no coinbases were duplicated after they were already spent - alltxids.erase(prevouthash); - coinbaseids.erase(prevouthash); + utxoset.erase(prevouthash); // The test is designed to ensure spending a duplicate coinbase will work properly // if that ever happens and not resurrect the previously overwritten coinbase if (duplicateids.count(prevouthash)) spent_a_duplicate_coinbase = true; - assert(!CTransaction(tx).IsCoinBase()); } - // Track this tx to possibly spend later - alltxids.insert(tx.GetHash()); - // Update the expected result to know about the new output coins - CCoins &coins = result[tx.GetHash()]; - coins.FromTx(tx, height); + result[tx.GetHash()].FromTx(tx, height); + + // Call UpdateCoins on the top cache + CTxUndo undo; + UpdateCoins(tx, *(stack.back()), undo, height); - UpdateCoins(tx, *(stack.back()), height); + // Update the utxo set for future spends + utxoset.insert(tx.GetHash()); + + // Track this tx and undo info to use later + alltxs.insert(std::make_pair(tx.GetHash(),std::make_tuple(tx,undo,oldcoins))); + } + + //1/20 times undo a previous transaction + else if (utxoset.size()) { + TxData &txd = FindRandomFrom(utxoset); + + CTransaction &tx = std::get<0>(txd); + CTxUndo &undo = std::get<1>(txd); + CCoins &origcoins = std::get<2>(txd); + + uint256 undohash = tx.GetHash(); + + // Update the expected result + // Remove new outputs + result[undohash].Clear(); + // If not coinbase restore prevout + if (!tx.IsCoinBase()) { + result[tx.vin[0].prevout.hash] = origcoins; + } + + // Disconnect the tx from the current UTXO + // See code in DisconnectBlock + // remove outputs + { + CCoinsModifier outs = stack.back()->ModifyCoins(undohash); + outs->Clear(); + } + // restore inputs + if (!tx.IsCoinBase()) { + const COutPoint &out = tx.vin[0].prevout; + const CTxInUndo &undoin = undo.vprevout[0]; + ApplyTxInUndo(undoin, *(stack.back()), out); + } + // Store as a candidate for reconnection + disconnectedids.insert(undohash); + + // Update the utxoset + utxoset.erase(undohash); + if (!tx.IsCoinBase()) + utxoset.insert(tx.vin[0].prevout.hash); } // Once every 1000 iterations and at the end, verify the full cache. @@ -308,9 +390,9 @@ BOOST_AUTO_TEST_CASE(updatecoins_simulation_test) const CCoins* coins = stack.back()->AccessCoins(it->first); if (coins) { BOOST_CHECK(*coins == it->second); - } else { + } else { BOOST_CHECK(it->second.IsPruned()); - } + } } } @@ -334,7 +416,7 @@ BOOST_AUTO_TEST_CASE(updatecoins_simulation_test) tip = stack.back(); } stack.push_back(new CCoinsViewCacheTest(tip)); - } + } } } @@ -420,6 +502,7 @@ BOOST_AUTO_TEST_CASE(ccoins_serialization) const static uint256 TXID; const static CAmount PRUNED = -1; const static CAmount ABSENT = -2; +const static CAmount FAIL = -3; const static CAmount VALUE1 = 100; const static CAmount VALUE2 = 200; const static CAmount VALUE3 = 300; @@ -630,11 +713,17 @@ BOOST_AUTO_TEST_CASE(ccoins_modify) void CheckModifyNewCoinsBase(CAmount base_value, CAmount cache_value, CAmount modify_value, CAmount expected_value, char cache_flags, char expected_flags, bool coinbase) { SingleEntryCacheTest test(base_value, cache_value, cache_flags); - SetCoinsValue(modify_value, *test.cache.ModifyNewCoins(TXID, coinbase)); CAmount result_value; char result_flags; - GetCoinsMapEntry(test.cache.map(), result_value, result_flags); + try { + SetCoinsValue(modify_value, *test.cache.ModifyNewCoins(TXID, coinbase)); + GetCoinsMapEntry(test.cache.map(), result_value, result_flags); + } catch (std::logic_error& e) { + result_value = FAIL; + result_flags = NO_ENTRY; + } + BOOST_CHECK_EQUAL(result_value, expected_value); BOOST_CHECK_EQUAL(result_flags, expected_flags); } @@ -669,7 +758,7 @@ BOOST_AUTO_TEST_CASE(ccoins_modify_new) CheckModifyNewCoins(PRUNED, PRUNED, PRUNED, 0 , DIRTY , true ); CheckModifyNewCoins(PRUNED, PRUNED, ABSENT, FRESH , NO_ENTRY , false); CheckModifyNewCoins(PRUNED, PRUNED, ABSENT, FRESH , NO_ENTRY , true ); - CheckModifyNewCoins(PRUNED, PRUNED, ABSENT, DIRTY , NO_ENTRY , false); + CheckModifyNewCoins(PRUNED, PRUNED, PRUNED, DIRTY , DIRTY , false); CheckModifyNewCoins(PRUNED, PRUNED, PRUNED, DIRTY , DIRTY , true ); CheckModifyNewCoins(PRUNED, PRUNED, ABSENT, DIRTY|FRESH, NO_ENTRY , false); CheckModifyNewCoins(PRUNED, PRUNED, ABSENT, DIRTY|FRESH, NO_ENTRY , true ); @@ -677,25 +766,25 @@ BOOST_AUTO_TEST_CASE(ccoins_modify_new) CheckModifyNewCoins(PRUNED, VALUE3, VALUE3, 0 , DIRTY , true ); CheckModifyNewCoins(PRUNED, VALUE3, VALUE3, FRESH , DIRTY|FRESH, false); CheckModifyNewCoins(PRUNED, VALUE3, VALUE3, FRESH , DIRTY|FRESH, true ); - CheckModifyNewCoins(PRUNED, VALUE3, VALUE3, DIRTY , DIRTY|FRESH, false); + CheckModifyNewCoins(PRUNED, VALUE3, VALUE3, DIRTY , DIRTY , false); CheckModifyNewCoins(PRUNED, VALUE3, VALUE3, DIRTY , DIRTY , true ); CheckModifyNewCoins(PRUNED, VALUE3, VALUE3, DIRTY|FRESH, DIRTY|FRESH, false); CheckModifyNewCoins(PRUNED, VALUE3, VALUE3, DIRTY|FRESH, DIRTY|FRESH, true ); - CheckModifyNewCoins(VALUE2, PRUNED, ABSENT, 0 , NO_ENTRY , false); + CheckModifyNewCoins(VALUE2, PRUNED, FAIL , 0 , NO_ENTRY , false); CheckModifyNewCoins(VALUE2, PRUNED, PRUNED, 0 , DIRTY , true ); - CheckModifyNewCoins(VALUE2, PRUNED, ABSENT, FRESH , NO_ENTRY , false); + CheckModifyNewCoins(VALUE2, PRUNED, FAIL , FRESH , NO_ENTRY , false); CheckModifyNewCoins(VALUE2, PRUNED, ABSENT, FRESH , NO_ENTRY , true ); - CheckModifyNewCoins(VALUE2, PRUNED, ABSENT, DIRTY , NO_ENTRY , false); + CheckModifyNewCoins(VALUE2, PRUNED, FAIL , DIRTY , NO_ENTRY , false); CheckModifyNewCoins(VALUE2, PRUNED, PRUNED, DIRTY , DIRTY , true ); - CheckModifyNewCoins(VALUE2, PRUNED, ABSENT, DIRTY|FRESH, NO_ENTRY , false); + CheckModifyNewCoins(VALUE2, PRUNED, FAIL , DIRTY|FRESH, NO_ENTRY , false); CheckModifyNewCoins(VALUE2, PRUNED, ABSENT, DIRTY|FRESH, NO_ENTRY , true ); - CheckModifyNewCoins(VALUE2, VALUE3, VALUE3, 0 , DIRTY|FRESH, false); + CheckModifyNewCoins(VALUE2, VALUE3, FAIL , 0 , NO_ENTRY , false); CheckModifyNewCoins(VALUE2, VALUE3, VALUE3, 0 , DIRTY , true ); - CheckModifyNewCoins(VALUE2, VALUE3, VALUE3, FRESH , DIRTY|FRESH, false); + CheckModifyNewCoins(VALUE2, VALUE3, FAIL , FRESH , NO_ENTRY , false); CheckModifyNewCoins(VALUE2, VALUE3, VALUE3, FRESH , DIRTY|FRESH, true ); - CheckModifyNewCoins(VALUE2, VALUE3, VALUE3, DIRTY , DIRTY|FRESH, false); + CheckModifyNewCoins(VALUE2, VALUE3, FAIL , DIRTY , NO_ENTRY , false); CheckModifyNewCoins(VALUE2, VALUE3, VALUE3, DIRTY , DIRTY , true ); - CheckModifyNewCoins(VALUE2, VALUE3, VALUE3, DIRTY|FRESH, DIRTY|FRESH, false); + CheckModifyNewCoins(VALUE2, VALUE3, FAIL , DIRTY|FRESH, NO_ENTRY , false); CheckModifyNewCoins(VALUE2, VALUE3, VALUE3, DIRTY|FRESH, DIRTY|FRESH, true ); } diff --git a/src/validation.cpp b/src/validation.cpp index bd60bbfdcd..744c228bb7 100644 --- a/src/validation.cpp +++ b/src/validation.cpp @@ -1498,7 +1498,7 @@ bool AbortNode(CValidationState& state, const std::string& strMessage, const std * @param out The out point that corresponds to the tx input. * @return True on success. */ -static bool ApplyTxInUndo(const CTxInUndo& undo, CCoinsViewCache& view, const COutPoint& out) +bool ApplyTxInUndo(const CTxInUndo& undo, CCoinsViewCache& view, const COutPoint& out) { bool fClean = true; |