chrome/browser/prerender/prerender_local_predictor.cc

   1 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "chrome/browser/prerender/prerender_local_predictor.h"
   6
   7 #include <algorithm>
   8 #include <ctype.h>
   9 #include <map>
  10 #include <set>
  11
  12 #include "base/metrics/histogram.h"
  13 #include "base/timer.h"
  14 #include "chrome/browser/prerender/prerender_histograms.h"
  15 #include "chrome/browser/prerender/prerender_manager.h"
  16 #include "chrome/browser/profiles/profile.h"
  17 #include "chrome/browser/history/history.h"
  18 #include "chrome/browser/history/history_database.h"
  19 #include "chrome/browser/history/history_service_factory.h"
  20 #include "content/public/browser/browser_thread.h"
  21 #include "content/public/common/page_transition_types.h"
  22
  23 using content::BrowserThread;
  24 using content::PageTransition;
  25 using history::URLID;
  26
  27 namespace prerender {
  28
  29 namespace {
  30
  31 // Task to lookup the URL for a given URLID.
  32 class GetURLForURLIDTask : public HistoryDBTask {
  33  public:
  34   GetURLForURLIDTask(URLID url_id, base::Callback<void(const GURL&)> callback)
  35       : url_id_(url_id),
  36         success_(false),
  37         callback_(callback),
  38         start_time_(base::Time::Now()) {
  39   }
  40
  41   virtual bool RunOnDBThread(history::HistoryBackend* backend,
  42                              history::HistoryDatabase* db) OVERRIDE {
  43     history::URLRow url_row;
  44     success_ = db->GetURLRow(url_id_, &url_row);
  45     if (success_)
  46       url_ = url_row.url();
  47     return true;
  48   }
  49
  50   virtual void DoneRunOnMainThread() OVERRIDE {
  51     if (success_) {
  52       callback_.Run(url_);
  53       UMA_HISTOGRAM_CUSTOM_TIMES("Prerender.LocalPredictorURLLookupTime",
  54                                  base::Time::Now() - start_time_,
  55                                  base::TimeDelta::FromMilliseconds(10),
  56                                  base::TimeDelta::FromSeconds(10),
  57                                  50);
  58     }
  59   }
  60
  61  private:
  62   virtual ~GetURLForURLIDTask() {}
  63
  64   URLID url_id_;
  65   bool success_;
  66   base::Callback<void(const GURL&)> callback_;
  67   base::Time start_time_;
  68   GURL url_;
  69   DISALLOW_COPY_AND_ASSIGN(GetURLForURLIDTask);
  70 };
  71
  72 // Task to load history from the visit database on startup.
  73 class GetVisitHistoryTask : public HistoryDBTask {
  74  public:
  75   GetVisitHistoryTask(PrerenderLocalPredictor* local_predictor,
  76                       int max_visits)
  77       : local_predictor_(local_predictor),
  78         max_visits_(max_visits),
  79         visit_history_(new std::vector<history::BriefVisitInfo>) {
  80   }
  81
  82   virtual bool RunOnDBThread(history::HistoryBackend* backend,
  83                              history::HistoryDatabase* db) OVERRIDE {
  84     db->GetBriefVisitInfoOfMostRecentVisits(max_visits_, visit_history_.get());
  85     return true;
  86   }
  87
  88   virtual void DoneRunOnMainThread() OVERRIDE {
  89     local_predictor_->OnGetInitialVisitHistory(visit_history_.Pass());
  90   }
  91
  92  private:
  93   virtual ~GetVisitHistoryTask() {}
  94
  95   PrerenderLocalPredictor* local_predictor_;
  96   int max_visits_;
  97   scoped_ptr<std::vector<history::BriefVisitInfo> > visit_history_;
  98   DISALLOW_COPY_AND_ASSIGN(GetVisitHistoryTask);
  99 };
 100
 101 // Maximum visit history to retrieve from the visit database.
 102 const int kMaxVisitHistory = 100 * 1000;
 103
 104 // Visit history size at which to trigger pruning, and number of items to prune.
 105 const int kVisitHistoryPruneThreshold = 120 * 1000;
 106 const int kVisitHistoryPruneAmount = 20 * 1000;
 107
 108 const int kMaxLocalPredictionTimeMs = 300 * 1000;
 109 const int kMinLocalPredictionTimeMs = 500;
 110
 111 bool IsBackForward(PageTransition transition) {
 112   return (transition & content::PAGE_TRANSITION_FORWARD_BACK) != 0;
 113 }
 114
 115 bool IsHomePage(PageTransition transition) {
 116   return (transition & content::PAGE_TRANSITION_HOME_PAGE) != 0;
 117 }
 118
 119 bool IsIntermediateRedirect(PageTransition transition) {
 120   return (transition & content::PAGE_TRANSITION_CHAIN_END) == 0;
 121 }
 122
 123 bool ShouldExcludeTransitionForPrediction(PageTransition transition) {
 124   return IsBackForward(transition) || IsHomePage(transition) ||
 125       IsIntermediateRedirect(transition);
 126 }
 127
 128 base::Time GetCurrentTime() {
 129   return base::Time::Now();
 130 }
 131
 132 bool StrCaseStr(std::string haystack, std::string needle) {
 133   std::transform(haystack.begin(), haystack.end(), haystack.begin(), ::tolower);
 134   std::transform(needle.begin(), needle.end(), needle.begin(), ::tolower);
 135   return (haystack.find(needle)!=std::string::npos);
 136 }
 137
 138 bool IsRootPageURL(const GURL& url) {
 139   return (url.path() == "/" || url.path() == "") && (!url.has_query()) &&
 140     (!url.has_ref());
 141 }
 142
 143 }  // namespace
 144
 145 struct PrerenderLocalPredictor::PrerenderData {
 146   PrerenderData(URLID url_id, const GURL& url, double priority,
 147                 base::Time start_time)
 148       : url_id(url_id),
 149         url(url),
 150         priority(priority),
 151         start_time(start_time) {
 152   }
 153
 154   URLID url_id;
 155   GURL url;
 156   double priority;
 157   // For expiration purposes, this is a synthetic start time consisting either
 158   // of the actual start time, or of the last time the page was re-requested
 159   // for prerendering - 10 seconds (unless the original request came after
 160   // that).  This is to emulate the effect of re-prerendering a page that is
 161   // about to expire, because it was re-requested for prerendering a second
 162   // time after the actual prerender being kept around.
 163   base::Time start_time;
 164   // The actual time this page was last requested for prerendering.
 165   base::Time actual_start_time;
 166
 167  private:
 168   DISALLOW_IMPLICIT_CONSTRUCTORS(PrerenderData);
 169 };
 170
 171 PrerenderLocalPredictor::PrerenderLocalPredictor(
 172     PrerenderManager* prerender_manager)
 173     : prerender_manager_(prerender_manager) {
 174   RecordEvent(EVENT_CONSTRUCTED);
 175   if (MessageLoop::current()) {
 176     timer_.Start(FROM_HERE,
 177                  base::TimeDelta::FromMilliseconds(kInitDelayMs),
 178                  this,
 179                  &PrerenderLocalPredictor::Init);
 180     RecordEvent(EVENT_INIT_SCHEDULED);
 181   }
 182 }
 183
 184 PrerenderLocalPredictor::~PrerenderLocalPredictor() {
 185   if (observing_history_service_.get())
 186     observing_history_service_->RemoveVisitDatabaseObserver(this);
 187 }
 188
 189 void PrerenderLocalPredictor::OnAddVisit(const history::BriefVisitInfo& info) {
 190   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
 191   RecordEvent(EVENT_ADD_VISIT);
 192   if (!visit_history_.get())
 193     return;
 194   visit_history_->push_back(info);
 195   if (static_cast<int>(visit_history_->size()) > kVisitHistoryPruneThreshold) {
 196     visit_history_->erase(visit_history_->begin(),
 197                           visit_history_->begin() + kVisitHistoryPruneAmount);
 198   }
 199   RecordEvent(EVENT_ADD_VISIT_INITIALIZED);
 200   if (current_prerender_.get() &&
 201       current_prerender_->url_id == info.url_id &&
 202       IsPrerenderStillValid(current_prerender_.get())) {
 203     prerender_manager_->histograms()->RecordLocalPredictorTimeUntilUsed(
 204         GetCurrentTime() - current_prerender_->actual_start_time,
 205         base::TimeDelta::FromMilliseconds(kMaxLocalPredictionTimeMs));
 206     last_swapped_in_prerender_.reset(current_prerender_.release());
 207     RecordEvent(EVENT_ADD_VISIT_PRERENDER_IDENTIFIED);
 208   }
 209   if (ShouldExcludeTransitionForPrediction(info.transition))
 210     return;
 211   RecordEvent(EVENT_ADD_VISIT_RELEVANT_TRANSITION);
 212   base::TimeDelta max_age =
 213       base::TimeDelta::FromMilliseconds(kMaxLocalPredictionTimeMs);
 214   base::TimeDelta min_age =
 215       base::TimeDelta::FromMilliseconds(kMinLocalPredictionTimeMs);
 216   std::set<URLID> next_urls_currently_found;
 217   std::map<URLID, int> next_urls_num_found;
 218   int num_occurrences_of_current_visit = 0;
 219   base::Time last_visited;
 220   URLID best_next_url = 0;
 221   int best_next_url_count = 0;
 222   const std::vector<history::BriefVisitInfo>& visits = *(visit_history_.get());
 223   for (int i = 0; i < static_cast<int>(visits.size()); i++) {
 224     if (!ShouldExcludeTransitionForPrediction(visits[i].transition)) {
 225       if (visits[i].url_id == info.url_id) {
 226         last_visited = visits[i].time;
 227         num_occurrences_of_current_visit++;
 228         next_urls_currently_found.clear();
 229         continue;
 230       }
 231       if (!last_visited.is_null() &&
 232           last_visited > visits[i].time - max_age &&
 233           last_visited < visits[i].time - min_age) {
 234         next_urls_currently_found.insert(visits[i].url_id);
 235       }
 236     }
 237     if (i == static_cast<int>(visits.size()) - 1 ||
 238         visits[i+1].url_id == info.url_id) {
 239       for (std::set<URLID>::iterator it = next_urls_currently_found.begin();
 240            it != next_urls_currently_found.end();
 241            ++it) {
 242         std::pair<std::map<URLID, int>::iterator, bool> insert_ret =
 243             next_urls_num_found.insert(std::pair<URLID, int>(*it, 0));
 244         std::map<URLID, int>::iterator num_found_it = insert_ret.first;
 245         num_found_it->second++;
 246         if (num_found_it->second > best_next_url_count) {
 247           best_next_url_count = num_found_it->second;
 248           best_next_url = *it;
 249         }
 250       }
 251     }
 252   }
 253
 254   // Only consider a candidate next page for prerendering if it was viewed
 255   // at least twice, and at least 10% of the time.
 256   if (num_occurrences_of_current_visit > 0 &&
 257       best_next_url_count > 1 &&
 258       best_next_url_count * 10 >= num_occurrences_of_current_visit) {
 259     RecordEvent(EVENT_ADD_VISIT_IDENTIFIED_PRERENDER_CANDIDATE);
 260     double priority = static_cast<double>(best_next_url_count) /
 261         static_cast<double>(num_occurrences_of_current_visit);
 262     if (ShouldReplaceCurrentPrerender(priority)) {
 263       RecordEvent(EVENT_START_URL_LOOKUP);
 264       HistoryService* history = GetHistoryIfExists();
 265       if (history) {
 266         history->ScheduleDBTask(
 267             new GetURLForURLIDTask(
 268                 best_next_url,
 269                 base::Bind(&PrerenderLocalPredictor::OnLookupURL,
 270                            base::Unretained(this),
 271                            best_next_url,
 272                            priority)),
 273             &history_db_consumer_);
 274       }
 275     }
 276   }
 277 }
 278
 279 void PrerenderLocalPredictor::OnLookupURL(history::URLID url_id,
 280                                           double priority,
 281                                           const GURL& url) {
 282   RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT);
 283
 284   base::Time current_time = GetCurrentTime();
 285   if (ShouldReplaceCurrentPrerender(priority)) {
 286     if (IsRootPageURL(url)) {
 287       RecordEvent(EVENT_ADD_VISIT_PRERENDERING);
 288       if (current_prerender_.get() && current_prerender_->url_id == url_id) {
 289         RecordEvent(EVENT_ADD_VISIT_PRERENDERING_EXTENDED);
 290         if (priority > current_prerender_->priority)
 291           current_prerender_->priority = priority;
 292         // If the prerender already existed, we want to extend it.  However,
 293         // we do not want to set its start_time to the current time to
 294         // disadvantage PLT computations when the prerender is swapped in.
 295         // So we set the new start time to current_time - 10s (since the vast
 296         // majority of PLTs are < 10s), provided that is not before the actual
 297         // time the prerender was started (so as to not artificially advantage
 298         // the PLT computation).
 299         base::Time simulated_new_start_time =
 300             current_time - base::TimeDelta::FromSeconds(10);
 301         if (simulated_new_start_time > current_prerender_->start_time)
 302           current_prerender_->start_time = simulated_new_start_time;
 303       } else {
 304         current_prerender_.reset(
 305             new PrerenderData(url_id, url, priority, current_time));
 306       }
 307       current_prerender_->actual_start_time = current_time;
 308     } else {
 309       RecordEvent(EVENT_ADD_VISIT_NOT_ROOTPAGE);
 310     }
 311   }
 312
 313   if (IsRootPageURL(url))
 314     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_ROOT_PAGE);
 315   if (url.SchemeIs("http"))
 316     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_IS_HTTP);
 317   if (url.has_query())
 318     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_HAS_QUERY_STRING);
 319   if (StrCaseStr(url.spec().c_str(), "logout") ||
 320       StrCaseStr(url.spec().c_str(), "signout"))
 321     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_CONTAINS_LOGOUT);
 322   if (StrCaseStr(url.spec().c_str(), "login") ||
 323       StrCaseStr(url.spec().c_str(), "signin"))
 324     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_CONTAINS_LOGIN);
 325 }
 326
 327 void PrerenderLocalPredictor::OnGetInitialVisitHistory(
 328     scoped_ptr<std::vector<history::BriefVisitInfo> > visit_history) {
 329   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
 330   DCHECK(!visit_history_.get());
 331   RecordEvent(EVENT_INIT_SUCCEEDED);
 332   // Since the visit history has descending timestamps, we must reverse it.
 333   visit_history_.reset(new std::vector<history::BriefVisitInfo>(
 334       visit_history->rbegin(), visit_history->rend()));
 335 }
 336
 337 HistoryService* PrerenderLocalPredictor::GetHistoryIfExists() const {
 338   Profile* profile = prerender_manager_->profile();
 339   if (!profile)
 340     return NULL;
 341   return HistoryServiceFactory::GetForProfileIfExists(profile);
 342 }
 343
 344 void PrerenderLocalPredictor::Init() {
 345   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
 346   RecordEvent(EVENT_INIT_STARTED);
 347   HistoryService* history = GetHistoryIfExists();
 348   if (!history) {
 349     RecordEvent(EVENT_INIT_FAILED_NO_HISTORY);
 350     return;
 351   }
 352   history->ScheduleDBTask(
 353       new GetVisitHistoryTask(this, kMaxVisitHistory),
 354       &history_db_consumer_);
 355   observing_history_service_ = history;
 356   observing_history_service_->AddVisitDatabaseObserver(this);
 357 }
 358
 359 void PrerenderLocalPredictor::OnPLTEventForURL(const GURL& url,
 360                                                base::TimeDelta page_load_time) {
 361   scoped_ptr<PrerenderData> prerender;
 362   if (DoesPrerenderMatchPLTRecord(last_swapped_in_prerender_.get(),
 363                                   url, page_load_time)) {
 364     prerender.reset(last_swapped_in_prerender_.release());
 365   }
 366   if (DoesPrerenderMatchPLTRecord(current_prerender_.get(),
 367                                   url, page_load_time)) {
 368     prerender.reset(current_prerender_.release());
 369   }
 370   if (!prerender.get())
 371     return;
 372   if (IsPrerenderStillValid(prerender.get())) {
 373     base::TimeDelta prerender_age = GetCurrentTime() - prerender->start_time;
 374     prerender_manager_->histograms()->RecordSimulatedLocalBrowsingBaselinePLT(
 375         page_load_time, url);
 376     if (prerender_age > page_load_time) {
 377       base::TimeDelta new_plt;
 378       if (prerender_age <  2 * page_load_time)
 379         new_plt = 2 * page_load_time - prerender_age;
 380       prerender_manager_->histograms()->RecordSimulatedLocalBrowsingPLT(
 381           new_plt, url);
 382     }
 383
 384   }
 385 }
 386
 387 bool PrerenderLocalPredictor::IsPrerenderStillValid(
 388     PrerenderLocalPredictor::PrerenderData* prerender) const {
 389   return (prerender &&
 390           (prerender->start_time +
 391            base::TimeDelta::FromMilliseconds(kMaxLocalPredictionTimeMs))
 392           > GetCurrentTime());
 393 }
 394
 395 void PrerenderLocalPredictor::RecordEvent(PrerenderLocalPredictor::Event event)
 396     const {
 397   prerender_manager_->histograms()->RecordLocalPredictorEvent(event);
 398 }
 399
 400 bool PrerenderLocalPredictor::DoesPrerenderMatchPLTRecord(
 401     PrerenderData* prerender, const GURL& url, base::TimeDelta plt) const {
 402   if (prerender && prerender->start_time < GetCurrentTime() - plt) {
 403     if (prerender->url.is_empty())
 404       RecordEvent(EVENT_ERROR_NO_PRERENDER_URL_FOR_PLT);
 405     return (prerender->url == url);
 406   } else {
 407     return false;
 408   }
 409 }
 410
 411 bool PrerenderLocalPredictor::ShouldReplaceCurrentPrerender(
 412     double priority) const {
 413   base::TimeDelta max_age =
 414       base::TimeDelta::FromMilliseconds(kMaxLocalPredictionTimeMs);
 415   return (!current_prerender_.get()) ||
 416     current_prerender_->priority < priority ||
 417     current_prerender_->start_time < GetCurrentTime() - max_age;
 418 }
 419
 420 }  // namespace prerender