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 "chrome/browser/net/predictor.h" 6 7 #include <algorithm> 8 #include <cmath> 9 #include <set> 10 #include <sstream> 11 12 #include "base/basictypes.h" 13 #include "base/bind.h" 14 #include "base/compiler_specific.h" 15 #include "base/containers/mru_cache.h" 16 #include "base/metrics/histogram.h" 17 #include "base/prefs/pref_service.h" 18 #include "base/prefs/scoped_user_pref_update.h" 19 #include "base/stl_util.h" 20 #include "base/strings/string_split.h" 21 #include "base/strings/string_util.h" 22 #include "base/strings/stringprintf.h" 23 #include "base/synchronization/waitable_event.h" 24 #include "base/threading/thread_restrictions.h" 25 #include "base/time/time.h" 26 #include "base/values.h" 27 #include "chrome/browser/io_thread.h" 28 #include "chrome/browser/net/preconnect.h" 29 #include "chrome/browser/net/spdyproxy/data_reduction_proxy_settings.h" 30 #include "chrome/browser/net/spdyproxy/proxy_advisor.h" 31 #include "chrome/browser/prefs/session_startup_pref.h" 32 #include "chrome/common/chrome_switches.h" 33 #include "chrome/common/pref_names.h" 34 #include "components/user_prefs/pref_registry_syncable.h" 35 #include "content/public/browser/browser_thread.h" 36 #include "net/base/address_list.h" 37 #include "net/base/completion_callback.h" 38 #include "net/base/host_port_pair.h" 39 #include "net/base/net_errors.h" 40 #include "net/base/net_log.h" 41 #include "net/dns/host_resolver.h" 42 #include "net/dns/single_request_host_resolver.h" 43 #include "net/url_request/url_request_context_getter.h" 44 45 using base::TimeDelta; 46 using content::BrowserThread; 47 48 namespace chrome_browser_net { 49 50 // static 51 const int Predictor::kPredictorReferrerVersion = 2; 52 const double Predictor::kPreconnectWorthyExpectedValue = 0.8; 53 const double Predictor::kDNSPreresolutionWorthyExpectedValue = 0.1; 54 const double Predictor::kDiscardableExpectedValue = 0.05; 55 // The goal is of trimming is to to reduce the importance (number of expected 56 // subresources needed) by a factor of 2 after about 24 hours of uptime. We will 57 // trim roughly once-an-hour of uptime. The ratio to use in each trim operation 58 // is then the 24th root of 0.5. If a user only surfs for 4 hours a day, then 59 // after about 6 days they will have halved all their estimates of subresource 60 // connections. Once this falls below kDiscardableExpectedValue the referrer 61 // will be discarded. 62 // TODO(jar): Measure size of referrer lists in the field. Consider an adaptive 63 // system that uses a higher trim ratio when the list is large. 64 // static 65 const double Predictor::kReferrerTrimRatio = 0.97153; 66 const int64 Predictor::kDurationBetweenTrimmingsHours = 1; 67 const int64 Predictor::kDurationBetweenTrimmingIncrementsSeconds = 15; 68 const size_t Predictor::kUrlsTrimmedPerIncrement = 5u; 69 const size_t Predictor::kMaxSpeculativeParallelResolves = 3; 70 const int Predictor::kMaxUnusedSocketLifetimeSecondsWithoutAGet = 10; 71 // To control our congestion avoidance system, which discards a queue when 72 // resolutions are "taking too long," we need an expected resolution time. 73 // Common average is in the range of 300-500ms. 74 const int kExpectedResolutionTimeMs = 500; 75 const int Predictor::kTypicalSpeculativeGroupSize = 8; 76 const int Predictor::kMaxSpeculativeResolveQueueDelayMs = 77 (kExpectedResolutionTimeMs * Predictor::kTypicalSpeculativeGroupSize) / 78 Predictor::kMaxSpeculativeParallelResolves; 79 80 static int g_max_queueing_delay_ms = 81 Predictor::kMaxSpeculativeResolveQueueDelayMs; 82 static size_t g_max_parallel_resolves = 83 Predictor::kMaxSpeculativeParallelResolves; 84 85 // A version number for prefs that are saved. This should be incremented when 86 // we change the format so that we discard old data. 87 static const int kPredictorStartupFormatVersion = 1; 88 89 class Predictor::LookupRequest { 90 public: 91 LookupRequest(Predictor* predictor, 92 net::HostResolver* host_resolver, 93 const GURL& url) 94 : predictor_(predictor), 95 url_(url), 96 resolver_(host_resolver) { 97 } 98 99 // Return underlying network resolver status. 100 // net::OK ==> Host was found synchronously. 101 // net:ERR_IO_PENDING ==> Network will callback later with result. 102 // anything else ==> Host was not found synchronously. 103 int Start() { 104 net::HostResolver::RequestInfo resolve_info( 105 net::HostPortPair::FromURL(url_)); 106 107 // Make a note that this is a speculative resolve request. This allows us 108 // to separate it from real navigations in the observer's callback, and 109 // lets the HostResolver know it can de-prioritize it. 110 resolve_info.set_is_speculative(true); 111 return resolver_.Resolve( 112 resolve_info, 113 net::DEFAULT_PRIORITY, 114 &addresses_, 115 base::Bind(&LookupRequest::OnLookupFinished, base::Unretained(this)), 116 net::BoundNetLog()); 117 } 118 119 private: 120 void OnLookupFinished(int result) { 121 predictor_->OnLookupFinished(this, url_, result == net::OK); 122 } 123 124 Predictor* predictor_; // The predictor which started us. 125 126 const GURL url_; // Hostname to resolve. 127 net::SingleRequestHostResolver resolver_; 128 net::AddressList addresses_; 129 130 DISALLOW_COPY_AND_ASSIGN(LookupRequest); 131 }; 132 133 // This records UMAs for preconnect usage based on navigation URLs to 134 // gather precision/recall for user-event based preconnect triggers. 135 // Stats are gathered via a LRU cache that remembers all preconnect within the 136 // last N seconds. 137 // A preconnect trigger is considered as used iff a navigation including 138 // access to the preconnected host occurs within a time period specified by 139 // kMaxUnusedSocketLifetimeSecondsWithoutAGet. 140 class Predictor::PreconnectUsage { 141 public: 142 PreconnectUsage(); 143 ~PreconnectUsage(); 144 145 // Record a preconnect trigger to |url|. 146 void ObservePreconnect(const GURL& url); 147 148 // Record a user navigation with its redirect history, |url_chain|. 149 // We are uncertain if this is actually a link navigation. 150 void ObserveNavigationChain(const std::vector<GURL>& url_chain, 151 bool is_subresource); 152 153 // Record a user link navigation to |final_url|. 154 // We are certain that this is a user-triggered link navigation. 155 void ObserveLinkNavigation(const GURL& final_url); 156 157 private: 158 // This tracks whether a preconnect was used in some navigation or not 159 class PreconnectPrecisionStat { 160 public: 161 PreconnectPrecisionStat() 162 : timestamp_(base::TimeTicks::Now()), 163 was_used_(false) { 164 } 165 166 const base::TimeTicks& timestamp() { return timestamp_; } 167 168 void set_was_used() { was_used_ = true; } 169 bool was_used() const { return was_used_; } 170 171 private: 172 base::TimeTicks timestamp_; 173 bool was_used_; 174 }; 175 176 typedef base::MRUCache<GURL, PreconnectPrecisionStat> MRUPreconnects; 177 MRUPreconnects mru_preconnects_; 178 179 // The longest time an entry can persist in mru_preconnect_ 180 const base::TimeDelta max_duration_; 181 182 std::vector<GURL> recent_navigation_chain_; 183 184 DISALLOW_COPY_AND_ASSIGN(PreconnectUsage); 185 }; 186 187 Predictor::PreconnectUsage::PreconnectUsage() 188 : mru_preconnects_(MRUPreconnects::NO_AUTO_EVICT), 189 max_duration_(base::TimeDelta::FromSeconds( 190 Predictor::kMaxUnusedSocketLifetimeSecondsWithoutAGet)) { 191 } 192 193 Predictor::PreconnectUsage::~PreconnectUsage() {} 194 195 void Predictor::PreconnectUsage::ObservePreconnect(const GURL& url) { 196 // Evict any overly old entries and record stats. 197 base::TimeTicks now = base::TimeTicks::Now(); 198 199 MRUPreconnects::reverse_iterator eldest_preconnect = 200 mru_preconnects_.rbegin(); 201 while (!mru_preconnects_.empty()) { 202 DCHECK(eldest_preconnect == mru_preconnects_.rbegin()); 203 if (now - eldest_preconnect->second.timestamp() < max_duration_) 204 break; 205 206 UMA_HISTOGRAM_BOOLEAN("Net.PreconnectTriggerUsed", 207 eldest_preconnect->second.was_used()); 208 eldest_preconnect = mru_preconnects_.Erase(eldest_preconnect); 209 } 210 211 // Add new entry. 212 GURL canonical_url(Predictor::CanonicalizeUrl(url)); 213 mru_preconnects_.Put(canonical_url, PreconnectPrecisionStat()); 214 } 215 216 void Predictor::PreconnectUsage::ObserveNavigationChain( 217 const std::vector<GURL>& url_chain, 218 bool is_subresource) { 219 if (url_chain.empty()) 220 return; 221 222 if (!is_subresource) 223 recent_navigation_chain_ = url_chain; 224 225 GURL canonical_url(Predictor::CanonicalizeUrl(url_chain.back())); 226 227 MRUPreconnects::iterator itPreconnect = mru_preconnects_.Peek(canonical_url); 228 bool was_preconnected = (itPreconnect != mru_preconnects_.end()); 229 230 // This is an UMA which was named incorrectly. This actually measures the 231 // ratio of URLRequests which have used a preconnected session. 232 UMA_HISTOGRAM_BOOLEAN("Net.PreconnectedNavigation", was_preconnected); 233 } 234 235 void Predictor::PreconnectUsage::ObserveLinkNavigation(const GURL& url) { 236 if (recent_navigation_chain_.empty() || 237 url != recent_navigation_chain_.back()) { 238 // The navigation chain is not available for this navigation. 239 recent_navigation_chain_.clear(); 240 recent_navigation_chain_.push_back(url); 241 } 242 243 // See if the link navigation involved preconnected session. 244 bool did_use_preconnect = false; 245 for (std::vector<GURL>::const_iterator it = recent_navigation_chain_.begin(); 246 it != recent_navigation_chain_.end(); 247 ++it) { 248 GURL canonical_url(Predictor::CanonicalizeUrl(*it)); 249 250 // Record the preconnect trigger for the url as used if exist 251 MRUPreconnects::iterator itPreconnect = 252 mru_preconnects_.Peek(canonical_url); 253 bool was_preconnected = (itPreconnect != mru_preconnects_.end()); 254 if (was_preconnected) { 255 itPreconnect->second.set_was_used(); 256 did_use_preconnect = true; 257 } 258 } 259 260 UMA_HISTOGRAM_BOOLEAN("Net.PreconnectedLinkNavigations", did_use_preconnect); 261 } 262 263 Predictor::Predictor(bool preconnect_enabled) 264 : url_request_context_getter_(NULL), 265 predictor_enabled_(true), 266 peak_pending_lookups_(0), 267 shutdown_(false), 268 max_concurrent_dns_lookups_(g_max_parallel_resolves), 269 max_dns_queue_delay_( 270 TimeDelta::FromMilliseconds(g_max_queueing_delay_ms)), 271 host_resolver_(NULL), 272 preconnect_enabled_(preconnect_enabled), 273 consecutive_omnibox_preconnect_count_(0), 274 next_trim_time_(base::TimeTicks::Now() + 275 TimeDelta::FromHours(kDurationBetweenTrimmingsHours)) { 276 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI)); 277 } 278 279 Predictor::~Predictor() { 280 // TODO(rlp): Add DCHECK for CurrentlyOn(BrowserThread::IO) when the 281 // ProfileManagerTest has been updated with a mock profile. 282 DCHECK(shutdown_); 283 } 284 285 // static 286 Predictor* Predictor::CreatePredictor(bool preconnect_enabled, 287 bool simple_shutdown) { 288 if (simple_shutdown) 289 return new SimplePredictor(preconnect_enabled); 290 return new Predictor(preconnect_enabled); 291 } 292 293 void Predictor::RegisterProfilePrefs( 294 user_prefs::PrefRegistrySyncable* registry) { 295 registry->RegisterListPref(prefs::kDnsPrefetchingStartupList, 296 user_prefs::PrefRegistrySyncable::UNSYNCABLE_PREF); 297 registry->RegisterListPref(prefs::kDnsPrefetchingHostReferralList, 298 user_prefs::PrefRegistrySyncable::UNSYNCABLE_PREF); 299 } 300 301 // --------------------- Start UI methods. ------------------------------------ 302 303 void Predictor::InitNetworkPredictor(PrefService* user_prefs, 304 PrefService* local_state, 305 IOThread* io_thread, 306 net::URLRequestContextGetter* getter) { 307 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI)); 308 309 bool predictor_enabled = 310 user_prefs->GetBoolean(prefs::kNetworkPredictionEnabled); 311 312 url_request_context_getter_ = getter; 313 314 // Gather the list of hostnames to prefetch on startup. 315 UrlList urls = GetPredictedUrlListAtStartup(user_prefs, local_state); 316 317 base::ListValue* referral_list = 318 static_cast<base::ListValue*>(user_prefs->GetList( 319 prefs::kDnsPrefetchingHostReferralList)->DeepCopy()); 320 321 // Now that we have the statistics in memory, wipe them from the Preferences 322 // file. They will be serialized back on a clean shutdown. This way we only 323 // have to worry about clearing our in-memory state when Clearing Browsing 324 // Data. 325 user_prefs->ClearPref(prefs::kDnsPrefetchingStartupList); 326 user_prefs->ClearPref(prefs::kDnsPrefetchingHostReferralList); 327 328 #if defined(OS_ANDROID) || defined(OS_IOS) 329 // TODO(marq): Once https://codereview.chromium.org/30883003/ lands, also 330 // condition this on DataReductionProxySettings::IsDataReductionProxyAllowed() 331 // Until then, we may create a proxy advisor when the proxy feature itself 332 // isn't available, and the advisor instance will never send advisory 333 // requests, which is slightly wasteful but not harmful. 334 if (DataReductionProxySettings::IsPreconnectHintingAllowed()) { 335 proxy_advisor_.reset(new ProxyAdvisor(user_prefs, getter)); 336 } 337 #endif 338 339 BrowserThread::PostTask( 340 BrowserThread::IO, 341 FROM_HERE, 342 base::Bind( 343 &Predictor::FinalizeInitializationOnIOThread, 344 base::Unretained(this), 345 urls, referral_list, 346 io_thread, predictor_enabled)); 347 } 348 349 void Predictor::AnticipateOmniboxUrl(const GURL& url, bool preconnectable) { 350 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI)); 351 if (!predictor_enabled_) 352 return; 353 if (!url.is_valid() || !url.has_host()) 354 return; 355 std::string host = url.HostNoBrackets(); 356 bool is_new_host_request = (host != last_omnibox_host_); 357 last_omnibox_host_ = host; 358 359 UrlInfo::ResolutionMotivation motivation(UrlInfo::OMNIBOX_MOTIVATED); 360 base::TimeTicks now = base::TimeTicks::Now(); 361 362 if (preconnect_enabled()) { 363 if (preconnectable && !is_new_host_request) { 364 ++consecutive_omnibox_preconnect_count_; 365 // The omnibox suggests a search URL (for which we can preconnect) after 366 // one or two characters are typed, even though such typing often (1 in 367 // 3?) becomes a real URL. This code waits till is has more evidence of a 368 // preconnectable URL (search URL) before forming a preconnection, so as 369 // to reduce the useless preconnect rate. 370 // Perchance this logic should be pushed back into the omnibox, where the 371 // actual characters typed, such as a space, can better forcast whether 372 // we need to search/preconnect or not. By waiting for at least 4 373 // characters in a row that have lead to a search proposal, we avoid 374 // preconnections for a prefix like "www." and we also wait until we have 375 // at least a 4 letter word to search for. 376 // Each character typed appears to induce 2 calls to 377 // AnticipateOmniboxUrl(), so we double 4 characters and limit at 8 378 // requests. 379 // TODO(jar): Use an A/B test to optimize this. 380 const int kMinConsecutiveRequests = 8; 381 if (consecutive_omnibox_preconnect_count_ >= kMinConsecutiveRequests) { 382 // TODO(jar): Perhaps we should do a GET to leave the socket open in the 383 // pool. Currently, we just do a connect, which MAY be reset if we 384 // don't use it in 10 secondes!!! As a result, we may do more 385 // connections, and actually cost the server more than if we did a real 386 // get with a fake request (/gen_204 might be the good path on Google). 387 const int kMaxSearchKeepaliveSeconds(10); 388 if ((now - last_omnibox_preconnect_).InSeconds() < 389 kMaxSearchKeepaliveSeconds) 390 return; // We've done a preconnect recently. 391 last_omnibox_preconnect_ = now; 392 const int kConnectionsNeeded = 1; 393 PreconnectUrl(CanonicalizeUrl(url), GURL(), motivation, 394 kConnectionsNeeded); 395 return; // Skip pre-resolution, since we'll open a connection. 396 } 397 } else { 398 consecutive_omnibox_preconnect_count_ = 0; 399 } 400 } 401 402 // Fall through and consider pre-resolution. 403 404 // Omnibox tends to call in pairs (just a few milliseconds apart), and we 405 // really don't need to keep resolving a name that often. 406 // TODO(jar): A/B tests could check for perf impact of the early returns. 407 if (!is_new_host_request) { 408 const int kMinPreresolveSeconds(10); 409 if (kMinPreresolveSeconds > (now - last_omnibox_preresolve_).InSeconds()) 410 return; 411 } 412 last_omnibox_preresolve_ = now; 413 414 BrowserThread::PostTask( 415 BrowserThread::IO, 416 FROM_HERE, 417 base::Bind(&Predictor::Resolve, base::Unretained(this), 418 CanonicalizeUrl(url), motivation)); 419 } 420 421 void Predictor::PreconnectUrlAndSubresources(const GURL& url, 422 const GURL& first_party_for_cookies) { 423 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI) || 424 BrowserThread::CurrentlyOn(BrowserThread::IO)); 425 if (!predictor_enabled_ || !preconnect_enabled() || 426 !url.is_valid() || !url.has_host()) 427 return; 428 429 UrlInfo::ResolutionMotivation motivation(UrlInfo::EARLY_LOAD_MOTIVATED); 430 const int kConnectionsNeeded = 1; 431 PreconnectUrl(CanonicalizeUrl(url), first_party_for_cookies, 432 motivation, kConnectionsNeeded); 433 PredictFrameSubresources(url.GetWithEmptyPath(), first_party_for_cookies); 434 } 435 436 UrlList Predictor::GetPredictedUrlListAtStartup( 437 PrefService* user_prefs, 438 PrefService* local_state) { 439 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI)); 440 UrlList urls; 441 // Recall list of URLs we learned about during last session. 442 // This may catch secondary hostnames, pulled in by the homepages. It will 443 // also catch more of the "primary" home pages, since that was (presumably) 444 // rendered first (and will be rendered first this time too). 445 const ListValue* startup_list = 446 user_prefs->GetList(prefs::kDnsPrefetchingStartupList); 447 448 if (startup_list) { 449 base::ListValue::const_iterator it = startup_list->begin(); 450 int format_version = -1; 451 if (it != startup_list->end() && 452 (*it)->GetAsInteger(&format_version) && 453 format_version == kPredictorStartupFormatVersion) { 454 ++it; 455 for (; it != startup_list->end(); ++it) { 456 std::string url_spec; 457 if (!(*it)->GetAsString(&url_spec)) { 458 LOG(DFATAL); 459 break; // Format incompatibility. 460 } 461 GURL url(url_spec); 462 if (!url.has_host() || !url.has_scheme()) { 463 LOG(DFATAL); 464 break; // Format incompatibility. 465 } 466 467 urls.push_back(url); 468 } 469 } 470 } 471 472 // Prepare for any static home page(s) the user has in prefs. The user may 473 // have a LOT of tab's specified, so we may as well try to warm them all. 474 SessionStartupPref tab_start_pref = 475 SessionStartupPref::GetStartupPref(user_prefs); 476 if (SessionStartupPref::URLS == tab_start_pref.type) { 477 for (size_t i = 0; i < tab_start_pref.urls.size(); i++) { 478 GURL gurl = tab_start_pref.urls[i]; 479 if (!gurl.is_valid() || gurl.SchemeIsFile() || gurl.host().empty()) 480 continue; 481 if (gurl.SchemeIsHTTPOrHTTPS()) 482 urls.push_back(gurl.GetWithEmptyPath()); 483 } 484 } 485 486 if (urls.empty()) 487 urls.push_back(GURL("http://www.google.com:80")); 488 489 return urls; 490 } 491 492 void Predictor::set_max_queueing_delay(int max_queueing_delay_ms) { 493 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI)); 494 g_max_queueing_delay_ms = max_queueing_delay_ms; 495 } 496 497 void Predictor::set_max_parallel_resolves(size_t max_parallel_resolves) { 498 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI)); 499 g_max_parallel_resolves = max_parallel_resolves; 500 } 501 502 void Predictor::ShutdownOnUIThread() { 503 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI)); 504 BrowserThread::PostTask( 505 BrowserThread::IO, 506 FROM_HERE, 507 base::Bind(&Predictor::Shutdown, base::Unretained(this))); 508 } 509 510 // ---------------------- End UI methods. ------------------------------------- 511 512 // --------------------- Start IO methods. ------------------------------------ 513 514 void Predictor::Shutdown() { 515 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::IO)); 516 DCHECK(!shutdown_); 517 shutdown_ = true; 518 519 STLDeleteElements(&pending_lookups_); 520 } 521 522 void Predictor::DiscardAllResults() { 523 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::IO)); 524 // Delete anything listed so far in this session that shows in about:dns. 525 referrers_.clear(); 526 527 528 // Try to delete anything in our work queue. 529 while (!work_queue_.IsEmpty()) { 530 // Emulate processing cycle as though host was not found. 531 GURL url = work_queue_.Pop(); 532 UrlInfo* info = &results_[url]; 533 DCHECK(info->HasUrl(url)); 534 info->SetAssignedState(); 535 info->SetNoSuchNameState(); 536 } 537 // Now every result_ is either resolved, or is being resolved 538 // (see LookupRequest). 539 540 // Step through result_, recording names of all hosts that can't be erased. 541 // We can't erase anything being worked on. 542 Results assignees; 543 for (Results::iterator it = results_.begin(); results_.end() != it; ++it) { 544 GURL url(it->first); 545 UrlInfo* info = &it->second; 546 DCHECK(info->HasUrl(url)); 547 if (info->is_assigned()) { 548 info->SetPendingDeleteState(); 549 assignees[url] = *info; 550 } 551 } 552 DCHECK_LE(assignees.size(), max_concurrent_dns_lookups_); 553 results_.clear(); 554 // Put back in the names being worked on. 555 for (Results::iterator it = assignees.begin(); assignees.end() != it; ++it) { 556 DCHECK(it->second.is_marked_to_delete()); 557 results_[it->first] = it->second; 558 } 559 } 560 561 // Overloaded Resolve() to take a vector of names. 562 void Predictor::ResolveList(const UrlList& urls, 563 UrlInfo::ResolutionMotivation motivation) { 564 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::IO)); 565 566 for (UrlList::const_iterator it = urls.begin(); it < urls.end(); ++it) { 567 AppendToResolutionQueue(*it, motivation); 568 } 569 } 570 571 // Basic Resolve() takes an invidual name, and adds it 572 // to the queue. 573 void Predictor::Resolve(const GURL& url, 574 UrlInfo::ResolutionMotivation motivation) { 575 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::IO)); 576 if (!url.has_host()) 577 return; 578 AppendToResolutionQueue(url, motivation); 579 } 580 581 void Predictor::LearnFromNavigation(const GURL& referring_url, 582 const GURL& target_url) { 583 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::IO)); 584 if (!predictor_enabled_) 585 return; 586 DCHECK_EQ(referring_url, Predictor::CanonicalizeUrl(referring_url)); 587 DCHECK_NE(referring_url, GURL::EmptyGURL()); 588 DCHECK_EQ(target_url, Predictor::CanonicalizeUrl(target_url)); 589 DCHECK_NE(target_url, GURL::EmptyGURL()); 590 591 referrers_[referring_url].SuggestHost(target_url); 592 // Possibly do some referrer trimming. 593 TrimReferrers(); 594 } 595 596 //----------------------------------------------------------------------------- 597 // This section supports the about:dns page. 598 599 void Predictor::PredictorGetHtmlInfo(Predictor* predictor, 600 std::string* output) { 601 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::IO)); 602 603 output->append("<html><head><title>About DNS</title>" 604 // We'd like the following no-cache... but it doesn't work. 605 // "<META HTTP-EQUIV=\"Pragma\" CONTENT=\"no-cache\">" 606 "</head><body>"); 607 if (predictor && predictor->predictor_enabled()) { 608 predictor->GetHtmlInfo(output); 609 } else { 610 output->append("DNS pre-resolution and TCP pre-connection is disabled."); 611 } 612 output->append("</body></html>"); 613 } 614 615 // Provide sort order so all .com's are together, etc. 616 struct RightToLeftStringSorter { 617 bool operator()(const GURL& left, const GURL& right) const { 618 return ReverseComponents(left) < ReverseComponents(right); 619 } 620 621 private: 622 // Transforms something like "http://www.google.com/xyz" to 623 // "http://com.google.www/xyz". 624 static std::string ReverseComponents(const GURL& url) { 625 // Reverse the components in the hostname. 626 std::vector<std::string> parts; 627 base::SplitString(url.host(), '.', &parts); 628 std::reverse(parts.begin(), parts.end()); 629 std::string reversed_host = JoinString(parts, '.'); 630 631 // Return the new URL. 632 GURL::Replacements url_components; 633 url_components.SetHostStr(reversed_host); 634 return url.ReplaceComponents(url_components).spec(); 635 } 636 }; 637 638 void Predictor::GetHtmlReferrerLists(std::string* output) { 639 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::IO)); 640 if (referrers_.empty()) 641 return; 642 643 // TODO(jar): Remove any plausible JavaScript from names before displaying. 644 645 typedef std::set<GURL, struct RightToLeftStringSorter> 646 SortedNames; 647 SortedNames sorted_names; 648 649 for (Referrers::iterator it = referrers_.begin(); 650 referrers_.end() != it; ++it) 651 sorted_names.insert(it->first); 652 653 output->append("<br><table border>"); 654 output->append( 655 "<tr><th>Host for Page</th>" 656 "<th>Page Load<br>Count</th>" 657 "<th>Subresource<br>Navigations</th>" 658 "<th>Subresource<br>PreConnects</th>" 659 "<th>Subresource<br>PreResolves</th>" 660 "<th>Expected<br>Connects</th>" 661 "<th>Subresource Spec</th></tr>"); 662 663 for (SortedNames::iterator it = sorted_names.begin(); 664 sorted_names.end() != it; ++it) { 665 Referrer* referrer = &(referrers_[*it]); 666 bool first_set_of_futures = true; 667 for (Referrer::iterator future_url = referrer->begin(); 668 future_url != referrer->end(); ++future_url) { 669 output->append("<tr align=right>"); 670 if (first_set_of_futures) { 671 base::StringAppendF(output, 672 "<td rowspan=%d>%s</td><td rowspan=%d>%d</td>", 673 static_cast<int>(referrer->size()), 674 it->spec().c_str(), 675 static_cast<int>(referrer->size()), 676 static_cast<int>(referrer->use_count())); 677 } 678 first_set_of_futures = false; 679 base::StringAppendF(output, 680 "<td>%d</td><td>%d</td><td>%d</td><td>%2.3f</td><td>%s</td></tr>", 681 static_cast<int>(future_url->second.navigation_count()), 682 static_cast<int>(future_url->second.preconnection_count()), 683 static_cast<int>(future_url->second.preresolution_count()), 684 static_cast<double>(future_url->second.subresource_use_rate()), 685 future_url->first.spec().c_str()); 686 } 687 } 688 output->append("</table>"); 689 } 690 691 void Predictor::GetHtmlInfo(std::string* output) { 692 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::IO)); 693 if (initial_observer_.get()) 694 initial_observer_->GetFirstResolutionsHtml(output); 695 // Show list of subresource predictions and stats. 696 GetHtmlReferrerLists(output); 697 698 // Local lists for calling UrlInfo 699 UrlInfo::UrlInfoTable name_not_found; 700 UrlInfo::UrlInfoTable name_preresolved; 701 702 // Get copies of all useful data. 703 typedef std::map<GURL, UrlInfo, RightToLeftStringSorter> SortedUrlInfo; 704 SortedUrlInfo snapshot; 705 // UrlInfo supports value semantics, so we can do a shallow copy. 706 for (Results::iterator it(results_.begin()); it != results_.end(); it++) 707 snapshot[it->first] = it->second; 708 709 // Partition the UrlInfo's into categories. 710 for (SortedUrlInfo::iterator it(snapshot.begin()); 711 it != snapshot.end(); it++) { 712 if (it->second.was_nonexistent()) { 713 name_not_found.push_back(it->second); 714 continue; 715 } 716 if (!it->second.was_found()) 717 continue; // Still being processed. 718 name_preresolved.push_back(it->second); 719 } 720 721 bool brief = false; 722 #ifdef NDEBUG 723 brief = true; 724 #endif // NDEBUG 725 726 // Call for display of each table, along with title. 727 UrlInfo::GetHtmlTable(name_preresolved, 728 "Preresolution DNS records performed for ", brief, output); 729 UrlInfo::GetHtmlTable(name_not_found, 730 "Preresolving DNS records revealed non-existence for ", brief, output); 731 } 732 733 void Predictor::TrimReferrersNow() { 734 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::IO)); 735 // Just finish up work if an incremental trim is in progress. 736 if (urls_being_trimmed_.empty()) 737 LoadUrlsForTrimming(); 738 IncrementalTrimReferrers(true); // Do everything now. 739 } 740 741 void Predictor::SerializeReferrers(base::ListValue* referral_list) { 742 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::IO)); 743 referral_list->Clear(); 744 referral_list->Append(new base::FundamentalValue(kPredictorReferrerVersion)); 745 for (Referrers::const_iterator it = referrers_.begin(); 746 it != referrers_.end(); ++it) { 747 // Serialize the list of subresource names. 748 Value* subresource_list(it->second.Serialize()); 749 750 // Create a list for each referer. 751 ListValue* motivator(new ListValue); 752 motivator->Append(new StringValue(it->first.spec())); 753 motivator->Append(subresource_list); 754 755 referral_list->Append(motivator); 756 } 757 } 758 759 void Predictor::DeserializeReferrers(const base::ListValue& referral_list) { 760 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::IO)); 761 int format_version = -1; 762 if (referral_list.GetSize() > 0 && 763 referral_list.GetInteger(0, &format_version) && 764 format_version == kPredictorReferrerVersion) { 765 for (size_t i = 1; i < referral_list.GetSize(); ++i) { 766 const base::ListValue* motivator; 767 if (!referral_list.GetList(i, &motivator)) { 768 NOTREACHED(); 769 return; 770 } 771 std::string motivating_url_spec; 772 if (!motivator->GetString(0, &motivating_url_spec)) { 773 NOTREACHED(); 774 return; 775 } 776 777 const Value* subresource_list; 778 if (!motivator->Get(1, &subresource_list)) { 779 NOTREACHED(); 780 return; 781 } 782 783 referrers_[GURL(motivating_url_spec)].Deserialize(*subresource_list); 784 } 785 } 786 } 787 788 void Predictor::DeserializeReferrersThenDelete( 789 base::ListValue* referral_list) { 790 DeserializeReferrers(*referral_list); 791 delete referral_list; 792 } 793 794 void Predictor::DiscardInitialNavigationHistory() { 795 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::IO)); 796 if (initial_observer_.get()) 797 initial_observer_->DiscardInitialNavigationHistory(); 798 } 799 800 void Predictor::FinalizeInitializationOnIOThread( 801 const UrlList& startup_urls, 802 base::ListValue* referral_list, 803 IOThread* io_thread, 804 bool predictor_enabled) { 805 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::IO)); 806 807 predictor_enabled_ = predictor_enabled; 808 initial_observer_.reset(new InitialObserver()); 809 host_resolver_ = io_thread->globals()->host_resolver.get(); 810 preconnect_usage_.reset(new PreconnectUsage()); 811 812 // base::WeakPtrFactory instances need to be created and destroyed 813 // on the same thread. The predictor lives on the IO thread and will die 814 // from there so now that we're on the IO thread we need to properly 815 // initialize the base::WeakPtrFactory. 816 // TODO(groby): Check if WeakPtrFactory has the same constraint. 817 weak_factory_.reset(new base::WeakPtrFactory<Predictor>(this)); 818 819 // Prefetch these hostnames on startup. 820 DnsPrefetchMotivatedList(startup_urls, UrlInfo::STARTUP_LIST_MOTIVATED); 821 DeserializeReferrersThenDelete(referral_list); 822 } 823 824 //----------------------------------------------------------------------------- 825 // This section intermingles prefetch results with actual browser HTTP 826 // network activity. It supports calculating of the benefit of a prefetch, as 827 // well as recording what prefetched hostname resolutions might be potentially 828 // helpful during the next chrome-startup. 829 //----------------------------------------------------------------------------- 830 831 void Predictor::LearnAboutInitialNavigation(const GURL& url) { 832 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::IO)); 833 if (!predictor_enabled_ || NULL == initial_observer_.get() ) 834 return; 835 initial_observer_->Append(url, this); 836 } 837 838 // This API is only used in the browser process. 839 // It is called from an IPC message originating in the renderer. It currently 840 // includes both Page-Scan, and Link-Hover prefetching. 841 // TODO(jar): Separate out link-hover prefetching, and page-scan results. 842 void Predictor::DnsPrefetchList(const NameList& hostnames) { 843 // TODO(jar): Push GURL transport further back into renderer, but this will 844 // require a Webkit change in the observer :-/. 845 UrlList urls; 846 for (NameList::const_iterator it = hostnames.begin(); 847 it < hostnames.end(); 848 ++it) { 849 urls.push_back(GURL("http://" + *it + ":80")); 850 } 851 852 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::IO)); 853 DnsPrefetchMotivatedList(urls, UrlInfo::PAGE_SCAN_MOTIVATED); 854 } 855 856 void Predictor::DnsPrefetchMotivatedList( 857 const UrlList& urls, 858 UrlInfo::ResolutionMotivation motivation) { 859 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI) || 860 BrowserThread::CurrentlyOn(BrowserThread::IO)); 861 if (!predictor_enabled_) 862 return; 863 864 if (BrowserThread::CurrentlyOn(BrowserThread::IO)) { 865 ResolveList(urls, motivation); 866 } else { 867 BrowserThread::PostTask( 868 BrowserThread::IO, 869 FROM_HERE, 870 base::Bind(&Predictor::ResolveList, base::Unretained(this), 871 urls, motivation)); 872 } 873 } 874 875 //----------------------------------------------------------------------------- 876 // Functions to handle saving of hostnames from one session to the next, to 877 // expedite startup times. 878 879 static void SaveDnsPrefetchStateForNextStartupAndTrimOnIOThread( 880 base::ListValue* startup_list, 881 base::ListValue* referral_list, 882 base::WaitableEvent* completion, 883 Predictor* predictor) { 884 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::IO)); 885 886 if (NULL == predictor) { 887 completion->Signal(); 888 return; 889 } 890 predictor->SaveDnsPrefetchStateForNextStartupAndTrim( 891 startup_list, referral_list, completion); 892 } 893 894 void Predictor::SaveStateForNextStartupAndTrim(PrefService* prefs) { 895 if (!predictor_enabled_) 896 return; 897 898 base::WaitableEvent completion(true, false); 899 900 ListPrefUpdate update_startup_list(prefs, prefs::kDnsPrefetchingStartupList); 901 ListPrefUpdate update_referral_list(prefs, 902 prefs::kDnsPrefetchingHostReferralList); 903 if (BrowserThread::CurrentlyOn(BrowserThread::IO)) { 904 SaveDnsPrefetchStateForNextStartupAndTrimOnIOThread( 905 update_startup_list.Get(), 906 update_referral_list.Get(), 907 &completion, 908 this); 909 } else { 910 bool posted = BrowserThread::PostTask( 911 BrowserThread::IO, 912 FROM_HERE, 913 base::Bind( 914 &SaveDnsPrefetchStateForNextStartupAndTrimOnIOThread, 915 update_startup_list.Get(), 916 update_referral_list.Get(), 917 &completion, 918 this)); 919 920 // TODO(jar): Synchronous waiting for the IO thread is a potential source 921 // to deadlocks and should be investigated. See http://crbug.com/78451. 922 DCHECK(posted); 923 if (posted) { 924 // http://crbug.com/124954 925 base::ThreadRestrictions::ScopedAllowWait allow_wait; 926 completion.Wait(); 927 } 928 } 929 } 930 931 void Predictor::SaveDnsPrefetchStateForNextStartupAndTrim( 932 base::ListValue* startup_list, 933 base::ListValue* referral_list, 934 base::WaitableEvent* completion) { 935 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::IO)); 936 if (initial_observer_.get()) 937 initial_observer_->GetInitialDnsResolutionList(startup_list); 938 939 // Do at least one trim at shutdown, in case the user wasn't running long 940 // enough to do any regular trimming of referrers. 941 TrimReferrersNow(); 942 SerializeReferrers(referral_list); 943 944 completion->Signal(); 945 } 946 947 void Predictor::EnablePredictor(bool enable) { 948 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI) || 949 BrowserThread::CurrentlyOn(BrowserThread::IO)); 950 951 if (BrowserThread::CurrentlyOn(BrowserThread::IO)) { 952 EnablePredictorOnIOThread(enable); 953 } else { 954 BrowserThread::PostTask( 955 BrowserThread::IO, 956 FROM_HERE, 957 base::Bind(&Predictor::EnablePredictorOnIOThread, 958 base::Unretained(this), enable)); 959 } 960 } 961 962 void Predictor::EnablePredictorOnIOThread(bool enable) { 963 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::IO)); 964 predictor_enabled_ = enable; 965 } 966 967 void Predictor::PreconnectUrl(const GURL& url, 968 const GURL& first_party_for_cookies, 969 UrlInfo::ResolutionMotivation motivation, 970 int count) { 971 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI) || 972 BrowserThread::CurrentlyOn(BrowserThread::IO)); 973 974 if (BrowserThread::CurrentlyOn(BrowserThread::IO)) { 975 PreconnectUrlOnIOThread(url, first_party_for_cookies, motivation, count); 976 } else { 977 BrowserThread::PostTask( 978 BrowserThread::IO, 979 FROM_HERE, 980 base::Bind(&Predictor::PreconnectUrlOnIOThread, 981 base::Unretained(this), url, first_party_for_cookies, 982 motivation, count)); 983 } 984 } 985 986 void Predictor::PreconnectUrlOnIOThread( 987 const GURL& url, 988 const GURL& first_party_for_cookies, 989 UrlInfo::ResolutionMotivation motivation, 990 int count) { 991 if (motivation == UrlInfo::MOUSE_OVER_MOTIVATED) 992 RecordPreconnectTrigger(url); 993 994 AdviseProxy(url, motivation, true /* is_preconnect */); 995 996 PreconnectOnIOThread(url, 997 first_party_for_cookies, 998 motivation, 999 count, 1000 url_request_context_getter_.get()); 1001 } 1002 1003 void Predictor::RecordPreconnectTrigger(const GURL& url) { 1004 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::IO)); 1005 if (preconnect_usage_) 1006 preconnect_usage_->ObservePreconnect(url); 1007 } 1008 1009 void Predictor::RecordPreconnectNavigationStat( 1010 const std::vector<GURL>& url_chain, 1011 bool is_subresource) { 1012 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::IO)); 1013 1014 if (preconnect_usage_) 1015 preconnect_usage_->ObserveNavigationChain(url_chain, is_subresource); 1016 } 1017 1018 void Predictor::RecordLinkNavigation(const GURL& url) { 1019 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::IO)); 1020 if (preconnect_usage_) 1021 preconnect_usage_->ObserveLinkNavigation(url); 1022 } 1023 1024 void Predictor::PredictFrameSubresources(const GURL& url, 1025 const GURL& first_party_for_cookies) { 1026 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI) || 1027 BrowserThread::CurrentlyOn(BrowserThread::IO)); 1028 if (!predictor_enabled_) 1029 return; 1030 DCHECK_EQ(url.GetWithEmptyPath(), url); 1031 // Add one pass through the message loop to allow current navigation to 1032 // proceed. 1033 if (BrowserThread::CurrentlyOn(BrowserThread::IO)) { 1034 PrepareFrameSubresources(url, first_party_for_cookies); 1035 } else { 1036 BrowserThread::PostTask( 1037 BrowserThread::IO, 1038 FROM_HERE, 1039 base::Bind(&Predictor::PrepareFrameSubresources, 1040 base::Unretained(this), url, first_party_for_cookies)); 1041 } 1042 } 1043 1044 void Predictor::AdviseProxy(const GURL& url, 1045 UrlInfo::ResolutionMotivation motivation, 1046 bool is_preconnect) { 1047 if (!proxy_advisor_) 1048 return; 1049 1050 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI) || 1051 BrowserThread::CurrentlyOn(BrowserThread::IO)); 1052 1053 if (BrowserThread::CurrentlyOn(BrowserThread::IO)) { 1054 AdviseProxyOnIOThread(url, motivation, is_preconnect); 1055 } else { 1056 BrowserThread::PostTask( 1057 BrowserThread::IO, 1058 FROM_HERE, 1059 base::Bind(&Predictor::AdviseProxyOnIOThread, 1060 base::Unretained(this), url, motivation, is_preconnect)); 1061 } 1062 } 1063 1064 enum SubresourceValue { 1065 PRECONNECTION, 1066 PRERESOLUTION, 1067 TOO_NEW, 1068 SUBRESOURCE_VALUE_MAX 1069 }; 1070 1071 void Predictor::PrepareFrameSubresources(const GURL& url, 1072 const GURL& first_party_for_cookies) { 1073 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::IO)); 1074 DCHECK_EQ(url.GetWithEmptyPath(), url); 1075 Referrers::iterator it = referrers_.find(url); 1076 if (referrers_.end() == it) { 1077 // Only when we don't know anything about this url, make 2 connections 1078 // available. We could do this completely via learning (by prepopulating 1079 // the referrer_ list with this expected value), but it would swell the 1080 // size of the list with all the "Leaf" nodes in the tree (nodes that don't 1081 // load any subresources). If we learn about this resource, we will instead 1082 // provide a more carefully estimated preconnection count. 1083 if (preconnect_enabled_) { 1084 PreconnectUrlOnIOThread(url, first_party_for_cookies, 1085 UrlInfo::SELF_REFERAL_MOTIVATED, 2); 1086 } 1087 return; 1088 } 1089 1090 Referrer* referrer = &(it->second); 1091 referrer->IncrementUseCount(); 1092 const UrlInfo::ResolutionMotivation motivation = 1093 UrlInfo::LEARNED_REFERAL_MOTIVATED; 1094 for (Referrer::iterator future_url = referrer->begin(); 1095 future_url != referrer->end(); ++future_url) { 1096 SubresourceValue evalution(TOO_NEW); 1097 double connection_expectation = future_url->second.subresource_use_rate(); 1098 UMA_HISTOGRAM_CUSTOM_COUNTS("Net.PreconnectSubresourceExpectation", 1099 static_cast<int>(connection_expectation * 100), 1100 10, 5000, 50); 1101 future_url->second.ReferrerWasObserved(); 1102 if (preconnect_enabled_ && 1103 connection_expectation > kPreconnectWorthyExpectedValue) { 1104 evalution = PRECONNECTION; 1105 future_url->second.IncrementPreconnectionCount(); 1106 int count = static_cast<int>(std::ceil(connection_expectation)); 1107 if (url.host() == future_url->first.host()) 1108 ++count; 1109 PreconnectUrlOnIOThread(future_url->first, first_party_for_cookies, 1110 motivation, count); 1111 } else if (connection_expectation > kDNSPreresolutionWorthyExpectedValue) { 1112 evalution = PRERESOLUTION; 1113 future_url->second.preresolution_increment(); 1114 UrlInfo* queued_info = AppendToResolutionQueue(future_url->first, 1115 motivation); 1116 if (queued_info) 1117 queued_info->SetReferringHostname(url); 1118 } 1119 UMA_HISTOGRAM_ENUMERATION("Net.PreconnectSubresourceEval", evalution, 1120 SUBRESOURCE_VALUE_MAX); 1121 } 1122 } 1123 1124 void Predictor::OnLookupFinished(LookupRequest* request, const GURL& url, 1125 bool found) { 1126 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::IO)); 1127 1128 LookupFinished(request, url, found); 1129 pending_lookups_.erase(request); 1130 delete request; 1131 1132 StartSomeQueuedResolutions(); 1133 } 1134 1135 void Predictor::LookupFinished(LookupRequest* request, const GURL& url, 1136 bool found) { 1137 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::IO)); 1138 UrlInfo* info = &results_[url]; 1139 DCHECK(info->HasUrl(url)); 1140 if (info->is_marked_to_delete()) { 1141 results_.erase(url); 1142 } else { 1143 if (found) 1144 info->SetFoundState(); 1145 else 1146 info->SetNoSuchNameState(); 1147 } 1148 } 1149 1150 UrlInfo* Predictor::AppendToResolutionQueue( 1151 const GURL& url, 1152 UrlInfo::ResolutionMotivation motivation) { 1153 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::IO)); 1154 DCHECK(url.has_host()); 1155 1156 if (shutdown_) 1157 return NULL; 1158 1159 UrlInfo* info = &results_[url]; 1160 info->SetUrl(url); // Initialize or DCHECK. 1161 // TODO(jar): I need to discard names that have long since expired. 1162 // Currently we only add to the domain map :-/ 1163 1164 DCHECK(info->HasUrl(url)); 1165 1166 if (!info->NeedsDnsUpdate()) { 1167 info->DLogResultsStats("DNS PrefetchNotUpdated"); 1168 return NULL; 1169 } 1170 1171 AdviseProxy(url, motivation, false /* is_preconnect */); 1172 if (proxy_advisor_ && proxy_advisor_->WouldProxyURL(url)) { 1173 info->DLogResultsStats("DNS PrefetchForProxiedRequest"); 1174 return NULL; 1175 } 1176 1177 info->SetQueuedState(motivation); 1178 work_queue_.Push(url, motivation); 1179 StartSomeQueuedResolutions(); 1180 return info; 1181 } 1182 1183 bool Predictor::CongestionControlPerformed(UrlInfo* info) { 1184 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::IO)); 1185 // Note: queue_duration is ONLY valid after we go to assigned state. 1186 if (info->queue_duration() < max_dns_queue_delay_) 1187 return false; 1188 // We need to discard all entries in our queue, as we're keeping them waiting 1189 // too long. By doing this, we'll have a chance to quickly service urgent 1190 // resolutions, and not have a bogged down system. 1191 while (true) { 1192 info->RemoveFromQueue(); 1193 if (work_queue_.IsEmpty()) 1194 break; 1195 info = &results_[work_queue_.Pop()]; 1196 info->SetAssignedState(); 1197 } 1198 return true; 1199 } 1200 1201 void Predictor::StartSomeQueuedResolutions() { 1202 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::IO)); 1203 1204 while (!work_queue_.IsEmpty() && 1205 pending_lookups_.size() < max_concurrent_dns_lookups_) { 1206 const GURL url(work_queue_.Pop()); 1207 UrlInfo* info = &results_[url]; 1208 DCHECK(info->HasUrl(url)); 1209 info->SetAssignedState(); 1210 1211 if (CongestionControlPerformed(info)) { 1212 DCHECK(work_queue_.IsEmpty()); 1213 return; 1214 } 1215 1216 LookupRequest* request = new LookupRequest(this, host_resolver_, url); 1217 int status = request->Start(); 1218 if (status == net::ERR_IO_PENDING) { 1219 // Will complete asynchronously. 1220 pending_lookups_.insert(request); 1221 peak_pending_lookups_ = std::max(peak_pending_lookups_, 1222 pending_lookups_.size()); 1223 } else { 1224 // Completed synchronously (was already cached by HostResolver), or else 1225 // there was (equivalently) some network error that prevents us from 1226 // finding the name. Status net::OK means it was "found." 1227 LookupFinished(request, url, status == net::OK); 1228 delete request; 1229 } 1230 } 1231 } 1232 1233 void Predictor::TrimReferrers() { 1234 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::IO)); 1235 if (!urls_being_trimmed_.empty()) 1236 return; // There is incremental trimming in progress already. 1237 1238 // Check to see if it is time to trim yet. 1239 base::TimeTicks now = base::TimeTicks::Now(); 1240 if (now < next_trim_time_) 1241 return; 1242 next_trim_time_ = now + TimeDelta::FromHours(kDurationBetweenTrimmingsHours); 1243 1244 LoadUrlsForTrimming(); 1245 PostIncrementalTrimTask(); 1246 } 1247 1248 void Predictor::LoadUrlsForTrimming() { 1249 DCHECK(urls_being_trimmed_.empty()); 1250 for (Referrers::const_iterator it = referrers_.begin(); 1251 it != referrers_.end(); ++it) 1252 urls_being_trimmed_.push_back(it->first); 1253 UMA_HISTOGRAM_COUNTS("Net.PredictionTrimSize", urls_being_trimmed_.size()); 1254 } 1255 1256 void Predictor::PostIncrementalTrimTask() { 1257 if (urls_being_trimmed_.empty()) 1258 return; 1259 const TimeDelta kDurationBetweenTrimmingIncrements = 1260 TimeDelta::FromSeconds(kDurationBetweenTrimmingIncrementsSeconds); 1261 base::MessageLoop::current()->PostDelayedTask( 1262 FROM_HERE, 1263 base::Bind(&Predictor::IncrementalTrimReferrers, 1264 weak_factory_->GetWeakPtr(), false), 1265 kDurationBetweenTrimmingIncrements); 1266 } 1267 1268 void Predictor::IncrementalTrimReferrers(bool trim_all_now) { 1269 size_t trim_count = urls_being_trimmed_.size(); 1270 if (!trim_all_now) 1271 trim_count = std::min(trim_count, kUrlsTrimmedPerIncrement); 1272 while (trim_count-- != 0) { 1273 Referrers::iterator it = referrers_.find(urls_being_trimmed_.back()); 1274 urls_being_trimmed_.pop_back(); 1275 if (it == referrers_.end()) 1276 continue; // Defensive code: It got trimmed away already. 1277 if (!it->second.Trim(kReferrerTrimRatio, kDiscardableExpectedValue)) 1278 referrers_.erase(it); 1279 } 1280 PostIncrementalTrimTask(); 1281 } 1282 1283 void Predictor::AdviseProxyOnIOThread(const GURL& url, 1284 UrlInfo::ResolutionMotivation motivation, 1285 bool is_preconnect) { 1286 if (!proxy_advisor_) 1287 return; 1288 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::IO)); 1289 proxy_advisor_->Advise(url, motivation, is_preconnect); 1290 } 1291 1292 // ---------------------- End IO methods. ------------------------------------- 1293 1294 //----------------------------------------------------------------------------- 1295 1296 Predictor::HostNameQueue::HostNameQueue() { 1297 } 1298 1299 Predictor::HostNameQueue::~HostNameQueue() { 1300 } 1301 1302 void Predictor::HostNameQueue::Push(const GURL& url, 1303 UrlInfo::ResolutionMotivation motivation) { 1304 switch (motivation) { 1305 case UrlInfo::STATIC_REFERAL_MOTIVATED: 1306 case UrlInfo::LEARNED_REFERAL_MOTIVATED: 1307 case UrlInfo::MOUSE_OVER_MOTIVATED: 1308 rush_queue_.push(url); 1309 break; 1310 1311 default: 1312 background_queue_.push(url); 1313 break; 1314 } 1315 } 1316 1317 bool Predictor::HostNameQueue::IsEmpty() const { 1318 return rush_queue_.empty() && background_queue_.empty(); 1319 } 1320 1321 GURL Predictor::HostNameQueue::Pop() { 1322 DCHECK(!IsEmpty()); 1323 std::queue<GURL> *queue(rush_queue_.empty() ? &background_queue_ 1324 : &rush_queue_); 1325 GURL url(queue->front()); 1326 queue->pop(); 1327 return url; 1328 } 1329 1330 //----------------------------------------------------------------------------- 1331 // Member definitions for InitialObserver class. 1332 1333 Predictor::InitialObserver::InitialObserver() { 1334 } 1335 1336 Predictor::InitialObserver::~InitialObserver() { 1337 } 1338 1339 void Predictor::InitialObserver::Append(const GURL& url, 1340 Predictor* predictor) { 1341 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::IO)); 1342 1343 // TODO(rlp): Do we really need the predictor check here? 1344 if (NULL == predictor) 1345 return; 1346 if (kStartupResolutionCount <= first_navigations_.size()) 1347 return; 1348 1349 DCHECK(url.SchemeIsHTTPOrHTTPS()); 1350 DCHECK_EQ(url, Predictor::CanonicalizeUrl(url)); 1351 if (first_navigations_.find(url) == first_navigations_.end()) 1352 first_navigations_[url] = base::TimeTicks::Now(); 1353 } 1354 1355 void Predictor::InitialObserver::GetInitialDnsResolutionList( 1356 base::ListValue* startup_list) { 1357 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::IO)); 1358 DCHECK(startup_list); 1359 startup_list->Clear(); 1360 DCHECK_EQ(0u, startup_list->GetSize()); 1361 startup_list->Append( 1362 new base::FundamentalValue(kPredictorStartupFormatVersion)); 1363 for (FirstNavigations::iterator it = first_navigations_.begin(); 1364 it != first_navigations_.end(); 1365 ++it) { 1366 DCHECK(it->first == Predictor::CanonicalizeUrl(it->first)); 1367 startup_list->Append(new StringValue(it->first.spec())); 1368 } 1369 } 1370 1371 void Predictor::InitialObserver::GetFirstResolutionsHtml( 1372 std::string* output) { 1373 DCHECK(BrowserThread::CurrentlyOn(BrowserThread::IO)); 1374 1375 UrlInfo::UrlInfoTable resolution_list; 1376 { 1377 for (FirstNavigations::iterator it(first_navigations_.begin()); 1378 it != first_navigations_.end(); 1379 it++) { 1380 UrlInfo info; 1381 info.SetUrl(it->first); 1382 info.set_time(it->second); 1383 resolution_list.push_back(info); 1384 } 1385 } 1386 UrlInfo::GetHtmlTable(resolution_list, 1387 "Future startups will prefetch DNS records for ", false, output); 1388 } 1389 1390 //----------------------------------------------------------------------------- 1391 // Helper functions 1392 //----------------------------------------------------------------------------- 1393 1394 // static 1395 GURL Predictor::CanonicalizeUrl(const GURL& url) { 1396 if (!url.has_host()) 1397 return GURL::EmptyGURL(); 1398 1399 std::string scheme; 1400 if (url.has_scheme()) { 1401 scheme = url.scheme(); 1402 if (scheme != "http" && scheme != "https") 1403 return GURL::EmptyGURL(); 1404 if (url.has_port()) 1405 return url.GetWithEmptyPath(); 1406 } else { 1407 scheme = "http"; 1408 } 1409 1410 // If we omit a port, it will default to 80 or 443 as appropriate. 1411 std::string colon_plus_port; 1412 if (url.has_port()) 1413 colon_plus_port = ":" + url.port(); 1414 1415 return GURL(scheme + "://" + url.host() + colon_plus_port); 1416 } 1417 1418 void SimplePredictor::InitNetworkPredictor( 1419 PrefService* user_prefs, 1420 PrefService* local_state, 1421 IOThread* io_thread, 1422 net::URLRequestContextGetter* getter) { 1423 // Empty function for unittests. 1424 } 1425 1426 void SimplePredictor::ShutdownOnUIThread() { 1427 SetShutdown(true); 1428 } 1429 1430 } // namespace chrome_browser_net 1431
