Reland of [ResourceScheduler] Yield after starting several requests

content/browser/loader/resource_scheduler.cc

 // 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 "content/browser/loader/resource_scheduler.h"
 
 #include <stdint.h>
 #include <set>
 #include <string>
 #include <utility>
 #include <vector>
 
 #include "base/feature_list.h"
 #include "base/macros.h"
 #include "base/metrics/field_trial.h"
+#include "base/metrics/field_trial_params.h"
 #include "base/metrics/histogram_macros.h"
 #include "base/stl_util.h"
 #include "base/supports_user_data.h"
 #include "base/threading/thread_task_runner_handle.h"
 #include "content/common/resource_messages.h"
 #include "content/public/browser/resource_request_info.h"
 #include "content/public/browser/resource_throttle.h"
 #include "net/base/host_port_pair.h"
 #include "net/base/load_flags.h"
 #include "net/base/request_priority.h"
 #include "net/http/http_server_properties.h"
 #include "net/url_request/url_request.h"
 #include "net/url_request/url_request_context.h"
 #include "url/scheme_host_port.h"
 
 namespace content {
 
 namespace {
 
 // When kPrioritySupportedRequestsDelayable is enabled, requests for
 // H2/QUIC/SPDY resources can be delayed by the ResourceScheduler just as
 // HTTP/1.1 resources are. Disabling this appears to have negative performance
 // impact, see https://crbug.com/655585.
 const base::Feature kPrioritySupportedRequestsDelayable{
     "PrioritySupportedRequestsDelayable", base::FEATURE_DISABLED_BY_DEFAULT};
 
+// In the event that many resource requests are started quickly, this feature
+// will periodically yield (e.g., delaying starting of requests) by posting a
+// task and waiting for the task to run to resume. This allows other
+// operations that rely on the IO thread (e.g., already running network
+// requests) to make progress.
+const base::Feature kNetworkSchedulerYielding{
+    "NetworkSchedulerYielding", base::FEATURE_DISABLED_BY_DEFAULT};
+const char kMaxRequestsBeforeYieldingParam[] = "MaxRequestsBeforeYieldingParam";
+const int kMaxRequestsBeforeYieldingDefault = 5;
+
 enum StartMode {
   START_SYNC,
   START_ASYNC
 };
 
 // Flags identifying various attributes of the request that are used
 // when making scheduling decisions.
 using RequestAttributes = uint8_t;
 const RequestAttributes kAttributeNone = 0x00;
 const RequestAttributes kAttributeInFlight = 0x01;
 const RequestAttributes kAttributeDelayable = 0x02;
 const RequestAttributes kAttributeLayoutBlocking = 0x04;
 
 // Reasons why pending requests may be started.  For logging only.
 enum class RequestStartTrigger {
   NONE,
   COMPLETION_PRE_BODY,
   COMPLETION_POST_BODY,
   BODY_REACHED,
   CLIENT_KILL,
   SPDY_PROXY_DETECTED,
   REQUEST_REPRIORITIZED,
+  START_WAS_YIELDED,
 };
 
 const char* RequestStartTriggerString(RequestStartTrigger trigger) {
   switch (trigger) {
     case RequestStartTrigger::NONE:
       return "NONE";
     case RequestStartTrigger::COMPLETION_PRE_BODY:
       return "COMPLETION_PRE_BODY";
     case RequestStartTrigger::COMPLETION_POST_BODY:
       return "COMPLETION_POST_BODY";
     case RequestStartTrigger::BODY_REACHED:
       return "BODY_REACHED";
     case RequestStartTrigger::CLIENT_KILL:
       return "CLIENT_KILL";
     case RequestStartTrigger::SPDY_PROXY_DETECTED:
       return "SPDY_PROXY_DETECTED";
     case RequestStartTrigger::REQUEST_REPRIORITIZED:
       return "REQUEST_REPRIORITIZED";
+    case RequestStartTrigger::START_WAS_YIELDED:
+      return "START_WAS_YIELDED";
   }
   NOTREACHED();
   return "Unknown";
 }
 
 }  // namespace
 
 // The maximum number of delayable requests to allow to be in-flight at any
 // point in time (across all hosts).
 static const size_t kMaxNumDelayableRequestsPerClient = 10;
@@ skipping 249 matching lines @@
 void ResourceScheduler::RequestQueue::Insert(
     ScheduledResourceRequest* request) {
   DCHECK(!base::ContainsKey(pointers_, request));
   request->set_fifo_ordering(MakeFifoOrderingId());
   pointers_[request] = queue_.insert(request);
 }
 
 // Each client represents a tab.
 class ResourceScheduler::Client {
  public:
-  explicit Client(bool priority_requests_delayable)
+  Client(bool priority_requests_delayable,
+         bool yielding_scheduler_enabled,
+         int max_requests_before_yielding)
       : is_loaded_(false),
         has_html_body_(false),
         using_spdy_proxy_(false),
         in_flight_delayable_count_(0),
         total_layout_blocking_count_(0),
         priority_requests_delayable_(priority_requests_delayable),
         has_pending_start_task_(false),
+        started_requests_since_yielding_(0),
+        did_scheduler_yield_(false),
+        yielding_scheduler_enabled_(yielding_scheduler_enabled),
+        max_requests_before_yielding_(max_requests_before_yielding),
         weak_ptr_factory_(this) {}
 
   ~Client() {}
 
   void ScheduleRequest(net::URLRequest* url_request,
                        ScheduledResourceRequest* request) {
     SetRequestAttributes(request, DetermineRequestAttributes(request));
-    if (ShouldStartRequest(request) == START_REQUEST) {
+    ShouldStartReqResult should_start = ShouldStartRequest(request);
+    if (should_start == START_REQUEST) {
       // New requests can be started synchronously without issue.
       StartRequest(request, START_SYNC, RequestStartTrigger::NONE);
     } else {
       pending_requests_.Insert(request);
+      if (should_start == YIELD_SCHEDULER)
+        did_scheduler_yield_ = true;
     }
   }
 
   void RemoveRequest(ScheduledResourceRequest* request) {
     if (pending_requests_.IsQueued(request)) {
       pending_requests_.Erase(request);
       DCHECK(!base::ContainsKey(in_flight_requests_, request));
     } else {
       EraseInFlightRequest(request);
 
@@ skipping 76 matching lines @@
       ScheduleLoadAnyStartablePendingRequests(
           RequestStartTrigger::REQUEST_REPRIORITIZED);
     }
   }
 
  private:
   enum ShouldStartReqResult {
     DO_NOT_START_REQUEST_AND_STOP_SEARCHING,
     DO_NOT_START_REQUEST_AND_KEEP_SEARCHING,
     START_REQUEST,
+    YIELD_SCHEDULER
   };
 
   void InsertInFlightRequest(ScheduledResourceRequest* request) {
     in_flight_requests_.insert(request);
     SetRequestAttributes(request, DetermineRequestAttributes(request));
   }
 
   void EraseInFlightRequest(ScheduledResourceRequest* request) {
     size_t erased = in_flight_requests_.erase(request);
     DCHECK_EQ(1u, erased);
@@ skipping 119 matching lines @@
         if (same_host_count >= kMaxNumDelayableRequestsPerHostPerClient)
           return true;
       }
     }
     return false;
   }
 
   void StartRequest(ScheduledResourceRequest* request,
                     StartMode start_mode,
                     RequestStartTrigger trigger) {
+    started_requests_since_yielding_ += 1;
+    if (started_requests_since_yielding_ == 1) {
+      // This is the first started request since last yielding. Post a task to
+      // reset the counter and start any yielded tasks if necessary. We post
+      // this now instead of when we first yield so that if there is a pause
+      // between requests the counter is reset.
+      base::ThreadTaskRunnerHandle::Get()->PostTask(
+          FROM_HERE,
+          base::Bind(&Client::ResumeAfterYielding,
+                     weak_ptr_factory_.GetWeakPtr()));
+    }
+
     // Only log on requests that were blocked by the ResourceScheduler.
     if (start_mode == START_ASYNC) {
       DCHECK_NE(RequestStartTrigger::NONE, trigger);
       request->url_request()->net_log().AddEvent(
           net::NetLogEventType::RESOURCE_SCHEDULER_REQUEST_STARTED,
           net::NetLog::StringCallback(
               "trigger", RequestStartTriggerString(trigger)));
     }
     InsertInFlightRequest(request);
     request->Start(start_mode);
@@ skipping 43 matching lines @@
 
     // TODO(simonjam): This may end up causing disk contention. We should
     // experiment with throttling if that happens.
     if (!url_request.url().SchemeIsHTTPOrHTTPS())
       return START_REQUEST;
 
     const net::HostPortPair& host_port_pair = request->host_port_pair();
 
     if (!priority_requests_delayable_) {
       if (using_spdy_proxy_ && url_request.url().SchemeIs(url::kHttpScheme))
-        return START_REQUEST;
+        return ShouldStartOrYieldRequest();
 
       url::SchemeHostPort scheme_host_port(url_request.url());
 
       net::HttpServerProperties& http_server_properties =
           *url_request.context()->http_server_properties();
 
       // TODO(willchan): We should really improve this algorithm as described in
       // crbug.com/164101. Also, theoretically we should not count a
       // request-priority capable request against the delayable requests limit.
       if (http_server_properties.SupportsRequestPriority(scheme_host_port))
-        return START_REQUEST;
+        return ShouldStartOrYieldRequest();
     }
 
     // Non-delayable requests.
     if (!RequestAttributesAreSet(request->attributes(), kAttributeDelayable))
-      return START_REQUEST;
+      return ShouldStartOrYieldRequest();
 
     if (in_flight_delayable_count_ >= kMaxNumDelayableRequestsPerClient)
       return DO_NOT_START_REQUEST_AND_STOP_SEARCHING;
 
     if (ShouldKeepSearching(host_port_pair)) {
       // There may be other requests for other hosts that may be allowed,
       // so keep checking.
       return DO_NOT_START_REQUEST_AND_KEEP_SEARCHING;
     }
 
@@ skipping 14 matching lines @@
       if (in_flight_requests_.size() > 0 &&
           (in_flight_delayable_count_ >=
            kMaxNumDelayableWhileLayoutBlockingPerClient)) {
         // Block the request if at least one request is in flight and the
         // number of in-flight delayable requests has hit the configured
         // limit.
         return DO_NOT_START_REQUEST_AND_STOP_SEARCHING;
       }
     }
 
-    return START_REQUEST;
+    return ShouldStartOrYieldRequest();
   }
 
   // It is common for a burst of messages to come from the renderer which
   // trigger starting pending requests. Naively, this would result in O(n*m)
   // behavior for n pending requests and m <= n messages, as
   // LoadAnyStartablePendingRequest is O(n) for n pending requests. To solve
   // this, just post a task to the end of the queue to call the method,
   // coalescing the m messages into a single call to
   // LoadAnyStartablePendingRequests.
   // TODO(csharrison): Reconsider this if IPC batching becomes an easy to use
   // pattern.
   void ScheduleLoadAnyStartablePendingRequests(RequestStartTrigger trigger) {
     if (has_pending_start_task_)
       return;
     has_pending_start_task_ = true;
     base::ThreadTaskRunnerHandle::Get()->PostTask(
         FROM_HERE, base::Bind(&Client::LoadAnyStartablePendingRequests,
                               weak_ptr_factory_.GetWeakPtr(), trigger));
   }
 
