1 files changed, 132 insertions, 47 deletions
diff --git a/src/crypto/x509/cert_pool.go b/src/crypto/x509/cert_pool.go
index 59ec4b6894..bcc5db3b70 100644
--- a/src/crypto/x509/cert_pool.go
+++ b/src/crypto/x509/cert_pool.go
@@ -5,43 +5,89 @@
 package x509
 
 import (
+	"bytes"
+	"crypto/sha256"
 	"encoding/pem"
 	"errors"
 	"runtime"
+	"sync"
 )
 
+type sum224 [sha256.Size224]byte
+
 // CertPool is a set of certificates.
 type CertPool struct {
-	bySubjectKeyId map[string][]int
-	byName         map[string][]int
-	certs          []*Certificate
+	byName map[string][]int // cert.RawSubject => index into lazyCerts
+
+	// lazyCerts contains funcs that return a certificate,
+	// lazily parsing/decompressing it as needed.
+	lazyCerts []lazyCert
+
+	// haveSum maps from sum224(cert.Raw) to true. It's used only
+	// for AddCert duplicate detection, to avoid CertPool.contains
+	// calls in the AddCert path (because the contains method can
+	// call getCert and otherwise negate savings from lazy getCert
+	// funcs).
+	haveSum map[sum224]bool
+}
+
+// lazyCert is minimal metadata about a Cert and a func to retrieve it
+// in its normal expanded *Certificate form.
+type lazyCert struct {
+	// rawSubject is the Certificate.RawSubject value.
+	// It's the same as the CertPool.byName key, but in []byte
+	// form to make CertPool.Subjects (as used by crypto/tls) do
+	// fewer allocations.
+	rawSubject []byte
+
+	// getCert returns the certificate.
+	//
+	// It is not meant to do network operations or anything else
+	// where a failure is likely; the func is meant to lazily
+	// parse/decompress data that is already known to be good. The
+	// error in the signature primarily is meant for use in the
+	// case where a cert file existed on local disk when the program
+	// started up is deleted later before it's read.
+	getCert func() (*Certificate, error)
 }
 
 // NewCertPool returns a new, empty CertPool.
 func NewCertPool() *CertPool {
 	return &CertPool{
-		bySubjectKeyId: make(map[string][]int),
-		byName:         make(map[string][]int),
+		byName:  make(map[string][]int),
+		haveSum: make(map[sum224]bool),
 	}
 }
 
+// len returns the number of certs in the set.
+// A nil set is a valid empty set.
+func (s *CertPool) len() int {
+	if s == nil {
+		return 0
+	}
+	return len(s.lazyCerts)
+}
+
+// cert returns cert index n in s.
+func (s *CertPool) cert(n int) (*Certificate, error) {
+	return s.lazyCerts[n].getCert()
+}
+
 func (s *CertPool) copy() *CertPool {
 	p := &CertPool{
-		bySubjectKeyId: make(map[string][]int, len(s.bySubjectKeyId)),
-		byName:         make(map[string][]int, len(s.byName)),
-		certs:          make([]*Certificate, len(s.certs)),
-	}
-	for k, v := range s.bySubjectKeyId {
-		indexes := make([]int, len(v))
-		copy(indexes, v)
-		p.bySubjectKeyId[k] = indexes
+		byName:    make(map[string][]int, len(s.byName)),
+		lazyCerts: make([]lazyCert, len(s.lazyCerts)),
+		haveSum:   make(map[sum224]bool, len(s.haveSum)),
 	}
 	for k, v := range s.byName {
 		indexes := make([]int, len(v))
 		copy(indexes, v)
 		p.byName[k] = indexes
 	}
-	copy(p.certs, s.certs)
+	for k := range s.haveSum {
+		p.haveSum[k] = true
+	}
+	copy(p.lazyCerts, s.lazyCerts)
 	return p
 }
 
@@ -70,19 +116,44 @@ func SystemCertPool() (*CertPool, error) {
 }
 
 // findPotentialParents returns the indexes of certificates in s which might
