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