Cache certificate verification results in memory.

net/base/cert_verifier.cc

-// 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 = 64;

[agl, 2010/12/13 16:25:04]

My feeling is that this is probably a little low? Given the complexity of modern
sites, we could flush a cache of this size from a single navigation. I feel that
256, 512 etc would be a better balance.

+
+// 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:
-  Request(CertVerifier* verifier,
-          X509Certificate* cert,
-          const std::string& hostname,
-          int flags,
-          CertVerifyResult* verify_result,
-          CompletionCallback* callback)
+  // 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 {

[willchan no longer on Chromium, 2010/12/13 09:30:53]

Should this be within the anonymous namespace?  I actually wonder if it's really
better to use the typedef void* RequestHandle.  We could just make this a nested
class within CertVerifier and rename it to CertVerifier::Request.  In
CertVerifier, we could forward declare class Request in CertVerifier and typedef
Request* RequestHandle.  Any attempts to dereference the handle would lead to a
compile error.  The advantage of this approach is avoiding a reinterpret_cast<>,
which always scares me a little bit.

+ public:
+  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)

[willchan no longer on Chromium, 2010/12/13 09:30:53]

I think you should just pass in a callback.  Then you don't need to friend
CertVerifierWorker.  And it's not like CertVerifierWorker should be calling
anything else on CertVerifier, it really should just be HandleResult().  If you
don't want to have too many parameters, you could change HandleResult to take a
const CertVerifierWorker&, and add const accessors for all the relevant data.

       : 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) {
   }
 
-  void DoVerify() {
-    // Running on the worker thread
-    error_ = cert_->Verify(hostname_, flags_, &result_);
+  bool Start() {
+    DCHECK_EQ(MessageLoop::current(), origin_loop_);

[willchan no longer on Chromium, 2010/12/13 09:30:53]

You may want to consider using ThreadChecker instead.  It uses PlatformThreadId
rather than MessageLoop::current(), which is generally speaking more accurate.

+
+    return WorkerPool::PostTask(
+               FROM_HERE, NewRunnableMethod(this, &CertVerifierWorker::Run),
+               true /* task is slow */);
+  }
+
+  // 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
     // the NSPR thread ID in thread-specific data.
     // The threads in our thread pool terminate after we have called
     // PR_Cleanup.  Unless we detach them from NSPR, net_unittests gets
     // segfaults on shutdown when the threads' thread-specific data
     // destructors run.
     PR_DetachThread();
 #endif
-
-    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!";
-    }
-  }
-
-  void DoCallback() {
-    // Running on the origin thread.
-
-    // We may have been cancelled!
-    if (!verifier_)
-      return;
-
-    *verify_result_ = result_;
-
-    // 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;
-
-    callback_->Run(error_);
-  }
-
-  void Cancel() {
-    verifier_ = NULL;
-
-    AutoLock locked(origin_loop_proxy_lock_);
-    origin_loop_proxy_ = NULL;
+    Finish();
+  }
+
+  // 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 Finish() {
+    // Runs on the worker thread.
+    // We assume that the origin loop outlives the CertVerifier. If the

[willchan no longer on Chromium, 2010/12/13 09:30:53]

See my note below for avoiding this complexity by using MessageLoopProxy.

+    // 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.
+
+    bool canceled;
+    {
+      AutoLock locked(lock_);
+      canceled = canceled_;
+      if (!canceled) {
+        origin_loop_->PostTask(
+            FROM_HERE, NewRunnableMethod(this, &CertVerifierWorker::DoReply));
+      }
+    }
+
+    if (canceled)
+      delete this;
+  }
+
+  scoped_refptr<X509Certificate> cert_;
+  const std::string hostname_;
+  const int flags_;
+  MessageLoop* const origin_loop_;

[willchan no longer on Chromium, 2010/12/13 09:30:53]

Note that if an object is leaked (not canceled properly), for example, an
SSLClientSocket, then origin_loop_ may refer to a deleted object.  This may
cause crashes like http://code.google.com/p/chromium/issues/detail?id=42275.  I
solved it there by using a MessageLoopProxy instead.  That will make the leak
not cause crashes, although it's still a leak and therefore a bug we should fix.

