1 // Copyright (c) 2012-present The Bitcoin Core developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 5 #include <coins.h>
6 7 #include <consensus/consensus.h>
8 #include <primitives/block.h>
9 #include <random.h>
10 #include <uint256.h>
11 #include <util/log.h>
12 #include <util/threadpool.h>
13 #include <util/trace.h>
14 15 #include <ranges>
16 #include <unordered_set>
17 18 TRACEPOINT_SEMAPHORE(utxocache, add);
19 TRACEPOINT_SEMAPHORE(utxocache, spent);
20 TRACEPOINT_SEMAPHORE(utxocache, uncache);
21 22 CoinsViewEmpty& CoinsViewEmpty::Get()
23 {
24 static CoinsViewEmpty instance;
25 return instance;
26 }
27 28 std::optional<Coin> CCoinsViewCache::PeekCoin(const COutPoint& outpoint) const
29 {
30 if (auto it{cacheCoins.find(outpoint)}; it != cacheCoins.end()) {
31 return it->second.coin.IsSpent() ? std::nullopt : std::optional{it->second.coin};
32 }
33 return base->PeekCoin(outpoint);
34 }
35 36 CCoinsViewCache::CCoinsViewCache(CCoinsView* in_base, bool deterministic) :
37 CCoinsViewBacked(in_base), m_deterministic(deterministic),
38 cacheCoins(0, SaltedOutpointHasher(/*deterministic=*/deterministic), CCoinsMap::key_equal{}, &m_cache_coins_memory_resource)
39 {
40 m_sentinel.second.SelfRef(m_sentinel);
41 }
42 43 size_t CCoinsViewCache::DynamicMemoryUsage() const {
44 return memusage::DynamicUsage(cacheCoins) + cachedCoinsUsage;
45 }
46 47 std::optional<Coin> CCoinsViewCache::FetchCoinFromBase(const COutPoint& outpoint) const
48 {
49 return base->GetCoin(outpoint);
50 }
51 52 CCoinsMap::iterator CCoinsViewCache::FetchCoin(const COutPoint &outpoint) const {
53 const auto [ret, inserted] = cacheCoins.try_emplace(outpoint);
54 if (inserted) {
55 if (auto coin{FetchCoinFromBase(outpoint)}) {
56 ret->second.coin = std::move(*coin);
57 cachedCoinsUsage += ret->second.coin.DynamicMemoryUsage();
58 Assert(!ret->second.coin.IsSpent());
59 } else {
60 cacheCoins.erase(ret);
61 return cacheCoins.end();
62 }
63 }
64 return ret;
65 }
66 67 std::optional<Coin> CCoinsViewCache::GetCoin(const COutPoint& outpoint) const
68 {
69 if (auto it{FetchCoin(outpoint)}; it != cacheCoins.end() && !it->second.coin.IsSpent()) return it->second.coin;
70 return std::nullopt;
71 }
72 73 void CCoinsViewCache::AddCoin(const COutPoint &outpoint, Coin&& coin, bool possible_overwrite) {
74 assert(!coin.IsSpent());
75 if (coin.out.scriptPubKey.IsUnspendable()) return;
76 CCoinsMap::iterator it;
77 bool inserted;
78 std::tie(it, inserted) = cacheCoins.emplace(std::piecewise_construct, std::forward_as_tuple(outpoint), std::tuple<>());
79 bool fresh = false;
80 if (!possible_overwrite) {
81 if (!it->second.coin.IsSpent()) {
82 throw std::logic_error("Attempted to overwrite an unspent coin (when possible_overwrite is false)");
83 }
84 // If the coin exists in this cache as a spent coin and is DIRTY, then
85 // its spentness hasn't been flushed to the parent cache. We're
86 // re-adding the coin to this cache now but we can't mark it as FRESH.
87 // If we mark it FRESH and then spend it before the cache is flushed
88 // we would remove it from this cache and would never flush spentness
89 // to the parent cache.
90 //
91 // Re-adding a spent coin can happen in the case of a re-org (the coin
92 // is 'spent' when the block adding it is disconnected and then
93 // re-added when it is also added in a newly connected block).
94 //
95 // If the coin doesn't exist in the current cache, or is spent but not
96 // DIRTY, then it can be marked FRESH.
97 fresh = !it->second.IsDirty();
98 }
99 if (!inserted) {
100 Assume(TrySub(m_dirty_count, it->second.IsDirty()));
101 Assume(TrySub(cachedCoinsUsage, it->second.coin.DynamicMemoryUsage()));
102 }
103 it->second.coin = std::move(coin);
104 CCoinsCacheEntry::SetDirty(*it, m_sentinel);
105 ++m_dirty_count;
106 if (fresh) CCoinsCacheEntry::SetFresh(*it, m_sentinel);
107 cachedCoinsUsage += it->second.coin.DynamicMemoryUsage();
108 TRACEPOINT(utxocache, add,
109 outpoint.hash.data(),
110 (uint32_t)outpoint.n,
111 (uint32_t)it->second.coin.nHeight,
112 (int64_t)it->second.coin.out.nValue,
113 (bool)it->second.coin.IsCoinBase());
114 }
115 116 void CCoinsViewCache::EmplaceCoinInternalDANGER(COutPoint&& outpoint, Coin&& coin) {
117 const auto mem_usage{coin.DynamicMemoryUsage()};
118 auto [it, inserted] = cacheCoins.try_emplace(std::move(outpoint), std::move(coin));
119 if (inserted) {
120 CCoinsCacheEntry::SetDirty(*it, m_sentinel);
121 ++m_dirty_count;
122 cachedCoinsUsage += mem_usage;
123 }
124 }
125 126 void AddCoins(CCoinsViewCache& cache, const CTransaction &tx, int nHeight, bool check_for_overwrite) {
127 bool fCoinbase = tx.IsCoinBase();
128 const Txid& txid = tx.GetHash();
129 for (size_t i = 0; i < tx.vout.size(); ++i) {
130 bool overwrite = check_for_overwrite ? cache.HaveCoin(COutPoint(txid, i)) : fCoinbase;
131 // Coinbase transactions can always be overwritten, in order to correctly
132 // deal with the pre-BIP30 occurrences of duplicate coinbase transactions.
133 cache.AddCoin(COutPoint(txid, i), Coin(tx.vout[i], nHeight, fCoinbase), overwrite);
134 }
135 }
136 137 bool CCoinsViewCache::SpendCoin(const COutPoint &outpoint, Coin* moveout) {
138 CCoinsMap::iterator it = FetchCoin(outpoint);
139 if (it == cacheCoins.end()) return false;
140 Assume(TrySub(m_dirty_count, it->second.IsDirty()));
141 Assume(TrySub(cachedCoinsUsage, it->second.coin.DynamicMemoryUsage()));
142 TRACEPOINT(utxocache, spent,
143 outpoint.hash.data(),
144 (uint32_t)outpoint.n,
145 (uint32_t)it->second.coin.nHeight,
146 (int64_t)it->second.coin.out.nValue,
147 (bool)it->second.coin.IsCoinBase());
148 if (moveout) {
149 *moveout = std::move(it->second.coin);
150 }
151 if (it->second.IsFresh()) {
152 cacheCoins.erase(it);
153 } else {
154 CCoinsCacheEntry::SetDirty(*it, m_sentinel);
155 ++m_dirty_count;
156 it->second.coin.Clear();
157 }
158 return true;
159 }
160 161 static const Coin coinEmpty;
162 163 const Coin& CCoinsViewCache::AccessCoin(const COutPoint &outpoint) const {
164 CCoinsMap::const_iterator it = FetchCoin(outpoint);
165 if (it == cacheCoins.end()) {
166 return coinEmpty;
167 } else {
168 return it->second.coin;
169 }
170 }
171 172 bool CCoinsViewCache::HaveCoin(const COutPoint& outpoint) const
173 {
174 CCoinsMap::const_iterator it = FetchCoin(outpoint);
175 return (it != cacheCoins.end() && !it->second.coin.IsSpent());
176 }
177 178 bool CCoinsViewCache::HaveCoinInCache(const COutPoint &outpoint) const {
179 CCoinsMap::const_iterator it = cacheCoins.find(outpoint);
180 return (it != cacheCoins.end() && !it->second.coin.IsSpent());
181 }
182 183 uint256 CCoinsViewCache::GetBestBlock() const {
184 if (m_block_hash.IsNull())
185 m_block_hash = base->GetBestBlock();
186 return m_block_hash;
187 }
188 189 void CCoinsViewCache::SetBestBlock(const uint256& in_block_hash)
190 {
191 m_block_hash = in_block_hash;
192 }
193 194 void CCoinsViewCache::BatchWrite(CoinsViewCacheCursor& cursor, const uint256& in_block_hash)
195 {
196 for (auto it{cursor.Begin()}; it != cursor.End(); it = cursor.NextAndMaybeErase(*it)) {
197 if (!it->second.IsDirty()) { // TODO a cursor can only contain dirty entries
198 continue;
199 }
200 auto [itUs, inserted]{cacheCoins.try_emplace(it->first)};
201 if (inserted) {
202 if (it->second.IsFresh() && it->second.coin.IsSpent()) {
203 cacheCoins.erase(itUs); // TODO fresh coins should have been removed at spend
204 } else {
205 // The parent cache does not have an entry, while the child cache does.
206 // Move the data up and mark it as dirty.
207 CCoinsCacheEntry& entry{itUs->second};
208 assert(entry.coin.DynamicMemoryUsage() == 0);
209 if (cursor.WillErase(*it)) {
210 // Since this entry will be erased,
211 // we can move the coin into us instead of copying it
212 entry.coin = std::move(it->second.coin);
213 } else {
214 entry.coin = it->second.coin;
215 }
216 CCoinsCacheEntry::SetDirty(*itUs, m_sentinel);
217 ++m_dirty_count;
218 cachedCoinsUsage += entry.coin.DynamicMemoryUsage();
219 // We can mark it FRESH in the parent if it was FRESH in the child
220 // Otherwise it might have just been flushed from the parent's cache
221 // and already exist in the grandparent
222 if (it->second.IsFresh()) CCoinsCacheEntry::SetFresh(*itUs, m_sentinel);
223 }
224 } else {
225 // Found the entry in the parent cache
226 if (it->second.IsFresh() && !itUs->second.coin.IsSpent()) {
227 // The coin was marked FRESH in the child cache, but the coin
228 // exists in the parent cache. If this ever happens, it means
229 // the FRESH flag was misapplied and there is a logic error in
230 // the calling code.
231 throw std::logic_error("FRESH flag misapplied to coin that exists in parent cache");
232 }
233 234 if (itUs->second.IsFresh() && it->second.coin.IsSpent()) {
235 // The grandparent cache does not have an entry, and the coin
236 // has been spent. We can just delete it from the parent cache.
237 Assume(TrySub(m_dirty_count, itUs->second.IsDirty()));
238 Assume(TrySub(cachedCoinsUsage, itUs->second.coin.DynamicMemoryUsage()));
239 cacheCoins.erase(itUs);
240 } else {
241 // A normal modification.
242 Assume(TrySub(cachedCoinsUsage, itUs->second.coin.DynamicMemoryUsage()));
243 if (cursor.WillErase(*it)) {
244 // Since this entry will be erased,
245 // we can move the coin into us instead of copying it
246 itUs->second.coin = std::move(it->second.coin);
247 } else {
248 itUs->second.coin = it->second.coin;
249 }
250 cachedCoinsUsage += itUs->second.coin.DynamicMemoryUsage();
251 if (!itUs->second.IsDirty()) {
252 CCoinsCacheEntry::SetDirty(*itUs, m_sentinel);
253 ++m_dirty_count;
254 }
255 // NOTE: It isn't safe to mark the coin as FRESH in the parent
256 // cache. If it already existed and was spent in the parent
257 // cache then marking it FRESH would prevent that spentness
258 // from being flushed to the grandparent.
259 }
260 }
261 }
262 SetBestBlock(in_block_hash);
263 }
264 265 void CCoinsViewCache::Flush(bool reallocate_cache)
266 {
267 auto cursor{CoinsViewCacheCursor(m_dirty_count, m_sentinel, cacheCoins, /*will_erase=*/true)};
268 base->BatchWrite(cursor, m_block_hash);
269 Assume(m_dirty_count == 0);
270 cacheCoins.clear();
271 if (reallocate_cache) {
272 ReallocateCache();
273 }
274 cachedCoinsUsage = 0;
275 }
276 277 void CCoinsViewCache::Sync()
278 {
279 auto cursor{CoinsViewCacheCursor(m_dirty_count, m_sentinel, cacheCoins, /*will_erase=*/false)};
280 base->BatchWrite(cursor, m_block_hash);
281 Assume(m_dirty_count == 0);
282 if (m_sentinel.second.Next() != &m_sentinel) {
283 /* BatchWrite must clear flags of all entries */
284 throw std::logic_error("Not all unspent flagged entries were cleared");
285 }
286 }
287 288 void CCoinsViewCache::Reset() noexcept
289 {
290 cacheCoins.clear();
291 cachedCoinsUsage = 0;
292 m_dirty_count = 0;
293 SetBestBlock(uint256::ZERO);
294 }
295 296 void CCoinsViewCache::Uncache(const COutPoint& hash)
297 {
298 CCoinsMap::iterator it = cacheCoins.find(hash);
299 if (it != cacheCoins.end() && !it->second.IsDirty()) {
300 Assume(TrySub(cachedCoinsUsage, it->second.coin.DynamicMemoryUsage()));
301 TRACEPOINT(utxocache, uncache,
302 hash.hash.data(),
303 (uint32_t)hash.n,
304 (uint32_t)it->second.coin.nHeight,
305 (int64_t)it->second.coin.out.nValue,
306 (bool)it->second.coin.IsCoinBase());
307 cacheCoins.erase(it);
308 }
309 }
310 311 unsigned int CCoinsViewCache::GetCacheSize() const {
312 return cacheCoins.size();
313 }
314 315 bool CCoinsViewCache::HaveInputs(const CTransaction& tx) const
316 {
317 if (!tx.IsCoinBase()) {
318 for (unsigned int i = 0; i < tx.vin.size(); i++) {
319 if (!HaveCoin(tx.vin[i].prevout)) {
320 return false;
321 }
322 }
323 }
324 return true;
325 }
326 327 void CCoinsViewCache::ReallocateCache()
328 {
329 // Cache should be empty when we're calling this.
330 assert(cacheCoins.size() == 0);
331 cacheCoins.~CCoinsMap();
332 m_cache_coins_memory_resource.~CCoinsMapMemoryResource();
333 ::new (&m_cache_coins_memory_resource) CCoinsMapMemoryResource{};
334 ::new (&cacheCoins) CCoinsMap{0, SaltedOutpointHasher{/*deterministic=*/m_deterministic}, CCoinsMap::key_equal{}, &m_cache_coins_memory_resource};
335 }
336 337 void CCoinsViewCache::SanityCheck() const
338 {
339 size_t recomputed_usage = 0;
340 size_t count_dirty = 0;
341 for (const auto& [_, entry] : cacheCoins) {
342 if (entry.coin.IsSpent()) {
343 assert(entry.IsDirty() && !entry.IsFresh()); // A spent coin must be dirty and cannot be fresh
344 } else {
345 assert(entry.IsDirty() || !entry.IsFresh()); // An unspent coin must not be fresh if not dirty
346 }
347 348 // Recompute cachedCoinsUsage.
349 recomputed_usage += entry.coin.DynamicMemoryUsage();
350 351 // Count the number of entries we expect in the linked list.
352 if (entry.IsDirty()) ++count_dirty;
353 }
354 // Iterate over the linked list of flagged entries.
355 size_t count_linked = 0;
356 for (auto it = m_sentinel.second.Next(); it != &m_sentinel; it = it->second.Next()) {
357 // Verify linked list integrity.
358 assert(it->second.Next()->second.Prev() == it);
359 assert(it->second.Prev()->second.Next() == it);
360 // Verify they are actually flagged.
361 assert(it->second.IsDirty());
362 // Count the number of entries actually in the list.
363 ++count_linked;
364 }
365 assert(count_dirty == count_linked && count_dirty == m_dirty_count);
366 assert(recomputed_usage == cachedCoinsUsage);
367 }
368 369 CCoinsViewCache::ResetGuard CoinsViewOverlay::StartFetching(const CBlock& block LIFETIMEBOUND) noexcept
370 {
371 Assert(m_futures.empty());
372 Assert(m_inputs.empty());
373 Assert(m_input_head.load(std::memory_order_relaxed) == 0);
374 Assert(m_input_tail == 0);
375 if (const auto workers_count{m_thread_pool->WorkersCount()}; workers_count > 0) {
376 // Loop through the block inputs and set their prevouts in the queue.
377 // Filter inputs that spend outputs created earlier in the same block. These outputs will be created
378 // directly in the cache from the tx that creates them, so they will not be requested from a base view.
379 std::unordered_set<Txid, SaltedTxidHasher> earlier_txids;
380 earlier_txids.reserve(block.vtx.size());
381 for (const auto& tx : block.vtx | std::views::drop(1)) {
382 for (const auto& input : tx->vin) {
383 if (!earlier_txids.contains(input.prevout.hash)) m_inputs.emplace_back(input.prevout);
384 }
385 earlier_txids.emplace(tx->GetHash());
386 }
387 // Only submit tasks if we have something to fetch.
388 if (m_inputs.size()) {
389 std::vector<std::function<void()>> tasks(workers_count, [this] {
390 while (ProcessInput()) {}
391 });
392 if (auto futures{m_thread_pool->Submit(std::move(tasks))}) {
393 m_futures = std::move(*futures);
394 } else {
395 // Submit can fail if a shared owner of the thread pool outside of this class calls Stop() or
396 // Interrupt() on a different thread after we call WorkersCount() above. In that case parallel
397 // fetching will not make progress, so we clear the inputs to fall back to single threaded fetching.
398 LogWarning("Failed to submit prevout fetch tasks; falling back to single-threaded fetching for this block.");
399 m_inputs.clear();
400 StopFetching(); // Assert nothing changed if we failed to start tasks.
401 }
402 }
403 }
404 return CreateResetGuard();
405 }
406 407 static const uint64_t MIN_TRANSACTION_OUTPUT_WEIGHT{WITNESS_SCALE_FACTOR * ::GetSerializeSize(CTxOut())};
408 static const uint64_t MAX_OUTPUTS_PER_BLOCK{MAX_BLOCK_WEIGHT / MIN_TRANSACTION_OUTPUT_WEIGHT};
409 410 const Coin& AccessByTxid(const CCoinsViewCache& view, const Txid& txid)
411 {
412 COutPoint iter(txid, 0);
413 while (iter.n < MAX_OUTPUTS_PER_BLOCK) {
414 const Coin& alternate = view.AccessCoin(iter);
415 if (!alternate.IsSpent()) return alternate;
416 ++iter.n;
417 }
418 return coinEmpty;
419 }
420 421 template <typename ReturnType, typename Func>
422 static ReturnType ExecuteBackedWrapper(Func func, const std::vector<std::function<void()>>& err_callbacks)
423 {
424 try {
425 return func();
426 } catch(const std::runtime_error& e) {
427 for (const auto& f : err_callbacks) {
428 f();
429 }
430 LogError("Error reading from database: %s\n", e.what());
431 // Starting the shutdown sequence and returning false to the caller would be
432 // interpreted as 'entry not found' (as opposed to unable to read data), and
433 // could lead to invalid interpretation. Just exit immediately, as we can't
434 // continue anyway, and all writes should be atomic.
435 std::abort();
436 }
437 }
438 439 std::optional<Coin> CCoinsViewErrorCatcher::GetCoin(const COutPoint& outpoint) const
440 {
441 return ExecuteBackedWrapper<std::optional<Coin>>([&]() { return CCoinsViewBacked::GetCoin(outpoint); }, m_err_callbacks);
442 }
443 444 bool CCoinsViewErrorCatcher::HaveCoin(const COutPoint& outpoint) const
445 {
446 return ExecuteBackedWrapper<bool>([&]() { return CCoinsViewBacked::HaveCoin(outpoint); }, m_err_callbacks);
447 }
448 449 std::optional<Coin> CCoinsViewErrorCatcher::PeekCoin(const COutPoint& outpoint) const
450 {
451 return ExecuteBackedWrapper<std::optional<Coin>>([&]() { return CCoinsViewBacked::PeekCoin(outpoint); }, m_err_callbacks);
452 }
453