Move caching out of MultiThreadedCertVerifier

net/cert/multi_threaded_cert_verifier.cc

 // Copyright (c) 2012 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/cert/multi_threaded_cert_verifier.h"
 
 #include <algorithm>
 #include <memory>
 #include <utility>
 
 #include "base/bind.h"
 #include "base/bind_helpers.h"
 #include "base/callback_helpers.h"
 #include "base/compiler_specific.h"
 #include "base/containers/linked_list.h"
 #include "base/memory/ptr_util.h"
 #include "base/message_loop/message_loop.h"
 #include "base/metrics/histogram_macros.h"
 #include "base/profiler/scoped_tracker.h"
 #include "base/sha1.h"
 #include "base/stl_util.h"
 #include "base/threading/worker_pool.h"
 #include "base/time/time.h"
 #include "base/trace_event/trace_event.h"
 #include "base/values.h"
 #include "net/base/hash_value.h"
 #include "net/base/net_errors.h"
-#include "net/cert/cert_trust_anchor_provider.h"
 #include "net/cert/cert_verify_proc.h"
+#include "net/cert/cert_verify_result.h"
 #include "net/cert/crl_set.h"
 #include "net/cert/x509_certificate.h"
 #include "net/cert/x509_certificate_net_log_param.h"
 #include "net/log/net_log.h"
 
 #if defined(USE_NSS_CERTS)
 #include <private/pprthred.h>  // PR_DetachThread
 #endif
 
 namespace net {
 
 ////////////////////////////////////////////////////////////////////////////
 //
 // MultiThreadedCertVerifier is a thread-unsafe object which lives, dies, and is
 // operated on a single thread, henceforth referred to as the "origin" thread.
 //
-// On a cache hit, MultiThreadedCertVerifier::Verify() returns synchronously
-// without posting a task to a worker thread.
+// When an incoming Verify() request is received, MultiThreadedCertVerifier
+// checks if there is an outstanding "job" (CertVerifierJob) in progress that
+// can service the request. If there is, the request is attached to that job.
+// Otherwise a new job is started.
 //
-// Otherwise when an incoming Verify() request is received,
-// MultiThreadedCertVerifier checks if there is an outstanding "job"
-// (CertVerifierJob) in progress that can service the request. If there is,
-// the request is attached to that job. Otherwise a new job is started.
-//
-// A job (CertVerifierJob) and is a way to de-duplicate requests that are
+// A job (CertVerifierJob) is a way to de-duplicate requests that are
 // fundamentally doing the same verification. CertVerifierJob is similarly
 // thread-unsafe and lives on the origin thread.
 //
 // To do the actual work, CertVerifierJob posts a task to WorkerPool
 // (PostTaskAndReply), and on completion notifies all requests attached to it.
 //
 // Cancellation:
 //
 // There are two ways for a request to be cancelled.
 //
 // (1) When the caller explicitly frees the Request.
 //
 //     If the request was in-flight (attached to a job), then it is detached.
 //     Note that no effort is made to reap jobs which have no attached requests.
 //     (Because the worker task isn't cancelable).
 //
 // (2) When the MultiThreadedCertVerifier is deleted.
 //
 //     This automatically cancels all outstanding requests. This is accomplished
 //     by deleting each of the jobs owned by the MultiThreadedCertVerifier,
 //     whose destructor in turn marks each attached request as canceled.
 //
 // TODO(eroman): If the MultiThreadedCertVerifier is deleted from within a
 // callback, the remaining requests in the completing job will NOT be cancelled.
 
 namespace {
 
-// The maximum number of cache entries to use for the ExpiringCache.
-const unsigned kMaxCacheEntries = 256;
-
-// The number of seconds to cache entries.
-const unsigned kTTLSecs = 1800;  // 30 minutes.
-
 std::unique_ptr<base::Value> CertVerifyResultCallback(
     const CertVerifyResult& verify_result,
     NetLogCaptureMode capture_mode) {
   std::unique_ptr<base::DictionaryValue> results(new base::DictionaryValue());
   results->SetBoolean("has_md5", verify_result.has_md5);
   results->SetBoolean("has_md2", verify_result.has_md2);
   results->SetBoolean("has_md4", verify_result.has_md4);
   results->SetBoolean("is_issued_by_known_root",
                       verify_result.is_issued_by_known_root);
   results->SetBoolean("is_issued_by_additional_trust_anchor",
@@ skipping 10 matching lines @@
            verify_result.public_key_hashes.begin();
        it != verify_result.public_key_hashes.end();
        ++it) {
     hashes->AppendString(it->ToString());
   }
   results->Set("public_key_hashes", std::move(hashes));
 
   return std::move(results);
 }
 
+// Helper structure used to keep |verify_result| alive for the lifetime of
+// the verification on the worker thread, and to communicate it back to the
+// calling thread.
+struct ResultHelper {
+  int error;
+  CertVerifyResult result;
+};
+
 }  // namespace
 
-MultiThreadedCertVerifier::CachedResult::CachedResult() : error(ERR_FAILED) {}
-
-MultiThreadedCertVerifier::CachedResult::~CachedResult() {}
-
-MultiThreadedCertVerifier::CacheValidityPeriod::CacheValidityPeriod(
-    const base::Time& now)
-    : verification_time(now),
-      expiration_time(now) {
-}
-
-MultiThreadedCertVerifier::CacheValidityPeriod::CacheValidityPeriod(
-    const base::Time& now,
-    const base::Time& expiration)
-    : verification_time(now),
-      expiration_time(expiration) {
-}
-
-bool MultiThreadedCertVerifier::CacheExpirationFunctor::operator()(
-    const CacheValidityPeriod& now,
-    const CacheValidityPeriod& expiration) const {
-  // Ensure this functor is being used for expiration only, and not strict
-  // weak ordering/sorting. |now| should only ever contain a single
-  // base::Time.
-  // Note: DCHECK_EQ is not used due to operator<< overloading requirements.
-  DCHECK(now.verification_time == now.expiration_time);
-
-  // |now| contains only a single time (verification_time), while |expiration|
-  // contains the validity range - both when the certificate was verified and
-  // when the verification result should expire.
-  //
-  // If the user receives a "not yet valid" message, and adjusts their clock
-  // foward to the correct time, this will (typically) cause
-  // now.verification_time to advance past expiration.expiration_time, thus
-  // treating the cached result as an expired entry and re-verifying.
-  // If the user receives a "expired" message, and adjusts their clock
-  // backwards to the correct time, this will cause now.verification_time to
-  // be less than expiration_verification_time, thus treating the cached
-  // result as an expired entry and re-verifying.
-  // If the user receives either of those messages, and does not adjust their
-  // clock, then the result will be (typically) be cached until the expiration
-  // TTL.
-  //
-  // This algorithm is only problematic if the user consistently keeps
-  // adjusting their clock backwards in increments smaller than the expiration
-  // TTL, in which case, cached elements continue to be added. However,
-  // because the cache has a fixed upper bound, if no entries are expired, a
-  // 'random' entry will be, thus keeping the memory constraints bounded over
-  // time.
-  return now.verification_time >= expiration.verification_time &&
-         now.verification_time < expiration.expiration_time;
-};
-
 // Represents the output and result callback of a request. The
 // CertVerifierRequest is owned by the caller that initiated the call to
 // CertVerifier::Verify().
 class CertVerifierRequest : public base::LinkNode<CertVerifierRequest>,
                             public CertVerifier::Request {
  public:
   CertVerifierRequest(CertVerifierJob* job,
                       const CompletionCallback& callback,
                       CertVerifyResult* verify_result,
                       const BoundNetLog& net_log)
@@ skipping 13 matching lines @@
 
       // Remove the request from the Job. No attempt is made to cancel the job
       // even though it may no longer have any requests attached to it. Because
       // it is running on a worker thread aborting it isn't feasible.
       RemoveFromList();
     }
   }
 
   // Copies the contents of |verify_result| to the caller's
   // CertVerifyResult and calls the callback.
