Revert of Introduce an intra-priority level sorting value - Chromium Side

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 <set>
-
 #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;
 
-struct ResourceScheduler::RequestPriorityParams {
-  RequestPriorityParams()
-    : priority(net::DEFAULT_PRIORITY),
-      intra_priority(0) {
-  }
+ public:
+  class Iterator {
+   public:
+    Iterator(NetQueue* queue) : queue_(queue) {
+      DCHECK(queue != NULL);
+      current_pointer_ = queue_->FirstMax();
+    }
 
-  RequestPriorityParams(net::RequestPriority priority, int intra_priority)
-    : priority(priority),
-      intra_priority(intra_priority) {
-  }
+    Iterator& operator++() {
+      current_pointer_ = queue_->GetNextTowardsLastMin(current_pointer_);
+      return *this;
+    }
 
-  bool operator==(const RequestPriorityParams& other) const {
-    return (priority == other.priority) &&
-        (intra_priority == other.intra_priority);
-  }
+    Iterator operator++(int) {
+      Iterator result(*this);
+      ++(*this);
+      return result;
+    }
 
-  bool operator!=(const RequestPriorityParams& other) const {
-    return !(*this == other);
-  }
+    ScheduledResourceRequest* value() {
+      return current_pointer_.value();
+    }
 
-  bool GreaterThan(const RequestPriorityParams& other) const {
-    if (priority != other.priority)
-      return priority > other.priority;
-    return intra_priority > other.intra_priority;
-  }
+    bool is_null() {
+      return current_pointer_.is_null();
+    }
 
-  net::RequestPriority priority;
-  int intra_priority;
-};
+   private:
+    NetQueue* queue_;
+    NetQueue::Pointer current_pointer_;
+  };
 
-class ResourceScheduler::RequestQueue {
- public:
-  typedef std::multiset<ScheduledResourceRequest*, ScheduledResourceSorter>
-      NetQueue;
-
-  RequestQueue() : fifo_ordering_ids_(0) {}
+  RequestQueue() : queue_(net::NUM_PRIORITIES) {}
   ~RequestQueue() {}
 
   // Adds |request| to the queue with given |priority|.
-  void Insert(ScheduledResourceRequest* request);
+  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());
     if (it == pointers_.end())
       return;
-    queue_.erase(it->second);
+    queue_.Erase(it->second);
     pointers_.erase(it);
   }
 
