1// Copyright (c) 2012 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "net/cert/multi_threaded_cert_verifier.h"
6
7#include <algorithm>
8
9#include "base/bind.h"
10#include "base/bind_helpers.h"
11#include "base/compiler_specific.h"
12#include "base/message_loop/message_loop.h"
13#include "base/metrics/histogram.h"
14#include "base/stl_util.h"
15#include "base/synchronization/lock.h"
16#include "base/threading/worker_pool.h"
17#include "base/time/time.h"
18#include "base/values.h"
19#include "net/base/hash_value.h"
20#include "net/base/net_errors.h"
21#include "net/base/net_log.h"
22#include "net/cert/cert_trust_anchor_provider.h"
23#include "net/cert/cert_verify_proc.h"
24#include "net/cert/crl_set.h"
25#include "net/cert/x509_certificate.h"
26#include "net/cert/x509_certificate_net_log_param.h"
27
28#if defined(USE_NSS) || defined(OS_IOS)
29#include <private/pprthred.h>  // PR_DetachThread
30#endif
31
32namespace net {
33
34////////////////////////////////////////////////////////////////////////////
35
36// Life of a request:
37//
38// MultiThreadedCertVerifier  CertVerifierJob  CertVerifierWorker     Request
39//      |                                         (origin loop)    (worker loop)
40//      |
41//   Verify()
42//      |---->-------------------------------------<creates>
43//      |
44//      |---->-------------------<creates>
45//      |
46//      |---->-------------------------------------------------------<creates>
47//      |
48//      |---->---------------------------------------Start
49//      |                                              |
50//      |                                           PostTask
51//      |
52//      |                                                     <starts verifying>
53//      |---->-------------------AddRequest                           |
54//                                                                    |
55//                                                                    |
56//                                                                    |
57//                                                                  Finish
58//                                                                    |
59//                                                                 PostTask
60//
61//                                                     |
62//                                                  DoReply
63//      |----<-----------------------------------------|
64//  HandleResult
65//      |
66//      |---->------------------HandleResult
67//                                   |
68//                                   |------>---------------------------Post
69//
70//
71//
72// On a cache hit, MultiThreadedCertVerifier::Verify() returns synchronously
73// without posting a task to a worker thread.
74
75namespace {
76
77// The default value of max_cache_entries_.
78const unsigned kMaxCacheEntries = 256;
79
80// The number of seconds for which we'll cache a cache entry.
81const unsigned kTTLSecs = 1800;  // 30 minutes.
82
83base::Value* CertVerifyResultCallback(const CertVerifyResult& verify_result,
84                                      NetLog::LogLevel log_level) {
85  base::DictionaryValue* results = new base::DictionaryValue();
86  results->SetBoolean("has_md5", verify_result.has_md5);
87  results->SetBoolean("has_md2", verify_result.has_md2);
88  results->SetBoolean("has_md4", verify_result.has_md4);
89  results->SetBoolean("is_issued_by_known_root",
90                      verify_result.is_issued_by_known_root);
91  results->SetBoolean("is_issued_by_additional_trust_anchor",
92                      verify_result.is_issued_by_additional_trust_anchor);
93  results->SetBoolean("common_name_fallback_used",
94                      verify_result.common_name_fallback_used);
95  results->SetInteger("cert_status", verify_result.cert_status);
96  results->Set("verified_cert",
97               NetLogX509CertificateCallback(verify_result.verified_cert.get(),
98                                             log_level));
99
100  base::ListValue* hashes = new base::ListValue();
101  for (std::vector<HashValue>::const_iterator it =
102           verify_result.public_key_hashes.begin();
103       it != verify_result.public_key_hashes.end();
104       ++it) {
105    hashes->AppendString(it->ToString());
106  }
107  results->Set("public_key_hashes", hashes);
108
109  return results;
110}
111
112}  // namespace
113
114MultiThreadedCertVerifier::CachedResult::CachedResult() : error(ERR_FAILED) {}
115
116MultiThreadedCertVerifier::CachedResult::~CachedResult() {}
117
118MultiThreadedCertVerifier::CacheValidityPeriod::CacheValidityPeriod(
119    const base::Time& now)
120    : verification_time(now),
121      expiration_time(now) {
122}
123
124MultiThreadedCertVerifier::CacheValidityPeriod::CacheValidityPeriod(
125    const base::Time& now,
126    const base::Time& expiration)
127    : verification_time(now),
128      expiration_time(expiration) {
129}
130
131bool MultiThreadedCertVerifier::CacheExpirationFunctor::operator()(
132    const CacheValidityPeriod& now,
133    const CacheValidityPeriod& expiration) const {
134  // Ensure this functor is being used for expiration only, and not strict
135  // weak ordering/sorting. |now| should only ever contain a single
136  // base::Time.
137  // Note: DCHECK_EQ is not used due to operator<< overloading requirements.
138  DCHECK(now.verification_time == now.expiration_time);
139
140  // |now| contains only a single time (verification_time), while |expiration|
141  // contains the validity range - both when the certificate was verified and
142  // when the verification result should expire.
143  //
144  // If the user receives a "not yet valid" message, and adjusts their clock
145  // foward to the correct time, this will (typically) cause
146  // now.verification_time to advance past expiration.expiration_time, thus
147  // treating the cached result as an expired entry and re-verifying.
148  // If the user receives a "expired" message, and adjusts their clock
149  // backwards to the correct time, this will cause now.verification_time to
150  // be less than expiration_verification_time, thus treating the cached
151  // result as an expired entry and re-verifying.
152  // If the user receives either of those messages, and does not adjust their
153  // clock, then the result will be (typically) be cached until the expiration
154  // TTL.
155  //
156  // This algorithm is only problematic if the user consistently keeps
157  // adjusting their clock backwards in increments smaller than the expiration
158  // TTL, in which case, cached elements continue to be added. However,
159  // because the cache has a fixed upper bound, if no entries are expired, a
160  // 'random' entry will be, thus keeping the memory constraints bounded over
161  // time.
162  return now.verification_time >= expiration.verification_time &&
163         now.verification_time < expiration.expiration_time;
164};
165
166
167// Represents the output and result callback of a request.
168class CertVerifierRequest {
169 public:
170  CertVerifierRequest(const CompletionCallback& callback,
171                      CertVerifyResult* verify_result,
172                      const BoundNetLog& net_log)
173      : callback_(callback),
174        verify_result_(verify_result),
175        net_log_(net_log) {
176    net_log_.BeginEvent(NetLog::TYPE_CERT_VERIFIER_REQUEST);
177  }
178
179  ~CertVerifierRequest() {
180  }
181
182  // Ensures that the result callback will never be made.
183  void Cancel() {
184    callback_.Reset();
185    verify_result_ = NULL;
186    net_log_.AddEvent(NetLog::TYPE_CANCELLED);
187    net_log_.EndEvent(NetLog::TYPE_CERT_VERIFIER_REQUEST);
188  }
189
190  // Copies the contents of |verify_result| to the caller's
191  // CertVerifyResult and calls the callback.
192  void Post(const MultiThreadedCertVerifier::CachedResult& verify_result) {
193    if (!callback_.is_null()) {
194      net_log_.EndEvent(NetLog::TYPE_CERT_VERIFIER_REQUEST);
195      *verify_result_ = verify_result.result;
196      callback_.Run(verify_result.error);
197    }
198    delete this;
199  }
200
201  bool canceled() const { return callback_.is_null(); }
202
203  const BoundNetLog& net_log() const { return net_log_; }
204
205 private:
206  CompletionCallback callback_;
207  CertVerifyResult* verify_result_;
208  const BoundNetLog net_log_;
209};
210
211
212// CertVerifierWorker runs on a worker thread and takes care of the blocking
213// process of performing the certificate verification.  Deletes itself
214// eventually if Start() succeeds.
215class CertVerifierWorker {
216 public:
217  CertVerifierWorker(CertVerifyProc* verify_proc,
218                     X509Certificate* cert,
219                     const std::string& hostname,
220                     int flags,
221                     CRLSet* crl_set,
222                     const CertificateList& additional_trust_anchors,
223                     MultiThreadedCertVerifier* cert_verifier)
224      : verify_proc_(verify_proc),
225        cert_(cert),
226        hostname_(hostname),
227        flags_(flags),
228        crl_set_(crl_set),
229        additional_trust_anchors_(additional_trust_anchors),
230        origin_loop_(base::MessageLoop::current()),
231        cert_verifier_(cert_verifier),
232        canceled_(false),
233        error_(ERR_FAILED) {
234  }
235
236  // Returns the certificate being verified. May only be called /before/
237  // Start() is called.
238  X509Certificate* certificate() const { return cert_.get(); }
239
240  bool Start() {
241    DCHECK_EQ(base::MessageLoop::current(), origin_loop_);
242
243    return base::WorkerPool::PostTask(
244        FROM_HERE, base::Bind(&CertVerifierWorker::Run, base::Unretained(this)),
245        true /* task is slow */);
246  }
247
248  // Cancel is called from the origin loop when the MultiThreadedCertVerifier is
249  // getting deleted.
250  void Cancel() {
251    DCHECK_EQ(base::MessageLoop::current(), origin_loop_);
252    base::AutoLock locked(lock_);
253    canceled_ = true;
254  }
255
256 private:
257  void Run() {
258    // Runs on a worker thread.
259    error_ = verify_proc_->Verify(cert_.get(),
260                                  hostname_,
261                                  flags_,
262                                  crl_set_.get(),
263                                  additional_trust_anchors_,
264                                  &verify_result_);
265#if defined(USE_NSS) || defined(OS_IOS)
266    // Detach the thread from NSPR.
267    // Calling NSS functions attaches the thread to NSPR, which stores
268    // the NSPR thread ID in thread-specific data.
269    // The threads in our thread pool terminate after we have called
270    // PR_Cleanup.  Unless we detach them from NSPR, net_unittests gets
271    // segfaults on shutdown when the threads' thread-specific data
272    // destructors run.
273    PR_DetachThread();
274#endif
275    Finish();
276  }
277
278  // DoReply runs on the origin thread.
279  void DoReply() {
280    DCHECK_EQ(base::MessageLoop::current(), origin_loop_);
281    {
282      // We lock here because the worker thread could still be in Finished,
283      // after the PostTask, but before unlocking |lock_|. If we do not lock in
284      // this case, we will end up deleting a locked Lock, which can lead to
285      // memory leaks or worse errors.
286      base::AutoLock locked(lock_);
287      if (!canceled_) {
288        cert_verifier_->HandleResult(cert_.get(),
289                                     hostname_,
290                                     flags_,
291                                     additional_trust_anchors_,
292                                     error_,
293                                     verify_result_);
294      }
295    }
296    delete this;
297  }
298
299  void Finish() {
300    // Runs on the worker thread.
301    // We assume that the origin loop outlives the MultiThreadedCertVerifier. If
302    // the MultiThreadedCertVerifier is deleted, it will call Cancel on us. If
303    // it does so before the Acquire, we'll delete ourselves and return. If it's
304    // trying to do so concurrently, then it'll block on the lock and we'll call
305    // PostTask while the MultiThreadedCertVerifier (and therefore the
306    // MessageLoop) is still alive.
307    // If it does so after this function, we assume that the MessageLoop will
308    // process pending tasks. In which case we'll notice the |canceled_| flag
309    // in DoReply.
310
311    bool canceled;
312    {
313      base::AutoLock locked(lock_);
314      canceled = canceled_;
315      if (!canceled) {
316        origin_loop_->PostTask(
317            FROM_HERE, base::Bind(
318                &CertVerifierWorker::DoReply, base::Unretained(this)));
319      }
320    }
321
322    if (canceled)
323      delete this;
324  }
325
326  scoped_refptr<CertVerifyProc> verify_proc_;
327  scoped_refptr<X509Certificate> cert_;
328  const std::string hostname_;
329  const int flags_;
330  scoped_refptr<CRLSet> crl_set_;
331  const CertificateList additional_trust_anchors_;
332  base::MessageLoop* const origin_loop_;
333  MultiThreadedCertVerifier* const cert_verifier_;
334
335  // lock_ protects canceled_.
336  base::Lock lock_;
337
338  // If canceled_ is true,
339  // * origin_loop_ cannot be accessed by the worker thread,
340  // * cert_verifier_ cannot be accessed by any thread.
341  bool canceled_;
342
343  int error_;
344  CertVerifyResult verify_result_;
345
346  DISALLOW_COPY_AND_ASSIGN(CertVerifierWorker);
347};
348
349// A CertVerifierJob is a one-to-one counterpart of a CertVerifierWorker. It
350// lives only on the CertVerifier's origin message loop.
351class CertVerifierJob {
352 public:
353  CertVerifierJob(CertVerifierWorker* worker,
354                  const BoundNetLog& net_log)
355      : start_time_(base::TimeTicks::Now()),
356        worker_(worker),
357        net_log_(net_log) {
358    net_log_.BeginEvent(
359        NetLog::TYPE_CERT_VERIFIER_JOB,
360        base::Bind(&NetLogX509CertificateCallback,
361                   base::Unretained(worker_->certificate())));
362  }
363
364  ~CertVerifierJob() {
365    if (worker_) {
366      net_log_.AddEvent(NetLog::TYPE_CANCELLED);
367      net_log_.EndEvent(NetLog::TYPE_CERT_VERIFIER_JOB);
368      worker_->Cancel();
369      DeleteAllCanceled();
370    }
371  }
372
373  void AddRequest(CertVerifierRequest* request) {
374    request->net_log().AddEvent(
375        NetLog::TYPE_CERT_VERIFIER_REQUEST_BOUND_TO_JOB,
376        net_log_.source().ToEventParametersCallback());
377
378    requests_.push_back(request);
379  }
380
381  void HandleResult(
382      const MultiThreadedCertVerifier::CachedResult& verify_result,
383      bool is_first_job) {
384    worker_ = NULL;
385    net_log_.EndEvent(
386        NetLog::TYPE_CERT_VERIFIER_JOB,
387        base::Bind(&CertVerifyResultCallback, verify_result.result));
388    base::TimeDelta latency = base::TimeTicks::Now() - start_time_;
389    UMA_HISTOGRAM_CUSTOM_TIMES("Net.CertVerifier_Job_Latency",
390                               latency,
391                               base::TimeDelta::FromMilliseconds(1),
392                               base::TimeDelta::FromMinutes(10),
393                               100);
394    if (is_first_job) {
395      UMA_HISTOGRAM_CUSTOM_TIMES("Net.CertVerifier_First_Job_Latency",
396                                 latency,
397                                 base::TimeDelta::FromMilliseconds(1),
398                                 base::TimeDelta::FromMinutes(10),
399                                 100);
400    }
401    PostAll(verify_result);
402  }
403
404 private:
405  void PostAll(const MultiThreadedCertVerifier::CachedResult& verify_result) {
406    std::vector<CertVerifierRequest*> requests;
407    requests_.swap(requests);
408
409    for (std::vector<CertVerifierRequest*>::iterator
410         i = requests.begin(); i != requests.end(); i++) {
411      (*i)->Post(verify_result);
412      // Post() causes the CertVerifierRequest to delete itself.
413    }
414  }
415
416  void DeleteAllCanceled() {
417    for (std::vector<CertVerifierRequest*>::iterator
418         i = requests_.begin(); i != requests_.end(); i++) {
419      if ((*i)->canceled()) {
420        delete *i;
421      } else {
422        LOG(DFATAL) << "CertVerifierRequest leaked!";
423      }
424    }
425  }
426
427  const base::TimeTicks start_time_;
428  std::vector<CertVerifierRequest*> requests_;
429  CertVerifierWorker* worker_;
430  const BoundNetLog net_log_;
431};
432
433MultiThreadedCertVerifier::MultiThreadedCertVerifier(
434    CertVerifyProc* verify_proc)
435    : cache_(kMaxCacheEntries),
436      first_job_(NULL),
437      requests_(0),
438      cache_hits_(0),
439      inflight_joins_(0),
440      verify_proc_(verify_proc),
441      trust_anchor_provider_(NULL) {
442  CertDatabase::GetInstance()->AddObserver(this);
443}
444
445MultiThreadedCertVerifier::~MultiThreadedCertVerifier() {
446  STLDeleteValues(&inflight_);
447  CertDatabase::GetInstance()->RemoveObserver(this);
448}
449
450void MultiThreadedCertVerifier::SetCertTrustAnchorProvider(
451    CertTrustAnchorProvider* trust_anchor_provider) {
452  DCHECK(CalledOnValidThread());
453  trust_anchor_provider_ = trust_anchor_provider;
454}
455
456int MultiThreadedCertVerifier::Verify(X509Certificate* cert,
457                                      const std::string& hostname,
458                                      int flags,
459                                      CRLSet* crl_set,
460                                      CertVerifyResult* verify_result,
461                                      const CompletionCallback& callback,
462                                      RequestHandle* out_req,
463                                      const BoundNetLog& net_log) {
464  DCHECK(CalledOnValidThread());
465
466  if (callback.is_null() || !verify_result || hostname.empty()) {
467    *out_req = NULL;
468    return ERR_INVALID_ARGUMENT;
469  }
470
471  requests_++;
472
473  const CertificateList empty_cert_list;
474  const CertificateList& additional_trust_anchors =
475      trust_anchor_provider_ ?
476          trust_anchor_provider_->GetAdditionalTrustAnchors() : empty_cert_list;
477
478  const RequestParams key(cert->fingerprint(), cert->ca_fingerprint(),
479                          hostname, flags, additional_trust_anchors);
480  const CertVerifierCache::value_type* cached_entry =
481      cache_.Get(key, CacheValidityPeriod(base::Time::Now()));
482  if (cached_entry) {
483    ++cache_hits_;
484    *out_req = NULL;
485    *verify_result = cached_entry->result;
486    return cached_entry->error;
487  }
488
489  // No cache hit. See if an identical request is currently in flight.
490  CertVerifierJob* job;
491  std::map<RequestParams, CertVerifierJob*>::const_iterator j;
492  j = inflight_.find(key);
493  if (j != inflight_.end()) {
494    // An identical request is in flight already. We'll just attach our
495    // callback.
496    inflight_joins_++;
497    job = j->second;
498  } else {
499    // Need to make a new request.
500    CertVerifierWorker* worker =
501        new CertVerifierWorker(verify_proc_.get(),
502                               cert,
503                               hostname,
504                               flags,
505                               crl_set,
506                               additional_trust_anchors,
507                               this);
508    job = new CertVerifierJob(
509        worker,
510        BoundNetLog::Make(net_log.net_log(), NetLog::SOURCE_CERT_VERIFIER_JOB));
511    if (!worker->Start()) {
512      delete job;
513      delete worker;
514      *out_req = NULL;
515      // TODO(wtc): log to the NetLog.
516      LOG(ERROR) << "CertVerifierWorker couldn't be started.";
517      return ERR_INSUFFICIENT_RESOURCES;  // Just a guess.
518    }
519    inflight_.insert(std::make_pair(key, job));
520    if (requests_ == 1) {
521      // Cleared in HandleResult.
522      first_job_ = job;
523    }
524  }
525
526  CertVerifierRequest* request =
527      new CertVerifierRequest(callback, verify_result, net_log);
528  job->AddRequest(request);
529  *out_req = request;
530  return ERR_IO_PENDING;
531}
532
533void MultiThreadedCertVerifier::CancelRequest(RequestHandle req) {
534  DCHECK(CalledOnValidThread());
535  CertVerifierRequest* request = reinterpret_cast<CertVerifierRequest*>(req);
536  request->Cancel();
537}
538
539MultiThreadedCertVerifier::RequestParams::RequestParams(
540    const SHA1HashValue& cert_fingerprint_arg,
541    const SHA1HashValue& ca_fingerprint_arg,
542    const std::string& hostname_arg,
543    int flags_arg,
544    const CertificateList& additional_trust_anchors)
545    : hostname(hostname_arg),
546      flags(flags_arg) {
547  hash_values.reserve(2 + additional_trust_anchors.size());
548  hash_values.push_back(cert_fingerprint_arg);
549  hash_values.push_back(ca_fingerprint_arg);
550  for (size_t i = 0; i < additional_trust_anchors.size(); ++i)
551    hash_values.push_back(additional_trust_anchors[i]->fingerprint());
552}
553
554MultiThreadedCertVerifier::RequestParams::~RequestParams() {}
555
556bool MultiThreadedCertVerifier::RequestParams::operator<(
557    const RequestParams& other) const {
558  // |flags| is compared before |cert_fingerprint|, |ca_fingerprint|, and
559  // |hostname| under assumption that integer comparisons are faster than
560  // memory and string comparisons.
561  if (flags != other.flags)
562    return flags < other.flags;
563  if (hostname != other.hostname)
564    return hostname < other.hostname;
565  return std::lexicographical_compare(
566      hash_values.begin(), hash_values.end(),
567      other.hash_values.begin(), other.hash_values.end(),
568      net::SHA1HashValueLessThan());
569}
570
571// HandleResult is called by CertVerifierWorker on the origin message loop.
572// It deletes CertVerifierJob.
573void MultiThreadedCertVerifier::HandleResult(
574    X509Certificate* cert,
575    const std::string& hostname,
576    int flags,
577    const CertificateList& additional_trust_anchors,
578    int error,
579    const CertVerifyResult& verify_result) {
580  DCHECK(CalledOnValidThread());
581
582  const RequestParams key(cert->fingerprint(), cert->ca_fingerprint(),
583                          hostname, flags, additional_trust_anchors);
584
585  CachedResult cached_result;
586  cached_result.error = error;
587  cached_result.result = verify_result;
588  base::Time now = base::Time::Now();
589  cache_.Put(
590      key, cached_result, CacheValidityPeriod(now),
591      CacheValidityPeriod(now, now + base::TimeDelta::FromSeconds(kTTLSecs)));
592
593  std::map<RequestParams, CertVerifierJob*>::iterator j;
594  j = inflight_.find(key);
595  if (j == inflight_.end()) {
596    NOTREACHED();
597    return;
598  }
599  CertVerifierJob* job = j->second;
600  inflight_.erase(j);
601  bool is_first_job = false;
602  if (first_job_ == job) {
603    is_first_job = true;
604    first_job_ = NULL;
605  }
606
607  job->HandleResult(cached_result, is_first_job);
608  delete job;
609}
610
611void MultiThreadedCertVerifier::OnCACertChanged(
612    const X509Certificate* cert) {
613  DCHECK(CalledOnValidThread());
614
615  ClearCache();
616}
617
618}  // namespace net
619
620