coins.cpp
1 // Copyright (c) 2012-present The Bitcoin Core developers 2 // Distributed under the MIT software license, see the accompanying 3 // file COPYING or http://www.opensource.org/licenses/mit-license.php. 4 5 #include <coins.h> 6 7 #include <consensus/consensus.h> 8 #include <random.h> 9 #include <uint256.h> 10 #include <util/log.h> 11 #include <util/trace.h> 12 13 TRACEPOINT_SEMAPHORE(utxocache, add); 14 TRACEPOINT_SEMAPHORE(utxocache, spent); 15 TRACEPOINT_SEMAPHORE(utxocache, uncache); 16 17 std::optional<Coin> CCoinsView::GetCoin(const COutPoint& outpoint) const { return std::nullopt; } 18 std::optional<Coin> CCoinsView::PeekCoin(const COutPoint& outpoint) const { return GetCoin(outpoint); } 19 uint256 CCoinsView::GetBestBlock() const { return uint256(); } 20 std::vector<uint256> CCoinsView::GetHeadBlocks() const { return std::vector<uint256>(); } 21 void CCoinsView::BatchWrite(CoinsViewCacheCursor& cursor, const uint256& hashBlock) 22 { 23 for (auto it{cursor.Begin()}; it != cursor.End(); it = cursor.NextAndMaybeErase(*it)) { } 24 } 25 26 std::unique_ptr<CCoinsViewCursor> CCoinsView::Cursor() const { return nullptr; } 27 28 bool CCoinsView::HaveCoin(const COutPoint &outpoint) const 29 { 30 return GetCoin(outpoint).has_value(); 31 } 32 33 CCoinsViewBacked::CCoinsViewBacked(CCoinsView *viewIn) : base(viewIn) { } 34 std::optional<Coin> CCoinsViewBacked::GetCoin(const COutPoint& outpoint) const { return base->GetCoin(outpoint); } 35 std::optional<Coin> CCoinsViewBacked::PeekCoin(const COutPoint& outpoint) const { return base->PeekCoin(outpoint); } 36 bool CCoinsViewBacked::HaveCoin(const COutPoint &outpoint) const { return base->HaveCoin(outpoint); } 37 uint256 CCoinsViewBacked::GetBestBlock() const { return base->GetBestBlock(); } 38 std::vector<uint256> CCoinsViewBacked::GetHeadBlocks() const { return base->GetHeadBlocks(); } 39 void CCoinsViewBacked::SetBackend(CCoinsView &viewIn) { base = &viewIn; } 40 void CCoinsViewBacked::BatchWrite(CoinsViewCacheCursor& cursor, const uint256& hashBlock) { base->BatchWrite(cursor, hashBlock); } 41 std::unique_ptr<CCoinsViewCursor> CCoinsViewBacked::Cursor() const { return base->Cursor(); } 42 size_t CCoinsViewBacked::EstimateSize() const { return base->EstimateSize(); } 43 44 std::optional<Coin> CCoinsViewCache::PeekCoin(const COutPoint& outpoint) const 45 { 46 if (auto it{cacheCoins.find(outpoint)}; it != cacheCoins.end()) { 47 return it->second.coin.IsSpent() ? std::nullopt : std::optional{it->second.coin}; 48 } 49 return base->PeekCoin(outpoint); 50 } 51 52 CCoinsViewCache::CCoinsViewCache(CCoinsView* baseIn, bool deterministic) : 53 CCoinsViewBacked(baseIn), m_deterministic(deterministic), 54 cacheCoins(0, SaltedOutpointHasher(/*deterministic=*/deterministic), CCoinsMap::key_equal{}, &m_cache_coins_memory_resource) 55 { 56 m_sentinel.second.SelfRef(m_sentinel); 57 } 58 59 size_t CCoinsViewCache::DynamicMemoryUsage() const { 60 return memusage::DynamicUsage(cacheCoins) + cachedCoinsUsage; 61 } 62 63 std::optional<Coin> CCoinsViewCache::FetchCoinFromBase(const COutPoint& outpoint) const 64 { 65 return base->GetCoin(outpoint); 66 } 67 68 CCoinsMap::iterator CCoinsViewCache::FetchCoin(const COutPoint &outpoint) const { 69 const auto [ret, inserted] = cacheCoins.try_emplace(outpoint); 70 if (inserted) { 71 if (auto coin{FetchCoinFromBase(outpoint)}) { 72 ret->second.coin = std::move(*coin); 73 cachedCoinsUsage += ret->second.coin.DynamicMemoryUsage(); 74 Assert(!ret->second.coin.IsSpent()); 75 } else { 76 cacheCoins.erase(ret); 77 return cacheCoins.end(); 78 } 79 } 80 return ret; 81 } 82 83 std::optional<Coin> CCoinsViewCache::GetCoin(const COutPoint& outpoint) const 84 { 85 if (auto it{FetchCoin(outpoint)}; it != cacheCoins.end() && !it->second.coin.IsSpent()) return it->second.coin; 86 return std::nullopt; 87 } 88 89 void CCoinsViewCache::AddCoin(const COutPoint &outpoint, Coin&& coin, bool possible_overwrite) { 90 assert(!coin.IsSpent()); 91 if (coin.out.scriptPubKey.IsUnspendable()) return; 92 CCoinsMap::iterator it; 93 bool inserted; 94 std::tie(it, inserted) = cacheCoins.emplace(std::piecewise_construct, std::forward_as_tuple(outpoint), std::tuple<>()); 95 bool fresh = false; 96 if (!possible_overwrite) { 97 if (!it->second.coin.IsSpent()) { 98 throw std::logic_error("Attempted to overwrite an unspent coin (when possible_overwrite is false)"); 99 } 100 // If the coin exists in this cache as a spent coin and is DIRTY, then 101 // its spentness hasn't been flushed to the parent cache. We're 102 // re-adding the coin to this cache now but we can't mark it as FRESH. 103 // If we mark it FRESH and then spend it before the cache is flushed 104 // we would remove it from this cache and would never flush spentness 105 // to the parent cache. 106 // 107 // Re-adding a spent coin can happen in the case of a re-org (the coin 108 // is 'spent' when the block adding it is disconnected and then 109 // re-added when it is also added in a newly connected block). 110 // 111 // If the coin doesn't exist in the current cache, or is spent but not 112 // DIRTY, then it can be marked FRESH. 113 fresh = !it->second.IsDirty(); 114 } 115 if (!inserted) { 116 Assume(TrySub(m_dirty_count, it->second.IsDirty())); 117 Assume(TrySub(cachedCoinsUsage, it->second.coin.DynamicMemoryUsage())); 118 } 119 it->second.coin = std::move(coin); 120 CCoinsCacheEntry::SetDirty(*it, m_sentinel); 121 ++m_dirty_count; 122 if (fresh) CCoinsCacheEntry::SetFresh(*it, m_sentinel); 123 cachedCoinsUsage += it->second.coin.DynamicMemoryUsage(); 124 TRACEPOINT(utxocache, add, 125 outpoint.hash.data(), 126 (uint32_t)outpoint.n, 127 (uint32_t)it->second.coin.nHeight, 128 (int64_t)it->second.coin.out.nValue, 129 (bool)it->second.coin.IsCoinBase()); 130 } 131 132 void CCoinsViewCache::EmplaceCoinInternalDANGER(COutPoint&& outpoint, Coin&& coin) { 133 const auto mem_usage{coin.DynamicMemoryUsage()}; 134 auto [it, inserted] = cacheCoins.try_emplace(std::move(outpoint), std::move(coin)); 135 if (inserted) { 136 CCoinsCacheEntry::SetDirty(*it, m_sentinel); 137 ++m_dirty_count; 138 cachedCoinsUsage += mem_usage; 139 } 140 } 141 142 void AddCoins(CCoinsViewCache& cache, const CTransaction &tx, int nHeight, bool check_for_overwrite) { 143 bool fCoinbase = tx.IsCoinBase(); 144 const Txid& txid = tx.GetHash(); 145 for (size_t i = 0; i < tx.vout.size(); ++i) { 146 bool overwrite = check_for_overwrite ? cache.HaveCoin(COutPoint(txid, i)) : fCoinbase; 147 // Coinbase transactions can always be overwritten, in order to correctly 148 // deal with the pre-BIP30 occurrences of duplicate coinbase transactions. 149 cache.AddCoin(COutPoint(txid, i), Coin(tx.vout[i], nHeight, fCoinbase), overwrite); 150 } 151 } 152 153 bool CCoinsViewCache::SpendCoin(const COutPoint &outpoint, Coin* moveout) { 154 CCoinsMap::iterator it = FetchCoin(outpoint); 155 if (it == cacheCoins.end()) return false; 156 Assume(TrySub(m_dirty_count, it->second.IsDirty())); 157 Assume(TrySub(cachedCoinsUsage, it->second.coin.DynamicMemoryUsage())); 158 TRACEPOINT(utxocache, spent, 159 outpoint.hash.data(), 160 (uint32_t)outpoint.n, 161 (uint32_t)it->second.coin.nHeight, 162 (int64_t)it->second.coin.out.nValue, 163 (bool)it->second.coin.IsCoinBase()); 164 if (moveout) { 165 *moveout = std::move(it->second.coin); 166 } 167 if (it->second.IsFresh()) { 168 cacheCoins.erase(it); 169 } else { 170 CCoinsCacheEntry::SetDirty(*it, m_sentinel); 171 ++m_dirty_count; 172 it->second.coin.Clear(); 173 } 174 return true; 175 } 176 177 static const Coin coinEmpty; 178 179 const Coin& CCoinsViewCache::AccessCoin(const COutPoint &outpoint) const { 180 CCoinsMap::const_iterator it = FetchCoin(outpoint); 181 if (it == cacheCoins.end()) { 182 return coinEmpty; 183 } else { 184 return it->second.coin; 185 } 186 } 187 188 bool CCoinsViewCache::HaveCoin(const COutPoint &outpoint) const { 189 CCoinsMap::const_iterator it = FetchCoin(outpoint); 190 return (it != cacheCoins.end() && !it->second.coin.IsSpent()); 191 } 192 193 bool CCoinsViewCache::HaveCoinInCache(const COutPoint &outpoint) const { 194 CCoinsMap::const_iterator it = cacheCoins.find(outpoint); 195 return (it != cacheCoins.end() && !it->second.coin.IsSpent()); 196 } 197 198 uint256 CCoinsViewCache::GetBestBlock() const { 199 if (hashBlock.IsNull()) 200 hashBlock = base->GetBestBlock(); 201 return hashBlock; 202 } 203 204 void CCoinsViewCache::SetBestBlock(const uint256 &hashBlockIn) { 205 hashBlock = hashBlockIn; 206 } 207 208 void CCoinsViewCache::BatchWrite(CoinsViewCacheCursor& cursor, const uint256& hashBlockIn) 209 { 210 for (auto it{cursor.Begin()}; it != cursor.End(); it = cursor.NextAndMaybeErase(*it)) { 211 if (!it->second.IsDirty()) { // TODO a cursor can only contain dirty entries 212 continue; 213 } 214 auto [itUs, inserted]{cacheCoins.try_emplace(it->first)}; 215 if (inserted) { 216 if (it->second.IsFresh() && it->second.coin.IsSpent()) { 217 cacheCoins.erase(itUs); // TODO fresh coins should have been removed at spend 218 } else { 219 // The parent cache does not have an entry, while the child cache does. 220 // Move the data up and mark it as dirty. 221 CCoinsCacheEntry& entry{itUs->second}; 222 assert(entry.coin.DynamicMemoryUsage() == 0); 223 if (cursor.WillErase(*it)) { 224 // Since this entry will be erased, 225 // we can move the coin into us instead of copying it 226 entry.coin = std::move(it->second.coin); 227 } else { 228 entry.coin = it->second.coin; 229 } 230 CCoinsCacheEntry::SetDirty(*itUs, m_sentinel); 231 ++m_dirty_count; 232 cachedCoinsUsage += entry.coin.DynamicMemoryUsage(); 233 // We can mark it FRESH in the parent if it was FRESH in the child 234 // Otherwise it might have just been flushed from the parent's cache 235 // and already exist in the grandparent 236 if (it->second.IsFresh()) CCoinsCacheEntry::SetFresh(*itUs, m_sentinel); 237 } 238 } else { 239 // Found the entry in the parent cache 240 if (it->second.IsFresh() && !itUs->second.coin.IsSpent()) { 241 // The coin was marked FRESH in the child cache, but the coin 242 // exists in the parent cache. If this ever happens, it means 243 // the FRESH flag was misapplied and there is a logic error in 244 // the calling code. 245 throw std::logic_error("FRESH flag misapplied to coin that exists in parent cache"); 246 } 247 248 if (itUs->second.IsFresh() && it->second.coin.IsSpent()) { 249 // The grandparent cache does not have an entry, and the coin 250 // has been spent. We can just delete it from the parent cache. 251 Assume(TrySub(m_dirty_count, itUs->second.IsDirty())); 252 Assume(TrySub(cachedCoinsUsage, itUs->second.coin.DynamicMemoryUsage())); 253 cacheCoins.erase(itUs); 254 } else { 255 // A normal modification. 256 Assume(TrySub(cachedCoinsUsage, itUs->second.coin.DynamicMemoryUsage())); 257 if (cursor.WillErase(*it)) { 258 // Since this entry will be erased, 259 // we can move the coin into us instead of copying it 260 itUs->second.coin = std::move(it->second.coin); 261 } else { 262 itUs->second.coin = it->second.coin; 263 } 264 cachedCoinsUsage += itUs->second.coin.DynamicMemoryUsage(); 265 if (!itUs->second.IsDirty()) { 266 CCoinsCacheEntry::SetDirty(*itUs, m_sentinel); 267 ++m_dirty_count; 268 } 269 // NOTE: It isn't safe to mark the coin as FRESH in the parent 270 // cache. If it already existed and was spent in the parent 271 // cache then marking it FRESH would prevent that spentness 272 // from being flushed to the grandparent. 273 } 274 } 275 } 276 SetBestBlock(hashBlockIn); 277 } 278 279 void CCoinsViewCache::Flush(bool reallocate_cache) 280 { 281 auto cursor{CoinsViewCacheCursor(m_dirty_count, m_sentinel, cacheCoins, /*will_erase=*/true)}; 282 base->BatchWrite(cursor, hashBlock); 283 Assume(m_dirty_count == 0); 284 cacheCoins.clear(); 285 if (reallocate_cache) { 286 ReallocateCache(); 287 } 288 cachedCoinsUsage = 0; 289 } 290 291 void CCoinsViewCache::Sync() 292 { 293 auto cursor{CoinsViewCacheCursor(m_dirty_count, m_sentinel, cacheCoins, /*will_erase=*/false)}; 294 base->BatchWrite(cursor, hashBlock); 295 Assume(m_dirty_count == 0); 296 if (m_sentinel.second.Next() != &m_sentinel) { 297 /* BatchWrite must clear flags of all entries */ 298 throw std::logic_error("Not all unspent flagged entries were cleared"); 299 } 300 } 301 302 void CCoinsViewCache::Reset() noexcept 303 { 304 cacheCoins.clear(); 305 cachedCoinsUsage = 0; 306 m_dirty_count = 0; 307 SetBestBlock(uint256::ZERO); 308 } 309 310 void CCoinsViewCache::Uncache(const COutPoint& hash) 311 { 312 CCoinsMap::iterator it = cacheCoins.find(hash); 313 if (it != cacheCoins.end() && !it->second.IsDirty()) { 314 Assume(TrySub(cachedCoinsUsage, it->second.coin.DynamicMemoryUsage())); 315 TRACEPOINT(utxocache, uncache, 316 hash.hash.data(), 317 (uint32_t)hash.n, 318 (uint32_t)it->second.coin.nHeight, 319 (int64_t)it->second.coin.out.nValue, 320 (bool)it->second.coin.IsCoinBase()); 321 cacheCoins.erase(it); 322 } 323 } 324 325 unsigned int CCoinsViewCache::GetCacheSize() const { 326 return cacheCoins.size(); 327 } 328 329 bool CCoinsViewCache::HaveInputs(const CTransaction& tx) const 330 { 331 if (!tx.IsCoinBase()) { 332 for (unsigned int i = 0; i < tx.vin.size(); i++) { 333 if (!HaveCoin(tx.vin[i].prevout)) { 334 return false; 335 } 336 } 337 } 338 return true; 339 } 340 341 void CCoinsViewCache::ReallocateCache() 342 { 343 // Cache should be empty when we're calling this. 344 assert(cacheCoins.size() == 0); 345 cacheCoins.~CCoinsMap(); 346 m_cache_coins_memory_resource.~CCoinsMapMemoryResource(); 347 ::new (&m_cache_coins_memory_resource) CCoinsMapMemoryResource{}; 348 ::new (&cacheCoins) CCoinsMap{0, SaltedOutpointHasher{/*deterministic=*/m_deterministic}, CCoinsMap::key_equal{}, &m_cache_coins_memory_resource}; 349 } 350 351 void CCoinsViewCache::SanityCheck() const 352 { 353 size_t recomputed_usage = 0; 354 size_t count_dirty = 0; 355 for (const auto& [_, entry] : cacheCoins) { 356 if (entry.coin.IsSpent()) { 357 assert(entry.IsDirty() && !entry.IsFresh()); // A spent coin must be dirty and cannot be fresh 358 } else { 359 assert(entry.IsDirty() || !entry.IsFresh()); // An unspent coin must not be fresh if not dirty 360 } 361 362 // Recompute cachedCoinsUsage. 363 recomputed_usage += entry.coin.DynamicMemoryUsage(); 364 365 // Count the number of entries we expect in the linked list. 366 if (entry.IsDirty()) ++count_dirty; 367 } 368 // Iterate over the linked list of flagged entries. 369 size_t count_linked = 0; 370 for (auto it = m_sentinel.second.Next(); it != &m_sentinel; it = it->second.Next()) { 371 // Verify linked list integrity. 372 assert(it->second.Next()->second.Prev() == it); 373 assert(it->second.Prev()->second.Next() == it); 374 // Verify they are actually flagged. 375 assert(it->second.IsDirty()); 376 // Count the number of entries actually in the list. 377 ++count_linked; 378 } 379 assert(count_dirty == count_linked && count_dirty == m_dirty_count); 380 assert(recomputed_usage == cachedCoinsUsage); 381 } 382 383 static const uint64_t MIN_TRANSACTION_OUTPUT_WEIGHT{WITNESS_SCALE_FACTOR * ::GetSerializeSize(CTxOut())}; 384 static const uint64_t MAX_OUTPUTS_PER_BLOCK{MAX_BLOCK_WEIGHT / MIN_TRANSACTION_OUTPUT_WEIGHT}; 385 386 const Coin& AccessByTxid(const CCoinsViewCache& view, const Txid& txid) 387 { 388 COutPoint iter(txid, 0); 389 while (iter.n < MAX_OUTPUTS_PER_BLOCK) { 390 const Coin& alternate = view.AccessCoin(iter); 391 if (!alternate.IsSpent()) return alternate; 392 ++iter.n; 393 } 394 return coinEmpty; 395 } 396 397 template <typename ReturnType, typename Func> 398 static ReturnType ExecuteBackedWrapper(Func func, const std::vector<std::function<void()>>& err_callbacks) 399 { 400 try { 401 return func(); 402 } catch(const std::runtime_error& e) { 403 for (const auto& f : err_callbacks) { 404 f(); 405 } 406 LogError("Error reading from database: %s\n", e.what()); 407 // Starting the shutdown sequence and returning false to the caller would be 408 // interpreted as 'entry not found' (as opposed to unable to read data), and 409 // could lead to invalid interpretation. Just exit immediately, as we can't 410 // continue anyway, and all writes should be atomic. 411 std::abort(); 412 } 413 } 414 415 std::optional<Coin> CCoinsViewErrorCatcher::GetCoin(const COutPoint& outpoint) const 416 { 417 return ExecuteBackedWrapper<std::optional<Coin>>([&]() { return CCoinsViewBacked::GetCoin(outpoint); }, m_err_callbacks); 418 } 419 420 bool CCoinsViewErrorCatcher::HaveCoin(const COutPoint& outpoint) const 421 { 422 return ExecuteBackedWrapper<bool>([&]() { return CCoinsViewBacked::HaveCoin(outpoint); }, m_err_callbacks); 423 } 424 425 std::optional<Coin> CCoinsViewErrorCatcher::PeekCoin(const COutPoint& outpoint) const 426 { 427 return ExecuteBackedWrapper<std::optional<Coin>>([&]() { return CCoinsViewBacked::PeekCoin(outpoint); }, m_err_callbacks); 428 }