net/cert/multi_threaded_cert_verifier.cc

   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/callback_helpers.h"
  12 #include "base/compiler_specific.h"
  13 #include "base/containers/linked_list.h"
  14 #include "base/message_loop/message_loop.h"
  15 #include "base/metrics/histogram.h"
  16 #include "base/profiler/scoped_tracker.h"
  17 #include "base/sha1.h"
  18 #include "base/stl_util.h"
  19 #include "base/threading/worker_pool.h"
  20 #include "base/time/time.h"
  21 #include "base/values.h"
  22 #include "net/base/hash_value.h"
  23 #include "net/base/net_errors.h"
  24 #include "net/cert/cert_trust_anchor_provider.h"
  25 #include "net/cert/cert_verify_proc.h"
  26 #include "net/cert/crl_set.h"
  27 #include "net/cert/x509_certificate.h"
  28 #include "net/cert/x509_certificate_net_log_param.h"
  29 #include "net/log/net_log.h"
  30
  31 #if defined(USE_NSS_CERTS) || defined(OS_IOS)
  32 #include <private/pprthred.h>  // PR_DetachThread
  33 #endif
  34
  35 namespace net {
  36
  37 ////////////////////////////////////////////////////////////////////////////
  38 //
  39 // MultiThreadedCertVerifier is a thread-unsafe object which lives, dies, and is
  40 // operated on a single thread, henceforth referred to as the "origin" thread.
  41 //
  42 // On a cache hit, MultiThreadedCertVerifier::Verify() returns synchronously
  43 // without posting a task to a worker thread.
  44 //
  45 // Otherwise when an incoming Verify() request is received,
  46 // MultiThreadedCertVerifier checks if there is an outstanding "job"
  47 // (CertVerifierJob) in progress that can service the request. If there is,
  48 // the request is attached to that job. Otherwise a new job is started.
  49 //
  50 // A job (CertVerifierJob) and is a way to de-duplicate requests that are
  51 // fundamentally doing the same verification. CertVerifierJob is similarly
  52 // thread-unsafe and lives on the origin thread.
  53 //
  54 // To do the actual work, CertVerifierJob posts a task to WorkerPool
  55 // (PostTaskAndReply), and on completion notifies all requests attached to it.
  56 //
  57 // Cancellation:
  58 //
  59 // There are two ways for a request to be cancelled.
  60 //
  61 // (1) When the caller explicitly frees the Request.
  62 //
  63 //     If the request was in-flight (attached to a job), then it is detached.
  64 //     Note that no effort is made to reap jobs which have no attached requests.
  65 //     (Because the worker task isn't cancelable).
  66 //
  67 // (2) When the MultiThreadedCertVerifier is deleted.
  68 //
  69 //     This automatically cancels all outstanding requests. This is accomplished
  70 //     by deleting each of the jobs owned by the MultiThreadedCertVerifier,
  71 //     whose destructor in turn marks each attached request as canceled.
  72 //
  73 // TODO(eroman): If the MultiThreadedCertVerifier is deleted from within a
  74 // callback, the remaining requests in the completing job will NOT be cancelled.
  75
  76 namespace {
  77
  78 // The maximum number of cache entries to use for the ExpiringCache.
  79 const unsigned kMaxCacheEntries = 256;
  80
  81 // The number of seconds to cache entries.
  82 const unsigned kTTLSecs = 1800;  // 30 minutes.
  83
  84 scoped_ptr<base::Value> CertVerifyResultCallback(
  85     const CertVerifyResult& verify_result,
  86     NetLogCaptureMode capture_mode) {
  87   scoped_ptr<base::DictionaryValue> results(new base::DictionaryValue());
  88   results->SetBoolean("has_md5", verify_result.has_md5);
  89   results->SetBoolean("has_md2", verify_result.has_md2);
  90   results->SetBoolean("has_md4", verify_result.has_md4);
  91   results->SetBoolean("is_issued_by_known_root",
  92                       verify_result.is_issued_by_known_root);
  93   results->SetBoolean("is_issued_by_additional_trust_anchor",
  94                       verify_result.is_issued_by_additional_trust_anchor);
  95   results->SetBoolean("common_name_fallback_used",
  96                       verify_result.common_name_fallback_used);
  97   results->SetInteger("cert_status", verify_result.cert_status);
  98   results->Set("verified_cert",
  99                NetLogX509CertificateCallback(verify_result.verified_cert.get(),
 100                                              capture_mode));
 101
 102   scoped_ptr<base::ListValue> hashes(new base::ListValue());
 103   for (std::vector<HashValue>::const_iterator it =
 104            verify_result.public_key_hashes.begin();
 105        it != verify_result.public_key_hashes.end();
 106        ++it) {
 107     hashes->AppendString(it->ToString());
 108   }
 109   results->Set("public_key_hashes", hashes.Pass());
 110
 111   return results.Pass();
 112 }
 113
 114 }  // namespace
 115
 116 MultiThreadedCertVerifier::CachedResult::CachedResult() : error(ERR_FAILED) {}
 117
 118 MultiThreadedCertVerifier::CachedResult::~CachedResult() {}
 119
 120 MultiThreadedCertVerifier::CacheValidityPeriod::CacheValidityPeriod(
 121     const base::Time& now)
 122     : verification_time(now),
 123       expiration_time(now) {
 124 }
 125
 126 MultiThreadedCertVerifier::CacheValidityPeriod::CacheValidityPeriod(
 127     const base::Time& now,
 128     const base::Time& expiration)
 129     : verification_time(now),
 130       expiration_time(expiration) {
 131 }
 132
 133 bool MultiThreadedCertVerifier::CacheExpirationFunctor::operator()(
 134     const CacheValidityPeriod& now,
 135     const CacheValidityPeriod& expiration) const {
 136   // Ensure this functor is being used for expiration only, and not strict
 137   // weak ordering/sorting. |now| should only ever contain a single
 138   // base::Time.
 139   // Note: DCHECK_EQ is not used due to operator<< overloading requirements.
 140   DCHECK(now.verification_time == now.expiration_time);
 141
 142   // |now| contains only a single time (verification_time), while |expiration|
 143   // contains the validity range - both when the certificate was verified and
 144   // when the verification result should expire.
 145   //
 146   // If the user receives a "not yet valid" message, and adjusts their clock
 147   // foward to the correct time, this will (typically) cause
 148   // now.verification_time to advance past expiration.expiration_time, thus
 149   // treating the cached result as an expired entry and re-verifying.
 150   // If the user receives a "expired" message, and adjusts their clock
 151   // backwards to the correct time, this will cause now.verification_time to
 152   // be less than expiration_verification_time, thus treating the cached
 153   // result as an expired entry and re-verifying.
 154   // If the user receives either of those messages, and does not adjust their
 155   // clock, then the result will be (typically) be cached until the expiration
 156   // TTL.
 157   //
 158   // This algorithm is only problematic if the user consistently keeps
 159   // adjusting their clock backwards in increments smaller than the expiration
 160   // TTL, in which case, cached elements continue to be added. However,
 161   // because the cache has a fixed upper bound, if no entries are expired, a
 162   // 'random' entry will be, thus keeping the memory constraints bounded over
 163   // time.
 164   return now.verification_time >= expiration.verification_time &&
 165          now.verification_time < expiration.expiration_time;
 166 };
 167
 168 // Represents the output and result callback of a request. The
 169 // CertVerifierRequest is owned by the caller that initiated the call to
 170 // CertVerifier::Verify().
 171 class CertVerifierRequest : public base::LinkNode<CertVerifierRequest>,
 172                             public CertVerifier::Request {
 173  public:
 174   CertVerifierRequest(CertVerifierJob* job,
 175                       const CompletionCallback& callback,
 176                       CertVerifyResult* verify_result,
 177                       const BoundNetLog& net_log)
 178       : job_(job),
 179         callback_(callback),
 180         verify_result_(verify_result),
 181         net_log_(net_log) {
 182     net_log_.BeginEvent(NetLog::TYPE_CERT_VERIFIER_REQUEST);
 183   }
 184
 185   // Cancels the request.
 186   ~CertVerifierRequest() override {
 187     if (job_) {
 188       // Cancel the outstanding request.
 189       net_log_.AddEvent(NetLog::TYPE_CANCELLED);
 190       net_log_.EndEvent(NetLog::TYPE_CERT_VERIFIER_REQUEST);
 191
 192       // Remove the request from the Job. No attempt is made to cancel the job
 193       // even though it may no longer have any requests attached to it. Because
 194       // it is running on a worker thread aborting it isn't feasible.
 195       RemoveFromList();
 196     }
 197   }
 198
 199   // Copies the contents of |verify_result| to the caller's
 200   // CertVerifyResult and calls the callback.
 201   void Post(const MultiThreadedCertVerifier::CachedResult& verify_result) {
 202     DCHECK(job_);
 203     job_ = nullptr;
 204
 205     net_log_.EndEvent(NetLog::TYPE_CERT_VERIFIER_REQUEST);
 206     *verify_result_ = verify_result.result;
 207
 208     base::ResetAndReturn(&callback_).Run(verify_result.error);
 209   }
 210
 211   void OnJobCancelled() {
 212     job_ = nullptr;
 213     callback_.Reset();
 214   }
 215
 216   const BoundNetLog& net_log() const { return net_log_; }
 217
 218  private:
 219   CertVerifierJob* job_;  // Not owned.
 220   CompletionCallback callback_;
 221   CertVerifyResult* verify_result_;
 222   const BoundNetLog net_log_;
 223 };
 224
 225 // DoVerifyOnWorkerThread runs the verification synchronously on a worker
 226 // thread. The output parameters (error and result) must remain alive.
 227 void DoVerifyOnWorkerThread(const scoped_refptr<CertVerifyProc>& verify_proc,
 228                             const scoped_refptr<X509Certificate>& cert,
 229                             const std::string& hostname,
 230                             const std::string& ocsp_response,
 231                             int flags,
 232                             const scoped_refptr<CRLSet>& crl_set,
 233                             const CertificateList& additional_trust_anchors,
 234                             int* error,
 235                             CertVerifyResult* result) {
 236   *error = verify_proc->Verify(cert.get(), hostname, ocsp_response, flags,
 237                                crl_set.get(), additional_trust_anchors, result);
 238
 239 #if defined(USE_NSS_CERTS) || defined(OS_IOS)
 240     // Detach the thread from NSPR.
 241     // Calling NSS functions attaches the thread to NSPR, which stores
 242     // the NSPR thread ID in thread-specific data.
 243     // The threads in our thread pool terminate after we have called
 244     // PR_Cleanup.  Unless we detach them from NSPR, net_unittests gets
 245     // segfaults on shutdown when the threads' thread-specific data
 246     // destructors run.
 247     PR_DetachThread();
 248 #endif
 249 }
 250
 251 // CertVerifierJob lives only on the verifier's origin message loop.
 252 class CertVerifierJob {
 253  public:
 254   CertVerifierJob(const MultiThreadedCertVerifier::RequestParams& key,
 255                   NetLog* net_log,
 256                   X509Certificate* cert,
 257                   MultiThreadedCertVerifier* cert_verifier)
 258       : key_(key),
 259         start_time_(base::TimeTicks::Now()),
 260         net_log_(BoundNetLog::Make(net_log, NetLog::SOURCE_CERT_VERIFIER_JOB)),
 261         cert_verifier_(cert_verifier),
 262         is_first_job_(false),
 263         weak_ptr_factory_(this) {
 264     net_log_.BeginEvent(
 265         NetLog::TYPE_CERT_VERIFIER_JOB,
 266         base::Bind(&NetLogX509CertificateCallback, base::Unretained(cert)));
 267   }
 268
 269   // Indicates whether this was the first job started by the CertVerifier. This
 270   // is only used for logging certain UMA stats.
 271   void set_is_first_job(bool is_first_job) { is_first_job_ = is_first_job; }
 272
 273   const MultiThreadedCertVerifier::RequestParams& key() const { return key_; }
 274
 275   // Posts a task to the worker pool to do the verification. Once the
 276   // verification has completed on the worker thread, it will call
 277   // OnJobCompleted() on the origin thread.
 278   bool Start(const scoped_refptr<CertVerifyProc>& verify_proc,
 279              const scoped_refptr<X509Certificate>& cert,
 280              const std::string& hostname,
 281              const std::string& ocsp_response,
 282              int flags,
 283              const scoped_refptr<CRLSet>& crl_set,
 284              const CertificateList& additional_trust_anchors) {
 285     // Owned by the bound reply callback.
 286     scoped_ptr<MultiThreadedCertVerifier::CachedResult> owned_result(
 287         new MultiThreadedCertVerifier::CachedResult());
 288
 289     // Parameter evaluation order is undefined in C++. Ensure the pointer value
 290     // is gotten before calling base::Passed().
 291     auto result = owned_result.get();
 292
 293     return base::WorkerPool::PostTaskAndReply(
 294         FROM_HERE,
 295         base::Bind(&DoVerifyOnWorkerThread, verify_proc, cert, hostname,
 296                    ocsp_response, flags, crl_set, additional_trust_anchors,
 297                    &result->error, &result->result),
 298         base::Bind(&CertVerifierJob::OnJobCompleted,
 299                    weak_ptr_factory_.GetWeakPtr(), base::Passed(&owned_result)),
 300         true /* task is slow */);
 301   }
 302
 303   ~CertVerifierJob() {
 304     // If the job is in progress, cancel it.
 305     if (cert_verifier_) {
 306       cert_verifier_ = nullptr;
 307
 308       net_log_.AddEvent(NetLog::TYPE_CANCELLED);
 309       net_log_.EndEvent(NetLog::TYPE_CERT_VERIFIER_JOB);
 310
 311       // Notify each request of the cancellation.
 312       for (base::LinkNode<CertVerifierRequest>* it = requests_.head();
 313            it != requests_.end(); it = it->next()) {
 314         it->value()->OnJobCancelled();
 315       }
 316     }
 317   }
 318
 319   // Creates and attaches a request to the Job.
 320   scoped_ptr<CertVerifierRequest> CreateRequest(
 321       const CompletionCallback& callback,
 322       CertVerifyResult* verify_result,
 323       const BoundNetLog& net_log) {
 324     scoped_ptr<CertVerifierRequest> request(
 325         new CertVerifierRequest(this, callback, verify_result, net_log));
 326
 327     request->net_log().AddEvent(
 328         NetLog::TYPE_CERT_VERIFIER_REQUEST_BOUND_TO_JOB,
 329         net_log_.source().ToEventParametersCallback());
 330
 331     requests_.Append(request.get());
 332     return request.Pass();
 333   }
 334
 335  private:
 336   using RequestList = base::LinkedList<CertVerifierRequest>;
 337
 338   // Called on completion of the Job to log UMA metrics and NetLog events.
 339   void LogMetrics(
 340       const MultiThreadedCertVerifier::CachedResult& verify_result) {
 341     net_log_.EndEvent(
 342         NetLog::TYPE_CERT_VERIFIER_JOB,
 343         base::Bind(&CertVerifyResultCallback, verify_result.result));
 344     base::TimeDelta latency = base::TimeTicks::Now() - start_time_;
 345     UMA_HISTOGRAM_CUSTOM_TIMES("Net.CertVerifier_Job_Latency",
 346                                latency,
 347                                base::TimeDelta::FromMilliseconds(1),
 348                                base::TimeDelta::FromMinutes(10),
 349                                100);
 350     if (is_first_job_) {
 351       UMA_HISTOGRAM_CUSTOM_TIMES("Net.CertVerifier_First_Job_Latency",
 352                                  latency,
 353                                  base::TimeDelta::FromMilliseconds(1),
 354                                  base::TimeDelta::FromMinutes(10),
 355                                  100);
 356     }
 357   }
 358
 359   void OnJobCompleted(
 360       scoped_ptr<MultiThreadedCertVerifier::CachedResult> verify_result) {
 361     scoped_ptr<CertVerifierJob> keep_alive = cert_verifier_->RemoveJob(this);
 362
 363     LogMetrics(*verify_result);
 364     cert_verifier_->SaveResultToCache(key_, *verify_result);
 365     cert_verifier_ = nullptr;
 366
 367     // TODO(eroman): If the cert_verifier_ is deleted from within one of the
 368     // callbacks, any remaining requests for that job should be cancelled. Right
 369     // now they will be called.
 370     while (!requests_.empty()) {
 371       base::LinkNode<CertVerifierRequest>* request = requests_.head();
 372       request->RemoveFromList();
 373       request->value()->Post(*verify_result);
 374     }
 375   }
 376
 377   const MultiThreadedCertVerifier::RequestParams key_;
 378   const base::TimeTicks start_time_;
 379
 380   RequestList requests_;  // Non-owned.
 381
 382   const BoundNetLog net_log_;
 383   MultiThreadedCertVerifier* cert_verifier_;  // Non-owned.
 384
 385   bool is_first_job_;
 386   base::WeakPtrFactory<CertVerifierJob> weak_ptr_factory_;
 387 };
 388
 389 MultiThreadedCertVerifier::MultiThreadedCertVerifier(
 390     CertVerifyProc* verify_proc)
 391     : cache_(kMaxCacheEntries),
 392       requests_(0),
 393       cache_hits_(0),
 394       inflight_joins_(0),
 395       verify_proc_(verify_proc),
 396       trust_anchor_provider_(NULL) {
 397   CertDatabase::GetInstance()->AddObserver(this);
 398 }
 399
 400 MultiThreadedCertVerifier::~MultiThreadedCertVerifier() {
 401   STLDeleteElements(&inflight_);
 402   CertDatabase::GetInstance()->RemoveObserver(this);
 403 }
 404
 405 void MultiThreadedCertVerifier::SetCertTrustAnchorProvider(
 406     CertTrustAnchorProvider* trust_anchor_provider) {
 407   DCHECK(CalledOnValidThread());
 408   trust_anchor_provider_ = trust_anchor_provider;
 409 }
 410
 411 int MultiThreadedCertVerifier::Verify(X509Certificate* cert,
 412                                       const std::string& hostname,
 413                                       const std::string& ocsp_response,
 414                                       int flags,
 415                                       CRLSet* crl_set,
 416                                       CertVerifyResult* verify_result,
 417                                       const CompletionCallback& callback,
 418                                       scoped_ptr<Request>* out_req,
 419                                       const BoundNetLog& net_log) {
 420   out_req->reset();
 421
 422   DCHECK(CalledOnValidThread());
 423
 424   if (callback.is_null() || !verify_result || hostname.empty())
 425     return ERR_INVALID_ARGUMENT;
 426
 427   requests_++;
 428
 429   const CertificateList empty_cert_list;
 430   const CertificateList& additional_trust_anchors =
 431       trust_anchor_provider_ ?
 432           trust_anchor_provider_->GetAdditionalTrustAnchors() : empty_cert_list;
 433
 434   const RequestParams key(cert->fingerprint(), cert->ca_fingerprint(), hostname,
 435                           ocsp_response, flags, additional_trust_anchors);
 436   const CertVerifierCache::value_type* cached_entry =
 437       cache_.Get(key, CacheValidityPeriod(base::Time::Now()));
 438   if (cached_entry) {
 439     ++cache_hits_;
 440     *verify_result = cached_entry->result;
 441     return cached_entry->error;
 442   }
 443
 444   // No cache hit. See if an identical request is currently in flight.
 445   CertVerifierJob* job = FindJob(key);
 446   if (job) {
 447     // An identical request is in flight already. We'll just attach our
 448     // callback.
 449     inflight_joins_++;
 450   } else {
 451     // Need to make a new job.
 452     scoped_ptr<CertVerifierJob> new_job(
 453         new CertVerifierJob(key, net_log.net_log(), cert, this));
 454
 455     if (!new_job->Start(verify_proc_, cert, hostname, ocsp_response, flags,
 456                         crl_set, additional_trust_anchors)) {
 457       // TODO(wtc): log to the NetLog.
 458       LOG(ERROR) << "CertVerifierWorker couldn't be started.";
 459       return ERR_INSUFFICIENT_RESOURCES;  // Just a guess.
 460     }
 461
 462     job = new_job.release();
 463     inflight_.insert(job);
 464
 465     if (requests_ == 1)
 466       job->set_is_first_job(true);
 467   }
 468
 469   scoped_ptr<CertVerifierRequest> request =
 470       job->CreateRequest(callback, verify_result, net_log);
 471   *out_req = request.Pass();
 472   return ERR_IO_PENDING;
 473 }
 474
 475 bool MultiThreadedCertVerifier::SupportsOCSPStapling() {
 476   return verify_proc_->SupportsOCSPStapling();
 477 }
 478
 479 MultiThreadedCertVerifier::RequestParams::RequestParams(
 480     const SHA1HashValue& cert_fingerprint_arg,
 481     const SHA1HashValue& ca_fingerprint_arg,
 482     const std::string& hostname_arg,
 483     const std::string& ocsp_response_arg,
 484     int flags_arg,
 485     const CertificateList& additional_trust_anchors)
 486     : hostname(hostname_arg), flags(flags_arg) {
 487   hash_values.reserve(3 + additional_trust_anchors.size());
 488   SHA1HashValue ocsp_hash;
 489   base::SHA1HashBytes(
 490       reinterpret_cast<const unsigned char*>(ocsp_response_arg.data()),
 491       ocsp_response_arg.size(), ocsp_hash.data);
 492   hash_values.push_back(ocsp_hash);
 493   hash_values.push_back(cert_fingerprint_arg);
 494   hash_values.push_back(ca_fingerprint_arg);
 495   for (size_t i = 0; i < additional_trust_anchors.size(); ++i)
 496     hash_values.push_back(additional_trust_anchors[i]->fingerprint());
 497 }
 498
 499 MultiThreadedCertVerifier::RequestParams::~RequestParams() {}
 500
 501 bool MultiThreadedCertVerifier::RequestParams::operator<(
 502     const RequestParams& other) const {
 503   // |flags| is compared before |cert_fingerprint|, |ca_fingerprint|,
 504   // |hostname|, and |ocsp_response|, under assumption that integer comparisons
 505   // are faster than memory and string comparisons.
 506   if (flags != other.flags)
 507     return flags < other.flags;
 508   if (hostname != other.hostname)
 509     return hostname < other.hostname;
 510   return std::lexicographical_compare(
 511       hash_values.begin(), hash_values.end(), other.hash_values.begin(),
 512       other.hash_values.end(), SHA1HashValueLessThan());
 513 }
 514
 515 bool MultiThreadedCertVerifier::JobComparator::operator()(
 516     const CertVerifierJob* job1,
 517     const CertVerifierJob* job2) const {
 518   return job1->key() < job2->key();
 519 }
 520
 521 void MultiThreadedCertVerifier::SaveResultToCache(const RequestParams& key,
 522                                                   const CachedResult& result) {
 523   DCHECK(CalledOnValidThread());
 524
 525   base::Time now = base::Time::Now();
 526   cache_.Put(
 527       key, result, CacheValidityPeriod(now),
 528       CacheValidityPeriod(now, now + base::TimeDelta::FromSeconds(kTTLSecs)));
 529 }
 530
 531 scoped_ptr<CertVerifierJob> MultiThreadedCertVerifier::RemoveJob(
 532     CertVerifierJob* job) {
 533   DCHECK(CalledOnValidThread());
 534   bool erased_job = inflight_.erase(job) == 1;
 535   DCHECK(erased_job);
 536   return make_scoped_ptr(job);
 537 }
 538
 539 void MultiThreadedCertVerifier::OnCACertChanged(
 540     const X509Certificate* cert) {
 541   DCHECK(CalledOnValidThread());
 542
 543   ClearCache();
 544 }
 545
 546 struct MultiThreadedCertVerifier::JobToRequestParamsComparator {
 547   bool operator()(const CertVerifierJob* job,
 548                   const MultiThreadedCertVerifier::RequestParams& value) const {
 549     return job->key() < value;
 550   }
 551 };
 552
 553 CertVerifierJob* MultiThreadedCertVerifier::FindJob(const RequestParams& key) {
 554   DCHECK(CalledOnValidThread());
 555
 556   // The JobSet is kept in sorted order so items can be found using binary
 557   // search.
 558   auto it = std::lower_bound(inflight_.begin(), inflight_.end(), key,
 559                              JobToRequestParamsComparator());
 560   if (it != inflight_.end() && !(key < (*it)->key()))
 561     return *it;
 562   return nullptr;
 563 }
 564
 565 }  // namespace net
 566