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 <primitives/transaction_identifier.h>
15 #include <serialize.h>
16 #include <support/allocators/pool.h>
17 #include <uint256.h>
18 #include <util/check.h>
19 #include <util/log.h>
20 #include <util/overflow.h>
21 #include <util/hasher.h>
22 23 #include <cassert>
24 #include <cstdint>
25 26 #include <atomic>
27 #include <functional>
28 #include <future>
29 #include <memory>
30 #include <optional>
31 #include <unordered_map>
32 #include <utility>
33 #include <vector>
34 35 class CBlock;
36 class ThreadPool;
37 38 /**
39 * A UTXO entry.
40 *
41 * Serialized format:
42 * - VARINT((height << 1) | (coinbase ? 1 : 0))
43 * - the non-spent CTxOut (via TxOutCompression)
44 */
45 class Coin
46 {
47 public:
48 //! unspent transaction output
49 CTxOut out;
50 51 //! whether containing transaction was a coinbase
52 bool fCoinBase : 1;
53 54 //! at which height this containing transaction was included in the active block chain
55 uint32_t nHeight : 31;
56 57 //! construct a Coin from a CTxOut and height/coinbase information.
58 Coin(CTxOut&& outIn, int nHeightIn, bool fCoinBaseIn) : out(std::move(outIn)), fCoinBase(fCoinBaseIn), nHeight(nHeightIn) {}
59 Coin(const CTxOut& outIn, int nHeightIn, bool fCoinBaseIn) : out(outIn), fCoinBase(fCoinBaseIn),nHeight(nHeightIn) {}
60 61 void Clear() {
62 out.SetNull();
63 fCoinBase = false;
64 nHeight = 0;
65 }
66 67 //! empty constructor
68 Coin() : fCoinBase(false), nHeight(0) { }
69 70 bool IsCoinBase() const {
71 return fCoinBase;
72 }
73 74 template<typename Stream>
75 void Serialize(Stream &s) const {
76 assert(!IsSpent());
77 uint32_t code{(uint32_t{nHeight} << 1) | uint32_t{fCoinBase}};
78 ::Serialize(s, VARINT(code));
79 ::Serialize(s, Using<TxOutCompression>(out));
80 }
81 82 template<typename Stream>
83 void Unserialize(Stream &s) {
84 uint32_t code = 0;
85 ::Unserialize(s, VARINT(code));
86 nHeight = code >> 1;
87 fCoinBase = code & 1;
88 ::Unserialize(s, Using<TxOutCompression>(out));
89 }
90 91 /** Either this coin never existed (see e.g. coinEmpty in coins.cpp), or it
92 * did exist and has been spent.
93 */
94 bool IsSpent() const {
95 return out.IsNull();
96 }
97 98 size_t DynamicMemoryUsage() const {
99 return memusage::DynamicUsage(out.scriptPubKey);
100 }
101 };
102 103 struct CCoinsCacheEntry;
104 using CoinsCachePair = std::pair<const COutPoint, CCoinsCacheEntry>;
105 106 /**
107 * A Coin in one level of the coins database caching hierarchy.
108 *
109 * A coin can either be:
110 * - unspent or spent (in which case the Coin object will be nulled out - see Coin.Clear())
111 * - DIRTY or not DIRTY
112 * - FRESH or not FRESH
113 *
114 * Out of these 2^3 = 8 states, only some combinations are valid:
115 * - unspent, FRESH, DIRTY (e.g. a new coin created in the cache)
116 * - unspent, not FRESH, DIRTY (e.g. a coin changed in the cache during a reorg)
117 * - unspent, not FRESH, not DIRTY (e.g. an unspent coin fetched from the parent cache)
118 * - spent, not FRESH, DIRTY (e.g. a coin is spent and spentness needs to be flushed to the parent)
119 */
120 struct CCoinsCacheEntry
121 {
122 private:
123 /**
124 * These are used to create a doubly linked list of flagged entries.
125 * They are set in SetDirty, SetFresh, and unset in SetClean.
126 * A flagged entry is any entry that is either DIRTY, FRESH, or both.
127 *
128 * DIRTY entries are tracked so that only modified entries can be passed to
129 * the parent cache for batch writing. This is a performance optimization
130 * compared to giving all entries in the cache to the parent and having the
131 * parent scan for only modified entries.
132 */
133 CoinsCachePair* m_prev{nullptr};
134 CoinsCachePair* m_next{nullptr};
135 uint8_t m_flags{0};
136 137 //! Adding a flag requires a reference to the sentinel of the flagged pair linked list.
138 static void AddFlags(uint8_t flags, CoinsCachePair& pair, CoinsCachePair& sentinel) noexcept
139 {
140 Assume(flags & (DIRTY | FRESH));
141 if (!pair.second.m_flags) {
142 Assume(!pair.second.m_prev && !pair.second.m_next);
143 pair.second.m_prev = sentinel.second.m_prev;
144 pair.second.m_next = &sentinel;
145 sentinel.second.m_prev = &pair;
146 pair.second.m_prev->second.m_next = &pair;
147 }
148 Assume(pair.second.m_prev && pair.second.m_next);
149 pair.second.m_flags |= flags;
150 }
151 152 public:
153 Coin coin; // The actual cached data.
154 155 enum Flags {
156 /**
157 * DIRTY means the CCoinsCacheEntry is potentially different from the
158 * version in the parent cache. Failure to mark a coin as DIRTY when
159 * it is potentially different from the parent cache will cause a
160 * consensus failure, since the coin's state won't get written to the
161 * parent when the cache is flushed.
162 */
163 DIRTY = (1 << 0),
164 /**
165 * FRESH means the parent cache does not have this coin or that it is a
166 * spent coin in the parent cache. If a FRESH coin in the cache is
167 * later spent, it can be deleted entirely and doesn't ever need to be
168 * flushed to the parent. This is a performance optimization. Marking a
169 * coin as FRESH when it exists unspent in the parent cache will cause a
170 * consensus failure, since it might not be deleted from the parent
171 * when this cache is flushed.
172 */
173 FRESH = (1 << 1),
174 };
175 176 CCoinsCacheEntry() noexcept = default;
177 explicit CCoinsCacheEntry(Coin&& coin_) noexcept : coin(std::move(coin_)) {}
178 ~CCoinsCacheEntry()
179 {
180 SetClean();
181 }
182 183 static void SetDirty(CoinsCachePair& pair, CoinsCachePair& sentinel) noexcept { AddFlags(DIRTY, pair, sentinel); }
184 static void SetFresh(CoinsCachePair& pair, CoinsCachePair& sentinel) noexcept { AddFlags(FRESH, pair, sentinel); }
185 186 void SetClean() noexcept
187 {
188 if (!m_flags) return;
189 m_next->second.m_prev = m_prev;
190 m_prev->second.m_next = m_next;
191 m_flags = 0;
192 m_prev = m_next = nullptr;
193 }
194 bool IsDirty() const noexcept { return m_flags & DIRTY; }
195 bool IsFresh() const noexcept { return m_flags & FRESH; }
196 197 //! Only call Next when this entry is DIRTY, FRESH, or both
198 CoinsCachePair* Next() const noexcept
199 {
200 Assume(m_flags);
201 return m_next;
202 }
203 204 //! Only call Prev when this entry is DIRTY, FRESH, or both
205 CoinsCachePair* Prev() const noexcept
206 {
207 Assume(m_flags);
208 return m_prev;
209 }
210 211 //! Only use this for initializing the linked list sentinel
212 void SelfRef(CoinsCachePair& pair) noexcept
213 {
214 Assume(&pair.second == this);
215 m_prev = &pair;
216 m_next = &pair;
217 // Set sentinel to DIRTY so we can call Next on it
218 m_flags = DIRTY;
219 }
220 };
221 222 /**
223 * PoolAllocator's MAX_BLOCK_SIZE_BYTES parameter here uses sizeof the data, and adds the size
224 * of 4 pointers. We do not know the exact node size used in the std::unordered_node implementation
225 * because it is implementation defined. Most implementations have an overhead of 1 or 2 pointers,
226 * so nodes can be connected in a linked list, and in some cases the hash value is stored as well.
227 * Using an additional sizeof(void*)*4 for MAX_BLOCK_SIZE_BYTES should thus be sufficient so that
228 * all implementations can allocate the nodes from the PoolAllocator.
229 */
230 using CCoinsMap = std::unordered_map<COutPoint,
231 CCoinsCacheEntry,
232 SaltedOutpointHasher,
233 std::equal_to<COutPoint>,
234 PoolAllocator<CoinsCachePair,
235 sizeof(CoinsCachePair) + sizeof(void*) * 4>>;
236 237 using CCoinsMapMemoryResource = CCoinsMap::allocator_type::ResourceType;
238 239 /** Cursor for iterating over CoinsView state */
240 class CCoinsViewCursor
241 {
242 public:
243 CCoinsViewCursor(const uint256& in_block_hash) : block_hash(in_block_hash) {}
244 virtual ~CCoinsViewCursor() = default;
245 246 virtual bool GetKey(COutPoint &key) const = 0;
247 virtual bool GetValue(Coin &coin) const = 0;
248 249 virtual bool Valid() const = 0;
250 virtual void Next() = 0;
251 252 //! Get best block at the time this cursor was created
253 const uint256& GetBestBlock() const { return block_hash; }
254 private:
255 uint256 block_hash;
256 };
257 258 /**
259 * Cursor for iterating over the linked list of flagged entries in CCoinsViewCache.
260 *
261 * This is a helper struct to encapsulate the diverging logic between a non-erasing
262 * CCoinsViewCache::Sync and an erasing CCoinsViewCache::Flush. This allows the receiver
263 * of CCoinsView::BatchWrite to iterate through the flagged entries without knowing
264 * the caller's intent.
265 *
266 * However, the receiver can still call CoinsViewCacheCursor::WillErase to see if the
267 * caller will erase the entry after BatchWrite returns. If so, the receiver can
268 * perform optimizations such as moving the coin out of the CCoinsCachEntry instead
269 * of copying it.
270 */
271 struct CoinsViewCacheCursor
272 {
273 //! If will_erase is not set, iterating through the cursor will erase spent coins from the map,
274 //! and other coins will be unflagged (removing them from the linked list).
275 //! If will_erase is set, the underlying map and linked list will not be modified,
276 //! as the caller is expected to wipe the entire map anyway.
277 //! This is an optimization compared to erasing all entries as the cursor iterates them when will_erase is set.
278 //! Calling CCoinsMap::clear() afterwards is faster because a CoinsCachePair cannot be coerced back into a
279 //! CCoinsMap::iterator to be erased, and must therefore be looked up again by key in the CCoinsMap before being erased.
280 CoinsViewCacheCursor(size_t& dirty_count LIFETIMEBOUND,
281 CoinsCachePair& sentinel LIFETIMEBOUND,
282 CCoinsMap& map LIFETIMEBOUND,
283 bool will_erase) noexcept
284 : m_dirty_count(dirty_count), m_sentinel(sentinel), m_map(map), m_will_erase(will_erase) {}
285 286 inline CoinsCachePair* Begin() const noexcept { return m_sentinel.second.Next(); }
287 inline CoinsCachePair* End() const noexcept { return &m_sentinel; }
288 289 //! Return the next entry after current, possibly erasing current
290 inline CoinsCachePair* NextAndMaybeErase(CoinsCachePair& current) noexcept
291 {
292 const auto next_entry{current.second.Next()};
293 Assume(TrySub(m_dirty_count, current.second.IsDirty()));
294 // If we are not going to erase the cache, we must still erase spent entries.
295 // Otherwise, clear the state of the entry.
296 if (!m_will_erase) {
297 if (current.second.coin.IsSpent()) {
298 assert(current.second.coin.DynamicMemoryUsage() == 0); // scriptPubKey was already cleared in SpendCoin
299 m_map.erase(current.first);
300 } else {
301 current.second.SetClean();
302 }
303 }
304 return next_entry;
305 }
306 307 inline bool WillErase(CoinsCachePair& current) const noexcept { return m_will_erase || current.second.coin.IsSpent(); }
308 size_t GetDirtyCount() const noexcept { return m_dirty_count; }
309 size_t GetTotalCount() const noexcept { return m_map.size(); }
310 private:
311 size_t& m_dirty_count;
312 CoinsCachePair& m_sentinel;
313 CCoinsMap& m_map;
314 bool m_will_erase;
315 };
316 317 /** Pure abstract view on the open txout dataset. */
318 class CCoinsView
319 {
320 public:
321 //! As we use CCoinsViews polymorphically, have a virtual destructor
322 virtual ~CCoinsView() = default;
323 324 //! Retrieve the Coin (unspent transaction output) for a given outpoint.
325 //! May populate the cache. Use PeekCoin() to perform a non-caching lookup.
326 virtual std::optional<Coin> GetCoin(const COutPoint& outpoint) const = 0;
327 328 //! Retrieve the Coin (unspent transaction output) for a given outpoint, without caching results.
329 //! Does not populate the cache. Use GetCoin() to cache the result.
330 virtual std::optional<Coin> PeekCoin(const COutPoint& outpoint) const = 0;
331 332 //! Just check whether a given outpoint is unspent.
333 //! May populate the cache. Use PeekCoin() to perform a non-caching lookup.
334 virtual bool HaveCoin(const COutPoint& outpoint) const = 0;
335 336 //! Retrieve the block hash whose state this CCoinsView currently represents
337 virtual uint256 GetBestBlock() const = 0;
338 339 //! Retrieve the range of blocks that may have been only partially written.
340 //! If the database is in a consistent state, the result is the empty vector.
341 //! Otherwise, a two-element vector is returned consisting of the new and
342 //! the old block hash, in that order.
343 virtual std::vector<uint256> GetHeadBlocks() const = 0;
344 345 //! Do a bulk modification (multiple Coin changes + BestBlock change).
346 //! The passed cursor is used to iterate through the coins.
347 virtual void BatchWrite(CoinsViewCacheCursor& cursor, const uint256& block_hash) = 0;
348 349 //! Get a cursor to iterate over the whole state. Implementations may return nullptr.
350 virtual std::unique_ptr<CCoinsViewCursor> Cursor() const = 0;
351 352 //! Estimate database size
353 virtual size_t EstimateSize() const = 0;
354 };
355 356 /** Noop coins view. */
357 class CoinsViewEmpty : public CCoinsView
358 {
359 protected:
360 CoinsViewEmpty() = default;
361 362 public:
363 static CoinsViewEmpty& Get();
364 365 CoinsViewEmpty(const CoinsViewEmpty&) = delete;
366 CoinsViewEmpty& operator=(const CoinsViewEmpty&) = delete;
367 368 std::optional<Coin> GetCoin(const COutPoint&) const override { return {}; }
369 std::optional<Coin> PeekCoin(const COutPoint& outpoint) const override { return GetCoin(outpoint); }
370 bool HaveCoin(const COutPoint& outpoint) const override { return !!GetCoin(outpoint); }
371 uint256 GetBestBlock() const override { return {}; }
372 std::vector<uint256> GetHeadBlocks() const override { return {}; }
373 void BatchWrite(CoinsViewCacheCursor& cursor, const uint256&) override
374 {
375 for (auto it{cursor.Begin()}; it != cursor.End(); it = cursor.NextAndMaybeErase(*it)) { }
376 }
377 std::unique_ptr<CCoinsViewCursor> Cursor() const override { return {}; }
378 size_t EstimateSize() const override { return 0; }
379 };
380 381 /** CCoinsView backed by another CCoinsView */
382 class CCoinsViewBacked : public CCoinsView
383 {
384 protected:
385 CCoinsView* base;
386 387 public:
388 explicit CCoinsViewBacked(CCoinsView* in_view) : base{Assert(in_view)} {}
389 390 void SetBackend(CCoinsView& in_view) { base = &in_view; }
391 392 std::optional<Coin> GetCoin(const COutPoint& outpoint) const override { return base->GetCoin(outpoint); }
393 std::optional<Coin> PeekCoin(const COutPoint& outpoint) const override { return base->PeekCoin(outpoint); }
394 bool HaveCoin(const COutPoint& outpoint) const override { return base->HaveCoin(outpoint); }
395 uint256 GetBestBlock() const override { return base->GetBestBlock(); }
396 std::vector<uint256> GetHeadBlocks() const override { return base->GetHeadBlocks(); }
397 void BatchWrite(CoinsViewCacheCursor& cursor, const uint256& block_hash) override { base->BatchWrite(cursor, block_hash); }
398 std::unique_ptr<CCoinsViewCursor> Cursor() const override { return base->Cursor(); }
399 size_t EstimateSize() const override { return base->EstimateSize(); }
400 };
401 402 403 /** CCoinsView that adds a memory cache for transactions to another CCoinsView */
404 class CCoinsViewCache : public CCoinsViewBacked
405 {
406 private:
407 const bool m_deterministic;
408 409 protected:
410 /**
411 * Make mutable so that we can "fill the cache" even from Get-methods
412 * declared as "const".
413 */
414 mutable uint256 m_block_hash;
415 mutable CCoinsMapMemoryResource m_cache_coins_memory_resource{};
416 /* The starting sentinel of the flagged entry circular doubly linked list. */
417 mutable CoinsCachePair m_sentinel;
418 mutable CCoinsMap cacheCoins;
419 420 /* Cached dynamic memory usage for the inner Coin objects. */
421 mutable size_t cachedCoinsUsage{0};
422 /* Running count of dirty Coin cache entries. */
423 mutable size_t m_dirty_count{0};
424 425 /**
426 * Discard all modifications made to this cache without flushing to the base view.
427 * This can be used to efficiently reuse a cache instance across multiple operations.
428 */
429 virtual void Reset() noexcept;
430 431 /* Fetch the coin from base. Used for cache misses in FetchCoin. */
432 virtual std::optional<Coin> FetchCoinFromBase(const COutPoint& outpoint) const;
433 434 public:
435 CCoinsViewCache(CCoinsView* in_base, bool deterministic = false);
436 437 /**
438 * By deleting the copy constructor, we prevent accidentally using it when one intends to create a cache on top of a base cache.
439 */
440 CCoinsViewCache(const CCoinsViewCache &) = delete;
441 442 // Standard CCoinsView methods
443 std::optional<Coin> GetCoin(const COutPoint& outpoint) const override;
444 std::optional<Coin> PeekCoin(const COutPoint& outpoint) const override;
445 bool HaveCoin(const COutPoint& outpoint) const override;
446 uint256 GetBestBlock() const override;
447 void SetBestBlock(const uint256& block_hash);
448 void BatchWrite(CoinsViewCacheCursor& cursor, const uint256& block_hash) override;
449 std::unique_ptr<CCoinsViewCursor> Cursor() const override {
450 throw std::logic_error("CCoinsViewCache cursor iteration not supported.");
451 }
452 453 /**
454 * Check if we have the given utxo already loaded in this cache.
455 * The semantics are the same as HaveCoin(), but no calls to
456 * the backing CCoinsView are made.
457 */
458 bool HaveCoinInCache(const COutPoint &outpoint) const;
459 460 /**
461 * Return a reference to Coin in the cache, or coinEmpty if not found. This is
462 * more efficient than GetCoin.
463 *
464 * Generally, do not hold the reference returned for more than a short scope.
465 * While the current implementation allows for modifications to the contents
466 * of the cache while holding the reference, this behavior should not be relied
467 * on! To be safe, best to not hold the returned reference through any other
468 * calls to this cache.
469 */
470 const Coin& AccessCoin(const COutPoint &output) const;
471 472 /**
473 * Add a coin. Set possible_overwrite to true if an unspent version may
474 * already exist in the cache.
475 */
476 void AddCoin(const COutPoint& outpoint, Coin&& coin, bool possible_overwrite);
477 478 /**
479 * Emplace a coin into cacheCoins without performing any checks, marking
480 * the emplaced coin as dirty.
481 *
482 * NOT FOR GENERAL USE. Used only when loading coins from a UTXO snapshot.
483 * @sa ChainstateManager::PopulateAndValidateSnapshot()
484 */
485 void EmplaceCoinInternalDANGER(COutPoint&& outpoint, Coin&& coin);
486 487 /**
488 * Spend a coin. Pass moveto in order to get the deleted data.
489 * If no unspent output exists for the passed outpoint, this call
490 * has no effect.
491 */
492 bool SpendCoin(const COutPoint &outpoint, Coin* moveto = nullptr);
493 494 /**
495 * Push the modifications applied to this cache to its base and wipe local state.
496 * Failure to call this method or Sync() before destruction will cause the changes
497 * to be forgotten.
498 * If reallocate_cache is false, the cache will retain the same memory footprint
499 * after flushing and should be destroyed to deallocate.
500 */
501 virtual void Flush(bool reallocate_cache = true);
502 503 /**
504 * Push the modifications applied to this cache to its base while retaining
505 * the contents of this cache (except for spent coins, which we erase).
506 * Failure to call this method or Flush() before destruction will cause the changes
507 * to be forgotten.
508 */
509 void Sync();
510 511 /**
512 * Removes the UTXO with the given outpoint from the cache, if it is
513 * not modified.
514 */
515 void Uncache(const COutPoint &outpoint);
516 517 //! Size of the cache (in number of transaction outputs)
518 unsigned int GetCacheSize() const;
519 520 //! Number of dirty cache entries (transaction outputs)
521 size_t GetDirtyCount() const noexcept { return m_dirty_count; }
522 523 //! Calculate the size of the cache (in bytes)
524 size_t DynamicMemoryUsage() const;
525 526 //! Check whether all prevouts of the transaction are present in the UTXO set represented by this view
527 bool HaveInputs(const CTransaction& tx) const;
528 529 //! Force a reallocation of the cache map. This is required when downsizing
530 //! the cache because the map's allocator may be hanging onto a lot of
531 //! memory despite having called .clear().
532 //!
533 //! See: https://stackoverflow.com/questions/42114044/how-to-release-unordered-map-memory
534 void ReallocateCache();
535 536 //! Run an internal sanity check on the cache data structure. */
537 void SanityCheck() const;
538 539 class ResetGuard
540 {
541 private:
542 friend CCoinsViewCache;
543 CCoinsViewCache& m_cache;
544 explicit ResetGuard(CCoinsViewCache& cache LIFETIMEBOUND) noexcept : m_cache{cache} {}
545 546 public:
547 ResetGuard(const ResetGuard&) = delete;
548 ResetGuard& operator=(const ResetGuard&) = delete;
549 ResetGuard(ResetGuard&&) = delete;
550 ResetGuard& operator=(ResetGuard&&) = delete;
551 552 ~ResetGuard() { m_cache.Reset(); }
553 };
554 555 //! Create a scoped guard that will call `Reset()` on this cache when it goes out of scope.
556 [[nodiscard]] ResetGuard CreateResetGuard() noexcept { return ResetGuard{*this}; }
557 558 private:
559 /**
560 * @note this is marked const, but may actually append to `cacheCoins`, increasing
561 * memory usage.
562 */
563 CCoinsMap::iterator FetchCoin(const COutPoint &outpoint) const;
564 };
565 566 /**
567 * CCoinsViewCache subclass that asynchronously fetches most block input prevouts in parallel during ConnectBlock without
568 * mutating the base cache.
569 *
570 * Only used in ConnectBlock to pass as an ephemeral view that can be reset if the block is invalid.
571 * It provides the same interface as CCoinsViewCache.
572 * It adds an additional StartFetching method to provide the block.
573 *
574 * When a block is passed to StartFetching, the inputs of the block are flattened into a vector of InputToFetch
575 * objects. StartFetching then submits worker tasks to a ThreadPool and keeps the returned futures alive until fetching
576 * is stopped.
577 *
578 * ProcessInput() atomically fetches and increments m_input_head, so each thread can only access a single element of the
579 * m_inputs vector at a time. Workers race to claim inputs, so they may fetch elements in any order. If the fetched
580 * index is greater than or equal to the size of m_inputs, no more inputs can be fetched and false is returned.
581 *
582 * The worker claims the InputToFetch at this index, fetches the coin from the base cache and moves it into the
583 * InputToFetch object. The ready flag is then set with a release memory order. This allows the ready flag to be
584 * used as a memory fence, guaranteeing the coin being written to the object will have happened before another
585 * thread tests the flag with an acquire memory order.
586 * This assumes all base->PeekCoin() paths are safe for concurrent readers and do not mutate lower cache layers.
587 *
588 * When a coin is requested from the cache on the main thread and is not already in cacheCoins map, FetchCoinFromBase
589 * checks whether the next unconsumed entry in m_inputs has the requested outpoint. On a match, m_input_tail is advanced
590 * and the entry's ready flag is waited on with an acquire memory order until a worker has finished fetching it. The
591 * coin is then moved out and returned. Since the main thread is the only consumer of validation results, it blocks
592 * on the specific input it needs rather than racing workers for other inputs.
593 *
594 * StopFetching() is called in Flush() and in Reset() (the per-block teardown) so workers stop before the block they
595 * reference goes away. It stops fetching by moving m_input_head to the end of m_inputs (so workers quickly exit),
596 * then waits for all futures to complete and clears the per-block state (m_inputs and the head/tail counters).
597 *
598 * Workers advance m_input_head to fetch inputs. Main thread advances m_input_tail to consume.
599 *
600 * Before workers start:
601 *
602 * m_input_head
603 * m_input_tail
604 * │
605 * ▼
606 * ┌─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┐
607 * m_inputs: │ waiting │ waiting │ waiting │ waiting │ waiting │ waiting │ waiting │ waiting │ waiting │
608 * │ │ │ │ │ │ │ │ │ │
609 * └─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┘
610 *
611 * After workers start:
612 *
613 * Worker 2 Worker 0 Worker 3 Worker 1 m_input_head
614 * │ │ │ │ │
615 * ▼ ▼ ▼ ▼ ▼
616 * ┌─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┐
617 * m_inputs: │ ready │ ready │fetching │ ready │fetching │fetching │fetching │ waiting │ waiting │
618 * │consumed │ ✓ │ ● │ ✓ │ ● │ ● │ ● │ │ │
619 * └─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┘
620 * ▲
621 * │
622 * m_input_tail
623 */
624 class CoinsViewOverlay : public CCoinsViewCache
625 {
626 private:
627 //! The latest input not yet being fetched. Workers atomically increment this when fetching.
628 std::atomic_uint32_t m_input_head{0};
629 //! The latest input not yet accessed by a consumer. Only the main thread increments this.
630 mutable uint32_t m_input_tail{0};
631 632 //! The inputs of the block which is being fetched.
633 struct InputToFetch {
634 //! Workers set this after setting the coin. The main thread tests this before reading the coin.
635 std::atomic_flag ready{};
636 //! The outpoint of the input to fetch.
637 const COutPoint& outpoint;
638 //! The coin that workers will fetch and main thread will insert into cache.
639 //! Mutable so it can be moved in FetchCoinFromBase.
640 mutable std::optional<Coin> coin{std::nullopt};
641 642 explicit InputToFetch(const COutPoint& o LIFETIMEBOUND) noexcept : outpoint{o} {}
643 644 //! Move ctor is required for resizing m_inputs in StartFetching. Elements will never move once parallel tasks
645 //! are started, so we can assert that coin is nullopt and ready is false.
646 InputToFetch(InputToFetch&& other) noexcept : outpoint{other.outpoint}
647 {
648 Assert(!other.coin);
649 Assert(!other.ready.test(std::memory_order_relaxed));
650 }
651 };
652 //! Must only be mutated when m_futures is empty. Elements may be mutated when m_futures is not empty.
653 std::vector<InputToFetch> m_inputs{};
654 655 /**
656 * Claim and fetch the next input in the queue.
657 *
658 * @return true if an input prevout was fetched
659 * @return false if there are no more input prevouts in the queue to fetch
660 */
661 bool ProcessInput() noexcept
662 {
663 const auto i{m_input_head.fetch_add(1, std::memory_order_relaxed)};
664 if (i >= m_inputs.size()) return false;
665 666 auto& input{m_inputs[i]};
667 input.coin = base->PeekCoin(input.outpoint);
668 // Use release so writing coin above happens before the main thread acquires.
669 Assert(!input.ready.test_and_set(std::memory_order_release));
670 input.ready.notify_one();
671 return true;
672 }
673 674 //! Stop all worker threads and clear fetching data.
675 //! Calling this is idempotent, and may safely be called if not fetching.
676 void StopFetching() noexcept
677 {
678 if (m_futures.empty()) {
679 Assert(m_inputs.empty());
680 Assert(m_input_head.load(std::memory_order_relaxed) == 0);
681 Assert(m_input_tail == 0);
682 return;
683 }
684 // Skip fetching the rest of the inputs by moving the head to the end.
685 m_input_head.store(m_inputs.size(), std::memory_order_relaxed);
686 // Wait for all threads to stop.
687 for (auto& future : m_futures) future.wait();
688 m_futures.clear();
689 m_inputs.clear();
690 m_input_head.store(0, std::memory_order_relaxed);
691 m_input_tail = 0;
692 }
693 694 std::optional<Coin> FetchCoinFromBase(const COutPoint& outpoint) const override
695 {
696 // This assumes ConnectBlock accesses all inputs in the same order as
697 // they are added to m_inputs in StartFetching.
698 if (m_input_tail < m_inputs.size() && m_inputs[m_input_tail].outpoint == outpoint) {
699 // We advance the tail since the input is cached and not accessed through this method again.
700 auto& input{m_inputs[m_input_tail++]};
701 // Wait until the coin is ready to be read. We need acquire so we match the worker thread's release.
702 input.ready.wait(/*old=*/false, std::memory_order_acquire);
703 // We can move the coin since we won't access this input again.
704 return std::move(input.coin);
705 }
706 707 // We will only get here for BIP30 checks, an invalid block, or if the threadpool has not been started.
708 return base->PeekCoin(outpoint);
709 }
710 711 //! Non-null. May have zero workers when input fetching is disabled.
712 std::shared_ptr<ThreadPool> m_thread_pool;
713 std::vector<std::future<void>> m_futures{};
714 715 protected:
716 void Reset() noexcept override
717 {
718 StopFetching();
719 CCoinsViewCache::Reset();
720 }
721 722 public:
723 explicit CoinsViewOverlay(CCoinsView* in_base, std::shared_ptr<ThreadPool> thread_pool,
724 bool deterministic = false) noexcept
725 : CCoinsViewCache{in_base, deterministic}, m_thread_pool{std::move(thread_pool)}
726 {
727 Assert(m_thread_pool);
728 }
729 730 ~CoinsViewOverlay() noexcept override { StopFetching(); }
731 732 //! Start fetching inputs from block.
733 [[nodiscard]] ResetGuard StartFetching(const CBlock& block LIFETIMEBOUND) noexcept;
734 735 void Flush(bool reallocate_cache = true) override
736 {
737 if (!Assume(AllInputsConsumed())) {
738 LogWarning("Block %s input prevout prefetch queue was not fully consumed; inputs were accessed out of order, so prefetching degraded to serial lookups for this block.", GetBestBlock().ToString());
739 }
740 StopFetching();
741 CCoinsViewCache::Flush(reallocate_cache);
742 }
743 744 //! Verify that all parallel fetched input prevouts have been consumed.
745 bool AllInputsConsumed() const noexcept { return m_input_tail == m_inputs.size(); }
746 };
747 748 //! Utility function to add all of a transaction's outputs to a cache.
749 //! When check is false, this assumes that overwrites are only possible for coinbase transactions.
750 //! When check is true, the underlying view may be queried to determine whether an addition is
751 //! an overwrite.
752 // TODO: pass in a boolean to limit these possible overwrites to known
753 // (pre-BIP34) cases.
754 void AddCoins(CCoinsViewCache& cache, const CTransaction& tx, int nHeight, bool check = false);
755 756 //! Utility function to find any unspent output with a given txid.
757 //! This function can be quite expensive because in the event of a transaction
758 //! which is not found in the cache, it can cause up to MAX_OUTPUTS_PER_BLOCK
759 //! lookups to database, so it should be used with care.
760 const Coin& AccessByTxid(const CCoinsViewCache& cache, const Txid& txid);
761 762 /**
763 * This is a minimally invasive approach to shutdown on LevelDB read errors from the
764 * chainstate, while keeping user interface out of the common library, which is shared
765 * between bitcoind, and bitcoin-qt and non-server tools.
766 *
767 * Writes do not need similar protection, as failure to write is handled by the caller.
768 */
769 class CCoinsViewErrorCatcher final : public CCoinsViewBacked
770 {
771 public:
772 explicit CCoinsViewErrorCatcher(CCoinsView* view) : CCoinsViewBacked(view) {}
773 774 void AddReadErrCallback(std::function<void()> f) {
775 m_err_callbacks.emplace_back(std::move(f));
776 }
777 778 std::optional<Coin> GetCoin(const COutPoint& outpoint) const override;
779 bool HaveCoin(const COutPoint& outpoint) const override;
780 std::optional<Coin> PeekCoin(const COutPoint& outpoint) const override;
781 782 private:
783 /** A list of callbacks to execute upon leveldb read error. */
784 std::vector<std::function<void()>> m_err_callbacks;
785 786 };
787 788 #endif // BITCOIN_COINS_H
789