Revert 123565 - Broke the "ASAN Tests (1)" bot: http://build.chromium.org/p/chromium.memory/buildstatus?builder=ASAN%20Tests%20%281%29&number=6260

Have the HostCache and CertVerifier cache use the common ExpiringCache.

BUG=114343
TEST=net_unittests:CertVerifier*, net_unittests:HostCache*


Review URL: http://codereview.chromium.org/9436003

TBR=rsleevi@chromium.org
Review URL: https://chromiumcodereview.appspot.com/9463028

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@123571 0039d316-1c4b-4281-b951-d872f2087c98

7 files changed, 530 insertions, 165 deletions

diff --git a/chrome/browser/ui/webui/net_internals/net_internals_ui.cc b/chrome/browser/ui/webui/net_internals/net_internals_ui.cc
index 2e50a7b..3b77d2e 100644
--- a/chrome/browser/ui/webui/net_internals/net_internals_ui.cc
+++ b/chrome/browser/ui/webui/net_internals/net_internals_ui.cc
@@ -901,10 +901,12 @@ void NetInternalsMessageHandler::IOThreadImpl::OnGetHostResolverInfo(
 
   ListValue* entry_list = new ListValue();
 
-  net::HostCache::EntryMap::Iterator it(cache->entries());
-  for (; it.HasNext(); it.Advance()) {
-    const net::HostCache::Key& key = it.key();
-    const net::HostCache::Entry& entry = it.value();
+  for (net::HostCache::EntryMap::const_iterator it =
+       cache->entries().begin();
+       it != cache->entries().end();
+       ++it) {
+    const net::HostCache::Key& key = it->first;
+    const net::HostCache::Entry* entry = it->second.get();
 
     DictionaryValue* entry_dict = new DictionaryValue();
 
@@ -912,14 +914,14 @@ void NetInternalsMessageHandler::IOThreadImpl::OnGetHostResolverInfo(
     entry_dict->SetInteger("address_family",
         static_cast<int>(key.address_family));
     entry_dict->SetString("expiration",
-                          net::NetLog::TickCountToString(it.expiration()));
+                          net::NetLog::TickCountToString(entry->expiration));
 
-    if (entry.error != net::OK) {
-      entry_dict->SetInteger("error", entry.error);
+    if (entry->error != net::OK) {
+      entry_dict->SetInteger("error", entry->error);
     } else {
       // Append all of the resolved addresses.
       ListValue* address_list = new ListValue();
-      const struct addrinfo* current_address = entry.addrlist.head();
+      const struct addrinfo* current_address = entry->addrlist.head();
       while (current_address) {
         address_list->Append(Value::CreateStringValue(
             net::NetAddressToStringWithPort(current_address)));
diff --git a/net/base/cert_verifier.cc b/net/base/cert_verifier.cc
index f5f0bc2..cb4734b 100644
--- a/net/base/cert_verifier.cc
+++ b/net/base/cert_verifier.cc
@@ -74,11 +74,22 @@ const unsigned kMaxCacheEntries = 256;
 // The number of seconds for which we'll cache a cache entry.
 const unsigned kTTLSecs = 1800;  // 30 minutes.
 
+class DefaultTimeService : public CertVerifier::TimeService {
+ public:
+  // CertVerifier::TimeService methods:
+  virtual base::Time Now() { return base::Time::Now(); }
+};
+
 }  // namespace
 
-CertVerifier::CachedResult::CachedResult() : error(ERR_FAILED) {}
+CachedCertVerifyResult::CachedCertVerifyResult() : error(ERR_FAILED) {
+}
 
-CertVerifier::CachedResult::~CachedResult() {}
+CachedCertVerifyResult::~CachedCertVerifyResult() {}
+
+bool CachedCertVerifyResult::HasExpired(const base::Time current_time) const {
+  return current_time >= expiry;
+}
 
 // Represents the output and result callback of a request.
 class CertVerifierRequest {
@@ -105,7 +116,7 @@ class CertVerifierRequest {
 
   // Copies the contents of |verify_result| to the caller's
   // CertVerifyResult and calls the callback.
-  void Post(const CertVerifier::CachedResult& verify_result) {
+  void Post(const CachedCertVerifyResult& verify_result) {
     if (!callback_.is_null()) {
       net_log_.EndEvent(NetLog::TYPE_CERT_VERIFIER_REQUEST, NULL);
       *verify_result_ = verify_result.result;
@@ -278,7 +289,7 @@ class CertVerifierJob {
     requests_.push_back(request);
   }
 
-  void HandleResult(const CertVerifier::CachedResult& verify_result) {
+  void HandleResult(const CachedCertVerifyResult& verify_result) {
     worker_ = NULL;
     net_log_.EndEvent(NetLog::TYPE_CERT_VERIFIER_JOB, NULL);
     UMA_HISTOGRAM_CUSTOM_TIMES("Net.CertVerifier_Job_Latency",
@@ -290,7 +301,7 @@ class CertVerifierJob {
   }
 
  private:
-  void PostAll(const CertVerifier::CachedResult& verify_result) {
+  void PostAll(const CachedCertVerifyResult& verify_result) {
     std::vector<CertVerifierRequest*> requests;
     requests_.swap(requests);
 
@@ -318,8 +329,19 @@ class CertVerifierJob {
   const BoundNetLog net_log_;
 };
 
+
 CertVerifier::CertVerifier()
-    : cache_(kMaxCacheEntries),
+    : time_service_(new DefaultTimeService),
+      max_cache_entries_(kMaxCacheEntries),
+      requests_(0),
+      cache_hits_(0),
+      inflight_joins_(0) {
+  CertDatabase::AddObserver(this);
+}
+
+CertVerifier::CertVerifier(TimeService* time_service)
+    : time_service_(time_service),
+      max_cache_entries_(kMaxCacheEntries),
       requests_(0),
       cache_hits_(0),
       inflight_joins_(0) {
@@ -351,13 +373,18 @@ int CertVerifier::Verify(X509Certificate* cert,
 
   const RequestParams key(cert->fingerprint(), cert->ca_fingerprint(),
                           hostname, flags);
-  const CertVerifierCache::value_type* cached_entry =
-      cache_.Get(key, base::TimeTicks::Now());
-  if (cached_entry) {
-    ++cache_hits_;
-    *out_req = NULL;
-    *verify_result = cached_entry->result;
-    return cached_entry->error;
+  // First check the cache.
+  std::map<RequestParams, CachedCertVerifyResult>::iterator i;
+  i = cache_.find(key);
+  if (i != cache_.end()) {
+    if (!i->second.HasExpired(time_service_->Now())) {
+      cache_hits_++;
+      *out_req = NULL;
+      *verify_result = i->second.result;
+      return i->second.error;
+    }
+    // Cache entry has expired.
+    cache_.erase(i);
   }
 
   // No cache hit. See if an identical request is currently in flight.
@@ -400,6 +427,19 @@ void CertVerifier::CancelRequest(RequestHandle req) {
   request->Cancel();
 }
 
+void CertVerifier::ClearCache() {
+  DCHECK(CalledOnValidThread());
+
+  cache_.clear();
+  // Leaves inflight_ alone.
+}
+
+size_t CertVerifier::GetCacheSize() const {
+  DCHECK(CalledOnValidThread());
+
+  return cache_.size();
+}
+
 // HandleResult is called by CertVerifierWorker on the origin message loop.
 // It deletes CertVerifierJob.
 void CertVerifier::HandleResult(X509Certificate* cert,
@@ -409,14 +449,35 @@ void CertVerifier::HandleResult(X509Certificate* cert,
                                 const CertVerifyResult& verify_result) {
   DCHECK(CalledOnValidThread());
 
-  const RequestParams key(cert->fingerprint(), cert->ca_fingerprint(),
-                          hostname, flags);
+  const base::Time current_time(time_service_->Now());
 
-  CachedResult cached_result;
+  CachedCertVerifyResult cached_result;
   cached_result.error = error;
   cached_result.result = verify_result;
-  cache_.Put(key, cached_result, base::TimeTicks::Now(),
-             base::TimeDelta::FromSeconds(kTTLSecs));
+  uint32 ttl = kTTLSecs;
+  cached_result.expiry = current_time + base::TimeDelta::FromSeconds(ttl);
+
+  const RequestParams key(cert->fingerprint(), cert->ca_fingerprint(),
+                          hostname, flags);
+
+  DCHECK_GE(max_cache_entries_, 1u);
+  DCHECK_LE(cache_.size(), max_cache_entries_);
+  if (cache_.size() == max_cache_entries_) {
+    // Need to remove an element of the cache.
+    std::map<RequestParams, CachedCertVerifyResult>::iterator i, cur;
+    for (i = cache_.begin(); i != cache_.end(); ) {
+      cur = i++;
+      if (cur->second.HasExpired(current_time))
+        cache_.erase(cur);
+    }
+  }
+  if (cache_.size() == max_cache_entries_) {
+    // If we didn't clear out any expired entries, we just remove the first
+    // element. Crummy but simple.
+    cache_.erase(cache_.begin());
+  }
+
+  cache_.insert(std::make_pair(key, cached_result));
 
   std::map<RequestParams, CertVerifierJob*>::iterator j;
   j = inflight_.find(key);
diff --git a/net/base/cert_verifier.h b/net/base/cert_verifier.h
index fae7ec4..b937010 100644
--- a/net/base/cert_verifier.h
+++ b/net/base/cert_verifier.h
@@ -1,4 +1,4 @@
-// Copyright (c) 2012 The Chromium Authors. All rights reserved.
+// Copyright (c) 2011 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.
 
@@ -10,13 +10,12 @@
 #include <string>
 
 #include "base/basictypes.h"
-#include "base/gtest_prod_util.h"
 #include "base/memory/scoped_ptr.h"
 #include "base/threading/non_thread_safe.h"
+#include "base/time.h"
 #include "net/base/cert_database.h"
 #include "net/base/cert_verify_result.h"
 #include "net/base/completion_callback.h"
-#include "net/base/expiring_cache.h"
 #include "net/base/net_export.h"
 #include "net/base/x509_cert_types.h"
 
@@ -28,6 +27,21 @@ class CertVerifierWorker;
 class CRLSet;
 class X509Certificate;
 
+// CachedCertVerifyResult contains the result of a certificate verification.
+struct CachedCertVerifyResult {
+  CachedCertVerifyResult();
+  ~CachedCertVerifyResult();
+
+  // Returns true if |current_time| is greater than or equal to |expiry|.
+  bool HasExpired(base::Time current_time) const;
+
+  int error;  // The return value of CertVerifier::Verify.
+  CertVerifyResult result;  // The output of CertVerifier::Verify.
+
+  // The time at which the certificate verification result expires.
+  base::Time expiry;
+};
+
 // CertVerifier represents a service for verifying certificates.
 //
 // CertVerifier can handle multiple requests at a time, so when canceling a
@@ -42,8 +56,21 @@ class NET_EXPORT CertVerifier : NON_EXPORTED_BASE(public base::NonThreadSafe),
   // Opaque type used to cancel a request.
   typedef void* RequestHandle;
 
+  // CertVerifier must not call base::Time::Now() directly.  It must call
+  // time_service_->Now().  This allows unit tests to mock the current time.
+  class TimeService {
+   public:
+    virtual ~TimeService() {}
+
+    virtual base::Time Now() = 0;
+  };
+
   CertVerifier();
 
+  // Used by unit tests to mock the current time.  Takes ownership of
+  // |time_service|.
+  explicit CertVerifier(TimeService* time_service);
+
   // When the verifier is destroyed, all certificate verifications requests are
   // canceled, and their completion callbacks will not be called.
   virtual ~CertVerifier();
@@ -89,15 +116,19 @@ class NET_EXPORT CertVerifier : NON_EXPORTED_BASE(public base::NonThreadSafe),
   // After a request is canceled, its completion callback will not be called.
   void CancelRequest(RequestHandle req);
 
+  // Clears the verification result cache.
+  void ClearCache();
+
+  size_t GetCacheSize() const;
+
+  void set_max_cache_entries(size_t max) { max_cache_entries_ = max; }
+
+  uint64 requests() const { return requests_; }
+  uint64 cache_hits() const { return cache_hits_; }
+  uint64 inflight_joins() const { return inflight_joins_; }
+
  private:
   friend class CertVerifierWorker;  // Calls HandleResult.
-  friend class CertVerifierRequest;
-  friend class CertVerifierJob;
-  FRIEND_TEST_ALL_PREFIXES(CertVerifierTest, CacheHit);
-  FRIEND_TEST_ALL_PREFIXES(CertVerifierTest, DifferentCACerts);
-  FRIEND_TEST_ALL_PREFIXES(CertVerifierTest, InflightJoin);
-  FRIEND_TEST_ALL_PREFIXES(CertVerifierTest, CancelRequest);
-  FRIEND_TEST_ALL_PREFIXES(CertVerifierTest, RequestParamsComparators);
 
   // Input parameters of a certificate verification request.
   struct RequestParams {
@@ -110,6 +141,18 @@ class NET_EXPORT CertVerifier : NON_EXPORTED_BASE(public base::NonThreadSafe),
           hostname(hostname_arg),
           flags(flags_arg) {}
 
+    bool operator==(const RequestParams& other) const {
+      // |flags| is compared before |cert_fingerprint|, |ca_fingerprint|, and
+      // |hostname| under assumption that integer comparisons are faster than
+      // memory and string comparisons.
+      return (flags == other.flags &&
+              memcmp(cert_fingerprint.data, other.cert_fingerprint.data,
+                     sizeof(cert_fingerprint.data)) == 0 &&
+              memcmp(ca_fingerprint.data, other.ca_fingerprint.data,
+                     sizeof(ca_fingerprint.data)) == 0 &&
+              hostname == other.hostname);
+    }
+
     bool operator<(const RequestParams& other) const {
       // |flags| is compared before |cert_fingerprint|, |ca_fingerprint|, and
       // |hostname| under assumption that integer comparisons are faster than
@@ -133,15 +176,6 @@ class NET_EXPORT CertVerifier : NON_EXPORTED_BASE(public base::NonThreadSafe),
     int flags;
   };
 
-  // CachedResult contains the result of a certificate verification.
-  struct CachedResult {
-    CachedResult();
-    ~CachedResult();
-
-    int error;  // The return value of CertVerifier::Verify.
-    CertVerifyResult result;  // The output of CertVerifier::Verify.
-  };
-
   void HandleResult(X509Certificate* cert,
                     const std::string& hostname,
                     int flags,
@@ -151,21 +185,19 @@ class NET_EXPORT CertVerifier : NON_EXPORTED_BASE(public base::NonThreadSafe),
   // CertDatabase::Observer methods:
   virtual void OnCertTrustChanged(const X509Certificate* cert) OVERRIDE;
 
-  // For unit testing.
-  void ClearCache() { cache_.Clear(); }
-  size_t GetCacheSize() const { return cache_.size(); }
-  uint64 cache_hits() const { return cache_hits_; }
-  uint64 requests() const { return requests_; }
-  uint64 inflight_joins() const { return inflight_joins_; }
-
-  // cache_ maps from a request to a cached result.
-  typedef ExpiringCache<RequestParams, CachedResult> CertVerifierCache;
-  CertVerifierCache cache_;
+  // cache_ maps from a request to a cached result. The cached result may
+  // have expired and the size of |cache_| must be <= max_cache_entries_.
+  std::map<RequestParams, CachedCertVerifyResult> cache_;
 
   // inflight_ maps from a request to an active verification which is taking
   // place.
   std::map<RequestParams, CertVerifierJob*> inflight_;
 
+  scoped_ptr<TimeService> time_service_;
+
+  // The number of CachedCertVerifyResult objects that we'll cache.
+  size_t max_cache_entries_;
+
   uint64 requests_;
   uint64 cache_hits_;
   uint64 inflight_joins_;
diff --git a/net/base/cert_verifier_unittest.cc b/net/base/cert_verifier_unittest.cc
index de3103d..f4c7dcd 100644
--- a/net/base/cert_verifier_unittest.cc
+++ b/net/base/cert_verifier_unittest.cc
@@ -1,4 +1,4 @@
-// Copyright (c) 2012 The Chromium Authors. All rights reserved.
+// Copyright (c) 2011 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.
 
@@ -6,7 +6,6 @@
 
 #include "base/bind.h"
 #include "base/file_path.h"
-#include "base/format_macros.h"
 #include "base/stringprintf.h"
 #include "net/base/cert_test_util.h"
 #include "net/base/net_errors.h"
@@ -19,15 +18,27 @@ namespace net {
 
 namespace {
 
+class TestTimeService : public CertVerifier::TimeService {
+ public:
+  // CertVerifier::TimeService methods:
+  virtual base::Time Now() { return current_time_; }
+
+  void set_current_time(base::Time now) { current_time_ = now; }
+
+ private:
+  base::Time current_time_;
+};
+
 void FailTest(int /* result */) {
   FAIL();
 }
 
-}  // namespace;
-
-// Tests a cache hit, which should result in synchronous completion.
+// Tests a cache hit, which should results in synchronous completion.
 TEST(CertVerifierTest, CacheHit) {
-  CertVerifier verifier;
+  TestTimeService* time_service = new TestTimeService;
+  base::Time current_time = base::Time::Now();
+  time_service->set_current_time(current_time);
+  CertVerifier verifier(time_service);
 
   FilePath certs_dir = GetTestCertsDirectory();
   scoped_refptr<X509Certificate> test_cert(
@@ -66,7 +77,10 @@ TEST(CertVerifierTest, CacheHit) {
 // certificates.  These should be treated as different certificate chains even
 // though the two X509Certificate objects contain the same server certificate.
 TEST(CertVerifierTest, DifferentCACerts) {
-  CertVerifier verifier;
+  TestTimeService* time_service = new TestTimeService;
+  base::Time current_time = base::Time::Now();
+  time_service->set_current_time(current_time);
+  CertVerifier verifier(time_service);
 
   FilePath certs_dir = GetTestCertsDirectory();
 
@@ -126,7 +140,10 @@ TEST(CertVerifierTest, DifferentCACerts) {
 
 // Tests an inflight join.
 TEST(CertVerifierTest, InflightJoin) {
-  CertVerifier verifier;
+  TestTimeService* time_service = new TestTimeService;
+  base::Time current_time = base::Time::Now();
+  time_service->set_current_time(current_time);
+  CertVerifier verifier(time_service);
 
   FilePath certs_dir = GetTestCertsDirectory();
   scoped_refptr<X509Certificate> test_cert(
@@ -159,6 +176,127 @@ TEST(CertVerifierTest, InflightJoin) {
   ASSERT_EQ(1u, verifier.inflight_joins());
 }
 
+// Tests cache entry expiration.
+TEST(CertVerifierTest, ExpiredCacheEntry) {
+  TestTimeService* time_service = new TestTimeService;
+  base::Time current_time = base::Time::Now();
+  time_service->set_current_time(current_time);
+  CertVerifier verifier(time_service);
+
+  FilePath certs_dir = GetTestCertsDirectory();
+  scoped_refptr<X509Certificate> test_cert(
+      ImportCertFromFile(certs_dir, "ok_cert.pem"));
+  ASSERT_NE(static_cast<X509Certificate*>(NULL), test_cert);
+
+  int error;
+  CertVerifyResult verify_result;
+  TestCompletionCallback callback;
+  CertVerifier::RequestHandle request_handle;
+
+  error = verifier.Verify(
+      test_cert, "www.example.com", 0, NULL, &verify_result,
+      callback.callback(), &request_handle, BoundNetLog());
+  ASSERT_EQ(ERR_IO_PENDING, error);
+  ASSERT_TRUE(request_handle != NULL);
+  error = callback.WaitForResult();
+  ASSERT_TRUE(IsCertificateError(error));
+  ASSERT_EQ(1u, verifier.requests());
+  ASSERT_EQ(0u, verifier.cache_hits());
+  ASSERT_EQ(0u, verifier.inflight_joins());
+
+  // Before expiration, should have a cache hit.
+  error = verifier.Verify(
+      test_cert, "www.example.com", 0, NULL, &verify_result,
+      callback.callback(), &request_handle, BoundNetLog());
+  // Synchronous completion.
+  ASSERT_NE(ERR_IO_PENDING, error);
+  ASSERT_TRUE(IsCertificateError(error));
+  ASSERT_TRUE(request_handle == NULL);
+  ASSERT_EQ(2u, verifier.requests());
+  ASSERT_EQ(1u, verifier.cache_hits());
+  ASSERT_EQ(0u, verifier.inflight_joins());
+
+  // After expiration, should not have a cache hit.
+  ASSERT_EQ(1u, verifier.GetCacheSize());
+  current_time += base::TimeDelta::FromMinutes(60);
+  time_service->set_current_time(current_time);
+  error = verifier.Verify(
+      test_cert, "www.example.com", 0, NULL, &verify_result,
+      callback.callback(), &request_handle, BoundNetLog());
+  ASSERT_EQ(ERR_IO_PENDING, error);
+  ASSERT_TRUE(request_handle != NULL);
+  ASSERT_EQ(0u, verifier.GetCacheSize());
+  error = callback.WaitForResult();
+  ASSERT_TRUE(IsCertificateError(error));
+  ASSERT_EQ(3u, verifier.requests());
+  ASSERT_EQ(1u, verifier.cache_hits());
+  ASSERT_EQ(0u, verifier.inflight_joins());
+}
+
+// Tests a full cache.
+TEST(CertVerifierTest, FullCache) {
+  TestTimeService* time_service = new TestTimeService;
+  base::Time current_time = base::Time::Now();
+  time_service->set_current_time(current_time);
+  CertVerifier verifier(time_service);
+
+  // Reduce the maximum cache size in this test so that we can fill up the
+  // cache quickly.
+  const unsigned kCacheSize = 5;
+  verifier.set_max_cache_entries(kCacheSize);
+
+  FilePath certs_dir = GetTestCertsDirectory();
+  scoped_refptr<X509Certificate> test_cert(
+      ImportCertFromFile(certs_dir, "ok_cert.pem"));
+  ASSERT_NE(static_cast<X509Certificate*>(NULL), test_cert);
+
+  int error;
+  CertVerifyResult verify_result;
+  TestCompletionCallback callback;
+  CertVerifier::RequestHandle request_handle;
+
+  error = verifier.Verify(
+      test_cert, "www.example.com", 0, NULL, &verify_result,
+      callback.callback(), &request_handle, BoundNetLog());
+  ASSERT_EQ(ERR_IO_PENDING, error);
+  ASSERT_TRUE(request_handle != NULL);
+  error = callback.WaitForResult();
+  ASSERT_TRUE(IsCertificateError(error));
+  ASSERT_EQ(1u, verifier.requests());
+  ASSERT_EQ(0u, verifier.cache_hits());
+  ASSERT_EQ(0u, verifier.inflight_joins());
+
+  for (unsigned i = 0; i < kCacheSize; i++) {
+    std::string hostname = base::StringPrintf("www%d.example.com", i + 1);
+    error = verifier.Verify(
+        test_cert, hostname, 0, NULL, &verify_result,
+        callback.callback(), &request_handle, BoundNetLog());
+    ASSERT_EQ(ERR_IO_PENDING, error);
+    ASSERT_TRUE(request_handle != NULL);
+    error = callback.WaitForResult();
+    ASSERT_TRUE(IsCertificateError(error));
+  }
+  ASSERT_EQ(kCacheSize + 1, verifier.requests());
+  ASSERT_EQ(0u, verifier.cache_hits());
+  ASSERT_EQ(0u, verifier.inflight_joins());
+
+  ASSERT_EQ(kCacheSize, verifier.GetCacheSize());
+  current_time += base::TimeDelta::FromMinutes(60);
+  time_service->set_current_time(current_time);
+  error = verifier.Verify(
+      test_cert, "www999.example.com", 0, NULL, &verify_result,
+      callback.callback(), &request_handle, BoundNetLog());
+  ASSERT_EQ(ERR_IO_PENDING, error);
+  ASSERT_TRUE(request_handle != NULL);
+  ASSERT_EQ(kCacheSize, verifier.GetCacheSize());
+  error = callback.WaitForResult();
+  ASSERT_EQ(1u, verifier.GetCacheSize());
+  ASSERT_TRUE(IsCertificateError(error));
+  ASSERT_EQ(kCacheSize + 2, verifier.requests());
+  ASSERT_EQ(0u, verifier.cache_hits());
+  ASSERT_EQ(0u, verifier.inflight_joins());
+}
+
 // Tests that the callback of a canceled request is never made.
 TEST(CertVerifierTest, CancelRequest) {
   CertVerifier verifier;
@@ -216,78 +354,6 @@ TEST(CertVerifierTest, CancelRequestThenQuit) {
   // Destroy |verifier| by going out of scope.
 }
 
-TEST(CertVerifierTest, RequestParamsComparators) {
-  SHA1Fingerprint a_key;
-  memset(a_key.data, 'a', sizeof(a_key.data));
-
-  SHA1Fingerprint z_key;
-  memset(z_key.data, 'z', sizeof(z_key.data));
-
-  struct {
-    // Keys to test
-    CertVerifier::RequestParams key1;
-    CertVerifier::RequestParams key2;
-
-    // Expectation:
-    // -1 means key1 is less than key2
-    //  0 means key1 equals key2
-    //  1 means key1 is greater than key2
-    int expected_result;
-  } tests[] = {
-    {  // Test for basic equivalence.
-      CertVerifier::RequestParams(a_key, a_key, "www.example.test", 0),
-      CertVerifier::RequestParams(a_key, a_key, "www.example.test", 0),
-      0,
-    },
-    {  // Test that different certificates but with the same CA and for
-       // the same host are different validation keys.
-      CertVerifier::RequestParams(a_key, a_key, "www.example.test", 0),
-      CertVerifier::RequestParams(z_key, a_key, "www.example.test", 0),
-      -1,
-    },
-    {  // Test that the same EE certificate for the same host, but with
-       // different chains are different validation keys.
-      CertVerifier::RequestParams(a_key, z_key, "www.example.test", 0),
-      CertVerifier::RequestParams(a_key, a_key, "www.example.test", 0),
-      1,
-    },
-    {  // The same certificate, with the same chain, but for different
-       // hosts are different validation keys.
-      CertVerifier::RequestParams(a_key, a_key, "www1.example.test", 0),
-      CertVerifier::RequestParams(a_key, a_key, "www2.example.test", 0),
-      -1,
-    },
-    {  // The same certificate, chain, and host, but with different flags
-       // are different validation keys.
-      CertVerifier::RequestParams(a_key, a_key, "www.example.test",
-                                  X509Certificate::VERIFY_EV_CERT),
-      CertVerifier::RequestParams(a_key, a_key, "www.example.test", 0),
-      1,
-    }
-  };
-  for (size_t i = 0; i < ARRAYSIZE_UNSAFE(tests); ++i) {
-    SCOPED_TRACE(base::StringPrintf("Test[%" PRIuS "]", i));
-
-    const CertVerifier::RequestParams& key1 = tests[i].key1;
-    const CertVerifier::RequestParams& key2 = tests[i].key2;
-
-    switch (tests[i].expected_result) {
-      case -1:
-        EXPECT_TRUE(key1 < key2);
-        EXPECT_FALSE(key2 < key1);
-        break;
-      case 0:
-        EXPECT_FALSE(key1 < key2);
-        EXPECT_FALSE(key2 < key1);
-        break;
-      case 1:
-        EXPECT_FALSE(key1 < key2);
-        EXPECT_TRUE(key2 < key1);
-        break;
-      default:
-        FAIL() << "Invalid expectation. Can be only -1, 0, 1";
-    }
-  }
-}
+}  // namespace
 
 }  // namespace net
diff --git a/net/base/host_cache.cc b/net/base/host_cache.cc
index 352513b..731e5f5 100644
--- a/net/base/host_cache.cc
+++ b/net/base/host_cache.cc
@@ -11,9 +11,10 @@ namespace net {
 
 //-----------------------------------------------------------------------------
 
-HostCache::Entry::Entry(int error, const AddressList& addrlist)
-    : error(error),
-      addrlist(addrlist) {
+HostCache::Entry::Entry(int error,
+                        const AddressList& addrlist,
+                        base::TimeTicks expiration)
+    : error(error), addrlist(addrlist), expiration(expiration) {
 }
 
 HostCache::Entry::~Entry() {
@@ -22,36 +23,63 @@ HostCache::Entry::~Entry() {
 //-----------------------------------------------------------------------------
 
 HostCache::HostCache(size_t max_entries)
-    : entries_(max_entries) {
+    : max_entries_(max_entries) {
 }
 
 HostCache::~HostCache() {
 }
 
 const HostCache::Entry* HostCache::Lookup(const Key& key,
-                                          base::TimeTicks now) {
+                                          base::TimeTicks now) const {
   DCHECK(CalledOnValidThread());
   if (caching_is_disabled())
     return NULL;
 
-  return entries_.Get(key, now);
+  EntryMap::const_iterator it = entries_.find(key);
+  if (it == entries_.end())
+    return NULL;  // Not found.
+
+  Entry* entry = it->second.get();
+  if (CanUseEntry(entry, now))
+    return entry;
+
+  return NULL;
 }
 
-void HostCache::Set(const Key& key,
-                    int error,
-                    const AddressList& addrlist,
-                    base::TimeTicks now,
-                    base::TimeDelta ttl) {
+HostCache::Entry* HostCache::Set(const Key& key,
+                                 int error,
+                                 const AddressList& addrlist,
+                                 base::TimeTicks now,
+                                 base::TimeDelta ttl) {
   DCHECK(CalledOnValidThread());
   if (caching_is_disabled())
-    return;
+    return NULL;
 
-  entries_.Put(key, Entry(error, addrlist), now, ttl);
+  base::TimeTicks expiration = now + ttl;
+
+  scoped_refptr<Entry>& entry = entries_[key];
+  if (!entry) {
+    // Entry didn't exist, creating one now.
+    Entry* ptr = new Entry(error, addrlist, expiration);
+    entry = ptr;
+
+    // Compact the cache if we grew it beyond limit -- exclude |entry| from
+    // being pruned though!
+    if (entries_.size() > max_entries_)
+      Compact(now, ptr);
+    return ptr;
+  } else {
+    // Update an existing cache entry.
+    entry->error = error;
+    entry->addrlist = addrlist;
+    entry->expiration = expiration;
+    return entry.get();
+  }
 }
 
 void HostCache::clear() {
   DCHECK(CalledOnValidThread());
-  entries_.Clear();
+  entries_.clear();
 }
 
 size_t HostCache::size() const {
@@ -61,7 +89,7 @@ size_t HostCache::size() const {
 
 size_t HostCache::max_entries() const {
   DCHECK(CalledOnValidThread());
-  return entries_.max_entries();
+  return max_entries_;
 }
 
 // Note that this map may contain expired entries.
@@ -71,9 +99,46 @@ const HostCache::EntryMap& HostCache::entries() const {
 }
 
 // static
+bool HostCache::CanUseEntry(const Entry* entry, const base::TimeTicks now) {
+  return entry->expiration > now;
+}
+
+// static
 HostCache* HostCache::CreateDefaultCache() {
   static const size_t kMaxHostCacheEntries = 100;
   return new HostCache(kMaxHostCacheEntries);
 }
 
+void HostCache::Compact(base::TimeTicks now, const Entry* pinned_entry) {
+  // Clear out expired entries.
+  for (EntryMap::iterator it = entries_.begin(); it != entries_.end(); ) {
+    Entry* entry = (it->second).get();
+    if (entry != pinned_entry && !CanUseEntry(entry, now)) {
+      entries_.erase(it++);
+    } else {
+      ++it;
+    }
+  }
+
+  if (entries_.size() <= max_entries_)
+    return;
+
+  // If we still have too many entries, start removing unexpired entries
+  // at random.
+  // TODO(eroman): this eviction policy could be better (access count FIFO
+  // or whatever).
+  for (EntryMap::iterator it = entries_.begin();
+       it != entries_.end() && entries_.size() > max_entries_; ) {
+    Entry* entry = (it->second).get();
+    if (entry != pinned_entry) {
+      entries_.erase(it++);
+    } else {
+      ++it;
+    }
+  }
+
+  if (entries_.size() > max_entries_)
+    DLOG(WARNING) << "Still above max entries limit";
+}
+
 }  // namespace net
diff --git a/net/base/host_cache.h b/net/base/host_cache.h
index a47a4ff..d7c1590 100644
--- a/net/base/host_cache.h
+++ b/net/base/host_cache.h
@@ -6,14 +6,15 @@
 #define NET_BASE_HOST_CACHE_H_
 #pragma once
 
+#include <map>
 #include <string>
 
 #include "base/gtest_prod_util.h"
+#include "base/memory/ref_counted.h"
 #include "base/threading/non_thread_safe.h"
 #include "base/time.h"
 #include "net/base/address_family.h"
 #include "net/base/address_list.h"
-#include "net/base/expiring_cache.h"
 #include "net/base/net_export.h"
 
 namespace net {
@@ -22,13 +23,20 @@ namespace net {
 class NET_EXPORT HostCache : NON_EXPORTED_BASE(public base::NonThreadSafe) {
  public:
   // Stores the latest address list that was looked up for a hostname.
-  struct Entry {
-    Entry(int error, const AddressList& addrlist);
-    ~Entry();
+  struct Entry : public base::RefCounted<Entry> {
+    Entry(int error, const AddressList& addrlist, base::TimeTicks expiration);
 
     // The resolve results for this entry.
     int error;
     AddressList addrlist;
+
+    // The time when this entry expires.
+    base::TimeTicks expiration;
+
+   private:
+    friend class base::RefCounted<Entry>;
+
+    ~Entry();
   };
 
   struct Key {
@@ -38,6 +46,15 @@ class NET_EXPORT HostCache : NON_EXPORTED_BASE(public base::NonThreadSafe) {
           address_family(address_family),
           host_resolver_flags(host_resolver_flags) {}
 
+    bool operator==(const Key& other) const {
+      // |address_family| and |host_resolver_flags| are compared before
+      // |hostname| under assumption that integer comparisons are faster than
+      // string comparisons.
+      return (other.address_family == address_family &&
+              other.host_resolver_flags == host_resolver_flags &&
+              other.hostname == hostname);
+    }
+
     bool operator<(const Key& other) const {
       // |address_family| and |host_resolver_flags| are compared before
       // |hostname| under assumption that integer comparisons are faster than
@@ -54,7 +71,7 @@ class NET_EXPORT HostCache : NON_EXPORTED_BASE(public base::NonThreadSafe) {
     HostResolverFlags host_resolver_flags;
   };
 
-  typedef ExpiringCache<Key, Entry> EntryMap;
+  typedef std::map<Key, scoped_refptr<Entry> > EntryMap;
 
   // Constructs a HostCache that stores up to |max_entries|.
   explicit HostCache(size_t max_entries);
@@ -63,16 +80,17 @@ class NET_EXPORT HostCache : NON_EXPORTED_BASE(public base::NonThreadSafe) {
 
   // Returns a pointer to the entry for |key|, which is valid at time
   // |now|. If there is no such entry, returns NULL.
-  const Entry* Lookup(const Key& key, base::TimeTicks now);
+  const Entry* Lookup(const Key& key, base::TimeTicks now) const;
 
-  // Overwrites or creates an entry for |key|.
+  // Overwrites or creates an entry for |key|. Returns the pointer to the
+  // entry, or NULL on failure (fails if caching is disabled).
   // (|error|, |addrlist|) is the value to set, |now| is the current time
   // |ttl| is the "time to live".
-  void Set(const Key& key,
-           int error,
-           const AddressList& addrlist,
-           base::TimeTicks now,
-           base::TimeDelta ttl);
+  Entry* Set(const Key& key,
+             int error,
+             const AddressList& addrlist,
+             base::TimeTicks now,
+             base::TimeDelta ttl);
 
   // Empties the cache
   void clear();
@@ -83,19 +101,31 @@ class NET_EXPORT HostCache : NON_EXPORTED_BASE(public base::NonThreadSafe) {
   // Following are used by net_internals UI.
   size_t max_entries() const;
 
+  // Note that this map may contain expired entries.
   const EntryMap& entries() const;
 
   // Creates a default cache.
   static HostCache* CreateDefaultCache();
 
  private:
+  FRIEND_TEST_ALL_PREFIXES(HostCacheTest, Compact);
   FRIEND_TEST_ALL_PREFIXES(HostCacheTest, NoCache);
 
+  // Returns true if this cache entry's result is valid at time |now|.
+  static bool CanUseEntry(const Entry* entry, const base::TimeTicks now);
+
+  // Prunes entries from the cache to bring it below max entry bound. Entries
+  // matching |pinned_entry| will NOT be pruned.
+  void Compact(base::TimeTicks now, const Entry* pinned_entry);
+
   // Returns true if this HostCache can contain no entries.
   bool caching_is_disabled() const {
-    return entries_.max_entries() == 0;
+    return max_entries_ == 0;
   }
 
+  // Bound on total size of the cache.
+  size_t max_entries_;
+
   // Map from hostname (presumably in lowercase canonicalized format) to
   // a resolved result entry.
   EntryMap entries_;
diff --git a/net/base/host_cache_unittest.cc b/net/base/host_cache_unittest.cc
index db9c00f..f00364d 100644
--- a/net/base/host_cache_unittest.cc
+++ b/net/base/host_cache_unittest.cc
@@ -176,6 +176,112 @@ TEST(HostCacheTest, CacheNegativeEntry) {
   EXPECT_TRUE(cache.Lookup(Key("foobar2.com"), now) == NULL);
 }
 
+TEST(HostCacheTest, Compact) {
+  // Initial entries limit is big enough to accomadate everything we add.
+  const base::TimeDelta kSuccessEntryTTL = base::TimeDelta::FromSeconds(10);
+  const base::TimeDelta kFailureEntryTTL = base::TimeDelta::FromSeconds(0);
+  HostCache cache(kMaxCacheEntries);
+
+  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, kSuccessEntryTTL);
+  }
+  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, kSuccessEntryTTL);
+  }
+  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, kFailureEntryTTL);
+  }
+  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) {
+  const base::TimeDelta kTTL = base::TimeDelta::FromSeconds(10);
+
+  HostCache cache(3);
+
+  // t=10
+  base::TimeTicks now = base::TimeTicks() + kTTL;
+
+  cache.Set(Key("host1"), OK, AddressList(), now, kTTL);
+  cache.Set(Key("host2"), OK, AddressList(), now, kTTL);
+  cache.Set(Key("expired"), OK, AddressList(), now, kTTL - kTTL);
+
+  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, kTTL);
+  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, kTTL);
+  EXPECT_EQ(3U, cache.size());
+  cache.Set(Key("host5"), OK, AddressList(), now, kTTL);
+  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) {
@@ -346,7 +452,7 @@ TEST(HostCacheTest, KeyComparators) {
       HostCache::Key("host2", ADDRESS_FAMILY_IPV4, 0),
       -1
     },
-    {
+        {
       HostCache::Key("host1", ADDRESS_FAMILY_UNSPECIFIED, 0),
       HostCache::Key("host1", ADDRESS_FAMILY_UNSPECIFIED,
                      HOST_RESOLVER_CANONNAME),
@@ -377,14 +483,17 @@ TEST(HostCacheTest, KeyComparators) {
       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";