// Copyright (c) 2010 The Chromium Authors. All rights reserved. // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. #include "net/base/host_cache.h" #include "base/format_macros.h" #include "base/stl_util-inl.h" #include "base/string_util.h" #include "base/stringprintf.h" #include "net/base/net_errors.h" #include "testing/gtest/include/gtest/gtest.h" namespace net { namespace { const int kMaxCacheEntries = 10; const base::TimeDelta kSuccessEntryTTL = base::TimeDelta::FromSeconds(10); const base::TimeDelta kFailureEntryTTL = base::TimeDelta::FromSeconds(0); // Builds a key for |hostname|, defaulting the address family to unspecified. HostCache::Key Key(const std::string& hostname) { return HostCache::Key(hostname, ADDRESS_FAMILY_UNSPECIFIED, 0); } } // namespace TEST(HostCacheTest, Basic) { HostCache cache(kMaxCacheEntries, kSuccessEntryTTL, kFailureEntryTTL); // Start at t=0. base::TimeTicks now; const HostCache::Entry* entry1 = NULL; // Entry for foobar.com. const HostCache::Entry* entry2 = NULL; // Entry for foobar2.com. EXPECT_EQ(0U, cache.size()); // Add an entry for "foobar.com" at t=0. EXPECT_TRUE(cache.Lookup(Key("foobar.com"), base::TimeTicks()) == NULL); cache.Set(Key("foobar.com"), OK, AddressList(), now); entry1 = cache.Lookup(Key("foobar.com"), base::TimeTicks()); EXPECT_FALSE(entry1 == NULL); EXPECT_EQ(1U, cache.size()); // Advance to t=5. now += base::TimeDelta::FromSeconds(5); // Add an entry for "foobar2.com" at t=5. EXPECT_TRUE(cache.Lookup(Key("foobar2.com"), base::TimeTicks()) == NULL); cache.Set(Key("foobar2.com"), OK, AddressList(), now); entry2 = cache.Lookup(Key("foobar2.com"), base::TimeTicks()); EXPECT_FALSE(NULL == entry1); EXPECT_EQ(2U, cache.size()); // Advance to t=9 now += base::TimeDelta::FromSeconds(4); // Verify that the entries we added are still retrievable, and usable. EXPECT_EQ(entry1, cache.Lookup(Key("foobar.com"), now)); EXPECT_EQ(entry2, cache.Lookup(Key("foobar2.com"), now)); // Advance to t=10; entry1 is now expired. now += base::TimeDelta::FromSeconds(1); EXPECT_TRUE(cache.Lookup(Key("foobar.com"), now) == NULL); EXPECT_EQ(entry2, cache.Lookup(Key("foobar2.com"), now)); // Update entry1, so it is no longer expired. cache.Set(Key("foobar.com"), OK, AddressList(), now); // Re-uses existing entry storage. EXPECT_EQ(entry1, cache.Lookup(Key("foobar.com"), now)); EXPECT_EQ(2U, cache.size()); // Both entries should still be retrievable and usable. EXPECT_EQ(entry1, cache.Lookup(Key("foobar.com"), now)); EXPECT_EQ(entry2, cache.Lookup(Key("foobar2.com"), now)); // Advance to t=20; both entries are now expired. now += base::TimeDelta::FromSeconds(10); EXPECT_TRUE(cache.Lookup(Key("foobar.com"), now) == NULL); EXPECT_TRUE(cache.Lookup(Key("foobar2.com"), now) == NULL); } // Try caching entries for a failed resolve attempt -- since we set // the TTL of such entries to 0 it won't work. TEST(HostCacheTest, NoCacheNegative) { HostCache cache(kMaxCacheEntries, kSuccessEntryTTL, kFailureEntryTTL); // Set t=0. base::TimeTicks now; EXPECT_TRUE(cache.Lookup(Key("foobar.com"), base::TimeTicks()) == NULL); cache.Set(Key("foobar.com"), ERR_NAME_NOT_RESOLVED, AddressList(), now); EXPECT_EQ(1U, cache.size()); // We disallow use of negative entries. EXPECT_TRUE(cache.Lookup(Key("foobar.com"), now) == NULL); // Now overwrite with a valid entry, and then overwrite with negative entry // again -- the valid entry should be kicked out. cache.Set(Key("foobar.com"), OK, AddressList(), now); EXPECT_FALSE(cache.Lookup(Key("foobar.com"), now) == NULL); cache.Set(Key("foobar.com"), ERR_NAME_NOT_RESOLVED, AddressList(), now); EXPECT_TRUE(cache.Lookup(Key("foobar.com"), now) == NULL); } // Try caching entries for a failed resolves for 10 seconds. TEST(HostCacheTest, CacheNegativeEntry) { HostCache cache(kMaxCacheEntries, base::TimeDelta::FromSeconds(0), // success entry TTL. base::TimeDelta::FromSeconds(10)); // failure entry TTL. // Start at t=0. base::TimeTicks now; const HostCache::Entry* entry1 = NULL; // Entry for foobar.com. const HostCache::Entry* entry2 = NULL; // Entry for foobar2.com. EXPECT_EQ(0U, cache.size()); // Add an entry for "foobar.com" at t=0. EXPECT_TRUE(cache.Lookup(Key("foobar.com"), base::TimeTicks()) == NULL); cache.Set(Key("foobar.com"), ERR_NAME_NOT_RESOLVED, AddressList(), now); entry1 = cache.Lookup(Key("foobar.com"), base::TimeTicks()); EXPECT_FALSE(entry1 == NULL); EXPECT_EQ(1U, cache.size()); // Advance to t=5. now += base::TimeDelta::FromSeconds(5); // Add an entry for "foobar2.com" at t=5. EXPECT_TRUE(cache.Lookup(Key("foobar2.com"), base::TimeTicks()) == NULL); cache.Set(Key("foobar2.com"), ERR_NAME_NOT_RESOLVED, AddressList(), now); entry2 = cache.Lookup(Key("foobar2.com"), base::TimeTicks()); EXPECT_FALSE(NULL == entry1); EXPECT_EQ(2U, cache.size()); // Advance to t=9 now += base::TimeDelta::FromSeconds(4); // Verify that the entries we added are still retrievable, and usable. EXPECT_EQ(entry1, cache.Lookup(Key("foobar.com"), now)); EXPECT_EQ(entry2, cache.Lookup(Key("foobar2.com"), now)); // Advance to t=10; entry1 is now expired. now += base::TimeDelta::FromSeconds(1); EXPECT_TRUE(cache.Lookup(Key("foobar.com"), now) == NULL); EXPECT_EQ(entry2, cache.Lookup(Key("foobar2.com"), now)); // Update entry1, so it is no longer expired. cache.Set(Key("foobar.com"), ERR_NAME_NOT_RESOLVED, AddressList(), now); // Re-uses existing entry storage. EXPECT_EQ(entry1, cache.Lookup(Key("foobar.com"), now)); EXPECT_EQ(2U, cache.size()); // Both entries should still be retrievable and usable. EXPECT_EQ(entry1, cache.Lookup(Key("foobar.com"), now)); EXPECT_EQ(entry2, cache.Lookup(Key("foobar2.com"), now)); // Advance to t=20; both entries are now expired. now += base::TimeDelta::FromSeconds(10); EXPECT_TRUE(cache.Lookup(Key("foobar.com"), now) == NULL); EXPECT_TRUE(cache.Lookup(Key("foobar2.com"), now) == NULL); } TEST(HostCacheTest, Compact) { // Initial entries limit is big enough to accomadate everything we add. HostCache cache(kMaxCacheEntries, kSuccessEntryTTL, kFailureEntryTTL); EXPECT_EQ(0U, cache.size()); // t=10 base::TimeTicks now = base::TimeTicks() + base::TimeDelta::FromSeconds(10); // Add five valid entries at t=10. for (int i = 0; i < 5; ++i) { std::string hostname = base::StringPrintf("valid%d", i); cache.Set(Key(hostname), OK, AddressList(), now); } EXPECT_EQ(5U, cache.size()); // Add 3 expired entries at t=0. for (int i = 0; i < 3; ++i) { std::string hostname = base::StringPrintf("expired%d", i); base::TimeTicks t = now - base::TimeDelta::FromSeconds(10); cache.Set(Key(hostname), OK, AddressList(), t); } EXPECT_EQ(8U, cache.size()); // Add 2 negative entries at t=10 for (int i = 0; i < 2; ++i) { std::string hostname = base::StringPrintf("negative%d", i); cache.Set(Key(hostname), ERR_NAME_NOT_RESOLVED, AddressList(), now); } EXPECT_EQ(10U, cache.size()); EXPECT_TRUE(ContainsKey(cache.entries_, Key("valid0"))); EXPECT_TRUE(ContainsKey(cache.entries_, Key("valid1"))); EXPECT_TRUE(ContainsKey(cache.entries_, Key("valid2"))); EXPECT_TRUE(ContainsKey(cache.entries_, Key("valid3"))); EXPECT_TRUE(ContainsKey(cache.entries_, Key("valid4"))); EXPECT_TRUE(ContainsKey(cache.entries_, Key("expired0"))); EXPECT_TRUE(ContainsKey(cache.entries_, Key("expired1"))); EXPECT_TRUE(ContainsKey(cache.entries_, Key("expired2"))); EXPECT_TRUE(ContainsKey(cache.entries_, Key("negative0"))); EXPECT_TRUE(ContainsKey(cache.entries_, Key("negative1"))); // Shrink the max constraints bound and compact. We expect the "negative" // and "expired" entries to have been dropped. cache.max_entries_ = 5; cache.Compact(now, NULL); EXPECT_EQ(5U, cache.entries_.size()); EXPECT_TRUE(ContainsKey(cache.entries_, Key("valid0"))); EXPECT_TRUE(ContainsKey(cache.entries_, Key("valid1"))); EXPECT_TRUE(ContainsKey(cache.entries_, Key("valid2"))); EXPECT_TRUE(ContainsKey(cache.entries_, Key("valid3"))); EXPECT_TRUE(ContainsKey(cache.entries_, Key("valid4"))); EXPECT_FALSE(ContainsKey(cache.entries_, Key("expired0"))); EXPECT_FALSE(ContainsKey(cache.entries_, Key("expired1"))); EXPECT_FALSE(ContainsKey(cache.entries_, Key("expired2"))); EXPECT_FALSE(ContainsKey(cache.entries_, Key("negative0"))); EXPECT_FALSE(ContainsKey(cache.entries_, Key("negative1"))); // Shrink further -- this time the compact will start dropping valid entries // to make space. cache.max_entries_ = 3; cache.Compact(now, NULL); EXPECT_EQ(3U, cache.size()); } // Add entries while the cache is at capacity, causing evictions. TEST(HostCacheTest, SetWithCompact) { HostCache cache(3, kSuccessEntryTTL, kFailureEntryTTL); // t=10 base::TimeTicks now = base::TimeTicks() + kSuccessEntryTTL; cache.Set(Key("host1"), OK, AddressList(), now); cache.Set(Key("host2"), OK, AddressList(), now); cache.Set(Key("expired"), OK, AddressList(), now - kSuccessEntryTTL); EXPECT_EQ(3U, cache.size()); // Should all be retrievable except "expired". EXPECT_FALSE(NULL == cache.Lookup(Key("host1"), now)); EXPECT_FALSE(NULL == cache.Lookup(Key("host2"), now)); EXPECT_TRUE(NULL == cache.Lookup(Key("expired"), now)); // Adding the fourth entry will cause "expired" to be evicted. cache.Set(Key("host3"), OK, AddressList(), now); EXPECT_EQ(3U, cache.size()); EXPECT_TRUE(cache.Lookup(Key("expired"), now) == NULL); EXPECT_FALSE(cache.Lookup(Key("host1"), now) == NULL); EXPECT_FALSE(cache.Lookup(Key("host2"), now) == NULL); EXPECT_FALSE(cache.Lookup(Key("host3"), now) == NULL); // Add two more entries. Something should be evicted, however "host5" // should definitely be in there (since it was last inserted). cache.Set(Key("host4"), OK, AddressList(), now); EXPECT_EQ(3U, cache.size()); cache.Set(Key("host5"), OK, AddressList(), now); EXPECT_EQ(3U, cache.size()); EXPECT_FALSE(cache.Lookup(Key("host5"), now) == NULL); } // Tests that the same hostname can be duplicated in the cache, so long as // the address family differs. TEST(HostCacheTest, AddressFamilyIsPartOfKey) { HostCache cache(kMaxCacheEntries, kSuccessEntryTTL, kFailureEntryTTL); // t=0. base::TimeTicks now; HostCache::Key key1("foobar.com", ADDRESS_FAMILY_UNSPECIFIED, 0); HostCache::Key key2("foobar.com", ADDRESS_FAMILY_IPV4, 0); const HostCache::Entry* entry1 = NULL; // Entry for key1 const HostCache::Entry* entry2 = NULL; // Entry for key2 EXPECT_EQ(0U, cache.size()); // Add an entry for ("foobar.com", UNSPECIFIED) at t=0. EXPECT_TRUE(cache.Lookup(key1, base::TimeTicks()) == NULL); cache.Set(key1, OK, AddressList(), now); entry1 = cache.Lookup(key1, base::TimeTicks()); EXPECT_FALSE(entry1 == NULL); EXPECT_EQ(1U, cache.size()); // Add an entry for ("foobar.com", IPV4_ONLY) at t=0. EXPECT_TRUE(cache.Lookup(key2, base::TimeTicks()) == NULL); cache.Set(key2, OK, AddressList(), now); entry2 = cache.Lookup(key2, base::TimeTicks()); EXPECT_FALSE(entry2 == NULL); EXPECT_EQ(2U, cache.size()); // Even though the hostnames were the same, we should have two unique // entries (because the address families differ). EXPECT_NE(entry1, entry2); } // Tests that the same hostname can be duplicated in the cache, so long as // the HostResolverFlags differ. TEST(HostCacheTest, HostResolverFlagsArePartOfKey) { HostCache cache(kMaxCacheEntries, kSuccessEntryTTL, kFailureEntryTTL); // t=0. base::TimeTicks now; HostCache::Key key1("foobar.com", ADDRESS_FAMILY_IPV4, 0); HostCache::Key key2("foobar.com", ADDRESS_FAMILY_IPV4, HOST_RESOLVER_CANONNAME); HostCache::Key key3("foobar.com", ADDRESS_FAMILY_IPV4, HOST_RESOLVER_LOOPBACK_ONLY); const HostCache::Entry* entry1 = NULL; // Entry for key1 const HostCache::Entry* entry2 = NULL; // Entry for key2 const HostCache::Entry* entry3 = NULL; // Entry for key3 EXPECT_EQ(0U, cache.size()); // Add an entry for ("foobar.com", IPV4, NONE) at t=0. EXPECT_TRUE(cache.Lookup(key1, base::TimeTicks()) == NULL); cache.Set(key1, OK, AddressList(), now); entry1 = cache.Lookup(key1, base::TimeTicks()); EXPECT_FALSE(entry1 == NULL); EXPECT_EQ(1U, cache.size()); // Add an entry for ("foobar.com", IPV4, CANONNAME) at t=0. EXPECT_TRUE(cache.Lookup(key2, base::TimeTicks()) == NULL); cache.Set(key2, OK, AddressList(), now); entry2 = cache.Lookup(key2, base::TimeTicks()); EXPECT_FALSE(entry2 == NULL); EXPECT_EQ(2U, cache.size()); // Add an entry for ("foobar.com", IPV4, LOOPBACK_ONLY) at t=0. EXPECT_TRUE(cache.Lookup(key3, base::TimeTicks()) == NULL); cache.Set(key3, OK, AddressList(), now); entry3 = cache.Lookup(key3, base::TimeTicks()); EXPECT_FALSE(entry3 == NULL); EXPECT_EQ(3U, cache.size()); // Even though the hostnames were the same, we should have two unique // entries (because the HostResolverFlags differ). EXPECT_NE(entry1, entry2); EXPECT_NE(entry1, entry3); EXPECT_NE(entry2, entry3); } TEST(HostCacheTest, NoCache) { // Disable caching. HostCache cache(0, kSuccessEntryTTL, kFailureEntryTTL); EXPECT_TRUE(cache.caching_is_disabled()); // Set t=0. base::TimeTicks now; // Lookup and Set should have no effect. EXPECT_TRUE(cache.Lookup(Key("foobar.com"), base::TimeTicks()) == NULL); cache.Set(Key("foobar.com"), OK, AddressList(), now); EXPECT_TRUE(cache.Lookup(Key("foobar.com"), base::TimeTicks()) == NULL); EXPECT_EQ(0U, cache.size()); } TEST(HostCacheTest, Clear) { HostCache cache(kMaxCacheEntries, kSuccessEntryTTL, kFailureEntryTTL); // Set t=0. base::TimeTicks now; EXPECT_EQ(0u, cache.size()); // Add three entries. cache.Set(Key("foobar1.com"), OK, AddressList(), now); cache.Set(Key("foobar2.com"), OK, AddressList(), now); cache.Set(Key("foobar3.com"), OK, AddressList(), now); EXPECT_EQ(3u, cache.size()); cache.clear(); EXPECT_EQ(0u, cache.size()); } // Tests the less than and equal operators for HostCache::Key work. TEST(HostCacheTest, KeyComparators) { struct { // Inputs. HostCache::Key key1; HostCache::Key key2; // Expectation. // -1 means key1 is less than key2 // 0 means key1 equals key2 // 1 means key1 is greater than key2 int expected_comparison; } tests[] = { { HostCache::Key("host1", ADDRESS_FAMILY_UNSPECIFIED, 0), HostCache::Key("host1", ADDRESS_FAMILY_UNSPECIFIED, 0), 0 }, { HostCache::Key("host1", ADDRESS_FAMILY_IPV4, 0), HostCache::Key("host1", ADDRESS_FAMILY_UNSPECIFIED, 0), 1 }, { HostCache::Key("host1", ADDRESS_FAMILY_UNSPECIFIED, 0), HostCache::Key("host1", ADDRESS_FAMILY_IPV4, 0), -1 }, { HostCache::Key("host1", ADDRESS_FAMILY_UNSPECIFIED, 0), HostCache::Key("host2", ADDRESS_FAMILY_UNSPECIFIED, 0), -1 }, { HostCache::Key("host1", ADDRESS_FAMILY_IPV4, 0), HostCache::Key("host2", ADDRESS_FAMILY_UNSPECIFIED, 0), 1 }, { HostCache::Key("host1", ADDRESS_FAMILY_UNSPECIFIED, 0), HostCache::Key("host2", ADDRESS_FAMILY_IPV4, 0), -1 }, { HostCache::Key("host1", ADDRESS_FAMILY_UNSPECIFIED, 0), HostCache::Key("host1", ADDRESS_FAMILY_UNSPECIFIED, HOST_RESOLVER_CANONNAME), -1 }, { HostCache::Key("host1", ADDRESS_FAMILY_UNSPECIFIED, HOST_RESOLVER_CANONNAME), HostCache::Key("host1", ADDRESS_FAMILY_UNSPECIFIED, 0), 1 }, { HostCache::Key("host1", ADDRESS_FAMILY_UNSPECIFIED, HOST_RESOLVER_CANONNAME), HostCache::Key("host2", ADDRESS_FAMILY_UNSPECIFIED, HOST_RESOLVER_CANONNAME), -1 }, }; for (size_t i = 0; i < ARRAYSIZE_UNSAFE(tests); ++i) { SCOPED_TRACE(base::StringPrintf("Test[%" PRIuS "]", i)); const HostCache::Key& key1 = tests[i].key1; const HostCache::Key& key2 = tests[i].key2; switch (tests[i].expected_comparison) { case -1: EXPECT_TRUE(key1 < key2); EXPECT_FALSE(key2 < key1); EXPECT_FALSE(key2 == key1); break; case 0: EXPECT_FALSE(key1 < key2); EXPECT_FALSE(key2 < key1); EXPECT_TRUE(key2 == key1); break; case 1: EXPECT_FALSE(key1 < key2); EXPECT_TRUE(key2 < key1); EXPECT_FALSE(key2 == key1); break; default: FAIL() << "Invalid expectation. Can be only -1, 0, 1"; } } } } // namespace net