Merge branch 'develop' into bthomee/graceful

src/libxrpl/shamap/SHAMap.cpp

@@ -142,9 +142,23 @@ SHAMap::walkTowardsKey(uint256 const& id, SharedPtrNodeStack* stack) const
         auto const inner = intr_ptr::staticPointerCast<SHAMapInnerNode>(inNode);
         auto const branch = selectBranch(nodeID, id);
         if (inner->isEmptyBranch(branch))
+        {
+            // An empty branch during a walk means "key not present".
             return nullptr;
+        }
 
-        inNode = descendThrow(*inner, branch);
+        inNode.adopt(descend(inner.get(), branch));
+        if (!inNode)
+        {
+            JLOG(journal_.warn()) << "xrpl::SHAMap::walkTowardsKey: missing child node "
+                                  << inner->getChildHash(branch);
+            // Clear the stack so callers that use stack.empty() as a missing-node sentinel reliably
+            // detect this error condition, rather than proceeding with a partially-populated stack
+            // whose top is an inner node instead of the expected leaf.
+            if (stack != nullptr)
+                *stack = {};
+            return nullptr;
+        }
         nodeID = nodeID.getChildNodeID(branch);
     }
 
@@ -322,9 +336,6 @@ SHAMap::descend(SHAMapInnerNode& parent, int branch) const
         return node;
 
     node = fetchNode(parent.getChildHash(branch));
-    if (!node)
-        return {};
-
     node = parent.canonicalizeChild(branch, std::move(node));
     return node;
 }
@@ -336,7 +347,7 @@ SHAMap::descendNoStore(SHAMapInnerNode& parent, int branch) const
 {
     SHAMapTreeNodePtr ret = parent.getChild(branch);
     if (!ret && backed_)
-        ret = fetchNode(parent.getChildHash(branch));
+        ret = fetchNodeNT(parent.getChildHash(branch));
     return ret;
 }
 

src/libxrpl/shamap/SHAMapSync.cpp

