SHAMap.h

#pragma once
 
#include <xrpl/basics/Blob.h>
#include <xrpl/basics/IntrusivePointer.h>
#include <xrpl/basics/SHAMapHash.h>
#include <xrpl/basics/base_uint.h>
#include <xrpl/beast/utility/Journal.h>
#include <xrpl/beast/utility/instrumentation.h>
#include <xrpl/nodestore/NodeObject.h>
#include <xrpl/protocol/Serializer.h>
#include <xrpl/shamap/Family.h>
#include <xrpl/shamap/SHAMapAddNode.h>
#include <xrpl/shamap/SHAMapInnerNode.h>
#include <xrpl/shamap/SHAMapItem.h>
#include <xrpl/shamap/SHAMapLeafNode.h>
#include <xrpl/shamap/SHAMapMissingNode.h>
#include <xrpl/shamap/SHAMapNodeID.h>
#include <xrpl/shamap/SHAMapTreeNode.h>
 
#include <condition_variable>
#include <cstddef>
#include <cstdint>
#include <deque>
#include <functional>
#include <iterator>
#include <map>
#include <memory>
#include <mutex>
#include <optional>
#include <set>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>
 
namespace xrpl {
 
class SHAMapSyncFilter;

enum class SHAMapState {
    Modifying = 0,

    Immutable = 1,

    Synching = 2,

    Invalid = 3,
};


struct SHAMapNodeData
{
    SHAMapNodeID nodeID;
    // The `data` field (a Blob, 8-byte aligned) needs 4 bytes of padding after the `nodeID` field
    // (36 bytes, 4-byte aligned) regardless of what comes between them, so `isLeaf` costs nothing
    // extra here. Moving it after `data` would add 8 bytes to the size of this struct instead.
    bool isLeaf;
    Blob data;
};
 
class SHAMap
{
private:
    Family& f_;
    beast::Journal journal_;

    std::uint32_t cowid_ = 1;

    std::uint32_t ledgerSeq_ = 0;
 
    SHAMapTreeNodePtr root_;
    mutable SHAMapState state_;
    SHAMapType const type_;
    bool backed_ = true;         // Map is backed by the database
    mutable bool full_ = false;  // Map is believed complete in database
 
public:
    static constexpr unsigned int kBranchFactor = SHAMapInnerNode::kBranchFactor;

    static constexpr unsigned int kLeafDepth = 64;
 
    using DeltaItem =
        std::pair<boost::intrusive_ptr<SHAMapItem const>, boost::intrusive_ptr<SHAMapItem const>>;
    using Delta = std::map<UInt256, DeltaItem>;
 
    SHAMap() = delete;
    SHAMap(SHAMap const&) = delete;
    SHAMap&
    operator=(SHAMap const&) = delete;
 
    // Take a snapshot of the given map:
    SHAMap(SHAMap const& other, bool isMutable);
 
    // build new map
    SHAMap(SHAMapType t, Family& f);
 
    SHAMap(SHAMapType t, UInt256 const& hash, Family& f);
 
    ~SHAMap() = default;
 
    Family const&
    family() const
    {
        return f_;
    }
 
    Family&
    family()
    {
        return f_;
    }
 
    //--------------------------------------------------------------------------

    class ConstIterator;
 
    ConstIterator
    begin() const;
    ConstIterator
    end() const;
 
    //--------------------------------------------------------------------------
 
    // Returns a new map that's a snapshot of this one.
    // Handles copy on write for mutable snapshots.
    std::shared_ptr<SHAMap>
    snapShot(bool isMutable) const;
 
    /*  Mark this SHAMap as "should be full", indicating
        that the local server wants all the corresponding nodes
        in durable storage.
    */
    void
    setFull();
 
    void
    setLedgerSeq(std::uint32_t lseq);
 
    bool
    fetchRoot(SHAMapHash const& hash, SHAMapSyncFilter const* filter);
 
    // normal hash access functions

    bool
    hasItem(UInt256 const& id) const;
 
    bool
    delItem(UInt256 const& id);
 
