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