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..49e8af3d683a4c7f0bc0185054f4c7c6e35af130
--- /dev/null
+++ b/net/proxy/proxy_resolver_v8_tracing.cc
@@ -0,0 +1,847 @@
+// 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

[mmenke, 2013/01/18 19:59:40]

"Sorry, the file you have requested does not exist."

[eroman, 2013/01/23 03:26:02]

Are you sure you copied the full line exactly? (it is multi-line). Works for me,
both when signed in and not.

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

Oops...A straight copy gets the spaces inserted by the Rietveld layout code. 
Shockingly, docs.google.com isn't smart enough to remove random extra spaces in
the URL.

+//
+// 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 synchronous or
+// asynchronous mode. Synchronous mode is used as a fallback when the PAC script
+// seems to be misbehaving under the tracing optimization.

[mmenke, 2013/01/18 19:59:40]

You call these blocking and non-blocking elsewhere.  Suggest a consistent naming
scheme.  I'm happy either way.

[eroman, 2013/01/23 03:26:02]

Done -- renamed everything to blocking/non-blocking.

+//
+// 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 lifetiime of Jobs does not exceed that of the ProxyResolverV8Tracing that

[mmenke, 2013/01/18 19:59:40]

nit: lifetime

[eroman, 2013/01/23 03:26:02]

Done.

