coins.h

Go to the documentation of this file.

// Copyright (c) 2009-2010 Satoshi Nakamoto
// Copyright (c) 2009-present The Bitcoin Core developers
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.
 
#ifndef BITCOIN_COINS_H
#define BITCOIN_COINS_H
 
#include <attributes.h>
#include <compressor.h>
#include <core_memusage.h>
#include <crypto/siphash.h>
#include <memusage.h>
#include <primitives/transaction.h>
#include <primitives/transaction_identifier.h>
#include <serialize.h>
#include <support/allocators/pool.h>
#include <uint256.h>
#include <util/check.h>
#include <util/log.h>
#include <util/overflow.h>
 
#include <cassert>
#include <cstdint>
 
#include <atomic>
#include <functional>
#include <future>
#include <memory>
#include <optional>
#include <unordered_map>
#include <utility>
#include <vector>
 
class CBlock;
class ThreadPool;

class Coin
{
public:
    CTxOut out;

    bool fCoinBase : 1;

    uint32_t nHeight : 31;

    Coin(CTxOut&& outIn, int nHeightIn, bool fCoinBaseIn) : out(std::move(outIn)), fCoinBase(fCoinBaseIn), nHeight(nHeightIn) {}
    Coin(const CTxOut& outIn, int nHeightIn, bool fCoinBaseIn) : out(outIn), fCoinBase(fCoinBaseIn),nHeight(nHeightIn) {}
 
    void Clear() {
        out.SetNull();
        fCoinBase = false;
        nHeight = 0;
    }

    Coin() : fCoinBase(false), nHeight(0) { }
 
    bool IsCoinBase() const {
        return fCoinBase;
    }
 
    template<typename Stream>
    void Serialize(Stream &s) const {
        assert(!IsSpent());
        uint32_t code{(uint32_t{nHeight} << 1) | uint32_t{fCoinBase}};
        ::Serialize(s, VARINT(code));
        ::Serialize(s, Using<TxOutCompression>(out));
    }
 
    template<typename Stream>
    void Unserialize(Stream &s) {
        uint32_t code = 0;
        ::Unserialize(s, VARINT(code));
        nHeight = code >> 1;
        fCoinBase = code & 1;
        ::Unserialize(s, Using<TxOutCompression>(out));
    }

    bool IsSpent() const {
        return out.IsNull();
    }
 
    size_t DynamicMemoryUsage() const {
        return memusage::DynamicUsage(out.scriptPubKey);
    }
};
 
struct CCoinsCacheEntry;
using CoinsCachePair = std::pair<const COutPoint, CCoinsCacheEntry>;

struct CCoinsCacheEntry
{
private:
    CoinsCachePair* m_prev{nullptr};
    CoinsCachePair* m_next{nullptr};
    uint8_t m_flags{0};

    static void AddFlags(uint8_t flags, CoinsCachePair& pair, CoinsCachePair& sentinel) noexcept
    {
        Assume(flags & (DIRTY | FRESH));
        if (!pair.second.m_flags) {
            Assume(!pair.second.m_prev && !pair.second.m_next);
            pair.second.m_prev = sentinel.second.m_prev;
            pair.second.m_next = &sentinel;
            sentinel.second.m_prev = &pair;
            pair.second.m_prev->second.m_next = &pair;
        }
        Assume(pair.second.m_prev && pair.second.m_next);
        pair.second.m_flags |= flags;
    }
 
public:
    Coin coin; // The actual cached data.
 
    enum Flags {
        DIRTY = (1 << 0),
        FRESH = (1 << 1),
    };
 
    CCoinsCacheEntry() noexcept = default;
    explicit CCoinsCacheEntry(Coin&& coin_) noexcept : coin(std::move(coin_)) {}
    ~CCoinsCacheEntry()
    {
        SetClean();
    }
 
    static void SetDirty(CoinsCachePair& pair, CoinsCachePair& sentinel) noexcept { AddFlags(DIRTY, pair, sentinel); }
    static void SetFresh(CoinsCachePair& pair, CoinsCachePair& sentinel) noexcept { AddFlags(FRESH, pair, sentinel); }
 
    void SetClean() noexcept
    {
        if (!m_flags) return;
        m_next->second.m_prev = m_prev;
        m_prev->second.m_next = m_next;
        m_flags = 0;
        m_prev = m_next = nullptr;
    }
    bool IsDirty() const noexcept { return m_flags & DIRTY; }
    bool IsFresh() const noexcept { return m_flags & FRESH; }

    CoinsCachePair* Next() const noexcept
    {
        Assume(m_flags);
        return m_next;
    }

