// Copyright (c) 2012 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/cert/multi_threaded_cert_verifier.h"

#include <algorithm>
#include <memory>
#include <utility>

#include "base/bind.h"
#include "base/bind_helpers.h"
#include "base/callback_helpers.h"
#include "base/compiler_specific.h"
#include "base/containers/linked_list.h"
#include "base/memory/ptr_util.h"
#include "base/message_loop/message_loop.h"
#include "base/metrics/histogram_macros.h"
#include "base/profiler/scoped_tracker.h"
#include "base/sha1.h"
#include "base/stl_util.h"
#include "base/threading/worker_pool.h"
#include "base/time/time.h"
#include "base/trace_event/trace_event.h"
#include "base/values.h"
#include "net/base/hash_value.h"
#include "net/base/net_errors.h"
#include "net/cert/cert_verify_proc.h"
#include "net/cert/cert_verify_result.h"
#include "net/cert/crl_set.h"
#include "net/cert/x509_certificate.h"
#include "net/cert/x509_certificate_net_log_param.h"
#include "net/log/net_log.h"

#if defined(USE_NSS_CERTS)
#include <private/pprthred.h>  // PR_DetachThread
#endif

namespace net {

////////////////////////////////////////////////////////////////////////////
//
// MultiThreadedCertVerifier is a thread-unsafe object which lives, dies, and is
// operated on a single thread, henceforth referred to as the "origin" thread.
//
// When an incoming Verify() request is received, MultiThreadedCertVerifier
// checks if there is an outstanding "job" (CertVerifierJob) in progress that
// can service the request. If there is, the request is attached to that job.
// Otherwise a new job is started.
//
// A job (CertVerifierJob) is a way to de-duplicate requests that are
// fundamentally doing the same verification. CertVerifierJob is similarly
// thread-unsafe and lives on the origin thread.
//
// To do the actual work, CertVerifierJob posts a task to WorkerPool
// (PostTaskAndReply), and on completion notifies all requests attached to it.
//
// Cancellation:
//
// There are two ways for a request to be cancelled.
//
// (1) When the caller explicitly frees the Request.
//
//     If the request was in-flight (attached to a job), then it is detached.
//     Note that no effort is made to reap jobs which have no attached requests.
//     (Because the worker task isn't cancelable).
//
// (2) When the MultiThreadedCertVerifier is deleted.
//
//     This automatically cancels all outstanding requests. This is accomplished
//     by deleting each of the jobs owned by the MultiThreadedCertVerifier,
//     whose destructor in turn marks each attached request as canceled.
//
// TODO(eroman): If the MultiThreadedCertVerifier is deleted from within a
// callback, the remaining requests in the completing job will NOT be cancelled.

namespace {

std::unique_ptr<base::Value> CertVerifyResultCallback(
    const CertVerifyResult& verify_result,
    NetLogCaptureMode capture_mode) {
  std::unique_ptr<base::DictionaryValue> results(new base::DictionaryValue());
  results->SetBoolean("has_md5", verify_result.has_md5);
  results->SetBoolean("has_md2", verify_result.has_md2);
  results->SetBoolean("has_md4", verify_result.has_md4);
  results->SetBoolean("is_issued_by_known_root",
                      verify_result.is_issued_by_known_root);
  results->SetBoolean("is_issued_by_additional_trust_anchor",
                      verify_result.is_issued_by_additional_trust_anchor);
  results->SetBoolean("common_name_fallback_used",
                      verify_result.common_name_fallback_used);
  results->SetInteger("cert_status", verify_result.cert_status);
  results->Set("verified_cert",
               NetLogX509CertificateCallback(verify_result.verified_cert.get(),
                                             capture_mode));

  std::unique_ptr<base::ListValue> hashes(new base::ListValue());
  for (std::vector<HashValue>::const_iterator it =
           verify_result.public_key_hashes.begin();
       it != verify_result.public_key_hashes.end();
       ++it) {
    hashes->AppendString(it->ToString());
  }
  results->Set("public_key_hashes", std::move(hashes));

  return std::move(results);
}

// Helper structure used to keep |verify_result| alive for the lifetime of
// the verification on the worker thread, and to communicate it back to the
// calling thread.
struct ResultHelper {
  int error;
  CertVerifyResult result;
};

}  // namespace

// Represents the output and result callback of a request. The
// CertVerifierRequest is owned by the caller that initiated the call to
// CertVerifier::Verify().
class CertVerifierRequest : public base::LinkNode<CertVerifierRequest>,
                            public CertVerifier::Request {
 public:
  CertVerifierRequest(CertVerifierJob* job,
                      const CompletionCallback& callback,
                      CertVerifyResult* verify_result,
                      const BoundNetLog& net_log)
      : job_(job),
        callback_(callback),
        verify_result_(verify_result),
        net_log_(net_log) {
    net_log_.BeginEvent(NetLog::TYPE_CERT_VERIFIER_REQUEST);
  }

  // Cancels the request.
  ~CertVerifierRequest() override {
    if (job_) {
      // Cancel the outstanding request.
      net_log_.AddEvent(NetLog::TYPE_CANCELLED);
      net_log_.EndEvent(NetLog::TYPE_CERT_VERIFIER_REQUEST);

      // Remove the request from the Job. No attempt is made to cancel the job
      // even though it may no longer have any requests attached to it. Because
      // it is running on a worker thread aborting it isn't feasible.
      RemoveFromList();
    }
  }

  // Copies the contents of |verify_result| to the caller's
  // CertVerifyResult and calls the callback.
  void Post(const ResultHelper& verify_result) {
    DCHECK(job_);
    job_ = nullptr;

    net_log_.EndEvent(NetLog::TYPE_CERT_VERIFIER_REQUEST);
    *verify_result_ = verify_result.result;

    base::ResetAndReturn(&callback_).Run(verify_result.error);
  }

  void OnJobCancelled() {
    job_ = nullptr;
    callback_.Reset();
  }

  const BoundNetLog& net_log() const { return net_log_; }

 private:
  CertVerifierJob* job_;  // Not owned.
  CompletionCallback callback_;
  CertVerifyResult* verify_result_;
  const BoundNetLog net_log_;
};

// DoVerifyOnWorkerThread runs the verification synchronously on a worker
// thread. The output parameters (error and result) must remain alive.
void DoVerifyOnWorkerThread(const scoped_refptr<CertVerifyProc>& verify_proc,
                            const scoped_refptr<X509Certificate>& cert,
                            const std::string& hostname,
                            const std::string& ocsp_response,
                            int flags,
                            const scoped_refptr<CRLSet>& crl_set,
                            const CertificateList& additional_trust_anchors,
                            int* error,
                            CertVerifyResult* result) {
  TRACE_EVENT0("net", "DoVerifyOnWorkerThread");
  *error = verify_proc->Verify(cert.get(), hostname, ocsp_response, flags,
                               crl_set.get(), additional_trust_anchors, result);

#if defined(USE_NSS_CERTS)
  // Detach the thread from NSPR.
  // Calling NSS functions attaches the thread to NSPR, which stores
  // the NSPR thread ID in thread-specific data.
  // The threads in our thread pool terminate after we have called
  // PR_Cleanup.  Unless we detach them from NSPR, net_unittests gets
  // segfaults on shutdown when the threads' thread-specific data
  // destructors run.
  PR_DetachThread();
#endif
}

// CertVerifierJob lives only on the verifier's origin message loop.
class CertVerifierJob {
 public:
  CertVerifierJob(const CertVerifier::RequestParams& key,
                  NetLog* net_log,
                  MultiThreadedCertVerifier* cert_verifier)
      : key_(key),
        start_time_(base::TimeTicks::Now()),
        net_log_(BoundNetLog::Make(net_log, NetLog::SOURCE_CERT_VERIFIER_JOB)),
        cert_verifier_(cert_verifier),
        is_first_job_(false),
        weak_ptr_factory_(this) {
    net_log_.BeginEvent(NetLog::TYPE_CERT_VERIFIER_JOB,
                        base::Bind(&NetLogX509CertificateCallback,
                                   base::Unretained(key.certificate().get())));
  }

