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