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/strings/string_number_conversions.h"
  15 #include "base/strings/stringprintf.h"
  16 #include "base/time/time.h"
  17 #include "chrome/browser/history/history_service_factory.h"
  18 #include "chrome/browser/predictors/predictor_database.h"
  19 #include "chrome/browser/predictors/predictor_database_factory.h"
  20 #include "chrome/browser/predictors/resource_prefetcher_manager.h"
  21 #include "chrome/browser/profiles/profile.h"
  22 #include "chrome/common/chrome_switches.h"
  23 #include "chrome/common/url_constants.h"
  24 #include "components/history/core/browser/history_database.h"
  25 #include "components/history/core/browser/history_db_task.h"
  26 #include "components/history/core/browser/history_service.h"
  27 #include "components/mime_util/mime_util.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() && !mime_util::IsSupportedImageMimeType(mime_type) &&
 250       !mime_util::IsSupportedJavascriptMimeType(mime_type) &&
 251       !net::MatchesMimeType("text/css", mime_type)) {
 252     resource_status |= RESOURCE_STATUS_UNSUPPORTED_MIME_TYPE;
 253   }
 254
 255   if (response->method() != "GET")
 256     resource_status |= RESOURCE_STATUS_NOT_GET;
 257
 258   if (response->original_url().spec().length() >
 259       ResourcePrefetchPredictorTables::kMaxStringLength) {
 260     resource_status |= RESOURCE_STATUS_URL_TOO_LONG;
 261   }
 262
 263   if (!response->response_info().headers.get())
 264     resource_status |= RESOURCE_STATUS_HEADERS_MISSING;
 265
 266   if (!IsCacheable(response))
 267     resource_status |= RESOURCE_STATUS_NOT_CACHEABLE;
 268
 269   UMA_HISTOGRAM_ENUMERATION("ResourcePrefetchPredictor.ResourceStatus",
 270                             resource_status,
 271                             RESOURCE_STATUS_MAX);
 272
 273   return resource_status == 0;
 274 }
 275
 276 // static
 277 bool ResourcePrefetchPredictor::IsCacheable(const net::URLRequest* response) {
 278   if (response->was_cached())
 279     return true;
 280
 281   // For non cached responses, we will ensure that the freshness lifetime is
 282   // some sane value.
 283   const net::HttpResponseInfo& response_info = response->response_info();
 284   if (!response_info.headers.get())
 285     return false;
 286   base::Time response_time(response_info.response_time);
 287   response_time += base::TimeDelta::FromSeconds(1);
 288   base::TimeDelta freshness =
 289       response_info.headers->GetFreshnessLifetimes(response_time).freshness;
 290   return freshness > base::TimeDelta();
 291 }
 292
 293 // static
 294 content::ResourceType ResourcePrefetchPredictor::GetResourceTypeFromMimeType(
 295     const std::string& mime_type,
 296     content::ResourceType fallback) {
 297   if (mime_util::IsSupportedImageMimeType(mime_type))
 298     return content::RESOURCE_TYPE_IMAGE;
 299   else if (mime_util::IsSupportedJavascriptMimeType(mime_type))
 300     return content::RESOURCE_TYPE_SCRIPT;
 301   else if (net::MatchesMimeType("text/css", mime_type))
 302     return content::RESOURCE_TYPE_STYLESHEET;
 303   else
 304     return fallback;
 305 }
 306
 307 ////////////////////////////////////////////////////////////////////////////////
 308 // ResourcePrefetchPredictor structs.
 309
 310 ResourcePrefetchPredictor::URLRequestSummary::URLRequestSummary()
 311     : resource_type(content::RESOURCE_TYPE_LAST_TYPE),
 312       was_cached(false) {
 313 }
 314
 315 ResourcePrefetchPredictor::URLRequestSummary::URLRequestSummary(
 316     const URLRequestSummary& other)
 317         : navigation_id(other.navigation_id),
 318           resource_url(other.resource_url),
 319           resource_type(other.resource_type),
 320           mime_type(other.mime_type),
 321           was_cached(other.was_cached),
 322           redirect_url(other.redirect_url) {
 323 }
 324
 325 ResourcePrefetchPredictor::URLRequestSummary::~URLRequestSummary() {
 326 }
 327
 328 ResourcePrefetchPredictor::Result::Result(
 329     PrefetchKeyType i_key_type,
 330     ResourcePrefetcher::RequestVector* i_requests)
 331     : key_type(i_key_type),
 332       requests(i_requests) {
 333 }
 334
 335 ResourcePrefetchPredictor::Result::~Result() {
 336 }
 337
 338 ////////////////////////////////////////////////////////////////////////////////
 339 // ResourcePrefetchPredictor.
 340
 341 ResourcePrefetchPredictor::ResourcePrefetchPredictor(
 342     const ResourcePrefetchPredictorConfig& config,
 343     Profile* profile)
 344     : profile_(profile),
 345       config_(config),
 346       initialization_state_(NOT_INITIALIZED),
 347       tables_(PredictorDatabaseFactory::GetForProfile(profile)
 348                   ->resource_prefetch_tables()),
 349       history_service_observer_(this) {
 350   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 351
 352   // Some form of learning has to be enabled.
 353   DCHECK(config_.IsLearningEnabled());
 354   if (config_.IsURLPrefetchingEnabled(profile_))
 355     DCHECK(config_.IsURLLearningEnabled());
 356   if (config_.IsHostPrefetchingEnabled(profile_))
 357     DCHECK(config_.IsHostLearningEnabled());
 358 }
 359
 360 ResourcePrefetchPredictor::~ResourcePrefetchPredictor() {
 361 }
 362
 363 void ResourcePrefetchPredictor::RecordURLRequest(
 364     const URLRequestSummary& request) {
 365   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 366   if (initialization_state_ != INITIALIZED)
 367     return;
 368
 369   CHECK_EQ(request.resource_type, content::RESOURCE_TYPE_MAIN_FRAME);
 370   OnMainFrameRequest(request);
 371 }
 372
 373 void ResourcePrefetchPredictor::RecordURLResponse(
 374     const URLRequestSummary& response) {
 375   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 376   if (initialization_state_ != INITIALIZED)
 377     return;
 378
 379   if (response.resource_type == content::RESOURCE_TYPE_MAIN_FRAME)
 380     OnMainFrameResponse(response);
 381   else
 382     OnSubresourceResponse(response);
 383 }
 384
 385 void ResourcePrefetchPredictor::RecordURLRedirect(
 386     const URLRequestSummary& response) {
 387   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 388   if (initialization_state_ != INITIALIZED)
 389     return;
 390
 391   CHECK_EQ(response.resource_type, content::RESOURCE_TYPE_MAIN_FRAME);
 392   OnMainFrameRedirect(response);
 393 }
 394
 395 void ResourcePrefetchPredictor::RecordMainFrameLoadComplete(
 396     const NavigationID& navigation_id) {
 397   switch (initialization_state_) {
 398     case NOT_INITIALIZED:
 399       StartInitialization();
 400       break;
 401     case INITIALIZING:
 402       break;
 403     case INITIALIZED: {
 404       RecordNavigationEvent(NAVIGATION_EVENT_ONLOAD);
 405       // WebContents can return an empty URL if the navigation entry
 406       // corresponding to the navigation has not been created yet.
 407       if (navigation_id.main_frame_url.is_empty())
 408         RecordNavigationEvent(NAVIGATION_EVENT_ONLOAD_EMPTY_URL);
 409       else
 410         OnNavigationComplete(navigation_id);
 411       break;
 412     }
 413     default:
 414       NOTREACHED() << "Unexpected initialization_state_: "
 415                    << initialization_state_;
 416   }
 417 }
 418
 419 void ResourcePrefetchPredictor::FinishedPrefetchForNavigation(
 420     const NavigationID& navigation_id,
 421     PrefetchKeyType key_type,
 422     ResourcePrefetcher::RequestVector* requests) {
 423   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 424
 425   scoped_ptr<Result> result(new Result(key_type, requests));
 426   // Add the results to the results map.
 427   if (!results_map_.insert(navigation_id, result.Pass()).second)
 428     DLOG(FATAL) << "Returning results for existing navigation.";
 429 }
 430
 431 void ResourcePrefetchPredictor::Shutdown() {
 432   if (prefetch_manager_.get()) {
 433     prefetch_manager_->ShutdownOnUIThread();
 434     prefetch_manager_ = NULL;
 435   }
 436   history_service_observer_.RemoveAll();
 437 }
 438
 439 void ResourcePrefetchPredictor::OnMainFrameRequest(
 440     const URLRequestSummary& request) {
 441   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 442   DCHECK_EQ(INITIALIZED, initialization_state_);
 443
 444   RecordNavigationEvent(NAVIGATION_EVENT_REQUEST_STARTED);
 445
 446   StartPrefetching(request.navigation_id);
 447
 448   // Cleanup older navigations.
 449   CleanupAbandonedNavigations(request.navigation_id);
 450
 451   // New empty navigation entry.
 452   inflight_navigations_.insert(std::make_pair(
 453       request.navigation_id,
 454       make_linked_ptr(new std::vector<URLRequestSummary>())));
 455 }
 456
 457 void ResourcePrefetchPredictor::OnMainFrameResponse(
 458     const URLRequestSummary& response) {
 459   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 460   if (initialization_state_ != INITIALIZED)
 461     return;
 462
 463   RecordNavigationEvent(NAVIGATION_EVENT_RESPONSE_STARTED);
 464
 465   StopPrefetching(response.navigation_id);
 466 }
 467
 468 void ResourcePrefetchPredictor::OnMainFrameRedirect(
 469     const URLRequestSummary& response) {
 470   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 471
 472   RecordNavigationEvent(NAVIGATION_EVENT_REQUEST_REDIRECTED);
 473
 474   // TODO(shishir): There are significant gains to be had here if we can use the
 475   // start URL in a redirect chain as the key to start prefetching. We can save
 476   // of redirect times considerably assuming that the redirect chains do not
 477   // change.
 478
 479   // Stop any inflight prefetching. Remove the older navigation.
 480   StopPrefetching(response.navigation_id);
 481   inflight_navigations_.erase(response.navigation_id);
 482
 483   // A redirect will not lead to another OnMainFrameRequest call, so record the
 484   // redirect url as a new navigation.
 485
 486   // The redirect url may be empty if the url was invalid.
 487   if (response.redirect_url.is_empty()) {
 488     RecordNavigationEvent(NAVIGATION_EVENT_REQUEST_REDIRECTED_EMPTY_URL);
 489     return;
 490   }
 491
 492   NavigationID navigation_id(response.navigation_id);
 493   navigation_id.main_frame_url = response.redirect_url;
 494   inflight_navigations_.insert(std::make_pair(
 495       navigation_id,
 496       make_linked_ptr(new std::vector<URLRequestSummary>())));
 497 }
 498
 499 void ResourcePrefetchPredictor::OnSubresourceResponse(
 500     const URLRequestSummary& response) {
 501   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 502
 503   NavigationMap::const_iterator nav_it =
 504         inflight_navigations_.find(response.navigation_id);
 505   if (nav_it == inflight_navigations_.end()) {
 506     return;
 507   }
 508
 509   nav_it->second->push_back(response);
 510 }
 511
 512 base::TimeDelta ResourcePrefetchPredictor::OnNavigationComplete(
 513     const NavigationID& nav_id_without_timing_info) {
 514   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 515
 516   NavigationMap::iterator nav_it =
 517       inflight_navigations_.find(nav_id_without_timing_info);
 518   if (nav_it == inflight_navigations_.end()) {
 519     RecordNavigationEvent(NAVIGATION_EVENT_ONLOAD_UNTRACKED_URL);
 520     return base::TimeDelta();
 521   }
 522   RecordNavigationEvent(NAVIGATION_EVENT_ONLOAD_TRACKED_URL);
 523
 524   // Get and use the navigation ID stored in |inflight_navigations_| because it
 525   // has the timing infomation.
 526   const NavigationID navigation_id(nav_it->first);
 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::const_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   return plt;
 585 }
 586
 587 bool ResourcePrefetchPredictor::GetPrefetchData(
 588     const NavigationID& navigation_id,
 589     ResourcePrefetcher::RequestVector* prefetch_requests,
 590     PrefetchKeyType* key_type) {
 591   DCHECK(prefetch_requests);
 592   DCHECK(key_type);
 593
 594   *key_type = PREFETCH_KEY_TYPE_URL;
 595   const GURL& main_frame_url = navigation_id.main_frame_url;
 596
 597   bool use_url_data = config_.IsPrefetchingEnabled(profile_) ?
 598       config_.IsURLPrefetchingEnabled(profile_) :
 599       config_.IsURLLearningEnabled();
 600   if (use_url_data) {
 601     PrefetchDataMap::const_iterator iterator =
 602         url_table_cache_->find(main_frame_url.spec());
 603     if (iterator != url_table_cache_->end())
 604       PopulatePrefetcherRequest(iterator->second, prefetch_requests);
 605   }
 606   if (!prefetch_requests->empty())
 607     return true;
 608
 609   bool use_host_data = config_.IsPrefetchingEnabled(profile_) ?
 610       config_.IsHostPrefetchingEnabled(profile_) :
 611       config_.IsHostLearningEnabled();
 612   if (use_host_data) {
 613     PrefetchDataMap::const_iterator iterator =
 614         host_table_cache_->find(main_frame_url.host());
 615     if (iterator != host_table_cache_->end()) {
 616       *key_type = PREFETCH_KEY_TYPE_HOST;
 617       PopulatePrefetcherRequest(iterator->second, prefetch_requests);
 618     }
 619   }
 620
 621   return !prefetch_requests->empty();
 622 }
 623
 624 void ResourcePrefetchPredictor::PopulatePrefetcherRequest(
 625     const PrefetchData& data,
 626     ResourcePrefetcher::RequestVector* requests) {
 627   for (ResourceRows::const_iterator it = data.resources.begin();
 628        it != data.resources.end(); ++it) {
 629     float confidence = static_cast<float>(it->number_of_hits) /
 630         (it->number_of_hits + it->number_of_misses);
 631     if (confidence < config_.min_resource_confidence_to_trigger_prefetch ||
 632         it->number_of_hits < config_.min_resource_hits_to_trigger_prefetch) {
 633       continue;
 634     }
 635
 636     ResourcePrefetcher::Request* req = new ResourcePrefetcher::Request(
 637         it->resource_url);
 638     requests->push_back(req);
 639   }
 640 }
 641
 642 void ResourcePrefetchPredictor::StartPrefetching(
 643     const NavigationID& navigation_id) {
 644   if (!prefetch_manager_.get())  // Prefetching not enabled.
 645     return;
 646
 647   // Prefer URL based data first.
 648   scoped_ptr<ResourcePrefetcher::RequestVector> requests(
 649       new ResourcePrefetcher::RequestVector);
 650   PrefetchKeyType key_type;
 651   if (!GetPrefetchData(navigation_id, requests.get(), &key_type)) {
 652     // No prefetching data at host or URL level.
 653     return;
 654   }
 655
 656   BrowserThread::PostTask(BrowserThread::IO, FROM_HERE,
 657       base::Bind(&ResourcePrefetcherManager::MaybeAddPrefetch,
 658                  prefetch_manager_,
 659                  navigation_id,
 660                  key_type,
 661                  base::Passed(&requests)));
 662 }
 663
 664 void ResourcePrefetchPredictor::StopPrefetching(
 665     const NavigationID& navigation_id) {
 666   if (!prefetch_manager_.get())  // Not enabled.
 667     return;
 668
 669   BrowserThread::PostTask(
 670       BrowserThread::IO, FROM_HERE,
 671       base::Bind(&ResourcePrefetcherManager::MaybeRemovePrefetch,
 672                  prefetch_manager_,
 673                  navigation_id));
 674 }
 675
 676 void ResourcePrefetchPredictor::StartInitialization() {
 677   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 678
 679   DCHECK_EQ(NOT_INITIALIZED, initialization_state_);
 680   initialization_state_ = INITIALIZING;
 681
 682   // Create local caches using the database as loaded.
 683   scoped_ptr<PrefetchDataMap> url_data_map(new PrefetchDataMap());
 684   scoped_ptr<PrefetchDataMap> host_data_map(new PrefetchDataMap());
 685   PrefetchDataMap* url_data_ptr = url_data_map.get();
 686   PrefetchDataMap* host_data_ptr = host_data_map.get();
 687
 688   BrowserThread::PostTaskAndReply(
 689       BrowserThread::DB, FROM_HERE,
 690       base::Bind(&ResourcePrefetchPredictorTables::GetAllData,
 691                  tables_, url_data_ptr, host_data_ptr),
 692       base::Bind(&ResourcePrefetchPredictor::CreateCaches, AsWeakPtr(),
 693                  base::Passed(&url_data_map), base::Passed(&host_data_map)));
 694 }
 695
 696 void ResourcePrefetchPredictor::CreateCaches(
 697     scoped_ptr<PrefetchDataMap> url_data_map,
 698     scoped_ptr<PrefetchDataMap> host_data_map) {
 699   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 700
 701   DCHECK_EQ(INITIALIZING, initialization_state_);
 702   DCHECK(!url_table_cache_);
 703   DCHECK(!host_table_cache_);
 704   DCHECK(inflight_navigations_.empty());
 705
 706   url_table_cache_.reset(url_data_map.release());
 707   host_table_cache_.reset(host_data_map.release());
 708
 709   UMA_HISTOGRAM_COUNTS("ResourcePrefetchPredictor.UrlTableMainFrameUrlCount",
 710                        url_table_cache_->size());
 711   UMA_HISTOGRAM_COUNTS("ResourcePrefetchPredictor.HostTableHostCount",
 712                        host_table_cache_->size());
 713
 714   ConnectToHistoryService();
 715 }
 716
 717 void ResourcePrefetchPredictor::OnHistoryAndCacheLoaded() {
 718   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 719   DCHECK_EQ(INITIALIZING, initialization_state_);
 720
 721   // Initialize the prefetch manager only if prefetching is enabled.
 722   if (config_.IsPrefetchingEnabled(profile_)) {
 723     prefetch_manager_ = new ResourcePrefetcherManager(
 724         this, config_, profile_->GetRequestContext());
 725   }
 726   initialization_state_ = INITIALIZED;
 727 }
 728
 729 void ResourcePrefetchPredictor::CleanupAbandonedNavigations(
 730     const NavigationID& navigation_id) {
 731   static const base::TimeDelta max_navigation_age =
 732       base::TimeDelta::FromSeconds(config_.max_navigation_lifetime_seconds);
 733
 734   base::TimeTicks time_now = base::TimeTicks::Now();
 735   for (NavigationMap::iterator it = inflight_navigations_.begin();
 736        it != inflight_navigations_.end();) {
 737     if (it->first.IsSameRenderer(navigation_id) ||
 738         (time_now - it->first.creation_time > max_navigation_age)) {
 739       inflight_navigations_.erase(it++);
 740       RecordNavigationEvent(NAVIGATION_EVENT_REQUEST_EXPIRED);
 741     } else {
 742       ++it;
 743     }
 744   }
 745   for (ResultsMap::const_iterator it = results_map_.begin();
 746        it != results_map_.end();) {
 747     if (it->first.IsSameRenderer(navigation_id) ||
 748         (time_now - it->first.creation_time > max_navigation_age)) {
 749       results_map_.erase(it++);
 750     } else {
 751       ++it;
 752     }
 753   }
 754 }
 755
 756 void ResourcePrefetchPredictor::DeleteAllUrls() {
 757   inflight_navigations_.clear();
 758   url_table_cache_->clear();
 759   host_table_cache_->clear();
 760
 761   BrowserThread::PostTask(BrowserThread::DB, FROM_HERE,
 762       base::Bind(&ResourcePrefetchPredictorTables::DeleteAllData, tables_));
 763 }
 764
 765 void ResourcePrefetchPredictor::DeleteUrls(const history::URLRows& urls) {
 766   // Check all the urls in the database and pick out the ones that are present
 767   // in the cache.
 768   std::vector<std::string> urls_to_delete, hosts_to_delete;
 769
 770   for (const auto& it : urls) {
 771     const std::string& url_spec = it.url().spec();
 772     if (url_table_cache_->find(url_spec) != url_table_cache_->end()) {
 773       urls_to_delete.push_back(url_spec);
 774       url_table_cache_->erase(url_spec);
 775     }
 776
 777     const std::string& host = it.url().host();
 778     if (host_table_cache_->find(host) != host_table_cache_->end()) {
 779       hosts_to_delete.push_back(host);
 780       host_table_cache_->erase(host);
 781     }
 782   }
 783
 784   if (!urls_to_delete.empty() || !hosts_to_delete.empty()) {
 785     BrowserThread::PostTask(BrowserThread::DB, FROM_HERE,
 786         base::Bind(&ResourcePrefetchPredictorTables::DeleteData,
 787                    tables_,
 788                    urls_to_delete,
 789                    hosts_to_delete));
 790   }
 791 }
 792
 793 void ResourcePrefetchPredictor::RemoveOldestEntryInPrefetchDataMap(
 794     PrefetchKeyType key_type,
 795     PrefetchDataMap* data_map) {
 796   if (data_map->empty())
 797     return;
 798
 799   base::Time oldest_time;
 800   std::string key_to_delete;
 801   for (PrefetchDataMap::iterator it = data_map->begin();
 802        it != data_map->end(); ++it) {
 803     if (key_to_delete.empty() || it->second.last_visit < oldest_time) {
 804       key_to_delete = it->first;
 805       oldest_time = it->second.last_visit;
 806     }
 807   }
 808
 809   data_map->erase(key_to_delete);
 810     BrowserThread::PostTask(BrowserThread::DB, FROM_HERE,
 811         base::Bind(&ResourcePrefetchPredictorTables::DeleteSingleDataPoint,
 812                    tables_,
 813                    key_to_delete,
 814                    key_type));
 815 }
 816
 817 void ResourcePrefetchPredictor::OnVisitCountLookup(
 818     size_t visit_count,
 819     const NavigationID& navigation_id,
 820     const std::vector<URLRequestSummary>& requests) {
 821   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 822
 823   UMA_HISTOGRAM_COUNTS("ResourcePrefetchPredictor.HistoryVisitCountForUrl",
 824                        visit_count);
 825
 826   // URL level data - merge only if we are already saving the data, or we it
 827   // meets the cutoff requirement.
 828   const std::string url_spec = navigation_id.main_frame_url.spec();
 829   bool already_tracking = url_table_cache_->find(url_spec) !=
 830       url_table_cache_->end();
 831   bool should_track_url = already_tracking ||
 832       (visit_count >= config_.min_url_visit_count);
 833
 834   if (should_track_url) {
 835     RecordNavigationEvent(NAVIGATION_EVENT_SHOULD_TRACK_URL);
 836
 837     if (config_.IsURLLearningEnabled()) {
 838       LearnNavigation(url_spec, PREFETCH_KEY_TYPE_URL, requests,
 839                       config_.max_urls_to_track, url_table_cache_.get());
 840     }
 841   } else {
 842     RecordNavigationEvent(NAVIGATION_EVENT_SHOULD_NOT_TRACK_URL);
 843   }
 844
 845   // Host level data - no cutoff, always learn the navigation if enabled.
 846   if (config_.IsHostLearningEnabled()) {
 847     LearnNavigation(navigation_id.main_frame_url.host(),
 848                     PREFETCH_KEY_TYPE_HOST,
 849                     requests,
 850                     config_.max_hosts_to_track,
 851                     host_table_cache_.get());
 852   }
 853
 854   // Remove the navigation from the results map.
 855   results_map_.erase(navigation_id);
 856 }
 857
 858 void ResourcePrefetchPredictor::LearnNavigation(
 859     const std::string& key,
 860     PrefetchKeyType key_type,
 861     const std::vector<URLRequestSummary>& new_resources,
 862     size_t max_data_map_size,
 863     PrefetchDataMap* data_map) {
 864   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 865
 866   // If the primary key is too long reject it.
 867   if (key.length() > ResourcePrefetchPredictorTables::kMaxStringLength) {
 868     if (key_type == PREFETCH_KEY_TYPE_HOST)
 869       RecordNavigationEvent(NAVIGATION_EVENT_HOST_TOO_LONG);
 870     else
 871       RecordNavigationEvent(NAVIGATION_EVENT_MAIN_FRAME_URL_TOO_LONG);
 872     return;
 873   }
 874
 875   PrefetchDataMap::iterator cache_entry = data_map->find(key);
 876   if (cache_entry == data_map->end()) {
 877     if (data_map->size() >= max_data_map_size) {
 878       // The table is full, delete an entry.
 879       RemoveOldestEntryInPrefetchDataMap(key_type, data_map);
 880     }
 881
 882     cache_entry = data_map->insert(std::make_pair(
 883         key, PrefetchData(key_type, key))).first;
 884     cache_entry->second.last_visit = base::Time::Now();
 885     size_t new_resources_size = new_resources.size();
 886     std::set<GURL> resources_seen;
 887     for (size_t i = 0; i < new_resources_size; ++i) {
 888       if (resources_seen.find(new_resources[i].resource_url) !=
 889           resources_seen.end()) {
 890         continue;
 891       }
 892       ResourceRow row_to_add;
 893       row_to_add.resource_url = new_resources[i].resource_url;
 894       row_to_add.resource_type = new_resources[i].resource_type;
 895       row_to_add.number_of_hits = 1;
 896       row_to_add.average_position = i + 1;
 897       cache_entry->second.resources.push_back(row_to_add);
 898       resources_seen.insert(new_resources[i].resource_url);
 899     }
 900   } else {
 901     ResourceRows& old_resources = cache_entry->second.resources;
 902     cache_entry->second.last_visit = base::Time::Now();
 903
 904     // Build indices over the data.
 905     std::map<GURL, int> new_index, old_index;
 906     int new_resources_size = static_cast<int>(new_resources.size());
 907     for (int i = 0; i < new_resources_size; ++i) {
 908       const URLRequestSummary& summary = new_resources[i];
 909       // Take the first occurence of every url.
 910       if (new_index.find(summary.resource_url) == new_index.end())
 911         new_index[summary.resource_url] = i;
 912     }
 913     int old_resources_size = static_cast<int>(old_resources.size());
 914     for (int i = 0; i < old_resources_size; ++i) {
 915       const ResourceRow& row = old_resources[i];
 916       DCHECK(old_index.find(row.resource_url) == old_index.end());
 917       old_index[row.resource_url] = i;
 918     }
 919
 920     // Go through the old urls and update their hit/miss counts.
 921     for (int i = 0; i < old_resources_size; ++i) {
 922       ResourceRow& old_row = old_resources[i];
 923       if (new_index.find(old_row.resource_url) == new_index.end()) {
 924         ++old_row.number_of_misses;
 925         ++old_row.consecutive_misses;
 926       } else {
 927         const URLRequestSummary& new_row =
 928             new_resources[new_index[old_row.resource_url]];
 929
 930         // Update the resource type since it could have changed.
 931         if (new_row.resource_type != content::RESOURCE_TYPE_LAST_TYPE)
 932           old_row.resource_type = new_row.resource_type;
 933
 934         int position = new_index[old_row.resource_url] + 1;
 935         int total = old_row.number_of_hits + old_row.number_of_misses;
 936         old_row.average_position =
 937             ((old_row.average_position * total) + position) / (total + 1);
 938         ++old_row.number_of_hits;
 939         old_row.consecutive_misses = 0;
 940       }
 941     }
 942
 943     // Add the new ones that we have not seen before.
 944     for (int i = 0; i < new_resources_size; ++i) {
 945       const URLRequestSummary& summary = new_resources[i];
 946       if (old_index.find(summary.resource_url) != old_index.end())
 947         continue;
 948
 949       // Only need to add new stuff.
 950       ResourceRow row_to_add;
 951       row_to_add.resource_url = summary.resource_url;
 952       row_to_add.resource_type = summary.resource_type;
 953       row_to_add.number_of_hits = 1;
 954       row_to_add.average_position = i + 1;
 955       old_resources.push_back(row_to_add);
 956
 957       // To ensure we dont add the same url twice.
 958       old_index[summary.resource_url] = 0;
 959     }
 960   }
 961
 962   // Trim and sort the resources after the update.
 963   ResourceRows& resources = cache_entry->second.resources;
 964   for (ResourceRows::iterator it = resources.begin();
 965        it != resources.end();) {
 966     it->UpdateScore();
 967     if (it->consecutive_misses >= config_.max_consecutive_misses)
 968       it = resources.erase(it);
 969     else
 970       ++it;
 971   }
 972   std::sort(resources.begin(), resources.end(),
 973             ResourcePrefetchPredictorTables::ResourceRowSorter());
 974   if (resources.size() > config_.max_resources_per_entry)
 975     resources.resize(config_.max_resources_per_entry);
 976
 977   // If the row has no resources, remove it from the cache and delete the
 978   // entry in the database. Else update the database.
 979   if (resources.empty()) {
 980     data_map->erase(key);
 981     BrowserThread::PostTask(
 982         BrowserThread::DB, FROM_HERE,
 983         base::Bind(&ResourcePrefetchPredictorTables::DeleteSingleDataPoint,
 984                    tables_,
 985                    key,
 986                    key_type));
 987   } else {
 988     bool is_host = key_type == PREFETCH_KEY_TYPE_HOST;
 989     PrefetchData empty_data(
 990         !is_host ? PREFETCH_KEY_TYPE_HOST : PREFETCH_KEY_TYPE_URL,
 991         std::string());
 992     const PrefetchData& host_data = is_host ? cache_entry->second : empty_data;
 993     const PrefetchData& url_data = is_host ? empty_data : cache_entry->second;
 994     BrowserThread::PostTask(
 995         BrowserThread::DB, FROM_HERE,
 996         base::Bind(&ResourcePrefetchPredictorTables::UpdateData,
 997                    tables_,
 998                    url_data,
 999                    host_data));
1000   }
1001 }
1002
1003 ////////////////////////////////////////////////////////////////////////////////
1004 // Page load time and accuracy measurement.
1005
1006 // This is essentially UMA_HISTOGRAM_MEDIUM_TIMES, but it avoids using the
1007 // STATIC_HISTOGRAM_POINTER_BLOCK in UMA_HISTOGRAM definitions.
1008 #define RPP_HISTOGRAM_MEDIUM_TIMES(name, page_load_time) \
1009   do { \
1010     base::HistogramBase* histogram = base::Histogram::FactoryTimeGet( \
1011         name, \
1012         base::TimeDelta::FromMilliseconds(10), \
1013         base::TimeDelta::FromMinutes(3), \
1014         50, \
1015         base::HistogramBase::kUmaTargetedHistogramFlag); \
1016     histogram->AddTime(page_load_time); \
1017   } while (0)
1018
1019 void ResourcePrefetchPredictor::ReportPageLoadTimeStats(
1020     base::TimeDelta plt) const {
1021   net::NetworkChangeNotifier::ConnectionType connection_type =
1022       net::NetworkChangeNotifier::GetConnectionType();
1023
1024   RPP_HISTOGRAM_MEDIUM_TIMES("ResourcePrefetchPredictor.PLT", plt);
1025   RPP_HISTOGRAM_MEDIUM_TIMES(
1026       "ResourcePrefetchPredictor.PLT_" + GetNetTypeStr(), plt);
1027   if (net::NetworkChangeNotifier::IsConnectionCellular(connection_type))
1028     RPP_HISTOGRAM_MEDIUM_TIMES("ResourcePrefetchPredictor.PLT_Cellular", plt);
1029 }
1030
1031 void ResourcePrefetchPredictor::ReportPageLoadTimePrefetchStats(
1032     base::TimeDelta plt,
1033     bool prefetched,
1034     base::Callback<void(int)> report_network_type_callback,
1035     PrefetchKeyType key_type) const {
1036   net::NetworkChangeNotifier::ConnectionType connection_type =
1037       net::NetworkChangeNotifier::GetConnectionType();
1038   bool on_cellular =
1039       net::NetworkChangeNotifier::IsConnectionCellular(connection_type);
1040
1041   report_network_type_callback.Run(CONNECTION_ALL);
1042   report_network_type_callback.Run(connection_type);
1043   if (on_cellular)
1044     report_network_type_callback.Run(CONNECTION_CELLULAR);
1045
1046   std::string prefetched_str;
1047   if (prefetched)
1048     prefetched_str = "Prefetched";
1049   else
1050     prefetched_str = "NotPrefetched";
1051
1052   RPP_HISTOGRAM_MEDIUM_TIMES(
1053       "ResourcePrefetchPredictor.PLT." + prefetched_str, plt);
1054   RPP_HISTOGRAM_MEDIUM_TIMES(
1055       "ResourcePrefetchPredictor.PLT." + prefetched_str + "_" + GetNetTypeStr(),
1056       plt);
1057   if (on_cellular) {
1058     RPP_HISTOGRAM_MEDIUM_TIMES(
1059         "ResourcePrefetchPredictor.PLT." + prefetched_str + "_Cellular", plt);
1060   }
1061
1062   if (!prefetched)
1063     return;
1064
1065   std::string type =
1066       key_type == PREFETCH_KEY_TYPE_HOST ? "Host" : "Url";
1067   RPP_HISTOGRAM_MEDIUM_TIMES(
1068       "ResourcePrefetchPredictor.PLT.Prefetched." + type, plt);
1069   RPP_HISTOGRAM_MEDIUM_TIMES(
1070       "ResourcePrefetchPredictor.PLT.Prefetched." + type + "_"
1071           + GetNetTypeStr(),
1072       plt);
1073   if (on_cellular) {
1074     RPP_HISTOGRAM_MEDIUM_TIMES(
1075         "ResourcePrefetchPredictor.PLT.Prefetched." + type + "_Cellular",
1076         plt);
1077   }
1078 }
1079
1080 void ResourcePrefetchPredictor::ReportAccuracyStats(
1081     PrefetchKeyType key_type,
1082     const std::vector<URLRequestSummary>& actual,
1083     ResourcePrefetcher::RequestVector* prefetched) const {
1084   // Annotate the results.
1085   std::map<GURL, bool> actual_resources;
1086   for (std::vector<URLRequestSummary>::const_iterator it = actual.begin();
1087        it != actual.end(); ++it) {
1088     actual_resources[it->resource_url] = it->was_cached;
1089   }
1090
1091   int prefetch_cancelled = 0, prefetch_failed = 0, prefetch_not_started = 0;
1092   // 'a_' -> actual, 'p_' -> predicted.
1093   int p_cache_a_cache = 0, p_cache_a_network = 0, p_cache_a_notused = 0,
1094       p_network_a_cache = 0, p_network_a_network = 0, p_network_a_notused = 0;
1095
1096   for (ResourcePrefetcher::RequestVector::iterator it = prefetched->begin();
1097        it != prefetched->end(); ++it) {
1098     ResourcePrefetcher::Request* req = *it;
1099
1100     // Set the usage states if the resource was actually used.
1101     std::map<GURL, bool>::const_iterator actual_it =
1102         actual_resources.find(req->resource_url);
1103     if (actual_it != actual_resources.end()) {
1104       if (actual_it->second) {
1105         req->usage_status =
1106             ResourcePrefetcher::Request::USAGE_STATUS_FROM_CACHE;
1107       } else {
1108         req->usage_status =
1109             ResourcePrefetcher::Request::USAGE_STATUS_FROM_NETWORK;
1110       }
1111     }
1112
1113     switch (req->prefetch_status) {
1114       // TODO(shishir): Add histogram for each cancellation reason.
1115       case ResourcePrefetcher::Request::PREFETCH_STATUS_REDIRECTED:
1116       case ResourcePrefetcher::Request::PREFETCH_STATUS_AUTH_REQUIRED:
1117       case ResourcePrefetcher::Request::PREFETCH_STATUS_CERT_REQUIRED:
1118       case ResourcePrefetcher::Request::PREFETCH_STATUS_CERT_ERROR:
1119       case ResourcePrefetcher::Request::PREFETCH_STATUS_CANCELLED:
1120         ++prefetch_cancelled;
1121         break;
1122
1123       case ResourcePrefetcher::Request::PREFETCH_STATUS_FAILED:
1124         ++prefetch_failed;
1125         break;
1126
1127       case ResourcePrefetcher::Request::PREFETCH_STATUS_FROM_CACHE:
1128         if (req->usage_status ==
1129             ResourcePrefetcher::Request::USAGE_STATUS_FROM_CACHE)
1130           ++p_cache_a_cache;
1131         else if (req->usage_status ==
1132                  ResourcePrefetcher::Request::USAGE_STATUS_FROM_NETWORK)
1133           ++p_cache_a_network;
1134         else
1135           ++p_cache_a_notused;
1136         break;
1137
1138       case ResourcePrefetcher::Request::PREFETCH_STATUS_FROM_NETWORK:
1139           if (req->usage_status ==
1140               ResourcePrefetcher::Request::USAGE_STATUS_FROM_CACHE)
1141             ++p_network_a_cache;
1142           else if (req->usage_status ==
1143                    ResourcePrefetcher::Request::USAGE_STATUS_FROM_NETWORK)
1144             ++p_network_a_network;
1145           else
1146             ++p_network_a_notused;
1147         break;
1148
1149       case ResourcePrefetcher::Request::PREFETCH_STATUS_NOT_STARTED:
1150         ++prefetch_not_started;
1151         break;
1152
1153       case ResourcePrefetcher::Request::PREFETCH_STATUS_STARTED:
1154         DLOG(FATAL) << "Invalid prefetch status";
1155         break;
1156     }
1157   }
1158
1159   int total_prefetched = p_cache_a_cache + p_cache_a_network + p_cache_a_notused
1160       + p_network_a_cache + p_network_a_network + p_network_a_notused;
1161
1162   std::string histogram_type = key_type == PREFETCH_KEY_TYPE_HOST ? "Host." :
1163       "Url.";
1164
1165   // Macros to avoid using the STATIC_HISTOGRAM_POINTER_BLOCK in UMA_HISTOGRAM
1166   // definitions.
1167 #define RPP_HISTOGRAM_PERCENTAGE(suffix, value) \
1168   { \
1169     std::string name = "ResourcePrefetchPredictor." + histogram_type + suffix; \
1170     std::string g_name = "ResourcePrefetchPredictor." + std::string(suffix); \
1171     base::HistogramBase* histogram = base::LinearHistogram::FactoryGet( \
1172         name, 1, 101, 102, base::Histogram::kUmaTargetedHistogramFlag); \
1173     histogram->Add(value); \
1174     UMA_HISTOGRAM_PERCENTAGE(g_name, value); \
1175   }
1176
1177   RPP_HISTOGRAM_PERCENTAGE("PrefetchCancelled",
1178                            prefetch_cancelled * 100.0 / total_prefetched);
1179   RPP_HISTOGRAM_PERCENTAGE("PrefetchFailed",
1180                            prefetch_failed * 100.0 / total_prefetched);
1181   RPP_HISTOGRAM_PERCENTAGE("PrefetchFromCacheUsedFromCache",
1182                            p_cache_a_cache * 100.0 / total_prefetched);
1183   RPP_HISTOGRAM_PERCENTAGE("PrefetchFromCacheUsedFromNetwork",
1184                            p_cache_a_network * 100.0 / total_prefetched);
1185   RPP_HISTOGRAM_PERCENTAGE("PrefetchFromCacheNotUsed",
1186                            p_cache_a_notused * 100.0 / total_prefetched);
1187   RPP_HISTOGRAM_PERCENTAGE("PrefetchFromNetworkUsedFromCache",
1188                            p_network_a_cache * 100.0 / total_prefetched);
1189   RPP_HISTOGRAM_PERCENTAGE("PrefetchFromNetworkUsedFromNetwork",
1190                            p_network_a_network * 100.0 / total_prefetched);
1191   RPP_HISTOGRAM_PERCENTAGE("PrefetchFromNetworkNotUsed",
1192                            p_network_a_notused * 100.0 / total_prefetched);
1193
1194   RPP_HISTOGRAM_PERCENTAGE(
1195       "PrefetchNotStarted",
1196       prefetch_not_started * 100.0 / (prefetch_not_started + total_prefetched));
1197
1198 #undef RPP_HISTOGRAM_PERCENTAGE
1199 }
1200
1201 void ResourcePrefetchPredictor::ReportPredictedAccuracyStats(
1202     PrefetchKeyType key_type,
1203     const std::vector<URLRequestSummary>& actual,
1204     const ResourcePrefetcher::RequestVector& predicted) const {
1205   std::map<GURL, bool> actual_resources;
1206   int from_network = 0;
1207   for (std::vector<URLRequestSummary>::const_iterator it = actual.begin();
1208        it != actual.end(); ++it) {
1209     actual_resources[it->resource_url] = it->was_cached;
1210     if (!it->was_cached)
1211       ++from_network;
1212   }
1213
1214   // Measure the accuracy at 25, 50 predicted resources.
1215   ReportPredictedAccuracyStatsHelper(key_type, predicted, actual_resources,
1216                                      from_network, 25);
1217   ReportPredictedAccuracyStatsHelper(key_type, predicted, actual_resources,
1218                                      from_network, 50);
1219 }
1220
1221 void ResourcePrefetchPredictor::ReportPredictedAccuracyStatsHelper(
1222     PrefetchKeyType key_type,
1223     const ResourcePrefetcher::RequestVector& predicted,
1224     const std::map<GURL, bool>& actual,
1225     size_t total_resources_fetched_from_network,
1226     size_t max_assumed_prefetched) const {
1227   int prefetch_cached = 0, prefetch_network = 0, prefetch_missed = 0;
1228   int num_assumed_prefetched = std::min(predicted.size(),
1229                                         max_assumed_prefetched);
1230   if (num_assumed_prefetched == 0)
1231     return;
1232
1233   for (int i = 0; i < num_assumed_prefetched; ++i) {
1234     const ResourcePrefetcher::Request& row = *(predicted[i]);
1235     std::map<GURL, bool>::const_iterator it = actual.find(row.resource_url);
1236     if (it == actual.end()) {
1237       ++prefetch_missed;
1238     } else if (it->second) {
1239       ++prefetch_cached;
1240     } else {
1241       ++prefetch_network;
1242     }
1243   }
1244
1245   std::string prefix = key_type == PREFETCH_KEY_TYPE_HOST ?
1246       "ResourcePrefetchPredictor.Host.Predicted" :
1247       "ResourcePrefetchPredictor.Url.Predicted";
1248   std::string suffix = "_" + base::SizeTToString(max_assumed_prefetched);
1249
1250   // Macros to avoid using the STATIC_HISTOGRAM_POINTER_BLOCK in UMA_HISTOGRAM
1251   // definitions.
1252 #define RPP_PREDICTED_HISTOGRAM_COUNTS(name, value) \
1253   { \
1254     std::string full_name = prefix + name + suffix; \
1255     base::HistogramBase* histogram = base::Histogram::FactoryGet( \
1256         full_name, 1, 1000000, 50, \
1257         base::Histogram::kUmaTargetedHistogramFlag); \
1258     histogram->Add(value); \
1259   }
1260
1261 #define RPP_PREDICTED_HISTOGRAM_PERCENTAGE(name, value) \
1262   { \
1263     std::string full_name = prefix + name + suffix; \
1264     base::HistogramBase* histogram = base::LinearHistogram::FactoryGet( \
1265         full_name, 1, 101, 102, base::Histogram::kUmaTargetedHistogramFlag); \
1266     histogram->Add(value); \
1267   }
1268
1269   RPP_PREDICTED_HISTOGRAM_COUNTS("PrefetchCount", num_assumed_prefetched);
1270   RPP_PREDICTED_HISTOGRAM_COUNTS("PrefetchMisses_Count", prefetch_missed);
1271   RPP_PREDICTED_HISTOGRAM_COUNTS("PrefetchFromCache_Count", prefetch_cached);
1272   RPP_PREDICTED_HISTOGRAM_COUNTS("PrefetchFromNetwork_Count", prefetch_network);
1273
1274   RPP_PREDICTED_HISTOGRAM_PERCENTAGE(
1275       "PrefetchMisses_PercentOfTotalPrefetched",
1276       prefetch_missed * 100.0 / num_assumed_prefetched);
1277   RPP_PREDICTED_HISTOGRAM_PERCENTAGE(
1278       "PrefetchFromCache_PercentOfTotalPrefetched",
1279       prefetch_cached * 100.0 / num_assumed_prefetched);
1280   RPP_PREDICTED_HISTOGRAM_PERCENTAGE(
1281       "PrefetchFromNetwork_PercentOfTotalPrefetched",
1282       prefetch_network * 100.0 / num_assumed_prefetched);
1283
1284   // Measure the ratio of total number of resources prefetched from network vs
1285   // the total number of resources fetched by the page from the network.
1286   if (total_resources_fetched_from_network > 0) {
1287     RPP_PREDICTED_HISTOGRAM_PERCENTAGE(
1288         "PrefetchFromNetworkPercentOfTotalFromNetwork",
1289         prefetch_network * 100.0 / total_resources_fetched_from_network);
1290   }
1291
1292 #undef RPP_HISTOGRAM_MEDIUM_TIMES
1293 #undef RPP_PREDICTED_HISTOGRAM_PERCENTAGE
1294 #undef RPP_PREDICTED_HISTOGRAM_COUNTS
1295 }
1296
1297 void ResourcePrefetchPredictor::OnURLsDeleted(
1298     history::HistoryService* history_service,
1299     bool all_history,
1300     bool expired,
1301     const history::URLRows& deleted_rows,
1302     const std::set<GURL>& favicon_urls) {
1303   DCHECK_CURRENTLY_ON(BrowserThread::UI);
1304   if (INITIALIZED != initialization_state_)
1305     return;
1306
1307   if (all_history) {
1308     DeleteAllUrls();
1309     UMA_HISTOGRAM_ENUMERATION("ResourcePrefetchPredictor.ReportingEvent",
1310                               REPORTING_EVENT_ALL_HISTORY_CLEARED,
1311                               REPORTING_EVENT_COUNT);
1312   } else {
1313     DeleteUrls(deleted_rows);
1314     UMA_HISTOGRAM_ENUMERATION("ResourcePrefetchPredictor.ReportingEvent",
1315                               REPORTING_EVENT_PARTIAL_HISTORY_CLEARED,
1316                               REPORTING_EVENT_COUNT);
1317   }
1318 }
1319
1320 void ResourcePrefetchPredictor::OnHistoryServiceLoaded(
1321     history::HistoryService* history_service) {
1322   OnHistoryAndCacheLoaded();
1323   history_service_observer_.Remove(history_service);
1324 }
1325
1326 void ResourcePrefetchPredictor::ConnectToHistoryService() {
1327   // Register for HistoryServiceLoading if it is not ready.
1328   history::HistoryService* history_service =
1329       HistoryServiceFactory::GetForProfile(profile_,
1330                                            ServiceAccessType::EXPLICIT_ACCESS);
1331   if (!history_service)
1332     return;
1333   if (history_service->BackendLoaded()) {
1334     // HistoryService is already loaded. Continue with Initialization.
1335     OnHistoryAndCacheLoaded();
1336     return;
1337   }
1338   DCHECK(!history_service_observer_.IsObserving(history_service));
1339   history_service_observer_.Add(history_service);
1340   return;
1341 }
1342
1343 }  // namespace predictors