Adds speculative prefetching of resources.

chrome/browser/predictors/resource_prefetch_predictor.cc

 // Copyright (c) 2012 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/predictors/resource_prefetch_predictor.h"
 
 #include <map>
 #include <set>
 #include <utility>
 
 #include "base/command_line.h"
 #include "base/metrics/histogram.h"
 #include "base/stl_util.h"
 #include "base/time.h"
 #include "chrome/browser/history/history.h"
 #include "chrome/browser/history/history_notifications.h"
 #include "chrome/browser/history/in_memory_database.h"
 #include "chrome/browser/history/url_database.h"
 #include "chrome/browser/predictors/predictor_database.h"
 #include "chrome/browser/predictors/predictor_database_factory.h"
+#include "chrome/browser/predictors/resource_prefetcher_manager.h"
 #include "chrome/browser/prerender/prerender_field_trial.h"
 #include "chrome/browser/profiles/profile.h"
 #include "chrome/common/chrome_notification_types.h"
 #include "chrome/common/chrome_switches.h"
 #include "chrome/common/url_constants.h"
 #include "content/public/browser/browser_thread.h"
 #include "content/public/browser/load_from_memory_cache_details.h"
 #include "content/public/browser/navigation_controller.h"
 #include "content/public/browser/notification_service.h"
 #include "content/public/browser/notification_source.h"
