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

net/base/x509_certificate.cc

 // 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.
 
 #include "net/base/x509_certificate.h"
 
 #include <stdlib.h>
 
 #include <algorithm>
 #include <map>
 #include <string>
 #include <vector>
 
 #include "base/lazy_instance.h"
 #include "base/logging.h"
 #include "base/memory/singleton.h"
 #include "base/metrics/histogram.h"
 #include "base/pickle.h"
 #include "base/sha1.h"
 #include "base/string_piece.h"
 #include "base/string_util.h"
+#include "base/synchronization/lock.h"
 #include "base/time.h"
 #include "googleurl/src/url_canon_ip.h"
 #include "net/base/cert_status_flags.h"
 #include "net/base/cert_verify_result.h"
 #include "net/base/net_errors.h"
 #include "net/base/net_util.h"
 #include "net/base/pem_tokenizer.h"
 
 namespace net {
 
@@ skipping 14 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 a duplicated reference to the existing cached
+  // certificate, with the caller taking ownership of this duplicated handle.
+  // If an equivalent OS certificate handle is not found, a duplicated
+  // reference to |*cert_handle| will be added to the cache. In either case,
+  // upon return, the caller fully owns |*cert_handle| and is responsible for
+  // calling FreeOSCertHandle(), after first calling Remove().
+  void InsertOrUpdate(X509Certificate::OSCertHandle* cert_handle);
+
+  // Decrements the cache reference count for |cert_handle|, a handle that was
+  // previously obtained by calling InsertOrUpdate(). If this is the last
+  // cached reference held, this will remove the handle from the cache. The
+  // caller retains ownership of |cert_handle| and remains responsible for
+  // calling FreeOSCertHandle() to release the underlying OS certificate
+  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 created by
+    // InsertOrUpdate() have been released, so the cache entry will be removed
+    // the cached OS certificate handle will be freed.
+    int 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 acquire this lock before using any private data of this object
   // You must not block while holding this lock.
   base::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);
+
+  X509Certificate::OSCertHandle old_handle = NULL;
+  {
+    base::AutoLock lock(lock_);
+    CertMap::iterator pos = cache_.find(fingerprint);
+    if (pos == cache_.end()) {
+      // A cached entry was not found, so initialize a new entry. The entry
+      // assumes ownership of the current |*cert_handle|.
+      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, 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;
+      }
+      // A cached entry was found and will be used instead of the caller's
+      // handle. Ensure the caller's original handle will be freed, since
+      // ownership is assumed.
+      old_handle = *cert_handle;
+    }
+    // Whether an existing cached handle or a new handle, increment the
+    // cache's reference count and return a handle that the caller can own.
+    ++pos->second.ref_count;
+    *cert_handle = X509Certificate::DupOSCertHandle(pos->second.cert_handle);
+  }
+  // If the caller's handle was replaced with a cached handle, free the
+  // original handle now. This is done outside of the lock because
+  // |old_handle| may be the only handle for this particular certificate, so
+  // freeing it may be complex or resource-intensive and does not need to
+  // be guarded by the lock.
+  if (old_handle) {
+    X509Certificate::FreeOSCertHandle(old_handle);
+    DHISTOGRAM_COUNTS("X509CertificateReuseCount", 1);
+  }
+}
+
+void X509CertificateCache::Remove(X509Certificate::OSCertHandle cert_handle) {
+  SHA1Fingerprint fingerprint =
+      X509Certificate::CalculateFingerprint(cert_handle);
   base::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 hash 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) {
-  base::AutoLock lock(lock_);
+  bool is_same_cert = X509Certificate::IsSameOSCert(cert_handle,
+                                                    pos->second.cert_handle);
+  if (!is_same_cert)
+    return;  // A hash 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) {
-  base::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
+    // Entry's OS handle and remove the Entry. The caller still holds a
+    // reference to |cert_handle| and is responsible for freeing it.
+    X509Certificate::FreeOSCertHandle(pos->second.cert_handle);
+    cache_.erase(pos);
+  }
+}
 
 // CompareSHA1Hashes is a helper function for using bsearch() with an array of
 // SHA1 hashes.
 int CompareSHA1Hashes(const void* a, const void* b) {
   return memcmp(a, b, base::SHA1_LENGTH);
 }
 
 // Utility to split |src| on the first occurrence of |c|, if any. |right| will
 // either be empty if |c| was not found, or will contain the remainder of the
 // string including the split character itself.
@@ skipping 23 matching lines @@
 }
 
 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));
 }
 
 // static
 X509Certificate* X509Certificate::CreateFromHandle(
     OSCertHandle cert_handle,
-    Source source,
     const OSCertHandles& intermediates) {
   DCHECK(cert_handle);
-  DCHECK_NE(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_NE(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);
-  return cert;
+  return new X509Certificate(cert_handle, intermediates);
 }
 
-#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);
-  return ok ? cert_handle : NULL;
-}
-#else
 static X509Certificate::OSCertHandle CreateOSCert(base::StringPiece der_cert) {
   return X509Certificate::CreateOSCertHandleFromBytes(
       const_cast<char*>(der_cert.data()), der_cert.size());
 }
-#endif
 
 // static
 X509Certificate* X509Certificate::CreateFromDERCertChain(
     const std::vector<base::StringPiece>& der_certs) {
   if (der_certs.empty())
     return NULL;
 
   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 = ReadOSCertHandleFromPickle(pickle, pickle_iter);
   if (!cert_handle)
@@ skipping 11 matching lines @@
       OSCertHandle intermediate = ReadOSCertHandleFromPickle(pickle,
                                                              pickle_iter);
       if (!intermediate)
         break;
       intermediates.push_back(intermediate);
     }
   }
 
   X509Certificate* cert = NULL;
   if (intermediates.size() == num_intermediates)
-    cert = CreateFromHandle(cert_handle, SOURCE_FROM_CACHE, intermediates);
+    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;
 }
 
 void X509Certificate::Persist(Pickle* pickle) {
   DCHECK(cert_handle_);
   if (!WriteOSCertHandleToPickle(cert_handle_, pickle)) {
@@ skipping 173 matching lines @@
 bool X509Certificate::VerifyNameMatch(const std::string& hostname) const {
   // TODO(joth): Define a cross platform version of ParseSubjectAltName and use
   // that to retrieve dns names and ip addresses, independent of common name.
   std::vector<std::string> dns_names, ip_addrs;
   GetDNSNames(&dns_names);
   return VerifyHostname(hostname, subject_.common_name, dns_names, ip_addrs);
 }
 #endif
 
 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() {
   // 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]);
+  }
 }
 
 bool X509Certificate::IsBlacklisted() const {
   static const unsigned kNumSerials = 10;
   static const unsigned kSerialBytes = 16;
   static const uint8 kSerials[kNumSerials][kSerialBytes] = {
     // Not a real certificate. For testing only.
     {0x07,0x7a,0x59,0xbc,0xd5,0x34,0x59,0x60,0x1c,0xa6,0x90,0x72,0x67,0xa6,0xdd,0x1c},
 
     // The next nine certificates all expire on Fri Mar 14 23:59:59 2014.
@@ skipping 47 matching lines @@
 bool X509Certificate::IsSHA1HashInSortedArray(const SHA1Fingerprint& hash,
                                               const uint8* array,
                                               size_t array_byte_len) {
   DCHECK_EQ(0u, array_byte_len % base::SHA1_LENGTH);
   const unsigned arraylen = array_byte_len / base::SHA1_LENGTH;
   return NULL != bsearch(hash.data, array, arraylen, base::SHA1_LENGTH,
                          CompareSHA1Hashes);
 }
 
 }  // namespace net