    CoinsCachePair* Prev() const noexcept
    {
        Assume(m_flags);
        return m_prev;
    }

    void SelfRef(CoinsCachePair& pair) noexcept
    {
        Assume(&pair.second == this);
        m_prev = &pair;
        m_next = &pair;
        // Set sentinel to DIRTY so we can call Next on it
        m_flags = DIRTY;
    }
};

class SaltedCoinsCacheHasher
{
    const SipHasher13UJ m_hasher;
 
public:
    SaltedCoinsCacheHasher(bool deterministic = false);

    size_t operator()(const Txid& id) const noexcept
    {
        return m_hasher.Hash(id.ToUint256());
    }

    size_t operator()(const COutPoint& id) const noexcept
    {
        return m_hasher.Hash(id.hash.ToUint256(), uint64_t{id.n});
    }
};

using CCoinsMap = std::unordered_map<COutPoint,
                                     CCoinsCacheEntry,
                                     SaltedCoinsCacheHasher,
                                     std::equal_to<COutPoint>,
                                     PoolAllocator<CoinsCachePair,
                                                   sizeof(CoinsCachePair) + sizeof(void*) * 4>>;
 
using CCoinsMapMemoryResource = CCoinsMap::allocator_type::ResourceType;

class CCoinsViewCursor
{
public:
    CCoinsViewCursor(const uint256& in_block_hash) : block_hash(in_block_hash) {}
    virtual ~CCoinsViewCursor() = default;
 
    virtual bool GetKey(COutPoint &key) const = 0;
    virtual bool GetValue(Coin &coin) const = 0;
 
    virtual bool Valid() const = 0;
    virtual void Next() = 0;

    const uint256& GetBestBlock() const { return block_hash; }
private:
    uint256 block_hash;
};

struct CoinsViewCacheCursor
{
    CoinsViewCacheCursor(size_t& dirty_count LIFETIMEBOUND,
                         CoinsCachePair& sentinel LIFETIMEBOUND,
                         CCoinsMap& map LIFETIMEBOUND,
                         bool will_erase) noexcept
        : m_dirty_count(dirty_count), m_sentinel(sentinel), m_map(map), m_will_erase(will_erase) {}
 
    inline CoinsCachePair* Begin() const noexcept { return m_sentinel.second.Next(); }
    inline CoinsCachePair* End() const noexcept { return &m_sentinel; }

    inline CoinsCachePair* NextAndMaybeErase(CoinsCachePair& current) noexcept
    {
        const auto next_entry{current.second.Next()};
        Assume(TrySub(m_dirty_count, current.second.IsDirty()));
        // If we are not going to erase the cache, we must still erase spent entries.
        // Otherwise, clear the state of the entry.
        if (!m_will_erase) {
            if (current.second.coin.IsSpent()) {
                assert(current.second.coin.DynamicMemoryUsage() == 0); // scriptPubKey was already cleared in SpendCoin
                m_map.erase(current.first);
            } else {
                current.second.SetClean();
            }
        }
        return next_entry;
    }
 
    inline bool WillErase(CoinsCachePair& current) const noexcept { return m_will_erase || current.second.coin.IsSpent(); }
    size_t GetDirtyCount() const noexcept { return m_dirty_count; }
    size_t GetTotalCount() const noexcept { return m_map.size(); }
private:
    size_t& m_dirty_count;
    CoinsCachePair& m_sentinel;
    CCoinsMap& m_map;
    bool m_will_erase;
};

class CCoinsView
{
public:
    virtual ~CCoinsView() = default;

    virtual std::optional<Coin> GetCoin(const COutPoint& outpoint) const = 0;

    virtual std::optional<Coin> PeekCoin(const COutPoint& outpoint) const = 0;

    virtual bool HaveCoin(const COutPoint& outpoint) const = 0;

    virtual uint256 GetBestBlock() const = 0;

    virtual std::vector<uint256> GetHeadBlocks() const = 0;

    virtual void BatchWrite(CoinsViewCacheCursor& cursor, const uint256& block_hash) = 0;

    virtual size_t EstimateSize() const = 0;
};

class CoinsViewEmpty : public CCoinsView
{
protected:
    CoinsViewEmpty() = default;
 
public:
    static CoinsViewEmpty& Get();
 
    CoinsViewEmpty(const CoinsViewEmpty&) = delete;
    CoinsViewEmpty& operator=(const CoinsViewEmpty&) = delete;
 
