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..fc9c38bacdb7ebab76f9cb8c4ff9ff5aea0534ba
--- /dev/null
+++ b/chrome/browser/predictors/resource_prefetch_predictor.cc
@@ -0,0 +1,721 @@
+// 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 "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

[dominich, 2012/05/21 16:16:53]

How much work has there been to tune these numbers? Do you expect them to
require experimentation?

[Shishir, 2012/05/23 01:46:46]

Some of these numbers do not need experimentation like
kMaxNavigationLifetimeSeconds. Other we might need to change based on the
histograms. 

+// 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;
+
+// Dont store subresources whose Urls are longer than this.

[dominich, 2012/05/21 16:16:53]

nit: Don't

[Shishir, 2012/05/23 01:46:46]

Done.

+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(std::string mime_type,

[dominich, 2012/05/21 16:16:53]

const std::string& mime_type to save the copy.

[Shishir, 2012/05/23 01:46:46]

Done.

+                                               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()
+    : 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(

[dominich, 2012/05/21 16:16:53]

TODO: check if this return value is used.

[Shishir, 2012/05/23 01:46:46]

It is used in the interceptor(now the network delegate). If we can't get the
renderer (it may not be a renderer request) we dont bother recording it.

+    net::URLRequest* request,
+    bool is_response) {
+  const content::ResourceRequestInfo* info =
+      content::ResourceRequestInfo::ForRequest(request);
+  if (!info) {
+    LOG(ERROR) << "No ResourceRequestInfo in request";

[dominich, 2012/05/21 16:16:53]

should this be a CHECK/DCHECK?

[Shishir, 2012/05/23 01:46:46]

No, as explained before.

+    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),
+      initialized_(false),
+      tables_(PredictorDatabaseFactory::GetForProfile(
+          profile)->resource_prefetch_tables()),
+      notification_registrar_(new content::NotificationRegistrar()) {
+  CHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
+
+  // 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();

[dominich, 2012/05/21 16:16:53]

You're not using the result of this call - this might cause a compile error on
some platform.

[Shishir, 2012/05/23 01:46:46]

Should not. There are examples of this in the codebase.

+
+  // 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, this,
+                 base::Owned(url_rows)));
+}
+
+ResourcePrefetchPredictor::~ResourcePrefetchPredictor() {
+}
+
+bool ResourcePrefetchPredictor::IsEnabled() {

[dominich, 2012/05/21 16:16:53]

These methods are not ordered as in the header - please rearrange them. Also, I
like the practice of labeling static methods with a // static comment.

[Shishir, 2012/05/23 01:46:46]

Added //static. I will reorder the function before checking in just to make sure
that the diff are not lost.

+  CommandLine* command_line = CommandLine::ForCurrentProcess();
+  return command_line->HasSwitch(
+      switches::kEnableSpeculativeResourcePrefetching);
+}
+
+void ResourcePrefetchPredictor::CreateCaches(
+    std::vector<UrlTableRow>* url_rows) {
+  CHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
+
+  DCHECK(!initialized_);
+  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

[dominich, 2012/05/21 16:16:53]

Can you use insertion sort to sort them as they're added instead?

[Shishir, 2012/05/23 01:46:46]

Will that be more efficient? They would still have the copying problem.

+  // 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();
+  }
+}
+
+bool ResourcePrefetchPredictor::ShouldInterceptRequest(
+    net::URLRequest* request) {
+  const content::ResourceRequestInfo* request_info =
+      content::ResourceRequestInfo::ForRequest(request);
+  if (!request_info)
+    return false;
+
+  switch (request_info->GetResourceType()) {

[dominich, 2012/05/21 16:16:53]

could be:

return request_info->GetResourceType() == ResourceType::MAIN_FRAME &&
    IsHandledMainPage(request);

[Shishir, 2012/05/23 01:46:46]

Done.

+    case ResourceType::MAIN_FRAME:
+      return IsHandledMainPage(request);
+    default:
+      return false;
+  }
+}
+
+bool ResourcePrefetchPredictor::ShouldInterceptResponse(
+    net::URLRequest* response) {
+  const content::ResourceRequestInfo* request_info =
+      content::ResourceRequestInfo::ForRequest(response);
+  if (!request_info)
+    return false;
+
+  switch (request_info->GetResourceType()) {

[dominich, 2012/05/21 16:16:53]

could be:

return request_info->GetResourceType() == ResourceType::MAIN_FRAME ?
    IsHandledMainPage(response) :
    IsHandledSubresource(response);

[Shishir, 2012/05/23 01:46:46]

Done.

+    case ResourceType::MAIN_FRAME:
+      return IsHandledMainPage(response);
+
+    // We discard request type here and look for mime type.
+    default:
+      return IsHandledSubresource(response);
+  }
+}
+
+bool ResourcePrefetchPredictor::ShouldInterceptRedirect(
+    net::URLRequest* response) {
+  const content::ResourceRequestInfo* request_info =
+      content::ResourceRequestInfo::ForRequest(response);
+  if (!request_info)
+    return false;
+
+  switch (request_info->GetResourceType()) {

[dominich, 2012/05/21 16:16:53]

As above

[Shishir, 2012/05/23 01:46:46]

Done.

+    case ResourceType::MAIN_FRAME:
+      return IsHandledMainPage(response);
+    default:
+      return false;
+  }
+}
+
+bool ResourcePrefetchPredictor::IsHandledMainPage(net::URLRequest* request) {
+  if (request->original_url().scheme() != chrome::kHttpScheme)

[dominich, 2012/05/21 16:16:53]

there's too many negatives here. How about:

return request->original_url().scheme() == chrome::kHttpScheme;

[Shishir, 2012/05/23 01:46:46]

Done.

+    return false;
+  return true;
+}
+
+bool ResourcePrefetchPredictor::IsHandledSubresource(
+    net::URLRequest* response) {
+  // If the embedding main page is not HTTP, we dont care.
+  if (response->first_party_for_cookies().scheme() != chrome::kHttpScheme)
+    return false;
+
+  // Check the scheme of the orign. We only do http.

[dominich, 2012/05/21 16:16:53]

nit: origin. Also, consider if these comments are actually useful. I think the
code is obvious enough that the comments don't add anything.

[Shishir, 2012/05/23 01:46:46]

Removed trivial comments.

+  if (response->original_url().scheme() != chrome::kHttpScheme)
+    return false;
+
+  // We can only deal with a few mime types.
+  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;
+  }
+
+  // Only lookup get requests.
+  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);
+  if (!is_cacheable)

