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