    bool
    addItem(SHAMapNodeType type, boost::intrusive_ptr<SHAMapItem const> item);
 
    SHAMapHash
    getHash() const;
 
    // save a copy if you have a temporary anyway
    bool
    updateGiveItem(SHAMapNodeType type, boost::intrusive_ptr<SHAMapItem const> item);
 
    bool
    addGiveItem(SHAMapNodeType type, boost::intrusive_ptr<SHAMapItem const> item);
 
    // Save a copy if you need to extend the life
    // of the SHAMapItem beyond this SHAMap
    boost::intrusive_ptr<SHAMapItem const> const&
    peekItem(UInt256 const& id) const;
    boost::intrusive_ptr<SHAMapItem const> const&
    peekItem(UInt256 const& id, SHAMapHash& hash) const;
 
    // traverse functions
    ConstIterator
    upperBound(UInt256 const& id) const;

    ConstIterator
    lowerBound(UInt256 const& id) const;

    void
    visitNodes(std::function<bool(SHAMapTreeNode&)> const& function) const;

    void
    visitDifferences(SHAMap const* have, std::function<bool(SHAMapTreeNode const&)> const&) const;

    void
    visitLeaves(std::function<void(boost::intrusive_ptr<SHAMapItem const> const&)> const&) const;
 
    // comparison/sync functions

    std::vector<std::pair<SHAMapNodeID, UInt256>>
    getMissingNodes(int maxNodes, SHAMapSyncFilter const* filter);
 
    [[nodiscard]] bool
    getNodeFat(
        SHAMapNodeID const& wanted,
        std::vector<SHAMapNodeData>& data,
        bool fatLeaves,
        std::uint32_t depth) const;

    std::optional<std::vector<Blob>>
    getProofPath(UInt256 const& key) const;

    static bool
    verifyProofPath(UInt256 const& rootHash, UInt256 const& key, std::vector<Blob> const& path);

    void
    serializeRoot(Serializer& s) const;

    SHAMapAddNode
    addRootNode(SHAMapHash const& hash, SHAMapTreeNodePtr rootNode, SHAMapSyncFilter const* filter);

    SHAMapAddNode
    addKnownNode(
        SHAMapNodeID const& nodeID,
        SHAMapTreeNodePtr treeNode,
        SHAMapSyncFilter const* filter);
 
    // status functions
    void
    setImmutable();
    bool
    isSynching() const;
    void
    setSynching();
    void
    clearSynching();
    bool
    isValid() const;
 
    // caution: otherMap must be accessed only by this function
    // return value: true=successfully completed, false=too different
    bool
    compare(SHAMap const& otherMap, Delta& differences, int maxCount) const;

    int
    unshare();

    int
    flushDirty(NodeObjectType t);
 
    void
    walkMap(std::vector<SHAMapMissingNode>& missingNodes, int maxMissing) const;
    bool
    walkMapParallel(std::vector<SHAMapMissingNode>& missingNodes, int maxMissing) const;
    bool
    deepCompare(SHAMap& other) const;  // Intended for debug/test only
 
    void
    setUnbacked();
 
    void
    dump(bool withHashes = false) const;
    void
    invariants() const;
 
private:
    class NodePathStack
    {
    public:
        [[nodiscard]] bool
        empty() const
        {
            return stack_.empty();
        }
 
        [[nodiscard]] std::size_t
        size() const
        {
            return stack_.size();
        }
 
        [[nodiscard]] std::pair<SHAMapTreeNodePtr, SHAMapNodeID> const&
        top() const
        {
            XRPL_ASSERT(!stack_.empty(), "xrpl::SHAMap::NodePathStack::top : non-empty stack");
            return stack_.top();
        }
 
        void
        pop()
        {
            XRPL_ASSERT(!stack_.empty(), "xrpl::SHAMap::NodePathStack::pop : non-empty stack");
            stack_.pop();
        }
 
        void
        clear()
        {
            stack_ = {};
        }

        void
        pushRoot(SHAMapTreeNodePtr node)
        {
            XRPL_ASSERT(stack_.empty(), "xrpl::SHAMap::NodePathStack::pushRoot : empty stack");
            stack_.emplace(std::move(node), SHAMapNodeID{});
        }

