test: add cache entry linked list tests

Co-Authored-By: l0rinc <pap.lorinc@gmail.com>

3 files changed, 227 insertions, 3 deletions

diff --git a/src/Makefile.test.include b/src/Makefile.test.include
index e2d6f94b24..3a6d56c9e1 100644
--- a/src/Makefile.test.include
+++ b/src/Makefile.test.include
@@ -85,6 +85,7 @@ BITCOIN_TESTS =\
   test/checkqueue_tests.cpp \
   test/cluster_linearize_tests.cpp \
   test/coins_tests.cpp \
+  test/coinscachepair_tests.cpp \
   test/coinstatsindex_tests.cpp \
   test/common_url_tests.cpp \
   test/compilerbug_tests.cpp \
diff --git a/src/test/coins_tests.cpp b/src/test/coins_tests.cpp
index 4fe560df95..a8af21c687 100644
--- a/src/test/coins_tests.cpp
+++ b/src/test/coins_tests.cpp
@@ -78,7 +78,7 @@ class CCoinsViewCacheTest : public CCoinsViewCache
 public:
     explicit CCoinsViewCacheTest(CCoinsView* _base) : CCoinsViewCache(_base) {}
 
-    void SelfTest() const
+    void SelfTest(bool sanity_check = true) const
     {
         // Manually recompute the dynamic usage of the whole data, and compare it.
         size_t ret = memusage::DynamicUsage(cacheCoins);
@@ -89,6 +89,9 @@ public:
         }
         BOOST_CHECK_EQUAL(GetCacheSize(), count);
         BOOST_CHECK_EQUAL(DynamicMemoryUsage(), ret);
+        if (sanity_check) {
+            SanityCheck();
+        }
     }
 
     CCoinsMap& map() const { return cacheCoins; }
