Adaptively identify URL subresources and pre-resolve hosts via DNS

Use the HTTP "referer" header to identify subresources used during a
page load.  Store that info, and use it when next visiting the referenced
hosts to pre-resolve the (probably) needed subresources.

This set of changes will surely evolve as we see how it plays out
on broader distribution (via histogram measurments), but this should be
the foundation of the change.

In design specs, this was previously referred to as "adaptive correlated
DNS prefetching."

r=mbelshe


Review URL: http://codereview.chromium.org/9168

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@4929 0039d316-1c4b-4281-b951-d872f2087c98

10 files changed, 617 insertions, 157 deletions

diff --git a/chrome/browser/net/dns_global.cc b/chrome/browser/net/dns_global.cc
index 52bddb2a..727af82 100644
--- a/chrome/browser/net/dns_global.cc
+++ b/chrome/browser/net/dns_global.cc
@@ -10,9 +10,10 @@
 #include "base/stats_counters.h"
 #include "base/string_util.h"
 #include "base/values.h"
-#include "chrome/browser/net/dns_host_info.h"
 #include "chrome/browser/browser.h"
 #include "chrome/browser/browser_process.h"
+#include "chrome/browser/net/dns_host_info.h"
+#include "chrome/browser/net/referrer.h"
 #include "chrome/browser/session_startup_pref.h"
 #include "chrome/common/notification_types.h"
 #include "chrome/common/notification_service.h"