Note that using the MessageLoopProxy will also eliminate the need for the
complication wrt the above code in Finish().  The code is very tricky, because
|lock_| actually is locking more than just |canceled|.  It's also trying to make
sure that |origin_loop_| is valid.  If you used the MessageLoopProxy, then you
wouldn't have to worry about that.  Then you could do the natural thing of just
having |lock_| synchronize access to |canceled_| so you can store it in the
local variable |canceled|.

Note that you will have to check the value of MessageLoopProxy::PostTask() to
see if it got posted successfully.  If not, then you need to delete |this|.

+  CertVerifier* const cert_verifier_;
+
+  Lock lock_;

[willchan no longer on Chromium, 2010/12/13 09:30:53]

You should document what |lock_| locks.  In particular, it seems to primarily be
|canceled_|.

[agl, 2010/12/13 16:25:04]

I used to do this by indenting the protected variables, i.e.:

Lock lock_;
  bool canceled_;

Although reviewers always thought that it was a typo.

+  bool canceled_;
+
+  int error_;
+  CertVerifyResult verify_result_;
+
+  DISALLOW_COPY_AND_ASSIGN(CertVerifierWorker);
+};
+
+// 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) {
+  }
+
+  ~CertVerifierJob() {
+    if (worker_)
+      worker_->Cancel();
+  }
+
+  void AddRequest(CertVerifierRequest* request) {
+    requests_.push_back(request);
+  }
+
+  void HandleResult(const CachedCertVerifyResult& verify_result) {
+    worker_ = NULL;
+    PostAll(verify_result);
   }
 
  private:
-  friend class base::RefCountedThreadSafe<CertVerifier::Request>;
-
-  ~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_;
-
-  // Only used on the origin thread (where Verify was called).
-  CertVerifier* verifier_;
-  CertVerifyResult* verify_result_;
-  CompletionCallback* callback_;
-
-  // 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_;
-
-  // Assigned on the worker thread, read on the origin thread.
-  int error_;
-  CertVerifyResult result_;
+  void PostAll(const CachedCertVerifyResult& verify_result) {
+    std::vector<CertVerifierRequest*> requests;
+    requests_.swap(requests);
+
+    for (std::vector<CertVerifierRequest*>::iterator
+         i = requests.begin(); i != requests.end(); i++) {
+      (*i)->Post(verify_result);
+      // Post() causes the CertVerifierRequest to delete itself.
+    }
+  }
+
+  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());
+
+  if (!callback || !verify_result || hostname.empty()) {

[willchan no longer on Chromium, 2010/12/13 09:30:53]

You should probably add a NOTREACHED().  These represent coding bugs, therefore
we should crash in debug mode.

+    *out_req = NULL;
+    return ERR_INVALID_ARGUMENT;
+  }
+
+  requests_++;
+
+  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));

[willchan no longer on Chromium, 2010/12/13 09:30:53]

Should this be moved after the conditional?  So we don't insert unless the
worker started successfully?

[agl, 2010/12/13 16:25:04]

I think, originally, my code could reenter this object, thus this order. But
that's no longer the case so reordering is safe.

+    if (!worker->Start()) {
+      inflight_.erase(key);
+      delete job;
+      delete worker;
+      *out_req = NULL;
+      return ERR_FAILED;  // TODO(wtc): Log an error message.

[willchan no longer on Chromium, 2010/12/13 09:30:53]

Should this be ERR_UNEXPECTED?

+    }
+  }
+
+  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.
+}
+
+int 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) {
-    CertVerifyResult result;
-    int rv = cert->Verify(hostname, flags, &result);
-    *verify_result = result;
-    return rv;
-  }
-
-  request_ = new Request(this, cert, hostname, flags, verify_result, callback);
-
-  // Dispatch to worker thread...
-  if (!WorkerPool::PostTask(FROM_HERE,
-          NewRunnableMethod(request_.get(), &Request::DoVerify), true)) {
-    NOTREACHED();
-    request_ = NULL;
-    return ERR_FAILED;
-  }
-
-  return ERR_IO_PENDING;
+  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);
+