Seculative resource prefetching for URLs CL.

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 <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;
+}
+
+// For reporting histograms about navigation status.
+enum NavigationStatus {
+  NAVIGATION_STATUS_COMPLETE = 0,
+  NAVIGATION_STATUS_COMPLETE_ABANDONED = 1,
+  NAVIGATION_STATUS_ABANDONED = 2,
+  NAVIGATION_STATUS_COUNT = 3
+};
+
+}  // namespace
+
+namespace predictors {
+
+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() {
+}
+
+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() {

[willchan no longer on Chromium, 2012/05/31 02:08:58]

This is deleted on the UI thread, right?

[Shishir, 2012/06/02 01:19:29]

Yes. Added assertion.

+}
+
+// static
+bool ResourcePrefetchPredictor::IsEnabled() {
+  CommandLine* command_line = CommandLine::ForCurrentProcess();
+  return command_line->HasSwitch(
+      switches::kEnableSpeculativeResourcePrefetching);

[willchan no longer on Chromium, 2012/05/31 02:08:58]

Is this supposed to dynamically checked? Do you want it dynamically configurable
via about:flags at some point? Or would you rather initialize it only on
startup?

[Shishir, 2012/06/02 01:19:29]

It can presently be set by about:flags. But i thought that still requires it to
restart? 

+}
+
+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);
+  }
+
+  // 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();
+    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;
+
+  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));
+  DCHECK_EQ(INITIALIZED, initialization_state_);
+
+  // 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())
+    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())
+    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_ENUMERATION("ResourcePrefetchPredictor.NavigationStatus",
+                                NAVIGATION_STATUS_ABANDONED,
+                                NAVIGATION_STATUS_COUNT);
+    } 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() {

[willchan no longer on Chromium, 2012/05/31 02:08:58]

In locations like this where you populate internal member variables from
persistent data stores (databases in this case), can you add a layer of
indirection? Use a PersistenceDelegate or something here. The reasons are
two-fold:
* ease of testing with fake delegates
* removes a dependency on chrome specifics, allowing for potential reuse in
other codebases that want to do resource prefetching but don't want to be tied
to desktop Chrome's persistence data stores.

[Shishir, 2012/06/02 01:19:29]

I think that it would be unnecessary at this stage because we are not yet sure
whether this code will even remain in chrome. It will only remain if we see
gains. At that stage it might make sense to create a persistence interface.

+  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));
+
+  if (inflight_navigations_.find(navigation_id) ==
+      inflight_navigations_.end()) {
+    UMA_HISTOGRAM_ENUMERATION("ResourcePrefetchPredictor.NavigationStatus",
+                              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);
+
+  // 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(
+      "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