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/stl_util.h"
  14 #include "base/strings/string_number_conversions.h"
  15 #include "base/strings/stringprintf.h"
  16 #include "base/time/time.h"
  17 #include "chrome/browser/chrome_notification_types.h"
  18 #include "chrome/browser/history/history_database.h"
  19 #include "chrome/browser/history/history_db_task.h"
  20 #include "chrome/browser/history/history_notifications.h"
  21 #include "chrome/browser/history/history_service.h"
  22 #include "chrome/browser/history/history_service_factory.h"
  23 #include "chrome/browser/predictors/predictor_database.h"
  24 #include "chrome/browser/predictors/predictor_database_factory.h"
  25 #include "chrome/browser/predictors/resource_prefetcher_manager.h"
  26 #include "chrome/browser/profiles/profile.h"
  27 #include "chrome/common/chrome_switches.h"
  28 #include "chrome/common/url_constants.h"
  29 #include "content/public/browser/browser_thread.h"
  30 #include "content/public/browser/navigation_controller.h"
  31 #include "content/public/browser/notification_service.h"
  32 #include "content/public/browser/notification_source.h"
  33 #include "content/public/browser/notification_types.h"
  34 #include "content/public/browser/resource_request_info.h"
  35 #include "content/public/browser/web_contents.h"
  36 #include "net/base/mime_util.h"
  37 #include "net/http/http_response_headers.h"
  38 #include "net/url_request/url_request.h"
  39 #include "net/url_request/url_request_context_getter.h"
  40
  41 using content::BrowserThread;
  42
  43 namespace {
  44
  45 // For reporting whether a subresource is handled or not, and for what reasons.
  46 enum ResourceStatus {
  47   RESOURCE_STATUS_HANDLED = 0,
  48   RESOURCE_STATUS_NOT_HTTP_PAGE = 1,
  49   RESOURCE_STATUS_NOT_HTTP_RESOURCE = 2,
  50   RESOURCE_STATUS_UNSUPPORTED_MIME_TYPE = 4,
  51   RESOURCE_STATUS_NOT_GET = 8,
  52   RESOURCE_STATUS_URL_TOO_LONG = 16,
  53   RESOURCE_STATUS_NOT_CACHEABLE = 32,
  54   RESOURCE_STATUS_HEADERS_MISSING = 64,
  55   RESOURCE_STATUS_MAX = 128,
  56 };
  57
  58 // For reporting various interesting events that occur during the loading of a
  59 // single main frame.
  60 enum NavigationEvent {
  61   NAVIGATION_EVENT_REQUEST_STARTED = 0,
  62   NAVIGATION_EVENT_REQUEST_REDIRECTED = 1,
  63   NAVIGATION_EVENT_REQUEST_REDIRECTED_EMPTY_URL = 2,
  64   NAVIGATION_EVENT_REQUEST_EXPIRED = 3,
  65   NAVIGATION_EVENT_RESPONSE_STARTED = 4,
  66   NAVIGATION_EVENT_ONLOAD = 5,
  67   NAVIGATION_EVENT_ONLOAD_EMPTY_URL = 6,
  68   NAVIGATION_EVENT_ONLOAD_UNTRACKED_URL = 7,
  69   NAVIGATION_EVENT_ONLOAD_TRACKED_URL = 8,
  70   NAVIGATION_EVENT_SHOULD_TRACK_URL = 9,
  71   NAVIGATION_EVENT_SHOULD_NOT_TRACK_URL = 10,
  72   NAVIGATION_EVENT_URL_TABLE_FULL = 11,
  73   NAVIGATION_EVENT_HAVE_PREDICTIONS_FOR_URL = 12,
  74   NAVIGATION_EVENT_NO_PREDICTIONS_FOR_URL = 13,
  75   NAVIGATION_EVENT_MAIN_FRAME_URL_TOO_LONG = 14,
  76   NAVIGATION_EVENT_HOST_TOO_LONG = 15,
  77   NAVIGATION_EVENT_COUNT = 16,
  78 };
  79
  80 // For reporting events of interest that are not tied to any navigation.
  81 enum ReportingEvent {
  82   REPORTING_EVENT_ALL_HISTORY_CLEARED = 0,
  83   REPORTING_EVENT_PARTIAL_HISTORY_CLEARED = 1,
  84   REPORTING_EVENT_COUNT = 2
  85 };
  86
  87 void RecordNavigationEvent(NavigationEvent event) {
  88   UMA_HISTOGRAM_ENUMERATION("ResourcePrefetchPredictor.NavigationEvent",
  89                             event,
  90                             NAVIGATION_EVENT_COUNT);
  91 }
  92
  93 }  // namespace
  94
  95 namespace predictors {
  96
  97 ////////////////////////////////////////////////////////////////////////////////
  98 // History lookup task.
  99
 100 // Used to fetch the visit count for a URL from the History database.
 101 class GetUrlVisitCountTask : public history::HistoryDBTask {
 102  public:
 103   typedef ResourcePrefetchPredictor::URLRequestSummary URLRequestSummary;
 104   typedef base::Callback<void(
 105       size_t,   // Visit count.
 106       const NavigationID&,
 107       const std::vector<URLRequestSummary>&)> VisitInfoCallback;
 108
 109   GetUrlVisitCountTask(
 110       const NavigationID& navigation_id,
 111       std::vector<URLRequestSummary>* requests,
 112       VisitInfoCallback callback)
 113       : visit_count_(0),
 114         navigation_id_(navigation_id),
 115         requests_(requests),
 116         callback_(callback) {
 117     DCHECK(requests_.get());
 118   }
 119
 120   virtual bool RunOnDBThread(history::HistoryBackend* backend,
 121                              history::HistoryDatabase* db) override {
 122     history::URLRow url_row;
 123     if (db->GetRowForURL(navigation_id_.main_frame_url, &url_row))
 124       visit_count_ = url_row.visit_count();
 125     return true;
 126   }
 127
 128   virtual void DoneRunOnMainThread() override {
 129     callback_.Run(visit_count_, navigation_id_, *requests_);
 130   }
 131
 132  private:
 133   virtual ~GetUrlVisitCountTask() { }
 134
 135   int visit_count_;
 136   NavigationID navigation_id_;
 137   scoped_ptr<std::vector<URLRequestSummary> > requests_;
 138   VisitInfoCallback callback_;
 139
 140   DISALLOW_COPY_AND_ASSIGN(GetUrlVisitCountTask);
 141 };
 142
 143 ////////////////////////////////////////////////////////////////////////////////
 144 // ResourcePrefetchPredictor static functions.
 145
 146 // static
 147 bool ResourcePrefetchPredictor::ShouldRecordRequest(
 148     net::URLRequest* request,
 149     content::ResourceType resource_type) {
 150   const content::ResourceRequestInfo* request_info =
 151       content::ResourceRequestInfo::ForRequest(request);
 152   if (!request_info)
 153     return false;
 154
 155   if (!request_info->IsMainFrame())
 156     return false;
 157
 158   return resource_type == content::RESOURCE_TYPE_MAIN_FRAME &&
 159       IsHandledMainPage(request);
 160 }
 161
 162 // static
 163 bool ResourcePrefetchPredictor::ShouldRecordResponse(
 164     net::URLRequest* response) {
 165   const content::ResourceRequestInfo* request_info =
 166       content::ResourceRequestInfo::ForRequest(response);
 167   if (!request_info)
 168     return false;
 169
 170   if (!request_info->IsMainFrame())
 171     return false;
 172
 173   return request_info->GetResourceType() == content::RESOURCE_TYPE_MAIN_FRAME ?
 174       IsHandledMainPage(response) : IsHandledSubresource(response);
 175 }
 176
 177 // static
 178 bool ResourcePrefetchPredictor::ShouldRecordRedirect(
 179     net::URLRequest* response) {
 180   const content::ResourceRequestInfo* request_info =
 181       content::ResourceRequestInfo::ForRequest(response);
 182   if (!request_info)
 183     return false;
 184
 185   if (!request_info->IsMainFrame())
 186     return false;
 187
 188   return request_info->GetResourceType() == content::RESOURCE_TYPE_MAIN_FRAME &&
 189       IsHandledMainPage(response);
 190 }
 191
 192 // static
 193 bool ResourcePrefetchPredictor::IsHandledMainPage(net::URLRequest* request) {
 194   return request->original_url().scheme() == url::kHttpScheme;
 195 }
 196
 197 // static
 198 bool ResourcePrefetchPredictor::IsHandledSubresource(
 199     net::URLRequest* response) {
 200   int resource_status = 0;
 201   if (response->first_party_for_cookies().scheme() != url::kHttpScheme)
 202     resource_status |= RESOURCE_STATUS_NOT_HTTP_PAGE;
 203
 204   if (response->original_url().scheme() != url::kHttpScheme)
 205     resource_status |= RESOURCE_STATUS_NOT_HTTP_RESOURCE;
 206
 207   std::string mime_type;
 208   response->GetMimeType(&mime_type);
 209   if (!mime_type.empty() &&
 210       !net::IsSupportedImageMimeType(mime_type.c_str()) &&
 211       !net::IsSupportedJavascriptMimeType(mime_type.c_str()) &&
 212       !net::MatchesMimeType("text/css", mime_type)) {
 213     resource_status |= RESOURCE_STATUS_UNSUPPORTED_MIME_TYPE;
 214   }
 215
 216   if (response->method() != "GET")
 217     resource_status |= RESOURCE_STATUS_NOT_GET;
 218
 219   if (response->original_url().spec().length() >
 220       ResourcePrefetchPredictorTables::kMaxStringLength) {
 221     resource_status |= RESOURCE_STATUS_URL_TOO_LONG;
 222   }
 223
 224   if (!response->response_info().headers.get())
 225     resource_status |= RESOURCE_STATUS_HEADERS_MISSING;
 226
 227   if (!IsCacheable(response))
 228     resource_status |= RESOURCE_STATUS_NOT_CACHEABLE;
 229
 230   UMA_HISTOGRAM_ENUMERATION("ResourcePrefetchPredictor.ResourceStatus",
 231                             resource_status,
 232                             RESOURCE_STATUS_MAX);
 233
 234   return resource_status == 0;
 235 }
 236
 237 // static
 238 bool ResourcePrefetchPredictor::IsCacheable(const net::URLRequest* response) {
 239   if (response->was_cached())
 240     return true;
 241
 242   // For non cached responses, we will ensure that the freshness lifetime is
 243   // some sane value.
 244   const net::HttpResponseInfo& response_info = response->response_info();
 245   if (!response_info.headers.get())
 246     return false;
 247   base::Time response_time(response_info.response_time);
 248   response_time += base::TimeDelta::FromSeconds(1);
 249   base::TimeDelta freshness =
 250       response_info.headers->GetFreshnessLifetimes(response_time).fresh;
 251   return freshness > base::TimeDelta();
 252 }
 253
 254 // static
 255 content::ResourceType ResourcePrefetchPredictor::GetResourceTypeFromMimeType(
 256     const std::string& mime_type,
 257     content::ResourceType fallback) {
 258   if (net::IsSupportedImageMimeType(mime_type.c_str()))
 259     return content::RESOURCE_TYPE_IMAGE;
 260   else if (net::IsSupportedJavascriptMimeType(mime_type.c_str()))
 261     return content::RESOURCE_TYPE_SCRIPT;
 262   else if (net::MatchesMimeType("text/css", mime_type))
 263     return content::RESOURCE_TYPE_STYLESHEET;
 264   else
 265     return fallback;
 266 }
 267
 268 ////////////////////////////////////////////////////////////////////////////////
 269 // ResourcePrefetchPredictor structs.
 270
 271 ResourcePrefetchPredictor::URLRequestSummary::URLRequestSummary()
 272     : resource_type(content::RESOURCE_TYPE_LAST_TYPE),
 273       was_cached(false) {
 274 }
 275
 276 ResourcePrefetchPredictor::URLRequestSummary::URLRequestSummary(
 277     const URLRequestSummary& other)
 278         : navigation_id(other.navigation_id),
 279           resource_url(other.resource_url),
 280           resource_type(other.resource_type),
 281           mime_type(other.mime_type),
 282           was_cached(other.was_cached),
 283           redirect_url(other.redirect_url) {
 284 }
 285
 286 ResourcePrefetchPredictor::URLRequestSummary::~URLRequestSummary() {
 287 }
 288
 289 ResourcePrefetchPredictor::Result::Result(
 290     PrefetchKeyType i_key_type,
 291     ResourcePrefetcher::RequestVector* i_requests)
 292     : key_type(i_key_type),
 293       requests(i_requests) {
 294 }
 295
 296 ResourcePrefetchPredictor::Result::~Result() {
 297 }
 298
 299 ////////////////////////////////////////////////////////////////////////////////
 300 // ResourcePrefetchPredictor.
 301
 302 ResourcePrefetchPredictor::ResourcePrefetchPredictor(
 303     const ResourcePrefetchPredictorConfig& config,
 304     Profile* profile)
 305     : profile_(profile),
 306       config_(config),
 307       initialization_state_(NOT_INITIALIZED),
 308       tables_(PredictorDatabaseFactory::GetForProfile(
 309           profile)->resource_prefetch_tables()),
 310       results_map_deleter_(&results_map_) {
 311   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 312
 313   // Some form of learning has to be enabled.
 314   DCHECK(config_.IsLearningEnabled());
 315   if (config_.IsURLPrefetchingEnabled(profile_))
 316     DCHECK(config_.IsURLLearningEnabled());
 317   if (config_.IsHostPrefetchingEnabled(profile_))
 318     DCHECK(config_.IsHostLearningEnabled());
 319 }
 320
 321 ResourcePrefetchPredictor::~ResourcePrefetchPredictor() {
 322 }
 323
 324 void ResourcePrefetchPredictor::RecordURLRequest(
 325     const URLRequestSummary& request) {
 326   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 327   if (initialization_state_ != INITIALIZED)
 328     return;
 329
 330   CHECK_EQ(request.resource_type, content::RESOURCE_TYPE_MAIN_FRAME);
 331   OnMainFrameRequest(request);
 332 }
 333
 334 void ResourcePrefetchPredictor::RecordURLResponse(
 335     const URLRequestSummary& response) {
 336   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 337   if (initialization_state_ != INITIALIZED)
 338     return;
 339
 340   if (response.resource_type == content::RESOURCE_TYPE_MAIN_FRAME)
 341     OnMainFrameResponse(response);
 342   else
 343     OnSubresourceResponse(response);
 344 }
 345
 346 void ResourcePrefetchPredictor::RecordURLRedirect(
 347     const URLRequestSummary& response) {
 348   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 349   if (initialization_state_ != INITIALIZED)
 350     return;
 351
 352   CHECK_EQ(response.resource_type, content::RESOURCE_TYPE_MAIN_FRAME);
 353   OnMainFrameRedirect(response);
 354 }
 355
 356 void ResourcePrefetchPredictor::RecordMainFrameLoadComplete(
 357     const NavigationID& navigation_id) {
 358   switch (initialization_state_) {
 359     case NOT_INITIALIZED:
 360       StartInitialization();
 361       break;
 362     case INITIALIZING:
 363       break;
 364     case INITIALIZED: {
 365       RecordNavigationEvent(NAVIGATION_EVENT_ONLOAD);
 366       // WebContents can return an empty URL if the navigation entry
 367       // corresponding to the navigation has not been created yet.
 368       if (navigation_id.main_frame_url.is_empty())
 369         RecordNavigationEvent(NAVIGATION_EVENT_ONLOAD_EMPTY_URL);
 370       else
 371         OnNavigationComplete(navigation_id);
 372       break;
 373     }
 374     default:
 375       NOTREACHED() << "Unexpected initialization_state_: "
 376                    << initialization_state_;
 377   }
 378 }
 379
 380 void ResourcePrefetchPredictor::FinishedPrefetchForNavigation(
 381     const NavigationID& navigation_id,
 382     PrefetchKeyType key_type,
 383     ResourcePrefetcher::RequestVector* requests) {
 384   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 385
 386   Result* result = new Result(key_type, requests);
 387   // Add the results to the results map.
 388   if (!results_map_.insert(std::make_pair(navigation_id, result)).second) {
 389     DLOG(FATAL) << "Returning results for existing navigation.";
 390     delete result;
 391   }
 392 }
 393
 394 void ResourcePrefetchPredictor::Observe(
 395     int type,
 396     const content::NotificationSource& source,
 397     const content::NotificationDetails& details) {
 398   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 399
 400   switch (type) {
 401     case chrome::NOTIFICATION_HISTORY_LOADED: {
 402       DCHECK_EQ(initialization_state_, INITIALIZING);
 403       notification_registrar_.Remove(this,
 404                                      chrome::NOTIFICATION_HISTORY_LOADED,
 405                                      content::Source<Profile>(profile_));
 406       OnHistoryAndCacheLoaded();
 407       break;
 408     }
 409
 410     case chrome::NOTIFICATION_HISTORY_URLS_DELETED: {
 411       DCHECK_EQ(initialization_state_, INITIALIZED);
 412       const content::Details<const history::URLsDeletedDetails>
 413           urls_deleted_details =
 414               content::Details<const history::URLsDeletedDetails>(details);
 415       if (urls_deleted_details->all_history) {
 416         DeleteAllUrls();
 417         UMA_HISTOGRAM_ENUMERATION("ResourcePrefetchPredictor.ReportingEvent",
 418                                   REPORTING_EVENT_ALL_HISTORY_CLEARED,
 419                                   REPORTING_EVENT_COUNT);
 420       } else {
 421         DeleteUrls(urls_deleted_details->rows);
 422         UMA_HISTOGRAM_ENUMERATION("ResourcePrefetchPredictor.ReportingEvent",
 423                                   REPORTING_EVENT_PARTIAL_HISTORY_CLEARED,
 424                                   REPORTING_EVENT_COUNT);
 425       }
 426       break;
 427     }
 428
 429     default:
 430       NOTREACHED() << "Unexpected notification observed.";
 431       break;
 432   }
 433 }
 434
 435 void ResourcePrefetchPredictor::Shutdown() {
 436   if (prefetch_manager_.get()) {
 437     prefetch_manager_->ShutdownOnUIThread();
 438     prefetch_manager_ = NULL;
 439   }
 440 }
 441
 442 void ResourcePrefetchPredictor::OnMainFrameRequest(
 443     const URLRequestSummary& request) {
 444   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 445   DCHECK_EQ(INITIALIZED, initialization_state_);
 446
 447   RecordNavigationEvent(NAVIGATION_EVENT_REQUEST_STARTED);
 448
 449   StartPrefetching(request.navigation_id);
 450
 451   // Cleanup older navigations.
 452   CleanupAbandonedNavigations(request.navigation_id);
 453
 454   // New empty navigation entry.
 455   inflight_navigations_.insert(std::make_pair(
 456       request.navigation_id,
 457       make_linked_ptr(new std::vector<URLRequestSummary>())));
 458 }
 459
 460 void ResourcePrefetchPredictor::OnMainFrameResponse(
 461     const URLRequestSummary& response) {
 462   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 463   if (initialization_state_ != INITIALIZED)
 464     return;
 465
 466   RecordNavigationEvent(NAVIGATION_EVENT_RESPONSE_STARTED);
 467
 468   StopPrefetching(response.navigation_id);
 469 }
 470
 471 void ResourcePrefetchPredictor::OnMainFrameRedirect(
 472     const URLRequestSummary& response) {
 473   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 474
 475   RecordNavigationEvent(NAVIGATION_EVENT_REQUEST_REDIRECTED);
 476
 477   // TODO(shishir): There are significant gains to be had here if we can use the
 478   // start URL in a redirect chain as the key to start prefetching. We can save
 479   // of redirect times considerably assuming that the redirect chains do not
 480   // change.
 481
 482   // Stop any inflight prefetching. Remove the older navigation.
 483   StopPrefetching(response.navigation_id);
 484   inflight_navigations_.erase(response.navigation_id);
 485
 486   // A redirect will not lead to another OnMainFrameRequest call, so record the
 487   // redirect url as a new navigation.
 488
 489   // The redirect url may be empty if the url was invalid.
 490   if (response.redirect_url.is_empty()) {
 491     RecordNavigationEvent(NAVIGATION_EVENT_REQUEST_REDIRECTED_EMPTY_URL);
 492     return;
 493   }
 494
 495   NavigationID navigation_id(response.navigation_id);
 496   navigation_id.main_frame_url = response.redirect_url;
 497   inflight_navigations_.insert(std::make_pair(
 498       navigation_id,
 499       make_linked_ptr(new std::vector<URLRequestSummary>())));
 500 }
 501
 502 void ResourcePrefetchPredictor::OnSubresourceResponse(
 503     const URLRequestSummary& response) {
 504   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 505
 506   NavigationMap::const_iterator nav_it =
 507         inflight_navigations_.find(response.navigation_id);
 508   if (nav_it == inflight_navigations_.end()) {
 509     return;
 510   }
 511
 512   nav_it->second->push_back(response);
 513 }
 514
 515 void ResourcePrefetchPredictor::OnNavigationComplete(
 516     const NavigationID& navigation_id) {
 517   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 518
 519   NavigationMap::iterator nav_it =
 520       inflight_navigations_.find(navigation_id);
 521   if (nav_it == inflight_navigations_.end()) {
 522     RecordNavigationEvent(NAVIGATION_EVENT_ONLOAD_UNTRACKED_URL);
 523     return;
 524   }
 525   RecordNavigationEvent(NAVIGATION_EVENT_ONLOAD_TRACKED_URL);
 526
 527   // Report any stats.
 528   if (prefetch_manager_.get()) {
 529     ResultsMap::iterator results_it = results_map_.find(navigation_id);
 530     bool have_prefetch_results = results_it != results_map_.end();
 531     UMA_HISTOGRAM_BOOLEAN("ResourcePrefetchPredictor.HavePrefetchResults",
 532                           have_prefetch_results);
 533     if (have_prefetch_results) {
 534       ReportAccuracyStats(results_it->second->key_type,
 535                           *(nav_it->second),
 536                           results_it->second->requests.get());
 537     }
 538   } else {
 539     scoped_ptr<ResourcePrefetcher::RequestVector> requests(
 540         new ResourcePrefetcher::RequestVector);
 541     PrefetchKeyType key_type;
 542     if (GetPrefetchData(navigation_id, requests.get(), &key_type)) {
 543       RecordNavigationEvent(NAVIGATION_EVENT_HAVE_PREDICTIONS_FOR_URL);
 544       ReportPredictedAccuracyStats(key_type,
 545                                    *(nav_it->second),
 546                                    *requests);
 547     } else {
 548       RecordNavigationEvent(NAVIGATION_EVENT_NO_PREDICTIONS_FOR_URL);
 549     }
 550   }
 551
 552   // Remove the navigation from the inflight navigations.
 553   std::vector<URLRequestSummary>* requests = (nav_it->second).release();
 554   inflight_navigations_.erase(nav_it);
 555
 556   // Kick off history lookup to determine if we should record the URL.
 557   HistoryService* history_service = HistoryServiceFactory::GetForProfile(
 558       profile_, Profile::EXPLICIT_ACCESS);
 559   DCHECK(history_service);
 560   history_service->ScheduleDBTask(
 561       scoped_ptr<history::HistoryDBTask>(
 562           new GetUrlVisitCountTask(
 563               navigation_id,
 564               requests,
 565               base::Bind(&ResourcePrefetchPredictor::OnVisitCountLookup,
 566                          AsWeakPtr()))),
 567       &history_lookup_consumer_);
 568 }
 569
 570 bool ResourcePrefetchPredictor::GetPrefetchData(
 571     const NavigationID& navigation_id,
 572     ResourcePrefetcher::RequestVector* prefetch_requests,
 573     PrefetchKeyType* key_type) {
 574   DCHECK(prefetch_requests);
 575   DCHECK(key_type);
 576
 577   *key_type = PREFETCH_KEY_TYPE_URL;
 578   const GURL& main_frame_url = navigation_id.main_frame_url;
 579
 580   bool use_url_data = config_.IsPrefetchingEnabled(profile_) ?
 581       config_.IsURLPrefetchingEnabled(profile_) :
 582       config_.IsURLLearningEnabled();
 583   if (use_url_data) {
 584     PrefetchDataMap::const_iterator iterator =
 585         url_table_cache_->find(main_frame_url.spec());
 586     if (iterator != url_table_cache_->end())
 587       PopulatePrefetcherRequest(iterator->second, prefetch_requests);
 588   }
 589   if (!prefetch_requests->empty())
 590     return true;
 591
 592   bool use_host_data = config_.IsPrefetchingEnabled(profile_) ?
 593       config_.IsHostPrefetchingEnabled(profile_) :
 594       config_.IsHostLearningEnabled();
 595   if (use_host_data) {
 596     PrefetchDataMap::const_iterator iterator =
 597         host_table_cache_->find(main_frame_url.host());
 598     if (iterator != host_table_cache_->end()) {
 599       *key_type = PREFETCH_KEY_TYPE_HOST;
 600       PopulatePrefetcherRequest(iterator->second, prefetch_requests);
 601     }
 602   }
 603
 604   return !prefetch_requests->empty();
 605 }
 606
 607 void ResourcePrefetchPredictor::PopulatePrefetcherRequest(
 608     const PrefetchData& data,
 609     ResourcePrefetcher::RequestVector* requests) {
 610   for (ResourceRows::const_iterator it = data.resources.begin();
 611        it != data.resources.end(); ++it) {
 612     float confidence = static_cast<float>(it->number_of_hits) /
 613         (it->number_of_hits + it->number_of_misses);
 614     if (confidence < config_.min_resource_confidence_to_trigger_prefetch ||
 615         it->number_of_hits < config_.min_resource_hits_to_trigger_prefetch) {
 616       continue;
 617     }
 618
 619     ResourcePrefetcher::Request* req = new ResourcePrefetcher::Request(
 620         it->resource_url);
 621     requests->push_back(req);
 622   }
 623 }
 624
 625 void ResourcePrefetchPredictor::StartPrefetching(
 626     const NavigationID& navigation_id) {
 627   if (!prefetch_manager_.get())  // Prefetching not enabled.
 628     return;
 629
 630   // Prefer URL based data first.
 631   scoped_ptr<ResourcePrefetcher::RequestVector> requests(
 632       new ResourcePrefetcher::RequestVector);
 633   PrefetchKeyType key_type;
 634   if (!GetPrefetchData(navigation_id, requests.get(), &key_type)) {
 635     // No prefetching data at host or URL level.
 636     return;
 637   }
 638
 639   BrowserThread::PostTask(BrowserThread::IO, FROM_HERE,
 640       base::Bind(&ResourcePrefetcherManager::MaybeAddPrefetch,
 641                  prefetch_manager_,
 642                  navigation_id,
 643                  key_type,
 644                  base::Passed(&requests)));
 645 }
 646
 647 void ResourcePrefetchPredictor::StopPrefetching(
 648     const NavigationID& navigation_id) {
 649   if (!prefetch_manager_.get())  // Not enabled.
 650     return;
 651
 652   BrowserThread::PostTask(
 653       BrowserThread::IO, FROM_HERE,
 654       base::Bind(&ResourcePrefetcherManager::MaybeRemovePrefetch,
 655                  prefetch_manager_,
 656                  navigation_id));
 657 }
 658
 659 void ResourcePrefetchPredictor::StartInitialization() {
 660   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 661
 662   DCHECK_EQ(initialization_state_, NOT_INITIALIZED);
 663   initialization_state_ = INITIALIZING;
 664
 665   // Create local caches using the database as loaded.
 666   scoped_ptr<PrefetchDataMap> url_data_map(new PrefetchDataMap());
 667   scoped_ptr<PrefetchDataMap> host_data_map(new PrefetchDataMap());
 668   PrefetchDataMap* url_data_ptr = url_data_map.get();
 669   PrefetchDataMap* host_data_ptr = host_data_map.get();
 670
 671   BrowserThread::PostTaskAndReply(
 672       BrowserThread::DB, FROM_HERE,
 673       base::Bind(&ResourcePrefetchPredictorTables::GetAllData,
 674                  tables_, url_data_ptr, host_data_ptr),
 675       base::Bind(&ResourcePrefetchPredictor::CreateCaches, AsWeakPtr(),
 676                  base::Passed(&url_data_map), base::Passed(&host_data_map)));
 677 }
 678
 679 void ResourcePrefetchPredictor::CreateCaches(
 680     scoped_ptr<PrefetchDataMap> url_data_map,
 681     scoped_ptr<PrefetchDataMap> host_data_map) {
 682   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 683
 684   DCHECK_EQ(initialization_state_, INITIALIZING);
 685   DCHECK(!url_table_cache_);
 686   DCHECK(!host_table_cache_);
 687   DCHECK(inflight_navigations_.empty());
 688
 689   url_table_cache_.reset(url_data_map.release());
 690   host_table_cache_.reset(host_data_map.release());
 691
 692   UMA_HISTOGRAM_COUNTS("ResourcePrefetchPredictor.UrlTableMainFrameUrlCount",
 693                        url_table_cache_->size());
 694   UMA_HISTOGRAM_COUNTS("ResourcePrefetchPredictor.HostTableHostCount",
 695                        host_table_cache_->size());
 696
 697   // Add notifications for history loading if it is not ready.
 698   HistoryService* history_service = HistoryServiceFactory::GetForProfile(
 699     profile_, Profile::EXPLICIT_ACCESS);
 700   if (!history_service) {
 701     notification_registrar_.Add(this, chrome::NOTIFICATION_HISTORY_LOADED,
 702                                 content::Source<Profile>(profile_));
 703   } else {
 704     OnHistoryAndCacheLoaded();
 705   }
 706 }
 707
 708 void ResourcePrefetchPredictor::OnHistoryAndCacheLoaded() {
 709   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 710   DCHECK_EQ(initialization_state_, INITIALIZING);
 711
 712   notification_registrar_.Add(this,
 713                               chrome::NOTIFICATION_HISTORY_URLS_DELETED,
 714                               content::Source<Profile>(profile_));
 715
 716   // Initialize the prefetch manager only if prefetching is enabled.
 717   if (config_.IsPrefetchingEnabled(profile_)) {
 718     prefetch_manager_ = new ResourcePrefetcherManager(
 719         this, config_, profile_->GetRequestContext());
 720   }
 721
 722   initialization_state_ = INITIALIZED;
 723 }
 724
 725 void ResourcePrefetchPredictor::CleanupAbandonedNavigations(
 726     const NavigationID& navigation_id) {
 727   static const base::TimeDelta max_navigation_age =
 728       base::TimeDelta::FromSeconds(config_.max_navigation_lifetime_seconds);
 729
 730   base::TimeTicks time_now = base::TimeTicks::Now();
 731   for (NavigationMap::iterator it = inflight_navigations_.begin();
 732        it != inflight_navigations_.end();) {
 733     if (it->first.IsSameRenderer(navigation_id) ||
 734         (time_now - it->first.creation_time > max_navigation_age)) {
 735       inflight_navigations_.erase(it++);
 736       RecordNavigationEvent(NAVIGATION_EVENT_REQUEST_EXPIRED);
 737     } else {
 738       ++it;
 739     }
 740   }
 741   for (ResultsMap::iterator it = results_map_.begin();
 742        it != results_map_.end();) {
 743     if (it->first.IsSameRenderer(navigation_id) ||
 744         (time_now - it->first.creation_time > max_navigation_age)) {
 745       delete it->second;
 746       results_map_.erase(it++);
 747     } else {
 748       ++it;
 749     }
 750   }
 751 }
 752
 753 void ResourcePrefetchPredictor::DeleteAllUrls() {
 754   inflight_navigations_.clear();
 755   url_table_cache_->clear();
 756   host_table_cache_->clear();
 757
 758   BrowserThread::PostTask(BrowserThread::DB, FROM_HERE,
 759       base::Bind(&ResourcePrefetchPredictorTables::DeleteAllData, tables_));
 760 }
 761
 762 void ResourcePrefetchPredictor::DeleteUrls(const history::URLRows& urls) {
 763   // Check all the urls in the database and pick out the ones that are present
 764   // in the cache.
 765   std::vector<std::string> urls_to_delete, hosts_to_delete;
 766
 767   for (history::URLRows::const_iterator it = urls.begin(); it != urls.end();
 768        ++it) {
 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 // Accuracy measurement.
1007
1008 void ResourcePrefetchPredictor::ReportAccuracyStats(
1009     PrefetchKeyType key_type,
1010     const std::vector<URLRequestSummary>& actual,
1011     ResourcePrefetcher::RequestVector* prefetched) const {
1012   // Annotate the results.
1013   std::map<GURL, bool> actual_resources;
1014   for (std::vector<URLRequestSummary>::const_iterator it = actual.begin();
1015        it != actual.end(); ++it) {
1016     actual_resources[it->resource_url] = it->was_cached;
1017   }
1018
1019   int prefetch_cancelled = 0, prefetch_failed = 0, prefetch_not_started = 0;
1020   // 'a_' -> actual, 'p_' -> predicted.
1021   int p_cache_a_cache = 0, p_cache_a_network = 0, p_cache_a_notused = 0,
1022       p_network_a_cache = 0, p_network_a_network = 0, p_network_a_notused = 0;
1023
1024   for (ResourcePrefetcher::RequestVector::iterator it = prefetched->begin();
1025        it != prefetched->end(); ++it) {
1026     ResourcePrefetcher::Request* req = *it;
1027
1028     // Set the usage states if the resource was actually used.
1029     std::map<GURL, bool>::iterator actual_it = actual_resources.find(
1030         req->resource_url);
1031     if (actual_it != actual_resources.end()) {
1032       if (actual_it->second) {
1033         req->usage_status =
1034             ResourcePrefetcher::Request::USAGE_STATUS_FROM_CACHE;
1035       } else {
1036         req->usage_status =
1037             ResourcePrefetcher::Request::USAGE_STATUS_FROM_NETWORK;
1038       }
1039     }
1040
1041     switch (req->prefetch_status) {
1042       // TODO(shishir): Add histogram for each cancellation reason.
1043       case ResourcePrefetcher::Request::PREFETCH_STATUS_REDIRECTED:
1044       case ResourcePrefetcher::Request::PREFETCH_STATUS_AUTH_REQUIRED:
1045       case ResourcePrefetcher::Request::PREFETCH_STATUS_CERT_REQUIRED:
1046       case ResourcePrefetcher::Request::PREFETCH_STATUS_CERT_ERROR:
1047       case ResourcePrefetcher::Request::PREFETCH_STATUS_CANCELLED:
1048         ++prefetch_cancelled;
1049         break;
1050
1051       case ResourcePrefetcher::Request::PREFETCH_STATUS_FAILED:
1052         ++prefetch_failed;
1053         break;
1054
1055       case ResourcePrefetcher::Request::PREFETCH_STATUS_FROM_CACHE:
1056         if (req->usage_status ==
1057             ResourcePrefetcher::Request::USAGE_STATUS_FROM_CACHE)
1058           ++p_cache_a_cache;
1059         else if (req->usage_status ==
1060                  ResourcePrefetcher::Request::USAGE_STATUS_FROM_NETWORK)
1061           ++p_cache_a_network;
1062         else
1063           ++p_cache_a_notused;
1064         break;
1065
1066       case ResourcePrefetcher::Request::PREFETCH_STATUS_FROM_NETWORK:
1067           if (req->usage_status ==
1068               ResourcePrefetcher::Request::USAGE_STATUS_FROM_CACHE)
1069             ++p_network_a_cache;
1070           else if (req->usage_status ==
1071                    ResourcePrefetcher::Request::USAGE_STATUS_FROM_NETWORK)
1072             ++p_network_a_network;
1073           else
1074             ++p_network_a_notused;
1075         break;
1076
1077       case ResourcePrefetcher::Request::PREFETCH_STATUS_NOT_STARTED:
1078         ++prefetch_not_started;
1079         break;
1080
1081       case ResourcePrefetcher::Request::PREFETCH_STATUS_STARTED:
1082         DLOG(FATAL) << "Invalid prefetch status";
1083         break;
1084     }
1085   }
1086
1087   int total_prefetched = p_cache_a_cache + p_cache_a_network + p_cache_a_notused
1088       + p_network_a_cache + p_network_a_network + p_network_a_notused;
1089
1090   std::string histogram_type = key_type == PREFETCH_KEY_TYPE_HOST ? "Host." :
1091       "Url.";
1092
1093   // Macros to avoid using the STATIC_HISTOGRAM_POINTER_BLOCK in UMA_HISTOGRAM
1094   // definitions.
1095 #define RPP_HISTOGRAM_PERCENTAGE(suffix, value) \
1096   { \
1097     std::string name = "ResourcePrefetchPredictor." + histogram_type + suffix; \
1098     std::string g_name = "ResourcePrefetchPredictor." + std::string(suffix); \
1099     base::HistogramBase* histogram = base::LinearHistogram::FactoryGet( \
1100         name, 1, 101, 102, base::Histogram::kUmaTargetedHistogramFlag); \
1101     histogram->Add(value); \
1102     UMA_HISTOGRAM_PERCENTAGE(g_name, value); \
1103   }
1104
1105   RPP_HISTOGRAM_PERCENTAGE("PrefetchCancelled",
1106                            prefetch_cancelled * 100.0 / total_prefetched);
1107   RPP_HISTOGRAM_PERCENTAGE("PrefetchFailed",
1108                            prefetch_failed * 100.0 / total_prefetched);
1109   RPP_HISTOGRAM_PERCENTAGE("PrefetchFromCacheUsedFromCache",
1110                            p_cache_a_cache * 100.0 / total_prefetched);
1111   RPP_HISTOGRAM_PERCENTAGE("PrefetchFromCacheUsedFromNetwork",
1112                            p_cache_a_network * 100.0 / total_prefetched);
1113   RPP_HISTOGRAM_PERCENTAGE("PrefetchFromCacheNotUsed",
1114                            p_cache_a_notused * 100.0 / total_prefetched);
1115   RPP_HISTOGRAM_PERCENTAGE("PrefetchFromNetworkUsedFromCache",
1116                            p_network_a_cache * 100.0 / total_prefetched);
1117   RPP_HISTOGRAM_PERCENTAGE("PrefetchFromNetworkUsedFromNetwork",
1118                            p_network_a_network * 100.0 / total_prefetched);
1119   RPP_HISTOGRAM_PERCENTAGE("PrefetchFromNetworkNotUsed",
1120                            p_network_a_notused * 100.0 / total_prefetched);
1121
1122   RPP_HISTOGRAM_PERCENTAGE(
1123       "PrefetchNotStarted",
1124       prefetch_not_started * 100.0 / (prefetch_not_started + total_prefetched));
1125
1126 #undef RPP_HISTOGRAM_PERCENTAGE
1127 }
1128
1129 void ResourcePrefetchPredictor::ReportPredictedAccuracyStats(
1130     PrefetchKeyType key_type,
1131     const std::vector<URLRequestSummary>& actual,
1132     const ResourcePrefetcher::RequestVector& predicted) const {
1133   std::map<GURL, bool> actual_resources;
1134   int from_network = 0;
1135   for (std::vector<URLRequestSummary>::const_iterator it = actual.begin();
1136        it != actual.end(); ++it) {
1137     actual_resources[it->resource_url] = it->was_cached;
1138     if (!it->was_cached)
1139       ++from_network;
1140   }
1141
1142   // Measure the accuracy at 25, 50 predicted resources.
1143   ReportPredictedAccuracyStatsHelper(key_type, predicted, actual_resources,
1144                                      from_network, 25);
1145   ReportPredictedAccuracyStatsHelper(key_type, predicted, actual_resources,
1146                                      from_network, 50);
1147 }
1148
1149 void ResourcePrefetchPredictor::ReportPredictedAccuracyStatsHelper(
1150     PrefetchKeyType key_type,
1151     const ResourcePrefetcher::RequestVector& predicted,
1152     const std::map<GURL, bool>& actual,
1153     size_t total_resources_fetched_from_network,
1154     size_t max_assumed_prefetched) const {
1155   int prefetch_cached = 0, prefetch_network = 0, prefetch_missed = 0;
1156   int num_assumed_prefetched = std::min(predicted.size(),
1157                                         max_assumed_prefetched);
1158   if (num_assumed_prefetched == 0)
1159     return;
1160
1161   for (int i = 0; i < num_assumed_prefetched; ++i) {
1162     const ResourcePrefetcher::Request& row = *(predicted[i]);
1163     std::map<GURL, bool>::const_iterator it = actual.find(row.resource_url);
1164     if (it == actual.end()) {
1165       ++prefetch_missed;
1166     } else if (it->second) {
1167       ++prefetch_cached;
1168     } else {
1169       ++prefetch_network;
1170     }
1171   }
1172
1173   std::string prefix = key_type == PREFETCH_KEY_TYPE_HOST ?
1174       "ResourcePrefetchPredictor.Host.Predicted" :
1175       "ResourcePrefetchPredictor.Url.Predicted";
1176   std::string suffix = "_" + base::IntToString(max_assumed_prefetched);
1177
1178   // Macros to avoid using the STATIC_HISTOGRAM_POINTER_BLOCK in UMA_HISTOGRAM
1179   // definitions.
1180 #define RPP_PREDICTED_HISTOGRAM_COUNTS(name, value) \
1181   { \
1182     std::string full_name = prefix + name + suffix; \
1183     base::HistogramBase* histogram = base::Histogram::FactoryGet( \
1184         full_name, 1, 1000000, 50, \
1185         base::Histogram::kUmaTargetedHistogramFlag); \
1186     histogram->Add(value); \
1187   }
1188
1189 #define RPP_PREDICTED_HISTOGRAM_PERCENTAGE(name, value) \
1190   { \
1191     std::string full_name = prefix + name + suffix; \
1192     base::HistogramBase* histogram = base::LinearHistogram::FactoryGet( \
1193         full_name, 1, 101, 102, base::Histogram::kUmaTargetedHistogramFlag); \
1194     histogram->Add(value); \
1195   }
1196
1197   RPP_PREDICTED_HISTOGRAM_COUNTS("PrefetchCount", num_assumed_prefetched);
1198   RPP_PREDICTED_HISTOGRAM_COUNTS("PrefetchMisses_Count", prefetch_missed);
1199   RPP_PREDICTED_HISTOGRAM_COUNTS("PrefetchFromCache_Count", prefetch_cached);
1200   RPP_PREDICTED_HISTOGRAM_COUNTS("PrefetchFromNetwork_Count", prefetch_network);
1201
1202   RPP_PREDICTED_HISTOGRAM_PERCENTAGE(
1203       "PrefetchMisses_PercentOfTotalPrefetched",
1204       prefetch_missed * 100.0 / num_assumed_prefetched);
1205   RPP_PREDICTED_HISTOGRAM_PERCENTAGE(
1206       "PrefetchFromCache_PercentOfTotalPrefetched",
1207       prefetch_cached * 100.0 / num_assumed_prefetched);
1208   RPP_PREDICTED_HISTOGRAM_PERCENTAGE(
1209       "PrefetchFromNetwork_PercentOfTotalPrefetched",
1210       prefetch_network * 100.0 / num_assumed_prefetched);
1211
1212   // Measure the ratio of total number of resources prefetched from network vs
1213   // the total number of resources fetched by the page from the network.
1214   if (total_resources_fetched_from_network > 0) {
1215     RPP_PREDICTED_HISTOGRAM_PERCENTAGE(
1216         "PrefetchFromNetworkPercentOfTotalFromNetwork",
1217         prefetch_network * 100.0 / total_resources_fetched_from_network);
1218   }
1219
1220 #undef RPP_PREDICTED_HISTOGRAM_PERCENTAGE
1221 #undef RPP_PREDICTED_HISTOGRAM_COUNTS
1222 }
1223
1224 }  // namespace predictors