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 <set>
      6 
      7 #include "content/browser/loader/resource_scheduler.h"
      8 
      9 #include "base/stl_util.h"
     10 #include "content/common/resource_messages.h"
     11 #include "content/browser/loader/resource_message_delegate.h"
     12 #include "content/public/browser/resource_controller.h"
     13 #include "content/public/browser/resource_request_info.h"
     14 #include "content/public/browser/resource_throttle.h"
     15 #include "ipc/ipc_message_macros.h"
     16 #include "net/base/host_port_pair.h"
     17 #include "net/base/load_flags.h"
     18 #include "net/base/request_priority.h"
     19 #include "net/http/http_server_properties.h"
     20 #include "net/url_request/url_request.h"
     21 #include "net/url_request/url_request_context.h"
     22 
     23 namespace content {
     24 
     25 static const size_t kCoalescedTimerPeriod = 5000;
     26 static const size_t kMaxNumDelayableRequestsPerClient = 10;
     27 static const size_t kMaxNumDelayableRequestsPerHost = 6;
     28 static const size_t kMaxNumThrottledRequestsPerClient = 1;
     29 
     30 struct ResourceScheduler::RequestPriorityParams {
     31   RequestPriorityParams()
     32     : priority(net::DEFAULT_PRIORITY),
     33       intra_priority(0) {
     34   }
     35 
     36   RequestPriorityParams(net::RequestPriority priority, int intra_priority)
     37     : priority(priority),
     38       intra_priority(intra_priority) {
     39   }
     40 
     41   bool operator==(const RequestPriorityParams& other) const {
     42     return (priority == other.priority) &&
     43         (intra_priority == other.intra_priority);
     44   }
     45 
     46   bool operator!=(const RequestPriorityParams& other) const {
     47     return !(*this == other);
     48   }
     49 
     50   bool GreaterThan(const RequestPriorityParams& other) const {
     51     if (priority != other.priority)
     52       return priority > other.priority;
     53     return intra_priority > other.intra_priority;
     54   }
     55 
     56   net::RequestPriority priority;
     57   int intra_priority;
     58 };
     59 
     60 class ResourceScheduler::RequestQueue {
     61  public:
     62   typedef std::multiset<ScheduledResourceRequest*, ScheduledResourceSorter>
     63       NetQueue;
     64 
     65   RequestQueue() : fifo_ordering_ids_(0) {}
     66   ~RequestQueue() {}
     67 
     68   // Adds |request| to the queue with given |priority|.
     69   void Insert(ScheduledResourceRequest* request);
     70 
     71   // Removes |request| from the queue.
     72   void Erase(ScheduledResourceRequest* request) {
     73     PointerMap::iterator it = pointers_.find(request);
     74     DCHECK(it != pointers_.end());
     75     if (it == pointers_.end())
     76       return;
     77     queue_.erase(it->second);
     78     pointers_.erase(it);
     79   }
     80 
     81   NetQueue::iterator GetNextHighestIterator() {
     82     return queue_.begin();
     83   }
     84 
     85   NetQueue::iterator End() {
     86     return queue_.end();
     87   }
     88 
     89   // Returns true if |request| is queued.
     90   bool IsQueued(ScheduledResourceRequest* request) const {
     91     return ContainsKey(pointers_, request);
     92   }
     93 
     94   // Returns true if no requests are queued.
     95   bool IsEmpty() const { return queue_.size() == 0; }
     96 
     97  private:
     98   typedef std::map<ScheduledResourceRequest*, NetQueue::iterator> PointerMap;
     99 
    100   uint32 MakeFifoOrderingId() {
    101     fifo_ordering_ids_ += 1;
    102     return fifo_ordering_ids_;
    103   }
    104 
    105   // Used to create an ordering ID for scheduled resources so that resources
    106   // with same priority/intra_priority stay in fifo order.
    107   uint32 fifo_ordering_ids_;
    108 
    109   NetQueue queue_;
    110   PointerMap pointers_;
    111 };
    112 
    113 // This is the handle we return to the ResourceDispatcherHostImpl so it can
    114 // interact with the request.
    115 class ResourceScheduler::ScheduledResourceRequest
    116     : public ResourceMessageDelegate,
    117       public ResourceThrottle {
    118  public:
    119   ScheduledResourceRequest(const ClientId& client_id,
    120                            net::URLRequest* request,
    121                            ResourceScheduler* scheduler,
    122                            const RequestPriorityParams& priority)
    123       : ResourceMessageDelegate(request),
    124         client_id_(client_id),
    125         request_(request),
    126         ready_(false),
    127         deferred_(false),
    128         classification_(NORMAL_REQUEST),
    129         scheduler_(scheduler),
    130         priority_(priority),
    131         fifo_ordering_(0) {
    132     TRACE_EVENT_ASYNC_BEGIN1("net", "URLRequest", request_,
    133                              "url", request->url().spec());
    134   }
    135 
    136   virtual ~ScheduledResourceRequest() {
    137     scheduler_->RemoveRequest(this);
    138   }
    139 
    140   void Start() {
    141     TRACE_EVENT_ASYNC_STEP_PAST0("net", "URLRequest", request_, "Queued");
    142     ready_ = true;
    143     if (deferred_ && request_->status().is_success()) {
    144       deferred_ = false;
    145       controller()->Resume();
    146     }
    147   }
    148 
    149   void set_request_priority_params(const RequestPriorityParams& priority) {
    150     priority_ = priority;
    151   }
    152   const RequestPriorityParams& get_request_priority_params() const {
    153     return priority_;
    154   }
    155   const ClientId& client_id() const { return client_id_; }
    156   net::URLRequest* url_request() { return request_; }
    157   const net::URLRequest* url_request() const { return request_; }
    158   uint32 fifo_ordering() const { return fifo_ordering_; }
    159   void set_fifo_ordering(uint32 fifo_ordering) {
    160     fifo_ordering_ = fifo_ordering;
    161   }
    162   RequestClassification classification() const {
    163     return classification_;
    164   }
    165   void set_classification(RequestClassification classification) {
    166     classification_ = classification;
    167   }
    168 
    169  private:
    170   // ResourceMessageDelegate interface:
    171   virtual bool OnMessageReceived(const IPC::Message& message) OVERRIDE {
    172     bool handled = true;
    173     IPC_BEGIN_MESSAGE_MAP(ScheduledResourceRequest, message)
    174       IPC_MESSAGE_HANDLER(ResourceHostMsg_DidChangePriority, DidChangePriority)
    175       IPC_MESSAGE_UNHANDLED(handled = false)
    176     IPC_END_MESSAGE_MAP()
    177     return handled;
    178   }
    179 
    180   // ResourceThrottle interface:
    181   virtual void WillStartRequest(bool* defer) OVERRIDE {
    182     deferred_ = *defer = !ready_;
    183   }
    184 
    185   virtual const char* GetNameForLogging() const OVERRIDE {
    186     return "ResourceScheduler";
    187   }
    188 
    189   void DidChangePriority(int request_id, net::RequestPriority new_priority,
    190                          int intra_priority_value) {
    191     scheduler_->ReprioritizeRequest(this, new_priority, intra_priority_value);
    192   }
    193 
    194   ClientId client_id_;
    195   net::URLRequest* request_;
    196   bool ready_;
    197   bool deferred_;
    198   RequestClassification classification_;
    199   ResourceScheduler* scheduler_;
    200   RequestPriorityParams priority_;
    201   uint32 fifo_ordering_;
    202 
    203   DISALLOW_COPY_AND_ASSIGN(ScheduledResourceRequest);
    204 };
    205 
    206 bool ResourceScheduler::ScheduledResourceSorter::operator()(
    207     const ScheduledResourceRequest* a,
    208     const ScheduledResourceRequest* b) const {
    209   // Want the set to be ordered first by decreasing priority, then by
    210   // decreasing intra_priority.
    211   // ie. with (priority, intra_priority)
    212   // [(1, 0), (1, 0), (0, 100), (0, 0)]
    213   if (a->get_request_priority_params() != b->get_request_priority_params())
    214     return a->get_request_priority_params().GreaterThan(
    215         b->get_request_priority_params());
    216 
    217   // If priority/intra_priority is the same, fall back to fifo ordering.
    218   // std::multiset doesn't guarantee this until c++11.
    219   return a->fifo_ordering() < b->fifo_ordering();
    220 }
    221 
    222 void ResourceScheduler::RequestQueue::Insert(
    223     ScheduledResourceRequest* request) {
    224   DCHECK(!ContainsKey(pointers_, request));
    225   request->set_fifo_ordering(MakeFifoOrderingId());
    226   pointers_[request] = queue_.insert(request);
    227 }
    228 
    229 // Each client represents a tab.
    230 class ResourceScheduler::Client {
    231  public:
    232   explicit Client(ResourceScheduler* scheduler, bool is_visible)
    233       : is_audible_(false),
    234         is_visible_(is_visible),
    235         is_loaded_(false),
    236         is_paused_(false),
    237         has_body_(false),
    238         using_spdy_proxy_(false),
    239         in_flight_delayable_count_(0),
    240         total_layout_blocking_count_(0),
    241         throttle_state_(ResourceScheduler::THROTTLED) {
    242     scheduler_ = scheduler;
    243   }
    244 
    245   ~Client() {
    246     // Update to default state and pause to ensure the scheduler has a
    247     // correct count of relevant types of clients.
    248     is_visible_ = false;
    249     is_audible_ = false;
    250     is_paused_ = true;
    251     UpdateThrottleState();
    252   }
    253 
    254   void ScheduleRequest(
    255       net::URLRequest* url_request,
    256       ScheduledResourceRequest* request) {
    257     if (ShouldStartRequest(request) == START_REQUEST)
    258       StartRequest(request);
    259     else
    260       pending_requests_.Insert(request);
    261     SetRequestClassification(request, ClassifyRequest(request));
    262   }
    263 
    264   void RemoveRequest(ScheduledResourceRequest* request) {
    265     if (pending_requests_.IsQueued(request)) {
    266       pending_requests_.Erase(request);
    267       DCHECK(!ContainsKey(in_flight_requests_, request));
    268     } else {
    269       EraseInFlightRequest(request);
    270 
    271       // Removing this request may have freed up another to load.
    272       LoadAnyStartablePendingRequests();
    273     }
    274   }
    275 
    276   RequestSet RemoveAllRequests() {
    277     RequestSet unowned_requests;
    278     for (RequestSet::iterator it = in_flight_requests_.begin();
    279          it != in_flight_requests_.end(); ++it) {
    280       unowned_requests.insert(*it);
    281       (*it)->set_classification(NORMAL_REQUEST);
    282     }
    283     ClearInFlightRequests();
    284     return unowned_requests;
    285   }
    286 
    287   bool is_active() const { return is_visible_ || is_audible_; }
    288 
    289   bool is_loaded() const { return is_loaded_; }
    290 
    291   bool is_visible() const { return is_visible_; }
    292 
    293   void OnAudibilityChanged(bool is_audible) {
    294     if (is_audible == is_audible_) {
    295       return;
    296     }
    297     is_audible_ = is_audible;
    298     UpdateThrottleState();
    299   }
    300 
    301   void OnVisibilityChanged(bool is_visible) {
    302     if (is_visible == is_visible_) {
    303       return;
    304     }
    305     is_visible_ = is_visible;
    306     UpdateThrottleState();
    307   }
    308 
    309   void OnLoadingStateChanged(bool is_loaded) {
    310     if (is_loaded == is_loaded_) {
    311       return;
    312     }
    313     is_loaded_ = is_loaded;
    314     UpdateThrottleState();
    315   }
    316 
    317   void SetPaused() {
    318     is_paused_ = true;
    319     UpdateThrottleState();
    320   }
    321 
    322   void UpdateThrottleState() {
    323     ClientThrottleState old_throttle_state = throttle_state_;
    324     if (!scheduler_->should_throttle()) {
    325       SetThrottleState(UNTHROTTLED);
    326     } else if (is_active() && !is_loaded_) {
    327       SetThrottleState(ACTIVE_AND_LOADING);
    328     } else if (is_active()) {
    329       SetThrottleState(UNTHROTTLED);
    330     } else if (is_paused_) {
    331       SetThrottleState(PAUSED);
    332     } else if (!scheduler_->active_clients_loaded()) {
    333       SetThrottleState(THROTTLED);
    334     } else if (is_loaded_ && scheduler_->should_coalesce()) {
    335       SetThrottleState(COALESCED);
    336     } else if (!is_active()) {
    337       SetThrottleState(UNTHROTTLED);
    338     }
    339 
    340     if (throttle_state_ == old_throttle_state) {
    341       return;
    342     }
    343     if (throttle_state_ == ACTIVE_AND_LOADING) {
    344       scheduler_->IncrementActiveClientsLoading();
    345     } else if (old_throttle_state == ACTIVE_AND_LOADING) {
    346       scheduler_->DecrementActiveClientsLoading();
    347     }
    348     if (throttle_state_ == COALESCED) {
    349       scheduler_->IncrementCoalescedClients();
    350     } else if (old_throttle_state == COALESCED) {
    351       scheduler_->DecrementCoalescedClients();
    352     }
    353   }
    354 
    355   void OnNavigate() {
    356     has_body_ = false;
    357     is_loaded_ = false;
    358   }
    359 
    360   void OnWillInsertBody() {
    361     has_body_ = true;
    362     LoadAnyStartablePendingRequests();
    363   }
    364 
    365   void OnReceivedSpdyProxiedHttpResponse() {
    366     if (!using_spdy_proxy_) {
    367       using_spdy_proxy_ = true;
    368       LoadAnyStartablePendingRequests();
    369     }
    370   }
    371 
    372   void ReprioritizeRequest(ScheduledResourceRequest* request,
    373                            RequestPriorityParams old_priority_params,
    374                            RequestPriorityParams new_priority_params) {
    375     request->url_request()->SetPriority(new_priority_params.priority);
    376     request->set_request_priority_params(new_priority_params);
    377     if (!pending_requests_.IsQueued(request)) {
    378       DCHECK(ContainsKey(in_flight_requests_, request));
    379       // The priority and SPDY support may have changed, so update the
    380       // delayable count.
    381       SetRequestClassification(request, ClassifyRequest(request));
    382       // Request has already started.
    383       return;
    384     }
    385 
    386     pending_requests_.Erase(request);
    387     pending_requests_.Insert(request);
    388 
    389     if (new_priority_params.priority > old_priority_params.priority) {
    390       // Check if this request is now able to load at its new priority.
    391       LoadAnyStartablePendingRequests();
    392     }
    393   }
    394 
    395   // Called on Client creation, when a Client changes user observability,
    396   // possibly when all observable Clients have finished loading, and
    397   // possibly when this Client has finished loading.
    398   // State changes:
    399   // Client became observable.
    400   //   any state -> UNTHROTTLED
    401   // Client is unobservable, but all observable clients finished loading.
    402   //   THROTTLED -> UNTHROTTLED
    403   // Non-observable client finished loading.
    404   //   THROTTLED || UNTHROTTLED -> COALESCED
    405   // Non-observable client, an observable client starts loading.
    406   //   COALESCED -> THROTTLED
    407   // A COALESCED client will transition into UNTHROTTLED when the network is
    408   // woken up by a heartbeat and then transition back into COALESCED.
    409   void SetThrottleState(ResourceScheduler::ClientThrottleState throttle_state) {
    410     if (throttle_state == throttle_state_) {
    411       return;
    412     }
    413     throttle_state_ = throttle_state;
    414     if (throttle_state_ != PAUSED) {
    415       is_paused_ = false;
    416     }
    417     LoadAnyStartablePendingRequests();
    418     // TODO(aiolos): Stop any started but not inflght requests when
    419     // switching to stricter throttle state?
    420   }
    421 
    422   ResourceScheduler::ClientThrottleState throttle_state() const {
    423     return throttle_state_;
    424   }
    425 
    426   void LoadCoalescedRequests() {
    427     if (throttle_state_ != COALESCED) {
    428       return;
    429     }
    430     if (scheduler_->active_clients_loaded()) {
    431       SetThrottleState(UNTHROTTLED);
    432     } else {
    433       SetThrottleState(THROTTLED);
    434     }
    435     LoadAnyStartablePendingRequests();
    436     SetThrottleState(COALESCED);
    437   }
    438 
    439  private:
    440   enum ShouldStartReqResult {
    441     DO_NOT_START_REQUEST_AND_STOP_SEARCHING,
    442     DO_NOT_START_REQUEST_AND_KEEP_SEARCHING,
    443     START_REQUEST,
    444   };
    445 
    446   void InsertInFlightRequest(ScheduledResourceRequest* request) {
    447     in_flight_requests_.insert(request);
    448     SetRequestClassification(request, ClassifyRequest(request));
    449   }
    450 
    451   void EraseInFlightRequest(ScheduledResourceRequest* request) {
    452     size_t erased = in_flight_requests_.erase(request);
    453     DCHECK_EQ(1u, erased);
    454     // Clear any special state that we were tracking for this request.
    455     SetRequestClassification(request, NORMAL_REQUEST);
    456   }
    457 
    458   void ClearInFlightRequests() {
    459     in_flight_requests_.clear();
    460     in_flight_delayable_count_ = 0;
    461     total_layout_blocking_count_ = 0;
    462   }
    463 
    464   size_t CountRequestsWithClassification(
    465       const RequestClassification classification, const bool include_pending) {
    466     size_t classification_request_count = 0;
    467     for (RequestSet::const_iterator it = in_flight_requests_.begin();
    468          it != in_flight_requests_.end(); ++it) {
    469       if ((*it)->classification() == classification)
    470         classification_request_count++;
    471     }
    472     if (include_pending) {
    473       for (RequestQueue::NetQueue::const_iterator
    474            it = pending_requests_.GetNextHighestIterator();
    475            it != pending_requests_.End(); ++it) {
    476         if ((*it)->classification() == classification)
    477           classification_request_count++;
    478       }
    479     }
    480     return classification_request_count;
    481   }
    482 
    483   void SetRequestClassification(ScheduledResourceRequest* request,
    484                                 RequestClassification classification) {
    485     RequestClassification old_classification = request->classification();
    486     if (old_classification == classification)
    487       return;
    488 
    489     if (old_classification == IN_FLIGHT_DELAYABLE_REQUEST)
    490       in_flight_delayable_count_--;
    491     if (old_classification == LAYOUT_BLOCKING_REQUEST)
    492       total_layout_blocking_count_--;
    493 
    494     if (classification == IN_FLIGHT_DELAYABLE_REQUEST)
    495       in_flight_delayable_count_++;
    496     if (classification == LAYOUT_BLOCKING_REQUEST)
    497       total_layout_blocking_count_++;
    498 
    499     request->set_classification(classification);
    500     DCHECK_EQ(
    501         CountRequestsWithClassification(IN_FLIGHT_DELAYABLE_REQUEST, false),
    502         in_flight_delayable_count_);
    503     DCHECK_EQ(CountRequestsWithClassification(LAYOUT_BLOCKING_REQUEST, true),
    504               total_layout_blocking_count_);
    505   }
    506 
    507   RequestClassification ClassifyRequest(ScheduledResourceRequest* request) {
    508     // If a request is already marked as layout-blocking make sure to keep the
    509     // classification across redirects unless the priority was lowered.
    510     if (request->classification() == LAYOUT_BLOCKING_REQUEST &&
    511         request->url_request()->priority() >= net::LOW) {
    512       return LAYOUT_BLOCKING_REQUEST;
    513     }
    514 
    515     if (!has_body_ && request->url_request()->priority() >= net::LOW)
    516       return LAYOUT_BLOCKING_REQUEST;
    517 
    518     if (request->url_request()->priority() < net::LOW) {
    519       net::HostPortPair host_port_pair =
    520           net::HostPortPair::FromURL(request->url_request()->url());
    521       net::HttpServerProperties& http_server_properties =
    522           *request->url_request()->context()->http_server_properties();
    523       if (!http_server_properties.SupportsSpdy(host_port_pair) &&
    524           ContainsKey(in_flight_requests_, request)) {
    525         return IN_FLIGHT_DELAYABLE_REQUEST;
    526       }
    527     }
    528     return NORMAL_REQUEST;
    529   }
    530 
    531   bool ShouldKeepSearching(
    532       const net::HostPortPair& active_request_host) const {
    533     size_t same_host_count = 0;
    534     for (RequestSet::const_iterator it = in_flight_requests_.begin();
    535          it != in_flight_requests_.end(); ++it) {
    536       net::HostPortPair host_port_pair =
    537           net::HostPortPair::FromURL((*it)->url_request()->url());
    538       if (active_request_host.Equals(host_port_pair)) {
    539         same_host_count++;
    540         if (same_host_count >= kMaxNumDelayableRequestsPerHost)
    541           return true;
    542       }
    543     }
    544     return false;
    545   }
    546 
    547   void StartRequest(ScheduledResourceRequest* request) {
    548     InsertInFlightRequest(request);
    549     request->Start();
    550   }
    551 
    552   // ShouldStartRequest is the main scheduling algorithm.
    553   //
    554   // Requests are evaluated on five attributes:
    555   //
    556   // 1. Non-delayable requests:
    557   //   * Synchronous requests.
    558   //   * Non-HTTP[S] requests.
    559   //
    560   // 2. Requests to SPDY-capable origin servers.
    561   //
    562   // 3. High-priority requests:
    563   //   * Higher priority requests (>= net::LOW).
    564   //
    565   // 4. Layout-blocking requests:
    566   //   * High-priority requests initiated before the renderer has a <body>.
    567   //
    568   // 5. Low priority requests
    569   //
    570   //  The following rules are followed:
    571   //
    572   //  ACTIVE_AND_LOADING and UNTHROTTLED Clients follow these rules:
    573   //   * Non-delayable, High-priority and SPDY capable requests are issued
    574   //     immediately.
    575   //   * Low priority requests are delayable.
    576   //   * Allow one delayable request to load at a time while layout-blocking
    577   //     requests are loading.
    578   //   * If no high priority or layout-blocking requests are in flight, start
    579   //     loading delayable requests.
    580   //   * Never exceed 10 delayable requests in flight per client.
    581   //   * Never exceed 6 delayable requests for a given host.
    582   //
    583   //  THROTTLED Clients follow these rules:
    584   //   * Non-delayable and SPDY-capable requests are issued immediately.
    585   //   * At most one non-SPDY request will be issued per THROTTLED Client
    586   //   * If no high priority requests are in flight, start loading low priority
    587   //     requests.
    588   //
    589   //  COALESCED Clients never load requests, with the following exceptions:
    590   //   * Non-delayable requests are issued imediately.
    591   //   * On a (currently 5 second) heart beat, they load all requests as an
    592   //     UNTHROTTLED Client, and then return to the COALESCED state.
    593   //   * When an active Client makes a request, they are THROTTLED until the
    594   //     active Client finishes loading.
    595   ShouldStartReqResult ShouldStartRequest(
    596       ScheduledResourceRequest* request) const {
    597     const net::URLRequest& url_request = *request->url_request();
    598     // Syncronous requests could block the entire render, which could impact
    599     // user-observable Clients.
    600     if (!ResourceRequestInfo::ForRequest(&url_request)->IsAsync()) {
    601       return START_REQUEST;
    602     }
    603 
    604     // TODO(simonjam): This may end up causing disk contention. We should
    605     // experiment with throttling if that happens.
    606     // TODO(aiolos): We probably want to Coalesce these as well to avoid
    607     // waking the disk.
    608     if (!url_request.url().SchemeIsHTTPOrHTTPS()) {
    609       return START_REQUEST;
    610     }
    611 
    612     if (throttle_state_ == COALESCED) {
    613       return DO_NOT_START_REQUEST_AND_STOP_SEARCHING;
    614     }
    615 
    616     if (using_spdy_proxy_ && url_request.url().SchemeIs(url::kHttpScheme)) {
    617       return START_REQUEST;
    618     }
    619 
    620     net::HostPortPair host_port_pair =
    621         net::HostPortPair::FromURL(url_request.url());
    622     net::HttpServerProperties& http_server_properties =
    623         *url_request.context()->http_server_properties();
    624 
    625     // TODO(willchan): We should really improve this algorithm as described in
    626     // crbug.com/164101. Also, theoretically we should not count a SPDY request
    627     // against the delayable requests limit.
    628     if (http_server_properties.SupportsSpdy(host_port_pair)) {
    629       return START_REQUEST;
    630     }
    631 
    632     if (throttle_state_ == THROTTLED &&
    633         in_flight_requests_.size() >= kMaxNumThrottledRequestsPerClient) {
    634       // There may still be SPDY-capable requests that should be issued.
    635       return DO_NOT_START_REQUEST_AND_KEEP_SEARCHING;
    636     }
    637 
    638     // High-priority and layout-blocking requests.
    639     if (url_request.priority() >= net::LOW) {
    640       return START_REQUEST;
    641     }
    642 
    643     if (in_flight_delayable_count_ >= kMaxNumDelayableRequestsPerClient) {
    644       return DO_NOT_START_REQUEST_AND_STOP_SEARCHING;
    645     }
    646 
    647     if (ShouldKeepSearching(host_port_pair)) {
    648       // There may be other requests for other hosts we'd allow,
    649       // so keep checking.
    650       return DO_NOT_START_REQUEST_AND_KEEP_SEARCHING;
    651     }
    652 
    653     bool have_immediate_requests_in_flight =
    654         in_flight_requests_.size() > in_flight_delayable_count_;
    655     if (have_immediate_requests_in_flight &&
    656         total_layout_blocking_count_ != 0 &&
    657         in_flight_delayable_count_ != 0) {
    658       return DO_NOT_START_REQUEST_AND_STOP_SEARCHING;
    659     }
    660 
    661     return START_REQUEST;
    662   }
    663 
    664   void LoadAnyStartablePendingRequests() {
    665     // We iterate through all the pending requests, starting with the highest
    666     // priority one. For each entry, one of three things can happen:
    667     // 1) We start the request, remove it from the list, and keep checking.
    668     // 2) We do NOT start the request, but ShouldStartRequest() signals us that
    669     //     there may be room for other requests, so we keep checking and leave
    670     //     the previous request still in the list.
    671     // 3) We do not start the request, same as above, but StartRequest() tells
    672     //     us there's no point in checking any further requests.
    673     RequestQueue::NetQueue::iterator request_iter =
    674         pending_requests_.GetNextHighestIterator();
    675 
    676     while (request_iter != pending_requests_.End()) {
    677       ScheduledResourceRequest* request = *request_iter;
    678       ShouldStartReqResult query_result = ShouldStartRequest(request);
    679 
    680       if (query_result == START_REQUEST) {
    681         pending_requests_.Erase(request);
    682         StartRequest(request);
    683 
    684         // StartRequest can modify the pending list, so we (re)start evaluation
    685         // from the currently highest priority request. Avoid copying a singular
    686         // iterator, which would trigger undefined behavior.
    687         if (pending_requests_.GetNextHighestIterator() ==
    688             pending_requests_.End())
    689           break;
    690         request_iter = pending_requests_.GetNextHighestIterator();
    691       } else if (query_result == DO_NOT_START_REQUEST_AND_KEEP_SEARCHING) {
    692         ++request_iter;
    693         continue;
    694       } else {
    695         DCHECK(query_result == DO_NOT_START_REQUEST_AND_STOP_SEARCHING);
    696         break;
    697       }
    698     }
    699   }
    700 
    701   bool is_audible_;
    702   bool is_visible_;
    703   bool is_loaded_;
    704   bool is_paused_;
    705   bool has_body_;
    706   bool using_spdy_proxy_;
    707   RequestQueue pending_requests_;
    708   RequestSet in_flight_requests_;
    709   ResourceScheduler* scheduler_;
    710   // The number of delayable in-flight requests.
    711   size_t in_flight_delayable_count_;
    712   // The number of layout-blocking in-flight requests.
    713   size_t total_layout_blocking_count_;
    714   ResourceScheduler::ClientThrottleState throttle_state_;
    715 };
    716 
    717 ResourceScheduler::ResourceScheduler()
    718     : should_coalesce_(false),
    719       should_throttle_(false),
    720       active_clients_loading_(0),
    721       coalesced_clients_(0),
    722       coalescing_timer_(new base::Timer(true /* retain_user_task */,
    723                                         true /* is_repeating */)) {
    724 }
    725 
    726 ResourceScheduler::~ResourceScheduler() {
    727   DCHECK(unowned_requests_.empty());
    728   DCHECK(client_map_.empty());
    729 }
    730 
    731 void ResourceScheduler::SetThrottleOptionsForTesting(bool should_throttle,
    732                                                      bool should_coalesce) {
    733   should_coalesce_ = should_coalesce;
    734   should_throttle_ = should_throttle;
    735   OnLoadingActiveClientsStateChangedForAllClients();
    736 }
    737 
    738 ResourceScheduler::ClientThrottleState
    739 ResourceScheduler::GetClientStateForTesting(int child_id, int route_id) {
    740   Client* client = GetClient(child_id, route_id);
    741   DCHECK(client);
    742   return client->throttle_state();
    743 }
    744 
    745 scoped_ptr<ResourceThrottle> ResourceScheduler::ScheduleRequest(
    746     int child_id,
    747     int route_id,
    748     net::URLRequest* url_request) {
    749   DCHECK(CalledOnValidThread());
    750   ClientId client_id = MakeClientId(child_id, route_id);
    751   scoped_ptr<ScheduledResourceRequest> request(
    752       new ScheduledResourceRequest(client_id, url_request, this,
    753           RequestPriorityParams(url_request->priority(), 0)));
    754 
    755   ClientMap::iterator it = client_map_.find(client_id);
    756   if (it == client_map_.end()) {
    757     // There are several ways this could happen:
    758     // 1. <a ping> requests don't have a route_id.
    759     // 2. Most unittests don't send the IPCs needed to register Clients.
    760     // 3. The tab is closed while a RequestResource IPC is in flight.
    761     unowned_requests_.insert(request.get());
    762     request->Start();
    763     return request.PassAs<ResourceThrottle>();
    764   }
    765 
    766   Client* client = it->second;
    767   client->ScheduleRequest(url_request, request.get());
    768   return request.PassAs<ResourceThrottle>();
    769 }
    770 
    771 void ResourceScheduler::RemoveRequest(ScheduledResourceRequest* request) {
    772   DCHECK(CalledOnValidThread());
    773   if (ContainsKey(unowned_requests_, request)) {
    774     unowned_requests_.erase(request);
    775     return;
    776   }
    777 
    778   ClientMap::iterator client_it = client_map_.find(request->client_id());
    779   if (client_it == client_map_.end()) {
    780     return;
    781   }
    782 
    783   Client* client = client_it->second;
    784   client->RemoveRequest(request);
    785 }
    786 
    787 void ResourceScheduler::OnClientCreated(int child_id,
    788                                         int route_id,
    789                                         bool is_visible) {
    790   DCHECK(CalledOnValidThread());
    791   ClientId client_id = MakeClientId(child_id, route_id);
    792   DCHECK(!ContainsKey(client_map_, client_id));
    793 
    794   Client* client = new Client(this, is_visible);
    795   client_map_[client_id] = client;
    796 
    797   // TODO(aiolos): set Client visibility/audibility when signals are added
    798   // this will UNTHROTTLE Clients as needed
    799   client->UpdateThrottleState();
    800 }
    801 
    802 void ResourceScheduler::OnClientDeleted(int child_id, int route_id) {
    803   DCHECK(CalledOnValidThread());
    804   ClientId client_id = MakeClientId(child_id, route_id);
    805   DCHECK(ContainsKey(client_map_, client_id));
    806   ClientMap::iterator it = client_map_.find(client_id);
    807   if (it == client_map_.end())
    808     return;
    809 
    810   Client* client = it->second;
    811   // FYI, ResourceDispatcherHost cancels all of the requests after this function
    812   // is called. It should end up canceling all of the requests except for a
    813   // cross-renderer navigation.
    814   RequestSet client_unowned_requests = client->RemoveAllRequests();
    815   for (RequestSet::iterator it = client_unowned_requests.begin();
    816        it != client_unowned_requests.end(); ++it) {
    817     unowned_requests_.insert(*it);
    818   }
    819 
    820   delete client;
    821   client_map_.erase(it);
    822 }
    823 
    824 void ResourceScheduler::OnVisibilityChanged(int child_id,
    825                                             int route_id,
    826                                             bool is_visible) {
    827   Client* client = GetClient(child_id, route_id);
    828   DCHECK(client);
    829   client->OnVisibilityChanged(is_visible);
    830 }
    831 
    832 void ResourceScheduler::OnLoadingStateChanged(int child_id,
    833                                               int route_id,
    834                                               bool is_loaded) {
    835   Client* client = GetClient(child_id, route_id);
    836   DCHECK(client);
    837   client->OnLoadingStateChanged(is_loaded);
    838 }
    839 
    840 void ResourceScheduler::OnNavigate(int child_id, int route_id) {
    841   DCHECK(CalledOnValidThread());
    842   ClientId client_id = MakeClientId(child_id, route_id);
    843 
    844   ClientMap::iterator it = client_map_.find(client_id);
    845   if (it == client_map_.end()) {
    846     // The client was likely deleted shortly before we received this IPC.
    847     return;
    848   }
    849 
    850   Client* client = it->second;
    851   client->OnNavigate();
    852 }
    853 
    854 void ResourceScheduler::OnWillInsertBody(int child_id, int route_id) {
    855   DCHECK(CalledOnValidThread());
    856   ClientId client_id = MakeClientId(child_id, route_id);
    857 
    858   ClientMap::iterator it = client_map_.find(client_id);
    859   if (it == client_map_.end()) {
    860     // The client was likely deleted shortly before we received this IPC.
    861     return;
    862   }
    863 
    864   Client* client = it->second;
    865   client->OnWillInsertBody();
    866 }
    867 
    868 void ResourceScheduler::OnReceivedSpdyProxiedHttpResponse(
    869     int child_id,
    870     int route_id) {
    871   DCHECK(CalledOnValidThread());
    872   ClientId client_id = MakeClientId(child_id, route_id);
    873 
    874   ClientMap::iterator client_it = client_map_.find(client_id);
    875   if (client_it == client_map_.end()) {
    876     return;
    877   }
    878 
    879   Client* client = client_it->second;
    880   client->OnReceivedSpdyProxiedHttpResponse();
    881 }
    882 
    883 void ResourceScheduler::OnAudibilityChanged(int child_id,
    884                                             int route_id,
    885                                             bool is_audible) {
    886   Client* client = GetClient(child_id, route_id);
    887   DCHECK(client);
    888   client->OnAudibilityChanged(is_audible);
    889 }
    890 
    891 bool ResourceScheduler::IsClientVisibleForTesting(int child_id, int route_id) {
    892   Client* client = GetClient(child_id, route_id);
    893   DCHECK(client);
    894   return client->is_visible();
    895 }
    896 
    897 ResourceScheduler::Client* ResourceScheduler::GetClient(int child_id,
    898                                                         int route_id) {
    899   ClientId client_id = MakeClientId(child_id, route_id);
    900   ClientMap::iterator client_it = client_map_.find(client_id);
    901   if (client_it == client_map_.end()) {
    902     return NULL;
    903   }
    904   return client_it->second;
    905 }
    906 
    907 void ResourceScheduler::DecrementActiveClientsLoading() {
    908   DCHECK_NE(0u, active_clients_loading_);
    909   --active_clients_loading_;
    910   DCHECK_EQ(active_clients_loading_, CountActiveClientsLoading());
    911   if (active_clients_loading_ == 0) {
    912     OnLoadingActiveClientsStateChangedForAllClients();
    913   }
    914 }
    915 
    916 void ResourceScheduler::IncrementActiveClientsLoading() {
    917   ++active_clients_loading_;
    918   DCHECK_EQ(active_clients_loading_, CountActiveClientsLoading());
    919   if (active_clients_loading_ == 1) {
    920     OnLoadingActiveClientsStateChangedForAllClients();
    921   }
    922 }
    923 
    924 void ResourceScheduler::OnLoadingActiveClientsStateChangedForAllClients() {
    925   ClientMap::iterator client_it = client_map_.begin();
    926   while (client_it != client_map_.end()) {
    927     Client* client = client_it->second;
    928     client->UpdateThrottleState();
    929     ++client_it;
    930   }
    931 }
    932 
    933 size_t ResourceScheduler::CountActiveClientsLoading() const {
    934   size_t active_and_loading = 0;
    935   ClientMap::const_iterator client_it = client_map_.begin();
    936   while (client_it != client_map_.end()) {
    937     Client* client = client_it->second;
    938     if (client->throttle_state() == ACTIVE_AND_LOADING) {
    939       ++active_and_loading;
    940     }
    941     ++client_it;
    942   }
    943   return active_and_loading;
    944 }
    945 
    946 void ResourceScheduler::IncrementCoalescedClients() {
    947   ++coalesced_clients_;
    948   DCHECK(should_coalesce_);
    949   DCHECK_EQ(coalesced_clients_, CountCoalescedClients());
    950   if (coalesced_clients_ == 1) {
    951     coalescing_timer_->Start(
    952         FROM_HERE,
    953         base::TimeDelta::FromMilliseconds(kCoalescedTimerPeriod),
    954         base::Bind(&ResourceScheduler::LoadCoalescedRequests,
    955                    base::Unretained(this)));
    956   }
    957 }
    958 
    959 void ResourceScheduler::DecrementCoalescedClients() {
    960   DCHECK(should_coalesce_);
    961   DCHECK_NE(0U, coalesced_clients_);
    962   --coalesced_clients_;
    963   DCHECK_EQ(coalesced_clients_, CountCoalescedClients());
    964   if (coalesced_clients_ == 0) {
    965     coalescing_timer_->Stop();
    966   }
    967 }
    968 
    969 size_t ResourceScheduler::CountCoalescedClients() const {
    970   DCHECK(should_coalesce_);
    971   size_t coalesced_clients = 0;
    972   ClientMap::const_iterator client_it = client_map_.begin();
    973   while (client_it != client_map_.end()) {
    974     Client* client = client_it->second;
    975     if (client->throttle_state() == COALESCED) {
    976       ++coalesced_clients;
    977     }
    978     ++client_it;
    979   }
    980   return coalesced_clients_;
    981 }
    982 
    983 void ResourceScheduler::LoadCoalescedRequests() {
    984   DCHECK(should_coalesce_);
    985   ClientMap::iterator client_it = client_map_.begin();
    986   while (client_it != client_map_.end()) {
    987     Client* client = client_it->second;
    988     client->LoadCoalescedRequests();
    989     ++client_it;
    990   }
    991 }
    992 
    993 void ResourceScheduler::ReprioritizeRequest(ScheduledResourceRequest* request,
    994                                             net::RequestPriority new_priority,
    995                                             int new_intra_priority_value) {
    996   if (request->url_request()->load_flags() & net::LOAD_IGNORE_LIMITS) {
    997     // We should not be re-prioritizing requests with the
    998     // IGNORE_LIMITS flag.
    999     NOTREACHED();
   1000     return;
   1001   }
   1002   RequestPriorityParams new_priority_params(new_priority,
   1003       new_intra_priority_value);
   1004   RequestPriorityParams old_priority_params =
   1005       request->get_request_priority_params();
   1006 
   1007   DCHECK(old_priority_params != new_priority_params);
   1008 
   1009   ClientMap::iterator client_it = client_map_.find(request->client_id());
   1010   if (client_it == client_map_.end()) {
   1011     // The client was likely deleted shortly before we received this IPC.
   1012     request->url_request()->SetPriority(new_priority_params.priority);
   1013     request->set_request_priority_params(new_priority_params);
   1014     return;
   1015   }
   1016 
   1017   if (old_priority_params == new_priority_params)
   1018     return;
   1019 
   1020   Client *client = client_it->second;
   1021   client->ReprioritizeRequest(
   1022       request, old_priority_params, new_priority_params);
   1023 }
   1024 
   1025 ResourceScheduler::ClientId ResourceScheduler::MakeClientId(
   1026     int child_id, int route_id) {
   1027   return (static_cast<ResourceScheduler::ClientId>(child_id) << 32) | route_id;
   1028 }
   1029 
   1030 }  // namespace content
   1031