Introduce an intra-priority level sorting value - Chromium Side

content/browser/loader/resource_scheduler.cc

Index: content/browser/loader/resource_scheduler.cc
diff --git a/content/browser/loader/resource_scheduler.cc b/content/browser/loader/resource_scheduler.cc
index 1753832998748c77099374a617f170a4e3c8b2c8..37dce454e54b5f5a44ee8c4b7822c5be366723c6 100644
--- a/content/browser/loader/resource_scheduler.cc
+++ b/content/browser/loader/resource_scheduler.cc
@@ -2,6 +2,8 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
+#include <set>
+
 #include "content/browser/loader/resource_scheduler.h"
 
 #include "base/stl_util.h"
@@ -23,55 +25,17 @@ 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;
 
+class ResourceScheduler::RequestQueue {
  public:
-  class Iterator {
-   public:
-    Iterator(NetQueue* queue) : queue_(queue) {
-      DCHECK(queue != NULL);
-      current_pointer_ = queue_->FirstMax();
-    }
-
-    Iterator& operator++() {
-      current_pointer_ = queue_->GetNextTowardsLastMin(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_;
-  };
+  typedef std::multiset<ScheduledResourceRequest*, ScheduledResourceSorter>
+      NetQueue;
 
-  RequestQueue() : queue_(net::NUM_PRIORITIES) {}
+  RequestQueue() : fifo_ordering_ids_(0) {}
   ~RequestQueue() {}
 
   // Adds |request| to the queue with given |priority|.
-  void Insert(ScheduledResourceRequest* request,
-              net::RequestPriority priority, int value) {
-    DCHECK(!ContainsKey(pointers_, request));
-    int calculated_priority = (priority << 16) | (0xFFFF & value);
-    NetQueue::Pointer pointer = queue_.Insert(request, calculated_priority);
-    pointers_[request] = pointer;
-  }
+  void Insert(ScheduledResourceRequest* request);
 
   // Removes |request| from the queue.
   void Erase(ScheduledResourceRequest* request) {
@@ -79,17 +43,16 @@ class ResourceScheduler::RequestQueue {
     DCHECK(it != pointers_.end());
     if (it == pointers_.end())
       return;
-    queue_.Erase(it->second);
+    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();
+  NetQueue::iterator GetNextHighestIterator() {
+    return queue_.begin();
   }
 
-  Iterator GetNextHighestIterator() {
-    return Iterator(&queue_);
+  NetQueue::iterator End() {
+    return queue_.end();
   }
 
   // Returns true if |request| is queued.
@@ -101,7 +64,16 @@ class ResourceScheduler::RequestQueue {
   bool IsEmpty() const { return queue_.size() == 0; }
 
  private:
-  typedef std::map<ScheduledResourceRequest*, NetQueue::Pointer> PointerMap;
+  typedef std::map<ScheduledResourceRequest*, NetQueue::iterator> PointerMap;
+
+  uint32 MakeFifoOrderingId() {
+    fifo_ordering_ids_ += 1;
+    return fifo_ordering_ids_;
+  }
+
+  // Used to create an ordering ID for scheduled resources so that resources
+  // with same priority/intra_priority stay in fifo order.
+  uint32 fifo_ordering_ids_;
 
   NetQueue queue_;
   PointerMap pointers_;
@@ -122,7 +94,8 @@ class ResourceScheduler::ScheduledResourceRequest
         ready_(false),
         deferred_(false),
         scheduler_(scheduler),
-        priorityValue_(0) {
+        intra_priority_value_(0),
+        fifo_ordering_(0) {
     TRACE_EVENT_ASYNC_BEGIN1("net", "URLRequest", request_,
                              "url", request->url().spec());
   }
@@ -143,8 +116,15 @@ class ResourceScheduler::ScheduledResourceRequest
   const ClientId& client_id() const { return client_id_; }
   net::URLRequest* url_request() { return request_; }
   const net::URLRequest* url_request() const { return request_; }
-  int priorityValue() const { return priorityValue_; }
-  void setPriorityValue(int priorityValue) { priorityValue_ = priorityValue; }
+  net::RequestPriority priority() const { return request_->priority(); }
+  int intra_priority_value() const { return intra_priority_value_; }
+  void set_intra_priority_value(int intra_priority_value) {
+    intra_priority_value_ = intra_priority_value;
+  }
+  uint32 fifo_ordering() const { return fifo_ordering_; }
+  void set_fifo_ordering(uint32 fifo_ordering) {
+    fifo_ordering_ = fifo_ordering;
+  }
 
  private:
   // ResourceMessageDelegate interface:
@@ -167,8 +147,9 @@ class ResourceScheduler::ScheduledResourceRequest
     return "ResourceScheduler";
   }
 
-  void DidChangePriority(int request_id, net::RequestPriority new_priority, int value) {
-    scheduler_->ReprioritizeRequest(this, new_priority, value);
+  void DidChangePriority(int request_id, net::RequestPriority new_priority,
+                         int intra_priority_value) {
+    scheduler_->ReprioritizeRequest(this, new_priority, intra_priority_value);
   }
 
   ClientId client_id_;
@@ -176,11 +157,37 @@ class ResourceScheduler::ScheduledResourceRequest
   bool ready_;
   bool deferred_;
   ResourceScheduler* scheduler_;
-  int priorityValue_;
+  int intra_priority_value_;
+  uint32 fifo_ordering_;
 
   DISALLOW_COPY_AND_ASSIGN(ScheduledResourceRequest);
 };
 
+bool ResourceScheduler::ScheduledResourceSorter::operator()(
+    const ScheduledResourceRequest* a,
+    const ScheduledResourceRequest* b) const {
+  // Want the set to be ordered first by decreasing priority, then by
+  // decreasing intra_priority.
+  // ie. with (priority, intra_priority)
+  // [(1, 0), (1, 0), (0, 100), (0, 0)]
+  if (a->priority() != b->priority())

[darin (slow to review), 2014/02/28 05:14:12]

it seems like you want to treat priority as a tuple with two values: major and
minor. that suggests that RequestPriority should become a struct with major and
minor fields, no?

since the network stack only needs to the major field, perhaps this implies that
net::RequestPriority shouldn't change but rather that we should invent a new
content level struct to represent this new priority representation.

[shatch, 2014/03/03 18:57:15]

Done.

+    return a->priority() > b->priority();
+
+  if (a->intra_priority_value() != b->intra_priority_value())
+    return a->intra_priority_value() > b->intra_priority_value();
+
+  // If priority/intra_priority is the same, fall back to fifo ordering.
+  // std::multiset doesn't guarantee this until c++11.
+  return a->fifo_ordering() < b->fifo_ordering();
+}
+
+void ResourceScheduler::RequestQueue::Insert(
+    ScheduledResourceRequest* request) {
+  DCHECK(!ContainsKey(pointers_, request));
+  request->set_fifo_ordering(MakeFifoOrderingId());
+  pointers_[request] = queue_.insert(request);
+}
+
 // Each client represents a tab.
 struct ResourceScheduler::Client {
   Client() : has_body(false), using_spdy_proxy(false) {}
@@ -224,7 +231,7 @@ scoped_ptr<ResourceThrottle> ResourceScheduler::ScheduleRequest(
   if (ShouldStartRequest(request.get(), client) == START_REQUEST) {
     StartRequest(request.get(), client);
   } else {
-    client->pending_requests.Insert(request.get(), url_request->priority(), request->priorityValue());
+    client->pending_requests.Insert(request.get());
   }
   return request.PassAs<ResourceThrottle>();
 }
@@ -341,7 +348,8 @@ void ResourceScheduler::StartRequest(ScheduledResourceRequest* request,
 }
 
 void ResourceScheduler::ReprioritizeRequest(ScheduledResourceRequest* request,
-                                            net::RequestPriority new_priority, int value) {
+                                            net::RequestPriority new_priority,
+                                            int new_intra_priority_value) {
   if (request->url_request()->load_flags() & net::LOAD_IGNORE_LIMITS) {
     // We should not be re-prioritizing requests with the
     // IGNORE_LIMITS flag.
@@ -349,15 +357,21 @@ void ResourceScheduler::ReprioritizeRequest(ScheduledResourceRequest* request,
     return;
   }
   net::RequestPriority old_priority = request->url_request()->priority();
-  DCHECK_NE(new_priority, old_priority);
+  int old_intra_priority = request->intra_priority_value();
+  DCHECK((new_priority != old_priority) ||
+         (old_intra_priority != new_intra_priority_value));
   request->url_request()->SetPriority(new_priority);
-  request->setPriorityValue(value);
+  request->set_intra_priority_value(new_intra_priority_value);
   ClientMap::iterator client_it = client_map_.find(request->client_id());
   if (client_it == client_map_.end()) {
     // The client was likely deleted shortly before we received this IPC.
     return;
   }
 
+  if ((new_priority == old_priority) &&
+      (new_intra_priority_value == old_intra_priority))
+    return;
+
   Client *client = client_it->second;
   if (!client->pending_requests.IsQueued(request)) {
     DCHECK(ContainsKey(client->in_flight_requests, request));
@@ -366,8 +380,7 @@ void ResourceScheduler::ReprioritizeRequest(ScheduledResourceRequest* request,
   }
 
   client->pending_requests.Erase(request);
-  client->pending_requests.Insert(request,
-                                  request->url_request()->priority(), value);
+  client->pending_requests.Insert(request);
 
   if (new_priority > old_priority) {
     // Check if this request is now able to load at its new priority.
@@ -384,12 +397,10 @@ void ResourceScheduler::LoadAnyStartablePendingRequests(Client* client) {
   //    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 =
+  RequestQueue::NetQueue::iterator request_iter =
       client->pending_requests.GetNextHighestIterator();
-
-  while (!request_iter.is_null()) {
-    ScheduledResourceRequest* request = request_iter.value();
+  while (request_iter != client->pending_requests.End()) {
+    ScheduledResourceRequest* request = *request_iter;
     ShouldStartReqResult query_result = ShouldStartRequest(request, client);
 
     if (query_result == START_REQUEST) {
@@ -399,7 +410,8 @@ void ResourceScheduler::LoadAnyStartablePendingRequests(Client* client) {
       // 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 (client->pending_requests.GetNextHighestIterator().is_null())
+      if (client->pending_requests.GetNextHighestIterator() ==
+          client->pending_requests.End())
         break;
       request_iter = client->pending_requests.GetNextHighestIterator();
     } else if (query_result == DO_NOT_START_REQUEST_AND_KEEP_SEARCHING) {