Add a cap of six in-flight requests per host to the ResourceScheduler

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 "base/stl_util.h"
 #include "content/common/resource_messages.h"
 #include "content/browser/loader/resource_message_delegate.h"
 #include "content/public/browser/resource_controller.h"
 #include "content/public/browser/resource_request_info.h"
 #include "content/public/browser/resource_throttle.h"
 #include "ipc/ipc_message_macros.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"
 
 namespace content {
 
 static const size_t kMaxNumDelayableRequestsPerClient = 10;
+static const size_t kMaxNumDelayableRequestsPerHost = 6;
 
 // A thin wrapper around net::PriorityQueue that deals with
 // ScheduledResourceRequests instead of PriorityQueue::Pointers.
 class ResourceScheduler::RequestQueue {
+ private:
+  typedef net::PriorityQueue<ScheduledResourceRequest*> NetQueue;
+
  public:
+  class Iterator {
+   public:
+    Iterator(NetQueue* queue) : queue_(queue) {
+      DCHECK(queue != NULL);
+      current_pointer_ = queue_->FirstMax();
+    }
+
+    Iterator& operator++() {
+      current_pointer_ = queue_->NextHighest(current_pointer_);
+      return *this;
+    }
+
+    Iterator operator++(int) {
+      Iterator result(*this);
+      ++(*this);
+      return result;
+    }
+
+    ScheduledResourceRequest* value() {
+      return current_pointer_.value();
+    }
+
+    bool is_null() {
+      return current_pointer_.is_null();
+    }
+
+   private:
+    NetQueue* queue_;
+    NetQueue::Pointer current_pointer_;
+  };
+
   RequestQueue() : queue_(net::NUM_PRIORITIES) {}
   ~RequestQueue() {}
 
   // Adds |request| to the queue with given |priority|.
   void Insert(ScheduledResourceRequest* request,
               net::RequestPriority priority) {
     DCHECK(!ContainsKey(pointers_, request));
     NetQueue::Pointer pointer = queue_.Insert(request, priority);
     pointers_[request] = pointer;
   }
 
   // Removes |request| from the queue.
   void Erase(ScheduledResourceRequest* request) {
     PointerMap::iterator it = pointers_.find(request);
     DCHECK(it != pointers_.end());
     queue_.Erase(it->second);
     pointers_.erase(it);
   }
 
   // Returns the highest priority request that's queued, or NULL if none are.
   ScheduledResourceRequest* FirstMax() {
     return queue_.FirstMax().value();
   }
 
+  Iterator GetNextHighestIterator() {
+    return Iterator(&queue_);
+  }
+
   // Returns true if |request| is queued.
   bool IsQueued(ScheduledResourceRequest* request) const {
     return ContainsKey(pointers_, request);
   }
 
   // Returns true if no requests are queued.
   bool IsEmpty() const { return queue_.size() == 0; }
 
  private:
-  typedef net::PriorityQueue<ScheduledResourceRequest*> NetQueue;
   typedef std::map<ScheduledResourceRequest*, NetQueue::Pointer> PointerMap;
 
   NetQueue queue_;
   PointerMap pointers_;
 };
 
 // This is the handle we return to the ResourceDispatcherHostImpl so it can
 // interact with the request.
 class ResourceScheduler::ScheduledResourceRequest
     : public ResourceMessageDelegate,
@@ skipping 91 matching lines @@
     // There are several ways this could happen:
     // 1. <a ping> requests don't have a route_id.
     // 2. Most unittests don't send the IPCs needed to register Clients.
     // 3. The tab is closed while a RequestResource IPC is in flight.
     unowned_requests_.insert(request.get());
     request->Start();
     return request.PassAs<ResourceThrottle>();
   }
 
   Client* client = it->second;
