sync with develop

.github/scripts/levelization/results/ordering.txt

@@ -144,6 +144,7 @@ test.toplevel > test.csf
 test.toplevel > xrpl.json
 test.unit_test > xrpl.basics
 tests.libxrpl > xrpl.basics
+tests.libxrpl > xrpl.ledger
 tests.libxrpl > xrpl.json
 tests.libxrpl > xrpl.net
 xrpl.json > xrpl.basics

include/xrpl/basics/TaggedCache.h

@@ -170,9 +170,6 @@ public:
     bool
     retrieve(key_type const& key, T& data);
 
-    mutex_type&
-    peekMutex();
-
     std::vector<key_type>
     getKeys() const;
 

include/xrpl/basics/TaggedCache.ipp

@@ -668,29 +668,6 @@ TaggedCache<
     return true;
 }
 
-template <
-    class Key,
-    class T,
-    bool IsKeyCache,
-    class SharedWeakUnionPointer,
-    class SharedPointerType,
-    class Hash,
-    class KeyEqual,
-    class Mutex>
-inline auto
-TaggedCache<
-    Key,
-    T,
-    IsKeyCache,
-    SharedWeakUnionPointer,
-    SharedPointerType,
-    Hash,
-    KeyEqual,
-    Mutex>::peekMutex() -> mutex_type&
-{
-    return m_mutex;
-}
-
 template <
     class Key,
     class T,

include/xrpl/ledger/LedgerIndexMap.h

@@ -0,0 +1,138 @@
+//------------------------------------------------------------------------------
+/*
+    This file is part of rippled: https://github.com/ripple/rippled
+    Copyright (c) 2012, 2013 Ripple Labs Inc.
+
+    Permission to use, copy, modify, and/or distribute this software for any
+    purpose  with  or without fee is hereby granted, provided that the above
+    copyright notice and this permission notice appear in all copies.
+
+    THE  SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+    WITH  REGARD  TO  THIS  SOFTWARE  INCLUDING  ALL  IMPLIED  WARRANTIES  OF
+    MERCHANTABILITY  AND  FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+    ANY  SPECIAL ,  DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+    WHATSOEVER  RESULTING  FROM  LOSS  OF  USE, DATA OR PROFITS, WHETHER IN AN
+    ACTION  OF  CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+    OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+*/
+//==============================================================================
+
+#ifndef RIPPLE_APP_LEDGER_INDEX_MAP_H_INCLUDED
+#define RIPPLE_APP_LEDGER_INDEX_MAP_H_INCLUDED
+
+#include <algorithm>
+#include <mutex>
+#include <unordered_map>
+
+namespace ripple {
+
+template <class Key, class Mapped>
+class LedgerIndexMap
+{
+public:
+    LedgerIndexMap() = default;
+    explicit LedgerIndexMap(std::size_t reserve_capacity)
+    {
+        data_.reserve(reserve_capacity);
+    }
+
+    LedgerIndexMap(LedgerIndexMap const&) = delete;
+    LedgerIndexMap&
+    operator=(LedgerIndexMap const&) = delete;
+    LedgerIndexMap(LedgerIndexMap&&) = delete;
+    LedgerIndexMap&
+    operator=(LedgerIndexMap&&) = delete;
+
+    Mapped&
+    operator[](Key const& k)
+    {
+        std::lock_guard lock(mutex_);
+        return data_[k];
+    }
+
+    Mapped&
+    operator[](Key&& k)
+    {
+        std::lock_guard lock(mutex_);
+        return data_[std::move(k)];
+    }
+
+    [[nodiscard]] Mapped*
+    get(Key const& k)
+    {
+        std::lock_guard lock(mutex_);
+        auto it = data_.find(k);
+        return it == data_.end() ? nullptr : &it->second;
+    }
+
+    [[nodiscard]] Mapped const*
+    get(Key const& k) const
+    {
+        std::lock_guard lock(mutex_);
+        auto it = data_.find(k);
+        return it == data_.end() ? nullptr : &it->second;
+    }
+
+    template <class... Args>
+    Mapped&
+    put(Key const& k, Args&&... args)
+    {
+        std::lock_guard lock(mutex_);
+        auto [it, inserted] = data_.try_emplace(k, std::forward<Args>(args)...);
+        if (!inserted)
+            it->second = Mapped(std::forward<Args>(args)...);
+        return it->second;
+    }
+
+    bool
+    contains(Key const& k) const
+    {
+        std::lock_guard lock(mutex_);
+        return data_.find(k) != data_.end();
+    }
+
+    std::size_t
+    size() const noexcept
+    {
+        std::lock_guard lock(mutex_);
+        return data_.size();
+    }
+
+    bool
+    empty() const noexcept
+    {
+        std::lock_guard lock(mutex_);
+        return data_.empty();
+    }
+
+    void
+    reserve(std::size_t n)
+    {
+        std::lock_guard lock(mutex_);
+        data_.reserve(n);
+    }
+
+    void
+    rehash(std::size_t n)
+    {
+        std::lock_guard lock(mutex_);
+        data_.rehash(n);
+    }
+
+    std::size_t
+    eraseBefore(Key const& cutoff)
+    {
+        std::lock_guard lock(mutex_);
+        auto const before = data_.size();
+        std::erase_if(data_, [&](auto const& kv) { return kv.first < cutoff; });
+        return before - data_.size();
+    }
+
+private:
+    std::unordered_map<Key, Mapped> data_;
+    mutable std::mutex mutex_;
+};
+
+}  // namespace ripple
+
+#endif  // RIPPLE_APP_LEDGER_INDEX_MAP_H_INCLUDED

