chrome/browser/net/predictor.cc

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