Branch data Line data Source code
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 [ + - + - : 100558093 : 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 [ + + ]: 66 : Coin(CTxOut&& outIn, int nHeightIn, bool fCoinBaseIn) : out(std::move(outIn)), fCoinBase(fCoinBaseIn), nHeight(nHeightIn) {}
59 [ + + + + ]: 23379737 : Coin(const CTxOut& outIn, int nHeightIn, bool fCoinBaseIn) : out(outIn), fCoinBase(fCoinBaseIn),nHeight(nHeightIn) {}
[ + - ]
60 : :
61 : 14738319 : void Clear() {
62 : 14738319 : out.SetNull();
63 : 14738319 : fCoinBase = false;
64 [ - + + + : 14738319 : nHeight = 0;
+ - ]
65 : 14670250 : }
66 : :
67 : : //! empty constructor
68 [ + - + - : 86096483 : Coin() : fCoinBase(false), nHeight(0) { }
+ - ]
[ + - # # ]
[ + - + + ]
[ + - + -
+ - - + -
+ + + ]
69 : :
70 : 15138295 : bool IsCoinBase() const {
71 [ + + ][ + + : 15138295 : return fCoinBase;
+ + + + ]
[ + - + - ]
72 : : }
73 : :
74 : : template<typename Stream>
75 : 320369 : void Serialize(Stream &s) const {
76 [ - + ]: 320369 : assert(!IsSpent());
77 : 320369 : uint32_t code{(uint32_t{nHeight} << 1) | uint32_t{fCoinBase}};
78 : 320369 : ::Serialize(s, VARINT(code));
79 : 320369 : ::Serialize(s, Using<TxOutCompression>(out));
80 : 320369 : }
81 : :
82 : : template<typename Stream>
83 : 370745 : void Unserialize(Stream &s) {
84 : 370745 : uint32_t code = 0;
85 : 370745 : ::Unserialize(s, VARINT(code));
86 : 370745 : nHeight = code >> 1;
87 : 370745 : fCoinBase = code & 1;
88 : 370745 : ::Unserialize(s, Using<TxOutCompression>(out));
89 : 370743 : }
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 [ + - ]: 137832142 : bool IsSpent() const {
95 [ - + + + : 137140182 : return out.IsNull();
- + ][ + -
+ + + - +
+ + + ][ +
+ + + + +
+ + + + +
+ + + - +
+ + + + -
+ + + ][ +
+ + - + -
+ - + + -
+ + - + -
+ - + + +
+ + + + +
+ - + + +
+ + + + +
- + ]
[ + + + + ]
[ - + + - ]
96 : : }
97 : :
98 : 55317095 : size_t DynamicMemoryUsage() const {
99 [ + + + + : 56146750 : 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 : 61269389 : static void AddFlags(uint8_t flags, CoinsCachePair& pair, CoinsCachePair& sentinel) noexcept
139 : : {
140 [ + + ]: 61269389 : Assume(flags & (DIRTY | FRESH));
141 [ + + ]: 61269389 : if (!pair.second.m_flags) {
142 : 38217814 : Assume(!pair.second.m_prev && !pair.second.m_next);
143 : 38217814 : pair.second.m_prev = sentinel.second.m_prev;
144 : 38217814 : pair.second.m_next = &sentinel;
145 : 38217814 : sentinel.second.m_prev = &pair;
146 : 38217814 : pair.second.m_prev->second.m_next = &pair;
147 : : }
148 : 61269389 : Assume(pair.second.m_prev && pair.second.m_next);
149 : 61269389 : pair.second.m_flags |= flags;
150 : 61269389 : }
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 : 64849468 : CCoinsCacheEntry() noexcept = default;
177 : 25207 : explicit CCoinsCacheEntry(Coin&& coin_) noexcept : coin(std::move(coin_)) {}
178 : 64874995 : ~CCoinsCacheEntry()
179 : : {
180 : 129749990 : SetClean();
181 : 64874995 : }
182 : :
183 : 38224824 : static void SetDirty(CoinsCachePair& pair, CoinsCachePair& sentinel) noexcept { AddFlags(DIRTY, pair, sentinel); }
184 : 23044565 : static void SetFresh(CoinsCachePair& pair, CoinsCachePair& sentinel) noexcept { AddFlags(FRESH, pair, sentinel); }
185 : :
186 : 64945001 : void SetClean() noexcept
187 : : {
188 [ + + ][ + - : 64875001 : if (!m_flags) return;
- + + - -
- ]
189 : 38650353 : m_next->second.m_prev = m_prev;
190 : 38650353 : m_prev->second.m_next = m_next;
191 : 38650353 : m_flags = 0;
192 : 38650353 : m_prev = m_next = nullptr;
193 : : }
194 [ + - ][ + - : 39887157 : bool IsDirty() const noexcept { return m_flags & DIRTY; }
+ + + + -
+ + + + +
+ + + - +
- ][ + - +
- + - + -
+ - + - +
- + - + -
+ - + - ]
195 [ + + + + : 15833931 : bool IsFresh() const noexcept { return m_flags & FRESH; }
+ + + + +
+ ][ + + ]
196 : :
197 : : //! Only call Next when this entry is DIRTY, FRESH, or both
198 : 1262504 : CoinsCachePair* Next() const noexcept
199 : : {
200 [ - + ][ + - : 1055253 : Assume(m_flags);
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
201 [ - + ][ + - : 210573 : return m_next;
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
202 : : }
203 : :
204 : : //! Only call Prev when this entry is DIRTY, FRESH, or both
205 : 105993 : CoinsCachePair* Prev() const noexcept
206 : : {
207 [ - + ][ + - : 53016 : Assume(m_flags);
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - ]
208 [ - + - + ]: 53016 : return m_prev;
[ + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
209 : : }
210 : :
211 : : //! Only use this for initializing the linked list sentinel
212 : 432539 : void SelfRef(CoinsCachePair& pair) noexcept
213 : : {
214 [ + - # # : 432539 : Assume(&pair.second == this);
# # ][ + -
+ - + - ]
215 : 432539 : m_prev = &pair;
216 : 432539 : m_next = &pair;
217 : : // Set sentinel to DIRTY so we can call Next on it
218 [ + - # # : 432539 : 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 : 1250 : CCoinsViewCursor(const uint256& in_block_hash) : block_hash(in_block_hash) {}
244 : 1250 : 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 [ + - + - : 104 : 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 : 155738 : CoinsViewCacheCursor(size_t& dirty_count LIFETIMEBOUND,
281 : : CoinsCachePair& sentinel LIFETIMEBOUND,
282 : : CCoinsMap& map LIFETIMEBOUND,
283 : : bool will_erase) noexcept
284 [ + + ]: 155738 : : m_dirty_count(dirty_count), m_sentinel(sentinel), m_map(map), m_will_erase(will_erase) {}
285 : :
286 : 155738 : inline CoinsCachePair* Begin() const noexcept { return m_sentinel.second.Next(); }
287 [ + + ]: 1101715 : inline CoinsCachePair* End() const noexcept { return &m_sentinel; }
288 : :
289 : : //! Return the next entry after current, possibly erasing current
290 : 945977 : inline CoinsCachePair* NextAndMaybeErase(CoinsCachePair& current) noexcept
291 : : {
292 [ + - ]: 945977 : const auto next_entry{current.second.Next()};
293 [ + - + + ]: 1891954 : 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 [ + + ]: 945977 : if (!m_will_erase) {
297 [ + + ]: 90724 : if (current.second.coin.IsSpent()) {
298 [ - + - - ]: 20724 : assert(current.second.coin.DynamicMemoryUsage() == 0); // scriptPubKey was already cleared in SpendCoin
299 : 20724 : m_map.erase(current.first);
300 : : } else {
301 [ + - ]: 70000 : current.second.SetClean();
302 : : }
303 : : }
304 : 945977 : return next_entry;
305 : : }
306 : :
307 [ + + + + : 477593 : inline bool WillErase(CoinsCachePair& current) const noexcept { return m_will_erase || current.second.coin.IsSpent(); }
+ + + + ]
308 : 3910 : size_t GetDirtyCount() const noexcept { return m_dirty_count; }
309 [ + - ]: 3910 : 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 : 486377 : class CCoinsView
319 : : {
320 : : public:
321 : : //! As we use CCoinsViews polymorphically, have a virtual destructor
322 : 1342 : 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 : : //! Estimate database size
350 : : virtual size_t EstimateSize() const = 0;
351 : : };
352 : :
353 : : /** Noop coins view. */
354 : 4 : class CoinsViewEmpty : public CCoinsView
355 : : {
356 : : protected:
357 [ + - + - : 4 : CoinsViewEmpty() = default;
+ - ]
358 : :
359 : : public:
360 : : static CoinsViewEmpty& Get();
361 : :
362 : : CoinsViewEmpty(const CoinsViewEmpty&) = delete;
363 : : CoinsViewEmpty& operator=(const CoinsViewEmpty&) = delete;
364 : :
365 : 29 : std::optional<Coin> GetCoin(const COutPoint&) const override { return {}; }
366 : 1 : std::optional<Coin> PeekCoin(const COutPoint& outpoint) const override { return GetCoin(outpoint); }
367 : 0 : bool HaveCoin(const COutPoint& outpoint) const override { return !!GetCoin(outpoint); }
368 : 0 : uint256 GetBestBlock() const override { return {}; }
369 : 0 : std::vector<uint256> GetHeadBlocks() const override { return {}; }
370 : 0 : void BatchWrite(CoinsViewCacheCursor& cursor, const uint256&) override
371 : : {
372 [ # # ]: 0 : for (auto it{cursor.Begin()}; it != cursor.End(); it = cursor.NextAndMaybeErase(*it)) { }
373 : 0 : }
374 : 0 : size_t EstimateSize() const override { return 0; }
375 : : };
376 : :
377 : : /** CCoinsView backed by another CCoinsView */
378 : 0 : class CCoinsViewBacked : public CCoinsView
379 : : {
380 : : protected:
381 : : CCoinsView* base;
382 : :
383 : : public:
384 [ - + ]: 485035 : explicit CCoinsViewBacked(CCoinsView* in_view) : base{Assert(in_view)} {}
385 : :
386 [ + - + - ]: 89271 : void SetBackend(CCoinsView& in_view) { base = &in_view; }
387 : :
388 : 925046 : std::optional<Coin> GetCoin(const COutPoint& outpoint) const override { return base->GetCoin(outpoint); }
389 : 446660 : std::optional<Coin> PeekCoin(const COutPoint& outpoint) const override { return base->PeekCoin(outpoint); }
390 : 0 : bool HaveCoin(const COutPoint& outpoint) const override { return base->HaveCoin(outpoint); }
391 : 45455 : uint256 GetBestBlock() const override { return base->GetBestBlock(); }
392 : 0 : std::vector<uint256> GetHeadBlocks() const override { return base->GetHeadBlocks(); }
393 : 3612 : void BatchWrite(CoinsViewCacheCursor& cursor, const uint256& block_hash) override { base->BatchWrite(cursor, block_hash); }
394 : 0 : size_t EstimateSize() const override { return base->EstimateSize(); }
395 : : };
396 : :
397 : :
398 : : /** CCoinsView that adds a memory cache for transactions to another CCoinsView */
399 : : class CCoinsViewCache : public CCoinsViewBacked
400 : : {
401 : : private:
402 : : const bool m_deterministic;
403 : :
404 : : protected:
405 : : /**
406 : : * Make mutable so that we can "fill the cache" even from Get-methods
407 : : * declared as "const".
408 : : */
409 : : mutable uint256 m_block_hash;
410 : : mutable CCoinsMapMemoryResource m_cache_coins_memory_resource{};
411 : : /* The starting sentinel of the flagged entry circular doubly linked list. */
412 : : mutable CoinsCachePair m_sentinel;
413 : : mutable CCoinsMap cacheCoins;
414 : :
415 : : /* Cached dynamic memory usage for the inner Coin objects. */
416 : : mutable size_t cachedCoinsUsage{0};
417 : : /* Running count of dirty Coin cache entries. */
418 : : mutable size_t m_dirty_count{0};
419 : :
420 : : /**
421 : : * Discard all modifications made to this cache without flushing to the base view.
422 : : * This can be used to efficiently reuse a cache instance across multiple operations.
423 : : */
424 : : virtual void Reset() noexcept;
425 : :
426 : : /* Fetch the coin from base. Used for cache misses in FetchCoin. */
427 : : virtual std::optional<Coin> FetchCoinFromBase(const COutPoint& outpoint) const;
428 : :
429 : : public:
430 : : CCoinsViewCache(CCoinsView* in_base, bool deterministic = false);
431 : :
432 : : /**
433 : : * By deleting the copy constructor, we prevent accidentally using it when one intends to create a cache on top of a base cache.
434 : : */
435 : : CCoinsViewCache(const CCoinsViewCache &) = delete;
436 : :
437 : : // Standard CCoinsView methods
438 : : std::optional<Coin> GetCoin(const COutPoint& outpoint) const override;
439 : : std::optional<Coin> PeekCoin(const COutPoint& outpoint) const override;
440 : : bool HaveCoin(const COutPoint& outpoint) const override;
441 : : uint256 GetBestBlock() const override;
442 : : void SetBestBlock(const uint256& block_hash);
443 : : void BatchWrite(CoinsViewCacheCursor& cursor, const uint256& block_hash) override;
444 : :
445 : : /**
446 : : * Check if we have the given utxo already loaded in this cache.
447 : : * The semantics are the same as HaveCoin(), but no calls to
448 : : * the backing CCoinsView are made.
449 : : */
450 : : bool HaveCoinInCache(const COutPoint &outpoint) const;
451 : :
452 : : /**
453 : : * Return a reference to Coin in the cache, or coinEmpty if not found. This is
454 : : * more efficient than GetCoin.
455 : : *
456 : : * Generally, do not hold the reference returned for more than a short scope.
457 : : * While the current implementation allows for modifications to the contents
458 : : * of the cache while holding the reference, this behavior should not be relied
459 : : * on! To be safe, best to not hold the returned reference through any other
460 : : * calls to this cache.
461 : : */
462 : : const Coin& AccessCoin(const COutPoint &output) const;
463 : :
464 : : /**
465 : : * Add a coin. Set possible_overwrite to true if an unspent version may
466 : : * already exist in the cache.
467 : : */
468 : : void AddCoin(const COutPoint& outpoint, Coin&& coin, bool possible_overwrite);
469 : :
470 : : /**
471 : : * Emplace a coin into cacheCoins without performing any checks, marking
472 : : * the emplaced coin as dirty.
473 : : *
474 : : * NOT FOR GENERAL USE. Used only when loading coins from a UTXO snapshot.
475 : : * @sa ChainstateManager::PopulateAndValidateSnapshot()
476 : : */
477 : : void EmplaceCoinInternalDANGER(const COutPoint& outpoint, Coin&& coin);
478 : :
479 : : /**
480 : : * Spend a coin. Pass moveto in order to get the deleted data.
481 : : * If no unspent output exists for the passed outpoint, this call
482 : : * has no effect.
483 : : */
484 : : bool SpendCoin(const COutPoint &outpoint, Coin* moveto = nullptr);
485 : :
486 : : /**
487 : : * Push the modifications applied to this cache to its base and wipe local state.
488 : : * Failure to call this method or Sync() before destruction will cause the changes
489 : : * to be forgotten.
490 : : * If reallocate_cache is false, the cache will retain the same memory footprint
491 : : * after flushing and should be destroyed to deallocate.
492 : : */
493 : : virtual void Flush(bool reallocate_cache = true);
494 : :
495 : : /**
496 : : * Push the modifications applied to this cache to its base while retaining
497 : : * the contents of this cache (except for spent coins, which we erase).
498 : : * Failure to call this method or Flush() before destruction will cause the changes
499 : : * to be forgotten.
500 : : */
501 : : void Sync();
502 : :
503 : : /**
504 : : * Removes the UTXO with the given outpoint from the cache, if it is
505 : : * not modified.
506 : : */
507 : : void Uncache(const COutPoint &outpoint);
508 : :
509 : : //! Size of the cache (in number of transaction outputs)
510 : : unsigned int GetCacheSize() const;
511 : :
512 : : //! Number of dirty cache entries (transaction outputs)
513 [ + - ][ + - : 3592 : size_t GetDirtyCount() const noexcept { return m_dirty_count; }
+ - + - +
- + - ]
514 : :
515 : : //! Calculate the size of the cache (in bytes)
516 : : size_t DynamicMemoryUsage() const;
517 : :
518 : : //! Check whether all prevouts of the transaction are present in the UTXO set represented by this view
519 : : bool HaveInputs(const CTransaction& tx) const;
520 : :
521 : : //! Force a reallocation of the cache map. This is required when downsizing
522 : : //! the cache because the map's allocator may be hanging onto a lot of
523 : : //! memory despite having called .clear().
524 : : //!
525 : : //! See: https://stackoverflow.com/questions/42114044/how-to-release-unordered-map-memory
526 : : void ReallocateCache();
527 : :
528 : : //! Run an internal sanity check on the cache data structure. */
529 : : void SanityCheck() const;
530 : :
531 : : class ResetGuard
532 : : {
533 : : private:
534 : : friend CCoinsViewCache;
535 : : CCoinsViewCache& m_cache;
536 : 139889 : explicit ResetGuard(CCoinsViewCache& cache LIFETIMEBOUND) noexcept : m_cache{cache} {}
537 : :
538 : : public:
539 : : ResetGuard(const ResetGuard&) = delete;
540 : : ResetGuard& operator=(const ResetGuard&) = delete;
541 : : ResetGuard(ResetGuard&&) = delete;
542 : : ResetGuard& operator=(ResetGuard&&) = delete;
543 : :
544 [ + - + - ]: 139889 : ~ResetGuard() { m_cache.Reset(); }
[ + - # # ]
545 : : };
546 : :
547 : : //! Create a scoped guard that will call `Reset()` on this cache when it goes out of scope.
548 [ + - ]: 139889 : [[nodiscard]] ResetGuard CreateResetGuard() noexcept { return ResetGuard{*this}; }
549 : :
550 : : private:
551 : : /**
552 : : * @note this is marked const, but may actually append to `cacheCoins`, increasing
553 : : * memory usage.
554 : : */
555 : : CCoinsMap::iterator FetchCoin(const COutPoint &outpoint) const;
556 : : };
557 : :
558 : : /**
559 : : * CCoinsViewCache subclass that asynchronously fetches most block input prevouts in parallel during ConnectBlock without
560 : : * mutating the base cache.
561 : : *
562 : : * Only used in ConnectBlock to pass as an ephemeral view that can be reset if the block is invalid.
563 : : * It provides the same interface as CCoinsViewCache.
564 : : * It adds an additional StartFetching method to provide the block.
565 : : *
566 : : * When a block is passed to StartFetching, the inputs of the block are flattened into a vector of InputToFetch
567 : : * objects. StartFetching then submits worker tasks to a ThreadPool and keeps the returned futures alive until fetching
568 : : * is stopped.
569 : : *
570 : : * ProcessInput() atomically fetches and increments m_input_head, so each thread can only access a single element of the
571 : : * m_inputs vector at a time. Workers race to claim inputs, so they may fetch elements in any order. If the fetched
572 : : * index is greater than or equal to the size of m_inputs, no more inputs can be fetched and false is returned.
573 : : *
574 : : * The worker claims the InputToFetch at this index, fetches the coin from the base cache and moves it into the
575 : : * InputToFetch object. The ready flag is then set with a release memory order. This allows the ready flag to be
576 : : * used as a memory fence, guaranteeing the coin being written to the object will have happened before another
577 : : * thread tests the flag with an acquire memory order.
578 : : * This assumes all base->PeekCoin() paths are safe for concurrent readers and do not mutate lower cache layers.
579 : : *
580 : : * When a coin is requested from the cache on the main thread and is not already in cacheCoins map, FetchCoinFromBase
581 : : * checks whether the next unconsumed entry in m_inputs has the requested outpoint. On a match, m_input_tail is advanced
582 : : * and the entry's ready flag is waited on with an acquire memory order until a worker has finished fetching it. The
583 : : * coin is then moved out and returned. Since the main thread is the only consumer of validation results, it blocks
584 : : * on the specific input it needs rather than racing workers for other inputs.
585 : : *
586 : : * StopFetching() is called in Flush() and in Reset() (the per-block teardown) so workers stop before the block they
587 : : * reference goes away. It stops fetching by moving m_input_head to the end of m_inputs (so workers quickly exit),
588 : : * then waits for all futures to complete and clears the per-block state (m_inputs and the head/tail counters).
589 : : *
590 : : * Workers advance m_input_head to fetch inputs. Main thread advances m_input_tail to consume.
591 : : *
592 : : * Before workers start:
593 : : *
594 : : * m_input_head
595 : : * m_input_tail
596 : : * │
597 : : * ▼
598 : : * ┌─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┐
599 : : * m_inputs: │ waiting │ waiting │ waiting │ waiting │ waiting │ waiting │ waiting │ waiting │ waiting │
600 : : * │ │ │ │ │ │ │ │ │ │
601 : : * └─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┘
602 : : *
603 : : * After workers start:
604 : : *
605 : : * Worker 2 Worker 0 Worker 3 Worker 1 m_input_head
606 : : * │ │ │ │ │
607 : : * ▼ ▼ ▼ ▼ ▼
608 : : * ┌─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┐
609 : : * m_inputs: │ ready │ ready │fetching │ ready │fetching │fetching │fetching │ waiting │ waiting │
610 : : * │consumed │ ✓ │ ● │ ✓ │ ● │ ● │ ● │ │ │
611 : : * └─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┘
612 : : * ▲
613 : : * │
614 : : * m_input_tail
615 : : */
616 : : class CoinsViewOverlay : public CCoinsViewCache
617 : : {
618 : : private:
619 : : //! The latest input not yet being fetched. Workers atomically increment this when fetching.
620 : : std::atomic_uint32_t m_input_head{0};
621 : : //! The latest input not yet accessed by a consumer. Only the main thread increments this.
622 : : mutable uint32_t m_input_tail{0};
623 : :
624 : : //! The inputs of the block which is being fetched.
625 : 68977 : struct InputToFetch {
626 : : //! Workers set this after setting the coin. The main thread tests this before reading the coin.
627 : : std::atomic_flag ready{};
628 : : //! The outpoint of the input to fetch.
629 : : const COutPoint& outpoint;
630 : : //! The coin that workers will fetch and main thread will insert into cache.
631 : : //! Mutable so it can be moved in FetchCoinFromBase.
632 : : mutable std::optional<Coin> coin{std::nullopt};
633 : :
634 : 54319 : explicit InputToFetch(const COutPoint& o LIFETIMEBOUND) noexcept : outpoint{o} {}
635 : :
636 : : //! Move ctor is required for resizing m_inputs in StartFetching. Elements will never move once parallel tasks
637 : : //! are started, so we can assert that coin is nullopt and ready is false.
638 : 14658 : InputToFetch(InputToFetch&& other) noexcept : outpoint{other.outpoint}
639 : : {
640 [ - + ]: 14658 : Assert(!other.coin);
641 [ - + ]: 14658 : Assert(!other.ready.test(std::memory_order_relaxed));
642 : 14658 : }
643 : : };
644 : : //! Must only be mutated when m_futures is empty. Elements may be mutated when m_futures is not empty.
645 : : std::vector<InputToFetch> m_inputs{};
646 : :
647 : : /**
648 : : * Claim and fetch the next input in the queue.
649 : : *
650 : : * @return true if an input prevout was fetched
651 : : * @return false if there are no more input prevouts in the queue to fetch
652 : : */
653 : 80024 : bool ProcessInput() noexcept
654 : : {
655 [ - + ]: 80024 : const auto i{m_input_head.fetch_add(1, std::memory_order_relaxed)};
656 [ - + + + ]: 80024 : if (i >= m_inputs.size()) return false;
657 : :
658 : 54224 : auto& input{m_inputs[i]};
659 : 54224 : input.coin = base->PeekCoin(input.outpoint);
660 : : // Use release so writing coin above happens before the main thread acquires.
661 [ - + ]: 54224 : Assert(!input.ready.test_and_set(std::memory_order_release));
662 : 54224 : input.ready.notify_one();
663 : 54224 : return true;
664 : : }
665 : :
666 : : //! Stop all worker threads and clear fetching data.
667 : : //! Calling this is idempotent, and may safely be called if not fetching.
668 : 278397 : void StopFetching() noexcept
669 : : {
670 [ + + ]: 278397 : if (m_futures.empty()) {
671 [ - + ]: 269061 : Assert(m_inputs.empty());
672 [ - + ]: 269061 : Assert(m_input_head.load(std::memory_order_relaxed) == 0);
673 [ - + ]: 269061 : Assert(m_input_tail == 0);
674 : 269061 : return;
675 : : }
676 : : // Skip fetching the rest of the inputs by moving the head to the end.
677 [ - + ]: 9336 : m_input_head.store(m_inputs.size(), std::memory_order_relaxed);
678 : : // Wait for all threads to stop.
679 [ + + ]: 35136 : for (auto& future : m_futures) future.wait();
680 : 9336 : m_futures.clear();
681 : 9336 : m_inputs.clear();
682 : 9336 : m_input_head.store(0, std::memory_order_relaxed);
683 : 9336 : m_input_tail = 0;
684 : : }
685 : :
686 : 504627 : std::optional<Coin> FetchCoinFromBase(const COutPoint& outpoint) const override
687 : : {
688 : : // This assumes ConnectBlock accesses all inputs in the same order as
689 : : // they are added to m_inputs in StartFetching.
690 [ - + + + : 504627 : if (m_input_tail < m_inputs.size() && m_inputs[m_input_tail].outpoint == outpoint) {
+ + ]
691 : : // We advance the tail since the input is cached and not accessed through this method again.
692 : 54126 : auto& input{m_inputs[m_input_tail++]};
693 : : // Wait until the coin is ready to be read. We need acquire so we match the worker thread's release.
694 : 54126 : input.ready.wait(/*old=*/false, std::memory_order_acquire);
695 : : // We can move the coin since we won't access this input again.
696 : 54126 : return std::move(input.coin);
697 : : }
698 : :
699 : : // We will only get here for BIP30 checks, an invalid block, or if the threadpool has not been started.
700 : 450501 : return base->PeekCoin(outpoint);
701 : : }
702 : :
703 : : //! Non-null. May have zero workers when input fetching is disabled.
704 : : std::shared_ptr<ThreadPool> m_thread_pool;
705 : : std::vector<std::future<void>> m_futures{};
706 : :
707 : : protected:
708 : 139887 : void Reset() noexcept override
709 : : {
710 : 139887 : StopFetching();
711 : 139887 : CCoinsViewCache::Reset();
712 : 139887 : }
713 : :
714 : : public:
715 : 1326 : explicit CoinsViewOverlay(CCoinsView* in_base, std::shared_ptr<ThreadPool> thread_pool,
716 : : bool deterministic = false) noexcept
717 [ - + ]: 1326 : : CCoinsViewCache{in_base, deterministic}, m_thread_pool{std::move(thread_pool)}
718 : : {
719 [ - + ]: 1326 : Assert(m_thread_pool);
720 : 1326 : }
721 : :
722 [ + - ]: 3969 : ~CoinsViewOverlay() noexcept override { StopFetching(); }
723 : :
724 : : //! Start fetching inputs from block.
725 : : [[nodiscard]] ResetGuard StartFetching(const CBlock& block LIFETIMEBOUND) noexcept;
726 : :
727 : 137183 : void Flush(bool reallocate_cache = true) override
728 : : {
729 : 274366 : if (!Assume(AllInputsConsumed())) {
730 [ # # ]: 0 : 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());
731 : : }
732 : 137183 : StopFetching();
733 : 137183 : CCoinsViewCache::Flush(reallocate_cache);
734 : 137183 : }
735 : :
736 : : //! Verify that all parallel fetched input prevouts have been consumed.
737 [ - + - + ]: 137183 : bool AllInputsConsumed() const noexcept { return m_input_tail == m_inputs.size(); }
738 : : };
739 : :
740 : : //! Utility function to add all of a transaction's outputs to a cache.
741 : : //! When check is false, this assumes that overwrites are only possible for coinbase transactions.
742 : : //! When check is true, the underlying view may be queried to determine whether an addition is
743 : : //! an overwrite.
744 : : // TODO: pass in a boolean to limit these possible overwrites to known
745 : : // (pre-BIP34) cases.
746 : : void AddCoins(CCoinsViewCache& cache, const CTransaction& tx, int nHeight, bool check = false);
747 : :
748 : : //! Utility function to find any unspent output with a given txid.
749 : : //! This function can be quite expensive because in the event of a transaction
750 : : //! which is not found in the cache, it can cause up to MAX_OUTPUTS_PER_BLOCK
751 : : //! lookups to database, so it should be used with care.
752 : : const Coin& AccessByTxid(const CCoinsViewCache& cache, const Txid& txid);
753 : :
754 : : /**
755 : : * This is a minimally invasive approach to shutdown on LevelDB read errors from the
756 : : * chainstate, while keeping user interface out of the common library, which is shared
757 : : * between bitcoind, and bitcoin-qt and non-server tools.
758 : : *
759 : : * Writes do not need similar protection, as failure to write is handled by the caller.
760 : : */
761 : : class CCoinsViewErrorCatcher final : public CCoinsViewBacked
762 : : {
763 : : public:
764 [ + - ]: 1317 : explicit CCoinsViewErrorCatcher(CCoinsView* view) : CCoinsViewBacked(view) {}
765 : :
766 : 1092 : void AddReadErrCallback(std::function<void()> f) {
767 [ + - ]: 1092 : m_err_callbacks.emplace_back(std::move(f));
768 : 1092 : }
769 : :
770 : : std::optional<Coin> GetCoin(const COutPoint& outpoint) const override;
771 : : bool HaveCoin(const COutPoint& outpoint) const override;
772 : : std::optional<Coin> PeekCoin(const COutPoint& outpoint) const override;
773 : :
774 : : private:
775 : : /** A list of callbacks to execute upon leveldb read error. */
776 : : std::vector<std::function<void()>> m_err_callbacks;
777 : :
778 : : };
779 : :
780 : : #endif // BITCOIN_COINS_H
|