+// 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.
+  explicit Job(ProxyResolverV8Tracing* parent)
+      : origin_loop_(base::MessageLoopProxy::current()),
+        parent_(parent),
+        event_(true, false) {
+  }
+
+  void StartSetPacScript(
+      const scoped_refptr<ProxyResolverScriptData>& script_data,
+      const CompletionCallback& callback) {

[mmenke, 2013/01/18 19:59:40]

I recommend de-inlining all these functions.  With a 600 line class, think
inlining makes it harder to get a high level view of a class.

[eroman, 2013/01/23 03:26:02]

Done.

+    CheckIsOnOriginThread();
+
+    operation_ = SET_PAC_SCRIPT;
+    // Script initialization uses a synchronous DNS since there isn't any
+    // advantage to using asynchronous mode here. That is because the
+    // parent ProxyService can't submit any ProxyResolve requests until
+    // initialization has completed successfully!

[mmenke, 2013/01/18 19:59:40]

Setting the PAC can call scripts?

[eroman, 2013/01/23 03:26:02]

Setting the PAC involves "sourcing" the script. It has the sideffect of running
any code in the global scope, which might include function calls.

+    nonblocking_dns_ = false;
+
+    script_data_ = script_data;
+    callback_ = callback;
+
+    PostStart();
+  }
+
+  void StartGetProxyForURL(const GURL& url,
+                           ProxyInfo* results,
+                           const BoundNetLog& net_log,
+                           const CompletionCallback& callback) {
+    CheckIsOnOriginThread();
+
+    operation_ = GET_PROXY_FOR_URL;
+    nonblocking_dns_ = true;
+
+    url_ = url;
+    user_results_ = results;
+    bound_net_log_ = net_log;
+    callback_ = callback;
+
+    last_num_dns_ = 0;
+
+    PostStart();
+  }
+
+  void Cancel() {
+    CheckIsOnOriginThread();
+
+    // There are three main possibility to consider for cancellation:
+    // (a) The job has been posted to the worker thread, but not yet started
+    // (b) The script is executing on the worker thread
+    // (c) The script is blocked waiting for DNS

[mmenke, 2013/01/18 19:59:40]

(d)  The script has stopped, and there's a pending DNS lookup on this thread
which will do the DNS lookup and then post a task to the worker thread to start
the script again.

[eroman, 2013/01/23 03:26:02]

Done.

+    //
+    // |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. Breaking out early is not necessary
+    // for correctness, however it does avoid doing unecessary work.

[mmenke, 2013/01/18 19:59:40]

It is necessary to in the blocking case, isn't it?  Otherwise, we'd hang  on the
next lookup on shutdown (Or fail a CHECK).

[eroman, 2013/01/23 03:26:02]

Yes that is true, cancellation which interrupts a DNS request is mandatory. I'll
adjust the wording by deleting the later phrases. (I don't want to be too
specific or it is hard to read). Mostly that "correctness" issue was interesting
when I did unprotected reads from the worker thread of cancelled_, but that is
no longer the case.

+    //
+    // The important check on |cancelled_| is done from the origin thread in
+    // NotifyCallerOnOriginLoop().
+    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_.get()) {

[mmenke, 2013/01/18 19:59:40]

nit:  Preferred style is not to use get().

[eroman, 2013/01/23 03:26:02]

Done.

+      host_resolver()->CancelRequest(pending_dns_->handle);
+      pending_dns_.reset();
+    }
+
+    // The worker thread might be blocked waiting for DNS.
+    event_.Signal();
+
+    Release();
+  }
+
+  LoadState GetLoadState() const {
+    CheckIsOnOriginThread();
+
+    if (pending_dns_.get())

[mmenke, 2013/01/18 19:59:40]

nit:  Preferred style is not to use get().

[eroman, 2013/01/23 03:26:02]

Done.

+      return LOAD_STATE_RESOLVING_HOST_IN_PROXY_SCRIPT;
+
+    return LOAD_STATE_RESOLVING_PROXY_FOR_URL;
+  }
+
+ private:
+  friend class base::RefCountedThreadSafe<ProxyResolverV8Tracing::Job>;
+
+  enum Operation {
+    SET_PAC_SCRIPT,
+    GET_PROXY_FOR_URL,
+  };
+
+  struct AlertOrError {
+    AlertOrError(bool is_alert, int line_number, const string16& message)
+        : is_alert(is_alert), line_number(line_number), message(message) {}
+
+    bool is_alert;
+    int line_number;
+    string16 message;

[mmenke, 2013/01/18 19:59:40]

Could you make these const?  Not sure if that would make vector sad or not.

[eroman, 2013/01/23 03:26:02]

Yeah const makes std::vector sad, because push_back relies on the assigment
operator, which cannot be implicitly generated when the members are const :(

+  };
+
+  struct ExecutionState {
+    bool was_abandoned;
+
+    // The number of times ResolveDns() was called so far.
+    int num_dns;
+    base::MD5Context dns_digest;
+
+    size_t alerts_and_errors_bytes_;
+    std::vector<AlertOrError> alerts_and_errors_;
+  };
+
+  struct PendingDns {
+    PendingDns(const std::string& host, ResolveDnsOperation op)
+        : host(host), op(op), handle(NULL) {}
+
+    std::string host;
+    ResolveDnsOperation op;
+
+    HostResolver::RequestHandle handle;
+    net::AddressList addresses;
+  };
+
+  ~Job() {
+    DCHECK(!pending_dns_.get());
+  }
+
+  void CheckIsOnWorkerThread() {
+    DCHECK_EQ(MessageLoop::current(), parent_->thread_->message_loop());
+  }
+
+  void CheckIsOnOriginThread() const {
+    DCHECK(origin_loop_->BelongsToCurrentThread());
+  }
+
+  ProxyResolverV8* v8_resolver() {
+    return parent_->v8_resolver_.get();
+  }
+
+  MessageLoop* worker_loop() {
+    return parent_->thread_->message_loop();
+  }
+
+  HostResolver* host_resolver() {
+    return parent_->host_resolver_;
+  }
+
+  ProxyResolverErrorObserver* error_observer() {
+    return parent_->error_observer_.get();
+  }
+
+  NetLog* net_log() {
+    return parent_->net_log_;
+  }
+
+  void PostStart() {
+    AddRef();  // Balanced on completion, or cancellation.
+    worker_loop()->PostTask(FROM_HERE, base::Bind(&Job::Start, this));
+  }
+
+  // Post a task to the origin thread, to invoke the user's callback.
+  void NotifyCaller(int result) {
+    CheckIsOnWorkerThread();
+
+    origin_loop_->PostTask(
+        FROM_HERE,
+        base::Bind(&Job::NotifyCallerOnOriginLoop, this, result));
+  }
+
+  void 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 Start() {
+    CheckIsOnWorkerThread();
+
+    if (cancelled_.IsSet())
+      return;
+
+    if (nonblocking_dns_) {
+      // Reset state pertaining to the current playthrough.
+      exec_.was_abandoned = false;
+      exec_.num_dns = 0;
+      base::MD5Init(&exec_.dns_digest);
+      exec_.alerts_and_errors_.clear();
+      exec_.alerts_and_errors_bytes_ = 0;
+    }
+
+    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 must guarantee that
+          // |user_results| is not accessed anymore.
+          &results_,
+          CompletionCallback(),
+          NULL,
+          bound_net_log_);
+        break;
+    }
+
+    v8_resolver()->set_js_bindings(prev_bindings);
+
+    if (nonblocking_dns_) {
+      if (!exec_.was_abandoned) {
+        // Some alerts() and errors may have been buffered, since it was not
+        // known at the time whether this run would be discarded. Now that it is
+        // known to be a full run, dispatch those buffered events.
+        DispatchBufferedAlertsAndErrors();
+        NotifyCaller(result);
+      }
+    } else {
+      NotifyCaller(result);
+    }
+  }
+
+  // Handler for "alert(message)"
+  virtual void Alert(const string16& message) OVERRIDE {
+    HandleAlertOrError(true, -1, message);
+  }
+
+  // Handler for when an error is encountered. |line_number| may be -1
+  // if a line number is not applicable to this error.
+  virtual void OnError(int line_number, const string16& error) OVERRIDE {
+    HandleAlertOrError(false, line_number, error);
+  }
+
+  void HandleAlertOrError(bool is_alert, int line_number,
+                          const string16& message) {
+    if (cancelled_.IsSet())
+      return;
+
+    if (!nonblocking_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 (exec_.was_abandoned)
+      return;
+
+    exec_.alerts_and_errors_bytes_ += message.size() * 2;
+
+    // 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 (exec_.alerts_and_errors_bytes_ > kMaxAlertsAndErrorsBytes) {
+      ScheduleRestartWithBlockingDns();
+      exec_.was_abandoned = true;
+      return;
+    }
+
+    exec_.alerts_and_errors_.push_back(
+        AlertOrError(is_alert, line_number, message));
+  }
+
+  void DispatchBufferedAlertsAndErrors() {
+    DCHECK(nonblocking_dns_);
+    DCHECK(!exec_.was_abandoned);
+
+    for (size_t i = 0; i < exec_.alerts_and_errors_.size(); ++i) {
+      const AlertOrError& x = exec_.alerts_and_errors_[i];
+      DispatchAlertOrError(x.is_alert, x.line_number, x.message);
+    }
+  }
+
+  void DispatchAlertOrError(bool is_alert, int line_number,
+                            const string16& message) {
+    // 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));
+    } 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 LogEventToCurrentRequestAndGlobally(

[mmenke, 2013/01/18 19:59:40]

nit:  Fix indent.

[eroman, 2013/01/23 03:26:02]

Done.

+      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);
+  }
+
+  virtual bool 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 nonblocking_dns_ ?
+      ResolveDnsNonBlocking(host, op, output) :
+      ResolveDnsBlocking(host, op, output);