[dominich, 2012/05/21 16:16:53]

return is_cacheable;

[Shishir, 2012/05/23 01:46:46]

Done.

+    return false;
+
+  return true;
+}
+
+bool ResourcePrefetchPredictor::IsCacheable(net::URLRequest* response) {

[dominich, 2012/05/21 16:16:53]

const net::URLRequest* response?

[Shishir, 2012/05/23 01:46:46]

Done.

+  // If this was serverd from cache, we are good.

[dominich, 2012/05/21 16:16:53]

nit: served

[Shishir, 2012/05/23 01:46:46]

Removed comment.

+  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));
+
+  switch (request.resource_type_) {

[dominich, 2012/05/21 16:16:53]

I find 'if' much more readable in the case of a single condition.

[Shishir, 2012/05/23 01:46:46]

Done.

+    case ResourceType::MAIN_FRAME:
+      OnMainFrameRequest(request);
+      break;
+    default:
+      NOTREACHED() << "Unhandled RecordURLRequest";
+  }
+}
+
+void ResourcePrefetchPredictor::RecordUrlResponse(
+    const URLRequestSummary& response) {
+  CHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
+
+  switch (response.resource_type_) {

[dominich, 2012/05/21 16:16:53]

if/else is more readable

[Shishir, 2012/05/23 01:46:46]

Done.

+    case ResourceType::MAIN_FRAME:
+      OnMainFrameResponse(response);
+      break;
+    default:
+      OnSubresourceResponse(response);
+  }
+}
+
+void ResourcePrefetchPredictor::RecordUrlRedirect(
+    const URLRequestSummary& response) {
+  CHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
+
+  switch (response.resource_type_) {
+    case ResourceType::MAIN_FRAME:

[dominich, 2012/05/21 16:16:53]

if rather than switch.

[Shishir, 2012/05/23 01:46:46]

Done.

+      OnMainFrameRedirect(response);
+      break;
+    default:
+      NOTREACHED() << "Unhandled RecordUrlRedirect";
+  }
+}
+
+void ResourcePrefetchPredictor::OnMainFrameRequest(
+    const URLRequestSummary& request) {
+  CHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
+  if (!initialized_)
+    return;
+
+  // It is possible to see this multiple times for the exact same navigation.
+  // TODO(shishir): Maybe fix it.

[dominich, 2012/05/21 16:16:53]

Enter a bug for this and reference it here.

[Shishir, 2012/05/23 01:46:46]

This should not be an issue now that we dont use an interceptor.

+  NavigationMap::const_iterator it =
+      inflight_navigations_.find(request.navigation_id_);
+  if (it != inflight_navigations_.end()) {
+    if (it->first.creation_time_ == request.navigation_id_.creation_time_) {
+      LOG(ERROR) << "Multiple OnMainFrameRequest for same navigation." <<
+                 it->first.creation_time_.ToInternalValue();
+      return;
+    }
+  }
+
+  // Cleanup older navigations.
+  CleanupAbandonedNavigations(request.navigation_id_);
+
+  // New empty navigation entry.
+  inflight_navigations_[request.navigation_id_];

[dominich, 2012/05/21 16:16:53]

Please use insert here with a default constructed
std::vector<UrlRequestSummary>() to make it clear what's going on.

[Shishir, 2012/05/23 01:46:46]

Done.

+}
+
+void ResourcePrefetchPredictor::OnMainFrameResponse(
+    const URLRequestSummary& response) {
+  CHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
+  if (!initialized_)
+    return;
+
+  // TODO(shishir): The prefreshing will be stopped here.

[dominich, 2012/05/21 16:16:53]

Can you add this as part of this CL?

[Shishir, 2012/05/23 01:46:46]

The entire prefreshing is missing from this CL. Tony suggested we just measure
accuracy first.

+}
+
+void ResourcePrefetchPredictor::OnMainFrameRedirect(
+    const URLRequestSummary& response) {
+  CHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
+  if (!initialized_)
+    return;
+
+  inflight_navigations_.erase(response.navigation_id_);

[dominich, 2012/05/21 16:16:53]

can you add a comment explaining why we're not stopping prefreshing here?

[Shishir, 2012/05/23 01:46:46]

Because we are not actually doing any prefreshing in this CL :) We are only
learning. I will add the comment when we actually do the prefreshing. 

