1#include <xrpl/basics/Blob.h>
2#include <xrpl/basics/IntrusivePointer.h>
3#include <xrpl/basics/Log.h>
4#include <xrpl/basics/Slice.h>
5#include <xrpl/basics/base_uint.h>
6#include <xrpl/basics/random.h>
7#include <xrpl/basics/safe_cast.h>
8#include <xrpl/beast/utility/instrumentation.h>
9#include <xrpl/protocol/Serializer.h>
10#include <xrpl/shamap/SHAMap.h>
11#include <xrpl/shamap/SHAMapAddNode.h>
12#include <xrpl/shamap/SHAMapInnerNode.h>
13#include <xrpl/shamap/SHAMapItem.h>
14#include <xrpl/shamap/SHAMapLeafNode.h>
15#include <xrpl/shamap/SHAMapNodeID.h>
16#include <xrpl/shamap/SHAMapSyncFilter.h>
17#include <xrpl/shamap/SHAMapTreeNode.h>
19#include <boost/smart_ptr/intrusive_ptr.hpp>
46isLeafDepth(
unsigned int depth)
55 std::function<
void(boost::intrusive_ptr<SHAMapItem const>
const& item)>
const& leafFunction)
73 if (!
root_->isInner())
86 if (!node->isEmptyBranch(pos))
89 if (!function(*child))
99 while ((pos !=
kBranchFactor - 1u) && node->isEmptyBranch(pos + 1))
105 stack.
emplace(pos + 1, std::move(node));
137 if (
root_->getHash().isZero())
140 if ((map !=
nullptr) && (
root_->getHash() == map->
root_->getHash()))
146 if ((map ==
nullptr) || !map->
hasLeafNode(leaf->peekItem()->key(), leaf->getHash()))
156 while (!stack.
empty())
158 auto const [node, nodeID] = stack.
top();
162 if (!function(*node))
168 if (isLeafDepth(nodeID.getDepth()))
171 UNREACHABLE(
"xrpl::SHAMap::visitDifferences : inner node at leaf depth");
179 if (!node->isEmptyBranch(i))
181 auto const& childHash = node->getChildHash(i);
182 auto const childID = nodeID.getChildNodeID(i);
187 if ((map ==
nullptr) || !map->
hasInnerNode(childID, childHash))
192 if (!function(*next))
209 auto& firstChild = std::get<2>(se);
210 auto& currentChild = std::get<3>(se);
211 bool& fullBelow = std::get<4>(se);
215 auto const branch = (firstChild + currentChild++) %
kBranchFactor;
231 !
f_.getFullBelowCache()->touchIfExists(childHash.asUInt256()))
233 bool pending =
false;
241 std::unique_lock<std::mutex> const lock{mn.deferLock};
242 mn.
finishedReads.emplace_back(node, nodeID, branch, std::move(found));
251 else if (d ==
nullptr)
262 else if (d->isInner() && isLeafDepth(nodeID.
getDepth() + 1))
268 JLOG(
journal_.warn()) <<
"Inner node at branch " << branch <<
" below " << nodeID
269 <<
" makes the map invalid";
292 node->setFullBelowGen(mn.generation);
295 f_.getFullBelowCache()->insert(node->getHash().asUInt256());
320 auto parent = std::get<0>(deferredNode);
321 auto const& parentID = std::get<1>(deferredNode);
322 auto const branch = std::get<2>(deferredNode);
323 auto nodePtr = std::get<3>(deferredNode);
324 auto const& nodeHash = parent->getChildHash(branch);
328 nodePtr = parent->canonicalizeChild(branch, std::move(nodePtr));
338 mn.
missingNodes.emplace_back(parentID.getChildNodeID(branch), nodeHash.asUInt256());
351 XRPL_ASSERT(
root_->getHash().isNonZero(),
"xrpl::SHAMap::getMissingNodes : nonzero root hash");
352 XRPL_ASSERT(max > 0,
"xrpl::SHAMap::getMissingNodes : valid max input");
357 JLOG(
journal_.warn()) <<
"getMissingNodes called on an invalid map, root hash "
366 f_.getFullBelowCache()->getGeneration());
368 if (!
root_->isInner() ||
383 auto& node = std::get<0>(pos);
384 auto const& nextChild = std::get<3>(pos);
385 auto& fullBelow = std::get<4>(pos);
402 if ((node ==
nullptr) && !mn.
stack.empty())
405 bool const was = fullBelow;
407 pos = mn.
stack.top();
417 fullBelow = fullBelow && was;
419 XRPL_ASSERT(node,
"xrpl::SHAMap::getMissingNodes : first non-null node");
442 for (
auto const& [innerNode, nodeId] : mn.
resumes)
445 mn.
stack.emplace(innerNode, nodeId,
randInt(255), 0,
true);
451 if (!mn.
stack.empty())
454 pos = mn.
stack.top();
456 XRPL_ASSERT(node,
"xrpl::SHAMap::getMissingNodes : second non-null node");
464 }
while (node !=
nullptr);
487 auto node =
root_.get();
490 while ((node !=
nullptr) && node->isInner() && (nodeID.
getDepth() < wanted.
getDepth()))
494 if (inner->isEmptyBranch(branch))
500 if (node ==
nullptr || wanted != nodeID)
502 JLOG(
journal_.info()) <<
"peer requested node that is not in the map: " << wanted
503 <<
" but found " << nodeID;
509 JLOG(
journal_.warn()) <<
"peer requests empty node";
514 stack.
emplace(node, nodeID, depth);
518 while (!stack.
empty())
525 node->serializeForWire(s);
526 data.emplace_back(nodeID, node->isLeaf(), s.
getData());
533 auto const bc = inner->getBranchCount();
535 if ((depth > 0) || (bc == 1))
540 if (!inner->isEmptyBranch(i))
545 if (childNode->isInner() && ((depth > 1) || (bc == 1)))
549 stack.
emplace(childNode, childID, (bc > 1) ? (depth - 1) : depth);
551 else if (childNode->isInner() || fatLeaves)
555 childNode->serializeForWire(s);
556 data.emplace_back(childID, childNode->isLeaf(), s.
getData());
570 root_->serializeForWire(s);
579 XRPL_ASSERT(
cowid_ >= 1,
"xrpl::SHAMap::addRootNode : valid cowid");
580 XRPL_ASSERT(rootNode,
"xrpl::SHAMap::addRootNode : non-null root node");
584 if (
root_->getHash().isNonZero())
586 JLOG(
journal_.trace()) <<
"Got root node, already have one";
588 if (
root_->getHash() != hash)
590 JLOG(
journal_.warn()) <<
"Root node offered under hash " << hash
591 <<
", but the map holds " <<
root_->getHash();
598 if (rootNode->getHash() != hash)
600 JLOG(
journal_.warn()) <<
"Corrupt root node received: expected hash " << hash <<
", got "
601 << rootNode->getHash();
608 root_ = std::move(rootNode);
613 if (filter !=
nullptr)
616 root_->serializeWithPrefix(s);
630 XRPL_ASSERT(!nodeID.
isRoot(),
"xrpl::SHAMap::addKnownNode : valid node");
631 XRPL_ASSERT(treeNode,
"xrpl::SHAMap::addKnownNode : non-null tree node");
635 "xrpl::SHAMap::addKnownNode : leaf position consistent with node ID");
639 JLOG(
journal_.trace()) <<
"AddKnownNode while not synching";
643 auto const generation =
f_.getFullBelowCache()->getGeneration();
645 auto currNode =
root_.get();
647 while (currNode->isInner() &&
653 if (inner->isEmptyBranch(branch))
655 JLOG(
journal_.warn()) <<
"Add known node " << nodeID <<
" for empty branch " << branch
656 <<
" at " << currNodeID;
660 auto childHash = inner->getChildHash(branch);
666 if (!isLeafDepth(currNodeID.
getDepth() + 1) &&
667 f_.getFullBelowCache()->touchIfExists(childHash.asUInt256()))
672 auto prevNode = inner;
673 std::tie(currNode, currNodeID) =
descend(inner, currNodeID, branch, filter);
675 if (currNode !=
nullptr)
678 if (childHash != treeNode->getHash())
680 JLOG(
journal_.warn()) <<
"Corrupt node " << nodeID <<
" received: expected hash "
681 << childHash <<
", got " << treeNode->getHash();
691 bool const badDepth = treeNode->isInner() && isLeafDepth(currNodeID.
getDepth());
692 SOMETIMES(badDepth,
"xrpl::SHAMap::addKnownNode : map is invalid");
695 JLOG(
journal_.warn()) <<
"Node " << nodeID <<
" makes the map invalid at "
704 bool const badPosition = (currNodeID != nodeID);
705 SOMETIMES(badPosition,
"xrpl::SHAMap::addKnownNode : node ID does not match its position");
708 JLOG(
journal_.warn()) <<
"Unable to hook node " << nodeID <<
", stuck at "
716 treeNode = prevNode->canonicalizeChild(branch, std::move(treeNode));
718 if (filter !=
nullptr)
721 treeNode->serializeWithPrefix(s);
723 false, childHash,
ledgerSeq(), std::move(s.
modData()), treeNode->getType());
729 JLOG(
journal_.trace()) <<
"got node, already had it (late)";
741 while (!stack.
empty())
743 auto const [node, otherNode] = stack.
top();
746 if ((node ==
nullptr) || (otherNode ==
nullptr))
748 JLOG(
journal_.info()) <<
"unable to fetch node";
751 if (otherNode->getHash() != node->getHash())
753 JLOG(
journal_.warn()) <<
"node hash mismatch";
759 if (!otherNode->isLeaf())
763 if (nodePeek->key() != otherNodePeek->key())
765 if (nodePeek->slice() != otherNodePeek->slice())
768 else if (node->isInner())
770 if (!otherNode->isInner())
776 if (nodeInner->isEmptyBranch(i))
778 if (!otherInner->isEmptyBranch(i))
783 if (otherInner->isEmptyBranch(i))
786 auto next =
descend(nodeInner, i);
787 auto otherNext = other.
descend(otherInner, i);
788 if ((next ==
nullptr) || (otherNext ==
nullptr))
790 JLOG(
journal_.warn()) <<
"unable to fetch inner node";
793 stack.
emplace(next, otherNext);
808 auto node =
root_.get();
815 if (inner->isEmptyBranch(branch))
822 return node->isInner() && (node->getHash() == targetNodeHash);
831 auto node =
root_.get();
834 if (!node->isInner())
835 return node->getHash() == targetNodeHash;
845 UNREACHABLE(
"xrpl::SHAMap::hasLeafNode : inner node at leaf depth");
852 if (inner->isEmptyBranch(branch))
855 if (inner->getChildHash(branch) == targetNodeHash)
860 }
while (node->isInner());
874 JLOG(
journal_.debug()) <<
"no path to " << key;
878 if (
auto const& node = stack.
top().first; !node || node->isInner() ||
881 JLOG(
journal_.debug()) <<
"no path to " << key;
887 while (!stack.
empty())
890 stack.
top().first->serializeForWire(s);
895 JLOG(
journal_.debug()) <<
"getPath for key " << key <<
", path length " <<
path.size();
908 for (
auto rit =
path.rbegin(); rit !=
path.rend(); ++rit)
910 auto const& blob = *rit;
915 if (node->getHash() != hash)
925 isLeafDepth(depth),
"xrpl::SHAMap::verifyProofPath : inner at leaf depth");
926 if (isLeafDepth(depth))
942 return depth + 1 ==
path.size();
static SHAMapAddNode duplicate()
static SHAMapAddNode useful()
static SHAMapAddNode invalid()
SHAMapHash const & getChildHash(unsigned int branch) const
bool isEmptyBranch(unsigned int branch) const
Identifies a node inside a SHAMap.
bool isPrefixOf(UInt256 const &key) const
Test whether this node ID lies on the path to the given leaf key.
SHAMapNodeID getChildNodeID(unsigned int branch) const
UInt256 const & getNodeID() const
static SHAMapNodeID createID(unsigned int depth, UInt256 const &key)
Create a SHAMapNodeID of a node with the depth of the node and the key of a leaf.
unsigned int getDepth() const
virtual void gotNode(bool fromFilter, SHAMapHash const &nodeHash, std::uint32_t ledgerSeq, Blob &&nodeData, SHAMapNodeType type) const =0
static SHAMapTreeNodePtr makeFromWire(Slice rawNode)
virtual bool isInner() const =0
Determines if this is an inner node.
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
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
std::uint32_t cowid_
ID to distinguish this map for all others we're sharing nodes with.
static constexpr unsigned int kLeafDepth
The depth of the hash map: data is only present in the leaves.
bool getNodeFat(SHAMapNodeID const &wanted, std::vector< SHAMapNodeData > &data, bool fatLeaves, std::uint32_t depth) const
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
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.
bool hasInnerNode(SHAMapNodeID const &nodeID, SHAMapHash const &hash) const
Does this map have this inner node?
bool deepCompare(SHAMap &other) const
void gmnProcessNodes(MissingNodes &, MissingNodes::StackEntry &node)
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.
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.
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
void clearSynching()
Mark this map as no longer syncing, so it can be modified again.
std::uint32_t ledgerSeq() const
The sequence of the ledger this map references, read atomically.
std::vector< std::pair< SHAMapNodeID, UInt256 > > getMissingNodes(int maxNodes, SHAMapSyncFilter const *filter)
Check for nodes in the SHAMap not available.
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.
boost::intrusive_ptr< SHAMapItem const > const & peekItem(UInt256 const &id) const
static bool verifyProofPath(UInt256 const &rootHash, UInt256 const &key, std::vector< Blob > const &path)
Verify the proof path.
T * get() const
Get the raw pointer.
SharedPtr< T > staticPointerCast(TT const &v)
Use hash_* containers for keys that do not need a cryptographically secure hashing algorithm.
intr_ptr::SharedPtr< SHAMapTreeNode > SHAMapTreeNodePtr
Slice makeSlice(std::array< T, N > const &a)
UInt256 const & leafKey(SHAMapTreeNode const &node)
Return the key of the item held by a SHAMap leaf node.
Integral randInt(Engine &engine, Integral min, Integral max)
Return a uniformly distributed random integer.
Dest safeDowncast(Src *s) noexcept
unsigned int selectBranch(SHAMapNodeID const &id, UInt256 const &hash)
Returns the branch that would contain the given hash.
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
SHAMapSyncFilter const * filter
std::map< SHAMapInnerNode *, SHAMapNodeID > resumes
std::stack< StackEntry, std::deque< StackEntry > > stack
std::condition_variable deferCondVar