chrome/browser/net/predictor.cc

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