[mmenke, 2013/01/18 19:59:40]

nit:  4 space indent.

[eroman, 2013/01/23 03:26:02]

Done.

+  }
+
+  bool 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;
+  }
+
+  // To detect inconsistencies, the past sequence of ResovleDns operations are
+  // saved and enforced during each replay. Instead of saving the full sequence
+  // of hostnames, just an MD5 checksum is kept (to avoid unbounded memory
+  // growth).
+  bool ResolveDnsNonBlocking(const std::string& host,
+                             ResolveDnsOperation op,
+                             std::string* output) {
+    CheckIsOnWorkerThread();
+
+    if (exec_.was_abandoned) {
+      // If this execution was alread abandoned can fail right away. Only 1 DNS

[mmenke, 2013/01/18 19:59:40]

nit "already"

[eroman, 2013/01/23 03:26:02]

Done.

+      // dependency will be traced at a time (for more predictable outcomes).
+      return false;
+    }
+
+    exec_.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 synchronous mode).
+    base::MD5Update(&exec_.dns_digest, host);
+    base::MD5Update(&exec_.dns_digest, base::IntToString(op));

[mmenke, 2013/01/18 19:59:40]

Does this really get us anything we care about over the "exec_.num_dns <=
last_num_dns_" test?

I suppose if your goal in life were to construct a PAC that would fail the MD5
test but pass the first non-cached lookup test, you could manage it, but doesn't
really seem worth the effort to me.

