Change multi-prerender API to include per launcher slots.

chrome/browser/prerender/prerender_link_manager.cc

Index: chrome/browser/prerender/prerender_link_manager.cc
diff --git a/chrome/browser/prerender/prerender_link_manager.cc b/chrome/browser/prerender/prerender_link_manager.cc
index da68f892f2c793cbf602a75554e4404cdc2f715b..89b228eadf893a01d742dba1d1e559fe8af46612 100644
--- a/chrome/browser/prerender/prerender_link_manager.cc
+++ b/chrome/browser/prerender/prerender_link_manager.cc
@@ -5,6 +5,7 @@
 #include "chrome/browser/prerender/prerender_link_manager.h"
 
 #include <limits>
+#include <set>
 #include <utility>
 
 #include "base/memory/scoped_ptr.h"
@@ -21,6 +22,8 @@
 #include "googleurl/src/gurl.h"
 #include "ui/gfx/size.h"
 
+using base::TimeDelta;
+using base::TimeTicks;
 using content::RenderViewHost;
 using content::SessionStorageNamespace;
 
@@ -41,131 +44,257 @@ void Send(int child_id, IPC::Message* raw_message) {
 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;
+  for (std::list<LinkPrerender>::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;
+    }
   }
 }
 
-bool PrerenderLinkManager::OnAddPrerender(int child_id,
+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;
+  DCHECK_EQ(static_cast<LinkPrerender*>(NULL),
+            FindByLauncherChildIdAndPrerenderId(launcher_child_id,
+                                                prerender_id));
+  LinkPrerender
+      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.";
+  LinkPrerender* prerender = FindByLauncherChildIdAndPrerenderId(child_id,
+                                                             prerender_id);
+  if (!prerender)
     return;
-  }
 
-  scoped_ptr<PrerenderHandle> prerender_handle(id_to_handle_iter->second);
-  ids_to_handle_map_.erase(id_to_handle_iter);
-  prerender_handle->OnCancel();
+  // 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);
 
-  // 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);
+  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())
+  LinkPrerender* prerender = FindByLauncherChildIdAndPrerenderId(child_id,
+                                                             prerender_id);
+  if (!prerender)
+    return;
+
+  if (!prerender->handle) {
+    RemovePrerender(prerender);
     return;
-  PrerenderHandle* prerender_handle = id_to_handle_iter->second;
-  prerender_handle->OnNavigateAway();
+  }
+
+  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<LinkPrerender>::iterator next = prerenders_.begin();
+  while (next != prerenders_.end()) {
+    std::list<LinkPrerender>::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);
+    if (child_id != it->launcher_child_id)
+      continue;
 
-    it = next;
+    const size_t running_prerender_count = CountRunningPrerenders();
+    OnAbandonPrerender(child_id, it->prerender_id);
+    DCHECK_EQ(running_prerender_count, CountRunningPrerenders());
   }
 }
 
+PrerenderLinkManager::LinkPrerender::LinkPrerender(
+    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::LinkPrerender::~LinkPrerender() {
+  DCHECK_EQ(static_cast<PrerenderHandle*>(NULL), handle)
+      << "The PrerenderHandle should be destroyed before its Prerender.";
+}
+
 bool PrerenderLinkManager::IsEmpty() const {
-  return ids_to_handle_map_.empty();
+  return prerenders_.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);
+size_t PrerenderLinkManager::CountRunningPrerenders() const {
+  size_t retval = 0;
+  for (std::list<LinkPrerender>::const_iterator i = prerenders_.begin();
+       i != prerenders_.end(); ++i) {
+    if (i->handle && i->handle->IsPrerendering())
+      ++retval;
+  }
+  return retval;
 }
 
-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;
+void PrerenderLinkManager::StartPrerenders() {
+  if (has_shutdown_)
+    return;
+
+  size_t total_started_prerender_count = 0;
+  std::multiset<std::pair<int, int> >
+      running_launcher_and_render_view_routes;
+
+  // 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<LinkPrerender>::iterator i = prerenders_.begin();
+       i != prerenders_.end(); ++i) {
+    if (i->handle) {
+      ++total_started_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_routes.insert(
+          launcher_and_render_view_route);
+      DCHECK_GE(manager_->config().max_link_concurrency_per_launcher,
+                running_launcher_and_render_view_routes.count(
+                    launcher_and_render_view_route));
+    }
+
+    DCHECK_EQ(&(*i), FindByLauncherChildIdAndPrerenderId(i->launcher_child_id,
+                                                         i->prerender_id));
+  }
+  DCHECK_GE(manager_->config().max_link_concurrency,
+            total_started_prerender_count);
+  DCHECK_LE(CountRunningPrerenders(), total_started_prerender_count);
+
+  TimeTicks now = manager_->GetCurrentTimeTicks();
+
+  // Scan the list again, starting prerenders as our counts allow.
+  std::list<LinkPrerender>::iterator next = prerenders_.begin();
+  while (next != prerenders_.end()) {
+    std::list<LinkPrerender>::iterator i = next;
+    ++next;
+
+    if (total_started_prerender_count >=
+            manager_->config().max_link_concurrency ||
+        total_started_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;
+    }
+
+    TimeDelta prerender_age = now - i->creation_time;
+    if (prerender_age >= manager_->config().max_wait_to_launch) {
+      // This prerender waited too long in the queue before launching.
+      prerenders_.erase(i);
+      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_routes.count(
+            launcher_and_render_view_route)) {
+      // This prerender's launcher is already at its limit.
+      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;
+    ++total_started_prerender_count;
+    handle->SetObserver(this);
+    if (handle->IsPrerendering())
+      OnPrerenderStart(handle);
+
+    running_launcher_and_render_view_routes.insert(
+        launcher_and_render_view_route);
   }
-  return ids_to_handle_map_.end();
+}
+
+PrerenderLinkManager::LinkPrerender*
+PrerenderLinkManager::FindByLauncherChildIdAndPrerenderId(int launcher_child_id,
+                                                          int prerender_id) {
+  for (std::list<LinkPrerender>::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::LinkPrerender*
+PrerenderLinkManager::FindByPrerenderHandle(PrerenderHandle* prerender_handle) {
+  DCHECK(prerender_handle);
+  for (std::list<LinkPrerender>::iterator i = prerenders_.begin();
+       i != prerenders_.end(); ++i) {
+    if (prerender_handle == i->handle)
+      return &(*i);
+  }
+  return NULL;
+}
+
+void PrerenderLinkManager::RemovePrerender(LinkPrerender* prerender) {
+  for (std::list<LinkPrerender>::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
@@ -173,39 +302,34 @@ PrerenderLinkManager::FindPrerenderHandle(
 // 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));
+  LinkPrerender* 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())
+  LinkPrerender* 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())
+  LinkPrerender* 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