diff --git a/src/coins.h b/src/coins.h --- a/src/coins.h +++ b/src/coins.h @@ -524,16 +524,18 @@ CCoinsModifier ModifyCoins(const uint256 &txid); /** - * Return a modifiable reference to a CCoins. Assumes that no entry with the - * given txid exists and creates a new one. This saves a database access in - * the case where the coins were to be wiped out by FromTx anyway. This - * should not be called with the 2 historical coinbase duplicate pairs - * because the new coins are marked fresh, and in the event the duplicate - * coinbase was spent before a flush, the now pruned coins would not - * properly overwrite the first coinbase of the pair. Simultaneous - * modifications are not allowed. + * Add a coin. Set potential_overwrite to true if a non-pruned version may + * already exist. */ - CCoinsModifier ModifyNewCoins(const uint256 &txid, bool coinbase); + void AddCoin(const COutPoint &outpoint, const Coin &coin, + bool potential_overwrite); + + /** + * Spend a coin. Pass moveto in order to get the deleted data. + * If no unspent output exists for the passed outpoint, this call has no + * effect. + */ + bool SpendCoin(const COutPoint &outpoint, Coin *moveto = nullptr); /** * Push the modifications applied to this cache to its base. @@ -582,7 +584,7 @@ friend class CCoinsModifier; private: - CCoinsMap::const_iterator FetchCoins(const uint256 &txid) const; + CCoinsMap::iterator FetchCoins(const uint256 &txid) const; /** * By making the copy constructor private, we prevent accidentally using it @@ -591,6 +593,12 @@ CCoinsViewCache(const CCoinsViewCache &); }; +//! Utility function to add all of a transaction's outputs to a cache. +// It assumes that overwrites are only possible for coinbase transactions. +// TODO: pass in a boolean to limit these possible overwrites to known +// (pre-BIP34) cases. +void AddCoins(CCoinsViewCache &cache, const CTransaction &tx, int nHeight); + //! Utility function to find any unspent output with a given txid. const Coin AccessByTxid(const CCoinsViewCache &cache, const uint256 &txid); diff --git a/src/coins.cpp b/src/coins.cpp --- a/src/coins.cpp +++ b/src/coins.cpp @@ -93,8 +93,7 @@ return memusage::DynamicUsage(cacheCoins) + cachedCoinsUsage; } -CCoinsMap::const_iterator -CCoinsViewCache::FetchCoins(const uint256 &txid) const { +CCoinsMap::iterator CCoinsViewCache::FetchCoins(const uint256 &txid) const { CCoinsMap::iterator it = cacheCoins.find(txid); if (it != cacheCoins.end()) { return it; @@ -147,53 +146,81 @@ return CCoinsModifier(*this, ret.first, cachedCoinUsage); } -/** - * 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 ret = - cacheCoins.insert(std::make_pair(txid, CCoinsCacheEntry())); - if (!coinbase) { - // 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; +void CCoinsViewCache::AddCoin(const COutPoint &outpoint, const Coin &coin, + bool possible_overwrite) { + assert(!coin.IsSpent()); + if (coin.GetTxOut().scriptPubKey.IsUnspendable()) { + return; + } + CCoinsMap::iterator it; + bool inserted; + std::tie(it, inserted) = cacheCoins.emplace( + std::piecewise_construct, std::forward_as_tuple(outpoint.hash), + std::tuple<>()); + bool fresh = false; + if (!inserted) { + cachedCoinsUsage -= it->second.coins.DynamicMemoryUsage(); + } + if (!possible_overwrite) { + if (it->second.coins.IsAvailable(outpoint.n)) { + throw std::logic_error( + "Adding new coin that replaces non-pruned entry"); } + fresh = it->second.coins.IsPruned() && + !(it->second.flags & CCoinsCacheEntry::DIRTY); + } + if (it->second.coins.vout.size() <= outpoint.n) { + it->second.coins.vout.resize(outpoint.n + 1); + } + it->second.coins.vout[outpoint.n] = coin.GetTxOut(); + it->second.coins.nHeight = coin.GetHeight(); + it->second.coins.fCoinBase = coin.IsCoinBase(); + it->second.flags |= + CCoinsCacheEntry::DIRTY | (fresh ? CCoinsCacheEntry::FRESH : 0); + cachedCoinsUsage += it->second.coins.DynamicMemoryUsage(); +} + +void AddCoins(CCoinsViewCache &cache, const CTransaction &tx, int nHeight) { + bool fCoinbase = tx.IsCoinBase(); + const uint256 &txid = tx.GetHash(); + for (size_t i = 0; i < tx.vout.size(); ++i) { + // Pass fCoinbase as the possible_overwrite flag to AddCoin, in order to + // correctly deal with the pre-BIP30 occurrances of duplicate coinbase + // transactions. + cache.AddCoin(COutPoint(txid, i), Coin(tx.vout[i], nHeight, fCoinbase), + fCoinbase); } - ret.first->second.coins.Clear(); - ret.first->second.flags |= CCoinsCacheEntry::DIRTY; - return CCoinsModifier(*this, ret.first, 0); +} + +bool CCoinsViewCache::SpendCoin(const COutPoint &outpoint, Coin *moveout) { + CCoinsMap::iterator it = FetchCoins(outpoint.hash); + if (it == cacheCoins.end()) { + return false; + } + cachedCoinsUsage -= it->second.coins.DynamicMemoryUsage(); + if (moveout && it->second.coins.IsAvailable(outpoint.n)) { + *moveout = Coin(it->second.coins.vout[outpoint.n], + it->second.coins.nHeight, it->second.coins.fCoinBase); + } + // Ignore return value: SpendCoin has no effect if no UTXO found. + it->second.coins.Spend(outpoint.n); + if (it->second.coins.IsPruned() && + it->second.flags & CCoinsCacheEntry::FRESH) { + cacheCoins.erase(it); + } else { + cachedCoinsUsage += it->second.coins.DynamicMemoryUsage(); + it->second.flags |= CCoinsCacheEntry::DIRTY; + } + return true; } const CCoins *CCoinsViewCache::AccessCoins(const uint256 &txid) const { CCoinsMap::const_iterator it = FetchCoins(txid); if (it == cacheCoins.end()) { return nullptr; - } else { - return &it->second.coins; } + + return &it->second.coins; } static const Coin coinEmpty; diff --git a/src/test/coins_tests.cpp b/src/test/coins_tests.cpp --- a/src/test/coins_tests.cpp +++ b/src/test/coins_tests.cpp @@ -607,7 +607,7 @@ // TODO: Remove TXID once the migration is over. static const uint256 TXID; -static const COutPoint OUTPOINT; +static const COutPoint OUTPOINT = {uint256(), 0}; static const CAmount PRUNED = -1; static const CAmount ABSENT = -2; static const CAmount FAIL = -3; @@ -821,16 +821,71 @@ DIRTY | FRESH); } -void CheckModifyNewCoinsBase(CAmount base_value, CAmount cache_value, - CAmount modify_value, CAmount expected_value, - char cache_flags, char expected_flags, - bool coinbase) { +void CheckSpendCoins(CAmount base_value, CAmount cache_value, + CAmount expected_value, char cache_flags, + char expected_flags) { + SingleEntryCacheTest test(base_value, cache_value, cache_flags); + test.cache.SpendCoin(OUTPOINT); + test.cache.SelfTest(); + + CAmount result_value; + char result_flags; + GetCoinsMapEntry(test.cache.map(), result_value, result_flags); + BOOST_CHECK_EQUAL(result_value, expected_value); + BOOST_CHECK_EQUAL(result_flags, expected_flags); +}; + +BOOST_AUTO_TEST_CASE(coin_spend) { + /** + * Check SpendCoin behavior, requesting a coin from a cache view layered on + * top of a base view, spending, and then checking the resulting entry in + * the cache after the modification. + * + * Base Cache Result Cache Result + * Value Value Value Flags Flags + */ + CheckSpendCoins(ABSENT, ABSENT, ABSENT, NO_ENTRY, NO_ENTRY); + CheckSpendCoins(ABSENT, PRUNED, PRUNED, 0, DIRTY); + CheckSpendCoins(ABSENT, PRUNED, ABSENT, FRESH, NO_ENTRY); + CheckSpendCoins(ABSENT, PRUNED, PRUNED, DIRTY, DIRTY); + CheckSpendCoins(ABSENT, PRUNED, ABSENT, DIRTY | FRESH, NO_ENTRY); + CheckSpendCoins(ABSENT, VALUE2, PRUNED, 0, DIRTY); + CheckSpendCoins(ABSENT, VALUE2, ABSENT, FRESH, NO_ENTRY); + CheckSpendCoins(ABSENT, VALUE2, PRUNED, DIRTY, DIRTY); + CheckSpendCoins(ABSENT, VALUE2, ABSENT, DIRTY | FRESH, NO_ENTRY); + CheckSpendCoins(PRUNED, ABSENT, ABSENT, NO_ENTRY, NO_ENTRY); + CheckSpendCoins(PRUNED, PRUNED, PRUNED, 0, DIRTY); + CheckSpendCoins(PRUNED, PRUNED, ABSENT, FRESH, NO_ENTRY); + CheckSpendCoins(PRUNED, PRUNED, PRUNED, DIRTY, DIRTY); + CheckSpendCoins(PRUNED, PRUNED, ABSENT, DIRTY | FRESH, NO_ENTRY); + CheckSpendCoins(PRUNED, VALUE2, PRUNED, 0, DIRTY); + CheckSpendCoins(PRUNED, VALUE2, ABSENT, FRESH, NO_ENTRY); + CheckSpendCoins(PRUNED, VALUE2, PRUNED, DIRTY, DIRTY); + CheckSpendCoins(PRUNED, VALUE2, ABSENT, DIRTY | FRESH, NO_ENTRY); + CheckSpendCoins(VALUE1, ABSENT, PRUNED, NO_ENTRY, DIRTY); + CheckSpendCoins(VALUE1, PRUNED, PRUNED, 0, DIRTY); + CheckSpendCoins(VALUE1, PRUNED, ABSENT, FRESH, NO_ENTRY); + CheckSpendCoins(VALUE1, PRUNED, PRUNED, DIRTY, DIRTY); + CheckSpendCoins(VALUE1, PRUNED, ABSENT, DIRTY | FRESH, NO_ENTRY); + CheckSpendCoins(VALUE1, VALUE2, PRUNED, 0, DIRTY); + CheckSpendCoins(VALUE1, VALUE2, ABSENT, FRESH, NO_ENTRY); + CheckSpendCoins(VALUE1, VALUE2, PRUNED, DIRTY, DIRTY); + CheckSpendCoins(VALUE1, VALUE2, ABSENT, DIRTY | FRESH, NO_ENTRY); +} + +void CheckAddCoinBase(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); CAmount result_value; char result_flags; try { - SetCoinsValue(modify_value, *test.cache.ModifyNewCoins(TXID, coinbase)); + CTxOut output; + output.nValue = modify_value; + test.cache.AddCoin(OUTPOINT, Coin(std::move(output), 1, coinbase), + coinbase); + test.cache.SelfTest(); GetCoinsMapEntry(test.cache.map(), result_value, result_flags); } catch (std::logic_error &e) { result_value = FAIL; @@ -841,64 +896,45 @@ BOOST_CHECK_EQUAL(result_flags, expected_flags); } -// Simple wrapper for CheckModifyNewCoinsBase function above that loops through +// Simple wrapper for CheckAddCoinBase function above that loops through // different possible base_values, making sure each one gives the same results. -// This wrapper lets the modify_new test below be shorter and less repetitive, -// while still verifying that the CoinsViewCache::ModifyNewCoins implementation -// ignores base values. -template void CheckModifyNewCoins(Args &&... args) { - for (CAmount base_value : {ABSENT, PRUNED, VALUE1}) - CheckModifyNewCoinsBase(base_value, std::forward(args)...); +// This wrapper lets the coin_add test below be shorter and less repetitive, +// while still verifying that the CoinsViewCache::AddCoin implementation ignores +// base values. +template void CheckAddCoin(Args &&... args) { + for (CAmount base_value : {ABSENT, PRUNED, VALUE1}) { + CheckAddCoinBase(base_value, std::forward(args)...); + } } -BOOST_AUTO_TEST_CASE(ccoins_modify_new) { - /* Check ModifyNewCoin behavior, requesting a new coin from a cache view, - * writing a modification to the coin, and then checking the resulting - * entry in the cache after the modification. Verify behavior with the - * with the ModifyNewCoin coinbase argument set to false, and to true. +BOOST_AUTO_TEST_CASE(coin_add) { + /** + * Check AddCoin behavior, requesting a new coin from a cache view, writing + * a modification to the coin, and then checking the resulting entry in the + * cache after the modification. Verify behavior with the with the AddCoin + * potential_overwrite argument set to false, and to true. * - * Cache Write Result Cache Result Coinbase - * Value Value Value Flags Flags + * Cache Write Result Cache Result potential_overwrite + * Value Value Value Flags Flags */ - CheckModifyNewCoins(ABSENT, PRUNED, ABSENT, NO_ENTRY, NO_ENTRY, false); - CheckModifyNewCoins(ABSENT, PRUNED, PRUNED, NO_ENTRY, DIRTY, true); - CheckModifyNewCoins(ABSENT, VALUE3, VALUE3, NO_ENTRY, DIRTY | FRESH, false); - CheckModifyNewCoins(ABSENT, VALUE3, VALUE3, NO_ENTRY, DIRTY, true); - CheckModifyNewCoins(PRUNED, PRUNED, ABSENT, 0, NO_ENTRY, false); - 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, 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); - CheckModifyNewCoins(PRUNED, VALUE3, VALUE3, 0, DIRTY | FRESH, false); - 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, 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, FAIL, 0, NO_ENTRY, false); - CheckModifyNewCoins(VALUE2, PRUNED, PRUNED, 0, DIRTY, true); - CheckModifyNewCoins(VALUE2, PRUNED, FAIL, FRESH, NO_ENTRY, false); - CheckModifyNewCoins(VALUE2, PRUNED, ABSENT, FRESH, NO_ENTRY, true); - CheckModifyNewCoins(VALUE2, PRUNED, FAIL, DIRTY, NO_ENTRY, false); - CheckModifyNewCoins(VALUE2, PRUNED, PRUNED, DIRTY, DIRTY, true); - CheckModifyNewCoins(VALUE2, PRUNED, FAIL, DIRTY | FRESH, NO_ENTRY, false); - CheckModifyNewCoins(VALUE2, PRUNED, ABSENT, DIRTY | FRESH, NO_ENTRY, true); - CheckModifyNewCoins(VALUE2, VALUE3, FAIL, 0, NO_ENTRY, false); - CheckModifyNewCoins(VALUE2, VALUE3, VALUE3, 0, DIRTY, true); - CheckModifyNewCoins(VALUE2, VALUE3, FAIL, FRESH, NO_ENTRY, false); - CheckModifyNewCoins(VALUE2, VALUE3, VALUE3, FRESH, DIRTY | FRESH, true); - CheckModifyNewCoins(VALUE2, VALUE3, FAIL, DIRTY, NO_ENTRY, false); - CheckModifyNewCoins(VALUE2, VALUE3, VALUE3, DIRTY, DIRTY, true); - CheckModifyNewCoins(VALUE2, VALUE3, FAIL, DIRTY | FRESH, NO_ENTRY, false); - CheckModifyNewCoins(VALUE2, VALUE3, VALUE3, DIRTY | FRESH, DIRTY | FRESH, - true); + CheckAddCoin(ABSENT, VALUE3, VALUE3, NO_ENTRY, DIRTY | FRESH, false); + CheckAddCoin(ABSENT, VALUE3, VALUE3, NO_ENTRY, DIRTY, true); + CheckAddCoin(PRUNED, VALUE3, VALUE3, 0, DIRTY | FRESH, false); + CheckAddCoin(PRUNED, VALUE3, VALUE3, 0, DIRTY, true); + CheckAddCoin(PRUNED, VALUE3, VALUE3, FRESH, DIRTY | FRESH, false); + CheckAddCoin(PRUNED, VALUE3, VALUE3, FRESH, DIRTY | FRESH, true); + CheckAddCoin(PRUNED, VALUE3, VALUE3, DIRTY, DIRTY, false); + CheckAddCoin(PRUNED, VALUE3, VALUE3, DIRTY, DIRTY, true); + CheckAddCoin(PRUNED, VALUE3, VALUE3, DIRTY | FRESH, DIRTY | FRESH, false); + CheckAddCoin(PRUNED, VALUE3, VALUE3, DIRTY | FRESH, DIRTY | FRESH, true); + CheckAddCoin(VALUE2, VALUE3, FAIL, 0, NO_ENTRY, false); + CheckAddCoin(VALUE2, VALUE3, VALUE3, 0, DIRTY, true); + CheckAddCoin(VALUE2, VALUE3, FAIL, FRESH, NO_ENTRY, false); + CheckAddCoin(VALUE2, VALUE3, VALUE3, FRESH, DIRTY | FRESH, true); + CheckAddCoin(VALUE2, VALUE3, FAIL, DIRTY, NO_ENTRY, false); + CheckAddCoin(VALUE2, VALUE3, VALUE3, DIRTY, DIRTY, true); + CheckAddCoin(VALUE2, VALUE3, FAIL, DIRTY | FRESH, NO_ENTRY, false); + CheckAddCoin(VALUE2, VALUE3, VALUE3, DIRTY | FRESH, DIRTY | FRESH, true); } void CheckWriteCoins(CAmount parent_value, CAmount child_value, diff --git a/src/test/undo_tests.cpp b/src/test/undo_tests.cpp --- a/src/test/undo_tests.cpp +++ b/src/test/undo_tests.cpp @@ -74,8 +74,7 @@ tx.nVersion = 2; auto prevTx0 = CTransaction(tx); - view.ModifyNewCoins(prevTx0.GetId(), prevTx0.IsCoinBase()) - ->FromTx(prevTx0, 100); + AddCoins(view, prevTx0, 100); tx.vin[0].prevout.hash = prevTx0.GetId(); auto tx0 = CTransaction(tx); diff --git a/src/validation.cpp b/src/validation.cpp --- a/src/validation.cpp +++ b/src/validation.cpp @@ -1247,23 +1247,15 @@ if (!tx.IsCoinBase()) { txundo.vprevout.reserve(tx.vin.size()); for (const CTxIn &txin : tx.vin) { - CCoinsModifier coins = inputs.ModifyCoins(txin.prevout.hash); - unsigned nPos = txin.prevout.n; - - if (nPos >= coins->vout.size() || coins->vout[nPos].IsNull()) { - assert(false); - } - - // Mark an outpoint spent, and construct undo information. - txundo.vprevout.emplace_back(coins->vout[nPos], coins->nHeight, - coins->fCoinBase); - bool ret = coins->Spend(nPos); - assert(ret); + txundo.vprevout.emplace_back(); + bool is_spent = + inputs.SpendCoin(txin.prevout, &txundo.vprevout.back()); + assert(is_spent); } } // Add outputs. - inputs.ModifyNewCoins(tx.GetId(), tx.IsCoinBase())->FromTx(tx, nHeight); + AddCoins(inputs, tx, nHeight); } void UpdateCoins(const CTransaction &tx, CCoinsViewCache &inputs, int nHeight) {