[eroman, 2013/01/23 03:26:02]

I chose to enforce the sequence of all DNS requests received, since that is the
strongest check I can do. I could have chosen something weaker like the sequence
of unique hostnames, but the implementation for those is actually more
complicated (since you would need sets).

As mentioned in the comment, saving a strict history could be expensive, since
scripts might have hundreds of "cache hits" (i.e. repeated calls to dnsResolve
with the same hostname).

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

I was just thinking that it's not too likely that this test would fail in the
case where the "exec_.num_dns <= last_num_dns_" test below passes.

My only real complaints about this are added complexity of two early exit cases.
 Nothing against using MD5s.

[eroman, 2013/01/24 22:13:58]

Thanks for discussing this issue!

Indeed, none of the tests I have right now need the MD5 check to succeed.

You are correct that constructing a PAC script that triggers this requires quite
a bit of craziness, and may not be worth doing the extra work for (could rely on
the kMaxUniqueResolveDnsPerExec detecting a problem in those cases).

I will start by adding at least one unittest that triggers this situation, and
then re-evaluate if enforcing same-ordering makes sense.

I suspect you are right, and we shouldn't bother MD5-ing. If these scripts do
exist and cause problems, then users will be best served if we fall-back to
synchronous mode for all requests anyway.

+
+    // Upon reaching the point of execution from the last run, make sure
+    // that the sequence of resolves has matched so far.
+    if (exec_.num_dns == last_num_dns_ &&
+        !MD5DigestEquals(last_dns_digest_, exec_.dns_digest)) {
+      // The sequence of DNS operations is different from last time!
+      ScheduleRestartWithBlockingDns();

[mmenke, 2013/01/18 19:59:40]

Restarting instead of just switching is primarily because there may be queued
alerts, too, so it's simpler just to restart?

[eroman, 2013/01/23 03:26:02]

Correct, restarting is to keep things simple. There are various bits of state
that would need to be twiddled with to support resuming in blocking mode.

Since this isn't supposed to happen often (at all), the slight performance
penalty is worth the code maintainability I think.

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

I was thinking that you could get rid of "ScheduleRestartWithBlockingDns()",
saving a little code and simplifying things a little, but with the extra state,
doesn't simplify things as I had hoped.

+      exec_.was_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 (exec_.num_dns <= last_num_dns_) {
+      // The sequence of DNS operations is different from last time!
+      ScheduleRestartWithBlockingDns();
+      exec_.was_abandoned = true;
+      return false;
+    }
+
+    if (dns_cache_.size() > kMaxUniqueResolveDnsPerExec) {
+      // 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.
+    exec_.was_abandoned = true;
+    last_num_dns_ = exec_.num_dns;
+    base::MD5Final(&last_dns_digest_, &exec_.dns_digest);
+    return false;
+  }
+
+  // Builds a RequestInfo to service the specified PAC DNS operation.
+  static HostResolver::RequestInfo MakeRequestInfo(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;
+  }
+
+  void DoDnsOperation(const std::string& host, ResolveDnsOperation op,
+                      bool* out_cache_hit) {
+    CheckIsOnOriginThread();
+
+    if (cancelled_.IsSet())
+      return;
+
+    DCHECK(!pending_dns_.get());
+
+    HostResolver::RequestInfo info = MakeRequestInfo(host, op);
+
+    if (nonblocking_dns_) {
+      // 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);
+      }
+
+      // 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;

[mmenke, 2013/01/18 19:59:40]

I don't think this cache hit optimization is worth it, first pass, and may well
not be worth doing at all.

If we do go that route, think we could share a bit more logic with the blocking
route, on the worker thread.

[eroman, 2013/01/23 03:26:02]

This cuts down quite a few restarts, and IMO is definitely worth it.

Commonly PAC scripts will contain both a call to myIpAddress() and
dnsResolve(host). The IP address one is extremely likely to be serviced from the
cache.

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

Suppose it depends on how expensive script execution is and how expensive
waiting on roundtrips to the IO thread are.  If we didn't block, we could be
running the next several couple PAC scripts in the queue, and posting tasks to
get what addresses they need.

[eroman, 2013/01/24 23:07:15]

One final comment on this issue:

Waiting for the IO thread should be very short. In which case waiting for the
cached value makes sense whether or not the script execution is slow (since it
just waits an infinitesimal amount of time).

If on the other hand waiting for the task to reach the IO thread is NOT short,
then this suggests there is a slowdown happening on the IO thread.

If there is a slowdown on the IO thread, then there will also be a slowdown in
processing our DNS requests, and there will be a slowdown in receiving
simultaneous proxy resolve requests. So the benefit to restarting the PAC script
to discover other request's DNS also decreases.

+    }
+
+    pending_dns_.reset(new PendingDns(host, op));
+
+    int result = host_resolver()->Resolve(
+        info,
+        &pending_dns_->addresses, base::Bind(&Job::OnResolveCompletion, this),
+        &pending_dns_->handle, bound_net_log_);
+
+    if (result != ERR_IO_PENDING)
+      OnResolveCompletion(result);
+  }
+
+  void OnResolveCompletion(int result) {
+    CheckIsOnOriginThread();
+
+    DCHECK(!cancelled_.IsSet());
+
+    SaveDnsToLocalCache(pending_dns_->host, pending_dns_->op, result,
+                        pending_dns_->addresses);
+    pending_dns_.reset();
+
+    if (nonblocking_dns_) {
+      // Restart. This time it should make more progress due to having
+      // cached items.
+      worker_loop()->PostTask(FROM_HERE, base::Bind(&Job::Start, this));
+    } else {
+      // Otherwise wakeup the blocked worker thread.
+      event_.Signal();
+    }
+  }
+
+  void ScheduleRestartWithBlockingDns() {
+    MessageLoop::current()->PostTask(
+        FROM_HERE, base::Bind(&Job::RestartWithBlockingDns, this));
+  }
+
+  void RestartWithBlockingDns() {
+    DCHECK(nonblocking_dns_);
+    nonblocking_dns_ = false;
+    Start();
+  }
+
+  // Make a key for looking up |host, op| in |dns_cache_|. Strings are used for
+  // convenience, to avoid defining custom comparators.
+  static std::string GetCacheKey(const std::string& host,
+                                 ResolveDnsOperation op) {
+    return StringPrintf("%d:%s", op, host.c_str());
+  }
+
+  // Serialize |net_error, address_list| into something that can be saved into
+  // |dns_cache|.
+  static std::string MakeCacheValue(ResolveDnsOperation op,
+                                    int net_error,
+                                    const AddressList& address_list) {
+    if (net_error != OK)
+      return std::string();
+
+    // dnsResolve() and myIpAddress() are expected to return a single IP
+    // address. Whereas the *Ex versions are expected to return a semi-colon
+    // separated list.
+
+    if (op == DNS_RESOLVE || op == MY_IP_ADDRESS) {
+      return address_list.front().ToStringWithoutPort();
+    }
+
+    std::string address_list_str;
+    for (AddressList::const_iterator iter = address_list.begin();
+         iter != address_list.end(); ++iter) {
+      if (!address_list_str.empty())
+        address_list_str += ";";
+      const std::string address_string = iter->ToStringWithoutPort();
+      if (address_string.empty())
+        return std::string();
+      address_list_str += address_string;
+    }
+
+    return address_list_str;
+  }
+
+  bool GetDnsFromLocalCache(const std::string& host, ResolveDnsOperation op,
+                            std::string* output, bool* return_value) {
+    DnsCache::const_iterator it = dns_cache_.find(GetCacheKey(host, op));
+    if (it == dns_cache_.end())
+      return false;
+
+    *output = it->second;
+    *return_value = !it->second.empty();
+    return true;
+  }
+
+  void SaveDnsToLocalCache(const std::string& host, ResolveDnsOperation op,
+                           int net_error, const net::AddressList& addresses) {
+    dns_cache_[GetCacheKey(host, op)] =
+        MakeCacheValue(op, net_error, addresses);
+  }
+
+  Operation operation_;
+  bool nonblocking_dns_;

