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 [ + + + - : 148909486 : 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 [ + + + + ]: 23746007 : Coin(const CTxOut& outIn, int nHeightIn, bool fCoinBaseIn) : out(outIn), fCoinBase(fCoinBaseIn),nHeight(nHeightIn) {}
[ + - + + ]
60 : :
61 : 14786675 : void Clear() {
62 : 14786675 : out.SetNull();
63 : 14786675 : fCoinBase = false;
64 [ - + + + : 14786675 : nHeight = 0;
+ - ]
65 : 14718651 : }
66 : :
67 : : //! empty constructor
68 [ + - # # ]: 86049048 : Coin() : fCoinBase(false), nHeight(0) { }
[ + - + -
+ - - + -
+ + + ]
[ + - + + ]
[ + - - -
+ - ]
69 : :
70 : 15331300 : bool IsCoinBase() const {
71 [ + + + + : 15331300 : return fCoinBase;
+ - ]
[ + + # # ]
[ + + + +
+ + ]
72 : : }
73 : :
74 : : template<typename Stream>
75 : 318321 : void Serialize(Stream &s) const {
76 [ - + ]: 318321 : assert(!IsSpent());
77 : 318321 : uint32_t code{(uint32_t{nHeight} << 1) | uint32_t{fCoinBase}};
78 : 318321 : ::Serialize(s, VARINT(code));
79 : 318321 : ::Serialize(s, Using<TxOutCompression>(out));
80 : 318321 : }
81 : :
82 : : template<typename Stream>
83 : 381996 : void Unserialize(Stream &s) {
84 : 381996 : uint32_t code = 0;
85 : 381996 : ::Unserialize(s, VARINT(code));
86 : 381996 : nHeight = code >> 1;
87 : 381996 : fCoinBase = code & 1;
88 : 381996 : ::Unserialize(s, Using<TxOutCompression>(out));
89 : 381994 : }
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 [ + - ]: 135769299 : bool IsSpent() const {
95 [ + + + + : 135818841 : return out.IsNull();
+ - + - +
+ - + + -
+ - + - +
+ + + + +
+ + + - +
+ + + + +
- - ][ + +
+ + + - +
+ + - # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
[ + + + +
- + ][ - +
+ + + + -
+ - + ][ +
+ + + + +
+ + + + +
+ + + - +
+ + + + -
+ + + ][ -
+ + - # #
# # # # #
# # # # #
# # # # #
# # # ]
96 : : }
97 : :
98 : 55846611 : size_t DynamicMemoryUsage() const {
99 [ - + + + : 56639214 : 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 : 62088117 : static void AddFlags(uint8_t flags, CoinsCachePair& pair, CoinsCachePair& sentinel) noexcept
139 : : {
140 [ + + ]: 62088117 : Assume(flags & (DIRTY | FRESH));
141 [ + + ]: 62088117 : if (!pair.second.m_flags) {
142 : 38648469 : Assume(!pair.second.m_prev && !pair.second.m_next);
143 : 38648469 : pair.second.m_prev = sentinel.second.m_prev;
144 : 38648469 : pair.second.m_next = &sentinel;
145 : 38648469 : sentinel.second.m_prev = &pair;
146 : 38648469 : pair.second.m_prev->second.m_next = &pair;
147 : : }
148 : 62088117 : Assume(pair.second.m_prev && pair.second.m_next);
149 : 62088117 : pair.second.m_flags |= flags;
150 : 62088117 : }
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 : 64160800 : CCoinsCacheEntry() noexcept = default;
177 : 25437 : explicit CCoinsCacheEntry(Coin&& coin_) noexcept : coin(std::move(coin_)) {}
178 : 64186557 : ~CCoinsCacheEntry()
179 : : {
180 : 128373114 : SetClean();
181 : 64186557 : }
182 : :
183 : 38655336 : static void SetDirty(CoinsCachePair& pair, CoinsCachePair& sentinel) noexcept { AddFlags(DIRTY, pair, sentinel); }
184 : 23432781 : static void SetFresh(CoinsCachePair& pair, CoinsCachePair& sentinel) noexcept { AddFlags(FRESH, pair, sentinel); }
185 : :
186 : 64259385 : void SetClean() noexcept
187 : : {
188 [ + + ][ + - : 64186563 : if (!m_flags) return;
- + + - -
- ]
189 : 39119836 : m_next->second.m_prev = m_prev;
190 : 39119836 : m_prev->second.m_next = m_next;
191 : 39119836 : m_flags = 0;
192 : 39119836 : m_prev = m_next = nullptr;
193 : : }
194 [ + - ][ + - : 40398252 : bool IsDirty() const noexcept { return m_flags & DIRTY; }
+ - + - +
- + + + +
+ + + - +
- + - + -
+ - ][ + -
+ + + + -
+ + + + +
+ + + - +
- ]
195 [ + + + + : 16021831 : bool IsFresh() const noexcept { return m_flags & FRESH; }
+ + + + +
+ ][ + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ][ + + +
+ + + + +
+ + ]
196 : :
197 : : //! Only call Next when this entry is DIRTY, FRESH, or both
198 : 1252184 : CoinsCachePair* Next() const noexcept
199 : : {
200 [ + - + - : 1052866 : Assume(m_flags);
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - ]
[ - + ]
201 [ + + + - : 202704 : return m_next;
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - ]
[ - + ]
202 : : }
203 : :
204 : : //! Only call Prev when this entry is DIRTY, FRESH, or both
205 : 106574 : CoinsCachePair* Prev() const noexcept
206 : : {
207 [ + - + - : 53307 : Assume(m_flags);
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ][ - + ]
208 [ + - + - : 53307 : return m_prev;
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
[ - + - + ]
209 : : }
210 : :
211 : : //! Only use this for initializing the linked list sentinel
212 : 471367 : void SelfRef(CoinsCachePair& pair) noexcept
213 : : {
214 [ + - ][ + - : 471367 : Assume(&pair.second == this);
+ - + - ]
215 : 471367 : m_prev = &pair;
216 : 471367 : m_next = &pair;
217 : : // Set sentinel to DIRTY so we can call Next on it
218 [ + - ][ + - : 471367 : 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 : 229646 : size_t operator()(const Txid& id) const noexcept
248 : : {
249 : 229646 : 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 : 297727184 : size_t operator()(const COutPoint& id) const noexcept
254 : : {
255 : 297727184 : 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 : 1256 : CCoinsViewCursor(const uint256& in_block_hash) : block_hash(in_block_hash) {}
281 : 1256 : 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 : 147563 : CoinsViewCacheCursor(size_t& dirty_count LIFETIMEBOUND,
318 : : CoinsCachePair& sentinel LIFETIMEBOUND,
319 : : CCoinsMap& map LIFETIMEBOUND,
320 : : bool will_erase) noexcept
321 [ + + ]: 147563 : : m_dirty_count(dirty_count), m_sentinel(sentinel), m_map(map), m_will_erase(will_erase) {}
322 : :
323 : 147563 : inline CoinsCachePair* Begin() const noexcept { return m_sentinel.second.Next(); }
324 [ + + ]: 1090507 : inline CoinsCachePair* End() const noexcept { return &m_sentinel; }
325 : :
326 : : //! Return the next entry after current, possibly erasing current
327 : 942944 : inline CoinsCachePair* NextAndMaybeErase(CoinsCachePair& current) noexcept
328 : : {
329 [ + - ]: 942944 : const auto next_entry{current.second.Next()};
330 [ + - + + ]: 1885888 : 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 [ + + ]: 942944 : if (!m_will_erase) {
334 [ + + ]: 94921 : if (current.second.coin.IsSpent()) {
335 [ - + - - ]: 22099 : assert(current.second.coin.DynamicMemoryUsage() == 0); // scriptPubKey was already cleared in SpendCoin
336 : 22099 : m_map.erase(current.first);
337 : : } else {
338 [ + - ]: 72822 : current.second.SetClean();
339 : : }
340 : : }
341 : 942944 : return next_entry;
342 : : }
343 : :
344 [ + + + + : 479939 : inline bool WillErase(CoinsCachePair& current) const noexcept { return m_will_erase || current.second.coin.IsSpent(); }
+ + + + ]
345 : 4007 : size_t GetDirtyCount() const noexcept { return m_dirty_count; }
346 [ + - ]: 4007 : 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 : 529352 : class CCoinsView
356 : : {
357 : : public:
358 : : //! As we use CCoinsViews polymorphically, have a virtual destructor
359 : 1405 : 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 [ - + ]: 527947 : explicit CCoinsViewBacked(CCoinsView* in_view) : base{Assert(in_view)} {}
422 : :
423 [ + - + - ]: 97220 : void SetBackend(CCoinsView& in_view) { base = &in_view; }
424 : :
425 : 921806 : std::optional<Coin> GetCoin(const COutPoint& outpoint) const override { return base->GetCoin(outpoint); }
426 : 437887 : 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 : 49564 : uint256 GetBestBlock() const override { return base->GetBestBlock(); }
429 : 0 : std::vector<uint256> GetHeadBlocks() const override { return base->GetHeadBlocks(); }
430 : 3724 : 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 : : //! Force a reallocation of the cache map. This is required when downsizing
442 : : //! the cache because the map's allocator may be hanging onto a lot of
443 : : //! memory despite having called .clear().
444 : : //!
445 : : //! See: https://stackoverflow.com/questions/42114044/how-to-release-unordered-map-memory
446 : : void ReallocateCache();
447 : :
448 : : /**
449 : : * @note this is marked const, but may actually append to `cacheCoins`, increasing
450 : : * memory usage.
451 : : */
452 : : CCoinsMap::iterator FetchCoin(const COutPoint &outpoint) const;
453 : :
454 : : protected:
455 : : /**
456 : : * Make mutable so that we can "fill the cache" even from Get-methods
457 : : * declared as "const".
458 : : */
459 : : mutable uint256 m_block_hash;
460 : : mutable CCoinsMapMemoryResource m_cache_coins_memory_resource{};
461 : : /* The starting sentinel of the flagged entry circular doubly linked list. */
462 : : mutable CoinsCachePair m_sentinel;
463 : : mutable CCoinsMap cacheCoins;
464 : :
465 : : /* Cached dynamic memory usage for the inner Coin objects. */
466 : : mutable size_t cachedCoinsUsage{0};
467 : : /* Running count of dirty Coin cache entries. */
468 : : mutable size_t m_dirty_count{0};
469 : :
470 : : /**
471 : : * Discard all modifications made to this cache without flushing to the base view.
472 : : * This can be used to efficiently reuse a cache instance across multiple operations.
473 : : */
474 : : virtual void Reset() noexcept;
475 : :
476 : : /* Fetch the coin from base. Used for cache misses in FetchCoin. */
477 : : virtual std::optional<Coin> FetchCoinFromBase(const COutPoint& outpoint) const;
478 : :
479 : : public:
480 : : CCoinsViewCache(CCoinsView* in_base, bool deterministic = false);
481 : :
482 : : /**
483 : : * By deleting the copy constructor, we prevent accidentally using it when one intends to create a cache on top of a base cache.
484 : : */
485 : : CCoinsViewCache(const CCoinsViewCache &) = delete;
486 : :
487 : : // Standard CCoinsView methods
488 : : std::optional<Coin> GetCoin(const COutPoint& outpoint) const override;
489 : : std::optional<Coin> PeekCoin(const COutPoint& outpoint) const override;
490 : : bool HaveCoin(const COutPoint& outpoint) const override;
491 : : uint256 GetBestBlock() const override;
492 : : void SetBestBlock(const uint256& block_hash);
493 : : void BatchWrite(CoinsViewCacheCursor& cursor, const uint256& block_hash) override;
494 : :
495 : : /**
496 : : * Check if we have the given utxo already loaded in this cache.
497 : : * The semantics are the same as HaveCoin(), but no calls to
498 : : * the backing CCoinsView are made.
499 : : */
500 : : bool HaveCoinInCache(const COutPoint &outpoint) const;
501 : :
502 : : /**
503 : : * Return a reference to Coin in the cache, or coinEmpty if not found. This is
504 : : * more efficient than GetCoin.
505 : : *
506 : : * Generally, do not hold the reference returned for more than a short scope.
507 : : * While the current implementation allows for modifications to the contents
508 : : * of the cache while holding the reference, this behavior should not be relied
509 : : * on! To be safe, best to not hold the returned reference through any other
510 : : * calls to this cache.
511 : : */
512 : : const Coin& AccessCoin(const COutPoint &output) const;
513 : :
514 : : /**
515 : : * Add a coin. Set possible_overwrite to true if an unspent version may
516 : : * already exist in the cache.
517 : : */
518 : : void AddCoin(const COutPoint& outpoint, Coin&& coin, bool possible_overwrite);
519 : :
520 : : /**
521 : : * Emplace a coin into cacheCoins without performing any checks, marking
522 : : * the emplaced coin as dirty.
523 : : *
524 : : * NOT FOR GENERAL USE. Used only when loading coins from a UTXO snapshot.
525 : : * @sa ChainstateManager::PopulateAndValidateSnapshot()
526 : : */
527 : : void EmplaceCoinInternalDANGER(const COutPoint& outpoint, Coin&& coin);
528 : :
529 : : /**
530 : : * Spend a coin. Pass moveto in order to get the deleted data.
531 : : * If no unspent output exists for the passed outpoint, this call
532 : : * has no effect.
533 : : */
534 : : bool SpendCoin(const COutPoint &outpoint, Coin* moveto = nullptr);
535 : :
536 : : /**
537 : : * Push the modifications applied to this cache to its base and wipe local state.
538 : : * Failure to call this method or Sync() before destruction will cause the changes
539 : : * to be forgotten.
540 : : * If reallocate_cache is false, the cache will retain the same memory footprint
541 : : * after flushing and should be destroyed to deallocate.
542 : : */
543 : : virtual void Flush(bool reallocate_cache = true);
544 : :
545 : : /**
546 : : * Push the modifications applied to this cache to its base while retaining
547 : : * the contents of this cache (except for spent coins, which we erase).
548 : : * Failure to call this method or Flush() before destruction will cause the changes
549 : : * to be forgotten.
550 : : */
551 : : void Sync();
552 : :
553 : : /**
554 : : * Removes the UTXO with the given outpoint from the cache, if it is
555 : : * not modified.
556 : : */
557 : : void Uncache(const COutPoint &outpoint);
558 : :
559 : : //! Size of the cache (in number of transaction outputs)
560 : : unsigned int GetCacheSize() const;
561 : :
562 : : //! Number of dirty cache entries (transaction outputs)
563 [ + - + - : 3704 : size_t GetDirtyCount() const noexcept { return m_dirty_count; }
+ - + - +
- ][ + - ]
564 : :
565 : : //! Calculate the size of the cache (in bytes)
566 : : size_t DynamicMemoryUsage() const;
567 : :
568 : : //! Check whether all prevouts of the transaction are present in the UTXO set represented by this view
569 : : bool HaveInputs(const CTransaction& tx) const;
570 : :
571 : : //! Run an internal sanity check on the cache data structure. */
572 : : void SanityCheck() const;
573 : :
574 : : class ResetGuard
575 : : {
576 : : private:
577 : : friend CCoinsViewCache;
578 : : CCoinsViewCache& m_cache;
579 : 135029 : explicit ResetGuard(CCoinsViewCache& cache LIFETIMEBOUND) noexcept : m_cache{cache} {}
580 : :
581 : : public:
582 : : ResetGuard(const ResetGuard&) = delete;
583 : : ResetGuard& operator=(const ResetGuard&) = delete;
584 : : ResetGuard(ResetGuard&&) = delete;
585 : : ResetGuard& operator=(ResetGuard&&) = delete;
586 : :
587 [ + - + - ]: 135029 : ~ResetGuard() { m_cache.Reset(); }
[ + - # # ]
588 : : };
589 : :
590 : : //! Create a scoped guard that will call `Reset()` on this cache when it goes out of scope.
591 [ + - ]: 135029 : [[nodiscard]] ResetGuard CreateResetGuard() noexcept { return ResetGuard{*this}; }
592 : : };
593 : :
594 : : /**
595 : : * CCoinsViewCache subclass that asynchronously fetches most block input prevouts in parallel during ConnectBlock
596 : : * without mutating the base cache. This is achieved by fetching coins from the base view using PeekCoin() instead of
597 : : * GetCoin(), so intermediate CCoinsViewCache layers are not filled.
598 : : *
599 : : * Used during ConnectBlock() as an ephemeral, resettable top-level view that is flushed only on success, so invalid
600 : : * blocks don't pollute the underlying cache.
601 : : *
602 : : * While this class uses threads internally to fetch coins, externally it is only safe to call its methods from a
603 : : * single "main" thread. It assumes StartFetching, StopFetching, FetchCoinFromBase, Flush and Reset will all only be
604 : : * called from the main thread.
605 : : *
606 : : * When a block is passed to StartFetching, the inputs of the block are flattened into a vector of InputToFetch
607 : : * objects. StartFetching then submits worker tasks to a ThreadPool and keeps the returned futures alive until fetching
608 : : * is stopped.
609 : : *
610 : : * ProcessInput() atomically fetches and increments m_input_head, so each thread can only access a single element of the
611 : : * m_inputs vector at a time. Workers race to claim inputs, so they may fetch elements in any order. If the fetched
612 : : * index is greater than or equal to the size of m_inputs, no more inputs can be fetched and false is returned.
613 : : *
614 : : * The worker claims the InputToFetch at this index, fetches the coin with base->PeekCoin() and moves it into the
615 : : * InputToFetch object. The ready flag is then set with a release memory order. This allows the ready flag to be
616 : : * used as a memory fence, guaranteeing the coin being written to the object will have happened before another
617 : : * thread tests the flag with an acquire memory order.
618 : : * This assumes all base->PeekCoin() paths are safe for concurrent readers.
619 : : *
620 : : * The main thread is the only consumer of the fetched coins. FetchCoinFromBase is called when a coin is requested on
621 : : * the main thread and is not already in the cache. It checks whether the next unconsumed entry in m_inputs has the
622 : : * requested outpoint. On a match, m_input_tail is advanced and the entry's ready flag is waited on with an acquire
623 : : * memory order until a worker has finished fetching it. The coin is then moved out and returned.
624 : : *
625 : : * StopFetching() is called in Flush() and in Reset() (the per-block teardown) so workers stop before the block they
626 : : * reference goes away. It stops fetching by moving m_input_head to the end of m_inputs (so workers quickly exit),
627 : : * then waits for all futures to complete and clears the per-block state (m_inputs and the head/tail counters).
628 : : *
629 : : * Workers advance m_input_head to fetch inputs. Main thread advances m_input_tail to consume.
630 : : *
631 : : * Before workers start:
632 : : *
633 : : * m_input_head
634 : : * m_input_tail
635 : : * │
636 : : * ▼
637 : : * ┌─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┐
638 : : * m_inputs: │ waiting │ waiting │ waiting │ waiting │ waiting │ waiting │ waiting │ waiting │ waiting │
639 : : * │ │ │ │ │ │ │ │ │ │
640 : : * └─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┘
641 : : *
642 : : * After workers start:
643 : : *
644 : : * Worker 2 Worker 0 Worker 3 Worker 1 m_input_head
645 : : * │ │ │ │ │
646 : : * ▼ ▼ ▼ ▼ ▼
647 : : * ┌─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┐
648 : : * m_inputs: │ ready │ ready │fetching │ ready │fetching │fetching │fetching │ waiting │ waiting │
649 : : * │consumed │ ✓ │ ● │ ✓ │ ● │ ● │ ● │ │ │
650 : : * └─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┘
651 : : * ▲
652 : : * │
653 : : * m_input_tail
654 : : */
655 : : class CoinsViewOverlay : public CCoinsViewCache
656 : : {
657 : : private:
658 : : //! The latest input not yet being fetched. Workers atomically increment this when fetching.
659 : : std::atomic_uint32_t m_input_head{0};
660 : : //! The latest input not yet accessed by a consumer. Only the main thread increments this.
661 : : mutable uint32_t m_input_tail{0};
662 : :
663 : : //! The inputs of the block which is being fetched.
664 : 70666 : struct InputToFetch {
665 : : //! Workers set this after setting the coin. The main thread tests this before reading the coin.
666 : : std::atomic_flag ready{};
667 : : //! The outpoint of the input to fetch.
668 : : const COutPoint& outpoint;
669 : : //! The coin that workers will fetch and main thread will insert into cache.
670 : : //! Mutable so it can be moved in FetchCoinFromBase.
671 : : mutable std::optional<Coin> coin{std::nullopt};
672 : :
673 : 55917 : explicit InputToFetch(const COutPoint& o LIFETIMEBOUND) noexcept : outpoint{o} {}
674 : :
675 : : //! Move ctor is required for resizing m_inputs in StartFetching. Elements will never move once parallel tasks
676 : : //! are started, so we can assert that coin is nullopt and ready is false.
677 : 14749 : InputToFetch(InputToFetch&& other) noexcept : outpoint{other.outpoint}
678 : : {
679 [ - + ]: 14749 : Assert(!other.coin);
680 [ - + ]: 14749 : Assert(!other.ready.test(std::memory_order_relaxed));
681 : 14749 : }
682 : : };
683 : : //! Must only be mutated when m_futures is empty. Elements may be mutated when m_futures is not empty.
684 : : std::vector<InputToFetch> m_inputs{};
685 : :
686 : : /**
687 : : * Claim and fetch the next input in the queue.
688 : : *
689 : : * @return true if an input prevout was fetched
690 : : * @return false if there are no more input prevouts in the queue to fetch
691 : : */
692 : 81775 : bool ProcessInput() noexcept
693 : : {
694 [ - + ]: 81775 : const auto i{m_input_head.fetch_add(1, std::memory_order_relaxed)};
695 [ - + + + ]: 81775 : if (i >= m_inputs.size()) return false;
696 : :
697 : 55822 : auto& input{m_inputs[i]};
698 : 55822 : input.coin = base->PeekCoin(input.outpoint);
699 : : // Use release so writing coin above happens before the main thread acquires.
700 [ - + ]: 55822 : Assert(!input.ready.test_and_set(std::memory_order_release));
701 : 55822 : input.ready.notify_one();
702 : 55822 : return true;
703 : : }
704 : :
705 : : //! Stop all worker threads and clear fetching data.
706 : : //! Calling this is idempotent, and may safely be called if not fetching.
707 : 268652 : void StopFetching() noexcept
708 : : {
709 [ + + ]: 268652 : if (m_futures.empty()) {
710 [ - + ]: 259068 : Assert(m_inputs.empty());
711 [ - + ]: 259068 : Assert(m_input_head.load(std::memory_order_relaxed) == 0);
712 [ - + ]: 259068 : Assert(m_input_tail == 0);
713 : : return;
714 : : }
715 : : // Skip fetching the rest of the inputs by moving the head to the end.
716 [ - + ]: 9584 : m_input_head.store(m_inputs.size(), std::memory_order_relaxed);
717 : : // Wait for all threads to stop.
718 [ + + ]: 35537 : for (auto& future : m_futures) future.wait();
719 : 9584 : m_futures.clear();
720 : 9584 : m_inputs.clear();
721 : 9584 : m_input_head.store(0, std::memory_order_relaxed);
722 : 9584 : m_input_tail = 0;
723 : : }
724 : :
725 : 497567 : std::optional<Coin> FetchCoinFromBase(const COutPoint& outpoint) const override
726 : : {
727 : : // This assumes ConnectBlock accesses all inputs in the same order as
728 : : // they are added to m_inputs in StartFetching.
729 [ - + + + : 497567 : if (m_input_tail < m_inputs.size() && m_inputs[m_input_tail].outpoint == outpoint) {
+ + ]
730 : : // We advance the tail since the input is cached and not accessed through this method again.
731 : 55724 : auto& input{m_inputs[m_input_tail++]};
732 : : // Wait until the coin is ready to be read. We need acquire so we match the worker thread's release.
733 : 55724 : input.ready.wait(/*old=*/false, std::memory_order_acquire);
734 : : // We can move the coin since we won't access this input again.
735 : 55724 : return std::move(input.coin);
736 : : }
737 : :
738 : : // We will only get here for BIP30 checks, an invalid block, or if the threadpool has not been started.
739 : 441843 : return base->PeekCoin(outpoint);
740 : : }
741 : :
742 : : //! Non-null. May have zero workers when input fetching is disabled.
743 : : std::shared_ptr<ThreadPool> m_thread_pool;
744 : : std::vector<std::future<void>> m_futures{};
745 : :
746 : : protected:
747 : : //! StopFetching must be called here for two reasons: InputToFetch objects hold references to the
748 : : //! block's outpoints, so they must not outlive the block being connected; and when connecting a
749 : : //! block fails, workers must not keep fetching inputs for the block that was abandoned.
750 : 135027 : void Reset() noexcept override
751 : : {
752 : 135027 : StopFetching();
753 : 135027 : CCoinsViewCache::Reset();
754 : 135027 : }
755 : :
756 : : public:
757 : 1389 : explicit CoinsViewOverlay(CCoinsView* in_base, std::shared_ptr<ThreadPool> thread_pool,
758 : : bool deterministic = false) noexcept
759 [ - + ]: 1389 : : CCoinsViewCache{in_base, deterministic}, m_thread_pool{std::move(thread_pool)}
760 : : {
761 [ - + ]: 1389 : Assert(m_thread_pool);
762 : 1389 : }
763 : :
764 [ + - ]: 4158 : ~CoinsViewOverlay() noexcept override { StopFetching(); }
765 : :
766 : : //! Start fetching inputs from block.
767 : : [[nodiscard]] ResetGuard StartFetching(const CBlock& block LIFETIMEBOUND) noexcept;
768 : :
769 : 132235 : void Flush(bool reallocate_cache = true) override
770 : : {
771 : 264470 : if (!Assume(AllInputsConsumed())) {
772 [ # # ]: 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());
773 : : }
774 : 132235 : StopFetching();
775 : 132235 : CCoinsViewCache::Flush(reallocate_cache);
776 : 132235 : }
777 : :
778 : : //! Swapping the backend or writing through to it with Sync() is not supported while fetching.
779 : : void SetBackend(CCoinsView&) = delete;
780 : : void Sync() = delete;
781 : :
782 : : //! Verify that all parallel fetched input prevouts have been consumed.
783 [ - + - + ]: 132235 : bool AllInputsConsumed() const noexcept { return m_input_tail == m_inputs.size(); }
784 : : };
785 : :
786 : : //! Utility function to add all of a transaction's outputs to a cache.
787 : : //! When check is false, this assumes that overwrites are only possible for coinbase transactions.
788 : : //! When check is true, the underlying view may be queried to determine whether an addition is
789 : : //! an overwrite.
790 : : // TODO: pass in a boolean to limit these possible overwrites to known
791 : : // (pre-BIP34) cases.
792 : : void AddCoins(CCoinsViewCache& cache, const CTransaction& tx, int nHeight, bool check = false);
793 : :
794 : : //! Utility function to find any unspent output with a given txid.
795 : : //! This function can be quite expensive because in the event of a transaction
796 : : //! which is not found in the cache, it can cause up to MAX_OUTPUTS_PER_BLOCK
797 : : //! lookups to database, so it should be used with care.
798 : : const Coin& AccessByTxid(const CCoinsViewCache& cache, const Txid& txid);
799 : :
800 : : /**
801 : : * This is a minimally invasive approach to shutdown on LevelDB read errors from the
802 : : * chainstate, while keeping user interface out of the common library, which is shared
803 : : * between bitcoind, and bitcoin-qt and non-server tools.
804 : : *
805 : : * Writes do not need similar protection, as failure to write is handled by the caller.
806 : : */
807 : : class CCoinsViewErrorCatcher final : public CCoinsViewBacked
808 : : {
809 : : public:
810 [ + - ]: 1380 : explicit CCoinsViewErrorCatcher(CCoinsView* view) : CCoinsViewBacked(view) {}
811 : :
812 : 1136 : void AddReadErrCallback(std::function<void()> f) {
813 [ + - ]: 1136 : m_err_callbacks.emplace_back(std::move(f));
814 : 1136 : }
815 : :
816 : : std::optional<Coin> GetCoin(const COutPoint& outpoint) const override;
817 : : bool HaveCoin(const COutPoint& outpoint) const override;
818 : : std::optional<Coin> PeekCoin(const COutPoint& outpoint) const override;
819 : :
820 : : private:
821 : : /** A list of callbacks to execute upon leveldb read error. */
822 : : std::vector<std::function<void()>> m_err_callbacks;
823 : :
824 : : };
825 : :
826 : : #endif // BITCOIN_COINS_H
|
