Change multi-prerender API to include per launcher slots.

chrome/browser/prerender/prerender_link_manager.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_link_manager.h"
 
 #include <limits>
+#include <set>
 #include <utility>
 
 #include "base/memory/scoped_ptr.h"
 #include "chrome/browser/prerender/prerender_contents.h"
 #include "chrome/browser/prerender/prerender_handle.h"
 #include "chrome/browser/prerender/prerender_manager.h"
 #include "chrome/browser/prerender/prerender_manager_factory.h"
 #include "chrome/browser/profiles/profile.h"
 #include "chrome/common/prerender_messages.h"
 #include "content/public/browser/render_process_host.h"
 #include "content/public/browser/render_view_host.h"
 #include "content/public/browser/session_storage_namespace.h"
 #include "content/public/common/referrer.h"
 #include "googleurl/src/gurl.h"
 #include "ui/gfx/size.h"
 
+using base::TimeDelta;
+using base::TimeTicks;
 using content::RenderViewHost;
 using content::SessionStorageNamespace;
 
 namespace {
 
 void Send(int child_id, IPC::Message* raw_message) {
   using content::RenderProcessHost;
   scoped_ptr<IPC::Message> own_message(raw_message);
 
   RenderProcessHost* render_process_host = RenderProcessHost::FromID(child_id);
   if (!render_process_host)
     return;
   render_process_host->Send(own_message.release());
 }
 
 }  // namespace
 
 namespace prerender {
 
 PrerenderLinkManager::PrerenderLinkManager(PrerenderManager* manager)
-    : manager_(manager) {
+    : has_shutdown_(false),
+      manager_(manager) {
 }
 
 PrerenderLinkManager::~PrerenderLinkManager() {
-  for (IdPairToPrerenderHandleMap::iterator it = ids_to_handle_map_.begin();
-       it != ids_to_handle_map_.end();
-       ++it) {
-    PrerenderHandle* prerender_handle = it->second;
-    DCHECK(!prerender_handle->IsPrerendering())
-        << "All running prerenders should stop at the same time as the "
-        << "PrerenderManager.";
-    delete prerender_handle;
-  }
-}
-
-bool PrerenderLinkManager::OnAddPrerender(int child_id,
+  for (std::list<Prerender>::iterator i = prerenders_.begin();
+       i != prerenders_.end(); ++i) {
+    if (i->handle) {
+      DCHECK(!i->handle->IsPrerendering())
+          << "All running prerenders should stop at the same time as the "
+          << "PrerenderManager.";
+      delete i->handle;
+      i->handle = 0;
+    }
+  }
+}
+
+void PrerenderLinkManager::OnAddPrerender(int launcher_child_id,
                                           int prerender_id,
                                           const GURL& url,
                                           const content::Referrer& referrer,
                                           const gfx::Size& size,
                                           int render_view_route_id) {
-  DVLOG(2) << "OnAddPrerender, child_id = " << child_id
-           << ", prerender_id = " << prerender_id
-           << ", url = " << url.spec();
-  DVLOG(3) << "... referrer url = " << referrer.url.spec()
-           << ", size = (" << size.width() << ", " << size.height() << ")"
-           << ", render_view_route_id = " << render_view_route_id;
-
-
-  PrerenderHandle* prerender_handle =
-      manager_->AddPrerenderFromLinkRelPrerender(
-          child_id, render_view_route_id, url, referrer, size);
-  if (!prerender_handle)
-    return false;
-
-  const ChildAndPrerenderIdPair child_and_prerender_id(child_id, prerender_id);
-  DCHECK_EQ(0u, ids_to_handle_map_.count(child_and_prerender_id));
-  ids_to_handle_map_[child_and_prerender_id] = prerender_handle;
-
-  // If we are given a prerender that is already prerendering, we have missed
-  // the start event.
-  if (prerender_handle->IsPrerendering())
-    OnPrerenderStart(prerender_handle);
-  prerender_handle->SetObserver(this);
-  return true;
+  Prerender prerender(launcher_child_id, prerender_id, url, referrer, size,
+                      render_view_route_id, manager_->GetCurrentTimeTicks());
+  prerenders_.push_back(prerender);
+  StartPrerenders();
 }
 
 void PrerenderLinkManager::OnCancelPrerender(int child_id, int prerender_id) {
-  DVLOG(2) << "OnCancelPrerender, child_id = " << child_id
-           << ", prerender_id = " << prerender_id;
-  const ChildAndPrerenderIdPair child_and_prerender_id(child_id, prerender_id);
-  IdPairToPrerenderHandleMap::iterator id_to_handle_iter =
-      ids_to_handle_map_.find(child_and_prerender_id);
-  if (id_to_handle_iter == ids_to_handle_map_.end()) {
-    DVLOG(5) << "... canceling a prerender that doesn't exist.";
-    return;
-  }
-
-  scoped_ptr<PrerenderHandle> prerender_handle(id_to_handle_iter->second);
-  ids_to_handle_map_.erase(id_to_handle_iter);
-  prerender_handle->OnCancel();
-
-  // Because OnCancel() can remove the prerender from the map, we need to
-  // consider our iterator invalid.
-  id_to_handle_iter = ids_to_handle_map_.find(child_and_prerender_id);
-  if (id_to_handle_iter != ids_to_handle_map_.end())
-    RemovePrerender(id_to_handle_iter);
+  Prerender* prerender = FindByLauncherChildIdAndPrerenderId(child_id,
+                                                             prerender_id);
+  if (!prerender)
+    return;
+
+  // Remove the handle from the PrerenderLinkManager before we cancel this
+  // prerender, to avoid reentering the PrerenderLinkManager, sending events to
+  // the underlying prerender and making a second erase.
+  scoped_ptr<PrerenderHandle> own_prerender_handle(prerender->handle);
+  prerender->handle = NULL;
+  RemovePrerender(prerender);
+
+  if (own_prerender_handle)
+    own_prerender_handle->OnCancel();
+
+  StartPrerenders();
 }
 
 void PrerenderLinkManager::OnAbandonPrerender(int child_id, int prerender_id) {
-  DVLOG(2) << "OnAbandonPrerender, child_id = " << child_id
-           << ", prerender_id = " << prerender_id;
-  const ChildAndPrerenderIdPair child_and_prerender_id(child_id, prerender_id);
-  IdPairToPrerenderHandleMap::iterator id_to_handle_iter =
-      ids_to_handle_map_.find(child_and_prerender_id);
-  if (id_to_handle_iter == ids_to_handle_map_.end())
-    return;
-  PrerenderHandle* prerender_handle = id_to_handle_iter->second;
-  prerender_handle->OnNavigateAway();
+  Prerender* prerender = FindByLauncherChildIdAndPrerenderId(child_id,
+                                                             prerender_id);
+  if (!prerender)
+    return;
+
+  if (!prerender->handle) {
+    RemovePrerender(prerender);
+    return;
+  }
+
+  prerender->handle->OnNavigateAway();
+  DCHECK(prerender->handle);
+
+  // If the prerender is not running, remove it from the list so it does not
+  // leak. If it is running, it will send a cancel event when it stops which
+  // will remove it.
+  if (!prerender->handle->IsPrerendering())
+    RemovePrerender(prerender);
 }
 
 void PrerenderLinkManager::OnChannelClosing(int child_id) {
-  DVLOG(2) << "OnChannelClosing, child id = " << child_id;
-  const ChildAndPrerenderIdPair child_and_minimum_prerender_id(
-      child_id, std::numeric_limits<int>::min());
-  const ChildAndPrerenderIdPair child_and_maximum_prerender_id(
-      child_id, std::numeric_limits<int>::max());
-
-  IdPairToPrerenderHandleMap::iterator
-      it = ids_to_handle_map_.lower_bound(child_and_minimum_prerender_id);
-  IdPairToPrerenderHandleMap::iterator
-      end = ids_to_handle_map_.upper_bound(child_and_maximum_prerender_id);
-  while (it != end) {
-    IdPairToPrerenderHandleMap::iterator next = it;
+  std::list<Prerender>::iterator next = prerenders_.begin();
+  while (next != prerenders_.end()) {
+    std::list<Prerender>::iterator it = next;
     ++next;
 
-    size_t size_before_abandon = ids_to_handle_map_.size();
-    OnAbandonPrerender(child_id, it->first.second);
-    DCHECK_EQ(size_before_abandon, ids_to_handle_map_.size());
-    RemovePrerender(it);
-
-    it = next;
-  }
+    if (child_id != it->launcher_child_id)
+      continue;
+
+    const size_t running_prerender_count = CountRunningPrerenders();
+    OnAbandonPrerender(child_id, it->prerender_id);
+    DCHECK_EQ(running_prerender_count, CountRunningPrerenders());
+  }
+}
+
+PrerenderLinkManager::Prerender::Prerender(int launcher_child_id,
+                                           int prerender_id,
+                                           const GURL& url,
+                                           const content::Referrer& referrer,
+                                           const gfx::Size& size,
+                                           int render_view_route_id,
+                                           TimeTicks creation_time)
+    : launcher_child_id(launcher_child_id),
+      prerender_id(prerender_id),
+      url(url),
+      referrer(referrer),
+      size(size),
+      render_view_route_id(render_view_route_id),
+      creation_time(creation_time),
+      handle(NULL) {
+}
+
+PrerenderLinkManager::Prerender::~Prerender() {
+  DCHECK_EQ(static_cast<PrerenderHandle*>(NULL), handle);

[mmenke, 2012/12/28 18:25:33]

Think this is non-intuitive enough to be worth a comment - just something along
the lines of "Make sure the PrerenderHandle was destroyed before the Prerender."

[gavinp, 2012/12/28 19:53:46]

Done.

 }
 
 bool PrerenderLinkManager::IsEmpty() const {
-  return ids_to_handle_map_.empty();
-}
-
-void PrerenderLinkManager::RemovePrerender(
-    const IdPairToPrerenderHandleMap::iterator& id_to_handle_iter) {
-  PrerenderHandle* prerender_handle = id_to_handle_iter->second;
-  delete prerender_handle;
-  ids_to_handle_map_.erase(id_to_handle_iter);
-}
-
-PrerenderLinkManager::IdPairToPrerenderHandleMap::iterator
-PrerenderLinkManager::FindPrerenderHandle(
-    PrerenderHandle* prerender_handle) {
-  for (IdPairToPrerenderHandleMap::iterator it = ids_to_handle_map_.begin();
-       it != ids_to_handle_map_.end(); ++it) {
-    if (it->second == prerender_handle)
-      return it;
-  }
-  return ids_to_handle_map_.end();
+  return prerenders_.empty();
+}
+
+size_t PrerenderLinkManager::CountRunningPrerenders() const {
+  size_t retval = 0;
+  for (std::list<Prerender>::const_iterator i = prerenders_.begin();
+       i != prerenders_.end(); ++i) {
+    if (i->handle && i->handle->IsPrerendering())
+      ++retval;
+  }
+  return retval;
+}
+
+void PrerenderLinkManager::StartPrerenders() {

[mmenke, 2012/12/28 18:25:33]

Some thoughts on this change (No need to address these in this CL):

We no longer see stats involved never started prerenders.  This will affect
existing histograms.  We may want to add new histograms (Blargh).  Think adding
fake FINAL_STATUS results directly to the histograms here would be a bit of a
layering violation.

net-internal's prerender tab won't display anything about these.  If we care
enough to have the tab display "active" prerenders in the first place, I assume
we care enough to add this information.

[gavinp, 2012/12/28 19:53:46]

Noted.

+  if (has_shutdown_)
+    return;
+
+  std::set<std::pair<int, int> > launcher_and_prerender_id_set;

[mmenke, 2012/12/28 18:25:33]

This is only used for sanity checking - are compilers smart enough to optimize
it out in release builds?

I'm not sure we actually need it - we have DCHECKs renderer-side for double
starts already.  Not a big fan of debugging-only code making it into production
binaries, unless we need it.

If we keep this, I think we should have a comment that it's only for DCHECKing,
and rename it to running_launcher_and_prerender_id_set, so these all have
consistent names.

[gavinp, 2012/12/28 19:53:46]

I doubt compilers are that smart. I'm removing it.

[mmenke, 2012/12/28 20:15:13]

optional:  Actually...you could do something like:

DCHECK_EQ(FindByLauncherChildIdAndPrerenderId(i->child_id, i->prerender_id),
&(*i)); where the current DCHECK_EQ was, if you want.

[gavinp, 2012/12/28 20:54:21]

Done. Also found I'd left a std::pair sitting around, which is probably not
great practice.

+
+  size_t added_prerender_count = 0;

[mmenke, 2012/12/28 18:25:33]

nit:  Think "running" or "started" would be clearer than "added".  "running" is
used in the variable below, so would be the more consistent choice.

[gavinp, 2012/12/28 19:53:46]

total_started_prerender_count avoided confusion I had around running and added.
Done.

+  std::multiset<std::pair<int, int> >
+      running_launcher_and_render_view_route_set;

[mmenke, 2012/12/28 18:25:33]

optional:  You may want to use a map here instead of a multiset.  multiset does
exactly what you want, uses less C++ code than map of pairs, and may compile
into marginally smaller code.  However, there are fewer than 30 files that use
them in the entire Chrome code base (Only 3 in chrome/, 5 in content/), so may
be easier for people to follow using a map here.  I leave the choice to you.

[mmenke, 2012/12/28 18:25:33]

optional:  May want to just pluralize this and remove the "set".  Same goes for
the other "set".  Given the mix of a set and a multiset, don't think the "set"
helps much, and I've noticed a tendency for STL types to switch over time (Not
that I think it's likely here, just not sure the suffixes are worth it, in
general).

[mmenke, 2012/12/28 18:32:39]

This is one of those time-of-day comments, btw - if it were between 10 am and 2
pm when reviewing, I may say one thing, between 2 pm and 6 pm, I may say
another.  After 6 pm, I may not comment either way.  Completely up to you.

[gavinp, 2012/12/28 19:53:46]

I liked the name change, but I can't bear to move to the map of pairs. I know
the pattern we're talking about, and it's a confusing anti-pattern if you ask
me...

You said you'll tolerate me leaving it in, so my next upload does that. If you
start to feel strongly about it, tell me, and I'll switch to the map of pairs.

[mmenke, 2012/12/28 20:15:13]

I'm content with keeping it as-is.  If I had particularly strong opinions about
it, I wouldn't have included the "optional" (Though I welcome pushback when I
don't use it, as well).

Think there are definite advantages to the multiset, and there are reasonable
reasons to stick with it.

+
+  // Scan the list, counting how many prerenders have handles (and so were added
+  // to the PrerenderManager). The count is done for the system as a whole, and
+  // also per launcher.
+  for (std::list<Prerender>::iterator i = prerenders_.begin();
+       i != prerenders_.end(); ++i) {
+    if (i->handle) {
+      ++added_prerender_count;
+      std::pair<int, int> launcher_and_render_view_route(
+          i->launcher_child_id, i->render_view_route_id);
+      running_launcher_and_render_view_route_set.insert(
+          launcher_and_render_view_route);
+      DCHECK_GE(manager_->config().max_link_concurrency_per_launcher,
+                running_launcher_and_render_view_route_set.count(
+                    launcher_and_render_view_route));
+    }
+
+    std::pair<int, int> launcher_and_prerender_id(i->launcher_child_id,
+                                                  i->prerender_id);
+    DCHECK_EQ(0u,
+              launcher_and_prerender_id_set.count(launcher_and_prerender_id));
+    launcher_and_prerender_id_set.insert(launcher_and_prerender_id);
+  }
+  DCHECK_GE(manager_->config().max_link_concurrency, added_prerender_count);
+  DCHECK_LE(CountRunningPrerenders(), added_prerender_count);
+
+  TimeTicks now = manager_->GetCurrentTimeTicks();
+
+  // Scan the list again, starting prerenders as our counts allow.
+  std::list<Prerender>::iterator next = prerenders_.begin();
+  while (next != prerenders_.end()) {
+    std::list<Prerender>::iterator i = next;
+    ++next;
+
+    if (added_prerender_count >= manager_->config().max_link_concurrency ||
+        added_prerender_count >= prerenders_.size()) {
+      // The system is already at its prerender concurrency limit.
+      return;
+    }
+
+    if (i->handle) {
+      // This prerender has already been added to the prerender manager.
+      continue;
+    }
+
+    std::pair<int, int> launcher_and_render_view_route(
+        i->launcher_child_id, i->render_view_route_id);
+    if (manager_->config().max_link_concurrency_per_launcher <=
+        running_launcher_and_render_view_route_set.count(
+            launcher_and_render_view_route)) {
+      // This prerender's launcher is already at its limit.
+      continue;
+    }
+
+    TimeDelta prerender_age = now - i->creation_time;
+    if (prerender_age >= manager_->config().max_wait_to_launch) {

[mmenke, 2012/12/28 18:25:33]

This should go before checking the launcher concurrency limit, since once this
has happened, we'll never launch the prerender, anyways.

Not exactly a huge/relevant optimization, but seems the logical thing to be
doing.

[gavinp, 2012/12/28 19:53:46]

Done.

+      // This prerender waited too long in the queue before launching.
+      prerenders_.erase(i);
+      continue;
+    }
+
+    PrerenderHandle* handle = manager_->AddPrerenderFromLinkRelPrerender(
+        i->launcher_child_id, i->render_view_route_id,
+        i->url, i->referrer, i->size);
+    if (!handle) {
+      // This prerender couldn't be launched, it's gone.
+      prerenders_.erase(i);
+      continue;
+    }
+
+    // We have successfully started a new prerender.
+    i->handle = handle;
+    ++added_prerender_count;
+    handle->SetObserver(this);
+    if (handle->IsPrerendering())
+      OnPrerenderStart(handle);
+
+    running_launcher_and_render_view_route_set.insert(
+        launcher_and_render_view_route);
+  }
+}
+
+PrerenderLinkManager::Prerender*
+PrerenderLinkManager::FindByLauncherChildIdAndPrerenderId(int launcher_child_id,
+                                                          int prerender_id) {
+  for (std::list<Prerender>::iterator i = prerenders_.begin();
+       i != prerenders_.end(); ++i) {
+    if (launcher_child_id == i->launcher_child_id &&
+        prerender_id == i->prerender_id) {
+      return &(*i);
+    }
+  }
+  return NULL;
+}
+
+PrerenderLinkManager::Prerender*
+PrerenderLinkManager::FindByPrerenderHandle(PrerenderHandle* prerender_handle) {
+  DCHECK(prerender_handle);
+  for (std::list<Prerender>::iterator i = prerenders_.begin();
+       i != prerenders_.end(); ++i) {
+    if (prerender_handle == i->handle)
+      return &(*i);
+  }
+  return NULL;
+}
+
+void PrerenderLinkManager::RemovePrerender(Prerender* prerender) {
+  for (std::list<Prerender>::iterator i = prerenders_.begin();
+       i != prerenders_.end(); ++i) {
+    if (&(*i) == prerender) {
+      scoped_ptr<PrerenderHandle> own_handle(i->handle);
+      i->handle = NULL;
+      prerenders_.erase(i);
+      return;
+    }
+  }
+  NOTREACHED();
+}
+
+void PrerenderLinkManager::Shutdown() {
+  has_shutdown_ = true;
 }
 
 // In practice, this is always called from either
 // PrerenderLinkManager::OnAddPrerender in the regular case, or in the pending
 // prerender case, from PrerenderHandle::AdoptPrerenderDataFrom.
 void PrerenderLinkManager::OnPrerenderStart(
     PrerenderHandle* prerender_handle) {
-  IdPairToPrerenderHandleMap::iterator it =
-      FindPrerenderHandle(prerender_handle);
-  DCHECK(it != ids_to_handle_map_.end());
-  const int child_id = it->first.first;
-  const int prerender_id = it->first.second;
-
-  Send(child_id, new PrerenderMsg_OnPrerenderStart(prerender_id));
+  Prerender* prerender = FindByPrerenderHandle(prerender_handle);
+  if (!prerender)
+    return;
+  Send(prerender->launcher_child_id,
+       new PrerenderMsg_OnPrerenderStart(prerender->prerender_id));
 }
 
 void PrerenderLinkManager::OnPrerenderAddAlias(
     PrerenderHandle* prerender_handle,
     const GURL& alias_url) {
-  IdPairToPrerenderHandleMap::iterator it =
-      FindPrerenderHandle(prerender_handle);
-  if (it == ids_to_handle_map_.end())
+  Prerender* prerender = FindByPrerenderHandle(prerender_handle);
+  if (!prerender)
     return;
-  const int child_id = it->first.first;
-  const int prerender_id = it->first.second;
-
-  Send(child_id, new PrerenderMsg_OnPrerenderAddAlias(prerender_id, alias_url));
+  Send(prerender->launcher_child_id,
+       new PrerenderMsg_OnPrerenderAddAlias(prerender->prerender_id,
+                                            alias_url));
 }
 
 void PrerenderLinkManager::OnPrerenderStop(
     PrerenderHandle* prerender_handle) {
-  IdPairToPrerenderHandleMap::iterator it =
-      FindPrerenderHandle(prerender_handle);
-  if (it == ids_to_handle_map_.end())
+  Prerender* prerender = FindByPrerenderHandle(prerender_handle);
+  if (!prerender)
     return;
-  const int child_id = it->first.first;
-  const int prerender_id = it->first.second;
 
-  Send(child_id, new PrerenderMsg_OnPrerenderStop(prerender_id));
-  RemovePrerender(it);
+  Send(prerender->launcher_child_id,
+       new PrerenderMsg_OnPrerenderStop(prerender->prerender_id));
+  RemovePrerender(prerender);
+  StartPrerenders();
 }
 
 }  // namespace prerender