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