Seculative resource prefetching for URLs CL.

chrome/browser/predictors/resource_prefetch_predictor.cc

Index: chrome/browser/predictors/resource_prefetch_predictor.cc
diff --git a/chrome/browser/predictors/resource_prefetch_predictor.cc b/chrome/browser/predictors/resource_prefetch_predictor.cc
new file mode 100644
index 0000000000000000000000000000000000000000..a967f14e1d21129726b5fe2ced833ceca418cec2
--- /dev/null
+++ b/chrome/browser/predictors/resource_prefetch_predictor.cc
@@ -0,0 +1,701 @@
+// 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 <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/profiles/profile.h"
+#include "chrome/common/chrome_notification_types.h"
+#include "chrome/common/chrome_switches.h"
+#include "chrome/common/url_constants.h"
+#include "content/browser/load_from_memory_cache_details.h"
+#include "content/public/browser/browser_thread.h"
+#include "content/public/browser/navigation_controller.h"
+#include "content/public/browser/notification_service.h"
+#include "content/public/browser/notification_source.h"
+#include "content/public/browser/notification_types.h"
+#include "content/public/browser/resource_request_info.h"
+#include "content/public/browser/web_contents.h"
+#include "net/base/mime_util.h"
+#include "net/http/http_response_headers.h"
+#include "net/url_request/url_request.h"
+#include "net/url_request/url_request_context_getter.h"
+
+using content::BrowserThread;
+
+namespace {
+
+// If a navigation hasn't seen a load complete event in this much time, it is
+// considered abandoned.
+static const int kMaxNavigationLifetimeSeconds = 60;
+
+// Size of LRU caches for the Url data.
+static const size_t kMaxNumUrlsToTrack = 500;
+
+// The number of times, we should have seen visit to this Url in history
+// to start tracking it. This is to ensure we dont bother with oneoff entries.
+static const int kMinUrlVisitCount = 3;
+
+// The maximum number of resources to store per entry. This is about double of
+// the expected 25 we expect to prefetch.
+static const int kMaxResourcesPerEntry = 50;
+
+// Don't store subresources whose Urls are longer than this.
+static const size_t kMaxSubresourceUrlLengthBytes = 1000;
+
+// The number of consecutive misses after we stop tracking a resource Url.
+static const int kMaxConsecutiveMisses = 3;
+
+// The number of resources we should report accuracy stats on.
+static const int kNumResourcesAssumedPrefetched = 25;
+
+ResourceType::Type GetResourceTypeFromMimeType(const std::string& mime_type,
+                                               ResourceType::Type fallback) {
+  if (net::IsSupportedImageMimeType(mime_type.c_str()))
+    return ResourceType::IMAGE;
+  else if (net::IsSupportedJavascriptMimeType(mime_type.c_str()))
+    return ResourceType::SCRIPT;
+  else if (net::MatchesMimeType("text/css", mime_type))
+    return ResourceType::STYLESHEET;
+  else
+    return fallback;
+}
+
+}  // namespace
+
+namespace predictors {
+
+ResourcePrefetchPredictor::URLRequestSummary::URLRequestSummary()

[dominich, 2012/05/30 15:35:01]

initialize resource_type_ and mime_type_ to something sensible

[Shishir, 2012/05/30 18:07:15]

Seemed to have lost this change. Fixed. Mime_type will be empty as default.

+    : 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() {
+}
+
+bool ResourcePrefetchPredictor::URLRequestSummary::InitFromURLRequest(
+    net::URLRequest* request,
+    bool is_response) {
+  const content::ResourceRequestInfo* info =
+      content::ResourceRequestInfo::ForRequest(request);
+  if (!info) {
+    LOG(ERROR) << "No ResourceRequestInfo in request";
+    return false;
+  }
+
+  int render_process_id, render_view_id;
+  if (!info->GetAssociatedRenderView(&render_process_id, &render_view_id)) {
+    LOG(ERROR) << "Could not get RenderViewId from request info.";
+    return false;
+  }
+
+  navigation_id_.render_process_id_ = render_process_id;
+  navigation_id_.render_view_id_ = render_view_id;
+  navigation_id_.main_frame_url_ = request->first_party_for_cookies();
+  navigation_id_.creation_time_ = request->creation_time();
+  resource_url_ = request->original_url();
+  resource_type_ = info->GetResourceType();
+  if (is_response) {
+    request->GetMimeType(&mime_type_);
+    was_cached_ = request->was_cached();
+    // We want to rely on the mime_type for the resource type.
+    resource_type_ = GetResourceTypeFromMimeType(mime_type_, resource_type_);
+  }
+
+  return true;
+}
+
+ResourcePrefetchPredictor::ResourcePrefetchPredictor(Profile* profile)
+    : profile_(profile),
+      initialization_state_(NOT_INITIALIZED),
+      tables_(PredictorDatabaseFactory::GetForProfile(
+          profile)->resource_prefetch_tables()),
+      notification_registrar_(new content::NotificationRegistrar()) {
+  CHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
+}
+
+ResourcePrefetchPredictor::~ResourcePrefetchPredictor() {
+}
+
+// static
+bool ResourcePrefetchPredictor::IsEnabled() {
+  CommandLine* command_line = CommandLine::ForCurrentProcess();
+  return command_line->HasSwitch(
+      switches::kEnableSpeculativeResourcePrefetching);
+}
+
+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.
+  HistoryService* history_service =
+      profile_->GetHistoryService(Profile::EXPLICIT_ACCESS);
+  if (history_service)
+    history_service->InMemoryDatabase();
+
+  // Create local caches using the database as loaded.
+  std::vector<UrlTableRow>* url_rows = new std::vector<UrlTableRow>();
+  BrowserThread::PostTaskAndReply(
+      BrowserThread::DB, FROM_HERE,
+      base::Bind(&ResourcePrefetchPredictorTables::GetAllRows,
+                 tables_, url_rows),
+      base::Bind(&ResourcePrefetchPredictor::CreateCaches, AsWeakPtr(),
+                 base::Owned(url_rows)));
+}
+
+void ResourcePrefetchPredictor::CreateCaches(
+    std::vector<UrlTableRow>* url_rows) {
+  CHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
+
+  DCHECK_EQ(initialization_state_, INITIALIZING);
+  DCHECK(url_table_cache_.empty());
+  DCHECK(inflight_navigations_.empty());
+
+  // Copy the data to local caches.
+  for (UrlTableRowVector::iterator it = url_rows->begin();
+       it != url_rows->end(); ++it) {
+    url_table_cache_[it->main_frame_url_].rows_.push_back(*it);

[dominich, 2012/05/30 15:35:01]

initialize last_visit_ to something useful?

[Shishir, 2012/05/30 18:07:15]

By default it will initialize to 0, and we will do an immediate filtering in the
OnHistoryAndCacheLoaded. So is there a need to do anything else here?

+  }
+
+  // Score and sort the database caches.
+  // TODO(shishir): The following would be much more efficient if we used
+  // pointers.
+  for (UrlTableCacheMap::iterator it = url_table_cache_.begin();
+       it != url_table_cache_.end(); ++it) {
+    std::sort(it->second.rows_.begin(),
+              it->second.rows_.end(),
+              ResourcePrefetchPredictorTables::UrlTableRowSorter());
+  }
+
+  // Add notifications for history loading if it is not ready.
+  if (!profile_->GetHistoryService(Profile::EXPLICIT_ACCESS)) {
+    notification_registrar_->Add(this, chrome::NOTIFICATION_HISTORY_LOADED,
+                                 content::Source<Profile>(profile_));
+  } else {
+    OnHistoryAndCacheLoaded();
+  }
+}
+
+// static
+bool ResourcePrefetchPredictor::ShouldRecordRequest(
+    net::URLRequest* request,
+    ResourceType::Type resource_type) {
+  return resource_type == ResourceType::MAIN_FRAME &&
+      IsHandledMainPage(request);
+}
+
+// static
+bool ResourcePrefetchPredictor::ShouldRecordResponse(
+    net::URLRequest* response) {
+  const content::ResourceRequestInfo* request_info =
+      content::ResourceRequestInfo::ForRequest(response);
+  if (!request_info)
+    return false;
+
+  return request_info->GetResourceType() == ResourceType::MAIN_FRAME ?
+      IsHandledMainPage(response) : IsHandledSubresource(response);
+}
+
+// static
+bool ResourcePrefetchPredictor::ShouldRecordRedirect(
+    net::URLRequest* response) {
+  const content::ResourceRequestInfo* request_info =
+      content::ResourceRequestInfo::ForRequest(response);
+  if (!request_info)
+    return false;
+
+  return request_info->GetResourceType() == ResourceType::MAIN_FRAME &&
+      IsHandledMainPage(response);
+}
+
+// static
+bool ResourcePrefetchPredictor::IsHandledMainPage(net::URLRequest* request) {
+  return request->original_url().scheme() == chrome::kHttpScheme;
+}
+
+// static
+bool ResourcePrefetchPredictor::IsHandledSubresource(
+    net::URLRequest* response) {
+  if (response->first_party_for_cookies().scheme() != chrome::kHttpScheme)
+    return false;
+
+  if (response->original_url().scheme() != chrome::kHttpScheme)
+    return false;
+
+  std::string mime_type;
+  response->GetMimeType(&mime_type);
+  if (!mime_type.empty() &&
+      !net::IsSupportedImageMimeType(mime_type.c_str()) &&
+      !net::IsSupportedJavascriptMimeType(mime_type.c_str()) &&
+      !net::MatchesMimeType("text/css", mime_type)) {
+    return false;
+  }
+
+  if (response->method() != "GET")
+    return false;
+
+  if (response->original_url().spec().length() > kMaxSubresourceUrlLengthBytes)
+    return false;
+
+  bool is_cacheable = IsCacheable(response);
+  UMA_HISTOGRAM_BOOLEAN("ResourcePrefetchPredictor.IsCacheableResource",
+                        is_cacheable);
+  return is_cacheable;
+}
+
+// static
+bool ResourcePrefetchPredictor::IsCacheable(const net::URLRequest* response) {
+  if (response->was_cached())
+    return true;
+
+  // For non cached responses, we will ensure that the freshness lifetime is
+  // some sane value.
+  const net::HttpResponseInfo& response_info = response->response_info();
+  base::Time response_time(response_info.response_time);
+  response_time += base::TimeDelta::FromSeconds(1);
+  base::TimeDelta freshness = response_info.headers->GetFreshnessLifetime(
+      response_time);
+  return freshness > base::TimeDelta();
+}
+
+void ResourcePrefetchPredictor::RecordURLRequest(
+    const URLRequestSummary& request) {
+  CHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
+
+  if (initialization_state_ == NOT_INITIALIZED) {
+    LazilyInitialize();

[dominich, 2012/05/30 15:35:01]

You could record the request in a pending list to process when initialization is
complete, if you don't want to miss these initial requests.

[Shishir, 2012/05/30 18:07:15]

That would add the initialization check all over the code, making it harder to
understand. I think missing a request or two might be acceptable for now.

+    return;
+  } else if (initialization_state_ != INITIALIZED) {

[dominich, 2012/05/30 15:35:01]

paranoid version:

else if (initialization_state_ == INITIALIZING)
  return;

DCHECK_EQ(INITALIZED, initialized_state_);

[Shishir, 2012/05/30 18:07:15]

Done.

+    return;
+  }
+
+  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;
+
+  if (response.resource_type_ == ResourceType::MAIN_FRAME)
+    OnMainFrameResponse(response);
+  else
+    OnSubresourceResponse(response);
+}
+
+void ResourcePrefetchPredictor::RecordUrlRedirect(
+    const URLRequestSummary& response) {
+  CHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
+  if (initialization_state_ != INITIALIZED)
+    return;
+
+  CHECK_EQ(response.resource_type_, ResourceType::MAIN_FRAME);
+  OnMainFrameRedirect(response);
+}
+
+void ResourcePrefetchPredictor::OnMainFrameRequest(
+    const URLRequestSummary& request) {
+  CHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));