+  void ResumeAfterYielding() {

[Charlie Harrison, 2017/02/22 17:42:14]

nit: I think a better name is "ResumeIfYielded"

[jkarlin, 2017/02/22 17:49:25]

Done.

+    bool yielded = did_scheduler_yield_;
+    started_requests_since_yielding_ = 0;
+    did_scheduler_yield_ = false;
+
+    if (yielded)
+      LoadAnyStartablePendingRequests(RequestStartTrigger::START_WAS_YIELDED);
+  }
+
+  // For a request that is ready to start, return START_REQUEST if the
+  // scheduler doesn't need to yield, else YIELD_SCHEDULER.
+  ShouldStartReqResult ShouldStartOrYieldRequest() const {
+    DCHECK_GE(started_requests_since_yielding_, 0);
+    if (!yielding_scheduler_enabled_)

[Charlie Harrison, 2017/02/22 17:42:14]

nit: merge this if statement into the below one:

if (yielding_scheduler_enabled_ && started_requests_since_yielding_ >=
max_requests_before_yielding_)...

[jkarlin, 2017/02/22 17:49:25]

Done.

+      return START_REQUEST;
+
+    if (started_requests_since_yielding_ >= max_requests_before_yielding_)
+      return YIELD_SCHEDULER;
+    return START_REQUEST;
+  }
+
   void LoadAnyStartablePendingRequests(RequestStartTrigger trigger) {
     // We iterate through all the pending requests, starting with the highest
     // priority one. For each entry, one of three things can happen:
     // 1) We start the request, remove it from the list, and keep checking.
     // 2) We do NOT start the request, but ShouldStartRequest() signals us that
     //     there may be room for other requests, so we keep checking and leave
     //     the previous request still in the list.
     // 3) We do not start the request, same as above, but StartRequest() tells
     //     us there's no point in checking any further requests.
     has_pending_start_task_ = false;
@@ skipping 11 matching lines @@
         // StartRequest can modify the pending list, so we (re)start evaluation
         // from the currently highest priority request. Avoid copying a singular
         // iterator, which would trigger undefined behavior.
         if (pending_requests_.GetNextHighestIterator() ==
             pending_requests_.End())
           break;
         request_iter = pending_requests_.GetNextHighestIterator();
       } else if (query_result == DO_NOT_START_REQUEST_AND_KEEP_SEARCHING) {
         ++request_iter;
         continue;
+      } else if (query_result == YIELD_SCHEDULER) {
+        did_scheduler_yield_ = true;
+        break;
       } else {
         DCHECK(query_result == DO_NOT_START_REQUEST_AND_STOP_SEARCHING);
         break;
       }
     }
   }
 
   bool is_loaded_;
   // Tracks if the main HTML parser has reached the body which marks the end of
   // layout-blocking resources.
   bool has_html_body_;
   bool using_spdy_proxy_;
   RequestQueue pending_requests_;
   RequestSet in_flight_requests_;
   // The number of delayable in-flight requests.
   size_t in_flight_delayable_count_;
   // The number of layout-blocking in-flight requests.
   size_t total_layout_blocking_count_;
 
   // True if requests to servers that support priorities (e.g., H2/QUIC) can
   // be delayed.
   bool priority_requests_delayable_;
 
   bool has_pending_start_task_;
 
