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
14namespace net {
15
16namespace {
17const int kMaxCacheEntries = 10;
18
19const base::TimeDelta kSuccessEntryTTL = base::TimeDelta::FromSeconds(10);
20const base::TimeDelta kFailureEntryTTL = base::TimeDelta::FromSeconds(0);
21
22// Builds a key for |hostname|, defaulting the address family to unspecified.
23HostCache::Key Key(const std::string& hostname) {
24  return HostCache::Key(hostname, ADDRESS_FAMILY_UNSPECIFIED, 0);
25}
26
27}  // namespace
28
29TEST(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.
89TEST(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.
111TEST(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
171TEST(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.
238TEST(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.
274TEST(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.
309TEST(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
355TEST(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
371TEST(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.
392TEST(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