xrpld
Loading...
Searching...
No Matches
SHAMap.h
1#pragma once
2
3#include <xrpl/basics/Blob.h>
4#include <xrpl/basics/IntrusivePointer.h>
5#include <xrpl/basics/Log.h>
6#include <xrpl/basics/SHAMapHash.h>
7#include <xrpl/basics/base_uint.h>
8#include <xrpl/beast/utility/Journal.h>
9#include <xrpl/beast/utility/instrumentation.h>
10#include <xrpl/nodestore/NodeObject.h>
11#include <xrpl/protocol/Serializer.h>
12#include <xrpl/shamap/Family.h>
13#include <xrpl/shamap/SHAMapAddNode.h>
14#include <xrpl/shamap/SHAMapInnerNode.h>
15#include <xrpl/shamap/SHAMapItem.h>
16#include <xrpl/shamap/SHAMapLeafNode.h>
17#include <xrpl/shamap/SHAMapMissingNode.h>
18#include <xrpl/shamap/SHAMapNodeID.h>
19#include <xrpl/shamap/SHAMapTreeNode.h>
20
21#include <atomic>
22#include <condition_variable>
23#include <cstddef>
24#include <cstdint>
25#include <deque>
26#include <functional>
27#include <iterator>
28#include <map>
29#include <memory>
30#include <mutex>
31#include <optional>
32#include <set>
33#include <stack>
34#include <tuple>
35#include <utility>
36#include <vector>
37
38namespace xrpl {
39
41
52
59
66
73};
74
99
105{
107 // The `data` field (a Blob, 8-byte aligned) needs 4 bytes of padding after the `nodeID` field
108 // (36 bytes, 4-byte aligned) regardless of what comes between them, so `isLeaf` costs nothing
109 // extra here. Moving it after `data` would add 8 bytes to the size of this struct instead.
110 bool isLeaf;
112};
113
115{
116private:
119
124
125 // ledgerSeq_, state_ and full_ are touched on the nodestore fetch path and on a
126 // getMissingNodes() walk, neither of which may block, so pin them lock-free.
130
139
141
152 bool backed_ = true; // Map is backed by the database
153
160 mutable std::atomic<bool> full_ = false;
161
162public:
167 static constexpr unsigned int kBranchFactor = SHAMapInnerNode::kBranchFactor;
168
172 static constexpr unsigned int kLeafDepth = 64;
173
174 using DeltaItem =
175 std::pair<boost::intrusive_ptr<SHAMapItem const>, boost::intrusive_ptr<SHAMapItem const>>;
177
178 SHAMap() = delete;
179 SHAMap(SHAMap const&) = delete;
180 SHAMap&
181 operator=(SHAMap const&) = delete;
182
191 SHAMap(SHAMap const& other, bool isMutable);
192
193 // build new map
194 SHAMap(SHAMapType t, Family& f);
195
196 SHAMap(SHAMapType t, UInt256 const& hash, Family& f);
197
198 ~SHAMap() = default;
199
200 Family const&
201 family() const
202 {
203 return f_;
204 }
205
206 Family&
208 {
209 return f_;
210 }
211
212 //--------------------------------------------------------------------------
213
219 class ConstIterator;
220
221 ConstIterator
222 begin() const;
223 ConstIterator
224 end() const;
225
226 //--------------------------------------------------------------------------
227
238 snapShot(bool isMutable) const;
239
253 void
255
256 void
258
259 bool
260 fetchRoot(SHAMapHash const& hash, SHAMapSyncFilter const* filter);
261
262 // normal hash access functions
263
267 bool
268 hasItem(UInt256 const& id) const;
269
270 bool
271 delItem(UInt256 const& id);
272
273 bool
274 addItem(SHAMapNodeType type, boost::intrusive_ptr<SHAMapItem const> item);
275
277 getHash() const;
278
279 // save a copy if you have a temporary anyway
280 bool
281 updateGiveItem(SHAMapNodeType type, boost::intrusive_ptr<SHAMapItem const> item);
282
283 bool
284 addGiveItem(SHAMapNodeType type, boost::intrusive_ptr<SHAMapItem const> item);
285
286 // Save a copy if you need to extend the life
287 // of the SHAMapItem beyond this SHAMap
288 boost::intrusive_ptr<SHAMapItem const> const&
289 peekItem(UInt256 const& id) const;
290 boost::intrusive_ptr<SHAMapItem const> const&
291 peekItem(UInt256 const& id, SHAMapHash& hash) const;
292
293 // traverse functions
301 ConstIterator
302 upperBound(UInt256 const& id) const;
303
311 ConstIterator
312 lowerBound(UInt256 const& id) const;
313
320 void
321 visitNodes(std::function<bool(SHAMapTreeNode&)> const& function) const;
322
330 void
331 visitDifferences(SHAMap const* have, std::function<bool(SHAMapTreeNode const&)> const&) const;
332
338 void
339 visitLeaves(std::function<void(boost::intrusive_ptr<SHAMapItem const> const&)> const&) const;
340
341 // comparison/sync functions
342
359 getMissingNodes(int maxNodes, SHAMapSyncFilter const* filter);
360
361 [[nodiscard]] bool
363 SHAMapNodeID const& wanted,
365 bool fatLeaves,
366 std::uint32_t depth) const;
367
375 getProofPath(UInt256 const& key) const;
376
384 static bool
385 verifyProofPath(UInt256 const& rootHash, UInt256 const& key, std::vector<Blob> const& path);
386
390 void
391 serializeRoot(Serializer& s) const;
392
412 addRootNode(SHAMapHash const& hash, SHAMapTreeNodePtr rootNode, SHAMapSyncFilter const* filter);
413
436 SHAMapNodeID const& nodeID,
437 SHAMapTreeNodePtr treeNode,
438 SHAMapSyncFilter const* filter);
439
446 [[nodiscard]] bool
447 setImmutable();
448
453 [[nodiscard]] bool
454 isSynching() const;
455
459 [[nodiscard]] bool
460 isImmutable() const;
461
470 void
471 setSynching();
472
479 void
481
490 [[nodiscard]] bool
491 isValid() const;
492
493 // caution: otherMap must be accessed only by this function
494 // return value: true=successfully completed, false=too different
495 bool
496 compare(SHAMap const& otherMap, Delta& differences, int maxCount) const;
497
501 int
502 unshare();
503
507 int
509
510 void
511 walkMap(std::vector<SHAMapMissingNode>& missingNodes, int maxMissing) const;
512 bool
513 walkMapParallel(std::vector<SHAMapMissingNode>& missingNodes, int maxMissing) const;
514 bool
515 deepCompare(SHAMap& other) const; // Intended for debug/test only
516
517 void
518 setUnbacked();
519
520 void
521 dump(bool withHashes = false) const;
522 void
523 invariants() const;
524
525private:
536 {
537 public:
538 [[nodiscard]] bool
539 empty() const
540 {
541 return stack_.empty();
542 }
543
544 [[nodiscard]] std::size_t
545 size() const
546 {
547 return stack_.size();
548 }
549
551 top() const
552 {
553 XRPL_ASSERT(!stack_.empty(), "xrpl::SHAMap::NodePathStack::top : non-empty stack");
554 return stack_.top();
555 }
556
557 void
559 {
560 XRPL_ASSERT(!stack_.empty(), "xrpl::SHAMap::NodePathStack::pop : non-empty stack");
561 stack_.pop();
562 }
563
564 void
566 {
567 stack_ = {};
568 }
569
573 void
575 {
576 XRPL_ASSERT(stack_.empty(), "xrpl::SHAMap::NodePathStack::pushRoot : empty stack");
577 stack_.emplace(std::move(node), SHAMapNodeID{});
578 }
579
586 void
587 pushChild(SHAMapTreeNodePtr node, unsigned int branch)
588 {
589 XRPL_ASSERT(node, "xrpl::SHAMap::NodePathStack::pushChild : non-null node input");
590 XRPL_ASSERT(
591 !stack_.empty(), "xrpl::SHAMap::NodePathStack::pushChild : non-empty stack");
592 auto const childID = stack_.top().second.getChildNodeID(branch);
593 XRPL_ASSERT_IF(
594 node->isInner(),
595 childID.getDepth() < kLeafDepth,
596 "xrpl::SHAMap::NodePathStack::pushChild : inner node above leaf depth");
597 XRPL_ASSERT_IF(
598 node->isLeaf(),
599 childID.isPrefixOf(leafKey(*node)),
600 "xrpl::SHAMap::NodePathStack::pushChild : leaf key below branch");
601 stack_.emplace(std::move(node), childID);
602 }
603
610 void
611 pushNode(SHAMapTreeNodePtr node, UInt256 const& target)
612 {
613 if (stack_.empty())
614 {
615 pushRoot(std::move(node));
616 }
617 else
618 {
619 pushChild(std::move(node), selectBranch(stack_.top().second, target));
620 }
621 }
622
623 private:
625 };
626
627 using DeltaRef =
628 std::pair<boost::intrusive_ptr<SHAMapItem const>, boost::intrusive_ptr<SHAMapItem const>>;
629
635 [[nodiscard]] std::uint32_t
636 ledgerSeq() const;
637
646 [[nodiscard]] SHAMapState
647 state() const;
648
656 void
657 setInvalid();
658
672 bool
673 trySetState(SHAMapState desired);
674
675 // tree node cache operations
677 cacheLookup(SHAMapHash const& hash) const;
678
679 void
680 canonicalize(SHAMapHash const& hash, SHAMapTreeNodePtr&) const;
681
682 // database operations
684 fetchNodeFromDB(SHAMapHash const& hash) const;
686 fetchNodeNT(SHAMapHash const& hash) const;
688 fetchNodeNT(SHAMapHash const& hash, SHAMapSyncFilter const* filter) const;
690 fetchNode(SHAMapHash const& hash) const;
692 checkFilter(SHAMapHash const& hash, SHAMapSyncFilter const* filter) const;
693
697 void
698 dirtyUp(NodePathStack& stack, UInt256 const& target, SHAMapTreeNodePtr terminal);
699
706 walkTowardsKey(UInt256 const& id, NodePathStack* stack = nullptr) const;
711 findKey(UInt256 const& id) const;
712
716 template <class Node>
719
723 template <class Node>
726
732
733 // direction in which a scan walks an inner node's branches
734 enum class BelowDirection { First, Last };
735
741 belowHelper(NodePathStack& stack, BelowDirection direction) const;
742
754 ConstIterator
755 boundHelper(UInt256 const& id, BelowDirection direction) const;
756
757 // Simple descent
758 // Get a child of the specified node
760 descend(SHAMapInnerNode*, unsigned int branch) const;
762 descendThrow(SHAMapInnerNode*, unsigned int branch) const;
764 descend(SHAMapInnerNode&, unsigned int branch) const;
766 descendThrow(SHAMapInnerNode&, unsigned int branch) const;
767
768 // Descend with filter
769 // If pending, callback is called as if it called fetchNodeNT
773 SHAMapInnerNode* parent,
774 unsigned int branch,
775 SHAMapSyncFilter const* filter,
776 bool& pending,
777 DescendCallback&&) const;
778
780 descend(
781 SHAMapInnerNode* parent,
782 SHAMapNodeID const& parentID,
783 unsigned int branch,
784 SHAMapSyncFilter const* filter) const;
785
786 // Non-storing
787 // Does not hook the returned node to its parent
789 descendNoStore(SHAMapInnerNode&, unsigned int branch) const;
790
794 boost::intrusive_ptr<SHAMapItem const> const&
796
797 bool
798 hasInnerNode(SHAMapNodeID const& nodeID, SHAMapHash const& hash) const;
799 bool
800 hasLeafNode(UInt256 const& tag, SHAMapHash const& hash) const;
801
802 SHAMapLeafNode const*
803 peekFirstItem(NodePathStack& stack) const;
804 SHAMapLeafNode const*
805 peekNextItem(UInt256 const& id, NodePathStack& stack) const;
806 bool
808 SHAMapTreeNode* node,
809 boost::intrusive_ptr<SHAMapItem const> const& otherMapItem,
810 bool isFirstMap,
811 Delta& differences,
812 int& maxCount) const;
813 int
814 walkSubTree(bool doWrite, NodeObjectType t);
815
816 // Structure to track information about call to
817 // getMissingNodes while it's in progress
819 {
820 MissingNodes() = delete;
821 MissingNodes(MissingNodes const&) = delete;
823 operator=(MissingNodes const&) = delete;
824
825 // basic parameters
826 int max;
828 int const maxDefer;
830
831 // nodes we have discovered to be missing
834
835 // nodes we are in the process of traversing
837 SHAMapInnerNode*, // pointer to the node
838 SHAMapNodeID, // the node's ID
839 unsigned int, // which child we check first
840 unsigned int, // which child we check next
841 bool>; // whether we've found any missing children yet
842
843 // We explicitly choose to specify the use of std::deque here, because
844 // we need to ensure that pointers and/or references to existing
845 // elements will not be invalidated during the course of element
846 // insertion and removal. Containers that do not offer this guarantee,
847 // such as std::vector, can't be used here.
849
850 // nodes we may have acquired from deferred reads
852 SHAMapInnerNode*, // parent node
853 SHAMapNodeID, // parent node ID
854 unsigned int, // branch
855 SHAMapTreeNodePtr>; // node
856
861
862 // nodes we need to resume after we get their children from deferred
863 // reads
865
867 int max,
869 int maxDefer,
872 {
873 missingNodes.reserve(max);
874 finishedReads.reserve(maxDefer);
875 }
876 };
877
878 // getMissingNodes helper functions
879 void
880 gmnProcessNodes(MissingNodes&, MissingNodes::StackEntry& node);
881 static void
882 gmnProcessDeferredReads(MissingNodes&);
883
884 // fetch from DB helper function
886 finishFetch(SHAMapHash const& hash, std::shared_ptr<NodeObject> const& object) const;
887};
888
889inline void
891{
892 ledgerSeq_.store(ledgerSeq, std::memory_order_relaxed);
893 full_.store(true, std::memory_order_release);
894}
895
896inline void
898{
899 ledgerSeq_.store(lseq, std::memory_order_relaxed);
900}
901
902inline std::uint32_t
904{
905 return ledgerSeq_.load(std::memory_order_relaxed);
906}
907
908inline SHAMapState
910{
911 return state_.load(std::memory_order_acquire);
912}
913
914inline bool
916{
917 // Invalid is stored outright: a walk reaching that verdict has to win against a thread
918 // settling the map.
919 if (desired == SHAMapState::Invalid)
920 {
921 state_.store(SHAMapState::Invalid, std::memory_order_release);
922 return true;
923 }
924
925 // A failed exchange both reports the state and refreshes expected, so no load is needed
926 // ahead of the loop.
927 auto expected = SHAMapState::Modifying;
928 while (expected != SHAMapState::Invalid)
929 {
930 if (state_.compare_exchange_weak(
931 expected, desired, std::memory_order_acq_rel, std::memory_order_acquire))
932 {
933 return true;
934 }
935 }
936 return false;
937}
938
939inline bool
941{
942 SOMETIMES(!isValid(), "xrpl::SHAMap::setImmutable : map is invalid");
944}
945
946inline bool
948{
949 return state() == SHAMapState::Synching;
950}
951
952inline bool
954{
955 return state() == SHAMapState::Immutable;
956}
957
958inline void
960{
961 // Guarded, so this is not a way out of Invalid.
963 {
964 // Only ever called on a freshly constructed map.
965 // LCOV_EXCL_START
966 UNREACHABLE("xrpl::SHAMap::setSynching : map is invalid");
967 // LCOV_EXCL_STOP
968 }
969}
970
971inline void
973{
974 // Only Synching moves. A walk can end after the ledger settled, and then the map stays
975 // Immutable; a Modifying map has nothing to clear; an invalid map stays invalid. Only that
976 // last refusal is logged, since a concurrent walk is what produces it.
977 auto expected = SHAMapState::Synching;
978 if (state_.compare_exchange_strong(
979 expected, SHAMapState::Modifying, std::memory_order_acq_rel, std::memory_order_acquire))
980 {
981 return;
982 }
983
984 bool const invalid = expected == SHAMapState::Invalid;
985 SOMETIMES(invalid, "xrpl::SHAMap::clearSynching : map is invalid");
986 if (invalid)
987 {
988 JLOG(journal_.warn()) << "Refused to clear synching on an invalid map, root hash "
989 << root_->getHash();
990 }
991}
992
993inline bool
995{
996 return state() != SHAMapState::Invalid;
997}
998
999inline void
1001{
1002 // Through trySetState() like every other transition, so state_ has one writer funnel.
1004}
1005
1006inline void
1008{
1009 backed_ = false;
1010}
1011
1012//------------------------------------------------------------------------------
1013
1015{
1016public:
1020 using reference = value_type const&;
1021 using pointer = value_type const*;
1022
1023private:
1025 SHAMap const* map_ = nullptr;
1026 pointer item_ = nullptr;
1027
1028public:
1029 ConstIterator() = delete;
1030
1031 ConstIterator(ConstIterator const& other) = default;
1033 operator=(ConstIterator const& other) = default;
1034
1035 ~ConstIterator() = default;
1036
1037 reference
1038 operator*() const;
1039 pointer
1040 operator->() const;
1041
1043 operator++();
1045 operator++(int);
1046
1047private:
1048 explicit ConstIterator(SHAMap const* map);
1049 ConstIterator(SHAMap const* map, std::nullptr_t);
1050 ConstIterator(SHAMap const* map, pointer item, NodePathStack&& stack);
1051
1052 friend bool
1053 operator==(ConstIterator const& x, ConstIterator const& y);
1054 friend class SHAMap;
1055};
1056
1058{
1059 XRPL_ASSERT(map_, "xrpl::SHAMap::ConstIterator::ConstIterator : non-null input");
1060
1061 if (auto temp = map_->peekFirstItem(stack_))
1062 item_ = temp->peekItem().get();
1063}
1064
1068
1070 : stack_(std::move(stack)), map_(map), item_(item)
1071{
1072}
1073
1076{
1077 return *item_;
1078}
1079
1082{
1083 return item_;
1084}
1085
1088{
1089 if (auto temp = map_->peekNextItem(item_->key(), stack_))
1090 {
1091 item_ = temp->peekItem().get();
1092 }
1093 else
1094 {
1095 item_ = nullptr;
1096 }
1097 return *this;
1098}
1099
1102{
1103 auto const tmp = *this;
1104 ++(*this);
1105 return tmp;
1106}
1107
1108inline bool
1110{
1111 XRPL_ASSERT(
1112 x.map_ == y.map_,
1113 "xrpl::operator==(SHAMap::const_iterator, SHAMap::const_iterator) : "
1114 "inputs map do match");
1115 return x.item_ == y.item_;
1116}
1117
1120{
1121 return ConstIterator(this);
1122}
1123
1126{
1127 return ConstIterator(this, nullptr);
1128}
1129
1130} // namespace xrpl
A generic endpoint for log messages.
Definition Journal.h:44
static constexpr unsigned int kBranchFactor
Each inner node has 16 children (the 'radix tree' part of the map).
Identifies a node inside a SHAMap.
pointer operator->() const
Definition SHAMap.h:1081
ConstIterator(ConstIterator const &other)=default
value_type const & reference
Definition SHAMap.h:1020
ConstIterator & operator=(ConstIterator const &other)=default
friend bool operator==(ConstIterator const &x, ConstIterator const &y)
Definition SHAMap.h:1109
std::forward_iterator_tag iterator_category
Definition SHAMap.h:1017
ConstIterator & operator++()
Definition SHAMap.h:1087
value_type const * pointer
Definition SHAMap.h:1021
reference operator*() const
Definition SHAMap.h:1075
std::ptrdiff_t difference_type
Definition SHAMap.h:1018
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::stack< std::pair< SHAMapTreeNodePtr, SHAMapNodeID > > stack_
Definition SHAMap.h:624
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
std::size_t size() const
Definition SHAMap.h:545
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
Family const & family() const
Definition SHAMap.h:201
bool setImmutable()
Mark this map as immutable, so it can no longer be modified.
Definition SHAMap.h:940
SHAMapTreeNode * descendAsync(SHAMapInnerNode *parent, unsigned int branch, SHAMapSyncFilter const *filter, bool &pending, DescendCallback &&) const
bool hasLeafNode(UInt256 const &tag, SHAMapHash const &hash) const
Does this map have this leaf node?
SHAMapTreeNode * descend(SHAMapInnerNode *, unsigned int branch) const
ConstIterator upperBound(UInt256 const &id) const
Find the first item after the given item.
std::uint32_t cowid_
ID to distinguish this map for all others we're sharing nodes with.
Definition SHAMap.h:123
SHAMapTreeNodePtr finishFetch(SHAMapHash const &hash, std::shared_ptr< NodeObject > const &object) const
void setLedgerSeq(std::uint32_t lseq)
Definition SHAMap.h:897
static constexpr unsigned int kLeafDepth
The depth of the hash map: data is only present in the leaves.
Definition SHAMap.h:172
void setFull(std::uint32_t ledgerSeq)
Mark this map as "should be full": the local server wants every node it references in durable storage...
Definition SHAMap.h:890
SHAMapTreeNodePtr fetchNodeFromDB(SHAMapHash const &hash) const
Family & f_
Definition SHAMap.h:117
bool getNodeFat(SHAMapNodeID const &wanted, std::vector< SHAMapNodeData > &data, bool fatLeaves, std::uint32_t depth) const
std::pair< boost::intrusive_ptr< SHAMapItem const >, boost::intrusive_ptr< SHAMapItem const > > DeltaItem
Definition SHAMap.h:174
SHAMapTreeNodePtr cacheLookup(SHAMapHash const &hash) const
Family & family()
Definition SHAMap.h:207
~SHAMap()=default
bool hasItem(UInt256 const &id) const
Does the tree have an item with the given ID?
int flushDirty(NodeObjectType t)
Flush modified nodes to the nodestore and convert them to shared.
static void gmnProcessDeferredReads(MissingNodes &)
bool isImmutable() const
Definition SHAMap.h:953
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
std::pair< boost::intrusive_ptr< SHAMapItem const >, boost::intrusive_ptr< SHAMapItem const > > DeltaRef
Definition SHAMap.h:627
void dirtyUp(NodePathStack &stack, UInt256 const &target, SHAMapTreeNodePtr terminal)
Update hashes up to the root.
void visitDifferences(SHAMap const *have, std::function< bool(SHAMapTreeNode const &)> const &) const
Visit every node in this SHAMap that is not present in the specified SHAMap.
SHAMapTreeNodePtr fetchNode(SHAMapHash const &hash) const
void setUnbacked()
Definition SHAMap.h:1007
bool walkMapParallel(std::vector< SHAMapMissingNode > &missingNodes, int maxMissing) const
void walkMap(std::vector< SHAMapMissingNode > &missingNodes, int maxMissing) const
void setSynching()
Mark this map as syncing, fixing its hash while still allowing missing nodes to be added.
Definition SHAMap.h:959
bool hasInnerNode(SHAMapNodeID const &nodeID, SHAMapHash const &hash) const
Does this map have this inner node?
SHAMap(SHAMap const &)=delete
bool isSynching() const
Definition SHAMap.h:947
bool deepCompare(SHAMap &other) const
void gmnProcessNodes(MissingNodes &, MissingNodes::StackEntry &node)
SHAMap & operator=(SHAMap const &)=delete
SHAMapLeafNode const * peekFirstItem(NodePathStack &stack) const
void dump(bool withHashes=false) const
beast::Journal journal_
Definition SHAMap.h:118
std::map< UInt256, DeltaItem > Delta
Definition SHAMap.h:176
std::atomic< std::uint32_t > ledgerSeq_
The sequence of the ledger that this map references, if any.
Definition SHAMap.h:138
bool compare(SHAMap const &otherMap, Delta &differences, int maxCount) const
SHAMapTreeNode * descendThrow(SHAMapInnerNode *, unsigned int branch) const
SHAMapAddNode addRootNode(SHAMapHash const &hash, SHAMapTreeNodePtr rootNode, SHAMapSyncFilter const *filter)
Add a root node to the SHAMap during synchronization.
void serializeRoot(Serializer &s) const
Serializes the root in a format appropriate for sending over the wire.
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
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)
void visitLeaves(std::function< void(boost::intrusive_ptr< SHAMapItem const > const &)> const &) const
Visit every leaf node in this SHAMap.
SHAMapLeafNode * walkTowardsKey(UInt256 const &id, NodePathStack *stack=nullptr) const
Walk towards the specified id, returning the node.
bool updateGiveItem(SHAMapNodeType type, boost::intrusive_ptr< SHAMapItem const > item)
SHAMapType const type_
Definition SHAMap.h:151
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
SHAMapTreeNodePtr fetchNodeNT(SHAMapHash const &hash) const
void clearSynching()
Mark this map as no longer syncing, so it can be modified again.
Definition SHAMap.h:972
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.
bool trySetState(SHAMapState desired)
Move the map to a new state, atomically.
Definition SHAMap.h:915
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)
std::vector< std::pair< SHAMapNodeID, UInt256 > > getMissingNodes(int maxNodes, SHAMapSyncFilter const *filter)
Check for nodes in the SHAMap not available.
SHAMapHash getHash() const
ConstIterator begin() const
Definition SHAMap.h:1119
void visitNodes(std::function< bool(SHAMapTreeNode &)> const &function) const
Visit every node in this SHAMap.
std::optional< std::vector< Blob > > getProofPath(UInt256 const &key) const
Get the proof path of the key.
bool walkBranch(SHAMapTreeNode *node, boost::intrusive_ptr< SHAMapItem const > const &otherMapItem, bool isFirstMap, Delta &differences, int &maxCount) const
boost::intrusive_ptr< SHAMapItem const > const & peekItem(UInt256 const &id) const
SHAMapLeafNode const * peekNextItem(UInt256 const &id, NodePathStack &stack) const
static bool verifyProofPath(UInt256 const &rootHash, UInt256 const &key, std::vector< Blob > const &path)
Verify the proof path.
STL namespace.
SharedIntrusive< T > SharedPtr
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
constexpr bool operator==(BaseUInt< Bits, Tag > const &lhs, BaseUInt< Bits, Tag > const &rhs)
Definition base_uint.h:613
NodeObjectType
The types of node objects.
Definition NodeObject.h:18
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.
unsigned int selectBranch(SHAMapNodeID const &id, UInt256 const &hash)
Returns the branch that would contain the given hash.
std::vector< unsigned char > Blob
Storage for linear binary data.
Definition Blob.h:11
@ Invalid
Timely, but invalid signature.
Definition Manifest.h:329
A SHAMap is both a radix tree with a fan-out of 16 and a Merkle tree.
Definition SHAMap.h:105
SHAMapNodeID nodeID
Definition SHAMap.h:106
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
MissingNodes & operator=(MissingNodes const &)=delete
MissingNodes(int max, SHAMapSyncFilter const *filter, int maxDefer, std::uint32_t generation)
Definition SHAMap.h:866
std::uint32_t generation
Definition SHAMap.h:829
MissingNodes(MissingNodes const &)=delete
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