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