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
18TRACEPOINT_SEMAPHORE(utxocache, add);
19TRACEPOINT_SEMAPHORE(utxocache, spent);
20TRACEPOINT_SEMAPHORE(utxocache, uncache);
21
22SaltedCoinsCacheHasher::SaltedCoinsCacheHasher(bool deterministic)
23    : m_hasher{
24          deterministic ? 0x8e819f2607a18de6 : FastRandomContext().rand64(),
25          deterministic ? 0xf4020d2e3983b0eb : FastRandomContext().rand64()}
26{
27}
28
29CoinsViewEmpty& CoinsViewEmpty::Get()
30{
31    static CoinsViewEmpty instance;
32    return instance;
33}
34
35std::optional<Coin> CCoinsViewCache::PeekCoin(const COutPoint& outpoint) const
36{
37    if (auto it{cacheCoins.find(outpoint)}; it != cacheCoins.end()) {
38        return it->second.coin.IsSpent() ? std::nullopt : std::optional{it->second.coin};
39    }
40    return base->PeekCoin(outpoint);
41}
42
43CCoinsViewCache::CCoinsViewCache(CCoinsView* in_base, bool deterministic) :
44    CCoinsViewBacked(in_base), m_deterministic(deterministic),
45    cacheCoins(0, SaltedCoinsCacheHasher{/*deterministic=*/deterministic}, CCoinsMap::key_equal{}, &m_cache_coins_memory_resource)
46{
47    m_sentinel.second.SelfRef(m_sentinel);
48}
49
50size_t CCoinsViewCache::DynamicMemoryUsage() const {
51    return memusage::DynamicUsage(cacheCoins) + cachedCoinsUsage;
52}
53
54std::optional<Coin> CCoinsViewCache::FetchCoinFromBase(const COutPoint& outpoint) const
55{
56    return base->GetCoin(outpoint);
57}
58
59CCoinsMap::iterator CCoinsViewCache::FetchCoin(const COutPoint &outpoint) const {
60    const auto [ret, inserted] = cacheCoins.try_emplace(outpoint);
61    if (inserted) {
62        if (auto coin{FetchCoinFromBase(outpoint)}) {
63            ret->second.coin = std::move(*coin);
64            cachedCoinsUsage += ret->second.coin.DynamicMemoryUsage();
65            Assert(!ret->second.coin.IsSpent());
66        } else {
67            cacheCoins.erase(ret);
68            return cacheCoins.end();
69        }
70    }
71    return ret;
72}
73
74std::optional<Coin> CCoinsViewCache::GetCoin(const COutPoint& outpoint) const
75{
76    if (auto it{FetchCoin(outpoint)}; it != cacheCoins.end() && !it->second.coin.IsSpent()) return it->second.coin;
77    return std::nullopt;
78}
79
80void CCoinsViewCache::AddCoin(const COutPoint &outpoint, Coin&& coin, bool possible_overwrite) {
81    assert(!coin.IsSpent());
82    if (coin.out.scriptPubKey.IsUnspendable()) return;
83    CCoinsMap::iterator it;
84    bool inserted;
85    std::tie(it, inserted) = cacheCoins.emplace(std::piecewise_construct, std::forward_as_tuple(outpoint), std::tuple<>());
86    bool fresh = false;
87    if (!possible_overwrite) {
88        if (!it->second.coin.IsSpent()) {
89            throw std::logic_error("Attempted to overwrite an unspent coin (when possible_overwrite is false)");
90        }
91        // If the coin exists in this cache as a spent coin and is DIRTY, then
92        // its spentness hasn't been flushed to the parent cache. We're
93        // re-adding the coin to this cache now but we can't mark it as FRESH.
94        // If we mark it FRESH and then spend it before the cache is flushed
95        // we would remove it from this cache and would never flush spentness
96        // to the parent cache.
97        //
98        // Re-adding a spent coin can happen in the case of a re-org (the coin
99        // is 'spent' when the block adding it is disconnected and then
100        // re-added when it is also added in a newly connected block).
101        //
102        // If the coin doesn't exist in the current cache, or is spent but not
103        // DIRTY, then it can be marked FRESH.
104        fresh = !it->second.IsDirty();
105    }
106    if (!inserted) {
107        Assume(TrySub(m_dirty_count, it->second.IsDirty()));
108        Assume(TrySub(cachedCoinsUsage, it->second.coin.DynamicMemoryUsage()));
109    }
110    it->second.coin = std::move(coin);
111    CCoinsCacheEntry::SetDirty(*it, m_sentinel);
112    ++m_dirty_count;
113    if (fresh) CCoinsCacheEntry::SetFresh(*it, m_sentinel);
114    cachedCoinsUsage += it->second.coin.DynamicMemoryUsage();
115    TRACEPOINT(utxocache, add,
116           outpoint.hash.data(),
117           (uint32_t)outpoint.n,
118           (uint32_t)it->second.coin.nHeight,
119           (int64_t)it->second.coin.out.nValue,
120           (bool)it->second.coin.IsCoinBase());
121}
122
123void CCoinsViewCache::EmplaceCoinInternalDANGER(const COutPoint& outpoint, Coin&& coin) {
124    const auto mem_usage{coin.DynamicMemoryUsage()};
125    auto [it, inserted] = cacheCoins.try_emplace(outpoint, std::move(coin));
126    if (inserted) {
127        CCoinsCacheEntry::SetDirty(*it, m_sentinel);
128        ++m_dirty_count;
129        cachedCoinsUsage += mem_usage;
130    }
131}
132
133void AddCoins(CCoinsViewCache& cache, const CTransaction &tx, int nHeight, bool check_for_overwrite) {
134    bool fCoinbase = tx.IsCoinBase();
135    const Txid& txid = tx.GetHash();
136    for (size_t i = 0; i < tx.vout.size(); ++i) {
137        bool overwrite = check_for_overwrite ? cache.HaveCoin(COutPoint(txid, i)) : fCoinbase;
138        // Coinbase transactions can always be overwritten, in order to correctly
139        // deal with the pre-BIP30 occurrences of duplicate coinbase transactions.
140        cache.AddCoin(COutPoint(txid, i), Coin(tx.vout[i], nHeight, fCoinbase), overwrite);
141    }
142}
143
144bool CCoinsViewCache::SpendCoin(const COutPoint &outpoint, Coin* moveout) {
145    CCoinsMap::iterator it = FetchCoin(outpoint);
146    if (it == cacheCoins.end()) return false;
147    Assume(TrySub(m_dirty_count, it->second.IsDirty()));
148    Assume(TrySub(cachedCoinsUsage, it->second.coin.DynamicMemoryUsage()));
149    TRACEPOINT(utxocache, spent,
150           outpoint.hash.data(),
151           (uint32_t)outpoint.n,
152           (uint32_t)it->second.coin.nHeight,
153           (int64_t)it->second.coin.out.nValue,
154           (bool)it->second.coin.IsCoinBase());
155    if (moveout) {
156        *moveout = std::move(it->second.coin);
157    }
158    if (it->second.IsFresh()) {
159        cacheCoins.erase(it);
160    } else {
161        CCoinsCacheEntry::SetDirty(*it, m_sentinel);
162        ++m_dirty_count;
163        it->second.coin.Clear();
164    }
165    return true;
166}
167
168static const Coin coinEmpty;
169
170const Coin& CCoinsViewCache::AccessCoin(const COutPoint &outpoint) const {
171    CCoinsMap::const_iterator it = FetchCoin(outpoint);
172    if (it == cacheCoins.end()) {
173        return coinEmpty;
174    } else {
175        return it->second.coin;
176    }
177}
178
179bool CCoinsViewCache::HaveCoin(const COutPoint& outpoint) const
180{
181    CCoinsMap::const_iterator it = FetchCoin(outpoint);
182    return (it != cacheCoins.end() && !it->second.coin.IsSpent());
183}
184
185bool CCoinsViewCache::HaveCoinInCache(const COutPoint &outpoint) const {
186    CCoinsMap::const_iterator it = cacheCoins.find(outpoint);
187    return (it != cacheCoins.end() && !it->second.coin.IsSpent());
188}
189
190uint256 CCoinsViewCache::GetBestBlock() const {
191    if (m_block_hash.IsNull())
192        m_block_hash = base->GetBestBlock();
193    return m_block_hash;
194}
195
196void CCoinsViewCache::SetBestBlock(const uint256& in_block_hash)
197{
198    m_block_hash = in_block_hash;
199}
200
201void CCoinsViewCache::BatchWrite(CoinsViewCacheCursor& cursor, const uint256& in_block_hash)
202{
203    for (auto it{cursor.Begin()}; it != cursor.End(); it = cursor.NextAndMaybeErase(*it)) {
204        if (!it->second.IsDirty()) { // TODO a cursor can only contain dirty entries
205            continue;
206        }
207        auto [itUs, inserted]{cacheCoins.try_emplace(it->first)};
208        if (inserted) {
209            if (it->second.IsFresh() && it->second.coin.IsSpent()) {
210                cacheCoins.erase(itUs); // TODO fresh coins should have been removed at spend
211            } else {
212                // The parent cache does not have an entry, while the child cache does.
213                // Move the data up and mark it as dirty.
214                CCoinsCacheEntry& entry{itUs->second};
215                assert(entry.coin.DynamicMemoryUsage() == 0);
216                if (cursor.WillErase(*it)) {
217                    // Since this entry will be erased,
218                    // we can move the coin into us instead of copying it
219                    entry.coin = std::move(it->second.coin);
220                } else {
221                    entry.coin = it->second.coin;
222                }
223                CCoinsCacheEntry::SetDirty(*itUs, m_sentinel);
224                ++m_dirty_count;
225                cachedCoinsUsage += entry.coin.DynamicMemoryUsage();
226                // We can mark it FRESH in the parent if it was FRESH in the child
227                // Otherwise it might have just been flushed from the parent's cache
228                // and already exist in the grandparent
229                if (it->second.IsFresh()) CCoinsCacheEntry::SetFresh(*itUs, m_sentinel);
230            }
231        } else {
232            // Found the entry in the parent cache
233            if (it->second.IsFresh() && !itUs->second.coin.IsSpent()) {
234                // The coin was marked FRESH in the child cache, but the coin
235                // exists in the parent cache. If this ever happens, it means
236                // the FRESH flag was misapplied and there is a logic error in
237                // the calling code.
238                throw std::logic_error("FRESH flag misapplied to coin that exists in parent cache");
239            }
240
241            if (itUs->second.IsFresh() && it->second.coin.IsSpent()) {
242                // The grandparent cache does not have an entry, and the coin
243                // has been spent. We can just delete it from the parent cache.
244                Assume(TrySub(m_dirty_count, itUs->second.IsDirty()));
245                Assume(TrySub(cachedCoinsUsage, itUs->second.coin.DynamicMemoryUsage()));
246                cacheCoins.erase(itUs);
247            } else {
248                // A normal modification.
249                Assume(TrySub(cachedCoinsUsage, itUs->second.coin.DynamicMemoryUsage()));
250                if (cursor.WillErase(*it)) {