-// have signed cert. The caller must not modify the returned slice.
-func (s *CertPool) findPotentialParents(cert *Certificate) []int {
+// have signed cert.
+func (s *CertPool) findPotentialParents(cert *Certificate) []*Certificate {
 	if s == nil {
 		return nil
 	}
 
-	var candidates []int
-	if len(cert.AuthorityKeyId) > 0 {
-		candidates = s.bySubjectKeyId[string(cert.AuthorityKeyId)]
+	// consider all candidates where cert.Issuer matches cert.Subject.
+	// when picking possible candidates the list is built in the order
+	// of match plausibility as to save cycles in buildChains:
+	//   AKID and SKID match
+	//   AKID present, SKID missing / AKID missing, SKID present
+	//   AKID and SKID don't match
+	var matchingKeyID, oneKeyID, mismatchKeyID []*Certificate
+	for _, c := range s.byName[string(cert.RawIssuer)] {
+		candidate, err := s.cert(c)
+		if err != nil {
+			continue
+		}
+		kidMatch := bytes.Equal(candidate.SubjectKeyId, cert.AuthorityKeyId)
+		switch {
+		case kidMatch:
+			matchingKeyID = append(matchingKeyID, candidate)
+		case (len(candidate.SubjectKeyId) == 0 && len(cert.AuthorityKeyId) > 0) ||
+			(len(candidate.SubjectKeyId) > 0 && len(cert.AuthorityKeyId) == 0):
+			oneKeyID = append(oneKeyID, candidate)
+		default:
+			mismatchKeyID = append(mismatchKeyID, candidate)
+		}
 	}
-	if len(candidates) == 0 {
-		candidates = s.byName[string(cert.RawIssuer)]
+
+	found := len(matchingKeyID) + len(oneKeyID) + len(mismatchKeyID)
+	if found == 0 {
+		return nil
 	}
+	candidates := make([]*Certificate, 0, found)
+	candidates = append(candidates, matchingKeyID...)
+	candidates = append(candidates, oneKeyID...)
+	candidates = append(candidates, mismatchKeyID...)
 	return candidates
 }
 
@@ -90,15 +161,7 @@ func (s *CertPool) contains(cert *Certificate) bool {
 	if s == nil {
 		return false
 	}
-
-	candidates := s.byName[string(cert.RawSubject)]
-	for _, c := range candidates {
-		if s.certs[c].Equal(cert) {
-			return true
-		}
-	}
-
-	return false
+	return s.haveSum[sha256.Sum224(cert.Raw)]
 }
 
 // AddCert adds a certificate to a pool.
@@ -106,21 +169,32 @@ func (s *CertPool) AddCert(cert *Certificate) {
 	if cert == nil {
 		panic("adding nil Certificate to CertPool")
 	}
+	s.addCertFunc(sha256.Sum224(cert.Raw), string(cert.RawSubject), func() (*Certificate, error) {
+		return cert, nil
+	})
+}
+
+// addCertFunc adds metadata about a certificate to a pool, along with
+// a func to fetch that certificate later when needed.
+//
+// The rawSubject is Certificate.RawSubject and must be non-empty.
+// The getCert func may be called 0 or more times.
+func (s *CertPool) addCertFunc(rawSum224 sum224, rawSubject string, getCert func() (*Certificate, error)) {
+	if getCert == nil {
+		panic("getCert can't be nil")
+	}
 
 	// Check that the certificate isn't being added twice.
-	if s.contains(cert) {
+	if s.haveSum[rawSum224] {
 		return
 	}
 
-	n := len(s.certs)
-	s.certs = append(s.certs, cert)
-
-	if len(cert.SubjectKeyId) > 0 {
-		keyId := string(cert.SubjectKeyId)
-		s.bySubjectKeyId[keyId] = append(s.bySubjectKeyId[keyId], n)
-	}
-	name := string(cert.RawSubject)
-	s.byName[name] = append(s.byName[name], n)
+	s.haveSum[rawSum224] = true
+	s.lazyCerts = append(s.lazyCerts, lazyCert{
+		rawSubject: []byte(rawSubject),
+		getCert:    getCert,
+	})
+	s.byName[rawSubject] = append(s.byName[rawSubject], len(s.lazyCerts)-1)
 }
 
 // AppendCertsFromPEM attempts to parse a series of PEM encoded certificates.
@@ -140,24 +214,35 @@ func (s *CertPool) AppendCertsFromPEM(pemCerts []byte) (ok bool) {
 			continue
 		}
 
-		cert, err := ParseCertificate(block.Bytes)
+		certBytes := block.Bytes
+		cert, err := ParseCertificate(certBytes)
 		if err != nil {
 			continue
 		}
-
-		s.AddCert(cert)
+		var lazyCert struct {
+			sync.Once
+			v *Certificate
+		}
+		s.addCertFunc(sha256.Sum224(cert.Raw), string(cert.RawSubject), func() (*Certificate, error) {
+			lazyCert.Do(func() {
+				// This can't fail, as the same bytes already parsed above.
+				lazyCert.v, _ = ParseCertificate(certBytes)
+				certBytes = nil
+			})
+			return lazyCert.v, nil
+		})
 		ok = true
 	}
 
-	return
+	return ok
 }
 
 // Subjects returns a list of the DER-encoded subjects of
 // all of the certificates in the pool.
 func (s *CertPool) Subjects() [][]byte {
-	res := make([][]byte, len(s.certs))
-	for i, c := range s.certs {
-		res[i] = c.RawSubject
+	res := make([][]byte, s.len())
+	for i, lc := range s.lazyCerts {
+		res[i] = lc.rawSubject
 	}
 	return res
 }