        void
        pushChild(SHAMapTreeNodePtr node, unsigned int branch)
        {
            XRPL_ASSERT(node, "xrpl::SHAMap::NodePathStack::pushChild : non-null node input");
            XRPL_ASSERT(
                !stack_.empty(), "xrpl::SHAMap::NodePathStack::pushChild : non-empty stack");
            auto childID = stack_.top().second.getChildNodeID(branch);
            XRPL_ASSERT_IF(
                node->isInner(),
                childID.getDepth() < kLeafDepth,
                "xrpl::SHAMap::NodePathStack::pushChild : inner node above leaf depth");
            XRPL_ASSERT_IF(
                node->isLeaf(),
                childID.isPrefixOf(leafKey(*node)),
                "xrpl::SHAMap::NodePathStack::pushChild : leaf key below branch");
            stack_.emplace(std::move(node), std::move(childID));
        }

        void
        pushNode(SHAMapTreeNodePtr node, UInt256 const& target)
        {
            if (stack_.empty())
            {
                pushRoot(std::move(node));
            }
            else
            {
                pushChild(std::move(node), selectBranch(stack_.top().second, target));
            }
        }
 
    private:
        std::stack<std::pair<SHAMapTreeNodePtr, SHAMapNodeID>> stack_;
    };
 
    using DeltaRef =
        std::pair<boost::intrusive_ptr<SHAMapItem const>, boost::intrusive_ptr<SHAMapItem const>>;
 
    // tree node cache operations
    SHAMapTreeNodePtr
    cacheLookup(SHAMapHash const& hash) const;
 
    void
    canonicalize(SHAMapHash const& hash, SHAMapTreeNodePtr&) const;
 
    // database operations
    SHAMapTreeNodePtr
    fetchNodeFromDB(SHAMapHash const& hash) const;
    SHAMapTreeNodePtr
    fetchNodeNT(SHAMapHash const& hash) const;
    SHAMapTreeNodePtr
    fetchNodeNT(SHAMapHash const& hash, SHAMapSyncFilter const* filter) const;
    SHAMapTreeNodePtr
    fetchNode(SHAMapHash const& hash) const;
    SHAMapTreeNodePtr
    checkFilter(SHAMapHash const& hash, SHAMapSyncFilter const* filter) const;

    void
    dirtyUp(NodePathStack& stack, UInt256 const& target, SHAMapTreeNodePtr terminal);

    SHAMapLeafNode*
    walkTowardsKey(UInt256 const& id, NodePathStack* stack = nullptr) const;
    SHAMapLeafNode*
    findKey(UInt256 const& id) const;

    template <class Node>
    intr_ptr::SharedPtr<Node>
    unshareNode(intr_ptr::SharedPtr<Node>, SHAMapNodeID const& nodeID);

    template <class Node>
    intr_ptr::SharedPtr<Node>
    preFlushNode(intr_ptr::SharedPtr<Node> node) const;

    SHAMapTreeNodePtr
    writeNode(NodeObjectType t, SHAMapTreeNodePtr node) const;
 
    // direction in which a scan walks an inner node's branches
    enum class BelowDirection { First, Last };

    SHAMapLeafNode*
    belowHelper(NodePathStack& stack, BelowDirection direction) const;

    ConstIterator
    boundHelper(UInt256 const& id, BelowDirection direction) const;
 
    // Simple descent
    // Get a child of the specified node
    SHAMapTreeNode*
    descend(SHAMapInnerNode*, unsigned int branch) const;
    SHAMapTreeNode*
    descendThrow(SHAMapInnerNode*, unsigned int branch) const;
    SHAMapTreeNodePtr
    descend(SHAMapInnerNode&, unsigned int branch) const;
    SHAMapTreeNodePtr
    descendThrow(SHAMapInnerNode&, unsigned int branch) const;
 
