Add a PrefetchList to Prerender Local Predictor, to emulate how effective

chrome/browser/prerender/prerender_local_predictor.cc

 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "chrome/browser/prerender/prerender_local_predictor.h"
 
 #include <ctype.h>
 
 #include <algorithm>
 #include <map>
@@ skipping 52 matching lines @@
 using std::vector;
 
 namespace prerender {
 
 namespace {
 
 static const size_t kURLHashSize = 5;
 static const int kNumPrerenderCandidates = 5;
 static const int kInvalidProcessId = -1;
 static const int kInvalidFrameId = -1;
+static const int kMaxPrefetchItems = 100;
 
 }  // namespace
 
 // When considering a candidate URL to be prerendered, we need to collect the
 // data in this struct to make the determination whether we should issue the
 // prerender or not.
 struct PrerenderLocalPredictor::LocalPredictorURLInfo {
   URLID id;
   GURL url;
   bool url_lookup_success;
@@ skipping 308 matching lines @@
   // time after the actual prerender being kept around.
   base::Time start_time;
   // The actual time this page was last requested for prerendering.
   base::Time actual_start_time;
   scoped_ptr<PrerenderHandle> prerender_handle;
   // Indicates whether this prerender would have matched a URL navigated to,
   // but was not swapped in for some reason.
   bool would_have_matched;
 };
 
+// A class simulating a set of URLs prefetched, for statistical purposes.
+class PrerenderLocalPredictor::PrefetchList {
+ public:
+  enum SeenType {
+    SEEN_TABCONTENTS_OBSERVER,
+    SEEN_HISTORY,
+    SEEN_MAX_VALUE
+  };

[davidben, 2014/08/05 18:51:12]

Nit: newline here

[tburkard, 2014/08/05 20:05:54]

Done.

+  PrefetchList() {}
+  ~PrefetchList() {
+    STLDeleteValues(&entries_);
+  }

[davidben, 2014/08/05 18:51:12]

Nit: newline here

[tburkard, 2014/08/05 20:05:54]

Done.

+  // Adds a new URL being prefetched. If the URL is already in the list,
+  // nothing will happen. Returns whether a new prefetch was added.
+  bool AddURL(const GURL& url) {
+    ExpireOldItems();
+    string url_string = url.spec().c_str();
+    base::hash_map<string, ListEntry*>::iterator it = entries_.find(url_string);
+    if (it != entries_.end()) {
+      // If a prefetch previously existed, and has not been seen yet in either
+      // a tab contents or a history, we will not re-issue it. Otherwise, if it
+      // may have been consumed by either tab contents or history, we will
+      // permit re-issuing another one.
+      if (!it->second->seen_history_ &&
+          !it->second->seen_tabcontents_) {
+        return false;
+      }
+    }
+    ListEntry* entry = new ListEntry(url_string);
+    entries_[entry->url_] = entry;
+    entry_list_.push_back(entry);
+    ExpireOldItems();
+    return true;
+  }

[davidben, 2014/08/05 18:51:12]

Nit: newline here

[tburkard, 2014/08/05 20:05:54]

Done.

+  // Marks the URL provided as seen in the context specified. Returns true
+  // iff the item is currently in the list and had not been seen before in
+  // the context specified, i.e. the marking was successful.
+  bool MarkURLSeen(const GURL& url, SeenType type) {
+    ExpireOldItems();
+    bool return_value = false;
+    base::hash_map<string, ListEntry*>::iterator it =
+        entries_.find(url.spec().c_str());
+    if (it == entries_.end())
+      return return_value;
+    if (type == SEEN_TABCONTENTS_OBSERVER && !it->second->seen_tabcontents_) {
+      it->second->seen_tabcontents_ = true;
+      return_value = true;
+    }
+    if (type == SEEN_HISTORY && !it->second->seen_history_) {
+      it->second->seen_history_ = true;
+      return_value = true;
+    }
+    // If the item has been seen in both the history and in tab contents,
+    // erase it from the map to make room for new prefetches.
+    if (it->second->seen_tabcontents_ && it->second->seen_history_)
+      entries_.erase(url.spec().c_str());
+    return return_value;
+  }
+
+ private:
+  struct ListEntry {
+    std::string url_;
+    base::Time add_time_;
+    bool seen_tabcontents_;
+    bool seen_history_;
+    explicit ListEntry(string url)

[davidben, 2014/08/05 18:51:12]

Nit: I think we usually put methods before members. Also if these are public
fields of a struct, they probably shouldn't have the underscore. (Writing
url(url) in the initialization list works fine.)

[Alexei Svitkine (slow), 2014/08/05 19:20:22]

Pass the param by const ref.

[tburkard, 2014/08/05 20:05:54]

Done.

[tburkard, 2014/08/05 20:05:54]

Done.

+        : url_(url),
+          add_time_(GetCurrentTime()),
+          seen_tabcontents_(false),
+          seen_history_(false) {
+    }
+  };

[davidben, 2014/08/05 18:51:12]

Nit: newline here

[tburkard, 2014/08/05 20:05:54]

Done.

+  void ExpireOldItems() {
+    base::Time expiry_cutoff = GetCurrentTime() -
+        base::TimeDelta::FromSeconds(GetPrerenderPrefetchListTimeoutSeconds());
+    while (!entry_list_.empty() &&
+           (entry_list_.front()->add_time_ < expiry_cutoff ||
+            entries_.size() > kMaxPrefetchItems)) {
+      ListEntry* entry = entry_list_.front();
+      entry_list_.pop_front();
+      // If the entry to be deleted is still the one active in entries_,
+      // we must erase it from entries_.
+      base::hash_map<string, ListEntry*>::iterator it =
+          entries_.find(entry->url_);
+      if (it != entries_.end() && it->second == entry)
+        entries_.erase(entry->url_);
+      delete entry;

[Alexei Svitkine (slow), 2014/08/05 19:20:22]

Can you use a scoped_ptr instead?

[tburkard, 2014/08/05 20:05:54]

Not obvious to me how this would work well here.
Can you point me to some existing code using a scoped_ptr inside STL containers?
I can change it in a follow-up CL (since I want to commit this today for
tomorrow's build and it's already 10pm in my timezone).

Thanks.

[Alexei Svitkine (slow), 2014/08/05 20:16:22]

Sorry, I meant in the body of the loop, not in the container - i.e.:

scoped_ptr<ListEntry> entry(entry_list_.front());
entry_list_.pop_front();

Then you don't need the delete (which is more error prone - e.g. if you decide
to add a break or continue statement later to the loop).

As for containers with owned pointers, I think we just have a ScopedVector,
which I didn't read your code careful enough to understand whether it's a good
fit here or not.

+    }
+  }

