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