src/chrome/browser/prerender/prerender_local_predictor.cc

   1 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "chrome/browser/prerender/prerender_local_predictor.h"
   6
   7 #include <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   base::DictionaryValue json_data;
 644   base::DictionaryValue* req = new base::DictionaryValue();
 645   req->SetInteger("version", 1);
 646   req->SetInteger("behavior_id", GetPrerenderServiceBehaviorID());
 647   if (ShouldQueryPrerenderServiceForCurrentURL() &&
 648       info->source_url_.url_lookup_success) {
 649     base::ListValue* browse_history = new base::ListValue();
 650     base::DictionaryValue* browse_item = new base::DictionaryValue();
 651     browse_item->SetString("url", info->source_url_.url.spec());
 652     browse_history->Append(browse_item);
 653     base::DictionaryValue* hint_request = new base::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     base::ListValue* candidates = new base::ListValue();
 665     base::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 base::DictionaryValue();
 669         candidate->SetString("url", info->candidate_urls_[i].url.spec());
 670         candidates->Append(candidate);
 671       }
 672     }
 673     base::DictionaryValue* candidate_check_request =
 674         new base::DictionaryValue();
 675     candidate_check_request->Set("candidates", candidates);
 676     req->Set("candidate_check_request", candidate_check_request);
 677   }
 678   json_data.Set("prerender_request", req);
 679   string request_string;
 680   base::JSONWriter::Write(&json_data, &request_string);
 681   GURL fetch_url(GetPrerenderServiceURLPrefix() +
 682                  net::EscapeQueryParamValue(request_string, false));
 683   net::URLFetcher* fetcher = net::URLFetcher::Create(
 684       0,
 685       fetch_url,
 686       URLFetcher::GET, this);
 687   fetcher->SetRequestContext(
 688       prerender_manager_->profile()->GetRequestContext());
 689   fetcher->SetLoadFlags(net::LOAD_DISABLE_CACHE |
 690                         net::LOAD_DO_NOT_SAVE_COOKIES |
 691                         net::LOAD_DO_NOT_SEND_COOKIES);
 692   fetcher->AddExtraRequestHeader("Pragma: no-cache");
 693   info->start_time_ = base::Time::Now();
 694   outstanding_prerender_service_requests_.insert(
 695       std::make_pair(fetcher, info.release()));
 696   base::MessageLoop::current()->PostDelayedTask(
 697       FROM_HERE,
 698       base::Bind(&PrerenderLocalPredictor::MaybeCancelURLFetcher,
 699                  weak_factory_.GetWeakPtr(), fetcher),
 700       base::TimeDelta::FromMilliseconds(GetPrerenderServiceFetchTimeoutMs()));
 701   RecordEvent(EVENT_PRERENDER_SERVICE_ISSUED_LOOKUP);
 702   fetcher->Start();
 703 }
 704
 705 void PrerenderLocalPredictor::MaybeCancelURLFetcher(net::URLFetcher* fetcher) {
 706   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
 707   OutstandingFetchers::iterator it =
 708       outstanding_prerender_service_requests_.find(fetcher);
 709   if (it == outstanding_prerender_service_requests_.end())
 710     return;
 711   delete it->first;
 712   scoped_ptr<CandidatePrerenderInfo> info(it->second);
 713   outstanding_prerender_service_requests_.erase(it);
 714   RecordEvent(EVENT_PRERENDER_SERVICE_LOOKUP_TIMED_OUT);
 715   DoLoggedInLookup(info.Pass());
 716 }
 717
 718 bool PrerenderLocalPredictor::ApplyParsedPrerenderServiceResponse(
 719     base::DictionaryValue* dict,
 720     CandidatePrerenderInfo* info,
 721     bool* hinting_timed_out,
 722     bool* hinting_url_lookup_timed_out,
 723     bool* candidate_url_lookup_timed_out) {
 724   /*
 725     Process the response to the request.
 726     Here is a sample response to illustrate the format.
 727     {
 728       "prerender_response": {
 729         "behavior_id": 6,
 730         "hint_response": {
 731           "hinting_timed_out": 0,
 732           "candidates": [
 733             { "url": "http://www.cnn.com/story-1",
 734               "in_index": 1,
 735               "likelihood": 0.60,
 736               "in_index_timed_out": 0
 737             },
 738             { "url": "http://www.cnn.com/story-2",
 739               "in_index": 1,
 740               "likelihood": 0.30,
 741               "in_index_timed_out": 0
 742             }
 743           ]
 744         },
 745         "candidate_check_response": {
 746           "candidates": [
 747             { "url": "http://www.cnn.com/sports/",
 748               "in_index": 1,
 749               "in_index_timed_out": 0
 750             },
 751             { "url": "http://www.cnn.com/politics/",
 752               "in_index": 0,
 753               "in_index_timed_out": "1"
 754             }
 755           ]
 756         }
 757       }
 758     }
 759   */
 760   base::ListValue* list = NULL;
 761   int int_value;
 762   if (!dict->GetInteger("prerender_response.behavior_id", &int_value) ||
 763       int_value != GetPrerenderServiceBehaviorID()) {
 764     return false;
 765   }
 766   if (!dict->GetList("prerender_response.candidate_check_response.candidates",
 767                      &list)) {
 768     if (ShouldQueryPrerenderServiceForCandidateURLs()) {
 769       for (int i = 0; i < static_cast<int>(info->candidate_urls_.size()); i++) {
 770         if (info->candidate_urls_[i].url_lookup_success)
 771           return false;
 772       }
 773     }
 774   } else {
 775     for (size_t i = 0; i < list->GetSize(); i++) {
 776       base::DictionaryValue* d;
 777       if (!list->GetDictionary(i, &d))
 778         return false;
 779       string url_string;
 780       if (!d->GetString("url", &url_string) || !GURL(url_string).is_valid())
 781         return false;
 782       GURL url(url_string);
 783       int in_index_timed_out = 0;
 784       int in_index = 0;
 785       if ((!d->GetInteger("in_index_timed_out", &in_index_timed_out) ||
 786            in_index_timed_out != 1) &&
 787           !d->GetInteger("in_index", &in_index)) {
 788         return false;
 789       }
 790       if (in_index < 0 || in_index > 1 ||
 791           in_index_timed_out < 0 || in_index_timed_out > 1) {
 792         return false;
 793       }
 794       if (in_index_timed_out == 1)
 795         *candidate_url_lookup_timed_out = true;
 796       for (size_t j = 0; j < info->candidate_urls_.size(); j++) {
 797         if (info->candidate_urls_[j].url == url) {
 798           info->candidate_urls_[j].service_whitelist_reported = true;
 799           info->candidate_urls_[j].service_whitelist = (in_index == 1);
 800           info->candidate_urls_[j].service_whitelist_lookup_ok =
 801               ((1 - in_index_timed_out) == 1);
 802         }
 803       }
 804     }
 805     for (size_t i = 0; i < info->candidate_urls_.size(); i++) {
 806       if (info->candidate_urls_[i].url_lookup_success &&
 807           !info->candidate_urls_[i].service_whitelist_reported) {
 808         return false;
 809       }
 810     }
 811   }
 812
 813   if (ShouldQueryPrerenderServiceForCurrentURL() &&
 814       info->source_url_.url_lookup_success) {
 815     list = NULL;
 816     if (dict->GetInteger("prerender_response.hint_response.hinting_timed_out",
 817                          &int_value) &&
 818         int_value == 1) {
 819       *hinting_timed_out = true;
 820     } else if (!dict->GetList("prerender_response.hint_response.candidates",
 821                               &list)) {
 822       return false;
 823     } else {
 824       for (int i = 0; i < static_cast<int>(list->GetSize()); i++) {
 825         base::DictionaryValue* d;
 826         if (!list->GetDictionary(i, &d))
 827           return false;
 828         string url;
 829         double priority;
 830         if (!d->GetString("url", &url) || !d->GetDouble("likelihood", &priority)
 831             || !GURL(url).is_valid()) {
 832           return false;
 833         }
 834         int in_index_timed_out = 0;
 835         int in_index = 0;
 836         if ((!d->GetInteger("in_index_timed_out", &in_index_timed_out) ||
 837              in_index_timed_out != 1) &&
 838             !d->GetInteger("in_index", &in_index)) {
 839           return false;
 840         }
 841         if (priority < 0.0 || priority > 1.0 || in_index < 0 || in_index > 1 ||
 842             in_index_timed_out < 0 || in_index_timed_out > 1) {
 843           return false;
 844         }
 845         if (in_index_timed_out == 1)
 846           *hinting_url_lookup_timed_out = true;
 847         info->MaybeAddCandidateURLFromService(GURL(url),
 848                                               priority,
 849                                               in_index == 1,
 850                                               (1 - in_index_timed_out) == 1);
 851       }
 852       if (list->GetSize() > 0)
 853         RecordEvent(EVENT_PRERENDER_SERIVCE_RETURNED_HINTING_CANDIDATES);
 854     }
 855   }
 856
 857   return true;
 858 }
 859
 860 void PrerenderLocalPredictor::OnURLFetchComplete(
 861     const net::URLFetcher* source) {
 862   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
 863   RecordEvent(EVENT_PRERENDER_SERVICE_RECEIVED_RESULT);
 864   net::URLFetcher* fetcher = const_cast<net::URLFetcher*>(source);
 865   OutstandingFetchers::iterator it =
 866       outstanding_prerender_service_requests_.find(fetcher);
 867   if (it == outstanding_prerender_service_requests_.end()) {
 868     RecordEvent(EVENT_PRERENDER_SERVICE_NO_RECORD_FOR_RESULT);
 869     return;
 870   }
 871   scoped_ptr<CandidatePrerenderInfo> info(it->second);
 872   outstanding_prerender_service_requests_.erase(it);
 873   TIMING_HISTOGRAM("Prerender.LocalPredictorServiceLookupTime",
 874                    base::Time::Now() - info->start_time_);
 875   string result;
 876   fetcher->GetResponseAsString(&result);
 877   scoped_ptr<base::Value> root;
 878   root.reset(base::JSONReader::Read(result));
 879   bool hinting_timed_out = false;
 880   bool hinting_url_lookup_timed_out = false;
 881   bool candidate_url_lookup_timed_out = false;
 882   if (!root.get() || !root->IsType(base::Value::TYPE_DICTIONARY)) {
 883     RecordEvent(EVENT_PRERENDER_SERVICE_PARSE_ERROR_INCORRECT_JSON);
 884   } else {
 885     if (ApplyParsedPrerenderServiceResponse(
 886             static_cast<base::DictionaryValue*>(root.get()),
 887             info.get(),
 888             &hinting_timed_out,
 889             &hinting_url_lookup_timed_out,
 890             &candidate_url_lookup_timed_out)) {
 891       // We finished parsing the result, and found no errors.
 892       RecordEvent(EVENT_PRERENDER_SERVICE_PARSED_CORRECTLY);
 893       if (hinting_timed_out)
 894         RecordEvent(EVENT_PRERENDER_SERVICE_HINTING_TIMED_OUT);
 895       if (hinting_url_lookup_timed_out)
 896         RecordEvent(EVENT_PRERENDER_SERVICE_HINTING_URL_LOOKUP_TIMED_OUT);
 897       if (candidate_url_lookup_timed_out)
 898         RecordEvent(EVENT_PRERENDER_SERVICE_CANDIDATE_URL_LOOKUP_TIMED_OUT);
 899       DoLoggedInLookup(info.Pass());
 900       return;
 901     }
 902   }
 903
 904   // If we did not return earlier, an error happened during parsing.
 905   // Record this, and proceed.
 906   RecordEvent(EVENT_PRERENDER_SERVICE_PARSE_ERROR);
 907   DoLoggedInLookup(info.Pass());
 908 }
 909
 910 void PrerenderLocalPredictor:: DoLoggedInLookup(
 911     scoped_ptr<CandidatePrerenderInfo> info) {
 912   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
 913   scoped_refptr<LoggedInPredictorTable> logged_in_table =
 914       prerender_manager_->logged_in_predictor_table();
 915
 916   if (!logged_in_table.get()) {
 917     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_NO_LOGGED_IN_TABLE_FOUND);
 918     return;
 919   }
 920
 921   RecordEvent(EVENT_PRERENDER_URL_LOOKUP_ISSUING_LOGGED_IN_LOOKUP);
 922
 923   info->start_time_ = base::Time::Now();
 924
 925   CandidatePrerenderInfo* info_ptr = info.get();
 926   BrowserThread::PostTaskAndReply(
 927       BrowserThread::DB, FROM_HERE,
 928       base::Bind(&LookupLoggedInStatesOnDBThread,
 929                  logged_in_table,
 930                  info_ptr),
 931       base::Bind(&PrerenderLocalPredictor::ContinuePrerenderCheck,
 932                  weak_factory_.GetWeakPtr(),
 933                  base::Passed(&info)));
 934 }
 935
 936 void PrerenderLocalPredictor::LogCandidateURLStats(const GURL& url) const {
 937   if (url_whitelist_.count(GetInt64URLHashForURL(url)) > 0) {
 938     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_ON_WHITELIST);
 939     if (IsRootPageURL(url))
 940       RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_ON_WHITELIST_ROOT_PAGE);
 941   }
 942   if (IsRootPageURL(url))
 943     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_ROOT_PAGE);
 944   if (IsExtendedRootURL(url))
 945     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_EXTENDED_ROOT_PAGE);
 946   if (IsRootPageURL(url) && url.SchemeIs("http"))
 947     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_ROOT_PAGE_HTTP);
 948   if (url.SchemeIs("http"))
 949     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_IS_HTTP);
 950   if (url.has_query())
 951     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_HAS_QUERY_STRING);
 952   if (IsLogOutURL(url))
 953     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_CONTAINS_LOGOUT);
 954   if (IsLogInURL(url))
 955     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_CONTAINS_LOGIN);
 956 }
 957
 958 void PrerenderLocalPredictor::OnGetInitialVisitHistory(
 959     scoped_ptr<vector<history::BriefVisitInfo> > visit_history) {
 960   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
 961   DCHECK(!visit_history_.get());
 962   RecordEvent(EVENT_INIT_SUCCEEDED);
 963   // Since the visit history has descending timestamps, we must reverse it.
 964   visit_history_.reset(new vector<history::BriefVisitInfo>(
 965       visit_history->rbegin(), visit_history->rend()));
 966 }
 967
 968 HistoryService* PrerenderLocalPredictor::GetHistoryIfExists() const {
 969   Profile* profile = prerender_manager_->profile();
 970   if (!profile)
 971     return NULL;
 972   return HistoryServiceFactory::GetForProfileWithoutCreating(profile);
 973 }
 974
 975 void PrerenderLocalPredictor::Init() {
 976   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
 977   RecordEvent(EVENT_INIT_STARTED);
 978   Profile* profile = prerender_manager_->profile();
 979   if (!profile || DisableLocalPredictorBasedOnSyncAndConfiguration(profile)) {
 980     RecordEvent(EVENT_INIT_FAILED_UNENCRYPTED_SYNC_NOT_ENABLED);
 981     return;
 982   }
 983   HistoryService* history = GetHistoryIfExists();
 984   if (history) {
 985     CHECK(!is_visit_database_observer_);
 986     history->ScheduleDBTask(
 987         new GetVisitHistoryTask(this, kMaxVisitHistory),
 988         &history_db_consumer_);
 989     history->AddVisitDatabaseObserver(this);
 990     is_visit_database_observer_ = true;
 991   } else {
 992     RecordEvent(EVENT_INIT_FAILED_NO_HISTORY);
 993   }
 994 }
 995
 996 void PrerenderLocalPredictor::OnPLTEventForURL(const GURL& url,
 997                                                base::TimeDelta page_load_time) {
 998   scoped_ptr<PrerenderProperties> prerender;
 999   if (DoesPrerenderMatchPLTRecord(last_swapped_in_prerender_.get(),
1000                                   url, page_load_time)) {
1001     prerender.reset(last_swapped_in_prerender_.release());
1002   }
1003   if (DoesPrerenderMatchPLTRecord(current_prerender_.get(),
1004                                   url, page_load_time)) {
1005     prerender.reset(current_prerender_.release());
1006   }
1007   if (!prerender.get())
1008     return;
1009   if (IsPrerenderStillValid(prerender.get())) {
1010     UMA_HISTOGRAM_CUSTOM_TIMES("Prerender.SimulatedLocalBrowsingBaselinePLT",
1011                                page_load_time,
1012                                base::TimeDelta::FromMilliseconds(10),
1013                                base::TimeDelta::FromSeconds(60),
1014                                100);
1015
1016     base::TimeDelta prerender_age = GetCurrentTime() - prerender->start_time;
1017     if (prerender_age > page_load_time) {
1018       base::TimeDelta new_plt;
1019       if (prerender_age <  2 * page_load_time)
1020         new_plt = 2 * page_load_time - prerender_age;
1021       UMA_HISTOGRAM_CUSTOM_TIMES("Prerender.SimulatedLocalBrowsingPLT",
1022                                  new_plt,
1023                                  base::TimeDelta::FromMilliseconds(10),
1024                                  base::TimeDelta::FromSeconds(60),
1025                                  100);
1026     }
1027   }
1028 }
1029
1030 bool PrerenderLocalPredictor::IsPrerenderStillValid(
1031     PrerenderLocalPredictor::PrerenderProperties* prerender) const {
1032   return (prerender &&
1033           (prerender->start_time +
1034            base::TimeDelta::FromMilliseconds(GetMaxLocalPredictionTimeMs()))
1035           > GetCurrentTime());
1036 }
1037
1038 void PrerenderLocalPredictor::RecordEvent(
1039     PrerenderLocalPredictor::Event event) const {
1040   UMA_HISTOGRAM_ENUMERATION("Prerender.LocalPredictorEvent",
1041       event, PrerenderLocalPredictor::EVENT_MAX_VALUE);
1042 }
1043
1044 bool PrerenderLocalPredictor::DoesPrerenderMatchPLTRecord(
1045     PrerenderProperties* prerender,
1046     const GURL& url,
1047     base::TimeDelta plt) const {
1048   if (prerender && prerender->start_time < GetCurrentTime() - plt) {
1049     if (prerender->url.is_empty())
1050       RecordEvent(EVENT_ERROR_NO_PRERENDER_URL_FOR_PLT);
1051     return (prerender->url == url);
1052   } else {
1053     return false;
1054   }
1055 }
1056
1057 PrerenderLocalPredictor::PrerenderProperties*
1058 PrerenderLocalPredictor::GetIssuedPrerenderSlotForPriority(double priority) {
1059   int num_prerenders = GetLocalPredictorMaxConcurrentPrerenders();
1060   while (static_cast<int>(issued_prerenders_.size()) < num_prerenders)
1061     issued_prerenders_.push_back(new PrerenderProperties());
1062   PrerenderProperties* lowest_priority_prerender = NULL;
1063   for (int i = 0; i < static_cast<int>(issued_prerenders_.size()); i++) {
1064     PrerenderProperties* p = issued_prerenders_[i];
1065     DCHECK(p != NULL);
1066     if (!p->prerender_handle || !p->prerender_handle->IsPrerendering())
1067       return p;
1068     double decayed_priority = p->GetCurrentDecayedPriority();
1069     if (decayed_priority > priority)
1070       continue;
1071     if (lowest_priority_prerender == NULL ||
1072         lowest_priority_prerender->GetCurrentDecayedPriority() >
1073         decayed_priority) {
1074       lowest_priority_prerender = p;
1075     }
1076   }
1077   return lowest_priority_prerender;
1078 }
1079
1080 void PrerenderLocalPredictor::ContinuePrerenderCheck(
1081     scoped_ptr<CandidatePrerenderInfo> info) {
1082   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
1083   TIMING_HISTOGRAM("Prerender.LocalPredictorLoggedInLookupTime",
1084                    base::Time::Now() - info->start_time_);
1085   RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_STARTED);
1086   if (info->candidate_urls_.size() == 0) {
1087     RecordEvent(EVENT_NO_PRERENDER_CANDIDATES);
1088     return;
1089   }
1090   scoped_ptr<LocalPredictorURLInfo> url_info;
1091 #if defined(FULL_SAFE_BROWSING)
1092   scoped_refptr<SafeBrowsingDatabaseManager> sb_db_manager =
1093       g_browser_process->safe_browsing_service()->database_manager();
1094 #endif
1095   PrerenderProperties* prerender_properties = NULL;
1096
1097   for (int i = 0; i < static_cast<int>(info->candidate_urls_.size()); i++) {
1098     RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_EXAMINE_NEXT_URL);
1099     url_info.reset(new LocalPredictorURLInfo(info->candidate_urls_[i]));
1100     if (url_info->local_history_based) {
1101       if (SkipLocalPredictorLocalCandidates()) {
1102         url_info.reset(NULL);
1103         continue;
1104       }
1105       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_EXAMINE_NEXT_URL_LOCAL);
1106     }
1107     if (!url_info->local_history_based) {
1108       if (SkipLocalPredictorServiceCandidates()) {
1109         url_info.reset(NULL);
1110         continue;
1111       }
1112       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_EXAMINE_NEXT_URL_SERVICE);
1113     }
1114
1115     RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_EXAMINE_NEXT_URL_NOT_SKIPPED);
1116
1117     // We need to check whether we can issue a prerender for this URL.
1118     // We test a set of conditions. Each condition can either rule out
1119     // a prerender (in which case we reset url_info, so that it will not
1120     // be prerendered, and we continue, which means try the next candidate
1121     // URL), or it can be sufficient to issue the prerender without any
1122     // further checks (in which case we just break).
1123     // The order of the checks is critical, because it prescribes the logic
1124     // we use here to decide what to prerender.
1125     if (!url_info->url_lookup_success) {
1126       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_NO_URL);
1127       url_info.reset(NULL);
1128       continue;
1129     }
1130     prerender_properties =
1131         GetIssuedPrerenderSlotForPriority(url_info->priority);
1132     if (!prerender_properties) {
1133       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_PRIORITY_TOO_LOW);
1134       url_info.reset(NULL);
1135       continue;
1136     }
1137     if (!SkipLocalPredictorFragment() &&
1138         URLsIdenticalIgnoringFragments(info->source_url_.url,
1139                                        url_info->url)) {
1140       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_URLS_IDENTICAL_BUT_FRAGMENT);
1141       url_info.reset(NULL);
1142       continue;
1143     }
1144     if (!SkipLocalPredictorHTTPS() && url_info->url.SchemeIs("https")) {
1145       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_HTTPS);
1146       url_info.reset(NULL);
1147       continue;
1148     }
1149     if (IsRootPageURL(url_info->url)) {
1150       // For root pages, we assume that they are reasonably safe, and we
1151       // will just prerender them without any additional checks.
1152       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_ROOT_PAGE);
1153       break;
1154     }
1155     if (IsLogOutURL(url_info->url)) {
1156       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_LOGOUT_URL);
1157       url_info.reset(NULL);
1158       continue;
1159     }
1160     if (IsLogInURL(url_info->url)) {
1161       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_LOGIN_URL);
1162       url_info.reset(NULL);
1163       continue;
1164     }
1165 #if defined(FULL_SAFE_BROWSING)
1166     if (!SkipLocalPredictorWhitelist() &&
1167         sb_db_manager->CheckSideEffectFreeWhitelistUrl(url_info->url)) {
1168       // If a page is on the side-effect free whitelist, we will just prerender
1169       // it without any additional checks.
1170       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_ON_SIDE_EFFECT_FREE_WHITELIST);
1171       break;
1172     }
1173 #endif
1174     if (!SkipLocalPredictorServiceWhitelist() &&
1175         url_info->service_whitelist && url_info->service_whitelist_lookup_ok) {
1176       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_ON_SERVICE_WHITELIST);
1177       break;
1178     }
1179     if (!SkipLocalPredictorLoggedIn() &&
1180         !url_info->logged_in && url_info->logged_in_lookup_ok) {
1181       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_NOT_LOGGED_IN);
1182       break;
1183     }
1184     if (!SkipLocalPredictorDefaultNoPrerender()) {
1185       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_FALLTHROUGH_NOT_PRERENDERING);
1186       url_info.reset(NULL);
1187     } else {
1188       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_FALLTHROUGH_PRERENDERING);
1189     }
1190   }
1191   if (!url_info.get())
1192     return;
1193   RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_ISSUING_PRERENDER);
1194   DCHECK(prerender_properties != NULL);
1195   if (IsLocalPredictorPrerenderLaunchEnabled()) {
1196     IssuePrerender(info.Pass(), url_info.Pass(), prerender_properties);
1197   }
1198 }
1199
1200 void PrerenderLocalPredictor::IssuePrerender(
1201     scoped_ptr<CandidatePrerenderInfo> info,
1202     scoped_ptr<LocalPredictorURLInfo> url_info,
1203     PrerenderProperties* prerender_properties) {
1204   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
1205   URLID url_id = url_info->id;
1206   const GURL& url = url_info->url;
1207   double priority = url_info->priority;
1208   base::Time current_time = GetCurrentTime();
1209   RecordEvent(EVENT_ISSUING_PRERENDER);
1210
1211   // Issue the prerender and obtain a new handle.
1212   scoped_ptr<prerender::PrerenderHandle> new_prerender_handle(
1213       prerender_manager_->AddPrerenderFromLocalPredictor(
1214           url, info->session_storage_namespace_.get(), *(info->size_)));
1215
1216   // Check if this is a duplicate of an existing prerender. If yes, clean up
1217   // the new handle.
1218   for (int i = 0; i < static_cast<int>(issued_prerenders_.size()); i++) {
1219     PrerenderProperties* p = issued_prerenders_[i];
1220     DCHECK(p != NULL);
1221     if (new_prerender_handle &&
1222         new_prerender_handle->RepresentingSamePrerenderAs(
1223             p->prerender_handle.get())) {
1224       new_prerender_handle->OnCancel();
1225       new_prerender_handle.reset(NULL);
1226       RecordEvent(EVENT_ISSUE_PRERENDER_ALREADY_PRERENDERING);
1227       break;
1228     }
1229   }
1230
1231   if (new_prerender_handle.get()) {
1232     RecordEvent(EVENT_ISSUE_PRERENDER_NEW_PRERENDER);
1233     // The new prerender does not match any existing prerenders. Update
1234     // prerender_properties so that it reflects the new entry.
1235     prerender_properties->url_id = url_id;
1236     prerender_properties->url = url;
1237     prerender_properties->priority = priority;
1238     prerender_properties->start_time = current_time;
1239     prerender_properties->actual_start_time = current_time;
1240     prerender_properties->would_have_matched = false;
1241     prerender_properties->prerender_handle.swap(new_prerender_handle);
1242     // new_prerender_handle now represents the old previou prerender that we
1243     // are replacing. So we need to cancel it.
1244     if (new_prerender_handle) {
1245       new_prerender_handle->OnCancel();
1246       RecordEvent(EVENT_ISSUE_PRERENDER_CANCELLED_OLD_PRERENDER);
1247     }
1248   }
1249
1250   RecordEvent(EVENT_ADD_VISIT_PRERENDERING);
1251   if (current_prerender_.get() && current_prerender_->url_id == url_id) {
1252     RecordEvent(EVENT_ADD_VISIT_PRERENDERING_EXTENDED);
1253     if (priority > current_prerender_->priority)
1254       current_prerender_->priority = priority;
1255     // If the prerender already existed, we want to extend it.  However,
1256     // we do not want to set its start_time to the current time to
1257     // disadvantage PLT computations when the prerender is swapped in.
1258     // So we set the new start time to current_time - 10s (since the vast
1259     // majority of PLTs are < 10s), provided that is not before the actual
1260     // time the prerender was started (so as to not artificially advantage
1261     // the PLT computation).
1262     base::Time simulated_new_start_time =
1263         current_time - base::TimeDelta::FromSeconds(10);
1264     if (simulated_new_start_time > current_prerender_->start_time)
1265       current_prerender_->start_time = simulated_new_start_time;
1266   } else {
1267     current_prerender_.reset(
1268         new PrerenderProperties(url_id, url, priority, current_time));
1269   }
1270   current_prerender_->actual_start_time = current_time;
1271 }
1272
1273 void PrerenderLocalPredictor::OnTabHelperURLSeen(
1274     const GURL& url, WebContents* web_contents) {
1275   RecordEvent(EVENT_TAB_HELPER_URL_SEEN);
1276
1277   bool browser_navigate_initiated = false;
1278   const content::NavigationEntry* entry =
1279       web_contents->GetController().GetPendingEntry();
1280   if (entry) {
1281     base::string16 result;
1282     browser_navigate_initiated =
1283         entry->GetExtraData(kChromeNavigateExtraDataKey, &result);
1284   }
1285
1286   // If the namespace matches and the URL matches, we might be able to swap
1287   // in. However, the actual code initating the swapin is in the renderer
1288   // and is checking for other criteria (such as POSTs). There may
1289   // also be conditions when a swapin should happen but does not. By recording
1290   // the two previous events, we can keep an eye on the magnitude of the
1291   // discrepancy.
1292
1293   PrerenderProperties* best_matched_prerender = NULL;
1294   bool session_storage_namespace_matches = false;
1295   SessionStorageNamespace* tab_session_storage_namespace =
1296       web_contents->GetController().GetDefaultSessionStorageNamespace();
1297   for (int i = 0; i < static_cast<int>(issued_prerenders_.size()); i++) {
1298     PrerenderProperties* p = issued_prerenders_[i];
1299     DCHECK(p != NULL);
1300     if (!p->prerender_handle.get() ||
1301         !p->prerender_handle->Matches(url, NULL) ||
1302         p->would_have_matched) {
1303       continue;
1304     }
1305     if (!best_matched_prerender || !session_storage_namespace_matches) {
1306       best_matched_prerender = p;
1307       session_storage_namespace_matches =
1308           p->prerender_handle->Matches(url, tab_session_storage_namespace);
1309     }
1310   }
1311   if (best_matched_prerender) {
1312     RecordEvent(EVENT_TAB_HELPER_URL_SEEN_MATCH);
1313     if (entry)
1314       RecordEvent(EVENT_TAB_HELPER_URL_SEEN_MATCH_ENTRY);
1315     if (browser_navigate_initiated)
1316       RecordEvent(EVENT_TAB_HELPER_URL_SEEN_MATCH_BROWSER_NAVIGATE);
1317     best_matched_prerender->would_have_matched = true;
1318     if (session_storage_namespace_matches) {
1319       RecordEvent(EVENT_TAB_HELPER_URL_SEEN_NAMESPACE_MATCH);
1320       if (entry)
1321         RecordEvent(EVENT_TAB_HELPER_URL_SEEN_NAMESPACE_MATCH_ENTRY);
1322       if (browser_navigate_initiated)
1323         RecordEvent(EVENT_TAB_HELPER_URL_SEEN_NAMESPACE_MATCH_BROWSER_NAVIGATE);
1324     } else {
1325       SessionStorageNamespace* prerender_session_storage_namespace =
1326           best_matched_prerender->prerender_handle->
1327           GetSessionStorageNamespace();
1328       if (!prerender_session_storage_namespace) {
1329         RecordEvent(EVENT_TAB_HELPER_URL_SEEN_NAMESPACE_MISMATCH_NO_NAMESPACE);
1330       } else {
1331         RecordEvent(EVENT_TAB_HELPER_URL_SEEN_NAMESPACE_MISMATCH_MERGE_ISSUED);
1332         prerender_session_storage_namespace->Merge(
1333             false,
1334             best_matched_prerender->prerender_handle->GetChildId(),
1335             tab_session_storage_namespace,
1336             base::Bind(&PrerenderLocalPredictor::ProcessNamespaceMergeResult,
1337                        weak_factory_.GetWeakPtr()));
1338       }
1339     }
1340   }
1341 }
1342
1343 void PrerenderLocalPredictor::ProcessNamespaceMergeResult(
1344     content::SessionStorageNamespace::MergeResult result) {
1345   RecordEvent(EVENT_NAMESPACE_MISMATCH_MERGE_RESULT_RECEIVED);
1346   switch (result) {
1347     case content::SessionStorageNamespace::MERGE_RESULT_NAMESPACE_NOT_FOUND:
1348       RecordEvent(EVENT_NAMESPACE_MISMATCH_MERGE_RESULT_NAMESPACE_NOT_FOUND);
1349       break;
1350     case content::SessionStorageNamespace::MERGE_RESULT_NAMESPACE_NOT_ALIAS:
1351       RecordEvent(EVENT_NAMESPACE_MISMATCH_MERGE_RESULT_NAMESPACE_NOT_ALIAS);
1352       break;
1353     case content::SessionStorageNamespace::MERGE_RESULT_NOT_LOGGING:
1354       RecordEvent(EVENT_NAMESPACE_MISMATCH_MERGE_RESULT_NOT_LOGGING);
1355       break;
1356     case content::SessionStorageNamespace::MERGE_RESULT_NO_TRANSACTIONS:
1357       RecordEvent(EVENT_NAMESPACE_MISMATCH_MERGE_RESULT_NO_TRANSACTIONS);
1358       break;
1359     case content::SessionStorageNamespace::MERGE_RESULT_TOO_MANY_TRANSACTIONS:
1360       RecordEvent(EVENT_NAMESPACE_MISMATCH_MERGE_RESULT_TOO_MANY_TRANSACTIONS);
1361       break;
1362     case content::SessionStorageNamespace::MERGE_RESULT_NOT_MERGEABLE:
1363       RecordEvent(EVENT_NAMESPACE_MISMATCH_MERGE_RESULT_NOT_MERGEABLE);
1364       break;
1365     case content::SessionStorageNamespace::MERGE_RESULT_MERGEABLE:
1366       RecordEvent(EVENT_NAMESPACE_MISMATCH_MERGE_RESULT_MERGEABLE);
1367       break;
1368     default:
1369       NOTREACHED();
1370   }
1371 }
1372
1373 }  // namespace prerender