1 | // Copyright (c) 2011 The LevelDB Authors. All rights reserved. |
2 | // Use of this source code is governed by a BSD-style license that can be |
3 | // found in the LICENSE file. See the AUTHORS file for names of contributors. |
4 | |
5 | #include "leveldb/cache.h" |
6 | |
7 | #include <vector> |
8 | |
9 | #include "gtest/gtest.h" |
10 | #include "util/coding.h" |
11 | |
12 | namespace leveldb { |
13 | |
14 | // Conversions between numeric keys/values and the types expected by Cache. |
15 | static std::string EncodeKey(int k) { |
16 | std::string result; |
17 | PutFixed32(&result, k); |
18 | return result; |
19 | } |
20 | static int DecodeKey(const Slice& k) { |
21 | assert(k.size() == 4); |
22 | return DecodeFixed32(k.data()); |
23 | } |
24 | static void* EncodeValue(uintptr_t v) { return reinterpret_cast<void*>(v); } |
25 | static int DecodeValue(void* v) { return reinterpret_cast<uintptr_t>(v); } |
26 | |
27 | class CacheTest : public testing::Test { |
28 | public: |
29 | static void Deleter(const Slice& key, void* v) { |
30 | current_->deleted_keys_.push_back(DecodeKey(key)); |
31 | current_->deleted_values_.push_back(DecodeValue(v)); |
32 | } |
33 | |
34 | static constexpr int kCacheSize = 1000; |
35 | std::vector<int> deleted_keys_; |
36 | std::vector<int> deleted_values_; |
37 | Cache* cache_; |
38 | |
39 | CacheTest() : cache_(NewLRUCache(kCacheSize)) { current_ = this; } |
40 | |
41 | ~CacheTest() { delete cache_; } |
42 | |
43 | int Lookup(int key) { |
44 | Cache::Handle* handle = cache_->Lookup(EncodeKey(key)); |
45 | const int r = (handle == nullptr) ? -1 : DecodeValue(cache_->Value(handle)); |
46 | if (handle != nullptr) { |
47 | cache_->Release(handle); |
48 | } |
49 | return r; |
50 | } |
51 | |
52 | void Insert(int key, int value, int charge = 1) { |
53 | cache_->Release(cache_->Insert(EncodeKey(key), EncodeValue(value), charge, |
54 | &CacheTest::Deleter)); |
55 | } |
56 | |
57 | Cache::Handle* InsertAndReturnHandle(int key, int value, int charge = 1) { |
58 | return cache_->Insert(EncodeKey(key), EncodeValue(value), charge, |
59 | &CacheTest::Deleter); |
60 | } |
61 | |
62 | void Erase(int key) { cache_->Erase(EncodeKey(key)); } |
63 | static CacheTest* current_; |
64 | }; |
65 | CacheTest* CacheTest::current_; |
66 | |
67 | TEST_F(CacheTest, HitAndMiss) { |
68 | ASSERT_EQ(-1, Lookup(100)); |
69 | |
70 | Insert(100, 101); |
71 | ASSERT_EQ(101, Lookup(100)); |
72 | ASSERT_EQ(-1, Lookup(200)); |
73 | ASSERT_EQ(-1, Lookup(300)); |
74 | |
75 | Insert(200, 201); |
76 | ASSERT_EQ(101, Lookup(100)); |
77 | ASSERT_EQ(201, Lookup(200)); |
78 | ASSERT_EQ(-1, Lookup(300)); |
79 | |
80 | Insert(100, 102); |
81 | ASSERT_EQ(102, Lookup(100)); |
82 | ASSERT_EQ(201, Lookup(200)); |
83 | ASSERT_EQ(-1, Lookup(300)); |
84 | |
85 | ASSERT_EQ(1, deleted_keys_.size()); |
86 | ASSERT_EQ(100, deleted_keys_[0]); |
87 | ASSERT_EQ(101, deleted_values_[0]); |
88 | } |
89 | |
90 | TEST_F(CacheTest, Erase) { |
91 | Erase(200); |
92 | ASSERT_EQ(0, deleted_keys_.size()); |
93 | |
94 | Insert(100, 101); |
95 | Insert(200, 201); |
96 | Erase(100); |
97 | ASSERT_EQ(-1, Lookup(100)); |
98 | ASSERT_EQ(201, Lookup(200)); |
99 | ASSERT_EQ(1, deleted_keys_.size()); |
100 | ASSERT_EQ(100, deleted_keys_[0]); |
101 | ASSERT_EQ(101, deleted_values_[0]); |
102 | |
103 | Erase(100); |
104 | ASSERT_EQ(-1, Lookup(100)); |
105 | ASSERT_EQ(201, Lookup(200)); |
106 | ASSERT_EQ(1, deleted_keys_.size()); |
107 | } |
108 | |
109 | TEST_F(CacheTest, EntriesArePinned) { |
110 | Insert(100, 101); |
111 | Cache::Handle* h1 = cache_->Lookup(EncodeKey(100)); |
112 | ASSERT_EQ(101, DecodeValue(cache_->Value(h1))); |
113 | |
114 | Insert(100, 102); |
115 | Cache::Handle* h2 = cache_->Lookup(EncodeKey(100)); |
116 | ASSERT_EQ(102, DecodeValue(cache_->Value(h2))); |
117 | ASSERT_EQ(0, deleted_keys_.size()); |
118 | |
119 | cache_->Release(h1); |
120 | ASSERT_EQ(1, deleted_keys_.size()); |
121 | ASSERT_EQ(100, deleted_keys_[0]); |
122 | ASSERT_EQ(101, deleted_values_[0]); |
123 | |
124 | Erase(100); |
125 | ASSERT_EQ(-1, Lookup(100)); |
126 | ASSERT_EQ(1, deleted_keys_.size()); |
127 | |
128 | cache_->Release(h2); |
129 | ASSERT_EQ(2, deleted_keys_.size()); |
130 | ASSERT_EQ(100, deleted_keys_[1]); |
131 | ASSERT_EQ(102, deleted_values_[1]); |
132 | } |
133 | |
134 | TEST_F(CacheTest, EvictionPolicy) { |
135 | Insert(100, 101); |
136 | Insert(200, 201); |
137 | Insert(300, 301); |
138 | Cache::Handle* h = cache_->Lookup(EncodeKey(300)); |
139 | |
140 | // Frequently used entry must be kept around, |
141 | // as must things that are still in use. |
142 | for (int i = 0; i < kCacheSize + 100; i++) { |
143 | Insert(1000 + i, 2000 + i); |
144 | ASSERT_EQ(2000 + i, Lookup(1000 + i)); |
145 | ASSERT_EQ(101, Lookup(100)); |
146 | } |
147 | ASSERT_EQ(101, Lookup(100)); |
148 | ASSERT_EQ(-1, Lookup(200)); |
149 | ASSERT_EQ(301, Lookup(300)); |
150 | cache_->Release(h); |
151 | } |
152 | |
153 | TEST_F(CacheTest, UseExceedsCacheSize) { |
154 | // Overfill the cache, keeping handles on all inserted entries. |
155 | std::vector<Cache::Handle*> h; |
156 | for (int i = 0; i < kCacheSize + 100; i++) { |
157 | h.push_back(InsertAndReturnHandle(1000 + i, 2000 + i)); |
158 | } |
159 | |
160 | // Check that all the entries can be found in the cache. |
161 | for (int i = 0; i < h.size(); i++) { |
162 | ASSERT_EQ(2000 + i, Lookup(1000 + i)); |
163 | } |
164 | |
165 | for (int i = 0; i < h.size(); i++) { |
166 | cache_->Release(h[i]); |
167 | } |
168 | } |
169 | |
170 | TEST_F(CacheTest, HeavyEntries) { |
171 | // Add a bunch of light and heavy entries and then count the combined |
172 | // size of items still in the cache, which must be approximately the |
173 | // same as the total capacity. |
174 | const int kLight = 1; |
175 | const int kHeavy = 10; |
176 | int added = 0; |
177 | int index = 0; |
178 | while (added < 2 * kCacheSize) { |
179 | const int weight = (index & 1) ? kLight : kHeavy; |
180 | Insert(index, 1000 + index, weight); |
181 | added += weight; |
182 | index++; |
183 | } |
184 | |
185 | int cached_weight = 0; |
186 | for (int i = 0; i < index; i++) { |
187 | const int weight = (i & 1 ? kLight : kHeavy); |
188 | int r = Lookup(i); |
189 | if (r >= 0) { |
190 | cached_weight += weight; |
191 | ASSERT_EQ(1000 + i, r); |
192 | } |
193 | } |
194 | ASSERT_LE(cached_weight, kCacheSize + kCacheSize / 10); |
195 | } |
196 | |
197 | TEST_F(CacheTest, NewId) { |
198 | uint64_t a = cache_->NewId(); |
199 | uint64_t b = cache_->NewId(); |
200 | ASSERT_NE(a, b); |
201 | } |
202 | |
203 | TEST_F(CacheTest, Prune) { |
204 | Insert(1, 100); |
205 | Insert(2, 200); |
206 | |
207 | Cache::Handle* handle = cache_->Lookup(EncodeKey(1)); |
208 | ASSERT_TRUE(handle); |
209 | cache_->Prune(); |
210 | cache_->Release(handle); |
211 | |
212 | ASSERT_EQ(100, Lookup(1)); |
213 | ASSERT_EQ(-1, Lookup(2)); |
214 | } |
215 | |
216 | TEST_F(CacheTest, ZeroSizeCache) { |
217 | delete cache_; |
218 | cache_ = NewLRUCache(0); |
219 | |
220 | Insert(1, 100); |
221 | ASSERT_EQ(-1, Lookup(1)); |
222 | } |
223 | |
224 | } // namespace leveldb |
225 | |