xrpld
Loading...
Searching...
No Matches
libxrpl/shamap/SHAMap.cpp
1#include <xrpl/shamap/SHAMap.h>
2
3#include <xrpl/basics/IntrusivePointer.h> // IWYU pragma: keep
4#include <xrpl/basics/IntrusivePointer.ipp> // IWYU pragma: keep
5#include <xrpl/basics/Log.h>
6#include <xrpl/basics/SHAMapHash.h>
7#include <xrpl/basics/Slice.h>
8#include <xrpl/basics/TaggedCache.ipp> // IWYU pragma: keep
9#include <xrpl/basics/base_uint.h>
10#include <xrpl/basics/contract.h>
11#include <xrpl/basics/safe_cast.h>
12#include <xrpl/beast/utility/instrumentation.h>
13#include <xrpl/nodestore/NodeObject.h>
14#include <xrpl/protocol/Serializer.h>
15#include <xrpl/shamap/Family.h>
16#include <xrpl/shamap/SHAMapAccountStateLeafNode.h>
17#include <xrpl/shamap/SHAMapInnerNode.h>
18#include <xrpl/shamap/SHAMapItem.h>
19#include <xrpl/shamap/SHAMapLeafNode.h>
20#include <xrpl/shamap/SHAMapMissingNode.h>
21#include <xrpl/shamap/SHAMapNodeID.h>
22#include <xrpl/shamap/SHAMapSyncFilter.h>
23#include <xrpl/shamap/SHAMapTreeNode.h>
24#include <xrpl/shamap/SHAMapTxLeafNode.h>
25#include <xrpl/shamap/SHAMapTxPlusMetaLeafNode.h>
26
27#include <boost/smart_ptr/intrusive_ptr.hpp>
28
29#include <atomic>
30#include <cstdint>
31#include <exception>
32#include <functional>
33#include <memory>
34#include <stack>
35#include <stdexcept>
36#include <string>
37#include <tuple>
38#include <type_traits>
39#include <utility>
40#include <vector>
41
42namespace xrpl {
43
45makeTypedLeaf(SHAMapNodeType type, boost::intrusive_ptr<SHAMapItem const> item, std::uint32_t owner)
46{
48 return intr_ptr::makeShared<SHAMapTxLeafNode>(std::move(item), owner);
49
51 return intr_ptr::makeShared<SHAMapTxPlusMetaLeafNode>(std::move(item), owner);
52
54 return intr_ptr::makeShared<SHAMapAccountStateLeafNode>(std::move(item), owner);
55
57 "Attempt to create leaf node of unknown type " +
59}
60
66
67// The `hash` parameter is unused. It is part of the interface so it's clear
68// from the parameters that this is the constructor to use when the hash is
69// known. The fact that the parameter is unused is an implementation detail that
70// should not change the interface.
76
77SHAMap::SHAMap(SHAMap const& other, bool isMutable)
78 : f_(other.f_)
79 , journal_(other.f_.journal())
80 , cowid_(other.cowid_ + 1)
81 , ledgerSeq_(other.ledgerSeq())
82 , root_(other.root_)
83 , type_(other.type_)
84 , backed_(other.backed_)
85{
86 // A snapshot shares the source's root, so Invalid carries over. Read once into a local, since
87 // the source's state can change while this runs.
88 auto const otherState = other.state();
89 auto const ownState = [&] {
90 if (otherState == SHAMapState::Invalid)
93 }();
94 state_.store(ownState, std::memory_order_release);
95
96 // If either map may change, they cannot share nodes
97 if ((ownState != SHAMapState::Immutable) || (otherState != SHAMapState::Immutable))
98 {
99 unshare();
100 }
101}
102
104SHAMap::snapShot(bool isMutable) const
105{
106 return std::make_shared<SHAMap>(*this, isMutable);
107}
108
109void
111{
112 // walk the tree up from through the inner nodes to the root_
113 // update hashes and links
114 // stack is a path of inner nodes up to, but not including, child
115 // child can be an inner node or a leaf
116
117 XRPL_ASSERT(
119 "xrpl::SHAMap::dirtyUp : valid state");
120 XRPL_ASSERT(child && (child->cowid() == cowid_), "xrpl::SHAMap::dirtyUp : valid child input");
121
122 while (!stack.empty())
123 {
124 auto node = intr_ptr::dynamicPointerCast<SHAMapInnerNode>(stack.top().first);
125 SHAMapNodeID const nodeID = stack.top().second;
126 stack.pop();
127 XRPL_ASSERT(node, "xrpl::SHAMap::dirtyUp : non-null node");
128
129 auto const branch = selectBranch(nodeID, target);
130
131 node = unshareNode(std::move(node), nodeID);
132 node->setChild(branch, std::move(child));
133
134 child = std::move(node);
135 }
136}
137
140{
141 XRPL_ASSERT(
142 stack == nullptr || stack->empty(), "xrpl::SHAMap::walkTowardsKey : empty stack input");
143 auto inNode = root_;
144 SHAMapNodeID nodeID;
145
146 // Every node on this walk lies on the path to `id`, so the stack can derive each ID from the
147 // branch `id` selects at the node above it.
148 auto const pushCurrent = [&] {
149 if (stack != nullptr)
150 stack->pushNode(inNode, id);
151 };
152
153 while (inNode->isInner())
154 {
155 pushCurrent();
156
157 auto& inner = safeDowncast<SHAMapInnerNode&>(*inNode);
158 auto const branch = selectBranch(nodeID, id);
159 if (inner.isEmptyBranch(branch))
160 return nullptr;
161
162 inNode = descendThrow(inner, branch);
163 nodeID = nodeID.getChildNodeID(branch);
164 }
165
166 pushCurrent();
167 return safeDowncast<SHAMapLeafNode*>(inNode.get());
168}
169
171SHAMap::findKey(UInt256 const& id) const
172{
173 SHAMapLeafNode* leaf = walkTowardsKey(id); // NOLINT(misc-const-correctness)
174 if ((leaf != nullptr) && leaf->peekItem()->key() != id)
175 leaf = nullptr;
176 return leaf;
177}
178
181{
182 XRPL_ASSERT(backed_, "xrpl::SHAMap::fetchNodeFromDB : is backed");
183 auto const obj = f_.db().fetchNodeObject(hash.asUInt256(), ledgerSeq());
184 return finishFetch(hash, obj);
185}
186
189{
190 XRPL_ASSERT(backed_, "xrpl::SHAMap::finishFetch : is backed");
191
192 try
193 {
194 if (!object)
195 {
196 // A missing node disproves full_, so withdraw it and report the gap. The exchange
197 // makes exactly one reader report it, and its acquire pairs with the release store in
198 // setFull(). It needs no release: the only other reader of full_ is this same path,
199 // and a reader that loses the exchange does nothing with what the winner did. The load
200 // ahead of it is relaxed, since all it decides is whether to try the exchange: a stale
201 // true costs one exchange that loses, and a stale false means another reader won, or
202 // setFull() is not visible yet and the gap goes unreported.
203 if (full_.load(std::memory_order_relaxed) &&
204 full_.exchange(false, std::memory_order_acquire))
205 {
206 f_.missingNodeAcquireBySeq(ledgerSeq(), hash.asUInt256());
207 }
208 return {};
209 }
210
211 auto node = SHAMapTreeNode::makeFromPrefix(makeSlice(object->getData()), hash);
212 if (node)
213 canonicalize(hash, node);
214 return node;
215 }
216 catch (std::runtime_error const& e)
217 {
218 JLOG(journal_.warn()) << "finishFetch exception: " << e.what();
219 }
220 catch (...)
221 {
222 JLOG(journal_.warn()) << "finishFetch exception: unknown exception: " << hash;
223 }
224
225 return {};
226}
227
228// See if a sync filter has a node
230SHAMap::checkFilter(SHAMapHash const& hash, SHAMapSyncFilter const* filter) const
231{
232 if (auto nodeData = filter->getNode(hash))
233 {
234 try
235 {
236 auto node = SHAMapTreeNode::makeFromPrefix(makeSlice(*nodeData), hash);
237 if (node)
238 {
239 filter->gotNode(true, hash, ledgerSeq(), std::move(*nodeData), node->getType());
240 if (backed_)
241 canonicalize(hash, node);
242 }
243 return node;
244 }
245 catch (std::exception const& x)
246 {
247 JLOG(f_.journal().warn()) << "Invalid node/data, hash=" << hash << ": " << x.what();
248 }
249 }
250 return {};
251}
252
253// Get a node without throwing
254// Used on maps where missing nodes are expected
256SHAMap::fetchNodeNT(SHAMapHash const& hash, SHAMapSyncFilter const* filter) const
257{
258 auto node = cacheLookup(hash);
259 if (node)
260 return node;
261
262 if (backed_)
263 {
264 node = fetchNodeFromDB(hash);
265 if (node)
266 {
267 canonicalize(hash, node);
268 return node;
269 }
270 }
271
272 if (filter != nullptr)
273 node = checkFilter(hash, filter);
274
275 return node;
276}
277
280{
281 auto node = cacheLookup(hash);
282
283 if (!node && backed_)
284 node = fetchNodeFromDB(hash);
285
286 return node;
287}
288
289// Throw if the node is missing
292{
293 auto node = fetchNodeNT(hash);
294
295 if (!node)
297
298 return node;
299}
300
302SHAMap::descendThrow(SHAMapInnerNode* parent, unsigned int branch) const
303{
304 SHAMapTreeNode* ret = descend(parent, branch); // NOLINT(misc-const-correctness)
305
306 if ((ret == nullptr) && !parent->isEmptyBranch(branch))
308
309 return ret;
310}
311
313SHAMap::descendThrow(SHAMapInnerNode& parent, unsigned int branch) const
314{
315 SHAMapTreeNodePtr ret = descend(parent, branch);
316
317 if (!ret && !parent.isEmptyBranch(branch))
319
320 return ret;
321}
322
324SHAMap::descend(SHAMapInnerNode* parent, unsigned int branch) const
325{
326 SHAMapTreeNode* ret = parent->getChildPointer(branch); // NOLINT(misc-const-correctness)
327 if ((ret != nullptr) || !backed_)
328 return ret;
329
330 SHAMapTreeNodePtr node = fetchNodeNT(parent->getChildHash(branch));
331 if (!node)
332 return nullptr;
333
334 node = parent->canonicalizeChild(branch, std::move(node));
335 return node.get();
336}
337
339SHAMap::descend(SHAMapInnerNode& parent, unsigned int branch) const
340{
341 SHAMapTreeNodePtr node = parent.getChild(branch);
342 if (node || !backed_)
343 return node;
344
345 node = fetchNode(parent.getChildHash(branch));
346 if (!node)
347 return {};
348
349 node = parent.canonicalizeChild(branch, std::move(node));
350 return node;
351}
352
353// Gets the node that would be hooked to this branch,
354// but doesn't hook it up.
356SHAMap::descendNoStore(SHAMapInnerNode& parent, unsigned int branch) const
357{
358 SHAMapTreeNodePtr ret = parent.getChild(branch);
359 if (!ret && backed_)
360 ret = fetchNode(parent.getChildHash(branch));
361 return ret;
362}
363
366 SHAMapInnerNode* parent,
367 SHAMapNodeID const& parentID,
368 unsigned int branch,
369 SHAMapSyncFilter const* filter) const
370{
371 XRPL_ASSERT(parent->isInner(), "xrpl::SHAMap::descend : valid parent input");
372 XRPL_ASSERT(branch < kBranchFactor, "xrpl::SHAMap::descend : valid branch input");
373 XRPL_ASSERT(
374 !parent->isEmptyBranch(branch), "xrpl::SHAMap::descend : parent branch is non-empty");
375
376 SHAMapTreeNode* child = parent->getChildPointer(branch); // NOLINT(misc-const-correctness)
377
378 if (child == nullptr)
379 {
380 auto const& childHash = parent->getChildHash(branch);
381 SHAMapTreeNodePtr childNode = fetchNodeNT(childHash, filter);
382
383 if (childNode)
384 {
385 childNode = parent->canonicalizeChild(branch, std::move(childNode));
386 child = childNode.get();
387 }
388 }
389
390 return std::make_pair(child, parentID.getChildNodeID(branch));
391}
392
395 SHAMapInnerNode* parent,
396 unsigned int branch,
397 SHAMapSyncFilter const* filter,
398 bool& pending,
399 DescendCallback&& callback) const
400{
401 pending = false;
402
403 SHAMapTreeNode* ret = parent->getChildPointer(branch); // NOLINT(misc-const-correctness)
404 if (ret != nullptr)
405 return ret;
406
407 auto const& hash = parent->getChildHash(branch);
408
409 auto ptr = cacheLookup(hash);
410 if (!ptr)
411 {
412 if (filter != nullptr)
413 ptr = checkFilter(hash, filter);
414
415 if (!ptr && backed_)
416 {
417 f_.db().asyncFetch(
418 hash.asUInt256(),
419 ledgerSeq(),
420 [this, hash, cb{std::move(callback)}](std::shared_ptr<NodeObject> const& object) {
421 auto const node = finishFetch(hash, object);
422 cb(node, hash);
423 });
424 pending = true;
425 return nullptr;
426 }
427 }
428
429 if (ptr)
430 ptr = parent->canonicalizeChild(branch, std::move(ptr));
431
432 return ptr.get();
433}
434
435template <class Node>
438{
439 // make sure the node is suitable for the intended operation (copy on write)
440 XRPL_ASSERT(node->cowid() <= cowid_, "xrpl::SHAMap::unshareNode : node valid for cowid");
441 if (node->cowid() != cowid_)
442 {
443 // have a CoW
444 XRPL_ASSERT(state() != SHAMapState::Immutable, "xrpl::SHAMap::unshareNode : not immutable");
445 node = intr_ptr::staticPointerCast<Node>(node->clone(cowid_));
446 if (nodeID.isRoot())
447 root_ = node;
448 }
449 return node;
450}
451
454{
455 XRPL_ASSERT(!stack.empty(), "xrpl::SHAMap::belowHelper : non-empty stack input");
456 if (auto const& top = stack.top().first; top->isLeaf())
457 return safeDowncast<SHAMapLeafNode*>(top.get());
458
459 // The stack owns the node/ID pairing, so descending is only ever "push the branch we took".
460 // `scanned` counts how many branches of the current node we have examined; the branch we look
461 // at is derived from it, so no index ever goes out of range. `inner` tracks the node on top of
462 // the stack, which keeps it alive, so it only needs recomputing after a push.
463 auto* inner = safeDowncast<SHAMapInnerNode*>(stack.top().first.get());
464 for (auto scanned = 0u; scanned < kBranchFactor;)
465 {
466 auto const childBranch =
467 (direction == BelowDirection::Last) ? (kBranchFactor - 1u - scanned) : scanned;
468
469 if (inner->isEmptyBranch(childBranch))
470 {
471 ++scanned; // scan next branch
472 continue;
473 }
474
475 stack.pushChild(descendThrow(*inner, childBranch), childBranch);
476
477 auto const& child = stack.top().first;
478 if (child->isLeaf())
479 return safeDowncast<SHAMapLeafNode*>(child.get());
480
481 inner = safeDowncast<SHAMapInnerNode*>(child.get());
482 scanned = 0u; // descend and restart the scan on the new node
483 }
484 return nullptr;
485}
486
487static boost::intrusive_ptr<SHAMapItem const> const kNoItem;
488
489boost::intrusive_ptr<SHAMapItem const> const&
491{
492 // If there is only one item below this node, return it
493
494 while (!node->isLeaf())
495 {
496 SHAMapTreeNode* nextNode = nullptr;
497 auto inner = safeDowncast<SHAMapInnerNode*>(node);
498 for (auto i = 0u; i < kBranchFactor; ++i)
499 {
500 if (!inner->isEmptyBranch(i))
501 {
502 if (nextNode != nullptr)
503 return kNoItem;
504
505 nextNode = descendThrow(inner, i);
506 }
507 }
508
509 if (nextNode == nullptr)
510 {
511 // LCOV_EXCL_START
512 UNREACHABLE("xrpl::SHAMap::onlyBelow : no next node");
513 return kNoItem;
514 // LCOV_EXCL_STOP
515 }
516
517 node = nextNode;
518 }
519
520 // An inner node must have at least one leaf
521 // below it, unless it's the root_
522 auto const leaf = safeDowncast<SHAMapLeafNode const*>(node);
523 XRPL_ASSERT(
524 leaf->peekItem() || (leaf == root_.get()), "xrpl::SHAMap::onlyBelow : valid inner node");
525 return leaf->peekItem();
526}
527
528SHAMapLeafNode const*
530{
531 XRPL_ASSERT(stack.empty(), "xrpl::SHAMap::peekFirstItem : empty stack input");
532 stack.pushRoot(root_);
534 if (node == nullptr)
535 {
536 stack.clear();
537 return nullptr;
538 }
539 return node;
540}
541
542SHAMapLeafNode const*
544{
545 XRPL_ASSERT(!stack.empty(), "xrpl::SHAMap::peekNextItem : non-empty stack input");
546 XRPL_ASSERT(stack.top().first->isLeaf(), "xrpl::SHAMap::peekNextItem : stack starts with leaf");
547 stack.pop();
548 while (!stack.empty())
549 {
550 auto const [node, nodeID] = stack.top();
551 XRPL_ASSERT(!node->isLeaf(), "xrpl::SHAMap::peekNextItem : another node is not leaf");
552 auto& inner = safeDowncast<SHAMapInnerNode&>(*node);
553 for (auto i = selectBranch(nodeID, id) + 1; i < kBranchFactor; ++i)
554 {
555 if (!inner.isEmptyBranch(i))
556 {
557 stack.pushChild(descendThrow(inner, i), i);
558 auto leaf = belowHelper(stack, BelowDirection::First);
559 if (leaf == nullptr)
561 XRPL_ASSERT(leaf->isLeaf(), "xrpl::SHAMap::peekNextItem : leaf is valid");
562 return leaf;
563 }
564 }
565 stack.pop();
566 }
567 // must be last item
568 return nullptr;
569}
570
571boost::intrusive_ptr<SHAMapItem const> const&
572SHAMap::peekItem(UInt256 const& id) const
573{
574 SHAMapLeafNode const* leaf = findKey(id);
575
576 if (leaf == nullptr)
577 return kNoItem;
578
579 return leaf->peekItem();
580}
581
582boost::intrusive_ptr<SHAMapItem const> const&
583SHAMap::peekItem(UInt256 const& id, SHAMapHash& hash) const
584{
585 SHAMapLeafNode const* leaf = findKey(id);
586
587 if (leaf == nullptr)
588 return kNoItem;
589
590 hash = leaf->getHash();
591 return leaf->peekItem();
592}
593
595SHAMap::boundHelper(UInt256 const& id, BelowDirection direction) const
596{
597 auto const searchingForward = direction == BelowDirection::First;
598
599 NodePathStack stack;
600 walkTowardsKey(id, &stack);
601 while (!stack.empty())
602 {
603 auto const [node, nodeID] = stack.top();
604 if (node->isLeaf())
605 {
606 auto const& item = safeDowncast<SHAMapLeafNode const&>(*node).peekItem();
607 if (searchingForward ? (item->key() > id) : (item->key() < id))
608 return ConstIterator(this, item.get(), std::move(stack));
609 }
610 else
611 {
612 auto& inner = safeDowncast<SHAMapInnerNode&>(*node);
613 auto const taken = selectBranch(nodeID, id);
614 auto const remaining = searchingForward ? (kBranchFactor - 1u - taken) : taken;
615
616 for (auto scanned = 0u; scanned < remaining; ++scanned)
617 {
618 auto const branch =
619 searchingForward ? (taken + 1u + scanned) : (taken - 1u - scanned);
620 if (inner.isEmptyBranch(branch))
621 continue;
622
623 stack.pushChild(descendThrow(inner, branch), branch);
624 auto const leaf = belowHelper(stack, direction);
625 if (leaf == nullptr)
627 return ConstIterator(this, leaf->peekItem().get(), std::move(stack));
628 }
629 }
630 stack.pop();
631 }
632 return end();
633}
634
637{
639}
640
643{
645}
646
647bool
648SHAMap::hasItem(UInt256 const& id) const
649{
650 return (findKey(id) != nullptr);
651}
652
653bool
655{
656 // delete the item with this ID
657 XRPL_ASSERT(state() != SHAMapState::Immutable, "xrpl::SHAMap::delItem : not immutable");
658
659 NodePathStack stack;
660 walkTowardsKey(id, &stack);
661
662 if (stack.empty())
664
665 auto const leaf = intr_ptr::dynamicPointerCast<SHAMapLeafNode>(stack.top().first);
666 stack.pop();
667
668 if (!leaf || (leaf->peekItem()->key() != id))
669 return false;
670
671 SHAMapNodeType const type = leaf->getType();
672
673 // What gets attached to the end of the chain (For now, nothing, since we deleted the leaf)
674 SHAMapTreeNodePtr prevNode;
675
676 while (!stack.empty())
677 {
678 auto node = intr_ptr::staticPointerCast<SHAMapInnerNode>(stack.top().first);
679 SHAMapNodeID const nodeID = stack.top().second;
680 stack.pop();
681
682 node = unshareNode(std::move(node), nodeID);
683 node->setChild(
684 selectBranch(nodeID, id), std::move(prevNode)); // NOLINT(bugprone-use-after-move)
685
686 XRPL_ASSERT(
687 not prevNode, // NOLINT(bugprone-use-after-move)
688 "xrpl::SHAMap::delItem : prevNode should be nullptr after std::move");
689
690 if (!nodeID.isRoot())
691 {
692 // we may have made this a node with 1 or 0 children
693 // And, if so, we need to remove this branch
694 auto const bc = node->getBranchCount();
695 if (bc == 0)
696 {
697 // no children below this branch
698 //
699 // Note: This is unnecessary due to the std::move above but left here for safety
700 prevNode = SHAMapTreeNodePtr{};
701 }
702 else if (bc == 1)
703 {
704 // If there's only one item, pull up on the thread
705 auto const item = onlyBelow(node.get());
706
707 if (item)
708 {
709 for (auto i = 0u; i < kBranchFactor; ++i)
710 {
711 if (!node->isEmptyBranch(i))
712 {
713 node->setChild(i, SHAMapTreeNodePtr{});
714 break;
715 }
716 }
717
718 prevNode = makeTypedLeaf(type, item, node->cowid());
719 }
720 else
721 {
722 prevNode = std::move(node);
723 }
724 }
725 else
726 {
727 // This node is now the end of the branch
728 prevNode = std::move(node);
729 }
730 }
731 }
732
733 return true;
734}
735
736bool
737SHAMap::addGiveItem(SHAMapNodeType type, boost::intrusive_ptr<SHAMapItem const> item)
738{
739 XRPL_ASSERT(state() != SHAMapState::Immutable, "xrpl::SHAMap::addGiveItem : not immutable");
740 XRPL_ASSERT(type != SHAMapNodeType::TnInner, "xrpl::SHAMap::addGiveItem : valid type input");
741
742 // add the specified item, does not update
743 UInt256 const tag = item->key();
744
745 NodePathStack stack;
746 walkTowardsKey(tag, &stack);
747
748 if (stack.empty())
750
751 auto [node, nodeID] = stack.top();
752 stack.pop();
753
754 if (node->isLeaf())
755 {
756 auto const leaf = intr_ptr::staticPointerCast<SHAMapLeafNode>(node);
757 if (leaf->peekItem()->key() == tag)
758 return false;
759 }
760 node = unshareNode(std::move(node), nodeID);
761 if (node->isInner())
762 {
763 // easy case, we end on an inner node
764 auto const inner = intr_ptr::staticPointerCast<SHAMapInnerNode>(node);
765 auto const branch = selectBranch(nodeID, tag);
766 XRPL_ASSERT(
767 inner->isEmptyBranch(branch), "xrpl::SHAMap::addGiveItem : inner branch is empty");
768 inner->setChild(branch, makeTypedLeaf(type, std::move(item), cowid_));
769 }
770 else
771 {
772 // this is a leaf node that has to be made an inner node holding two
773 // items
774 auto const leaf = intr_ptr::staticPointerCast<SHAMapLeafNode>(node);
775 auto otherItem = leaf->peekItem();
776 XRPL_ASSERT(
777 otherItem && (tag != otherItem->key()), "xrpl::SHAMap::addGiveItem : non-null item");
778
779 node = intr_ptr::makeShared<SHAMapInnerNode>(node->cowid());
780
781 auto b1 = 0u, b2 = 0u;
782
783 while ((b1 = selectBranch(nodeID, tag)) == (b2 = selectBranch(nodeID, otherItem->key())))
784 {
785 stack.pushNode(node, tag);
786
787 // we need a new inner node, since both go on same branch at this
788 // level
789 nodeID = nodeID.getChildNodeID(b1);
791 }
792
793 // we can add the two leaf nodes here
794 XRPL_ASSERT(node->isInner(), "xrpl::SHAMap::addGiveItem : node is inner");
795
796 auto inner = safeDowncast<SHAMapInnerNode*>(node.get());
797 inner->setChild(b1, makeTypedLeaf(type, std::move(item), cowid_));
798 inner->setChild(b2, makeTypedLeaf(type, std::move(otherItem), cowid_));
799 }
800
801 dirtyUp(stack, tag, node);
802 return true;
803}
804
805bool
806SHAMap::addItem(SHAMapNodeType type, boost::intrusive_ptr<SHAMapItem const> item)
807{
808 return addGiveItem(type, std::move(item));
809}
810
813{
814 auto hash = root_->getHash();
815 if (hash.isZero())
816 {
817 // NOLINTNEXTLINE(cppcoreguidelines-pro-type-const-cast)
818 const_cast<SHAMap&>(*this).unshare();
819 hash = root_->getHash();
820 }
821 return hash;
822}
823
824bool
825SHAMap::updateGiveItem(SHAMapNodeType type, boost::intrusive_ptr<SHAMapItem const> item)
826{
827 // can't change the tag but can change the hash
828 UInt256 const tag = item->key();
829
830 XRPL_ASSERT(state() != SHAMapState::Immutable, "xrpl::SHAMap::updateGiveItem : not immutable");
831
832 NodePathStack stack;
833 walkTowardsKey(tag, &stack);
834
835 if (stack.empty())
837
838 auto node = intr_ptr::dynamicPointerCast<SHAMapLeafNode>(stack.top().first);
839 auto const nodeID = stack.top().second;
840 stack.pop();
841
842 if (!node || (node->peekItem()->key() != tag))
843 {
844 // LCOV_EXCL_START
845 UNREACHABLE("xrpl::SHAMap::updateGiveItem : invalid node");
846 return false;
847 // LCOV_EXCL_STOP
848 }
849
850 if (node->getType() != type)
851 {
852 JLOG(journal_.fatal()) << "SHAMap::updateGiveItem: cross-type change!";
853 return false;
854 }
855
856 node = unshareNode(std::move(node), nodeID);
857
858 if (node->setItem(item))
859 dirtyUp(stack, tag, node);
860
861 return true;
862}
863
864bool
866{
867 if (hash == root_->getHash())
868 return true;
869
870 if (auto const stream = journal_.trace())
871 {
873 {
874 stream << "Fetch root TXN node " << hash;
875 }
876 else if (type_ == SHAMapType::STATE)
877 {
878 stream << "Fetch root STATE node " << hash;
879 }
880 else
881 {
882 stream << "Fetch root SHAMap node " << hash;
883 }
884 }
885
886 auto const newRoot = fetchNodeNT(hash, filter);
887
888 if (newRoot)
889 {
890 root_ = newRoot;
891 XRPL_ASSERT(root_->getHash() == hash, "xrpl::SHAMap::fetchRoot : root hash do match");
892 return true;
893 }
894
895 return false;
896}
897
913{
914 XRPL_ASSERT(node->cowid() == 0, "xrpl::SHAMap::writeNode : valid input node");
915 XRPL_ASSERT(backed_, "xrpl::SHAMap::writeNode : is backed");
916
917 canonicalize(node->getHash(), node);
918
919 Serializer s;
920 node->serializeWithPrefix(s);
921 f_.db().store(t, std::move(s.modData()), node->getHash().asUInt256(), ledgerSeq());
922 return node;
923}
924
925// We can't modify an inner node someone else might have a
926// pointer to because flushing modifies inner nodes -- it
927// makes them point to canonical/shared nodes.
928template <class Node>
931{
932 // A shared node should never need to be flushed
933 // because that would imply someone modified it
934 XRPL_ASSERT(node->cowid(), "xrpl::SHAMap::preFlushNode : valid input node");
935
936 if (node->cowid() != cowid_)
937 {
938 // Node is not uniquely ours, so unshare it before
939 // possibly modifying it
940 node = intr_ptr::staticPointerCast<Node>(node->clone(cowid_));
941 }
942 return node;
943}
944
945int
947{
948 // Don't share nodes with parent map
950}
951
952int
954{
955 // We only write back if this map is backed.
956 return walkSubTree(backed_, t);
957}
958
959int
961{
962 XRPL_ASSERT(!doWrite || backed_, "xrpl::SHAMap::walkSubTree : valid input");
963
964 int flushed = 0;
965
966 if (!root_ || (root_->cowid() == 0))
967 return flushed;
968
969 if (root_->isLeaf())
970 { // special case -- root_ is leaf
971 root_ = preFlushNode(std::move(root_));
972 root_->updateHash();
973 root_->unshare();
974
975 if (doWrite)
976 root_ = writeNode(t, std::move(root_));
977
978 return 1;
979 }
980
982
983 if (node->isEmpty())
984 { // replace empty root with a new empty root
986 return 1;
987 }
988
989 // Stack of {parent,index,child} pointers representing
990 // inner nodes we are in the process of flushing
991 using StackEntry = std::pair<intr_ptr::SharedPtr<SHAMapInnerNode>, unsigned int>;
993
994 node = preFlushNode(std::move(node));
995
996 auto pos = 0u;
997
998 // We can't flush an inner node until we flush its children
999 while (true)
1000 {
1001 while (pos < kBranchFactor)
1002 {
1003 if (node->isEmptyBranch(pos))
1004 {
1005 ++pos;
1006 }
1007 else
1008 {
1009 // No need to do I/O. If the node isn't linked,
1010 // it can't need to be flushed
1011 auto const branch = pos;
1012 auto child = node->getChild(pos++);
1013
1014 if (child && (child->cowid() != 0))
1015 {
1016 // This is a node that needs to be flushed
1017
1018 child = preFlushNode(std::move(child));
1019
1020 if (child->isInner())
1021 {
1022 // save our place and work on this node
1023
1024 stack.emplace(std::move(node), branch);
1026 pos = 0;
1027 }
1028 else
1029 {
1030 // flush this leaf
1031 ++flushed;
1032
1033 XRPL_ASSERT(
1034 node->cowid() == cowid_,
1035 "xrpl::SHAMap::walkSubTree : node cowid do "
1036 "match");
1037 child->updateHash();
1038 child->unshare();
1039
1040 if (doWrite)
1041 child = writeNode(t, std::move(child));
1042
1043 node->shareChild(branch, child);
1044 }
1045 }
1046 }
1047 }
1048
1049 // update the hash of this inner node
1050 node->updateHashDeep();
1051
1052 // This inner node can now be shared
1053 node->unshare();
1054
1055 if (doWrite)
1056 node = intr_ptr::staticPointerCast<SHAMapInnerNode>(writeNode(t, std::move(node)));
1057
1058 ++flushed;
1059
1060 if (stack.empty())
1061 break;
1062
1063 auto parent = std::move(stack.top().first);
1064 pos = stack.top().second;
1065 stack.pop();
1066
1067 // Hook this inner node to its parent
1068 XRPL_ASSERT(parent->cowid() == cowid_, "xrpl::SHAMap::walkSubTree : parent cowid do match");
1069 parent->shareChild(pos, node);
1070
1071 // Continue with parent's next child, if any
1072 node = std::move(parent);
1073 ++pos;
1074 }
1075
1076 // Last inner node is the new root_
1077 root_ = std::move(node);
1078
1079 return flushed;
1080}
1081
1082void
1083SHAMap::dump(bool hash) const
1084{
1085 int leafCount = 0;
1086 JLOG(journal_.info()) << " MAP Contains";
1087
1089 stack.emplace(root_.get(), SHAMapNodeID());
1090
1091 do
1092 {
1093 auto [node, nodeID] = stack.top();
1094 stack.pop();
1095
1096 JLOG(journal_.info()) << node->getString(nodeID);
1097 if (hash)
1098 {
1099 JLOG(journal_.info()) << "Hash: " << node->getHash();
1100 }
1101
1102 if (node->isInner())
1103 {
1104 auto inner = safeDowncast<SHAMapInnerNode*>(node);
1105 for (auto i = 0u; i < kBranchFactor; ++i)
1106 {
1107 if (!inner->isEmptyBranch(i))
1108 {
1109 auto child = inner->getChildPointer(i);
1110 if (child != nullptr)
1111 {
1112 XRPL_ASSERT(
1113 child->getHash() == inner->getChildHash(i),
1114 "xrpl::SHAMap::dump : child hash do match");
1115 stack.emplace(child, nodeID.getChildNodeID(i));
1116 }
1117 }
1118 }
1119 }
1120 else
1121 {
1122 ++leafCount;
1123 }
1124 } while (!stack.empty());
1125
1126 JLOG(journal_.info()) << leafCount << " resident leaves";
1127}
1128
1131{
1132 auto ret = f_.getTreeNodeCache()->fetch(hash.asUInt256());
1133 XRPL_ASSERT(!ret || !ret->cowid(), "xrpl::SHAMap::cacheLookup : not found or zero cowid");
1134 return ret;
1135}
1136
1137void
1139{
1140 XRPL_ASSERT(backed_, "xrpl::SHAMap::canonicalize : is backed");
1141 XRPL_ASSERT(node->cowid() == 0, "xrpl::SHAMap::canonicalize : valid node input");
1142 XRPL_ASSERT(node->getHash() == hash, "xrpl::SHAMap::canonicalize : node hash do match");
1143
1144 f_.getTreeNodeCache()->canonicalizeReplaceClient(hash.asUInt256(), node);
1145}
1146
1147void
1149{
1150 (void)getHash(); // update node hashes
1151 auto node = root_.get();
1152 XRPL_ASSERT(node, "xrpl::SHAMap::invariants : non-null root node");
1153 XRPL_ASSERT(!node->isLeaf(), "xrpl::SHAMap::invariants : root node is not leaf");
1154 NodePathStack stack;
1155 for (auto leaf = peekFirstItem(stack); leaf != nullptr;
1156 leaf = peekNextItem(leaf->peekItem()->key(), stack))
1157 ;
1158 node->invariants(true);
1159}
1160
1161} // namespace xrpl
UInt256 const & asUInt256() const
Definition SHAMapHash.h:26
SHAMapHash const & getChildHash(unsigned int branch) const
bool isInner() const override
Determines if this is an inner node.
SHAMapTreeNodePtr getChild(unsigned int branch)
SHAMapTreeNode * getChildPointer(unsigned int branch)
SHAMapTreeNodePtr canonicalizeChild(unsigned int branch, SHAMapTreeNodePtr node)
bool isEmptyBranch(unsigned int branch) const
boost::intrusive_ptr< SHAMapItem const > const & peekItem() const
Identifies a node inside a SHAMap.
SHAMapNodeID getChildNodeID(unsigned int branch) const
bool isRoot() const
virtual std::optional< Blob > getNode(SHAMapHash const &nodeHash) const =0
virtual void gotNode(bool fromFilter, SHAMapHash const &nodeHash, std::uint32_t ledgerSeq, Blob &&nodeData, SHAMapNodeType type) const =0
static SHAMapTreeNodePtr makeFromPrefix(Slice rawNode, SHAMapHash const &hash)
SHAMapHash const & getHash() const
Return the hash of this node.
virtual bool isLeaf() const =0
Determines if this is a leaf 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
void pushChild(SHAMapTreeNodePtr node, unsigned int branch)
Extend the path to the child of the current node reached by branch.
Definition SHAMap.h:587
void pushRoot(SHAMapTreeNodePtr node)
Start a path at the root of the map, whose ID is the zero-depth ID by definition.
Definition SHAMap.h:574
void pushNode(SHAMapTreeNodePtr node, UInt256 const &target)
Extend the path to a node lying on the path to target.
Definition SHAMap.h:611
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.
Definition SHAMap.h:150
SHAMapTreeNode * descendAsync(SHAMapInnerNode *parent, unsigned int branch, SHAMapSyncFilter const *filter, bool &pending, DescendCallback &&) const
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.
Definition SHAMap.h:123
SHAMapTreeNodePtr finishFetch(SHAMapHash const &hash, std::shared_ptr< NodeObject > const &object) const
SHAMapTreeNodePtr fetchNodeFromDB(SHAMapHash const &hash) const
Family & f_
Definition SHAMap.h:117
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 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 dirtyUp(NodePathStack &stack, UInt256 const &target, SHAMapTreeNodePtr terminal)
Update hashes up to the root.
SHAMapTreeNodePtr fetchNode(SHAMapHash const &hash) const
SHAMapLeafNode const * peekFirstItem(NodePathStack &stack) const
void dump(bool withHashes=false) const
beast::Journal journal_
Definition SHAMap.h:118
std::atomic< std::uint32_t > ledgerSeq_
The sequence of the ledger that this map references, if any.
Definition SHAMap.h:138
SHAMapTreeNode * descendThrow(SHAMapInnerNode *, unsigned int branch) const
bool backed_
Definition SHAMap.h:152
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.
Definition SHAMap.h:909
bool delItem(UInt256 const &id)
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)
SHAMapType const type_
Definition SHAMap.h:151
SHAMap()=delete
void canonicalize(SHAMapHash const &hash, SHAMapTreeNodePtr &) const
SHAMapTreeNodePtr fetchNodeNT(SHAMapHash const &hash) const
SHAMapTreeNodePtr checkFilter(SHAMapHash const &hash, SHAMapSyncFilter const *filter) const
std::uint32_t ledgerSeq() const
The sequence of the ledger this map references, read atomically.
Definition SHAMap.h:903
bool addGiveItem(SHAMapNodeType type, boost::intrusive_ptr< SHAMapItem const > item)
std::function< void(SHAMapTreeNodePtr, SHAMapHash const &)> DescendCallback
Definition SHAMap.h:770
SHAMapTreeNodePtr root_
Definition SHAMap.h:140
ConstIterator end() const
Definition SHAMap.h:1125
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.
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.
Definition SHAMap.h:160
int walkSubTree(bool doWrite, NodeObjectType t)
SHAMapHash getHash() const
boost::intrusive_ptr< SHAMapItem const > const & peekItem(UInt256 const &id) const
SHAMapLeafNode const * peekNextItem(UInt256 const &id, NodePathStack &stack) const
T * get() const
Get the raw pointer.
T emplace(T... args)
T empty(T... args)
T make_pair(T... args)
T make_shared(T... args)
SharedPtr< T > dynamicPointerCast(TT const &v)
SharedPtr< T > staticPointerCast(TT const &v)
SharedIntrusive< T > SharedPtr
SharedPtr< T > makeShared(A &&... args)
Use hash_* containers for keys that do not need a cryptographically secure hashing algorithm.
Definition algorithm.h:5
intr_ptr::SharedPtr< SHAMapTreeNode > SHAMapTreeNodePtr
SHAMapState
Describes the current state of a given SHAMap.
Definition SHAMap.h:45
@ Immutable
The map is set in stone and cannot be changed.
Definition SHAMap.h:58
@ Invalid
The map is known to not be valid.
Definition SHAMap.h:72
@ Synching
The map's hash is fixed but valid nodes may be missing and can be added.
Definition SHAMap.h:65
@ Modifying
The map is in flux and objects can be added and removed.
Definition SHAMap.h:51
NodeObjectType
The types of node objects.
Definition NodeObject.h:18
void logicError(std::string const &how) noexcept
Called when faulty logic causes a broken invariant.
intr_ptr::SharedPtr< SHAMapLeafNode > makeTypedLeaf(SHAMapNodeType type, boost::intrusive_ptr< SHAMapItem const > item, std::uint32_t owner)
Slice makeSlice(std::array< T, N > const &a)
Definition Slice.h:228
BaseUInt< 256 > UInt256
Definition base_uint.h:581
static boost::intrusive_ptr< SHAMapItem const > const kNoItem
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.
XRPL_NO_SANITIZE_ADDRESS void Throw(Args &&... args)
Definition contract.h:52
T pop(T... args)
T to_string(T... args)
T top(T... args)
T what(T... args)