src/tests/libxrpl/CMakeLists.txt

@@ -16,3 +16,5 @@ xrpl_add_test(json)
 target_link_libraries(xrpl.test.json PRIVATE xrpl.imports.test)
 xrpl_add_test(net)
 target_link_libraries(xrpl.test.net PRIVATE xrpl.imports.test)
+xrpl_add_test(ledger)
+target_link_libraries(xrpl.test.ledger PRIVATE xrpl.imports.test)

src/tests/libxrpl/ledger/LedgerIndexMap.cpp

@@ -0,0 +1,210 @@
+//------------------------------------------------------------------------------
+/*
+    This file is part of rippled: https://github.com/ripple/rippled
+    Copyright (c) 2012 Ripple Labs Inc.
+
+    Permission to use, copy, modify, and/or distribute this software for any
+    purpose  with  or without fee is hereby granted, provided that the above
+    copyright notice and this permission notice appear in all copies.
+
+    THE  SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+    WITH  REGARD  TO  THIS  SOFTWARE  INCLUDING ALL  IMPLIED  WARRANTIES  OF
+    MERCHANTABILITY  AND  FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+    ANY  SPECIAL ,  DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+    WHATSOEVER  RESULTING  FROM  LOSS  OF USE, DATA OR PROFITS, WHETHER IN AN
+    ACTION  OF  CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+    OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+*/
+//==============================================================================
+
+#include <xrpl/ledger/LedgerIndexMap.h>
+
+#include <doctest/doctest.h>
+
+#include <cstdint>
+#include <string>
+#include <vector>
+
+using namespace ripple;
+
+TEST_SUITE_BEGIN("LedgerIndexMap");
+
+using TestMap = LedgerIndexMap<int, std::string>;
+
+TEST_CASE("Default empty")
+{
+    TestMap m;
+    CHECK(m.size() == 0);
+    CHECK(m.empty());
+    CHECK(m.get(42) == nullptr);
+    CHECK_FALSE(m.contains(42));
+}
+
+TEST_CASE("Operator bracket inserts default")
+{
+    TestMap m;
+    auto& v = m[10];
+    CHECK(m.size() == 1);
+    CHECK(m.contains(10));
+    CHECK(v.empty());
+}
+
+TEST_CASE("Operator bracket, rvalue key")
+{
+    TestMap m;
+    int k = 7;
+    auto& v1 = m[std::move(k)];
+    v1 = "seven";
+    CHECK(m.size() == 1);
+    auto* got = m.get(7);
+    REQUIRE(got != nullptr);
+    CHECK(*got == "seven");
+}
+
+TEST_CASE("Insert through put")
+{
+    TestMap m;
+    auto& v = m.put(20, "twenty");
+    CHECK(v == "twenty");
+    auto* got = m.get(20);
+    REQUIRE(got != nullptr);
+    CHECK(*got == "twenty");
+    CHECK(m.size() == 1);
+}
+
+TEST_CASE("Overwrite existing key with put")
+{
+    TestMap m;
+    m.put(5, "five");
+    CHECK(m.size() == 1);
+    m.put(5, "FIVE");
+    CHECK(m.size() == 1);
+    auto* got = m.get(5);
+    REQUIRE(got != nullptr);
+    CHECK(*got == "FIVE");
+}
+
+TEST_CASE("Once found, one not found")
+{
+    TestMap m;
+    m.put(1, "one");
+    CHECK(m.get(1) != nullptr);
+    CHECK(m.get(2) == nullptr);
+}
+
+TEST_CASE("Try eraseBefore - nothing to do")
+{
+    TestMap m;
+    m.put(10, "a");
+    m.put(11, "b");
+    m.put(12, "c");
+    CHECK(m.eraseBefore(10) == 0);
+    CHECK(m.size() == 3);
+    CHECK(m.contains(10));
+    CHECK(m.contains(11));
+    CHECK(m.contains(12));
+}
+
+TEST_CASE("eraseBefore - removes several entries")
+{
+    TestMap m;
+    m.put(10, "a");
+    m.put(11, "b");
+    m.put(12, "c");
+    m.put(13, "d");
+    CHECK(m.eraseBefore(12) == 2);
+    CHECK_FALSE(m.contains(10));
+    CHECK_FALSE(m.contains(11));
+    CHECK(m.contains(12));
+    CHECK(m.contains(13));
+    CHECK(m.size() == 2);
+}
+
+TEST_CASE("eraseBefore - removes all entries")
+{
+    TestMap m;
+    m.put(1, "x");
+    m.put(2, "y");
+    CHECK(m.eraseBefore(1000) == 2);
+    CHECK(m.size() == 0);
+    CHECK(m.empty());
+}
+
+TEST_CASE("eraseBefore - same call, second time nothing to do")
+{
+    TestMap m;
+    m.put(10, "a");
+    m.put(11, "b");
+    m.put(12, "c");
+    CHECK(m.eraseBefore(12) == 2);
+    CHECK(m.contains(12));
+    CHECK(m.eraseBefore(12) == 0);
+    CHECK(m.size() == 1);
+}
+
+TEST_CASE("eraseBefore - single entry removed")
+{
+    TestMap m;
+    m.put(10, "v1");
+    m.put(10, "v2");
+    m.put(10, "v3");
+    CHECK(m.size() == 1);
+    CHECK(m.eraseBefore(11) == 1);
+    CHECK(m.size() == 0);
+}
+
+TEST_CASE("eraseBefore - outlier still removed in one call")
+{
+    TestMap m;
+    m.put(10, "a");
+    m.put(12, "c");
+    m.put(11, "b");  // out-of-order insert
+
+    CHECK(m.eraseBefore(12) == 2);  // removes 10 and 11
+    CHECK_FALSE(m.contains(10));
+    CHECK_FALSE(m.contains(11));
+    CHECK(m.contains(12));
+    CHECK(m.size() == 1);
+}
+
+TEST_CASE("eraseBefore - erase in two steps (one first, then some more)")
+{
+    TestMap m;
+    for (int k : {10, 11, 12, 13})
+        m.put(k, std::to_string(k));
+
+    CHECK(m.eraseBefore(11) == 1);
+    CHECK_FALSE(m.contains(10));
+    CHECK(m.size() == 3);
+
+    CHECK(m.eraseBefore(13) == 2);
+    CHECK_FALSE(m.contains(11));
+    CHECK_FALSE(m.contains(12));
+    CHECK(m.contains(13));
+    CHECK(m.size() == 1);
+}
+
+TEST_CASE("rehash does not lose entries")
+{
+    TestMap m;
+    for (int k = 0; k < 16; ++k)
+        m.put(k, "v" + std::to_string(k));
+
+    m.reserve(64);
+    m.rehash(32);
+
+    for (int k = 0; k < 16; ++k)
+    {
+        auto* v = m.get(k);
+        REQUIRE(v != nullptr);
+        CHECK(*v == "v" + std::to_string(k));
+    }
+
+    CHECK(m.eraseBefore(8) == 8);
+    for (int k = 0; k < 8; ++k)
+        CHECK_FALSE(m.contains(k));
+    for (int k = 8; k < 16; ++k)
+        CHECK(m.contains(k));
+}
+
+TEST_SUITE_END();