@@ -67,6 +67,15 @@ SHAMap::visitNodes(std::function<bool(SHAMapTreeNode&)> const& function) const
             if (!node->isEmptyBranch(pos))
             {
                 SHAMapTreeNodePtr const child = descendNoStore(*node, pos);
+                if (!child)
+                {
+                    // Child node couldn't be fetched, which can be for a variety of reasons (e.g.
+                    // partial sync, node evicted after database rotation), so skip this subtree.
+                    JLOG(journal_.info())
+                        << "visitNodes: missing child node " << node->getChildHash(pos);
+                    ++pos;
+                    continue;
+                }
                 if (!function(*child))
                     return;
 

src/tests/libxrpl/CMakeLists.txt

@@ -27,6 +27,7 @@ set(test_modules
     basics
     crypto
     json
+    shamap
     tx
     protocol_autogen
 )

src/tests/libxrpl/helpers/SHAMapTestHelpers.h

@@ -0,0 +1,53 @@
+#pragma once
+
+#include <xrpl/basics/random.h>
+#include <xrpl/protocol/Serializer.h>
+#include <xrpl/shamap/SHAMap.h>
+#include <xrpl/shamap/SHAMapItem.h>
+#include <xrpl/shamap/SHAMapTreeNode.h>
+
+#include <boost/smart_ptr/intrusive_ptr.hpp>
+
+#include <cassert>
+#include <cstdint>
+
+namespace xrpl::test {
+
+/** Return a randomly-generated SHAMapItem using the supplied engine. */
+template <class Engine>
+boost::intrusive_ptr<SHAMapItem>
+makeRandomSHAMapItem(Engine& engine)
+{
+    Serializer s;
+    for (int d = 0; d < 3; ++d)
+        s.add32(randInt<std::uint32_t>(engine));
+    return makeShamapitem(s.getSHA512Half(), s.slice());
+}
+
+struct NodeCounts
+{
+    int inner = 0;
+    int leaves = 0;
+};
+
+/** Count all inner and leaf nodes reachable via visitNodes. */
+inline NodeCounts
+countNodes(SHAMap const& map)
+{
+    NodeCounts counts;
+    map.visitNodes([&counts](SHAMapTreeNode& node) {
+        assert(node.isInner() || node.isLeaf());
+        if (node.isInner())
+        {
+            ++counts.inner;
+        }
+        else if (node.isLeaf())
+        {
+            ++counts.leaves;
+        }
+        return true;
+    });
+    return counts;
+}
+
+}  // namespace xrpl::test

src/tests/libxrpl/helpers/TestRNG.h

@@ -0,0 +1,20 @@
+#pragma once
+
+#include <cstdint>
+#include <random>
+
+namespace xrpl::test {
+
+/** Return a pseudo-random engine seeded with the given value.
+
+    Each test should call this with its own fixed seed so that results are
+    fully reproducible when a test is retried in isolation, regardless of the
+    order in which other tests ran.
+*/
+inline std::mt19937
+rng(std::uint32_t seed)
+{
+    return std::mt19937{seed};
+}
+
+}  // namespace xrpl::test

src/tests/libxrpl/shamap/SHAMapMissingNode.cpp

@@ -0,0 +1,126 @@
+#include <xrpl/shamap/SHAMapMissingNode.h>
+
+#include <xrpl/basics/Blob.h>
+#include <xrpl/basics/Slice.h>
+#include <xrpl/beast/utility/Journal.h>
+#include <xrpl/shamap/SHAMap.h>
+#include <xrpl/shamap/SHAMapNodeID.h>
+#include <xrpl/shamap/SHAMapTreeNode.h>
+
+#include <gtest/gtest.h>
+#include <helpers/SHAMapTestHelpers.h>
+#include <helpers/TestFamily.h>
+#include <helpers/TestRNG.h>
+
+#include <cstddef>
+#include <cstdint>
+#include <utility>
+#include <vector>
+
+using namespace xrpl;
+
+namespace {
+
+// Seed for the random number generator used to create the test data.
+constexpr std::uint32_t kSeed = 0xdeadbeefU;
+
+// Sync source into dest, delivering at most nodeLimit nodes requested by dest.getMissingNodes().
+// This intentionally leaves parts of the tree absent to simulate missing subtrees.
+void
+syncWithLimit(SHAMap const& source, SHAMap& dest, std::size_t nodeLimit)
+{
+    // Copy over the root node from the source map to the dest map.
+    std::vector<std::pair<SHAMapNodeID, Blob>> rootData;
+    if (!source.getNodeFat(SHAMapNodeID{}, rootData, false, 0))
+        FAIL() << "Could not get root node";
+    if (!dest.addRootNode(source.getHash(), makeSlice(rootData[0].second), nullptr).isGood())
+        FAIL() << "Could not add root node";
+
+    // Fetch nodes from the source map and deliver them to the dest map until we reach the limit or
+    // there are no more missing nodes.
+    std::size_t delivered = 0;
+    do
+    {
+        auto missing = dest.getMissingNodes(2048, nullptr);
+        if (missing.empty())
+            break;
+
+        for (auto const& [nodeID, _] : missing)
+        {
+            if (delivered >= nodeLimit)
+                return;
+
+            std::vector<std::pair<SHAMapNodeID, Blob>> nodeData;
+            if (!source.getNodeFat(nodeID, nodeData, false, 0))
+                continue;
+
+            for (auto const& [id, blob] : nodeData)
+            {
+                if (!dest.addKnownNode(id, makeSlice(blob), nullptr).isGood())
+                    FAIL() << "Could not add known node";
+            }
+
+            ++delivered;
+        }
+    } while (true);
+}
+
+}  // namespace
+
+// visitLeaves on a map with missing child nodes must not throw and must produce a partial
+// traversal, skipping the unavailable subtrees.
+TEST(SHAMapMissingNode, visitLeavesSkipsMissingNodes)
+{
+    auto rngEngine = test::rng(kSeed);
+
+    beast::Journal const j{beast::Journal::getNullSink()};
+    test::TestFamily sourceFamily(j);
+    test::TestFamily destFamily(j);
+
+    // Create a map and add random nodes to it.
+    SHAMap source(SHAMapType::FREE, sourceFamily);
+    static constexpr auto kItems = 200;
+    for (auto i = 0; i < kItems; ++i)
+        source.addItem(SHAMapNodeType::TnAccountState, test::makeRandomSHAMapItem(rngEngine));
+    source.setImmutable();
+
+    // Count the total number of leaf nodes in the source map, which should match the number of
+    // items that were added.
+    auto beforeCount = 0;
+    source.visitLeaves([&beforeCount](auto const&) { ++beforeCount; });
+    EXPECT_EQ(beforeCount, kItems);
+
+    // Deliver only 3 nodes so most subtrees remain absent from destFamily's DB, simulating child
+    // nodes evicted after a rotation or otherwise unavailable.
+    SHAMap dest(SHAMapType::FREE, source.getHash().asUInt256(), destFamily);
+    dest.setSynching();
+    ASSERT_NO_FATAL_FAILURE(syncWithLimit(source, dest, 3));
+
+    // Count the total number of leaf nodes in the dest map. Since most subtrees are now missing,
+    // the traversal will result in fewer nodes being visited. The function must not throw.
+    auto afterCount = 0;
+    EXPECT_NO_THROW(dest.visitLeaves([&afterCount](auto const&) { ++afterCount; }));
+    EXPECT_LT(afterCount, beforeCount);
+}
+
+// visitNodes on a fully populated map must visit every node without skipping.
+TEST(SHAMapMissingNode, visitNodesCompleteMap)
+{
+    auto rngEngine = test::rng(kSeed);
+
+    beast::Journal const j{beast::Journal::getNullSink()};
+    test::TestFamily family(j);
+
+    // Create a map and add random nodes to it.
+    SHAMap map(SHAMapType::FREE, family);
+    static constexpr auto kItems = 50;
+    for (auto i = 0; i < kItems; ++i)
+        map.addItem(SHAMapNodeType::TnAccountState, test::makeRandomSHAMapItem(rngEngine));
+    map.setImmutable();
+
+    // There should be an identical number of leaf nodes as the number of items that were added.
+    // During inserting the items, the map may have created additional inner nodes to store them.
+    auto const counts = test::countNodes(map);
+    EXPECT_EQ(counts.leaves, kItems);
+    EXPECT_GE(counts.inner + counts.leaves, kItems);
+}