[davidben, 2014/08/05 18:51:12]

Nit: newline here

[tburkard, 2014/08/05 20:05:54]

Done.

+  base::hash_map<string, ListEntry*> entries_;
+  std::list<ListEntry*> entry_list_;
+  DISALLOW_COPY_AND_ASSIGN(PrefetchList);
+};
+
 PrerenderLocalPredictor::PrerenderLocalPredictor(
     PrerenderManager* prerender_manager)
     : prerender_manager_(prerender_manager),
       is_visit_database_observer_(false),
-      weak_factory_(this) {
+      weak_factory_(this),
+      prefetch_list_(new PrefetchList()) {
   RecordEvent(EVENT_CONSTRUCTED);
   if (base::MessageLoop::current()) {
     timer_.Start(FROM_HERE,
                  base::TimeDelta::FromMilliseconds(kInitDelayMs),
                  this,
                  &PrerenderLocalPredictor::Init);
     RecordEvent(EVENT_INIT_SCHEDULED);
   }
 
   static const size_t kChecksumHashSize = 32;
@@ skipping 153 matching lines @@
     scoped_ptr<CandidatePrerenderInfo> info) {
   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
 
   RecordEvent(EVENT_PRERENDER_URL_LOOKUP_RESULT);
 
   if (!info->source_url_.url_lookup_success) {
     RecordEvent(EVENT_PRERENDER_URL_LOOKUP_FAILED);
     return;
   }
 
+  if (prefetch_list_->MarkURLSeen(info->source_url_.url,
+                                  PrefetchList::SEEN_HISTORY)) {
+    RecordEvent(EVENT_PREFETCH_LIST_SEEN_HISTORY);
+  }
+
   if (info->candidate_urls_.size() > 0 &&
       info->candidate_urls_[0].url_lookup_success) {
     LogCandidateURLStats(info->candidate_urls_[0].url);
   }
 
   WebContents* source_web_contents = NULL;
   bool multiple_source_web_contents_candidates = false;
 
 #if !defined(OS_ANDROID)
   // We need to figure out what tab launched the prerender. We do this by
@@ skipping 529 matching lines @@
   RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_STARTED);
   if (info->candidate_urls_.size() == 0) {
     RecordEvent(EVENT_NO_PRERENDER_CANDIDATES);
     return;
   }
   scoped_ptr<LocalPredictorURLInfo> url_info;
 #if defined(FULL_SAFE_BROWSING)
   scoped_refptr<SafeBrowsingDatabaseManager> sb_db_manager =
       g_browser_process->safe_browsing_service()->database_manager();
 #endif
-  PrerenderProperties* prerender_properties = NULL;
   int num_issued = 0;
   for (int i = 0; i < static_cast<int>(info->candidate_urls_.size()); i++) {
-    if (num_issued > GetLocalPredictorMaxLaunchPrerenders())
+    if (num_issued >= GetLocalPredictorMaxLaunchPrerenders())
       return;
     RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_EXAMINE_NEXT_URL);
     url_info.reset(new LocalPredictorURLInfo(info->candidate_urls_[i]));
     if (url_info->local_history_based) {
       if (SkipLocalPredictorLocalCandidates()) {
         url_info.reset(NULL);
         continue;
       }
       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_EXAMINE_NEXT_URL_LOCAL);
     }