[dominich, 2012/05/30 15:35:01]

paranoid version:

DCHECK_EQ(INITALIZED, initialized_state_);

[Shishir, 2012/05/30 18:07:15]

Done.

+
+  // TODO(shishir): Remove this code after verifying that the same navigation is
+  // not seen multiple times.
+  NavigationMap::const_iterator it =
+      inflight_navigations_.find(request.navigation_id_);
+  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>()));
+}
+
+void ResourcePrefetchPredictor::OnMainFrameResponse(
+    const URLRequestSummary& response) {
+  CHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
+
+  // TODO(shishir): The prefreshing will be stopped here.
+}
+
+void ResourcePrefetchPredictor::OnMainFrameRedirect(
+    const URLRequestSummary& response) {
+  CHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
+
+  inflight_navigations_.erase(response.navigation_id_);
+}
+
+void ResourcePrefetchPredictor::OnSubresourceResponse(
+    const URLRequestSummary& response) {
+  CHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
+
+  if (inflight_navigations_.find(response.navigation_id_) ==
+      inflight_navigations_.end())

[dominich, 2012/05/30 15:35:01]

it may be worth counting these in a histogram to determine if you're marking
navigations as abandoned too aggressively.

[Shishir, 2012/05/30 18:07:15]

Added enum

+    return;
+
+  inflight_navigations_[response.navigation_id_].push_back(response);
+}
+
+void ResourcePrefetchPredictor::OnSubresourceLoadedFromMemory(
+    const NavigationID& navigation_id,
+    const GURL& resource_url) {
+  if (inflight_navigations_.find(navigation_id) == inflight_navigations_.end())

[dominich, 2012/05/30 15:35:01]

see above re counting

[Shishir, 2012/05/30 18:07:15]

same comment as above.

+    return;
+
+  URLRequestSummary summary;
+  summary.navigation_id_ = navigation_id;
+  summary.resource_url_ = resource_url;
+  // The mime_type is currently not available in this notification.
+  // TODO(shishir): Set correct type when CL:10413064 is committed.
+  summary.resource_type_ = ResourceType::LAST_TYPE;
+  summary.was_cached_ = true;
+  inflight_navigations_[navigation_id].push_back(summary);
+}
+
+void ResourcePrefetchPredictor::CleanupAbandonedNavigations(
+    const NavigationID& navigation_id) {
+  static const base::TimeDelta max_navigation_age =
+      base::TimeDelta::FromSeconds(kMaxNavigationLifetimeSeconds);
+
+  base::TimeTicks time_now = base::TimeTicks::Now();
+  for (NavigationMap::iterator it = inflight_navigations_.begin();
+       it != inflight_navigations_.end();) {
+    if (it->first.IsSameRenderer(navigation_id) ||
+        (time_now - it->first.creation_time_ > max_navigation_age)) {
+      inflight_navigations_.erase(it++);
+      UMA_HISTOGRAM_BOOLEAN("ResourcePrefetchPredictor.DidNavigationComplete",
+                            false);
+    } 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: {
+      const content::WebContents* web_contents =
+          content::Source<content::WebContents>(source).ptr();
+      NavigationID navigation_id(*web_contents);
+      OnNavigationComplete(navigation_id);
+      break;
+    }
+
+    case content::NOTIFICATION_LOAD_FROM_MEMORY_CACHE: {
+      const LoadFromMemoryCacheDetails* load_details =
+          content::Details<LoadFromMemoryCacheDetails>(details).ptr();
+      const content::WebContents* web_contents =
+          content::Source<content::NavigationController>(
+              source).ptr()->GetWebContents();
+
+      NavigationID navigation_id(*web_contents);
+      OnSubresourceLoadedFromMemory(navigation_id, load_details->url());
+      break;
+    }
+
+    case chrome::NOTIFICATION_HISTORY_LOADED: {
+      DCHECK_EQ(initialization_state_, INITIALIZING);
+      notification_registrar_->Remove(this,
+                                      chrome::NOTIFICATION_HISTORY_LOADED,
+                                      content::Source<Profile>(profile_));
+      OnHistoryAndCacheLoaded();
+      break;
+    }
+
+    default:
+      NOTREACHED() << "Unexpected notification observed.";
+      break;
+  }
+}
+
+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) {
+    std::vector<GURL> urls_to_delete;
+    for (UrlTableCacheMap::iterator it = url_table_cache_.begin();
+         it != url_table_cache_.end();) {
+      history::URLRow url_row;
+      if (url_db->GetRowForURL(it->first, &url_row) == 0) {
+        urls_to_delete.push_back(it->first);
+        url_table_cache_.erase(it++);
+      } else {
+        it->second.last_visit_ = url_row.last_visit();
+        ++it;
+      }
+    }
+    if (!urls_to_delete.empty())
+      BrowserThread::PostTask(BrowserThread::DB, FROM_HERE,
+          base::Bind(&ResourcePrefetchPredictorTables::DeleteUrlRows,
+                     tables_,
+                     urls_to_delete));
+  }
+
+  notification_registrar_->Add(
+    this,
+    content::NOTIFICATION_LOAD_FROM_MEMORY_CACHE,
+    content::NotificationService::AllSources());
+
+  notification_registrar_->Add(
+    this,
+    content::NOTIFICATION_LOAD_COMPLETED_MAIN_FRAME,
+    content::NotificationService::AllSources());
+
+  // TODO(shishir): Maybe listen for notifications for navigation being
+  // abandoned and cleanup the inflight_navigations_.
+
+  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);
+  history::URLDatabase* url_db = history_service->InMemoryDatabase();
+  if (!url_db)
+    return false;
+
+  history::URLRow url_row;
+  return url_db->GetRowForURL(url, &url_row) != 0 &&
+      url_row.visit_count() >= kMinUrlVisitCount;
+}
+
+void ResourcePrefetchPredictor::OnNavigationComplete(
+    const NavigationID& navigation_id) {
+  CHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
+
+  UMA_HISTOGRAM_BOOLEAN("ResourcePrefetchPredictor.DidNavigationComplete",

[dominich, 2012/05/30 15:35:01]

should this be counted after the check for inflight? Maybe you need three
states: complete, complete_abandoned, incomplete.

[Shishir, 2012/05/30 18:07:15]

Done.

+                        true);
+
+  if (inflight_navigations_.find(navigation_id) == inflight_navigations_.end())

[dominich, 2012/05/30 15:35:01]

see above re counting

[Shishir, 2012/05/30 18:07:15]

Done.

+    return;
+
+  // Report any stats.
+  MaybeReportAccuracyStats(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);
+}
+
+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() >= kMaxNumUrlsToTrack)
+      RemoveAnEntryFromUrlDB();
+
+    url_table_cache_[main_frame_url].last_visit_ = base::Time::Now();
+    int new_resources_size = static_cast<int>(new_resources.size());
+    for (int i = 0; i < new_resources_size; ++i) {
+      UrlTableRow row_to_add;
+      row_to_add.main_frame_url_ = main_frame_url;
+      row_to_add.resource_url_ = new_resources[i].resource_url_;
+      row_to_add.resource_type_ = new_resources[i].resource_type_;
+      row_to_add.number_of_hits_ = 1;
+      row_to_add.average_position_ = i + 1;
+      url_table_cache_[main_frame_url].rows_.push_back(row_to_add);
+    }
+  } else {
+    UrlTableRowVector& old_resources = url_table_cache_[main_frame_url].rows_;
+    url_table_cache_[main_frame_url].last_visit_ = base::Time::Now();
+
+    // Build indices over the data.
+    std::map<GURL, int> new_index, old_index;
+    int new_resources_size = static_cast<int>(new_resources.size());
+    for (int i = 0; i < new_resources_size; ++i) {
+      const URLRequestSummary& summary = new_resources[i];
+      // Take the first occurence of every url.
+      if (new_index.find(summary.resource_url_) == new_index.end())
+        new_index[summary.resource_url_] = i;
+    }
+    int old_resources_size = static_cast<int>(old_resources.size());
+    for (int i = 0; i < old_resources_size; ++i) {
+      const UrlTableRow& row = old_resources[i];
+      DCHECK(old_index.find(row.resource_url_) == old_index.end());
+      old_index[row.resource_url_] = i;
+    }
+
+    // Go through the old urls and update their hit/miss counts.
+    for (int i = 0; i < old_resources_size; ++i) {
+      UrlTableRow& old_row = old_resources[i];
+      if (new_index.find(old_row.resource_url_) == new_index.end()) {
+        ++old_row.number_of_misses_;
+        ++old_row.consecutive_misses_;
+      } else {
+        const URLRequestSummary& new_row =
+            new_resources[new_index[old_row.resource_url_]];
+
+        // Update the resource type since it could have changed.
+        if (new_row.resource_type_ != ResourceType::LAST_TYPE)
+          old_row.resource_type_ = new_row.resource_type_;
+
+        int position = new_index[old_row.resource_url_] + 1;
+        int total = old_row.number_of_hits_ + old_row.number_of_misses_;
+        old_row.average_position_ =
+            ((old_row.average_position_ * total) + position) / (total + 1);
+        ++old_row.number_of_hits_;
+        old_row.consecutive_misses_ = 0;
+      }
+    }
+
+    // Add the new ones that we have not seen before.
+    for (int i = 0; i < new_resources_size; ++i) {
+      const URLRequestSummary& summary = new_resources[i];
+      if (old_index.find(summary.resource_url_) != old_index.end())
+        continue;
+
+      // Only need to add new stuff.
+      UrlTableRow row_to_add;
+      row_to_add.main_frame_url_ = main_frame_url;
+      row_to_add.resource_url_ = summary.resource_url_;
+      row_to_add.resource_type_ = summary.resource_type_;
+      row_to_add.number_of_hits_ = 1;
+      row_to_add.average_position_ = i + 1;
+      old_resources.push_back(row_to_add);
+
+      // To ensure we dont add the same url twice.
+      old_index[summary.resource_url_] = 0;
+    }
+  }
+
+  // Trim and sort the rows after the update.
+  UrlTableRowVector& rows = url_table_cache_[main_frame_url].rows_;
+  for (UrlTableRowVector::iterator it = rows.begin(); it != rows.end();) {
+    it->UpdateScore();
+    if (it->consecutive_misses_ >= kMaxConsecutiveMisses)
+      it = rows.erase(it);
+    else
+      ++it;
+  }
+  std::sort(rows.begin(), rows.end(),
+            ResourcePrefetchPredictorTables::UrlTableRowSorter());
+
+  BrowserThread::PostTask(
+      BrowserThread::DB, FROM_HERE,
+      base::Bind(&ResourcePrefetchPredictorTables::UpdateRowsForUrl,
+                 tables_,
+                 main_frame_url,
+                 rows));
+}
+
+void ResourcePrefetchPredictor::RemoveAnEntryFromUrlDB() {
+  if (url_table_cache_.empty())
+    return;
+
+  // TODO(shishir): Maybe use a heap to do this more efficiently.
+  base::Time oldest_time;
+  GURL url_to_erase;
+  for (UrlTableCacheMap::iterator it = url_table_cache_.begin();
+       it != url_table_cache_.end(); ++it) {
+    if (url_to_erase.is_empty() || it->second.last_visit_ < oldest_time) {
+      url_to_erase = it->first;
+      oldest_time = it->second.last_visit_;
+    }
+  }
+  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::DeleteUrlRows,
+                 tables_,
+                 urls_to_delete));
+}
+
+void ResourcePrefetchPredictor::MaybeReportAccuracyStats(
+    const NavigationID& navigation_id) {
+  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)
+    return;
+
+  const std::vector<URLRequestSummary>& actual =
+      inflight_navigations_[navigation_id];
+  const UrlTableRowVector& predicted = url_table_cache_[main_frame_url].rows_;
+
+  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_cached = 0, prefetch_network = 0, prefetch_missed = 0;
+  int num_assumed_prefetched = std::min(static_cast<int>(predicted.size()),
+                                        kNumResourcesAssumedPrefetched);
+  for (int i = 0; i < num_assumed_prefetched; ++i) {
+    const UrlTableRow& row = predicted[i];
+    if (actual_resources.find(row.resource_url_) == actual_resources.end()) {
+      ++prefetch_missed;
+    } else if (actual_resources[row.resource_url_]) {
+      ++prefetch_cached;
+    } else {
+      ++prefetch_network;
+    }
+  }
+
+  UMA_HISTOGRAM_PERCENTAGE(

[dominich, 2012/05/30 15:35:01]

It's up to you to decide what stats are important. I found it more useful to
have the raw counts to analyze rather than precomputed percentages.

[Shishir, 2012/05/30 18:07:15]

Since both the numerator and denominator vary per request, having all stats on a
single base makes sense.

+      "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);
+}
+
+}  // namespace predictors