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/json/json_reader.h"
     16 #include "base/json/json_writer.h"
     17 #include "base/metrics/field_trial.h"
     18 #include "base/metrics/histogram.h"
     19 #include "base/stl_util.h"
     20 #include "base/timer/timer.h"
     21 #include "chrome/browser/browser_process.h"
     22 #include "chrome/browser/history/history_database.h"
     23 #include "chrome/browser/history/history_db_task.h"
     24 #include "chrome/browser/history/history_service.h"
     25 #include "chrome/browser/history/history_service_factory.h"
     26 #include "chrome/browser/prerender/prerender_field_trial.h"
     27 #include "chrome/browser/prerender/prerender_handle.h"
     28 #include "chrome/browser/prerender/prerender_histograms.h"
     29 #include "chrome/browser/prerender/prerender_manager.h"
     30 #include "chrome/browser/prerender/prerender_util.h"
     31 #include "chrome/browser/profiles/profile.h"
     32 #include "chrome/browser/safe_browsing/database_manager.h"
     33 #include "chrome/browser/safe_browsing/safe_browsing_service.h"
     34 #include "chrome/browser/ui/tab_contents/tab_contents_iterator.h"
     35 #include "content/public/browser/browser_thread.h"
     36 #include "content/public/browser/navigation_controller.h"
     37 #include "content/public/browser/navigation_entry.h"
     38 #include "content/public/browser/web_contents.h"
     39 #include "content/public/browser/web_contents_view.h"
     40 #include "content/public/common/page_transition_types.h"
     41 #include "crypto/secure_hash.h"
     42 #include "grit/browser_resources.h"
     43 #include "net/base/escape.h"
     44 #include "net/base/load_flags.h"
     45 #include "net/url_request/url_fetcher.h"
     46 #include "ui/base/resource/resource_bundle.h"
     47 #include "url/url_canon.h"
     48 
     49 using base::DictionaryValue;
     50 using base::ListValue;
     51 using base::Value;
     52 using content::BrowserThread;
     53 using content::PageTransition;
     54 using content::SessionStorageNamespace;
     55 using content::WebContents;
     56 using history::URLID;
     57 using net::URLFetcher;
     58 using predictors::LoggedInPredictorTable;
     59 using std::string;
     60 using std::vector;
     61 
     62 namespace prerender {
     63 
     64 namespace {
     65 
     66 static const size_t kURLHashSize = 5;
     67 static const int kNumPrerenderCandidates = 5;
     68 
     69 }  // namespace
     70 
     71 // When considering a candidate URL to be prerendered, we need to collect the
     72 // data in this struct to make the determination whether we should issue the
     73 // prerender or not.
     74 struct PrerenderLocalPredictor::LocalPredictorURLInfo {
     75   URLID id;
     76   GURL url;
     77   bool url_lookup_success;
     78   bool logged_in;
     79   bool logged_in_lookup_ok;
     80   bool local_history_based;
     81   bool service_whitelist;
     82   bool service_whitelist_lookup_ok;
     83   bool service_whitelist_reported;
     84   double priority;
     85 };
     86 
     87 // A struct consisting of everything needed for launching a potential prerender
     88 // on a navigation: The navigation URL (source) triggering potential prerenders,
     89 // and a set of candidate URLs.
     90 struct PrerenderLocalPredictor::CandidatePrerenderInfo {
     91   LocalPredictorURLInfo source_url_;
     92   vector<LocalPredictorURLInfo> candidate_urls_;
     93   scoped_refptr<SessionStorageNamespace> session_storage_namespace_;
     94   scoped_ptr<gfx::Size> size_;
     95   base::Time start_time_;  // used for various time measurements
     96   explicit CandidatePrerenderInfo(URLID source_id) {
     97     source_url_.id = source_id;
     98   }
     99   void MaybeAddCandidateURLFromLocalData(URLID id, double priority) {
    100     LocalPredictorURLInfo info;
    101     info.id = id;
    102     info.local_history_based = true;
    103     info.service_whitelist = false;
    104     info.service_whitelist_lookup_ok = false;
    105     info.service_whitelist_reported = false;
    106     info.priority = priority;
    107     MaybeAddCandidateURLInternal(info);
    108   }
    109   void MaybeAddCandidateURLFromService(GURL url, double priority,
    110                                        bool whitelist,
    111                                        bool whitelist_lookup_ok) {
    112     LocalPredictorURLInfo info;
    113     info.id = kint64max;
    114     info.url = url;
    115     info.url_lookup_success = true;
    116     info.local_history_based = false;
    117     info.service_whitelist = whitelist;
    118     info.service_whitelist_lookup_ok = whitelist_lookup_ok;
    119     info.service_whitelist_reported = true;
    120     info.priority = priority;
    121     MaybeAddCandidateURLInternal(info);
    122   }
    123   void MaybeAddCandidateURLInternal(const LocalPredictorURLInfo& info) {
    124     // TODO(tburkard): clean up this code, potentially using a list or a heap
    125     int max_candidates = kNumPrerenderCandidates;
    126     // We first insert local candidates, then service candidates.
    127     // Since we want to keep kNumPrerenderCandidates for both local & service
    128     // candidates, we need to double the maximum number of candidates once
    129     // we start seeing service candidates.
    130     if (!info.local_history_based)
    131       max_candidates *= 2;
    132     int insert_pos = candidate_urls_.size();
    133     if (insert_pos < max_candidates)
    134       candidate_urls_.push_back(info);
    135     while (insert_pos > 0 &&
    136            candidate_urls_[insert_pos - 1].priority < info.priority) {
    137       if (insert_pos < max_candidates)
    138         candidate_urls_[insert_pos] = candidate_urls_[insert_pos - 1];
    139       insert_pos--;
    140     }
    141     if (insert_pos < max_candidates)
    142       candidate_urls_[insert_pos] = info;
    143   }
    144 };
    145 
    146 namespace {
    147 
    148 #define TIMING_HISTOGRAM(name, value)                               \
    149   UMA_HISTOGRAM_CUSTOM_TIMES(name, value,                           \
    150                              base::TimeDelta::FromMilliseconds(10), \
    151                              base::TimeDelta::FromSeconds(10),      \
    152                              50);
    153 
    154 // Task to lookup the URL for a given URLID.
    155 class GetURLForURLIDTask : public history::HistoryDBTask {
    156  public:
    157   GetURLForURLIDTask(
    158       PrerenderLocalPredictor::CandidatePrerenderInfo* request,
    159       const base::Closure& callback)
    160       : request_(request),
    161         callback_(callback),
    162         start_time_(base::Time::Now()) {
    163   }
    164 
    165   virtual bool RunOnDBThread(history::HistoryBackend* backend,
    166                              history::HistoryDatabase* db) OVERRIDE {
    167     DoURLLookup(db, &request_->source_url_);
    168     for (int i = 0; i < static_cast<int>(request_->candidate_urls_.size()); i++)
    169       DoURLLookup(db, &request_->candidate_urls_[i]);
    170     return true;
    171   }
    172 
    173   virtual void DoneRunOnMainThread() OVERRIDE {
    174     callback_.Run();
    175     TIMING_HISTOGRAM("Prerender.LocalPredictorURLLookupTime",
    176                      base::Time::Now() - start_time_);
    177   }
    178 
    179  private:
    180   virtual ~GetURLForURLIDTask() {}
    181 
    182   void DoURLLookup(history::HistoryDatabase* db,
    183                    PrerenderLocalPredictor::LocalPredictorURLInfo* request) {
    184     history::URLRow url_row;
    185     request->url_lookup_success = db->GetURLRow(request->id, &url_row);
    186     if (request->url_lookup_success)
    187       request->url = url_row.url();
    188   }
    189 
    190   PrerenderLocalPredictor::CandidatePrerenderInfo* request_;
    191   base::Closure callback_;
    192   base::Time start_time_;
    193   DISALLOW_COPY_AND_ASSIGN(GetURLForURLIDTask);
    194 };
    195 
    196 // Task to load history from the visit database on startup.
    197 class GetVisitHistoryTask : public history::HistoryDBTask {
    198  public:
    199   GetVisitHistoryTask(PrerenderLocalPredictor* local_predictor,
    200                       int max_visits)
    201       : local_predictor_(local_predictor),
    202         max_visits_(max_visits),
    203         visit_history_(new vector<history::BriefVisitInfo>) {
    204   }
    205 
    206   virtual bool RunOnDBThread(history::HistoryBackend* backend,
    207                              history::HistoryDatabase* db) OVERRIDE {
    208     db->GetBriefVisitInfoOfMostRecentVisits(max_visits_, visit_history_.get());
    209     return true;
    210   }
    211 
    212   virtual void DoneRunOnMainThread() OVERRIDE {
    213     local_predictor_->OnGetInitialVisitHistory(visit_history_.Pass());
    214   }
    215 
    216  private:
    217   virtual ~GetVisitHistoryTask() {}
    218 
    219   PrerenderLocalPredictor* local_predictor_;
    220   int max_visits_;
    221   scoped_ptr<vector<history::BriefVisitInfo> > visit_history_;
    222   DISALLOW_COPY_AND_ASSIGN(GetVisitHistoryTask);
    223 };
    224 
    225 // Maximum visit history to retrieve from the visit database.
    226 const int kMaxVisitHistory = 100 * 1000;
    227 
    228 // Visit history size at which to trigger pruning, and number of items to prune.
    229 const int kVisitHistoryPruneThreshold = 120 * 1000;
    230 const int kVisitHistoryPruneAmount = 20 * 1000;
    231 
    232 const int kMinLocalPredictionTimeMs = 500;
    233 
    234 int GetMaxLocalPredictionTimeMs() {
    235   return GetLocalPredictorTTLSeconds() * 1000;
    236 }
    237 
    238 bool IsBackForward(PageTransition transition) {
    239   return (transition & content::PAGE_TRANSITION_FORWARD_BACK) != 0;
    240 }
    241 
    242 bool IsHomePage(PageTransition transition) {
    243   return (transition & content::PAGE_TRANSITION_HOME_PAGE) != 0;
    244 }
    245 
    246 bool IsIntermediateRedirect(PageTransition transition) {
    247   return (transition & content::PAGE_TRANSITION_CHAIN_END) == 0;
    248 }
    249 
    250 bool IsFormSubmit(PageTransition transition) {
    251   return PageTransitionCoreTypeIs(transition,
    252                                   content::PAGE_TRANSITION_FORM_SUBMIT);
    253 }
    254 
    255 bool ShouldExcludeTransitionForPrediction(PageTransition transition) {
    256   return IsBackForward(transition) || IsHomePage(transition) ||
    257       IsIntermediateRedirect(transition);
    258 }
    259 
    260 base::Time GetCurrentTime() {
    261   return base::Time::Now();
    262 }
    263 
    264 bool StringContainsIgnoringCase(string haystack, string needle) {
    265   std::transform(haystack.begin(), haystack.end(), haystack.begin(), ::tolower);
    266   std::transform(needle.begin(), needle.end(), needle.begin(), ::tolower);
    267   return haystack.find(needle) != string::npos;
    268 }
    269 
    270 bool IsExtendedRootURL(const GURL& url) {
    271   const string& path = url.path();
    272   return path == "/index.html" || path == "/home.html" ||
    273       path == "/main.html" ||
    274       path == "/index.htm" || path == "/home.htm" || path == "/main.htm" ||
    275       path == "/index.php" || path == "/home.php" || path == "/main.php" ||
    276       path == "/index.asp" || path == "/home.asp" || path == "/main.asp" ||
    277       path == "/index.py" || path == "/home.py" || path == "/main.py" ||
    278       path == "/index.pl" || path == "/home.pl" || path == "/main.pl";
    279 }
    280 
    281 bool IsRootPageURL(const GURL& url) {
    282   return (url.path() == "/" || url.path() == "" || IsExtendedRootURL(url)) &&
    283       (!url.has_query()) && (!url.has_ref());
    284 }
    285 
    286 bool IsLogInURL(const GURL& url) {
    287   return StringContainsIgnoringCase(url.spec().c_str(), "login") ||
    288       StringContainsIgnoringCase(url.spec().c_str(), "signin");
    289 }
    290 
    291 bool IsLogOutURL(const GURL& url) {
    292   return StringContainsIgnoringCase(url.spec().c_str(), "logout") ||
    293       StringContainsIgnoringCase(url.spec().c_str(), "signout");
    294 }
    295 
    296 int64 URLHashToInt64(const unsigned char* data) {
    297   COMPILE_ASSERT(kURLHashSize < sizeof(int64), url_hash_must_fit_in_int64);
    298   int64 value = 0;
    299   memcpy(&value, data, kURLHashSize);
    300   return value;
    301 }
    302 
    303 int64 GetInt64URLHashForURL(const GURL& url) {
    304   COMPILE_ASSERT(kURLHashSize < sizeof(int64), url_hash_must_fit_in_int64);
    305   scoped_ptr<crypto::SecureHash> hash(
    306       crypto::SecureHash::Create(crypto::SecureHash::SHA256));
    307   int64 hash_value = 0;
    308   const char* url_string = url.spec().c_str();
    309   hash->Update(url_string, strlen(url_string));
    310   hash->Finish(&hash_value, kURLHashSize);
    311   return hash_value;
    312 }
    313 
    314 bool URLsIdenticalIgnoringFragments(const GURL& url1, const GURL& url2) {
    315   url_canon::Replacements<char> replacement;
    316   replacement.ClearRef();
    317   GURL u1 = url1.ReplaceComponents(replacement);
    318   GURL u2 = url2.ReplaceComponents(replacement);
    319   return (u1 == u2);
    320 }
    321 
    322 void LookupLoggedInStatesOnDBThread(
    323     scoped_refptr<LoggedInPredictorTable> logged_in_predictor_table,
    324     PrerenderLocalPredictor::CandidatePrerenderInfo* request) {
    325   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::DB));
    326   for (int i = 0; i < static_cast<int>(request->candidate_urls_.size()); i++) {
    327     PrerenderLocalPredictor::LocalPredictorURLInfo* info =
    328         &request->candidate_urls_[i];
    329     if (info->url_lookup_success) {
    330       logged_in_predictor_table->HasUserLoggedIn(
    331           info->url, &info->logged_in, &info->logged_in_lookup_ok);
    332     } else {
    333       info->logged_in_lookup_ok = false;
    334     }
    335   }
    336 }
    337 
    338 }  // namespace
    339 
    340 struct PrerenderLocalPredictor::PrerenderProperties {
    341   PrerenderProperties(URLID url_id, const GURL& url, double priority,
    342                 base::Time start_time)
    343       : url_id(url_id),
    344         url(url),
    345         priority(priority),
    346         start_time(start_time),
    347         would_have_matched(false) {
    348   }
    349 
    350   // Default constructor for dummy element
    351   PrerenderProperties()
    352       : priority(0.0), would_have_matched(false) {
    353   }
    354 
    355   double GetCurrentDecayedPriority() {
    356     // If we are no longer prerendering, the priority is 0.
    357     if (!prerender_handle || !prerender_handle->IsPrerendering())
    358       return 0.0;
    359     int half_life_time_seconds =
    360         GetLocalPredictorPrerenderPriorityHalfLifeTimeSeconds();
    361     if (half_life_time_seconds < 1)
    362       return priority;
    363     double multiple_elapsed =
    364         (GetCurrentTime() - actual_start_time).InMillisecondsF() /
    365         base::TimeDelta::FromSeconds(half_life_time_seconds).InMillisecondsF();
    366     // Decay factor: 2 ^ (-multiple_elapsed)
    367     double decay_factor = exp(- multiple_elapsed * log(2.0));
    368     return priority * decay_factor;
    369   }
    370 
    371   URLID url_id;
    372   GURL url;
    373   double priority;
    374   // For expiration purposes, this is a synthetic start time consisting either
    375   // of the actual start time, or of the last time the page was re-requested
    376   // for prerendering - 10 seconds (unless the original request came after
    377   // that).  This is to emulate the effect of re-prerendering a page that is
    378   // about to expire, because it was re-requested for prerendering a second
    379   // time after the actual prerender being kept around.
    380   base::Time start_time;
    381   // The actual time this page was last requested for prerendering.
    382   base::Time actual_start_time;
    383   scoped_ptr<PrerenderHandle> prerender_handle;
    384   // Indicates whether this prerender would have matched a URL navigated to,
    385   // but was not swapped in for some reason.
    386   bool would_have_matched;
    387 };
    388 
    389 PrerenderLocalPredictor::PrerenderLocalPredictor(
    390     PrerenderManager* prerender_manager)
    391     : prerender_manager_(prerender_manager),
    392       is_visit_database_observer_(false),
    393       weak_factory_(this) {
    394   RecordEvent(EVENT_CONSTRUCTED);
    395   if (base::MessageLoop::current()) {
    396     timer_.Start(FROM_HERE,
    397                  base::TimeDelta::FromMilliseconds(kInitDelayMs),
    398                  this,
    399                  &PrerenderLocalPredictor::Init);
    400     RecordEvent(EVENT_INIT_SCHEDULED);
    401   }
    402 
    403   static const size_t kChecksumHashSize = 32;
    404   base::RefCountedStaticMemory* url_whitelist_data =
    405       ResourceBundle::GetSharedInstance().LoadDataResourceBytes(
    406           IDR_PRERENDER_URL_WHITELIST);
    407   size_t size = url_whitelist_data->size();
    408   const unsigned char* front = url_whitelist_data->front();
    409   if (size < kChecksumHashSize ||
    410       (size - kChecksumHashSize) % kURLHashSize != 0) {
    411     RecordEvent(EVENT_URL_WHITELIST_ERROR);
    412     return;
    413   }
    414   scoped_ptr<crypto::SecureHash> hash(
    415       crypto::SecureHash::Create(crypto::SecureHash::SHA256));
    416   hash->Update(front + kChecksumHashSize, size - kChecksumHashSize);
    417   char hash_value[kChecksumHashSize];
    418   hash->Finish(hash_value, kChecksumHashSize);
    419   if (memcmp(hash_value, front, kChecksumHashSize)) {
    420     RecordEvent(EVENT_URL_WHITELIST_ERROR);
    421     return;
    422   }
    423   for (const unsigned char* p = front + kChecksumHashSize;
    424        p < front + size;
    425        p += kURLHashSize) {
    426     url_whitelist_.insert(URLHashToInt64(p));
    427   }
    428   RecordEvent(EVENT_URL_WHITELIST_OK);
    429 }
    430 
    431 PrerenderLocalPredictor::~PrerenderLocalPredictor() {
    432   Shutdown();
    433   for (int i = 0; i < static_cast<int>(issued_prerenders_.size()); i++) {
    434     PrerenderProperties* p = issued_prerenders_[i];
    435     DCHECK(p != NULL);
    436     if (p->prerender_handle)
    437       p->prerender_handle->OnCancel();
    438   }
    439   STLDeleteContainerPairPointers(
    440       outstanding_prerender_service_requests_.begin(),
    441       outstanding_prerender_service_requests_.end());
    442 }
    443 
    444 void PrerenderLocalPredictor::Shutdown() {
    445   timer_.Stop();
    446   if (is_visit_database_observer_) {
    447     HistoryService* history = GetHistoryIfExists();
    448     CHECK(history);
    449     history->RemoveVisitDatabaseObserver(this);
    450     is_visit_database_observer_ = false;
    451   }
    452 }
    453 
    454 void PrerenderLocalPredictor::OnAddVisit(const history::BriefVisitInfo& info) {
    455   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    456   RecordEvent(EVENT_ADD_VISIT);
    457   if (!visit_history_.get())
    458     return;
    459   visit_history_->push_back(info);
    460   if (static_cast<int>(visit_history_->size()) > kVisitHistoryPruneThreshold) {
    461     visit_history_->erase(visit_history_->begin(),
    462                           visit_history_->begin() + kVisitHistoryPruneAmount);
    463   }
    464   RecordEvent(EVENT_ADD_VISIT_INITIALIZED);
    465   if (current_prerender_.get() &&
    466       current_prerender_->url_id == info.url_id &&
    467       IsPrerenderStillValid(current_prerender_.get())) {
    468     UMA_HISTOGRAM_CUSTOM_TIMES(
    469         "Prerender.LocalPredictorTimeUntilUsed",
    470         GetCurrentTime() - current_prerender_->actual_start_time,
    471         base::TimeDelta::FromMilliseconds(10),
    472         base::TimeDelta::FromMilliseconds(GetMaxLocalPredictionTimeMs()),
    473         50);
    474     last_swapped_in_prerender_.reset(current_prerender_.release());
    475     RecordEvent(EVENT_ADD_VISIT_PRERENDER_IDENTIFIED);
    476   }
    477   if (ShouldExcludeTransitionForPrediction(info.transition))
    478     return;
    479   RecordEvent(EVENT_ADD_VISIT_RELEVANT_TRANSITION);
    480   base::TimeDelta max_age =
    481       base::TimeDelta::FromMilliseconds(GetMaxLocalPredictionTimeMs());
    482   base::TimeDelta min_age =
    483       base::TimeDelta::FromMilliseconds(kMinLocalPredictionTimeMs);
    484   std::set<URLID> next_urls_currently_found;
    485   std::map<URLID, int> next_urls_num_found;
    486   int num_occurrences_of_current_visit = 0;
    487   base::Time last_visited;
    488   scoped_ptr<CandidatePrerenderInfo> lookup_info(
    489       new CandidatePrerenderInfo(info.url_id));
    490   const vector<history::BriefVisitInfo>& visits = *(visit_history_.get());
    491   for (int i = 0; i < static_cast<int>(visits.size()); i++) {
    492     if (!ShouldExcludeTransitionForPrediction(visits[i].transition)) {
    493       if (visits[i].url_id == info.url_id) {
    494         last_visited = visits[i].time;
    495         num_occurrences_of_current_visit++;
    496         next_urls_currently_found.clear();
    497         continue;
    498       }
    499       if (!last_visited.is_null() &&
    500           last_visited > visits[i].time - max_age &&
    501           last_visited < visits[i].time - min_age) {
    502         if (!IsFormSubmit(visits[i].transition))
    503           next_urls_currently_found.insert(visits[i].url_id);
    504       }
    505     }
    506     if (i == static_cast<int>(visits.size()) - 1 ||
    507         visits[i+1].url_id == info.url_id) {
    508       for (std::set<URLID>::iterator it = next_urls_currently_found.begin();
    509            it != next_urls_currently_found.end();
    510            ++it) {
    511         std::pair<std::map<URLID, int>::iterator, bool> insert_ret =
    512             next_urls_num_found.insert(std::pair<URLID, int>(*it, 0));
    513         std::map<URLID, int>::iterator num_found_it = insert_ret.first;
    514         num_found_it->second++;
    515       }
    516     }
    517   }
    518 
    519   if (num_occurrences_of_current_visit > 1) {
    520     RecordEvent(EVENT_ADD_VISIT_RELEVANT_TRANSITION_REPEAT_URL);
    521   } else {
    522     RecordEvent(EVENT_ADD_VISIT_RELEVANT_TRANSITION_NEW_URL);
    523   }
    524 
    525   for (std::map<URLID, int>::const_iterator it = next_urls_num_found.begin();
    526        it != next_urls_num_found.end();
    527        ++it) {
    528     // Only consider a candidate next page for prerendering if it was viewed
    529     // at least twice, and at least 10% of the time.
    530     if (num_occurrences_of_current_visit > 0 &&
    531         it->second > 1 &&
    532         it->second * 10 >= num_occurrences_of_current_visit) {
    533       RecordEvent(EVENT_ADD_VISIT_IDENTIFIED_PRERENDER_CANDIDATE);
    534       double priority = static_cast<double>(it->second) /
    535           static_cast<double>(num_occurrences_of_current_visit);
    536       lookup_info->MaybeAddCandidateURLFromLocalData(it->first, priority);
    537     }
    538   }
    539 
    540   RecordEvent(EVENT_START_URL_LOOKUP);
    541   HistoryService* history = GetHistoryIfExists();
    542   if (history) {
    543     RecordEvent(EVENT_GOT_HISTORY_ISSUING_LOOKUP);
    544     CandidatePrerenderInfo* lookup_info_ptr = lookup_info.get();
    545     history->ScheduleDBTask(
    546         new GetURLForURLIDTask(
    547             lookup_info_ptr,
    548             base::Bind(&PrerenderLocalPredictor::OnLookupURL,
    549                        base::Unretained(this),
    550                        base::Passed(&lookup_info))),
    551         &history_db_consumer_);
    552   }
    553 }
    554 
    555 void PrerenderLocalPredictor::OnLookupURL(
    556     scoped_ptr<CandidatePrerenderInfo> info) {
    557   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    558 
    559   RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT);
    560 
    561   if (!info->source_url_.url_lookup_success) {
    562     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_FAILED);
    563     return;
    564   }
    565 
    566   if (info->candidate_urls_.size() > 0 &&
    567       info->candidate_urls_[0].url_lookup_success) {
    568     LogCandidateURLStats(info->candidate_urls_[0].url);
    569   }
    570 
    571   WebContents* source_web_contents = NULL;
    572   bool multiple_source_web_contents_candidates = false;
    573 
    574 #if !defined(OS_ANDROID)
    575   // We need to figure out what tab launched the prerender. We do this by
    576   // comparing URLs. This may not always work: the URL may occur in two
    577   // tabs, and we pick the wrong one, or the tab we should have picked
    578   // may have navigated elsewhere. Hopefully, this doesn't happen too often,
    579   // so we ignore these cases for now.
    580   // TODO(tburkard): Reconsider this, potentially measure it, and fix this
    581   // in the future.
    582   for (TabContentsIterator it; !it.done(); it.Next()) {
    583     if (it->GetURL() == info->source_url_.url) {
    584       if (!source_web_contents)
    585         source_web_contents = *it;
    586       else
    587         multiple_source_web_contents_candidates = true;
    588     }
    589   }
    590 #endif
    591 
    592   if (!source_web_contents) {
    593     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_NO_SOURCE_WEBCONTENTS_FOUND);
    594     return;
    595   }
    596 
    597   if (multiple_source_web_contents_candidates)
    598     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_MULTIPLE_SOURCE_WEBCONTENTS_FOUND);
    599 
    600   info->session_storage_namespace_ =
    601       source_web_contents->GetController().GetDefaultSessionStorageNamespace();
    602 
    603   gfx::Rect container_bounds;
    604   source_web_contents->GetView()->GetContainerBounds(&container_bounds);
    605   info->size_.reset(new gfx::Size(container_bounds.size()));
    606 
    607   RecordEvent(EVENT_PRERENDER_URL_LOOKUP_SUCCESS);
    608 
    609   DoPrerenderServiceCheck(info.Pass());
    610 }
    611 
    612 void PrerenderLocalPredictor::DoPrerenderServiceCheck(
    613     scoped_ptr<CandidatePrerenderInfo> info) {
    614   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    615   if (!ShouldQueryPrerenderService(prerender_manager_->profile())) {
    616     RecordEvent(EVENT_PRERENDER_SERVICE_DISABLED);
    617     DoLoggedInLookup(info.Pass());
    618     return;
    619   }
    620   /*
    621     Create a JSON request.
    622     Here is a sample request:
    623     { "prerender_request": {
    624         "version": 1,
    625         "behavior_id": 6,
    626         "hint_request": {
    627           "browse_history": [
    628             { "url": "http://www.cnn.com/"
    629             }
    630           ]
    631         },
    632         "candidate_check_request": {
    633           "candidates": [
    634             { "url": "http://www.cnn.com/sports/"
    635             },
    636             { "url": "http://www.cnn.com/politics/"
    637             }
    638           ]
    639         }
    640       }
    641     }
    642   */
    643   DictionaryValue json_data;
    644   DictionaryValue* req = new DictionaryValue();
    645   req->SetInteger("version", 1);
    646   req->SetInteger("behavior_id", GetPrerenderServiceBehaviorID());
    647   if (ShouldQueryPrerenderServiceForCurrentURL() &&
    648       info->source_url_.url_lookup_success) {
    649     ListValue* browse_history = new ListValue();
    650     DictionaryValue* browse_item = new DictionaryValue();
    651     browse_item->SetString("url", info->source_url_.url.spec());
    652     browse_history->Append(browse_item);
    653     DictionaryValue* hint_request = new DictionaryValue();
    654     hint_request->Set("browse_history", browse_history);
    655     req->Set("hint_request", hint_request);
    656   }
    657   int num_candidate_urls = 0;
    658   for (int i = 0; i < static_cast<int>(info->candidate_urls_.size()); i++) {
    659     if (info->candidate_urls_[i].url_lookup_success)
    660       num_candidate_urls++;
    661   }
    662   if (ShouldQueryPrerenderServiceForCandidateURLs() &&
    663       num_candidate_urls > 0) {
    664     ListValue* candidates = new ListValue();
    665     DictionaryValue* candidate;
    666     for (int i = 0; i < static_cast<int>(info->candidate_urls_.size()); i++) {
    667       if (info->candidate_urls_[i].url_lookup_success) {
    668         candidate = new DictionaryValue();
    669         candidate->SetString("url", info->candidate_urls_[i].url.spec());
    670         candidates->Append(candidate);
    671       }
    672     }
    673     DictionaryValue* candidate_check_request = new DictionaryValue();
    674     candidate_check_request->Set("candidates", candidates);
    675     req->Set("candidate_check_request", candidate_check_request);
    676   }
    677   json_data.Set("prerender_request", req);
    678   string request_string;
    679   base::JSONWriter::Write(&json_data, &request_string);
    680   GURL fetch_url(GetPrerenderServiceURLPrefix() +
    681                  net::EscapeQueryParamValue(request_string, false));
    682   net::URLFetcher* fetcher = net::URLFetcher::Create(
    683       0,
    684       fetch_url,
    685       URLFetcher::GET, this);
    686   fetcher->SetRequestContext(
    687       prerender_manager_->profile()->GetRequestContext());
    688   fetcher->SetLoadFlags(net::LOAD_DISABLE_CACHE |
    689                         net::LOAD_DO_NOT_SAVE_COOKIES |
    690                         net::LOAD_DO_NOT_SEND_COOKIES);
    691   fetcher->AddExtraRequestHeader("Pragma: no-cache");
    692   info->start_time_ = base::Time::Now();
    693   outstanding_prerender_service_requests_.insert(
    694       std::make_pair(fetcher, info.release()));
    695   base::MessageLoop::current()->PostDelayedTask(
    696       FROM_HERE,
    697       base::Bind(&PrerenderLocalPredictor::MaybeCancelURLFetcher,
    698                  weak_factory_.GetWeakPtr(), fetcher),
    699       base::TimeDelta::FromMilliseconds(GetPrerenderServiceFetchTimeoutMs()));
    700   RecordEvent(EVENT_PRERENDER_SERVICE_ISSUED_LOOKUP);
    701   fetcher->Start();
    702 }
    703 
    704 void PrerenderLocalPredictor::MaybeCancelURLFetcher(net::URLFetcher* fetcher) {
    705   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    706   OutstandingFetchers::iterator it =
    707       outstanding_prerender_service_requests_.find(fetcher);
    708   if (it == outstanding_prerender_service_requests_.end())
    709     return;
    710   delete it->first;
    711   scoped_ptr<CandidatePrerenderInfo> info(it->second);
    712   outstanding_prerender_service_requests_.erase(it);
    713   RecordEvent(EVENT_PRERENDER_SERVICE_LOOKUP_TIMED_OUT);
    714   DoLoggedInLookup(info.Pass());
    715 }
    716 
    717 bool PrerenderLocalPredictor::ApplyParsedPrerenderServiceResponse(
    718     DictionaryValue* dict,
    719     CandidatePrerenderInfo* info,
    720     bool* hinting_timed_out,
    721     bool* hinting_url_lookup_timed_out,
    722     bool* candidate_url_lookup_timed_out) {
    723   /*
    724     Process the response to the request.
    725     Here is a sample response to illustrate the format.
    726     {
    727       "prerender_response": {
    728         "behavior_id": 6,
    729         "hint_response": {
    730           "hinting_timed_out": 0,
    731           "candidates": [
    732             { "url": "http://www.cnn.com/story-1",
    733               "in_index": 1,
    734               "likelihood": 0.60,
    735               "in_index_timed_out": 0
    736             },
    737             { "url": "http://www.cnn.com/story-2",
    738               "in_index": 1,
    739               "likelihood": 0.30,
    740               "in_index_timed_out": 0
    741             }
    742           ]
    743         },
    744         "candidate_check_response": {
    745           "candidates": [
    746             { "url": "http://www.cnn.com/sports/",
    747               "in_index": 1,
    748               "in_index_timed_out": 0
    749             },
    750             { "url": "http://www.cnn.com/politics/",
    751               "in_index": 0,
    752               "in_index_timed_out": "1"
    753             }
    754           ]
    755         }
    756       }
    757     }
    758   */
    759   ListValue* list = NULL;
    760   int int_value;
    761   if (!dict->GetInteger("prerender_response.behavior_id", &int_value) ||
    762       int_value != GetPrerenderServiceBehaviorID()) {
    763     return false;
    764   }
    765   if (!dict->GetList("prerender_response.candidate_check_response.candidates",
    766                      &list)) {
    767     if (ShouldQueryPrerenderServiceForCandidateURLs()) {
    768       for (int i = 0; i < static_cast<int>(info->candidate_urls_.size()); i++) {
    769         if (info->candidate_urls_[i].url_lookup_success)
    770           return false;
    771       }
    772     }
    773   } else {
    774     for (size_t i = 0; i < list->GetSize(); i++) {
    775       DictionaryValue* d;
    776       if (!list->GetDictionary(i, &d))
    777         return false;
    778       string url_string;
    779       if (!d->GetString("url", &url_string) || !GURL(url_string).is_valid())
    780         return false;
    781       GURL url(url_string);
    782       int in_index_timed_out = 0;
    783       int in_index = 0;
    784       if ((!d->GetInteger("in_index_timed_out", &in_index_timed_out) ||
    785            in_index_timed_out != 1) &&
    786           !d->GetInteger("in_index", &in_index)) {
    787         return false;
    788       }
    789       if (in_index < 0 || in_index > 1 ||
    790           in_index_timed_out < 0 || in_index_timed_out > 1) {
    791         return false;
    792       }
    793       if (in_index_timed_out == 1)
    794         *candidate_url_lookup_timed_out = true;
    795       for (size_t j = 0; j < info->candidate_urls_.size(); j++) {
    796         if (info->candidate_urls_[j].url == url) {
    797           info->candidate_urls_[j].service_whitelist_reported = true;
    798           info->candidate_urls_[j].service_whitelist = (in_index == 1);
    799           info->candidate_urls_[j].service_whitelist_lookup_ok =
    800               ((1 - in_index_timed_out) == 1);
    801         }
    802       }
    803     }
    804     for (size_t i = 0; i < info->candidate_urls_.size(); i++) {
    805       if (info->candidate_urls_[i].url_lookup_success &&
    806           !info->candidate_urls_[i].service_whitelist_reported) {
    807         return false;
    808       }
    809     }
    810   }
    811 
    812   if (ShouldQueryPrerenderServiceForCurrentURL() &&
    813       info->source_url_.url_lookup_success) {
    814     list = NULL;
    815     if (dict->GetInteger("prerender_response.hint_response.hinting_timed_out",
    816                          &int_value) &&
    817         int_value == 1) {
    818       *hinting_timed_out = true;
    819     } else if (!dict->GetList("prerender_response.hint_response.candidates",
    820                               &list)) {
    821       return false;
    822     } else {
    823       for (int i = 0; i < static_cast<int>(list->GetSize()); i++) {
    824         DictionaryValue* d;
    825         if (!list->GetDictionary(i, &d))
    826           return false;
    827         string url;
    828         double priority;
    829         if (!d->GetString("url", &url) || !d->GetDouble("likelihood", &priority)
    830             || !GURL(url).is_valid()) {
    831           return false;
    832         }
    833         int in_index_timed_out = 0;
    834         int in_index = 0;
    835         if ((!d->GetInteger("in_index_timed_out", &in_index_timed_out) ||
    836              in_index_timed_out != 1) &&
    837             !d->GetInteger("in_index", &in_index)) {
    838           return false;
    839         }
    840         if (priority < 0.0 || priority > 1.0 || in_index < 0 || in_index > 1 ||
    841             in_index_timed_out < 0 || in_index_timed_out > 1) {
    842           return false;
    843         }
    844         if (in_index_timed_out == 1)
    845           *hinting_url_lookup_timed_out = true;
    846         info->MaybeAddCandidateURLFromService(GURL(url),
    847                                               priority,
    848                                               in_index == 1,
    849                                               (1 - in_index_timed_out) == 1);
    850       }
    851       if (list->GetSize() > 0)
    852         RecordEvent(EVENT_PRERENDER_SERIVCE_RETURNED_HINTING_CANDIDATES);
    853     }
    854   }
    855 
    856   return true;
    857 }
    858 
    859 void PrerenderLocalPredictor::OnURLFetchComplete(
    860     const net::URLFetcher* source) {
    861   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    862   RecordEvent(EVENT_PRERENDER_SERVICE_RECEIVED_RESULT);
    863   net::URLFetcher* fetcher = const_cast<net::URLFetcher*>(source);
    864   OutstandingFetchers::iterator it =
    865       outstanding_prerender_service_requests_.find(fetcher);
    866   if (it == outstanding_prerender_service_requests_.end()) {
    867     RecordEvent(EVENT_PRERENDER_SERVICE_NO_RECORD_FOR_RESULT);
    868     return;
    869   }
    870   scoped_ptr<CandidatePrerenderInfo> info(it->second);
    871   outstanding_prerender_service_requests_.erase(it);
    872   TIMING_HISTOGRAM("Prerender.LocalPredictorServiceLookupTime",
    873                    base::Time::Now() - info->start_time_);
    874   string result;
    875   fetcher->GetResponseAsString(&result);
    876   scoped_ptr<Value> root;
    877   root.reset(base::JSONReader::Read(result));
    878   bool hinting_timed_out = false;
    879   bool hinting_url_lookup_timed_out = false;
    880   bool candidate_url_lookup_timed_out = false;
    881   if (!root.get() || !root->IsType(Value::TYPE_DICTIONARY)) {
    882     RecordEvent(EVENT_PRERENDER_SERVICE_PARSE_ERROR_INCORRECT_JSON);
    883   } else {
    884     if (ApplyParsedPrerenderServiceResponse(
    885             static_cast<DictionaryValue*>(root.get()),
    886             info.get(),
    887             &hinting_timed_out,
    888             &hinting_url_lookup_timed_out,
    889             &candidate_url_lookup_timed_out)) {
    890       // We finished parsing the result, and found no errors.
    891       RecordEvent(EVENT_PRERENDER_SERVICE_PARSED_CORRECTLY);
    892       if (hinting_timed_out)
    893         RecordEvent(EVENT_PRERENDER_SERVICE_HINTING_TIMED_OUT);
    894       if (hinting_url_lookup_timed_out)
    895         RecordEvent(EVENT_PRERENDER_SERVICE_HINTING_URL_LOOKUP_TIMED_OUT);
    896       if (candidate_url_lookup_timed_out)
    897         RecordEvent(EVENT_PRERENDER_SERVICE_CANDIDATE_URL_LOOKUP_TIMED_OUT);
    898       DoLoggedInLookup(info.Pass());
    899       return;
    900     }
    901   }
    902 
    903   // If we did not return earlier, an error happened during parsing.
    904   // Record this, and proceed.
    905   RecordEvent(EVENT_PRERENDER_SERVICE_PARSE_ERROR);
    906   DoLoggedInLookup(info.Pass());
    907 }
    908 
    909 void PrerenderLocalPredictor:: DoLoggedInLookup(
    910     scoped_ptr<CandidatePrerenderInfo> info) {
    911   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    912   scoped_refptr<LoggedInPredictorTable> logged_in_table =
    913       prerender_manager_->logged_in_predictor_table();
    914 
    915   if (!logged_in_table.get()) {
    916     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_NO_LOGGED_IN_TABLE_FOUND);
    917     return;
    918   }
    919 
    920   RecordEvent(EVENT_PRERENDER_URL_LOOKUP_ISSUING_LOGGED_IN_LOOKUP);
    921 
    922   info->start_time_ = base::Time::Now();
    923 
    924   CandidatePrerenderInfo* info_ptr = info.get();
    925   BrowserThread::PostTaskAndReply(
    926       BrowserThread::DB, FROM_HERE,
    927       base::Bind(&LookupLoggedInStatesOnDBThread,
    928                  logged_in_table,
    929                  info_ptr),
    930       base::Bind(&PrerenderLocalPredictor::ContinuePrerenderCheck,
    931                  weak_factory_.GetWeakPtr(),
    932                  base::Passed(&info)));
    933 }
    934 
    935 void PrerenderLocalPredictor::LogCandidateURLStats(const GURL& url) const {
    936   if (url_whitelist_.count(GetInt64URLHashForURL(url)) > 0) {
    937     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_ON_WHITELIST);
    938     if (IsRootPageURL(url))
    939       RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_ON_WHITELIST_ROOT_PAGE);
    940   }
    941   if (IsRootPageURL(url))
    942     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_ROOT_PAGE);
    943   if (IsExtendedRootURL(url))
    944     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_EXTENDED_ROOT_PAGE);
    945   if (IsRootPageURL(url) && url.SchemeIs("http"))
    946     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_ROOT_PAGE_HTTP);
    947   if (url.SchemeIs("http"))
    948     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_IS_HTTP);
    949   if (url.has_query())
    950     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_HAS_QUERY_STRING);
    951   if (IsLogOutURL(url))
    952     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_CONTAINS_LOGOUT);
    953   if (IsLogInURL(url))
    954     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_CONTAINS_LOGIN);
    955 }
    956 
    957 void PrerenderLocalPredictor::OnGetInitialVisitHistory(
    958     scoped_ptr<vector<history::BriefVisitInfo> > visit_history) {
    959   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    960   DCHECK(!visit_history_.get());
    961   RecordEvent(EVENT_INIT_SUCCEEDED);
    962   // Since the visit history has descending timestamps, we must reverse it.
    963   visit_history_.reset(new vector<history::BriefVisitInfo>(
    964       visit_history->rbegin(), visit_history->rend()));
    965 }
    966 
    967 HistoryService* PrerenderLocalPredictor::GetHistoryIfExists() const {
    968   Profile* profile = prerender_manager_->profile();
    969   if (!profile)
    970     return NULL;
    971   return HistoryServiceFactory::GetForProfileWithoutCreating(profile);
    972 }
    973 
    974 void PrerenderLocalPredictor::Init() {
    975   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    976   RecordEvent(EVENT_INIT_STARTED);
    977   Profile* profile = prerender_manager_->profile();
    978   if (!profile || DisableLocalPredictorBasedOnSyncAndConfiguration(profile)) {
    979     RecordEvent(EVENT_INIT_FAILED_UNENCRYPTED_SYNC_NOT_ENABLED);
    980     return;
    981   }
    982   HistoryService* history = GetHistoryIfExists();
    983   if (history) {
    984     CHECK(!is_visit_database_observer_);
    985     history->ScheduleDBTask(
    986         new GetVisitHistoryTask(this, kMaxVisitHistory),
    987         &history_db_consumer_);
    988     history->AddVisitDatabaseObserver(this);
    989     is_visit_database_observer_ = true;
    990   } else {
    991     RecordEvent(EVENT_INIT_FAILED_NO_HISTORY);
    992   }
    993 }
    994 
    995 void PrerenderLocalPredictor::OnPLTEventForURL(const GURL& url,
    996                                                base::TimeDelta page_load_time) {
    997   scoped_ptr<PrerenderProperties> prerender;
    998   if (DoesPrerenderMatchPLTRecord(last_swapped_in_prerender_.get(),
    999                                   url, page_load_time)) {
   1000     prerender.reset(last_swapped_in_prerender_.release());
   1001   }
   1002   if (DoesPrerenderMatchPLTRecord(current_prerender_.get(),
   1003                                   url, page_load_time)) {
   1004     prerender.reset(current_prerender_.release());
   1005   }
   1006   if (!prerender.get())
   1007     return;
   1008   if (IsPrerenderStillValid(prerender.get())) {
   1009     UMA_HISTOGRAM_CUSTOM_TIMES("Prerender.SimulatedLocalBrowsingBaselinePLT",
   1010                                page_load_time,
   1011                                base::TimeDelta::FromMilliseconds(10),
   1012                                base::TimeDelta::FromSeconds(60),
   1013                                100);
   1014 
   1015     base::TimeDelta prerender_age = GetCurrentTime() - prerender->start_time;
   1016     if (prerender_age > page_load_time) {
   1017       base::TimeDelta new_plt;
   1018       if (prerender_age <  2 * page_load_time)
   1019         new_plt = 2 * page_load_time - prerender_age;
   1020       UMA_HISTOGRAM_CUSTOM_TIMES("Prerender.SimulatedLocalBrowsingPLT",
   1021                                  new_plt,
   1022                                  base::TimeDelta::FromMilliseconds(10),
   1023                                  base::TimeDelta::FromSeconds(60),
   1024                                  100);
   1025     }
   1026   }
   1027 }
   1028 
   1029 bool PrerenderLocalPredictor::IsPrerenderStillValid(
   1030     PrerenderLocalPredictor::PrerenderProperties* prerender) const {
   1031   return (prerender &&
   1032           (prerender->start_time +
   1033            base::TimeDelta::FromMilliseconds(GetMaxLocalPredictionTimeMs()))
   1034           > GetCurrentTime());
   1035 }
   1036 
   1037 void PrerenderLocalPredictor::RecordEvent(
   1038     PrerenderLocalPredictor::Event event) const {
   1039   UMA_HISTOGRAM_ENUMERATION("Prerender.LocalPredictorEvent",
   1040       event, PrerenderLocalPredictor::EVENT_MAX_VALUE);
   1041 }
   1042 
   1043 bool PrerenderLocalPredictor::DoesPrerenderMatchPLTRecord(
   1044     PrerenderProperties* prerender,
   1045     const GURL& url,
   1046     base::TimeDelta plt) const {
   1047   if (prerender && prerender->start_time < GetCurrentTime() - plt) {
   1048     if (prerender->url.is_empty())
   1049       RecordEvent(EVENT_ERROR_NO_PRERENDER_URL_FOR_PLT);
   1050     return (prerender->url == url);
   1051   } else {
   1052     return false;
   1053   }
   1054 }
   1055 
   1056 PrerenderLocalPredictor::PrerenderProperties*
   1057 PrerenderLocalPredictor::GetIssuedPrerenderSlotForPriority(double priority) {
   1058   int num_prerenders = GetLocalPredictorMaxConcurrentPrerenders();
   1059   while (static_cast<int>(issued_prerenders_.size()) < num_prerenders)
   1060     issued_prerenders_.push_back(new PrerenderProperties());
   1061   PrerenderProperties* lowest_priority_prerender = NULL;
   1062   for (int i = 0; i < static_cast<int>(issued_prerenders_.size()); i++) {
   1063     PrerenderProperties* p = issued_prerenders_[i];
   1064     DCHECK(p != NULL);
   1065     if (!p->prerender_handle || !p->prerender_handle->IsPrerendering())
   1066       return p;
   1067     double decayed_priority = p->GetCurrentDecayedPriority();
   1068     if (decayed_priority > priority)
   1069       continue;
   1070     if (lowest_priority_prerender == NULL ||
   1071         lowest_priority_prerender->GetCurrentDecayedPriority() >
   1072         decayed_priority) {
   1073       lowest_priority_prerender = p;
   1074     }
   1075   }
   1076   return lowest_priority_prerender;
   1077 }
   1078 
   1079 void PrerenderLocalPredictor::ContinuePrerenderCheck(
   1080     scoped_ptr<CandidatePrerenderInfo> info) {
   1081   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
   1082   TIMING_HISTOGRAM("Prerender.LocalPredictorLoggedInLookupTime",
   1083                    base::Time::Now() - info->start_time_);
   1084   RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_STARTED);
   1085   if (info->candidate_urls_.size() == 0) {
   1086     RecordEvent(EVENT_NO_PRERENDER_CANDIDATES);
   1087     return;
   1088   }
   1089   scoped_ptr<LocalPredictorURLInfo> url_info;
   1090 #if defined(FULL_SAFE_BROWSING)
   1091   scoped_refptr<SafeBrowsingDatabaseManager> sb_db_manager =
   1092       g_browser_process->safe_browsing_service()->database_manager();
   1093 #endif
   1094   PrerenderProperties* prerender_properties = NULL;
   1095 
   1096   for (int i = 0; i < static_cast<int>(info->candidate_urls_.size()); i++) {
   1097     RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_EXAMINE_NEXT_URL);
   1098     url_info.reset(new LocalPredictorURLInfo(info->candidate_urls_[i]));
   1099     if (url_info->local_history_based) {
   1100       if (SkipLocalPredictorLocalCandidates()) {
   1101         url_info.reset(NULL);
   1102         continue;
   1103       }
   1104       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_EXAMINE_NEXT_URL_LOCAL);
   1105     }
   1106     if (!url_info->local_history_based) {
   1107       if (SkipLocalPredictorServiceCandidates()) {
   1108         url_info.reset(NULL);
   1109         continue;
   1110       }
   1111       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_EXAMINE_NEXT_URL_SERVICE);
   1112     }
   1113 
   1114     RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_EXAMINE_NEXT_URL_NOT_SKIPPED);
   1115 
   1116     // We need to check whether we can issue a prerender for this URL.
   1117     // We test a set of conditions. Each condition can either rule out
   1118     // a prerender (in which case we reset url_info, so that it will not
   1119     // be prerendered, and we continue, which means try the next candidate
   1120     // URL), or it can be sufficient to issue the prerender without any
   1121     // further checks (in which case we just break).
   1122     // The order of the checks is critical, because it prescribes the logic
   1123     // we use here to decide what to prerender.
   1124     if (!url_info->url_lookup_success) {
   1125       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_NO_URL);
   1126       url_info.reset(NULL);
   1127       continue;
   1128     }
   1129     prerender_properties =
   1130         GetIssuedPrerenderSlotForPriority(url_info->priority);
   1131     if (!prerender_properties) {
   1132       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_PRIORITY_TOO_LOW);
   1133       url_info.reset(NULL);
   1134       continue;
   1135     }
   1136     if (!SkipLocalPredictorFragment() &&
   1137         URLsIdenticalIgnoringFragments(info->source_url_.url,
   1138                                        url_info->url)) {
   1139       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_URLS_IDENTICAL_BUT_FRAGMENT);
   1140       url_info.reset(NULL);
   1141       continue;
   1142     }
   1143     if (!SkipLocalPredictorHTTPS() && url_info->url.SchemeIs("https")) {
   1144       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_HTTPS);
   1145       url_info.reset(NULL);
   1146       continue;
   1147     }
   1148     if (IsRootPageURL(url_info->url)) {
   1149       // For root pages, we assume that they are reasonably safe, and we
   1150       // will just prerender them without any additional checks.
   1151       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_ROOT_PAGE);
   1152       break;
   1153     }
   1154     if (IsLogOutURL(url_info->url)) {
   1155       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_LOGOUT_URL);
   1156       url_info.reset(NULL);
   1157       continue;
   1158     }
   1159     if (IsLogInURL(url_info->url)) {
   1160       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_LOGIN_URL);
   1161       url_info.reset(NULL);
   1162       continue;
   1163     }
   1164 #if defined(FULL_SAFE_BROWSING)
   1165     if (!SkipLocalPredictorWhitelist() &&
   1166         sb_db_manager->CheckSideEffectFreeWhitelistUrl(url_info->url)) {
   1167       // If a page is on the side-effect free whitelist, we will just prerender
   1168       // it without any additional checks.
   1169       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_ON_SIDE_EFFECT_FREE_WHITELIST);
   1170       break;
   1171     }
   1172 #endif
   1173     if (!SkipLocalPredictorServiceWhitelist() &&
   1174         url_info->service_whitelist && url_info->service_whitelist_lookup_ok) {
   1175       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_ON_SERVICE_WHITELIST);
   1176       break;
   1177     }
   1178     if (!SkipLocalPredictorLoggedIn() &&
   1179         !url_info->logged_in && url_info->logged_in_lookup_ok) {
   1180       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_NOT_LOGGED_IN);
   1181       break;
   1182     }
   1183     if (!SkipLocalPredictorDefaultNoPrerender()) {
   1184       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_FALLTHROUGH_NOT_PRERENDERING);
   1185       url_info.reset(NULL);
   1186     } else {
   1187       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_FALLTHROUGH_PRERENDERING);
   1188     }
   1189   }
   1190   if (!url_info.get())
   1191     return;
   1192   RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_ISSUING_PRERENDER);
   1193   DCHECK(prerender_properties != NULL);
   1194   if (IsLocalPredictorPrerenderLaunchEnabled()) {
   1195     IssuePrerender(info.Pass(), url_info.Pass(), prerender_properties);
   1196   }
   1197 }
   1198 
   1199 void PrerenderLocalPredictor::IssuePrerender(
   1200     scoped_ptr<CandidatePrerenderInfo> info,
   1201     scoped_ptr<LocalPredictorURLInfo> url_info,
   1202     PrerenderProperties* prerender_properties) {
   1203   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
   1204   URLID url_id = url_info->id;
   1205   const GURL& url = url_info->url;
   1206   double priority = url_info->priority;
   1207   base::Time current_time = GetCurrentTime();
   1208   RecordEvent(EVENT_ISSUING_PRERENDER);
   1209 
   1210   // Issue the prerender and obtain a new handle.
   1211   scoped_ptr<prerender::PrerenderHandle> new_prerender_handle(
   1212       prerender_manager_->AddPrerenderFromLocalPredictor(
   1213           url, info->session_storage_namespace_.get(), *(info->size_)));
   1214 
   1215   // Check if this is a duplicate of an existing prerender. If yes, clean up
   1216   // the new handle.
   1217   for (int i = 0; i < static_cast<int>(issued_prerenders_.size()); i++) {
   1218     PrerenderProperties* p = issued_prerenders_[i];
   1219     DCHECK(p != NULL);
   1220     if (new_prerender_handle &&
   1221         new_prerender_handle->RepresentingSamePrerenderAs(
   1222             p->prerender_handle.get())) {
   1223       new_prerender_handle->OnCancel();
   1224       new_prerender_handle.reset(NULL);
   1225       RecordEvent(EVENT_ISSUE_PRERENDER_ALREADY_PRERENDERING);
   1226       break;
   1227     }
   1228   }
   1229 
   1230   if (new_prerender_handle.get()) {
   1231     RecordEvent(EVENT_ISSUE_PRERENDER_NEW_PRERENDER);
   1232     // The new prerender does not match any existing prerenders. Update
   1233     // prerender_properties so that it reflects the new entry.
   1234     prerender_properties->url_id = url_id;
   1235     prerender_properties->url = url;
   1236     prerender_properties->priority = priority;
   1237     prerender_properties->start_time = current_time;
   1238     prerender_properties->actual_start_time = current_time;
   1239     prerender_properties->would_have_matched = false;
   1240     prerender_properties->prerender_handle.swap(new_prerender_handle);
   1241     // new_prerender_handle now represents the old previou prerender that we
   1242     // are replacing. So we need to cancel it.
   1243     if (new_prerender_handle) {
   1244       new_prerender_handle->OnCancel();
   1245       RecordEvent(EVENT_ISSUE_PRERENDER_CANCELLED_OLD_PRERENDER);
   1246     }
   1247   }
   1248 
   1249   RecordEvent(EVENT_ADD_VISIT_PRERENDERING);
   1250   if (current_prerender_.get() && current_prerender_->url_id == url_id) {
   1251     RecordEvent(EVENT_ADD_VISIT_PRERENDERING_EXTENDED);
   1252     if (priority > current_prerender_->priority)
   1253       current_prerender_->priority = priority;
   1254     // If the prerender already existed, we want to extend it.  However,
   1255     // we do not want to set its start_time to the current time to
   1256     // disadvantage PLT computations when the prerender is swapped in.
   1257     // So we set the new start time to current_time - 10s (since the vast
   1258     // majority of PLTs are < 10s), provided that is not before the actual
   1259     // time the prerender was started (so as to not artificially advantage
   1260     // the PLT computation).
   1261     base::Time simulated_new_start_time =
   1262         current_time - base::TimeDelta::FromSeconds(10);
   1263     if (simulated_new_start_time > current_prerender_->start_time)
   1264       current_prerender_->start_time = simulated_new_start_time;
   1265   } else {
   1266     current_prerender_.reset(
   1267         new PrerenderProperties(url_id, url, priority, current_time));
   1268   }
   1269   current_prerender_->actual_start_time = current_time;
   1270 }
   1271 
   1272 void PrerenderLocalPredictor::OnTabHelperURLSeen(
   1273     const GURL& url, WebContents* web_contents) {
   1274   RecordEvent(EVENT_TAB_HELPER_URL_SEEN);
   1275 
   1276   bool browser_navigate_initiated = false;
   1277   const content::NavigationEntry* entry =
   1278       web_contents->GetController().GetPendingEntry();
   1279   if (entry) {
   1280     base::string16 result;
   1281     browser_navigate_initiated =
   1282         entry->GetExtraData(kChromeNavigateExtraDataKey, &result);
   1283   }
   1284 
   1285   // If the namespace matches and the URL matches, we might be able to swap
   1286   // in. However, the actual code initating the swapin is in the renderer
   1287   // and is checking for other criteria (such as POSTs). There may
   1288   // also be conditions when a swapin should happen but does not. By recording
   1289   // the two previous events, we can keep an eye on the magnitude of the
   1290   // discrepancy.
   1291 
   1292   PrerenderProperties* best_matched_prerender = NULL;
   1293   bool session_storage_namespace_matches = false;
   1294   SessionStorageNamespace* tab_session_storage_namespace =
   1295       web_contents->GetController().GetDefaultSessionStorageNamespace();
   1296   for (int i = 0; i < static_cast<int>(issued_prerenders_.size()); i++) {
   1297     PrerenderProperties* p = issued_prerenders_[i];
   1298     DCHECK(p != NULL);
   1299     if (!p->prerender_handle.get() ||
   1300         !p->prerender_handle->Matches(url, NULL) ||
   1301         p->would_have_matched) {
   1302       continue;
   1303     }
   1304     if (!best_matched_prerender || !session_storage_namespace_matches) {
   1305       best_matched_prerender = p;
   1306       session_storage_namespace_matches =
   1307           p->prerender_handle->Matches(url, tab_session_storage_namespace);
   1308     }
   1309   }
   1310   if (best_matched_prerender) {
   1311     RecordEvent(EVENT_TAB_HELPER_URL_SEEN_MATCH);
   1312     if (entry)
   1313       RecordEvent(EVENT_TAB_HELPER_URL_SEEN_MATCH_ENTRY);
   1314     if (browser_navigate_initiated)
   1315       RecordEvent(EVENT_TAB_HELPER_URL_SEEN_MATCH_BROWSER_NAVIGATE);
   1316     best_matched_prerender->would_have_matched = true;
   1317     if (session_storage_namespace_matches) {
   1318       RecordEvent(EVENT_TAB_HELPER_URL_SEEN_NAMESPACE_MATCH);
   1319       if (entry)
   1320         RecordEvent(EVENT_TAB_HELPER_URL_SEEN_NAMESPACE_MATCH_ENTRY);
   1321       if (browser_navigate_initiated)
   1322         RecordEvent(EVENT_TAB_HELPER_URL_SEEN_NAMESPACE_MATCH_BROWSER_NAVIGATE);
   1323     } else {
   1324       SessionStorageNamespace* prerender_session_storage_namespace =
   1325           best_matched_prerender->prerender_handle->
   1326           GetSessionStorageNamespace();
   1327       if (!prerender_session_storage_namespace) {
   1328         RecordEvent(EVENT_TAB_HELPER_URL_SEEN_NAMESPACE_MISMATCH_NO_NAMESPACE);
   1329       } else {
   1330         RecordEvent(EVENT_TAB_HELPER_URL_SEEN_NAMESPACE_MISMATCH_MERGE_ISSUED);
   1331         prerender_session_storage_namespace->Merge(
   1332             false,
   1333             best_matched_prerender->prerender_handle->GetChildId(),
   1334             tab_session_storage_namespace,
   1335             base::Bind(&PrerenderLocalPredictor::ProcessNamespaceMergeResult,
   1336                        weak_factory_.GetWeakPtr()));
   1337       }
   1338     }
   1339   }
   1340 }
   1341 
   1342 void PrerenderLocalPredictor::ProcessNamespaceMergeResult(
   1343     content::SessionStorageNamespace::MergeResult result) {
   1344   RecordEvent(EVENT_NAMESPACE_MISMATCH_MERGE_RESULT_RECEIVED);
   1345   switch (result) {
   1346     case content::SessionStorageNamespace::MERGE_RESULT_NAMESPACE_NOT_FOUND:
   1347       RecordEvent(EVENT_NAMESPACE_MISMATCH_MERGE_RESULT_NAMESPACE_NOT_FOUND);
   1348       break;
   1349     case content::SessionStorageNamespace::MERGE_RESULT_NAMESPACE_NOT_ALIAS:
   1350       RecordEvent(EVENT_NAMESPACE_MISMATCH_MERGE_RESULT_NAMESPACE_NOT_ALIAS);
   1351       break;
   1352     case content::SessionStorageNamespace::MERGE_RESULT_NOT_LOGGING:
   1353       RecordEvent(EVENT_NAMESPACE_MISMATCH_MERGE_RESULT_NOT_LOGGING);
   1354       break;
   1355     case content::SessionStorageNamespace::MERGE_RESULT_NO_TRANSACTIONS:
   1356       RecordEvent(EVENT_NAMESPACE_MISMATCH_MERGE_RESULT_NO_TRANSACTIONS);
   1357       break;
   1358     case content::SessionStorageNamespace::MERGE_RESULT_TOO_MANY_TRANSACTIONS:
   1359       RecordEvent(EVENT_NAMESPACE_MISMATCH_MERGE_RESULT_TOO_MANY_TRANSACTIONS);
   1360       break;
   1361     case content::SessionStorageNamespace::MERGE_RESULT_NOT_MERGEABLE:
   1362       RecordEvent(EVENT_NAMESPACE_MISMATCH_MERGE_RESULT_NOT_MERGEABLE);
   1363       break;
   1364     case content::SessionStorageNamespace::MERGE_RESULT_MERGEABLE:
   1365       RecordEvent(EVENT_NAMESPACE_MISMATCH_MERGE_RESULT_MERGEABLE);
   1366       break;
   1367     default:
   1368       NOTREACHED();
   1369   }
   1370 }
   1371 
   1372 }  // namespace prerender
   1373