xrpld
Loading...
Searching...
No Matches
libxrpl/shamap/SHAMapSync.cpp
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>
18
19#include <boost/smart_ptr/intrusive_ptr.hpp>
20
21#include <cstdint>
22#include <exception>
23#include <functional>
24#include <iterator>
25#include <mutex>
26#include <optional>
27#include <stack>
28#include <tuple>
29#include <utility>
30#include <vector>
31
32namespace xrpl {
33
34namespace {
35
45[[nodiscard]] bool
46isLeafDepth(unsigned int depth)
47{
48 return depth >= SHAMap::kLeafDepth;
49}
50
51} // namespace
52
53void
55 std::function<void(boost::intrusive_ptr<SHAMapItem const> const& item)> const& leafFunction)
56 const
57{
58 visitNodes([&leafFunction](SHAMapTreeNode& node) {
59 if (!node.isInner())
60 leafFunction(safeDowncast<SHAMapLeafNode&>(node).peekItem());
61 return true;
62 });
63}
64
65void
66SHAMap::visitNodes(std::function<bool(SHAMapTreeNode&)> const& function) const
67{
68 if (!root_)
69 return;
70
71 function(*root_);
72
73 if (!root_->isInner())
74 return;
75
78
80 auto pos = 0u;
81
82 while (true)
83 {
84 while (pos < kBranchFactor)
85 {
86 if (!node->isEmptyBranch(pos))
87 {
88 SHAMapTreeNodePtr const child = descendNoStore(*node, pos);
89 if (!function(*child))
90 return;
91
92 if (child->isLeaf())
93 {
94 ++pos;
95 }
96 else
97 {
98 // If there are no more children, don't push this node
99 while ((pos != kBranchFactor - 1u) && node->isEmptyBranch(pos + 1))
100 ++pos;
101
102 if (pos != kBranchFactor - 1u)
103 {
104 // save next position to resume at
105 stack.emplace(pos + 1, std::move(node));
106 }
107
108 // descend to the child's first position
110 pos = 0;
111 }
112 }
113 else
114 {
115 ++pos; // move to next position
116 }
117 }
118
119 if (stack.empty())
120 break;
121
122 std::tie(pos, node) = stack.top();
123 stack.pop();
124 }
125}
126
127void
129 SHAMap const* map,
130 std::function<bool(SHAMapTreeNode const&)> const& function) const
131{
132 // Visit every node in this SHAMap that is not present
133 // in the specified SHAMap
134 if (!root_)
135 return;
136
137 if (root_->getHash().isZero())
138 return;
139
140 if ((map != nullptr) && (root_->getHash() == map->root_->getHash()))
141 return;
142
143 if (root_->isLeaf())
144 {
146 if ((map == nullptr) || !map->hasLeafNode(leaf->peekItem()->key(), leaf->getHash()))
147 function(*root_);
148 return;
149 }
150 // contains unexplored non-matching inner node entries
153
155
156 while (!stack.empty())
157 {
158 auto const [node, nodeID] = stack.top();
159 stack.pop();
160
161 // 1) Add this node to the pack
162 if (!function(*node))
163 return;
164
165 // Only a leaf belongs at kLeafDepth. The node is still reported, since the wire form
166 // carries no depth and the recipient hooks blobs by hash. Its children are skipped, since
167 // getChildNodeID has no answer past kLeafDepth.
168 if (isLeafDepth(nodeID.getDepth()))
169 {
170 // LCOV_EXCL_START
171 UNREACHABLE("xrpl::SHAMap::visitDifferences : inner node at leaf depth");
172 continue;
173 // LCOV_EXCL_STOP
174 }
175
176 // 2) push non-matching child inner nodes
177 for (auto i = 0u; i < kBranchFactor; ++i)
178 {
179 if (!node->isEmptyBranch(i))
180 {
181 auto const& childHash = node->getChildHash(i);
182 auto const childID = nodeID.getChildNodeID(i);
183 auto next = descendThrow(node, i);
184
185 if (next->isInner())
186 {
187 if ((map == nullptr) || !map->hasInnerNode(childID, childHash))
188 stack.emplace(safeDowncast<SHAMapInnerNode*>(next), childID);
189 }
190 else if ((map == nullptr) || !map->hasLeafNode(leafKey(*next), childHash))
191 {
192 if (!function(*next))
193 return;
194 }
195 }
196 }
197 }
198}
199
200// Starting at the position referred to by the specfied
201// StackEntry, process that node and its first resident
202// children, descending the SHAMap until we complete the
203// processing of a node.
204void
206{
207 SHAMapInnerNode*& node = std::get<0>(se);
208 SHAMapNodeID& nodeID = std::get<1>(se);
209 auto& firstChild = std::get<2>(se);
210 auto& currentChild = std::get<3>(se);
211 bool& fullBelow = std::get<4>(se);
212
213 while (currentChild < kBranchFactor)
214 {
215 auto const branch = (firstChild + currentChild++) % kBranchFactor;
216 if (node->isEmptyBranch(branch))
217 continue;
218
219 auto const& childHash = node->getChildHash(branch);
220
221 if (mn.missingHashes.contains(childHash))
222 {
223 // we already know this child node is missing
224 fullBelow = false;
225 }
226 // The depth test precedes the cache lookup for the same reason it does in addKnownNode():
227 // the cache is keyed by node hash and shared across maps, and a hash covers a node's
228 // children but not its depth. Skipping the shortcut forgoes an optimization only.
229 else if (
230 !backed_ || isLeafDepth(nodeID.getDepth() + 1) ||
231 !f_.getFullBelowCache()->touchIfExists(childHash.asUInt256()))
232 {
233 bool pending = false;
234 auto d = descendAsync(
235 node,
236 branch,
237 mn.filter,
238 pending,
239 [node, nodeID, branch, &mn](SHAMapTreeNodePtr found, SHAMapHash const&) {
240 // a read completed asynchronously
241 std::unique_lock<std::mutex> const lock{mn.deferLock};
242 mn.finishedReads.emplace_back(node, nodeID, branch, std::move(found));
244 });
245
246 if (pending)
247 {
248 fullBelow = false;
249 ++mn.deferred;
250 }
251 else if (d == nullptr)
252 {
253 // node is not in database
254
255 fullBelow = false; // for now, not known full below
256 mn.missingHashes.insert(childHash);
257 mn.missingNodes.emplace_back(nodeID.getChildNodeID(branch), childHash.asUInt256());
258
259 if (--mn.max <= 0)
260 return;
261 }
262 else if (d->isInner() && isLeafDepth(nodeID.getDepth() + 1))
263 {
264 // Only a leaf belongs that deep (see isLeafDepth and SHAMap::addKnownNode). A node
265 // resolved locally reaches the walk without passing through addKnownNode(), so the
266 // walk reaches this verdict itself. Ordered ahead of the full-below test below,
267 // which canonicalization shares across maps.
268 JLOG(journal_.warn()) << "Inner node at branch " << branch << " below " << nodeID
269 << " makes the map invalid";
270 setInvalid();
271 return;
272 }
273 else if (d->isInner() && !safeDowncast<SHAMapInnerNode*>(d)->isFullBelow(mn.generation))
274 {
275 mn.stack.push(se);
276
277 // Switch to processing the child node
279 nodeID = nodeID.getChildNodeID(branch);
280 firstChild = randInt(255);
281 currentChild = 0;
282 fullBelow = true;
283 }
284 }
285 }
286
287 // We have finished processing an inner node
288 // and thus (for now) all its children
289
290 if (fullBelow)
291 { // No partial node encountered below this node
292 node->setFullBelowGen(mn.generation);
293 if (backed_)
294 {
295 f_.getFullBelowCache()->insert(node->getHash().asUInt256());
296 }
297 }
298
299 node = nullptr;
300}
301
302// Wait for deferred reads to finish and
303// process their results
304void
306{
307 // Process all deferred reads
308 int complete = 0;
309 while (complete != mn.deferred)
310 {
311 MissingNodes::DeferredNode deferredNode;
312 {
314
315 while (mn.finishedReads.size() <= complete)
316 mn.deferCondVar.wait(lock);
317 deferredNode = std::move(mn.finishedReads[complete++]);
318 }
319
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);
325
326 if (nodePtr)
327 { // Got the node
328 nodePtr = parent->canonicalizeChild(branch, std::move(nodePtr));
329
330 // When we finish this stack, we need to restart
331 // with the parent of this node
332 mn.resumes[parent] = parentID;
333 }
334 else if ((mn.max > 0) && mn.missingHashes.insert(nodeHash).second)
335 {
336 // getChildNodeID() is safe here: gmnProcessNodes refuses to descend into an inner node
337 // at kLeafDepth, so a deferred parent sits at most one level above it.
338 mn.missingNodes.emplace_back(parentID.getChildNodeID(branch), nodeHash.asUInt256());
339 --mn.max;
340 }
341 }
342
343 mn.finishedReads.clear();
344 mn.finishedReads.reserve(mn.maxDefer);
345 mn.deferred = 0;
346}
347
350{
351 XRPL_ASSERT(root_->getHash().isNonZero(), "xrpl::SHAMap::getMissingNodes : nonzero root hash");
352 XRPL_ASSERT(max > 0, "xrpl::SHAMap::getMissingNodes : valid max input");
353
354 if (!isValid())
355 {
356 // The root node's own hash, since getHash() unshares the tree on a zero hash.
357 JLOG(journal_.warn()) << "getMissingNodes called on an invalid map, root hash "
358 << root_->getHash() << " seq " << ledgerSeq();
359 return {};
360 }
361
362 MissingNodes mn(
363 max,
364 filter,
365 512, // number of async reads per pass
366 f_.getFullBelowCache()->getGeneration());
367
368 if (!root_->isInner() ||
370 {
372 return std::move(mn.missingNodes);
373 }
374
375 // Start at the root.
376 // The firstChild value is selected randomly so if multiple threads
377 // are traversing the map, each thread will start at a different
378 // (randomly selected) inner node. This increases the likelihood
379 // that the two threads will produce different request sets (which is
380 // more efficient than sending identical requests).
383 auto& node = std::get<0>(pos);
384 auto const& nextChild = std::get<3>(pos);
385 auto& fullBelow = std::get<4>(pos);
386
387 // Traverse the map without blocking
388 do
389 {
390 while ((node != nullptr) && (mn.deferred <= mn.maxDefer))
391 {
392 gmnProcessNodes(mn, pos);
393
394 // The walk just invalidated the map. The loop stops descending here but falls through
395 // to the drain below, since every posted read must be drained while `mn` is alive.
396 if (!isValid())
397 break;
398
399 if (mn.max <= 0)
400 break;
401
402 if ((node == nullptr) && !mn.stack.empty())
403 {
404 // Pick up where we left off with this node's parent
405 bool const was = fullBelow; // was full below
406
407 pos = mn.stack.top();
408 mn.stack.pop();
409 if (nextChild == 0)
410 {
411 // This is a node we are processing for the first time
412 fullBelow = true;
413 }
414 else
415 {
416 // This is a node we are continuing to process
417 fullBelow = fullBelow && was; // was and still is
418 }
419 XRPL_ASSERT(node, "xrpl::SHAMap::getMissingNodes : first non-null node");
420 }
421 }
422
423 // We have either emptied the stack or
424 // posted as many deferred reads as we can
425 if (mn.deferred != 0)
427
428 // Reads are drained, so the map can be abandoned. What was collected belongs to a tree
429 // that cannot exist.
430 if (!isValid())
431 return {};
432
433 if (mn.max <= 0)
434 return std::move(mn.missingNodes);
435
436 if (node == nullptr)
437 { // We weren't in the middle of processing a node
438
439 if (mn.stack.empty() && !mn.resumes.empty())
440 {
441 // Recheck nodes we could not finish before
442 for (auto const& [innerNode, nodeId] : mn.resumes)
443 {
444 if (!innerNode->isFullBelow(mn.generation))
445 mn.stack.emplace(innerNode, nodeId, randInt(255), 0, true);
446 }
447
448 mn.resumes.clear();
449 }
450
451 if (!mn.stack.empty())
452 {
453 // Resume at the top of the stack
454 pos = mn.stack.top();
455 mn.stack.pop();
456 XRPL_ASSERT(node, "xrpl::SHAMap::getMissingNodes : second non-null node");
457 }
458 }
459
460 // node will only still be nullptr if
461 // we finished the current node, the stack is empty
462 // and we have no nodes to resume
463
464 } while (node != nullptr);
465
466 // addKnownNode() on another thread can write the verdict after the loop's own test, so the map
467 // is judged once more before the result is returned.
468 if (!isValid())
469 return {}; // LCOV_EXCL_LINE: only that other thread reaches this, so no test does
470
471 if (mn.missingNodes.empty())
473
474 return std::move(mn.missingNodes);
475}
476
477bool
479 SHAMapNodeID const& wanted,
481 bool fatLeaves,
482 std::uint32_t depth) const
483{
484 // Gets a node and some of its children
485 // to a specified depth
486
487 auto node = root_.get();
488 SHAMapNodeID nodeID;
489
490 while ((node != nullptr) && node->isInner() && (nodeID.getDepth() < wanted.getDepth()))
491 {
492 auto const branch = selectBranch(nodeID, wanted.getNodeID());
493 auto inner = safeDowncast<SHAMapInnerNode*>(node);
494 if (inner->isEmptyBranch(branch))
495 return false;
496 node = descendThrow(inner, branch);
497 nodeID = nodeID.getChildNodeID(branch);
498 }
499
500 if (node == nullptr || wanted != nodeID)
501 {
502 JLOG(journal_.info()) << "peer requested node that is not in the map: " << wanted
503 << " but found " << nodeID;
504 return false;
505 }
506
507 if (node->isInner() && safeDowncast<SHAMapInnerNode*>(node)->isEmpty())
508 {
509 JLOG(journal_.warn()) << "peer requests empty node";
510 return false;
511 }
512
514 stack.emplace(node, nodeID, depth);
515
516 Serializer s(8192);
517
518 while (!stack.empty())
519 {
520 std::tie(node, nodeID, depth) = stack.top();
521 stack.pop();
522
523 // Add this node to the reply
524 s.erase();
525 node->serializeForWire(s);
526 data.emplace_back(nodeID, node->isLeaf(), s.getData());
527
528 if (node->isInner())
529 {
530 // We descend inner nodes with only a single child
531 // without decrementing the depth
532 auto inner = safeDowncast<SHAMapInnerNode*>(node);
533 auto const bc = inner->getBranchCount();
534
535 if ((depth > 0) || (bc == 1))
536 {
537 // We need to process this node's children
538 for (auto i = 0u; i < kBranchFactor; ++i)
539 {
540 if (!inner->isEmptyBranch(i))
541 {
542 auto const childNode = descendThrow(inner, i);
543 auto const childID = nodeID.getChildNodeID(i);
544
545 if (childNode->isInner() && ((depth > 1) || (bc == 1)))
546 {
547 // If there's more than one child, reduce the depth
548 // If only one child, follow the chain
549 stack.emplace(childNode, childID, (bc > 1) ? (depth - 1) : depth);
550 }
551 else if (childNode->isInner() || fatLeaves)
552 {
553 // Just include this node
554 s.erase();
555 childNode->serializeForWire(s);
556 data.emplace_back(childID, childNode->isLeaf(), s.getData());
557 }
558 }
559 }
560 }
561 }
562 }
563
564 return true;
565}
566
567void
569{
570 root_->serializeForWire(s);
571}
572
575 SHAMapHash const& hash,
576 SHAMapTreeNodePtr rootNode,
577 SHAMapSyncFilter const* filter)
578{
579 XRPL_ASSERT(cowid_ >= 1, "xrpl::SHAMap::addRootNode : valid cowid");
580 XRPL_ASSERT(rootNode, "xrpl::SHAMap::addRootNode : non-null root node");
581
582 // A map syncs against one hash and installs a root once, so a root already held is a duplicate
583 // only once it hashes to the hash asked for.
584 if (root_->getHash().isNonZero())
585 {
586 JLOG(journal_.trace()) << "Got root node, already have one";
587
588 if (root_->getHash() != hash)
589 {
590 JLOG(journal_.warn()) << "Root node offered under hash " << hash
591 << ", but the map holds " << root_->getHash();
592 return SHAMapAddNode::invalid();
593 }
594
596 }
597
598 if (rootNode->getHash() != hash)
599 {
600 JLOG(journal_.warn()) << "Corrupt root node received: expected hash " << hash << ", got "
601 << rootNode->getHash();
602 return SHAMapAddNode::invalid();
603 }
604
605 if (backed_)
606 canonicalize(hash, rootNode);
607
608 root_ = std::move(rootNode);
609
610 if (root_->isLeaf())
612
613 if (filter != nullptr)
614 {
615 Serializer s;
616 root_->serializeWithPrefix(s);
617 filter->gotNode(
618 false, root_->getHash(), ledgerSeq(), std::move(s.modData()), root_->getType());
619 }
620
621 return SHAMapAddNode::useful();
622}
623
626 SHAMapNodeID const& nodeID,
627 SHAMapTreeNodePtr treeNode,
628 SHAMapSyncFilter const* filter)
629{
630 XRPL_ASSERT(!nodeID.isRoot(), "xrpl::SHAMap::addKnownNode : valid node");
631 XRPL_ASSERT(treeNode, "xrpl::SHAMap::addKnownNode : non-null tree node");
632 XRPL_ASSERT_IF(
633 treeNode->isLeaf(),
634 nodeID.isPrefixOf(leafKey(*treeNode)),
635 "xrpl::SHAMap::addKnownNode : leaf position consistent with node ID");
636
637 if (!isSynching())
638 {
639 JLOG(journal_.trace()) << "AddKnownNode while not synching";
641 }
642
643 auto const generation = f_.getFullBelowCache()->getGeneration();
644 SHAMapNodeID currNodeID;
645 auto currNode = root_.get();
646
647 while (currNode->isInner() &&
648 !safeDowncast<SHAMapInnerNode*>(currNode)->isFullBelow(generation) &&
649 (currNodeID.getDepth() < nodeID.getDepth()))
650 {
651 auto const branch = selectBranch(currNodeID, nodeID.getNodeID());
652 auto inner = safeDowncast<SHAMapInnerNode*>(currNode);
653 if (inner->isEmptyBranch(branch))
654 {
655 JLOG(journal_.warn()) << "Add known node " << nodeID << " for empty branch " << branch
656 << " at " << currNodeID;
657 return SHAMapAddNode::invalid();
658 }
659
660 auto childHash = inner->getChildHash(branch);
661
662 // Depth before the cache: the cache is keyed by node hash and shared across the family, and
663 // a hash covers a node's children but not its depth, so the same subtree can be cached as
664 // complete at one depth and reached at another. Skipping the shortcut only forgoes an
665 // optimization.
666 if (!isLeafDepth(currNodeID.getDepth() + 1) &&
667 f_.getFullBelowCache()->touchIfExists(childHash.asUInt256()))
668 {
670 }
671
672 auto prevNode = inner;
673 std::tie(currNode, currNodeID) = descend(inner, currNodeID, branch, filter);
674
675 if (currNode != nullptr)
676 continue;
677
678 if (childHash != treeNode->getHash())
679 {
680 JLOG(journal_.warn()) << "Corrupt node " << nodeID << " received: expected hash "
681 << childHash << ", got " << treeNode->getHash();
682 return SHAMapAddNode::invalid();
683 }
684
685 // Only leaves may sit at kLeafDepth (see isLeafDepth), so an inner node there makes the map
686 // impossible. The node is reported as bad data.
687 //
688 // Every node from the root down hash-verified to get here, so it is the requested root hash
689 // itself that commits to a shape no valid tree can have. The verdict belongs to that hash
690 // rather than to our copy of the tree.
691 bool const badDepth = treeNode->isInner() && isLeafDepth(currNodeID.getDepth());
692 SOMETIMES(badDepth, "xrpl::SHAMap::addKnownNode : map is invalid");
693 if (badDepth)
694 {
695 JLOG(journal_.warn()) << "Node " << nodeID << " makes the map invalid at "
696 << currNodeID;
697 setInvalid();
698 return SHAMapAddNode::invalid();
699 }
700
701 // The data hashes to the child at currNodeID but claims to belong at nodeID, so it is not
702 // the node that was asked for. Only the label is wrong, so the map stays sound and the node
703 // is still obtainable from another sender.
704 bool const badPosition = (currNodeID != nodeID);
705 SOMETIMES(badPosition, "xrpl::SHAMap::addKnownNode : node ID does not match its position");
706 if (badPosition)
707 {
708 JLOG(journal_.warn()) << "Unable to hook node " << nodeID << ", stuck at "
709 << currNodeID;
710 return SHAMapAddNode::invalid();
711 }
712
713 if (backed_)
714 canonicalize(childHash, treeNode);
715
716 treeNode = prevNode->canonicalizeChild(branch, std::move(treeNode));
717
718 if (filter != nullptr)
719 {
720 Serializer s;
721 treeNode->serializeWithPrefix(s);
722 filter->gotNode(
723 false, childHash, ledgerSeq(), std::move(s.modData()), treeNode->getType());
724 }
725
726 return SHAMapAddNode::useful();
727 }
728
729 JLOG(journal_.trace()) << "got node, already had it (late)";
731}
732
733bool
735{
736 // Intended for debug/test only
738
739 stack.emplace(root_.get(), other.root_.get());
740
741 while (!stack.empty())
742 {
743 auto const [node, otherNode] = stack.top();
744 stack.pop();
745
746 if ((node == nullptr) || (otherNode == nullptr))
747 {
748 JLOG(journal_.info()) << "unable to fetch node";
749 return false;
750 }
751 if (otherNode->getHash() != node->getHash())
752 {
753 JLOG(journal_.warn()) << "node hash mismatch";
754 return false;
755 }
756
757 if (node->isLeaf())
758 {
759 if (!otherNode->isLeaf())
760 return false;
761 auto& nodePeek = safeDowncast<SHAMapLeafNode*>(node)->peekItem();
762 auto& otherNodePeek = safeDowncast<SHAMapLeafNode*>(otherNode)->peekItem();
763 if (nodePeek->key() != otherNodePeek->key())
764 return false;
765 if (nodePeek->slice() != otherNodePeek->slice())
766 return false;
767 }
768 else if (node->isInner())
769 {
770 if (!otherNode->isInner())
771 return false;
772 auto nodeInner = safeDowncast<SHAMapInnerNode*>(node);
773 auto otherInner = safeDowncast<SHAMapInnerNode*>(otherNode);
774 for (auto i = 0u; i < kBranchFactor; ++i)
775 {
776 if (nodeInner->isEmptyBranch(i))
777 {
778 if (!otherInner->isEmptyBranch(i))
779 return false;
780 }
781 else
782 {
783 if (otherInner->isEmptyBranch(i))
784 return false;
785
786 auto next = descend(nodeInner, i);
787 auto otherNext = other.descend(otherInner, i);
788 if ((next == nullptr) || (otherNext == nullptr))
789 {
790 JLOG(journal_.warn()) << "unable to fetch inner node";
791 return false;
792 }
793 stack.emplace(next, otherNext);
794 }
795 }
796 }
797 }
798
799 return true;
800}
801
805bool
806SHAMap::hasInnerNode(SHAMapNodeID const& targetNodeID, SHAMapHash const& targetNodeHash) const
807{
808 auto node = root_.get();
809 SHAMapNodeID nodeID;
810
811 while (node->isInner() && (nodeID.getDepth() < targetNodeID.getDepth()))
812 {
813 auto const branch = selectBranch(nodeID, targetNodeID.getNodeID());
814 auto inner = safeDowncast<SHAMapInnerNode*>(node);
815 if (inner->isEmptyBranch(branch))
816 return false;
817
818 node = descendThrow(inner, branch);
819 nodeID = nodeID.getChildNodeID(branch);
820 }
821
822 return node->isInner() && (node->getHash() == targetNodeHash);
823}
824
828bool
829SHAMap::hasLeafNode(UInt256 const& tag, SHAMapHash const& targetNodeHash) const
830{
831 auto node = root_.get();
832 SHAMapNodeID nodeID;
833
834 if (!node->isInner()) // only one leaf node in the tree
835 return node->getHash() == targetNodeHash;
836
837 do
838 {
839 // Same kLeafDepth hazard as in visitDifferences above. That guard bounds the caller's own
840 // traversal, not the map queried here, and the loop below descends from this map's root
841 // independently, so this check is what keeps a malformed map from reaching getChildNodeID.
842 if (isLeafDepth(nodeID.getDepth()))
843 {
844 // LCOV_EXCL_START
845 UNREACHABLE("xrpl::SHAMap::hasLeafNode : inner node at leaf depth");
846 return false;
847 // LCOV_EXCL_STOP
848 }
849
850 auto const branch = selectBranch(nodeID, tag);
851 auto inner = safeDowncast<SHAMapInnerNode*>(node);
852 if (inner->isEmptyBranch(branch))
853 return false; // Dead end, node must not be here
854
855 if (inner->getChildHash(branch) == targetNodeHash) // Matching leaf, no need to retrieve it
856 return true;
857
858 node = descendThrow(inner, branch);
859 nodeID = nodeID.getChildNodeID(branch);
860 } while (node->isInner());
861
862 return false; // If this was a matching leaf, we would have caught it
863 // already
864}
865
868{
869 NodePathStack stack;
870 walkTowardsKey(key, &stack);
871
872 if (stack.empty())
873 {
874 JLOG(journal_.debug()) << "no path to " << key;
875 return {};
876 }
877
878 if (auto const& node = stack.top().first; !node || node->isInner() ||
879 intr_ptr::staticPointerCast<SHAMapLeafNode>(node)->peekItem()->key() != key)
880 {
881 JLOG(journal_.debug()) << "no path to " << key;
882 return {};
883 }
884
886 path.reserve(stack.size());
887 while (!stack.empty())
888 {
889 Serializer s;
890 stack.top().first->serializeForWire(s);
891 path.emplace_back(std::move(s.modData()));
892 stack.pop();
893 }
894
895 JLOG(journal_.debug()) << "getPath for key " << key << ", path length " << path.size();
896 return path;
897}
898
899bool
901{
902 if (path.empty() || path.size() > kLeafDepth + 1u)
903 return false;
904
905 SHAMapHash hash{rootHash};
906 try
907 {
908 for (auto rit = path.rbegin(); rit != path.rend(); ++rit)
909 {
910 auto const& blob = *rit;
911 auto const node = SHAMapTreeNode::makeFromWire(makeSlice(blob));
912 if (!node)
913 return false;
914 node->updateHash();
915 if (node->getHash() != hash)
916 return false;
917
918 auto const depth = static_cast<unsigned int>(std::distance(path.rbegin(), rit));
919 if (node->isInner())
920 {
921 // Nibbles run out at kLeafDepth, so only the leaf terminating the path may sit
922 // there. These nodes come off the wire, so a peer can still claim an inner one;
923 // reject it rather than passing this depth to selectBranch.
924 SOMETIMES(
925 isLeafDepth(depth), "xrpl::SHAMap::verifyProofPath : inner at leaf depth");
926 if (isLeafDepth(depth))
927 return false;
928
929 auto const nodeId = SHAMapNodeID::createID(depth, key);
930 hash = safeDowncast<SHAMapInnerNode*>(node.get())
931 ->getChildHash(selectBranch(nodeId, key));
932 }
933 else
934 {
935 // The hash chain up to rootHash proves this leaf sits where the path claims. Any
936 // leaf whose subtree hashes the same at every level above satisfies that chain, so
937 // the terminal leaf's own key is what ties the proof to `key`.
938 if (leafKey(*node) != key)
939 return false;
940
941 // should exhaust all the blobs now
942 return depth + 1 == path.size();
943 }
944 }
945 }
946 catch (std::exception const&)
947 {
948 // the data in the path may come from the network,
949 // exception could be thrown when parsing the data
950 return false;
951 }
952 return false;
953}
954
955} // namespace xrpl
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
bool isRoot() 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.
Definition SHAMap.h:536
std::pair< SHAMapTreeNodePtr, SHAMapNodeID > const & top() const
Definition SHAMap.h:551
std::size_t size() const
Definition SHAMap.h:545
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.
Definition SHAMap.h:123
static constexpr unsigned int kLeafDepth
The depth of the hash map: data is only present in the leaves.
Definition SHAMap.h:172
Family & f_
Definition SHAMap.h:117
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).
Definition SHAMap.h:167
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 isSynching() const
Definition SHAMap.h:947
bool deepCompare(SHAMap &other) const
void gmnProcessNodes(MissingNodes &, MissingNodes::StackEntry &node)
beast::Journal journal_
Definition SHAMap.h:118
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.
bool backed_
Definition SHAMap.h:152
void setInvalid()
Record that the map is provably not the one it claims to be.
Definition SHAMap.h:1000
bool isValid() const
Whether the map can still be the map it claims to be.
Definition SHAMap.h:994
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.
SHAMap()=delete
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.
Definition SHAMap.h:972
std::uint32_t ledgerSeq() const
The sequence of the ledger this map references, read atomically.
Definition SHAMap.h:903
SHAMapTreeNodePtr root_
Definition SHAMap.h:140
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.
Blob getData() const
Definition Serializer.h:278
T * get() const
Get the raw pointer.
T distance(T... args)
T emplace(T... args)
T empty(T... args)
SharedPtr< T > staticPointerCast(TT const &v)
Use hash_* containers for keys that do not need a cryptographically secure hashing algorithm.
Definition algorithm.h:5
intr_ptr::SharedPtr< SHAMapTreeNode > SHAMapTreeNodePtr
Slice makeSlice(std::array< T, N > const &a)
Definition Slice.h:228
BaseUInt< 256 > UInt256
Definition base_uint.h:581
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
Definition safe_cast.h:84
unsigned int selectBranch(SHAMapNodeID const &id, UInt256 const &hash)
Returns the branch that would contain the given hash.
T pop(T... args)
std::tuple< SHAMapInnerNode *, SHAMapNodeID, unsigned int, unsigned int, bool > StackEntry
Definition SHAMap.h:836
std::vector< std::pair< SHAMapNodeID, UInt256 > > missingNodes
Definition SHAMap.h:832
std::set< SHAMapHash > missingHashes
Definition SHAMap.h:833
std::tuple< SHAMapInnerNode *, SHAMapNodeID, unsigned int, SHAMapTreeNodePtr > DeferredNode
Definition SHAMap.h:851
std::vector< DeferredNode > finishedReads
Definition SHAMap.h:860
std::uint32_t generation
Definition SHAMap.h:829
SHAMapSyncFilter const * filter
Definition SHAMap.h:827
std::map< SHAMapInnerNode *, SHAMapNodeID > resumes
Definition SHAMap.h:864
std::stack< StackEntry, std::deque< StackEntry > > stack
Definition SHAMap.h:848
std::condition_variable deferCondVar
Definition SHAMap.h:859
T tie(T... args)
T top(T... args)