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