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