  // Indicates whether this was the first job started by the CertVerifier. This
  // is only used for logging certain UMA stats.
  void set_is_first_job(bool is_first_job) { is_first_job_ = is_first_job; }

  const CertVerifier::RequestParams& key() const { return key_; }

  // Posts a task to the worker pool to do the verification. Once the
  // verification has completed on the worker thread, it will call
  // OnJobCompleted() on the origin thread.
  bool Start(const scoped_refptr<CertVerifyProc>& verify_proc,
             const scoped_refptr<CRLSet>& crl_set) {
    // Owned by the bound reply callback.
    std::unique_ptr<ResultHelper> owned_result(new ResultHelper());

    // Parameter evaluation order is undefined in C++. Ensure the pointer value
    // is gotten before calling base::Passed().
    auto* result = owned_result.get();

    return base::WorkerPool::PostTaskAndReply(
        FROM_HERE,
        base::Bind(&DoVerifyOnWorkerThread, verify_proc, key_.certificate(),
                   key_.hostname(), key_.ocsp_response(), key_.flags(), crl_set,
                   key_.additional_trust_anchors(), &result->error,
                   &result->result),
        base::Bind(&CertVerifierJob::OnJobCompleted,
                   weak_ptr_factory_.GetWeakPtr(), base::Passed(&owned_result)),
        true /* task is slow */);
  }

