Change TCacheCache to return safe page lists

8 files changed, 124 insertions, 58 deletions

diff --git a/ydb/core/tablet_flat/shared_sausagecache.cpp b/ydb/core/tablet_flat/shared_sausagecache.cpp
index f168297644e..c0cb5e7987a 100644
--- a/ydb/core/tablet_flat/shared_sausagecache.cpp
+++ b/ydb/core/tablet_flat/shared_sausagecache.cpp
@@ -930,11 +930,9 @@ class TSharedPageCache : public TActor<TSharedPageCache> {
         }
     }
 
-    void Evict(TPage *pages) {
-        if (pages == nullptr)
-            return;
-        TPage *page = pages;
-        for (;;) {
+    void Evict(TIntrusiveList<TPage>&& pages) {
+        while (!pages.Empty()) {
+            TPage* page = pages.PopFront();
             Y_VERIFY(page->CacheGeneration == TCacheCacheConfig::CacheGenEvicted);
             page->CacheGeneration = TCacheCacheConfig::CacheGenNone;
 
@@ -962,16 +960,6 @@ class TSharedPageCache : public TActor<TSharedPageCache> {
             default:
                 Y_FAIL("unknown load state");
             }
-
-            TPage *next = page->Next()->Node();
-            if (page != next) {
-                page->Unlink();
-            }
-
-            if (page == next)
-                break;
-
-            page = next;
         }
     }
 
diff --git a/ydb/core/util/cache_cache.h b/ydb/core/util/cache_cache.h
index 939b438f196..d94d281b42b 100644
--- a/ydb/core/util/cache_cache.h
+++ b/ydb/core/util/cache_cache.h
@@ -81,47 +81,50 @@ public:
     {}
 
     // returns evicted elements as list
-    TItem* EnsureLimits() {
-        TItem *ret = nullptr;
-        ret = LimitFresh(ret);
-        ret = LimitWarm(ret);
-        ret = LimitStaging(ret);
+    TIntrusiveList<TItem> EnsureLimits() {
+        TIntrusiveList<TItem> evictedList;
+        LimitFresh(evictedList);
+        LimitWarm(evictedList);
+        LimitStaging(evictedList);
 
-        if (ret) {
-            if (Config.ReportedFresh)
-                *Config.ReportedFresh = FreshWeight;
-            if (Config.ReportedWarm)
-                *Config.ReportedWarm = WarmWeight;
-            if (Config.ReportedStaging)
-                *Config.ReportedStaging = StagingWeight;
-        }
+        // Note: levels may be rearranged even if nothing was evicted
+        if (Config.ReportedFresh)
+            *Config.ReportedFresh = FreshWeight;
+        if (Config.ReportedWarm)
+            *Config.ReportedWarm = WarmWeight;
+        if (Config.ReportedStaging)
+            *Config.ReportedStaging = StagingWeight;
 
-        return ret;
+        return evictedList;
     }
 
     // returns evicted elements as list
-    TItem* Touch(TItem *item) {
+    TIntrusiveList<TItem> Touch(TItem *item) {
+        TIntrusiveList<TItem> evictedList;
         TIntrusiveListItem<TItem> *xitem = item;
 
         const TCacheCacheConfig::ECacheGeneration cacheGen = GenerationOp.Get(item);
         switch (cacheGen) {
         case TCacheCacheConfig::CacheGenNone: // place in fresh
         case TCacheCacheConfig::CacheGenEvicted: // corner case: was evicted from staging and touched in same update
-            return AddToFresh(item);
+            AddToFresh(item, evictedList);
         case TCacheCacheConfig::CacheGenFresh: // just update inside fresh
             xitem->Unlink();
             FreshList.PushFront(xitem);
-            return nullptr;
+            break;
         case TCacheCacheConfig::CacheGenStaging: // move to warm
-            return MoveToWarm(item);
+            MoveToWarm(item, evictedList);
+            break;
         case TCacheCacheConfig::CacheGenWarm: // just update inside warm
             xitem->Unlink();
             WarmList.PushFront(xitem);
-            return nullptr;
+            break;
         default:
             Y_VERIFY_DEBUG(false, "unknown/broken cache generation");
-            return nullptr;
+            break;
         }
+
+        return evictedList;
     }
 
     // evict and erase differs on Evicted handling
@@ -186,6 +189,7 @@ public:
 
         Config.SetLimit(cacheSize);
     }
+
 private:
     void Unlink(TItem *item, ui64 &weight) {
         item->Unlink();
@@ -195,8 +199,8 @@ private:
         weight -= elementWeight;
     }
 
-    TItem* AddToFresh(TItem *item) {
-        TItem *ret = LimitFresh(nullptr);
+    void AddToFresh(TItem *item, TIntrusiveList<TItem>& evictedList) {
+        LimitFresh(evictedList);
         item->Unlink();
         FreshWeight += WeightOp.Get(item);
         FreshList.PushFront(item);
@@ -206,13 +210,12 @@ private:
             *Config.ReportedStaging = StagingWeight;
         if (Config.ReportedFresh)
             *Config.ReportedFresh = FreshWeight;
-
-        return ret;
     }
 
-    TItem* MoveToWarm(TItem *item) {
-        TItem *ret = LimitWarm(nullptr);
+    void MoveToWarm(TItem *item, TIntrusiveList<TItem>& evictedList) {
+        // Note: unlink first, so item is not evicted by LimitWarm call below
         Unlink(item, StagingWeight);
+        LimitWarm(evictedList);
         WarmWeight += WeightOp.Get(item);
         WarmList.PushFront(item);
         GenerationOp.Set(item, TCacheCacheConfig::CacheGenWarm);
@@ -221,53 +224,44 @@ private:
             *Config.ReportedStaging = StagingWeight;
         if (Config.ReportedWarm)
             *Config.ReportedWarm = WarmWeight;
-
-        return ret;
     }
 
-    TItem* AddToStaging(TItem *item, TItem *ret) {
-        ret = LimitStaging(ret);
+    void AddToStaging(TItem *item, TIntrusiveList<TItem>& evictedList) {
+        LimitStaging(evictedList);
         StagingWeight += WeightOp.Get(item);
         StagingList.PushFront(item);
         GenerationOp.Set(item, TCacheCacheConfig::CacheGenStaging);
-        return ret;
     }
 
-    TItem* LimitFresh(TItem *ret) {
+    void LimitFresh(TIntrusiveList<TItem>& evictedList) {
         while (FreshWeight > Config.FreshLimit) {
             Y_VERIFY_DEBUG(!FreshList.Empty());
             TItem *x = FreshList.PopBack();
             Y_VERIFY(GenerationOp.Get(x) == TCacheCacheConfig::CacheGenFresh, "malformed entry in fresh cache. %" PRIu32, (ui32)GenerationOp.Get(x));
             Unlink(x, FreshWeight);
-            ret = AddToStaging(x, ret);
+            AddToStaging(x, evictedList);
         }
-        return ret;
     }
 
-    TItem* LimitWarm(TItem *ret) {
+    void LimitWarm(TIntrusiveList<TItem>& evictedList) {
         while (WarmWeight > Config.WarmLimit) {
             Y_VERIFY_DEBUG(!WarmList.Empty());
             TItem *x = WarmList.PopBack();
             Y_VERIFY(GenerationOp.Get(x) == TCacheCacheConfig::CacheGenWarm, "malformed entry in warm cache. %" PRIu32, (ui32)GenerationOp.Get(x));
             Unlink(x, WarmWeight);
-            ret = AddToStaging(x, ret);
+            AddToStaging(x, evictedList);
         }
-        return ret;
     }
 
-    TItem* LimitStaging(TItem *ret) {
+    void LimitStaging(TIntrusiveList<TItem>& evictedList) {
         while (StagingWeight > Config.StagingLimit) {
             Y_VERIFY_DEBUG(!StagingList.Empty());
             TItem *evicted = StagingList.PopBack();
             Y_VERIFY(GenerationOp.Get(evicted) == TCacheCacheConfig::CacheGenStaging, "malformed entry in staging cache %" PRIu32, (ui32)GenerationOp.Get(evicted));
             Unlink(evicted, StagingWeight);
             GenerationOp.Set(evicted, TCacheCacheConfig::CacheGenEvicted);
-            if (ret == nullptr)
-                ret = evicted;
-            else
-                evicted->LinkBefore(ret);
+            evictedList.PushBack(evicted);
         }
-        return ret;
     }
 
 private:
diff --git a/ydb/core/util/cache_cache_ut.cpp b/ydb/core/util/cache_cache_ut.cpp
new file mode 100644
index 00000000000..4efd16bc5b3
--- /dev/null
+++ b/ydb/core/util/cache_cache_ut.cpp
@@ -0,0 +1,79 @@
+#include "cache_cache.h"
+#include <library/cpp/testing/unittest/registar.h>
+
+namespace NKikimr {
+
+Y_UNIT_TEST_SUITE(TCacheCacheTest) {
+
+    struct TPage : public TIntrusiveListItem<TPage> {
+        TCacheCacheConfig::ECacheGeneration CacheGeneration = TCacheCacheConfig::CacheGenNone;
+    };
+
+    Y_UNIT_TEST(MoveToWarm) {
+        TCacheCacheConfig::TCounterPtr fresh = new NMonitoring::TCounterForPtr;
+        TCacheCacheConfig::TCounterPtr staging = new NMonitoring::TCounterForPtr;
+        TCacheCacheConfig::TCounterPtr warm = new NMonitoring::TCounterForPtr;
+        // use limit 1 which translates to limit 0 at each level
+        // this should mean nothing is cacheable, but currently we will
+        // place 1 page on a level until it is inspected again.
+        TCacheCacheConfig config(1, fresh, staging, warm);
+        TCacheCache<TPage> cache(config);
+
+        TVector<TPage> pages(3);
+        TIntrusiveList<TPage> evicted;
+
+        // page 0 added to fresh
+        evicted = cache.Touch(&pages[0]);
+        UNIT_ASSERT(pages[0].CacheGeneration == TCacheCacheConfig::CacheGenFresh);
+        UNIT_ASSERT_VALUES_EQUAL(fresh->Val(), 1ULL);
+        UNIT_ASSERT_VALUES_EQUAL(staging->Val(), 0ULL);
+        UNIT_ASSERT_VALUES_EQUAL(warm->Val(), 0ULL);
+        UNIT_ASSERT(evicted.Empty());
+
+        // page 1 added to fresh first bumps page 0 to staging 
+        evicted = cache.Touch(&pages[1]);
+        UNIT_ASSERT(pages[1].CacheGeneration == TCacheCacheConfig::CacheGenFresh);
+        UNIT_ASSERT(pages[0].CacheGeneration == TCacheCacheConfig::CacheGenStaging);
+        UNIT_ASSERT_VALUES_EQUAL(fresh->Val(), 1ULL);
+        UNIT_ASSERT_VALUES_EQUAL(staging->Val(), 1ULL);
+        UNIT_ASSERT_VALUES_EQUAL(warm->Val(), 0ULL);
+        UNIT_ASSERT(evicted.Empty());
+
+        // page 0 is moved to warm from staging
+        evicted = cache.Touch(&pages[0]);
+        UNIT_ASSERT(pages[0].CacheGeneration == TCacheCacheConfig::CacheGenWarm);
+        UNIT_ASSERT_VALUES_EQUAL(fresh->Val(), 1ULL);
+        UNIT_ASSERT_VALUES_EQUAL(staging->Val(), 0ULL);
+        UNIT_ASSERT_VALUES_EQUAL(warm->Val(), 1ULL);
+        UNIT_ASSERT(evicted.Empty());
+
+        // page 2 added to fresh first bumps page 1 to staging
+        evicted = cache.Touch(&pages[2]);
+        UNIT_ASSERT(pages[2].CacheGeneration == TCacheCacheConfig::CacheGenFresh);
+        UNIT_ASSERT(pages[1].CacheGeneration == TCacheCacheConfig::CacheGenStaging);
+        UNIT_ASSERT_VALUES_EQUAL(fresh->Val(), 1ULL);
+        UNIT_ASSERT_VALUES_EQUAL(staging->Val(), 1ULL);
+        UNIT_ASSERT_VALUES_EQUAL(warm->Val(), 1ULL);
+        UNIT_ASSERT(evicted.Empty());
+
+        // page 1 moves to warm, but first it bumps page 0 to staging
+        evicted = cache.Touch(&pages[1]);
+        UNIT_ASSERT(pages[1].CacheGeneration == TCacheCacheConfig::CacheGenWarm);
+        UNIT_ASSERT(pages[0].CacheGeneration == TCacheCacheConfig::CacheGenStaging);
+        UNIT_ASSERT_VALUES_EQUAL(fresh->Val(), 1ULL);
+        UNIT_ASSERT_VALUES_EQUAL(staging->Val(), 1ULL);
+        UNIT_ASSERT_VALUES_EQUAL(warm->Val(), 1ULL);
+        UNIT_ASSERT(evicted.Empty());
+
+        // note: cache eviction is unintuitive at the moment
+        // all levels are above their limits so EnsureLimits will evict everything
+        evicted = cache.EnsureLimits();
+        UNIT_ASSERT(!evicted.Empty());
+        UNIT_ASSERT(pages[0].CacheGeneration == TCacheCacheConfig::CacheGenEvicted);
+        UNIT_ASSERT(pages[1].CacheGeneration == TCacheCacheConfig::CacheGenEvicted);
+        UNIT_ASSERT(pages[2].CacheGeneration == TCacheCacheConfig::CacheGenEvicted);
+    }
+
+}
+
+} // namespace NKikimr
diff --git a/ydb/core/util/ut/CMakeLists.darwin-x86_64.txt b/ydb/core/util/ut/CMakeLists.darwin-x86_64.txt
index 1356cf5497c..cad749140e3 100644
--- a/ydb/core/util/ut/CMakeLists.darwin-x86_64.txt
+++ b/ydb/core/util/ut/CMakeLists.darwin-x86_64.txt
@@ -33,6 +33,7 @@ target_sources(ydb-core-util-ut PRIVATE
   ${CMAKE_SOURCE_DIR}/ydb/core/util/bits_ut.cpp
   ${CMAKE_SOURCE_DIR}/ydb/core/util/btree_cow_ut.cpp
   ${CMAKE_SOURCE_DIR}/ydb/core/util/btree_ut.cpp
+  ${CMAKE_SOURCE_DIR}/ydb/core/util/cache_cache_ut.cpp
   ${CMAKE_SOURCE_DIR}/ydb/core/util/cache_ut.cpp
   ${CMAKE_SOURCE_DIR}/ydb/core/util/circular_queue_ut.cpp
   ${CMAKE_SOURCE_DIR}/ydb/core/util/concurrent_rw_hash_ut.cpp
diff --git a/ydb/core/util/ut/CMakeLists.linux-aarch64.txt b/ydb/core/util/ut/CMakeLists.linux-aarch64.txt
index ac5e35a9043..e24aac4b9bf 100644
--- a/ydb/core/util/ut/CMakeLists.linux-aarch64.txt
+++ b/ydb/core/util/ut/CMakeLists.linux-aarch64.txt
@@ -36,6 +36,7 @@ target_sources(ydb-core-util-ut PRIVATE
   ${CMAKE_SOURCE_DIR}/ydb/core/util/bits_ut.cpp
   ${CMAKE_SOURCE_DIR}/ydb/core/util/btree_cow_ut.cpp
   ${CMAKE_SOURCE_DIR}/ydb/core/util/btree_ut.cpp
+  ${CMAKE_SOURCE_DIR}/ydb/core/util/cache_cache_ut.cpp
   ${CMAKE_SOURCE_DIR}/ydb/core/util/cache_ut.cpp
   ${CMAKE_SOURCE_DIR}/ydb/core/util/circular_queue_ut.cpp
   ${CMAKE_SOURCE_DIR}/ydb/core/util/concurrent_rw_hash_ut.cpp
diff --git a/ydb/core/util/ut/CMakeLists.linux-x86_64.txt b/ydb/core/util/ut/CMakeLists.linux-x86_64.txt
index 79ab4968846..337a2f3d14a 100644
--- a/ydb/core/util/ut/CMakeLists.linux-x86_64.txt
+++ b/ydb/core/util/ut/CMakeLists.linux-x86_64.txt
@@ -37,6 +37,7 @@ target_sources(ydb-core-util-ut PRIVATE
   ${CMAKE_SOURCE_DIR}/ydb/core/util/bits_ut.cpp
   ${CMAKE_SOURCE_DIR}/ydb/core/util/btree_cow_ut.cpp
   ${CMAKE_SOURCE_DIR}/ydb/core/util/btree_ut.cpp
+  ${CMAKE_SOURCE_DIR}/ydb/core/util/cache_cache_ut.cpp
   ${CMAKE_SOURCE_DIR}/ydb/core/util/cache_ut.cpp
   ${CMAKE_SOURCE_DIR}/ydb/core/util/circular_queue_ut.cpp
   ${CMAKE_SOURCE_DIR}/ydb/core/util/concurrent_rw_hash_ut.cpp
diff --git a/ydb/core/util/ut/CMakeLists.windows-x86_64.txt b/ydb/core/util/ut/CMakeLists.windows-x86_64.txt
index 68bfb701a3f..ee0656544c1 100644
--- a/ydb/core/util/ut/CMakeLists.windows-x86_64.txt
+++ b/ydb/core/util/ut/CMakeLists.windows-x86_64.txt
@@ -26,6 +26,7 @@ target_sources(ydb-core-util-ut PRIVATE
   ${CMAKE_SOURCE_DIR}/ydb/core/util/bits_ut.cpp
   ${CMAKE_SOURCE_DIR}/ydb/core/util/btree_cow_ut.cpp
   ${CMAKE_SOURCE_DIR}/ydb/core/util/btree_ut.cpp
+  ${CMAKE_SOURCE_DIR}/ydb/core/util/cache_cache_ut.cpp
   ${CMAKE_SOURCE_DIR}/ydb/core/util/cache_ut.cpp
   ${CMAKE_SOURCE_DIR}/ydb/core/util/circular_queue_ut.cpp
   ${CMAKE_SOURCE_DIR}/ydb/core/util/concurrent_rw_hash_ut.cpp
diff --git a/ydb/core/util/ut/ya.make b/ydb/core/util/ut/ya.make
index f8a9e217d38..9cc0d62ce87 100644
--- a/ydb/core/util/ut/ya.make
+++ b/ydb/core/util/ut/ya.make
@@ -22,6 +22,7 @@ SRCS(
     bits_ut.cpp
     btree_cow_ut.cpp
     btree_ut.cpp
+    cache_cache_ut.cpp
     cache_ut.cpp
     circular_queue_ut.cpp
     concurrent_rw_hash_ut.cpp