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