Refactor X509Certificate caching to cache the OS handle, rather than the X509Certificate

net/base/x509_certificate.cc

 // Copyright (c) 2006-2008 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/x509_certificate.h"
 
 #include <map>
 
 #include "base/lazy_instance.h"
 #include "base/logging.h"
@@ skipping 23 matching lines @@
 const X509Certificate::Format kFormatDecodePriority[] = {
   X509Certificate::FORMAT_SINGLE_CERTIFICATE,
   X509Certificate::FORMAT_PKCS7
 };
 
 // The PEM block header used for DER certificates
 const char kCertificateHeader[] = "CERTIFICATE";
 // The PEM block header used for PKCS#7 data
 const char kPKCS7Header[] = "PKCS7";
 
-// A thread-safe cache for X509Certificate objects.
+// A thread-safe cache for OS certificate handles.
 //
-// The cache does not hold a reference to the certificate objects.  The objects
-// must |Remove| themselves from the cache upon destruction (or else the cache
-// will be holding dead pointers to the objects).
-// TODO(rsleevi): There exists a chance of a use-after-free, due to a race
-// between Find() and Remove(). See http://crbug.com/49377
+// Within each of the supported underlying crypto libraries, a certificate
+// handle is represented as a ref-counted object that contains the parsed
+// data for the certificate. In addition, the underlying OS handle may also
+// contain a copy of the original ASN.1 DER used to constructed the handle.
+//
+// In order to reduce the memory usage when multiple SSL connections exist,
+// with each connection storing the server's identity certificate plus any
+// intermediates supplied, the certificate handles are cached. Any two
+// X509Certificates that were created from the same ASN.1 DER data,
+// regardless of where that data came from, will share the same underlying
+// OS certificate handle.
 class X509CertificateCache {
  public:
-  void Insert(X509Certificate* cert);
-  void Remove(X509Certificate* cert);
-  X509Certificate* Find(const SHA1Fingerprint& fingerprint);
+  // Performs a compare-and-swap like operation. If an OS certificate handle
+  // for the same certificate data as |*cert_handle| already exists in the
+  // cache, the original |*cert_handle| will be freed, and |cert_handle|
+  // will be updated to point to the existing cached certificate, after
+  // adding to the reference count. If an equivalent OS certificate handle
+  // is not found, |*cert_handle| will be added to the cache and its
+  // reference count increased, while otherwise remaining unmodified and
+  // pointing to the caller's original certificate.
+  void InsertOrUpdate(X509Certificate::OSCertHandle* cert_handle);
+
+  // Decrements the reference count for |cert_handle|, and if it is the last
+  // reference held in the cache, frees the underlying OS certificate
+  // handle. InsertOrUpdate() must have been called prior to Remove() for
+  // the |cert_handle|.
+  void Remove(X509Certificate::OSCertHandle cert_handle);
 
  private:
-  typedef std::map<SHA1Fingerprint, X509Certificate*, SHA1FingerprintLessThan>
-      CertMap;
+  // A single entry in the cache. Certificates will be keyed by their SHA1
+  // fingerprints, but will not be considered equivalent unless the entire
+  // certificate data matches.
+  struct Entry {
+    Entry() : cert_handle(NULL), ref_count(0) {}
+    X509Certificate::OSCertHandle cert_handle;
+
+    // Increased by each call to InsertOrUpdate(), and balanced by each call
+    // to Remove(). When it equals 0, all references have been released, so
+    // the cache entry will be removed and the OS certificate released.
+    size_t ref_count;
+  };
+  typedef std::map<SHA1Fingerprint, Entry, SHA1FingerprintLessThan> CertMap;
 
   // Obtain an instance of X509CertificateCache via a LazyInstance.
   X509CertificateCache() {}
   ~X509CertificateCache() {}
   friend struct base::DefaultLazyInstanceTraits<X509CertificateCache>;
 
-  // You must acquire this lock before using any private data of this object.
-  // You must not block while holding this lock.
+  // You must acquire this lock before using any private data of this
+  // object. You must not block while holding this lock.
   Lock lock_;
 
   // The certificate cache.  You must acquire |lock_| before using |cache_|.
   CertMap cache_;
 
   DISALLOW_COPY_AND_ASSIGN(X509CertificateCache);
 };
 
 base::LazyInstance<X509CertificateCache,
                    base::LeakyLazyInstanceTraits<X509CertificateCache> >
     g_x509_certificate_cache(base::LINKER_INITIALIZED);
 