  ~CertVerifierJob() {
    // If the job is in progress, cancel it.
    if (cert_verifier_) {
      cert_verifier_ = nullptr;

      net_log_.AddEvent(NetLog::TYPE_CANCELLED);
      net_log_.EndEvent(NetLog::TYPE_CERT_VERIFIER_JOB);

      // Notify each request of the cancellation.
      for (base::LinkNode<CertVerifierRequest>* it = requests_.head();
           it != requests_.end(); it = it->next()) {
        it->value()->OnJobCancelled();
      }
    }
  }

  // Creates and attaches a request to the Job.
  std::unique_ptr<CertVerifierRequest> CreateRequest(
      const CompletionCallback& callback,
      CertVerifyResult* verify_result,
      const BoundNetLog& net_log) {
    std::unique_ptr<CertVerifierRequest> request(
        new CertVerifierRequest(this, callback, verify_result, net_log));

    request->net_log().AddEvent(
        NetLog::TYPE_CERT_VERIFIER_REQUEST_BOUND_TO_JOB,
        net_log_.source().ToEventParametersCallback());

    requests_.Append(request.get());
    return request;
  }

 private:
  using RequestList = base::LinkedList<CertVerifierRequest>;

  // Called on completion of the Job to log UMA metrics and NetLog events.
  void LogMetrics(const ResultHelper& verify_result) {
    net_log_.EndEvent(
        NetLog::TYPE_CERT_VERIFIER_JOB,
        base::Bind(&CertVerifyResultCallback, verify_result.result));
    base::TimeDelta latency = base::TimeTicks::Now() - start_time_;
    UMA_HISTOGRAM_CUSTOM_TIMES("Net.CertVerifier_Job_Latency",
                               latency,
                               base::TimeDelta::FromMilliseconds(1),
                               base::TimeDelta::FromMinutes(10),
                               100);
    if (is_first_job_) {
      UMA_HISTOGRAM_CUSTOM_TIMES("Net.CertVerifier_First_Job_Latency",
                                 latency,
                                 base::TimeDelta::FromMilliseconds(1),
                                 base::TimeDelta::FromMinutes(10),
                                 100);
    }
  }

