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