Representing unspent outputs and cache state

251
252    /** Hash an outpoint as its txid jumbo block followed by the zero-extended index as one normal block. */
253    size_t operator()(const COutPoint& id) const noexcept
254    {
255        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 */
267using CCoinsMap = std::unordered_map<COutPoint,
268                                     CCoinsCacheEntry,
269                                     SaltedCoinsCacheHasher,
270                                     std::equal_to<COutPoint>,
271                                     PoolAllocator<CoinsCachePair,
272                                                   sizeof(CoinsCachePair) + sizeof(void*) * 4>>;
273
274using CCoinsMapMemoryResource = CCoinsMap::allocator_type::ResourceType;
275
276/** Cursor for iterating over CoinsView state */
277class CCoinsViewCursor
278{
279public:
280    CCoinsViewCursor(const uint256& in_block_hash) : block_hash(in_block_hash) {}
281    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    const uint256& GetBestBlock() const { return block_hash; }
291private:
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 */
308struct 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    CoinsViewCacheCursor(size_t& dirty_count LIFETIMEBOUND,
318                         CoinsCachePair& sentinel LIFETIMEBOUND,
319                         CCoinsMap& map LIFETIMEBOUND,
320                         bool will_erase) noexcept
321        : m_dirty_count(dirty_count), m_sentinel(sentinel), m_map(map), m_will_erase(will_erase) {}
322
323    inline CoinsCachePair* Begin() const noexcept { return m_sentinel.second.Next(); }
324    inline CoinsCachePair* End() const noexcept { return &m_sentinel; }
325
326    //! Return the next entry after current, possibly erasing current
327    inline CoinsCachePair* NextAndMaybeErase(CoinsCachePair& current) noexcept
328    {
329        const auto next_entry{current.second.Next()};
330        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        if (!m_will_erase) {
334            if (current.second.coin.IsSpent()) {
335                assert(current.second.coin.DynamicMemoryUsage() == 0); // scriptPubKey was already cleared in SpendCoin
336                m_map.erase(current.first);
337            } else {
338                current.second.SetClean();
339            }
340        }
341        return next_entry;
342    }
343
344    inline bool WillErase(CoinsCachePair& current) const noexcept { return m_will_erase || current.second.coin.IsSpent(); }
345    size_t GetDirtyCount() const noexcept { return m_dirty_count; }
346    size_t GetTotalCount() const noexcept { return m_map.size(); }
347private:
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. */
355class CCoinsView
356{
357public:
358    //! As we use CCoinsViews polymorphically, have a virtual destructor
359    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. */
391class CoinsViewEmpty : public CCoinsView
392{
393protected:
394    CoinsViewEmpty() = default;
395
396public:
397    static CoinsViewEmpty& Get();
398
399    CoinsViewEmpty(const CoinsViewEmpty&) = delete;
400    CoinsViewEmpty& operator=(const CoinsViewEmpty&) = delete;
401
402    std::optional<Coin> GetCoin(const COutPoint&) const override { return {}; }
403    std::optional<Coin> PeekCoin(const COutPoint& outpoint) const override { return GetCoin(outpoint); }
404    bool HaveCoin(const COutPoint& outpoint) const override { return !!GetCoin(outpoint); }
405    uint256 GetBestBlock() const override { return {}; }
406    std::vector<uint256> GetHeadBlocks() const override { return {}; }
407    void BatchWrite(CoinsViewCacheCursor& cursor, const uint256&) override
408    {
409        for (auto it{cursor.Begin()}; it != cursor.End(); it = cursor.NextAndMaybeErase(*it)) { }
410    }
411    size_t EstimateSize() const override { return 0; }
412};
413
414/** CCoinsView backed by another CCoinsView */
415class CCoinsViewBacked : public CCoinsView
416{
417protected:
418    CCoinsView* base;
419
420public:
421    explicit CCoinsViewBacked(CCoinsView* in_view) : base{Assert(in_view)} {}
422
423    void SetBackend(CCoinsView& in_view) { base = &in_view; }
424
425    std::optional<Coin> GetCoin(const COutPoint& outpoint) const override { return base->GetCoin(outpoint); }
426    std::optional<Coin> PeekCoin(const COutPoint& outpoint) const override { return base->PeekCoin(outpoint); }
427    bool HaveCoin(const COutPoint& outpoint) const override { return base->HaveCoin(outpoint); }
428    uint256 GetBestBlock() const override { return base->GetBestBlock(); }
429    std::vector<uint256> GetHeadBlocks() const override { return base->GetHeadBlocks(); }
430    void BatchWrite(CoinsViewCacheCursor& cursor, const uint256& block_hash) override { base->BatchWrite(cursor, block_hash); }
431    size_t EstimateSize() const override { return base->EstimateSize(); }
432};
433
434
435/** CCoinsView that adds a memory cache for transactions to another CCoinsView */
436class CCoinsViewCache : public CCoinsViewBacked
437{
438private:
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
454protected:
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
479public:
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;