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