1 // Copyright (c) 2012 The Chromium 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. 4 5 #include "net/base/expiring_cache.h" 6 7 #include <functional> 8 #include <string> 9 10 #include "base/stl_util.h" 11 #include "base/strings/stringprintf.h" 12 #include "base/time/time.h" 13 #include "testing/gmock/include/gmock/gmock.h" 14 #include "testing/gtest/include/gtest/gtest.h" 15 16 using testing::Pointee; 17 using testing::StrEq; 18 19 namespace net { 20 21 namespace { 22 23 const int kMaxCacheEntries = 10; 24 typedef ExpiringCache<std::string, std::string, base::TimeTicks, 25 std::less<base::TimeTicks> > Cache; 26 27 struct TestFunctor { 28 bool operator()(const std::string& now, 29 const std::string& expiration) const { 30 return now != expiration; 31 } 32 }; 33 34 } // namespace 35 36 TEST(ExpiringCacheTest, Basic) { 37 const base::TimeDelta kTTL = base::TimeDelta::FromSeconds(10); 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)); 47 cache.Put("entry1", "test1", now, now + kTTL); 48 EXPECT_THAT(cache.Get("entry1", now), Pointee(StrEq("test1"))); 49 EXPECT_EQ(1U, cache.size()); 50 51 // Advance to t=5. 52 now += base::TimeDelta::FromSeconds(5); 53 54 // Add an entry at t=5. 55 EXPECT_FALSE(cache.Get("entry2", now)); 56 cache.Put("entry2", "test2", now, now + kTTL); 57 EXPECT_THAT(cache.Get("entry2", now), Pointee(StrEq("test2"))); 58 EXPECT_EQ(2U, cache.size()); 59 60 // Advance to t=9. 61 now += base::TimeDelta::FromSeconds(4); 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. 68 now += base::TimeDelta::FromSeconds(1); 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. 77 cache.Put("entry1", "test1", now, now + kTTL); 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. 85 now += base::TimeDelta::FromSeconds(10); 86 87 EXPECT_FALSE(cache.Get("entry1", now)); 88 EXPECT_FALSE(cache.Get("entry2", now)); 89 } 90 91 TEST(ExpiringCacheTest, Compact) { 92 const base::TimeDelta kTTL = base::TimeDelta::FromSeconds(10); 93 94 Cache cache(kMaxCacheEntries); 95 96 // Start at t=0. 97 base::TimeTicks now; 98 EXPECT_EQ(0U, cache.size()); 99 100 // Add five valid entries at t=10 that expire at t=20. 101 base::TimeTicks t10 = now + kTTL; 102 for (int i = 0; i < 5; ++i) { 103 std::string name = base::StringPrintf("valid%d", i); 104 cache.Put(name, "I'm valid!", t10, t10 + kTTL); 105 } 106 EXPECT_EQ(5U, cache.size()); 107 108 // Add three entries at t=0 that expire at t=10. 109 for (int i = 0; i < 3; ++i) { 110 std::string name = base::StringPrintf("expired%d", i); 111 cache.Put(name, "I'm expired.", now, t10); 112 } 113 EXPECT_EQ(8U, cache.size()); 114 115 // Add two negative (instantly expired) entries at t=0 that expire at t=0. 116 for (int i = 0; i < 2; ++i) { 117 std::string name = base::StringPrintf("negative%d", i); 118 cache.Put(name, "I was never valid.", now, now); 119 } 120 EXPECT_EQ(10U, cache.size()); 121 122 EXPECT_TRUE(ContainsKey(cache.entries_, "valid0")); 123 EXPECT_TRUE(ContainsKey(cache.entries_, "valid1")); 124 EXPECT_TRUE(ContainsKey(cache.entries_, "valid2")); 125 EXPECT_TRUE(ContainsKey(cache.entries_, "valid3")); 126 EXPECT_TRUE(ContainsKey(cache.entries_, "valid4")); 127 EXPECT_TRUE(ContainsKey(cache.entries_, "expired0")); 128 EXPECT_TRUE(ContainsKey(cache.entries_, "expired1")); 129 EXPECT_TRUE(ContainsKey(cache.entries_, "expired2")); 130 EXPECT_TRUE(ContainsKey(cache.entries_, "negative0")); 131 EXPECT_TRUE(ContainsKey(cache.entries_, "negative1")); 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 139 EXPECT_TRUE(ContainsKey(cache.entries_, "valid0")); 140 EXPECT_TRUE(ContainsKey(cache.entries_, "valid1")); 141 EXPECT_TRUE(ContainsKey(cache.entries_, "valid2")); 142 EXPECT_TRUE(ContainsKey(cache.entries_, "valid3")); 143 EXPECT_TRUE(ContainsKey(cache.entries_, "valid4")); 144 EXPECT_FALSE(ContainsKey(cache.entries_, "expired0")); 145 EXPECT_FALSE(ContainsKey(cache.entries_, "expired1")); 146 EXPECT_FALSE(ContainsKey(cache.entries_, "expired2")); 147 EXPECT_FALSE(ContainsKey(cache.entries_, "negative0")); 148 EXPECT_FALSE(ContainsKey(cache.entries_, "negative1")); 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. 158 TEST(ExpiringCacheTest, SetWithCompact) { 159 const base::TimeDelta kTTL = base::TimeDelta::FromSeconds(10); 160 161 Cache cache(3); 162 163 // t=10 164 base::TimeTicks now = base::TimeTicks() + kTTL; 165 166 cache.Put("test1", "test1", now, now + kTTL); 167 cache.Put("test2", "test2", now, now + kTTL); 168 cache.Put("expired", "expired", now, now); 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. 178 cache.Put("test3", "test3", now, now + kTTL); 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). 188 cache.Put("test4", "test4", now, now + kTTL); 189 EXPECT_EQ(3U, cache.size()); 190 cache.Put("test5", "test5", now, now + kTTL); 191 EXPECT_EQ(3U, cache.size()); 192 EXPECT_THAT(cache.Get("test5", now), Pointee(StrEq("test5"))); 193 } 194 195 TEST(ExpiringCacheTest, Clear) { 196 const base::TimeDelta kTTL = base::TimeDelta::FromSeconds(10); 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. 205 cache.Put("test1", "foo", now, now + kTTL); 206 cache.Put("test2", "foo", now, now + kTTL); 207 cache.Put("test3", "foo", now, now + kTTL); 208 EXPECT_EQ(3U, cache.size()); 209 210 cache.Clear(); 211 212 EXPECT_EQ(0U, cache.size()); 213 } 214 215 TEST(ExpiringCacheTest, GetTruncatesExpiredEntries) { 216 const base::TimeDelta kTTL = base::TimeDelta::FromSeconds(10); 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. 225 cache.Put("test1", "foo1", now, now + kTTL); 226 cache.Put("test2", "foo2", now, now + kTTL); 227 cache.Put("test3", "foo3", now, now + kTTL); 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); 239 cache.Put(name, name, now, now + kTTL); // Expire at t=20. 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 257 TEST(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 311 } // namespace net 312
