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