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