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 [ - - + - : 7258859 : 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 [ + - + + ]: 113884 : Coin(const CTxOut& outIn, int nHeightIn, bool fCoinBaseIn) : out(outIn), fCoinBase(fCoinBaseIn),nHeight(nHeightIn) {}
[ + - ]
60 : :
61 : 129466 : void Clear() {
62 : 129466 : out.SetNull();
63 : 129466 : fCoinBase = false;
64 [ - + + + : 129466 : nHeight = 0;
+ - ]
65 : 61441 : }
66 : :
67 : : //! empty constructor
68 [ + - - - : 4885026 : Coin() : fCoinBase(false), nHeight(0) { }
+ - ]
[ + - + + ]
[ + - # #
# # ][ + -
+ - + - -
+ - + +
+ ]
69 : :
70 : 2226 : bool IsCoinBase() const {
71 [ # # # # : 2226 : return fCoinBase;
# # ][ + +
+ + + - ]
[ + + ]
72 : : }
73 : :
74 : : template<typename Stream>
75 : 85422 : void Serialize(Stream &s) const {
76 [ - + ]: 85422 : assert(!IsSpent());
77 : 85422 : uint32_t code{(uint32_t{nHeight} << 1) | uint32_t{fCoinBase}};
78 : 85422 : ::Serialize(s, VARINT(code));
79 : 85422 : ::Serialize(s, Using<TxOutCompression>(out));
80 : 85422 : }
81 : :
82 : : template<typename Stream>
83 : 87512 : void Unserialize(Stream &s) {
84 : 87512 : uint32_t code = 0;
85 : 87512 : ::Unserialize(s, VARINT(code));
86 : 87512 : nHeight = code >> 1;
87 : 87512 : fCoinBase = code & 1;
88 : 87512 : ::Unserialize(s, Using<TxOutCompression>(out));
89 : 87510 : }
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 [ + - ]: 14745241 : bool IsSpent() const {
95 [ + + # # ]: 13952135 : return out.IsNull();
[ + - + +
+ - + + +
- ][ - + +
+ - + # #
# # ][ + +
+ + + + +
+ + + + +
+ + - + +
+ + + - +
+ + ][ - +
+ - # # #
# # # # #
# # # # #
# # # # #
# # ][ + -
+ - + - +
- + + - +
+ - + - +
- + + + +
+ + + + +
- + + + +
+ + + + -
+ ]
96 : : }
97 : :
98 : 2181820 : size_t DynamicMemoryUsage() const {
99 [ + + + + : 2990438 : 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 : 551168 : static void AddFlags(uint8_t flags, CoinsCachePair& pair, CoinsCachePair& sentinel) noexcept
139 : : {
140 [ + + ]: 551168 : Assume(flags & (DIRTY | FRESH));
141 [ + + ]: 551168 : if (!pair.second.m_flags) {
142 : 412391 : Assume(!pair.second.m_prev && !pair.second.m_next);
143 : 412391 : pair.second.m_prev = sentinel.second.m_prev;
144 : 412391 : pair.second.m_next = &sentinel;
145 : 412391 : sentinel.second.m_prev = &pair;
146 : 412391 : pair.second.m_prev->second.m_next = &pair;
147 : : }
148 : 551168 : Assume(pair.second.m_prev && pair.second.m_next);
149 : 551168 : pair.second.m_flags |= flags;
150 : 551168 : }
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 : 25990636 : CCoinsCacheEntry() noexcept = default;
177 : 20320 : explicit CCoinsCacheEntry(Coin&& coin_) noexcept : coin(std::move(coin_)) {}
178 : 26011276 : ~CCoinsCacheEntry()
179 : : {
180 : 52022552 : SetClean();
181 : 26011276 : }
182 : :
183 : 418739 : static void SetDirty(CoinsCachePair& pair, CoinsCachePair& sentinel) noexcept { AddFlags(DIRTY, pair, sentinel); }
184 : 132429 : static void SetFresh(CoinsCachePair& pair, CoinsCachePair& sentinel) noexcept { AddFlags(FRESH, pair, sentinel); }
185 : :
186 : 26037067 : void SetClean() noexcept
187 : : {
188 [ + + ][ + - : 26011282 : if (!m_flags) return;
- + + - -
- ]
189 : 571389 : m_next->second.m_prev = m_prev;
190 : 571389 : m_prev->second.m_next = m_next;
191 : 571389 : m_flags = 0;
192 : 571389 : m_prev = m_next = nullptr;
193 : : }
194 [ + - ][ + - : 1611019 : bool IsDirty() const noexcept { return m_flags & DIRTY; }
+ + + + -
+ + + + +
+ + + - +
- ][ + - +
- + - + -
+ - + - +
- + - + -
+ - + - ]
195 [ + + + + : 418120 : bool IsFresh() const noexcept { return m_flags & FRESH; }
+ + + + +
+ ][ + + ]
196 : :
197 : : //! Only call Next when this entry is DIRTY, FRESH, or both
198 : 509159 : CoinsCachePair* Next() const noexcept
199 : : {
200 [ - + ][ + - : 457586 : Assume(m_flags);
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
201 [ - + ][ + - : 51236 : return m_next;
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
202 : : }
203 : :
204 : : //! Only call Prev when this entry is DIRTY, FRESH, or both
205 : 79915 : CoinsCachePair* Prev() const noexcept
206 : : {
207 [ - + ][ + - : 39977 : Assume(m_flags);
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - ]
208 [ - + - + ]: 39977 : return m_prev;
[ + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
209 : : }
210 : :
211 : : //! Only use this for initializing the linked list sentinel
212 : 158998 : void SelfRef(CoinsCachePair& pair) noexcept
213 : : {
214 [ + - + - : 158998 : Assume(&pair.second == this);
+ - ][ + - ]
215 : 158998 : m_prev = &pair;
216 : 158998 : m_next = &pair;
217 : : // Set sentinel to DIRTY so we can call Next on it
218 [ + - + - : 158998 : 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 : 79 : CCoinsViewCursor(const uint256& in_block_hash) : block_hash(in_block_hash) {}
244 : 79 : 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 [ - - - - : 46 : 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 : 10690 : CoinsViewCacheCursor(size_t& dirty_count LIFETIMEBOUND,
281 : : CoinsCachePair& sentinel LIFETIMEBOUND,
282 : : CCoinsMap& map LIFETIMEBOUND,
283 : : bool will_erase) noexcept
284 [ + + ]: 10690 : : m_dirty_count(dirty_count), m_sentinel(sentinel), m_map(map), m_will_erase(will_erase) {}
285 : :
286 : 10690 : inline CoinsCachePair* Begin() const noexcept { return m_sentinel.second.Next(); }
287 [ + + ]: 388737 : inline CoinsCachePair* End() const noexcept { return &m_sentinel; }
288 : :
289 : : //! Return the next entry after current, possibly erasing current
290 : 378047 : inline CoinsCachePair* NextAndMaybeErase(CoinsCachePair& current) noexcept
291 : : {
292 [ + - ]: 378047 : const auto next_entry{current.second.Next()};
293 [ + - + + ]: 756094 : 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 [ + + ]: 378047 : if (!m_will_erase) {
297 [ + + ]: 43478 : if (current.second.coin.IsSpent()) {
298 [ - + - - ]: 17693 : assert(current.second.coin.DynamicMemoryUsage() == 0); // scriptPubKey was already cleared in SpendCoin
299 : 17693 : m_map.erase(current.first);
300 : : } else {
301 [ + - ]: 25785 : current.second.SetClean();
302 : : }
303 : : }
304 : 378047 : return next_entry;
305 : : }
306 : :
307 [ + + + + : 195316 : inline bool WillErase(CoinsCachePair& current) const noexcept { return m_will_erase || current.second.coin.IsSpent(); }
+ + + + ]
308 : 256 : size_t GetDirtyCount() const noexcept { return m_dirty_count; }
309 [ + - ]: 256 : 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 : 159240 : class CCoinsView
319 : : {
320 : : public:
321 : : //! As we use CCoinsViews polymorphically, have a virtual destructor
322 : 212 : 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 : 4 : class CoinsViewEmpty : public CCoinsView
358 : : {
359 : : protected:
360 [ + - + - : 4 : CoinsViewEmpty() = default;
+ - ]
361 : :
362 : : public:
363 : : static CoinsViewEmpty& Get();
364 : :
365 : : CoinsViewEmpty(const CoinsViewEmpty&) = delete;
366 : : CoinsViewEmpty& operator=(const CoinsViewEmpty&) = delete;
367 : :
368 : 3 : std::optional<Coin> GetCoin(const COutPoint&) const override { return {}; }
369 : 1 : std::optional<Coin> PeekCoin(const COutPoint& outpoint) const override { return GetCoin(outpoint); }
370 : 0 : bool HaveCoin(const COutPoint& outpoint) const override { return !!GetCoin(outpoint); }
371 : 0 : uint256 GetBestBlock() const override { return {}; }
372 : 0 : std::vector<uint256> GetHeadBlocks() const override { return {}; }
373 : 0 : void BatchWrite(CoinsViewCacheCursor& cursor, const uint256&) override
374 : : {
375 [ # # ]: 0 : for (auto it{cursor.Begin()}; it != cursor.End(); it = cursor.NextAndMaybeErase(*it)) { }
376 : 0 : }
377 : 0 : std::unique_ptr<CCoinsViewCursor> Cursor() const override { return {}; }
378 : 0 : size_t EstimateSize() const override { return 0; }
379 : : };
380 : :
381 : : /** CCoinsView backed by another CCoinsView */
382 : 0 : class CCoinsViewBacked : public CCoinsView
383 : : {
384 : : protected:
385 : : CCoinsView* base;
386 : :
387 : : public:
388 [ - + ]: 159028 : explicit CCoinsViewBacked(CCoinsView* in_view) : base{Assert(in_view)} {}
389 : :
390 [ + - + - ]: 284 : void SetBackend(CCoinsView& in_view) { base = &in_view; }
391 : :
392 : 19139 : std::optional<Coin> GetCoin(const COutPoint& outpoint) const override { return base->GetCoin(outpoint); }
393 : 18213 : std::optional<Coin> PeekCoin(const COutPoint& outpoint) const override { return base->PeekCoin(outpoint); }
394 : 0 : bool HaveCoin(const COutPoint& outpoint) const override { return base->HaveCoin(outpoint); }
395 : 613 : uint256 GetBestBlock() const override { return base->GetBestBlock(); }
396 : 0 : std::vector<uint256> GetHeadBlocks() const override { return base->GetHeadBlocks(); }
397 : 95 : void BatchWrite(CoinsViewCacheCursor& cursor, const uint256& block_hash) override { base->BatchWrite(cursor, block_hash); }
398 : 0 : std::unique_ptr<CCoinsViewCursor> Cursor() const override { return base->Cursor(); }
399 : 0 : 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 : 0 : std::unique_ptr<CCoinsViewCursor> Cursor() const override {
450 [ # # ]: 0 : 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 [ + - ][ + - : 89 : 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 : 8826 : 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 [ + - # # ]: 8826 : ~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 [ + - ]: 8826 : [[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 : 1897 : 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 : 978 : 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 : 919 : InputToFetch(InputToFetch&& other) noexcept : outpoint{other.outpoint}
647 : : {
648 [ - + ]: 919 : Assert(!other.coin);
649 [ - + ]: 919 : Assert(!other.ready.test(std::memory_order_relaxed));
650 : 919 : }
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 : 1515 : bool ProcessInput() noexcept
662 : : {
663 [ - + ]: 1515 : const auto i{m_input_head.fetch_add(1, std::memory_order_relaxed)};
664 [ - + + + ]: 1515 : if (i >= m_inputs.size()) return false;
665 : :
666 : 883 : auto& input{m_inputs[i]};
667 : 883 : input.coin = base->PeekCoin(input.outpoint);
668 : : // Use release so writing coin above happens before the main thread acquires.
669 [ - + ]: 883 : Assert(!input.ready.test_and_set(std::memory_order_release));
670 : 883 : input.ready.notify_one();
671 : 883 : 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 : 17843 : void StopFetching() noexcept
677 : : {
678 [ + + ]: 17843 : if (m_futures.empty()) {
679 [ - + ]: 17764 : Assert(m_inputs.empty());
680 [ - + ]: 17764 : Assert(m_input_head.load(std::memory_order_relaxed) == 0);
681 [ - + ]: 17764 : Assert(m_input_tail == 0);
682 : 17764 : return;
683 : : }
684 : : // Skip fetching the rest of the inputs by moving the head to the end.
685 [ - + ]: 79 : m_input_head.store(m_inputs.size(), std::memory_order_relaxed);
686 : : // Wait for all threads to stop.
687 [ + + ]: 711 : for (auto& future : m_futures) future.wait();
688 : 79 : m_futures.clear();
689 : 79 : m_inputs.clear();
690 : 79 : m_input_head.store(0, std::memory_order_relaxed);
691 : 79 : m_input_tail = 0;
692 : : }
693 : :
694 : 19757 : 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 [ - + + + : 19757 : 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 : 788 : 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 : 788 : input.ready.wait(/*old=*/false, std::memory_order_acquire);
703 : : // We can move the coin since we won't access this input again.
704 : 788 : 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 : 18969 : 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 : 8824 : void Reset() noexcept override
717 : : {
718 : 8824 : StopFetching();
719 : 8824 : CCoinsViewCache::Reset();
720 : 8824 : }
721 : :
722 : : public:
723 : 206 : explicit CoinsViewOverlay(CCoinsView* in_base, std::shared_ptr<ThreadPool> thread_pool,
724 : : bool deterministic = false) noexcept
725 [ - + ]: 206 : : CCoinsViewCache{in_base, deterministic}, m_thread_pool{std::move(thread_pool)}
726 : : {
727 [ - + ]: 206 : Assert(m_thread_pool);
728 : 206 : }
729 : :
730 [ + - ]: 609 : ~CoinsViewOverlay() noexcept override { StopFetching(); }
731 : :
732 : : //! Start fetching inputs from block.
733 : : [[nodiscard]] ResetGuard StartFetching(const CBlock& block LIFETIMEBOUND) noexcept;
734 : :
735 : 8812 : void Flush(bool reallocate_cache = true) override
736 : : {
737 : 17624 : if (!Assume(AllInputsConsumed())) {
738 [ # # ]: 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());
739 : : }
740 : 8812 : StopFetching();
741 : 8812 : CCoinsViewCache::Flush(reallocate_cache);
742 : 8812 : }
743 : :
744 : : //! Verify that all parallel fetched input prevouts have been consumed.
745 [ - + - + ]: 8812 : 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 [ + - ]: 196 : explicit CCoinsViewErrorCatcher(CCoinsView* view) : CCoinsViewBacked(view) {}
773 : :
774 : 1 : void AddReadErrCallback(std::function<void()> f) {
775 [ + - ]: 1 : m_err_callbacks.emplace_back(std::move(f));
776 : 1 : }
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
|