    std::optional<Coin> GetCoin(const COutPoint&) const override { return {}; }
    std::optional<Coin> PeekCoin(const COutPoint& outpoint) const override { return GetCoin(outpoint); }
    bool HaveCoin(const COutPoint& outpoint) const override { return !!GetCoin(outpoint); }
    uint256 GetBestBlock() const override { return {}; }
    std::vector<uint256> GetHeadBlocks() const override { return {}; }
    void BatchWrite(CoinsViewCacheCursor& cursor, const uint256&) override
    {
        for (auto it{cursor.Begin()}; it != cursor.End(); it = cursor.NextAndMaybeErase(*it)) { }
    }
    size_t EstimateSize() const override { return 0; }
};

class CCoinsViewBacked : public CCoinsView
{
protected:
    CCoinsView* base;
 
public:
    explicit CCoinsViewBacked(CCoinsView* in_view) : base{Assert(in_view)} {}
 
    void SetBackend(CCoinsView& in_view) { base = &in_view; }
 
    std::optional<Coin> GetCoin(const COutPoint& outpoint) const override { return base->GetCoin(outpoint); }
    std::optional<Coin> PeekCoin(const COutPoint& outpoint) const override { return base->PeekCoin(outpoint); }
    bool HaveCoin(const COutPoint& outpoint) const override { return base->HaveCoin(outpoint); }
    uint256 GetBestBlock() const override { return base->GetBestBlock(); }
    std::vector<uint256> GetHeadBlocks() const override { return base->GetHeadBlocks(); }
    void BatchWrite(CoinsViewCacheCursor& cursor, const uint256& block_hash) override { base->BatchWrite(cursor, block_hash); }
    size_t EstimateSize() const override { return base->EstimateSize(); }
};
 

class CCoinsViewCache : public CCoinsViewBacked
{
private:
    const bool m_deterministic;

    void ReallocateCache();

    CCoinsMap::iterator FetchCoin(const COutPoint &outpoint) const;
 
protected:
    mutable uint256 m_block_hash;
    mutable CCoinsMapMemoryResource m_cache_coins_memory_resource{};
    /* The starting sentinel of the flagged entry circular doubly linked list. */
    mutable CoinsCachePair m_sentinel;
    mutable CCoinsMap cacheCoins;
 
    /* Cached dynamic memory usage for the inner Coin objects. */
    mutable size_t cachedCoinsUsage{0};
    /* Running count of dirty Coin cache entries. */
    mutable size_t m_dirty_count{0};

    virtual void Reset() noexcept;
 
    /* Fetch the coin from base. Used for cache misses in FetchCoin. */
    virtual std::optional<Coin> FetchCoinFromBase(const COutPoint& outpoint) const;
 
public:
    CCoinsViewCache(CCoinsView* in_base, bool deterministic = false);

    CCoinsViewCache(const CCoinsViewCache &) = delete;
 
    // Standard CCoinsView methods
    std::optional<Coin> GetCoin(const COutPoint& outpoint) const override;
    std::optional<Coin> PeekCoin(const COutPoint& outpoint) const override;
    bool HaveCoin(const COutPoint& outpoint) const override;
    uint256 GetBestBlock() const override;
    void SetBestBlock(const uint256& block_hash);
    void BatchWrite(CoinsViewCacheCursor& cursor, const uint256& block_hash) override;

    bool HaveCoinInCache(const COutPoint &outpoint) const;

    const Coin& AccessCoin(const COutPoint &output) const;

    void AddCoin(const COutPoint& outpoint, Coin&& coin, bool possible_overwrite);

    void EmplaceCoinInternalDANGER(const COutPoint& outpoint, Coin&& coin);

    bool SpendCoin(const COutPoint &outpoint, Coin* moveto = nullptr);

    virtual void Flush(bool reallocate_cache = true);

    void Sync();

    void Uncache(const COutPoint &outpoint);

    unsigned int GetCacheSize() const;

    size_t GetDirtyCount() const noexcept { return m_dirty_count; }

    size_t DynamicMemoryUsage() const;

    bool HaveInputs(const CTransaction& tx) const;

    void SanityCheck() const;
 
    class ResetGuard
    {
    private:
        friend CCoinsViewCache;
        CCoinsViewCache& m_cache;
        explicit ResetGuard(CCoinsViewCache& cache LIFETIMEBOUND) noexcept : m_cache{cache} {}
 
    public:
        ResetGuard(const ResetGuard&) = delete;
        ResetGuard& operator=(const ResetGuard&) = delete;
        ResetGuard(ResetGuard&&) = delete;
        ResetGuard& operator=(ResetGuard&&) = delete;
 
        ~ResetGuard() { m_cache.Reset(); }
    };

    [[nodiscard]] ResetGuard CreateResetGuard() noexcept { return ResetGuard{*this}; }
};

class CoinsViewOverlay : public CCoinsViewCache
{
private:
    std::atomic_uint32_t m_input_head{0};
    mutable uint32_t m_input_tail{0};

