1 //  Copyright (c) 2011-present, Facebook, Inc.  All rights reserved.
2 //  This source code is licensed under both the GPLv2 (found in the
3 //  COPYING file in the root directory) and Apache 2.0 License
4 //  (found in the LICENSE.Apache file in the root directory).
5 
6 #include "cache/lru_cache.h"
7 
8 #include <string>
9 #include <vector>
10 #include "port/port.h"
11 #include "test_util/testharness.h"
12 
13 namespace ROCKSDB_NAMESPACE {
14 
15 class LRUCacheTest : public testing::Test {
16  public:
LRUCacheTest()17   LRUCacheTest() {}
~LRUCacheTest()18   ~LRUCacheTest() override { DeleteCache(); }
19 
DeleteCache()20   void DeleteCache() {
21     if (cache_ != nullptr) {
22       cache_->~LRUCacheShard();
23       port::cacheline_aligned_free(cache_);
24       cache_ = nullptr;
25     }
26   }
27 
NewCache(size_t capacity,double high_pri_pool_ratio=0.0,bool use_adaptive_mutex=kDefaultToAdaptiveMutex)28   void NewCache(size_t capacity, double high_pri_pool_ratio = 0.0,
29                 bool use_adaptive_mutex = kDefaultToAdaptiveMutex) {
30     DeleteCache();
31     cache_ = reinterpret_cast<LRUCacheShard*>(
32         port::cacheline_aligned_alloc(sizeof(LRUCacheShard)));
33     new (cache_) LRUCacheShard(capacity, false /*strict_capcity_limit*/,
34                                high_pri_pool_ratio, use_adaptive_mutex,
35                                kDontChargeCacheMetadata);
36   }
37 
Insert(const std::string & key,Cache::Priority priority=Cache::Priority::LOW)38   void Insert(const std::string& key,
39               Cache::Priority priority = Cache::Priority::LOW) {
40     cache_->Insert(key, 0 /*hash*/, nullptr /*value*/, 1 /*charge*/,
41                    nullptr /*deleter*/, nullptr /*handle*/, priority);
42   }
43 
Insert(char key,Cache::Priority priority=Cache::Priority::LOW)44   void Insert(char key, Cache::Priority priority = Cache::Priority::LOW) {
45     Insert(std::string(1, key), priority);
46   }
47 
Lookup(const std::string & key)48   bool Lookup(const std::string& key) {
49     auto handle = cache_->Lookup(key, 0 /*hash*/);
50     if (handle) {
51       cache_->Release(handle);
52       return true;
53     }
54     return false;
55   }
56 
Lookup(char key)57   bool Lookup(char key) { return Lookup(std::string(1, key)); }
58 
Erase(const std::string & key)59   void Erase(const std::string& key) { cache_->Erase(key, 0 /*hash*/); }
60 
ValidateLRUList(std::vector<std::string> keys,size_t num_high_pri_pool_keys=0)61   void ValidateLRUList(std::vector<std::string> keys,
62                        size_t num_high_pri_pool_keys = 0) {
63     LRUHandle* lru;
64     LRUHandle* lru_low_pri;
65     cache_->TEST_GetLRUList(&lru, &lru_low_pri);
66     LRUHandle* iter = lru;
67     bool in_high_pri_pool = false;
68     size_t high_pri_pool_keys = 0;
69     if (iter == lru_low_pri) {
70       in_high_pri_pool = true;
71     }
72     for (const auto& key : keys) {
73       iter = iter->next;
74       ASSERT_NE(lru, iter);
75       ASSERT_EQ(key, iter->key().ToString());
76       ASSERT_EQ(in_high_pri_pool, iter->InHighPriPool());
77       if (in_high_pri_pool) {
78         high_pri_pool_keys++;
79       }
80       if (iter == lru_low_pri) {
81         ASSERT_FALSE(in_high_pri_pool);
82         in_high_pri_pool = true;
83       }
84     }
85     ASSERT_EQ(lru, iter->next);
86     ASSERT_TRUE(in_high_pri_pool);
87     ASSERT_EQ(num_high_pri_pool_keys, high_pri_pool_keys);
88   }
89 
90  private:
91   LRUCacheShard* cache_ = nullptr;
92 };
93 
TEST_F(LRUCacheTest,BasicLRU)94 TEST_F(LRUCacheTest, BasicLRU) {
95   NewCache(5);
96   for (char ch = 'a'; ch <= 'e'; ch++) {
97     Insert(ch);
98   }
99   ValidateLRUList({"a", "b", "c", "d", "e"});
100   for (char ch = 'x'; ch <= 'z'; ch++) {
101     Insert(ch);
102   }
103   ValidateLRUList({"d", "e", "x", "y", "z"});
104   ASSERT_FALSE(Lookup("b"));
105   ValidateLRUList({"d", "e", "x", "y", "z"});
106   ASSERT_TRUE(Lookup("e"));
107   ValidateLRUList({"d", "x", "y", "z", "e"});
108   ASSERT_TRUE(Lookup("z"));
109   ValidateLRUList({"d", "x", "y", "e", "z"});
110   Erase("x");
111   ValidateLRUList({"d", "y", "e", "z"});
112   ASSERT_TRUE(Lookup("d"));
113   ValidateLRUList({"y", "e", "z", "d"});
114   Insert("u");
115   ValidateLRUList({"y", "e", "z", "d", "u"});
116   Insert("v");
117   ValidateLRUList({"e", "z", "d", "u", "v"});
118 }
119 
TEST_F(LRUCacheTest,MidpointInsertion)120 TEST_F(LRUCacheTest, MidpointInsertion) {
121   // Allocate 2 cache entries to high-pri pool.
122   NewCache(5, 0.45);
123 
124   Insert("a", Cache::Priority::LOW);
125   Insert("b", Cache::Priority::LOW);
126   Insert("c", Cache::Priority::LOW);
127   Insert("x", Cache::Priority::HIGH);
128   Insert("y", Cache::Priority::HIGH);
129   ValidateLRUList({"a", "b", "c", "x", "y"}, 2);
130 
131   // Low-pri entries inserted to the tail of low-pri list (the midpoint).
132   // After lookup, it will move to the tail of the full list.
133   Insert("d", Cache::Priority::LOW);
134   ValidateLRUList({"b", "c", "d", "x", "y"}, 2);
135   ASSERT_TRUE(Lookup("d"));
136   ValidateLRUList({"b", "c", "x", "y", "d"}, 2);
137 
138   // High-pri entries will be inserted to the tail of full list.
139   Insert("z", Cache::Priority::HIGH);
140   ValidateLRUList({"c", "x", "y", "d", "z"}, 2);
141 }
142 
TEST_F(LRUCacheTest,EntriesWithPriority)143 TEST_F(LRUCacheTest, EntriesWithPriority) {
144   // Allocate 2 cache entries to high-pri pool.
145   NewCache(5, 0.45);
146 
147   Insert("a", Cache::Priority::LOW);
148   Insert("b", Cache::Priority::LOW);
149   Insert("c", Cache::Priority::LOW);
150   ValidateLRUList({"a", "b", "c"}, 0);
151 
152   // Low-pri entries can take high-pri pool capacity if available
153   Insert("u", Cache::Priority::LOW);
154   Insert("v", Cache::Priority::LOW);
155   ValidateLRUList({"a", "b", "c", "u", "v"}, 0);
156 
157   Insert("X", Cache::Priority::HIGH);
158   Insert("Y", Cache::Priority::HIGH);
159   ValidateLRUList({"c", "u", "v", "X", "Y"}, 2);
160 
161   // High-pri entries can overflow to low-pri pool.
162   Insert("Z", Cache::Priority::HIGH);
163   ValidateLRUList({"u", "v", "X", "Y", "Z"}, 2);
164 
165   // Low-pri entries will be inserted to head of low-pri pool.
166   Insert("a", Cache::Priority::LOW);
167   ValidateLRUList({"v", "X", "a", "Y", "Z"}, 2);
168 
169   // Low-pri entries will be inserted to head of high-pri pool after lookup.
170   ASSERT_TRUE(Lookup("v"));
171   ValidateLRUList({"X", "a", "Y", "Z", "v"}, 2);
172 
173   // High-pri entries will be inserted to the head of the list after lookup.
174   ASSERT_TRUE(Lookup("X"));
175   ValidateLRUList({"a", "Y", "Z", "v", "X"}, 2);
176   ASSERT_TRUE(Lookup("Z"));
177   ValidateLRUList({"a", "Y", "v", "X", "Z"}, 2);
178 
179   Erase("Y");
180   ValidateLRUList({"a", "v", "X", "Z"}, 2);
181   Erase("X");
182   ValidateLRUList({"a", "v", "Z"}, 1);
183   Insert("d", Cache::Priority::LOW);
184   Insert("e", Cache::Priority::LOW);
185   ValidateLRUList({"a", "v", "d", "e", "Z"}, 1);
186   Insert("f", Cache::Priority::LOW);
187   Insert("g", Cache::Priority::LOW);
188   ValidateLRUList({"d", "e", "f", "g", "Z"}, 1);
189   ASSERT_TRUE(Lookup("d"));
190   ValidateLRUList({"e", "f", "g", "Z", "d"}, 2);
191 }
192 
193 }  // namespace ROCKSDB_NAMESPACE
194 
main(int argc,char ** argv)195 int main(int argc, char** argv) {
196   ::testing::InitGoogleTest(&argc, argv);
197   return RUN_ALL_TESTS();
198 }
199