1#include <xrpl/shamap/SHAMap.h>
3#include <xrpl/basics/IntrusivePointer.h>
4#include <xrpl/basics/IntrusivePointer.ipp>
5#include <xrpl/basics/Log.h>
6#include <xrpl/basics/SHAMapHash.h>
7#include <xrpl/basics/Slice.h>
8#include <xrpl/basics/TaggedCache.ipp>
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>
27#include <boost/smart_ptr/intrusive_ptr.hpp>
57 "Attempt to create leaf node of unknown type " +
88 auto const otherState = other.
state();
89 auto const ownState = [&] {
94 state_.store(ownState, std::memory_order_release);
119 "xrpl::SHAMap::dirtyUp : valid state");
120 XRPL_ASSERT(child && (child->cowid() ==
cowid_),
"xrpl::SHAMap::dirtyUp : valid child input");
122 while (!stack.
empty())
127 XRPL_ASSERT(node,
"xrpl::SHAMap::dirtyUp : non-null node");
132 node->setChild(branch, std::move(child));
134 child = std::move(node);
142 stack ==
nullptr || stack->
empty(),
"xrpl::SHAMap::walkTowardsKey : empty stack input");
148 auto const pushCurrent = [&] {
149 if (stack !=
nullptr)
153 while (inNode->isInner())
159 if (inner.isEmptyBranch(branch))
174 if ((leaf !=
nullptr) && leaf->
peekItem()->key() !=
id)
182 XRPL_ASSERT(
backed_,
"xrpl::SHAMap::fetchNodeFromDB : is backed");
190 XRPL_ASSERT(
backed_,
"xrpl::SHAMap::finishFetch : is backed");
203 if (
full_.load(std::memory_order_relaxed) &&
204 full_.exchange(
false, std::memory_order_acquire))
218 JLOG(
journal_.warn()) <<
"finishFetch exception: " << e.
what();
222 JLOG(
journal_.warn()) <<
"finishFetch exception: unknown exception: " << hash;
232 if (
auto nodeData = filter->
getNode(hash))
239 filter->
gotNode(
true, hash,
ledgerSeq(), std::move(*nodeData), node->getType());
247 JLOG(
f_.journal().warn()) <<
"Invalid node/data, hash=" << hash <<
": " << x.
what();
272 if (filter !=
nullptr)
327 if ((ret !=
nullptr) || !
backed_)
371 XRPL_ASSERT(parent->
isInner(),
"xrpl::SHAMap::descend : valid parent input");
372 XRPL_ASSERT(branch <
kBranchFactor,
"xrpl::SHAMap::descend : valid branch input");
374 !parent->
isEmptyBranch(branch),
"xrpl::SHAMap::descend : parent branch is non-empty");
378 if (child ==
nullptr)
386 child = childNode.
get();
412 if (filter !=
nullptr)
440 XRPL_ASSERT(node->cowid() <=
cowid_,
"xrpl::SHAMap::unshareNode : node valid for cowid");
441 if (node->cowid() !=
cowid_)
455 XRPL_ASSERT(!stack.
empty(),
"xrpl::SHAMap::belowHelper : non-empty stack input");
456 if (
auto const& top = stack.
top().first; top->isLeaf())
466 auto const childBranch =
469 if (inner->isEmptyBranch(childBranch))
477 auto const& child = stack.
top().first;
487static boost::intrusive_ptr<SHAMapItem const>
const kNoItem;
489boost::intrusive_ptr<SHAMapItem const>
const&
500 if (!inner->isEmptyBranch(i))
502 if (nextNode !=
nullptr)
509 if (nextNode ==
nullptr)
512 UNREACHABLE(
"xrpl::SHAMap::onlyBelow : no next node");
524 leaf->peekItem() || (leaf ==
root_.get()),
"xrpl::SHAMap::onlyBelow : valid inner node");
525 return leaf->peekItem();
531 XRPL_ASSERT(stack.
empty(),
"xrpl::SHAMap::peekFirstItem : empty stack input");
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");
548 while (!stack.
empty())
550 auto const [node, nodeID] = stack.
top();
551 XRPL_ASSERT(!node->isLeaf(),
"xrpl::SHAMap::peekNextItem : another node is not leaf");
555 if (!inner.isEmptyBranch(i))
561 XRPL_ASSERT(leaf->isLeaf(),
"xrpl::SHAMap::peekNextItem : leaf is valid");
571boost::intrusive_ptr<SHAMapItem const>
const&
582boost::intrusive_ptr<SHAMapItem const>
const&
601 while (!stack.
empty())
603 auto const [node, nodeID] = stack.
top();
607 if (searchingForward ? (item->key() >
id) : (item->key() <
id))
614 auto const remaining = searchingForward ? (
kBranchFactor - 1u - taken) : taken;
616 for (
auto scanned = 0u; scanned < remaining; ++scanned)
619 searchingForward ? (taken + 1u + scanned) : (taken - 1u - scanned);
620 if (inner.isEmptyBranch(branch))
627 return ConstIterator(
this, leaf->peekItem().get(), std::move(stack));
650 return (
findKey(
id) !=
nullptr);
668 if (!leaf || (leaf->peekItem()->key() !=
id))
676 while (!stack.
empty())
688 "xrpl::SHAMap::delItem : prevNode should be nullptr after std::move");
694 auto const bc = node->getBranchCount();
711 if (!node->isEmptyBranch(i))
722 prevNode = std::move(node);
728 prevNode = std::move(node);
743 UInt256 const tag = item->key();
751 auto [node, nodeID] = stack.
top();
757 if (leaf->peekItem()->key() == tag)
767 inner->isEmptyBranch(branch),
"xrpl::SHAMap::addGiveItem : inner branch is empty");
775 auto otherItem = leaf->peekItem();
777 otherItem && (tag != otherItem->key()),
"xrpl::SHAMap::addGiveItem : non-null item");
781 auto b1 = 0u, b2 = 0u;
789 nodeID = nodeID.getChildNodeID(b1);
794 XRPL_ASSERT(node->isInner(),
"xrpl::SHAMap::addGiveItem : node is inner");
814 auto hash =
root_->getHash();
818 const_cast<SHAMap&
>(*this).unshare();
819 hash =
root_->getHash();
828 UInt256 const tag = item->key();
839 auto const nodeID = stack.
top().second;
842 if (!node || (node->peekItem()->key() != tag))
845 UNREACHABLE(
"xrpl::SHAMap::updateGiveItem : invalid node");
850 if (node->getType() != type)
852 JLOG(
journal_.fatal()) <<
"SHAMap::updateGiveItem: cross-type change!";
858 if (node->setItem(item))
867 if (hash ==
root_->getHash())
870 if (
auto const stream =
journal_.trace())
874 stream <<
"Fetch root TXN node " << hash;
878 stream <<
"Fetch root STATE node " << hash;
882 stream <<
"Fetch root SHAMap node " << hash;
891 XRPL_ASSERT(
root_->getHash() == hash,
"xrpl::SHAMap::fetchRoot : root hash do match");
914 XRPL_ASSERT(node->cowid() == 0,
"xrpl::SHAMap::writeNode : valid input node");
915 XRPL_ASSERT(
backed_,
"xrpl::SHAMap::writeNode : is backed");
920 node->serializeWithPrefix(s);
934 XRPL_ASSERT(node->cowid(),
"xrpl::SHAMap::preFlushNode : valid input node");
936 if (node->cowid() !=
cowid_)
962 XRPL_ASSERT(!doWrite ||
backed_,
"xrpl::SHAMap::walkSubTree : valid input");
1003 if (node->isEmptyBranch(pos))
1011 auto const branch = pos;
1012 auto child = node->getChild(pos++);
1014 if (child && (child->cowid() != 0))
1020 if (child->isInner())
1024 stack.
emplace(std::move(node), branch);
1035 "xrpl::SHAMap::walkSubTree : node cowid do "
1037 child->updateHash();
1043 node->shareChild(branch, child);
1050 node->updateHashDeep();
1063 auto parent = std::move(stack.
top().first);
1064 pos = stack.
top().second;
1068 XRPL_ASSERT(parent->cowid() ==
cowid_,
"xrpl::SHAMap::walkSubTree : parent cowid do match");
1069 parent->shareChild(pos, node);
1072 node = std::move(parent);
1077 root_ = std::move(node);
1086 JLOG(
journal_.info()) <<
" MAP Contains";
1093 auto [node, nodeID] = stack.
top();
1096 JLOG(
journal_.info()) << node->getString(nodeID);
1099 JLOG(
journal_.info()) <<
"Hash: " << node->getHash();
1102 if (node->isInner())
1107 if (!inner->isEmptyBranch(i))
1109 auto child = inner->getChildPointer(i);
1110 if (child !=
nullptr)
1113 child->getHash() == inner->getChildHash(i),
1114 "xrpl::SHAMap::dump : child hash do match");
1115 stack.
emplace(child, nodeID.getChildNodeID(i));
1124 }
while (!stack.
empty());
1126 JLOG(
journal_.info()) << leafCount <<
" resident leaves";
1132 auto ret =
f_.getTreeNodeCache()->fetch(hash.
asUInt256());
1133 XRPL_ASSERT(!ret || !ret->cowid(),
"xrpl::SHAMap::cacheLookup : not found or zero cowid");
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");
1144 f_.getTreeNodeCache()->canonicalizeReplaceClient(hash.
asUInt256(), node);
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");
1158 node->invariants(
true);
UInt256 const & asUInt256() const
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
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.
std::pair< SHAMapTreeNodePtr, SHAMapNodeID > const & top() const
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.
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.
SHAMapTreeNodePtr finishFetch(SHAMapHash const &hash, std::shared_ptr< NodeObject > const &object) const
SHAMapTreeNodePtr fetchNodeFromDB(SHAMapHash const &hash) const
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).
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
std::atomic< std::uint32_t > ledgerSeq_
The sequence of the ledger that this map references, if any.
SHAMapTreeNode * descendThrow(SHAMapInnerNode *, unsigned int branch) const
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)
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)
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.
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.
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)
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.
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.
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.
NodeObjectType
The types of node objects.
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)
static boost::intrusive_ptr< SHAMapItem const > const kNoItem
Dest safeDowncast(Src *s) noexcept
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)