@@ skipping 30 matching lines @@
   RESOURCE_STATUS_URL_TOO_LONG = 16,
   RESOURCE_STATUS_NOT_CACHEABLE = 32,
   RESOURCE_STATUS_HEADERS_MISSING = 64,
   RESOURCE_STATUS_MAX = 128,
 };
 
 }  // namespace
 
 namespace predictors {
 
-ResourcePrefetchPredictor::Config::Config()
-    : max_navigation_lifetime_seconds(60),
-      max_urls_to_track(500),
-      min_url_visit_count(3),
-      max_resources_per_entry(50),
-      max_consecutive_misses(3),
-      num_resources_assumed_prefetched(25) {
-}
-
 ResourcePrefetchPredictor::URLRequestSummary::URLRequestSummary()
     : resource_type(ResourceType::LAST_TYPE),
       was_cached(false) {
 }
 
 ResourcePrefetchPredictor::URLRequestSummary::URLRequestSummary(
     const URLRequestSummary& other)
       : navigation_id(other.navigation_id),
         resource_url(other.resource_url),
         resource_type(other.resource_type),
         mime_type(other.mime_type),
         was_cached(other.was_cached) {
 }
 
 ResourcePrefetchPredictor::URLRequestSummary::~URLRequestSummary() {
 }
 
 ResourcePrefetchPredictor::UrlTableCacheValue::UrlTableCacheValue() {
 }
 
 ResourcePrefetchPredictor::UrlTableCacheValue::~UrlTableCacheValue() {
 }
 
 ResourcePrefetchPredictor::ResourcePrefetchPredictor(
-    const Config& config,
+    const ResourcePrefetchPredictorConfig& config,
     Profile* profile)
     : profile_(profile),
       config_(config),
       initialization_state_(NOT_INITIALIZED),
       tables_(PredictorDatabaseFactory::GetForProfile(
-          profile)->resource_prefetch_tables()) {
+          profile)->resource_prefetch_tables()),
+      results_map_deleter_(&results_map_) {
   CHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
 }
 
 ResourcePrefetchPredictor::~ResourcePrefetchPredictor() {
-}
-
-// static
-bool ResourcePrefetchPredictor::IsEnabled(Profile* profile) {
-  return prerender::IsSpeculativeResourcePrefetchingLearningEnabled(profile);
+  prefetch_manager_->ShutdownOnUIThread();
+  prefetch_manager_ = NULL;
 }
 
 void ResourcePrefetchPredictor::LazilyInitialize() {
   CHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
 
   DCHECK_EQ(initialization_state_, NOT_INITIALIZED);
   initialization_state_ = INITIALIZING;
 
   // Request the in-memory database from the history to force it to load so it's
   // available as soon as possible.
@@ skipping 156 matching lines @@
 void ResourcePrefetchPredictor::RecordURLRequest(
     const URLRequestSummary& request) {
   CHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
 
   if (initialization_state_ == NOT_INITIALIZED) {
     LazilyInitialize();
     return;
   } else if (initialization_state_ != INITIALIZED) {
     return;
   }
-  DCHECK_EQ(INITIALIZED, initialization_state_);
 
   CHECK_EQ(request.resource_type, ResourceType::MAIN_FRAME);
   OnMainFrameRequest(request);
 }
 
 void ResourcePrefetchPredictor::RecordUrlResponse(
     const URLRequestSummary& response) {
   CHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
   if (initialization_state_ != INITIALIZED)
     return;
@@ skipping 18 matching lines @@
     const URLRequestSummary& request) {
   CHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
   DCHECK_EQ(INITIALIZED, initialization_state_);
 
   // Cleanup older navigations.
   CleanupAbandonedNavigations(request.navigation_id);
 
   // New empty navigation entry.
   inflight_navigations_.insert(std::make_pair(
       request.navigation_id, std::vector<URLRequestSummary>()));
+
+  // If prefetching is enabled, and we can prefetch something, start
+  // prefetching.
+  if (!prefetch_manager_.get())
+    return;
+
+  const GURL& main_frame_url = request.navigation_id.main_frame_url;
+  const UrlTableCacheMap::const_iterator value_iter = url_table_cache_.find(
+      main_frame_url);
+  if (value_iter == url_table_cache_.end())
+    return;
+
+  const UrlTableCacheValue& value = value_iter->second;
+
+  scoped_ptr<ResourcePrefetcher::RequestVector> requests(
+      new ResourcePrefetcher::RequestVector);
+  for (UrlTableRowVector::const_iterator it = value.rows.begin();
+       it != value.rows.end(); ++it) {
+    float confidence = static_cast<float>(it->number_of_hits) /
+        (it->number_of_hits + it->number_of_misses);
+    if (confidence < config_.min_resource_confidence_to_trigger_prefetch ||
+        it->number_of_hits < config_.min_resource_hits_to_trigger_prefetch) {
+      continue;
+    }
+
+    ResourcePrefetcher::Request* req = new ResourcePrefetcher::Request(
+        it->resource_url);
+    requests->push_back(req);
+  }
+
+  if (requests->empty())
+    return;
+
+  BrowserThread::PostTask(BrowserThread::IO, FROM_HERE,
+      base::Bind(&ResourcePrefetcherManager::MaybeAddPrefetch,
+                 prefetch_manager_,
+                 request.navigation_id,
+                 base::Passed(requests.Pass())));

[dominich, 2012/08/02 15:00:50]

I believe you can use &requests instead of calling Pass(). Would remove one set
of parentheses.

[Shishir, 2012/08/02 22:06:54]

Done.

 }
 
 void ResourcePrefetchPredictor::OnMainFrameResponse(
     const URLRequestSummary& response) {
   CHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
+  if (initialization_state_ != INITIALIZED)
+    return;
 
-  // TODO(shishir): The prefreshing will be stopped here.
+  if (prefetch_manager_.get())
+    BrowserThread::PostTask(
+        BrowserThread::IO, FROM_HERE,
+        base::Bind(&ResourcePrefetcherManager::MaybeRemovePrefetch,
+                   prefetch_manager_,
+                   response.navigation_id));
 }
 
 void ResourcePrefetchPredictor::OnMainFrameRedirect(
     const URLRequestSummary& response) {
   CHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
 
   inflight_navigations_.erase(response.navigation_id);
 }
 
 void ResourcePrefetchPredictor::OnSubresourceResponse(
@@ skipping 36 matching lines @@
     if (it->first.IsSameRenderer(navigation_id) ||
         (time_now - it->first.creation_time > max_navigation_age)) {
       inflight_navigations_.erase(it++);
       UMA_HISTOGRAM_ENUMERATION("ResourcePrefetchPredictor.NavigationStatus",
                                 NAVIGATION_STATUS_ABANDONED,
                                 NAVIGATION_STATUS_COUNT);
     } else {
       ++it;
     }
   }
+  for (ResultsMap::iterator it = results_map_.begin();
+       it != results_map_.end();) {
+    if (it->first.IsSameRenderer(navigation_id) ||
+        (time_now - it->first.creation_time > max_navigation_age)) {
+      delete it->second;
+      results_map_.erase(it++);
+    } else {
+      ++it;
+    }
+  }
 }
 
 void ResourcePrefetchPredictor::Observe(
     int type,
     const content::NotificationSource& source,
     const content::NotificationDetails& details) {
   CHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
 
   switch (type) {
     case content::NOTIFICATION_LOAD_COMPLETED_MAIN_FRAME: {
@@ skipping 42 matching lines @@
         DeleteUrls(urls_deleted_details->rows);
       break;
     }
 
     default:
       NOTREACHED() << "Unexpected notification observed.";
       break;
   }
 }
 
