expiring_cache_unittest.cc 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311
  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. #include "net/base/expiring_cache.h"
  5. #include <functional>
  6. #include <string>
  7. #include "base/containers/contains.h"
  8. #include "base/strings/stringprintf.h"
  9. #include "base/time/time.h"
  10. #include "testing/gmock/include/gmock/gmock.h"
  11. #include "testing/gtest/include/gtest/gtest.h"
  12. using testing::Pointee;
  13. using testing::StrEq;
  14. namespace net {
  15. namespace {
  16. const int kMaxCacheEntries = 10;
  17. typedef ExpiringCache<std::string, std::string, base::TimeTicks, std::less<>>
  18. Cache;
  19. struct TestFunctor {
  20. bool operator()(const std::string& now,
  21. const std::string& expiration) const {
  22. return now != expiration;
  23. }
  24. };
  25. } // namespace
  26. TEST(ExpiringCacheTest, Basic) {
  27. const base::TimeDelta kTTL = base::Seconds(10);
  28. Cache cache(kMaxCacheEntries);
  29. // Start at t=0.
  30. base::TimeTicks now;
  31. EXPECT_EQ(0U, cache.size());
  32. // Add an entry at t=0
  33. EXPECT_FALSE(cache.Get("entry1", now));
  34. cache.Put("entry1", "test1", now, now + kTTL);
  35. EXPECT_THAT(cache.Get("entry1", now), Pointee(StrEq("test1")));
  36. EXPECT_EQ(1U, cache.size());
  37. // Advance to t=5.
  38. now += base::Seconds(5);
  39. // Add an entry at t=5.
  40. EXPECT_FALSE(cache.Get("entry2", now));
  41. cache.Put("entry2", "test2", now, now + kTTL);
  42. EXPECT_THAT(cache.Get("entry2", now), Pointee(StrEq("test2")));
  43. EXPECT_EQ(2U, cache.size());
  44. // Advance to t=9.
  45. now += base::Seconds(4);
  46. // Verify that the entries added are still retrievable and usable.
  47. EXPECT_THAT(cache.Get("entry1", now), Pointee(StrEq("test1")));
  48. EXPECT_THAT(cache.Get("entry2", now), Pointee(StrEq("test2")));
  49. // Advance to t=10; entry1 is now expired.
  50. now += base::Seconds(1);
  51. EXPECT_FALSE(cache.Get("entry1", now));
  52. EXPECT_THAT(cache.Get("entry2", now), Pointee(StrEq("test2")));
  53. // The expired element should no longer be in the cache.
  54. EXPECT_EQ(1U, cache.size());
  55. // Update entry1 so it is no longer expired.
  56. cache.Put("entry1", "test1", now, now + kTTL);
  57. // Both entries should be retrievable and usable.
  58. EXPECT_EQ(2U, cache.size());
  59. EXPECT_THAT(cache.Get("entry1", now), Pointee(StrEq("test1")));
  60. EXPECT_THAT(cache.Get("entry2", now), Pointee(StrEq("test2")));
  61. // Advance to t=20; both entries are now expired.
  62. now += base::Seconds(10);
  63. EXPECT_FALSE(cache.Get("entry1", now));
  64. EXPECT_FALSE(cache.Get("entry2", now));
  65. }
  66. TEST(ExpiringCacheTest, Compact) {
  67. const base::TimeDelta kTTL = base::Seconds(10);
  68. Cache cache(kMaxCacheEntries);
  69. // Start at t=0.
  70. base::TimeTicks now;
  71. EXPECT_EQ(0U, cache.size());
  72. // Add five valid entries at t=10 that expire at t=20.
  73. base::TimeTicks t10 = now + kTTL;
  74. for (int i = 0; i < 5; ++i) {
  75. std::string name = base::StringPrintf("valid%d", i);
  76. cache.Put(name, "I'm valid!", t10, t10 + kTTL);
  77. }
  78. EXPECT_EQ(5U, cache.size());
  79. // Add three entries at t=0 that expire at t=10.
  80. for (int i = 0; i < 3; ++i) {
  81. std::string name = base::StringPrintf("expired%d", i);
  82. cache.Put(name, "I'm expired.", now, t10);
  83. }
  84. EXPECT_EQ(8U, cache.size());
  85. // Add two negative (instantly expired) entries at t=0 that expire at t=0.
  86. for (int i = 0; i < 2; ++i) {
  87. std::string name = base::StringPrintf("negative%d", i);
  88. cache.Put(name, "I was never valid.", now, now);
  89. }
  90. EXPECT_EQ(10U, cache.size());
  91. EXPECT_TRUE(base::Contains(cache.entries_, "valid0"));
  92. EXPECT_TRUE(base::Contains(cache.entries_, "valid1"));
  93. EXPECT_TRUE(base::Contains(cache.entries_, "valid2"));
  94. EXPECT_TRUE(base::Contains(cache.entries_, "valid3"));
  95. EXPECT_TRUE(base::Contains(cache.entries_, "valid4"));
  96. EXPECT_TRUE(base::Contains(cache.entries_, "expired0"));
  97. EXPECT_TRUE(base::Contains(cache.entries_, "expired1"));
  98. EXPECT_TRUE(base::Contains(cache.entries_, "expired2"));
  99. EXPECT_TRUE(base::Contains(cache.entries_, "negative0"));
  100. EXPECT_TRUE(base::Contains(cache.entries_, "negative1"));
  101. // Shrink the new max constraints bound and compact. The "negative" and
  102. // "expired" entries should be dropped.
  103. cache.max_entries_ = 6;
  104. cache.Compact(now);
  105. EXPECT_EQ(5U, cache.size());
  106. EXPECT_TRUE(base::Contains(cache.entries_, "valid0"));
  107. EXPECT_TRUE(base::Contains(cache.entries_, "valid1"));
  108. EXPECT_TRUE(base::Contains(cache.entries_, "valid2"));
  109. EXPECT_TRUE(base::Contains(cache.entries_, "valid3"));
  110. EXPECT_TRUE(base::Contains(cache.entries_, "valid4"));
  111. EXPECT_FALSE(base::Contains(cache.entries_, "expired0"));
  112. EXPECT_FALSE(base::Contains(cache.entries_, "expired1"));
  113. EXPECT_FALSE(base::Contains(cache.entries_, "expired2"));
  114. EXPECT_FALSE(base::Contains(cache.entries_, "negative0"));
  115. EXPECT_FALSE(base::Contains(cache.entries_, "negative1"));
  116. // Shrink further -- this time the compact will start dropping valid entries
  117. // to make space.
  118. cache.max_entries_ = 4;
  119. cache.Compact(now);
  120. EXPECT_EQ(3U, cache.size());
  121. }
  122. // Add entries while the cache is at capacity, causing evictions.
  123. TEST(ExpiringCacheTest, SetWithCompact) {
  124. const base::TimeDelta kTTL = base::Seconds(10);
  125. Cache cache(3);
  126. // t=10
  127. base::TimeTicks now = base::TimeTicks() + kTTL;
  128. cache.Put("test1", "test1", now, now + kTTL);
  129. cache.Put("test2", "test2", now, now + kTTL);
  130. cache.Put("expired", "expired", now, now);
  131. EXPECT_EQ(3U, cache.size());
  132. // Should all be retrievable except "expired".
  133. EXPECT_THAT(cache.Get("test1", now), Pointee(StrEq("test1")));
  134. EXPECT_THAT(cache.Get("test2", now), Pointee(StrEq("test2")));
  135. EXPECT_FALSE(cache.Get("expired", now));
  136. // Adding the fourth entry will cause "expired" to be evicted.
  137. cache.Put("test3", "test3", now, now + kTTL);
  138. EXPECT_EQ(3U, cache.size());
  139. EXPECT_FALSE(cache.Get("expired", now));
  140. EXPECT_THAT(cache.Get("test1", now), Pointee(StrEq("test1")));
  141. EXPECT_THAT(cache.Get("test2", now), Pointee(StrEq("test2")));
  142. EXPECT_THAT(cache.Get("test3", now), Pointee(StrEq("test3")));
  143. // Add two more entries. Something should be evicted, however "test5"
  144. // should definitely be in there (since it was last inserted).
  145. cache.Put("test4", "test4", now, now + kTTL);
  146. EXPECT_EQ(3U, cache.size());
  147. cache.Put("test5", "test5", now, now + kTTL);
  148. EXPECT_EQ(3U, cache.size());
  149. EXPECT_THAT(cache.Get("test5", now), Pointee(StrEq("test5")));
  150. }
  151. TEST(ExpiringCacheTest, Clear) {
  152. const base::TimeDelta kTTL = base::Seconds(10);
  153. Cache cache(kMaxCacheEntries);
  154. // Start at t=0.
  155. base::TimeTicks now;
  156. EXPECT_EQ(0U, cache.size());
  157. // Add three entries.
  158. cache.Put("test1", "foo", now, now + kTTL);
  159. cache.Put("test2", "foo", now, now + kTTL);
  160. cache.Put("test3", "foo", now, now + kTTL);
  161. EXPECT_EQ(3U, cache.size());
  162. cache.Clear();
  163. EXPECT_EQ(0U, cache.size());
  164. }
  165. TEST(ExpiringCacheTest, GetTruncatesExpiredEntries) {
  166. const base::TimeDelta kTTL = base::Seconds(10);
  167. Cache cache(kMaxCacheEntries);
  168. // Start at t=0.
  169. base::TimeTicks now;
  170. EXPECT_EQ(0U, cache.size());
  171. // Add three entries at t=0.
  172. cache.Put("test1", "foo1", now, now + kTTL);
  173. cache.Put("test2", "foo2", now, now + kTTL);
  174. cache.Put("test3", "foo3", now, now + kTTL);
  175. EXPECT_EQ(3U, cache.size());
  176. // Ensure the entries were added.
  177. EXPECT_THAT(cache.Get("test1", now), Pointee(StrEq("foo1")));
  178. EXPECT_THAT(cache.Get("test2", now), Pointee(StrEq("foo2")));
  179. EXPECT_THAT(cache.Get("test3", now), Pointee(StrEq("foo3")));
  180. // Add five entries at t=10.
  181. now += kTTL;
  182. for (int i = 0; i < 5; ++i) {
  183. std::string name = base::StringPrintf("valid%d", i);
  184. cache.Put(name, name, now, now + kTTL); // Expire at t=20.
  185. }
  186. EXPECT_EQ(8U, cache.size());
  187. // Now access two expired entries and ensure the cache size goes down.
  188. EXPECT_FALSE(cache.Get("test1", now));
  189. EXPECT_FALSE(cache.Get("test2", now));
  190. EXPECT_EQ(6U, cache.size());
  191. // Accessing non-expired entries should return entries and not adjust the
  192. // cache size.
  193. for (int i = 0; i < 5; ++i) {
  194. std::string name = base::StringPrintf("valid%d", i);
  195. EXPECT_THAT(cache.Get(name, now), Pointee(StrEq(name)));
  196. }
  197. EXPECT_EQ(6U, cache.size());
  198. }
  199. TEST(ExpiringCacheTest, CustomFunctor) {
  200. ExpiringCache<std::string, std::string, std::string, TestFunctor> cache(5);
  201. const std::string kNow("Now");
  202. const std::string kLater("A little bit later");
  203. const std::string kMuchLater("Much later");
  204. const std::string kHeatDeath("The heat death of the universe");
  205. EXPECT_EQ(0u, cache.size());
  206. // Add three entries at t=kNow that expire at kLater.
  207. cache.Put("test1", "foo1", kNow, kLater);
  208. cache.Put("test2", "foo2", kNow, kLater);
  209. cache.Put("test3", "foo3", kNow, kLater);
  210. EXPECT_EQ(3U, cache.size());
  211. // Add two entries at t=kNow that expire at kMuchLater
  212. cache.Put("test4", "foo4", kNow, kMuchLater);
  213. cache.Put("test5", "foo5", kNow, kMuchLater);
  214. EXPECT_EQ(5U, cache.size());
  215. // Ensure the entries were added.
  216. EXPECT_THAT(cache.Get("test1", kNow), Pointee(StrEq("foo1")));
  217. EXPECT_THAT(cache.Get("test2", kNow), Pointee(StrEq("foo2")));
  218. EXPECT_THAT(cache.Get("test3", kNow), Pointee(StrEq("foo3")));
  219. EXPECT_THAT(cache.Get("test4", kNow), Pointee(StrEq("foo4")));
  220. EXPECT_THAT(cache.Get("test5", kNow), Pointee(StrEq("foo5")));
  221. // Add one entry at t=kLater that expires at kHeatDeath, which will expire
  222. // one of test1-3.
  223. cache.Put("test6", "foo6", kLater, kHeatDeath);
  224. EXPECT_THAT(cache.Get("test6", kLater), Pointee(StrEq("foo6")));
  225. EXPECT_EQ(3U, cache.size());
  226. // Now compact at kMuchLater, which should remove all but "test6".
  227. cache.max_entries_ = 2;
  228. cache.Compact(kMuchLater);
  229. EXPECT_EQ(1U, cache.size());
  230. EXPECT_THAT(cache.Get("test6", kMuchLater), Pointee(StrEq("foo6")));
  231. // Finally, "test6" should not be valid at the end of the universe.
  232. EXPECT_FALSE(cache.Get("test6", kHeatDeath));
  233. // Because comparison is based on equality, not strict weak ordering, we
  234. // should be able to add something at kHeatDeath that expires at kMuchLater.
  235. cache.Put("test7", "foo7", kHeatDeath, kMuchLater);
  236. EXPECT_EQ(1U, cache.size());
  237. EXPECT_THAT(cache.Get("test7", kNow), Pointee(StrEq("foo7")));
  238. EXPECT_THAT(cache.Get("test7", kLater), Pointee(StrEq("foo7")));
  239. EXPECT_THAT(cache.Get("test7", kHeatDeath), Pointee(StrEq("foo7")));
  240. EXPECT_FALSE(cache.Get("test7", kMuchLater));
  241. }
  242. } // namespace net