Cache certificate verification results in memory.

R=agl
BUG=63357
TEST=none
Review URL: http://codereview.chromium.org/5386001

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

1 files changed, 414 insertions, 91 deletions

diff --git a/net/base/cert_verifier.cc b/net/base/cert_verifier.cc
index ae910b4..4b3d904 100644
--- a/net/base/cert_verifier.cc
+++ b/net/base/cert_verifier.cc
@@ -1,45 +1,158 @@
-// Copyright (c) 2008 The Chromium Authors. All rights reserved.
+// Copyright (c) 2010 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "net/base/cert_verifier.h"
 
-#if defined(USE_NSS)
-#include <private/pprthred.h>  // PR_DetatchThread
-#endif
-
+#include "base/compiler_specific.h"
 #include "base/lock.h"
-#include "base/message_loop_proxy.h"
-#include "base/scoped_ptr.h"
+#include "base/message_loop.h"
+#include "base/stl_util-inl.h"
 #include "base/worker_pool.h"
-#include "net/base/cert_verify_result.h"
 #include "net/base/net_errors.h"
 #include "net/base/x509_certificate.h"
 
+#if defined(USE_NSS)
+#include <private/pprthred.h>  // PR_DetachThread
+#endif
+
 namespace net {
 
-class CertVerifier::Request :
-    public base::RefCountedThreadSafe<CertVerifier::Request> {
+////////////////////////////////////////////////////////////////////////////
+
+// Life of a request:
+//
+// CertVerifier CertVerifierJob       CertVerifierWorker          Request
+//      |                       (origin loop)    (worker loop)
+//      |
+//   Verify()
+//      |---->-------------------<creates>
+//      |
+//      |---->----<creates>
+//      |
+//      |---->---------------------------------------------------<creates>
+//      |
+//      |---->--------------------Start
+//      |                           |
+//      |                        PostTask
+//      |
+//      |                                     <starts verifying>
+//      |---->-----AddRequest                         |
+//                                                    |
+//                                                    |
+//                                                    |
+//                                                  Finish
+//                                                    |
+//                                                 PostTask
+//
+//                                   |
+//                                DoReply
+//      |----<-----------------------|
+//  HandleResult
+//      |
+//      |---->-----HandleResult
+//                      |
+//                      |------>-----------------------------------Post
+//
+//
+//
+// On a cache hit, CertVerifier::Verify() returns synchronously without
+// posting a task to a worker thread.
+
+// The number of CachedCertVerifyResult objects that we'll cache.
+static const unsigned kMaxCacheEntries = 256;
+
+// The number of seconds for which we'll cache a cache entry.
+static const unsigned kTTLSecs = 1800;  // 30 minutes.
+
+namespace {
+
+class DefaultTimeService : public CertVerifier::TimeService {
+ public:
+  // CertVerifier::TimeService methods:
+  virtual base::Time Now() { return base::Time::Now(); }
+};
+
+}  // namespace
+
+CachedCertVerifyResult::CachedCertVerifyResult() : error(ERR_FAILED) {
+}
+
+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 {
  public:
-  Request(CertVerifier* verifier,
-          X509Certificate* cert,
-          const std::string& hostname,
-          int flags,
-          CertVerifyResult* verify_result,
-          CompletionCallback* callback)
+  CertVerifierRequest(CompletionCallback* callback,
+                      CertVerifyResult* verify_result)
+      : callback_(callback),
+        verify_result_(verify_result) {
+  }
+
+  // Ensures that the result callback will never be made.
+  void Cancel() {
+    callback_ = NULL;
+    verify_result_ = NULL;
+  }
+
+  // Copies the contents of |verify_result| to the caller's
+  // CertVerifyResult and calls the callback.
+  void Post(const CachedCertVerifyResult& verify_result) {
+    if (callback_) {
+      *verify_result_ = verify_result.result;
+      callback_->Run(verify_result.error);
+    }
+    delete this;
+  }
+
+ private:
+  CompletionCallback* callback_;
+  CertVerifyResult* verify_result_;
+};
+
+
+// CertVerifierWorker runs on a worker thread and takes care of the blocking
+// process of performing the certificate verification.  Deletes itself
+// eventually if Start() succeeds.
+class CertVerifierWorker {
+ public:
+  CertVerifierWorker(X509Certificate* cert,
+                     const std::string& hostname,
+                     int flags,
+                     CertVerifier* cert_verifier)
       : cert_(cert),
         hostname_(hostname),
         flags_(flags),
-        verifier_(verifier),
-        verify_result_(verify_result),
-        callback_(callback),
-        origin_loop_proxy_(base::MessageLoopProxy::CreateForCurrentThread()),
-        error_(OK) {
+        origin_loop_(MessageLoop::current()),
+        cert_verifier_(cert_verifier),
+        canceled_(false),
+        error_(ERR_FAILED) {
+  }
+
+  bool Start() {
+    DCHECK_EQ(MessageLoop::current(), origin_loop_);
+
+    return WorkerPool::PostTask(
+               FROM_HERE, NewRunnableMethod(this, &CertVerifierWorker::Run),
+               true /* task is slow */);
   }
 
-  void DoVerify() {
-    // Running on the worker thread
-    error_ = cert_->Verify(hostname_, flags_, &result_);
+  // Cancel is called from the origin loop when the CertVerifier is getting
+  // deleted.
+  void Cancel() {
+    DCHECK_EQ(MessageLoop::current(), origin_loop_);
+    AutoLock locked(lock_);
+    canceled_ = true;
+  }
+
+ private:
+  void Run() {
+    // Runs on a worker thread.
+    error_ = cert_->Verify(hostname_, flags_, &verify_result_);
 #if defined(USE_NSS)
     // Detach the thread from NSPR.
     // Calling NSS functions attaches the thread to NSPR, which stores
@@ -50,109 +163,319 @@ class CertVerifier::Request :
     // destructors run.
     PR_DetachThread();
 #endif
+    Finish();
+  }
 
-    scoped_ptr<Task> reply(NewRunnableMethod(this, &Request::DoCallback));
-
-    // The origin loop could go away while we are trying to post to it, so we
-    // need to call its PostTask method inside a lock.  See ~CertVerifier.
-    AutoLock locked(origin_loop_proxy_lock_);
-    if (origin_loop_proxy_) {
-      bool posted = origin_loop_proxy_->PostTask(FROM_HERE, reply.release());
-      // TODO(willchan): Fix leaks and then change this to a DCHECK.
-      LOG_IF(ERROR, !posted) << "Leaked CertVerifier!";
+  // DoReply runs on the origin thread.
+  void DoReply() {
+    DCHECK_EQ(MessageLoop::current(), origin_loop_);
+    {
+      // We lock here because the worker thread could still be in Finished,
+      // after the PostTask, but before unlocking |lock_|. If we do not lock in
+      // this case, we will end up deleting a locked Lock, which can lead to
+      // memory leaks or worse errors.
+      AutoLock locked(lock_);
+      if (!canceled_) {
+        cert_verifier_->HandleResult(cert_, hostname_, flags_,
+                                     error_, verify_result_);
+      }
     }
+    delete this;
   }
 
-  void DoCallback() {
-    // Running on the origin thread.
+  void Finish() {
+    // Runs on the worker thread.
+    // We assume that the origin loop outlives the CertVerifier. If the
+    // CertVerifier is deleted, it will call Cancel on us. If it does so
+    // before the Acquire, we'll delete ourselves and return. If it's trying to
+    // do so concurrently, then it'll block on the lock and we'll call PostTask
+    // while the CertVerifier (and therefore the MessageLoop) is still alive.
+    // If it does so after this function, we assume that the MessageLoop will
+    // process pending tasks. In which case we'll notice the |canceled_| flag
+    // in DoReply.
 
-    // We may have been cancelled!
-    if (!verifier_)
-      return;
+    bool canceled;
+    {
+      AutoLock locked(lock_);
+      canceled = canceled_;
+      if (!canceled) {
+        origin_loop_->PostTask(
+            FROM_HERE, NewRunnableMethod(this, &CertVerifierWorker::DoReply));
+      }
+    }
 
-    *verify_result_ = result_;
+    if (canceled)
+      delete this;
+  }
 
-    // Drop the verifier's reference to us.  Do this before running the
-    // callback since the callback might result in the verifier being
-    // destroyed.
-    verifier_->request_ = NULL;
+  scoped_refptr<X509Certificate> cert_;
+  const std::string hostname_;
+  const int flags_;
+  MessageLoop* const origin_loop_;
+  CertVerifier* const cert_verifier_;
 
-    callback_->Run(error_);
-  }
+  // lock_ protects canceled_.
+  Lock lock_;
 
-  void Cancel() {
-    verifier_ = NULL;
+  // If canceled_ is true,
+  // * origin_loop_ cannot be accessed by the worker thread,
+  // * cert_verifier_ cannot be accessed by any thread.
+  bool canceled_;
+
+  int error_;
+  CertVerifyResult verify_result_;
+
+  DISALLOW_COPY_AND_ASSIGN(CertVerifierWorker);
+};
 
-    AutoLock locked(origin_loop_proxy_lock_);
-    origin_loop_proxy_ = NULL;
+// A CertVerifierJob is a one-to-one counterpart of a CertVerifierWorker. It
+// lives only on the CertVerifier's origin message loop.
+class CertVerifierJob {
+ public:
+  explicit CertVerifierJob(CertVerifierWorker* worker) : worker_(worker) {
   }
 
- private:
-  friend class base::RefCountedThreadSafe<CertVerifier::Request>;
+  ~CertVerifierJob() {
+    if (worker_)
+      worker_->Cancel();
+  }
 
-  ~Request() {}
+  void AddRequest(CertVerifierRequest* request) {
+    requests_.push_back(request);
+  }
 
-  // Set on the origin thread, read on the worker thread.
-  scoped_refptr<X509Certificate> cert_;
-  std::string hostname_;
-  // bitwise OR'd of X509Certificate::VerifyFlags.
-  int flags_;
+  void HandleResult(const CachedCertVerifyResult& verify_result) {
+    worker_ = NULL;
+    PostAll(verify_result);
+  }
 
-  // Only used on the origin thread (where Verify was called).
-  CertVerifier* verifier_;
-  CertVerifyResult* verify_result_;
-  CompletionCallback* callback_;
+ private:
+  void PostAll(const CachedCertVerifyResult& verify_result) {
+    std::vector<CertVerifierRequest*> requests;
+    requests_.swap(requests);
 
-  // Used to post ourselves onto the origin thread.
-  Lock origin_loop_proxy_lock_;
-  // Use a MessageLoopProxy in case the owner of the CertVerifier is leaked, so
-  // this code won't crash: http://crbug.com/42275.  If this is leaked, then it
-  // doesn't get Cancel()'d, so |origin_loop_proxy_| doesn't get NULL'd out.  If
-  // the MessageLoop goes away, then if we had used a MessageLoop, this would
-  // crash.
-  scoped_refptr<base::MessageLoopProxy> origin_loop_proxy_;
+    for (std::vector<CertVerifierRequest*>::iterator
+         i = requests.begin(); i != requests.end(); i++) {
+      (*i)->Post(verify_result);
+      // Post() causes the CertVerifierRequest to delete itself.
+    }
+  }
 
-  // Assigned on the worker thread, read on the origin thread.
-  int error_;
-  CertVerifyResult result_;
+  std::vector<CertVerifierRequest*> requests_;
+  CertVerifierWorker* worker_;
 };
 
-//-----------------------------------------------------------------------------
 
-CertVerifier::CertVerifier() {
+CertVerifier::CertVerifier()
+    : time_service_(new DefaultTimeService),
+      requests_(0),
+      cache_hits_(0),
+      inflight_joins_(0) {
+}
+
+CertVerifier::CertVerifier(TimeService* time_service)
+    : time_service_(time_service),
+      requests_(0),
+      cache_hits_(0),
+      inflight_joins_(0) {
 }
 
 CertVerifier::~CertVerifier() {
-  if (request_)
-    request_->Cancel();
+  STLDeleteValues(&inflight_);
 }
 
 int CertVerifier::Verify(X509Certificate* cert,
                          const std::string& hostname,
                          int flags,
                          CertVerifyResult* verify_result,
-                         CompletionCallback* callback) {
-  DCHECK(!request_) << "verifier already in use";
+                         CompletionCallback* callback,
+                         RequestHandle* out_req) {
+  DCHECK(CalledOnValidThread());
 
-  // Do a synchronous verification.
-  if (!callback) {
-    CertVerifyResult result;
-    int rv = cert->Verify(hostname, flags, &result);
-    *verify_result = result;
-    return rv;
+  if (!callback || !verify_result || hostname.empty()) {
+    *out_req = NULL;
+    return ERR_INVALID_ARGUMENT;
   }
 
-  request_ = new Request(this, cert, hostname, flags, verify_result, callback);
+  requests_++;
 
-  // Dispatch to worker thread...
-  if (!WorkerPool::PostTask(FROM_HERE,
-          NewRunnableMethod(request_.get(), &Request::DoVerify), true)) {
-    NOTREACHED();
-    request_ = NULL;
-    return ERR_FAILED;
+  const RequestParams key = {cert->fingerprint(), hostname, flags};
+  // 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.
+  CertVerifierJob* job;
+  std::map<RequestParams, CertVerifierJob*>::const_iterator j;
+  j = inflight_.find(key);
+  if (j != inflight_.end()) {
+    // An identical request is in flight already. We'll just attach our
+    // callback.
+    inflight_joins_++;
+    job = j->second;
+  } else {
+    // Need to make a new request.
+    CertVerifierWorker* worker = new CertVerifierWorker(cert, hostname, flags,
+                                                        this);
+    job = new CertVerifierJob(worker);
+    inflight_.insert(std::make_pair(key, job));
+    if (!worker->Start()) {
+      inflight_.erase(key);
+      delete job;
+      delete worker;
+      *out_req = NULL;
+      return ERR_FAILED;  // TODO(wtc): Log an error message.
+    }
+  }
+
+  CertVerifierRequest* request =
+      new CertVerifierRequest(callback, verify_result);
+  job->AddRequest(request);
+  *out_req = request;
   return ERR_IO_PENDING;
 }
 
+void CertVerifier::CancelRequest(RequestHandle req) {
+  DCHECK(CalledOnValidThread());
+  CertVerifierRequest* request = reinterpret_cast<CertVerifierRequest*>(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,
+                                const std::string& hostname,
+                                int flags,
+                                int error,
+                                const CertVerifyResult& verify_result) {
+  DCHECK(CalledOnValidThread());
+
+  const base::Time current_time(time_service_->Now());
+
+  CachedCertVerifyResult cached_result;
+  cached_result.error = error;
+  cached_result.result = verify_result;
+  uint32 ttl = kTTLSecs;
+  cached_result.expiry = current_time + base::TimeDelta::FromSeconds(ttl);
+
+  const RequestParams key = {cert->fingerprint(), hostname, flags};
+
+  DCHECK_GE(kMaxCacheEntries, 1u);
+  DCHECK_LE(cache_.size(), kMaxCacheEntries);
+  if (cache_.size() == kMaxCacheEntries) {
+    // 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() == kMaxCacheEntries) {
+    // 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);
+  if (j == inflight_.end()) {
+    NOTREACHED();
+    return;
+  }
+  CertVerifierJob* job = j->second;
+  inflight_.erase(j);
+
+  job->HandleResult(cached_result);
+  delete job;
+}
+
+/////////////////////////////////////////////////////////////////////
+
+SingleRequestCertVerifier::SingleRequestCertVerifier(
+    CertVerifier* cert_verifier)
+    : cert_verifier_(cert_verifier),
+      cur_request_(NULL),
+      cur_request_callback_(NULL),
+      ALLOW_THIS_IN_INITIALIZER_LIST(
+          callback_(this, &SingleRequestCertVerifier::OnVerifyCompletion)) {
+  DCHECK(cert_verifier_ != NULL);
+}
+
+SingleRequestCertVerifier::~SingleRequestCertVerifier() {
+  if (cur_request_) {
+    cert_verifier_->CancelRequest(cur_request_);
+    cur_request_ = NULL;
+  }
+}
+
+int SingleRequestCertVerifier::Verify(X509Certificate* cert,
+                                      const std::string& hostname,
+                                      int flags,
+                                      CertVerifyResult* verify_result,
+                                      CompletionCallback* callback) {
+  // Should not be already in use.
+  DCHECK(!cur_request_ && !cur_request_callback_);
+
+  // Do a synchronous verification.
+  if (!callback)
+    return cert->Verify(hostname, flags, verify_result);
+
+  CertVerifier::RequestHandle request = NULL;
+
+  // We need to be notified of completion before |callback| is called, so that
+  // we can clear out |cur_request_*|.
+  int rv = cert_verifier_->Verify(
+      cert, hostname, flags, verify_result, &callback_, &request);
+
+  if (rv == ERR_IO_PENDING) {
+    // Cleared in OnVerifyCompletion().
+    cur_request_ = request;
+    cur_request_callback_ = callback;
+  }
+
+  return rv;
+}
+
+void SingleRequestCertVerifier::OnVerifyCompletion(int result) {
+  DCHECK(cur_request_ && cur_request_callback_);
+
+  CompletionCallback* callback = cur_request_callback_;
+
+  // Clear the outstanding request information.
+  cur_request_ = NULL;
+  cur_request_callback_ = NULL;
+
+  // Call the user's original callback.
+  callback->Run(result);
+}
+
 }  // namespace net
+
+DISABLE_RUNNABLE_METHOD_REFCOUNT(net::CertVerifierWorker);
+