-// Insert |cert| into the cache.  The cache does NOT AddRef |cert|.
-// Any existing certificate with the same fingerprint will be replaced.
-void X509CertificateCache::Insert(X509Certificate* cert) {
+void X509CertificateCache::InsertOrUpdate(
+    X509Certificate::OSCertHandle* cert_handle) {
+  DCHECK(cert_handle);
+  SHA1Fingerprint fingerprint =
+      X509Certificate::CalculateFingerprint(*cert_handle);
+  DCHECK(!IsNullFingerprint(fingerprint)) <<
+       "Only insert certs with real fingerprints.";
+
+  AutoLock lock(lock_);
+  CertMap::iterator pos(cache_.find(fingerprint));
+  if (pos == cache_.end()) {
+    // Cached entry not found. Initialize a new entry. |*cert_handle| is
+    // guaranteed to have at least one OS reference (the caller's), which
+    // will be incremented, along with cache_entry.ref_count, below.
+    Entry cache_entry;
+    cache_entry.cert_handle = *cert_handle;
+    cache_entry.ref_count = 0;
+    CertMap::value_type cache_value(fingerprint, cache_entry);
+    pos = cache_.insert(cache_value).first;
+  } else {
+    bool is_same_cert =
+        X509Certificate::IsSameOSCert(*cert_handle, pos->second.cert_handle);
+    if (!is_same_cert) {
+      // Two certificates don't match, likely due to a SHA1 hash collision.
+      // Given the low probability, the simplest solution is to not cache
+      // the certificate, which should not affect performance too
+      // negatively.
+      return;
+    }
+    // Release the caller's reference to |*cert_handle|, as it will be
+    // replaced by the cached handle just found.
+    X509Certificate::FreeOSCertHandle(*cert_handle);
+    DHISTOGRAM_COUNTS("X509CertificateReuseCount", 1);
+  }
+
+  ++pos->second.ref_count;
+  *cert_handle = X509Certificate::DupOSCertHandle(pos->second.cert_handle);
+}
+
+void X509CertificateCache::Remove(X509Certificate::OSCertHandle cert_handle) {
+  SHA1Fingerprint fingerprint =
+      X509Certificate::CalculateFingerprint(cert_handle);
   AutoLock lock(lock_);
 
-  DCHECK(!IsNullFingerprint(cert->fingerprint())) <<
-      "Only insert certs with real fingerprints.";
-  cache_[cert->fingerprint()] = cert;
-};
+   CertMap::iterator pos(cache_.find(fingerprint));
+   if (pos == cache_.end())
+    return;  // A cache collision where the winning cert was already freed.
 
-// Remove |cert| from the cache.  The cache does not assume that |cert| is
-// already in the cache.
-void X509CertificateCache::Remove(X509Certificate* cert) {
-  AutoLock lock(lock_);
+  bool is_same_cert = X509Certificate::IsSameOSCert(cert_handle,
+                                                    pos->second.cert_handle);
+  DCHECK(is_same_cert) << "Hash collision between different certificates";
+  if (!is_same_cert)
+    return;  // A cache collision where the winning cert is still around.
 
-  CertMap::iterator pos(cache_.find(cert->fingerprint()));
-  if (pos == cache_.end())
-    return;  // It is not an error to remove a cert that is not in the cache.
-  cache_.erase(pos);
-};
-
-// Find a certificate in the cache with the given fingerprint.  If one does
-// not exist, this method returns NULL.
-X509Certificate* X509CertificateCache::Find(
-    const SHA1Fingerprint& fingerprint) {
-  AutoLock lock(lock_);
-
-  CertMap::iterator pos(cache_.find(fingerprint));
-  if (pos == cache_.end())
-    return NULL;
-
-  return pos->second;
-};
+  if (--pos->second.ref_count == 0) {
+    // The last reference to |cert_handle| has been removed, so release the
+    // underlying OS handle and remove from the cache. The caller still
+    // holds a reference to the underlying OS handle and still bears
+    // responsibility for freeing it.
+    X509Certificate::FreeOSCertHandle(pos->second.cert_handle);
+    cache_.erase(pos);
+  }
+}
 
 }  // namespace
 
 bool X509Certificate::LessThan::operator()(X509Certificate* lhs,
                                            X509Certificate* rhs) const {
   if (lhs == rhs)
     return false;
 
   SHA1FingerprintLessThan fingerprint_functor;
   return fingerprint_functor(lhs->fingerprint_, rhs->fingerprint_);
 }
 
 // static
 X509Certificate* X509Certificate::CreateFromHandle(
     OSCertHandle cert_handle,
-    Source source,
     const OSCertHandles& intermediates) {
   DCHECK(cert_handle);
-  DCHECK(source != SOURCE_UNUSED);
-
-  // Check if we already have this certificate in memory.
-  X509CertificateCache* cache = g_x509_certificate_cache.Pointer();
-  X509Certificate* cached_cert =
-      cache->Find(CalculateFingerprint(cert_handle));
-  if (cached_cert) {
-    DCHECK(cached_cert->source_ != SOURCE_UNUSED);
-    if (cached_cert->source_ > source ||
-        (cached_cert->source_ == source &&
-         cached_cert->HasIntermediateCertificates(intermediates))) {
-      // Return the certificate with the same fingerprint from our cache.
-      DHISTOGRAM_COUNTS("X509CertificateReuseCount", 1);
-      return cached_cert;
-    }
-    // Else the new cert is better and will replace the old one in the cache.
-  }
-
-  // Otherwise, allocate and cache a new object.
-  X509Certificate* cert = new X509Certificate(cert_handle, source,
-                                              intermediates);
-  cache->Insert(cert);
+  X509Certificate* cert = new X509Certificate(cert_handle, intermediates);
   return cert;
 }
 
 #if defined(OS_WIN)
 static X509Certificate::OSCertHandle CreateOSCert(base::StringPiece der_cert) {
   X509Certificate::OSCertHandle cert_handle = NULL;
   BOOL ok = CertAddEncodedCertificateToStore(
       X509Certificate::cert_store(), X509_ASN_ENCODING | PKCS_7_ASN_ENCODING,
       reinterpret_cast<const BYTE*>(der_cert.data()), der_cert.size(),
       CERT_STORE_ADD_USE_EXISTING, &cert_handle);
@@ skipping 14 matching lines @@
 
   X509Certificate::OSCertHandles intermediate_ca_certs;
   for (size_t i = 1; i < der_certs.size(); i++) {
     OSCertHandle handle = CreateOSCert(der_certs[i]);
     DCHECK(handle);
     intermediate_ca_certs.push_back(handle);
   }
 
   OSCertHandle handle = CreateOSCert(der_certs[0]);
   DCHECK(handle);
-  X509Certificate* cert =
-      CreateFromHandle(handle, SOURCE_FROM_NETWORK, intermediate_ca_certs);
+  X509Certificate* cert = CreateFromHandle(handle, intermediate_ca_certs);
   FreeOSCertHandle(handle);
   for (size_t i = 0; i < intermediate_ca_certs.size(); i++)
     FreeOSCertHandle(intermediate_ca_certs[i]);
 
   return cert;
 }
 
 // static
 X509Certificate* X509Certificate::CreateFromBytes(const char* data,
                                                   int length) {
   OSCertHandle cert_handle = CreateOSCertHandleFromBytes(data, length);
   if (!cert_handle)
     return NULL;
 
-  X509Certificate* cert = CreateFromHandle(cert_handle,
-                                           SOURCE_LONE_CERT_IMPORT,
-                                           OSCertHandles());
+  X509Certificate* cert = CreateFromHandle(cert_handle, OSCertHandles());
   FreeOSCertHandle(cert_handle);
   return cert;
 }
 
 // static
 X509Certificate* X509Certificate::CreateFromPickle(const Pickle& pickle,
                                                    void** pickle_iter,
                                                    PickleType type) {
   OSCertHandle cert_handle = ReadCertHandleFromPickle(pickle, pickle_iter);
   OSCertHandles intermediates;
@@ skipping 24 matching lines @@
     if (!ok) {
       FreeOSCertHandle(cert_handle);
       for (size_t i = 0; i < intermediates.size(); ++i)
         FreeOSCertHandle(intermediates[i]);
       return NULL;
     }
   }
 
   if (!cert_handle)
     return NULL;
