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