xrpld
Loading...
Searching...
No Matches
tests/libxrpl/shamap/SHAMapSync.cpp
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>
24
25#include <boost/smart_ptr/intrusive_ptr.hpp>
26
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>
32
33#include <atomic>
34#include <chrono>
35#include <cstddef>
36#include <cstdint>
37#include <list>
38#include <map>
39#include <optional>
40#include <thread>
41#include <unordered_set>
42#include <utility>
43#include <vector>
44
45namespace xrpl::tests {
46
47// The cap on how many nodes a walk reports, above what any test here expects.
48static constexpr int kMaxNodesPerRequest = 2048;
49
58[[nodiscard]] static Rules
60{
61 static std::unordered_set<UInt256, beast::Uhash<>> const kNoPresets;
62 return Rules{kNoPresets};
63}
64
78[[nodiscard]] static ::testing::AssertionResult
79tallyIs(SHAMapAddNode const& san, int good, int bad, int duplicate)
80{
81 if (san.getGood() == good && san.getBad() == bad && san.getDuplicate() == duplicate)
82 return ::testing::AssertionSuccess();
83
84 return ::testing::AssertionFailure() << "tally is " << san.get() << ", expected good:" << good
85 << " bad:" << bad << " dupe:" << duplicate;
86}
87
88class SHAMapSyncTest : public ::testing::Test
89{
90protected:
93
94 boost::intrusive_ptr<SHAMapItem>
96 {
97 static constexpr auto kWordsPerState = 3uz;
98
99 Serializer s;
100
101 for (auto word = 0uz; word < kWordsPerState; ++word)
103 return makeShamapitem(s.getSHA512Half(), s.slice());
104 }
105
106 bool
108 {
109 // add a bunch of random states to a map, then remove them
110 // map should be the same
111 SHAMapHash const beforeHash = map.getHash();
112
113 std::list<UInt256> items;
114
115 for (auto i = 0uz; i < count; ++i)
116 {
117 auto const item = makeRandomAS();
118 items.push_back(item->key());
119
121 {
122 ADD_FAILURE() << "Unable to add item to map";
123 return false;
124 }
125 }
126
127 for (auto const& item : items)
128 {
129 if (!map.delItem(item))
130 {
131 ADD_FAILURE() << "Unable to remove item from map";
132 return false;
133 }
134 }
135
136 if (beforeHash != map.getHash())
137 {
138 ADD_FAILURE() << "Hashes do not match " << beforeHash << " " << map.getHash();
139 return false;
140 }
141
142 return true;
143 }
144
153 {
154 public:
155 // What one gotNode() call was told, in the order the calls arrived.
162
163 void
165 bool fromFilter,
166 SHAMapHash const& hash,
167 std::uint32_t ledgerSeq,
168 Blob&&, // NOLINT(cppcoreguidelines-rvalue-reference-param-not-moved)
169 SHAMapNodeType) const override
170 {
171 reports_.push_back({.fromFilter = fromFilter, .hash = hash, .ledgerSeq = ledgerSeq});
172 }
173
174 [[nodiscard]] std::optional<Blob>
175 getNode(SHAMapHash const& hash) const override
176 {
177 if (auto const it = served_.find(hash); it != served_.end())
178 return it->second;
179 return std::nullopt;
180 }
181
187 void
189 {
190 Serializer s;
191 node->serializeWithPrefix(s);
192 served_.emplace(node->getHash(), s.modData());
193 }
194
195 [[nodiscard]] std::vector<Report> const&
196 reports() const
197 {
198 return reports_;
199 }
200
201 private:
202 // Mutable because the whole interface is const: a filter is handed to the map by
203 // const pointer, so recording has to happen through one.
206 };
207
217 {
218 public:
224 explicit ChainFilter(
225 DeepChain const& chain,
226 unsigned int maxDepth = SHAMap::kLeafDepth,
227 unsigned int minDepth = 0)
228 {
229 for (auto depth = minDepth; depth <= maxDepth; ++depth)
230 nodes_.emplace(chain.nodeAt(depth)->getHash(), chain.prefixedNodeAt(depth));
231 }
232
233 void
235 bool,
236 SHAMapHash const&,
238 Blob&&, // NOLINT(cppcoreguidelines-rvalue-reference-param-not-moved)
239 SHAMapNodeType) const override
240 {
241 }
242
243 [[nodiscard]] std::optional<Blob>
244 getNode(SHAMapHash const& hash) const override
245 {
246 if (auto const it = nodes_.find(hash); it != nodes_.end())
247 return it->second;
248 return std::nullopt;
249 }
250
251 private:
253 };
254
263 struct WideRoot
264 {
267
269 {
272
273 for (auto branch = 0u; branch < SHAMap::kBranchFactor; ++branch)
274 {
275 // Derived from the branch, so each posts its own read and no hash collides with a
276 // real node's.
277 UInt256 childHash;
278 childHash.begin()[0] = 0xFA;
279 childHash.begin()[1] = 0xB1;
280 childHash.begin()[2] = static_cast<unsigned char>(branch);
281 children.push_back({.branch = branch, .hash = SHAMapHash{childHash}});
282 }
283
284 node = makeFullInnerNode(children);
285 hash = node->getHash();
286 }
287 };
288};
289
290// Only a leaf may sit at kLeafDepth. An inner node there is reported as bad data and leaves the
291// map invalid.
292TEST_F(SHAMapSyncTest, inner_node_at_leaf_depth)
293{
294 TestNodeFamily f{j_};
295 DeepChain const chain;
296
297 SHAMap map{SHAMapType::FREE, f};
298 map.setSynching();
299
300 ASSERT_TRUE(chain.fill(map));
301 ASSERT_TRUE(map.isValid());
302
303 auto const result = chain.addOffendingNode(map);
304
305 EXPECT_TRUE(tallyIs(result, 0, 1, 0));
306 EXPECT_FALSE(result.isGood());
307 EXPECT_FALSE(map.isValid());
308
309 // Invalid is terminal, so setImmutable() refuses.
310 EXPECT_FALSE(map.setImmutable());
311}
312
313// The depth verdict is for inner nodes alone. A leaf is what belongs at kLeafDepth, so one offered
314// there through addKnownNode() is accepted and can be read back.
315TEST_F(SHAMapSyncTest, add_known_node_accepts_leaf_at_leaf_depth)
316{
317 TestNodeFamily f{j_};
318 auto const chain = DeepChain::toLeaf(SHAMap::kLeafDepth);
319
320 SHAMap map{SHAMapType::FREE, f};
321 map.setSynching();
322
323 ASSERT_TRUE(map.addRootNode(chain.rootHash, chain.nodeAt(0), nullptr).isGood());
324
325 // Every node below the root, the leaf last.
326 for (auto const& [nodeID, node] : chain.nodesBelowRoot())
327 {
328 auto const result = map.addKnownNode(nodeID, node, nullptr);
329
330 ASSERT_TRUE(tallyIs(result, 1, 0, 0)) << "depth " << nodeID.getDepth();
331 ASSERT_TRUE(result.isUseful());
332 }
333
334 EXPECT_TRUE(map.isValid());
335 EXPECT_TRUE(map.hasItem(chain.pathKey));
336 EXPECT_EQ(map.getHash(), chain.rootHash);
337}
338
339// A node the descent cannot hook in is bad data: the batch counts it bad and the map stays usable
340// for another sender. All three refusals are covered: a depth the node does not sit at, a branch
341// the root leaves empty, and a hash the root does not name.
342TEST_F(SHAMapSyncTest, node_that_cannot_be_hooked_is_bad_data)
343{
344 TestNodeFamily f{j_};
345 DeepChain const chain;
346
347 SHAMap map{SHAMapType::FREE, f};
348 map.setSynching();
349
350 ASSERT_TRUE(map.addRootNode(chain.rootHash, chain.nodeAt(0), nullptr).isGood());
351
352 // nodeAt(1) is the node the root is missing and its hash matches, but we claim depth 2.
353 auto const wrongDepth = map.addKnownNode(SHAMapNodeID{2, UInt256{}}, chain.nodeAt(1), nullptr);
354
355 EXPECT_TRUE(tallyIs(wrongDepth, 0, 1, 0));
356 EXPECT_FALSE(wrongDepth.isUseful());
357
358 // The chain sits on branch 0 at every depth, so a node claiming a position on branch 1 asks the
359 // descent to follow a branch the root leaves empty.
360 UInt256 otherBranch;
361 otherBranch.begin()[0] = 0x10;
362 auto const emptyBranch =
363 map.addKnownNode(SHAMapNodeID{1, otherBranch}, chain.nodeAt(1), nullptr);
364
365 EXPECT_TRUE(tallyIs(emptyBranch, 0, 1, 0));
366
367 // The right position this time, but the data hashes to something other than the child the root
368 // says belongs there.
369 auto const corrupt = map.addKnownNode(SHAMapNodeID{1, UInt256{}}, chain.nodeAt(2), nullptr);
370
371 EXPECT_TRUE(tallyIs(corrupt, 0, 1, 0));
372
373 // The verdict is bad data alone, so the map stays usable.
374 EXPECT_TRUE(map.isValid());
375}
376
377// A root is installed once and a map is synced against one hash, so a root offered under a hash the
378// map does not hold names another tree and is bad data. The same root under the hash the map does
379// hold is the duplicate it is.
380TEST_F(SHAMapSyncTest, add_root_node_judges_the_hash_asked_for)
381{
382 TestNodeFamily f{j_};
383 DeepChain const chain;
384
385 SHAMap map{SHAMapType::FREE, f};
386 map.setSynching();
387
388 ASSERT_TRUE(map.addRootNode(chain.rootHash, chain.nodeAt(0), nullptr).isGood());
389
390 // The same root under the hash the map holds: already held, and reported as such.
391 auto const same = map.addRootNode(chain.rootHash, chain.nodeAt(0), nullptr);
392
393 EXPECT_TRUE(tallyIs(same, 0, 0, 1));
394 EXPECT_TRUE(same.isGood());
395
396 // A hash the map does not hold. nodeAt(1) is a real node of the same chain, so this is a
397 // well-formed hash that names another tree.
398 auto const other = map.addRootNode(chain.nodeAt(1)->getHash(), chain.nodeAt(0), nullptr);
399
400 EXPECT_TRUE(tallyIs(other, 0, 1, 0));
401 EXPECT_FALSE(other.isGood());
402 EXPECT_TRUE(other.isInvalid());
403
404 // The same hash, now with the node it names. The offered node hashes to the hash asked for, so
405 // only a comparison against the root the map holds can refuse it.
406 auto const consistent = map.addRootNode(chain.nodeAt(1)->getHash(), chain.nodeAt(1), nullptr);
407
408 EXPECT_TRUE(tallyIs(consistent, 0, 1, 0));
409 EXPECT_FALSE(consistent.isGood());
410 EXPECT_TRUE(consistent.isInvalid());
411
412 // Both refusals are about the hash asked for, so the root the map holds stays in place and the
413 // map stays usable.
414 EXPECT_EQ(map.getHash(), chain.rootHash);
415 EXPECT_TRUE(map.isValid());
416}
417
418// The verdict outranks the full-below cache. That cache is keyed by node hash and shared by every
419// map of a family, and a hash covers a node's children but not its depth, so an earlier walk can
420// mark the same subtree hash complete at one depth while this map reaches it at kLeafDepth, with no
421// collision involved. The descent therefore skips the lookup at that boundary and reaches the depth
422// verdict first. This case seeds the entry a lookup would match, so dropping the skip turns the
423// verdict back into a duplicate.
424TEST_F(SHAMapSyncTest, map_invalidating_node_is_judged_before_the_cache_is_read)
425{
426 TestNodeFamily f{j_};
427 DeepChain const chain;
428
429 SHAMap map{SHAMapType::FREE, f};
430 map.setSynching();
431
432 ASSERT_TRUE(chain.fill(map));
433 ASSERT_TRUE(map.isValid());
434
435 // This case seeds the entry a lookup at the boundary would match: the offending node's own
436 // hash. The descent skips the lookup there, so the entry is never read and the depth verdict
437 // stands. Drop the skip and the hit returns for the whole branch, so the tally below becomes
438 // a duplicate.
439 f.getFullBelowCache()->insert(chain.nodeAt(SHAMap::kLeafDepth)->getHash().asUInt256());
440
441 auto const result = chain.addOffendingNode(map);
442
443 EXPECT_TRUE(tallyIs(result, 0, 1, 0));
444 EXPECT_FALSE(result.isGood());
445 EXPECT_FALSE(map.isValid());
446 EXPECT_FALSE(map.setImmutable());
447}
448
449// An invalid tx map must also stop the enclosing ledger from being marked immutable, since an
450// immutable ledger is treated as persistable.
451TEST_F(SHAMapSyncTest, invalid_tx_map_blocks_immutable_ledger)
452{
453 TestNodeFamily f{j_};
454 DeepChain const chain;
455
456 Ledger ledger{1, NetClock::time_point{}, noAmendments(), Fees{}, f};
457 ASSERT_FALSE(ledger.isImmutable());
458
459 ledger.txMap().setSynching();
460 ASSERT_TRUE(chain.fill(ledger.txMap()));
461
462 auto const result = chain.addOffendingNode(ledger.txMap());
463 ASSERT_TRUE(tallyIs(result, 0, 1, 0));
464 ASSERT_FALSE(ledger.txMap().isValid());
465
466 // The state map is untouched, so only the transaction map can be refusing.
467 ASSERT_TRUE(ledger.stateMap().isValid());
468
469 EXPECT_FALSE(ledger.setImmutable());
470 EXPECT_FALSE(ledger.isImmutable());
471
472 // The up-front mapsValid() check is what keeps the valid map from being settled on its own.
473 EXPECT_FALSE(ledger.stateMap().isImmutable());
474}
475
476// The same for the state map, which is the second operand of the one expression
477// Ledger::setImmutable() tests both maps in.
478TEST_F(SHAMapSyncTest, invalid_state_map_blocks_immutable_ledger)
479{
480 TestNodeFamily f{j_};
481 DeepChain const chain;
482
483 Ledger ledger{1, NetClock::time_point{}, noAmendments(), Fees{}, f};
484 ASSERT_FALSE(ledger.isImmutable());
485
486 ledger.stateMap().setSynching();
487 ASSERT_TRUE(chain.fill(ledger.stateMap()));
488
489 auto const result = chain.addOffendingNode(ledger.stateMap());
490 ASSERT_TRUE(tallyIs(result, 0, 1, 0));
491 ASSERT_FALSE(ledger.stateMap().isValid());
492
493 // The transaction map is untouched, so only the state map can be refusing.
494 ASSERT_TRUE(ledger.txMap().isValid());
495
496 EXPECT_FALSE(ledger.setImmutable());
497 EXPECT_FALSE(ledger.isImmutable());
498
499 // The up-front mapsValid() check is what keeps the valid map from being settled on its own.
500 EXPECT_FALSE(ledger.txMap().isImmutable());
501}
502
503// A refusal leaves the header exactly as it was. setImmutable() derives the map hashes from the
504// maps and then the ledger hash from the header, and writes them only after every check has
505// passed. The up-front check covers this case, and the re-test after the maps are settled shares
506// the rule, which is why the header is written only once that one has passed too.
507TEST_F(SHAMapSyncTest, refused_settle_leaves_the_header_alone)
508{
509 TestNodeFamily f{j_};
510 DeepChain const chain;
511
512 // Not the header constructor: this one derives its map hashes, which is what must not happen.
513 Ledger ledger{1, NetClock::time_point{}, noAmendments(), Fees{}, f};
514 ASSERT_FALSE(ledger.isImmutable());
515 ASSERT_TRUE(ledger.header().txHash.isZero());
516 ASSERT_TRUE(ledger.header().accountHash.isZero());
517 auto const hashBefore = ledger.header().hash;
518
519 // A transaction map that hashes to something, so a derived header hash differs from the one
520 // the ledger has now.
521 ASSERT_TRUE(ledger.txMap().addItem(SHAMapNodeType::TnTransactionNm, makeRandomAS()));
522 ASSERT_TRUE(ledger.txMap().getHash().isNonZero());
523
524 // And a state map the chain abandons, so settling has to refuse.
525 ledger.stateMap().setSynching();
526 ASSERT_TRUE(chain.fill(ledger.stateMap()));
527 ASSERT_TRUE(chain.addOffendingNode(ledger.stateMap()).isInvalid());
528 ASSERT_FALSE(ledger.stateMap().isValid());
529
530 EXPECT_FALSE(ledger.setImmutable());
531
532 // The map hashes, the ledger hash and the flag all still hold their pre-refusal values.
533 EXPECT_FALSE(ledger.isImmutable());
534 EXPECT_TRUE(ledger.header().txHash.isZero());
535 EXPECT_TRUE(ledger.header().accountHash.isZero());
536 EXPECT_EQ(ledger.header().hash, hashBefore);
537}
538
539// Invalid is terminal: setImmutable() and clearSynching() offer no way back out of it, however
540// many times they are called. setSynching() is left alone, since it is unreachable on an invalid
541// map today and says so with an UNREACHABLE.
542TEST_F(SHAMapSyncTest, invalid_state_is_terminal)
543{
544 TestNodeFamily f{j_};
545 DeepChain const chain;
546
547 SHAMap map{SHAMapType::FREE, f};
548 map.setSynching();
549
550 ASSERT_TRUE(chain.fill(map));
551 ASSERT_TRUE(chain.addOffendingNode(map).isInvalid());
552 ASSERT_FALSE(map.isValid());
553
554 // Repeated attempts must each fail, and must not leave the map reporting a valid state.
555 for (auto attempt = 0; attempt < 3; ++attempt)
556 {
557 EXPECT_FALSE(map.setImmutable()) << "attempt " << attempt;
558 EXPECT_FALSE(map.isValid()) << "attempt " << attempt;
559 }
560
561 // Nor does clearSynching(), which keeps an abandoned map from being moved back to Modifying and
562 // passing isValid() again. It refuses rather than treating that as unreachable, since a
563 // concurrent walk can invalidate a map between a caller's own check and this call.
564 for (auto attempt = 0; attempt < 3; ++attempt)
565 {
566 map.clearSynching();
567 EXPECT_FALSE(map.isValid()) << "attempt " << attempt;
568 }
569
570 // isSynching() answers false for an invalid map.
571 EXPECT_FALSE(map.isSynching());
572}
573
574// Immutable holds against clearSynching(): a walk that ends after the ledger settled leaves the map
575// settled rather than reopening it for modification.
576TEST_F(SHAMapSyncTest, clear_synching_leaves_an_immutable_map_immutable)
577{
578 TestNodeFamily f{j_};
579
580 SHAMap map{SHAMapType::FREE, f};
581 map.setSynching();
582 ASSERT_TRUE(map.setImmutable());
583 ASSERT_TRUE(map.isImmutable());
584
585 map.clearSynching();
586
587 EXPECT_TRUE(map.isImmutable());
588 EXPECT_FALSE(map.isSynching());
589}
590
591// A snapshot shares the source map's root, so Invalid carries over to it.
592TEST_F(SHAMapSyncTest, snapshot_of_invalid_map_stays_invalid)
593{
594 TestNodeFamily f{j_};
595 DeepChain const chain;
596
597 SHAMap map{SHAMapType::FREE, f};
598 map.setSynching();
599
600 ASSERT_TRUE(chain.fill(map));
601
602 auto const result = chain.addOffendingNode(map);
603 ASSERT_TRUE(tallyIs(result, 0, 1, 0));
604 ASSERT_FALSE(map.isValid());
605
606 // Both flavors: the immutable snapshot is the one the store reads, and the
607 // mutable one is the one that sets Modifying.
608 for (bool const isMutable : {false, true})
609 {
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;
614 }
615
616 // A snapshot of a sound map is unaffected.
618 valid.addItem(SHAMapNodeType::TnAccountState, makeRandomAS());
619 EXPECT_TRUE(valid.snapShot(false)->isValid());
620 EXPECT_TRUE(valid.snapShot(true)->isValid());
621}
622
623// getMissingNodes() refuses an invalid map outright, before consulting a filter. addKnownNode()
624// reaches the verdict here. A walk reaches it on its own in
625// get_missing_nodes_rejects_inner_node_at_leaf_depth.
626TEST_F(SHAMapSyncTest, get_missing_nodes_refuses_invalid_map)
627{
628 // The lookups are counted because the result alone cannot tell the refusal from a walk that
629 // reaches the same verdict: the loop discards what it collected once the map is invalid.
630 struct CountingFilter : ChainFilter
631 {
632 using ChainFilter::ChainFilter;
633
634 // How many times the walk asked for a node.
635 mutable std::size_t lookups = 0;
636
643 [[nodiscard]] std::optional<Blob>
644 getNode(SHAMapHash const& hash) const override
645 {
646 ++lookups;
647 return ChainFilter::getNode(hash);
648 }
649 };
650
651 TestNodeFamily f{j_};
652 DeepChain const chain;
653
654 SHAMap map{SHAMapType::FREE, f};
655 // Unbacked, like TransactionAcquire's map, so the walk resolves synchronously.
656 map.setUnbacked();
657 map.setSynching();
658
659 ASSERT_TRUE(chain.fill(map));
660
661 auto const offendingResult = chain.addOffendingNode(map);
662 ASSERT_TRUE(tallyIs(offendingResult, 0, 1, 0));
663 ASSERT_FALSE(map.isValid());
664
665 // Only the node the map rejected, offered back as a fetch pack does.
666 CountingFilter const filter{chain, SHAMap::kLeafDepth, SHAMap::kLeafDepth};
667
668 EXPECT_TRUE(map.getMissingNodes(kMaxNodesPerRequest, &filter).empty());
669 EXPECT_EQ(filter.lookups, 0u);
670 EXPECT_FALSE(map.isValid());
671 EXPECT_FALSE(map.setImmutable());
672}
673
674// A walk reaches kLeafDepth through the filter alone, since each node is checked against its own
675// hash and the walk resolves every level locally. The walk is what reaches the verdict here.
676TEST_F(SHAMapSyncTest, get_missing_nodes_rejects_inner_node_at_leaf_depth)
677{
678 TestNodeFamily f{j_};
679 DeepChain const chain;
680
681 SHAMap map{SHAMapType::FREE, f};
682 // Unbacked so the walk resolves each level synchronously through the filter.
683 map.setUnbacked();
684 map.setSynching();
685
686 // Only the root goes in through the sync path. Everything below comes from the filter, so the
687 // map is still valid when the walk starts.
688 ASSERT_TRUE(map.addRootNode(chain.rootHash, chain.nodeAt(0), nullptr).isGood());
689 ASSERT_TRUE(map.isValid());
690
691 ChainFilter const filter{chain};
692
693 EXPECT_TRUE(map.getMissingNodes(kMaxNodesPerRequest, &filter).empty());
694
695 // The walk reaches the same verdict addKnownNode() does, so the map is invalid and
696 // setImmutable() refuses.
697 EXPECT_FALSE(map.isValid());
698 EXPECT_FALSE(map.setImmutable());
699
700 // An empty result from a valid map clears the synching flag. An invalid map returns before
701 // that, and stays invalid across a second walk.
702 EXPECT_TRUE(map.getMissingNodes(kMaxNodesPerRequest, &filter).empty());
703 EXPECT_FALSE(map.isValid());
704}
705
706// The depth rule holds on a full-below cache hit reached by a walk too. A node's hash covers its
707// child hashes but not its depth, so a hit cannot stand in for the depth check. Backed, as
708// InboundLedger's map is.
709TEST_F(SHAMapSyncTest, get_missing_nodes_rejects_inner_node_at_leaf_depth_before_the_cache_is_read)
710{
711 TestNodeFamily f{j_};
712 DeepChain const chain;
713
714 // Backed, unlike the cases above, so the full-below cache is consulted at all.
715 SHAMap map{SHAMapType::FREE, f};
716 map.setSynching();
717
718 ASSERT_TRUE(map.addRootNode(chain.rootHash, chain.nodeAt(0), nullptr).isGood());
719 ASSERT_TRUE(map.isValid());
720
721 // This case seeds the entry a lookup at the boundary would match: the offending node's own
722 // hash. The walk skips the lookup there, so the entry is never read and the depth verdict
723 // stands. Drop the skip and the hit returns for the whole branch, guard included.
724 f.getFullBelowCache()->insert(chain.nodeAt(SHAMap::kLeafDepth)->getHash().asUInt256());
725
726 ChainFilter const filter{chain};
727
728 EXPECT_TRUE(map.getMissingNodes(kMaxNodesPerRequest, &filter).empty());
729 EXPECT_FALSE(map.isValid());
730 EXPECT_FALSE(map.setImmutable());
731}
732
733// Every read a walk posts is drained before the walk returns, the verdict included: the
734// MissingNodes block lives on getMissingNodes()'s stack frame and each posted read holds a
735// reference to it. Each level here has an unresolvable second child, so reads are outstanding when
736// the verdict lands. The expectations below read the result alone, so a sanitizer build is what
737// exercises the drain.
738TEST_F(SHAMapSyncTest, get_missing_nodes_drains_posted_reads_when_invalidated)
739{
740 TestNodeFamily f{j_};
741 auto const chain = DeepChain::withDecoys();
742
743 // The decoy is the point of the shape: every inner node has a second child, so the case
744 // pins that shape rather than trusting the builder.
745 for (unsigned int depth = 0; depth < SHAMap::kLeafDepth; ++depth)
746 {
747 ASSERT_EQ(
748 safeDowncast<SHAMapInnerNode const*>(chain.nodeAt(depth).get())->getBranchCount(), 2);
749 }
750
751 // Backed, so descendAsync() posts real asynchronous reads rather than resolving inline.
752 SHAMap map{SHAMapType::FREE, f};
753 map.setSynching();
754
755 ASSERT_TRUE(map.addRootNode(chain.rootHash, chain.nodeAt(0), nullptr).isGood());
756 ASSERT_TRUE(map.isValid());
757
758 // Only the chain nodes are served, so the decoy at each level has to be read asynchronously.
759 ChainFilter const filter{chain};
760
761 // The walk descends the chain, posting a read per level for the decoy child, and marks the map
762 // invalid on reaching kLeafDepth. Returning empty is the visible part; draining first is the
763 // part only a sanitizer can see.
764 EXPECT_TRUE(map.getMissingNodes(kMaxNodesPerRequest, &filter).empty());
765 EXPECT_FALSE(map.isValid());
766 EXPECT_FALSE(map.setImmutable());
767}
768
769// A walk that only meets legitimate depths must be left alone. Stopping one level short of
770// kLeafDepth leaves a deepest node whose child is genuinely missing, so the walk reports it and
771// the map stays valid.
772TEST_F(SHAMapSyncTest, get_missing_nodes_accepts_inner_node_above_leaf_depth)
773{
774 TestNodeFamily f{j_};
775 DeepChain const chain;
776
777 SHAMap map{SHAMapType::FREE, f};
778 map.setUnbacked();
779 map.setSynching();
780
781 ASSERT_TRUE(map.addRootNode(chain.rootHash, chain.nodeAt(0), nullptr).isGood());
782
783 // Every node above kLeafDepth is served, so the one at kLeafDepth is what the walk reports.
784 SHAMapHash const withheld = chain.nodeAt(SHAMap::kLeafDepth)->getHash();
785 ChainFilter const filter{chain, SHAMap::kLeafDepth - 1};
786
787 auto const missing = map.getMissingNodes(kMaxNodesPerRequest, &filter);
788
789 ASSERT_EQ(missing.size(), 1u);
790 EXPECT_EQ(missing[0].first.getDepth(), SHAMap::kLeafDepth);
791 EXPECT_EQ(missing[0].second, withheld.asUInt256());
792 EXPECT_TRUE(map.isValid());
793}
794
795// The negative control for the depth verdict: a real leaf at kLeafDepth is what belongs there, so a
796// walk that resolves one through the filter completes the map and leaves it valid.
797TEST_F(SHAMapSyncTest, get_missing_nodes_accepts_leaf_at_leaf_depth)
798{
799 TestNodeFamily f{j_};
800 auto const chain = DeepChain::toLeaf(SHAMap::kLeafDepth);
801
802 SHAMap map{SHAMapType::FREE, f};
803 map.setUnbacked();
804 map.setSynching();
805
806 ASSERT_TRUE(map.addRootNode(chain.rootHash, chain.nodeAt(0), nullptr).isGood());
807
808 // Every node is served, the leaf included, so nothing is left to fetch.
809 ChainFilter const filter{chain};
810
811 EXPECT_TRUE(map.getMissingNodes(kMaxNodesPerRequest, &filter).empty());
812 EXPECT_TRUE(map.isValid());
813 EXPECT_FALSE(map.isSynching());
814 EXPECT_TRUE(map.setImmutable());
815}
816
817// The clearSynching() call site in addRootNode() needs a leaf root, and so a zero root hash. An
818// invalid map always has an inner root with a non-zero hash, so the root is treated as a duplicate
819// and the flag stands.
820TEST_F(SHAMapSyncTest, add_root_node_leaves_invalid_map_invalid)
821{
822 TestNodeFamily f{j_};
823 DeepChain const chain;
824
825 SHAMap map{SHAMapType::FREE, f};
826 map.setUnbacked();
827 map.setSynching();
828
829 ASSERT_TRUE(chain.fill(map));
830
831 auto const offendingResult = chain.addOffendingNode(map);
832 ASSERT_TRUE(tallyIs(offendingResult, 0, 1, 0));
833 ASSERT_FALSE(map.isValid());
834
835 // A duplicate: counted as good, and counted in the duplicate tally.
836 auto const result = map.addRootNode(chain.rootHash, chain.nodeAt(0), nullptr);
837 EXPECT_TRUE(tallyIs(result, 0, 0, 1));
838 EXPECT_TRUE(result.isGood());
839 EXPECT_FALSE(result.isUseful());
840
841 EXPECT_FALSE(map.isValid());
842 EXPECT_FALSE(map.setImmutable());
843}
844
845// The concurrent half of the same contract: a walk writing Invalid while another thread calls
846// setImmutable(). trySetState() leaves Invalid in place, so the map ends up invalid and
847// setImmutable() refuses.
848//
849// Meaningful only under ThreadSanitizer. Skipped at run time, so every build still parses the body.
850TEST_F(SHAMapSyncTest, invalid_state_survives_concurrent_set_immutable)
851{
852#ifndef XRPL_TSAN
853 GTEST_SKIP() << "Only meaningful under ThreadSanitizer";
854#endif
855
856 static constexpr auto kRounds = 200uz;
857
858 for (auto round = 0uz; round < kRounds; ++round)
859 {
860 TestNodeFamily f{j_};
861 DeepChain const chain;
862
863 SHAMap map{SHAMapType::FREE, f};
864 map.setUnbacked();
865 map.setSynching();
866
867 // Only the root goes in through the sync path, so the map is still valid here. The walk
868 // below resolves the rest through the filter.
869 ASSERT_TRUE(map.addRootNode(chain.rootHash, chain.nodeAt(0), nullptr).isGood());
870 ChainFilter const filter{chain};
871
872 // One thread walks and invalidates while the other calls setImmutable() repeatedly. Both
873 // wait on the same flag, so neither is given a head start.
874 std::atomic<bool> go{false};
875
876 std::thread walker([&] {
877 while (!go.load(std::memory_order_acquire))
880 });
881
882 std::thread setter([&] {
883 while (!go.load(std::memory_order_acquire))
885 for (auto attempt = 0uz; attempt < 64uz; ++attempt)
886 static_cast<void>(map.setImmutable());
887 });
888
889 go.store(true, std::memory_order_release);
890 walker.join();
891 setter.join();
892
893 // The walk always reaches the verdict, so the map ends up invalid and setImmutable()
894 // refuses.
895 EXPECT_FALSE(map.isValid()) << "round " << round;
896 EXPECT_FALSE(map.setImmutable()) << "round " << round;
897 }
898}
899
900// A map marked complete in the database withdraws that claim the first time a read misses, and
901// reports the miss once so the ledger can be re-acquired. Sixteen unresolvable branches are posted
902// in one pass, so with four reader threads finishFetch() runs concurrently for one map. Only a
903// ThreadSanitizer build observes the ordering.
904TEST_F(SHAMapSyncTest, full_flag_is_withdrawn_once_by_concurrent_readers)
905{
906 static constexpr auto kRounds = 8uz;
907 static constexpr auto kReadThreads = 4;
908 static constexpr std::uint32_t kLedgerSeq = 7;
909
910 for (auto round = 0uz; round < kRounds; ++round)
911 {
912 TestNodeFamily f{j_, kReadThreads};
913 WideRoot const root;
914
915 // Backed, so descendAsync() posts real asynchronous reads rather than resolving inline.
916 SHAMap map{SHAMapType::FREE, f};
917 map.setSynching();
918
919 ASSERT_TRUE(map.addRootNode(root.hash, root.node, nullptr).isGood());
920
921 // The claim the first miss has to withdraw, and the sequence its report names.
922 map.setFull(kLedgerSeq);
923
924 // A null filter, so every branch is read from a database that lacks it.
925 EXPECT_EQ(map.getMissingNodes(kMaxNodesPerRequest, nullptr).size(), SHAMap::kBranchFactor)
926 << "round " << round;
927
928 EXPECT_EQ(f.missingBySeqReports(), 1uz) << "round " << round;
929 EXPECT_EQ(f.missingBySeqRefNum(), kLedgerSeq) << "round " << round;
930 }
931}
932
933// Every node the sync path hands to a filter carries the map's ledger sequence. All three call
934// sites are covered: a root taken from a peer, a node taken from a peer, and a node the walk
935// resolved out of the filter itself.
936TEST_F(SHAMapSyncTest, sync_filter_is_told_the_ledger_sequence)
937{
938 static constexpr std::uint32_t kLedgerSeq = 7;
939
940 TestNodeFamily f{j_};
941
942 // A three-level chain, built bottom-up so each hash covers the one below it. Every node keeps
943 // its one child on branch 0. The deepest points at a child the fixture withholds, so the walk
944 // always has something to ask for.
945 auto const deepest = makeCompressedInnerNode({{.branch = 0u, .hash = SHAMapHash{UInt256{1}}}});
946 auto const middle = makeCompressedInnerNode({{.branch = 0u, .hash = deepest->getHash()}});
947 auto const root = makeCompressedInnerNode({{.branch = 0u, .hash = middle->getHash()}});
948
949 // Unbacked, so the filter is the only source, and a node it withholds counts as missing.
950 SHAMap map{SHAMapType::FREE, f};
951 map.setUnbacked();
952 map.setSynching();
953 map.setLedgerSeq(kLedgerSeq);
954
955 RecordingFilter filter;
956
957 ASSERT_TRUE(map.addRootNode(root->getHash(), root, &filter).isGood());
958 ASSERT_TRUE(map.addKnownNode(SHAMapNodeID{1, UInt256{}}, middle, &filter).isUseful());
959
960 // The deepest node becomes resolvable only now, after the two above were added directly.
961 filter.serve(deepest);
962 auto const missing = map.getMissingNodes(kMaxNodesPerRequest, &filter);
963
964 // The walk resolved the deepest node through the filter and then asked for its child.
965 ASSERT_EQ(missing.size(), 1u);
966 EXPECT_EQ(missing[0].second, UInt256{1});
967
968 ASSERT_EQ(filter.reports().size(), 3u);
969
970 // The two nodes taken from a peer, which the filter is told about so it can store them.
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());
975
976 // The one the walk read back out of the filter, which is reported as such.
977 EXPECT_TRUE(filter.reports()[2].fromFilter);
978 EXPECT_EQ(filter.reports()[2].hash, deepest->getHash());
979
980 for (auto const& report : filter.reports())
981 EXPECT_EQ(report.ledgerSeq, kLedgerSeq) << "hash " << report.hash;
982}
983
984// Ledger::setFull() publishes each map's ledger sequence alongside the flag that lets the first
985// nodestore miss report a gap. The sequence is what the lookup resolving that gap reads.
986//
987// This pins that setFull() sets the sequence on both maps. It says nothing about the order of the
988// two stores, since it reads only after both have completed. That is the next test's concern.
989TEST_F(SHAMapSyncTest, ledger_set_full_publishes_the_ledger_sequence)
990{
991 static constexpr std::uint32_t kLedgerSeq = 7;
992
993 TestNodeFamily f{j_};
994
995 LedgerHeader header;
996 header.seq = kLedgerSeq;
997 // Non-zero, so each map has a root to look for and the lookup can miss.
998 header.txHash = UInt256{1};
999 header.accountHash = UInt256{2};
1000 header.hash = calculateLedgerHash(header);
1001
1002 Ledger ledger{header, noAmendments(), f};
1003
1004 // Nothing has looked for either root yet: this constructor only builds the two maps. The
1005 // count is zero, and the two reports below are the first.
1006 ASSERT_EQ(f.missingBySeqReports(), 0uz);
1007
1008 ledger.setFull();
1009
1010 // Both roots are missing, and now each map has a claim to withdraw, so each gap is reported.
1011 // TestNodeFamily throws in place of the real family's re-acquisition, which finishFetch()
1012 // logs and swallows.
1013 EXPECT_FALSE(ledger.txMap().fetchRoot(SHAMapHash{header.txHash}, nullptr));
1014 EXPECT_EQ(f.missingBySeqReports(), 1uz);
1015 EXPECT_EQ(f.missingBySeqRefNum(), kLedgerSeq);
1016
1017 EXPECT_FALSE(ledger.stateMap().fetchRoot(SHAMapHash{header.accountHash}, nullptr));
1018 EXPECT_EQ(f.missingBySeqReports(), 2uz);
1019 EXPECT_EQ(f.missingBySeqRefNum(), kLedgerSeq);
1020}
1021
1022// SHAMap::setFull() stores the sequence before the flag, and the miss that wins the flag does so
1023// with an acquire exchange, so the winner always sees the sequence. Readers keep missing the tx
1024// root while the test thread publishes through Ledger::setFull(), so the winning report is taken
1025// during publication, not after it, and must still carry the sequence.
1026//
1027// ThreadSanitizer cannot check this: both fields are atomic, so swapped stores would not be a data
1028// race, only a report of sequence zero. Nor would this test catch a swap reliably, since the two
1029// stores are adjacent instructions and a miss lands between them about once in three thousand
1030// rounds. The order is pinned by setFull() keeping both stores in one place. This test exercises
1031// the race around it and checks that the readers racing for the flag produce exactly one report.
1032TEST_F(SHAMapSyncTest, ledger_set_full_publishes_the_sequence_before_the_flag)
1033{
1034 static constexpr std::uint32_t kFirstLedgerSeq = 7;
1035 static constexpr auto kRounds = 2000uz;
1036 // Several readers keep the cache line holding the flag and the sequence moving between cores,
1037 // which widens the gap between the two stores. One reader almost never lands in it.
1038 static constexpr auto kReaders = 4uz;
1039 // Misses to wait for before publishing, so every reader has had time to enter its loop.
1040 static constexpr auto kWarmMisses = 2 * kReaders;
1041
1042 // One family shared by every round: it owns the nodestore and its reader thread, which cost far
1043 // more to set up and tear down than a Ledger does.
1044 TestNodeFamily f{j_};
1045
1046 for (auto round = 0uz; round < kRounds; ++round)
1047 {
1048 // A sequence of its own per round, so a report left over from an earlier round cannot
1049 // satisfy this round's check.
1050 auto const ledgerSeq = static_cast<std::uint32_t>(kFirstLedgerSeq + round);
1051 auto const reportsBefore = f.missingBySeqReports();
1052
1053 LedgerHeader header;
1054 header.seq = ledgerSeq;
1055 // Non-zero, so the map has a root to look for and the lookup can miss.
1056 header.txHash = UInt256{1};
1057 header.hash = calculateLedgerHash(header);
1058
1059 Ledger ledger{header, noAmendments(), f};
1060
1061 // Each reader misses without a report until setFull() gives the map a claim to withdraw.
1062 // One of them then wins the flag and reports, and all of them stop. They count their
1063 // misses so the test thread can tell when they are in their loops.
1064 std::atomic<std::size_t> misses = 0;
1066 readers.reserve(kReaders);
1067 for (auto i = 0uz; i < kReaders; ++i)
1068 {
1069 readers.emplace_back([&] {
1070 while (f.missingBySeqReports() == reportsBefore)
1071 {
1072 ledger.txMap().fetchRoot(SHAMapHash{header.txHash}, nullptr);
1073 misses.fetch_add(1, std::memory_order_relaxed);
1074 }
1075 });
1076 }
1077
1078 // Publish only once the readers are missing in their loops, so the two overlap. A thread
1079 // takes far longer to start than setFull() takes to finish, so without this wait the stores
1080 // would nearly always complete before the first miss.
1081 while (misses.load(std::memory_order_relaxed) < kWarmMisses)
1082 {
1083 }
1084 ledger.setFull();
1085 for (auto& reader : readers)
1086 reader.join();
1087
1088 EXPECT_EQ(f.missingBySeqReports(), reportsBefore + 1) << "round " << round;
1089 EXPECT_EQ(f.missingBySeqRefNum(), ledgerSeq) << "round " << round;
1090 }
1091}
1092
1094{
1095 TestNodeFamily f{j_}, f2{j_};
1096 SHAMap source{SHAMapType::FREE, f};
1097 SHAMap destination{SHAMapType::FREE, f2};
1098
1099 static constexpr auto kItemCount = 10000uz;
1100 static constexpr auto kInvariantInterval = 100uz;
1101 static constexpr auto kNodesToConfuse = 500uz;
1102
1103 for (auto i = 0uz; i < kItemCount; ++i)
1104 {
1105 source.addItem(SHAMapNodeType::TnAccountState, makeRandomAS());
1106 if (i % kInvariantInterval == 0)
1107 source.invariants();
1108 }
1109
1110 source.invariants();
1111 ASSERT_TRUE(confuseMap(source, kNodesToConfuse));
1112 source.invariants();
1113
1114 ASSERT_TRUE(source.setImmutable());
1115
1116 std::size_t count = 0;
1117 source.visitLeaves([&count]([[maybe_unused]] auto const& item) { ++count; });
1118 EXPECT_EQ(count, kItemCount);
1119
1120 std::vector<SHAMapMissingNode> missingNodes;
1121 source.walkMap(missingNodes, kMaxNodesPerRequest);
1122 EXPECT_TRUE(missingNodes.empty());
1123
1124 destination.setSynching();
1125
1126 {
1128
1129 ASSERT_TRUE(source.getNodeFat(SHAMapNodeID(), a, randBool(eng_), randInt(eng_, 2)));
1130
1131 ASSERT_FALSE(a.empty()) << "NodeSize";
1132
1133 auto node = SHAMapTreeNode::makeFromWire(makeSlice(a[0].data));
1134 if (!node)
1135 FAIL() << "Could not create node";
1136 ASSERT_TRUE(destination.addRootNode(source.getHash(), std::move(node), nullptr).isGood());
1137 }
1138
1139 do
1140 {
1142
1143 // get the list of nodes we know we need
1144 auto const nodesMissing = destination.getMissingNodes(kMaxNodesPerRequest, nullptr);
1145
1146 if (nodesMissing.empty())
1147 break;
1148
1149 // get as many nodes as possible based on this information
1151
1152 for (auto const& it : nodesMissing)
1153 {
1154 // Keep failures fatal here because this loop is data-dependent.
1155 // non-deterministic number of times and the number of tests run
1156 // should be deterministic
1157 if (!source.getNodeFat(it.first, b, randBool(eng_), randInt(eng_, 2)))
1158 FAIL() << "Unable to fetch node";
1159 }
1160
1161 // Keep failures fatal here because this loop is data-dependent.
1162 // non-deterministic number of times and the number of tests run
1163 // should be deterministic
1164 if (b.empty())
1165 FAIL() << "No nodes returned";
1166
1167 for (auto const& i : b)
1168 {
1169 // Keep failures fatal here because this loop is data-dependent.
1170 // non-deterministic number of times and the number of tests run
1171 // should be deterministic
1172 auto node = SHAMapTreeNode::makeFromWire(makeSlice(i.data));
1173 if (!node)
1174 FAIL() << "Could not create node";
1175 if (i.isLeaf != node->isLeaf())
1176 FAIL() << "Node is not a leaf";
1177 if (!destination.addKnownNode(i.nodeID, std::move(node), nullptr).isUseful())
1178 FAIL() << "Known node was not useful";
1179 }
1180 } while (true);
1181
1182 destination.clearSynching();
1183
1184 EXPECT_TRUE(source.deepCompare(destination));
1185
1186 destination.invariants();
1187}
1188
1189// The duplicate verdict also answers for a node that did not need to be added, which is the half
1190// of incDuplicate()'s contract that "already held" does not cover. addKnownNode() reaches it when
1191// the map has stopped taking nodes, and returns there before looking at the offer at all.
1192//
1193// An A/B on one offer and two maps of the same shape, so the synching state is the only difference
1194// between the two verdicts. Neither map holds the offered node, so a count that meant "already
1195// held" would be wrong for it.
1196TEST_F(SHAMapSyncTest, add_known_node_reports_duplicate_once_a_map_stops_synching)
1197{
1198 TestNodeFamily f{j_};
1199
1200 // A well-formed inner node with one child. Its contents do not matter: both verdicts below
1201 // are reached without the map reading them.
1202 auto const makeOffer = [] {
1203 Serializer s;
1204 s.addBitString(UInt256{1});
1205 s.add8(0);
1208 };
1209 ASSERT_TRUE(makeOffer());
1210
1211 SHAMapNodeID const target{1, UInt256{}};
1212
1213 // Synching, so the offer is examined, and refused because the empty root has no branch to
1214 // hook it onto. The point is that the map looked.
1215 SHAMap synching{SHAMapType::FREE, f};
1216 synching.setSynching();
1217
1218 auto const examined = synching.addKnownNode(target, makeOffer(), nullptr);
1219 EXPECT_TRUE(examined.isInvalid());
1220 EXPECT_EQ(examined.getDuplicate(), 0);
1221
1222 // The same offer to a map that has stopped taking nodes.
1223 SHAMap stopped{SHAMapType::FREE, f};
1224 stopped.setSynching();
1225 stopped.clearSynching();
1226 ASSERT_FALSE(stopped.isSynching());
1227
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";
1233}
1234
1235} // namespace xrpl::tests
A generic endpoint for log messages.
Definition Journal.h:44
void advance(std::chrono::duration< Rep, Period > const &elapsed)
Advance the clock by a duration.
bool isZero() const
Definition base_uint.h:563
iterator begin()
Definition base_uint.h:128
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
Definition chrono.h:48
Rules controlling protocol behavior.
Definition Rules.h:40
int getDuplicate() const
bool isInvalid() const
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.
bool isUseful() const
UInt256 const & asUInt256() const
Definition SHAMapHash.h:26
bool isNonZero() const
Definition SHAMapHash.h:41
Identifies a node inside a SHAMap.
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.
Definition SHAMap.h:940
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
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?
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
void setUnbacked()
Definition SHAMap.h:1007
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 isSynching() const
Definition SHAMap.h:947
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.
Definition SHAMap.h:994
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.
Definition SHAMap.h:972
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
Definition Serializer.h:273
int addBitString(BaseUInt< Bits, Tag > const &v)
Definition Serializer.h:202
int add8(unsigned char byteValue)
Slice slice() const noexcept
Definition Serializer.h:141
static TestSink & instance()
Definition TestSink.h:12
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...
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
boost::intrusive_ptr< SHAMapItem > makeRandomAS()
bool confuseMap(SHAMap &map, std::size_t count)
TestStopwatch & clock()
Definition common.h:167
std::shared_ptr< FullBelowCache > getFullBelowCache() override
Return a pointer to the Family Full Below Cache.
Definition common.h:88
std::uint32_t missingBySeqRefNum() const
The ledger sequence the most recent such report named.
Definition common.h:154
std::size_t missingBySeqReports() const
How many times a map of this family has withdrawn its claim of being complete in the database.
Definition common.h:143
T emplace_back(T... args)
T empty(T... args)
T fetch_add(T... args)
T load(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.
Definition InnerNode.h:87
SHAMapTreeNodePtr makeFullInnerNode(std::vector< InnerChild > const &children)
Assemble an inner node in the wire format's full form.
Definition InnerNode.h:42
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)
Definition Slice.h:228
BaseUInt< 256 > UInt256
Definition base_uint.h:581
boost::intrusive_ptr< SHAMapItem > makeShamapitem(UInt256 const &tag, Slice data)
Definition SHAMapItem.h:148
Integral randInt(Engine &engine, Integral min, Integral max)
Return a uniformly distributed random integer.
Dest safeDowncast(Src *s) noexcept
Definition safe_cast.h:84
UInt256 calculateLedgerHash(LedgerHeader const &info)
Calculate the hash of a ledger header.
std::vector< unsigned char > Blob
Storage for linear binary data.
Definition Blob.h:11
T push_back(T... args)
T reserve(T... args)
T store(T... args)
Reflects the fee settings for a particular ledger.
Information about the notional ledger backing the view.
A chain of inner nodes in wire form, from the root down to one deepest node, each with one real child...
Definition DeepChain.h:38
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...
Definition DeepChain.h:135
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...
Definition DeepChain.h:78
SHAMapAddNode addOffendingNode(SHAMap &map) const
Offer the deepest node, which for a fabricated chain is the inner node at SHAMap::kLeafDepth,...
Definition DeepChain.h:196
bool fill(SHAMap &map) const
Fill a synching map, stopping one level short of the deepest node so the caller offers that one itsel...
Definition DeepChain.h:170
SHAMapTreeNodePtr nodeAt(unsigned int depth) const
The node the chain holds at the given depth, root first.
Definition DeepChain.h:109
static DeepChain toLeaf(unsigned int depth, unsigned int seed=1)
A chain ending in a real transaction leaf, which completes an acquisition.
Definition DeepChain.h:95
T yield(T... args)