Home | History | Annotate | Download | only in predictors 
      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/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/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.get())
    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.get())
    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_.get()) {
    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
   1249