    struct InputToFetch {
        std::atomic_flag ready{};
        const COutPoint& outpoint;
        mutable std::optional<Coin> coin{std::nullopt};
 
        explicit InputToFetch(const COutPoint& o LIFETIMEBOUND) noexcept : outpoint{o} {}

        InputToFetch(InputToFetch&& other) noexcept : outpoint{other.outpoint}
        {
            Assert(!other.coin);
            Assert(!other.ready.test(std::memory_order_relaxed));
        }
    };

    std::vector<InputToFetch> m_inputs{};

    bool ProcessInput() noexcept
    {
        const auto i{m_input_head.fetch_add(1, std::memory_order_relaxed)};
        if (i >= m_inputs.size()) return false;
 
        auto& input{m_inputs[i]};
        input.coin = base->PeekCoin(input.outpoint);
        // Use release so writing coin above happens before the main thread acquires.
        Assert(!input.ready.test_and_set(std::memory_order_release));
        input.ready.notify_one();
        return true;
    }

    void StopFetching() noexcept
    {
        if (m_futures.empty()) {
            Assert(m_inputs.empty());
            Assert(m_input_head.load(std::memory_order_relaxed) == 0);
            Assert(m_input_tail == 0);
            return;
        }
        // Skip fetching the rest of the inputs by moving the head to the end.
        m_input_head.store(m_inputs.size(), std::memory_order_relaxed);
        // Wait for all threads to stop.
        for (auto& future : m_futures) future.wait();
        m_futures.clear();
        m_inputs.clear();
        m_input_head.store(0, std::memory_order_relaxed);
        m_input_tail = 0;
    }
 
    std::optional<Coin> FetchCoinFromBase(const COutPoint& outpoint) const override
    {
        // This assumes ConnectBlock accesses all inputs in the same order as
        // they are added to m_inputs in StartFetching.
        if (m_input_tail < m_inputs.size() && m_inputs[m_input_tail].outpoint == outpoint) {
            // We advance the tail since the input is cached and not accessed through this method again.
            auto& input{m_inputs[m_input_tail++]};
            // Wait until the coin is ready to be read. We need acquire so we match the worker thread's release.
            input.ready.wait(/*old=*/false, std::memory_order_acquire);
            // We can move the coin since we won't access this input again.
            return std::move(input.coin);
        }
 
        // We will only get here for BIP30 checks, an invalid block, or if the threadpool has not been started.
        return base->PeekCoin(outpoint);
    }

    std::shared_ptr<ThreadPool> m_thread_pool;
    std::vector<std::future<void>> m_futures{};
 
protected:
    void Reset() noexcept override
    {
        StopFetching();
        CCoinsViewCache::Reset();
    }
 
public:
    explicit CoinsViewOverlay(CCoinsView* in_base, std::shared_ptr<ThreadPool> thread_pool,
                              bool deterministic = false) noexcept
        : CCoinsViewCache{in_base, deterministic}, m_thread_pool{std::move(thread_pool)}
    {
        Assert(m_thread_pool);
    }
 
    ~CoinsViewOverlay() noexcept override { StopFetching(); }

    [[nodiscard]] ResetGuard StartFetching(const CBlock& block LIFETIMEBOUND) noexcept;
 
    void Flush(bool reallocate_cache = true) override
    {
        if (!Assume(AllInputsConsumed())) {
            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());
        }
        StopFetching();
        CCoinsViewCache::Flush(reallocate_cache);
    }

    void SetBackend(CCoinsView&) = delete;
    void Sync() = delete;

    bool AllInputsConsumed() const noexcept { return m_input_tail == m_inputs.size(); }
};

// TODO: pass in a boolean to limit these possible overwrites to known
// (pre-BIP34) cases.
void AddCoins(CCoinsViewCache& cache, const CTransaction& tx, int nHeight, bool check = false);

const Coin& AccessByTxid(const CCoinsViewCache& cache, const Txid& txid);

class CCoinsViewErrorCatcher final : public CCoinsViewBacked
{
public:
    explicit CCoinsViewErrorCatcher(CCoinsView* view) : CCoinsViewBacked(view) {}
 
    void AddReadErrCallback(std::function<void()> f) {
        m_err_callbacks.emplace_back(std::move(f));
    }
 
    std::optional<Coin> GetCoin(const COutPoint& outpoint) const override;
    bool HaveCoin(const COutPoint& outpoint) const override;
    std::optional<Coin> PeekCoin(const COutPoint& outpoint) const override;
 
private:
    std::vector<std::function<void()>> m_err_callbacks;
 
};
 
#endif // BITCOIN_COINS_H