+}
+
+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;
+  summary.resource_type_ = ResourceType::LAST_TYPE;   // Dont have type here.

[dominich, 2012/05/21 16:16:53]

You could add it - WebContentsImpl::OnDidLoadResourceFromMemoryCache has the
type.

[Shishir, 2012/05/23 01:46:46]

The resource_type is not very accurate. I am adding a CL to get the mime_type.
Adding a todo here to use it once available.

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

[dominich, 2012/05/21 16:16:53]

You can increment |it| in the for loop as map::erase doesn't invalidate the
iterator.

[Shishir, 2012/05/23 01:46:46]

That actually shouldn't work because 'it' itself should become invalid after the
erase.

+    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::ShutdownOnUIThread() {
+  notification_registrar_.reset(NULL);
+}
+
+void ResourcePrefetchPredictor::Observe(
+    int type,
+    const content::NotificationSource& source,
+    const content::NotificationDetails& details) {
+  CHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));

[dominich, 2012/05/21 16:16:53]

DCHECK instead of CHECK.

[Shishir, 2012/05/23 01:46:46]

I have all the thread checks as CHECKS and DCHECKs. I see the same in some other
files. Any reason this should be a DCHECK?

+
+  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(!initialized_);
+      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));
+  CHECK(!initialized_);
+
+  // Update the data with last visit info from in memory history db.
+  HistoryService* history_service =
+      profile_->GetHistoryService(Profile::EXPLICIT_ACCESS);
+  if (history_service && history_service->InMemoryDatabase()) {

[dominich, 2012/05/21 16:16:53]

I think you can DCHECK on history_service, or even assume that it's available,
given when this method is called.

[Shishir, 2012/05/23 01:46:46]

Done.

+    history::URLDatabase* url_db = history_service->InMemoryDatabase();

[dominich, 2012/05/21 16:16:53]

Then you can store this in the local var outside the conditional and save a call
to InMemoryDatabase.

[Shishir, 2012/05/23 01:46:46]

Done.

+
+    std::vector<GURL> urls_to_delete;
+    for (UrlTableCacheMap::iterator it = url_table_cache_.begin();
+         it != url_table_cache_.end();) {

[dominich, 2012/05/21 16:16:53]

Increment |it| in the for loop. map::erase doesn't invalidate iterators.

[Shishir, 2012/05/23 01:46:46]

As above the after the erase call, the 'it' itself becomes invalid so I have to
++ it in the erase call or create a copy.

+      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_.
+
+  initialized_ = true;
+}
+
+bool ResourcePrefetchPredictor::ShouldTrackUrl(const GURL& url) {
+  HistoryService* history_service =
+      profile_->GetHistoryService(Profile::EXPLICIT_ACCESS);
+  if (!history_service)
+    return false;
+  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",
+                        true);
+
+  // The following should probably be a DCHECK.
+  if (inflight_navigations_.find(navigation_id) == inflight_navigations_.end())

[dominich, 2012/05/21 16:16:53]

So make it a DCHECK :)

[Shishir, 2012/05/23 01:46:46]

Done.