-  X509Certificate* cert = CreateFromHandle(cert_handle, SOURCE_FROM_CACHE,
-                                           intermediates);
+  X509Certificate* cert = CreateFromHandle(cert_handle, intermediates);
   FreeOSCertHandle(cert_handle);
   for (size_t i = 0; i < intermediates.size(); ++i)
     FreeOSCertHandle(intermediates[i]);
 
   return cert;
 }
 
 // static
 CertificateList X509Certificate::CreateCertificateListFromBytes(
     const char* data, int length, int format) {
@@ skipping 56 matching lines @@
                                                   kFormatDecodePriority[i]);
   }
 
   CertificateList results;
   // No certificates parsed.
   if (certificates.empty())
     return results;
 
   for (OSCertHandles::iterator it = certificates.begin();
        it != certificates.end(); ++it) {
-    X509Certificate* result = CreateFromHandle(*it, SOURCE_LONE_CERT_IMPORT,
-                                               OSCertHandles());
+    X509Certificate* result = CreateFromHandle(*it, OSCertHandles());
     results.push_back(scoped_refptr<X509Certificate>(result));
     FreeOSCertHandle(*it);
   }
 
   return results;
 }
 
 X509Certificate::X509Certificate(OSCertHandle cert_handle,
-                                 Source source,
                                  const OSCertHandles& intermediates)