-  NetQueue::iterator GetNextHighestIterator() {
-    return queue_.begin();
+  // Returns the highest priority request that's queued, or NULL if none are.
+  ScheduledResourceRequest* FirstMax() {
+    return queue_.FirstMax().value();
   }
 
-  NetQueue::iterator End() {
-    return queue_.end();
+  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 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_;
+  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,
       public ResourceThrottle {
  public:
   ScheduledResourceRequest(const ClientId& client_id,
                            net::URLRequest* request,
-                           ResourceScheduler* scheduler,
-                           const RequestPriorityParams& priority)
+                           ResourceScheduler* scheduler)
       : ResourceMessageDelegate(request),
         client_id_(client_id),
         request_(request),
         ready_(false),
         deferred_(false),
-        scheduler_(scheduler),
-        priority_(priority),
-        fifo_ordering_(0) {
+        scheduler_(scheduler) {
     TRACE_EVENT_ASYNC_BEGIN1("net", "URLRequest", request_,
                              "url", request->url().spec());
   }
 
   virtual ~ScheduledResourceRequest() {
     scheduler_->RemoveRequest(this);
   }
 
   void Start() {
     TRACE_EVENT_ASYNC_STEP_PAST0("net", "URLRequest", request_, "Queued");
     ready_ = true;
     if (deferred_ && request_->status().is_success()) {
       deferred_ = false;
       controller()->Resume();
     }
   }
 
-  void set_request_priority_params(const RequestPriorityParams& priority) {
-    priority_ = priority;
-  }
-  const RequestPriorityParams& get_request_priority_params() const {
-    return priority_;
-  }
   const ClientId& client_id() const { return client_id_; }
   net::URLRequest* url_request() { return request_; }
   const net::URLRequest* url_request() const { return request_; }
-  uint32 fifo_ordering() const { return fifo_ordering_; }
-  void set_fifo_ordering(uint32 fifo_ordering) {
-    fifo_ordering_ = fifo_ordering;
-  }
 
  private:
   // ResourceMessageDelegate interface:
   virtual bool OnMessageReceived(const IPC::Message& message,
                                  bool* message_was_ok) OVERRIDE {
     bool handled = true;
     IPC_BEGIN_MESSAGE_MAP_EX(ScheduledResourceRequest, message, *message_was_ok)
       IPC_MESSAGE_HANDLER(ResourceHostMsg_DidChangePriority, DidChangePriority)
       IPC_MESSAGE_UNHANDLED(handled = false)
     IPC_END_MESSAGE_MAP_EX()
     return handled;
   }
 
   // ResourceThrottle interface:
   virtual void WillStartRequest(bool* defer) OVERRIDE {
     deferred_ = *defer = !ready_;
   }
 
   virtual const char* GetNameForLogging() const OVERRIDE {
     return "ResourceScheduler";
   }
 
-  void DidChangePriority(int request_id, net::RequestPriority new_priority,
-                         int intra_priority_value) {
-    scheduler_->ReprioritizeRequest(this, new_priority, intra_priority_value);
+  void DidChangePriority(int request_id, net::RequestPriority new_priority) {
+    scheduler_->ReprioritizeRequest(this, new_priority);
   }
 
   ClientId client_id_;
   net::URLRequest* request_;
   bool ready_;
   bool deferred_;
   ResourceScheduler* scheduler_;
-  RequestPriorityParams priority_;
-  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->get_request_priority_params() != b->get_request_priority_params())
-    return a->get_request_priority_params().GreaterThan(
-        b->get_request_priority_params());
-
-  // 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) {}
   ~Client() {}
 
   bool has_body;
   bool using_spdy_proxy;
   RequestQueue pending_requests;
   RequestSet in_flight_requests;
 };
 
 ResourceScheduler::ResourceScheduler() {
 }
 
 ResourceScheduler::~ResourceScheduler() {
   DCHECK(unowned_requests_.empty());
   DCHECK(client_map_.empty());
 }
 
 scoped_ptr<ResourceThrottle> ResourceScheduler::ScheduleRequest(
     int child_id,
     int route_id,
     net::URLRequest* url_request) {
   DCHECK(CalledOnValidThread());
   ClientId client_id = MakeClientId(child_id, route_id);
   scoped_ptr<ScheduledResourceRequest> request(
-      new ScheduledResourceRequest(client_id, url_request, this,
-          RequestPriorityParams(url_request->priority(), 0)));
+      new ScheduledResourceRequest(client_id, url_request, this));
 
   ClientMap::iterator it = client_map_.find(client_id);
   if (it == client_map_.end()) {
     // 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) == START_REQUEST) {
     StartRequest(request.get(), client);
   } else {
-    client->pending_requests.Insert(request.get());
+    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)) {
     unowned_requests_.erase(request);
     return;
   }
@@ skipping 96 matching lines @@
   }
 }
 
 void ResourceScheduler::StartRequest(ScheduledResourceRequest* request,
                                      Client* client) {
   client->in_flight_requests.insert(request);
   request->Start();
 }
 
 void ResourceScheduler::ReprioritizeRequest(ScheduledResourceRequest* request,
-                                            net::RequestPriority new_priority,
-                                            int new_intra_priority_value) {
+                                            net::RequestPriority new_priority) {
   if (request->url_request()->load_flags() & net::LOAD_IGNORE_LIMITS) {
     // We should not be re-prioritizing requests with the
     // IGNORE_LIMITS flag.
     NOTREACHED();
     return;
   }
-
-  RequestPriorityParams new_priority_params(new_priority,
-      new_intra_priority_value);
-  RequestPriorityParams old_priority_params =
-      request->get_request_priority_params();
-
-  DCHECK(old_priority_params != new_priority_params);
-
-  request->url_request()->SetPriority(new_priority_params.priority);
-  request->set_request_priority_params(new_priority_params);
+  net::RequestPriority old_priority = request->url_request()->priority();
+  DCHECK_NE(new_priority, old_priority);
+  request->url_request()->SetPriority(new_priority);
   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 (old_priority_params == new_priority_params)
-    return;
-
   Client *client = client_it->second;
   if (!client->pending_requests.IsQueued(request)) {
     DCHECK(ContainsKey(client->in_flight_requests, request));
     // Request has already started.
     return;
   }
 
   client->pending_requests.Erase(request);
-  client->pending_requests.Insert(request);
+  client->pending_requests.Insert(request,
+                                  request->url_request()->priority());
 
-  if (new_priority_params.priority > old_priority_params.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) {
   // 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::NetQueue::iterator request_iter =
+
+  RequestQueue::Iterator request_iter =
       client->pending_requests.GetNextHighestIterator();
-  while (request_iter != client->pending_requests.End()) {
-    ScheduledResourceRequest* request = *request_iter;
+
+  while (!request_iter.is_null()) {
+    ScheduledResourceRequest* request = request_iter.value();
     ShouldStartReqResult query_result = ShouldStartRequest(request, client);
 
     if (query_result == START_REQUEST) {
       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. Avoid copying a singular
       // iterator, which would trigger undefined behavior.
-      if (client->pending_requests.GetNextHighestIterator() ==
-          client->pending_requests.End())
+      if (client->pending_requests.GetNextHighestIterator().is_null())
         break;
       request_iter = client->pending_requests.GetNextHighestIterator();
     } else if (query_result == DO_NOT_START_REQUEST_AND_KEEP_SEARCHING) {
       ++request_iter;
       continue;
     } else {
       DCHECK(query_result == DO_NOT_START_REQUEST_AND_STOP_SEARCHING);
       break;
     }
   }
@@ skipping 107 matching lines @@
 
   return START_REQUEST;
 }
 
 ResourceScheduler::ClientId ResourceScheduler::MakeClientId(
     int child_id, int route_id) {
   return (static_cast<ResourceScheduler::ClientId>(child_id) << 32) | route_id;
 }
 
 }  // namespace content