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