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 <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 "net/base/cert_status_flags.h"
 #include "net/base/cert_verify_result.h"
 #include "net/base/net_errors.h"
 #include "net/base/pem_tokenizer.h"
 
 namespace net {
 
 namespace {
 
@@ skipping 12 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 {

[wtc, 2011/07/17 01:55:32]

This class should be renamed OSCertHandleCache.
You can do the renaming in a separate CL.

  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) {}

[wtc, 2011/07/17 01:55:32]

Add a blank line below.

+    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;

[wtc, 2011/07/17 01:55:32]

Define ref_count as an 'int'.  This is what RefCountedBase
does.

+  };
+  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.

[wtc, 2011/07/17 01:55:32]

It doesn't seem necessary to wrap this line.

-  // 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.
   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);
+  DCHECK(!IsNullFingerprint(fingerprint)) <<
+       "Only insert certs with real fingerprints.";

[wtc, 2011/07/17 01:55:32]

Delete this DCHECK.  This DCHECK was only meaningful in the
old code because some X509Certificate objects are fake
certificates and don't have fingerprints.

+
+  X509Certificate::OSCertHandle old_handle = NULL;
+  {
+    base::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.

[wtc, 2011/07/17 01:55:32]

Remove "likely".

+        // 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;
+      DHISTOGRAM_COUNTS("X509CertificateReuseCount", 1);

[wtc, 2011/07/17 01:55:32]

Move this DHISTOGRAM_COUNTS call outside the critical section.

You can do this at the end of this function:
  if (old_handle) {
    X509Certificate::FreeOSCertHandle(old_handle);
    DHISTOGRAM_COUNTS("X509CertificateReuseCount", 1);
  }
    

+    }
+    ++pos->second.ref_count;
+    *cert_handle = X509Certificate::DupOSCertHandle(pos->second.cert_handle);

[wtc, 2011/07/17 01:55:32]

Note how you increment pos->second.ref_count and the
ref-count of pos->second.cert_handle together.  This point
will be important in my comment on Remove() below.

+  }
+  // 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);
+}
+
+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 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) {
-  base::AutoLock lock(lock_);
+  bool is_same_cert = X509Certificate::IsSameOSCert(cert_handle,
+                                                    pos->second.cert_handle);
+  if (!is_same_cert)
+    return;  // A cache collision where the winning cert is still around.

[wtc, 2011/07/17 01:55:32]

In the comments on lines 175 and 180, change
"cache collision" to "hash collision".

 
-  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
+    // 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);

[wtc, 2011/07/17 01:55:32]

Here, you decrement pos->second.ref_count every time, but
only decrement the ref-count of pos->second.cert_handle when
pos->second.ref_count becomes 0.  So pos->second.cert_handle
has a reference leak.

This can be fixed in two ways.

1. Move this X509Certificate::FreeOSCertHandle() call outside
the if statement, to line 181.

2. In InsertOrUpdate(), call X509Certificate::DupOSCertHandle()
only when an Entry is newly created, on line 136.
This means we acquire an OSCertHandle reference for
Entry::cert_handle.

The second solution is my preference.

[Ryan Sleevi, 2011/07/17 03:52:22]

I don't believe there is a leak, and have made an attempt to update the
documentation to that effect. I want to make sure you're happy with the
explanation being sufficiently clear, so I'll hold off committing until you're
OK with the verbiage.

Each caller to InsertOrUpdate is guaranteed to "own" their own OS handle -
meaning they're responsible for calling FreeOSCertHandle() on it as well. If the
entry is new to the cache, the cache will add a reference that the Cache owns as
well (so two handles - one for the cache, one for the caller).

If the entry is an existing element, then the caller's original handle will be
freed, and it will be substituted with a duplicate of the element in the cache.

When Remove() is called, the caller owns a handle and the Cache, if it's found,
also owns a handle. This call removes the Cache's handle, so that the only owner
left (of the OS Cert handle) is the caller, who then subsequently frees it
(lines 587/591). So the adds and removes are balanced.

+    cache_.erase(pos);
+  }
+}
 
 // CompareSHA1Hashes is a helper function for using bsearch() with an array of
 // SHA1 hashes.
 static int CompareSHA1Hashes(const void* a, const void* b) {
   return memcmp(a, b, base::SHA1_LENGTH);
 }
 
 }  // 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_);
 }
 
 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);
+  X509Certificate* cert = new X509Certificate(cert_handle, intermediates);

[wtc, 2011/07/17 01:55:32]

The local variable 'cert' was necessary in the old code.
In the new code, just do
  return 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);
-  return ok ? cert_handle : NULL;

[wtc, 2011/07/16 00:54:54]

IMPORTANT: Removing X509Certificate::cert_store() may
reintroduce bug 45706.

In r48650 I made essentially the same change:
http://codereview.chromium.org/2322008

But it introduced bug 45706.  I couldn't track down the
bug, so I reverted it in r48953:
http://codereview.chromium.org/2605007

Note that the way we get the server's certificate chain
has changed since then.  We used to call the NSS function
CERT_GetCertChainFromCert.  Now we call the new NSS function
SSL_PeerCertificateChain.  It is possible that bug 45706
was caused by the use of CERT_GetCertChainFromCert.

So please test this carefully, including the test case in
bug 45706.  I would love this to work!

-}
-#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 170 matching lines @@
 
 #if !defined(USE_NSS)
 bool X509Certificate::VerifyNameMatch(const std::string& hostname) const {
   std::vector<std::string> dns_names;
   GetDNSNames(&dns_names);
   return VerifyHostname(hostname, dns_names);
 }
 #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