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