src/coins.h

   1 // Copyright (c) 2009-2010 Satoshi Nakamoto
   2 // Copyright (c) 2009-2016 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 "primitives/transaction.h"
  10 #include "compressor.h"
  11 #include "core_memusage.h"
  12 #include "hash.h"
  13 #include "memusage.h"
  14 #include "serialize.h"
  15 #include "uint256.h"
  16
  17 #include <assert.h>
  18 #include <stdint.h>
  19
  20 #include <unordered_map>
  21
  22 /**
  23  * A UTXO entry.
  24  *
  25  * Serialized format:
  26  * - VARINT((coinbase ? 1 : 0) | (height << 1))
  27  * - the non-spent CTxOut (via CTxOutCompressor)
  28  */
  29 class Coin
  30 {
  31 public:
  32     //! unspent transaction output
  33     CTxOut out;
  34
  35     //! whether containing transaction was a coinbase
  36     unsigned int fCoinBase : 1;
  37
  38     //! at which height this containing transaction was included in the active block chain
  39     uint32_t nHeight : 31;
  40
  41     //! construct a Coin from a CTxOut and height/coinbase information.
  42     Coin(CTxOut&& outIn, int nHeightIn, bool fCoinBaseIn) : out(std::move(outIn)), fCoinBase(fCoinBaseIn), nHeight(nHeightIn) {}
  43     Coin(const CTxOut& outIn, int nHeightIn, bool fCoinBaseIn) : out(outIn), fCoinBase(fCoinBaseIn),nHeight(nHeightIn) {}
  44
  45     void Clear() {
  46         out.SetNull();
  47         fCoinBase = false;
  48         nHeight = 0;
  49     }
  50
  51     //! empty constructor
  52     Coin() : fCoinBase(false), nHeight(0) { }
  53
  54     bool IsCoinBase() const {
  55         return fCoinBase;
  56     }
  57
  58     template<typename Stream>
  59     void Serialize(Stream &s) const {
  60         assert(!IsSpent());
  61         uint32_t code = nHeight * 2 + fCoinBase;
  62         ::Serialize(s, VARINT(code));
  63         ::Serialize(s, CTxOutCompressor(REF(out)));
  64     }
  65
  66     template<typename Stream>
  67     void Unserialize(Stream &s) {
  68         uint32_t code = 0;
  69         ::Unserialize(s, VARINT(code));
  70         nHeight = code >> 1;
  71         fCoinBase = code & 1;
  72         ::Unserialize(s, REF(CTxOutCompressor(out)));
  73     }
  74
  75     bool IsSpent() const {
  76         return out.IsNull();
  77     }
  78
  79     size_t DynamicMemoryUsage() const {
  80         return memusage::DynamicUsage(out.scriptPubKey);
  81     }
  82 };
  83
  84 class SaltedOutpointHasher
  85 {
  86 private:
  87     /** Salt */
  88     const uint64_t k0, k1;
  89
  90 public:
  91     SaltedOutpointHasher();
  92
  93     /**
  94      * This *must* return size_t. With Boost 1.46 on 32-bit systems the
  95      * unordered_map will behave unpredictably if the custom hasher returns a
  96      * uint64_t, resulting in failures when syncing the chain (#4634).
  97      */
  98     size_t operator()(const COutPoint& id) const {
  99         return SipHashUint256Extra(k0, k1, id.hash, id.n);
 100     }
 101 };
 102
 103 struct CCoinsCacheEntry
 104 {
 105     Coin coin; // The actual cached data.
 106     unsigned char flags;
 107
 108     enum Flags {
 109         DIRTY = (1 << 0), // This cache entry is potentially different from the version in the parent view.
 110         FRESH = (1 << 1), // The parent view does not have this entry (or it is pruned).
 111         /* Note that FRESH is a performance optimization with which we can
 112          * erase coins that are fully spent if we know we do not need to
 113          * flush the changes to the parent cache.  It is always safe to
 114          * not mark FRESH if that condition is not guaranteed.
 115          */
 116     };
 117
 118     CCoinsCacheEntry() : flags(0) {}
 119     explicit CCoinsCacheEntry(Coin&& coin_) : coin(std::move(coin_)), flags(0) {}
 120 };
 121
 122 typedef std::unordered_map<COutPoint, CCoinsCacheEntry, SaltedOutpointHasher> CCoinsMap;
 123
 124 /** Cursor for iterating over CoinsView state */
 125 class CCoinsViewCursor
 126 {
 127 public:
 128     CCoinsViewCursor(const uint256 &hashBlockIn): hashBlock(hashBlockIn) {}
 129     virtual ~CCoinsViewCursor() {}
 130
 131     virtual bool GetKey(COutPoint &key) const = 0;
 132     virtual bool GetValue(Coin &coin) const = 0;
 133     virtual unsigned int GetValueSize() const = 0;
 134
 135     virtual bool Valid() const = 0;
 136     virtual void Next() = 0;
 137
 138     //! Get best block at the time this cursor was created
 139     const uint256 &GetBestBlock() const { return hashBlock; }
 140 private:
 141     uint256 hashBlock;
 142 };
 143
 144 /** Abstract view on the open txout dataset. */
 145 class CCoinsView
 146 {
 147 public:
 148     /** Retrieve the Coin (unspent transaction output) for a given outpoint.
 149      *  Returns true only when an unspent coin was found, which is returned in coin.
 150      *  When false is returned, coin's value is unspecified.
 151      */
 152     virtual bool GetCoin(const COutPoint &outpoint, Coin &coin) const;
 153
 154     //! Just check whether a given outpoint is unspent.
 155     virtual bool HaveCoin(const COutPoint &outpoint) const;
 156
 157     //! Retrieve the block hash whose state this CCoinsView currently represents
 158     virtual uint256 GetBestBlock() const;
 159
 160     //! Retrieve the range of blocks that may have been only partially written.
 161     //! If the database is in a consistent state, the result is the empty vector.
 162     //! Otherwise, a two-element vector is returned consisting of the new and
 163     //! the old block hash, in that order.
 164     virtual std::vector<uint256> GetHeadBlocks() const;
 165
 166     //! Do a bulk modification (multiple Coin changes + BestBlock change).
 167     //! The passed mapCoins can be modified.
 168     virtual bool BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock);
 169
 170     //! Get a cursor to iterate over the whole state
 171     virtual CCoinsViewCursor *Cursor() const;
 172
 173     //! As we use CCoinsViews polymorphically, have a virtual destructor
 174     virtual ~CCoinsView() {}
 175
 176     //! Estimate database size (0 if not implemented)
 177     virtual size_t EstimateSize() const { return 0; }
 178 };
 179
 180
 181 /** CCoinsView backed by another CCoinsView */
 182 class CCoinsViewBacked : public CCoinsView
 183 {
 184 protected:
 185     CCoinsView *base;
 186
 187 public:
 188     CCoinsViewBacked(CCoinsView *viewIn);
 189     bool GetCoin(const COutPoint &outpoint, Coin &coin) const override;
 190     bool HaveCoin(const COutPoint &outpoint) const override;
 191     uint256 GetBestBlock() const override;
 192     std::vector<uint256> GetHeadBlocks() const override;
 193     void SetBackend(CCoinsView &viewIn);
 194     bool BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock) override;
 195     CCoinsViewCursor *Cursor() const override;
 196     size_t EstimateSize() const override;
 197 };
 198
 199
 200 /** CCoinsView that adds a memory cache for transactions to another CCoinsView */
 201 class CCoinsViewCache : public CCoinsViewBacked
 202 {
 203 protected:
 204     /**
 205      * Make mutable so that we can "fill the cache" even from Get-methods
 206      * declared as "const".
 207      */
 208     mutable uint256 hashBlock;
 209     mutable CCoinsMap cacheCoins;
 210
 211     /* Cached dynamic memory usage for the inner Coin objects. */
 212     mutable size_t cachedCoinsUsage;
 213
 214 public:
 215     CCoinsViewCache(CCoinsView *baseIn);
 216
 217     // Standard CCoinsView methods
 218     bool GetCoin(const COutPoint &outpoint, Coin &coin) const override;
 219     bool HaveCoin(const COutPoint &outpoint) const override;
 220     uint256 GetBestBlock() const override;
 221     void SetBestBlock(const uint256 &hashBlock);
 222     bool BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock) override;
 223     CCoinsViewCursor* Cursor() const override {
 224         throw std::logic_error("CCoinsViewCache cursor iteration not supported.");
 225     }
 226
 227     /**
 228      * Check if we have the given utxo already loaded in this cache.
 229      * The semantics are the same as HaveCoin(), but no calls to
 230      * the backing CCoinsView are made.
 231      */
 232     bool HaveCoinInCache(const COutPoint &outpoint) const;
 233
 234     /**
 235      * Return a reference to Coin in the cache, or a pruned one if not found. This is
 236      * more efficient than GetCoin.
 237      *
 238      * Generally, do not hold the reference returned for more than a short scope.
 239      * While the current implementation allows for modifications to the contents
 240      * of the cache while holding the reference, this behavior should not be relied
 241      * on! To be safe, best to not hold the returned reference through any other
 242      * calls to this cache.
 243      */
 244     const Coin& AccessCoin(const COutPoint &output) const;
 245
 246     /**
 247      * Add a coin. Set potential_overwrite to true if a non-pruned version may
 248      * already exist.
 249      */
 250     void AddCoin(const COutPoint& outpoint, Coin&& coin, bool potential_overwrite);
 251
 252     /**
 253      * Spend a coin. Pass moveto in order to get the deleted data.
 254      * If no unspent output exists for the passed outpoint, this call
 255      * has no effect.
 256      */
 257     bool SpendCoin(const COutPoint &outpoint, Coin* moveto = nullptr);
 258
 259     /**
 260      * Push the modifications applied to this cache to its base.
 261      * Failure to call this method before destruction will cause the changes to be forgotten.
 262      * If false is returned, the state of this cache (and its backing view) will be undefined.
 263      */
 264     bool Flush();
 265
 266     /**
 267      * Removes the UTXO with the given outpoint from the cache, if it is
 268      * not modified.
 269      */
 270     void Uncache(const COutPoint &outpoint);
 271
 272     //! Calculate the size of the cache (in number of transaction outputs)
 273     unsigned int GetCacheSize() const;
 274
 275     //! Calculate the size of the cache (in bytes)
 276     size_t DynamicMemoryUsage() const;
 277
 278     /**
 279      * Amount of bitcoins coming in to a transaction
 280      * Note that lightweight clients may not know anything besides the hash of previous transactions,
 281      * so may not be able to calculate this.
 282      *
 283      * @param[in] tx    transaction for which we are checking input total
 284      * @return  Sum of value of all inputs (scriptSigs)
 285      */
 286     CAmount GetValueIn(const CTransaction& tx) const;
 287
 288     //! Check whether all prevouts of the transaction are present in the UTXO set represented by this view
 289     bool HaveInputs(const CTransaction& tx) const;
 290
 291 private:
 292     CCoinsMap::iterator FetchCoin(const COutPoint &outpoint) const;
 293
 294     /**
 295      * By making the copy constructor private, we prevent accidentally using it when one intends to create a cache on top of a base cache.
 296      */
 297     CCoinsViewCache(const CCoinsViewCache &);
 298 };
 299
 300 //! Utility function to add all of a transaction's outputs to a cache.
 301 // When check is false, this assumes that overwrites are only possible for coinbase transactions.
 302 // When check is true, the underlying view may be queried to determine whether an addition is
 303 // an overwrite.
 304 // TODO: pass in a boolean to limit these possible overwrites to known
 305 // (pre-BIP34) cases.
 306 void AddCoins(CCoinsViewCache& cache, const CTransaction& tx, int nHeight, bool check = false);
 307
 308 //! Utility function to find any unspent output with a given txid.
 309 // This function can be quite expensive because in the event of a transaction
 310 // which is not found in the cache, it can cause up to MAX_OUTPUTS_PER_BLOCK
 311 // lookups to database, so it should be used with care.
 312 const Coin& AccessByTxid(const CCoinsViewCache& cache, const uint256& txid);
 313
 314 #endif // BITCOIN_COINS_H