-    : cert_handle_(DupOSCertHandle(cert_handle)),
-      source_(source) {
-  // Copy/retain the intermediate cert handles.
-  for (size_t i = 0; i < intermediates.size(); ++i)
-    intermediate_ca_certs_.push_back(DupOSCertHandle(intermediates[i]));
+    : cert_handle_(DupOSCertHandle(cert_handle)) {
+  X509CertificateCache* cache = g_x509_certificate_cache.Pointer();
+  cache->InsertOrUpdate(&cert_handle_);
+  for (size_t i = 0; i < intermediates.size(); ++i) {
+    // Duplicate the incoming certificate, as the caller retains ownership
+    // of |intermediates|.
+    OSCertHandle intermediate = DupOSCertHandle(intermediates[i]);
+    // Update the cache, which will assume ownership of the duplicated
+    // handle and return a suitable equivalent, potentially from the cache.
+    cache->InsertOrUpdate(&intermediate);
+    intermediate_ca_certs_.push_back(intermediate);
+  }
   // Platform-specific initialization.
   Initialize();
 }
 
 X509Certificate::X509Certificate(const std::string& subject,
                                  const std::string& issuer,
                                  base::Time start_date,
                                  base::Time expiration_date)
     : subject_(subject),
       issuer_(issuer),
       valid_start_(start_date),
       valid_expiry_(expiration_date),
-      cert_handle_(NULL),
-      source_(SOURCE_UNUSED) {
+      cert_handle_(NULL) {
   memset(fingerprint_.data, 0, sizeof(fingerprint_.data));
 }
 
 X509Certificate::~X509Certificate() {
-  // We might not be in the cache, but it is safe to remove ourselves anyway.
-  g_x509_certificate_cache.Get().Remove(this);
-  if (cert_handle_)
+  X509CertificateCache* cache = g_x509_certificate_cache.Pointer();
+  if (cert_handle_) {
+    cache->Remove(cert_handle_);
     FreeOSCertHandle(cert_handle_);
-  for (size_t i = 0; i < intermediate_ca_certs_.size(); ++i)
+  }
+  for (size_t i = 0; i < intermediate_ca_certs_.size(); ++i) {
+    cache->Remove(intermediate_ca_certs_[i]);
     FreeOSCertHandle(intermediate_ca_certs_[i]);
+  }
 }
 
 void X509Certificate::Persist(Pickle* pickle) {
   DCHECK(cert_handle_);
   if (!WriteCertHandleToPickle(cert_handle_, pickle)) {
     NOTREACHED();
     return;
   }
 
   if (!pickle->WriteSize(intermediate_ca_certs_.size())) {
@@ skipping 27 matching lines @@
 
 bool X509Certificate::HasIntermediateCertificates(const OSCertHandles& certs) {
   for (size_t i = 0; i < certs.size(); ++i) {
     if (!HasIntermediateCertificate(certs[i]))
       return false;
   }
   return true;
 }
 
 }  // namespace net