Support both preconnection, and pre-resolution for subresources...

chrome/browser/net/predictor.cc

 // Copyright (c) 2010 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "chrome/browser/net/predictor.h"
 
 #include <algorithm>
 #include <set>
 #include <sstream>
 
 #include "base/compiler_specific.h"
 #include "base/histogram.h"
 #include "base/stats_counters.h"
 #include "base/string_util.h"
 #include "base/time.h"
 #include "chrome/browser/chrome_thread.h"
 #include "chrome/browser/net/preconnect.h"
 #include "net/base/address_list.h"
 #include "net/base/completion_callback.h"
 #include "net/base/host_port_pair.h"
 #include "net/base/host_resolver.h"
 #include "net/base/net_errors.h"
 #include "net/base/net_log.h"
 
 using base::TimeDelta;
 
 namespace chrome_browser_net {
 
+// static
+const double Predictor::kPreconnectWorthyExpectedValue = 0.7;
+// static
+const double Predictor::kDNSPreresolutionWorthyExpectedValue = 0.2;
+// static
+const double Predictor::kPersistWorthyExpectedValue = 0.1;
+
+
 class Predictor::LookupRequest {
  public:
   LookupRequest(Predictor* predictor,
                 net::HostResolver* host_resolver,
                 const GURL& url)
       : ALLOW_THIS_IN_INITIALIZER_LIST(
           net_callback_(this, &LookupRequest::OnLookupFinished)),
         predictor_(predictor),
         url_(url),
         resolver_(host_resolver) {
@@ skipping 72 matching lines @@
 // Basic Resolve() takes an invidual name, and adds it
 // to the queue.
 void Predictor::Resolve(const GURL& url,
                         UrlInfo::ResolutionMotivation motivation) {
   DCHECK(ChromeThread::CurrentlyOn(ChromeThread::IO));
   if (!url.has_host())
     return;
   AppendToResolutionQueue(url, motivation);
 }
 
-bool Predictor::AccruePrefetchBenefits(const GURL& referrer,
-                                       UrlInfo* navigation_info) {
-  DCHECK(ChromeThread::CurrentlyOn(ChromeThread::IO));
-  GURL url = navigation_info->url();
-  Results::iterator it = results_.find(url);
-  if (it == results_.end()) {
-    // Use UMA histogram to quantify potential future gains here.
-    UMA_HISTOGRAM_LONG_TIMES("DNS.UnexpectedResolutionL",
-                             navigation_info->resolve_duration());
-    navigation_info->DLogResultsStats("DNS UnexpectedResolution");
-
-    LearnFromNavigation(referrer, navigation_info->url());
-    return false;
-  }
-  UrlInfo& prefetched_host_info(it->second);
-
-  // Sometimes a host is used as a subresource by several referrers, so it is
-  // in our list, but was never motivated by a page-link-scan.  In that case, it
-  // really is an "unexpected" navigation, and we should tally it, and augment
-  // our referrers_.
-  bool referrer_based_prefetch = !prefetched_host_info.was_linked();
-  if (referrer_based_prefetch) {
-    // This wasn't the first time this host refered to *some* referrer.
-    LearnFromNavigation(referrer, navigation_info->url());
-  }
-
-  DnsBenefit benefit = prefetched_host_info.AccruePrefetchBenefits(
-      navigation_info);
-  switch (benefit) {
-    case PREFETCH_NAME_FOUND:
-    case PREFETCH_NAME_NONEXISTANT:
-      dns_cache_hits_.push_back(*navigation_info);
-      if (referrer_based_prefetch) {
-        if (referrer.has_host()) {
-          referrers_[referrer].AccrueValue(
-              navigation_info->benefits_remaining(), url);
-        }
-      }
-      return true;
-
-    case PREFETCH_CACHE_EVICTION:
-      cache_eviction_map_[url] = *navigation_info;
-      return false;
-
-    case PREFETCH_NO_BENEFIT:
-      // Prefetch never hit the network. Name was pre-cached.
-      return false;
-
-    default:
-      NOTREACHED();
-      return false;
-  }
-}
-
 void Predictor::LearnFromNavigation(const GURL& referring_url,
                                     const GURL& target_url) {
   DCHECK(ChromeThread::CurrentlyOn(ChromeThread::IO));
   if (referring_url.has_host() &&
       referring_url != target_url) {
     DCHECK(referring_url == referring_url.GetWithEmptyPath());
     referrers_[referring_url].SuggestHost(target_url);
   }
 }
 
-void Predictor::PredictSubresources(const GURL& url) {
-  DCHECK(ChromeThread::CurrentlyOn(ChromeThread::IO));
-  Referrers::iterator it = referrers_.find(url);
-  if (referrers_.end() == it)
-    return;
-  Referrer* referrer = &(it->second);
-  referrer->IncrementUseCount();
-  for (Referrer::iterator future_url = referrer->begin();
-       future_url != referrer->end(); ++future_url) {
-    UrlInfo* queued_info = AppendToResolutionQueue(
-        future_url->first,
-        UrlInfo::LEARNED_REFERAL_MOTIVATED);
-    if (queued_info)
-      queued_info->SetReferringHostname(url);
-  }
-}
+enum SubresourceValue {
+  PRECONNECTION,
+  PRERESOLUTION,
+  TOO_NEW,
+  SUBRESOURCE_VALUE_MAX
+};
 
 void Predictor::PredictFrameSubresources(const GURL& url) {
   DCHECK(ChromeThread::CurrentlyOn(ChromeThread::IO));
   DCHECK(url.GetWithEmptyPath() == url);
   Referrers::iterator it = referrers_.find(url);
   if (referrers_.end() == it)
     return;
   Referrer* referrer = &(it->second);
   referrer->IncrementUseCount();
+  const UrlInfo::ResolutionMotivation motivation =
+      UrlInfo::LEARNED_REFERAL_MOTIVATED;
   for (Referrer::iterator future_url = referrer->begin();
        future_url != referrer->end(); ++future_url) {
-    if (future_url->second.IsPreconnectWorthDoing())
-      Preconnect::PreconnectOnIOThread(future_url->first);
+    SubresourceValue evalution(TOO_NEW);
+    double connection_expectation = future_url->second.subresource_use_rate();
+    UMA_HISTOGRAM_CUSTOM_COUNTS("Net.PreconnectSubresourceExpectation",
+                                static_cast<int>(connection_expectation * 100),
+                                10, 5000, 50);
+    future_url->second.ReferrerWasObserved();
+    if (preconnect_enabled_ &&
+        kPreconnectWorthyExpectedValue < connection_expectation) {
+      evalution = PRECONNECTION;
+      future_url->second.IncrementPreconnectionCount();
+      Preconnect::PreconnectOnIOThread(future_url->first, motivation);
+    } else if (kDNSPreresolutionWorthyExpectedValue < connection_expectation) {
+      evalution = PRERESOLUTION;
+      future_url->second.preresolution_increment();
+      UrlInfo* queued_info = AppendToResolutionQueue(future_url->first,
+                                                     motivation);
+      if (queued_info)
+        queued_info->SetReferringHostname(url);
+    }
+    UMA_HISTOGRAM_ENUMERATION("Net.PreconnectSubresourceEval", evalution,
+                              SUBRESOURCE_VALUE_MAX);
   }
 }
 
 // Provide sort order so all .com's are together, etc.
 struct RightToLeftStringSorter {
-  bool operator()(const net::HostPortPair& left,
-                  const net::HostPortPair& right) const {
-    return string_compare(left.host(), right.host());
-  }
   bool operator()(const GURL& left,
                   const GURL& right) const {
     return string_compare(left.host(), right.host());
   }
 
   static bool string_compare(const std::string& left_host,
                              const std::string right_host) {
     if (left_host == right_host) return true;
     size_t left_already_matched = left_host.size();
     size_t right_already_matched = right_host.size();
@@ skipping 61 matching lines @@
   for (Referrers::iterator it = referrers_.begin();
        referrers_.end() != it; ++it)
     sorted_names.insert(it->first);
 
   output->append("<br><table border>");
   output->append(
       "<tr><th>Host for Page</th>"
       "<th>Page Load<br>Count</th>"
       "<th>Subresource<br>Navigations</th>"
       "<th>Subresource<br>PreConnects</th>"
+      "<th>Subresource<br>PreResolves</th>"
       "<th>Expected<br>Connects</th>"
-      "<th>DNS<br>Savings</th>"
       "<th>Subresource Spec</th></tr>");
 
   for (SortedNames::iterator it = sorted_names.begin();
        sorted_names.end() != it; ++it) {
     Referrer* referrer = &(referrers_[*it]);
     bool first_set_of_futures = true;
     for (Referrer::iterator future_url = referrer->begin();
          future_url != referrer->end(); ++future_url) {
       output->append("<tr align=right>");
       if (first_set_of_futures)
         StringAppendF(output, "<td rowspan=%d>%s</td><td rowspan=%d>%d</td>",
                       static_cast<int>(referrer->size()),
                       it->spec().c_str(),
                       static_cast<int>(referrer->size()),
                       static_cast<int>(referrer->use_count()));
       first_set_of_futures = false;
       StringAppendF(output,
-          "<td>%d</td><td>%d</td><td>%2.3f</td><td>%dms</td><td>%s</td></tr>",
+          "<td>%d</td><td>%d</td><td>%d</td><td>%2.3f</td><td>%s</td></tr>",
           static_cast<int>(future_url->second.navigation_count()),
           static_cast<int>(future_url->second.preconnection_count()),
+          static_cast<int>(future_url->second.preresolution_count()),
           static_cast<double>(future_url->second.subresource_use_rate()),
-          static_cast<int>(future_url->second.latency().InMilliseconds()),
           future_url->first.spec().c_str());
     }
   }
   output->append("</table>");
 }
 
 void Predictor::GetHtmlInfo(std::string* output) {
   DCHECK(ChromeThread::CurrentlyOn(ChromeThread::IO));
   // Local lists for calling UrlInfo
-  UrlInfo::DnsInfoTable cache_hits;
-  UrlInfo::DnsInfoTable cache_evictions;
-  UrlInfo::DnsInfoTable name_not_found;
-  UrlInfo::DnsInfoTable network_hits;
-  UrlInfo::DnsInfoTable already_cached;
+  UrlInfo::UrlInfoTable name_not_found;
+  UrlInfo::UrlInfoTable name_preresolved;
 
   // Get copies of all useful data.
-  typedef std::map<GURL, UrlInfo, RightToLeftStringSorter>
-      Snapshot;
-  Snapshot snapshot;
-  {
-    // UrlInfo supports value semantics, so we can do a shallow copy.
-    for (Results::iterator it(results_.begin()); it != results_.end(); it++) {
-      snapshot[it->first] = it->second;
-    }
-    for (Results::iterator it(cache_eviction_map_.begin());
-         it != cache_eviction_map_.end();
-         it++) {
-      cache_evictions.push_back(it->second);
-    }
-    // Reverse list as we copy cache hits, so that new hits are at the top.
-    size_t index = dns_cache_hits_.size();
-    while (index > 0) {
-      index--;
-      cache_hits.push_back(dns_cache_hits_[index]);
-    }
-  }
+  typedef std::map<GURL, UrlInfo, RightToLeftStringSorter> SortedUrlInfo;
+  SortedUrlInfo snapshot;
+  // UrlInfo supports value semantics, so we can do a shallow copy.
+  for (Results::iterator it(results_.begin()); it != results_.end(); it++)
+    snapshot[it->first] = it->second;
 
   // Partition the UrlInfo's into categories.
-  for (Snapshot::iterator it(snapshot.begin()); it != snapshot.end(); it++) {
+  for (SortedUrlInfo::iterator it(snapshot.begin());
+       it != snapshot.end(); it++) {
     if (it->second.was_nonexistant()) {
       name_not_found.push_back(it->second);
       continue;
     }
     if (!it->second.was_found())
       continue;  // Still being processed.
-    if (TimeDelta() != it->second.benefits_remaining()) {
-      network_hits.push_back(it->second);  // With no benefit yet.
-      continue;
-    }
-    if (UrlInfo::kMaxNonNetworkDnsLookupDuration >
-      it->second.resolve_duration()) {
-      already_cached.push_back(it->second);
-      continue;
-    }
-    // Remaining case is where prefetch benefit was significant, and was used.
-    // Since we shot those cases as historical hits, we won't bother here.
+    name_preresolved.push_back(it->second);
   }
 
   bool brief = false;
 #ifdef NDEBUG
   brief = true;
 #endif  // NDEBUG
 
   // Call for display of each table, along with title.
-  UrlInfo::GetHtmlTable(cache_hits,
-      "Prefetching DNS records produced benefits for ", false, output);
-  UrlInfo::GetHtmlTable(cache_evictions,
-      "Cache evictions negated DNS prefetching benefits for ", brief, output);
-  UrlInfo::GetHtmlTable(network_hits,
-      "Prefetching DNS records was not yet beneficial for ", brief, output);
-  UrlInfo::GetHtmlTable(already_cached,
-      "Previously cached resolutions were found for ", brief, output);
+  UrlInfo::GetHtmlTable(name_preresolved,
+      "Preresolution DNS records performed for ", brief, output);
   UrlInfo::GetHtmlTable(name_not_found,
-      "Prefetching DNS records revealed non-existance for ", brief, output);
+      "Preresolving DNS records revealed non-existance for ", brief, output);
 }
 
 UrlInfo* Predictor::AppendToResolutionQueue(
     const GURL& url,
     UrlInfo::ResolutionMotivation motivation) {
   DCHECK(ChromeThread::CurrentlyOn(ChromeThread::IO));
   DCHECK(url.has_host());
 
   if (shutdown_)
     return NULL;
@@ skipping 88 matching lines @@
     if (found)
       info->SetFoundState();
     else
       info->SetNoSuchNameState();
   }
 }
 
 void Predictor::DiscardAllResults() {
   DCHECK(ChromeThread::CurrentlyOn(ChromeThread::IO));
   // Delete anything listed so far in this session that shows in about:dns.
-  cache_eviction_map_.clear();
-  dns_cache_hits_.clear();
   referrers_.clear();
 
 
   // Try to delete anything in our work queue.
   while (!work_queue_.IsEmpty()) {
     // Emulate processing cycle as though host was not found.
     GURL url = work_queue_.Pop();
     UrlInfo* info = &results_[url];
     DCHECK(info->HasUrl(url));
     info->SetAssignedState();
@@ skipping 30 matching lines @@
        it != referrers_.end(); ++it)
     urls.push_back(it->first);
   for (size_t i = 0; i < urls.size(); ++i)
     if (!referrers_[urls[i]].Trim())
       referrers_.erase(urls[i]);
 }
 
 void Predictor::SerializeReferrers(ListValue* referral_list) {
   DCHECK(ChromeThread::CurrentlyOn(ChromeThread::IO));
   referral_list->Clear();
-  referral_list->Append(new FundamentalValue(DNS_REFERRER_VERSION));
+  referral_list->Append(new FundamentalValue(PREDICTOR_REFERRER_VERSION));
   for (Referrers::const_iterator it = referrers_.begin();
        it != referrers_.end(); ++it) {
     // Serialize the list of subresource names.
     Value* subresource_list(it->second.Serialize());
 
     // Create a list for each referer.
     ListValue* motivator(new ListValue);
     motivator->Append(new StringValue(it->first.spec()));
     motivator->Append(subresource_list);
 
     referral_list->Append(motivator);
   }
 }
 
 void Predictor::DeserializeReferrers(const ListValue& referral_list) {
   DCHECK(ChromeThread::CurrentlyOn(ChromeThread::IO));
   int format_version = -1;
   if (referral_list.GetSize() > 0 &&
       referral_list.GetInteger(0, &format_version) &&
-      format_version == DNS_REFERRER_VERSION) {
+      format_version == PREDICTOR_REFERRER_VERSION) {
     for (size_t i = 1; i < referral_list.GetSize(); ++i) {
       ListValue* motivator;
       if (!referral_list.GetList(i, &motivator)) {
         NOTREACHED();
         return;
       }
       std::string motivating_url_spec;
       if (!motivator->GetString(0, &motivating_url_spec)) {
         NOTREACHED();
         return;
@@ skipping 41 matching lines @@
 GURL Predictor::HostNameQueue::Pop() {
   DCHECK(!IsEmpty());
   std::queue<GURL> *queue(rush_queue_.empty() ? &background_queue_
                                               : &rush_queue_);
   GURL url(queue->front());
   queue->pop();
   return url;
 }
 
 }  // namespace chrome_browser_net