ceph/src/rocksdb/cache/lru_cache_test.cc

   1 //  Copyright (c) 2011-present, Facebook, Inc.  All rights reserved.
   2 //  This source code is licensed under the BSD-style license found in the
   3 //  LICENSE file in the root directory of this source tree. An additional grant
   4 //  of patent rights can be found in the PATENTS file in the same directory.
   5
   6 #include "cache/lru_cache.h"
   7
   8 #include <string>
   9 #include <vector>
  10 #include "util/testharness.h"
  11
  12 namespace rocksdb {
  13
  14 class LRUCacheTest : public testing::Test {
  15  public:
  16   LRUCacheTest() {}
  17   ~LRUCacheTest() {}
  18
  19   void NewCache(size_t capacity, double high_pri_pool_ratio = 0.0) {
  20     cache_.reset(new LRUCacheShard());
  21     cache_->SetCapacity(capacity);
  22     cache_->SetStrictCapacityLimit(false);
  23     cache_->SetHighPriorityPoolRatio(high_pri_pool_ratio);
  24   }
  25
  26   void Insert(const std::string& key,
  27               Cache::Priority priority = Cache::Priority::LOW) {
  28     cache_->Insert(key, 0 /*hash*/, nullptr /*value*/, 1 /*charge*/,
  29                    nullptr /*deleter*/, nullptr /*handle*/, priority);
  30   }
  31
  32   void Insert(char key, Cache::Priority priority = Cache::Priority::LOW) {
  33     Insert(std::string(1, key), priority);
  34   }
  35
  36   bool Lookup(const std::string& key) {
  37     auto handle = cache_->Lookup(key, 0 /*hash*/);
  38     if (handle) {
  39       cache_->Release(handle);
  40       return true;
  41     }
  42     return false;
  43   }
  44
  45   bool Lookup(char key) { return Lookup(std::string(1, key)); }
  46
  47   void Erase(const std::string& key) { cache_->Erase(key, 0 /*hash*/); }
  48
  49   void ValidateLRUList(std::vector<std::string> keys,
  50                        size_t num_high_pri_pool_keys = 0) {
  51     LRUHandle* lru;
  52     LRUHandle* lru_low_pri;
  53     cache_->TEST_GetLRUList(&lru, &lru_low_pri);
  54     LRUHandle* iter = lru;
  55     bool in_high_pri_pool = false;
  56     size_t high_pri_pool_keys = 0;
  57     if (iter == lru_low_pri) {
  58       in_high_pri_pool = true;
  59     }
  60     for (const auto& key : keys) {
  61       iter = iter->next;
  62       ASSERT_NE(lru, iter);
  63       ASSERT_EQ(key, iter->key().ToString());
  64       ASSERT_EQ(in_high_pri_pool, iter->InHighPriPool());
  65       if (in_high_pri_pool) {
  66         high_pri_pool_keys++;
  67       }
  68       if (iter == lru_low_pri) {
  69         ASSERT_FALSE(in_high_pri_pool);
  70         in_high_pri_pool = true;
  71       }
  72     }
  73     ASSERT_EQ(lru, iter->next);
  74     ASSERT_TRUE(in_high_pri_pool);
  75     ASSERT_EQ(num_high_pri_pool_keys, high_pri_pool_keys);
  76   }
  77
  78  private:
  79   std::unique_ptr<LRUCacheShard> cache_;
  80 };
  81
  82 TEST_F(LRUCacheTest, BasicLRU) {
  83   NewCache(5);
  84   for (char ch = 'a'; ch <= 'e'; ch++) {
  85     Insert(ch);
  86   }
  87   ValidateLRUList({"a", "b", "c", "d", "e"});
  88   for (char ch = 'x'; ch <= 'z'; ch++) {
  89     Insert(ch);
  90   }
  91   ValidateLRUList({"d", "e", "x", "y", "z"});
  92   ASSERT_FALSE(Lookup("b"));
  93   ValidateLRUList({"d", "e", "x", "y", "z"});
  94   ASSERT_TRUE(Lookup("e"));
  95   ValidateLRUList({"d", "x", "y", "z", "e"});
  96   ASSERT_TRUE(Lookup("z"));
  97   ValidateLRUList({"d", "x", "y", "e", "z"});
  98   Erase("x");
  99   ValidateLRUList({"d", "y", "e", "z"});
 100   ASSERT_TRUE(Lookup("d"));
 101   ValidateLRUList({"y", "e", "z", "d"});
 102   Insert("u");
 103   ValidateLRUList({"y", "e", "z", "d", "u"});
 104   Insert("v");
 105   ValidateLRUList({"e", "z", "d", "u", "v"});
 106 }
 107
 108 TEST_F(LRUCacheTest, MidPointInsertion) {
 109   // Allocate 2 cache entries to high-pri pool.
 110   NewCache(5, 0.45);
 111
 112   Insert("a", Cache::Priority::LOW);
 113   Insert("b", Cache::Priority::LOW);
 114   Insert("c", Cache::Priority::LOW);
 115   ValidateLRUList({"a", "b", "c"}, 0);
 116
 117   // Low-pri entries can take high-pri pool capacity if available
 118   Insert("u", Cache::Priority::LOW);
 119   Insert("v", Cache::Priority::LOW);
 120   ValidateLRUList({"a", "b", "c", "u", "v"}, 0);
 121
 122   Insert("X", Cache::Priority::HIGH);
 123   Insert("Y", Cache::Priority::HIGH);
 124   ValidateLRUList({"c", "u", "v", "X", "Y"}, 2);
 125
 126   // High-pri entries can overflow to low-pri pool.
 127   Insert("Z", Cache::Priority::HIGH);
 128   ValidateLRUList({"u", "v", "X", "Y", "Z"}, 2);
 129
 130   // Low-pri entries will be inserted to head of low-pri pool.
 131   Insert("a", Cache::Priority::LOW);
 132   ValidateLRUList({"v", "X", "a", "Y", "Z"}, 2);
 133
 134   // Low-pri entries will be inserted to head of low-pri pool after lookup.
 135   ASSERT_TRUE(Lookup("v"));
 136   ValidateLRUList({"X", "a", "v", "Y", "Z"}, 2);
 137
 138   // High-pri entries will be inserted to the head of the list after lookup.
 139   ASSERT_TRUE(Lookup("X"));
 140   ValidateLRUList({"a", "v", "Y", "Z", "X"}, 2);
 141   ASSERT_TRUE(Lookup("Z"));
 142   ValidateLRUList({"a", "v", "Y", "X", "Z"}, 2);
 143
 144   Erase("Y");
 145   ValidateLRUList({"a", "v", "X", "Z"}, 2);
 146   Erase("X");
 147   ValidateLRUList({"a", "v", "Z"}, 1);
 148   Insert("d", Cache::Priority::LOW);
 149   Insert("e", Cache::Priority::LOW);
 150   ValidateLRUList({"a", "v", "d", "e", "Z"}, 1);
 151   Insert("f", Cache::Priority::LOW);
 152   Insert("g", Cache::Priority::LOW);
 153   ValidateLRUList({"d", "e", "f", "g", "Z"}, 1);
 154   ASSERT_TRUE(Lookup("d"));
 155   ValidateLRUList({"e", "f", "g", "d", "Z"}, 1);
 156 }
 157
 158 }  // namespace rocksdb
 159
 160 int main(int argc, char** argv) {
 161   ::testing::InitGoogleTest(&argc, argv);
 162   return RUN_ALL_TESTS();
 163 }