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