chrome/browser/predictors/resource_prefetch_predictor.cc

   1 // Copyright 2014 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "chrome/browser/predictors/resource_prefetch_predictor.h"
   6
   7 #include <map>
   8 #include <set>
   9 #include <utility>
  10
  11 #include "base/command_line.h"
  12 #include "base/metrics/histogram.h"
  13 #include "base/metrics/sparse_histogram.h"
  14 #include "base/stl_util.h"
  15 #include "base/strings/string_number_conversions.h"
  16 #include "base/strings/stringprintf.h"
  17 #include "base/time/time.h"
  18 #include "chrome/browser/history/history_service_factory.h"
  19 #include "chrome/browser/predictors/predictor_database.h"
  20 #include "chrome/browser/predictors/predictor_database_factory.h"
  21 #include "chrome/browser/predictors/resource_prefetcher_manager.h"
  22 #include "chrome/browser/profiles/profile.h"
  23 #include "chrome/common/chrome_switches.h"
  24 #include "chrome/common/url_constants.h"
  25 #include "components/history/core/browser/history_database.h"
  26 #include "components/history/core/browser/history_db_task.h"
  27 #include "components/history/core/browser/history_service.h"
  28 #include "content/public/browser/browser_thread.h"
  29 #include "content/public/browser/navigation_controller.h"
  30 #include "content/public/browser/resource_request_info.h"
  31 #include "content/public/browser/web_contents.h"
  32 #include "net/base/mime_util.h"
  33 #include "net/base/network_change_notifier.h"
  34 #include "net/http/http_response_headers.h"
  35 #include "net/url_request/url_request.h"
  36 #include "net/url_request/url_request_context_getter.h"
  37
  38 using content::BrowserThread;
  39
  40 namespace {
  41
  42 // For reporting whether a subresource is handled or not, and for what reasons.
  43 enum ResourceStatus {
  44   RESOURCE_STATUS_HANDLED = 0,
  45   RESOURCE_STATUS_NOT_HTTP_PAGE = 1,
  46   RESOURCE_STATUS_NOT_HTTP_RESOURCE = 2,
  47   RESOURCE_STATUS_UNSUPPORTED_MIME_TYPE = 4,
  48   RESOURCE_STATUS_NOT_GET = 8,
  49   RESOURCE_STATUS_URL_TOO_LONG = 16,
  50   RESOURCE_STATUS_NOT_CACHEABLE = 32,
  51   RESOURCE_STATUS_HEADERS_MISSING = 64,
  52   RESOURCE_STATUS_MAX = 128,
  53 };
  54
  55 // For reporting various interesting events that occur during the loading of a
  56 // single main frame.
  57 enum NavigationEvent {
  58   NAVIGATION_EVENT_REQUEST_STARTED = 0,
  59   NAVIGATION_EVENT_REQUEST_REDIRECTED = 1,
  60   NAVIGATION_EVENT_REQUEST_REDIRECTED_EMPTY_URL = 2,
  61   NAVIGATION_EVENT_REQUEST_EXPIRED = 3,
  62   NAVIGATION_EVENT_RESPONSE_STARTED = 4,
  63   NAVIGATION_EVENT_ONLOAD = 5,
  64   NAVIGATION_EVENT_ONLOAD_EMPTY_URL = 6,
  65   NAVIGATION_EVENT_ONLOAD_UNTRACKED_URL = 7,
  66   NAVIGATION_EVENT_ONLOAD_TRACKED_URL = 8,
  67   NAVIGATION_EVENT_SHOULD_TRACK_URL = 9,
  68   NAVIGATION_EVENT_SHOULD_NOT_TRACK_URL = 10,
  69   NAVIGATION_EVENT_URL_TABLE_FULL = 11,
  70   NAVIGATION_EVENT_HAVE_PREDICTIONS_FOR_URL = 12,
  71   NAVIGATION_EVENT_NO_PREDICTIONS_FOR_URL = 13,
  72   NAVIGATION_EVENT_MAIN_FRAME_URL_TOO_LONG = 14,
  73   NAVIGATION_EVENT_HOST_TOO_LONG = 15,
  74   NAVIGATION_EVENT_COUNT = 16,
  75 };
  76
  77 // For reporting events of interest that are not tied to any navigation.
  78 enum ReportingEvent {
  79   REPORTING_EVENT_ALL_HISTORY_CLEARED = 0,
  80   REPORTING_EVENT_PARTIAL_HISTORY_CLEARED = 1,
  81   REPORTING_EVENT_COUNT = 2
  82 };
  83
  84 void RecordNavigationEvent(NavigationEvent event) {
  85   UMA_HISTOGRAM_ENUMERATION("ResourcePrefetchPredictor.NavigationEvent",
  86                             event,
  87                             NAVIGATION_EVENT_COUNT);
  88 }
  89
  90 // These are additional connection types for
  91 // net::NetworkChangeNotifier::ConnectionType. They have negative values in case
  92 // the original network connection types expand.
  93 enum AdditionalConnectionType {
  94   CONNECTION_ALL = -2,
  95   CONNECTION_CELLULAR = -1
  96 };
  97
  98 std::string GetNetTypeStr() {
  99   switch (net::NetworkChangeNotifier::GetConnectionType()) {
 100     case net::NetworkChangeNotifier::CONNECTION_ETHERNET:
 101       return "Ethernet";
 102     case net::NetworkChangeNotifier::CONNECTION_WIFI:
 103       return "WiFi";
 104     case net::NetworkChangeNotifier::CONNECTION_2G:
 105       return "2G";
 106     case net::NetworkChangeNotifier::CONNECTION_3G:
 107       return "3G";
 108     case net::NetworkChangeNotifier::CONNECTION_4G:
 109       return "4G";
 110     case net::NetworkChangeNotifier::CONNECTION_NONE:
 111       return "None";
 112     case net::NetworkChangeNotifier::CONNECTION_BLUETOOTH:
 113       return "Bluetooth";
 114     case net::NetworkChangeNotifier::CONNECTION_UNKNOWN:
 115     default:
 116       break;
 117   }
 118   return "Unknown";
 119 }
 120
 121 void ReportPrefetchedNetworkType(int type) {
 122   UMA_HISTOGRAM_SPARSE_SLOWLY(
 123       "ResourcePrefetchPredictor.NetworkType.Prefetched",
 124       type);
 125 }
 126
 127 void ReportNotPrefetchedNetworkType(int type) {
 128   UMA_HISTOGRAM_SPARSE_SLOWLY(
 129       "ResourcePrefetchPredictor.NetworkType.NotPrefetched",
 130       type);
 131 }
 132
 133 }  // namespace
 134
 135 namespace predictors {
 136
 137 ////////////////////////////////////////////////////////////////////////////////
 138 // History lookup task.
 139
 140 // Used to fetch the visit count for a URL from the History database.
 141 class GetUrlVisitCountTask : public history::HistoryDBTask {
 142  public:
 143   typedef ResourcePrefetchPredictor::URLRequestSummary URLRequestSummary;
 144   typedef base::Callback<void(
 145       size_t,   // Visit count.
 146       const NavigationID&,
 147       const std::vector<URLRequestSummary>&)> VisitInfoCallback;
 148
 149   GetUrlVisitCountTask(
 150       const NavigationID& navigation_id,
 151       std::vector<URLRequestSummary>* requests,
 152       VisitInfoCallback callback)
 153       : visit_count_(0),
 154         navigation_id_(navigation_id),
 155         requests_(requests),
 156         callback_(callback) {
 157     DCHECK(requests_.get());
 158   }
 159
 160   bool RunOnDBThread(history::HistoryBackend* backend,
 161                      history::HistoryDatabase* db) override {
 162     history::URLRow url_row;
 163     if (db->GetRowForURL(navigation_id_.main_frame_url, &url_row))
 164       visit_count_ = url_row.visit_count();
 165     return true;
 166   }
 167
 168   void DoneRunOnMainThread() override {
 169     callback_.Run(visit_count_, navigation_id_, *requests_);
 170   }
 171
 172  private:
 173   ~GetUrlVisitCountTask() override {}
 174
 175   int visit_count_;
 176   NavigationID navigation_id_;
 177   scoped_ptr<std::vector<URLRequestSummary> > requests_;
 178   VisitInfoCallback callback_;
 179
 180   DISALLOW_COPY_AND_ASSIGN(GetUrlVisitCountTask);
 181 };
 182
 183 ////////////////////////////////////////////////////////////////////////////////
 184 // ResourcePrefetchPredictor static functions.
 185
 186 // static
 187 bool ResourcePrefetchPredictor::ShouldRecordRequest(
 188     net::URLRequest* request,
 189     content::ResourceType resource_type) {
 190   const content::ResourceRequestInfo* request_info =
 191       content::ResourceRequestInfo::ForRequest(request);
 192   if (!request_info)
 193     return false;
 194
 195   if (!request_info->IsMainFrame())
 196     return false;
 197
 198   return resource_type == content::RESOURCE_TYPE_MAIN_FRAME &&
 199       IsHandledMainPage(request);
 200 }
 201
 202 // static
 203 bool ResourcePrefetchPredictor::ShouldRecordResponse(
 204     net::URLRequest* response) {
 205   const content::ResourceRequestInfo* request_info =
 206       content::ResourceRequestInfo::ForRequest(response);
 207   if (!request_info)
 208     return false;
 209
 210   if (!request_info->IsMainFrame())
 211     return false;
 212
 213   return request_info->GetResourceType() == content::RESOURCE_TYPE_MAIN_FRAME ?
 214       IsHandledMainPage(response) : IsHandledSubresource(response);
 215 }
 216
 217 // static
 218 bool ResourcePrefetchPredictor::ShouldRecordRedirect(
 219     net::URLRequest* response) {
 220   const content::ResourceRequestInfo* request_info =
 221       content::ResourceRequestInfo::ForRequest(response);
 222   if (!request_info)
 223     return false;
 224
 225   if (!request_info->IsMainFrame())
 226     return false;
 227
 228   return request_info->GetResourceType() == content::RESOURCE_TYPE_MAIN_FRAME &&
 229       IsHandledMainPage(response);
 230 }
 231
 232 // static
 233 bool ResourcePrefetchPredictor::IsHandledMainPage(net::URLRequest* request) {
 234   return request->original_url().scheme() == url::kHttpScheme;
 235 }
 236
 237 // static
 238 bool ResourcePrefetchPredictor::IsHandledSubresource(
 239     net::URLRequest* response) {
 240   int resource_status = 0;
 241   if (response->first_party_for_cookies().scheme() != url::kHttpScheme)
 242     resource_status |= RESOURCE_STATUS_NOT_HTTP_PAGE;
 243
 244   if (response->original_url().scheme() != url::kHttpScheme)
 245     resource_status |= RESOURCE_STATUS_NOT_HTTP_RESOURCE;
 246
 247   std::string mime_type;
 248   response->GetMimeType(&mime_type);
 249   if (!mime_type.empty() &&
 250       !net::IsSupportedImageMimeType(mime_type.c_str()) &&
 251       !net::IsSupportedJavascriptMimeType(mime_type.c_str()) &&
 252       !net::MatchesMimeType("text/css", mime_type)) {
 253     resource_status |= RESOURCE_STATUS_UNSUPPORTED_MIME_TYPE;
 254   }
 255
 256   if (response->method() != "GET")
 257     resource_status |= RESOURCE_STATUS_NOT_GET;
 258
 259   if (response->original_url().spec().length() >
 260       ResourcePrefetchPredictorTables::kMaxStringLength) {
 261     resource_status |= RESOURCE_STATUS_URL_TOO_LONG;
 262   }
 263
 264   if (!response->response_info().headers.get())
 265     resource_status |= RESOURCE_STATUS_HEADERS_MISSING;
 266
 267   if (!IsCacheable(response))
 268     resource_status |= RESOURCE_STATUS_NOT_CACHEABLE;
 269
 270   UMA_HISTOGRAM_ENUMERATION("ResourcePrefetchPredictor.ResourceStatus",
 271                             resource_status,
 272                             RESOURCE_STATUS_MAX);
 273
 274   return resource_status == 0;
 275 }
 276
 277 // static
 278 bool ResourcePrefetchPredictor::IsCacheable(const net::URLRequest* response) {
 279   if (response->was_cached())
 280     return true;
 281
 282   // For non cached responses, we will ensure that the freshness lifetime is
 283   // some sane value.
 284   const net::HttpResponseInfo& response_info = response->response_info();
 285   if (!response_info.headers.get())
 286     return false;
 287   base::Time response_time(response_info.response_time);
 288   response_time += base::TimeDelta::FromSeconds(1);
 289   base::TimeDelta freshness =
 290       response_info.headers->GetFreshnessLifetimes(response_time).freshness;
 291   return freshness > base::TimeDelta();
 292 }
 293
 294 // static
 295 content::ResourceType ResourcePrefetchPredictor::GetResourceTypeFromMimeType(
 296     const std::string& mime_type,
 297     content::ResourceType fallback) {
 298   if (net::IsSupportedImageMimeType(mime_type.c_str()))
 299     return content::RESOURCE_TYPE_IMAGE;
 300   else if (net::IsSupportedJavascriptMimeType(mime_type.c_str()))
 301     return content::RESOURCE_TYPE_SCRIPT;
 302   else if (net::MatchesMimeType("text/css", mime_type))
 303     return content::RESOURCE_TYPE_STYLESHEET;
 304   else
 305     return fallback;
 306 }
 307
 308 ////////////////////////////////////////////////////////////////////////////////
 309 // ResourcePrefetchPredictor structs.
 310
 311 ResourcePrefetchPredictor::URLRequestSummary::URLRequestSummary()
 312     : resource_type(content::RESOURCE_TYPE_LAST_TYPE),
 313       was_cached(false) {
 314 }
 315
 316 ResourcePrefetchPredictor::URLRequestSummary::URLRequestSummary(
 317     const URLRequestSummary& other)
 318         : navigation_id(other.navigation_id),
 319           resource_url(other.resource_url),
 320           resource_type(other.resource_type),
 321           mime_type(other.mime_type),
 322           was_cached(other.was_cached),
 323           redirect_url(other.redirect_url) {
 324 }
 325
 326 ResourcePrefetchPredictor::URLRequestSummary::~URLRequestSummary() {
 327 }
 328
 329 ResourcePrefetchPredictor::Result::Result(
 330     PrefetchKeyType i_key_type,
 331     ResourcePrefetcher::RequestVector* i_requests)
 332     : key_type(i_key_type),
 333       requests(i_requests) {
 334 }
 335
 336 ResourcePrefetchPredictor::Result::~Result() {
 337 }
 338
 339 ////////////////////////////////////////////////////////////////////////////////
 340 // ResourcePrefetchPredictor.
 341
 342 ResourcePrefetchPredictor::ResourcePrefetchPredictor(
 343     const ResourcePrefetchPredictorConfig& config,
 344     Profile* profile)
 345     : profile_(profile),
 346       config_(config),
 347       initialization_state_(NOT_INITIALIZED),
 348       tables_(PredictorDatabaseFactory::GetForProfile(profile)
 349                   ->resource_prefetch_tables()),
 350       results_map_deleter_(&results_map_),
 351       history_service_observer_(this) {
 352   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 353
 354   // Some form of learning has to be enabled.
 355   DCHECK(config_.IsLearningEnabled());
 356   if (config_.IsURLPrefetchingEnabled(profile_))
 357     DCHECK(config_.IsURLLearningEnabled());
 358   if (config_.IsHostPrefetchingEnabled(profile_))
 359     DCHECK(config_.IsHostLearningEnabled());
 360 }
 361
 362 ResourcePrefetchPredictor::~ResourcePrefetchPredictor() {
 363 }
 364
 365 void ResourcePrefetchPredictor::RecordURLRequest(
 366     const URLRequestSummary& request) {
 367   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 368   if (initialization_state_ != INITIALIZED)
 369     return;
 370
 371   CHECK_EQ(request.resource_type, content::RESOURCE_TYPE_MAIN_FRAME);
 372   OnMainFrameRequest(request);
 373 }
 374
 375 void ResourcePrefetchPredictor::RecordURLResponse(
 376     const URLRequestSummary& response) {
 377   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 378   if (initialization_state_ != INITIALIZED)
 379     return;
 380
 381   if (response.resource_type == content::RESOURCE_TYPE_MAIN_FRAME)
 382     OnMainFrameResponse(response);
 383   else
 384     OnSubresourceResponse(response);
 385 }
 386
 387 void ResourcePrefetchPredictor::RecordURLRedirect(
 388     const URLRequestSummary& response) {
 389   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 390   if (initialization_state_ != INITIALIZED)
 391     return;
 392
 393   CHECK_EQ(response.resource_type, content::RESOURCE_TYPE_MAIN_FRAME);
 394   OnMainFrameRedirect(response);
 395 }
 396
 397 void ResourcePrefetchPredictor::RecordMainFrameLoadComplete(
 398     const NavigationID& navigation_id) {
 399   switch (initialization_state_) {
 400     case NOT_INITIALIZED:
 401       StartInitialization();
 402       break;
 403     case INITIALIZING:
 404       break;
 405     case INITIALIZED: {
 406       RecordNavigationEvent(NAVIGATION_EVENT_ONLOAD);
 407       // WebContents can return an empty URL if the navigation entry
 408       // corresponding to the navigation has not been created yet.
 409       if (navigation_id.main_frame_url.is_empty())
 410         RecordNavigationEvent(NAVIGATION_EVENT_ONLOAD_EMPTY_URL);
 411       else
 412         OnNavigationComplete(navigation_id);
 413       break;
 414     }
 415     default:
 416       NOTREACHED() << "Unexpected initialization_state_: "
 417                    << initialization_state_;
 418   }
 419 }
 420
 421 void ResourcePrefetchPredictor::FinishedPrefetchForNavigation(
 422     const NavigationID& navigation_id,
 423     PrefetchKeyType key_type,
 424     ResourcePrefetcher::RequestVector* requests) {
 425   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 426
 427   Result* result = new Result(key_type, requests);
 428   // Add the results to the results map.
 429   if (!results_map_.insert(std::make_pair(navigation_id, result)).second) {
 430     DLOG(FATAL) << "Returning results for existing navigation.";
 431     delete result;
 432   }
 433 }
 434
 435 void ResourcePrefetchPredictor::Shutdown() {
 436   if (prefetch_manager_.get()) {
 437     prefetch_manager_->ShutdownOnUIThread();
 438     prefetch_manager_ = NULL;
 439   }
 440   history_service_observer_.RemoveAll();
 441 }
 442
 443 void ResourcePrefetchPredictor::OnMainFrameRequest(
 444     const URLRequestSummary& request) {
 445   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 446   DCHECK_EQ(INITIALIZED, initialization_state_);
 447
 448   RecordNavigationEvent(NAVIGATION_EVENT_REQUEST_STARTED);
 449
 450   StartPrefetching(request.navigation_id);
 451
 452   // Cleanup older navigations.
 453   CleanupAbandonedNavigations(request.navigation_id);
 454
 455   // New empty navigation entry.
 456   inflight_navigations_.insert(std::make_pair(
 457       request.navigation_id,
 458       make_linked_ptr(new std::vector<URLRequestSummary>())));
 459 }
 460
 461 void ResourcePrefetchPredictor::OnMainFrameResponse(
 462     const URLRequestSummary& response) {
 463   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 464   if (initialization_state_ != INITIALIZED)
 465     return;
 466
 467   RecordNavigationEvent(NAVIGATION_EVENT_RESPONSE_STARTED);
 468
 469   StopPrefetching(response.navigation_id);
 470 }
 471
 472 void ResourcePrefetchPredictor::OnMainFrameRedirect(
 473     const URLRequestSummary& response) {
 474   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 475
 476   RecordNavigationEvent(NAVIGATION_EVENT_REQUEST_REDIRECTED);
 477
 478   // TODO(shishir): There are significant gains to be had here if we can use the
 479   // start URL in a redirect chain as the key to start prefetching. We can save
 480   // of redirect times considerably assuming that the redirect chains do not
 481   // change.
 482
 483   // Stop any inflight prefetching. Remove the older navigation.
 484   StopPrefetching(response.navigation_id);
 485   inflight_navigations_.erase(response.navigation_id);
 486
 487   // A redirect will not lead to another OnMainFrameRequest call, so record the
 488   // redirect url as a new navigation.
 489
 490   // The redirect url may be empty if the url was invalid.
 491   if (response.redirect_url.is_empty()) {
 492     RecordNavigationEvent(NAVIGATION_EVENT_REQUEST_REDIRECTED_EMPTY_URL);
 493     return;
 494   }
 495
 496   NavigationID navigation_id(response.navigation_id);
 497   navigation_id.main_frame_url = response.redirect_url;
 498   inflight_navigations_.insert(std::make_pair(
 499       navigation_id,
 500       make_linked_ptr(new std::vector<URLRequestSummary>())));
 501 }
 502
 503 void ResourcePrefetchPredictor::OnSubresourceResponse(
 504     const URLRequestSummary& response) {
 505   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 506
 507   NavigationMap::const_iterator nav_it =
 508         inflight_navigations_.find(response.navigation_id);
 509   if (nav_it == inflight_navigations_.end()) {
 510     return;
 511   }
 512
 513   nav_it->second->push_back(response);
 514 }
 515
 516 void ResourcePrefetchPredictor::OnNavigationComplete(
 517     const NavigationID& navigation_id) {
 518   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 519
 520   NavigationMap::iterator nav_it =
 521       inflight_navigations_.find(navigation_id);
 522   if (nav_it == inflight_navigations_.end()) {
 523     RecordNavigationEvent(NAVIGATION_EVENT_ONLOAD_UNTRACKED_URL);
 524     return;
 525   }
 526   RecordNavigationEvent(NAVIGATION_EVENT_ONLOAD_TRACKED_URL);
 527
 528   // Report any stats.
 529   base::TimeDelta plt = base::TimeTicks::Now() - navigation_id.creation_time;
 530   ReportPageLoadTimeStats(plt);
 531   if (prefetch_manager_.get()) {
 532     ResultsMap::iterator results_it = results_map_.find(navigation_id);
 533     bool have_prefetch_results = results_it != results_map_.end();
 534     UMA_HISTOGRAM_BOOLEAN("ResourcePrefetchPredictor.HavePrefetchResults",
 535                           have_prefetch_results);
 536     if (have_prefetch_results) {
 537       ReportAccuracyStats(results_it->second->key_type,
 538                           *(nav_it->second),
 539                           results_it->second->requests.get());
 540       ReportPageLoadTimePrefetchStats(
 541           plt,
 542           true,
 543           base::Bind(&ReportPrefetchedNetworkType),
 544           results_it->second->key_type);
 545     } else {
 546       ReportPageLoadTimePrefetchStats(
 547           plt,
 548           false,
 549           base::Bind(&ReportNotPrefetchedNetworkType),
 550           PREFETCH_KEY_TYPE_URL);
 551     }
 552   } else {
 553     scoped_ptr<ResourcePrefetcher::RequestVector> requests(
 554         new ResourcePrefetcher::RequestVector);
 555     PrefetchKeyType key_type;
 556     if (GetPrefetchData(navigation_id, requests.get(), &key_type)) {
 557       RecordNavigationEvent(NAVIGATION_EVENT_HAVE_PREDICTIONS_FOR_URL);
 558       ReportPredictedAccuracyStats(key_type,
 559                                    *(nav_it->second),
 560                                    *requests);
 561     } else {
 562       RecordNavigationEvent(NAVIGATION_EVENT_NO_PREDICTIONS_FOR_URL);
 563     }
 564   }
 565
 566   // Remove the navigation from the inflight navigations.
 567   std::vector<URLRequestSummary>* requests = (nav_it->second).release();
 568   inflight_navigations_.erase(nav_it);
 569
 570   // Kick off history lookup to determine if we should record the URL.
 571   history::HistoryService* history_service =
 572       HistoryServiceFactory::GetForProfile(profile_,
 573                                            ServiceAccessType::EXPLICIT_ACCESS);
 574   DCHECK(history_service);
 575   history_service->ScheduleDBTask(
 576       scoped_ptr<history::HistoryDBTask>(
 577           new GetUrlVisitCountTask(
 578               navigation_id,
 579               requests,
 580               base::Bind(&ResourcePrefetchPredictor::OnVisitCountLookup,
 581                          AsWeakPtr()))),
 582       &history_lookup_consumer_);
 583 }
 584
 585 bool ResourcePrefetchPredictor::GetPrefetchData(
 586     const NavigationID& navigation_id,
 587     ResourcePrefetcher::RequestVector* prefetch_requests,
 588     PrefetchKeyType* key_type) {
 589   DCHECK(prefetch_requests);
 590   DCHECK(key_type);
 591
 592   *key_type = PREFETCH_KEY_TYPE_URL;
 593   const GURL& main_frame_url = navigation_id.main_frame_url;
 594
 595   bool use_url_data = config_.IsPrefetchingEnabled(profile_) ?
 596       config_.IsURLPrefetchingEnabled(profile_) :
 597       config_.IsURLLearningEnabled();
 598   if (use_url_data) {
 599     PrefetchDataMap::const_iterator iterator =
 600         url_table_cache_->find(main_frame_url.spec());
 601     if (iterator != url_table_cache_->end())
 602       PopulatePrefetcherRequest(iterator->second, prefetch_requests);
 603   }
 604   if (!prefetch_requests->empty())
 605     return true;
 606
 607   bool use_host_data = config_.IsPrefetchingEnabled(profile_) ?
 608       config_.IsHostPrefetchingEnabled(profile_) :
 609       config_.IsHostLearningEnabled();
 610   if (use_host_data) {
 611     PrefetchDataMap::const_iterator iterator =
 612         host_table_cache_->find(main_frame_url.host());
 613     if (iterator != host_table_cache_->end()) {
 614       *key_type = PREFETCH_KEY_TYPE_HOST;
 615       PopulatePrefetcherRequest(iterator->second, prefetch_requests);
 616     }
 617   }
 618
 619   return !prefetch_requests->empty();
 620 }
 621
 622 void ResourcePrefetchPredictor::PopulatePrefetcherRequest(
 623     const PrefetchData& data,
 624     ResourcePrefetcher::RequestVector* requests) {
 625   for (ResourceRows::const_iterator it = data.resources.begin();
 626        it != data.resources.end(); ++it) {
 627     float confidence = static_cast<float>(it->number_of_hits) /
 628         (it->number_of_hits + it->number_of_misses);
 629     if (confidence < config_.min_resource_confidence_to_trigger_prefetch ||
 630         it->number_of_hits < config_.min_resource_hits_to_trigger_prefetch) {
 631       continue;
 632     }
 633
 634     ResourcePrefetcher::Request* req = new ResourcePrefetcher::Request(
 635         it->resource_url);
 636     requests->push_back(req);
 637   }
 638 }
 639
 640 void ResourcePrefetchPredictor::StartPrefetching(
 641     const NavigationID& navigation_id) {
 642   if (!prefetch_manager_.get())  // Prefetching not enabled.
 643     return;
 644
 645   // Prefer URL based data first.
 646   scoped_ptr<ResourcePrefetcher::RequestVector> requests(
 647       new ResourcePrefetcher::RequestVector);
 648   PrefetchKeyType key_type;
 649   if (!GetPrefetchData(navigation_id, requests.get(), &key_type)) {
 650     // No prefetching data at host or URL level.
 651     return;
 652   }
 653
 654   BrowserThread::PostTask(BrowserThread::IO, FROM_HERE,
 655       base::Bind(&ResourcePrefetcherManager::MaybeAddPrefetch,
 656                  prefetch_manager_,
 657                  navigation_id,
 658                  key_type,
 659                  base::Passed(&requests)));
 660 }
 661
 662 void ResourcePrefetchPredictor::StopPrefetching(
 663     const NavigationID& navigation_id) {
 664   if (!prefetch_manager_.get())  // Not enabled.
 665     return;
 666
 667   BrowserThread::PostTask(
 668       BrowserThread::IO, FROM_HERE,
 669       base::Bind(&ResourcePrefetcherManager::MaybeRemovePrefetch,
 670                  prefetch_manager_,
 671                  navigation_id));
 672 }
 673
 674 void ResourcePrefetchPredictor::StartInitialization() {
 675   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 676
 677   DCHECK_EQ(NOT_INITIALIZED, initialization_state_);
 678   initialization_state_ = INITIALIZING;
 679
 680   // Create local caches using the database as loaded.
 681   scoped_ptr<PrefetchDataMap> url_data_map(new PrefetchDataMap());
 682   scoped_ptr<PrefetchDataMap> host_data_map(new PrefetchDataMap());
 683   PrefetchDataMap* url_data_ptr = url_data_map.get();
 684   PrefetchDataMap* host_data_ptr = host_data_map.get();
 685
 686   BrowserThread::PostTaskAndReply(
 687       BrowserThread::DB, FROM_HERE,
 688       base::Bind(&ResourcePrefetchPredictorTables::GetAllData,
 689                  tables_, url_data_ptr, host_data_ptr),
 690       base::Bind(&ResourcePrefetchPredictor::CreateCaches, AsWeakPtr(),
 691                  base::Passed(&url_data_map), base::Passed(&host_data_map)));
 692 }
 693
 694 void ResourcePrefetchPredictor::CreateCaches(
 695     scoped_ptr<PrefetchDataMap> url_data_map,
 696     scoped_ptr<PrefetchDataMap> host_data_map) {
 697   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 698
 699   DCHECK_EQ(INITIALIZING, initialization_state_);
 700   DCHECK(!url_table_cache_);
 701   DCHECK(!host_table_cache_);
 702   DCHECK(inflight_navigations_.empty());
 703
 704   url_table_cache_.reset(url_data_map.release());
 705   host_table_cache_.reset(host_data_map.release());
 706
 707   UMA_HISTOGRAM_COUNTS("ResourcePrefetchPredictor.UrlTableMainFrameUrlCount",
 708                        url_table_cache_->size());
 709   UMA_HISTOGRAM_COUNTS("ResourcePrefetchPredictor.HostTableHostCount",
 710                        host_table_cache_->size());
 711
 712   ConnectToHistoryService();
 713 }
 714
 715 void ResourcePrefetchPredictor::OnHistoryAndCacheLoaded() {
 716   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 717   DCHECK_EQ(INITIALIZING, initialization_state_);
 718
 719   // Initialize the prefetch manager only if prefetching is enabled.
 720   if (config_.IsPrefetchingEnabled(profile_)) {
 721     prefetch_manager_ = new ResourcePrefetcherManager(
 722         this, config_, profile_->GetRequestContext());
 723   }
 724   initialization_state_ = INITIALIZED;
 725 }
 726
 727 void ResourcePrefetchPredictor::CleanupAbandonedNavigations(
 728     const NavigationID& navigation_id) {
 729   static const base::TimeDelta max_navigation_age =
 730       base::TimeDelta::FromSeconds(config_.max_navigation_lifetime_seconds);
 731
 732   base::TimeTicks time_now = base::TimeTicks::Now();
 733   for (NavigationMap::iterator it = inflight_navigations_.begin();
 734        it != inflight_navigations_.end();) {
 735     if (it->first.IsSameRenderer(navigation_id) ||
 736         (time_now - it->first.creation_time > max_navigation_age)) {
 737       inflight_navigations_.erase(it++);
 738       RecordNavigationEvent(NAVIGATION_EVENT_REQUEST_EXPIRED);
 739     } else {
 740       ++it;
 741     }
 742   }
 743   for (ResultsMap::iterator it = results_map_.begin();
 744        it != results_map_.end();) {
 745     if (it->first.IsSameRenderer(navigation_id) ||
 746         (time_now - it->first.creation_time > max_navigation_age)) {
 747       delete it->second;
 748       results_map_.erase(it++);
 749     } else {
 750       ++it;
 751     }
 752   }
 753 }
 754
 755 void ResourcePrefetchPredictor::DeleteAllUrls() {
 756   inflight_navigations_.clear();
 757   url_table_cache_->clear();
 758   host_table_cache_->clear();
 759
 760   BrowserThread::PostTask(BrowserThread::DB, FROM_HERE,
 761       base::Bind(&ResourcePrefetchPredictorTables::DeleteAllData, tables_));
 762 }
 763
 764 void ResourcePrefetchPredictor::DeleteUrls(const history::URLRows& urls) {
 765   // Check all the urls in the database and pick out the ones that are present
 766   // in the cache.
 767   std::vector<std::string> urls_to_delete, hosts_to_delete;
 768
 769   for (const auto& it : urls) {
 770     const std::string& url_spec = it.url().spec();
 771     if (url_table_cache_->find(url_spec) != url_table_cache_->end()) {
 772       urls_to_delete.push_back(url_spec);
 773       url_table_cache_->erase(url_spec);
 774     }
 775
 776     const std::string& host = it.url().host();
 777     if (host_table_cache_->find(host) != host_table_cache_->end()) {
 778       hosts_to_delete.push_back(host);
 779       host_table_cache_->erase(host);
 780     }
 781   }
 782
 783   if (!urls_to_delete.empty() || !hosts_to_delete.empty()) {
 784     BrowserThread::PostTask(BrowserThread::DB, FROM_HERE,
 785         base::Bind(&ResourcePrefetchPredictorTables::DeleteData,
 786                    tables_,
 787                    urls_to_delete,
 788                    hosts_to_delete));
 789   }
 790 }
 791
 792 void ResourcePrefetchPredictor::RemoveOldestEntryInPrefetchDataMap(
 793     PrefetchKeyType key_type,
 794     PrefetchDataMap* data_map) {
 795   if (data_map->empty())
 796     return;
 797
 798   base::Time oldest_time;
 799   std::string key_to_delete;
 800   for (PrefetchDataMap::iterator it = data_map->begin();
 801        it != data_map->end(); ++it) {
 802     if (key_to_delete.empty() || it->second.last_visit < oldest_time) {
 803       key_to_delete = it->first;
 804       oldest_time = it->second.last_visit;
 805     }
 806   }
 807
 808   data_map->erase(key_to_delete);
 809     BrowserThread::PostTask(BrowserThread::DB, FROM_HERE,
 810         base::Bind(&ResourcePrefetchPredictorTables::DeleteSingleDataPoint,
 811                    tables_,
 812                    key_to_delete,
 813                    key_type));
 814 }
 815
 816 void ResourcePrefetchPredictor::OnVisitCountLookup(
 817     size_t visit_count,
 818     const NavigationID& navigation_id,
 819     const std::vector<URLRequestSummary>& requests) {
 820   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 821
 822   UMA_HISTOGRAM_COUNTS("ResourcePrefetchPredictor.HistoryVisitCountForUrl",
 823                        visit_count);
 824
 825   // URL level data - merge only if we are already saving the data, or we it
 826   // meets the cutoff requirement.
 827   const std::string url_spec = navigation_id.main_frame_url.spec();
 828   bool already_tracking = url_table_cache_->find(url_spec) !=
 829       url_table_cache_->end();
 830   bool should_track_url = already_tracking ||
 831       (visit_count >= config_.min_url_visit_count);
 832
 833   if (should_track_url) {
 834     RecordNavigationEvent(NAVIGATION_EVENT_SHOULD_TRACK_URL);
 835
 836     if (config_.IsURLLearningEnabled()) {
 837       LearnNavigation(url_spec, PREFETCH_KEY_TYPE_URL, requests,
 838                       config_.max_urls_to_track, url_table_cache_.get());
 839     }
 840   } else {
 841     RecordNavigationEvent(NAVIGATION_EVENT_SHOULD_NOT_TRACK_URL);
 842   }
 843
 844   // Host level data - no cutoff, always learn the navigation if enabled.
 845   if (config_.IsHostLearningEnabled()) {
 846     LearnNavigation(navigation_id.main_frame_url.host(),
 847                     PREFETCH_KEY_TYPE_HOST,
 848                     requests,
 849                     config_.max_hosts_to_track,
 850                     host_table_cache_.get());
 851   }
 852
 853   // Remove the navigation from the results map.
 854   ResultsMap::iterator results_it = results_map_.find(navigation_id);
 855   if (results_it != results_map_.end()) {
 856     delete results_it->second;
 857     results_map_.erase(results_it);
 858   }
 859 }
 860
 861 void ResourcePrefetchPredictor::LearnNavigation(
 862     const std::string& key,
 863     PrefetchKeyType key_type,
 864     const std::vector<URLRequestSummary>& new_resources,
 865     size_t max_data_map_size,
 866     PrefetchDataMap* data_map) {
 867   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 868
 869   // If the primary key is too long reject it.
 870   if (key.length() > ResourcePrefetchPredictorTables::kMaxStringLength) {
 871     if (key_type == PREFETCH_KEY_TYPE_HOST)
 872       RecordNavigationEvent(NAVIGATION_EVENT_HOST_TOO_LONG);
 873     else
 874       RecordNavigationEvent(NAVIGATION_EVENT_MAIN_FRAME_URL_TOO_LONG);
 875     return;
 876   }
 877
 878   PrefetchDataMap::iterator cache_entry = data_map->find(key);
 879   if (cache_entry == data_map->end()) {
 880     if (data_map->size() >= max_data_map_size) {
 881       // The table is full, delete an entry.
 882       RemoveOldestEntryInPrefetchDataMap(key_type, data_map);
 883     }
 884
 885     cache_entry = data_map->insert(std::make_pair(
 886         key, PrefetchData(key_type, key))).first;
 887     cache_entry->second.last_visit = base::Time::Now();
 888     size_t new_resources_size = new_resources.size();
 889     std::set<GURL> resources_seen;
 890     for (size_t i = 0; i < new_resources_size; ++i) {
 891       if (resources_seen.find(new_resources[i].resource_url) !=
 892           resources_seen.end()) {
 893         continue;
 894       }
 895       ResourceRow row_to_add;
 896       row_to_add.resource_url = new_resources[i].resource_url;
 897       row_to_add.resource_type = new_resources[i].resource_type;
 898       row_to_add.number_of_hits = 1;
 899       row_to_add.average_position = i + 1;
 900       cache_entry->second.resources.push_back(row_to_add);
 901       resources_seen.insert(new_resources[i].resource_url);
 902     }
 903   } else {
 904     ResourceRows& old_resources = cache_entry->second.resources;
 905     cache_entry->second.last_visit = base::Time::Now();
 906
 907     // Build indices over the data.
 908     std::map<GURL, int> new_index, old_index;
 909     int new_resources_size = static_cast<int>(new_resources.size());
 910     for (int i = 0; i < new_resources_size; ++i) {
 911       const URLRequestSummary& summary = new_resources[i];
 912       // Take the first occurence of every url.
 913       if (new_index.find(summary.resource_url) == new_index.end())
 914         new_index[summary.resource_url] = i;
 915     }
 916     int old_resources_size = static_cast<int>(old_resources.size());
 917     for (int i = 0; i < old_resources_size; ++i) {
 918       const ResourceRow& row = old_resources[i];
 919       DCHECK(old_index.find(row.resource_url) == old_index.end());
 920       old_index[row.resource_url] = i;
 921     }
 922
 923     // Go through the old urls and update their hit/miss counts.
 924     for (int i = 0; i < old_resources_size; ++i) {
 925       ResourceRow& old_row = old_resources[i];
 926       if (new_index.find(old_row.resource_url) == new_index.end()) {
 927         ++old_row.number_of_misses;
 928         ++old_row.consecutive_misses;
 929       } else {
 930         const URLRequestSummary& new_row =
 931             new_resources[new_index[old_row.resource_url]];
 932
 933         // Update the resource type since it could have changed.
 934         if (new_row.resource_type != content::RESOURCE_TYPE_LAST_TYPE)
 935           old_row.resource_type = new_row.resource_type;
 936
 937         int position = new_index[old_row.resource_url] + 1;
 938         int total = old_row.number_of_hits + old_row.number_of_misses;
 939         old_row.average_position =
 940             ((old_row.average_position * total) + position) / (total + 1);
 941         ++old_row.number_of_hits;
 942         old_row.consecutive_misses = 0;
 943       }
 944     }
 945
 946     // Add the new ones that we have not seen before.
 947     for (int i = 0; i < new_resources_size; ++i) {
 948       const URLRequestSummary& summary = new_resources[i];
 949       if (old_index.find(summary.resource_url) != old_index.end())
 950         continue;
 951
 952       // Only need to add new stuff.
 953       ResourceRow row_to_add;
 954       row_to_add.resource_url = summary.resource_url;
 955       row_to_add.resource_type = summary.resource_type;
 956       row_to_add.number_of_hits = 1;
 957       row_to_add.average_position = i + 1;
 958       old_resources.push_back(row_to_add);
 959
 960       // To ensure we dont add the same url twice.
 961       old_index[summary.resource_url] = 0;
 962     }
 963   }
 964
 965   // Trim and sort the resources after the update.
 966   ResourceRows& resources = cache_entry->second.resources;
 967   for (ResourceRows::iterator it = resources.begin();
 968        it != resources.end();) {
 969     it->UpdateScore();
 970     if (it->consecutive_misses >= config_.max_consecutive_misses)
 971       it = resources.erase(it);
 972     else
 973       ++it;
 974   }
 975   std::sort(resources.begin(), resources.end(),
 976             ResourcePrefetchPredictorTables::ResourceRowSorter());
 977   if (resources.size() > config_.max_resources_per_entry)
 978     resources.resize(config_.max_resources_per_entry);
 979
 980   // If the row has no resources, remove it from the cache and delete the
 981   // entry in the database. Else update the database.
 982   if (resources.empty()) {
 983     data_map->erase(key);
 984     BrowserThread::PostTask(
 985         BrowserThread::DB, FROM_HERE,
 986         base::Bind(&ResourcePrefetchPredictorTables::DeleteSingleDataPoint,
 987                    tables_,
 988                    key,
 989                    key_type));
 990   } else {
 991     bool is_host = key_type == PREFETCH_KEY_TYPE_HOST;
 992     PrefetchData empty_data(
 993         !is_host ? PREFETCH_KEY_TYPE_HOST : PREFETCH_KEY_TYPE_URL,
 994         std::string());
 995     const PrefetchData& host_data = is_host ? cache_entry->second : empty_data;
 996     const PrefetchData& url_data = is_host ? empty_data : cache_entry->second;
 997     BrowserThread::PostTask(
 998         BrowserThread::DB, FROM_HERE,
 999         base::Bind(&ResourcePrefetchPredictorTables::UpdateData,
1000                    tables_,
1001                    url_data,
1002                    host_data));
1003   }
1004 }
1005
1006 ////////////////////////////////////////////////////////////////////////////////
1007 // Page load time and accuracy measurement.
1008
1009 // This is essentially UMA_HISTOGRAM_MEDIUM_TIMES, but it avoids using the
1010 // STATIC_HISTOGRAM_POINTER_BLOCK in UMA_HISTOGRAM definitions.
1011 #define RPP_HISTOGRAM_MEDIUM_TIMES(name, page_load_time) \
1012   do { \
1013     base::HistogramBase* histogram = base::Histogram::FactoryTimeGet( \
1014         name, \
1015         base::TimeDelta::FromMilliseconds(10), \
1016         base::TimeDelta::FromMinutes(3), \
1017         50, \
1018         base::HistogramBase::kUmaTargetedHistogramFlag); \
1019     histogram->AddTime(page_load_time); \
1020   } while (0)
1021
1022 void ResourcePrefetchPredictor::ReportPageLoadTimeStats(
1023     base::TimeDelta plt) const {
1024   net::NetworkChangeNotifier::ConnectionType connection_type =
1025       net::NetworkChangeNotifier::GetConnectionType();
1026
1027   RPP_HISTOGRAM_MEDIUM_TIMES("ResourcePrefetchPredictor.PLT", plt);
1028   RPP_HISTOGRAM_MEDIUM_TIMES(
1029       "ResourcePrefetchPredictor.PLT_" + GetNetTypeStr(), plt);
1030   if (net::NetworkChangeNotifier::IsConnectionCellular(connection_type))
1031     RPP_HISTOGRAM_MEDIUM_TIMES("ResourcePrefetchPredictor.PLT_Cellular", plt);
1032 }
1033
1034 void ResourcePrefetchPredictor::ReportPageLoadTimePrefetchStats(
1035     base::TimeDelta plt,
1036     bool prefetched,
1037     base::Callback<void(int)> report_network_type_callback,
1038     PrefetchKeyType key_type) const {
1039   net::NetworkChangeNotifier::ConnectionType connection_type =
1040       net::NetworkChangeNotifier::GetConnectionType();
1041   bool on_cellular =
1042       net::NetworkChangeNotifier::IsConnectionCellular(connection_type);
1043
1044   report_network_type_callback.Run(CONNECTION_ALL);
1045   report_network_type_callback.Run(connection_type);
1046   if (on_cellular)
1047     report_network_type_callback.Run(CONNECTION_CELLULAR);
1048
1049   std::string prefetched_str;
1050   if (prefetched)
1051     prefetched_str = "Prefetched";
1052   else
1053     prefetched_str = "NotPrefetched";
1054
1055   RPP_HISTOGRAM_MEDIUM_TIMES(
1056       "ResourcePrefetchPredictor.PLT." + prefetched_str, plt);
1057   RPP_HISTOGRAM_MEDIUM_TIMES(
1058       "ResourcePrefetchPredictor.PLT." + prefetched_str + "_" + GetNetTypeStr(),
1059       plt);
1060   if (on_cellular) {
1061     RPP_HISTOGRAM_MEDIUM_TIMES(
1062         "ResourcePrefetchPredictor.PLT." + prefetched_str + "_Cellular", plt);
1063   }
1064
1065   if (!prefetched)
1066     return;
1067
1068   std::string type =
1069       key_type == PREFETCH_KEY_TYPE_HOST ? "Host" : "Url";
1070   RPP_HISTOGRAM_MEDIUM_TIMES(
1071       "ResourcePrefetchPredictor.PLT.Prefetched." + type, plt);
1072   RPP_HISTOGRAM_MEDIUM_TIMES(
1073       "ResourcePrefetchPredictor.PLT.Prefetched." + type + "_"
1074           + GetNetTypeStr(),
1075       plt);
1076   if (on_cellular) {
1077     RPP_HISTOGRAM_MEDIUM_TIMES(
1078         "ResourcePrefetchPredictor.PLT.Prefetched." + type + "_Cellular",
1079         plt);
1080   }
1081 }
1082
1083 void ResourcePrefetchPredictor::ReportAccuracyStats(
1084     PrefetchKeyType key_type,
1085     const std::vector<URLRequestSummary>& actual,
1086     ResourcePrefetcher::RequestVector* prefetched) const {
1087   // Annotate the results.
1088   std::map<GURL, bool> actual_resources;
1089   for (std::vector<URLRequestSummary>::const_iterator it = actual.begin();
1090        it != actual.end(); ++it) {
1091     actual_resources[it->resource_url] = it->was_cached;
1092   }
1093
1094   int prefetch_cancelled = 0, prefetch_failed = 0, prefetch_not_started = 0;
1095   // 'a_' -> actual, 'p_' -> predicted.
1096   int p_cache_a_cache = 0, p_cache_a_network = 0, p_cache_a_notused = 0,
1097       p_network_a_cache = 0, p_network_a_network = 0, p_network_a_notused = 0;
1098
1099   for (ResourcePrefetcher::RequestVector::iterator it = prefetched->begin();
1100        it != prefetched->end(); ++it) {
1101     ResourcePrefetcher::Request* req = *it;
1102
1103     // Set the usage states if the resource was actually used.
1104     std::map<GURL, bool>::iterator actual_it = actual_resources.find(
1105         req->resource_url);
1106     if (actual_it != actual_resources.end()) {
1107       if (actual_it->second) {
1108         req->usage_status =
1109             ResourcePrefetcher::Request::USAGE_STATUS_FROM_CACHE;
1110       } else {
1111         req->usage_status =
1112             ResourcePrefetcher::Request::USAGE_STATUS_FROM_NETWORK;
1113       }
1114     }
1115
1116     switch (req->prefetch_status) {
1117       // TODO(shishir): Add histogram for each cancellation reason.
1118       case ResourcePrefetcher::Request::PREFETCH_STATUS_REDIRECTED:
1119       case ResourcePrefetcher::Request::PREFETCH_STATUS_AUTH_REQUIRED:
1120       case ResourcePrefetcher::Request::PREFETCH_STATUS_CERT_REQUIRED:
1121       case ResourcePrefetcher::Request::PREFETCH_STATUS_CERT_ERROR:
1122       case ResourcePrefetcher::Request::PREFETCH_STATUS_CANCELLED:
1123         ++prefetch_cancelled;
1124         break;
1125
1126       case ResourcePrefetcher::Request::PREFETCH_STATUS_FAILED:
1127         ++prefetch_failed;
1128         break;
1129
1130       case ResourcePrefetcher::Request::PREFETCH_STATUS_FROM_CACHE:
1131         if (req->usage_status ==
1132             ResourcePrefetcher::Request::USAGE_STATUS_FROM_CACHE)
1133           ++p_cache_a_cache;
1134         else if (req->usage_status ==
1135                  ResourcePrefetcher::Request::USAGE_STATUS_FROM_NETWORK)
1136           ++p_cache_a_network;
1137         else
1138           ++p_cache_a_notused;
1139         break;
1140
1141       case ResourcePrefetcher::Request::PREFETCH_STATUS_FROM_NETWORK:
1142           if (req->usage_status ==
1143               ResourcePrefetcher::Request::USAGE_STATUS_FROM_CACHE)
1144             ++p_network_a_cache;
1145           else if (req->usage_status ==
1146                    ResourcePrefetcher::Request::USAGE_STATUS_FROM_NETWORK)
1147             ++p_network_a_network;
1148           else
1149             ++p_network_a_notused;
1150         break;
1151
1152       case ResourcePrefetcher::Request::PREFETCH_STATUS_NOT_STARTED:
1153         ++prefetch_not_started;
1154         break;
1155
1156       case ResourcePrefetcher::Request::PREFETCH_STATUS_STARTED:
1157         DLOG(FATAL) << "Invalid prefetch status";
1158         break;
1159     }
1160   }
1161
1162   int total_prefetched = p_cache_a_cache + p_cache_a_network + p_cache_a_notused
1163       + p_network_a_cache + p_network_a_network + p_network_a_notused;
1164
1165   std::string histogram_type = key_type == PREFETCH_KEY_TYPE_HOST ? "Host." :
1166       "Url.";
1167
1168   // Macros to avoid using the STATIC_HISTOGRAM_POINTER_BLOCK in UMA_HISTOGRAM
1169   // definitions.
1170 #define RPP_HISTOGRAM_PERCENTAGE(suffix, value) \
1171   { \
1172     std::string name = "ResourcePrefetchPredictor." + histogram_type + suffix; \
1173     std::string g_name = "ResourcePrefetchPredictor." + std::string(suffix); \
1174     base::HistogramBase* histogram = base::LinearHistogram::FactoryGet( \
1175         name, 1, 101, 102, base::Histogram::kUmaTargetedHistogramFlag); \
1176     histogram->Add(value); \
1177     UMA_HISTOGRAM_PERCENTAGE(g_name, value); \
1178   }
1179
1180   RPP_HISTOGRAM_PERCENTAGE("PrefetchCancelled",
1181                            prefetch_cancelled * 100.0 / total_prefetched);
1182   RPP_HISTOGRAM_PERCENTAGE("PrefetchFailed",
1183                            prefetch_failed * 100.0 / total_prefetched);
1184   RPP_HISTOGRAM_PERCENTAGE("PrefetchFromCacheUsedFromCache",
1185                            p_cache_a_cache * 100.0 / total_prefetched);
1186   RPP_HISTOGRAM_PERCENTAGE("PrefetchFromCacheUsedFromNetwork",
1187                            p_cache_a_network * 100.0 / total_prefetched);
1188   RPP_HISTOGRAM_PERCENTAGE("PrefetchFromCacheNotUsed",
1189                            p_cache_a_notused * 100.0 / total_prefetched);
1190   RPP_HISTOGRAM_PERCENTAGE("PrefetchFromNetworkUsedFromCache",
1191                            p_network_a_cache * 100.0 / total_prefetched);
1192   RPP_HISTOGRAM_PERCENTAGE("PrefetchFromNetworkUsedFromNetwork",
1193                            p_network_a_network * 100.0 / total_prefetched);
1194   RPP_HISTOGRAM_PERCENTAGE("PrefetchFromNetworkNotUsed",
1195                            p_network_a_notused * 100.0 / total_prefetched);
1196
1197   RPP_HISTOGRAM_PERCENTAGE(
1198       "PrefetchNotStarted",
1199       prefetch_not_started * 100.0 / (prefetch_not_started + total_prefetched));
1200
1201 #undef RPP_HISTOGRAM_PERCENTAGE
1202 }
1203
1204 void ResourcePrefetchPredictor::ReportPredictedAccuracyStats(
1205     PrefetchKeyType key_type,
1206     const std::vector<URLRequestSummary>& actual,
1207     const ResourcePrefetcher::RequestVector& predicted) const {
1208   std::map<GURL, bool> actual_resources;
1209   int from_network = 0;
1210   for (std::vector<URLRequestSummary>::const_iterator it = actual.begin();
1211        it != actual.end(); ++it) {
1212     actual_resources[it->resource_url] = it->was_cached;
1213     if (!it->was_cached)
1214       ++from_network;
1215   }
1216
1217   // Measure the accuracy at 25, 50 predicted resources.
1218   ReportPredictedAccuracyStatsHelper(key_type, predicted, actual_resources,
1219                                      from_network, 25);
1220   ReportPredictedAccuracyStatsHelper(key_type, predicted, actual_resources,
1221                                      from_network, 50);
1222 }
1223
1224 void ResourcePrefetchPredictor::ReportPredictedAccuracyStatsHelper(
1225     PrefetchKeyType key_type,
1226     const ResourcePrefetcher::RequestVector& predicted,
1227     const std::map<GURL, bool>& actual,
1228     size_t total_resources_fetched_from_network,
1229     size_t max_assumed_prefetched) const {
1230   int prefetch_cached = 0, prefetch_network = 0, prefetch_missed = 0;
1231   int num_assumed_prefetched = std::min(predicted.size(),
1232                                         max_assumed_prefetched);
1233   if (num_assumed_prefetched == 0)
1234     return;
1235
1236   for (int i = 0; i < num_assumed_prefetched; ++i) {
1237     const ResourcePrefetcher::Request& row = *(predicted[i]);
1238     std::map<GURL, bool>::const_iterator it = actual.find(row.resource_url);
1239     if (it == actual.end()) {
1240       ++prefetch_missed;
1241     } else if (it->second) {
1242       ++prefetch_cached;
1243     } else {
1244       ++prefetch_network;
1245     }
1246   }
1247
1248   std::string prefix = key_type == PREFETCH_KEY_TYPE_HOST ?
1249       "ResourcePrefetchPredictor.Host.Predicted" :
1250       "ResourcePrefetchPredictor.Url.Predicted";
1251   std::string suffix = "_" + base::IntToString(max_assumed_prefetched);
1252
1253   // Macros to avoid using the STATIC_HISTOGRAM_POINTER_BLOCK in UMA_HISTOGRAM
1254   // definitions.
1255 #define RPP_PREDICTED_HISTOGRAM_COUNTS(name, value) \
1256   { \
1257     std::string full_name = prefix + name + suffix; \
1258     base::HistogramBase* histogram = base::Histogram::FactoryGet( \
1259         full_name, 1, 1000000, 50, \
1260         base::Histogram::kUmaTargetedHistogramFlag); \
1261     histogram->Add(value); \
1262   }
1263
1264 #define RPP_PREDICTED_HISTOGRAM_PERCENTAGE(name, value) \
1265   { \
1266     std::string full_name = prefix + name + suffix; \
1267     base::HistogramBase* histogram = base::LinearHistogram::FactoryGet( \
1268         full_name, 1, 101, 102, base::Histogram::kUmaTargetedHistogramFlag); \
1269     histogram->Add(value); \
1270   }
1271
1272   RPP_PREDICTED_HISTOGRAM_COUNTS("PrefetchCount", num_assumed_prefetched);
1273   RPP_PREDICTED_HISTOGRAM_COUNTS("PrefetchMisses_Count", prefetch_missed);
1274   RPP_PREDICTED_HISTOGRAM_COUNTS("PrefetchFromCache_Count", prefetch_cached);
1275   RPP_PREDICTED_HISTOGRAM_COUNTS("PrefetchFromNetwork_Count", prefetch_network);
1276
1277   RPP_PREDICTED_HISTOGRAM_PERCENTAGE(
1278       "PrefetchMisses_PercentOfTotalPrefetched",
1279       prefetch_missed * 100.0 / num_assumed_prefetched);
1280   RPP_PREDICTED_HISTOGRAM_PERCENTAGE(
1281       "PrefetchFromCache_PercentOfTotalPrefetched",
1282       prefetch_cached * 100.0 / num_assumed_prefetched);
1283   RPP_PREDICTED_HISTOGRAM_PERCENTAGE(
1284       "PrefetchFromNetwork_PercentOfTotalPrefetched",
1285       prefetch_network * 100.0 / num_assumed_prefetched);
1286
1287   // Measure the ratio of total number of resources prefetched from network vs
1288   // the total number of resources fetched by the page from the network.
1289   if (total_resources_fetched_from_network > 0) {
1290     RPP_PREDICTED_HISTOGRAM_PERCENTAGE(
1291         "PrefetchFromNetworkPercentOfTotalFromNetwork",
1292         prefetch_network * 100.0 / total_resources_fetched_from_network);
1293   }
1294
1295 #undef RPP_HISTOGRAM_MEDIUM_TIMES
1296 #undef RPP_PREDICTED_HISTOGRAM_PERCENTAGE
1297 #undef RPP_PREDICTED_HISTOGRAM_COUNTS
1298 }
1299
1300 void ResourcePrefetchPredictor::OnURLsDeleted(
1301     history::HistoryService* history_service,
1302     bool all_history,
1303     bool expired,
1304     const history::URLRows& deleted_rows,
1305     const std::set<GURL>& favicon_urls) {
1306   DCHECK_CURRENTLY_ON(BrowserThread::UI);
1307   if (INITIALIZED != initialization_state_)
1308     return;
1309
1310   if (all_history) {
1311     DeleteAllUrls();
1312     UMA_HISTOGRAM_ENUMERATION("ResourcePrefetchPredictor.ReportingEvent",
1313                               REPORTING_EVENT_ALL_HISTORY_CLEARED,
1314                               REPORTING_EVENT_COUNT);
1315   } else {
1316     DeleteUrls(deleted_rows);
1317     UMA_HISTOGRAM_ENUMERATION("ResourcePrefetchPredictor.ReportingEvent",
1318                               REPORTING_EVENT_PARTIAL_HISTORY_CLEARED,
1319                               REPORTING_EVENT_COUNT);
1320   }
1321 }
1322
1323 void ResourcePrefetchPredictor::OnHistoryServiceLoaded(
1324     history::HistoryService* history_service) {
1325   OnHistoryAndCacheLoaded();
1326   history_service_observer_.Remove(history_service);
1327 }
1328
1329 void ResourcePrefetchPredictor::ConnectToHistoryService() {
1330   // Register for HistoryServiceLoading if it is not ready.
1331   history::HistoryService* history_service =
1332       HistoryServiceFactory::GetForProfile(profile_,
1333                                            ServiceAccessType::EXPLICIT_ACCESS);
1334   if (!history_service)
1335     return;
1336   if (history_service->BackendLoaded()) {
1337     // HistoryService is already loaded. Continue with Initialization.
1338     OnHistoryAndCacheLoaded();
1339     return;
1340   }
1341   DCHECK(!history_service_observer_.IsObserving(history_service));
1342   history_service_observer_.Add(history_service);
1343   return;
1344 }
1345
1346 }  // namespace predictors