    // Descend with filter
    // If pending, callback is called as if it called fetchNodeNT
    using DescendCallback = std::function<void(SHAMapTreeNodePtr, SHAMapHash const&)>;
    SHAMapTreeNode*
    descendAsync(
        SHAMapInnerNode* parent,
        unsigned int branch,
        SHAMapSyncFilter const* filter,
        bool& pending,
        DescendCallback&&) const;
 
    std::pair<SHAMapTreeNode*, SHAMapNodeID>
    descend(
        SHAMapInnerNode* parent,
        SHAMapNodeID const& parentID,
        unsigned int branch,
        SHAMapSyncFilter const* filter) const;
 
    // Non-storing
    // Does not hook the returned node to its parent
    SHAMapTreeNodePtr
    descendNoStore(SHAMapInnerNode&, unsigned int branch) const;

    boost::intrusive_ptr<SHAMapItem const> const&
    onlyBelow(SHAMapTreeNode*) const;
 
    bool
    hasInnerNode(SHAMapNodeID const& nodeID, SHAMapHash const& hash) const;
    bool
    hasLeafNode(UInt256 const& tag, SHAMapHash const& hash) const;
 
    SHAMapLeafNode const*
    peekFirstItem(NodePathStack& stack) const;
    SHAMapLeafNode const*
    peekNextItem(UInt256 const& id, NodePathStack& stack) const;
    bool
    walkBranch(
        SHAMapTreeNode* node,
        boost::intrusive_ptr<SHAMapItem const> const& otherMapItem,
        bool isFirstMap,
        Delta& differences,
        int& maxCount) const;
    int
    walkSubTree(bool doWrite, NodeObjectType t);
 
    // Structure to track information about call to
    // getMissingNodes while it's in progress
    struct MissingNodes
    {
        MissingNodes() = delete;
        MissingNodes(MissingNodes const&) = delete;
        MissingNodes&
        operator=(MissingNodes const&) = delete;
 
        // basic parameters
        int max;
        SHAMapSyncFilter const* filter;
        int const maxDefer;
        std::uint32_t generation;
 
        // nodes we have discovered to be missing
        std::vector<std::pair<SHAMapNodeID, UInt256>> missingNodes;
        std::set<SHAMapHash> missingHashes;
 
        // nodes we are in the process of traversing
        using StackEntry = std::tuple<
            SHAMapInnerNode*,  // pointer to the node
            SHAMapNodeID,      // the node's ID
            unsigned int,      // which child we check first
            unsigned int,      // which child we check next
            bool>;             // whether we've found any missing children yet
 
        // We explicitly choose to specify the use of std::deque here, because
        // we need to ensure that pointers and/or references to existing
        // elements will not be invalidated during the course of element
        // insertion and removal. Containers that do not offer this guarantee,
        // such as std::vector, can't be used here.
        std::stack<StackEntry, std::deque<StackEntry>> stack;
 
        // nodes we may have acquired from deferred reads
        using DeferredNode = std::tuple<
            SHAMapInnerNode*,    // parent node
            SHAMapNodeID,        // parent node ID
            unsigned int,        // branch
            SHAMapTreeNodePtr>;  // node
 
        int deferred;
        std::mutex deferLock;
        std::condition_variable deferCondVar;
        std::vector<DeferredNode> finishedReads;
 
        // nodes we need to resume after we get their children from deferred
        // reads
        std::map<SHAMapInnerNode*, SHAMapNodeID> resumes;
 
        MissingNodes(
            int max,
            SHAMapSyncFilter const* filter,
            int maxDefer,
            std::uint32_t generation)
            : max(max), filter(filter), maxDefer(maxDefer), generation(generation), deferred(0)
        {
            missingNodes.reserve(max);
            finishedReads.reserve(maxDefer);
        }
    };
 
    // getMissingNodes helper functions
    void
    gmnProcessNodes(MissingNodes&, MissingNodes::StackEntry& node);
    static void
    gmnProcessDeferredReads(MissingNodes&);
 
