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
35class CBlock;
36class 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 */
45class Coin
46{
47public:
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    Coin(CTxOut&& outIn, int nHeightIn, bool fCoinBaseIn) : out(std::move(outIn)), fCoinBase(fCoinBaseIn), nHeight(nHeightIn) {}
59    Coin(const CTxOut& outIn, int nHeightIn, bool fCoinBaseIn) : out(outIn), fCoinBase(fCoinBaseIn),nHeight(nHeightIn) {}
60
61    void Clear() {
62        out.SetNull();
63        fCoinBase = false;
64        nHeight = 0;
65    }
66
67    //! empty constructor
68    Coin() : fCoinBase(false), nHeight(0) { }
69
70    bool IsCoinBase() const {
71        return fCoinBase;
72    }
73
74    template<typename Stream>
75    void Serialize(Stream &s) const {
76        assert(!IsSpent());
77        uint32_t code{(uint32_t{nHeight} << 1) | uint32_t{fCoinBase}};
78        ::Serialize(s, VARINT(code));
79        ::Serialize(s, Using<TxOutCompression>(out));
80    }
81
82    template<typename Stream>
83    void Unserialize(Stream &s) {
84        uint32_t code = 0;
85        ::Unserialize(s, VARINT(code));
86        nHeight = code >> 1;
87        fCoinBase = code & 1;
88        ::Unserialize(s, Using<TxOutCompression>(out));
89    }
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    bool IsSpent() const {
95        return out.IsNull();
96    }
97
98    size_t DynamicMemoryUsage() const {
99        return memusage::DynamicUsage(out.scriptPubKey);
100    }
101};
102
103struct CCoinsCacheEntry;
104using 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 */
120struct CCoinsCacheEntry
121{
122private:
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    static void AddFlags(uint8_t flags, CoinsCachePair& pair, CoinsCachePair& sentinel) noexcept
139    {
140        Assume(flags & (DIRTY | FRESH));
141        if (!pair.second.m_flags) {
142            Assume(!pair.second.m_prev && !pair.second.m_next);
143            pair.second.m_prev = sentinel.second.m_prev;
144            pair.second.m_next = &sentinel;
145            sentinel.second.m_prev = &pair;
146            pair.second.m_prev->second.m_next = &pair;
147        }
148        Assume(pair.second.m_prev && pair.second.m_next);
149        pair.second.m_flags |= flags;
150    }
151
152public:
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    CCoinsCacheEntry() noexcept = default;
177    explicit CCoinsCacheEntry(Coin&& coin_) noexcept : coin(std::move(coin_)) {}
178    ~CCoinsCacheEntry()
179    {
180        SetClean();
181    }
182
183    static void SetDirty(CoinsCachePair& pair, CoinsCachePair& sentinel) noexcept { AddFlags(DIRTY, pair, sentinel); }
184    static void SetFresh(CoinsCachePair& pair, CoinsCachePair& sentinel) noexcept { AddFlags(FRESH, pair, sentinel); }
185
186    void SetClean() noexcept
187    {
188        if (!m_flags) return;
189        m_next->second.m_prev = m_prev;
190        m_prev->second.m_next = m_next;
191        m_flags = 0;
192        m_prev = m_next = nullptr;
193    }
194    bool IsDirty() const noexcept { return m_flags & DIRTY; }
195    bool IsFresh() const noexcept { return m_flags & FRESH; }
196
197    //! Only call Next when this entry is DIRTY, FRESH, or both
198    CoinsCachePair* Next() const noexcept
199    {
200        Assume(m_flags);
201        return m_next;
202    }
203
204    //! Only call Prev when this entry is DIRTY, FRESH, or both
205    CoinsCachePair* Prev() const noexcept
206    {
207        Assume(m_flags);
208        return m_prev;
209    }
210
211    //! Only use this for initializing the linked list sentinel
212    void SelfRef(CoinsCachePair& pair) noexcept
213    {
214        Assume(&pair.second == this);
215        m_prev = &pair;
216        m_next = &pair;
217        // Set sentinel to DIRTY so we can call Next on it
218        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 */
239class SaltedCoinsCacheHasher
240{
241    const SipHasher13UJ m_hasher;
242
243public:
244    SaltedCoinsCacheHasher(bool deterministic = false);
245
246    /** Hash a transaction ID, itself a cryptographic hash, as one jumbo block. */
247    size_t operator()(const Txid& id) const noexcept
248    {
249        return m_hasher.Hash(id.ToUint256());
250    }