content/browser/loader/resource_scheduler.cc

   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 IsVisible() 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("http")) {
 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::OnNavigate(int child_id, int route_id) {
 825   DCHECK(CalledOnValidThread());
 826   ClientId client_id = MakeClientId(child_id, route_id);
 827
 828   ClientMap::iterator it = client_map_.find(client_id);
 829   if (it == client_map_.end()) {
 830     // The client was likely deleted shortly before we received this IPC.
 831     return;
 832   }
 833
 834   Client* client = it->second;
 835   client->OnNavigate();
 836 }
 837
 838 void ResourceScheduler::OnWillInsertBody(int child_id, int route_id) {
 839   DCHECK(CalledOnValidThread());
 840   ClientId client_id = MakeClientId(child_id, route_id);
 841
 842   ClientMap::iterator it = client_map_.find(client_id);
 843   if (it == client_map_.end()) {
 844     // The client was likely deleted shortly before we received this IPC.
 845     return;
 846   }
 847
 848   Client* client = it->second;
 849   client->OnWillInsertBody();
 850 }
 851
 852 void ResourceScheduler::OnReceivedSpdyProxiedHttpResponse(
 853     int child_id,
 854     int route_id) {
 855   DCHECK(CalledOnValidThread());
 856   ClientId client_id = MakeClientId(child_id, route_id);
 857
 858   ClientMap::iterator client_it = client_map_.find(client_id);
 859   if (client_it == client_map_.end()) {
 860     return;
 861   }
 862
 863   Client* client = client_it->second;
 864   client->OnReceivedSpdyProxiedHttpResponse();
 865 }
 866
 867 void ResourceScheduler::OnAudibilityChanged(int child_id,
 868                                             int route_id,
 869                                             bool is_audible) {
 870   Client* client = GetClient(child_id, route_id);
 871   DCHECK(client);
 872   client->OnAudibilityChanged(is_audible);
 873 }
 874
 875 void ResourceScheduler::OnVisibilityChanged(int child_id,
 876                                             int route_id,
 877                                             bool is_visible) {
 878   Client* client = GetClient(child_id, route_id);
 879   DCHECK(client);
 880   client->OnVisibilityChanged(is_visible);
 881 }
 882
 883 void ResourceScheduler::OnLoadingStateChanged(int child_id,
 884                                               int route_id,
 885                                               bool is_loaded) {
 886   Client* client = GetClient(child_id, route_id);
 887   DCHECK(client);
 888   client->OnLoadingStateChanged(is_loaded);
 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->IsVisible();
 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