@@ skipping 13 matching lines @@
     // be prerendered, and we continue, which means try the next candidate
     // URL), or it can be sufficient to issue the prerender without any
     // further checks (in which case we just break).
     // The order of the checks is critical, because it prescribes the logic
     // we use here to decide what to prerender.
     if (!url_info->url_lookup_success) {
       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_NO_URL);
       url_info.reset(NULL);
       continue;
     }
-    prerender_properties =
-        GetIssuedPrerenderSlotForPriority(url_info->url, url_info->priority);
-    if (!prerender_properties) {
-      RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_PRIORITY_TOO_LOW);
-      url_info.reset(NULL);
-      continue;
-    }

[davidben, 2014/08/05 18:51:12]

This will count candidate URLs toward num_issued even if they fail this check.
Is this intentional?

[tburkard, 2014/08/05 20:05:54]

Yes, that's fine, because they are ordered in descending priority. Therefore,
once the first one fails this check, all next ones should fail, too.

     if (!SkipLocalPredictorFragment() &&
         URLsIdenticalIgnoringFragments(info->source_url_.url,
                                        url_info->url)) {
       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_URLS_IDENTICAL_BUT_FRAGMENT);
       url_info.reset(NULL);
       continue;
     }
     if (!SkipLocalPredictorHTTPS() && url_info->url.SchemeIs("https")) {
       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_HTTPS);
       url_info.reset(NULL);
       continue;
     }
     if (IsRootPageURL(url_info->url)) {
       // For root pages, we assume that they are reasonably safe, and we
       // will just prerender them without any additional checks.
       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_ROOT_PAGE);
-      IssuePrerender(info.get(), url_info.get(), prerender_properties);
+      IssuePrerender(info.get(), url_info.get());
       num_issued++;
       continue;
     }
     if (IsLogOutURL(url_info->url)) {
       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_LOGOUT_URL);
       url_info.reset(NULL);
       continue;
     }
     if (IsLogInURL(url_info->url)) {
       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_LOGIN_URL);
       url_info.reset(NULL);
       continue;
     }
 #if defined(FULL_SAFE_BROWSING)
     if (!SkipLocalPredictorWhitelist() && sb_db_manager &&
         sb_db_manager->CheckSideEffectFreeWhitelistUrl(url_info->url)) {
       // If a page is on the side-effect free whitelist, we will just prerender
       // it without any additional checks.
       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_ON_SIDE_EFFECT_FREE_WHITELIST);
