1 // Copyright (c) 2009 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/host_cache.h" 6 7 #include "base/format_macros.h" 8 #include "base/stl_util-inl.h" 9 #include "base/string_util.h" 10 #include "net/base/net_errors.h" 11 #include "testing/gtest/include/gtest/gtest.h" 12 13 namespace net { 14 15 namespace { 16 const int kMaxCacheEntries = 10; 17 18 const base::TimeDelta kSuccessEntryTTL = base::TimeDelta::FromSeconds(10); 19 const base::TimeDelta kFailureEntryTTL = base::TimeDelta::FromSeconds(0); 20 21 // Builds a key for |hostname|, defaulting the address family to unspecified. 22 HostCache::Key Key(const std::string& hostname) { 23 return HostCache::Key(hostname, ADDRESS_FAMILY_UNSPECIFIED); 24 } 25 26 } // namespace 27 28 TEST(HostCacheTest, Basic) { 29 HostCache cache(kMaxCacheEntries, kSuccessEntryTTL, kFailureEntryTTL); 30 31 // Start at t=0. 32 base::TimeTicks now; 33 34 const HostCache::Entry* entry1 = NULL; // Entry for foobar.com. 35 const HostCache::Entry* entry2 = NULL; // Entry for foobar2.com. 36 37 EXPECT_EQ(0U, cache.size()); 38 39 // Add an entry for "foobar.com" at t=0. 40 EXPECT_TRUE(cache.Lookup(Key("foobar.com"), base::TimeTicks()) == NULL); 41 cache.Set(Key("foobar.com"), OK, AddressList(), now); 42 entry1 = cache.Lookup(Key("foobar.com"), base::TimeTicks()); 43 EXPECT_FALSE(entry1 == NULL); 44 EXPECT_EQ(1U, cache.size()); 45 46 // Advance to t=5. 47 now += base::TimeDelta::FromSeconds(5); 48 49 // Add an entry for "foobar2.com" at t=5. 50 EXPECT_TRUE(cache.Lookup(Key("foobar2.com"), base::TimeTicks()) == NULL); 51 cache.Set(Key("foobar2.com"), OK, AddressList(), now); 52 entry2 = cache.Lookup(Key("foobar2.com"), base::TimeTicks()); 53 EXPECT_FALSE(NULL == entry1); 54 EXPECT_EQ(2U, cache.size()); 55 56 // Advance to t=9 57 now += base::TimeDelta::FromSeconds(4); 58 59 // Verify that the entries we added are still retrievable, and usable. 60 EXPECT_EQ(entry1, cache.Lookup(Key("foobar.com"), now)); 61 EXPECT_EQ(entry2, cache.Lookup(Key("foobar2.com"), now)); 62 63 // Advance to t=10; entry1 is now expired. 64 now += base::TimeDelta::FromSeconds(1); 65 66 EXPECT_TRUE(cache.Lookup(Key("foobar.com"), now) == NULL); 67 EXPECT_EQ(entry2, cache.Lookup(Key("foobar2.com"), now)); 68 69 // Update entry1, so it is no longer expired. 70 cache.Set(Key("foobar.com"), OK, AddressList(), now); 71 // Re-uses existing entry storage. 72 EXPECT_EQ(entry1, cache.Lookup(Key("foobar.com"), now)); 73 EXPECT_EQ(2U, cache.size()); 74 75 // Both entries should still be retrievable and usable. 76 EXPECT_EQ(entry1, cache.Lookup(Key("foobar.com"), now)); 77 EXPECT_EQ(entry2, cache.Lookup(Key("foobar2.com"), now)); 78 79 // Advance to t=20; both entries are now expired. 80 now += base::TimeDelta::FromSeconds(10); 81 82 EXPECT_TRUE(cache.Lookup(Key("foobar.com"), now) == NULL); 83 EXPECT_TRUE(cache.Lookup(Key("foobar2.com"), now) == NULL); 84 } 85 86 // Try caching entries for a failed resolve attempt -- since we set 87 // the TTL of such entries to 0 it won't work. 88 TEST(HostCacheTest, NoCacheNegative) { 89 HostCache cache(kMaxCacheEntries, kSuccessEntryTTL, kFailureEntryTTL); 90 91 // Set t=0. 92 base::TimeTicks now; 93 94 EXPECT_TRUE(cache.Lookup(Key("foobar.com"), base::TimeTicks()) == NULL); 95 cache.Set(Key("foobar.com"), ERR_NAME_NOT_RESOLVED, AddressList(), now); 96 EXPECT_EQ(1U, cache.size()); 97 98 // We disallow use of negative entries. 99 EXPECT_TRUE(cache.Lookup(Key("foobar.com"), now) == NULL); 100 101 // Now overwrite with a valid entry, and then overwrite with negative entry 102 // again -- the valid entry should be kicked out. 103 cache.Set(Key("foobar.com"), OK, AddressList(), now); 104 EXPECT_FALSE(cache.Lookup(Key("foobar.com"), now) == NULL); 105 cache.Set(Key("foobar.com"), ERR_NAME_NOT_RESOLVED, AddressList(), now); 106 EXPECT_TRUE(cache.Lookup(Key("foobar.com"), now) == NULL); 107 } 108 109 // Try caching entries for a failed resolves for 10 seconds. 110 TEST(HostCacheTest, CacheNegativeEntry) { 111 HostCache cache(kMaxCacheEntries, 112 base::TimeDelta::FromSeconds(0), // success entry TTL. 113 base::TimeDelta::FromSeconds(10)); // failure entry TTL. 114 115 // Start at t=0. 116 base::TimeTicks now; 117 118 const HostCache::Entry* entry1 = NULL; // Entry for foobar.com. 119 const HostCache::Entry* entry2 = NULL; // Entry for foobar2.com. 120 121 EXPECT_EQ(0U, cache.size()); 122 123 // Add an entry for "foobar.com" at t=0. 124 EXPECT_TRUE(cache.Lookup(Key("foobar.com"), base::TimeTicks()) == NULL); 125 cache.Set(Key("foobar.com"), ERR_NAME_NOT_RESOLVED, AddressList(), now); 126 entry1 = cache.Lookup(Key("foobar.com"), base::TimeTicks()); 127 EXPECT_FALSE(entry1 == NULL); 128 EXPECT_EQ(1U, cache.size()); 129 130 // Advance to t=5. 131 now += base::TimeDelta::FromSeconds(5); 132 133 // Add an entry for "foobar2.com" at t=5. 134 EXPECT_TRUE(cache.Lookup(Key("foobar2.com"), base::TimeTicks()) == NULL); 135 cache.Set(Key("foobar2.com"), ERR_NAME_NOT_RESOLVED, AddressList(), now); 136 entry2 = cache.Lookup(Key("foobar2.com"), base::TimeTicks()); 137 EXPECT_FALSE(NULL == entry1); 138 EXPECT_EQ(2U, cache.size()); 139 140 // Advance to t=9 141 now += base::TimeDelta::FromSeconds(4); 142 143 // Verify that the entries we added are still retrievable, and usable. 144 EXPECT_EQ(entry1, cache.Lookup(Key("foobar.com"), now)); 145 EXPECT_EQ(entry2, cache.Lookup(Key("foobar2.com"), now)); 146 147 // Advance to t=10; entry1 is now expired. 148 now += base::TimeDelta::FromSeconds(1); 149 150 EXPECT_TRUE(cache.Lookup(Key("foobar.com"), now) == NULL); 151 EXPECT_EQ(entry2, cache.Lookup(Key("foobar2.com"), now)); 152 153 // Update entry1, so it is no longer expired. 154 cache.Set(Key("foobar.com"), ERR_NAME_NOT_RESOLVED, AddressList(), now); 155 // Re-uses existing entry storage. 156 EXPECT_EQ(entry1, cache.Lookup(Key("foobar.com"), now)); 157 EXPECT_EQ(2U, cache.size()); 158 159 // Both entries should still be retrievable and usable. 160 EXPECT_EQ(entry1, cache.Lookup(Key("foobar.com"), now)); 161 EXPECT_EQ(entry2, cache.Lookup(Key("foobar2.com"), now)); 162 163 // Advance to t=20; both entries are now expired. 164 now += base::TimeDelta::FromSeconds(10); 165 166 EXPECT_TRUE(cache.Lookup(Key("foobar.com"), now) == NULL); 167 EXPECT_TRUE(cache.Lookup(Key("foobar2.com"), now) == NULL); 168 } 169 170 TEST(HostCacheTest, Compact) { 171 // Initial entries limit is big enough to accomadate everything we add. 172 HostCache cache(kMaxCacheEntries, kSuccessEntryTTL, kFailureEntryTTL); 173 174 EXPECT_EQ(0U, cache.size()); 175 176 // t=10 177 base::TimeTicks now = base::TimeTicks() + base::TimeDelta::FromSeconds(10); 178 179 // Add five valid entries at t=10. 180 for (int i = 0; i < 5; ++i) { 181 std::string hostname = StringPrintf("valid%d", i); 182 cache.Set(Key(hostname), OK, AddressList(), now); 183 } 184 EXPECT_EQ(5U, cache.size()); 185 186 // Add 3 expired entries at t=0. 187 for (int i = 0; i < 3; ++i) { 188 std::string hostname = StringPrintf("expired%d", i); 189 base::TimeTicks t = now - base::TimeDelta::FromSeconds(10); 190 cache.Set(Key(hostname), OK, AddressList(), t); 191 } 192 EXPECT_EQ(8U, cache.size()); 193 194 // Add 2 negative entries at t=10 195 for (int i = 0; i < 2; ++i) { 196 std::string hostname = StringPrintf("negative%d", i); 197 cache.Set(Key(hostname), ERR_NAME_NOT_RESOLVED, AddressList(), now); 198 } 199 EXPECT_EQ(10U, cache.size()); 200 201 EXPECT_TRUE(ContainsKey(cache.entries_, Key("valid0"))); 202 EXPECT_TRUE(ContainsKey(cache.entries_, Key("valid1"))); 203 EXPECT_TRUE(ContainsKey(cache.entries_, Key("valid2"))); 204 EXPECT_TRUE(ContainsKey(cache.entries_, Key("valid3"))); 205 EXPECT_TRUE(ContainsKey(cache.entries_, Key("valid4"))); 206 EXPECT_TRUE(ContainsKey(cache.entries_, Key("expired0"))); 207 EXPECT_TRUE(ContainsKey(cache.entries_, Key("expired1"))); 208 EXPECT_TRUE(ContainsKey(cache.entries_, Key("expired2"))); 209 EXPECT_TRUE(ContainsKey(cache.entries_, Key("negative0"))); 210 EXPECT_TRUE(ContainsKey(cache.entries_, Key("negative1"))); 211 212 // Shrink the max constraints bound and compact. We expect the "negative" 213 // and "expired" entries to have been dropped. 214 cache.max_entries_ = 5; 215 cache.Compact(now, NULL); 216 EXPECT_EQ(5U, cache.entries_.size()); 217 218 EXPECT_TRUE(ContainsKey(cache.entries_, Key("valid0"))); 219 EXPECT_TRUE(ContainsKey(cache.entries_, Key("valid1"))); 220 EXPECT_TRUE(ContainsKey(cache.entries_, Key("valid2"))); 221 EXPECT_TRUE(ContainsKey(cache.entries_, Key("valid3"))); 222 EXPECT_TRUE(ContainsKey(cache.entries_, Key("valid4"))); 223 EXPECT_FALSE(ContainsKey(cache.entries_, Key("expired0"))); 224 EXPECT_FALSE(ContainsKey(cache.entries_, Key("expired1"))); 225 EXPECT_FALSE(ContainsKey(cache.entries_, Key("expired2"))); 226 EXPECT_FALSE(ContainsKey(cache.entries_, Key("negative0"))); 227 EXPECT_FALSE(ContainsKey(cache.entries_, Key("negative1"))); 228 229 // Shrink further -- this time the compact will start dropping valid entries 230 // to make space. 231 cache.max_entries_ = 3; 232 cache.Compact(now, NULL); 233 EXPECT_EQ(3U, cache.size()); 234 } 235 236 // Add entries while the cache is at capacity, causing evictions. 237 TEST(HostCacheTest, SetWithCompact) { 238 HostCache cache(3, kSuccessEntryTTL, kFailureEntryTTL); 239 240 // t=10 241 base::TimeTicks now = base::TimeTicks() + kSuccessEntryTTL; 242 243 cache.Set(Key("host1"), OK, AddressList(), now); 244 cache.Set(Key("host2"), OK, AddressList(), now); 245 cache.Set(Key("expired"), OK, AddressList(), now - kSuccessEntryTTL); 246 247 EXPECT_EQ(3U, cache.size()); 248 249 // Should all be retrievable except "expired". 250 EXPECT_FALSE(NULL == cache.Lookup(Key("host1"), now)); 251 EXPECT_FALSE(NULL == cache.Lookup(Key("host2"), now)); 252 EXPECT_TRUE(NULL == cache.Lookup(Key("expired"), now)); 253 254 // Adding the fourth entry will cause "expired" to be evicted. 255 cache.Set(Key("host3"), OK, AddressList(), now); 256 EXPECT_EQ(3U, cache.size()); 257 EXPECT_TRUE(cache.Lookup(Key("expired"), now) == NULL); 258 EXPECT_FALSE(cache.Lookup(Key("host1"), now) == NULL); 259 EXPECT_FALSE(cache.Lookup(Key("host2"), now) == NULL); 260 EXPECT_FALSE(cache.Lookup(Key("host3"), now) == NULL); 261 262 // Add two more entries. Something should be evicted, however "host5" 263 // should definitely be in there (since it was last inserted). 264 cache.Set(Key("host4"), OK, AddressList(), now); 265 EXPECT_EQ(3U, cache.size()); 266 cache.Set(Key("host5"), OK, AddressList(), now); 267 EXPECT_EQ(3U, cache.size()); 268 EXPECT_FALSE(cache.Lookup(Key("host5"), now) == NULL); 269 } 270 271 // Tests that the same hostname can be duplicated in the cache, so long as 272 // the address family differs. 273 TEST(HostCacheTest, AddressFamilyIsPartOfKey) { 274 HostCache cache(kMaxCacheEntries, kSuccessEntryTTL, kFailureEntryTTL); 275 276 // t=0. 277 base::TimeTicks now; 278 279 HostCache::Key key1("foobar.com", ADDRESS_FAMILY_UNSPECIFIED); 280 HostCache::Key key2("foobar.com", ADDRESS_FAMILY_IPV4); 281 282 const HostCache::Entry* entry1 = NULL; // Entry for key1 283 const HostCache::Entry* entry2 = NULL; // Entry for key2 284 285 EXPECT_EQ(0U, cache.size()); 286 287 // Add an entry for ("foobar.com", UNSPECIFIED) at t=0. 288 EXPECT_TRUE(cache.Lookup(key1, base::TimeTicks()) == NULL); 289 cache.Set(key1, OK, AddressList(), now); 290 entry1 = cache.Lookup(key1, base::TimeTicks()); 291 EXPECT_FALSE(entry1 == NULL); 292 EXPECT_EQ(1U, cache.size()); 293 294 // Add an entry for ("foobar.com", IPV4_ONLY) at t=0. 295 EXPECT_TRUE(cache.Lookup(key2, base::TimeTicks()) == NULL); 296 cache.Set(key2, OK, AddressList(), now); 297 entry2 = cache.Lookup(key2, base::TimeTicks()); 298 EXPECT_FALSE(entry2 == NULL); 299 EXPECT_EQ(2U, cache.size()); 300 301 // Even though the hostnames were the same, we should have two unique 302 // entries (because the address families differ). 303 EXPECT_NE(entry1, entry2); 304 } 305 306 TEST(HostCacheTest, NoCache) { 307 // Disable caching. 308 HostCache cache(0, kSuccessEntryTTL, kFailureEntryTTL); 309 EXPECT_TRUE(cache.caching_is_disabled()); 310 311 // Set t=0. 312 base::TimeTicks now; 313 314 // Lookup and Set should have no effect. 315 EXPECT_TRUE(cache.Lookup(Key("foobar.com"), base::TimeTicks()) == NULL); 316 cache.Set(Key("foobar.com"), OK, AddressList(), now); 317 EXPECT_TRUE(cache.Lookup(Key("foobar.com"), base::TimeTicks()) == NULL); 318 319 EXPECT_EQ(0U, cache.size()); 320 } 321 322 TEST(HostCacheTest, Clear) { 323 HostCache cache(kMaxCacheEntries, kSuccessEntryTTL, kFailureEntryTTL); 324 325 // Set t=0. 326 base::TimeTicks now; 327 328 EXPECT_EQ(0u, cache.size()); 329 330 // Add three entries. 331 cache.Set(Key("foobar1.com"), OK, AddressList(), now); 332 cache.Set(Key("foobar2.com"), OK, AddressList(), now); 333 cache.Set(Key("foobar3.com"), OK, AddressList(), now); 334 335 EXPECT_EQ(3u, cache.size()); 336 337 cache.clear(); 338 339 EXPECT_EQ(0u, cache.size()); 340 } 341 342 // Tests the less than and equal operators for HostCache::Key work. 343 TEST(HostCacheTest, KeyComparators) { 344 struct { 345 // Inputs. 346 HostCache::Key key1; 347 HostCache::Key key2; 348 349 // Expectation. 350 // -1 means key1 is less than key2 351 // 0 means key1 equals key2 352 // 1 means key1 is greater than key2 353 int expected_comparison; 354 } tests[] = { 355 { 356 HostCache::Key("host1", ADDRESS_FAMILY_UNSPECIFIED), 357 HostCache::Key("host1", ADDRESS_FAMILY_UNSPECIFIED), 358 0 359 }, 360 { 361 HostCache::Key("host1", ADDRESS_FAMILY_IPV4), 362 HostCache::Key("host1", ADDRESS_FAMILY_UNSPECIFIED), 363 1 364 }, 365 { 366 HostCache::Key("host1", ADDRESS_FAMILY_UNSPECIFIED), 367 HostCache::Key("host1", ADDRESS_FAMILY_IPV4), 368 -1 369 }, 370 { 371 HostCache::Key("host1", ADDRESS_FAMILY_UNSPECIFIED), 372 HostCache::Key("host2", ADDRESS_FAMILY_UNSPECIFIED), 373 -1 374 }, 375 { 376 HostCache::Key("host1", ADDRESS_FAMILY_IPV4), 377 HostCache::Key("host2", ADDRESS_FAMILY_UNSPECIFIED), 378 1 379 }, 380 { 381 HostCache::Key("host1", ADDRESS_FAMILY_UNSPECIFIED), 382 HostCache::Key("host2", ADDRESS_FAMILY_IPV4), 383 -1 384 }, 385 }; 386 387 for (size_t i = 0; i < ARRAYSIZE_UNSAFE(tests); ++i) { 388 SCOPED_TRACE(StringPrintf("Test[%" PRIuS "]", i)); 389 390 const HostCache::Key& key1 = tests[i].key1; 391 const HostCache::Key& key2 = tests[i].key2; 392 393 switch (tests[i].expected_comparison) { 394 case -1: 395 EXPECT_TRUE(key1 < key2); 396 EXPECT_FALSE(key2 < key1); 397 EXPECT_FALSE(key2 == key1); 398 break; 399 case 0: 400 EXPECT_FALSE(key1 < key2); 401 EXPECT_FALSE(key2 < key1); 402 EXPECT_TRUE(key2 == key1); 403 break; 404 case 1: 405 EXPECT_FALSE(key1 < key2); 406 EXPECT_TRUE(key2 < key1); 407 EXPECT_FALSE(key2 == key1); 408 break; 409 default: 410 FAIL() << "Invalid expectation. Can be only -1, 0, 1"; 411 } 412 } 413 } 414 415 } // namespace net 416