+void ResourcePrefetchPredictor::FinishedPrefetchForNavigation(
+    const NavigationID& navigation_id,
+    scoped_ptr<ResourcePrefetcher::RequestVector> requests) {
+  CHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
+
+  // Add the results to the results map.
+  ResourcePrefetcher::RequestVector* req = requests.release();
+  if (!results_map_.insert(std::make_pair(navigation_id, req)).second) {
+    DLOG(FATAL) << "Returning results for existing navigation.";
+    delete req;
+  }
+}
+
 void ResourcePrefetchPredictor::OnHistoryAndCacheLoaded() {
   CHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
   DCHECK_EQ(initialization_state_, INITIALIZING);
 
   // Update the data with last visit info from in memory history db.
   HistoryService* history_service =
       profile_->GetHistoryService(Profile::EXPLICIT_ACCESS);
   DCHECK(history_service);
   history::URLDatabase* url_db = history_service->InMemoryDatabase();
   if (url_db) {
@@ skipping 22 matching lines @@
   notification_registrar_.Add(this,
                               content::NOTIFICATION_LOAD_COMPLETED_MAIN_FRAME,
                               content::NotificationService::AllSources());
   notification_registrar_.Add(this,
                               chrome::NOTIFICATION_HISTORY_URLS_DELETED,
                               content::Source<Profile>(profile_));
 
   // TODO(shishir): Maybe listen for notifications for navigation being
   // abandoned and cleanup the inflight_navigations_.
 
+  // Initialize the prefetch manager only if prefetching is enabled.
+  if (prerender::IsSpeculativeResourcePrefetchingEnabled(profile_)) {
+    prefetch_manager_ = new ResourcePrefetcherManager(
+        this, config_, profile_->GetRequestContext());
+  }
+
   initialization_state_ = INITIALIZED;
 }
 
 bool ResourcePrefetchPredictor::ShouldTrackUrl(const GURL& url) {
   if (url_table_cache_.find(url) != url_table_cache_.end())
     return true;
 
   HistoryService* history_service =
       profile_->GetHistoryService(Profile::EXPLICIT_ACCESS);
   DCHECK(history_service);
@@ skipping 16 matching lines @@
                               NAVIGATION_STATUS_COMPLETE_ABANDONED,
                               NAVIGATION_STATUS_COUNT);
     return;
   }
 
   UMA_HISTOGRAM_ENUMERATION("ResourcePrefetchPredictor.NavigationStatus",
                             NAVIGATION_STATUS_COMPLETE,
                             NAVIGATION_STATUS_COUNT);
 
   // Report any stats.
-  MaybeReportAccuracyStats(navigation_id);
+  if (prefetch_manager_.get()) {
+    MaybeReportAccuracyStats(navigation_id);
+  } else {
+    MaybeReportSimulatedAccuracyStats(navigation_id);
+  }
 
   // Update the URL table.
   const GURL& main_frame_url = navigation_id.main_frame_url;
   if (ShouldTrackUrl(main_frame_url))
     LearnUrlNavigation(main_frame_url, inflight_navigations_[navigation_id]);
 
   // Remove the navigation.
   inflight_navigations_.erase(navigation_id);
