1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #include <set> 6 7 #include "content/browser/loader/resource_scheduler.h" 8 9 #include "base/stl_util.h" 10 #include "content/common/resource_messages.h" 11 #include "content/browser/loader/resource_message_delegate.h" 12 #include "content/public/browser/resource_controller.h" 13 #include "content/public/browser/resource_request_info.h" 14 #include "content/public/browser/resource_throttle.h" 15 #include "ipc/ipc_message_macros.h" 16 #include "net/base/host_port_pair.h" 17 #include "net/base/load_flags.h" 18 #include "net/base/request_priority.h" 19 #include "net/http/http_server_properties.h" 20 #include "net/url_request/url_request.h" 21 #include "net/url_request/url_request_context.h" 22 23 namespace content { 24 25 static const size_t kMaxNumDelayableRequestsPerClient = 10; 26 static const size_t kMaxNumDelayableRequestsPerHost = 6; 27 28 29 struct ResourceScheduler::RequestPriorityParams { 30 RequestPriorityParams() 31 : priority(net::DEFAULT_PRIORITY), 32 intra_priority(0) { 33 } 34 35 RequestPriorityParams(net::RequestPriority priority, int intra_priority) 36 : priority(priority), 37 intra_priority(intra_priority) { 38 } 39 40 bool operator==(const RequestPriorityParams& other) const { 41 return (priority == other.priority) && 42 (intra_priority == other.intra_priority); 43 } 44 45 bool operator!=(const RequestPriorityParams& other) const { 46 return !(*this == other); 47 } 48 49 bool GreaterThan(const RequestPriorityParams& other) const { 50 if (priority != other.priority) 51 return priority > other.priority; 52 return intra_priority > other.intra_priority; 53 } 54 55 net::RequestPriority priority; 56 int intra_priority; 57 }; 58 59 class ResourceScheduler::RequestQueue { 60 public: 61 typedef std::multiset<ScheduledResourceRequest*, ScheduledResourceSorter> 62 NetQueue; 63 64 RequestQueue() : fifo_ordering_ids_(0) {} 65 ~RequestQueue() {} 66 67 // Adds |request| to the queue with given |priority|. 68 void Insert(ScheduledResourceRequest* request); 69 70 // Removes |request| from the queue. 71 void Erase(ScheduledResourceRequest* request) { 72 PointerMap::iterator it = pointers_.find(request); 73 DCHECK(it != pointers_.end()); 74 if (it == pointers_.end()) 75 return; 76 queue_.erase(it->second); 77 pointers_.erase(it); 78 } 79 80 NetQueue::iterator GetNextHighestIterator() { 81 return queue_.begin(); 82 } 83 84 NetQueue::iterator End() { 85 return queue_.end(); 86 } 87 88 // Returns true if |request| is queued. 89 bool IsQueued(ScheduledResourceRequest* request) const { 90 return ContainsKey(pointers_, request); 91 } 92 93 // Returns true if no requests are queued. 94 bool IsEmpty() const { return queue_.size() == 0; } 95 96 private: 97 typedef std::map<ScheduledResourceRequest*, NetQueue::iterator> PointerMap; 98 99 uint32 MakeFifoOrderingId() { 100 fifo_ordering_ids_ += 1; 101 return fifo_ordering_ids_; 102 } 103 104 // Used to create an ordering ID for scheduled resources so that resources 105 // with same priority/intra_priority stay in fifo order. 106 uint32 fifo_ordering_ids_; 107 108 NetQueue queue_; 109 PointerMap pointers_; 110 }; 111 112 // This is the handle we return to the ResourceDispatcherHostImpl so it can 113 // interact with the request. 114 class ResourceScheduler::ScheduledResourceRequest 115 : public ResourceMessageDelegate, 116 public ResourceThrottle { 117 public: 118 ScheduledResourceRequest(const ClientId& client_id, 119 net::URLRequest* request, 120 ResourceScheduler* scheduler, 121 const RequestPriorityParams& priority) 122 : ResourceMessageDelegate(request), 123 client_id_(client_id), 124 request_(request), 125 ready_(false), 126 deferred_(false), 127 scheduler_(scheduler), 128 priority_(priority), 129 fifo_ordering_(0), 130 accounted_as_delayable_request_(false) { 131 TRACE_EVENT_ASYNC_BEGIN1("net", "URLRequest", request_, 132 "url", request->url().spec()); 133 } 134 135 virtual ~ScheduledResourceRequest() { 136 scheduler_->RemoveRequest(this); 137 } 138 139 void Start() { 140 TRACE_EVENT_ASYNC_STEP_PAST0("net", "URLRequest", request_, "Queued"); 141 ready_ = true; 142 if (deferred_ && request_->status().is_success()) { 143 deferred_ = false; 144 controller()->Resume(); 145 } 146 } 147 148 void set_request_priority_params(const RequestPriorityParams& priority) { 149 priority_ = priority; 150 } 151 const RequestPriorityParams& get_request_priority_params() const { 152 return priority_; 153 } 154 const ClientId& client_id() const { return client_id_; } 155 net::URLRequest* url_request() { return request_; } 156 const net::URLRequest* url_request() const { return request_; } 157 uint32 fifo_ordering() const { return fifo_ordering_; } 158 void set_fifo_ordering(uint32 fifo_ordering) { 159 fifo_ordering_ = fifo_ordering; 160 } 161 bool accounted_as_delayable_request() const { 162 return accounted_as_delayable_request_; 163 } 164 void set_accounted_as_delayable_request(bool accounted) { 165 accounted_as_delayable_request_ = accounted; 166 } 167 168 private: 169 // ResourceMessageDelegate interface: 170 virtual bool OnMessageReceived(const IPC::Message& message) OVERRIDE { 171 bool handled = true; 172 IPC_BEGIN_MESSAGE_MAP(ScheduledResourceRequest, message) 173 IPC_MESSAGE_HANDLER(ResourceHostMsg_DidChangePriority, DidChangePriority) 174 IPC_MESSAGE_UNHANDLED(handled = false) 175 IPC_END_MESSAGE_MAP() 176 return handled; 177 } 178 179 // ResourceThrottle interface: 180 virtual void WillStartRequest(bool* defer) OVERRIDE { 181 deferred_ = *defer = !ready_; 182 } 183 184 virtual const char* GetNameForLogging() const OVERRIDE { 185 return "ResourceScheduler"; 186 } 187 188 void DidChangePriority(int request_id, net::RequestPriority new_priority, 189 int intra_priority_value) { 190 scheduler_->ReprioritizeRequest(this, new_priority, intra_priority_value); 191 } 192 193 ClientId client_id_; 194 net::URLRequest* request_; 195 bool ready_; 196 bool deferred_; 197 ResourceScheduler* scheduler_; 198 RequestPriorityParams priority_; 199 uint32 fifo_ordering_; 200 // True if the request is delayable in |in_flight_requests_|. 201 bool accounted_as_delayable_request_; 202 203 DISALLOW_COPY_AND_ASSIGN(ScheduledResourceRequest); 204 }; 205 206 bool ResourceScheduler::ScheduledResourceSorter::operator()( 207 const ScheduledResourceRequest* a, 208 const ScheduledResourceRequest* b) const { 209 // Want the set to be ordered first by decreasing priority, then by 210 // decreasing intra_priority. 211 // ie. with (priority, intra_priority) 212 // [(1, 0), (1, 0), (0, 100), (0, 0)] 213 if (a->get_request_priority_params() != b->get_request_priority_params()) 214 return a->get_request_priority_params().GreaterThan( 215 b->get_request_priority_params()); 216 217 // If priority/intra_priority is the same, fall back to fifo ordering. 218 // std::multiset doesn't guarantee this until c++11. 219 return a->fifo_ordering() < b->fifo_ordering(); 220 } 221 222 void ResourceScheduler::RequestQueue::Insert( 223 ScheduledResourceRequest* request) { 224 DCHECK(!ContainsKey(pointers_, request)); 225 request->set_fifo_ordering(MakeFifoOrderingId()); 226 pointers_[request] = queue_.insert(request); 227 } 228 229 // Each client represents a tab. 230 class ResourceScheduler::Client { 231 public: 232 Client() 233 : has_body_(false), 234 using_spdy_proxy_(false), 235 total_delayable_count_(0) {} 236 ~Client() {} 237 238 void ScheduleRequest( 239 net::URLRequest* url_request, 240 ScheduledResourceRequest* request) { 241 if (ShouldStartRequest(request) == START_REQUEST) { 242 StartRequest(request); 243 } else { 244 pending_requests_.Insert(request); 245 } 246 } 247 248 void RemoveRequest(ScheduledResourceRequest* request) { 249 if (pending_requests_.IsQueued(request)) { 250 pending_requests_.Erase(request); 251 DCHECK(!ContainsKey(in_flight_requests_, request)); 252 } else { 253 EraseInFlightRequest(request); 254 255 // Removing this request may have freed up another to load. 256 LoadAnyStartablePendingRequests(); 257 } 258 } 259 260 RequestSet RemoveAllRequests() { 261 RequestSet unowned_requests; 262 for (RequestSet::iterator it = in_flight_requests_.begin(); 263 it != in_flight_requests_.end(); ++it) { 264 unowned_requests.insert(*it); 265 (*it)->set_accounted_as_delayable_request(false); 266 } 267 ClearInFlightRequests(); 268 return unowned_requests; 269 } 270 271 void OnNavigate() { 272 has_body_ = false; 273 } 274 275 void OnWillInsertBody() { 276 has_body_ = true; 277 LoadAnyStartablePendingRequests(); 278 } 279 280 void OnReceivedSpdyProxiedHttpResponse() { 281 if (!using_spdy_proxy_) { 282 using_spdy_proxy_ = true; 283 LoadAnyStartablePendingRequests(); 284 } 285 } 286 287 void ReprioritizeRequest(ScheduledResourceRequest* request, 288 RequestPriorityParams old_priority_params, 289 RequestPriorityParams new_priority_params) { 290 request->url_request()->SetPriority(new_priority_params.priority); 291 request->set_request_priority_params(new_priority_params); 292 if (!pending_requests_.IsQueued(request)) { 293 DCHECK(ContainsKey(in_flight_requests_, request)); 294 // The priority and SPDY support may have changed, so update the 295 // delayable count. 296 SetRequestDelayable(request, IsDelayableRequest(request)); 297 // Request has already started. 298 return; 299 } 300 301 pending_requests_.Erase(request); 302 pending_requests_.Insert(request); 303 304 if (new_priority_params.priority > old_priority_params.priority) { 305 // Check if this request is now able to load at its new priority. 306 LoadAnyStartablePendingRequests(); 307 } 308 } 309 310 private: 311 enum ShouldStartReqResult { 312 DO_NOT_START_REQUEST_AND_STOP_SEARCHING = -2, 313 DO_NOT_START_REQUEST_AND_KEEP_SEARCHING = -1, 314 START_REQUEST = 1, 315 }; 316 317 void InsertInFlightRequest(ScheduledResourceRequest* request) { 318 in_flight_requests_.insert(request); 319 if (IsDelayableRequest(request)) 320 SetRequestDelayable(request, true); 321 } 322 323 void EraseInFlightRequest(ScheduledResourceRequest* request) { 324 size_t erased = in_flight_requests_.erase(request); 325 DCHECK_EQ(1u, erased); 326 SetRequestDelayable(request, false); 327 DCHECK_LE(total_delayable_count_, in_flight_requests_.size()); 328 } 329 330 void ClearInFlightRequests() { 331 in_flight_requests_.clear(); 332 total_delayable_count_ = 0; 333 } 334 335 bool IsDelayableRequest(ScheduledResourceRequest* request) { 336 if (request->url_request()->priority() < net::LOW) { 337 net::HostPortPair host_port_pair = 338 net::HostPortPair::FromURL(request->url_request()->url()); 339 net::HttpServerProperties& http_server_properties = 340 *request->url_request()->context()->http_server_properties(); 341 if (!http_server_properties.SupportsSpdy(host_port_pair)) { 342 return true; 343 } 344 } 345 return false; 346 } 347 348 void SetRequestDelayable(ScheduledResourceRequest* request, 349 bool delayable) { 350 if (request->accounted_as_delayable_request() == delayable) 351 return; 352 if (delayable) 353 total_delayable_count_++; 354 else 355 total_delayable_count_--; 356 request->set_accounted_as_delayable_request(delayable); 357 } 358 359 bool ShouldKeepSearching( 360 const net::HostPortPair& active_request_host) const { 361 size_t same_host_count = 0; 362 for (RequestSet::const_iterator it = in_flight_requests_.begin(); 363 it != in_flight_requests_.end(); ++it) { 364 net::HostPortPair host_port_pair = 365 net::HostPortPair::FromURL((*it)->url_request()->url()); 366 if (active_request_host.Equals(host_port_pair)) { 367 same_host_count++; 368 if (same_host_count >= kMaxNumDelayableRequestsPerHost) 369 return true; 370 } 371 } 372 return false; 373 } 374 375 void StartRequest(ScheduledResourceRequest* request) { 376 InsertInFlightRequest(request); 377 request->Start(); 378 } 379 380 // ShouldStartRequest is the main scheduling algorithm. 381 // 382 // Requests are categorized into two categories: 383 // 384 // 1. Immediately issued requests, which are: 385 // 386 // * Higher priority requests (>= net::LOW). 387 // * Synchronous requests. 388 // * Requests to SPDY-capable origin servers. 389 // * Non-HTTP[S] requests. 390 // 391 // 2. The remainder are delayable requests, which follow these rules: 392 // 393 // * If no high priority requests are in flight, start loading low priority 394 // requests. 395 // * Once the renderer has a <body>, start loading delayable requests. 396 // * Never exceed 10 delayable requests in flight per client. 397 // * Never exceed 6 delayable requests for a given host. 398 // * Prior to <body>, allow one delayable request to load at a time. 399 ShouldStartReqResult ShouldStartRequest( 400 ScheduledResourceRequest* request) const { 401 const net::URLRequest& url_request = *request->url_request(); 402 // TODO(simonjam): This may end up causing disk contention. We should 403 // experiment with throttling if that happens. 404 if (!url_request.url().SchemeIsHTTPOrHTTPS()) { 405 return START_REQUEST; 406 } 407 408 if (using_spdy_proxy_ && url_request.url().SchemeIs("http")) { 409 return START_REQUEST; 410 } 411 412 net::HttpServerProperties& http_server_properties = 413 *url_request.context()->http_server_properties(); 414 415 if (url_request.priority() >= net::LOW || 416 !ResourceRequestInfo::ForRequest(&url_request)->IsAsync()) { 417 return START_REQUEST; 418 } 419 420 net::HostPortPair host_port_pair = 421 net::HostPortPair::FromURL(url_request.url()); 422 423 // TODO(willchan): We should really improve this algorithm as described in 424 // crbug.com/164101. Also, theoretically we should not count a SPDY request 425 // against the delayable requests limit. 426 if (http_server_properties.SupportsSpdy(host_port_pair)) { 427 return START_REQUEST; 428 } 429 430 size_t num_delayable_requests_in_flight = total_delayable_count_; 431 if (num_delayable_requests_in_flight >= kMaxNumDelayableRequestsPerClient) { 432 return DO_NOT_START_REQUEST_AND_STOP_SEARCHING; 433 } 434 435 if (ShouldKeepSearching(host_port_pair)) { 436 // There may be other requests for other hosts we'd allow, 437 // so keep checking. 438 return DO_NOT_START_REQUEST_AND_KEEP_SEARCHING; 439 } 440 441 bool have_immediate_requests_in_flight = 442 in_flight_requests_.size() > num_delayable_requests_in_flight; 443 if (have_immediate_requests_in_flight && !has_body_ && 444 num_delayable_requests_in_flight != 0) { 445 return DO_NOT_START_REQUEST_AND_STOP_SEARCHING; 446 } 447 448 return START_REQUEST; 449 } 450 451 void LoadAnyStartablePendingRequests() { 452 // We iterate through all the pending requests, starting with the highest 453 // priority one. For each entry, one of three things can happen: 454 // 1) We start the request, remove it from the list, and keep checking. 455 // 2) We do NOT start the request, but ShouldStartRequest() signals us that 456 // there may be room for other requests, so we keep checking and leave 457 // the previous request still in the list. 458 // 3) We do not start the request, same as above, but StartRequest() tells 459 // us there's no point in checking any further requests. 460 RequestQueue::NetQueue::iterator request_iter = 461 pending_requests_.GetNextHighestIterator(); 462 463 while (request_iter != pending_requests_.End()) { 464 ScheduledResourceRequest* request = *request_iter; 465 ShouldStartReqResult query_result = ShouldStartRequest(request); 466 467 if (query_result == START_REQUEST) { 468 pending_requests_.Erase(request); 469 StartRequest(request); 470 471 // StartRequest can modify the pending list, so we (re)start evaluation 472 // from the currently highest priority request. Avoid copying a singular 473 // iterator, which would trigger undefined behavior. 474 if (pending_requests_.GetNextHighestIterator() == 475 pending_requests_.End()) 476 break; 477 request_iter = pending_requests_.GetNextHighestIterator(); 478 } else if (query_result == DO_NOT_START_REQUEST_AND_KEEP_SEARCHING) { 479 ++request_iter; 480 continue; 481 } else { 482 DCHECK(query_result == DO_NOT_START_REQUEST_AND_STOP_SEARCHING); 483 break; 484 } 485 } 486 } 487 488 bool has_body_; 489 bool using_spdy_proxy_; 490 RequestQueue pending_requests_; 491 RequestSet in_flight_requests_; 492 // The number of delayable in-flight requests. 493 size_t total_delayable_count_; 494 }; 495 496 ResourceScheduler::ResourceScheduler() { 497 } 498 499 ResourceScheduler::~ResourceScheduler() { 500 DCHECK(unowned_requests_.empty()); 501 DCHECK(client_map_.empty()); 502 } 503 504 scoped_ptr<ResourceThrottle> ResourceScheduler::ScheduleRequest( 505 int child_id, 506 int route_id, 507 net::URLRequest* url_request) { 508 DCHECK(CalledOnValidThread()); 509 ClientId client_id = MakeClientId(child_id, route_id); 510 scoped_ptr<ScheduledResourceRequest> request( 511 new ScheduledResourceRequest(client_id, url_request, this, 512 RequestPriorityParams(url_request->priority(), 0))); 513 514 ClientMap::iterator it = client_map_.find(client_id); 515 if (it == client_map_.end()) { 516 // There are several ways this could happen: 517 // 1. <a ping> requests don't have a route_id. 518 // 2. Most unittests don't send the IPCs needed to register Clients. 519 // 3. The tab is closed while a RequestResource IPC is in flight. 520 unowned_requests_.insert(request.get()); 521 request->Start(); 522 return request.PassAs<ResourceThrottle>(); 523 } 524 525 Client* client = it->second; 526 client->ScheduleRequest(url_request, request.get()); 527 return request.PassAs<ResourceThrottle>(); 528 } 529 530 void ResourceScheduler::RemoveRequest(ScheduledResourceRequest* request) { 531 DCHECK(CalledOnValidThread()); 532 if (ContainsKey(unowned_requests_, request)) { 533 unowned_requests_.erase(request); 534 return; 535 } 536 537 ClientMap::iterator client_it = client_map_.find(request->client_id()); 538 if (client_it == client_map_.end()) { 539 return; 540 } 541 542 Client* client = client_it->second; 543 client->RemoveRequest(request); 544 } 545 546 void ResourceScheduler::OnClientCreated(int child_id, int route_id) { 547 DCHECK(CalledOnValidThread()); 548 ClientId client_id = MakeClientId(child_id, route_id); 549 DCHECK(!ContainsKey(client_map_, client_id)); 550 551 client_map_[client_id] = new Client; 552 } 553 554 void ResourceScheduler::OnClientDeleted(int child_id, int route_id) { 555 DCHECK(CalledOnValidThread()); 556 ClientId client_id = MakeClientId(child_id, route_id); 557 DCHECK(ContainsKey(client_map_, client_id)); 558 ClientMap::iterator it = client_map_.find(client_id); 559 if (it == client_map_.end()) 560 return; 561 562 Client* client = it->second; 563 564 // FYI, ResourceDispatcherHost cancels all of the requests after this function 565 // is called. It should end up canceling all of the requests except for a 566 // cross-renderer navigation. 567 RequestSet client_unowned_requests = client->RemoveAllRequests(); 568 for (RequestSet::iterator it = client_unowned_requests.begin(); 569 it != client_unowned_requests.end(); ++it) { 570 unowned_requests_.insert(*it); 571 } 572 573 delete client; 574 client_map_.erase(it); 575 } 576 577 void ResourceScheduler::OnNavigate(int child_id, int route_id) { 578 DCHECK(CalledOnValidThread()); 579 ClientId client_id = MakeClientId(child_id, route_id); 580 581 ClientMap::iterator it = client_map_.find(client_id); 582 if (it == client_map_.end()) { 583 // The client was likely deleted shortly before we received this IPC. 584 return; 585 } 586 587 Client* client = it->second; 588 client->OnNavigate(); 589 } 590 591 void ResourceScheduler::OnWillInsertBody(int child_id, int route_id) { 592 DCHECK(CalledOnValidThread()); 593 ClientId client_id = MakeClientId(child_id, route_id); 594 595 ClientMap::iterator it = client_map_.find(client_id); 596 if (it == client_map_.end()) { 597 // The client was likely deleted shortly before we received this IPC. 598 return; 599 } 600 601 Client* client = it->second; 602 client->OnWillInsertBody(); 603 } 604 605 void ResourceScheduler::OnReceivedSpdyProxiedHttpResponse( 606 int child_id, 607 int route_id) { 608 DCHECK(CalledOnValidThread()); 609 ClientId client_id = MakeClientId(child_id, route_id); 610 611 ClientMap::iterator client_it = client_map_.find(client_id); 612 if (client_it == client_map_.end()) { 613 return; 614 } 615 616 Client* client = client_it->second; 617 client->OnReceivedSpdyProxiedHttpResponse(); 618 } 619 620 void ResourceScheduler::ReprioritizeRequest(ScheduledResourceRequest* request, 621 net::RequestPriority new_priority, 622 int new_intra_priority_value) { 623 if (request->url_request()->load_flags() & net::LOAD_IGNORE_LIMITS) { 624 // We should not be re-prioritizing requests with the 625 // IGNORE_LIMITS flag. 626 NOTREACHED(); 627 return; 628 } 629 RequestPriorityParams new_priority_params(new_priority, 630 new_intra_priority_value); 631 RequestPriorityParams old_priority_params = 632 request->get_request_priority_params(); 633 634 DCHECK(old_priority_params != new_priority_params); 635 636 ClientMap::iterator client_it = client_map_.find(request->client_id()); 637 if (client_it == client_map_.end()) { 638 // The client was likely deleted shortly before we received this IPC. 639 request->url_request()->SetPriority(new_priority_params.priority); 640 request->set_request_priority_params(new_priority_params); 641 return; 642 } 643 644 if (old_priority_params == new_priority_params) 645 return; 646 647 Client *client = client_it->second; 648 client->ReprioritizeRequest( 649 request, old_priority_params, new_priority_params); 650 } 651 652 ResourceScheduler::ClientId ResourceScheduler::MakeClientId( 653 int child_id, int route_id) { 654 return (static_cast<ResourceScheduler::ClientId>(child_id) << 32) | route_id; 655 } 656 657 } // namespace content 658