-      IssuePrerender(info.get(), url_info.get(), prerender_properties);
+      IssuePrerender(info.get(), url_info.get());
       num_issued++;
       continue;
     }
 #endif
     if (!SkipLocalPredictorServiceWhitelist() &&
         url_info->service_whitelist && url_info->service_whitelist_lookup_ok) {
       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_ON_SERVICE_WHITELIST);
-      IssuePrerender(info.get(), url_info.get(), prerender_properties);
+      IssuePrerender(info.get(), url_info.get());
       num_issued++;
       continue;
     }
     if (!SkipLocalPredictorLoggedIn() &&
         !url_info->logged_in && url_info->logged_in_lookup_ok) {
       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_NOT_LOGGED_IN);
-      IssuePrerender(info.get(), url_info.get(), prerender_properties);
+      IssuePrerender(info.get(), url_info.get());
       num_issued++;
       continue;
     }
     if (!SkipLocalPredictorDefaultNoPrerender()) {
       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_FALLTHROUGH_NOT_PRERENDERING);
       url_info.reset(NULL);
     } else {
       RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_FALLTHROUGH_PRERENDERING);
-      IssuePrerender(info.get(), url_info.get(), prerender_properties);
+      IssuePrerender(info.get(), url_info.get());
       num_issued++;
       continue;
     }
   }
 }
 
 void PrerenderLocalPredictor::IssuePrerender(
     CandidatePrerenderInfo* info,
-    LocalPredictorURLInfo* url_info,
-    PrerenderProperties* prerender_properties) {
+    LocalPredictorURLInfo* url_info) {
   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
+  if (prefetch_list_->AddURL(url_info->url))
+    RecordEvent(EVENT_PREFETCH_LIST_ADDED);
+  PrerenderProperties* prerender_properties =
+      GetIssuedPrerenderSlotForPriority(url_info->url, url_info->priority);
+  if (!prerender_properties) {
+    RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_PRIORITY_TOO_LOW);
+    return;
+  }
   RecordEvent(EVENT_CONTINUE_PRERENDER_CHECK_ISSUING_PRERENDER);
   DCHECK(prerender_properties != NULL);
   DCHECK(info != NULL);
   DCHECK(url_info != NULL);
   if (!IsLocalPredictorPrerenderLaunchEnabled())
     return;
   URLID url_id = url_info->id;
   const GURL& url = url_info->url;
   double priority = url_info->priority;
   base::Time current_time = GetCurrentTime();
@@ skipping 68 matching lines @@
     current_prerender_.reset(
         new PrerenderProperties(url_id, url, priority, current_time));
   }
   current_prerender_->actual_start_time = current_time;
 }
 
 void PrerenderLocalPredictor::OnTabHelperURLSeen(
     const GURL& url, WebContents* web_contents) {
   RecordEvent(EVENT_TAB_HELPER_URL_SEEN);
 
+  if (prefetch_list_->MarkURLSeen(url, PrefetchList::SEEN_TABCONTENTS_OBSERVER))
+    RecordEvent(EVENT_PREFETCH_LIST_SEEN_TABCONTENTS);
   bool browser_navigate_initiated = false;
   const content::NavigationEntry* entry =
       web_contents->GetController().GetPendingEntry();
   if (entry) {
     base::string16 result;
     browser_navigate_initiated =
         entry->GetExtraData(kChromeNavigateExtraDataKey, &result);
   }
 
   // If the namespace matches and the URL matches, we might be able to swap
@@ skipping 77 matching lines @@
       break;
     case content::SessionStorageNamespace::MERGE_RESULT_MERGEABLE:
       RecordEvent(EVENT_NAMESPACE_MISMATCH_MERGE_RESULT_MERGEABLE);
       break;
     default:
       NOTREACHED();
   }
 }
 
 }  // namespace prerender