chrome/browser/predictors/resource_prefetch_predictor.cc

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