[mmenke, 2013/01/18 19:59:40]

Wonder if this should be a property of the PAC script.  Then we could detect
PACs that cache results from their different signatures, reset the JS
environment, and run all scripts synchronously.

Believe it would result in us handling all scripts correctly, as opposed to just
those that don't cache results.  Of course, it would make us slower for such
PACs, but at least they'd work.

[mmenke, 2013/01/18 19:59:40]

Suggest using blocking_dns_ instead.  "!non_blocking_dns_" gets a bit silly.

[eroman, 2013/01/23 03:26:02]

To make sure I understand:

Do you mean keep track of when a request falls back to blocking mode, and avoid
ever running requests for that PAC script in non-blocking mode again?

I don't think that alone is worth it. Here is why:

For starters, I don't believe such scripts truly exist in the wild, although as
a follow-up I would like to histogram this.

If such scripts are a reality and worth optimizing for, then we will need to do
better ==> right now by falling back to synchronous mode we have effectively
reduced the parallelism from 4 under MultiThreadedProxyResolver to just 1. So a
better fallback strategy would be to use MultiThreadedProxyResolver for such
scripts.

But yeah, I am hoping we won't need to do that, since I can't imagine legitimate
scripts behaving this way.

[eroman, 2013/01/23 03:26:02]

Done.