    // fetch from DB helper function
    SHAMapTreeNodePtr
    finishFetch(SHAMapHash const& hash, std::shared_ptr<NodeObject> const& object) const;
};
 
inline void
SHAMap::setFull()
{
    full_ = true;
}
 
inline void
SHAMap::setLedgerSeq(std::uint32_t lseq)
{
    ledgerSeq_ = lseq;
}
 
inline void
SHAMap::setImmutable()
{
    XRPL_ASSERT(state_ != SHAMapState::Invalid, "xrpl::SHAMap::setImmutable : state is valid");
    state_ = SHAMapState::Immutable;
}
 
inline bool
SHAMap::isSynching() const
{
    return state_ == SHAMapState::Synching;
}
 
inline void
SHAMap::setSynching()
{
    state_ = SHAMapState::Synching;
}
 
inline void
SHAMap::clearSynching()
{
    state_ = SHAMapState::Modifying;
}
 
inline bool
SHAMap::isValid() const
{
    return state_ != SHAMapState::Invalid;
}
 
inline void
SHAMap::setUnbacked()
{
    backed_ = false;
}
 
//------------------------------------------------------------------------------
 
class SHAMap::ConstIterator
{
public:
    using iterator_category = std::forward_iterator_tag;
    using difference_type = std::ptrdiff_t;
    using value_type = SHAMapItem;
    using reference = value_type const&;
    using pointer = value_type const*;
 
private:
    NodePathStack stack_;
    SHAMap const* map_ = nullptr;
    pointer item_ = nullptr;
 
public:
    ConstIterator() = delete;
 
    ConstIterator(ConstIterator const& other) = default;
    ConstIterator&
    operator=(ConstIterator const& other) = default;
 
    ~ConstIterator() = default;
 
    reference
    operator*() const;
    pointer
    operator->() const;
 
    ConstIterator&
    operator++();
    ConstIterator
    operator++(int);
 
private:
    explicit ConstIterator(SHAMap const* map);
    ConstIterator(SHAMap const* map, std::nullptr_t);
    ConstIterator(SHAMap const* map, pointer item, NodePathStack&& stack);
 
    friend bool
    operator==(ConstIterator const& x, ConstIterator const& y);
    friend class SHAMap;
};
 
inline SHAMap::ConstIterator::ConstIterator(SHAMap const* map) : map_(map)
{
    XRPL_ASSERT(map_, "xrpl::SHAMap::ConstIterator::ConstIterator : non-null input");
 
    if (auto temp = map_->peekFirstItem(stack_))
        item_ = temp->peekItem().get();
}
 
inline SHAMap::ConstIterator::ConstIterator(SHAMap const* map, std::nullptr_t) : map_(map)
{
}
 
inline SHAMap::ConstIterator::ConstIterator(SHAMap const* map, pointer item, NodePathStack&& stack)
    : stack_(std::move(stack)), map_(map), item_(item)
{
}
 
inline SHAMap::ConstIterator::reference
SHAMap::ConstIterator::operator*() const
{
    return *item_;
}
 
inline SHAMap::ConstIterator::pointer
SHAMap::ConstIterator::operator->() const
{
    return item_;
}
 
inline SHAMap::ConstIterator&
SHAMap::ConstIterator::operator++()
{
    if (auto temp = map_->peekNextItem(item_->key(), stack_))
    {
        item_ = temp->peekItem().get();
    }
    else
    {
        item_ = nullptr;
    }
    return *this;
}
 
inline SHAMap::ConstIterator
SHAMap::ConstIterator::operator++(int)
{
    auto tmp = *this;
    ++(*this);
    return tmp;
}
 
inline bool
operator==(SHAMap::ConstIterator const& x, SHAMap::ConstIterator const& y)
{
    XRPL_ASSERT(
        x.map_ == y.map_,
        "xrpl::operator==(SHAMap::const_iterator, SHAMap::const_iterator) : "
        "inputs map do match");
    return x.item_ == y.item_;
}
 
inline SHAMap::ConstIterator
SHAMap::begin() const
{
    return ConstIterator(this);
}
 
inline SHAMap::ConstIterator
SHAMap::end() const
{
    return ConstIterator(this, nullptr);
}
 
}  // namespace xrpl