src/tests/libxrpl/ledger/main.cpp

@@ -0,0 +1,2 @@
+#define DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN
+#include <doctest/doctest.h>

src/xrpld/app/ledger/LedgerHistory.cpp

@@ -27,8 +27,6 @@
 
 namespace ripple {
 
-// FIXME: Need to clean up ledgers by index at some point
-
 LedgerHistory::LedgerHistory(
     beast::insight::Collector::ptr const& collector,
     Application& app)
@@ -47,6 +45,7 @@ LedgerHistory::LedgerHistory(
           std::chrono::minutes{5},
           stopwatch(),
           app_.journal("TaggedCache"))
+    , mLedgersByIndex(512)
     , j_(app.journal("LedgerHistory"))
 {
 }
@@ -63,8 +62,6 @@ LedgerHistory::insert(
         ledger->stateMap().getHash().isNonZero(),
         "ripple::LedgerHistory::insert : nonzero hash");
 
-    std::unique_lock sl(m_ledgers_by_hash.peekMutex());
-
     bool const alreadyHad = m_ledgers_by_hash.canonicalize_replace_cache(
         ledger->info().hash, ledger);
     if (validated)
@@ -76,25 +73,18 @@ LedgerHistory::insert(
 LedgerHash
 LedgerHistory::getLedgerHash(LedgerIndex index)
 {
-    std::unique_lock sl(m_ledgers_by_hash.peekMutex());
+    if (auto p = mLedgersByIndex.get(index))
-    if (auto it = mLedgersByIndex.find(index); it != mLedgersByIndex.end())
+        return *p;
-        return it->second;
     return {};
 }
 
 std::shared_ptr<Ledger const>
 LedgerHistory::getLedgerBySeq(LedgerIndex index)
 {
+    if (auto p = mLedgersByIndex.get(index))
     {
-        std::unique_lock sl(m_ledgers_by_hash.peekMutex());
+        uint256 const hash = *p;
-        auto it = mLedgersByIndex.find(index);
+        return getLedgerByHash(hash);
-
-        if (it != mLedgersByIndex.end())
-        {
-            uint256 hash = it->second;
-            sl.unlock();
-            return getLedgerByHash(hash);
-        }
     }
 
     std::shared_ptr<Ledger const> ret = loadByIndex(index, app_);
@@ -108,8 +98,6 @@ LedgerHistory::getLedgerBySeq(LedgerIndex index)
 
     {
         // Add this ledger to the local tracking by index
-        std::unique_lock sl(m_ledgers_by_hash.peekMutex());
-
         XRPL_ASSERT(
             ret->isImmutable(),
             "ripple::LedgerHistory::getLedgerBySeq : immutable result ledger");
@@ -458,8 +446,6 @@ LedgerHistory::builtLedger(
     XRPL_ASSERT(
         !hash.isZero(), "ripple::LedgerHistory::builtLedger : nonzero hash");
 
-    std::unique_lock sl(m_consensus_validated.peekMutex());
-
     auto entry = std::make_shared<cv_entry>();
     m_consensus_validated.canonicalize_replace_client(index, entry);
 
@@ -500,8 +486,6 @@ LedgerHistory::validatedLedger(
         !hash.isZero(),
         "ripple::LedgerHistory::validatedLedger : nonzero hash");
 
-    std::unique_lock sl(m_consensus_validated.peekMutex());
-
     auto entry = std::make_shared<cv_entry>();
     m_consensus_validated.canonicalize_replace_client(index, entry);
 
@@ -535,13 +519,13 @@ LedgerHistory::validatedLedger(
 bool
 LedgerHistory::fixIndex(LedgerIndex ledgerIndex, LedgerHash const& ledgerHash)
 {
-    std::unique_lock sl(m_ledgers_by_hash.peekMutex());
+    if (auto cur = mLedgersByIndex.get(ledgerIndex))
-    auto it = mLedgersByIndex.find(ledgerIndex);
-
-    if ((it != mLedgersByIndex.end()) && (it->second != ledgerHash))
     {
-        it->second = ledgerHash;
+        if (*cur != ledgerHash)
-        return false;
+        {
+            mLedgersByIndex.put(ledgerIndex, ledgerHash);
+            return false;
+        }
     }
     return true;
 }
@@ -549,12 +533,24 @@ LedgerHistory::fixIndex(LedgerIndex ledgerIndex, LedgerHash const& ledgerHash)
 void
 LedgerHistory::clearLedgerCachePrior(LedgerIndex seq)
 {
+    std::size_t hashesCleared = 0;
     for (LedgerHash it : m_ledgers_by_hash.getKeys())
     {
         auto const ledger = getLedgerByHash(it);
         if (!ledger || ledger->info().seq < seq)
+        {
             m_ledgers_by_hash.del(it, false);
+            ++hashesCleared;
+        }
     }
+    JLOG(j_.debug()) << "LedgersByHash: cleared " << hashesCleared
+                     << " entries before seq " << seq << " (total now "
+                     << m_ledgers_by_hash.size() << ")";
+
+    std::size_t const indexesCleared = mLedgersByIndex.eraseBefore(seq);
+    JLOG(j_.debug()) << "LedgerIndexMap: cleared " << indexesCleared
+                     << " index entries before seq " << seq << " (total now "
+                     << mLedgersByIndex.size() << ")";
 }
 
 }  // namespace ripple

src/xrpld/app/ledger/LedgerHistory.h

@@ -24,6 +24,7 @@
 #include <xrpld/app/main/Application.h>
 
 #include <xrpl/beast/insight/Collector.h>
+#include <xrpl/ledger/LedgerIndexMap.h>
 #include <xrpl/protocol/RippleLedgerHash.h>
 
 #include <optional>
@@ -149,7 +150,8 @@ private:
     ConsensusValidated m_consensus_validated;
 
     // Maps ledger indexes to the corresponding hash.
-    std::map<LedgerIndex, LedgerHash> mLedgersByIndex;  // validated ledgers
+    ripple::LedgerIndexMap<LedgerIndex, LedgerHash>
+        mLedgersByIndex;  // validated ledgers
 
     beast::Journal j_;
 };