Home | History | Annotate | Download | only in loader 
      1 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style license that can be
      3 // found in the LICENSE file.
      4 
      5 #include "content/browser/loader/resource_scheduler.h"
      6 
      7 #include "base/stl_util.h"
      8 #include "content/common/resource_messages.h"
      9 #include "content/browser/loader/resource_message_delegate.h"
     10 #include "content/public/browser/resource_controller.h"
     11 #include "content/public/browser/resource_request_info.h"
     12 #include "content/public/browser/resource_throttle.h"
     13 #include "ipc/ipc_message_macros.h"
     14 #include "net/base/host_port_pair.h"
     15 #include "net/base/load_flags.h"
     16 #include "net/base/request_priority.h"
     17 #include "net/http/http_server_properties.h"
     18 #include "net/url_request/url_request.h"
     19 #include "net/url_request/url_request_context.h"
     20 
     21 namespace content {
     22 
     23 static const size_t kMaxNumDelayableRequestsPerClient = 10;
     24 
     25 // A thin wrapper around net::PriorityQueue that deals with
     26 // ScheduledResourceRequests instead of PriorityQueue::Pointers.
     27 class ResourceScheduler::RequestQueue {
     28  public:
     29   RequestQueue() : queue_(net::NUM_PRIORITIES) {}
     30   ~RequestQueue() {}
     31 
     32   // Adds |request| to the queue with given |priority|.
     33   void Insert(ScheduledResourceRequest* request,
     34               net::RequestPriority priority) {
     35     DCHECK(!ContainsKey(pointers_, request));
     36     NetQueue::Pointer pointer = queue_.Insert(request, priority);
     37     pointers_[request] = pointer;
     38   }
     39 
     40   // Removes |request| from the queue.
     41   void Erase(ScheduledResourceRequest* request) {
     42     PointerMap::iterator it = pointers_.find(request);
     43     DCHECK(it != pointers_.end());
     44     queue_.Erase(it->second);
     45     pointers_.erase(it);
     46   }
     47 
     48   // Returns the highest priority request that's queued, or NULL if none are.
     49   ScheduledResourceRequest* FirstMax() {
     50     return queue_.FirstMax().value();
     51   }
     52 
     53   // Returns true if |request| is queued.
     54   bool IsQueued(ScheduledResourceRequest* request) const {
     55     return ContainsKey(pointers_, request);
     56   }
     57 
     58   // Returns true if no requests are queued.
     59   bool IsEmpty() const { return queue_.size() == 0; }
     60 
     61  private:
     62   typedef net::PriorityQueue<ScheduledResourceRequest*> NetQueue;
     63   typedef std::map<ScheduledResourceRequest*, NetQueue::Pointer> PointerMap;
     64 
     65   NetQueue queue_;
     66   PointerMap pointers_;
     67 };
     68 
     69 // This is the handle we return to the ResourceDispatcherHostImpl so it can
     70 // interact with the request.
     71 class ResourceScheduler::ScheduledResourceRequest
     72     : public ResourceMessageDelegate,
     73       public ResourceThrottle {
     74  public:
     75   ScheduledResourceRequest(const ClientId& client_id,
     76                            net::URLRequest* request,
     77                            ResourceScheduler* scheduler)
     78       : ResourceMessageDelegate(request),
     79         client_id_(client_id),
     80         request_(request),
     81         ready_(false),
     82         deferred_(false),
     83         scheduler_(scheduler) {
     84   }
     85 
     86   virtual ~ScheduledResourceRequest() {
     87     scheduler_->RemoveRequest(this);
     88   }
     89 
     90   void Start() {
     91     ready_ = true;
     92     if (deferred_ && request_->status().is_success()) {
     93       deferred_ = false;
     94       controller()->Resume();
     95     }
     96   }
     97 
     98   const ClientId& client_id() const { return client_id_; }
     99   net::URLRequest* url_request() { return request_; }
    100   const net::URLRequest* url_request() const { return request_; }
    101 
    102  private:
    103   // ResourceMessageDelegate interface:
    104   virtual bool OnMessageReceived(const IPC::Message& message,
    105                                  bool* message_was_ok) OVERRIDE {
    106     bool handled = true;
    107     IPC_BEGIN_MESSAGE_MAP_EX(ScheduledResourceRequest, message, *message_was_ok)
    108       IPC_MESSAGE_HANDLER(ResourceHostMsg_DidChangePriority, DidChangePriority)
    109       IPC_MESSAGE_UNHANDLED(handled = false)
    110     IPC_END_MESSAGE_MAP_EX()
    111     return handled;
    112   }
    113 
    114   // ResourceThrottle interface:
    115   virtual void WillStartRequest(bool* defer) OVERRIDE {
    116     deferred_ = *defer = !ready_;
    117   }
    118 
    119   void DidChangePriority(int request_id, net::RequestPriority new_priority) {
    120     scheduler_->ReprioritizeRequest(this, new_priority);
    121   }
    122 
    123   ClientId client_id_;
    124   net::URLRequest* request_;
    125   bool ready_;
    126   bool deferred_;
    127   ResourceScheduler* scheduler_;
    128 
    129   DISALLOW_COPY_AND_ASSIGN(ScheduledResourceRequest);
    130 };
    131 
    132 // Each client represents a tab.
    133 struct ResourceScheduler::Client {
    134   Client() : has_body(false) {}
    135   ~Client() {}
    136 
    137   bool has_body;
    138   RequestQueue pending_requests;
    139   RequestSet in_flight_requests;
    140 };
    141 
    142 ResourceScheduler::ResourceScheduler() {
    143 }
    144 
    145 ResourceScheduler::~ResourceScheduler() {
    146   DCHECK(unowned_requests_.empty());
    147   DCHECK(client_map_.empty());
    148 }
    149 
    150 scoped_ptr<ResourceThrottle> ResourceScheduler::ScheduleRequest(
    151     int child_id,
    152     int route_id,
    153     net::URLRequest* url_request) {
    154   DCHECK(CalledOnValidThread());
    155   ClientId client_id = MakeClientId(child_id, route_id);
    156   scoped_ptr<ScheduledResourceRequest> request(
    157       new ScheduledResourceRequest(client_id, url_request, this));
    158 
    159   ClientMap::iterator it = client_map_.find(client_id);
    160   if (it == client_map_.end()) {
    161     // There are several ways this could happen:
    162     // 1. <a ping> requests don't have a route_id.
    163     // 2. Most unittests don't send the IPCs needed to register Clients.
    164     // 3. The tab is closed while a RequestResource IPC is in flight.
    165     unowned_requests_.insert(request.get());
    166     request->Start();
    167     return request.PassAs<ResourceThrottle>();
    168   }
    169 
    170   Client* client = it->second;
    171   if (ShouldStartRequest(request.get(), client)) {
    172     StartRequest(request.get(), client);
    173   } else {
    174     client->pending_requests.Insert(request.get(), url_request->priority());
    175   }
    176   return request.PassAs<ResourceThrottle>();
    177 }
    178 
    179 void ResourceScheduler::RemoveRequest(ScheduledResourceRequest* request) {
    180   DCHECK(CalledOnValidThread());
    181   if (ContainsKey(unowned_requests_, request)) {
    182     unowned_requests_.erase(request);
    183     return;
    184   }
    185 
    186   ClientMap::iterator client_it = client_map_.find(request->client_id());
    187   if (client_it == client_map_.end()) {
    188     return;
    189   }
    190 
    191   Client* client = client_it->second;
    192 
    193   if (client->pending_requests.IsQueued(request)) {
    194     client->pending_requests.Erase(request);
    195     DCHECK(!ContainsKey(client->in_flight_requests, request));
    196   } else {
    197     size_t erased = client->in_flight_requests.erase(request);
    198     DCHECK(erased);
    199 
    200     // Removing this request may have freed up another to load.
    201     LoadAnyStartablePendingRequests(client);
    202   }
    203 }
    204 
    205 void ResourceScheduler::OnClientCreated(int child_id, int route_id) {
    206   DCHECK(CalledOnValidThread());
    207   ClientId client_id = MakeClientId(child_id, route_id);
    208   DCHECK(!ContainsKey(client_map_, client_id));
    209 
    210   client_map_[client_id] = new Client;
    211 }
    212 
    213 void ResourceScheduler::OnClientDeleted(int child_id, int route_id) {
    214   DCHECK(CalledOnValidThread());
    215   ClientId client_id = MakeClientId(child_id, route_id);
    216   DCHECK(ContainsKey(client_map_, client_id));
    217   ClientMap::iterator it = client_map_.find(client_id);
    218   Client* client = it->second;
    219 
    220   // FYI, ResourceDispatcherHost cancels all of the requests after this function
    221   // is called. It should end up canceling all of the requests except for a
    222   // cross-renderer navigation.
    223   for (RequestSet::iterator it = client->in_flight_requests.begin();
    224        it != client->in_flight_requests.end(); ++it) {
    225     unowned_requests_.insert(*it);
    226   }
    227   client->in_flight_requests.clear();
    228 
    229   delete client;
    230   client_map_.erase(it);
    231 }
    232 
    233 void ResourceScheduler::OnNavigate(int child_id, int route_id) {
    234   DCHECK(CalledOnValidThread());
    235   ClientId client_id = MakeClientId(child_id, route_id);
    236 
    237   ClientMap::iterator it = client_map_.find(client_id);
    238   if (it == client_map_.end()) {
    239     // The client was likely deleted shortly before we received this IPC.
    240     return;
    241   }
    242 
    243   Client* client = it->second;
    244   client->has_body = false;
    245 }
    246 
    247 void ResourceScheduler::OnWillInsertBody(int child_id, int route_id) {
    248   DCHECK(CalledOnValidThread());
    249   ClientId client_id = MakeClientId(child_id, route_id);
    250 
    251   ClientMap::iterator it = client_map_.find(client_id);
    252   if (it == client_map_.end()) {
    253     // The client was likely deleted shortly before we received this IPC.
    254     return;
    255   }
    256 
    257   Client* client = it->second;
    258   client->has_body = false;
    259   if (!client->has_body) {
    260     client->has_body = true;
    261     LoadAnyStartablePendingRequests(client);
    262   }
    263 }
    264 
    265 void ResourceScheduler::StartRequest(ScheduledResourceRequest* request,
    266                                      Client* client) {
    267   client->in_flight_requests.insert(request);
    268   request->Start();
    269 }
    270 
    271 void ResourceScheduler::ReprioritizeRequest(ScheduledResourceRequest* request,
    272                                             net::RequestPriority new_priority) {
    273   net::RequestPriority old_priority = request->url_request()->priority();
    274   DCHECK_NE(new_priority, old_priority);
    275   request->url_request()->SetPriority(new_priority);
    276   ClientMap::iterator client_it = client_map_.find(request->client_id());
    277   if (client_it == client_map_.end()) {
    278     // The client was likely deleted shortly before we received this IPC.
    279     return;
    280   }
    281 
    282   Client *client = client_it->second;
    283   if (!client->pending_requests.IsQueued(request)) {
    284     DCHECK(ContainsKey(client->in_flight_requests, request));
    285     // Request has already started.
    286     return;
    287   }
    288 
    289   client->pending_requests.Erase(request);
    290   client->pending_requests.Insert(request, request->url_request()->priority());
    291 
    292   if (new_priority > old_priority) {
    293     // Check if this request is now able to load at its new priority.
    294     LoadAnyStartablePendingRequests(client);
    295   }
    296 }
    297 
    298 void ResourceScheduler::LoadAnyStartablePendingRequests(Client* client) {
    299   while (!client->pending_requests.IsEmpty()) {
    300     ScheduledResourceRequest* request = client->pending_requests.FirstMax();
    301     if (ShouldStartRequest(request, client)) {
    302       client->pending_requests.Erase(request);
    303       StartRequest(request, client);
    304     } else {
    305       break;
    306     }
    307   }
    308 }
    309 
    310 size_t ResourceScheduler::GetNumDelayableRequestsInFlight(
    311     Client* client) const {
    312   size_t count = 0;
    313   for (RequestSet::iterator it = client->in_flight_requests.begin();
    314        it != client->in_flight_requests.end(); ++it) {
    315     if ((*it)->url_request()->priority() < net::LOW) {
    316       const net::HttpServerProperties& http_server_properties =
    317           *(*it)->url_request()->context()->http_server_properties();
    318       if (!http_server_properties.SupportsSpdy(
    319           net::HostPortPair::FromURL((*it)->url_request()->url()))) {
    320         ++count;
    321       }
    322     }
    323   }
    324   return count;
    325 }
    326 
    327 // ShouldStartRequest is the main scheduling algorithm.
    328 //
    329 // Requests are categorized into two categories:
    330 //
    331 // 1. Immediately issued requests, which are:
    332 //
    333 //   * Higher priority requests (>= net::LOW).
    334 //   * Synchronous requests.
    335 //   * Requests to SPDY-capable origin servers.
    336 //
    337 // 2. The remainder are delayable requests, which follow these rules:
    338 //
    339 //   * If no high priority requests are in flight, start loading low priority
    340 //     requests.
    341 //   * Once the renderer has a <body>, start loading delayable requests.
    342 //   * Never exceed 10 delayable requests in flight per client.
    343 //   * Prior to <body>, allow one delayable request to load at a time.
    344 bool ResourceScheduler::ShouldStartRequest(ScheduledResourceRequest* request,
    345                                            Client* client) const {
    346   const net::URLRequest& url_request = *request->url_request();
    347   const net::HttpServerProperties& http_server_properties =
    348       *url_request.context()->http_server_properties();
    349 
    350   // TODO(willchan): We should really improve this algorithm as described in
    351   // crbug.com/164101. Also, theoretically we should not count a SPDY request
    352   // against the delayable requests limit.
    353   bool origin_supports_spdy = http_server_properties.SupportsSpdy(
    354       net::HostPortPair::FromURL(url_request.url()));
    355 
    356   if (url_request.priority() >= net::LOW ||
    357       !ResourceRequestInfo::ForRequest(&url_request)->IsAsync() ||
    358       origin_supports_spdy) {
    359     return true;
    360   }
    361 
    362   size_t num_delayable_requests_in_flight =
    363       GetNumDelayableRequestsInFlight(client);
    364   if (num_delayable_requests_in_flight >= kMaxNumDelayableRequestsPerClient) {
    365     return false;
    366   }
    367 
    368   bool have_immediate_requests_in_flight =
    369       client->in_flight_requests.size() > num_delayable_requests_in_flight;
    370   if (have_immediate_requests_in_flight && !client->has_body &&
    371       num_delayable_requests_in_flight != 0) {
    372     return false;
    373   }
    374 
    375   return true;
    376 }
    377 
    378 ResourceScheduler::ClientId ResourceScheduler::MakeClientId(
    379     int child_id, int route_id) {
    380   return (static_cast<ResourceScheduler::ClientId>(child_id) << 32) | route_id;
    381 }
    382 
    383 }  // namespace content
    384