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>
 
@@ skipping 50 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()) {
   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 26 matching lines @@
   if (it != inflight_navigations_.end()) {
     DCHECK(it->first.creation_time != request.navigation_id.creation_time);
   }
 
   // Cleanup older navigations.
   CleanupAbandonedNavigations(request.navigation_id);
 
   // New empty navigation entry.
   inflight_navigations_.insert(std::make_pair(
       request.navigation_id, std::vector<URLRequestSummary>()));
+
+  const GURL& main_frame_url = request.navigation_id.main_frame_url;
+
+  // If prefetching is enabled, and we can prefetch something, start
+  // prefetching.
+  if (prefetch_manager_.get() &&

[dominich, 2012/07/23 16:04:41]

simpler:

if (!prefetch_manager_.get())
  return;

const UrlTableCacheMap::const_iterator iter =
url_table_cache_.find(main_frame_url);
if (iter == url_table_cache_.end())
  return;
const UrlTableCacheValue& value = *iter;
  ...

This saves the double lookup.

[Shishir, 2012/08/01 22:35:24]

Done.

+      url_table_cache_.find(main_frame_url) != url_table_cache_.end()) {
+    const UrlTableCacheValue& value = url_table_cache_[main_frame_url];
+
+    scoped_ptr<ResourcePrefetcher::RequestVector> requests(
+        new ResourcePrefetcher::RequestVector);
+    for (UrlTableRowVector::const_iterator it = value.rows.begin();
+         it != value.rows.end(); ++it) {
+      double confidence = static_cast<double>(it->number_of_hits) /
+          (it->number_of_hits + it->number_of_misses);
+      if (confidence < config_.min_resource_confidence_to_trigger_prefetch ||

[dominich, 2012/07/23 16:04:41]

warning: comparing double to float. Use double throughout config if you're going
to use double here. Or just use float here - accuracy is not exactly paramount.

[Shishir, 2012/08/01 22:35:24]

Everything is float now.

+          it->number_of_hits < config_.min_resource_hits_to_trigger_prefetch) {

[dominich, 2012/07/23 16:04:41]

maybe histogram this failure case

[Shishir, 2012/08/01 22:35:24]

We indirectly measure this.

+        continue;
+      }
+
+      ResourcePrefetcher::Request* req = new ResourcePrefetcher::Request(
+          it->resource_url);
+      requests->push_back(make_linked_ptr(req));

[dominich, 2012/07/23 16:04:41]

why is this a linked_ptr?

[Shishir, 2012/08/01 22:35:24]

Changed to scoped vector.

+    }
+
+    if (requests->empty())
+      return;
+
+    BrowserThread::PostTask(BrowserThread::IO, FROM_HERE,
+        base::Bind(&ResourcePrefetcherManager::MaybeAddPrefetch,
+                   prefetch_manager_,
+                   request.navigation_id,
+                   base::Passed(requests.Pass())));
+  }
 }
 
 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)) {
+      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 39 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));
+
+  DCHECK(results_map_.find(navigation_id) == results_map_.end());

[dominich, 2012/07/23 16:04:41]

again here you're doing a double lookup (in DEBUG). Use insert instead of [] to
save an implicit find.

[Shishir, 2012/08/01 22:35:24]

Done.

+
+  // Add the results to the results map.
+  results_map_[navigation_id].reset(requests.release());

[dominich, 2012/07/23 16:04:41]

ah, so you're using linked_ptr to have the vector deleted on erase? i'd prefer
an explicit call to delete than the overhead of the linked_ptr.

Similarly, you can use ScopedVector to have the vector contents deleted on
vector destruction.

[Shishir, 2012/08/01 22:35:24]

Done.

+}
+
 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);
+  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)
       RemoveAnEntryFromUrlDB();
@@ skipping 116 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) {
+  DCHECK(inflight_navigations_.find(navigation_id) !=
+         inflight_navigations_.end());
+
+  bool have_prefetch_results = results_map_.find(navigation_id) !=
+      results_map_.end();
+  UMA_HISTOGRAM_BOOLEAN("ResourcePrefetchPredictor.HavePrefetchResults",
+                        have_prefetch_results);
+  if (!have_prefetch_results)
+    return;
+
+  // Annotate the results.
+  const std::vector<URLRequestSummary>& actual =
+      inflight_navigations_.find(navigation_id)->second;

[dominich, 2012/07/23 16:04:41]

you're doing this find twice - do it once and use the iterator here and in the
DCHECK above.

[Shishir, 2012/08/01 22:35:24]

Done.

+  ResourcePrefetcher::RequestVector* prefetched =
+      results_map_.find(navigation_id)->second.get();

[dominich, 2012/07/23 16:04:41]

you're doing this find twice. do it once and cache the iterator.

[Shishir, 2012/08/01 22:35:24]

Done.

+
+  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;
+  }
+  for (ResourcePrefetcher::RequestVector::iterator it = prefetched->begin();
+       it != prefetched->end(); ++it) {
+    ResourcePrefetcher::Request* req = it->get();
+    if (actual_resources.find(req->resource_url) != actual_resources.end()) {
+      if (actual_resources[req->resource_url]) {

[dominich, 2012/07/23 16:04:41]

You just did the find to get the iterator - you should use that instead of [] to
save another lookup.

[Shishir, 2012/08/01 22:35:24]

Done.

+        req->usage_status =
+            ResourcePrefetcher::Request::USAGE_STATUS_FROM_CACHE;
+      } else {
+        req->usage_status =
+            ResourcePrefetcher::Request::USAGE_STATUS_FROM_NETWORK;
+      }
+    }
+  }
+
+  int prefetch_cancelled = 0, prefetch_failed = 0, prefetch_not_started = 0;
+  int p_cache_a_cache = 0, p_cache_a_network = 0, p_cache_a_notused = 0,

[dominich, 2012/07/23 16:04:41]

what is p_? don't use abbreviations.

[Shishir, 2012/08/01 22:35:24]

p_ is for predicted and a_ is actual. Added comment, else the names are far too
long.

+      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->get();

[dominich, 2012/07/23 16:04:41]

You can combine this loop with the one above that is setting usage_status.

[Shishir, 2012/08/01 22:35:24]

Done.

+    switch (req->prefetch_status) {
+      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";
+
+    }
+  }
+
+  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