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