+
+  scoped_refptr<base::MessageLoopProxy> origin_loop_;
+  CompletionCallback callback_;
+  ProxyResolverV8Tracing* parent_;
+  base::CancellationFlag cancelled_;
+
+  scoped_refptr<ProxyResolverScriptData> script_data_;

[mmenke, 2013/01/18 19:59:40]

What do you think of splitting this class into two subclasses, to make it much
clearer which variables and methods live on each thread, and what their
interface is.

Currently, it's not easy to distinguish them, and to be sure there are no
contract violations.

The IOThread half can keep a reference to the worker thread half, so you can get
rid of the Add/RemoveRef calls.

It still wouldn't really have a clear owner, and while a weak_ptr could replace
some cancelled checks, it wouldn't be be able to replace the ones on the worker
thread, so doesn't really clean things up much, just serves to help ensure
thread safety.

[mmenke, 2013/01/18 20:02:39]

If you think that's too ugly, clearly separating out and labeling which
members/methods can be accessed on what thread would be an improvement.

[eroman, 2013/01/23 03:26:02]

I couldn't get it any cleaner splitting off into subclasses, since there is
still a fair bit of overlapping state (that lives between both threads).

I have re-organized the state variables, added more comments, and split up more
methods into *Blocking *NonBlocking versions so there is less |if
(blocking_dns_)| to follow. Hopefully this is easier to read.

+
+  base::WaitableEvent event_;
+
+  GURL url_;
+  ProxyInfo results_;
+  ProxyInfo* user_results_;
+  BoundNetLog bound_net_log_;
+
+  ExecutionState exec_;
+
+  int last_num_dns_;
+  base::MD5Digest last_dns_digest_;
+
+  typedef std::map<std::string, std::string> DnsCache;
+  DnsCache dns_cache_;
+
+  scoped_ptr<PendingDns> pending_dns_;
+};
+
+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);
+}
+
+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