-  void Post(const MultiThreadedCertVerifier::CachedResult& verify_result) {
+  void Post(const ResultHelper& verify_result) {
     DCHECK(job_);
     job_ = nullptr;
 
     net_log_.EndEvent(NetLog::TYPE_CERT_VERIFIER_REQUEST);
     *verify_result_ = verify_result.result;
 
     base::ResetAndReturn(&callback_).Run(verify_result.error);
   }
 
   void OnJobCancelled() {
@@ skipping 38 matching lines @@
 }
 
 // CertVerifierJob lives only on the verifier's origin message loop.
 class CertVerifierJob {
  public:
   CertVerifierJob(const CertVerifier::RequestParams& key,
                   NetLog* net_log,
                   MultiThreadedCertVerifier* cert_verifier)
       : key_(key),
         start_time_(base::TimeTicks::Now()),
-        wall_start_time_(base::Time::Now()),
         net_log_(BoundNetLog::Make(net_log, NetLog::SOURCE_CERT_VERIFIER_JOB)),
         cert_verifier_(cert_verifier),
         is_first_job_(false),
         weak_ptr_factory_(this) {
     net_log_.BeginEvent(NetLog::TYPE_CERT_VERIFIER_JOB,
                         base::Bind(&NetLogX509CertificateCallback,
                                    base::Unretained(key.certificate().get())));
   }
 
   // Indicates whether this was the first job started by the CertVerifier. This
   // is only used for logging certain UMA stats.
   void set_is_first_job(bool is_first_job) { is_first_job_ = is_first_job; }
 
   const CertVerifier::RequestParams& key() const { return key_; }
 
   // Posts a task to the worker pool to do the verification. Once the
   // verification has completed on the worker thread, it will call
   // OnJobCompleted() on the origin thread.
   bool Start(const scoped_refptr<CertVerifyProc>& verify_proc,
              const scoped_refptr<CRLSet>& crl_set) {
     // Owned by the bound reply callback.
-    std::unique_ptr<MultiThreadedCertVerifier::CachedResult> owned_result(
-        new MultiThreadedCertVerifier::CachedResult());
+    std::unique_ptr<ResultHelper> owned_result(new ResultHelper());
 
     // Parameter evaluation order is undefined in C++. Ensure the pointer value
     // is gotten before calling base::Passed().
     auto result = owned_result.get();
 
     return base::WorkerPool::PostTaskAndReply(
         FROM_HERE,
         base::Bind(&DoVerifyOnWorkerThread, verify_proc, key_.certificate(),
                    key_.hostname(), key_.ocsp_response(), key_.flags(), crl_set,
                    key_.additional_trust_anchors(), &result->error,
@@ skipping 32 matching lines @@
         net_log_.source().ToEventParametersCallback());
 
     requests_.Append(request.get());
     return request;
   }
 
  private:
   using RequestList = base::LinkedList<CertVerifierRequest>;
 
   // Called on completion of the Job to log UMA metrics and NetLog events.
-  void LogMetrics(
-      const MultiThreadedCertVerifier::CachedResult& verify_result) {
+  void LogMetrics(const ResultHelper& verify_result) {
     net_log_.EndEvent(
         NetLog::TYPE_CERT_VERIFIER_JOB,
         base::Bind(&CertVerifyResultCallback, verify_result.result));
     base::TimeDelta latency = base::TimeTicks::Now() - start_time_;
     UMA_HISTOGRAM_CUSTOM_TIMES("Net.CertVerifier_Job_Latency",
                                latency,
                                base::TimeDelta::FromMilliseconds(1),
                                base::TimeDelta::FromMinutes(10),
                                100);
     if (is_first_job_) {
       UMA_HISTOGRAM_CUSTOM_TIMES("Net.CertVerifier_First_Job_Latency",
                                  latency,
                                  base::TimeDelta::FromMilliseconds(1),
                                  base::TimeDelta::FromMinutes(10),
                                  100);
     }
   }
 
-  void OnJobCompleted(
-      std::unique_ptr<MultiThreadedCertVerifier::CachedResult> verify_result) {
+  void OnJobCompleted(std::unique_ptr<ResultHelper> verify_result) {
     TRACE_EVENT0("net", "CertVerifierJob::OnJobCompleted");
     std::unique_ptr<CertVerifierJob> keep_alive =
         cert_verifier_->RemoveJob(this);
 
     LogMetrics(*verify_result);
-    cert_verifier_->SaveResultToCache(key_, wall_start_time_, *verify_result);
     cert_verifier_ = nullptr;
 
     // TODO(eroman): If the cert_verifier_ is deleted from within one of the
     // callbacks, any remaining requests for that job should be cancelled. Right
     // now they will be called.
     while (!requests_.empty()) {
       base::LinkNode<CertVerifierRequest>* request = requests_.head();
       request->RemoveFromList();
       request->value()->Post(*verify_result);
     }
   }
 
   const CertVerifier::RequestParams key_;
   // The tick count of when the job started. This is used to measure how long
   // the job actually took to complete.
   const base::TimeTicks start_time_;
 
-  // The wall time of when the job started. This is to account for situations
-  // where the system clock may have changed after the Job had started, which
-  // could otherwise result in caching the wrong data.
-  const base::Time wall_start_time_;
-
   RequestList requests_;  // Non-owned.
 
   const BoundNetLog net_log_;
   MultiThreadedCertVerifier* cert_verifier_;  // Non-owned.
 
   bool is_first_job_;
   base::WeakPtrFactory<CertVerifierJob> weak_ptr_factory_;
 };
 
 MultiThreadedCertVerifier::MultiThreadedCertVerifier(
     CertVerifyProc* verify_proc)
-    : cache_(kMaxCacheEntries),
-      requests_(0),
-      cache_hits_(0),
-      inflight_joins_(0),
-      verify_proc_(verify_proc),
-      trust_anchor_provider_(NULL) {
-  CertDatabase::GetInstance()->AddObserver(this);
-}
+    : requests_(0), inflight_joins_(0), verify_proc_(verify_proc) {}
 
 MultiThreadedCertVerifier::~MultiThreadedCertVerifier() {
   STLDeleteElements(&inflight_);
-  CertDatabase::GetInstance()->RemoveObserver(this);
-}
-
-void MultiThreadedCertVerifier::SetCertTrustAnchorProvider(
-    CertTrustAnchorProvider* trust_anchor_provider) {
-  DCHECK(CalledOnValidThread());
-  trust_anchor_provider_ = trust_anchor_provider;
 }
 
 int MultiThreadedCertVerifier::Verify(const RequestParams& params,
                                       CRLSet* crl_set,
                                       CertVerifyResult* verify_result,
                                       const CompletionCallback& callback,
                                       std::unique_ptr<Request>* out_req,
                                       const BoundNetLog& net_log) {
   out_req->reset();
 
   DCHECK(CalledOnValidThread());
 
   if (callback.is_null() || !verify_result || params.hostname().empty())
     return ERR_INVALID_ARGUMENT;
 
   requests_++;
 
-  CertificateList new_trust_anchors(params.additional_trust_anchors());
-  if (trust_anchor_provider_) {
-    const CertificateList& trust_anchors =
-        trust_anchor_provider_->GetAdditionalTrustAnchors();
-    new_trust_anchors.insert(new_trust_anchors.end(), trust_anchors.begin(),
-                             trust_anchors.end());
-  }
-
-  const RequestParams key(params.certificate(), params.hostname(),
-                          params.flags(), params.ocsp_response(),
-                          new_trust_anchors);
-  const CertVerifierCache::value_type* cached_entry =
-      cache_.Get(key, CacheValidityPeriod(base::Time::Now()));
-  if (cached_entry) {
-    ++cache_hits_;
-    *verify_result = cached_entry->result;
-    return cached_entry->error;
-  }
-
-  // No cache hit. See if an identical request is currently in flight.
-  CertVerifierJob* job = FindJob(key);
+  // See if an identical request is currently in flight.
+  CertVerifierJob* job = FindJob(params);
   if (job) {
     // An identical request is in flight already. We'll just attach our
     // callback.
     inflight_joins_++;
   } else {
     // Need to make a new job.
     std::unique_ptr<CertVerifierJob> new_job(
-        new CertVerifierJob(key, net_log.net_log(), this));
+        new CertVerifierJob(params, net_log.net_log(), this));
 
     if (!new_job->Start(verify_proc_, crl_set)) {
       // TODO(wtc): log to the NetLog.
       LOG(ERROR) << "CertVerifierJob couldn't be started.";
       return ERR_INSUFFICIENT_RESOURCES;  // Just a guess.
     }
 
     job = new_job.release();
     inflight_.insert(job);
 
@@ skipping 10 matching lines @@
 bool MultiThreadedCertVerifier::SupportsOCSPStapling() {
   return verify_proc_->SupportsOCSPStapling();
 }
 
 bool MultiThreadedCertVerifier::JobComparator::operator()(
     const CertVerifierJob* job1,
     const CertVerifierJob* job2) const {
   return job1->key() < job2->key();
 }
 
-void MultiThreadedCertVerifier::SaveResultToCache(const RequestParams& key,
-                                                  const base::Time& start_time,
-                                                  const CachedResult& result) {
-  DCHECK(CalledOnValidThread());
-
-  // When caching, this uses the time that validation started as the
-  // beginning of the validity, rather than the time that it ended (aka
-  // base::Time::Now()), to account for the fact that during validation,
-  // the clock may have changed.
-  //
-  // If the clock has changed significantly, then this result will ideally
-  // be evicted and the next time the certificate is encountered, it will
-  // be revalidated.
-  //
-  // Because of this, it's possible for situations to arise where the
-  // clock was correct at the start of validation, changed to an
-  // incorrect time during validation (such as too far in the past or
-  // future), and then was reset to the correct time. If this happens,
-  // it's likely that the result will not be a valid/correct result,
-  // but will still be used from the cache because the clock was reset
-  // to the correct time after the (bad) validation result completed.
-  //
-  // However, this solution optimizes for the case where the clock is
-  // bad at the start of validation, and subsequently is corrected. In
-  // that situation, the result is also incorrect, but because the clock
-  // was corrected after validation, if the cache validity period was
-  // computed at the end of validation, it would continue to serve an
-  // invalid result for kTTLSecs.
-  cache_.Put(
-      key, result, CacheValidityPeriod(start_time),
-      CacheValidityPeriod(start_time,
-                          start_time + base::TimeDelta::FromSeconds(kTTLSecs)));
-}
-
 std::unique_ptr<CertVerifierJob> MultiThreadedCertVerifier::RemoveJob(
     CertVerifierJob* job) {
   DCHECK(CalledOnValidThread());
   bool erased_job = inflight_.erase(job) == 1;
   DCHECK(erased_job);
   return base::WrapUnique(job);
 }
 
-void MultiThreadedCertVerifier::OnCACertChanged(
-    const X509Certificate* cert) {
-  DCHECK(CalledOnValidThread());
-
-  ClearCache();
-}
-
 struct MultiThreadedCertVerifier::JobToRequestParamsComparator {
   bool operator()(const CertVerifierJob* job,
                   const CertVerifier::RequestParams& value) const {
     return job->key() < value;
   }
 };
 
 CertVerifierJob* MultiThreadedCertVerifier::FindJob(const RequestParams& key) {
   DCHECK(CalledOnValidThread());
 
   // The JobSet is kept in sorted order so items can be found using binary
   // search.
   auto it = std::lower_bound(inflight_.begin(), inflight_.end(), key,
                              JobToRequestParamsComparator());
   if (it != inflight_.end() && !(key < (*it)->key()))
     return *it;
   return nullptr;
 }
 
 }  // namespace net