Home | History | Annotate | Download | only in prerender 
      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 <ctype.h>
      8 
      9 #include <algorithm>
     10 #include <map>
     11 #include <set>
     12 #include <string>
     13 #include <utility>
     14 
     15 #include "base/metrics/field_trial.h"
     16 #include "base/metrics/histogram.h"
     17 #include "base/timer/timer.h"
     18 #include "chrome/browser/browser_process.h"
     19 #include "chrome/browser/history/history_database.h"
     20 #include "chrome/browser/history/history_db_task.h"
     21 #include "chrome/browser/history/history_service.h"
     22 #include "chrome/browser/history/history_service_factory.h"
     23 #include "chrome/browser/prerender/prerender_field_trial.h"
     24 #include "chrome/browser/prerender/prerender_handle.h"
     25 #include "chrome/browser/prerender/prerender_histograms.h"
     26 #include "chrome/browser/prerender/prerender_manager.h"
     27 #include "chrome/browser/profiles/profile.h"
     28 #include "chrome/browser/safe_browsing/database_manager.h"
     29 #include "chrome/browser/safe_browsing/safe_browsing_service.h"
     30 #include "chrome/browser/ui/tab_contents/tab_contents_iterator.h"
     31 #include "content/public/browser/browser_thread.h"
     32 #include "content/public/browser/navigation_controller.h"
     33 #include "content/public/browser/session_storage_namespace.h"
     34 #include "content/public/browser/web_contents.h"
     35 #include "content/public/browser/web_contents_view.h"
     36 #include "content/public/common/page_transition_types.h"
     37 #include "crypto/secure_hash.h"
     38 #include "grit/browser_resources.h"
     39 #include "ui/base/resource/resource_bundle.h"
     40 #include "url/url_canon.h"
     41 
     42 using content::BrowserThread;
     43 using content::PageTransition;
     44 using content::SessionStorageNamespace;
     45 using content::WebContents;
     46 using history::URLID;
     47 using predictors::LoggedInPredictorTable;
     48 using std::string;
     49 using std::vector;
     50 
     51 namespace prerender {
     52 
     53 namespace {
     54 
     55 static const size_t kURLHashSize = 5;
     56 static const int kNumPrerenderCandidates = 5;
     57 
     58 }  // namespace
     59 
     60 // When considering a candidate URL to be prerendered, we need to collect the
     61 // data in this struct to make the determination whether we should issue the
     62 // prerender or not.
     63 struct PrerenderLocalPredictor::LocalPredictorURLInfo {
     64   URLID id;
     65   GURL url;
     66   bool url_lookup_success;
     67   bool logged_in;
     68   bool logged_in_lookup_ok;
     69   double priority;
     70 };
     71 
     72 // A struct consisting of everything needed for launching a potential prerender
     73 // on a navigation: The navigation URL (source) triggering potential prerenders,
     74 // and a set of candidate URLs.
     75 struct PrerenderLocalPredictor::LocalPredictorURLLookupInfo {
     76   LocalPredictorURLInfo source_url_;
     77   vector<LocalPredictorURLInfo> candidate_urls_;
     78   explicit LocalPredictorURLLookupInfo(URLID source_id) {
     79     source_url_.id = source_id;
     80   }
     81   void MaybeAddCandidateURL(URLID id, double priority) {
     82     // TODO(tburkard): clean up this code, potentially using a list or a heap
     83     LocalPredictorURLInfo info;
     84     info.id = id;
     85     info.priority = priority;
     86     int insert_pos = candidate_urls_.size();
     87     if (insert_pos < kNumPrerenderCandidates)
     88       candidate_urls_.push_back(info);
     89     while (insert_pos > 0 &&
     90            candidate_urls_[insert_pos - 1].priority < info.priority) {
     91       if (insert_pos < kNumPrerenderCandidates)
     92         candidate_urls_[insert_pos] = candidate_urls_[insert_pos - 1];
     93       insert_pos--;
     94     }
     95     if (insert_pos < kNumPrerenderCandidates)
     96       candidate_urls_[insert_pos] = info;
     97   }
     98 };
     99 
    100 namespace {
    101 
    102 // Task to lookup the URL for a given URLID.
    103 class GetURLForURLIDTask : public history::HistoryDBTask {
    104  public:
    105   GetURLForURLIDTask(
    106       PrerenderLocalPredictor::LocalPredictorURLLookupInfo* request,
    107       const base::Closure& callback)
    108       : request_(request),
    109         callback_(callback),
    110         start_time_(base::Time::Now()) {
    111   }
    112 
    113   virtual bool RunOnDBThread(history::HistoryBackend* backend,
    114                              history::HistoryDatabase* db) OVERRIDE {
    115     DoURLLookup(db, &request_->source_url_);
    116     for (int i = 0; i < static_cast<int>(request_->candidate_urls_.size()); i++)
    117       DoURLLookup(db, &request_->candidate_urls_[i]);
    118     return true;
    119   }
    120 
    121   virtual void DoneRunOnMainThread() OVERRIDE {
    122     callback_.Run();
    123     UMA_HISTOGRAM_CUSTOM_TIMES("Prerender.LocalPredictorURLLookupTime",
    124                                base::Time::Now() - start_time_,
    125                                base::TimeDelta::FromMilliseconds(10),
    126                                base::TimeDelta::FromSeconds(10),
    127                                50);
    128   }
    129 
    130  private:
    131   virtual ~GetURLForURLIDTask() {}
    132 
    133   void DoURLLookup(history::HistoryDatabase* db,
    134                    PrerenderLocalPredictor::LocalPredictorURLInfo* request) {
    135     history::URLRow url_row;
    136     request->url_lookup_success = db->GetURLRow(request->id, &url_row);
    137     if (request->url_lookup_success)
    138       request->url = url_row.url();
    139   }
    140 
    141   PrerenderLocalPredictor::LocalPredictorURLLookupInfo* request_;
    142   base::Closure callback_;
    143   base::Time start_time_;
    144   DISALLOW_COPY_AND_ASSIGN(GetURLForURLIDTask);
    145 };
    146 
    147 // Task to load history from the visit database on startup.
    148 class GetVisitHistoryTask : public history::HistoryDBTask {
    149  public:
    150   GetVisitHistoryTask(PrerenderLocalPredictor* local_predictor,
    151                       int max_visits)
    152       : local_predictor_(local_predictor),
    153         max_visits_(max_visits),
    154         visit_history_(new vector<history::BriefVisitInfo>) {
    155   }
    156 
    157   virtual bool RunOnDBThread(history::HistoryBackend* backend,
    158                              history::HistoryDatabase* db) OVERRIDE {
    159     db->GetBriefVisitInfoOfMostRecentVisits(max_visits_, visit_history_.get());
    160     return true;
    161   }
    162 
    163   virtual void DoneRunOnMainThread() OVERRIDE {
    164     local_predictor_->OnGetInitialVisitHistory(visit_history_.Pass());
    165   }
    166 
    167  private:
    168   virtual ~GetVisitHistoryTask() {}
    169 
    170   PrerenderLocalPredictor* local_predictor_;
    171   int max_visits_;
    172   scoped_ptr<vector<history::BriefVisitInfo> > visit_history_;
    173   DISALLOW_COPY_AND_ASSIGN(GetVisitHistoryTask);
    174 };
    175 
    176 // Maximum visit history to retrieve from the visit database.
    177 const int kMaxVisitHistory = 100 * 1000;
    178 
    179 // Visit history size at which to trigger pruning, and number of items to prune.
    180 const int kVisitHistoryPruneThreshold = 120 * 1000;
    181 const int kVisitHistoryPruneAmount = 20 * 1000;
    182 
    183 const int kMinLocalPredictionTimeMs = 500;
    184 
    185 int GetMaxLocalPredictionTimeMs() {
    186   return GetLocalPredictorTTLSeconds() * 1000;
    187 }
    188 
    189 bool IsBackForward(PageTransition transition) {
    190   return (transition & content::PAGE_TRANSITION_FORWARD_BACK) != 0;
    191 }
    192 
    193 bool IsHomePage(PageTransition transition) {
    194   return (transition & content::PAGE_TRANSITION_HOME_PAGE) != 0;
    195 }
    196 
    197 bool IsIntermediateRedirect(PageTransition transition) {
    198   return (transition & content::PAGE_TRANSITION_CHAIN_END) == 0;
    199 }
    200 
    201 bool IsFormSubmit(PageTransition transition) {
    202   return (transition & content::PAGE_TRANSITION_FORM_SUBMIT) != 0;
    203 }
    204 
    205 bool ShouldExcludeTransitionForPrediction(PageTransition transition) {
    206   return IsBackForward(transition) || IsHomePage(transition) ||
    207       IsIntermediateRedirect(transition);
    208 }
    209 
    210 base::Time GetCurrentTime() {
    211   return base::Time::Now();
    212 }
    213 
    214 bool StringContainsIgnoringCase(string haystack, string needle) {
    215   std::transform(haystack.begin(), haystack.end(), haystack.begin(), ::tolower);
    216   std::transform(needle.begin(), needle.end(), needle.begin(), ::tolower);
    217   return haystack.find(needle) != string::npos;
    218 }
    219 
    220 bool IsExtendedRootURL(const GURL& url) {
    221   const string& path = url.path();
    222   return path == "/index.html" || path == "/home.html" ||
    223       path == "/main.html" ||
    224       path == "/index.htm" || path == "/home.htm" || path == "/main.htm" ||
    225       path == "/index.php" || path == "/home.php" || path == "/main.php" ||
    226       path == "/index.asp" || path == "/home.asp" || path == "/main.asp" ||
    227       path == "/index.py" || path == "/home.py" || path == "/main.py" ||
    228       path == "/index.pl" || path == "/home.pl" || path == "/main.pl";
    229 }
    230 
    231 bool IsRootPageURL(const GURL& url) {
    232   return (url.path() == "/" || url.path() == "" || IsExtendedRootURL(url)) &&
    233       (!url.has_query()) && (!url.has_ref());
    234 }
    235 
    236 bool IsLogInURL(const GURL& url) {
    237   return StringContainsIgnoringCase(url.spec().c_str(), "login") ||
    238       StringContainsIgnoringCase(url.spec().c_str(), "signin");
    239 }
    240 
    241 bool IsLogOutURL(const GURL& url) {
    242   return StringContainsIgnoringCase(url.spec().c_str(), "logout") ||
    243       StringContainsIgnoringCase(url.spec().c_str(), "signout");
    244 }
    245 
    246 int64 URLHashToInt64(const unsigned char* data) {
    247   COMPILE_ASSERT(kURLHashSize < sizeof(int64), url_hash_must_fit_in_int64);
    248   int64 value = 0;
    249   memcpy(&value, data, kURLHashSize);
    250   return value;
    251 }
    252 
    253 int64 GetInt64URLHashForURL(const GURL& url) {
    254   COMPILE_ASSERT(kURLHashSize < sizeof(int64), url_hash_must_fit_in_int64);
    255   scoped_ptr<crypto::SecureHash> hash(
    256       crypto::SecureHash::Create(crypto::SecureHash::SHA256));
    257   int64 hash_value = 0;
    258   const char* url_string = url.spec().c_str();
    259   hash->Update(url_string, strlen(url_string));
    260   hash->Finish(&hash_value, kURLHashSize);
    261   return hash_value;
    262 }
    263 
    264 bool URLsIdenticalIgnoringFragments(const GURL& url1, const GURL& url2) {
    265   url_canon::Replacements<char> replacement;
    266   replacement.ClearRef();
    267   GURL u1 = url1.ReplaceComponents(replacement);
    268   GURL u2 = url2.ReplaceComponents(replacement);
    269   return (u1 == u2);
    270 }
    271 
    272 void LookupLoggedInStatesOnDBThread(
    273     scoped_refptr<LoggedInPredictorTable> logged_in_predictor_table,
    274     PrerenderLocalPredictor::LocalPredictorURLLookupInfo* request_) {
    275   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::DB));
    276   for (int i = 0; i < static_cast<int>(request_->candidate_urls_.size()); i++) {
    277     PrerenderLocalPredictor::LocalPredictorURLInfo* info =
    278         &request_->candidate_urls_[i];
    279     if (info->url_lookup_success) {
    280       logged_in_predictor_table->HasUserLoggedIn(
    281           info->url, &info->logged_in, &info->logged_in_lookup_ok);
    282     } else {
    283       info->logged_in_lookup_ok = false;
    284     }
    285   }
    286 }
    287 
    288 }  // namespace
    289 
    290 struct PrerenderLocalPredictor::PrerenderProperties {
    291   PrerenderProperties(URLID url_id, const GURL& url, double priority,
    292                 base::Time start_time)
    293       : url_id(url_id),
    294         url(url),
    295         priority(priority),
    296         start_time(start_time) {
    297   }
    298 
    299   // Default constructor for dummy element
    300   PrerenderProperties()
    301       : priority(0.0) {
    302   }
    303 
    304   double GetCurrentDecayedPriority() {
    305     // If we are no longer prerendering, the priority is 0.
    306     if (!prerender_handle || !prerender_handle->IsPrerendering())
    307       return 0.0;
    308     int half_life_time_seconds =
    309         GetLocalPredictorPrerenderPriorityHalfLifeTimeSeconds();
    310     if (half_life_time_seconds < 1)
    311       return priority;
    312     double multiple_elapsed =
    313         (GetCurrentTime() - actual_start_time).InMillisecondsF() /
    314         base::TimeDelta::FromSeconds(half_life_time_seconds).InMillisecondsF();
    315     // Decay factor: 2 ^ (-multiple_elapsed)
    316     double decay_factor = exp(- multiple_elapsed * log(2.0));
    317     return priority * decay_factor;
    318   }
    319 
    320   URLID url_id;
    321   GURL url;
    322   double priority;
    323   // For expiration purposes, this is a synthetic start time consisting either
    324   // of the actual start time, or of the last time the page was re-requested
    325   // for prerendering - 10 seconds (unless the original request came after
    326   // that).  This is to emulate the effect of re-prerendering a page that is
    327   // about to expire, because it was re-requested for prerendering a second
    328   // time after the actual prerender being kept around.
    329   base::Time start_time;
    330   // The actual time this page was last requested for prerendering.
    331   base::Time actual_start_time;
    332   scoped_ptr<PrerenderHandle> prerender_handle;
    333   // Indicates whether this prerender would have matched a URL navigated to,
    334   // but was not swapped in for some reason.
    335   bool would_have_matched;
    336 };
    337 
    338 PrerenderLocalPredictor::PrerenderLocalPredictor(
    339     PrerenderManager* prerender_manager)
    340     : prerender_manager_(prerender_manager),
    341       is_visit_database_observer_(false),
    342       weak_factory_(this) {
    343   RecordEvent(EVENT_CONSTRUCTED);
    344   if (base::MessageLoop::current()) {
    345     timer_.Start(FROM_HERE,
    346                  base::TimeDelta::FromMilliseconds(kInitDelayMs),
    347                  this,
    348                  &PrerenderLocalPredictor::Init);
    349     RecordEvent(EVENT_INIT_SCHEDULED);
    350   }
    351 
    352   static const size_t kChecksumHashSize = 32;
    353   base::RefCountedStaticMemory* url_whitelist_data =
    354       ResourceBundle::GetSharedInstance().LoadDataResourceBytes(
    355           IDR_PRERENDER_URL_WHITELIST);
    356   size_t size = url_whitelist_data->size();
    357   const unsigned char* front = url_whitelist_data->front();
    358   if (size < kChecksumHashSize ||
    359       (size - kChecksumHashSize) % kURLHashSize != 0) {
    360     RecordEvent(EVENT_URL_WHITELIST_ERROR);
    361     return;
    362   }
    363   scoped_ptr<crypto::SecureHash> hash(
    364       crypto::SecureHash::Create(crypto::SecureHash::SHA256));
    365   hash->Update(front + kChecksumHashSize, size - kChecksumHashSize);
    366   char hash_value[kChecksumHashSize];
    367   hash->Finish(hash_value, kChecksumHashSize);
    368   if (memcmp(hash_value, front, kChecksumHashSize)) {
    369     RecordEvent(EVENT_URL_WHITELIST_ERROR);
    370     return;
    371   }
    372   for (const unsigned char* p = front + kChecksumHashSize;
    373        p < front + size;
    374        p += kURLHashSize) {
    375     url_whitelist_.insert(URLHashToInt64(p));
    376   }
    377   RecordEvent(EVENT_URL_WHITELIST_OK);
    378 }
    379 
    380 PrerenderLocalPredictor::~PrerenderLocalPredictor() {
    381   Shutdown();
    382   for (int i = 0; i < static_cast<int>(issued_prerenders_.size()); i++) {
    383     PrerenderProperties* p = issued_prerenders_[i];
    384     DCHECK(p != NULL);
    385     if (p->prerender_handle)
    386       p->prerender_handle->OnCancel();
    387   }
    388 }
    389 
    390 void PrerenderLocalPredictor::Shutdown() {
    391   timer_.Stop();
    392   if (is_visit_database_observer_) {
    393     HistoryService* history = GetHistoryIfExists();
    394     CHECK(history);
    395     history->RemoveVisitDatabaseObserver(this);
    396     is_visit_database_observer_ = false;
    397   }
    398 }
    399 
    400 void PrerenderLocalPredictor::OnAddVisit(const history::BriefVisitInfo& info) {
    401   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    402   RecordEvent(EVENT_ADD_VISIT);
    403   if (!visit_history_.get())
    404     return;
    405   visit_history_->push_back(info);
    406   if (static_cast<int>(visit_history_->size()) > kVisitHistoryPruneThreshold) {
    407     visit_history_->erase(visit_history_->begin(),
    408                           visit_history_->begin() + kVisitHistoryPruneAmount);
    409   }
    410   RecordEvent(EVENT_ADD_VISIT_INITIALIZED);
    411   if (current_prerender_.get() &&
    412       current_prerender_->url_id == info.url_id &&
    413       IsPrerenderStillValid(current_prerender_.get())) {
    414     UMA_HISTOGRAM_CUSTOM_TIMES(
    415         "Prerender.LocalPredictorTimeUntilUsed",
    416         GetCurrentTime() - current_prerender_->actual_start_time,
    417         base::TimeDelta::FromMilliseconds(10),
    418         base::TimeDelta::FromMilliseconds(GetMaxLocalPredictionTimeMs()),
    419         50);
    420     last_swapped_in_prerender_.reset(current_prerender_.release());
    421     RecordEvent(EVENT_ADD_VISIT_PRERENDER_IDENTIFIED);
    422   }
    423   if (ShouldExcludeTransitionForPrediction(info.transition))
    424     return;
    425   RecordEvent(EVENT_ADD_VISIT_RELEVANT_TRANSITION);
    426   base::TimeDelta max_age =
    427       base::TimeDelta::FromMilliseconds(GetMaxLocalPredictionTimeMs());
    428   base::TimeDelta min_age =
    429       base::TimeDelta::FromMilliseconds(kMinLocalPredictionTimeMs);
    430   std::set<URLID> next_urls_currently_found;
    431   std::map<URLID, int> next_urls_num_found;
    432   int num_occurrences_of_current_visit = 0;
    433   base::Time last_visited;
    434   scoped_ptr<LocalPredictorURLLookupInfo> lookup_info(
    435       new LocalPredictorURLLookupInfo(info.url_id));
    436   const vector<history::BriefVisitInfo>& visits = *(visit_history_.get());
    437   for (int i = 0; i < static_cast<int>(visits.size()); i++) {
    438     if (!ShouldExcludeTransitionForPrediction(visits[i].transition)) {
    439       if (visits[i].url_id == info.url_id) {
    440         last_visited = visits[i].time;
    441         num_occurrences_of_current_visit++;
    442         next_urls_currently_found.clear();
    443         continue;
    444       }
    445       if (!last_visited.is_null() &&
    446           last_visited > visits[i].time - max_age &&
    447           last_visited < visits[i].time - min_age) {
    448         if (!IsFormSubmit(visits[i].transition))
    449           next_urls_currently_found.insert(visits[i].url_id);
    450       }
    451     }
    452     if (i == static_cast<int>(visits.size()) - 1 ||
    453         visits[i+1].url_id == info.url_id) {
    454       for (std::set<URLID>::iterator it = next_urls_currently_found.begin();
    455            it != next_urls_currently_found.end();
    456            ++it) {
    457         std::pair<std::map<URLID, int>::iterator, bool> insert_ret =
    458             next_urls_num_found.insert(std::pair<URLID, int>(*it, 0));
    459         std::map<URLID, int>::iterator num_found_it = insert_ret.first;
    460         num_found_it->second++;
    461       }
    462     }
    463   }
    464 
    465   for (std::map<URLID, int>::const_iterator it = next_urls_num_found.begin();
    466        it != next_urls_num_found.end();
    467        ++it) {
    468     // Only consider a candidate next page for prerendering if it was viewed
    469     // at least twice, and at least 10% of the time.
    470     if (num_occurrences_of_current_visit > 0 &&
    471         it->second > 1 &&
    472         it->second * 10 >= num_occurrences_of_current_visit) {
    473       RecordEvent(EVENT_ADD_VISIT_IDENTIFIED_PRERENDER_CANDIDATE);
    474       double priority = static_cast<double>(it->second) /
    475           static_cast<double>(num_occurrences_of_current_visit);
    476       lookup_info->MaybeAddCandidateURL(it->first, priority);
    477     }
    478   }
    479 
    480   if (lookup_info->candidate_urls_.size() == 0) {
    481     RecordEvent(EVENT_NO_PRERENDER_CANDIDATES);
    482     return;
    483   }
    484 
    485   RecordEvent(EVENT_START_URL_LOOKUP);
    486   HistoryService* history = GetHistoryIfExists();
    487   if (history) {
    488     RecordEvent(EVENT_GOT_HISTORY_ISSUING_LOOKUP);
    489     LocalPredictorURLLookupInfo* lookup_info_ptr = lookup_info.get();
    490     history->ScheduleDBTask(
    491         new GetURLForURLIDTask(
    492             lookup_info_ptr,
    493             base::Bind(&PrerenderLocalPredictor::OnLookupURL,
    494                        base::Unretained(this),
    495                        base::Passed(&lookup_info))),
    496         &history_db_consumer_);
    497   }
    498 }
    499 
    500 void PrerenderLocalPredictor::OnLookupURL(
    501     scoped_ptr<LocalPredictorURLLookupInfo> info) {
    502   RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT);
    503 
    504   DCHECK_GE(static_cast<int>(info->candidate_urls_.size()), 1);
    505 
    506   if (!info->source_url_.url_lookup_success) {
    507     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_FAILED);
    508     return;
    509   }
    510 
    511   LogCandidateURLStats(info->candidate_urls_[0].url);
    512 
    513   WebContents* source_web_contents = NULL;
    514   bool multiple_source_web_contents_candidates = false;
    515 
    516 #if !defined(OS_ANDROID)
    517   // We need to figure out what tab launched the prerender. We do this by
    518   // comparing URLs. This may not always work: the URL may occur in two
    519   // tabs, and we pick the wrong one, or the tab we should have picked
    520   // may have navigated elsewhere. Hopefully, this doesn't happen too often,
    521   // so we ignore these cases for now.
    522   // TODO(tburkard): Reconsider this, potentially measure it, and fix this
    523   // in the future.
    524   for (TabContentsIterator it; !it.done(); it.Next()) {
    525     if (it->GetURL() == info->source_url_.url) {
    526       if (!source_web_contents)
    527         source_web_contents = *it;
    528       else
    529         multiple_source_web_contents_candidates = true;
    530     }
    531   }
    532 #endif
    533 
    534   if (!source_web_contents) {
    535     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_NO_SOURCE_WEBCONTENTS_FOUND);
    536     return;
    537   }
    538 
    539   if (multiple_source_web_contents_candidates)
    540     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_MULTIPLE_SOURCE_WEBCONTENTS_FOUND);
    541 
    542 
    543   scoped_refptr<SessionStorageNamespace> session_storage_namespace =
    544       source_web_contents->GetController().GetDefaultSessionStorageNamespace();
    545 
    546   gfx::Rect container_bounds;
    547   source_web_contents->GetView()->GetContainerBounds(&container_bounds);
    548   scoped_ptr<gfx::Size> size(new gfx::Size(container_bounds.size()));
    549 
    550   scoped_refptr<LoggedInPredictorTable> logged_in_table =
    551       prerender_manager_->logged_in_predictor_table();
    552 
    553   if (!logged_in_table.get()) {
    554     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_NO_LOGGED_IN_TABLE_FOUND);
    555     return;
    556   }
    557 
    558   RecordEvent(EVENT_PRERENDER_URL_LOOKUP_ISSUING_LOGGED_IN_LOOKUP);
    559 
    560   LocalPredictorURLLookupInfo* info_ptr = info.get();
    561   BrowserThread::PostTaskAndReply(
    562       BrowserThread::DB, FROM_HERE,
    563       base::Bind(&LookupLoggedInStatesOnDBThread,
    564                  logged_in_table,
    565                  info_ptr),
    566       base::Bind(&PrerenderLocalPredictor::ContinuePrerenderCheck,
    567                  weak_factory_.GetWeakPtr(),
    568                  session_storage_namespace,
    569                  base::Passed(&size),
    570                  base::Passed(&info)));
    571 }
    572 
    573 void PrerenderLocalPredictor::LogCandidateURLStats(const GURL& url) const {
    574   if (url_whitelist_.count(GetInt64URLHashForURL(url)) > 0) {
    575     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_ON_WHITELIST);
    576     if (IsRootPageURL(url))
    577       RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_ON_WHITELIST_ROOT_PAGE);
    578   }
    579   if (IsRootPageURL(url))
    580     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_ROOT_PAGE);
    581   if (IsExtendedRootURL(url))
    582     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_EXTENDED_ROOT_PAGE);
    583   if (IsRootPageURL(url) && url.SchemeIs("http"))
    584     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_ROOT_PAGE_HTTP);
    585   if (url.SchemeIs("http"))
    586     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_IS_HTTP);
    587   if (url.has_query())
    588     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_HAS_QUERY_STRING);
    589   if (IsLogOutURL(url))
    590     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_CONTAINS_LOGOUT);
    591   if (IsLogInURL(url))
    592     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_CONTAINS_LOGIN);
    593 }
    594 
    595 void PrerenderLocalPredictor::OnGetInitialVisitHistory(
    596     scoped_ptr<vector<history::BriefVisitInfo> > visit_history) {
    597   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    598   DCHECK(!visit_history_.get());
    599   RecordEvent(EVENT_INIT_SUCCEEDED);
    600   // Since the visit history has descending timestamps, we must reverse it.
    601   visit_history_.reset(new vector<history::BriefVisitInfo>(
    602       visit_history->rbegin(), visit_history->rend()));
    603 }
    604 
    605 HistoryService* PrerenderLocalPredictor::GetHistoryIfExists() const {
    606   Profile* profile = prerender_manager_->profile();
    607   if (!profile)
    608     return NULL;
    609   return HistoryServiceFactory::GetForProfileWithoutCreating(profile);
    610 }
    611 
    612 void PrerenderLocalPredictor::Init() {
    613   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    614   RecordEvent(EVENT_INIT_STARTED);
    615   HistoryService* history = GetHistoryIfExists();
    616   if (history) {
    617     CHECK(!is_visit_database_observer_);
    618     history->ScheduleDBTask(
    619         new GetVisitHistoryTask(this, kMaxVisitHistory),
    620         &history_db_consumer_);
    621     history->AddVisitDatabaseObserver(this);
    622     is_visit_database_observer_ = true;
    623   } else {
    624     RecordEvent(EVENT_INIT_FAILED_NO_HISTORY);
    625   }
    626 }
    627 
    628 void PrerenderLocalPredictor::OnPLTEventForURL(const GURL& url,
    629                                                base::TimeDelta page_load_time) {
    630   scoped_ptr<PrerenderProperties> prerender;
    631   if (DoesPrerenderMatchPLTRecord(last_swapped_in_prerender_.get(),
    632                                   url, page_load_time)) {
    633     prerender.reset(last_swapped_in_prerender_.release());
    634   }
    635   if (DoesPrerenderMatchPLTRecord(current_prerender_.get(),
    636                                   url, page_load_time)) {
    637     prerender.reset(current_prerender_.release());
    638   }
    639   if (!prerender.get())
    640     return;
    641   if (IsPrerenderStillValid(prerender.get())) {
    642     UMA_HISTOGRAM_CUSTOM_TIMES("Prerender.SimulatedLocalBrowsingBaselinePLT",
    643                                page_load_time,
    644                                base::TimeDelta::FromMilliseconds(10),
    645                                base::TimeDelta::FromSeconds(60),
    646                                100);
    647 
    648     base::TimeDelta prerender_age = GetCurrentTime() - prerender->start_time;
    649     if (prerender_age > page_load_time) {
    650       base::TimeDelta new_plt;
    651       if (prerender_age <  2 * page_load_time)
    652         new_plt = 2 * page_load_time - prerender_age;
    653       UMA_HISTOGRAM_CUSTOM_TIMES("Prerender.SimulatedLocalBrowsingPLT",
    654                                  new_plt,
    655                                  base::TimeDelta::FromMilliseconds(10),
    656                                  base::TimeDelta::FromSeconds(60),
    657                                  100);
    658     }
    659   }
    660 }
    661 
    662 bool PrerenderLocalPredictor::IsPrerenderStillValid(
    663     PrerenderLocalPredictor::PrerenderProperties* prerender) const {
    664   return (prerender &&
    665           (prerender->start_time +
    666            base::TimeDelta::FromMilliseconds(GetMaxLocalPredictionTimeMs()))
    667           > GetCurrentTime());
    668 }
    669 
    670 void PrerenderLocalPredictor::RecordEvent(
    671     PrerenderLocalPredictor::Event event) const {
    672   UMA_HISTOGRAM_ENUMERATION("Prerender.LocalPredictorEvent",
    673       event, PrerenderLocalPredictor::EVENT_MAX_VALUE);
    674 }
    675 
    676 bool PrerenderLocalPredictor::DoesPrerenderMatchPLTRecord(
    677     PrerenderProperties* prerender,
    678     const GURL& url,
    679     base::TimeDelta plt) const {
    680   if (prerender && prerender->start_time < GetCurrentTime() - plt) {
    681     if (prerender->url.is_empty())
    682       RecordEvent(EVENT_ERROR_NO_PRERENDER_URL_FOR_PLT);
    683     return (prerender->url == url);
    684   } else {
    685     return false;
    686   }
    687 }
    688 
    689 PrerenderLocalPredictor::PrerenderProperties*
    690 PrerenderLocalPredictor::GetIssuedPrerenderSlotForPriority(double priority) {
    691   int num_prerenders = GetLocalPredictorMaxConcurrentPrerenders();
    692   while (static_cast<int>(issued_prerenders_.size()) < num_prerenders)
    693     issued_prerenders_.push_back(new PrerenderProperties());
    694   PrerenderProperties* lowest_priority_prerender = NULL;
    695   for (int i = 0; i < static_cast<int>(issued_prerenders_.size()); i++) {
    696     PrerenderProperties* p = issued_prerenders_[i];
    697     DCHECK(p != NULL);
    698     if (!p->prerender_handle || !p->prerender_handle->IsPrerendering())
    699       return p;
    700     double decayed_priority = p->GetCurrentDecayedPriority();
    701     if (decayed_priority > priority)
    702       continue;
    703     if (lowest_priority_prerender == NULL ||
    704         lowest_priority_prerender->GetCurrentDecayedPriority() >
    705         decayed_priority) {
    706       lowest_priority_prerender = p;
    707     }
    708   }
    709   return lowest_priority_prerender;
    710 }
    711 
    712 void PrerenderLocalPredictor::ContinuePrerenderCheck(
    713     scoped_refptr<SessionStorageNamespace> session_storage_namespace,
    714     scoped_ptr<gfx::Size> size,
    715     scoped_ptr<LocalPredictorURLLookupInfo> info) {
    716   RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_STARTED);
    717   scoped_ptr<LocalPredictorURLInfo> url_info;
    718   scoped_refptr<SafeBrowsingDatabaseManager> sb_db_manager =
    719       g_browser_process->safe_browsing_service()->database_manager();
    720   PrerenderProperties* prerender_properties = NULL;
    721 
    722   for (int i = 0; i < static_cast<int>(info->candidate_urls_.size()); i++) {
    723     RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_EXAMINE_NEXT_URL);
    724     url_info.reset(new LocalPredictorURLInfo(info->candidate_urls_[i]));
    725 
    726     // We need to check whether we can issue a prerender for this URL.
    727     // We test a set of conditions. Each condition can either rule out
    728     // a prerender (in which case we reset url_info, so that it will not
    729     // be prerendered, and we continue, which means try the next candidate
    730     // URL), or it can be sufficient to issue the prerender without any
    731     // further checks (in which case we just break).
    732     // The order of the checks is critical, because it prescribes the logic
    733     // we use here to decide what to prerender.
    734     if (!url_info->url_lookup_success) {
    735       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_NO_URL);
    736       url_info.reset(NULL);
    737       continue;
    738     }
    739     prerender_properties =
    740         GetIssuedPrerenderSlotForPriority(url_info->priority);
    741     if (!prerender_properties) {
    742       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_PRIORITY_TOO_LOW);
    743       url_info.reset(NULL);
    744       continue;
    745     }
    746     if (!SkipLocalPredictorFragment() &&
    747         URLsIdenticalIgnoringFragments(info->source_url_.url,
    748                                        url_info->url)) {
    749       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_URLS_IDENTICAL_BUT_FRAGMENT);
    750       url_info.reset(NULL);
    751       continue;
    752     }
    753     if (!SkipLocalPredictorHTTPS() && url_info->url.SchemeIs("https")) {
    754       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_HTTPS);
    755       url_info.reset(NULL);
    756       continue;
    757     }
    758     if (IsRootPageURL(url_info->url)) {
    759       // For root pages, we assume that they are reasonably safe, and we
    760       // will just prerender them without any additional checks.
    761       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_ROOT_PAGE);
    762       break;
    763     }
    764     if (IsLogOutURL(url_info->url)) {
    765       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_LOGOUT_URL);
    766       url_info.reset(NULL);
    767       continue;
    768     }
    769     if (IsLogInURL(url_info->url)) {
    770       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_LOGIN_URL);
    771       url_info.reset(NULL);
    772       continue;
    773     }
    774     if (!SkipLocalPredictorWhitelist() &&
    775         sb_db_manager->CheckSideEffectFreeWhitelistUrl(url_info->url)) {
    776       // If a page is on the side-effect free whitelist, we will just prerender
    777       // it without any additional checks.
    778       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_ON_SIDE_EFFECT_FREE_WHITELIST);
    779       break;
    780     }
    781     if (!SkipLocalPredictorLoggedIn() &&
    782         !url_info->logged_in && url_info->logged_in_lookup_ok) {
    783       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_NOT_LOGGED_IN);
    784       break;
    785     }
    786     if (!SkipLocalPredictorDefaultNoPrerender()) {
    787       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_FALLTHROUGH_NOT_PRERENDERING);
    788       url_info.reset(NULL);
    789     } else {
    790       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_FALLTHROUGH_PRERENDERING);
    791     }
    792   }
    793   if (!url_info.get())
    794     return;
    795   RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_ISSUING_PRERENDER);
    796   DCHECK(prerender_properties != NULL);
    797   if (IsLocalPredictorPrerenderLaunchEnabled()) {
    798     IssuePrerender(session_storage_namespace, size.Pass(),
    799                    url_info.Pass(), prerender_properties);
    800   }
    801 }
    802 
    803 void PrerenderLocalPredictor::IssuePrerender(
    804     scoped_refptr<SessionStorageNamespace> session_storage_namespace,
    805     scoped_ptr<gfx::Size> size,
    806     scoped_ptr<LocalPredictorURLInfo> info,
    807     PrerenderProperties* prerender_properties) {
    808   URLID url_id = info->id;
    809   const GURL& url = info->url;
    810   double priority = info->priority;
    811   base::Time current_time = GetCurrentTime();
    812   RecordEvent(EVENT_ISSUING_PRERENDER);
    813 
    814   // Issue the prerender and obtain a new handle.
    815   scoped_ptr<prerender::PrerenderHandle> new_prerender_handle(
    816       prerender_manager_->AddPrerenderFromLocalPredictor(
    817           url, session_storage_namespace.get(), *size));
    818 
    819   // Check if this is a duplicate of an existing prerender. If yes, clean up
    820   // the new handle.
    821   for (int i = 0; i < static_cast<int>(issued_prerenders_.size()); i++) {
    822     PrerenderProperties* p = issued_prerenders_[i];
    823     DCHECK(p != NULL);
    824     if (new_prerender_handle &&
    825         new_prerender_handle->RepresentingSamePrerenderAs(
    826             p->prerender_handle.get())) {
    827       new_prerender_handle->OnCancel();
    828       new_prerender_handle.reset(NULL);
    829       RecordEvent(EVENT_ISSUE_PRERENDER_ALREADY_PRERENDERING);
    830       break;
    831     }
    832   }
    833 
    834   if (new_prerender_handle.get()) {
    835     RecordEvent(EVENT_ISSUE_PRERENDER_NEW_PRERENDER);
    836     // The new prerender does not match any existing prerenders. Update
    837     // prerender_properties so that it reflects the new entry.
    838     prerender_properties->url_id = url_id;
    839     prerender_properties->url = url;
    840     prerender_properties->priority = priority;
    841     prerender_properties->start_time = current_time;
    842     prerender_properties->actual_start_time = current_time;
    843     prerender_properties->would_have_matched = false;
    844     prerender_properties->prerender_handle.swap(new_prerender_handle);
    845     // new_prerender_handle now represents the old previou prerender that we
    846     // are replacing. So we need to cancel it.
    847     if (new_prerender_handle) {
    848       new_prerender_handle->OnCancel();
    849       RecordEvent(EVENT_ISSUE_PRERENDER_CANCELLED_OLD_PRERENDER);
    850     }
    851   }
    852 
    853   RecordEvent(EVENT_ADD_VISIT_PRERENDERING);
    854   if (current_prerender_.get() && current_prerender_->url_id == url_id) {
    855     RecordEvent(EVENT_ADD_VISIT_PRERENDERING_EXTENDED);
    856     if (priority > current_prerender_->priority)
    857       current_prerender_->priority = priority;
    858     // If the prerender already existed, we want to extend it.  However,
    859     // we do not want to set its start_time to the current time to
    860     // disadvantage PLT computations when the prerender is swapped in.
    861     // So we set the new start time to current_time - 10s (since the vast
    862     // majority of PLTs are < 10s), provided that is not before the actual
    863     // time the prerender was started (so as to not artificially advantage
    864     // the PLT computation).
    865     base::Time simulated_new_start_time =
    866         current_time - base::TimeDelta::FromSeconds(10);
    867     if (simulated_new_start_time > current_prerender_->start_time)
    868       current_prerender_->start_time = simulated_new_start_time;
    869   } else {
    870     current_prerender_.reset(
    871         new PrerenderProperties(url_id, url, priority, current_time));
    872   }
    873   current_prerender_->actual_start_time = current_time;
    874 }
    875 
    876 void PrerenderLocalPredictor::OnTabHelperURLSeen(
    877     const GURL& url, WebContents* web_contents) {
    878   RecordEvent(EVENT_TAB_HELPER_URL_SEEN);
    879 
    880   // If the namespace matches and the URL matches, we might be able to swap
    881   // in. However, the actual code initating the swapin is in the renderer
    882   // and is checking for other criteria (such as POSTs). There may
    883   // also be conditions when a swapin should happen but does not. By recording
    884   // the two previous events, we can keep an eye on the magnitude of the
    885   // discrepancy.
    886 
    887   PrerenderProperties* best_matched_prerender = NULL;
    888   bool session_storage_namespace_matches = false;
    889   for (int i = 0; i < static_cast<int>(issued_prerenders_.size()); i++) {
    890     PrerenderProperties* p = issued_prerenders_[i];
    891     DCHECK(p != NULL);
    892     if (!p->prerender_handle.get() ||
    893         !p->prerender_handle->Matches(url, NULL) ||
    894         p->would_have_matched) {
    895       continue;
    896     }
    897     if (!best_matched_prerender || !session_storage_namespace_matches) {
    898       best_matched_prerender = p;
    899       session_storage_namespace_matches =
    900           p->prerender_handle->Matches(
    901               url,
    902               web_contents->GetController().
    903               GetDefaultSessionStorageNamespace());
    904     }
    905   }
    906   if (best_matched_prerender) {
    907     RecordEvent(EVENT_TAB_HELPER_URL_SEEN_MATCH);
    908     best_matched_prerender->would_have_matched = true;
    909     if (session_storage_namespace_matches)
    910       RecordEvent(EVENT_TAB_HELPER_URL_SEEN_NAMESPACE_MATCH);
    911   }
    912 }
    913 
    914 }  // namespace prerender
    915