Improve performance of proxy resolver by tracing DNS dependencies.

net/proxy/proxy_resolver_v8_tracing.cc

Index: net/proxy/proxy_resolver_v8_tracing.cc
diff --git a/net/proxy/proxy_resolver_v8_tracing.cc b/net/proxy/proxy_resolver_v8_tracing.cc
new file mode 100644
index 0000000000000000000000000000000000000000..0537d6ebb4c3a845a008b076a253715c570e0ab5
--- /dev/null
+++ b/net/proxy/proxy_resolver_v8_tracing.cc
@@ -0,0 +1,956 @@
+// Copyright (c) 2013 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/proxy/proxy_resolver_v8_tracing.h"
+
+#include "base/bind.h"
+#include "base/md5.h"
+#include "base/message_loop_proxy.h"
+#include "base/string_number_conversions.h"
+#include "base/string_util.h"
+#include "base/stringprintf.h"
+#include "base/synchronization/cancellation_flag.h"
+#include "base/synchronization/waitable_event.h"
+#include "base/threading/thread.h"
+#include "base/threading/thread_restrictions.h"
+#include "base/values.h"
+#include "net/base/address_list.h"
+#include "net/base/host_resolver.h"
+#include "net/base/net_errors.h"
+#include "net/base/net_log.h"
+#include "net/proxy/proxy_info.h"
+#include "net/proxy/proxy_resolver_error_observer.h"
+#include "net/proxy/proxy_resolver_v8.h"
+
+// The intent of this class is explained in the design document:
+// https://docs.google.com/a/chromium.org/document/d/16Ij5OcVnR3s0MH4Z5XkhI9VTPoMJdaBn9rKreAmGOdE/edit
+//
+// In a nutshell, PAC scripts are Javascript programs and may depend on
+// network I/O, by calling functions like dnsResolve().
+//
+// This is problematic since functions such as dnsResolve() will block the
+// Javascript execution until the DNS result is availble, thereby stalling the
+// PAC thread, which hurts the ability to process parallel proxy resolves.
+// An obvious solution is to simply start more PAC threads, however this scales
+// poorly, which hurts the ability to process parallel proxy resolves.
+//
+// The solution in ProxyResolverV8Tracing is to model PAC scripts as being
+// deterministic, and depending only on the inputted URL. When the script
+// issues a dnsResolve() for a yet unresolved hostname, the Javascript
+// execution is "aborted", and then re-started once the DNS result is
+// known.
+namespace net {
+
+namespace {
+
+// Upper bound on how many *unique* DNS resolves a PAC script is allowed
+// to make. This is a failsafe in case the logic to detect PAC scripts
+// incompatible with the tracing optimization doesn't work. It is not
+// expected for well behaved scripts to hit this.
+const size_t kMaxUniqueResolveDnsPerExec = 20;
+
+// Approximate number of bytes to use for buffering alerts() and errors.
+// This is a failsafe in case repeated executions of the script causes
+// too much memory bloat. It is not expected for well behaved scripts to
+// hit this. (In fact normal scripts should not even have alerts() or errors).
+const size_t kMaxAlertsAndErrorsBytes = 2048;
+
+// Compares two MD5 digests for equality. The second digest is given as a
+// non-finalized MD5Context.
+bool MD5DigestEquals(const base::MD5Digest& digest1,
+                     const base::MD5Context& digest2_context) {
+  // Finalize the context into a digest. (Make a copy first
+  // because MD5Final() mutates the context).
+  base::MD5Digest digest2;
+  base::MD5Context digest2_copy;
+  memcpy(&digest2_copy[0], &digest2_context[0], sizeof(base::MD5Context));
+  base::MD5Final(&digest2, &digest2_copy);
+
+  return memcmp(&digest1, &digest2, sizeof(base::MD5Digest)) == 0;
+}
+
+// Returns event parameters for a PAC error message (line number + message).
+base::Value* NetLogErrorCallback(int line_number,
+                                 const string16* message,
+                                 NetLog::LogLevel /* log_level */) {
+  base::DictionaryValue* dict = new base::DictionaryValue();
+  dict->SetInteger("line_number", line_number);
+  dict->SetString("message", *message);
+  return dict;
+}
+
+}  // namespace
+
+// The Job class is responsible for executing GetProxyForURL() and
+// SetPacScript(), since both of these operations share similar code.
+//
+// The DNS for these operations can operate in either blocking or
+// non-blocking mode. Blocking mode is used as a fallback when the PAC script
+// seems to be misbehaving under the tracing optimization.
+//
+// Note that this class runs on both the origin thread and a worker
+// thread. Most methods are expected to be used exclusively on one thread
+// or the other.
+//
+// The lifetime of Jobs does not exceed that of the ProxyResolverV8Tracing that
+// spawned it. Destruction might happen on either the origin thread or the
+// worker thread.
+class ProxyResolverV8Tracing::Job
+    : public base::RefCountedThreadSafe<ProxyResolverV8Tracing::Job>,
+      public ProxyResolverV8::JSBindings {
+ public:
+  // |parent| is non-owned and references the ProxyResolverV8Tracing that
+  // spawned this Job.

[mmenke, 2013/01/24 21:06:33]

Suggest separating into two sentences, or making it a compound sentence.

Kept on reading this as "|parent| is [non-owned and references ...]" rather than
"|parent [is non-owned] and [references ...]"

[eroman, 2013/01/25 03:02:01]

Done.

+  explicit Job(ProxyResolverV8Tracing* parent);
+
+  void StartSetPacScript(

[mmenke, 2013/01/24 21:06:33]

Suggest a comment either here or in the class description that the public
functions are all only called on the origin thread.

[eroman, 2013/01/25 03:02:01]

Done.

+      const scoped_refptr<ProxyResolverScriptData>& script_data,
+      const CompletionCallback& callback);
+
+  void StartGetProxyForURL(const GURL& url,
+                           ProxyInfo* results,
+                           const BoundNetLog& net_log,
+                           const CompletionCallback& callback);
+
+  void Cancel();
+  LoadState GetLoadState() const;
+
+ private:
+  typedef std::map<std::string, std::string> DnsCache;
+  friend class base::RefCountedThreadSafe<ProxyResolverV8Tracing::Job>;
+
+  enum Operation {
+    SET_PAC_SCRIPT,
+    GET_PROXY_FOR_URL,
+  };
+
+  struct AlertOrError {
+    bool is_alert;
+    int line_number;
+    string16 message;
+  };
+
+  ~Job();
+
+  void CheckIsOnWorkerThread() const;
+  void CheckIsOnOriginThread() const;
+
+  ProxyResolverV8* v8_resolver();
+  MessageLoop* worker_loop();
+  HostResolver* host_resolver();
+  ProxyResolverErrorObserver* error_observer();
+  NetLog* net_log();
+
+  // Invokes the user's callback.
+  void NotifyCaller(int result);
+  void NotifyCallerOnOriginLoop(int result);
+
+  void Start(Operation op, bool blocking_dns, const CompletionCallback& callback);

[mmenke, 2013/01/24 21:06:33]

nit:  Line too long.

[eroman, 2013/01/25 03:02:01]

Done.

+
+  void ExecuteBlocking();
+  void ExecuteNonBlocking();
+  int ExecuteProxyResolver();
+
+  // Implementation of ProxyResolverv8::JSBindings
+  virtual bool ResolveDns(const std::string& host,
+                          ResolveDnsOperation op,
+                          std::string* output) OVERRIDE;
+  virtual void Alert(const string16& message) OVERRIDE;
+  virtual void OnError(int line_number, const string16& error) OVERRIDE;
+
+  bool ResolveDnsBlocking(const std::string& host,
+                          ResolveDnsOperation op,
+                          std::string* output);
+
+  bool ResolveDnsNonBlocking(const std::string& host,
+                             ResolveDnsOperation op,
+                             std::string* output);
+
+  void DoDnsOperation(const std::string& host, ResolveDnsOperation op,
+                      bool* out_cache_hit);
+  void OnDnsOperationComplete(int result);
+
+  void ScheduleRestartWithBlockingDns();
+  void RestartWithBlockingDns();
+
+  bool GetDnsFromLocalCache(const std::string& host, ResolveDnsOperation op,
+                            std::string* output, bool* return_value);
+
+  void SaveDnsToLocalCache(const std::string& host, ResolveDnsOperation op,
+                           int net_error, const net::AddressList& addresses);
+
+  // Builds a RequestInfo to service the specified PAC DNS operation.
+  static HostResolver::RequestInfo MakeDnsRequestInfo(const std::string& host,
+                                                      ResolveDnsOperation op);
+
+  // Makes a key for looking up |host, op| in |dns_cache_|. Strings are used for
+  // convenience, to avoid defining custom comparators.
+  static std::string MakeDnsCacheKey(const std::string& host,
+                                     ResolveDnsOperation op);
+
+  void HandleAlertOrError(bool is_alert, int line_number,
+                          const string16& message);
+  void DispatchBufferedAlertsAndErrors();
+  void DispatchAlertOrError(bool is_alert, int line_number,
+                            const string16& message);
+
+  void LogEventToCurrentRequestAndGlobally(
+      NetLog::EventType type,
+      const NetLog::ParametersCallback& parameters_callback);
+
+  // The thread which called into ProxyResolverV8Tracing, and on which the
+  // completion callback is expected to run.
+  scoped_refptr<base::MessageLoopProxy> origin_loop_;
+
+  // The ProxyResolverV8Tracing which spawned this Job.
+  // Initialized on origin thread and then accessed from both threads.
+  ProxyResolverV8Tracing* parent_;
+
+  // The callback to run (on the origin thread) when the Job finishes.
+  // Should only be accessed from origin thread.
+  CompletionCallback callback_;
+
+  // Flag to indicate whether the request has been cancelled.
+  base::CancellationFlag cancelled_;
+
+  // The operation that this Job is running.
+  // Initialized on origin thread and then accessed from both threads.
+  Operation operation_;
+
+  // The DNS mode for this Job.
+  // Initialized on origin thread and then accessed from both threads.
+  bool blocking_dns_;
+
+  // Used to block the worker thread on a DNS operation taking place on the
+  // origin thread.
+  base::WaitableEvent event_;
+
+  // Map of DNS operations completed so far. Written into on the origin thread
+  // and read on the worker thread.
+  DnsCache dns_cache_;
+
+  // -------------------------------------------------------
+  // State specific to SET_PAC_SCRIPT.
+  // -------------------------------------------------------
+
+  scoped_refptr<ProxyResolverScriptData> script_data_;
+
+  // -------------------------------------------------------
+  // State specific to GET_PROXY_FOR_URL.
+  // -------------------------------------------------------
+
+  ProxyInfo* user_results_;  // Owned by caller, lives on origin thread.
+  GURL url_;
+  ProxyInfo results_;
+  BoundNetLog bound_net_log_;
+
+  // ---------------------------------------------------------------------------
+  // State for ExecuteNonBlocking()
+  // ---------------------------------------------------------------------------
+  // These variables are used exclusively on the worker thread and are only
+  // meaningful when executing inside of ExecuteNonBlocking().
+
+  // Whether this execution was abandoned due to a missing DNS dependency.
+  bool abandoned_;
+
+  // Sequence of calls made to ResolveDns() by this execution.
+  int num_dns_;  // Count.
+  base::MD5Context dns_digest_;  // MD5 digest of the parameters.
+
+  // Sequence of calls made to Alert() or OnError() by this execution.
+  std::vector<AlertOrError> alerts_and_errors_;
+  size_t alerts_and_errors_byte_cost_;  // Approximate byte cost of the above.
+
+  // Sequence of calls made to ResolveDns() by the PREVIOUS execution.
+  int last_num_dns_;
+  base::MD5Digest last_dns_digest_;
+
+  // ---------------------------------------------------------------------------
+  // State for pending DNS request.
+  // ---------------------------------------------------------------------------
+  // These variables are used exclusively on the origin thread.
+
+  HostResolver::RequestHandle pending_dns_;
+  // Only meaningful when |pending_dns_|:
+  std::string pending_dns_host_;
+  ResolveDnsOperation pending_dns_op_;
+  AddressList pending_dns_addresses_;
+};
+
+ProxyResolverV8Tracing::Job::Job(ProxyResolverV8Tracing* parent)
+    : origin_loop_(base::MessageLoopProxy::current()),
+  parent_(parent),
+  event_(true, false),
+  last_num_dns_(0),
+  pending_dns_(NULL) {
+}
+
+void ProxyResolverV8Tracing::Job::StartSetPacScript(
+    const scoped_refptr<ProxyResolverScriptData>& script_data,
+    const CompletionCallback& callback) {
+  CheckIsOnOriginThread();
+
+  script_data_ = script_data;
+
+  // Script initialization uses blocking DNS since there isn't any
+  // advantage to using non-blocking mode here. That is because the
+  // parent ProxyService can't submit any ProxyResolve requests until
+  // initialization has completed successfully!
+  Start(SET_PAC_SCRIPT, true /*blocking*/, callback);

[mmenke, 2013/01/24 21:06:33]

If the PAC script changes to a new PAC script, what about ongoing PAC lookups? 
If they aren't cancelled elsewhere, they all may become blocking if the new
script doesn't match the old one, right?

[eroman, 2013/01/25 03:02:01]

There shouldn't be any outstanding PAC requests when calling SetPacScript
(proxy_service.cc is supposed to cancel everything before calling it).

I'll add some comments to that effect for now. I could probably also add a
counter for in-progress jobs to assert this fact, what do you think?

[mmenke, 2013/01/25 05:03:28]

Thought that might be the case, but looks like the MultiThreadedProxyResolver
has some code to handle it.  I like the idea of having a counter for sanity
checking.

[eroman, 2013/01/25 21:42:25]

MutliThreadedProxyResolver asserts that there are no outstanding jobs. I have
added similar assertions to ProxyResolverV8Tracing.

+}
+
+void ProxyResolverV8Tracing::Job::StartGetProxyForURL(
+    const GURL& url,
+    ProxyInfo* results,
+    const BoundNetLog& net_log,
+    const CompletionCallback& callback) {
+  CheckIsOnOriginThread();
+
+  url_ = url;
+  user_results_ = results;
+  bound_net_log_ = net_log;
+
+  Start(GET_PROXY_FOR_URL, false /*non-blocking*/, callback);
+}
+
+void ProxyResolverV8Tracing::Job::Cancel() {
+  CheckIsOnOriginThread();
+
+  // There are three main possibility to consider for cancellation:

[mmenke, 2013/01/24 21:06:33]

five?

[eroman, 2013/01/25 03:02:01]

Done.

+  // (a) The job has been posted to the worker thread, but not yet started

[mmenke, 2013/01/24 21:06:33]

nit:  started->[re]started

[eroman, 2013/01/25 03:02:01]

What i meant here was the first execution, hence "started". the "restart" case
probably falls under (d).

[mmenke, 2013/01/25 05:03:28]

I think it falls under a), actually.  We run a script, it does a host resolver
lookup.  Lookup isn't resolved synchronously, so the task is abandoned.  We get
a result, and post a tast to the worker thread to run again with the newly added
entry to the cache.  queuing this task is much more like the start case than the
pending DNS lookup case.

+  // (b) The script is executing on the worker thread
+  // (c) The script is blocked waiting for DNS
+  // (c) The script has stopped and there is a pending DNS request.

[mmenke, 2013/01/24 21:06:33]

nit:  (d)

[mmenke, 2013/01/24 21:06:33]

(e) The script has a pending NotifyCallerOnOriginLoop.

Worth testing this?  Can't be 100 percent sure we're in this state, but can be
fairly sure.

[eroman, 2013/01/25 03:02:01]

This can probabilistic-ally happen in the CancelSome and CancelAll tests. I
could add some sleeps to make it more likely, what do you think?

[mmenke, 2013/01/25 05:03:28]

I was thinking this:  Start a lookup with a synchronous DNS resolver, wait x
milliseconds.  Run all pending tasks (Don't run until idle - believe there's a
function for this).  Then wait x milliseconds.  Then cancel the task.

+  //
+  // |cancelled_| is read on both the origin thread and worker thread. The
+  // code that runs on the worker thread is littered with checks on
+  // |cancelled_| to break out early.
+  cancelled_.Set();
+
+  // These two assignments are not necessary for correctness. Just defensive
+  // programming to make sure the user-provided data is not used beyond this
+  // point.
+  user_results_ = NULL;
+  callback_ = CompletionCallback();
+
+  if (pending_dns_) {
+    host_resolver()->CancelRequest(pending_dns_);
+    pending_dns_ = NULL;
+  }
+
+  // The worker thread might be blocked waiting for DNS.
+  event_.Signal();
+
+  Release();
+}
+
+LoadState ProxyResolverV8Tracing::Job::GetLoadState() const {
+  CheckIsOnOriginThread();
+
+  if (pending_dns_)
+    return LOAD_STATE_RESOLVING_HOST_IN_PROXY_SCRIPT;
+
+  return LOAD_STATE_RESOLVING_PROXY_FOR_URL;
+}
+
+ProxyResolverV8Tracing::Job::~Job() {
+  DCHECK(!pending_dns_);
+}
+
+void ProxyResolverV8Tracing::Job::CheckIsOnWorkerThread() const {
+  DCHECK_EQ(MessageLoop::current(), parent_->thread_->message_loop());
+}
+
+void ProxyResolverV8Tracing::Job::CheckIsOnOriginThread() const {
+  DCHECK(origin_loop_->BelongsToCurrentThread());
+}
+
+ProxyResolverV8* ProxyResolverV8Tracing::Job::v8_resolver() {
+  return parent_->v8_resolver_.get();
+}
+
+MessageLoop* ProxyResolverV8Tracing::Job::worker_loop() {
+  return parent_->thread_->message_loop();
+}
+
+HostResolver* ProxyResolverV8Tracing::Job::host_resolver() {
+  return parent_->host_resolver_;
+}
+
+ProxyResolverErrorObserver* ProxyResolverV8Tracing::Job::error_observer() {
+  return parent_->error_observer_.get();
+}
+
+NetLog* ProxyResolverV8Tracing::Job::net_log() {
+  return parent_->net_log_;
+}
+
+// Post a task to the origin thread, to invoke the user's callback.
+void ProxyResolverV8Tracing::Job::NotifyCaller(int result) {
+  CheckIsOnWorkerThread();
+
+  origin_loop_->PostTask(
+      FROM_HERE,
+      base::Bind(&Job::NotifyCallerOnOriginLoop, this, result));
+}
+
+void ProxyResolverV8Tracing::Job::NotifyCallerOnOriginLoop(int result) {
+  CheckIsOnOriginThread();
+
+  if (cancelled_.IsSet())
+    return;
+
+  if (operation_ == GET_PROXY_FOR_URL)
+    *user_results_ = results_;
+
+  // There is only ever 1 outstanding SET_PAC_SCRIPT job. It needs to be
+  // tracked to support cancellation.
+  if (operation_ == SET_PAC_SCRIPT) {
+    DCHECK(parent_->set_pac_script_job_);
+    parent_->set_pac_script_job_ = NULL;
+  }
+
+  callback_.Run(result);
+  callback_.Reset();
+
+  Release();
+}
+
+void ProxyResolverV8Tracing::Job::Start(Operation op, bool blocking_dns,
+                                        const CompletionCallback& callback) {
+  operation_ = op;
+  blocking_dns_ = blocking_dns;
+  callback_ = callback;
+
+  AddRef();
+
+  worker_loop()->PostTask(FROM_HERE,
+      blocking_dns_ ? base::Bind(&Job::ExecuteBlocking, this) :
+                      base::Bind(&Job::ExecuteNonBlocking, this));
+}
+
+void ProxyResolverV8Tracing::Job::ExecuteBlocking() {
+  CheckIsOnWorkerThread();
+  DCHECK(blocking_dns_);
+
+  if (cancelled_.IsSet())
+    return;
+
+  NotifyCaller(ExecuteProxyResolver());
+}
+
+void ProxyResolverV8Tracing::Job::ExecuteNonBlocking() {
+  CheckIsOnWorkerThread();
+  DCHECK(!blocking_dns_);
+
+  if (cancelled_.IsSet())
+    return;
+
+  // Reset state for the current execution.
+  abandoned_ = false;
+  num_dns_ = 0;
+  base::MD5Init(&dns_digest_);
+  alerts_and_errors_.clear();
+  alerts_and_errors_byte_cost_ = 0;
+
+  int result = ExecuteProxyResolver();
+
+  if (abandoned_)
+    return;
+
+  DispatchBufferedAlertsAndErrors();
+  NotifyCaller(result);
+}
+
+int ProxyResolverV8Tracing::Job::ExecuteProxyResolver() {
+  JSBindings* prev_bindings = v8_resolver()->js_bindings();
+  v8_resolver()->set_js_bindings(this);
+
+  int result = ERR_UNEXPECTED;  // Initialized to silence warnings.
+
+  switch (operation_) {
+    case SET_PAC_SCRIPT:
+      result = v8_resolver()->SetPacScript(
+          script_data_, CompletionCallback());
+      break;
+    case GET_PROXY_FOR_URL:
+      result = v8_resolver()->GetProxyForURL(
+        url_,
+        // Important: Do not write directly into |user_results_|, since if the
+        // request were to be cancelled from the origin thread, must guarantee
+        // that |user_results_| is not accessed anymore.
+        &results_,
+        CompletionCallback(),
+        NULL,
+        bound_net_log_);
+      break;
+  }
+
+  v8_resolver()->set_js_bindings(prev_bindings);
+  return result;
+}
+
+bool ProxyResolverV8Tracing::Job::ResolveDns(const std::string& host,
+                        ResolveDnsOperation op,
+                        std::string* output) {
+  if (cancelled_.IsSet())
+    return false;
+
+  if ((op == DNS_RESOLVE || op == DNS_RESOLVE_EX) && host.empty()) {
+    // a DNS resolve with an empty hostname is considered an error.
+    return false;
+  }
+
+  return blocking_dns_ ?
+      ResolveDnsBlocking(host, op, output) :
+      ResolveDnsNonBlocking(host, op, output);
+}
+
+void ProxyResolverV8Tracing::Job::Alert(const string16& message) {
+  HandleAlertOrError(true, -1, message);
+}
+
+void ProxyResolverV8Tracing::Job::OnError(int line_number,
+                                          const string16& error) {
+  HandleAlertOrError(false, line_number, error);
+}
+
+bool ProxyResolverV8Tracing::Job::ResolveDnsBlocking(const std::string& host,
+                                                     ResolveDnsOperation op,
+                                                     std::string* output) {
+  CheckIsOnWorkerThread();
+
+  // Check if the DNS result for this host has already been cached.
+  bool rv;
+  if (GetDnsFromLocalCache(host, op, output, &rv)) {
+    // Yay, cache hit!
+    return rv;
+  }
+
+  // If the host was not in the local cache, this is a new hostname.
+
+  if (dns_cache_.size() > kMaxUniqueResolveDnsPerExec) {
+    // Safety net for scripts with unexpectedly many DNS calls.
+    // We will continue running to completion, but will fail every
+    // subsequent DNS request.
+    return false;
+  }
+
+  bool unused;
+  origin_loop_->PostTask(
+      FROM_HERE, base::Bind(&Job::DoDnsOperation, this, host, op, &unused));
+
+  // Wait for the DNS operation to be completed by the host resolver on the
+  // origin thread. After waking up, either the request was cancelled, or
+  // the DNS result is now available in the cache.
+  event_.Wait();
+  event_.Reset();
+
+  if (cancelled_.IsSet())
+    return false;
+
+  CHECK(GetDnsFromLocalCache(host, op, output, &rv));
+  return rv;
+}
+
+bool ProxyResolverV8Tracing::Job::ResolveDnsNonBlocking(const std::string& host,
+                                                        ResolveDnsOperation op,
+                                                        std::string* output) {
+  CheckIsOnWorkerThread();
+
+  if (abandoned_) {
+    // If this execution was already abandoned can fail right away. Only 1 DNS
+    // dependency will be traced at a time (for more predictable outcomes).
+    return false;
+  }
+
+  num_dns_ += 1;
+
+  // Keep a digest of the sequence of DNS requests this execution has seen so
+  // far. This is cheaper than keeping a full list of the history, and good
+  // enough for our purposes (we want to detect when things have gone wrong in
+  // order to fallback to blocking mode).
+  base::MD5Update(&dns_digest_, host);
+  base::MD5Update(&dns_digest_, base::IntToString(op));
+
+  // Upon reaching the point of execution from the last run, make sure
+  // that the sequence of resolves has matched so far.
+  if (num_dns_ == last_num_dns_ &&
+      !MD5DigestEquals(last_dns_digest_, dns_digest_)) {
+    // The sequence of DNS operations is different from last time!
+    ScheduleRestartWithBlockingDns();
+    abandoned_ = true;
+    return false;
+  }
+
+  // Check if the DNS result for this host has already been cached.
+  bool rv;
+  if (GetDnsFromLocalCache(host, op, output, &rv)) {
+    // Yay, cache hit!
+    return rv;
+  }
+
+  // If the host was not in the local cache, then this is a new hostname.
+
+  if (num_dns_ <= last_num_dns_) {
+    // The sequence of DNS operations is different from last time!
+    ScheduleRestartWithBlockingDns();
+    abandoned_ = true;
+    return false;
+  }
+
+  if (dns_cache_.size() > kMaxUniqueResolveDnsPerExec) {

[mmenke, 2013/01/24 21:06:33]

No test goes through here, I believe.  This code is complicated enough that I
believe we should try and hit every case in tests that we reasonably can.

[eroman, 2013/01/25 03:02:01]

Thanks. Now covered by the InfiniteDNSSequence* tests.

+    // Safety net for scripts with unexpectedly many DNS calls.
+    return false;
+  }
+
+  // Post the DNS request to the origin thread.
+  bool resolver_cache_hit = false;
+  origin_loop_->PostTask(
+      FROM_HERE, base::Bind(&Job::DoDnsOperation, this, host, op,
+                            &resolver_cache_hit));
+
+  // As an optimization to avoid restarting too often, wait until the
+  // resolver's cache has been inspected on the origin thread.
+  event_.Wait();
+  event_.Reset();
+
+  if (cancelled_.IsSet())
+    return false;
+
+  if (resolver_cache_hit) {
+    CHECK(GetDnsFromLocalCache(host, op, output, &rv));
+    return rv;
+  }
+
+  // Otherwise if the result was not in the cache, then a DNS request has
+  // been started. Abandon this invocation of FindProxyForURL(), it will be
+  // restarted once the DNS request completes.
+  abandoned_ = true;
+  last_num_dns_ = num_dns_;
+  base::MD5Final(&last_dns_digest_, &dns_digest_);
+  return false;
+}
+
+void ProxyResolverV8Tracing::Job::DoDnsOperation(
+    const std::string& host, ResolveDnsOperation op, bool* out_cache_hit) {
+  CheckIsOnOriginThread();
+
+  if (cancelled_.IsSet())
+    return;
+
+  DCHECK(!pending_dns_);
+
+  HostResolver::RequestInfo info = MakeDnsRequestInfo(host, op);
+
+  if (!blocking_dns_) {

[mmenke, 2013/01/24 21:06:33]

Rather than have all this cruft here, suggest moving this block to below the
Resolve() call and checking for ERR_IO_PENDING rather than ERR_CACHE_MISS. 
Saves you a couple lines of code, and the double call into the HostResolver.

Could even have cache hits use OnDnsOperationComplete on cache hits and follow
the blocking_ path if cache_hit_ is true (Which should be made a class
variable).  Then you could get rid of this block, always set cache_hit_ based on
whether or not result is ERR_IO_PENDING, and just call event_.Signal() on cache
misses when not blocking.

[eroman, 2013/01/25 03:02:01]

Done -- Good idea, I have removed the duplicate calls into HostResolver.

+    // Check if the DNS result can be serviced directly from the cache.
+    // (The worker thread is blocked waiting for this information).
+    net::AddressList addresses;
+    int result = host_resolver()->ResolveFromCache(
+        info, &addresses, bound_net_log_);
+
+    bool cache_hit = result != ERR_DNS_CACHE_MISS;
+    if (cache_hit) {
+      // Cool, it was in the host resolver's cache. Copy it to the
+      // per-request cache.
+      SaveDnsToLocalCache(host, op, result, addresses);

[mmenke, 2013/01/24 21:06:33]

HostResolver cache hit case doesn't seem to be tested (Not to be confused with
"local cache" hit), either in the blocking or non-blocking case.

[eroman, 2013/01/25 03:02:01]

Thanks! Added a test to exercise this: DnsChecksCache

+    }
+
+    // Important: Do not read/write |out_cache_hit| after signalling, since
+    // the memory may no longer be valid.
+    *out_cache_hit = cache_hit;
+    event_.Signal();
+
+    if (cache_hit)
+      return;
+  }
+
+  pending_dns_host_ = host;
+  pending_dns_op_ = op;
+
+  int result = host_resolver()->Resolve(
+      info,
+      &pending_dns_addresses_, base::Bind(&Job::OnDnsOperationComplete, this),
+      &pending_dns_, bound_net_log_);
+
+  if (result != ERR_IO_PENDING)
+    OnDnsOperationComplete(result);
+}
+
+void ProxyResolverV8Tracing::Job::OnDnsOperationComplete(int result) {
+  CheckIsOnOriginThread();
+
+  DCHECK(pending_dns_);
+  DCHECK(!cancelled_.IsSet());
+
+  SaveDnsToLocalCache(pending_dns_host_, pending_dns_op_, result,
+                      pending_dns_addresses_);
+  pending_dns_ = NULL;
+
+  if (!blocking_dns_) {
+    // Restart. This time it should make more progress due to having
+    // cached items.
+    worker_loop()->PostTask(FROM_HERE, base::Bind(&Job::ExecuteNonBlocking, this));

[mmenke, 2013/01/24 21:06:33]

nit:  Line too long

[eroman, 2013/01/25 03:02:01]

Done.

+  } else {
+    // Otherwise wakeup the blocked worker thread.
+    event_.Signal();
+  }
+}
+
+void ProxyResolverV8Tracing::Job::ScheduleRestartWithBlockingDns() {

[mmenke, 2013/01/24 21:06:33]

In the interest of failing early, suggest:

DCHECK(!blocking_dns_);
DCHECK(!abandoned_);

[mmenke, 2013/01/24 21:06:33]

Any reason not to just set abandoned_ to true here, rather than just before
every call to this function?

Could set blocking_dns_ to true, too, if you wanted (And get rid of
RestartWithBlockingDns()), though that doesn't give us too much.

[mmenke, 2013/01/24 21:06:33]

CheckIsOnWorkerThread(); for documentation purposes.

[eroman, 2013/01/25 03:02:01]

Done.

[eroman, 2013/01/25 03:02:01]

I can't set blocking_dns_ to true, because we may still be executing inside of
the proxy resolver. If DnsResolve() were to get called again, it would see
|blocking_dns_| and start doing the stuff for blocking DNS (blocking_dns_ trumps
abandoned).

For this reason, I post a task back to the message loop to set blocking_dns_
once the stack has unwound.

I have added a comment explaining this since it isn't obvious, and moved the
assignment to abandoned_ into the function.

+  MessageLoop::current()->PostTask(
+      FROM_HERE, base::Bind(&Job::RestartWithBlockingDns, this));
+}
+
+void ProxyResolverV8Tracing::Job::RestartWithBlockingDns() {

[mmenke, 2013/01/24 21:06:33]

CheckIsOnWorkerThread();

[eroman, 2013/01/25 03:02:01]

Done.

+  DCHECK(!blocking_dns_);
+  blocking_dns_ = true;
+  ExecuteBlocking();
+}
+
+bool ProxyResolverV8Tracing::Job::GetDnsFromLocalCache(
+    const std::string& host,
+    ResolveDnsOperation op,
+    std::string* output,
+    bool* return_value) {

[mmenke, 2013/01/24 21:06:33]

CheckIsOnWorkerThread();

[eroman, 2013/01/25 03:02:01]

Done.

+  DnsCache::const_iterator it = dns_cache_.find(MakeDnsCacheKey(host, op));
+  if (it == dns_cache_.end())
+    return false;
+
+  *output = it->second;
+  *return_value = !it->second.empty();
+  return true;
+}
+
+void ProxyResolverV8Tracing::Job::SaveDnsToLocalCache(
+    const std::string& host,
+    ResolveDnsOperation op,
+    int net_error,
+    const net::AddressList& addresses) {

[mmenke, 2013/01/24 21:06:33]

"CheckIsOnOriginThread();" for documentation purposes.

[eroman, 2013/01/25 03:02:01]

Done.

+
+  // Serialize the result into a string to save to the cache.
+  std::string cache_value;
+  if (net_error != OK) {
+    cache_value = std::string();
+  } else if (op == DNS_RESOLVE || op == MY_IP_ADDRESS) {
+    // dnsResolve() and myIpAddress() are expected to return a single IP
+    // address.
+    cache_value = addresses.front().ToStringWithoutPort();
+  } else {
+    // The *Ex versions are expected to return a semi-colon separated list.
+    for (AddressList::const_iterator iter = addresses.begin();
+         iter != addresses.end(); ++iter) {
+      if (!cache_value.empty())
+        cache_value += ";";
+      const std::string address_string = iter->ToStringWithoutPort();
+      if (address_string.empty()) {
+        cache_value = std::string();
+        break;
+      }
+      cache_value += address_string;
+    }
+  }
+
+  dns_cache_[MakeDnsCacheKey(host, op)] = cache_value;
+}
+
+HostResolver::RequestInfo ProxyResolverV8Tracing::Job::MakeDnsRequestInfo(
+    const std::string& host, ResolveDnsOperation op) {
+  HostPortPair host_port = HostPortPair(host, 80);
+  if (op == MY_IP_ADDRESS || op == MY_IP_ADDRESS_EX) {
+    host_port.set_host(GetHostName());
+  }
+
+  HostResolver::RequestInfo info(host_port);
+
+  // The non-ex flavors are limited to IPv4 results.
+  if (op == MY_IP_ADDRESS || op == DNS_RESOLVE) {
+    info.set_address_family(ADDRESS_FAMILY_IPV4);
+  }
+
+  return info;
+}
+
+// Make a key for looking up |host, op| in |dns_cache_|. Strings are used for
+// convenience, to avoid defining custom comparators.
+std::string ProxyResolverV8Tracing::Job::MakeDnsCacheKey(
+    const std::string& host, ResolveDnsOperation op) {
+  return StringPrintf("%d:%s", op, host.c_str());
+}
+
+void ProxyResolverV8Tracing::Job::HandleAlertOrError(bool is_alert,
+                                                     int line_number,
+                                                     const string16& message) {
+  if (cancelled_.IsSet())
+    return;
+
+  if (blocking_dns_) {
+    // In blocking DNS mode the events can be dispatched immediately.
+    DispatchAlertOrError(is_alert, line_number, message);
+    return;
+  }
+
+  // Otherwise in nonblocking mode, buffer all the messages until
+  // the end.
+
+  if (abandoned_)
+    return;
+
+  alerts_and_errors_byte_cost_ += message.size() * 2;

[mmenke, 2013/01/24 21:06:33]

Should we toss in a sizeof(AlertOrError)?  Otherwise, could add a bunch of
0-length messages until Bad Things happen.

[eroman, 2013/01/25 03:02:01]

Excellent point. Done.

+
+  // If there have been lots of messages, enqueuing could be expensive on
+  // memory. (consider a script which does megabytes worth of alerts()).
+  // Avoid this by falling back to blocking mode.
+  if (alerts_and_errors_byte_cost_ > kMaxAlertsAndErrorsBytes) {
+    ScheduleRestartWithBlockingDns();
+    abandoned_ = true;
+    return;
+  }
+
+  AlertOrError entry = {is_alert, line_number, message};
+  alerts_and_errors_.push_back(entry);
+}
+
+void ProxyResolverV8Tracing::Job::DispatchBufferedAlertsAndErrors() {
+  DCHECK(!blocking_dns_);
+  DCHECK(!abandoned_);
+
+  for (size_t i = 0; i < alerts_and_errors_.size(); ++i) {
+    const AlertOrError& x = alerts_and_errors_[i];
+    DispatchAlertOrError(x.is_alert, x.line_number, x.message);
+  }
+}
+
+void ProxyResolverV8Tracing::Job::DispatchAlertOrError(
+    bool is_alert, int line_number, const string16& message) {

[mmenke, 2013/01/24 21:06:33]

Suggest a CheckIsOnWorkerThread() for documentation reasons.

[eroman, 2013/01/25 03:02:01]

Done.

+  // Note that the handling of cancellation is racy with regard to
+  // alerts/errors. The request might get cancelled shortly after this
+  // check! (There is no lock being held to guarantee otherwise).
+  //
+  // If this happens, then some information will get written to the NetLog
+  // needlessly, however the NetLog will still be alive so it shouldn't cause
+  // problems.
+  if (cancelled_.IsSet())
+    return;
+
+  if (is_alert) {
+    // -------------------
+    // alert
+    // -------------------
+    VLOG(1) << "PAC-alert: " << message;
+
+    // Send to the NetLog.
+    LogEventToCurrentRequestAndGlobally(
+        NetLog::TYPE_PAC_JAVASCRIPT_ALERT,
+        NetLog::StringCallback("message", &message));

[mmenke, 2013/01/24 21:06:33]

So we basically just silently consume PAC script alerts?  So we're supporting
them only for debugging Chrome itself?

[eroman, 2013/01/25 03:02:01]

Correct. Actually popping up an alert() is silly, especially in a blocking
manner.

alert() is analogous to a printf() for authors trying to debug PAC scripts.

In the case of Chrome it is sent to about:net-internals. In the case of Firefox
it gets sent to the error console.

IE actually *does* pop open an alert dialog, which is pretty ridiculous if you
ask me.

The world needs fewer alerts, not more :)

Note also that this is not changing Chrome's current behavior; it already is
doing this.

[mmenke, 2013/01/25 05:03:28]

In an ideal world, we'd have some mechanism to surface them to developers. 
Given that we aren't surfacing them to developers, wonder if it's even worth
buffering them as we currently are.  Since you're the one who actually has to
debug the code, I defer to you in whether it's worth the effort.

[eroman, 2013/01/25 21:42:25]

Developers actually do use alerts(), so it is good to deliver them in the
expected order (would be weird to see all the intermediary alerts from
restarts).

Since buffering them is pretty straight forward I believe this is worth doing.

Not buffering errors could lead to incorrect results, since there may be error
observers, and a partial execution could give an error whereas once the DNS
dependency is resolved it may not.

+  } else {
+    // -------------------
+    // error
+    // -------------------
+    if (line_number == -1)
+      VLOG(1) << "PAC-error: " << message;
+    else
+      VLOG(1) << "PAC-error: " << "line: " << line_number << ": " << message;
+
+    // Send the error to the NetLog.
+    LogEventToCurrentRequestAndGlobally(
+        NetLog::TYPE_PAC_JAVASCRIPT_ERROR,
+        base::Bind(&NetLogErrorCallback, line_number, &message));
+
+    if (error_observer())
+      error_observer()->OnPACScriptError(line_number, message);
+  }
+}
+
+void ProxyResolverV8Tracing::Job::LogEventToCurrentRequestAndGlobally(
+    NetLog::EventType type,
+    const NetLog::ParametersCallback& parameters_callback) {
+  bound_net_log_.AddEvent(type, parameters_callback);
+
+  // Emit to the global NetLog event stream.
+  if (net_log())
+    net_log()->AddGlobalEntry(type, parameters_callback);
+}
+
+ProxyResolverV8Tracing::ProxyResolverV8Tracing(
+    HostResolver* host_resolver,
+    ProxyResolverErrorObserver* error_observer,
+    NetLog* net_log)
+    : ProxyResolver(true /*expects_pac_bytes*/),
+      host_resolver_(host_resolver),
+      error_observer_(error_observer),
+      net_log_(net_log) {
+  DCHECK(host_resolver);
+  // Start up the thread.
+  thread_.reset(new base::Thread("Proxy resolver"));
+  CHECK(thread_->Start());
+
+  v8_resolver_.reset(new ProxyResolverV8);

[mmenke, 2013/01/24 21:06:33]

Any compelling reason not to include this and thread_'s initialization in the
initializer list?

[eroman, 2013/01/25 03:02:01]

It is so I can use base::ThreadRestrictions::ScopedAllowIO

+}
+
+ProxyResolverV8Tracing::~ProxyResolverV8Tracing() {
+  // Note, all requests should have been cancelled.
+  DCHECK(!set_pac_script_job_);
+
+  // Join the worker thread.
+  // See http://crbug.com/69710.
+  base::ThreadRestrictions::ScopedAllowIO allow_io;
+  thread_.reset();
+}
+
+int ProxyResolverV8Tracing::GetProxyForURL(const GURL& url,
+                                           ProxyInfo* results,
+                                           const CompletionCallback& callback,
+                                           RequestHandle* request,
+                                           const BoundNetLog& net_log) {
+  DCHECK(CalledOnValidThread());
+  DCHECK(!callback.is_null());
+
+  scoped_refptr<Job> job = new Job(this);
+
+  if (request)
+    *request = job.get();
+
+  job->StartGetProxyForURL(url, results, net_log, callback);
+  return ERR_IO_PENDING;
+}
+
+void ProxyResolverV8Tracing::CancelRequest(RequestHandle request) {
+  Job* job = reinterpret_cast<Job*>(request);
+  job->Cancel();
+}
+
+LoadState ProxyResolverV8Tracing::GetLoadState(RequestHandle request) const {
+  Job* job = reinterpret_cast<Job*>(request);
+  return job->GetLoadState();
+}
+
+void ProxyResolverV8Tracing::CancelSetPacScript() {
+  set_pac_script_job_->Cancel();
+  set_pac_script_job_ = NULL;
+}
+
+void ProxyResolverV8Tracing::PurgeMemory() {
+  thread_->message_loop()->PostTask(
+      FROM_HERE,
+      base::Bind(&ProxyResolverV8::PurgeMemory,
+                 // The use of unretained is safe, since the worker thread
+                 // cannot outlive |this|.
+                 base::Unretained(v8_resolver_.get())));
+}
+
+int ProxyResolverV8Tracing::SetPacScript(
+    const scoped_refptr<ProxyResolverScriptData>& script_data,
+    const CompletionCallback& callback) {
+  DCHECK(CalledOnValidThread());
+  DCHECK(!callback.is_null());
+
+  set_pac_script_job_ = new Job(this);
+  set_pac_script_job_->StartSetPacScript(script_data, callback);
+
+  return ERR_IO_PENDING;
+}
+
+}  // namespace net