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 "content/public/common/page_transition_types.h"
  43 #include "crypto/secure_hash.h"
  44 #include "grit/browser_resources.h"
  45 #include "net/base/escape.h"
  46 #include "net/base/load_flags.h"
  47 #include "net/url_request/url_fetcher.h"
  48 #include "ui/base/resource/resource_bundle.h"
  49 #include "url/url_canon.h"
  50
  51 using base::DictionaryValue;
  52 using base::ListValue;
  53 using base::Value;
  54 using content::BrowserThread;
  55 using content::PageTransition;
  56 using content::RenderFrameHost;
  57 using content::SessionStorageNamespace;
  58 using content::WebContents;
  59 using history::URLID;
  60 using net::URLFetcher;
  61 using predictors::LoggedInPredictorTable;
  62 using std::string;
  63 using std::vector;
  64
  65 namespace prerender {
  66
  67 namespace {
  68
  69 static const size_t kURLHashSize = 5;
  70 static const int kNumPrerenderCandidates = 5;
  71 static const int kInvalidProcessId = -1;
  72 static const int kInvalidFrameId = -1;
  73 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 & content::PAGE_TRANSITION_FORWARD_BACK) != 0;
 253 }
 254
 255 bool IsHomePage(PageTransition transition) {
 256   return (transition & content::PAGE_TRANSITION_HOME_PAGE) != 0;
 257 }
 258
 259 bool IsIntermediateRedirect(PageTransition transition) {
 260   return (transition & content::PAGE_TRANSITION_CHAIN_END) == 0;
 261 }
 262
 263 bool IsFormSubmit(PageTransition transition) {
 264   return PageTransitionCoreTypeIs(transition,
 265                                   content::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_visit_database_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_visit_database_observer_) {
 587     HistoryService* history = GetHistoryIfExists();
 588     CHECK(history);
 589     history->RemoveVisitDatabaseObserver(this);
 590     is_visit_database_observer_ = false;
 591   }
 592 }
 593
 594 void PrerenderLocalPredictor::OnAddVisit(const history::BriefVisitInfo& info) {
 595   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
 596   RecordEvent(EVENT_ADD_VISIT);
 597   if (!visit_history_.get())
 598     return;
 599   visit_history_->push_back(info);
 600   if (static_cast<int>(visit_history_->size()) > kVisitHistoryPruneThreshold) {
 601     visit_history_->erase(visit_history_->begin(),
 602                           visit_history_->begin() + kVisitHistoryPruneAmount);
 603   }
 604   RecordEvent(EVENT_ADD_VISIT_INITIALIZED);
 605   if (current_prerender_.get() &&
 606       current_prerender_->url_id == info.url_id &&
 607       IsPrerenderStillValid(current_prerender_.get())) {
 608     UMA_HISTOGRAM_CUSTOM_TIMES(
 609         "Prerender.LocalPredictorTimeUntilUsed",
 610         GetCurrentTime() - current_prerender_->actual_start_time,
 611         base::TimeDelta::FromMilliseconds(10),
 612         base::TimeDelta::FromMilliseconds(GetMaxLocalPredictionTimeMs()),
 613         50);
 614     last_swapped_in_prerender_.reset(current_prerender_.release());
 615     RecordEvent(EVENT_ADD_VISIT_PRERENDER_IDENTIFIED);
 616   }
 617   if (ShouldExcludeTransitionForPrediction(info.transition))
 618     return;
 619   RecordEvent(EVENT_ADD_VISIT_RELEVANT_TRANSITION);
 620   base::TimeDelta max_age =
 621       base::TimeDelta::FromMilliseconds(GetMaxLocalPredictionTimeMs());
 622   base::TimeDelta min_age =
 623       base::TimeDelta::FromMilliseconds(kMinLocalPredictionTimeMs);
 624   std::set<URLID> next_urls_currently_found;
 625   std::map<URLID, int> next_urls_num_found;
 626   int num_occurrences_of_current_visit = 0;
 627   base::Time last_visited;
 628   scoped_ptr<CandidatePrerenderInfo> lookup_info(
 629       new CandidatePrerenderInfo(info.url_id));
 630   const vector<history::BriefVisitInfo>& visits = *(visit_history_.get());
 631   for (int i = 0; i < static_cast<int>(visits.size()); i++) {
 632     if (!ShouldExcludeTransitionForPrediction(visits[i].transition)) {
 633       if (visits[i].url_id == info.url_id) {
 634         last_visited = visits[i].time;
 635         num_occurrences_of_current_visit++;
 636         next_urls_currently_found.clear();
 637         continue;
 638       }
 639       if (!last_visited.is_null() &&
 640           last_visited > visits[i].time - max_age &&
 641           last_visited < visits[i].time - min_age) {
 642         if (!IsFormSubmit(visits[i].transition))
 643           next_urls_currently_found.insert(visits[i].url_id);
 644       }
 645     }
 646     if (i == static_cast<int>(visits.size()) - 1 ||
 647         visits[i+1].url_id == info.url_id) {
 648       for (std::set<URLID>::iterator it = next_urls_currently_found.begin();
 649            it != next_urls_currently_found.end();
 650            ++it) {
 651         std::pair<std::map<URLID, int>::iterator, bool> insert_ret =
 652             next_urls_num_found.insert(std::pair<URLID, int>(*it, 0));
 653         std::map<URLID, int>::iterator num_found_it = insert_ret.first;
 654         num_found_it->second++;
 655       }
 656     }
 657   }
 658
 659   if (num_occurrences_of_current_visit > 1) {
 660     RecordEvent(EVENT_ADD_VISIT_RELEVANT_TRANSITION_REPEAT_URL);
 661   } else {
 662     RecordEvent(EVENT_ADD_VISIT_RELEVANT_TRANSITION_NEW_URL);
 663   }
 664
 665   for (std::map<URLID, int>::const_iterator it = next_urls_num_found.begin();
 666        it != next_urls_num_found.end();
 667        ++it) {
 668     // Only consider a candidate next page for prerendering if it was viewed
 669     // at least twice, and at least 10% of the time.
 670     if (num_occurrences_of_current_visit > 0 &&
 671         it->second > 1 &&
 672         it->second * 10 >= num_occurrences_of_current_visit) {
 673       RecordEvent(EVENT_ADD_VISIT_IDENTIFIED_PRERENDER_CANDIDATE);
 674       double priority = static_cast<double>(it->second) /
 675           static_cast<double>(num_occurrences_of_current_visit);
 676       lookup_info->MaybeAddCandidateURLFromLocalData(it->first, priority);
 677     }
 678   }
 679
 680   RecordEvent(EVENT_START_URL_LOOKUP);
 681   HistoryService* history = GetHistoryIfExists();
 682   if (history) {
 683     RecordEvent(EVENT_GOT_HISTORY_ISSUING_LOOKUP);
 684     CandidatePrerenderInfo* lookup_info_ptr = lookup_info.get();
 685     history->ScheduleDBTask(
 686         scoped_ptr<history::HistoryDBTask>(
 687             new GetURLForURLIDTask(
 688                 lookup_info_ptr,
 689                 base::Bind(&PrerenderLocalPredictor::OnLookupURL,
 690                            base::Unretained(this),
 691                            base::Passed(&lookup_info)))),
 692         &history_db_tracker_);
 693   }
 694 }
 695
 696 void PrerenderLocalPredictor::OnLookupURL(
 697     scoped_ptr<CandidatePrerenderInfo> info) {
 698   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
 699
 700   RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT);
 701
 702   if (!info->source_url_.url_lookup_success) {
 703     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_FAILED);
 704     return;
 705   }
 706
 707   if (prefetch_list_->MarkURLSeen(info->source_url_.url,
 708                                   PrefetchList::SEEN_HISTORY)) {
 709     RecordEvent(EVENT_PREFETCH_LIST_SEEN_HISTORY);
 710   }
 711
 712   if (info->candidate_urls_.size() > 0 &&
 713       info->candidate_urls_[0].url_lookup_success) {
 714     LogCandidateURLStats(info->candidate_urls_[0].url);
 715   }
 716
 717   WebContents* source_web_contents = NULL;
 718   bool multiple_source_web_contents_candidates = false;
 719
 720 #if !defined(OS_ANDROID)
 721   // We need to figure out what tab launched the prerender. We do this by
 722   // comparing URLs. This may not always work: the URL may occur in two
 723   // tabs, and we pick the wrong one, or the tab we should have picked
 724   // may have navigated elsewhere. Hopefully, this doesn't happen too often,
 725   // so we ignore these cases for now.
 726   // TODO(tburkard): Reconsider this, potentially measure it, and fix this
 727   // in the future.
 728   for (TabContentsIterator it; !it.done(); it.Next()) {
 729     if (it->GetURL() == info->source_url_.url) {
 730       if (!source_web_contents)
 731         source_web_contents = *it;
 732       else
 733         multiple_source_web_contents_candidates = true;
 734     }
 735   }
 736 #endif
 737
 738   if (!source_web_contents) {
 739     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_NO_SOURCE_WEBCONTENTS_FOUND);
 740     return;
 741   }
 742
 743   if (multiple_source_web_contents_candidates)
 744     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_MULTIPLE_SOURCE_WEBCONTENTS_FOUND);
 745
 746   info->session_storage_namespace_ =
 747       source_web_contents->GetController().GetDefaultSessionStorageNamespace();
 748   RenderFrameHost* rfh = source_web_contents->GetMainFrame();
 749   info->render_process_id_ = rfh->GetProcess()->GetID();
 750   info->render_frame_id_ = rfh->GetRoutingID();
 751
 752   gfx::Rect container_bounds = source_web_contents->GetContainerBounds();
 753   info->size_.reset(new gfx::Size(container_bounds.size()));
 754
 755   RecordEvent(EVENT_PRERENDER_URL_LOOKUP_SUCCESS);
 756
 757   DoPrerenderServiceCheck(info.Pass());
 758 }
 759
 760 void PrerenderLocalPredictor::DoPrerenderServiceCheck(
 761     scoped_ptr<CandidatePrerenderInfo> info) {
 762   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
 763   if (!ShouldQueryPrerenderService(prerender_manager_->profile())) {
 764     RecordEvent(EVENT_PRERENDER_SERVICE_DISABLED);
 765     DoLoggedInLookup(info.Pass());
 766     return;
 767   }
 768   /*
 769     Create a JSON request.
 770     Here is a sample request:
 771     { "prerender_request": {
 772         "version": 1,
 773         "behavior_id": 6,
 774         "hint_request": {
 775           "browse_history": [
 776             { "url": "http://www.cnn.com/"
 777             }
 778           ]
 779         },
 780         "candidate_check_request": {
 781           "candidates": [
 782             { "url": "http://www.cnn.com/sports/"
 783             },
 784             { "url": "http://www.cnn.com/politics/"
 785             }
 786           ]
 787         }
 788       }
 789     }
 790   */
 791   base::DictionaryValue json_data;
 792   base::DictionaryValue* req = new base::DictionaryValue();
 793   req->SetInteger("version", 1);
 794   req->SetInteger("behavior_id", GetPrerenderServiceBehaviorID());
 795   if (ShouldQueryPrerenderServiceForCurrentURL() &&
 796       info->source_url_.url_lookup_success) {
 797     base::ListValue* browse_history = new base::ListValue();
 798     base::DictionaryValue* browse_item = new base::DictionaryValue();
 799     browse_item->SetString("url", info->source_url_.url.spec());
 800     browse_history->Append(browse_item);
 801     base::DictionaryValue* hint_request = new base::DictionaryValue();
 802     hint_request->Set("browse_history", browse_history);
 803     req->Set("hint_request", hint_request);
 804   }
 805   int num_candidate_urls = 0;
 806   for (int i = 0; i < static_cast<int>(info->candidate_urls_.size()); i++) {
 807     if (info->candidate_urls_[i].url_lookup_success)
 808       num_candidate_urls++;
 809   }
 810   if (ShouldQueryPrerenderServiceForCandidateURLs() &&
 811       num_candidate_urls > 0) {
 812     base::ListValue* candidates = new base::ListValue();
 813     base::DictionaryValue* candidate;
 814     for (int i = 0; i < static_cast<int>(info->candidate_urls_.size()); i++) {
 815       if (info->candidate_urls_[i].url_lookup_success) {
 816         candidate = new base::DictionaryValue();
 817         candidate->SetString("url", info->candidate_urls_[i].url.spec());
 818         candidates->Append(candidate);
 819       }
 820     }
 821     base::DictionaryValue* candidate_check_request =
 822         new base::DictionaryValue();
 823     candidate_check_request->Set("candidates", candidates);
 824     req->Set("candidate_check_request", candidate_check_request);
 825   }
 826   json_data.Set("prerender_request", req);
 827   string request_string;
 828   base::JSONWriter::Write(&json_data, &request_string);
 829   GURL fetch_url(GetPrerenderServiceURLPrefix() +
 830                  net::EscapeQueryParamValue(request_string, false));
 831   net::URLFetcher* fetcher = net::URLFetcher::Create(
 832       0,
 833       fetch_url,
 834       URLFetcher::GET, this);
 835   fetcher->SetRequestContext(
 836       prerender_manager_->profile()->GetRequestContext());
 837   fetcher->SetLoadFlags(net::LOAD_DISABLE_CACHE |
 838                         net::LOAD_DO_NOT_SAVE_COOKIES |
 839                         net::LOAD_DO_NOT_SEND_COOKIES);
 840   fetcher->AddExtraRequestHeader("Pragma: no-cache");
 841   info->start_time_ = base::Time::Now();
 842   outstanding_prerender_service_requests_.insert(
 843       std::make_pair(fetcher, info.release()));
 844   base::MessageLoop::current()->PostDelayedTask(
 845       FROM_HERE,
 846       base::Bind(&PrerenderLocalPredictor::MaybeCancelURLFetcher,
 847                  weak_factory_.GetWeakPtr(), fetcher),
 848       base::TimeDelta::FromMilliseconds(GetPrerenderServiceFetchTimeoutMs()));
 849   RecordEvent(EVENT_PRERENDER_SERVICE_ISSUED_LOOKUP);
 850   fetcher->Start();
 851 }
 852
 853 void PrerenderLocalPredictor::MaybeCancelURLFetcher(net::URLFetcher* fetcher) {
 854   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
 855   OutstandingFetchers::iterator it =
 856       outstanding_prerender_service_requests_.find(fetcher);
 857   if (it == outstanding_prerender_service_requests_.end())
 858     return;
 859   delete it->first;
 860   scoped_ptr<CandidatePrerenderInfo> info(it->second);
 861   outstanding_prerender_service_requests_.erase(it);
 862   RecordEvent(EVENT_PRERENDER_SERVICE_LOOKUP_TIMED_OUT);
 863   DoLoggedInLookup(info.Pass());
 864 }
 865
 866 bool PrerenderLocalPredictor::ApplyParsedPrerenderServiceResponse(
 867     base::DictionaryValue* dict,
 868     CandidatePrerenderInfo* info,
 869     bool* hinting_timed_out,
 870     bool* hinting_url_lookup_timed_out,
 871     bool* candidate_url_lookup_timed_out) {
 872   /*
 873     Process the response to the request.
 874     Here is a sample response to illustrate the format.
 875     {
 876       "prerender_response": {
 877         "behavior_id": 6,
 878         "hint_response": {
 879           "hinting_timed_out": 0,
 880           "candidates": [
 881             { "url": "http://www.cnn.com/story-1",
 882               "in_index": 1,
 883               "likelihood": 0.60,
 884               "in_index_timed_out": 0
 885             },
 886             { "url": "http://www.cnn.com/story-2",
 887               "in_index": 1,
 888               "likelihood": 0.30,
 889               "in_index_timed_out": 0
 890             }
 891           ]
 892         },
 893         "candidate_check_response": {
 894           "candidates": [
 895             { "url": "http://www.cnn.com/sports/",
 896               "in_index": 1,
 897               "in_index_timed_out": 0
 898             },
 899             { "url": "http://www.cnn.com/politics/",
 900               "in_index": 0,
 901               "in_index_timed_out": "1"
 902             }
 903           ]
 904         }
 905       }
 906     }
 907   */
 908   base::ListValue* list = NULL;
 909   int int_value;
 910   if (!dict->GetInteger("prerender_response.behavior_id", &int_value) ||
 911       int_value != GetPrerenderServiceBehaviorID()) {
 912     return false;
 913   }
 914   if (!dict->GetList("prerender_response.candidate_check_response.candidates",
 915                      &list)) {
 916     if (ShouldQueryPrerenderServiceForCandidateURLs()) {
 917       for (int i = 0; i < static_cast<int>(info->candidate_urls_.size()); i++) {
 918         if (info->candidate_urls_[i].url_lookup_success)
 919           return false;
 920       }
 921     }
 922   } else {
 923     for (size_t i = 0; i < list->GetSize(); i++) {
 924       base::DictionaryValue* d;
 925       if (!list->GetDictionary(i, &d))
 926         return false;
 927       string url_string;
 928       if (!d->GetString("url", &url_string) || !GURL(url_string).is_valid())
 929         return false;
 930       GURL url(url_string);
 931       int in_index_timed_out = 0;
 932       int in_index = 0;
 933       if ((!d->GetInteger("in_index_timed_out", &in_index_timed_out) ||
 934            in_index_timed_out != 1) &&
 935           !d->GetInteger("in_index", &in_index)) {
 936         return false;
 937       }
 938       if (in_index < 0 || in_index > 1 ||
 939           in_index_timed_out < 0 || in_index_timed_out > 1) {
 940         return false;
 941       }
 942       if (in_index_timed_out == 1)
 943         *candidate_url_lookup_timed_out = true;
 944       for (size_t j = 0; j < info->candidate_urls_.size(); j++) {
 945         if (info->candidate_urls_[j].url == url) {
 946           info->candidate_urls_[j].service_whitelist_reported = true;
 947           info->candidate_urls_[j].service_whitelist = (in_index == 1);
 948           info->candidate_urls_[j].service_whitelist_lookup_ok =
 949               ((1 - in_index_timed_out) == 1);
 950         }
 951       }
 952     }
 953     for (size_t i = 0; i < info->candidate_urls_.size(); i++) {
 954       if (info->candidate_urls_[i].url_lookup_success &&
 955           !info->candidate_urls_[i].service_whitelist_reported) {
 956         return false;
 957       }
 958     }
 959   }
 960
 961   if (ShouldQueryPrerenderServiceForCurrentURL() &&
 962       info->source_url_.url_lookup_success) {
 963     list = NULL;
 964     if (dict->GetInteger("prerender_response.hint_response.hinting_timed_out",
 965                          &int_value) &&
 966         int_value == 1) {
 967       *hinting_timed_out = true;
 968     } else if (!dict->GetList("prerender_response.hint_response.candidates",
 969                               &list)) {
 970       return false;
 971     } else {
 972       for (int i = 0; i < static_cast<int>(list->GetSize()); i++) {
 973         base::DictionaryValue* d;
 974         if (!list->GetDictionary(i, &d))
 975           return false;
 976         string url;
 977         if (!d->GetString("url", &url) || !GURL(url).is_valid())
 978           return false;
 979         double priority;
 980         if (!d->GetDouble("likelihood", &priority) || priority < 0.0 ||
 981             priority > 1.0) {
 982           return false;
 983         }
 984         int in_index_timed_out = 0;
 985         int in_index = 0;
 986         if ((!d->GetInteger("in_index_timed_out", &in_index_timed_out) ||
 987              in_index_timed_out != 1) &&
 988             !d->GetInteger("in_index", &in_index)) {
 989           return false;
 990         }
 991         if (in_index < 0 || in_index > 1 || in_index_timed_out < 0 ||
 992             in_index_timed_out > 1) {
 993           return false;
 994         }
 995         if (in_index_timed_out == 1)
 996           *hinting_url_lookup_timed_out = true;
 997         info->MaybeAddCandidateURLFromService(GURL(url),
 998                                               priority,
 999                                               in_index == 1,
1000                                               !in_index_timed_out);
1001       }
1002       if (list->GetSize() > 0)
1003         RecordEvent(EVENT_PRERENDER_SERVICE_RETURNED_HINTING_CANDIDATES);
1004     }
1005   }
1006
1007   return true;
1008 }
1009
1010 void PrerenderLocalPredictor::OnURLFetchComplete(
1011     const net::URLFetcher* source) {
1012   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
1013   RecordEvent(EVENT_PRERENDER_SERVICE_RECEIVED_RESULT);
1014   net::URLFetcher* fetcher = const_cast<net::URLFetcher*>(source);
1015   OutstandingFetchers::iterator it =
1016       outstanding_prerender_service_requests_.find(fetcher);
1017   if (it == outstanding_prerender_service_requests_.end()) {
1018     RecordEvent(EVENT_PRERENDER_SERVICE_NO_RECORD_FOR_RESULT);
1019     return;
1020   }
1021   scoped_ptr<CandidatePrerenderInfo> info(it->second);
1022   outstanding_prerender_service_requests_.erase(it);
1023   TIMING_HISTOGRAM("Prerender.LocalPredictorServiceLookupTime",
1024                    base::Time::Now() - info->start_time_);
1025   string result;
1026   fetcher->GetResponseAsString(&result);
1027   scoped_ptr<base::Value> root;
1028   root.reset(base::JSONReader::Read(result));
1029   bool hinting_timed_out = false;
1030   bool hinting_url_lookup_timed_out = false;
1031   bool candidate_url_lookup_timed_out = false;
1032   if (!root.get() || !root->IsType(base::Value::TYPE_DICTIONARY)) {
1033     RecordEvent(EVENT_PRERENDER_SERVICE_PARSE_ERROR_INCORRECT_JSON);
1034   } else {
1035     if (ApplyParsedPrerenderServiceResponse(
1036             static_cast<base::DictionaryValue*>(root.get()),
1037             info.get(),
1038             &hinting_timed_out,
1039             &hinting_url_lookup_timed_out,
1040             &candidate_url_lookup_timed_out)) {
1041       // We finished parsing the result, and found no errors.
1042       RecordEvent(EVENT_PRERENDER_SERVICE_PARSED_CORRECTLY);
1043       if (hinting_timed_out)
1044         RecordEvent(EVENT_PRERENDER_SERVICE_HINTING_TIMED_OUT);
1045       if (hinting_url_lookup_timed_out)
1046         RecordEvent(EVENT_PRERENDER_SERVICE_HINTING_URL_LOOKUP_TIMED_OUT);
1047       if (candidate_url_lookup_timed_out)
1048         RecordEvent(EVENT_PRERENDER_SERVICE_CANDIDATE_URL_LOOKUP_TIMED_OUT);
1049       DoLoggedInLookup(info.Pass());
1050       return;
1051     }
1052   }
1053
1054   // If we did not return earlier, an error happened during parsing.
1055   // Record this, and proceed.
1056   RecordEvent(EVENT_PRERENDER_SERVICE_PARSE_ERROR);
1057   DoLoggedInLookup(info.Pass());
1058 }
1059
1060 void PrerenderLocalPredictor:: DoLoggedInLookup(
1061     scoped_ptr<CandidatePrerenderInfo> info) {
1062   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
1063   scoped_refptr<LoggedInPredictorTable> logged_in_table =
1064       prerender_manager_->logged_in_predictor_table();
1065
1066   if (!logged_in_table.get()) {
1067     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_NO_LOGGED_IN_TABLE_FOUND);
1068     return;
1069   }
1070
1071   RecordEvent(EVENT_PRERENDER_URL_LOOKUP_ISSUING_LOGGED_IN_LOOKUP);
1072
1073   info->start_time_ = base::Time::Now();
1074
1075   CandidatePrerenderInfo* info_ptr = info.get();
1076   BrowserThread::PostTaskAndReply(
1077       BrowserThread::DB, FROM_HERE,
1078       base::Bind(&LookupLoggedInStatesOnDBThread,
1079                  logged_in_table,
1080                  info_ptr),
1081       base::Bind(&PrerenderLocalPredictor::ContinuePrerenderCheck,
1082                  weak_factory_.GetWeakPtr(),
1083                  base::Passed(&info)));
1084 }
1085
1086 void PrerenderLocalPredictor::LogCandidateURLStats(const GURL& url) const {
1087   if (url_whitelist_.count(GetInt64URLHashForURL(url)) > 0) {
1088     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_ON_WHITELIST);
1089     if (IsRootPageURL(url))
1090       RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_ON_WHITELIST_ROOT_PAGE);
1091   }
1092   if (IsRootPageURL(url))
1093     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_ROOT_PAGE);
1094   if (IsExtendedRootURL(url))
1095     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_EXTENDED_ROOT_PAGE);
1096   if (IsRootPageURL(url) && url.SchemeIs("http"))
1097     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_ROOT_PAGE_HTTP);
1098   if (url.SchemeIs("http"))
1099     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_IS_HTTP);
1100   if (url.has_query())
1101     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_HAS_QUERY_STRING);
1102   if (IsLogOutURL(url))
1103     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_CONTAINS_LOGOUT);
1104   if (IsLogInURL(url))
1105     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT_CONTAINS_LOGIN);
1106 }
1107
1108 void PrerenderLocalPredictor::OnGetInitialVisitHistory(
1109     scoped_ptr<vector<history::BriefVisitInfo> > visit_history) {
1110   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
1111   DCHECK(!visit_history_.get());
1112   RecordEvent(EVENT_INIT_SUCCEEDED);
1113   // Since the visit history has descending timestamps, we must reverse it.
1114   visit_history_.reset(new vector<history::BriefVisitInfo>(
1115       visit_history->rbegin(), visit_history->rend()));
1116 }
1117
1118 HistoryService* PrerenderLocalPredictor::GetHistoryIfExists() const {
1119   Profile* profile = prerender_manager_->profile();
1120   if (!profile)
1121     return NULL;
1122   return HistoryServiceFactory::GetForProfileWithoutCreating(profile);
1123 }
1124
1125 void PrerenderLocalPredictor::Init() {
1126   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
1127   RecordEvent(EVENT_INIT_STARTED);
1128   Profile* profile = prerender_manager_->profile();
1129   if (!profile || DisableLocalPredictorBasedOnSyncAndConfiguration(profile)) {
1130     RecordEvent(EVENT_INIT_FAILED_UNENCRYPTED_SYNC_NOT_ENABLED);
1131     return;
1132   }
1133   HistoryService* history = GetHistoryIfExists();
1134   if (history) {
1135     CHECK(!is_visit_database_observer_);
1136     history->ScheduleDBTask(
1137         scoped_ptr<history::HistoryDBTask>(
1138             new GetVisitHistoryTask(this, kMaxVisitHistory)),
1139         &history_db_tracker_);
1140     history->AddVisitDatabaseObserver(this);
1141     is_visit_database_observer_ = true;
1142   } else {
1143     RecordEvent(EVENT_INIT_FAILED_NO_HISTORY);
1144   }
1145 }
1146
1147 void PrerenderLocalPredictor::OnPLTEventForURL(const GURL& url,
1148                                                base::TimeDelta page_load_time) {
1149   if (prefetch_list_->MarkPLTSeen(url, page_load_time)) {
1150     UMA_HISTOGRAM_CUSTOM_TIMES("Prerender.LocalPredictorPrefetchMatchPLT",
1151                                page_load_time,
1152                                base::TimeDelta::FromMilliseconds(10),
1153                                base::TimeDelta::FromSeconds(60),
1154                                100);
1155   }
1156
1157   scoped_ptr<PrerenderProperties> prerender;
1158   if (DoesPrerenderMatchPLTRecord(last_swapped_in_prerender_.get(),
1159                                   url, page_load_time)) {
1160     prerender.reset(last_swapped_in_prerender_.release());
1161   }
1162   if (DoesPrerenderMatchPLTRecord(current_prerender_.get(),
1163                                   url, page_load_time)) {
1164     prerender.reset(current_prerender_.release());
1165   }
1166   if (!prerender.get())
1167     return;
1168   if (IsPrerenderStillValid(prerender.get())) {
1169     UMA_HISTOGRAM_CUSTOM_TIMES("Prerender.SimulatedLocalBrowsingBaselinePLT",
1170                                page_load_time,
1171                                base::TimeDelta::FromMilliseconds(10),
1172                                base::TimeDelta::FromSeconds(60),
1173                                100);
1174
1175     base::TimeDelta prerender_age = GetCurrentTime() - prerender->start_time;
1176     if (prerender_age > page_load_time) {
1177       base::TimeDelta new_plt;
1178       if (prerender_age <  2 * page_load_time)
1179         new_plt = 2 * page_load_time - prerender_age;
1180       UMA_HISTOGRAM_CUSTOM_TIMES("Prerender.SimulatedLocalBrowsingPLT",
1181                                  new_plt,
1182                                  base::TimeDelta::FromMilliseconds(10),
1183                                  base::TimeDelta::FromSeconds(60),
1184                                  100);
1185     }
1186   }
1187 }
1188
1189 bool PrerenderLocalPredictor::IsPrerenderStillValid(
1190     PrerenderLocalPredictor::PrerenderProperties* prerender) const {
1191   return (prerender &&
1192           (prerender->start_time +
1193            base::TimeDelta::FromMilliseconds(GetMaxLocalPredictionTimeMs()))
1194           > GetCurrentTime());
1195 }
1196
1197 void PrerenderLocalPredictor::RecordEvent(
1198     PrerenderLocalPredictor::Event event) const {
1199   UMA_HISTOGRAM_ENUMERATION("Prerender.LocalPredictorEvent",
1200       event, PrerenderLocalPredictor::EVENT_MAX_VALUE);
1201 }
1202
1203 bool PrerenderLocalPredictor::DoesPrerenderMatchPLTRecord(
1204     PrerenderProperties* prerender,
1205     const GURL& url,
1206     base::TimeDelta plt) const {
1207   if (prerender && prerender->start_time < GetCurrentTime() - plt) {
1208     if (prerender->url.is_empty())
1209       RecordEvent(EVENT_ERROR_NO_PRERENDER_URL_FOR_PLT);
1210     return (prerender->url == url);
1211   } else {
1212     return false;
1213   }
1214 }
1215
1216 PrerenderLocalPredictor::PrerenderProperties*
1217 PrerenderLocalPredictor::GetIssuedPrerenderSlotForPriority(const GURL& url,
1218                                                            double priority) {
1219   int num_prerenders = GetLocalPredictorMaxConcurrentPrerenders();
1220   while (static_cast<int>(issued_prerenders_.size()) < num_prerenders)
1221     issued_prerenders_.push_back(new PrerenderProperties());
1222   // First, check if we already have a prerender for the same URL issued.
1223   // If yes, we don't want to prerender this URL again, so we return NULL
1224   // (on matching slot found).
1225   for (int i = 0; i < static_cast<int>(issued_prerenders_.size()); i++) {
1226     PrerenderProperties* p = issued_prerenders_[i];
1227     DCHECK(p != NULL);
1228     if (p->prerender_handle && p->prerender_handle->IsPrerendering() &&
1229         p->prerender_handle->Matches(url, NULL)) {
1230       return NULL;
1231     }
1232   }
1233   // Otherwise, let's see if there are any empty slots. If yes, return the first
1234   // one we find. Otherwise, if the lowest priority prerender has a lower
1235   // priority than the page we want to prerender, use its slot.
1236   PrerenderProperties* lowest_priority_prerender = NULL;
1237   for (int i = 0; i < static_cast<int>(issued_prerenders_.size()); i++) {
1238     PrerenderProperties* p = issued_prerenders_[i];
1239     DCHECK(p != NULL);
1240     if (!p->prerender_handle || !p->prerender_handle->IsPrerendering())
1241       return p;
1242     double decayed_priority = p->GetCurrentDecayedPriority();
1243     if (decayed_priority > priority)
1244       continue;
1245     if (lowest_priority_prerender == NULL ||
1246         lowest_priority_prerender->GetCurrentDecayedPriority() >
1247         decayed_priority) {
1248       lowest_priority_prerender = p;
1249     }
1250   }
1251   return lowest_priority_prerender;
1252 }
1253
1254 void PrerenderLocalPredictor::ContinuePrerenderCheck(
1255     scoped_ptr<CandidatePrerenderInfo> info) {
1256   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
1257   TIMING_HISTOGRAM("Prerender.LocalPredictorLoggedInLookupTime",
1258                    base::Time::Now() - info->start_time_);
1259   RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_STARTED);
1260   if (info->candidate_urls_.size() == 0) {
1261     RecordEvent(EVENT_NO_PRERENDER_CANDIDATES);
1262     return;
1263   }
1264   scoped_ptr<LocalPredictorURLInfo> url_info;
1265 #if defined(FULL_SAFE_BROWSING)
1266   scoped_refptr<SafeBrowsingDatabaseManager> sb_db_manager =
1267       g_browser_process->safe_browsing_service()->database_manager();
1268 #endif
1269   int num_issued = 0;
1270   for (int i = 0; i < static_cast<int>(info->candidate_urls_.size()); i++) {
1271     if (num_issued >= GetLocalPredictorMaxLaunchPrerenders())
1272       return;
1273     RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_EXAMINE_NEXT_URL);
1274     url_info.reset(new LocalPredictorURLInfo(info->candidate_urls_[i]));
1275     if (url_info->local_history_based) {
1276       if (SkipLocalPredictorLocalCandidates()) {
1277         url_info.reset(NULL);
1278         continue;
1279       }
1280       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_EXAMINE_NEXT_URL_LOCAL);
1281     }
1282     if (!url_info->local_history_based) {
1283       if (SkipLocalPredictorServiceCandidates()) {
1284         url_info.reset(NULL);
1285         continue;
1286       }
1287       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_EXAMINE_NEXT_URL_SERVICE);
1288     }
1289
1290     RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_EXAMINE_NEXT_URL_NOT_SKIPPED);
1291
1292     // We need to check whether we can issue a prerender for this URL.
1293     // We test a set of conditions. Each condition can either rule out
1294     // a prerender (in which case we reset url_info, so that it will not
1295     // be prerendered, and we continue, which means try the next candidate
1296     // URL), or it can be sufficient to issue the prerender without any
1297     // further checks (in which case we just break).
1298     // The order of the checks is critical, because it prescribes the logic
1299     // we use here to decide what to prerender.
1300     if (!url_info->url_lookup_success) {
1301       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_NO_URL);
1302       url_info.reset(NULL);
1303       continue;
1304     }
1305     if (!SkipLocalPredictorFragment() &&
1306         URLsIdenticalIgnoringFragments(info->source_url_.url,
1307                                        url_info->url)) {
1308       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_URLS_IDENTICAL_BUT_FRAGMENT);
1309       url_info.reset(NULL);
1310       continue;
1311     }
1312     if (!SkipLocalPredictorHTTPS() && url_info->url.SchemeIs("https")) {
1313       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_HTTPS);
1314       url_info.reset(NULL);
1315       continue;
1316     }
1317     if (IsRootPageURL(url_info->url)) {
1318       // For root pages, we assume that they are reasonably safe, and we
1319       // will just prerender them without any additional checks.
1320       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_ROOT_PAGE);
1321       IssuePrerender(info.get(), url_info.get());
1322       num_issued++;
1323       continue;
1324     }
1325     if (IsLogOutURL(url_info->url)) {
1326       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_LOGOUT_URL);
1327       url_info.reset(NULL);
1328       continue;
1329     }
1330     if (IsLogInURL(url_info->url)) {
1331       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_LOGIN_URL);
1332       url_info.reset(NULL);
1333       continue;
1334     }
1335 #if defined(FULL_SAFE_BROWSING)
1336     if (!SkipLocalPredictorWhitelist() && sb_db_manager.get() &&
1337         sb_db_manager->CheckSideEffectFreeWhitelistUrl(url_info->url)) {
1338       // If a page is on the side-effect free whitelist, we will just prerender
1339       // it without any additional checks.
1340       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_ON_SIDE_EFFECT_FREE_WHITELIST);
1341       IssuePrerender(info.get(), url_info.get());
1342       num_issued++;
1343       continue;
1344     }
1345 #endif
1346     if (!SkipLocalPredictorServiceWhitelist() &&
1347         url_info->service_whitelist && url_info->service_whitelist_lookup_ok) {
1348       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_ON_SERVICE_WHITELIST);
1349       IssuePrerender(info.get(), url_info.get());
1350       num_issued++;
1351       continue;
1352     }
1353     if (!SkipLocalPredictorLoggedIn() &&
1354         !url_info->logged_in && url_info->logged_in_lookup_ok) {
1355       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_NOT_LOGGED_IN);
1356       IssuePrerender(info.get(), url_info.get());
1357       num_issued++;
1358       continue;
1359     }
1360     if (!SkipLocalPredictorDefaultNoPrerender()) {
1361       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_FALLTHROUGH_NOT_PRERENDERING);
1362       url_info.reset(NULL);
1363     } else {
1364       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_FALLTHROUGH_PRERENDERING);
1365       IssuePrerender(info.get(), url_info.get());
1366       num_issued++;
1367       continue;
1368     }
1369   }
1370 }
1371
1372 void PrerenderLocalPredictor::IssuePrerender(
1373     CandidatePrerenderInfo* info,
1374     LocalPredictorURLInfo* url_info) {
1375   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
1376   RecordEvent(EVENT_ISSUE_PRERENDER_CALLED);
1377   if (prefetch_list_->AddURL(url_info->url)) {
1378     RecordEvent(EVENT_PREFETCH_LIST_ADDED);
1379     // If we are prefetching rather than prerendering, now is the time to launch
1380     // the prefetch.
1381     if (IsLocalPredictorPrerenderPrefetchEnabled()) {
1382       RecordEvent(EVENT_ISSUE_PRERENDER_PREFETCH_ENABLED);
1383       // Obtain the render frame host that caused this prefetch.
1384       RenderFrameHost* rfh = RenderFrameHost::FromID(info->render_process_id_,
1385                                                      info->render_frame_id_);
1386       // If it is still alive, launch the prefresh.
1387       if (rfh) {
1388         rfh->Send(new PrefetchMsg_Prefetch(rfh->GetRoutingID(), url_info->url));
1389         RecordEvent(EVENT_ISSUE_PRERENDER_PREFETCH_ISSUED);
1390       }
1391     }
1392   }
1393   PrerenderProperties* prerender_properties =
1394       GetIssuedPrerenderSlotForPriority(url_info->url, url_info->priority);
1395   if (!prerender_properties) {
1396     RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_PRIORITY_TOO_LOW);
1397     return;
1398   }
1399   RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_ISSUING_PRERENDER);
1400   DCHECK(prerender_properties != NULL);
1401   DCHECK(info != NULL);
1402   DCHECK(url_info != NULL);
1403   if (!IsLocalPredictorPrerenderLaunchEnabled())
1404     return;
1405   URLID url_id = url_info->id;
1406   const GURL& url = url_info->url;
1407   double priority = url_info->priority;
1408   base::Time current_time = GetCurrentTime();
1409   RecordEvent(EVENT_ISSUING_PRERENDER);
1410
1411   // Issue the prerender and obtain a new handle.
1412   scoped_ptr<prerender::PrerenderHandle> new_prerender_handle(
1413       prerender_manager_->AddPrerenderFromLocalPredictor(
1414           url, info->session_storage_namespace_.get(), *(info->size_)));
1415
1416   // Check if this is a duplicate of an existing prerender. If yes, clean up
1417   // the new handle.
1418   for (int i = 0; i < static_cast<int>(issued_prerenders_.size()); i++) {
1419     PrerenderProperties* p = issued_prerenders_[i];
1420     DCHECK(p != NULL);
1421     if (new_prerender_handle &&
1422         new_prerender_handle->RepresentingSamePrerenderAs(
1423             p->prerender_handle.get())) {
1424       new_prerender_handle->OnCancel();
1425       new_prerender_handle.reset(NULL);
1426       RecordEvent(EVENT_ISSUE_PRERENDER_ALREADY_PRERENDERING);
1427       break;
1428     }
1429   }
1430
1431   if (new_prerender_handle.get()) {
1432     RecordEvent(EVENT_ISSUE_PRERENDER_NEW_PRERENDER);
1433     // The new prerender does not match any existing prerenders. Update
1434     // prerender_properties so that it reflects the new entry.
1435     prerender_properties->url_id = url_id;
1436     prerender_properties->url = url;
1437     prerender_properties->priority = priority;
1438     prerender_properties->start_time = current_time;
1439     prerender_properties->actual_start_time = current_time;
1440     prerender_properties->would_have_matched = false;
1441     prerender_properties->prerender_handle.swap(new_prerender_handle);
1442     // new_prerender_handle now represents the old previou prerender that we
1443     // are replacing. So we need to cancel it.
1444     if (new_prerender_handle) {
1445       new_prerender_handle->OnCancel();
1446       RecordEvent(EVENT_ISSUE_PRERENDER_CANCELLED_OLD_PRERENDER);
1447     }
1448   }
1449
1450   RecordEvent(EVENT_ADD_VISIT_PRERENDERING);
1451   if (current_prerender_.get() && current_prerender_->url_id == url_id) {
1452     RecordEvent(EVENT_ADD_VISIT_PRERENDERING_EXTENDED);
1453     if (priority > current_prerender_->priority)
1454       current_prerender_->priority = priority;
1455     // If the prerender already existed, we want to extend it.  However,
1456     // we do not want to set its start_time to the current time to
1457     // disadvantage PLT computations when the prerender is swapped in.
1458     // So we set the new start time to current_time - 10s (since the vast
1459     // majority of PLTs are < 10s), provided that is not before the actual
1460     // time the prerender was started (so as to not artificially advantage
1461     // the PLT computation).
1462     base::Time simulated_new_start_time =
1463         current_time - base::TimeDelta::FromSeconds(10);
1464     if (simulated_new_start_time > current_prerender_->start_time)
1465       current_prerender_->start_time = simulated_new_start_time;
1466   } else {
1467     current_prerender_.reset(
1468         new PrerenderProperties(url_id, url, priority, current_time));
1469   }
1470   current_prerender_->actual_start_time = current_time;
1471 }
1472
1473 void PrerenderLocalPredictor::OnTabHelperURLSeen(
1474     const GURL& url, WebContents* web_contents) {
1475   RecordEvent(EVENT_TAB_HELPER_URL_SEEN);
1476
1477   if (prefetch_list_->MarkURLSeen(url, PrefetchList::SEEN_TABCONTENTS_OBSERVER))
1478     RecordEvent(EVENT_PREFETCH_LIST_SEEN_TABCONTENTS);
1479   bool browser_navigate_initiated = false;
1480   const content::NavigationEntry* entry =
1481       web_contents->GetController().GetPendingEntry();
1482   if (entry) {
1483     base::string16 result;
1484     browser_navigate_initiated =
1485         entry->GetExtraData(kChromeNavigateExtraDataKey, &result);
1486   }
1487
1488   // If the namespace matches and the URL matches, we might be able to swap
1489   // in. However, the actual code initating the swapin is in the renderer
1490   // and is checking for other criteria (such as POSTs). There may
1491   // also be conditions when a swapin should happen but does not. By recording
1492   // the two previous events, we can keep an eye on the magnitude of the
1493   // discrepancy.
1494
1495   PrerenderProperties* best_matched_prerender = NULL;
1496   bool session_storage_namespace_matches = false;
1497   SessionStorageNamespace* tab_session_storage_namespace =
1498       web_contents->GetController().GetDefaultSessionStorageNamespace();
1499   for (int i = 0; i < static_cast<int>(issued_prerenders_.size()); i++) {
1500     PrerenderProperties* p = issued_prerenders_[i];
1501     DCHECK(p != NULL);
1502     if (!p->prerender_handle.get() ||
1503         !p->prerender_handle->Matches(url, NULL) ||
1504         p->would_have_matched) {
1505       continue;
1506     }
1507     if (!best_matched_prerender || !session_storage_namespace_matches) {
1508       best_matched_prerender = p;
1509       session_storage_namespace_matches =
1510           p->prerender_handle->Matches(url, tab_session_storage_namespace);
1511     }
1512   }
1513   if (best_matched_prerender) {
1514     RecordEvent(EVENT_TAB_HELPER_URL_SEEN_MATCH);
1515     if (entry)
1516       RecordEvent(EVENT_TAB_HELPER_URL_SEEN_MATCH_ENTRY);
1517     if (browser_navigate_initiated)
1518       RecordEvent(EVENT_TAB_HELPER_URL_SEEN_MATCH_BROWSER_NAVIGATE);
1519     best_matched_prerender->would_have_matched = true;
1520     if (session_storage_namespace_matches) {
1521       RecordEvent(EVENT_TAB_HELPER_URL_SEEN_NAMESPACE_MATCH);
1522       if (entry)
1523         RecordEvent(EVENT_TAB_HELPER_URL_SEEN_NAMESPACE_MATCH_ENTRY);
1524       if (browser_navigate_initiated)
1525         RecordEvent(EVENT_TAB_HELPER_URL_SEEN_NAMESPACE_MATCH_BROWSER_NAVIGATE);
1526     } else {
1527       SessionStorageNamespace* prerender_session_storage_namespace =
1528           best_matched_prerender->prerender_handle->
1529           GetSessionStorageNamespace();
1530       if (!prerender_session_storage_namespace) {
1531         RecordEvent(EVENT_TAB_HELPER_URL_SEEN_NAMESPACE_MISMATCH_NO_NAMESPACE);
1532       } else {
1533         RecordEvent(EVENT_TAB_HELPER_URL_SEEN_NAMESPACE_MISMATCH_MERGE_ISSUED);
1534         prerender_session_storage_namespace->Merge(
1535             false,
1536             best_matched_prerender->prerender_handle->GetChildId(),
1537             tab_session_storage_namespace,
1538             base::Bind(&PrerenderLocalPredictor::ProcessNamespaceMergeResult,
1539                        weak_factory_.GetWeakPtr()));
1540       }
1541     }
1542   }
1543 }
1544
1545 void PrerenderLocalPredictor::ProcessNamespaceMergeResult(
1546     content::SessionStorageNamespace::MergeResult result) {
1547   RecordEvent(EVENT_NAMESPACE_MISMATCH_MERGE_RESULT_RECEIVED);
1548   switch (result) {
1549     case content::SessionStorageNamespace::MERGE_RESULT_NAMESPACE_NOT_FOUND:
1550       RecordEvent(EVENT_NAMESPACE_MISMATCH_MERGE_RESULT_NAMESPACE_NOT_FOUND);
1551       break;
1552     case content::SessionStorageNamespace::MERGE_RESULT_NAMESPACE_NOT_ALIAS:
1553       RecordEvent(EVENT_NAMESPACE_MISMATCH_MERGE_RESULT_NAMESPACE_NOT_ALIAS);
1554       break;
1555     case content::SessionStorageNamespace::MERGE_RESULT_NOT_LOGGING:
1556       RecordEvent(EVENT_NAMESPACE_MISMATCH_MERGE_RESULT_NOT_LOGGING);
1557       break;
1558     case content::SessionStorageNamespace::MERGE_RESULT_NO_TRANSACTIONS:
1559       RecordEvent(EVENT_NAMESPACE_MISMATCH_MERGE_RESULT_NO_TRANSACTIONS);
1560       break;
1561     case content::SessionStorageNamespace::MERGE_RESULT_TOO_MANY_TRANSACTIONS:
1562       RecordEvent(EVENT_NAMESPACE_MISMATCH_MERGE_RESULT_TOO_MANY_TRANSACTIONS);
1563       break;
1564     case content::SessionStorageNamespace::MERGE_RESULT_NOT_MERGEABLE:
1565       RecordEvent(EVENT_NAMESPACE_MISMATCH_MERGE_RESULT_NOT_MERGEABLE);
1566       break;
1567     case content::SessionStorageNamespace::MERGE_RESULT_MERGEABLE:
1568       RecordEvent(EVENT_NAMESPACE_MISMATCH_MERGE_RESULT_MERGEABLE);
1569       break;
1570     default:
1571       NOTREACHED();
1572   }
1573 }
1574
1575 }  // namespace prerender