+    return;
+
+  // Report any stats.
+  MaybeReportAccuracyStats(navigation_id);
+
+  // Update the URL table.
+  const GURL& main_frame_url = navigation_id.main_frame_url_;
+  if (url_table_cache_.find(main_frame_url) != url_table_cache_.end() ||

[dominich, 2012/05/21 16:16:53]

Is it worth putting the cache_ check inside ShouldTrackUrl?

[Shishir, 2012/05/23 01:46:46]

Done.

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

[dominich, 2012/05/21 16:16:53]

Can any of this be done as a PostTask to avoid blocking the UI loop?

[Shishir, 2012/05/23 01:46:46]

We could potentially post this to the DB thread let it do the math and report
back the results. Do you think it is worth it? This happens once per page load.

+
+  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();
+    for (int i = 0; i < static_cast<int>(new_resources.size()); ++i) {

[dominich, 2012/05/21 16:16:53]

cache the loop end variable outside the loop to avoid recalculation every
iteration.

[Shishir, 2012/05/23 01:46:46]

Done.

+      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;
+    for (int i = 0; i < static_cast<int>(new_resources.size()); ++i) {

[dominich, 2012/05/21 16:16:53]

cache the loop end var in a local variable.

[Shishir, 2012/05/23 01:46:46]

Done.

+      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;
+    }
+    for (int i = 0; i < static_cast<int>(old_resources.size()); ++i) {

[dominich, 2012/05/21 16:16:53]

cache the loop end var in a local variable.

[Shishir, 2012/05/23 01:46:46]

Done.

+      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 < static_cast<int>(old_resources.size()); ++i) {

[dominich, 2012/05/21 16:16:53]

cache loop end var.

[Shishir, 2012/05/23 01:46:46]

Done.

+      UrlTableRow& old_row = old_resources[i];
+      if (new_index.find(old_row.resource_url_) == new_index.end()) {
+        old_row.number_of_misses_++;

[dominich, 2012/05/21 16:16:53]

prefer pre-increment.

[Shishir, 2012/05/23 01:46:46]

Done.

+        old_row.consecutive_misses_++;
+      } else {
+        const URLRequestSummary& new_row =
+            new_resources[new_index[old_row.resource_url_]];

[dominich, 2012/05/21 16:16:53]

you could remove it from new_resources here to make the following loop smaller.

[Shishir, 2012/05/23 01:46:46]

Wont removing the struct from the vector be more inefficient than just iterating
over it once?

+
+        // Update the resource type if its missing.

[dominich, 2012/05/21 16:16:53]

nit: it's

[Shishir, 2012/05/23 01:46:46]

Done.

+        if (old_row.resource_type_ == ResourceType::LAST_TYPE)
+          old_row.resource_type_ = new_row.resource_type_;

[dominich, 2012/05/21 16:16:53]

what if the resource_type has changed? unlikely, but an edge case to consider.

[Shishir, 2012/05/23 01:46:46]

Fixed.

+
+        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_++;

[dominich, 2012/05/21 16:16:53]

prefer pre-increment.

[Shishir, 2012/05/23 01:46:46]

Done.

+        old_row.consecutive_misses_ = 0;
+      }
+    }
+
+    // Add the new ones that we have not seen before.
+    for (int i = 0; i < static_cast<int>(new_resources.size()); ++i) {

[dominich, 2012/05/21 16:16:53]

cache loop var.

[Shishir, 2012/05/23 01:46:46]

Done.

+      const URLRequestSummary& summary = new_resources[i];
+      if (old_index.find(summary.resource_url_) != old_index.end())

[dominich, 2012/05/21 16:16:53]

This would be a DCHECK if you remove from new_resources above.

[Shishir, 2012/05/23 01:46:46]

Pending reply on the above comemnt.

+        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 (int i = rows.size() - 1; i >= 0; --i) {

[dominich, 2012/05/21 16:16:53]

use iterator loop here.

[Shishir, 2012/05/23 01:46:46]

Done.

+    UrlTableRow& row = rows[i];
+    row.UpdateScore();
+    if (row.consecutive_misses_ >= kMaxConsecutiveMisses)
+      rows.erase(rows.begin() + i);
+  }
+  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 (int i = 0; i < static_cast<int>(actual.size()); ++i) {

[dominich, 2012/05/21 16:16:53]

use iterator loop.

[Shishir, 2012/05/23 01:46:46]

Done.

+    actual_resources[actual[i].resource_url_] = actual[i].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++;

[dominich, 2012/05/21 16:16:53]

prefer pre-increment

[Shishir, 2012/05/23 01:46:46]

Done.

+    } else if (actual_resources[row.resource_url_]) {
+      prefetch_cached++;

[dominich, 2012/05/21 16:16:53]

prefer pre-increment

[Shishir, 2012/05/23 01:46:46]

Done.

+    } else {
+      prefetch_network++;

[dominich, 2012/05/21 16:16:53]

prefer pre-increment

[Shishir, 2012/05/23 01:46:46]

Done.

+    }
+  }
+
+  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