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