diff options
| -rw-r--r-- | src/coins.cpp | 47 | ||||
| -rw-r--r-- | src/coins.h | 20 | ||||
| -rw-r--r-- | src/test/coins_tests.cpp | 242 | ||||
| -rw-r--r-- | src/txdb.cpp | 5 | ||||
| -rw-r--r-- | src/txdb.h | 2 |
5 files changed, 288 insertions, 28 deletions
diff --git a/src/coins.cpp b/src/coins.cpp index 976118e23c..ecbd625cd7 100644 --- a/src/coins.cpp +++ b/src/coins.cpp @@ -13,7 +13,7 @@ bool CCoinsView::GetCoin(const COutPoint &outpoint, Coin &coin) const { return false; } uint256 CCoinsView::GetBestBlock() const { return uint256(); } std::vector<uint256> CCoinsView::GetHeadBlocks() const { return std::vector<uint256>(); } -bool CCoinsView::BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock) { return false; } +bool CCoinsView::BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock, bool erase) { return false; } std::unique_ptr<CCoinsViewCursor> CCoinsView::Cursor() const { return nullptr; } bool CCoinsView::HaveCoin(const COutPoint &outpoint) const @@ -28,7 +28,7 @@ bool CCoinsViewBacked::HaveCoin(const COutPoint &outpoint) const { return base-> uint256 CCoinsViewBacked::GetBestBlock() const { return base->GetBestBlock(); } std::vector<uint256> CCoinsViewBacked::GetHeadBlocks() const { return base->GetHeadBlocks(); } void CCoinsViewBacked::SetBackend(CCoinsView &viewIn) { base = &viewIn; } -bool CCoinsViewBacked::BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock) { return base->BatchWrite(mapCoins, hashBlock); } +bool CCoinsViewBacked::BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock, bool erase) { return base->BatchWrite(mapCoins, hashBlock, erase); } std::unique_ptr<CCoinsViewCursor> CCoinsViewBacked::Cursor() const { return base->Cursor(); } size_t CCoinsViewBacked::EstimateSize() const { return base->EstimateSize(); } @@ -176,8 +176,10 @@ void CCoinsViewCache::SetBestBlock(const uint256 &hashBlockIn) { hashBlock = hashBlockIn; } -bool CCoinsViewCache::BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlockIn) { - for (CCoinsMap::iterator it = mapCoins.begin(); it != mapCoins.end(); it = mapCoins.erase(it)) { +bool CCoinsViewCache::BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlockIn, bool erase) { + for (CCoinsMap::iterator it = mapCoins.begin(); + it != mapCoins.end(); + it = erase ? mapCoins.erase(it) : std::next(it)) { // Ignore non-dirty entries (optimization). if (!(it->second.flags & CCoinsCacheEntry::DIRTY)) { continue; @@ -190,7 +192,14 @@ bool CCoinsViewCache::BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlockIn // Create the coin in the parent cache, move the data up // and mark it as dirty. CCoinsCacheEntry& entry = cacheCoins[it->first]; - entry.coin = std::move(it->second.coin); + if (erase) { + // The `move` call here is purely an optimization; we rely on the + // `mapCoins.erase` call in the `for` expression to actually remove + // the entry from the child map. + entry.coin = std::move(it->second.coin); + } else { + entry.coin = it->second.coin; + } cachedCoinsUsage += entry.coin.DynamicMemoryUsage(); entry.flags = CCoinsCacheEntry::DIRTY; // We can mark it FRESH in the parent if it was FRESH in the child @@ -218,7 +227,14 @@ bool CCoinsViewCache::BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlockIn } else { // A normal modification. cachedCoinsUsage -= itUs->second.coin.DynamicMemoryUsage(); - itUs->second.coin = std::move(it->second.coin); + if (erase) { + // The `move` call here is purely an optimization; we rely on the + // `mapCoins.erase` call in the `for` expression to actually remove + // the entry from the child map. + itUs->second.coin = std::move(it->second.coin); + } else { + itUs->second.coin = it->second.coin; + } cachedCoinsUsage += itUs->second.coin.DynamicMemoryUsage(); itUs->second.flags |= CCoinsCacheEntry::DIRTY; // NOTE: It isn't safe to mark the coin as FRESH in the parent @@ -233,12 +249,29 @@ bool CCoinsViewCache::BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlockIn } bool CCoinsViewCache::Flush() { - bool fOk = base->BatchWrite(cacheCoins, hashBlock); + bool fOk = base->BatchWrite(cacheCoins, hashBlock, /*erase=*/ true); cacheCoins.clear(); cachedCoinsUsage = 0; return fOk; } +bool CCoinsViewCache::Sync() +{ + bool fOk = base->BatchWrite(cacheCoins, hashBlock, /*erase=*/ false); + // Instead of clearing `cacheCoins` as we would in Flush(), just clear the + // FRESH/DIRTY flags of any coin that isn't spent. + for (auto it = cacheCoins.begin(); it != cacheCoins.end(); ) { + if (it->second.coin.IsSpent()) { + cachedCoinsUsage -= it->second.coin.DynamicMemoryUsage(); + it = cacheCoins.erase(it); + } else { + it->second.flags = 0; + ++it; + } + } + return fOk; +} + void CCoinsViewCache::Uncache(const COutPoint& hash) { CCoinsMap::iterator it = cacheCoins.find(hash); diff --git a/src/coins.h b/src/coins.h index b0d6bdf333..4edc146a14 100644 --- a/src/coins.h +++ b/src/coins.h @@ -176,7 +176,7 @@ public: //! Do a bulk modification (multiple Coin changes + BestBlock change). //! The passed mapCoins can be modified. - virtual bool BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock); + virtual bool BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock, bool erase = true); //! Get a cursor to iterate over the whole state virtual std::unique_ptr<CCoinsViewCursor> Cursor() const; @@ -202,7 +202,7 @@ public: uint256 GetBestBlock() const override; std::vector<uint256> GetHeadBlocks() const override; void SetBackend(CCoinsView &viewIn); - bool BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock) override; + bool BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock, bool erase = true) override; std::unique_ptr<CCoinsViewCursor> Cursor() const override; size_t EstimateSize() const override; }; @@ -235,7 +235,7 @@ public: bool HaveCoin(const COutPoint &outpoint) const override; uint256 GetBestBlock() const override; void SetBestBlock(const uint256 &hashBlock); - bool BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock) override; + bool BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock, bool erase = true) override; std::unique_ptr<CCoinsViewCursor> Cursor() const override { throw std::logic_error("CCoinsViewCache cursor iteration not supported."); } @@ -282,13 +282,23 @@ public: bool SpendCoin(const COutPoint &outpoint, Coin* moveto = nullptr); /** - * Push the modifications applied to this cache to its base. - * Failure to call this method before destruction will cause the changes to be forgotten. + * Push the modifications applied to this cache to its base and wipe local state. + * Failure to call this method or Sync() before destruction will cause the changes + * to be forgotten. * If false is returned, the state of this cache (and its backing view) will be undefined. */ bool Flush(); /** + * Push the modifications applied to this cache to its base while retaining + * the contents of this cache (except for spent coins, which we erase). + * Failure to call this method or Flush() before destruction will cause the changes + * to be forgotten. + * If false is returned, the state of this cache (and its backing view) will be undefined. + */ + bool Sync(); + + /** * Removes the UTXO with the given outpoint from the cache, if it is * not modified. */ diff --git a/src/test/coins_tests.cpp b/src/test/coins_tests.cpp index 31d437081a..92bad8dd2e 100644 --- a/src/test/coins_tests.cpp +++ b/src/test/coins_tests.cpp @@ -53,9 +53,9 @@ public: uint256 GetBestBlock() const override { return hashBestBlock_; } - bool BatchWrite(CCoinsMap& mapCoins, const uint256& hashBlock) override + bool BatchWrite(CCoinsMap& mapCoins, const uint256& hashBlock, bool erase = true) override { - for (CCoinsMap::iterator it = mapCoins.begin(); it != mapCoins.end(); ) { + for (CCoinsMap::iterator it = mapCoins.begin(); it != mapCoins.end(); it = erase ? mapCoins.erase(it) : ++it) { if (it->second.flags & CCoinsCacheEntry::DIRTY) { // Same optimization used in CCoinsViewDB is to only write dirty entries. map_[it->first] = it->second.coin; @@ -64,7 +64,6 @@ public: map_.erase(it->first); } } - mapCoins.erase(it++); } if (!hashBlock.IsNull()) hashBestBlock_ = hashBlock; @@ -126,6 +125,7 @@ void SimulationTest(CCoinsView* base, bool fake_best_block) bool found_an_entry = false; bool missed_an_entry = false; bool uncached_an_entry = false; + bool flushed_without_erase = false; // A simple map to track what we expect the cache stack to represent. std::map<COutPoint, Coin> result; @@ -154,9 +154,16 @@ void SimulationTest(CCoinsView* base, bool fake_best_block) bool test_havecoin_after = InsecureRandBits(2) == 0; bool result_havecoin = test_havecoin_before ? stack.back()->HaveCoin(COutPoint(txid, 0)) : false; - const Coin& entry = (InsecureRandRange(500) == 0) ? AccessByTxid(*stack.back(), txid) : stack.back()->AccessCoin(COutPoint(txid, 0)); + + // Infrequently, test usage of AccessByTxid instead of AccessCoin - the + // former just delegates to the latter and returns the first unspent in a txn. + const Coin& entry = (InsecureRandRange(500) == 0) ? + AccessByTxid(*stack.back(), txid) : stack.back()->AccessCoin(COutPoint(txid, 0)); BOOST_CHECK(coin == entry); - BOOST_CHECK(!test_havecoin_before || result_havecoin == !entry.IsSpent()); + + if (test_havecoin_before) { + BOOST_CHECK(result_havecoin == !entry.IsSpent()); + } if (test_havecoin_after) { bool ret = stack.back()->HaveCoin(COutPoint(txid, 0)); @@ -167,24 +174,29 @@ void SimulationTest(CCoinsView* base, bool fake_best_block) Coin newcoin; newcoin.out.nValue = InsecureRand32(); newcoin.nHeight = 1; + + // Infrequently test adding unspendable coins. if (InsecureRandRange(16) == 0 && coin.IsSpent()) { newcoin.out.scriptPubKey.assign(1 + InsecureRandBits(6), OP_RETURN); BOOST_CHECK(newcoin.out.scriptPubKey.IsUnspendable()); added_an_unspendable_entry = true; } else { - newcoin.out.scriptPubKey.assign(InsecureRandBits(6), 0); // Random sizes so we can test memory usage accounting + // Random sizes so we can test memory usage accounting + newcoin.out.scriptPubKey.assign(InsecureRandBits(6), 0); (coin.IsSpent() ? added_an_entry : updated_an_entry) = true; coin = newcoin; } - stack.back()->AddCoin(COutPoint(txid, 0), std::move(newcoin), !coin.IsSpent() || InsecureRand32() & 1); + bool is_overwrite = !coin.IsSpent() || InsecureRand32() & 1; + stack.back()->AddCoin(COutPoint(txid, 0), std::move(newcoin), is_overwrite); } else { + // Spend the coin. removed_an_entry = true; coin.Clear(); BOOST_CHECK(stack.back()->SpendCoin(COutPoint(txid, 0))); } } - // One every 10 iterations, remove a random entry from the cache + // Once every 10 iterations, remove a random entry from the cache if (InsecureRandRange(10) == 0) { COutPoint out(txids[InsecureRand32() % txids.size()], 0); int cacheid = InsecureRand32() % stack.size(); @@ -216,7 +228,9 @@ void SimulationTest(CCoinsView* base, bool fake_best_block) if (stack.size() > 1 && InsecureRandBool() == 0) { unsigned int flushIndex = InsecureRandRange(stack.size() - 1); if (fake_best_block) stack[flushIndex]->SetBestBlock(InsecureRand256()); - BOOST_CHECK(stack[flushIndex]->Flush()); + bool should_erase = InsecureRandRange(4) < 3; + BOOST_CHECK(should_erase ? stack[flushIndex]->Flush() : stack[flushIndex]->Sync()); + flushed_without_erase |= !should_erase; } } if (InsecureRandRange(100) == 0) { @@ -224,7 +238,9 @@ void SimulationTest(CCoinsView* base, bool fake_best_block) if (stack.size() > 0 && InsecureRandBool() == 0) { //Remove the top cache if (fake_best_block) stack.back()->SetBestBlock(InsecureRand256()); - BOOST_CHECK(stack.back()->Flush()); + bool should_erase = InsecureRandRange(4) < 3; + BOOST_CHECK(should_erase ? stack.back()->Flush() : stack.back()->Sync()); + flushed_without_erase |= !should_erase; delete stack.back(); stack.pop_back(); } @@ -260,6 +276,7 @@ void SimulationTest(CCoinsView* base, bool fake_best_block) BOOST_CHECK(found_an_entry); BOOST_CHECK(missed_an_entry); BOOST_CHECK(uncached_an_entry); + BOOST_CHECK(flushed_without_erase); } // Run the above simulation for multiple base types. @@ -589,9 +606,9 @@ static size_t InsertCoinsMapEntry(CCoinsMap& map, CAmount value, char flags) return inserted.first->second.coin.DynamicMemoryUsage(); } -void GetCoinsMapEntry(const CCoinsMap& map, CAmount& value, char& flags) +void GetCoinsMapEntry(const CCoinsMap& map, CAmount& value, char& flags, const COutPoint& outp = OUTPOINT) { - auto it = map.find(OUTPOINT); + auto it = map.find(outp); if (it == map.end()) { value = ABSENT; flags = NO_ENTRY; @@ -877,4 +894,205 @@ BOOST_AUTO_TEST_CASE(ccoins_write) CheckWriteCoins(parent_value, child_value, parent_value, parent_flags, child_flags, parent_flags); } + +Coin MakeCoin() +{ + Coin coin; + coin.out.nValue = InsecureRand32(); + coin.nHeight = InsecureRandRange(4096); + coin.fCoinBase = 0; + return coin; +} + + +//! For CCoinsViewCache instances backed by either another cache instance or +//! leveldb, test cache behavior and flag state (DIRTY/FRESH) by +//! +//! 1. Adding a random coin to the child-most cache, +//! 2. Flushing all caches (without erasing), +//! 3. Ensure the entry still exists in the cache and has been written to parent, +//! 4. (if `do_erasing_flush`) Flushing the caches again (with erasing), +//! 5. (if `do_erasing_flush`) Ensure the entry has been written to the parent and is no longer in the cache, +//! 6. Spend the coin, ensure it no longer exists in the parent. +//! +void TestFlushBehavior( + CCoinsViewCacheTest* view, + CCoinsViewDB& base, + std::vector<CCoinsViewCacheTest*>& all_caches, + bool do_erasing_flush) +{ + CAmount value; + char flags; + size_t cache_usage; + + auto flush_all = [&all_caches](bool erase) { + // Flush in reverse order to ensure that flushes happen from children up. + for (auto i = all_caches.rbegin(); i != all_caches.rend(); ++i) { + auto cache = *i; + // hashBlock must be filled before flushing to disk; value is + // unimportant here. This is normally done during connect/disconnect block. + cache->SetBestBlock(InsecureRand256()); + erase ? cache->Flush() : cache->Sync(); + } + }; + + uint256 txid = InsecureRand256(); + COutPoint outp = COutPoint(txid, 0); + Coin coin = MakeCoin(); + // Ensure the coins views haven't seen this coin before. + BOOST_CHECK(!base.HaveCoin(outp)); + BOOST_CHECK(!view->HaveCoin(outp)); + + // --- 1. Adding a random coin to the child cache + // + view->AddCoin(outp, Coin(coin), false); + + cache_usage = view->DynamicMemoryUsage(); + // `base` shouldn't have coin (no flush yet) but `view` should have cached it. + BOOST_CHECK(!base.HaveCoin(outp)); + BOOST_CHECK(view->HaveCoin(outp)); + + GetCoinsMapEntry(view->map(), value, flags, outp); + BOOST_CHECK_EQUAL(value, coin.out.nValue); + BOOST_CHECK_EQUAL(flags, DIRTY|FRESH); + + // --- 2. Flushing all caches (without erasing) + // + flush_all(/*erase=*/ false); + + // CoinsMap usage should be unchanged since we didn't erase anything. + BOOST_CHECK_EQUAL(cache_usage, view->DynamicMemoryUsage()); + + // --- 3. Ensuring the entry still exists in the cache and has been written to parent + // + GetCoinsMapEntry(view->map(), value, flags, outp); + BOOST_CHECK_EQUAL(value, coin.out.nValue); + BOOST_CHECK_EQUAL(flags, 0); // Flags should have been wiped. + + // Both views should now have the coin. + BOOST_CHECK(base.HaveCoin(outp)); + BOOST_CHECK(view->HaveCoin(outp)); + + if (do_erasing_flush) { + // --- 4. Flushing the caches again (with erasing) + // + flush_all(/*erase=*/ true); + + // Memory usage should have gone down. + BOOST_CHECK(view->DynamicMemoryUsage() < cache_usage); + + // --- 5. Ensuring the entry is no longer in the cache + // + GetCoinsMapEntry(view->map(), value, flags, outp); + BOOST_CHECK_EQUAL(value, ABSENT); + BOOST_CHECK_EQUAL(flags, NO_ENTRY); + + view->AccessCoin(outp); + GetCoinsMapEntry(view->map(), value, flags, outp); + BOOST_CHECK_EQUAL(value, coin.out.nValue); + BOOST_CHECK_EQUAL(flags, 0); + } + + // Can't overwrite an entry without specifying that an overwrite is + // expected. + BOOST_CHECK_THROW( + view->AddCoin(outp, Coin(coin), /*possible_overwrite=*/ false), + std::logic_error); + + // --- 6. Spend the coin. + // + BOOST_CHECK(view->SpendCoin(outp)); + + // The coin should be in the cache, but spent and marked dirty. + GetCoinsMapEntry(view->map(), value, flags, outp); + BOOST_CHECK_EQUAL(value, SPENT); + BOOST_CHECK_EQUAL(flags, DIRTY); + BOOST_CHECK(!view->HaveCoin(outp)); // Coin should be considered spent in `view`. + BOOST_CHECK(base.HaveCoin(outp)); // But coin should still be unspent in `base`. + + flush_all(/*erase=*/ false); + + // Coin should be considered spent in both views. + BOOST_CHECK(!view->HaveCoin(outp)); + BOOST_CHECK(!base.HaveCoin(outp)); + + // Spent coin should not be spendable. + BOOST_CHECK(!view->SpendCoin(outp)); + + // --- Bonus check: ensure that a coin added to the base view via one cache + // can be spent by another cache which has never seen it. + // + txid = InsecureRand256(); + outp = COutPoint(txid, 0); + coin = MakeCoin(); + BOOST_CHECK(!base.HaveCoin(outp)); + BOOST_CHECK(!all_caches[0]->HaveCoin(outp)); + BOOST_CHECK(!all_caches[1]->HaveCoin(outp)); + + all_caches[0]->AddCoin(outp, std::move(coin), false); + all_caches[0]->Sync(); + BOOST_CHECK(base.HaveCoin(outp)); + BOOST_CHECK(all_caches[0]->HaveCoin(outp)); + BOOST_CHECK(!all_caches[1]->HaveCoinInCache(outp)); + + BOOST_CHECK(all_caches[1]->SpendCoin(outp)); + flush_all(/*erase=*/ false); + BOOST_CHECK(!base.HaveCoin(outp)); + BOOST_CHECK(!all_caches[0]->HaveCoin(outp)); + BOOST_CHECK(!all_caches[1]->HaveCoin(outp)); + + flush_all(/*erase=*/ true); // Erase all cache content. + + // --- Bonus check 2: ensure that a FRESH, spent coin is deleted by Sync() + // + txid = InsecureRand256(); + outp = COutPoint(txid, 0); + coin = MakeCoin(); + CAmount coin_val = coin.out.nValue; + BOOST_CHECK(!base.HaveCoin(outp)); + BOOST_CHECK(!all_caches[0]->HaveCoin(outp)); + BOOST_CHECK(!all_caches[1]->HaveCoin(outp)); + + // Add and spend from same cache without flushing. + all_caches[0]->AddCoin(outp, std::move(coin), false); + + // Coin should be FRESH in the cache. + GetCoinsMapEntry(all_caches[0]->map(), value, flags, outp); + BOOST_CHECK_EQUAL(value, coin_val); + BOOST_CHECK_EQUAL(flags, DIRTY|FRESH); + + // Base shouldn't have seen coin. + BOOST_CHECK(!base.HaveCoin(outp)); + + BOOST_CHECK(all_caches[0]->SpendCoin(outp)); + all_caches[0]->Sync(); + + // Ensure there is no sign of the coin after spend/flush. + GetCoinsMapEntry(all_caches[0]->map(), value, flags, outp); + BOOST_CHECK_EQUAL(value, ABSENT); + BOOST_CHECK_EQUAL(flags, NO_ENTRY); + BOOST_CHECK(!all_caches[0]->HaveCoinInCache(outp)); + BOOST_CHECK(!base.HaveCoin(outp)); +} + +BOOST_AUTO_TEST_CASE(ccoins_flush_behavior) +{ + // Create two in-memory caches atop a leveldb view. + CCoinsViewDB base{"test", /*nCacheSize=*/ 1 << 23, /*fMemory=*/ true, /*fWipe=*/ false}; + std::vector<CCoinsViewCacheTest*> caches; + caches.push_back(new CCoinsViewCacheTest(&base)); + caches.push_back(new CCoinsViewCacheTest(caches.back())); + + for (CCoinsViewCacheTest* view : caches) { + TestFlushBehavior(view, base, caches, /*do_erasing_flush=*/ false); + TestFlushBehavior(view, base, caches, /*do_erasing_flush=*/ true); + } + + // Clean up the caches. + while (caches.size() > 0) { + delete caches.back(); + caches.pop_back(); + } +} + BOOST_AUTO_TEST_SUITE_END() diff --git a/src/txdb.cpp b/src/txdb.cpp index f04a4e9800..c12b540b9b 100644 --- a/src/txdb.cpp +++ b/src/txdb.cpp @@ -111,7 +111,7 @@ std::vector<uint256> CCoinsViewDB::GetHeadBlocks() const { return vhashHeadBlocks; } -bool CCoinsViewDB::BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock) { +bool CCoinsViewDB::BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock, bool erase) { CDBBatch batch(*m_db); size_t count = 0; size_t changed = 0; @@ -146,8 +146,7 @@ bool CCoinsViewDB::BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock) { changed++; } count++; - CCoinsMap::iterator itOld = it++; - mapCoins.erase(itOld); + it = erase ? mapCoins.erase(it) : std::next(it); if (batch.SizeEstimate() > batch_size) { LogPrint(BCLog::COINDB, "Writing partial batch of %.2f MiB\n", batch.SizeEstimate() * (1.0 / 1048576.0)); m_db->WriteBatch(batch); diff --git a/src/txdb.h b/src/txdb.h index 5a409d7dcc..e3422846c0 100644 --- a/src/txdb.h +++ b/src/txdb.h @@ -62,7 +62,7 @@ public: bool HaveCoin(const COutPoint &outpoint) const override; uint256 GetBestBlock() const override; std::vector<uint256> GetHeadBlocks() const override; - bool BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock) override; + bool BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock, bool erase = true) override; std::unique_ptr<CCoinsViewCursor> Cursor() const override; //! Whether an unsupported database format is used. |