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