  void OnJobCompleted(std::unique_ptr<ResultHelper> verify_result) {
    TRACE_EVENT0("net", "CertVerifierJob::OnJobCompleted");
    std::unique_ptr<CertVerifierJob> keep_alive =
        cert_verifier_->RemoveJob(this);

    LogMetrics(*verify_result);
    cert_verifier_ = nullptr;

    // TODO(eroman): If the cert_verifier_ is deleted from within one of the
    // callbacks, any remaining requests for that job should be cancelled. Right
    // now they will be called.
    while (!requests_.empty()) {
      base::LinkNode<CertVerifierRequest>* request = requests_.head();
      request->RemoveFromList();
      request->value()->Post(*verify_result);
    }
  }

  const CertVerifier::RequestParams key_;
  // The tick count of when the job started. This is used to measure how long
  // the job actually took to complete.
  const base::TimeTicks start_time_;

  RequestList requests_;  // Non-owned.

  const BoundNetLog net_log_;
  MultiThreadedCertVerifier* cert_verifier_;  // Non-owned.

  bool is_first_job_;
  base::WeakPtrFactory<CertVerifierJob> weak_ptr_factory_;
};

MultiThreadedCertVerifier::MultiThreadedCertVerifier(
    CertVerifyProc* verify_proc)
    : requests_(0), inflight_joins_(0), verify_proc_(verify_proc) {}

MultiThreadedCertVerifier::~MultiThreadedCertVerifier() {
  STLDeleteElements(&inflight_);
}

int MultiThreadedCertVerifier::Verify(const RequestParams& params,
                                      CRLSet* crl_set,
                                      CertVerifyResult* verify_result,
                                      const CompletionCallback& callback,
                                      std::unique_ptr<Request>* out_req,
                                      const BoundNetLog& net_log) {
  out_req->reset();

  DCHECK(CalledOnValidThread());

  if (callback.is_null() || !verify_result || params.hostname().empty())
    return ERR_INVALID_ARGUMENT;

  requests_++;

  // See if an identical request is currently in flight.
  CertVerifierJob* job = FindJob(params);
  if (job) {
    // An identical request is in flight already. We'll just attach our
    // callback.
    inflight_joins_++;
  } else {
    // Need to make a new job.
    std::unique_ptr<CertVerifierJob> new_job(
        new CertVerifierJob(params, net_log.net_log(), this));

    if (!new_job->Start(verify_proc_, crl_set)) {
      // TODO(wtc): log to the NetLog.
      LOG(ERROR) << "CertVerifierJob couldn't be started.";
      return ERR_INSUFFICIENT_RESOURCES;  // Just a guess.
    }

    job = new_job.release();
    inflight_.insert(job);

    if (requests_ == 1)
      job->set_is_first_job(true);
  }

  std::unique_ptr<CertVerifierRequest> request =
      job->CreateRequest(callback, verify_result, net_log);
  *out_req = std::move(request);
  return ERR_IO_PENDING;
}

bool MultiThreadedCertVerifier::SupportsOCSPStapling() {
  return verify_proc_->SupportsOCSPStapling();
}

bool MultiThreadedCertVerifier::JobComparator::operator()(
    const CertVerifierJob* job1,
    const CertVerifierJob* job2) const {
  return job1->key() < job2->key();
}

std::unique_ptr<CertVerifierJob> MultiThreadedCertVerifier::RemoveJob(
    CertVerifierJob* job) {
  DCHECK(CalledOnValidThread());
  bool erased_job = inflight_.erase(job) == 1;
  DCHECK(erased_job);
  return base::WrapUnique(job);
}

struct MultiThreadedCertVerifier::JobToRequestParamsComparator {
  bool operator()(const CertVerifierJob* job,
                  const CertVerifier::RequestParams& value) const {
    return job->key() < value;
  }
};

CertVerifierJob* MultiThreadedCertVerifier::FindJob(const RequestParams& key) {
  DCHECK(CalledOnValidThread());

  // The JobSet is kept in sorted order so items can be found using binary
  // search.
  auto it = std::lower_bound(inflight_.begin(), inflight_.end(), key,
                             JobToRequestParamsComparator());
  if (it != inflight_.end() && !(key < (*it)->key()))
    return *it;
  return nullptr;
}

}  // namespace net