1  // Copyright (c) 2009-2010 Satoshi Nakamoto
  2  // Copyright (c) 2009-present The Bitcoin Core developers
  3  // Distributed under the MIT software license, see the accompanying
  4  // file COPYING or http://www.opensource.org/licenses/mit-license.php.
  5  
  6  #ifndef BITCOIN_COINS_H
  7  #define BITCOIN_COINS_H
  8  
  9  #include <attributes.h>
 10  #include <compressor.h>
 11  #include <core_memusage.h>
 12  #include <memusage.h>
 13  #include <primitives/transaction.h>
 14  #include <serialize.h>
 15  #include <support/allocators/pool.h>
 16  #include <uint256.h>
 17  #include <util/check.h>
 18  #include <util/overflow.h>
 19  #include <util/hasher.h>
 20  
 21  #include <cassert>
 22  #include <cstdint>
 23  
 24  #include <functional>
 25  #include <unordered_map>
 26  
 27  /**
 28   * A UTXO entry.
 29   *
 30   * Serialized format:
 31   * - VARINT((coinbase ? 1 : 0) | (height << 1))
 32   * - the non-spent CTxOut (via TxOutCompression)
 33   */
 34  class Coin
 35  {
 36  public:
 37      //! unspent transaction output
 38      CTxOut out;
 39  
 40      //! whether containing transaction was a coinbase
 41      unsigned int fCoinBase : 1;
 42  
 43      //! at which height this containing transaction was included in the active block chain
 44      uint32_t nHeight : 31;
 45  
 46      //! construct a Coin from a CTxOut and height/coinbase information.
 47      Coin(CTxOut&& outIn, int nHeightIn, bool fCoinBaseIn) : out(std::move(outIn)), fCoinBase(fCoinBaseIn), nHeight(nHeightIn) {}
 48      Coin(const CTxOut& outIn, int nHeightIn, bool fCoinBaseIn) : out(outIn), fCoinBase(fCoinBaseIn),nHeight(nHeightIn) {}
 49  
 50      void Clear() {
 51          out.SetNull();
 52          fCoinBase = false;
 53          nHeight = 0;
 54      }
 55  
 56      //! empty constructor
 57      Coin() : fCoinBase(false), nHeight(0) { }
 58  
 59      bool IsCoinBase() const {
 60          return fCoinBase;
 61      }
 62  
 63      template<typename Stream>
 64      void Serialize(Stream &s) const {
 65          assert(!IsSpent());
 66          uint32_t code = nHeight * uint32_t{2} + fCoinBase;
 67          ::Serialize(s, VARINT(code));
 68          ::Serialize(s, Using<TxOutCompression>(out));
 69      }
 70  
 71      template<typename Stream>
 72      void Unserialize(Stream &s) {
 73          uint32_t code = 0;
 74          ::Unserialize(s, VARINT(code));
 75          nHeight = code >> 1;
 76          fCoinBase = code & 1;
 77          ::Unserialize(s, Using<TxOutCompression>(out));
 78      }
 79  
 80      /** Either this coin never existed (see e.g. coinEmpty in coins.cpp), or it
 81        * did exist and has been spent.
 82        */
 83      bool IsSpent() const {
 84          return out.IsNull();
 85      }
 86  
 87      size_t DynamicMemoryUsage() const {
 88          return memusage::DynamicUsage(out.scriptPubKey);
 89      }
 90  };
 91  
 92  struct CCoinsCacheEntry;
 93  using CoinsCachePair = std::pair<const COutPoint, CCoinsCacheEntry>;
 94  
 95  /**
 96   * A Coin in one level of the coins database caching hierarchy.
 97   *
 98   * A coin can either be:
 99   * - unspent or spent (in which case the Coin object will be nulled out - see Coin.Clear())
100   * - DIRTY or not DIRTY
101   * - FRESH or not FRESH
102   *
103   * Out of these 2^3 = 8 states, only some combinations are valid:
104   * - unspent, FRESH, DIRTY (e.g. a new coin created in the cache)
105   * - unspent, not FRESH, DIRTY (e.g. a coin changed in the cache during a reorg)
106   * - unspent, not FRESH, not DIRTY (e.g. an unspent coin fetched from the parent cache)
107   * - spent, not FRESH, DIRTY (e.g. a coin is spent and spentness needs to be flushed to the parent)
108   */
109  struct CCoinsCacheEntry
110  {
111  private:
112      /**
113       * These are used to create a doubly linked list of flagged entries.
114       * They are set in SetDirty, SetFresh, and unset in SetClean.
115       * A flagged entry is any entry that is either DIRTY, FRESH, or both.
116       *
117       * DIRTY entries are tracked so that only modified entries can be passed to
118       * the parent cache for batch writing. This is a performance optimization
119       * compared to giving all entries in the cache to the parent and having the
120       * parent scan for only modified entries.
121       */
122      CoinsCachePair* m_prev{nullptr};
123      CoinsCachePair* m_next{nullptr};
124      uint8_t m_flags{0};
125  
126      //! Adding a flag requires a reference to the sentinel of the flagged pair linked list.
127      static void AddFlags(uint8_t flags, CoinsCachePair& pair, CoinsCachePair& sentinel) noexcept
128      {
129          Assume(flags & (DIRTY | FRESH));
130          if (!pair.second.m_flags) {
131              Assume(!pair.second.m_prev && !pair.second.m_next);
132              pair.second.m_prev = sentinel.second.m_prev;
133              pair.second.m_next = &sentinel;
134              sentinel.second.m_prev = &pair;
135              pair.second.m_prev->second.m_next = &pair;
136          }
137          Assume(pair.second.m_prev && pair.second.m_next);
138          pair.second.m_flags |= flags;
139      }
140  
141  public:
142      Coin coin; // The actual cached data.
143  
144      enum Flags {
145          /**
146           * DIRTY means the CCoinsCacheEntry is potentially different from the
147           * version in the parent cache. Failure to mark a coin as DIRTY when
148           * it is potentially different from the parent cache will cause a
149           * consensus failure, since the coin's state won't get written to the
150           * parent when the cache is flushed.
151           */
152          DIRTY = (1 << 0),
153          /**
154           * FRESH means the parent cache does not have this coin or that it is a
155           * spent coin in the parent cache. If a FRESH coin in the cache is
156           * later spent, it can be deleted entirely and doesn't ever need to be
157           * flushed to the parent. This is a performance optimization. Marking a
158           * coin as FRESH when it exists unspent in the parent cache will cause a
159           * consensus failure, since it might not be deleted from the parent
160           * when this cache is flushed.
161           */
162          FRESH = (1 << 1),
163      };
164  
165      CCoinsCacheEntry() noexcept = default;
166      explicit CCoinsCacheEntry(Coin&& coin_) noexcept : coin(std::move(coin_)) {}
167      ~CCoinsCacheEntry()
168      {
169          SetClean();
170      }
171  
172      static void SetDirty(CoinsCachePair& pair, CoinsCachePair& sentinel) noexcept { AddFlags(DIRTY, pair, sentinel); }
173      static void SetFresh(CoinsCachePair& pair, CoinsCachePair& sentinel) noexcept { AddFlags(FRESH, pair, sentinel); }
174  
175      void SetClean() noexcept
176      {
177          if (!m_flags) return;
178          m_next->second.m_prev = m_prev;
179          m_prev->second.m_next = m_next;
180          m_flags = 0;
181          m_prev = m_next = nullptr;
182      }
183      bool IsDirty() const noexcept { return m_flags & DIRTY; }
184      bool IsFresh() const noexcept { return m_flags & FRESH; }
185  
186      //! Only call Next when this entry is DIRTY, FRESH, or both
187      CoinsCachePair* Next() const noexcept
188      {
189          Assume(m_flags);
190          return m_next;
191      }
192  
193      //! Only call Prev when this entry is DIRTY, FRESH, or both
194      CoinsCachePair* Prev() const noexcept
195      {
196          Assume(m_flags);
197          return m_prev;
198      }
199  
200      //! Only use this for initializing the linked list sentinel
201      void SelfRef(CoinsCachePair& pair) noexcept
202      {
203          Assume(&pair.second == this);
204          m_prev = &pair;
205          m_next = &pair;
206          // Set sentinel to DIRTY so we can call Next on it
207          m_flags = DIRTY;
208      }
209  };
210  
211  /**
212   * PoolAllocator's MAX_BLOCK_SIZE_BYTES parameter here uses sizeof the data, and adds the size
213   * of 4 pointers. We do not know the exact node size used in the std::unordered_node implementation
214   * because it is implementation defined. Most implementations have an overhead of 1 or 2 pointers,
215   * so nodes can be connected in a linked list, and in some cases the hash value is stored as well.
216   * Using an additional sizeof(void*)*4 for MAX_BLOCK_SIZE_BYTES should thus be sufficient so that
217   * all implementations can allocate the nodes from the PoolAllocator.
218   */
219  using CCoinsMap = std::unordered_map<COutPoint,
220                                       CCoinsCacheEntry,
221                                       SaltedOutpointHasher,
222                                       std::equal_to<COutPoint>,
223                                       PoolAllocator<CoinsCachePair,
224                                                     sizeof(CoinsCachePair) + sizeof(void*) * 4>>;
225  
226  using CCoinsMapMemoryResource = CCoinsMap::allocator_type::ResourceType;
227  
228  /** Cursor for iterating over CoinsView state */
229  class CCoinsViewCursor
230  {
231  public:
232      CCoinsViewCursor(const uint256 &hashBlockIn): hashBlock(hashBlockIn) {}
233      virtual ~CCoinsViewCursor() = default;
234  
235      virtual bool GetKey(COutPoint &key) const = 0;
236      virtual bool GetValue(Coin &coin) const = 0;
237  
238      virtual bool Valid() const = 0;
239      virtual void Next() = 0;
240  
241      //! Get best block at the time this cursor was created
242      const uint256 &GetBestBlock() const { return hashBlock; }
243  private:
244      uint256 hashBlock;
245  };
246  
247  /**
248   * Cursor for iterating over the linked list of flagged entries in CCoinsViewCache.
249   *
250   * This is a helper struct to encapsulate the diverging logic between a non-erasing
251   * CCoinsViewCache::Sync and an erasing CCoinsViewCache::Flush. This allows the receiver
252   * of CCoinsView::BatchWrite to iterate through the flagged entries without knowing
253   * the caller's intent.
254   *
255   * However, the receiver can still call CoinsViewCacheCursor::WillErase to see if the
256   * caller will erase the entry after BatchWrite returns. If so, the receiver can
257   * perform optimizations such as moving the coin out of the CCoinsCachEntry instead
258   * of copying it.
259   */
260  struct CoinsViewCacheCursor
261  {
262      //! If will_erase is not set, iterating through the cursor will erase spent coins from the map,
263      //! and other coins will be unflagged (removing them from the linked list).
264      //! If will_erase is set, the underlying map and linked list will not be modified,
265      //! as the caller is expected to wipe the entire map anyway.
266      //! This is an optimization compared to erasing all entries as the cursor iterates them when will_erase is set.
267      //! Calling CCoinsMap::clear() afterwards is faster because a CoinsCachePair cannot be coerced back into a
268      //! CCoinsMap::iterator to be erased, and must therefore be looked up again by key in the CCoinsMap before being erased.
269      CoinsViewCacheCursor(size_t& dirty_count LIFETIMEBOUND,
270                           CoinsCachePair& sentinel LIFETIMEBOUND,
271                           CCoinsMap& map LIFETIMEBOUND,
272                           bool will_erase) noexcept
273          : m_dirty_count(dirty_count), m_sentinel(sentinel), m_map(map), m_will_erase(will_erase) {}
274  
275      inline CoinsCachePair* Begin() const noexcept { return m_sentinel.second.Next(); }
276      inline CoinsCachePair* End() const noexcept { return &m_sentinel; }
277  
278      //! Return the next entry after current, possibly erasing current
279      inline CoinsCachePair* NextAndMaybeErase(CoinsCachePair& current) noexcept
280      {
281          const auto next_entry{current.second.Next()};
282          Assume(TrySub(m_dirty_count, current.second.IsDirty()));
283          // If we are not going to erase the cache, we must still erase spent entries.
284          // Otherwise, clear the state of the entry.
285          if (!m_will_erase) {
286              if (current.second.coin.IsSpent()) {
287                  assert(current.second.coin.DynamicMemoryUsage() == 0); // scriptPubKey was already cleared in SpendCoin
288                  m_map.erase(current.first);
289              } else {
290                  current.second.SetClean();
291              }
292          }
293          return next_entry;
294      }
295  
296      inline bool WillErase(CoinsCachePair& current) const noexcept { return m_will_erase || current.second.coin.IsSpent(); }
297      size_t GetDirtyCount() const noexcept { return m_dirty_count; }
298      size_t GetTotalCount() const noexcept { return m_map.size(); }
299  private:
300      size_t& m_dirty_count;
301      CoinsCachePair& m_sentinel;
302      CCoinsMap& m_map;
303      bool m_will_erase;
304  };
305  
306  /** Abstract view on the open txout dataset. */
307  class CCoinsView
308  {
309  public:
310      //! Retrieve the Coin (unspent transaction output) for a given outpoint.
311      //! May populate the cache. Use PeekCoin() to perform a non-caching lookup.
312      virtual std::optional<Coin> GetCoin(const COutPoint& outpoint) const;
313  
314      //! Retrieve the Coin (unspent transaction output) for a given outpoint, without caching results.
315      //! Does not populate the cache. Use GetCoin() to cache the result.
316      virtual std::optional<Coin> PeekCoin(const COutPoint& outpoint) const;
317  
318      //! Just check whether a given outpoint is unspent.
319      //! May populate the cache. Use PeekCoin() to perform a non-caching lookup.
320      virtual bool HaveCoin(const COutPoint &outpoint) const;
321  
322      //! Retrieve the block hash whose state this CCoinsView currently represents
323      virtual uint256 GetBestBlock() const;
324  
325      //! Retrieve the range of blocks that may have been only partially written.
326      //! If the database is in a consistent state, the result is the empty vector.
327      //! Otherwise, a two-element vector is returned consisting of the new and
328      //! the old block hash, in that order.
329      virtual std::vector<uint256> GetHeadBlocks() const;
330  
331      //! Do a bulk modification (multiple Coin changes + BestBlock change).
332      //! The passed cursor is used to iterate through the coins.
333      virtual void BatchWrite(CoinsViewCacheCursor& cursor, const uint256& hashBlock);
334  
335      //! Get a cursor to iterate over the whole state
336      virtual std::unique_ptr<CCoinsViewCursor> Cursor() const;
337  
338      //! As we use CCoinsViews polymorphically, have a virtual destructor
339      virtual ~CCoinsView() = default;
340  
341      //! Estimate database size (0 if not implemented)
342      virtual size_t EstimateSize() const { return 0; }
343  };
344  
345  
346  /** CCoinsView backed by another CCoinsView */
347  class CCoinsViewBacked : public CCoinsView
348  {
349  protected:
350      CCoinsView *base;
351  
352  public:
353      CCoinsViewBacked(CCoinsView *viewIn);
354      std::optional<Coin> GetCoin(const COutPoint& outpoint) const override;
355      std::optional<Coin> PeekCoin(const COutPoint& outpoint) const override;
356      bool HaveCoin(const COutPoint &outpoint) const override;
357      uint256 GetBestBlock() const override;
358      std::vector<uint256> GetHeadBlocks() const override;
359      void SetBackend(CCoinsView &viewIn);
360      void BatchWrite(CoinsViewCacheCursor& cursor, const uint256& hashBlock) override;
361      std::unique_ptr<CCoinsViewCursor> Cursor() const override;
362      size_t EstimateSize() const override;
363  };
364  
365  
366  /** CCoinsView that adds a memory cache for transactions to another CCoinsView */
367  class CCoinsViewCache : public CCoinsViewBacked
368  {
369  private:
370      const bool m_deterministic;
371  
372  protected:
373      /**
374       * Make mutable so that we can "fill the cache" even from Get-methods
375       * declared as "const".
376       */
377      mutable uint256 hashBlock;
378      mutable CCoinsMapMemoryResource m_cache_coins_memory_resource{};
379      /* The starting sentinel of the flagged entry circular doubly linked list. */
380      mutable CoinsCachePair m_sentinel;
381      mutable CCoinsMap cacheCoins;
382  
383      /* Cached dynamic memory usage for the inner Coin objects. */
384      mutable size_t cachedCoinsUsage{0};
385      /* Running count of dirty Coin cache entries. */
386      mutable size_t m_dirty_count{0};
387  
388      /**
389       * Discard all modifications made to this cache without flushing to the base view.
390       * This can be used to efficiently reuse a cache instance across multiple operations.
391       */
392      void Reset() noexcept;
393  
394      /* Fetch the coin from base. Used for cache misses in FetchCoin. */
395      virtual std::optional<Coin> FetchCoinFromBase(const COutPoint& outpoint) const;
396  
397  public:
398      CCoinsViewCache(CCoinsView *baseIn, bool deterministic = false);
399  
400      /**
401       * By deleting the copy constructor, we prevent accidentally using it when one intends to create a cache on top of a base cache.
402       */
403      CCoinsViewCache(const CCoinsViewCache &) = delete;
404  
405      // Standard CCoinsView methods
406      std::optional<Coin> GetCoin(const COutPoint& outpoint) const override;
407      std::optional<Coin> PeekCoin(const COutPoint& outpoint) const override;
408      bool HaveCoin(const COutPoint &outpoint) const override;
409      uint256 GetBestBlock() const override;
410      void SetBestBlock(const uint256 &hashBlock);
411      void BatchWrite(CoinsViewCacheCursor& cursor, const uint256& hashBlock) override;
412      std::unique_ptr<CCoinsViewCursor> Cursor() const override {
413          throw std::logic_error("CCoinsViewCache cursor iteration not supported.");
414      }
415  
416      /**
417       * Check if we have the given utxo already loaded in this cache.
418       * The semantics are the same as HaveCoin(), but no calls to
419       * the backing CCoinsView are made.
420       */
421      bool HaveCoinInCache(const COutPoint &outpoint) const;
422  
423      /**
424       * Return a reference to Coin in the cache, or coinEmpty if not found. This is
425       * more efficient than GetCoin.
426       *
427       * Generally, do not hold the reference returned for more than a short scope.
428       * While the current implementation allows for modifications to the contents
429       * of the cache while holding the reference, this behavior should not be relied
430       * on! To be safe, best to not hold the returned reference through any other
431       * calls to this cache.
432       */
433      const Coin& AccessCoin(const COutPoint &output) const;
434  
435      /**
436       * Add a coin. Set possible_overwrite to true if an unspent version may
437       * already exist in the cache.
438       */
439      void AddCoin(const COutPoint& outpoint, Coin&& coin, bool possible_overwrite);
440  
441      /**
442       * Emplace a coin into cacheCoins without performing any checks, marking
443       * the emplaced coin as dirty.
444       *
445       * NOT FOR GENERAL USE. Used only when loading coins from a UTXO snapshot.
446       * @sa ChainstateManager::PopulateAndValidateSnapshot()
447       */
448      void EmplaceCoinInternalDANGER(COutPoint&& outpoint, Coin&& coin);
449  
450      /**
451       * Spend a coin. Pass moveto in order to get the deleted data.
452       * If no unspent output exists for the passed outpoint, this call
453       * has no effect.
454       */
455      bool SpendCoin(const COutPoint &outpoint, Coin* moveto = nullptr);
456  
457      /**
458       * Push the modifications applied to this cache to its base and wipe local state.
459       * Failure to call this method or Sync() before destruction will cause the changes
460       * to be forgotten.
461       * If reallocate_cache is false, the cache will retain the same memory footprint
462       * after flushing and should be destroyed to deallocate.
463       */
464      void Flush(bool reallocate_cache = true);
465  
466      /**
467       * Push the modifications applied to this cache to its base while retaining
468       * the contents of this cache (except for spent coins, which we erase).
469       * Failure to call this method or Flush() before destruction will cause the changes
470       * to be forgotten.
471       */
472      void Sync();
473  
474      /**
475       * Removes the UTXO with the given outpoint from the cache, if it is
476       * not modified.
477       */
478      void Uncache(const COutPoint &outpoint);
479  
480      //! Size of the cache (in number of transaction outputs)
481      unsigned int GetCacheSize() const;
482  
483      //! Number of dirty cache entries (transaction outputs)
484      size_t GetDirtyCount() const noexcept { return m_dirty_count; }
485  
486      //! Calculate the size of the cache (in bytes)
487      size_t DynamicMemoryUsage() const;
488  
489      //! Check whether all prevouts of the transaction are present in the UTXO set represented by this view
490      bool HaveInputs(const CTransaction& tx) const;
491  
492      //! Force a reallocation of the cache map. This is required when downsizing
493      //! the cache because the map's allocator may be hanging onto a lot of
494      //! memory despite having called .clear().
495      //!
496      //! See: https://stackoverflow.com/questions/42114044/how-to-release-unordered-map-memory
497      void ReallocateCache();
498  
499      //! Run an internal sanity check on the cache data structure. */
500      void SanityCheck() const;
501  
502      class ResetGuard
503      {
504      private:
505          friend CCoinsViewCache;
506          CCoinsViewCache& m_cache;
507          explicit ResetGuard(CCoinsViewCache& cache LIFETIMEBOUND) noexcept : m_cache{cache} {}
508  
509      public:
510          ResetGuard(const ResetGuard&) = delete;
511          ResetGuard& operator=(const ResetGuard&) = delete;
512          ResetGuard(ResetGuard&&) = delete;
513          ResetGuard& operator=(ResetGuard&&) = delete;
514  
515          ~ResetGuard() { m_cache.Reset(); }
516      };
517  
518      //! Create a scoped guard that will call `Reset()` on this cache when it goes out of scope.
519      [[nodiscard]] ResetGuard CreateResetGuard() noexcept { return ResetGuard{*this}; }
520  
521  private:
522      /**
523       * @note this is marked const, but may actually append to `cacheCoins`, increasing
524       * memory usage.
525       */
526      CCoinsMap::iterator FetchCoin(const COutPoint &outpoint) const;
527  };
528  
529  /**
530   * CCoinsViewCache overlay that avoids populating/mutating parent cache layers on cache misses.
531   *
532   * This is achieved by fetching coins from the base view using PeekCoin() instead of GetCoin(),
533   * so intermediate CCoinsViewCache layers are not filled.
534   *
535   * Used during ConnectBlock() as an ephemeral, resettable top-level view that is flushed only
536   * on success, so invalid blocks don't pollute the underlying cache.
537   */
538  class CoinsViewOverlay : public CCoinsViewCache
539  {
540  private:
541      std::optional<Coin> FetchCoinFromBase(const COutPoint& outpoint) const override
542      {
543          return base->PeekCoin(outpoint);
544      }
545  
546  public:
547      using CCoinsViewCache::CCoinsViewCache;
548  };
549  
550  //! Utility function to add all of a transaction's outputs to a cache.
551  //! When check is false, this assumes that overwrites are only possible for coinbase transactions.
552  //! When check is true, the underlying view may be queried to determine whether an addition is
553  //! an overwrite.
554  // TODO: pass in a boolean to limit these possible overwrites to known
555  // (pre-BIP34) cases.
556  void AddCoins(CCoinsViewCache& cache, const CTransaction& tx, int nHeight, bool check = false);
557  
558  //! Utility function to find any unspent output with a given txid.
559  //! This function can be quite expensive because in the event of a transaction
560  //! which is not found in the cache, it can cause up to MAX_OUTPUTS_PER_BLOCK
561  //! lookups to database, so it should be used with care.
562  const Coin& AccessByTxid(const CCoinsViewCache& cache, const Txid& txid);
563  
564  /**
565   * This is a minimally invasive approach to shutdown on LevelDB read errors from the
566   * chainstate, while keeping user interface out of the common library, which is shared
567   * between bitcoind, and bitcoin-qt and non-server tools.
568   *
569   * Writes do not need similar protection, as failure to write is handled by the caller.
570  */
571  class CCoinsViewErrorCatcher final : public CCoinsViewBacked
572  {
573  public:
574      explicit CCoinsViewErrorCatcher(CCoinsView* view) : CCoinsViewBacked(view) {}
575  
576      void AddReadErrCallback(std::function<void()> f) {
577          m_err_callbacks.emplace_back(std::move(f));
578      }
579  
580      std::optional<Coin> GetCoin(const COutPoint& outpoint) const override;
581      bool HaveCoin(const COutPoint &outpoint) const override;
582      std::optional<Coin> PeekCoin(const COutPoint& outpoint) const override;
583  
584  private:
585      /** A list of callbacks to execute upon leveldb read error. */
586      std::vector<std::function<void()>> m_err_callbacks;
587  
588  };
589  
590  #endif // BITCOIN_COINS_H