+  // The number of started requests since the last ResumeFromYielding task was
+  // run.
+  int started_requests_since_yielding_;
+
+  // If the scheduler had to yield the start of a request since the last
+  // ResumeFromYielding task was run.
+  bool did_scheduler_yield_;

[Charlie Harrison, 2017/02/22 17:42:14]

Do we really need this member? Can't we just use
started_requests_since_yielding_ >= max_requests_before_yielding_? 

[jkarlin, 2017/02/22 17:49:25]

We need it. started_requests_since_yielding_ won't increment for yielded
requests (but will increment for unyieldable requests, e.g., synchronous).

[jkarlin, 2017/02/22 17:58:37]

Ah, what you said was a little more subtle. If we use >= then we can't be sure
if we yielded or not and we'd rename this "scheduler_possibly_yielded". We'd
sometimes run LoadAnyStartablePendingRequests extra times but we wouldn't need
to keep track of did_scheduler_yield_. 

WDYT?

[Charlie Harrison, 2017/02/22 18:01:36]

I thought about that but it seemed weird and hard to understand. I'm happy with
the bool.

+
+  // Whether or not to periodically yield when starting lots of requests.
+  bool yielding_scheduler_enabled_;
+
+  // The number of requests that can start before yielding.
+  int max_requests_before_yielding_;
+
   base::WeakPtrFactory<ResourceScheduler::Client> weak_ptr_factory_;
 };
 
 ResourceScheduler::ResourceScheduler()
     : priority_requests_delayable_(
-          base::FeatureList::IsEnabled(kPrioritySupportedRequestsDelayable)) {}
+          base::FeatureList::IsEnabled(kPrioritySupportedRequestsDelayable)),
+      yielding_scheduler_enabled_(
+          base::FeatureList::IsEnabled(kNetworkSchedulerYielding)),
+      max_requests_before_yielding_(base::GetFieldTrialParamByFeatureAsInt(
+          kNetworkSchedulerYielding,
+          kMaxRequestsBeforeYieldingParam,
+          kMaxRequestsBeforeYieldingDefault)) {}
 
 ResourceScheduler::~ResourceScheduler() {
   DCHECK(unowned_requests_.empty());
   DCHECK(client_map_.empty());
 }
 
 std::unique_ptr<ResourceThrottle> ResourceScheduler::ScheduleRequest(
     int child_id,
     int route_id,
     bool is_async,
@@ skipping 36 matching lines @@
   Client* client = client_it->second;
   client->RemoveRequest(request);
 }
 
 void ResourceScheduler::OnClientCreated(int child_id,
                                         int route_id) {
   DCHECK(CalledOnValidThread());
   ClientId client_id = MakeClientId(child_id, route_id);
   DCHECK(!base::ContainsKey(client_map_, client_id));
 
-  Client* client = new Client(priority_requests_delayable_);
+  Client* client =
+      new Client(priority_requests_delayable_, yielding_scheduler_enabled_,
+                 max_requests_before_yielding_);
   client_map_[client_id] = client;
 }
 
 void ResourceScheduler::OnClientDeleted(int child_id, int route_id) {
   DCHECK(CalledOnValidThread());
   ClientId client_id = MakeClientId(child_id, route_id);
   ClientMap::iterator it = client_map_.find(client_id);
   DCHECK(it != client_map_.end());
 
   Client* client = it->second;
@@ skipping 118 matching lines @@
   client->ReprioritizeRequest(scheduled_resource_request, old_priority_params,
                               new_priority_params);
 }
 
 ResourceScheduler::ClientId ResourceScheduler::MakeClientId(
     int child_id, int route_id) {
   return (static_cast<ResourceScheduler::ClientId>(child_id) << 32) | route_id;
 }
 
 }  // namespace content