@@ -26,6 +27,11 @@ using base::TimeDelta;
 namespace chrome_browser_net {
 
 static void DiscardAllPrefetchState();
+static void DnsMotivatedPrefetch(const std::string& hostname,
+                                 DnsHostInfo::ResolutionMotivation motivation);
+static void DnsPrefetchMotivatedList(
+    const NameList& hostnames,
+    DnsHostInfo::ResolutionMotivation motivation);
 
 //------------------------------------------------------------------------------
 // This section contains all the globally accessable API entry points for the
@@ -64,12 +70,22 @@ void RegisterUserPrefs(PrefService* user_prefs) {
 static DnsMaster* dns_master;
 
 // This API is only used in the browser process.
+// It is called from an IPC message originating in the renderer.  It currently
+// includes both Page-Scan, and Link-Hover prefetching.
+// TODO(jar): Separate out link-hover prefetching, and histogram results
+// separately.
 void DnsPrefetchList(const NameList& hostnames) {
+  DnsPrefetchMotivatedList(hostnames, DnsHostInfo::PAGE_SCAN_MOTIVATED);
+}
+
+static void DnsPrefetchMotivatedList(
+    const NameList& hostnames,
+    DnsHostInfo::ResolutionMotivation motivation) {
   if (!dns_prefetch_enabled)
     return;
   DCHECK(NULL != dns_master);
   if (NULL != dns_master)
-    dns_master->ResolveList(hostnames);
+    dns_master->ResolveList(hostnames, motivation);
 }
 
 // This API is used by the autocomplete popup box (wher URLs are typed).
@@ -78,15 +94,15 @@ void DnsPrefetchUrlString(const url_canon::UTF16String& url_string) {
     return;
   GURL gurl(url_string);
   if (gurl.is_valid()) {
-    DnsPrefetch(gurl.host());
+    DnsMotivatedPrefetch(gurl.host(), DnsHostInfo::OMNIBOX_MOTIVATED);
   }
 }
 
-// This API currently used after translating a url_string.
-void DnsPrefetch(const std::string& hostname) {
+static void DnsMotivatedPrefetch(const std::string& hostname,
+                                 DnsHostInfo::ResolutionMotivation motivation) {
   if (!dns_prefetch_enabled || NULL == dns_master || !hostname.size())
     return;
-  dns_master->Resolve(hostname);
+  dns_master->Resolve(hostname, motivation);
 }
 
 //------------------------------------------------------------------------------
@@ -97,11 +113,20 @@ void DnsPrefetch(const std::string& hostname) {
 //------------------------------------------------------------------------------
 
 // This function determines if there was a saving by prefetching the hostname
-// for which the host_info is supplied.
-static bool AcruePrefetchBenefits(DnsHostInfo* host_info) {
+// for which the navigation_info is supplied.
+static bool AccruePrefetchBenefits(const GURL& referrer,
+                                   DnsHostInfo* navigation_info) {
   if (!dns_prefetch_enabled || NULL == dns_master)
     return false;
-  return dns_master->AcruePrefetchBenefits(host_info);
+  return dns_master->AccruePrefetchBenefits(referrer, navigation_info);
+}
+
+// When we navigate, we may know in advance some other domains that will need to
+// be resolved.  This function initiates those side effects.
+static void NavigatingTo(const std::string& host_name) {
+  if (!dns_prefetch_enabled || NULL == dns_master)
+    return;
+  dns_master->NavigatingTo(host_name);
 }
 
 // The observer class needs to connect starts and finishes of HTTP network
@@ -116,14 +141,17 @@ class PrefetchObserver : public net::DnsResolutionObserver {
   PrefetchObserver();
   ~PrefetchObserver();
 
-  virtual void OnStartResolution(const std::string& name, void* context);
-  virtual void OnFinishResolutionWithStatus(bool was_resolved, void* context);
+  virtual void OnStartResolution(const std::string& host_name,
+                                 void* context);
+  virtual void OnFinishResolutionWithStatus(bool was_resolved,
+                                            const GURL& referrer,
+                                            void* context);
 
   static void DnsGetFirstResolutionsHtml(std::string* output);
   static void SaveStartupListAsPref(PrefService* local_state);
 
  private:
-  static void StartupListAppend(const DnsHostInfo& host_info);
+  static void StartupListAppend(const DnsHostInfo& navigation_info);
 
   // We avoid using member variables to better comply with the style guide.
   // We had permission to instantiate only a very minimal class as a global
@@ -159,49 +187,56 @@ PrefetchObserver::~PrefetchObserver() {
   lock = NULL;
 }
 
-void PrefetchObserver::OnStartResolution(const std::string& name,
+void PrefetchObserver::OnStartResolution(const std::string& host_name,
                                          void* context) {
-  DCHECK_NE(0, name.length());
-  DnsHostInfo host_info;
-  host_info.SetHostname(name);
-  host_info.SetStartedState();
+  DCHECK_NE(0, host_name.length());
+  DnsHostInfo navigation_info;
+  navigation_info.SetHostname(host_name);
+  navigation_info.SetStartedState();
+
+  NavigatingTo(host_name);
 
   AutoLock auto_lock(*lock);
-  (*resolutions)[context] = host_info;
+  (*resolutions)[context] = navigation_info;
 }
 
 void PrefetchObserver::OnFinishResolutionWithStatus(bool was_resolved,
+                                                    const GURL& referrer,
                                                     void* context) {
-  DnsHostInfo host_info;
+  DnsHostInfo navigation_info;
   size_t startup_count;
   {
     AutoLock auto_lock(*lock);
     ObservedResolutionMap::iterator it = resolutions->find(context);
     if (resolutions->end() == it) {
+      DCHECK(false);
       return;
     }
-    host_info = it->second;
+    navigation_info = it->second;
     resolutions->erase(it);
     startup_count = first_resolutions->size();
   }
-  host_info.SetFinishedState(was_resolved);  // Get timing info
-  AcruePrefetchBenefits(&host_info);  // Update prefetch benefit (if any).
+  navigation_info.SetFinishedState(was_resolved);  // Get timing info
+  AccruePrefetchBenefits(referrer, &navigation_info);
   if (kStartupResolutionCount <= startup_count || !was_resolved)
     return;
-  StartupListAppend(host_info);
+  // TODO(jar): Don't add host to our list if it is a non-linked lookup, and
+  // instead rely on Referrers to pull this in automatically with the enclosing
+  // page load.
+  StartupListAppend(navigation_info);
 }
 
 // static
-void PrefetchObserver::StartupListAppend(const DnsHostInfo& host_info) {
+void PrefetchObserver::StartupListAppend(const DnsHostInfo& navigation_info) {
   if (!on_the_record_switch || NULL == dns_master)
     return;
   AutoLock auto_lock(*lock);
   if (kStartupResolutionCount <= first_resolutions->size())
     return;  // Someone just added the last item.
-  std::string host_name = host_info.hostname();
+  std::string host_name = navigation_info.hostname();
   if (first_resolutions->find(host_name) != first_resolutions->end())
     return;  // We already have this hostname listed.
-  (*first_resolutions)[host_name] = host_info;
+  (*first_resolutions)[host_name] = navigation_info;
 }
 
 // static
@@ -327,6 +362,7 @@ void DnsPrefetchGetHtmlInfo(std::string* output) {
     } else {
       dns_master->GetHtmlInfo(output);
       PrefetchObserver::DnsGetFirstResolutionsHtml(output);
+      dns_master->GetHtmlReferrerLists(output);
     }
   }
   output->append("</body></html>");
@@ -425,9 +461,10 @@ void DnsPrefetchHostNamesAtStartup(PrefService* user_prefs,
   }
 
   if (hostnames.size() > 0)
-    DnsPrefetchList(hostnames);
-  else
-    DnsPrefetch(std::string("www.google.com"));  // Start a thread.
+    DnsPrefetchMotivatedList(hostnames, DnsHostInfo::STARTUP_LIST_MOTIVATED);
+  else  // Start a thread.
+    DnsMotivatedPrefetch(std::string("www.google.com"),
+                         DnsHostInfo::STARTUP_LIST_MOTIVATED);
 }
 
 
diff --git a/chrome/browser/net/dns_global.h b/chrome/browser/net/dns_global.h
index 5fa1e1c..3b76f45 100644
--- a/chrome/browser/net/dns_global.h
+++ b/chrome/browser/net/dns_global.h
@@ -23,21 +23,25 @@ namespace chrome_browser_net {
 void InitDnsPrefetch(PrefService* user_prefs);
 void ShutdownDnsPrefetch();
 
-// Global API relating to Prefetching in browser
+//------------------------------------------------------------------------------
+// Global APIs relating to Prefetching in browser
 void EnableDnsPrefetch(bool enable);
 void RegisterPrefs(PrefService* local_state);
 void RegisterUserPrefs(PrefService* user_prefs);
+// Renderer bundles up list and sends to this browser API via IPC.
 void DnsPrefetchList(const NameList& hostnames);
+// This API is used by the autocomplete popup box (as user types).
 void DnsPrefetchUrlString(const url_canon::UTF16String& url_string);
-void DnsPrefetch(const std::string& hostname);
 void DnsPrefetchGetHtmlInfo(std::string* output);
 
+//------------------------------------------------------------------------------
 // Save the hostnames actually used at the start of this session to prefetch
 // during the next startup.
 void SaveHostNamesForNextStartup(PrefService* local_state);
 void DnsPrefetchHostNamesAtStartup(PrefService* user_prefs,
                                    PrefService* local_state);
 
+//------------------------------------------------------------------------------
 // Helper class to handle global init and shutdown.
 class DnsPrefetcherInit {
  public:
diff --git a/chrome/browser/net/dns_host_info.cc b/chrome/browser/net/dns_host_info.cc
index 96251f5..cb11902 100644
--- a/chrome/browser/net/dns_host_info.cc
+++ b/chrome/browser/net/dns_host_info.cc
@@ -64,10 +64,11 @@ void DnsHostInfo::set_cache_expiration(TimeDelta time) {
   kCacheExpirationDuration = time;
 }
 
-void DnsHostInfo::SetQueuedState() {
+void DnsHostInfo::SetQueuedState(ResolutionMotivation motivation) {
   DCHECK(PENDING == state_ || FOUND == state_ || NO_SUCH_NAME == state_);
   state_ = QUEUED;
   queue_duration_ = resolve_duration_ = kNullDuration;
+  SetMotivation(motivation);
   GetDuration();  // Set time_
   DLogResultsStats("DNS Prefetch in queue");
 }
@@ -117,6 +118,7 @@ void DnsHostInfo::SetStartedState() {
   DCHECK(PENDING == state_);
   state_ = STARTED;
   queue_duration_ = resolve_duration_ = TimeDelta();  // 0ms.
+  SetMotivation(NO_PREFETCH_MOTIVATION);
   GetDuration();  // Set time.
 }
 
@@ -128,6 +130,13 @@ void DnsHostInfo::SetFinishedState(bool was_resolved) {
   DLogResultsStats("DNS HTTP Finished");
 }
 
+void DnsHostInfo::SetHostname(const std::string& hostname) {
+  if (hostname != hostname_) {
+    DCHECK(hostname_.size() == 0);  // Not yet initialized.
+    hostname_ = hostname;
+  }
+}
+
 // IsStillCached() guesses if the DNS cache still has IP data,
 // or at least remembers results about "not finding host."
 bool DnsHostInfo::IsStillCached() const {
@@ -153,21 +162,34 @@ bool DnsHostInfo::IsStillCached() const {
   return time_since_resolution < kCacheExpirationDuration;
 }
 
-// Compare the later results, to the previously prefetched info.
-DnsBenefit DnsHostInfo::AcruePrefetchBenefits(DnsHostInfo* later_host_info) {
-  DCHECK(FINISHED == later_host_info->state_
-         || FINISHED_UNRESOLVED == later_host_info->state_);
-  DCHECK(0 == later_host_info->hostname_.compare(hostname_.data()));
+// Compare the actual navigation DNS latency found in navigation_info, to the
+// previously prefetched info.
+DnsBenefit DnsHostInfo::AccruePrefetchBenefits(DnsHostInfo* navigation_info) {
+  DCHECK(FINISHED == navigation_info->state_ ||
+         FINISHED_UNRESOLVED == navigation_info->state_);
+  DCHECK(0 == navigation_info->hostname_.compare(hostname_.data()));
+
   if ((0 == benefits_remaining_.InMilliseconds()) ||
       (FOUND != state_ && NO_SUCH_NAME != state_)) {
+    if (FINISHED == navigation_info->state_)
+      UMA_HISTOGRAM_LONG_TIMES(L"DNS.IndependentNavigation",
+                               navigation_info->resolve_duration_);
+    else
+      UMA_HISTOGRAM_LONG_TIMES(L"DNS.IndependentFailedNavigation",
+                               navigation_info->resolve_duration_);
     return PREFETCH_NO_BENEFIT;
   }
 
-  TimeDelta benefit = benefits_remaining_ - later_host_info->resolve_duration_;
-  later_host_info->benefits_remaining_ = benefits_remaining_;
-  benefits_remaining_ = TimeDelta();  // zero ms.
+  TimeDelta benefit = benefits_remaining_ - navigation_info->resolve_duration_;
+  navigation_info->benefits_remaining_ = benefits_remaining_;
+  benefits_remaining_ = TimeDelta();  // We used up all our benefits here.
+
+  navigation_info->motivation_ = motivation_;
+  if (LEARNED_REFERAL_MOTIVATED == motivation_ ||
+      STATIC_REFERAL_MOTIVATED == motivation_)
+    navigation_info->referring_hostname_ = referring_hostname_;
 
-  if (later_host_info->resolve_duration_ > kMaxNonNetworkDnsLookupDuration) {
+  if (navigation_info->resolve_duration_ > kMaxNonNetworkDnsLookupDuration) {
     // Our precache effort didn't help since HTTP stack hit the network.
     UMA_HISTOGRAM_TIMES(L"DNS.PrefetchCacheEviction", resolve_duration_);
     DLogResultsStats("DNS PrefetchCacheEviction");
@@ -181,8 +203,14 @@ DnsBenefit DnsHostInfo::AcruePrefetchBenefits(DnsHostInfo* later_host_info) {
   }
 
   DCHECK_EQ(FOUND, state_);
-  UMA_HISTOGRAM_LONG_TIMES(L"DNS.PrefetchPositiveHitL", benefit);
-  DLogResultsStats("DNS PrefetchPositiveHit");
+  if (LEARNED_REFERAL_MOTIVATED == motivation_ ||
+      STATIC_REFERAL_MOTIVATED == motivation_) {
+    UMA_HISTOGRAM_TIMES(L"DNS.PrefetchReferredPositiveHit", benefit);
+    DLogResultsStats("DNS PrefetchReferredPositiveHit");
+  } else {
+    UMA_HISTOGRAM_LONG_TIMES(L"DNS.PrefetchPositiveHitL", benefit);
+    DLogResultsStats("DNS PrefetchPositiveHit");
+  }
   return PREFETCH_NAME_FOUND;
 }
 
@@ -208,7 +236,7 @@ static std::string RemoveJs(const std::string& text) {
   size_t length = output.length();
   for (size_t i = 0; i < length; i++) {
     char next = output[i];
-    if (isalnum(next) || isspace(next) || '.' == next)
+    if (isalnum(next) || isspace(next) || '.' == next || '-' == next)
       continue;
     output[i] = '?';
   }
@@ -284,12 +312,14 @@ void DnsHostInfo::GetHtmlTable(const DnsInfoTable host_infos,
   }
 
   const char* row_format = "<tr align=right><td>%s</td>"
-                           "<td>%d</td><td>%d</td><td>%s</td></tr>";
+                           "<td>%d</td><td>%d</td><td>%s</td><td>%s</td></tr>";
 
   output->append("<br><table border=1>");
-  StringAppendF(output, "<tr><th>%s</th><th>%s</th><th>%s</th><th>%s</th></tr>",
-                "Host name", "Applicable Prefetch<br>Time (ms)",
-                "Recent Resolution<br>Time(ms)", "How long ago<br>(HH:MM:SS)");
+  StringAppendF(output,
+      "<tr><th>%s</th><th>%s</th><th>%s</th><th>%s</th><th>%s</th></tr>",
+      "Host name", "Applicable Prefetch<br>Time (ms)",
+      "Recent Resolution<br>Time(ms)", "How long ago<br>(HH:MM:SS)",
+      "Motivation");
 
   // Print bulk of table, and gather stats at same time.
   MinMaxAverage queue, resolve, preresolve, when;
@@ -302,7 +332,8 @@ void DnsHostInfo::GetHtmlTable(const DnsInfoTable host_infos,
                   preresolve.sample((it->benefits_remaining_.InMilliseconds())),
                   resolve.sample((it->resolve_duration_.InMilliseconds())),
                   HoursMinutesSeconds(when.sample(
-                      (current_time - it->time_).InSeconds())).c_str());
+                      (current_time - it->time_).InSeconds())).c_str(),
+                  it->GetAsciiMotivation().c_str());
   }
   // Write min, max, and average summary lines.
   if (host_infos.size() > 2) {
@@ -310,22 +341,22 @@ void DnsHostInfo::GetHtmlTable(const DnsInfoTable host_infos,
     StringAppendF(output, row_format,
                   "<b>---minimum---</b>",
                   preresolve.minimum(), resolve.minimum(),
-                  HoursMinutesSeconds(when.minimum()).c_str());
+                  HoursMinutesSeconds(when.minimum()).c_str(), "");
     StringAppendF(output, row_format,
                   "<b>---average---</b>",
                   preresolve.average(), resolve.average(),
-                  HoursMinutesSeconds(when.average()).c_str());
+                  HoursMinutesSeconds(when.average()).c_str(), "");
     StringAppendF(output, row_format,
                   "<b>standard deviation</b>",
                   preresolve.standard_deviation(),
-                  resolve.standard_deviation(), "n/a");
+                  resolve.standard_deviation(), "n/a", "");
     StringAppendF(output, row_format,
                   "<b>---maximum---</b>",
                   preresolve.maximum(), resolve.maximum(),
-                  HoursMinutesSeconds(when.maximum()).c_str());
+                  HoursMinutesSeconds(when.maximum()).c_str(), "");
     StringAppendF(output, row_format,
                   "<b>-----SUM-----</b>",
-                  preresolve.sum(), resolve.sum(), "n/a");
+                  preresolve.sum(), resolve.sum(), "n/a", "");
   }
   output->append("</table>");
 
@@ -337,5 +368,40 @@ void DnsHostInfo::GetHtmlTable(const DnsInfoTable host_infos,
 
   output->append("<br>");
 }
+
+void DnsHostInfo::SetMotivation(ResolutionMotivation motivation) {
+  motivation_ = motivation;
+  if (motivation < LINKED_MAX_MOTIVATED)
+    was_linked_ = true;
+}
+
+std::string DnsHostInfo::GetAsciiMotivation() const {
+  switch (motivation_) {
+    case MOUSE_OVER_MOTIVATED:
+      return "[mouse-over]";
+
+    case PAGE_SCAN_MOTIVATED:
+      return "[page scan]";
+
+    case OMNIBOX_MOTIVATED:
+      return "[omnibox]";
+
+    case STARTUP_LIST_MOTIVATED:
+      return "[startup list]";
+
+    case NO_PREFETCH_MOTIVATION:
+      return "n/a";
+
+    case STATIC_REFERAL_MOTIVATED:
+      return RemoveJs(referring_hostname_) + "*";
+
+    case LEARNED_REFERAL_MOTIVATED:
+      return RemoveJs(referring_hostname_);
+
+    default:
+      return "";
+  }
+}
+
 }  // namespace chrome_browser_net
 
diff --git a/chrome/browser/net/dns_host_info.h b/chrome/browser/net/dns_host_info.h
index 2f2a51c..50c44f3 100644
--- a/chrome/browser/net/dns_host_info.h
+++ b/chrome/browser/net/dns_host_info.h
@@ -16,6 +16,7 @@
 
 #include "base/logging.h"
 #include "base/time.h"
+#include "googleurl/src/gurl.h"
 
 namespace chrome_browser_net {
 
@@ -32,18 +33,36 @@ enum DnsBenefit {
 
 class DnsHostInfo {
  public:
+  // Reasons for a domain to be resolved.
+  enum ResolutionMotivation {
+    MOUSE_OVER_MOTIVATED,  // Mouse-over link induced resolution.
+    PAGE_SCAN_MOTIVATED,   // Scan of rendered page induced resolution.
+    UNIT_TEST_MOTIVATED,
+    LINKED_MAX_MOTIVATED,    // enum demarkation above motivation from links.
+    OMNIBOX_MOTIVATED,       // Omni-box suggested resolving this.
+    STARTUP_LIST_MOTIVATED,  // Startup list caused this resolution.
+
+    NO_PREFETCH_MOTIVATION,  // Browser navigation info (not prefetch related).
+
+    // The following involve predictive prefetching, triggered by a navigation.
+    // The referring_hostname_ is also set when these are used.
+    // TODO(jar): Support STATIC_REFERAL_MOTIVATED API and integration.
+    STATIC_REFERAL_MOTIVATED,  // External database suggested this resolution.
+    LEARNED_REFERAL_MOTIVATED,  // Prior navigation taught us this resolution.
+  };
+
   enum DnsProcessingState {
-      // When processed by our prefetching system, there are 4 states:
+      // When processed by our prefetching system, the states are:
       PENDING,       // Constructor has completed.
       QUEUED,        // In prefetch queue but not yet assigned to a slave.
       ASSIGNED,      // Currently being processed by a slave.
       ASSIGNED_BUT_MARKED,  // Needs to be deleted as soon as slave is done.
       FOUND,         // DNS prefetch search completed.
       NO_SUCH_NAME,  // DNS prefetch search completed.
-      // When processed by the HTTP network stack, there are 3 states:
-      STARTED,               // Resolution has begun.
-      FINISHED,              // Resolution has completed.
-      FINISHED_UNRESOLVED};  // No resolution found.
+      // When processed by the network stack during navigation, the states are:
+      STARTED,               // Resolution has begun for a navigation.
+      FINISHED,              // Resolution has completed for a navigation.
+      FINISHED_UNRESOLVED};  // No resolution found, so navigation will fail.
   static const base::TimeDelta kMaxNonNetworkDnsLookupDuration;
   // The number of OS cache entries we can guarantee(?) before cache eviction
   // might likely take place.
@@ -60,7 +79,8 @@ class DnsHostInfo {
         resolve_duration_(kNullDuration),
         queue_duration_(kNullDuration),
         benefits_remaining_(),
-        sequence_number_(0) {
+        sequence_number_(0),
+        was_linked_(false) {
   }
 
   ~DnsHostInfo() {}
@@ -74,7 +94,7 @@ class DnsHostInfo {
   static void set_cache_expiration(base::TimeDelta time);
 
   // The prefetching lifecycle.
-  void SetQueuedState();
+  void SetQueuedState(ResolutionMotivation motivation);
   void SetAssignedState();
   void SetPendingDeleteState();
   void SetFoundState();
@@ -83,11 +103,14 @@ class DnsHostInfo {
   void SetStartedState();
   void SetFinishedState(bool was_resolved);
 
-  void SetHostname(const std::string& hostname) {
-    if (hostname != hostname_) {
-      DCHECK(hostname_.size() == 0);  // Not yet initialized.
-      hostname_ = hostname;
-    }
+  // Finish initialization. Must only be called once.
+  void SetHostname(const std::string& hostname);
+
+  bool was_linked() const { return was_linked_; }
+
+  std::string referring_hostname() const { return referring_hostname_; }
+  void SetReferringHostname(const std::string& hostname) {
+    referring_hostname_ = hostname;
   }
 
   bool was_found() const { return FOUND == state_; }
@@ -106,7 +129,7 @@ class DnsHostInfo {
   base::TimeDelta queue_duration() const { return queue_duration_;}
   base::TimeDelta benefits_remaining() const { return benefits_remaining_; }
 
-  DnsBenefit AcruePrefetchBenefits(DnsHostInfo* later_host_info);
+  DnsBenefit AccruePrefetchBenefits(DnsHostInfo* navigation_info);
 
   void DLogResultsStats(const char* message) const;
 
@@ -116,6 +139,22 @@ class DnsHostInfo {
                            std::string* output);
 
  private:
+  base::TimeDelta GetDuration() {
+    base::TimeTicks old_time = time_;
+    time_ = base::TimeTicks::Now();
+    return time_ - old_time;
+  }
+
+  // IsStillCached() guesses if the DNS cache still has IP data.
+  bool IsStillCached() const;
+
+  // Record why we created, or have updated (reqested pre-resolution) of this
+  // instance.
+  void SetMotivation(ResolutionMotivation motivation);
+
+  // Helper function for about:dns printing.
+  std::string GetAsciiMotivation() const;
+
   // The next declaration is non-const to facilitate testing.
   static base::TimeDelta kCacheExpirationDuration;
 
@@ -134,14 +173,16 @@ class DnsHostInfo {
   int sequence_number_;  // Used to calculate potential of cache eviction.
   static int sequence_counter;  // Used to allocate sequence_number_'s.
 
-  base::TimeDelta GetDuration() {
-    base::TimeTicks old_time = time_;
-    time_ = base::TimeTicks::Now();
-    return time_ - old_time;
-  }
+  // Motivation for creation of this instance.
+  ResolutionMotivation motivation_;
 
-  // IsStillCached() guesses if the DNS cache still has IP data.
-  bool IsStillCached() const;
+  // Record if the motivation for prefetching was ever a page-link-scan.
+  bool was_linked_;
+
+  // If this instance holds data about a navigation, we store the referrer.
+  // If this instance hold data about a prefetch, and the prefetch was
+  // instigated by a referrer, we store it here (for use in about:dns).
+  std::string referring_hostname_;
 
   // We put these objects into a std::map, and hence we
   // need some "evil" constructors.
diff --git a/chrome/browser/net/dns_host_info_unittest.cc b/chrome/browser/net/dns_host_info_unittest.cc
index bc04336..79cca93 100644
--- a/chrome/browser/net/dns_host_info_unittest.cc
+++ b/chrome/browser/net/dns_host_info_unittest.cc
@@ -28,7 +28,7 @@ TEST(DnsHostInfoTest, StateChangeTest) {
   // Some tests involve timing function performance, and DLL time can overwhelm
   // test durations (which are considering network vs cache response times).
   info_practice.SetHostname(hostname2);
-  info_practice.SetQueuedState();
+  info_practice.SetQueuedState(DnsHostInfo::UNIT_TEST_MOTIVATED);
   info_practice.SetAssignedState();
   info_practice.SetFoundState();
   PlatformThread::Sleep(500);  // Allow time for DLLs to fully load.
@@ -37,7 +37,7 @@ TEST(DnsHostInfoTest, StateChangeTest) {
   info.SetHostname(hostname1);
 
   EXPECT_TRUE(info.NeedsDnsUpdate(hostname1)) << "error in construction state";
-  info.SetQueuedState();
+  info.SetQueuedState(DnsHostInfo::UNIT_TEST_MOTIVATED);
   EXPECT_FALSE(info.NeedsDnsUpdate(hostname1))
     << "update needed after being queued";
   info.SetAssignedState();
@@ -67,7 +67,7 @@ TEST(DnsHostInfoTest, StateChangeTest) {
 
   // That was a nice life when the object was found.... but next time it won't
   // be found.  We'll sleep for a while, and then come back with not-found.
-  info.SetQueuedState();
+  info.SetQueuedState(DnsHostInfo::UNIT_TEST_MOTIVATED);
   info.SetAssignedState();
   EXPECT_FALSE(info.NeedsDnsUpdate(hostname1))
     << "update needed while assigned to slave";
diff --git a/chrome/browser/net/dns_master.cc b/chrome/browser/net/dns_master.cc
index 0ea83ec..29bf139 100644
--- a/chrome/browser/net/dns_master.cc
+++ b/chrome/browser/net/dns_master.cc
@@ -10,6 +10,7 @@
 
 #include "base/histogram.h"
 #include "base/stats_counters.h"
+#include "base/string_util.h"
 #include "base/thread.h"
 #include "base/win_util.h"
 #include "chrome/browser/net/dns_slave.h"
@@ -18,9 +19,6 @@ using base::TimeDelta;
 
 namespace chrome_browser_net {
 
-//------------------------------------------------------------------------------
-// This section contains methods for the DnsMaster class.
-//------------------------------------------------------------------------------
 DnsMaster::DnsMaster(TimeDelta shutdown_wait_time)
   : slave_count_(0),
     shutdown_(false),
@@ -35,7 +33,9 @@ DnsMaster::DnsMaster(TimeDelta shutdown_wait_time)
 }
 
 // Overloaded Resolve() to take a vector of names.
-void DnsMaster::ResolveList(const NameList& hostnames) {
+void DnsMaster::ResolveList(const NameList& hostnames,
+                            DnsHostInfo::ResolutionMotivation motivation) {
+  bool need_to_signal = false;
   {
     AutoLock auto_lock(lock_);
     if (shutdown_) return;
@@ -52,62 +52,122 @@ void DnsMaster::ResolveList(const NameList& hostnames) {
     for (NameList::const_iterator it = hostnames.begin();
       it < hostnames.end();
          it++) {
-      PreLockedResolve(*it);
+      if (PreLockedResolve(*it, motivation))
+        need_to_signal = true;
     }
   }
-  slaves_have_work_.Signal();
+  if (need_to_signal)
+    slaves_have_work_.Signal();
 }
 
 // Basic Resolve() takes an invidual name, and adds it
 // to the queue.
-void DnsMaster::Resolve(const std::string& hostname) {
+void DnsMaster::Resolve(const std::string& hostname,
+                        DnsHostInfo::ResolutionMotivation motivation) {
   if (0 == hostname.length())
     return;
+  bool need_to_signal = false;
   {
     AutoLock auto_lock(lock_);
     if (shutdown_) return;
     PreLockedCreateNewSlaveIfNeeded();  // Allocate one at a time.
-    PreLockedResolve(hostname);
+    if (PreLockedResolve(hostname, motivation))
+      need_to_signal = true;
   }
-  slaves_have_work_.Signal();
+  if (need_to_signal)
+    slaves_have_work_.Signal();
 }
 
-bool DnsMaster::AcruePrefetchBenefits(DnsHostInfo* host_info) {
-  std::string hostname = host_info->hostname();
-  DnsBenefit benefit;
-  DnsHostInfo prefetched_host_info;
-  {
-    AutoLock auto_lock(lock_);
-    if (results_.find(hostname) == results_.end()) {
-      // Remain under lock to assure static HISTOGRAM constructor is safely run.
-      // Use UMA histogram to quantify potential future gains here.
-      UMA_HISTOGRAM_LONG_TIMES(L"DNS.UnexpectedResolutionL",
-                          host_info->resolve_duration());
-      SIMPLE_STATS_COUNTER(L"DNS.PrefetchCacheOblivious");
-      host_info->DLogResultsStats("DNS PrefetchCacheOblivious");
+bool DnsMaster::AccruePrefetchBenefits(const GURL& referrer,
+                                      DnsHostInfo* navigation_info) {
+  std::string hostname = navigation_info->hostname();
+
+  AutoLock auto_lock(lock_);
+  Results::iterator it = results_.find(hostname);
+  if (it == results_.end()) {
+    // Remain under lock to assure static HISTOGRAM constructor is safely run.
+    // Use UMA histogram to quantify potential future gains here.
+    UMA_HISTOGRAM_LONG_TIMES(L"DNS.UnexpectedResolutionL",
+                             navigation_info->resolve_duration());
+    navigation_info->DLogResultsStats("DNS UnexpectedResolution");
+
+    NonlinkNavigation(referrer, navigation_info);
+    return false;
+  }
+  DnsHostInfo& 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.
+    NonlinkNavigation(referrer, navigation_info);
+  }
+
+  DnsBenefit benefit = prefetched_host_info.AccruePrefetchBenefits(
+      navigation_info);
+  switch (benefit) {
+    case PREFETCH_NAME_FOUND:
+    case PREFETCH_NAME_NONEXISTANT:
+      // Remain under lock to push data.
+      cache_hits_.push_back(*navigation_info);
+      if (referrer_based_prefetch) {
+        std::string& motivating_referrer(
+            prefetched_host_info.referring_hostname());
+        if (!motivating_referrer.empty()) {
+          referrers_[motivating_referrer].AccrueValue(
+              navigation_info->benefits_remaining(), hostname);
+        }
+      }
+      return true;
+
+    case PREFETCH_CACHE_EVICTION:
+      // Remain under lock to push data.
+      cache_eviction_map_[hostname] = *navigation_info;
       return false;
-    }
-    benefit = results_[hostname].AcruePrefetchBenefits(host_info);
-    switch (benefit) {
-      case PREFETCH_NAME_FOUND:
-      case PREFETCH_NAME_NONEXISTANT:
-        // Remain under lock to push data.
-        cache_hits_.push_back(*host_info);
-        return true;
 
-      case PREFETCH_CACHE_EVICTION:
-        // Remain under lock to push data.
-        cache_eviction_map_[hostname] = *host_info;
-        return false;
-      case PREFETCH_NO_BENEFIT:
-        // Prefetch never hit the network. Name was pre-cached.
-        return false;
+    case PREFETCH_NO_BENEFIT:
+      // Prefetch never hit the network. Name was pre-cached.
+      return false;
 
-      default:
-        DCHECK(false);
-        return false;
+    default:
+      DCHECK(false);
+      return false;
+  }
+}
+
+void DnsMaster::NonlinkNavigation(const GURL& referrer,
+                                  DnsHostInfo* navigation_info) {
+  std::string referring_host = referrer.host();
+  if (referring_host.empty() || referring_host == navigation_info->hostname())
+    return;
+
+  referrers_[referring_host].SuggestHost(navigation_info->hostname());
+}
+
+void DnsMaster::NavigatingTo(const std::string& host_name) {
+  bool need_to_signal = false;
+  {
+    AutoLock auto_lock(lock_);
+    Referrers::iterator it = referrers_.find(host_name);
+    if (referrers_.end() == it)
+      return;
+    Referrer* referrer = &(it->second);
+    for (Referrer::iterator future_host = referrer->begin();
+         future_host != referrer->end(); ++future_host) {
+      DnsHostInfo* queued_info = PreLockedResolve(
+          future_host->first,
+          DnsHostInfo::LEARNED_REFERAL_MOTIVATED);
+      if (queued_info) {
+        need_to_signal = true;
+        queued_info->SetReferringHostname(host_name);
+      }
     }
   }
+  if (need_to_signal)
+    slaves_have_work_.Signal();
 }
 
 static char* PluralOptionalHostname(size_t count) {
@@ -119,24 +179,93 @@ static char* PluralOptionalHostname(size_t count) {
 // Provide sort order so all .com's are together, etc.
 struct RightToLeftStringSorter {
   bool operator()(const std::string& left, const std::string& right) const {
-    size_t left_length = left.length();
-    size_t right_length = right.length();
-    const char* left_data = left.data();
-    const char* right_data = right.data();
-    while (true) {
-      if (0 == right_length)
-        return false;
-      if (0 == left_length)
+    if (left == right) return true;
+    size_t left_already_matched = left.size();
+    size_t right_already_matched = right.size();
+
+    // Ensure both strings have characters.
+    if (!left_already_matched) return true;
+    if (!right_already_matched) return false;
+
+    // Watch for trailing dot, so we'll always be safe to go one beyond dot.
+    if ('.' == left[left.size() - 1]) {
+      if ('.' != right[right.size() - 1])
         return true;
-      left_length--;
-      right_length--;
-      int difference = left_data[left_length] - right_data[right_length];
-      if (difference)
-        return difference < 0;
+      // Both have dots at end of string.
+      --left_already_matched;
+      --right_already_matched;
+    } else {
+      if ('.' == right[right.size() - 1])
+        return false;
+    }
+
+    while (1) {
+      if (!left_already_matched) return true;
+      if (!right_already_matched) return false;
+
+      size_t left_length, right_length;
+      size_t left_start = left.find_last_of('.', left_already_matched - 1);
+      if (std::string::npos == left_start) {
+        left_length = left_already_matched;
+        left_already_matched = left_start = 0;
+      } else {
+        left_length = left_already_matched - left_start;
+        left_already_matched = left_start;
+        ++left_start;  // Don't compare the dot.
+      }
+      size_t right_start = right.find_last_of('.', right_already_matched - 1);
+      if (std::string::npos == right_start) {
+        right_length = right_already_matched;
+        right_already_matched = right_start = 0;
+      } else {
+        right_length = right_already_matched - right_start;
+        right_already_matched = right_start;
+        ++right_start;  // Don't compare the dot.
+      }
+
+      int diff = left.compare(left_start, left.size(),
+                              right, right_start, right.size());
+      if (diff > 0) return false;
+      if (diff < 0) return true;
     }
   }
 };
 
+void DnsMaster::GetHtmlReferrerLists(std::string* output) {
+  AutoLock auto_lock(lock_);
+  if (referrers_.empty())
+    return;
+
+  // TODO(jar): Remove any plausible JavaScript from names before displaying.
+
+  typedef std::set<std::string, struct RightToLeftStringSorter> SortedNames;
+  SortedNames sorted_names;
+
+  for (Referrers::iterator it = referrers_.begin();
+       referrers_.end() != it; ++it)
+    sorted_names.insert(it->first);
+
+  output->append("<br><table border>");
+  StringAppendF(output,
+      "<tr><th>%s</th><th>%s</th></tr>",
+      "Host for Page", "Host(s) in Page<br>(benefits in ms)");
+
+  for (SortedNames::iterator it = sorted_names.begin();
+       sorted_names.end() != it; ++it) {
+    Referrer* referrer = &(referrers_[*it]);
+    StringAppendF(output, "<tr align=right><td>%s</td><td>", it->c_str());
+    output->append("<table>");
+    for (Referrer::iterator future_host = referrer->begin();
+         future_host != referrer->end(); ++future_host) {
+      StringAppendF(output, "<tr align=right><td>(%dms)</td><td>%s</td></tr>",
+          static_cast<int>(future_host->second.latency().InMilliseconds()),
+          future_host->first.c_str());
+    }
+    output->append("</table></td></tr>");
+  }
+  output->append("</table>");
+}
+
 void DnsMaster::GetHtmlInfo(std::string* output) {
   // Local lists for calling DnsHostInfo
   DnsHostInfo::DnsInfoTable cache_hits;
@@ -206,7 +335,9 @@ void DnsMaster::GetHtmlInfo(std::string* output) {
       "Prefetching DNS records revealed non-existance for ", brief, output);
 }
 
-void DnsMaster::PreLockedResolve(const std::string& hostname) {
+DnsHostInfo* DnsMaster::PreLockedResolve(
+    const std::string& hostname,
+    DnsHostInfo::ResolutionMotivation motivation) {
   // DCHECK(We have the lock);
   DCHECK(0 != slave_count_);
   DCHECK(0 != hostname.length());
@@ -218,16 +349,14 @@ void DnsMaster::PreLockedResolve(const std::string& hostname) {
 
   DCHECK(info->HasHostname(hostname));
 
-  static StatsCounter count(L"DNS.PrefetchContemplated");
-  count.Increment();
-
   if (!info->NeedsDnsUpdate(hostname)) {
     info->DLogResultsStats("DNS PrefetchNotUpdated");
-    return;
+    return NULL;
   }
 
-  info->SetQueuedState();
+  info->SetQueuedState(motivation);
   name_buffer_.push(hostname);
+  return info;
 }
 
 // GetNextAssignment() is executed on the thread associated with
@@ -364,7 +493,7 @@ bool DnsMaster::ShutdownSlaves() {
     while (0 < slave_count_--) {
       if (0 == thread_ids_[slave_count_]) {  // Thread terminated.
         int result = CloseHandle(thread_handles_[slave_count_]);
-        CHECK(0 != result);
+        CHECK(result);
         thread_handles_[slave_count_] = 0;
         delete slaves_[slave_count_];
         slaves_[slave_count_] = NULL;
@@ -379,6 +508,7 @@ void DnsMaster::DiscardAllResults() {
   // Delete anything listed so far in this session that shows in about:dns.
   cache_eviction_map_.clear();
   cache_hits_.clear();
+  referrers_.clear();
 
 
   // Try to delete anything in our work queue.
diff --git a/chrome/browser/net/dns_master.h b/chrome/browser/net/dns_master.h
index 1da6b4f..4bc61ee 100644
--- a/chrome/browser/net/dns_master.h
+++ b/chrome/browser/net/dns_master.h
@@ -24,6 +24,7 @@
 #include "base/condition_variable.h"
 #include "base/scoped_ptr.h"
 #include "chrome/browser/net/dns_host_info.h"
+#include "chrome/browser/net/referrer.h"
 #include "chrome/common/net/dns.h"
 #include "googleurl/src/url_canon.h"
 
@@ -63,12 +64,28 @@ class DnsMaster {
   void DiscardAllResults();
 
   // Add hostname(s) to the queue for processing by slaves
-  void ResolveList(const NameList& hostnames);
-  void Resolve(const std::string& hostname);
+  void ResolveList(const NameList& hostnames,
+                   DnsHostInfo::ResolutionMotivation motivation);
+  void Resolve(const std::string& hostname,
+               DnsHostInfo::ResolutionMotivation motivation);
 
   // Get latency benefit of the prefetch that we are navigating to.
-  bool AcruePrefetchBenefits(DnsHostInfo* host_info);
+  bool AccruePrefetchBenefits(const GURL& referrer,
+                              DnsHostInfo* navigation_info);
 
+  // Instigate prefetch of any domains we predict will be needed after this
+  // navigation.
+  void NavigatingTo(const std::string& host_name);
+
+  // Record details of a navigation so that we can preresolve the host name
+  // ahead of time the next time the users navigates to the indicated host.
+  void NonlinkNavigation(const GURL& referrer, DnsHostInfo* navigation_info);
+
+  // Dump HTML table containing list of referrers for about:dns.
+  void GetHtmlReferrerLists(std::string* output);
+
+  // Dump the list of currently know referrer domains and related prefetchable
+  // domains.
   void GetHtmlInfo(std::string* output);
 
   // For testing only...
@@ -120,25 +137,36 @@ class DnsMaster {
   void SetSlaveHasTerminated(int slave_index);
 
  private:
-  //----------------------------------------------------------------------------
-  // Internal helper functions
+  // A map that is keyed with the hostnames that we've learned were the cause
+  // of loading additional hostnames.  The list of additional hostnames in held
+  // in a Referrer instance, which is found in this type.
+  typedef std::map<std::string, Referrer> Referrers;
 
   // "PreLocked" means that the caller has already Acquired lock_ in the
   // following method names.
-  void PreLockedResolve(const std::string& hostname);
+  // Queue hostname for resolution.  If queueing was done, return the pointer
+  // to the queued instance, otherwise return NULL.
+  DnsHostInfo* PreLockedResolve(const std::string& hostname,
+                                DnsHostInfo::ResolutionMotivation motivation);
   bool PreLockedCreateNewSlaveIfNeeded();  // Lazy slave processes creation.
 
   // Number of slave processes started early (to help with startup prefetch).
   static const int kSlaveCountMin = 4;
 
+  // Synchronize access to results_, referrers_, and slave control data.
   Lock lock_;
 
   // name_buffer_ holds a list of names we need to look up.
   std::queue<std::string> name_buffer_;
 
-  // results_ contains information progress for existing/prior prefetches.
+  // results_ contains information for existing/prior prefetches.
   Results results_;
 
+  // For each hostname that we might navigate to (that we've "learned about")
+  // we have a Referrer list. Each Referrer list has all hostnames we need to
+  // pre-resolve when there is a navigation to the orginial hostname.
+  Referrers referrers_;
+
   // Signaling slaves to process elements in the queue, or to terminate,
   // is done using ConditionVariables.
   ConditionVariable slaves_have_work_;
diff --git a/chrome/browser/net/dns_master_unittest.cc b/chrome/browser/net/dns_master_unittest.cc
index c843b36..228c764 100644
--- a/chrome/browser/net/dns_master_unittest.cc
+++ b/chrome/browser/net/dns_master_unittest.cc
@@ -197,7 +197,7 @@ TEST(DnsMasterTest, BenefitLookupTest) {
 
   // First only cause a minimal set of threads to start up.
   // Currently we actually start 4 threads when we get called with an array
-  testing_master.ResolveList(names);
+  testing_master.ResolveList(names, DnsHostInfo::PAGE_SCAN_MOTIVATED);
 
   // Wait for some resoultion for each google.
   SPIN_FOR_1_SECOND_OR_UNTIL_TRUE(0 <=
@@ -223,16 +223,16 @@ TEST(DnsMasterTest, BenefitLookupTest) {
 
   // Simulate actual navigation, and acrue the benefit for "helping" the DNS
   // part of the navigation.
-  EXPECT_TRUE(testing_master.AcruePrefetchBenefits(&goog_info));
-  EXPECT_TRUE(testing_master.AcruePrefetchBenefits(&goog2_info));
-  EXPECT_TRUE(testing_master.AcruePrefetchBenefits(&goog3_info));
-  EXPECT_TRUE(testing_master.AcruePrefetchBenefits(&goog4_info));
+  EXPECT_TRUE(testing_master.AccruePrefetchBenefits(GURL(), &goog_info));
+  EXPECT_TRUE(testing_master.AccruePrefetchBenefits(GURL(), &goog2_info));
+  EXPECT_TRUE(testing_master.AccruePrefetchBenefits(GURL(), &goog3_info));
+  EXPECT_TRUE(testing_master.AccruePrefetchBenefits(GURL(), &goog4_info));
 
   // Benefits can ONLY be reported once (for the first navigation).
-  EXPECT_FALSE(testing_master.AcruePrefetchBenefits(&goog_info));
-  EXPECT_FALSE(testing_master.AcruePrefetchBenefits(&goog2_info));
-  EXPECT_FALSE(testing_master.AcruePrefetchBenefits(&goog3_info));
-  EXPECT_FALSE(testing_master.AcruePrefetchBenefits(&goog4_info));
+  EXPECT_FALSE(testing_master.AccruePrefetchBenefits(GURL(), &goog_info));
+  EXPECT_FALSE(testing_master.AccruePrefetchBenefits(GURL(), &goog2_info));
+  EXPECT_FALSE(testing_master.AccruePrefetchBenefits(GURL(), &goog3_info));
+  EXPECT_FALSE(testing_master.AccruePrefetchBenefits(GURL(), &goog4_info));
 
   // Ensure a clean shutdown.
   EXPECT_TRUE(testing_master.ShutdownSlaves());
@@ -260,7 +260,7 @@ TEST(DnsMasterTest, DISABLED_SingleSlaveLookupTest) {
   names.insert(names.end(), bad2);
 
   // First only cause a single thread to start up
-  testing_master.ResolveList(names);
+  testing_master.ResolveList(names, DnsHostInfo::PAGE_SCAN_MOTIVATED);
 
   // Wait for some resoultion for google.
   SPIN_FOR_1_SECOND_OR_UNTIL_TRUE(0 <=
@@ -320,7 +320,7 @@ TEST(DnsMasterTest, DISABLED_MultiThreadedLookupTest) {
 
   // Get all 8 threads running by calling many times before queue is handled.
   for (int i = 0; i < 10; i++) {
-    testing_master.ResolveList(names);
+    testing_master.ResolveList(names, DnsHostInfo::PAGE_SCAN_MOTIVATED);
   }
 
   Sleep(10);  // Allow time for async DNS to get answers.
@@ -363,7 +363,7 @@ TEST(DnsMasterTest, DISABLED_MultiThreadedSpeedupTest) {
   names.insert(names.end(), goog4);
 
   // First cause a lookup using a single thread.
-  testing_master.ResolveList(names);
+  testing_master.ResolveList(names, DnsHostInfo::PAGE_SCAN_MOTIVATED);
 
   // Wait for some resoultion for google.
   SPIN_FOR_1_SECOND_OR_UNTIL_TRUE(0 <=
@@ -383,7 +383,8 @@ TEST(DnsMasterTest, DISABLED_MultiThreadedSpeedupTest) {
   // Get all 8 threads running by calling many times before queue is handled.
   names.clear();
   for (int i = 0; i < 10; i++)
-    testing_master.Resolve(GetNonexistantDomain());
+    testing_master.Resolve(GetNonexistantDomain(),
+                           DnsHostInfo::PAGE_SCAN_MOTIVATED);
 
   // Wait long enough for all the goog's to be resolved.
   // They should all take about the same time, and run in parallel.
diff --git a/chrome/browser/net/referrer.cc b/chrome/browser/net/referrer.cc
new file mode 100644
index 0000000..a4b0812
--- /dev/null
+++ b/chrome/browser/net/referrer.cc
@@ -0,0 +1,61 @@
+// Copyright (c) 2006-2008 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/referrer.h"
+
+#include "base/logging.h"
+
+namespace chrome_browser_net {
+
+void Referrer::SuggestHost(const std::string& host) {
+  if (host.empty())
+    return;
+  if (kMaxSuggestions <= size()) {
+    DeleteLeastUseful();
+    DCHECK(kMaxSuggestions > size());
+  }
+  // Add in the new suggestion.
+  (*this)[host];
+}
+
+void Referrer::DeleteLeastUseful() {
+  std::string least_useful_name;
+  // We use longs for durations because we will use multiplication on them.
+  int64 least_useful_latency;  // Duration in milliseconds.
+  int64 least_useful_lifetime;  // Duration in milliseconds.
+
+  const base::Time kNow(base::Time::Now());  // Avoid multiple calls.
+  for (HostNameMap::iterator it = this->begin(); it != this->end(); ++it) {
+    int64 lifetime = (kNow - it->second.birth_time()).InMilliseconds();
+    int64 latency = it->second.latency().InMilliseconds();
+    if (!least_useful_name.empty()) {
+      if (!latency && !least_useful_latency) {
+        // Older name is less useful.
+        if (lifetime <= least_useful_lifetime)
+          continue;
+      } else {
+        // Compare the ratios latency/lifetime vs.
+        // least_useful_latency/least_useful_lifetime by cross multiplying (to
+        // avoid integer division hassles).  Overflow's won't happen until
+        // both latency and lifetime pass about 49 days.
+        if (latency * least_useful_lifetime >=
+            least_useful_latency * lifetime) {
+          continue;
+        }
+      }
+    }
+    least_useful_name = it->first;
+    least_useful_latency = latency;
+    least_useful_lifetime = lifetime;
+  }
+  erase(least_useful_name);
+}
+
+void Referrer::AccrueValue(const base::TimeDelta& delta,
+                           const std::string host) {
+  DCHECK(this->find(host) != this->end());
+  (*this)[host].AccrueValue(delta);
+}
+
+}  // namespace chrome_browser_net
diff --git a/chrome/browser/net/referrer.h b/chrome/browser/net/referrer.h
new file mode 100644
index 0000000..f0cf40c
--- /dev/null
+++ b/chrome/browser/net/referrer.h
@@ -0,0 +1,92 @@
+// Copyright (c) 2006-2008 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.
+
+// This class helps to remember what domains may be needed to be resolved when a
+// navigation takes place to a given URL.  This information is gathered when a
+// navigation resolution was not foreseen by identifying the referrer field that
+// induced the navigation.  When future navigations take place to known referrer
+// sites, then we automatically pre-resolve the expected set of useful domains.
+
+// All access to this class is performed via the DnsMaster class, and is
+// protected by the its lock.
+
+#ifndef CHROME_BROWSER_NET_REFERRER_H_
+#define CHROME_BROWSER_NET_REFERRER_H_
+
+#include <map>
+#include <string>
+
+#include "base/basictypes.h"
+#include "base/time.h"
+#include "googleurl/src/gurl.h"
+
+namespace chrome_browser_net {
+
+//------------------------------------------------------------------------------
+// For each hostname in a Referrer, we have a ReferrerValue.  It indicates
+// exactly how much value (re: latency reduction) has resulted from having this
+// entry.
+class ReferrerValue {
+ public:
+  ReferrerValue() : birth_time_(base::Time::Now()) {}
+
+  base::TimeDelta latency() const { return latency_; }
+  base::Time birth_time() const { return birth_time_; }
+  void AccrueValue(const base::TimeDelta& delta) { latency_ += delta; }
+ private:
+  base::TimeDelta latency_;  // Accumulated latency savings.
+  const base::Time birth_time_;
+};
+
+//------------------------------------------------------------------------------
+// A list of domain names to pre-resolve. The names are the keys to this map,
+// and the values indicate the amount of benefit derived from having each name
+// around.
+typedef std::map<std::string, ReferrerValue> HostNameMap;
+
+//------------------------------------------------------------------------------
+// There is one Referrer instance for each hostname that has acted as an HTTP
+// referer (note mispelling is intentional) for a domain that was otherwise
+// unexpectedly navgated towards ("unexpected" in the sense that the domain was
+// probably for a subresource of a page, and was not otherwise predictable until
+// the content with the reference arrived).  Most typically, an outer page was a
+// page fetched by the user, and this instance lists names in HostNameMap which
+// are subresources and that were needed to complete the rendering of the outer
+// page.
+class Referrer : public HostNameMap {
+ public:
+  // Add the indicated host to the list of hosts that are resolved via DNS when
+  // the user navigates to this referrer.  Note that if the list is long, an
+  // entry may be discarded to make room for this insertion.
+  void SuggestHost(const std::string& host);
+
+  // Record additional usefulness of having this host name in the list.
+  // Value is expressed as positive latency of amount delta.
+  void AccrueValue(const base::TimeDelta& delta, const std::string host);
+
+ private:
+  // Helper function for pruning list.  Metric for usefulness is "large accrued
+  // value," in the form of latency_ savings associated with a host name.  We
+  // also give credit for a name being newly added, by scalling latency per
+  // lifetime (time since birth).  For instance, when to names have accrued
+  // the same latency_ savings, the older one is less valuable as it didn't
+  // accrue savings as quickly.
+  void Referrer::DeleteLeastUseful();
+
+  // Limit how large our list can get, in case we start make mistakes about
+  // what hostnames are in sub-resources (example: Some advertisments have
+  // a link to the ad agency, and then provide a "surprising" redirect to
+  // the advertised entity, which appears to be a subresource on the page
+  // hosting the ad).
+  static const int kMaxSuggestions = 8;
+
+  // We put these into a std::map<>, so we need copy constructors.
+  // DISALLOW_COPY_AND_ASSIGN(Referrer);
+  // TODO(jar): Consider optimization to use pointers to these instances, and
+  // avoid deep copies during re-alloc of the containing map.
+};
+
+}  // namespace chrome_browser_net
+
+#endif  // CHROME_BROWSER_NET_REFERRER_H_