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 "content/browser/loader/resource_scheduler.h" 6 7 #include "base/stl_util.h" 8 #include "content/common/resource_messages.h" 9 #include "content/browser/loader/resource_message_delegate.h" 10 #include "content/public/browser/resource_controller.h" 11 #include "content/public/browser/resource_request_info.h" 12 #include "content/public/browser/resource_throttle.h" 13 #include "ipc/ipc_message_macros.h" 14 #include "net/base/host_port_pair.h" 15 #include "net/base/load_flags.h" 16 #include "net/base/request_priority.h" 17 #include "net/http/http_server_properties.h" 18 #include "net/url_request/url_request.h" 19 #include "net/url_request/url_request_context.h" 20 21 namespace content { 22 23 static const size_t kMaxNumDelayableRequestsPerClient = 10; 24 25 // A thin wrapper around net::PriorityQueue that deals with 26 // ScheduledResourceRequests instead of PriorityQueue::Pointers. 27 class ResourceScheduler::RequestQueue { 28 public: 29 RequestQueue() : queue_(net::NUM_PRIORITIES) {} 30 ~RequestQueue() {} 31 32 // Adds |request| to the queue with given |priority|. 33 void Insert(ScheduledResourceRequest* request, 34 net::RequestPriority priority) { 35 DCHECK(!ContainsKey(pointers_, request)); 36 NetQueue::Pointer pointer = queue_.Insert(request, priority); 37 pointers_[request] = pointer; 38 } 39 40 // Removes |request| from the queue. 41 void Erase(ScheduledResourceRequest* request) { 42 PointerMap::iterator it = pointers_.find(request); 43 DCHECK(it != pointers_.end()); 44 queue_.Erase(it->second); 45 pointers_.erase(it); 46 } 47 48 // Returns the highest priority request that's queued, or NULL if none are. 49 ScheduledResourceRequest* FirstMax() { 50 return queue_.FirstMax().value(); 51 } 52 53 // Returns true if |request| is queued. 54 bool IsQueued(ScheduledResourceRequest* request) const { 55 return ContainsKey(pointers_, request); 56 } 57 58 // Returns true if no requests are queued. 59 bool IsEmpty() const { return queue_.size() == 0; } 60 61 private: 62 typedef net::PriorityQueue<ScheduledResourceRequest*> NetQueue; 63 typedef std::map<ScheduledResourceRequest*, NetQueue::Pointer> PointerMap; 64 65 NetQueue queue_; 66 PointerMap pointers_; 67 }; 68 69 // This is the handle we return to the ResourceDispatcherHostImpl so it can 70 // interact with the request. 71 class ResourceScheduler::ScheduledResourceRequest 72 : public ResourceMessageDelegate, 73 public ResourceThrottle { 74 public: 75 ScheduledResourceRequest(const ClientId& client_id, 76 net::URLRequest* request, 77 ResourceScheduler* scheduler) 78 : ResourceMessageDelegate(request), 79 client_id_(client_id), 80 request_(request), 81 ready_(false), 82 deferred_(false), 83 scheduler_(scheduler) { 84 } 85 86 virtual ~ScheduledResourceRequest() { 87 scheduler_->RemoveRequest(this); 88 } 89 90 void Start() { 91 ready_ = true; 92 if (deferred_ && request_->status().is_success()) { 93 deferred_ = false; 94 controller()->Resume(); 95 } 96 } 97 98 const ClientId& client_id() const { return client_id_; } 99 net::URLRequest* url_request() { return request_; } 100 const net::URLRequest* url_request() const { return request_; } 101 102 private: 103 // ResourceMessageDelegate interface: 104 virtual bool OnMessageReceived(const IPC::Message& message, 105 bool* message_was_ok) OVERRIDE { 106 bool handled = true; 107 IPC_BEGIN_MESSAGE_MAP_EX(ScheduledResourceRequest, message, *message_was_ok) 108 IPC_MESSAGE_HANDLER(ResourceHostMsg_DidChangePriority, DidChangePriority) 109 IPC_MESSAGE_UNHANDLED(handled = false) 110 IPC_END_MESSAGE_MAP_EX() 111 return handled; 112 } 113 114 // ResourceThrottle interface: 115 virtual void WillStartRequest(bool* defer) OVERRIDE { 116 deferred_ = *defer = !ready_; 117 } 118 119 void DidChangePriority(int request_id, net::RequestPriority new_priority) { 120 scheduler_->ReprioritizeRequest(this, new_priority); 121 } 122 123 ClientId client_id_; 124 net::URLRequest* request_; 125 bool ready_; 126 bool deferred_; 127 ResourceScheduler* scheduler_; 128 129 DISALLOW_COPY_AND_ASSIGN(ScheduledResourceRequest); 130 }; 131 132 // Each client represents a tab. 133 struct ResourceScheduler::Client { 134 Client() : has_body(false) {} 135 ~Client() {} 136 137 bool has_body; 138 RequestQueue pending_requests; 139 RequestSet in_flight_requests; 140 }; 141 142 ResourceScheduler::ResourceScheduler() { 143 } 144 145 ResourceScheduler::~ResourceScheduler() { 146 DCHECK(unowned_requests_.empty()); 147 DCHECK(client_map_.empty()); 148 } 149 150 scoped_ptr<ResourceThrottle> ResourceScheduler::ScheduleRequest( 151 int child_id, 152 int route_id, 153 net::URLRequest* url_request) { 154 DCHECK(CalledOnValidThread()); 155 ClientId client_id = MakeClientId(child_id, route_id); 156 scoped_ptr<ScheduledResourceRequest> request( 157 new ScheduledResourceRequest(client_id, url_request, this)); 158 159 ClientMap::iterator it = client_map_.find(client_id); 160 if (it == client_map_.end()) { 161 // There are several ways this could happen: 162 // 1. <a ping> requests don't have a route_id. 163 // 2. Most unittests don't send the IPCs needed to register Clients. 164 // 3. The tab is closed while a RequestResource IPC is in flight. 165 unowned_requests_.insert(request.get()); 166 request->Start(); 167 return request.PassAs<ResourceThrottle>(); 168 } 169 170 Client* client = it->second; 171 if (ShouldStartRequest(request.get(), client)) { 172 StartRequest(request.get(), client); 173 } else { 174 client->pending_requests.Insert(request.get(), url_request->priority()); 175 } 176 return request.PassAs<ResourceThrottle>(); 177 } 178 179 void ResourceScheduler::RemoveRequest(ScheduledResourceRequest* request) { 180 DCHECK(CalledOnValidThread()); 181 if (ContainsKey(unowned_requests_, request)) { 182 unowned_requests_.erase(request); 183 return; 184 } 185 186 ClientMap::iterator client_it = client_map_.find(request->client_id()); 187 if (client_it == client_map_.end()) { 188 return; 189 } 190 191 Client* client = client_it->second; 192 193 if (client->pending_requests.IsQueued(request)) { 194 client->pending_requests.Erase(request); 195 DCHECK(!ContainsKey(client->in_flight_requests, request)); 196 } else { 197 size_t erased = client->in_flight_requests.erase(request); 198 DCHECK(erased); 199 200 // Removing this request may have freed up another to load. 201 LoadAnyStartablePendingRequests(client); 202 } 203 } 204 205 void ResourceScheduler::OnClientCreated(int child_id, int route_id) { 206 DCHECK(CalledOnValidThread()); 207 ClientId client_id = MakeClientId(child_id, route_id); 208 DCHECK(!ContainsKey(client_map_, client_id)); 209 210 client_map_[client_id] = new Client; 211 } 212 213 void ResourceScheduler::OnClientDeleted(int child_id, int route_id) { 214 DCHECK(CalledOnValidThread()); 215 ClientId client_id = MakeClientId(child_id, route_id); 216 DCHECK(ContainsKey(client_map_, client_id)); 217 ClientMap::iterator it = client_map_.find(client_id); 218 Client* client = it->second; 219 220 // FYI, ResourceDispatcherHost cancels all of the requests after this function 221 // is called. It should end up canceling all of the requests except for a 222 // cross-renderer navigation. 223 for (RequestSet::iterator it = client->in_flight_requests.begin(); 224 it != client->in_flight_requests.end(); ++it) { 225 unowned_requests_.insert(*it); 226 } 227 client->in_flight_requests.clear(); 228 229 delete client; 230 client_map_.erase(it); 231 } 232 233 void ResourceScheduler::OnNavigate(int child_id, int route_id) { 234 DCHECK(CalledOnValidThread()); 235 ClientId client_id = MakeClientId(child_id, route_id); 236 237 ClientMap::iterator it = client_map_.find(client_id); 238 if (it == client_map_.end()) { 239 // The client was likely deleted shortly before we received this IPC. 240 return; 241 } 242 243 Client* client = it->second; 244 client->has_body = false; 245 } 246 247 void ResourceScheduler::OnWillInsertBody(int child_id, int route_id) { 248 DCHECK(CalledOnValidThread()); 249 ClientId client_id = MakeClientId(child_id, route_id); 250 251 ClientMap::iterator it = client_map_.find(client_id); 252 if (it == client_map_.end()) { 253 // The client was likely deleted shortly before we received this IPC. 254 return; 255 } 256 257 Client* client = it->second; 258 client->has_body = false; 259 if (!client->has_body) { 260 client->has_body = true; 261 LoadAnyStartablePendingRequests(client); 262 } 263 } 264 265 void ResourceScheduler::StartRequest(ScheduledResourceRequest* request, 266 Client* client) { 267 client->in_flight_requests.insert(request); 268 request->Start(); 269 } 270 271 void ResourceScheduler::ReprioritizeRequest(ScheduledResourceRequest* request, 272 net::RequestPriority new_priority) { 273 net::RequestPriority old_priority = request->url_request()->priority(); 274 DCHECK_NE(new_priority, old_priority); 275 request->url_request()->SetPriority(new_priority); 276 ClientMap::iterator client_it = client_map_.find(request->client_id()); 277 if (client_it == client_map_.end()) { 278 // The client was likely deleted shortly before we received this IPC. 279 return; 280 } 281 282 Client *client = client_it->second; 283 if (!client->pending_requests.IsQueued(request)) { 284 DCHECK(ContainsKey(client->in_flight_requests, request)); 285 // Request has already started. 286 return; 287 } 288 289 client->pending_requests.Erase(request); 290 client->pending_requests.Insert(request, request->url_request()->priority()); 291 292 if (new_priority > old_priority) { 293 // Check if this request is now able to load at its new priority. 294 LoadAnyStartablePendingRequests(client); 295 } 296 } 297 298 void ResourceScheduler::LoadAnyStartablePendingRequests(Client* client) { 299 while (!client->pending_requests.IsEmpty()) { 300 ScheduledResourceRequest* request = client->pending_requests.FirstMax(); 301 if (ShouldStartRequest(request, client)) { 302 client->pending_requests.Erase(request); 303 StartRequest(request, client); 304 } else { 305 break; 306 } 307 } 308 } 309 310 size_t ResourceScheduler::GetNumDelayableRequestsInFlight( 311 Client* client) const { 312 size_t count = 0; 313 for (RequestSet::iterator it = client->in_flight_requests.begin(); 314 it != client->in_flight_requests.end(); ++it) { 315 if ((*it)->url_request()->priority() < net::LOW) { 316 const net::HttpServerProperties& http_server_properties = 317 *(*it)->url_request()->context()->http_server_properties(); 318 if (!http_server_properties.SupportsSpdy( 319 net::HostPortPair::FromURL((*it)->url_request()->url()))) { 320 ++count; 321 } 322 } 323 } 324 return count; 325 } 326 327 // ShouldStartRequest is the main scheduling algorithm. 328 // 329 // Requests are categorized into two categories: 330 // 331 // 1. Immediately issued requests, which are: 332 // 333 // * Higher priority requests (>= net::LOW). 334 // * Synchronous requests. 335 // * Requests to SPDY-capable origin servers. 336 // 337 // 2. The remainder are delayable requests, which follow these rules: 338 // 339 // * If no high priority requests are in flight, start loading low priority 340 // requests. 341 // * Once the renderer has a <body>, start loading delayable requests. 342 // * Never exceed 10 delayable requests in flight per client. 343 // * Prior to <body>, allow one delayable request to load at a time. 344 bool ResourceScheduler::ShouldStartRequest(ScheduledResourceRequest* request, 345 Client* client) const { 346 const net::URLRequest& url_request = *request->url_request(); 347 const net::HttpServerProperties& http_server_properties = 348 *url_request.context()->http_server_properties(); 349 350 // TODO(willchan): We should really improve this algorithm as described in 351 // crbug.com/164101. Also, theoretically we should not count a SPDY request 352 // against the delayable requests limit. 353 bool origin_supports_spdy = http_server_properties.SupportsSpdy( 354 net::HostPortPair::FromURL(url_request.url())); 355 356 if (url_request.priority() >= net::LOW || 357 !ResourceRequestInfo::ForRequest(&url_request)->IsAsync() || 358 origin_supports_spdy) { 359 return true; 360 } 361 362 size_t num_delayable_requests_in_flight = 363 GetNumDelayableRequestsInFlight(client); 364 if (num_delayable_requests_in_flight >= kMaxNumDelayableRequestsPerClient) { 365 return false; 366 } 367 368 bool have_immediate_requests_in_flight = 369 client->in_flight_requests.size() > num_delayable_requests_in_flight; 370 if (have_immediate_requests_in_flight && !client->has_body && 371 num_delayable_requests_in_flight != 0) { 372 return false; 373 } 374 375 return true; 376 } 377 378 ResourceScheduler::ClientId ResourceScheduler::MakeClientId( 379 int child_id, int route_id) { 380 return (static_cast<ResourceScheduler::ClientId>(child_id) << 32) | route_id; 381 } 382 383 } // namespace content 384