+  delete results_map_[navigation_id];
+  results_map_.erase(navigation_id);
 }
 
 void ResourcePrefetchPredictor::LearnUrlNavigation(
     const GURL& main_frame_url,
     const std::vector<URLRequestSummary>& new_resources) {
   CHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
 
   if (url_table_cache_.find(main_frame_url) == url_table_cache_.end()) {
-    if (url_table_cache_.size() >= config_.max_urls_to_track)
+    if (static_cast<int>(url_table_cache_.size()) >= config_.max_urls_to_track)

[dominich, 2012/08/02 15:00:50]

if it makes sense for this to be size_t that's fine.

[Shishir, 2012/08/02 22:06:54]

Lets leave it at int to be consistent through out.

       RemoveAnEntryFromUrlDB();
 
     url_table_cache_[main_frame_url].last_visit = base::Time::Now();
     int new_resources_size = static_cast<int>(new_resources.size());
     std::set<GURL> resources_seen;
     for (int i = 0; i < new_resources_size; ++i) {
       if (resources_seen.find(new_resources[i].resource_url) !=
           resources_seen.end()) {
         continue;
       }
@@ skipping 107 matching lines @@
   }
   url_table_cache_.erase(url_to_erase);
 
   std::vector<GURL> urls_to_delete(1, url_to_erase);
   BrowserThread::PostTask(BrowserThread::DB, FROM_HERE,
       base::Bind(&ResourcePrefetchPredictorTables::DeleteRowsForUrls,
                  tables_,
                  urls_to_delete));
 }
 
-void ResourcePrefetchPredictor::MaybeReportAccuracyStats(
+void ResourcePrefetchPredictor::MaybeReportSimulatedAccuracyStats(
     const NavigationID& navigation_id) const {
   const GURL& main_frame_url = navigation_id.main_frame_url;
   DCHECK(inflight_navigations_.find(navigation_id) !=
          inflight_navigations_.end());
 
   bool have_predictions_for_url =
       url_table_cache_.find(main_frame_url) != url_table_cache_.end();
   UMA_HISTOGRAM_BOOLEAN("ResourcePrefetchPredictor.HavePredictionsForUrl",
                         have_predictions_for_url);
   if (!have_predictions_for_url)
@@ skipping 29 matching lines @@
       "ResourcePrefetchPredictor.PredictedPrefetchMisses",
       prefetch_missed * 100.0 / num_assumed_prefetched);
   UMA_HISTOGRAM_PERCENTAGE(
       "ResourcePrefetchPredictor.PredictedPrefetchFromCache",
       prefetch_cached * 100.0 / num_assumed_prefetched);
   UMA_HISTOGRAM_PERCENTAGE(
       "ResourcePrefetchPredictor.PredictedPrefetchFromNetwork",
       prefetch_network * 100.0 / num_assumed_prefetched);
 }
 
+void ResourcePrefetchPredictor::MaybeReportAccuracyStats(
+    const NavigationID& navigation_id) {
+  NavigationMap::iterator nav_it = inflight_navigations_.find(navigation_id);

[dominich, 2012/08/02 15:00:50]

no need to do this before checking have_prefetch_results. Ie, move down to 814.

[Shishir, 2012/08/02 22:06:54]

This is a correctness DCHECK, so I would prefer to have it at the start of the
function.

+  DCHECK(nav_it != inflight_navigations_.end());
+
+  ResultsMap::iterator results_it = results_map_.find(navigation_id);
+  bool have_prefetch_results = results_it != results_map_.end();
+  UMA_HISTOGRAM_BOOLEAN("ResourcePrefetchPredictor.HavePrefetchResults",
+                        have_prefetch_results);
+  if (!have_prefetch_results)
+    return;
+
+  // Annotate the results.
+  const std::vector<URLRequestSummary>& actual = nav_it->second;
+  ResourcePrefetcher::RequestVector* prefetched = results_it->second;
+
+  std::map<GURL, bool> actual_resources;
+  for (std::vector<URLRequestSummary>::const_iterator it = actual.begin();
+       it != actual.end(); ++it) {
+    actual_resources[it->resource_url] = it->was_cached;
+  }
+
+  int prefetch_cancelled = 0, prefetch_failed = 0, prefetch_not_started = 0;
+  // 'a_' -> actual, 'p_' -> predicted.
+  int p_cache_a_cache = 0, p_cache_a_network = 0, p_cache_a_notused = 0,
+      p_network_a_cache = 0, p_network_a_network = 0, p_network_a_notused = 0;
+
+  for (ResourcePrefetcher::RequestVector::iterator it = prefetched->begin();
+       it != prefetched->end(); ++it) {
+    ResourcePrefetcher::Request* req = *it;
+
+    // Set the usage states if the resource was actually used.
+    std::map<GURL, bool>::iterator actual_it = actual_resources.find(
+        req->resource_url);
+    if (actual_it != actual_resources.end()) {
+      if (actual_it->second) {
+        req->usage_status =
+            ResourcePrefetcher::Request::USAGE_STATUS_FROM_CACHE;
+      } else {
+        req->usage_status =
+            ResourcePrefetcher::Request::USAGE_STATUS_FROM_NETWORK;
+      }
+    }
+
+    switch (req->prefetch_status) {
+
+      // TODO(shishir): Add histogram for each cancellation reason.
+      case ResourcePrefetcher::Request::PREFETCH_STATUS_REDIRECTED:
+      case ResourcePrefetcher::Request::PREFETCH_STATUS_AUTH_REQUIRED:
+      case ResourcePrefetcher::Request::PREFETCH_STATUS_CERT_REQUIRED:
+      case ResourcePrefetcher::Request::PREFETCH_STATUS_CERT_ERROR:
+      case ResourcePrefetcher::Request::PREFETCH_STATUS_CANCELLED:
+        ++prefetch_cancelled;
+        break;
+
+      case ResourcePrefetcher::Request::PREFETCH_STATUS_FAILED:
+        ++prefetch_failed;
+        break;
+
+      case ResourcePrefetcher::Request::PREFETCH_STATUS_FROM_CACHE:
+        if (req->usage_status ==
+            ResourcePrefetcher::Request::USAGE_STATUS_FROM_CACHE)
+          ++p_cache_a_cache;
+        else if (req->usage_status ==
+                 ResourcePrefetcher::Request::USAGE_STATUS_FROM_NETWORK)
+          ++p_cache_a_network;
+        else
+          ++p_cache_a_notused;
+        break;
+
+      case ResourcePrefetcher::Request::PREFETCH_STATUS_FROM_NETWORK:
+          if (req->usage_status ==
+              ResourcePrefetcher::Request::USAGE_STATUS_FROM_CACHE)
+            ++p_network_a_cache;
+          else if (req->usage_status ==
+                   ResourcePrefetcher::Request::USAGE_STATUS_FROM_NETWORK)
+            ++p_network_a_network;
+          else
+            ++p_network_a_notused;
+        break;
+
+      case ResourcePrefetcher::Request::PREFETCH_STATUS_NOT_STARTED:
+        ++prefetch_not_started;
+        break;
+
+      case ResourcePrefetcher::Request::PREFETCH_STATUS_STARTED:
+        DLOG(FATAL) << "Invalid prefetch status";
+        break;
+    }
+  }
+
+  int total_prefetched = p_cache_a_cache + p_cache_a_network + p_cache_a_notused
+      + p_network_a_cache + p_network_a_network + p_network_a_notused;
+
+  UMA_HISTOGRAM_PERCENTAGE(
+      "ResourcePrefetchPredictor.PrefetchCancelled",
+      prefetch_cancelled * 100.0 / total_prefetched);
+  UMA_HISTOGRAM_PERCENTAGE(
+      "ResourcePrefetchPredictor.PrefetchFailed",
+      prefetch_failed * 100.0 / total_prefetched);
+  UMA_HISTOGRAM_PERCENTAGE(
+      "ResourcePrefetchPredictor.PrefetchFromCacheUsedFromCache",
+      p_cache_a_cache * 100.0 / total_prefetched);
+  UMA_HISTOGRAM_PERCENTAGE(
+      "ResourcePrefetchPredictor.PrefetchFromCacheUsedFromNetwork",
+      p_cache_a_network * 100.0 / total_prefetched);
+  UMA_HISTOGRAM_PERCENTAGE(
+      "ResourcePrefetchPredictor.PrefetchFromCacheNotUsed",
+      p_cache_a_notused * 100.0 / total_prefetched);
+  UMA_HISTOGRAM_PERCENTAGE(
+      "ResourcePrefetchPredictor.PrefetchFromNetworkUsedFromCache",
+      p_network_a_cache * 100.0 / total_prefetched);
+  UMA_HISTOGRAM_PERCENTAGE(
+      "ResourcePrefetchPredictor.PrefetchFromNetworkUsedFromNetwork",
+      p_network_a_network * 100.0 / total_prefetched);
+  UMA_HISTOGRAM_PERCENTAGE(
+      "ResourcePrefetchPredictor.PrefetchFromNetworkNotUsed",
+      p_network_a_notused * 100.0 / total_prefetched);
+
+  UMA_HISTOGRAM_PERCENTAGE(
+      "ResourcePrefetchPredictor.PrefetchNotStarted",
+      prefetch_not_started * 100.0 / (prefetch_not_started + total_prefetched));
+}
+
 void ResourcePrefetchPredictor::DeleteAllUrls() {
   inflight_navigations_.clear();
   url_table_cache_.clear();
 
   BrowserThread::PostTask(BrowserThread::DB, FROM_HERE,
       base::Bind(&ResourcePrefetchPredictorTables::DeleteAllRows, tables_));
 }
 
 void ResourcePrefetchPredictor::DeleteUrls(const history::URLRows& urls) {
   std::vector<GURL> urls_to_delete;
@@ skipping 14 matching lines @@
                    tables_,
                    urls_to_delete));
 }
 
 void ResourcePrefetchPredictor::SetTablesForTesting(
     scoped_refptr<ResourcePrefetchPredictorTables> tables) {
   tables_ = tables;
 }
 
 }  // namespace predictors