net/base/expiring_cache_unittest.cc

   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