Google Git
Sign in
chromium / chromium / src / lkgr / . / net / base / expiring_cache_unittest.cc
blob: 06bb0f0f9cde9709a893e42a4f3f4c5712d98b4e [file] [log] [blame]
Avi Drissman64595482022-09-14 20:52:29[diff] [blame]1// Copyright 2012 The Chromium Authors
[email protected]2e9a06e2012-02-24 08:40:31[diff] [blame]2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "net/base/expiring_cache.h"
6
[email protected]94bf72f2012-06-19 19:37:28[diff] [blame]7#include <functional>
8#include <string>
9
Lei Zhangde197672021-04-29 08:11:24[diff] [blame]10#include "base/containers/contains.h"
[email protected]4b355212013-06-11 10:35:19[diff] [blame]11#include "base/strings/stringprintf.h"
[email protected]9da992db2013-06-28 05:40:47[diff] [blame]12#include "base/time/time.h"
[email protected]2e9a06e2012-02-24 08:40:31[diff] [blame]13#include "testing/gmock/include/gmock/gmock.h"
14#include "testing/gtest/include/gtest/gtest.h"
15
16using testing::Pointee;
17using testing::StrEq;
18
19namespace net {
20
21namespace {
22
23const int kMaxCacheEntries = 10;
Tsuyoshi Horo7bc2baa2022-06-29 09:48:02[diff] [blame]24typedef ExpiringCache<std::string, std::string, base::TimeTicks, std::less<>>
25 Cache;
[email protected]94bf72f2012-06-19 19:37:28[diff] [blame]26
27struct TestFunctor {
28 bool operator()(const std::string& now,
29 const std::string& expiration) const {
30 return now != expiration;
31 }
32};
[email protected]2e9a06e2012-02-24 08:40:31[diff] [blame]33
34} // namespace
35
36TEST(ExpiringCacheTest, Basic) {
Peter Kastinge5a38ed2021-10-02 03:06:35[diff] [blame]37 const base::TimeDelta kTTL = base::Seconds(10);
[email protected]2e9a06e2012-02-24 08:40:31[diff] [blame]38
39 Cache cache(kMaxCacheEntries);
40
41 // Start at t=0.
42 base::TimeTicks now;
43 EXPECT_EQ(0U, cache.size());
44
45 // Add an entry at t=0
46 EXPECT_FALSE(cache.Get("entry1", now));
[email protected]94bf72f2012-06-19 19:37:28[diff] [blame]47 cache.Put("entry1", "test1", now, now + kTTL);
[email protected]2e9a06e2012-02-24 08:40:31[diff] [blame]48 EXPECT_THAT(cache.Get("entry1", now), Pointee(StrEq("test1")));
49 EXPECT_EQ(1U, cache.size());
50
51 // Advance to t=5.
Peter Kastinge5a38ed2021-10-02 03:06:35[diff] [blame]52 now += base::Seconds(5);
[email protected]2e9a06e2012-02-24 08:40:31[diff] [blame]53
54 // Add an entry at t=5.
55 EXPECT_FALSE(cache.Get("entry2", now));
[email protected]94bf72f2012-06-19 19:37:28[diff] [blame]56 cache.Put("entry2", "test2", now, now + kTTL);
[email protected]2e9a06e2012-02-24 08:40:31[diff] [blame]57 EXPECT_THAT(cache.Get("entry2", now), Pointee(StrEq("test2")));
58 EXPECT_EQ(2U, cache.size());
59
60 // Advance to t=9.
Peter Kastinge5a38ed2021-10-02 03:06:35[diff] [blame]61 now += base::Seconds(4);
[email protected]2e9a06e2012-02-24 08:40:31[diff] [blame]62
63 // Verify that the entries added are still retrievable and usable.
64 EXPECT_THAT(cache.Get("entry1", now), Pointee(StrEq("test1")));
65 EXPECT_THAT(cache.Get("entry2", now), Pointee(StrEq("test2")));
66
67 // Advance to t=10; entry1 is now expired.
Peter Kastinge5a38ed2021-10-02 03:06:35[diff] [blame]68 now += base::Seconds(1);
[email protected]2e9a06e2012-02-24 08:40:31[diff] [blame]69
70 EXPECT_FALSE(cache.Get("entry1", now));
71 EXPECT_THAT(cache.Get("entry2", now), Pointee(StrEq("test2")));
72
73 // The expired element should no longer be in the cache.
74 EXPECT_EQ(1U, cache.size());
75
76 // Update entry1 so it is no longer expired.
[email protected]94bf72f2012-06-19 19:37:28[diff] [blame]77 cache.Put("entry1", "test1", now, now + kTTL);
[email protected]2e9a06e2012-02-24 08:40:31[diff] [blame]78
79 // Both entries should be retrievable and usable.
80 EXPECT_EQ(2U, cache.size());
81 EXPECT_THAT(cache.Get("entry1", now), Pointee(StrEq("test1")));
82 EXPECT_THAT(cache.Get("entry2", now), Pointee(StrEq("test2")));
83
84 // Advance to t=20; both entries are now expired.
Peter Kastinge5a38ed2021-10-02 03:06:35[diff] [blame]85 now += base::Seconds(10);
[email protected]2e9a06e2012-02-24 08:40:31[diff] [blame]86
87 EXPECT_FALSE(cache.Get("entry1", now));
88 EXPECT_FALSE(cache.Get("entry2", now));
89}
90
91TEST(ExpiringCacheTest, Compact) {
Peter Kastinge5a38ed2021-10-02 03:06:35[diff] [blame]92 const base::TimeDelta kTTL = base::Seconds(10);
[email protected]2e9a06e2012-02-24 08:40:31[diff] [blame]93
94 Cache cache(kMaxCacheEntries);
95
96 // Start at t=0.
97 base::TimeTicks now;
98 EXPECT_EQ(0U, cache.size());
99
[email protected]94bf72f2012-06-19 19:37:28[diff] [blame]100 // Add five valid entries at t=10 that expire at t=20.
[email protected]2e9a06e2012-02-24 08:40:31[diff] [blame]101 base::TimeTicks t10 = now + kTTL;
102 for (int i = 0; i < 5; ++i) {
103 std::string name = base::StringPrintf("valid%d", i);
[email protected]94bf72f2012-06-19 19:37:28[diff] [blame]104 cache.Put(name, "I'm valid!", t10, t10 + kTTL);
[email protected]2e9a06e2012-02-24 08:40:31[diff] [blame]105 }
106 EXPECT_EQ(5U, cache.size());
107
[email protected]94bf72f2012-06-19 19:37:28[diff] [blame]108 // Add three entries at t=0 that expire at t=10.
[email protected]2e9a06e2012-02-24 08:40:31[diff] [blame]109 for (int i = 0; i < 3; ++i) {
110 std::string name = base::StringPrintf("expired%d", i);
[email protected]94bf72f2012-06-19 19:37:28[diff] [blame]111 cache.Put(name, "I'm expired.", now, t10);
[email protected]2e9a06e2012-02-24 08:40:31[diff] [blame]112 }
113 EXPECT_EQ(8U, cache.size());
114
[email protected]94bf72f2012-06-19 19:37:28[diff] [blame]115 // Add two negative (instantly expired) entries at t=0 that expire at t=0.
[email protected]2e9a06e2012-02-24 08:40:31[diff] [blame]116 for (int i = 0; i < 2; ++i) {
117 std::string name = base::StringPrintf("negative%d", i);
[email protected]94bf72f2012-06-19 19:37:28[diff] [blame]118 cache.Put(name, "I was never valid.", now, now);
[email protected]2e9a06e2012-02-24 08:40:31[diff] [blame]119 }
120 EXPECT_EQ(10U, cache.size());
121
Jan Wilken Dörrie21f9de72019-06-07 10:41:53[diff] [blame]122 EXPECT_TRUE(base::Contains(cache.entries_, "valid0"));
123 EXPECT_TRUE(base::Contains(cache.entries_, "valid1"));
124 EXPECT_TRUE(base::Contains(cache.entries_, "valid2"));
125 EXPECT_TRUE(base::Contains(cache.entries_, "valid3"));
126 EXPECT_TRUE(base::Contains(cache.entries_, "valid4"));
127 EXPECT_TRUE(base::Contains(cache.entries_, "expired0"));
128 EXPECT_TRUE(base::Contains(cache.entries_, "expired1"));
129 EXPECT_TRUE(base::Contains(cache.entries_, "expired2"));
130 EXPECT_TRUE(base::Contains(cache.entries_, "negative0"));
131 EXPECT_TRUE(base::Contains(cache.entries_, "negative1"));
[email protected]2e9a06e2012-02-24 08:40:31[diff] [blame]132
133 // Shrink the new max constraints bound and compact. The "negative" and
134 // "expired" entries should be dropped.
135 cache.max_entries_ = 6;
136 cache.Compact(now);
137 EXPECT_EQ(5U, cache.size());
138
Jan Wilken Dörrie21f9de72019-06-07 10:41:53[diff] [blame]139 EXPECT_TRUE(base::Contains(cache.entries_, "valid0"));
140 EXPECT_TRUE(base::Contains(cache.entries_, "valid1"));
141 EXPECT_TRUE(base::Contains(cache.entries_, "valid2"));
142 EXPECT_TRUE(base::Contains(cache.entries_, "valid3"));
143 EXPECT_TRUE(base::Contains(cache.entries_, "valid4"));
144 EXPECT_FALSE(base::Contains(cache.entries_, "expired0"));
145 EXPECT_FALSE(base::Contains(cache.entries_, "expired1"));
146 EXPECT_FALSE(base::Contains(cache.entries_, "expired2"));
147 EXPECT_FALSE(base::Contains(cache.entries_, "negative0"));
148 EXPECT_FALSE(base::Contains(cache.entries_, "negative1"));
[email protected]2e9a06e2012-02-24 08:40:31[diff] [blame]149
150 // Shrink further -- this time the compact will start dropping valid entries
151 // to make space.
152 cache.max_entries_ = 4;
153 cache.Compact(now);
154 EXPECT_EQ(3U, cache.size());
155}
156
157// Add entries while the cache is at capacity, causing evictions.
158TEST(ExpiringCacheTest, SetWithCompact) {
Peter Kastinge5a38ed2021-10-02 03:06:35[diff] [blame]159 const base::TimeDelta kTTL = base::Seconds(10);
[email protected]2e9a06e2012-02-24 08:40:31[diff] [blame]160
161 Cache cache(3);
162
163 // t=10
164 base::TimeTicks now = base::TimeTicks() + kTTL;
165
[email protected]94bf72f2012-06-19 19:37:28[diff] [blame]166 cache.Put("test1", "test1", now, now + kTTL);
167 cache.Put("test2", "test2", now, now + kTTL);
168 cache.Put("expired", "expired", now, now);
[email protected]2e9a06e2012-02-24 08:40:31[diff] [blame]169
170 EXPECT_EQ(3U, cache.size());
171
172 // Should all be retrievable except "expired".
173 EXPECT_THAT(cache.Get("test1", now), Pointee(StrEq("test1")));
174 EXPECT_THAT(cache.Get("test2", now), Pointee(StrEq("test2")));
175 EXPECT_FALSE(cache.Get("expired", now));
176
177 // Adding the fourth entry will cause "expired" to be evicted.
[email protected]94bf72f2012-06-19 19:37:28[diff] [blame]178 cache.Put("test3", "test3", now, now + kTTL);
[email protected]2e9a06e2012-02-24 08:40:31[diff] [blame]179 EXPECT_EQ(3U, cache.size());
180
181 EXPECT_FALSE(cache.Get("expired", now));
182 EXPECT_THAT(cache.Get("test1", now), Pointee(StrEq("test1")));
183 EXPECT_THAT(cache.Get("test2", now), Pointee(StrEq("test2")));
184 EXPECT_THAT(cache.Get("test3", now), Pointee(StrEq("test3")));
185
186 // Add two more entries. Something should be evicted, however "test5"
187 // should definitely be in there (since it was last inserted).
[email protected]94bf72f2012-06-19 19:37:28[diff] [blame]188 cache.Put("test4", "test4", now, now + kTTL);
[email protected]2e9a06e2012-02-24 08:40:31[diff] [blame]189 EXPECT_EQ(3U, cache.size());
[email protected]94bf72f2012-06-19 19:37:28[diff] [blame]190 cache.Put("test5", "test5", now, now + kTTL);
[email protected]2e9a06e2012-02-24 08:40:31[diff] [blame]191 EXPECT_EQ(3U, cache.size());
192 EXPECT_THAT(cache.Get("test5", now), Pointee(StrEq("test5")));
193}
194
195TEST(ExpiringCacheTest, Clear) {
Peter Kastinge5a38ed2021-10-02 03:06:35[diff] [blame]196 const base::TimeDelta kTTL = base::Seconds(10);
[email protected]2e9a06e2012-02-24 08:40:31[diff] [blame]197
198 Cache cache(kMaxCacheEntries);
199
200 // Start at t=0.
201 base::TimeTicks now;
202 EXPECT_EQ(0U, cache.size());
203
204 // Add three entries.
[email protected]94bf72f2012-06-19 19:37:28[diff] [blame]205 cache.Put("test1", "foo", now, now + kTTL);
206 cache.Put("test2", "foo", now, now + kTTL);
207 cache.Put("test3", "foo", now, now + kTTL);
[email protected]2e9a06e2012-02-24 08:40:31[diff] [blame]208 EXPECT_EQ(3U, cache.size());
209
210 cache.Clear();
211
212 EXPECT_EQ(0U, cache.size());
213}
214
[email protected]94bf72f2012-06-19 19:37:28[diff] [blame]215TEST(ExpiringCacheTest, GetTruncatesExpiredEntries) {
Peter Kastinge5a38ed2021-10-02 03:06:35[diff] [blame]216 const base::TimeDelta kTTL = base::Seconds(10);
[email protected]2e9a06e2012-02-24 08:40:31[diff] [blame]217
218 Cache cache(kMaxCacheEntries);
219
220 // Start at t=0.
221 base::TimeTicks now;
222 EXPECT_EQ(0U, cache.size());
223
224 // Add three entries at t=0.
[email protected]94bf72f2012-06-19 19:37:28[diff] [blame]225 cache.Put("test1", "foo1", now, now + kTTL);
226 cache.Put("test2", "foo2", now, now + kTTL);
227 cache.Put("test3", "foo3", now, now + kTTL);
[email protected]2e9a06e2012-02-24 08:40:31[diff] [blame]228 EXPECT_EQ(3U, cache.size());
229
230 // Ensure the entries were added.
231 EXPECT_THAT(cache.Get("test1", now), Pointee(StrEq("foo1")));
232 EXPECT_THAT(cache.Get("test2", now), Pointee(StrEq("foo2")));
233 EXPECT_THAT(cache.Get("test3", now), Pointee(StrEq("foo3")));
234
235 // Add five entries at t=10.
236 now += kTTL;
237 for (int i = 0; i < 5; ++i) {
238 std::string name = base::StringPrintf("valid%d", i);
[email protected]94bf72f2012-06-19 19:37:28[diff] [blame]239 cache.Put(name, name, now, now + kTTL); // Expire at t=20.
[email protected]2e9a06e2012-02-24 08:40:31[diff] [blame]240 }
241 EXPECT_EQ(8U, cache.size());
242
243 // Now access two expired entries and ensure the cache size goes down.
244 EXPECT_FALSE(cache.Get("test1", now));
245 EXPECT_FALSE(cache.Get("test2", now));
246 EXPECT_EQ(6U, cache.size());
247
248 // Accessing non-expired entries should return entries and not adjust the
249 // cache size.
250 for (int i = 0; i < 5; ++i) {
251 std::string name = base::StringPrintf("valid%d", i);
252 EXPECT_THAT(cache.Get(name, now), Pointee(StrEq(name)));
253 }
254 EXPECT_EQ(6U, cache.size());
255}
256
[email protected]94bf72f2012-06-19 19:37:28[diff] [blame]257TEST(ExpiringCacheTest, CustomFunctor) {
258 ExpiringCache<std::string, std::string, std::string, TestFunctor> cache(5);
259
260 const std::string kNow("Now");
261 const std::string kLater("A little bit later");
262 const std::string kMuchLater("Much later");
263 const std::string kHeatDeath("The heat death of the universe");
264
265 EXPECT_EQ(0u, cache.size());
266
267 // Add three entries at t=kNow that expire at kLater.
268 cache.Put("test1", "foo1", kNow, kLater);
269 cache.Put("test2", "foo2", kNow, kLater);
270 cache.Put("test3", "foo3", kNow, kLater);
271 EXPECT_EQ(3U, cache.size());
272
273 // Add two entries at t=kNow that expire at kMuchLater
274 cache.Put("test4", "foo4", kNow, kMuchLater);
275 cache.Put("test5", "foo5", kNow, kMuchLater);
276 EXPECT_EQ(5U, cache.size());
277
278 // Ensure the entries were added.
279 EXPECT_THAT(cache.Get("test1", kNow), Pointee(StrEq("foo1")));
280 EXPECT_THAT(cache.Get("test2", kNow), Pointee(StrEq("foo2")));
281 EXPECT_THAT(cache.Get("test3", kNow), Pointee(StrEq("foo3")));
282 EXPECT_THAT(cache.Get("test4", kNow), Pointee(StrEq("foo4")));
283 EXPECT_THAT(cache.Get("test5", kNow), Pointee(StrEq("foo5")));
284
285 // Add one entry at t=kLater that expires at kHeatDeath, which will expire
286 // one of test1-3.
287 cache.Put("test6", "foo6", kLater, kHeatDeath);
288 EXPECT_THAT(cache.Get("test6", kLater), Pointee(StrEq("foo6")));
289 EXPECT_EQ(3U, cache.size());
290
291 // Now compact at kMuchLater, which should remove all but "test6".
292 cache.max_entries_ = 2;
293 cache.Compact(kMuchLater);
294
295 EXPECT_EQ(1U, cache.size());
296 EXPECT_THAT(cache.Get("test6", kMuchLater), Pointee(StrEq("foo6")));
297
298 // Finally, "test6" should not be valid at the end of the universe.
299 EXPECT_FALSE(cache.Get("test6", kHeatDeath));
300
301 // Because comparison is based on equality, not strict weak ordering, we
302 // should be able to add something at kHeatDeath that expires at kMuchLater.
303 cache.Put("test7", "foo7", kHeatDeath, kMuchLater);
304 EXPECT_EQ(1U, cache.size());
305 EXPECT_THAT(cache.Get("test7", kNow), Pointee(StrEq("foo7")));
306 EXPECT_THAT(cache.Get("test7", kLater), Pointee(StrEq("foo7")));
307 EXPECT_THAT(cache.Get("test7", kHeatDeath), Pointee(StrEq("foo7")));
308 EXPECT_FALSE(cache.Get("test7", kMuchLater));
309}
310
[email protected]2e9a06e2012-02-24 08:40:31[diff] [blame]311} // namespace net