-  if (ShouldStartRequest(request.get(), client)) {
+  if (ShouldStartRequest(request.get(), client) == kStartRequest) {
     StartRequest(request.get(), client);
   } else {
     client->pending_requests.Insert(request.get(), url_request->priority());
   }
   return request.PassAs<ResourceThrottle>();
 }
 
 void ResourceScheduler::RemoveRequest(ScheduledResourceRequest* request) {
   DCHECK(CalledOnValidThread());
   if (ContainsKey(unowned_requests_, request)) {
@@ skipping 107 matching lines @@
   client->pending_requests.Erase(request);
   client->pending_requests.Insert(request, request->url_request()->priority());
 
   if (new_priority > old_priority) {
     // Check if this request is now able to load at its new priority.
     LoadAnyStartablePendingRequests(client);
   }
 }
 
 void ResourceScheduler::LoadAnyStartablePendingRequests(Client* client) {
-  while (!client->pending_requests.IsEmpty()) {
-    ScheduledResourceRequest* request = client->pending_requests.FirstMax();
-    if (ShouldStartRequest(request, client)) {
+  // 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.
+
+  RequestQueue::Iterator request_iter =
+      client->pending_requests.GetNextHighestIterator();
+
+  while (!request_iter.is_null()) {
+    ScheduledResourceRequest* request = request_iter.value();
+    ShouldStartReqResult query_result = ShouldStartRequest(request, client);
+
+    if (query_result == kStartRequest) {
       client->pending_requests.Erase(request);
       StartRequest(request, client);
+
+      // StartRequest can modify the pending list, so we (re)start evaluation
+      // from the currently highest priority request.
+      request_iter = client->pending_requests.GetNextHighestIterator();
+    } else if (query_result == kDoNotStartRequest_KeepSearching) {
+      ++request_iter;
+      continue;
     } else {
+      DCHECK(query_result == kDoNotStartRequest_StopSearching);

[James Simonsen, 2013/11/13 01:26:23]

I'd prefer it be a switch instead of if/else. Let the compiler take care of
making sure all of the cases are covered instead of finding this in a debug
build at runtime. The D in DCHECK means only crash if we're debug.

[oystein (OOO til 10th of July), 2013/11/14 00:19:07]

The reason I didn't go with a switch is to avoid nasty gotos or a flag to be
able to break out of the outer while() loop; is the compile-time safety worth
the additional logic?

       break;
     }
   }
 }
 
-size_t ResourceScheduler::GetNumDelayableRequestsInFlight(
-    Client* client) const {
-  size_t count = 0;
+void ResourceScheduler::GetNumDelayableRequestsInFlight(

[James Simonsen, 2013/11/13 01:26:23]

It feels like we're doing a lot of work here now. Can we punt that to data
structures instead?

We could use a multimap to hold the inflight_delayable requests. Then you could
get the total number from size() and the number for this host from count(). The
downside is searching for the one to remove.

Alternatively, use a map of sets. The downside is handling empty map entries.

Any other ideas? I prefer the first one.

Either way, I think we're better off keeping inflight delayable and inflight
immediate requests separate. I should've done that when I wrote it.

[oystein (OOO til 10th of July), 2013/11/14 00:19:07]

I looked into this a bit now, I think the main problem is that we then have to
deal with multiple containers not only when removing a request, but also when
deleting a client and when reprioritizing a request. 

We could maintain a separate count of the delayable requests, but we'd still
have to loop through and check how many matches our current host so it doesn't
really gain us much.

Or we could store the requests in an std::map instead of an std::list and store
the net::HostPortPair as the value to avoid recreating it all the time

Thoughts?

[James Simonsen, 2013/11/14 19:22:43]

There has to be an easier way to keep track of all this. I don't really want to
spend any more time on it though, so I'm okay with what we've got.

[oystein (OOO til 10th of July), 2013/11/14 19:51:49]

I agree, but I suggest we wait until the next change to this system and
reevaluate at that point. It'll hopefully become more clear then.

+    Client* client,
+    net::HostPortPair* active_request_host,

[James Simonsen, 2013/11/13 01:26:23]

This should be a const reference. It shouldn't ever be null.

As much as possible, you should only ever pass a raw pointer if you expect the
callee to modify the object. Otherwise, it needs to be const and a pointer only
if it's nullable.

[oystein (OOO til 10th of July), 2013/11/14 19:51:49]

Done.

+    size_t* total_delayable,
+    size_t* total_for_active_host) const {
+  DCHECK(client != NULL && active_request_host != NULL &&
+         total_delayable != NULL && total_for_active_host != NULL);
+
+  size_t total_delayable_count = 0;
+  size_t same_host_count = 0;
   for (RequestSet::iterator it = client->in_flight_requests.begin();
        it != client->in_flight_requests.end(); ++it) {
+    net::HostPortPair host_port_pair =
+        net::HostPortPair::FromURL((*it)->url_request()->url());

[James Simonsen, 2013/11/13 01:26:23]

Yeah, the multimap or whatever would be nice here. Then we don't have to
repeatedly parse the URL.

+
+    if (active_request_host->Equals(host_port_pair)) {
+      same_host_count++;
+    }
+
     if ((*it)->url_request()->priority() < net::LOW) {
       const net::HttpServerProperties& http_server_properties =
           *(*it)->url_request()->context()->http_server_properties();
-      if (!http_server_properties.SupportsSpdy(
-          net::HostPortPair::FromURL((*it)->url_request()->url()))) {
-        ++count;
+
+      if (!http_server_properties.SupportsSpdy(host_port_pair)) {

[James Simonsen, 2013/11/13 01:26:23]

Maybe we should keep these in a separate set.

+        ++total_delayable_count;
       }
     }
   }
-  return count;
+  *total_delayable = total_delayable_count;
+  *total_for_active_host = same_host_count;
 }
 
 // ShouldStartRequest is the main scheduling algorithm.
 //
 // Requests are categorized into two categories:
 //
 // 1. Immediately issued requests, which are:
 //
 //   * Higher priority requests (>= net::LOW).
 //   * Synchronous requests.
 //   * Requests to SPDY-capable origin servers.
 //   * Non-HTTP[S] requests.
 //
 // 2. The remainder are delayable requests, which follow these rules:
 //
 //   * If no high priority requests are in flight, start loading low priority
 //     requests.
 //   * Once the renderer has a <body>, start loading delayable requests.
 //   * Never exceed 10 delayable requests in flight per client.
+//   * Never exceed 6 delayable requests for a given host.
 //   * Prior to <body>, allow one delayable request to load at a time.
-bool ResourceScheduler::ShouldStartRequest(ScheduledResourceRequest* request,
-                                           Client* client) const {
+ResourceScheduler::ShouldStartReqResult ResourceScheduler::ShouldStartRequest(
+    ScheduledResourceRequest* request,
+    Client* client) const {
   const net::URLRequest& url_request = *request->url_request();
 
   // TODO(simonjam): This may end up causing disk contention. We should
   // experiment with throttling if that happens.
   if (!url_request.url().SchemeIsHTTPOrHTTPS()) {
-    return true;
+    return kStartRequest;
   }
 
   const net::HttpServerProperties& http_server_properties =
       *url_request.context()->http_server_properties();
 
+  if (url_request.priority() >= net::LOW ||
+      !ResourceRequestInfo::ForRequest(&url_request)->IsAsync()) {
+    return kStartRequest;
+  }
+
+  net::HostPortPair host_port_pair =
+      net::HostPortPair::FromURL(url_request.url());
+
   // TODO(willchan): We should really improve this algorithm as described in
   // crbug.com/164101. Also, theoretically we should not count a SPDY request
   // against the delayable requests limit.
-  bool origin_supports_spdy = http_server_properties.SupportsSpdy(
-      net::HostPortPair::FromURL(url_request.url()));
-
-  if (url_request.priority() >= net::LOW ||
-      !ResourceRequestInfo::ForRequest(&url_request)->IsAsync() ||
-      origin_supports_spdy) {
-    return true;
+  if (http_server_properties.SupportsSpdy(host_port_pair)) {
+    return kStartRequest;
   }
 
-  size_t num_delayable_requests_in_flight =
-      GetNumDelayableRequestsInFlight(client);
+  size_t num_delayable_requests_in_flight = 0;
+  size_t num_requests_in_flight_for_host = 0;
+  GetNumDelayableRequestsInFlight(client, &host_port_pair,
+                                  &num_delayable_requests_in_flight,
+                                  &num_requests_in_flight_for_host);
+
   if (num_delayable_requests_in_flight >= kMaxNumDelayableRequestsPerClient) {
-    return false;
+    return kDoNotStartRequest_StopSearching;
+  }
+
+  if (num_requests_in_flight_for_host >= kMaxNumDelayableRequestsPerHost) {
+    // There may be other requests for other hosts we'd allow, so keep checking.
+    return kDoNotStartRequest_KeepSearching;
   }
 
   bool have_immediate_requests_in_flight =
       client->in_flight_requests.size() > num_delayable_requests_in_flight;
   if (have_immediate_requests_in_flight && !client->has_body &&
       num_delayable_requests_in_flight != 0) {
-    return false;
+    return kDoNotStartRequest_StopSearching;
   }
 
-  return true;
+  return kStartRequest;
 }
 
 ResourceScheduler::ClientId ResourceScheduler::MakeClientId(
     int child_id, int route_id) {
   return (static_cast<ResourceScheduler::ClientId>(child_id) << 32) | route_id;
 }
 
 }  // namespace content