1 // Copyright (c) 2009-2010 Satoshi Nakamoto 2 // Copyright (c) 2009-2020 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 <compressor.h> 10 #include <core_memusage.h> 11 #include <memusage.h> 12 #include <primitives/transaction.h> 13 #include <serialize.h> 14 #include <uint256.h> 15 #include <util/hasher.h> 16 17 #include <assert.h> 18 #include <stdint.h> 19 20 #include <functional> 21 #include <unordered_map> 22 23 /** 24 * A UTXO entry. 25 * 26 * Serialized format: 27 * - VARINT((coinbase ? 1 : 0) | (height << 1)) 28 * - the non-spent CTxOut (via TxOutCompression) 29 */ 30 class Coin 31 { 32 public: 33 //! unspent transaction output 34 CTxOut out; 35 36 //! whether containing transaction was a coinbase 37 unsigned int fCoinBase : 1; 38 39 //! at which height this containing transaction was included in the active block chain 40 uint32_t nHeight : 31; 41 42 //! construct a Coin from a CTxOut and height/coinbase information. Coin(CTxOut && outIn,int nHeightIn,bool fCoinBaseIn)43 Coin(CTxOut&& outIn, int nHeightIn, bool fCoinBaseIn) : out(std::move(outIn)), fCoinBase(fCoinBaseIn), nHeight(nHeightIn) {} Coin(const CTxOut & outIn,int nHeightIn,bool fCoinBaseIn)44 Coin(const CTxOut& outIn, int nHeightIn, bool fCoinBaseIn) : out(outIn), fCoinBase(fCoinBaseIn),nHeight(nHeightIn) {} 45 Clear()46 void Clear() { 47 out.SetNull(); 48 fCoinBase = false; 49 nHeight = 0; 50 } 51 52 //! empty constructor Coin()53 Coin() : fCoinBase(false), nHeight(0) { } 54 IsCoinBase()55 bool IsCoinBase() const { 56 return fCoinBase; 57 } 58 59 template<typename Stream> Serialize(Stream & s)60 void Serialize(Stream &s) const { 61 assert(!IsSpent()); 62 uint32_t code = nHeight * uint32_t{2} + fCoinBase; 63 ::Serialize(s, VARINT(code)); 64 ::Serialize(s, Using<TxOutCompression>(out)); 65 } 66 67 template<typename Stream> Unserialize(Stream & s)68 void Unserialize(Stream &s) { 69 uint32_t code = 0; 70 ::Unserialize(s, VARINT(code)); 71 nHeight = code >> 1; 72 fCoinBase = code & 1; 73 ::Unserialize(s, Using<TxOutCompression>(out)); 74 } 75 76 /** Either this coin never existed (see e.g. coinEmpty in coins.cpp), or it 77 * did exist and has been spent. 78 */ IsSpent()79 bool IsSpent() const { 80 return out.IsNull(); 81 } 82 DynamicMemoryUsage()83 size_t DynamicMemoryUsage() const { 84 return memusage::DynamicUsage(out.scriptPubKey); 85 } 86 }; 87 88 /** 89 * A Coin in one level of the coins database caching hierarchy. 90 * 91 * A coin can either be: 92 * - unspent or spent (in which case the Coin object will be nulled out - see Coin.Clear()) 93 * - DIRTY or not DIRTY 94 * - FRESH or not FRESH 95 * 96 * Out of these 2^3 = 8 states, only some combinations are valid: 97 * - unspent, FRESH, DIRTY (e.g. a new coin created in the cache) 98 * - unspent, not FRESH, DIRTY (e.g. a coin changed in the cache during a reorg) 99 * - unspent, not FRESH, not DIRTY (e.g. an unspent coin fetched from the parent cache) 100 * - spent, FRESH, not DIRTY (e.g. a spent coin fetched from the parent cache) 101 * - spent, not FRESH, DIRTY (e.g. a coin is spent and spentness needs to be flushed to the parent) 102 */ 103 struct CCoinsCacheEntry 104 { 105 Coin coin; // The actual cached data. 106 unsigned char flags; 107 108 enum Flags { 109 /** 110 * DIRTY means the CCoinsCacheEntry is potentially different from the 111 * version in the parent cache. Failure to mark a coin as DIRTY when 112 * it is potentially different from the parent cache will cause a 113 * consensus failure, since the coin's state won't get written to the 114 * parent when the cache is flushed. 115 */ 116 DIRTY = (1 << 0), 117 /** 118 * FRESH means the parent cache does not have this coin or that it is a 119 * spent coin in the parent cache. If a FRESH coin in the cache is 120 * later spent, it can be deleted entirely and doesn't ever need to be 121 * flushed to the parent. This is a performance optimization. Marking a 122 * coin as FRESH when it exists unspent in the parent cache will cause a 123 * consensus failure, since it might not be deleted from the parent 124 * when this cache is flushed. 125 */ 126 FRESH = (1 << 1), 127 }; 128 CCoinsCacheEntryCCoinsCacheEntry129 CCoinsCacheEntry() : flags(0) {} CCoinsCacheEntryCCoinsCacheEntry130 explicit CCoinsCacheEntry(Coin&& coin_) : coin(std::move(coin_)), flags(0) {} CCoinsCacheEntryCCoinsCacheEntry131 CCoinsCacheEntry(Coin&& coin_, unsigned char flag) : coin(std::move(coin_)), flags(flag) {} 132 }; 133 134 typedef std::unordered_map<COutPoint, CCoinsCacheEntry, SaltedOutpointHasher> CCoinsMap; 135 136 /** Cursor for iterating over CoinsView state */ 137 class CCoinsViewCursor 138 { 139 public: CCoinsViewCursor(const uint256 & hashBlockIn)140 CCoinsViewCursor(const uint256 &hashBlockIn): hashBlock(hashBlockIn) {} ~CCoinsViewCursor()141 virtual ~CCoinsViewCursor() {} 142 143 virtual bool GetKey(COutPoint &key) const = 0; 144 virtual bool GetValue(Coin &coin) const = 0; 145 virtual unsigned int GetValueSize() const = 0; 146 147 virtual bool Valid() const = 0; 148 virtual void Next() = 0; 149 150 //! Get best block at the time this cursor was created GetBestBlock()151 const uint256 &GetBestBlock() const { return hashBlock; } 152 private: 153 uint256 hashBlock; 154 }; 155 156 /** Abstract view on the open txout dataset. */ 157 class CCoinsView 158 { 159 public: 160 /** Retrieve the Coin (unspent transaction output) for a given outpoint. 161 * Returns true only when an unspent coin was found, which is returned in coin. 162 * When false is returned, coin's value is unspecified. 163 */ 164 virtual bool GetCoin(const COutPoint &outpoint, Coin &coin) const; 165 166 //! Just check whether a given outpoint is unspent. 167 virtual bool HaveCoin(const COutPoint &outpoint) const; 168 169 //! Retrieve the block hash whose state this CCoinsView currently represents 170 virtual uint256 GetBestBlock() const; 171 172 //! Retrieve the range of blocks that may have been only partially written. 173 //! If the database is in a consistent state, the result is the empty vector. 174 //! Otherwise, a two-element vector is returned consisting of the new and 175 //! the old block hash, in that order. 176 virtual std::vector<uint256> GetHeadBlocks() const; 177 178 //! Do a bulk modification (multiple Coin changes + BestBlock change). 179 //! The passed mapCoins can be modified. 180 virtual bool BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock); 181 182 //! Get a cursor to iterate over the whole state 183 virtual std::unique_ptr<CCoinsViewCursor> Cursor() const; 184 185 //! As we use CCoinsViews polymorphically, have a virtual destructor ~CCoinsView()186 virtual ~CCoinsView() {} 187 188 //! Estimate database size (0 if not implemented) EstimateSize()189 virtual size_t EstimateSize() const { return 0; } 190 }; 191 192 193 /** CCoinsView backed by another CCoinsView */ 194 class CCoinsViewBacked : public CCoinsView 195 { 196 protected: 197 CCoinsView *base; 198 199 public: 200 CCoinsViewBacked(CCoinsView *viewIn); 201 bool GetCoin(const COutPoint &outpoint, Coin &coin) const override; 202 bool HaveCoin(const COutPoint &outpoint) const override; 203 uint256 GetBestBlock() const override; 204 std::vector<uint256> GetHeadBlocks() const override; 205 void SetBackend(CCoinsView &viewIn); 206 bool BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock) override; 207 std::unique_ptr<CCoinsViewCursor> Cursor() const override; 208 size_t EstimateSize() const override; 209 }; 210 211 212 /** CCoinsView that adds a memory cache for transactions to another CCoinsView */ 213 class CCoinsViewCache : public CCoinsViewBacked 214 { 215 protected: 216 /** 217 * Make mutable so that we can "fill the cache" even from Get-methods 218 * declared as "const". 219 */ 220 mutable uint256 hashBlock; 221 mutable CCoinsMap cacheCoins; 222 223 /* Cached dynamic memory usage for the inner Coin objects. */ 224 mutable size_t cachedCoinsUsage; 225 226 public: 227 CCoinsViewCache(CCoinsView *baseIn); 228 229 /** 230 * By deleting the copy constructor, we prevent accidentally using it when one intends to create a cache on top of a base cache. 231 */ 232 CCoinsViewCache(const CCoinsViewCache &) = delete; 233 234 // Standard CCoinsView methods 235 bool GetCoin(const COutPoint &outpoint, Coin &coin) const override; 236 bool HaveCoin(const COutPoint &outpoint) const override; 237 uint256 GetBestBlock() const override; 238 void SetBestBlock(const uint256 &hashBlock); 239 bool BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock) override; Cursor()240 std::unique_ptr<CCoinsViewCursor> Cursor() const override { 241 throw std::logic_error("CCoinsViewCache cursor iteration not supported."); 242 } 243 244 /** 245 * Check if we have the given utxo already loaded in this cache. 246 * The semantics are the same as HaveCoin(), but no calls to 247 * the backing CCoinsView are made. 248 */ 249 bool HaveCoinInCache(const COutPoint &outpoint) const; 250 251 /** 252 * Return a reference to Coin in the cache, or coinEmpty if not found. This is 253 * more efficient than GetCoin. 254 * 255 * Generally, do not hold the reference returned for more than a short scope. 256 * While the current implementation allows for modifications to the contents 257 * of the cache while holding the reference, this behavior should not be relied 258 * on! To be safe, best to not hold the returned reference through any other 259 * calls to this cache. 260 */ 261 const Coin& AccessCoin(const COutPoint &output) const; 262 263 /** 264 * Add a coin. Set possible_overwrite to true if an unspent version may 265 * already exist in the cache. 266 */ 267 void AddCoin(const COutPoint& outpoint, Coin&& coin, bool possible_overwrite); 268 269 /** 270 * Emplace a coin into cacheCoins without performing any checks, marking 271 * the emplaced coin as dirty. 272 * 273 * NOT FOR GENERAL USE. Used only when loading coins from a UTXO snapshot. 274 * @sa ChainstateManager::PopulateAndValidateSnapshot() 275 */ 276 void EmplaceCoinInternalDANGER(COutPoint&& outpoint, Coin&& coin); 277 278 /** 279 * Spend a coin. Pass moveto in order to get the deleted data. 280 * If no unspent output exists for the passed outpoint, this call 281 * has no effect. 282 */ 283 bool SpendCoin(const COutPoint &outpoint, Coin* moveto = nullptr); 284 285 /** 286 * Push the modifications applied to this cache to its base. 287 * Failure to call this method before destruction will cause the changes to be forgotten. 288 * If false is returned, the state of this cache (and its backing view) will be undefined. 289 */ 290 bool Flush(); 291 292 /** 293 * Removes the UTXO with the given outpoint from the cache, if it is 294 * not modified. 295 */ 296 void Uncache(const COutPoint &outpoint); 297 298 //! Calculate the size of the cache (in number of transaction outputs) 299 unsigned int GetCacheSize() const; 300 301 //! Calculate the size of the cache (in bytes) 302 size_t DynamicMemoryUsage() const; 303 304 //! Check whether all prevouts of the transaction are present in the UTXO set represented by this view 305 bool HaveInputs(const CTransaction& tx) const; 306 307 //! Force a reallocation of the cache map. This is required when downsizing 308 //! the cache because the map's allocator may be hanging onto a lot of 309 //! memory despite having called .clear(). 310 //! 311 //! See: https://stackoverflow.com/questions/42114044/how-to-release-unordered-map-memory 312 void ReallocateCache(); 313 314 private: 315 /** 316 * @note this is marked const, but may actually append to `cacheCoins`, increasing 317 * memory usage. 318 */ 319 CCoinsMap::iterator FetchCoin(const COutPoint &outpoint) const; 320 }; 321 322 //! Utility function to add all of a transaction's outputs to a cache. 323 //! When check is false, this assumes that overwrites are only possible for coinbase transactions. 324 //! When check is true, the underlying view may be queried to determine whether an addition is 325 //! an overwrite. 326 // TODO: pass in a boolean to limit these possible overwrites to known 327 // (pre-BIP34) cases. 328 void AddCoins(CCoinsViewCache& cache, const CTransaction& tx, int nHeight, bool check = false); 329 330 //! Utility function to find any unspent output with a given txid. 331 //! This function can be quite expensive because in the event of a transaction 332 //! which is not found in the cache, it can cause up to MAX_OUTPUTS_PER_BLOCK 333 //! lookups to database, so it should be used with care. 334 const Coin& AccessByTxid(const CCoinsViewCache& cache, const uint256& txid); 335 336 /** 337 * This is a minimally invasive approach to shutdown on LevelDB read errors from the 338 * chainstate, while keeping user interface out of the common library, which is shared 339 * between bitcoind, and bitcoin-qt and non-server tools. 340 * 341 * Writes do not need similar protection, as failure to write is handled by the caller. 342 */ 343 class CCoinsViewErrorCatcher final : public CCoinsViewBacked 344 { 345 public: CCoinsViewErrorCatcher(CCoinsView * view)346 explicit CCoinsViewErrorCatcher(CCoinsView* view) : CCoinsViewBacked(view) {} 347 AddReadErrCallback(std::function<void ()> f)348 void AddReadErrCallback(std::function<void()> f) { 349 m_err_callbacks.emplace_back(std::move(f)); 350 } 351 352 bool GetCoin(const COutPoint &outpoint, Coin &coin) const override; 353 354 private: 355 /** A list of callbacks to execute upon leveldb read error. */ 356 std::vector<std::function<void()>> m_err_callbacks; 357 358 }; 359 360 #endif // BITCOIN_COINS_H 361