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