1#include <xrpl/basics/Blob.h>
2#include <xrpl/basics/SHAMapHash.h>
3#include <xrpl/basics/Slice.h>
4#include <xrpl/basics/base_uint.h>
5#include <xrpl/basics/chrono.h>
6#include <xrpl/basics/random.h>
7#include <xrpl/basics/safe_cast.h>
8#include <xrpl/beast/hash/uhash.h>
9#include <xrpl/beast/utility/Journal.h>
10#include <xrpl/beast/xor_shift_engine.h>
11#include <xrpl/ledger/Ledger.h>
12#include <xrpl/protocol/Fees.h>
13#include <xrpl/protocol/LedgerHeader.h>
14#include <xrpl/protocol/Rules.h>
15#include <xrpl/protocol/Serializer.h>
16#include <xrpl/shamap/SHAMap.h>
17#include <xrpl/shamap/SHAMapAddNode.h>
18#include <xrpl/shamap/SHAMapInnerNode.h>
19#include <xrpl/shamap/SHAMapItem.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>
25#include <boost/smart_ptr/intrusive_ptr.hpp>
27#include <gtest/gtest.h>
28#include <helpers/TestSink.h>
29#include <shamap/DeepChain.h>
30#include <shamap/InnerNode.h>
31#include <shamap/common.h>
58[[nodiscard]]
static Rules
62 return Rules{kNoPresets};
78[[nodiscard]] static ::testing::AssertionResult
82 return ::testing::AssertionSuccess();
84 return ::testing::AssertionFailure() <<
"tally is " << san.
get() <<
", expected good:" << good
85 <<
" bad:" << bad <<
" dupe:" << duplicate;
94 boost::intrusive_ptr<SHAMapItem>
97 static constexpr auto kWordsPerState = 3uz;
101 for (
auto word = 0uz; word < kWordsPerState; ++word)
115 for (
auto i = 0uz; i < count; ++i)
122 ADD_FAILURE() <<
"Unable to add item to map";
127 for (
auto const& item : items)
131 ADD_FAILURE() <<
"Unable to remove item from map";
136 if (beforeHash != map.
getHash())
138 ADD_FAILURE() <<
"Hashes do not match " << beforeHash <<
" " << map.
getHash();
171 reports_.push_back({.fromFilter = fromFilter, .hash = hash, .ledgerSeq = ledgerSeq});
191 node->serializeWithPrefix(s);
227 unsigned int minDepth = 0)
229 for (
auto depth = minDepth; depth <= maxDepth; ++depth)
246 if (
auto const it =
nodes_.find(hash); it !=
nodes_.end())
278 childHash.
begin()[0] = 0xFA;
279 childHash.
begin()[1] = 0xB1;
280 childHash.
begin()[2] =
static_cast<unsigned char>(branch);
300 ASSERT_TRUE(chain.
fill(map));
305 EXPECT_TRUE(
tallyIs(result, 0, 1, 0));
306 EXPECT_FALSE(result.isGood());
326 for (
auto const& [nodeID, node] : chain.nodesBelowRoot())
328 auto const result = map.
addKnownNode(nodeID, node,
nullptr);
330 ASSERT_TRUE(
tallyIs(result, 1, 0, 0)) <<
"depth " << nodeID.getDepth();
331 ASSERT_TRUE(result.isUseful());
335 EXPECT_TRUE(map.
hasItem(chain.pathKey));
336 EXPECT_EQ(map.
getHash(), chain.rootHash);
355 EXPECT_TRUE(
tallyIs(wrongDepth, 0, 1, 0));
356 EXPECT_FALSE(wrongDepth.isUseful());
361 otherBranch.
begin()[0] = 0x10;
362 auto const emptyBranch =
365 EXPECT_TRUE(
tallyIs(emptyBranch, 0, 1, 0));
371 EXPECT_TRUE(
tallyIs(corrupt, 0, 1, 0));
393 EXPECT_TRUE(
tallyIs(same, 0, 0, 1));
394 EXPECT_TRUE(same.isGood());
400 EXPECT_TRUE(
tallyIs(other, 0, 1, 0));
401 EXPECT_FALSE(other.isGood());
402 EXPECT_TRUE(other.isInvalid());
408 EXPECT_TRUE(
tallyIs(consistent, 0, 1, 0));
409 EXPECT_FALSE(consistent.isGood());
410 EXPECT_TRUE(consistent.isInvalid());
432 ASSERT_TRUE(chain.
fill(map));
443 EXPECT_TRUE(
tallyIs(result, 0, 1, 0));
444 EXPECT_FALSE(result.isGood());
463 ASSERT_TRUE(
tallyIs(result, 0, 1, 0));
490 ASSERT_TRUE(
tallyIs(result, 0, 1, 0));
550 ASSERT_TRUE(chain.
fill(map));
555 for (
auto attempt = 0; attempt < 3; ++attempt)
557 EXPECT_FALSE(map.
setImmutable()) <<
"attempt " << attempt;
558 EXPECT_FALSE(map.
isValid()) <<
"attempt " << attempt;
564 for (
auto attempt = 0; attempt < 3; ++attempt)
567 EXPECT_FALSE(map.
isValid()) <<
"attempt " << attempt;
600 ASSERT_TRUE(chain.
fill(map));
603 ASSERT_TRUE(
tallyIs(result, 0, 1, 0));
608 for (
bool const isMutable : {
false,
true})
610 auto const snapshot = map.
snapShot(isMutable);
611 ASSERT_TRUE(snapshot !=
nullptr);
612 EXPECT_FALSE(snapshot->isValid()) <<
"isMutable " << isMutable;
613 EXPECT_FALSE(snapshot->setImmutable()) <<
"isMutable " << isMutable;
619 EXPECT_TRUE(
valid.snapShot(
false)->isValid());
620 EXPECT_TRUE(
valid.snapShot(
true)->isValid());
630 struct CountingFilter : ChainFilter
632 using ChainFilter::ChainFilter;
644 getNode(
SHAMapHash const& hash)
const override
647 return ChainFilter::getNode(hash);
659 ASSERT_TRUE(chain.
fill(map));
662 ASSERT_TRUE(
tallyIs(offendingResult, 0, 1, 0));
669 EXPECT_EQ(filter.lookups, 0u);
691 ChainFilter
const filter{chain};
726 ChainFilter
const filter{chain};
759 ChainFilter
const filter{chain};
789 ASSERT_EQ(missing.size(), 1u);
791 EXPECT_EQ(missing[0].second, withheld.
asUInt256());
809 ChainFilter
const filter{chain};
829 ASSERT_TRUE(chain.
fill(map));
832 ASSERT_TRUE(
tallyIs(offendingResult, 0, 1, 0));
837 EXPECT_TRUE(
tallyIs(result, 0, 0, 1));
838 EXPECT_TRUE(result.isGood());
839 EXPECT_FALSE(result.isUseful());
853 GTEST_SKIP() <<
"Only meaningful under ThreadSanitizer";
856 static constexpr auto kRounds = 200uz;
858 for (
auto round = 0uz; round < kRounds; ++round)
870 ChainFilter
const filter{chain};
877 while (!go.
load(std::memory_order_acquire))
883 while (!go.
load(std::memory_order_acquire))
885 for (
auto attempt = 0uz; attempt < 64uz; ++attempt)
889 go.
store(
true, std::memory_order_release);
895 EXPECT_FALSE(map.
isValid()) <<
"round " << round;
906 static constexpr auto kRounds = 8uz;
907 static constexpr auto kReadThreads = 4;
910 for (
auto round = 0uz; round < kRounds; ++round)
926 <<
"round " << round;
953 map.setLedgerSeq(kLedgerSeq);
955 RecordingFilter filter;
957 ASSERT_TRUE(map.addRootNode(
root->getHash(),
root, &filter).isGood());
958 ASSERT_TRUE(map.addKnownNode(
SHAMapNodeID{1, UInt256{}}, middle, &filter).isUseful());
961 filter.serve(deepest);
965 ASSERT_EQ(missing.size(), 1u);
966 EXPECT_EQ(missing[0].second,
UInt256{1});
968 ASSERT_EQ(filter.reports().size(), 3u);
971 EXPECT_FALSE(filter.reports()[0].fromFilter);
972 EXPECT_EQ(filter.reports()[0].hash,
root->getHash());
973 EXPECT_FALSE(filter.reports()[1].fromFilter);
974 EXPECT_EQ(filter.reports()[1].hash, middle->getHash());
977 EXPECT_TRUE(filter.reports()[2].fromFilter);
978 EXPECT_EQ(filter.reports()[2].hash, deepest->getHash());
980 for (
auto const& report : filter.reports())
981 EXPECT_EQ(report.ledgerSeq, kLedgerSeq) <<
"hash " << report.hash;
996 header.
seq = kLedgerSeq;
1035 static constexpr auto kRounds = 2000uz;
1038 static constexpr auto kReaders = 4uz;
1040 static constexpr auto kWarmMisses = 2 * kReaders;
1046 for (
auto round = 0uz; round < kRounds; ++round)
1050 auto const ledgerSeq =
static_cast<std::uint32_t>(kFirstLedgerSeq + round);
1054 header.
seq = ledgerSeq;
1067 for (
auto i = 0uz; i < kReaders; ++i)
1073 misses.
fetch_add(1, std::memory_order_relaxed);
1081 while (misses.
load(std::memory_order_relaxed) < kWarmMisses)
1085 for (
auto& reader : readers)
1099 static constexpr auto kItemCount = 10000uz;
1100 static constexpr auto kInvariantInterval = 100uz;
1101 static constexpr auto kNodesToConfuse = 500uz;
1103 for (
auto i = 0uz; i < kItemCount; ++i)
1106 if (i % kInvariantInterval == 0)
1111 ASSERT_TRUE(confuseMap(source, kNodesToConfuse));
1117 source.
visitLeaves([&count]([[maybe_unused]]
auto const& item) { ++count; });
1118 EXPECT_EQ(count, kItemCount);
1122 EXPECT_TRUE(missingNodes.
empty());
1131 ASSERT_FALSE(a.
empty()) <<
"NodeSize";
1135 FAIL() <<
"Could not create node";
1146 if (nodesMissing.empty())
1152 for (
auto const& it : nodesMissing)
1158 FAIL() <<
"Unable to fetch node";
1165 FAIL() <<
"No nodes returned";
1167 for (
auto const& i : b)
1174 FAIL() <<
"Could not create node";
1175 if (i.isLeaf != node->isLeaf())
1176 FAIL() <<
"Node is not a leaf";
1178 FAIL() <<
"Known node was not useful";
1202 auto const makeOffer = [] {
1209 ASSERT_TRUE(makeOffer());
1218 auto const examined = synching.
addKnownNode(target, makeOffer(),
nullptr);
1219 EXPECT_TRUE(examined.isInvalid());
1220 EXPECT_EQ(examined.getDuplicate(), 0);
1228 auto const notNeeded = stopped.
addKnownNode(target, makeOffer(),
nullptr);
1229 EXPECT_EQ(notNeeded.getGood(), 0);
1230 EXPECT_EQ(notNeeded.getBad(), 0);
1231 EXPECT_EQ(notNeeded.getDuplicate(), 1);
1232 EXPECT_TRUE(notNeeded.isGood()) <<
"a node that was not needed counts on the accepted side";
A generic endpoint for log messages.
void advance(std::chrono::duration< Rep, Period > const &elapsed)
Advance the clock by a duration.
bool setImmutable(bool rehash=true)
Mark this ledger as immutable, so it can no longer be modified.
SHAMap const & stateMap() const
SHAMap const & txMap() const
LedgerHeader const & header() const override
Returns information about the ledger.
void setFull() const
Mark this ledger as "should be full", indicating that the local server wants all the corresponding no...
std::chrono::time_point< NetClock > time_point
Rules controlling protocol behavior.
bool isGood() const
Whether nodes that produced a good result or were not needed outnumber the ones rejected.
std::string get() const
Render the tally as a log line.
UInt256 const & asUInt256() const
Identifies a node inside a SHAMap.
SHAMapSyncFilter()=default
static SHAMapTreeNodePtr makeFromWire(Slice rawNode)
bool fetchRoot(SHAMapHash const &hash, SHAMapSyncFilter const *filter)
bool addItem(SHAMapNodeType type, boost::intrusive_ptr< SHAMapItem const > item)
bool setImmutable()
Mark this map as immutable, so it can no longer be modified.
static constexpr unsigned int kLeafDepth
The depth of the hash map: data is only present in the leaves.
void setFull(std::uint32_t ledgerSeq)
Mark this map as "should be full": the local server wants every node it references in durable storage...
bool getNodeFat(SHAMapNodeID const &wanted, std::vector< SHAMapNodeData > &data, bool fatLeaves, std::uint32_t depth) const
bool hasItem(UInt256 const &id) const
Does the tree have an item with the given ID?
static constexpr unsigned int kBranchFactor
Number of children each non-leaf node has (the 'radix tree' part of the map).
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.
bool deepCompare(SHAMap &other) const
SHAMapAddNode addRootNode(SHAMapHash const &hash, SHAMapTreeNodePtr rootNode, SHAMapSyncFilter const *filter)
Add a root node to the SHAMap during synchronization.
bool isValid() const
Whether the map can still be the map it claims to be.
std::shared_ptr< SHAMap > snapShot(bool isMutable) const
Return a new map that is a snapshot of this one.
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.
SHAMapAddNode addKnownNode(SHAMapNodeID const &nodeID, SHAMapTreeNodePtr treeNode, SHAMapSyncFilter const *filter)
Add a known node at a specific position in the SHAMap during synchronization.
void clearSynching()
Mark this map as no longer syncing, so it can be modified again.
std::vector< std::pair< SHAMapNodeID, UInt256 > > getMissingNodes(int maxNodes, SHAMapSyncFilter const *filter)
Check for nodes in the SHAMap not available.
SHAMapHash getHash() const
Blob const & peekData() const
int addBitString(BaseUInt< Bits, Tag > const &v)
UInt256 getSHA512Half() const
int add8(unsigned char byteValue)
Slice slice() const noexcept
static TestSink & instance()
std::map< SHAMapHash, Blob > nodes_
void gotNode(bool, SHAMapHash const &, std::uint32_t, Blob &&, SHAMapNodeType) const override
ChainFilter(DeepChain const &chain, unsigned int maxDepth=SHAMap::kLeafDepth, unsigned int minDepth=0)
std::optional< Blob > getNode(SHAMapHash const &hash) const override
A sync filter that records every node it is told about, and serves back only the ones it was explicit...
std::vector< Report > const & reports() const
std::vector< Report > reports_
void serve(SHAMapTreeNodePtr const &node)
Offer a node back to the map, as a fetch pack does.
std::optional< Blob > getNode(SHAMapHash const &hash) const override
void gotNode(bool fromFilter, SHAMapHash const &hash, std::uint32_t ledgerSeq, Blob &&, SHAMapNodeType) const override
std::map< SHAMapHash, Blob > served_
beast::XorShiftEngine eng_
boost::intrusive_ptr< SHAMapItem > makeRandomAS()
bool confuseMap(SHAMap &map, std::size_t count)
std::shared_ptr< FullBelowCache > getFullBelowCache() override
Return a pointer to the Family Full Below Cache.
std::uint32_t missingBySeqRefNum() const
The ledger sequence the most recent such report named.
std::size_t missingBySeqReports() const
How many times a map of this family has withdrawn its claim of being complete in the database.
T emplace_back(T... args)
detail::XorShiftEngine<> XorShiftEngine
XOR-shift Generator.
TER valid(STTx const &tx, ReadView const &view, AccountID const &src, beast::Journal j)
static constexpr int kMaxNodesPerRequest
TEST_F(HashRouterTest, clear_flags_clears_only_the_named_flags)
static Rules noAmendments()
Rules with no amendments enabled.
static ::testing::AssertionResult tallyIs(SHAMapAddNode const &san, int good, int bad, int duplicate)
Whether a verdict carries exactly the given counts.
SHAMapTreeNodePtr makeCompressedInnerNode(std::vector< InnerChild > const &children)
Assemble an inner node in the wire format's compressed form.
SHAMapTreeNodePtr makeFullInnerNode(std::vector< InnerChild > const &children)
Assemble an inner node in the wire format's full form.
intr_ptr::SharedPtr< SHAMapTreeNode > SHAMapTreeNodePtr
bool randBool(Engine &engine)
Return a random boolean value.
Number root(Number f, unsigned d)
static constexpr unsigned char const kWireTypeCompressedInner
Slice makeSlice(std::array< T, N > const &a)
boost::intrusive_ptr< SHAMapItem > makeShamapitem(UInt256 const &tag, Slice data)
Integral randInt(Engine &engine, Integral min, Integral max)
Return a uniformly distributed random integer.
Dest safeDowncast(Src *s) noexcept
UInt256 calculateLedgerHash(LedgerHeader const &info)
Calculate the hash of a ledger header.
std::vector< unsigned char > Blob
Storage for linear binary data.
Reflects the fee settings for a particular ledger.
A chain of inner nodes in wire form, from the root down to one deepest node, each with one real child...
Blob prefixedNodeAt(unsigned int depth) const
The same node in the prefixed form used for storage and fetch packs, which is what hashes to the node...
static DeepChain withDecoys(unsigned int seed=1)
The same chain, with an unresolvable second child at every level, so a backed map's descendAsync() po...
SHAMapAddNode addOffendingNode(SHAMap &map) const
Offer the deepest node, which for a fabricated chain is the inner node at SHAMap::kLeafDepth,...
bool fill(SHAMap &map) const
Fill a synching map, stopping one level short of the deepest node so the caller offers that one itsel...
SHAMapTreeNodePtr nodeAt(unsigned int depth) const
The node the chain holds at the given depth, root first.
static DeepChain toLeaf(unsigned int depth, unsigned int seed=1)
A chain ending in a real transaction leaf, which completes an acquisition.