Representing unspent outputs and cache state

501
502    /**
503     * Return a reference to Coin in the cache, or coinEmpty if not found. This is
504     * more efficient than GetCoin.
505     *
506     * Generally, do not hold the reference returned for more than a short scope.
507     * While the current implementation allows for modifications to the contents
508     * of the cache while holding the reference, this behavior should not be relied
509     * on! To be safe, best to not hold the returned reference through any other
510     * calls to this cache.
511     */
512    const Coin& AccessCoin(const COutPoint &output) const;
513
514    /**
515     * Add a coin. Set possible_overwrite to true if an unspent version may
516     * already exist in the cache.
517     */
518    void AddCoin(const COutPoint& outpoint, Coin&& coin, bool possible_overwrite);
519
520    /**
521     * Emplace a coin into cacheCoins without performing any checks, marking
522     * the emplaced coin as dirty.
523     *
524     * NOT FOR GENERAL USE. Used only when loading coins from a UTXO snapshot.
525     * @sa ChainstateManager::PopulateAndValidateSnapshot()
526     */
527    void EmplaceCoinInternalDANGER(const COutPoint& outpoint, Coin&& coin);
528
529    /**
530     * Spend a coin. Pass moveto in order to get the deleted data.
531     * If no unspent output exists for the passed outpoint, this call
532     * has no effect.
533     */
534    bool SpendCoin(const COutPoint &outpoint, Coin* moveto = nullptr);
535
536    /**
537     * Push the modifications applied to this cache to its base and wipe local state.
538     * Failure to call this method or Sync() before destruction will cause the changes
539     * to be forgotten.
540     * If reallocate_cache is false, the cache will retain the same memory footprint
541     * after flushing and should be destroyed to deallocate.
542     */
543    virtual void Flush(bool reallocate_cache = true);
544
545    /**
546     * Push the modifications applied to this cache to its base while retaining
547     * the contents of this cache (except for spent coins, which we erase).
548     * Failure to call this method or Flush() before destruction will cause the changes
549     * to be forgotten.
550     */
551    void Sync();
552
553    /**
554     * Removes the UTXO with the given outpoint from the cache, if it is
555     * not modified.
556     */
557    void Uncache(const COutPoint &outpoint);
558
559    //! Size of the cache (in number of transaction outputs)
560    unsigned int GetCacheSize() const;
561
562    //! Number of dirty cache entries (transaction outputs)
563    size_t GetDirtyCount() const noexcept { return m_dirty_count; }
564
565    //! Calculate the size of the cache (in bytes)
566    size_t DynamicMemoryUsage() const;
567
568    //! Check whether all prevouts of the transaction are present in the UTXO set represented by this view
569    bool HaveInputs(const CTransaction& tx) const;
570
571    //! Run an internal sanity check on the cache data structure. */
572    void SanityCheck() const;
573
574    class ResetGuard
575    {
576    private:
577        friend CCoinsViewCache;
578        CCoinsViewCache& m_cache;
579        explicit ResetGuard(CCoinsViewCache& cache LIFETIMEBOUND) noexcept : m_cache{cache} {}
580
581    public:
582        ResetGuard(const ResetGuard&) = delete;
583        ResetGuard& operator=(const ResetGuard&) = delete;
584        ResetGuard(ResetGuard&&) = delete;
585        ResetGuard& operator=(ResetGuard&&) = delete;
586
587        ~ResetGuard() { m_cache.Reset(); }
588    };
589
590    //! Create a scoped guard that will call `Reset()` on this cache when it goes out of scope.
591    [[nodiscard]] ResetGuard CreateResetGuard() noexcept { return ResetGuard{*this}; }
592};
593
594/**
595 * CCoinsViewCache subclass that asynchronously fetches most block input prevouts in parallel during ConnectBlock
596 * without mutating the base cache. This is achieved by fetching coins from the base view using PeekCoin() instead of
597 * GetCoin(), so intermediate CCoinsViewCache layers are not filled.
598 *
599 * Used during ConnectBlock() as an ephemeral, resettable top-level view that is flushed only on success, so invalid
600 * blocks don't pollute the underlying cache.
601 *
602 * While this class uses threads internally to fetch coins, externally it is only safe to call its methods from a
603 * single "main" thread. It assumes StartFetching, StopFetching, FetchCoinFromBase, Flush and Reset will all only be
604 * called from the main thread.
605 *
606 * When a block is passed to StartFetching, the inputs of the block are flattened into a vector of InputToFetch
607 * objects. StartFetching then submits worker tasks to a ThreadPool and keeps the returned futures alive until fetching
608 * is stopped.
609 *
610 * ProcessInput() atomically fetches and increments m_input_head, so each thread can only access a single element of the
611 * m_inputs vector at a time. Workers race to claim inputs, so they may fetch elements in any order. If the fetched
612 * index is greater than or equal to the size of m_inputs, no more inputs can be fetched and false is returned.
613 *
614 * The worker claims the InputToFetch at this index, fetches the coin with base->PeekCoin() and moves it into the
615 * InputToFetch object. The ready flag is then set with a release memory order. This allows the ready flag to be
616 * used as a memory fence, guaranteeing the coin being written to the object will have happened before another
617 * thread tests the flag with an acquire memory order.
618 * This assumes all base->PeekCoin() paths are safe for concurrent readers.
619 *
620 * The main thread is the only consumer of the fetched coins. FetchCoinFromBase is called when a coin is requested on
621 * the main thread and is not already in the cache. It checks whether the next unconsumed entry in m_inputs has the
622 * requested outpoint. On a match, m_input_tail is advanced and the entry's ready flag is waited on with an acquire
623 * memory order until a worker has finished fetching it. The coin is then moved out and returned.
624 *
625 * StopFetching() is called in Flush() and in Reset() (the per-block teardown) so workers stop before the block they
626 * reference goes away. It stops fetching by moving m_input_head to the end of m_inputs (so workers quickly exit),
627 * then waits for all futures to complete and clears the per-block state (m_inputs and the head/tail counters).
628 *
629 *       Workers advance m_input_head to fetch inputs. Main thread advances m_input_tail to consume.
630 *
631 *       Before workers start:
632 *
633 *                 m_input_head
634 *                 m_input_tail
635 *                      │
636 *                      ▼
637 *                 ┌─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┐
638 *       m_inputs: │ waiting │ waiting │ waiting │ waiting │ waiting │ waiting │ waiting │ waiting │ waiting │
639 *                 │         │         │         │         │         │         │         │         │         │
640 *                 └─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┘
641 *
642 *       After workers start:
643 *
644 *                                       Worker 2            Worker 0  Worker 3  Worker 1  m_input_head
645 *                                          │                   │         │         │         │
646 *                                          ▼                   ▼         ▼         ▼         ▼
647 *                 ┌─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┐
648 *       m_inputs: │  ready  │  ready  │fetching │  ready  │fetching │fetching │fetching │ waiting │ waiting │
649 *                 │consumed │    ✓    │    ●    │    ✓    │    ●    │    ●    │    ●    │         │         │
650 *                 └─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┘
651 *                                ▲
652 *                                │
653 *                           m_input_tail
654 */
655class CoinsViewOverlay : public CCoinsViewCache
656{
657private:
658    //! The latest input not yet being fetched. Workers atomically increment this when fetching.
659    std::atomic_uint32_t m_input_head{0};
660    //! The latest input not yet accessed by a consumer. Only the main thread increments this.
661    mutable uint32_t m_input_tail{0};
662
663    //! The inputs of the block which is being fetched.
664    struct InputToFetch {
665        //! Workers set this after setting the coin. The main thread tests this before reading the coin.
666        std::atomic_flag ready{};
667        //! The outpoint of the input to fetch.
668        const COutPoint& outpoint;
669        //! The coin that workers will fetch and main thread will insert into cache.
670        //! Mutable so it can be moved in FetchCoinFromBase.
671        mutable std::optional<Coin> coin{std::nullopt};
672
673        explicit InputToFetch(const COutPoint& o LIFETIMEBOUND) noexcept : outpoint{o} {}
674
675        //! Move ctor is required for resizing m_inputs in StartFetching. Elements will never move once parallel tasks
676        //! are started, so we can assert that coin is nullopt and ready is false.
677        InputToFetch(InputToFetch&& other) noexcept : outpoint{other.outpoint}
678        {
679            Assert(!other.coin);
680            Assert(!other.ready.test(std::memory_order_relaxed));
681        }
682    };
683    //! Must only be mutated when m_futures is empty. Elements may be mutated when m_futures is not empty.
684    std::vector<InputToFetch> m_inputs{};
685
686    /**
687     * Claim and fetch the next input in the queue.
688     *
689     * @return true if an input prevout was fetched
690     * @return false if there are no more input prevouts in the queue to fetch
691     */
692    bool ProcessInput() noexcept
693    {
694        const auto i{m_input_head.fetch_add(1, std::memory_order_relaxed)};
695        if (i >= m_inputs.size()) return false;
696
697        auto& input{m_inputs[i]};
698        input.coin = base->PeekCoin(input.outpoint);
699        // Use release so writing coin above happens before the main thread acquires.
700        Assert(!input.ready.test_and_set(std::memory_order_release));
701        input.ready.notify_one();
702        return true;
703    }
704
705    //! Stop all worker threads and clear fetching data.
706    //! Calling this is idempotent, and may safely be called if not fetching.
707    void StopFetching() noexcept
708    {
709        if (m_futures.empty()) {
710            Assert(m_inputs.empty());
711            Assert(m_input_head.load(std::memory_order_relaxed) == 0);
712            Assert(m_input_tail == 0);
713            return;
714        }
715        // Skip fetching the rest of the inputs by moving the head to the end.
716        m_input_head.store(m_inputs.size(), std::memory_order_relaxed);
717        // Wait for all threads to stop.
718        for (auto& future : m_futures) future.wait();
719        m_futures.clear();
720        m_inputs.clear();
721        m_input_head.store(0, std::memory_order_relaxed);
722        m_input_tail = 0;
723    }
724
725    std::optional<Coin> FetchCoinFromBase(const COutPoint& outpoint) const override
726    {
727        // This assumes ConnectBlock accesses all inputs in the same order as
728        // they are added to m_inputs in StartFetching.
729        if (m_input_tail < m_inputs.size() && m_inputs[m_input_tail].outpoint == outpoint) {
730            // We advance the tail since the input is cached and not accessed through this method again.
731            auto& input{m_inputs[m_input_tail++]};
732            // Wait until the coin is ready to be read. We need acquire so we match the worker thread's release.
733            input.ready.wait(/*old=*/false, std::memory_order_acquire);
734            // We can move the coin since we won't access this input again.
735            return std::move(input.coin);
736        }
737
738        // We will only get here for BIP30 checks, an invalid block, or if the threadpool has not been started.
739        return base->PeekCoin(outpoint);
740    }
741
742    //! Non-null. May have zero workers when input fetching is disabled.
743    std::shared_ptr<ThreadPool> m_thread_pool;
744    std::vector<std::future<void>> m_futures{};
745
746protected:
747    //! StopFetching must be called here for two reasons: InputToFetch objects hold references to the
748    //! block's outpoints, so they must not outlive the block being connected; and when connecting a
749    //! block fails, workers must not keep fetching inputs for the block that was abandoned.
750    void Reset() noexcept override