@@ -637,7 +640,7 @@ static void CheckAccessCoin(CAmount base_value, CAmount cache_value, CAmount exp
 {
     SingleEntryCacheTest test(base_value, cache_value, cache_flags);
     test.cache.AccessCoin(OUTPOINT);
-    test.cache.SelfTest();
+    test.cache.SelfTest(/*sanity_check=*/false);
 
     CAmount result_value;
     char result_flags;
@@ -806,7 +809,7 @@ void CheckWriteCoins(CAmount parent_value, CAmount child_value, CAmount expected
     char result_flags;
     try {
         WriteCoinsViewEntry(test.cache, child_value, child_flags);
-        test.cache.SelfTest();
+        test.cache.SelfTest(/*sanity_check=*/false);
         GetCoinsMapEntry(test.cache.map(), result_value, result_flags);
     } catch (std::logic_error&) {
         result_value = FAIL;
@@ -919,6 +922,7 @@ void TestFlushBehavior(
         // Flush in reverse order to ensure that flushes happen from children up.
         for (auto i = all_caches.rbegin(); i != all_caches.rend(); ++i) {
             auto& cache = *i;
+            cache->SanityCheck();
             // hashBlock must be filled before flushing to disk; value is
             // unimportant here. This is normally done during connect/disconnect block.
             cache->SetBestBlock(InsecureRand256());
diff --git a/src/test/coinscachepair_tests.cpp b/src/test/coinscachepair_tests.cpp
new file mode 100644
index 0000000000..61840f1f09
--- /dev/null
+++ b/src/test/coinscachepair_tests.cpp
@@ -0,0 +1,219 @@
+// Copyright (c) 2024-present The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include <coins.h>
+
+#include <boost/test/unit_test.hpp>
+
+#include <list>
+
+BOOST_AUTO_TEST_SUITE(coinscachepair_tests)
+
+static constexpr auto NUM_NODES{4};
+
+std::list<CoinsCachePair> CreatePairs(CoinsCachePair& sentinel)
+{
+    std::list<CoinsCachePair> nodes;
+    for (auto i{0}; i < NUM_NODES; ++i) {
+        nodes.emplace_back();
+
+        auto node{std::prev(nodes.end())};
+        node->second.AddFlags(CCoinsCacheEntry::DIRTY, *node, sentinel);
+
+        BOOST_CHECK_EQUAL(node->second.GetFlags(), CCoinsCacheEntry::DIRTY);
+        BOOST_CHECK_EQUAL(node->second.Next(), &sentinel);
+        BOOST_CHECK_EQUAL(sentinel.second.Prev(), &(*node));
+
+        if (i > 0) {
+            BOOST_CHECK_EQUAL(std::prev(node)->second.Next(), &(*node));
+            BOOST_CHECK_EQUAL(node->second.Prev(), &(*std::prev(node)));
+        }
+    }
+    return nodes;
+}
+
+BOOST_AUTO_TEST_CASE(linked_list_iteration)
+{
+    CoinsCachePair sentinel;
+    sentinel.second.SelfRef(sentinel);
+    auto nodes{CreatePairs(sentinel)};
+
+    // Check iterating through pairs is identical to iterating through a list
+    auto node{sentinel.second.Next()};
+    for (const auto& expected : nodes) {
+        BOOST_CHECK_EQUAL(&expected, node);
+        node = node->second.Next();
+    }
+    BOOST_CHECK_EQUAL(node, &sentinel);
+
+    // Check iterating through pairs is identical to iterating through a list
+    // Clear the flags during iteration
+    node = sentinel.second.Next();
+    for (const auto& expected : nodes) {
+        BOOST_CHECK_EQUAL(&expected, node);
+        auto next = node->second.Next();
+        node->second.ClearFlags();
+        node = next;
+    }
+    BOOST_CHECK_EQUAL(node, &sentinel);
+    // Check that sentinel's next and prev are itself
+    BOOST_CHECK_EQUAL(sentinel.second.Next(), &sentinel);
+    BOOST_CHECK_EQUAL(sentinel.second.Prev(), &sentinel);
+
+    // Delete the nodes from the list to make sure there are no dangling pointers
+    for (auto it{nodes.begin()}; it != nodes.end(); it = nodes.erase(it)) {
+        BOOST_CHECK_EQUAL(it->second.GetFlags(), 0);
+    }
+}
+
+BOOST_AUTO_TEST_CASE(linked_list_iterate_erase)
+{
+    CoinsCachePair sentinel;
+    sentinel.second.SelfRef(sentinel);
+    auto nodes{CreatePairs(sentinel)};
+
+    // Check iterating through pairs is identical to iterating through a list
+    // Erase the nodes as we iterate through, but don't clear flags
+    // The flags will be cleared by the CCoinsCacheEntry's destructor
+    auto node{sentinel.second.Next()};
+    for (auto expected{nodes.begin()}; expected != nodes.end(); expected = nodes.erase(expected)) {
+        BOOST_CHECK_EQUAL(&(*expected), node);
+        node = node->second.Next();
+    }
+    BOOST_CHECK_EQUAL(node, &sentinel);
+
+    // Check that sentinel's next and prev are itself
+    BOOST_CHECK_EQUAL(sentinel.second.Next(), &sentinel);
+    BOOST_CHECK_EQUAL(sentinel.second.Prev(), &sentinel);
+}
+
+BOOST_AUTO_TEST_CASE(linked_list_random_deletion)
+{
+    CoinsCachePair sentinel;
+    sentinel.second.SelfRef(sentinel);
+    auto nodes{CreatePairs(sentinel)};
+
+    // Create linked list sentinel->n1->n2->n3->n4->sentinel
+    auto n1{nodes.begin()};
+    auto n2{std::next(n1)};
+    auto n3{std::next(n2)};
+    auto n4{std::next(n3)};
+
+    // Delete n2
+    // sentinel->n1->n3->n4->sentinel
+    nodes.erase(n2);
+    // Check that n1 now points to n3, and n3 still points to n4
+    // Also check that flags were not altered
+    BOOST_CHECK_EQUAL(n1->second.GetFlags(), CCoinsCacheEntry::DIRTY);
+    BOOST_CHECK_EQUAL(n1->second.Next(), &(*n3));
+    BOOST_CHECK_EQUAL(n3->second.GetFlags(), CCoinsCacheEntry::DIRTY);
+    BOOST_CHECK_EQUAL(n3->second.Next(), &(*n4));
+    BOOST_CHECK_EQUAL(n3->second.Prev(), &(*n1));
+
+    // Delete n1
+    // sentinel->n3->n4->sentinel
+    nodes.erase(n1);
+    // Check that sentinel now points to n3, and n3 still points to n4
+    // Also check that flags were not altered
+    BOOST_CHECK_EQUAL(n3->second.GetFlags(), CCoinsCacheEntry::DIRTY);
+    BOOST_CHECK_EQUAL(sentinel.second.Next(), &(*n3));
+    BOOST_CHECK_EQUAL(n3->second.Next(), &(*n4));
+    BOOST_CHECK_EQUAL(n3->second.Prev(), &sentinel);
+
+    // Delete n4
+    // sentinel->n3->sentinel
+    nodes.erase(n4);
+    // Check that sentinel still points to n3, and n3 points to sentinel
+    // Also check that flags were not altered
+    BOOST_CHECK_EQUAL(n3->second.GetFlags(), CCoinsCacheEntry::DIRTY);
+    BOOST_CHECK_EQUAL(sentinel.second.Next(), &(*n3));
+    BOOST_CHECK_EQUAL(n3->second.Next(), &sentinel);
+    BOOST_CHECK_EQUAL(sentinel.second.Prev(), &(*n3));
+
+    // Delete n3
+    // sentinel->sentinel
+    nodes.erase(n3);
+    // Check that sentinel's next and prev are itself
+    BOOST_CHECK_EQUAL(sentinel.second.Next(), &sentinel);
+    BOOST_CHECK_EQUAL(sentinel.second.Prev(), &sentinel);
+}
+
+BOOST_AUTO_TEST_CASE(linked_list_add_flags)
+{
+    CoinsCachePair sentinel;
+    sentinel.second.SelfRef(sentinel);
+    CoinsCachePair n1;
+    CoinsCachePair n2;
+
+    // Check that adding 0 flag has no effect
+    n1.second.AddFlags(0, n1, sentinel);
+    BOOST_CHECK_EQUAL(n1.second.GetFlags(), 0);
+    BOOST_CHECK_EQUAL(sentinel.second.Next(), &sentinel);
+    BOOST_CHECK_EQUAL(sentinel.second.Prev(), &sentinel);
+
+    // Check that adding DIRTY flag inserts it into linked list and sets flags
+    n1.second.AddFlags(CCoinsCacheEntry::DIRTY, n1, sentinel);
+    BOOST_CHECK_EQUAL(n1.second.GetFlags(), CCoinsCacheEntry::DIRTY);
+    BOOST_CHECK_EQUAL(n1.second.Next(), &sentinel);
+    BOOST_CHECK_EQUAL(n1.second.Prev(), &sentinel);
+    BOOST_CHECK_EQUAL(sentinel.second.Next(), &n1);
+    BOOST_CHECK_EQUAL(sentinel.second.Prev(), &n1);
+
+    // Check that adding FRESH flag on new node inserts it after n1
+    n2.second.AddFlags(CCoinsCacheEntry::FRESH, n2, sentinel);
+    BOOST_CHECK_EQUAL(n2.second.GetFlags(), CCoinsCacheEntry::FRESH);
+    BOOST_CHECK_EQUAL(n2.second.Next(), &sentinel);
+    BOOST_CHECK_EQUAL(n2.second.Prev(), &n1);
+    BOOST_CHECK_EQUAL(n1.second.Next(), &n2);
+    BOOST_CHECK_EQUAL(sentinel.second.Prev(), &n2);
+
+    // Check that adding 0 flag has no effect, and doesn't change position
+    n1.second.AddFlags(0, n1, sentinel);
+    BOOST_CHECK_EQUAL(n1.second.GetFlags(), CCoinsCacheEntry::DIRTY);
+    BOOST_CHECK_EQUAL(n1.second.Next(), &n2);
+    BOOST_CHECK_EQUAL(n1.second.Prev(), &sentinel);
+    BOOST_CHECK_EQUAL(sentinel.second.Next(), &n1);
+    BOOST_CHECK_EQUAL(n2.second.Prev(), &n1);
+
+    // Check that we can add extra flags, but they don't change our position
+    n1.second.AddFlags(CCoinsCacheEntry::FRESH, n1, sentinel);
+    BOOST_CHECK_EQUAL(n1.second.GetFlags(), CCoinsCacheEntry::DIRTY | CCoinsCacheEntry::FRESH);
+    BOOST_CHECK_EQUAL(n1.second.Next(), &n2);
+    BOOST_CHECK_EQUAL(n1.second.Prev(), &sentinel);
+    BOOST_CHECK_EQUAL(sentinel.second.Next(), &n1);
+    BOOST_CHECK_EQUAL(n2.second.Prev(), &n1);
+
+    // Check that we can clear flags then re-add them
+    n1.second.ClearFlags();
+    BOOST_CHECK_EQUAL(n1.second.GetFlags(), 0);
+    BOOST_CHECK_EQUAL(sentinel.second.Next(), &n2);
+    BOOST_CHECK_EQUAL(sentinel.second.Prev(), &n2);
+    BOOST_CHECK_EQUAL(n2.second.Next(), &sentinel);
+    BOOST_CHECK_EQUAL(n2.second.Prev(), &sentinel);
+
+    // Check that calling `ClearFlags` with 0 flags has no effect
+    n1.second.ClearFlags();
+    BOOST_CHECK_EQUAL(n1.second.GetFlags(), 0);
+    BOOST_CHECK_EQUAL(sentinel.second.Next(), &n2);
+    BOOST_CHECK_EQUAL(sentinel.second.Prev(), &n2);
+    BOOST_CHECK_EQUAL(n2.second.Next(), &sentinel);
+    BOOST_CHECK_EQUAL(n2.second.Prev(), &sentinel);
+
+    // Adding 0 still has no effect
+    n1.second.AddFlags(0, n1, sentinel);
+    BOOST_CHECK_EQUAL(sentinel.second.Next(), &n2);
+    BOOST_CHECK_EQUAL(sentinel.second.Prev(), &n2);
+    BOOST_CHECK_EQUAL(n2.second.Next(), &sentinel);
+    BOOST_CHECK_EQUAL(n2.second.Prev(), &sentinel);
+
+    // But adding DIRTY re-inserts it after n2
+    n1.second.AddFlags(CCoinsCacheEntry::DIRTY, n1, sentinel);
+    BOOST_CHECK_EQUAL(n1.second.GetFlags(), CCoinsCacheEntry::DIRTY);
+    BOOST_CHECK_EQUAL(n2.second.Next(), &n1);
+    BOOST_CHECK_EQUAL(n1.second.Prev(), &n2);
+    BOOST_CHECK_EQUAL(n1.second.Next(), &sentinel);
+    BOOST_CHECK_EQUAL(sentinel.second.Prev(), &n1);
+}
+
+BOOST_AUTO_TEST_SUITE_END()