3#include <xrpl/basics/Blob.h>
4#include <xrpl/basics/IntrusivePointer.h>
5#include <xrpl/basics/Log.h>
6#include <xrpl/basics/SHAMapHash.h>
7#include <xrpl/basics/base_uint.h>
8#include <xrpl/beast/utility/Journal.h>
9#include <xrpl/beast/utility/instrumentation.h>
10#include <xrpl/nodestore/NodeObject.h>
11#include <xrpl/protocol/Serializer.h>
12#include <xrpl/shamap/Family.h>
13#include <xrpl/shamap/SHAMapAddNode.h>
14#include <xrpl/shamap/SHAMapInnerNode.h>
15#include <xrpl/shamap/SHAMapItem.h>
16#include <xrpl/shamap/SHAMapLeafNode.h>
17#include <xrpl/shamap/SHAMapMissingNode.h>
18#include <xrpl/shamap/SHAMapNodeID.h>
19#include <xrpl/shamap/SHAMapTreeNode.h>
288 boost::intrusive_ptr<SHAMapItem const>
const&
290 boost::intrusive_ptr<SHAMapItem const>
const&
521 dump(
bool withHashes =
false)
const;
553 XRPL_ASSERT(!
stack_.empty(),
"xrpl::SHAMap::NodePathStack::top : non-empty stack");
560 XRPL_ASSERT(!
stack_.empty(),
"xrpl::SHAMap::NodePathStack::pop : non-empty stack");
576 XRPL_ASSERT(
stack_.empty(),
"xrpl::SHAMap::NodePathStack::pushRoot : empty stack");
589 XRPL_ASSERT(node,
"xrpl::SHAMap::NodePathStack::pushChild : non-null node input");
591 !
stack_.empty(),
"xrpl::SHAMap::NodePathStack::pushChild : non-empty stack");
592 auto const childID =
stack_.top().second.getChildNodeID(branch);
596 "xrpl::SHAMap::NodePathStack::pushChild : inner node above leaf depth");
599 childID.isPrefixOf(
leafKey(*node)),
600 "xrpl::SHAMap::NodePathStack::pushChild : leaf key below branch");
601 stack_.emplace(std::move(node), childID);
716 template <
class Node>
723 template <
class Node>
794 boost::intrusive_ptr<SHAMapItem const>
const&
809 boost::intrusive_ptr<SHAMapItem const>
const& otherMapItem,
812 int& maxCount)
const;
893 full_.store(
true, std::memory_order_release);
899 ledgerSeq_.store(lseq, std::memory_order_relaxed);
905 return ledgerSeq_.load(std::memory_order_relaxed);
911 return state_.load(std::memory_order_acquire);
930 if (
state_.compare_exchange_weak(
931 expected, desired, std::memory_order_acq_rel, std::memory_order_acquire))
942 SOMETIMES(!
isValid(),
"xrpl::SHAMap::setImmutable : map is invalid");
966 UNREACHABLE(
"xrpl::SHAMap::setSynching : map is invalid");
978 if (
state_.compare_exchange_strong(
985 SOMETIMES(invalid,
"xrpl::SHAMap::clearSynching : map is invalid");
988 JLOG(
journal_.warn()) <<
"Refused to clear synching on an invalid map, root hash "
1059 XRPL_ASSERT(
map_,
"xrpl::SHAMap::ConstIterator::ConstIterator : non-null input");
1062 item_ = temp->peekItem().get();
1091 item_ = temp->peekItem().get();
1103 auto const tmp = *
this;
1113 "xrpl::operator==(SHAMap::const_iterator, SHAMap::const_iterator) : "
1114 "inputs map do match");
A generic endpoint for log messages.
static constexpr unsigned int kBranchFactor
Each inner node has 16 children (the 'radix tree' part of the map).
Identifies a node inside a SHAMap.
pointer operator->() const
ConstIterator(ConstIterator const &other)=default
value_type const & reference
ConstIterator & operator=(ConstIterator const &other)=default
friend bool operator==(ConstIterator const &x, ConstIterator const &y)
std::forward_iterator_tag iterator_category
ConstIterator & operator++()
value_type const * pointer
reference operator*() const
std::ptrdiff_t difference_type
A path from the root of the map down to some node, pairing each node with the ID naming its position.
std::pair< SHAMapTreeNodePtr, SHAMapNodeID > const & top() const
std::stack< std::pair< SHAMapTreeNodePtr, SHAMapNodeID > > stack_
void pushChild(SHAMapTreeNodePtr node, unsigned int branch)
Extend the path to the child of the current node reached by branch.
void pushRoot(SHAMapTreeNodePtr node)
Start a path at the root of the map, whose ID is the zero-depth ID by definition.
void pushNode(SHAMapTreeNodePtr node, UInt256 const &target)
Extend the path to a node lying on the path to target.
bool fetchRoot(SHAMapHash const &hash, SHAMapSyncFilter const *filter)
bool addItem(SHAMapNodeType type, boost::intrusive_ptr< SHAMapItem const > item)
std::atomic< SHAMapState > state_
The map's state.
Family const & family() const
bool setImmutable()
Mark this map as immutable, so it can no longer be modified.
SHAMapTreeNode * descendAsync(SHAMapInnerNode *parent, unsigned int branch, SHAMapSyncFilter const *filter, bool &pending, DescendCallback &&) const
bool hasLeafNode(UInt256 const &tag, SHAMapHash const &hash) const
Does this map have this leaf node?
SHAMapTreeNode * descend(SHAMapInnerNode *, unsigned int branch) const
ConstIterator upperBound(UInt256 const &id) const
Find the first item after the given item.
std::uint32_t cowid_
ID to distinguish this map for all others we're sharing nodes with.
SHAMapTreeNodePtr finishFetch(SHAMapHash const &hash, std::shared_ptr< NodeObject > const &object) const
void setLedgerSeq(std::uint32_t lseq)
static constexpr unsigned int kLeafDepth
The depth of the hash map: data is only present in the leaves.
void setFull(std::uint32_t ledgerSeq)
Mark this map as "should be full": the local server wants every node it references in durable storage...
SHAMapTreeNodePtr fetchNodeFromDB(SHAMapHash const &hash) const
bool getNodeFat(SHAMapNodeID const &wanted, std::vector< SHAMapNodeData > &data, bool fatLeaves, std::uint32_t depth) const
std::pair< boost::intrusive_ptr< SHAMapItem const >, boost::intrusive_ptr< SHAMapItem const > > DeltaItem
SHAMapTreeNodePtr cacheLookup(SHAMapHash const &hash) const
bool hasItem(UInt256 const &id) const
Does the tree have an item with the given ID?
int flushDirty(NodeObjectType t)
Flush modified nodes to the nodestore and convert them to shared.
static void gmnProcessDeferredReads(MissingNodes &)
static constexpr unsigned int kBranchFactor
Number of children each non-leaf node has (the 'radix tree' part of the map).
SHAMapTreeNodePtr descendNoStore(SHAMapInnerNode &, unsigned int branch) const
std::pair< boost::intrusive_ptr< SHAMapItem const >, boost::intrusive_ptr< SHAMapItem const > > DeltaRef
void dirtyUp(NodePathStack &stack, UInt256 const &target, SHAMapTreeNodePtr terminal)
Update hashes up to the root.
void visitDifferences(SHAMap const *have, std::function< bool(SHAMapTreeNode const &)> const &) const
Visit every node in this SHAMap that is not present in the specified SHAMap.
SHAMapTreeNodePtr fetchNode(SHAMapHash const &hash) const
bool walkMapParallel(std::vector< SHAMapMissingNode > &missingNodes, int maxMissing) const
void walkMap(std::vector< SHAMapMissingNode > &missingNodes, int maxMissing) const
void setSynching()
Mark this map as syncing, fixing its hash while still allowing missing nodes to be added.
bool hasInnerNode(SHAMapNodeID const &nodeID, SHAMapHash const &hash) const
Does this map have this inner node?
SHAMap(SHAMap const &)=delete
bool deepCompare(SHAMap &other) const
void gmnProcessNodes(MissingNodes &, MissingNodes::StackEntry &node)
SHAMap & operator=(SHAMap const &)=delete
SHAMapLeafNode const * peekFirstItem(NodePathStack &stack) const
void dump(bool withHashes=false) const
std::map< UInt256, DeltaItem > Delta
std::atomic< std::uint32_t > ledgerSeq_
The sequence of the ledger that this map references, if any.
bool compare(SHAMap const &otherMap, Delta &differences, int maxCount) const
SHAMapTreeNode * descendThrow(SHAMapInnerNode *, unsigned int branch) const
SHAMapAddNode addRootNode(SHAMapHash const &hash, SHAMapTreeNodePtr rootNode, SHAMapSyncFilter const *filter)
Add a root node to the SHAMap during synchronization.
void serializeRoot(Serializer &s) const
Serializes the root in a format appropriate for sending over the wire.
void setInvalid()
Record that the map is provably not the one it claims to be.
bool isValid() const
Whether the map can still be the map it claims to be.
std::shared_ptr< SHAMap > snapShot(bool isMutable) const
Return a new map that is a snapshot of this one.
int unshare()
Convert any modified nodes to shared.
SHAMapState state() const
The current state, read atomically.
bool delItem(UInt256 const &id)
void visitLeaves(std::function< void(boost::intrusive_ptr< SHAMapItem const > const &)> const &) const
Visit every leaf node in this SHAMap.
SHAMapLeafNode * walkTowardsKey(UInt256 const &id, NodePathStack *stack=nullptr) const
Walk towards the specified id, returning the node.
bool updateGiveItem(SHAMapNodeType type, boost::intrusive_ptr< SHAMapItem const > item)
SHAMapAddNode addKnownNode(SHAMapNodeID const &nodeID, SHAMapTreeNodePtr treeNode, SHAMapSyncFilter const *filter)
Add a known node at a specific position in the SHAMap during synchronization.
void canonicalize(SHAMapHash const &hash, SHAMapTreeNodePtr &) const
SHAMapTreeNodePtr fetchNodeNT(SHAMapHash const &hash) const
void clearSynching()
Mark this map as no longer syncing, so it can be modified again.
SHAMapTreeNodePtr checkFilter(SHAMapHash const &hash, SHAMapSyncFilter const *filter) const
std::uint32_t ledgerSeq() const
The sequence of the ledger this map references, read atomically.
bool addGiveItem(SHAMapNodeType type, boost::intrusive_ptr< SHAMapItem const > item)
std::function< void(SHAMapTreeNodePtr, SHAMapHash const &)> DescendCallback
ConstIterator end() const
SHAMapTreeNodePtr writeNode(NodeObjectType t, SHAMapTreeNodePtr node) const
write and canonicalize modified node
SHAMapLeafNode * belowHelper(NodePathStack &stack, BelowDirection direction) const
Returns the first or last item at or below the node already on top of stack, extending stack with the...
ConstIterator boundHelper(UInt256 const &id, BelowDirection direction) const
Returns the nearest item strictly past id, in the given direction.
ConstIterator lowerBound(UInt256 const &id) const
Find the object with the greatest object id smaller than the input id.
intr_ptr::SharedPtr< Node > preFlushNode(intr_ptr::SharedPtr< Node > node) const
prepare a node to be modified before flushing
SHAMapLeafNode * findKey(UInt256 const &id) const
Return nullptr if key not found.
intr_ptr::SharedPtr< Node > unshareNode(intr_ptr::SharedPtr< Node >, SHAMapNodeID const &nodeID)
Unshare the node, allowing it to be modified.
bool trySetState(SHAMapState desired)
Move the map to a new state, atomically.
boost::intrusive_ptr< SHAMapItem const > const & onlyBelow(SHAMapTreeNode *) const
If there is only one leaf below this node, get its contents.
std::atomic< bool > full_
Map is believed complete in database.
int walkSubTree(bool doWrite, NodeObjectType t)
std::vector< std::pair< SHAMapNodeID, UInt256 > > getMissingNodes(int maxNodes, SHAMapSyncFilter const *filter)
Check for nodes in the SHAMap not available.
SHAMapHash getHash() const
ConstIterator begin() const
void visitNodes(std::function< bool(SHAMapTreeNode &)> const &function) const
Visit every node in this SHAMap.
std::optional< std::vector< Blob > > getProofPath(UInt256 const &key) const
Get the proof path of the key.
bool walkBranch(SHAMapTreeNode *node, boost::intrusive_ptr< SHAMapItem const > const &otherMapItem, bool isFirstMap, Delta &differences, int &maxCount) const
boost::intrusive_ptr< SHAMapItem const > const & peekItem(UInt256 const &id) const
SHAMapLeafNode const * peekNextItem(UInt256 const &id, NodePathStack &stack) const
static bool verifyProofPath(UInt256 const &rootHash, UInt256 const &key, std::vector< Blob > const &path)
Verify the proof path.
SharedIntrusive< T > SharedPtr
Use hash_* containers for keys that do not need a cryptographically secure hashing algorithm.
intr_ptr::SharedPtr< SHAMapTreeNode > SHAMapTreeNodePtr
SHAMapState
Describes the current state of a given SHAMap.
@ Immutable
The map is set in stone and cannot be changed.
@ Invalid
The map is known to not be valid.
@ Synching
The map's hash is fixed but valid nodes may be missing and can be added.
@ Modifying
The map is in flux and objects can be added and removed.
constexpr bool operator==(BaseUInt< Bits, Tag > const &lhs, BaseUInt< Bits, Tag > const &rhs)
NodeObjectType
The types of node objects.
UInt256 const & leafKey(SHAMapTreeNode const &node)
Return the key of the item held by a SHAMap leaf node.
unsigned int selectBranch(SHAMapNodeID const &id, UInt256 const &hash)
Returns the branch that would contain the given hash.
std::vector< unsigned char > Blob
Storage for linear binary data.
@ Invalid
Timely, but invalid signature.
A SHAMap is both a radix tree with a fan-out of 16 and a Merkle tree.
std::tuple< SHAMapInnerNode *, SHAMapNodeID, unsigned int, unsigned int, bool > StackEntry
std::vector< std::pair< SHAMapNodeID, UInt256 > > missingNodes
std::set< SHAMapHash > missingHashes
std::tuple< SHAMapInnerNode *, SHAMapNodeID, unsigned int, SHAMapTreeNodePtr > DeferredNode
std::vector< DeferredNode > finishedReads
MissingNodes & operator=(MissingNodes const &)=delete
MissingNodes(int max, SHAMapSyncFilter const *filter, int maxDefer, std::uint32_t generation)
MissingNodes(MissingNodes const &)=delete
SHAMapSyncFilter const * filter
std::map< SHAMapInnerNode *, SHAMapNodeID > resumes
std::stack< StackEntry, std::deque< StackEntry > > stack
std::condition_variable deferCondVar