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